Add a counter-function insertion pass

[hfinkel]

Summary

As discussed in D22666, our current mechanism to support -pg profiling, where we insert calls to mcount(), or some similar function, is fundamentally broken. We insert these calls in the frontend, which means they get duplicated when inlining, and so the accumulated execution counts for the inlined-into functions are wrong.

Because we don't want the presence of these functions to affect optimizaton, they should be inserted in the backend. Here's a pass which would do just that. The knowledge of the name of the counting function lives in the frontend, so I'm passing it here as a function attribute. This should be easy to add in the frontend, work correctly with LTO, etc.

[hfinkel]

@majnemer pointed out on IRC that this pass does not preserve all analyses. Here's a more-refined version (it currently does not matter what we do here, since CGP will run afterward, and that does not preserve anything; since we use AA in the backend, I've just included GlobalsAA preservation for good measure).

[rjmccall]

This seems like the right approach to me; I won't review the pass parts, though. Should we do this + the change to actually start setting the flags in one patch?

lib/CodeGen/TargetPassConfig.cpp

474 ↗

(On Diff #65566)

This should only be added if the flag to add the attributes is enabled, right?

[hfinkel]

lib/CodeGen/TargetPassConfig.cpp

474 ↗

(On Diff #65566)

No, it always adds the pass. The pass just dosen't do anything if the function does not have the attribute. We don't want to predicate it on some CodeGen state because then it won't work with LTO.

[hfinkel]

In D22825#496546, @rjmccall wrote:

This seems like the right approach to me; I won't review the pass parts, though. Should we do this + the change to actually start setting the flags in one patch?

Do you prefer that? I generally prefer when people split the Clang and LLVM patches into separate reviews (especially when they're functionally separable). On other other hand, if we move everything to one git repository, single patches will be easier...

[rjmccall]

Ah, no, doing it separately is fine, then.

[honggyu.kim]

In D22825#496681, @rjmccall wrote:

In D22825#496680, @hfinkel wrote:

In D22825#496546, @rjmccall wrote:

This seems like the right approach to me; I won't review the pass parts, though. Should we do this + the change to actually start setting the flags in one patch?

Do you prefer that? I generally prefer when people split the Clang and LLVM patches into separate reviews (especially when they're functionally separable). On other other hand, if we move everything to one git repository, single patches will be easier...

Ah, no, doing it separately is fine, then.

Hi, I have tested it and it works great for the backend. Thanks for the patch!

[honggyu.kim]

And I think we should consider -finstrument-functions option as well. It inserts two functions both at the entry and exit. We maybe better to change the name 'CountingFunction' to something else to cover both cases. 'CountingEntryFunction' and 'CountingExitFunction' seems to be okay as well.

[hfinkel]

In D22825#497099, @honggyu.kim wrote:

And I think we should consider -finstrument-functions option as well. It inserts two functions both at the entry and exit. We maybe better to change the name 'CountingFunction' to something else to cover both cases. 'CountingEntryFunction' and 'CountingExitFunction' seems to be okay as well.

No, those are different. They're supposed to be duplicated upon inlining. The GCC manual says:

"This instrumentation is also done for functions expanded inline in other functions. The profiling calls will indicate where, conceptually, the inline function is entered and exited. This means that addressable versions of such functions must be available. If all your uses of a function are expanded inline, this may mean an additional expansion of code size. If you use `extern inline' in your C code, an addressable version of such functions must be provided."

So these can be be inserted in the frontend as they are now.

[honggyu.kim]

In D22825#497109, @hfinkel wrote:

In D22825#497099, @honggyu.kim wrote:

And I think we should consider -finstrument-functions option as well. It inserts two functions both at the entry and exit. We maybe better to change the name 'CountingFunction' to something else to cover both cases. 'CountingEntryFunction' and 'CountingExitFunction' seems to be okay as well.

No, those are different. They're supposed to be duplicated upon inlining. The GCC manual says:

"This instrumentation is also done for functions expanded inline in other functions. The profiling calls will indicate where, conceptually, the inline function is entered and exited. This means that addressable versions of such functions must be available. If all your uses of a function are expanded inline, this may mean an additional expansion of code size. If you use `extern inline' in your C code, an addressable version of such functions must be provided."

So these can be be inserted in the frontend as they are now.

I see. Thanks for the correction.

[honggyu.kim]

test/Transforms/CountingFunctionInserter/mcount.ll

26 ↗

(On Diff #65566)

Is there a reason that we have to explicitly provide name of "counting-function" attribute? Would it be better to get the name from TargetInfo? I need to find a way to get TargetInfo in FunctionPass first thought. I think we better not to increase target-dependency in IR level even if it's just attributes because mcount name is kind of target-dependent.

[hfinkel]

test/Transforms/CountingFunctionInserter/mcount.ll

26 ↗

(On Diff #65566)

Is there a reason that we have to explicitly provide name of "counting-function" attribute? Would it be better to get the name from TargetInfo?

Because the functionality might be useful for cases outside of -pg (and might even be useful for a tracing JIT), and there's no need to make a trivially-generalizable functionality artificially specific, I think it makes sense to make the function name something the IR-generator can specify.

I think we better not to increase target-dependency in IR level even if it's just attributes because mcount name is kind of target-dependent.

I'm fine with having a target-specific default. We'd move the current logic for setting the mcount name into initialize in lib/Analysis/TargetLibraryInfo.cpp - see, for example, the calls to TLI.setAvailableWithName in that function.

[honggyu.kim]

It works fine with D22666 now. Thanks for your help :)

[honggyu.kim]

Hi Hal,

I've just got commit access from Chris. Can you please commit this patch? I will also commit D22666 and D23792 as soon as you commit this.

Thanks,
Honggyu

[honggyu.kim]

I've also committed related patches. I really appreciate your help, Hal!

Honggyu

llvm/trunk/include/llvm/CodeGen/Passes.h

namespace llvm {
   /// createUnreachableBlockEliminationPass - The LLVM code generator does not
   /// work well with unreachable basic blocks (what live ranges make sense for a
   /// block that cannot be reached?).  As such, a code generator should either
   /// not instruction select unreachable blocks, or run this pass as its
   /// last LLVM modifying pass to clean up blocks that are not reachable from
   /// the entry block.
   FunctionPass *createUnreachableBlockEliminationPass();
 
+  /// Insert mcount-like function calls.
+  FunctionPass *createCountingFunctionInserterPass();
+
   /// MachineFunctionPrinter pass - This pass prints out the machine function to
   /// the given stream as a debugging tool.
   MachineFunctionPass *
   createMachineFunctionPrinterPass(raw_ostream &OS,
                                    const std::string &Banner ="");
 
   /// MIRPrinting pass - this pass prints out the LLVM IR into the given stream
   /// using the MIR serialization format.

llvm/trunk/include/llvm/InitializePasses.h

 void initializeCFGViewerPass(PassRegistry&);
 void initializeCFLAndersAAWrapperPassPass(PassRegistry&);
 void initializeCFLSteensAAWrapperPassPass(PassRegistry&);
 void initializeCallGraphDOTPrinterPass(PassRegistry&);
 void initializeCallGraphPrinterLegacyPassPass(PassRegistry&);
 void initializeCallGraphViewerPass(PassRegistry&);
 void initializeCallGraphWrapperPassPass(PassRegistry &);
 void initializeCodeGenPreparePass(PassRegistry&);
+void initializeCountingFunctionInserterPass(PassRegistry&);
 void initializeConstantHoistingLegacyPassPass(PassRegistry&);
 void initializeConstantMergeLegacyPassPass(PassRegistry &);
 void initializeConstantPropagationPass(PassRegistry&);
 void initializeCorrelatedValuePropagationPass(PassRegistry&);
 void initializeCostModelAnalysisPass(PassRegistry&);
 void initializeCrossDSOCFIPass(PassRegistry&);
 void initializeDAEPass(PassRegistry&);
 void initializeDAHPass(PassRegistry&);

llvm/trunk/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createStripDeadDebugInfoPass();
       (void) llvm::createStripDeadPrototypesPass();
       (void) llvm::createTailCallEliminationPass();
       (void) llvm::createJumpThreadingPass();
       (void) llvm::createUnifyFunctionExitNodesPass();
       (void) llvm::createInstCountPass();
       (void) llvm::createConstantHoistingPass();
       (void) llvm::createCodeGenPreparePass();
+      (void) llvm::createCountingFunctionInserterPass();
       (void) llvm::createEarlyCSEPass();
       (void) llvm::createGVNHoistPass();
       (void) llvm::createMergedLoadStoreMotionPass();
       (void) llvm::createGVNPass();
       (void) llvm::createMemCpyOptPass();
       (void) llvm::createLoopDeletionPass();
       (void) llvm::createPostDomTree();
       (void) llvm::createInstructionNamerPass();

llvm/trunk/lib/CodeGen/CMakeLists.txt

 add_llvm_library(LLVMCodeGen
   AggressiveAntiDepBreaker.cpp
   AllocationOrder.cpp
   Analysis.cpp
   AtomicExpandPass.cpp
   BasicTargetTransformInfo.cpp
   BranchFolding.cpp
   BuiltinGCs.cpp
   CalcSpillWeights.cpp
   CallingConvLower.cpp
   CodeGen.cpp
   CodeGenPrepare.cpp
+  CountingFunctionInserter.cpp
   CriticalAntiDepBreaker.cpp
   DeadMachineInstructionElim.cpp
   DetectDeadLanes.cpp
   DFAPacketizer.cpp
   DwarfEHPrepare.cpp
   EarlyIfConversion.cpp
   EdgeBundles.cpp
   ExecutionDepsFix.cpp

llvm/trunk/lib/CodeGen/CodeGen.cpp

 
 using namespace llvm;
 
 /// initializeCodeGen - Initialize all passes linked into the CodeGen library.
 void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeAtomicExpandPass(Registry);
   initializeBranchFolderPassPass(Registry);
   initializeCodeGenPreparePass(Registry);
+  initializeCountingFunctionInserterPass(Registry);
   initializeDeadMachineInstructionElimPass(Registry);
   initializeDetectDeadLanesPass(Registry);
   initializeDwarfEHPreparePass(Registry);
   initializeEarlyIfConverterPass(Registry);
   initializeExpandISelPseudosPass(Registry);
   initializeExpandPostRAPass(Registry);
   initializeFinalizeMachineBundlesPass(Registry);
   initializeFuncletLayoutPass(Registry);

llvm/trunk/lib/CodeGen/CountingFunctionInserter.cpp

+//===- CountingFunctionInserter.cpp - Insert mcount-like function calls ---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Insert calls to counter functions, such as mcount, intended to be called
+// once per function, at the beginning of each function.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Type.h"
+#include "llvm/Pass.h"
+using namespace llvm;
+
+namespace {
+  struct CountingFunctionInserter : public FunctionPass {
+    static char ID; // Pass identification, replacement for typeid
+    CountingFunctionInserter() : FunctionPass(ID) {
+      initializeCountingFunctionInserterPass(*PassRegistry::getPassRegistry());
+    }
+    
+    void getAnalysisUsage(AnalysisUsage &AU) const override {
+      AU.addPreserved<GlobalsAAWrapperPass>();
+    }
+
+    bool runOnFunction(Function &F) override {
+      std::string CountingFunctionName =
+        F.getFnAttribute("counting-function").getValueAsString();
+      if (CountingFunctionName.empty())
+        return false;
+
+      Type *VoidTy = Type::getVoidTy(F.getContext());
+      Constant *CountingFn =
+        F.getParent()->getOrInsertFunction(CountingFunctionName,
+                                           VoidTy, nullptr);
+      CallInst::Create(CountingFn, "", &*F.begin()->getFirstInsertionPt());
+      return true;
+    }
+  };
+  
+  char CountingFunctionInserter::ID = 0;
+}
+
+INITIALIZE_PASS(CountingFunctionInserter, "cfinserter", 
+                "Inserts calls to mcount-like functions", false, false)
+
+//===----------------------------------------------------------------------===//
+//
+// CountingFunctionInserter - Give any unnamed non-void instructions "tmp" names.
+//
+FunctionPass *llvm::createCountingFunctionInserterPass() {
+  return new CountingFunctionInserter();
+}

llvm/trunk/lib/CodeGen/TargetPassConfig.cpp

void TargetPassConfig::addIRPasses() {
   addPass(createUnreachableBlockEliminationPass());
 
   // Prepare expensive constants for SelectionDAG.
   if (getOptLevel() != CodeGenOpt::None && !DisableConstantHoisting)
     addPass(createConstantHoistingPass());
 
   if (getOptLevel() != CodeGenOpt::None && !DisablePartialLibcallInlining)
     addPass(createPartiallyInlineLibCallsPass());
+
+  // Insert calls to mcount-like functions.
+  addPass(createCountingFunctionInserterPass());
 }
 
 /// Turn exception handling constructs into something the code generators can
 /// handle.
 void TargetPassConfig::addPassesToHandleExceptions() {
   const MCAsmInfo *MCAI = TM->getMCAsmInfo();
   assert(MCAI && "No MCAsmInfo");
   switch (MCAI->getExceptionHandlingType()) {

llvm/trunk/test/CodeGen/PowerPC/mcount-insertion.ll

+; RUN: llc < %s | FileCheck %s
+target datalayout = "E-m:e-i64:64-n32:64"
+target triple = "powerpc64-bgq-linux"
+
+define void @test1() #0 {
+entry:
+  ret void
+
+; CHECK-LABEL: @test1
+; CHECK: bl mcount
+; CHECK-NOT: mcount
+; CHECK: blr
+}
+
+attributes #0 = { "counting-function"="mcount" }
+

llvm/trunk/test/Transforms/CountingFunctionInserter/mcount.ll

+; RUN: opt -S -cfinserter < %s | FileCheck %s
+target datalayout = "E-m:e-i64:64-n32:64"
+target triple = "powerpc64-bgq-linux"
+
+define void @test1() #0 {
+entry:
+  ret void
+
+; CHECK-LABEL: define void @test1()
+; CHECK: entry:
+; CHECK-NEXT: call void @mcount()
+; CHECK: ret void
+}
+
+define void @test2() #1 {
+entry:
+  ret void
+
+; CHECK-LABEL: define void @test2()
+; CHECK: entry:
+; CHECK-NEXT: call void @.mcount()
+; CHECK: ret void
+}
+
+attributes #0 = { "counting-function"="mcount" }
+attributes #1 = { "counting-function"=".mcount" }
+

llvm/trunk/tools/llc/llc.cpp

int main(int argc, char **argv) {
 
   // Initialize codegen and IR passes used by llc so that the -print-after,
   // -print-before, and -stop-after options work.
   PassRegistry *Registry = PassRegistry::getPassRegistry();
   initializeCore(*Registry);
   initializeCodeGen(*Registry);
   initializeLoopStrengthReducePass(*Registry);
   initializeLowerIntrinsicsPass(*Registry);
+  initializeCountingFunctionInserterPass(*Registry);
   initializeUnreachableBlockElimLegacyPassPass(*Registry);
 
   // Register the target printer for --version.
   cl::AddExtraVersionPrinter(TargetRegistry::printRegisteredTargetsForVersion);
 
   cl::ParseCommandLineOptions(argc, argv, "llvm system compiler\n");
 
   Context.setDiscardValueNames(DiscardValueNames);

llvm/trunk/tools/opt/opt.cpp

int main(int argc, char **argv) {
   initializeRewriteSymbolsLegacyPassPass(Registry);
   initializeWinEHPreparePass(Registry);
   initializeDwarfEHPreparePass(Registry);
   initializeSafeStackPass(Registry);
   initializeSjLjEHPreparePass(Registry);
   initializePreISelIntrinsicLoweringLegacyPassPass(Registry);
   initializeGlobalMergePass(Registry);
   initializeInterleavedAccessPass(Registry);
+  initializeCountingFunctionInserterPass(Registry);
   initializeUnreachableBlockElimLegacyPassPass(Registry);
 
 #ifdef LINK_POLLY_INTO_TOOLS
   polly::initializePollyPasses(Registry);
 #endif
 
   cl::ParseCommandLineOptions(argc, argv,
     "llvm .bc -> .bc modular optimizer and analysis printer\n");