Dear David,
As you mentioned previously, Poly/ML first compiles ML program into the IR, which is further passed to a code generator to produce low level code.
I was trying to understand and document the semantics of the opcode set used by Poly/ML's interpreter, and I'm wondering whether inside Poly/ML's compiler, there are such debugging functions which could print out the IR tree as well as the generated op code for an input ML program? These functions would help me a lot to test my understanding on Poly's IR data structure and code generation. Thank you very much!
Best,
Yue
Yue Li wrote:
I was trying to understand and document the semantics of the opcode set used by Poly/ML's interpreter, and I'm wondering whether inside Poly/ML's compiler, there are such debugging functions which could print out the IR tree as well as the generated op code for an input ML program? These functions would help me a lot to test my understanding on Poly's IR data structure and code generation. Thank you very much!
Yue, There are switches in the PolyML.Compiler structure that will print out various stages of the compilation process when compiling something. Probably the most useful for you would be PolyML.Compiler.codetree := true; which will cause the compiler to print out the code-tree. You may also find "codetreeAfterOpt" (i.e. code-tree after it has been through the optimiser) and "assemblyCode" (the machine code generated by the final code-generator) useful as well.
Regards, David
On Sun, Aug 22, 2010 at 5:32 AM, David Matthews David.Matthews@prolingua.co.uk wrote:
Yue Li wrote:
I was trying to understand and document the semantics of the opcode set used by Poly/ML's interpreter, and I'm wondering whether inside Poly/ML's compiler, there are such debugging functions which could print out the IR tree as well as the generated op code for an input ML program? These functions would help me a lot to test my understanding on Poly's IR data structure and code generation. ?Thank you very much!
Yue, There are switches in the PolyML.Compiler structure that will print out various stages of the compilation process when compiling something. Probably the most useful for you would be PolyML.Compiler.codetree := true; which will cause the compiler to print out the code-tree. ?You may also find "codetreeAfterOpt" (i.e. code-tree after it has been through the optimiser) and "assemblyCode" (the machine code generated by the final code-generator) useful as well.
This works and I can see the printed code tree now. I will have more questions later when I tried more examples.
Many thanks!!
Yue
Dear David,
After trying many example ML programs, printing out IR code tree, I've documented and understood several IR components. I accumulated several questions here, and I would appreciate if I could obtain some hints from you. I only turned on codetree flag of the compiler.
1. In the printed IR of a program, seems the print out has two sections, for example:
2 * 3;
BLOCK(DECL #1{0 uses} = GLOBAL (FUN "run_call2(1)", LAMBDAINLINE( run_call2(1) CL=false CR=0 LEV=0 LOCALS=0 ARGS=G ARGLIVES= RES=G CLOS=() LOCAL(1,1) G $(INDIRECT(0, PARAM(0,1)) G, INDIRECT(1, PARAM(0,1)) G)){LAMBDA} ) (*GLOBAL*){early} G $(LIT <long> G); DECL #2{0 uses} = LOCAL(0,1); MUTUAL(); RECCONSTR(LOCAL(0,2)) ) BLOCK(DECL #1{0 uses} = GLOBAL (FUN "run_call2(1)", LAMBDAINLINE( run_call2(1) CL=false CR=0 LEV=0 LOCALS=0 ARGS=G ARGLIVES= RES=G CLOS=() LOCAL(1,1) G $(INDIRECT(0, PARAM(0,1)) G, INDIRECT(1, PARAM(0,1)) G)){LAMBDA} ) (*GLOBAL*){early} G $(LIT <long> G); DECL #2{0 uses} = LOCAL(0,1); MUTUAL(); RECCONSTR(LOCAL(0,2)) ) POLY_SYS_amul{early} G $(LIT2 G, LIT3 G)
The first section contains two same blocks, and always the block is duplicated in the first section for every input ML program. The second section contains an expression. It seems that the second expression is included in the blocks of the first section, and I'm a little bit confused here, so why the first section duplicates the blocks, and why the expression
POLY_SYS_amul{early} G $(LIT2 G, LIT3 G)
is separately printed out?
2. TAGTEST(x, y, z) is used in several different places such as generation of the boolean constants true and false, or testing whether a list is empty, but I still couldn't find documentation of TagTest from the source code, and I'm wondering what is the semantics of TAGTEST?
3. When I printed the IR of a signature, say:
signature Set =
# sig # type element # type set # val empty : set # end; BLOCK(LIT0) BLOCK(LIT0)
I suppose here again BLOCK(LIT0) is duplicated, and I'm wondering why this signature is represented like this simple instead of using a tuple whose elements are the decls, and its internal representations?
4. I found some documentation about the members of LAMBDA, but still couldn't figure out how CL, CR and LOCALS are determined. In all my testing cases, always CL=false, and CR=0. Also for LOCALS, I thought it indicates the times that local variables are used. For instance:
fun f a = a + 2;
BLOCK(DECL #1{0 uses} = LAMBDA( f(1) CL=false CR=0 LEV=0 LOCALS=0 ARGS=G ARGLIVES= RES=G CLOS=() BLOCK(BLOCK(DECL #2{0 uses} = PARAM(0,1); GLOBAL (FUN "run_call2(1)", LAMBDAINLINE( run_call2(1) CL=false CR=0 LEV=0 LOCALS=0 ARGS=G ARGLIVES= RES=G CLOS=() LOCAL(1,1) G $(INDIRECT(0, PARAM(0,1)) G, INDIRECT(1, PARAM(0,1)) G)){LAMBDA} ) (*GLOBAL*){early} G $(RECCONSTR(LOCAL(0,2), LIT2) G) ) )){LAMBDA}; RECCONSTR(LOCAL(0,1)) )
(* the skip the duplicated copy of the above block)
LAMBDASMALL( f(1) CL=false CR=0 LEV=1 LOCALS=3 ARGS=G ARGLIVES= RES=G CLOS=() POLY_SYS_aplus{early} G $(PARAM(0,1) G, LIT2 G)){LAMBDA}
Here I don't quite understand why LOCALS in the first Block is always 0, and why the LOCALS below is 3.
Thank you very much!!
-- Yue
On Sun, Aug 22, 2010 at 3:22 PM, Yue Li xyly781@gmail.com wrote:
On Sun, Aug 22, 2010 at 5:32 AM, David Matthews David.Matthews@prolingua.co.uk wrote:
Yue Li wrote:
I was trying to understand and document the semantics of the opcode set used by Poly/ML's interpreter, and I'm wondering whether inside Poly/ML's compiler, there are such debugging functions which could print out the IR tree as well as the generated op code for an input ML program? These functions would help me a lot to test my understanding on Poly's IR data structure and code generation. ?Thank you very much!
Yue, There are switches in the PolyML.Compiler structure that will print out various stages of the compilation process when compiling something. Probably the most useful for you would be PolyML.Compiler.codetree := true; which will cause the compiler to print out the code-tree. ?You may also find "codetreeAfterOpt" (i.e. code-tree after it has been through the optimiser) and "assemblyCode" (the machine code generated by the final code-generator) useful as well.
? This works and I can see the printed code tree now. I will have more questions later when I tried more examples.
Many thanks!!
Yue
Dear Yue, You've obviously made quite a lot of progress.
Yue Li wrote:
- In the printed IR of a program, seems the print out has two
sections, for example:
2 * 3;
BLOCK(DECL #1{0 uses} = GLOBAL (FUN "run_call2(1)", LAMBDAINLINE( run_call2(1) CL=false CR=0 LEV=0 LOCALS=0 ARGS=G ARGLIVES= RES=G CLOS=() LOCAL(1,1) G $(INDIRECT(0, PARAM(0,1)) G, INDIRECT(1, PARAM(0,1)) G)){LAMBDA} ) (*GLOBAL*){early} G $(LIT <long> G); DECL #2{0 uses} = LOCAL(0,1); MUTUAL(); RECCONSTR(LOCAL(0,2)) ) BLOCK(DECL #1{0 uses} = GLOBAL (FUN "run_call2(1)", LAMBDAINLINE( run_call2(1) CL=false CR=0 LEV=0 LOCALS=0 ARGS=G ARGLIVES= RES=G CLOS=() LOCAL(1,1) G $(INDIRECT(0, PARAM(0,1)) G, INDIRECT(1, PARAM(0,1)) G)){LAMBDA} ) (*GLOBAL*){early} G $(LIT <long> G); DECL #2{0 uses} = LOCAL(0,1); MUTUAL(); RECCONSTR(LOCAL(0,2)) ) POLY_SYS_amul{early} G $(LIT2 G, LIT3 G)
I've had to go back to the code to try to understand what's going on here. It is actually printing the tree twice and that's a mistake. I added code to print the tree in the CODETREE functor, I think because in a very few cases it wasn't being printed, and omitted to remove the original printing code. I'll fix that.
The first section contains two same blocks, and always the block is duplicated in the first section for every input ML program. The second section contains an expression. It seems that the second expression is included in the blocks of the first section, and I'm a little bit confused here, so why the first section duplicates the blocks, and why the expression
POLY_SYS_amul{early} G $(LIT2 G, LIT3 G)
is separately printed out?
This is actually the output of the first phase of processing of the generated code-tree. In this case the original code contained some inline functions which have been stripped out leaving this code. It will actually be code-generated and evaluated by the compiler to reduce it to a constant. That's not going to provide any saving in this particular case since it's going to be evaluated only once but it may well do if this occurred inside a more complex function.
- TAGTEST(x, y, z) is used in several different places such as
generation of the boolean constants true and false, or testing whether a list is empty, but I still couldn't find documentation of TagTest from the source code, and I'm wondering what is the semantics of TAGTEST?
TAGTEST is really just an equality operation. It occurs primarily with datatypes but that does include the bool type which is essentially datatype bool = false | true TAGTEST(c1, c2, exp) is essentially the same as "c1 = exp". c2 is the maximum value of the tag (i.e. one less than the number of tags since they're numbered from zero) and is used if a sequence of tests is converted into an indexed jump.
- When I printed the IR of a signature, say:
signature Set =
# sig # type element # type set # val empty : set # end; BLOCK(LIT0) BLOCK(LIT0)
I suppose here again BLOCK(LIT0) is duplicated, and I'm wondering why this signature is represented like this simple instead of using a tuple whose elements are the decls, and its internal representations?
Declaring a signature doesn't generate any code so it's putting in zero here as a place-holder. Try declaring a structure.
- I found some documentation about the members of LAMBDA, but still
couldn't figure out how CL, CR and LOCALS are determined. In all my testing cases, always CL=false, and CR=0. Also for LOCALS, I thought it indicates the times that local variables are used. For instance:
Here I don't quite understand why LOCALS in the first Block is always 0, and why the LOCALS below is 3.
There are some values that are only used in later phases of the code-generator. It's simpler to have a single datatype and printer for the code-tree for all the phases and have the early phases just set the unused values to zero. CL, CR, LEV, LOCALS, CLOS and ARGLIVES are all of this sort. ARGS and RES are set in the initial phase. ARGS defines the the number and type of the arguments: F for Floating point and G for General (i.e. everything else) and RES the type of the result, again either F or G. ML functions are all expected to have precisely one argument and one result but the front end generates LAMBDAs that take more arguments for curried functions.
David
Dear David,
On Thu, Sep 2, 2010 at 6:20 AM, David Matthews David.Matthews@prolingua.co.uk wrote:
Dear Yue, You've obviously made quite a lot of progress.
Thanks! It was a pleasant experience to read the Poly/ML's compiler code.
Yue Li wrote:
- In the printed IR of a program, seems the print out has two
sections, for example:
2 * 3;
BLOCK(DECL #1{0 uses} = ?GLOBAL (FUN "run_call2(1)", ? ? ?LAMBDAINLINE( ? ? ? run_call2(1) ? ? ? CL=false CR=0 LEV=0 LOCALS=0 ? ? ? ARGS=G ? ? ? ARGLIVES= ? ? ? RES=G CLOS=() ? ? ? LOCAL(1,1) G $(INDIRECT(0, PARAM(0,1)) G, INDIRECT(1, PARAM(0,1)) G)){LAMBDA} ? ? ?) (*GLOBAL*){early} G $(LIT <long> G); ?DECL #2{0 uses} = LOCAL(0,1); ?MUTUAL(); ?RECCONSTR(LOCAL(0,2)) ?) BLOCK(DECL #1{0 uses} = ?GLOBAL (FUN "run_call2(1)", ? ? ?LAMBDAINLINE( ? ? ? run_call2(1) ? ? ? CL=false CR=0 LEV=0 LOCALS=0 ? ? ? ARGS=G ? ? ? ARGLIVES= ? ? ? RES=G CLOS=() ? ? ? LOCAL(1,1) G $(INDIRECT(0, PARAM(0,1)) G, INDIRECT(1, PARAM(0,1)) G)){LAMBDA} ? ? ?) (*GLOBAL*){early} G $(LIT <long> G); ?DECL #2{0 uses} = LOCAL(0,1); ?MUTUAL(); ?RECCONSTR(LOCAL(0,2)) ?) POLY_SYS_amul{early} G $(LIT2 G, LIT3 G)
I've had to go back to the code to try to understand what's going on here. ?It is actually printing the tree twice and that's a mistake. ?I added code to print the tree in the CODETREE functor, I think because in a very few cases it wasn't being printed, and omitted to remove the original printing code. ?I'll fix that.
OK.
The first section contains two same blocks, and always the block is duplicated in the first section for every input ML program. The second section contains an expression. It seems that the second expression is included in the blocks of the first section, and I'm a little bit confused here, so why the first section duplicates the blocks, and why the expression
POLY_SYS_amul{early} G $(LIT2 G, LIT3 G)
is separately printed out?
This is actually the output of the first phase of processing of the generated code-tree. ?In this case the original code contained some inline functions which have been stripped out leaving this code. ?It will actually be code-generated and evaluated by the compiler to reduce it to a constant. ?That's not going to provide any saving in this particular case since it's going to be evaluated only once but it may well do if this occurred inside a more complex function.
I see, no wonder such optimized expression is generated for some program, and is not generated for some other of my examples.
- TAGTEST(x, y, z) is used in several different places such as
generation of the boolean constants true and false, or testing whether a list is empty, but I still couldn't find documentation of TagTest from the source code, and I'm wondering what is the semantics of TAGTEST?
TAGTEST is really just an equality operation. ?It occurs primarily with datatypes but that does include the bool type which is essentially datatype bool = false | true TAGTEST(c1, c2, exp) ?is essentially the same as "c1 = exp". ?c2 is the
I see.
maximum value of the tag (i.e. one less than the number of tags since they're numbered from zero) and is used if a sequence of tests is converted into an indexed jump.
Ok, no problem.
- When I printed the IR of a signature, say:
signature Set =
# sig # ? type element # ? type set # ? val empty : set # end; BLOCK(LIT0) BLOCK(LIT0)
I suppose here again BLOCK(LIT0) is duplicated, and I'm wondering why this signature is represented like this simple instead of using a tuple whose elements are the decls, and its internal representations?
Declaring a signature doesn't generate any code so it's putting in zero here as a place-holder.
Are signatures preserved only until type checking phase before the code generation phase?
Try declaring a structure.
Yes, and I got a tuple containing IR for each function/value definitions of the structure.
- I found some documentation about the members of LAMBDA, but still
couldn't figure out how CL, CR and LOCALS are determined. In all my testing cases, always CL=false, and CR=0. Also for LOCALS, I thought it indicates the times that local variables are used. For instance:
Here I don't quite understand why LOCALS in the first Block is always 0, and why the LOCALS below is 3.
There are some values that are only used in later phases of the code-generator. ?It's simpler to have a single datatype and printer for the code-tree for all the phases and have the early phases just set the unused values to zero. ?CL, CR, LEV, LOCALS, CLOS and ARGLIVES are all of this sort.
I see, seems these flags are set with initial values in the generated blocks (the duplicated ones), and are computed in the stripped version later.
?ARGS and RES are set in the initial phase. ?ARGS defines the the number and type of the arguments: F for Floating point and G for General (i.e. everything else) and RES the type of the result, again either F or G. ?ML functions are all expected to have precisely one argument and one result but the front end generates LAMBDAs that take more arguments for curried functions.
Could you introduce a little bit on how CR CL and LOCALS are determined in the later phase of code generation? Thanks again!
Best,
Yue
David
Yue Li wrote:
Are signatures preserved only until type checking phase before the code generation phase?
Any declaration will involve a name, a description of some sort and some code. The description might be the type of a value or in the case of a structure or signature a data-structure representing the signature. The code may involve evaluating some expression or, in the case of signature, infix and simple type bindings it may be zero. The resulting of compiling anything is a unit->unit function which when called executes the code and also side-effects the name-space to put the declared value into the name-space.
Could you introduce a little bit on how CR CL and LOCALS are determined in the later phase of code generation? Thanks again!
LOCALS is used as a high-water mark to indicate the maximum number of local bindings in the function. Not all the bindings may be present because often they are created as part of the inline function expansion process and then removed if they are not actually referenced.
CL is false if the function has non-local references but does not require a closure. This may happen if it is declared as local to another function but is only ever called and not, for example, returned as a result. Creating a closure requires heap allocation so it's better if it can be avoided.
CR has to do with when the register that contains the address of the closure is no longer required and can be reused.
All these are computed within later phases of the code-generator.
Regards, David
On Fri, Sep 3, 2010 at 12:33 PM, David Matthews David.Matthews@prolingua.co.uk wrote:
Yue Li wrote:
? Are signatures preserved only until type checking phase before the code generation phase?
Any declaration will involve a name, a description of some sort and some code. ?The description might be the type of a value or in the case of a structure or signature a data-structure representing the signature. ?The code may involve evaluating some expression or, in the case of signature, infix and simple type bindings it may be zero. ?The resulting of compiling anything is a unit->unit function which when called executes the code and also side-effects the name-space to put the declared value into the name-space.
I see, I think now I fully understand that the generated IR of a signature contains only zero because of no evaluation.
?Could you introduce a little bit on how CR CL and LOCALS are determined in the later phase of code generation? Thanks again!
LOCALS is used as a high-water mark to indicate the maximum number of local bindings in the function. ?Not all the bindings may be present because often they are created as part of the inline function expansion process and then removed if they are not actually referenced.
Ok. No wonder for some function definition whose body involves constant expressions, the value of LOCALS is not what I expect due to this kind of optimization, which removes local references.
CL is false if the function has non-local references but does not require a closure. ?This may happen if it is declared as local to another function but is only ever called and not, for example, returned as a result. ?Creating a closure requires heap allocation so it's better if it can be avoided.
CR has to do with when the register that contains the address of the closure is no longer required and can be reused.
All these are computed within later phases of the code-generator.
I'm much clearer now, many thanks!!
Best,
Yue
-
David.Matthews＠prolingua.co.uk -
xyly781＠gmail.com