llvm dev - Feb 2009 - [LLVMdev] Broke my tail (call)

Hello Duncan and Jon,

I am the criminal responsible for the tail call implementation in the backends.

On Mon, Feb 23, 2009 at 9:17 AM, Duncan Sands <baldrick at free.fr>
wrote:
> Hi Jon,
>
>> >From what I have understood of the LLVM docs about when tail calls
get
>> eliminated on x86 and x64 it should be a tail call, yes.
See below.
> this list is for the code generator, and it seems obviously incomplete: it
makes
> no mention of local variables (alloca).  Probably it is implicitly assuming
that
> the call was marked "tail call" by the LLVM optimizers.  So you
also need to check
> under what conditions the LLVM optimizers do that.
The backend does not check the following condition but assumes it to be true.
>From <http://llvm.org/docs/LangRef.html#i_call>:
The optional "tail" marker indicates whether the callee function
accesses any allocas or varargs in the caller. If the "tail" marker is
present, the function call is eligible for tail call optimization.
Note that calls may be marked "tail" even if they do not occur before
a ret instruction.

If the llvm IR is generated by a front end (HLVM) the front end must
guarantee this condition.

>> > I didn't look closely but at a glance it seems to be passing a
local stack
>> > variable as a call parameter.
To me, also only glancing over the code and with a bit rusty llvm ir
knowledge, it seems that %14 (the value passed to the tail call)is
allocated in the stack frame  (alloca) of the calling function. So the
above condition is violated.

%3   = alloca { { i8*, i8* }*, i8* }
%13 = getelementptr { { i8*, i8* }*, i8* }* %3, i32 0
%14 = load { { i8*, i8* }*, i8* }* %13
%17 = tail call fastcc { { i8*, i8* }*, i8* }
     @init({ { i8*, i8* }*,i8*} %14, i32 %16)
>> Is this a bug in LLVM?
> Could be, but first I'd like to be sure that you are not misusing tail
calls.
Assuming that i am right and a pointer to alloca'ed memory is passed
this is not a bug but a misuse of the 'tail' instruction.

Maybe we should add a link or a note on
<http://llvm.org/docs/CodeGenerator.html#tailcallopt> to
<http://llvm.org/docs/LangRef.html#i_call> that explains that the call
can only be marked as 'tail' if no pointers to alloca'ed memory are
passed.

regards arnold

On Monday 23 February 2009 12:08:00 Arnold Schwaighofer
wrote:
> Hello Duncan and Jon,
>
> I am the criminal responsible for the tail call implementation in the
> backends.
Thanks! :-)
> On Mon, Feb 23, 2009 at 9:17 AM, Duncan Sands <baldrick at free.fr>
wrote:
> > Hi Jon,
> >
> >> >From what I have understood of the LLVM docs about when tail
calls get
> >>
> >> eliminated on x86 and x64 it should be a tail call, yes.
>
> See below.
>
> > this list is for the code generator, and it seems obviously
incomplete:
> > it makes no mention of local variables (alloca).  Probably it is
> > implicitly assuming that the call was marked "tail call" by
the LLVM
> > optimizers.  So you also need to check under what conditions the LLVM
> > optimizers do that.
>
> The backend does not check the following condition but assumes it to be
> true.
>
> >From <http://llvm.org/docs/LangRef.html#i_call>:
>
> The optional "tail" marker indicates whether the callee function
> accesses any allocas or varargs in the caller. If the "tail"
marker is
> present, the function call is eligible for tail call optimization.
> Note that calls may be marked "tail" even if they do not occur
before
> a ret instruction.
>
> If the llvm IR is generated by a front end (HLVM) the front end must
> guarantee this condition.
Right, that is in agreement with my observations:

1. Blindly setting "tail" everywhere in HLVM breaks some of LLVM's
optimization passes (which blindly assume it to be correct) and culminates in 
the generation of broken code.

2. Passing a reference to a local struct on the current stack frame through a 
tail call by reference is *not* detected as an error by LLVM and produces 
code that corrupts data by overwriting the memory locations of the struct 
from the caller with whatever the callee uses the same stack frame for.
> >> > I didn't look closely but at a glance it seems to be
passing a local
> >> > stack variable as a call parameter.
>
> To me, also only glancing over the code and with a bit rusty llvm ir
> knowledge, it seems that %14 (the value passed to the tail call)is
> allocated in the stack frame  (alloca) of the calling function. So the
> above condition is violated.
>
> %3   = alloca { { i8*, i8* }*, i8* }
> %13 = getelementptr { { i8*, i8* }*, i8* }* %3, i32 0
> %14 = load { { i8*, i8* }*, i8* }* %13
> %17 = tail call fastcc { { i8*, i8* }*, i8* }
>      @init({ { i8*, i8* }*,i8*} %14, i32 %16)
I do not understand. Surely you should be testing for structs locally 
allocated on the caller's frame being passed *by reference* to the callee?
In
this case, the struct is passed by value so the fact that it came from the 
stack should be irrelevant: that stack space is not being depended upon 
because the fields of the struct are now in registers.

This is all swinging on my interpretation of first-class structs though. I am 
under the impression that they are essentially a set of registers holding 
their first-class fields. So you can pass them by value as arguments to 
functions with the behaviour of any other first-class type regardless of 
where they came from.
> >> Is this a bug in LLVM?
> >
> > Could be, but first I'd like to be sure that you are not misusing
tail
> > calls.
>
> Assuming that i am right and a pointer to alloca'ed memory is passed
> this is not a bug but a misuse of the 'tail' instruction.
I disagree. I think the fields of the struct should be passed by value with no 
pointer to the original alloca'd data.

Moreover, I now have evidence that LLVM is not behaving as you expect:

3. Adjusting the return value from this function into sret form results in 
tail call elimination being performed correctly. Note that this is still 
passing a first-class struct by value as an argument to a function through a 
tail call.

Here is my code that does get tail call eliminated correctly:

define fastcc i32 @init({ i8*, i8* }*, { i8*, i8* }, i32) {
entry:
	%3 = alloca { i32, { i8*, i8* } }		; <{ i32, { i8*, i8* } }*> [#uses=3]
	%4 = alloca { i8*, i8* }		; <{ i8*, i8* }*> [#uses=3]
	br label %start

start:		; preds = %entry
	%5 = bitcast { i32, { i8*, i8* } }* %3 to i32*		; <i32*> [#uses=1]
	store i32 %2, i32* %5
	%6 = getelementptr { i32, { i8*, i8* } }* %3, i32 0, i32 1		; <{ i8*, i8*
}*>
[#uses=1]
	store { i8*, i8* } %1, { i8*, i8* }* %6
	%7 = bitcast { i32, { i8*, i8* } }* %3 to { i32, { i8*, i8* } }*		; <{ i32,
{
i8*, i8* } }*> [#uses=1]
	%8 = load { i32, { i8*, i8* } }* %7		; <{ i32, { i8*, i8* } }> [#uses=1]
	%9 = malloc { i32, { i8*, i8* } }		; <{ i32, { i8*, i8* } }*> [#uses=2]
	%10 = bitcast { i32, { i8*, i8* } }* %9 to { i32, { i8*, i8* } }*		; <{ i32,
{ i8*, i8* } }*> [#uses=1]
	store { i32, { i8*, i8* } } %8, { i32, { i8*, i8* } }* %10
	%11 = bitcast { i32, { i8*, i8* } }* %9 to i8*		; <i8*> [#uses=1]
	%12 = bitcast { i8*, i8* }* %4 to i8**		; <i8**> [#uses=1]
	store i8* bitcast ({ i8*, i32 ({ i8*, i8* })* }* @Cons to i8*), i8** %12
	%13 = getelementptr { i8*, i8* }* %4, i32 0, i32 1		; <i8**> [#uses=1]
	store i8* %11, i8** %13
	%14 = bitcast { i8*, i8* }* %4 to { i8*, i8* }*		; <{ i8*, i8* }*>
[#uses=1]
	%15 = load { i8*, i8* }* %14		; <{ i8*, i8* }> [#uses=2]
	%16 = icmp eq i32 %2, 0		; <i1> [#uses=1]
	br i1 %16, label %pass, label %fail

fail:		; preds = %start
	%17 = sub i32 %2, 1		; <i32> [#uses=1]
	%18 = tail call fastcc i32 @init({ i8*, i8* }* %0, { i8*, i8* } %15, 
i32 %17)		; <i32> [#uses=1]
	ret i32 %18

pass:		; preds = %start
	%19 = bitcast { i8*, i8* }* %0 to { i8*, i8* }*		; <{ i8*, i8* }*>
[#uses=1]
	store { i8*, i8* } %15, { i8*, i8* }* %19
	ret i32 0
}
> Maybe we should add a link or a note on
> <http://llvm.org/docs/CodeGenerator.html#tailcallopt> to
> <http://llvm.org/docs/LangRef.html#i_call> that explains that the
call
> can only be marked as 'tail' if no pointers to alloca'ed memory
are
> passed.
The documentation should probably be clarified but I am leaning toward this 
being a bug in LLVM itself: tail call elimination should be done when the 
return value is a first-class struct.

Also, I said before that I had found first-class structs to be broken. In 
retrospect, I think I was probably observing this phenomenon and seeing a 
segmentation fault due to stack overflow caused by broken tail calls and not 
broken structs.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

> This is all swinging on my interpretation of first-class structs though. I
am
> under the impression that they are essentially a set of registers holding 
> their first-class fields. So you can pass them by value as arguments to 
> functions with the behaviour of any other first-class type regardless of 
> where they came from.
This is not true in general and highly target- and CC- dependent. For
example, you can ran out of registers and then your struct can be passed
partly in registers and partly on stack. And depending on the stack
frame size of the callee you can easily get infinite stack growth.

As for returning struct-by-value - I think the situation is more
complicated and you can expect only "small structs" to behave so
(small
= fits in the single target register)

-- 
With best regards, Anton Korobeynikov.

Faculty of Mathematics & Mechanics, Saint Petersburg State University.

On Mon, Feb 23, 2009 at 2:13 PM, Jon Harrop <jon at ffconsultancy.com>
wrote:
> Moreover, I now have evidence that LLVM is not behaving as you expect:
>
> 3. Adjusting the return value from this function into sret form results in
> tail call elimination being performed correctly. Note that this is still
> passing a first-class struct by value as an argument to a function through
a
> tail call.
Yes i was wrong the problem is of a different kind and has nothing to
do with the alloca. As you say the struct is passed by value. This is
not the problem. For example the following code (not containing any
allocas) will also not be tail call optimized.

define fastcc { { i8*, i8* }*, i8*} @init({ { i8*, i8* }*, i8*}, i32) {
entry:
       %2 = tail call fastcc { { i8*, i8* }*, i8* } @init({ { i8*, i8*
}*, i8*} %0, i32 %1)
       ret { { i8*, i8* }*, i8*} %2
}

The problem has to do with how struct returns are represented
internally by llvm (in the SelectionDAG) and how the tail call
optimization implementation checks if it may perform the tail call.
The implementation checks that the <call> node is immediately followed
by a <ret> node. A struct return causes the insertion of a
<merge_values> node between the tail call instruction and the return
instruction node. Because of the intermediate node the backend
believes it must not optimize the tail call.

[result1, result2] = <call ... >
[merged] = <merge_values [result1, result2]>
<ret [merged]>

So the current situation is that tail calls on functions that return a
struct are not optimized (as you correctly observed ;). Sorry.

regards arnold