Add a module pass for order file instrumentation

[manmanren]

Summary

The basic idea of the pass is to use a circular buffer to log the execution ordering of the functions. We only log the function when it is first executed. We use a 8-byte hash to log the function symbol name.

In this pass, we add three global variables:
(1) an order file buffer: a circular buffer at its own llvm section.
(2) a bitmap for each module: one byte for each function to say if the function is already executed.
(3) a global index to the order file buffer.

At the function prologue, if the function has not been executed (by checking the bitmap), log the function hash, then atomically increase the index.

[davidxl]

Have not looked at it in details, but it looks like the support for the new PM is missing. Can that be added?

[davidxl]

There is a copy of InstrProfData.inc in compiler-rt, and that one needs to be kept in sync with the one in compiler side.

include/llvm/ProfileData/InstrProfData.inc

686

should probably remove mentioning of Pika here.

698

Same here.

743

the #ifndef is not needed. The whole macro definition section is already preprocessing guarded.

749

The #else part is not needed either.

lib/Transforms/Instrumentation/InstrOrderFile.cpp

40

Why is it called 'write mapping'? Sounds a little confusing.

43

Since mapping file is already needed, should this option has a default value?

[manmanren]

Add support for the new pass manager

[manmanren]

Address some review comments

[davidxl]

lib/Passes/PassBuilder.cpp

775

The pass should probably be moved after partial inlining and eliminateAvailableExternallyPass. Partial inlining may create new functions, and it is also unnecessary to instrument availableExternally functions.

lib/Transforms/Instrumentation/InstrOrderFile.cpp

81

Should define macro in InstProfData.inc file.

The name of the symbol is also too generic. Need to prefix with __llvm_...

88

Same here.

148

Why not having a runtime interface to flush the buffer here?

[manmanren]

I think I have addressed most of the comments. There is one comment which I am not sure.

Thanks for reviewing David!

Manman

[manmanren]

lib/Transforms/Instrumentation/InstrOrderFile.cpp

148

Can you give an example of a runtime interface? Are you referring to helpers in another file maybe InstrProfiling.cpp?

[davidxl]

lib/Transforms/Instrumentation/InstrOrderFile.cpp

148

something in compiler-rt like '__llvm_profile_orderfile_buffer_flush' which append the buffer data when the buffer overflows.

This can be done later if it is a needed in practice.

[davidxl]

lgtm.

LLVM part looks ok. Do you have plan to hook it up with Clang driver? It is also good to add support in llvm-profdata to support converting the raw mapping+dumping into linker order file format.

[manmanren]

Rebase

[stella.stamenova]

This broke the windows LLDB bot:

http://lab.llvm.org:8011/builders/lldb-x64-windows-ninja/builds/2182

It looks like it's not the only broken one either.

[krytarowski]

The NetBSD buildbot is broken after this change.

http://lab.llvm.org:8011/builders/netbsd-amd64/builds/19200

[thakis]

Hi,

is there any documentation on how to use this? I see that clang has a -forder-file-instrumentation switch to enable this. But what do I do after I enabled it? Run the instrumented program and then…? From the name, I'm guessing maybe the idea is that this will produce an order file?

Part of why I'm asking is because I'm trying to teach lld/mac about section$start$ symbols, but with a candidate patch I'm still getting undefined symbol: section$start$__DATA$__llvm_orderfile. It's well possible my patch is wrong, but I don't see what's supposed to create the __llvm_orderfile section (https://bugs.chromium.org/p/chromium/issues/detail?id=1220128#c10 has the candidate patch).

Thanks,
Nico

[thakis]

is there any documentation on how to use this? I see that clang has a -forder-file-instrumentation switch to enable this. But what do I do after I enabled it? Run the instrumented program and then…? From the name, I'm guessing maybe the idea is that this will produce an order file?

Looks like compiler-rt/test/profile/instrprof-order-file.test gives a demo for how this is supposed to be used: clang -forder-file-instrumentation -O1 compiler-rt/test/profile/Inputs/instrprof-order-file-2.c compiler-rt/test/profile/Inputs/instrprof-order-file.c -mllvm -orderfile-write-mapping="mapping.txt", i.e. it needs an -mllvm flag to make it have an effect.

[manmanren]

In D57463#2823600, @thakis wrote:

is there any documentation on how to use this? I see that clang has a -forder-file-instrumentation switch to enable this. But what do I do after I enabled it? Run the instrumented program and then…? From the name, I'm guessing maybe the idea is that this will produce an order file?

I don't think I wrote a doc on this. Yes 'compiler-rt/test/profile/instrprof-order-file.test' shows how to use it, build the app with -forder-file-instrumentation and -mllvm -orderfile-write-mapping, then run the app, use the mapping file to decode the profile.

The profile should be in default.profraw.order. But you can change its name via:

• Writes to the file with the last name given to \a *
• __llvm_profile_set_filename(),
• or if it hasn't been called, the \c LLVM_PROFILE_FILE environment variable,
• or if that's not set, the last name set to INSTR_PROF_PROFILE_NAME_VAR,
• or if that's not set, \c "default.profraw".

Hope this helps!
Manman

Looks like compiler-rt/test/profile/instrprof-order-file.test gives a demo for how this is supposed to be used: clang -forder-file-instrumentation -O1 compiler-rt/test/profile/Inputs/instrprof-order-file-2.c compiler-rt/test/profile/Inputs/instrprof-order-file.c -mllvm -orderfile-write-mapping="mapping.txt", i.e. it needs an -mllvm flag to make it have an effect.

In D57463#2823575, @thakis wrote:

Hi,

is there any documentation on how to use this? I see that clang has a -forder-file-instrumentation switch to enable this. But what do I do after I enabled it? Run the instrumented program and then…? From the name, I'm guessing maybe the idea is that this will produce an order file?

Part of why I'm asking is because I'm trying to teach lld/mac about section$start$ symbols, but with a candidate patch I'm still getting undefined symbol: section$start$__DATA$__llvm_orderfile. It's well possible my patch is wrong, but I don't see what's supposed to create the __llvm_orderfile section (https://bugs.chromium.org/p/chromium/issues/detail?id=1220128#c10 has the candidate patch).

Thanks,
Nico

include/llvm/InitializePasses.h

 void initializeIndirectBrExpandPassPass(PassRegistry&);
 void initializeInferAddressSpacesPass(PassRegistry&);
 void initializeInferFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeInlineCostAnalysisPass(PassRegistry&);
 void initializeInstCountPass(PassRegistry&);
 void initializeInstNamerPass(PassRegistry&);
 void initializeInstSimplifyLegacyPassPass(PassRegistry &);
 void initializeInstrProfilingLegacyPassPass(PassRegistry&);
+void initializeInstrOrderFileLegacyPassPass(PassRegistry&);
 void initializeInstructionCombiningPassPass(PassRegistry&);
 void initializeInstructionSelectPass(PassRegistry&);
 void initializeInterleavedAccessPass(PassRegistry&);
 void initializeInterleavedLoadCombinePass(PassRegistry &);
 void initializeInternalizeLegacyPassPass(PassRegistry&);
 void initializeIntervalPartitionPass(PassRegistry&);
 void initializeJumpThreadingPass(PassRegistry&);
 void initializeLCSSAVerificationPassPass(PassRegistry&);

include/llvm/ProfileData/InstrProfData.inc

INSTR_PROF_SECT_ENTRY(IPSK_vals, \
                       INSTR_PROF_QUOTE(INSTR_PROF_VALS_COMMON), \
                       INSTR_PROF_VALS_COFF, "__DATA,")
 INSTR_PROF_SECT_ENTRY(IPSK_vnodes, \
                       INSTR_PROF_QUOTE(INSTR_PROF_VNODES_COMMON), \
                       INSTR_PROF_VNODES_COFF, "__DATA,")
 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
 
 
 #ifdef INSTR_PROF_VALUE_PROF_DATA
 #define INSTR_PROF_DATA_DEFINED
 

 /* section name strings common to all targets other
    than WIN32 */
 #define INSTR_PROF_DATA_COMMON __llvm_prf_data
 #define INSTR_PROF_NAME_COMMON __llvm_prf_names
 #define INSTR_PROF_CNTS_COMMON __llvm_prf_cnts
 #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.
  */
 #define INSTR_PROF_DATA_COFF ".lprfd$M"
 #define INSTR_PROF_NAME_COFF ".lprfn$M"
 #define INSTR_PROF_CNTS_COFF ".lprfc$M"
 #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.  */
 #define INSTR_PROF_DATA_SECT_NAME INSTR_PROF_DATA_COFF
 #define INSTR_PROF_NAME_SECT_NAME INSTR_PROF_NAME_COFF
 #define INSTR_PROF_CNTS_SECT_NAME INSTR_PROF_CNTS_COFF
 /* Array of pointers. Each pointer points to a list
  * of value nodes associated with one value site.
  */
 #define INSTR_PROF_VALS_SECT_NAME INSTR_PROF_VALS_COFF
 /* 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)
 #define INSTR_PROF_NAME_SECT_NAME INSTR_PROF_QUOTE(INSTR_PROF_NAME_COMMON)
 #define INSTR_PROF_CNTS_SECT_NAME INSTR_PROF_QUOTE(INSTR_PROF_CNTS_COMMON)
 /* Array of pointers. Each pointer points to a list
  * of value nodes associated with one value site.
  */
 #define INSTR_PROF_VALS_SECT_NAME INSTR_PROF_QUOTE(INSTR_PROF_VALS_COMMON)
 /* 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
  * section on Linux. For instance
  * INSTR_PROF_SECT_START(INSTR_PROF_DATA_SECT_NAME) will
  * expand to __start___llvm_prof_data
  */
 #define INSTR_PROF_SECT_START(Sect) \
typedef struct InstrProfValueData {
   /* Profiled value. */
   uint64_t Value;
   /* Number of times the value appears in the training run. */
   uint64_t Count;
 } InstrProfValueData;
 
 #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

include/llvm/Transforms/Instrumentation.h

struct InstrProfOptions {
   InstrProfOptions() = default;
 };
 
 /// Insert frontend instrumentation based profiling. Parameter IsCS indicates if
 // this is the context senstive instrumentation.
 ModulePass *createInstrProfilingLegacyPass(
     const InstrProfOptions &Options = InstrProfOptions(), bool IsCS = false);
 
+ModulePass *createInstrOrderFilePass();
+
 FunctionPass *createHWAddressSanitizerPass(bool CompileKernel = false,
                                            bool Recover = false);
 
 // Insert DataFlowSanitizer (dynamic data flow analysis) instrumentation
 ModulePass *createDataFlowSanitizerPass(
     const std::vector<std::string> &ABIListFiles = std::vector<std::string>(),
     void *(*getArgTLS)() = nullptr, void *(*getRetValTLS)() = nullptr);
 

include/llvm/Transforms/Instrumentation/InstrOrderFile.h

+//===- 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<InstrOrderFilePass> {
+public:
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_INSTRORDERFILE_H

lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/IPO/WholeProgramDevirt.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Instrumentation/AddressSanitizer.h"
 #include "llvm/Transforms/Instrumentation/BoundsChecking.h"
 #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"
 #include "llvm/Transforms/Instrumentation/ThreadSanitizer.h"
 #include "llvm/Transforms/Scalar/ADCE.h"
 #include "llvm/Transforms/Scalar/AlignmentFromAssumptions.h"
 #include "llvm/Transforms/Scalar/BDCE.h"
 #include "llvm/Transforms/Scalar/CallSiteSplitting.h"

 static Regex DefaultAliasRegex(
     "^(default|thinlto-pre-link|thinlto|lto-pre-link|lto)<(O[0123sz])>$");
 
 static cl::opt<bool>
     EnableCHR("enable-chr-npm", cl::init(true), cl::Hidden,
               cl::desc("Enable control height reduction optimization (CHR)"));
 
 extern cl::opt<bool> EnableHotColdSplit;
+extern cl::opt<bool> EnableOrderFileInstrumentation;
 
 extern cl::opt<bool> FlattenedProfileUsed;
 
 static bool isOptimizingForSize(PassBuilder::OptimizationLevel Level) {
   switch (Level) {
   case PassBuilder::O0:
   case PassBuilder::O1:
   case PassBuilder::O2:

 ModulePassManager PassBuilder::buildModuleOptimizationPipeline(
     OptimizationLevel Level, bool DebugLogging, bool LTOPreLink) {
   ModulePassManager MPM(DebugLogging);
 
   // Optimize globals now that the module is fully simplified.
   MPM.addPass(GlobalOptPass());
   MPM.addPass(GlobalDCEPass());
 
   // Run partial inlining pass to partially inline functions that have
   // large bodies.
   if (RunPartialInlining)
     MPM.addPass(PartialInlinerPass());
 
   // Remove avail extern fns and globals definitions since we aren't compiling
   // an object file for later LTO. For LTO we want to preserve these so they
   // are eligible for inlining at link-time. Note if they are unreferenced they
   // will be removed by GlobalDCE later, so this only impacts referenced
   // available externally globals. Eventually they will be suppressed during
   // codegen, but eliminating here enables more opportunity for GlobalDCE as it
   // may make globals referenced by available external functions dead and saves
   // 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?
   MPM.addPass(ReversePostOrderFunctionAttrsPass());
 
   // Re-require GloblasAA here prior to function passes. This is particularly
   // useful as the above will have inlined, DCE'ed, and function-attr
   // propagated everything. We should at this point have a reasonably minimal

lib/Passes/PassRegistry.def

 MODULE_PASS("forceattrs", ForceFunctionAttrsPass())
 MODULE_PASS("function-import", FunctionImportPass())
 MODULE_PASS("globaldce", GlobalDCEPass())
 MODULE_PASS("globalopt", GlobalOptPass())
 MODULE_PASS("globalsplit", GlobalSplitPass())
 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<all>", InvalidateAllAnalysesPass())
 MODULE_PASS("ipsccp", IPSCCPPass())
 MODULE_PASS("lowertypetests", LowerTypeTestsPass(nullptr, nullptr))
 MODULE_PASS("name-anon-globals", NameAnonGlobalPass())
 MODULE_PASS("no-op-module", NoOpModulePass())
 MODULE_PASS("partial-inliner", PartialInlinerPass())

lib/Transforms/IPO/PassManagerBuilder.cpp

static cl::opt<bool>
     EnableCHR("enable-chr", cl::init(true), cl::Hidden,
               cl::desc("Enable control height reduction optimization (CHR)"));
 
 cl::opt<bool> FlattenedProfileUsed(
     "flattened-profile-used", cl::init(false), cl::Hidden,
     cl::desc("Indicate the sample profile being used is flattened, i.e., "
              "no inline hierachy exists in the profile. "));
 
+cl::opt<bool> EnableOrderFileInstrumentation(
+    "enable-order-file-instrumentation", cl::init(false), cl::Hidden,
+    cl::desc("Enable order file instrumentation (default = off)"));
+
 PassManagerBuilder::PassManagerBuilder() {
     OptLevel = 2;
     SizeLevel = 0;
     LibraryInfo = nullptr;
     Inliner = nullptr;
     DisableUnrollLoops = false;
     SLPVectorize = RunSLPVectorization;
     LoopVectorize = RunLoopVectorization;
if (OptLevel > 1 && !PrepareForLTO && !PrepareForThinLTO)
     // are unreferenced they will be removed by GlobalDCE later, so
     // this only impacts referenced available externally globals.
     // Eventually they will be suppressed during codegen, but eliminating
     // here enables more opportunity for GlobalDCE as it may make
     // globals referenced by available external functions dead
     // 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,
   // but there are cases that are not really caught by it. We might
   // at some point consider teaching the inliner about them, but it
   // is OK for now to run GlobalOpt + GlobalDCE in tandem as their
   // benefits generally outweight the cost, making the whole pipeline
   // faster.

lib/Transforms/Instrumentation/CMakeLists.txt

 add_llvm_library(LLVMInstrumentation
   AddressSanitizer.cpp
   BoundsChecking.cpp
   CGProfile.cpp
   ControlHeightReduction.cpp
   DataFlowSanitizer.cpp
   GCOVProfiling.cpp
   MemorySanitizer.cpp
   IndirectCallPromotion.cpp
   Instrumentation.cpp
+  InstrOrderFile.cpp
   InstrProfiling.cpp
   PGOInstrumentation.cpp
   PGOMemOPSizeOpt.cpp
   SanitizerCoverage.cpp
   ThreadSanitizer.cpp
   EfficiencySanitizer.cpp
   HWAddressSanitizer.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
 
   DEPENDS
   intrinsics_gen
   )

lib/Transforms/Instrumentation/InstrOrderFile.cpp

+//===- 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 <fstream>
+#include <map>
+#include <set>
+#include <sstream>
+
+using namespace llvm;
+#define DEBUG_TYPE "instrorderfile"
+
+static cl::opt<std::string> 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<std::mutex> 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();
+}

lib/Transforms/Instrumentation/Instrumentation.cpp

void llvm::initializeInstrumentation(PassRegistry &Registry) {
   initializeModuleAddressSanitizerLegacyPassPass(Registry);
   initializeBoundsCheckingLegacyPassPass(Registry);
   initializeControlHeightReductionLegacyPassPass(Registry);
   initializeGCOVProfilerLegacyPassPass(Registry);
   initializePGOInstrumentationGenLegacyPassPass(Registry);
   initializePGOInstrumentationUseLegacyPassPass(Registry);
   initializePGOIndirectCallPromotionLegacyPassPass(Registry);
   initializePGOMemOPSizeOptLegacyPassPass(Registry);
+  initializeInstrOrderFileLegacyPassPass(Registry);
   initializeInstrProfilingLegacyPassPass(Registry);
   initializeMemorySanitizerLegacyPassPass(Registry);
   initializeHWAddressSanitizerPass(Registry);
   initializeThreadSanitizerLegacyPassPass(Registry);
   initializeSanitizerCoverageModulePass(Registry);
   initializeDataFlowSanitizerPass(Registry);
   initializeEfficiencySanitizerPass(Registry);
 }
 
 /// LLVMInitializeInstrumentation - C binding for
 /// initializeInstrumentation.
 void LLVMInitializeInstrumentation(LLVMPassRegistryRef R) {
   initializeInstrumentation(*unwrap(R));
 }

test/Instrumentation/InstrOrderFile/basic.ll

+; 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]]