aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/RegAllocBasic.cpp
AgeCommit message (Collapse)Author
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
2010-11-20Whitespace.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119895 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-11Check TRI->getReservedRegs because other allocators do it. Even thoughAndrew Trick
it makes no sense for allocation_order iterators to visit reserved regs. The inline spiller depends on AliasAnalysis. Manage the Query state to avoid uninitialized or stale results. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118800 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-10RABasic is nearly functionally complete. There are a few remainingAndrew Trick
benchmarks hitting an assertion. Adds LiveIntervalUnion::collectInterferingVRegs. Fixes "late spilling" by checking for any unspillable live vregs among all physReg aliases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118701 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-09Adds RABasic verification and tracing.Andrew Trick
(retry now that the windows build is green) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118630 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-09Reverting r118604. Windows build broke.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118613 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-09Adds RABasic verification and tracing.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118604 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-08Adds support for spilling previously allocated live intervals toAndrew Trick
handle cases in which a register is unavailable for spill code. Adds LiveIntervalUnion::extract. While processing interferences on a live virtual register, reuses the same Query object for each physcial reg. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118423 91177308-0d34-0410-b5e6-96231b3b80d8
2010-11-03Let RegAllocBasic require MachineDominators - they are already available andJakob Stoklund Olesen
splitting needs them. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118194 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-26Jakob's review of the basic register allocator.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117384 91177308-0d34-0410-b5e6-96231b3b80d8
2010-10-22This is a prototype of an experimental register allocationAndrew Trick
framework. It's purpose is not to improve register allocation per se, but to make it easier to develop powerful live range splitting. I call it the basic allocator because it is as simple as a global allocator can be but provides the building blocks for sophisticated register allocation with live range splitting. A minimal implementation is provided that trivially spills whenever it runs out of registers. I'm checking in now to get high-level design and style feedback. I've only done minimal testing. The next step is implementing a "greedy" allocation algorithm that does some register reassignment and makes better splitting decisions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117174 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-28 22:09:40 +0000