[cfe-dev] [LLVMdev] Unwind behaviour in Clang/LLVM

[Logan Chien]

Hi all,

I feel that there are two problems with the existing infrastructure:

* The nounwind attribute is ambiguous for (1) not throwing exceptions and
(2) not performing stack unwinding. I feel that it will be better to
separate this in two different attributes

* There is some problem when the function has both uwtable and nounwind.
Although, I think it fine to keep the current definition of nounwind,
however, the uwtable attribute will be much useless to its user. Besides,
even if we wish to keep the current definition, to avoid the undefined
behavior, we have to slightly change the code generator to emit [can't
unwind] whenever there is a nounwind attribute.

I am writing my thoughts in detail below, please have a look, and feel free
to challenge or send me the feedback. Thanks.

Sincerely,
Logan

tl;dr

(HTML version: http://loganchien.github.io/llvm/nounwind.html )

Notations
---------

To make my argument clear, I would like to use a different notation from
LLVM IR:

* The no-throw attribute guarantees that the function will not throw any
exception object.

* The no-unwind attribute guarantees that the function won't read the prior
calling sequence with the stack unwinder.

For simplification, if the function is not tagged with no-throw then it is
may-throw. Similarly, if the function is not tagged with no-unwind, then it
is may-unwind.

* The ehtable attribute guarantees that the exception handling table, such
as the LSDA handler data and (by implementation) the stack unwinding
information for exception, will be generated for exception handling. If the
table includes stack unwinding infomration, then it is guaranteed that the
unwinding information is sufficient enough to go back to previous
propagation barrier (landingpad, cleanup filter, or can't unwind.)

* The uwtable attribute guarantees that the unwind table will be generated
for stack unwinding for profilers, debuggers, (possibly) exception handling
mechansim and etc. This attribute guarantees that the complete stack trace
can be obtained as long as the calling sequence does not contain the
external function or the function marked with no-unwind.

It is possible for some exception handling implemenation requires uwtable
to unwind the stack, it is not necessary to do so. On the other hand, even
if the stack unwind information for exception handling is encoded in
ehtable, it might be insufficient to implement the stack unwinder. We will
come back with this later.

If a function has both no-uwnind and uwtable, then there must be a
mechanism (might be an agreement between the compiler and the run-time
library) to signal the stack unwinder to stop before passing through the
function. Otherwise, the undefined behavior might be happened. Similarly,
we need a similar mechanism for the function with both no-throw and ehtable

With these notations, we can do some simple reasoning:

* may-throw implies may-unwind -- We have to unwind the stack if the
exception is thrown by the function, thus the may-throw attribute will
imply may-unwind.

* no-unwind implies no-throw -- The contraposition to the previous statement.

Please notice that no-throw does not imply no-unwind. We will come back
with this later.


Attribute Properties
--------------------

In this section, I would like to discuss the properties of no-unwind and
no-throw, and the rules to infer the attributes if the programmer didn't
specified them in function definition. These properties may be used by some
optimization passes, such as PruneEH.

First, since no-unwind implies no-throw, we can add no-throw attribute to
the functions which have no-unwind attribute.

Second, it is clear that the external functions should be considered as
may-throw unless it is explicitly tagged with no-throw. Similarly, the
external functions should be may-unwind unless it is explicitly tagged with
no-unwind.

For function definition, we can inspect the instructions:

* If the function does not have any call or invoke instruction to a
may-unwind callee function and -fasynchronous-unwind-table compiler option
isn't given, then we can add the no-unwind attribute to the function.

* If the function does not have any call or invoke instruction to a
may-throw callee function, then we can add the no-throw attribute to the
function (safe approximation.)

* If we can prove that every exceptions are caught by the landing pad and
the function won't re-throw the exception or won't continue the unwinding,
then we can add the no-throw to the function attribute.

Please notice that we have to deliberately separate the attribute into
no-throw and no-unwind because the landingpad instruction can't give any
guarantee on no-unwind attribute.


Problems with Existing LLVM Infrastructure
------------------------------------------

There are two function attributes related with unwinding and exception
handling in the existing LLVM infrastructure. Here are the descriptions
copied from the LLVM reference manual:

* nounwind -- This function attribute indicates that the function never
returns with an unwind or exceptional control flow. If the function does
unwind, its runtime behavior is undefined.

* uwtable -- This attribute indicates that the ABI being targeted requires
that an unwind table entry be produce for this function even if we can show
that no exceptions passes by it. This is normally the case for the ELF
x86-64 abi, but it can be disabled for some compilation units.

>From my interpretation, the specification for nounwind guarantees that the
function will neither throw an exception nor unwind the stack, i.e.
nounwind = no-throw + no-unwind. The specification for uwtable guarantees
some unwind table will be generated; however, it does not specify which
kind of unwind table should be generated. IIRC, the ARM backend actually
implements ehtable, which has only limited capability to unwind the stack.

# Inconsistant Interpretation of nounwind

The things are getting tricky when it comes to the implementation. There is
a PruneEH pass, which will try to remove the unnecessary exception handling
informantion. For example, the following code:

define void @foo() {
entry:
  ret void
}

will be converted to:

define void @foo() nounwind {
entry:
  ret void
}

Here's a much more complex example:

define void @foo() {

declare void @_Z3barv()

declare i32 @__gxx_personality_v0(...)

define void @_Z3foov() {
entry:
  invoke void @_Z3barv() to label %try.cont unwind label %lpad

lpad:
  %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)*
@__gxx_personality_v0 to i8*)
          catch i8* null
  ret void

try.cont:
  ret void
}

is converted to

declare void @_Z3barv()

declare i32 @__gxx_personality_v0(...)

; Function Attrs: nounwind
define void @_Z3foov() #0 {
entry:
  invoke void @_Z3barv()
          to label %try.cont unwind label %lpad

lpad:
  %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)*
@__gxx_personality_v0 to i8*)
          catch i8* null
  ret void

try.cont:
  ret void
}

attributes #0 = { nounwind }

Some careful reader might have noticed the problem here. The nounwind
attribute is added to @_Z3foov() simply because the landingpad can catch
the exception object. However, in my notation, only no-throw can be added
to this function, and no-throw does not imply no-unwind. It is possible for
@_Z3foov() to unwind the stack. For example, the function @_Z3barv() may
call _Unwind_Backtrace() to get the backtrace.

Besides, some optimization might make the situation even worse. AFAIK, most
of the stack unwinding implementations rely on the value in the link
register or the return address on the stack. However, there is an
optimization in LLVM code generation which will not save the link register
if the callee function has noreturn attribute [1]. Even though the
optimization will only be applied when the callee function has nounwind
attribute as well, the problem still occurs because PruneEH will
(incorrectly) add nounwind to some function which actually unwinds.
Besides, I am in doubt about whether we can apply this optimization when
the caller function has the uwtable attribute and requires the unwind table.

# Unwind Table and Can't Unwind

The mixture of uwtable and nounwind will cause another problem.

IMO, it is incorrect to decide whether to emit [can't unwind] with
!needsUnwindTableEntry() [2]. The needsUnwindTableEntry() is defined as
either the function has uwtable attribute or the function does not have
nounwind. Thus, !needsUnwindTableEntry() imples not having uwtable
attribute and having nounwind. As the result, the [can't unwind] won't be
generated for the following function:

define void @foo() uwtable nounwind {
entry:
  call void @bar()
  ret void
}

The stack unwinder might continue to unwind the stack because there isn't
any mark in the unwind table to stop the stack unwinding. And,
unfortunately, according to the LLVM reference manual, this will result in
undefined behavior. In fact, I did encounter some real example [3] which
will fall into an infinite loop during the phase 1 unwinding.
Summary

In conclusion, I would like to suggest that we need to put more efforts to
define a precise specification for exception handling and stack unwinding
mechanism, so that the optimization passes and the run-time environment can
interact with each other without problems.

In summary, IMO, these are the topic have to be discussed:

* Should we separate nounwind into no-throw and no-unwind?
  - What is the impact in terms of the run-time performance?
  - What is the impact on the code size?

* Should we write more implementation details about uwtable in the LLVM
reference manual?
  - What is the possible expected behavior when uwtable is used with
nounwind

If we have some decision, I am willing to write the patch. :-)


Footnotes
---------

    See <llvm>/lib/CodeGen/VirtRegMap.cpp line 290
    See <llvm>/lib/CodeGen/AsmPrinter/ARMException.cpp line 65
    See <libc++abi>/test/test_vector3.cpp




On Sat, Feb 15, 2014 at 11:36 PM, Renato Golin <renato.golin at linaro.org>wrote:

> On 15 February 2014 11:38, Evgeniy Stepanov <eugeni.stepanov at gmail.com>
> wrote:
> > I'd love to hear more details. Are you saying that this infinite loop
> > is a limitation of EHABI table format, and not something that can be
> > fixed in the compiler?
>
> I'd find it hard to believe. EHABI has been out for a long time and I
> don't remember any intrinsic problem like that.
>
> Remember that our EHABI implementation is *very* new, and that this
> problem is when mixing Dwarf unwinding with EHABI unwinding, which we
> have just enabled yesterday (by Keith's patch), so "here be dragons".
> ;)
>
>
> > Meanwhile, please notice that gcc behavior matches current clang
> > behavior that I described above. We would not want to create an
> > incompatibility.
>
> Absolutely! We need to be extra careful.
>
> It'd be good if we had some examples compiled with GCC and LLVM
> intermixed and throw exceptions from different places, either on the
> check-all or the test-suite.
>
> cheers,
> --renato
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20140218/a04cedb6/attachment.html>