It has finally happened. Spiller is now using live interval info.

This fixes a very subtle bug. vr defined by an implicit_def is allowed overlap with any register since it doesn't actually modify anything. However, if it's used as a two-address use, its live range can be extended and it can be spilled. The spiller must take care not to emit a reload for the vn number that's defined by the implicit_def. This is both a correctness and performance issue.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69743 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 68 insertions, 40 deletions

diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index f6a1c48..6691c2e 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -1304,7 +1304,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
 
     // Update stack slot spill weight if we are splitting.
     float Weight = getSpillWeight(HasDef, HasUse, loopDepth);
-      if (!TrySplit)
+    if (!TrySplit)
       SSWeight += Weight;
 
     // Create a new virtual register for the spill interval.
@@ -1338,7 +1338,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
           HasUse = false;
           HasDef = false;
           CanFold = false;
-          if (isRemoved(MI)) {
+          if (isNotInMIMap(MI)) {
             SSWeight -= Weight;
             break;
           }
@@ -1393,7 +1393,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
     if (DefIsReMat && ImpUse)
       MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
 
-    // create a new register interval for this spill / remat.
+    // Create a new register interval for this spill / remat.
     LiveInterval &nI = getOrCreateInterval(NewVReg);
     if (CreatedNewVReg) {
       NewLIs.push_back(&nI);
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index c738315..2e65b3f 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -345,7 +345,7 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
   linearScan();
 
   // Rewrite spill code and update the PhysRegsUsed set.
-  spiller_->runOnMachineFunction(*mf_, *vrm_);
+  spiller_->runOnMachineFunction(*mf_, *vrm_, li_);
 
   assert(unhandled_.empty() && "Unhandled live intervals remain!");
   fixed_.clear();
diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp
index adab2b0..748fae4 100644
--- a/lib/CodeGen/RegAllocPBQP.cpp
+++ b/lib/CodeGen/RegAllocPBQP.cpp
@@ -854,7 +854,7 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
 
   // Run spiller
   std::auto_ptr<Spiller> spiller(createSpiller());
-  spiller->runOnMachineFunction(*mf, *vrm);
+  spiller->runOnMachineFunction(*mf, *vrm, lis);
 
   return true;
 }
diff --git a/lib/CodeGen/Spiller.cpp b/lib/CodeGen/Spiller.cpp
index 92bb785..26366d6 100644
--- a/lib/CodeGen/Spiller.cpp
+++ b/lib/CodeGen/Spiller.cpp
@@ -23,6 +23,7 @@ STATISTIC(NumDRM     , "Number of re-materializable defs elided");
 STATISTIC(NumStores  , "Number of stores added");
 STATISTIC(NumPSpills , "Number of physical register spills");
 STATISTIC(NumOmitted , "Number of reloads omited");
+STATISTIC(NumAvoided , "Number of reloads deemed unnecessary");
 STATISTIC(NumCopified, "Number of available reloads turned into copies");
 STATISTIC(NumReMats  , "Number of re-materialization");
 STATISTIC(NumLoads   , "Number of loads added");
@@ -50,7 +51,8 @@ SpillerOpt("spiller",
 
 Spiller::~Spiller() {}
 
-bool SimpleSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) {
+bool SimpleSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
+                                         LiveIntervals* LIs) {
   DOUT << "********** REWRITE MACHINE CODE **********\n";
   DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
   const TargetMachine &TM = MF.getTarget();
@@ -521,7 +523,8 @@ unsigned ReuseInfo::GetRegForReload(unsigned PhysReg, MachineInstr *MI,
 // Local Spiller Implementation  //
 // ***************************** //
 
-bool LocalSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) {
+bool LocalSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
+                                        LiveIntervals* LIs) {
   RegInfo = &MF.getRegInfo(); 
   TRI = MF.getTarget().getRegisterInfo();
   TII = MF.getTarget().getInstrInfo();
@@ -555,7 +558,7 @@ bool LocalSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) {
        DFI != E; ++DFI) {
     MachineBasicBlock *MBB = *DFI;
     if (!EarlyVisited.count(MBB))
-      RewriteMBB(*MBB, VRM, Spills, RegKills, KillOps);
+      RewriteMBB(*MBB, VRM, LIs, Spills, RegKills, KillOps);
 
     // If this MBB is the only predecessor of a successor. Keep the
     // availability information and visit it next.
@@ -571,7 +574,7 @@ bool LocalSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) {
         MBB = SinglePredSuccs[0];
         if (!Visited.count(MBB) && EarlyVisited.insert(MBB)) {
           Spills.AddAvailableRegsToLiveIn(*MBB, RegKills, KillOps);
-          RewriteMBB(*MBB, VRM, Spills, RegKills, KillOps);
+          RewriteMBB(*MBB, VRM, LIs, Spills, RegKills, KillOps);
         }
       }
     } while (MBB);
@@ -1109,6 +1112,7 @@ void LocalSpiller::TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist,
 /// rewriteMBB - Keep track of which spills are available even after the
 /// register allocator is done with them.  If possible, avid reloading vregs.
 void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
+                              LiveIntervals *LIs,
                               AvailableSpills &Spills, BitVector &RegKills,
                               std::vector<MachineOperand*> &KillOps) {
   DOUT << "\n**** Local spiller rewriting MBB '"
@@ -1339,6 +1343,22 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
       if (!MO.isUse())
         continue;  // Handle defs in the loop below (handle use&def here though)
 
+      bool AvoidReload = false;
+      if (LIs->hasInterval(VirtReg)) {
+        LiveInterval &LI = LIs->getInterval(VirtReg);
+        if (!LI.liveAt(LIs->getUseIndex(LI.beginNumber())))
+          // Must be defined by an implicit def. It should not be spilled. Note,
+          // this is for correctness reason. e.g.
+          // 8   %reg1024<def> = IMPLICIT_DEF
+          // 12  %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
+          // The live range [12, 14) are not part of the r1024 live interval since
+          // it's defined by an implicit def. It will not conflicts with live
+          // interval of r1025. Now suppose both registers are spilled, you can
+          // easily see a situation where both registers are reloaded before
+          // the INSERT_SUBREG and both target registers that would overlap.
+          AvoidReload = true;
+      }
+
       bool DoReMat = VRM.isReMaterialized(VirtReg);
       int SSorRMId = DoReMat
         ? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg);
@@ -1357,14 +1377,14 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
       //       = EXTRACT_SUBREG fi#1
       // fi#1 is available in EDI, but it cannot be reused because it's not in
       // the right register file.
-      if (PhysReg &&
+      if (PhysReg && !AvoidReload &&
           (SubIdx || MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)) {
         const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
         if (!RC->contains(PhysReg))
           PhysReg = 0;
       }
 
-      if (PhysReg) {
+      if (PhysReg && !AvoidReload) {
         // This spilled operand might be part of a two-address operand.  If this
         // is the case, then changing it will necessarily require changing the 
         // def part of the instruction as well.  However, in some cases, we
@@ -1513,34 +1533,39 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
       
       RegInfo->setPhysRegUsed(PhysReg);
       ReusedOperands.markClobbered(PhysReg);
-      if (DoReMat) {
-        ReMaterialize(MBB, MII, PhysReg, VirtReg, TII, TRI, VRM);
-      } else {
-        const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
-        TII->loadRegFromStackSlot(MBB, &MI, PhysReg, SSorRMId, RC);
-        MachineInstr *LoadMI = prior(MII);
-        VRM.addSpillSlotUse(SSorRMId, LoadMI);
-        ++NumLoads;
-      }
-      // This invalidates PhysReg.
-      Spills.ClobberPhysReg(PhysReg);
-
-      // Any stores to this stack slot are not dead anymore.
-      if (!DoReMat)
-        MaybeDeadStores[SSorRMId] = NULL;
-      Spills.addAvailable(SSorRMId, PhysReg);
-      // Assumes this is the last use. IsKill will be unset if reg is reused
-      // unless it's a two-address operand.
-      if (!MI.isRegTiedToDefOperand(i) &&
-          KilledMIRegs.count(VirtReg) == 0) {
-        MI.getOperand(i).setIsKill();
-        KilledMIRegs.insert(VirtReg);
+      if (AvoidReload)
+        ++NumAvoided;
+      else {
+        if (DoReMat) {
+          ReMaterialize(MBB, MII, PhysReg, VirtReg, TII, TRI, VRM);
+        } else {
+          const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
+          TII->loadRegFromStackSlot(MBB, &MI, PhysReg, SSorRMId, RC);
+          MachineInstr *LoadMI = prior(MII);
+          VRM.addSpillSlotUse(SSorRMId, LoadMI);
+          ++NumLoads;
+        }
+        // This invalidates PhysReg.
+        Spills.ClobberPhysReg(PhysReg);
+
+        // Any stores to this stack slot are not dead anymore.
+        if (!DoReMat)
+          MaybeDeadStores[SSorRMId] = NULL;
+        Spills.addAvailable(SSorRMId, PhysReg);
+        // Assumes this is the last use. IsKill will be unset if reg is reused
+        // unless it's a two-address operand.
+        if (!MI.isRegTiedToDefOperand(i) &&
+            KilledMIRegs.count(VirtReg) == 0) {
+          MI.getOperand(i).setIsKill();
+          KilledMIRegs.insert(VirtReg);
+        }
+
+        UpdateKills(*prior(MII), RegKills, KillOps, TRI);
+        DOUT << '\t' << *prior(MII);
       }
       unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
       MI.getOperand(i).setReg(RReg);
       MI.getOperand(i).setSubReg(0);
-      UpdateKills(*prior(MII), RegKills, KillOps, TRI);
-      DOUT << '\t' << *prior(MII);
     }
 
     // Ok - now we can remove stores that have been confirmed dead.
diff --git a/lib/CodeGen/Spiller.h b/lib/CodeGen/Spiller.h
index c0d0837..f00831f 100644
--- a/lib/CodeGen/Spiller.h
+++ b/lib/CodeGen/Spiller.h
@@ -17,6 +17,7 @@
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Streams.h"
 #include "llvm/Function.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
@@ -37,8 +38,8 @@ namespace llvm {
   /// virtual registers to stack slots, rewriting the code.
   struct Spiller {
     virtual ~Spiller();
-    virtual bool runOnMachineFunction(MachineFunction &MF,
-                                      VirtRegMap &VRM) = 0;
+    virtual bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
+                                      LiveIntervals* LIs) = 0;
   };
 
   /// createSpiller - Create an return a spiller object, as specified on the
@@ -49,7 +50,8 @@ namespace llvm {
   
   // Simple Spiller Implementation
   struct VISIBILITY_HIDDEN SimpleSpiller : public Spiller {
-    bool runOnMachineFunction(MachineFunction& mf, VirtRegMap &VRM);
+    bool runOnMachineFunction(MachineFunction& mf, VirtRegMap &VRM,
+                              LiveIntervals* LIs);
   };
   
   // ************************************************************************ //
@@ -287,7 +289,8 @@ namespace llvm {
     BitVector AllocatableRegs;
     DenseMap<MachineInstr*, unsigned> DistanceMap;
   public:
-    bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM);
+    bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
+                              LiveIntervals* LI);
   private:
     void TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist,
                           unsigned Reg, BitVector &RegKills,
@@ -329,7 +332,7 @@ namespace llvm {
                              VirtRegMap &VRM);
 
     void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
-                    AvailableSpills &Spills,
+                    LiveIntervals *LIs, AvailableSpills &Spills,
                     BitVector &RegKills, std::vector<MachineOperand*> &KillOps);
   };
 }