summaryrefslogtreecommitdiff
path: root/lib/CodeGen/SplitKit.cpp
Commit message (Collapse)AuthorAge
* [Modules] Remove potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-22
| | | | | | | | | | | | define below all header includes in the lib/CodeGen/... tree. While the current modules implementation doesn't check for this kind of ODR violation yet, it is likely to grow support for it in the future. It also removes one layer of macro pollution across all the included headers. Other sub-trees will follow. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206837 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-14
| | | | | | instead of comparing to nullptr. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206142 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch a number of loops in lib/CodeGen over to range-based for-loops, now thatOwen Anderson2014-03-17
| | | | | | | the MachineRegisterInfo iterators are compatible with it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@204075 91177308-0d34-0410-b5e6-96231b3b80d8
* Phase 2 of the great MachineRegisterInfo cleanup. This time, we're changingOwen Anderson2014-03-13
| | | | | | | | | | | operator* on the by-operand iterators to return a MachineOperand& rather than a MachineInstr&. At this point they almost behave like normal iterators! Again, this requires making some existing loops more verbose, but should pave the way for the big range-based for-loop cleanups in the future. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@203865 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Replace llvm::tie with std::tie.Benjamin Kramer2014-03-02
| | | | | | The old implementation is no longer needed in C++11. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202644 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-02
| | | | | | Remove the old functions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202636 91177308-0d34-0410-b5e6-96231b3b80d8
* Work on LiveRange instead of LiveInterval where possibleMatthias Braun2013-10-10
| | | | | | | Also change some pointer arguments to references at some places where 0-pointers are not allowed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192396 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename LiveRange to LiveInterval::SegmentMatthias Braun2013-10-10
| | | | | | | | The Segment struct contains a single interval; multiple instances of this struct are used to construct a live range, but the struct is not a live range by itself. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192392 91177308-0d34-0410-b5e6-96231b3b80d8
* Auto-compute live intervals on demand.Mark Lacey2013-08-14
| | | | | | | | | | | | | | | When new virtual registers are created during splitting/spilling, defer creation of the live interval until we need to use the live interval. Along with the recent commits to notify LiveRangeEdit when new virtual registers are created, this makes it possible for functions like TargetInstrInfo::loadRegFromStackSlot() and TargetInstrInfo::storeRegToStackSlot() to create multiple virtual registers as part of the process of generating loads/stores for different register classes, and then have the live intervals for those new registers computed when they are needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188437 91177308-0d34-0410-b5e6-96231b3b80d8
* Track new virtual registers by register number.Mark Lacey2013-08-14
| | | | | | | | | | Track new virtual registers by register number, rather than by the live interval created for them. This is the first step in separating the creation of new virtual registers and new live intervals. Eventually live intervals will be created and populated on demand after the virtual registers have been created and used in instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188434 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unnecessary parameter to RenumberValues.Jakob Stoklund Olesen2013-08-14
| | | | | | Patch by Matthias Braun! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188393 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.Benjamin Kramer2013-06-17
| | | | | | | | | | | | | | | | | | The main advantages here are way better heuristics, taking into account not just loop depth but also __builtin_expect and other static heuristics and will eventually learn how to use profile info. Most of the work in this patch is pushing the MachineBlockFrequencyInfo analysis into the right places. This is good for a 5% speedup on zlib's deflate (x86_64), there were some very unfortunate spilling decisions in its hottest loop in longest_match(). Other benchmarks I tried were mostly neutral. This changes register allocation in subtle ways, update the tests for it. 2012-02-20-MachineCPBug.ll was deleted as it's very fragile and the instruction it looked for was gone already (but the FileCheck pattern picked up unrelated stuff). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@184105 91177308-0d34-0410-b5e6-96231b3b80d8
* Make the LiveRegMatrix analysis available to targets.Jakob Stoklund Olesen2012-11-28
| | | | | | | | | | | No functional change, just moved header files. Targets can inject custom passes between register allocation and rewriting. This makes it possible to tweak the register allocation before rewriting, using the full global interference checking available from LiveRegMatrix. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168806 91177308-0d34-0410-b5e6-96231b3b80d8
* Release build: guard dump functions withManman Ren2012-09-11
| | | | | | | | | "#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163339. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163653 91177308-0d34-0410-b5e6-96231b3b80d8
* Release build: guard dump functions with "ifndef NDEBUG"Manman Ren2012-09-06
| | | | | | | No functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163339 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a couple of loops that were processing unused value numbers.Jakob Stoklund Olesen2012-08-03
| | | | | | | Unused VNInfos should be left alone. Their def SlotIndex doesn't point to anything. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161257 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminate the IS_PHI_DEF flag and VNInfo::setIsPHIDef().Jakob Stoklund Olesen2012-07-27
| | | | | | | | A value number is a PHI def if and only if it begins at a block boundary. This can be derived from the def slot, a separate flag is not necessary. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160893 91177308-0d34-0410-b5e6-96231b3b80d8
* Pass context pointers to LiveRangeCalc::reset().Jakob Stoklund Olesen2012-06-04
| | | | | | | Remove the same pointers from all the other LiveRangeCalc functions, simplifying the interface. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157941 91177308-0d34-0410-b5e6-96231b3b80d8
* Moved LiveRangeEdit.h so that it can be called from other parts of the ↵Pete Cooper2012-04-02
| | | | | | backend, not just libCodeGen git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153906 91177308-0d34-0410-b5e6-96231b3b80d8
* Refactored the LiveRangeEdit interface so that MachineFunction, ↵Pete Cooper2012-04-02
| | | | | | TargetInstrInfo, MachineRegisterInfo, LiveIntervals, and VirtRegMap are all passed into the constructor and stored as members instead of passed in to each method. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153903 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't store COPY pointers in VNInfo.Jakob Stoklund Olesen2012-02-04
| | | | | | | | | | If a value is defined by a COPY, that instuction can easily and cheaply be found by getInstructionFromIndex(VNI->def). This reduces the size of VNInfo from 24 to 16 bytes, and improves llc compile time by 3%. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149763 91177308-0d34-0410-b5e6-96231b3b80d8
* More dead code removal (using -Wunreachable-code)David Blaikie2012-01-20
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148578 91177308-0d34-0410-b5e6-96231b3b80d8
* Detect when a value is undefined on an edge to a landing pad.Jakob Stoklund Olesen2012-01-11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Consider this code: int h() { int x; try { x = f(); g(); } catch (...) { return x+1; } return x; } The variable x is undefined on the first edge to the landing pad, but it has the f() return value on the second edge to the landing pad. SplitAnalysis::getLastSplitPoint() would assume that the return value from f() was live into the landing pad when f() throws, which is of course impossible. Detect these cases, and treat them as if the landing pad wasn't there. This allows spill code to be inserted after the function call to f(). <rdar://problem/10664933> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147912 91177308-0d34-0410-b5e6-96231b3b80d8
* Exclusively use SplitAnalysis::getLastSplitPoint().Jakob Stoklund Olesen2012-01-11
| | | | | | | | | Delete the alternative implementation in LiveIntervalAnalysis. These functions computed the same thing, but SplitAnalysis caches the result. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147911 91177308-0d34-0410-b5e6-96231b3b80d8
* Add bundle aware API for querying instruction properties and switch the codeEvan Cheng2011-12-07
| | | | | | | | | | | | | | | generator to it. For non-bundle instructions, these behave exactly the same as the MC layer API. For properties like mayLoad / mayStore, look into the bundle and if any of the bundled instructions has the property it would return true. For properties like isPredicable, only return true if *all* of the bundled instructions have the property. For properties like canFoldAsLoad, isCompare, conservatively return false for bundles. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146026 91177308-0d34-0410-b5e6-96231b3b80d8
* Use getVNInfoBefore() when it makes sense.Jakob Stoklund Olesen2011-11-14
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144517 91177308-0d34-0410-b5e6-96231b3b80d8
* Terminate all dead defs at the dead slot instead of the 'next' slot.Jakob Stoklund Olesen2011-11-13
| | | | | | | | | | | | | | | | | | | This makes no difference for normal defs, but early clobber dead defs now look like: [Slot_EarlyClobber; Slot_Dead) instead of: [Slot_EarlyClobber; Slot_Register). Live ranges for normal dead defs look like: [Slot_Register; Slot_Dead) as before. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144512 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename SlotIndexes to match how they are used.Jakob Stoklund Olesen2011-11-13
| | | | | | | | | | | | | | | | | | | | The old naming scheme (load/use/def/store) can be traced back to an old linear scan article, but the names don't match how slots are actually used. The load and store slots are not needed after the deferred spill code insertion framework was deleted. The use and def slots don't make any sense because we are using half-open intervals as is customary in C code, but the names suggest closed intervals. In reality, these slots were used to distinguish early-clobber defs from normal defs. The new naming scheme also has 4 slots, but the names match how the slots are really used. This is a purely mechanical renaming, but some of the code makes a lot more sense now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144503 91177308-0d34-0410-b5e6-96231b3b80d8
* Spill mode: Hoist back-copies locally.Jakob Stoklund Olesen2011-09-16
| | | | | | | | | | | | | | | | | The leaveIntvAfter() function normally inserts a back-copy after the requested instruction, making the back-copy kill the live range. In spill mode, try to insert the back-copy before the last use instead. That means the last use becomes the kill instead of the back-copy. This lowers the register pressure because the last use can now redefine the same register it was reading. This will also improve compile time: The back-copy isn't a kill, so hoisting it in hoistCopiesForSize() won't force a recomputation of the source live range. Similarly, if the back-copy isn't hoisted by the splitter, the spiller will not attempt hoisting it locally. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139883 91177308-0d34-0410-b5e6-96231b3b80d8
* Hoist back-copies to the least busy dominator.Jakob Stoklund Olesen2011-09-14
| | | | | | | | | | | | | | | | When a back-copy is hoisted to the nearest common dominator, keep looking up the dominator tree for a less loopy dominator, and place the back-copy there instead. Don't do this when a single existing back-copy dominates all the others. Assume the client knows what he is doing, and keep the dominating back-copy. This prevents us from hoisting back-copies into loops in most cases. If a value is defined in a loop with multiple exits, we may still hoist back-copies into that loop. That is the speed/size tradeoff. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139698 91177308-0d34-0410-b5e6-96231b3b80d8
* Distinguish complex mapped values from forced recomputation.Jakob Stoklund Olesen2011-09-13
| | | | | | | | | | | | | | | | | | When a ParentVNI maps to multiple defs in a new interval, its live range may still be derived directly from RegAssign by transferValues(). On the other hand, when instructions have been rematerialized or hoisted, it may be necessary to completely recompute live ranges using LiveRangeCalc::extend() to all uses. Use a bit in the value map to indicate that a live range must be recomputed. Rename markComplexMapped() to forceRecompute(). This fixes some live range verification errors when -split-spill-mode=size hoists back-copies by recomputing source ranges when RegAssign kills can't be moved. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139660 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement -split-spill-mode=size.Jakob Stoklund Olesen2011-09-13
| | | | | | | | | | Whenever the complement interval is defined by multiple copies of the same value, hoist those back-copies to the nearest common dominator. This ensures that at most one copy is inserted per value in the complement inteval, and no phi-defs are needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139651 91177308-0d34-0410-b5e6-96231b3b80d8
* Add SplitEditor::markOverlappedComplement().Jakob Stoklund Olesen2011-09-13
| | | | | | | | This function is used to flag values where the complement interval may overlap other intervals. Call it from overlapIntv, and use the flag to fully recompute those live ranges in transferValues(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139612 91177308-0d34-0410-b5e6-96231b3b80d8
* Eliminate the extendRange() wrapper.Jakob Stoklund Olesen2011-09-13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139608 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch extendInBlock() to take a kill slot instead of the last use slot.Jakob Stoklund Olesen2011-09-13
| | | | | | | Three out of four clients prefer this interface which is consistent with extendIntervalEndTo() and LiveRangeCalc::extend(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139604 91177308-0d34-0410-b5e6-96231b3b80d8
* Use a separate LiveRangeCalc for the complement in spill modes.Jakob Stoklund Olesen2011-09-13
| | | | | | | | | | The complement interval may overlap the other intervals created, so use a separate LiveRangeCalc instance to compute its live range. A LiveRangeCalc instance can only be shared among non-overlapping intervals. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139603 91177308-0d34-0410-b5e6-96231b3b80d8
* Extract live range calculations from SplitKit.Jakob Stoklund Olesen2011-09-13
| | | | | | | | SplitKit will soon need two copies of these data structures, and the algorithms will also be useful when LiveIntervalAnalysis becomes independent of LiveVariables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139572 91177308-0d34-0410-b5e6-96231b3b80d8
* Add an interface for SplitKit complement spill modes.Jakob Stoklund Olesen2011-09-12
| | | | | | | | | | | | | | | | | | | | | | | | | SplitKit always computes a complement live range to cover the places where the original live range was live, but no explicit region has been allocated. Currently, the complement live range is created to be as small as possible - it never overlaps any of the regions. This minimizes register pressure, but if the complement is going to be spilled anyway, that is not very important. The spiller will eliminate redundant spills, and hoist others by making the spill slot live range overlap some of the regions created by splitting. Stack slots are cheap. This patch adds the interface to enable spill modes in SplitKit. In spill mode, SplitKit will assume that the complement is going to spill, so it will allow it to overlap regions in order to avoid back-copies. By doing some of the spiller's work early, the complement live range becomes simpler. In some cases, it can become much simpler because no extra PHI-defs are required. This will speed up both splitting and spilling. This is only the interface to enable spill modes, no implementation yet. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139500 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete getMultiUseBlocks and splitSingleBlocks.Jakob Stoklund Olesen2011-08-05
| | | | | | | These functions are no longer used, and they are easily replaced with a loop calling shouldSplitSingleBlock and splitSingleBlock. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136993 91177308-0d34-0410-b5e6-96231b3b80d8
* Split around single instructions to enable register class inflation.Jakob Stoklund Olesen2011-08-05
| | | | | | | | | | | | | Normally, we don't create a live range for a single instruction in a basic block, the spiller does that anyway. However, when splitting a live range that belongs to a proper register sub-class, inserting these extra COPY instructions completely remove the constraints from the remainder interval, and it may be allocated from the larger super-class. The spiller will mop up these small live ranges if we end up spilling anyway. It calls them snippets. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136989 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename {First,Last}Use to {First,Last}Instr.Jakob Stoklund Olesen2011-08-02
| | | | | | | With a 'FirstDef' field right there, it is very confusing that FirstUse refers to an instruction that may be a def. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136739 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a BlockInfo::FirstDef field.Jakob Stoklund Olesen2011-08-02
| | | | | | | | | | | This is either an invalid SlotIndex, or valno->def for the first value defined inside the block. PHI values are not counted as defined inside the block. The FirstDef field will be used when estimating the cost of spilling around a block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136736 91177308-0d34-0410-b5e6-96231b3b80d8
* Delete BlockInfo::LiveThrough. It wasn't used any more.Jakob Stoklund Olesen2011-08-02
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136735 91177308-0d34-0410-b5e6-96231b3b80d8
* Never extend live ranges for <undef> uses.Jakob Stoklund Olesen2011-07-24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135886 91177308-0d34-0410-b5e6-96231b3b80d8
* Correctly handle <undef> tied uses when rewriting after a split.Jakob Stoklund Olesen2011-07-24
| | | | | | | | | | | This fixes PR10463. A two-address instruction with an <undef> use operand was incorrectly rewritten so the def and use no longer used the same register, violating the tie constraint. Fix this by always rewriting <undef> operands with the register a def operand would use. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135885 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix bug in SplitEditor::splitLiveThroughBlock when switching registers.Jakob Stoklund Olesen2011-07-23
| | | | | | | | | | | If there is no interference and no last split point, we cannot enterIntvBefore(Stop) - that function needs a real instruction. Use enterIntvAtEnd instead for that very easy case. This code doesn't currently run, it is needed by multi-way splitting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135846 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a crash when building 177.mesa for armv6.Jakob Stoklund Olesen2011-07-18
| | | | | | | | | | | | When splitting a live range immediately before an LDR_POST instruction that redefines the address register, make sure to use the correct value number in leaveIntvBefore. We need the value number entering the instruction. <rdar://problem/9793765> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135413 91177308-0d34-0410-b5e6-96231b3b80d8
* Silence unused variable warningMatt Beaumont-Gay2011-07-16
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135339 91177308-0d34-0410-b5e6-96231b3b80d8
* He said *before* the last split point.Jakob Stoklund Olesen2011-07-16
| | | | | | | This should unbreak the build-self-4-mingw32 tester. I have a very complicated test case that I will try to clean up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135329 91177308-0d34-0410-b5e6-96231b3b80d8
* Extract parts of RAGreedy::splitAroundRegion as SplitKit methods.Jakob Stoklund Olesen2011-07-15
| | | | | | | | | | | This gets rid of some of the gory splitting details in RAGreedy and makes them available to future SplitKit clients. Slightly generalize the functionality to support multi-way splitting. Specifically, SplitEditor::splitLiveThroughBlock() supports switching between different register intervals in a block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135307 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-14 06:34:44 +0000