prop-src/rwgen3.cc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //  This file is generated automatically using Prop (version 2.3.6),
   3 //  last updated on Nov 2, 1999.
   4 //  The original source file is "rwgen3.pcc".
   5 ///////////////////////////////////////////////////////////////////////////////
   6
   7 #line 1 "rwgen3.pcc"
   8 ///////////////////////////////////////////////////////////////////////////////
   9 //
  10 //  This file implements the dynamic tree parser algorithm, which is
  11 //  used to parse a tree grammar with associated reduction cost functions.
  12 //
  13 ///////////////////////////////////////////////////////////////////////////////
  14 #include <iostream>
  15 #include <AD/contain/bitset.h>
  16 #include "funmap.h"
  17 #include "ir.h"
  18 #include "ast.h"
  19 #include "matchcom.h"
  20 #include "type.h"
  21 #include "hashtab.h"
  22 #include "rwgen.h"
  23 #include "list.h"
  24 #include "options.h"
  25
  26 extern Id redex_name(Ty);
  27
  28 ///////////////////////////////////////////////////////////////////////////////
  29 //
  30 //  Top level method to generate a dynamic tree parser.
  31 //  We use a simple dynamic programming algorithm.
  32 //
  33 ///////////////////////////////////////////////////////////////////////////////
  34 void RewritingCompiler::gen_dynamic_rewriter (FunctorMap& F)
  35 {
  36    generate_state_record(F);        // generate the state record definition
  37    generate_accept_rules_tables(F); // generate the accept rule tables
  38    generate_closures(F);            // generate the closure routines
  39    generate_dynamic_labelers(F);    // generate the labeler functions
  40    generate_reducers(F);            // generate the reducer functions
  41    // Generate report
  42    if (options.generate_report) F.print_report(open_logfile());
  43 }
  44
  45 ///////////////////////////////////////////////////////////////////////////////
  46 //
  47 //  Method to generate the state record.
  48 //
  49 ///////////////////////////////////////////////////////////////////////////////
  50 void RewritingCompiler::generate_state_record (FunctorMap& F)
  51 {  pr("\n"
  52       "%^%/"
  53       "%^// State record for rewrite class %s"
  54       "%^%/"
  55       "%^struct %s_StateRec {\n"
  56       "%^   TreeTables::Cost cost[%i]; // cost for each non-terminal"
  57       "%^   struct { // accept rule number",
  58       F.class_name, F.class_name, F.nonterm_map.size()+1
  59      );
  60
  61    foreach_entry (e, F.nonterm_rules_bits)
  62    {  Id  lhs  = Id(e->k);
  63       int bits = int(e->v);
  64       pr("%^      unsigned int _%S : %i;", lhs, bits);
  65    }
  66
  67    pr("%^   } rule;"
  68       "%^};\n\n");
  69 }
  70
  71 ///////////////////////////////////////////////////////////////////////////////
  72 //
  73 //  Method to generate the accept rule tables.
  74 //
  75 ///////////////////////////////////////////////////////////////////////////////
  76 void RewritingCompiler::generate_accept_rules_tables (FunctorMap& F)
  77 {  pr("%^%/"
  78       "%^// Accept rules tables for rewrite class %s"
  79       "%^%/",
  80       F.class_name
  81      );
  82
  83    foreach_entry (e, F.nonterm_rules)
  84    {  Id         lhs   = Id(e->k);
  85       MatchRules rules = MatchRules(e->v);
  86       int max_rule     = 0;
  87
  88
  89 #line 81 "rwgen3.pcc"
  90 #line 85 "rwgen3.pcc"
  91 {
  92    for (;;) {
  93       if (rules) {
  94 #line 83 "rwgen3.pcc"
  95        if (max_rule < rules->_1->rule_number) max_rule = rules->_1->rule_number;
  96          rules = rules->_2;
  97
  98 #line 85 "rwgen3.pcc"
  99       } else { goto L1; }
 100    }
 101    L1:;
 102 }
 103 #line 86 "rwgen3.pcc"
 104 #line 86 "rwgen3.pcc"
 105
 106
 107       Id storage_class = max_rule < 128 ? "char" : "short";
 108
 109       pr ("%^const %s %s_%S_accept[] = { -1, ",
 110           storage_class, F.class_name, lhs);
 111
 112       rules = MatchRules(e->v);
 113
 114 #line 94 "rwgen3.pcc"
 115 #line 98 "rwgen3.pcc"
 116 {
 117    for (;;) {
 118       if (rules) {
 119 #line 96 "rwgen3.pcc"
 120        pr ("%i%s", rules->_1->rule_number, (rules->_2 !=
 121 #line 96 "rwgen3.pcc"
 122 #line 96 "rwgen3.pcc"
 123          nil_1_
 124 #line 96 "rwgen3.pcc"
 125 #line 96 "rwgen3.pcc"
 126         ? ", " : ""));
 127          rules = rules->_2;
 128
 129 #line 98 "rwgen3.pcc"
 130       } else { goto L2; }
 131    }
 132    L2:;
 133 }
 134 #line 99 "rwgen3.pcc"
 135 #line 99 "rwgen3.pcc"
 136
 137       pr (" };\n\n");
 138    }
 139 }
 140
 141 ///////////////////////////////////////////////////////////////////////////////
 142 //
 143 //  Method to generate the closure routines for each non-terminal
 144 //  which appears the rhs of a chain rule.
 145 //
 146 ///////////////////////////////////////////////////////////////////////////////
 147 void RewritingCompiler::generate_closures (FunctorMap& F)
 148 {  pr("%^%/"
 149       "%^// Closure methods for rewrite class %s"
 150       "%^%/",
 151       F.class_name
 152      );
 153
 154    // Generate the headers first
 155    {  foreach_entry (e, F.chain_rules)
 156       {  Id         rhs   = Id(e->k);
 157          MatchRules rules = MatchRules(e->v);
 158          Ty         ty    = rules->_1->ty; // type of states.
 159          pr ("%^static void %s_%S_closure(%t,int cost);\n",
 160              F.class_name, rhs, ty, "redex"
 161             );
 162       }
 163    }
 164
 165    pr ("\n");
 166
 167    // Then generate the definitions.
 168    {  foreach_entry (e, F.chain_rules)
 169       {  Id         rhs   = Id(e->k);
 170          MatchRules rules = MatchRules(e->v);
 171          gen_closure(F,rhs,rules);
 172       }
 173    }
 174 }
 175
 176 ///////////////////////////////////////////////////////////////////////////////
 177 //
 178 //  Method to generate the closure routine for one non-terminal.
 179 //
 180 ///////////////////////////////////////////////////////////////////////////////
 181 void RewritingCompiler::gen_closure (FunctorMap& F, Id rhs, MatchRules rules)
 182 {  Ty ty = rules->_1->ty; // type of states.
 183    pr ("%^static void %s_%S_closure(%t,int cost__)\n"
 184        "%^{%+"
 185        "%^%s_StateRec * _state_rec = (%s_StateRec *)(%s->get_state_rec());",
 186         F.class_name, rhs, ty, "redex", F.class_name,
 187         F.class_name, redex_name(ty)
 188       );
 189    int rule_no = 1;
 190    rules = rev(rules);
 191
 192 #line 154 "rwgen3.pcc"
 193 #line 186 "rwgen3.pcc"
 194 {
 195    for (;;) {
 196       if (rules) {
 197 #line 156 "rwgen3.pcc"
 198        Exp cost_exp;
 199
 200 #line 157 "rwgen3.pcc"
 201 #line 165 "rwgen3.pcc"
 202          {
 203             Cost _V1 = rules->_1->_4;
 204             if (_V1) {
 205                if (untagp(_V1)) {
 206
 207 #line 159 "rwgen3.pcc"
 208                  cost_exp = LITERALexp(INTlit(((Cost_INTcost *)derefp(_V1))->INTcost));
 209 #line 159 "rwgen3.pcc"
 210                } else {
 211
 212 #line 161 "rwgen3.pcc"
 213                 // Avoid recomputation of cost
 214                   Id v = vars.new_label();
 215                   pr ("%^const int %s = %e;", v, ((Cost_EXPcost *)_V1)->_1);
 216                   cost_exp = IDexp(v);
 217
 218 #line 165 "rwgen3.pcc"
 219                }
 220             } else {
 221 #line 158 "rwgen3.pcc"
 222               cost_exp = LITERALexp(INTlit(0));
 223 #line 158 "rwgen3.pcc"
 224             }
 225          }
 226 #line 166 "rwgen3.pcc"
 227 #line 166 "rwgen3.pcc"
 228
 229          int nonterm_number = int(F.var_map[rules->_1->_1]);
 230
 231          if (nonterm_number > 0)
 232          {  pr ("%^if (cost__ + %e < _state_rec->cost[%i])"
 233                 "%^{  _state_rec->cost[%i] = cost__ + %e;"
 234                 "%^   _state_rec->rule._%S = %i;",
 235                 cost_exp, nonterm_number, nonterm_number, cost_exp, rules->_1->_1, rule_no
 236                );
 237
 238             // Chain rules
 239             if (F.chain_rules.contains(rules->_1->_1))
 240             {  pr ("%^   %s_%S_closure(redex,cost__ + %e);",
 241                    F.class_name, rules->_1->_1, cost_exp);
 242             }
 243
 244             pr ("%^}");
 245          }
 246          rule_no++;
 247          rules = rules->_2;
 248
 249 #line 186 "rwgen3.pcc"
 250       } else { goto L3; }
 251    }
 252    L3:;
 253 }
 254 #line 187 "rwgen3.pcc"
 255 #line 187 "rwgen3.pcc"
 256
 257
 258    pr ("%-%^}\n\n");
 259 }
 260
 261 ///////////////////////////////////////////////////////////////////////////////
 262 //
 263 //  Method to generate the dynamic labelers
 264 //
 265 ///////////////////////////////////////////////////////////////////////////////
 266 void RewritingCompiler::generate_dynamic_labelers (FunctorMap& F)
 267 {
 268    ////////////////////////////////////////////////////////////////////////////
 269    //  Generate a dynamic labeler for each datatype
 270    ////////////////////////////////////////////////////////////////////////////
 271    foreach_entry (e, F.type_map)
 272    {  Ty ty = Ty(F.type_map.key(e));
 273       debug_msg("[Rewrite class %s: generating dynamic labeler for datatype %T\n",
 274                 F.class_name, ty);
 275       gen_dynamic_datatype_labeler(F, ty);
 276    }
 277 }
 278
 279 ///////////////////////////////////////////////////////////////////////////////
 280 //
 281 //  Method to generate a labeler routine for one datatype.
 282 //
 283 ///////////////////////////////////////////////////////////////////////////////
 284 void RewritingCompiler::gen_dynamic_datatype_labeler(FunctorMap& F, Ty ty)
 285 {
 286    ///////////////////////////////////////////////////////////////////////////
 287    // Generate the protocol of this labeler routine
 288    ///////////////////////////////////////////////////////////////////////////
 289    pr ("%^void %s::labeler (%t)"
 290        "%^{%+"
 291           "%^int cost__;",
 292        F.class_name, ty, "redex");
 293
 294    ///////////////////////////////////////////////////////////////////////////
 295    // Name of the redex inside this routine.
 296    ///////////////////////////////////////////////////////////////////////////
 297    Id redex = redex_name(ty);
 298
 299    ///////////////////////////////////////////////////////////////////////////
 300    //
 301    // Allocate and initialize a state record.
 302    //
 303    ///////////////////////////////////////////////////////////////////////////
 304    pr ("%^%s_StateRec * _state_rec = (%s_StateRec *)mem[sizeof(%s_StateRec)];"
 305        "%^%s->set_state_rec(_state_rec);"
 306        "%^_state_rec->cost[0] = 0;",
 307        F.class_name, F.class_name, F.class_name, redex);
 308    for (int i = 1; i <= F.nonterm_map.size(); i++)
 309    {  pr("%^_state_rec->cost[%i] = ", i);
 310    }
 311    pr ("%i;\n", TreeTables::infinite_cost);
 312
 313    ///////////////////////////////////////////////////////////////////////////
 314    // Generate code for bottomup traversal on the datatype
 315    ///////////////////////////////////////////////////////////////////////////
 316    gen_dynamic_traversals(F, ty);
 317
 318    ///////////////////////////////////////////////////////////////////////////
 319    // Update the state record.
 320    ///////////////////////////////////////////////////////////////////////////
 321
 322    ///////////////////////////////////////////////////////////////////////////
 323    // End of this routine
 324    ///////////////////////////////////////////////////////////////////////////
 325    pr ("%^%-%^}\n\n");
 326 }
 327
 328 ///////////////////////////////////////////////////////////////////////////////
 329 //
 330 //  Method to generate code for dynamic traversals of one datatype.
 331 //
 332 ///////////////////////////////////////////////////////////////////////////////
 333 void RewritingCompiler::gen_dynamic_traversals(FunctorMap& F, Ty ty)
 334 {  if (!F.rule_map.contains(ty))
 335    {  bug("%Lgen_dynamic_traversals: %t\n", ty); }
 336    MatchRules rules = MatchRules(F.rule_map[ty]);
 337    MatchExps  exps  =
 338 #line 268 "rwgen3.pcc"
 339 #line 268 "rwgen3.pcc"
 340 list_1_(MATCHexp(IDexp("redex"),0))
 341 #line 268 "rwgen3.pcc"
 342 #line 268 "rwgen3.pcc"
 343 ;
 344    rules = rev(rules);
 345    gen_match_stmt(exps, rules,
 346       MATCHnocheck + MATCHnotrace + MATCHall + MATCHwithtreecost);
 347 }
 348
 349 ///////////////////////////////////////////////////////////////////////////////
 350 //
 351 //  Method to annotate the matching tree with tree reduction cost nodes.
 352 //  Return the set of rules that matches.  The idea is to hoist
 353 //  the cost minimalization rules as near the root as possible.
 354 //
 355 ///////////////////////////////////////////////////////////////////////////////
 356 const BitSet * label_treecost (Match& m, int, MatchRules rules);
 357 const BitSet * label_treecost (Match& m, int, MatchRules rules, Match&, Match&);
 358 const BitSet * label_treecost (Match& m, int, MatchRules rules, int, Match[], Match&, Bool);
 359
 360 const BitSet * label_treecost (Match& m, int N, MatchRules rules)
 361 {
 362 #line 286 "rwgen3.pcc"
 363 #line 299 "rwgen3.pcc"
 364 {
 365    if (boxed(m)) {
 366       switch (m->tag__) {
 367          case a_Match::tag_SUCCESSmatch: {
 368             L4:;
 369 #line 287 "rwgen3.pcc"
 370            return 0;
 371 #line 287 "rwgen3.pcc"
 372             } break;
 373          case a_Match::tag_SUCCESSESmatch: {
 374 #line 290 "rwgen3.pcc"
 375            return ((Match_SUCCESSESmatch *)m)->_2;
 376 #line 290 "rwgen3.pcc"
 377             } break;
 378          case a_Match::tag_COSTmatch: {
 379 #line 289 "rwgen3.pcc"
 380            return ((Match_COSTmatch *)m)->_3;
 381 #line 289 "rwgen3.pcc"
 382             } break;
 383          case a_Match::tag_GUARDmatch: {
 384 #line 292 "rwgen3.pcc"
 385           return label_treecost(m,N,rules,((Match_GUARDmatch *)m)->_2,((Match_GUARDmatch *)m)->_3);
 386 #line 292 "rwgen3.pcc"
 387             } break;
 388          case a_Match::tag_LITERALmatch: {
 389 #line 296 "rwgen3.pcc"
 390           return label_treecost(m,N,rules,((Match_LITERALmatch *)m)->_4,((Match_LITERALmatch *)m)->_5,((Match_LITERALmatch *)m)->_6,false);
 391 #line 296 "rwgen3.pcc"
 392             } break;
 393          case a_Match::tag_RANGEmatch: {
 394 #line 298 "rwgen3.pcc"
 395           return label_treecost(m,N,rules,((Match_RANGEmatch *)m)->_5,((Match_RANGEmatch *)m)->_6);
 396 #line 298 "rwgen3.pcc"
 397             } break;
 398          case a_Match::tag_CONSmatch: {
 399 #line 294 "rwgen3.pcc"
 400           return label_treecost(m,N,rules,((Match_CONSmatch *)m)->_5,((Match_CONSmatch *)m)->_6,((Match_CONSmatch *)m)->_7,true);
 401 #line 294 "rwgen3.pcc"
 402             } break;
 403          case a_Match::tag_TREECOSTmatch: {
 404 #line 288 "rwgen3.pcc"
 405            return ((Match_TREECOSTmatch *)m)->_2;
 406 #line 288 "rwgen3.pcc"
 407             } break;
 408          default: {
 409             L5:;
 410 #line 299 "rwgen3.pcc"
 411            bug("label_treecost: %M", m); return 0;
 412 #line 299 "rwgen3.pcc"
 413             } break;
 414       }
 415    } else {
 416       if (m) {
 417           goto L5; } else {
 418           goto L4; }
 419    }
 420 }
 421 #line 300 "rwgen3.pcc"
 422 #line 300 "rwgen3.pcc"
 423
 424 }
 425
 426 ///////////////////////////////////////////////////////////////////////////////
 427 //
 428 //  Method to annotate the matching tree with tree reduction cost nodes.
 429 //  Return the set of rules that matches.
 430 //
 431 ///////////////////////////////////////////////////////////////////////////////
 432 const BitSet * label_treecost (Match& m, int N, MatchRules rules, Match& a, Match& b)
 433 {  const BitSet * s1 = label_treecost(a,N,rules);
 434    const BitSet * s2 = label_treecost(b,N,rules);
 435    if (s1 == 0 || s2 == 0) return 0;
 436    BitSet * S = new (mem_pool, N) BitSet;
 437    S->Intersect(*s1,*s2);
 438    if (S->count() == 0) return 0;
 439    m = TREECOSTmatch(m,S,rules);
 440    m->label = 0; m->shared = 0;
 441    return S;
 442 }
 443
 444 ///////////////////////////////////////////////////////////////////////////////
 445 //
 446 //  Method to annotate the matching tree with tree reduction cost nodes.
 447 //  Return the set of rules that matches.
 448 //
 449 ///////////////////////////////////////////////////////////////////////////////
 450 const BitSet * label_treecost (Match& m, int N, MatchRules rules,
 451                               int fanout, Match a[], Match& b, Bool ignore)
 452 {  const BitSet * Sb = label_treecost(b,N,rules);
 453    BitSet * S = new (mem_pool, N) BitSet;
 454    Bool empty = ! ignore && Sb == 0;
 455    if (! ignore) S->copy(*Sb);
 456    else          S->complement();
 457    for (int i = 0; i < fanout; i++)
 458    {  const BitSet * Sa = label_treecost(a[i],N,rules);
 459       if (Sa) { if (! empty) S->Intersect(*Sa); }
 460       else    empty = true;
 461    }
 462    if (empty || S->count() == 0) return 0;
 463    m = TREECOSTmatch(m,S,rules);
 464    debug_msg("[NEW TREE]\n");
 465    m->label = 0; m->shared = 0;
 466    return S;
 467 }
 468
 469 ///////////////////////////////////////////////////////////////////////////////
 470 //
 471 //  Method to prune the matching tree with tree reduction cost nodes.
 472 //  We reduce unnecessary cost minimalization nodes.
 473 //
 474 ///////////////////////////////////////////////////////////////////////////////
 475 void prune_treecost (Match& m, const BitSet * ignore)
 476 {
 477 #line 353 "rwgen3.pcc"
 478 #line 386 "rwgen3.pcc"
 479 {
 480    if (boxed(m)) {
 481       switch (m->tag__) {
 482          case a_Match::tag_SUCCESSmatch: {
 483             L6:;
 484 #line 354 "rwgen3.pcc"
 485            return;
 486 #line 354 "rwgen3.pcc"
 487             } break;
 488          case a_Match::tag_SUCCESSESmatch: {
 489 #line 361 "rwgen3.pcc"
 490            if (ignore) { ((Match_SUCCESSESmatch *)m)->_2->Difference(*ignore);
 491             if (((Match_SUCCESSESmatch *)m)->_2->count() == 0) m = FAILmatch;
 492             }
 493
 494 #line 364 "rwgen3.pcc"
 495             } break;
 496          case a_Match::tag_COSTmatch: {
 497 #line 356 "rwgen3.pcc"
 498            if (ignore) { ((Match_COSTmatch *)m)->_3->Difference(*ignore);
 499             if (((Match_COSTmatch *)m)->_3->count() == 0) m = FAILmatch;
 500             }
 501
 502 #line 359 "rwgen3.pcc"
 503             } break;
 504          case a_Match::tag_GUARDmatch: {
 505 #line 377 "rwgen3.pcc"
 506           prune_treecost(((Match_GUARDmatch *)m)->_2,ignore); prune_treecost(((Match_GUARDmatch *)m)->_3,ignore);
 507 #line 377 "rwgen3.pcc"
 508             } break;
 509          case a_Match::tag_LITERALmatch: {
 510 #line 384 "rwgen3.pcc"
 511           for (int i = 0; i < ((Match_LITERALmatch *)m)->_4; i++) prune_treecost(((Match_LITERALmatch *)m)->_5[i],ignore);
 512             prune_treecost(((Match_LITERALmatch *)m)->_6,ignore);
 513 #line 385 "rwgen3.pcc"
 514             } break;
 515          case a_Match::tag_RANGEmatch: {
 516 #line 379 "rwgen3.pcc"
 517           prune_treecost(((Match_RANGEmatch *)m)->_5,ignore); prune_treecost(((Match_RANGEmatch *)m)->_6,ignore);
 518 #line 379 "rwgen3.pcc"
 519             } break;
 520          case a_Match::tag_CONSmatch: {
 521 #line 381 "rwgen3.pcc"
 522           for (int i = 0; i < ((Match_CONSmatch *)m)->_5; i++) prune_treecost(((Match_CONSmatch *)m)->_6[i],ignore);
 523             prune_treecost(((Match_CONSmatch *)m)->_7,ignore);
 524 #line 382 "rwgen3.pcc"
 525             } break;
 526          case a_Match::tag_TREECOSTmatch: {
 527 #line 366 "rwgen3.pcc"
 528           BitSet * new_ignore;
 529             if (ignore) { new_ignore = new (mem_pool, ignore->size()) BitSet;
 530                           new_ignore->Union(*((Match_TREECOSTmatch *)m)->_2);
 531                         }
 532             else new_ignore = ((Match_TREECOSTmatch *)m)->_2;
 533             prune_treecost(((Match_TREECOSTmatch *)m)->_1,new_ignore);
 534             if (ignore) { ((Match_TREECOSTmatch *)m)->_2->Difference(*ignore);
 535                           if (((Match_TREECOSTmatch *)m)->_2->count() == 0) m = ((Match_TREECOSTmatch *)m)->_1;
 536                         }
 537
 538 #line 375 "rwgen3.pcc"
 539             } break;
 540          default: {
 541             L7:;
 542 #line 386 "rwgen3.pcc"
 543            bug("prune_treecost: %M", m);
 544 #line 386 "rwgen3.pcc"
 545             } break;
 546       }
 547    } else {
 548       if (m) {
 549           goto L7; } else {
 550           goto L6; }
 551    }
 552 }
 553 #line 387 "rwgen3.pcc"
 554 #line 387 "rwgen3.pcc"
 555
 556 }
 557
 558 ///////////////////////////////////////////////////////////////////////////////
 559 //
 560 //  Method to insert traversal code
 561 //
 562 ///////////////////////////////////////////////////////////////////////////////
 563 void add_traversal (Match& m)
 564 {
 565 #line 396 "rwgen3.pcc"
 566 #line 402 "rwgen3.pcc"
 567 {
 568    if (boxed(m)) {
 569       switch (m->tag__) {
 570          case a_Match::tag_CONSmatch: {
 571 #line 398 "rwgen3.pcc"
 572           for (int i = 0; i < ((Match_CONSmatch *)m)->_5; i++)
 573             ((Match_CONSmatch *)m)->_6[i] = TREELABELmatch(((Match_CONSmatch *)m)->_6[i],((Match_CONSmatch *)m)->_3,((Match_CONSmatch *)m)->_4,i);
 574
 575 #line 400 "rwgen3.pcc"
 576             } break;
 577          case a_Match::tag_TREECOSTmatch: {
 578 #line 401 "rwgen3.pcc"
 579           add_traversal(((Match_TREECOSTmatch *)m)->_1);
 580 #line 401 "rwgen3.pcc"
 581             } break;
 582          default: {
 583             L8:;
 584 #line 402 "rwgen3.pcc"
 585           bug ("add_traversal: %M", m);
 586 #line 402 "rwgen3.pcc"
 587             } break;
 588       }
 589    } else { goto L8; }
 590 }
 591 #line 403 "rwgen3.pcc"
 592 #line 403 "rwgen3.pcc"
 593
 594 }
 595
 596 ///////////////////////////////////////////////////////////////////////////////
 597 //
 598 //  Method to translate the matching tree into a tree with
 599 //  tree reduction cost nodes.
 600 //
 601 ///////////////////////////////////////////////////////////////////////////////
 602 Match translate_treecost (Match m, MatchRules rules)
 603 {  debug_msg("%Ltranslating rules into treecost\n");
 604    label_treecost(m,length(rules),rules);
 605    prune_treecost(m,0);
 606    add_traversal(m);
 607    return m;
 608 }
 609
 610 ///////////////////////////////////////////////////////////////////////////////
 611 //
 612 //  Return the encoded rule number.
 613 //
 614 ///////////////////////////////////////////////////////////////////////////////
 615 static int rule_of(FunctorMap * Fmap, Id lhs, int r)
 616 {  int rule_no = 1;
 617    MatchRules rules = MatchRules(Fmap->nonterm_rules[lhs]);
 618
 619 #line 428 "rwgen3.pcc"
 620 #line 433 "rwgen3.pcc"
 621 {
 622    for (;;) {
 623       if (rules) {
 624 #line 430 "rwgen3.pcc"
 625        if (rules->_1->rule_number == r) return rule_no;
 626          rules = rules->_2;
 627          rule_no++;
 628
 629 #line 433 "rwgen3.pcc"
 630       } else { goto L9; }
 631    }
 632    L9:;
 633 }
 634 #line 434 "rwgen3.pcc"
 635 #line 434 "rwgen3.pcc"
 636
 637    bug("rule_of");
 638    return 0;
 639 }
 640
 641 ///////////////////////////////////////////////////////////////////////////////
 642 //
 643 //  Method for generating labeling code for pattern parsing.
 644 //
 645 ///////////////////////////////////////////////////////////////////////////////
 646 void RewritingCompiler::gen_treelabel_match (Match m, Ty ty, Ty alg_ty, int k)
 647 {  // Generate traversal code
 648
 649 #line 446 "rwgen3.pcc"
 650 #line 474 "rwgen3.pcc"
 651 {
 652    Ty _V2 = deref_all(ty);
 653    if (alg_ty) {
 654       switch (alg_ty->tag__) {
 655          case a_Ty::tag_TYCONty: {
 656             if (boxed(((Ty_TYCONty *)alg_ty)->_1)) {
 657                switch (((Ty_TYCONty *)alg_ty)->_1->tag__) {
 658                   case a_TyCon::tag_DATATYPEtycon: {
 659                      if (_V2) {
 660                         switch (_V2->tag__) {
 661                            case a_Ty::tag_TYCONty: {
 662 #line 448 "rwgen3.pcc"
 663                             Cons cons = ((TyCon_DATATYPEtycon *)((Ty_TYCONty *)alg_ty)->_1)->terms[k];
 664                               Ty arg_ty = apply_ty(cons->cons_ty,((Ty_TYCONty *)_V2)->_2);
 665                               Exp e     = select(IDexp("redex"),cons);
 666                                  if (cons->ty == NOty)
 667                                  {  error("%Ltree parsing mode cannot be used on datatype with unit constructors: %T\n", alg_ty);
 668                                  }
 669
 670 #line 454 "rwgen3.pcc"
 671 #line 471 "rwgen3.pcc"
 672                               {
 673                                  if (arg_ty) {
 674                                     switch (arg_ty->tag__) {
 675                                        case a_Ty::tag_TYCONty: {
 676                                           if (boxed(((Ty_TYCONty *)arg_ty)->_1)) {
 677                                              switch (((Ty_TYCONty *)arg_ty)->_1->tag__) {
 678                                                 case a_TyCon::tag_RECORDtycon: {
 679 #line 464 "rwgen3.pcc"
 680                                                  Ids ids; Tys ((Ty_TYCONty *)_V2)->_2;
 681                                                    for (ids = ((TyCon_RECORDtycon *)((Ty_TYCONty *)arg_ty)->_1)->_1, ((Ty_TYCONty *)_V2)->_2 = ((Ty_TYCONty *)arg_ty)->_2; ids && ((Ty_TYCONty *)arg_ty)->_2;
 682                                                         ids = ids->_2, ((Ty_TYCONty *)_V2)->_2 = ((Ty_TYCONty *)_V2)->_2->_2)
 683                                                    {  if (Fmap->is_rewritable_type(((Ty_TYCONty *)_V2)->_2->_1))
 684                                                          pr("%^labeler(%e);", DOTexp(e,ids->_1));
 685                                                    }
 686
 687 #line 470 "rwgen3.pcc"
 688                                                    } break;
 689                                                 default: {
 690                                                    L10:;
 691 #line 471 "rwgen3.pcc"
 692                                                  if (Fmap->is_rewritable_type(arg_ty)) pr("%^labeler(%e);",e);
 693 #line 471 "rwgen3.pcc"
 694                                                    } break;
 695                                              }
 696                                           } else {
 697                                              switch ((int)((Ty_TYCONty *)arg_ty)->_1) {
 698                                                 case ((int)TUPLEtycon): {
 699 #line 457 "rwgen3.pcc"
 700                                                  int i = 1;
 701                                                    for_each(Ty, t, ((Ty_TYCONty *)arg_ty)->_2)
 702                                                    {  if (Fmap->is_rewritable_type(t))
 703                                                          pr("%^labeler(%e);", DOTexp(e,index_of(i))); i++;
 704                                                    }
 705
 706 #line 462 "rwgen3.pcc"
 707                                                    } break;
 708                                                 default: { goto L10; } break;
 709                                              }
 710                                           }
 711                                           } break;
 712                                        default: { goto L10; } break;
 713                                     }
 714                                  } else {}
 715                               }
 716 #line 472 "rwgen3.pcc"
 717 #line 472 "rwgen3.pcc"
 718
 719
 720 #line 473 "rwgen3.pcc"
 721                               } break;
 722                            default: {
 723                               L11:;
 724 #line 474 "rwgen3.pcc"
 725                              bug("RewritingCompiler::gen_treelabel_match");
 726 #line 474 "rwgen3.pcc"
 727                               } break;
 728                         }
 729                      } else { goto L11; }
 730                      } break;
 731                   default: { goto L11; } break;
 732                }
 733             } else { goto L11; }
 734             } break;
 735          default: { goto L11; } break;
 736       }
 737    } else { goto L11; }
 738 }
 739 #line 475 "rwgen3.pcc"
 740 #line 475 "rwgen3.pcc"
 741
 742
 743    // Generate labeling code
 744    gen(m);
 745 }
 746
 747 ///////////////////////////////////////////////////////////////////////////////
 748 //
 749 //  Method for generating treecost minimalization code from a pattern
 750 //  matching tree.
 751 //
 752 ///////////////////////////////////////////////////////////////////////////////
 753 void RewritingCompiler::gen_treecost_match (Match m, const BitSet * set,
 754                                             MatchRules rules)
 755 {  gen(m);
 756    int rule_no = 0;
 757
 758 #line 491 "rwgen3.pcc"
 759 #line 520 "rwgen3.pcc"
 760 {
 761    for (;;) {
 762       if (rules) {
 763 #line 493 "rwgen3.pcc"
 764        if (set->contains(rule_no))
 765          {  if (rules->_1->_1)
 766             {  pr ("%^// %r\n", rules->_1);
 767                Exp cost_exp;
 768
 769 #line 497 "rwgen3.pcc"
 770 #line 502 "rwgen3.pcc"
 771          {
 772             Cost _V3 = rules->_1->_4;
 773             if (_V3) {
 774                if (untagp(_V3)) {
 775
 776 #line 499 "rwgen3.pcc"
 777                  cost_exp = LITERALexp(INTlit(((Cost_INTcost *)derefp(_V3))->INTcost));
 778 #line 499 "rwgen3.pcc"
 779                } else {
 780
 781 #line 500 "rwgen3.pcc"
 782                  cost_exp = IDexp(vars.new_label());
 783                   pr("%^int %e = %e;",cost_exp,((Cost_EXPcost *)_V3)->_1);
 784
 785 #line 502 "rwgen3.pcc"
 786                }
 787             } else {
 788 #line 498 "rwgen3.pcc"
 789               cost_exp = LITERALexp(INTlit(0));
 790 #line 498 "rwgen3.pcc"
 791             }
 792          }
 793 #line 503 "rwgen3.pcc"
 794 #line 503 "rwgen3.pcc"
 795
 796          int nonterm_number = int(Fmap->var_map[rules->_1->_1]);
 797          pr ("%^cost__ = %e + %e;"
 798              "%^if (cost__ < _state_rec->cost[%i])"
 799              "%^{   _state_rec->cost[%i] = cost__;"
 800              "%^    _state_rec->rule._%S = %i;",
 801              cost_exp, Fmap->cost_expr(rules->_1->_1,rules->_1->_2),
 802              nonterm_number, nonterm_number,
 803              rules->_1->_1, rule_of(Fmap,rules->_1->_1,rules->_1->rule_number));
 804
 805          if (Fmap->chain_rules.contains(rules->_1->_1))
 806             pr ("%^   %s_%S_closure(redex, cost__);",
 807                    Fmap->class_name, rules->_1->_1);
 808          pr ("%^}");
 809          }
 810          }
 811          rules = rules->_2; rule_no++;
 812
 813 #line 520 "rwgen3.pcc"
 814       } else { goto L12; }
 815    }
 816    L12:;
 817 }
 818 #line 521 "rwgen3.pcc"
 819 #line 521 "rwgen3.pcc"
 820
 821 }
 822 #line 523 "rwgen3.pcc"
 823 /*
 824 ------------------------------- Statistics -------------------------------
 825 Merge matching rules         = yes
 826 Number of DFA nodes merged   = 77
 827 Number of ifs generated      = 19
 828 Number of switches generated = 9
 829 Number of labels             = 7
 830 Number of gotos              = 12
 831 Adaptive matching            = enabled
 832 Fast string matching         = disabled
 833 Inline downcasts             = enabled
 834 --------------------------------------------------------------------------
 835 */