Add the ShadowCallStack pass

[vlad.tsyrklevich]

Summary

The ShadowCallStack pass instruments functions marked with the
shadowcallstack attribute. The instrumented prolog saves the return
address to [gs:offset] where offset is stored and updated in [gs:0].
The instrumented epilog loads/updates the return address from [gs:0]
and checks that it matches the return address on the stack before
returning.

[vlad.tsyrklevich]

@craig.topper Just wanted to give you a heads up about this change as it's landing a pass in the X86 backend. The pass is specific to functions compiled with -fsanitize=shadow-call-stack so it shouldn't affect most users.

[eugenis]

lib/Target/X86/ShadowCallStack.cpp

95 ↗

(On Diff #139495)

AFAIK you can do it without a dummy instruction by using the iterator form of BuildMI and passing MBB->end() or MBB->begin() in case of the empty basic block.

[pcc]

lib/Target/X86/ShadowCallStack.cpp

89 ↗

(On Diff #139495)

I think this is possible if the function takes a nest parameter -- probably best to disable the protection in that case for now.

[vlad.tsyrklevich]

• Skip functions with r10/r11 live-in instead of assert()ing

[kcc]

+Vitaly for another set of eyes.

[vlad.tsyrklevich]

First-pass leaf function optimization

[vlad.tsyrklevich]

lib/Target/X86/ShadowCallStack.cpp

89 ↗

(On Diff #139495)

Yup, I double checked and that looks like the case in X86FrameLowering.

95 ↗

(On Diff #139495)

You could use the MBB->begin() form and insert them backwards, but for the sake of readability I insert them forwards.

[vitalybuka]

lib/Target/X86/ShadowCallStack.cpp

64 ↗

(On Diff #140109)

Do you need this functions like members.
probably static non member should work as well

90 ↗

(On Diff #140109)

Why is there inconsistency reference vs pointer?

287 ↗

(On Diff #140109)

LeafFuncOptimization looks redundunt: LeafFuncOptimization == ( LeafFuncRegister != X86::NoRegister)

293 ↗

(On Diff #140109)

for (auto &MBB : Fn)
  MBB.addLiveIn(LeafFuncRegister);

324 ↗

(On Diff #140109)

can getFallThrough return null?

[vlad.tsyrklevich]

• Address Vitaly's comments
• Only add live-ins when a register was found
• Add a short leaf function test case

lib/Target/X86/ShadowCallStack.cpp

293 ↗

(On Diff #140109)

The original loop actually skips the first basic bock: ++Fn.begin(), I'll add a comment to make that clearer.

324 ↗

(On Diff #140109)

I don't think so, the check at 241 demonstrates there is at least one instruction in this function so if the first MBB is empty then there has to be another MBB following it.

[pcc]

lib/Target/X86/ShadowCallStack.cpp

95 ↗

(On Diff #139495)

I would imagine that you could save the result of MBB->begin() and use that to insert instructions forwards, as it should always refer to what used to be the first instruction. Does that not work?

[vlad.tsyrklevich]

lib/Target/X86/ShadowCallStack.cpp

95 ↗

(On Diff #139495)

Sorry, let me be more clear. BuildMI() has two forms: one to add to the end of an MBB and one to add before a given instruction in the MBB. That means that for an empty MBB we can't insert instructions in forwards order without inserting a fake instruction to insert behind or using two different forms to insert the same instructions (one inserting behind the first instruction and the other always using the add-to-the-end form.)

[pcc]

lib/Target/X86/ShadowCallStack.cpp

95 ↗

(On Diff #139495)

But there is another form that takes an iterator.

http://llvm-cs.pcc.me.uk/include/llvm/CodeGen/MachineInstrBuilder.h#313

Can you pass the iterator that you previously got from MBB->begin() to it?

[vlad.tsyrklevich]

lib/Target/X86/ShadowCallStack.cpp

95 ↗

(On Diff #139495)

Huh, I didn't think this form would work because the iterator would be invalidated between MBB insertions but it looks like that's not the case for ilists so this form does work.

[vlad.tsyrklevich]

• Simplify addProlog

[pcc]

LGTM

lib/Target/X86/ShadowCallStack.cpp

94 ↗

(On Diff #140341)

Nit: I'd call this MBBI because it might not actually point to a MachineInstr.

121 ↗

(On Diff #140341)

Looks like this can be simplified to addDirectMem(BuildMI(&MBB, MBB.begin(), ...

[vlad.tsyrklevich]

• Address Peter's comments

llvm/trunk/lib/Target/X86/CMakeLists.txt

 
 if (X86_GEN_FOLD_TABLES)
   tablegen(LLVM X86GenFoldTables.inc -gen-x86-fold-tables)
 endif()
 
 add_public_tablegen_target(X86CommonTableGen)
 
 set(sources
+  ShadowCallStack.cpp
   X86AsmPrinter.cpp
   X86CallFrameOptimization.cpp
   X86CallingConv.cpp
   X86CallLowering.cpp
   X86CmovConversion.cpp
   X86DomainReassignment.cpp
   X86ExpandPseudo.cpp
   X86FastISel.cpp

llvm/trunk/lib/Target/X86/ShadowCallStack.cpp

+//===------- ShadowCallStack.cpp - Shadow Call Stack pass -----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The ShadowCallStack pass instruments function prologs/epilogs to check that
+// the return address has not been corrupted during the execution of the
+// function. The return address is stored in a 'shadow call stack' addressed
+// using the %gs segment register.
+//
+//===----------------------------------------------------------------------===//
+
+#include "X86.h"
+#include "X86InstrBuilder.h"
+#include "X86InstrInfo.h"
+#include "X86Subtarget.h"
+
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetInstrInfo.h"
+
+using namespace llvm;
+
+namespace llvm {
+void initializeShadowCallStackPass(PassRegistry &);
+}
+
+namespace {
+
+class ShadowCallStack : public MachineFunctionPass {
+public:
+  static char ID;
+
+  ShadowCallStack() : MachineFunctionPass(ID) {
+    initializeShadowCallStackPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
+  bool runOnMachineFunction(MachineFunction &Fn) override;
+
+private:
+  // Do not instrument leaf functions with this many or fewer instructions. The
+  // shadow call stack instrumented prolog/epilog are slightly race-y reading
+  // and checking the saved return address, so it is better to not instrument
+  // functions that have fewer instructions than the instrumented prolog/epilog
+  // race.
+  static const size_t SkipLeafInstructions = 3;
+};
+
+char ShadowCallStack::ID = 0;
+} // end anonymous namespace.
+
+static void addProlog(MachineFunction &Fn, const TargetInstrInfo *TII,
+                      MachineBasicBlock &MBB, const DebugLoc &DL);
+static void addPrologLeaf(MachineFunction &Fn, const TargetInstrInfo *TII,
+                          MachineBasicBlock &MBB, const DebugLoc &DL,
+                          MCPhysReg FreeRegister);
+
+static void addEpilog(const TargetInstrInfo *TII, MachineBasicBlock &MBB,
+                      MachineInstr &MI, MachineBasicBlock &TrapBB);
+static void addEpilogLeaf(const TargetInstrInfo *TII, MachineBasicBlock &MBB,
+                          MachineInstr &MI, MachineBasicBlock &TrapBB,
+                          MCPhysReg FreeRegister);
+// Generate a longer epilog that only uses r10 when a tailcall branches to r11.
+static void addEpilogOnlyR10(const TargetInstrInfo *TII, MachineBasicBlock &MBB,
+                             MachineInstr &MI, MachineBasicBlock &TrapBB);
+
+// Helper function to add ModR/M references for [Seg: Reg + Offset] memory
+// accesses
+static inline const MachineInstrBuilder &
+addSegmentedMem(const MachineInstrBuilder &MIB, MCPhysReg Seg, MCPhysReg Reg,
+                int Offset = 0) {
+  return MIB.addReg(Reg).addImm(1).addReg(0).addImm(Offset).addReg(Seg);
+}
+
+static void addProlog(MachineFunction &Fn, const TargetInstrInfo *TII,
+                      MachineBasicBlock &MBB, const DebugLoc &DL) {
+  const MCPhysReg ReturnReg = X86::R10;
+  const MCPhysReg OffsetReg = X86::R11;
+
+  auto MBBI = MBB.begin();
+  // mov r10, [rsp]
+  addDirectMem(BuildMI(MBB, MBBI, DL, TII->get(X86::MOV64rm)).addDef(ReturnReg),
+               X86::RSP);
+  // xor r11, r11
+  BuildMI(MBB, MBBI, DL, TII->get(X86::XOR64rr))
+      .addDef(OffsetReg)
+      .addReg(OffsetReg, RegState::Undef)
+      .addReg(OffsetReg, RegState::Undef);
+  // add QWORD [gs:r11], 8
+  addSegmentedMem(BuildMI(MBB, MBBI, DL, TII->get(X86::ADD64mi8)), X86::GS,
+                  OffsetReg)
+      .addImm(8);
+  // mov r11, [gs:r11]
+  addSegmentedMem(
+      BuildMI(MBB, MBBI, DL, TII->get(X86::MOV64rm)).addDef(OffsetReg), X86::GS,
+      OffsetReg);
+  // mov [gs:r11], r10
+  addSegmentedMem(BuildMI(MBB, MBBI, DL, TII->get(X86::MOV64mr)), X86::GS,
+                  OffsetReg)
+      .addReg(ReturnReg);
+}
+
+static void addPrologLeaf(MachineFunction &Fn, const TargetInstrInfo *TII,
+                          MachineBasicBlock &MBB, const DebugLoc &DL,
+                          MCPhysReg FreeRegister) {
+  // mov REG, [rsp]
+  addDirectMem(BuildMI(MBB, MBB.begin(), DL, TII->get(X86::MOV64rm))
+                   .addDef(FreeRegister),
+               X86::RSP);
+}
+
+static void addEpilog(const TargetInstrInfo *TII, MachineBasicBlock &MBB,
+                      MachineInstr &MI, MachineBasicBlock &TrapBB) {
+  const DebugLoc &DL = MI.getDebugLoc();
+
+  // xor r11, r11
+  BuildMI(MBB, MI, DL, TII->get(X86::XOR64rr))
+      .addDef(X86::R11)
+      .addReg(X86::R11, RegState::Undef)
+      .addReg(X86::R11, RegState::Undef);
+  // mov r10, [gs:r11]
+  addSegmentedMem(BuildMI(MBB, MI, DL, TII->get(X86::MOV64rm)).addDef(X86::R10),
+                  X86::GS, X86::R11);
+  // mov r10, [gs:r10]
+  addSegmentedMem(BuildMI(MBB, MI, DL, TII->get(X86::MOV64rm)).addDef(X86::R10),
+                  X86::GS, X86::R10);
+  // sub QWORD [gs:r11], 8
+  // This instruction should not be moved up to avoid a signal race.
+  addSegmentedMem(BuildMI(MBB, MI, DL, TII->get(X86::SUB64mi8)),
+                  X86::GS, X86::R11)
+      .addImm(8);
+  // cmp [rsp], r10
+  addDirectMem(BuildMI(MBB, MI, DL, TII->get(X86::CMP64mr)), X86::RSP)
+      .addReg(X86::R10);
+  // jne trap
+  BuildMI(MBB, MI, DL, TII->get(X86::JNE_1)).addMBB(&TrapBB);
+  MBB.addSuccessor(&TrapBB);
+}
+
+static void addEpilogLeaf(const TargetInstrInfo *TII, MachineBasicBlock &MBB,
+                          MachineInstr &MI, MachineBasicBlock &TrapBB,
+                          MCPhysReg FreeRegister) {
+  const DebugLoc &DL = MI.getDebugLoc();
+
+  // cmp [rsp], REG
+  addDirectMem(BuildMI(MBB, MI, DL, TII->get(X86::CMP64mr)), X86::RSP)
+      .addReg(FreeRegister);
+  // jne trap
+  BuildMI(MBB, MI, DL, TII->get(X86::JNE_1)).addMBB(&TrapBB);
+  MBB.addSuccessor(&TrapBB);
+}
+
+static void addEpilogOnlyR10(const TargetInstrInfo *TII, MachineBasicBlock &MBB,
+                             MachineInstr &MI, MachineBasicBlock &TrapBB) {
+  const DebugLoc &DL = MI.getDebugLoc();
+
+  // xor r10, r10
+  BuildMI(MBB, MI, DL, TII->get(X86::XOR64rr))
+      .addDef(X86::R10)
+      .addReg(X86::R10, RegState::Undef)
+      .addReg(X86::R10, RegState::Undef);
+  // mov r10, [gs:r10]
+  addSegmentedMem(BuildMI(MBB, MI, DL, TII->get(X86::MOV64rm)).addDef(X86::R10),
+                  X86::GS, X86::R10);
+  // mov r10, [gs:r10]
+  addSegmentedMem(BuildMI(MBB, MI, DL, TII->get(X86::MOV64rm)).addDef(X86::R10),
+                  X86::GS, X86::R10);
+  // sub QWORD [gs:0], 8
+  // This instruction should not be moved up to avoid a signal race.
+  addSegmentedMem(BuildMI(MBB, MI, DL, TII->get(X86::SUB64mi8)), X86::GS, 0)
+      .addImm(8);
+  // cmp [rsp], r10
+  addDirectMem(BuildMI(MBB, MI, DL, TII->get(X86::CMP64mr)), X86::RSP)
+      .addReg(X86::R10);
+  // jne trap
+  BuildMI(MBB, MI, DL, TII->get(X86::JNE_1)).addMBB(&TrapBB);
+  MBB.addSuccessor(&TrapBB);
+}
+
+bool ShadowCallStack::runOnMachineFunction(MachineFunction &Fn) {
+  if (!Fn.getFunction().hasFnAttribute(Attribute::ShadowCallStack) ||
+      Fn.getFunction().hasFnAttribute(Attribute::Naked))
+    return false;
+
+  if (Fn.empty() || !Fn.getRegInfo().tracksLiveness())
+    return false;
+
+  // FIXME: Skip functions that have r10 or r11 live on entry (r10 can be live
+  // on entry for parameters with the nest attribute.)
+  if (Fn.front().isLiveIn(X86::R10) || Fn.front().isLiveIn(X86::R11))
+    return false;
+
+  // FIXME: Skip functions with conditional and r10 tail calls for now.
+  bool HasReturn = false;
+  for (auto &MBB : Fn) {
+    if (MBB.empty())
+      continue;
+
+    const MachineInstr &MI = MBB.instr_back();
+    if (MI.isReturn())
+      HasReturn = true;
+
+    if (MI.isReturn() && MI.isCall()) {
+      if (MI.findRegisterUseOperand(X86::EFLAGS))
+        return false;
+      // This should only be possible on Windows 64 (see GR64_TC versus
+      // GR64_TCW64.)
+      if (MI.findRegisterUseOperand(X86::R10) ||
+          MI.hasRegisterImplicitUseOperand(X86::R10))
+        return false;
+    }
+  }
+
+  if (!HasReturn)
+    return false;
+
+  // For leaf functions:
+  // 1. Do not instrument very short functions where it would not improve that
+  //    function's security.
+  // 2. Detect if there is an unused caller-saved register we can reserve to
+  //    hold the return address instead of writing/reading it from the shadow
+  //    call stack.
+  MCPhysReg LeafFuncRegister = X86::NoRegister;
+  if (!Fn.getFrameInfo().adjustsStack()) {
+    size_t InstructionCount = 0;
+    std::bitset<X86::NUM_TARGET_REGS> UsedRegs;
+    for (auto &MBB : Fn) {
+      for (auto &LiveIn : MBB.liveins())
+        UsedRegs.set(LiveIn.PhysReg);
+      for (auto &MI : MBB) {
+        InstructionCount++;
+        for (auto &Op : MI.operands())
+          if (Op.isReg() && Op.isDef())
+            UsedRegs.set(Op.getReg());
+      }
+    }
+
+    if (InstructionCount <= SkipLeafInstructions)
+      return false;
+
+    std::bitset<X86::NUM_TARGET_REGS> CalleeSavedRegs;
+    const MCPhysReg *CSRegs = Fn.getRegInfo().getCalleeSavedRegs();
+    for (size_t i = 0; CSRegs[i]; i++)
+      CalleeSavedRegs.set(CSRegs[i]);
+
+    const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo();
+    for (auto &Reg : X86::GR64_NOSPRegClass.getRegisters()) {
+      // FIXME: Optimization opportunity: spill/restore a callee-saved register
+      // if a caller-saved register is unavailable.
+      if (CalleeSavedRegs.test(Reg))
+        continue;
+
+      bool Used = false;
+      for (MCSubRegIterator SR(Reg, TRI, true); SR.isValid(); ++SR)
+        if ((Used = UsedRegs.test(*SR)))
+          break;
+
+      if (!Used) {
+        LeafFuncRegister = Reg;
+        break;
+      }
+    }
+  }
+
+  const bool LeafFuncOptimization = LeafFuncRegister != X86::NoRegister;
+  if (LeafFuncOptimization)
+    // Mark the leaf function register live-in for all MBBs except the entry MBB
+    for (auto I = ++Fn.begin(), E = Fn.end(); I != E; ++I)
+      I->addLiveIn(LeafFuncRegister);
+
+  MachineBasicBlock &MBB = Fn.front();
+  const MachineBasicBlock *NonEmpty = MBB.empty() ? MBB.getFallThrough() : &MBB;
+  const DebugLoc &DL = NonEmpty->front().getDebugLoc();
+
+  const TargetInstrInfo *TII = Fn.getSubtarget().getInstrInfo();
+  if (LeafFuncOptimization)
+    addPrologLeaf(Fn, TII, MBB, DL, LeafFuncRegister);
+  else
+    addProlog(Fn, TII, MBB, DL);
+
+  MachineBasicBlock *Trap = nullptr;
+  for (auto &MBB : Fn) {
+    if (MBB.empty())
+      continue;
+
+    MachineInstr &MI = MBB.instr_back();
+    if (MI.isReturn()) {
+      if (!Trap) {
+        Trap = Fn.CreateMachineBasicBlock();
+        BuildMI(Trap, MI.getDebugLoc(), TII->get(X86::TRAP));
+        Fn.push_back(Trap);
+      }
+
+      if (LeafFuncOptimization)
+        addEpilogLeaf(TII, MBB, MI, *Trap, LeafFuncRegister);
+      else if (MI.findRegisterUseOperand(X86::R11))
+        addEpilogOnlyR10(TII, MBB, MI, *Trap);
+      else
+        addEpilog(TII, MBB, MI, *Trap);
+    }
+  }
+
+  return true;
+}
+
+INITIALIZE_PASS(ShadowCallStack, "shadow-call-stack", "Shadow Call Stack",
+                false, false)
+
+FunctionPass *llvm::createShadowCallStackPass() {
+  return new ShadowCallStack();
+}

llvm/trunk/lib/Target/X86/X86.h

 /// references and pseudo instructions into floating-point stack references and
 /// physical instructions.
 FunctionPass *createX86FloatingPointStackifierPass();
 
 /// This pass inserts AVX vzeroupper instructions before each call to avoid
 /// transition penalty between functions encoded with AVX and SSE.
 FunctionPass *createX86IssueVZeroUpperPass();
 
+/// This pass instruments the function prolog to save the return address to a
+/// 'shadow call stack' and the function epilog to check that the return address
+/// did not change during function execution.
+FunctionPass *createShadowCallStackPass();
+
 /// This pass inserts ENDBR instructions before indirect jump/call
 /// destinations as part of CET IBT mechanism.
 FunctionPass *createX86IndirectBranchTrackingPass();
 
 /// Return a pass that pads short functions with NOOPs.
 /// This will prevent a stall when returning on the Atom.
 FunctionPass *createX86PadShortFunctions();
 

llvm/trunk/lib/Target/X86/X86TargetMachine.cpp

 static cl::opt<bool> EnableMachineCombinerPass("x86-machine-combiner",
                                cl::desc("Enable the machine combiner pass"),
                                cl::init(true), cl::Hidden);
 
 namespace llvm {
 
 void initializeWinEHStatePassPass(PassRegistry &);
 void initializeFixupLEAPassPass(PassRegistry &);
+void initializeShadowCallStackPass(PassRegistry &);
 void initializeX86CallFrameOptimizationPass(PassRegistry &);
 void initializeX86CmovConverterPassPass(PassRegistry &);
 void initializeX86ExecutionDomainFixPass(PassRegistry &);
 void initializeX86DomainReassignmentPass(PassRegistry &);
 void initializeX86AvoidSFBPassPass(PassRegistry &);
 
 } // end namespace llvm
 
 extern "C" void LLVMInitializeX86Target() {
   // Register the target.
   RegisterTargetMachine<X86TargetMachine> X(getTheX86_32Target());
   RegisterTargetMachine<X86TargetMachine> Y(getTheX86_64Target());
 
   PassRegistry &PR = *PassRegistry::getPassRegistry();
   initializeGlobalISel(PR);
   initializeWinEHStatePassPass(PR);
   initializeFixupBWInstPassPass(PR);
   initializeEvexToVexInstPassPass(PR);
   initializeFixupLEAPassPass(PR);
+  initializeShadowCallStackPass(PR);
   initializeX86CallFrameOptimizationPass(PR);
   initializeX86CmovConverterPassPass(PR);
   initializeX86ExecutionDomainFixPass(PR);
   initializeX86DomainReassignmentPass(PR);
   initializeX86AvoidSFBPassPass(PR);
 }
 
 static std::unique_ptr<TargetLoweringObjectFile> createTLOF(const Triple &TT) {

 void X86PassConfig::addPreSched2() { addPass(createX86ExpandPseudoPass()); }
 
 void X86PassConfig::addPreEmitPass() {
   if (getOptLevel() != CodeGenOpt::None) {
     addPass(new X86ExecutionDomainFix());
     addPass(createBreakFalseDeps());
   }
 
+  addPass(createShadowCallStackPass());
   addPass(createX86IndirectBranchTrackingPass());
 
   if (UseVZeroUpper)
     addPass(createX86IssueVZeroUpperPass());
 
   if (getOptLevel() != CodeGenOpt::None) {
     addPass(createX86FixupBWInsts());
     addPass(createX86PadShortFunctions());
     addPass(createX86FixupLEAs());
     addPass(createX86EvexToVexInsts());
   }
 }
 
 void X86PassConfig::addPreEmitPass2() {
   addPass(createX86RetpolineThunksPass());
 }

llvm/trunk/test/CodeGen/X86/O0-pipeline.ll

 ; CHECK-NEXT:       Bundle Machine CFG Edges
 ; CHECK-NEXT:       X86 FP Stackifier
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       Prologue/Epilogue Insertion & Frame Finalization
 ; CHECK-NEXT:       Post-RA pseudo instruction expansion pass
 ; CHECK-NEXT:       X86 pseudo instruction expansion pass
 ; CHECK-NEXT:       Analyze Machine Code For Garbage Collection
+; CHECK-NEXT:       Shadow Call Stack
 ; CHECK-NEXT:       X86 Indirect Branch Tracking
 ; CHECK-NEXT:       X86 vzeroupper inserter
 ; CHECK-NEXT:       Contiguously Lay Out Funclets
 ; CHECK-NEXT:       StackMap Liveness Analysis
 ; CHECK-NEXT:       Live DEBUG_VALUE analysis
 ; CHECK-NEXT:       Insert fentry calls
 ; CHECK-NEXT:       Insert XRay ops
 ; CHECK-NEXT:       Implement the 'patchable-function' attribute

llvm/trunk/test/CodeGen/X86/O3-pipeline.ll

 ; CHECK-NEXT:       Post RA top-down list latency scheduler
 ; CHECK-NEXT:       Analyze Machine Code For Garbage Collection
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       MachinePostDominator Tree Construction
 ; CHECK-NEXT:       Branch Probability Basic Block Placement
 ; CHECK-NEXT:       ReachingDefAnalysis
 ; CHECK-NEXT:       X86 Execution Dependency Fix
 ; CHECK-NEXT:       BreakFalseDeps
+; CHECK-NEXT:       Shadow Call Stack
 ; CHECK-NEXT:       X86 Indirect Branch Tracking
 ; CHECK-NEXT:       X86 vzeroupper inserter
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Natural Loop Construction
 ; CHECK-NEXT:       X86 Byte/Word Instruction Fixup
 ; CHECK-NEXT:       X86 Atom pad short functions
 ; CHECK-NEXT:       X86 LEA Fixup
 ; CHECK-NEXT:       Compressing EVEX instrs to VEX encoding when possible

llvm/trunk/test/CodeGen/X86/shadow-call-stack.mir

+# RUN: llc -mtriple=x86_64-unknown-linux-gnu -run-pass shadow-call-stack -verify-machineinstrs -o - %s | FileCheck %s
+--- |
+
+  define void @no_return() #0 { ret void }
+  define void @normal_return() #0 { ret void }
+  define void @normal_return_leaf_func() #0 { ret void }
+  define void @short_leaf_func() #0 { ret void }
+  define void @normal_tail_call() #0 { ret void }
+  define void @r11_tail_call() #0 { ret void }
+  define void @conditional_tail_call() #0 { ret void }
+  define void @r10_live_in() #0 { ret void }
+
+  attributes #0 = { shadowcallstack }
+
+...
+---
+# CHECK-LABEL: name: no_return
+name: no_return
+tracksRegLiveness: true
+frameInfo:
+  adjustsStack: true # not a leaf function
+body: |
+  ; CHECK: bb.0:
+  bb.0:
+    ; CHECK-NEXT: $eax = MOV32ri 13
+    $eax = MOV32ri 13
+...
+---
+# CHECK-LABEL: name: normal_return
+name: normal_return
+tracksRegLiveness: true
+frameInfo:
+  adjustsStack: true # not a leaf function
+body: |
+  ; CHECK: bb.0:
+  bb.0:
+    ; CHECK: $r10 = MOV64rm $rsp, 1, $noreg, 0, $noreg
+    ; CHECK-NEXT: $r11 = XOR64rr undef $r11, undef $r11, implicit-def $eflags
+    ; CHECK-NEXT: ADD64mi8 $r11, 1, $noreg, 0, $gs, 8, implicit-def $eflags
+    ; CHECK-NEXT: $r11 = MOV64rm $r11, 1, $noreg, 0, $gs
+    ; CHECK-NEXT: MOV64mr $r11, 1, $noreg, 0, $gs, $r10
+    ; CHECK-NEXT: $eax = MOV32ri 13
+    $eax = MOV32ri 13
+
+    ; CHECK-NEXT: $r11 = XOR64rr undef $r11, undef $r11, implicit-def $eflags
+    ; CHECK-NEXT: $r10 = MOV64rm $r11, 1, $noreg, 0, $gs
+    ; CHECK-NEXT: $r10 = MOV64rm $r10, 1, $noreg, 0, $gs
+    ; CHECK-NEXT: SUB64mi8 $r11, 1, $noreg, 0, $gs, 8, implicit-def $eflags
+    ; CHECK-NEXT: CMP64mr $rsp, 1, $noreg, 0, $noreg, $r10, implicit-def $eflags
+    ; CHECK-NEXT: JNE_1 %bb.1, implicit $eflags
+    ; CHECK-NEXT: RETQ $eax
+    RETQ $eax
+
+    ; CHECK: bb.1:
+    ; CHECK-NEXT; TRAP
+...
+---
+# CHECK-LABEL: name: normal_return_leaf_func
+name: normal_return_leaf_func
+tracksRegLiveness: true
+frameInfo:
+  adjustsStack: false # leaf function
+body: |
+  ; CHECK: bb.0:
+  ; CHECK: liveins: $rcx
+  bb.0:
+    liveins: $rcx
+
+    ; CHECK: $rdx = MOV64rm $rsp, 1, $noreg, 0, $noreg
+    ; CHECK-NEXT: $eax = MOV32ri 0
+    $eax = MOV32ri 0
+    ; CHECK-NEXT: CMP64ri8 $rcx, 5, implicit-def $eflags
+    CMP64ri8 $rcx, 5, implicit-def $eflags
+    ; CHECK-NEXT: JA_1 %bb.1, implicit $eflags
+    JA_1 %bb.1, implicit $eflags
+    ; CHECK-NEXT: JMP_1 %bb.2
+    JMP_1 %bb.2
+
+  ; CHECK: bb.1
+  ; CHECK: liveins: $eax, $rdx
+  bb.1:
+    liveins: $eax
+
+    ; CHECKT: $eax = MOV32ri 1
+    $eax = MOV32ri 1
+
+  ; CHECK: bb.2
+  ; CHECK: liveins: $eax, $rdx
+  bb.2:
+    liveins: $eax
+
+    ; CHECK: CMP64mr $rsp, 1, $noreg, 0, $noreg, $rdx, implicit-def $eflags
+    ; CHECK-NEXT: JNE_1 %bb.3, implicit $eflags
+    ; CHECK-NEXT: RETQ $eax
+    RETQ $eax
+
+    ; CHECK: bb.3:
+    ; CHECK-NEXT; TRAP
+...
+---
+# CHECK-LABEL: name: short_leaf_func
+name: short_leaf_func
+tracksRegLiveness: true
+frameInfo:
+  adjustsStack: false # leaf function
+body: |
+  ; CHECK: bb.0:
+  bb.0:
+    ; CHECK: $eax = MOV32ri 13
+    $eax = MOV32ri 13
+
+    ; CHECK-NEXT: RETQ $eax
+    RETQ $eax
+...
+---
+# CHECK-LABEL: name: normal_tail_call
+name: normal_tail_call
+tracksRegLiveness: true
+frameInfo:
+  adjustsStack: true # not a leaf function
+body: |
+  ; CHECK: bb.0:
+  bb.0:
+    ; CHECK: $r10 = MOV64rm $rsp, 1, $noreg, 0, $noreg
+    ; CHECK-NEXT: $r11 = XOR64rr undef $r11, undef $r11, implicit-def $eflags
+    ; CHECK-NEXT: ADD64mi8 $r11, 1, $noreg, 0, $gs, 8, implicit-def $eflags
+    ; CHECK-NEXT: $r11 = MOV64rm $r11, 1, $noreg, 0, $gs
+    ; CHECK-NEXT: MOV64mr $r11, 1, $noreg, 0, $gs, $r10
+    ; CHECK-NEXT: $eax = MOV32ri 13
+    $eax = MOV32ri 13
+
+    ; CHECK-NEXT: $r11 = XOR64rr undef $r11, undef $r11, implicit-def $eflags
+    ; CHECK-NEXT: $r10 = MOV64rm $r11, 1, $noreg, 0, $gs
+    ; CHECK-NEXT: $r10 = MOV64rm $r10, 1, $noreg, 0, $gs
+    ; CHECK-NEXT: SUB64mi8 $r11, 1, $noreg, 0, $gs, 8, implicit-def $eflags
+    ; CHECK-NEXT: CMP64mr $rsp, 1, $noreg, 0, $noreg, $r10, implicit-def $eflags
+    ; CHECK-NEXT: JNE_1 %bb.1, implicit $eflags
+    ; CHECK-NEXT: TAILJMPr64 $rax
+    TAILJMPr64 $rax
+
+    ; CHECK: bb.1:
+    ; CHECK-NEXT; TRAP
+...
+---
+# CHECK-LABEL: name: r11_tail_call
+name: r11_tail_call
+tracksRegLiveness: true
+frameInfo:
+  adjustsStack: true # not a leaf function
+body: |
+  ; CHECK: bb.0:
+  bb.0:
+    ; CHECK: $r10 = MOV64rm $rsp, 1, $noreg, 0, $noreg
+    ; CHECK-NEXT: $r11 = XOR64rr undef $r11, undef $r11, implicit-def $eflags
+    ; CHECK-NEXT: ADD64mi8 $r11, 1, $noreg, 0, $gs, 8, implicit-def $eflags
+    ; CHECK-NEXT: $r11 = MOV64rm $r11, 1, $noreg, 0, $gs
+    ; CHECK-NEXT: MOV64mr $r11, 1, $noreg, 0, $gs, $r10
+    ; CHECK-NEXT: $eax = MOV32ri 13
+    $eax = MOV32ri 13
+
+    ; CHECK-NEXT: $r10 = XOR64rr undef $r10, undef $r10, implicit-def $eflags
+    ; CHECK-NEXT: $r10 = MOV64rm $r10, 1, $noreg, 0, $gs
+    ; CHECK-NEXT: $r10 = MOV64rm $r10, 1, $noreg, 0, $gs
+    ; CHECK-NEXT: SUB64mi8 $noreg, 1, $noreg, 0, $gs, 8, implicit-def $eflags
+    ; CHECK-NEXT: CMP64mr $rsp, 1, $noreg, 0, $noreg, $r10, implicit-def $eflags
+    ; CHECK-NEXT: JNE_1 %bb.1, implicit $eflags
+    ; CHECK-NEXT: TAILJMPr64 undef $r11
+    TAILJMPr64 undef $r11
+
+    ; CHECK: bb.1:
+    ; CHECK-NEXT; TRAP
+...
+---
+# CHECK-LABEL: name: conditional_tail_call
+name: conditional_tail_call
+tracksRegLiveness: true
+frameInfo:
+  adjustsStack: true # not a leaf function
+body: |
+  ; CHECK: bb.0:
+  bb.0:
+    ; CHECK: $eax = MOV32ri 13
+    $eax = MOV32ri 13
+
+    ; CHECK-NEXT: TAILJMPd64_CC @conditional_tail_call, undef $eflags
+    TAILJMPd64_CC @conditional_tail_call, undef $eflags
+...
+---
+# CHECK-LABEL: name: r10_live_in
+name: r10_live_in
+tracksRegLiveness: true
+frameInfo:
+  adjustsStack: true # not a leaf function
+body: |
+  ; CHECK: bb.0:
+  ; CHECK: liveins: $r10
+  bb.0:
+    liveins: $r10
+
+    ; CHECK: $eax = MOV32ri 13
+    $eax = MOV32ri 13
+    ; CHECK-NEXT: RETQ $eax
+    RETQ $eax
+...