[LLVMdev] Requirements for the EH representation
John McCall
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.
_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Renato Golin
I'll read your email with greater care along the week, but I have
added a page on the wiki to help us organise our thoughts.
http://wiki.llvm.org/Exception_Handling
I'll change it as I go reading your email, but for now, I've separated
into each of the requirements you said. New ones could be added,
existing ones merged, but the most important is to add more complete
rationale to each, so every one agrees on the same thing when reading
them.
I think we lost a lot of context from last year when the discussion
started, and we had a lot of momentum and came up with good design
decisions for the IR language (IMO). We should immortalise it in an
official document in SVN.
Let's start on the wiki and move to docs whenever that's set in stone.
cheers,
--renato
On 13 April 2011 03:59, John McCall <rjmc...@apple.com> wrote:
> 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.
...
John McCall
> I'll read your email with greater care along the week, but I have
> added a page on the wiki to help us organise our thoughts.
>
> http://wiki.llvm.org/Exception_Handling
If you want to volunteer to keep track of the discussion on the wiki, I
think that would be great. I don't think we're going to hold the
discussion on the wiki, though.
Also, what you've listed as "Areas to Consider" are explicitly things
I *don't* want to consider immediately. Those are interesting
questions, but they're separate questions, and we should settle
on these basic requirements first.
For example, if it's a real goal to make LLVM IR capable of supporting
a wider range of unwinders than it currently can — at a gloss,
non-resumptive EH with a single, non-reentrant landing pad per region
and LSDA layout approximating what's consumed by __gxx_personality_v0
— then that touches on almost everything else. Contrariwise, if we're
only really interested in finding a better fix to the current IPO problems,
then maybe we can get away with very modest changes. And it's okay
to have limited goals! I personally don't; I think we should aim to get
the IR design good enough to support crazy resumptive languages
with crazy custom unwinding schemes. But I need to know what range
of problems we're willing to consider solving before I can usefully weigh
different solutions.
John.
Renato Golin
> If you want to volunteer to keep track of the discussion on the wiki, I
> think that would be great. I don't think we're going to hold the
> discussion on the wiki, though.
Of course. But all our discussions last year got lost and the context
is gone. To get the context back one would have to re-read *all*
emails, which is a long way to go.
I can keep track on the wiki. no problems, but I need everyone
interested in the subject to constantly validate it, as I plan to
transform that into a design document that we must follow when
considering changing the IR, not only for EH, since EH touches
everything.
Ultimately, the goals and design decisions should go in its own
document and the IR changes in LangRef.
> Also, what you've listed as "Areas to Consider" are explicitly things
> I *don't* want to consider immediately. Those are interesting
> questions, but they're separate questions, and we should settle
> on these basic requirements first.
We need at least two points to draw a line. One in the near future and
one in the far future.
The former fixes our problems, but that's not enough. We need the
latter to steer us in the right direction and not get lost again.
As you very well know, exception handling cannot be underestimated. We
need everyone to agree one near and far goals to avoid this topic
showing up every year.
> I personally don't; I think we should aim to get
> the IR design good enough to support crazy resumptive languages
> with crazy custom unwinding schemes. But I need to know what range
> of problems we're willing to consider solving before I can usefully weigh
> different solutions.
Thus, long term plan. ;)
Whatever quick fix we do now will only postpone the real issue. The IR
cannot represent many of the exception cases we came up last year and
the (somewhat radical) changes we proposed could, but every time we
got to a conclusion, someone else would come and say: "this doesn't
work for <language>" or "consider <this> case" and we were back to
square one.
We need a stable place to list *all* languages, *all* cases and
consider *all* ABI constraints (as far as possible, obviously), before
we start taking strong design decisions. That's probably the only
reason to have a wiki in the first place.
cheers,
--renato