[LLVMdev] Inlining and exception handling in LLVM and GCC

[Duncan Sands]

The poor interaction between exception handling and inlining in LLVM is one of
the main motivations for the new exception handling models proposed recently.
Here I give my analysis of the origin of the problem in the hope of clarifying
the situation.

Soon after dwarf exception handling was implemented in LLVM, I noticed that some
programs would fail when compiled at -O3, for example the following:

#include <stdio.h>

struct X { ~X() { printf("Running destructor!\n"); } };

void foo() {
   struct X x;
   throw 1;
}

int main() {
   try {
     foo();
   } catch (int) {
     printf("Caught exception!\n");
   }
   return 0;
}

When the exception is thrown in foo, first the destructor for "x" should be run
outputting "Running destructor!", then the exception should be caught in main,
and "Caught exception!" should be output from the handler.  This worked fine
up to -O2, but at -O3 instead the output was:
   terminate called after throwing an instance of 'int'
   Aborted
The difference between -O2 and -O3 was due to inlining: at -O3 foo was being
inlined into main, and for some reason this was causing the C++ runtime to
terminate the program.  To explain why, let me first describe how the GCC
inliner deals with exception handling.

What GCC does
-------------

A "try" clause in C++ contains a certain number of basic blocks (in the above
example just one basic block containing a call to "foo").  That set of basic
blocks is one example of an exception handling region in GCC.  There are various
types of regions, and these can be nested (just as try clauses can be nested).
As well as regions corresponding to "try" clauses, there are also "cleanup"
regions.  These represent scopes for which some destructor needs to be run when
the scope is left.  The function "foo" in the example has a cleanup region that
represents the fact that the destructor for "x" needs to be run when the
function is left due to an exception being unwound:

void foo() {
   struct X x;
                ---\
   throw 1;         | region with a cleanup to be run (the destructor for x)
                ---/
}

int main() {
   try {
                ---\
     foo();         | region corresponding to the "try" statement
                ---/
   } catch (int) { <-- a handler for the above try region
     printf("Caught exception!\n");
   }
   return 0;
}

GCC's exception handling regions correspond in a fairly straightforward way to
the list of "actions" that the exception unwinder actually sees: for a cleanup
region there is a cleanup action, for a try region there is one action for each
catch clause.  When the "throw" statement is executed, the unwinder looks up
the call stack and sees:

     action: catch "int" [ in function main ]         /\ direction of stack
     action: cleanup     [ in function foo ]          || unwinding

There is additional information in the unwind tables, such as where control
should jump to to run the cleanup (i.e. run the destructor), where to jump
to if the exception matches the catch clause (i.e. if the type of the object
thrown is "int") etc, but this additional information is not important in what
follows.

When GCC inlines foo into main it simply nests the exception regions of foo
inside those of main:

int main() {
   try {
                ------------ region corresponding to the "try" statement ---\
   struct X x;                                                               |
                ---\                                                         |
   throw 1;         | region with a cleanup to be run (the destructor for x) |
                ---/                                                         |
                                                                             |
                ------------------------------------------------------------/
   } catch (int) { <-- a handler for the above try region
     printf("Caught exception!\n");
   }
   return 0;
}

When the "throw" statement is executed, the unwinder looks up the call stack
and sees:

     action: catch "int" [ in function main ]         /\ direction of stack
     action: cleanup     [ in function main ]         || unwinding

The important point here is that the list of actions seen by the unwinder has
not changed, though the functions they occur in have.  That's just as well
because some programs look up the call stack and decide what they are going to
do based on what actions they see.  For example, the libstdc++ implementation
of throw first looks up the call stack and if the only actions are cleanups
then it terminates the program without bothering to unwind the exception.  If
inlining removed handlers from the action list it could change the program to
one that is terminated by the throw implementation.  Another example is (so I'm
told) the Darwin objective-c runtime which in order to support a dynamic form
of destructor looks up the stack to see what catch clauses are there and does a
bunch of tricky stuff based on what it discovers.  Since the GCC inliner never
changes the list of actions seen by the unwinder, inlining doesn't change the
decisions made by code of this kind.

Let me say it again because it is important: the GCC inliner has the following
fundamental property:

***************************************************************************
* Inlining never changes the list of actions seen by the unwinder when it *
* looks up the call stack.                                                *
***************************************************************************

I am going to argue that the fundamental reason why LLVM has problems with
inlining in the presence of exception handling is that it doesn't follow this
rule.  And that until it does follow this rule exception handling will not work
100% correctly: it will continue to break tricky code that makes decisions by
looking up the call stack to see what catch clauses etc are up there.

What LLVM did
-------------

Why did the example program die with
   terminate called after throwing an instance of 'int'
   Aborted
if compiled by LLVM with inlining enabled?  In short, because the inliner
changed the set of actions on the call stack so that there was only a cleanup
there; the code implementing "throw" looked up the call stack, saw that there
were only cleanups, and called terminate rather than unwinding the exception.

Here's the LLVM IR for foo:

define void @_Z3foov() noreturn {
entry:
   %memtmp = alloca %struct.X, align 8 ; <= Stack object for variable "x"
   %D.2669_1 = call i8* @__cxa_allocate_exception(i64 4) nounwind
   %D.2687_2 = bitcast i8* %D.2669_1 to i32*
   store i32 1, i32* %D.2687_2, align 4
   invoke void @__cxa_throw(i8* %D.2669_1, i8* bitcast 
(%struct.__fundamental_type_info_pseudo* @_ZTIi to i8*), void (i8*)* null) 
noreturn ; <= Call "throw"
           to label %invcont unwind label %rewind

invcont:                                       ; preds = %entry
   unreachable

rewind:                                           ; preds = %entry
   %exc_ptr = call i8* @llvm.eh.exception()
   %filter = call i32 (i8*, i8*, ...)* @llvm.eh.selector(i8* %exc_ptr, i8* 
bitcast (i32 (i32, i64, i8*, i8*)* @__gxx_personality_v0 to i8*), i32 0) ; <= 
i32 0 means that we are running a cleanup
   call void @_ZN1XD2Ev(%struct.X* %memtmp) inlinehint ; <= Run the destructor 
for "x"
   call void @_Unwind_Resume(i8* %exc_ptr) noreturn ; <= Keep unwinding
   unreachable
}

The GCC cleanup region containing the "throw" becomes an invoke of "throw" in
LLVM.  The fact that this is a cleanup is indicated by the "i32 0" in the call
to eh.selector.  Note that you have to rummage around in the landing pad of the
invoke, i.e. the basic block indicated by the invoke's unwind label, in order
to find this out.

Symbolically the code for foo can be represented as:

void foo() {
   invoke "throw int" ; action: cleanup ---\
                                            |
   run destructor                       <--/  cleanup code here
   continue unwinding
}

Here's the LLVM IR for main:

define i32 @main() {
entry:
   invoke void @_Z3foov() ; <= Call foo
           to label %return unwind label %lpad

return:                                         ; preds = %entry
   ret i32 0

lpad:                                           ; preds = %entry
   %exc_ptr = tail call i8* @llvm.eh.exception()
   %filter = tail call i32 (i8*, i8*, ...)* @llvm.eh.selector(i8* %exc_ptr, i8* 
bitcast (i32 (i32, i64, i8*, i8*)* @__gxx_personality_v0 to i8*), i8* bitcast 
(%struct.__fundamental_type_info_pseudo* @_ZTIi to i8*)) ; <= @_ZTIi means we 
catch type "int"
   %typeid = tail call i32 @llvm.eh.typeid.for(i8* bitcast 
(%struct.__fundamental_type_info_pseudo* @_ZTIi to i8*))
   %0 = icmp eq i32 %filter, %typeid ; <= Was the exception object of type "int"?
   br i1 %0, label %handler, label %rewind

handler:                                         ; preds = %lpad
   %D.2679_3 = tail call i8* @__cxa_begin_catch(i8* %exc_ptr) nounwind
   %1 = tail call i32 @puts(i8* getelementptr inbounds ([18 x i8]* @.str1, i64 
0, i64 0)) ; <= Output "Caught exception!\n"
   tail call void @__cxa_end_catch() nounwind
   ret i32 0

rewind:                                           ; preds = %lpad
   tail call void @_Unwind_Resume(i8* %exc_ptr) noreturn ; <= Keep unwinding
   unreachable
}

The GCC try region containing the call to foo becomes an invoke of foo.  If you
look in the landing pad lpad you find a call to eh.selector which indicates that
the action is "catch int".  It is followed by code to see if the exception type
matches "int".  If so, the handler is run (in block "handler"); otherwise code
to keep unwinding the exception is run.

Symbolically the code for main can be represented as:

int main() {
   invoke foo ; action "catch int" ---\
   return 0;                           |
   was it really an "int"?         <--/ handler code here
yes: print message, cleanup the exception object, return 0
no: continue unwinding
}

The entries in eh.selector after the personality argument correspond exactly to
the "actions" that the unwinder sees (the code generators create tables in the
object file that list the actions for each region, i.e. for each invoke; the
tables are read by the unwinder).  So when the "throw" statement is executed,
the unwinder looks up the call stack and sees:

     action: catch "int" [ in function main ]         /\ direction of stack
     action: cleanup     [ in function foo ]          || unwinding

So far this is exactly the same as what GCC produced, and indeed if the inliner
is not run then the program works fine.

Here's the LLVM IR after running the inliner:

define i32 @main() {
entry:
   %D.2669_1.i = call i8* @__cxa_allocate_exception(i64 4) nounwind
   %D.2687_2.i = bitcast i8* %D.2669_1.i to i32*
   store i32 1, i32* %D.2687_2.i, align 4
   invoke void @__cxa_throw(i8* %D.2669_1.i, i8* bitcast 
(%struct.__fundamental_type_info_pseudo* @_ZTIi to i8*), void (i8*)* null) 
noreturn ; <= Call throw
           to label %invcont unwind label %rewind.i

invcont:                                       ; preds = %entry
   unreachable

rewind.i:                                         ; preds = %entry
   %exc_ptr.i = call i8* @llvm.eh.exception()
   %filter.i = call i32 (i8*, i8*, ...)* @llvm.eh.selector(i8* %exc_ptr.i, i8* 
bitcast (i32 (i32, i64, i8*, i8*)* @__gxx_personality_v0 to i8*), i32 0) ; <= 
the i32 0 indicates a "cleanup"
   %1 = call i32 @puts(i8* getelementptr inbounds ([20 x i8]* @.str, i64 0, i64 
0)) nounwind ; <= Output "Running destructor!\n"
   invoke void @_Unwind_Resume(i8* %exc_ptr.i) noreturn ; <= Continue unwinding, 
but in fact branch to %lpad because of the invoke
           to label %.noexc unwind label %lpad

.noexc:                                           ; preds = %rewind.i
   unreachable

_Z3foov.exit:                                     ; No predecessors!
   br label %return

return:                                           ; preds = %_Z3foov.exit
   ret i32 0

lpad:                                             ; preds = %rewind.i
   %exc_ptr = tail call i8* @llvm.eh.exception()
   %filter = tail call i32 (i8*, i8*, ...)* @llvm.eh.selector(i8* %exc_ptr, i8* 
bitcast (i32 (i32, i64, i8*, i8*)* @__gxx_personality_v0 to i8*), i8* bitcast 
(%struct.__fundamental_type_info_pseudo* @_ZTIi to i8*)) ; <= Catch type "int"
   %typeid = tail call i32 @llvm.eh.typeid.for(i8* bitcast 
(%struct.__fundamental_type_info_pseudo* @_ZTIi to i8*))
   %2 = icmp eq i32 %filter, %typeid ; <= Was the exception object of type "int"?
   br i1 %2, label %handler, label %rewind

handler:                                          ; preds = %lpad
   %D.2679_3 = tail call i8* @__cxa_begin_catch(i8* %exc_ptr) nounwind
   %3 = tail call i32 @puts(i8* getelementptr inbounds ([18 x i8]* @.str1, i64 
0, i64 0)) ; <= Output "Caught exception!\n"
   tail call void @__cxa_end_catch() nounwind
   ret i32 0

rewind:                                           ; preds = %lpad
   tail call void @_Unwind_Resume(i8* %exc_ptr) noreturn ; <= Keep unwinding
   unreachable
}

Symbolically this can be represented as:

int main() {
   invoke "throw int" ; action: cleanup ---\
                                            |
   run destructor                       <--/  cleanup code here
   invoke "continue unwinding"; action "catch int" ---\
   return 0;                                           |
   was it really an "int"?                         <--/ handler code here
yes: print message, cleanup the exception object, return 0
no: continue unwinding
}

The way the LLVM inliner works is (in essence) the following: when inlining
through an invoke
   invoke foo_bar ; actions: A, B, C...
it turns all calls it inlines into invokes, and attaches the actions A, B, C...
to them.  However if it inlines an invoke it just leaves it alone, and doesn't
attach A, B, C... to it.  This is unlike GCC which nested everything it inlines
inside any exception handling regions containing the call site, which in LLVM
speak would mean that it attaches actions A, B, C... to everything it inlines,
both calls and invokes.

When the "throw" statement is executed, the unwinder looks up the call stack
and sees:

                                                      /\ direction of stack
     action: cleanup     [ in function main ]         || unwinding

So it terminates the program rather than unwinding the exception, because it
only saw cleanups.

In order to preserve the list of actions the unwinder sees, what the inliner
should do is append the "catch int" action to the cleanup action, giving

int main() {
   invoke "throw int" ; actions: cleanup, "catch int" ---\--------------------\
                                                          |                    |
   run destructor                                     <--/  cleanup code here  |
   invoke "continue unwinding"; action "catch int" ---\                        |
   return 0;                                           |                       |
   was it really an "int"?                         <--/ catch handler here <--/
yes: print message, cleanup the exception object, return 0
no: continue unwinding
}

Another way of saying this is that the eh.selector call
   %filter.i = call i32 (i8*, i8*, ...)* @llvm.eh.selector(i8* %exc_ptr.i, i8* 
bitcast (i32 (i32, i64, i8*, i8*)* @__gxx_personality_v0 to i8*), i32 0)
should be transformed into the following when inlined:
   %filter.i = call i32 (i8*, i8*, ...)* @llvm.eh.selector(i8* %exc_ptr.i, i8* 
bitcast (i32 (i32, i64, i8*, i8*)* @__gxx_personality_v0 to i8*), i32 0, i8* 
bitcast (%struct.__fundamental_type_info_pseudo* @_ZTIi to i8*))

Then, when the "throw" statement is executed, the unwinder would look up the
call stack and see:

     action: catch "int" [ in function main ]         /\ direction of stack
     action: cleanup     [ in function main ]         || unwinding

i.e. the same set of actions as with GCC, and the same set of actions as when
the inliner isn't run, and all would be well.

A nice additional improvement would be to change the invoke of "continue
unwinding" (aka _Unwind_Resume) into a branch to the catch handler, but this
is fairly orthogonal to the current discussion so I won't discuss it.  GCC
does do this optimization.  Except for that, if you append the "catch int"
to the "cleanup" as described above then GCC and LLVM produce the same code.

The flaw in the inliner's logic
-------------------------------

Why does the inliner work the way it does?  The logic behind it is plausible
but wrong, and goes something like this.  An invoke instruction does not let
exceptions unwind through it (instead control branches to the landing pad).
So when inlining it into another function, there is no need to do anything
with it: it is not a throwing instruction.  This logic assumes that inlining
does not affect whether an exception is unwound or not.  It is true that *if*
an exception is unwound then the code produced by the LLVM inliner will
function correctly.  But what if it is not unwound in the first place because
whoever is doing the unwinding looks up the call stack and bases its decision
as to whether to unwind (or potentially even what type of exception it unwinds)
on what actions it sees there?  Then the whole LLVM approach falls apart.  And
that's exactly what happens in the example program.

What LLVM did next
------------------

My "solution" to the problem of the example aborting was unfortunately wrong and
has been causing trouble ever since.  Dale told me this at the time IIRC, and he
even pointed out what should be done (i.e. the contents of the eh.selector call
for the invoke call site being inlined through should be appended to any calls
to eh.selector inlined through it, see discussion of the example above).  But I
didn't get it and instead changed llvm-gcc to output a "catch all" wherever it
would normally output a cleanup.  Then after inlining the unwinder would see the
following up the call stack

                                                      /\ direction of stack
     action: "catch ..."     [ in function main ]     || unwinding

and wouldn't terminate the program any more.  Of course inlining was still
changing the list of actions seen by the unwinder (which is wrong), but other
problems were introduced too.  For example, if a C++ program really only had
cleanups then it wouldn't immediately abort any more when an exception was
thrown, instead it would run all destructors and only abort afterwards.  This
may not seem so bad (the C++ standard says it is implementation defined as to
whether destructors are run or not) but in fact there is code in libstdc++ that
depends on the program being aborted without cleanups being run.  Also, the
objective-c runtime "knows" all kinds of stuff such as: if there is a catch
clause then __cxa_begin_catch will be run in the handler; but this wasn't true
any more.  Recent unwinder libraries also "know" things of this kind and have
implemented optimizations based on it (which break due to the "catch all").
The list goes on and on.  I should have listened to Dale.

When LLVM does now
------------------

Currently the LLVM inliner is still doing the wrong thing.  However the
workaround of turning cleanups into catch-alls has been partially abandoned.
Instead of turning cleanups into catch-alls, llvm-gcc outputs a cleanup as
it should.  Rather, the code generators try hard to correct the problems
introduced by inlining, shifting catch actions from one invoke to another
(and occasionally adding in a catch-all here and there).  This is not always
possible but the result is something that works in practice.  However the
fundamental property of inlining not altering the list of actions seen by the
unwinder does not hold.

What LLVM should do
-------------------

When inlining through an invoke callsite, the list of actions for the invoke
should be appended to everything inlined, which can be achieved by appending
it to every eh.selector call that is inlined.  If this was done then inlining
would no longer change the set of actions up the call stack, the workarounds
in the code generator would go away, and LLVM behaviour would be more correct,
and in fact would be identical to GCC's.

But there's a problem here: how to find the actions for the invoke?  They are
listed in the eh.selector call which should be in the invoke's landing pad.
But the optimizers can move it out of the landing pad, and indeed in theory
eh.selector calls could occur far away from the landing pad (though this in
not true in practice for LLVM IR produced by llvm-gcc and clang).

The obvious solution is to simply attach the list of actions directly to the
invoke instruction, which is the content of my recent exception handling
proposal.  Then the inliner can just grab them and append them to those of
any invokes it inlines through the call site.

Bill's recent exception handling proposal has rules which (if I understand
them right) ensure that you can always find the actions for an invoke without
any trouble (the actions would be listed in a dispatch instruction that is
not allowed to be moved out of the landing pad).  Thus with this proposal too
there would also be no problem in teaching the inliner to do the right thing.
This presumably would also simplify the proposal since the dispatch instruction
would no longer need to specially know about the "catch all" for the language
since the code generators would no longer need to know about catch-all (they
currently do to work around the inliner's faulty logic, see above).

However it also possible to improve things without any IR changes at all (but
not make things perfect).  The inliner can always *try* to find the actions
associated with an invoke, even if it is not guaranteed to find the call to
eh.selector.  If it can't find the eh.selector then too bad (in this case it
could act as if they were an empty list, which is of course wrong).  If it can
find the actions, it would then append them to everything it inlines, i.e. to
every eh.selector call it inlines.  Most of the time it will find the actions -
this is clear because the code generator actually aborts with an assert failure
if it can't find them itself!  So clearly the code generators always finds them
in practice - the inliner just needs to try at least as hard as the code
generators.  The result is that the inliner will do the right thing for all
code that the code generator currently doesn't abort on, and the codegen logic
that tries to fix up lists of actions by shifting them around can be removed.
In short, the situation would be strictly improved, but of course it would still
just be a workaround while waiting for an improved exception handling design.

Duncan.