[LLVMdev] Requirements for the EH representation

[John McCall]

Since it looks like we're going to start discussing changing the EH
representation again, I think it would be a very good idea to first
review the core requirements we have of the exceptions IR.

Mostly, here, I'm taking the major exceptions implementations I
have direct knowledge of --- zero-cost DWARF-based libUnwind with the
default GCC personalities, builtin_sjlj-based libUnwind with the same
personalities, various alternative personality proposals I've been
asked to consider, and C++ over SEH --- and trying to make sure that
LLVM IR can reasonably express them with high quality, with
interesting optimization potential, and without loss of semantic
fidelity.

Furthermore, I believe that LLVM IR should be able to reasonably
express the full range of behavior of the platform's exceptions
implementation.  Specifically, we should able to implement resumptive
exception handlers on unwinders that support them, which (to summarize
briefly) is all of above.  Now, obviously, actually implementing
codegen lowering for resumptive handlers is not an immediate priority
(although the problems there roughly coincide with the problems we'd
face in implementing SEH); I'm just saying that our exceptions IR
should stop precluding the possibility.

These requirements punt on three major questions that I consider
separable:

  - the structure or appearance of the actual IR:  I'm just trying
    to lay down what I expect of the information preserved there;

  - what IR constructs can serve as origin points of unwinds:
    that is, whether exceptions can originate from:
      - only calls (status quo)
      - any instruction marked as potentially throwing (to support
        synchronous throwing signal handlers: e.g., null pointer
        exceptions and zero divides)
      - any arbitrary location (to support asynchronous signal
        handlers that throw)

  - what IR constructs to attach unwind actions to:  that is,
    whether cleanups and handlers are linked from individual throwing
    instructions or from entire basic blocks

With all that said, on with the show.

An "unwinder" is a mechanism which propagates exceptions.  Generally
the unwinder is part of the OS / language runtime.  Many environments
divide the unwinder into language-agnostic and language-specific
components; for example, the standard C++ unwinder on Darwin is
libUnwind using __gxx_personality_v0, and the standard C++ unwinder
under the MSVC++ ABI is SEH using a magic exception code.  There are
often many similarities between unwinders using the same
language-agnostic framework, but that just means that the
implementations (both in the runtime and the compiler) can share code;
it doesn't mean that it's necessarily safe to assume that code or
metadata has the same semantics under different unwinders.

Some language-specific unwinders interoperate in the sense that
frontend-generated metadata designed for one unwinder may be used for
the other.  Usually this only works in one direction.

  Requirement: Unwinders should be explicit in the representation so
    as to simplify tasks like deciding when IPO can be performed or
    choosing how to lower the IR.  I would suggest that an unwind is
    the name of an "unwinder family" --- probably one of a family of
    reserved, built-in codes --- together with a sequence of other
    configuration data, to be interpreted by the backend code for that
    family.  For example, one unwinder family would be "traditional
    zero-cost DWARF exceptions", and the configuration data for that
    family would just be a singleton address of a personality
    function.  A personality function requiring a significantly
    different LSDA layout would use a different unwinder family.
    Effectively, unwinder families would act like little,
    function-specific EH targets.

  Requirement: The backend is permitted to explode if given an
    unwinder family it doesn't know about.  Other IR manipulations,
    like bitcode loading and storing, should not.  Unwinder family
    implementations should be resilient (if suboptimal) against
    unexpected but well-formed configuration data --- for example, it
    should be possible to use a new personality function with the
    libunwind-zerocost-dwarf unwinder family, and as long as that
    personality uses an LSDA that looks like the zerocost DWARF LSDA,
    everything should be fine.

Unwinders generally operate in units of call frames.  When considering
a call frame, an unwinder must have a complete idea of the frame's
desired unwinding behavior.  It is not burdensome for a frontend to
make sure it generates a complete picture of the local context within
a function, but IPO inherently complicates this.  It is not desireable
for IPO to be inhibited by the mere presence of exception code or for
IPO to break semantics.

Given sufficient ingenuity, it might be possible to mix unwinders
within a function in some situations, which could lead to performance
benefits on the right LTO-enabled benchmark, but it's not clear that
it's worth supporting this in the model given the complexity and
limitations.

  Requirement: IPO should not move code from the control of one
    unwinder to that of another unless it knows that semantics
    are preserved, e.g. if the new unwinder accepts metadata for
    old, or if the code cannot throw.

  Requirement: The IR should be expressive enough to allow
    exception-handling code to be moved between functions without that
    automatically breaking semantics (if the functions specify the
    same unwinder).  This applies both to moving code into a function
    (e.g. inlining) and the reverse.  For example, we should be able
    to safely convert between any of the following programs as an
    unwinder-agnostic operation:

      void foo() { try { std::string s; bar(s); } catch (...) {} }

      void foo() { try { std::string s; baz(s); } catch (...) {} }
      void baz(std::string &s) { bar(s); }

      void foo() { try { baz(); } catch (...) {} }
      void baz() { std::string s; bar(s); }

Most unwinders will work by interpreting some sort of implicit or
explicit "unwind table": locations within the function will be mapped
to a set of unwinder-specific information generated by the frontend
and a new location within the function (a "landing pad").  This is a
very vague view; any more specific and the unwinders start varying
widely.  For example:

  - Some unwinders track the location implicitly, by recovering
    the return address in the frame and having a table indexed by
    relative offsets from the start of the function;  others
    do so explicitly, by maintaining a table index in a special
    call frame slot or an object accessible from a thread-local.

  - The standard GCC personalities can only map a location to a single
    landing pad, so they give the landing pad some extra information
    (the "selector") about what action it should be.  C++ SEH actually
    lands at different places in the code, and a cleverer libUnwind
    personality could do the same thing.

  - __gxx_personality_v0 wants a single pointer of metadata per catch
    handler; C++ SEH uses more than that.

  - SEH actually invokes cleanups and catch handlers as subfunctions,
    which return to indicate completion; libUnwind restores registers
    to a known state and resumes execution in the original call frame,
    with some expectations about the valid range of behavior.

Frontends will never be able to emit totally unwinder-agnostic code:
the unwinder must be configured, unwind tables must be seeded with
appropriate metadata, and the right runtime calls must be emitted at
the right times.  However, it is clearly desireable for the structure
of emitted code to be reasonably consistent, for the sake of
frontends, middle-ends, and backends.  For example, we could require
that frontends targetting SEH manually lower EH code into
sub-functions, but that would require a radically different emission
strategy and would generally produce challenging barriers to
optimization.

  Requirement: The choice of unwinder should only minimally affect the
    basic structure of the IR.  At a gloss, the code should differ
    only in (1) the structure of the unwinder-specific data for unwind
    actions (see below) and (2) high-level behavioral differences,
    like the calls to __cxa_{begin,end}_catch required by the Itanium
    EH ABI.

Languages can define a pretty wide range of different actions which
might need to be performed when unwinding into a function, but I
believe they can be categorized into two classes:

  - First, actions taken in response to the exception itself;  call
    them "handlers".  These actions halt the propagation of the
    exception (possibly only temporarily) and execute arbitrary code
    before ultimately doing one of the following:
      - consuming the exception and resuming execution in the handling
        function,
      - resuming the propagation of the exception, starting from the
        handler, or
      - (in some languages) resuming execution within the throwing
        function.

  - Second, actions taken in response to a scope being abnormally
    terminated by the exception; call them "cleanups".  These actions
    do not formally halt the propagation of the exception.  They are
    expected to eventually return control to the unwinder, and the
    language usually specifies some level of severe consequence if
    they instead raise their own exception.  For example, C++ requires
    a call to std::terminate(), whereas Ada causes both exceptions
    to be cancelled and a new exception to be thrown.

In languages which do not support resumptive exceptions, the unwinder
is typically required to execute inner cleanups, from the inside out,
before entering a matching exception handler.  In languages which do
support resumptive exceptions, the unwinder is typically required to
*not* execute inner cleanups before entering a matching exception
handler; only if the handler consumes the exception are the cleanups
between the throwing scope and the handling scope performed.

The correct inter-ordering of handlers and cleanups within a function
must be preserved to correctly support languages like C++ which
require all cleanups to be executed before entering an exception
handler.  However, to correctly support languages with resumptive
exception handling, the unwinder must be able to bypass cleanups and
find an exception handler to subinvoke.

  Requirement: The representation should not force the assumption of
    an execution dependency between different unwind actions, or that
    there is necessarily only one "unwind edge" from a unwinding point
    or only one "landing pad" associated with a specific action.

  Requirement: The representation should preserve the ordering of
    dependent unwind actions.

[Non-"normative": to me, these ordering requirements, together with
the requirement that IPO be able to move code without changing
semantics, strongly suggest a representation featuring an explicit DAG
(with out-degree 1) of the high-level structure of unwind actions,
where each node would carry opaque payloads to be interpreted by
unwinder-specific optimizations and lowering.  How this DAG is related
to the CFG --- for example, whether it involves separate objects, is
encoded in special instructions, or is actually just annotations on
BasicBlocks --- is something I leave open.  IPO would be able to just
move appropriate segments from this DAG between functions as it moves
the affected code.]

Languages and unwinders may support a menagerie of kinds of handlers
and cleanups; for example, __gxx_personality_v0 allows the efficient
encoding of a handler which calls std::terminate().  It can be a
significant optimization to use these.

  Requirement: The representation should be capable of carrying an
    opaque channel of data about unwind actions from the frontend to
    the backend.

I hope this all at least serves as a foundation for further
discussion.  Right now, I'm worried that we've been focusing on
specific problems and specific proposed solutions rather than the
overall shape of the problem and what we'd like to be able to express.

John.