rgobj.pas 66 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070
  1. {
  2. $Id$
  3. Copyright (c) 1998-2002 by Florian Klaempfl
  4. This unit implements the base class for the register allocator
  5. This program is free software; you can redistribute it and/or modify
  6. it under the terms of the GNU General Public License as published by
  7. the Free Software Foundation; either version 2 of the License, or
  8. (at your option) any later version.
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU General Public License for more details.
  13. You should have received a copy of the GNU General Public License
  14. along with this program; if not, write to the Free Software
  15. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16. ****************************************************************************
  17. }
  18. {$i fpcdefs.inc}
  19. { Allow duplicate allocations, can be used to get the .s file written }
  20. { $define ALLOWDUPREG}
  21. unit rgobj;
  22. interface
  23. uses
  24. cutils, cpubase,
  25. aasmbase,aasmtai,aasmcpu,
  26. cclasses,globtype,cgbase,node,
  27. {$ifdef delphi}
  28. dmisc,
  29. {$endif}
  30. cpuinfo
  31. ;
  32. type
  33. {
  34. regvarother_longintarray = array[tregisterindex] of longint;
  35. regvarother_booleanarray = array[tregisterindex] of boolean;
  36. regvarint_longintarray = array[first_int_supreg..last_int_supreg] of longint;
  37. regvarint_ptreearray = array[first_int_supreg..last_int_supreg] of tnode;
  38. }
  39. {
  40. The interference bitmap contains of 2 layers:
  41. layer 1 - 256*256 blocks with pointers to layer 2 blocks
  42. layer 2 - blocks of 32*256 (32 bytes = 256 bits)
  43. }
  44. Tinterferencebitmap2 = array[byte] of set of byte;
  45. Pinterferencebitmap2 = ^Tinterferencebitmap2;
  46. Tinterferencebitmap1 = array[byte] of Pinterferencebitmap2;
  47. pinterferencebitmap1 = ^tinterferencebitmap1;
  48. Tinterferencebitmap=class
  49. private
  50. maxx1,
  51. maxy1 : byte;
  52. fbitmap : pinterferencebitmap1;
  53. function getbitmap(x,y:tsuperregister):boolean;
  54. procedure setbitmap(x,y:tsuperregister;b:boolean);
  55. public
  56. constructor create;
  57. destructor destroy;override;
  58. property bitmap[x,y:tsuperregister]:boolean read getbitmap write setbitmap;default;
  59. end;
  60. Tmovelistheader=record
  61. count,
  62. maxcount,
  63. sorted_until : cardinal;
  64. end;
  65. Tmovelist=record
  66. header : Tmovelistheader;
  67. data : array[tsuperregister] of Tlinkedlistitem;
  68. end;
  69. Pmovelist=^Tmovelist;
  70. {In the register allocator we keep track of move instructions.
  71. These instructions are moved between five linked lists. There
  72. is also a linked list per register to keep track about the moves
  73. it is associated with. Because we need to determine quickly in
  74. which of the five lists it is we add anu enumeradtion to each
  75. move instruction.}
  76. Tmoveset=(ms_coalesced_moves,ms_constrained_moves,ms_frozen_moves,
  77. ms_worklist_moves,ms_active_moves);
  78. Tmoveins=class(Tlinkedlistitem)
  79. moveset:Tmoveset;
  80. x,y:Tsuperregister;
  81. end;
  82. Treginfoflag=(ri_coalesced,ri_selected);
  83. Treginfoflagset=set of Treginfoflag;
  84. Treginfo=record
  85. live_start,
  86. live_end : Tai;
  87. subreg : tsubregister;
  88. alias : Tsuperregister;
  89. { The register allocator assigns each register a colour }
  90. colour : Tsuperregister;
  91. movelist : Pmovelist;
  92. adjlist : Psuperregisterworklist;
  93. degree : TSuperregister;
  94. flags : Treginfoflagset;
  95. end;
  96. Preginfo=^TReginfo;
  97. tspillreginfo = record
  98. spillreg : tregister;
  99. orgreg : tsuperregister;
  100. tempreg : tregister;
  101. regread,regwritten, mustbespilled: boolean;
  102. end;
  103. tspillregsinfo = array[0..2] of tspillreginfo;
  104. {#------------------------------------------------------------------
  105. This class implements the default register allocator. It is used by the
  106. code generator to allocate and free registers which might be valid
  107. across nodes. It also contains utility routines related to registers.
  108. Some of the methods in this class should be overriden
  109. by cpu-specific implementations.
  110. --------------------------------------------------------------------}
  111. trgobj=class
  112. preserved_by_proc : tcpuregisterset;
  113. used_in_proc : tcpuregisterset;
  114. constructor create(Aregtype:Tregistertype;
  115. Adefaultsub:Tsubregister;
  116. const Ausable:array of tsuperregister;
  117. Afirst_imaginary:Tsuperregister;
  118. Apreserved_by_proc:Tcpuregisterset);
  119. destructor destroy;override;
  120. {# Allocate a register. An internalerror will be generated if there is
  121. no more free registers which can be allocated.}
  122. function getregister(list:Taasmoutput;subreg:Tsubregister):Tregister;virtual;
  123. {# Get the register specified.}
  124. procedure getcpuregister(list:Taasmoutput;r:Tregister);virtual;
  125. procedure ungetcpuregister(list:Taasmoutput;r:Tregister);virtual;
  126. {# Get multiple registers specified.}
  127. procedure alloccpuregisters(list:Taasmoutput;r:Tcpuregisterset);virtual;
  128. {# Free multiple registers specified.}
  129. procedure dealloccpuregisters(list:Taasmoutput;r:Tcpuregisterset);virtual;
  130. function uses_registers:boolean;virtual;
  131. procedure add_reg_instruction(instr:Tai;r:tregister);
  132. procedure add_move_instruction(instr:Taicpu);
  133. {# Do the register allocation.}
  134. procedure do_register_allocation(list:Taasmoutput;headertai:tai);virtual;
  135. { Adds an interference edge.
  136. don't move this to the protected section, the arm cg requires to access this (FK) }
  137. procedure add_edge(u,v:Tsuperregister);
  138. protected
  139. regtype : Tregistertype;
  140. { default subregister used }
  141. defaultsub : tsubregister;
  142. live_registers:Tsuperregisterworklist;
  143. { can be overriden to add cpu specific interferences }
  144. procedure add_cpu_interferences(p : tai);virtual;
  145. procedure add_constraints(reg:Tregister);virtual;
  146. function getregisterinline(list:Taasmoutput;subreg:Tsubregister):Tregister;
  147. procedure ungetregisterinline(list:Taasmoutput;r:Tregister);
  148. function get_spill_subreg(r : tregister) : tsubregister;virtual;
  149. function do_spill_replace(list:Taasmoutput;instr:taicpu;orgreg:tsuperregister;const spilltemp:treference):boolean;virtual;
  150. procedure do_spill_read(list:Taasmoutput;pos:tai;const spilltemp:treference;tempreg:tregister);virtual;
  151. procedure do_spill_written(list:Taasmoutput;pos:tai;const spilltemp:treference;tempreg:tregister);virtual;
  152. function instr_spill_register(list:Taasmoutput;
  153. instr:taicpu;
  154. const r:Tsuperregisterset;
  155. const spilltemplist:Tspill_temp_list): boolean;virtual;
  156. private
  157. {# First imaginary register.}
  158. first_imaginary : Tsuperregister;
  159. {# Highest register allocated until now.}
  160. reginfo : PReginfo;
  161. maxreginfo,
  162. maxreginfoinc,
  163. maxreg : Tsuperregister;
  164. usable_registers_cnt : word;
  165. usable_registers : array[0..maxcpuregister-1] of tsuperregister;
  166. ibitmap : Tinterferencebitmap;
  167. spillednodes,
  168. simplifyworklist,
  169. freezeworklist,
  170. spillworklist,
  171. coalescednodes,
  172. selectstack : tsuperregisterworklist;
  173. worklist_moves,
  174. active_moves,
  175. frozen_moves,
  176. coalesced_moves,
  177. constrained_moves : Tlinkedlist;
  178. {$ifdef EXTDEBUG}
  179. procedure writegraph(loopidx:longint);
  180. {$endif EXTDEBUG}
  181. {# Disposes of the reginfo array.}
  182. procedure dispose_reginfo;
  183. {# Prepare the register colouring.}
  184. procedure prepare_colouring;
  185. {# Clean up after register colouring.}
  186. procedure epilogue_colouring;
  187. {# Colour the registers; that is do the register allocation.}
  188. procedure colour_registers;
  189. procedure insert_regalloc_info(list:Taasmoutput;u:tsuperregister);
  190. procedure insert_regalloc_info_all(list:Taasmoutput);
  191. procedure generate_interference_graph(list:Taasmoutput;headertai:tai);
  192. procedure translate_registers(list:Taasmoutput);
  193. function spill_registers(list:Taasmoutput;headertai:tai):boolean;virtual;
  194. function getnewreg(subreg:tsubregister):tsuperregister;
  195. procedure add_edges_used(u:Tsuperregister);
  196. procedure add_to_movelist(u:Tsuperregister;data:Tlinkedlistitem);
  197. function move_related(n:Tsuperregister):boolean;
  198. procedure make_work_list;
  199. procedure sort_simplify_worklist;
  200. procedure enable_moves(n:Tsuperregister);
  201. procedure decrement_degree(m:Tsuperregister);
  202. procedure simplify;
  203. function get_alias(n:Tsuperregister):Tsuperregister;
  204. procedure add_worklist(u:Tsuperregister);
  205. function adjacent_ok(u,v:Tsuperregister):boolean;
  206. function conservative(u,v:Tsuperregister):boolean;
  207. procedure combine(u,v:Tsuperregister);
  208. procedure coalesce;
  209. procedure freeze_moves(u:Tsuperregister);
  210. procedure freeze;
  211. procedure select_spill;
  212. procedure assign_colours;
  213. procedure clear_interferences(u:Tsuperregister);
  214. end;
  215. const
  216. first_reg = 0;
  217. last_reg = high(tsuperregister)-1;
  218. maxspillingcounter = 20;
  219. implementation
  220. uses
  221. systems,
  222. globals,verbose,tgobj,procinfo;
  223. procedure sort_movelist(ml:Pmovelist);
  224. {Ok, sorting pointers is silly, but it does the job to make Trgobj.combine
  225. faster.}
  226. var h,i,p:word;
  227. t:Tlinkedlistitem;
  228. begin
  229. with ml^ do
  230. begin
  231. if header.count<2 then
  232. exit;
  233. p:=1;
  234. while 2*p<header.count do
  235. p:=2*p;
  236. while p<>0 do
  237. begin
  238. for h:=p to header.count-1 do
  239. begin
  240. i:=h;
  241. t:=data[i];
  242. repeat
  243. if ptrint(data[i-p])<=ptrint(t) then
  244. break;
  245. data[i]:=data[i-p];
  246. dec(i,p);
  247. until i<p;
  248. data[i]:=t;
  249. end;
  250. p:=p shr 1;
  251. end;
  252. header.sorted_until:=header.count-1;
  253. end;
  254. end;
  255. {******************************************************************************
  256. tinterferencebitmap
  257. ******************************************************************************}
  258. constructor tinterferencebitmap.create;
  259. begin
  260. inherited create;
  261. maxx1:=1;
  262. getmem(fbitmap,sizeof(tinterferencebitmap1)*2);
  263. fillchar(fbitmap^,sizeof(tinterferencebitmap1)*2,0);
  264. end;
  265. destructor tinterferencebitmap.destroy;
  266. var i,j:byte;
  267. begin
  268. for i:=0 to maxx1 do
  269. for j:=0 to maxy1 do
  270. if assigned(fbitmap[i,j]) then
  271. dispose(fbitmap[i,j]);
  272. freemem(fbitmap);
  273. end;
  274. function tinterferencebitmap.getbitmap(x,y:tsuperregister):boolean;
  275. var
  276. page : pinterferencebitmap2;
  277. begin
  278. result:=false;
  279. if (x shr 8>maxx1) then
  280. exit;
  281. page:=fbitmap[x shr 8,y shr 8];
  282. result:=assigned(page) and
  283. ((x and $ff) in page^[y and $ff]);
  284. end;
  285. procedure tinterferencebitmap.setbitmap(x,y:tsuperregister;b:boolean);
  286. var
  287. x1,y1 : byte;
  288. begin
  289. x1:=x shr 8;
  290. y1:=y shr 8;
  291. if x1>maxx1 then
  292. begin
  293. reallocmem(fbitmap,sizeof(tinterferencebitmap1)*(x1+1));
  294. fillchar(fbitmap[maxx1+1],sizeof(tinterferencebitmap1)*(x1-maxx1),0);
  295. maxx1:=x1;
  296. end;
  297. if not assigned(fbitmap[x1,y1]) then
  298. begin
  299. if y1>maxy1 then
  300. maxy1:=y1;
  301. new(fbitmap[x1,y1]);
  302. fillchar(fbitmap[x1,y1]^,sizeof(tinterferencebitmap2),0);
  303. end;
  304. if b then
  305. include(fbitmap[x1,y1]^[y and $ff],(x and $ff))
  306. else
  307. exclude(fbitmap[x1,y1]^[y and $ff],(x and $ff));
  308. end;
  309. {******************************************************************************
  310. trgobj
  311. ******************************************************************************}
  312. constructor trgobj.create(Aregtype:Tregistertype;
  313. Adefaultsub:Tsubregister;
  314. const Ausable:array of tsuperregister;
  315. Afirst_imaginary:Tsuperregister;
  316. Apreserved_by_proc:Tcpuregisterset);
  317. var
  318. i : Tsuperregister;
  319. begin
  320. { empty super register sets can cause very strange problems }
  321. if high(Ausable)=0 then
  322. internalerror(200210181);
  323. first_imaginary:=Afirst_imaginary;
  324. maxreg:=Afirst_imaginary;
  325. regtype:=Aregtype;
  326. defaultsub:=Adefaultsub;
  327. preserved_by_proc:=Apreserved_by_proc;
  328. used_in_proc:=[];
  329. live_registers.init;
  330. { Get reginfo for CPU registers }
  331. maxreginfo:=first_imaginary;
  332. maxreginfoinc:=16;
  333. worklist_moves:=Tlinkedlist.create;
  334. reginfo:=allocmem(first_imaginary*sizeof(treginfo));
  335. for i:=0 to first_imaginary-1 do
  336. begin
  337. reginfo[i].degree:=high(tsuperregister);
  338. reginfo[i].alias:=RS_INVALID;
  339. end;
  340. { Usable registers }
  341. fillchar(usable_registers,sizeof(usable_registers),0);
  342. for i:=low(Ausable) to high(Ausable) do
  343. usable_registers[i]:=Ausable[i];
  344. usable_registers_cnt:=high(Ausable)+1;
  345. { Initialize Worklists }
  346. spillednodes.init;
  347. simplifyworklist.init;
  348. freezeworklist.init;
  349. spillworklist.init;
  350. coalescednodes.init;
  351. selectstack.init;
  352. end;
  353. destructor trgobj.destroy;
  354. begin
  355. spillednodes.done;
  356. simplifyworklist.done;
  357. freezeworklist.done;
  358. spillworklist.done;
  359. coalescednodes.done;
  360. selectstack.done;
  361. live_registers.done;
  362. worklist_moves.free;
  363. dispose_reginfo;
  364. end;
  365. procedure Trgobj.dispose_reginfo;
  366. var i:Tsuperregister;
  367. begin
  368. if reginfo<>nil then
  369. begin
  370. for i:=0 to maxreg-1 do
  371. with reginfo[i] do
  372. begin
  373. if adjlist<>nil then
  374. dispose(adjlist,done);
  375. if movelist<>nil then
  376. dispose(movelist);
  377. end;
  378. freemem(reginfo);
  379. reginfo:=nil;
  380. end;
  381. end;
  382. function trgobj.getnewreg(subreg:tsubregister):tsuperregister;
  383. var
  384. oldmaxreginfo : tsuperregister;
  385. begin
  386. result:=maxreg;
  387. inc(maxreg);
  388. if maxreg>=last_reg then
  389. internalerror(200310146);
  390. if maxreg>=maxreginfo then
  391. begin
  392. oldmaxreginfo:=maxreginfo;
  393. inc(maxreginfo,maxreginfoinc);
  394. if maxreginfoinc<256 then
  395. maxreginfoinc:=maxreginfoinc*2;
  396. reallocmem(reginfo,maxreginfo*sizeof(treginfo));
  397. { Do we really need it to clear it ? At least for 1.0.x (PFV) }
  398. fillchar(reginfo[oldmaxreginfo],(maxreginfo-oldmaxreginfo)*sizeof(treginfo),0);
  399. end;
  400. reginfo[result].subreg:=subreg;
  401. end;
  402. function trgobj.getregister(list:Taasmoutput;subreg:Tsubregister):Tregister;
  403. begin
  404. {$ifdef EXTDEBUG}
  405. if reginfo=nil then
  406. InternalError(2004020901);
  407. {$endif EXTDEBUG}
  408. if defaultsub=R_SUBNONE then
  409. result:=newreg(regtype,getnewreg(R_SUBNONE),R_SUBNONE)
  410. else
  411. result:=newreg(regtype,getnewreg(subreg),subreg);
  412. end;
  413. function trgobj.uses_registers:boolean;
  414. begin
  415. result:=(maxreg>first_imaginary);
  416. end;
  417. procedure trgobj.ungetcpuregister(list:Taasmoutput;r:Tregister);
  418. begin
  419. if (getsupreg(r)>=first_imaginary) then
  420. InternalError(2004020901);
  421. list.concat(Tai_regalloc.dealloc(r,nil));
  422. end;
  423. procedure trgobj.getcpuregister(list:Taasmoutput;r:Tregister);
  424. var
  425. supreg:Tsuperregister;
  426. begin
  427. supreg:=getsupreg(r);
  428. if supreg>=first_imaginary then
  429. internalerror(2003121503);
  430. include(used_in_proc,supreg);
  431. list.concat(Tai_regalloc.alloc(r,nil));
  432. end;
  433. procedure trgobj.alloccpuregisters(list:Taasmoutput;r:Tcpuregisterset);
  434. var i:Tsuperregister;
  435. begin
  436. for i:=0 to first_imaginary-1 do
  437. if i in r then
  438. getcpuregister(list,newreg(regtype,i,defaultsub));
  439. end;
  440. procedure trgobj.dealloccpuregisters(list:Taasmoutput;r:Tcpuregisterset);
  441. var i:Tsuperregister;
  442. begin
  443. for i:=0 to first_imaginary-1 do
  444. if i in r then
  445. ungetcpuregister(list,newreg(regtype,i,defaultsub));
  446. end;
  447. procedure trgobj.do_register_allocation(list:Taasmoutput;headertai:tai);
  448. var
  449. spillingcounter:byte;
  450. endspill:boolean;
  451. i:Tsuperregister;
  452. begin
  453. { Insert regalloc info for imaginary registers }
  454. insert_regalloc_info_all(list);
  455. ibitmap:=tinterferencebitmap.create;
  456. generate_interference_graph(list,headertai);
  457. { Don't do the real allocation when -sr is passed }
  458. if (cs_no_regalloc in aktglobalswitches) then
  459. exit;
  460. {Do register allocation.}
  461. spillingcounter:=0;
  462. repeat
  463. prepare_colouring;
  464. colour_registers;
  465. epilogue_colouring;
  466. endspill:=true;
  467. if spillednodes.length<>0 then
  468. begin
  469. inc(spillingcounter);
  470. if spillingcounter>maxspillingcounter then
  471. exit;
  472. if spillingcounter>maxspillingcounter then
  473. internalerror(200309041);
  474. endspill:=not spill_registers(list,headertai);
  475. end;
  476. until endspill;
  477. ibitmap.free;
  478. translate_registers(list);
  479. dispose_reginfo;
  480. end;
  481. procedure trgobj.add_constraints(reg:Tregister);
  482. begin
  483. end;
  484. procedure trgobj.add_edge(u,v:Tsuperregister);
  485. {This procedure will add an edge to the virtual interference graph.}
  486. procedure addadj(u,v:Tsuperregister);
  487. begin
  488. with reginfo[u] do
  489. begin
  490. if adjlist=nil then
  491. new(adjlist,init);
  492. adjlist^.add(v);
  493. end;
  494. end;
  495. begin
  496. if (u<>v) and not(ibitmap[v,u]) then
  497. begin
  498. ibitmap[v,u]:=true;
  499. ibitmap[u,v]:=true;
  500. {Precoloured nodes are not stored in the interference graph.}
  501. if (u>=first_imaginary) then
  502. addadj(u,v);
  503. if (v>=first_imaginary) then
  504. addadj(v,u);
  505. end;
  506. end;
  507. procedure trgobj.add_edges_used(u:Tsuperregister);
  508. var i:word;
  509. begin
  510. with live_registers do
  511. if length>0 then
  512. for i:=0 to length-1 do
  513. add_edge(u,get_alias(buf^[i]));
  514. end;
  515. {$ifdef EXTDEBUG}
  516. procedure trgobj.writegraph(loopidx:longint);
  517. {This procedure writes out the current interference graph in the
  518. register allocator.}
  519. var f:text;
  520. i,j:Tsuperregister;
  521. begin
  522. assign(f,'igraph'+tostr(loopidx));
  523. rewrite(f);
  524. writeln(f,'Interference graph');
  525. writeln(f);
  526. write(f,' ');
  527. for i:=0 to 15 do
  528. for j:=0 to 15 do
  529. write(f,hexstr(i,1));
  530. writeln(f);
  531. write(f,' ');
  532. for i:=0 to 15 do
  533. write(f,'0123456789ABCDEF');
  534. writeln(f);
  535. for i:=0 to maxreg-1 do
  536. begin
  537. write(f,hexstr(i,2):4);
  538. for j:=0 to maxreg-1 do
  539. if ibitmap[i,j] then
  540. write(f,'*')
  541. else
  542. write(f,'-');
  543. writeln(f);
  544. end;
  545. close(f);
  546. end;
  547. {$endif EXTDEBUG}
  548. procedure trgobj.add_to_movelist(u:Tsuperregister;data:Tlinkedlistitem);
  549. begin
  550. with reginfo[u] do
  551. begin
  552. if movelist=nil then
  553. begin
  554. getmem(movelist,sizeof(tmovelistheader)+60*sizeof(pointer));
  555. movelist^.header.maxcount:=60;
  556. movelist^.header.count:=0;
  557. movelist^.header.sorted_until:=0;
  558. end
  559. else
  560. begin
  561. if movelist^.header.count>=movelist^.header.maxcount then
  562. begin
  563. movelist^.header.maxcount:=movelist^.header.maxcount*2;
  564. reallocmem(movelist,sizeof(tmovelistheader)+movelist^.header.maxcount*sizeof(pointer));
  565. end;
  566. end;
  567. movelist^.data[movelist^.header.count]:=data;
  568. inc(movelist^.header.count);
  569. end;
  570. end;
  571. procedure trgobj.add_reg_instruction(instr:Tai;r:tregister);
  572. var
  573. supreg : tsuperregister;
  574. begin
  575. supreg:=getsupreg(r);
  576. if supreg>=first_imaginary then
  577. with reginfo[supreg] do
  578. begin
  579. if not assigned(live_start) then
  580. live_start:=instr;
  581. live_end:=instr;
  582. end;
  583. end;
  584. procedure trgobj.add_move_instruction(instr:Taicpu);
  585. {This procedure notifies a certain as a move instruction so the
  586. register allocator can try to eliminate it.}
  587. var i:Tmoveins;
  588. ssupreg,dsupreg:Tsuperregister;
  589. begin
  590. {$ifdef extdebug}
  591. if (instr.oper[O_MOV_SOURCE]^.typ<>top_reg) or
  592. (instr.oper[O_MOV_DEST]^.typ<>top_reg) then
  593. internalerror(200311291);
  594. {$endif}
  595. i:=Tmoveins.create;
  596. i.moveset:=ms_worklist_moves;
  597. worklist_moves.insert(i);
  598. ssupreg:=getsupreg(instr.oper[O_MOV_SOURCE]^.reg);
  599. add_to_movelist(ssupreg,i);
  600. dsupreg:=getsupreg(instr.oper[O_MOV_DEST]^.reg);
  601. if ssupreg<>dsupreg then
  602. {Avoid adding the same move instruction twice to a single register.}
  603. add_to_movelist(dsupreg,i);
  604. i.x:=ssupreg;
  605. i.y:=dsupreg;
  606. end;
  607. function trgobj.move_related(n:Tsuperregister):boolean;
  608. var i:cardinal;
  609. begin
  610. move_related:=false;
  611. with reginfo[n] do
  612. if movelist<>nil then
  613. with movelist^ do
  614. for i:=0 to header.count-1 do
  615. if Tmoveins(data[i]).moveset in [ms_worklist_moves,ms_active_moves] then
  616. begin
  617. move_related:=true;
  618. break;
  619. end;
  620. end;
  621. procedure Trgobj.sort_simplify_worklist;
  622. {Sorts the simplifyworklist by the number of interferences the
  623. registers in it cause. This allows simplify to execute in
  624. constant time.}
  625. var p,h,i,leni,lent:word;
  626. t:Tsuperregister;
  627. adji,adjt:Psuperregisterworklist;
  628. begin
  629. with simplifyworklist do
  630. begin
  631. if length<2 then
  632. exit;
  633. p:=1;
  634. while 2*p<length do
  635. p:=2*p;
  636. while p<>0 do
  637. begin
  638. for h:=p to length-1 do
  639. begin
  640. i:=h;
  641. t:=buf^[i];
  642. adjt:=reginfo[buf^[i]].adjlist;
  643. lent:=0;
  644. if adjt<>nil then
  645. lent:=adjt^.length;
  646. repeat
  647. adji:=reginfo[buf^[i-p]].adjlist;
  648. leni:=0;
  649. if adji<>nil then
  650. leni:=adji^.length;
  651. if leni<=lent then
  652. break;
  653. buf^[i]:=buf^[i-p];
  654. dec(i,p)
  655. until i<p;
  656. buf^[i]:=t;
  657. end;
  658. p:=p shr 1;
  659. end;
  660. end;
  661. end;
  662. procedure trgobj.make_work_list;
  663. var n:Tsuperregister;
  664. begin
  665. {If we have 7 cpu registers, and the degree of a node is 7, we cannot
  666. assign it to any of the registers, thus it is significant.}
  667. for n:=first_imaginary to maxreg-1 do
  668. with reginfo[n] do
  669. begin
  670. if adjlist=nil then
  671. degree:=0
  672. else
  673. degree:=adjlist^.length;
  674. if degree>=usable_registers_cnt then
  675. spillworklist.add(n)
  676. else if move_related(n) then
  677. freezeworklist.add(n)
  678. else
  679. simplifyworklist.add(n);
  680. end;
  681. sort_simplify_worklist;
  682. end;
  683. procedure trgobj.prepare_colouring;
  684. var i:word;
  685. begin
  686. make_work_list;
  687. active_moves:=Tlinkedlist.create;
  688. frozen_moves:=Tlinkedlist.create;
  689. coalesced_moves:=Tlinkedlist.create;
  690. constrained_moves:=Tlinkedlist.create;
  691. selectstack.clear;
  692. end;
  693. procedure trgobj.enable_moves(n:Tsuperregister);
  694. var m:Tlinkedlistitem;
  695. i:cardinal;
  696. begin
  697. with reginfo[n] do
  698. if movelist<>nil then
  699. for i:=0 to movelist^.header.count-1 do
  700. begin
  701. m:=movelist^.data[i];
  702. if Tmoveins(m).moveset in [ms_worklist_moves,ms_active_moves] then
  703. if Tmoveins(m).moveset=ms_active_moves then
  704. begin
  705. {Move m from the set active_moves to the set worklist_moves.}
  706. active_moves.remove(m);
  707. Tmoveins(m).moveset:=ms_worklist_moves;
  708. worklist_moves.concat(m);
  709. end;
  710. end;
  711. end;
  712. procedure Trgobj.decrement_degree(m:Tsuperregister);
  713. var adj : Psuperregisterworklist;
  714. n : tsuperregister;
  715. d,i : word;
  716. begin
  717. with reginfo[m] do
  718. begin
  719. d:=degree;
  720. if d=0 then
  721. internalerror(200312151);
  722. dec(degree);
  723. if d=usable_registers_cnt then
  724. begin
  725. {Enable moves for m.}
  726. enable_moves(m);
  727. {Enable moves for adjacent.}
  728. adj:=adjlist;
  729. if adj<>nil then
  730. for i:=1 to adj^.length do
  731. begin
  732. n:=adj^.buf^[i-1];
  733. if reginfo[n].flags*[ri_selected,ri_coalesced]<>[] then
  734. enable_moves(n);
  735. end;
  736. {Remove the node from the spillworklist.}
  737. if not spillworklist.delete(m) then
  738. internalerror(200310145);
  739. if move_related(m) then
  740. freezeworklist.add(m)
  741. else
  742. simplifyworklist.add(m);
  743. end;
  744. end;
  745. end;
  746. procedure trgobj.simplify;
  747. var adj : Psuperregisterworklist;
  748. m,n : Tsuperregister;
  749. i : word;
  750. begin
  751. {We take the element with the least interferences out of the
  752. simplifyworklist. Since the simplifyworklist is now sorted, we
  753. no longer need to search, but we can simply take the first element.}
  754. m:=simplifyworklist.get;
  755. {Push it on the selectstack.}
  756. selectstack.add(m);
  757. with reginfo[m] do
  758. begin
  759. include(flags,ri_selected);
  760. adj:=adjlist;
  761. end;
  762. if adj<>nil then
  763. for i:=1 to adj^.length do
  764. begin
  765. n:=adj^.buf^[i-1];
  766. if (n>=first_imaginary) and
  767. (reginfo[n].flags*[ri_selected,ri_coalesced]=[]) then
  768. decrement_degree(n);
  769. end;
  770. end;
  771. function trgobj.get_alias(n:Tsuperregister):Tsuperregister;
  772. begin
  773. while ri_coalesced in reginfo[n].flags do
  774. n:=reginfo[n].alias;
  775. get_alias:=n;
  776. end;
  777. procedure trgobj.add_worklist(u:Tsuperregister);
  778. begin
  779. if (u>=first_imaginary) and
  780. (not move_related(u)) and
  781. (reginfo[u].degree<usable_registers_cnt) then
  782. begin
  783. if not freezeworklist.delete(u) then
  784. internalerror(200308161); {must be found}
  785. simplifyworklist.add(u);
  786. end;
  787. end;
  788. function trgobj.adjacent_ok(u,v:Tsuperregister):boolean;
  789. {Check wether u and v should be coalesced. u is precoloured.}
  790. function ok(t,r:Tsuperregister):boolean;
  791. begin
  792. ok:=(t<first_imaginary) or
  793. (reginfo[t].degree<usable_registers_cnt) or
  794. ibitmap[r,t];
  795. end;
  796. var adj : Psuperregisterworklist;
  797. i : word;
  798. n : tsuperregister;
  799. begin
  800. with reginfo[v] do
  801. begin
  802. adjacent_ok:=true;
  803. adj:=adjlist;
  804. if adj<>nil then
  805. for i:=1 to adj^.length do
  806. begin
  807. n:=adj^.buf^[i-1];
  808. if (flags*[ri_coalesced,ri_selected]=[]) and not ok(n,u) then
  809. begin
  810. adjacent_ok:=false;
  811. break;
  812. end;
  813. end;
  814. end;
  815. end;
  816. function trgobj.conservative(u,v:Tsuperregister):boolean;
  817. var adj : Psuperregisterworklist;
  818. done : Tsuperregisterset; {To prevent that we count nodes twice.}
  819. i,k:word;
  820. n : tsuperregister;
  821. begin
  822. k:=0;
  823. supregset_reset(done,false,maxreg);
  824. with reginfo[u] do
  825. begin
  826. adj:=adjlist;
  827. if adj<>nil then
  828. for i:=1 to adj^.length do
  829. begin
  830. n:=adj^.buf^[i-1];
  831. if flags*[ri_coalesced,ri_selected]=[] then
  832. begin
  833. supregset_include(done,n);
  834. if reginfo[n].degree>=usable_registers_cnt then
  835. inc(k);
  836. end;
  837. end;
  838. end;
  839. adj:=reginfo[v].adjlist;
  840. if adj<>nil then
  841. for i:=1 to adj^.length do
  842. begin
  843. n:=adj^.buf^[i-1];
  844. if not supregset_in(done,n) and
  845. (reginfo[n].degree>=usable_registers_cnt) and
  846. (reginfo[u].flags*[ri_coalesced,ri_selected]=[]) then
  847. inc(k);
  848. end;
  849. conservative:=(k<usable_registers_cnt);
  850. end;
  851. procedure trgobj.combine(u,v:Tsuperregister);
  852. var adj : Psuperregisterworklist;
  853. i,n,p,q:cardinal;
  854. t : tsuperregister;
  855. searched:Tlinkedlistitem;
  856. label l1;
  857. begin
  858. if not freezeworklist.delete(v) then
  859. spillworklist.delete(v);
  860. coalescednodes.add(v);
  861. include(reginfo[v].flags,ri_coalesced);
  862. reginfo[v].alias:=u;
  863. {Combine both movelists. Since the movelists are sets, only add
  864. elements that are not already present. The movelists cannot be
  865. empty by definition; nodes are only coalesced if there is a move
  866. between them. To prevent quadratic time blowup (movelists of
  867. especially machine registers can get very large because of moves
  868. generated during calls) we need to go into disgusting complexity.
  869. (See webtbs/tw2242 for an example that stresses this.)
  870. We want to sort the movelist to be able to search logarithmically.
  871. Unfortunately, sorting the movelist every time before searching
  872. is counter-productive, since the movelist usually grows with a few
  873. items at a time. Therefore, we split the movelist into a sorted
  874. and an unsorted part and search through both. If the unsorted part
  875. becomes too large, we sort.}
  876. if assigned(reginfo[u].movelist) then
  877. begin
  878. {We have to weigh the cost of sorting the list against searching
  879. the cost of the unsorted part. I use factor of 8 here; if the
  880. number of items is less than 8 times the numer of unsorted items,
  881. we'll sort the list.}
  882. with reginfo[u].movelist^ do
  883. if header.count<8*(header.count-header.sorted_until) then
  884. sort_movelist(reginfo[u].movelist);
  885. if assigned(reginfo[v].movelist) then
  886. begin
  887. for n:=0 to reginfo[v].movelist^.header.count-1 do
  888. begin
  889. {Binary search the sorted part of the list.}
  890. searched:=reginfo[v].movelist^.data[n];
  891. p:=0;
  892. q:=reginfo[u].movelist^.header.sorted_until;
  893. i:=0;
  894. if q<>0 then
  895. repeat
  896. i:=(p+q) shr 1;
  897. if ptrint(searched)>ptrint(reginfo[u].movelist^.data[i]) then
  898. p:=i+1
  899. else
  900. q:=i;
  901. until p=q;
  902. with reginfo[u].movelist^ do
  903. if searched<>data[i] then
  904. begin
  905. {Linear search the unsorted part of the list.}
  906. for i:=header.sorted_until+1 to header.count-1 do
  907. if searched=data[i] then
  908. goto l1;
  909. {Not found -> add}
  910. add_to_movelist(u,searched);
  911. l1:
  912. end;
  913. end;
  914. end;
  915. end;
  916. enable_moves(v);
  917. adj:=reginfo[v].adjlist;
  918. if adj<>nil then
  919. for i:=1 to adj^.length do
  920. begin
  921. t:=adj^.buf^[i-1];
  922. with reginfo[t] do
  923. if not(ri_coalesced in flags) then
  924. begin
  925. {t has a connection to v. Since we are adding v to u, we
  926. need to connect t to u. However, beware if t was already
  927. connected to u...}
  928. if (ibitmap[t,u]) and not (ri_selected in flags) then
  929. {... because in that case, we are actually removing an edge
  930. and the degree of t decreases.}
  931. decrement_degree(t)
  932. else
  933. begin
  934. add_edge(t,u);
  935. {We have added an edge to t and u. So their degree increases.
  936. However, v is added to u. That means its neighbours will
  937. no longer point to v, but to u instead. Therefore, only the
  938. degree of u increases.}
  939. if (u>=first_imaginary) and not (ri_selected in flags) then
  940. inc(reginfo[u].degree);
  941. end;
  942. end;
  943. end;
  944. if (reginfo[u].degree>=usable_registers_cnt) and freezeworklist.delete(u) then
  945. spillworklist.add(u);
  946. end;
  947. procedure trgobj.coalesce;
  948. var m:Tmoveins;
  949. x,y,u,v:Tsuperregister;
  950. begin
  951. m:=Tmoveins(worklist_moves.getfirst);
  952. x:=get_alias(m.x);
  953. y:=get_alias(m.y);
  954. if (y<first_imaginary) then
  955. begin
  956. u:=y;
  957. v:=x;
  958. end
  959. else
  960. begin
  961. u:=x;
  962. v:=y;
  963. end;
  964. if (u=v) then
  965. begin
  966. m.moveset:=ms_coalesced_moves; {Already coalesced.}
  967. coalesced_moves.insert(m);
  968. add_worklist(u);
  969. end
  970. {Do u and v interfere? In that case the move is constrained. Two
  971. precoloured nodes interfere allways. If v is precoloured, by the above
  972. code u is precoloured, thus interference...}
  973. else if (v<first_imaginary) or ibitmap[u,v] then
  974. begin
  975. m.moveset:=ms_constrained_moves; {Cannot coalesce yet...}
  976. constrained_moves.insert(m);
  977. add_worklist(u);
  978. add_worklist(v);
  979. end
  980. {Next test: is it possible and a good idea to coalesce??}
  981. else if ((u<first_imaginary) and adjacent_ok(u,v)) or
  982. ((u>=first_imaginary) and conservative(u,v)) then
  983. begin
  984. m.moveset:=ms_coalesced_moves; {Move coalesced!}
  985. coalesced_moves.insert(m);
  986. combine(u,v);
  987. add_worklist(u);
  988. end
  989. else
  990. begin
  991. m.moveset:=ms_active_moves;
  992. active_moves.insert(m);
  993. end;
  994. end;
  995. procedure trgobj.freeze_moves(u:Tsuperregister);
  996. var i:cardinal;
  997. m:Tlinkedlistitem;
  998. v,x,y:Tsuperregister;
  999. begin
  1000. if reginfo[u].movelist<>nil then
  1001. for i:=0 to reginfo[u].movelist^.header.count-1 do
  1002. begin
  1003. m:=reginfo[u].movelist^.data[i];
  1004. if Tmoveins(m).moveset in [ms_worklist_moves,ms_active_moves] then
  1005. begin
  1006. x:=Tmoveins(m).x;
  1007. y:=Tmoveins(m).y;
  1008. if get_alias(y)=get_alias(u) then
  1009. v:=get_alias(x)
  1010. else
  1011. v:=get_alias(y);
  1012. {Move m from active_moves/worklist_moves to frozen_moves.}
  1013. if Tmoveins(m).moveset=ms_active_moves then
  1014. active_moves.remove(m)
  1015. else
  1016. worklist_moves.remove(m);
  1017. Tmoveins(m).moveset:=ms_frozen_moves;
  1018. frozen_moves.insert(m);
  1019. if (v>=first_imaginary) and not(move_related(v)) and
  1020. (reginfo[v].degree<usable_registers_cnt) then
  1021. begin
  1022. freezeworklist.delete(v);
  1023. simplifyworklist.add(v);
  1024. end;
  1025. end;
  1026. end;
  1027. end;
  1028. procedure trgobj.freeze;
  1029. var n:Tsuperregister;
  1030. begin
  1031. { We need to take a random element out of the freezeworklist. We take
  1032. the last element. Dirty code! }
  1033. n:=freezeworklist.get;
  1034. {Add it to the simplifyworklist.}
  1035. simplifyworklist.add(n);
  1036. freeze_moves(n);
  1037. end;
  1038. procedure trgobj.select_spill;
  1039. var
  1040. n : tsuperregister;
  1041. adj : psuperregisterworklist;
  1042. max,p,i:word;
  1043. begin
  1044. { We must look for the element with the most interferences in the
  1045. spillworklist. This is required because those registers are creating
  1046. the most conflicts and keeping them in a register will not reduce the
  1047. complexity and even can cause the help registers for the spilling code
  1048. to get too much conflicts with the result that the spilling code
  1049. will never converge (PFV) }
  1050. max:=0;
  1051. p:=0;
  1052. with spillworklist do
  1053. begin
  1054. {Safe: This procedure is only called if length<>0}
  1055. for i:=0 to length-1 do
  1056. begin
  1057. adj:=reginfo[buf^[i]].adjlist;
  1058. if assigned(adj) and (adj^.length>max) then
  1059. begin
  1060. p:=i;
  1061. max:=adj^.length;
  1062. end;
  1063. end;
  1064. n:=buf^[p];
  1065. deleteidx(p);
  1066. end;
  1067. simplifyworklist.add(n);
  1068. freeze_moves(n);
  1069. end;
  1070. procedure trgobj.assign_colours;
  1071. {Assign_colours assigns the actual colours to the registers.}
  1072. var adj : Psuperregisterworklist;
  1073. i,j,k : word;
  1074. n,a,c : Tsuperregister;
  1075. colourednodes : Tsuperregisterset;
  1076. adj_colours:set of 0..255;
  1077. found : boolean;
  1078. begin
  1079. spillednodes.clear;
  1080. {Reset colours}
  1081. for n:=0 to maxreg-1 do
  1082. reginfo[n].colour:=n;
  1083. {Colour the cpu registers...}
  1084. supregset_reset(colourednodes,false,maxreg);
  1085. for n:=0 to first_imaginary-1 do
  1086. supregset_include(colourednodes,n);
  1087. {Now colour the imaginary registers on the select-stack.}
  1088. for i:=selectstack.length downto 1 do
  1089. begin
  1090. n:=selectstack.buf^[i-1];
  1091. {Create a list of colours that we cannot assign to n.}
  1092. adj_colours:=[];
  1093. adj:=reginfo[n].adjlist;
  1094. if adj<>nil then
  1095. for j:=0 to adj^.length-1 do
  1096. begin
  1097. a:=get_alias(adj^.buf^[j]);
  1098. if supregset_in(colourednodes,a) and (reginfo[a].colour<=255) then
  1099. include(adj_colours,reginfo[a].colour);
  1100. end;
  1101. include(adj_colours,RS_STACK_POINTER_REG);
  1102. {Assume a spill by default...}
  1103. found:=false;
  1104. {Search for a colour not in this list.}
  1105. for k:=0 to usable_registers_cnt-1 do
  1106. begin
  1107. c:=usable_registers[k];
  1108. if not(c in adj_colours) then
  1109. begin
  1110. reginfo[n].colour:=c;
  1111. found:=true;
  1112. supregset_include(colourednodes,n);
  1113. include(used_in_proc,c);
  1114. break;
  1115. end;
  1116. end;
  1117. if not found then
  1118. spillednodes.add(n);
  1119. end;
  1120. {Finally colour the nodes that were coalesced.}
  1121. for i:=1 to coalescednodes.length do
  1122. begin
  1123. n:=coalescednodes.buf^[i-1];
  1124. k:=get_alias(n);
  1125. reginfo[n].colour:=reginfo[k].colour;
  1126. if reginfo[k].colour<maxcpuregister then
  1127. include(used_in_proc,reginfo[k].colour);
  1128. end;
  1129. end;
  1130. procedure trgobj.colour_registers;
  1131. begin
  1132. repeat
  1133. if simplifyworklist.length<>0 then
  1134. simplify
  1135. else if not(worklist_moves.empty) then
  1136. coalesce
  1137. else if freezeworklist.length<>0 then
  1138. freeze
  1139. else if spillworklist.length<>0 then
  1140. select_spill;
  1141. until (simplifyworklist.length=0) and
  1142. worklist_moves.empty and
  1143. (freezeworklist.length=0) and
  1144. (spillworklist.length=0);
  1145. assign_colours;
  1146. end;
  1147. procedure trgobj.epilogue_colouring;
  1148. var
  1149. i : Tsuperregister;
  1150. begin
  1151. worklist_moves.clear;
  1152. active_moves.destroy;
  1153. active_moves:=nil;
  1154. frozen_moves.destroy;
  1155. frozen_moves:=nil;
  1156. coalesced_moves.destroy;
  1157. coalesced_moves:=nil;
  1158. constrained_moves.destroy;
  1159. constrained_moves:=nil;
  1160. for i:=0 to maxreg-1 do
  1161. with reginfo[i] do
  1162. if movelist<>nil then
  1163. begin
  1164. dispose(movelist);
  1165. movelist:=nil;
  1166. end;
  1167. end;
  1168. procedure trgobj.clear_interferences(u:Tsuperregister);
  1169. {Remove node u from the interference graph and remove all collected
  1170. move instructions it is associated with.}
  1171. var i : word;
  1172. v : Tsuperregister;
  1173. adj,adj2 : Psuperregisterworklist;
  1174. begin
  1175. adj:=reginfo[u].adjlist;
  1176. if adj<>nil then
  1177. begin
  1178. for i:=1 to adj^.length do
  1179. begin
  1180. v:=adj^.buf^[i-1];
  1181. {Remove (u,v) and (v,u) from bitmap.}
  1182. ibitmap[u,v]:=false;
  1183. ibitmap[v,u]:=false;
  1184. {Remove (v,u) from adjacency list.}
  1185. adj2:=reginfo[v].adjlist;
  1186. if adj2<>nil then
  1187. begin
  1188. adj2^.delete(u);
  1189. if adj2^.length=0 then
  1190. begin
  1191. dispose(adj2,done);
  1192. reginfo[v].adjlist:=nil;
  1193. end;
  1194. end;
  1195. end;
  1196. {Remove ( u,* ) from adjacency list.}
  1197. dispose(adj,done);
  1198. reginfo[u].adjlist:=nil;
  1199. end;
  1200. end;
  1201. function trgobj.getregisterinline(list:Taasmoutput;subreg:Tsubregister):Tregister;
  1202. var
  1203. p : Tsuperregister;
  1204. r : Tregister;
  1205. begin
  1206. p:=getnewreg(subreg);
  1207. live_registers.add(p);
  1208. result:=newreg(regtype,p,subreg);
  1209. add_edges_used(p);
  1210. add_constraints(result);
  1211. end;
  1212. procedure trgobj.ungetregisterinline(list:Taasmoutput;r:Tregister);
  1213. var
  1214. supreg:Tsuperregister;
  1215. begin
  1216. supreg:=getsupreg(r);
  1217. live_registers.delete(supreg);
  1218. insert_regalloc_info(list,supreg);
  1219. end;
  1220. procedure trgobj.insert_regalloc_info(list:Taasmoutput;u:tsuperregister);
  1221. var
  1222. p : tai;
  1223. r : tregister;
  1224. begin
  1225. { Insert regallocs for all imaginary registers }
  1226. with reginfo[u] do
  1227. begin
  1228. r:=newreg(regtype,u,subreg);
  1229. if assigned(live_start) then
  1230. begin
  1231. list.insertbefore(Tai_regalloc.alloc(r,live_start),live_start);
  1232. { Insert live end deallocation before reg allocations
  1233. to reduce conflicts }
  1234. p:=live_end;
  1235. while assigned(p) and
  1236. assigned(p.previous) and
  1237. (tai(p.previous).typ=ait_regalloc) and
  1238. (tai_regalloc(p.previous).ratype=ra_alloc) and
  1239. (tai_regalloc(p.previous).reg<>r) do
  1240. p:=tai(p.previous);
  1241. { , but add release after sync }
  1242. if assigned(p) and
  1243. (p.typ=ait_regalloc) and
  1244. (tai_regalloc(p).ratype=ra_sync) then
  1245. p:=tai(p.next);
  1246. if assigned(p) then
  1247. list.insertbefore(Tai_regalloc.dealloc(r,live_end),p)
  1248. else
  1249. list.concat(Tai_regalloc.dealloc(r,live_end));
  1250. end
  1251. {$ifdef EXTDEBUG}
  1252. else
  1253. Comment(V_Warning,'Register '+std_regname(r)+' not used');
  1254. {$endif EXTDEBUG}
  1255. end;
  1256. end;
  1257. procedure trgobj.insert_regalloc_info_all(list:Taasmoutput);
  1258. var
  1259. supreg : tsuperregister;
  1260. begin
  1261. { Insert regallocs for all imaginary registers }
  1262. for supreg:=first_imaginary to maxreg-1 do
  1263. insert_regalloc_info(list,supreg);
  1264. end;
  1265. procedure trgobj.add_cpu_interferences(p : tai);
  1266. begin
  1267. end;
  1268. procedure trgobj.generate_interference_graph(list:Taasmoutput;headertai:tai);
  1269. var
  1270. p : tai;
  1271. i : integer;
  1272. supreg : tsuperregister;
  1273. begin
  1274. { All allocations are available. Now we can generate the
  1275. interference graph. Walk through all instructions, we can
  1276. start with the headertai, because before the header tai is
  1277. only symbols. }
  1278. live_registers.clear;
  1279. p:=headertai;
  1280. while assigned(p) do
  1281. begin
  1282. if p.typ=ait_regalloc then
  1283. with Tai_regalloc(p) do
  1284. begin
  1285. if (getregtype(reg)=regtype) then
  1286. begin
  1287. supreg:=getsupreg(reg);
  1288. case ratype of
  1289. ra_alloc :
  1290. begin
  1291. live_registers.add(supreg);
  1292. add_edges_used(supreg);
  1293. end;
  1294. ra_dealloc :
  1295. begin
  1296. live_registers.delete(supreg);
  1297. add_edges_used(supreg);
  1298. end;
  1299. end;
  1300. { constraints needs always to be updated }
  1301. add_constraints(reg);
  1302. end;
  1303. end;
  1304. add_cpu_interferences(p);
  1305. p:=Tai(p.next);
  1306. end;
  1307. {$ifdef EXTDEBUG}
  1308. if live_registers.length>0 then
  1309. begin
  1310. for i:=0 to live_registers.length-1 do
  1311. begin
  1312. { Only report for imaginary registers }
  1313. if live_registers.buf^[i]>=first_imaginary then
  1314. Comment(V_Warning,'Register '+std_regname(newreg(R_INTREGISTER,live_registers.buf^[i],defaultsub))+' not released');
  1315. end;
  1316. end;
  1317. {$endif}
  1318. end;
  1319. procedure Trgobj.translate_registers(list:taasmoutput);
  1320. var
  1321. hp,p,q:Tai;
  1322. i:shortint;
  1323. {$ifdef arm}
  1324. so:pshifterop;
  1325. {$endif arm}
  1326. begin
  1327. { Leave when no imaginary registers are used }
  1328. if maxreg<=first_imaginary then
  1329. exit;
  1330. p:=Tai(list.first);
  1331. while assigned(p) do
  1332. begin
  1333. case p.typ of
  1334. ait_regalloc:
  1335. with Tai_regalloc(p) do
  1336. begin
  1337. { Only alloc/dealloc is needed for the optimizer, remove
  1338. other regalloc }
  1339. if not(ratype in [ra_alloc,ra_dealloc]) then
  1340. begin
  1341. q:=Tai(next);
  1342. list.remove(p);
  1343. p.free;
  1344. p:=q;
  1345. continue;
  1346. end
  1347. else
  1348. begin
  1349. if (getregtype(reg)=regtype) then
  1350. setsupreg(reg,reginfo[getsupreg(reg)].colour);
  1351. {
  1352. Remove sequences of release and
  1353. allocation of the same register like. Other combinations
  1354. of release/allocate need to stay in the list.
  1355. # Register X released
  1356. # Register X allocated
  1357. }
  1358. if assigned(previous) and
  1359. (ratype=ra_alloc) and
  1360. (Tai(previous).typ=ait_regalloc) and
  1361. (Tai_regalloc(previous).reg=reg) and
  1362. (Tai_regalloc(previous).ratype=ra_dealloc) then
  1363. begin
  1364. q:=Tai(next);
  1365. hp:=tai(previous);
  1366. list.remove(hp);
  1367. hp.free;
  1368. list.remove(p);
  1369. p.free;
  1370. p:=q;
  1371. continue;
  1372. end;
  1373. end;
  1374. end;
  1375. ait_instruction:
  1376. with Taicpu(p) do
  1377. begin
  1378. aktfilepos:=fileinfo;
  1379. for i:=0 to ops-1 do
  1380. with oper[i]^ do
  1381. case typ of
  1382. Top_reg:
  1383. if (getregtype(reg)=regtype) then
  1384. setsupreg(reg,reginfo[getsupreg(reg)].colour);
  1385. Top_ref:
  1386. begin
  1387. if regtype=R_INTREGISTER then
  1388. with ref^ do
  1389. begin
  1390. if base<>NR_NO then
  1391. setsupreg(base,reginfo[getsupreg(base)].colour);
  1392. if index<>NR_NO then
  1393. setsupreg(index,reginfo[getsupreg(index)].colour);
  1394. end;
  1395. end;
  1396. {$ifdef arm}
  1397. Top_shifterop:
  1398. begin
  1399. so:=shifterop;
  1400. if so^.rs<>NR_NO then
  1401. setsupreg(so^.rs,reginfo[getsupreg(so^.rs)].colour);
  1402. end;
  1403. {$endif arm}
  1404. end;
  1405. { Maybe the operation can be removed when
  1406. it is a move and both arguments are the same }
  1407. if is_same_reg_move(regtype) then
  1408. begin
  1409. q:=Tai(p.next);
  1410. list.remove(p);
  1411. p.free;
  1412. p:=q;
  1413. continue;
  1414. end;
  1415. end;
  1416. end;
  1417. p:=Tai(p.next);
  1418. end;
  1419. aktfilepos:=current_procinfo.exitpos;
  1420. end;
  1421. function trgobj.spill_registers(list:Taasmoutput;headertai:tai):boolean;
  1422. { Returns true if any help registers have been used }
  1423. var
  1424. i : word;
  1425. t : tsuperregister;
  1426. p,q : Tai;
  1427. regs_to_spill_set:Tsuperregisterset;
  1428. spill_temps : ^Tspill_temp_list;
  1429. supreg : tsuperregister;
  1430. templist : taasmoutput;
  1431. begin
  1432. spill_registers:=false;
  1433. live_registers.clear;
  1434. for i:=first_imaginary to maxreg-1 do
  1435. exclude(reginfo[i].flags,ri_selected);
  1436. spill_temps:=allocmem(sizeof(treference)*maxreg);
  1437. supregset_reset(regs_to_spill_set,false,$ffff);
  1438. { Allocate temps and insert in front of the list }
  1439. templist:=taasmoutput.create;
  1440. {Safe: this procedure is only called if there are spilled nodes.}
  1441. with spillednodes do
  1442. for i:=0 to length-1 do
  1443. begin
  1444. t:=buf^[i];
  1445. {Alternative representation.}
  1446. supregset_include(regs_to_spill_set,t);
  1447. {Clear all interferences of the spilled register.}
  1448. clear_interferences(t);
  1449. {Get a temp for the spilled register, the size must at least equal a complete register,
  1450. take also care of the fact that subreg can be larger than a single register like doubles
  1451. that occupy 2 registers }
  1452. tg.gettemp(templist,
  1453. max(tcgsize2size[reg_cgsize(newreg(regtype,t,R_SUBWHOLE))],
  1454. tcgsize2size[reg_cgsize(newreg(regtype,t,reginfo[t].subreg))]),
  1455. tt_noreuse,spill_temps^[t]);
  1456. end;
  1457. list.insertlistafter(headertai,templist);
  1458. templist.free;
  1459. { Walk through all instructions, we can start with the headertai,
  1460. because before the header tai is only symbols }
  1461. p:=headertai;
  1462. while assigned(p) do
  1463. begin
  1464. case p.typ of
  1465. ait_regalloc:
  1466. with Tai_regalloc(p) do
  1467. begin
  1468. if (getregtype(reg)=regtype) then
  1469. begin
  1470. {A register allocation of a spilled register can be removed.}
  1471. supreg:=getsupreg(reg);
  1472. if supregset_in(regs_to_spill_set,supreg) then
  1473. begin
  1474. q:=Tai(p.next);
  1475. list.remove(p);
  1476. p.free;
  1477. p:=q;
  1478. continue;
  1479. end
  1480. else
  1481. begin
  1482. case ratype of
  1483. ra_alloc :
  1484. live_registers.add(supreg);
  1485. ra_dealloc :
  1486. live_registers.delete(supreg);
  1487. end;
  1488. end;
  1489. end;
  1490. end;
  1491. ait_instruction:
  1492. with Taicpu(p) do
  1493. begin
  1494. aktfilepos:=fileinfo;
  1495. if instr_spill_register(list,taicpu(p),regs_to_spill_set,spill_temps^) then
  1496. spill_registers:=true;
  1497. end;
  1498. end;
  1499. p:=Tai(p.next);
  1500. end;
  1501. aktfilepos:=current_procinfo.exitpos;
  1502. {Safe: this procedure is only called if there are spilled nodes.}
  1503. with spillednodes do
  1504. for i:=0 to length-1 do
  1505. tg.ungettemp(list,spill_temps^[buf^[i]]);
  1506. freemem(spill_temps);
  1507. end;
  1508. function trgobj.do_spill_replace(list:Taasmoutput;instr:taicpu;orgreg:tsuperregister;const spilltemp:treference):boolean;
  1509. begin
  1510. result:=false;
  1511. end;
  1512. procedure Trgobj.do_spill_read(list:Taasmoutput;pos:tai;const spilltemp:treference;tempreg:tregister);
  1513. begin
  1514. list.insertafter(spilling_create_load(spilltemp,tempreg),pos);
  1515. end;
  1516. procedure Trgobj.do_spill_written(list:Taasmoutput;pos:tai;const spilltemp:treference;tempreg:tregister);
  1517. begin
  1518. list.insertafter(spilling_create_store(tempreg,spilltemp),pos);
  1519. end;
  1520. function trgobj.get_spill_subreg(r : tregister) : tsubregister;
  1521. begin
  1522. result:=defaultsub;
  1523. end;
  1524. function trgobj.instr_spill_register(list:Taasmoutput;
  1525. instr:taicpu;
  1526. const r:Tsuperregisterset;
  1527. const spilltemplist:Tspill_temp_list): boolean;
  1528. var
  1529. counter, regindex: longint;
  1530. regs: tspillregsinfo;
  1531. spilled: boolean;
  1532. procedure addreginfo(reg: tregister; operation: topertype);
  1533. var
  1534. i, tmpindex: longint;
  1535. supreg : tsuperregister;
  1536. begin
  1537. tmpindex := regindex;
  1538. supreg:=getsupreg(reg);
  1539. { did we already encounter this register? }
  1540. for i := 0 to pred(regindex) do
  1541. if (regs[i].orgreg = supreg) then
  1542. begin
  1543. tmpindex := i;
  1544. break;
  1545. end;
  1546. if tmpindex > high(regs) then
  1547. internalerror(2003120301);
  1548. regs[tmpindex].orgreg := supreg;
  1549. regs[tmpindex].spillreg:=reg;
  1550. if supregset_in(r,supreg) then
  1551. begin
  1552. { add/update info on this register }
  1553. regs[tmpindex].mustbespilled := true;
  1554. case operation of
  1555. operand_read:
  1556. regs[tmpindex].regread := true;
  1557. operand_write:
  1558. regs[tmpindex].regwritten := true;
  1559. operand_readwrite:
  1560. begin
  1561. regs[tmpindex].regread := true;
  1562. regs[tmpindex].regwritten := true;
  1563. end;
  1564. end;
  1565. spilled := true;
  1566. end;
  1567. inc(regindex,ord(regindex=tmpindex));
  1568. end;
  1569. procedure tryreplacereg(var reg: tregister);
  1570. var
  1571. i: longint;
  1572. supreg: tsuperregister;
  1573. begin
  1574. supreg:=getsupreg(reg);
  1575. for i:=0 to pred(regindex) do
  1576. if (regs[i].mustbespilled) and
  1577. (regs[i].orgreg=supreg) then
  1578. begin
  1579. { Only replace supreg }
  1580. setsupreg(reg,getsupreg(regs[i].tempreg));
  1581. break;
  1582. end;
  1583. end;
  1584. var
  1585. loadpos,
  1586. storepos : tai;
  1587. oldlive_registers : tsuperregisterworklist;
  1588. begin
  1589. result := false;
  1590. fillchar(regs,sizeof(regs),0);
  1591. for counter := low(regs) to high(regs) do
  1592. regs[counter].orgreg := RS_INVALID;
  1593. spilled := false;
  1594. regindex := 0;
  1595. { check whether and if so which and how (read/written) this instructions contains
  1596. registers that must be spilled }
  1597. for counter := 0 to instr.ops-1 do
  1598. with instr.oper[counter]^ do
  1599. begin
  1600. case typ of
  1601. top_reg:
  1602. begin
  1603. if (getregtype(reg) = regtype) then
  1604. addreginfo(reg,instr.spilling_get_operation_type(counter));
  1605. end;
  1606. top_ref:
  1607. begin
  1608. if regtype in [R_INTREGISTER,R_ADDRESSREGISTER] then
  1609. with ref^ do
  1610. begin
  1611. if (base <> NR_NO) then
  1612. addreginfo(base,operand_read);
  1613. if (index <> NR_NO) then
  1614. addreginfo(index,operand_read);
  1615. end;
  1616. end;
  1617. {$ifdef ARM}
  1618. top_shifterop:
  1619. begin
  1620. if shifterop^.rs<>NR_NO then
  1621. addreginfo(shifterop^.rs,operand_read);
  1622. end;
  1623. {$endif ARM}
  1624. end;
  1625. end;
  1626. { if no spilling for this instruction we can leave }
  1627. if not spilled then
  1628. exit;
  1629. {$ifdef x86}
  1630. { Try replacing the register with the spilltemp. This is usefull only
  1631. for the i386,x86_64 that support memory locations for several instructions }
  1632. for counter := 0 to pred(regindex) do
  1633. with regs[counter] do
  1634. begin
  1635. if mustbespilled then
  1636. begin
  1637. if do_spill_replace(list,instr,orgreg,spilltemplist[orgreg]) then
  1638. mustbespilled:=false;
  1639. end;
  1640. end;
  1641. {$endif x86}
  1642. {
  1643. There are registers that need are spilled. We generate the
  1644. following code for it. The used positions where code need
  1645. to be inserted are marked using #. Note that code is always inserted
  1646. before the positions using pos.previous. This way the position is always
  1647. the same since pos doesn't change, but pos.previous is modified everytime
  1648. new code is inserted.
  1649. [
  1650. - reg_allocs load spills
  1651. - load spills
  1652. ]
  1653. [#loadpos
  1654. - reg_deallocs
  1655. - reg_allocs
  1656. ]
  1657. [
  1658. - reg_deallocs for load-only spills
  1659. - reg_allocs for store-only spills
  1660. ]
  1661. [#instr
  1662. - original instruction
  1663. ]
  1664. [
  1665. - store spills
  1666. - reg_deallocs store spills
  1667. ]
  1668. [#storepos
  1669. ]
  1670. }
  1671. result := true;
  1672. oldlive_registers.copyfrom(live_registers);
  1673. { Process all tai_regallocs belonging to this instruction. All
  1674. released registers are also added to the live_registers because
  1675. they can't be used during the spilling }
  1676. loadpos:=tai(instr.previous);
  1677. while assigned(loadpos) and
  1678. (loadpos.typ=ait_regalloc) and
  1679. (tai_regalloc(loadpos).instr=instr) do
  1680. begin
  1681. if tai_regalloc(loadpos).ratype=ra_dealloc then
  1682. live_registers.add(getsupreg(tai_regalloc(loadpos).reg));
  1683. loadpos:=tai(loadpos.previous);
  1684. end;
  1685. loadpos:=tai(loadpos.next);
  1686. { Load the spilled registers }
  1687. for counter := 0 to pred(regindex) do
  1688. with regs[counter] do
  1689. begin
  1690. if mustbespilled and regread then
  1691. begin
  1692. tempreg:=getregisterinline(list,get_spill_subreg(regs[counter].spillreg));
  1693. do_spill_read(list,tai(loadpos.previous),spilltemplist[orgreg],tempreg);
  1694. end;
  1695. end;
  1696. { Release temp registers of read-only registers, and add reference of the instruction
  1697. to the reginfo }
  1698. for counter := 0 to pred(regindex) do
  1699. with regs[counter] do
  1700. begin
  1701. if mustbespilled and regread and (not regwritten) then
  1702. begin
  1703. { The original instruction will be the next that uses this register }
  1704. add_reg_instruction(instr,tempreg);
  1705. ungetregisterinline(list,tempreg);
  1706. end;
  1707. end;
  1708. { Allocate temp registers of write-only registers, and add reference of the instruction
  1709. to the reginfo }
  1710. for counter := 0 to pred(regindex) do
  1711. with regs[counter] do
  1712. begin
  1713. if mustbespilled and regwritten then
  1714. begin
  1715. { When the register is also loaded there is already a register assigned }
  1716. if (not regread) then
  1717. tempreg:=getregisterinline(list,get_spill_subreg(regs[counter].spillreg));
  1718. { The original instruction will be the next that uses this register, this
  1719. also needs to be done for read-write registers }
  1720. add_reg_instruction(instr,tempreg);
  1721. end;
  1722. end;
  1723. { store the spilled registers }
  1724. storepos:=tai(instr.next);
  1725. for counter := 0 to pred(regindex) do
  1726. with regs[counter] do
  1727. begin
  1728. if mustbespilled and regwritten then
  1729. begin
  1730. do_spill_written(list,tai(storepos.previous),spilltemplist[orgreg],tempreg);
  1731. ungetregisterinline(list,tempreg);
  1732. end;
  1733. end;
  1734. { now all spilling code is generated we can restore the live registers. This
  1735. must be done after the store because the store can need an extra register
  1736. that also needs to conflict with the registers of the instruction }
  1737. live_registers.done;
  1738. live_registers:=oldlive_registers;
  1739. { substitute registers }
  1740. for counter:=0 to instr.ops-1 do
  1741. with instr.oper[counter]^ do
  1742. begin
  1743. case typ of
  1744. top_reg:
  1745. begin
  1746. if (getregtype(reg) = regtype) then
  1747. tryreplacereg(reg);
  1748. end;
  1749. top_ref:
  1750. begin
  1751. if regtype in [R_INTREGISTER,R_ADDRESSREGISTER] then
  1752. begin
  1753. tryreplacereg(ref^.base);
  1754. tryreplacereg(ref^.index);
  1755. end;
  1756. end;
  1757. {$ifdef ARM}
  1758. top_shifterop:
  1759. begin
  1760. tryreplacereg(shifterop^.rs);
  1761. end;
  1762. {$endif ARM}
  1763. end;
  1764. end;
  1765. end;
  1766. end.
  1767. {
  1768. $Log$
  1769. Revision 1.141 2004-10-11 15:47:03 peter
  1770. * removed warning about register used only once
  1771. Revision 1.140 2004/10/06 20:14:08 peter
  1772. * live_registers must be restored after the spilling store code
  1773. is generate to add correct conflicts for extra temporary registers
  1774. Revision 1.139 2004/10/05 20:41:01 peter
  1775. * more spilling rewrites
  1776. Revision 1.138 2004/10/04 20:46:22 peter
  1777. * spilling code rewritten for x86. It now used the generic
  1778. spilling routines. Special x86 optimization still needs
  1779. to be added.
  1780. * Spilling fixed when both operands needed to be spilled
  1781. * Cleanup of spilling routine, do_spill_readwritten removed
  1782. Revision 1.137 2004/09/26 17:45:30 peter
  1783. * simple regvar support, not yet finished
  1784. Revision 1.136 2004/09/25 14:23:54 peter
  1785. * ungetregister is now only used for cpuregisters, renamed to
  1786. ungetcpuregister
  1787. * renamed (get|unget)explicitregister(s) to ..cpuregister
  1788. * removed location-release/reference_release
  1789. Revision 1.135 2004/09/21 17:25:12 peter
  1790. * paraloc branch merged
  1791. Revision 1.134.4.2 2004/09/21 17:03:26 peter
  1792. * Include aliases of coalesce registers when adding conflicts
  1793. Revision 1.134.4.1 2004/09/12 13:36:40 peter
  1794. * fixed alignment issues
  1795. Revision 1.134 2004/08/24 21:02:32 florian
  1796. * fixed longbool(<int64>) on sparc
  1797. Revision 1.133 2004/07/09 21:38:30 daniel
  1798. * Add check <= 255 when adding to adj_colours
  1799. Revision 1.132 2004/07/08 09:57:55 daniel
  1800. * Use a normal pascal set in assign_colours, since it only will contain
  1801. real registers
  1802. Revision 1.131 2004/07/07 17:35:26 daniel
  1803. * supregset_reset clears 8kb of memory. However, it is being called in
  1804. inner loops, see for example colour_registers. According to profile data
  1805. this causes fillchar to be the most time consuming procedure.
  1806. Some modifications done to make it clear less than 8kb of memory each
  1807. call. Divides time spent in fillchar by two, but it still is the no.1
  1808. procedure.
  1809. Revision 1.130 2004/06/22 18:24:18 florian
  1810. * fixed arm compilation
  1811. Revision 1.129 2004/06/20 08:55:30 florian
  1812. * logs truncated
  1813. Revision 1.128 2004/06/20 08:47:33 florian
  1814. * spilling of doubles on sparc fixed
  1815. Revision 1.127 2004/06/16 20:07:09 florian
  1816. * dwarf branch merged
  1817. Revision 1.126 2004/05/22 23:34:28 peter
  1818. tai_regalloc.allocation changed to ratype to notify rgobj of register size changes
  1819. Revision 1.125 2004/04/26 19:57:50 jonas
  1820. * do not remove "allocation,deallocation" pairs, as those are important
  1821. for the optimizer
  1822. Revision 1.124.2.3 2004/06/13 10:51:16 florian
  1823. * fixed several register allocator problems (sparc/arm)
  1824. }