aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/RegAllocFast.cpp
AgeCommit message (Collapse)Author
2010-06-28Add more special treatment for inline asm in RegAllocFast.Jakob Stoklund Olesen
When an instruction has tied operands and physreg defines, we must take extra care that the tied operands conflict with neither physreg defs nor uses. The special treatment is given to inline asm and instructions with tied operands / early clobbers and physreg defines. This fixes PR7509. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@107043 91177308-0d34-0410-b5e6-96231b3b80d8
2010-06-15Avoid processing early clobbers twice in RegAllocFast.Jakob Stoklund Olesen
Early clobbers defining a virtual register were first alocated to a physreg and then processed as a physreg EC, spilling the virtreg. This fixes PR7382. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@105998 91177308-0d34-0410-b5e6-96231b3b80d8
2010-06-04Keep track of the call instructions whose clobber lists were skipped during fastJakob Stoklund Olesen
register allocation. Process all of the clobber lists at the end of the function, marking the registers as used in MachineRegisterInfo. This is necessary in case the calls clobber callee-saved registers (sic). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@105473 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-19Add support for partial redefs to the fast register allocator.Jakob Stoklund Olesen
A partial redef now triggers a reload if required. Also don't add <imp-def,dead> operands for physical superregisters. Kill flags are still treated as full register kills, and <imp-use,kill> operands are added for physical superregisters as before. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@104167 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-18Properly handle multiple definitions of a virtual register in the sameJakob Stoklund Olesen
instruction. This can happen on ARM: >> %reg1035:5<def>, %reg1035:6<def> = VLD1q16 %reg1028, 0, pred:14, pred:%reg0 Regs: Q0=%reg1032* R0=%reg1028* R1=%reg1029* R2 R3=%reg1031* Killing last use: %reg1028 Allocating %reg1035 from QPR Assigning %reg1035 to Q1 << %D2<def>, %D3<def> = VLD1q16 %R0<kill>, 0, pred:14, pred:%reg0, %Q1<imp-def> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@104056 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Pull the UsedInInstr.test() calls into calcSpillCost() and remember aliases.Jakob Stoklund Olesen
This fixes the miscompilations of MultiSource/Applications/JM/l{en,de}cod. Clang now successfully self hosts in a debug build with the fast register allocator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103975 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Remove debug option. Add comment on spill order determinism.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103961 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Avoid allocating the same physreg to multiple virtregs in one instruction.Jakob Stoklund Olesen
While that approach works wonders for register pressure, it tends to break everything. This should unbreak the arm-linux builder and fix a number of miscompilations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103946 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Minor optimizations. DenseMap::begin() is surprisingly slow on an empty map.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103940 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Extract spill cost calculation to a new method, and use definePhysReg() to clearJakob Stoklund Olesen
out aliases when allocating. Clean up allocVirtReg(). Use calcSpillCost() to allow more aggressive hinting. Now the hint is always taken unless blocked by a reserved register. This leads to more coalescing, lower register pressure, and less spilling. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103939 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Only use clairvoyance when defining a register, and then only if it has one use.Jakob Stoklund Olesen
This makes allocation independent on the ordering of use-def chains. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103935 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Eliminate a hash table probe when killing virtual registers.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103934 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Execute virtreg kills immediately instead of after processing all uses.Jakob Stoklund Olesen
This is safe to do because the physreg has been marked UsedInInstr and the kill flag will be set on the last operand using the virtreg if there are more then one. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103933 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Sprinkle superregister <imp-def> and <imp-kill> operands when dealing with ↵Jakob Stoklund Olesen
subregister indices. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103931 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Now that we don't keep live registers across calls, there is not reason to goJakob Stoklund Olesen
through the very long list of call-clobbered registers. We just assume all registers are clobbered. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103930 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Boldly attempt consistent capitalization. Functional changes unintended.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103929 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Spill and kill all virtual registers across a call.Jakob Stoklund Olesen
Debug code doesn't use callee saved registers anyway, and the code is simpler this way. Now spillVirtReg always kills, and the isKill parameter is not needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103927 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Reduce hashtable probes by using DenseMap::insert() for lookup.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103926 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-17Make MBB a class member instead of passing it around everywhere.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103925 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-15Fix an GCC warning that seems to have actually caught a bug (!!!) inChandler Carruth
a condition's grouping. Every other use of Allocatable.test(Hint) groups it the same way as it is indented, so move the parentheses to agree with that grouping. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103869 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-15Calculate liveness on the fly for local registers.Jakob Stoklund Olesen
When working top-down in a basic block, substituting physregs for virtregs, the use-def chains are kept up to date. That means we can recognize a virtreg kill by the use-def chain becoming empty. This makes the fast allocator independent of incoming kill flags. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103866 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-14Don't bother spilling before a returnJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103831 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-14Track allocatable instead of reserved regs, and never take an unallocatable ↵Jakob Stoklund Olesen
hint. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103828 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-14Avoid scanning the long tail of physreg operands on callsJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103823 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-14Count coalesced copiesJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103821 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-14Allow virtreg redefines when verifying for RegAllocFastJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103820 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-14When verifying two-address instructions, check the following:Jakob Stoklund Olesen
- Kill is implicit when use and def registers are identical. - Only virtual registers can differ. Add a -verify-fast-regalloc to run the verifier before the fast allocator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103797 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-14Simplify the handling of physreg defs and uses in RegAllocFast.Jakob Stoklund Olesen
This adds extra security against using clobbered physregs, and it adds kill markers to physreg uses. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103784 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-14Enable opportunistic coalescingJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103764 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-14Trust kill flags from isel and later passes.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103748 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-14Fix an embarrassing runtime regression for RegAllocFast.Jakob Stoklund Olesen
This loop is quadratic in the capacity for a DenseMap: while(!map.empty()) map.erase(map.begin()); Instead we now do a normal begin() - end() iteration followed by map.clear(). That also has the nice sideeffect of shrinking the map capacity on demand. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103747 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-13Clean up RegAllocFast debug outputJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103739 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-13Take allocation hints from copy instructions to/from physregs.Jakob Stoklund Olesen
This causes way more identity copies to be generated, ripe for coalescing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103686 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-13More asserts around physreg usesJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103685 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-12Make sure to add kill flags to the last use of a virtreg when it is redefined.Jakob Stoklund Olesen
The X86 floating point stack pass and others depend on good kill flags. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103635 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-12Avoid scoping issues, fix buildbotsJakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103530 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-11Make Clang happy.Daniel Dunbar
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103528 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-11Store the Dirty bit in the LiveReg structure instead of a bit vector.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103522 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-11Keep track of the last place a live virtreg was used.Jakob Stoklund Olesen
This allows us to add accurate kill markers, something the scavenger likes. Add some more tests from ARM that needed this. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103521 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-11Simplify the tracking of used physregs to a bulk bitor followed by a transitiveJakob Stoklund Olesen
closure after allocating all blocks. Add a few more test cases for -regalloc=fast. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103500 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-11Mostly rewrite RegAllocFast.Jakob Stoklund Olesen
Sorry for the big change. The path leading up to this patch had some TableGen changes that I didn't want to commit before I knew they were useful. They weren't, and this version does not need them. The fast register allocator now does no liveness calculations. Instead it relies on kill flags provided by isel. (Currently those kill flags are also ignored due to isel bugs). The allocation algorithm is supposed to work with any subset of valid kill flags. More kill flags simply means fewer spills inserted. Registers are allocated from a working set that contains no aliases. That means most allocations can be done directly without expensive alias checks. When the working set runs out of registers we do the full alias check to find new free registers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103488 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-11It's not safe eliminate copies where src and dst have different sub-register ↵Evan Cheng
indices. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103450 91177308-0d34-0410-b5e6-96231b3b80d8
2010-05-06Add argument TargetRegisterInfo to loadRegFromStackSlot and storeRegToStackSlot.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103193 91177308-0d34-0410-b5e6-96231b3b80d8
2010-04-21Run LiveVariables instead of computing liveness locally in -regalloc=fast.Jakob Stoklund Olesen
This actually makes everything slower, but the plan is to have isel add <kill> flags the way it is already adding <dead> flags. Then LiveVariables can be removed again. When ignoring the time spent in LiveVariables, -regalloc=fast is now twice as fast as -regalloc=local. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@102034 91177308-0d34-0410-b5e6-96231b3b80d8
2010-04-21Add fast register allocator, enabled with -regalloc=fast.Jakob Stoklund Olesen
So far this is just a clone of -regalloc=local that has been lobotomized to run 25% faster. It drops the least-recently-used calculations, and is just plain stupid when it runs out of registers. The plan is to make this go even faster for -O0 by taking advantage of the short live intervals in unoptimized code. It should not be necessary to calculate liveness when most virtual registers are killed 2-3 instructions after they are born. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@102006 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-06-22 21:50:19 +0000