Add a bit IsUndef to MachineOperand. This indicates the def / use register operand is defined by an implicit_def. That means it can def / use any register and passes (e.g. register scavenger) can feel free to ignore them.

The register allocator, when it allocates a register to a virtual register defined by an implicit_def, can allocate any physical register without worrying about overlapping live ranges. It should mark all of operands of the said virtual register so later passes will do the right thing.

This is not the best solution. But it should be a lot less fragile to having the scavenger try to track what is defined by implicit_def.


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

6 files changed, 58 insertions, 59 deletions

diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 21bb5dc..b017f91 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -1782,8 +1782,12 @@ LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
       NewLIs.push_back(&getOrCreateInterval(NewVReg));
       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
         MachineOperand &MO = MI->getOperand(i);
-        if (MO.isReg() && MO.getReg() == li.reg)
+        if (MO.isReg() && MO.getReg() == li.reg) {
           MO.setReg(NewVReg);
+          MO.setIsUndef();
+          if (MO.isKill())
+            MO.setIsKill(false);
+        }
       }
     }
   }
diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp
index c977508..d44305f 100644
--- a/lib/CodeGen/MachineInstr.cpp
+++ b/lib/CodeGen/MachineInstr.cpp
@@ -120,7 +120,7 @@ void MachineOperand::ChangeToImmediate(int64_t ImmVal) {
 /// the specified value.  If an operand is known to be an register already,
 /// the setReg method should be used.
 void MachineOperand::ChangeToRegister(unsigned Reg, bool isDef, bool isImp,
-                                      bool isKill, bool isDead) {
+                                      bool isKill, bool isDead, bool isUndef) {
   // If this operand is already a register operand, use setReg to update the 
   // register's use/def lists.
   if (isReg()) {
@@ -143,6 +143,7 @@ void MachineOperand::ChangeToRegister(unsigned Reg, bool isDef, bool isImp,
   IsImp = isImp;
   IsKill = isKill;
   IsDead = isDead;
+  IsUndef = isUndef;
   IsEarlyClobber = false;
   SubReg = 0;
 }
@@ -206,11 +207,11 @@ void MachineOperand::print(raw_ostream &OS, const TargetMachine *TM) const {
         OS << "%mreg" << getReg();
     }
 
-    if (getSubReg() != 0) {
+    if (getSubReg() != 0)
       OS << ':' << getSubReg();
-    }
 
-    if (isDef() || isKill() || isDead() || isImplicit() || isEarlyClobber()) {
+    if (isDef() || isKill() || isDead() || isImplicit() || isUndef() ||
+        isEarlyClobber()) {
       OS << '<';
       bool NeedComma = false;
       if (isImplicit()) {
@@ -224,10 +225,15 @@ void MachineOperand::print(raw_ostream &OS, const TargetMachine *TM) const {
         OS << "def";
         NeedComma = true;
       }
-      if (isKill() || isDead()) {
+      if (isKill() || isDead() || isUndef()) {
         if (NeedComma) OS << ',';
         if (isKill())  OS << "kill";
         if (isDead())  OS << "dead";
+        if (isUndef()) {
+          if (isKill() || isDead())
+            OS << ',';
+          OS << "undef";
+        }
       }
       OS << '>';
     }
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 41a42fd..2caa2f9 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -905,6 +905,17 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
     DOUT <<  tri_->getName(physReg) << '\n';
     // Note the register is not really in use.
     vrm_->assignVirt2Phys(cur->reg, physReg);
+    // Since the register allocator is allowed to assign this virtual register
+    // physical register that overlaps other live intervals. Mark these
+    // operands as "Undef" which means later passes, e.g. register scavenger
+    // can ignore them.
+    for (MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(cur->reg),
+           RE = mri_->reg_end(); RI != RE; ++RI) {
+      MachineOperand &MO = RI.getOperand();
+      MO.setIsUndef();
+      if (MO.isKill())
+        MO.setIsKill(false);
+    }
     return;
   }
 
diff --git a/lib/CodeGen/RegisterScavenging.cpp b/lib/CodeGen/RegisterScavenging.cpp
index 3feb92f..7d8e3af 100644
--- a/lib/CodeGen/RegisterScavenging.cpp
+++ b/lib/CodeGen/RegisterScavenging.cpp
@@ -36,7 +36,7 @@ static bool RedefinesSuperRegPart(const MachineInstr *MI, unsigned SubReg,
   bool SeenSuperDef = false;
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isReg())
+    if (!MO.isReg() || MO.isUndef())
       continue;
     if (TRI->isSuperRegister(SubReg, MO.getReg())) {
       if (MO.isUse())
@@ -57,28 +57,22 @@ static bool RedefinesSuperRegPart(const MachineInstr *MI,
 }
 
 /// setUsed - Set the register and its sub-registers as being used.
-void RegScavenger::setUsed(unsigned Reg, bool ImpDef) {
+void RegScavenger::setUsed(unsigned Reg) {
   RegsAvailable.reset(Reg);
-  ImplicitDefed[Reg] = ImpDef;
 
   for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
-       unsigned SubReg = *SubRegs; ++SubRegs) {
+       unsigned SubReg = *SubRegs; ++SubRegs)
     RegsAvailable.reset(SubReg);
-    ImplicitDefed[SubReg] = ImpDef;
-  }
 }
 
 /// setUnused - Set the register and its sub-registers as being unused.
 void RegScavenger::setUnused(unsigned Reg, const MachineInstr *MI) {
   RegsAvailable.set(Reg);
-  ImplicitDefed.reset(Reg);
 
   for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
        unsigned SubReg = *SubRegs; ++SubRegs)
-    if (!RedefinesSuperRegPart(MI, Reg, TRI)) {
+    if (!RedefinesSuperRegPart(MI, Reg, TRI))
       RegsAvailable.set(SubReg);
-      ImplicitDefed.reset(SubReg);
-    }
 }
 
 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
@@ -94,7 +88,6 @@ void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
   if (!MBB) {
     NumPhysRegs = TRI->getNumRegs();
     RegsAvailable.resize(NumPhysRegs);
-    ImplicitDefed.resize(NumPhysRegs);
 
     // Create reserved registers bitvector.
     ReservedRegs = TRI->getReservedRegs(MF);
@@ -113,7 +106,6 @@ void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
   ScavengeRestore = NULL;
   CurrDist = 0;
   DistanceMap.clear();
-  ImplicitDefed.reset();
 
   // All registers started out unused.
   RegsAvailable.set();
@@ -195,15 +187,13 @@ void RegScavenger::forward() {
     ScavengeRestore = NULL;
   }
 
-  bool IsImpDef = MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF;
-
   // Separate register operands into 3 classes: uses, defs, earlyclobbers.
   SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs;
   SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs;
   SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs;
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isReg() || MO.getReg() == 0)
+    if (!MO.isReg() || MO.getReg() == 0 || MO.isUndef())
       continue;
     if (MO.isUse())
       UseMOs.push_back(std::make_pair(&MO,i));
@@ -221,14 +211,7 @@ void RegScavenger::forward() {
 
     assert(isUsed(Reg) && "Using an undefined register!");
 
-    // Kill of implicit_def defined registers are ignored. e.g.
-    // entry: 0x2029ab8, LLVM BB @0x1b06080, ID#0:
-    // Live Ins: %R0
-    //  %R0<def> = IMPLICIT_DEF
-    //  %R0<def> = IMPLICIT_DEF
-    //  STR %R0<kill>, %R0, %reg0, 0, 14, %reg0, Mem:ST(4,4) [0x1b06510 + 0]
-    //  %R1<def> = LDR %R0, %reg0, 24, 14, %reg0, Mem:LD(4,4) [0x1b065bc + 0]
-    if (MO.isKill() && !isReserved(Reg) && !isImplicitlyDefined(Reg)) {
+    if (MO.isKill() && !isReserved(Reg)) {
       KillRegs.set(Reg);
 
       // Mark sub-registers as used.
@@ -274,10 +257,9 @@ void RegScavenger::forward() {
     // Implicit def is allowed to "re-define" any register. Similarly,
     // implicitly defined registers can be clobbered.
     assert((isReserved(Reg) || isUnused(Reg) ||
-            IsImpDef || isImplicitlyDefined(Reg) ||
             isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
            "Re-defining a live register!");
-    setUsed(Reg, IsImpDef);
+    setUsed(Reg);
   }
 }
 
@@ -297,7 +279,7 @@ void RegScavenger::backward() {
   SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs;
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isReg() || MO.getReg() == 0)
+    if (!MO.isReg() || MO.getReg() == 0 || MO.isUndef())
       continue;
     if (MO.isUse())
       UseMOs.push_back(std::make_pair(&MO,i));
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp
index e372b5b..7926339 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp
@@ -617,7 +617,7 @@ void ScheduleDAGSDNodes::EmitNode(SDNode *Node, bool IsClone, bool IsCloned,
         for (; NumVals; --NumVals, ++i) {
           unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
           MI->addOperand(MachineOperand::CreateReg(Reg, true, false, false, 
-                                                   false, 0, true));
+                                                   false, false, true));
         }
         break;
       case 1:  // Use of register.
diff --git a/lib/CodeGen/VirtRegRewriter.cpp b/lib/CodeGen/VirtRegRewriter.cpp
index bd6584a..bbf1e24 100644
--- a/lib/CodeGen/VirtRegRewriter.cpp
+++ b/lib/CodeGen/VirtRegRewriter.cpp
@@ -356,7 +356,7 @@ static void InvalidateKills(MachineInstr &MI,
                             SmallVector<unsigned, 2> *KillRegs = NULL) {
   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     MachineOperand &MO = MI.getOperand(i);
-    if (!MO.isReg() || !MO.isUse() || !MO.isKill())
+    if (!MO.isReg() || !MO.isUse() || !MO.isKill() || MO.isUndef())
       continue;
     unsigned Reg = MO.getReg();
     if (TargetRegisterInfo::isVirtualRegister(Reg))
@@ -390,12 +390,12 @@ static bool InvalidateRegDef(MachineBasicBlock::iterator I,
   MachineOperand *DefOp = NULL;
   for (unsigned i = 0, e = DefMI->getNumOperands(); i != e; ++i) {
     MachineOperand &MO = DefMI->getOperand(i);
-    if (MO.isReg() && MO.isDef()) {
-      if (MO.getReg() == Reg)
-        DefOp = &MO;
-      else if (!MO.isDead())
-        HasLiveDef = true;
-    }
+    if (!MO.isReg() || !MO.isUse() || !MO.isKill() || MO.isUndef())
+      continue;
+    if (MO.getReg() == Reg)
+      DefOp = &MO;
+    else if (!MO.isDead())
+      HasLiveDef = true;
   }
   if (!DefOp)
     return false;
@@ -430,7 +430,7 @@ static void UpdateKills(MachineInstr &MI, const TargetRegisterInfo* TRI,
                         std::vector<MachineOperand*> &KillOps) {
   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     MachineOperand &MO = MI.getOperand(i);
-    if (!MO.isReg() || !MO.isUse())
+    if (!MO.isReg() || !MO.isUse() || MO.isUndef())
       continue;
     unsigned Reg = MO.getReg();
     if (Reg == 0)
@@ -1289,8 +1289,7 @@ private:
           if (InvalidateRegDef(PrevMII, *MII, KillRegs[j], HasOtherDef)) {
             MachineInstr *DeadDef = PrevMII;
             if (ReMatDefs.count(DeadDef) && !HasOtherDef) {
-              // FIXME: This assumes a remat def does not have side
-              // effects.
+              // FIXME: This assumes a remat def does not have side effects.
               VRM.RemoveMachineInstrFromMaps(DeadDef);
               MBB.erase(DeadDef);
               ++NumDRM;
@@ -1569,6 +1568,8 @@ private:
         if (MO.isImplicit())
           // If the virtual register is implicitly defined, emit a implicit_def
           // before so scavenger knows it's "defined".
+          // FIXME: This is a horrible hack done the by register allocator to
+          // remat a definition with virtual register operand.
           VirtUseOps.insert(VirtUseOps.begin(), i);
         else
           VirtUseOps.push_back(i);
@@ -1595,6 +1596,7 @@ private:
           MI.getOperand(i).setReg(RReg);
           MI.getOperand(i).setSubReg(0);
           if (VRM.isImplicitlyDefined(VirtReg))
+            // FIXME: Is this needed?
             BuildMI(MBB, &MI, MI.getDebugLoc(),
                     TII->get(TargetInstrInfo::IMPLICIT_DEF), RReg);
           continue;
@@ -1604,22 +1606,16 @@ private:
         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 AvoidReload = MO.isUndef();
+        // Check if it is 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.
         bool DoReMat = VRM.isReMaterialized(VirtReg);
         int SSorRMId = DoReMat
           ? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg);