Index: include/llvm/CodeGen/CommandFlags.h =================================================================== --- include/llvm/CodeGen/CommandFlags.h +++ include/llvm/CodeGen/CommandFlags.h @@ -210,4 +210,9 @@ cl::value_desc("pass-name"), cl::init("")); +cl::opt +NOPInsertion("nop-insertion", + cl::desc("Randomly add NOPs."), + cl::init(false)); + #endif Index: include/llvm/MC/MCRegisterInfo.h =================================================================== --- include/llvm/MC/MCRegisterInfo.h +++ include/llvm/MC/MCRegisterInfo.h @@ -18,6 +18,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/RandomNumberGenerator.h" #include namespace llvm { Index: include/llvm/Support/RandomNumberGenerator.h =================================================================== --- /dev/null +++ include/llvm/Support/RandomNumberGenerator.h @@ -0,0 +1,127 @@ +//==- 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 the crypto-secure Random Number Generator. This +// RNG is based on HMAC_DRBG with MD5 as the hash. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_ +#define LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_ + +#include "llvm/Config/config.h" +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/ManagedStatic.h" +#include "llvm/Support/ThreadLocal.h" +#include "llvm/Support/raw_ostream.h" +#include +#include + +namespace llvm { + +class StringRef; + +#define BLOCK_SIZE 16 // MD5 has a block size of 128 bits + +/// RandomNumberGenerator is a crypto-secure RNG which can be used to +/// generate randomness for security uses. The RNG is based on the +/// standard HMAC_DRBG with MD5 as the hash function. +class RandomNumberGenerator { +public: + /// Initialized by the frontend using SetSalt. Should contain + /// unique, deterministic data. Currently initialized to + /// command-line paramater string, without any randomly generated + /// arguments. + static std::string SaltData; + + uint64_t Random(); + + static RandomNumberGenerator *Generator(); + + /// \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) { SaltData = Salt; } + + /// \brief Returns a random number in the range [0, Max) + /// + /// Uses sampling to make sure that the result is not biased because + /// Max does not divide evenly into 2^64 + uint64_t Random(uint64_t Max) { + uint64_t t = Max * (((uint64_t)1 << 63) / Max); + uint64_t r; + while ((r = Random()) >= t) + ; /*noop */ + + return r % Max; + } + + /// \brief Shuffles an *array* of type T. + /// + /// Uses the Durstenfeld version of the Fisher-Yates method (aka the Knuth + /// method). See http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle + template void shuffle(T *array, size_t length) { + for (size_t i = length - 1; i > 0; i--) { + size_t j = Random(i + 1); + if (j < i) + std::swap(array[j], array[i]); + } + } + + /// \brief Shuffles a SmallVector of type T, default size N + template void shuffle(SmallVector &sv) { + if (sv.empty()) + return; + for (size_t i = sv.size() - 1; i > 0; i--) { + size_t j = Random(i + 1); + if (j < i) + std::swap(sv[j], sv[i]); + } + } + + /// \brief Shuffles an iplist of type T + template void shuffle(iplist &list) { + if (list.empty()) + return; + SmallVector sv(list.begin(), list.end()); + shuffle(sv); + list.clear(); + for (typename SmallVector::size_type i = 0; i < sv.size(); i++) { + list.push_back(sv[i]); + } + } + +private: + typedef uint8_t BlockType[BLOCK_SIZE]; + + BlockType Value; + BlockType Key; + + RandomNumberGenerator(); + + // Noncopyable. + RandomNumberGenerator( + const RandomNumberGenerator &other) LLVM_DELETED_FUNCTION; + RandomNumberGenerator & + operator=(const RandomNumberGenerator &other) LLVM_DELETED_FUNCTION; + + void HMAC(BlockType Key, ArrayRef Text, BlockType &Result); + void HMAC_DRBG_Update(ArrayRef Data); + + void Seed(StringRef Salt, uint64_t Seed); +}; +} + +#endif Index: include/llvm/Target/TargetOptions.h =================================================================== --- include/llvm/Target/TargetOptions.h +++ include/llvm/Target/TargetOptions.h @@ -50,8 +50,9 @@ GuaranteedTailCallOpt(false), DisableTailCalls(false), StackAlignmentOverride(0), EnableFastISel(false), PositionIndependentExecutable(false), - EnableSegmentedStacks(false), UseInitArray(false), TrapFuncName(""), - FloatABIType(FloatABI::Default), AllowFPOpFusion(FPOpFusion::Standard) + EnableSegmentedStacks(false), NOPInsertion(false), UseInitArray(false), + TrapFuncName(""), FloatABIType(FloatABI::Default), + AllowFPOpFusion(FPOpFusion::Standard) {} /// PrintMachineCode - This flag is enabled when the -print-machineinstrs @@ -154,6 +155,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/LLVMBuild.txt =================================================================== --- lib/CodeGen/LLVMBuild.txt +++ lib/CodeGen/LLVMBuild.txt @@ -22,4 +22,4 @@ type = Library name = CodeGen parent = Libraries -required_libraries = Analysis Core MC Scalar Support Target TransformUtils +required_libraries = Analysis Core Instrumentation MC Scalar Support Target TransformUtils 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 @@ -1765,6 +1777,17 @@ class RegReductionPriorityQueue : public RegReductionPQBase { SF Picker; + static SUnit *popRandom(std::vector &Q) { + RandomNumberGenerator *randGen = + RandomNumberGenerator::Generator(); + 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, @@ -1785,7 +1808,19 @@ SUnit *pop() { if (Queue.empty()) return NULL; - SUnit *V = popFromQueue(Queue, Picker, scheduleDAG); + SUnit *V; + if (RandomizeSchedule) { + RandomNumberGenerator *randGen = + RandomNumberGenerator::Generator(); + 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 @@ -39,6 +39,7 @@ #include "llvm/Support/FormattedStream.h" #include "llvm/Support/Host.h" #include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/RandomNumberGenerator.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Support/Signals.h" #include "llvm/Support/TargetRegistry.h" @@ -143,6 +144,7 @@ Options.PositionIndependentExecutable = options.PositionIndependentExecutable; Options.EnableSegmentedStacks = options.EnableSegmentedStacks; Options.UseInitArray = options.UseInitArray; + Options.NOPInsertion = options.NOPInsertion; } void LTOCodeGenerator::setDebugInfo(lto_debug_model debug) { @@ -466,7 +468,12 @@ Module *mergedModule = Linker.getModule(); - // Mark which symbols can not be internalized + // if options were requested, set them + if ( !CodegenOptions.empty() ) + cl::ParseCommandLineOptions(CodegenOptions.size(), + const_cast(&CodegenOptions[0])); + + // mark which symbols can not be internalized this->applyScopeRestrictions(); // Instantiate the pass manager to organize the passes. Index: lib/LTO/LTOModule.cpp =================================================================== --- lib/LTO/LTOModule.cpp +++ lib/LTO/LTOModule.cpp @@ -35,6 +35,7 @@ #include "llvm/Support/Host.h" #include "llvm/Support/MemoryBuffer.h" #include "llvm/Support/Path.h" +#include "llvm/Support/RandomNumberGenerator.h" #include "llvm/Support/SourceMgr.h" #include "llvm/Support/TargetRegistry.h" #include "llvm/Support/TargetSelect.h" 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,163 @@ +//===-- 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 cryptographically secure random number generation +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "rng" +#include "llvm/Support/RandomNumberGenerator.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Config/config.h" +#include "llvm/Support/Atomic.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/MD5.h" +#include "llvm/Support/Mutex.h" +#include "llvm/Support/raw_ostream.h" + +using namespace llvm; + +// Only read by threads, so no locking +// Needs to be available for SaltDataOpt to set by testing +// command-line, so must be public +std::string RandomNumberGenerator::SaltData; + +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(RandomNumberGenerator::SaltData)); + +static ManagedStatic > Instance; +static unsigned InstanceCount = 0; + +/// This RNG is an implementation of the standard NIST SP 800-90A +/// HMAC_DRBG random number generator, however with MD5 as the hash +/// function. The use of MD5 does not comply with the NIST standard, +/// which specifies SHA as the hash function instead. Since we are +/// using HMAC-MD5, instead of plain MD5, and the random number stream +/// is not directly revealed to an attacker, this should be +/// sufficient. +/// +/// Since this RNG is initialized from a 64-bit seed, it has only 64 +/// bits of entropy, rather than 128 as might be expected from +/// MD5. This should not be a problem as long as possible attacks +/// cannot brute-force through 2^64 possibilities. +/// +/// Note: We do NOT perform reseeding due to constrained entropy +/// data. Since we need reproducibility, we can only use the given +/// 64-bit seed as entropy, and therefore have no additional entropy +/// to reseed with. This means that we assume less than 2^48 calls to +/// Random(). However, it is unlikely that compromise of the RNG is +/// even possible in practice since the actual random stream is not +/// exposed to an attacker. +RandomNumberGenerator::RandomNumberGenerator() { + // Make sure each thread is seeded with a different seed + unsigned InstanceID = sys::AtomicIncrement(&InstanceCount); + + if (RandomSeed == 0 && SaltData.empty()) + DEBUG(errs() << "Warning! Using unseeded random number generator\n"); + + Seed(SaltData, RandomSeed + InstanceID); +} + +void RandomNumberGenerator::HMAC(BlockType Key, ArrayRef Text, + BlockType &Result) { + uint8_t Buffer[64]; + + // Set up ipad + memset(Buffer, 0, sizeof(Buffer)); + memcpy(Buffer, Key, 16); + for (unsigned i = 0; i < 64; ++i) { + Buffer[i] ^= 0x36; + } + + MD5 InnerHash; + MD5::MD5Result InnerResult; + InnerHash.update(makeArrayRef(Buffer)); + InnerHash.update(Text); + InnerHash.final(InnerResult); + + // Set up opad + memset(Buffer, 0, sizeof(Buffer)); + memcpy(Buffer, Key, 16); + for (unsigned i = 0; i < 64; ++i) { + Buffer[i] ^= 0x5c; + } + + MD5 OuterHash; + OuterHash.update(makeArrayRef(Buffer)); + OuterHash.update(makeArrayRef(InnerResult)); + OuterHash.final(Result); +} + +void RandomNumberGenerator::HMAC_DRBG_Update(ArrayRef Data = + ArrayRef()) { + SmallVector Buffer(Key, Key + 16); + Buffer.push_back(0x00); + Buffer.append(Data.begin(), Data.end()); + HMAC(Key, Buffer, Key); + HMAC(Key, Value, Key); + if (Data.size() == 0) + return; + + Buffer.clear(); + Buffer.append(Key, Key + 16); + Buffer.push_back(0x01); + Buffer.append(Data.begin(), Data.end()); + HMAC(Key, Buffer, Key); + HMAC(Key, Value, Value); +} + +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"); + + memset(Key, 0, sizeof(Key)); + memset(Value, 1, sizeof(Value)); + + unsigned SeedSize = sizeof(Seed) + Salt.size(); + uint8_t *SeedMaterial = new uint8_t[SeedSize]; + memcpy(SeedMaterial, &Seed, sizeof(Seed)); + memcpy(SeedMaterial + sizeof(Seed), Salt.data(), Salt.size()); + + HMAC_DRBG_Update(makeArrayRef(SeedMaterial, SeedSize)); + + delete[] SeedMaterial; +} + +uint64_t RandomNumberGenerator::Random() { + HMAC(Key, Value, Value); + uint64_t Output = *(uint64_t *)(Value); + + HMAC_DRBG_Update(); + + return Output; +} + +RandomNumberGenerator *RandomNumberGenerator::Generator() { + RandomNumberGenerator *RNG = + const_cast(Instance->get()); + + if (RNG == 0) { + RNG = new RandomNumberGenerator; + Instance->set(RNG); + } + + return RNG; +} 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,144 @@ +//===- 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 = llvm::next(I); + if (I->isPseudo()) { + I = NextI; + continue; + } + // Insert random number of NOP-like instructions. + for (unsigned int i = 0; i < MaxNOPsPerInstruction; i++) { + unsigned int Roll = RandomNumberGenerator::Generator()->Random(100); + if (Roll >= NOPInsertionPercentage) + continue; + + int NOPCode = RandomNumberGenerator::Generator()->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; +} + +FunctionPass *llvm::createNOPInsertionPass(bool is64Bit) { + return new NOPInsertionPass(is64Bit); +} Index: lib/Target/X86/X86.h =================================================================== --- lib/Target/X86/X86.h +++ lib/Target/X86/X86.h @@ -52,6 +52,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 @@ -225,6 +225,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,48 @@ +; 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: leaq (%rdi), %rdi +; PERCENT10: nop + +; PERCENT50: leaq (%rsi), %rsi +; PERCENT50: nop +; PERCENT50: nop +; PERCENT50: leaq (%rsi), %rsi +; PERCENT50: nop +; PERCENT50: nop +; PERCENT50: nop + +; PERCENT100: leaq (%rsi), %rsi +; PERCENT100: nop +; PERCENT100: leaq (%rdi), %rdi +; PERCENT100: movq %rbp, %rbp +; PERCENT100: movq %rsp, %rsp +; PERCENT100: nop +; PERCENT100: movq %rsp, %rsp +; PERCENT100: movq %rsp, %rsp +; PERCENT100: movq %rsp, %rsp +; PERCENT100: leaq (%rdi), %rdi +; PERCENT100: movq %rsp, %rsp +; PERCENT100: movq %rsp, %rsp Index: test/CodeGen/X86/nop-insert.ll =================================================================== --- /dev/null +++ test/CodeGen/X86/nop-insert.ll @@ -0,0 +1,30 @@ +; 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 (%rsi), %rsi + +; SEED1: nop +; SEED1-NOT: leaq (%rsi), %rsi + +; SEED2: leaq (%rdi), %rdi +; SEED2: leaq (%rdi), %rdi +; SEED2-NOT: leaq (%rsi), %rsi + +; SEED3: nop + +; ENTROPY: movq %rbp, %rbp +; ENTROPY: leaq (%rdi), %rdi +; ENTROPY-NOT: nop + +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,%rdx), %ecx +; SEED1-NEXT: leal (%rdi,%rsi), %eax +; SEED1-NEXT: imull %ecx, %eax +; SEED1-NEXT: addl %edx, %esi +; SEED1-NEXT: imull %esi, %eax + +; SEED2: leal (%rdi,%rdx), %ecx +; SEED2-NEXT: addl %esi, %edx +; SEED2-NEXT: leal (%rdi,%rsi), %eax +; SEED2-NEXT: imull %ecx, %eax +; SEED2-NEXT: imull %edx, %eax + +; PERCENTAGE: leal (%rsi,%rdx), %eax +; PERCENTAGE: addl %edi, %edx +; PERCENTAGE: addl %edi, %esi +; PERCENTAGE: imull %edx, %esi +; PERCENTAGE: imull %esi, %eax Index: tools/llc/llc.cpp =================================================================== --- tools/llc/llc.cpp +++ tools/llc/llc.cpp @@ -33,6 +33,7 @@ #include "llvm/Support/ManagedStatic.h" #include "llvm/Support/PluginLoader.h" #include "llvm/Support/PrettyStackTrace.h" +#include "llvm/Support/RandomNumberGenerator.h" #include "llvm/Support/Signals.h" #include "llvm/Support/SourceMgr.h" #include "llvm/Support/TargetRegistry.h" @@ -279,6 +280,7 @@ Options.PositionIndependentExecutable = EnablePIE; Options.EnableSegmentedStacks = SegmentedStacks; Options.UseInitArray = UseInitArray; + Options.NOPInsertion = NOPInsertion; OwningPtr target(TheTarget->createTargetMachine(TheTriple.getTriple(), Index: tools/llvm-lto/llvm-lto.cpp =================================================================== --- tools/llvm-lto/llvm-lto.cpp +++ tools/llvm-lto/llvm-lto.cpp @@ -97,6 +97,7 @@ Options.PositionIndependentExecutable = EnablePIE; Options.EnableSegmentedStacks = SegmentedStacks; Options.UseInitArray = UseInitArray; + Options.NOPInsertion = NOPInsertion; unsigned BaseArg = 0; Index: tools/lto/lto.cpp =================================================================== --- tools/lto/lto.cpp +++ tools/lto/lto.cpp @@ -75,6 +75,7 @@ Options.TrapFuncName = TrapFuncName; Options.PositionIndependentExecutable = EnablePIE; Options.EnableSegmentedStacks = SegmentedStacks; + Options.NOPInsertion = NOPInsertion; Options.UseInitArray = UseInitArray; } Index: tools/opt/opt.cpp =================================================================== --- tools/opt/opt.cpp +++ tools/opt/opt.cpp @@ -37,6 +37,7 @@ #include "llvm/Support/PassNameParser.h" #include "llvm/Support/PluginLoader.h" #include "llvm/Support/PrettyStackTrace.h" +#include "llvm/Support/RandomNumberGenerator.h" #include "llvm/Support/Signals.h" #include "llvm/Support/SourceMgr.h" #include "llvm/Support/SystemUtils.h" @@ -552,6 +553,7 @@ Options.PositionIndependentExecutable = EnablePIE; Options.EnableSegmentedStacks = SegmentedStacks; Options.UseInitArray = UseInitArray; + Options.NOPInsertion = NOPInsertion; return Options; }