LiveIntervalAnalysis.cpp

        else {
          MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
          int LdSlot = 0;
          bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
          // If the rematerializable def is a load, also try to fold it.
          if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad())
            Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
                                          Ops, isLoadSS, LdSlot, VReg);
          if (!Folded) {
            unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
            if (ImpUse) {
              // Re-matting an instruction with virtual register use. Add the
              // register as an implicit use on the use MI and mark the register
              // interval as unspillable.
              LiveInterval &ImpLi = getInterval(ImpUse);
              ImpLi.markNotSpillable();
              MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
            }
          }
        }
      }
      // If folding is not possible / failed, then tell the spiller to issue a
      // load / rematerialization for us.
      if (Folded)
        nI.removeRange(index.getLoadIndex(), index.getDefIndex());
      else
        vrm.addRestorePoint(VReg, MI);
    }
    Id = RestoreMBBs.find_next(Id);
  }

  // Finalize intervals: add kills, finalize spill weights, and filter out
  // dead intervals.
  std::vector<LiveInterval*> RetNewLIs;
  for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
    LiveInterval *LI = NewLIs[i];
    if (!LI->empty()) {
      LI->weight /= SlotIndex::NUM * getApproximateInstructionCount(*LI);
      if (!AddedKill.count(LI)) {
        LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
        SlotIndex LastUseIdx = LR->end.getBaseIndex();
        MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
        int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
        assert(UseIdx != -1);
        if (!LastUse->isRegTiedToDefOperand(UseIdx)) {
          LastUse->getOperand(UseIdx).setIsKill();
          vrm.addKillPoint(LI->reg, LastUseIdx);
        }
      }
      RetNewLIs.push_back(LI);
    }
  }

  handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
  normalizeSpillWeights(RetNewLIs);
  return RetNewLIs;
}

/// hasAllocatableSuperReg - Return true if the specified physical register has
/// any super register that's allocatable.
bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
  for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
    if (allocatableRegs_[*AS] && hasInterval(*AS))
      return true;
  return false;
}

/// getRepresentativeReg - Find the largest super register of the specified
/// physical register.
unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
  // Find the largest super-register that is allocatable. 
  unsigned BestReg = Reg;
  for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
    unsigned SuperReg = *AS;
    if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
      BestReg = SuperReg;
      break;
    }
  }
  return BestReg;
}

/// getNumConflictsWithPhysReg - Return the number of uses and defs of the
/// specified interval that conflicts with the specified physical register.
unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
                                                   unsigned PhysReg) const {
  unsigned NumConflicts = 0;
  const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
  for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
         E = mri_->reg_end(); I != E; ++I) {
    MachineOperand &O = I.getOperand();
    MachineInstr *MI = O.getParent();
    if (MI->isDebugValue())
      continue;
    SlotIndex Index = getInstructionIndex(MI);
    if (pli.liveAt(Index))
      ++NumConflicts;
  }
  return NumConflicts;
}

/// spillPhysRegAroundRegDefsUses - Spill the specified physical register
/// around all defs and uses of the specified interval. Return true if it
/// was able to cut its interval.
bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
                                            unsigned PhysReg, VirtRegMap &vrm) {
  unsigned SpillReg = getRepresentativeReg(PhysReg);

  for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
    // If there are registers which alias PhysReg, but which are not a
    // sub-register of the chosen representative super register. Assert
    // since we can't handle it yet.
    assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) ||
           tri_->isSuperRegister(*AS, SpillReg));

  bool Cut = false;
  SmallVector<unsigned, 4> PRegs;
  if (hasInterval(SpillReg))
    PRegs.push_back(SpillReg);
  else {
    SmallSet<unsigned, 4> Added;
    for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS)
      if (Added.insert(*AS) && hasInterval(*AS)) {
        PRegs.push_back(*AS);
        for (const unsigned* ASS = tri_->getSubRegisters(*AS); *ASS; ++ASS)
          Added.insert(*ASS);
      }
  }

  SmallPtrSet<MachineInstr*, 8> SeenMIs;
  for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
         E = mri_->reg_end(); I != E; ++I) {
    MachineOperand &O = I.getOperand();
    MachineInstr *MI = O.getParent();
    if (MI->isDebugValue() || SeenMIs.count(MI))
      continue;
    SeenMIs.insert(MI);
    SlotIndex Index = getInstructionIndex(MI);
    for (unsigned i = 0, e = PRegs.size(); i != e; ++i) {
      unsigned PReg = PRegs[i];
      LiveInterval &pli = getInterval(PReg);
      if (!pli.liveAt(Index))
        continue;
      vrm.addEmergencySpill(PReg, MI);
      SlotIndex StartIdx = Index.getLoadIndex();
      SlotIndex EndIdx = Index.getNextIndex().getBaseIndex();
      if (pli.isInOneLiveRange(StartIdx, EndIdx)) {
        pli.removeRange(StartIdx, EndIdx);
        Cut = true;
      } else {
        std::string msg;
        raw_string_ostream Msg(msg);
        Msg << "Ran out of registers during register allocation!";
        if (MI->isInlineAsm()) {
          Msg << "\nPlease check your inline asm statement for invalid "
              << "constraints:\n";
          MI->print(Msg, tm_);
        }
        report_fatal_error(Msg.str());
      }
      for (const unsigned* AS = tri_->getSubRegisters(PReg); *AS; ++AS) {
        if (!hasInterval(*AS))
          continue;
        LiveInterval &spli = getInterval(*AS);
        if (spli.liveAt(Index))
          spli.removeRange(Index.getLoadIndex(),
                           Index.getNextIndex().getBaseIndex());
      }
    }
  }
  return Cut;
}

LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
                                                  MachineInstr* startInst) {
  LiveInterval& Interval = getOrCreateInterval(reg);
  VNInfo* VN = Interval.getNextValue(
    SlotIndex(getInstructionIndex(startInst).getDefIndex()),
    startInst, true, getVNInfoAllocator());
  VN->setHasPHIKill(true);
  VN->kills.push_back(indexes_->getTerminatorGap(startInst->getParent()));
  LiveRange LR(
     SlotIndex(getInstructionIndex(startInst).getDefIndex()),
     getMBBEndIdx(startInst->getParent()), VN);
  Interval.addRange(LR);
  
  return LR;
}