Be more forgiving when calculating alias interference for physreg coalescing.

It is OK for an alias live range to overlap if there is a copy to or from the
physical register. CoalescerPair can work out if the copy is coalescable
independently of the alias.

This means that we can join with the actual destination interval instead of
using the getOrigDstReg() hack. It is no longer necessary to merge clobber
ranges into subregisters.

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

5 files changed, 62 insertions, 116 deletions

diff --git a/include/llvm/CodeGen/RegisterCoalescer.h b/include/llvm/CodeGen/RegisterCoalescer.h
index 7aec10c..7644433 100644
--- a/include/llvm/CodeGen/RegisterCoalescer.h
+++ b/include/llvm/CodeGen/RegisterCoalescer.h
@@ -165,9 +165,6 @@ namespace llvm {
     /// virtual register.
     unsigned subIdx_;
 
-    /// origDstReg_ - dstReg_ without subreg adjustments.
-    unsigned origDstReg_;
-
     /// partial_ - True when the original copy was a partial subregister copy.
     bool partial_;
 
@@ -192,8 +189,7 @@ namespace llvm {
   public:
     CoalescerPair(const TargetInstrInfo &tii, const TargetRegisterInfo &tri)
       : tii_(tii), tri_(tri), dstReg_(0), srcReg_(0), subIdx_(0),
-        origDstReg_(0), partial_(false), crossClass_(false), flipped_(false),
-        newRC_(0) {}
+        partial_(false), crossClass_(false), flipped_(false), newRC_(0) {}
 
     /// setRegisters - set registers to match the copy instruction MI. Return
     /// false if MI is not a coalescable copy instruction.
@@ -232,10 +228,6 @@ namespace llvm {
     /// coalesced into, or 0.
     unsigned getSubIdx() const { return subIdx_; }
 
-    /// getOrigDstReg - Return DstReg as it appeared in the original copy
-    /// instruction before any subreg adjustments.
-    unsigned getOrigDstReg() const { return isPhys() ? origDstReg_ : dstReg_; }
-
     /// getNewRC - Return the register class of the coalesced register.
     const TargetRegisterClass *getNewRC() const { return newRC_; }
   };
diff --git a/lib/CodeGen/RegisterCoalescer.cpp b/lib/CodeGen/RegisterCoalescer.cpp
index 8ff0883..1aeedaa 100644
--- a/lib/CodeGen/RegisterCoalescer.cpp
+++ b/lib/CodeGen/RegisterCoalescer.cpp
@@ -83,7 +83,6 @@ bool CoalescerPair::setRegisters(const MachineInstr *MI) {
     std::swap(SrcSub, DstSub);
     flipped_ = true;
   }
-  origDstReg_ = Dst;
 
   const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo();
 
diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index f41b8a8..0a1885f 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -101,6 +101,11 @@ void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const {
 ///
 bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(const CoalescerPair &CP,
                                                     MachineInstr *CopyMI) {
+  // Bail if there is no dst interval - can happen when merging physical subreg
+  // operations.
+  if (!li_->hasInterval(CP.getDstReg()))
+    return false;
+
   LiveInterval &IntA =
     li_->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
   LiveInterval &IntB =
@@ -110,7 +115,7 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(const CoalescerPair &CP,
   // BValNo is a value number in B that is defined by a copy from A.  'B3' in
   // the example above.
   LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
-  assert(BLR != IntB.end() && "Live range not found!");
+  if (BLR == IntB.end()) return false;
   VNInfo *BValNo = BLR->valno;
 
   // Get the location that B is defined at.  Two options: either this value has
@@ -301,23 +306,31 @@ TransferImplicitOps(MachineInstr *MI, MachineInstr *NewMI) {
 ///
 /// This returns true if an interval was modified.
 ///
-bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
-                                                        LiveInterval &IntB,
+bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(const CoalescerPair &CP,
                                                         MachineInstr *CopyMI) {
-  SlotIndex CopyIdx =
-    li_->getInstructionIndex(CopyMI).getDefIndex();
-
   // FIXME: For now, only eliminate the copy by commuting its def when the
   // source register is a virtual register. We want to guard against cases
   // where the copy is a back edge copy and commuting the def lengthen the
   // live interval of the source register to the entire loop.
-  if (TargetRegisterInfo::isPhysicalRegister(IntA.reg))
+  if (CP.isPhys() && CP.isFlipped())
+    return false;
+
+  // Bail if there is no dst interval.
+  if (!li_->hasInterval(CP.getDstReg()))
     return false;
 
+  SlotIndex CopyIdx =
+    li_->getInstructionIndex(CopyMI).getDefIndex();
+
+  LiveInterval &IntA =
+    li_->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
+  LiveInterval &IntB =
+    li_->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
+
   // BValNo is a value number in B that is defined by a copy from A. 'B3' in
   // the example above.
   LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
-  assert(BLR != IntB.end() && "Live range not found!");
+  if (BLR == IntB.end()) return false;
   VNInfo *BValNo = BLR->valno;
 
   // Get the location that B is defined at.  Two options: either this value has
@@ -505,16 +518,6 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
     if (EI != BExtend.end())
       End = EI->second;
     IntB.addRange(LiveRange(AI->start, End, ValNo));
-
-    // If the IntB live range is assigned to a physical register, and if that
-    // physreg has sub-registers, update their live intervals as well.
-    if (BHasSubRegs) {
-      for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
-        LiveInterval &SRLI = li_->getInterval(*SR);
-        SRLI.MergeInClobberRange(*li_, AI->start, End,
-                                 li_->getVNInfoAllocator());
-      }
-    }
   }
   ValNo->setHasPHIKill(BHasPHIKill);
 
@@ -1134,11 +1137,6 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
     }
   }
 
-  // We may need the source interval after JoinIntervals has destroyed it.
-  OwningPtr<LiveInterval> SavedLI;
-  if (CP.getOrigDstReg() != CP.getDstReg())
-    SavedLI.reset(li_->dupInterval(&li_->getInterval(CP.getSrcReg())));
-
   // Okay, attempt to join these two intervals.  On failure, this returns false.
   // Otherwise, if one of the intervals being joined is a physreg, this method
   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
@@ -1155,12 +1153,8 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
 
     // If we can eliminate the copy without merging the live ranges, do so now.
     if (!CP.isPartial()) {
-      LiveInterval *UseInt = &li_->getInterval(CP.getSrcReg());
-      LiveInterval *DefInt = &li_->getInterval(CP.getDstReg());
-      if (CP.isFlipped())
-        std::swap(UseInt, DefInt);
       if (AdjustCopiesBackFrom(CP, CopyMI) ||
-          RemoveCopyByCommutingDef(*UseInt, *DefInt, CopyMI)) {
+          RemoveCopyByCommutingDef(CP, CopyMI)) {
         JoinedCopies.insert(CopyMI);
         DEBUG(dbgs() << "\tTrivial!\n");
         return true;
@@ -1173,38 +1167,6 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
     return false;
   }
 
-  if (CP.isPhys()) {
-    // If this is a extract_subreg where dst is a physical register, e.g.
-    // cl = EXTRACT_SUBREG reg1024, 1
-    // then create and update the actual physical register allocated to RHS.
-    unsigned LargerDstReg = CP.getDstReg();
-    if (CP.getOrigDstReg() != CP.getDstReg()) {
-      if (tri_->isSubRegister(CP.getOrigDstReg(), LargerDstReg))
-        LargerDstReg = CP.getOrigDstReg();
-      LiveInterval &RealInt = li_->getOrCreateInterval(CP.getDstReg());
-      for (LiveInterval::const_vni_iterator I = SavedLI->vni_begin(),
-             E = SavedLI->vni_end(); I != E; ++I) {
-        const VNInfo *ValNo = *I;
-        VNInfo *NewValNo = RealInt.getNextValue(ValNo->def, ValNo->getCopy(),
-                                                false, // updated at *
-                                                li_->getVNInfoAllocator());
-        NewValNo->setFlags(ValNo->getFlags()); // * updated here.
-        RealInt.MergeValueInAsValue(*SavedLI, ValNo, NewValNo);
-      }
-      RealInt.weight += SavedLI->weight;
-    }
-
-    // Update the liveintervals of sub-registers.
-    LiveInterval &LargerInt = li_->getInterval(LargerDstReg);
-    for (const unsigned *AS = tri_->getSubRegisters(LargerDstReg); *AS; ++AS) {
-      LiveInterval &SRI = li_->getOrCreateInterval(*AS);
-      SRI.MergeInClobberRanges(*li_, LargerInt, li_->getVNInfoAllocator());
-      DEBUG({
-        dbgs() << "\t\tsubreg: "; SRI.print(dbgs(), tri_); dbgs() << "\n";
-      });
-    }
-  }
-
   // Coalescing to a virtual register that is of a sub-register class of the
   // other. Make sure the resulting register is set to the right register class.
   if (CP.isCrossClass()) {
@@ -1311,50 +1273,44 @@ bool SimpleRegisterCoalescing::JoinIntervals(CoalescerPair &CP) {
   LiveInterval &RHS = li_->getInterval(CP.getSrcReg());
   DEBUG({ dbgs() << "\t\tRHS = "; RHS.print(dbgs(), tri_); dbgs() << "\n"; });
 
-  // FIXME: Join into CP.getDstReg instead of CP.getOrigDstReg.
-  // When looking at
-  //   %reg2000 = EXTRACT_SUBREG %EAX, sub_16bit
-  // we really want to join %reg2000 with %AX ( = CP.getDstReg). We are actually
-  // joining into %EAX ( = CP.getOrigDstReg) because it is guaranteed to have an
-  // existing live interval, and we are better equipped to handle interference.
-  // JoinCopy cleans up the mess by taking a copy of RHS before calling here,
-  // and merging that copy into CP.getDstReg after.
-
-  // If a live interval is a physical register, conservatively check if any
-  // of its sub-registers is overlapping the live interval of the virtual
-  // register. If so, do not coalesce.
-  if (CP.isPhys() && *tri_->getSubRegisters(CP.getOrigDstReg())) {
-    // If it's coalescing a virtual register to a physical register, estimate
-    // its live interval length. This is the *cost* of scanning an entire live
-    // interval. If the cost is low, we'll do an exhaustive check instead.
-
-    // If this is something like this:
-    // BB1:
-    // v1024 = op
-    // ...
-    // BB2:
-    // ...
-    // RAX   = v1024
-    //
-    // That is, the live interval of v1024 crosses a bb. Then we can't rely on
-    // less conservative check. It's possible a sub-register is defined before
-    // v1024 (or live in) and live out of BB1.
-    if (RHS.containsOneValue() &&
-        li_->intervalIsInOneMBB(RHS) &&
-        li_->getApproximateInstructionCount(RHS) <= 10) {
-      // Perform a more exhaustive check for some common cases.
-      if (li_->conflictsWithAliasRef(RHS, CP.getOrigDstReg(), JoinedCopies))
-        return false;
-    } else {
-      for (const unsigned* SR = tri_->getAliasSet(CP.getOrigDstReg()); *SR;
-           ++SR)
-        if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
+  // If a live interval is a physical register, check for interference with any
+  // aliases. The interference check implemented here is a bit more conservative
+  // than the full interfeence check below. We allow overlapping live ranges
+  // only when one is a copy of the other.
+  if (CP.isPhys()) {
+    for (const unsigned *AS = tri_->getAliasSet(CP.getDstReg()); *AS; ++AS){
+      if (!li_->hasInterval(*AS))
+        continue;
+      const LiveInterval &LHS = li_->getInterval(*AS);
+      LiveInterval::const_iterator LI = LHS.begin();
+      for (LiveInterval::const_iterator RI = RHS.begin(), RE = RHS.end();
+           RI != RE; ++RI) {
+        LI = std::lower_bound(LI, LHS.end(), RI->start);
+        // Does LHS have an overlapping live range starting before RI?
+        if ((LI != LHS.begin() && LI[-1].end > RI->start) &&
+            (RI->start != RI->valno->def ||
+             !CP.isCoalescable(li_->getInstructionFromIndex(RI->start)))) {
           DEBUG({
-              dbgs() << "\tInterfere with sub-register ";
-              li_->getInterval(*SR).print(dbgs(), tri_);
-            });
+            dbgs() << "\t\tInterference from alias: ";
+            LHS.print(dbgs(), tri_);
+            dbgs() << "\n\t\tOverlap at " << RI->start << " and no copy.\n";
+          });
           return false;
         }
+
+        // Check that LHS ranges beginning in this range are copies.
+        for (; LI != LHS.end() && LI->start < RI->end; ++LI) {
+          if (LI->start != LI->valno->def ||
+              !CP.isCoalescable(li_->getInstructionFromIndex(LI->start))) {
+            DEBUG({
+              dbgs() << "\t\tInterference from alias: ";
+              LHS.print(dbgs(), tri_);
+              dbgs() << "\n\t\tDef at " << LI->start << " is not a copy.\n";
+            });
+            return false;
+          }
+        }
+      }
     }
   }
 
@@ -1366,7 +1322,7 @@ bool SimpleRegisterCoalescing::JoinIntervals(CoalescerPair &CP) {
   DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS;
   SmallVector<VNInfo*, 16> NewVNInfo;
 
-  LiveInterval &LHS = li_->getInterval(CP.getOrigDstReg());
+  LiveInterval &LHS = li_->getOrCreateInterval(CP.getDstReg());
   DEBUG({ dbgs() << "\t\tLHS = "; LHS.print(dbgs(), tri_); dbgs() << "\n"; });
 
   // Loop over the value numbers of the LHS, seeing if any are defined from
diff --git a/lib/CodeGen/SimpleRegisterCoalescing.h b/lib/CodeGen/SimpleRegisterCoalescing.h
index b65cbf1..e154da6 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.h
+++ b/lib/CodeGen/SimpleRegisterCoalescing.h
@@ -130,8 +130,7 @@ namespace llvm {
     /// If the source value number is defined by a commutable instruction and
     /// its other operand is coalesced to the copy dest register, see if we
     /// can transform the copy into a noop by commuting the definition.
-    bool RemoveCopyByCommutingDef(LiveInterval &IntA, LiveInterval &IntB,
-                                  MachineInstr *CopyMI);
+    bool RemoveCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI);
 
     /// TrimLiveIntervalToLastUse - If there is a last use in the same basic
     /// block as the copy instruction, trim the ive interval to the last use
diff --git a/test/CodeGen/X86/pic.ll b/test/CodeGen/X86/pic.ll
index d7b0805..a1a9759 100644
--- a/test/CodeGen/X86/pic.ll
+++ b/test/CodeGen/X86/pic.ll
@@ -78,8 +78,8 @@ entry:
 ; LINUX: 	call	.L3$pb
 ; LINUX-NEXT: .L3$pb:
 ; LINUX: 	popl
-; LINUX: 	addl	$_GLOBAL_OFFSET_TABLE_+(.L{{.*}}-.L3$pb),
-; LINUX: 	movl	pfoo@GOT(%esi),
+; LINUX: 	addl	$_GLOBAL_OFFSET_TABLE_+(.L{{.*}}-.L3$pb), %[[REG3:e..]]
+; LINUX: 	movl	pfoo@GOT(%[[REG3]]),
 ; LINUX: 	call	afoo@PLT
 ; LINUX: 	call	*
 }