RegAllocLinearScan.cpp

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

/// findPhysReg - get the physical register, if any, assigned to this operand.
/// This may be an original physical register, or the physical register which
/// has been assigned to a virtual register.
unsigned RALinScan::findPhysReg(MachineOperand &MO) {
  unsigned PhysReg = MO.getReg();
  if (PhysReg && TargetRegisterInfo::isVirtualRegister(PhysReg)) {
    if (!vrm_->hasPhys(PhysReg))
      return 0;
    PhysReg = vrm_->getPhys(PhysReg);
  }
  return PhysReg;
}

/// noEarlyClobberConflict - see whether LiveInternal cur has a conflict with
/// hard reg HReg because of earlyclobbers.  
///
/// Earlyclobber operands may not be assigned the same register as
/// each other, or as earlyclobber-conflict operands (i.e. those that
/// are non-earlyclobbered inputs to an asm that also has earlyclobbers).
///
/// Thus there are two cases to check for:
/// 1.  cur->reg is an earlyclobber-conflict register and HReg is an
/// earlyclobber register in some asm that also has cur->reg as an input.
/// 2.  cur->reg is an earlyclobber register and HReg is an 
/// earlyclobber-conflict input, or a different earlyclobber register,
/// elsewhere in some asm.
/// In both cases HReg can be assigned by the user, or assigned early in
/// register allocation.
/// 
/// Dropping the distinction between earlyclobber and earlyclobber-conflict,
/// keeping only one bit, looks promising, but two earlyclobber-conflict
/// operands may be assigned the same register if they happen to contain the 
/// same value, and that implementation would prevent this.
///
bool RALinScan::noEarlyClobberConflict(LiveInterval *cur, unsigned HReg) {
  if (cur->overlapsEarlyClobber) {
    for (MachineRegisterInfo::use_iterator I = mri_->use_begin(cur->reg),
          E = mri_->use_end(); I!=E; ++I) {
      MachineInstr *MI = I.getOperand().getParent();
      if (MI->getOpcode()==TargetInstrInfo::INLINEASM) {
        for (int i = MI->getNumOperands()-1; i>=0; --i) {
          MachineOperand &MO = MI->getOperand(i);
          if (MO.isRegister() && MO.isEarlyClobber()) {
            unsigned PhysReg = findPhysReg(MO);
            if (HReg==PhysReg) {
              DOUT << "  earlyclobber conflict: " << 
                  "%reg" << cur->reg << ", " << tri_->getName(HReg) << "\n\t";
              return false;
            }
          }
        }
      }
    }
  }
  if (cur->isEarlyClobber) {
    for (MachineRegisterInfo::def_iterator I = mri_->def_begin(cur->reg),
          E = mri_->def_end(); I!=E; ++I) {
      MachineInstr *MI = I.getOperand().getParent();
      if (MI->getOpcode()==TargetInstrInfo::INLINEASM) {
        // make sure cur->reg is really clobbered in this instruction.
        bool earlyClobberFound = false, overlapFound = false;
        for (int i = MI->getNumOperands()-1; i>=0; --i) {
          MachineOperand &MO = MI->getOperand(i);
          if (MO.isRegister()) {
            if ((MO.overlapsEarlyClobber() || MO.isEarlyClobber())) {
              unsigned PhysReg = findPhysReg(MO);
              if (HReg==PhysReg)
                overlapFound = true;
            }
            if (MO.isEarlyClobber() && cur->reg==MO.getReg())
              earlyClobberFound = true;
          }
        }
        if (earlyClobberFound && overlapFound) {
          DOUT << "  earlyclobber conflict: " << 
                  "%reg" << cur->reg << ", " << tri_->getName(HReg) << "\n\t";
          return false;
        }
      }
    }
  }
  return true;
}

/// 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 = mri_->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 = mri_->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) && 
        noEarlyClobberConflict(cur, *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] &&
        noEarlyClobberConflict(cur, *I)) {
      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();
}