[Projects] XRM 34: Use static const variables in constant propagation.

https://svn.lrde.epita.fr/svn/xrm/trunk Index: ChangeLog from SIGOURE Benoit &lt;sigoure.benoit(a)lrde.epita.fr&gt; Use static const variables in constant propagation. * src/sig/Makefile.am: Patch a possible dependency problem. * src/str/xrm-front.str: Change some comments. * src/str/xrm-to-prism.str: Collect static const variables. * src/str/prism-desugar.str: Use the known values of static const variables in constant propagation if possible. * TODO: Update things done. Add a question about PRISM's behavior. TODO | 13 +++++++++---- src/sig/Makefile.am | 8 +++++--- src/str/prism-desugar.str | 21 +++++++++++++++++++-- src/str/xrm-front.str | 6 +++--- src/str/xrm-to-prism.str | 45 +++++++++++++++++++++++++++++++++++++++++---- 5 files changed, 77 insertions(+), 16 deletions(-) Index: src/sig/Makefile.am --- src/sig/Makefile.am (revision 33) +++ src/sig/Makefile.am (working copy) @@ -5,7 +5,7 @@ ## Mail &lt;sigoure.benoit(a)lrde.epita.fr&gt; ## ## Started on Mon May 8 18:38:32 2006 SIGOURE Benoit -## Last update Tue May 9 20:39:39 2006 SIGOURE Benoit +## Last update Thu May 25 23:41:55 2006 SIGOURE Benoit ## include $(top_srcdir)/config/Transformers.mk @@ -18,8 +18,10 @@ SDF2RTG_FLAGS = --main $* -PRISM.def: +PRISM.def: $(top_builddir)/src/syn/prism/PRISM.def + rm -f $@ $(LN_S) $(top_builddir)/src/syn/prism/$@ $@ -XRM.def: +XRM.def: $(top_builddir)/src/syn/xrm/XRM.def + rm -f $@ $(LN_S) $(top_builddir)/src/syn/xrm/$@ $@ Index: src/str/xrm-front.str --- src/str/xrm-front.str (revision 33) +++ src/str/xrm-front.str (working copy) @@ -36,7 +36,7 @@ end end - // pipeline of transformations performed by xrm-front + /** pipeline of transformations performed by xrm-front */ xrm-front-pipeline = dbg(|"xrm-front-pipeline starting") ; xrm-to-prism @@ -47,14 +47,14 @@ end ; id // FIXME: add more transformations here - // list of available options for xrm-front + /** list of available options for xrm-front */ xrm-front-options = pp-aterm-option + add-pos-option + keep-attributes-option + desugar-option - // check the options are consistent + /** checks the options are consistent */ check-options = if <get-config> "-b" then // if we're asked for binary output, don't bother with pretty printing Index: src/str/xrm-to-prism.str --- src/str/xrm-to-prism.str (revision 33) +++ src/str/xrm-to-prism.str (working copy) @@ -1,6 +1,19 @@ /* ** This sub-module does the real work of the front-end. It transforms the ** program into a valid PRISM AST. +** +** Dynamic rules inventory: +** - DeclarationList: used by the strategy reorder-module-contents to +** store all the declarations within a given module. This way declarations +** can be grouped together in the module (as required by the PRISM grammar) +** - CommandList: used by the strategy reorder-module-contents to +** store all the commands within a given module. This way commands can +** be grouped together in the module (as required by the PRISM grammar) +** - ExpandStaticConsts: created by the strategy collect-static-const-decl +** and used by prism-desugar for constant propagation. Maps an identifier +** with a value and an annotated type. Only constants with a static value +** provided will be put here (constants can have their value defined in +** init blocks and chosen at random at runtime). */ module xrm-to-prism imports @@ -17,11 +30,15 @@ /* remove XRM sugar, normalize some nodes */ innermost(xrm-to-prism-desugar) - /* Desugar array declarations + /* Two things in one traversal: + * 1/ Desugar array declarations * eg: x[4][5] is transformed into two nested meta for loops * We can't do this in xrm-to-prism-desugar because the innermost - * traversal is bottomup and won't recurse into generated code */ - ; topdown(try(array-decl-desugar)) + * traversal is bottomup and won't recurse into generated code + * 2/ Collect static const variables + * Two goals: expand them if needed, look for variable name conflicts. + */ + ; topdown(try(array-decl-desugar); try(collect-static-const-decl)) /* Check that meta vars are always defined in the current scope when used * and that they are not redefined twice in the same scope */ @@ -48,7 +65,7 @@ xrm-to-prism-desugar: |[ e1 << e2 ]| -> |[ e1 * func(pow, 2, e2) ]| - // if the step is not specified, it is implicitely set to 1 + /** if the step is not specified, it is implicitly set to 1 */ xrm-to-prism-desugar: MetaFor(identifier, from, to, body) -> MetaFor(identifier, from, to, Int("1"), body) @@ -58,6 +75,26 @@ //|[ if e then s* end ]| -> |[ if e then s* else end ]| MetaIf(e, m*) -> MetaIf(e, m*, []) +signature constructors + Type : String -> Type + +strategies + + collect-static-const-decl = + ?ConstInt(idf, value) + ; where(!value{Type("int")} => v) + ; rules(ExpandStaticConsts: idf -> v) + + collect-static-const-decl = + ?ConstDouble(idf, value) + ; where(!value{Type("double")} => v) + ; rules(ExpandStaticConsts: idf -> v) + + collect-static-const-decl = + ?ConstBool(idf, value) + ; where(!value{Type("bool")} => v) + ; rules(ExpandStaticConsts: idf -> v) + strategies /** Index: src/str/prism-desugar.str --- src/str/prism-desugar.str (revision 33) +++ src/str/prism-desugar.str (working copy) @@ -9,13 +9,14 @@ ** 1. First convert all literal ints to doubles. This makes the ** simplifications easier to write since there is less cases to ** address (eg: int + int, int + double, double + int, - ** double + double etc.). + ** double + double etc.). This first pass works in a slightly + ** special way, see prism-desugar-first-pass for more info. ** 2. Desugar the AST ** 3. Convert the doubles which are round numbers back to ints. ** Simplify doubles (round them up and remove trailing zeros) */ prism-desugar = - topdown(try(IntToDouble)) + prism-desugar-first-pass ; innermost( RemoveUnconditionnalUpdates <+ AddZero <+ MulOne <+ MulZero <+ DivOne <+ catch-div-by-zero @@ -26,6 +27,22 @@ ) ; topdown(try(SimplifyDoubles <+ TruncateDouble)) + /** + ** Main goal: Transform all Int(_) -> Double(_) + ** In this first pass we also want to expand static consts. However, we + ** must be careful as to where these expansions occur. For instance, say + ** that N=10 (we know it thanks to the DR ExpandStaticConsts). If we are + ** on the node where N is declared (that is: |[ const int N = 10; ]|) we + ** should NOT expand `N' here. Otherwise we'll end up with + ** |[ const int 10 = 10; ]|. + */ + prism-desugar-first-pass = + ConstInt(id, prism-desugar) + <+ ConstDouble(id, prism-desugar) + <+ ConstBool(id, prism-desugar) + <+ ?Int(_); IntToDouble + <+ all(try(ExpandStaticConsts); prism-desugar-first-pass) + rules IntToDouble: Int(i) -> Double(i) Index: TODO --- TODO (revision 33) +++ TODO (working copy) @@ -17,6 +17,11 @@ * Add more tests. Add tests which actually do check that the generated code is correct (which is not done ATM). + * How are handled mutually recursive static constant variables in PRISM? + eg: const int x = y; + const int y = x; + Is it even possible to define a static const variable from another one? + ## ---------- ## ## Extensions ## ## ---------- ## @@ -91,10 +96,6 @@ x = 1..5,7,10..13 ==> (x>=1 & x<=5) | (x=7) | (x>=10 & x<=13) - * Evaluate constant calls to built-in functions, eg - func(min, 4, 5) - ==> 4 - * Expand formulas, eg formula lfree = p2=0..4,6,10; // ... @@ -159,3 +160,7 @@ [] x[0]=0 -> ... => ... <=> end endmodule => [] x_0=0 -> ... <=> [] x_0=0 -> ... => endmodule <=> endmodule + + * Evaluate constant calls to built-in functions, eg + func(min, 4, 5) + ==> 4