invoke/unwind

[Dustin_Laurence]

I put invoke/unwind aside because I couldn't get them to work, but I'm
working on my evaluator now and it would be nice to figure this out so I
don't have to unwind the stack manually. This was the reason for my
earlier question about global declarations, and as that's cleared up I
can easily pass exception data...if I can make unwind return out of some
deep recursion.

The behavior I get is sort of odd and took a while to
characterize--unwind returns every time if done one level deep in the
same translation unit. If I try it across translation units, or more
than one call deep, I get a seg fault every time.

I have reduced the problem to a trivial test case which I can post if
there is an obvious "you idiot, everyone knows you have to frob your
gismoids" answer.

Dustin

[Duncan_Sands]

Hi Dustin, the code generators do not support unwind, only the
interpreter does.

Ciao,

Duncan.

[Garrison_Venn]

If it helps, to see what is involved, outside of a pure IR context, see the example code, and doc at:

http://wiki.llvm.org/HowTo:_Build_JIT_based_Exception_mechanism#Source_Code:_exceptionDemo.cpp

Although this is a pure example that shows several test cases, including foreign exception interaction, it is
not an IR example, but rather a LLVM IR API example. It would be interesting to see a pure IR version of a
personality function. I don't see why this would not be possible, although costly in terms of effort. Clang
would help.

There are also ways to lower your invoke/unwind into a setjump/longjump implementation, but I do not know
how to do this in IR, as it requires function pass setup which is outside the scope of IR.

Garrison

[Kenneth_Uildriks]

I thought someone implemented invoke/unwind for x86 a few months ago.
I remember seeing a post to that effect.

[Duncan_Sands]

Hi Kenneth,

I thought someone implemented invoke/unwind for x86 a few months ago.
I remember seeing a post to that effect.

unwind will work as a rethrow, i.e. you do an invoke and in the landing
pad or downstream of it you can use invoke to rethrow the exception that
caused you to branch to the landing pad. But that's it as far as I know.

Ciao,

Duncan.

[Dustin_Laurence]

Ah, the secret is not to even try to frob the gnorts. Manual unwinding,
here I come.

I was going to say the interpreter doesn't either, but then I recalled
it JITs when it can. I don't know how to call into libc from the
interpreter to test that.

So how is clang doing C++ exceptions?

Dustin

[Dustin_Laurence]

If it helps, to see what is involved, outside of a pure IR context,
see the example code, and doc at:

http://wiki.llvm.org/HowTo:_Build_JIT_based_Exception_mechanism#Source_Code:_exceptionDemo.cpp

It does, although in the "let me show you why this is too much to
tackle" way.

Although this is a pure example that shows several test cases,
including foreign exception interaction, it is not an IR example, but
rather a LLVM IR API example. It would be interesting to see a pure
IR version of a personality function. I don't see why this would not
be possible, although costly in terms of effort. Clang would help.

Beyond the scope of the project, I guess. Sounds too far out on the
diminishing returns curve for knowledge. If I spend too much time
handcoding IR the first extension to the project would be to write a
"high-level IR" front-end that provides a 1-1 mapping of the semantics,
but with handcoding-friendly syntax and tools. It would actually save
time at some level, given that I'm manually #including headers just to
reduce the amount of code duplication to saying it twice instead of many
times.

Complete aside--I hate when people tell me something is impossible, even
me. So after I said you couldn't do without CPP-style #includes a
few days ago I was annoyed enough to design in my head an import/export
mechanism using only unix tools everyone has laying around. Just to
prove myself wrong, I guess. I'm not sure I'll implement it given that
I already have a lot of code written the other way, but LLVM syntax is
simple enough that it could be done without parsing the IR.

I don't know if I have enough IR left to justify switching over, but it
would be satisfying in principle to get rid of the duplication of headers.

There are also ways to lower your invoke/unwind into a
setjump/longjump implementation, but I do not know how to do this in
IR, as it requires function pass setup which is outside the scope of
IR.

I don't know enough about how setjmp/longjmp are implemented to have a
clue. If I'm getting into uncharted territory it's easier to just
unwind the evaluator stack by hand, just as I already did with the
parser when unwinding didn't work. The focus is on learning IR and
about the simple lisp evaluation model.

There are actually limits to my madness, you know. It would be more
profitable to learn another aspect of the system by implementing a MMIX
back-end or something.

Or, and I know this is just *crazy* talk, I could actually follow the
intended learning path and use the main C++ API for something.

Dustin

[Mike_Stump1]

Roughly, like so:

$ cat t.cc
int main() {
  try { throw 1; } catch (int i) { }
}
$ clang -S t.cc -emit-llvm
$ cat t.s
; ModuleID = 't.cc'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
target triple = "x86_64-apple-darwin10.0"

@_ZTIi = external constant i8* ; <i8**> [#uses=1]

define i32 @main() ssp {
entry:
  %retval = alloca i32 ; <i32*> [#uses=2]
  %exception.ptr = alloca i8* ; <i8**> [#uses=1]
  %_rethrow = alloca i8* ; <i8**> [#uses=4]
  %i = alloca i32, align 4 ; <i32*> [#uses=1]
  %cleanup.dst = alloca i32 ; <i32*> [#uses=3]
  %cleanup.dst6 = alloca i32 ; <i32*> [#uses=5]
  store i32 0, i32* %retval
  %exception = call i8* @__cxa_allocate_exception(i64 4) ; <i8*> [#uses=3]
  store i8* %exception, i8** %exception.ptr
  %0 = bitcast i8* %exception to i32* ; <i32*> [#uses=1]
  store i32 1, i32* %0
  invoke void @__cxa_throw(i8* %exception, i8* bitcast (i8** @_ZTIi to i8*), i8* null) noreturn
          to label %invoke.cont unwind label %try.handler

invoke.cont: ; preds = %entry
  unreachable

terminate.handler: ; preds = %match.end
  %exc = call i8* @llvm.eh.exception() ; <i8*> [#uses=1]
  %1 = call i32 (i8*, i8*, ...)* @llvm.eh.selector(i8* %exc, i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*), i32 1) ; <i32> [#uses=0]
  call void @_ZSt9terminatev() noreturn nounwind
  unreachable

try.handler: ; preds = %entry
  %exc1 = call i8* @llvm.eh.exception() ; <i8*> [#uses=3]
  %selector = call i32 (i8*, i8*, ...)* @llvm.eh.selector(i8* %exc1, i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*), i8* bitcast (i8** @_ZTIi to i8*), i8* null) ; <i32> [#uses=1]
  %2 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*)) ; <i32> [#uses=1]
  %3 = icmp eq i32 %selector, %2 ; <i1> [#uses=1]
  br i1 %3, label %match, label %catch.next

match: ; preds = %try.handler
  %4 = call i8* @__cxa_begin_catch(i8* %exc1) ; <i8*> [#uses=1]
  %5 = bitcast i8* %4 to i32* ; <i32*> [#uses=1]
  %6 = load i32* %5 ; <i32> [#uses=1]
  store i32 %6, i32* %i
  store i32 1, i32* %cleanup.dst
  br label %match.end

match.handler: ; No predecessors!
  %exc2 = call i8* @llvm.eh.exception() ; <i8*> [#uses=2]
  %7 = call i32 (i8*, i8*, ...)* @llvm.eh.selector(i8* %exc2, i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*), i32 0) ; <i32> [#uses=0]
  store i8* %exc2, i8** %_rethrow
  store i32 2, i32* %cleanup.dst
  br label %match.end

cleanup.pad: ; preds = %cleanup.switch
  store i32 1, i32* %cleanup.dst6
  br label %finally

cleanup.pad3: ; preds = %cleanup.switch
  store i32 2, i32* %cleanup.dst6
  br label %finally

match.end: ; preds = %match.handler, %match
  invoke void @__cxa_end_catch()
          to label %invoke.cont4 unwind label %terminate.handler

invoke.cont4: ; preds = %match.end
  br label %cleanup.switch

cleanup.switch: ; preds = %invoke.cont4
  %tmp = load i32* %cleanup.dst ; <i32> [#uses=1]
  switch i32 %tmp, label %cleanup.end [
    i32 1, label %cleanup.pad
    i32 2, label %cleanup.pad3
  ]

cleanup.end: ; preds = %cleanup.switch
  %exc5 = call i8* @llvm.eh.exception() ; <i8*> [#uses=1]
  store i8* %exc5, i8** %_rethrow
  store i32 2, i32* %cleanup.dst6
  br label %finally

catch.next: ; preds = %try.handler
  store i8* %exc1, i8** %_rethrow
  store i32 2, i32* %cleanup.dst6
  br label %finally

finally: ; preds = %catch.next, %cleanup.end, %cleanup.pad3, %cleanup.pad
  br label %cleanup.switch8

cleanup.switch8: ; preds = %finally
  %tmp7 = load i32* %cleanup.dst6 ; <i32> [#uses=1]
  switch i32 %tmp7, label %cleanup.end9 [
    i32 1, label %finally.end
    i32 2, label %finally.throw
  ]

cleanup.end9: ; preds = %cleanup.switch8
  br label %finally.end

finally.throw: ; preds = %cleanup.switch8
  %8 = load i8** %_rethrow ; <i8*> [#uses=1]
  call void @_Unwind_Resume_or_Rethrow(i8* %8)
  unreachable

finally.end: ; preds = %cleanup.end9, %cleanup.switch8
  %9 = load i32* %retval ; <i32> [#uses=1]
  ret i32 %9
}

declare i32 @__gxx_personality_v0(...)

declare i8* @llvm.eh.exception() nounwind readonly

declare i32 @llvm.eh.selector(i8*, i8*, ...) nounwind

declare i8* @__cxa_allocate_exception(i64)

declare void @__cxa_throw(i8*, i8*, i8*)

declare void @_ZSt9terminatev()

declare i32 @llvm.eh.typeid.for(i8*) nounwind

declare i8* @__cxa_begin_catch(i8*)

declare void @__cxa_end_catch()

declare void @_Unwind_Resume_or_Rethrow(i8*)

[Garrison_Venn]

If it helps, to see what is involved, outside of a pure IR context,
see the example code, and doc at:

http://wiki.llvm.org/HowTo:_Build_JIT_based_Exception_mechanism#Source_Code:_exceptionDemo.cpp

It does, although in the "let me show you why this is too much to
tackle" way.

Yeah, I hear you. The LLVM developer fly trap got me.

Although this is a pure example that shows several test cases,
including foreign exception interaction, it is not an IR example, but
rather a LLVM IR API example. It would be interesting to see a pure
IR version of a personality function. I don't see why this would not
be possible, although costly in terms of effort. Clang would help.

snip

There are also ways to lower your invoke/unwind into a
setjump/longjump implementation, but I do not know how to do this in
IR, as it requires function pass setup which is outside the scope of
IR.

I don't know enough about how setjmp/longjmp are implemented to have a
clue. If I'm getting into uncharted territory it's easier to just
unwind the evaluator stack by hand, just as I already did with the
parser when unwinding didn't work. The focus is on learning IR and
about the simple lisp evaluation model.

For pedagogical purposes, the lowering is accomplished by an IR to IR graph transformation
that you add to a function pass manager. I personally view LLVM as a term re-writing
system where the rules are controlled by the developer a priori. The above IR to IR
transformation is one of these rules, which in LLVM parlance, and from a compiler viewpoint,
is a pass. See -lowerinvoke in LLVM’s Analysis and Transform Passes — LLVM 18.0.0git documentation for the command line option. See
llvm::createLowerInvokePass(...) in Scalar.h; note the comments. However this kind of
implementation does not do stack unwinding but rather creates the standard longjmp to a pevious
setjmp behavior. This is why I thought the pursuit of the zero cost (exception setup with no throw), unwind
approach was worth being caught by the venus fly trap.

There are actually limits to my madness, you know. It would be more
profitable to learn another aspect of the system by implementing a MMIX
back-end or something.

Funny I was thinking the same thing. Implementing MIX would be a cool way to learn the other side
of LLVM (backends). I didn't even know there was a MMIX until your email forced me to query.

Or, and I know this is just *crazy* talk, I could actually follow the
intended learning path and use the main C++ API for something.

Well, even though I did not take your route, I still use the IR ref. doc as my true documentation. It is
fairly isomorphic to C++ IR API. So I think your approach is worth while.

Dustin

Garrison

[Dustin_Laurence]

I
personally view LLVM as a term re-writing system where the rules are
controlled by the developer a priori.

Hopefully I'll remember that comment when I understand its significance
better.

Funny I was thinking the same thing. Implementing MIX would be a cool
way to learn the other side of LLVM (backends).

It seemed appropriate, especially since I've always been too lazy to
really learn MIX and that's unfortunate when one wants to go to the
source instead of read one of Knuth's interpreters. I haven't needed to
do that often, but one should always have the option. Also, I have
common hardware so I have no real motivation to target a real machine
(the only possible reason I could see is if I wanted to buy a board and
do robotics with my boy, and at five he's not ready for that yet). So
doing an (M)MIX backend would have the salutary effect of making me able
to read Knuth better and that's more motivating than real hardware I'm
not actually using myself.

Plus, a priori I'd guess that (M)MIX is very likely more consistent and
less quirky than any real architecture, as it has no practical
constraints or opportunities to exploit.

(M)Mix would probably be a good choice for a backend-writing tutorial.
I think expectations would be suitably modest--I don't think anyone is
going to port the Linux kernel to MIX or anything, so presumably one
wouldn't get endless requests to tweak the code gen to within an inch of
its life. The existence of both MIX and MMIX could even be an advantage
if both were supported, as one would have examples of both CISC and RISC
style architectures.

...I didn't even know
there was a MMIX until your email forced me to query.

I guess MMIX is to MIX as x86-64 is to 16-bit x86. Hopefully that
rather than it being like ia64 is to x86.

Of course, the usefulness of MMIX more or less depends on Knuth
finishing stuff.

Well, even though I did not take your route, I still use the IR ref.
doc as my true documentation. It is fairly isomorphic to C++ IR API.
So I think your approach is worth while.

I hope so. Though of course I have an agenda for learning LLVM too, and
if that pans out I won't be able to escape doing things normally. I do
not envision writing interpreters for anything more complex than Forth
or Lisp in IR.

One advantage this backwards approach has is exposing more of the real
machine nature than even C. I'd like to think that makes one a better
compiler user in the end. It's nice to know what all those nice
high-level semantics are really costing you. I think part of my
motivation, besides just doing the unexpected, is that long ago someone
told me they took a class in "assembly and lisp"; basically, they taught
programming by teaching you how to implement a higher-level language.
Being young and stupid, I didn't see the point, but eventually I figured
it out. It's never too late to re-do your childhood right, is it?

I also think that the effort to write good code at such a low level is
very good discipline. At least, I find it so, because the consequences
of good and bad design become magnified. The absence of scope nesting
and the difficulty of doing many simple operations really makes
factoring out a vocabulary of small toolkit functions useful, for
example, and that's not a bad discipline to reinforce. I just created a
couple of functions whose body is a single shift simply because it
enforced some abstraction and the names are documentation. I can always
move the body into the header and let LLVM inline them if I want to
optimize away the function call overhead (not that there is any great
need to do that in a learning tool). (It's easy to tell which parts of
the code I care about. The expression representation is pretty cleanly
divided into a toolkit. The user interaction loop is a big fat function
I didn't take the time to decompose.)

Apropos of nothing, learning that I'm not going to use invoke/unwind
puts me back a bit while I bloat and uglify the evaluator code with
exception tests and unwinding, but I'm not that far from Turing
completeness now and that's kind of a good feeling. I probably
didn't oblige myself to go further than that unless I just want to.

Dustin