Fixed Noop insertion

[rinon]

Summary

Fixes build and test failures from r225908. Replaces std::uniform_real_distribution in Noop insertion.

std::uniform_real_distribution is not consistent across platforms. This
patch implements a simple integer unbiased random number range
distribution.

Original description:

A pass that adds random noops to X86 binaries to introduce diversity with the goal of increasing security against most return-oriented programming attacks.

Command line options:

-noop-insertion Enable noop insertion.
-noop-insertion-percentage=X X% of assembly instructions will have a noop prepended (default: 50%, requires -noop-insertion)
-max-noops-per-instruction=X // Randomly generate X noops per instruction. ie. roll the dice X times with probability set above (default: 1). This doesn't guarantee X noop instructions.

In addition, the following 'quick switch' in clang enables basic diversity using default settings (currently: noop insertion and schedule randomization; it is intended to be extended in the future).

-fdiversify

[rinon]

• Replace uint_fast64_t with result_type

[rinon]

lib/Support/RandomNumberGenerator.cpp

57

This seems like a strange way to break this line, but it's what clang-format seems to think is right...

[rinon]

Verified that tests pass on Linux now (Ubuntu 14.04, current master). Having completely removed the dependence on the Distribution member, there shouldn't be any build problems on Windows. Just needs someone to look over the new ranged RNG operator(Max) function.

[jfb]

lib/Support/RandomNumberGenerator.cpp

69

Do you think you could create a utility that effectively meets the uniform_int_distribution requirements of the standard, while offering an implementation that doesn't change from one standard library to another? This would make it easier to convince readers of the code that the RNG+distribution is actually doing what they expect.

The obvious fix is to simply include libc++'s implementation since the license is the same:

template<class _IntType>
template<class _URNG>
typename uniform_int_distribution<_IntType>::result_type
uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
{
    typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
                                            uint32_t, uint64_t>::type _UIntType;
    const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1);
    if (_Rp == 1)
        return __p.a();
    const size_t _Dt = numeric_limits<_UIntType>::digits;
    typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
    if (_Rp == 0)
        return static_cast<result_type>(_Eng(__g, _Dt)());
    size_t __w = _Dt - __clz(_Rp) - 1;
    if ((_Rp & (_UIntType(~0) >> (_Dt - __w))) != 0)
        ++__w;
    _Eng __e(__g, __w);
    _UIntType __u;
    do
    {
        __u = __e();
    } while (__u >= _Rp);
    return static_cast<result_type>(__u + __p.a());
}

The duplication is unfortunate, but generating the same sequence independently of stdlib implementation kind of makes duplication a requirement.

[rinon]

lib/Support/RandomNumberGenerator.cpp

69

Sorry, I missed your comment. Somehow it slipped by my email.

Yes, I think we could use libc++'s implementation (from the spec it seems that independent_bits_engine should be stable). However, I think the only thing we really gain with this is efficiency. The libc++ implementation is faster, at the expense of readability and code size.

I'm happy to integrate this optimized implementation into the current RNG class, but I'd be adverse to creating a completely duplicate uniform_int_distribution utility class. That seems like a lot of code duplication for a simple feature.

[jfb]

lib/Support/RandomNumberGenerator.cpp

69

My main concern is convincing myself that your implementation indeed has the advertised uniform distribution. When I read the code I don't find this obvious, and there's no unit test for this function to check the distribution is indeed uniform.

It's indeed even less obvious from the libc++ implementation, but having the same implementation means that we can rely on libc++'s {test suite / users / following the spec} to make sure it's correct. AFAICT libc++ doesn't have a unit test on its distribution either...

[rinon]

lib/Support/RandomNumberGenerator.cpp

69

On closer inspection, we can't use the libc++ implementation. It depends on independent_bits_engine taking the number of bits as a constructor parameter, not as a template parameter as the standard dictates. Since the range should be a parameter, this makes life difficult.

I'll see if I can't find a solid reference or implementation so we don't need to worry about this bit. It really shouldn't be bad.

[rinon]

lib/Support/RandomNumberGenerator.cpp

69

If you want a "more-tested" implementation, how would you feel about using OpenBSD's arc4random_uniform implementation (http://cvsweb.openbsd.org/cgi-bin/cvsweb/~checkout~/src/lib/libc/crypt/arc4random_uniform.c?rev=1.1&content-type=text/plain)? It's BSD licensed and a super simple uniform distribution.

[jfb]

lib/Support/RandomNumberGenerator.cpp

69

I'd make sure it's initialized first :-p

But sure, as long as the implementation is license-compatible and well tested then that sounds acceptable.

[rinon]

• Replace uniform random implementation with OpenBSD's

[rinon]

lib/Support/RandomNumberGenerator.cpp

56

There is precedent for using OpenBSD libc code in LLVM: see lib/Support/regstrlcpy.c.

[joerg]

Please don't mix in completely unrelated changes to the support library. Start a separate review for those.

[jfb]

Is there interest in moving program diversification efforts forward, or should we close this work and rely on others to take it on?

[rinon]

If there's no external interest that I am unaware of, I think we should close this. I've still been working in this space. However due to deployment constraints, load-time rather than compile-time diversity is far more practical and interesting to everyone I've talked to. Fuzz testing micro-architectures may still be an exception to this, but I don't know of anyone who wants to use these type of features for that currently.

That said, if anyone does still want this, I'm happening to fix up and modernize these patches.

include/llvm/CodeGen/CommandFlags.h

cl::opt<bool> DataSections("data-sections",
                            cl::desc("Emit data into separate sections"),
                            cl::init(false));
 
 cl::opt<bool>
 FunctionSections("function-sections",
                  cl::desc("Emit functions into separate sections"),
                  cl::init(false));
 
+cl::opt<bool>
+NoopInsertion("noop-insertion",
+             cl::desc("Randomly add Noop instructions to create fine-grained "
+                      "code layout diversity."),
+             cl::init(false));
+
 cl::opt<llvm::JumpTable::JumpTableType>
 JTableType("jump-table-type",
           cl::desc("Choose the type of Jump-Instruction Table for jumptable."),
           cl::init(JumpTable::Single),
           cl::values(
               clEnumValN(JumpTable::Single, "single",
                          "Create a single table for all jumptable functions"),
               clEnumValN(JumpTable::Arity, "arity",
static inline TargetOptions InitTargetOptionsFromCodeGenFlags() {
   Options.GuaranteedTailCallOpt = EnableGuaranteedTailCallOpt;
   Options.DisableTailCalls = DisableTailCalls;
   Options.StackAlignmentOverride = OverrideStackAlignment;
   Options.TrapFuncName = TrapFuncName;
   Options.PositionIndependentExecutable = EnablePIE;
   Options.UseInitArray = !UseCtors;
   Options.DataSections = DataSections;
   Options.FunctionSections = FunctionSections;
+  Options.NoopInsertion = NoopInsertion;
 
   Options.MCOptions = InitMCTargetOptionsFromFlags();
   Options.JTType = JTableType;
   Options.FCFI = FCFI;
   Options.CFIType = CFIType;
   Options.CFIEnforcing = CFIEnforcing;
   Options.CFIFuncName = CFIFuncName;
 
   Options.ThreadModel = TMModel;
 
   return Options;
 }
 
 #endif

include/llvm/CodeGen/NoopInsertion.h

+//===-- NoopInsertion.h - Noop Insertion ------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass adds fine-grained diversity by displacing code using randomly
+// placed (optionally target supplied) Noop instructions.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_NOOPINSERTION_H
+#define LLVM_CODEGEN_NOOPINSERTION_H
+
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include <random>
+
+namespace llvm {
+
+class RandomNumberGenerator;
+
+class NoopInsertion : public MachineFunctionPass {
+public:
+  static char ID;
+
+  NoopInsertion();
+
+private:
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  std::unique_ptr<RandomNumberGenerator> RNG;
+};
+}
+
+#endif // LLVM_CODEGEN_NOOPINSERTION_H

include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
   /// bundles (created earlier, e.g. during pre-RA scheduling).
   extern char &FinalizeMachineBundlesID;
 
   /// StackMapLiveness - This pass analyses the register live-out set of
   /// stackmap/patchpoint intrinsics and attaches the calculated information to
   /// the intrinsic for later emission to the StackMap.
   extern char &StackMapLivenessID;
 
+  /// NoopInsertion - This pass adds fine-grained diversity by displacing code
+  /// using randomly placed (optionally target supplied) Noop instructions.
+  extern char &NoopInsertionID;
+
   /// createJumpInstrTables - This pass creates jump-instruction tables.
   ModulePass *createJumpInstrTablesPass();
 
   /// createForwardControlFlowIntegrityPass - This pass adds control-flow
   /// integrity.
   ModulePass *createForwardControlFlowIntegrityPass();
 } // End llvm namespace
 

include/llvm/InitializePasses.h

 void initializeMemCpyOptPass(PassRegistry&);
 void initializeMemDepPrinterPass(PassRegistry&);
 void initializeMemoryDependenceAnalysisPass(PassRegistry&);
 void initializeMergedLoadStoreMotionPass(PassRegistry &);
 void initializeMetaRenamerPass(PassRegistry&);
 void initializeMergeFunctionsPass(PassRegistry&);
 void initializeModuleDebugInfoPrinterPass(PassRegistry&);
 void initializeNoAAPass(PassRegistry&);
+void initializeNoopInsertionPass(PassRegistry&);
 void initializeObjCARCAliasAnalysisPass(PassRegistry&);
 void initializeObjCARCAPElimPass(PassRegistry&);
 void initializeObjCARCExpandPass(PassRegistry&);
 void initializeObjCARCContractPass(PassRegistry&);
 void initializeObjCARCOptPass(PassRegistry&);
 void initializePAEvalPass(PassRegistry &);
 void initializeOptimizePHIsPass(PassRegistry&);
 void initializePartiallyInlineLibCallsPass(PassRegistry&);

include/llvm/Support/RandomNumberGenerator.h

 /// A random number generator.
 ///
 /// Instances of this class should not be shared across threads. The
 /// seed should be set by passing the -rng-seed=<uint64> option. Use
 /// Module::createRNG to create a new RNG instance for use with that
 /// module.
 class RandomNumberGenerator {
 public:
-  /// Returns a random number in the range [0, Max).
-  uint_fast64_t operator()();
+  typedef std::mt19937_64 RNG;
+  typedef RNG::result_type result_type;
+
+  /// Returns a random number in the range [0, RNG::max()).
+  result_type operator()();
+
+  /// Returns an unbiased random number in the range [0, Max). Max
+  /// must be <= RNG::max().
+  result_type operator()(result_type Max);
+
+  // Must define min and max to be compatible with URNG as used by
+  // std::uniform_*_distribution
+  static LLVM_CONSTEXPR result_type min() {
+    return RNG::min();
+  }
+  static LLVM_CONSTEXPR result_type max() {
+    return RNG::max();
+  }
 
 private:
   /// Seeds and salts the underlying RNG engine.
   ///
   /// This constructor should not be used directly. Instead use
   /// Module::createRNG to create a new RNG salted with the Module ID.
   RandomNumberGenerator(StringRef Salt);
 
   // 64-bit Mersenne Twister by Matsumoto and Nishimura, 2000
   // http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine
   // This RNG is deterministically portable across C++11
   // implementations.
-  std::mt19937_64 Generator;
+  RNG Generator;
 
   // Noncopyable.
   RandomNumberGenerator(const RandomNumberGenerator &other)
       LLVM_DELETED_FUNCTION;
   RandomNumberGenerator &
   operator=(const RandomNumberGenerator &other) LLVM_DELETED_FUNCTION;
 
   friend class Module;
 };
 }
 
 #endif

include/llvm/Target/TargetInstrInfo.h

 class LiveVariables;
 class MCAsmInfo;
 class MachineMemOperand;
 class MachineRegisterInfo;
 class MDNode;
 class MCInst;
 struct MCSchedModel;
 class MCSymbolRefExpr;
+class RandomNumberGenerator;
 class SDNode;
 class ScheduleHazardRecognizer;
 class SelectionDAG;
 class ScheduleDAG;
 class TargetRegisterClass;
 class TargetRegisterInfo;
 class BranchProbability;
 class TargetSubtargetInfo;
bool ReverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const {
     return true;
   }
 
   /// insertNoop - Insert a noop into the instruction stream at the specified
   /// point.
   virtual void insertNoop(MachineBasicBlock &MBB,
                           MachineBasicBlock::iterator MI) const;
 
+  /// insertNoop - Insert a type of noop into the instruction stream at the
+  /// specified point to introduce fine-grained diversity. A target may randomly
+  /// choose from a pool of valid noops using the provided RNG.
+  virtual void insertNoop(MachineBasicBlock &MBB,
+                          MachineBasicBlock::iterator MI,
+                          RandomNumberGenerator&) const {
+    insertNoop(MBB, MI);
+  }
 
   /// Return the noop instruction to use for a noop.
   virtual void getNoopForMachoTarget(MCInst &NopInst) const;
 
 
   /// isPredicated - Returns true if the instruction is already predicated.
   ///
   virtual bool isPredicated(const MachineInstr *MI) const {

include/llvm/Target/TargetOptions.h

TargetOptions()
           NoInfsFPMath(false), NoNaNsFPMath(false),
           HonorSignDependentRoundingFPMathOption(false), UseSoftFloat(false),
           NoZerosInBSS(false), JITEmitDebugInfo(false),
           JITEmitDebugInfoToDisk(false), GuaranteedTailCallOpt(false),
           DisableTailCalls(false), StackAlignmentOverride(0),
           EnableFastISel(false), PositionIndependentExecutable(false),
           UseInitArray(false), DisableIntegratedAS(false),
           CompressDebugSections(false), FunctionSections(false),
-          DataSections(false), TrapUnreachable(false), TrapFuncName(),
-          FloatABIType(FloatABI::Default),
-          AllowFPOpFusion(FPOpFusion::Standard), JTType(JumpTable::Single),
-          FCFI(false), ThreadModel(ThreadModel::POSIX),
-          CFIType(CFIntegrity::Sub), CFIEnforcing(false), CFIFuncName() {}
+          DataSections(false), NoopInsertion(false),
+          TrapUnreachable(false), TrapFuncName(),
+          FloatABIType(FloatABI::Default), AllowFPOpFusion(FPOpFusion::Standard),
+          JTType(JumpTable::Single), FCFI(false),
+          ThreadModel(ThreadModel::POSIX), CFIType(CFIntegrity::Sub),
+          CFIEnforcing(false), CFIFuncName() {}
 
     /// PrintMachineCode - This flag is enabled when the -print-machineinstrs
     /// option is specified on the command line, and should enable debugging
     /// output from the code generator.
     unsigned PrintMachineCode : 1;
 
     /// NoFramePointerElim - This flag is enabled when the -disable-fp-elim is
     /// specified on the command line.  If the target supports the frame pointer
public:
     unsigned CompressDebugSections : 1;
 
     /// Emit functions into separate sections.
     unsigned FunctionSections : 1;
 
     /// Emit data into separate sections.
     unsigned DataSections : 1;
 
+    /// Randomly insert noop instructions to create fine-grained code
+    /// layout diversity.
+    unsigned NoopInsertion : 1;
+
     /// Emit target-specific trap instruction for 'unreachable' IR instructions.
     unsigned TrapUnreachable : 1;
 
     /// getTrapFunctionName - If this returns a non-empty string, this means
     /// isel should lower Intrinsic::trap to a call to the specified function
     /// name instead of an ISD::TRAP node.
     std::string TrapFuncName;
     StringRef getTrapFunctionName() const;

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   MachinePostDominators.cpp
   MachineRegisterInfo.cpp
   MachineRegionInfo.cpp
   MachineSSAUpdater.cpp
   MachineScheduler.cpp
   MachineSink.cpp
   MachineTraceMetrics.cpp
   MachineVerifier.cpp
+  NoopInsertion.cpp
   OcamlGC.cpp
   OptimizePHIs.cpp
   PHIElimination.cpp
   PHIEliminationUtils.cpp
   Passes.cpp
   PeepholeOptimizer.cpp
   PostRASchedulerList.cpp
   ProcessImplicitDefs.cpp

lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeMachineDominatorTreePass(Registry);
   initializeMachinePostDominatorTreePass(Registry);
   initializeMachineLICMPass(Registry);
   initializeMachineLoopInfoPass(Registry);
   initializeMachineModuleInfoPass(Registry);
   initializeMachineSchedulerPass(Registry);
   initializeMachineSinkingPass(Registry);
   initializeMachineVerifierPassPass(Registry);
+  initializeNoopInsertionPass(Registry);
   initializeOptimizePHIsPass(Registry);
   initializePHIEliminationPass(Registry);
   initializePeepholeOptimizerPass(Registry);
   initializePostMachineSchedulerPass(Registry);
   initializePostRASchedulerPass(Registry);
   initializeProcessImplicitDefsPass(Registry);
   initializePEIPass(Registry);
   initializeRegisterCoalescerPass(Registry);

lib/CodeGen/NoopInsertion.cpp

+//===- NoopInsertion.cpp - Noop Insertion ---------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass adds fine-grained diversity by displacing code using randomly
+// placed (optionally target supplied) Noop instructions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/NoopInsertion.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/RandomNumberGenerator.h"
+#include "llvm/Target/TargetInstrInfo.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "noop-insertion"
+
+static cl::opt<unsigned> NoopInsertionPercentage(
+    "noop-insertion-percentage",
+    cl::desc("Percentage of instructions that have Noops prepended"),
+    cl::init(25)); // Default is a good balance between entropy and
+                   // performance impact
+
+static cl::opt<unsigned> MaxNoopsPerInstruction(
+    "max-noops-per-instruction",
+    llvm::cl::desc("Maximum number of Noops per instruction"),
+    llvm::cl::init(1));
+
+STATISTIC(InsertedNoops,
+          "Total number of noop type instructions inserted for diversity");
+
+char NoopInsertion::ID = 0;
+char &llvm::NoopInsertionID = NoopInsertion::ID;
+INITIALIZE_PASS(NoopInsertion, "noop-insertion",
+                "Noop Insertion for fine-grained code randomization", false,
+                false)
+
+NoopInsertion::NoopInsertion() : MachineFunctionPass(ID) {
+  initializeNoopInsertionPass(*PassRegistry::getPassRegistry());
+
+  // clamp percentage to 100
+  if (NoopInsertionPercentage > 100)
+    NoopInsertionPercentage = 100;
+}
+
+void NoopInsertion::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesCFG();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+bool NoopInsertion::runOnMachineFunction(MachineFunction &Fn) {
+  // The RNG must be initialized on first use so we have a Module to
+  // construct it from
+  if (!RNG)
+    RNG.reset(Fn.getFunction()->getParent()->createRNG(this));
+
+  const TargetInstrInfo *TII = Fn.getSubtarget().getInstrInfo();
+
+  unsigned FnInsertedNoopCount = 0;
+
+  for (auto &BB : Fn) {
+    MachineBasicBlock::iterator FirstTerm = BB.getFirstTerminator();
+
+    for (MachineBasicBlock::iterator I = BB.begin(), E = BB.end(); I != E;
+         ++I) {
+      if (I->isPseudo())
+        continue;
+
+      // Insert random number of Noop-like instructions.
+      for (unsigned i = 0; i < MaxNoopsPerInstruction; i++) {
+        if ((*RNG)(100) >= NoopInsertionPercentage)
+          continue;
+
+        TII->insertNoop(BB, I, *RNG);
+
+        ++FnInsertedNoopCount;
+      }
+
+      if (I == FirstTerm)
+        break;
+    }
+  }
+
+  InsertedNoops += FnInsertedNoopCount;
+
+  return FnInsertedNoopCount > 0;
+}

lib/CodeGen/Passes.cpp

void TargetPassConfig::addMachinePasses() {
   }
 
   // GC
   if (addGCPasses()) {
     if (PrintGCInfo)
       addPass(createGCInfoPrinter(dbgs()), false, false);
   }
 
+  if (TM->Options.NoopInsertion)
+    addPass(&NoopInsertionID);
+
   // Basic block placement.
   if (getOptLevel() != CodeGenOpt::None)
     addBlockPlacement();
 
   addPreEmitPass();
 
   addPass(&StackMapLivenessID, false);
 

lib/Support/RandomNumberGenerator.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/RandomNumberGenerator.h"
 
 using namespace llvm;
 
 // Tracking BUG: 19665
 // http://llvm.org/bugs/show_bug.cgi?id=19665
 //
-// Do not change to cl::opt<uint64_t> since this silently breaks argument parsing.
+// Do not change to cl::opt<uint64_t> since this silently breaks argument
+// parsing.
 static cl::opt<unsigned long long>
     Seed("rng-seed", cl::value_desc("seed"),
          cl::desc("Seed for the random number generator"), cl::init(0));
 
 RandomNumberGenerator::RandomNumberGenerator(StringRef Salt) {
-  DEBUG(
-    if (Seed == 0)
-      dbgs() << "Warning! Using unseeded random number generator.\n"
-  );
+  DEBUG(if (Seed == 0) dbgs()
+        << "Warning! Using unseeded random number generator.\n");
 
   // Combine seed and salts using std::seed_seq.
   // Data: Seed-low, Seed-high, Salt
   // Note: std::seed_seq can only store 32-bit values, even though we
   // are using a 64-bit RNG. This isn't a problem since the Mersenne
   // twister constructor copies these correctly into its initial state.
   std::vector<uint32_t> Data;
   Data.reserve(2 + Salt.size());
   Data.push_back(Seed);
   Data.push_back(Seed >> 32);
 
   std::copy(Salt.begin(), Salt.end(), Data.end());
 
   std::seed_seq SeedSeq(Data.begin(), Data.end());
   Generator.seed(SeedSeq);
 }
 
-uint_fast64_t RandomNumberGenerator::operator()() {
+RandomNumberGenerator::result_type RandomNumberGenerator::operator()() {
   return Generator();
 }
+
+// This function is derived from OpenBSD's libc, original license
+// follows:
+//
+// Copyright (c) 2008, Damien Miller <[e-mail]>
+//
+// Permission to use, copy, modify, and distribute this software for any
+// purpose with or without fee is hereby granted, provided that the above
+// copyright notice and this permission notice appear in all copies.
+//
+// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+// ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+// ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+// OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+
+// Calculate a uniformly distributed random number less than upper_bound
+// avoiding "modulo bias".
+//
+// Uniformity is achieved by generating new random numbers until the one
+// returned is outside the range [0, 2**32 % upper_bound).  This
+// guarantees the selected random number will be inside
+// [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
+// after reduction modulo upper_bound.
+RandomNumberGenerator::result_type RandomNumberGenerator::
+operator()(result_type upper_bound) {
+  result_type r, min;
+
+  if (upper_bound < 2)
+    return 0;
+
+  /* 2**32 % x == (2**32 - x) % x */
+  min = -upper_bound % upper_bound;
+
+  /*
+   * This could theoretically loop forever but each retry has
+   * p > 0.5 (worst case, usually far better) of selecting a
+   * number inside the range we need, so it should rarely need
+   * to re-roll.
+   */
+  for (;;) {
+    r = Generator();
+    if (r >= min)
+      break;
+  }
+
+  return r % upper_bound;
+}

lib/Target/X86/X86InstrInfo.h

public:
   /// have already been scheduled after Load1.
   bool shouldScheduleLoadsNear(SDNode *Load1, SDNode *Load2,
                                int64_t Offset1, int64_t Offset2,
                                unsigned NumLoads) const override;
 
   bool shouldScheduleAdjacent(MachineInstr* First,
                               MachineInstr *Second) const override;
 
+  void insertNoop(MachineBasicBlock &MBB,
+                  MachineBasicBlock::iterator MI) const override;
+
+  void insertNoop(MachineBasicBlock &MBB,
+                  MachineBasicBlock::iterator MI,
+                  RandomNumberGenerator &RNG) const override;
+
   void getNoopForMachoTarget(MCInst &NopInst) const override;
 
   bool
   ReverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const override;
 
   /// isSafeToMoveRegClassDefs - Return true if it's safe to move a machine
   /// instruction that defines the specified register class.
   bool isSafeToMoveRegClassDefs(const TargetRegisterClass *RC) const override;

lib/Target/X86/X86InstrInfo.cpp

 #include "llvm/IR/Function.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetOptions.h"
 #include <limits>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "x86-instr-info"
 
if (!table) { // try the other table
     assert((Subtarget.hasAVX2() || Domain < 3) &&
            "256-bit vector operations only available in AVX2");
     table = lookupAVX2(MI->getOpcode(), dom);
   }
   assert(table && "Cannot change domain");
   MI->setDesc(get(table[Domain-1]));
 }
 
+/// insertNoop - Insert a noop into the instruction stream at the specified
+/// point.
+void X86InstrInfo::insertNoop(MachineBasicBlock &MBB,
+                              MachineBasicBlock::iterator MI) const {
+  DebugLoc DL;
+  BuildMI(MBB, MI, DL, get(X86::NOOP));
+}
+
+/// insertNoop - Insert a randomly chosen type of noop into the instruction
+/// stream at the specified point to introduce fine-grained diversity.
+void X86InstrInfo::insertNoop(MachineBasicBlock &MBB,
+                              MachineBasicBlock::iterator MI,
+                              RandomNumberGenerator &RNG) const {
+  // This set of Noop instructions was carefully chosen so that
+  // misaligned parses of these instructions do not introduce new,
+  // useful ROP gadgets. The ASM instructions noted are for misaligned
+  // parses of the noop in 32 and 64 bits.
+  enum {
+    NOP,    // 90
+    MOV_BP, // 89 ed, 48 89 ed -- IN EAX, IN AL (privileged)
+    MOV_SP, // 89 e4, 48 89 e4 -- IN AL, IN EAX (privileged)
+    LEA_SI, // 8d 36, 48 8d 36 -- SS segment override, NULL
+            // prefix (does not add new gadget)
+    LEA_DI, // 8d 3f, 48 8d 3f -- AAS (bcd->hex), invalid
+    MAX_NOPS
+  };
+
+  static const unsigned NopRegs[MAX_NOPS][2] = {
+      {0, 0},
+      {X86::EBP, X86::RBP},
+      {X86::ESP, X86::RSP},
+      {X86::ESI, X86::RSI},
+      {X86::EDI, X86::RDI},
+  };
+
+  unsigned Type = RNG(MAX_NOPS);
+
+  DebugLoc DL;
+  bool is64Bit = Subtarget.is64Bit();
+  unsigned Reg = NopRegs[Type][is64Bit];
+
+  switch (Type) {
+  case NOP:
+    BuildMI(MBB, MI, DL, get(X86::NOOP));
+    break;
+  case MOV_BP:
+  case MOV_SP:
+    copyPhysReg(MBB, MI, DL, Reg, Reg, false);
+    break;
+  case LEA_SI:
+  case LEA_DI: {
+    unsigned opc = is64Bit ? X86::LEA64r : X86::LEA32r;
+    addRegOffset(BuildMI(MBB, MI, DL, get(opc), Reg), Reg, false, 0);
+    break;
+  }
+  }
+}
+
 /// getNoopForMachoTarget - Return the noop instruction to use for a noop.
 void X86InstrInfo::getNoopForMachoTarget(MCInst &NopInst) const {
   NopInst.setOpcode(X86::NOOP);
 }
 
 // This code must remain in sync with getJumpInstrTableEntryBound in this class!
 // In particular, getJumpInstrTableEntryBound must always return an upper bound
 // on the encoding lengths of the instructions generated by

test/CodeGen/Mips/noop-insert.ll

+; RUN: llc < %s -march=mips -noop-insertion | FileCheck %s
+; RUN: llc < %s -march=mips -noop-insertion -rng-seed=10 | FileCheck %s --check-prefix=SEED1
+; RUN: llc < %s -march=mips -noop-insertion -noop-insertion-percentage=100 | FileCheck %s --check-prefix=100PERCENT
+
+; This test case checks that NOOPs are inserted correctly for MIPS.
+
+; CHECK: mul
+; CHECK-NEXT: nop
+; CHECK-NEXT: jr
+
+; SEED1: mul
+; SEED1-NEXT: jr
+
+; 100PERCENT: nop
+; 100PERCENT-NEXT: mul
+; 100PERCENT-NEXT: nop
+; 100PERCENT-NEXT: jr
+
+define i32 @test1(i32 %x, i32 %y, i32 %z) {
+entry:
+    %tmp = mul i32 %x, %y
+    %tmp2 = add i32 %tmp, %z
+    ret i32 %tmp2
+}

test/CodeGen/PowerPC/noop-insert.ll

+; RUN: llc < %s -march=ppc32 -noop-insertion | FileCheck %s
+; RUN: llc < %s -march=ppc32 -noop-insertion -rng-seed=10 | FileCheck %s --check-prefix=SEED1
+; RUN: llc < %s -march=ppc32 -noop-insertion -noop-insertion-percentage=100 | FileCheck %s --check-prefix=100PERCENT
+
+; This test case checks that NOOPs are inserted correctly for PowerPC.
+
+; CHECK: mullw
+; CHECK-NEXT: nop
+; CHECK-NEXT: add
+; CHECK-NEXT: blr
+
+; SEED1: mullw
+; SEED1-NEXT: add
+; SEED1-NEXT: blr
+
+; 100PERCENT: nop
+; 100PERCENT-NEXT: mullw
+; 100PERCENT-NEXT: nop
+; 100PERCENT-NEXT: add
+; 100PERCENT-NEXT: nop
+; 100PERCENT-NEXT: blr
+
+define i32 @test1(i32 %x, i32 %y, i32 %z) {
+entry:
+    %tmp = mul i32 %x, %y
+    %tmp2 = add i32 %tmp, %z
+    ret i32 %tmp2
+}

test/CodeGen/X86/noop-insert-percentage.ll

+; RUN: llc < %s -mtriple=x86_64-linux -rng-seed=5 -noop-insertion -noop-insertion-percentage=10 \
+; RUN:     | FileCheck %s --check-prefix=PERCENT10
+; RUN: llc < %s -mtriple=x86_64-linux -rng-seed=5 -noop-insertion -noop-insertion-percentage=50 \
+; RUN:     | FileCheck %s --check-prefix=PERCENT50
+; RUN: llc < %s -mtriple=x86_64-linux -rng-seed=5 -noop-insertion -noop-insertion-percentage=100 \
+; RUN:     | FileCheck %s --check-prefix=PERCENT100
+
+; RUN: llc < %s -march=x86 -rng-seed=5 -noop-insertion -noop-insertion-percentage=100 \
+; RUN:     | FileCheck %s --check-prefix=X86-PERCENT100
+
+; This test case tests NOOP insertion at varying percentage levels.
+
+define i32 @test(i32 %x, i32 %y, i32 %z) {
+entry:
+    %t1 = add i32 %x, %y
+    %t2 = mul i32 %t1, %z
+    %t3 = add i32 %t2, %x
+    %t4 = mul i32 %t3, %z
+    %t5 = add i32 %t4, %x
+    %t6 = mul i32 %t5, %z
+    %t7 = add i32 %t6, %x
+    %t8 = mul i32 %t7, %z
+    %t9 = add i32 %t8, %x
+    %t10 = mul i32 %t9, %z
+    %t11 = add i32 %t10, %x
+    ret i32 %t11
+}
+
+; PERCENT10: leaq   (%rsi), %rsi
+; PERCENT10: retq
+
+; PERCENT50: movq   %rbp, %rbp
+; PERCENT50: nop
+; PERCENT50: leaq   (%rsi), %rsi
+; PERCENT50: leaq   (%rdi), %rdi
+; PERCENT50: movq   %rbp, %rbp
+; PERCENT50: movq   %rsp, %rsp
+; PERCENT50: retq
+
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: movq  %rsp, %rsp
+; PERCENT100: movq  %rsp, %rsp
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: leaq  (%rsi), %rsi
+; PERCENT100: leaq  (%rdi), %rdi
+; PERCENT100: movq  %rbp, %rbp
+; PERCENT100: movq  %rsp, %rsp
+; PERCENT100: leaq  (%rsi), %rsi
+; PERCENT100: nop
+; PERCENT100: leaq  (%rsi), %rsi
+; PERCENT100: retq
+
+
+; X86-PERCENT100: leal  (%edi), %edi
+; X86-PERCENT100: leal  (%edi), %edi
+; X86-PERCENT100: movl  %esp, %esp
+; X86-PERCENT100: movl  %esp, %esp
+; X86-PERCENT100: leal  (%edi), %edi
+; X86-PERCENT100: leal  (%esi), %esi
+; X86-PERCENT100: leal  (%edi), %edi
+; X86-PERCENT100: movl  %ebp, %ebp
+; X86-PERCENT100: movl  %esp, %esp
+; X86-PERCENT100: leal  (%esi), %esi
+; X86-PERCENT100: nop
+; X86-PERCENT100: leal  (%esi), %esi
+; X86-PERCENT100: leal  (%esi), %esi
+; X86-PERCENT100: movl  %ebp, %ebp
+; X86-PERCENT100: movl  %esp, %esp
+; X86-PERCENT100: retl

test/CodeGen/X86/noop-insert.ll

+; RUN: llc < %s -mtriple=x86_64-linux -noop-insertion | FileCheck %s
+; RUN: llc < %s -mtriple=x86_64-linux -noop-insertion -rng-seed=1 | FileCheck %s --check-prefix=SEED1
+; RUN: llc < %s -mtriple=x86_64-linux -noop-insertion -rng-seed=20 | FileCheck %s --check-prefix=SEED2
+; RUN: llc < %s -mtriple=x86_64-linux -noop-insertion -rng-seed=500 | FileCheck %s --check-prefix=SEED3
+
+; RUN: llc < %s -march=x86 -noop-insertion | FileCheck %s --check-prefix=x86_32
+
+; This test case checks that NOOPs are inserted, and that the RNG seed
+; affects both the placement (position of imull) and choice of these NOOPs.
+
+; CHECK: imull
+; CHECK-NEXT: leaq (%rsi), %rsi
+; CHECK-NEXT: leal
+; CHECK-NEXT: retq
+
+; SEED1: imull
+; SEED1-NEXT: movq %rbp, %rbp
+; SEED1-NEXT: leal
+; SEED1-NEXT: retq
+
+; SEED2: imull
+; SEED2-NEXT: movq %rsp, %rsp
+; SEED2-NEXT: leal
+; SEED2-NEXT: retq
+
+; SEED3: imull
+; SEED3-NEXT: leal
+; SEED3-NEXT: movq %rsp, %rsp
+; SEED3-NEXT: retq
+
+; The operand of the following is used to distinguish from a movl NOOP
+; x86_32: movl 4(%esp),
+; x86_32-NEXT: leal (%esi), %esi
+; x86_32-NEXT: imull
+; x86_32-NEXT: addl
+; x86_32-NEXT: leal (%edi), %edi
+; x86_32-NEXT: retl
+
+define i32 @test1(i32 %x, i32 %y, i32 %z) {
+entry:
+    %tmp = mul i32 %x, %y
+    %tmp2 = add i32 %tmp, %z
+    ret i32 %tmp2
+}