[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.

221

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 :).

296

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

336

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

428

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.

491

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

393–394

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

401–405

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

410–411

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

420

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

431

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

442

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

444–447

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 {
+
+// 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 renameCopys();
   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) {}
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool runOnMachineFunction(MachineFunction&) override;
   MachineFunctionProperties getSetProperties() const override {
     return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::NoVRegs);
   }
 };
 } // end anonymous namespace
 
+static cl::opt<bool> DisableRenameCopys(
+    "disable-virtregrewriter-rename", cl::Hidden,
+    cl::desc(
+        "Disable Virtual Register Rewriter Copy Rename Optimization"));
+
 char &llvm::VirtRegRewriterID = VirtRegRewriter::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());
 
+  // Rename virtual register COPY destinations to allow more identical COPYs to
+  // be removed.
+  if (!DisableRenameCopys)
+    renameCopys();
+
   // Add kill flags while we still have virtual registers.
   LIS->addKillFlags(VRM);
 
   // 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 (unsigned VI = 0, VE = LI.getNumValNums(); VI != VE; ++VI) {
+      SlotIndex DefIndex = LI.getValNumInfo(VI)->def;
+      if (!DefIndex.isValid())
+        continue;
+      DefIndexes.push_back(DefIndex);
+    }
+  }
+}
+
+// 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 (unsigned VI = 0, VE = LI.getNumValNums(); VI != VE; ++VI) {
+      SlotIndex DefIndex = LI.getValNumInfo(VI)->def;
+      if (!DefIndex.isValid())
+        continue;
+      bool FoundDef = false;
+      for (auto DI = DefIndexes.begin(); DI != DefIndexes.end(); ++DI)
+        if (*DI == DefIndex) {
+          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 (unsigned VI = 0, VE = PLR->getNumValNums(); VI != VE; ++VI) {
+        SlotIndex DefIndex = PLR->getValNumInfo(VI)->def;
+        if (DefIndex.isValid() && LI.liveAt(DefIndex))
+          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 beyond the end of LI.
+  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 renaming their
+// destination register live range to be the same as their source
+// register.
+void VirtRegRewriter::renameCopys() {
+  PhysDefsMap MappedPhysDefs;
+
+  for (size_t VI = 0, VE = MRI->getNumVirtRegs(); VI < VE; ++VI) {
+    unsigned VReg = TargetRegisterInfo::index2VirtReg(VI);
+    if (!LIS->hasInterval(VReg))
+      continue;
+    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()) {
+        // Ignore defs from the current COPY and from any COPYs we have
+        // previously renamed to make identical.
+        assert(&OpndInst == MI || OpndInst.isIdentityCopy());
+        continue;
+      }
+      // We've already counted the benefit from this previous renaming.
+      if (OpndInst.isIdentityCopy())
+        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() << "renameCopys reassigning " << PrintReg(DstReg) << " to "
+                 << PrintReg(SrcReg, TRI) << "(" << PrintReg(SrcPhysReg, TRI)
+                 << ")"
+                 << "\n";);
+
+    // Change COPY destination vreg mapping to COPY source reg assigned physical
+    // register.
+    VRM->clearVirt(DstReg);
+    VRM->assignVirt2Phys(DstReg, SrcPhysReg);
+
+    // Update MappedPhysDefs since we are now clobbering SrcPhysReg at this COPY
+    // and no longer clobbering DstPhysReg.  This needs to be done before we
+    // remove the interval for DstReg below.
+    // 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);
+
+    // Update LiveInterval info and replace COPY destination reg with COPY src
+    // reg so kill flags computation will be correct.
+    assert(LI.getNumValNums() == 1);
+    SlotIndex SrcDefPrevSlot = LI.getValNumInfo(0)->def.getPrevSlot();
+    if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
+      LiveInterval &SrcLI = LIS->getInterval(SrcReg);
+      VNInfo *SrcDefVN = SrcLI.getVNInfoAt(SrcDefPrevSlot);
+      LiveRangeUpdater Updater(&SrcLI);
+      for (const LiveRange::Segment &S : LI.segments)
+        Updater.add(S.start, S.end, SrcDefVN);
+      MRI->replaceRegWith(DstReg, SrcReg);
+      LIS->removeInterval(DstReg);
+    }
+  }
+}
+
 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