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.

llvm-svn: 69743

7 files changed, 96 insertions, 43 deletions

diff --git a/llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h b/llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 33837a2ca23..b54cf6468d2 100644
--- a/llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -300,9 +300,9 @@ namespace llvm {
       r2iMap_.erase(I);
     }
 
-    /// isRemoved - returns true if the specified machine instr has been
-    /// removed.
-    bool isRemoved(MachineInstr* instr) const {
+    /// isNotInMIMap - returns true if the specified machine instr has been
+    /// removed or was never entered in the map.
+    bool isNotInMIMap(MachineInstr* instr) const {
       return !mi2iMap_.count(instr);
     }
 
diff --git a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp b/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
index f6a1c48ec8c..6691c2edeee 100644
--- a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/llvm/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/llvm/lib/CodeGen/RegAllocLinearScan.cpp b/llvm/lib/CodeGen/RegAllocLinearScan.cpp
index c7383154841..2e65b3f9371 100644
--- a/llvm/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/llvm/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/llvm/lib/CodeGen/RegAllocPBQP.cpp b/llvm/lib/CodeGen/RegAllocPBQP.cpp
index adab2b01d80..748fae48639 100644
--- a/llvm/lib/CodeGen/RegAllocPBQP.cpp
+++ b/llvm/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/llvm/lib/CodeGen/Spiller.cpp b/llvm/lib/CodeGen/Spiller.cpp
index 92bb785de60..26366d6042e 100644
--- a/llvm/lib/CodeGen/Spiller.cpp
+++ b/llvm/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/llvm/lib/CodeGen/Spiller.h b/llvm/lib/CodeGen/Spiller.h
index c0d08379604..f00831f7e84 100644
--- a/llvm/lib/CodeGen/Spiller.h
+++ b/llvm/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);
   };
 }
diff --git a/llvm/test/CodeGen/X86/2009-04-21-NoReloadImpDef.ll b/llvm/test/CodeGen/X86/2009-04-21-NoReloadImpDef.ll
new file mode 100644
index 00000000000..750dba77214
--- /dev/null
+++ b/llvm/test/CodeGen/X86/2009-04-21-NoReloadImpDef.ll
@@ -0,0 +1,25 @@
+; RUN: llvm-as < %s | llc -mtriple=i386-apple-darwin10.0 -relocation-model=pic -disable-fp-elim -mattr=-sse41,-sse3,+sse2 | \
+; RUN:   %prcontext {14} 2 | grep {(%ebp)} | count 1
+; rdar://6808032
+
+define void @update(i8** %args_list) nounwind {
+entry:
+	%cmp.i = icmp eq i32 0, 0		; <i1> [#uses=1]
+	br i1 %cmp.i, label %if.then.i, label %test_cl.exit
+
+if.then.i:		; preds = %entry
+	%val = load <16 x i8> addrspace(1)* null		; <<16 x i8>> [#uses=8]
+	%tmp10.i = shufflevector <16 x i8> <i8 0, i8 0, i8 0, i8 undef, i8 0, i8 undef, i8 0, i8 undef, i8 undef, i8 undef, i8 0, i8 0, i8 0, i8 undef, i8 undef, i8 undef>, <16 x i8> %val, <16 x i32> <i32 0, i32 1, i32 2, i32 undef, i32 4, i32 undef, i32 6, i32 undef, i32 29, i32 undef, i32 10, i32 11, i32 12, i32 undef, i32 undef, i32 undef>		; <<16 x i8>> [#uses=1]
+	%tmp17.i = shufflevector <16 x i8> %tmp10.i, <16 x i8> %val, <16 x i32> <i32 0, i32 1, i32 2, i32 18, i32 4, i32 undef, i32 6, i32 undef, i32 8, i32 undef, i32 10, i32 11, i32 12, i32 undef, i32 undef, i32 undef>		; <<16 x i8>> [#uses=1]
+	%tmp24.i = shufflevector <16 x i8> %tmp17.i, <16 x i8> %val, <16 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 24, i32 6, i32 undef, i32 8, i32 undef, i32 10, i32 11, i32 12, i32 undef, i32 undef, i32 undef>		; <<16 x i8>> [#uses=1]
+	%tmp31.i = shufflevector <16 x i8> %tmp24.i, <16 x i8> %val, <16 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 undef, i32 8, i32 undef, i32 10, i32 11, i32 12, i32 21, i32 undef, i32 undef>		; <<16 x i8>> [#uses=1]
+	%tmp38.i = shufflevector <16 x i8> %tmp31.i, <16 x i8> %val, <16 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 27, i32 8, i32 undef, i32 10, i32 11, i32 12, i32 13, i32 undef, i32 undef>		; <<16 x i8>> [#uses=1]
+	%tmp45.i = shufflevector <16 x i8> %tmp38.i, <16 x i8> %val, <16 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 undef, i32 10, i32 11, i32 12, i32 13, i32 29, i32 undef>		; <<16 x i8>> [#uses=1]
+	%tmp52.i = shufflevector <16 x i8> %tmp45.i, <16 x i8> %val, <16 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 21, i32 10, i32 11, i32 12, i32 13, i32 14, i32 undef>		; <<16 x i8>> [#uses=1]
+	%tmp59.i = shufflevector <16 x i8> %tmp52.i, <16 x i8> %val, <16 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 20>		; <<16 x i8>> [#uses=1]
+	store <16 x i8> %tmp59.i, <16 x i8> addrspace(1)* null
+	ret void
+
+test_cl.exit:		; preds = %entry
+	ret void
+}