summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/LiveRangeEdit.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Create subranges for new intervals resulting from live interval splittingKrzysztof Parzyszek2016-08-241-0/+10
| | | | | | | | | | | | | | | | | | | The register allocator can split a live interval of a register into a set of smaller intervals. After the allocation of registers is complete, the rewriter will modify the IR to replace virtual registers with the corres- ponding physical registers. At this stage, if a register corresponding to a subregister of a virtual register is used, the rewriter will check if that subregister is undefined, and if so, it will add the <undef> flag to the machine operand. The function verifying liveness of the subregis- ter would assume that it is undefined, unless any of the subranges of the live interval proves otherwise. The problem is that the live intervals created during splitting do not have any subranges, even if the original parent interval did. This could result in the <undef> flag placed on a register that is actually defined. Differential Revision: http://reviews.llvm.org/D21189 llvm-svn: 279625
* Allow dead insts to be kept in DeadRemat only when they are rematerializable.Wei Mi2016-07-081-8/+11
| | | | | | | | | | | | | | | Because isReallyTriviallyReMaterializableGeneric puts many limits on rematerializable instructions, this fix can prevent instructions with tied virtual operands and instructions with virtual register uses from being kept in DeadRemat, so as to workaround the live interval consistency problem for the dummy instructions kept in DeadRemat. But we still need to fix the live interval consistency problem. This patch is just a short time relieve. PR28464 has been filed as a reminder. Differential Revision: http://reviews.llvm.org/D19486 llvm-svn: 274928
* CodeGen: Use MachineInstr& in TargetInstrInfo, NFCDuncan P. N. Exon Smith2016-06-301-4/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is mostly a mechanical change to make TargetInstrInfo API take MachineInstr& (instead of MachineInstr* or MachineBasicBlock::iterator) when the argument is expected to be a valid MachineInstr. This is a general API improvement. Although it would be possible to do this one function at a time, that would demand a quadratic amount of churn since many of these functions call each other. Instead I've done everything as a block and just updated what was necessary. This is mostly mechanical fixes: adding and removing `*` and `&` operators. The only non-mechanical change is to split ARMBaseInstrInfo::getOperandLatencyImpl out from ARMBaseInstrInfo::getOperandLatency. Previously, the latter took a `MachineInstr*` which it updated to the instruction bundle leader; now, the latter calls the former either with the same `MachineInstr&` or the bundle leader. As a side effect, this removes a bunch of MachineInstr* to MachineBasicBlock::iterator implicit conversions, a necessary step toward fixing PR26753. Note: I updated WebAssembly, Lanai, and AVR (despite being off-by-default) since it turned out to be easy. I couldn't run tests for AVR since llc doesn't link with it turned on. llvm-svn: 274189
* [LiveRangeEdit] Fix a crash in eliminateDeadDef.Quentin Colombet2016-06-091-1/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | When we delete a live-range, we check if that live-range is the origin of others to keep it around for rematerialization. For that we check that the instruction we are about to remove is the same as the definition of the VNI of the original live-range. If this is the case, we just shrink the live-range to an empty one. Now, when we try to delete one of the children of such live-range (product of splitting), we do the same check. However, now the original live-range is empty and there is no way we can access the VNI to check its definition, and we crash. When we cannot get the VNI for the original live-range, that means we are not in the presence of the original definition. Thus, this check does not need to happen in that case and the crash is sloved! This bug was introduced in r266162 | wmi | 2016-04-12 20:08:27. It affects every target that uses the greedy register allocator. To happen, we need to delete both a the original instruction and its split products, in that order. This is likely to happen when rematerialization comes into play. Trying to produce a more robust test case. Will follow in a coming commit. This fixes llvm.org/PR27983. rdar://problem/26651519 llvm-svn: 272314
* [foldMemoryOperand()] Pass LiveIntervals to enable liveness check.Jonas Paulsson2016-05-101-1/+1
| | | | | | | | | | | | | | | SystemZ (and probably other targets as well) can fold a memory operand by changing the opcode into a new instruction that as a side-effect also clobbers the CC-reg. In order to do this, liveness of that reg must first be checked. When LIS is passed, getRegUnit() can be called on it and the right LiveRange is computed on demand. Reviewed by Matthias Braun. http://reviews.llvm.org/D19861 llvm-svn: 269026
* Don't skip splitSeparateComponents in eliminateDeadDefs for ↵Wei Mi2016-04-151-5/+1
| | | | | | | | | | | | | | | | | | HoistSpillHelper::hoistAllSpills. Because HoistSpillHelper::hoistAllSpills is called in postOptimization, before the patch we didn't want LiveRangeEdit::eliminateDeadDefs to call splitSeparateComponents and generate unassigned new vregs. However, skipping splitSeparateComponents will make verify-machineinstrs unhappy, so I remove the early return, and use HoistSpillHelper::LRE_DidCloneVirtReg to assign physreg/stackslot for those new vregs. In addition, some code reorganization to make class HoistSpillHelper privately inheriting from LiveRangeEdit::Delegate possible. This is to be consistent with class RAGreedy and class RegisterCoalescer. Differential Revision: http://reviews.llvm.org/D19142 llvm-svn: 266489
* Recommit r265547, and r265610,r265639,r265657 on top of it, plusWei Mi2016-04-131-23/+50
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | two fixes with one about error verify-regalloc reported, and another about live range update of phi after rematerialization. r265547: Replace analyzeSiblingValues with new algorithm to fix its compile time issue. The patch is to solve PR17409 and its duplicates. analyzeSiblingValues is a N x N complexity algorithm where N is the number of siblings generated by reg splitting. Although it causes siginificant compile time issue when N is large, it is also important for performance since it removes redundent spills and enables rematerialization. To solve the compile time issue, the patch removes analyzeSiblingValues and replaces it with lower cost alternatives containing two parts. The first part creates a new spill hoisting method in postOptimization of register allocation. It does spill hoisting at once after all the spills are generated instead of inside every instance of selectOrSplit. The second part queries the define expr of the original register for rematerializaiton and keep it always available during register allocation even if it is already dead. It deletes those dead instructions only in postOptimization. With the two parts in the patch, it can remove analyzeSiblingValues without sacrificing performance. Patches on top of r265547: r265610 "Fix the compare-clang diff error introduced by r265547." r265639 "Fix the sanitizer bootstrap error in r265547." r265657 "InlineSpiller.cpp: Escap \@ in r265547. [-Wdocumentation]" Differential Revision: http://reviews.llvm.org/D15302 Differential Revision: http://reviews.llvm.org/D18934 Differential Revision: http://reviews.llvm.org/D18935 Differential Revision: http://reviews.llvm.org/D18936 llvm-svn: 266162
* Revert r265547 "Recommit r265309 after fixed an invalid memory reference bug ↵Hans Wennborg2016-04-081-43/+20
| | | | | | | | | | | | | happened" It caused PR27275: "ARM: Bad machine code: Using an undefined physical register" Also reverting the following commits that were landed on top: r265610 "Fix the compare-clang diff error introduced by r265547." r265639 "Fix the sanitizer bootstrap error in r265547." r265657 "InlineSpiller.cpp: Escap \@ in r265547. [-Wdocumentation]" llvm-svn: 265790
* Recommit r265309 after fixed an invalid memory reference bug happenedWei Mi2016-04-061-20/+43
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | when DenseMap growed and moved memory. I verified it fixed the bootstrap problem on x86_64-linux-gnu but I cannot verify whether it fixes the bootstrap error on clang-ppc64be-linux. I will watch the build-bot result closely. Replace analyzeSiblingValues with new algorithm to fix its compile time issue. The patch is to solve PR17409 and its duplicates. analyzeSiblingValues is a N x N complexity algorithm where N is the number of siblings generated by reg splitting. Although it causes siginificant compile time issue when N is large, it is also important for performance since it removes redundent spills and enables rematerialization. To solve the compile time issue, the patch removes analyzeSiblingValues and replaces it with lower cost alternatives containing two parts. The first part creates a new spill hoisting method in postOptimization of register allocation. It does spill hoisting at once after all the spills are generated instead of inside every instance of selectOrSplit. The second part queries the define expr of the original register for rematerializaiton and keep it always available during register allocation even if it is already dead. It deletes those dead instructions only in postOptimization. With the two parts in the patch, it can remove analyzeSiblingValues without sacrificing performance. Differential Revision: http://reviews.llvm.org/D15302 llvm-svn: 265547
* Revert r265309 and r265312 because they caused some errors I need to ↵Wei Mi2016-04-041-43/+20
| | | | | | investigate. llvm-svn: 265317
* Replace analyzeSiblingValues with new algorithm to fix its compileWei Mi2016-04-041-20/+43
| | | | | | | | | | | | | | | | | | | | | | | | | time issue. The patch is to solve PR17409 and its duplicates. analyzeSiblingValues is a N x N complexity algorithm where N is the number of siblings generated by reg splitting. Although it causes siginificant compile time issue when N is large, it is also important for performance since it removes redundent spills and enables rematerialization. To solve the compile time issue, the patch removes analyzeSiblingValues and replaces it with lower cost alternatives containing two parts. The first part creates a new spill hoisting method in postOptimization of register allocation. It does spill hoisting at once after all the spills are generated instead of inside every instance of selectOrSplit. The second part queries the define expr of the original register for rematerializaiton and keep it always available during register allocation even if it is already dead. It deletes those dead instructions only in postOptimization. With the two parts in the patch, it can remove analyzeSiblingValues without sacrificing performance. Differential Revision: http://reviews.llvm.org/D15302 llvm-svn: 265309
* CodeGen: Take MachineInstr& in SlotIndexes and LiveIntervals, NFCDuncan P. N. Exon Smith2016-02-271-10/+10
| | | | | | | | | | | | | | Take MachineInstr by reference instead of by pointer in SlotIndexes and the SlotIndex wrappers in LiveIntervals. The MachineInstrs here are never null, so this cleans up the API a bit. It also incidentally removes a few implicit conversions from MachineInstrBundleIterator to MachineInstr* (see PR26753). At a couple of call sites it was convenient to convert to a range-based for loop over MachineBasicBlock::instr_begin/instr_end, so I added MachineBasicBlock::instrs. llvm-svn: 262115
* TargetRegisterInfo: Add typedef unsigned LaneBitmask and use it where ↵Matthias Braun2015-09-251-1/+1
| | | | | | apropriate; NFC llvm-svn: 248623
* LiveIntervalAnalysis: Factor common code into splitSeparateComponents; NFCMatthias Braun2015-09-221-20/+13
| | | | llvm-svn: 248241
* Trace copies when checking for rematerializability in spill weight calculationRobert Lougher2015-08-101-1/+1
| | | | | | | | | | | | | | | PR24139 contains an analysis of poor register allocation. One of the findings was that when calculating the spill weight, a rematerializable interval once split is no longer rematerializable. This is because the isRematerializable check in CalcSpillWeights.cpp does not follow the copies introduced by live range splitting (after splitting, the live interval register definition is a copy which is not rematerializable). Reviewers: qcolombet Differential Revision: http://reviews.llvm.org/D11686 llvm-svn: 244439
* LiveRangeEdit: Fix liveranges not shrinking on subrange kill.Matthias Braun2015-06-011-3/+18
| | | | | | | | | | | | | | If a dead instruction we may not only have a last-use in the main live range but also in a subregister range if subregisters are tracked. We need to partially rebuild live ranges in both cases. The testcase only broke when subregister liveness was enabled. I commited it in the current form because there is currently no flag to enable/disable subregister liveness. This fixes PR23720. llvm-svn: 238785
* MachineInstr: Remove unused parameter.Matthias Braun2015-05-191-2/+2
| | | | llvm-svn: 237726
* MachineRegisterInfo can access TII off of the MachineFunction'sEric Christopher2015-01-271-1/+1
| | | | | | | subtarget and so doesn't need the TargetMachine or to access via getSubtargetImpl. Update all callers. llvm-svn: 227160
* LiveIntervalAnalysis: Factor out code to update liveness on vreg def removalMatthias Braun2015-01-211-15/+5
| | | | | | | | | | | This cleans up code and is more in line with the general philosophy of modifying LiveIntervals through LiveIntervalAnalysis instead of changing them directly. This also fixes a case where SplitEditor::removeBackCopies() would miss the subregister ranges. llvm-svn: 226690
* LiveIntervalAnalysis: Factor out code to update liveness on physreg def removalMatthias Braun2015-01-211-9/+2
| | | | | | | | This cleans up code and is more in line with the general philosophy of modifying LiveIntervals through LiveIntervalAnalysis instead of changing them directly. llvm-svn: 226687
* LiveRangeEdit: Check for completely empy subranges after removing ValNos.Matthias Braun2014-12-241-0/+1
| | | | | | | Completely empty subranges are not allowed and must be removed when subreg liveness is enabled. llvm-svn: 224804
* LiveInterval: Use range based for loops for subregister ranges.Matthias Braun2014-12-111-4/+3
| | | | llvm-svn: 223991
* LiveInterval: Use more range based for loops for value numbers and segments.Matthias Braun2014-12-101-3/+1
| | | | llvm-svn: 223978
* LiveRangeEdit: Adapt eliminateDeadDef() to subregister liveness.Matthias Braun2014-12-101-1/+9
| | | | llvm-svn: 223882
* Add missing semicolon from r222118.Craig Topper2014-11-171-1/+1
| | | | llvm-svn: 222119
* Move register class name strings to a single array in MCRegisterInfo to ↵Craig Topper2014-11-171-2/+5
| | | | | | | | reduce static table size and number of relocation entries. Indices into the table are stored in each MCRegisterClass instead of a pointer. A new method, getRegClassName, is added to MCRegisterInfo and TargetRegisterInfo to lookup the string in the table. llvm-svn: 222118
* Add TargetInstrInfo interface isAsCheapAsAMove.Jiangning Liu2014-07-291-1/+1
| | | | llvm-svn: 214158
* [Modules] Remove potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | | | 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. llvm-svn: 206837
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-141-4/+4
| | | | | | instead of comparing to nullptr. llvm-svn: 206142
* Switch a number of loops in lib/CodeGen over to range-based for-loops, now thatOwen Anderson2014-03-171-4/+2
| | | | | | the MachineRegisterInfo iterators are compatible with it. llvm-svn: 204075
* Phase 2 of the great MachineRegisterInfo cleanup. This time, we're changingOwen Anderson2014-03-131-2/+2
| | | | | | | | | | 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. llvm-svn: 203865
* CalcSpillWeights: give a better describing name to calculateSpillWeightsArnaud A. de Grandmaison2013-11-111-1/+1
| | | | | | | | Besides, this relates it more obviously to the VirtRegAuxInfo::calculateSpillWeightAndHint. No functionnal change. llvm-svn: 194404
* Represent RegUnit liveness with LiveRange instanceMatthias Braun2013-10-101-3/+3
| | | | | | | Previously LiveInterval has been used, but having a spill weight and register number is unnecessary for a register unit. llvm-svn: 192397
* Pass LiveQueryResult by valueMatthias Braun2013-10-101-1/+1
| | | | | | | This makes the API a bit more natural to use and makes it easier to make LiveRanges implementation details private. llvm-svn: 192394
* Use LiveRangeQuery for instruction-level liveness queries.Andrew Trick2013-08-301-1/+1
| | | | | | Remove redundant or bug-prone LiveInterval APIs. llvm-svn: 189685
* Replace LiveInterval::killedAt with isKilledAtInstr.Andrew Trick2013-08-301-1/+1
| | | | | | Return true for LRGs that end at EarlyClobber or Register slots. llvm-svn: 189642
* Auto-compute live intervals on demand.Mark Lacey2013-08-141-3/+11
| | | | | | | | | | | | | | | 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. llvm-svn: 188437
* Notify LiveRangeEdit of new virtual registers.Mark Lacey2013-08-141-2/+11
| | | | | | | | | Add a delegate class to MachineRegisterInfo with a single virtual function, MRI_NoteNewVirtualRegister(). Update LiveRangeEdit to inherit from this delegate class and override the definition of the callback with an implementation that tracks the newly created virtual registers. llvm-svn: 188435
* Track new virtual registers by register number.Mark Lacey2013-08-141-3/+3
| | | | | | | | | | 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. llvm-svn: 188434
* Remove unnecessary parameter to RenumberValues.Jakob Stoklund Olesen2013-08-141-1/+1
| | | | | | Patch by Matthias Braun! llvm-svn: 188393
* Prevent LiveRangeEdit from deleting bundled instructions.Andrew Trick2013-06-221-0/+4
| | | | | | | | | We have no targets on trunk that bundle before regalloc. However, we have been advertising regalloc as bundle safe for use with out-of-tree targets. We need to at least contain the parts of the code that are still unsafe. llvm-svn: 184620
* Handle more cases in LiveRangeEdit::eliminateDeadDefs.Andrew Trick2013-06-211-0/+9
| | | | | | | | | | Live intervals for dead physregs may be created during coalescing. We need to update these in the event that their instruction goes away. crash.ll is the unit test that catches it when MI sched is enabled on X86. llvm-svn: 184572
* Refactor LiveRangeEdit::eliminateDeadDefs.Andrew Trick2013-06-211-95/+95
| | | | | | I want to add logic to handle more cases. llvm-svn: 184571
* whitespaceAndrew Trick2013-06-211-2/+2
| | | | llvm-svn: 184570
* Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.Benjamin Kramer2013-06-171-3/+5
| | | | | | | | | | | | | | | | | | 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). llvm-svn: 184105
* Add some constantness.Jakub Staszak2013-03-181-1/+1
| | | | llvm-svn: 177356
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-2/+2
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Make the LiveRegMatrix analysis available to targets.Jakob Stoklund Olesen2012-11-281-1/+1
| | | | | | | | | | | 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. llvm-svn: 168806
* Avoid rematerializing a redef immediately after the old def.Jakob Stoklund Olesen2012-10-161-0/+7
| | | | | | | | | | | | | | | | | PR14098 contains an example where we would rematerialize a MOV8ri immediately after the original instruction: %vreg7:sub_8bit<def> = MOV8ri 9; GR32_ABCD:%vreg7 %vreg22:sub_8bit<def> = MOV8ri 9; GR32_ABCD:%vreg7 Besides being pointless, it is also wrong since the original instruction only redefines part of the register, and the value read by the new instruction is wrong. The problem was the LiveRangeEdit::allUsesAvailableAt() didn't special-case OrigIdx == UseIdx and found the wrong SSA value. llvm-svn: 166068
* Remove LIS::isAllocatable() and isReserved() helpers.Jakob Stoklund Olesen2012-10-151-1/+1
| | | | | | All callers can simply use the corresponding MRI functions. llvm-svn: 165985
OpenPOWER on IntegriCloud