From 4751eb760e7f4e51cfd594cbe46c7d0d7865d693 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 2 Aug 2011 22:37:20 +0000 Subject: Delete BlockInfo::LiveThrough. It wasn't used any more. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136735 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/SplitKit.h | 1 - 1 file changed, 1 deletion(-) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 7948b72..4566b84 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -78,7 +78,6 @@ public: MachineBasicBlock *MBB; SlotIndex FirstUse; ///< First instr using current reg. SlotIndex LastUse; ///< Last instr using current reg. - bool LiveThrough; ///< Live in whole block (Templ 5. above). bool LiveIn; ///< Current reg is live in. bool LiveOut; ///< Current reg is live out. -- cgit v1.1 From 77ee1140a3297e6fbd6cb7cf586872af6d00d07e Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 2 Aug 2011 22:37:22 +0000 Subject: Add a BlockInfo::FirstDef field. 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 --- lib/CodeGen/SplitKit.h | 1 + 1 file changed, 1 insertion(+) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 4566b84..92d6bc8 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -78,6 +78,7 @@ public: MachineBasicBlock *MBB; SlotIndex FirstUse; ///< First instr using current reg. SlotIndex LastUse; ///< Last instr using current reg. + SlotIndex FirstDef; ///< First non-phi valno->def, or SlotIndex(). bool LiveIn; ///< Current reg is live in. bool LiveOut; ///< Current reg is live out. -- cgit v1.1 From fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 2 Aug 2011 22:54:14 +0000 Subject: Rename {First,Last}Use to {First,Last}Instr. 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 --- lib/CodeGen/SplitKit.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 92d6bc8..33c3c07 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -76,8 +76,8 @@ public: /// struct BlockInfo { MachineBasicBlock *MBB; - SlotIndex FirstUse; ///< First instr using current reg. - SlotIndex LastUse; ///< Last instr using current reg. + SlotIndex FirstInstr; ///< First instr accessing current reg. + SlotIndex LastInstr; ///< Last instr accessing current reg. SlotIndex FirstDef; ///< First non-phi valno->def, or SlotIndex(). bool LiveIn; ///< Current reg is live in. bool LiveOut; ///< Current reg is live out. @@ -85,7 +85,7 @@ public: /// isOneInstr - Returns true when this BlockInfo describes a single /// instruction. bool isOneInstr() const { - return SlotIndex::isSameInstr(FirstUse, LastUse); + return SlotIndex::isSameInstr(FirstInstr, LastInstr); } }; -- cgit v1.1 From 2d6d86be84ee355223ccd20b7f87a0c9971c50c9 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Fri, 5 Aug 2011 22:20:45 +0000 Subject: Split around single instructions to enable register class inflation. 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 --- lib/CodeGen/SplitKit.h | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 33c3c07..8bed2a0 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -185,6 +185,16 @@ public: typedef SmallPtrSet BlockPtrSet; + /// shouldSplitSingleBlock - Returns true if it would help to create a local + /// live range for the instructions in BI. There is normally no benefit to + /// creating a live range for a single instruction, but it does enable + /// register class inflation if the instruction has a restricted register + /// class. + /// + /// @param BI The block to be isolated. + /// @param SingleInstrs True when single instructions should be isolated. + bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const; + /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from /// having CurLI split to a new live interval. Return true if Blocks can be /// passed to SplitEditor::splitSingleBlocks. -- cgit v1.1 From 75e28f74b051e72ca3fc1aa38e5e43a5204a65ce Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Fri, 5 Aug 2011 22:52:17 +0000 Subject: Delete getMultiUseBlocks and splitSingleBlocks. 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 --- lib/CodeGen/SplitKit.h | 9 --------- 1 file changed, 9 deletions(-) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 8bed2a0..89ce24b 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -194,11 +194,6 @@ public: /// @param BI The block to be isolated. /// @param SingleInstrs True when single instructions should be isolated. bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const; - - /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from - /// having CurLI split to a new live interval. Return true if Blocks can be - /// passed to SplitEditor::splitSingleBlocks. - bool getMultiUseBlocks(BlockPtrSet &Blocks); }; @@ -433,10 +428,6 @@ public: /// split, and doesn't call finish(). void splitSingleBlock(const SplitAnalysis::BlockInfo &BI); - /// splitSingleBlocks - Split CurLI into a separate live interval inside each - /// basic block in Blocks. - void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); - /// splitLiveThroughBlock - Split CurLI in the given block such that it /// enters the block in IntvIn and leaves it in IntvOut. There may be uses in /// the block, but they will be ignored when placing split points. -- cgit v1.1 From 3d4ec14ffc6b957b9418578567a5751ef6f80fdb Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Mon, 12 Sep 2011 16:03:26 +0000 Subject: Update comments to reflect some (not so) recent changes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139498 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/SplitKit.h | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 89ce24b..becd22c 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -255,7 +255,7 @@ class SplitEditor { // live-out value and its defining block. // One of these conditions shall be true: // - // 1. !LiveOutCache.count(MBB) + // 1. !LiveOutSeen.count(MBB->getNumber()) // 2. LiveOutCache[MBB].second.getNode() == MBB // 3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB] // @@ -264,12 +264,13 @@ class SplitEditor { // VNI = Edit.get(RegIdx)->getVNInfoAt(LIS.getMBBEndIdx(MBB)) // Node = mbt_[LIS.getMBBFromIndex(VNI->def)] // - // The cache is also used as a visited set by extendRange(). It can be shared - // by all the new registers because at most one is live out of each block. + // The cache can be shared by all the new registers because at most one is + // live out of each block. LiveOutMap LiveOutCache; // LiveOutSeen - Indexed by MBB->getNumber(), a bit is set for each valid - // entry in LiveOutCache. + // entry in LiveOutCache. This is also used as a visited set for + // findReachingDefs(). BitVector LiveOutSeen; /// LiveInBlock - Info for updateSSA() about a block where a register is -- cgit v1.1 From 708d06f7fb5dfd9c8559aea07b042a88c65645f8 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Mon, 12 Sep 2011 16:49:21 +0000 Subject: Add an interface for SplitKit complement spill modes. 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 --- lib/CodeGen/SplitKit.h | 35 ++++++++++++++++++++++++++++++++++- 1 file changed, 34 insertions(+), 1 deletion(-) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index becd22c..7f74d3a 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -217,6 +217,36 @@ class SplitEditor { const TargetInstrInfo &TII; const TargetRegisterInfo &TRI; +public: + + /// ComplementSpillMode - Select how the complement live range should be + /// created. SplitEditor automatically creates interval 0 to contain + /// anything that isn't added to another interval. This complement interval + /// can get quite complicated, and it can sometimes be an advantage to allow + /// it to overlap the other intervals. If it is going to spill anyway, no + /// registers are wasted by keeping a value in two places at the same time. + enum ComplementSpillMode { + /// SM_Partition(Default) - Try to create the complement interval so it + /// doesn't overlap any other intervals, and the original interval is + /// partitioned. This may require a large number of back copies and extra + /// PHI-defs. Only segments marked with overlapIntv will be overlapping. + SM_Partition, + + /// SM_Size - Overlap intervals to minimize the number of inserted COPY + /// instructions. Copies to the complement interval are hoisted to their + /// common dominator, so only one COPY is required per value in the + /// complement interval. This also means that no extra PHI-defs need to be + /// inserted in the complement interval. + SM_Size, + + /// SM_Speed - Overlap intervals to minimize the expected execution + /// frequency of the inserted copies. This is very similar to SM_Size, but + /// the complement interval may get some extra PHI-defs. + SM_Speed + }; + +private: + /// Edit - The current parent register and new intervals created. LiveRangeEdit *Edit; @@ -225,6 +255,9 @@ class SplitEditor { /// openIntv will be 1. unsigned OpenIdx; + /// The current spill mode, selected by reset(). + ComplementSpillMode SpillMode; + typedef IntervalMap RegAssignMap; /// Allocator for the interval map. This will eventually be shared with @@ -354,7 +387,7 @@ public: MachineDominatorTree&); /// reset - Prepare for a new split. - void reset(LiveRangeEdit&); + void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition); /// Create a new virtual register and live interval. /// Return the interval index, starting from 1. Interval index 0 is the -- cgit v1.1 From b5a457c4cbc71db6ae313ef1bf8eadac65767ab0 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 13 Sep 2011 01:34:21 +0000 Subject: Extract live range calculations from SplitKit. 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 --- lib/CodeGen/SplitKit.h | 73 +++----------------------------------------------- 1 file changed, 3 insertions(+), 70 deletions(-) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 7f74d3a..c00b8d3 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -15,13 +15,11 @@ #ifndef LLVM_CODEGEN_SPLITKIT_H #define LLVM_CODEGEN_SPLITKIT_H +#include "LiveRangeCalc.h" #include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/IntervalMap.h" #include "llvm/ADT/SmallPtrSet.h" -#include "llvm/CodeGen/SlotIndexes.h" namespace llvm { @@ -38,12 +36,6 @@ class VirtRegMap; class VNInfo; class raw_ostream; -/// At some point we should just include MachineDominators.h: -class MachineDominatorTree; -template class DomTreeNodeBase; -typedef DomTreeNodeBase MachineDomTreeNode; - - /// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting /// opportunities. class SplitAnalysis { @@ -281,54 +273,8 @@ private: /// The new value has no live ranges anywhere. ValueMap Values; - typedef std::pair LiveOutPair; - typedef IndexedMap LiveOutMap; - - // LiveOutCache - Map each basic block where a new register is live out to the - // live-out value and its defining block. - // One of these conditions shall be true: - // - // 1. !LiveOutSeen.count(MBB->getNumber()) - // 2. LiveOutCache[MBB].second.getNode() == MBB - // 3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB] - // - // This is only a cache, the values can be computed as: - // - // VNI = Edit.get(RegIdx)->getVNInfoAt(LIS.getMBBEndIdx(MBB)) - // Node = mbt_[LIS.getMBBFromIndex(VNI->def)] - // - // The cache can be shared by all the new registers because at most one is - // live out of each block. - LiveOutMap LiveOutCache; - - // LiveOutSeen - Indexed by MBB->getNumber(), a bit is set for each valid - // entry in LiveOutCache. This is also used as a visited set for - // findReachingDefs(). - BitVector LiveOutSeen; - - /// LiveInBlock - Info for updateSSA() about a block where a register is - /// live-in. - /// The updateSSA caller provides DomNode and Kill inside MBB, updateSSA() - /// adds the computed live-in value. - struct LiveInBlock { - // Dominator tree node for the block. - // Cleared by updateSSA when the final value has been determined. - MachineDomTreeNode *DomNode; - - // Live-in value filled in by updateSSA once it is known. - VNInfo *Value; - - // Position in block where the live-in range ends, or SlotIndex() if the - // range passes through the block. - SlotIndex Kill; - - LiveInBlock(MachineDomTreeNode *node) : DomNode(node), Value(0) {} - }; - - /// LiveInBlocks - List of live-in blocks used by findReachingDefs() and - /// updateSSA(). This list is usually empty, it exists here to avoid frequent - /// reallocations. - SmallVector LiveInBlocks; + /// LRCalc - Cache for computing live ranges and SSA update. + LiveRangeCalc LRCalc; /// defValue - define a value in RegIdx from ParentVNI at Idx. /// Idx does not have to be ParentVNI->def, but it must be contained within @@ -353,19 +299,6 @@ private: /// Insert PHIDefs as needed to preserve SSA form. void extendRange(unsigned RegIdx, SlotIndex Idx); - /// findReachingDefs - Starting from MBB, add blocks to LiveInBlocks until all - /// reaching defs for LI are found. - /// @param LI Live interval whose value is needed. - /// @param MBB Block where LI should be live-in. - /// @param Kill Kill point in MBB. - /// @return Unique value seen, or NULL. - VNInfo *findReachingDefs(LiveInterval *LI, MachineBasicBlock *MBB, - SlotIndex Kill); - - /// updateSSA - Compute and insert PHIDefs such that all blocks in - // LiveInBlocks get a known live-in value. Add live ranges to the blocks. - void updateSSA(); - /// transferValues - Transfer values to the new ranges. /// Return true if any ranges were skipped. bool transferValues(); -- cgit v1.1 From c1c622ef0dd29d1bafd580790aec5231af50abf2 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 13 Sep 2011 16:47:53 +0000 Subject: Use a separate LiveRangeCalc for the complement in spill modes. 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 --- lib/CodeGen/SplitKit.h | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index c00b8d3..cd6a306 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -273,8 +273,17 @@ private: /// The new value has no live ranges anywhere. ValueMap Values; - /// LRCalc - Cache for computing live ranges and SSA update. - LiveRangeCalc LRCalc; + /// LRCalc - Cache for computing live ranges and SSA update. Each instance + /// can only handle non-overlapping live ranges, so use a separate + /// LiveRangeCalc instance for the complement interval when in spill mode. + LiveRangeCalc LRCalc[2]; + + /// getLRCalc - Return the LRCalc to use for RegIdx. In spill mode, the + /// complement interval can overlap the other intervals, so it gets its own + /// LRCalc instance. When not in spill mode, all intervals can share one. + LiveRangeCalc &getLRCalc(unsigned RegIdx) { + return LRCalc[SpillMode != SM_Partition && RegIdx != 0]; + } /// defValue - define a value in RegIdx from ParentVNI at Idx. /// Idx does not have to be ParentVNI->def, but it must be contained within -- cgit v1.1 From abcc73e8ba3131c7c4f198840ece31453a0101ac Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 13 Sep 2011 17:38:57 +0000 Subject: Eliminate the extendRange() wrapper. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139608 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/SplitKit.h | 4 ---- 1 file changed, 4 deletions(-) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index cd6a306..1a4937c 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -304,10 +304,6 @@ private: MachineBasicBlock &MBB, MachineBasicBlock::iterator I); - /// extendRange - Extend the live range of Edit.get(RegIdx) so it reaches Idx. - /// Insert PHIDefs as needed to preserve SSA form. - void extendRange(unsigned RegIdx, SlotIndex Idx); - /// transferValues - Transfer values to the new ranges. /// Return true if any ranges were skipped. bool transferValues(); -- cgit v1.1 From e5a2e366322ef5f0d597b1fb8dbf55f2cf36cf15 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 13 Sep 2011 18:05:29 +0000 Subject: Add SplitEditor::markOverlappedComplement(). 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 --- lib/CodeGen/SplitKit.h | 15 +++++++++++++++ 1 file changed, 15 insertions(+) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 1a4937c..5abdd4c 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -250,6 +250,10 @@ private: /// The current spill mode, selected by reset(). ComplementSpillMode SpillMode; + /// Parent interval values where the complement interval may be overlapping + /// other intervals. + SmallPtrSet OverlappedComplement; + typedef IntervalMap RegAssignMap; /// Allocator for the interval map. This will eventually be shared with @@ -296,6 +300,17 @@ private: /// of the number of defs. void markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI); + /// markOverlappedComplement - Mark ParentVNI as being overlapped in the + /// complement interval. The complement interval may overlap other intervals + /// after overlapIntv has been called, or when in spill mode. + void markOverlappedComplement(const VNInfo *ParentVNI); + + /// needsRecompute - Returns true if the live range of ParentVNI needs to be + /// recomputed in RegIdx using LiveRangeCalc::extend. This is the case if + /// the value has been rematerialized, or when back-copies have been hoisted + /// in spill mode. + bool needsRecompute(unsigned RegIdx, const VNInfo *ParentVNI); + /// defFromParent - Define Reg from ParentVNI at UseIdx using either /// rematerialization or a COPY from parent. Return the new value. VNInfo *defFromParent(unsigned RegIdx, -- cgit v1.1 From b21abfed813fa46976f896439ca2f9fbd2eba9ba Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 13 Sep 2011 22:22:39 +0000 Subject: Implement -split-spill-mode=size. 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 --- lib/CodeGen/SplitKit.h | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 5abdd4c..67e80fa 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -319,6 +319,14 @@ private: MachineBasicBlock &MBB, MachineBasicBlock::iterator I); + /// removeBackCopies - Remove the copy instructions that defines the values + /// in the vector in the complement interval. + void removeBackCopies(SmallVectorImpl &Copies); + + /// hoistCopiesForSize - Hoist back-copies to the complement interval in a + /// way that minimizes code size. This implements the SM_Size spill mode. + void hoistCopiesForSize(); + /// transferValues - Transfer values to the new ranges. /// Return true if any ranges were skipped. bool transferValues(); -- cgit v1.1 From 393bfcb263fa46e4badc73c6aa56306986f94dcf Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 13 Sep 2011 23:09:04 +0000 Subject: Distinguish complex mapped values from forced recomputation. 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 --- lib/CodeGen/SplitKit.h | 36 ++++++++++++++---------------------- 1 file changed, 14 insertions(+), 22 deletions(-) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 67e80fa..5a294e5 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -250,10 +250,6 @@ private: /// The current spill mode, selected by reset(). ComplementSpillMode SpillMode; - /// Parent interval values where the complement interval may be overlapping - /// other intervals. - SmallPtrSet OverlappedComplement; - typedef IntervalMap RegAssignMap; /// Allocator for the interval map. This will eventually be shared with @@ -265,15 +261,20 @@ private: /// Idx. RegAssignMap RegAssign; - typedef DenseMap, VNInfo*> ValueMap; + typedef PointerIntPair ValueForcePair; + typedef DenseMap, ValueForcePair> ValueMap; /// Values - keep track of the mapping from parent values to values in the new /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains: /// /// 1. No entry - the value is not mapped to Edit.get(RegIdx). - /// 2. Null - the value is mapped to multiple values in Edit.get(RegIdx). - /// Each value is represented by a minimal live range at its def. - /// 3. A non-null VNInfo - the value is mapped to a single new value. + /// 2. (Null, false) - the value is mapped to multiple values in + /// Edit.get(RegIdx). Each value is represented by a minimal live range at + /// its def. The full live range can be inferred exactly from the range + /// of RegIdx in RegAssign. + /// 3. (Null, true). As above, but the ranges in RegAssign are too large, and + /// the live range must be recomputed using LiveRangeCalc::extend(). + /// 4. (VNI, false) The value is mapped to a single new value. /// The new value has no live ranges anywhere. ValueMap Values; @@ -296,20 +297,11 @@ private: /// Return the new LI value. VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx); - /// markComplexMapped - Mark ParentVNI as complex mapped in RegIdx regardless - /// of the number of defs. - void markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI); - - /// markOverlappedComplement - Mark ParentVNI as being overlapped in the - /// complement interval. The complement interval may overlap other intervals - /// after overlapIntv has been called, or when in spill mode. - void markOverlappedComplement(const VNInfo *ParentVNI); - - /// needsRecompute - Returns true if the live range of ParentVNI needs to be - /// recomputed in RegIdx using LiveRangeCalc::extend. This is the case if - /// the value has been rematerialized, or when back-copies have been hoisted - /// in spill mode. - bool needsRecompute(unsigned RegIdx, const VNInfo *ParentVNI); + /// forceRecompute - Force the live range of ParentVNI in RegIdx to be + /// recomputed by LiveRangeCalc::extend regardless of the number of defs. + /// This is used for values whose live range doesn't match RegAssign exactly. + /// They could have rematerialized, or back-copies may have been moved. + void forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI); /// defFromParent - Define Reg from ParentVNI at UseIdx using either /// rematerialization or a COPY from parent. Return the new value. -- cgit v1.1 From c4c633852fbb8ab9ef2679b679d2862746d2fa3e Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Wed, 14 Sep 2011 16:45:39 +0000 Subject: Hoist back-copies to the least busy dominator. 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 --- lib/CodeGen/SplitKit.h | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'lib/CodeGen/SplitKit.h') diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 5a294e5..d8fc212 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -315,6 +315,11 @@ private: /// in the vector in the complement interval. void removeBackCopies(SmallVectorImpl &Copies); + /// getShallowDominator - Returns the least busy dominator of MBB that is + /// also dominated by DefMBB. Busy is measured by loop depth. + MachineBasicBlock *findShallowDominator(MachineBasicBlock *MBB, + MachineBasicBlock *DefMBB); + /// hoistCopiesForSize - Hoist back-copies to the complement interval in a /// way that minimizes code size. This implements the SM_Size spill mode. void hoistCopiesForSize(); -- cgit v1.1