gitweb on Svarog

projekti pod git sistemom za održavanje verzija -- projects under the git version control system
Hill Climbing automated transformation added to the repo
[mjc2wsl.git] / src-wsl / hill_climbing.wsl
1 C:"
2 ==========================================================================
3 Hill Climbing Automated Transformation Selection program
4 Copyright (C) 2018 Martin Ward (martin@gkc.org.uk)
5 Doni Pracner (doni.pracner@dmi.uns.ac.rs)
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or
10 (at your option) any later version.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
19 ==========================================================================";
21 MW_PROC @HC_Main() ==
22 VAR < trs := ARRAY(200, 0), i := 0, wanted := < >, whole := < >,
23 pre_trans := < >, tr := 0,
24 prog := "simple5.wsl", base := "", result := "",
25 count := 1000, done := 0, Argv := ARGV,
26 hc_version_string := "hc-18-jan-1",
27 log_failure := 1,
28 minimal_output := 1,
29 total_transformations_tried := 0, writeout_mod := 100,
30 temp_folder := "hc-temp-versions/", use_temp_folder := 1, last := 0 >:
32 C:" Transformations to use: (not sure about TR_Collapse_Action_System!) ";
34 wanted := @Make_Set(<
36 TR_Absorb_Left, TR_Absorb_Right,
37 TR_Add_Assertion, TR_Add_Left,
38 TR_Add_Loop_To_Action, TR_Align_Nested_Statements,
39 TR_Collapse_Action_System, TR_Combine_Wheres, TR_Constant_Propagation,
40 TR_D_Do_To_Floop, TR_Decrement_Statement, TR_Delete_All_Assertions,
41 TR_Delete_All_Skips, TR_Delete_Item,
42 TR_Delete_Redundant_Statement, TR_Delete_Unreachable_Code,
43 TR_Delete_What_Follows, TR_Double_To_Single_Loop,
44 TR_Else_If_To_Elsif, TR_Elsif_To_Else_If,
45 TR_Expand_And_Separate, TR_Expand_Call,
46 TR_Expand_Forward, TR_Floop_To_While,
47 TR_For_In_To_Reduce, TR_For_To_While, TR_Force_Double_To_Single_Loop,
48 TR_Fully_Absorb_Right, TR_Fully_Expand_Forward, TR_Increment_Statement,
49 TR_Insert_Assertion, TR_Join_All_Cases, TR_Join_Cases_Left,
50 TR_Join_Cases_Right, TR_Make_Loop, TR_Make_Reducible,
51 TR_Merge_Calls_In_Action, TR_Merge_Calls_In_System, TR_Merge_Cond_Right,
52 TR_Merge_Left, TR_Merge_Right, TR_Move_Comment_Left,
53 TR_Move_Comment_Right, TR_Move_Comments, TR_Move_To_Left,
54 TR_Move_To_Right, TR_Partially_Join_Cases, TR_Push_Pop,
55 TR_Recursion_To_Loop, TR_Reduce_Loop, TR_Reduce_Multiple_Loops,
56 TR_Remove_Dummy_Loop, TR_Remove_Redundant_Vars, TR_Reverse_Order,
57 TR_Roll_Loop, TR_Separate_Both, TR_Separate_Exit_Code, TR_Separate_Left,
58 TR_Separate_Right, TR_Simplify, TR_Simplify_Action_System,
59 TR_Simplify_If, TR_Simplify_Item, TR_Substitute_And_Delete,
60 TR_Take_Out_Left, TR_Take_Out_Of_Loop, TR_Take_Out_Right,
61 TR_Unroll_Loop, TR_Use_Assertion,
62 TR_Stack_To_Var, TR_Stack_To_Par,
63 TR_Proc_To_Funct, TR_Stack_To_Return, TR_Array_To_Vars,
64 TR_While_To_Abort, TR_While_To_Floop, TR_While_To_For_In, TR_While_To_Reduce
66 >);
68 C:" Transformations which only make sense when applied to the whole program: ";
70 whole := @Make_Set(< TR_Constant_Propagation, TR_Simplify, TR_Delete_All_Redundant >);
72 C:" Transformations which are potentially useful preparation for ";
73 C:" another transformation: ";
75 trans1 := @Make_Set(<
76 TR_Absorb_Left, TR_Absorb_Right, TR_Constant_Propagation,
77 TR_Make_Loop, TR_Move_To_Left, TR_Remove_Redundant_Vars,
78 TR_Separate_Both, TR_Separate_Right, TR_Substitute_And_Delete,
79 TR_While_To_Floop
80 >);
82 trans2 := @Make_Set(<
83 TR_Absorb_Left, TR_Absorb_Right, TR_Constant_Propagation,
84 TR_Delete_Redundant_Statement,
85 TR_Remove_Redundant_Vars, TR_Substitute_And_Delete
86 >);
88 IF minimal_output = 0 THEN PRINT("Found ", LENGTH(wanted), " transformations.") FI;
90 Argv := TAIL(Argv);
91 IF Argv = < > THEN Argv := <prog> FI;
93 FOR prog IN Argv DO
95 base := prog;
96 IF SLENGTH(base) > 4 AND SUBSTR(base, SLENGTH(base) - 4, 4) = ".wsl"
97 THEN base := SUBSTR(base, 0, SLENGTH(base) - 4) FI;
98 result := base ++ "_tr.wsl";
99 @Write_To(base ++ ".log");
101 IF use_temp_folder = 1 THEN
102 C:"other versions should go to the temp folder";
104 C:"check for folders in path, set temp folder";
105 last := @Last_Index(base,"/");
106 IF last > 0 THEN
107 temp_folder := SUBSTR(base,0,last+1) ++ temp_folder;
108 base := temp_folder ++ SUBSTR(base,last+1);
109 ELSE
110 base := temp_folder ++ base; FI;
111 @Create_Folder(temp_folder) FI;
113 @WL("Hill Climbing");
114 @WL("version:" ++ hc_version_string);
115 @WL("Input file: " ++ prog);
116 @WL("Output file: " ++ result);
118 @New_Program(@Parse_File(prog, T_Statements));
121 @WL("Found " ++ @String(LENGTH(wanted)) ++ " transformations.");
122 @WL("");
124 done := 0;
125 WHILE done >= 0 DO
126 WHILE done >= 0 DO
127 PRINT("----------------- Level 1 ---------------");
128 @WL ("----------------- Level 1 ---------------");
129 WHILE done >= 0 DO
130 @HC_Test_All(1, whole, @Program, < > VAR done, count) OD;
131 done := 0;
132 PRINT("----------------- Level 2 ---------------");
133 @WL ("----------------- Level 2 ---------------");
134 @HC_Test_All(2, whole, @Program, < > VAR done, count) OD;
135 done := 0;
136 VAR < trans1 := wanted, trans2 := wanted >:
137 PRINT("----------------- Level 3 ---------------");
138 @WL ("----------------- Level 3 ---------------");
139 @HC_Test_All(2, whole, @Program, < > VAR done, count) ENDVAR OD;
141 @Checkpoint(result);
142 @WL("transformations tried:" ++ @String(total_transformations_tried));
143 PRINT("total transformations tried:", total_transformations_tried);
144 @WL("");
145 @End_Write();
147 SKIP OD ENDVAR .;
150 C:" Return TRUE if I1 is better than I2 according to the defined metrics ";
152 MW_BFUNCT @HC_Better?(I1, I2) == :
153 SKIP;
154 (@Struct_Metric(I1) < @Struct_Metric(I2)) .;
157 MW_PROC @HC_Checkpoint(tr, prev VAR count) ==
158 C:" Keep this version ";
159 count := count + 1;
160 @Checkpoint(base ++ "-" ++ @String(count) ++ ".wsl");
161 IF minimal_output =0
162 THEN PRINT(TRs_Name[tr], " at ", posn) FI;
163 @WS(@String(count) ++ ": Success:");
164 VAR < L := REVERSE(<<tr, posn>> ++ prev) >:
165 WHILE NOT EMPTY?(L) DO
166 pair := HEAD(L); L := TAIL(L);
167 @WS(TRs_Name[pair[1]] ++ ": at <");
168 @WL(@Join(",", MAP("@String", pair[2])) ++ ">");
169 IF NOT EMPTY?(L) THEN @WS(" +: Success:") FI OD ENDVAR;
170 IF minimal_output = 0 THEN
171 @HC_Metrics("old: ", old);
172 @HC_Metrics("orig: ", orig);
173 @HC_Metrics("new: ", @Program) FI .;
176 MW_PROC @HC_Metrics(str, I) ==
177 PRINFLUSH(str);
178 FOR n IN < @Struct_Metric(I),
179 @Spec_Type_Count(T_Action, I), @Spec_Type_Count(T_Call, I),
180 @Spec_Type_Count(T_A_Proc_Call, I), @McCabe(I),
181 @Stat_Count(I), @Gen_Type_Count(T_Expression, I) > DO
182 PRINFLUSH(n, " ") OD;
183 PRINT("") .;
186 MW_PROC @HC_Test_All(depth, whole, orig, prev VAR done, count) ==
187 VAR < tr := 0, trs := < >, old := @Program, posn := < > >:
188 @Goto(< >);
189 IF depth = 1 AND EMPTY?(prev)
190 THEN trs := wanted
191 ELSIF depth = 2 AND EMPTY?(prev)
192 THEN trs := trans1
193 ELSIF depth = 1 AND NOT EMPTY?(prev)
194 THEN trs := trans2
195 ELSE PRINT("depth = ", depth, " prev = ", LENGTH(prev));
196 ERROR("-- not yet implemented") FI;
197 IF EMPTY?(trs) THEN ERROR("Empty transformation list!") FI;
198 tr := HEAD(trs);
199 DO IF FALSE
200 THEN PRINT(depth, " testing ", TRs_Name[tr], " at ", @Posn) FI;
201 IF tr IN whole AND @Up?
202 THEN SKIP
203 ELSIF @GT(@I) IN <T_Expression, T_Condition, T_Lvalue,
204 T_Expressions, T_Lvalues>
205 THEN SKIP
206 ELSIF @Trans?(tr)
207 THEN posn := @Posn;
208 @Trans(tr, "");
209 total_transformations_tried := total_transformations_tried + 1;
210 IF total_transformations_tried MOD writeout_mod = 0
211 THEN PRINT("*** transformations tried:", total_transformations_tried) FI;
212 IF @ST(@I) = T_Assignment AND @Size(@I) > 1
213 THEN C:" don't generate parallel assignments "
214 ELSIF @HC_Better?(@Program, orig)
215 THEN done := tr;
216 @HC_Checkpoint(tr, prev VAR count);
217 EXIT(1)
218 ELSIF depth > 1 AND NOT @Equal?(@Program, orig)
219 THEN IF minimal_output = 0 THEN PRINT("== Sub-test after ", TRs_Name[tr], " at ", posn) FI;
220 @HC_Test_All(depth - 1, whole, orig, <<tr, posn>> ++ prev
221 VAR done, count);
222 IF done > 0
223 THEN EXIT(1) FI FI;
224 IF log_failure = 1
225 THEN @WL("- Depth:" ++ @String(depth) ++ " Tried:" ++ TRs_Name[tr]) FI;
226 C:" Revert program ";
227 @New_Program(old);
228 @Goto(posn) FI;
229 C:" Move to new position. ";
230 C:" Do not descend into these types: ";
231 IF @Down? AND @GT(@I) NOTIN <T_Expression, T_Condition, T_Lvalue,
232 T_Expressions, T_Lvalues>
233 THEN @Down
234 ELSIF @Right?
235 THEN @Right
236 ELSE WHILE @Up? AND NOT @Right? DO @Up OD;
237 IF @Right?
238 THEN @Right
239 ELSE C:" Next transformation ";
240 trs := TAIL(trs);
241 IF EMPTY?(trs) THEN done := -1; EXIT(1) FI;
242 tr := HEAD(trs);
243 @Goto(< >) FI FI OD ENDVAR .;
245 MW_FUNCT @Last_Index(string, sep) ==
246 VAR< last := SLENGTH(string) - 1 >:
248 WHILE last > 0 AND SUBSTR(string,last,1) <> sep DO
249 last := last - 1; OD;
251 (last) END;
253 C:" Call the main routine after all other routines have been defined: ";
255 @HC_Main;
258 SKIP
Svarog.pmf.uns.ac.rs/gitweb maintanance Doni Pracner