summaryrefslogtreecommitdiff
path: root/compiler/nativeGen/RegAllocColor.hs
Commit message (Collapse)AuthorAgeFilesLines
* NCG: Move the graph allocator into its own dirBen.Lippmeier@anu.edu.au2009-02-031-368/+0
|
* Fixes for haddock 0.8Ian Lynagh2008-07-211-1/+1
|
* Fix Haddock errors.Thomas Schilling2008-07-201-3/+3
|
* Make some more modules use LazyUniqFM instead of UniqFMIan Lynagh2008-02-071-1/+1
| | | | | If these modules use UniqFM then we get a stack overflow when compiling modules that use fundeps. I haven't tracked down the actual cause.
* Make some more modules use LazyUniqFM instead of UniqFMIan Lynagh2008-02-071-1/+1
| | | | | If these modules use UniqFM then we get a stack overflow when compiling modules that use fundeps. I haven't tracked down the actual cause.
* lots of portability changes (#1405)Isaac Dupree2008-01-171-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | re-recording to avoid new conflicts was too hard, so I just put it all in one big patch :-( (besides, some of the changes depended on each other.) Here are what the component patches were: Fri Dec 28 11:02:55 EST 2007 Isaac Dupree <id@isaac.cedarswampstudios.org> * document BreakArray better Fri Dec 28 11:39:22 EST 2007 Isaac Dupree <id@isaac.cedarswampstudios.org> * properly ifdef BreakArray for GHCI Fri Jan 4 13:50:41 EST 2008 Isaac Dupree <id@isaac.cedarswampstudios.org> * change ifs on __GLASGOW_HASKELL__ to account for... (#1405) for it not being defined. I assume it being undefined implies a compiler with relatively modern libraries but without most unportable glasgow extensions. Fri Jan 4 14:21:21 EST 2008 Isaac Dupree <id@isaac.cedarswampstudios.org> * MyEither-->EitherString to allow Haskell98 instance Fri Jan 4 16:13:29 EST 2008 Isaac Dupree <id@isaac.cedarswampstudios.org> * re-portabilize Pretty, and corresponding changes Fri Jan 4 17:19:55 EST 2008 Isaac Dupree <id@isaac.cedarswampstudios.org> * Augment FastTypes to be much more complete Fri Jan 4 20:14:19 EST 2008 Isaac Dupree <id@isaac.cedarswampstudios.org> * use FastFunctions, cleanup FastString slightly Fri Jan 4 21:00:22 EST 2008 Isaac Dupree <id@isaac.cedarswampstudios.org> * Massive de-"#", mostly Int# --> FastInt (#1405) Fri Jan 4 21:02:49 EST 2008 Isaac Dupree <id@isaac.cedarswampstudios.org> * miscellaneous unnecessary-extension-removal Sat Jan 5 19:30:13 EST 2008 Isaac Dupree <id@isaac.cedarswampstudios.org> * add FastFunctions
* Move OPTIONS pragmas above commentsIan Lynagh2007-09-211-1/+1
| | | | Fixes building with -Werror (i.e. validate) and GHC < 6.6
* Tune coalescing in non-iterative register allocatorBen.Lippmeier@anu.edu.au2007-09-171-21/+8
| | | | | | | | | | | If iterative coalescing isn't turned on, then do a single aggressive coalescing pass for the first build/color cycle and then back off to conservative coalescing for subseqent passes. Aggressive coalescing is a cheap way to eliminate lots of the reg-reg moves, but it can make the graph less colorable - if we turn it on for every pass then allocation for code with a large amount of register pressure (ie SHA1) doesn't converge in a sensible number of cycles.
* Bugfix to iterative coalescerBen.Lippmeier@anu.edu.au2007-09-171-6/+7
| | | | | | Coalescences must be applied to the unsimplified graph in the same order they were found by the iterative coalescing algorithm - otherwise the vreg rewrite mapping will be wrong and badness will ensue.
* Add -dasm-lintBen.Lippmeier@anu.edu.au2007-09-171-4/+20
| | | | | | | | When -dasm-lint is turned on the register conflict graph is checked for internal consistency after each build/color pass. Make sure that all edges point to valid nodes, that nodes are colored differently to their neighbours, and if the graph is supposed to be colored, that all nodes actually have a color.
* warning policeBen.Lippmeier@anu.edu.au2007-09-131-1/+0
|
* Better calculation of spill costs / selection of spill candidates.Ben.Lippmeier@anu.edu.au2007-09-131-55/+10
| | | | | | | | | | | | | | | | | | | | | | Use Chaitin's formula for calculation of spill costs. Cost to spill some vreg = (num writes + num reads) / degree of node With 2 extra provisos: 1) Don't spill vregs that live for only 1 instruction. 2) Always prefer to spill vregs that live for a number of instructions more than 10 times the number of vregs in that class. Proviso 2 is there to help deal with basic blocks containing very long live ranges - SHA1 has live ranges > 1700 instructions. We don't ever try to keep these long lived ranges in regs at the expense of others. Because stack slots are allocated from a global pool, and there is no slot coalescing yet, without this condition the allocation of SHA1 dosn't converge fast enough and eventually runs out of stack slots. Prior to this patch we were just choosing to spill the range with the longest lifetime, so we didn't bump into this particular problem.
* comment wibblesBen.Lippmeier@anu.edu.au2007-09-121-8/+22
|
* Try and allocate vregs spilled/reloaded from some slot to the same hregBen.Lippmeier@anu.edu.au2007-09-111-5/+7
|
* Better handling of live range joins via spill slots in spill cleanerBen.Lippmeier@anu.edu.au2007-09-111-1/+1
|
* Add iterative coalescing to graph coloring allocatorBen.Lippmeier@anu.edu.au2007-09-071-6/+19
| | | | | | | | | | | | | | | | | Iterative coalescing interleaves conservative coalesing with the regular simplify/scan passes. This increases the chance that nodes will be coalesced as they will have a lower degree than at the beginning of simplify. The end result is that more register to register moves will be eliminated in the output code, though the iterative nature of the algorithm makes it slower compared to non-iterative coloring. Use -fregs-iterative for graph coloring allocation with iterative coalescing -fregs-graph for non-iterative coalescing. The plan is for iterative coalescing to be enabled with -O2 and have a quicker, non-iterative algorithm otherwise. The time/benefit tradeoff between iterative and not is still being tuned - optimal graph coloring is NP-hard, afterall..
* Cure space leak in coloring register allocatorBen.Lippmeier@anu.edu.au2007-09-061-14/+70
| | | | | | | | We now do a deep seq on the graph after it is 'built', but before coloring. Without this, the colorer will just force bits of it and the heap will fill up with half evaluated pieces of graph from previous build/spill stages and zillions of apply thunks.
* Improve GraphColor.colorScanBen.Lippmeier@anu.edu.au2007-09-051-8/+21
| | | | | | | | | | | | | | | | | | Testing whether a node in the conflict graph is trivially colorable (triv) is still a somewhat expensive operation. When we find a triv node during scanning, even though we remove it and its edges from the graph, this is unlikely to to make the nodes we've just scanned become triv - so there's not much point re-scanning them right away. Scanning now takes place in passes. We scan the whole graph for triv nodes and remove all the ones found in a batch before rescanning old nodes. Register allocation for SHA1.lhs now takes (just) 40% of total compile time with -O2 -fregs-graph on x86
* Refactor MachRegs.trivColorable to do unboxed accumulationBen.Lippmeier@anu.edu.au2007-09-051-4/+5
| | | | | | | | | trivColorable was soaking up total 31% time, 41% alloc when compiling SHA1.lhs with -O2 -fregs-graph on x86. Refactoring to use unboxed accumulators and walk directly over the UniqFM holding the set of conflicts reduces this to 17% time, 6% alloc.
* warning policeBen.Lippmeier@anu.edu.au2007-09-051-12/+6
|
* Fix CodingStyle#Warnings URLsIan Lynagh2007-09-041-1/+1
|
* Use OPTIONS rather than OPTIONS_GHC for pragmasIan Lynagh2007-09-031-2/+2
| | | | | | | Older GHCs can't parse OPTIONS_GHC. This also changes the URL referenced for the -w options from WorkingConventions#Warnings to CodingStyle#Warnings for the compiler modules.
* Do aggressive register coalescingBen.Lippmeier@anu.edu.au2007-09-031-3/+13
| | | | Conservative and iterative coalescing come next.
* Add coalescence edges back to the register graphBen.Lippmeier@anu.edu.au2007-08-281-7/+10
|
* Add {-# OPTIONS_GHC -w #-} and some blurb to all compiler modulesIan Lynagh2007-09-011-0/+7
|
* Add a count of how many spill/reloads/reg-reg-moves remain to dump-asm-statsBen.Lippmeier@anu.edu.au2007-08-241-1/+2
|
* Erase unneeded spill/reloads after register allocationBen.Lippmeier@anu.edu.au2007-08-241-3/+8
|
* Be more paranoid about not creating space leaks in coloring allocatorBen.Lippmeier@anu.edu.au2007-08-241-7/+12
|
* Show spill/reload pseudo instrs in regalloc stage dumpBen.Lippmeier@anu.edu.au2007-08-241-4/+7
|
* Add spill/reload pseudo instrs to MachInstrsBen.Lippmeier@anu.edu.au2007-08-231-1/+5
| | | | | | | Spiller can now insert spill/reload instrs without having to worry about the current stack delta. Generation of actual machine instructions for spills/reloads is deferred until after register allocation proper.
* Regalloc stage dump in right orderBen.Lippmeier@anu.edu.au2007-08-231-2/+2
|
* comment wibbleBen.Lippmeier@anu.edu.au2007-08-221-9/+9
|
* Refactor cmmNativeGen so dumps can be emitted inline with NCG stagesBen.Lippmeier@anu.edu.au2007-08-221-10/+18
|
* Add vreg-population-lifetimes to drop-asm-statsBen.Lippmeier@anu.edu.au2007-08-171-2/+4
|
* Refactor dumping of register allocator statistics.Ben.Lippmeier@anu.edu.au2007-08-171-82/+19
|
* Add graph coloring register allocator.Ben.Lippmeier@anu.edu.au2007-08-141-0/+332
Refactored linear allocator into separate liveness annotation and allocation stages. Added graph coloring allocator, use -fregs-graph to enable. New dump flags are -ddump-asm-native -- output of cmm -> native transform. -ddump-asm-liveness -- code annotated with register liveness info -ddump-asm-coalesce -- output of register move coalescing (this is a separate pass when using the coloring allocator) (this could change in the future) -ddump-asm-regalloc -- code after register allocation -ddump-asm-regalloc-stages -- blocks after each build/spill stage of coloring allocator -ddump-asm-conflicts -- a global register liveness graph in graphviz format The new register allocator will allocate some registers, but it's not quite ready for prime-time yet. The spill code generator needs some work...
View Lorry Controller Status