Remove AsmThatEarlyClobber etc. from LiveIntervalAnalysis

and redo as linked list walk.  Logic moved into RA.
Per review feedback.



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

5 files changed, 86 insertions, 96 deletions

diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index 5e5e4b1957..8b9eb530ad 100644
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -105,12 +105,17 @@ namespace llvm {
                          // if the top bits is set, it represents a stack slot.
     unsigned preference; // preferred register to allocate for this interval
     float weight;        // weight of this interval
+    bool isEarlyClobber;
+    bool overlapsEarlyClobber;
     Ranges ranges;       // the ranges in which this register is live
     VNInfoList valnos;   // value#'s
 
   public:
-    LiveInterval(unsigned Reg, float Weight, bool IsSS = false)
-      : reg(Reg), preference(0), weight(Weight) {
+    LiveInterval(unsigned Reg, float Weight, bool IsSS = false, 
+                 bool IsEarlyClobber = false, bool OverlapsEarlyClobber = false)
+      : reg(Reg), preference(0), weight(Weight), 
+        isEarlyClobber(IsEarlyClobber), 
+        overlapsEarlyClobber(OverlapsEarlyClobber) {
       if (IsSS)
         reg = reg | (1U << (sizeof(unsigned)*8-1));
     }
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 31eadcf7f8..1910649bfe 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -65,22 +65,6 @@ namespace llvm {
     AliasAnalysis *aa_;
     LiveVariables* lv_;
 
-    /// AsmsWithEarlyClobber - maps a virtual register number to all the
-    /// inline asm's that have the register marked earlyclobber.
-    /// 
-    std::multimap<unsigned, MachineInstr*> AsmsThatEarlyClobber;
-
-    /// AsmsWithEarlyClobberConflict - maps a virtual register number
-    /// to all the inline asm's that have earlyclobber operands elsewhere
-    /// and use the register as a (non-earlyclobber) input.
-    ///
-    /// Note: earlyclobber operands may not be assigned the same register as
-    /// each other, or as earlyclobber-conflict operands.  However two
-    /// earlyclobber-conflict operands may be assigned the same register if
-    /// they happen to contain the same value.
-    /// 
-    std::multimap<unsigned, MachineInstr*> AsmsWithEarlyClobberConflict;
-
     /// Special pool allocator for VNInfo's (LiveInterval val#).
     ///
     BumpPtrAllocator VNInfoAllocator;
@@ -353,11 +337,6 @@ namespace llvm {
     unsigned getNumConflictsWithPhysReg(const LiveInterval &li,
                                         unsigned PhysReg) const;
 
-    /// noEarlyclobberConflict - see whether virtual reg VReg has a conflict
-    /// with hard reg HReg because HReg is used as an earlyclobber register in
-    /// asm that also has VReg live into or across it.
-    bool noEarlyclobberConflict(unsigned VReg, VirtRegMap &vrm, unsigned HReg);
-
     /// computeNumbering - Compute the index numbering.
     void computeNumbering();
 
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index ff430d71c7..06e9722b97 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -686,6 +686,10 @@ void LiveInterval::print(std::ostream &OS,
     OS << "%reg" << reg;
 
   OS << ',' << weight;
+  if (isEarlyClobber)
+    OS << ",earlyclobber";
+  if (overlapsEarlyClobber)
+    OS << ",overlapsearly";
 
   if (empty())
     OS << " EMPTY";
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index cb83194d97..2a23d492c7 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -674,8 +674,6 @@ exit:
 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 /// which a variable is live
 void LiveIntervals::computeIntervals() { 
-  AsmsThatEarlyClobber.clear();
-  AsmsWithEarlyClobberConflict.clear();
 
   DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
        << "********** Function: "
@@ -716,13 +714,15 @@ void LiveIntervals::computeIntervals() {
         if (MO.isRegister() && MO.getReg() && MO.isDef()) {
           handleRegisterDef(MBB, MI, MIIndex, MO, i);
           if (MO.isEarlyClobber()) {
-            AsmsThatEarlyClobber.insert(std::make_pair(MO.getReg(), MI));
+            LiveInterval &interval =  getOrCreateInterval(MO.getReg());
+            interval.isEarlyClobber = true;
           }
         }
         if (MO.isRegister() && !MO.isDef() &&
             MO.getReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg()) &&
             MO.overlapsEarlyClobber()) {
-          AsmsWithEarlyClobberConflict.insert(std::make_pair(MO.getReg(), MI));
+          LiveInterval &interval = getOrCreateInterval(MO.getReg());
+          interval.overlapsEarlyClobber = true;
         }
       }
       
@@ -752,73 +752,6 @@ bool LiveIntervals::findLiveInMBBs(const LiveRange &LR,
   return ResVal;
 }
 
-/// noEarlyclobberConflict - see whether virtual reg VReg has a conflict with
-/// hard reg HReg because of earlyclobbers.  
-///
-/// Earlyclobber operands may not be assigned the same register as
-/// each other, or as earlyclobber-conflict operands (i.e. those that
-/// are non-earlyclobbered inputs to an asm that also has earlyclobbers).
-///
-/// Thus there are two cases to check for:
-/// 1.  VReg is an earlyclobber-conflict register and HReg is an earlyclobber
-/// register in some asm that also has VReg as an input.
-/// 2.  VReg is an earlyclobber register and HReg is an earlyclobber-conflict
-/// input elsewhere in some asm.
-/// In both cases HReg can be assigned by the user, or assigned early in
-/// register allocation.
-/// 
-/// Dropping the distinction between earlyclobber and earlyclobber-conflict,
-/// keeping only one multimap, looks promising, but two earlyclobber-conflict
-/// operands may be assigned the same register if they happen to contain the 
-/// same value, and that implementation would prevent this.
-///
-bool LiveIntervals::noEarlyclobberConflict(unsigned VReg, VirtRegMap &vrm,
-                                           unsigned HReg) {
-  typedef std::multimap<unsigned, MachineInstr*>::iterator It;
-
-  // Short circuit the most common case.
-  if (AsmsWithEarlyClobberConflict.size()!=0) {
-    std::pair<It, It> x = AsmsWithEarlyClobberConflict.equal_range(VReg);
-    for (It I = x.first; I!=x.second; I++) {
-      MachineInstr* MI = I->second;
-      for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
-        MachineOperand &MO = MI->getOperand(i);
-        if (MO.isRegister() && MO.isEarlyClobber()) {
-          unsigned PhysReg = MO.getReg();
-          if (PhysReg && TargetRegisterInfo::isVirtualRegister(PhysReg)) {
-            if (!vrm.hasPhys(PhysReg))
-              continue;
-            PhysReg = vrm.getPhys(PhysReg);
-          }
-          if (PhysReg==HReg)
-            return false;
-        }
-      }
-    }
-  }
-  // Short circuit the most common case.
-  if (AsmsThatEarlyClobber.size()!=0) {
-    std::pair<It, It> x = AsmsThatEarlyClobber.equal_range(VReg);
-    for (It I = x.first; I!=x.second; I++) {
-      MachineInstr* MI = I->second;
-      for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
-        MachineOperand &MO = MI->getOperand(i);
-        if (MO.isRegister() && MO.overlapsEarlyClobber()) {
-          unsigned PhysReg = MO.getReg();
-          if (PhysReg && TargetRegisterInfo::isVirtualRegister(PhysReg)) {
-            if (!vrm.hasPhys(PhysReg))
-              continue;
-            PhysReg = vrm.getPhys(PhysReg);
-          }
-          if (PhysReg==HReg)
-            return false;
-        }
-      }
-    }
-  }
-  return true;
-}
-
 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
   float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ?
                        HUGE_VALF : 0.0F;
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 0279db6ab1..af70db882e 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -173,6 +173,8 @@ namespace {
 
     void ComputeRelatedRegClasses();
 
+    bool noEarlyClobberConflict(LiveInterval *cur, unsigned RegNo);
+
     template <typename ItTy>
     void printIntervals(const char* const str, ItTy i, ItTy e) const {
       if (str) DOUT << str << " intervals:\n";
@@ -1001,6 +1003,73 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
     unhandled_.push(added[i]);
 }
 
+/// noEarlyClobberConflict - see whether LiveInternal cur has a conflict with
+/// hard reg HReg because of earlyclobbers.  
+///
+/// Earlyclobber operands may not be assigned the same register as
+/// each other, or as earlyclobber-conflict operands (i.e. those that
+/// are non-earlyclobbered inputs to an asm that also has earlyclobbers).
+///
+/// Thus there are two cases to check for:
+/// 1.  cur->reg is an earlyclobber-conflict register and HReg is an
+/// earlyclobber register in some asm that also has cur->reg as an input.
+/// 2.  cur->reg is an earlyclobber register and HReg is an 
+/// earlyclobber-conflict input, or a different earlyclobber register,
+/// elsewhere in some asm.
+/// In both cases HReg can be assigned by the user, or assigned early in
+/// register allocation.
+/// 
+/// Dropping the distinction between earlyclobber and earlyclobber-conflict,
+/// keeping only one bit, looks promising, but two earlyclobber-conflict
+/// operands may be assigned the same register if they happen to contain the 
+/// same value, and that implementation would prevent this.
+///
+bool RALinScan::noEarlyClobberConflict(LiveInterval *cur, unsigned HReg) {
+  if (cur->overlapsEarlyClobber) {
+    for (MachineRegisterInfo::use_iterator I = mri_->use_begin(cur->reg),
+          E = mri_->use_end(); I!=E; ++I) {
+      MachineInstr *MI = I.getOperand().getParent();
+      if (MI->getOpcode()==TargetInstrInfo::INLINEASM) {
+        for (int i = MI->getNumOperands()-1; i>=0; --i) {
+          MachineOperand &MO = MI->getOperand(i);
+          if (MO.isRegister() && MO.getReg() && MO.isEarlyClobber() &&
+              HReg==MO.getReg()) {
+            DOUT << "  earlyclobber conflict: " << 
+                  "%reg" << cur->reg << ", " << tri_->getName(HReg) << "\n\t";
+            return false;
+          }
+        }
+      }
+    }
+  }
+  if (cur->isEarlyClobber) {
+    for (MachineRegisterInfo::def_iterator I = mri_->def_begin(cur->reg),
+          E = mri_->def_end(); I!=E; ++I) {
+      MachineInstr *MI = I.getOperand().getParent();
+      if (MI->getOpcode()==TargetInstrInfo::INLINEASM) {
+        // make sure cur->reg is really clobbered in this instruction.
+        bool earlyClobberFound = false, overlapFound = false;
+        for (int i = MI->getNumOperands()-1; i>=0; --i) {
+          MachineOperand &MO = MI->getOperand(i);
+          if (MO.isRegister() && MO.getReg()) {
+            if ((MO.overlapsEarlyClobber() || MO.isEarlyClobber()) && 
+                HReg==MO.getReg())
+              overlapFound = true;
+            if (MO.isEarlyClobber() && cur->reg==MO.getReg())
+              earlyClobberFound = true;
+          }
+        }
+        if (earlyClobberFound && overlapFound) {
+          DOUT << "  earlyclobber conflict: " << 
+                  "%reg" << cur->reg << ", " << tri_->getName(HReg) << "\n\t";
+          return false;
+        }
+      }
+    }
+  }
+  return true;
+}
+
 /// getFreePhysReg - return a free physical register for this virtual register
 /// interval if we have one, otherwise return 0.
 unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
@@ -1049,7 +1118,7 @@ unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
   assert(I != E && "No allocatable register in this register class!");
   for (; I != E; ++I)
     if (prt_->isRegAvail(*I) && 
-        li_->noEarlyclobberConflict(cur->reg, *vrm_, *I)) {
+        noEarlyClobberConflict(cur, *I)) {
       FreeReg = *I;
       if (FreeReg < inactiveCounts.size())
         FreeRegInactiveCount = inactiveCounts[FreeReg];
@@ -1070,7 +1139,7 @@ unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
     unsigned Reg = *I;
     if (prt_->isRegAvail(Reg) && Reg < inactiveCounts.size() &&
         FreeRegInactiveCount < inactiveCounts[Reg] &&
-        li_->noEarlyclobberConflict(cur->reg, *vrm_, Reg)) {
+        noEarlyClobberConflict(cur, *I)) {
       FreeReg = Reg;
       FreeRegInactiveCount = inactiveCounts[Reg];
       if (FreeRegInactiveCount == MaxInactiveCount)