Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -181,6 +181,7 @@ void initializeInstNamerPass(PassRegistry&); void initializeInstSimplifyLegacyPassPass(PassRegistry &); void initializeInstrProfilingLegacyPassPass(PassRegistry&); +void initializeInstrOrderFileLegacyPassPass(PassRegistry&); void initializeInstructionCombiningPassPass(PassRegistry&); void initializeInstructionSelectPass(PassRegistry&); void initializeInterleavedAccessPass(PassRegistry&); Index: include/llvm/ProfileData/InstrProfData.inc =================================================================== --- include/llvm/ProfileData/InstrProfData.inc +++ include/llvm/ProfileData/InstrProfData.inc @@ -265,6 +265,9 @@ INSTR_PROF_SECT_ENTRY(IPSK_covmap, \ INSTR_PROF_QUOTE(INSTR_PROF_COVMAP_COMMON), \ INSTR_PROF_COVMAP_COFF, "__LLVM_COV,") +INSTR_PROF_SECT_ENTRY(IPSK_orderfile, \ + INSTR_PROF_QUOTE(INSTR_PROF_ORDERFILE_COMMON), \ + INSTR_PROF_QUOTE(INSTR_PROF_ORDERFILE_COFF), "__DATA,") #undef INSTR_PROF_SECT_ENTRY #endif @@ -656,6 +659,7 @@ #define INSTR_PROF_VALS_COMMON __llvm_prf_vals #define INSTR_PROF_VNODES_COMMON __llvm_prf_vnds #define INSTR_PROF_COVMAP_COMMON __llvm_covmap +#define INSTR_PROF_ORDERFILE_COMMON __llvm_orderfile /* Windows section names. Because these section names contain dollar characters, * they must be quoted. */ @@ -665,6 +669,7 @@ #define INSTR_PROF_VALS_COFF ".lprfv$M" #define INSTR_PROF_VNODES_COFF ".lprfnd$M" #define INSTR_PROF_COVMAP_COFF ".lcovmap$M" +#define INSTR_PROF_ORDERFILE_COFF ".lorderfile$M" #ifdef _WIN32 /* Runtime section names and name strings. */ @@ -678,6 +683,7 @@ /* Value profile nodes section. */ #define INSTR_PROF_VNODES_SECT_NAME INSTR_PROF_VNODES_COFF #define INSTR_PROF_COVMAP_SECT_NAME INSTR_PROF_COVMAP_COFF +#define INSTR_PROF_ORDERFILE_SECT_NAME INSTR_PROF_ORDERFILE_COFF #else /* Runtime section names and name strings. */ #define INSTR_PROF_DATA_SECT_NAME INSTR_PROF_QUOTE(INSTR_PROF_DATA_COMMON) @@ -690,6 +696,15 @@ /* Value profile nodes section. */ #define INSTR_PROF_VNODES_SECT_NAME INSTR_PROF_QUOTE(INSTR_PROF_VNODES_COMMON) #define INSTR_PROF_COVMAP_SECT_NAME INSTR_PROF_QUOTE(INSTR_PROF_COVMAP_COMMON) +/* Order file instrumentation. */ +#define INSTR_PROF_ORDERFILE_SECT_NAME \ + INSTR_PROF_QUOTE(INSTR_PROF_ORDERFILE_COMMON) +#define INSTR_PROF_ORDERFILE_BUFFER_NAME _llvm_order_file_buffer +#define INSTR_PROF_ORDERFILE_BUFFER_NAME_STR \ + INSTR_PROF_QUOTE(INSTR_PROF_ORDERFILE_BUFFER_NAME) +#define INSTR_PROF_ORDERFILE_BUFFER_IDX_NAME _llvm_order_file_buffer_idx +#define INSTR_PROF_ORDERFILE_BUFFER_IDX_NAME_STR \ + INSTR_PROF_QUOTE(INSTR_PROF_ORDERFILE_BUFFER_IDX_NAME) #endif /* Macros to define start/stop section symbol for a given @@ -725,6 +740,12 @@ #endif /* INSTR_PROF_DATA_INC */ +#ifndef INSTR_ORDER_FILE_INC +// The maximal # of functions: 128*1024 (the buffer size will be 128*4 KB). +#define INSTR_ORDER_FILE_BUFFER_SIZE 131072 +#define INSTR_ORDER_FILE_BUFFER_BITS 17 +#define INSTR_ORDER_FILE_BUFFER_MASK 0x1ffff +#endif /* INSTR_ORDER_FILE_INC */ #else #undef INSTR_PROF_DATA_DEFINED #endif Index: include/llvm/Transforms/Instrumentation.h =================================================================== --- include/llvm/Transforms/Instrumentation.h +++ include/llvm/Transforms/Instrumentation.h @@ -150,6 +150,8 @@ ModulePass *createInstrProfilingLegacyPass( const InstrProfOptions &Options = InstrProfOptions(), bool IsCS = false); +ModulePass *createInstrOrderFilePass(); + FunctionPass *createHWAddressSanitizerPass(bool CompileKernel = false, bool Recover = false); Index: include/llvm/Transforms/Instrumentation/InstrOrderFile.h =================================================================== --- include/llvm/Transforms/Instrumentation/InstrOrderFile.h +++ include/llvm/Transforms/Instrumentation/InstrOrderFile.h @@ -0,0 +1,28 @@ +//===- InstrOrderFile.h ---- Late IR instrumentation for order file ----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_INSTRORDERFILE_H +#define LLVM_TRANSFORMS_INSTRORDERFILE_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { +class Module; + +/// The instrumentation pass for recording function order. +class InstrOrderFilePass : public PassInfoMixin { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_INSTRORDERFILE_H Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -93,6 +93,7 @@ #include "llvm/Transforms/Instrumentation/CGProfile.h" #include "llvm/Transforms/Instrumentation/ControlHeightReduction.h" #include "llvm/Transforms/Instrumentation/GCOVProfiler.h" +#include "llvm/Transforms/Instrumentation/InstrOrderFile.h" #include "llvm/Transforms/Instrumentation/InstrProfiling.h" #include "llvm/Transforms/Instrumentation/MemorySanitizer.h" #include "llvm/Transforms/Instrumentation/PGOInstrumentation.h" @@ -211,6 +212,7 @@ cl::desc("Enable control height reduction optimization (CHR)")); extern cl::opt EnableHotColdSplit; +extern cl::opt EnableOrderFileInstrumentation; extern cl::opt FlattenedProfileUsed; @@ -785,6 +787,9 @@ // running remaining passes on the eliminated functions. MPM.addPass(EliminateAvailableExternallyPass()); + if (EnableOrderFileInstrumentation) + MPM.addPass(InstrOrderFilePass()); + // Do RPO function attribute inference across the module to forward-propagate // attributes where applicable. // FIXME: Is this really an optimization rather than a canonicalization? Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -56,6 +56,7 @@ MODULE_PASS("hotcoldsplit", HotColdSplittingPass()) MODULE_PASS("inferattrs", InferFunctionAttrsPass()) MODULE_PASS("insert-gcov-profiling", GCOVProfilerPass()) +MODULE_PASS("instrorderfile", InstrOrderFilePass()) MODULE_PASS("instrprof", InstrProfiling()) MODULE_PASS("internalize", InternalizePass()) MODULE_PASS("invalidate", InvalidateAllAnalysesPass()) Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -154,6 +154,10 @@ cl::desc("Indicate the sample profile being used is flattened, i.e., " "no inline hierachy exists in the profile. ")); +cl::opt EnableOrderFileInstrumentation( + "enable-order-file-instrumentation", cl::init(false), cl::Hidden, + cl::desc("Enable order file instrumentation (default = off)")); + PassManagerBuilder::PassManagerBuilder() { OptLevel = 2; SizeLevel = 0; @@ -570,6 +574,9 @@ // and saves running remaining passes on the eliminated functions. MPM.add(createEliminateAvailableExternallyPass()); + if (EnableOrderFileInstrumentation) + MPM.add(createInstrOrderFilePass()); + MPM.add(createReversePostOrderFunctionAttrsPass()); // The inliner performs some kind of dead code elimination as it goes, Index: lib/Transforms/Instrumentation/CMakeLists.txt =================================================================== --- lib/Transforms/Instrumentation/CMakeLists.txt +++ lib/Transforms/Instrumentation/CMakeLists.txt @@ -8,6 +8,7 @@ MemorySanitizer.cpp IndirectCallPromotion.cpp Instrumentation.cpp + InstrOrderFile.cpp InstrProfiling.cpp PGOInstrumentation.cpp PGOMemOPSizeOpt.cpp Index: lib/Transforms/Instrumentation/InstrOrderFile.cpp =================================================================== --- lib/Transforms/Instrumentation/InstrOrderFile.cpp +++ lib/Transforms/Instrumentation/InstrOrderFile.cpp @@ -0,0 +1,210 @@ +//===- InstrOrderFile.cpp ---- Late IR instrumentation for order file ----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/Statistic.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/GlobalValue.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Metadata.h" +#include "llvm/IR/Module.h" +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" +#include "llvm/ProfileData/InstrProf.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/Path.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Instrumentation.h" +#include "llvm/Transforms/Instrumentation/InstrOrderFile.h" +#include +#include +#include +#include + +using namespace llvm; +#define DEBUG_TYPE "instrorderfile" + +static cl::opt ClOrderFileWriteMapping( + "orderfile-write-mapping", cl::init(""), + cl::desc( + "Dump functions and their MD5 hash to deobfuscate profile data"), + cl::Hidden); + +namespace { + +// We need a global bitmap to tell if a function is executed. We also +// need a global variable to save the order of functions. We can use a +// fixed-size buffer that saves the MD5 hash of the function. We need +// a global variable to save the index into the buffer. + +std::mutex MappingMutex; + +struct InstrOrderFile { +private: + GlobalVariable *OrderFileBuffer; + GlobalVariable *BufferIdx; + GlobalVariable *BitMap; + ArrayType *BufferTy; + ArrayType *MapTy; + +public: + InstrOrderFile() {} + + void createOrderFileData(Module &M) { + LLVMContext &Ctx = M.getContext(); + int NumFunctions = 0; + for (Function &F : M) { + if (!F.isDeclaration()) + NumFunctions++; + } + + BufferTy = + ArrayType::get(Type::getInt64Ty(Ctx), INSTR_ORDER_FILE_BUFFER_SIZE); + Type *IdxTy = Type::getInt32Ty(Ctx); + MapTy = ArrayType::get(Type::getInt8Ty(Ctx), NumFunctions); + + // Create the global variables. + std::string SymbolName = INSTR_PROF_ORDERFILE_BUFFER_NAME_STR; + OrderFileBuffer = new GlobalVariable(M, BufferTy, false, GlobalValue::LinkOnceODRLinkage, + Constant::getNullValue(BufferTy), SymbolName); + Triple TT = Triple(M.getTargetTriple()); + OrderFileBuffer->setSection( + getInstrProfSectionName(IPSK_orderfile, TT.getObjectFormat())); + + std::string IndexName = INSTR_PROF_ORDERFILE_BUFFER_IDX_NAME_STR; + BufferIdx = new GlobalVariable(M, IdxTy, false, GlobalValue::LinkOnceODRLinkage, + Constant::getNullValue(IdxTy), IndexName); + + std::string BitMapName = "bitmap_0"; + BitMap = new GlobalVariable(M, MapTy, false, GlobalValue::PrivateLinkage, + Constant::getNullValue(MapTy), BitMapName); + } + + // Generate the code sequence in the entry block of each function to + // update the buffer. + void generateCodeSequence(Module &M, Function &F, int FuncId) { + if (!ClOrderFileWriteMapping.empty()) { + std::lock_guard LogLock(MappingMutex); + std::error_code EC; + llvm::raw_fd_ostream OS(ClOrderFileWriteMapping, EC, llvm::sys::fs::F_Append); + if (EC) { + report_fatal_error(Twine("Failed to open ") + ClOrderFileWriteMapping + + " to save mapping file for order file instrumentation\n"); + } else { + std::stringstream stream; + stream << std::hex << MD5Hash(F.getName()); + std::string singleLine = "MD5 " + stream.str() + " " + + std::string(F.getName()) + '\n'; + OS << singleLine; + } + } + + BasicBlock *OrigEntry = &F.getEntryBlock(); + + LLVMContext &Ctx = M.getContext(); + IntegerType *Int32Ty = Type::getInt32Ty(Ctx); + IntegerType *Int8Ty = Type::getInt8Ty(Ctx); + + // Create a new entry block for instrumentation. We will check the bitmap + // in this basic block. + BasicBlock *NewEntry = + BasicBlock::Create(M.getContext(), "order_file_entry", &F, OrigEntry); + IRBuilder<> entryB(NewEntry); + // Create a basic block for updating the circular buffer. + BasicBlock *UpdateOrderFileBB = + BasicBlock::Create(M.getContext(), "order_file_set", &F, OrigEntry); + IRBuilder<> updateB(UpdateOrderFileBB); + + // Check the bitmap, if it is already 1, do nothing. + // Otherwise, set the bit, grab the index, update the buffer. + Value *IdxFlags[] = {ConstantInt::get(Int32Ty, 0), + ConstantInt::get(Int32Ty, FuncId)}; + Value *MapAddr = entryB.CreateGEP(MapTy, BitMap, IdxFlags, ""); + LoadInst *loadBitMap = entryB.CreateLoad(Int8Ty, MapAddr, ""); + entryB.CreateStore(ConstantInt::get(Int8Ty, 1), MapAddr); + Value *IsNotExecuted = + entryB.CreateICmpEQ(loadBitMap, ConstantInt::get(Int8Ty, 0)); + entryB.CreateCondBr(IsNotExecuted, UpdateOrderFileBB, OrigEntry); + + // Fill up UpdateOrderFileBB: grab the index, update the buffer! + Value *IdxVal = updateB.CreateAtomicRMW( + AtomicRMWInst::Add, BufferIdx, ConstantInt::get(Int32Ty, 1), + AtomicOrdering::SequentiallyConsistent); + // We need to wrap around the index to fit it inside the buffer. + Value *WrappedIdx = updateB.CreateAnd( + IdxVal, ConstantInt::get(Int32Ty, INSTR_ORDER_FILE_BUFFER_MASK)); + Value *BufferGEPIdx[] = {ConstantInt::get(Int32Ty, 0), WrappedIdx}; + Value *BufferAddr = + updateB.CreateGEP(BufferTy, OrderFileBuffer, BufferGEPIdx, ""); + updateB.CreateStore(ConstantInt::get(Type::getInt64Ty(Ctx), MD5Hash(F.getName())), + BufferAddr); + updateB.CreateBr(OrigEntry); + } + + bool run(Module &M) { + createOrderFileData(M); + + int FuncId = 0; + for (Function &F : M) { + if (F.isDeclaration()) + continue; + generateCodeSequence(M, F, FuncId); + ++FuncId; + } + + return true; + } + +}; // End of InstrOrderFile struct + +class InstrOrderFileLegacyPass : public ModulePass { +public: + static char ID; + + InstrOrderFileLegacyPass() : ModulePass(ID) { + initializeInstrOrderFileLegacyPassPass( + *PassRegistry::getPassRegistry()); + } + + bool runOnModule(Module &M) override; +}; + +} // End anonymous namespace + +bool InstrOrderFileLegacyPass::runOnModule(Module &M) { + if (skipModule(M)) + return false; + + return InstrOrderFile().run(M); +} + +PreservedAnalyses +InstrOrderFilePass::run(Module &M, ModuleAnalysisManager &AM) { + if (InstrOrderFile().run(M)) + return PreservedAnalyses::none(); + return PreservedAnalyses::all(); +} + +INITIALIZE_PASS_BEGIN(InstrOrderFileLegacyPass, "instrorderfile", + "Instrumentation for Order File", false, false) +INITIALIZE_PASS_END(InstrOrderFileLegacyPass, "instrorderfile", + "Instrumentation for Order File", false, false) + +char InstrOrderFileLegacyPass::ID = 0; + +ModulePass *llvm::createInstrOrderFilePass() { + return new InstrOrderFileLegacyPass(); +} Index: lib/Transforms/Instrumentation/Instrumentation.cpp =================================================================== --- lib/Transforms/Instrumentation/Instrumentation.cpp +++ lib/Transforms/Instrumentation/Instrumentation.cpp @@ -109,6 +109,7 @@ initializePGOInstrumentationUseLegacyPassPass(Registry); initializePGOIndirectCallPromotionLegacyPassPass(Registry); initializePGOMemOPSizeOptLegacyPassPass(Registry); + initializeInstrOrderFileLegacyPassPass(Registry); initializeInstrProfilingLegacyPassPass(Registry); initializeMemorySanitizerLegacyPassPass(Registry); initializeHWAddressSanitizerPass(Registry); Index: test/Instrumentation/InstrOrderFile/basic.ll =================================================================== --- test/Instrumentation/InstrOrderFile/basic.ll +++ test/Instrumentation/InstrOrderFile/basic.ll @@ -0,0 +1,24 @@ +; RUN: opt -instrorderfile -S < %s | FileCheck %s +; RUN: opt -passes=instrorderfile -S < %s | FileCheck %s + +target triple = "x86_64-apple-macosx10.10.0" + +; CHECK: @_llvm_order_file_buffer ={{.*}}global [131072 x i64] zeroinitializer +; CHECK: @_llvm_order_file_buffer_idx = linkonce_odr global i32 0 +; CHECK: @bitmap_0 ={{.*}}global [1 x i8] zeroinitializer + +define i32 @_Z1fv() { + ret i32 0 +} +; CHECK-LABEL: define i32 @_Z1fv +; CHECK: order_file_entry +; CHECK: %[[T1:.+]] = load i8, i8* getelementptr inbounds ([1 x i8], [1 x i8]* @bitmap_0, i32 0, i32 0 +; CHECK: store i8 1, i8* getelementptr inbounds ([1 x i8], [1 x i8]* @bitmap_0, i32 0, i32 0) +; CHECK: %[[T2:.+]] = icmp eq i8 %[[T1]], 0 +; CHECK: br i1 %[[T2]], label %order_file_set, label + +; CHECK: order_file_set +; CHECK: %[[T3:.+]] = atomicrmw add i32* @_llvm_order_file_buffer_idx, i32 1 seq_cst +; CHECK: %[[T5:.+]] = and i32 %[[T3]], 131071 +; CHECK: %[[T4:.+]] = getelementptr [131072 x i64], [131072 x i64]* @_llvm_order_file_buffer, i32 0, i32 %[[T5]] +; CHECK: store i64 {{.*}}, i64* %[[T4]]