Add a callee-saved register verifier to LLVM

[sanjoy]

Summary

This change adds a pass to LLVM to (optionally) generate code around
function calls to check, at runtime, that the function preserves the
registers it is expected to preserve. The motivation for this was
covered on the list a couple of weeks ago [0], but generally the
intention is to support CSR verification around calls to hand-written
assembly stubs that are common in managed runtimes.

I'm not familiar with much of the areas of LLVM I've touched in this
patch, so a careful review will be appreciated.

[0]: http://lists.llvm.org/pipermail/llvm-dev/2016-May/099693.html

[mehdi_amini]

(summary from our IRC discussion)

I understand that is easier to do pre-RA, but I'm sad it won't help to validate the inter-procedural register allocation we're working on these days, because this will clobbered every physical registers and limit the analysis.
If other backend-gurus have a solution that could be easily implemented post-RA, I'd love it :)

[qcolombet]

include/llvm/InitializePasses.h

342

Could you sort that call in alphabetical order?
I know this is not the case for the last few calls, but really, it should be the case for all of them.

include/llvm/Target/TargetInstrInfo.h

764

I would go with something more generic in the name, like insertLoadImmediate.
The fact that DestReg is a physical register or not shouldn’t be a criteria.

769

Shouldn’t we return false for the default implementation.

1186

I have mixed feeling about that method. We already have insert branch and I was wondering if it would make sense to have a insertCmp like method to achieve the same goal.
What other people think?

Assuming we go with that one, I would be more generic in the arguments. Instead of Imm what about a register. If that register happens to be holding an immediate, we should fold it in the optimizer. That being said, right now we do not need the register support so I can live with this specific version.

1187

Return false instead of fatal error?
I guessing you want the error to tell the backend what they need to implement in order to use the pass, but I would rather use the documentation of the pass for that.

1191

Could you be more specific on what you expect the breakpoint instruction to do?

1192

Ditto.

lib/CodeGen/VerifyCalleeSavedRegs.cpp

12

Use doxygen comment.

50

The name of the function is misleading because CSRs depends on ABI and this prototype does not allow to query that information (no function argument). What about gatherMaximalPreservedRegisters.

As a side note, the name of the argument changed from Regs in the declaration to CSRs in the definition.

57

Mark this last remark as a precondition using \pre.

82

The formatting looks strange to me, is this clang-formatted?

93

Add a comment like “Check that this register is used or defined”.
BTW, can’t you use isPhysRegModified?

95

if (!ShouldVerify)

return;

96

Add some comments.
E.g.,
Check if any of its super register is used or defined.
If that is the case, this register is not maximal and we are done.

100

return;

106

I don’t get why we need to do that a second time but with one less check.

175

Period.

193

Document what it would take to implement wider types.
I believe this is just a matter of doing the right thing with the APInt object, right?

263

Nowhere in the documentation we made this commitment.
I wouldn’t rely on it anyway :).

[sanjoy]

• Address review

[sanjoy]

include/llvm/Target/TargetInstrInfo.h

1186

I've extracted out a InsertCompareImm method for now.

1191

I've stated that it is an instruction that raises a SIGTRAP. Is that sufficient?

lib/CodeGen/VerifyCalleeSavedRegs.cpp

12

Doesn't look like other files use doxygen comments for the header? Is that a new convention?

82

Yes it is clang-formatted, but I've changed to code to not make it look odd anymore.

86

I've refactored this function to make the logic more obvious.

193

The real issue here is that the callbacks don't support wider types and e.g. emitting the comparison for AVX registers has to be implemented in TII before we can use wider registers here.

[sanjoy]

ping!

[MatzeB]

I fear that this pass will not be used much and is in danger of bitrotting. I hope you have some internal bots or something that use the code from time to time...

lib/CodeGen/VerifyCalleeSavedRegs.cpp

14

The convention is often broken, but not always. In any way it is helpful and also mentioned in the coding standards.

29

"verify-callee-saved-regs" to match the passname?

100–101

This seems like an unnecessary pessimization of the verifier to me. The thing triggering isPhysRegUsed() may be elsewhere in the function. Why not check the implicit-use/-def operands of the call for physregs that are used for parameter/result passing?

I would also exclude reserved registers just to be sure, even if they are not reported as preserved in any of the existing backends.

129–130

Too much auto for my taste. MachineBasicBlock& / MachineInstr&/ MachineRegisterInfo& etc. are not much longer to write and friendlier to the reader IMO.

140–141

Why are MRI, TRI, TII, Ctx are passed around as arguments to the functions, while these two are class members?

221–224

This could include additional COPYs unrelated to the call. I would at least tighten this a bit to only walk over COPYs with physregs as source.

[sanjoy]

I'm not actively working on this now. Will reopen if that changes.

include/llvm/ADT/APInt.h

public:
   /// @{
 
   /// \brief Truncate to new width.
   ///
   /// Truncate the APInt to a specified width. It is an error to specify a width
   /// that is greater than or equal to the current width.
   APInt LLVM_ATTRIBUTE_UNUSED_RESULT trunc(unsigned width) const;
 
+  /// Truncate to a width.
+  ///
+  /// Truncate the APInt to \p width, or leave it leave it alone if its current
+  /// width is \p width.  It is an error to specify a \p width that is greater
+  /// than its current width.
+  APInt LLVM_ATTRIBUTE_UNUSED_RESULT truncOrSelf(unsigned width) const;
+
   /// \brief Sign extend to a new width.
   ///
   /// This operation sign extends the APInt to a new width. If the high order
   /// bit is set, the fill on the left will be done with 1 bits, otherwise zero.
   /// It is an error to specify a width that is less than or equal to the
   /// current width.
   APInt LLVM_ATTRIBUTE_UNUSED_RESULT sext(unsigned width) const;
 

include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
   extern char &OptimizePHIsID;
 
   /// StackSlotColoring - This pass performs stack slot coloring.
   extern char &StackSlotColoringID;
 
   /// \brief This pass lays out funclets contiguously.
   extern char &FuncletLayoutID;
 
+  /// This pass instruments generated code to verify that call targets honour
+  /// their callee saved registers specification.
+  extern char &VerifyCalleeSavedRegsID;
+
   /// \brief This pass implements the "patchable-function" attribute.
   extern char &PatchableFunctionID;
 
   /// createStackProtectorPass - This pass adds stack protectors to functions.
   ///
   FunctionPass *createStackProtectorPass(const TargetMachine *TM);
 
   /// createMachineVerifierPass - This pass verifies cenerated machine code

include/llvm/InitializePasses.h

 void initializeSjLjEHPreparePass(PassRegistry&);
 void initializeDemandedBitsWrapperPassPass(PassRegistry&);
 void initializeFuncletLayoutPass(PassRegistry &);
 void initializeLoopLoadEliminationPass(PassRegistry&);
 void initializeFunctionImportPassPass(PassRegistry &);
 void initializeLoopVersioningPassPass(PassRegistry &);
 void initializeWholeProgramDevirtPass(PassRegistry &);
 void initializePatchableFunctionPass(PassRegistry &);
+void initializeVerifyCalleeSavedRegsPass(PassRegistry &);
 }
 
 #endif

include/llvm/Target/TargetInstrInfo.h

public:
   /// large registers. See for example the ARM target.
   virtual void copyPhysReg(MachineBasicBlock &MBB,
                            MachineBasicBlock::iterator MI, DebugLoc DL,
                            unsigned DestReg, unsigned SrcReg,
                            bool KillSrc) const {
     llvm_unreachable("Target didn't implement TargetInstrInfo::copyPhysReg!");
   }
 
+  /// Emit instructions to copy the constant \p Imm into \p DestReg (which has
+  /// to be a physical register).  If \p AllowConstantPool is true, use a
+  /// constant pool value if profitable or required.  Return true on success.
+  virtual bool copyImmToPhysReg(MachineBasicBlock &MBB,
+                                MachineBasicBlock::iterator MI, DebugLoc DL,
+                                const TargetRegisterClass *RC, unsigned DestReg,
+                                Constant *Imm,
+                                bool AllowConstantPool = true) const {
+    llvm_unreachable("Target didn't implement TargetInstrInfo::copyPhysReg!");
+  }
+
   /// Store the specified register of the given register class to the specified
   /// stack frame index. The store instruction is to be added to the given
   /// machine basic block before the specified machine instruction. If isKill
   /// is true, the register operand is the last use and must be marked kill.
   virtual void storeRegToStackSlot(MachineBasicBlock &MBB,
                                    MachineBasicBlock::iterator MI,
                                    unsigned SrcReg, bool isKill, int FrameIndex,
                                    const TargetRegisterClass *RC,
public:
   /// then the caller may assume that DefMI has been erased from its parent
   /// block. The caller may assume that it will not be erased by this
   /// function otherwise.
   virtual bool FoldImmediate(MachineInstr *UseMI, MachineInstr *DefMI,
                              unsigned Reg, MachineRegisterInfo *MRI) const {
     return false;
   }
 
+  /// Append code to the end of MBB to branch to \p DestMBB if the value in \p
+  /// Reg is not equal to \p Imm.  Return true on success.
+  virtual bool InsertBranchIfInequal(MachineBasicBlock &MBB, DebugLoc DL,
+                                     const TargetRegisterClass *RC,
+                                     unsigned Reg, Constant *Imm,
+                                     MachineBasicBlock &DestMBB) const {
+    report_fatal_error("Unimplemented");
+  }
+
+  /// Append a breakpoint instruction to the end of \p MBB.
+  virtual void EmitBreakpoint(MachineBasicBlock &MBB, DebugLoc DL) const {
+    report_fatal_error("Unimplemented");
+  }
+
   /// Return the number of u-operations the given machine
   /// instruction will be decoded to on the target cpu. The itinerary's
   /// IssueWidth is the number of microops that can be dispatched each
   /// cycle. An instruction with zero microops takes no dispatch resources.
   virtual unsigned getNumMicroOps(const InstrItineraryData *ItinData,
                                   const MachineInstr *MI) const;
 
   /// Return true for pseudo instructions that don't consume any

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   TargetLoweringBase.cpp
   TargetLoweringObjectFileImpl.cpp
   TargetOptionsImpl.cpp
   TargetPassConfig.cpp
   TargetRegisterInfo.cpp
   TargetSchedule.cpp
   TwoAddressInstructionPass.cpp
   UnreachableBlockElim.cpp
+  VerifyCalleeSavedRegs.cpp
   VirtRegMap.cpp
   WinEHPrepare.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/CodeGen
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/CodeGen/PBQP
 
   LINK_LIBS ${PTHREAD_LIB}
   )
 
 add_dependencies(LLVMCodeGen intrinsics_gen)
 
 add_subdirectory(SelectionDAG)
 add_subdirectory(AsmPrinter)
 add_subdirectory(MIRParser)
 add_subdirectory(GlobalISel)

lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeStackProtectorPass(Registry);
   initializeStackSlotColoringPass(Registry);
   initializeTailDuplicatePassPass(Registry);
   initializeTargetPassConfigPass(Registry);
   initializeTwoAddressInstructionPassPass(Registry);
   initializeUnpackMachineBundlesPass(Registry);
   initializeUnreachableBlockElimPass(Registry);
   initializeUnreachableMachineBlockElimPass(Registry);
+  initializeVerifyCalleeSavedRegsPass(Registry);
   initializeVirtRegMapPass(Registry);
   initializeVirtRegRewriterPass(Registry);
   initializeWinEHPreparePass(Registry);
 }
 
 void LLVMInitializeCodeGen(LLVMPassRegistryRef R) {
   initializeCodeGen(*unwrap(R));
 }

lib/CodeGen/TargetPassConfig.cpp

static cl::opt<bool> VerifyMachineCode("verify-machineinstrs", cl::Hidden,
     cl::init(false),
     cl::ZeroOrMore);
 
 static cl::opt<std::string>
 PrintMachineInstrs("print-machineinstrs", cl::ValueOptional,
                    cl::desc("Print machine instrs"),
                    cl::value_desc("pass-name"), cl::init("option-unspecified"));
 
+static cl::opt<bool> EnableCSRVerification(
+    "verify-callee-saved-registers", cl::Hidden,
+    cl::desc(
+        "Instrument code to check that call targets honour their CSR list"),
+    cl::init(false));
+
 // Temporary option to allow experimenting with MachineScheduler as a post-RA
 // scheduler. Targets can "properly" enable this with
 // substitutePass(&PostRASchedulerID, &PostMachineSchedulerID).
 // Targets can return true in targetSchedulesPostRAScheduling() and
 // insert a PostRA scheduling pass wherever it wants.
 cl::opt<bool> MISchedPostRA("misched-postra", cl::Hidden,
   cl::desc("Run MachineScheduler post regalloc (independent of preRA sched)"));
 
void TargetPassConfig::addMachinePasses() {
   if (getOptLevel() != CodeGenOpt::None) {
     addMachineSSAOptimization();
   } else {
     // If the target requests it, assign local variables to stack slots relative
     // to one another and simplify frame index references where possible.
     addPass(&LocalStackSlotAllocationID, false);
   }
 
+  if (EnableCSRVerification)
+    addPass(&VerifyCalleeSavedRegsID, true);
+
   // Run pre-ra passes.
   addPreRegAlloc();
 
   // Run register allocation and passes that are tightly coupled with it,
   // including phi elimination and scheduling.
   if (getOptimizeRegAlloc())
     addOptimizedRegAlloc(createRegAllocPass(true));
   else

lib/CodeGen/VerifyCalleeSavedRegs.cpp

+//===-- VerifyCalleeSavedRegs.cpp - Instrument code to verify CSR spec ----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass instruments generated code to check that call targets preserve the
+// registers they were supposed to preserve.  This is a best-effort pass, but it
+// does get many interesting cases.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/Sequence.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/Analysis.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/Target/TargetInstrInfo.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "verify-calling-convs"
+
+namespace {
+struct VerifyCalleeSavedRegs : public MachineFunctionPass {
+  static char ID; // Pass identification, replacement for typeid
+  VerifyCalleeSavedRegs() : MachineFunctionPass(ID) {
+    initializeVerifyCalleeSavedRegsPass(*PassRegistry::getPassRegistry());
+  }
+
+  unsigned FrameSetupOp;
+  unsigned FrameDestroyOp;
+
+  bool runOnMachineFunction(MachineFunction &F) override;
+
+  /// Gather all of the callee saved registers specified in \p Regs that are:
+  ///
+  ///   - Maximal (i.e. do not also have a super register specified in \p Regs).
+  ///   - Not used elsewhere in the function.  Since this is running before
+  ///     register allocation, such cases should be rare.
+  void gatherMaximalUnusedCSRs(const TargetRegisterInfo &TRI,
+                               const MachineRegisterInfo &MRI,
+                               MachineOperand &RegMask,
+                               SmallVectorImpl<unsigned> &Regs);
+
+  /// Rewrites all of the physical registers live over the edge from FromMBB to
+  /// ToMBB to use virtual registers instead, since in SSA physical registers
+  /// cannot be live across basic blocks.  This inserts COPY instructions at the
+  /// end of \p FromMBB, so it is expected that \p FromMBB does not yet have a
+  /// terminator.
+  void updatePhysRegUses(MachineRegisterInfo &MRI,
+                         const TargetRegisterInfo &TRI,
+                         const TargetInstrInfo &TII, const DebugLoc &DL,
+                         MachineBasicBlock &FromMBB,
+                         MachineBasicBlock &ToMBB) const;
+
+  /// Instrument the call instruction at \p MI to verify at runtime that the
+  /// callee saved registers specified in \p CSRs are preserved across the call.
+  bool instrumentCall(LLVMContext &, const TargetInstrInfo &,
+                      const TargetRegisterInfo &, MachineRegisterInfo &,
+                      MachineFunction &, MachineInstr *MI,
+                      ArrayRef<unsigned> CSRs) const;
+};
+}
+
+char VerifyCalleeSavedRegs::ID = 0;
+char &llvm::VerifyCalleeSavedRegsID = VerifyCalleeSavedRegs::ID;
+INITIALIZE_PASS(VerifyCalleeSavedRegs, "verify-calling-convs",
+                "Add code to verify callee saved registers", false, false)
+
+static MachineOperand &getRegMask(MachineInstr &MI) {
+  assert(MI.isCall() && "Must be!");
+  auto IsRegMask = [&](const MachineOperand &MO) { return MO.isRegMask(); };
+  assert(std::count_if(MI.operands_begin(), MI.operands_end(), IsRegMask) ==
+             1 &&
+         "Expected exactly one regmask operand!");
+  return *find_if(MI.operands(), IsRegMask);
+}
+
+void VerifyCalleeSavedRegs::gatherMaximalUnusedCSRs(
+    const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI,
+    MachineOperand &RegMask, SmallVectorImpl<unsigned> &CSRs) {
+  for (unsigned Reg : seq(0u, TRI.getNumRegs())) {
+    if (RegMask.clobbersPhysReg(Reg))
+      continue;
+
+    bool ShouldVerify = MRI.use_begin(Reg) == MRI.use_end() &&
+                        MRI.def_begin(Reg) == MRI.def_end();
+    if (ShouldVerify)
+      for (MCSuperRegIterator SR(Reg, &TRI, false); SR.isValid(); ++SR) {
+        if (!RegMask.clobbersPhysReg(*SR) ||
+            MRI.use_begin(*SR) != MRI.use_end() ||
+            MRI.def_begin(*SR) != MRI.def_end()) {
+          ShouldVerify = false;
+          break;
+        }
+      }
+
+    if (ShouldVerify)
+      for (MCSubRegIterator SR(Reg, &TRI, false); SR.isValid(); ++SR) {
+        if (MRI.use_begin(*SR) != MRI.use_end() ||
+            MRI.def_begin(*SR) != MRI.def_end()) {
+          ShouldVerify = false;
+          break;
+        }
+      }
+
+    if (ShouldVerify)
+      CSRs.push_back(Reg);
+  }
+}
+
+bool VerifyCalleeSavedRegs::runOnMachineFunction(MachineFunction &MF) {
+  bool Changed = false;
+  auto &MRI = MF.getRegInfo();
+  auto &TRI = *MRI.getTargetRegisterInfo();
+  auto &TII = *MF.getSubtarget().getInstrInfo();
+  auto &Ctx = MF.getFunction()->getContext();
+
+  SmallVector<MachineInstr *, 16> Calls;
+  std::vector<SmallVector<unsigned, 16>> CSRsAtCall;
+
+  for (auto &BB : MF)
+    for (auto &MI : BB) {
+      if (!MI.isCall())
+        continue;
+
+      Calls.push_back(&MI);
+      CSRsAtCall.emplace_back();
+      gatherMaximalUnusedCSRs(TRI, MRI, getRegMask(MI), CSRsAtCall.back());
+    }
+
+  FrameSetupOp = TII.getCallFrameSetupOpcode();
+  FrameDestroyOp = TII.getCallFrameDestroyOpcode();
+
+  for (unsigned CallIdx : seq(0ul, Calls.size()))
+    Changed |= instrumentCall(Ctx, TII, TRI, MRI, MF, Calls[CallIdx],
+                              CSRsAtCall[CallIdx]);
+
+  return Changed;
+}
+
+bool VerifyCalleeSavedRegs::instrumentCall(
+    LLVMContext &Ctx, const TargetInstrInfo &TII, const TargetRegisterInfo &TRI,
+    MachineRegisterInfo &MRI, MachineFunction &MF, MachineInstr *CallMI,
+    ArrayRef<unsigned> CSRsAtCall) const {
+  const auto &DL = CallMI->getDebugLoc();
+  auto *CallMBB = CallMI->getParent();
+
+  // Compute the locations before and after the call instruction.
+  auto BeforeCallIt = std::next(MachineBasicBlock::iterator(CallMI));
+  auto AfterCallIt = std::next(MachineBasicBlock::iterator(CallMI));
+
+  while (BeforeCallIt != CallMBB->begin() &&
+         BeforeCallIt->getOpcode() != FrameSetupOp)
+    BeforeCallIt--;
+
+  assert(BeforeCallIt->getOpcode() == FrameSetupOp &&
+         "Could not find beginning of call sequence!");
+
+  while (AfterCallIt != CallMBB->end() &&
+         AfterCallIt->getOpcode() != FrameDestroyOp)
+    AfterCallIt++;
+
+  assert(AfterCallIt->getOpcode() == FrameDestroyOp &&
+         "Could not find end of call sequence!");
+  AfterCallIt++;
+
+  // We don't handle invokes yet
+  if (AfterCallIt->isEHLabel())
+    return false;
+
+  struct CSRToCheck {
+    unsigned Reg;
+    const TargetRegisterClass *RC;
+    ConstantInt *Cookie;
+
+    CSRToCheck(unsigned Reg, const TargetRegisterClass *RC, ConstantInt *Cookie)
+        : Reg(Reg), RC(RC), Cookie(Cookie) {}
+  };
+
+  SmallVector<CSRToCheck, 16> CSRsToCheck;
+  for (unsigned PhysReg : CSRsAtCall) {
+    auto *RC = TRI.getMinimalPhysRegClass(PhysReg);
+    unsigned RegSize = RC->getSize();
+    if (RegSize > 8)
+      continue;
+
+    auto *Cookie = ConstantInt::get(
+        Ctx, APInt(64, 0xCA5FCA5FCA5FCA5F).truncOrSelf(RegSize * 8));
+
+    if (!TII.copyImmToPhysReg(*CallMBB, BeforeCallIt, DL, RC, PhysReg, Cookie))
+      continue;
+
+    unsigned VirtReg = MRI.createVirtualRegister(RC);
+    BuildMI(*CallMBB, AfterCallIt, DL, TII.get(TargetOpcode::COPY), VirtReg)
+        .addReg(PhysReg, RegState::Kill);
+
+    CSRsToCheck.emplace_back(VirtReg, RC, Cookie);
+  }
+
+  if (CSRsToCheck.empty())
+    return false;
+
+  auto *ContinueMBB = MF.CreateMachineBasicBlock();
+
+  // AfterCopiesIt points to the location in CallMBB after all the physical
+  // registers have been copied to virtual registers.  This includes the COPY
+  // out of the return value, if any.
+  auto AfterCopiesIt = AfterCallIt;
+  while (AfterCopiesIt != CallMBB->end() &&
+         AfterCopiesIt->getOpcode() == TargetOpcode::COPY)
+    AfterCopiesIt++;
+
+  MF.insert(std::next(MachineFunction::iterator(CallMBB)), ContinueMBB);
+  ContinueMBB->splice(ContinueMBB->begin(), CallMBB, AfterCopiesIt,
+                      CallMBB->end());
+  ContinueMBB->transferSuccessorsAndUpdatePHIs(CallMBB);
+
+  updatePhysRegUses(MRI, TRI, TII, DL, *CallMBB, *ContinueMBB);
+
+  // FailingMBB is the block we branch to to indicate that something went wrong.
+  auto *FailingMBB = MF.CreateMachineBasicBlock();
+  MF.insert(MF.end(), FailingMBB);
+  TII.EmitBreakpoint(*FailingMBB, DL);
+
+  MachineBasicBlock *CheckMBB = CallMBB;
+
+  for (auto &RegToCheck : CSRsToCheck) {
+    unsigned Reg = RegToCheck.Reg;
+    ConstantInt *Cookie = RegToCheck.Cookie;
+    const TargetRegisterClass *RC = RegToCheck.RC;
+
+    // The control flow we want is:
+    //
+    //   CALL
+    //   CMP64rm %csr0, <cp#0>
+    //   JNE <fail>
+    //   JMP <check_next_0>
+    //
+    // check_next_0:
+    //   CMP64rm %csr1, <cp#0>
+    //   JNE <fail>
+    //   JMP <check_next_1>
+    //
+    // check_next_1:
+    //   ...
+    // ...
+    //
+    // check_next_<last>:
+    //   br <continue_mbb>
+
+    bool BranchEmitted =
+        TII.InsertBranchIfInequal(*CheckMBB, DL, RC, Reg, Cookie, *FailingMBB);
+    (void)BranchEmitted;
+    assert(BranchEmitted && "Expected InsertBranchIfInequal to be successful "
+                            "(since copyImmToPhysReg was fine)!");
+
+    auto *NextCheckMBB = MF.CreateMachineBasicBlock();
+
+    MF.insert(std::next(MachineFunction::iterator(CheckMBB)), NextCheckMBB);
+    TII.InsertBranch(*CheckMBB, NextCheckMBB, nullptr, None, DL);
+
+    CheckMBB->addSuccessor(NextCheckMBB);
+    CheckMBB->addSuccessor(FailingMBB);
+
+    CheckMBB = NextCheckMBB;
+  }
+
+  TII.InsertBranch(*CheckMBB, ContinueMBB, nullptr, None, DL);
+  CheckMBB->addSuccessor(ContinueMBB);
+
+  return true;
+}
+
+void VerifyCalleeSavedRegs::updatePhysRegUses(MachineRegisterInfo &MRI,
+                                              const TargetRegisterInfo &TRI,
+                                              const TargetInstrInfo &TII,
+                                              const DebugLoc &DL,
+                                              MachineBasicBlock &FromMBB,
+                                              MachineBasicBlock &ToMBB) const {
+  DenseMap<unsigned, unsigned> ExportedPhysRegs;
+  SmallSet<unsigned, 32> PhysRegDefs;
+
+  for (auto &MI : ToMBB) {
+    // Look at every physical register use in ToMBB, and rewrite them to use a
+    // virtual register exported from FromMBB.
+    for (auto &MO : MI.operands()) {
+      if (!MO.isReg() || !TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
+        continue;
+
+      if (MO.isDef()) {
+        PhysRegDefs.insert(MO.getReg());
+        continue;
+      }
+
+      if (PhysRegDefs.count(MO.getReg()))
+        continue;
+
+      auto Itr = ExportedPhysRegs.find(MO.getReg());
+      if (Itr == ExportedPhysRegs.end()) {
+        // Add copies only if we've not already copies out the physical
+        // register.
+        unsigned VirtReg =
+            MRI.createVirtualRegister(TRI.getMinimalPhysRegClass(MO.getReg()));
+        BuildMI(FromMBB, FromMBB.end(), DL, TII.get(TargetOpcode::COPY),
+                VirtReg).addReg(MO.getReg(), RegState::Kill);
+        Itr = ExportedPhysRegs.insert({MO.getReg(), VirtReg}).first;
+      }
+
+      // Change to use a virtual register.
+      MO.setReg(Itr->second);
+    }
+  }
+}

lib/Support/APInt.cpp

APInt APInt::trunc(unsigned width) const {
   // Truncate and copy any partial word.
   unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
   if (bits != 0)
     Result.pVal[i] = pVal[i] << bits >> bits;
 
   return Result;
 }
 
+APInt APInt::truncOrSelf(unsigned width) const {
+  assert(width <= BitWidth && "Invalid APInt Truncate request");
+  assert(width && "Can't truncate to 0 bits");
+
+  return width == BitWidth ? *this : trunc(width);
+}
+
 // Sign extend to a new width.
 APInt APInt::sext(unsigned width) const {
   assert(width > BitWidth && "Invalid APInt SignExtend request");
 
   if (width <= APINT_BITS_PER_WORD) {
     uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
     val = (int64_t)val >> (width - BitWidth);
     return APInt(width, val >> (APINT_BITS_PER_WORD - width));

lib/Target/X86/X86InstrInfo.h

public:
   /// defined by the load we are trying to fold. DefMI returns the machine
   /// instruction that defines FoldAsLoadDefReg, and the function returns
   /// the machine instruction generated due to folding.
   MachineInstr* optimizeLoadInstr(MachineInstr *MI,
                                   const MachineRegisterInfo *MRI,
                                   unsigned &FoldAsLoadDefReg,
                                   MachineInstr *&DefMI) const override;
 
+  bool InsertBranchIfInequal(MachineBasicBlock &MBB, DebugLoc DL,
+                             const TargetRegisterClass *RC, unsigned Reg,
+                             Constant *Imm,
+                             MachineBasicBlock &DestBB) const override;
+
+  void EmitBreakpoint(MachineBasicBlock &MBB, DebugLoc DL) const override;
+
+  bool copyImmToPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
+                        DebugLoc DL, const TargetRegisterClass *RC,
+                        unsigned DestReg, Constant *Imm,
+                        bool AllowConstantPool) const override;
+
   std::pair<unsigned, unsigned>
   decomposeMachineOperandsTargetFlags(unsigned TF) const override;
 
   ArrayRef<std::pair<unsigned, const char *>>
   getSerializableDirectMachineOperandTargetFlags() const override;
 
 protected:
   /// Commutes the operands in the given instruction by changing the operands

lib/Target/X86/X86InstrInfo.cpp

while (I != MBB.begin()) {
     I->eraseFromParent();
     I = MBB.end();
     ++Count;
   }
 
   return Count;
 }
 
+void X86InstrInfo::EmitBreakpoint(MachineBasicBlock &MBB, DebugLoc DL) const {
+  BuildMI(MBB, MBB.end(), DL, get(X86::INT3));
+}
+
 unsigned
 X86InstrInfo::InsertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
                            MachineBasicBlock *FBB, ArrayRef<MachineOperand> Cond,
                            DebugLoc DL) const {
   // Shouldn't be a fall through.
   assert(TBB && "InsertBranch must not be told to insert a fallthrough");
   assert((Cond.size() == 1 || Cond.size() == 0) &&
          "X86 branch conditions have one component!");
if ((FromEFLAGS || ToEFLAGS) && (is32 || is64)) {
     return;
   }
 
   DEBUG(dbgs() << "Cannot copy " << RI.getName(SrcReg)
                << " to " << RI.getName(DestReg) << '\n');
   llvm_unreachable("Cannot emit physreg copy instruction");
 }
 
+static unsigned getLoadStoreRegOpcode(unsigned Reg,
+                                      const TargetRegisterClass *RC,
+                                      bool isStackAligned,
+                                      const X86Subtarget &STI, bool load);
+
 static unsigned getLoadStoreMaskRegOpcode(const TargetRegisterClass *RC,
                                           bool load) {
   switch (RC->getSize()) {
   default:
     llvm_unreachable("Unknown spill size");
   case 2:
     return load ? X86::KMOVWkm : X86::KMOVWmk;
   case 4:

 
 static unsigned getLoadRegOpcode(unsigned DestReg,
                                  const TargetRegisterClass *RC,
                                  bool isStackAligned,
                                  const X86Subtarget &STI) {
   return getLoadStoreRegOpcode(DestReg, RC, isStackAligned, STI, true);
 }
 
+bool X86InstrInfo::copyImmToPhysReg(MachineBasicBlock &MBB,
+                                    MachineBasicBlock::iterator MI, DebugLoc DL,
+                                    const TargetRegisterClass *RC,
+                                    unsigned DestReg, Constant *Imm,
+                                    bool AllowConstantPool) const {
+  unsigned Opcode;
+  if (X86::GR8RegClass.contains(DestReg))
+    Opcode = X86::MOV8ri;
+  else if (X86::GR16RegClass.contains(DestReg))
+    Opcode = X86::MOV16ri;
+  else if (X86::GR32RegClass.contains(DestReg))
+    Opcode = X86::MOV32ri;
+  else if (X86::GR64RegClass.contains(DestReg)) {
+    MachineFunction &MF = *MBB.getParent();
+    if (!AllowConstantPool ||
+        MF.getTarget().getRelocationModel() == Reloc::PIC_)
+      Opcode = X86::MOV64ri;
+    else {
+      MachineConstantPool &MCP = *MF.getConstantPool();
+      unsigned CPI = MCP.getConstantPoolIndex(Imm, RC->getSize());
+      BuildMI(MBB, MI, DL, get(X86::MOV64rm), DestReg)
+          .addReg(0)
+          .addImm(1)
+          .addReg(0)
+          .addConstantPoolIndex(CPI)
+          .addReg(0);
+      return true;
+    }
+  } else
+    return false;
+
+  BuildMI(MBB, MI, DL, get(Opcode), DestReg)
+      .addImm(cast<ConstantInt>(Imm)->getZExtValue());
+  return true;
+}
+
+bool X86InstrInfo::InsertBranchIfInequal(MachineBasicBlock &MBB, DebugLoc DL,
+                                         const TargetRegisterClass *RC,
+                                         unsigned Reg, Constant *Imm,
+                                         MachineBasicBlock &DestMBB) const {
+  unsigned CmpOpcode;
+  if (X86::GR8RegClass.hasSubClassEq(RC))
+    CmpOpcode = X86::MOV8ri;
+  else if (X86::GR16RegClass.hasSubClassEq(RC))
+    CmpOpcode = X86::MOV16ri;
+  else if (X86::GR32RegClass.hasSubClassEq(RC))
+    CmpOpcode = X86::MOV32ri;
+  else if (X86::GR64RegClass.hasSubClassEq(RC)) {
+    MachineFunction &MF = *MBB.getParent();
+    if (MF.getTarget().getRelocationModel() == Reloc::PIC_)
+      return false;
+
+    CmpOpcode = 0;
+    MachineConstantPool &MCP = *MF.getConstantPool();
+    unsigned CPI = MCP.getConstantPoolIndex(Imm, RC->getSize());
+    BuildMI(MBB, MBB.end(), DL, get(X86::CMP64rm))
+        .addReg(Reg)
+        .addReg(0)
+        .addImm(1)
+        .addReg(0)
+        .addConstantPoolIndex(CPI)
+        .addReg(0);
+  } else
+    return false;
+
+  if (CmpOpcode)
+    BuildMI(MBB, MBB.end(), DL, get(CmpOpcode)).addReg(Reg).addImm(
+        cast<ConstantInt>(Imm)->getZExtValue());
+  BuildMI(MBB, MBB.end(), DL, get(X86::JNE_1)).addMBB(&DestMBB);
+  return true;
+}
+
 void X86InstrInfo::storeRegToStackSlot(MachineBasicBlock &MBB,
                                        MachineBasicBlock::iterator MI,
                                        unsigned SrcReg, bool isKill, int FrameIdx,
                                        const TargetRegisterClass *RC,
                                        const TargetRegisterInfo *TRI) const {
   const MachineFunction &MF = *MBB.getParent();
   assert(MF.getFrameInfo()->getObjectSize(FrameIdx) >= RC->getSize() &&
          "Stack slot too small for store");

test/CodeGen/X86/verify-csrs.ll

+; RUN: llc -O3 -verify-machineinstrs -verify-callee-saved-registers < %s | FileCheck %s
+
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @foo()
+declare double @foo_dbl()
+declare i32 @bar(i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32)
+
+define void @f_0(i32* %ptr) {
+; CHECK-LABEL: f_0:
+; CHECK:  movl  $10, (%rdi)
+; CHECK:  movq  .LCPI0_0, %rbp
+; CHECK:  movq  .LCPI0_0, %rbx
+; CHECK:  movq  .LCPI0_0, %r12
+; CHECK:  movq  .LCPI0_0, %r13
+; CHECK:  movq  .LCPI0_0, %r14
+; CHECK:  movq  .LCPI0_0, %r15
+; CHECK:  callq foo
+; CHECK:  cmpq  .LCPI0_0, %rbp
+; CHECK:  jne [[BREAK_LBL_F_0:.LBB[0-9_]+]]
+; CHECK:  cmpq  .LCPI0_0, %rbx
+; CHECK:  jne [[BREAK_LBL_F_0]]
+; CHECK:  cmpq  .LCPI0_0, %r12
+; CHECK:  jne [[BREAK_LBL_F_0]]
+; CHECK:  cmpq  .LCPI0_0, %r13
+; CHECK:  jne [[BREAK_LBL_F_0]]
+; CHECK:  cmpq  .LCPI0_0, %r14
+; CHECK:  jne [[BREAK_LBL_F_0]]
+; CHECK:  cmpq  .LCPI0_0, %r15
+; CHECK:  jne [[BREAK_LBL_F_0]]
+; CHECK:  movl  $20, (%rax)
+; CHECK:  retq
+; CHECK: [[BREAK_LBL_F_0]]:
+; CHECK:  int3
+
+entry:
+  store i32 10, i32* %ptr
+  call void @foo()
+  store i32 20, i32* %ptr
+  ret void
+}
+
+define void @f_1(i32* %ptr) personality i8 3 {
+; Invokes are not supported yet
+
+; CHECK-LABEL: f_1:
+; CHECK-NOT: .LCPI
+; CHECK: .cfi_endproc
+entry:
+  store i32 10, i32* %ptr
+  invoke void @foo() to label %ok unwind label %not_ok
+
+ok:
+  store i32 20, i32* %ptr
+  ret void
+
+not_ok:
+  %e = landingpad { i8*, i32 } cleanup
+  store i32 30, i32* %ptr
+  ret void
+}
+
+define void @f_2(i32* %ptr) {
+; CHECK-LABEL: f_2:
+; CHECK:  movl  $10, (%rdi)
+; CHECK:  movq  .LCPI2_0, %rbp
+; CHECK:  movq  .LCPI2_0, %rbx
+; CHECK:  movq  .LCPI2_0, %r12
+; CHECK:  movq  .LCPI2_0, %r13
+; CHECK:  movq  .LCPI2_0, %r14
+; CHECK:  movq  .LCPI2_0, %r15
+; CHECK:  movl  $100, %edi
+; CHECK:  movl  $200, %esi
+; CHECK:  movl  $300, %edx              # imm = 0x12C
+; CHECK:  movl  $400, %ecx              # imm = 0x190
+; CHECK:  movl  $500, %r8d              # imm = 0x1F4
+; CHECK:  movl  $600, %r9d              # imm = 0x258
+; CHECK:  pushq $1200                   # imm = 0x4B0
+; CHECK:  pushq $1100                   # imm = 0x44C
+; CHECK:  pushq $1000                   # imm = 0x3E8
+; CHECK:  pushq $900                    # imm = 0x384
+; CHECK:  pushq $800                    # imm = 0x320
+; CHECK:  pushq $700                    # imm = 0x2BC
+; CHECK:  callq bar
+; CHECK:  addq  $48, %rsp
+; CHECK:  cmpq  .LCPI2_0, %rbp
+; CHECK:  jne [[BREAK_LBL_F_2:.LBB[0-9_]+]]
+; CHECK:  cmpq  .LCPI2_0, %rbx
+; CHECK:  jne [[BREAK_LBL_F_2]]
+; CHECK:  cmpq  .LCPI2_0, %r12
+; CHECK:  jne [[BREAK_LBL_F_2]]
+; CHECK:  cmpq  .LCPI2_0, %r13
+; CHECK:  jne [[BREAK_LBL_F_2]]
+; CHECK:  cmpq  .LCPI2_0, %r14
+; CHECK:  jne [[BREAK_LBL_F_2]]
+; CHECK:  cmpq  .LCPI2_0, %r15
+; CHECK:  jne [[BREAK_LBL_F_2]]
+; CHECK:  movl  %eax, (%rcx)
+; CHECK: [[BREAK_LBL_F_2]]:
+; CHECK:  int3
+
+entry:
+  store i32 10, i32* %ptr
+  %val = call i32 @bar(i32 100, i32 200, i32 300, i32 400, i32 500, i32 600, i32 700, i32 800, i32 900, i32 1000, i32 1100, i32 1200)
+  store i32 %val, i32* %ptr
+  ret void
+}
+
+define double @f_3(i32 %cond) {
+; CHECK-LABEL: f_3:
+; CHECK:  movq  .LCPI3_0, %rbp
+; CHECK:  movq  .LCPI3_0, %rbx
+; CHECK:  movq  .LCPI3_0, %r12
+; CHECK:  movq  .LCPI3_0, %r13
+; CHECK:  movq  .LCPI3_0, %r14
+; CHECK:  movq  .LCPI3_0, %r15
+; CHECK:  callq foo_dbl
+; CHECK:  cmpq  .LCPI3_0, %rbp
+; CHECK:  jne [[BREAK_LBL_F_3:.LBB[0-9_]+]]
+; CHECK:  cmpq  .LCPI3_0, %rbx
+; CHECK:  jne [[BREAK_LBL_F_3]]
+; CHECK:  cmpq  .LCPI3_0, %r12
+; CHECK:  jne [[BREAK_LBL_F_3]]
+; CHECK:  cmpq  .LCPI3_0, %r13
+; CHECK:  jne [[BREAK_LBL_F_3]]
+; CHECK:  cmpq  .LCPI3_0, %r14
+; CHECK:  jne [[BREAK_LBL_F_3]]
+; CHECK:  cmpq  .LCPI3_0, %r15
+; CHECK:  jne [[BREAK_LBL_F_3]]
+; CHECK:  retq
+; CHECK: [[BREAK_LBL_F_3]]:
+; CHECK:  int3
+
+entry:
+  %rval = call double @foo_dbl()
+  ret double %rval
+}
+
+
+define void @f_4(i32 %cond, i32* %ptr) {
+; FileCheck for only one CSR to avoid verbosity.
+
+; CHECK-LABEL: f_4:
+; CHECK:  movq  .LCPI4_0, %r15
+; CHECK:  callq foo
+; CHECK:  cmpq  .LCPI4_0, %rbp
+; CHECK:  jne [[BREAK_LBL_F_4:.LBB[0-9_]+]]
+; CHECK:  movq  .LCPI4_0, %r15
+; CHECK:  callq foo
+; CHECK:  cmpq  .LCPI4_0, %rbp
+; CHECK:  jne [[BREAK_LBL_F_4]]
+
+entry:
+  %cmp = icmp eq i32 %cond, 0
+  br i1 %cmp, label %leave, label %stay
+
+leave:
+  store i32 10, i32* %ptr
+  call void @foo()
+  call void @foo()
+  unreachable
+
+stay:
+  ret void
+}