Index: include/llvm/CodeGen/CommandFlags.h
===================================================================
--- include/llvm/CodeGen/CommandFlags.h
+++ include/llvm/CodeGen/CommandFlags.h
@@ -208,6 +208,12 @@
cl::value_desc("pass-name"),
cl::init(""));
+cl::opt<bool>
+NOPInsertion("nop-insertion",
+ cl::desc("Randomly add NOPs."),
+ cl::init(false));
+
+
// Common utility function tightly tied to the options listed here. Initializes
// a TargetOptions object with CodeGen flags and returns it.
static inline TargetOptions InitTargetOptionsFromCodeGenFlags() {
@@ -231,6 +237,7 @@
Options.PositionIndependentExecutable = EnablePIE;
Options.EnableSegmentedStacks = SegmentedStacks;
Options.UseInitArray = UseInitArray;
+ Options.NOPInsertion = NOPInsertion;
return Options;
}
Index: include/llvm/Support/RandomNumberGenerator.h
===================================================================
--- /dev/null
+++ include/llvm/Support/RandomNumberGenerator.h
@@ -0,0 +1,54 @@
+//==- llvm/Support/RandomNumberGenerator.h - RNG for diversity ---*- C++ -*-==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines an abstraction for random number generation (RNG).
+// Note that the current implementation is not cryptographically secure
+// as it uses the C++11 <random> facilities.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_
+#define LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_
+
+#include "llvm/ADT/StringRef.h"
+#include <string>
+#include <random>
+
+namespace llvm {
+
+class RandomNumberGenerator {
+public:
+ /// \brief Add additional personalization data to the RNG seed.
+ ///
+ /// This function should be used to add deterministic command line
+ /// argument data to the RNG initialization, resulting in a
+ /// different stream of random numbers for each invocation during a
+ /// build. The input to this function should be unique per
+ /// compilation unit.
+ static void SetSalt(const StringRef &Salt);
+
+ static RandomNumberGenerator *Get();
+
+ /// \brief Returns a random number in the range [0, Max).
+ uint64_t Random(uint64_t Max);
+
+private:
+ std::default_random_engine generator;
+
+ void Seed(StringRef Salt, uint64_t Seed);
+
+ RandomNumberGenerator();
+ // Noncopyable.
+ RandomNumberGenerator(const RandomNumberGenerator &other) = delete;
+ RandomNumberGenerator &
+ operator=(const RandomNumberGenerator &other) = delete;
+};
+}
+
+#endif
Index: include/llvm/Target/TargetOptions.h
===================================================================
--- include/llvm/Target/TargetOptions.h
+++ include/llvm/Target/TargetOptions.h
@@ -49,7 +49,7 @@
JITEmitDebugInfoToDisk(false), GuaranteedTailCallOpt(false),
DisableTailCalls(false), StackAlignmentOverride(0),
EnableFastISel(false), PositionIndependentExecutable(false),
- EnableSegmentedStacks(false), UseInitArray(false),
+ EnableSegmentedStacks(false), NOPInsertion(false), UseInitArray(false),
DisableIntegratedAS(false), CompressDebugSections(false),
TrapFuncName(""), FloatABIType(FloatABI::Default),
AllowFPOpFusion(FPOpFusion::Standard) {}
@@ -154,6 +154,9 @@
unsigned EnableSegmentedStacks : 1;
+ /// Attempt to insert NOPs
+ unsigned NOPInsertion : 1;
+
/// UseInitArray - Use .init_array instead of .ctors for static
/// constructors.
unsigned UseInitArray : 1;
Index: lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
===================================================================
--- lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -28,6 +28,7 @@
#include "llvm/IR/InlineAsm.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/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
@@ -103,6 +104,17 @@
"sched-avg-ipc", cl::Hidden, cl::init(1),
cl::desc("Average inst/cycle whan no target itinerary exists."));
+static cl::opt<bool> RandomizeSchedule(
+ "sched-randomize",
+ cl::desc("Enable randomization of scheduling"),
+ cl::init(false));
+
+static cl::opt<unsigned> SchedRandPercentage(
+ "sched-randomize-percentage",
+ cl::desc("Percentage of instructions where schedule is randomized"),
+ cl::init(50));
+
+
namespace {
//===----------------------------------------------------------------------===//
/// ScheduleDAGRRList - The actual register reduction list scheduler
@@ -1757,6 +1769,16 @@
class RegReductionPriorityQueue : public RegReductionPQBase {
SF Picker;
+ static SUnit *popRandom(std::vector<SUnit*> &Q) {
+ RandomNumberGenerator *randGen = RandomNumberGenerator::Get();
+ size_t randIndex = randGen->Random(Q.size());
+ SUnit *V = Q[randIndex];
+ if (randIndex < Q.size() - 1)
+ std::swap(Q[randIndex], Q.back());
+ Q.pop_back();
+ return V;
+ }
+
public:
RegReductionPriorityQueue(MachineFunction &mf,
bool tracksrp,
@@ -1777,7 +1799,18 @@
SUnit *pop() override {
if (Queue.empty()) return NULL;
- SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
+ SUnit *V;
+ if (RandomizeSchedule) {
+ RandomNumberGenerator *randGen = RandomNumberGenerator::Get();
+ unsigned int Roll = randGen->Random(100);
+ if (Roll < SchedRandPercentage) {
+ V = popRandom(Queue);
+ } else {
+ V = popFromQueue(Queue, Picker, scheduleDAG);
+ }
+ } else {
+ V = popFromQueue(Queue, Picker, scheduleDAG);
+ }
V->NodeQueueId = 0;
return V;
}
Index: lib/LTO/LTOCodeGenerator.cpp
===================================================================
--- lib/LTO/LTOCodeGenerator.cpp
+++ lib/LTO/LTOCodeGenerator.cpp
@@ -142,6 +142,7 @@
Options.PositionIndependentExecutable = options.PositionIndependentExecutable;
Options.EnableSegmentedStacks = options.EnableSegmentedStacks;
Options.UseInitArray = options.UseInitArray;
+ Options.NOPInsertion = options.NOPInsertion;
}
void LTOCodeGenerator::setDebugInfo(lto_debug_model debug) {
Index: lib/Support/CMakeLists.txt
===================================================================
--- lib/Support/CMakeLists.txt
+++ lib/Support/CMakeLists.txt
@@ -40,6 +40,7 @@
MD5.cpp
PluginLoader.cpp
PrettyStackTrace.cpp
+ RandomNumberGenerator.cpp
Regex.cpp
SmallPtrSet.cpp
SmallVector.cpp
Index: lib/Support/RandomNumberGenerator.cpp
===================================================================
--- /dev/null
+++ lib/Support/RandomNumberGenerator.cpp
@@ -0,0 +1,87 @@
+//===-- RandomNumberGenerator.cpp - Implement RNG class -------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements random number generation (RNG).
+// The current implementation is NOT cryptographically secure as it uses
+// the C++11 <random> facilities.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "rng"
+#include "llvm/Support/RandomNumberGenerator.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/ManagedStatic.h"
+#include "llvm/Support/ThreadLocal.h"
+
+using namespace llvm;
+
+// Initialized once, then only read by threads, so no locking required.
+static std::string SaltData;
+
+// Do not change to cl::opt<uint64_t> since this silently breaks argument parsing.
+static cl::opt<unsigned long long>
+RandomSeed("rng-seed", cl::value_desc("seed"),
+ cl::desc("Seed for the random number generator"), cl::init(0));
+
+static cl::opt<std::string, true>
+SaltDataOpt("entropy-data",
+ cl::desc("Entropy data for the RNG (testing only, should be set "
+ "by command line options"),
+ cl::Hidden, cl::location(SaltData));
+
+static ManagedStatic<sys::ThreadLocal<const RandomNumberGenerator> > Instance;
+
+void RandomNumberGenerator::SetSalt(const StringRef &Salt) {
+ SaltData = Salt;
+}
+
+RandomNumberGenerator *RandomNumberGenerator::Get() {
+ RandomNumberGenerator *RNG =
+ const_cast<RandomNumberGenerator *>(Instance->get());
+
+ if (RNG == 0) {
+ RNG = new RandomNumberGenerator;
+ Instance->set(RNG);
+ }
+
+ return RNG;
+}
+
+// Note that every new RNG will produce the same stream of
+// pseudo-random numbers, unless SetSalt is called again.
+RandomNumberGenerator::RandomNumberGenerator() {
+ if (RandomSeed == 0 && SaltData.empty())
+ DEBUG(errs()
+ << "Warning! Using unseeded and unsalted random number generator\n");
+
+ Seed(SaltData, RandomSeed);
+}
+
+uint64_t RandomNumberGenerator::Random(uint64_t Max) {
+ std::uniform_int_distribution<uint64_t> distribution(0, Max - 1);
+ return distribution(generator);
+}
+
+void RandomNumberGenerator::Seed(StringRef Salt, uint64_t Seed) {
+ DEBUG(dbgs() << "Re-Seeding RNG from salt and seed\n");
+ DEBUG(dbgs() << "Salt: " << Salt << "\n");
+ DEBUG(dbgs() << "Seed: " << Seed << "\n");
+
+ // Sequence: Seed-low, Seed-high, Salt...
+ unsigned SeedSize = Salt.size() + 2;
+ unsigned Seeds[SeedSize];
+ Seeds[0] = Seed;
+ Seeds[1] = Seed >> 32;
+ for (unsigned i = 0; i < Salt.size(); ++i)
+ Seeds[2 + i] = Salt[i];
+
+ std::seed_seq SeedSeq(Seeds, Seeds + SeedSize);
+ generator.seed(SeedSeq);
+}
Index: lib/Target/X86/CMakeLists.txt
===================================================================
--- lib/Target/X86/CMakeLists.txt
+++ lib/Target/X86/CMakeLists.txt
@@ -13,6 +13,7 @@
add_public_tablegen_target(X86CommonTableGen)
set(sources
+ NOPInsertion.cpp
X86AsmPrinter.cpp
X86COFFMachineModuleInfo.cpp
X86CodeEmitter.cpp
Index: lib/Target/X86/NOPInsertion.cpp
===================================================================
--- /dev/null
+++ lib/Target/X86/NOPInsertion.cpp
@@ -0,0 +1,146 @@
+//===- NOPInsertion.cpp - Insert NOPs between instructions ----------------===//
+//
+// 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 NOPInsertion pass.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "nop-insertion"
+#include "X86InstrBuilder.h"
+#include "X86InstrInfo.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/RandomNumberGenerator.h"
+#include "llvm/Target/TargetInstrInfo.h"
+
+using namespace llvm;
+
+static cl::opt<unsigned>
+NOPInsertionPercentage(
+ "nop-insertion-percentage",
+ cl::desc("Percentage of instructions that have NOPs prepended"),
+ cl::init(50));
+
+static cl::opt<unsigned>
+MaxNOPsPerInstruction(
+ "max-nops-per-instruction",
+ llvm::cl::desc("Maximum number of NOPs per instruction"),
+ llvm::cl::init(1));
+
+
+STATISTIC(InsertedNOPs,
+ "Total number of noop type instructions inserted for diversity");
+
+namespace {
+class NOPInsertionPass : public MachineFunctionPass {
+
+ static char ID;
+
+ bool is64Bit;
+
+public:
+ NOPInsertionPass(bool is64Bit_) :
+ MachineFunctionPass(ID), is64Bit(is64Bit_) {
+ }
+
+ virtual bool runOnMachineFunction(MachineFunction &MF);
+
+ virtual const char *getPassName() const {
+ return "NOP insertion pass";
+ }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesCFG();
+ MachineFunctionPass::getAnalysisUsage(AU);
+ }
+};
+}
+
+char NOPInsertionPass::ID = 0;
+
+enum { NOP,
+ MOV_EBP, MOV_ESP,
+ LEA_ESI, LEA_EDI,
+ 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 },
+};
+
+bool NOPInsertionPass::runOnMachineFunction(MachineFunction &Fn) {
+ const TargetInstrInfo *TII = Fn.getTarget().getInstrInfo();
+ for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
+ MachineBasicBlock::iterator FirstTerm = BB->getFirstTerminator();
+ // Insert NOPs before instruction.
+ for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
+ MachineBasicBlock::iterator NextI = std::next(I);
+ if (I->isPseudo()) {
+ I = NextI;
+ continue;
+ }
+ // Insert random number of NOP-like instructions.
+ for (unsigned i = 0; i < MaxNOPsPerInstruction; i++) {
+ unsigned Roll = RandomNumberGenerator::Get()->Random(100);
+ if (Roll >= NOPInsertionPercentage)
+ continue;
+
+ unsigned NOPCode = RandomNumberGenerator::Get()->Random(MAX_NOPS);
+
+ MachineInstr *NewMI = NULL;
+ unsigned reg = nopRegs[NOPCode][is64Bit];
+ switch (NOPCode) {
+ case NOP:
+ NewMI = BuildMI(*BB, I, I->getDebugLoc(), TII->get(X86::NOOP));
+ break;
+ case MOV_EBP:
+ case MOV_ESP: {
+ unsigned opc = is64Bit ? X86::MOV64rr : X86::MOV32rr;
+ NewMI = BuildMI(*BB, I, I->getDebugLoc(), TII->get(opc), reg)
+ .addReg(reg);
+ break;
+ }
+
+ case LEA_ESI:
+ case LEA_EDI: {
+ unsigned opc = is64Bit ? X86::LEA64r : X86::LEA32r;
+ NewMI = addRegOffset(BuildMI(*BB, I, I->getDebugLoc(),
+ TII->get(opc), reg),
+ reg, false, 0);
+ break;
+ }
+ }
+
+ if (NewMI != NULL)
+ ++InsertedNOPs;
+ }
+ // Do not insert NOPs between terminators.
+ if (I == FirstTerm)
+ break;
+
+ I = NextI;
+ }
+ }
+ return true;
+}
+
+namespace llvm {
+ FunctionPass *createNOPInsertionPass(bool is64Bit) {
+ return new NOPInsertionPass(is64Bit);
+ }
+}
Index: lib/Target/X86/X86.h
===================================================================
--- lib/Target/X86/X86.h
+++ lib/Target/X86/X86.h
@@ -50,6 +50,10 @@
/// AVX and SSE.
FunctionPass *createX86IssueVZeroUpperPass();
+/// createNOPInsertionPass - This pass adds NOPs at random between
+/// instructions.
+FunctionPass *createNOPInsertionPass(bool is64Bit);
+
/// createX86CodeEmitterPass - Return a pass that emits the collected X86 code
/// to the specified MCE object.
FunctionPass *createX86JITCodeEmitterPass(X86TargetMachine &TM,
Index: lib/Target/X86/X86TargetMachine.cpp
===================================================================
--- lib/Target/X86/X86TargetMachine.cpp
+++ lib/Target/X86/X86TargetMachine.cpp
@@ -224,6 +224,11 @@
ShouldPrint = true;
}
+ if (TM->Options.NOPInsertion) {
+ addPass(createNOPInsertionPass(getX86Subtarget().is64Bit()));
+ ShouldPrint = true;
+ }
+
return ShouldPrint;
}
Index: test/CodeGen/X86/nop-insert-percentage.ll
===================================================================
--- /dev/null
+++ test/CodeGen/X86/nop-insert-percentage.ll
@@ -0,0 +1,47 @@
+; RUN: llc < %s -rng-seed=5 -nop-insertion -nop-insertion-percentage=10 \
+; RUN: | FileCheck %s --check-prefix=PERCENT10
+; RUN: llc < %s -rng-seed=5 -nop-insertion -nop-insertion-percentage=50 \
+; RUN: | FileCheck %s --check-prefix=PERCENT50
+; RUN: llc < %s -rng-seed=5 -nop-insertion -nop-insertion-percentage=100 \
+; RUN: | FileCheck %s --check-prefix=PERCENT100
+
+; This test case tests NOP 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
+
+; PERCENT50: movq %rbp, %rbp
+; PERCENT50: leaq (%rsi), %rsi
+; PERCENT50: movq %rbp, %rbp
+; PERCENT50: leaq (%rdi), %rdi
+; PERCENT50: movq %rsp, %rsp
+; PERCENT50: leaq (%rsi), %rsi
+; PERCENT50: leaq (%rdi), %rdi
+
+; PERCENT100: leaq (%rdi), %rdi
+; PERCENT100: movq %rbp, %rbp
+; PERCENT100: leaq (%rsi), %rsi
+; PERCENT100: movq %rbp, %rbp
+; PERCENT100: leaq (%rdi), %rdi
+; PERCENT100: movq %rsp, %rsp
+; PERCENT100: leaq (%rsi), %rsi
+; PERCENT100: leaq (%rsi), %rsi
+; PERCENT100: nop
+; PERCENT100: leaq (%rsi), %rsi
+; PERCENT100: movq %rsp, %rsp
+; PERCENT100: movq %rbp, %rbp
Index: test/CodeGen/X86/nop-insert.ll
===================================================================
--- /dev/null
+++ test/CodeGen/X86/nop-insert.ll
@@ -0,0 +1,44 @@
+; RUN: llc < %s -nop-insertion | FileCheck %s
+; RUN: llc < %s -nop-insertion -entropy-data="test" -rng-seed=1 | FileCheck %s --check-prefix=SEED1
+; RUN: llc < %s -nop-insertion -entropy-data="test" -rng-seed=25 | FileCheck %s --check-prefix=SEED2
+; RUN: llc < %s -nop-insertion -entropy-data="test" -rng-seed=1534 | FileCheck %s --check-prefix=SEED3
+; RUN: llc < %s -nop-insertion -entropy-data="different entropy" -rng-seed=1 | FileCheck %s --check-prefix=ENTROPY
+
+; This test case checks that NOPs are inserted, and that the RNG seed
+; affects both the placement (position of imull) and choice of these NOPs.
+
+; CHECK: movq %rsp, %rsp
+; CHECK: imull
+; CHECK: movq %rbp, %rbp
+; CHECK-NOT: leaq
+; CHECK-NOT: nop
+
+; SEED1: imull
+; SEED1: leaq (%rsi), %rsi
+; SEED1-NOT: movq
+; SEED1-NOT: nop
+
+; SEED2: movq %rbp, %rbp
+; SEED2: imull
+; SEED2: movq %rbp, %rbp
+; SEED2-NOT: leaq
+; SEED2-NOT: nop
+
+; SEED3: movq %rsp, %rsp
+; SEED3: imull
+; SEED3: movq %rsp, %rsp
+; SEED3-NOT: leaq
+; SEED3-NOT: nop
+
+; ENTROPY: imull
+; ENTROPY: nop
+; ENTROPY: nop
+; ENTROPY-NOT: leaq
+; ENTROPY-NOT: movq
+
+define i32 @test1(i32 %x, i32 %y, i32 %z) {
+entry:
+ %tmp = mul i32 %x, %y
+ %tmp2 = add i32 %tmp, %z
+ ret i32 %tmp2
+}
Index: test/CodeGen/X86/sched-rnd-test.ll
===================================================================
--- /dev/null
+++ test/CodeGen/X86/sched-rnd-test.ll
@@ -0,0 +1,36 @@
+; RUN: llc < %s -rng-seed=1 -sched-randomize -sched-randomize-percentage=100 | FileCheck %s --check-prefix=SEED1
+; RUN: llc < %s -rng-seed=5 -sched-randomize -sched-randomize-percentage=100 | FileCheck %s --check-prefix=SEED2
+; RUN: llc < %s -rng-seed=5 -sched-randomize -sched-randomize-percentage=50 | FileCheck %s --check-prefix=PERCENTAGE
+
+; This test case checks that the schedule randomization is changing
+; scheduling decisions, that different seeds result in different
+; schedules, and that the percentage alters the amount of
+; randomization
+
+define i32 @test(i32 %x, i32 %y, i32 %z) {
+entry:
+ %a = add i32 %x, %y
+ %b = add i32 %x, %z
+ %c = add i32 %y, %z
+ %d = mul i32 %a, %b
+ %e = mul i32 %d, %c
+ ret i32 %e
+}
+
+; SEED1: leal (%rdi,%rsi), %eax
+; SEED1-NEXT: addl %edx, %esi
+; SEED1-NEXT: addl %edx, %edi
+; SEED1-NEXT: imull %edi, %eax
+; SEED1-NEXT: imull %esi, %eax
+
+; SEED2: leal (%rdi,%rsi), %eax
+; SEED2-NEXT: addl %edx, %edi
+; SEED2-NEXT: imull %edi, %eax
+; SEED2-NEXT: addl %edx, %esi
+; SEED2-NEXT: imull %esi, %eax
+
+; PERCENTAGE: leal (%rdi,%rsi), %eax
+; PERCENTAGE: addl %edx, %esi
+; PERCENTAGE: addl %edx, %edi
+; PERCENTAGE: imull %edi, %eax
+; PERCENTAGE: imull %esi, %eax