Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 1 | //===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file contains the SplitAnalysis class as well as mutator functions for |
| 11 | // live range splitting. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
Jakob Stoklund Olesen | 376dcbd | 2010-11-03 20:39:23 +0000 | [diff] [blame] | 15 | #define DEBUG_TYPE "regalloc" |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 16 | #include "SplitKit.h" |
Jakob Stoklund Olesen | a17768f | 2010-10-14 23:49:52 +0000 | [diff] [blame] | 17 | #include "LiveRangeEdit.h" |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 18 | #include "VirtRegMap.h" |
Jakob Stoklund Olesen | 08e93b1 | 2010-08-10 17:07:22 +0000 | [diff] [blame] | 19 | #include "llvm/CodeGen/CalcSpillWeights.h" |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 20 | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
Jakob Stoklund Olesen | d68f458 | 2010-10-28 20:34:50 +0000 | [diff] [blame] | 21 | #include "llvm/CodeGen/MachineDominators.h" |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 22 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 23 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
Jakob Stoklund Olesen | 6a0dc07 | 2010-07-20 21:46:58 +0000 | [diff] [blame] | 24 | #include "llvm/Support/CommandLine.h" |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 25 | #include "llvm/Support/Debug.h" |
| 26 | #include "llvm/Support/raw_ostream.h" |
Jakob Stoklund Olesen | 6a0dc07 | 2010-07-20 21:46:58 +0000 | [diff] [blame] | 27 | #include "llvm/Target/TargetInstrInfo.h" |
| 28 | #include "llvm/Target/TargetMachine.h" |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 29 | |
| 30 | using namespace llvm; |
| 31 | |
Jakob Stoklund Olesen | 6a0dc07 | 2010-07-20 21:46:58 +0000 | [diff] [blame] | 32 | static cl::opt<bool> |
| 33 | AllowSplit("spiller-splits-edges", |
| 34 | cl::desc("Allow critical edge splitting during spilling")); |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 35 | |
| 36 | //===----------------------------------------------------------------------===// |
| 37 | // Split Analysis |
| 38 | //===----------------------------------------------------------------------===// |
| 39 | |
Jakob Stoklund Olesen | 1b847de | 2011-02-19 00:53:42 +0000 | [diff] [blame] | 40 | SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, |
Jakob Stoklund Olesen | f2c6e36 | 2010-07-20 23:50:15 +0000 | [diff] [blame] | 41 | const LiveIntervals &lis, |
| 42 | const MachineLoopInfo &mli) |
Jakob Stoklund Olesen | 1b847de | 2011-02-19 00:53:42 +0000 | [diff] [blame] | 43 | : MF(vrm.getMachineFunction()), |
| 44 | VRM(vrm), |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 45 | LIS(lis), |
| 46 | Loops(mli), |
Jakob Stoklund Olesen | 1b847de | 2011-02-19 00:53:42 +0000 | [diff] [blame] | 47 | TII(*MF.getTarget().getInstrInfo()), |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 48 | CurLI(0) {} |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 49 | |
| 50 | void SplitAnalysis::clear() { |
Jakob Stoklund Olesen | b5fa933 | 2011-01-18 21:13:27 +0000 | [diff] [blame] | 51 | UseSlots.clear(); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 52 | UsingInstrs.clear(); |
| 53 | UsingBlocks.clear(); |
Jakob Stoklund Olesen | f0ac26c | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 54 | LiveBlocks.clear(); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 55 | CurLI = 0; |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 56 | } |
| 57 | |
Jakob Stoklund Olesen | 6a0dc07 | 2010-07-20 21:46:58 +0000 | [diff] [blame] | 58 | bool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) { |
| 59 | MachineBasicBlock *T, *F; |
| 60 | SmallVector<MachineOperand, 4> Cond; |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 61 | return !TII.AnalyzeBranch(const_cast<MachineBasicBlock&>(*MBB), T, F, Cond); |
Jakob Stoklund Olesen | 6a0dc07 | 2010-07-20 21:46:58 +0000 | [diff] [blame] | 62 | } |
| 63 | |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 64 | /// analyzeUses - Count instructions, basic blocks, and loops using CurLI. |
Jakob Stoklund Olesen | abff280 | 2010-07-20 16:12:37 +0000 | [diff] [blame] | 65 | void SplitAnalysis::analyzeUses() { |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 66 | const MachineRegisterInfo &MRI = MF.getRegInfo(); |
Jakob Stoklund Olesen | a372d16 | 2011-02-09 21:52:09 +0000 | [diff] [blame] | 67 | for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(CurLI->reg), |
| 68 | E = MRI.reg_end(); I != E; ++I) { |
| 69 | MachineOperand &MO = I.getOperand(); |
| 70 | if (MO.isUse() && MO.isUndef()) |
| 71 | continue; |
| 72 | MachineInstr *MI = MO.getParent(); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 73 | if (MI->isDebugValue() || !UsingInstrs.insert(MI)) |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 74 | continue; |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 75 | UseSlots.push_back(LIS.getInstructionIndex(MI).getDefIndex()); |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 76 | MachineBasicBlock *MBB = MI->getParent(); |
Jakob Stoklund Olesen | 4f5c9d2 | 2011-02-09 23:56:18 +0000 | [diff] [blame] | 77 | UsingBlocks[MBB]++; |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 78 | } |
Jakob Stoklund Olesen | b5fa933 | 2011-01-18 21:13:27 +0000 | [diff] [blame] | 79 | array_pod_sort(UseSlots.begin(), UseSlots.end()); |
Jakob Stoklund Olesen | f0ac26c | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 80 | calcLiveBlockInfo(); |
Jakob Stoklund Olesen | e1f543f | 2010-08-12 18:50:55 +0000 | [diff] [blame] | 81 | DEBUG(dbgs() << " counted " |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 82 | << UsingInstrs.size() << " instrs, " |
Jakob Stoklund Olesen | 4f5c9d2 | 2011-02-09 23:56:18 +0000 | [diff] [blame] | 83 | << UsingBlocks.size() << " blocks.\n"); |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 84 | } |
| 85 | |
Jakob Stoklund Olesen | f0ac26c | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 86 | /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks |
| 87 | /// where CurLI is live. |
| 88 | void SplitAnalysis::calcLiveBlockInfo() { |
| 89 | if (CurLI->empty()) |
| 90 | return; |
| 91 | |
| 92 | LiveInterval::const_iterator LVI = CurLI->begin(); |
| 93 | LiveInterval::const_iterator LVE = CurLI->end(); |
| 94 | |
| 95 | SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; |
| 96 | UseI = UseSlots.begin(); |
| 97 | UseE = UseSlots.end(); |
| 98 | |
| 99 | // Loop over basic blocks where CurLI is live. |
| 100 | MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); |
| 101 | for (;;) { |
| 102 | BlockInfo BI; |
| 103 | BI.MBB = MFI; |
| 104 | SlotIndex Start, Stop; |
| 105 | tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); |
| 106 | |
| 107 | // The last split point is the latest possible insertion point that dominates |
| 108 | // all successor blocks. If interference reaches LastSplitPoint, it is not |
| 109 | // possible to insert a split or reload that makes CurLI live in the |
| 110 | // outgoing bundle. |
| 111 | MachineBasicBlock::iterator LSP = LIS.getLastSplitPoint(*CurLI, BI.MBB); |
| 112 | if (LSP == BI.MBB->end()) |
| 113 | BI.LastSplitPoint = Stop; |
| 114 | else |
| 115 | BI.LastSplitPoint = LIS.getInstructionIndex(LSP); |
| 116 | |
| 117 | // LVI is the first live segment overlapping MBB. |
| 118 | BI.LiveIn = LVI->start <= Start; |
| 119 | if (!BI.LiveIn) |
| 120 | BI.Def = LVI->start; |
| 121 | |
| 122 | // Find the first and last uses in the block. |
| 123 | BI.Uses = hasUses(MFI); |
| 124 | if (BI.Uses && UseI != UseE) { |
| 125 | BI.FirstUse = *UseI; |
| 126 | assert(BI.FirstUse >= Start); |
| 127 | do ++UseI; |
| 128 | while (UseI != UseE && *UseI < Stop); |
| 129 | BI.LastUse = UseI[-1]; |
| 130 | assert(BI.LastUse < Stop); |
| 131 | } |
| 132 | |
| 133 | // Look for gaps in the live range. |
| 134 | bool hasGap = false; |
| 135 | BI.LiveOut = true; |
| 136 | while (LVI->end < Stop) { |
| 137 | SlotIndex LastStop = LVI->end; |
| 138 | if (++LVI == LVE || LVI->start >= Stop) { |
| 139 | BI.Kill = LastStop; |
| 140 | BI.LiveOut = false; |
| 141 | break; |
| 142 | } |
| 143 | if (LastStop < LVI->start) { |
| 144 | hasGap = true; |
| 145 | BI.Kill = LastStop; |
| 146 | BI.Def = LVI->start; |
| 147 | } |
| 148 | } |
| 149 | |
| 150 | // Don't set LiveThrough when the block has a gap. |
| 151 | BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut; |
| 152 | LiveBlocks.push_back(BI); |
| 153 | |
| 154 | // LVI is now at LVE or LVI->end >= Stop. |
| 155 | if (LVI == LVE) |
| 156 | break; |
| 157 | |
| 158 | // Live segment ends exactly at Stop. Move to the next segment. |
| 159 | if (LVI->end == Stop && ++LVI == LVE) |
| 160 | break; |
| 161 | |
| 162 | // Pick the next basic block. |
| 163 | if (LVI->start < Stop) |
| 164 | ++MFI; |
| 165 | else |
| 166 | MFI = LIS.getMBBFromIndex(LVI->start); |
| 167 | } |
| 168 | } |
| 169 | |
Jakob Stoklund Olesen | 06c0f25 | 2011-02-21 23:09:46 +0000 | [diff] [blame] | 170 | bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { |
| 171 | unsigned OrigReg = VRM.getOriginal(CurLI->reg); |
| 172 | const LiveInterval &Orig = LIS.getInterval(OrigReg); |
| 173 | assert(!Orig.empty() && "Splitting empty interval?"); |
| 174 | LiveInterval::const_iterator I = Orig.find(Idx); |
| 175 | |
| 176 | // Range containing Idx should begin at Idx. |
| 177 | if (I != Orig.end() && I->start <= Idx) |
| 178 | return I->start == Idx; |
| 179 | |
| 180 | // Range does not contain Idx, previous must end at Idx. |
| 181 | return I != Orig.begin() && (--I)->end == Idx; |
| 182 | } |
| 183 | |
Jakob Stoklund Olesen | 532de3d | 2010-10-22 20:28:21 +0000 | [diff] [blame] | 184 | void SplitAnalysis::print(const BlockPtrSet &B, raw_ostream &OS) const { |
| 185 | for (BlockPtrSet::const_iterator I = B.begin(), E = B.end(); I != E; ++I) { |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 186 | unsigned count = UsingBlocks.lookup(*I); |
Jakob Stoklund Olesen | 532de3d | 2010-10-22 20:28:21 +0000 | [diff] [blame] | 187 | OS << " BB#" << (*I)->getNumber(); |
| 188 | if (count) |
| 189 | OS << '(' << count << ')'; |
| 190 | } |
| 191 | } |
| 192 | |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 193 | void SplitAnalysis::analyze(const LiveInterval *li) { |
| 194 | clear(); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 195 | CurLI = li; |
Jakob Stoklund Olesen | abff280 | 2010-07-20 16:12:37 +0000 | [diff] [blame] | 196 | analyzeUses(); |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 197 | } |
| 198 | |
Jakob Stoklund Olesen | 697483a | 2010-12-15 17:49:52 +0000 | [diff] [blame] | 199 | |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 200 | //===----------------------------------------------------------------------===// |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 201 | // LiveIntervalMap |
| 202 | //===----------------------------------------------------------------------===// |
| 203 | |
Jakob Stoklund Olesen | b3e9681 | 2010-09-13 21:29:45 +0000 | [diff] [blame] | 204 | // Work around the fact that the std::pair constructors are broken for pointer |
| 205 | // pairs in some implementations. makeVV(x, 0) works. |
| 206 | static inline std::pair<const VNInfo*, VNInfo*> |
| 207 | makeVV(const VNInfo *a, VNInfo *b) { |
| 208 | return std::make_pair(a, b); |
| 209 | } |
| 210 | |
Jakob Stoklund Olesen | 9ca2aeb | 2010-09-13 23:29:09 +0000 | [diff] [blame] | 211 | void LiveIntervalMap::reset(LiveInterval *li) { |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 212 | LI = li; |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 213 | LiveOutCache.clear(); |
Jakob Stoklund Olesen | 9ca2aeb | 2010-09-13 23:29:09 +0000 | [diff] [blame] | 214 | } |
| 215 | |
Jakob Stoklund Olesen | 5fa42a4 | 2010-09-21 22:32:21 +0000 | [diff] [blame] | 216 | |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 217 | // mapValue - Find the mapped value for ParentVNI at Idx. |
| 218 | // Potentially create phi-def values. |
Jakob Stoklund Olesen | 5fa42a4 | 2010-09-21 22:32:21 +0000 | [diff] [blame] | 219 | VNInfo *LiveIntervalMap::mapValue(const VNInfo *ParentVNI, SlotIndex Idx, |
| 220 | bool *simple) { |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 221 | assert(LI && "call reset first"); |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 222 | assert(ParentVNI && "Mapping NULL value"); |
| 223 | assert(Idx.isValid() && "Invalid SlotIndex"); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 224 | assert(ParentLI.getVNInfoAt(Idx) == ParentVNI && "Bad ParentVNI"); |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 225 | |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 226 | // This is a complex mapped value. There may be multiple defs, and we may need |
| 227 | // to create phi-defs. |
Jakob Stoklund Olesen | 5fa42a4 | 2010-09-21 22:32:21 +0000 | [diff] [blame] | 228 | if (simple) *simple = false; |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 229 | MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx); |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 230 | assert(IdxMBB && "No MBB at Idx"); |
| 231 | |
| 232 | // Is there a def in the same MBB we can extend? |
| 233 | if (VNInfo *VNI = extendTo(IdxMBB, Idx)) |
| 234 | return VNI; |
| 235 | |
| 236 | // Now for the fun part. We know that ParentVNI potentially has multiple defs, |
| 237 | // and we may need to create even more phi-defs to preserve VNInfo SSA form. |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 238 | // Perform a search for all predecessor blocks where we know the dominating |
| 239 | // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB. |
| 240 | DEBUG(dbgs() << "\n Reaching defs for BB#" << IdxMBB->getNumber() |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 241 | << " at " << Idx << " in " << *LI << '\n'); |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 242 | |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 243 | // Blocks where LI should be live-in. |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 244 | SmallVector<MachineDomTreeNode*, 16> LiveIn; |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 245 | LiveIn.push_back(MDT[IdxMBB]); |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 246 | |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 247 | // Using LiveOutCache as a visited set, perform a BFS for all reaching defs. |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 248 | for (unsigned i = 0; i != LiveIn.size(); ++i) { |
| 249 | MachineBasicBlock *MBB = LiveIn[i]->getBlock(); |
| 250 | for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), |
| 251 | PE = MBB->pred_end(); PI != PE; ++PI) { |
| 252 | MachineBasicBlock *Pred = *PI; |
| 253 | // Is this a known live-out block? |
| 254 | std::pair<LiveOutMap::iterator,bool> LOIP = |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 255 | LiveOutCache.insert(std::make_pair(Pred, LiveOutPair())); |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 256 | // Yes, we have been here before. |
| 257 | if (!LOIP.second) { |
Benjamin Kramer | 8a8e26f | 2010-10-29 17:40:05 +0000 | [diff] [blame] | 258 | DEBUG(if (VNInfo *VNI = LOIP.first->second.first) |
| 259 | dbgs() << " known valno #" << VNI->id |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 260 | << " at BB#" << Pred->getNumber() << '\n'); |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 261 | continue; |
| 262 | } |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 263 | |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 264 | // Does Pred provide a live-out value? |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 265 | SlotIndex Last = LIS.getMBBEndIdx(Pred).getPrevSlot(); |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 266 | if (VNInfo *VNI = extendTo(Pred, Last)) { |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 267 | MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(VNI->def); |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 268 | DEBUG(dbgs() << " found valno #" << VNI->id |
Jakob Stoklund Olesen | c94fcb1 | 2010-10-29 17:37:25 +0000 | [diff] [blame] | 269 | << " from BB#" << DefMBB->getNumber() |
| 270 | << " at BB#" << Pred->getNumber() << '\n'); |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 271 | LiveOutPair &LOP = LOIP.first->second; |
| 272 | LOP.first = VNI; |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 273 | LOP.second = MDT[DefMBB]; |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 274 | continue; |
| 275 | } |
| 276 | // No, we need a live-in value for Pred as well |
| 277 | if (Pred != IdxMBB) |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 278 | LiveIn.push_back(MDT[Pred]); |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 279 | } |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 280 | } |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 281 | |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 282 | // We may need to add phi-def values to preserve the SSA form. |
| 283 | // This is essentially the same iterative algorithm that SSAUpdater uses, |
| 284 | // except we already have a dominator tree, so we don't have to recompute it. |
| 285 | VNInfo *IdxVNI = 0; |
| 286 | unsigned Changes; |
| 287 | do { |
| 288 | Changes = 0; |
| 289 | DEBUG(dbgs() << " Iterating over " << LiveIn.size() << " blocks.\n"); |
| 290 | // Propagate live-out values down the dominator tree, inserting phi-defs when |
| 291 | // necessary. Since LiveIn was created by a BFS, going backwards makes it more |
| 292 | // likely for us to visit immediate dominators before their children. |
| 293 | for (unsigned i = LiveIn.size(); i; --i) { |
| 294 | MachineDomTreeNode *Node = LiveIn[i-1]; |
| 295 | MachineBasicBlock *MBB = Node->getBlock(); |
| 296 | MachineDomTreeNode *IDom = Node->getIDom(); |
| 297 | LiveOutPair IDomValue; |
| 298 | // We need a live-in value to a block with no immediate dominator? |
| 299 | // This is probably an unreachable block that has survived somehow. |
| 300 | bool needPHI = !IDom; |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 301 | |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 302 | // Get the IDom live-out value. |
| 303 | if (!needPHI) { |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 304 | LiveOutMap::iterator I = LiveOutCache.find(IDom->getBlock()); |
| 305 | if (I != LiveOutCache.end()) |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 306 | IDomValue = I->second; |
| 307 | else |
| 308 | // If IDom is outside our set of live-out blocks, there must be new |
| 309 | // defs, and we need a phi-def here. |
| 310 | needPHI = true; |
| 311 | } |
Jakob Stoklund Olesen | 984a7fc | 2010-10-05 20:36:28 +0000 | [diff] [blame] | 312 | |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 313 | // IDom dominates all of our predecessors, but it may not be the immediate |
| 314 | // dominator. Check if any of them have live-out values that are properly |
| 315 | // dominated by IDom. If so, we need a phi-def here. |
| 316 | if (!needPHI) { |
| 317 | for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), |
| 318 | PE = MBB->pred_end(); PI != PE; ++PI) { |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 319 | LiveOutPair Value = LiveOutCache[*PI]; |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 320 | if (!Value.first || Value.first == IDomValue.first) |
| 321 | continue; |
| 322 | // This predecessor is carrying something other than IDomValue. |
| 323 | // It could be because IDomValue hasn't propagated yet, or it could be |
| 324 | // because MBB is in the dominance frontier of that value. |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 325 | if (MDT.dominates(IDom, Value.second)) { |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 326 | needPHI = true; |
| 327 | break; |
| 328 | } |
| 329 | } |
| 330 | } |
Jakob Stoklund Olesen | ff3ae86 | 2010-08-18 20:29:53 +0000 | [diff] [blame] | 331 | |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 332 | // Create a phi-def if required. |
| 333 | if (needPHI) { |
| 334 | ++Changes; |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 335 | SlotIndex Start = LIS.getMBBStartIdx(MBB); |
| 336 | VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator()); |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 337 | VNI->setIsPHIDef(true); |
| 338 | DEBUG(dbgs() << " - BB#" << MBB->getNumber() |
| 339 | << " phi-def #" << VNI->id << " at " << Start << '\n'); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 340 | // We no longer need LI to be live-in. |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 341 | LiveIn.erase(LiveIn.begin()+(i-1)); |
| 342 | // Blocks in LiveIn are either IdxMBB, or have a value live-through. |
| 343 | if (MBB == IdxMBB) |
| 344 | IdxVNI = VNI; |
| 345 | // Check if we need to update live-out info. |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 346 | LiveOutMap::iterator I = LiveOutCache.find(MBB); |
| 347 | if (I == LiveOutCache.end() || I->second.second == Node) { |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 348 | // We already have a live-out defined in MBB, so this must be IdxMBB. |
| 349 | assert(MBB == IdxMBB && "Adding phi-def to known live-out"); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 350 | LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI)); |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 351 | } else { |
| 352 | // This phi-def is also live-out, so color the whole block. |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 353 | LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 354 | I->second = LiveOutPair(VNI, Node); |
| 355 | } |
| 356 | } else if (IDomValue.first) { |
Jakob Stoklund Olesen | c94fcb1 | 2010-10-29 17:37:25 +0000 | [diff] [blame] | 357 | // No phi-def here. Remember incoming value for IdxMBB. |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 358 | if (MBB == IdxMBB) |
| 359 | IdxVNI = IDomValue.first; |
Jakob Stoklund Olesen | c94fcb1 | 2010-10-29 17:37:25 +0000 | [diff] [blame] | 360 | // Propagate IDomValue if needed: |
| 361 | // MBB is live-out and doesn't define its own value. |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 362 | LiveOutMap::iterator I = LiveOutCache.find(MBB); |
| 363 | if (I != LiveOutCache.end() && I->second.second != Node && |
Jakob Stoklund Olesen | c94fcb1 | 2010-10-29 17:37:25 +0000 | [diff] [blame] | 364 | I->second.first != IDomValue.first) { |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 365 | ++Changes; |
| 366 | I->second = IDomValue; |
| 367 | DEBUG(dbgs() << " - BB#" << MBB->getNumber() |
| 368 | << " idom valno #" << IDomValue.first->id |
| 369 | << " from BB#" << IDom->getBlock()->getNumber() << '\n'); |
| 370 | } |
Jakob Stoklund Olesen | ff3ae86 | 2010-08-18 20:29:53 +0000 | [diff] [blame] | 371 | } |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 372 | } |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 373 | DEBUG(dbgs() << " - made " << Changes << " changes.\n"); |
| 374 | } while (Changes); |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 375 | |
| 376 | assert(IdxVNI && "Didn't find value for Idx"); |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 377 | |
| 378 | #ifndef NDEBUG |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 379 | // Check the LiveOutCache invariants. |
| 380 | for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end(); |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 381 | I != E; ++I) { |
| 382 | assert(I->first && "Null MBB entry in cache"); |
| 383 | assert(I->second.first && "Null VNInfo in cache"); |
| 384 | assert(I->second.second && "Null DomTreeNode in cache"); |
| 385 | if (I->second.second->getBlock() == I->first) |
| 386 | continue; |
| 387 | for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(), |
| 388 | PE = I->first->pred_end(); PI != PE; ++PI) |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 389 | assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant"); |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 390 | } |
| 391 | #endif |
| 392 | |
| 393 | // Since we went through the trouble of a full BFS visiting all reaching defs, |
| 394 | // the values in LiveIn are now accurate. No more phi-defs are needed |
| 395 | // for these blocks, so we can color the live ranges. |
| 396 | // This makes the next mapValue call much faster. |
| 397 | for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) { |
| 398 | MachineBasicBlock *MBB = LiveIn[i]->getBlock(); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 399 | SlotIndex Start = LIS.getMBBStartIdx(MBB); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 400 | VNInfo *VNI = LiveOutCache.lookup(MBB).first; |
Jakob Stoklund Olesen | 08eb8dd | 2011-02-03 20:29:36 +0000 | [diff] [blame] | 401 | |
| 402 | // Anything in LiveIn other than IdxMBB is live-through. |
| 403 | // In IdxMBB, we should stop at Idx unless the same value is live-out. |
| 404 | if (MBB == IdxMBB && IdxVNI != VNI) |
| 405 | LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI)); |
| 406 | else |
| 407 | LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI)); |
Jakob Stoklund Olesen | e1dde7b | 2010-10-28 20:34:52 +0000 | [diff] [blame] | 408 | } |
| 409 | |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 410 | return IdxVNI; |
| 411 | } |
| 412 | |
Jakob Stoklund Olesen | d7ca577 | 2011-01-20 17:45:20 +0000 | [diff] [blame] | 413 | #ifndef NDEBUG |
| 414 | void LiveIntervalMap::dumpCache() { |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 415 | for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end(); |
Jakob Stoklund Olesen | d7ca577 | 2011-01-20 17:45:20 +0000 | [diff] [blame] | 416 | I != E; ++I) { |
| 417 | assert(I->first && "Null MBB entry in cache"); |
| 418 | assert(I->second.first && "Null VNInfo in cache"); |
| 419 | assert(I->second.second && "Null DomTreeNode in cache"); |
| 420 | dbgs() << " cache: BB#" << I->first->getNumber() |
| 421 | << " has valno #" << I->second.first->id << " from BB#" |
| 422 | << I->second.second->getBlock()->getNumber() << ", preds"; |
| 423 | for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(), |
| 424 | PE = I->first->pred_end(); PI != PE; ++PI) |
| 425 | dbgs() << " BB#" << (*PI)->getNumber(); |
| 426 | dbgs() << '\n'; |
| 427 | } |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 428 | dbgs() << " cache: " << LiveOutCache.size() << " entries.\n"; |
Jakob Stoklund Olesen | d7ca577 | 2011-01-20 17:45:20 +0000 | [diff] [blame] | 429 | } |
| 430 | #endif |
| 431 | |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 432 | // extendTo - Find the last LI value defined in MBB at or before Idx. The |
| 433 | // ParentLI is assumed to be live at Idx. Extend the live range to Idx. |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 434 | // Return the found VNInfo, or NULL. |
Jakob Stoklund Olesen | c95c146 | 2010-10-27 00:39:07 +0000 | [diff] [blame] | 435 | VNInfo *LiveIntervalMap::extendTo(const MachineBasicBlock *MBB, SlotIndex Idx) { |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 436 | assert(LI && "call reset first"); |
| 437 | LiveInterval::iterator I = std::upper_bound(LI->begin(), LI->end(), Idx); |
| 438 | if (I == LI->begin()) |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 439 | return 0; |
| 440 | --I; |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 441 | if (I->end <= LIS.getMBBStartIdx(MBB)) |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 442 | return 0; |
Jakob Stoklund Olesen | f6a129a | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 443 | if (I->end <= Idx) |
| 444 | I->end = Idx.getNextSlot(); |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 445 | return I->valno; |
| 446 | } |
| 447 | |
Jakob Stoklund Olesen | f6a129a | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 448 | |
Jakob Stoklund Olesen | 1407c84 | 2010-08-18 19:00:08 +0000 | [diff] [blame] | 449 | //===----------------------------------------------------------------------===// |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 450 | // Split Editor |
| 451 | //===----------------------------------------------------------------------===// |
| 452 | |
| 453 | /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. |
Jakob Stoklund Olesen | d68f458 | 2010-10-28 20:34:50 +0000 | [diff] [blame] | 454 | SplitEditor::SplitEditor(SplitAnalysis &sa, |
| 455 | LiveIntervals &lis, |
| 456 | VirtRegMap &vrm, |
| 457 | MachineDominatorTree &mdt, |
Jakob Stoklund Olesen | a17768f | 2010-10-14 23:49:52 +0000 | [diff] [blame] | 458 | LiveRangeEdit &edit) |
Jakob Stoklund Olesen | 0eeca44 | 2011-02-19 00:42:33 +0000 | [diff] [blame] | 459 | : SA(sa), LIS(lis), VRM(vrm), |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 460 | MRI(vrm.getMachineFunction().getRegInfo()), |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 461 | MDT(mdt), |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 462 | TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), |
| 463 | TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), |
| 464 | Edit(edit), |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 465 | OpenIdx(0), |
| 466 | RegAssign(Allocator) |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 467 | { |
Jakob Stoklund Olesen | cfa7134 | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 468 | // We don't need an AliasAnalysis since we will only be performing |
| 469 | // cheap-as-a-copy remats anyway. |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 470 | Edit.anyRematerializable(LIS, TII, 0); |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 471 | } |
| 472 | |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 473 | void SplitEditor::dump() const { |
| 474 | if (RegAssign.empty()) { |
| 475 | dbgs() << " empty\n"; |
| 476 | return; |
| 477 | } |
| 478 | |
| 479 | for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) |
| 480 | dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); |
| 481 | dbgs() << '\n'; |
Jakob Stoklund Olesen | 5fa42a4 | 2010-09-21 22:32:21 +0000 | [diff] [blame] | 482 | } |
| 483 | |
Jakob Stoklund Olesen | 670ccd1 | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 484 | VNInfo *SplitEditor::defValue(unsigned RegIdx, |
| 485 | const VNInfo *ParentVNI, |
| 486 | SlotIndex Idx) { |
| 487 | assert(ParentVNI && "Mapping NULL value"); |
| 488 | assert(Idx.isValid() && "Invalid SlotIndex"); |
| 489 | assert(Edit.getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); |
| 490 | LiveInterval *LI = Edit.get(RegIdx); |
| 491 | |
| 492 | // Create a new value. |
| 493 | VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); |
| 494 | |
| 495 | // Preserve the PHIDef bit. |
| 496 | if (ParentVNI->isPHIDef() && Idx == ParentVNI->def) |
| 497 | VNI->setIsPHIDef(true); |
| 498 | |
| 499 | // Use insert for lookup, so we can add missing values with a second lookup. |
| 500 | std::pair<ValueMap::iterator, bool> InsP = |
| 501 | Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); |
| 502 | |
| 503 | // This was the first time (RegIdx, ParentVNI) was mapped. |
| 504 | // Keep it as a simple def without any liveness. |
| 505 | if (InsP.second) |
| 506 | return VNI; |
| 507 | |
| 508 | // If the previous value was a simple mapping, add liveness for it now. |
| 509 | if (VNInfo *OldVNI = InsP.first->second) { |
| 510 | SlotIndex Def = OldVNI->def; |
| 511 | LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); |
| 512 | // No longer a simple mapping. |
| 513 | InsP.first->second = 0; |
| 514 | } |
| 515 | |
| 516 | // This is a complex mapping, add liveness for VNI |
| 517 | SlotIndex Def = VNI->def; |
| 518 | LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); |
| 519 | |
| 520 | return VNI; |
| 521 | } |
| 522 | |
| 523 | void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { |
| 524 | assert(ParentVNI && "Mapping NULL value"); |
| 525 | VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; |
| 526 | |
| 527 | // ParentVNI was either unmapped or already complex mapped. Either way. |
| 528 | if (!VNI) |
| 529 | return; |
| 530 | |
| 531 | // This was previously a single mapping. Make sure the old def is represented |
| 532 | // by a trivial live range. |
| 533 | SlotIndex Def = VNI->def; |
| 534 | Edit.get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); |
| 535 | VNI = 0; |
| 536 | } |
| 537 | |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 538 | VNInfo *SplitEditor::defFromParent(unsigned RegIdx, |
Jakob Stoklund Olesen | cfa7134 | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 539 | VNInfo *ParentVNI, |
| 540 | SlotIndex UseIdx, |
| 541 | MachineBasicBlock &MBB, |
| 542 | MachineBasicBlock::iterator I) { |
Jakob Stoklund Olesen | cfa7134 | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 543 | MachineInstr *CopyMI = 0; |
| 544 | SlotIndex Def; |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 545 | LiveInterval *LI = Edit.get(RegIdx); |
Jakob Stoklund Olesen | cfa7134 | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 546 | |
| 547 | // Attempt cheap-as-a-copy rematerialization. |
| 548 | LiveRangeEdit::Remat RM(ParentVNI); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 549 | if (Edit.canRematerializeAt(RM, UseIdx, true, LIS)) { |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 550 | Def = Edit.rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI); |
Jakob Stoklund Olesen | cfa7134 | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 551 | } else { |
| 552 | // Can't remat, just insert a copy from parent. |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 553 | CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) |
| 554 | .addReg(Edit.getReg()); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 555 | Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex(); |
Jakob Stoklund Olesen | cfa7134 | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 556 | } |
| 557 | |
Jakob Stoklund Olesen | 670ccd1 | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 558 | // Temporarily mark all values as complex mapped. |
| 559 | markComplexMapped(RegIdx, ParentVNI); |
Jakob Stoklund Olesen | cfa7134 | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 560 | |
Jakob Stoklund Olesen | 670ccd1 | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 561 | // Define the value in Reg. |
| 562 | VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); |
| 563 | VNI->setCopy(CopyMI); |
Jakob Stoklund Olesen | cfa7134 | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 564 | return VNI; |
| 565 | } |
| 566 | |
Jakob Stoklund Olesen | 7536f72 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 567 | /// Create a new virtual register and live interval. |
| 568 | void SplitEditor::openIntv() { |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 569 | assert(!OpenIdx && "Previous LI not closed before openIntv"); |
Jakob Stoklund Olesen | f6a129a | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 570 | |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 571 | // Create the complement as index 0. |
| 572 | if (Edit.empty()) { |
| 573 | Edit.create(MRI, LIS, VRM); |
| 574 | LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent())); |
| 575 | LIMappers.back().reset(Edit.get(0)); |
| 576 | } |
| 577 | |
| 578 | // Create the open interval. |
| 579 | OpenIdx = Edit.size(); |
| 580 | Edit.create(MRI, LIS, VRM); |
| 581 | LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent())); |
| 582 | LIMappers[OpenIdx].reset(Edit.get(OpenIdx)); |
Jakob Stoklund Olesen | 7536f72 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 583 | } |
| 584 | |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 585 | SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 586 | assert(OpenIdx && "openIntv not called before enterIntvBefore"); |
Jakob Stoklund Olesen | 9b24afe | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 587 | DEBUG(dbgs() << " enterIntvBefore " << Idx); |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 588 | Idx = Idx.getBaseIndex(); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 589 | VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); |
Jakob Stoklund Olesen | f6a129a | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 590 | if (!ParentVNI) { |
Jakob Stoklund Olesen | 9b24afe | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 591 | DEBUG(dbgs() << ": not live\n"); |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 592 | return Idx; |
Jakob Stoklund Olesen | f1b05f2 | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 593 | } |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 594 | DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 595 | MachineInstr *MI = LIS.getInstructionFromIndex(Idx); |
Jakob Stoklund Olesen | f6a129a | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 596 | assert(MI && "enterIntvBefore called with invalid index"); |
Jakob Stoklund Olesen | cfa7134 | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 597 | |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 598 | VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); |
| 599 | return VNI->def; |
Jakob Stoklund Olesen | f1b05f2 | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 600 | } |
| 601 | |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 602 | SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 603 | assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 604 | SlotIndex End = LIS.getMBBEndIdx(&MBB); |
| 605 | SlotIndex Last = End.getPrevSlot(); |
| 606 | DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); |
| 607 | VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Last); |
Jakob Stoklund Olesen | f6a129a | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 608 | if (!ParentVNI) { |
Jakob Stoklund Olesen | 9b24afe | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 609 | DEBUG(dbgs() << ": not live\n"); |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 610 | return End; |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 611 | } |
Jakob Stoklund Olesen | 9b24afe | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 612 | DEBUG(dbgs() << ": valno " << ParentVNI->id); |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 613 | VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, |
Jakob Stoklund Olesen | cb64047 | 2011-02-04 19:33:11 +0000 | [diff] [blame] | 614 | LIS.getLastSplitPoint(Edit.getParent(), &MBB)); |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 615 | RegAssign.insert(VNI->def, End, OpenIdx); |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 616 | DEBUG(dump()); |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 617 | return VNI->def; |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 618 | } |
| 619 | |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 620 | /// useIntv - indicate that all instructions in MBB should use OpenLI. |
Jakob Stoklund Olesen | 7536f72 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 621 | void SplitEditor::useIntv(const MachineBasicBlock &MBB) { |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 622 | useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 623 | } |
| 624 | |
Jakob Stoklund Olesen | 7536f72 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 625 | void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 626 | assert(OpenIdx && "openIntv not called before useIntv"); |
| 627 | DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); |
| 628 | RegAssign.insert(Start, End, OpenIdx); |
| 629 | DEBUG(dump()); |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 630 | } |
| 631 | |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 632 | SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 633 | assert(OpenIdx && "openIntv not called before leaveIntvAfter"); |
Jakob Stoklund Olesen | 9b24afe | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 634 | DEBUG(dbgs() << " leaveIntvAfter " << Idx); |
Jakob Stoklund Olesen | f1b05f2 | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 635 | |
Jakob Stoklund Olesen | f6a129a | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 636 | // The interval must be live beyond the instruction at Idx. |
Jakob Stoklund Olesen | cfa7134 | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 637 | Idx = Idx.getBoundaryIndex(); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 638 | VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); |
Jakob Stoklund Olesen | f6a129a | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 639 | if (!ParentVNI) { |
Jakob Stoklund Olesen | 9b24afe | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 640 | DEBUG(dbgs() << ": not live\n"); |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 641 | return Idx.getNextSlot(); |
Jakob Stoklund Olesen | f1b05f2 | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 642 | } |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 643 | DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); |
Jakob Stoklund Olesen | f1b05f2 | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 644 | |
Jakob Stoklund Olesen | 01cb34b | 2011-02-08 18:50:18 +0000 | [diff] [blame] | 645 | MachineInstr *MI = LIS.getInstructionFromIndex(Idx); |
| 646 | assert(MI && "No instruction at index"); |
| 647 | VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), |
| 648 | llvm::next(MachineBasicBlock::iterator(MI))); |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 649 | return VNI->def; |
Jakob Stoklund Olesen | f1b05f2 | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 650 | } |
| 651 | |
Jakob Stoklund Olesen | 9b05777 | 2011-02-09 23:30:25 +0000 | [diff] [blame] | 652 | SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { |
| 653 | assert(OpenIdx && "openIntv not called before leaveIntvBefore"); |
| 654 | DEBUG(dbgs() << " leaveIntvBefore " << Idx); |
| 655 | |
| 656 | // The interval must be live into the instruction at Idx. |
| 657 | Idx = Idx.getBoundaryIndex(); |
| 658 | VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); |
| 659 | if (!ParentVNI) { |
| 660 | DEBUG(dbgs() << ": not live\n"); |
| 661 | return Idx.getNextSlot(); |
| 662 | } |
| 663 | DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); |
| 664 | |
| 665 | MachineInstr *MI = LIS.getInstructionFromIndex(Idx); |
| 666 | assert(MI && "No instruction at index"); |
| 667 | VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); |
| 668 | return VNI->def; |
| 669 | } |
| 670 | |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 671 | SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 672 | assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 673 | SlotIndex Start = LIS.getMBBStartIdx(&MBB); |
Jakob Stoklund Olesen | 9b24afe | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 674 | DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); |
Jakob Stoklund Olesen | 7536f72 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 675 | |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 676 | VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Start); |
Jakob Stoklund Olesen | f6a129a | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 677 | if (!ParentVNI) { |
Jakob Stoklund Olesen | 9b24afe | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 678 | DEBUG(dbgs() << ": not live\n"); |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 679 | return Start; |
Jakob Stoklund Olesen | 7536f72 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 680 | } |
| 681 | |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 682 | VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, |
Jakob Stoklund Olesen | cfa7134 | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 683 | MBB.SkipPHIsAndLabels(MBB.begin())); |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 684 | RegAssign.insert(Start, VNI->def, OpenIdx); |
| 685 | DEBUG(dump()); |
Jakob Stoklund Olesen | 207c868 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 686 | return VNI->def; |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 687 | } |
| 688 | |
Jakob Stoklund Olesen | 5c716bd | 2011-02-08 18:50:21 +0000 | [diff] [blame] | 689 | void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { |
| 690 | assert(OpenIdx && "openIntv not called before overlapIntv"); |
| 691 | assert(Edit.getParent().getVNInfoAt(Start) == |
| 692 | Edit.getParent().getVNInfoAt(End.getPrevSlot()) && |
| 693 | "Parent changes value in extended range"); |
| 694 | assert(Edit.get(0)->getVNInfoAt(Start) && "Start must come from leaveIntv*"); |
| 695 | assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && |
| 696 | "Range cannot span basic blocks"); |
| 697 | |
| 698 | // Treat this as useIntv() for now. The complement interval will be extended |
| 699 | // as needed by mapValue(). |
| 700 | DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); |
| 701 | RegAssign.insert(Start, End, OpenIdx); |
| 702 | DEBUG(dump()); |
| 703 | } |
| 704 | |
Jakob Stoklund Olesen | 7536f72 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 705 | /// closeIntv - Indicate that we are done editing the currently open |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 706 | /// LiveInterval, and ranges can be trimmed. |
Jakob Stoklund Olesen | 7536f72 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 707 | void SplitEditor::closeIntv() { |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 708 | assert(OpenIdx && "openIntv not called before closeIntv"); |
| 709 | OpenIdx = 0; |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 710 | } |
| 711 | |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 712 | /// rewriteAssigned - Rewrite all uses of Edit.getReg(). |
| 713 | void SplitEditor::rewriteAssigned() { |
| 714 | for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit.getReg()), |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 715 | RE = MRI.reg_end(); RI != RE;) { |
Jakob Stoklund Olesen | 7466927 | 2010-10-08 23:42:21 +0000 | [diff] [blame] | 716 | MachineOperand &MO = RI.getOperand(); |
| 717 | MachineInstr *MI = MO.getParent(); |
| 718 | ++RI; |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 719 | // LiveDebugVariables should have handled all DBG_VALUE instructions. |
Jakob Stoklund Olesen | 7466927 | 2010-10-08 23:42:21 +0000 | [diff] [blame] | 720 | if (MI->isDebugValue()) { |
| 721 | DEBUG(dbgs() << "Zapping " << *MI); |
Jakob Stoklund Olesen | 7466927 | 2010-10-08 23:42:21 +0000 | [diff] [blame] | 722 | MO.setReg(0); |
| 723 | continue; |
| 724 | } |
Jakob Stoklund Olesen | a372d16 | 2011-02-09 21:52:09 +0000 | [diff] [blame] | 725 | |
| 726 | // <undef> operands don't really read the register, so just assign them to |
| 727 | // the complement. |
| 728 | if (MO.isUse() && MO.isUndef()) { |
| 729 | MO.setReg(Edit.get(0)->reg); |
| 730 | continue; |
| 731 | } |
| 732 | |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 733 | SlotIndex Idx = LIS.getInstructionIndex(MI); |
Jakob Stoklund Olesen | 7466927 | 2010-10-08 23:42:21 +0000 | [diff] [blame] | 734 | Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 735 | |
| 736 | // Rewrite to the mapped register at Idx. |
| 737 | unsigned RegIdx = RegAssign.lookup(Idx); |
| 738 | MO.setReg(Edit.get(RegIdx)->reg); |
| 739 | DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' |
| 740 | << Idx << ':' << RegIdx << '\t' << *MI); |
| 741 | |
| 742 | // Extend liveness to Idx. |
| 743 | const VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx); |
| 744 | LIMappers[RegIdx].mapValue(ParentVNI, Idx); |
Jakob Stoklund Olesen | 7466927 | 2010-10-08 23:42:21 +0000 | [diff] [blame] | 745 | } |
| 746 | } |
| 747 | |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 748 | /// rewriteSplit - Rewrite uses of Intvs[0] according to the ConEQ mapping. |
| 749 | void SplitEditor::rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs, |
| 750 | const ConnectedVNInfoEqClasses &ConEq) { |
| 751 | for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Intvs[0]->reg), |
| 752 | RE = MRI.reg_end(); RI != RE;) { |
| 753 | MachineOperand &MO = RI.getOperand(); |
| 754 | MachineInstr *MI = MO.getParent(); |
| 755 | ++RI; |
| 756 | if (MO.isUse() && MO.isUndef()) |
Jakob Stoklund Olesen | 9d99977 | 2010-10-21 18:47:08 +0000 | [diff] [blame] | 757 | continue; |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 758 | // DBG_VALUE instructions should have been eliminated earlier. |
| 759 | SlotIndex Idx = LIS.getInstructionIndex(MI); |
| 760 | Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); |
| 761 | DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' |
| 762 | << Idx << ':'); |
| 763 | const VNInfo *VNI = Intvs[0]->getVNInfoAt(Idx); |
| 764 | assert(VNI && "Interval not live at use."); |
| 765 | MO.setReg(Intvs[ConEq.getEqClass(VNI)]->reg); |
| 766 | DEBUG(dbgs() << VNI->id << '\t' << *MI); |
Eric Christopher | 463a297 | 2011-02-03 05:40:54 +0000 | [diff] [blame] | 767 | } |
Eric Christopher | 463a297 | 2011-02-03 05:40:54 +0000 | [diff] [blame] | 768 | } |
Jakob Stoklund Olesen | 2cd2111 | 2011-02-03 00:54:23 +0000 | [diff] [blame] | 769 | |
Eric Christopher | 463a297 | 2011-02-03 05:40:54 +0000 | [diff] [blame] | 770 | void SplitEditor::finish() { |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 771 | assert(OpenIdx == 0 && "Previous LI not closed before rewrite"); |
Eric Christopher | 463a297 | 2011-02-03 05:40:54 +0000 | [diff] [blame] | 772 | |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 773 | // At this point, the live intervals in Edit contain VNInfos corresponding to |
| 774 | // the inserted copies. |
| 775 | |
| 776 | // Add the original defs from the parent interval. |
| 777 | for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(), |
| 778 | E = Edit.getParent().vni_end(); I != E; ++I) { |
| 779 | const VNInfo *ParentVNI = *I; |
Jakob Stoklund Olesen | 9ecd1e7 | 2011-02-04 00:59:23 +0000 | [diff] [blame] | 780 | if (ParentVNI->isUnused()) |
| 781 | continue; |
Jakob Stoklund Olesen | 670ccd1 | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 782 | unsigned RegIdx = RegAssign.lookup(ParentVNI->def); |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 783 | // Mark all values as complex to force liveness computation. |
| 784 | // This should really only be necessary for remat victims, but we are lazy. |
Jakob Stoklund Olesen | 670ccd1 | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 785 | markComplexMapped(RegIdx, ParentVNI); |
| 786 | defValue(RegIdx, ParentVNI, ParentVNI->def); |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 787 | } |
| 788 | |
| 789 | #ifndef NDEBUG |
| 790 | // Every new interval must have a def by now, otherwise the split is bogus. |
| 791 | for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I) |
| 792 | assert((*I)->hasAtLeastOneValue() && "Split interval has no value"); |
| 793 | #endif |
| 794 | |
| 795 | // FIXME: Don't recompute the liveness of all values, infer it from the |
| 796 | // overlaps between the parent live interval and RegAssign. |
| 797 | // The mapValue algorithm is only necessary when: |
| 798 | // - The parent value maps to multiple defs, and new phis are needed, or |
| 799 | // - The value has been rematerialized before some uses, and we want to |
| 800 | // minimize the live range so it only reaches the remaining uses. |
| 801 | // All other values have simple liveness that can be computed from RegAssign |
| 802 | // and the parent live interval. |
| 803 | |
| 804 | // Extend live ranges to be live-out for successor PHI values. |
| 805 | for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(), |
| 806 | E = Edit.getParent().vni_end(); I != E; ++I) { |
| 807 | const VNInfo *PHIVNI = *I; |
Jakob Stoklund Olesen | 9ecd1e7 | 2011-02-04 00:59:23 +0000 | [diff] [blame] | 808 | if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 809 | continue; |
Jakob Stoklund Olesen | c50f077 | 2011-02-03 20:29:39 +0000 | [diff] [blame] | 810 | unsigned RegIdx = RegAssign.lookup(PHIVNI->def); |
| 811 | LiveIntervalMap &LIM = LIMappers[RegIdx]; |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 812 | MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); |
Jakob Stoklund Olesen | c50f077 | 2011-02-03 20:29:39 +0000 | [diff] [blame] | 813 | DEBUG(dbgs() << " map phi in BB#" << MBB->getNumber() << '@' << PHIVNI->def |
| 814 | << " -> " << RegIdx << '\n'); |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 815 | for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), |
| 816 | PE = MBB->pred_end(); PI != PE; ++PI) { |
| 817 | SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); |
Jakob Stoklund Olesen | c50f077 | 2011-02-03 20:29:39 +0000 | [diff] [blame] | 818 | DEBUG(dbgs() << " pred BB#" << (*PI)->getNumber() << '@' << End); |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 819 | // The predecessor may not have a live-out value. That is OK, like an |
| 820 | // undef PHI operand. |
Jakob Stoklund Olesen | c50f077 | 2011-02-03 20:29:39 +0000 | [diff] [blame] | 821 | if (VNInfo *VNI = Edit.getParent().getVNInfoAt(End)) { |
| 822 | DEBUG(dbgs() << " has parent valno #" << VNI->id << " live out\n"); |
| 823 | assert(RegAssign.lookup(End) == RegIdx && |
| 824 | "Different register assignment in phi predecessor"); |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 825 | LIM.mapValue(VNI, End); |
Jakob Stoklund Olesen | c50f077 | 2011-02-03 20:29:39 +0000 | [diff] [blame] | 826 | } |
| 827 | else |
| 828 | DEBUG(dbgs() << " is not live-out\n"); |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 829 | } |
Jakob Stoklund Olesen | c50f077 | 2011-02-03 20:29:39 +0000 | [diff] [blame] | 830 | DEBUG(dbgs() << " " << *LIM.getLI() << '\n'); |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 831 | } |
| 832 | |
| 833 | // Rewrite instructions. |
| 834 | rewriteAssigned(); |
| 835 | |
| 836 | // FIXME: Delete defs that were rematted everywhere. |
Jakob Stoklund Olesen | 5fa42a4 | 2010-09-21 22:32:21 +0000 | [diff] [blame] | 837 | |
Jakob Stoklund Olesen | 0253df9 | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 838 | // Get rid of unused values and set phi-kill flags. |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 839 | for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I) |
| 840 | (*I)->RenumberValues(LIS); |
Jakob Stoklund Olesen | 5fa42a4 | 2010-09-21 22:32:21 +0000 | [diff] [blame] | 841 | |
Jakob Stoklund Olesen | 3a0e071 | 2010-10-26 22:36:09 +0000 | [diff] [blame] | 842 | // Now check if any registers were separated into multiple components. |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 843 | ConnectedVNInfoEqClasses ConEQ(LIS); |
| 844 | for (unsigned i = 0, e = Edit.size(); i != e; ++i) { |
Jakob Stoklund Olesen | 3a0e071 | 2010-10-26 22:36:09 +0000 | [diff] [blame] | 845 | // Don't use iterators, they are invalidated by create() below. |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 846 | LiveInterval *li = Edit.get(i); |
Jakob Stoklund Olesen | 3a0e071 | 2010-10-26 22:36:09 +0000 | [diff] [blame] | 847 | unsigned NumComp = ConEQ.Classify(li); |
| 848 | if (NumComp <= 1) |
| 849 | continue; |
| 850 | DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); |
| 851 | SmallVector<LiveInterval*, 8> dups; |
| 852 | dups.push_back(li); |
| 853 | for (unsigned i = 1; i != NumComp; ++i) |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 854 | dups.push_back(&Edit.create(MRI, LIS, VRM)); |
Eric Christopher | 0f43811 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 855 | rewriteComponents(dups, ConEQ); |
Jakob Stoklund Olesen | 3a0e071 | 2010-10-26 22:36:09 +0000 | [diff] [blame] | 856 | ConEQ.Distribute(&dups[0]); |
Jakob Stoklund Olesen | 3a0e071 | 2010-10-26 22:36:09 +0000 | [diff] [blame] | 857 | } |
| 858 | |
Jakob Stoklund Olesen | 08e93b1 | 2010-08-10 17:07:22 +0000 | [diff] [blame] | 859 | // Calculate spill weight and allocation hints for new intervals. |
Jakob Stoklund Olesen | 0eeca44 | 2011-02-19 00:42:33 +0000 | [diff] [blame] | 860 | VirtRegAuxInfo vrai(VRM.getMachineFunction(), LIS, SA.Loops); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 861 | for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I){ |
Jakob Stoklund Olesen | a17768f | 2010-10-14 23:49:52 +0000 | [diff] [blame] | 862 | LiveInterval &li = **I; |
Jakob Stoklund Olesen | 9db3ea4 | 2010-08-10 18:37:40 +0000 | [diff] [blame] | 863 | vrai.CalculateRegClass(li.reg); |
Jakob Stoklund Olesen | 08e93b1 | 2010-08-10 17:07:22 +0000 | [diff] [blame] | 864 | vrai.CalculateWeightAndHint(li); |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 865 | DEBUG(dbgs() << " new interval " << MRI.getRegClass(li.reg)->getName() |
Jakob Stoklund Olesen | e1f543f | 2010-08-12 18:50:55 +0000 | [diff] [blame] | 866 | << ":" << li << '\n'); |
Jakob Stoklund Olesen | 08e93b1 | 2010-08-10 17:07:22 +0000 | [diff] [blame] | 867 | } |
Jakob Stoklund Olesen | f017900 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 868 | } |
| 869 | |
| 870 | |
Jakob Stoklund Olesen | 8ae0263 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 871 | //===----------------------------------------------------------------------===// |
Jakob Stoklund Olesen | f1b05f2 | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 872 | // Single Block Splitting |
| 873 | //===----------------------------------------------------------------------===// |
| 874 | |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 875 | /// getMultiUseBlocks - if CurLI has more than one use in a basic block, it |
| 876 | /// may be an advantage to split CurLI for the duration of the block. |
Jakob Stoklund Olesen | 2bfb324 | 2010-10-22 22:48:56 +0000 | [diff] [blame] | 877 | bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 878 | // If CurLI is local to one block, there is no point to splitting it. |
Jakob Stoklund Olesen | 9b05777 | 2011-02-09 23:30:25 +0000 | [diff] [blame] | 879 | if (LiveBlocks.size() <= 1) |
Jakob Stoklund Olesen | 2bfb324 | 2010-10-22 22:48:56 +0000 | [diff] [blame] | 880 | return false; |
| 881 | // Add blocks with multiple uses. |
Jakob Stoklund Olesen | 9b05777 | 2011-02-09 23:30:25 +0000 | [diff] [blame] | 882 | for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) { |
| 883 | const BlockInfo &BI = LiveBlocks[i]; |
| 884 | if (!BI.Uses) |
Jakob Stoklund Olesen | 2bfb324 | 2010-10-22 22:48:56 +0000 | [diff] [blame] | 885 | continue; |
Jakob Stoklund Olesen | 9b05777 | 2011-02-09 23:30:25 +0000 | [diff] [blame] | 886 | unsigned Instrs = UsingBlocks.lookup(BI.MBB); |
| 887 | if (Instrs <= 1) |
| 888 | continue; |
| 889 | if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough) |
| 890 | continue; |
| 891 | Blocks.insert(BI.MBB); |
| 892 | } |
Jakob Stoklund Olesen | 2bfb324 | 2010-10-22 22:48:56 +0000 | [diff] [blame] | 893 | return !Blocks.empty(); |
| 894 | } |
| 895 | |
Jakob Stoklund Olesen | 0786284 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 896 | /// splitSingleBlocks - Split CurLI into a separate live interval inside each |
Jakob Stoklund Olesen | 57d0f2d | 2010-10-05 22:19:33 +0000 | [diff] [blame] | 897 | /// basic block in Blocks. |
| 898 | void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { |
Jakob Stoklund Olesen | e1f543f | 2010-08-12 18:50:55 +0000 | [diff] [blame] | 899 | DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); |
Jakob Stoklund Olesen | f1b05f2 | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 900 | |
Jakob Stoklund Olesen | 0eeca44 | 2011-02-19 00:42:33 +0000 | [diff] [blame] | 901 | for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) { |
| 902 | const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i]; |
Jakob Stoklund Olesen | 9b05777 | 2011-02-09 23:30:25 +0000 | [diff] [blame] | 903 | if (!BI.Uses || !Blocks.count(BI.MBB)) |
| 904 | continue; |
Jakob Stoklund Olesen | f1b05f2 | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 905 | |
| 906 | openIntv(); |
Jakob Stoklund Olesen | 9b05777 | 2011-02-09 23:30:25 +0000 | [diff] [blame] | 907 | SlotIndex SegStart = enterIntvBefore(BI.FirstUse); |
Jakob Stoklund Olesen | c70f687 | 2011-02-23 18:26:31 +0000 | [diff] [blame] | 908 | if (!BI.LiveOut || BI.LastUse < BI.LastSplitPoint) { |
Jakob Stoklund Olesen | 9b05777 | 2011-02-09 23:30:25 +0000 | [diff] [blame] | 909 | useIntv(SegStart, leaveIntvAfter(BI.LastUse)); |
| 910 | } else { |
Jakob Stoklund Olesen | c70f687 | 2011-02-23 18:26:31 +0000 | [diff] [blame] | 911 | // The last use is after the last valid split point. |
Jakob Stoklund Olesen | 9b05777 | 2011-02-09 23:30:25 +0000 | [diff] [blame] | 912 | SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint); |
| 913 | useIntv(SegStart, SegStop); |
| 914 | overlapIntv(SegStop, BI.LastUse); |
| 915 | } |
Jakob Stoklund Olesen | f1b05f2 | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 916 | closeIntv(); |
| 917 | } |
Jakob Stoklund Olesen | 7466927 | 2010-10-08 23:42:21 +0000 | [diff] [blame] | 918 | finish(); |
Jakob Stoklund Olesen | f1b05f2 | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 919 | } |