summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* LiveIntervalAnalysis: Support moving of subregister defs in handleMoveMatthias Braun2016-02-111-34/+152
| | | | | | | | | | | | | | | | If two definitions write to independent subregisters then they can be put in any order. LiveIntervalAnalysis::handleMove() did not support this previously because it looks like moving a definition of a vreg past another one. This is a modified version of a patch proposed (two years ago) by Vincent Lejeune! This version does not touch the read-undef flags and is extended for the case of moving a subregister def behind all uses - this can happen for subregister defs that are completely unused. Differential Revision: http://reviews.llvm.org/D9067 llvm-svn: 260565
* LiveIntervalAnalysis: Improve some commentsMatthias Braun2016-01-261-4/+4
| | | | | | As recommended by Justin. llvm-svn: 258771
* LiveIntervalAnalysis: Cleanup handleMove{Down|Up}() functions, NFCMatthias Braun2016-01-261-131/+141
| | | | | | | | | | | | | | | | | | | | | | These two functions are hard to reason about. This commit makes the code more comprehensible: - Use four distinct variables (OldIdxIn, OldIdxOut, NewIdxIn, NewIdxOut) with a fixed value instead of a changing iterator I that points to different things during the function. - Remove the early explanation before the function in favor of more detailed comments inside the function. Should have more/clearer comments now stating which conditions are tested and which invariants hold at different points in the functions. The behaviour of the code was not changed. I hope that this will make it easier to review the changes in http://reviews.llvm.org/D9067 which I will adapt next. Differential Revision: http://reviews.llvm.org/D16379 llvm-svn: 258756
* LiveInterval: Add utility class to rename independent subregister usageMatthias Braun2016-01-201-0/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This renaming is necessary to avoid a subregister aware scheduler accidentally creating liveness "holes" which are rejected by the MachineVerifier. Explanation as found in this patch: Helper class that can divide MachineOperands of a virtual register into equivalence classes of connected components. MachineOperands belong to the same equivalence class when they are part of the same SubRange segment or adjacent segments (adjacent in control flow); Different subranges affected by the same MachineOperand belong to the same equivalence class. Example: vreg0:sub0 = ... vreg0:sub1 = ... vreg0:sub2 = ... ... xxx = op vreg0:sub1 vreg0:sub1 = ... store vreg0:sub0_sub1 The example contains 3 different equivalence classes: - One for the (dead) vreg0:sub2 definition - One containing the first vreg0:sub1 definition and its use, but not the second definition! - The remaining class contains all other operands involving vreg0. We provide a utility function here to rename disjunct classes to different virtual registers. Differential Revision: http://reviews.llvm.org/D16126 llvm-svn: 258257
* LiveInterval: A LiveRange is enough for ConnectedVNInfoEqClasses::Classify()Matthias Braun2016-01-081-1/+1
| | | | llvm-svn: 257129
* MachineInstr: addRegisterDefReadUndef() => setRegisterDefReadUndef()Matthias Braun2015-11-111-1/+1
| | | | | | This way we can not only add but also remove read undef flags. llvm-svn: 252678
* [WinEH] Mark funclet entries and exits as clobbering all registersReid Kleckner2015-11-061-0/+14
| | | | | | | | | | | | | | | | | Summary: In this implementation, LiveIntervalAnalysis invents a few register masks on basic block boundaries that preserve no registers. The nice thing about this is that it prevents the prologue inserter from thinking it needs to spill all XMM CSRs, because it doesn't see any explicit physreg defs in the MI. Reviewers: MatzeB, qcolombet, JosephTremoulet, majnemer Subscribers: MatzeB, llvm-commits Differential Revision: http://reviews.llvm.org/D14407 llvm-svn: 252318
* Range-for some LiveIntervals code under reviewReid Kleckner2015-11-061-9/+7
| | | | llvm-svn: 252267
* CodeGen: Remove more ilist iterator implicit conversions, NFCDuncan P. N. Exon Smith2015-10-091-2/+2
| | | | llvm-svn: 249879
* TargetRegisterInfo: Introduce PrintLaneMask.Matthias Braun2015-09-251-2/+1
| | | | | | | This makes it more convenient to print lane masks and lead to more uniform printing. llvm-svn: 248624
* TargetRegisterInfo: Add typedef unsigned LaneBitmask and use it where ↵Matthias Braun2015-09-251-10/+10
| | | | | | apropriate; NFC llvm-svn: 248623
* LiveIntervalAnalysis: Avoid multiple connected liveness componentsMatthias Braun2015-09-221-8/+26
| | | | | | | | | | | | | We may have subregister defs which are unused but not discovered and cleaned up prior to liveness analysis. This creates multiple connected components in the resulting live range which are forbidden in the MachineVerifier because they would unnecesarily constrain the register allocator. Rewrite those dead definitions to define a newly created virtual register. Differential Revision: http://reviews.llvm.org/D13035 llvm-svn: 248335
* LiveIntervalAnalysis: Factor common code into splitSeparateComponents; NFCMatthias Braun2015-09-221-0/+17
| | | | llvm-svn: 248241
* Save LaneMask with livein registersMatthias Braun2015-09-091-2/+2
| | | | | | | | | | | | | | | | | With subregister liveness enabled we can detect the case where only parts of a register are live in, this is expressed as a 32bit lanemask. The current code only keeps registers in the live-in list and therefore enumerated all subregisters affected by the lanemask. This turned out to be too conservative as the subregister may also cover additional parts of the lanemask which are not live. Expressing a given lanemask by enumerating a minimum set of subregisters is computationally expensive so the best solution is to simply change the live-in list to store the lanemasks as well. This will reduce memory usage for targets using subregister liveness and slightly increase it for other targets Differential Revision: http://reviews.llvm.org/D12442 llvm-svn: 247171
* [PM/AA] Rebuild LLVM's alias analysis infrastructure in a way compatibleChandler Carruth2015-09-091-4/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | with the new pass manager, and no longer relying on analysis groups. This builds essentially a ground-up new AA infrastructure stack for LLVM. The core ideas are the same that are used throughout the new pass manager: type erased polymorphism and direct composition. The design is as follows: - FunctionAAResults is a type-erasing alias analysis results aggregation interface to walk a single query across a range of results from different alias analyses. Currently this is function-specific as we always assume that aliasing queries are *within* a function. - AAResultBase is a CRTP utility providing stub implementations of various parts of the alias analysis result concept, notably in several cases in terms of other more general parts of the interface. This can be used to implement only a narrow part of the interface rather than the entire interface. This isn't really ideal, this logic should be hoisted into FunctionAAResults as currently it will cause a significant amount of redundant work, but it faithfully models the behavior of the prior infrastructure. - All the alias analysis passes are ported to be wrapper passes for the legacy PM and new-style analysis passes for the new PM with a shared result object. In some cases (most notably CFL), this is an extremely naive approach that we should revisit when we can specialize for the new pass manager. - BasicAA has been restructured to reflect that it is much more fundamentally a function analysis because it uses dominator trees and loop info that need to be constructed for each function. All of the references to getting alias analysis results have been updated to use the new aggregation interface. All the preservation and other pass management code has been updated accordingly. The way the FunctionAAResultsWrapperPass works is to detect the available alias analyses when run, and add them to the results object. This means that we should be able to continue to respect when various passes are added to the pipeline, for example adding CFL or adding TBAA passes should just cause their results to be available and to get folded into this. The exception to this rule is BasicAA which really needs to be a function pass due to using dominator trees and loop info. As a consequence, the FunctionAAResultsWrapperPass directly depends on BasicAA and always includes it in the aggregation. This has significant implications for preserving analyses. Generally, most passes shouldn't bother preserving FunctionAAResultsWrapperPass because rebuilding the results just updates the set of known AA passes. The exception to this rule are LoopPass instances which need to preserve all the function analyses that the loop pass manager will end up needing. This means preserving both BasicAAWrapperPass and the aggregating FunctionAAResultsWrapperPass. Now, when preserving an alias analysis, you do so by directly preserving that analysis. This is only necessary for non-immutable-pass-provided alias analyses though, and there are only three of interest: BasicAA, GlobalsAA (formerly GlobalsModRef), and SCEVAA. Usually BasicAA is preserved when needed because it (like DominatorTree and LoopInfo) is marked as a CFG-only pass. I've expanded GlobalsAA into the preserved set everywhere we previously were preserving all of AliasAnalysis, and I've added SCEVAA in the intersection of that with where we preserve SCEV itself. One significant challenge to all of this is that the CGSCC passes were actually using the alias analysis implementations by taking advantage of a pretty amazing set of loop holes in the old pass manager's analysis management code which allowed analysis groups to slide through in many cases. Moving away from analysis groups makes this problem much more obvious. To fix it, I've leveraged the flexibility the design of the new PM components provides to just directly construct the relevant alias analyses for the relevant functions in the IPO passes that need them. This is a bit hacky, but should go away with the new pass manager, and is already in many ways cleaner than the prior state. Another significant challenge is that various facilities of the old alias analysis infrastructure just don't fit any more. The most significant of these is the alias analysis 'counter' pass. That pass relied on the ability to snoop on AA queries at different points in the analysis group chain. Instead, I'm planning to build printing functionality directly into the aggregation layer. I've not included that in this patch merely to keep it smaller. Note that all of this needs a nearly complete rewrite of the AA documentation. I'm planning to do that, but I'd like to make sure the new design settles, and to flesh out a bit more of what it looks like in the new pass manager first. Differential Revision: http://reviews.llvm.org/D12080 llvm-svn: 247167
* [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
OpenPOWER on IntegriCloud