summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [WinEH] Add some support for code generating catchpadReid Kleckner2015-08-271-1/+1
| | | | | | | We can now run 32-bit programs with empty catch bodies. The next step is to change PEI so that we get funclet prologues and epilogues. llvm-svn: 246235
* MachineBasicBlock: Add liveins() method returning an iterator_rangeMatthias Braun2015-08-241-3/+2
| | | | llvm-svn: 245895
* LiveInterval: Document and enforce rules about empty subranges.Matthias Braun2015-07-161-0/+5
| | | | | | | | | Empty subranges are not allowed in a LiveInterval and must be removed instead: Check this in the verifiers, put a reminder for this in the comment of the shrinkToUses variant for a single lane and make it automatic for the shrinkToUses variant for a LiveInterval. llvm-svn: 242431
* Do not duplicate method name in comment, remove duplicate commentMatthias Braun2015-07-161-3/+0
| | | | llvm-svn: 242430
* CodeGen: Use mop_iterator instead of MIOperands/ConstMIOperandsMatthias Braun2015-05-291-10/+10
| | | | | | | | | | | | | | | | | | | | | | | | MIOperands/ConstMIOperands are classes iterating over the MachineOperand of a MachineInstr, however MachineInstr::mop_iterator does the same thing. I assume these two iterators exist to have a uniform interface to iterate over the operands of a machine instruction bundle and a single machine instruction. However in practice I find it more confusing to have 2 different iterator classes, so this patch transforms (nearly all) the code to use mop_iterators. The only exception being MIOperands::anlayzePhysReg() and MIOperands::analyzeVirtReg() still needing an equivalent, I leave that as an exercise for the next patch. Differential Revision: http://reviews.llvm.org/D9932 This version is slightly modified from the proposed revision in that it introduces MachineInstr::getOperandNo to avoid the extra counting variable in the few loops that previously used MIOperands::getOperandNo. llvm-svn: 238539
* Do not track subregister liveness when it brings no benefitsMatthias Braun2015-03-191-4/+4
| | | | | | | | | | | Some subregisters are only to indicate different access sizes, while not providing any way to actually divide the register up into multiple disjunct parts. Avoid tracking subregister liveness in these cases as it is not beneficial. Differential Revision: http://reviews.llvm.org/D8429 llvm-svn: 232695
* [LiveIntervalAnalysis] Speed up creation of live ranges for physical registersQuentin Colombet2015-02-061-1/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | by using a segment set. The patch addresses a compile-time performance regression in the LiveIntervals analysis pass (see http://llvm.org/bugs/show_bug.cgi?id=18580). This regression is especially critical when compiling long functions. Our analysis had shown that the most of time is taken for generation of live intervals for physical registers. Insertions in the middle of the array of live ranges cause quadratic algorithmic complexity, which is apparently the main reason for the slow-down. Overview of changes: - The patch introduces an additional std::set<Segment>* member in LiveRange for storing segments in the phase of initial creation. The set is used if this member is not NULL, otherwise everything works the old way. - The set of operations on LiveRange used during initial creation (i.e. used by createDeadDefs and extendToUses) have been reimplemented to use the segment set if it is available. - After a live range is created the contents of the set are flushed to the segment vector, because the set is not as efficient as the vector for the later uses of the live range. After the flushing, the set is deleted and cannot be used again. - The set is only for live ranges computed in LiveIntervalAnalysis::computeLiveInRegUnits() and getRegUnit() but not in computeVirtRegs(), because I did not bring any performance benefits to computeVirtRegs() and for some examples even brought a slow down. Patch by Vaidas Gasiunas <vaidas.gasiunas@sap.com> Differential Revision: http://reviews.llvm.org/D6013 llvm-svn: 228421
* LiveIntervalAnalysis: Mark subregister defs as undef when we determined they ↵Matthias Braun2015-01-211-5/+16
| | | | | | | | | are only reading a dead superregister value This was not necessary before as this case can only be detected when the liveness analysis is at subregister level. llvm-svn: 226733
* LiveIntervalAnalysis: Factor out code to update liveness on vreg def removalMatthias Braun2015-01-211-0/+14
| | | | | | | | | | | 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-0/+8
| | | | | | | | 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
* LiveIntervalAnalysis: Remove unused pruneValue() variant.Matthias Braun2015-01-211-9/+0
| | | | llvm-svn: 226686
* LiveIntervalAnalysis: Fix performance bug that I introduced in r224663.Matthias Braun2014-12-241-2/+2
| | | | | | | | Without a reference the code did not remember when moving the iterators of the subranges/registerunit ranges forward and instead would scan from the beginning again at the next position. llvm-svn: 224803
* LiveIntervalAnalysis: No kill flags for partially undefined uses.Matthias Braun2014-12-201-24/+68
| | | | | | | | | We must not add kill flags when reading a vreg with some undefined subregisters, if subreg liveness tracking is enabled. This is because the register allocator may reuse these undefined subregisters for other values which are not killed. llvm-svn: 224664
* LiveIntervalAnalysis: cleanup addKills(), NFCMatthias Braun2014-12-201-19/+18
| | | | | | | | - Use more const modifiers - Use references for things that can't be nullptr - Improve some variable names llvm-svn: 224663
* LiveIntervalAnalysis: Cleanup computeDeadValuesMatthias Braun2014-12-181-24/+33
| | | | | | | | | - This also fixes a bug introduced in r223880 where values were not correctly marked as Dead anymore. - Cleanup computeDeadValues(): split up SubRange code variant, simplify arguments. llvm-svn: 224538
* LiveRangeCalc: Rewrite subrange calculationMatthias Braun2014-12-161-2/+1
| | | | | | | | | This changes subrange calculation to calculate subranges sequentially instead of in parallel. The code is easier to understand that way and addresses the code review issues raised about LiveOutData being hard to understand/needing more comments by removing them :) llvm-svn: 224313
* Revert "LiveRangeCalc: Rewrite subrange calculation"Matthias Braun2014-12-151-6/+14
| | | | | | | | Revert until I find out why non-subreg enabled targets break. This reverts commit 6097277eefb9c5fb35a7f493c783ee1fd1b9d6a7. llvm-svn: 224278
* LiveRangeCalc: Rewrite subrange calculationMatthias Braun2014-12-151-14/+6
| | | | | | | | | This changes subrange calculation to calculate subranges sequentially instead of in parallel. The code is easier to understand that way and addresses the code review issues raised about LiveOutData being hard to understand/needing more comments by removing them :) llvm-svn: 224272
* LiveInterval: Use range based for loops for subregister ranges.Matthias Braun2014-12-111-13/+9
| | | | llvm-svn: 223991
* LiveInterval: Use more range based for loops for value numbers and segments.Matthias Braun2014-12-101-4/+2
| | | | llvm-svn: 223978
* VirtRegMap: No implicit defs/uses for super registers with subreg liveness ↵Matthias Braun2014-12-101-0/+24
| | | | | | | | | | | | | tracking. Adding the implicit defs/uses to the superregisters is semantically questionable but was not dangerous before as the register allocator never assigned the same register to two overlapping LiveIntervals even when the actually live subregisters do not overlap. With subregister liveness tracking enabled this does actually happen and leads to subsequent bugs if we don't stop adding the superregister defs/uses. llvm-svn: 223892
* LiveIntervalAnalysis: Add subregister aware variants pruneValue().Matthias Braun2014-12-101-10/+20
| | | | llvm-svn: 223886
* Add a flag to enable/disable subregister liveness.Matthias Braun2014-12-101-0/+8
| | | | llvm-svn: 223884
* LiveIntervalAnalysis: Adapt repairIntervalsInRange() to subregister liveness.Matthias Braun2014-12-101-77/+92
| | | | llvm-svn: 223883
* LiveIntervalAnalysis: Adapt handleMove() to subregister ranges.Matthias Braun2014-12-101-16/+30
| | | | llvm-svn: 223881
* LiveIntervalAnalysis: Update SubRanges in shrinkToUses().Matthias Braun2014-12-101-75/+146
| | | | llvm-svn: 223880
* LiveInterval: Add support to track liveness of subregisters.Matthias Braun2014-12-101-0/+2
| | | | | | This code adds the required data structures. Algorithms to compute it follow. llvm-svn: 223877
* Update SetVector to rely on the underlying set's insert to return a ↵David Blaikie2014-11-191-4/+5
| | | | | | | | | | | | | pair<iterator, bool> This is to be consistent with StringSet and ultimately with the standard library's associative container insert function. This lead to updating SmallSet::insert to return pair<iterator, bool>, and then to update SmallPtrSet::insert to return pair<iterator, bool>, and then to update all the existing users of those functions... llvm-svn: 222334
* Access the subtarget off of the MachineFunction rather thanEric Christopher2014-10-141-4/+2
| | | | | | through the TargetMachine. llvm-svn: 219661
* Remove the TargetMachine forwards for TargetSubtargetInfo basedEric Christopher2014-08-041-2/+3
| | | | | | information and update all callers. No functional change. llvm-svn: 214781
* Calculate dead instructions when a live interval is created.Pete Cooper2014-06-031-9/+18
| | | | | | | | This gets us closer to being able to remove LiveVariables entirely which is where dead instructions are currently tagged as such. Reviewed by Jakob Olesen llvm-svn: 210132
* [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-6/+6
| | | | | | instead of comparing to nullptr. llvm-svn: 206142
* Phase 1 of refactoring the MachineRegisterInfo iterators to make them suitableOwen Anderson2014-03-131-6/+8
| | | | | | | | | | | | | | | | | | | for use with C++11 range-based for-loops. The gist of phase 1 is to remove the skipInstruction() and skipBundle() methods from these iterators, instead splitting each iterator into a version that walks operands, a version that walks instructions, and a version that walks bundles. This has the result of making some "clever" loops in lib/CodeGen more verbose, but also makes their iterator invalidation characteristics much more obvious to the casual reader. (Making them concise again in the future is a good motivating case for a pre-incrementing range adapter!) Phase 2 of this undertaking with consist of removing the getOperand() method, and changing operator*() of the operand-walker to return a MachineOperand&. At that point, it should be possible to add range views for them that work as one might expect. llvm-svn: 203757
* [C++11] Replace llvm::tie with std::tie.Benjamin Kramer2014-03-021-2/+2
| | | | | | The old implementation is no longer needed in C++11. llvm-svn: 202644
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-10/+10
| | | | | | Remove the old functions. llvm-svn: 202636
* [block-freq] Rename getEntryFrequency() -> getEntryFreq() to match ↵Michael Gottesman2013-12-141-1/+1
| | | | | | getBlockFreq() in all *BlockFrequencyInfo*. llvm-svn: 197304
* [block-freq] Refactor LiveInterals::getSpillWeight to use the new ↵Michael Gottesman2013-12-141-3/+7
| | | | | | | | | | | | | | | | | | | | | | | MachineBlockFrequencyInfo methods. This is slightly more interesting than the previous batch of changes. Specifically: 1. We refactor getSpillWeight to take a MachineBlockFrequencyInfo (MBFI) object. This enables us to completely encapsulate the actual manner we use the MachineBlockFrequencyInfo to get our spill weights. This yields cleaner code since one does not need to fetch the actual block frequency before getting the spill weight if all one wants it the spill weight. It also gives us access to entry frequency which we need for our computation. 2. Instead of having getSpillWeight take a MachineBasicBlock (as one might think) to look up the block frequency via the MBFI object, we instead take in a MachineInstr object. The reason for this is that the method is supposed to return the spill weight for an instruction according to the comments around the function. llvm-svn: 197296
* Replacing HUGE_VALF with llvm::huge_valf in order to work around a warning ↵Aaron Ballman2013-11-131-1/+2
| | | | | | | | triggered in MSVC 12. Patch reviewed by Reid Kleckner and Jim Grosbach. llvm-svn: 194533
* Print register in LiveInterval::print()Matthias Braun2013-10-101-2/+2
| | | | llvm-svn: 192398
* Represent RegUnit liveness with LiveRange instanceMatthias Braun2013-10-101-69/+70
| | | | | | | Previously LiveInterval has been used, but having a spill weight and register number is unnecessary for a register unit. llvm-svn: 192397
* Work on LiveRange instead of LiveInterval where possibleMatthias Braun2013-10-101-7/+7
| | | | | | | Also change some pointer arguments to references at some places where 0-pointers are not allowed. llvm-svn: 192396
* Pass LiveQueryResult by valueMatthias Braun2013-10-101-3/+3
| | | | | | | This makes the API a bit more natural to use and makes it easier to make LiveRanges implementation details private. llvm-svn: 192394
* Refactor LiveInterval: introduce new LiveRange classMatthias Braun2013-10-101-18/+17
| | | | | | | | | | LiveRange just manages a list of segments and a list of value numbers now as LiveInterval did previously, but without having details like spill weight or a fixed register number. LiveInterval is now a subclass of LiveRange and simply adds the spill weight and the register number. llvm-svn: 192393
* Rename LiveRange to LiveInterval::SegmentMatthias Braun2013-10-101-28/+32
| | | | | | | | 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. llvm-svn: 192392
* Fix typoMatthias Braun2013-10-041-1/+1
| | | | llvm-svn: 191964
* Auto-compute live intervals on demand.Mark Lacey2013-08-141-6/+3
| | | | | | | | | | | | | | | 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
* Improve misleading comment.Jakob Stoklund Olesen2013-08-141-1/+1
| | | | | | Patch by Matthias Braun! llvm-svn: 188391
* Added -precompute-phys-liveness for testing LiveIntervals updates.Andrew Trick2013-06-211-0/+14
| | | | llvm-svn: 184573
* Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.Benjamin Kramer2013-06-171-15/+4
| | | | | | | | | | | | | | | | | | 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
OpenPOWER on IntegriCloud