LiveIntervalAnalysis.cpp

            }
          }
        }
      }
      // 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()) {
      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);

  DEBUG(dbgs() << "spillPhysRegAroundRegDefsUses " << tri_->getName(PhysReg)
               << " represented by " << tri_->getName(SpillReg) << '\n');

  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);
  for (const unsigned *SR = tri_->getSubRegisters(SpillReg); *SR; ++SR)
    if (hasInterval(*SR))
      PRegs.push_back(*SR);

  DEBUG({
    dbgs() << "Trying to spill:";
    for (unsigned i = 0, e = PRegs.size(); i != e; ++i)
      dbgs() << ' ' << tri_->getName(PRegs[i]);
    dbgs() << '\n';
  });

  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);
    bool LiveReg = false;
    for (unsigned i = 0, e = PRegs.size(); i != e; ++i) {
      unsigned PReg = PRegs[i];
      LiveInterval &pli = getInterval(PReg);
      if (!pli.liveAt(Index))
        continue;
      LiveReg = true;
      SlotIndex StartIdx = Index.getLoadIndex();
      SlotIndex EndIdx = Index.getNextIndex().getBaseIndex();
      if (!pli.isInOneLiveRange(StartIdx, EndIdx)) {
        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());
      }
      pli.removeRange(StartIdx, EndIdx);
      LiveReg = true;
    }
    if (!LiveReg)
      continue;
    DEBUG(dbgs() << "Emergency spill around " << Index << '\t' << *MI);
    vrm.addEmergencySpill(SpillReg, MI);
    Cut = true;
  }
  return Cut;
}

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

  return LR;
}