prop-src/rwgen3.pcc.old

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  This file implements the dynamic tree parser algorithm, which is
   4 //  used to parse a tree grammar with associated reduction cost functions.
   5 //
   6 ///////////////////////////////////////////////////////////////////////////////
   7 #include <iostream.h>
   8 #include "funmap.ph"
   9 #include "ir.ph"
  10 #include "ast.ph"
  11 #include "matchcom.ph"
  12 #include "type.h"
  13 #include "hashtab.h"
  14 #include "rwgen.h"
  15 #include "options.h"
  16 #include "list.h"
  17
  18 extern Id redex_name(Ty);
  19
  20 ///////////////////////////////////////////////////////////////////////////////
  21 //
  22 //  Top level method to generate a dynamic tree parser.
  23 //  We use a simple dynamic programming algorithm.
  24 //
  25 ///////////////////////////////////////////////////////////////////////////////
  26 void RewritingCompiler::gen_dynamic_rewriter (FunctorMap& F)
  27 {
  28    generate_state_record(F);        // generate the state record definition
  29    generate_accept_rules_tables(F); // generate the accept rule tables
  30    generate_closures(F);            // generate the closure routines
  31    generate_dynamic_labelers(F);    // generate the labeler functions
  32    generate_reducers(F);            // generate the reducer functions
  33    // Generate report
  34    if (PropOptions::generate_report) F.print_report(open_logfile());
  35 }
  36
  37 ///////////////////////////////////////////////////////////////////////////////
  38 //
  39 //  Method to generate the state record.
  40 //
  41 ///////////////////////////////////////////////////////////////////////////////
  42 void RewritingCompiler::generate_state_record (FunctorMap& F)
  43 {  pr("\n"
  44       "%^%/"
  45       "%^// State record for rewrite class %s"
  46       "%^%/"
  47       "%^struct %s_StateRec {\n"
  48       "%^   TreeTables::Cost cost[%i]; // cost for each non-terminal"
  49       "%^   struct { // accept rule number",
  50       F.class_name, F.class_name, F.nonterm_map.size()+1
  51      );
  52
  53    foreach_entry (e, F.nonterm_rules_bits)
  54    {  Id  lhs  = Id(e->k);
  55       int bits = int(e->v);
  56       pr("%^      unsigned int _%S : %i;", lhs, bits);
  57    }
  58
  59    pr("%^   } rule;"
  60       "%^};\n\n");
  61 }
  62
  63 ///////////////////////////////////////////////////////////////////////////////
  64 //
  65 //  Method to generate the accept rule tables.
  66 //
  67 ///////////////////////////////////////////////////////////////////////////////
  68 void RewritingCompiler::generate_accept_rules_tables (FunctorMap& F)
  69 {  pr("%^%/"
  70       "%^// Accept rules tables for rewrite class %s"
  71       "%^%/",
  72       F.class_name
  73      );
  74
  75    foreach_entry (e, F.nonterm_rules)
  76    {  Id         lhs   = Id(e->k);
  77       MatchRules rules = MatchRules(e->v);
  78       int max_rule     = 0;
  79
  80       match while (rules)
  81       {  #[ one ... rest ]:
  82          {  if (max_rule < one->rule_number) max_rule = one->rule_number;
  83             rules = rest;
  84          }
  85       }
  86
  87       Id storage_class = max_rule < 128 ? "char" : "short";
  88
  89       pr ("%^const %s %s_%S_accept[] = { -1, ",
  90           storage_class, F.class_name, lhs);
  91
  92       rules = MatchRules(e->v);
  93       match while (rules)
  94       {  #[ one ... rest ]:
  95          {  pr ("%i%s", one->rule_number, (rest != #[] ? ", " : ""));
  96             rules = rest;
  97          }
  98       }
  99       pr (" };\n\n");
 100    }
 101 }
 102
 103 ///////////////////////////////////////////////////////////////////////////////
 104 //
 105 //  Method to generate the closure routines for each non-terminal
 106 //  which appears the rhs of a chain rule.
 107 //
 108 ///////////////////////////////////////////////////////////////////////////////
 109 void RewritingCompiler::generate_closures (FunctorMap& F)
 110 {  pr("%^%/"
 111       "%^// Closure methods for rewrite class %s"
 112       "%^%/",
 113       F.class_name
 114      );
 115
 116    // Generate the headers first
 117    {  foreach_entry (e, F.chain_rules)
 118       {  Id         rhs   = Id(e->k);
 119          MatchRules rules = MatchRules(e->v);
 120          Ty         ty    = rules->#1->ty; // type of states.
 121          pr ("%^static void %s_%S_closure(%t,int cost);\n",
 122              F.class_name, rhs, ty, "redex"
 123             );
 124       }
 125    }
 126
 127    pr ("\n");
 128
 129    // Then generate the definitions.
 130    {  foreach_entry (e, F.chain_rules)
 131       {  Id         rhs   = Id(e->k);
 132          MatchRules rules = MatchRules(e->v);
 133          gen_closure(F,rhs,rules);
 134       }
 135    }
 136 }
 137
 138 ///////////////////////////////////////////////////////////////////////////////
 139 //
 140 //  Method to generate the closure routine for one non-terminal.
 141 //
 142 ///////////////////////////////////////////////////////////////////////////////
 143 void RewritingCompiler::gen_closure (FunctorMap& F, Id rhs, MatchRules rules)
 144 {  Ty ty = rules->#1->ty; // type of states.
 145    pr ("%^static void %s_%S_closure(%t,int cost)\n"
 146        "%^{%+"
 147        "%^%s_StateRec * _state_rec = (%s_StateRec *)(%s->get_state_rec());",
 148         F.class_name, rhs, ty, "redex", F.class_name,
 149         F.class_name, redex_name(ty)
 150       );
 151    int rule_no = 1;
 152    rules = rev(rules);
 153    match while (rules)
 154    {  #[ MATCHrule(lhs,pat,guard,cost,_) ... rest ]:
 155       {  Exp cost_exp;
 156          match (cost)
 157          {  NOcost:        { cost_exp = LITERALexp(INTlit(0)); }
 158          |  INTcost i:     { cost_exp = LITERALexp(INTlit(i)); }
 159          |  EXPcost (e,_):
 160             {  // Avoid recomputation of cost
 161                Id v = vars.new_label();
 162                pr ("%^const int %s = %e;", v, e);
 163                cost_exp = IDexp(v);
 164             }
 165          }
 166          int nonterm_number = int(F.var_map[lhs]);
 167
 168          if (nonterm_number > 0)
 169          {  pr ("%^if (cost + %e < _state_rec->cost[%i])"
 170                 "%^{  _state_rec->cost[%i] = cost + %e;"
 171                 "%^   _state_rec->rule._%S = %i;",
 172                 cost_exp, nonterm_number, nonterm_number, cost_exp, lhs, rule_no
 173                );
 174
 175             // Chain rules
 176             if (F.chain_rules.contains(lhs))
 177             {  pr ("%^   %s_%S_closure(redex,cost + %e);",
 178                    F.class_name, lhs, cost_exp);
 179             }
 180
 181             pr ("%^}");
 182          }
 183          rule_no++;
 184          rules = rest;
 185       }
 186    }
 187
 188    pr ("%-%^}\n\n");
 189 }
 190
 191 ///////////////////////////////////////////////////////////////////////////////
 192 //
 193 //  Method to generate the dynamic labelers
 194 //
 195 ///////////////////////////////////////////////////////////////////////////////
 196 void RewritingCompiler::generate_dynamic_labelers (FunctorMap& F)
 197 {
 198    ////////////////////////////////////////////////////////////////////////////
 199    //  Generate a dynamic labeler for each datatype
 200    ////////////////////////////////////////////////////////////////////////////
 201    foreach_entry (e, F.type_map)
 202    {  Ty ty = Ty(F.type_map.key(e));
 203       debug_msg("[Rewrite class %s: generating dynamic labeler for datatype %T\n",
 204                 F.class_name, ty);
 205       gen_dynamic_datatype_labeler(F, ty);
 206    }
 207 }
 208
 209 ///////////////////////////////////////////////////////////////////////////////
 210 //
 211 //  Method to generate a labeler routine for one datatype.
 212 //
 213 ///////////////////////////////////////////////////////////////////////////////
 214 void RewritingCompiler::gen_dynamic_datatype_labeler(FunctorMap& F, Ty ty)
 215 {
 216    ///////////////////////////////////////////////////////////////////////////
 217    // Generate the protocol of this labeler routine
 218    ///////////////////////////////////////////////////////////////////////////
 219    pr ("%^void %s::labeler (%t)"
 220        "%^{%+"
 221           "%^int cost;",
 222        F.class_name, ty, "redex");
 223
 224    ///////////////////////////////////////////////////////////////////////////
 225    // Name of the redex inside this routine.
 226    ///////////////////////////////////////////////////////////////////////////
 227    Id redex = redex_name(ty);
 228
 229    ///////////////////////////////////////////////////////////////////////////
 230    //
 231    // Allocate and initialize a state record.
 232    //
 233    ///////////////////////////////////////////////////////////////////////////
 234    pr ("%^%s_StateRec * _state_rec = (%s_StateRec *)mem[sizeof(%s_StateRec)];"
 235        "%^%s->set_state_rec(_state_rec);"
 236        "%^_state_rec->cost[0] = 0;",
 237        F.class_name, F.class_name, F.class_name, redex);
 238    for (int i = 1; i <= F.nonterm_map.size(); i++)
 239    {  pr("%^_state_rec->cost[%i] = ", i);
 240    }
 241    pr ("%i;\n", TreeTables::infinite_cost);
 242
 243    ///////////////////////////////////////////////////////////////////////////
 244    // Generate code for bottomup traversal on the datatype
 245    ///////////////////////////////////////////////////////////////////////////
 246    gen_dynamic_traversals(F, ty);
 247
 248    ///////////////////////////////////////////////////////////////////////////
 249    // Update the state record.
 250    ///////////////////////////////////////////////////////////////////////////
 251
 252    ///////////////////////////////////////////////////////////////////////////
 253    // End of this routine
 254    ///////////////////////////////////////////////////////////////////////////
 255    pr ("%^%-%^}\n\n");
 256 }
 257
 258 ///////////////////////////////////////////////////////////////////////////////
 259 //
 260 //  Method to generate code for dynamic traversals of one datatype.
 261 //
 262 ///////////////////////////////////////////////////////////////////////////////
 263 void RewritingCompiler::gen_dynamic_traversals(FunctorMap& F, Ty ty)
 264 {  MatchRules rules = MatchRules(F.rule_map[ty]);
 265    MatchExps  exps  = #[ MATCHexp(IDexp("redex"),0) ];
 266    rules = append(rules, #[ MATCHrule(0,WILDpat(),NOexp,NOcost,#[]) ]);
 267    gen_match_stmt(exps, rules, MATCHnotrace + MATCHwithtreecost);
 268 /*
 269    match (deref_all(ty))
 270    {  DATATYPEty( { unit, arg, terms ... }, _):
 271       {  int  arity = unit + arg;  // arity of this datatype
 272          if (arg == 0)  // all unit functors
 273          {  gen_dynamic_traversals(F, unit, terms, ty); }
 274          else if (unit == 0)  // all argument functors
 275          {  gen_dynamic_traversals(F, arg, terms, ty); }
 276          else
 277          {  pr("%^if (%s(redex)) {%+", (unit > 1 ? "boxed" : ""));
 278             gen_dynamic_traversals(F, arg, terms + unit, ty);
 279             pr("%-%^} else {%+");
 280             gen_dynamic_traversals(F, unit, terms, ty);
 281             pr("%-%^}");
 282          }
 283       }
 284    |  _: // skip, can't happen if things are ok.
 285    }
 286 */
 287 }
 288
 289 ///////////////////////////////////////////////////////////////////////////////
 290 //
 291 //  Method to generate code for dynamic traversals of one datatype,
 292 //  using a switch statement.
 293 //
 294 ///////////////////////////////////////////////////////////////////////////////
 295 void RewritingCompiler::gen_dynamic_traversals
 296    (FunctorMap& F, int arity, Cons terms[], Ty ty)
 297 {  Bool is_boxed = terms[0]->ty != NOty; // are we dealing with boxed terms?
 298    Id redex    = is_boxed ? redex_name(ty) : "(int)redex";
 299    Id untagger = is_boxed ? "->untag()" : "";
 300
 301    if (arity == 1)
 302    {  ////////////////////////////////////////////////////////////////////////
 303       //  (1 branch) No ifs or switches
 304       ////////////////////////////////////////////////////////////////////////
 305       gen_one_dynamic_traversal(F, terms[0], ty);
 306    } else if (arity == 2)
 307    {  ////////////////////////////////////////////////////////////////////////
 308       //  (2 branches) Generate an if
 309       ////////////////////////////////////////////////////////////////////////
 310       pr("%^if (%s%s) {%+", redex, untagger);
 311       gen_one_dynamic_traversal(F, terms[1], ty);
 312       pr("%-%^} else {%+");
 313       gen_one_dynamic_traversal(F, terms[0], ty);
 314       pr("%-%^}");
 315    } else
 316    {  ////////////////////////////////////////////////////////////////////////
 317       // (n-branches) Generate a switch
 318       ////////////////////////////////////////////////////////////////////////
 319       pr("%^switch(%s%s) {%+",redex,untagger);
 320       for (int i = 0; i < arity; i++)
 321       {  pr(i == arity - 1 ? "%^default: { %+" : "%^case %*: { %+",
 322             terms[i], #[], false);
 323          gen_one_dynamic_traversal(F, terms[i], ty);
 324          pr("%?} break;%-");
 325       }
 326       pr("%-%^}");
 327    }
 328 }
 329
 330 ///////////////////////////////////////////////////////////////////////////////
 331 //
 332 //  Method to generate a traversal routine for one term in a datatype.
 333 //
 334 ///////////////////////////////////////////////////////////////////////////////
 335 void RewritingCompiler::gen_one_dynamic_traversal
 336    (FunctorMap& F, Cons term, Ty ty)
 337 {  if (is_array_constructor(term->name))
 338    {  ////////////////////////////////////////////////////////////////////////
 339       // Generate array code
 340       ////////////////////////////////////////////////////////////////////////
 341       bug("RewritingCompiler::gen_one_dynamic_traversal");
 342    } else
 343    {  gen_component_dynamic_traversal(F, term, ty);
 344    }
 345 }
 346
 347 ///////////////////////////////////////////////////////////////////////////////
 348 //
 349 //  Method to generate code to traverse a component of a term.
 350 //
 351 ///////////////////////////////////////////////////////////////////////////////
 352 void RewritingCompiler::gen_component_dynamic_traversal
 353    (FunctorMap& F, Cons term, Ty ty)
 354 {  Ty  arg_ty = component_ty(ty, term);  // argument type of the term.
 355    int arity  = arity_of(arg_ty);        // arity of this type.
 356    Bool relevant[256];
 357    Bool is_record = false;
 358
 359    ///////////////////////////////////////////////////////////////////////////
 360    // Generate code to call the labeler on subcomponents.
 361    ///////////////////////////////////////////////////////////////////////////
 362    match (arg_ty)
 363    {  NOty:
 364    |  TUPLEty tys:
 365       { gen_tuple_component_dynamic_traversal(F,term,arity,tys); }
 366    |  RECORDty(labels,_,tys):
 367       { gen_record_component_dynamic_traversal(F,term,arity,relevant,labels,tys);
 368         is_record = true;
 369       }
 370    |  _: { gen_single_component_dynamic_traversal(F,term,arg_ty); }
 371    }
 372 }
 373
 374 ///////////////////////////////////////////////////////////////////////////////
 375 //
 376 //  Method to generate traversal code on one single component of a datatype
 377 //
 378 ///////////////////////////////////////////////////////////////////////////////
 379 void RewritingCompiler::gen_single_component_dynamic_traversal
 380   (FunctorMap& F, Cons term, Ty arg_ty)
 381 {  Exp e = select(IDexp("redex"),term);
 382    if (is_array_constructor(term->name))
 383    {  if (F.is_known_type(arg_ty)) // generate traversal code for vectors
 384       {  bug("RewritingCompiler::gen_single_component_dynamic_traversal");
 385       } else                       // type is unknown.
 386       {
 387       }
 388    } else
 389    {  if (F.is_known_type(arg_ty))
 390       {  pr("%^labeler(%e);\n", e); }
 391       else
 392       {  pr("%^// %T\n", arg_ty); }
 393    }
 394 }
 395
 396 ///////////////////////////////////////////////////////////////////////////////
 397 //
 398 //  Method to generate traversal code on the tuple component of a datatype
 399 //
 400 ///////////////////////////////////////////////////////////////////////////////
 401 void RewritingCompiler::gen_tuple_component_dynamic_traversal
 402   (FunctorMap& F, Cons term, int arity, Tys tys)
 403 {  Tys ts; int i;
 404    Exp e = select(IDexp("redex"),term);
 405    for (i = 0, ts = tys; i < arity && ts; i++, ts = ts->#2)
 406    {  Ty ty = ts->#1;
 407       if (F.is_known_type(ty))
 408          pr("%^labeler(%e);\n", DOTexp(e,index_of(i+1)));
 409       else
 410          pr("%^// %T\n", ty);
 411    }
 412 }
 413
 414 ///////////////////////////////////////////////////////////////////////////////
 415 //
 416 //  Method to generate traversal code on the record component of a datatype
 417 //
 418 ///////////////////////////////////////////////////////////////////////////////
 419 void RewritingCompiler::gen_record_component_dynamic_traversal
 420    (FunctorMap& F, Cons term, int arity, Bool relevant[], Ids labels, Tys tys)
 421 {  Tys ts; Ids ids; int i;
 422    Exp e = select(IDexp("redex"),term);
 423    for (ids = labels, ts = tys, i = 0; ids && ts; ids=ids->#2, ts=ts->#2, i++)
 424    {  Ty ty = ts->#1;
 425       if (F.is_known_type(ty))
 426       {  relevant[i] = true;
 427          pr("%^labeler(%e);\n", DOTexp(e,ids->#1));
 428       } else
 429       {  relevant[i] = false;
 430          pr("%^// %T\n",ty);
 431       }
 432    }
 433 }