1 files changed, 197 insertions, 59 deletions

diff --git a/contrib/llvm-project/llvm/lib/CodeGen/TwoAddressInstructionPass.cpp b/contrib/llvm-project/llvm/lib/CodeGen/TwoAddressInstructionPass.cpp
index 1664b4dadfec..46cec5407565 100644
--- a/contrib/llvm-project/llvm/lib/CodeGen/TwoAddressInstructionPass.cpp
+++ b/contrib/llvm-project/llvm/lib/CodeGen/TwoAddressInstructionPass.cpp
@@ -118,6 +118,8 @@ class TwoAddressInstructionPass : public MachineFunctionPass {
   // registers. e.g. r1 = move v1024.
   DenseMap<Register, Register> DstRegMap;
 
+  void removeClobberedSrcRegMap(MachineInstr *MI);
+
   bool isRevCopyChain(Register FromReg, Register ToReg, int Maxlen);
 
   bool noUseAfterLastDef(Register Reg, unsigned Dist, unsigned &LastDef);
@@ -132,7 +134,7 @@ class TwoAddressInstructionPass : public MachineFunctionPass {
 
   bool convertInstTo3Addr(MachineBasicBlock::iterator &mi,
                           MachineBasicBlock::iterator &nmi, Register RegA,
-                          Register RegB, unsigned Dist);
+                          Register RegB, unsigned &Dist);
 
   bool isDefTooClose(Register Reg, unsigned Dist, MachineInstr *MI);
 
@@ -144,7 +146,7 @@ class TwoAddressInstructionPass : public MachineFunctionPass {
   bool tryInstructionTransform(MachineBasicBlock::iterator &mi,
                                MachineBasicBlock::iterator &nmi,
                                unsigned SrcIdx, unsigned DstIdx,
-                               unsigned Dist, bool shouldOnlyCommute);
+                               unsigned &Dist, bool shouldOnlyCommute);
 
   bool tryInstructionCommute(MachineInstr *MI,
                              unsigned DstOpIdx,
@@ -380,7 +382,8 @@ findOnlyInterestingUse(Register Reg, MachineBasicBlock *MBB,
   if (!MRI->hasOneNonDBGUse(Reg))
     // None or more than one use.
     return nullptr;
-  MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(Reg);
+  MachineOperand &UseOp = *MRI->use_nodbg_begin(Reg);
+  MachineInstr &UseMI = *UseOp.getParent();
   if (UseMI.getParent() != MBB)
     return nullptr;
   Register SrcReg;
@@ -394,6 +397,18 @@ findOnlyInterestingUse(Register Reg, MachineBasicBlock *MBB,
     IsDstPhys = DstReg.isPhysical();
     return &UseMI;
   }
+  if (UseMI.isCommutable()) {
+    unsigned Src1 = TargetInstrInfo::CommuteAnyOperandIndex;
+    unsigned Src2 = UseMI.getOperandNo(&UseOp);
+    if (TII->findCommutedOpIndices(UseMI, Src1, Src2)) {
+      MachineOperand &MO = UseMI.getOperand(Src1);
+      if (MO.isReg() && MO.isUse() &&
+          isTwoAddrUse(UseMI, MO.getReg(), DstReg)) {
+        IsDstPhys = DstReg.isPhysical();
+        return &UseMI;
+      }
+    }
+  }
   return nullptr;
 }
 
@@ -422,6 +437,76 @@ static bool regsAreCompatible(Register RegA, Register RegB,
   return TRI->regsOverlap(RegA, RegB);
 }
 
+/// From RegMap remove entries mapped to a physical register which overlaps MO.
+static void removeMapRegEntry(const MachineOperand &MO,
+                              DenseMap<Register, Register> &RegMap,
+                              const TargetRegisterInfo *TRI) {
+  assert(
+      (MO.isReg() || MO.isRegMask()) &&
+      "removeMapRegEntry must be called with a register or regmask operand.");
+
+  SmallVector<Register, 2> Srcs;
+  for (auto SI : RegMap) {
+    Register ToReg = SI.second;
+    if (ToReg.isVirtual())
+      continue;
+
+    if (MO.isReg()) {
+      Register Reg = MO.getReg();
+      if (TRI->regsOverlap(ToReg, Reg))
+        Srcs.push_back(SI.first);
+    } else if (MO.clobbersPhysReg(ToReg))
+      Srcs.push_back(SI.first);
+  }
+
+  for (auto SrcReg : Srcs)
+    RegMap.erase(SrcReg);
+}
+
+/// If a physical register is clobbered, old entries mapped to it should be
+/// deleted. For example
+///
+///     %2:gr64 = COPY killed $rdx
+///     MUL64r %3:gr64, implicit-def $rax, implicit-def $rdx
+///
+/// After the MUL instruction, $rdx contains different value than in the COPY
+/// instruction. So %2 should not map to $rdx after MUL.
+void TwoAddressInstructionPass::removeClobberedSrcRegMap(MachineInstr *MI) {
+  if (MI->isCopy()) {
+    // If a virtual register is copied to its mapped physical register, it
+    // doesn't change the potential coalescing between them, so we don't remove
+    // entries mapped to the physical register. For example
+    //
+    // %100 = COPY $r8
+    //     ...
+    // $r8  = COPY %100
+    //
+    // The first copy constructs SrcRegMap[%100] = $r8, the second copy doesn't
+    // destroy the content of $r8, and should not impact SrcRegMap.
+    Register Dst = MI->getOperand(0).getReg();
+    if (!Dst || Dst.isVirtual())
+      return;
+
+    Register Src = MI->getOperand(1).getReg();
+    if (regsAreCompatible(Dst, getMappedReg(Src, SrcRegMap), TRI))
+      return;
+  }
+
+  for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) {
+    const MachineOperand &MO = MI->getOperand(i);
+    if (MO.isRegMask()) {
+      removeMapRegEntry(MO, SrcRegMap, TRI);
+      continue;
+    }
+    if (!MO.isReg() || !MO.isDef())
+      continue;
+    Register Reg = MO.getReg();
+    if (!Reg || Reg.isVirtual())
+      continue;
+    removeMapRegEntry(MO, SrcRegMap, TRI);
+  }
+}
+
 // Returns true if Reg is equal or aliased to at least one register in Set.
 static bool regOverlapsSet(const SmallVectorImpl<Register> &Set, Register Reg,
                            const TargetRegisterInfo *TRI) {
@@ -589,21 +674,15 @@ bool TwoAddressInstructionPass::isProfitableToConv3Addr(Register RegA,
 /// Return true if this transformation was successful.
 bool TwoAddressInstructionPass::convertInstTo3Addr(
     MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi,
-    Register RegA, Register RegB, unsigned Dist) {
-  // FIXME: Why does convertToThreeAddress() need an iterator reference?
-  MachineFunction::iterator MFI = MBB->getIterator();
-  MachineInstr *NewMI = TII->convertToThreeAddress(MFI, *mi, LV);
-  assert(MBB->getIterator() == MFI &&
-         "convertToThreeAddress changed iterator reference");
+    Register RegA, Register RegB, unsigned &Dist) {
+  MachineInstrSpan MIS(mi, MBB);
+  MachineInstr *NewMI = TII->convertToThreeAddress(*mi, LV, LIS);
   if (!NewMI)
     return false;
 
   LLVM_DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi);
   LLVM_DEBUG(dbgs() << "2addr:         TO 3-ADDR: " << *NewMI);
 
-  if (LIS)
-    LIS->ReplaceMachineInstrInMaps(*mi, *NewMI);
-
   // If the old instruction is debug value tracked, an update is required.
   if (auto OldInstrNum = mi->peekDebugInstrNum()) {
     // Sanity check.
@@ -624,7 +703,9 @@ bool TwoAddressInstructionPass::convertInstTo3Addr(
 
   MBB->erase(mi); // Nuke the old inst.
 
-  DistanceMap.insert(std::make_pair(NewMI, Dist));
+  for (MachineInstr &MI : MIS)
+    DistanceMap.insert(std::make_pair(&MI, Dist++));
+  Dist--;
   mi = NewMI;
   nmi = std::next(mi);
 
@@ -656,9 +737,7 @@ void TwoAddressInstructionPass::scanUses(Register DstReg) {
       VirtRegPairs.push_back(NewReg);
       break;
     }
-    bool isNew = SrcRegMap.insert(std::make_pair(NewReg, Reg)).second;
-    if (!isNew)
-      assert(SrcRegMap[NewReg] == Reg && "Can't map to two src registers!");
+    SrcRegMap[NewReg] = Reg;
     VirtRegPairs.push_back(NewReg);
     Reg = NewReg;
   }
@@ -667,8 +746,7 @@ void TwoAddressInstructionPass::scanUses(Register DstReg) {
     unsigned ToReg = VirtRegPairs.back();
     VirtRegPairs.pop_back();
     while (!VirtRegPairs.empty()) {
-      unsigned FromReg = VirtRegPairs.back();
-      VirtRegPairs.pop_back();
+      unsigned FromReg = VirtRegPairs.pop_back_val();
       bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second;
       if (!isNew)
         assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!");
@@ -857,12 +935,13 @@ bool TwoAddressInstructionPass::rescheduleMIBelowKill(
   nmi = End;
   MachineBasicBlock::iterator InsertPos = KillPos;
   if (LIS) {
-    // We have to move the copies first so that the MBB is still well-formed
-    // when calling handleMove().
+    // We have to move the copies (and any interleaved debug instructions)
+    // first so that the MBB is still well-formed when calling handleMove().
     for (MachineBasicBlock::iterator MBBI = AfterMI; MBBI != End;) {
       auto CopyMI = MBBI++;
       MBB->splice(InsertPos, MBB, CopyMI);
-      LIS->handleMove(*CopyMI);
+      if (!CopyMI->isDebugOrPseudoInstr())
+        LIS->handleMove(*CopyMI);
       InsertPos = CopyMI;
     }
     End = std::next(MachineBasicBlock::iterator(MI));
@@ -1130,7 +1209,7 @@ bool TwoAddressInstructionPass::
 tryInstructionTransform(MachineBasicBlock::iterator &mi,
                         MachineBasicBlock::iterator &nmi,
                         unsigned SrcIdx, unsigned DstIdx,
-                        unsigned Dist, bool shouldOnlyCommute) {
+                        unsigned &Dist, bool shouldOnlyCommute) {
   if (OptLevel == CodeGenOpt::None)
     return false;
 
@@ -1238,6 +1317,8 @@ tryInstructionTransform(MachineBasicBlock::iterator &mi,
         // look "normal" to the transformation logic.
         MBB->insert(mi, NewMIs[0]);
         MBB->insert(mi, NewMIs[1]);
+        DistanceMap.insert(std::make_pair(NewMIs[0], Dist++));
+        DistanceMap.insert(std::make_pair(NewMIs[1], Dist));
 
         LLVM_DEBUG(dbgs() << "2addr:    NEW LOAD: " << *NewMIs[0]
                           << "2addr:    NEW INST: " << *NewMIs[1]);
@@ -1288,9 +1369,12 @@ tryInstructionTransform(MachineBasicBlock::iterator &mi,
               if (MO.isReg())
                 OrigRegs.push_back(MO.getReg());
             }
+
+            LIS->RemoveMachineInstrFromMaps(MI);
           }
 
           MI.eraseFromParent();
+          DistanceMap.erase(&MI);
 
           // Update LiveIntervals.
           if (LIS) {
@@ -1307,6 +1391,9 @@ tryInstructionTransform(MachineBasicBlock::iterator &mi,
           LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
           NewMIs[0]->eraseFromParent();
           NewMIs[1]->eraseFromParent();
+          DistanceMap.erase(NewMIs[0]);
+          DistanceMap.erase(NewMIs[1]);
+          Dist--;
         }
       }
     }
@@ -1320,7 +1407,6 @@ tryInstructionTransform(MachineBasicBlock::iterator &mi,
 // Return true if any tied operands where found, including the trivial ones.
 bool TwoAddressInstructionPass::
 collectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) {
-  const MCInstrDesc &MCID = MI->getDesc();
   bool AnyOps = false;
   unsigned NumOps = MI->getNumOperands();
 
@@ -1342,10 +1428,10 @@ collectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) {
     // Deal with undef uses immediately - simply rewrite the src operand.
     if (SrcMO.isUndef() && !DstMO.getSubReg()) {
       // Constrain the DstReg register class if required.
-      if (DstReg.isVirtual())
-        if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx,
-                                                             TRI, *MF))
-          MRI->constrainRegClass(DstReg, RC);
+      if (DstReg.isVirtual()) {
+        const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
+        MRI->constrainRegClass(DstReg, RC);
+      }
       SrcMO.setReg(DstReg);
       SrcMO.setSubReg(0);
       LLVM_DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI);
@@ -1434,12 +1520,24 @@ TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI,
     if (LIS) {
       LastCopyIdx = LIS->InsertMachineInstrInMaps(*PrevMI).getRegSlot();
 
+      SlotIndex endIdx =
+          LIS->getInstructionIndex(*MI).getRegSlot(IsEarlyClobber);
       if (RegA.isVirtual()) {
         LiveInterval &LI = LIS->getInterval(RegA);
         VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
-        SlotIndex endIdx =
-            LIS->getInstructionIndex(*MI).getRegSlot(IsEarlyClobber);
-        LI.addSegment(LiveInterval::Segment(LastCopyIdx, endIdx, VNI));
+        LI.addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI));
+        for (auto &S : LI.subranges()) {
+          VNI = S.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
+          S.addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI));
+        }
+      } else {
+        for (MCRegUnitIterator Unit(RegA, TRI); Unit.isValid(); ++Unit) {
+          if (LiveRange *LR = LIS->getCachedRegUnit(*Unit)) {
+            VNInfo *VNI =
+                LR->getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
+            LR->addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI));
+          }
+        }
       }
     }
 
@@ -1461,49 +1559,58 @@ TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI,
     // by SubRegB is compatible with RegA with no subregister. So regardless of
     // whether the dest oper writes a subreg, the source oper should not.
     MO.setSubReg(0);
-
-    // Propagate SrcRegMap.
-    SrcRegMap[RegA] = RegB;
   }
 
   if (AllUsesCopied) {
-    bool ReplacedAllUntiedUses = true;
-    if (!IsEarlyClobber) {
-      // Replace other (un-tied) uses of regB with LastCopiedReg.
-      for (MachineOperand &MO : MI->operands()) {
-        if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) {
-          if (MO.getSubReg() == SubRegB) {
-            if (MO.isKill()) {
-              MO.setIsKill(false);
-              RemovedKillFlag = true;
-            }
-            MO.setReg(LastCopiedReg);
-            MO.setSubReg(0);
-          } else {
-            ReplacedAllUntiedUses = false;
+    LaneBitmask RemainingUses = LaneBitmask::getNone();
+    // Replace other (un-tied) uses of regB with LastCopiedReg.
+    for (MachineOperand &MO : MI->operands()) {
+      if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) {
+        if (MO.getSubReg() == SubRegB && !IsEarlyClobber) {
+          if (MO.isKill()) {
+            MO.setIsKill(false);
+            RemovedKillFlag = true;
           }
+          MO.setReg(LastCopiedReg);
+          MO.setSubReg(0);
+        } else {
+          RemainingUses |= TRI->getSubRegIndexLaneMask(MO.getSubReg());
         }
       }
     }
 
     // Update live variables for regB.
-    if (RemovedKillFlag && ReplacedAllUntiedUses &&
-        LV && LV->getVarInfo(RegB).removeKill(*MI)) {
+    if (RemovedKillFlag && RemainingUses.none() && LV &&
+        LV->getVarInfo(RegB).removeKill(*MI)) {
       MachineBasicBlock::iterator PrevMI = MI;
       --PrevMI;
       LV->addVirtualRegisterKilled(RegB, *PrevMI);
     }
 
+    if (RemovedKillFlag && RemainingUses.none())
+      SrcRegMap[LastCopiedReg] = RegB;
+
     // Update LiveIntervals.
     if (LIS) {
-      LiveInterval &LI = LIS->getInterval(RegB);
-      SlotIndex MIIdx = LIS->getInstructionIndex(*MI);
-      LiveInterval::const_iterator I = LI.find(MIIdx);
-      assert(I != LI.end() && "RegB must be live-in to use.");
+      SlotIndex UseIdx = LIS->getInstructionIndex(*MI);
+      auto Shrink = [=](LiveRange &LR, LaneBitmask LaneMask) {
+        LiveRange::Segment *S = LR.getSegmentContaining(LastCopyIdx);
+        if (!S)
+          return true;
+        if ((LaneMask & RemainingUses).any())
+          return false;
+        if (S->end.getBaseIndex() != UseIdx)
+          return false;
+        S->end = LastCopyIdx;
+        return true;
+      };
 
-      SlotIndex UseIdx = MIIdx.getRegSlot(IsEarlyClobber);
-      if (I->end == UseIdx)
-        LI.removeSegment(LastCopyIdx, UseIdx);
+      LiveInterval &LI = LIS->getInterval(RegB);
+      bool ShrinkLI = true;
+      for (auto &S : LI.subranges())
+        ShrinkLI &= Shrink(S, S.LaneMask);
+      if (ShrinkLI)
+        Shrink(LI, LaneBitmask::getAll());
     }
   } else if (RemovedKillFlag) {
     // Some tied uses of regB matched their destination registers, so
@@ -1580,6 +1687,7 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) {
       // First scan through all the tied register uses in this instruction
       // and record a list of pairs of tied operands for each register.
       if (!collectTiedOperands(&*mi, TiedOperands)) {
+        removeClobberedSrcRegMap(&*mi);
         mi = nmi;
         continue;
       }
@@ -1604,6 +1712,7 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) {
             // The tied operands have been eliminated or shifted further down
             // the block to ease elimination. Continue processing with 'nmi'.
             TiedOperands.clear();
+            removeClobberedSrcRegMap(&*mi);
             mi = nmi;
             continue;
           }
@@ -1628,18 +1737,44 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) {
         mi->RemoveOperand(1);
         mi->setDesc(TII->get(TargetOpcode::COPY));
         LLVM_DEBUG(dbgs() << "\t\tconvert to:\t" << *mi);
+
+        // Update LiveIntervals.
+        if (LIS) {
+          Register Reg = mi->getOperand(0).getReg();
+          LiveInterval &LI = LIS->getInterval(Reg);
+          if (LI.hasSubRanges()) {
+            // The COPY no longer defines subregs of %reg except for
+            // %reg.subidx.
+            LaneBitmask LaneMask =
+                TRI->getSubRegIndexLaneMask(mi->getOperand(0).getSubReg());
+            SlotIndex Idx = LIS->getInstructionIndex(*mi);
+            for (auto &S : LI.subranges()) {
+              if ((S.LaneMask & LaneMask).none()) {
+                LiveRange::iterator UseSeg = S.FindSegmentContaining(Idx);
+                LiveRange::iterator DefSeg = std::next(UseSeg);
+                S.MergeValueNumberInto(DefSeg->valno, UseSeg->valno);
+              }
+            }
+
+            // The COPY no longer has a use of %reg.
+            LIS->shrinkToUses(&LI);
+          } else {
+            // The live interval for Reg did not have subranges but now it needs
+            // them because we have introduced a subreg def. Recompute it.
+            LIS->removeInterval(Reg);
+            LIS->createAndComputeVirtRegInterval(Reg);
+          }
+        }
       }
 
       // Clear TiedOperands here instead of at the top of the loop
       // since most instructions do not have tied operands.
       TiedOperands.clear();
+      removeClobberedSrcRegMap(&*mi);
       mi = nmi;
     }
   }
 
-  if (LIS)
-    MF->verify(this, "After two-address instruction pass");
-
   return MadeChange;
 }
 
@@ -1722,6 +1857,9 @@ eliminateRegSequence(MachineBasicBlock::iterator &MBBI) {
     for (int j = MI.getNumOperands() - 1, ee = 0; j > ee; --j)
       MI.RemoveOperand(j);
   } else {
+    if (LIS)
+      LIS->RemoveMachineInstrFromMaps(MI);
+
     LLVM_DEBUG(dbgs() << "Eliminated: " << MI);
     MI.eraseFromParent();
   }