When extending a liveinterval by commuting, don't throw away the live ranges that...

[oota-llvm.git] / lib / CodeGen / RegAllocLinearScan.cpp

diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 6925de3abf155cdfe046b15c26ff1c78b3585e4b..d29f6da7fdff677769ed8c5f78402c39b46c48cb 100644 (file)
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -12,10 +12,11 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "regalloc"
-#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "PhysRegTracker.h"
 #include "VirtRegMap.h"
 #include "llvm/Function.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveStackAnalysis.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
@@ -67,6 +68,7 @@ namespace {
     MachineRegisterInfo *reginfo_;
     BitVector allocatableRegs_;
     LiveIntervals* li_;
+    LiveStacks* ls_;
     const MachineLoopInfo *loopInfo;
 
     /// handled_ - Intervals are added to the handled_ set in the order of their
@@ -103,6 +105,8 @@ namespace {
       // Make sure PassManager knows which analyses to make available
       // to coalescing and which analyses coalescing invalidates.
       AU.addRequiredTransitive<RegisterCoalescer>();
+      AU.addRequired<LiveStacks>();
+      AU.addPreserved<LiveStacks>();
       AU.addRequired<MachineLoopInfo>();
       AU.addPreserved<MachineLoopInfo>();
       AU.addPreservedID(MachineDominatorsID);
@@ -171,6 +175,9 @@ namespace {
   char RALinScan::ID = 0;
 }
 
+static RegisterPass<RALinScan>
+X("linearscan-regalloc", "Linear Scan Register Allocator");
+
 void RALinScan::ComputeRelatedRegClasses() {
   const TargetRegisterInfo &TRI = *tri_;
   
@@ -258,6 +265,7 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
   reginfo_ = &mf_->getRegInfo();
   allocatableRegs_ = tri_->getAllocatableSet(fn);
   li_ = &getAnalysis<LiveIntervals>();
+  ls_ = &getAnalysis<LiveStacks>();
   loopInfo = &getAnalysis<MachineLoopInfo>();
 
   // We don't run the coalescer here because we have no reason to
@@ -322,11 +330,13 @@ void RALinScan::linearScan()
     ++NumIters;
     DOUT << "\n*** CURRENT ***: " << *cur << '\n';
 
-    processActiveIntervals(cur->beginNumber());
-    processInactiveIntervals(cur->beginNumber());
+    if (!cur->empty()) {
+      processActiveIntervals(cur->beginNumber());
+      processInactiveIntervals(cur->beginNumber());
 
-    assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
-           "Can only allocate virtual registers!");
+      assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
+             "Can only allocate virtual registers!");
+    }
 
     // Allocating a virtual register. try to find a free
     // physical register or spill an interval (possibly this one) in order to
@@ -502,17 +512,50 @@ static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){
   }
 }
 
+/// addStackInterval - Create a LiveInterval for stack if the specified live
+/// interval has been spilled.
+static void addStackInterval(LiveInterval *cur, LiveStacks *ls_,
+                             LiveIntervals *li_, float &Weight,
+                             VirtRegMap &vrm_) {
+  int SS = vrm_.getStackSlot(cur->reg);
+  if (SS == VirtRegMap::NO_STACK_SLOT)
+    return;
+  LiveInterval &SI = ls_->getOrCreateInterval(SS);
+  SI.weight += Weight;
+
+  VNInfo *VNI;
+  if (SI.getNumValNums())
+    VNI = SI.getValNumInfo(0);
+  else
+    VNI = SI.getNextValue(~0U, 0, ls_->getVNInfoAllocator());
+
+  LiveInterval &RI = li_->getInterval(cur->reg);
+  // FIXME: This may be overly conservative.
+  SI.MergeRangesInAsValue(RI, VNI);
+}
+
 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
 /// spill.
 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);
+  if (cur->empty()) {
+    unsigned physReg = cur->preference;
+    if (!physReg)
+      physReg = *RC->allocation_order_begin(*mf_);
+    DOUT <<  tri_->getName(physReg) << '\n';
+    // Note the register is not really in use.
+    vrm_->assignVirt2Phys(cur->reg, physReg);
+    return;
+  }
+
   PhysRegTracker backupPrt = *prt_;
 
   std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
   unsigned StartPosition = cur->beginNumber();
-  const TargetRegisterClass *RC = reginfo_->getRegClass(cur->reg);
   const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
 
   // If this live interval is defined by a move instruction and its source is
@@ -525,7 +568,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
     if (vni->def && vni->def != ~1U && vni->def != ~0U) {
       MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
       unsigned SrcReg, DstReg;
-      if (tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) {
+      if (CopyMI && tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) {
         unsigned Reg = 0;
         if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
           Reg = SrcReg;
@@ -702,8 +745,10 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
   // linearscan.
   if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
     DOUT << "\t\t\tspilling(c): " << *cur << '\n';
+    float SSWeight;
     std::vector<LiveInterval*> added =
-      li_->addIntervalsForSpills(*cur, loopInfo, *vrm_);
+      li_->addIntervalsForSpills(*cur, loopInfo, *vrm_, SSWeight);
+    addStackInterval(cur, ls_, li_, SSWeight, *vrm_);
     if (added.empty())
       return;  // Early exit if all spills were folded.
 
@@ -754,8 +799,10 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
         cur->overlapsFrom(*i->first, i->second)) {
       DOUT << "\t\t\tspilling(a): " << *i->first << '\n';
       earliestStart = std::min(earliestStart, i->first->beginNumber());
+      float SSWeight;
       std::vector<LiveInterval*> newIs =
-        li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_);
+        li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_, SSWeight);
+      addStackInterval(i->first, ls_, li_, SSWeight, *vrm_);
       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
       spilled.insert(reg);
     }
@@ -767,8 +814,10 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
         cur->overlapsFrom(*i->first, i->second-1)) {
       DOUT << "\t\t\tspilling(i): " << *i->first << '\n';
       earliestStart = std::min(earliestStart, i->first->beginNumber());
+      float SSWeight;
       std::vector<LiveInterval*> newIs =
-        li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_);
+        li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_, SSWeight);
+      addStackInterval(i->first, ls_, li_, SSWeight, *vrm_);
       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
       spilled.insert(reg);
     }