X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSimpleRegisterCoalescing.cpp;h=a60939c301057c2d0f0498c316c866cb949eec6c;hb=a29c13086a3add78a3a79f744573fe09eaa9dc88;hp=08c0ab3c54b3ac16cb271ee1f1157d0ff0b81269;hpb=9242cb8b8288664da4147fd6dda43514926a9041;p=oota-llvm.git

diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 08c0ab3c54b..a60939c3010 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -25,6 +25,7 @@
 #include "llvm/CodeGen/RegisterCoalescer.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetOptions.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/ADT/SmallSet.h"
@@ -67,13 +68,16 @@ static RegisterAnalysisGroup<RegisterCoalescer, true/*The Default*/> V(X);
 const PassInfo *const llvm::SimpleRegisterCoalescingID = &X;
 
 void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<LiveIntervals>();
   AU.addPreserved<LiveIntervals>();
+  AU.addRequired<MachineLoopInfo>();
   AU.addPreserved<MachineLoopInfo>();
   AU.addPreservedID(MachineDominatorsID);
-  AU.addPreservedID(PHIEliminationID);
+  if (StrongPHIElim)
+    AU.addPreservedID(StrongPHIEliminationID);
+  else
+    AU.addPreservedID(PHIEliminationID);
   AU.addPreservedID(TwoAddressInstructionPassID);
-  AU.addRequired<LiveIntervals>();
-  AU.addRequired<MachineLoopInfo>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
@@ -182,16 +186,20 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA,
   }
 
   // Okay, merge "B1" into the same value number as "B0".
-  if (BValNo != ValLR->valno)
+  if (BValNo != ValLR->valno) {
+    IntB.addKills(ValLR->valno, BValNo->kills);
     IntB.MergeValueNumberInto(BValNo, ValLR->valno);
+  }
   DOUT << "   result = "; IntB.print(DOUT, tri_);
   DOUT << "\n";
 
   // If the source instruction was killing the source register before the
   // merge, unset the isKill marker given the live range has been extended.
   int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true);
-  if (UIdx != -1)
+  if (UIdx != -1) {
     ValLREndInst->getOperand(UIdx).setIsKill(false);
+    IntB.removeKill(ValLR->valno, FillerStart);
+  }
 
   ++numExtends;
   return true;
@@ -452,14 +460,41 @@ bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt,
   unsigned DefIdx = li_->getDefIndex(CopyIdx);
   const LiveRange *DLR= li_->getInterval(DstReg).getLiveRangeContaining(DefIdx);
   DLR->valno->copy = NULL;
+  // Don't forget to update sub-register intervals.
+  if (TargetRegisterInfo::isPhysicalRegister(DstReg)) {
+    for (const unsigned* SR = tri_->getSubRegisters(DstReg); *SR; ++SR) {
+      if (!li_->hasInterval(*SR))
+        continue;
+      DLR = li_->getInterval(*SR).getLiveRangeContaining(DefIdx);
+      if (DLR && DLR->valno->copy == CopyMI)
+        DLR->valno->copy = NULL;
+    }
+  }
 
-  MachineBasicBlock::iterator MII = CopyMI;
   MachineBasicBlock *MBB = CopyMI->getParent();
+  MachineBasicBlock::iterator MII = next(MachineBasicBlock::iterator(CopyMI));
+  CopyMI->removeFromParent();
   tii_->reMaterialize(*MBB, MII, DstReg, DefMI);
   MachineInstr *NewMI = prior(MII);
+  // CopyMI may have implicit operands, transfer them over to the newly
+  // rematerialized instruction. And update implicit def interval valnos.
+  for (unsigned i = CopyMI->getDesc().getNumOperands(),
+         e = CopyMI->getNumOperands(); i != e; ++i) {
+    MachineOperand &MO = CopyMI->getOperand(i);
+    if (MO.isReg() && MO.isImplicit())
+      NewMI->addOperand(MO);
+    if (MO.isDef() && li_->hasInterval(MO.getReg())) {
+      unsigned Reg = MO.getReg();
+      DLR = li_->getInterval(Reg).getLiveRangeContaining(DefIdx);
+      if (DLR && DLR->valno->copy == CopyMI)
+        DLR->valno->copy = NULL;
+    }
+  }
+
   li_->ReplaceMachineInstrInMaps(CopyMI, NewMI);
-  CopyMI->eraseFromParent();
+  MBB->getParent()->DeleteMachineInstr(CopyMI);
   ReMatCopies.insert(CopyMI);
+  ReMatDefs.insert(DefMI);
   ++NumReMats;
   return true;
 }
@@ -526,20 +561,37 @@ SimpleRegisterCoalescing::UpdateRegDefsUses(unsigned SrcReg, unsigned DstReg,
 
       O.setReg(UseDstReg);
       O.setSubReg(0);
-    } else {
-      // Sub-register indexes goes from small to large. e.g.
-      // RAX: 1 -> AL, 2 -> AX, 3 -> EAX
-      // EAX: 1 -> AL, 2 -> AX
-      // So RAX's sub-register 2 is AX, RAX's sub-regsiter 3 is EAX, whose
-      // sub-register 2 is also AX.
-      if (SubIdx && OldSubIdx && SubIdx != OldSubIdx)
-        assert(OldSubIdx < SubIdx && "Conflicting sub-register index!");
-      else if (SubIdx)
-        O.setSubReg(SubIdx);
-      // Remove would-be duplicated kill marker.
-      if (O.isKill() && UseMI->killsRegister(DstReg))
-        O.setIsKill(false);
-      O.setReg(DstReg);
+      continue;
+    }
+
+    // Sub-register indexes goes from small to large. e.g.
+    // RAX: 1 -> AL, 2 -> AX, 3 -> EAX
+    // EAX: 1 -> AL, 2 -> AX
+    // So RAX's sub-register 2 is AX, RAX's sub-regsiter 3 is EAX, whose
+    // sub-register 2 is also AX.
+    if (SubIdx && OldSubIdx && SubIdx != OldSubIdx)
+      assert(OldSubIdx < SubIdx && "Conflicting sub-register index!");
+    else if (SubIdx)
+      O.setSubReg(SubIdx);
+    // Remove would-be duplicated kill marker.
+    if (O.isKill() && UseMI->killsRegister(DstReg))
+      O.setIsKill(false);
+    O.setReg(DstReg);
+
+    // After updating the operand, check if the machine instruction has
+    // become a copy. If so, update its val# information.
+    const TargetInstrDesc &TID = UseMI->getDesc();
+    unsigned CopySrcReg, CopyDstReg;
+    if (TID.getNumDefs() == 1 && TID.getNumOperands() > 2 &&
+        tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg) &&
+        CopySrcReg != CopyDstReg &&
+        (TargetRegisterInfo::isVirtualRegister(CopyDstReg) ||
+         allocatableRegs_[CopyDstReg])) {
+      LiveInterval &LI = li_->getInterval(CopyDstReg);
+      unsigned DefIdx = li_->getDefIndex(li_->getInstructionIndex(UseMI));
+      const LiveRange *DLR = LI.getLiveRangeContaining(DefIdx);
+      if (DLR->valno->def == DefIdx)
+        DLR->valno->copy = UseMI;
     }
   }
 }
@@ -655,6 +707,18 @@ bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li,
   return false;
 }
 
+/// RemoveDeadDef - If a def of a live interval is now determined dead, remove
+/// the val# it defines. If the live interval becomes empty, remove it as well.
+bool SimpleRegisterCoalescing::RemoveDeadDef(LiveInterval &li,
+                                             MachineInstr *DefMI) {
+  unsigned DefIdx = li_->getDefIndex(li_->getInstructionIndex(DefMI));
+  LiveInterval::iterator MLR = li.FindLiveRangeContaining(DefIdx);
+  if (DefIdx != MLR->valno->def)
+    return false;
+  li.removeValNo(MLR->valno);
+  return removeIntervalIfEmpty(li, li_, tri_);
+}
+
 /// PropagateDeadness - Propagate the dead marker to the instruction which
 /// defines the val#.
 static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI,
@@ -860,6 +924,8 @@ void SimpleRegisterCoalescing::RemoveCopiesFromValNo(LiveInterval &li,
   }
 }
 
+/// getMatchingSuperReg - Return a super-register of the specified register
+/// Reg so its sub-register of index SubIdx is Reg.
 static unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx, 
                                     const TargetRegisterClass *RC,
                                     const TargetRegisterInfo* TRI) {
@@ -904,6 +970,61 @@ SimpleRegisterCoalescing::isProfitableToCoalesceToSubRC(unsigned SrcReg,
   return (SrcSize + DstSize) <= Threshold;
 }
 
+/// HasIncompatibleSubRegDefUse - If we are trying to coalesce a virtual
+/// register with a physical register, check if any of the virtual register
+/// operand is a sub-register use or def. If so, make sure it won't result
+/// in an illegal extract_subreg or insert_subreg instruction. e.g.
+/// vr1024 = extract_subreg vr1025, 1
+/// ...
+/// vr1024 = mov8rr AH
+/// If vr1024 is coalesced with AH, the extract_subreg is now illegal since
+/// AH does not have a super-reg whose sub-register 1 is AH.
+bool
+SimpleRegisterCoalescing::HasIncompatibleSubRegDefUse(MachineInstr *CopyMI,
+                                                      unsigned VirtReg,
+                                                      unsigned PhysReg) {
+  for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(VirtReg),
+         E = mri_->reg_end(); I != E; ++I) {
+    MachineOperand &O = I.getOperand();
+    MachineInstr *MI = &*I;
+    if (MI == CopyMI || JoinedCopies.count(MI))
+      continue;
+    unsigned SubIdx = O.getSubReg();
+    if (SubIdx && !tri_->getSubReg(PhysReg, SubIdx))
+      return true;
+    if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
+      SubIdx = MI->getOperand(2).getImm();
+      if (O.isUse() && !tri_->getSubReg(PhysReg, SubIdx))
+        return true;
+      if (O.isDef()) {
+        unsigned SrcReg = MI->getOperand(1).getReg();
+        const TargetRegisterClass *RC =
+          TargetRegisterInfo::isPhysicalRegister(SrcReg)
+          ? tri_->getPhysicalRegisterRegClass(SrcReg)
+          : mri_->getRegClass(SrcReg);
+        if (!getMatchingSuperReg(PhysReg, SubIdx, RC, tri_))
+          return true;
+      }
+    }
+    if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) {
+      SubIdx = MI->getOperand(3).getImm();
+      if (VirtReg == MI->getOperand(0).getReg()) {
+        if (!tri_->getSubReg(PhysReg, SubIdx))
+          return true;
+      } else {
+        unsigned DstReg = MI->getOperand(0).getReg();
+        const TargetRegisterClass *RC =
+          TargetRegisterInfo::isPhysicalRegister(DstReg)
+          ? tri_->getPhysicalRegisterRegClass(DstReg)
+          : mri_->getRegClass(DstReg);
+        if (!getMatchingSuperReg(PhysReg, SubIdx, RC, tri_))
+          return true;
+      }
+    }
+  }
+  return false;
+}
+
 
 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
 /// which are the src/dst of the copy instruction CopyMI.  This returns true
@@ -1014,10 +1135,10 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
         mri_->getRegClass(isExtSubReg ? SrcReg : DstReg);
       if (isExtSubReg) {
         RealDstReg = getMatchingSuperReg(DstReg, SubIdx, RC, tri_);
-        assert(RealDstReg && "Invalid extra_subreg instruction!");
+        assert(RealDstReg && "Invalid extract_subreg instruction!");
       } else {
         RealSrcReg = getMatchingSuperReg(SrcReg, SubIdx, RC, tri_);
-        assert(RealSrcReg && "Invalid extra_subreg instruction!");
+        assert(RealSrcReg && "Invalid extract_subreg instruction!");
       }
 
       // For this type of EXTRACT_SUBREG, conservatively
@@ -1096,6 +1217,12 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
       return false;
     }
   }
+
+  // Will it create illegal extract_subreg / insert_subreg?
+  if (SrcIsPhys && HasIncompatibleSubRegDefUse(CopyMI, DstReg, SrcReg))
+    return false;
+  if (DstIsPhys && HasIncompatibleSubRegDefUse(CopyMI, SrcReg, DstReg))
+    return false;
   
   LiveInterval &SrcInt = li_->getInterval(SrcReg);
   LiveInterval &DstInt = li_->getInterval(DstReg);
@@ -1302,6 +1429,15 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
     }
   }
 
+  // If resulting interval has a preference that no longer fits because of subreg
+  // coalescing, just clear the preference.
+  if (ResDstInt->preference && (isExtSubReg || isInsSubReg) &&
+      TargetRegisterInfo::isVirtualRegister(ResDstInt->reg)) {
+    const TargetRegisterClass *RC = mri_->getRegClass(ResDstInt->reg);
+    if (!RC->contains(ResDstInt->preference))
+      ResDstInt->preference = 0;
+  }
+
   DOUT << "\n\t\tJoined.  Result = "; ResDstInt->print(DOUT, tri_);
   DOUT << "\n";
 
@@ -2051,7 +2187,7 @@ SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End,
     if (!(tii_->isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg))
       for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) {
         MachineOperand &Use = MI->getOperand(i);
-        if (Use.isRegister() && Use.isUse() && Use.getReg() &&
+        if (Use.isReg() && Use.isUse() && Use.getReg() &&
             tri_->regsOverlap(Use.getReg(), Reg)) {
           UseIdx = e;
           return &Use;
@@ -2075,6 +2211,7 @@ void SimpleRegisterCoalescing::printRegName(unsigned reg) const {
 void SimpleRegisterCoalescing::releaseMemory() {
   JoinedCopies.clear();
   ReMatCopies.clear();
+  ReMatDefs.clear();
 }
 
 static bool isZeroLengthInterval(LiveInterval *li) {
@@ -2155,6 +2292,7 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
 
   // Perform a final pass over the instructions and compute spill weights
   // and remove identity moves.
+  SmallVector<unsigned, 4> DeadDefs;
   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
        mbbi != mbbe; ++mbbi) {
     MachineBasicBlock* mbb = mbbi;
@@ -2183,26 +2321,57 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
         continue;
       }
 
+      // Now check if this is a remat'ed def instruction which is now dead.
+      if (ReMatDefs.count(MI)) {
+        bool isDead = true;
+        for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+          const MachineOperand &MO = MI->getOperand(i);
+          if (!MO.isReg())
+            continue;
+          unsigned Reg = MO.getReg();
+          if (TargetRegisterInfo::isVirtualRegister(Reg))
+            DeadDefs.push_back(Reg);
+          if (MO.isDead())
+            continue;
+          if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
+              !mri_->use_empty(Reg)) {
+            isDead = false;
+            break;
+          }
+        }
+        if (isDead) {
+          while (!DeadDefs.empty()) {
+            unsigned DeadDef = DeadDefs.back();
+            DeadDefs.pop_back();
+            RemoveDeadDef(li_->getInterval(DeadDef), MI);
+          }
+          li_->RemoveMachineInstrFromMaps(mii);
+          mii = mbbi->erase(mii);
+          continue;
+        } else
+          DeadDefs.clear();
+      }
+
       // If the move will be an identity move delete it
-      bool isMove = tii_->isMoveInstr(*mii, SrcReg, DstReg);
+      bool isMove = tii_->isMoveInstr(*MI, SrcReg, DstReg);
       if (isMove && SrcReg == DstReg) {
         if (li_->hasInterval(SrcReg)) {
           LiveInterval &RegInt = li_->getInterval(SrcReg);
           // If def of this move instruction is dead, remove its live range
           // from the dstination register's live interval.
-          if (mii->registerDefIsDead(DstReg)) {
-            if (!ShortenDeadCopySrcLiveRange(RegInt, mii))
-              ShortenDeadCopyLiveRange(RegInt, mii);
+          if (MI->registerDefIsDead(DstReg)) {
+            if (!ShortenDeadCopySrcLiveRange(RegInt, MI))
+              ShortenDeadCopyLiveRange(RegInt, MI);
           }
         }
-        li_->RemoveMachineInstrFromMaps(mii);
+        li_->RemoveMachineInstrFromMaps(MI);
         mii = mbbi->erase(mii);
         ++numPeep;
       } else if (!isMove || !TurnCopyIntoImpDef(mii, mbb, DstReg, SrcReg)) {
         SmallSet<unsigned, 4> UniqueUses;
-        for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
-          const MachineOperand &mop = mii->getOperand(i);
-          if (mop.isRegister() && mop.getReg() &&
+        for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+          const MachineOperand &mop = MI->getOperand(i);
+          if (mop.isReg() && mop.getReg() &&
               TargetRegisterInfo::isVirtualRegister(mop.getReg())) {
             unsigned reg = mop.getReg();
             // Multiple uses of reg by the same instruction. It should not
@@ -2230,7 +2399,8 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
         LI.weight = HUGE_VALF;
       else {
         bool isLoad = false;
-        if (li_->isReMaterializable(LI, isLoad)) {
+        SmallVector<LiveInterval*, 4> SpillIs;
+        if (li_->isReMaterializable(LI, SpillIs, isLoad)) {
           // If all of the definitions of the interval are re-materializable,
           // it is a preferred candidate for spilling. If non of the defs are
           // loads, then it's potentially very cheap to re-materialize.