[VirtRegRewriter] Eliminate COPYs before re-writing by renaming.

[gberry]

Summary

This adds a simple copy propagation pass to VirtRegRewriter that uses
LiveIntervals to find COPYs whose destination can be renamed allowing
the COPY to be eliminated when doing so would be beneficial.

[qcolombet]

Hi Geoff,

Disclaimer: I haven't looked at the patch, just a comment.
I would rather fix the MachineCopyPropagation pass than adding this logic to this pass.

Why aren't we catching those cases in the MachineCopyPropagation pass?

Cheers,
-Quentin

[gberry]

In D25347#563996, @qcolombet wrote:

Hi Geoff,

Disclaimer: I haven't looked at the patch, just a comment.
I would rather fix the MachineCopyPropagation pass than adding this logic to this pass.

Why aren't we catching those cases in the MachineCopyPropagation pass?

Hi Quentin,

I believe this was discussed before here: https://reviews.llvm.org/D20531. In this change, the COPYs only become removable as the result of renaming/recoloring their destination registers. I thought the consensus was that this recoloring was only safe to do with virtual registers to avoid violating ABI/other register constraints. The COPYs that this change catches are mostly only removable after register allocation since they are only removable once live range splitting/spilling has occurred.

In D25347#563996, @qcolombet wrote:

Hi Geoff,

Disclaimer: I haven't looked at the patch, just a comment.
I would rather fix the MachineCopyPropagation pass than adding this logic to this pass.

Why aren't we catching those cases in the MachineCopyPropagation pass?

Cheers,
-Quentin

[gberry]

Hi Quentin,
I've discovered a problem with this change that I am in the middle of addressing. Unfortunately, I'm going to be out for the rest of the week, so I won't be able to upload a new version until sometime next week.

[gberry]

Update algorithm to be more contained w.r.t. kill flag updating

[gberry]

Hi Quentin (and anyone else interested),

I just uploaded a new version that fixes the last issue that I am aware of and also simplifies the algorithm a bit. Please take a look when you get a chance.

[qcolombet]

Hi Geoff,

I'll have a look by the end of the week.
I still worried by having so much logic in the rewriter, it feels wrong to me. I'll check what happen in the alloc to see if we could catch that there.

Cheers,
-Quentin

[gberry]

Hi Quentin,

Thanks. FWIW, I could split this out into a separate pass that optionally runs just before VirtRegRewriter if that is more desirable.

[qcolombet]

Hi Geoff,

I could split this out into a separate pass that optionally runs just before VirtRegRewriter if that is more desirable.

Yes, that's more desirable.

Thanks,
Q.

[qcolombet]

lib/CodeGen/VirtRegMap.cpp

158

For consistency with the rest of LLVM source code I would use typedef.

158

Having read the code now, I believe it would be more efficient to map PhysReg to LI.
It would greatly simplify add/removeMappedPhysReg.

227

We could gate that dependency on DisableRenameCopys.
That being said, if we move all that code in its own pass, that's not going to be a problem :).

305

Seems inefficient to use a vector here.
At the very least it should be sorted.

345

Looks to me like this is reimplementing functionalities already available in the LiveRegMatrix class.
Reuse that instead.

437

Wasn't the goal to propagate useless copies, i.e., that should always be beneficial, right?

If you want to do more, then please add test cases covering that. Indeed, as far as I can tell, the changes in the test cases only cover the simple case of propagating useless copies.

500

Add && "Msg" in the assert.

Also explain in the comment before the assert what would it take to extend that to multiple VNs.

[MatzeB]

I just read the main function to understand the purpose, comments below.

So my understanding is that this looks for

%vreg0 = COPY %vreg1

with vreg0 assigned different from vreg1 but where it is possible to use the vreg1's register for vreg0 as well without any interference?

This obviously needs to buildup new interference checking infrastructure. Why not do this as part of RegAlloc when LiveRegMatrix is still around?

lib/CodeGen/VirtRegMap.cpp

402–403

Try MachineRegisterInfo::hasOneDef(), LiveRange::constainsOneValue() seems to also count invalid VNInfos and I am not sure those are all cleared here.

410–414

Isn't that the same as VReg and should rather be assert(CopyDst.getReg() == VReg);

419–420

This needs to adjust to subregister indexes on the dest/source operand!

429

!TargetRegisterInfo::isVirtualRegister -> isPhysicalRegister that also avoids hitting NoReg (though not a problem in this case).

440

Call it MO instead of Opnd like most of the code?

451

Isn't &OpndInst.getOperand(1) == &Opnd always true and can be an assert?

453–456

What about subregister indexes?

[gberry]

This work has been superseded by

r287070 [RegAllocGreedy] Record missed hint for late recoloring

and other follow-on changes.

lib/CodeGen/VirtRegMap.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/VirtRegMap.h"
 #include "LiveDebugVariables.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveStackAnalysis.h"
+#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"

 //===----------------------------------------------------------------------===//
 //
 // The VirtRegRewriter is the last of the register allocator passes.
 // It rewrites virtual registers to physical registers as specified in the
 // VirtRegMap analysis. It also updates live-in information on basic blocks
 // according to LiveIntervals.
 //
 namespace {
+
+// Used to record register renaming done by copyProp, used by
+// fixupKillFlagsAfterCopyProp to fix kill flags.
+struct RegRename {
+  RegRename(unsigned DstVirtReg, unsigned SrcReg)
+      : DstVirtReg(DstVirtReg), SrcReg(SrcReg) {}
+
+  unsigned DstVirtReg;
+  unsigned SrcReg; // Can be virtual or physical
+};
+
+// Map from physical regunit to list of def SlotIndexes.
+using PhysDefsMap = DenseMap<unsigned, SmallVector<SlotIndex, 4>>;
+
 class VirtRegRewriter : public MachineFunctionPass {
   MachineFunction *MF;
   const TargetMachine *TM;
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
   MachineRegisterInfo *MRI;
   SlotIndexes *Indexes;
   LiveIntervals *LIS;
   VirtRegMap *VRM;
+  MachineBlockFrequencyInfo *MBFI;
 
   void rewrite();
+  void copyProp(SmallVectorImpl<RegRename>&);
+  void fixupKillFlagsAfterCopyProp(const SmallVectorImpl<RegRename>&);
   void addMBBLiveIns();
   bool readsUndefSubreg(const MachineOperand &MO) const;
   void addLiveInsForSubRanges(const LiveInterval &LI, unsigned PhysReg) const;
   void handleIdentityCopy(MachineInstr &MI) const;
 
 public:
   static char ID;
   VirtRegRewriter() : MachineFunctionPass(ID) {}

 
 INITIALIZE_PASS_BEGIN(VirtRegRewriter, "virtregrewriter",
                       "Virtual Register Rewriter", false, false)
 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
 INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables)
 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
+INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
 INITIALIZE_PASS_END(VirtRegRewriter, "virtregrewriter",
                     "Virtual Register Rewriter", false, false)
 
 char VirtRegRewriter::ID = 0;
 
 void VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
   AU.addRequired<LiveIntervals>();
   AU.addRequired<SlotIndexes>();
   AU.addPreserved<SlotIndexes>();
   AU.addRequired<LiveDebugVariables>();
   AU.addRequired<LiveStacks>();
   AU.addPreserved<LiveStacks>();
   AU.addRequired<VirtRegMap>();
+  AU.addRequired<MachineBlockFrequencyInfo>();
+  AU.addPreserved<MachineBlockFrequencyInfo>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 bool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) {
   MF = &fn;
   TM = &MF->getTarget();
   TRI = MF->getSubtarget().getRegisterInfo();
   TII = MF->getSubtarget().getInstrInfo();
   MRI = &MF->getRegInfo();
   Indexes = &getAnalysis<SlotIndexes>();
   LIS = &getAnalysis<LiveIntervals>();
   VRM = &getAnalysis<VirtRegMap>();
+  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
   DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n"
                << "********** Function: "
                << MF->getName() << '\n');
   DEBUG(VRM->dump());
 
+  // RegRenames records the register renamings done by copyProp for use by
+  // fixupKillFlagsAfterCopyProp in fixing up kill flags on renamed registers.
+  SmallVector<RegRename, 16> RegRenames;
+  copyProp(RegRenames);
+
   // Add kill flags while we still have virtual registers.
   LIS->addKillFlags(VRM);
 
+  // Remove kill flags to take into account register renamings done by copyProp.
+  fixupKillFlagsAfterCopyProp(RegRenames);
+
   // Live-in lists on basic blocks are required for physregs.
   addMBBLiveIns();
 
   // Rewrite virtual registers.
   rewrite();
 
   // Write out new DBG_VALUE instructions.
   getAnalysis<LiveDebugVariables>().emitDebugValues(VRM);
 
   // All machine operands and other references to virtual registers have been
   // replaced. Remove the virtual registers and release all the transient data.
   VRM->clearAllVirt();
   MRI->clearVirtRegs();
   return true;
 }
 
+static unsigned getPhysReg(const VirtRegMap &VRM, unsigned Reg) {
+  return TargetRegisterInfo::isVirtualRegister(Reg) ? VRM.getPhys(Reg) : Reg;
+};
+
+// Record PhysReg as being defined at every Index in LI that a def occurs.
+static void addMappedPhysDefs(PhysDefsMap &MappedPhysDefs,
+                              const LiveInterval &LI, unsigned PhysReg,
+                              const TargetRegisterInfo &TRI) {
+  for (MCRegUnitIterator Units(PhysReg, &TRI); Units.isValid(); ++Units) {
+    SmallVectorImpl<SlotIndex> &DefIndexes = MappedPhysDefs[*Units];
+    for (const LiveRange::Segment &S : LI.segments)
+      DefIndexes.push_back(S.start);
+  }
+}
+
+// Record PhysReg as no longer being defined at every Index in LI that a def
+// occurs.
+static void removeMappedPhysDefs(PhysDefsMap &MappedPhysDefs,
+                                 const LiveInterval &LI, unsigned PhysReg,
+                                 const TargetRegisterInfo &TRI) {
+  for (MCRegUnitIterator Units(PhysReg, &TRI); Units.isValid(); ++Units) {
+    SmallVectorImpl<SlotIndex> &DefIndexes = MappedPhysDefs[*Units];
+    for (const LiveRange::Segment &S : LI.segments) {
+      bool FoundDef = false;
+      for (auto DI = DefIndexes.begin(); DI != DefIndexes.end(); ++DI)
+        if (*DI == S.start) {
+          FoundDef = true;
+          std::iter_swap(DI, DefIndexes.end()-1);
+          DefIndexes.pop_back();
+          break;
+        }
+      assert(FoundDef && "Couldn't find def to remove.");
+    }
+  }
+}
+
+// Record the Indexes where every allocated physical register is defined.
+static void buildMappedPhysDefs(PhysDefsMap &MappedPhysDefs,
+                                const MachineRegisterInfo &MRI,
+                                const LiveIntervals &LIS,
+                                const TargetRegisterInfo &TRI,
+                                const VirtRegMap &VRM) {
+  // Build def index list for each physical reg unit allocated to a virtual
+  // register by scanning all live ranges.
+  for (size_t VI = 0, VE = MRI.getNumVirtRegs(); VI < VE; ++VI) {
+    unsigned VReg = TargetRegisterInfo::index2VirtReg(VI);
+    if (!LIS.hasInterval(VReg))
+      continue;
+
+    unsigned VIPhysReg = VRM.getPhys(VReg);
+    if (VIPhysReg == VirtRegMap::NO_PHYS_REG)
+      continue;
+
+    const LiveInterval &LI = LIS.getInterval(VReg);
+    addMappedPhysDefs(MappedPhysDefs, LI, VIPhysReg, TRI);
+  }
+}
+
+// Look for any LiveRanges that clobber SrcPhysReg over a given live interval.
+static bool isClobberedOverInterval(const LiveInterval &LI, unsigned PhysReg,
+                                    PhysDefsMap &MappedPhysDefs,
+                                    const MachineRegisterInfo &MRI,
+                                    const LiveIntervals &LIS,
+                                    const TargetRegisterInfo &TRI,
+                                    const VirtRegMap &VRM) {
+
+  for (MCRegUnitIterator Units(PhysReg, &TRI); Units.isValid(); ++Units) {
+    // Check physical reg live intervals.
+    if (const LiveRange *PLR = LIS.getCachedRegUnit(*Units))
+      for (auto SegI = PLR->begin(), SegE = PLR->end(); SegI != SegE; ++SegI)
+        if (LI.liveAt(SegI->start))
+          return true;
+
+    // Check virtual reg live intervals that are assigned to phys reg.
+    if (MappedPhysDefs.empty())
+      buildMappedPhysDefs(MappedPhysDefs, MRI, LIS, TRI, VRM);
+    auto MLRIt = MappedPhysDefs.find(*Units);
+    if (MLRIt != MappedPhysDefs.end())
+      for (const SlotIndex &DefIndex : MLRIt->second)
+        if (LI.liveAt(DefIndex))
+          return true;
+  }
+
+  // Check regmask clobbers.
+  const ArrayRef<SlotIndex> RegMaskSlots = LIS.getRegMaskSlots();
+  const ArrayRef<const uint32_t *> RegMaskBits = LIS.getRegMaskBits();
+  SlotIndex BeginIndex = LI.beginIndex();
+  SlotIndex EndIndex = LI.endIndex();
+  unsigned I = 0, E = RegMaskSlots.size();
+  // Skip over regmasks that are before LI starts.
+  for (; I != E && RegMaskSlots[I] < BeginIndex; ++I)
+    ;
+  // Stop once we reach a regmask that is after LI ends.
+  for (; I != E && RegMaskSlots[I] < EndIndex; ++I)
+    if (MachineOperand::clobbersPhysReg(RegMaskBits[I], PhysReg) &&
+        LI.liveAt(RegMaskSlots[I]))
+      return true;
+
+  return false;
+}
+
+// Look for COPY instructions that can be made unnecessary by propagating their
+// source value to all users.
+void VirtRegRewriter::copyProp(SmallVectorImpl<RegRename> &RegRenames) {
+  PhysDefsMap MappedPhysDefs;
+
+  for (size_t VI = 0, VE = MRI->getNumVirtRegs(); VI < VE; ++VI) {
+    unsigned VReg = TargetRegisterInfo::index2VirtReg(VI);
+    if (!LIS->hasInterval(VReg))
+      continue;
+    const LiveInterval &LI = LIS->getInterval(VReg);
+
+    // Don't consider intervals not assigned to a physical register.
+    if (VRM->getPhys(LI.reg) == VirtRegMap::NO_PHYS_REG)
+      continue;
+
+    // Only consider intervals that have a single def that is a full copy
+    // instruction.
+    if (!LI.containsOneValue())
+      continue;
+    const MachineInstr *MI =
+        Indexes->getInstructionFromIndex(LI.getValNumInfo(0)->def);
+    if (!MI || !MI->isFullCopy())
+      continue;
+
+    const MachineOperand &CopyDst = MI->getOperand(0);
+    unsigned DstReg = CopyDst.getReg();
+
+    // Only consider renaming virtual registers.
+    if (!TargetRegisterInfo::isVirtualRegister(DstReg))
+      continue;
+
+    const MachineOperand &CopySrc = MI->getOperand(1);
+    unsigned SrcReg = CopySrc.getReg();
+
+    unsigned DstPhysReg = getPhysReg(*VRM, DstReg);
+    unsigned SrcPhysReg = getPhysReg(*VRM, SrcReg);
+
+    // This copy will already be removed by handleIdentityCopy.
+    if (SrcPhysReg == DstPhysReg)
+      continue;
+    // Check that the allocated src reg is in the regclass of the dst reg.
+    if (!MRI->getRegClass(DstReg)->contains(SrcPhysReg))
+      continue;
+
+    bool IsSrcConstant = !TargetRegisterInfo::isVirtualRegister(SrcReg) &&
+      MRI->isConstantPhysReg(SrcPhysReg, *MF);
+
+    // Skip COPY from a reserved reg unless it is a known constant.
+    if (MRI->isReserved(SrcPhysReg) && !IsSrcConstant)
+      continue;
+
+    // Check the cost/benefit of renaming.
+    BlockFrequency DefFreq = MBFI->getBlockFreq(MI->getParent());
+    BlockFrequency Benefit(DefFreq);
+    BlockFrequency Cost(0);
+    for (const MachineOperand &Opnd : MRI->reg_nodbg_operands(DstReg)) {
+      const MachineInstr& OpndInst = *Opnd.getParent();
+      if (Opnd.isDef()) {
+        assert(&OpndInst == MI);
+        continue;
+      }
+      if (OpndInst.isFullCopy() && &OpndInst.getOperand(1) == &Opnd) {
+        BlockFrequency OpndFreq = MBFI->getBlockFreq(OpndInst.getParent());
+        unsigned OpndDstPhysReg =
+            getPhysReg(*VRM, OpndInst.getOperand(0).getReg());
+        unsigned OpndSrcPhysReg =
+            getPhysReg(*VRM, OpndInst.getOperand(1).getReg());
+        // This COPY would be removed if we don't rename.
+        if (OpndDstPhysReg == OpndSrcPhysReg)
+          Cost += OpndFreq;
+        // Renaming would cause this COPY to also be removed.
+        if (OpndDstPhysReg == SrcPhysReg)
+          Benefit += OpndFreq;
+      }
+    }
+    if (Cost >= Benefit)
+      continue;
+
+    // Check that the source register isn't clobbered at any point that the
+    // destination register is live.  We don't need to check for constant
+    // registers since they can't be clobbered by definition.
+    if (!IsSrcConstant &&
+        isClobberedOverInterval(LI, SrcPhysReg, MappedPhysDefs, *MRI,
+                                *LIS, *TRI, *VRM))
+      continue;
+
+    DEBUG(dbgs() << "Copyprop reassigning " << PrintReg(DstReg) << " to "
+                 << PrintReg(SrcPhysReg, TRI) << "\n";);
+    VRM->clearVirt(DstReg);
+    VRM->assignVirt2Phys(DstReg, SrcPhysReg);
+    RegRenames.emplace_back(DstReg, SrcReg);
+
+    // Update MappedPhysDefs since we are now clobbering SrcPhysReg at this COPY
+    // and no longer clobbering DstPhysReg.
+    // Don't need to update MappedPhysDefs if we haven't built it yet, which can
+    // be the case if we're renaming to a constant physical reg.
+    if (!MappedPhysDefs.empty())
+      removeMappedPhysDefs(MappedPhysDefs, LI, DstPhysReg, *TRI);
+    // Don't need to update constant physical reg defs since we never check for
+    // them.
+    if (!IsSrcConstant)
+      addMappedPhysDefs(MappedPhysDefs, LI, SrcPhysReg, *TRI);
+  }
+}
+
+// Clear kill flags of on uses of remapped registers that are no longer
+// accurate.
+// For example, in the following code:
+//
+//   vr2 = COPY vr1
+//   ...
+//   OP vr1<kill>
+//   ...
+//   OP vr2<kill>
+//
+// since vr2 and vr1 are now mapped to the same register, the kill flag on vr1
+// must be removed.
+void VirtRegRewriter::fixupKillFlagsAfterCopyProp(
+    const SmallVectorImpl<RegRename> &RegRenames) {
+
+  auto clearOverlappingKill = [](MachineRegisterInfo &MRI, LiveIntervals &LIS,
+                                 unsigned Reg1, unsigned Reg2) {
+    LiveInterval &LI = LIS.getInterval(Reg1);
+    for (MachineOperand &Use : MRI.use_operands(Reg2)) {
+      if (Use.isKill()) {
+        SlotIndex UseIndex = LIS.getInstructionIndex(*Use.getParent());
+        if (LI.liveAt(UseIndex))
+          Use.setIsKill(false);
+      }
+    }
+  };
+
+  for (const RegRename &R : RegRenames)
+    if (TargetRegisterInfo::isVirtualRegister(R.SrcReg)) {
+      clearOverlappingKill(*MRI, *LIS, R.SrcReg, R.DstVirtReg);
+      clearOverlappingKill(*MRI, *LIS, R.DstVirtReg, R.SrcReg);
+    }
+}
+
 void VirtRegRewriter::addLiveInsForSubRanges(const LiveInterval &LI,
                                              unsigned PhysReg) const {
   assert(!LI.empty());
   assert(LI.hasSubRanges());
 
   typedef std::pair<const LiveInterval::SubRange *,
                     LiveInterval::const_iterator> SubRangeIteratorPair;
   SmallVector<SubRangeIteratorPair, 4> SubRanges;
for (MachineBasicBlock::instr_iterator
           MRI->addPhysRegsUsedFromRegMask(MO.getRegMask());
 
         if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
           continue;
         unsigned VirtReg = MO.getReg();
         unsigned PhysReg = VRM->getPhys(VirtReg);
         assert(PhysReg != VirtRegMap::NO_PHYS_REG &&
                "Instruction uses unmapped VirtReg");
-        assert(!MRI->isReserved(PhysReg) && "Reserved register assignment");
+        assert((!MRI->isReserved(PhysReg) ||
+                MRI->isConstantPhysReg(PhysReg, *MF)) &&
+               "Reserved register assignment");
 
         // Preserve semantics of sub-register operands.
         unsigned SubReg = MO.getSubReg();
         if (SubReg != 0) {
           if (NoSubRegLiveness) {
             // A virtual register kill refers to the whole register, so we may
             // have to add <imp-use,kill> operands for the super-register.  A
             // partial redef always kills and redefines the super-register.

test/CodeGen/AArch64/machine_cse_impdef_killflags.ll

 ; RUN: llc < %s -mtriple=aarch64-apple-ios -fast-isel -verify-machineinstrs | FileCheck %s
 
 ; Check that the kill flag is cleared between CSE'd instructions on their
 ; imp-def'd registers.
 ; The verifier would complain otherwise.
 define i64 @csed-impdef-killflag(i64 %a) {
 ; CHECK-LABEL: csed-impdef-killflag
-; CHECK-DAG:  mov    [[REG0:w[0-9]+]], wzr
 ; CHECK-DAG:  orr    [[REG1:w[0-9]+]], wzr, #0x1
 ; CHECK-DAG:  orr    [[REG2:x[0-9]+]], xzr, #0x2
 ; CHECK-DAG:  orr    [[REG3:x[0-9]+]], xzr, #0x3
 ; CHECK:      cmp    x0, #0
-; CHECK-DAG:  csel   w[[SELECT_WREG_1:[0-9]+]], [[REG0]], [[REG1]], ne
+; CHECK-DAG:  csel   w[[SELECT_WREG_1:[0-9]+]], wzr, [[REG1]], ne
 ; CHECK-DAG:  csel   [[SELECT_XREG_2:x[0-9]+]], [[REG2]], [[REG3]], ne
 ; CHECK:      ubfx   [[SELECT_XREG_1:x[0-9]+]], x[[SELECT_WREG_1]], #0, #32
 ; CHECK-NEXT: add    x0, [[SELECT_XREG_2]], [[SELECT_XREG_1]]
 ; CHECK-NEXT: ret
 
   %1 = icmp ne i64 %a, 0
   %2 = select i1 %1, i32 0, i32 1
   %3 = icmp ne i64 %a, 0
   %4 = select i1 %3, i64 2, i64 3
   %5 = zext i32 %2 to i64
   %6 = add i64 %4, %5
   ret i64 %6
 }

test/CodeGen/X86/ipra-local-linkage.ll

define void @bar(i32 %X) {
   call void asm sideeffect "movl  %r12d, $0", "{r15}~{r12}"(i32 %X)
   ; As R15 is clobbered by foo() when IPRA is enabled value of R15 should be
   ; saved if register containing orignal value is also getting clobbered
   ; and reloaded after foo(), here original value is loaded back into R15D after
   ; call to foo.
   call void @foo()
   ; CHECK-LABEL: bar:
   ; CHECK: callq foo
-  ; CHECK-NEXT: movl  %eax, %r15d
+  ; CHECK-NEXT: movl  %edi, %r15d
   call void asm sideeffect "movl  $0, %r12d", "{r15}~{r12}"(i32 %X)
   ret void
 }

test/CodeGen/X86/mul-i1024.ll

 ; X64-NEXT:    movq %rax, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    addq {{[0-9]+}}(%rsp), %rax # 8-byte Folded Reload
 ; X64-NEXT:    movq %rdx, %rcx
 ; X64-NEXT:    adcq %r15, %rcx
 ; X64-NEXT:    addq %rsi, %rax
 ; X64-NEXT:    movq %rax, %r13
 ; X64-NEXT:    adcq %rbp, %rcx
 ; X64-NEXT:    movq %rcx, %rbp
-; X64-NEXT:    movq %r11, %rcx
-; X64-NEXT:    movq (%rcx), %r8
+; X64-NEXT:    movq (%r11), %r8
 ; X64-NEXT:    movq %r8, %rax
-; X64-NEXT:    movq %r12, %rsi
-; X64-NEXT:    mulq %rsi
+; X64-NEXT:    mulq %r12
 ; X64-NEXT:    movq %rax, %rdi
 ; X64-NEXT:    movq %rdi, -{{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    movq %rdx, %r10
 ; X64-NEXT:    movq %r10, {{[0-9]+}}(%rsp) # 8-byte Spill
-; X64-NEXT:    movq 8(%rcx), %r11
+; X64-NEXT:    movq 8(%r11), %r11
 ; X64-NEXT:    movq %r11, %rax
-; X64-NEXT:    mulq %rsi
+; X64-NEXT:    mulq %r12
 ; X64-NEXT:    movq %rax, %rsi
 ; X64-NEXT:    addq %rdi, %rsi
 ; X64-NEXT:    adcq $0, %rdx
 ; X64-NEXT:    movq %rdx, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    movq %r8, %rax
 ; X64-NEXT:    mulq %r9
 ; X64-NEXT:    movq %rdx, %r12
 ; X64-NEXT:    addq %rsi, %rax

 ; X64-NEXT:    movq %r11, -{{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    imulq %r15, %rcx
 ; X64-NEXT:    movq %rcx, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    leaq (%r13,%rdi), %rsi
 ; X64-NEXT:    addq %rcx, %rsi
 ; X64-NEXT:    addq %r9, %rbx
 ; X64-NEXT:    adcq %rdx, %rsi
 ; X64-NEXT:    movq %r8, %rax
-; X64-NEXT:    movq %r8, %r15
-; X64-NEXT:    movq %r15, -{{[0-9]+}}(%rsp) # 8-byte Spill
+; X64-NEXT:    movq %r8, -{{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    xorl %ecx, %ecx
 ; X64-NEXT:    mulq %rcx
 ; X64-NEXT:    movq %rax, %rdi
 ; X64-NEXT:    movq %rax, %r9
 ; X64-NEXT:    movq %r9, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    addq -{{[0-9]+}}(%rsp), %rdi # 8-byte Folded Reload
 ; X64-NEXT:    movq %rdx, %rcx
-; X64-NEXT:    movq %rdx, %r8
-; X64-NEXT:    movq %r8, {{[0-9]+}}(%rsp) # 8-byte Spill
+; X64-NEXT:    movq %rdx, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    adcq {{[0-9]+}}(%rsp), %rcx # 8-byte Folded Reload
 ; X64-NEXT:    addq %rbx, %rdi
 ; X64-NEXT:    adcq %rsi, %rcx
 ; X64-NEXT:    addq %r13, %r10
 ; X64-NEXT:    movq %r10, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    adcq %r14, %rbp
 ; X64-NEXT:    movq %rbp, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    adcq $0, %rdi
 ; X64-NEXT:    movq %rdi, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    adcq $0, %rcx
 ; X64-NEXT:    movq %rcx, -{{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    addq {{[0-9]+}}(%rsp), %r12 # 8-byte Folded Reload
 ; X64-NEXT:    sbbq %rax, %rax
-; X64-NEXT:    movq %r15, %rcx
+; X64-NEXT:    movq %r8, %rcx
 ; X64-NEXT:    imulq -{{[0-9]+}}(%rsp), %rcx # 8-byte Folded Reload
 ; X64-NEXT:    addq {{[0-9]+}}(%rsp), %rcx # 8-byte Folded Reload
 ; X64-NEXT:    imulq -{{[0-9]+}}(%rsp), %r11 # 8-byte Folded Reload
 ; X64-NEXT:    addq %rcx, %r11
 ; X64-NEXT:    andl $1, %eax
 ; X64-NEXT:    addq -{{[0-9]+}}(%rsp), %r12 # 8-byte Folded Reload
 ; X64-NEXT:    movq %r12, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    adcq %rax, %r11

 ; X64-NEXT:    adcq %rdi, %rax
 ; X64-NEXT:    movq %rax, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    adcq %rbp, %rdx
 ; X64-NEXT:    movq %rdx, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    movq {{[0-9]+}}(%rsp), %rdi # 8-byte Reload
 ; X64-NEXT:    addq {{[0-9]+}}(%rsp), %rdi # 8-byte Folded Reload
 ; X64-NEXT:    movq -{{[0-9]+}}(%rsp), %rbp # 8-byte Reload
 ; X64-NEXT:    adcq {{[0-9]+}}(%rsp), %rbp # 8-byte Folded Reload
-; X64-NEXT:    movq %r9, %rsi
-; X64-NEXT:    movq %rsi, %rax
+; X64-NEXT:    movq %r9, %rax
 ; X64-NEXT:    movq {{[0-9]+}}(%rsp), %rcx # 8-byte Reload
 ; X64-NEXT:    mulq %rcx
 ; X64-NEXT:    movq %rdx, %r14
 ; X64-NEXT:    movq %rax, %r8
 ; X64-NEXT:    movq -{{[0-9]+}}(%rsp), %rax # 8-byte Reload
 ; X64-NEXT:    mulq %rcx
 ; X64-NEXT:    movq %rdx, %rbx
 ; X64-NEXT:    movq %rax, %rcx
 ; X64-NEXT:    addq %r8, %rcx
 ; X64-NEXT:    adcq $0, %rbx
-; X64-NEXT:    movq %rsi, %rax
+; X64-NEXT:    movq %r9, %rax
 ; X64-NEXT:    mulq {{[0-9]+}}(%rsp) # 8-byte Folded Reload
 ; X64-NEXT:    movq %rdx, %rsi
 ; X64-NEXT:    movq %rax, %r15
 ; X64-NEXT:    addq %rcx, %r15
 ; X64-NEXT:    adcq $0, %rsi
 ; X64-NEXT:    addq %rbx, %rsi
 ; X64-NEXT:    sbbq %rax, %rax
 ; X64-NEXT:    movq -{{[0-9]+}}(%rsp), %r12 # 8-byte Reload

 ; X64-NEXT:    movq %rax, %rdi
 ; X64-NEXT:    addq {{[0-9]+}}(%rsp), %rdi # 8-byte Folded Reload
 ; X64-NEXT:    adcq {{[0-9]+}}(%rsp), %rcx # 8-byte Folded Reload
 ; X64-NEXT:    addq %rsi, %rdi
 ; X64-NEXT:    adcq %rbp, %rcx
 ; X64-NEXT:    movq %r9, %rsi
 ; X64-NEXT:    movq 64(%rsi), %rax
 ; X64-NEXT:    movq %rax, %r13
-; X64-NEXT:    movq %r14, %rbp
-; X64-NEXT:    mulq %rbp
+; X64-NEXT:    mulq %r14
 ; X64-NEXT:    movq %rax, %rbx
 ; X64-NEXT:    movq %rbx, -{{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    movq %rdx, %r9
 ; X64-NEXT:    movq %r9, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    movq 72(%rsi), %r8
 ; X64-NEXT:    movq %r8, %rax
-; X64-NEXT:    mulq %rbp
+; X64-NEXT:    mulq %r14
 ; X64-NEXT:    movq %rax, %rsi
 ; X64-NEXT:    addq %rbx, %rsi
 ; X64-NEXT:    adcq $0, %rdx
 ; X64-NEXT:    movq %rdx, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    movq %r13, %rax
 ; X64-NEXT:    mulq %r10
 ; X64-NEXT:    addq %rsi, %rax
 ; X64-NEXT:    movq %rax, {{[0-9]+}}(%rsp) # 8-byte Spill

 ; X64-NEXT:    addq %rbp, %rdx
 ; X64-NEXT:    andl $1, %eax
 ; X64-NEXT:    addq %r10, %rdi
 ; X64-NEXT:    adcq %rax, %rdx
 ; X64-NEXT:    addq %r11, %rdi
 ; X64-NEXT:    adcq %rbx, %rdx
 ; X64-NEXT:    movq %rdx, -{{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    movq {{[0-9]+}}(%rsp), %rbx # 8-byte Reload
+; X64-NEXT:    imulq %r12, %rbx
 ; X64-NEXT:    movq %r12, %rax
-; X64-NEXT:    imulq %rax, %rbx
 ; X64-NEXT:    movq {{[0-9]+}}(%rsp), %rcx # 8-byte Reload
 ; X64-NEXT:    mulq %rcx
 ; X64-NEXT:    movq %rax, %rsi
 ; X64-NEXT:    addq %rbx, %rdx
 ; X64-NEXT:    movq -{{[0-9]+}}(%rsp), %r8 # 8-byte Reload
 ; X64-NEXT:    imulq %r8, %rcx
 ; X64-NEXT:    addq %rdx, %rcx
 ; X64-NEXT:    movq %rcx, %r11

test/CodeGen/X86/mul-i512.ll

 ; X64-NEXT:    mulq %rbp
 ; X64-NEXT:    movq %rdx, %rcx
 ; X64-NEXT:    movq %rax, %r9
 ; X64-NEXT:    addq %rsi, %r9
 ; X64-NEXT:    adcq $0, %rcx
 ; X64-NEXT:    addq %rbx, %rcx
 ; X64-NEXT:    sbbq %rax, %rax
 ; X64-NEXT:    andl $1, %eax
-; X64-NEXT:    movq %r15, %rbx
-; X64-NEXT:    movq %rbx, -{{[0-9]+}}(%rsp) # 8-byte Spill
-; X64-NEXT:    movq %rbx, %rdx
+; X64-NEXT:    movq %r15, -{{[0-9]+}}(%rsp) # 8-byte Spill
+; X64-NEXT:    movq %r15, %rdx
 ; X64-NEXT:    imulq %rbp, %rdx
 ; X64-NEXT:    movq %rdx, -{{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    movq %rbp, %r12
 ; X64-NEXT:    movq %r12, -{{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    leaq (%r8,%rdx), %rbp
 ; X64-NEXT:    imulq %r11, %r14
 ; X64-NEXT:    movq %r14, -{{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    addq %r14, %rbp
 ; X64-NEXT:    addq %r10, %rcx
 ; X64-NEXT:    adcq %rax, %rbp
 ; X64-NEXT:    xorl %r14d, %r14d
 ; X64-NEXT:    movq %r11, %rax
 ; X64-NEXT:    mulq %r14
 ; X64-NEXT:    movq %rdx, %r10
 ; X64-NEXT:    movq %r10, {{[0-9]+}}(%rsp) # 8-byte Spill
 ; X64-NEXT:    movq %rax, %rsi
 ; X64-NEXT:    movq %rsi, {{[0-9]+}}(%rsp) # 8-byte Spill
-; X64-NEXT:    movq %rbx, %rax
+; X64-NEXT:    movq %r15, %rax
 ; X64-NEXT:    mulq %r14
 ; X64-NEXT:    movq %rdx, %r14
 ; X64-NEXT:    movq %rax, %rbx
 ; X64-NEXT:    addq %rsi, %rbx
 ; X64-NEXT:    adcq %r10, %r14
 ; X64-NEXT:    addq %rcx, %rbx
 ; X64-NEXT:    adcq %rbp, %r14
 ; X64-NEXT:    movq %rdi, -{{[0-9]+}}(%rsp) # 8-byte Spill