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)
   6
   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.
  11
  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.
  16
  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 ==========================================================================";
  20
  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 >:
  31
  32   C:" Transformations to use: (not sure about TR_Collapse_Action_System!) ";
  33
  34   wanted := @Make_Set(<
  35
  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
  65
  66   >);
  67
  68   C:" Transformations which only make sense when applied to the whole program: ";
  69
  70   whole := @Make_Set(< TR_Constant_Propagation, TR_Simplify, TR_Delete_All_Redundant >);
  71
  72   C:" Transformations which are potentially useful preparation for ";
  73   C:" another transformation: ";
  74
  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   >);
  81
  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   >);
  87
  88   IF minimal_output = 0 THEN PRINT("Found ", LENGTH(wanted), " transformations.") FI;
  89
  90   Argv := TAIL(Argv);
  91   IF Argv = < > THEN Argv := <prog> FI;
  92
  93   FOR prog IN Argv DO
  94
  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");
 100
 101     IF use_temp_folder = 1 THEN
 102        C:"other versions should go to the temp folder";
 103
 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;
 112
 113     @WL("Hill Climbing");
 114     @WL("version:" ++ hc_version_string);
 115     @WL("Input file: " ++ prog);
 116     @WL("Output file: " ++ result);
 117
 118     @New_Program(@Parse_File(prog, T_Statements));
 119
 120
 121     @WL("Found " ++ @String(LENGTH(wanted)) ++ " transformations.");
 122     @WL("");
 123
 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;
 140
 141     @Checkpoint(result);
 142     @WL("transformations tried:" ++ @String(total_transformations_tried));
 143     PRINT("total transformations tried:", total_transformations_tried);
 144     @WL("");
 145     @End_Write();
 146
 147     SKIP OD ENDVAR .;
 148
 149
 150 C:" Return TRUE if I1 is better than I2 according to the defined metrics ";
 151
 152 MW_BFUNCT @HC_Better?(I1, I2) == :
 153   SKIP;
 154   (@Struct_Metric(I1) < @Struct_Metric(I2)) .;
 155
 156
 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 .;
 174
 175
 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("") .;
 184
 185
 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 .;
 244
 245 MW_FUNCT @Last_Index(string, sep) ==
 246 VAR< last := SLENGTH(string) - 1 >:
 247
 248         WHILE last > 0 AND SUBSTR(string,last,1) <> sep DO
 249                 last := last - 1; OD;
 250
 251 (last) END;
 252
 253 C:" Call the main routine after all other routines have been defined: ";
 254
 255 @HC_Main;
 256
 257
 258 SKIP
 259
 260