Diff from hg rev 0b098ca44de7

18 files changed, 5066 insertions, 0 deletions

diff --git a/lib/Target/ARM/ARMInstrNaCl.td b/lib/Target/ARM/ARMInstrNaCl.td
new file mode 100644
index 0000000000..c884cd0fe4
--- /dev/null
+++ b/lib/Target/ARM/ARMInstrNaCl.td
@@ -0,0 +1,145 @@
+//====- ARMInstrNaCl.td - Describe NaCl Instructions ----*- tablegen -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file describes the modifications to the X86 instruction set needed for
+// Native Client code generation.
+//
+//===----------------------------------------------------------------------===//
+
+
+//===----------------------------------------------------------------------===//
+//
+//                       Native Client Pseudo-Instructions
+//
+// These instructions implement the Native Client pseudo-instructions, such
+// as nacljmp and naclasp.
+//
+// TableGen and MC consider these to be "real" instructions. They can be
+// parsed by the AsmParser and emitted by the AsmStreamer as if they
+// were just regular instructions. They are not marked "Pseudo" because
+// this would imply isCodeGenOnly=1, which would stop them from being
+// parsed by the assembler.
+//
+// These instructions cannot be encoded (written into an object file) by the
+// MCCodeEmitter. Instead, during direct object emission, they get lowered to
+// a sequence of streamer emits. (see ARMInstrNaCl.cpp)
+// 
+// These instructions should not be used in CodeGen. They have no pattern
+// and lack CodeGen metadata. Instead, the ARMNaClRewritePass should
+// generate these instructions after CodeGen is finished.
+//
+//===----------------------------------------------------------------------===//
+
+//===----------------------------------------------------------------------===//
+// ARM Native Client "Pseudo" Instructions
+//===----------------------------------------------------------------------===//
+
+// It does not seem possible to define a single base class for both the 
+// synthetic isCodeGenOnly=1 instructions as well as the isAsmParserOnly=1 
+// versions.
+
+// These are the fixed flags:
+// AddrMode am = AddrModeNone
+// SizeFlagVal sz = SizeSpecial
+// IndexMode im = IndexModeNone
+// Domain d = GenericDomain
+// InstrItinClass = NoItinerary
+
+// The non-fixed flags need their own class 
+// InOperandList = !con(iops, (ins pred:$p)) or left alone
+// AsmString = !strconcat(opc, "${p}", asm) or left alone
+// Format f = MiscFrm/Pseudo
+// isPredicable = 0/1 
+
+/// However, it is possible to make a set of two base classes for the isAsmParserOnly=1
+/// synthetic instructions.
+
+
+/***** FIXME: ADD in isAsmParserOnly naclguard instructions ***************************
+/// required args:
+// dag outs, dag ins, string opc, string asm, string cstr, Format f, list<dag> pat
+
+class NaClSI<dag outs, dag ins, string opc, string asm, string cstr> 
+  : I<outs, ins, AddrModeNone, SizeSpecial, IndexModeNone, MiscFrm, 
+              NoItinerary, opc, asm, cstr, pat>, Requires<[IsNaCl]>;
+
+class NaClSINoP<dag outs, dag ins, string opc, string asm, string cstr> 
+  : InoP <outs, ins, AddrModeNone, SizeSpecial, IndexModeNone, MiscFrm, 
+              NoItinerary, opc, asm, cstr, pat>, Requires<[IsNaCl]>;
+
+class NaClSI<dag outs, dag ins, string opc, string asm, string cstr, Format f, list<dag> pat> 
+  : InstARM<AddrModeNone, SizeSpecial, IndexModeNone, f,
+            GenericDomain, cstr, NoItinerary>, Requires<[IsNaCl]> {
+  let OutOperandList = oops;
+  let InOperandList = iops;
+  let Pattern = pattern;
+  let AsmString = !strconcat(opc, asm);
+};
+
+
+/// For not pseudo instructionable      
+class NaClSINoP<dag outs, dag ins, string opc, string asm, string cstr, Format f, list<dag> pat> 
+  : InstARM<AddrModeNone, SizeSpecial, IndexModeNone, f,
+            GenericDomain, cstr, NoItinerary>, Requires<[IsNaCl]> {
+  let OutOperandList = oops;
+  let InOperandList = iops;
+  let Pattern = pattern;
+  let AsmString = !strconcat(opc, asm);
+};
+
+/// This is the guarded isCodeGenOnly pseudo instruction for BX_RET
+let isReturn = 1, isTerminator = 1, isBarrier = 1, isCodeGenOnly = 1,
+    // Make sure this is selected in lieu of 
+    AddedComplexity = 1 
+ in {
+  // ARMV4T and above
+  def NACL_CG_BX_RET : 
+     ARMPseudoInst<(outs), (ins), BrMiscFrm, IIC_Br, 
+                   "naclbx", "\tlr", [(ARMretflag)]>,
+     Requires<[HasV4T, IsNaCl]> {
+  }
+}
+
+
+// These are assembler only instructions 
+let isAsmParserOnly = 1 in {
+  def NACL_GUARD_LOADSTORE :
+  NaClSI<(outs GPR:$dst), (ins GPR:$a), 
+         "naclguard", "\t${dst}, ${a}", "" []>;
+
+  let Defs = [CPSR] in
+  def NACL_GUARD_LOADSTORE_TST :
+    NaClSINoP<
+  PseudoInst<(outs GPR:$dst), (ins GPR:$a), NoItinerary, []> ;
+
+
+  let Defs = [CPSR] in
+  def NACL_GUARD_LOADSTORE_TST :
+  PseudoInst<(outs GPR:$dst), (ins GPR:$a), NoItinerary, []>;
+
+  def NACL_GUARD_INDIRECT_CALL :
+  PseudoInst<(outs GPR:$dst), (ins GPR:$a, pred:$p), NoItinerary, []>;
+
+  def NACL_GUARD_INDIRECT_JMP :
+  PseudoInst<(outs GPR:$dst), (ins GPR:$a, pred:$p), NoItinerary, []>;
+
+  def NACL_GUARD_CALL :
+  PseudoInst<(outs), (ins pred:$p), NoItinerary, []>;
+
+  // NOTE: the BX_RET instruction hardcodes lr as well
+  def NACL_GUARD_RETURN :
+  PseudoInst<(outs), (ins pred:$p), NoItinerary, []>;
+
+  // Note: intention is that $src and $dst are the same register.
+  def NACL_DATA_MASK :
+  PseudoInst<(outs GPR:$dst), (ins GPR:$src, pred:$p), NoItinerary, []>;
+}
+
+
+**************************************************************************/
diff --git a/lib/Target/ARM/ARMNaClHeaders.cpp b/lib/Target/ARM/ARMNaClHeaders.cpp
new file mode 100644
index 0000000000..781702158a
--- /dev/null
+++ b/lib/Target/ARM/ARMNaClHeaders.cpp
@@ -0,0 +1,192 @@
+//===-- ARMNaClHeaders.cpp - Print SFI headers to an ARM .s file -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the initial header string needed
+// for the Native Client target in ARM assembly.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/raw_ostream.h"
+#include "ARMNaClRewritePass.h"
+#include <string>
+
+using namespace llvm;
+
+void EmitSFIHeaders(raw_ostream &O) {
+  O << " @ ========================================\n";
+  O << "@ Branch: " << FlagSfiBranch << "\n";
+  O << "@ Stack: " << FlagSfiStack << "\n";
+  O << "@ Store: " << FlagSfiStore << "\n";
+  O << "@ Data: " << FlagSfiData << "\n";
+
+  O << " @ ========================================\n";
+  // NOTE: this macro does bundle alignment as follows
+  //       if current bundle pos is X emit pX data items of value "val"
+  // NOTE: that pos will be one of: 0,4,8,12
+  //
+  O <<
+    "\t.macro sfi_long_based_on_pos p0 p1 p2 p3 val\n"
+    "\t.set pos, (. - XmagicX) % 16\n"
+    "\t.fill  (((\\p3<<12)|(\\p2<<8)|(\\p1<<4)|\\p0)>>pos) & 15, 4, \\val\n"
+    "\t.endm\n"
+    "\n\n";
+
+  O <<
+    "\t.macro sfi_illegal_if_at_bundle_begining\n"
+    "\tsfi_long_based_on_pos 1 0 0 0 0xe1277777\n"
+    "\t.endm\n"
+    "\n\n";
+
+  O <<
+    "\t.macro sfi_nop_if_at_bundle_end\n"
+    "\tsfi_long_based_on_pos 0 0 0 1 0xe320f000\n"
+    "\t.endm\n"
+      "\n\n";
+
+  O <<
+    "\t.macro sfi_nops_to_force_slot3\n"
+    "\tsfi_long_based_on_pos 3 2 1 0 0xe320f000\n"
+    "\t.endm\n"
+    "\n\n";
+
+  O <<
+    "\t.macro sfi_nops_to_force_slot2\n"
+    "\tsfi_long_based_on_pos 2 1 0 3 0xe320f000\n"
+    "\t.endm\n"
+    "\n\n";
+
+  O <<
+    "\t.macro sfi_nops_to_force_slot1\n"
+    "\tsfi_long_based_on_pos 1 0 3 2 0xe320f000\n"
+    "\t.endm\n"
+    "\n\n";
+
+  O << " @ ========================================\n";
+  if (FlagSfiZeroMask) {
+    // This mode sets all mask to zero which makes them into nops
+    // this is useful for linking this code against non-sandboxed code
+    // for debugging purposes
+    O <<
+      "\t.macro sfi_data_mask reg cond\n"
+      "\tbic\\cond \\reg, \\reg, #0\n"
+      "\t.endm\n"
+      "\n\n";
+
+    O <<
+      "\t.macro sfi_data_tst reg\n"
+      "\ttst \\reg, #0x00000000\n"
+      "\t.endm\n"
+      "\n\n";
+
+    O <<
+      "\t.macro sfi_code_mask reg cond=\n"
+      "\tbic\\cond \\reg, \\reg, #0\n"
+      "\t.endm\n"
+      "\n\n";
+
+  } else {
+    O <<
+      "\t.macro sfi_data_mask reg cond\n"
+      "\tbic\\cond \\reg, \\reg, #0xc0000000\n"
+      "\t.endm\n"
+      "\n\n";
+
+    O <<
+      "\t.macro sfi_data_tst reg\n"
+      "\ttst \\reg, #0xc0000000\n"
+      "\t.endm\n"
+      "\n\n";
+
+    O <<
+      "\t.macro sfi_code_mask reg cond=\n"
+      "\tbic\\cond \\reg, \\reg, #0xc000000f\n"
+      "\t.endm\n"
+      "\n\n";
+  }
+
+  O << " @ ========================================\n";
+  if (FlagSfiBranch) {
+    O <<
+      "\t.macro sfi_call_preamble cond=\n"
+      "\tsfi_nops_to_force_slot3\n"
+      "\t.endm\n"
+      "\n\n";
+
+    O <<
+      "\t.macro sfi_return_preamble reg cond=\n"
+      "\tsfi_nop_if_at_bundle_end\n"
+      "\tsfi_code_mask \\reg \\cond\n"
+      "\t.endm\n"
+      "\n\n";
+    
+    // This is used just before "bx rx"
+    O <<
+      "\t.macro sfi_indirect_jump_preamble link cond=\n"
+      "\tsfi_nop_if_at_bundle_end\n"
+      "\tsfi_code_mask \\link \\cond\n"
+      "\t.endm\n"
+      "\n\n";
+
+    // This is use just before "blx rx"
+    O <<
+      "\t.macro sfi_indirect_call_preamble link cond=\n"
+      "\tsfi_nops_to_force_slot2\n"
+      "\tsfi_code_mask \\link \\cond\n"
+      "\t.endm\n"
+      "\n\n";
+
+  }
+
+  if (FlagSfiStore) {
+    O << " @ ========================================\n";
+
+    O <<
+      "\t.macro sfi_load_store_preamble reg cond\n"
+      "\tsfi_nop_if_at_bundle_end\n"
+      "\tsfi_data_mask \\reg, \\cond\n"
+      "\t.endm\n"
+      "\n\n";
+
+    O <<
+      "\t.macro sfi_cstore_preamble reg\n"
+      "\tsfi_nop_if_at_bundle_end\n"
+      "\tsfi_data_tst \\reg\n"
+      "\t.endm\n"
+      "\n\n";
+  } else {
+    O <<
+      "\t.macro sfi_load_store_preamble reg cond\n"
+      "\t.endm\n"
+      "\n\n";
+
+    O <<
+      "\t.macro sfi_cstore_preamble reg cond\n"
+      "\t.endm\n"
+      "\n\n";
+  }
+
+  const char* kPreds[] = {
+    "eq",
+    "ne",
+    "lt",
+    "le",
+    "ls",
+    "ge",
+    "gt",
+    "hs",
+    "hi",
+    "lo",
+    "mi",
+    "pl",
+    NULL,
+  };
+
+  O << " @ ========================================\n";
+  O << "\t.text\n";
+}
diff --git a/lib/Target/ARM/ARMNaClRewritePass.cpp b/lib/Target/ARM/ARMNaClRewritePass.cpp
new file mode 100644
index 0000000000..91087aaaa2
--- /dev/null
+++ b/lib/Target/ARM/ARMNaClRewritePass.cpp
@@ -0,0 +1,755 @@
+//===-- ARMNaClRewritePass.cpp - Native Client Rewrite Pass  ------*- C++ -*-=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Native Client Rewrite Pass
+// This final pass inserts the sandboxing instructions needed to run inside
+// the Native Client sandbox. Native Client requires certain software fault
+// isolation (SFI) constructions to be put in place, to prevent escape from
+// the sandbox. Native Client refuses to execute binaries without the correct
+// SFI sequences.
+// 
+// Potentially dangerous operations which are protected include:
+// * Stores
+// * Branches
+// * Changes to SP
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "arm-sfi"
+#include "ARM.h"
+#include "ARMBaseInstrInfo.h"
+#include "ARMNaClRewritePass.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/Function.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/CommandLine.h"
+#include <set>
+#include <stdio.h>
+
+using namespace llvm;
+
+namespace llvm {
+
+cl::opt<bool>
+FlagSfiData("sfi-data", cl::desc("use illegal at data bundle beginning"));
+
+cl::opt<bool>
+FlagSfiLoad("sfi-load", cl::desc("enable sandboxing for load"));
+
+cl::opt<bool>
+FlagSfiStore("sfi-store", cl::desc("enable sandboxing for stores"));
+
+cl::opt<bool>
+FlagSfiStack("sfi-stack", cl::desc("enable sandboxing for stack changes"));
+
+cl::opt<bool>
+FlagSfiBranch("sfi-branch", cl::desc("enable sandboxing for branches"));
+
+}
+
+namespace {
+  class ARMNaClRewritePass : public MachineFunctionPass {
+  public:
+    static char ID;
+    ARMNaClRewritePass() : MachineFunctionPass(ID) {}
+
+    const ARMBaseInstrInfo *TII;
+    const TargetRegisterInfo *TRI;
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+    virtual bool runOnMachineFunction(MachineFunction &Fn);
+
+    virtual const char *getPassName() const {
+      return "ARM Native Client Rewrite Pass";
+    }
+
+  private:
+
+    bool SandboxMemoryReferencesInBlock(MachineBasicBlock &MBB);
+    void SandboxMemory(MachineBasicBlock &MBB,
+                       MachineBasicBlock::iterator MBBI,
+                       MachineInstr &MI,
+                       int AddrIdx,
+                       bool CPSRLive,
+                       bool IsLoad);
+    bool TryPredicating(MachineInstr &MI, ARMCC::CondCodes);
+
+    bool SandboxBranchesInBlock(MachineBasicBlock &MBB);
+    bool SandboxStackChangesInBlock(MachineBasicBlock &MBB);
+
+    void SandboxStackChange(MachineBasicBlock &MBB,
+                              MachineBasicBlock::iterator MBBI);
+    void LightweightVerify(MachineFunction &MF);
+  };
+  char ARMNaClRewritePass::ID = 0;
+}
+
+static bool IsReturn(const MachineInstr &MI) {
+  return (MI.getOpcode() == ARM::BX_RET);
+}
+
+static bool IsIndirectJump(const MachineInstr &MI) {
+  switch (MI.getOpcode()) {
+   default: return false;
+   case ARM::BX:
+   case ARM::TAILJMPr:
+    return true;
+  }
+}
+
+static bool IsIndirectCall(const MachineInstr &MI) {
+  return MI.getOpcode() == ARM::BLX;
+}
+
+static bool IsDirectCall(const MachineInstr &MI) {
+  switch (MI.getOpcode()) {
+   default: return false;
+   case ARM::BL:
+   case ARM::BL_pred:
+   case ARM::TPsoft:
+     return true;
+  }
+}
+
+static bool IsCPSRLiveOut(const MachineBasicBlock &MBB) {
+  // CPSR is live-out if any successor lists it as live-in.
+  for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(),
+                                              E = MBB.succ_end();
+       SI != E;
+       ++SI) {
+    const MachineBasicBlock *Succ = *SI;
+    if (Succ->isLiveIn(ARM::CPSR)) return true;
+  }
+  return false;
+}
+
+static void DumpInstructionVerbose(const MachineInstr &MI) {
+  dbgs() << MI;
+  dbgs() << MI.getNumOperands() << " operands:" << "\n";
+  for (unsigned i = 0; i < MI.getNumOperands(); ++i) {
+    const MachineOperand& op = MI.getOperand(i);
+    dbgs() << "  " << i << "(" << op.getType() << "):" << op << "\n";
+  }
+  dbgs() << "\n";
+}
+
+static void DumpBasicBlockVerbose(const MachineBasicBlock &MBB) {
+  dbgs() << "\n<<<<< DUMP BASIC BLOCK START\n";
+  for (MachineBasicBlock::const_iterator MBBI = MBB.begin(), MBBE = MBB.end();
+       MBBI != MBBE;
+       ++MBBI) {
+    DumpInstructionVerbose(*MBBI);
+  }
+  dbgs() << "<<<<< DUMP BASIC BLOCK END\n\n";
+}
+
+static void DumpBasicBlockVerboseCond(const MachineBasicBlock &MBB, bool b) {
+  if (b) {
+    DumpBasicBlockVerbose(MBB);
+  }
+}
+
+/**********************************************************************/
+/* Exported functions */
+
+namespace ARM_SFI {
+
+bool IsStackChange(const MachineInstr &MI, const TargetRegisterInfo *TRI) {
+  return MI.modifiesRegister(ARM::SP, TRI);
+}
+
+bool NextInstrMasksSP(const MachineInstr &MI) {
+  MachineBasicBlock::const_iterator It = &MI;
+  const MachineBasicBlock *MBB = MI.getParent();
+
+  MachineBasicBlock::const_iterator next = ++It;
+  if (next == MBB->end()) {
+    return false;
+  }
+
+  const MachineInstr &next_instr = *next;
+  unsigned opcode = next_instr.getOpcode();
+  return (opcode == ARM::SFI_DATA_MASK) &&
+      (next_instr.getOperand(0).getReg() == ARM::SP);
+}
+
+bool IsSandboxedStackChange(const MachineInstr &MI) {
+  // Calls do not change the stack on ARM but they have implicit-defs, so
+  // make sure they do not get sandboxed.
+  if (MI.getDesc().isCall())
+    return true;
+
+  unsigned opcode = MI.getOpcode();
+  switch (opcode) {
+    default: break;
+
+    // These just bump SP by a little (and access the stack),
+    // so that is okay due to guard pages.
+    case ARM::STMIA_UPD:
+    case ARM::STMDA_UPD:
+    case ARM::STMDB_UPD:
+    case ARM::STMIB_UPD:
+
+    case ARM::VSTMDIA_UPD:
+    case ARM::VSTMDDB_UPD:
+    case ARM::VSTMSIA_UPD:
+    case ARM::VSTMSDB_UPD:
+      return true;
+
+    // Similar, unless it is a load into SP...
+    case ARM::LDMIA_UPD:
+    case ARM::LDMDA_UPD:
+    case ARM::LDMDB_UPD:
+    case ARM::LDMIB_UPD:
+
+    case ARM::VLDMDIA_UPD:
+    case ARM::VLDMDDB_UPD:
+    case ARM::VLDMSIA_UPD:
+    case ARM::VLDMSDB_UPD: {
+      bool dest_SP = false;
+      // Dest regs start at operand index 4.
+      for (unsigned i = 4; i < MI.getNumOperands(); ++i) {
+        const MachineOperand &DestReg = MI.getOperand(i);
+        dest_SP = dest_SP || (DestReg.getReg() == ARM::SP);
+      }
+      if (dest_SP) {
+        break;
+      }
+      return true;
+    }
+
+    // Some localmods *should* prevent selecting a reg offset
+    // (see SelectAddrMode2 in ARMISelDAGToDAG.cpp).
+    // Otherwise, the store is already a potential violation.
+    case ARM::STR_PRE_REG:
+    case ARM::STR_PRE_IMM:
+
+    case ARM::STRH_PRE:
+
+    case ARM::STRB_PRE_REG:
+    case ARM::STRB_PRE_IMM:
+      return true;
+
+    // Similar, unless it is a load into SP...
+    case ARM::LDRi12:
+    case ARM::LDR_PRE_REG:
+    case ARM::LDR_PRE_IMM:
+    case ARM::LDRH_PRE:
+    case ARM::LDRB_PRE_REG:
+    case ARM::LDRB_PRE_IMM:
+    case ARM::LDRSH_PRE:
+    case ARM::LDRSB_PRE: {
+      const MachineOperand &DestReg = MI.getOperand(0);
+      if (DestReg.getReg() == ARM::SP) {
+        break;
+      }
+      return true;
+    }
+
+    // Here, if SP is the base / write-back reg, we need to check if
+    // a reg is used as offset (otherwise it is not a small nudge).
+    case ARM::STR_POST_REG:
+    case ARM::STR_POST_IMM:
+    case ARM::STRH_POST:
+    case ARM::STRB_POST_REG:
+    case ARM::STRB_POST_IMM: {
+      const MachineOperand &WBReg = MI.getOperand(0);
+      const MachineOperand &OffReg = MI.getOperand(3);
+      if (WBReg.getReg() == ARM::SP && OffReg.getReg() != 0) {
+        break;
+      }
+      return true;
+    }
+
+    // Similar, but also check that DestReg is not SP.
+    case ARM::LDR_POST_REG:
+    case ARM::LDR_POST_IMM:
+    case ARM::LDRB_POST_REG:
+    case ARM::LDRB_POST_IMM:
+    case ARM::LDRH_POST:
+    case ARM::LDRSH_POST:
+    case ARM::LDRSB_POST: {
+      const MachineOperand &DestReg = MI.getOperand(0);
+      if (DestReg.getReg() == ARM::SP) {
+        break;
+      }
+      const MachineOperand &WBReg = MI.getOperand(1);
+      const MachineOperand &OffReg = MI.getOperand(3);
+      if (WBReg.getReg() == ARM::SP && OffReg.getReg() != 0) {
+        break;
+      }
+      return true;
+    }
+  }
+
+  return (NextInstrMasksSP(MI));
+}
+
+bool NeedSandboxStackChange(const MachineInstr &MI,
+                               const TargetRegisterInfo *TRI) {
+  return (IsStackChange(MI, TRI) && !IsSandboxedStackChange(MI));
+}
+
+} // namespace ARM_SFI
+
+/**********************************************************************/
+
+void ARMNaClRewritePass::getAnalysisUsage(AnalysisUsage &AU) const {
+  // Slight (possibly unnecessary) efficiency tweak:
+  // Promise not to modify the CFG.
+  AU.setPreservesCFG();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+/*
+ * A primitive validator to catch problems at compile time.
+ * E.g., it could be used along with bugpoint to reduce a bitcode file.
+ */
+void ARMNaClRewritePass::LightweightVerify(MachineFunction &MF) {
+
+  for (MachineFunction::iterator MFI = MF.begin(), MFE = MF.end();
+       MFI != MFE;
+       ++MFI) {
+    MachineBasicBlock &MBB = *MFI;
+    for (MachineBasicBlock::iterator MBBI = MBB.begin(), MBBE = MBB.end();
+         MBBI != MBBE;
+         ++MBBI) {
+      MachineInstr &MI = *MBBI;
+
+      if (ARM_SFI::NeedSandboxStackChange(MI, TRI)) {
+        dbgs() << "LightWeightVerify for function: "
+               << MF.getFunction()->getName() << "  (BAD STACK CHANGE)\n";
+        DumpInstructionVerbose(MI);
+        DumpBasicBlockVerbose(MBB);
+        //        assert(false && "LightweightVerify Failed");
+      }
+    }
+  }
+}
+
+void ARMNaClRewritePass::SandboxStackChange(MachineBasicBlock &MBB,
+                                       MachineBasicBlock::iterator MBBI) {
+  // (1) Ensure there is room in the bundle for a data mask instruction
+  // (nop'ing to the next bundle if needed).
+  // (2) Do a data mask on SP after the instruction that updated SP.
+  MachineInstr &MI = *MBBI;
+
+  // Use same predicate as current instruction.
+  ARMCC::CondCodes Pred = TII->getPredicate(&MI);
+
+  BuildMI(MBB, MBBI, MI.getDebugLoc(),
+          TII->get(ARM::SFI_NOP_IF_AT_BUNDLE_END));
+
+  // Get to next instr (one + to get the original, and one more + to get past)
+  MachineBasicBlock::iterator MBBINext = (MBBI++);
+  MachineBasicBlock::iterator MBBINext2 = (MBBI++);
+
+  BuildMI(MBB, MBBINext2, MI.getDebugLoc(),
+          TII->get(ARM::SFI_DATA_MASK))
+      .addReg(ARM::SP)         // modify SP (as dst)
+      .addReg(ARM::SP)         // start with SP (as src)
+      .addImm((int64_t) Pred)  // predicate condition
+      .addReg(ARM::CPSR);      // predicate source register (CPSR)
+
+  return;
+}
+
+bool ARMNaClRewritePass::SandboxStackChangesInBlock(MachineBasicBlock &MBB) {
+  bool Modified = false;
+  for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
+       MBBI != E;
+       ++MBBI) {
+    MachineInstr &MI = *MBBI;
+    if (ARM_SFI::NeedSandboxStackChange(MI, TRI)) {
+      SandboxStackChange(MBB, MBBI);
+      Modified |= true;
+    }
+  }
+  return Modified;
+}
+
+bool ARMNaClRewritePass::SandboxBranchesInBlock(MachineBasicBlock &MBB) {
+  bool Modified = false;
+
+  for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
+       MBBI != E;
+       ++MBBI) {
+    MachineInstr &MI = *MBBI;
+
+    if (IsReturn(MI)) {
+      ARMCC::CondCodes Pred = TII->getPredicate(&MI);
+      BuildMI(MBB, MBBI, MI.getDebugLoc(),
+              TII->get(ARM::SFI_GUARD_RETURN))
+        .addImm((int64_t) Pred)  // predicate condition
+        .addReg(ARM::CPSR);      // predicate source register (CPSR)
+      Modified = true;
+    }
+
+    if (IsIndirectJump(MI)) {
+      MachineOperand &Addr = MI.getOperand(0);
+      ARMCC::CondCodes Pred = TII->getPredicate(&MI);
+      BuildMI(MBB, MBBI, MI.getDebugLoc(),
+              TII->get(ARM::SFI_GUARD_INDIRECT_JMP))
+        .addOperand(Addr)        // rD
+        .addReg(0)               // apparently unused source register?
+        .addImm((int64_t) Pred)  // predicate condition
+        .addReg(ARM::CPSR);      // predicate source register (CPSR)
+      Modified = true;
+    }
+
+    if (IsDirectCall(MI)) {
+      ARMCC::CondCodes Pred = TII->getPredicate(&MI);
+      BuildMI(MBB, MBBI, MI.getDebugLoc(),
+              TII->get(ARM::SFI_GUARD_CALL))
+        .addImm((int64_t) Pred)  // predicate condition
+        .addReg(ARM::CPSR);      // predicate source register (CPSR)
+      Modified = true;
+    }
+
+    if (IsIndirectCall(MI)) {
+      MachineOperand &Addr = MI.getOperand(0);
+      ARMCC::CondCodes Pred = TII->getPredicate(&MI);
+      BuildMI(MBB, MBBI, MI.getDebugLoc(),
+              TII->get(ARM::SFI_GUARD_INDIRECT_CALL))
+        .addOperand(Addr)        // rD
+        .addReg(0)               // apparently unused source register?
+        .addImm((int64_t) Pred)  // predicate condition
+        .addReg(ARM::CPSR);      // predicate source register (CPSR)
+        Modified = true;
+    }
+  }
+
+  return Modified;
+}
+
+bool ARMNaClRewritePass::TryPredicating(MachineInstr &MI, ARMCC::CondCodes Pred) {
+  // Can't predicate if it's already predicated.
+  // TODO(cbiffle): actually we can, if the conditions match.
+  if (TII->isPredicated(&MI)) return false;
+
+  /*
+   * ARM predicate operands use two actual MachineOperands: an immediate
+   * holding the predicate condition, and a register referencing the flags.
+   */
+  SmallVector<MachineOperand, 2> PredOperands;
+  PredOperands.push_back(MachineOperand::CreateImm((int64_t) Pred));
+  PredOperands.push_back(MachineOperand::CreateReg(ARM::CPSR, false));
+
+  // This attempts to rewrite, but some instructions can't be predicated.
+  return TII->PredicateInstruction(&MI, PredOperands);
+}
+
+static bool IsDangerousLoad(const MachineInstr &MI, int *AddrIdx) {
+  unsigned Opcode = MI.getOpcode();
+  switch (Opcode) {
+  default: return false;
+
+  // Instructions with base address register in position 0...
+  case ARM::LDMIA:
+  case ARM::LDMDA:
+  case ARM::LDMDB:
+  case ARM::LDMIB:
+
+  case ARM::VLDMDIA:
+  case ARM::VLDMSIA:
+    *AddrIdx = 0;
+    break;
+  // Instructions with base address register in position 1...
+  case ARM::LDMIA_UPD: // same reg at position 0 and position 1
+  case ARM::LDMDA_UPD:
+  case ARM::LDMDB_UPD:
+  case ARM::LDMIB_UPD:
+
+  case ARM::LDRSB:
+  case ARM::LDRH:
+  case ARM::LDRSH:
+
+  case ARM::LDRi12:
+  case ARM::LDRrs:
+  case ARM::LDRBi12:
+  case ARM::LDRBrs:
+  case ARM::VLDMDIA_UPD:
+  case ARM::VLDMDDB_UPD:
+  case ARM::VLDMSIA_UPD:
+  case ARM::VLDMSDB_UPD:
+  case ARM::VLDRS:
+  case ARM::VLDRD:
+
+  case ARM::LDREX:
+  case ARM::LDREXB:
+  case ARM::LDREXH:
+    *AddrIdx = 1;
+    break;
+
+  // Instructions with base address register in position 2...
+  case ARM::LDR_PRE_REG:
+  case ARM::LDR_PRE_IMM:
+  case ARM::LDR_POST_REG:
+  case ARM::LDR_POST_IMM:
+
+  case ARM::LDRB_PRE_REG:
+  case ARM::LDRB_PRE_IMM:
+  case ARM::LDRB_POST_REG:
+  case ARM::LDRB_POST_IMM:
+  case ARM::LDRSB_PRE:
+  case ARM::LDRSB_POST:
+
+  case ARM::LDRH_PRE:
+  case ARM::LDRH_POST:
+  case ARM::LDRSH_PRE:
+  case ARM::LDRSH_POST:
+
+  case ARM::LDRD:
+    *AddrIdx = 2;
+    break;
+  }
+
+  if (MI.getOperand(*AddrIdx).getReg() == ARM::SP) {
+    // The contents of SP do not require masking.
+    return false;
+  }
+
+  return true;
+}
+
+/*
+ * Sandboxes a memory reference instruction by inserting an appropriate mask
+ * or check operation before it.
+ */
+void ARMNaClRewritePass::SandboxMemory(MachineBasicBlock &MBB,
+                                       MachineBasicBlock::iterator MBBI,
+                                       MachineInstr &MI,
+                                       int AddrIdx,
+                                       bool CPSRLive,
+                                       bool IsLoad) {
+  MachineOperand &Addr = MI.getOperand(AddrIdx);
+
+  if (!CPSRLive && TryPredicating(MI, ARMCC::EQ)) {
+    /*
+     * For unconditional memory references where CPSR is not in use, we can use
+     * a faster sandboxing sequence by predicating the load/store -- assuming we
+     * *can* predicate the load/store.
+     */
+
+    // TODO(sehr): add SFI_GUARD_SP_LOAD_TST.
+    // Instruction can be predicated -- use the new sandbox.
+    BuildMI(MBB, MBBI, MI.getDebugLoc(),
+            TII->get(ARM::SFI_GUARD_LOADSTORE_TST))
+      .addOperand(Addr)   // rD
+      .addReg(0);         // apparently unused source register?
+  } else {
+    unsigned Opcode;
+    if (IsLoad && (MI.getOperand(0).getReg() == ARM::SP)) {
+      Opcode = ARM::SFI_GUARD_SP_LOAD;
+    } else {
+      Opcode = ARM::SFI_GUARD_LOADSTORE;
+    }
+    // Use the older BIC sandbox, which is universal, but incurs a stall.
+    ARMCC::CondCodes Pred = TII->getPredicate(&MI);
+    BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(Opcode))
+      .addOperand(Addr)        // rD
+      .addReg(0)               // apparently unused source register?
+      .addImm((int64_t) Pred)  // predicate condition
+      .addReg(ARM::CPSR);      // predicate source register (CPSR)
+
+    /*
+     * This pseudo-instruction is intended to generate something resembling the
+     * following, but with alignment enforced.
+     * TODO(cbiffle): move alignment into this function, use the code below.
+     *
+     *  // bic<cc> Addr, Addr, #0xC0000000
+     *  BuildMI(MBB, MBBI, MI.getDebugLoc(),
+     *          TII->get(ARM::BICri))
+     *    .addOperand(Addr)        // rD
+     *    .addOperand(Addr)        // rN
+     *    .addImm(0xC0000000)      // imm
+     *    .addImm((int64_t) Pred)  // predicate condition
+     *    .addReg(ARM::CPSR)       // predicate source register (CPSR)
+     *    .addReg(0);              // flag output register (0 == no flags)
+     */
+  }
+}
+
+static bool IsDangerousStore(const MachineInstr &MI, int *AddrIdx) {
+  unsigned Opcode = MI.getOpcode();
+  switch (Opcode)