Mercurial > hg > CbC > CbC_llvm

comparison lib/CodeGen/LiveIntervalAnalysis.cpp @ 121:803732b1fca8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 5.0
author kono
date Fri, 27 Oct 2017 17:07:41 +0900
parents 1172e4bd9c6f
children
comparison
equal deleted inserted replaced
120:1172e4bd9c6f 121:803732b1fca8
1 //===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 1 //===- LiveIntervalAnalysis.cpp - Live Interval Analysis ------------------===//
2 // 2 //
3 // The LLVM Compiler Infrastructure 3 // The LLVM Compiler Infrastructure
4 // 4 //
5 // This file is distributed under the University of Illinois Open Source 5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details. 6 // License. See LICENSE.TXT for details.
7 // 7 //
8 //===----------------------------------------------------------------------===// 8 //===----------------------------------------------------------------------===//
9 // 9 //
10 // This file implements the LiveInterval analysis pass which is used 10 /// \file This file implements the LiveInterval analysis pass which is used
11 // by the Linear Scan Register allocator. This pass linearizes the 11 /// by the Linear Scan Register allocator. This pass linearizes the
12 // basic blocks of the function in DFS order and computes live intervals for 12 /// basic blocks of the function in DFS order and computes live intervals for
13 // each virtual and physical register. 13 /// each virtual and physical register.
14 // 14 //
15 //===----------------------------------------------------------------------===// 15 //===----------------------------------------------------------------------===//
16 16
17 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 17 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
18 #include "LiveRangeCalc.h" 18 #include "LiveRangeCalc.h"
19 #include "llvm/ADT/STLExtras.h" 19 #include "llvm/ADT/ArrayRef.h"
20 #include "llvm/ADT/DepthFirstIterator.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/iterator_range.h"
20 #include "llvm/Analysis/AliasAnalysis.h" 24 #include "llvm/Analysis/AliasAnalysis.h"
25 #include "llvm/CodeGen/LiveInterval.h"
21 #include "llvm/CodeGen/LiveVariables.h" 26 #include "llvm/CodeGen/LiveVariables.h"
27 #include "llvm/CodeGen/MachineBasicBlock.h"
22 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 28 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
23 #include "llvm/CodeGen/MachineDominators.h" 29 #include "llvm/CodeGen/MachineDominators.h"
30 #include "llvm/CodeGen/MachineFunction.h"
24 #include "llvm/CodeGen/MachineInstr.h" 31 #include "llvm/CodeGen/MachineInstr.h"
32 #include "llvm/CodeGen/MachineInstrBundle.h"
33 #include "llvm/CodeGen/MachineOperand.h"
25 #include "llvm/CodeGen/MachineRegisterInfo.h" 34 #include "llvm/CodeGen/MachineRegisterInfo.h"
26 #include "llvm/CodeGen/Passes.h" 35 #include "llvm/CodeGen/Passes.h"
36 #include "llvm/CodeGen/SlotIndexes.h"
27 #include "llvm/CodeGen/VirtRegMap.h" 37 #include "llvm/CodeGen/VirtRegMap.h"
28 #include "llvm/IR/Value.h" 38 #include "llvm/MC/LaneBitmask.h"
39 #include "llvm/MC/MCRegisterInfo.h"
40 #include "llvm/Pass.h"
29 #include "llvm/Support/BlockFrequency.h" 41 #include "llvm/Support/BlockFrequency.h"
30 #include "llvm/Support/CommandLine.h" 42 #include "llvm/Support/CommandLine.h"
43 #include "llvm/Support/Compiler.h"
31 #include "llvm/Support/Debug.h" 44 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/ErrorHandling.h" 45 #include "llvm/Support/MathExtras.h"
33 #include "llvm/Support/raw_ostream.h" 46 #include "llvm/Support/raw_ostream.h"
34 #include "llvm/Target/TargetInstrInfo.h"
35 #include "llvm/Target/TargetRegisterInfo.h" 47 #include "llvm/Target/TargetRegisterInfo.h"
36 #include "llvm/Target/TargetSubtargetInfo.h" 48 #include "llvm/Target/TargetSubtargetInfo.h"
37 #include <algorithm> 49 #include <algorithm>
38 #include <cmath> 50 #include <cassert>
51 #include <cstdint>
52 #include <iterator>
53 #include <tuple>
54 #include <utility>
55
39 using namespace llvm; 56 using namespace llvm;
40 57
41 #define DEBUG_TYPE "regalloc" 58 #define DEBUG_TYPE "regalloc"
42 59
43 char LiveIntervals::ID = 0; 60 char LiveIntervals::ID = 0;
57 #else 74 #else
58 static bool EnablePrecomputePhysRegs = false; 75 static bool EnablePrecomputePhysRegs = false;
59 #endif // NDEBUG 76 #endif // NDEBUG
60 77
61 namespace llvm { 78 namespace llvm {
79
62 cl::opt<bool> UseSegmentSetForPhysRegs( 80 cl::opt<bool> UseSegmentSetForPhysRegs(
63 "use-segment-set-for-physregs", cl::Hidden, cl::init(true), 81 "use-segment-set-for-physregs", cl::Hidden, cl::init(true),
64 cl::desc( 82 cl::desc(
65 "Use segment set for the computation of the live ranges of physregs.")); 83 "Use segment set for the computation of the live ranges of physregs."));
66 } 84
85 } // end namespace llvm
67 86
68 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 87 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
69 AU.setPreservesCFG(); 88 AU.setPreservesCFG();
70 AU.addRequired<AAResultsWrapperPass>(); 89 AU.addRequired<AAResultsWrapperPass>();
71 AU.addPreserved<AAResultsWrapperPass>(); 90 AU.addPreserved<AAResultsWrapperPass>();
76 AU.addPreserved<SlotIndexes>(); 95 AU.addPreserved<SlotIndexes>();
77 AU.addRequiredTransitive<SlotIndexes>(); 96 AU.addRequiredTransitive<SlotIndexes>();
78 MachineFunctionPass::getAnalysisUsage(AU); 97 MachineFunctionPass::getAnalysisUsage(AU);
79 } 98 }
80 99
81 LiveIntervals::LiveIntervals() : MachineFunctionPass(ID), 100 LiveIntervals::LiveIntervals() : MachineFunctionPass(ID) {
82 DomTree(nullptr), LRCalc(nullptr) {
83 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 101 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
84 } 102 }
85 103
86 LiveIntervals::~LiveIntervals() { 104 LiveIntervals::~LiveIntervals() {
87 delete LRCalc; 105 delete LRCalc;
94 VirtRegIntervals.clear(); 112 VirtRegIntervals.clear();
95 RegMaskSlots.clear(); 113 RegMaskSlots.clear();
96 RegMaskBits.clear(); 114 RegMaskBits.clear();
97 RegMaskBlocks.clear(); 115 RegMaskBlocks.clear();
98 116
99 for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i) 117 for (LiveRange *LR : RegUnitRanges)
100 delete RegUnitRanges[i]; 118 delete LR;
101 RegUnitRanges.clear(); 119 RegUnitRanges.clear();
102 120
103 // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. 121 // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
104 VNInfoAllocator.Reset(); 122 VNInfoAllocator.Reset();
105 } 123 }
106 124
107 /// runOnMachineFunction - calculates LiveIntervals
108 ///
109 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 125 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
110 MF = &fn; 126 MF = &fn;
111 MRI = &MF->getRegInfo(); 127 MRI = &MF->getRegInfo();
112 TRI = MF->getSubtarget().getRegisterInfo(); 128 TRI = MF->getSubtarget().getRegisterInfo();
113 TII = MF->getSubtarget().getInstrInfo(); 129 TII = MF->getSubtarget().getInstrInfo();
133 } 149 }
134 DEBUG(dump()); 150 DEBUG(dump());
135 return true; 151 return true;
136 } 152 }
137 153
138 /// print - Implement the dump method.
139 void LiveIntervals::print(raw_ostream &OS, const Module* ) const { 154 void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
140 OS << "********** INTERVALS **********\n"; 155 OS << "********** INTERVALS **********\n";
141 156
142 // Dump the regunits. 157 // Dump the regunits.
143 for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i) 158 for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit)
144 if (LiveRange *LR = RegUnitRanges[i]) 159 if (LiveRange *LR = RegUnitRanges[Unit])
145 OS << PrintRegUnit(i, TRI) << ' ' << *LR << '\n'; 160 OS << PrintRegUnit(Unit, TRI) << ' ' << *LR << '\n';
146 161
147 // Dump the virtregs. 162 // Dump the virtregs.
148 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 163 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
149 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 164 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
150 if (hasInterval(Reg)) 165 if (hasInterval(Reg))
151 OS << getInterval(Reg) << '\n'; 166 OS << getInterval(Reg) << '\n';
152 } 167 }
153 168
154 OS << "RegMasks:"; 169 OS << "RegMasks:";
155 for (unsigned i = 0, e = RegMaskSlots.size(); i != e; ++i) 170 for (SlotIndex Idx : RegMaskSlots)
156 OS << ' ' << RegMaskSlots[i]; 171 OS << ' ' << Idx;
157 OS << '\n'; 172 OS << '\n';
158 173
159 printInstrs(OS); 174 printInstrs(OS);
160 } 175 }
161 176
163 OS << "********** MACHINEINSTRS **********\n"; 178 OS << "********** MACHINEINSTRS **********\n";
164 MF->print(OS, Indexes); 179 MF->print(OS, Indexes);
165 } 180 }
166 181
167 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 182 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
168 void LiveIntervals::dumpInstrs() const { 183 LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const {
169 printInstrs(dbgs()); 184 printInstrs(dbgs());
170 } 185 }
171 #endif 186 #endif
172 187
173 LiveInterval* LiveIntervals::createInterval(unsigned reg) { 188 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
174 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? 189 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? huge_valf : 0.0F;
175 llvm::huge_valf : 0.0F;
176 return new LiveInterval(reg, Weight); 190 return new LiveInterval(reg, Weight);
177 } 191 }
178 192
179 193 /// Compute the live interval of a virtual register, based on defs and uses.
180 /// computeVirtRegInterval - Compute the live interval of a virtual register,
181 /// based on defs and uses.
182 void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { 194 void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {
183 assert(LRCalc && "LRCalc not initialized."); 195 assert(LRCalc && "LRCalc not initialized.");
184 assert(LI.empty() && "Should only compute empty intervals."); 196 assert(LI.empty() && "Should only compute empty intervals.");
185 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 197 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
186 LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg)); 198 LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg));
198 210
199 void LiveIntervals::computeRegMasks() { 211 void LiveIntervals::computeRegMasks() {
200 RegMaskBlocks.resize(MF->getNumBlockIDs()); 212 RegMaskBlocks.resize(MF->getNumBlockIDs());
201 213
202 // Find all instructions with regmask operands. 214 // Find all instructions with regmask operands.
203 for (MachineBasicBlock &MBB : *MF) { 215 for (const MachineBasicBlock &MBB : *MF) {
204 std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()]; 216 std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()];
205 RMB.first = RegMaskSlots.size(); 217 RMB.first = RegMaskSlots.size();
206 218
207 // Some block starts, such as EH funclets, create masks. 219 // Some block starts, such as EH funclets, create masks.
208 if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) { 220 if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) {
209 RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB)); 221 RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));
210 RegMaskBits.push_back(Mask); 222 RegMaskBits.push_back(Mask);
211 } 223 }
212 224
213 for (MachineInstr &MI : MBB) { 225 for (const MachineInstr &MI : MBB) {
214 for (const MachineOperand &MO : MI.operands()) { 226 for (const MachineOperand &MO : MI.operands()) {
215 if (!MO.isRegMask()) 227 if (!MO.isRegMask())
216 continue; 228 continue;
217 RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot()); 229 RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
218 RegMaskBits.push_back(MO.getRegMask()); 230 RegMaskBits.push_back(MO.getRegMask());
243 // pointers entering landing pads. Certain instructions require values to be 255 // pointers entering landing pads. Certain instructions require values to be
244 // present in specific registers. That is also represented through fixed 256 // present in specific registers. That is also represented through fixed
245 // interference. 257 // interference.
246 // 258 //
247 259
248 /// computeRegUnitInterval - Compute the live range of a register unit, based 260 /// Compute the live range of a register unit, based on the uses and defs of
249 /// on the uses and defs of aliasing registers. The range should be empty, 261 /// aliasing registers. The range should be empty, or contain only dead
250 /// or contain only dead phi-defs from ABI blocks. 262 /// phi-defs from ABI blocks.
251 void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { 263 void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) {
252 assert(LRCalc && "LRCalc not initialized."); 264 assert(LRCalc && "LRCalc not initialized.");
253 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 265 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
254 266
255 // The physregs aliasing Unit are the roots and their super-registers. 267 // The physregs aliasing Unit are the roots and their super-registers.
256 // Create all values as dead defs before extending to uses. Note that roots 268 // Create all values as dead defs before extending to uses. Note that roots
257 // may share super-registers. That's OK because createDeadDefs() is 269 // may share super-registers. That's OK because createDeadDefs() is
258 // idempotent. It is very rare for a register unit to have multiple roots, so 270 // idempotent. It is very rare for a register unit to have multiple roots, so
259 // uniquing super-registers is probably not worthwhile. 271 // uniquing super-registers is probably not worthwhile.
260 for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { 272 bool IsReserved = false;
261 for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); 273 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
262 Supers.isValid(); ++Supers) { 274 bool IsRootReserved = true;
263 if (!MRI->reg_empty(*Supers)) 275 for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
264 LRCalc->createDeadDefs(LR, *Supers); 276 Super.isValid(); ++Super) {
265 } 277 unsigned Reg = *Super;
266 } 278 if (!MRI->reg_empty(Reg))
279 LRCalc->createDeadDefs(LR, Reg);
280 // A register unit is considered reserved if all its roots and all their
281 // super registers are reserved.
282 if (!MRI->isReserved(Reg))
283 IsRootReserved = false;
284 }
285 IsReserved |= IsRootReserved;
286 }
287 assert(IsReserved == MRI->isReservedRegUnit(Unit) &&
288 "reserved computation mismatch");
267 289
268 // Now extend LR to reach all uses. 290 // Now extend LR to reach all uses.
269 // Ignore uses of reserved registers. We only track defs of those. 291 // Ignore uses of reserved registers. We only track defs of those.
270 for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { 292 if (!IsReserved) {
271 for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); 293 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
272 Supers.isValid(); ++Supers) { 294 for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
273 unsigned Reg = *Supers; 295 Super.isValid(); ++Super) {
274 if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg)) 296 unsigned Reg = *Super;
275 LRCalc->extendToUses(LR, Reg); 297 if (!MRI->reg_empty(Reg))
298 LRCalc->extendToUses(LR, Reg);
299 }
276 } 300 }
277 } 301 }
278 302
279 // Flush the segment set to the segment vector. 303 // Flush the segment set to the segment vector.
280 if (UseSegmentSetForPhysRegs) 304 if (UseSegmentSetForPhysRegs)
281 LR.flushSegmentSet(); 305 LR.flushSegmentSet();
282 } 306 }
283 307
284 308 /// Precompute the live ranges of any register units that are live-in to an ABI
285 /// computeLiveInRegUnits - Precompute the live ranges of any register units 309 /// block somewhere. Register values can appear without a corresponding def when
286 /// that are live-in to an ABI block somewhere. Register values can appear 310 /// entering the entry block or a landing pad.
287 /// without a corresponding def when entering the entry block or a landing pad.
288 ///
289 void LiveIntervals::computeLiveInRegUnits() { 311 void LiveIntervals::computeLiveInRegUnits() {
290 RegUnitRanges.resize(TRI->getNumRegUnits()); 312 RegUnitRanges.resize(TRI->getNumRegUnits());
291 DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n"); 313 DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
292 314
293 // Keep track of the live range sets allocated. 315 // Keep track of the live range sets allocated.
294 SmallVector<unsigned, 8> NewRanges; 316 SmallVector<unsigned, 8> NewRanges;
295 317
296 // Check all basic blocks for live-ins. 318 // Check all basic blocks for live-ins.
297 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 319 for (const MachineBasicBlock &MBB : *MF) {
298 MFI != MFE; ++MFI) {
299 const MachineBasicBlock *MBB = &*MFI;
300
301 // We only care about ABI blocks: Entry + landing pads. 320 // We only care about ABI blocks: Entry + landing pads.
302 if ((MFI != MF->begin() && !MBB->isEHPad()) || MBB->livein_empty()) 321 if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty())
303 continue; 322 continue;
304 323
305 // Create phi-defs at Begin for all live-in registers. 324 // Create phi-defs at Begin for all live-in registers.
306 SlotIndex Begin = Indexes->getMBBStartIdx(MBB); 325 SlotIndex Begin = Indexes->getMBBStartIdx(&MBB);
307 DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber()); 326 DEBUG(dbgs() << Begin << "\tBB#" << MBB.getNumber());
308 for (const auto &LI : MBB->liveins()) { 327 for (const auto &LI : MBB.liveins()) {
309 for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) { 328 for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) {
310 unsigned Unit = *Units; 329 unsigned Unit = *Units;
311 LiveRange *LR = RegUnitRanges[Unit]; 330 LiveRange *LR = RegUnitRanges[Unit];
312 if (!LR) { 331 if (!LR) {
313 // Use segment set to speed-up initial computation of the live range. 332 // Use segment set to speed-up initial computation of the live range.
322 DEBUG(dbgs() << '\n'); 341 DEBUG(dbgs() << '\n');
323 } 342 }
324 DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n"); 343 DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
325 344
326 // Compute the 'normal' part of the ranges. 345 // Compute the 'normal' part of the ranges.
327 for (unsigned i = 0, e = NewRanges.size(); i != e; ++i) { 346 for (unsigned Unit : NewRanges)
328 unsigned Unit = NewRanges[i];
329 computeRegUnitRange(*RegUnitRanges[Unit], Unit); 347 computeRegUnitRange(*RegUnitRanges[Unit], Unit);
330 } 348 }
331 }
332
333 349
334 static void createSegmentsForValues(LiveRange &LR, 350 static void createSegmentsForValues(LiveRange &LR,
335 iterator_range<LiveInterval::vni_iterator> VNIs) { 351 iterator_range<LiveInterval::vni_iterator> VNIs) {
336 for (auto VNI : VNIs) { 352 for (VNInfo *VNI : VNIs) {
337 if (VNI->isUnused()) 353 if (VNI->isUnused())
338 continue; 354 continue;
339 SlotIndex Def = VNI->def; 355 SlotIndex Def = VNI->def;
340 LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI)); 356 LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
341 } 357 }
342 } 358 }
343 359
344 typedef SmallVector<std::pair<SlotIndex, VNInfo*>, 16> ShrinkToUsesWorkList; 360 using ShrinkToUsesWorkList = SmallVector<std::pair<SlotIndex, VNInfo*>, 16>;
345 361
346 static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes, 362 static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
347 ShrinkToUsesWorkList &WorkList, 363 ShrinkToUsesWorkList &WorkList,
348 const LiveRange &OldRange) { 364 const LiveRange &OldRange) {
349 // Keep track of the PHIs that are in use. 365 // Keep track of the PHIs that are in use.
350 SmallPtrSet<VNInfo*, 8> UsedPHIs; 366 SmallPtrSet<VNInfo*, 8> UsedPHIs;
351 // Blocks that have already been added to WorkList as live-out. 367 // Blocks that have already been added to WorkList as live-out.
352 SmallPtrSet<MachineBasicBlock*, 16> LiveOut; 368 SmallPtrSet<const MachineBasicBlock*, 16> LiveOut;
353 369
354 // Extend intervals to reach all uses in WorkList. 370 // Extend intervals to reach all uses in WorkList.
355 while (!WorkList.empty()) { 371 while (!WorkList.empty()) {
356 SlotIndex Idx = WorkList.back().first; 372 SlotIndex Idx = WorkList.back().first;
357 VNInfo *VNI = WorkList.back().second; 373 VNInfo *VNI = WorkList.back().second;
366 // Is this a PHIDef we haven't seen before? 382 // Is this a PHIDef we haven't seen before?
367 if (!VNI->isPHIDef() || VNI->def != BlockStart || 383 if (!VNI->isPHIDef() || VNI->def != BlockStart ||
368 !UsedPHIs.insert(VNI).second) 384 !UsedPHIs.insert(VNI).second)
369 continue; 385 continue;
370 // The PHI is live, make sure the predecessors are live-out. 386 // The PHI is live, make sure the predecessors are live-out.
371 for (auto &Pred : MBB->predecessors()) { 387 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
372 if (!LiveOut.insert(Pred).second) 388 if (!LiveOut.insert(Pred).second)
373 continue; 389 continue;
374 SlotIndex Stop = Indexes.getMBBEndIdx(Pred); 390 SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
375 // A predecessor is not required to have a live-out value for a PHI. 391 // A predecessor is not required to have a live-out value for a PHI.
376 if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop)) 392 if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
382 // VNI is live-in to MBB. 398 // VNI is live-in to MBB.
383 DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); 399 DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
384 LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI)); 400 LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
385 401
386 // Make sure VNI is live-out from the predecessors. 402 // Make sure VNI is live-out from the predecessors.
387 for (auto &Pred : MBB->predecessors()) { 403 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
388 if (!LiveOut.insert(Pred).second) 404 if (!LiveOut.insert(Pred).second)
389 continue; 405 continue;
390 SlotIndex Stop = Indexes.getMBBEndIdx(Pred); 406 SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
391 assert(OldRange.getVNInfoBefore(Stop) == VNI && 407 assert(OldRange.getVNInfoBefore(Stop) == VNI &&
392 "Wrong value out of predecessor"); 408 "Wrong value out of predecessor");
413 429
414 // Find all the values used, including PHI kills. 430 // Find all the values used, including PHI kills.
415 ShrinkToUsesWorkList WorkList; 431 ShrinkToUsesWorkList WorkList;
416 432
417 // Visit all instructions reading li->reg. 433 // Visit all instructions reading li->reg.
418 for (MachineRegisterInfo::reg_instr_iterator 434 unsigned Reg = li->reg;
419 I = MRI->reg_instr_begin(li->reg), E = MRI->reg_instr_end(); 435 for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) {
420 I != E; ) { 436 if (UseMI.isDebugValue() || !UseMI.readsVirtualRegister(Reg))
421 MachineInstr *UseMI = &*(I++); 437 continue;
422 if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) 438 SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
423 continue;
424 SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot();
425 LiveQueryResult LRQ = li->Query(Idx); 439 LiveQueryResult LRQ = li->Query(Idx);
426 VNInfo *VNI = LRQ.valueIn(); 440 VNInfo *VNI = LRQ.valueIn();
427 if (!VNI) { 441 if (!VNI) {
428 // This shouldn't happen: readsVirtualRegister returns true, but there is 442 // This shouldn't happen: readsVirtualRegister returns true, but there is
429 // no live value. It is likely caused by a target getting <undef> flags 443 // no live value. It is likely caused by a target getting <undef> flags
430 // wrong. 444 // wrong.
431 DEBUG(dbgs() << Idx << '\t' << *UseMI 445 DEBUG(dbgs() << Idx << '\t' << UseMI
432 << "Warning: Instr claims to read non-existent value in " 446 << "Warning: Instr claims to read non-existent value in "
433 << *li << '\n'); 447 << *li << '\n');
434 continue; 448 continue;
435 } 449 }
436 // Special case: An early-clobber tied operand reads and writes the 450 // Special case: An early-clobber tied operand reads and writes the
437 // register one slot early. 451 // register one slot early.
438 if (VNInfo *DefVNI = LRQ.valueDefined()) 452 if (VNInfo *DefVNI = LRQ.valueDefined())
456 } 470 }
457 471
458 bool LiveIntervals::computeDeadValues(LiveInterval &LI, 472 bool LiveIntervals::computeDeadValues(LiveInterval &LI,
459 SmallVectorImpl<MachineInstr*> *dead) { 473 SmallVectorImpl<MachineInstr*> *dead) {
460 bool MayHaveSplitComponents = false; 474 bool MayHaveSplitComponents = false;
461 for (auto VNI : LI.valnos) { 475 for (VNInfo *VNI : LI.valnos) {
462 if (VNI->isUnused()) 476 if (VNI->isUnused())
463 continue; 477 continue;
464 SlotIndex Def = VNI->def; 478 SlotIndex Def = VNI->def;
465 LiveRange::iterator I = LI.FindSegmentContaining(Def); 479 LiveRange::iterator I = LI.FindSegmentContaining(Def);
466 assert(I != LI.end() && "Missing segment for VNI"); 480 assert(I != LI.end() && "Missing segment for VNI");
512 continue; 526 continue;
513 // Maybe the operand is for a subregister we don't care about. 527 // Maybe the operand is for a subregister we don't care about.
514 unsigned SubReg = MO.getSubReg(); 528 unsigned SubReg = MO.getSubReg();
515 if (SubReg != 0) { 529 if (SubReg != 0) {
516 LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg); 530 LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);
517 if ((LaneMask & SR.LaneMask) == 0) 531 if ((LaneMask & SR.LaneMask).none())
518 continue; 532 continue;
519 } 533 }
520 // We only need to visit each instruction once. 534 // We only need to visit each instruction once.
521 MachineInstr *UseMI = MO.getParent(); 535 MachineInstr *UseMI = MO.getParent();
522 SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot(); 536 SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot();
546 560
547 // Move the trimmed ranges back. 561 // Move the trimmed ranges back.
548 SR.segments.swap(NewLR.segments); 562 SR.segments.swap(NewLR.segments);
549 563
550 // Remove dead PHI value numbers 564 // Remove dead PHI value numbers
551 for (auto VNI : SR.valnos) { 565 for (VNInfo *VNI : SR.valnos) {
552 if (VNI->isUnused()) 566 if (VNI->isUnused())
553 continue; 567 continue;
554 const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def); 568 const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);
555 assert(Segment != nullptr && "Missing segment for VNI"); 569 assert(Segment != nullptr && "Missing segment for VNI");
556 if (Segment->end != VNI->def.getDeadSlot()) 570 if (Segment->end != VNI->def.getDeadSlot())
569 void LiveIntervals::extendToIndices(LiveRange &LR, 583 void LiveIntervals::extendToIndices(LiveRange &LR,
570 ArrayRef<SlotIndex> Indices, 584 ArrayRef<SlotIndex> Indices,
571 ArrayRef<SlotIndex> Undefs) { 585 ArrayRef<SlotIndex> Undefs) {
572 assert(LRCalc && "LRCalc not initialized."); 586 assert(LRCalc && "LRCalc not initialized.");
573 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 587 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
574 for (unsigned i = 0, e = Indices.size(); i != e; ++i) 588 for (SlotIndex Idx : Indices)
575 LRCalc->extend(LR, Indices[i], /*PhysReg=*/0, Undefs); 589 LRCalc->extend(LR, Idx, /*PhysReg=*/0, Undefs);
576 } 590 }
577 591
578 void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill, 592 void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill,
579 SmallVectorImpl<SlotIndex> *EndPoints) { 593 SmallVectorImpl<SlotIndex> *EndPoints) {
580 LiveQueryResult LRQ = LR.Query(Kill); 594 LiveQueryResult LRQ = LR.Query(Kill);
597 if (EndPoints) EndPoints->push_back(MBBEnd); 611 if (EndPoints) EndPoints->push_back(MBBEnd);
598 612
599 // Find all blocks that are reachable from KillMBB without leaving VNI's live 613 // Find all blocks that are reachable from KillMBB without leaving VNI's live
600 // range. It is possible that KillMBB itself is reachable, so start a DFS 614 // range. It is possible that KillMBB itself is reachable, so start a DFS
601 // from each successor. 615 // from each successor.
602 typedef df_iterator_default_set<MachineBasicBlock*,9> VisitedTy; 616 using VisitedTy = df_iterator_default_set<MachineBasicBlock*,9>;
603 VisitedTy Visited; 617 VisitedTy Visited;
604 for (MachineBasicBlock::succ_iterator 618 for (MachineBasicBlock *Succ : KillMBB->successors()) {
605 SuccI = KillMBB->succ_begin(), SuccE = KillMBB->succ_end();
606 SuccI != SuccE; ++SuccI) {
607 for (df_ext_iterator<MachineBasicBlock*, VisitedTy> 619 for (df_ext_iterator<MachineBasicBlock*, VisitedTy>
608 I = df_ext_begin(*SuccI, Visited), E = df_ext_end(*SuccI, Visited); 620 I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited);
609 I != E;) { 621 I != E;) {
610 MachineBasicBlock *MBB = *I; 622 MachineBasicBlock *MBB = *I;
611 623
612 // Check if VNI is live in to MBB. 624 // Check if VNI is live in to MBB.
613 SlotIndex MBBStart, MBBEnd; 625 SlotIndex MBBStart, MBBEnd;
655 continue; 667 continue;
656 668
657 // Find the regunit intervals for the assigned register. They may overlap 669 // Find the regunit intervals for the assigned register. They may overlap
658 // the virtual register live range, cancelling any kills. 670 // the virtual register live range, cancelling any kills.
659 RU.clear(); 671 RU.clear();
660 for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid(); 672 for (MCRegUnitIterator Unit(VRM->getPhys(Reg), TRI); Unit.isValid();
661 ++Units) { 673 ++Unit) {
662 const LiveRange &RURange = getRegUnit(*Units); 674 const LiveRange &RURange = getRegUnit(*Unit);
663 if (RURange.empty()) 675 if (RURange.empty())
664 continue; 676 continue;
665 RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end))); 677 RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));
666 } 678 }
667 679
716 // are actually never written by %vreg2. After assignment the <kill> 728 // are actually never written by %vreg2. After assignment the <kill>
717 // flag at the read instruction is invalid. 729 // flag at the read instruction is invalid.
718 LaneBitmask DefinedLanesMask; 730 LaneBitmask DefinedLanesMask;
719 if (!SRs.empty()) { 731 if (!SRs.empty()) {
720 // Compute a mask of lanes that are defined. 732 // Compute a mask of lanes that are defined.
721 DefinedLanesMask = 0; 733 DefinedLanesMask = LaneBitmask::getNone();
722 for (auto &SRP : SRs) { 734 for (auto &SRP : SRs) {
723 const LiveInterval::SubRange &SR = *SRP.first; 735 const LiveInterval::SubRange &SR = *SRP.first;
724 LiveRange::const_iterator &I = SRP.second; 736 LiveRange::const_iterator &I = SRP.second;
725 if (I == SR.end()) 737 if (I == SR.end())
726 continue; 738 continue;
729 continue; 741 continue;
730 // I is overlapping RI 742 // I is overlapping RI
731 DefinedLanesMask |= SR.LaneMask; 743 DefinedLanesMask |= SR.LaneMask;
732 } 744 }
733 } else 745 } else
734 DefinedLanesMask = ~0u; 746 DefinedLanesMask = LaneBitmask::getAll();
735 747
736 bool IsFullWrite = false; 748 bool IsFullWrite = false;
737 for (const MachineOperand &MO : MI->operands()) { 749 for (const MachineOperand &MO : MI->operands()) {
738 if (!MO.isReg() || MO.getReg() != Reg) 750 if (!MO.isReg() || MO.getReg() != Reg)
739 continue; 751 continue;
740 if (MO.isUse()) { 752 if (MO.isUse()) {
741 // Reading any undefined lanes? 753 // Reading any undefined lanes?
742 LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg()); 754 LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());
743 if ((UseMask & ~DefinedLanesMask) != 0) 755 if ((UseMask & ~DefinedLanesMask).any())
744 goto CancelKill; 756 goto CancelKill;
745 } else if (MO.getSubReg() == 0) { 757 } else if (MO.getSubReg() == 0) {
746 // Writing to the full register? 758 // Writing to the full register?
747 assert(MO.isDef()); 759 assert(MO.isDef());
748 IsFullWrite = true; 760 IsFullWrite = true;
800 continue; 812 continue;
801 const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def); 813 const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
802 // Conservatively return true instead of scanning huge predecessor lists. 814 // Conservatively return true instead of scanning huge predecessor lists.
803 if (PHIMBB->pred_size() > 100) 815 if (PHIMBB->pred_size() > 100)
804 return true; 816 return true;
805 for (MachineBasicBlock::const_pred_iterator 817 for (const MachineBasicBlock *Pred : PHIMBB->predecessors())
806 PI = PHIMBB->pred_begin(), PE = PHIMBB->pred_end(); PI != PE; ++PI) 818 if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred)))
807 if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(*PI)))
808 return true; 819 return true;
809 } 820 }
810 return false; 821 return false;
811 } 822 }
812 823
813 float LiveIntervals::getSpillWeight(bool isDef, bool isUse, 824 float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
814 const MachineBlockFrequencyInfo *MBFI, 825 const MachineBlockFrequencyInfo *MBFI,
815 const MachineInstr &MI) { 826 const MachineInstr &MI) {
816 BlockFrequency Freq = MBFI->getBlockFreq(MI.getParent()); 827 return getSpillWeight(isDef, isUse, MBFI, MI.getParent());
828 }
829
830 float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
831 const MachineBlockFrequencyInfo *MBFI,
832 const MachineBasicBlock *MBB) {
833 BlockFrequency Freq = MBFI->getBlockFreq(MBB);
817 const float Scale = 1.0f / MBFI->getEntryFreq(); 834 const float Scale = 1.0f / MBFI->getEntryFreq();
818 return (isDef + isUse) * (Freq.getFrequency() * Scale); 835 return (isDef + isUse) * (Freq.getFrequency() * Scale);
819 } 836 }
820 837
821 LiveRange::Segment 838 LiveRange::Segment
829 Interval.addSegment(S); 846 Interval.addSegment(S);
830 847
831 return S; 848 return S;
832 } 849 }
833 850
834
835 //===----------------------------------------------------------------------===// 851 //===----------------------------------------------------------------------===//
836 // Register mask functions 852 // Register mask functions
837 //===----------------------------------------------------------------------===// 853 //===----------------------------------------------------------------------===//
838 854
839 bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, 855 bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
862 // No slots in range, LI begins after the last call. 878 // No slots in range, LI begins after the last call.
863 if (SlotI == SlotE) 879 if (SlotI == SlotE)
864 return false; 880 return false;
865 881
866 bool Found = false; 882 bool Found = false;
867 for (;;) { 883 while (true) {
868 assert(*SlotI >= LiveI->start); 884 assert(*SlotI >= LiveI->start);
869 // Loop over all slots overlapping this segment. 885 // Loop over all slots overlapping this segment.
870 while (*SlotI < LiveI->end) { 886 while (*SlotI < LiveI->end) {
871 // *SlotI overlaps LI. Collect mask bits. 887 // *SlotI overlaps LI. Collect mask bits.
872 if (!Found) { 888 if (!Found) {
893 909
894 //===----------------------------------------------------------------------===// 910 //===----------------------------------------------------------------------===//
895 // IntervalUpdate class. 911 // IntervalUpdate class.
896 //===----------------------------------------------------------------------===// 912 //===----------------------------------------------------------------------===//
897 913
898 // HMEditor is a toolkit used by handleMove to trim or extend live intervals. 914 /// Toolkit used by handleMove to trim or extend live intervals.
899 class LiveIntervals::HMEditor { 915 class LiveIntervals::HMEditor {
900 private: 916 private:
901 LiveIntervals& LIS; 917 LiveIntervals& LIS;
902 const MachineRegisterInfo& MRI; 918 const MachineRegisterInfo& MRI;
903 const TargetRegisterInfo& TRI; 919 const TargetRegisterInfo& TRI;
916 // FIXME: UpdateFlags is a workaround that creates live intervals for all 932 // FIXME: UpdateFlags is a workaround that creates live intervals for all
917 // physregs, even those that aren't needed for regalloc, in order to update 933 // physregs, even those that aren't needed for regalloc, in order to update
918 // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill 934 // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
919 // flags, and postRA passes will use a live register utility instead. 935 // flags, and postRA passes will use a live register utility instead.
920 LiveRange *getRegUnitLI(unsigned Unit) { 936 LiveRange *getRegUnitLI(unsigned Unit) {
921 if (UpdateFlags) 937 if (UpdateFlags && !MRI.isReservedRegUnit(Unit))
922 return &LIS.getRegUnit(Unit); 938 return &LIS.getRegUnit(Unit);
923 return LIS.getCachedRegUnit(Unit); 939 return LIS.getCachedRegUnit(Unit);
924 } 940 }
925 941
926 /// Update all live ranges touched by MI, assuming a move from OldIdx to 942 /// Update all live ranges touched by MI, assuming a move from OldIdx to
949 if (LI.hasSubRanges()) { 965 if (LI.hasSubRanges()) {
950 unsigned SubReg = MO.getSubReg(); 966 unsigned SubReg = MO.getSubReg();
951 LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg) 967 LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
952 : MRI.getMaxLaneMaskForVReg(Reg); 968 : MRI.getMaxLaneMaskForVReg(Reg);
953 for (LiveInterval::SubRange &S : LI.subranges()) { 969 for (LiveInterval::SubRange &S : LI.subranges()) {
954 if ((S.LaneMask & LaneMask) == 0) 970 if ((S.LaneMask & LaneMask).none())
955 continue; 971 continue;
956 updateRange(S, Reg, S.LaneMask); 972 updateRange(S, Reg, S.LaneMask);
957 } 973 }
958 } 974 }
959 updateRange(LI, Reg, 0); 975 updateRange(LI, Reg, LaneBitmask::getNone());
960 continue; 976 continue;
961 } 977 }
962 978
963 // For physregs, only update the regunits that actually have a 979 // For physregs, only update the regunits that actually have a
964 // precomputed live range. 980 // precomputed live range.
965 for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) 981 for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
966 if (LiveRange *LR = getRegUnitLI(*Units)) 982 if (LiveRange *LR = getRegUnitLI(*Units))
967 updateRange(*LR, *Units, 0); 983 updateRange(*LR, *Units, LaneBitmask::getNone());
968 } 984 }
969 if (hasRegMask) 985 if (hasRegMask)
970 updateRegMaskSlots(); 986 updateRegMaskSlots();
971 } 987 }
972 988
978 return; 994 return;
979 DEBUG({ 995 DEBUG({
980 dbgs() << " "; 996 dbgs() << " ";
981 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 997 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
982 dbgs() << PrintReg(Reg); 998 dbgs() << PrintReg(Reg);
983 if (LaneMask != 0) 999 if (LaneMask.any())
984 dbgs() << " L" << PrintLaneMask(LaneMask); 1000 dbgs() << " L" << PrintLaneMask(LaneMask);
985 } else { 1001 } else {
986 dbgs() << PrintRegUnit(Reg, &TRI); 1002 dbgs() << PrintRegUnit(Reg, &TRI);
987 } 1003 }
988 dbgs() << ":\t" << LR << '\n'; 1004 dbgs() << ":\t" << LR << '\n';
1239 SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) { 1255 SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) {
1240 // OldIdx is not a dead def and NewIdx is before predecessor start. 1256 // OldIdx is not a dead def and NewIdx is before predecessor start.
1241 LiveRange::iterator NewIdxIn = NewIdxOut; 1257 LiveRange::iterator NewIdxIn = NewIdxOut;
1242 assert(NewIdxIn == LR.find(NewIdx.getBaseIndex())); 1258 assert(NewIdxIn == LR.find(NewIdx.getBaseIndex()));
1243 const SlotIndex SplitPos = NewIdxDef; 1259 const SlotIndex SplitPos = NewIdxDef;
1260 OldIdxVNI = OldIdxIn->valno;
1244 1261
1245 // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut. 1262 // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut.
1263 OldIdxOut->valno->def = OldIdxIn->start;
1246 *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end, 1264 *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end,
1247 OldIdxIn->valno); 1265 OldIdxOut->valno);
1248 // OldIdxIn and OldIdxVNI are now undef and can be overridden. 1266 // OldIdxIn and OldIdxVNI are now undef and can be overridden.
1249 // We Slide [NewIdxIn, OldIdxIn) down one position. 1267 // We Slide [NewIdxIn, OldIdxIn) down one position.
1250 // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -| 1268 // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -|
1251 // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -| 1269 // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -|
1252 std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut); 1270 std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);
1312 SlotIndex LastUse = Before; 1330 SlotIndex LastUse = Before;
1313 for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) { 1331 for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1314 if (MO.isUndef()) 1332 if (MO.isUndef())
1315 continue; 1333 continue;
1316 unsigned SubReg = MO.getSubReg(); 1334 unsigned SubReg = MO.getSubReg();
1317 if (SubReg != 0 && LaneMask != 0 1335 if (SubReg != 0 && LaneMask.any()
1318 && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask) == 0) 1336 && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none())
1319 continue; 1337 continue;
1320 1338
1321 const MachineInstr &MI = *MO.getParent(); 1339 const MachineInstr &MI = *MO.getParent();
1322 SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); 1340 SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
1323 if (InstSlot > LastUse && InstSlot < OldIdx) 1341 if (InstSlot > LastUse && InstSlot < OldIdx)
1420 if (!MO.isReg() || MO.getReg() != Reg) 1438 if (!MO.isReg() || MO.getReg() != Reg)
1421 continue; 1439 continue;
1422 1440
1423 unsigned SubReg = MO.getSubReg(); 1441 unsigned SubReg = MO.getSubReg();
1424 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg); 1442 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
1425 if ((Mask & LaneMask) == 0) 1443 if ((Mask & LaneMask).none())
1426 continue; 1444 continue;
1427 1445
1428 if (MO.isDef()) { 1446 if (MO.isDef()) {
1429 if (!isStartValid) { 1447 if (!isStartValid) {
1430 if (LII->end.isDead()) { 1448 if (LII->end.isDead()) {
1512 createAndComputeVirtRegInterval(MOI->getReg()); 1530 createAndComputeVirtRegInterval(MOI->getReg());
1513 } 1531 }
1514 } 1532 }
1515 } 1533 }
1516 1534
1517 for (unsigned i = 0, e = OrigRegs.size(); i != e; ++i) { 1535 for (unsigned Reg : OrigRegs) {
1518 unsigned Reg = OrigRegs[i];
1519 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1536 if (!TargetRegisterInfo::isVirtualRegister(Reg))
1520 continue; 1537 continue;
1521 1538
1522 LiveInterval &LI = getInterval(Reg); 1539 LiveInterval &LI = getInterval(Reg);
1523 // FIXME: Should we support undefs that gain defs? 1540 // FIXME: Should we support undefs that gain defs?
1524 if (!LI.hasAtLeastOneValue()) 1541 if (!LI.hasAtLeastOneValue())
1525 continue; 1542 continue;
1526 1543
1527 for (LiveInterval::SubRange &S : LI.subranges()) { 1544 for (LiveInterval::SubRange &S : LI.subranges())
1528 repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask); 1545 repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask);
1529 } 1546
1530 repairOldRegInRange(Begin, End, endIdx, LI, Reg); 1547 repairOldRegInRange(Begin, End, endIdx, LI, Reg);
1531 } 1548 }
1532 } 1549 }
1533 1550
1534 void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) { 1551 void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) {
1535 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 1552 for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) {
1536 if (LiveRange *LR = getCachedRegUnit(*Units)) 1553 if (LiveRange *LR = getCachedRegUnit(*Unit))
1537 if (VNInfo *VNI = LR->getVNInfoAt(Pos)) 1554 if (VNInfo *VNI = LR->getVNInfoAt(Pos))
1538 LR->removeValNo(VNI); 1555 LR->removeValNo(VNI);
1539 } 1556 }
1540 } 1557 }
1541 1558