contrib/llvm/lib/CodeGen/LiveRangeCalc.cpp

   1 //===---- LiveRangeCalc.cpp - Calculate 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 // Implementation of the LiveRangeCalc class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "LiveRangeCalc.h"
  15 #include "llvm/ADT/SetVector.h"
  16 #include "llvm/CodeGen/MachineDominators.h"
  17 #include "llvm/CodeGen/MachineRegisterInfo.h"
  18
  19 using namespace llvm;
  20
  21 #define DEBUG_TYPE "regalloc"
  22
  23 // Reserve an address that indicates a value that is known to be "undef".
  24 static VNInfo UndefVNI(0xbad, SlotIndex());
  25
  26 void LiveRangeCalc::resetLiveOutMap() {
  27   unsigned NumBlocks = MF->getNumBlockIDs();
  28   Seen.clear();
  29   Seen.resize(NumBlocks);
  30   EntryInfos.clear();
  31   Map.resize(NumBlocks);
  32 }
  33
  34 void LiveRangeCalc::reset(const MachineFunction *mf,
  35                           SlotIndexes *SI,
  36                           MachineDominatorTree *MDT,
  37                           VNInfo::Allocator *VNIA) {
  38   MF = mf;
  39   MRI = &MF->getRegInfo();
  40   Indexes = SI;
  41   DomTree = MDT;
  42   Alloc = VNIA;
  43   resetLiveOutMap();
  44   LiveIn.clear();
  45 }
  46
  47
  48 static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
  49                           LiveRange &LR, const MachineOperand &MO) {
  50   const MachineInstr &MI = *MO.getParent();
  51   SlotIndex DefIdx =
  52       Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber());
  53
  54   // Create the def in LR. This may find an existing def.
  55   LR.createDeadDef(DefIdx, Alloc);
  56 }
  57
  58 void LiveRangeCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
  59   assert(MRI && Indexes && "call reset() first");
  60
  61   // Step 1: Create minimal live segments for every definition of Reg.
  62   // Visit all def operands. If the same instruction has multiple defs of Reg,
  63   // createDeadDef() will deduplicate.
  64   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
  65   unsigned Reg = LI.reg;
  66   for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
  67     if (!MO.isDef() && !MO.readsReg())
  68       continue;
  69
  70     unsigned SubReg = MO.getSubReg();
  71     if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
  72       LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
  73                                         : MRI->getMaxLaneMaskForVReg(Reg);
  74       // If this is the first time we see a subregister def, initialize
  75       // subranges by creating a copy of the main range.
  76       if (!LI.hasSubRanges() && !LI.empty()) {
  77         LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
  78         LI.createSubRangeFrom(*Alloc, ClassMask, LI);
  79       }
  80
  81       LI.refineSubRanges(*Alloc, SubMask,
  82           [&MO, this](LiveInterval::SubRange &SR) {
  83         if (MO.isDef())
  84           createDeadDef(*Indexes, *Alloc, SR, MO);
  85       });
  86     }
  87
  88     // Create the def in the main liverange. We do not have to do this if
  89     // subranges are tracked as we recreate the main range later in this case.
  90     if (MO.isDef() && !LI.hasSubRanges())
  91       createDeadDef(*Indexes, *Alloc, LI, MO);
  92   }
  93
  94   // We may have created empty live ranges for partially undefined uses, we
  95   // can't keep them because we won't find defs in them later.
  96   LI.removeEmptySubRanges();
  97
  98   // Step 2: Extend live segments to all uses, constructing SSA form as
  99   // necessary.
 100   if (LI.hasSubRanges()) {
 101     for (LiveInterval::SubRange &S : LI.subranges()) {
 102       LiveRangeCalc SubLRC;
 103       SubLRC.reset(MF, Indexes, DomTree, Alloc);
 104       SubLRC.extendToUses(S, Reg, S.LaneMask, &LI);
 105     }
 106     LI.clear();
 107     constructMainRangeFromSubranges(LI);
 108   } else {
 109     resetLiveOutMap();
 110     extendToUses(LI, Reg, LaneBitmask::getAll());
 111   }
 112 }
 113
 114 void LiveRangeCalc::constructMainRangeFromSubranges(LiveInterval &LI) {
 115   // First create dead defs at all defs found in subranges.
 116   LiveRange &MainRange = LI;
 117   assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
 118          "Expect empty main liverange");
 119
 120   for (const LiveInterval::SubRange &SR : LI.subranges()) {
 121     for (const VNInfo *VNI : SR.valnos) {
 122       if (!VNI->isUnused() && !VNI->isPHIDef())
 123         MainRange.createDeadDef(VNI->def, *Alloc);
 124     }
 125   }
 126   resetLiveOutMap();
 127   extendToUses(MainRange, LI.reg, LaneBitmask::getAll(), &LI);
 128 }
 129
 130 void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) {
 131   assert(MRI && Indexes && "call reset() first");
 132
 133   // Visit all def operands. If the same instruction has multiple defs of Reg,
 134   // LR.createDeadDef() will deduplicate.
 135   for (MachineOperand &MO : MRI->def_operands(Reg))
 136     createDeadDef(*Indexes, *Alloc, LR, MO);
 137 }
 138
 139
 140 void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask Mask,
 141                                  LiveInterval *LI) {
 142   SmallVector<SlotIndex, 4> Undefs;
 143   if (LI != nullptr)
 144     LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes);
 145
 146   // Visit all operands that read Reg. This may include partial defs.
 147   bool IsSubRange = !Mask.all();
 148   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
 149   for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
 150     // Clear all kill flags. They will be reinserted after register allocation
 151     // by LiveIntervalAnalysis::addKillFlags().
 152     if (MO.isUse())
 153       MO.setIsKill(false);
 154     // MO::readsReg returns "true" for subregister defs. This is for keeping
 155     // liveness of the entire register (i.e. for the main range of the live
 156     // interval). For subranges, definitions of non-overlapping subregisters
 157     // do not count as uses.
 158     if (!MO.readsReg() || (IsSubRange && MO.isDef()))
 159       continue;
 160
 161     unsigned SubReg = MO.getSubReg();
 162     if (SubReg != 0) {
 163       LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
 164       if (MO.isDef())
 165         SLM = ~SLM;
 166       // Ignore uses not reading the current (sub)range.
 167       if ((SLM & Mask).none())
 168         continue;
 169     }
 170
 171     // Determine the actual place of the use.
 172     const MachineInstr *MI = MO.getParent();
 173     unsigned OpNo = (&MO - &MI->getOperand(0));
 174     SlotIndex UseIdx;
 175     if (MI->isPHI()) {
 176       assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
 177       // The actual place where a phi operand is used is the end of the pred
 178       // MBB. PHI operands are paired: (Reg, PredMBB).
 179       UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB());
 180     } else {
 181       // Check for early-clobber redefs.
 182       bool isEarlyClobber = false;
 183       unsigned DefIdx;
 184       if (MO.isDef())
 185         isEarlyClobber = MO.isEarlyClobber();
 186       else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
 187         // FIXME: This would be a lot easier if tied early-clobber uses also
 188         // had an early-clobber flag.
 189         isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
 190       }
 191       UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber);
 192     }
 193
 194     // MI is reading Reg. We may have visited MI before if it happens to be
 195     // reading Reg multiple times. That is OK, extend() is idempotent.
 196     extend(LR, UseIdx, Reg, Undefs);
 197   }
 198 }
 199
 200
 201 void LiveRangeCalc::updateFromLiveIns() {
 202   LiveRangeUpdater Updater;
 203   for (const LiveInBlock &I : LiveIn) {
 204     if (!I.DomNode)
 205       continue;
 206     MachineBasicBlock *MBB = I.DomNode->getBlock();
 207     assert(I.Value && "No live-in value found");
 208     SlotIndex Start, End;
 209     std::tie(Start, End) = Indexes->getMBBRange(MBB);
 210
 211     if (I.Kill.isValid())
 212       // Value is killed inside this block.
 213       End = I.Kill;
 214     else {
 215       // The value is live-through, update LiveOut as well.
 216       // Defer the Domtree lookup until it is needed.
 217       assert(Seen.test(MBB->getNumber()));
 218       Map[MBB] = LiveOutPair(I.Value, nullptr);
 219     }
 220     Updater.setDest(&I.LR);
 221     Updater.add(Start, End, I.Value);
 222   }
 223   LiveIn.clear();
 224 }
 225
 226 void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
 227                            ArrayRef<SlotIndex> Undefs) {
 228   assert(Use.isValid() && "Invalid SlotIndex");
 229   assert(Indexes && "Missing SlotIndexes");
 230   assert(DomTree && "Missing dominator tree");
 231
 232   MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot());
 233   assert(UseMBB && "No MBB at Use");
 234
 235   // Is there a def in the same MBB we can extend?
 236   auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);
 237   if (EP.first != nullptr || EP.second)
 238     return;
 239
 240   // Find the single reaching def, or determine if Use is jointly dominated by
 241   // multiple values, and we may need to create even more phi-defs to preserve
 242   // VNInfo SSA form.  Perform a search for all predecessor blocks where we
 243   // know the dominating VNInfo.
 244   if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))
 245     return;
 246
 247   // When there were multiple different values, we may need new PHIs.
 248   calculateValues();
 249 }
 250
 251
 252 // This function is called by a client after using the low-level API to add
 253 // live-out and live-in blocks.  The unique value optimization is not
 254 // available, SplitEditor::transferValues handles that case directly anyway.
 255 void LiveRangeCalc::calculateValues() {
 256   assert(Indexes && "Missing SlotIndexes");
 257   assert(DomTree && "Missing dominator tree");
 258   updateSSA();
 259   updateFromLiveIns();
 260 }
 261
 262
 263 bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
 264                                  MachineBasicBlock &MBB, BitVector &DefOnEntry,
 265                                  BitVector &UndefOnEntry) {
 266   unsigned BN = MBB.getNumber();
 267   if (DefOnEntry[BN])
 268     return true;
 269   if (UndefOnEntry[BN])
 270     return false;
 271
 272   auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {
 273     for (MachineBasicBlock *S : B.successors())
 274       DefOnEntry[S->getNumber()] = true;
 275     DefOnEntry[BN] = true;
 276     return true;
 277   };
 278
 279   SetVector<unsigned> WorkList;
 280   // Checking if the entry of MBB is reached by some def: add all predecessors
 281   // that are potentially defined-on-exit to the work list.
 282   for (MachineBasicBlock *P : MBB.predecessors())
 283     WorkList.insert(P->getNumber());
 284
 285   for (unsigned i = 0; i != WorkList.size(); ++i) {
 286     // Determine if the exit from the block is reached by some def.
 287     unsigned N = WorkList[i];
 288     MachineBasicBlock &B = *MF->getBlockNumbered(N);
 289     if (Seen[N]) {
 290       const LiveOutPair &LOB = Map[&B];
 291       if (LOB.first != nullptr && LOB.first != &UndefVNI)
 292         return MarkDefined(B);
 293     }
 294     SlotIndex Begin, End;
 295     std::tie(Begin, End) = Indexes->getMBBRange(&B);
 296     // Treat End as not belonging to B.
 297     // If LR has a segment S that starts at the next block, i.e. [End, ...),
 298     // std::upper_bound will return the segment following S. Instead,
 299     // S should be treated as the first segment that does not overlap B.
 300     LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(),
 301                                               End.getPrevSlot());
 302     if (UB != LR.begin()) {
 303       LiveRange::Segment &Seg = *std::prev(UB);
 304       if (Seg.end > Begin) {
 305         // There is a segment that overlaps B. If the range is not explicitly
 306         // undefined between the end of the segment and the end of the block,
 307         // treat the block as defined on exit. If it is, go to the next block
 308         // on the work list.
 309         if (LR.isUndefIn(Undefs, Seg.end, End))
 310           continue;
 311         return MarkDefined(B);
 312       }
 313     }
 314
 315     // No segment overlaps with this block. If this block is not defined on
 316     // entry, or it undefines the range, do not process its predecessors.
 317     if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
 318       UndefOnEntry[N] = true;
 319       continue;
 320     }
 321     if (DefOnEntry[N])
 322       return MarkDefined(B);
 323
 324     // Still don't know: add all predecessors to the work list.
 325     for (MachineBasicBlock *P : B.predecessors())
 326       WorkList.insert(P->getNumber());
 327   }
 328
 329   UndefOnEntry[BN] = true;
 330   return false;
 331 }
 332
 333 bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
 334                                      SlotIndex Use, unsigned PhysReg,
 335                                      ArrayRef<SlotIndex> Undefs) {
 336   unsigned UseMBBNum = UseMBB.getNumber();
 337
 338   // Block numbers where LR should be live-in.
 339   SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
 340
 341   // Remember if we have seen more than one value.
 342   bool UniqueVNI = true;
 343   VNInfo *TheVNI = nullptr;
 344
 345   bool FoundUndef = false;
 346
 347   // Using Seen as a visited set, perform a BFS for all reaching defs.
 348   for (unsigned i = 0; i != WorkList.size(); ++i) {
 349     MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
 350
 351 #ifndef NDEBUG
 352     if (MBB->pred_empty()) {
 353       MBB->getParent()->verify();
 354       errs() << "Use of " << PrintReg(PhysReg)
 355              << " does not have a corresponding definition on every path:\n";
 356       const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
 357       if (MI != nullptr)
 358         errs() << Use << " " << *MI;
 359       report_fatal_error("Use not jointly dominated by defs.");
 360     }
 361
 362     if (TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
 363         !MBB->isLiveIn(PhysReg)) {
 364       MBB->getParent()->verify();
 365       const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
 366       errs() << "The register " << PrintReg(PhysReg, TRI)
 367              << " needs to be live in to BB#" << MBB->getNumber()
 368              << ", but is missing from the live-in list.\n";
 369       report_fatal_error("Invalid global physical register");
 370     }
 371 #endif
 372     FoundUndef |= MBB->pred_empty();
 373
 374     for (MachineBasicBlock *Pred : MBB->predecessors()) {
 375        // Is this a known live-out block?
 376        if (Seen.test(Pred->getNumber())) {
 377          if (VNInfo *VNI = Map[Pred].first) {
 378            if (TheVNI && TheVNI != VNI)
 379              UniqueVNI = false;
 380            TheVNI = VNI;
 381          }
 382          continue;
 383        }
 384
 385        SlotIndex Start, End;
 386        std::tie(Start, End) = Indexes->getMBBRange(Pred);
 387
 388        // First time we see Pred.  Try to determine the live-out value, but set
 389        // it as null if Pred is live-through with an unknown value.
 390        auto EP = LR.extendInBlock(Undefs, Start, End);
 391        VNInfo *VNI = EP.first;
 392        FoundUndef |= EP.second;
 393        setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI);
 394        if (VNI) {
 395          if (TheVNI && TheVNI != VNI)
 396            UniqueVNI = false;
 397          TheVNI = VNI;
 398        }
 399        if (VNI || EP.second)
 400          continue;
 401
 402        // No, we need a live-in value for Pred as well
 403        if (Pred != &UseMBB)
 404          WorkList.push_back(Pred->getNumber());
 405        else
 406           // Loopback to UseMBB, so value is really live through.
 407          Use = SlotIndex();
 408     }
 409   }
 410
 411   LiveIn.clear();
 412   FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI);
 413   if (Undefs.size() > 0 && FoundUndef)
 414     UniqueVNI = false;
 415
 416   // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
 417   // neither require it. Skip the sorting overhead for small updates.
 418   if (WorkList.size() > 4)
 419     array_pod_sort(WorkList.begin(), WorkList.end());
 420
 421   // If a unique reaching def was found, blit in the live ranges immediately.
 422   if (UniqueVNI) {
 423     assert(TheVNI != nullptr && TheVNI != &UndefVNI);
 424     LiveRangeUpdater Updater(&LR);
 425     for (unsigned BN : WorkList) {
 426       SlotIndex Start, End;
 427       std::tie(Start, End) = Indexes->getMBBRange(BN);
 428       // Trim the live range in UseMBB.
 429       if (BN == UseMBBNum && Use.isValid())
 430         End = Use;
 431       else
 432         Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);
 433       Updater.add(Start, End, TheVNI);
 434     }
 435     return true;
 436   }
 437
 438   // Prepare the defined/undefined bit vectors.
 439   EntryInfoMap::iterator Entry;
 440   bool DidInsert;
 441   std::tie(Entry, DidInsert) = EntryInfos.insert(
 442       std::make_pair(&LR, std::make_pair(BitVector(), BitVector())));
 443   if (DidInsert) {
 444     // Initialize newly inserted entries.
 445     unsigned N = MF->getNumBlockIDs();
 446     Entry->second.first.resize(N);
 447     Entry->second.second.resize(N);
 448   }
 449   BitVector &DefOnEntry = Entry->second.first;
 450   BitVector &UndefOnEntry = Entry->second.second;
 451
 452   // Multiple values were found, so transfer the work list to the LiveIn array
 453   // where UpdateSSA will use it as a work list.
 454   LiveIn.reserve(WorkList.size());
 455   for (unsigned BN : WorkList) {
 456     MachineBasicBlock *MBB = MF->getBlockNumbered(BN);
 457     if (Undefs.size() > 0 &&
 458         !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))
 459       continue;
 460     addLiveInBlock(LR, DomTree->getNode(MBB));
 461     if (MBB == &UseMBB)
 462       LiveIn.back().Kill = Use;
 463   }
 464
 465   return false;
 466 }
 467
 468
 469 // This is essentially the same iterative algorithm that SSAUpdater uses,
 470 // except we already have a dominator tree, so we don't have to recompute it.
 471 void LiveRangeCalc::updateSSA() {
 472   assert(Indexes && "Missing SlotIndexes");
 473   assert(DomTree && "Missing dominator tree");
 474
 475   // Interate until convergence.
 476   bool Changed;
 477   do {
 478     Changed = false;
 479     // Propagate live-out values down the dominator tree, inserting phi-defs
 480     // when necessary.
 481     for (LiveInBlock &I : LiveIn) {
 482       MachineDomTreeNode *Node = I.DomNode;
 483       // Skip block if the live-in value has already been determined.
 484       if (!Node)
 485         continue;
 486       MachineBasicBlock *MBB = Node->getBlock();
 487       MachineDomTreeNode *IDom = Node->getIDom();
 488       LiveOutPair IDomValue;
 489
 490       // We need a live-in value to a block with no immediate dominator?
 491       // This is probably an unreachable block that has survived somehow.
 492       bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
 493
 494       // IDom dominates all of our predecessors, but it may not be their
 495       // immediate dominator. Check if any of them have live-out values that are
 496       // properly dominated by IDom. If so, we need a phi-def here.
 497       if (!needPHI) {
 498         IDomValue = Map[IDom->getBlock()];
 499
 500         // Cache the DomTree node that defined the value.
 501         if (IDomValue.first && IDomValue.first != &UndefVNI &&
 502             !IDomValue.second) {
 503           Map[IDom->getBlock()].second = IDomValue.second =
 504             DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
 505         }
 506
 507         for (MachineBasicBlock *Pred : MBB->predecessors()) {
 508           LiveOutPair &Value = Map[Pred];
 509           if (!Value.first || Value.first == IDomValue.first)
 510             continue;
 511           if (Value.first == &UndefVNI) {
 512             needPHI = true;
 513             break;
 514           }
 515
 516           // Cache the DomTree node that defined the value.
 517           if (!Value.second)
 518             Value.second =
 519               DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
 520
 521           // This predecessor is carrying something other than IDomValue.
 522           // It could be because IDomValue hasn't propagated yet, or it could be
 523           // because MBB is in the dominance frontier of that value.
 524           if (DomTree->dominates(IDom, Value.second)) {
 525             needPHI = true;
 526             break;
 527           }
 528         }
 529       }
 530
 531       // The value may be live-through even if Kill is set, as can happen when
 532       // we are called from extendRange. In that case LiveOutSeen is true, and
 533       // LiveOut indicates a foreign or missing value.
 534       LiveOutPair &LOP = Map[MBB];
 535
 536       // Create a phi-def if required.
 537       if (needPHI) {
 538         Changed = true;
 539         assert(Alloc && "Need VNInfo allocator to create PHI-defs");
 540         SlotIndex Start, End;
 541         std::tie(Start, End) = Indexes->getMBBRange(MBB);
 542         LiveRange &LR = I.LR;
 543         VNInfo *VNI = LR.getNextValue(Start, *Alloc);
 544         I.Value = VNI;
 545         // This block is done, we know the final value.
 546         I.DomNode = nullptr;
 547
 548         // Add liveness since updateFromLiveIns now skips this node.
 549         if (I.Kill.isValid()) {
 550           if (VNI)
 551             LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
 552         } else {
 553           if (VNI)
 554             LR.addSegment(LiveInterval::Segment(Start, End, VNI));
 555           LOP = LiveOutPair(VNI, Node);
 556         }
 557       } else if (IDomValue.first && IDomValue.first != &UndefVNI) {
 558         // No phi-def here. Remember incoming value.
 559         I.Value = IDomValue.first;
 560
 561         // If the IDomValue is killed in the block, don't propagate through.
 562         if (I.Kill.isValid())
 563           continue;
 564
 565         // Propagate IDomValue if it isn't killed:
 566         // MBB is live-out and doesn't define its own value.
 567         if (LOP.first == IDomValue.first)
 568           continue;
 569         Changed = true;
 570         LOP = IDomValue;
 571       }
 572     }
 573   } while (Changed);
 574 }