[hot-cold-split] fix static analysis of cold regions

[sebpop]

Summary

Make the code of blockEndsInUnreachable to match the function
blockEndsInUnreachable in CodeGen/BranchFolding.cpp. I also have
added a note to make sure the code of this function will not be
modified unless the back-end version is also modified.

An early return before outlining has been added to avoid
outlining the full function body when the first block in the
function is marked cold.

The static analysis of cold code has been amended to avoid
marking the whole function as cold by back-propagation
because the back-propagation would mark blocks with return
statements as cold.

The patch adds debug statements to help discover these problems.

[sebpop]

Before this patch we have a 10% regression in sqlite with hot-cold-split pass.
With this patch I now see a 3% speedup on sqlite vs. no hot-cold-split pass.

[sebpop]

Added an early return for outlining if function entry is cold.
Added a check for invoke calls: invoke should not be marked as cold by back propagation.

There are only a few cold regions that are now extracted with the static analysis of hot/cold blocks on a relatively large benchmark.
Through those extracted blocks there are some diamonds that do not contain much code.
We may want to avoid outlining a candidate cold region if the number of instructions in the region is too low.

[brzycki]

Hi @sebpop, I have a few comments inline regarding the function determining side effect status.

llvm/lib/Transforms/IPO/HotColdSplitting.cpp

150

Why is an Indirect branch considered a return? The instruction is required to branch to an address of a label within the current function.

I am also wondering about the EH TIs: catchswitch, resume, catchret, cleanupret. Should we just pessimize all EH code with:

if (I->isEHPad())
  return true;

154

Should we consider adding a per-instruction side-effect check?

if (I.mayHaveSideEffects())
  return true;

[tejohnson]

llvm/lib/Transforms/IPO/HotColdSplitting.cpp

105

Suggest copying in the explanatory header comments from there.

385

Suggest moving this check outside this loop. I.e. just check if Begin is cold and return early if so.

[sebpop]

I will post a patch to fix the comments from @tejohnson.

llvm/lib/Transforms/IPO/HotColdSplitting.cpp

150

Why is an Indirect branch considered a return?

This function is similar to blockEndsInUnreachable which is used to detect cold code for the forward propagation. The documentation of blockEndsInUnreachable says:

Also consider a block that ends in an indirect branch to be a return block, since many targets use plain indirect branches to return.

I am not sure why the back propagation should stop on an instruction which is I->isEHPad.

154

I would say no because

bool mayHaveSideEffects() const { return mayWriteToMemory() || mayThrow(); }

Code that stores to memory or that throws can be cold.

[sebpop]

Fix two comments from @tejohnson.

[tejohnson]

Are both fixes necessary to fix the issue (the one for back propagation and the one to bail out if the entry block is cold), or is either one sufficient? The patch description only mentions the former.

[sebpop]

Are both fixes necessary to fix the issue (the one for back propagation and the one to bail out if the entry block is cold), or is either one sufficient? The patch description only mentions the former.

I am not sure whether the entry block will get marked as cold after the two fixes to the forward and back propagation.
We could try to transform the early return into an assert that the entry block of a function is never marked cold.
I will test this change.

Thanks for your careful review of the patch!

[sebpop]

In D52904#1265841, @sebpop wrote:

Are both fixes necessary to fix the issue (the one for back propagation and the one to bail out if the entry block is cold), or is either one sufficient? The patch description only mentions the former.

We need both parts of the patch to fix the issue.

I am not sure whether the entry block will get marked as cold after the two fixes to the forward and back propagation.
We could try to transform the early return into an assert that the entry block of a function is never marked cold.
I will test this change.

Static analysis would mark the first block in the next function as cold:

define void @fun() {
entry:

unreachable

}

When the entry block is marked cold,
we need an early return before outlining the full function.

[hiraditya]

With this patch I now see a 3% speedup on sqlite vs. no hot-cold-split pass.

Awesome! Thanks for improving this!

[sebpop]

In D52904#1265893, @hiraditya wrote:

With this patch I now see a 3% speedup on sqlite vs. no hot-cold-split pass.

Awesome! Thanks for improving this!

I think the 3% uplift in performance is within the noise level.
At least with this patch I do not see the 10% regression in performance with hot/cold partitioning
which most likely was due to doubling the cost of function calls when the whole function was outlined.

[tejohnson]

This LGTM, but please wait for @brzycki

[hiraditya]

In D52904#1265895, @sebpop wrote:

In D52904#1265893, @hiraditya wrote:

With this patch I now see a 3% speedup on sqlite vs. no hot-cold-split pass.

Awesome! Thanks for improving this!

I think the 3% uplift in performance is within the noise level.
At least with this patch I do not see the 10% regression in performance with hot/cold partitioning
which most likely was due to doubling the cost of function calls when the whole function was outlined.

I think hot-cold splitting with function merging can help reduce code-size as well.

[orivej]

llvm/trunk/lib/Transforms/IPO/HotColdSplitting.cpp

153 ↗

(On Diff #169757)

This line fails to compile with g++ 5.4.0 with:

error: invalid conversion from 'const llvm::Instruction*' to 'const llvm::TerminatorInst*' [-fpermissive]

Did you mean const Instruction *I = BB.getTerminator();.

[sebpop]

Fixed in https://reviews.llvm.org/rL344566

[NoQ]

There seem to be more buildbot issues, eg. http://lab.llvm.org:8080/green/job/clang-stage1-cmake-RA-incremental/54221/console

: 'RUN: at line 1';   /Users/buildslave/jenkins/workspace/clang-stage1-cmake-RA-incremental/clang-build/bin/opt -hotcoldsplit -S < /Users/buildslave/jenkins/workspace/clang-stage1-cmake-RA-incremental/llvm/test/Transforms/HotColdSplit/split-out-dbg-val-of-arg.ll | /Users/buildslave/jenkins/workspace/clang-stage1-cmake-RA-incremental/clang-build/bin/FileCheck /Users/buildslave/jenkins/workspace/clang-stage1-cmake-RA-incremental/llvm/test/Transforms/HotColdSplit/split-out-dbg-val-of-arg.ll
--
Exit Code: 1

Command Output (stderr):
--
/Users/buildslave/jenkins/workspace/clang-stage1-cmake-RA-incremental/llvm/test/Transforms/HotColdSplit/split-out-dbg-val-of-arg.ll:3:16: error: CHECK-LABEL: expected string not found in input
; CHECK-LABEL: define {{.*}}@foo_if.end
               ^
<stdin>:1:1: note: scanning from here
; ModuleID = '<stdin>'
^
<stdin>:4:1: note: possible intended match here
define void @foo(i32 %arg1) !dbg !6 {
^

[sebpop]

In D52904#1266032, @NoQ wrote:

There seem to be more buildbot issues, eg. http://lab.llvm.org:8080/green/job/clang-stage1-cmake-RA-incremental/54221/console

Fixed in https://reviews.llvm.org/rL344577

[NoQ]

This helped, thanks!

[brzycki]

Nice work @sebpop. Here's a delayed "LGTM". :)

llvm/lib/Transforms/IPO/HotColdSplitting.cpp

for (auto I = df_begin(Entry), E = df_end(Entry); I != E;) {
     if (!DT->dominates(Entry, *I))
       return false;
     Region.push_back(*I);
     ++I;
   }
   return true;
 }
 
+// Same as blockEndsInUnreachable in CodeGen/BranchFolding.cpp. Do not modify
+// this function unless you modify the MBB version as well.
 bool blockEndsInUnreachable(const BasicBlock &BB) {
+  if (!succ_empty(&BB))
+    return false;
   if (BB.empty())
     return true;
   const TerminatorInst *I = BB.getTerminator();
-  if (isa<ReturnInst>(I) || isa<IndirectBrInst>(I))
-    return true;
-  // Unreachable blocks do not have any successor.
-  return succ_empty(&BB);
+  return !(isa<ReturnInst>(I) || isa<IndirectBrInst>(I));
 }
 
 static bool exceptionHandlingFunctions(const CallInst *CI) {
   auto F = CI->getCalledFunction();
   if (!F)
     return false;
   auto FName = F->getName();
   return FName == "__cxa_begin_catch" ||
          FName == "__cxa_free_exception" ||
          FName == "__cxa_allocate_exception" ||
          FName == "__cxa_begin_catch" ||
          FName == "__cxa_end_catch";
 }
 
-static
-bool unlikelyExecuted(const BasicBlock &BB) {
+static bool unlikelyExecuted(const BasicBlock &BB) {
   if (blockEndsInUnreachable(BB))
     return true;
   // Exception handling blocks are unlikely executed.
   if (BB.isEHPad())
     return true;
   for (const Instruction &I : BB)
     if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
       // The block is cold if it calls functions tagged as cold or noreturn.
       if (CI->hasFnAttr(Attribute::Cold) ||
           CI->hasFnAttr(Attribute::NoReturn) ||
           exceptionHandlingFunctions(CI))
         return true;
 
       // Assume that inline assembly is hot code.
       if (isa<InlineAsm>(CI->getCalledValue()))
         return false;
     }
   return false;
 }
 
+static bool returnsOrHasSideEffects(const BasicBlock &BB) {
+  const TerminatorInst *I = BB.getTerminator();
+  if (isa<ReturnInst>(I) || isa<IndirectBrInst>(I))
+    return true;
+
+  for (const Instruction &I : BB)
+    if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
+      if (CI->hasFnAttr(Attribute::NoReturn))
+        return true;
+
+      if (isa<InlineAsm>(CI->getCalledValue()))
+        return true;
+    }
+
+  return false;
+}
+
 static DenseSetBB getHotBlocks(Function &F) {
 
   // Mark all cold basic blocks.
   DenseSetBB ColdBlocks;
   for (BasicBlock &BB : F)
-    if (unlikelyExecuted(BB))
+    if (unlikelyExecuted(BB)) {
+      LLVM_DEBUG(llvm::dbgs() << "\nForward propagation marks cold: " << BB);
       ColdBlocks.insert((const BasicBlock *)&BB);
+    }
 
   // Forward propagation: basic blocks are hot when they are reachable from the
   // beginning of the function through a path that does not contain cold blocks.
   SmallVector<const BasicBlock *, 8> WL;
   DenseSetBB HotBlocks;
 
   const BasicBlock *It = &F.front();
   if (!ColdBlocks.count(It)) {
for (BasicBlock &BBRef : F) {
     }
   }
 
   while (WL.size() > 0) {
     It = WL.pop_back_val();
     if (ColdBlocks.count(It))
       continue;
 
+    // Do not back-propagate to blocks that return or have side effects.
+    if (returnsOrHasSideEffects(*It))
+      continue;
+
     // Move the block from HotBlocks to ColdBlocks.
+    LLVM_DEBUG(llvm::dbgs() << "\nBack propagation marks cold: " << *It);
     HotBlocks.erase(It);
     ColdBlocks.insert(It);
 
     // Iterate over the predecessors.
     for (const BasicBlock *Pred : predecessors(It)) {
       if (HotBlocks.count(Pred)) {
         NumHotSuccessors[Pred] -= 1;
 
const Function *HotColdSplitting::outlineColdBlocks(Function &F,
   // Walking the dominator tree allows us to find the largest
   // cold region.
   BasicBlock *Begin = DT->getRootNode()->getBlock();
   for (auto I = df_begin(Begin), E = df_end(Begin); I != E; ++I) {
     BasicBlock *BB = *I;
     if (PSI->isColdBB(BB, BFI) || !HotBlocks.count(BB)) {
       SmallVector<BasicBlock *, 4> ValidColdRegion, Region;
       BasicBlock *Exit = (*PDT)[BB]->getIDom()->getBlock();
       BasicBlock *ExitColdRegion = nullptr;
 
       // Estimated cold region between a BB and its dom-frontier.
       while (Exit && isSingleEntrySingleExit(BB, Exit, DT, PDT, Region) &&
              isOutlineCandidate(Region, Exit)) {
         ExitColdRegion = Exit;
         ValidColdRegion = Region;
         Region.clear();
         // Update Exit recursively to its dom-frontier.

llvm/test/Transforms/HotColdSplit/split-cold-1.ll

 ; RUN: opt -hotcoldsplit -S < %s | FileCheck %s
 ; RUN: opt -passes=hotcoldsplit -S < %s | FileCheck %s
 
-; Outlined function is called from a basic block named codeRepl
-; CHECK: codeRepl:
-; CHECK-NEXT: call void @foo
+; Check that the function is not split. Outlined function is called from a
+; basic block named codeRepl.
+
+; CHECK-LABEL: @foo
+; CHECK-NOT: codeRepl
 define void @foo() {
 entry:
   br i1 undef, label %if.then, label %if.end
 
 if.then:                                          ; preds = %entry
   unreachable
 
 if.end:                                           ; preds = %entry
   br label %if.then12
 
 if.then12:                                        ; preds = %if.end
   br label %cleanup40
 
 cleanup40:                                        ; preds = %if.then12
   br label %return
 
 return:                                           ; preds = %cleanup40
   ret void
 }
+
+; Check that the function is not split. We used to outline the full function.
+
+; CHECK-LABEL: @fun
+; CHECK-NOT: codeRepl
+
+define void @fun() {
+entry:
+  br i1 undef, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  br label %if.end
+
+if.end:                                           ; preds = %entry
+  ret void
+}

llvm/test/Transforms/HotColdSplit/split-cold-2.ll

 ; RUN: opt -hotcoldsplit -S < %s
 ; RUN: opt -passes=hotcoldsplit -S < %s
 
 ; Make sure this compiles. This test used to fail with an invalid phi node: the
 ; two predecessors were outlined and the SSA representation was invalid.
 
+; CHECK-LABEL: @fun
+; CHECK: codeRepl:
+; CHECK-NEXT: call void @fun_if.else
+
 define void @fun() {
 entry:
   br i1 undef, label %if.then, label %if.else
 
 if.then:
   unreachable
 
 if.else: