RegAllocLinearScan.cpp

  // merge added with unhandled
  for (unsigned i = 0, e = added.size(); i != e; ++i)
    unhandled_.push(added[i]);
}

/// getFreePhysReg - return a free physical register for this virtual register
/// interval if we have one, otherwise return 0.
unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
  SmallVector<unsigned, 256> inactiveCounts;
  unsigned MaxInactiveCount = 0;
  
  const TargetRegisterClass *RC = reginfo_->getRegClass(cur->reg);
  const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
 
  for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
       i != e; ++i) {
    unsigned reg = i->first->reg;
    assert(TargetRegisterInfo::isVirtualRegister(reg) &&
           "Can only allocate virtual registers!");

    // If this is not in a related reg class to the register we're allocating, 
    // don't check it.
    const TargetRegisterClass *RegRC = reginfo_->getRegClass(reg);
    if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
      reg = vrm_->getPhys(reg);
      if (inactiveCounts.size() <= reg)
        inactiveCounts.resize(reg+1);
      ++inactiveCounts[reg];
      MaxInactiveCount = std::max(MaxInactiveCount, inactiveCounts[reg]);
    }
  }

  unsigned FreeReg = 0;
  unsigned FreeRegInactiveCount = 0;

  // If copy coalescer has assigned a "preferred" register, check if it's
  // available first.
  if (cur->preference) {
    if (prt_->isRegAvail(cur->preference) && RC->contains(cur->preference)) {
      DOUT << "\t\tassigned the preferred register: "
           << tri_->getName(cur->preference) << "\n";
      return cur->preference;
    } else
      DOUT << "\t\tunable to assign the preferred register: "
           << tri_->getName(cur->preference) << "\n";
  }

  // Scan for the first available register.
  TargetRegisterClass::iterator I = RC->allocation_order_begin(*mf_);
  TargetRegisterClass::iterator E = RC->allocation_order_end(*mf_);
  assert(I != E && "No allocatable register in this register class!");
  for (; I != E; ++I)
    if (prt_->isRegAvail(*I) && 
        li_->noEarlyclobberConflict(cur->reg, *vrm_, *I)) {
      FreeReg = *I;
      if (FreeReg < inactiveCounts.size())
        FreeRegInactiveCount = inactiveCounts[FreeReg];
      else
        FreeRegInactiveCount = 0;
      break;
    }

  // If there are no free regs, or if this reg has the max inactive count,
  // return this register.
  if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) return FreeReg;
  
  // Continue scanning the registers, looking for the one with the highest
  // inactive count.  Alkis found that this reduced register pressure very
  // slightly on X86 (in rev 1.94 of this file), though this should probably be
  // reevaluated now.
  for (; I != E; ++I) {
    unsigned Reg = *I;
    if (prt_->isRegAvail(Reg) && Reg < inactiveCounts.size() &&
        FreeRegInactiveCount < inactiveCounts[Reg] &&
        li_->noEarlyclobberConflict(cur->reg, *vrm_, Reg)) {
      FreeReg = Reg;
      FreeRegInactiveCount = inactiveCounts[Reg];
      if (FreeRegInactiveCount == MaxInactiveCount)
        break;    // We found the one with the max inactive count.
    }
  }
  
  return FreeReg;
}

FunctionPass* llvm::createLinearScanRegisterAllocator() {
  return new RALinScan();
}