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

682

should probably remove mentioning of Pika here.

695

Same here.

746

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

752

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

751

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

80

Should define macro in InstProfData.inc file.

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

87

Same here.

147

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

147

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

147

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

 /* 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
 /* Win32 */
 #define INSTR_PROF_DATA_COFF .lprfd
 #define INSTR_PROF_NAME_COFF .lprfn
 #define INSTR_PROF_CNTS_COFF .lprfc
 #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.  */
 #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_DATA_COMMON
 #define INSTR_PROF_NAME_SECT_NAME INSTR_PROF_NAME_COMMON
 #define INSTR_PROF_CNTS_SECT_NAME 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_VALS_COMMON
 /* 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                                          \
   INSTR_PROF_QUOTE(INSTR_PROF_DATA_SECT_NAME)
 #define INSTR_PROF_NAME_SECT_NAME_STR                                          \
   INSTR_PROF_QUOTE(INSTR_PROF_NAME_SECT_NAME)
 #define INSTR_PROF_CNTS_SECT_NAME_STR                                          \
   INSTR_PROF_QUOTE(INSTR_PROF_CNTS_SECT_NAME)
 #define INSTR_PROF_COVMAP_SECT_NAME_STR                                        \
   INSTR_PROF_QUOTE(INSTR_PROF_COVMAP_SECT_NAME)
 #define INSTR_PROF_VALS_SECT_NAME_STR                                          \
   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
  * INSTR_PROF_SECT_START(INSTR_PROF_DATA_SECT_NAME) will
  * expand to __start___llvm_prof_data
  */
 #define INSTR_PROF_SECT_START(Sect) \
         INSTR_PROF_CONCAT(__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.
 ModulePass *createInstrProfilingLegacyPass(
     const InstrProfOptions &Options = InstrProfOptions());
 
+ModulePass *createInstrOrderFilePass();
+
 // Insert AddressSanitizer (address sanity checking) instrumentation
 FunctionPass *createAddressSanitizerFunctionPass(bool CompileKernel = false,
                                                  bool Recover = false,
                                                  bool UseAfterScope = false);
 ModulePass *createAddressSanitizerModulePass(bool CompileKernel = false,
                                              bool Recover = false,
                                              bool UseGlobalsGC = true,
                                              bool UseOdrIndicator = true);

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/SyntheticCountsPropagation.h"
 #include "llvm/Transforms/IPO/WholeProgramDevirt.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
 #include "llvm/Transforms/Instrumentation.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/Scalar/ADCE.h"
 #include "llvm/Transforms/Scalar/AlignmentFromAssumptions.h"
 #include "llvm/Transforms/Scalar/BDCE.h"
 #include "llvm/Transforms/Scalar/CallSiteSplitting.h"
 #include "llvm/Transforms/Scalar/ConstantHoisting.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;
 
 static bool isOptimizingForSize(PassBuilder::OptimizationLevel Level) {
   switch (Level) {
   case PassBuilder::O0:
   case PassBuilder::O1:
   case PassBuilder::O2:
   case PassBuilder::O3:
     return false;

 PassBuilder::buildModuleOptimizationPipeline(OptimizationLevel Level,
                                              bool DebugLogging) {
   ModulePassManager MPM(DebugLogging);
 
   // Optimize globals now that the module is fully simplified.
   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)
     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

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> EnableGVNSink(
     "enable-gvn-sink", cl::init(false), cl::Hidden,
     cl::desc("Enable the GVN sinking pass (default = off)"));
 
 static cl::opt<bool>
     EnableCHR("enable-chr", cl::init(true), cl::Hidden,
               cl::desc("Enable control height reduction optimization (CHR)"));
 
+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;
void PassManagerBuilder::populateModulePassManager(
   addExtensionsToPM(EP_CGSCCOptimizerLate, MPM);
   addFunctionSimplificationPasses(MPM);
 
   // FIXME: This is a HACK! The inliner pass above implicitly creates a CGSCC
   // pass manager that we are specifically trying to avoid. To prevent this
   // 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());
 
   if (OptLevel > 1 && !PrepareForLTO && !PrepareForThinLTO)
     // Remove avail extern fns and globals definitions if 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

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> 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<std::mutex> 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();
+}

lib/Transforms/Instrumentation/Instrumentation.cpp

void llvm::initializeInstrumentation(PassRegistry &Registry) {
   initializeAddressSanitizerModulePass(Registry);
   initializeBoundsCheckingLegacyPassPass(Registry);
   initializeControlHeightReductionLegacyPassPass(Registry);
   initializeGCOVProfilerLegacyPassPass(Registry);
   initializePGOInstrumentationGenLegacyPassPass(Registry);
   initializePGOInstrumentationUseLegacyPassPass(Registry);
   initializePGOIndirectCallPromotionLegacyPassPass(Registry);
   initializePGOMemOPSizeOptLegacyPassPass(Registry);
+  initializeInstrOrderFileLegacyPassPass(Registry);
   initializeInstrProfilingLegacyPassPass(Registry);
   initializeMemorySanitizerLegacyPassPass(Registry);
   initializeHWAddressSanitizerPass(Registry);
   initializeThreadSanitizerPass(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: @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]]