parrot bug: continuations/multiple return
Michal Wallace
Hey all,
Sorry for the huge code listing here, but I don't
have a simpler case. This is what pirate outputs
when it compiles the following program:
def f(x):
if x:
return 1
else:
return 0
print f(1), f(0)
As far as I can tell, I'm doing exactly the same thing
for the return 1 and return 0 branches... But the output
of this program is:
"1 get_string() not implemented in class 'Continuation'\n"
Calling f(0) causes the bug even if f(1) isn't called first.
I think this is a bug in parrot's register allocation scheme.
Or am I just doing something stupid? :)
BTW: It would be SO nice if parrot could print a line
number for ALL its error messages. (Or if the debugger
didn't segfault <g>)
######################################
.sub __main__
new_pad 0
setline 1
newsub $P0, .Sub, _sub0
store_lex -1, 'f', $P0
.local object arg0
arg0 = new PerlInt
arg0 = 1
find_lex $P2, 'f'
newsub $P3, .Continuation, ret0
.pcc_begin non_prototyped
.arg arg0
.pcc_call $P2, $P3
ret0:
.result $P1
.pcc_end
.arg $P1
call __py__print
print " "
.local object arg1
arg1 = new PerlInt
arg1 = 0
find_lex $P5, 'f'
newsub $P6, .Continuation, ret1
.pcc_begin non_prototyped
.arg arg1
.pcc_call $P5, $P6
ret1:
.result $P4
.pcc_end
.arg $P4
call __py__print
print "\n"
end
.end
.include 'pirate.imc'
# f from line 1
.pcc_sub _sub0 non_prototyped
.param object x
setline 2
.local object test0
test0 = new PerlInt
test0 = x
unless test0 goto elif0 ### if x return 1
.local object res0
res0 = new PerlInt
res0 = 1
.pcc_begin_return
.return res0
.pcc_end_return
goto endif0
elif0: ### else return 0
.local object res1
res1 = new PerlInt
res1 = 0
.pcc_begin_return
.return res1
.pcc_end_return
endif0:
.end
######################################
Sincerely,
Michal J Wallace
Sabren Enterprises, Inc.
-------------------------------------
contact: mic...@sabren.com
hosting: http://www.cornerhost.com/
my site: http://www.withoutane.com/
--------------------------------------
Leopold Toetsch
> def f(x):
> if x:
> return 1
> else:
> return 0
> print f(1), f(0)
Nice coincidence. S. Togos' bug report too.
Anyway, its already fixed.
leo
Michal Wallace
> Nice coincidence. S. Togos' bug report too.
> Anyway, its already fixed.
Gosh you're quick. Thanks!
Want another one? :)
def g():
return 0
def f():
return g()
print f()
This prints:
'No more I register frames to pop!'
I was hoping those two were the same problem,
but it doesn't look like it. This happens any
time one function calls another, whether it passes
in arguments or not. The bug seems to happen on
the "return 0" line.
(It may very well be my generated code, but I
can't find it if it is)
##############################
.sub __main__
new_pad 0
setline 1 # (set_lineno:81)
newsub $P0, .Sub, _sub0 # (genFunction:378)
store_lex -1, 'g', $P0 # (genFunction:380)
setline 3 # (set_lineno:81)
newsub $P1, .Sub, _sub1 # (genFunction:378)
store_lex -1, 'f', $P1 # (genFunction:380)
find_lex $P5, 'f' # (callingExpression:325)
newsub $P6, .Continuation, ret1# (callingExpression:331)
.pcc_begin non_prototyped # (callingExpression:332)
.pcc_call $P5, $P6 # (callingExpression:335)
ret1:
.result $P4 # (callingExpression:338)
.pcc_end # (callingExpression:339)
.arg $P4 # (visitPrint:394)
call __py__print # (visitPrint:395)
print "\n" # (visitPrintnl:403)
end # (compile:574)
.end
.include 'pirate.imc'
# g from line 1
.pcc_sub _sub0 non_prototyped
.local object res0 # (visitReturn:528)
res0 = new PerlInt # (expressConstant:153)
res0 = 0 # (expressConstant:154)
.pcc_begin_return # (visitReturn:530)
.return res0 # (visitReturn:531)
.pcc_end_return # (visitReturn:532)
.end
# f from line 3
.pcc_sub _sub1 non_prototyped
.local object res1 # (visitReturn:528)
find_lex $P2, 'g' # (callingExpression:325)
newsub $P3, .Continuation, ret0# (callingExpression:331)
.pcc_begin non_prototyped # (callingExpression:332)
.pcc_call $P2, $P3 # (callingExpression:335)
ret0:
.result res1 # (callingExpression:338)
.pcc_end # (callingExpression:339)
.pcc_begin_return # (visitReturn:530)
.return res1 # (visitReturn:531)
.pcc_end_return # (visitReturn:532)
.end
Leopold Toetsch
> Gosh you're quick. Thanks!
Welcome
> Want another one? :)
Always.
> def g():
> return 0
> def f():
> return g()
> print f()
>
>
> This prints:
>
> 'No more I register frames to pop!'
The return continuation P1 in f() isnt preserved.
> # f from line 3
> .pcc_sub _sub1 non_prototyped
.local Continuation retcc
retcc = P1
> .local object res1 # (visitReturn:528)
> find_lex $P2, 'g' # (callingExpression:325)
> newsub $P3, .Continuation, ret0# (callingExpression:331)
> .pcc_begin non_prototyped # (callingExpression:332)
> .pcc_call $P2, $P3 # (callingExpression:335)
> ret0:
> .result res1 # (callingExpression:338)
> .pcc_end # (callingExpression:339)
P1 = retcc
> .pcc_begin_return # (visitReturn:530)
> .return res1 # (visitReturn:531)
> .pcc_end_return # (visitReturn:532)
> .end
As calling conventions clearly state, that the caller has to save
everything, its probably up to imcc/pcc.c to insert above statements, if
another sub gets called from a sub. I'll fix that in a minute ;-)
> Michal J Wallace
Thanks,
leo
Michal Wallace
> As calling conventions clearly state, that the caller has to save
> everything, its probably up to imcc/pcc.c to insert above statements, if
> another sub gets called from a sub. I'll fix that in a minute ;-)
I just synced up with cvs and now everything works! Thanks!
Piers Cawley
> As calling conventions clearly state, that the caller has to save
> everything, its probably up to imcc/pcc.c to insert above
> statements, if another sub gets called from a sub. I'll fix that in
> a minute ;-)
If and only if that's not a tail call of course.
Benjamin Goldberg
[snip]
> def f():
> return g()
[snip]
> # f from line 3
> .pcc_sub _sub1 non_prototyped
> find_lex $P2, 'g' # (callingExpression:325)
> newsub $P3, .Continuation, ret0# (callingExpression:331)
> .pcc_begin non_prototyped # (callingExpression:332)
> .pcc_call $P2, $P3 # (callingExpression:335)
> ret0:
> .result res1 # (callingExpression:338)
> .pcc_end # (callingExpression:339)
> .return res1 # (visitReturn:531)
> .pcc_end_return # (visitReturn:532)
> .end
Does python allow tail calls to be optomized? That is, would it be
legal python semantics if f were to become:
.pcc_sub _sub1 non_prototyped
find_lex $P2, 'g'
.pcc_begin non_prototyped
.pcc_call $P2, P1
.pcc_end
.end
(untested)
Also... why is $P2 merely an imcc temporary, without a real name? That
is, why not do:
.pcc_sub _sub1 non_prototyped
.local object sub1
find_lex sub1, 'g'
.pcc_begin non_prototyped
.pcc_call sub1, P1
.pcc_end
.end
The more different prefixes you use ("res", "sub", "$P"), the lower the
numbers you'll need to append to them to make the names unique. Not to
mention, it'll make the generated code more meaningful.
Another advantage is that with '.local' names, if you accidentally use a
name declared in one subroutine, in another, imcc will consider this to
be an error. Such a mistake might be otherwise difficult to spot.
--
$a=24;split//,240513;s/\B/ => /for@@=qw(ac ab bc ba cb ca
);{push(@b,$a),($a-=6)^=1 for 2..$a/6x--$|;print "$@[$a%6
]\n";((6<=($a-=6))?$a+=$_[$a%6]-$a%6:($a=pop @b))&&redo;}
Leopold Toetsch
Good point. But I can imagine, that's by far more simple to detect tail
calls at the AST level then inside the flattened code parrot sees. So
the HL can emit (a TBD) flag like "tailcall" appended to the .pcc_call
sequence.
Then the call can be optimized to a C<jump> opcode. The construction of
the subroutine object (which is outside of the call sequence) will lead
to an used once LHS, which the optimizer already can get rid of.
leo
Michal Wallace
Well, the "real" python doesn't optimize tail-calls at all.
You'll get a nasty "max recursion depth exceeded" traceback
if you try running "def f(x): return f(x+1)"
But I don't see any reason pirate shouldn't do it, since the
difference is pretty much transparent.
> (untested)
> Also... why is $P2 merely an imcc temporary, without a real name? That
> is, why not do:
>
> .pcc_sub _sub1 non_prototyped
> .local object sub1
> find_lex sub1, 'g'
> .pcc_begin non_prototyped
> .pcc_call sub1, P1
> .pcc_end
> .end
>
> The more different prefixes you use ("res", "sub", "$P"), the lower the
> numbers you'll need to append to them to make the names unique. Not to
> mention, it'll make the generated code more meaningful.
>
> Another advantage is that with '.local' names, if you accidentally use a
> name declared in one subroutine, in another, imcc will consider this to
> be an error. Such a mistake might be otherwise difficult to spot.
Hmmm. The counters are global so there shouldn't be any conflicts.
I'd actually been trying to move away from .local now that I started
using lexicals... If there's going to be two sets of names for
everything I'd rather one of them was just $Pxx...
Now, if I could say:
.lexical g
That would be really nice... :)
Michal Wallace
Well, if you write it, I'll have pirate inspect the AST
and try it out for you. :)
Benjamin Goldberg
> Benjamin Goldberg wrote:
> > Michal Wallace wrote:
[snip]
> > That is, why not do:
> >
> > .pcc_sub _sub1 non_prototyped
> > .local object sub1
> > find_lex sub1, 'g'
> > .pcc_begin non_prototyped
> > .pcc_call sub1, P1
> > .pcc_end
> > .end
> >
> > The more different prefixes you use ("res", "sub", "$P"), the lower
> > the numbers you'll need to append to them to make the names unique.
> > Not to mention, it'll make the generated code more meaningful.
> >
> > Another advantage is that with '.local' names, if you accidentally use
> > a name declared in one subroutine, in another, imcc will consider this
> > to be an error. Such a mistake might be otherwise difficult to spot.
>
> Hmmm. The counters are global so there shouldn't be any conflicts.
> I'd actually been trying to move away from .local now that I started
> using lexicals... If there's going to be two sets of names for
> everything I'd rather one of them was just $Pxx...
Ehh, why would there be two sets of names for everything? You mean, one
of them the name to lookup in the pad, the other the imcc name of the
register to use? There's no reason not to use the same name for both.
(Except that using a unique .local name is still good for preventing
accidental leakage of a name from one sub to another)
> Now, if I could say:
>
> .lexical g
>
> That would be really nice... :)
This is where .macro comes in handy :)
.macro lexical(name_in_pad, register_name)
local .register_name
find_lex .register_name, .name_in_pad
.endm
And in pirate.py, you'd do:
self.append('.lexical "%s" %s', lexname, lexname)
Ok, so it's not *quite* what you were asking for, but it's close enough,
eh? :)
Piers Cawley
I'm not sure you can optimize it to a jump opcode when you're tail
calling another function can you? You could be tailcalling into a
closure so you'll need to use invoke to do the right thing with the
lexical stack etc.
Leopold Toetsch
> This is where .macro comes in handy :)
> .macro lexical(name_in_pad, register_name)
> local .register_name
> find_lex .register_name, .name_in_pad
> .endm
Macros are currently enabled for PASM mode only. But there is no special
reason, that they shouldn't be enabled in PIR mode too, if needed.
leo
Leopold Toetsch
> On Sun, 10 Aug 2003, Leopold Toetsch wrote:
>> Piers Cawley <pdca...@bofh.org.uk> wrote:
>> > If and only if that's not a tail call of course.
>>
>> Good point. But I can imagine, that's by far more simple to detect tail
>> calls at the AST level
> Well, if you write it, I'll have pirate inspect the AST
> and try it out for you. :)
I have checked in a first attempt to do tail call optimizations. I don't
know yet, when its safe or not to perform this optimization and if a
rather simple test like now may detect all these cases.
So for now, $HL could append a comment "#tail_call" after the prototyped
specifier of the sub call. Then we can compare the debug output of
$ parrot -Oc -d60 x.imc
if both would do a tail call or not.
> Sincerely,
>
> Michal J Wallace
leo
Leopold Toetsch
> I'm not sure you can optimize it to a jump opcode when you're tail
> calling another function can you? You could be tailcalling into a
> closure so you'll need to use invoke to do the right thing with the
> lexical stack etc.
Argh, yes. What about:
If the subroutine is constructed inside the sub, parrot sees the class
and can decide at compile time to either jump or invoke.
If the subroutine is passed in, a runtime check could be done:
if sub.isa("Sub") goto do_jump
invoke
leo
Piers Cawley
Umm... not sure quite what you mean there. Don't forget that the sub
could be got by doing:
find_lex P0, 'sub_name'
Juergen Boemmels
One of my projects is to allow tail-calls in languages/scheme (Don't
assume anything in the near future; i currently work on the io-system
and its near and far friends). My plan for this is to use a new
emitting instruction _tail_call_function which does emit
find_lex P0, 'name'
invoke # this does not change P1
instead of
find_lex P0, 'name'
save P1
invokecc # this uses P1 as return address
restore P1 # invoke P1 from the function brings us back here
invoke P1 # this brings us back to our caller
which the current _call_function would emit
Thinking a little about it, even call/cc is very simple to implement
# checking of arguments
set P0, P5 # first argument is the function which will be called
set P5, P1 # first argument of the called function is cc
invoke # tail call
No jumps are needed in this code. Jump should get translated
jmp/branch -> invoke
jsr/bsr -> invokecc
ret -> invoke P1
bye
boe
--
Juergen Boemmels boem...@physik.uni-kl.de
Fachbereich Physik Tel: ++49-(0)631-205-2817
Universitaet Kaiserslautern Fax: ++49-(0)631-205-3906
PGP Key fingerprint = 9F 56 54 3D 45 C1 32 6F 23 F6 C7 2F 85 93 DD 47
Leopold Toetsch
> Leopold Toetsch <l...@toetsch.at> writes:
>> If the subroutine is passed in, a runtime check could be done:
>>
>> if sub.isa("Sub") goto do_jump
>> invoke
> Umm... not sure quite what you mean there. Don't forget that the sub
> could be got by doing:
> find_lex P0, 'sub_name'
That's kind of a "passed in". So the runtime check variant applies.
leo