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 +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 facilities. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_ +#define LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_ + +#include "llvm/ADT/StringRef.h" +#include +#include + +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 RandomizeSchedule( + "sched-randomize", + cl::desc("Enable randomization of scheduling"), + cl::init(false)); + +static cl::opt 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 &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 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 since this silently breaks argument parsing. +static cl::opt +RandomSeed("rng-seed", cl::value_desc("seed"), + cl::desc("Seed for the random number generator"), cl::init(0)); + +static cl::opt +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 > Instance; + +void RandomNumberGenerator::SetSalt(const StringRef &Salt) { + SaltData = Salt; +} + +RandomNumberGenerator *RandomNumberGenerator::Get() { + RandomNumberGenerator *RNG = + const_cast(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 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 +NOPInsertionPercentage( + "nop-insertion-percentage", + cl::desc("Percentage of instructions that have NOPs prepended"), + cl::init(50)); + +static cl::opt +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,49 @@ +; RUN: llc < %s -rng-seed=1 -nop-insertion -nop-insertion-percentage=10 \ +; RUN: | FileCheck %s --check-prefix=PERCENT10 +; RUN: llc < %s -rng-seed=1 -nop-insertion -nop-insertion-percentage=50 \ +; RUN: | FileCheck %s --check-prefix=PERCENT50 +; RUN: llc < %s -rng-seed=1 -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: movq %rbp, %rbp + +; PERCENT50: movq %rbp, %rbp +; PERCENT50: nop +; PERCENT50: leaq (%rdi), %rdi +; PERCENT50: leaq (%rsi), %rsi +; PERCENT50: leaq (%rsi), %rsi +; PERCENT50: leaq (%rsi), %rsi +; PERCENT50: leaq (%rdi), %rdi +; PERCENT50: nop +; PERCENT50: leaq (%rsi), %rsi + +; PERCENT100: movq %rbp, %rbp +; PERCENT100: nop +; PERCENT100: leaq (%rdi), %rdi +; PERCENT100: leaq (%rsi), %rsi +; PERCENT100: leaq (%rsi), %rsi +; PERCENT100: movq %rsp, %rsp +; PERCENT100: leaq (%rdi), %rdi +; PERCENT100: leaq (%rdi), %rdi +; PERCENT100: movq %rsp, %rsp +; PERCENT100: movq %rbp, %rbp +; PERCENT100: movq %rsp, %rsp +; PERCENT100: leaq (%rsi), %rsi Index: test/CodeGen/X86/nop-insert.ll =================================================================== --- /dev/null +++ test/CodeGen/X86/nop-insert.ll @@ -0,0 +1,34 @@ +; 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 and choice of these NOPs. + +; CHECK: leaq (%rdi), %rdi +; CHECK: movq %rsp, %rsp + +; SEED1: leaq (%rsi), %rsi +; SEED1-NOT: movq +; SEED1-NOT: nop + +; SEED2: nop +; SEED2-NOT: movq +; SEED2-NOT: leaq + +; SEED3-NOT: movq +; SEED3-NOT: nop +; SEED3-NOT: leaq + +; ENTROPY: movq %rsp, %rsp +; ENTROPY-NOT: nop +; ENTROPY-NOT: leaq + +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, %edi +; SEED1-NEXT: imull %edi, %eax +; SEED1-NEXT: addl %edx, %esi +; SEED1-NEXT: imull %esi, %eax + +; SEED2: leal (%rdi,%rdx), %ecx +; SEED2-NEXT: leal (%rdi,%rsi), %eax +; SEED2-NEXT: imull %ecx, %eax +; SEED2-NEXT: addl %edx, %esi +; SEED2-NEXT: imull %esi, %eax + +; PERCENTAGE: leal (%rdi,%rsi), %eax +; PERCENTAGE: addl %edx, %edi +; PERCENTAGE: addl %edx, %esi +; PERCENTAGE: imull %edi, %eax +; PERCENTAGE: imull %esi, %eax