Perform InstructioinCombiningPass before SampleProfile pass.

[danielcdh]

Summary

SampleProfile pass needs to be performed after InstructionCombiningPass, which helps eliminate un-inlinable function calls.

[dnovillo]

Could you give me a bit more context? A C/C++ motivating example would be great. I think I follow what the intent is, but I'd like to make sure and leave it documented in the commit log.

Thanks.

test/Transforms/SampleProfile/cov-zero-samples.ll

3

Why did the discriminators change here? Was this because of instcombine? What did it do?

test/Transforms/SampleProfile/inline-coverage.ll

19

Likewise here. Why did the discriminators change?

[danielcdh]

In D17742#365240, @dnovillo wrote:

Could you give me a bit more context? A C/C++ motivating example would be great. I think I follow what the intent is, but I'd like to make sure and leave it documented in the commit log.

Thanks.

This is observed from compiling clang (FoldingSet) itself. The function is llvm::FoldingSetNodeID::~FoldingSetNodeID()

opt -S FoldingSet.bc |grep "call.*bit"

call void bitcast (void (%"class.llvm::SmallVectorImpl"*)* @_ZN4llvm15SmallVectorImplIjED2Ev to void (%"class.llvm::SmallVector"*)*)(%"class.llvm::SmallVector"* %3) #7, !dbg !4175

I just spent ~2 hours to generate a small C++ file to produce this "call with bitcast" pattern, but whatever I tried, front end will not give me exactly the same pattern. Shall I just keep the record in the commit log about how to reproduce with FoldingSet.bc?

test/Transforms/SampleProfile/cov-zero-samples.ll

3

This is not changing discriminator but column number.
inst-combine optimized the code to combine some instructions together and used the LOC of one instruction as the new instruction's LOC.

test/Transforms/SampleProfile/inline-coverage.ll

19

Same as above.

[danielcdh]

With the patch, the AutoFDO compile time for the entire clang increased from 190min to 192min (user time), the it's ~1% increase

include/llvm/Transforms/InstCombine/InstCombine.h

public:
   InstCombinePass &operator=(InstCombinePass &&RHS) {
     Worklist = std::move(RHS.Worklist);
     return *this;
   }
 
   PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
 };
 
+/// \brief The legacy pass manager's instcombine pass.
+///
+/// This is a basic whole-function wrapper around the instcombine utility. It
+/// will try to combine all instructions in the function.
+class InstructionCombiningPass : public FunctionPass {
+  InstCombineWorklist Worklist;
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+
+  InstructionCombiningPass() : FunctionPass(ID) {
+    initializeInstructionCombiningPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  bool runOnFunction(Function &F) override;
+};
 }
 
 #endif

lib/Transforms/IPO/SampleProfile.cpp

 #include "llvm/ProfileData/SampleProfReader.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/InstCombine/InstCombine.h"
 #include <cctype>
 
 using namespace llvm;
 using namespace sampleprof;
 
 #define DEBUG_TYPE "sample-profile"
 
 // Command line option to specify the file to read samples from. This is
public:
 
   void dump() { Reader->dump(); }
 
   const char *getPassName() const override { return "Sample profile pass"; }
 
   bool runOnModule(Module &M) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.setPreservesCFG();
+    AU.addRequired<InstructionCombiningPass>();
   }
 
 protected:
   bool runOnFunction(Function &F);
   unsigned getFunctionLoc(Function &F);
   bool emitAnnotations(Function &F);
   ErrorOr<uint64_t> getInstWeight(const Instruction &I) const;
   ErrorOr<uint64_t> getBlockWeight(const BasicBlock *BB) const;
bool SampleProfileLoader::emitAnnotations(Function &F) {
   }
   return Changed;
 }
 
 char SampleProfileLoader::ID = 0;
 INITIALIZE_PASS_BEGIN(SampleProfileLoader, "sample-profile",
                       "Sample Profile loader", false, false)
 INITIALIZE_PASS_DEPENDENCY(AddDiscriminators)
+INITIALIZE_PASS_DEPENDENCY(InstructionCombiningPass)
 INITIALIZE_PASS_END(SampleProfileLoader, "sample-profile",
                     "Sample Profile loader", false, false)
 
 bool SampleProfileLoader::doInitialization(Module &M) {
   auto &Ctx = M.getContext();
   auto ReaderOrErr = SampleProfileReader::create(Filename, Ctx);
   if (std::error_code EC = ReaderOrErr.getError()) {
     std::string Msg = "Could not open profile: " + EC.message();
if (!F.isDeclaration()) {
       clearFunctionData();
       retval |= runOnFunction(F);
     }
   return retval;
 }
 
 bool SampleProfileLoader::runOnFunction(Function &F) {
   F.setEntryCount(0);
+  getAnalysis<InstructionCombiningPass>(F);
   Samples = Reader->getSamplesFor(F);
   if (!Samples->empty())
     return emitAnnotations(F);
   return false;
 }

lib/Transforms/InstCombine/InstructionCombining.cpp

PreservedAnalyses InstCombinePass::run(Function &F,
 
   // Mark all the analyses that instcombine updates as preserved.
   // FIXME: Need a way to preserve CFG analyses here!
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   return PA;
 }
 
-namespace {
-/// \brief The legacy pass manager's instcombine pass.
-///
-/// This is a basic whole-function wrapper around the instcombine utility. It
-/// will try to combine all instructions in the function.
-class InstructionCombiningPass : public FunctionPass {
-  InstCombineWorklist Worklist;
-
-public:
-  static char ID; // Pass identification, replacement for typeid
-
-  InstructionCombiningPass() : FunctionPass(ID) {
-    initializeInstructionCombiningPassPass(*PassRegistry::getPassRegistry());
-  }
-
-  void getAnalysisUsage(AnalysisUsage &AU) const override;
-  bool runOnFunction(Function &F) override;
-};
-}
-
 void InstructionCombiningPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
   AU.addRequired<AAResultsWrapperPass>();
   AU.addRequired<AssumptionCacheTracker>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
   AU.addRequired<DominatorTreeWrapperPass>();
   AU.addPreserved<DominatorTreeWrapperPass>();
   AU.addPreserved<AAResultsWrapperPass>();

test/Transforms/SampleProfile/Inputs/inline-combine.prof

+foo:1000:1000
+ 1: bar:1000

test/Transforms/SampleProfile/calls.ll

 while.body:                                       ; preds = %while.cond
   %1 = load i32, i32* %i, align 4, !dbg !16
   %cmp1 = icmp ne i32 %1, 100, !dbg !16
   br i1 %cmp1, label %if.then, label %if.else, !dbg !16
 ; Without discriminator information, the profiler used to think that
 ; both branches out of while.body had the same weight. In reality,
 ; the edge while.body->if.then is taken most of the time.
 ;
-; CHECK: edge while.body -> if.then probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 ; CHECK: edge while.body -> if.else probability is 0x00000000 / 0x80000000 = 0.00%
+; CHECK: edge while.body -> if.then probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 
 if.then:                                          ; preds = %while.body
   %2 = load i32, i32* %i, align 4, !dbg !18
   %3 = load i32, i32* %s, align 4, !dbg !18
   %call = call i32 @_Z3sumii(i32 %2, i32 %3), !dbg !18
   store i32 %call, i32* %s, align 4, !dbg !18
   br label %if.end, !dbg !18

test/Transforms/SampleProfile/cov-zero-samples.ll

 ; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/cov-zero-samples.prof -sample-profile-check-record-coverage=100 -pass-remarks=sample-profile -o /dev/null 2>&1 | FileCheck %s
 ;
-; CHECK: remark: cov-zero-samples.cc:9:25: Applied 404065 samples from profile (offset: 2.1)
+; CHECK: remark: cov-zero-samples.cc:9:29: Applied 404065 samples from profile (offset: 2.1)
 ; CHECK: remark: cov-zero-samples.cc:10:9: Applied 443089 samples from profile (offset: 3)
 ; CHECK: remark: cov-zero-samples.cc:10:36: Applied 0 samples from profile (offset: 3.1)
 ; CHECK: remark: cov-zero-samples.cc:11:12: Applied 404066 samples from profile (offset: 4)
 ; CHECK: remark: cov-zero-samples.cc:13:25: Applied 0 samples from profile (offset: 6)
 ; CHECK: remark: cov-zero-samples.cc:14:3: Applied 0 samples from profile (offset: 7)
 ; CHECK: remark: cov-zero-samples.cc:10:9: most popular destination for conditional branches at cov-zero-samples.cc:9:3
 ; CHECK: remark: cov-zero-samples.cc:11:12: most popular destination for conditional branches at cov-zero-samples.cc:10:9
 ;

test/Transforms/SampleProfile/inline-combine.ll

+; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/inline-combine.prof -S | FileCheck %s
+
+%"class.llvm::FoldingSetNodeID" = type { %"class.llvm::SmallVector" }
+%"class.llvm::SmallVector" = type { %"class.llvm::SmallVectorImpl.base", %"struct.llvm::SmallVectorStorage" }
+%"class.llvm::SmallVectorImpl.base" = type { %"class.llvm::SmallVectorTemplateBase.base" }
+%"class.llvm::SmallVectorTemplateBase.base" = type { %"class.llvm::SmallVectorTemplateCommon.base" }
+%"class.llvm::SmallVectorTemplateCommon.base" = type <{ %"class.llvm::SmallVectorBase", %"struct.llvm::AlignedCharArrayUnion" }>
+%"class.llvm::SmallVectorBase" = type { i8*, i8*, i8* }
+%"struct.llvm::AlignedCharArrayUnion" = type { %"struct.llvm::AlignedCharArray" }
+%"struct.llvm::AlignedCharArray" = type { [4 x i8] }
+%"struct.llvm::SmallVectorStorage" = type { [31 x %"struct.llvm::AlignedCharArrayUnion"] }
+%"class.llvm::SmallVectorImpl" = type { %"class.llvm::SmallVectorTemplateBase.base", [4 x i8] }
+
+$foo = comdat any
+
+$bar = comdat any
+
+define void @foo(%"class.llvm::FoldingSetNodeID"* %this) comdat align 2 !dbg !3 {
+  %1 = alloca %"class.llvm::FoldingSetNodeID"*, align 8
+  store %"class.llvm::FoldingSetNodeID"* %this, %"class.llvm::FoldingSetNodeID"** %1, align 8
+  %2 = load %"class.llvm::FoldingSetNodeID"*, %"class.llvm::FoldingSetNodeID"** %1, align 8
+  %3 = getelementptr inbounds %"class.llvm::FoldingSetNodeID", %"class.llvm::FoldingSetNodeID"* %2, i32 0, i32 0
+; the call should have been inlined after sample-profile pass
+; CHECK-NOT: call
+  call void bitcast (void (%"class.llvm::SmallVectorImpl"*)* @bar to void (%"class.llvm::SmallVector"*)*)(%"class.llvm::SmallVector"* %3), !dbg !7
+  ret void
+}
+
+define void @bar(%"class.llvm::SmallVectorImpl"* %this) comdat align 2 !dbg !8 {
+  ret void
+}
+
+!llvm.module.flags = !{!0, !1}
+!llvm.ident = !{!2}
+
+!0 = !{i32 2, !"Dwarf Version", i32 4}
+!1 = !{i32 1, !"Debug Info Version", i32 3}
+!2 = !{!"clang version 3.5 "}
+!3 = distinct !DISubprogram(name: "foo", scope: !4, file: !4, line: 3, type: !5, isLocal: false, isDefinition: true, scopeLine: 3, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, variables: !6)
+!4 = !DIFile(filename: "test.cc", directory: ".")
+!5 = !DISubroutineType(types: !6)
+!6 = !{}
+!7 = !DILocation(line: 4, scope: !3)
+!8 = distinct !DISubprogram(name: "bar", scope: !4, file: !4, line: 7, type: !5, isLocal: false, isDefinition: true, scopeLine: 7, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, variables: !6)

test/Transforms/SampleProfile/inline-coverage.ll

 ;     7    int main() {
 ;     8      long long int sum = 0;
 ;     9      for (int i = 0; i < 200000 * 3000; i++)
 ;    10        sum += foo(i);
 ;    11      return sum > 0 ? 0 : 1;
 ;    12    }
 ;
 ; CHECK: remark: coverage.cc:10:12: inlined hot callee '_Z3fool' with 172746 samples into 'main'
-; CHECK: remark: coverage.cc:9:19: Applied 23478 samples from profile (offset: 2.1)
+; CHECK: remark: coverage.cc:9:21: Applied 23478 samples from profile (offset: 2.1)
 ; CHECK: remark: coverage.cc:10:16: Applied 23478 samples from profile (offset: 3)
 ; CHECK: remark: coverage.cc:4:10: Applied 31878 samples from profile (offset: 1)
 ; CHECK: remark: coverage.cc:11:10: Applied 0 samples from profile (offset: 4)
 ; CHECK: remark: coverage.cc:10:16: most popular destination for conditional branches at coverage.cc:9:3
 ;
 ; There is one sample record with 0 samples at offset 4 in main() that we never
 ; use:
 ; CHECK: warning: coverage.cc:7: 4 of 5 available profile records (80%) were applied