Jakob Stoklund Olesen | 36d12c6 | 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 | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 15 | #include "SplitKit.h" |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 16 | #include "llvm/ADT/Statistic.h" |
Jakob Stoklund Olesen | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 17 | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
Pete Cooper | 3ca96f9 | 2012-04-02 22:44:18 +0000 | [diff] [blame] | 18 | #include "llvm/CodeGen/LiveRangeEdit.h" |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 19 | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" |
Jakob Stoklund Olesen | e172a8b | 2010-10-28 20:34:50 +0000 | [diff] [blame] | 20 | #include "llvm/CodeGen/MachineDominators.h" |
Jakob Stoklund Olesen | c698417 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 21 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
Jakob Stoklund Olesen | a98af39 | 2011-09-14 16:45:39 +0000 | [diff] [blame] | 22 | #include "llvm/CodeGen/MachineLoopInfo.h" |
Jakob Stoklund Olesen | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 23 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
Jakob Stoklund Olesen | 26c9d70 | 2012-11-28 19:13:06 +0000 | [diff] [blame] | 24 | #include "llvm/CodeGen/VirtRegMap.h" |
Jakob Stoklund Olesen | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 25 | #include "llvm/Support/Debug.h" |
Matthias Braun | f0b68d3 | 2017-03-17 00:41:39 +0000 | [diff] [blame] | 26 | #include "llvm/Support/MathExtras.h" |
Jakob Stoklund Olesen | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 27 | #include "llvm/Support/raw_ostream.h" |
Jakob Stoklund Olesen | ed4075c | 2010-07-20 21:46:58 +0000 | [diff] [blame] | 28 | #include "llvm/Target/TargetInstrInfo.h" |
| 29 | #include "llvm/Target/TargetMachine.h" |
Jakob Stoklund Olesen | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 30 | |
| 31 | using namespace llvm; |
| 32 | |
Chandler Carruth | 1b9dde0 | 2014-04-22 02:02:50 +0000 | [diff] [blame] | 33 | #define DEBUG_TYPE "regalloc" |
| 34 | |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 35 | STATISTIC(NumFinished, "Number of splits finished"); |
| 36 | STATISTIC(NumSimple, "Number of splits that were simple"); |
Jakob Stoklund Olesen | c5a8c08 | 2011-05-05 17:22:53 +0000 | [diff] [blame] | 37 | STATISTIC(NumCopies, "Number of copies inserted for splitting"); |
| 38 | STATISTIC(NumRemats, "Number of rematerialized defs for splitting"); |
Jakob Stoklund Olesen | 50215af | 2011-05-10 17:37:41 +0000 | [diff] [blame] | 39 | STATISTIC(NumRepairs, "Number of invalid live ranges repaired"); |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 40 | |
Jakob Stoklund Olesen | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 41 | //===----------------------------------------------------------------------===// |
Wei Mi | 35ee933 | 2016-05-11 22:28:29 +0000 | [diff] [blame] | 42 | // Last Insert Point Analysis |
| 43 | //===----------------------------------------------------------------------===// |
| 44 | |
| 45 | InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis, |
| 46 | unsigned BBNum) |
Wei Mi | f3c8f53 | 2016-05-23 19:39:19 +0000 | [diff] [blame] | 47 | : LIS(lis), LastInsertPoint(BBNum) {} |
Wei Mi | 35ee933 | 2016-05-11 22:28:29 +0000 | [diff] [blame] | 48 | |
| 49 | SlotIndex |
Wei Mi | f3c8f53 | 2016-05-23 19:39:19 +0000 | [diff] [blame] | 50 | InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI, |
| 51 | const MachineBasicBlock &MBB) { |
Wei Mi | 35ee933 | 2016-05-11 22:28:29 +0000 | [diff] [blame] | 52 | unsigned Num = MBB.getNumber(); |
| 53 | std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num]; |
| 54 | SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB); |
| 55 | |
| 56 | SmallVector<const MachineBasicBlock *, 1> EHPadSucessors; |
| 57 | for (const MachineBasicBlock *SMBB : MBB.successors()) |
| 58 | if (SMBB->isEHPad()) |
| 59 | EHPadSucessors.push_back(SMBB); |
| 60 | |
| 61 | // Compute insert points on the first call. The pair is independent of the |
| 62 | // current live interval. |
| 63 | if (!LIP.first.isValid()) { |
| 64 | MachineBasicBlock::const_iterator FirstTerm = MBB.getFirstTerminator(); |
| 65 | if (FirstTerm == MBB.end()) |
| 66 | LIP.first = MBBEnd; |
| 67 | else |
| 68 | LIP.first = LIS.getInstructionIndex(*FirstTerm); |
| 69 | |
| 70 | // If there is a landing pad successor, also find the call instruction. |
| 71 | if (EHPadSucessors.empty()) |
| 72 | return LIP.first; |
| 73 | // There may not be a call instruction (?) in which case we ignore LPad. |
| 74 | LIP.second = LIP.first; |
| 75 | for (MachineBasicBlock::const_iterator I = MBB.end(), E = MBB.begin(); |
| 76 | I != E;) { |
| 77 | --I; |
| 78 | if (I->isCall()) { |
| 79 | LIP.second = LIS.getInstructionIndex(*I); |
| 80 | break; |
| 81 | } |
| 82 | } |
| 83 | } |
| 84 | |
| 85 | // If CurLI is live into a landing pad successor, move the last insert point |
| 86 | // back to the call that may throw. |
| 87 | if (!LIP.second) |
| 88 | return LIP.first; |
| 89 | |
Wei Mi | 35ee933 | 2016-05-11 22:28:29 +0000 | [diff] [blame] | 90 | if (none_of(EHPadSucessors, [&](const MachineBasicBlock *EHPad) { |
Wei Mi | f3c8f53 | 2016-05-23 19:39:19 +0000 | [diff] [blame] | 91 | return LIS.isLiveInToMBB(CurLI, EHPad); |
Wei Mi | 35ee933 | 2016-05-11 22:28:29 +0000 | [diff] [blame] | 92 | })) |
| 93 | return LIP.first; |
| 94 | |
| 95 | // Find the value leaving MBB. |
Wei Mi | f3c8f53 | 2016-05-23 19:39:19 +0000 | [diff] [blame] | 96 | const VNInfo *VNI = CurLI.getVNInfoBefore(MBBEnd); |
Wei Mi | 35ee933 | 2016-05-11 22:28:29 +0000 | [diff] [blame] | 97 | if (!VNI) |
| 98 | return LIP.first; |
| 99 | |
| 100 | // If the value leaving MBB was defined after the call in MBB, it can't |
| 101 | // really be live-in to the landing pad. This can happen if the landing pad |
| 102 | // has a PHI, and this register is undef on the exceptional edge. |
| 103 | // <rdar://problem/10664933> |
| 104 | if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd) |
| 105 | return LIP.first; |
| 106 | |
| 107 | // Value is properly live-in to the landing pad. |
| 108 | // Only allow inserts before the call. |
| 109 | return LIP.second; |
| 110 | } |
| 111 | |
| 112 | MachineBasicBlock::iterator |
Wei Mi | f3c8f53 | 2016-05-23 19:39:19 +0000 | [diff] [blame] | 113 | InsertPointAnalysis::getLastInsertPointIter(const LiveInterval &CurLI, |
| 114 | MachineBasicBlock &MBB) { |
| 115 | SlotIndex LIP = getLastInsertPoint(CurLI, MBB); |
Wei Mi | 35ee933 | 2016-05-11 22:28:29 +0000 | [diff] [blame] | 116 | if (LIP == LIS.getMBBEndIdx(&MBB)) |
| 117 | return MBB.end(); |
| 118 | return LIS.getInstructionFromIndex(LIP); |
| 119 | } |
| 120 | |
| 121 | //===----------------------------------------------------------------------===// |
Jakob Stoklund Olesen | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 122 | // Split Analysis |
| 123 | //===----------------------------------------------------------------------===// |
| 124 | |
Eric Christopher | d913448 | 2014-08-04 21:25:23 +0000 | [diff] [blame] | 125 | SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, |
Jakob Stoklund Olesen | 0fef9dd | 2010-07-20 23:50:15 +0000 | [diff] [blame] | 126 | const MachineLoopInfo &mli) |
Eric Christopher | d913448 | 2014-08-04 21:25:23 +0000 | [diff] [blame] | 127 | : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli), |
Eric Christopher | fc6de42 | 2014-08-05 02:39:49 +0000 | [diff] [blame] | 128 | TII(*MF.getSubtarget().getInstrInfo()), CurLI(nullptr), |
Wei Mi | 35ee933 | 2016-05-11 22:28:29 +0000 | [diff] [blame] | 129 | IPA(lis, MF.getNumBlockIDs()) {} |
Jakob Stoklund Olesen | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 130 | |
| 131 | void SplitAnalysis::clear() { |
Jakob Stoklund Olesen | 267f6c1 | 2011-01-18 21:13:27 +0000 | [diff] [blame] | 132 | UseSlots.clear(); |
Jakob Stoklund Olesen | bf91c4e | 2011-04-06 03:57:00 +0000 | [diff] [blame] | 133 | UseBlocks.clear(); |
| 134 | ThroughBlocks.clear(); |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 135 | CurLI = nullptr; |
Jakob Stoklund Olesen | eaa6ed1 | 2011-05-03 20:42:13 +0000 | [diff] [blame] | 136 | DidRepairRange = false; |
Jakob Stoklund Olesen | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 137 | } |
| 138 | |
Jakob Stoklund Olesen | b308902 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 139 | /// analyzeUses - Count instructions, basic blocks, and loops using CurLI. |
Jakob Stoklund Olesen | ff09550 | 2010-07-20 16:12:37 +0000 | [diff] [blame] | 140 | void SplitAnalysis::analyzeUses() { |
Jakob Stoklund Olesen | fe6e07f | 2011-04-05 15:18:18 +0000 | [diff] [blame] | 141 | assert(UseSlots.empty() && "Call clear first"); |
| 142 | |
| 143 | // First get all the defs from the interval values. This provides the correct |
| 144 | // slots for early clobbers. |
Matthias Braun | 9676195 | 2014-12-10 23:07:54 +0000 | [diff] [blame] | 145 | for (const VNInfo *VNI : CurLI->valnos) |
| 146 | if (!VNI->isPHIDef() && !VNI->isUnused()) |
| 147 | UseSlots.push_back(VNI->def); |
Jakob Stoklund Olesen | fe6e07f | 2011-04-05 15:18:18 +0000 | [diff] [blame] | 148 | |
| 149 | // Get use slots form the use-def chain. |
Jakob Stoklund Olesen | b308902 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 150 | const MachineRegisterInfo &MRI = MF.getRegInfo(); |
Owen Anderson | b36376e | 2014-03-17 19:36:09 +0000 | [diff] [blame] | 151 | for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg)) |
| 152 | if (!MO.isUndef()) |
Duncan P. N. Exon Smith | 3ac9cc6 | 2016-02-27 06:40:41 +0000 | [diff] [blame] | 153 | UseSlots.push_back(LIS.getInstructionIndex(*MO.getParent()).getRegSlot()); |
Jakob Stoklund Olesen | fe6e07f | 2011-04-05 15:18:18 +0000 | [diff] [blame] | 154 | |
Jakob Stoklund Olesen | 267f6c1 | 2011-01-18 21:13:27 +0000 | [diff] [blame] | 155 | array_pod_sort(UseSlots.begin(), UseSlots.end()); |
Jakob Stoklund Olesen | 27e0a4a | 2011-03-05 18:33:49 +0000 | [diff] [blame] | 156 | |
Jakob Stoklund Olesen | fe6e07f | 2011-04-05 15:18:18 +0000 | [diff] [blame] | 157 | // Remove duplicates, keeping the smaller slot for each instruction. |
| 158 | // That is what we want for early clobbers. |
| 159 | UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(), |
| 160 | SlotIndex::isSameInstr), |
| 161 | UseSlots.end()); |
| 162 | |
Jakob Stoklund Olesen | 27e0a4a | 2011-03-05 18:33:49 +0000 | [diff] [blame] | 163 | // Compute per-live block info. |
| 164 | if (!calcLiveBlockInfo()) { |
| 165 | // FIXME: calcLiveBlockInfo found inconsistencies in the live range. |
Rafael Espindola | 676c405 | 2011-06-26 22:34:10 +0000 | [diff] [blame] | 166 | // I am looking at you, RegisterCoalescer! |
Jakob Stoklund Olesen | eaa6ed1 | 2011-05-03 20:42:13 +0000 | [diff] [blame] | 167 | DidRepairRange = true; |
Jakob Stoklund Olesen | 50215af | 2011-05-10 17:37:41 +0000 | [diff] [blame] | 168 | ++NumRepairs; |
Jakob Stoklund Olesen | 27e0a4a | 2011-03-05 18:33:49 +0000 | [diff] [blame] | 169 | DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n"); |
| 170 | const_cast<LiveIntervals&>(LIS) |
| 171 | .shrinkToUses(const_cast<LiveInterval*>(CurLI)); |
Jakob Stoklund Olesen | bf91c4e | 2011-04-06 03:57:00 +0000 | [diff] [blame] | 172 | UseBlocks.clear(); |
| 173 | ThroughBlocks.clear(); |
Jakob Stoklund Olesen | 27e0a4a | 2011-03-05 18:33:49 +0000 | [diff] [blame] | 174 | bool fixed = calcLiveBlockInfo(); |
| 175 | (void)fixed; |
| 176 | assert(fixed && "Couldn't fix broken live interval"); |
| 177 | } |
| 178 | |
Jakob Stoklund Olesen | bd6b86e | 2011-03-27 22:49:23 +0000 | [diff] [blame] | 179 | DEBUG(dbgs() << "Analyze counted " |
Jakob Stoklund Olesen | bf91c4e | 2011-04-06 03:57:00 +0000 | [diff] [blame] | 180 | << UseSlots.size() << " instrs in " |
| 181 | << UseBlocks.size() << " blocks, through " |
Jakob Stoklund Olesen | ed47ed4 | 2011-04-09 02:59:09 +0000 | [diff] [blame] | 182 | << NumThroughBlocks << " blocks.\n"); |
Jakob Stoklund Olesen | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 183 | } |
| 184 | |
Jakob Stoklund Olesen | b1b76ad | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 185 | /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks |
| 186 | /// where CurLI is live. |
Jakob Stoklund Olesen | 27e0a4a | 2011-03-05 18:33:49 +0000 | [diff] [blame] | 187 | bool SplitAnalysis::calcLiveBlockInfo() { |
Jakob Stoklund Olesen | ed47ed4 | 2011-04-09 02:59:09 +0000 | [diff] [blame] | 188 | ThroughBlocks.resize(MF.getNumBlockIDs()); |
Jakob Stoklund Olesen | ec43d5d | 2011-05-30 01:33:26 +0000 | [diff] [blame] | 189 | NumThroughBlocks = NumGapBlocks = 0; |
Jakob Stoklund Olesen | b1b76ad | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 190 | if (CurLI->empty()) |
Jakob Stoklund Olesen | 27e0a4a | 2011-03-05 18:33:49 +0000 | [diff] [blame] | 191 | return true; |
Jakob Stoklund Olesen | b1b76ad | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 192 | |
| 193 | LiveInterval::const_iterator LVI = CurLI->begin(); |
| 194 | LiveInterval::const_iterator LVE = CurLI->end(); |
| 195 | |
| 196 | SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; |
| 197 | UseI = UseSlots.begin(); |
| 198 | UseE = UseSlots.end(); |
| 199 | |
| 200 | // Loop over basic blocks where CurLI is live. |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 201 | MachineFunction::iterator MFI = |
| 202 | LIS.getMBBFromIndex(LVI->start)->getIterator(); |
Jakob Stoklund Olesen | b1b76ad | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 203 | for (;;) { |
| 204 | BlockInfo BI; |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 205 | BI.MBB = &*MFI; |
Jakob Stoklund Olesen | 8933907 | 2011-04-04 15:32:15 +0000 | [diff] [blame] | 206 | SlotIndex Start, Stop; |
Benjamin Kramer | d6f1f84 | 2014-03-02 13:30:33 +0000 | [diff] [blame] | 207 | std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); |
Jakob Stoklund Olesen | b1b76ad | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 208 | |
Jakob Stoklund Olesen | ec43d5d | 2011-05-30 01:33:26 +0000 | [diff] [blame] | 209 | // If the block contains no uses, the range must be live through. At one |
Rafael Espindola | 676c405 | 2011-06-26 22:34:10 +0000 | [diff] [blame] | 210 | // point, RegisterCoalescer could create dangling ranges that ended |
Jakob Stoklund Olesen | ec43d5d | 2011-05-30 01:33:26 +0000 | [diff] [blame] | 211 | // mid-block. |
| 212 | if (UseI == UseE || *UseI >= Stop) { |
| 213 | ++NumThroughBlocks; |
| 214 | ThroughBlocks.set(BI.MBB->getNumber()); |
| 215 | // The range shouldn't end mid-block if there are no uses. This shouldn't |
| 216 | // happen. |
| 217 | if (LVI->end < Stop) |
| 218 | return false; |
| 219 | } else { |
| 220 | // This block has uses. Find the first and last uses in the block. |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 221 | BI.FirstInstr = *UseI; |
| 222 | assert(BI.FirstInstr >= Start); |
Jakob Stoklund Olesen | b1b76ad | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 223 | do ++UseI; |
Jakob Stoklund Olesen | 8933907 | 2011-04-04 15:32:15 +0000 | [diff] [blame] | 224 | while (UseI != UseE && *UseI < Stop); |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 225 | BI.LastInstr = UseI[-1]; |
| 226 | assert(BI.LastInstr < Stop); |
Jakob Stoklund Olesen | b1b76ad | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 227 | |
Jakob Stoklund Olesen | ec43d5d | 2011-05-30 01:33:26 +0000 | [diff] [blame] | 228 | // LVI is the first live segment overlapping MBB. |
| 229 | BI.LiveIn = LVI->start <= Start; |
Jakob Stoklund Olesen | ca6a4d8 | 2011-05-29 21:24:39 +0000 | [diff] [blame] | 230 | |
Jakob Stoklund Olesen | ae8027c | 2011-08-02 22:37:22 +0000 | [diff] [blame] | 231 | // When not live in, the first use should be a def. |
| 232 | if (!BI.LiveIn) { |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 233 | assert(LVI->start == LVI->valno->def && "Dangling Segment start"); |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 234 | assert(LVI->start == BI.FirstInstr && "First instr should be a def"); |
| 235 | BI.FirstDef = BI.FirstInstr; |
Jakob Stoklund Olesen | ae8027c | 2011-08-02 22:37:22 +0000 | [diff] [blame] | 236 | } |
| 237 | |
Jakob Stoklund Olesen | ec43d5d | 2011-05-30 01:33:26 +0000 | [diff] [blame] | 238 | // Look for gaps in the live range. |
| 239 | BI.LiveOut = true; |
| 240 | while (LVI->end < Stop) { |
| 241 | SlotIndex LastStop = LVI->end; |
| 242 | if (++LVI == LVE || LVI->start >= Stop) { |
| 243 | BI.LiveOut = false; |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 244 | BI.LastInstr = LastStop; |
Jakob Stoklund Olesen | ec43d5d | 2011-05-30 01:33:26 +0000 | [diff] [blame] | 245 | break; |
| 246 | } |
Jakob Stoklund Olesen | ae8027c | 2011-08-02 22:37:22 +0000 | [diff] [blame] | 247 | |
Jakob Stoklund Olesen | ec43d5d | 2011-05-30 01:33:26 +0000 | [diff] [blame] | 248 | if (LastStop < LVI->start) { |
| 249 | // There is a gap in the live range. Create duplicate entries for the |
| 250 | // live-in snippet and the live-out snippet. |
| 251 | ++NumGapBlocks; |
| 252 | |
| 253 | // Push the Live-in part. |
Jakob Stoklund Olesen | ec43d5d | 2011-05-30 01:33:26 +0000 | [diff] [blame] | 254 | BI.LiveOut = false; |
| 255 | UseBlocks.push_back(BI); |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 256 | UseBlocks.back().LastInstr = LastStop; |
Jakob Stoklund Olesen | ec43d5d | 2011-05-30 01:33:26 +0000 | [diff] [blame] | 257 | |
| 258 | // Set up BI for the live-out part. |
| 259 | BI.LiveIn = false; |
| 260 | BI.LiveOut = true; |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 261 | BI.FirstInstr = BI.FirstDef = LVI->start; |
Jakob Stoklund Olesen | ec43d5d | 2011-05-30 01:33:26 +0000 | [diff] [blame] | 262 | } |
Jakob Stoklund Olesen | ae8027c | 2011-08-02 22:37:22 +0000 | [diff] [blame] | 263 | |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 264 | // A Segment that starts in the middle of the block must be a def. |
| 265 | assert(LVI->start == LVI->valno->def && "Dangling Segment start"); |
Jakob Stoklund Olesen | ae8027c | 2011-08-02 22:37:22 +0000 | [diff] [blame] | 266 | if (!BI.FirstDef) |
| 267 | BI.FirstDef = LVI->start; |
Jakob Stoklund Olesen | ec43d5d | 2011-05-30 01:33:26 +0000 | [diff] [blame] | 268 | } |
| 269 | |
Jakob Stoklund Olesen | ca6a4d8 | 2011-05-29 21:24:39 +0000 | [diff] [blame] | 270 | UseBlocks.push_back(BI); |
Jakob Stoklund Olesen | ca6a4d8 | 2011-05-29 21:24:39 +0000 | [diff] [blame] | 271 | |
Jakob Stoklund Olesen | ec43d5d | 2011-05-30 01:33:26 +0000 | [diff] [blame] | 272 | // LVI is now at LVE or LVI->end >= Stop. |
| 273 | if (LVI == LVE) |
| 274 | break; |
| 275 | } |
Jakob Stoklund Olesen | ca6a4d8 | 2011-05-29 21:24:39 +0000 | [diff] [blame] | 276 | |
Jakob Stoklund Olesen | b1b76ad | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 277 | // Live segment ends exactly at Stop. Move to the next segment. |
Jakob Stoklund Olesen | 8933907 | 2011-04-04 15:32:15 +0000 | [diff] [blame] | 278 | if (LVI->end == Stop && ++LVI == LVE) |
Jakob Stoklund Olesen | b1b76ad | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 279 | break; |
| 280 | |
| 281 | // Pick the next basic block. |
Jakob Stoklund Olesen | 8933907 | 2011-04-04 15:32:15 +0000 | [diff] [blame] | 282 | if (LVI->start < Stop) |
Jakob Stoklund Olesen | b1b76ad | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 283 | ++MFI; |
| 284 | else |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 285 | MFI = LIS.getMBBFromIndex(LVI->start)->getIterator(); |
Jakob Stoklund Olesen | b1b76ad | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 286 | } |
Jakob Stoklund Olesen | 5cc91b2 | 2011-05-28 02:32:57 +0000 | [diff] [blame] | 287 | |
| 288 | assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count"); |
Jakob Stoklund Olesen | 27e0a4a | 2011-03-05 18:33:49 +0000 | [diff] [blame] | 289 | return true; |
Jakob Stoklund Olesen | b1b76ad | 2011-02-09 22:50:26 +0000 | [diff] [blame] | 290 | } |
| 291 | |
Jakob Stoklund Olesen | eef2327 | 2011-04-26 22:33:12 +0000 | [diff] [blame] | 292 | unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { |
| 293 | if (cli->empty()) |
| 294 | return 0; |
| 295 | LiveInterval *li = const_cast<LiveInterval*>(cli); |
| 296 | LiveInterval::iterator LVI = li->begin(); |
| 297 | LiveInterval::iterator LVE = li->end(); |
| 298 | unsigned Count = 0; |
| 299 | |
| 300 | // Loop over basic blocks where li is live. |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 301 | MachineFunction::const_iterator MFI = |
| 302 | LIS.getMBBFromIndex(LVI->start)->getIterator(); |
| 303 | SlotIndex Stop = LIS.getMBBEndIdx(&*MFI); |
Jakob Stoklund Olesen | eef2327 | 2011-04-26 22:33:12 +0000 | [diff] [blame] | 304 | for (;;) { |
| 305 | ++Count; |
| 306 | LVI = li->advanceTo(LVI, Stop); |
| 307 | if (LVI == LVE) |
| 308 | return Count; |
| 309 | do { |
| 310 | ++MFI; |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 311 | Stop = LIS.getMBBEndIdx(&*MFI); |
Jakob Stoklund Olesen | eef2327 | 2011-04-26 22:33:12 +0000 | [diff] [blame] | 312 | } while (Stop <= LVI->start); |
| 313 | } |
| 314 | } |
| 315 | |
Jakob Stoklund Olesen | 60a26a6 | 2011-02-21 23:09:46 +0000 | [diff] [blame] | 316 | bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { |
| 317 | unsigned OrigReg = VRM.getOriginal(CurLI->reg); |
| 318 | const LiveInterval &Orig = LIS.getInterval(OrigReg); |
| 319 | assert(!Orig.empty() && "Splitting empty interval?"); |
| 320 | LiveInterval::const_iterator I = Orig.find(Idx); |
| 321 | |
| 322 | // Range containing Idx should begin at Idx. |
| 323 | if (I != Orig.end() && I->start <= Idx) |
| 324 | return I->start == Idx; |
| 325 | |
| 326 | // Range does not contain Idx, previous must end at Idx. |
| 327 | return I != Orig.begin() && (--I)->end == Idx; |
| 328 | } |
| 329 | |
Jakob Stoklund Olesen | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 330 | void SplitAnalysis::analyze(const LiveInterval *li) { |
| 331 | clear(); |
Jakob Stoklund Olesen | b308902 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 332 | CurLI = li; |
Jakob Stoklund Olesen | ff09550 | 2010-07-20 16:12:37 +0000 | [diff] [blame] | 333 | analyzeUses(); |
Jakob Stoklund Olesen | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 334 | } |
| 335 | |
Jakob Stoklund Olesen | 28e769c | 2010-12-15 17:49:52 +0000 | [diff] [blame] | 336 | |
Jakob Stoklund Olesen | c698417 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 337 | //===----------------------------------------------------------------------===// |
| 338 | // Split Editor |
| 339 | //===----------------------------------------------------------------------===// |
| 340 | |
| 341 | /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. |
Wei Mi | c022370 | 2016-07-08 21:08:09 +0000 | [diff] [blame] | 342 | SplitEditor::SplitEditor(SplitAnalysis &sa, AliasAnalysis &aa, |
| 343 | LiveIntervals &lis, VirtRegMap &vrm, |
Benjamin Kramer | e2a1d89 | 2013-06-17 19:00:36 +0000 | [diff] [blame] | 344 | MachineDominatorTree &mdt, |
| 345 | MachineBlockFrequencyInfo &mbfi) |
Wei Mi | c022370 | 2016-07-08 21:08:09 +0000 | [diff] [blame] | 346 | : SA(sa), AA(aa), LIS(lis), VRM(vrm), |
| 347 | MRI(vrm.getMachineFunction().getRegInfo()), MDT(mdt), |
| 348 | TII(*vrm.getMachineFunction().getSubtarget().getInstrInfo()), |
Eric Christopher | 6062180 | 2014-10-14 07:22:00 +0000 | [diff] [blame] | 349 | TRI(*vrm.getMachineFunction().getSubtarget().getRegisterInfo()), |
Eric Christopher | d913448 | 2014-08-04 21:25:23 +0000 | [diff] [blame] | 350 | MBFI(mbfi), Edit(nullptr), OpenIdx(0), SpillMode(SM_Partition), |
| 351 | RegAssign(Allocator) {} |
Jakob Stoklund Olesen | c960198 | 2011-03-03 01:29:13 +0000 | [diff] [blame] | 352 | |
Jakob Stoklund Olesen | eecb2fb | 2011-09-12 16:49:21 +0000 | [diff] [blame] | 353 | void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { |
| 354 | Edit = &LRE; |
| 355 | SpillMode = SM; |
Jakob Stoklund Olesen | c960198 | 2011-03-03 01:29:13 +0000 | [diff] [blame] | 356 | OpenIdx = 0; |
| 357 | RegAssign.clear(); |
| 358 | Values.clear(); |
Jakob Stoklund Olesen | 054984d | 2011-09-13 16:47:53 +0000 | [diff] [blame] | 359 | |
| 360 | // Reset the LiveRangeCalc instances needed for this spill mode. |
Jakob Stoklund Olesen | 5ef0e0b | 2012-06-04 18:21:16 +0000 | [diff] [blame] | 361 | LRCalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, |
| 362 | &LIS.getVNInfoAllocator()); |
Jakob Stoklund Olesen | 054984d | 2011-09-13 16:47:53 +0000 | [diff] [blame] | 363 | if (SpillMode) |
Jakob Stoklund Olesen | 5ef0e0b | 2012-06-04 18:21:16 +0000 | [diff] [blame] | 364 | LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, |
| 365 | &LIS.getVNInfoAllocator()); |
Jakob Stoklund Olesen | c960198 | 2011-03-03 01:29:13 +0000 | [diff] [blame] | 366 | |
Jakob Stoklund Olesen | 6ee7d9aa | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 367 | // We don't need an AliasAnalysis since we will only be performing |
| 368 | // cheap-as-a-copy remats anyway. |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 369 | Edit->anyRematerializable(nullptr); |
Jakob Stoklund Olesen | c698417 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 370 | } |
| 371 | |
Manman Ren | 19f49ac | 2012-09-11 22:23:19 +0000 | [diff] [blame] | 372 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
Yaron Keren | eb2a254 | 2016-01-29 20:50:44 +0000 | [diff] [blame] | 373 | LLVM_DUMP_METHOD void SplitEditor::dump() const { |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 374 | if (RegAssign.empty()) { |
| 375 | dbgs() << " empty\n"; |
| 376 | return; |
| 377 | } |
| 378 | |
| 379 | for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) |
| 380 | dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); |
| 381 | dbgs() << '\n'; |
Jakob Stoklund Olesen | 6f8bd42 | 2010-09-21 22:32:21 +0000 | [diff] [blame] | 382 | } |
Manman Ren | 742534c | 2012-09-06 19:06:06 +0000 | [diff] [blame] | 383 | #endif |
Jakob Stoklund Olesen | 6f8bd42 | 2010-09-21 22:32:21 +0000 | [diff] [blame] | 384 | |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 385 | LiveInterval::SubRange &SplitEditor::getSubRangeForMask(LaneBitmask LM, |
| 386 | LiveInterval &LI) { |
| 387 | for (LiveInterval::SubRange &S : LI.subranges()) |
| 388 | if (S.LaneMask == LM) |
| 389 | return S; |
| 390 | llvm_unreachable("SubRange for this mask not found"); |
George Burgess IV | b42e0e7 | 2016-08-25 02:15:54 +0000 | [diff] [blame] | 391 | } |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 392 | |
| 393 | void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) { |
| 394 | if (!LI.hasSubRanges()) { |
| 395 | LI.createDeadDef(VNI); |
| 396 | return; |
| 397 | } |
| 398 | |
| 399 | SlotIndex Def = VNI->def; |
| 400 | if (Original) { |
| 401 | // If we are transferring a def from the original interval, make sure |
| 402 | // to only update the subranges for which the original subranges had |
| 403 | // a def at this location. |
| 404 | for (LiveInterval::SubRange &S : LI.subranges()) { |
| 405 | auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent()); |
| 406 | VNInfo *PV = PS.getVNInfoAt(Def); |
| 407 | if (PV != nullptr && PV->def == Def) |
| 408 | S.createDeadDef(Def, LIS.getVNInfoAllocator()); |
| 409 | } |
| 410 | } else { |
| 411 | // This is a new def: either from rematerialization, or from an inserted |
| 412 | // copy. Since rematerialization can regenerate a definition of a sub- |
| 413 | // register, we need to check which subranges need to be updated. |
| 414 | const MachineInstr *DefMI = LIS.getInstructionFromIndex(Def); |
| 415 | assert(DefMI != nullptr); |
Krzysztof Parzyszek | 91b5cf8 | 2016-12-15 14:36:06 +0000 | [diff] [blame] | 416 | LaneBitmask LM; |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 417 | for (const MachineOperand &DefOp : DefMI->defs()) { |
| 418 | unsigned R = DefOp.getReg(); |
| 419 | if (R != LI.reg) |
| 420 | continue; |
| 421 | if (unsigned SR = DefOp.getSubReg()) |
| 422 | LM |= TRI.getSubRegIndexLaneMask(SR); |
| 423 | else { |
| 424 | LM = MRI.getMaxLaneMaskForVReg(R); |
| 425 | break; |
| 426 | } |
| 427 | } |
| 428 | for (LiveInterval::SubRange &S : LI.subranges()) |
Krzysztof Parzyszek | ea9f8ce | 2016-12-16 19:11:56 +0000 | [diff] [blame] | 429 | if ((S.LaneMask & LM).any()) |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 430 | S.createDeadDef(Def, LIS.getVNInfoAllocator()); |
| 431 | } |
| 432 | } |
| 433 | |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 434 | VNInfo *SplitEditor::defValue(unsigned RegIdx, |
| 435 | const VNInfo *ParentVNI, |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 436 | SlotIndex Idx, |
| 437 | bool Original) { |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 438 | assert(ParentVNI && "Mapping NULL value"); |
| 439 | assert(Idx.isValid() && "Invalid SlotIndex"); |
Jakob Stoklund Olesen | 815196c | 2011-03-02 23:31:50 +0000 | [diff] [blame] | 440 | assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); |
Mark Lacey | f9ea885 | 2013-08-14 23:50:04 +0000 | [diff] [blame] | 441 | LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 442 | |
| 443 | // Create a new value. |
Jakob Stoklund Olesen | ad6b22e | 2012-02-04 05:20:49 +0000 | [diff] [blame] | 444 | VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator()); |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 445 | |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 446 | bool Force = LI->hasSubRanges(); |
| 447 | ValueForcePair FP(Force ? nullptr : VNI, Force); |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 448 | // Use insert for lookup, so we can add missing values with a second lookup. |
| 449 | std::pair<ValueMap::iterator, bool> InsP = |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 450 | Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP)); |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 451 | |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 452 | // This was the first time (RegIdx, ParentVNI) was mapped, and it is not |
| 453 | // forced. Keep it as a simple def without any liveness. |
| 454 | if (!Force && InsP.second) |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 455 | return VNI; |
| 456 | |
| 457 | // If the previous value was a simple mapping, add liveness for it now. |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 458 | if (VNInfo *OldVNI = InsP.first->second.getPointer()) { |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 459 | addDeadDef(*LI, OldVNI, Original); |
| 460 | |
| 461 | // No longer a simple mapping. Switch to a complex mapping. If the |
| 462 | // interval has subranges, make it a forced mapping. |
| 463 | InsP.first->second = ValueForcePair(nullptr, Force); |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 464 | } |
| 465 | |
| 466 | // This is a complex mapping, add liveness for VNI |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 467 | addDeadDef(*LI, VNI, Original); |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 468 | return VNI; |
| 469 | } |
| 470 | |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 471 | void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) { |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 472 | assert(ParentVNI && "Mapping NULL value"); |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 473 | ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)]; |
| 474 | VNInfo *VNI = VFP.getPointer(); |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 475 | |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 476 | // ParentVNI was either unmapped or already complex mapped. Either way, just |
| 477 | // set the force bit. |
| 478 | if (!VNI) { |
| 479 | VFP.setInt(true); |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 480 | return; |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 481 | } |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 482 | |
| 483 | // This was previously a single mapping. Make sure the old def is represented |
| 484 | // by a trivial live range. |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 485 | addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false); |
| 486 | |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 487 | // Mark as complex mapped, forced. |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 488 | VFP = ValueForcePair(nullptr, true); |
Jakob Stoklund Olesen | 4484f99 | 2011-09-13 18:05:29 +0000 | [diff] [blame] | 489 | } |
| 490 | |
Matthias Braun | f0b68d3 | 2017-03-17 00:41:39 +0000 | [diff] [blame] | 491 | SlotIndex SplitEditor::buildSingleSubRegCopy(unsigned FromReg, unsigned ToReg, |
| 492 | MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore, |
| 493 | unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def) { |
| 494 | const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY); |
| 495 | bool FirstCopy = !Def.isValid(); |
| 496 | MachineInstr *CopyMI = BuildMI(MBB, InsertBefore, DebugLoc(), Desc) |
| 497 | .addReg(ToReg, RegState::Define | getUndefRegState(FirstCopy) |
| 498 | | getInternalReadRegState(!FirstCopy), SubIdx) |
| 499 | .addReg(FromReg, 0, SubIdx); |
| 500 | |
| 501 | BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator(); |
| 502 | if (FirstCopy) { |
| 503 | SlotIndexes &Indexes = *LIS.getSlotIndexes(); |
| 504 | Def = Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot(); |
Matthias Braun | f0b68d3 | 2017-03-17 00:41:39 +0000 | [diff] [blame] | 505 | } else { |
| 506 | CopyMI->bundleWithPred(); |
| 507 | } |
| 508 | LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubIdx); |
| 509 | DestLI.refineSubRanges(Allocator, LaneMask, |
| 510 | [Def, &Allocator](LiveInterval::SubRange& SR) { |
| 511 | SR.createDeadDef(Def, Allocator); |
| 512 | }); |
| 513 | return Def; |
| 514 | } |
| 515 | |
| 516 | SlotIndex SplitEditor::buildCopy(unsigned FromReg, unsigned ToReg, |
| 517 | LaneBitmask LaneMask, MachineBasicBlock &MBB, |
| 518 | MachineBasicBlock::iterator InsertBefore, bool Late, unsigned RegIdx) { |
| 519 | const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY); |
| 520 | if (LaneMask.all() || LaneMask == MRI.getMaxLaneMaskForVReg(FromReg)) { |
| 521 | // The full vreg is copied. |
| 522 | MachineInstr *CopyMI = |
| 523 | BuildMI(MBB, InsertBefore, DebugLoc(), Desc, ToReg).addReg(FromReg); |
| 524 | SlotIndexes &Indexes = *LIS.getSlotIndexes(); |
| 525 | return Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot(); |
| 526 | } |
| 527 | |
| 528 | // Only a subset of lanes needs to be copied. The following is a simple |
| 529 | // heuristic to construct a sequence of COPYs. We could add a target |
| 530 | // specific callback if this turns out to be suboptimal. |
| 531 | LiveInterval &DestLI = LIS.getInterval(Edit->get(RegIdx)); |
| 532 | |
| 533 | // First pass: Try to find a perfectly matching subregister index. If none |
| 534 | // exists find the one covering the most lanemask bits. |
| 535 | SmallVector<unsigned, 8> PossibleIndexes; |
| 536 | unsigned BestIdx = 0; |
| 537 | unsigned BestCover = 0; |
| 538 | const TargetRegisterClass *RC = MRI.getRegClass(FromReg); |
| 539 | assert(RC == MRI.getRegClass(ToReg) && "Should have same reg class"); |
| 540 | for (unsigned Idx = 1, E = TRI.getNumSubRegIndices(); Idx < E; ++Idx) { |
| 541 | // Is this index even compatible with the given class? |
| 542 | if (TRI.getSubClassWithSubReg(RC, Idx) != RC) |
| 543 | continue; |
| 544 | LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(Idx); |
| 545 | // Early exit if we found a perfect match. |
| 546 | if (SubRegMask == LaneMask) { |
| 547 | BestIdx = Idx; |
| 548 | break; |
| 549 | } |
| 550 | |
| 551 | // The index must not cover any lanes outside \p LaneMask. |
| 552 | if ((SubRegMask & ~LaneMask).any()) |
| 553 | continue; |
| 554 | |
| 555 | unsigned PopCount = countPopulation(SubRegMask.getAsInteger()); |
| 556 | PossibleIndexes.push_back(Idx); |
| 557 | if (PopCount > BestCover) { |
| 558 | BestCover = PopCount; |
| 559 | BestIdx = Idx; |
| 560 | } |
| 561 | } |
| 562 | |
| 563 | // Abort if we cannot possibly implement the COPY with the given indexes. |
| 564 | if (BestIdx == 0) |
| 565 | report_fatal_error("Impossible to implement partial COPY"); |
| 566 | |
| 567 | SlotIndex Def = buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, |
| 568 | BestIdx, DestLI, Late, SlotIndex()); |
| 569 | |
| 570 | // Greedy heuristic: Keep iterating keeping the best covering subreg index |
| 571 | // each time. |
| 572 | LaneBitmask LanesLeft = |
| 573 | LaneMask & ~(TRI.getSubRegIndexLaneMask(BestCover)); |
| 574 | while (LanesLeft.any()) { |
| 575 | unsigned BestIdx = 0; |
| 576 | int BestCover = INT_MIN; |
| 577 | for (unsigned Idx : PossibleIndexes) { |
| 578 | LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(Idx); |
| 579 | // Early exit if we found a perfect match. |
| 580 | if (SubRegMask == LanesLeft) { |
| 581 | BestIdx = Idx; |
| 582 | break; |
| 583 | } |
| 584 | |
| 585 | // Try to cover as much of the remaining lanes as possible but |
| 586 | // as few of the already covered lanes as possible. |
| 587 | int Cover = countPopulation((SubRegMask & LanesLeft).getAsInteger()) |
| 588 | - countPopulation((SubRegMask & ~LanesLeft).getAsInteger()); |
| 589 | if (Cover > BestCover) { |
| 590 | BestCover = Cover; |
| 591 | BestIdx = Idx; |
| 592 | } |
| 593 | } |
| 594 | |
| 595 | if (BestIdx == 0) |
| 596 | report_fatal_error("Impossible to implement partial COPY"); |
| 597 | |
| 598 | buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, BestIdx, |
| 599 | DestLI, Late, Def); |
| 600 | LanesLeft &= ~TRI.getSubRegIndexLaneMask(BestIdx); |
| 601 | } |
| 602 | |
| 603 | return Def; |
| 604 | } |
| 605 | |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 606 | VNInfo *SplitEditor::defFromParent(unsigned RegIdx, |
Jakob Stoklund Olesen | 6ee7d9aa | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 607 | VNInfo *ParentVNI, |
| 608 | SlotIndex UseIdx, |
| 609 | MachineBasicBlock &MBB, |
| 610 | MachineBasicBlock::iterator I) { |
Jakob Stoklund Olesen | 6ee7d9aa | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 611 | SlotIndex Def; |
Mark Lacey | f9ea885 | 2013-08-14 23:50:04 +0000 | [diff] [blame] | 612 | LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); |
Jakob Stoklund Olesen | 6ee7d9aa | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 613 | |
Jakob Stoklund Olesen | 7d40679 | 2011-05-02 05:29:58 +0000 | [diff] [blame] | 614 | // We may be trying to avoid interference that ends at a deleted instruction, |
| 615 | // so always begin RegIdx 0 early and all others late. |
| 616 | bool Late = RegIdx != 0; |
| 617 | |
Jakob Stoklund Olesen | 6ee7d9aa | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 618 | // Attempt cheap-as-a-copy rematerialization. |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 619 | unsigned Original = VRM.getOriginal(Edit->get(RegIdx)); |
| 620 | LiveInterval &OrigLI = LIS.getInterval(Original); |
| 621 | VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx); |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 622 | |
Matthias Braun | f0b68d3 | 2017-03-17 00:41:39 +0000 | [diff] [blame] | 623 | unsigned Reg = LI->reg; |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 624 | bool DidRemat = false; |
| 625 | if (OrigVNI) { |
| 626 | LiveRangeEdit::Remat RM(ParentVNI); |
| 627 | RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def); |
| 628 | if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) { |
Matthias Braun | f0b68d3 | 2017-03-17 00:41:39 +0000 | [diff] [blame] | 629 | Def = Edit->rematerializeAt(MBB, I, Reg, RM, TRI, Late); |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 630 | ++NumRemats; |
| 631 | DidRemat = true; |
| 632 | } |
| 633 | } |
| 634 | if (!DidRemat) { |
Matthias Braun | f0b68d3 | 2017-03-17 00:41:39 +0000 | [diff] [blame] | 635 | LaneBitmask LaneMask; |
Stanislav Mekhanoshin | 70c245e | 2017-02-01 01:18:36 +0000 | [diff] [blame] | 636 | if (LI->hasSubRanges()) { |
Matthias Braun | f0b68d3 | 2017-03-17 00:41:39 +0000 | [diff] [blame] | 637 | LaneMask = LaneBitmask::getNone(); |
Stanislav Mekhanoshin | 70c245e | 2017-02-01 01:18:36 +0000 | [diff] [blame] | 638 | for (LiveInterval::SubRange &S : LI->subranges()) |
Matthias Braun | f0b68d3 | 2017-03-17 00:41:39 +0000 | [diff] [blame] | 639 | LaneMask |= S.LaneMask; |
| 640 | } else { |
| 641 | LaneMask = LaneBitmask::getAll(); |
Stanislav Mekhanoshin | 70c245e | 2017-02-01 01:18:36 +0000 | [diff] [blame] | 642 | } |
Matthias Braun | f0b68d3 | 2017-03-17 00:41:39 +0000 | [diff] [blame] | 643 | |
Jakob Stoklund Olesen | c5a8c08 | 2011-05-05 17:22:53 +0000 | [diff] [blame] | 644 | ++NumCopies; |
Matthias Braun | f0b68d3 | 2017-03-17 00:41:39 +0000 | [diff] [blame] | 645 | Def = buildCopy(Edit->getReg(), Reg, LaneMask, MBB, I, Late, RegIdx); |
Jakob Stoklund Olesen | 6ee7d9aa | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 646 | } |
| 647 | |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 648 | // Define the value in Reg. |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 649 | return defValue(RegIdx, ParentVNI, Def, false); |
Jakob Stoklund Olesen | 6ee7d9aa | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 650 | } |
| 651 | |
Jakob Stoklund Olesen | dc96e28 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 652 | /// Create a new virtual register and live interval. |
Jakob Stoklund Olesen | 0840f50 | 2011-04-12 18:11:31 +0000 | [diff] [blame] | 653 | unsigned SplitEditor::openIntv() { |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 654 | // Create the complement as index 0. |
Jakob Stoklund Olesen | 815196c | 2011-03-02 23:31:50 +0000 | [diff] [blame] | 655 | if (Edit->empty()) |
Mark Lacey | 9d8103d | 2013-08-14 23:50:16 +0000 | [diff] [blame] | 656 | Edit->createEmptyInterval(); |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 657 | |
| 658 | // Create the open interval. |
Jakob Stoklund Olesen | 815196c | 2011-03-02 23:31:50 +0000 | [diff] [blame] | 659 | OpenIdx = Edit->size(); |
Mark Lacey | 9d8103d | 2013-08-14 23:50:16 +0000 | [diff] [blame] | 660 | Edit->createEmptyInterval(); |
Jakob Stoklund Olesen | 0840f50 | 2011-04-12 18:11:31 +0000 | [diff] [blame] | 661 | return OpenIdx; |
| 662 | } |
| 663 | |
| 664 | void SplitEditor::selectIntv(unsigned Idx) { |
| 665 | assert(Idx != 0 && "Cannot select the complement interval"); |
| 666 | assert(Idx < Edit->size() && "Can only select previously opened interval"); |
Jakob Stoklund Olesen | adc6a4c | 2011-06-30 01:30:39 +0000 | [diff] [blame] | 667 | DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n'); |
Jakob Stoklund Olesen | 0840f50 | 2011-04-12 18:11:31 +0000 | [diff] [blame] | 668 | OpenIdx = Idx; |
Jakob Stoklund Olesen | dc96e28 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 669 | } |
| 670 | |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 671 | SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 672 | assert(OpenIdx && "openIntv not called before enterIntvBefore"); |
Jakob Stoklund Olesen | 9575af4 | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 673 | DEBUG(dbgs() << " enterIntvBefore " << Idx); |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 674 | Idx = Idx.getBaseIndex(); |
Jakob Stoklund Olesen | 815196c | 2011-03-02 23:31:50 +0000 | [diff] [blame] | 675 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); |
Jakob Stoklund Olesen | 9855109 | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 676 | if (!ParentVNI) { |
Jakob Stoklund Olesen | 9575af4 | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 677 | DEBUG(dbgs() << ": not live\n"); |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 678 | return Idx; |
Jakob Stoklund Olesen | 622848b | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 679 | } |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 680 | DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); |
Jakob Stoklund Olesen | b308902 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 681 | MachineInstr *MI = LIS.getInstructionFromIndex(Idx); |
Jakob Stoklund Olesen | 9855109 | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 682 | assert(MI && "enterIntvBefore called with invalid index"); |
Jakob Stoklund Olesen | 6ee7d9aa | 2010-11-10 19:31:50 +0000 | [diff] [blame] | 683 | |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 684 | VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); |
| 685 | return VNI->def; |
Jakob Stoklund Olesen | 622848b | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 686 | } |
| 687 | |
Jakob Stoklund Olesen | adc6a4c | 2011-06-30 01:30:39 +0000 | [diff] [blame] | 688 | SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { |
| 689 | assert(OpenIdx && "openIntv not called before enterIntvAfter"); |
| 690 | DEBUG(dbgs() << " enterIntvAfter " << Idx); |
| 691 | Idx = Idx.getBoundaryIndex(); |
| 692 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); |
| 693 | if (!ParentVNI) { |
| 694 | DEBUG(dbgs() << ": not live\n"); |
| 695 | return Idx; |
| 696 | } |
| 697 | DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); |
| 698 | MachineInstr *MI = LIS.getInstructionFromIndex(Idx); |
| 699 | assert(MI && "enterIntvAfter called with invalid index"); |
| 700 | |
| 701 | VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 702 | std::next(MachineBasicBlock::iterator(MI))); |
Jakob Stoklund Olesen | adc6a4c | 2011-06-30 01:30:39 +0000 | [diff] [blame] | 703 | return VNI->def; |
| 704 | } |
| 705 | |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 706 | SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 707 | assert(OpenIdx && "openIntv not called before enterIntvAtEnd"); |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 708 | SlotIndex End = LIS.getMBBEndIdx(&MBB); |
| 709 | SlotIndex Last = End.getPrevSlot(); |
| 710 | DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last); |
Jakob Stoklund Olesen | 815196c | 2011-03-02 23:31:50 +0000 | [diff] [blame] | 711 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); |
Jakob Stoklund Olesen | 9855109 | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 712 | if (!ParentVNI) { |
Jakob Stoklund Olesen | 9575af4 | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 713 | DEBUG(dbgs() << ": not live\n"); |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 714 | return End; |
Jakob Stoklund Olesen | c698417 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 715 | } |
Jakob Stoklund Olesen | 9575af4 | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 716 | DEBUG(dbgs() << ": valno " << ParentVNI->id); |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 717 | VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, |
Jakob Stoklund Olesen | 67aec12 | 2012-01-11 02:07:00 +0000 | [diff] [blame] | 718 | SA.getLastSplitPointIter(&MBB)); |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 719 | RegAssign.insert(VNI->def, End, OpenIdx); |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 720 | DEBUG(dump()); |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 721 | return VNI->def; |
Jakob Stoklund Olesen | c698417 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 722 | } |
| 723 | |
Jakob Stoklund Olesen | b308902 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 724 | /// useIntv - indicate that all instructions in MBB should use OpenLI. |
Jakob Stoklund Olesen | dc96e28 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 725 | void SplitEditor::useIntv(const MachineBasicBlock &MBB) { |
Jakob Stoklund Olesen | b308902 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 726 | useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); |
Jakob Stoklund Olesen | c698417 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 727 | } |
| 728 | |
Jakob Stoklund Olesen | dc96e28 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 729 | void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 730 | assert(OpenIdx && "openIntv not called before useIntv"); |
| 731 | DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):"); |
| 732 | RegAssign.insert(Start, End, OpenIdx); |
| 733 | DEBUG(dump()); |
Jakob Stoklund Olesen | c698417 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 734 | } |
| 735 | |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 736 | SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 737 | assert(OpenIdx && "openIntv not called before leaveIntvAfter"); |
Jakob Stoklund Olesen | 9575af4 | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 738 | DEBUG(dbgs() << " leaveIntvAfter " << Idx); |
Jakob Stoklund Olesen | 622848b | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 739 | |
Jakob Stoklund Olesen | 9855109 | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 740 | // The interval must be live beyond the instruction at Idx. |
Jakob Stoklund Olesen | e2c92a3 | 2011-09-16 00:03:35 +0000 | [diff] [blame] | 741 | SlotIndex Boundary = Idx.getBoundaryIndex(); |
| 742 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary); |
Jakob Stoklund Olesen | 9855109 | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 743 | if (!ParentVNI) { |
Jakob Stoklund Olesen | 9575af4 | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 744 | DEBUG(dbgs() << ": not live\n"); |
Jakob Stoklund Olesen | e2c92a3 | 2011-09-16 00:03:35 +0000 | [diff] [blame] | 745 | return Boundary.getNextSlot(); |
Jakob Stoklund Olesen | 622848b | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 746 | } |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 747 | DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); |
Jakob Stoklund Olesen | e2c92a3 | 2011-09-16 00:03:35 +0000 | [diff] [blame] | 748 | MachineInstr *MI = LIS.getInstructionFromIndex(Boundary); |
Jakob Stoklund Olesen | 3d11c8e | 2011-02-08 18:50:18 +0000 | [diff] [blame] | 749 | assert(MI && "No instruction at index"); |
Jakob Stoklund Olesen | e2c92a3 | 2011-09-16 00:03:35 +0000 | [diff] [blame] | 750 | |
| 751 | // In spill mode, make live ranges as short as possible by inserting the copy |
| 752 | // before MI. This is only possible if that instruction doesn't redefine the |
| 753 | // value. The inserted COPY is not a kill, and we don't need to recompute |
| 754 | // the source live range. The spiller also won't try to hoist this copy. |
| 755 | if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) && |
| 756 | MI->readsVirtualRegister(Edit->getReg())) { |
| 757 | forceRecompute(0, ParentVNI); |
| 758 | defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); |
| 759 | return Idx; |
| 760 | } |
| 761 | |
| 762 | VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(), |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 763 | std::next(MachineBasicBlock::iterator(MI))); |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 764 | return VNI->def; |
Jakob Stoklund Olesen | 622848b | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 765 | } |
| 766 | |
Jakob Stoklund Olesen | 7cb57b3 | 2011-02-09 23:30:25 +0000 | [diff] [blame] | 767 | SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { |
| 768 | assert(OpenIdx && "openIntv not called before leaveIntvBefore"); |
| 769 | DEBUG(dbgs() << " leaveIntvBefore " << Idx); |
| 770 | |
| 771 | // The interval must be live into the instruction at Idx. |
Jakob Stoklund Olesen | c45d38e | 2011-07-18 18:47:13 +0000 | [diff] [blame] | 772 | Idx = Idx.getBaseIndex(); |
Jakob Stoklund Olesen | 815196c | 2011-03-02 23:31:50 +0000 | [diff] [blame] | 773 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); |
Jakob Stoklund Olesen | 7cb57b3 | 2011-02-09 23:30:25 +0000 | [diff] [blame] | 774 | if (!ParentVNI) { |
| 775 | DEBUG(dbgs() << ": not live\n"); |
| 776 | return Idx.getNextSlot(); |
| 777 | } |
| 778 | DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); |
| 779 | |
| 780 | MachineInstr *MI = LIS.getInstructionFromIndex(Idx); |
| 781 | assert(MI && "No instruction at index"); |
| 782 | VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); |
| 783 | return VNI->def; |
| 784 | } |
| 785 | |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 786 | SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 787 | assert(OpenIdx && "openIntv not called before leaveIntvAtTop"); |
Jakob Stoklund Olesen | b308902 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 788 | SlotIndex Start = LIS.getMBBStartIdx(&MBB); |
Jakob Stoklund Olesen | 9575af4 | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 789 | DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start); |
Jakob Stoklund Olesen | dc96e28 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 790 | |
Jakob Stoklund Olesen | 815196c | 2011-03-02 23:31:50 +0000 | [diff] [blame] | 791 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); |
Jakob Stoklund Olesen | 9855109 | 2010-09-16 00:01:36 +0000 | [diff] [blame] | 792 | if (!ParentVNI) { |
Jakob Stoklund Olesen | 9575af4 | 2010-10-07 17:56:35 +0000 | [diff] [blame] | 793 | DEBUG(dbgs() << ": not live\n"); |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 794 | return Start; |
Jakob Stoklund Olesen | dc96e28 | 2010-08-04 22:08:39 +0000 | [diff] [blame] | 795 | } |
| 796 | |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 797 | VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, |
Keith Walker | 830a8c1 | 2016-09-16 14:07:29 +0000 | [diff] [blame] | 798 | MBB.SkipPHIsLabelsAndDebug(MBB.begin())); |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 799 | RegAssign.insert(Start, VNI->def, OpenIdx); |
| 800 | DEBUG(dump()); |
Jakob Stoklund Olesen | f12e120 | 2011-02-03 17:04:16 +0000 | [diff] [blame] | 801 | return VNI->def; |
Jakob Stoklund Olesen | c698417 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 802 | } |
| 803 | |
Jakob Stoklund Olesen | 1749935 | 2011-02-08 18:50:21 +0000 | [diff] [blame] | 804 | void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { |
| 805 | assert(OpenIdx && "openIntv not called before overlapIntv"); |
Jakob Stoklund Olesen | 815196c | 2011-03-02 23:31:50 +0000 | [diff] [blame] | 806 | const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); |
Jakob Stoklund Olesen | d7bcf43 | 2011-11-14 01:39:36 +0000 | [diff] [blame] | 807 | assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) && |
Jakob Stoklund Olesen | 1749935 | 2011-02-08 18:50:21 +0000 | [diff] [blame] | 808 | "Parent changes value in extended range"); |
Jakob Stoklund Olesen | 1749935 | 2011-02-08 18:50:21 +0000 | [diff] [blame] | 809 | assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && |
| 810 | "Range cannot span basic blocks"); |
| 811 | |
Jakob Stoklund Olesen | 820c8fd0 | 2011-09-13 17:38:57 +0000 | [diff] [blame] | 812 | // The complement interval will be extended as needed by LRCalc.extend(). |
Jakob Stoklund Olesen | 5c482cd | 2011-04-05 23:43:14 +0000 | [diff] [blame] | 813 | if (ParentVNI) |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 814 | forceRecompute(0, ParentVNI); |
Jakob Stoklund Olesen | 1749935 | 2011-02-08 18:50:21 +0000 | [diff] [blame] | 815 | DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); |
| 816 | RegAssign.insert(Start, End, OpenIdx); |
| 817 | DEBUG(dump()); |
| 818 | } |
| 819 | |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 820 | //===----------------------------------------------------------------------===// |
| 821 | // Spill modes |
| 822 | //===----------------------------------------------------------------------===// |
| 823 | |
| 824 | void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) { |
Mark Lacey | f9ea885 | 2013-08-14 23:50:04 +0000 | [diff] [blame] | 825 | LiveInterval *LI = &LIS.getInterval(Edit->get(0)); |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 826 | DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n"); |
| 827 | RegAssignMap::iterator AssignI; |
| 828 | AssignI.setMap(RegAssign); |
| 829 | |
| 830 | for (unsigned i = 0, e = Copies.size(); i != e; ++i) { |
Matthias Braun | 311730a | 2015-01-21 19:02:30 +0000 | [diff] [blame] | 831 | SlotIndex Def = Copies[i]->def; |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 832 | MachineInstr *MI = LIS.getInstructionFromIndex(Def); |
| 833 | assert(MI && "No instruction for back-copy"); |
| 834 | |
| 835 | MachineBasicBlock *MBB = MI->getParent(); |
| 836 | MachineBasicBlock::iterator MBBI(MI); |
| 837 | bool AtBegin; |
| 838 | do AtBegin = MBBI == MBB->begin(); |
| 839 | while (!AtBegin && (--MBBI)->isDebugValue()); |
| 840 | |
| 841 | DEBUG(dbgs() << "Removing " << Def << '\t' << *MI); |
Matthias Braun | 311730a | 2015-01-21 19:02:30 +0000 | [diff] [blame] | 842 | LIS.removeVRegDefAt(*LI, Def); |
Duncan P. N. Exon Smith | 3ac9cc6 | 2016-02-27 06:40:41 +0000 | [diff] [blame] | 843 | LIS.RemoveMachineInstrFromMaps(*MI); |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 844 | MI->eraseFromParent(); |
| 845 | |
Matthias Braun | 311730a | 2015-01-21 19:02:30 +0000 | [diff] [blame] | 846 | // Adjust RegAssign if a register assignment is killed at Def. We want to |
| 847 | // avoid calculating the live range of the source register if possible. |
Jakob Stoklund Olesen | 2180938 | 2012-08-03 20:59:29 +0000 | [diff] [blame] | 848 | AssignI.find(Def.getPrevSlot()); |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 849 | if (!AssignI.valid() || AssignI.start() >= Def) |
| 850 | continue; |
| 851 | // If MI doesn't kill the assigned register, just leave it. |
| 852 | if (AssignI.stop() != Def) |
| 853 | continue; |
| 854 | unsigned RegIdx = AssignI.value(); |
| 855 | if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) { |
| 856 | DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx << '\n'); |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 857 | forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def)); |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 858 | } else { |
Duncan P. N. Exon Smith | 3ac9cc6 | 2016-02-27 06:40:41 +0000 | [diff] [blame] | 859 | SlotIndex Kill = LIS.getInstructionIndex(*MBBI).getRegSlot(); |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 860 | DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI); |
| 861 | AssignI.setStop(Kill); |
| 862 | } |
| 863 | } |
| 864 | } |
| 865 | |
Jakob Stoklund Olesen | a98af39 | 2011-09-14 16:45:39 +0000 | [diff] [blame] | 866 | MachineBasicBlock* |
| 867 | SplitEditor::findShallowDominator(MachineBasicBlock *MBB, |
| 868 | MachineBasicBlock *DefMBB) { |
| 869 | if (MBB == DefMBB) |
| 870 | return MBB; |
| 871 | assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def."); |
| 872 | |
| 873 | const MachineLoopInfo &Loops = SA.Loops; |
| 874 | const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB); |
| 875 | MachineDomTreeNode *DefDomNode = MDT[DefMBB]; |
| 876 | |
| 877 | // Best candidate so far. |
| 878 | MachineBasicBlock *BestMBB = MBB; |
| 879 | unsigned BestDepth = UINT_MAX; |
| 880 | |
| 881 | for (;;) { |
| 882 | const MachineLoop *Loop = Loops.getLoopFor(MBB); |
| 883 | |
| 884 | // MBB isn't in a loop, it doesn't get any better. All dominators have a |
| 885 | // higher frequency by definition. |
| 886 | if (!Loop) { |
| 887 | DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" |
| 888 | << MBB->getNumber() << " at depth 0\n"); |
| 889 | return MBB; |
| 890 | } |
| 891 | |
| 892 | // We'll never be able to exit the DefLoop. |
| 893 | if (Loop == DefLoop) { |
| 894 | DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" |
| 895 | << MBB->getNumber() << " in the same loop\n"); |
| 896 | return MBB; |
| 897 | } |
| 898 | |
| 899 | // Least busy dominator seen so far. |
| 900 | unsigned Depth = Loop->getLoopDepth(); |
| 901 | if (Depth < BestDepth) { |
| 902 | BestMBB = MBB; |
| 903 | BestDepth = Depth; |
| 904 | DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" |
| 905 | << MBB->getNumber() << " at depth " << Depth << '\n'); |
| 906 | } |
| 907 | |
| 908 | // Leave loop by going to the immediate dominator of the loop header. |
| 909 | // This is a bigger stride than simply walking up the dominator tree. |
| 910 | MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom(); |
| 911 | |
| 912 | // Too far up the dominator tree? |
| 913 | if (!IDom || !MDT.dominates(DefDomNode, IDom)) |
| 914 | return BestMBB; |
| 915 | |
| 916 | MBB = IDom->getBlock(); |
| 917 | } |
| 918 | } |
| 919 | |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 920 | void SplitEditor::computeRedundantBackCopies( |
| 921 | DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) { |
| 922 | LiveInterval *LI = &LIS.getInterval(Edit->get(0)); |
| 923 | LiveInterval *Parent = &Edit->getParent(); |
| 924 | SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums()); |
| 925 | SmallPtrSet<VNInfo *, 8> DominatedVNIs; |
| 926 | |
| 927 | // Aggregate VNIs having the same value as ParentVNI. |
| 928 | for (VNInfo *VNI : LI->valnos) { |
| 929 | if (VNI->isUnused()) |
| 930 | continue; |
| 931 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); |
| 932 | EqualVNs[ParentVNI->id].insert(VNI); |
| 933 | } |
| 934 | |
| 935 | // For VNI aggregation of each ParentVNI, collect dominated, i.e., |
| 936 | // redundant VNIs to BackCopies. |
| 937 | for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { |
| 938 | VNInfo *ParentVNI = Parent->getValNumInfo(i); |
| 939 | if (!NotToHoistSet.count(ParentVNI->id)) |
| 940 | continue; |
| 941 | SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin(); |
| 942 | SmallPtrSetIterator<VNInfo *> It2 = It1; |
| 943 | for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) { |
| 944 | It2 = It1; |
| 945 | for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) { |
| 946 | if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2)) |
| 947 | continue; |
| 948 | |
| 949 | MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def); |
| 950 | MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def); |
| 951 | if (MBB1 == MBB2) { |
| 952 | DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1)); |
| 953 | } else if (MDT.dominates(MBB1, MBB2)) { |
| 954 | DominatedVNIs.insert(*It2); |
| 955 | } else if (MDT.dominates(MBB2, MBB1)) { |
| 956 | DominatedVNIs.insert(*It1); |
| 957 | } |
| 958 | } |
| 959 | } |
| 960 | if (!DominatedVNIs.empty()) { |
| 961 | forceRecompute(0, ParentVNI); |
| 962 | for (auto VNI : DominatedVNIs) { |
| 963 | BackCopies.push_back(VNI); |
| 964 | } |
| 965 | DominatedVNIs.clear(); |
| 966 | } |
| 967 | } |
| 968 | } |
| 969 | |
| 970 | /// For SM_Size mode, find a common dominator for all the back-copies for |
| 971 | /// the same ParentVNI and hoist the backcopies to the dominator BB. |
| 972 | /// For SM_Speed mode, if the common dominator is hot and it is not beneficial |
| 973 | /// to do the hoisting, simply remove the dominated backcopies for the same |
| 974 | /// ParentVNI. |
| 975 | void SplitEditor::hoistCopies() { |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 976 | // Get the complement interval, always RegIdx 0. |
Mark Lacey | f9ea885 | 2013-08-14 23:50:04 +0000 | [diff] [blame] | 977 | LiveInterval *LI = &LIS.getInterval(Edit->get(0)); |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 978 | LiveInterval *Parent = &Edit->getParent(); |
| 979 | |
| 980 | // Track the nearest common dominator for all back-copies for each ParentVNI, |
| 981 | // indexed by ParentVNI->id. |
| 982 | typedef std::pair<MachineBasicBlock*, SlotIndex> DomPair; |
| 983 | SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums()); |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 984 | // The total cost of all the back-copies for each ParentVNI. |
| 985 | SmallVector<BlockFrequency, 8> Costs(Parent->getNumValNums()); |
| 986 | // The ParentVNI->id set for which hoisting back-copies are not beneficial |
| 987 | // for Speed. |
| 988 | DenseSet<unsigned> NotToHoistSet; |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 989 | |
| 990 | // Find the nearest common dominator for parent values with multiple |
| 991 | // back-copies. If a single back-copy dominates, put it in DomPair.second. |
Matthias Braun | 9676195 | 2014-12-10 23:07:54 +0000 | [diff] [blame] | 992 | for (VNInfo *VNI : LI->valnos) { |
Jakob Stoklund Olesen | 2180938 | 2012-08-03 20:59:29 +0000 | [diff] [blame] | 993 | if (VNI->isUnused()) |
| 994 | continue; |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 995 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); |
| 996 | assert(ParentVNI && "Parent not live at complement def"); |
| 997 | |
| 998 | // Don't hoist remats. The complement is probably going to disappear |
| 999 | // completely anyway. |
| 1000 | if (Edit->didRematerialize(ParentVNI)) |
| 1001 | continue; |
| 1002 | |
| 1003 | MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def); |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 1004 | |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 1005 | DomPair &Dom = NearestDom[ParentVNI->id]; |
| 1006 | |
| 1007 | // Keep directly defined parent values. This is either a PHI or an |
| 1008 | // instruction in the complement range. All other copies of ParentVNI |
| 1009 | // should be eliminated. |
| 1010 | if (VNI->def == ParentVNI->def) { |
| 1011 | DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n'); |
| 1012 | Dom = DomPair(ValMBB, VNI->def); |
| 1013 | continue; |
| 1014 | } |
| 1015 | // Skip the singly mapped values. There is nothing to gain from hoisting a |
| 1016 | // single back-copy. |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 1017 | if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) { |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 1018 | DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n'); |
| 1019 | continue; |
| 1020 | } |
| 1021 | |
| 1022 | if (!Dom.first) { |
| 1023 | // First time we see ParentVNI. VNI dominates itself. |
| 1024 | Dom = DomPair(ValMBB, VNI->def); |
| 1025 | } else if (Dom.first == ValMBB) { |
| 1026 | // Two defs in the same block. Pick the earlier def. |
| 1027 | if (!Dom.second.isValid() || VNI->def < Dom.second) |
| 1028 | Dom.second = VNI->def; |
| 1029 | } else { |
| 1030 | // Different basic blocks. Check if one dominates. |
| 1031 | MachineBasicBlock *Near = |
| 1032 | MDT.findNearestCommonDominator(Dom.first, ValMBB); |
| 1033 | if (Near == ValMBB) |
| 1034 | // Def ValMBB dominates. |
| 1035 | Dom = DomPair(ValMBB, VNI->def); |
| 1036 | else if (Near != Dom.first) |
| 1037 | // None dominate. Hoist to common dominator, need new def. |
| 1038 | Dom = DomPair(Near, SlotIndex()); |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 1039 | Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB); |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 1040 | } |
| 1041 | |
| 1042 | DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' << VNI->def |
| 1043 | << " for parent " << ParentVNI->id << '@' << ParentVNI->def |
| 1044 | << " hoist to BB#" << Dom.first->getNumber() << ' ' |
| 1045 | << Dom.second << '\n'); |
| 1046 | } |
| 1047 | |
| 1048 | // Insert the hoisted copies. |
| 1049 | for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { |
| 1050 | DomPair &Dom = NearestDom[i]; |
| 1051 | if (!Dom.first || Dom.second.isValid()) |
| 1052 | continue; |
Jakob Stoklund Olesen | a98af39 | 2011-09-14 16:45:39 +0000 | [diff] [blame] | 1053 | // This value needs a hoisted copy inserted at the end of Dom.first. |
| 1054 | VNInfo *ParentVNI = Parent->getValNumInfo(i); |
| 1055 | MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def); |
| 1056 | // Get a less loopy dominator than Dom.first. |
| 1057 | Dom.first = findShallowDominator(Dom.first, DefMBB); |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 1058 | if (SpillMode == SM_Speed && |
| 1059 | MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) { |
| 1060 | NotToHoistSet.insert(ParentVNI->id); |
| 1061 | continue; |
| 1062 | } |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 1063 | SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot(); |
| 1064 | Dom.second = |
Jakob Stoklund Olesen | a98af39 | 2011-09-14 16:45:39 +0000 | [diff] [blame] | 1065 | defFromParent(0, ParentVNI, Last, *Dom.first, |
Jakob Stoklund Olesen | 67aec12 | 2012-01-11 02:07:00 +0000 | [diff] [blame] | 1066 | SA.getLastSplitPointIter(Dom.first))->def; |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 1067 | } |
| 1068 | |
| 1069 | // Remove redundant back-copies that are now known to be dominated by another |
| 1070 | // def with the same value. |
| 1071 | SmallVector<VNInfo*, 8> BackCopies; |
Matthias Braun | 9676195 | 2014-12-10 23:07:54 +0000 | [diff] [blame] | 1072 | for (VNInfo *VNI : LI->valnos) { |
Jakob Stoklund Olesen | 2180938 | 2012-08-03 20:59:29 +0000 | [diff] [blame] | 1073 | if (VNI->isUnused()) |
| 1074 | continue; |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 1075 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); |
| 1076 | const DomPair &Dom = NearestDom[ParentVNI->id]; |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 1077 | if (!Dom.first || Dom.second == VNI->def || |
| 1078 | NotToHoistSet.count(ParentVNI->id)) |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 1079 | continue; |
| 1080 | BackCopies.push_back(VNI); |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 1081 | forceRecompute(0, ParentVNI); |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 1082 | } |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 1083 | |
| 1084 | // If it is not beneficial to hoist all the BackCopies, simply remove |
| 1085 | // redundant BackCopies in speed mode. |
| 1086 | if (SpillMode == SM_Speed && !NotToHoistSet.empty()) |
| 1087 | computeRedundantBackCopies(NotToHoistSet, BackCopies); |
| 1088 | |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 1089 | removeBackCopies(BackCopies); |
| 1090 | } |
| 1091 | |
| 1092 | |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1093 | /// transferValues - Transfer all possible values to the new live ranges. |
Jakob Stoklund Olesen | 820c8fd0 | 2011-09-13 17:38:57 +0000 | [diff] [blame] | 1094 | /// Values that were rematerialized are left alone, they need LRCalc.extend(). |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1095 | bool SplitEditor::transferValues() { |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 1096 | bool Skipped = false; |
| 1097 | RegAssignMap::const_iterator AssignI = RegAssign.begin(); |
Matthias Braun | 9676195 | 2014-12-10 23:07:54 +0000 | [diff] [blame] | 1098 | for (const LiveRange::Segment &S : Edit->getParent()) { |
| 1099 | DEBUG(dbgs() << " blit " << S << ':'); |
| 1100 | VNInfo *ParentVNI = S.valno; |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 1101 | // RegAssign has holes where RegIdx 0 should be used. |
Matthias Braun | 9676195 | 2014-12-10 23:07:54 +0000 | [diff] [blame] | 1102 | SlotIndex Start = S.start; |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 1103 | AssignI.advanceTo(Start); |
| 1104 | do { |
| 1105 | unsigned RegIdx; |
Matthias Braun | 9676195 | 2014-12-10 23:07:54 +0000 | [diff] [blame] | 1106 | SlotIndex End = S.end; |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 1107 | if (!AssignI.valid()) { |
| 1108 | RegIdx = 0; |
| 1109 | } else if (AssignI.start() <= Start) { |
| 1110 | RegIdx = AssignI.value(); |
| 1111 | if (AssignI.stop() < End) { |
| 1112 | End = AssignI.stop(); |
| 1113 | ++AssignI; |
| 1114 | } |
| 1115 | } else { |
| 1116 | RegIdx = 0; |
| 1117 | End = std::min(End, AssignI.start()); |
| 1118 | } |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1119 | |
| 1120 | // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1121 | DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx |
| 1122 | << '(' << PrintReg(Edit->get(RegIdx)) << ')'); |
| 1123 | LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1124 | |
| 1125 | // Check for a simply defined value that can be blitted directly. |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 1126 | ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id)); |
| 1127 | if (VNInfo *VNI = VFP.getPointer()) { |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 1128 | DEBUG(dbgs() << ':' << VNI->id); |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1129 | LI.addSegment(LiveInterval::Segment(Start, End, VNI)); |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1130 | Start = End; |
| 1131 | continue; |
| 1132 | } |
| 1133 | |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 1134 | // Skip values with forced recomputation. |
| 1135 | if (VFP.getInt()) { |
| 1136 | DEBUG(dbgs() << "(recalc)"); |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 1137 | Skipped = true; |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1138 | Start = End; |
| 1139 | continue; |
| 1140 | } |
| 1141 | |
Jakob Stoklund Olesen | 054984d | 2011-09-13 16:47:53 +0000 | [diff] [blame] | 1142 | LiveRangeCalc &LRC = getLRCalc(RegIdx); |
| 1143 | |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1144 | // This value has multiple defs in RegIdx, but it wasn't rematerialized, |
| 1145 | // so the live range is accurate. Add live-in blocks in [Start;End) to the |
| 1146 | // LiveInBlocks. |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 1147 | MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator(); |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1148 | SlotIndex BlockStart, BlockEnd; |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 1149 | std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB); |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1150 | |
| 1151 | // The first block may be live-in, or it may have its own def. |
| 1152 | if (Start != BlockStart) { |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1153 | VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End)); |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1154 | assert(VNI && "Missing def for complex mapped value"); |
| 1155 | DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); |
| 1156 | // MBB has its own def. Is it also live-out? |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 1157 | if (BlockEnd <= End) |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 1158 | LRC.setLiveOutValue(&*MBB, VNI); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 1159 | |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1160 | // Skip to the next block for live-in. |
| 1161 | ++MBB; |
| 1162 | BlockStart = BlockEnd; |
| 1163 | } |
| 1164 | |
| 1165 | // Handle the live-in blocks covered by [Start;End). |
| 1166 | assert(Start <= BlockStart && "Expected live-in block"); |
| 1167 | while (BlockStart < End) { |
| 1168 | DEBUG(dbgs() << ">BB#" << MBB->getNumber()); |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 1169 | BlockEnd = LIS.getMBBEndIdx(&*MBB); |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1170 | if (BlockStart == ParentVNI->def) { |
| 1171 | // This block has the def of a parent PHI, so it isn't live-in. |
| 1172 | assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1173 | VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End)); |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1174 | assert(VNI && "Missing def for complex mapped parent PHI"); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 1175 | if (End >= BlockEnd) |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 1176 | LRC.setLiveOutValue(&*MBB, VNI); // Live-out as well. |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1177 | } else { |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 1178 | // This block needs a live-in value. The last block covered may not |
| 1179 | // be live-out. |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1180 | if (End < BlockEnd) |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1181 | LRC.addLiveInBlock(LI, MDT[&*MBB], End); |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1182 | else { |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 1183 | // Live-through, and we don't know the value. |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1184 | LRC.addLiveInBlock(LI, MDT[&*MBB]); |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 1185 | LRC.setLiveOutValue(&*MBB, nullptr); |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1186 | } |
| 1187 | } |
| 1188 | BlockStart = BlockEnd; |
| 1189 | ++MBB; |
| 1190 | } |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 1191 | Start = End; |
Matthias Braun | 9676195 | 2014-12-10 23:07:54 +0000 | [diff] [blame] | 1192 | } while (Start != S.end); |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 1193 | DEBUG(dbgs() << '\n'); |
| 1194 | } |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1195 | |
Jakob Stoklund Olesen | 5ef0e0b | 2012-06-04 18:21:16 +0000 | [diff] [blame] | 1196 | LRCalc[0].calculateValues(); |
Jakob Stoklund Olesen | 054984d | 2011-09-13 16:47:53 +0000 | [diff] [blame] | 1197 | if (SpillMode) |
Jakob Stoklund Olesen | 5ef0e0b | 2012-06-04 18:21:16 +0000 | [diff] [blame] | 1198 | LRCalc[1].calculateValues(); |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1199 | |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 1200 | return Skipped; |
| 1201 | } |
| 1202 | |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1203 | static bool removeDeadSegment(SlotIndex Def, LiveRange &LR) { |
| 1204 | const LiveRange::Segment *Seg = LR.getSegmentContaining(Def); |
| 1205 | if (Seg == nullptr) |
| 1206 | return true; |
| 1207 | if (Seg->end != Def.getDeadSlot()) |
| 1208 | return false; |
| 1209 | // This is a dead PHI. Remove it. |
| 1210 | LR.removeSegment(*Seg, true); |
| 1211 | return true; |
| 1212 | } |
| 1213 | |
| 1214 | void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveRangeCalc &LRC, |
Krzysztof Parzyszek | 73c8a9b | 2016-11-21 20:24:12 +0000 | [diff] [blame] | 1215 | LiveRange &LR, LaneBitmask LM, |
| 1216 | ArrayRef<SlotIndex> Undefs) { |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1217 | for (MachineBasicBlock *P : B.predecessors()) { |
| 1218 | SlotIndex End = LIS.getMBBEndIdx(P); |
| 1219 | SlotIndex LastUse = End.getPrevSlot(); |
| 1220 | // The predecessor may not have a live-out value. That is OK, like an |
| 1221 | // undef PHI operand. |
Krzysztof Parzyszek | 73c8a9b | 2016-11-21 20:24:12 +0000 | [diff] [blame] | 1222 | LiveInterval &PLI = Edit->getParent(); |
| 1223 | // Need the cast because the inputs to ?: would otherwise be deemed |
| 1224 | // "incompatible": SubRange vs LiveInterval. |
Krzysztof Parzyszek | 91b5cf8 | 2016-12-15 14:36:06 +0000 | [diff] [blame] | 1225 | LiveRange &PSR = !LM.all() ? getSubRangeForMask(LM, PLI) |
| 1226 | : static_cast<LiveRange&>(PLI); |
Krzysztof Parzyszek | 73c8a9b | 2016-11-21 20:24:12 +0000 | [diff] [blame] | 1227 | if (PSR.liveAt(LastUse)) |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1228 | LRC.extend(LR, End, /*PhysReg=*/0, Undefs); |
| 1229 | } |
| 1230 | } |
| 1231 | |
Jakob Stoklund Olesen | 3648263 | 2011-03-02 23:05:16 +0000 | [diff] [blame] | 1232 | void SplitEditor::extendPHIKillRanges() { |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 1233 | // Extend live ranges to be live-out for successor PHI values. |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 1234 | |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1235 | // Visit each PHI def slot in the parent live interval. If the def is dead, |
| 1236 | // remove it. Otherwise, extend the live interval to reach the end indexes |
| 1237 | // of all predecessor blocks. |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 1238 | |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1239 | LiveInterval &ParentLI = Edit->getParent(); |
| 1240 | for (const VNInfo *V : ParentLI.valnos) { |
| 1241 | if (V->isUnused() || !V->isPHIDef()) |
| 1242 | continue; |
| 1243 | |
| 1244 | unsigned RegIdx = RegAssign.lookup(V->def); |
| 1245 | LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); |
Jakob Stoklund Olesen | 820c8fd0 | 2011-09-13 17:38:57 +0000 | [diff] [blame] | 1246 | LiveRangeCalc &LRC = getLRCalc(RegIdx); |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1247 | MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def); |
| 1248 | if (!removeDeadSegment(V->def, LI)) |
Krzysztof Parzyszek | 91b5cf8 | 2016-12-15 14:36:06 +0000 | [diff] [blame] | 1249 | extendPHIRange(B, LRC, LI, LaneBitmask::getAll(), /*Undefs=*/{}); |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1250 | } |
| 1251 | |
| 1252 | SmallVector<SlotIndex, 4> Undefs; |
| 1253 | LiveRangeCalc SubLRC; |
| 1254 | |
| 1255 | for (LiveInterval::SubRange &PS : ParentLI.subranges()) { |
| 1256 | for (const VNInfo *V : PS.valnos) { |
| 1257 | if (V->isUnused() || !V->isPHIDef()) |
| 1258 | continue; |
| 1259 | unsigned RegIdx = RegAssign.lookup(V->def); |
| 1260 | LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); |
| 1261 | LiveInterval::SubRange &S = getSubRangeForMask(PS.LaneMask, LI); |
| 1262 | if (removeDeadSegment(V->def, S)) |
| 1263 | continue; |
| 1264 | |
| 1265 | MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def); |
| 1266 | SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, |
| 1267 | &LIS.getVNInfoAllocator()); |
| 1268 | Undefs.clear(); |
| 1269 | LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes()); |
Krzysztof Parzyszek | 73c8a9b | 2016-11-21 20:24:12 +0000 | [diff] [blame] | 1270 | extendPHIRange(B, SubLRC, S, PS.LaneMask, Undefs); |
Jakob Stoklund Olesen | 3648263 | 2011-03-02 23:05:16 +0000 | [diff] [blame] | 1271 | } |
| 1272 | } |
| 1273 | } |
| 1274 | |
Jakob Stoklund Olesen | 815196c | 2011-03-02 23:31:50 +0000 | [diff] [blame] | 1275 | /// rewriteAssigned - Rewrite all uses of Edit->getReg(). |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 1276 | void SplitEditor::rewriteAssigned(bool ExtendRanges) { |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1277 | struct ExtPoint { |
| 1278 | ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N) |
| 1279 | : MO(O), RegIdx(R), Next(N) {} |
| 1280 | MachineOperand MO; |
| 1281 | unsigned RegIdx; |
| 1282 | SlotIndex Next; |
| 1283 | }; |
| 1284 | |
| 1285 | SmallVector<ExtPoint,4> ExtPoints; |
| 1286 | |
Jakob Stoklund Olesen | 815196c | 2011-03-02 23:31:50 +0000 | [diff] [blame] | 1287 | for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), |
Jakob Stoklund Olesen | b308902 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 1288 | RE = MRI.reg_end(); RI != RE;) { |
Owen Anderson | 16c6bf4 | 2014-03-13 23:12:04 +0000 | [diff] [blame] | 1289 | MachineOperand &MO = *RI; |
Jakob Stoklund Olesen | 959fcc6 | 2010-10-08 23:42:21 +0000 | [diff] [blame] | 1290 | MachineInstr *MI = MO.getParent(); |
| 1291 | ++RI; |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 1292 | // LiveDebugVariables should have handled all DBG_VALUE instructions. |
Jakob Stoklund Olesen | 959fcc6 | 2010-10-08 23:42:21 +0000 | [diff] [blame] | 1293 | if (MI->isDebugValue()) { |
| 1294 | DEBUG(dbgs() << "Zapping " << *MI); |
Jakob Stoklund Olesen | 959fcc6 | 2010-10-08 23:42:21 +0000 | [diff] [blame] | 1295 | MO.setReg(0); |
| 1296 | continue; |
| 1297 | } |
Jakob Stoklund Olesen | f6e0394 | 2011-02-09 21:52:09 +0000 | [diff] [blame] | 1298 | |
Jakob Stoklund Olesen | 56a56eb | 2011-07-24 20:23:50 +0000 | [diff] [blame] | 1299 | // <undef> operands don't really read the register, so it doesn't matter |
| 1300 | // which register we choose. When the use operand is tied to a def, we must |
| 1301 | // use the same register as the def, so just do that always. |
Duncan P. N. Exon Smith | 3ac9cc6 | 2016-02-27 06:40:41 +0000 | [diff] [blame] | 1302 | SlotIndex Idx = LIS.getInstructionIndex(*MI); |
Jakob Stoklund Olesen | 56a56eb | 2011-07-24 20:23:50 +0000 | [diff] [blame] | 1303 | if (MO.isDef() || MO.isUndef()) |
Jakob Stoklund Olesen | 90b5e56 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 1304 | Idx = Idx.getRegSlot(MO.isEarlyClobber()); |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 1305 | |
| 1306 | // Rewrite to the mapped register at Idx. |
| 1307 | unsigned RegIdx = RegAssign.lookup(Idx); |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1308 | LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); |
| 1309 | MO.setReg(LI.reg); |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 1310 | DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' |
| 1311 | << Idx << ':' << RegIdx << '\t' << *MI); |
| 1312 | |
Jakob Stoklund Olesen | c099dde | 2011-03-18 03:06:02 +0000 | [diff] [blame] | 1313 | // Extend liveness to Idx if the instruction reads reg. |
Jakob Stoklund Olesen | 73a9eb9 | 2011-07-24 20:33:23 +0000 | [diff] [blame] | 1314 | if (!ExtendRanges || MO.isUndef()) |
Jakob Stoklund Olesen | c099dde | 2011-03-18 03:06:02 +0000 | [diff] [blame] | 1315 | continue; |
| 1316 | |
| 1317 | // Skip instructions that don't read Reg. |
| 1318 | if (MO.isDef()) { |
| 1319 | if (!MO.getSubReg() && !MO.isEarlyClobber()) |
| 1320 | continue; |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1321 | // We may want to extend a live range for a partial redef, or for a use |
Jakob Stoklund Olesen | c099dde | 2011-03-18 03:06:02 +0000 | [diff] [blame] | 1322 | // tied to an early clobber. |
| 1323 | Idx = Idx.getPrevSlot(); |
| 1324 | if (!Edit->getParent().liveAt(Idx)) |
| 1325 | continue; |
| 1326 | } else |
Jakob Stoklund Olesen | 90b5e56 | 2011-11-13 20:45:27 +0000 | [diff] [blame] | 1327 | Idx = Idx.getRegSlot(true); |
Jakob Stoklund Olesen | c099dde | 2011-03-18 03:06:02 +0000 | [diff] [blame] | 1328 | |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1329 | SlotIndex Next = Idx.getNextSlot(); |
| 1330 | if (LI.hasSubRanges()) { |
| 1331 | // We have to delay extending subranges until we have seen all operands |
| 1332 | // defining the register. This is because a <def,read-undef> operand |
| 1333 | // will create an "undef" point, and we cannot extend any subranges |
| 1334 | // until all of them have been accounted for. |
Krzysztof Parzyszek | 3bf4aec | 2016-09-02 19:48:55 +0000 | [diff] [blame] | 1335 | if (MO.isUse()) |
| 1336 | ExtPoints.push_back(ExtPoint(MO, RegIdx, Next)); |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1337 | } else { |
| 1338 | LiveRangeCalc &LRC = getLRCalc(RegIdx); |
| 1339 | LRC.extend(LI, Next, 0, ArrayRef<SlotIndex>()); |
| 1340 | } |
| 1341 | } |
| 1342 | |
| 1343 | for (ExtPoint &EP : ExtPoints) { |
| 1344 | LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx)); |
| 1345 | assert(LI.hasSubRanges()); |
| 1346 | |
| 1347 | LiveRangeCalc SubLRC; |
| 1348 | unsigned Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg(); |
| 1349 | LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub) |
| 1350 | : MRI.getMaxLaneMaskForVReg(Reg); |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1351 | for (LiveInterval::SubRange &S : LI.subranges()) { |
Krzysztof Parzyszek | 91b5cf8 | 2016-12-15 14:36:06 +0000 | [diff] [blame] | 1352 | if ((S.LaneMask & LM).none()) |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1353 | continue; |
| 1354 | // The problem here can be that the new register may have been created |
| 1355 | // for a partially defined original register. For example: |
| 1356 | // %vreg827:subreg_hireg<def,read-undef> = ... |
| 1357 | // ... |
| 1358 | // %vreg828<def> = COPY %vreg827 |
| 1359 | if (S.empty()) |
| 1360 | continue; |
| 1361 | SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, |
| 1362 | &LIS.getVNInfoAllocator()); |
| 1363 | SmallVector<SlotIndex, 4> Undefs; |
| 1364 | LI.computeSubRangeUndefs(Undefs, S.LaneMask, MRI, *LIS.getSlotIndexes()); |
| 1365 | SubLRC.extend(S, EP.Next, 0, Undefs); |
| 1366 | } |
| 1367 | } |
| 1368 | |
| 1369 | for (unsigned R : *Edit) { |
| 1370 | LiveInterval &LI = LIS.getInterval(R); |
| 1371 | if (!LI.hasSubRanges()) |
| 1372 | continue; |
| 1373 | LI.clear(); |
| 1374 | LI.removeEmptySubRanges(); |
| 1375 | LIS.constructMainRangeFromSubranges(LI); |
Jakob Stoklund Olesen | 959fcc6 | 2010-10-08 23:42:21 +0000 | [diff] [blame] | 1376 | } |
| 1377 | } |
| 1378 | |
Jakob Stoklund Olesen | ea5ebfe | 2011-03-08 22:46:11 +0000 | [diff] [blame] | 1379 | void SplitEditor::deleteRematVictims() { |
| 1380 | SmallVector<MachineInstr*, 8> Dead; |
Jakob Stoklund Olesen | 3550242 | 2011-03-20 19:46:23 +0000 | [diff] [blame] | 1381 | for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ |
Mark Lacey | f9ea885 | 2013-08-14 23:50:04 +0000 | [diff] [blame] | 1382 | LiveInterval *LI = &LIS.getInterval(*I); |
Matthias Braun | 9676195 | 2014-12-10 23:07:54 +0000 | [diff] [blame] | 1383 | for (const LiveRange::Segment &S : LI->segments) { |
Jakob Stoklund Olesen | d8f2405 | 2011-11-13 22:42:13 +0000 | [diff] [blame] | 1384 | // Dead defs end at the dead slot. |
Matthias Braun | 9676195 | 2014-12-10 23:07:54 +0000 | [diff] [blame] | 1385 | if (S.end != S.valno->def.getDeadSlot()) |
Jakob Stoklund Olesen | 3550242 | 2011-03-20 19:46:23 +0000 | [diff] [blame] | 1386 | continue; |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 1387 | if (S.valno->isPHIDef()) |
| 1388 | continue; |
Matthias Braun | 9676195 | 2014-12-10 23:07:54 +0000 | [diff] [blame] | 1389 | MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def); |
Jakob Stoklund Olesen | 3550242 | 2011-03-20 19:46:23 +0000 | [diff] [blame] | 1390 | assert(MI && "Missing instruction for dead def"); |
| 1391 | MI->addRegisterDead(LI->reg, &TRI); |
Jakob Stoklund Olesen | ea5ebfe | 2011-03-08 22:46:11 +0000 | [diff] [blame] | 1392 | |
Jakob Stoklund Olesen | 3550242 | 2011-03-20 19:46:23 +0000 | [diff] [blame] | 1393 | if (!MI->allDefsAreDead()) |
| 1394 | continue; |
Jakob Stoklund Olesen | ea5ebfe | 2011-03-08 22:46:11 +0000 | [diff] [blame] | 1395 | |
Jakob Stoklund Olesen | 3550242 | 2011-03-20 19:46:23 +0000 | [diff] [blame] | 1396 | DEBUG(dbgs() << "All defs dead: " << *MI); |
| 1397 | Dead.push_back(MI); |
| 1398 | } |
Jakob Stoklund Olesen | ea5ebfe | 2011-03-08 22:46:11 +0000 | [diff] [blame] | 1399 | } |
| 1400 | |
| 1401 | if (Dead.empty()) |
| 1402 | return; |
| 1403 | |
Wei Mi | c022370 | 2016-07-08 21:08:09 +0000 | [diff] [blame] | 1404 | Edit->eliminateDeadDefs(Dead, None, &AA); |
Jakob Stoklund Olesen | ea5ebfe | 2011-03-08 22:46:11 +0000 | [diff] [blame] | 1405 | } |
| 1406 | |
Jakob Stoklund Olesen | 6a663b8 | 2011-04-21 18:38:15 +0000 | [diff] [blame] | 1407 | void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 1408 | ++NumFinished; |
Eric Christopher | 2193353 | 2011-02-03 05:40:54 +0000 | [diff] [blame] | 1409 | |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 1410 | // At this point, the live intervals in Edit contain VNInfos corresponding to |
| 1411 | // the inserted copies. |
| 1412 | |
| 1413 | // Add the original defs from the parent interval. |
Matthias Braun | 9676195 | 2014-12-10 23:07:54 +0000 | [diff] [blame] | 1414 | for (const VNInfo *ParentVNI : Edit->getParent().valnos) { |
Jakob Stoklund Olesen | 3295a99 | 2011-02-04 00:59:23 +0000 | [diff] [blame] | 1415 | if (ParentVNI->isUnused()) |
| 1416 | continue; |
Jakob Stoklund Olesen | 8ef91fc | 2011-03-01 23:14:53 +0000 | [diff] [blame] | 1417 | unsigned RegIdx = RegAssign.lookup(ParentVNI->def); |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1418 | defValue(RegIdx, ParentVNI, ParentVNI->def, true); |
Jakob Stoklund Olesen | 32210de | 2011-03-15 21:13:22 +0000 | [diff] [blame] | 1419 | |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 1420 | // Force rematted values to be recomputed everywhere. |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 1421 | // The new live ranges may be truncated. |
Jakob Stoklund Olesen | 815196c | 2011-03-02 23:31:50 +0000 | [diff] [blame] | 1422 | if (Edit->didRematerialize(ParentVNI)) |
| 1423 | for (unsigned i = 0, e = Edit->size(); i != e; ++i) |
Jakob Stoklund Olesen | 5d4277d | 2011-09-13 23:09:04 +0000 | [diff] [blame] | 1424 | forceRecompute(i, ParentVNI); |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 1425 | } |
| 1426 | |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 1427 | // Hoist back-copies to the complement interval when in spill mode. |
| 1428 | switch (SpillMode) { |
| 1429 | case SM_Partition: |
| 1430 | // Leave all back-copies as is. |
| 1431 | break; |
| 1432 | case SM_Size: |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 1433 | case SM_Speed: |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 1434 | // hoistCopies will behave differently between size and speed. |
| 1435 | hoistCopies(); |
Jakob Stoklund Olesen | a25330f | 2011-09-13 22:22:39 +0000 | [diff] [blame] | 1436 | } |
| 1437 | |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1438 | // Transfer the simply mapped values, check if any are skipped. |
| 1439 | bool Skipped = transferValues(); |
Wei Mi | 9a16d65 | 2016-04-13 03:08:27 +0000 | [diff] [blame] | 1440 | |
| 1441 | // Rewrite virtual registers, possibly extending ranges. |
| 1442 | rewriteAssigned(Skipped); |
| 1443 | |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1444 | if (Skipped) |
Jakob Stoklund Olesen | 503b143 | 2011-03-02 23:05:19 +0000 | [diff] [blame] | 1445 | extendPHIKillRanges(); |
| 1446 | else |
| 1447 | ++NumSimple; |
Eric Christopher | ede6267 | 2011-02-03 06:18:29 +0000 | [diff] [blame] | 1448 | |
Jakob Stoklund Olesen | ea5ebfe | 2011-03-08 22:46:11 +0000 | [diff] [blame] | 1449 | // Delete defs that were rematted everywhere. |
Jakob Stoklund Olesen | 1af8b4d | 2011-04-15 17:24:49 +0000 | [diff] [blame] | 1450 | if (Skipped) |
Jakob Stoklund Olesen | ea5ebfe | 2011-03-08 22:46:11 +0000 | [diff] [blame] | 1451 | deleteRematVictims(); |
Jakob Stoklund Olesen | 6f8bd42 | 2010-09-21 22:32:21 +0000 | [diff] [blame] | 1452 | |
Jakob Stoklund Olesen | 0f1677e | 2010-10-07 23:34:34 +0000 | [diff] [blame] | 1453 | // Get rid of unused values and set phi-kill flags. |
Krzysztof Parzyszek | a7ed090 | 2016-08-24 13:37:55 +0000 | [diff] [blame] | 1454 | for (unsigned Reg : *Edit) { |
| 1455 | LiveInterval &LI = LIS.getInterval(Reg); |
| 1456 | LI.removeEmptySubRanges(); |
Mark Lacey | f9ea885 | 2013-08-14 23:50:04 +0000 | [diff] [blame] | 1457 | LI.RenumberValues(); |
| 1458 | } |
Jakob Stoklund Olesen | 6f8bd42 | 2010-09-21 22:32:21 +0000 | [diff] [blame] | 1459 | |
Jakob Stoklund Olesen | 6a663b8 | 2011-04-21 18:38:15 +0000 | [diff] [blame] | 1460 | // Provide a reverse mapping from original indices to Edit ranges. |
| 1461 | if (LRMap) { |
| 1462 | LRMap->clear(); |
| 1463 | for (unsigned i = 0, e = Edit->size(); i != e; ++i) |
| 1464 | LRMap->push_back(i); |
| 1465 | } |
| 1466 | |
Jakob Stoklund Olesen | e4f3317 | 2010-10-26 22:36:09 +0000 | [diff] [blame] | 1467 | // Now check if any registers were separated into multiple components. |
Jakob Stoklund Olesen | b308902 | 2011-01-26 00:50:53 +0000 | [diff] [blame] | 1468 | ConnectedVNInfoEqClasses ConEQ(LIS); |
Jakob Stoklund Olesen | 815196c | 2011-03-02 23:31:50 +0000 | [diff] [blame] | 1469 | for (unsigned i = 0, e = Edit->size(); i != e; ++i) { |
Jakob Stoklund Olesen | e4f3317 | 2010-10-26 22:36:09 +0000 | [diff] [blame] | 1470 | // Don't use iterators, they are invalidated by create() below. |
Matthias Braun | d3dd135 | 2015-09-22 03:44:41 +0000 | [diff] [blame] | 1471 | unsigned VReg = Edit->get(i); |
| 1472 | LiveInterval &LI = LIS.getInterval(VReg); |
| 1473 | SmallVector<LiveInterval*, 8> SplitLIs; |
| 1474 | LIS.splitSeparateComponents(LI, SplitLIs); |
| 1475 | unsigned Original = VRM.getOriginal(VReg); |
| 1476 | for (LiveInterval *SplitLI : SplitLIs) |
| 1477 | VRM.setIsSplitFromReg(SplitLI->reg, Original); |
| 1478 | |
Jakob Stoklund Olesen | 6a663b8 | 2011-04-21 18:38:15 +0000 | [diff] [blame] | 1479 | // The new intervals all map back to i. |
| 1480 | if (LRMap) |
| 1481 | LRMap->resize(Edit->size(), i); |
Jakob Stoklund Olesen | e4f3317 | 2010-10-26 22:36:09 +0000 | [diff] [blame] | 1482 | } |
| 1483 | |
Jakob Stoklund Olesen | 284c2db | 2010-08-10 17:07:22 +0000 | [diff] [blame] | 1484 | // Calculate spill weight and allocation hints for new intervals. |
Benjamin Kramer | e2a1d89 | 2013-06-17 19:00:36 +0000 | [diff] [blame] | 1485 | Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops, MBFI); |
Jakob Stoklund Olesen | 6a663b8 | 2011-04-21 18:38:15 +0000 | [diff] [blame] | 1486 | |
| 1487 | assert(!LRMap || LRMap->size() == Edit->size()); |
Jakob Stoklund Olesen | c698417 | 2010-07-26 23:44:11 +0000 | [diff] [blame] | 1488 | } |
| 1489 | |
| 1490 | |
Jakob Stoklund Olesen | 36d12c6 | 2010-07-20 15:41:07 +0000 | [diff] [blame] | 1491 | //===----------------------------------------------------------------------===// |
Jakob Stoklund Olesen | 622848b | 2010-08-12 17:07:14 +0000 | [diff] [blame] | 1492 | // Single Block Splitting |
| 1493 | //===----------------------------------------------------------------------===// |
| 1494 | |
Jakob Stoklund Olesen | 8627ea9 | 2011-08-05 22:20:45 +0000 | [diff] [blame] | 1495 | bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI, |
| 1496 | bool SingleInstrs) const { |
| 1497 | // Always split for multiple instructions. |
| 1498 | if (!BI.isOneInstr()) |
| 1499 | return true; |
| 1500 | // Don't split for single instructions unless explicitly requested. |
| 1501 | if (!SingleInstrs) |
| 1502 | return false; |
| 1503 | // Splitting a live-through range always makes progress. |
| 1504 | if (BI.LiveIn && BI.LiveOut) |
| 1505 | return true; |
| 1506 | // No point in isolating a copy. It has no register class constraints. |
| 1507 | if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike()) |
| 1508 | return false; |
| 1509 | // Finally, don't isolate an end point that was created by earlier splits. |
| 1510 | return isOriginalEndpoint(BI.FirstInstr); |
| 1511 | } |
| 1512 | |
Jakob Stoklund Olesen | c70b697 | 2011-04-12 19:32:53 +0000 | [diff] [blame] | 1513 | void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { |
| 1514 | openIntv(); |
| 1515 | SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber()); |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1516 | SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr, |
Jakob Stoklund Olesen | c70b697 | 2011-04-12 19:32:53 +0000 | [diff] [blame] | 1517 | LastSplitPoint)); |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1518 | if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) { |
| 1519 | useIntv(SegStart, leaveIntvAfter(BI.LastInstr)); |
Jakob Stoklund Olesen | c70b697 | 2011-04-12 19:32:53 +0000 | [diff] [blame] | 1520 | } else { |
| 1521 | // The last use is after the last valid split point. |
| 1522 | SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); |
| 1523 | useIntv(SegStart, SegStop); |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1524 | overlapIntv(SegStop, BI.LastInstr); |
Jakob Stoklund Olesen | c70b697 | 2011-04-12 19:32:53 +0000 | [diff] [blame] | 1525 | } |
Jakob Stoklund Olesen | c70b697 | 2011-04-12 19:32:53 +0000 | [diff] [blame] | 1526 | } |
| 1527 | |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1528 | |
| 1529 | //===----------------------------------------------------------------------===// |
| 1530 | // Global Live Range Splitting Support |
| 1531 | //===----------------------------------------------------------------------===// |
| 1532 | |
| 1533 | // These methods support a method of global live range splitting that uses a |
| 1534 | // global algorithm to decide intervals for CFG edges. They will insert split |
| 1535 | // points and color intervals in basic blocks while avoiding interference. |
| 1536 | // |
| 1537 | // Note that splitSingleBlock is also useful for blocks where both CFG edges |
| 1538 | // are on the stack. |
| 1539 | |
| 1540 | void SplitEditor::splitLiveThroughBlock(unsigned MBBNum, |
| 1541 | unsigned IntvIn, SlotIndex LeaveBefore, |
| 1542 | unsigned IntvOut, SlotIndex EnterAfter){ |
| 1543 | SlotIndex Start, Stop; |
Benjamin Kramer | d6f1f84 | 2014-03-02 13:30:33 +0000 | [diff] [blame] | 1544 | std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1545 | |
| 1546 | DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop |
| 1547 | << ") intf " << LeaveBefore << '-' << EnterAfter |
| 1548 | << ", live-through " << IntvIn << " -> " << IntvOut); |
| 1549 | |
| 1550 | assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks"); |
| 1551 | |
Jakob Stoklund Olesen | f500cce | 2011-07-23 03:32:26 +0000 | [diff] [blame] | 1552 | assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block"); |
| 1553 | assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf"); |
| 1554 | assert((!EnterAfter || EnterAfter >= Start) && "Interference before block"); |
| 1555 | |
| 1556 | MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum); |
| 1557 | |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1558 | if (!IntvOut) { |
| 1559 | DEBUG(dbgs() << ", spill on entry.\n"); |
| 1560 | // |
| 1561 | // <<<<<<<<< Possible LeaveBefore interference. |
| 1562 | // |-----------| Live through. |
| 1563 | // -____________ Spill on entry. |
| 1564 | // |
| 1565 | selectIntv(IntvIn); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1566 | SlotIndex Idx = leaveIntvAtTop(*MBB); |
| 1567 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); |
| 1568 | (void)Idx; |
| 1569 | return; |
| 1570 | } |
| 1571 | |
| 1572 | if (!IntvIn) { |
| 1573 | DEBUG(dbgs() << ", reload on exit.\n"); |
| 1574 | // |
| 1575 | // >>>>>>> Possible EnterAfter interference. |
| 1576 | // |-----------| Live through. |
| 1577 | // ___________-- Reload on exit. |
| 1578 | // |
| 1579 | selectIntv(IntvOut); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1580 | SlotIndex Idx = enterIntvAtEnd(*MBB); |
| 1581 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); |
| 1582 | (void)Idx; |
| 1583 | return; |
| 1584 | } |
| 1585 | |
| 1586 | if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) { |
| 1587 | DEBUG(dbgs() << ", straight through.\n"); |
| 1588 | // |
| 1589 | // |-----------| Live through. |
| 1590 | // ------------- Straight through, same intv, no interference. |
| 1591 | // |
| 1592 | selectIntv(IntvOut); |
| 1593 | useIntv(Start, Stop); |
| 1594 | return; |
| 1595 | } |
| 1596 | |
| 1597 | // We cannot legally insert splits after LSP. |
| 1598 | SlotIndex LSP = SA.getLastSplitPoint(MBBNum); |
Jakob Stoklund Olesen | f500cce | 2011-07-23 03:32:26 +0000 | [diff] [blame] | 1599 | assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf"); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1600 | |
| 1601 | if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter || |
| 1602 | LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) { |
| 1603 | DEBUG(dbgs() << ", switch avoiding interference.\n"); |
| 1604 | // |
| 1605 | // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. |
| 1606 | // |-----------| Live through. |
| 1607 | // ------======= Switch intervals between interference. |
| 1608 | // |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1609 | selectIntv(IntvOut); |
Jakob Stoklund Olesen | f500cce | 2011-07-23 03:32:26 +0000 | [diff] [blame] | 1610 | SlotIndex Idx; |
| 1611 | if (LeaveBefore && LeaveBefore < LSP) { |
| 1612 | Idx = enterIntvBefore(LeaveBefore); |
| 1613 | useIntv(Idx, Stop); |
| 1614 | } else { |
| 1615 | Idx = enterIntvAtEnd(*MBB); |
| 1616 | } |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1617 | selectIntv(IntvIn); |
| 1618 | useIntv(Start, Idx); |
| 1619 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); |
| 1620 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); |
| 1621 | return; |
| 1622 | } |
| 1623 | |
| 1624 | DEBUG(dbgs() << ", create local intv for interference.\n"); |
| 1625 | // |
| 1626 | // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference. |
| 1627 | // |-----------| Live through. |
| 1628 | // ==---------== Switch intervals before/after interference. |
| 1629 | // |
| 1630 | assert(LeaveBefore <= EnterAfter && "Missed case"); |
| 1631 | |
| 1632 | selectIntv(IntvOut); |
| 1633 | SlotIndex Idx = enterIntvAfter(EnterAfter); |
| 1634 | useIntv(Idx, Stop); |
| 1635 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); |
| 1636 | |
| 1637 | selectIntv(IntvIn); |
| 1638 | Idx = leaveIntvBefore(LeaveBefore); |
| 1639 | useIntv(Start, Idx); |
| 1640 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); |
| 1641 | } |
| 1642 | |
| 1643 | |
| 1644 | void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, |
| 1645 | unsigned IntvIn, SlotIndex LeaveBefore) { |
| 1646 | SlotIndex Start, Stop; |
Benjamin Kramer | d6f1f84 | 2014-03-02 13:30:33 +0000 | [diff] [blame] | 1647 | std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1648 | |
| 1649 | DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1650 | << "), uses " << BI.FirstInstr << '-' << BI.LastInstr |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1651 | << ", reg-in " << IntvIn << ", leave before " << LeaveBefore |
| 1652 | << (BI.LiveOut ? ", stack-out" : ", killed in block")); |
| 1653 | |
| 1654 | assert(IntvIn && "Must have register in"); |
| 1655 | assert(BI.LiveIn && "Must be live-in"); |
| 1656 | assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference"); |
| 1657 | |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1658 | if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) { |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1659 | DEBUG(dbgs() << " before interference.\n"); |
| 1660 | // |
| 1661 | // <<< Interference after kill. |
| 1662 | // |---o---x | Killed in block. |
| 1663 | // ========= Use IntvIn everywhere. |
| 1664 | // |
| 1665 | selectIntv(IntvIn); |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1666 | useIntv(Start, BI.LastInstr); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1667 | return; |
| 1668 | } |
| 1669 | |
| 1670 | SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); |
| 1671 | |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1672 | if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) { |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1673 | // |
| 1674 | // <<< Possible interference after last use. |
| 1675 | // |---o---o---| Live-out on stack. |
| 1676 | // =========____ Leave IntvIn after last use. |
| 1677 | // |
| 1678 | // < Interference after last use. |
| 1679 | // |---o---o--o| Live-out on stack, late last use. |
| 1680 | // ============ Copy to stack after LSP, overlap IntvIn. |
| 1681 | // \_____ Stack interval is live-out. |
| 1682 | // |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1683 | if (BI.LastInstr < LSP) { |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1684 | DEBUG(dbgs() << ", spill after last use before interference.\n"); |
| 1685 | selectIntv(IntvIn); |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1686 | SlotIndex Idx = leaveIntvAfter(BI.LastInstr); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1687 | useIntv(Start, Idx); |
| 1688 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); |
| 1689 | } else { |
| 1690 | DEBUG(dbgs() << ", spill before last split point.\n"); |
| 1691 | selectIntv(IntvIn); |
Jakob Stoklund Olesen | 37e3a13 | 2011-07-16 00:13:30 +0000 | [diff] [blame] | 1692 | SlotIndex Idx = leaveIntvBefore(LSP); |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1693 | overlapIntv(Idx, BI.LastInstr); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1694 | useIntv(Start, Idx); |
| 1695 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference"); |
| 1696 | } |
| 1697 | return; |
| 1698 | } |
| 1699 | |
| 1700 | // The interference is overlapping somewhere we wanted to use IntvIn. That |
| 1701 | // means we need to create a local interval that can be allocated a |
| 1702 | // different register. |
| 1703 | unsigned LocalIntv = openIntv(); |
Matt Beaumont-Gay | 26909d8 | 2011-07-16 04:18:47 +0000 | [diff] [blame] | 1704 | (void)LocalIntv; |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1705 | DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n"); |
| 1706 | |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1707 | if (!BI.LiveOut || BI.LastInstr < LSP) { |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1708 | // |
| 1709 | // <<<<<<< Interference overlapping uses. |
| 1710 | // |---o---o---| Live-out on stack. |
| 1711 | // =====----____ Leave IntvIn before interference, then spill. |
| 1712 | // |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1713 | SlotIndex To = leaveIntvAfter(BI.LastInstr); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1714 | SlotIndex From = enterIntvBefore(LeaveBefore); |
| 1715 | useIntv(From, To); |
| 1716 | selectIntv(IntvIn); |
| 1717 | useIntv(Start, From); |
| 1718 | assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); |
| 1719 | return; |
| 1720 | } |
| 1721 | |
| 1722 | // <<<<<<< Interference overlapping uses. |
| 1723 | // |---o---o--o| Live-out on stack, late last use. |
| 1724 | // =====------- Copy to stack before LSP, overlap LocalIntv. |
| 1725 | // \_____ Stack interval is live-out. |
| 1726 | // |
| 1727 | SlotIndex To = leaveIntvBefore(LSP); |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1728 | overlapIntv(To, BI.LastInstr); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1729 | SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore)); |
| 1730 | useIntv(From, To); |
| 1731 | selectIntv(IntvIn); |
| 1732 | useIntv(Start, From); |
| 1733 | assert((!LeaveBefore || From <= LeaveBefore) && "Interference"); |
| 1734 | } |
| 1735 | |
| 1736 | void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, |
| 1737 | unsigned IntvOut, SlotIndex EnterAfter) { |
| 1738 | SlotIndex Start, Stop; |
Benjamin Kramer | d6f1f84 | 2014-03-02 13:30:33 +0000 | [diff] [blame] | 1739 | std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1740 | |
| 1741 | DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1742 | << "), uses " << BI.FirstInstr << '-' << BI.LastInstr |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1743 | << ", reg-out " << IntvOut << ", enter after " << EnterAfter |
| 1744 | << (BI.LiveIn ? ", stack-in" : ", defined in block")); |
| 1745 | |
| 1746 | SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber()); |
| 1747 | |
| 1748 | assert(IntvOut && "Must have register out"); |
| 1749 | assert(BI.LiveOut && "Must be live-out"); |
| 1750 | assert((!EnterAfter || EnterAfter < LSP) && "Bad interference"); |
| 1751 | |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1752 | if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) { |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1753 | DEBUG(dbgs() << " after interference.\n"); |
| 1754 | // |
| 1755 | // >>>> Interference before def. |
| 1756 | // | o---o---| Defined in block. |
| 1757 | // ========= Use IntvOut everywhere. |
| 1758 | // |
| 1759 | selectIntv(IntvOut); |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1760 | useIntv(BI.FirstInstr, Stop); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1761 | return; |
| 1762 | } |
| 1763 | |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1764 | if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) { |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1765 | DEBUG(dbgs() << ", reload after interference.\n"); |
| 1766 | // |
| 1767 | // >>>> Interference before def. |
| 1768 | // |---o---o---| Live-through, stack-in. |
| 1769 | // ____========= Enter IntvOut before first use. |
| 1770 | // |
| 1771 | selectIntv(IntvOut); |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1772 | SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr)); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1773 | useIntv(Idx, Stop); |
| 1774 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); |
| 1775 | return; |
| 1776 | } |
| 1777 | |
| 1778 | // The interference is overlapping somewhere we wanted to use IntvOut. That |
| 1779 | // means we need to create a local interval that can be allocated a |
| 1780 | // different register. |
| 1781 | DEBUG(dbgs() << ", interference overlaps uses.\n"); |
| 1782 | // |
| 1783 | // >>>>>>> Interference overlapping uses. |
| 1784 | // |---o---o---| Live-through, stack-in. |
| 1785 | // ____---====== Create local interval for interference range. |
| 1786 | // |
| 1787 | selectIntv(IntvOut); |
| 1788 | SlotIndex Idx = enterIntvAfter(EnterAfter); |
| 1789 | useIntv(Idx, Stop); |
| 1790 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference"); |
| 1791 | |
| 1792 | openIntv(); |
Jakob Stoklund Olesen | 43859a6 | 2011-08-02 22:54:14 +0000 | [diff] [blame] | 1793 | SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr)); |
Jakob Stoklund Olesen | 795da1c | 2011-07-15 21:47:57 +0000 | [diff] [blame] | 1794 | useIntv(From, Idx); |
| 1795 | } |