/// extendIntervalEndTo - This method is used when we want to extend the range
/// specified by I to end at the specified endpoint.  To do this, we should
/// merge and eliminate all ranges that this will overlap with.  The iterator is
/// not invalidated.
void LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) {
  assert(I != ranges.end() && "Not a valid interval!");
  VNInfo *ValNo = I->valno;
  SlotIndex OldEnd = I->end;

  // Search for the first interval that we can't merge with.
  Ranges::iterator MergeTo = next(I);
  for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) {
    assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
  }

  // If NewEnd was in the middle of an interval, make sure to get its endpoint.
  I->end = std::max(NewEnd, prior(MergeTo)->end);

  // Erase any dead ranges.
  ranges.erase(next(I), MergeTo);

  // Update kill info.
  ValNo->removeKills(OldEnd, I->end.getPrevSlot());

  // If the newly formed range now touches the range after it and if they have
  // the same value number, merge the two ranges into one range.
  Ranges::iterator Next = next(I);
  if (Next != ranges.end() && Next->start <= I->end && Next->valno == ValNo) {
    I->end = Next->end;
    ranges.erase(Next);
  }
}

/// analyzeSiblingValues - Trace values defined by sibling copies back to
/// something that isn't a sibling copy.
///
/// Keep track of values that may be rematerializable.
void InlineSpiller::analyzeSiblingValues() {
  SibValues.clear();

  // No siblings at all?
  if (Edit->getReg() == Original)
    return;

  LiveInterval &OrigLI = LIS.getInterval(Original);
  for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) {
    unsigned Reg = RegsToSpill[i];
    LiveInterval &LI = LIS.getInterval(Reg);
    for (LiveInterval::const_vni_iterator VI = LI.vni_begin(),
         VE = LI.vni_end(); VI != VE; ++VI) {
      VNInfo *VNI = *VI;
      if (VNI->isUnused())
        continue;
      MachineInstr *DefMI = 0;
      if (!VNI->isPHIDef()) {
       DefMI = LIS.getInstructionFromIndex(VNI->def);
       assert(DefMI && "No defining instruction");
      }
      // Check possible sibling copies.
      if (VNI->isPHIDef() || DefMI->isCopy()) {
        VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def);
        assert(OrigVNI && "Def outside original live range");
        if (OrigVNI->def != VNI->def)
          DefMI = traceSiblingValue(Reg, VNI, OrigVNI);
      }
      if (DefMI && Edit->checkRematerializable(VNI, DefMI, AA)) {
        DEBUG(dbgs() << "Value " << PrintReg(Reg) << ':' << VNI->id << '@'
                     << VNI->def << " may remat from " << *DefMI);
      }
    }
  }
}

VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
                                   VNInfo *ParentVNI,
                                   SlotIndex UseIdx,
                                   MachineBasicBlock &MBB,
                                   MachineBasicBlock::iterator I) {
  MachineInstr *CopyMI = 0;
  SlotIndex Def;
  LiveInterval *LI = Edit->get(RegIdx);

  // We may be trying to avoid interference that ends at a deleted instruction,
  // so always begin RegIdx 0 early and all others late.
  bool Late = RegIdx != 0;

  // Attempt cheap-as-a-copy rematerialization.
  LiveRangeEdit::Remat RM(ParentVNI);
  if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) {
    Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI, Late);
    ++NumRemats;
  } else {
    // Can't remat, just insert a copy from parent.
    CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
               .addReg(Edit->getReg());
    Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late)
            .getDefIndex();
    ++NumCopies;
  }

  // Define the value in Reg.
  VNInfo *VNI = defValue(RegIdx, ParentVNI, Def);
  VNI->setCopy(CopyMI);
  return VNI;
}

/// getCriticalExits - It may be necessary to partially break critical edges
/// leaving the loop if an exit block has phi uses of curli. Collect the exit
/// blocks that need special treatment into CriticalExits.
void SplitAnalysis::getCriticalExits(const SplitAnalysis::LoopBlocks &Blocks,
                                     BlockPtrSet &CriticalExits) {
  CriticalExits.clear();

  // A critical exit block contains a phi def of curli, and has a predecessor
  // that is not in the loop nor a loop predecessor.
  // For such an exit block, the edges carrying the new variable must be moved
  // to a new pre-exit block.
  for (BlockPtrSet::iterator I = Blocks.Exits.begin(), E = Blocks.Exits.end();
       I != E; ++I) {
    const MachineBasicBlock *Succ = *I;
    SlotIndex SuccIdx = lis_.getMBBStartIdx(Succ);
    VNInfo *SuccVNI = curli_->getVNInfoAt(SuccIdx);
    // This exit may not have curli live in at all. No need to split.
    if (!SuccVNI)
      continue;
    // If this is not a PHI def, it is either using a value from before the
    // loop, or a value defined inside the loop. Both are safe.
    if (!SuccVNI->isPHIDef() || SuccVNI->def.getBaseIndex() != SuccIdx)
      continue;
    // This exit block does have a PHI. Does it also have a predecessor that is
    // not a loop block or loop predecessor?
    for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(),
         PE = Succ->pred_end(); PI != PE; ++PI) {
      const MachineBasicBlock *Pred = *PI;
      if (Blocks.Loop.count(Pred) || Blocks.Preds.count(Pred))
        continue;
      // This is a critical exit block, and we need to split the exit edge.
      CriticalExits.insert(Succ);
      break;
    }
  }
}

/// RenumberValues - Renumber all values in order of appearance and delete the
/// remaining unused values.
void LiveRange::RenumberValues() {
  SmallPtrSet<VNInfo*, 8> Seen;
  valnos.clear();
  for (const Segment &S : segments) {
    VNInfo *VNI = S.valno;
    if (!Seen.insert(VNI).second)
      continue;
    assert(!VNI->isUnused() && "Unused valno used by live segment");
    VNI->id = (unsigned)valnos.size();
    valnos.push_back(VNI);
  }
}

/// InsertCopies - insert copies into MBB and all of its successors
void StrongPHIElimination::InsertCopies(MachineDomTreeNode* MDTN,
                                 SmallPtrSet<MachineBasicBlock*, 16>& visited) {
  MachineBasicBlock* MBB = MDTN->getBlock();
  visited.insert(MBB);
  
  std::set<unsigned> pushed;
  
  LiveIntervals& LI = getAnalysis<LiveIntervals>();
  // Rewrite register uses from Stacks
  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
      I != E; ++I) {
    if (I->isPHI())
      continue;
    
    for (unsigned i = 0; i < I->getNumOperands(); ++i)
      if (I->getOperand(i).isReg() &&
          Stacks[I->getOperand(i).getReg()].size()) {
        // Remove the live range for the old vreg.
        LiveInterval& OldInt = LI.getInterval(I->getOperand(i).getReg());
        LiveInterval::iterator OldLR =
          OldInt.FindLiveRangeContaining(LI.getInstructionIndex(I).getUseIndex());
        if (OldLR != OldInt.end())
          OldInt.removeRange(*OldLR, true);
        
        // Change the register
        I->getOperand(i).setReg(Stacks[I->getOperand(i).getReg()].back());
        
        // Add a live range for the new vreg
        LiveInterval& Int = LI.getInterval(I->getOperand(i).getReg());
        VNInfo* FirstVN = *Int.vni_begin();
        FirstVN->setHasPHIKill(false);
        LiveRange LR (LI.getMBBStartIdx(I->getParent()),
                      LI.getInstructionIndex(I).getUseIndex().getNextSlot(),
                      FirstVN);
        
        Int.addRange(LR);
      }
  }    
  
  // Schedule the copies for this block
  ScheduleCopies(MBB, pushed);
  
  // Recur down the dominator tree.
  for (MachineDomTreeNode::iterator I = MDTN->begin(),
       E = MDTN->end(); I != E; ++I)
    if (!visited.count((*I)->getBlock()))
      InsertCopies(*I, visited);
  
  // As we exit this block, pop the names we pushed while processing it
  for (std::set<unsigned>::iterator I = pushed.begin(), 
       E = pushed.end(); I != E; ++I)
    Stacks[*I].pop_back();
}

/// RenumberValues - Renumber all values in order of appearance and delete the
/// remaining unused values.
void LiveRange::RenumberValues() {
  SmallPtrSet<VNInfo*, 8> Seen;
  valnos.clear();
  for (const_iterator I = begin(), E = end(); I != E; ++I) {
    VNInfo *VNI = I->valno;
    if (!Seen.insert(VNI))
      continue;
    assert(!VNI->isUnused() && "Unused valno used by live segment");
    VNI->id = (unsigned)valnos.size();
    valnos.push_back(VNI);
  }
}

void LiveRangeEdit::scanRemattable(AliasAnalysis *aa) {
  for (LiveInterval::vni_iterator I = getParent().vni_begin(),
       E = getParent().vni_end(); I != E; ++I) {
    VNInfo *VNI = *I;
    if (VNI->isUnused())
      continue;
    MachineInstr *DefMI = LIS.getInstructionFromIndex(VNI->def);
    if (!DefMI)
      continue;
    checkRematerializable(VNI, DefMI, aa);
  }
  ScannedRemattable = true;
}

static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
                                 ShrinkToUsesWorkList &WorkList,
                                 const LiveRange &OldRange) {
  // Keep track of the PHIs that are in use.
  SmallPtrSet<VNInfo*, 8> UsedPHIs;
  // Blocks that have already been added to WorkList as live-out.
  SmallPtrSet<MachineBasicBlock*, 16> LiveOut;

  // Extend intervals to reach all uses in WorkList.
  while (!WorkList.empty()) {
    SlotIndex Idx = WorkList.back().first;
    VNInfo *VNI = WorkList.back().second;
    WorkList.pop_back();
    const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Idx.getPrevSlot());
    SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB);

    // Extend the live range for VNI to be live at Idx.
    if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) {
      assert(ExtVNI == VNI && "Unexpected existing value number");
      (void)ExtVNI;
      // Is this a PHIDef we haven't seen before?
      if (!VNI->isPHIDef() || VNI->def != BlockStart ||
          !UsedPHIs.insert(VNI).second)
        continue;
      // The PHI is live, make sure the predecessors are live-out.
      for (auto &Pred : MBB->predecessors()) {
        if (!LiveOut.insert(Pred).second)
          continue;
        SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
        // A predecessor is not required to have a live-out value for a PHI.
        if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
          WorkList.push_back(std::make_pair(Stop, PVNI));
      }
      continue;
    }

    // VNI is live-in to MBB.
    DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
    LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));

    // Make sure VNI is live-out from the predecessors.
    for (auto &Pred : MBB->predecessors()) {
      if (!LiveOut.insert(Pred).second)
        continue;
      SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
      assert(OldRange.getVNInfoBefore(Stop) == VNI &&
             "Wrong value out of predecessor");
      WorkList.push_back(std::make_pair(Stop, VNI));
    }
  }
}

void MachineVerifier::verifyLiveIntervals() {
  assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
  for (LiveIntervals::const_iterator LVI = LiveInts->begin(),
       LVE = LiveInts->end(); LVI != LVE; ++LVI) {
    const LiveInterval &LI = *LVI->second;
    assert(LVI->first == LI.reg && "Invalid reg to interval mapping");

    for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
         I!=E; ++I) {
      VNInfo *VNI = *I;
      const LiveRange *DefLR = LI.getLiveRangeContaining(VNI->def);

      if (!DefLR) {
        if (!VNI->isUnused()) {
          report("Valno not live at def and not marked unused", MF);
          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
        }
        continue;
      }

      if (VNI->isUnused())
        continue;

      if (DefLR->valno != VNI) {
        report("Live range at def has different valno", MF);
        DefLR->print(*OS);
        *OS << " should use valno #" << VNI->id << " in " << LI << '\n';
      }

    }

    for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) {
      const LiveRange &LR = *I;
      assert(LR.valno && "Live range has no valno");

      if (LR.valno->id >= LI.getNumValNums() ||
          LR.valno != LI.getValNumInfo(LR.valno->id)) {
        report("Foreign valno in live range", MF);
        LR.print(*OS);
        *OS << " has a valno not in " << LI << '\n';
      }

      if (LR.valno->isUnused()) {
        report("Live range valno is marked unused", MF);
        LR.print(*OS);
        *OS << " in " << LI << '\n';
      }

    }
  }
}

/// RenumberValues - Renumber all values in order of appearance and delete the
/// remaining unused values.
void LiveInterval::RenumberValues(LiveIntervals &lis) {
  SmallPtrSet<VNInfo*, 8> Seen;
  bool seenPHIDef = false;
  valnos.clear();
  for (const_iterator I = begin(), E = end(); I != E; ++I) {
    VNInfo *VNI = I->valno;
    if (!Seen.insert(VNI))
      continue;
    assert(!VNI->isUnused() && "Unused valno used by live range");
    VNI->id = (unsigned)valnos.size();
    valnos.push_back(VNI);
    VNI->setHasPHIKill(false);
    if (VNI->isPHIDef())
      seenPHIDef = true;
  }

  // Recompute phi kill flags.
  if (!seenPHIDef)
    return;
  for (const_vni_iterator I = vni_begin(), E = vni_end(); I != E; ++I) {
    VNInfo *VNI = *I;
    if (!VNI->isPHIDef())
      continue;
    const MachineBasicBlock *PHIBB = lis.getMBBFromIndex(VNI->def);
    assert(PHIBB && "No basic block for phi-def");
    for (MachineBasicBlock::const_pred_iterator PI = PHIBB->pred_begin(),
         PE = PHIBB->pred_end(); PI != PE; ++PI) {
      VNInfo *KVNI = getVNInfoAt(lis.getMBBEndIdx(*PI).getPrevSlot());
      if (KVNI)
        KVNI->setHasPHIKill(true);
    }
  }
}

/// enterIntvAtEnd - Enter openli at the end of MBB.
/// PhiMBB is a successor inside openli where a PHI value is created.
/// Currently, all entries must share the same PhiMBB.
void SplitEditor::enterIntvAtEnd(MachineBasicBlock &A, MachineBasicBlock &B) {
  assert(openli_ && "openIntv not called before enterIntvAtEnd");

  SlotIndex EndA = lis_.getMBBEndIdx(&A);
  VNInfo *CurVNIA = curli_->getVNInfoAt(EndA.getPrevIndex());
  if (!CurVNIA) {
    DEBUG(dbgs() << "    enterIntvAtEnd, curli not live out of BB#"
                 << A.getNumber() << ".\n");
    return;
  }

  // Add a phi kill value and live range out of A.
  VNInfo *VNIA = insertCopy(*openli_, A, A.getFirstTerminator());
  openli_->addRange(LiveRange(VNIA->def, EndA, VNIA));

  // FIXME: If this is the only entry edge, we don't need the extra PHI value.
  // FIXME: If there are multiple entry blocks (so not a loop), we need proper
  // SSA update.

  // Now look at the start of B.
  SlotIndex StartB = lis_.getMBBStartIdx(&B);
  SlotIndex EndB = lis_.getMBBEndIdx(&B);
  const LiveRange *CurB = curli_->getLiveRangeContaining(StartB);
  if (!CurB) {
    DEBUG(dbgs() << "    enterIntvAtEnd: curli not live in to BB#"
                 << B.getNumber() << ".\n");
    return;
  }

  VNInfo *VNIB = openli_->getVNInfoAt(StartB);
  if (!VNIB) {
    // Create a phi value.
    VNIB = openli_->getNextValue(SlotIndex(StartB, true), 0, false,
                                 lis_.getVNInfoAllocator());
    VNIB->setIsPHIDef(true);
    VNInfo *&mapVNI = valueMap_[CurB->valno];
    if (mapVNI) {
      // Multiple copies - must create PHI value.
      abort();
    } else {
      // This is the first copy of dupLR. Mark the mapping.
      mapVNI = VNIB;
    }

  }

  DEBUG(dbgs() << "    enterIntvAtEnd: " << *openli_ << '\n');
}

void LiveRangeCalc::createDeadDefs(LiveInterval *LI, unsigned Reg) {
  assert(MRI && Indexes && "call reset() first");

  // Visit all def operands. If the same instruction has multiple defs of Reg,
  // LI->createDeadDef() will deduplicate.
  for (MachineRegisterInfo::def_iterator
       I = MRI->def_begin(Reg), E = MRI->def_end(); I != E; ++I) {
    const MachineInstr *MI = &*I;
    // Find the corresponding slot index.
    SlotIndex Idx;
    if (MI->isPHI())
      // PHI defs begin at the basic block start index.
      Idx = Indexes->getMBBStartIdx(MI->getParent());
    else
      // Instructions are either normal 'r', or early clobber 'e'.
      Idx = Indexes->getInstructionIndex(MI)
        .getRegSlot(I.getOperand().isEarlyClobber());

    // Create the def in LI. This may find an existing def.
    VNInfo *VNI = LI->createDeadDef(Idx, *Alloc);
    VNI->setIsPHIDef(MI->isPHI());
  }
}

void MachineVerifier::verifyLiveIntervals() {
  assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
  for (LiveIntervals::const_iterator LVI = LiveInts->begin(),
       LVE = LiveInts->end(); LVI != LVE; ++LVI) {
    const LiveInterval &LI = *LVI->second;

    // Spilling and splitting may leave unused registers around. Skip them.
    if (MRI->use_empty(LI.reg))
      continue;

    // Physical registers have much weirdness going on, mostly from coalescing.
    // We should probably fix it, but for now just ignore them.
    if (TargetRegisterInfo::isPhysicalRegister(LI.reg))
      continue;

    assert(LVI->first == LI.reg && "Invalid reg to interval mapping");

    for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
         I!=E; ++I) {
      VNInfo *VNI = *I;
      const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def);

      if (!DefVNI) {
        if (!VNI->isUnused()) {
          report("Valno not live at def and not marked unused", MF);
          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
        }
        continue;
      }

      if (VNI->isUnused())
        continue;

      if (DefVNI != VNI) {
        report("Live range at def has different valno", MF);
        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
            << " where valno #" << DefVNI->id << " is live in " << LI << '\n';
        continue;
      }

      const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
      if (!MBB) {
        report("Invalid definition index", MF);
        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
            << " in " << LI << '\n';
        continue;
      }

      if (VNI->isPHIDef()) {
        if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
          report("PHIDef value is not defined at MBB start", MF);
          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
              << ", not at the beginning of BB#" << MBB->getNumber()
              << " in " << LI << '\n';
        }
      } else {
        // Non-PHI def.
        const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
        if (!MI) {
          report("No instruction at def index", MF);
          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
              << " in " << LI << '\n';
        } else if (!MI->modifiesRegister(LI.reg, TRI)) {
          report("Defining instruction does not modify register", MI);
          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
        }

        bool isEarlyClobber = false;
        if (MI) {
          for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(),
               MOE = MI->operands_end(); MOI != MOE; ++MOI) {
            if (MOI->isReg() && MOI->getReg() == LI.reg && MOI->isDef() &&
                MOI->isEarlyClobber()) {
              isEarlyClobber = true;
              break;
            }
          }
        }

        // Early clobber defs begin at USE slots, but other defs must begin at
        // DEF slots.
        if (isEarlyClobber) {
          if (!VNI->def.isUse()) {
            report("Early clobber def must be at a USE slot", MF);
            *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
                << " in " << LI << '\n';
          }
        } else if (!VNI->def.isDef()) {
          report("Non-PHI, non-early clobber def must be at a DEF slot", MF);
          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
              << " in " << LI << '\n';
        }
      }
    }

    for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) {
      const VNInfo *VNI = I->valno;
      assert(VNI && "Live range has no valno");

      if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) {
//.........这里部分代码省略.........

void MachineVerifier::verifyLiveIntervals() {
  assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);

    // Spilling and splitting may leave unused registers around. Skip them.
    if (MRI->reg_nodbg_empty(Reg))
      continue;

    if (!LiveInts->hasInterval(Reg)) {
      report("Missing live interval for virtual register", MF);
      *OS << PrintReg(Reg, TRI) << " still has defs or uses\n";
      continue;
    }

    const LiveInterval &LI = LiveInts->getInterval(Reg);
    assert(Reg == LI.reg && "Invalid reg to interval mapping");

    for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
         I!=E; ++I) {
      VNInfo *VNI = *I;
      const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def);

      if (!DefVNI) {
        if (!VNI->isUnused()) {
          report("Valno not live at def and not marked unused", MF);
          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
        }
        continue;
      }

      if (VNI->isUnused())
        continue;

      if (DefVNI != VNI) {
        report("Live range at def has different valno", MF);
        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
            << " where valno #" << DefVNI->id << " is live in " << LI << '\n';
        continue;
      }

      const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
      if (!MBB) {
        report("Invalid definition index", MF);
        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
            << " in " << LI << '\n';
        continue;
      }

      if (VNI->isPHIDef()) {
        if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
          report("PHIDef value is not defined at MBB start", MF);
          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
              << ", not at the beginning of BB#" << MBB->getNumber()
              << " in " << LI << '\n';
        }
      } else {
        // Non-PHI def.
        const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
        if (!MI) {
          report("No instruction at def index", MF);
          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
              << " in " << LI << '\n';
          continue;
        }

        bool hasDef = false;
        bool isEarlyClobber = false;
        for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
          if (!MOI->isReg() || !MOI->isDef())
            continue;
          if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
            if (MOI->getReg() != LI.reg)
              continue;
          } else {
            if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) ||
                !TRI->regsOverlap(LI.reg, MOI->getReg()))
              continue;
          }
          hasDef = true;
          if (MOI->isEarlyClobber())
            isEarlyClobber = true;
        }

        if (!hasDef) {
          report("Defining instruction does not modify register", MI);
          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
        }

        // Early clobber defs begin at USE slots, but other defs must begin at
        // DEF slots.
        if (isEarlyClobber) {
          if (!VNI->def.isEarlyClobber()) {
            report("Early clobber def must be at an early-clobber slot", MF);
            *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
                << " in " << LI << '\n';
          }
        } else if (!VNI->def.isRegister()) {
          report("Non-PHI, non-early clobber def must be at a register slot",
                 MF);
//.........这里部分代码省略.........

/// Update the live interval information to reflect the removal of the given
/// instruction from the program. As with "addInstrToLiveness", this function
/// is called while the program code is being changed.
void HexagonExpandCondsets::removeInstrFromLiveness(MachineInstr *MI) {
  SlotIndex MX = LIS->getInstructionIndex(*MI).getRegSlot();
  DEBUG(dbgs() << "removing instr\n  " << MX << "  " << *MI);

  // For each def in MI:
  // If MI starts a live segment, merge this segment with the previous segment.
  //
  for (auto &Op : MI->operands()) {
    if (!Op.isReg() || !Op.isDef())
      continue;
    unsigned DefR = Op.getReg();
    LiveInterval &LID = LIS->getInterval(DefR);
    LiveInterval::iterator LT = LID.FindSegmentContaining(MX);
    assert(LT != LID.end() && "Expecting live segments");
    DEBUG(dbgs() << "removing def at " << MX << " of " << PrintReg(DefR, TRI)
                 << " with interval\n  " << LID << "\n");
    if (LT->start != MX)
      continue;

    VNInfo *MVN = LT->valno;
    if (LT != LID.begin()) {
      // If the current live segment is not the first, the task is easy. If
      // the previous segment continues into the current block, extend it to
      // the end of the current one, and merge the value numbers.
      // Otherwise, remove the current segment, and make the end of it "undef".
      LiveInterval::iterator P = std::prev(LT);
      SlotIndex PE = P->end.isBlock() ? P->end.getPrevIndex() : P->end;
      MachineBasicBlock *MB = MI->getParent();
      MachineBasicBlock *PB = LIS->getMBBFromIndex(PE);
      if (PB != MB && !LIS->isLiveInToMBB(LID, MB)) {
        makeDefined(DefR, LT->end, false);
        LID.removeSegment(*LT);
      } else {
        // Make the segments adjacent, so that merge-vn can also merge the
        // segments.
        P->end = LT->start;
        makeUndead(DefR, P->valno->def);
        LID.MergeValueNumberInto(MVN, P->valno);
      }
    } else {
      LiveInterval::iterator N = std::next(LT);
      LiveInterval::iterator RmB = LT, RmE = N;
      while (N != LID.end()) {
        // Iterate until the first register-based definition is found
        // (i.e. skip all block-boundary entries).
        LiveInterval::iterator Next = std::next(N);
        if (N->start.isRegister()) {
          makeDefined(DefR, N->start, false);
          break;
        }
        if (N->end.isRegister()) {
          makeDefined(DefR, N->end, false);
          RmE = Next;
          break;
        }
        RmE = Next;
        N = Next;
      }
      // Erase the segments in one shot to avoid invalidating iterators.
      LID.segments.erase(RmB, RmE);
    }

    bool VNUsed = false;
    for (LiveInterval::iterator I = LID.begin(), E = LID.end(); I != E; ++I) {
      if (I->valno != MVN)
        continue;
      VNUsed = true;
      break;
    }
    if (!VNUsed)
      MVN->markUnused();

    DEBUG(dbgs() << "new interval: ");
    if (!LID.empty()) {
      DEBUG(dbgs() << LID << "\n");
      LID.verify();
    } else {
      DEBUG(dbgs() << "<empty>\n");
      LIS->removeInterval(DefR);
    }
  }

  // For uses there is nothing to do. The intervals will be updated via
  // shrinkToUses.
  SmallVector<unsigned,4> Uses;
  for (auto &Op : MI->operands()) {
    if (!Op.isReg() || !Op.isUse())
      continue;
    unsigned R = Op.getReg();
    if (!TargetRegisterInfo::isVirtualRegister(R))
      continue;
    Uses.push_back(R);
  }
  LIS->RemoveMachineInstrFromMaps(*MI);
  MI->eraseFromParent();
  for (unsigned i = 0, n = Uses.size(); i < n; ++i) {
    LiveInterval &LI = LIS->getInterval(Uses[i]);
//.........这里部分代码省略.........

void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI,
                                              MachineBasicBlock *MBB) {
  assert(PHI->isPHI());
  unsigned PHIColor = getPHIColor(PHI);

  for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
    MachineOperand &SrcMO = PHI->getOperand(i);

    // If a source is defined by an implicit def, there is no need to insert a
    // copy in the predecessor.
    if (SrcMO.isUndef())
      continue;

    unsigned SrcReg = SrcMO.getReg();
    assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
           "Machine PHI Operands must all be virtual registers!");

    MachineBasicBlock *PredBB = PHI->getOperand(i + 1).getMBB();
    unsigned SrcColor = getRegColor(SrcReg);

    // If neither the PHI nor the operand were isolated, then we only need to
    // set the phi-kill flag on the VNInfo at this PHI.
    if (PHIColor && SrcColor == PHIColor) {
      LiveInterval &SrcInterval = LI->getInterval(SrcReg);
      SlotIndex PredIndex = LI->getMBBEndIdx(PredBB);
      VNInfo *SrcVNI = SrcInterval.getVNInfoAt(PredIndex.getPrevIndex());
      assert(SrcVNI);
      SrcVNI->setHasPHIKill(true);
      continue;
    }

    unsigned CopyReg = 0;
    if (PHIColor) {
      SrcCopyMap::const_iterator I
        = InsertedSrcCopyMap.find(std::make_pair(PredBB, PHIColor));
      CopyReg
        = I != InsertedSrcCopyMap.end() ? I->second->getOperand(0).getReg() : 0;
    }

    if (!CopyReg) {
      const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
      CopyReg = MRI->createVirtualRegister(RC);

      MachineBasicBlock::iterator
        CopyInsertPoint = findPHICopyInsertPoint(PredBB, MBB, SrcReg);
      unsigned SrcSubReg = SrcMO.getSubReg();
      MachineInstr *CopyInstr = BuildMI(*PredBB,
                                        CopyInsertPoint,
                                        PHI->getDebugLoc(),
                                        TII->get(TargetOpcode::COPY),
                                        CopyReg).addReg(SrcReg, 0, SrcSubReg);
      LI->InsertMachineInstrInMaps(CopyInstr);

      // addLiveRangeToEndOfBlock() also adds the phikill flag to the VNInfo for
      // the newly added range.
      LI->addLiveRangeToEndOfBlock(CopyReg, CopyInstr);
      InsertedSrcCopySet.insert(std::make_pair(PredBB, SrcReg));

      addReg(CopyReg);
      if (PHIColor) {
        unionRegs(PHIColor, CopyReg);
        assert(getRegColor(CopyReg) != CopyReg);
      } else {
        PHIColor = CopyReg;
        assert(getRegColor(CopyReg) == CopyReg);
      }

      if (!InsertedSrcCopyMap.count(std::make_pair(PredBB, PHIColor)))
        InsertedSrcCopyMap[std::make_pair(PredBB, PHIColor)] = CopyInstr;
    }

    SrcMO.setReg(CopyReg);

    // If SrcReg is not live beyond the PHI, trim its interval so that it is no
    // longer live-in to MBB. Note that SrcReg may appear in other PHIs that are
    // processed later, but this is still correct to do at this point because we
    // never rely on LiveIntervals being correct while inserting copies.
    // FIXME: Should this just count uses at PHIs like the normal PHIElimination
    // pass does?
    LiveInterval &SrcLI = LI->getInterval(SrcReg);
    SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
    SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
    SlotIndex NextInstrIndex = PHIIndex.getNextIndex();
    if (SrcLI.liveAt(MBBStartIndex) && SrcLI.expiredAt(NextInstrIndex))
      SrcLI.removeRange(MBBStartIndex, PHIIndex, true);
  }

  unsigned DestReg = PHI->getOperand(0).getReg();
  unsigned DestColor = getRegColor(DestReg);

  if (PHIColor && DestColor == PHIColor) {
    LiveInterval &DestLI = LI->getInterval(DestReg);

    // Set the phi-def flag for the VN at this PHI.
    SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
    VNInfo *DestVNI = DestLI.getVNInfoAt(PHIIndex.getDefIndex());
    assert(DestVNI);
    DestVNI->setIsPHIDef(true);
  
    // Prior to PHI elimination, the live ranges of PHIs begin at their defining
//.........这里部分代码省略.........

void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
  ++NumFinished;

  // At this point, the live intervals in Edit contain VNInfos corresponding to
  // the inserted copies.

  // Add the original defs from the parent interval.
  for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(),
         E = Edit->getParent().vni_end(); I != E; ++I) {
    const VNInfo *ParentVNI = *I;
    if (ParentVNI->isUnused())
      continue;
    unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
    VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def);
    VNI->setIsPHIDef(ParentVNI->isPHIDef());
    VNI->setCopy(ParentVNI->getCopy());

    // Force rematted values to be recomputed everywhere.
    // The new live ranges may be truncated.
    if (Edit->didRematerialize(ParentVNI))
      for (unsigned i = 0, e = Edit->size(); i != e; ++i)
        forceRecompute(i, ParentVNI);
  }

  // Hoist back-copies to the complement interval when in spill mode.
  switch (SpillMode) {
  case SM_Partition:
    // Leave all back-copies as is.
    break;
  case SM_Size:
    hoistCopiesForSize();
    break;
  case SM_Speed:
    llvm_unreachable("Spill mode 'speed' not implemented yet");
    break;
  }

  // Transfer the simply mapped values, check if any are skipped.
  bool Skipped = transferValues();
  if (Skipped)
    extendPHIKillRanges();
  else
    ++NumSimple;

  // Rewrite virtual registers, possibly extending ranges.
  rewriteAssigned(Skipped);

  // Delete defs that were rematted everywhere.
  if (Skipped)
    deleteRematVictims();

  // Get rid of unused values and set phi-kill flags.
  for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I)
    (*I)->RenumberValues(LIS);

  // Provide a reverse mapping from original indices to Edit ranges.
  if (LRMap) {
    LRMap->clear();
    for (unsigned i = 0, e = Edit->size(); i != e; ++i)
      LRMap->push_back(i);
  }

  // Now check if any registers were separated into multiple components.
  ConnectedVNInfoEqClasses ConEQ(LIS);
  for (unsigned i = 0, e = Edit->size(); i != e; ++i) {
    // Don't use iterators, they are invalidated by create() below.
    LiveInterval *li = Edit->get(i);
    unsigned NumComp = ConEQ.Classify(li);
    if (NumComp <= 1)
      continue;
    DEBUG(dbgs() << "  " << NumComp << " components: " << *li << '\n');
    SmallVector<LiveInterval*, 8> dups;
    dups.push_back(li);
    for (unsigned j = 1; j != NumComp; ++j)
      dups.push_back(&Edit->create(LIS, VRM));
    ConEQ.Distribute(&dups[0], MRI);
    // The new intervals all map back to i.
    if (LRMap)
      LRMap->resize(Edit->size(), i);
  }

  // Calculate spill weight and allocation hints for new intervals.
  Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops);

  assert(!LRMap || LRMap->size() == Edit->size());
}

/// transferValues - Transfer all possible values to the new live ranges.
/// Values that were rematerialized are left alone, they need LRCalc.extend().
bool SplitEditor::transferValues() {
  bool Skipped = false;
  RegAssignMap::const_itera