- Change the horrible N^2 isRegReDefinedByTwoAddr. Now callers must supply the operand index of def machineoperand and at most one full scan of non-implicit operands is needed.

- Change local register allocator to use the new isRegReDefinedByTwoAddr instead of reinventing the wheel.


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

5 files changed, 24 insertions, 37 deletions

diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 6a2fd9eb70..8efcbee290 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -328,14 +328,14 @@ namespace llvm {
     /// handleVirtualRegisterDef)
     void handleRegisterDef(MachineBasicBlock *MBB,
                            MachineBasicBlock::iterator MI, unsigned MIIdx,
-                           MachineOperand& MO);
+                           MachineOperand& MO, unsigned MOIdx);
 
     /// handleVirtualRegisterDef - update intervals for a virtual
     /// register def
     void handleVirtualRegisterDef(MachineBasicBlock *MBB,
                                   MachineBasicBlock::iterator MI,
                                   unsigned MIIdx, MachineOperand& MO,
-                                  LiveInterval& interval);
+                                  unsigned MOIdx, LiveInterval& interval);
 
     /// handlePhysicalRegisterDef - update intervals for a physical register
     /// def.
diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index 77e5e76521..88116d2bb2 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -207,9 +207,9 @@ public:
   /// none is found.
   int findFirstPredOperandIdx() const;
   
-  /// isRegReDefinedByTwoAddr - Returns true if the Reg re-definition is due
-  /// to two addr elimination.
-  bool isRegReDefinedByTwoAddr(unsigned Reg) const;
+  /// isRegReDefinedByTwoAddr - Given the defined register and the operand index,
+  /// check if the register def is a re-definition due to two addr elimination.
+  bool isRegReDefinedByTwoAddr(unsigned Reg, unsigned DefIdx) const;
 
   /// copyKillDeadInfo - Copies kill / dead operand properties from MI.
   ///
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 7b0eaeb341..974571944a 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -298,6 +298,7 @@ void LiveIntervals::printRegName(unsigned reg) const {
 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
                                              MachineBasicBlock::iterator mi,
                                              unsigned MIIdx, MachineOperand& MO,
+                                             unsigned MOIdx,
                                              LiveInterval &interval) {
   DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
   LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
@@ -390,7 +391,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
     // must be due to phi elimination or two addr elimination.  If this is
     // the result of two address elimination, then the vreg is one of the
     // def-and-use register operand.
-    if (mi->isRegReDefinedByTwoAddr(interval.reg)) {
+    if (mi->isRegReDefinedByTwoAddr(interval.reg, MOIdx)) {
       // If this is a two-address definition, then we have already processed
       // the live range.  The only problem is that we didn't realize there
       // are actually two values in the live interval.  Because of this we
@@ -553,9 +554,10 @@ exit:
 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
                                       MachineBasicBlock::iterator MI,
                                       unsigned MIIdx,
-                                      MachineOperand& MO) {
+                                      MachineOperand& MO,
+                                      unsigned MOIdx) {
   if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
-    handleVirtualRegisterDef(MBB, MI, MIIdx, MO, 
+    handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
                              getOrCreateInterval(MO.getReg()));
   else if (allocatableRegs_[MO.getReg()]) {
     MachineInstr *CopyMI = NULL;
@@ -660,7 +662,7 @@ void LiveIntervals::computeIntervals() {
         MachineOperand &MO = MI->getOperand(i);
         // handle register defs - build intervals
         if (MO.isRegister() && MO.getReg() && MO.isDef())
-          handleRegisterDef(MBB, MI, MIIndex, MO);
+          handleRegisterDef(MBB, MI, MIIndex, MO, i);
       }
       
       MIIndex += InstrSlots::NUM;
diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp
index e9a8c63abd..6f616b4202 100644
--- a/lib/CodeGen/MachineInstr.cpp
+++ b/lib/CodeGen/MachineInstr.cpp
@@ -623,20 +623,15 @@ int MachineInstr::findFirstPredOperandIdx() const {
   return -1;
 }
   
-/// isRegReDefinedByTwoAddr - Returns true if the Reg re-definition is due
-/// to two addr elimination.
-bool MachineInstr::isRegReDefinedByTwoAddr(unsigned Reg) const {
+/// isRegReDefinedByTwoAddr - Given the defined register and the operand index,
+/// check if the register def is a re-definition due to two addr elimination.
+bool MachineInstr::isRegReDefinedByTwoAddr(unsigned Reg, unsigned DefIdx) const{
   const TargetInstrDesc &TID = getDesc();
-  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
-    const MachineOperand &MO1 = getOperand(i);
-    if (MO1.isRegister() && MO1.isDef() && MO1.getReg() == Reg) {
-      for (unsigned j = i+1; j < e; ++j) {
-        const MachineOperand &MO2 = getOperand(j);
-        if (MO2.isRegister() && MO2.isUse() && MO2.getReg() == Reg &&
-            TID.getOperandConstraint(j, TOI::TIED_TO) == (int)i)
-          return true;
-      }
-    }
+  for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
+    const MachineOperand &MO = getOperand(i);
+    if (MO.isRegister() && MO.isUse() && MO.getReg() == Reg &&
+        TID.getOperandConstraint(i, TOI::TIED_TO) == (int)DefIdx)
+      return true;
   }
   return false;
 }
diff --git a/lib/CodeGen/RegAllocLocal.cpp b/lib/CodeGen/RegAllocLocal.cpp
index c1dacb6cb8..d3e38d043a 100644
--- a/lib/CodeGen/RegAllocLocal.cpp
+++ b/lib/CodeGen/RegAllocLocal.cpp
@@ -604,25 +604,15 @@ void RALocal::ComputeLocalLiveness(MachineBasicBlock& MBB) {
         if (last != LastUseDef.end()) {
           // Check if this is a two address instruction.  If so, then
           // the def does not kill the use.
-          if (last->second.first == I) {
-            bool isTwoAddr = false;
-            for (unsigned j = i+1, je = I->getDesc().getNumOperands();
-                j < je; ++j) {
-              const MachineOperand &MO2 = I->getOperand(j);
-              if (MO2.isRegister() && MO2.isUse() &&
-                  MO2.getReg() == MO.getReg() &&
-                  I->getDesc().getOperandConstraint(j, TOI::TIED_TO) == (int)i)
-                isTwoAddr = true;
-            }
-
-            if (isTwoAddr) continue;
-          }
+          if (last->second.first == I &&
+              I->isRegReDefinedByTwoAddr(MO.getReg(), i))
+            continue;
           
           MachineOperand& lastUD =
                       last->second.first->getOperand(last->second.second);
           if (lastUD.isDef())
             lastUD.setIsDead(true);
-          else if (lastUD.isUse())
+          else
             lastUD.setIsKill(true);
         }
         
@@ -677,7 +667,7 @@ void RALocal::ComputeLocalLiveness(MachineBasicBlock& MBB) {
     if (isPhysReg || !usedOutsideBlock) {
       if (MO.isUse())
         MO.setIsKill(true);
-      else if (MI->getOperand(idx).isDef())
+      else
         MO.setIsDead(true);
     }
   }