X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLinearScan.cpp;h=a9444619fa5d239120a79ad663911d361e09af15;hb=b0000c376cf13ed63306622ab9642cfae49f074a;hp=4df172d40c7f61abb3b7fb75fbb36de85fd24d5f;hpb=a1566f2e12ce87a5bca30bc0189a0cdbb40136a4;p=oota-llvm.git

diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 4df172d40c7..a9444619fa5 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -26,8 +26,10 @@
 #include "llvm/CodeGen/RegisterCoalescer.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetOptions.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/ADT/EquivalenceClasses.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Debug.h"
@@ -48,30 +50,34 @@ NewHeuristic("new-spilling-heuristic",
              cl::desc("Use new spilling heuristic"),
              cl::init(false), cl::Hidden);
 
+static cl::opt<bool>
+PreSplitIntervals("pre-alloc-split",
+                  cl::desc("Pre-register allocation live interval splitting"),
+                  cl::init(false), cl::Hidden);
+
 static RegisterRegAlloc
-linearscanRegAlloc("linearscan", "  linear scan register allocator",
+linearscanRegAlloc("linearscan", "linear scan register allocator",
                    createLinearScanRegisterAllocator);
 
 namespace {
   struct VISIBILITY_HIDDEN RALinScan : public MachineFunctionPass {
     static char ID;
-    RALinScan() : MachineFunctionPass((intptr_t)&ID) {}
+    RALinScan() : MachineFunctionPass(&ID) {}
 
     typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
-    typedef std::vector<IntervalPtr> IntervalPtrs;
+    typedef SmallVector<IntervalPtr, 32> IntervalPtrs;
   private:
     /// RelatedRegClasses - This structure is built the first time a function is
     /// compiled, and keeps track of which register classes have registers that
     /// belong to multiple classes or have aliases that are in other classes.
     EquivalenceClasses<const TargetRegisterClass*> RelatedRegClasses;
-    std::map<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg;
+    DenseMap<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg;
 
     MachineFunction* mf_;
     MachineRegisterInfo* mri_;
     const TargetMachine* tm_;
     const TargetRegisterInfo* tri_;
     const TargetInstrInfo* tii_;
-    MachineRegisterInfo *reginfo_;
     BitVector allocatableRegs_;
     LiveIntervals* li_;
     LiveStacks* ls_;
@@ -94,7 +100,7 @@ namespace {
     IntervalPtrs inactive_;
 
     typedef std::priority_queue<LiveInterval*,
-                                std::vector<LiveInterval*>,
+                                SmallVector<LiveInterval*, 64>,
                                 greater_ptr<LiveInterval> > IntervalHeap;
     IntervalHeap unhandled_;
     std::auto_ptr<PhysRegTracker> prt_;
@@ -108,9 +114,13 @@ namespace {
 
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.addRequired<LiveIntervals>();
+      if (StrongPHIElim)
+        AU.addRequiredID(StrongPHIEliminationID);
       // Make sure PassManager knows which analyses to make available
       // to coalescing and which analyses coalescing invalidates.
       AU.addRequiredTransitive<RegisterCoalescer>();
+      if (PreSplitIntervals)
+        AU.addRequiredID(PreAllocSplittingID);
       AU.addRequired<LiveStacks>();
       AU.addPreserved<LiveStacks>();
       AU.addRequired<MachineLoopInfo>();
@@ -221,7 +231,7 @@ void RALinScan::ComputeRelatedRegClasses() {
   // belongs to, add info about aliases.  We don't need to do this for targets
   // without register aliases.
   if (HasAliases)
-    for (std::map<unsigned, const TargetRegisterClass*>::iterator
+    for (DenseMap<unsigned, const TargetRegisterClass*>::iterator
          I = OneClassForEachPhysReg.begin(), E = OneClassForEachPhysReg.end();
          I != E; ++I)
       for (const unsigned *AS = TRI.getAliasSet(I->first); *AS; ++AS)
@@ -239,12 +249,13 @@ unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) {
   if ((cur.preference && cur.preference == Reg) || !cur.containsOneValue())
     return Reg;
 
-  VNInfo *vni = cur.getValNumInfo(0);
+  VNInfo *vni = cur.begin()->valno;
   if (!vni->def || vni->def == ~1U || vni->def == ~0U)
     return Reg;
   MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
-  unsigned SrcReg, DstReg;
-  if (!CopyMI || !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg))
+  unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+  if (!CopyMI ||
+      !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg))
     return Reg;
   if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
     if (!vrm_->isAssignedReg(SrcReg))
@@ -255,7 +266,7 @@ unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) {
   if (Reg == SrcReg)
     return Reg;
 
-  const TargetRegisterClass *RC = reginfo_->getRegClass(cur.reg);
+  const TargetRegisterClass *RC = mri_->getRegClass(cur.reg);
   if (!RC->contains(SrcReg))
     return Reg;
 
@@ -278,7 +289,6 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
   tm_ = &fn.getTarget();
   tri_ = tm_->getRegisterInfo();
   tii_ = tm_->getInstrInfo();
-  reginfo_ = &mf_->getRegInfo();
   allocatableRegs_ = tri_->getAllocatableSet(fn);
   li_ = &getAnalysis<LiveIntervals>();
   ls_ = &getAnalysis<LiveStacks>();
@@ -322,12 +332,14 @@ void RALinScan::initIntervalSets()
          active_.empty() && inactive_.empty() &&
          "interval sets should be empty on initialization");
 
+  handled_.reserve(li_->getNumIntervals());
+
   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
-    if (TargetRegisterInfo::isPhysicalRegister(i->second.reg)) {
-      reginfo_->setPhysRegUsed(i->second.reg);
-      fixed_.push_back(std::make_pair(&i->second, i->second.begin()));
+    if (TargetRegisterInfo::isPhysicalRegister(i->second->reg)) {
+      mri_->setPhysRegUsed(i->second->reg);
+      fixed_.push_back(std::make_pair(i->second, i->second->begin()));
     } else
-      unhandled_.push(&i->second);
+      unhandled_.push(i->second);
   }
 }
 
@@ -385,11 +397,11 @@ void RALinScan::linearScan()
   MachineFunction::iterator EntryMBB = mf_->begin();
   SmallVector<MachineBasicBlock*, 8> LiveInMBBs;
   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
-    LiveInterval &cur = i->second;
+    LiveInterval &cur = *i->second;
     unsigned Reg = 0;
     bool isPhys = TargetRegisterInfo::isPhysicalRegister(cur.reg);
     if (isPhys)
-      Reg = i->second.reg;
+      Reg = cur.reg;
     else if (vrm_->isAssignedReg(cur.reg))
       Reg = attemptTrivialCoalescing(cur, vrm_->getPhys(cur.reg));
     if (!Reg)
@@ -400,7 +412,7 @@ void RALinScan::linearScan()
     for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end();
          I != E; ++I) {
       const LiveRange &LR = *I;
-      if (li_->findLiveInMBBs(LR, LiveInMBBs)) {
+      if (li_->findLiveInMBBs(LR.start, LR.end, LiveInMBBs)) {
         for (unsigned i = 0, e = LiveInMBBs.size(); i != e; ++i)
           if (LiveInMBBs[i] != EntryMBB)
             LiveInMBBs[i]->addLiveIn(Reg);
@@ -540,7 +552,7 @@ static void addStackInterval(LiveInterval *cur, LiveStacks *ls_,
   SI.weight += Weight;
 
   VNInfo *VNI;
-  if (SI.getNumValNums())
+  if (SI.hasAtLeastOneValue())
     VNI = SI.getValNumInfo(0);
   else
     VNI = SI.getNextValue(~0U, 0, ls_->getVNInfoAllocator());
@@ -658,7 +670,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
   DOUT << "\tallocating current interval: ";
 
   // This is an implicitly defined live interval, just assign any register.
-  const TargetRegisterClass *RC = reginfo_->getRegClass(cur->reg);
+  const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
   if (cur->empty()) {
     unsigned physReg = cur->preference;
     if (!physReg)
@@ -675,17 +687,18 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
   unsigned StartPosition = cur->beginNumber();
   const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
 
-  // If this live interval is defined by a move instruction and its source is
-  // assigned a physical register that is compatible with the target register
-  // class, then we should try to assign it the same register.
+  // If start of this live interval is defined by a move instruction and its
+  // source is assigned a physical register that is compatible with the target
+  // register class, then we should try to assign it the same register.
   // This can happen when the move is from a larger register class to a smaller
   // one, e.g. X86::mov32to32_. These move instructions are not coalescable.
-  if (!cur->preference && cur->containsOneValue()) {
-    VNInfo *vni = cur->getValNumInfo(0);
+  if (!cur->preference && cur->hasAtLeastOneValue()) {
+    VNInfo *vni = cur->begin()->valno;
     if (vni->def && vni->def != ~1U && vni->def != ~0U) {
       MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
-      unsigned SrcReg, DstReg;
-      if (CopyMI && tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) {
+      unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+      if (CopyMI &&
+          tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg)) {
         unsigned Reg = 0;
         if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
           Reg = SrcReg;
@@ -704,7 +717,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
     unsigned Reg = i->first->reg;
     assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
            "Can only allocate virtual registers!");
-    const TargetRegisterClass *RegRC = reginfo_->getRegClass(Reg);
+    const TargetRegisterClass *RegRC = mri_->getRegClass(Reg);
     // If this is not in a related reg class to the register we're allocating, 
     // don't check it.
     if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
@@ -852,9 +865,12 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
     // All registers must have inf weight. Just grab one!
     minReg = BestPhysReg ? BestPhysReg : *RC->allocation_order_begin(*mf_);
     if (cur->weight == HUGE_VALF ||
-        li_->getApproximateInstructionCount(*cur) == 1)
+        li_->getApproximateInstructionCount(*cur) == 0) {
       // Spill a physical register around defs and uses.
       li_->spillPhysRegAroundRegDefsUses(*cur, minReg, *vrm_);
+      assignRegOrStackSlotAtInterval(cur);
+      return;
+    }
   }
 
   // Find up to 3 registers to consider as spill candidates.
@@ -876,8 +892,9 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
   if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
     DOUT << "\t\t\tspilling(c): " << *cur << '\n';
     float SSWeight;
+    SmallVector<LiveInterval*, 8> spillIs;
     std::vector<LiveInterval*> added =
-      li_->addIntervalsForSpills(*cur, loopInfo, *vrm_, SSWeight);
+      li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_, SSWeight);
     addStackInterval(cur, ls_, li_, SSWeight, *vrm_);
     if (added.empty())
       return;  // Early exit if all spills were folded.
@@ -928,7 +945,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
     earliestStart = std::min(earliestStart, sli->beginNumber());
     float SSWeight;
     std::vector<LiveInterval*> newIs =
-      li_->addIntervalsForSpills(*sli, loopInfo, *vrm_, SSWeight);
+      li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_, SSWeight);
     addStackInterval(sli, ls_, li_, SSWeight, *vrm_);
     std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
     spilled.insert(sli->reg);
@@ -1007,7 +1024,7 @@ unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
   SmallVector<unsigned, 256> inactiveCounts;
   unsigned MaxInactiveCount = 0;
   
-  const TargetRegisterClass *RC = reginfo_->getRegClass(cur->reg);
+  const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
   const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
  
   for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
@@ -1018,7 +1035,7 @@ unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
 
     // 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);
+    const TargetRegisterClass *RegRC = mri_->getRegClass(reg);
     if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
       reg = vrm_->getPhys(reg);
       if (inactiveCounts.size() <= reg)
@@ -1034,7 +1051,8 @@ unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
   // If copy coalescer has assigned a "preferred" register, check if it's
   // available first.
   if (cur->preference) {
-    if (prt_->isRegAvail(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;