Avoid inlining in exception handling context

[junbuml]

Summary

It might be reasonably to avoid inlining CallSites invoked in
exception handling context so that we can reduce code size blow-up in
EH regions as well as indirectly increase inline opportunites for unwinding
functions containing exception handling code.

In this change, the NoInline attribute is added in CallSites
invoked specifically by the throw statement.

[hfinkel]

lib/Transforms/IPO/PruneEH.cpp

340

There's no need to require the bitcast here. What if you actually want an i8* as the exception type? You should just call stripPointerCasts instead.

[junbuml]

Addressed comments from Hal and make this check only once per module.

[hfinkel]

lib/Transforms/IPO/PruneEH.cpp

195

unwind -> unwinds

196

mark the -> mark them with the

199

You should MarkNoInlineInEHR = true; here instead of in AddNoinlineForCSInEH (no need to do the CGSCC traversal here to call functions that don't do anything).

Also, to maintain the general pass model, I think you need to override the pass's 'virtual bool doFinalization(Module &)' function and reset the MarkNoInlineInEHR flag to false.

[junbuml]

Addressed Philip's comments.
Thanks Philip for the review.

[junbuml]

Addressed comments from Hal.
Thanks Hal for the review!

lib/Transforms/IPO/PruneEH.cpp

340

Thanks Hal for the review.
I refactor this part into a separate function to trace bitcast from __cxa_allocate_exception().

[majnemer]

lib/Transforms/IPO/PruneEH.cpp

47

Please do not have a space between the variable and the parenthesis.

313

You can use auto *BCInst to avoid repetition.

313–315

Please use consistent bracing.

[junbuml]

Addressed comments from David.
Thanks David for the review !

[hfinkel]

lib/Transforms/IPO/PruneEH.cpp

79

As I understand it, you want this flag to apply per-module, not per run over the call graph. So you need to do this in 'bool doFinalization(Module &)', not in 'doFinalization(CallGraph &CG)' which is called at the end of the call graph's runOnModule function. If there's no functional difference, then you don't need the flag at all.

[majnemer]

Out of curiosity, why not handle this as an inline cost heuristic? I imagine we'd want to inline very trivial constructors.

lib/Transforms/IPO/PruneEH.cpp

308

NoInlie -> NoInline

358

Likewise, you can use auto * here.

363

And here.

[junbuml]

I agree that using the NoInline attribute will prevent even a trivial constructor from being inlined. Initially, I intended to use Attribute::Cold, but by default, Attribute::Cold doesn't seem to have any impact in inline heuristic because the current ColdThreshold is not tuned yet (r200898).

In my opinion, considering that CallSites in exception handling region is very cold is not unreasonable even without PGO, and avoiding inlining in exception handling region may not have significant impacts on performance unless a program execution logic is really depend on exception handling flows.

For now, I can add FIXME mentioning that Attribute::Cold could be used when the inline cold-threshold is tune. We could continue discussing any other options if using NoInline attribute is to strong to use here.

[junbuml]

lib/Transforms/IPO/PruneEH.cpp

79

As you mention, doFinalization(CallGraph &CG) is called at the end of runOnModule() of CGPassManager. Since doFinalization(CallGraph &CG) is called after all SCCs in the module has been processed, I believe this is called once per module.

[hfinkel]

For now, I can add FIXME mentioning that Attribute::Cold could be used when the inline cold-threshold is tune.

Please do. Actually, please add both attributes for now and make the FIXME to just use 'cold'. Even if the attribute does not do the right thing in the inliner, it does have the correct affect on MachineBlockPlacement, etc.

include/llvm/IR/CallSite.h

274–283

Why are you changing this?

lib/Transforms/IPO/PruneEH.cpp

79

Indeed, I agree.

[junbuml]

Addressed Hal's comments

• Add FIXME mentioning that Attribute::NoInline should be removed when the inline cold-threshold is tuned.
• Add both Attribute::NoInline and Attribute::Cold in CallSites for now.

[junbuml]

include/llvm/IR/CallSite.h

274–283

Both CallInst and InvokeInst have only setIsNoInline(); there is no setIsNoInline(bool) in both CallInst and InvokeInst. I believe it was bug.

[hfinkel]

lib/Transforms/IPO/PruneEH.cpp

203

Why do you 'break;' here? If you do that, you'll only visit the first function in each call graph.

I think you want to have:

if (!MarkColdInEHR && SCCMightUnwind) {
  MarkColdInEHR = true;
   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
     Function *F = (*I)->getFunction();
     if (!F)
       continue;

     AddColdForCSInEH(F);
  }
}

[junbuml]

lib/Transforms/IPO/PruneEH.cpp

203

As I comment above, AddColdForCSInEH() does not need to be performed multiple times for each function. Since it handle all CallSites for __cxa_throw() in a module, it should be called only once per module. That's also why I have MarkColdInEHR .

[hfinkel]

lib/Transforms/IPO/PruneEH.cpp

203

OIC, you don't really want to iterate over the call graph here at all; you're just trying to get the first function, any function, so that you can call getParent() to get the module.

Don't do that, just call CG.getModule().

[junbuml]

Yes, right.
Okay I will use CG.getModule(). Thanks Hal!

[hfinkel]

lib/Transforms/IPO/PruneEH.cpp

365

Why are you looking for users of cxa_throw? Can we make the assumption that all user of cxa_allocate_exception are essentially cold, and just look for the users of return values of that function?

[junbuml]

lib/Transforms/IPO/PruneEH.cpp

365

I'm trying to find all actual calls for __cxa_throw() by looking at the users of FnThrowE where an exception is thrown.

Here, I specifically check the exception allocated to be thrown (__cxa_throw()) in throw statement, which should be cold unless the program logic highly rely on throw statement.

When a exception handling class is created in throw statement,
the constructor must take the exception used in __cxa_throw() as its first parameter.

Please correct me if I miss something.

[hfinkel]

lib/Transforms/IPO/PruneEH.cpp

365

I understand what you're doing, but my question is this: Is the call to cxa_allocate_exception itself cold? If so, perhaps that's all we need to find. Maybe looking for the cxa_throw calls is an unnecessary complication.

[junbuml]

lib/Transforms/IPO/PruneEH.cpp

365

I believe cxa_allocate_exception() itself must be cold in almost all normal c++ program. But, I just wanted to make sure the exception allocated is actually used for throwing. If checking cxa_throw() doesn't make it too complicated, I believe there is no harm with it. I can also leave FIXME about it. Please let me know your thought!

[hfinkel]

lib/Transforms/IPO/PruneEH.cpp

365

I believe cxa_allocate_exception() itself must be cold in almost all normal c++ program. But, I just wanted to make sure the exception allocated is actually used for throwing. If checking cxa_throw() doesn't make it too complicated, I believe there is no harm with it. I can also leave FIXME about it. Please let me know your thought!

Okay.

Let me also ask something I should have asked in the very beginning: Why are you doing this here and not in Clang? It seems that, in Clang, it would be simple to have a piece of state that records whether we're in a throw statement or a catch block, and marks the call sites appropriately.

[junbuml]

lib/Transforms/IPO/PruneEH.cpp

365

I just wanted to place it somewhere exception handling specific pass, instead of directly touching inliner. If you believe Clang (ItaniumCXXABI.cpp ?) is better place I can do the same thing in there.

[hfinkel]

lib/Transforms/IPO/PruneEH.cpp

365

This might be really off base, but here's what I was thinking about last night...

We're trying to mark all callsites within throw statements (and catch blocks) as cold (noinline). This seems analogous to me to how we handle setting instruction fast-math flags, where we give the IRBuilder a default state, and change it based on scope information.

1. Give IRBuilder a new default state argument (along with DefaultFPMathTag/FMF) to indicate that all calls are cold (noinline).
2. In Clang, update CodeGenFunction::EmitCXXThrowExpr in lib/CodeGen/CGException.cpp to set/reset this default IRBuilder state around the rest of what it does.
3. To make the catch regions also have cold callsites, edit CodeGenFunction::ExitCXXTryStmt, and set/reset the default IRBuilder state around the loop over Handlers.

This seems like it might be both more general and simpler.

[junbuml]

Thanks Hal for the suggestion. I will take a look at this approach and get back to you soon.

[junbuml]

In this clang change, I added a state flag (bool IsColdRegion) in CodeGenFunction and set/reset the flag in EmitCXXThrowExpr(). In EmitCall(), the NoInline attribute would be added if IsColdRegion is true. As of now, this change only handles throw statements because I don't have any data / test for catch blocks yet.

[hfinkel]

You should start a new differential for this, so that you can get a clean summary e-mail with a description sent to cfe-commits. There's some overlap, but you'll also get potentially-different reviewers here.

[junbuml]

Move this clang change in http://reviews.llvm.org/D13304

include/llvm/Analysis/TargetLibraryInfo.def

 TLI_DEFINE_ENUM_INTERNAL(ZnwmRKSt9nothrow_t)
 TLI_DEFINE_STRING_INTERNAL("_ZnwmRKSt9nothrow_t")
 /// double __cospi(double x);
 TLI_DEFINE_ENUM_INTERNAL(cospi)
 TLI_DEFINE_STRING_INTERNAL("__cospi")
 /// float __cospif(float x);
 TLI_DEFINE_ENUM_INTERNAL(cospif)
 TLI_DEFINE_STRING_INTERNAL("__cospif")
+/// void* __cxa_allocate_exception(size_t thrown_size) throw();
+TLI_DEFINE_ENUM_INTERNAL(cxa_allocate_exception)
+TLI_DEFINE_STRING_INTERNAL("__cxa_allocate_exception")
 /// int __cxa_atexit(void (*f)(void *), void *p, void *d);
 TLI_DEFINE_ENUM_INTERNAL(cxa_atexit)
 TLI_DEFINE_STRING_INTERNAL("__cxa_atexit")
 /// void __cxa_guard_abort(guard_t *guard);
 /// guard_t is int64_t in Itanium ABI or int32_t on ARM eabi.
 TLI_DEFINE_ENUM_INTERNAL(cxa_guard_abort)
 TLI_DEFINE_STRING_INTERNAL("__cxa_guard_abort")
 /// int __cxa_guard_acquire(guard_t *guard);
 TLI_DEFINE_ENUM_INTERNAL(cxa_guard_acquire)
 TLI_DEFINE_STRING_INTERNAL("__cxa_guard_acquire")
 /// void __cxa_guard_release(guard_t *guard);
 TLI_DEFINE_ENUM_INTERNAL(cxa_guard_release)
 TLI_DEFINE_STRING_INTERNAL("__cxa_guard_release")
+/// void __cxa_throw(guard_t *guard);
+TLI_DEFINE_ENUM_INTERNAL(cxa_throw)
+TLI_DEFINE_STRING_INTERNAL("__cxa_throw")
 /// int __isoc99_scanf (const char *format, ...)
 TLI_DEFINE_ENUM_INTERNAL(dunder_isoc99_scanf)
 TLI_DEFINE_STRING_INTERNAL("__isoc99_scanf")
 /// int __isoc99_sscanf(const char *s, const char *format, ...)
 TLI_DEFINE_ENUM_INTERNAL(dunder_isoc99_sscanf)
 TLI_DEFINE_STRING_INTERNAL("__isoc99_sscanf")
 /// void *__memcpy_chk(void *s1, const void *s2, size_t n, size_t s1size);
 TLI_DEFINE_ENUM_INTERNAL(memcpy_chk)

include/llvm/IR/CallSite.h

#define CALLSITE_DELEGATE_SETTER(METHOD) \
   bool isNoBuiltin() const {
     CALLSITE_DELEGATE_GETTER(isNoBuiltin());
   }
 
   /// @brief Return true if the call should not be inlined.
   bool isNoInline() const {
     CALLSITE_DELEGATE_GETTER(isNoInline());
   }
-  void setIsNoInline(bool Value = true) {
-    CALLSITE_DELEGATE_SETTER(setIsNoInline(Value));
+  void setIsNoInline() {
+    CALLSITE_DELEGATE_SETTER(setIsNoInline());
+  }
+
+  /// @brief Return true if the call is cold.
+  bool isCold() const {
+    CALLSITE_DELEGATE_GETTER(isCold());
+  }
+  void setIsCold() {
+    CALLSITE_DELEGATE_SETTER(setIsCold());
   }
 
   /// @brief Determine if the call does not access memory.
   bool doesNotAccessMemory() const {
     CALLSITE_DELEGATE_GETTER(doesNotAccessMemory());
   }
   void setDoesNotAccessMemory() {
     CALLSITE_DELEGATE_SETTER(setDoesNotAccessMemory());

include/llvm/IR/Instructions.h

public:
   }
 
   /// \brief Return true if the call should not be inlined.
   bool isNoInline() const { return hasFnAttr(Attribute::NoInline); }
   void setIsNoInline() {
     addAttribute(AttributeSet::FunctionIndex, Attribute::NoInline);
   }
 
+  /// \brief Return true if the call is Cold.
+  bool isCold() const { return hasFnAttr(Attribute::Cold); }
+  void setIsCold() {
+    addAttribute(AttributeSet::FunctionIndex, Attribute::Cold);
+  }
+
   /// \brief Return true if the call can return twice
   bool canReturnTwice() const {
     return hasFnAttr(Attribute::ReturnsTwice);
   }
   void setCanReturnTwice() {
     addAttribute(AttributeSet::FunctionIndex, Attribute::ReturnsTwice);
   }
 
public:
   }
 
   /// \brief Return true if the call should not be inlined.
   bool isNoInline() const { return hasFnAttr(Attribute::NoInline); }
   void setIsNoInline() {
     addAttribute(AttributeSet::FunctionIndex, Attribute::NoInline);
   }
 
+  /// \brief Return true if the call is Cold.
+  bool isCold() const { return hasFnAttr(Attribute::Cold); }
+  void setIsCold() {
+    addAttribute(AttributeSet::FunctionIndex, Attribute::Cold);
+  }
+
   /// \brief Determine if the call does not access memory.
   bool doesNotAccessMemory() const {
     return hasFnAttr(Attribute::ReadNone);
   }
   void setDoesNotAccessMemory() {
     addAttribute(AttributeSet::FunctionIndex, Attribute::ReadNone);
   }
 

lib/Transforms/IPO/PruneEH.cpp

 #include "llvm/Transforms/IPO.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/LibCallSemantics.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include <algorithm>
 using namespace llvm;
 
 #define DEBUG_TYPE "prune-eh"
 
 STATISTIC(NumRemoved, "Number of invokes removed");
 STATISTIC(NumUnreach, "Number of noreturn calls optimized");
 
 namespace {
   struct PruneEH : public CallGraphSCCPass {
     static char ID; // Pass identification, replacement for typeid
-    PruneEH() : CallGraphSCCPass(ID) {
+    TargetLibraryInfo *TLI;
+    bool MarkColdInEHR;
+
+    PruneEH() : CallGraphSCCPass(ID), MarkColdInEHR(false) {
       initializePruneEHPass(*PassRegistry::getPassRegistry());
     }
 
     // runOnSCC - Analyze the SCC, performing the transformation if possible.
     bool runOnSCC(CallGraphSCC &SCC) override;
+    bool doFinalization(CallGraph &CG) override;
+    void getAnalysisUsage(AnalysisUsage &AU) const override;
 
     bool SimplifyFunction(Function *F);
     void DeleteBasicBlock(BasicBlock *BB);
+    void AddColdForCSInEH(Function *F);
+    void AddColdForEHAllocUsers(Value *EHAlloc, CallInst *EHAllocCall);
   };
 }
 
 char PruneEH::ID = 0;
 INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh",
                 "Remove unused exception handling info", false, false)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(PruneEH, "prune-eh",
                 "Remove unused exception handling info", false, false)
 
 Pass *llvm::createPruneEHPass() { return new PruneEH(); }
 
 
+void PruneEH::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<TargetLibraryInfoWrapperPass>();
+  CallGraphSCCPass::getAnalysisUsage(AU);
+}
+
+bool PruneEH::doFinalization(CallGraph &CG) {
+  MarkColdInEHR = false;
+  return false;
+}
+
 bool PruneEH::runOnSCC(CallGraphSCC &SCC) {
   SmallPtrSet<CallGraphNode *, 8> SCCNodes;
   CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
+  TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+
   bool MadeChange = false;
 
   // Fill SCCNodes with the elements of the SCC.  Used for quickly
   // looking up whether a given CallGraphNode is in this SCC.
   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
     SCCNodes.insert(*I);
 
   // First pass, scan all of the functions in the SCC, simplifying them
for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
           F->getContext(), AttributeSet::FunctionIndex, NewAttributes);
 
       if (PAL != NPAL) {
         MadeChange = true;
         F->addAttributes(AttributeSet::FunctionIndex, NPAL);
       }
     }
 
+  // If the SCC unwinds, find CallSites in exception handling regions,
+  // and mark them with the NoInline and Cold attributes. Note that this need
+  // to be performed only once per module.
+  if (!MarkColdInEHR && SCCMightUnwind)
+    for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
+      if (Function *F = (*I)->getFunction()) {
+        AddColdForCSInEH(F);
+        MarkColdInEHR = true;
+        break;
+      }
+
   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
     // Convert any invoke instructions to non-throwing functions in this node
     // into call instructions with a branch.  This makes the exception blocks
     // dead.
     if (Function *F = (*I)->getFunction())
       MadeChange |= SimplifyFunction(F);
   }
 
void PruneEH::DeleteBasicBlock(BasicBlock *BB) {
   // Get the list of successors of this block.
   std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB));
 
   for (unsigned i = 0, e = Succs.size(); i != e; ++i)
     Succs[i]->removePredecessor(BB);
 
   BB->eraseFromParent();
 }
+
+/// AddColdForEHAllocUsers - add the NoInline and Cold attributes if
+/// CallSites take the memory allocated for the exception to be thrown
+/// as its first argument.
+/// FIXME: We add both NoInline and Cold because the inline cold-threshold
+/// is not tuned yet (r200898). As of now, considering that CallSites in
+/// exception handling regions are very cold is not unreasonable even without
+/// profiling, and avoiding inlining in exception handling region may not have
+/// significant impacts on performance unless a program execution logic
+/// really depends on exception handling flows. However, when the inline
+/// cold-threshold is tuned, we may need to remove NoInline here so that we
+/// can allow a trivial constructor to be inlined.
+void PruneEH::AddColdForEHAllocUsers(Value *EHAlloc, CallInst *EHAllocCall) {
+  for (User *AllocU : EHAlloc->users()) {
+    if (auto *BCInst = dyn_cast<BitCastInst>(AllocU)) {
+      AddColdForEHAllocUsers(BCInst, EHAllocCall);
+    } else {
+      CallSite CS(AllocU);
+      if (CS && !isa<IntrinsicInst>(AllocU) && !CS.arg_empty() &&
+          CS.getArgument(0)->stripPointerCasts() == EHAllocCall) {
+        if (!CS.hasFnAttr(Attribute::NoInline) &&
+            !CS.hasFnAttr(Attribute::AlwaysInline) &&
+            !CS.hasFnAttr(Attribute::InlineHint) &&
+            !CS.hasFnAttr(Attribute::Cold)) {
+          CS.setIsNoInline();
+          CS.setIsCold();
+        }
+      }
+    }
+  }
+}
+
+/// AddColdForCSInEH - it might be reasonably to avoid inlining CallSites
+/// invoked in exception handling context so that we can reduce code size
+/// blow-up in EH region as well as indirectly increase inline opportunites
+/// for unwinding functions containing exception handling code. This function
+/// adds the NoInline and Cold attributes for CallSites invoked in exception
+/// handling context.
+void PruneEH::AddColdForCSInEH(Function *F) {
+  Function *FnThrowE =
+      F->getParent()->getFunction(TLI->getName(LibFunc::cxa_throw));
+  Function *FnEAlloc = F->getParent()->getFunction(
+      TLI->getName(LibFunc::cxa_allocate_exception));
+
+  if (!FnEAlloc || !FnThrowE || !FnEAlloc->isDeclaration() ||
+      !FnThrowE->isDeclaration())
+    return;
+  // Try to find functions which takes memory allocated specifically for
+  // exception to be thrown as its first argument, which must be a constructor
+  // or method executed in the context of exception handling.
+  // For example, in IR below, the NoInline and Cold attributes will be added in
+  // CallInst for MyException() as it takes the memory allocated for the
+  // exception thrown.
+  //
+  // %exception = call i8* @__cxa_allocate_exception(i64 1)
+  // %0 = bitcast i8* %exception to %class.MyException*
+  // call void @MyException(%class.MyException* %0)
+  // call void @__cxa_throw(i8* %exception, .. )
+  for (User *FnU : FnThrowE->users()) {
+    auto *ThrowCall = dyn_cast<CallInst>(FnU);
+    if (!ThrowCall || ThrowCall->isNoBuiltin())
+      continue;
+    // Make sure that the first argument of __cxa_throw() is the memory
+    // allocated by __cxa_allocate_exception().
+    auto *EHAllocCall = dyn_cast<CallInst>(ThrowCall->getArgOperand(0));
+    if (!EHAllocCall || EHAllocCall->isNoBuiltin() ||
+        EHAllocCall->getCalledFunction() != FnEAlloc)
+      continue;
+    AddColdForEHAllocUsers(EHAllocCall, EHAllocCall);
+  }
+  // FIXME: Similarly, we could add the same attributes for CallSites in
+  // catch blocks by traversing blocks reachable from landingpads until EH
+  // return points.
+}

test/Transforms/PruneEH/noinlineattr.ll

+; RUN: opt < %s -prune-eh -S | FileCheck %s
+
+%class.MyException = type { i8 }
+$MyException = comdat any
+@_ZTIi = external global i8*
+
+; CHECK-LABEL: f_throw
+; CHECK: call void @MyException(%class.MyException* %0) [[ATTR_NUM:#[0-9]+]]
+; CHECK: attributes [[ATTR_NUM]] = { cold noinline }
+define i32 @f_throw(i32 %idx, i32 %limit)  personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+entry:
+  %cmp = icmp sge i32 %idx, %limit
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  %exception = call i8* @__cxa_allocate_exception(i64 1) #0
+  %0 = bitcast i8* %exception to %class.MyException*
+  call void @MyException(%class.MyException* %0)
+  br label %invoke.cont
+
+invoke.cont:
+  call void @__cxa_throw(i8* %exception, i8* bitcast (i8** @_ZTIi to i8*), i8* null) #1
+  unreachable
+
+if.end:
+  ret i32 %idx
+}
+
+define linkonce_odr void @MyException(%class.MyException* %this) {
+entry:
+  ret void
+}
+
+declare i8* @__cxa_allocate_exception(i64)
+declare i32 @__gxx_personality_v0(...)
+declare void @__cxa_throw(i8*, i8*, i8*)
+
+attributes #0 = { nounwind }
+attributes #1 = { noreturn }