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 @@ -266,7 +266,9 @@ INSTR_PROF_SECT_ENTRY(IPSK_covmap, \ INSTR_PROF_QUOTE(INSTR_PROF_COVMAP_COMMON), \ INSTR_PROF_QUOTE(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 @@ -655,6 +657,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 /* Win32 */ #define INSTR_PROF_DATA_COFF .lprfd #define INSTR_PROF_NAME_COFF .lprfn @@ -662,6 +665,7 @@ #define INSTR_PROF_VALS_COFF .lprfv #define INSTR_PROF_VNODES_COFF .lprfnd #define INSTR_PROF_COVMAP_COFF .lcovmap +#define INSTR_PROF_ORDERFILE_COFF .lorderfile #ifdef _WIN32 /* Runtime section names and name strings. */ @@ -675,6 +679,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_DATA_COMMON @@ -687,6 +692,7 @@ /* Value profile nodes section. */ #define INSTR_PROF_VNODES_SECT_NAME INSTR_PROF_VNODES_COMMON #define INSTR_PROF_COVMAP_SECT_NAME INSTR_PROF_COVMAP_COMMON +#define INSTR_PROF_ORDERFILE_SECT_NAME INSTR_PROF_ORDERFILE_COMMON #endif #define INSTR_PROF_DATA_SECT_NAME_STR \ @@ -701,6 +707,8 @@ INSTR_PROF_QUOTE(INSTR_PROF_VALS_SECT_NAME) #define INSTR_PROF_VNODES_SECT_NAME_STR \ INSTR_PROF_QUOTE(INSTR_PROF_VNODES_SECT_NAME) +#define INSTR_PROF_ORDERFILE_SECT_NAME_STR \ + INSTR_PROF_QUOTE(INSTR_PROF_ORDERFILE_SECT_NAME) /* Macros to define start/stop section symbol for a given * section on Linux. For instance @@ -735,6 +743,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 @@ -143,6 +143,8 @@ ModulePass *createInstrProfilingLegacyPass( const InstrProfOptions &Options = InstrProfOptions()); +ModulePass *createInstrOrderFilePass(); + // Insert AddressSanitizer (address sanity checking) instrumentation FunctionPass *createAddressSanitizerFunctionPass(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" @@ -209,6 +210,7 @@ cl::desc("Enable control height reduction optimization (CHR)")); extern cl::opt EnableHotColdSplit; +extern cl::opt EnableOrderFileInstrumentation; static bool isOptimizingForSize(PassBuilder::OptimizationLevel Level) { switch (Level) { @@ -746,6 +748,9 @@ MPM.addPass(GlobalOptPass()); MPM.addPass(GlobalDCEPass()); + if (EnableOrderFileInstrumentation) + MPM.addPass(InstrOrderFilePass()); + // Run partial inlining pass to partially inline functions that have // large bodies. if (RunPartialInlining) 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 @@ -160,6 +160,10 @@ EnableCHR("enable-chr", cl::init(true), cl::Hidden, cl::desc("Enable control height reduction optimization (CHR)")); +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; @@ -552,6 +556,9 @@ // we must insert a no-op module pass to reset the pass manager. MPM.add(createBarrierNoopPass()); + if (EnableOrderFileInstrumentation) { + MPM.add(createInstrOrderFilePass()); + } if (RunPartialInlining) MPM.add(createPartialInliningPass()); 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 ClWriteMapping( + "orderfile-write-mapping", + cl::desc( + "Write mapping from (module id, function id) to the function symbol"), + 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 = "order_file_buffer"; + 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 = "order_file_buffer_idx"; + 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 (!ClWriteMapping.empty()) { + std::lock_guard LogLock(MappingMutex); + std::error_code EC; + llvm::raw_fd_ostream OS(ClWriteMapping, EC, llvm::sys::fs::F_Text); + if (EC) { + report_fatal_error(Twine("Failed to open ") + ClWriteMapping + + " 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 @@ -110,6 +110,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: @order_file_buffer ={{.*}}global [131072 x i64] zeroinitializer +; CHECK: @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* @order_file_buffer_idx, i32 1 seq_cst +; CHECK: %[[T5:.+]] = and i32 %[[T3]], 131071 +; CHECK: %[[T4:.+]] = getelementptr [131072 x i64], [131072 x i64]* @order_file_buffer, i32 0, i32 %[[T5]] +; CHECK: store i64 {{.*}}, i64* %[[T4]]