aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/RegAllocBasic.cpp
AgeCommit message (Collapse)Author
2012-02-21Clear virtual registers after they are no longer referenced.Andrew Trick
Passes after RegAlloc should be able to rely on MRI->getNumVirtRegs() == 0. This makes sharing code for pre/postRA passes more robust. Now, to check if a pass is running before the RA pipeline begins, use MRI->isSSA(). To check if a pass is running after the RA pipeline ends, use !MRI->getNumVirtRegs(). PEI resets virtual regs when it's done scavenging. PTX will either have to provide its own PEI pass or assign physregs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151032 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-10RegAlloc superpass: includes phi elimination, coalescing, and scheduling.Andrew Trick
Creates a configurable regalloc pipeline. Ensure specific llc options do what they say and nothing more: -reglloc=... has no effect other than selecting the allocator pass itself. This patch introduces a new umbrella flag, "-optimize-regalloc", to enable/disable the optimizing regalloc "superpass". This allows for example testing coalscing and scheduling under -O0 or vice-versa. When a CodeGen pass requires the MachineFunction to have a particular property, we need to explicitly define that property so it can be directly queried rather than naming a specific Pass. For example, to check for SSA, use MRI->isSSA, not addRequired<PHIElimination>. CodeGen transformation passes are never "required" as an analysis ProcessImplicitDefs does not require LiveVariables. We have a plan to massively simplify some of the early passes within the regalloc superpass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150226 91177308-0d34-0410-b5e6-96231b3b80d8
2012-02-08Add Register mask support to RABasic.Jakob Stoklund Olesen
When a virtual register is live across a call, limit the search space to call-preserved registers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150081 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-17Renamed MachineScheduler to ScheduleTopDownLive.Andrew Trick
Responding to code review. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148290 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-17Moving options declarations around.Andrew Trick
More short term hackery until we have a way to configure passes that work on LiveIntervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148289 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-13Added the MachineSchedulerPass skeleton.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148105 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-11Make data structures private.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147979 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-11Sink spillInterferences into RABasic.Jakob Stoklund Olesen
This helper method is too simplistic for RAGreedy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147976 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-11Move RegAllocBase into its own cpp file separate from RABasic.Jakob Stoklund Olesen
No functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147972 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-05Freeze reserved registers before starting register allocation.Jakob Stoklund Olesen
The register allocators don't currently support adding reserved registers while they are running. Extend the MRI API to keep track of the set of reserved registers when register allocation started. Target hooks like hasFP() and needsStackRealignment() can look at this set to avoid reserving more registers during register allocation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147577 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-11Privatize an unused part of the LiveIntervalUnion::Query interface.Jakob Stoklund Olesen
No clients are iterating over interference overlaps. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137350 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-09Refer to the RegisterCoalescer pass by ID.Jakob Stoklund Olesen
A public interface is no longer needed since RegisterCoalescer is not an analysis any more. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137082 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-26Print out the MBB live-in registers.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136178 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-02Better diagnostics when inline asm fails to allocate.Jakob Stoklund Olesen
asm.c:2:7: error: ran out of registers during register allocation asm(""::"r"(0), "r"(1), "r"(2), "r"(3), "r"(4), "r"(5), "r"(6), "r"(7), "r"(8), "r"(9)); ^ git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134310 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-26There is only one register coalescer. Merge it into the base class andRafael Espindola
remove the analysis group. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133899 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-26Move RegisterCoalescer.h to lib/CodeGen.Rafael Espindola
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133895 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-03Switch AllocationOrder to using RegisterClassInfo instead of a BitVectorJakob Stoklund Olesen
of reserved registers. Use RegisterClassInfo in RABasic as well. This slightly changes som allocation orders because RegisterClassInfo puts CSR aliases last. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132581 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-10Fix PR9883. Make sure all caches are invalidated when a live range is repaired.Jakob Stoklund Olesen
The previous invalidation missed the alias interference caches. Also add a stats counter for the number of repaired ranges. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131133 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-06Emit a proper error message when register allocators run out of registers.Jakob Stoklund Olesen
This can't be just an assertion, users can always write impossible inline assembly. Such an assembly statement should be included in the error message. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131024 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-20Prefer cheap registers for busy live ranges.Jakob Stoklund Olesen
On the x86-64 and thumb2 targets, some registers are more expensive to encode than others in the same register class. Add a CostPerUse field to the TableGen register description, and make it available from TRI->getCostPerUse. This represents the cost of a REX prefix or a 32-bit instruction encoding required by choosing a high register. Teach the greedy register allocator to prefer cheap registers for busy live ranges (as indicated by spill weight). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129864 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-12Fix a bug in RegAllocBase::addMBBLiveIns() where a basic block could ↵Jakob Stoklund Olesen
accidentally be skipped. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129373 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-11Reuse live interval union between functions. This saves a bit of compile timeJakob Stoklund Olesen
when compiling many small functions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129321 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-11Use a faster algorithm for computing MBB live-in registers after register ↵Jakob Stoklund Olesen
allocation. LiveIntervals::findLiveInMBBs has to do a full binary search for each segment. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129292 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-11Time the initial seeding of live registersJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129276 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-05Run LiveDebugVariables in RegAllocBasic and RegAllocGreedy.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128935 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-31The basic register allocator must also use the inline spiller.Jakob Stoklund Olesen
It is using a trivial rewriter that doesn't know how to insert spill code requested by the standard spiller. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128688 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-23Allow the allocation of empty live ranges that have uses.Jakob Stoklund Olesen
Empty ranges may represent undef values. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128144 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-16Tag cached interference with a user-provided tag instead of the virtual ↵Jakob Stoklund Olesen
register number. The live range of a virtual register may change which invalidates the cached interference information. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127772 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-12Spill multiple registers at once.Jakob Stoklund Olesen
Live range splitting can create a number of small live ranges containing only a single real use. Spill these small live ranges along with the large range they are connected to with copies. This enables memory operand folding and maximizes the spill to fill distance. Work in progress with known bugs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127529 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-10Change the Spiller interface to take a LiveRangeEdit reference.Jakob Stoklund Olesen
This makes it possible to register delegates and get callbacks when the spiller edits live ranges. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127389 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-10Make SpillIs an optional pointer. Avoid creating a bunch of temporary ↵Jakob Stoklund Olesen
SmallVectors. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127388 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-22Change the RAGreedy register assignment order so large live ranges are ↵Jakob Stoklund Olesen
allocated first. This is based on the observation that long live ranges are more difficult to allocate, so there is a better chance of solving the puzzle by handling the big pieces first. The allocator will evict and split long alive ranges when they get in the way. RABasic is still using spill weights for its priority queue, so the interface to the queue has been virtualized. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126259 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-18Add VirtRegMap::rewrite() and use it in the new register allocators.Jakob Stoklund Olesen
The rewriter works almost identically to -rewriter=trivial, except it also eliminates any identity copies. This makes the new register allocators independent of VirtRegRewriter.cpp which will be going away at the same time as RegAllocLinearScan. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125967 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-18Trim debugging output.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125802 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-17Add basic register allocator statistics.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125789 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-09Evict a lighter single interference before attempting to split a live range.Jakob Stoklund Olesen
Registers are not allocated strictly in spill weight order when live range splitting and spilling has created new shorter intervals with higher spill weights. When one of the new heavy intervals conflicts with a single lighter interval, simply evict the old interval instead of trying to split the heavy one. The lighter interval is a better candidate for splitting, it has a smaller use density. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125151 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-18Pass a Banner argument to the machine code verifier both fromJakob Stoklund Olesen
createMachineVerifierPass and MachineFunction::verify. The banner is printed before the machine code dump, just like the printer pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122113 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-17Make the -verify-regalloc command line option available to base classes asJakob Stoklund Olesen
RegAllocBase::VerifyEnabled. Run the machine code verifier in a few interesting places during RegAllocGreedy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122107 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-14Simplyfy RegAllocBasic by using getOverlaps instead of getAliasSet.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121801 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-14Use TRI::printReg instead of AbstractRegisterDescription when printingJakob Stoklund Olesen
LiveIntervalUnions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121781 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-11Add named timer groups for the different stages of register allocation.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121604 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-10Move MRI into RegAllocBase. Clean up debug output a bit.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121599 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-09Added register reassignment prototype to RAGreedy. It's a simpleAndrew Trick
heuristic to reshuffle register assignments when we can't find an available reg. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121388 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-08Store (priority,regnum) pairs in the priority queue instead of providing anJakob Stoklund Olesen
abstract priority queue interface in subclasses that want to override the priority calculations. Subclasses must provide a getPriority() implementation instead. This approach requires less code as long as priorities are expressable as simple floats, and it avoids the dangers of defining potentially expensive priority comparison functions. It also should speed up priority_queue operations since they no longer have to chase pointers when comparing registers. This is not measurable, though. Preferably, we shouldn't use floats to guide code generation. The use of floats here is derived from the use of floats for spill weights. Spill weights have a dynamic range that doesn't lend itself easily to a fixpoint implementation. When someone invents a stable spill weight representation, it can be reused for allocation priorities. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121294 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-08Move RABasic::addMBBLiveIns to the base class, it is generally useful.Jakob Stoklund Olesen
Minor optimization to the use of IntervalMap iterators. They are fairly heavyweight, so prefer SI.valid() over SI != end(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121217 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-07Switch LiveIntervalUnion from std::set to IntervalMap.Jakob Stoklund Olesen
This speeds up RegAllocBasic by 20%, not counting releaseMemory which becomes way faster. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121201 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-07Simplify assertion.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121162 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-30Coding style. No significant functionality. Abandon linear scan styleAndrew Trick
in favor of the widespread llvm style. Capitalize variables and add newlines for visual parsing. Rename variables for readability. And other cleanup. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120490 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-25Namespacify.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120146 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-20RABasic fix. Regalloc is responsible for updating block live ins.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119896 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-28 22:22:37 +0000