1 //===- ExecutionDepsFix.cpp - Fix execution dependecy issues ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/CodeGen/ExecutionDepsFix.h"
12 #include "llvm/ADT/PostOrderIterator.h"
13 #include "llvm/ADT/iterator_range.h"
14 #include "llvm/CodeGen/LivePhysRegs.h"
15 #include "llvm/CodeGen/MachineFunctionPass.h"
16 #include "llvm/CodeGen/MachineRegisterInfo.h"
17 #include "llvm/CodeGen/RegisterClassInfo.h"
18 #include "llvm/CodeGen/TargetInstrInfo.h"
19 #include "llvm/CodeGen/TargetSubtargetInfo.h"
20 #include "llvm/Support/Allocator.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/raw_ostream.h"
26 #define DEBUG_TYPE "execution-deps-fix"
28 /// Translate TRI register number to a list of indices into our smaller tables
29 /// of interesting registers.
30 iterator_range<SmallVectorImpl<int>::const_iterator>
31 ExecutionDepsFix::regIndices(unsigned Reg) const {
32 assert(Reg < AliasMap.size() && "Invalid register");
33 const auto &Entry = AliasMap[Reg];
34 return make_range(Entry.begin(), Entry.end());
37 DomainValue *ExecutionDepsFix::alloc(int domain) {
38 DomainValue *dv = Avail.empty() ?
39 new(Allocator.Allocate()) DomainValue :
42 dv->addDomain(domain);
43 assert(dv->Refs == 0 && "Reference count wasn't cleared");
44 assert(!dv->Next && "Chained DomainValue shouldn't have been recycled");
48 /// Release a reference to DV. When the last reference is released,
49 /// collapse if needed.
50 void ExecutionDepsFix::release(DomainValue *DV) {
52 assert(DV->Refs && "Bad DomainValue");
56 // There are no more DV references. Collapse any contained instructions.
57 if (DV->AvailableDomains && !DV->isCollapsed())
58 collapse(DV, DV->getFirstDomain());
60 DomainValue *Next = DV->Next;
63 // Also release the next DomainValue in the chain.
68 /// Follow the chain of dead DomainValues until a live DomainValue is reached.
69 /// Update the referenced pointer when necessary.
70 DomainValue *ExecutionDepsFix::resolve(DomainValue *&DVRef) {
71 DomainValue *DV = DVRef;
75 // DV has a chain. Find the end.
79 // Update DVRef to point to DV.
86 /// Set LiveRegs[rx] = dv, updating reference counts.
87 void ExecutionDepsFix::setLiveReg(int rx, DomainValue *dv) {
88 assert(unsigned(rx) < NumRegs && "Invalid index");
89 assert(LiveRegs && "Must enter basic block first.");
91 if (LiveRegs[rx].Value == dv)
93 if (LiveRegs[rx].Value)
94 release(LiveRegs[rx].Value);
95 LiveRegs[rx].Value = retain(dv);
98 // Kill register rx, recycle or collapse any DomainValue.
99 void ExecutionDepsFix::kill(int rx) {
100 assert(unsigned(rx) < NumRegs && "Invalid index");
101 assert(LiveRegs && "Must enter basic block first.");
102 if (!LiveRegs[rx].Value)
105 release(LiveRegs[rx].Value);
106 LiveRegs[rx].Value = nullptr;
109 /// Force register rx into domain.
110 void ExecutionDepsFix::force(int rx, unsigned domain) {
111 assert(unsigned(rx) < NumRegs && "Invalid index");
112 assert(LiveRegs && "Must enter basic block first.");
113 if (DomainValue *dv = LiveRegs[rx].Value) {
114 if (dv->isCollapsed())
115 dv->addDomain(domain);
116 else if (dv->hasDomain(domain))
117 collapse(dv, domain);
119 // This is an incompatible open DomainValue. Collapse it to whatever and
120 // force the new value into domain. This costs a domain crossing.
121 collapse(dv, dv->getFirstDomain());
122 assert(LiveRegs[rx].Value && "Not live after collapse?");
123 LiveRegs[rx].Value->addDomain(domain);
126 // Set up basic collapsed DomainValue.
127 setLiveReg(rx, alloc(domain));
131 /// Collapse open DomainValue into given domain. If there are multiple
132 /// registers using dv, they each get a unique collapsed DomainValue.
133 void ExecutionDepsFix::collapse(DomainValue *dv, unsigned domain) {
134 assert(dv->hasDomain(domain) && "Cannot collapse");
136 // Collapse all the instructions.
137 while (!dv->Instrs.empty())
138 TII->setExecutionDomain(*dv->Instrs.pop_back_val(), domain);
139 dv->setSingleDomain(domain);
141 // If there are multiple users, give them new, unique DomainValues.
142 if (LiveRegs && dv->Refs > 1)
143 for (unsigned rx = 0; rx != NumRegs; ++rx)
144 if (LiveRegs[rx].Value == dv)
145 setLiveReg(rx, alloc(domain));
148 /// All instructions and registers in B are moved to A, and B is released.
149 bool ExecutionDepsFix::merge(DomainValue *A, DomainValue *B) {
150 assert(!A->isCollapsed() && "Cannot merge into collapsed");
151 assert(!B->isCollapsed() && "Cannot merge from collapsed");
154 // Restrict to the domains that A and B have in common.
155 unsigned common = A->getCommonDomains(B->AvailableDomains);
158 A->AvailableDomains = common;
159 A->Instrs.append(B->Instrs.begin(), B->Instrs.end());
161 // Clear the old DomainValue so we won't try to swizzle instructions twice.
163 // All uses of B are referred to A.
166 for (unsigned rx = 0; rx != NumRegs; ++rx) {
167 assert(LiveRegs && "no space allocated for live registers");
168 if (LiveRegs[rx].Value == B)
174 /// Set up LiveRegs by merging predecessor live-out values.
175 void ExecutionDepsFix::enterBasicBlock(MachineBasicBlock *MBB) {
176 // Reset instruction counter in each basic block.
179 // Set up UndefReads to track undefined register reads.
183 // Set up LiveRegs to represent registers entering MBB.
185 LiveRegs = new LiveReg[NumRegs];
187 // Default values are 'nothing happened a long time ago'.
188 for (unsigned rx = 0; rx != NumRegs; ++rx) {
189 LiveRegs[rx].Value = nullptr;
190 LiveRegs[rx].Def = -(1 << 20);
193 // This is the entry block.
194 if (MBB->pred_empty()) {
195 for (const auto &LI : MBB->liveins()) {
196 for (int rx : regIndices(LI.PhysReg)) {
197 // Treat function live-ins as if they were defined just before the first
198 // instruction. Usually, function arguments are set up immediately
200 LiveRegs[rx].Def = -1;
203 DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
207 // Try to coalesce live-out registers from predecessors.
208 for (MachineBasicBlock::const_pred_iterator pi = MBB->pred_begin(),
209 pe = MBB->pred_end(); pi != pe; ++pi) {
210 auto fi = MBBInfos.find(*pi);
211 assert(fi != MBBInfos.end() &&
212 "Should have pre-allocated MBBInfos for all MBBs");
213 LiveReg *Incoming = fi->second.OutRegs;
214 // Incoming is null if this is a backedge from a BB
215 // we haven't processed yet
216 if (Incoming == nullptr) {
220 for (unsigned rx = 0; rx != NumRegs; ++rx) {
221 // Use the most recent predecessor def for each register.
222 LiveRegs[rx].Def = std::max(LiveRegs[rx].Def, Incoming[rx].Def);
224 DomainValue *pdv = resolve(Incoming[rx].Value);
227 if (!LiveRegs[rx].Value) {
232 // We have a live DomainValue from more than one predecessor.
233 if (LiveRegs[rx].Value->isCollapsed()) {
234 // We are already collapsed, but predecessor is not. Force it.
235 unsigned Domain = LiveRegs[rx].Value->getFirstDomain();
236 if (!pdv->isCollapsed() && pdv->hasDomain(Domain))
237 collapse(pdv, Domain);
241 // Currently open, merge in predecessor.
242 if (!pdv->isCollapsed())
243 merge(LiveRegs[rx].Value, pdv);
245 force(rx, pdv->getFirstDomain());
249 dbgs() << printMBBReference(*MBB)
250 << (!isBlockDone(MBB) ? ": incomplete\n" : ": all preds known\n"));
253 void ExecutionDepsFix::leaveBasicBlock(MachineBasicBlock *MBB) {
254 assert(LiveRegs && "Must enter basic block first.");
255 LiveReg *OldOutRegs = MBBInfos[MBB].OutRegs;
256 // Save register clearances at end of MBB - used by enterBasicBlock().
257 MBBInfos[MBB].OutRegs = LiveRegs;
259 // While processing the basic block, we kept `Def` relative to the start
260 // of the basic block for convenience. However, future use of this information
261 // only cares about the clearance from the end of the block, so adjust
262 // everything to be relative to the end of the basic block.
263 for (unsigned i = 0, e = NumRegs; i != e; ++i)
264 LiveRegs[i].Def -= CurInstr;
266 // This must be the second pass.
267 // Release all the DomainValues instead of keeping them.
268 for (unsigned i = 0, e = NumRegs; i != e; ++i)
269 release(OldOutRegs[i].Value);
275 bool ExecutionDepsFix::visitInstr(MachineInstr *MI) {
276 // Update instructions with explicit execution domains.
277 std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(*MI);
280 visitSoftInstr(MI, DomP.second);
282 visitHardInstr(MI, DomP.first);
288 /// \brief Helps avoid false dependencies on undef registers by updating the
289 /// machine instructions' undef operand to use a register that the instruction
290 /// is truly dependent on, or use a register with clearance higher than Pref.
291 /// Returns true if it was able to find a true dependency, thus not requiring
292 /// a dependency breaking instruction regardless of clearance.
293 bool ExecutionDepsFix::pickBestRegisterForUndef(MachineInstr *MI,
294 unsigned OpIdx, unsigned Pref) {
295 MachineOperand &MO = MI->getOperand(OpIdx);
296 assert(MO.isUndef() && "Expected undef machine operand");
298 unsigned OriginalReg = MO.getReg();
300 // Update only undef operands that are mapped to one register.
301 if (AliasMap[OriginalReg].size() != 1)
304 // Get the undef operand's register class
305 const TargetRegisterClass *OpRC =
306 TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF);
308 // If the instruction has a true dependency, we can hide the false depdency
310 for (MachineOperand &CurrMO : MI->operands()) {
311 if (!CurrMO.isReg() || CurrMO.isDef() || CurrMO.isUndef() ||
312 !OpRC->contains(CurrMO.getReg()))
314 // We found a true dependency - replace the undef register with the true
316 MO.setReg(CurrMO.getReg());
320 // Go over all registers in the register class and find the register with
321 // max clearance or clearance higher than Pref.
322 unsigned MaxClearance = 0;
323 unsigned MaxClearanceReg = OriginalReg;
324 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(OpRC);
325 for (auto Reg : Order) {
326 assert(AliasMap[Reg].size() == 1 &&
327 "Reg is expected to be mapped to a single index");
328 int RCrx = *regIndices(Reg).begin();
329 unsigned Clearance = CurInstr - LiveRegs[RCrx].Def;
330 if (Clearance <= MaxClearance)
332 MaxClearance = Clearance;
333 MaxClearanceReg = Reg;
335 if (MaxClearance > Pref)
339 // Update the operand if we found a register with better clearance.
340 if (MaxClearanceReg != OriginalReg)
341 MO.setReg(MaxClearanceReg);
346 /// \brief Return true to if it makes sense to break dependence on a partial def
348 bool ExecutionDepsFix::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
350 unsigned reg = MI->getOperand(OpIdx).getReg();
351 for (int rx : regIndices(reg)) {
352 unsigned Clearance = CurInstr - LiveRegs[rx].Def;
353 DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
355 if (Pref > Clearance) {
356 DEBUG(dbgs() << ": Break dependency.\n");
359 DEBUG(dbgs() << ": OK .\n");
365 // Update def-ages for registers defined by MI.
366 // If Kill is set, also kill off DomainValues clobbered by the defs.
368 // Also break dependencies on partial defs and undef uses.
369 void ExecutionDepsFix::processDefs(MachineInstr *MI, bool breakDependency,
371 assert(!MI->isDebugValue() && "Won't process debug values");
373 // Break dependence on undef uses. Do this before updating LiveRegs below.
375 if (breakDependency) {
376 unsigned Pref = TII->getUndefRegClearance(*MI, OpNum, TRI);
378 bool HadTrueDependency = pickBestRegisterForUndef(MI, OpNum, Pref);
379 // We don't need to bother trying to break a dependency if this
380 // instruction has a true dependency on that register through another
381 // operand - we'll have to wait for it to be available regardless.
382 if (!HadTrueDependency && shouldBreakDependence(MI, OpNum, Pref))
383 UndefReads.push_back(std::make_pair(MI, OpNum));
386 const MCInstrDesc &MCID = MI->getDesc();
388 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
390 MachineOperand &MO = MI->getOperand(i);
395 for (int rx : regIndices(MO.getReg())) {
396 // This instruction explicitly defines rx.
397 DEBUG(dbgs() << printReg(RC->getRegister(rx), TRI) << ":\t" << CurInstr
400 if (breakDependency) {
401 // Check clearance before partial register updates.
402 // Call breakDependence before setting LiveRegs[rx].Def.
403 unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
404 if (Pref && shouldBreakDependence(MI, i, Pref))
405 TII->breakPartialRegDependency(*MI, i, TRI);
408 // How many instructions since rx was last written?
409 LiveRegs[rx].Def = CurInstr;
411 // Kill off domains redefined by generic instructions.
419 /// \break Break false dependencies on undefined register reads.
421 /// Walk the block backward computing precise liveness. This is expensive, so we
422 /// only do it on demand. Note that the occurrence of undefined register reads
423 /// that should be broken is very rare, but when they occur we may have many in
425 void ExecutionDepsFix::processUndefReads(MachineBasicBlock *MBB) {
426 if (UndefReads.empty())
429 // Collect this block's live out register units.
430 LiveRegSet.init(*TRI);
431 // We do not need to care about pristine registers as they are just preserved
432 // but not actually used in the function.
433 LiveRegSet.addLiveOutsNoPristines(*MBB);
435 MachineInstr *UndefMI = UndefReads.back().first;
436 unsigned OpIdx = UndefReads.back().second;
438 for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) {
439 // Update liveness, including the current instruction's defs.
440 LiveRegSet.stepBackward(I);
443 if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
444 TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);
446 UndefReads.pop_back();
447 if (UndefReads.empty())
450 UndefMI = UndefReads.back().first;
451 OpIdx = UndefReads.back().second;
456 // A hard instruction only works in one domain. All input registers will be
457 // forced into that domain.
458 void ExecutionDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) {
459 // Collapse all uses.
460 for (unsigned i = mi->getDesc().getNumDefs(),
461 e = mi->getDesc().getNumOperands(); i != e; ++i) {
462 MachineOperand &mo = mi->getOperand(i);
463 if (!mo.isReg()) continue;
464 for (int rx : regIndices(mo.getReg())) {
469 // Kill all defs and force them.
470 for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
471 MachineOperand &mo = mi->getOperand(i);
472 if (!mo.isReg()) continue;
473 for (int rx : regIndices(mo.getReg())) {
480 // A soft instruction can be changed to work in other domains given by mask.
481 void ExecutionDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) {
482 // Bitmask of available domains for this instruction after taking collapsed
483 // operands into account.
484 unsigned available = mask;
486 // Scan the explicit use operands for incoming domains.
487 SmallVector<int, 4> used;
489 for (unsigned i = mi->getDesc().getNumDefs(),
490 e = mi->getDesc().getNumOperands(); i != e; ++i) {
491 MachineOperand &mo = mi->getOperand(i);
492 if (!mo.isReg()) continue;
493 for (int rx : regIndices(mo.getReg())) {
494 DomainValue *dv = LiveRegs[rx].Value;
497 // Bitmask of domains that dv and available have in common.
498 unsigned common = dv->getCommonDomains(available);
499 // Is it possible to use this collapsed register for free?
500 if (dv->isCollapsed()) {
501 // Restrict available domains to the ones in common with the operand.
502 // If there are no common domains, we must pay the cross-domain
503 // penalty for this operand.
504 if (common) available = common;
506 // Open DomainValue is compatible, save it for merging.
509 // Open DomainValue is not compatible with instruction. It is useless
515 // If the collapsed operands force a single domain, propagate the collapse.
516 if (isPowerOf2_32(available)) {
517 unsigned domain = countTrailingZeros(available);
518 TII->setExecutionDomain(*mi, domain);
519 visitHardInstr(mi, domain);
523 // Kill off any remaining uses that don't match available, and build a list of
524 // incoming DomainValues that we want to merge.
525 SmallVector<const LiveReg *, 4> Regs;
526 for (int rx : used) {
527 assert(LiveRegs && "no space allocated for live registers");
528 const LiveReg &LR = LiveRegs[rx];
529 // This useless DomainValue could have been missed above.
530 if (!LR.Value->getCommonDomains(available)) {
535 auto I = std::upper_bound(Regs.begin(), Regs.end(), &LR,
536 [](const LiveReg *LHS, const LiveReg *RHS) {
537 return LHS->Def < RHS->Def;
542 // doms are now sorted in order of appearance. Try to merge them all, giving
543 // priority to the latest ones.
544 DomainValue *dv = nullptr;
545 while (!Regs.empty()) {
547 dv = Regs.pop_back_val()->Value;
548 // Force the first dv to match the current instruction.
549 dv->AvailableDomains = dv->getCommonDomains(available);
550 assert(dv->AvailableDomains && "Domain should have been filtered");
554 DomainValue *Latest = Regs.pop_back_val()->Value;
555 // Skip already merged values.
556 if (Latest == dv || Latest->Next)
558 if (merge(dv, Latest))
561 // If latest didn't merge, it is useless now. Kill all registers using it.
563 assert(LiveRegs && "no space allocated for live registers");
564 if (LiveRegs[i].Value == Latest)
569 // dv is the DomainValue we are going to use for this instruction.
572 dv->AvailableDomains = available;
574 dv->Instrs.push_back(mi);
576 // Finally set all defs and non-collapsed uses to dv. We must iterate through
577 // all the operators, including imp-def ones.
578 for (MachineInstr::mop_iterator ii = mi->operands_begin(),
579 ee = mi->operands_end();
581 MachineOperand &mo = *ii;
582 if (!mo.isReg()) continue;
583 for (int rx : regIndices(mo.getReg())) {
584 if (!LiveRegs[rx].Value || (mo.isDef() && LiveRegs[rx].Value != dv)) {
592 void ExecutionDepsFix::processBasicBlock(MachineBasicBlock *MBB,
594 enterBasicBlock(MBB);
595 // If this block is not done, it makes little sense to make any decisions
596 // based on clearance information. We need to make a second pass anyway,
597 // and by then we'll have better information, so we can avoid doing the work
598 // to try and break dependencies now.
599 bool breakDependency = isBlockDone(MBB);
600 for (MachineInstr &MI : *MBB) {
601 if (!MI.isDebugValue()) {
604 Kill = visitInstr(&MI);
605 processDefs(&MI, breakDependency, Kill);
609 processUndefReads(MBB);
610 leaveBasicBlock(MBB);
613 bool ExecutionDepsFix::isBlockDone(MachineBasicBlock *MBB) {
614 return MBBInfos[MBB].PrimaryCompleted &&
615 MBBInfos[MBB].IncomingCompleted == MBBInfos[MBB].PrimaryIncoming &&
616 MBBInfos[MBB].IncomingProcessed == MBB->pred_size();
619 bool ExecutionDepsFix::runOnMachineFunction(MachineFunction &mf) {
620 if (skipFunction(mf.getFunction()))
623 TII = MF->getSubtarget().getInstrInfo();
624 TRI = MF->getSubtarget().getRegisterInfo();
625 RegClassInfo.runOnMachineFunction(mf);
627 assert(NumRegs == RC->getNumRegs() && "Bad regclass");
629 DEBUG(dbgs() << "********** FIX EXECUTION DEPENDENCIES: "
630 << TRI->getRegClassName(RC) << " **********\n");
632 // If no relevant registers are used in the function, we can skip it
634 bool anyregs = false;
635 const MachineRegisterInfo &MRI = mf.getRegInfo();
636 for (unsigned Reg : *RC) {
637 if (MRI.isPhysRegUsed(Reg)) {
642 if (!anyregs) return false;
644 // Initialize the AliasMap on the first use.
645 if (AliasMap.empty()) {
646 // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and
647 // therefore the LiveRegs array.
648 AliasMap.resize(TRI->getNumRegs());
649 for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i)
650 for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true);
652 AliasMap[*AI].push_back(i);
655 // Initialize the MMBInfos
656 for (auto &MBB : mf) {
658 MBBInfos.insert(std::make_pair(&MBB, InitialInfo));
662 * We want to visit every instruction in every basic block in order to update
663 * it's execution domain or break any false dependencies. However, for the
664 * dependency breaking, we need to know clearances from all predecessors
665 * (including any backedges). One way to do so would be to do two complete
666 * passes over all basic blocks/instructions, the first for recording
667 * clearances, the second to break the dependencies. However, for functions
668 * without backedges, or functions with a lot of straight-line code, and
669 * a small loop, that would be a lot of unnecessary work (since only the
670 * BBs that are part of the loop require two passes). As an example,
671 * consider the following loop.
674 * PH -> A -> B (xmm<Undef> -> xmm<Def>) -> C -> D -> EXIT
676 * +----------------------------------+
678 * The iteration order is as follows:
679 * Naive: PH A B C D A' B' C' D'
680 * Optimized: PH A B C A' B' C' D
682 * Note that we avoid processing D twice, because we can entirely process
683 * the predecessors before getting to D. We call a block that is ready
684 * for its second round of processing `done` (isBlockDone). Once we finish
685 * processing some block, we update the counters in MBBInfos and re-process
686 * any successors that are now done.
689 MachineBasicBlock *Entry = &*MF->begin();
690 ReversePostOrderTraversal<MachineBasicBlock*> RPOT(Entry);
691 SmallVector<MachineBasicBlock *, 4> Workqueue;
692 for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
693 MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
694 MachineBasicBlock *MBB = *MBBI;
695 // N.B: IncomingProcessed and IncomingCompleted were already updated while
696 // processing this block's predecessors.
697 MBBInfos[MBB].PrimaryCompleted = true;
698 MBBInfos[MBB].PrimaryIncoming = MBBInfos[MBB].IncomingProcessed;
700 Workqueue.push_back(MBB);
701 while (!Workqueue.empty()) {
702 MachineBasicBlock *ActiveMBB = &*Workqueue.back();
703 Workqueue.pop_back();
704 processBasicBlock(ActiveMBB, Primary);
705 bool Done = isBlockDone(ActiveMBB);
706 for (auto *Succ : ActiveMBB->successors()) {
707 if (!isBlockDone(Succ)) {
709 MBBInfos[Succ].IncomingProcessed++;
712 MBBInfos[Succ].IncomingCompleted++;
714 if (isBlockDone(Succ)) {
715 Workqueue.push_back(Succ);
723 // We need to go through again and finalize any blocks that are not done yet.
724 // This is possible if blocks have dead predecessors, so we didn't visit them
726 for (ReversePostOrderTraversal<MachineBasicBlock *>::rpo_iterator
729 MBBI != MBBE; ++MBBI) {
730 MachineBasicBlock *MBB = *MBBI;
731 if (!isBlockDone(MBB)) {
732 processBasicBlock(MBB, false);
733 // Don't update successors here. We'll get to them anyway through this
738 // Clear the LiveOuts vectors and collapse any remaining DomainValues.
739 for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
740 MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
741 auto FI = MBBInfos.find(*MBBI);
742 if (FI == MBBInfos.end() || !FI->second.OutRegs)
744 for (unsigned i = 0, e = NumRegs; i != e; ++i)
745 if (FI->second.OutRegs[i].Value)
746 release(FI->second.OutRegs[i].Value);
747 delete[] FI->second.OutRegs;
752 Allocator.DestroyAll();