Home | History | Annotate | Download | only in CodeGen 
      1 //===-- RegisterClassInfo.cpp - Dynamic Register Class Info ---------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements the RegisterClassInfo class which provides dynamic
     11 // information about target register classes. Callee saved and reserved
     12 // registers depends on calling conventions and other dynamic information, so
     13 // some things cannot be determined statically.
     14 //
     15 //===----------------------------------------------------------------------===//
     16 
     17 #define DEBUG_TYPE "regalloc"
     18 #include "llvm/CodeGen/RegisterClassInfo.h"
     19 #include "llvm/CodeGen/MachineFunction.h"
     20 #include "llvm/CodeGen/MachineRegisterInfo.h"
     21 #include "llvm/Support/CommandLine.h"
     22 #include "llvm/Support/Debug.h"
     23 #include "llvm/Support/raw_ostream.h"
     24 #include "llvm/Target/TargetMachine.h"
     25 
     26 using namespace llvm;
     27 
     28 static cl::opt<unsigned>
     29 StressRA("stress-regalloc", cl::Hidden, cl::init(0), cl::value_desc("N"),
     30          cl::desc("Limit all regclasses to N registers"));
     31 
     32 RegisterClassInfo::RegisterClassInfo() : Tag(0), MF(0), TRI(0), CalleeSaved(0)
     33 {}
     34 
     35 void RegisterClassInfo::runOnMachineFunction(const MachineFunction &mf) {
     36   bool Update = false;
     37   MF = &mf;
     38 
     39   // Allocate new array the first time we see a new target.
     40   if (MF->getTarget().getRegisterInfo() != TRI) {
     41     TRI = MF->getTarget().getRegisterInfo();
     42     RegClass.reset(new RCInfo[TRI->getNumRegClasses()]);
     43     Update = true;
     44   }
     45 
     46   // Does this MF have different CSRs?
     47   const MCPhysReg *CSR = TRI->getCalleeSavedRegs(MF);
     48   if (Update || CSR != CalleeSaved) {
     49     // Build a CSRNum map. Every CSR alias gets an entry pointing to the last
     50     // overlapping CSR.
     51     CSRNum.clear();
     52     CSRNum.resize(TRI->getNumRegs(), 0);
     53     for (unsigned N = 0; unsigned Reg = CSR[N]; ++N)
     54       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
     55         CSRNum[*AI] = N + 1; // 0 means no CSR, 1 means CalleeSaved[0], ...
     56     Update = true;
     57   }
     58   CalleeSaved = CSR;
     59 
     60   // Different reserved registers?
     61   const BitVector &RR = MF->getRegInfo().getReservedRegs();
     62   if (Reserved.size() != RR.size() || RR != Reserved) {
     63     Update = true;
     64     Reserved = RR;
     65   }
     66 
     67   // Invalidate cached information from previous function.
     68   if (Update)
     69     ++Tag;
     70 }
     71 
     72 /// compute - Compute the preferred allocation order for RC with reserved
     73 /// registers filtered out. Volatile registers come first followed by CSR
     74 /// aliases ordered according to the CSR order specified by the target.
     75 void RegisterClassInfo::compute(const TargetRegisterClass *RC) const {
     76   RCInfo &RCI = RegClass[RC->getID()];
     77 
     78   // Raw register count, including all reserved regs.
     79   unsigned NumRegs = RC->getNumRegs();
     80 
     81   if (!RCI.Order)
     82     RCI.Order.reset(new MCPhysReg[NumRegs]);
     83 
     84   unsigned N = 0;
     85   SmallVector<MCPhysReg, 16> CSRAlias;
     86   unsigned MinCost = 0xff;
     87   unsigned LastCost = ~0u;
     88   unsigned LastCostChange = 0;
     89 
     90   // FIXME: Once targets reserve registers instead of removing them from the
     91   // allocation order, we can simply use begin/end here.
     92   ArrayRef<MCPhysReg> RawOrder = RC->getRawAllocationOrder(*MF);
     93   for (unsigned i = 0; i != RawOrder.size(); ++i) {
     94     unsigned PhysReg = RawOrder[i];
     95     // Remove reserved registers from the allocation order.
     96     if (Reserved.test(PhysReg))
     97       continue;
     98     unsigned Cost = TRI->getCostPerUse(PhysReg);
     99     MinCost = std::min(MinCost, Cost);
    100 
    101     if (CSRNum[PhysReg])
    102       // PhysReg aliases a CSR, save it for later.
    103       CSRAlias.push_back(PhysReg);
    104     else {
    105       if (Cost != LastCost)
    106         LastCostChange = N;
    107       RCI.Order[N++] = PhysReg;
    108       LastCost = Cost;
    109     }
    110   }
    111   RCI.NumRegs = N + CSRAlias.size();
    112   assert (RCI.NumRegs <= NumRegs && "Allocation order larger than regclass");
    113 
    114   // CSR aliases go after the volatile registers, preserve the target's order.
    115   for (unsigned i = 0, e = CSRAlias.size(); i != e; ++i) {
    116     unsigned PhysReg = CSRAlias[i];
    117     unsigned Cost = TRI->getCostPerUse(PhysReg);
    118     if (Cost != LastCost)
    119       LastCostChange = N;
    120     RCI.Order[N++] = PhysReg;
    121     LastCost = Cost;
    122   }
    123 
    124   // Register allocator stress test.  Clip register class to N registers.
    125   if (StressRA && RCI.NumRegs > StressRA)
    126     RCI.NumRegs = StressRA;
    127 
    128   // Check if RC is a proper sub-class.
    129   if (const TargetRegisterClass *Super = TRI->getLargestLegalSuperClass(RC))
    130     if (Super != RC && getNumAllocatableRegs(Super) > RCI.NumRegs)
    131       RCI.ProperSubClass = true;
    132 
    133   RCI.MinCost = uint8_t(MinCost);
    134   RCI.LastCostChange = LastCostChange;
    135 
    136   DEBUG({
    137     dbgs() << "AllocationOrder(" << RC->getName() << ") = [";
    138     for (unsigned I = 0; I != RCI.NumRegs; ++I)
    139       dbgs() << ' ' << PrintReg(RCI.Order[I], TRI);
    140     dbgs() << (RCI.ProperSubClass ? " ] (sub-class)\n" : " ]\n");
    141   });
    142 
    143   // RCI is now up-to-date.
    144   RCI.Tag = Tag;
    145 }
    146 
    147