Yhc/Notes
< Yhc
Yhc Bytecode
AUTHOR: Neil Mitchell & Tom Shackell
DATE: 1 Nov 2005
An instant message conversation, contains details about yhc bytecode
--
Neil: can i ask a few questions on yhc bytecode?
Tom: sure.
Neil: PUSH_ARG 0 1 <["218"] | {"218"}>
what is the 218 for?
also, bcodecompile, mem, flatten, rel - what is the order of these stages?
Tom: in order to do stack and argument zapping it's necessary to know what variables are live at any time.
Neil: so they are annotations?
Tom: IIRC the [218] says variable with id 218 is needed at this point and {218} says that 218 is the only live variable at this point.
Neil: cool
(will make sure i convert all the stuff in this irc into documentation...)
and the bit before the < | > is the stack depth?
Tom: the order is first it compiles the expressions into code, then it does memory analysis, then it flattens the call graph into jumps and then it turns the jumps into relative jumps.
Neil: cool
Tom: yes that's the stack depth.
Neil: eval is evaluate to whnf i guess
Tom: yup.
Neil: mk_ap?
what are the numbers, and does it use the stack?
Tom: builds an application node in the heap, using the arguments on the stack.
Neil: application to what?
Tom: you'd need to show me an example for me to tell you what the numbers were :-)
Neil: FUN Main;fac{189}(2/0) ["v218","v219"]
STACK 3
{
PUSH_ARG 0 1 <["218"] | {"218"}>
EVAL 1 <[] | {}>
INT_CASE {1 -> L_2, _ -> L_4} 1 <[] | {}>
L_2 1 <[] | {}>
POP 1 0 <[] | {}>
PUSH_ARG 1 1 <["219"] | {"219"}>
EVAL 1 <[] | {}>
JUMP L_3 1 <[] | {}>
L_4 1 <[] | {}>
POP 1 0 <[] | {}>
JUMP L_0 0 <[] | {}>
L_3 1 <[] | {}>
JUMP L_1 0 <[] | {}>
L_0 0 <[] | {}>
PUSH_ARG 1 1 <["219"] | {"219"}>
PUSH_ARG 0 2 <["218"] | {"218"}>
MK_AP 0 2 1 <[] | {}>
PUSH_INT 1 2 <[] | {}>
PUSH_ARG 0 3 <["218"] | {"218"}>
MK_AP 1 2 2 <[] | {}>
MK_AP 2 2 1 <[] | {}>
EVAL 1 <[] | {}>
L_1 1 <[] | {}>
RETURN 1 <[] | {}>
}
the first mk_app 0 2
Tom: mk_app using the function described in constant table item 0, with 2 arguments.
Neil: oh! constraint table
Tom: constant table :-)
Neil: yeah, thats obvious now - forgot abou tit
and push_int is just a specialised version of push with the constant 1?
http://thread.gmane.org/gmane.comp.lang.haskell.glasgow.user/8827
Tom: indeed.
Neil: was reading that thread, and wanted to see what yhc gives for it
see if we can beat ghc for factorial :)
Tom: something completely different, because yhc is based on a stack machine :-)
Neil: i released hoogle and hugs in beta today
Tom: very unlikely :-)
Neil: so i need a new project
using yhc to beat ghc for speed in at least one ridiculous microbenchmark might be it!
Tom: ehehe I wouldn't bother :-)
Neil: we'll see
i feel i should know more about yhc's details
Sent at 4:32 pm on Tuesday
Tom: feel free to read the source code or ask questions :-)
Neil: i was going to write up a document on the bytecode
as a way to learn
and for documentation
Tom: sounds good :-)
Neil: possibly an executable spec....
Tom: you won't like the source code for the backend of the compiler though :-)
Neil: i know, too many monads!
zap is purely for gc issues, right?
Tom: no zapping is to prevent memory leaks.
Neil: what does zap'ing something do?
Tom: zapping the nth stack item replaces it with a reference to a runtime-known object, same with zapping an argument.
Neil: and that argument is fixed, so gc can collect the argument that was there?
kind of like setting a pointer to null, so gc can clean up?
Tom: yup exactly that idea.
Neil: cool
ok, now going to "execute" it in my head, and see where i get, cheers
Tom: np :-)
Neil: return_eval ?
and end_code
i guess return_eval is eval then return
does something have a special return register?
Tom: return_eval is indeed eval,return although it's more clever about that stack. No it returns on the top of the stack.
Neil: so is return just equivalent to push?
or does it pop the elements beneath the result off
Tom: no ... it removes the top frame from the stack aswell.
Neil: so it removes the elements beneath the result?
Tom: so if the stack before was
X,Y,Z,Frame1,A,B,C,Frame2
then after it is
X,A,B,C,Frame2
Neil: where C is the result returned
Tom: where X was the result returned sorry.
Neil: sorry, reading it the wrong direction...
Tom: (my frames go that way :-))
Neil: Frame1 is the arguments to the function?
Tom: a frame is used to record 3 peices of information:
- the code pointer to return to at the end of the current function call
- the node under evaluation to use when returning
- the address of the previous frame
Neil: ok, got it
and END_CODE?
Tom: end_code is a marker to make sure the program doesn't end up outside the code, for example if the compiler forgot to generate a return or got a jump destination wrong or something.
Neil: cool, i guessed that
fantastic, cheers
Tom: it's actually useful having someone else document something you wrote :-) because then they don't skip over the bits you consider to be obvious :-)
Neil: indeed
and for laziness, is only eval lazy?
i.e. it runs linearly, until it gets to an eval which might cause it to invoke a mk_ap ?
Tom: no ... how much do you know about how functional programs are implemented in general?
Neil: a bit....
will just assume "neil" semantics, and might ask for more help in person
i guess that's a hard bit :)
Tom: okay, well laziness is dealt with using thunks. A thunk is a piece of memory that says
a) which function to call
b) which arguments to call it with.
MK_AP produces a thunk for a given function. When an EVAL instruction is used either a constructor is on the top of the stack or a thunk is. If it's a constructor EVAL is a NOP. if it's a thunk EVAL calls the function named by the thunk with the arguments inside the thunk.
Neil: ok, i get that
so all code is "simple linear time" apart from eval
i.e. once you do the first instruction, you do to the end
Tom: yup, apart from jumps :-)
Neil: i got that :)
Tom: but yes, another interesting property is that there are no backward jumps./
Neil: oh...
i'm going to have a go at hand optimising fac
and see if you could have yhc -o or something...
why does fac eval before returning?
surely it could just return a thunk
oh, i get it
Tom: no function should ever return a WHNF.
since that function must have been called by EVAL.
Neil: so every function should return a WHNF
Tom: no it should always return a HNF.
i.e. evaluated.
Neil: i.e. at least HNF => WHNF ?
it must return fully evaluted expressions?
Tom: it must either return
a) a constructor of some sort
b) an application that does not have enough arguments to be evaluated further (a so called 'partial application).
Neil: ok, so WHNF for constructors
or partial apps
Tom: a constructor is a HNF, not a WHNF. WHNF = thunk.
Neil: hmm, i use WHNF for a constructor at teh root
so my WHNF is your HNF
(i may well be wrong...)
Tom: ehehe well most people generally view a constructor as a head normal form ;-)
Neil: i think i got it off wikipedia...
Tom: In the lambda calculus, a term is in beta normal form if no beta reduction is possible ... . A term is in head normal form if there is no beta-redex in head position.
a constructor has no redex in the head position, because it's fully evaluated.
Neil: ok
Sent at 5:06 pm on Tuesday
Factorial optimisation
AUTHOR: Neil Mitchell
DATE: 01 Nov 2005
Thoughts on how to optimise factorial
--
====== BCode after flattening::
FUN Main;fac{189}(2/0) ["v218","v219"]
STACK 3
{
L_5
NEED_HEAP 4
PUSH_ARG 0
EVAL
L_2
INT_SWITCH {1 -> L_1, _ -> L_4}
L_1
NEED_HEAP 3
POP 1
PUSH_ZAP_ARG 1
RETURN_EVAL
L_4
NEED_HEAP 16
POP 1
PUSH_ZAP_ARG 1
PUSH_ARG 0
MK_AP 0 2
PUSH_INT 1
PUSH_ZAP_ARG 0
MK_AP 1 2
MK_AP 2 2
RETURN_EVAL
END_CODE
}
---- ConstTable ---------------
0 FUN Prelude;Prelude.Num.Prelude.Int.*{216}
1 FUN Prelude;Prelude.Num.Prelude.Int.-{215}
2 FUN Main;fac{189}
-------------------------------
1 ######################################
Lets convert this into friendlier syntax
and drop the GC relevant bits
main.fac(a, b)
push a
eval
switch (1 -> L1, _ -> L2)
L1
pop
push b
eval
return
L2
pop
push b
push a
app * 2
push 1
push a
app - 2
app fac 2
eval
return
2 ######################################
Stack motion, pop; push x is equivalent to push x; push y at the previous push
push x; pop; push x is just push x
main.fac(a, b)
push b
push a
eval
switch (1 -> L1, _ -> L2)
L1
pop
eval
return
L2
app * 2
push 1
push a
app - 2
app fac 2
eval
return
3 ######################################
Determine by strictness analysis that fac is strict in both arguments
This is relatively easy - look down each path, either all arguments are eval'd
Or its a recursive call, hence all arguments are always eval'd
Its easier because its Int, therefore eval is full eval
This allows us to move eval b to the common part
main.fac(a, b)
push b
eval
push a
eval
switch (1 -> L1, _ -> L2)
L1
pop
return
L2
app * 2
push 1
push a
app - 2
app fac 2
eval
return
4 ######################################
Since simple analysis now gives us that * and + are applied to strict arguments
lets convert that into call, instead of app
main.fac(a, b)
push b
eval
push a
eval
switch (1 -> L1, _ -> L2)
L1
pop
return
L2
call * 2
push 1
push a
call - 2
call fac 2
return
5 ######################################
Now we have a tailcall, since fac 2 already has a and b on the stack
and since they are both fully evaluated, we can skip that bit
it appears the order in the call is wrong though, so lets fix that by swapping them
main.fac(a, b)
push b
eval
push a
eval
L0
switch (1 -> L1, _ -> L2)
L1
pop
return
L2
call * 2
push 1
push a
call - 2
swap
goto L0
6 ######################################
That's as good as the bytecode can go, I think, but now lets head off to a C generator
plus a wrapper for the boxing/unboxing
main.fac(a, b)
{
L0:
if (a == 1)
{
return b
}
else
{
int ta = a - 1
int tb = a * b
a = ta
b = tb
goto L0
}
}
7 ######################################
goto, urgh - lets hoist it into a loop
main.fac(a, b)
{
while (a != 1)
{
int ta = a - 1
int tb = a * b
a = ta
b = tb
}
return b
}
8 ######################################
and lets get rid of those temporaries
main.fac(a, b)
{
while (a != 1)
{
b *= a--
}
return b
}
9 #####################################
Done, and I'm certain GHC doesn't do any better!