gcc/genmatch.c

   1 /* Generate pattern matching and transform code shared between
   2    GENERIC and GIMPLE folding code from match-and-simplify description.
   3
   4    Copyright (C) 2014-2015 Free Software Foundation, Inc.
   5    Contributed by Richard Biener <rguenther@suse.de>
   6    and Prathamesh Kulkarni  <bilbotheelffriend@gmail.com>
   7
   8 This file is part of GCC.
   9
  10 GCC is free software; you can redistribute it and/or modify it under
  11 the terms of the GNU General Public License as published by the Free
  12 Software Foundation; either version 3, or (at your option) any later
  13 version.
  14
  15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  18 for more details.
  19
  20 You should have received a copy of the GNU General Public License
  21 along with GCC; see the file COPYING3.  If not see
  22 <http://www.gnu.org/licenses/>.  */
  23
  24 #include "bconfig.h"
  25 #include <new>
  26 #include "system.h"
  27 #include "coretypes.h"
  28 #include <cpplib.h>
  29 #include "errors.h"
  30 #include "hash-table.h"
  31 #include "hash-set.h"
  32 #include "is-a.h"
  33
  34
  35 /* Stubs for GGC referenced through instantiations triggered by hash-map.  */
  36 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
  37                                   size_t, size_t MEM_STAT_DECL)
  38 {
  39   return NULL;
  40 }
  41 void ggc_free (void *)
  42 {
  43 }
  44
  45
  46 /* libccp helpers.  */
  47
  48 static struct line_maps *line_table;
  49
  50 static bool
  51 #if GCC_VERSION >= 4001
  52 __attribute__((format (printf, 6, 0)))
  53 #endif
  54 error_cb (cpp_reader *, int errtype, int, source_location location,
  55           unsigned int, const char *msg, va_list *ap)
  56 {
  57   const line_map_ordinary *map;
  58   linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
  59   expanded_location loc = linemap_expand_location (line_table, map, location);
  60   fprintf (stderr, "%s:%d:%d %s: ", loc.file, loc.line, loc.column,
  61            (errtype == CPP_DL_WARNING) ? "warning" : "error");
  62   vfprintf (stderr, msg, *ap);
  63   fprintf (stderr, "\n");
  64   FILE *f = fopen (loc.file, "r");
  65   if (f)
  66     {
  67       char buf[128];
  68       while (loc.line > 0)
  69         {
  70           if (!fgets (buf, 128, f))
  71             goto notfound;
  72           if (buf[strlen (buf) - 1] != '\n')
  73             {
  74               if (loc.line > 1)
  75                 loc.line++;
  76             }
  77           loc.line--;
  78         }
  79       fprintf (stderr, "%s", buf);
  80       for (int i = 0; i < loc.column - 1; ++i)
  81         fputc (' ', stderr);
  82       fputc ('^', stderr);
  83       fputc ('\n', stderr);
  84 notfound:
  85       fclose (f);
  86     }
  87
  88   if (errtype == CPP_DL_FATAL)
  89     exit (1);
  90   return false;
  91 }
  92
  93 static void
  94 #if GCC_VERSION >= 4001
  95 __attribute__((format (printf, 2, 3)))
  96 #endif
  97 fatal_at (const cpp_token *tk, const char *msg, ...)
  98 {
  99   va_list ap;
 100   va_start (ap, msg);
 101   error_cb (NULL, CPP_DL_FATAL, 0, tk->src_loc, 0, msg, &ap);
 102   va_end (ap);
 103 }
 104
 105 static void
 106 #if GCC_VERSION >= 4001
 107 __attribute__((format (printf, 2, 3)))
 108 #endif
 109 fatal_at (source_location loc, const char *msg, ...)
 110 {
 111   va_list ap;
 112   va_start (ap, msg);
 113   error_cb (NULL, CPP_DL_FATAL, 0, loc, 0, msg, &ap);
 114   va_end (ap);
 115 }
 116
 117 static void
 118 #if GCC_VERSION >= 4001
 119 __attribute__((format (printf, 2, 3)))
 120 #endif
 121 warning_at (const cpp_token *tk, const char *msg, ...)
 122 {
 123   va_list ap;
 124   va_start (ap, msg);
 125   error_cb (NULL, CPP_DL_WARNING, 0, tk->src_loc, 0, msg, &ap);
 126   va_end (ap);
 127 }
 128
 129 /* Like fprintf, but print INDENT spaces at the beginning.  */
 130
 131 static void
 132 #if GCC_VERSION >= 4001
 133 __attribute__((format (printf, 3, 4)))
 134 #endif
 135 fprintf_indent (FILE *f, unsigned int indent, const char *format, ...)
 136 {
 137   va_list ap;
 138   for (; indent >= 8; indent -= 8)
 139     fputc ('\t', f);
 140   fprintf (f, "%*s", indent, "");
 141   va_start (ap, format);
 142   vfprintf (f, format, ap);
 143   va_end (ap);
 144 }
 145
 146 static void
 147 output_line_directive (FILE *f, source_location location,
 148                        bool dumpfile = false)
 149 {
 150   const line_map_ordinary *map;
 151   linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
 152   expanded_location loc = linemap_expand_location (line_table, map, location);
 153   if (dumpfile)
 154     {
 155       /* When writing to a dumpfile only dump the filename.  */
 156       const char *file = strrchr (loc.file, DIR_SEPARATOR);
 157       if (!file)
 158         file = loc.file;
 159       else
 160         ++file;
 161       fprintf (f, "%s:%d", file, loc.line);
 162     }
 163   else
 164     /* Other gen programs really output line directives here, at least for
 165        development it's right now more convenient to have line information
 166        from the generated file.  Still keep the directives as comment for now
 167        to easily back-point to the meta-description.  */
 168     fprintf (f, "/* #line %d \"%s\" */\n", loc.line, loc.file);
 169 }
 170
 171
 172 /* Pull in tree codes and builtin function codes from their
 173    definition files.  */
 174
 175 #define DEFTREECODE(SYM, STRING, TYPE, NARGS)   SYM,
 176 enum tree_code {
 177 #include "tree.def"
 178 CONVERT0,
 179 CONVERT1,
 180 CONVERT2,
 181 VIEW_CONVERT0,
 182 VIEW_CONVERT1,
 183 VIEW_CONVERT2,
 184 MAX_TREE_CODES
 185 };
 186 #undef DEFTREECODE
 187
 188 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
 189 enum built_in_function {
 190 #include "builtins.def"
 191 END_BUILTINS
 192 };
 193 #undef DEF_BUILTIN
 194
 195 /* Return true if CODE represents a commutative tree code.  Otherwise
 196    return false.  */
 197 bool
 198 commutative_tree_code (enum tree_code code)
 199 {
 200   switch (code)
 201     {
 202     case PLUS_EXPR:
 203     case MULT_EXPR:
 204     case MULT_HIGHPART_EXPR:
 205     case MIN_EXPR:
 206     case MAX_EXPR:
 207     case BIT_IOR_EXPR:
 208     case BIT_XOR_EXPR:
 209     case BIT_AND_EXPR:
 210     case NE_EXPR:
 211     case EQ_EXPR:
 212     case UNORDERED_EXPR:
 213     case ORDERED_EXPR:
 214     case UNEQ_EXPR:
 215     case LTGT_EXPR:
 216     case TRUTH_AND_EXPR:
 217     case TRUTH_XOR_EXPR:
 218     case TRUTH_OR_EXPR:
 219     case WIDEN_MULT_EXPR:
 220     case VEC_WIDEN_MULT_HI_EXPR:
 221     case VEC_WIDEN_MULT_LO_EXPR:
 222     case VEC_WIDEN_MULT_EVEN_EXPR:
 223     case VEC_WIDEN_MULT_ODD_EXPR:
 224       return true;
 225
 226     default:
 227       break;
 228     }
 229   return false;
 230 }
 231
 232 /* Return true if CODE represents a ternary tree code for which the
 233    first two operands are commutative.  Otherwise return false.  */
 234 bool
 235 commutative_ternary_tree_code (enum tree_code code)
 236 {
 237   switch (code)
 238     {
 239     case WIDEN_MULT_PLUS_EXPR:
 240     case WIDEN_MULT_MINUS_EXPR:
 241     case DOT_PROD_EXPR:
 242     case FMA_EXPR:
 243       return true;
 244
 245     default:
 246       break;
 247     }
 248   return false;
 249 }
 250
 251
 252 /* Base class for all identifiers the parser knows.  */
 253
 254 struct id_base : nofree_ptr_hash<id_base>
 255 {
 256   enum id_kind { CODE, FN, PREDICATE, USER } kind;
 257
 258   id_base (id_kind, const char *, int = -1);
 259
 260   hashval_t hashval;
 261   int nargs;
 262   const char *id;
 263
 264   /* hash_table support.  */
 265   static inline hashval_t hash (const id_base *);
 266   static inline int equal (const id_base *, const id_base *);
 267 };
 268
 269 inline hashval_t
 270 id_base::hash (const id_base *op)
 271 {
 272   return op->hashval;
 273 }
 274
 275 inline int
 276 id_base::equal (const id_base *op1,
 277                         const id_base *op2)
 278 {
 279   return (op1->hashval == op2->hashval
 280           && strcmp (op1->id, op2->id) == 0);
 281 }
 282
 283 /* Hashtable of known pattern operators.  This is pre-seeded from
 284    all known tree codes and all known builtin function ids.  */
 285 static hash_table<id_base> *operators;
 286
 287 id_base::id_base (id_kind kind_, const char *id_, int nargs_)
 288 {
 289   kind = kind_;
 290   id = id_;
 291   nargs = nargs_;
 292   hashval = htab_hash_string (id);
 293 }
 294
 295 /* Identifier that maps to a tree code.  */
 296
 297 struct operator_id : public id_base
 298 {
 299   operator_id (enum tree_code code_, const char *id_, unsigned nargs_,
 300                const char *tcc_)
 301       : id_base (id_base::CODE, id_, nargs_), code (code_), tcc (tcc_) {}
 302   enum tree_code code;
 303   const char *tcc;
 304 };
 305
 306 /* Identifier that maps to a builtin function code.  */
 307
 308 struct fn_id : public id_base
 309 {
 310   fn_id (enum built_in_function fn_, const char *id_)
 311       : id_base (id_base::FN, id_), fn (fn_) {}
 312   enum built_in_function fn;
 313 };
 314
 315 struct simplify;
 316
 317 /* Identifier that maps to a user-defined predicate.  */
 318
 319 struct predicate_id : public id_base
 320 {
 321   predicate_id (const char *id_)
 322     : id_base (id_base::PREDICATE, id_), matchers (vNULL) {}
 323   vec<simplify *> matchers;
 324 };
 325
 326 /* Identifier that maps to a operator defined by a 'for' directive.  */
 327
 328 struct user_id : public id_base
 329 {
 330   user_id (const char *id_, bool is_oper_list_ = false)
 331     : id_base (id_base::USER, id_), substitutes (vNULL),
 332       used (false), is_oper_list (is_oper_list_) {}
 333   vec<id_base *> substitutes;
 334   bool used;
 335   bool is_oper_list;
 336 };
 337
 338 template<>
 339 template<>
 340 inline bool
 341 is_a_helper <fn_id *>::test (id_base *id)
 342 {
 343   return id->kind == id_base::FN;
 344 }
 345
 346 template<>
 347 template<>
 348 inline bool
 349 is_a_helper <operator_id *>::test (id_base *id)
 350 {
 351   return id->kind == id_base::CODE;
 352 }
 353
 354 template<>
 355 template<>
 356 inline bool
 357 is_a_helper <predicate_id *>::test (id_base *id)
 358 {
 359   return id->kind == id_base::PREDICATE;
 360 }
 361
 362 template<>
 363 template<>
 364 inline bool
 365 is_a_helper <user_id *>::test (id_base *id)
 366 {
 367   return id->kind == id_base::USER;
 368 }
 369
 370 /* Add a predicate identifier to the hash.  */
 371
 372 static predicate_id *
 373 add_predicate (const char *id)
 374 {
 375   predicate_id *p = new predicate_id (id);
 376   id_base **slot = operators->find_slot_with_hash (p, p->hashval, INSERT);
 377   if (*slot)
 378     fatal ("duplicate id definition");
 379   *slot = p;
 380   return p;
 381 }
 382
 383 /* Add a tree code identifier to the hash.  */
 384
 385 static void
 386 add_operator (enum tree_code code, const char *id,
 387               const char *tcc, unsigned nargs)
 388 {
 389   if (strcmp (tcc, "tcc_unary") != 0
 390       && strcmp (tcc, "tcc_binary") != 0
 391       && strcmp (tcc, "tcc_comparison") != 0
 392       && strcmp (tcc, "tcc_expression") != 0
 393       /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR.  */
 394       && strcmp (tcc, "tcc_reference") != 0
 395       /* To have INTEGER_CST and friends as "predicate operators".  */
 396       && strcmp (tcc, "tcc_constant") != 0
 397       /* And allow CONSTRUCTOR for vector initializers.  */
 398       && !(code == CONSTRUCTOR))
 399     return;
 400   /* Treat ADDR_EXPR as atom, thus don't allow matching its operand.  */
 401   if (code == ADDR_EXPR)
 402     nargs = 0;
 403   operator_id *op = new operator_id (code, id, nargs, tcc);
 404   id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
 405   if (*slot)
 406     fatal ("duplicate id definition");
 407   *slot = op;
 408 }
 409
 410 /* Add a builtin identifier to the hash.  */
 411
 412 static void
 413 add_builtin (enum built_in_function code, const char *id)
 414 {
 415   fn_id *fn = new fn_id (code, id);
 416   id_base **slot = operators->find_slot_with_hash (fn, fn->hashval, INSERT);
 417   if (*slot)
 418     fatal ("duplicate id definition");
 419   *slot = fn;
 420 }
 421
 422 /* Helper for easy comparing ID with tree code CODE.  */
 423
 424 static bool
 425 operator==(id_base &id, enum tree_code code)
 426 {
 427   if (operator_id *oid = dyn_cast <operator_id *> (&id))
 428     return oid->code == code;
 429   return false;
 430 }
 431
 432 /* Lookup the identifier ID.  */
 433
 434 id_base *
 435 get_operator (const char *id)
 436 {
 437   id_base tem (id_base::CODE, id);
 438
 439   id_base *op = operators->find_with_hash (&tem, tem.hashval);
 440   if (op)
 441     {
 442       /* If this is a user-defined identifier track whether it was used.  */
 443       if (user_id *uid = dyn_cast<user_id *> (op))
 444         uid->used = true;
 445       return op;
 446     }
 447
 448   /* Try all-uppercase.  */
 449   char *id2 = xstrdup (id);
 450   for (unsigned i = 0; i < strlen (id2); ++i)
 451     id2[i] = TOUPPER (id2[i]);
 452   new (&tem) id_base (id_base::CODE, id2);
 453   op = operators->find_with_hash (&tem, tem.hashval);
 454   if (op)
 455     {
 456       free (id2);
 457       return op;
 458     }
 459
 460   /* Try _EXPR appended.  */
 461   id2 = (char *)xrealloc (id2, strlen (id2) + sizeof ("_EXPR") + 1);
 462   strcat (id2, "_EXPR");
 463   new (&tem) id_base (id_base::CODE, id2);
 464   op = operators->find_with_hash (&tem, tem.hashval);
 465   if (op)
 466     {
 467       free (id2);
 468       return op;
 469     }
 470
 471   return 0;
 472 }
 473
 474 typedef hash_map<nofree_string_hash, unsigned> cid_map_t;
 475
 476
 477 /* The AST produced by parsing of the pattern definitions.  */
 478
 479 struct dt_operand;
 480 struct capture_info;
 481
 482 /* The base class for operands.  */
 483
 484 struct operand {
 485   enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR, OP_IF, OP_WITH };
 486   operand (enum op_type type_, source_location loc_)
 487     : type (type_), location (loc_) {}
 488   enum op_type type;
 489   source_location location;
 490   virtual void gen_transform (FILE *, int, const char *, bool, int,
 491                               const char *, capture_info *,
 492                               dt_operand ** = 0,
 493                               bool = true)
 494     { gcc_unreachable  (); }
 495 };
 496
 497 /* A predicate operand.  Predicates are leafs in the AST.  */
 498
 499 struct predicate : public operand
 500 {
 501   predicate (predicate_id *p_, source_location loc)
 502     : operand (OP_PREDICATE, loc), p (p_) {}
 503   predicate_id *p;
 504 };
 505
 506 /* An operand that constitutes an expression.  Expressions include
 507    function calls and user-defined predicate invocations.  */
 508
 509 struct expr : public operand
 510 {
 511   expr (id_base *operation_, source_location loc, bool is_commutative_ = false)
 512     : operand (OP_EXPR, loc), operation (operation_),
 513       ops (vNULL), expr_type (NULL), is_commutative (is_commutative_),
 514       is_generic (false), force_single_use (false) {}
 515   expr (expr *e)
 516     : operand (OP_EXPR, e->location), operation (e->operation),
 517       ops (vNULL), expr_type (e->expr_type), is_commutative (e->is_commutative),
 518       is_generic (e->is_generic), force_single_use (e->force_single_use) {}
 519   void append_op (operand *op) { ops.safe_push (op); }
 520   /* The operator and its operands.  */
 521   id_base *operation;
 522   vec<operand *> ops;
 523   /* An explicitely specified type - used exclusively for conversions.  */
 524   const char *expr_type;
 525   /* Whether the operation is to be applied commutatively.  This is
 526      later lowered to two separate patterns.  */
 527   bool is_commutative;
 528   /* Whether the expression is expected to be in GENERIC form.  */
 529   bool is_generic;
 530   /* Whether pushing any stmt to the sequence should be conditional
 531      on this expression having a single-use.  */
 532   bool force_single_use;
 533   virtual void gen_transform (FILE *f, int, const char *, bool, int,
 534                               const char *, capture_info *,
 535                               dt_operand ** = 0, bool = true);
 536 };
 537
 538 /* An operator that is represented by native C code.  This is always
 539    a leaf operand in the AST.  This class is also used to represent
 540    the code to be generated for 'if' and 'with' expressions.  */
 541
 542 struct c_expr : public operand
 543 {
 544   /* A mapping of an identifier and its replacement.  Used to apply
 545      'for' lowering.  */
 546   struct id_tab {
 547     const char *id;
 548     const char *oper;
 549     id_tab (const char *id_, const char *oper_): id (id_), oper (oper_) {}
 550   };
 551
 552   c_expr (cpp_reader *r_, source_location loc,
 553           vec<cpp_token> code_, unsigned nr_stmts_,
 554           vec<id_tab> ids_, cid_map_t *capture_ids_)
 555     : operand (OP_C_EXPR, loc), r (r_), code (code_),
 556       capture_ids (capture_ids_), nr_stmts (nr_stmts_), ids (ids_) {}
 557   /* cpplib tokens and state to transform this back to source.  */
 558   cpp_reader *r;
 559   vec<cpp_token> code;
 560   cid_map_t *capture_ids;
 561   /* The number of statements parsed (well, the number of ';'s).  */
 562   unsigned nr_stmts;
 563   /* The identifier replacement vector.  */
 564   vec<id_tab> ids;
 565   virtual void gen_transform (FILE *f, int, const char *, bool, int,
 566                               const char *, capture_info *,
 567                               dt_operand ** = 0, bool = true);
 568 };
 569
 570 /* A wrapper around another operand that captures its value.  */
 571
 572 struct capture : public operand
 573 {
 574   capture (source_location loc, unsigned where_, operand *what_)
 575       : operand (OP_CAPTURE, loc), where (where_), what (what_) {}
 576   /* Identifier index for the value.  */
 577   unsigned where;
 578   /* The captured value.  */
 579   operand *what;
 580   virtual void gen_transform (FILE *f, int, const char *, bool, int,
 581                               const char *, capture_info *,
 582                               dt_operand ** = 0, bool = true);
 583 };
 584
 585 /* if expression.  */
 586
 587 struct if_expr : public operand
 588 {
 589   if_expr (source_location loc)
 590     : operand (OP_IF, loc), cond (NULL), trueexpr (NULL), falseexpr (NULL) {}
 591   c_expr *cond;
 592   operand *trueexpr;
 593   operand *falseexpr;
 594 };
 595
 596 /* with expression.  */
 597
 598 struct with_expr : public operand
 599 {
 600   with_expr (source_location loc)
 601     : operand (OP_WITH, loc), with (NULL), subexpr (NULL) {}
 602   c_expr *with;
 603   operand *subexpr;
 604 };
 605
 606 template<>
 607 template<>
 608 inline bool
 609 is_a_helper <capture *>::test (operand *op)
 610 {
 611   return op->type == operand::OP_CAPTURE;
 612 }
 613
 614 template<>
 615 template<>
 616 inline bool
 617 is_a_helper <predicate *>::test (operand *op)
 618 {
 619   return op->type == operand::OP_PREDICATE;
 620 }
 621
 622 template<>
 623 template<>
 624 inline bool
 625 is_a_helper <c_expr *>::test (operand *op)
 626 {
 627   return op->type == operand::OP_C_EXPR;
 628 }
 629
 630 template<>
 631 template<>
 632 inline bool
 633 is_a_helper <expr *>::test (operand *op)
 634 {
 635   return op->type == operand::OP_EXPR;
 636 }
 637
 638 template<>
 639 template<>
 640 inline bool
 641 is_a_helper <if_expr *>::test (operand *op)
 642 {
 643   return op->type == operand::OP_IF;
 644 }
 645
 646 template<>
 647 template<>
 648 inline bool
 649 is_a_helper <with_expr *>::test (operand *op)
 650 {
 651   return op->type == operand::OP_WITH;
 652 }
 653
 654 /* The main class of a pattern and its transform.  This is used to
 655    represent both (simplify ...) and (match ...) kinds.  The AST
 656    duplicates all outer 'if' and 'for' expressions here so each
 657    simplify can exist in isolation.  */
 658
 659 struct simplify
 660 {
 661   enum simplify_kind { SIMPLIFY, MATCH };
 662
 663   simplify (simplify_kind kind_, operand *match_, operand *result_,
 664             vec<vec<user_id *> > for_vec_, cid_map_t *capture_ids_)
 665       : kind (kind_), match (match_), result (result_),
 666       for_vec (for_vec_),
 667       capture_ids (capture_ids_), capture_max (capture_ids_->elements () - 1) {}
 668
 669   simplify_kind kind;
 670   /* The expression that is matched against the GENERIC or GIMPLE IL.  */
 671   operand *match;
 672   /* For a (simplify ...) an expression with ifs and withs with the expression
 673      produced when the pattern applies in the leafs.
 674      For a (match ...) the leafs are either empty if it is a simple predicate
 675      or the single expression specifying the matched operands.  */
 676   struct operand *result;
 677   /* Collected 'for' expression operators that have to be replaced
 678      in the lowering phase.  */
 679   vec<vec<user_id *> > for_vec;
 680   /* A map of capture identifiers to indexes.  */
 681   cid_map_t *capture_ids;
 682   int capture_max;
 683 };
 684
 685 /* Debugging routines for dumping the AST.  */
 686
 687 DEBUG_FUNCTION void
 688 print_operand (operand *o, FILE *f = stderr, bool flattened = false)
 689 {
 690   if (capture *c = dyn_cast<capture *> (o))
 691     {
 692       fprintf (f, "@%u", c->where);
 693       if (c->what && flattened == false)
 694         {
 695           putc (':', f);
 696           print_operand (c->what, f, flattened);
 697           putc (' ', f);
 698         }
 699     }
 700
 701   else if (predicate *p = dyn_cast<predicate *> (o))
 702     fprintf (f, "%s", p->p->id);
 703
 704   else if (is_a<c_expr *> (o))
 705     fprintf (f, "c_expr");
 706
 707   else if (expr *e = dyn_cast<expr *> (o))
 708     {
 709       fprintf (f, "(%s", e->operation->id);
 710
 711       if (flattened == false)
 712         {
 713           putc (' ', f);
 714           for (unsigned i = 0; i < e->ops.length (); ++i)
 715             {
 716               print_operand (e->ops[i], f, flattened);
 717               putc (' ', f);
 718             }
 719         }
 720       putc (')', f);
 721     }
 722
 723   else
 724     gcc_unreachable ();
 725 }
 726
 727 DEBUG_FUNCTION void
 728 print_matches (struct simplify *s, FILE *f = stderr)
 729 {
 730   fprintf (f, "for expression: ");
 731   print_operand (s->match, f);
 732   putc ('\n', f);
 733 }
 734
 735
 736 /* AST lowering.  */
 737
 738 /* Lowering of commutative operators.  */
 739
 740 static void
 741 cartesian_product (const vec< vec<operand *> >& ops_vector,
 742                    vec< vec<operand *> >& result, vec<operand *>& v, unsigned n)
 743 {
 744   if (n == ops_vector.length ())
 745     {
 746       vec<operand *> xv = v.copy ();
 747       result.safe_push (xv);
 748       return;
 749     }
 750
 751   for (unsigned i = 0; i < ops_vector[n].length (); ++i)
 752     {
 753       v[n] = ops_vector[n][i];
 754       cartesian_product (ops_vector, result, v, n + 1);
 755     }
 756 }
 757
 758 /* Lower OP to two operands in case it is marked as commutative.  */
 759
 760 static vec<operand *>
 761 commutate (operand *op)
 762 {
 763   vec<operand *> ret = vNULL;
 764
 765   if (capture *c = dyn_cast <capture *> (op))
 766     {
 767       if (!c->what)
 768         {
 769           ret.safe_push (op);
 770           return ret;
 771         }
 772       vec<operand *> v = commutate (c->what);
 773       for (unsigned i = 0; i < v.length (); ++i)
 774         {
 775           capture *nc = new capture (c->location, c->where, v[i]);
 776           ret.safe_push (nc);
 777         }
 778       return ret;
 779     }
 780
 781   expr *e = dyn_cast <expr *> (op);
 782   if (!e || e->ops.length () == 0)
 783     {
 784       ret.safe_push (op);
 785       return ret;
 786     }
 787
 788   vec< vec<operand *> > ops_vector = vNULL;
 789   for (unsigned i = 0; i < e->ops.length (); ++i)
 790     ops_vector.safe_push (commutate (e->ops[i]));
 791
 792   auto_vec< vec<operand *> > result;
 793   auto_vec<operand *> v (e->ops.length ());
 794   v.quick_grow_cleared (e->ops.length ());
 795   cartesian_product (ops_vector, result, v, 0);
 796
 797
 798   for (unsigned i = 0; i < result.length (); ++i)
 799     {
 800       expr *ne = new expr (e);
 801       ne->is_commutative = false;
 802       for (unsigned j = 0; j < result[i].length (); ++j)
 803         ne->append_op (result[i][j]);
 804       ret.safe_push (ne);
 805     }
 806
 807   if (!e->is_commutative)
 808     return ret;
 809
 810   for (unsigned i = 0; i < result.length (); ++i)
 811     {
 812       expr *ne = new expr (e);
 813       ne->is_commutative = false;
 814       // result[i].length () is 2 since e->operation is binary
 815       for (unsigned j = result[i].length (); j; --j)
 816         ne->append_op (result[i][j-1]);
 817       ret.safe_push (ne);
 818     }
 819
 820   return ret;
 821 }
 822
 823 /* Lower operations marked as commutative in the AST of S and push
 824    the resulting patterns to SIMPLIFIERS.  */
 825
 826 static void
 827 lower_commutative (simplify *s, vec<simplify *>& simplifiers)
 828 {
 829   vec<operand *> matchers = commutate (s->match);
 830   for (unsigned i = 0; i < matchers.length (); ++i)
 831     {
 832       simplify *ns = new simplify (s->kind, matchers[i], s->result,
 833                                    s->for_vec, s->capture_ids);
 834       simplifiers.safe_push (ns);
 835     }
 836 }
 837
 838 /* Strip conditional conversios using operator OPER from O and its
 839    children if STRIP, else replace them with an unconditional convert.  */
 840
 841 operand *
 842 lower_opt_convert (operand *o, enum tree_code oper,
 843                    enum tree_code to_oper, bool strip)
 844 {
 845   if (capture *c = dyn_cast<capture *> (o))
 846     {
 847       if (c->what)
 848         return new capture (c->location, c->where,
 849                             lower_opt_convert (c->what, oper, to_oper, strip));
 850       else
 851         return c;
 852     }
 853
 854   expr *e = dyn_cast<expr *> (o);
 855   if (!e)
 856     return o;
 857
 858   if (*e->operation == oper)
 859     {
 860       if (strip)
 861         return lower_opt_convert (e->ops[0], oper, to_oper, strip);
 862
 863       expr *ne = new expr (e);
 864       ne->operation = (to_oper == CONVERT_EXPR
 865                        ? get_operator ("CONVERT_EXPR")
 866                        : get_operator ("VIEW_CONVERT_EXPR"));
 867       ne->append_op (lower_opt_convert (e->ops[0], oper, to_oper, strip));
 868       return ne;
 869     }
 870
 871   expr *ne = new expr (e);
 872   for (unsigned i = 0; i < e->ops.length (); ++i)
 873     ne->append_op (lower_opt_convert (e->ops[i], oper, to_oper, strip));
 874
 875   return ne;
 876 }
 877
 878 /* Determine whether O or its children uses the conditional conversion
 879    operator OPER.  */
 880
 881 static bool
 882 has_opt_convert (operand *o, enum tree_code oper)
 883 {
 884   if (capture *c = dyn_cast<capture *> (o))
 885     {
 886       if (c->what)
 887         return has_opt_convert (c->what, oper);
 888       else
 889         return false;
 890     }
 891
 892   expr *e = dyn_cast<expr *> (o);
 893   if (!e)
 894     return false;
 895
 896   if (*e->operation == oper)
 897     return true;
 898
 899   for (unsigned i = 0; i < e->ops.length (); ++i)
 900     if (has_opt_convert (e->ops[i], oper))
 901       return true;
 902
 903   return false;
 904 }
 905
 906 /* Lower conditional convert operators in O, expanding it to a vector
 907    if required.  */
 908
 909 static vec<operand *>
 910 lower_opt_convert (operand *o)
 911 {
 912   vec<operand *> v1 = vNULL, v2;
 913
 914   v1.safe_push (o);
 915
 916   enum tree_code opers[]
 917     = { CONVERT0, CONVERT_EXPR,
 918         CONVERT1, CONVERT_EXPR,
 919         CONVERT2, CONVERT_EXPR,
 920         VIEW_CONVERT0, VIEW_CONVERT_EXPR,
 921         VIEW_CONVERT1, VIEW_CONVERT_EXPR,
 922         VIEW_CONVERT2, VIEW_CONVERT_EXPR };
 923
 924   /* Conditional converts are lowered to a pattern with the
 925      conversion and one without.  The three different conditional
 926      convert codes are lowered separately.  */
 927
 928   for (unsigned i = 0; i < sizeof (opers) / sizeof (enum tree_code); i += 2)
 929     {
 930       v2 = vNULL;
 931       for (unsigned j = 0; j < v1.length (); ++j)
 932         if (has_opt_convert (v1[j], opers[i]))
 933           {
 934             v2.safe_push (lower_opt_convert (v1[j],
 935                                              opers[i], opers[i+1], false));
 936             v2.safe_push (lower_opt_convert (v1[j],
 937                                              opers[i], opers[i+1], true));
 938           }
 939
 940       if (v2 != vNULL)
 941         {
 942           v1 = vNULL;
 943           for (unsigned j = 0; j < v2.length (); ++j)
 944             v1.safe_push (v2[j]);
 945         }
 946     }
 947
 948   return v1;
 949 }
 950
 951 /* Lower conditional convert operators in the AST of S and push
 952    the resulting multiple patterns to SIMPLIFIERS.  */
 953
 954 static void
 955 lower_opt_convert (simplify *s, vec<simplify *>& simplifiers)
 956 {
 957   vec<operand *> matchers = lower_opt_convert (s->match);
 958   for (unsigned i = 0; i < matchers.length (); ++i)
 959     {
 960       simplify *ns = new simplify (s->kind, matchers[i], s->result,
 961                                    s->for_vec, s->capture_ids);
 962       simplifiers.safe_push (ns);
 963     }
 964 }
 965
 966 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
 967    GENERIC and a GIMPLE variant.  */
 968
 969 static vec<operand *>
 970 lower_cond (operand *o)
 971 {
 972   vec<operand *> ro = vNULL;
 973
 974   if (capture *c = dyn_cast<capture *> (o))
 975     {
 976       if (c->what)
 977         {
 978           vec<operand *> lop = vNULL;
 979           lop = lower_cond (c->what);
 980
 981           for (unsigned i = 0; i < lop.length (); ++i)
 982             ro.safe_push (new capture (c->location, c->where, lop[i]));
 983           return ro;
 984         }
 985     }
 986
 987   expr *e = dyn_cast<expr *> (o);
 988   if (!e || e->ops.length () == 0)
 989     {
 990       ro.safe_push (o);
 991       return ro;
 992     }
 993
 994   vec< vec<operand *> > ops_vector = vNULL;
 995   for (unsigned i = 0; i < e->ops.length (); ++i)
 996     ops_vector.safe_push (lower_cond (e->ops[i]));
 997
 998   auto_vec< vec<operand *> > result;
 999   auto_vec<operand *> v (e->ops.length ());
1000   v.quick_grow_cleared (e->ops.length ());
1001   cartesian_product (ops_vector, result, v, 0);
1002
1003   for (unsigned i = 0; i < result.length (); ++i)
1004     {
1005       expr *ne = new expr (e);
1006       for (unsigned j = 0; j < result[i].length (); ++j)
1007         ne->append_op (result[i][j]);
1008       ro.safe_push (ne);
1009       /* If this is a COND with a captured expression or an
1010          expression with two operands then also match a GENERIC
1011          form on the compare.  */
1012       if ((*e->operation == COND_EXPR
1013            || *e->operation == VEC_COND_EXPR)
1014           && ((is_a <capture *> (e->ops[0])
1015                && as_a <capture *> (e->ops[0])->what
1016                && is_a <expr *> (as_a <capture *> (e->ops[0])->what)
1017                && as_a <expr *>
1018                     (as_a <capture *> (e->ops[0])->what)->ops.length () == 2)
1019               || (is_a <expr *> (e->ops[0])
1020                   && as_a <expr *> (e->ops[0])->ops.length () == 2)))
1021         {
1022           expr *ne = new expr (e);
1023           for (unsigned j = 0; j < result[i].length (); ++j)
1024             ne->append_op (result[i][j]);
1025           if (capture *c = dyn_cast <capture *> (ne->ops[0]))
1026             {
1027               expr *ocmp = as_a <expr *> (c->what);
1028               expr *cmp = new expr (ocmp);
1029               for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1030                 cmp->append_op (ocmp->ops[j]);
1031               cmp->is_generic = true;
1032               ne->ops[0] = new capture (c->location, c->where, cmp);
1033             }
1034           else
1035             {
1036               expr *ocmp = as_a <expr *> (ne->ops[0]);
1037               expr *cmp = new expr (ocmp);
1038               for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1039                 cmp->append_op (ocmp->ops[j]);
1040               cmp->is_generic = true;
1041               ne->ops[0] = cmp;
1042             }
1043           ro.safe_push (ne);
1044         }
1045     }
1046
1047   return ro;
1048 }
1049
1050 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1051    GENERIC and a GIMPLE variant.  */
1052
1053 static void
1054 lower_cond (simplify *s, vec<simplify *>& simplifiers)
1055 {
1056   vec<operand *> matchers = lower_cond (s->match);
1057   for (unsigned i = 0; i < matchers.length (); ++i)
1058     {
1059       simplify *ns = new simplify (s->kind, matchers[i], s->result,
1060                                    s->for_vec, s->capture_ids);
1061       simplifiers.safe_push (ns);
1062     }
1063 }
1064
1065 /* In AST operand O replace operator ID with operator WITH.  */
1066
1067 operand *
1068 replace_id (operand *o, user_id *id, id_base *with)
1069 {
1070   /* Deep-copy captures and expressions, replacing operations as
1071      needed.  */
1072   if (capture *c = dyn_cast<capture *> (o))
1073     {
1074       if (!c->what)
1075         return c;
1076       return new capture (c->location, c->where,
1077                           replace_id (c->what, id, with));
1078     }
1079   else if (expr *e = dyn_cast<expr *> (o))
1080     {
1081       expr *ne = new expr (e);
1082       if (e->operation == id)
1083         ne->operation = with;
1084       for (unsigned i = 0; i < e->ops.length (); ++i)
1085         ne->append_op (replace_id (e->ops[i], id, with));
1086       return ne;
1087     }
1088   else if (with_expr *w = dyn_cast <with_expr *> (o))
1089     {
1090       with_expr *nw = new with_expr (w->location);
1091       nw->with = as_a <c_expr *> (replace_id (w->with, id, with));
1092       nw->subexpr = replace_id (w->subexpr, id, with);
1093       return nw;
1094     }
1095   else if (if_expr *ife = dyn_cast <if_expr *> (o))
1096     {
1097       if_expr *nife = new if_expr (ife->location);
1098       nife->cond = as_a <c_expr *> (replace_id (ife->cond, id, with));
1099       nife->trueexpr = replace_id (ife->trueexpr, id, with);
1100       if (ife->falseexpr)
1101         nife->falseexpr = replace_id (ife->falseexpr, id, with);
1102       return nife;
1103     }
1104
1105   /* For c_expr we simply record a string replacement table which is
1106      applied at code-generation time.  */
1107   if (c_expr *ce = dyn_cast<c_expr *> (o))
1108     {
1109       vec<c_expr::id_tab> ids = ce->ids.copy ();
1110       ids.safe_push (c_expr::id_tab (id->id, with->id));
1111       return new c_expr (ce->r, ce->location,
1112                          ce->code, ce->nr_stmts, ids, ce->capture_ids);
1113     }
1114
1115   return o;
1116 }
1117
1118 /* Lower recorded fors for SIN and output to SIMPLIFIERS.  */
1119
1120 static void
1121 lower_for (simplify *sin, vec<simplify *>& simplifiers)
1122 {
1123   vec<vec<user_id *> >& for_vec = sin->for_vec;
1124   unsigned worklist_start = 0;
1125   auto_vec<simplify *> worklist;
1126   worklist.safe_push (sin);
1127
1128   /* Lower each recorded for separately, operating on the
1129      set of simplifiers created by the previous one.
1130      Lower inner-to-outer so inner for substitutes can refer
1131      to operators replaced by outer fors.  */
1132   for (int fi = for_vec.length () - 1; fi >= 0; --fi)
1133     {
1134       vec<user_id *>& ids = for_vec[fi];
1135       unsigned n_ids = ids.length ();
1136       unsigned max_n_opers = 0;
1137       for (unsigned i = 0; i < n_ids; ++i)
1138         if (ids[i]->substitutes.length () > max_n_opers)
1139           max_n_opers = ids[i]->substitutes.length ();
1140
1141       unsigned worklist_end = worklist.length ();
1142       for (unsigned si = worklist_start; si < worklist_end; ++si)
1143         {
1144           simplify *s = worklist[si];
1145           for (unsigned j = 0; j < max_n_opers; ++j)
1146             {
1147               operand *match_op = s->match;
1148               operand *result_op = s->result;
1149               for (unsigned i = 0; i < n_ids; ++i)
1150                 {
1151                   user_id *id = ids[i];
1152                   id_base *oper = id->substitutes[j % id->substitutes.length ()];
1153                   match_op = replace_id (match_op, id, oper);
1154                   if (result_op)
1155                     result_op = replace_id (result_op, id, oper);
1156                 }
1157               simplify *ns = new simplify (s->kind, match_op, result_op,
1158                                            vNULL, s->capture_ids);
1159               worklist.safe_push (ns);
1160             }
1161         }
1162       worklist_start = worklist_end;
1163     }
1164
1165   /* Copy out the result from the last for lowering.  */
1166   for (unsigned i = worklist_start; i < worklist.length (); ++i)
1167     simplifiers.safe_push (worklist[i]);
1168 }
1169
1170 /* Lower the AST for everything in SIMPLIFIERS.  */
1171
1172 static void
1173 lower (vec<simplify *>& simplifiers, bool gimple)
1174 {
1175   auto_vec<simplify *> out_simplifiers;
1176   for (unsigned i = 0; i < simplifiers.length (); ++i)
1177     lower_opt_convert (simplifiers[i], out_simplifiers);
1178
1179   simplifiers.truncate (0);
1180   for (unsigned i = 0; i < out_simplifiers.length (); ++i)
1181     lower_commutative (out_simplifiers[i], simplifiers);
1182
1183   out_simplifiers.truncate (0);
1184   if (gimple)
1185     for (unsigned i = 0; i < simplifiers.length (); ++i)
1186       lower_cond (simplifiers[i], out_simplifiers);
1187   else
1188     out_simplifiers.safe_splice (simplifiers);
1189
1190
1191   simplifiers.truncate (0);
1192   for (unsigned i = 0; i < out_simplifiers.length (); ++i)
1193     lower_for (out_simplifiers[i], simplifiers);
1194 }
1195
1196
1197
1198
1199 /* The decision tree built for generating GIMPLE and GENERIC pattern
1200    matching code.  It represents the 'match' expression of all
1201    simplifies and has those as its leafs.  */
1202
1203 /* Decision tree base class, used for DT_TRUE and DT_NODE.  */
1204
1205 struct dt_node
1206 {
1207   enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
1208
1209   enum dt_type type;
1210   unsigned level;
1211   vec<dt_node *> kids;
1212
1213   dt_node (enum dt_type type_): type (type_), level (0), kids (vNULL) {}
1214
1215   dt_node *append_node (dt_node *);
1216   dt_node *append_op (operand *, dt_node *parent = 0, unsigned pos = 0);
1217   dt_node *append_true_op (dt_node *parent = 0, unsigned pos = 0);
1218   dt_node *append_match_op (dt_operand *, dt_node *parent = 0, unsigned pos = 0);
1219   dt_node *append_simplify (simplify *, unsigned, dt_operand **);
1220
1221   virtual void gen (FILE *, int, bool) {}
1222
1223   void gen_kids (FILE *, int, bool);
1224   void gen_kids_1 (FILE *, int, bool,
1225                    vec<dt_operand *>, vec<dt_operand *>, vec<dt_operand *>,
1226                    vec<dt_operand *>, vec<dt_operand *>, vec<dt_node *>);
1227 };
1228
1229 /* Generic decision tree node used for DT_OPERAND and DT_MATCH.  */
1230
1231 struct dt_operand : public dt_node
1232 {
1233   operand *op;
1234   dt_operand *match_dop;
1235   dt_operand *parent;
1236   unsigned pos;
1237
1238   dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_,
1239               dt_operand *parent_ = 0, unsigned pos_ = 0)
1240       : dt_node (type), op (op_), match_dop (match_dop_),
1241       parent (parent_), pos (pos_) {}
1242
1243   void gen (FILE *, int, bool);
1244   unsigned gen_predicate (FILE *, int, const char *, bool);
1245   unsigned gen_match_op (FILE *, int, const char *);
1246
1247   unsigned gen_gimple_expr (FILE *, int);
1248   unsigned gen_generic_expr (FILE *, int, const char *);
1249
1250   char *get_name (char *);
1251   void gen_opname (char *, unsigned);
1252 };
1253
1254 /* Leaf node of the decision tree, used for DT_SIMPLIFY.  */
1255
1256 struct dt_simplify : public dt_node
1257 {
1258   simplify *s;
1259   unsigned pattern_no;
1260   dt_operand **indexes;
1261
1262   dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
1263         : dt_node (DT_SIMPLIFY), s (s_), pattern_no (pattern_no_),
1264           indexes (indexes_)  {}
1265
1266   void gen_1 (FILE *, int, bool, operand *);
1267   void gen (FILE *f, int, bool);
1268 };
1269
1270 template<>
1271 template<>
1272 inline bool
1273 is_a_helper <dt_operand *>::test (dt_node *n)
1274 {
1275   return (n->type == dt_node::DT_OPERAND
1276           || n->type == dt_node::DT_MATCH);
1277 }
1278
1279 /* A container for the actual decision tree.  */
1280
1281 struct decision_tree
1282 {
1283   dt_node *root;
1284
1285   void insert (struct simplify *, unsigned);
1286   void gen_gimple (FILE *f = stderr);
1287   void gen_generic (FILE *f = stderr);
1288   void print (FILE *f = stderr);
1289
1290   decision_tree () { root = new dt_node (dt_node::DT_NODE); }
1291
1292   static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes,
1293                                   unsigned pos = 0, dt_node *parent = 0);
1294   static dt_node *find_node (vec<dt_node *>&, dt_node *);
1295   static bool cmp_node (dt_node *, dt_node *);
1296   static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
1297 };
1298
1299 /* Compare two AST operands O1 and O2 and return true if they are equal.  */
1300
1301 bool
1302 cmp_operand (operand *o1, operand *o2)
1303 {
1304   if (!o1 || !o2 || o1->type != o2->type)
1305     return false;
1306
1307   if (o1->type == operand::OP_PREDICATE)
1308     {
1309       predicate *p1 = as_a<predicate *>(o1);
1310       predicate *p2 = as_a<predicate *>(o2);
1311       return p1->p == p2->p;
1312     }
1313   else if (o1->type == operand::OP_EXPR)
1314     {
1315       expr *e1 = static_cast<expr *>(o1);
1316       expr *e2 = static_cast<expr *>(o2);
1317       return (e1->operation == e2->operation
1318               && e1->is_generic == e2->is_generic);
1319     }
1320   else
1321     return false;
1322 }
1323
1324 /* Compare two decision tree nodes N1 and N2 and return true if they
1325    are equal.  */
1326
1327 bool
1328 decision_tree::cmp_node (dt_node *n1, dt_node *n2)
1329 {
1330   if (!n1 || !n2 || n1->type != n2->type)
1331     return false;
1332
1333   if (n1 == n2)
1334     return true;
1335
1336   if (n1->type == dt_node::DT_TRUE)
1337     return false;
1338
1339   if (n1->type == dt_node::DT_OPERAND)
1340     return cmp_operand ((as_a<dt_operand *> (n1))->op,
1341                         (as_a<dt_operand *> (n2))->op);
1342   else if (n1->type == dt_node::DT_MATCH)
1343     return ((as_a<dt_operand *> (n1))->match_dop
1344             == (as_a<dt_operand *> (n2))->match_dop);
1345   return false;
1346 }
1347
1348 /* Search OPS for a decision tree node like P and return it if found.  */
1349
1350 dt_node *
1351 decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
1352 {
1353   /* We can merge adjacent DT_TRUE.  */
1354   if (p->type == dt_node::DT_TRUE
1355       && !ops.is_empty ()
1356       && ops.last ()->type == dt_node::DT_TRUE)
1357     return ops.last ();
1358   for (int i = ops.length () - 1; i >= 0; --i)
1359     {
1360       /* But we can't merge across DT_TRUE nodes as they serve as
1361          pattern order barriers to make sure that patterns apply
1362          in order of appearance in case multiple matches are possible.  */
1363       if (ops[i]->type == dt_node::DT_TRUE)
1364         return NULL;
1365       if (decision_tree::cmp_node (ops[i], p))
1366         return ops[i];
1367     }
1368   return NULL;
1369 }
1370
1371 /* Append N to the decision tree if it there is not already an existing
1372    identical child.  */
1373
1374 dt_node *
1375 dt_node::append_node (dt_node *n)
1376 {
1377   dt_node *kid;
1378
1379   kid = decision_tree::find_node (kids, n);
1380   if (kid)
1381     return kid;
1382
1383   kids.safe_push (n);
1384   n->level = this->level + 1;
1385
1386   return n;
1387 }
1388
1389 /* Append OP to the decision tree.  */
1390
1391 dt_node *
1392 dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
1393 {
1394   dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1395   dt_operand *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos);
1396   return append_node (n);
1397 }
1398
1399 /* Append a DT_TRUE decision tree node.  */
1400
1401 dt_node *
1402 dt_node::append_true_op (dt_node *parent, unsigned pos)
1403 {
1404   dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1405   dt_operand *n = new dt_operand (DT_TRUE, 0, 0, parent_, pos);
1406   return append_node (n);
1407 }
1408
1409 /* Append a DT_MATCH decision tree node.  */
1410
1411 dt_node *
1412 dt_node::append_match_op (dt_operand *match_dop, dt_node *parent, unsigned pos)
1413 {
1414   dt_operand *parent_ = as_a<dt_operand *> (parent);
1415   dt_operand *n = new dt_operand (DT_MATCH, 0, match_dop, parent_, pos);
1416   return append_node (n);
1417 }
1418
1419 /* Append S to the decision tree.  */
1420
1421 dt_node *
1422 dt_node::append_simplify (simplify *s, unsigned pattern_no,
1423                           dt_operand **indexes)
1424 {
1425   dt_simplify *n = new dt_simplify (s, pattern_no, indexes);
1426   return append_node (n);
1427 }
1428
1429 /* Insert O into the decision tree and return the decision tree node found
1430    or created.  */
1431
1432 dt_node *
1433 decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
1434                                unsigned pos, dt_node *parent)
1435 {
1436   dt_node *q, *elm = 0;
1437
1438   if (capture *c = dyn_cast<capture *> (o))
1439     {
1440       unsigned capt_index = c->where;
1441
1442       if (indexes[capt_index] == 0)
1443         {
1444           if (c->what)
1445             q = insert_operand (p, c->what, indexes, pos, parent);
1446           else
1447             {
1448               q = elm = p->append_true_op (parent, pos);
1449               goto at_assert_elm;
1450             }
1451           // get to the last capture
1452           for (operand *what = c->what;
1453                what && is_a<capture *> (what);
1454                c = as_a<capture *> (what), what = c->what)
1455             ;
1456
1457           if (!c->what)
1458             {
1459               unsigned cc_index = c->where;
1460               dt_operand *match_op = indexes[cc_index];
1461
1462               dt_operand temp (dt_node::DT_TRUE, 0, 0);
1463               elm = decision_tree::find_node (p->kids, &temp);
1464
1465               if (elm == 0)
1466                 {
1467                   dt_operand temp (dt_node::DT_MATCH, 0, match_op);
1468                   elm = decision_tree::find_node (p->kids, &temp);
1469                 }
1470             }
1471           else
1472             {
1473               dt_operand temp (dt_node::DT_OPERAND, c->what, 0);
1474               elm = decision_tree::find_node (p->kids, &temp);
1475             }
1476
1477 at_assert_elm:
1478           gcc_assert (elm->type == dt_node::DT_TRUE
1479                       || elm->type == dt_node::DT_OPERAND
1480                       || elm->type == dt_node::DT_MATCH);
1481           indexes[capt_index] = static_cast<dt_operand *> (elm);
1482           return q;
1483         }
1484       else
1485         {
1486           p = p->append_match_op (indexes[capt_index], parent, pos);
1487           if (c->what)
1488             return insert_operand (p, c->what, indexes, 0, p);
1489           else
1490             return p;
1491         }
1492     }
1493   p = p->append_op (o, parent, pos);
1494   q = p;
1495
1496   if (expr *e = dyn_cast <expr *>(o))
1497     {
1498       for (unsigned i = 0; i < e->ops.length (); ++i)
1499         q = decision_tree::insert_operand (q, e->ops[i], indexes, i, p);
1500     }
1501
1502   return q;
1503 }
1504
1505 /* Insert S into the decision tree.  */
1506
1507 void
1508 decision_tree::insert (struct simplify *s, unsigned pattern_no)
1509 {
1510   dt_operand **indexes = XCNEWVEC (dt_operand *, s->capture_max + 1);
1511   dt_node *p = decision_tree::insert_operand (root, s->match, indexes);
1512   p->append_simplify (s, pattern_no, indexes);
1513 }
1514
1515 /* Debug functions to dump the decision tree.  */
1516
1517 DEBUG_FUNCTION void
1518 decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
1519 {
1520   if (p->type == dt_node::DT_NODE)
1521     fprintf (f, "root");
1522   else
1523     {
1524       fprintf (f, "|");
1525       for (unsigned i = 0; i < indent; i++)
1526         fprintf (f, "-");
1527
1528       if (p->type == dt_node::DT_OPERAND)
1529         {
1530           dt_operand *dop = static_cast<dt_operand *>(p);
1531           print_operand (dop->op, f, true);
1532         }
1533       else if (p->type == dt_node::DT_TRUE)
1534         fprintf (f, "true");
1535       else if (p->type == dt_node::DT_MATCH)
1536         fprintf (f, "match (%p)", (void *)((as_a<dt_operand *>(p))->match_dop));
1537       else if (p->type == dt_node::DT_SIMPLIFY)
1538         {
1539           dt_simplify *s = static_cast<dt_simplify *> (p);
1540           fprintf (f, "simplify_%u { ", s->pattern_no);
1541           for (int i = 0; i <= s->s->capture_max; ++i)
1542             fprintf (f, "%p, ", (void *) s->indexes[i]);
1543           fprintf (f, " } ");
1544         }
1545     }
1546
1547   fprintf (stderr, " (%p), %u, %u\n", (void *) p, p->level, p->kids.length ());
1548
1549   for (unsigned i = 0; i < p->kids.length (); ++i)
1550     decision_tree::print_node (p->kids[i], f, indent + 2);
1551 }
1552
1553 DEBUG_FUNCTION void
1554 decision_tree::print (FILE *f)
1555 {
1556   return decision_tree::print_node (root, f);
1557 }
1558
1559
1560 /* For GENERIC we have to take care of wrapping multiple-used
1561    expressions with side-effects in save_expr and preserve side-effects
1562    of expressions with omit_one_operand.  Analyze captures in
1563    match, result and with expressions and perform early-outs
1564    on the outermost match expression operands for cases we cannot
1565    handle.  */
1566
1567 struct capture_info
1568 {
1569   capture_info (simplify *s, operand *);
1570   void walk_match (operand *o, unsigned toplevel_arg, bool, bool);
1571   bool walk_result (operand *o, bool, operand *);
1572   void walk_c_expr (c_expr *);
1573
1574   struct cinfo
1575     {
1576       bool expr_p;
1577       bool cse_p;
1578       bool force_no_side_effects_p;
1579       bool force_single_use;
1580       bool cond_expr_cond_p;
1581       unsigned long toplevel_msk;
1582       int result_use_count;
1583     };
1584
1585   auto_vec<cinfo> info;
1586   unsigned long force_no_side_effects;
1587 };
1588
1589 /* Analyze captures in S.  */
1590
1591 capture_info::capture_info (simplify *s, operand *result)
1592 {
1593   expr *e;
1594   if (s->kind == simplify::MATCH)
1595     {
1596       force_no_side_effects = -1;
1597       return;
1598     }
1599
1600   force_no_side_effects = 0;
1601   info.safe_grow_cleared (s->capture_max + 1);
1602   e = as_a <expr *> (s->match);
1603   for (unsigned i = 0; i < e->ops.length (); ++i)
1604     walk_match (e->ops[i], i,
1605                 (i != 0 && *e->operation == COND_EXPR)
1606                 || *e->operation == TRUTH_ANDIF_EXPR
1607                 || *e->operation == TRUTH_ORIF_EXPR,
1608                 i == 0
1609                 && (*e->operation == COND_EXPR
1610                     || *e->operation == VEC_COND_EXPR));
1611
1612   walk_result (s->result, false, result);
1613 }
1614
1615 /* Analyze captures in the match expression piece O.  */
1616
1617 void
1618 capture_info::walk_match (operand *o, unsigned toplevel_arg,
1619                           bool conditional_p, bool cond_expr_cond_p)
1620 {
1621   if (capture *c = dyn_cast <capture *> (o))
1622     {
1623       unsigned where = c->where;
1624       info[where].toplevel_msk |= 1 << toplevel_arg;
1625       info[where].force_no_side_effects_p |= conditional_p;
1626       info[where].cond_expr_cond_p |= cond_expr_cond_p;
1627       if (!c->what)
1628         return;
1629       /* Recurse to exprs and captures.  */
1630       if (is_a <capture *> (c->what)
1631           || is_a <expr *> (c->what))
1632         walk_match (c->what, toplevel_arg, conditional_p, false);
1633       /* We need to look past multiple captures to find a captured
1634          expression as with conditional converts two captures
1635          can be collapsed onto the same expression.  */
1636       while (c->what && is_a <capture *> (c->what))
1637         c = as_a <capture *> (c->what);
1638       /* Mark expr (non-leaf) captures and forced single-use exprs.  */
1639       expr *e;
1640       if (c->what
1641           && (e = dyn_cast <expr *> (c->what)))
1642         {
1643           info[where].expr_p = true;
1644           info[where].force_single_use |= e->force_single_use;
1645         }
1646     }
1647   else if (expr *e = dyn_cast <expr *> (o))
1648     {
1649       for (unsigned i = 0; i < e->ops.length (); ++i)
1650         {
1651           bool cond_p = conditional_p;
1652           bool cond_expr_cond_p = false;
1653           if (i != 0 && *e->operation == COND_EXPR)
1654             cond_p = true;
1655           else if (*e->operation == TRUTH_ANDIF_EXPR
1656                    || *e->operation == TRUTH_ORIF_EXPR)
1657             cond_p = true;
1658           if (i == 0
1659               && (*e->operation == COND_EXPR
1660                   || *e->operation == VEC_COND_EXPR))
1661             cond_expr_cond_p = true;
1662           walk_match (e->ops[i], toplevel_arg, cond_p, cond_expr_cond_p);
1663         }
1664     }
1665   else if (is_a <predicate *> (o))
1666     {
1667       /* Mark non-captured leafs toplevel arg for checking.  */
1668       force_no_side_effects |= 1 << toplevel_arg;
1669     }
1670   else
1671     gcc_unreachable ();
1672 }
1673
1674 /* Analyze captures in the result expression piece O.  Return true
1675    if RESULT was visited in one of the children.  Only visit
1676    non-if/with children if they are rooted on RESULT.  */
1677
1678 bool
1679 capture_info::walk_result (operand *o, bool conditional_p, operand *result)
1680 {
1681   if (capture *c = dyn_cast <capture *> (o))
1682     {
1683       info[c->where].result_use_count++;
1684       /* If we substitute an expression capture we don't know
1685          which captures this will end up using (well, we don't
1686          compute that).  Force the uses to be side-effect free
1687          which means forcing the toplevels that reach the
1688          expression side-effect free.  */
1689       if (info[c->where].expr_p)
1690         force_no_side_effects |= info[c->where].toplevel_msk;
1691       /* Mark CSE capture uses as forced to have no side-effects. */
1692       if (c->what
1693           && is_a <expr *> (c->what))
1694         {
1695           info[c->where].cse_p = true;
1696           walk_result (c->what, true, result);
1697         }
1698     }
1699   else if (expr *e = dyn_cast <expr *> (o))
1700     {
1701       for (unsigned i = 0; i < e->ops.length (); ++i)
1702         {
1703           bool cond_p = conditional_p;
1704           if (i != 0 && *e->operation == COND_EXPR)
1705             cond_p = true;
1706           else if (*e->operation == TRUTH_ANDIF_EXPR
1707                    || *e->operation == TRUTH_ORIF_EXPR)
1708             cond_p = true;
1709           walk_result (e->ops[i], cond_p, result);
1710         }
1711     }
1712   else if (if_expr *e = dyn_cast <if_expr *> (o))
1713     {
1714       /* 'if' conditions should be all fine.  */
1715       if (e->trueexpr == result)
1716         {
1717           walk_result (e->trueexpr, false, result);
1718           return true;
1719         }
1720       if (e->falseexpr == result)
1721         {
1722           walk_result (e->falseexpr, false, result);
1723           return true;
1724         }
1725       bool res = false;
1726       if (is_a <if_expr *> (e->trueexpr)
1727           || is_a <with_expr *> (e->trueexpr))
1728         res |= walk_result (e->trueexpr, false, result);
1729       if (e->falseexpr
1730           && (is_a <if_expr *> (e->falseexpr)
1731               || is_a <with_expr *> (e->falseexpr)))
1732         res |= walk_result (e->falseexpr, false, result);
1733       return res;
1734     }
1735   else if (with_expr *e = dyn_cast <with_expr *> (o))
1736     {
1737       bool res = (e->subexpr == result);
1738       if (res
1739           || is_a <if_expr *> (e->subexpr)
1740           || is_a <with_expr *> (e->subexpr))
1741         res |= walk_result (e->subexpr, false, result);
1742       if (res)
1743         walk_c_expr (e->with);
1744       return res;
1745     }
1746   else if (c_expr *e = dyn_cast <c_expr *> (o))
1747     walk_c_expr (e);
1748   else
1749     gcc_unreachable ();
1750
1751   return false;
1752 }
1753
1754 /* Look for captures in the C expr E.  */
1755
1756 void
1757 capture_info::walk_c_expr (c_expr *e)
1758 {
1759   /* Give up for C exprs mentioning captures not inside TREE_TYPE ().  */
1760   unsigned p_depth = 0;
1761   for (unsigned i = 0; i < e->code.length (); ++i)
1762     {
1763       const cpp_token *t = &e->code[i];
1764       const cpp_token *n = i < e->code.length () - 1 ? &e->code[i+1] : NULL;
1765       if (t->type == CPP_NAME
1766           && strcmp ((const char *)CPP_HASHNODE
1767                        (t->val.node.node)->ident.str, "TREE_TYPE") == 0
1768           && n->type == CPP_OPEN_PAREN)
1769         p_depth++;
1770       else if (t->type == CPP_CLOSE_PAREN
1771                && p_depth > 0)
1772         p_depth--;
1773       else if (p_depth == 0
1774                && t->type == CPP_ATSIGN
1775                && (n->type == CPP_NUMBER
1776                    || n->type == CPP_NAME)
1777                && !(n->flags & PREV_WHITE))
1778         {
1779           const char *id;
1780           if (n->type == CPP_NUMBER)
1781             id = (const char *)n->val.str.text;
1782           else
1783             id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
1784           info[*e->capture_ids->get(id)].force_no_side_effects_p = true;
1785         }
1786     }
1787 }
1788
1789
1790 /* Code generation off the decision tree and the refered AST nodes.  */
1791
1792 bool
1793 is_conversion (id_base *op)
1794 {
1795   return (*op == CONVERT_EXPR
1796           || *op == NOP_EXPR
1797           || *op == FLOAT_EXPR
1798           || *op == FIX_TRUNC_EXPR
1799           || *op == VIEW_CONVERT_EXPR);
1800 }
1801
1802 /* Get the type to be used for generating operands of OP from the
1803    various sources.  */
1804
1805 static const char *
1806 get_operand_type (id_base *op, const char *in_type,
1807                   const char *expr_type,
1808                   const char *other_oprnd_type)
1809 {
1810   /* Generally operands whose type does not match the type of the
1811      expression generated need to know their types but match and
1812      thus can fall back to 'other_oprnd_type'.  */
1813   if (is_conversion (op))
1814     return other_oprnd_type;
1815   else if (*op == REALPART_EXPR
1816            || *op == IMAGPART_EXPR)
1817     return other_oprnd_type;
1818   else if (is_a <operator_id *> (op)
1819            && strcmp (as_a <operator_id *> (op)->tcc, "tcc_comparison") == 0)
1820     return other_oprnd_type;
1821   else
1822     {
1823       /* Otherwise all types should match - choose one in order of
1824          preference.  */
1825       if (expr_type)
1826         return expr_type;
1827       else if (in_type)
1828         return in_type;
1829       else
1830         return other_oprnd_type;
1831     }
1832 }
1833
1834 /* Generate transform code for an expression.  */
1835
1836 void
1837 expr::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
1838                      int depth, const char *in_type, capture_info *cinfo,
1839                      dt_operand **indexes, bool)
1840 {
1841   bool conversion_p = is_conversion (operation);
1842   const char *type = expr_type;
1843   char optype[64];
1844   if (type)
1845     /* If there was a type specification in the pattern use it.  */
1846     ;
1847   else if (conversion_p)
1848     /* For conversions we need to build the expression using the
1849        outer type passed in.  */
1850     type = in_type;
1851   else if (*operation == REALPART_EXPR
1852            || *operation == IMAGPART_EXPR)
1853     {
1854       /* __real and __imag use the component type of its operand.  */
1855       sprintf (optype, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth);
1856       type = optype;
1857     }
1858   else if (is_a <operator_id *> (operation)
1859            && !strcmp (as_a <operator_id *> (operation)->tcc, "tcc_comparison"))
1860     {
1861       /* comparisons use boolean_type_node (or what gets in), but
1862          their operands need to figure out the types themselves.  */
1863       sprintf (optype, "boolean_type_node");
1864       type = optype;
1865     }
1866   else if (*operation == COND_EXPR
1867            || *operation == VEC_COND_EXPR)
1868     {
1869       /* Conditions are of the same type as their first alternative.  */
1870       sprintf (optype, "TREE_TYPE (ops%d[1])", depth);
1871       type = optype;
1872     }
1873   else
1874     {
1875       /* Other operations are of the same type as their first operand.  */
1876       sprintf (optype, "TREE_TYPE (ops%d[0])", depth);
1877       type = optype;
1878     }
1879   if (!type)
1880     fatal ("two conversions in a row");
1881
1882   fprintf_indent (f, indent, "{\n");
1883   indent += 2;
1884   fprintf_indent (f, indent, "tree ops%d[%u], res;\n", depth, ops.length ());
1885   char op0type[64];
1886   snprintf (op0type, 64, "TREE_TYPE (ops%d[0])", depth);
1887   for (unsigned i = 0; i < ops.length (); ++i)
1888     {
1889       char dest[32];
1890       snprintf (dest, 32, "ops%d[%u]", depth, i);
1891       const char *optype
1892         = get_operand_type (operation, in_type, expr_type,
1893                             i == 0 ? NULL : op0type);
1894       ops[i]->gen_transform (f, indent, dest, gimple, depth + 1, optype,
1895                              cinfo, indexes,
1896                              ((!(*operation == COND_EXPR)
1897                                && !(*operation == VEC_COND_EXPR))
1898                               || i != 0));
1899     }
1900
1901   const char *opr;
1902   if (*operation == CONVERT_EXPR)
1903     opr = "NOP_EXPR";
1904   else
1905     opr = operation->id;
1906
1907   if (gimple)
1908     {
1909       if (*operation == CONVERT_EXPR)
1910         {
1911           fprintf_indent (f, indent,
1912                           "if (%s != TREE_TYPE (ops%d[0])\n",
1913                           type, depth);
1914           fprintf_indent (f, indent,
1915                           "    && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
1916                           type, depth);
1917           fprintf_indent (f, indent + 2, "{\n");
1918           indent += 4;
1919         }
1920       /* ???  Building a stmt can fail for various reasons here, seq being
1921          NULL or the stmt referencing SSA names occuring in abnormal PHIs.
1922          So if we fail here we should continue matching other patterns.  */
1923       fprintf_indent (f, indent, "code_helper tem_code = %s;\n", opr);
1924       fprintf_indent (f, indent, "tree tem_ops[3] = { ");
1925       for (unsigned i = 0; i < ops.length (); ++i)
1926         fprintf (f, "ops%d[%u]%s", depth, i,
1927                  i == ops.length () - 1 ? " };\n" : ", ");
1928       fprintf_indent (f, indent,
1929                       "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
1930                       ops.length (), type);
1931       fprintf_indent (f, indent,
1932                       "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
1933                       type);
1934       fprintf_indent (f, indent,
1935                       "if (!res) return false;\n");
1936       if (*operation == CONVERT_EXPR)
1937         {
1938           indent -= 4;
1939           fprintf_indent (f, indent, "  }\n");
1940           fprintf_indent (f, indent, "else\n");
1941           fprintf_indent (f, indent, "  res = ops%d[0];\n", depth);
1942         }
1943     }
1944   else
1945     {
1946       if (*operation == CONVERT_EXPR)
1947         {
1948           fprintf_indent (f, indent, "if (TREE_TYPE (ops%d[0]) != %s)\n",
1949                           depth, type);
1950           indent += 2;
1951         }
1952       if (operation->kind == id_base::CODE)
1953         fprintf_indent (f, indent, "res = fold_build%d_loc (loc, %s, %s",
1954                         ops.length(), opr, type);
1955       else
1956         fprintf_indent (f, indent, "res = build_call_expr_loc (loc, "
1957                         "builtin_decl_implicit (%s), %d", opr, ops.length());
1958       for (unsigned i = 0; i < ops.length (); ++i)
1959         fprintf (f, ", ops%d[%u]", depth, i);
1960       fprintf (f, ");\n");
1961       if (*operation == CONVERT_EXPR)
1962         {
1963           indent -= 2;
1964           fprintf_indent (f, indent, "else\n");
1965           fprintf_indent (f, indent, "  res = ops%d[0];\n", depth);
1966         }
1967     }
1968   fprintf_indent (f, indent, "%s = res;\n", dest);
1969   indent -= 2;
1970   fprintf_indent (f, indent, "}\n");
1971 }
1972
1973 /* Generate code for a c_expr which is either the expression inside
1974    an if statement or a sequence of statements which computes a
1975    result to be stored to DEST.  */
1976
1977 void
1978 c_expr::gen_transform (FILE *f, int indent, const char *dest,
1979                        bool, int, const char *, capture_info *,
1980                        dt_operand **, bool)
1981 {
1982   if (dest && nr_stmts == 1)
1983     fprintf_indent (f, indent, "%s = ", dest);
1984
1985   unsigned stmt_nr = 1;
1986   for (unsigned i = 0; i < code.length (); ++i)
1987     {
1988       const cpp_token *token = &code[i];
1989
1990       /* Replace captures for code-gen.  */
1991       if (token->type == CPP_ATSIGN)
1992         {
1993           const cpp_token *n = &code[i+1];
1994           if ((n->type == CPP_NUMBER
1995                || n->type == CPP_NAME)
1996               && !(n->flags & PREV_WHITE))
1997             {
1998               if (token->flags & PREV_WHITE)
1999                 fputc (' ', f);
2000               const char *id;
2001               if (n->type == CPP_NUMBER)
2002                 id = (const char *)n->val.str.text;
2003               else
2004                 id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2005               fprintf (f, "captures[%u]", *capture_ids->get(id));
2006               ++i;
2007               continue;
2008             }
2009         }
2010
2011       if (token->flags & PREV_WHITE)
2012         fputc (' ', f);
2013
2014       if (token->type == CPP_NAME)
2015         {
2016           const char *id = (const char *) NODE_NAME (token->val.node.node);
2017           unsigned j;
2018           for (j = 0; j < ids.length (); ++j)
2019             {
2020             if (strcmp (id, ids[j].id) == 0)
2021               {
2022                 fprintf (f, "%s", ids[j].oper);
2023                 break;
2024               }
2025             }
2026           if (j < ids.length ())
2027             continue;
2028         }
2029
2030       /* Output the token as string.  */
2031       char *tk = (char *)cpp_token_as_text (r, token);
2032       fputs (tk, f);
2033
2034       if (token->type == CPP_SEMICOLON)
2035         {
2036           stmt_nr++;
2037           fputc ('\n', f);
2038           if (dest && stmt_nr == nr_stmts)
2039             fprintf_indent (f, indent, "%s = ", dest);
2040         }
2041     }
2042 }
2043
2044 /* Generate transform code for a capture.  */
2045
2046 void
2047 capture::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2048                         int depth, const char *in_type, capture_info *cinfo,
2049                         dt_operand **indexes, bool expand_compares)
2050 {
2051   if (what && is_a<expr *> (what))
2052     {
2053       if (indexes[where] == 0)
2054         {
2055           char buf[20];
2056           sprintf (buf, "captures[%u]", where);
2057           what->gen_transform (f, indent, buf, gimple, depth, in_type,
2058                                cinfo, NULL);
2059         }
2060     }
2061
2062   fprintf_indent (f, indent, "%s = captures[%u];\n", dest, where);
2063
2064   /* ???  Stupid tcc_comparison GENERIC trees in COND_EXPRs.  Deal
2065      with substituting a capture of that.
2066      ???  Returning false here will also not allow any other patterns
2067      to match.  */
2068   if (gimple && expand_compares
2069       && cinfo->info[where].cond_expr_cond_p)
2070     {
2071       fprintf_indent (f, indent, "if (COMPARISON_CLASS_P (%s))\n", dest);
2072       fprintf_indent (f, indent, "  {\n");
2073       fprintf_indent (f, indent, "    if (!seq) return false;\n");
2074       fprintf_indent (f, indent, "    %s = gimple_build (seq, TREE_CODE (%s),"
2075                                  " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2076                                  " TREE_OPERAND (%s, 1));\n",
2077                                  dest, dest, dest, dest, dest);
2078       fprintf_indent (f, indent, "  }\n");
2079     }
2080 }
2081
2082 /* Return the name of the operand representing the decision tree node.
2083    Use NAME as space to generate it.  */
2084
2085 char *
2086 dt_operand::get_name (char *name)
2087 {
2088   if (!parent)
2089     sprintf (name, "t");
2090   else if (parent->level == 1)
2091     sprintf (name, "op%u", pos);
2092   else if (parent->type == dt_node::DT_MATCH)
2093     return parent->get_name (name);
2094   else
2095     sprintf (name, "o%u%u", parent->level, pos);
2096   return name;
2097 }
2098
2099 /* Fill NAME with the operand name at position POS.  */
2100
2101 void
2102 dt_operand::gen_opname (char *name, unsigned pos)
2103 {
2104   if (!parent)
2105     sprintf (name, "op%u", pos);
2106   else
2107     sprintf (name, "o%u%u", level, pos);
2108 }
2109
2110 /* Generate matching code for the decision tree operand which is
2111    a predicate.  */
2112
2113 unsigned
2114 dt_operand::gen_predicate (FILE *f, int indent, const char *opname, bool gimple)
2115 {
2116   predicate *p = as_a <predicate *> (op);
2117
2118   if (p->p->matchers.exists ())
2119     {
2120       /* If this is a predicate generated from a pattern mangle its
2121          name and pass on the valueize hook.  */
2122       if (gimple)
2123         fprintf_indent (f, indent, "if (gimple_%s (%s, valueize))\n",
2124                         p->p->id, opname);
2125       else
2126         fprintf_indent (f, indent, "if (tree_%s (%s))\n", p->p->id, opname);
2127     }
2128   else
2129     fprintf_indent (f, indent, "if (%s (%s))\n", p->p->id, opname);
2130   fprintf_indent (f, indent + 2, "{\n");
2131   return 1;
2132 }
2133
2134 /* Generate matching code for the decision tree operand which is
2135    a capture-match.  */
2136
2137 unsigned
2138 dt_operand::gen_match_op (FILE *f, int indent, const char *opname)
2139 {
2140   char match_opname[20];
2141   match_dop->get_name (match_opname);
2142   fprintf_indent (f, indent, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2143                   opname, match_opname, opname, match_opname);
2144   fprintf_indent (f, indent + 2, "{\n");
2145   return 1;
2146 }
2147
2148 /* Generate GIMPLE matching code for the decision tree operand.  */
2149
2150 unsigned
2151 dt_operand::gen_gimple_expr (FILE *f, int indent)
2152 {
2153   expr *e = static_cast<expr *> (op);
2154   id_base *id = e->operation;
2155   unsigned n_ops = e->ops.length ();
2156
2157   for (unsigned i = 0; i < n_ops; ++i)
2158     {
2159       char child_opname[20];
2160       gen_opname (child_opname, i);
2161
2162       if (id->kind == id_base::CODE)
2163         {
2164           if (e->is_generic
2165               || *id == REALPART_EXPR || *id == IMAGPART_EXPR
2166               || *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR)
2167             {
2168               /* ???  If this is a memory operation we can't (and should not)
2169                  match this.  The only sensible operand types are
2170                  SSA names and invariants.  */
2171               fprintf_indent (f, indent,
2172                               "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
2173                               child_opname, i);
2174               fprintf_indent (f, indent,
2175                               "if ((TREE_CODE (%s) == SSA_NAME\n",
2176                               child_opname);
2177               fprintf_indent (f, indent,
2178                               "     || is_gimple_min_invariant (%s))\n",
2179                               child_opname);
2180               fprintf_indent (f, indent,
2181                               "    && (%s = do_valueize (valueize, %s)))\n",
2182                               child_opname, child_opname);
2183               fprintf_indent (f, indent,
2184                               "  {\n");
2185               indent += 4;
2186               continue;
2187             }
2188           else
2189             fprintf_indent (f, indent,
2190                             "tree %s = gimple_assign_rhs%u (def_stmt);\n",
2191                             child_opname, i + 1);
2192         }
2193       else
2194         fprintf_indent (f, indent,
2195                         "tree %s = gimple_call_arg (def_stmt, %u);\n",
2196                         child_opname, i);
2197       fprintf_indent (f, indent,
2198                       "if ((%s = do_valueize (valueize, %s)))\n",
2199                       child_opname, child_opname);
2200       fprintf_indent (f, indent, "  {\n");
2201       indent += 4;
2202     }
2203   /* While the toplevel operands are canonicalized by the caller
2204      after valueizing operands of sub-expressions we have to
2205      re-canonicalize operand order.  */
2206   if (operator_id *code = dyn_cast <operator_id *> (id))
2207     {
2208       /* ???  We can't canonicalize tcc_comparison operands here
2209          because that requires changing the comparison code which
2210          we already matched...  */
2211       if (commutative_tree_code (code->code)
2212           || commutative_ternary_tree_code (code->code))
2213         {
2214           char child_opname0[20], child_opname1[20];
2215           gen_opname (child_opname0, 0);
2216           gen_opname (child_opname1, 1);
2217           fprintf_indent (f, indent,
2218                           "if (tree_swap_operands_p (%s, %s, false))\n",
2219                           child_opname0, child_opname1);
2220           fprintf_indent (f, indent,
2221                           "  std::swap (%s, %s);\n",
2222                           child_opname0, child_opname1);
2223         }
2224     }
2225
2226   return n_ops;
2227 }
2228
2229 /* Generate GENERIC matching code for the decision tree operand.  */
2230
2231 unsigned
2232 dt_operand::gen_generic_expr (FILE *f, int indent, const char *opname)
2233 {
2234   expr *e = static_cast<expr *> (op);
2235   unsigned n_ops = e->ops.length ();
2236
2237   for (unsigned i = 0; i < n_ops; ++i)
2238     {
2239       char child_opname[20];
2240       gen_opname (child_opname, i);
2241
2242       if (e->operation->kind == id_base::CODE)
2243         fprintf_indent (f, indent, "tree %s = TREE_OPERAND (%s, %u);\n",
2244                         child_opname, opname, i);
2245       else
2246         fprintf_indent (f, indent, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2247                         child_opname, opname, i);
2248     }
2249
2250   return 0;
2251 }
2252
2253 /* Generate matching code for the children of the decision tree node.  */
2254
2255 void
2256 dt_node::gen_kids (FILE *f, int indent, bool gimple)
2257 {
2258   auto_vec<dt_operand *> gimple_exprs;
2259   auto_vec<dt_operand *> generic_exprs;
2260   auto_vec<dt_operand *> fns;
2261   auto_vec<dt_operand *> generic_fns;
2262   auto_vec<dt_operand *> preds;
2263   auto_vec<dt_node *> others;
2264
2265   for (unsigned i = 0; i < kids.length (); ++i)
2266     {
2267       if (kids[i]->type == dt_node::DT_OPERAND)
2268         {
2269           dt_operand *op = as_a<dt_operand *> (kids[i]);
2270           if (expr *e = dyn_cast <expr *> (op->op))
2271             {
2272               if (e->ops.length () == 0
2273                   && (!gimple || !(*e->operation == CONSTRUCTOR)))
2274                 generic_exprs.safe_push (op);
2275               else if (e->operation->kind == id_base::FN)
2276                 {
2277                   if (gimple)
2278                     fns.safe_push (op);
2279                   else
2280                     generic_fns.safe_push (op);
2281                 }
2282               else if (e->operation->kind == id_base::PREDICATE)
2283                 preds.safe_push (op);
2284               else
2285                 {
2286                   if (gimple)
2287                     gimple_exprs.safe_push (op);
2288                   else
2289                     generic_exprs.safe_push (op);
2290                 }
2291             }
2292           else if (op->op->type == operand::OP_PREDICATE)
2293             others.safe_push (kids[i]);
2294           else
2295             gcc_unreachable ();
2296         }
2297       else if (kids[i]->type == dt_node::DT_MATCH
2298                || kids[i]->type == dt_node::DT_SIMPLIFY)
2299         others.safe_push (kids[i]);
2300       else if (kids[i]->type == dt_node::DT_TRUE)
2301         {
2302           /* A DT_TRUE operand serves as a barrier - generate code now
2303              for what we have collected sofar.  */
2304           gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2305                       fns, generic_fns, preds, others);
2306           /* And output the true operand itself.  */
2307           kids[i]->gen (f, indent, gimple);
2308           gimple_exprs.truncate (0);
2309           generic_exprs.truncate (0);
2310           fns.truncate (0);
2311           generic_fns.truncate (0);
2312           preds.truncate (0);
2313           others.truncate (0);
2314         }
2315       else
2316         gcc_unreachable ();
2317     }
2318
2319   /* Generate code for the remains.  */
2320   gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2321               fns, generic_fns, preds, others);
2322 }
2323
2324 /* Generate matching code for the children of the decision tree node.  */
2325
2326 void
2327 dt_node::gen_kids_1 (FILE *f, int indent, bool gimple,
2328                      vec<dt_operand *> gimple_exprs,
2329                      vec<dt_operand *> generic_exprs,
2330                      vec<dt_operand *> fns,
2331                      vec<dt_operand *> generic_fns,
2332                      vec<dt_operand *> preds,
2333                      vec<dt_node *> others)
2334 {
2335   char buf[128];
2336   char *kid_opname = buf;
2337
2338   unsigned exprs_len = gimple_exprs.length ();
2339   unsigned gexprs_len = generic_exprs.length ();
2340   unsigned fns_len = fns.length ();
2341   unsigned gfns_len = generic_fns.length ();
2342
2343   if (exprs_len || fns_len || gexprs_len || gfns_len)
2344     {
2345       if (exprs_len)
2346         gimple_exprs[0]->get_name (kid_opname);
2347       else if (fns_len)
2348         fns[0]->get_name (kid_opname);
2349       else if (gfns_len)
2350         generic_fns[0]->get_name (kid_opname);
2351       else
2352         generic_exprs[0]->get_name (kid_opname);
2353
2354       fprintf_indent (f, indent, "switch (TREE_CODE (%s))\n", kid_opname);
2355       fprintf_indent (f, indent, "  {\n");
2356       indent += 2;
2357     }
2358
2359   if (exprs_len || fns_len)
2360     {
2361       fprintf_indent (f, indent,
2362                       "case SSA_NAME:\n");
2363       fprintf_indent (f, indent,
2364                       "  if (do_valueize (valueize, %s) != NULL_TREE)\n",
2365                       kid_opname);
2366       fprintf_indent (f, indent,
2367                       "    {\n");
2368       fprintf_indent (f, indent,
2369                       "      gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2370                       kid_opname);
2371
2372       indent += 6;
2373       if (exprs_len)
2374         {
2375           fprintf_indent (f, indent,
2376                           "if (is_gimple_assign (def_stmt))\n");
2377           fprintf_indent (f, indent,
2378                           "  switch (gimple_assign_rhs_code (def_stmt))\n");
2379           indent += 4;
2380           fprintf_indent (f, indent, "{\n");
2381           for (unsigned i = 0; i < exprs_len; ++i)
2382             {
2383               expr *e = as_a <expr *> (gimple_exprs[i]->op);
2384               id_base *op = e->operation;
2385               if (*op == CONVERT_EXPR || *op == NOP_EXPR)
2386                 fprintf_indent (f, indent, "CASE_CONVERT:\n");
2387               else
2388                 fprintf_indent (f, indent, "case %s:\n", op->id);
2389               fprintf_indent (f, indent, "  {\n");
2390               gimple_exprs[i]->gen (f, indent + 4, true);
2391               fprintf_indent (f, indent, "    break;\n");
2392               fprintf_indent (f, indent, "  }\n");
2393             }
2394           fprintf_indent (f, indent, "default:;\n");
2395           fprintf_indent (f, indent, "}\n");
2396           indent -= 4;
2397         }
2398
2399       if (fns_len)
2400         {
2401           if (exprs_len)
2402             fprintf_indent (f, indent, "else ");
2403           else
2404             fprintf_indent (f, indent, " ");
2405
2406           fprintf (f, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n");
2407           fprintf_indent (f, indent,
2408                           "  {\n");
2409           fprintf_indent (f, indent,
2410                           "    tree fndecl = gimple_call_fndecl (def_stmt);\n");
2411           fprintf_indent (f, indent,
2412                           "    switch (DECL_FUNCTION_CODE (fndecl))\n");
2413           fprintf_indent (f, indent,
2414                           "      {\n");
2415
2416           indent += 6;
2417           for (unsigned i = 0; i < fns_len; ++i)
2418             {
2419               expr *e = as_a <expr *>(fns[i]->op);
2420               fprintf_indent (f, indent, "case %s:\n", e->operation->id);
2421               fprintf_indent (f, indent, "  {\n");
2422               fns[i]->gen (f, indent + 4, true);
2423               fprintf_indent (f, indent, "    break;\n");
2424               fprintf_indent (f, indent, "  }\n");
2425             }
2426
2427           fprintf_indent (f, indent, "default:;\n");
2428           fprintf_indent (f, indent, "}\n");
2429           indent -= 6;
2430           fprintf_indent (f, indent, "  }\n");
2431         }
2432
2433       indent -= 6;
2434       fprintf_indent (f, indent, "    }\n");
2435       fprintf_indent (f, indent, "  break;\n");
2436     }
2437
2438   for (unsigned i = 0; i < generic_exprs.length (); ++i)
2439     {
2440       expr *e = as_a <expr *>(generic_exprs[i]->op);
2441       id_base *op = e->operation;
2442       if (*op == CONVERT_EXPR || *op == NOP_EXPR)
2443         fprintf_indent (f, indent, "CASE_CONVERT:\n");
2444       else
2445         fprintf_indent (f, indent, "case %s:\n", op->id);
2446       fprintf_indent (f, indent, "  {\n");
2447       generic_exprs[i]->gen (f, indent + 4, gimple);
2448       fprintf_indent (f, indent, "    break;\n");
2449       fprintf_indent (f, indent, "  }\n");
2450     }
2451
2452   if (gfns_len)
2453     {
2454       fprintf_indent (f, indent,
2455                       "case CALL_EXPR:\n");
2456       fprintf_indent (f, indent,
2457                       "  {\n");
2458       fprintf_indent (f, indent,
2459                       "    tree fndecl = get_callee_fndecl (%s);\n",
2460                       kid_opname);
2461       fprintf_indent (f, indent,
2462                       "    if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n");
2463       fprintf_indent (f, indent,
2464                       "      switch (DECL_FUNCTION_CODE (fndecl))\n");
2465       fprintf_indent (f, indent,
2466                       "        {\n");
2467       indent += 8;
2468
2469       for (unsigned j = 0; j < generic_fns.length (); ++j)
2470         {
2471           expr *e = as_a <expr *>(generic_fns[j]->op);
2472           gcc_assert (e->operation->kind == id_base::FN);
2473
2474           fprintf_indent (f, indent, "case %s:\n", e->operation->id);
2475           fprintf_indent (f, indent, "  {\n");
2476           generic_fns[j]->gen (f, indent + 4, false);
2477           fprintf_indent (f, indent, "    break;\n");
2478           fprintf_indent (f, indent, "  }\n");
2479         }
2480
2481       indent -= 8;
2482       fprintf_indent (f, indent, "          default:;\n");
2483       fprintf_indent (f, indent, "        }\n");
2484       fprintf_indent (f, indent, "    break;\n");
2485       fprintf_indent (f, indent, "  }\n");
2486     }
2487
2488   /* Close switch (TREE_CODE ()).  */
2489   if (exprs_len || fns_len || gexprs_len || gfns_len)
2490     {
2491       indent -= 4;
2492       fprintf_indent (f, indent, "    default:;\n");
2493       fprintf_indent (f, indent, "    }\n");
2494     }
2495
2496   for (unsigned i = 0; i < preds.length (); ++i)
2497     {
2498       expr *e = as_a <expr *> (preds[i]->op);
2499       predicate_id *p = as_a <predicate_id *> (e->operation);
2500       preds[i]->get_name (kid_opname);
2501       fprintf_indent (f, indent, "tree %s_pops[%d];\n", kid_opname, p->nargs);
2502       fprintf_indent (f, indent, "if (%s_%s (%s, %s_pops%s))\n",
2503                gimple ? "gimple" : "tree",
2504                p->id, kid_opname, kid_opname,
2505                gimple ? ", valueize" : "");
2506       fprintf_indent (f, indent, "  {\n");
2507       for (int j = 0; j < p->nargs; ++j)
2508         {
2509           char child_opname[20];
2510           preds[i]->gen_opname (child_opname, j);
2511           fprintf_indent (f, indent + 4, "tree %s = %s_pops[%d];\n",
2512                           child_opname, kid_opname, j);
2513         }
2514       preds[i]->gen_kids (f, indent + 4, gimple);
2515       fprintf (f, "}\n");
2516     }
2517
2518   for (unsigned i = 0; i < others.length (); ++i)
2519     others[i]->gen (f, indent, gimple);
2520 }
2521
2522 /* Generate matching code for the decision tree operand.  */
2523
2524 void
2525 dt_operand::gen (FILE *f, int indent, bool gimple)
2526 {
2527   char opname[20];
2528   get_name (opname);
2529
2530   unsigned n_braces = 0;
2531
2532   if (type == DT_OPERAND)
2533     switch (op->type)
2534       {
2535         case operand::OP_PREDICATE:
2536           n_braces = gen_predicate (f, indent, opname, gimple);
2537           break;
2538
2539         case operand::OP_EXPR:
2540           if (gimple)
2541             n_braces = gen_gimple_expr (f, indent);
2542           else
2543             n_braces = gen_generic_expr (f, indent, opname);
2544           break;
2545
2546         default:
2547           gcc_unreachable ();
2548       }
2549   else if (type == DT_TRUE)
2550     ;
2551   else if (type == DT_MATCH)
2552     n_braces = gen_match_op (f, indent, opname);
2553   else
2554     gcc_unreachable ();
2555
2556   indent += 4 * n_braces;
2557   gen_kids (f, indent, gimple);
2558
2559   for (unsigned i = 0; i < n_braces; ++i)
2560     {
2561       indent -= 4;
2562       if (indent < 0)
2563         indent = 0;
2564       fprintf_indent (f, indent, "  }\n");
2565     }
2566 }
2567
2568
2569 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2570    step of a '(simplify ...)' or '(match ...)'.  This handles everything
2571    that is not part of the decision tree (simplify->match).
2572    Main recursive worker.  */
2573
2574 void
2575 dt_simplify::gen_1 (FILE *f, int indent, bool gimple, operand *result)
2576 {
2577   if (result)
2578     {
2579       if (with_expr *w = dyn_cast <with_expr *> (result))
2580         {
2581           fprintf_indent (f, indent, "{\n");
2582           indent += 4;
2583           output_line_directive (f, w->location);
2584           w->with->gen_transform (f, indent, NULL, true, 1, "type", NULL);
2585           gen_1 (f, indent, gimple, w->subexpr);
2586           indent -= 4;
2587           fprintf_indent (f, indent, "}\n");
2588           return;
2589         }
2590       else if (if_expr *ife = dyn_cast <if_expr *> (result))
2591         {
2592           output_line_directive (f, ife->location);
2593           fprintf_indent (f, indent, "if (");
2594           ife->cond->gen_transform (f, indent, NULL, true, 1, "type", NULL);
2595           fprintf (f, ")\n");
2596           fprintf_indent (f, indent + 2, "{\n");
2597           indent += 4;
2598           gen_1 (f, indent, gimple, ife->trueexpr);
2599           indent -= 4;
2600           fprintf_indent (f, indent + 2, "}\n");
2601           if (ife->falseexpr)
2602             {
2603               fprintf_indent (f, indent, "else\n");
2604               fprintf_indent (f, indent + 2, "{\n");
2605               indent += 4;
2606               gen_1 (f, indent, gimple, ife->falseexpr);
2607               indent -= 4;
2608               fprintf_indent (f, indent + 2, "}\n");
2609             }
2610           return;
2611         }
2612     }
2613
2614   /* Analyze captures and perform early-outs on the incoming arguments
2615      that cover cases we cannot handle.  */
2616   capture_info cinfo (s, result);
2617   if (s->kind == simplify::SIMPLIFY)
2618     {
2619       if (!gimple)
2620         {
2621           for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
2622             if (cinfo.force_no_side_effects & (1 << i))
2623               fprintf_indent (f, indent,
2624                               "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
2625                               i);
2626           for (int i = 0; i <= s->capture_max; ++i)
2627             if (cinfo.info[i].cse_p)
2628               ;
2629             else if (cinfo.info[i].force_no_side_effects_p
2630                      && (cinfo.info[i].toplevel_msk
2631                          & cinfo.force_no_side_effects) == 0)
2632               fprintf_indent (f, indent,
2633                               "if (TREE_SIDE_EFFECTS (captures[%d])) "
2634                               "return NULL_TREE;\n", i);
2635             else if ((cinfo.info[i].toplevel_msk
2636                       & cinfo.force_no_side_effects) != 0)
2637               /* Mark capture as having no side-effects if we had to verify
2638                  that via forced toplevel operand checks.  */
2639               cinfo.info[i].force_no_side_effects_p = true;
2640         }
2641       if (gimple)
2642         {
2643           /* Force single-use restriction by only allowing simple
2644              results via setting seq to NULL.  */
2645           fprintf_indent (f, indent, "gimple_seq *lseq = seq;\n");
2646           bool first_p = true;
2647           for (int i = 0; i <= s->capture_max; ++i)
2648             if (cinfo.info[i].force_single_use)
2649               {
2650                 if (first_p)
2651                   {
2652                     fprintf_indent (f, indent, "if (lseq\n");
2653                     fprintf_indent (f, indent, "    && (");
2654                     first_p = false;
2655                   }
2656                 else
2657                   {
2658                     fprintf (f, "\n");
2659                     fprintf_indent (f, indent, "        || ");
2660                   }
2661                 fprintf (f, "!single_use (captures[%d])", i);
2662               }
2663           if (!first_p)
2664             {
2665               fprintf (f, "))\n");
2666               fprintf_indent (f, indent, "  lseq = NULL;\n");
2667             }
2668         }
2669     }
2670
2671   fprintf_indent (f, indent, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2672            "fprintf (dump_file, \"Applying pattern ");
2673   output_line_directive (f,
2674                          result ? result->location : s->match->location, true);
2675   fprintf (f, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2676
2677   if (!result)
2678     {
2679       /* If there is no result then this is a predicate implementation.  */
2680       fprintf_indent (f, indent, "return true;\n");
2681     }
2682   else if (gimple)
2683     {
2684       /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2685          in outermost position).  */
2686       if (result->type == operand::OP_EXPR
2687           && *as_a <expr *> (result)->operation == NON_LVALUE_EXPR)
2688         result = as_a <expr *> (result)->ops[0];
2689       if (result->type == operand::OP_EXPR)
2690         {
2691           expr *e = as_a <expr *> (result);
2692           bool is_predicate = is_a <predicate_id *> (e->operation);
2693           if (!is_predicate)
2694             fprintf_indent (f, indent, "*res_code = %s;\n",
2695                             *e->operation == CONVERT_EXPR
2696                             ? "NOP_EXPR" : e->operation->id);
2697           for (unsigned j = 0; j < e->ops.length (); ++j)
2698             {
2699               char dest[32];
2700               snprintf (dest, 32, "res_ops[%d]", j);
2701               const char *optype
2702                 = get_operand_type (e->operation,
2703                                     "type", e->expr_type,
2704                                     j == 0 ? NULL : "TREE_TYPE (res_ops[0])");
2705               /* We need to expand GENERIC conditions we captured from
2706                  COND_EXPRs.  */
2707               bool expand_generic_cond_exprs_p
2708                 = (!is_predicate
2709                    /* But avoid doing that if the GENERIC condition is
2710                       valid - which it is in the first operand of COND_EXPRs
2711                       and VEC_COND_EXRPs.  */
2712                    && ((!(*e->operation == COND_EXPR)
2713                         && !(*e->operation == VEC_COND_EXPR))
2714                        || j != 0));
2715               e->ops[j]->gen_transform (f, indent, dest, true, 1, optype,
2716                                         &cinfo,
2717                                         indexes, expand_generic_cond_exprs_p);
2718             }
2719
2720           /* Re-fold the toplevel result.  It's basically an embedded
2721              gimple_build w/o actually building the stmt.  */
2722           if (!is_predicate)
2723             fprintf_indent (f, indent,
2724                             "gimple_resimplify%d (lseq, res_code, type, "
2725                             "res_ops, valueize);\n", e->ops.length ());
2726         }
2727       else if (result->type == operand::OP_CAPTURE
2728                || result->type == operand::OP_C_EXPR)
2729         {
2730           result->gen_transform (f, indent, "res_ops[0]", true, 1, "type",
2731                                  &cinfo, indexes, false);
2732           fprintf_indent (f, indent, "*res_code = TREE_CODE (res_ops[0]);\n");
2733           if (is_a <capture *> (result)
2734               && cinfo.info[as_a <capture *> (result)->where].cond_expr_cond_p)
2735             {
2736               /* ???  Stupid tcc_comparison GENERIC trees in COND_EXPRs.  Deal
2737                  with substituting a capture of that.  */
2738               fprintf_indent (f, indent,
2739                               "if (COMPARISON_CLASS_P (res_ops[0]))\n");
2740               fprintf_indent (f, indent,
2741                               "  {\n");
2742               fprintf_indent (f, indent,
2743                               "    tree tem = res_ops[0];\n");
2744               fprintf_indent (f, indent,
2745                               "    res_ops[0] = TREE_OPERAND (tem, 0);\n");
2746               fprintf_indent (f, indent,
2747                               "    res_ops[1] = TREE_OPERAND (tem, 1);\n");
2748               fprintf_indent (f, indent,
2749                               "  }\n");
2750             }
2751         }
2752       else
2753         gcc_unreachable ();
2754       fprintf_indent (f, indent, "return true;\n");
2755     }
2756   else /* GENERIC */
2757     {
2758       bool is_predicate = false;
2759       if (result->type == operand::OP_EXPR)
2760         {
2761           expr *e = as_a <expr *> (result);
2762           is_predicate = is_a <predicate_id *> (e->operation);
2763           /* Search for captures used multiple times in the result expression
2764              and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR.  */
2765           if (!is_predicate)
2766             for (int i = 0; i < s->capture_max + 1; ++i)
2767               {
2768                 if (!cinfo.info[i].force_no_side_effects_p
2769                     && cinfo.info[i].result_use_count > 1)
2770                   {
2771                     fprintf_indent (f, indent,
2772                                     "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
2773                                     i);
2774                     fprintf_indent (f, indent,
2775                                     "  captures[%d] = save_expr (captures[%d]);\n",
2776                                     i, i);
2777                   }
2778               }
2779           for (unsigned j = 0; j < e->ops.length (); ++j)
2780             {
2781               char dest[32];
2782               if (is_predicate)
2783                 snprintf (dest, 32, "res_ops[%d]", j);
2784               else
2785                 {
2786                   fprintf_indent (f, indent, "tree res_op%d;\n", j);
2787                   snprintf (dest, 32, "res_op%d", j);
2788                 }
2789               const char *optype
2790                 = get_operand_type (e->operation,
2791                                     "type", e->expr_type,
2792                                     j == 0
2793                                     ? NULL : "TREE_TYPE (res_op0)");
2794               e->ops[j]->gen_transform (f, indent, dest, false, 1, optype,
2795                                         &cinfo, indexes);
2796             }
2797           if (is_predicate)
2798             fprintf_indent (f, indent, "return true;\n");
2799           else
2800             {
2801               fprintf_indent (f, indent, "tree res;\n");
2802               /* Re-fold the toplevel result.  Use non_lvalue to
2803                  build NON_LVALUE_EXPRs so they get properly
2804                  ignored when in GIMPLE form.  */
2805               if (*e->operation == NON_LVALUE_EXPR)
2806                 fprintf_indent (f, indent,
2807                                 "res = non_lvalue_loc (loc, res_op0);\n");
2808               else
2809                 {
2810                   if (e->operation->kind == id_base::CODE)
2811                     fprintf_indent (f, indent,
2812                                     "res = fold_build%d_loc (loc, %s, type",
2813                                     e->ops.length (),
2814                                     *e->operation == CONVERT_EXPR
2815                                     ? "NOP_EXPR" : e->operation->id);
2816                   else
2817                     fprintf_indent (f, indent,
2818                                     "res = build_call_expr_loc "
2819                                     "(loc, builtin_decl_implicit (%s), %d",
2820                                     e->operation->id, e->ops.length());
2821                   for (unsigned j = 0; j < e->ops.length (); ++j)
2822                     fprintf (f, ", res_op%d", j);
2823                   fprintf (f, ");\n");
2824                 }
2825             }
2826         }
2827       else if (result->type == operand::OP_CAPTURE
2828                || result->type == operand::OP_C_EXPR)
2829
2830         {
2831           fprintf_indent (f, indent, "tree res;\n");
2832           result->gen_transform (f, indent, "res", false, 1, "type",
2833                                     &cinfo, indexes);
2834         }
2835       else
2836         gcc_unreachable ();
2837       if (!is_predicate)
2838         {
2839           /* Search for captures not used in the result expression and dependent
2840              on TREE_SIDE_EFFECTS emit omit_one_operand.  */
2841           for (int i = 0; i < s->capture_max + 1; ++i)
2842             {
2843               if (!cinfo.info[i].force_no_side_effects_p
2844                   && !cinfo.info[i].expr_p
2845                   && cinfo.info[i].result_use_count == 0)
2846                 {
2847                   fprintf_indent (f, indent,
2848                                   "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
2849                                   i);
2850                   fprintf_indent (f, indent + 2,
2851                                   "res = build2_loc (loc, COMPOUND_EXPR, type, "
2852                                   "fold_ignored_result (captures[%d]), res);\n",
2853                                   i);
2854                 }
2855             }
2856           fprintf_indent (f, indent, "return res;\n");
2857         }
2858     }
2859 }
2860
2861 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2862    step of a '(simplify ...)' or '(match ...)'.  This handles everything
2863    that is not part of the decision tree (simplify->match).  */
2864
2865 void
2866 dt_simplify::gen (FILE *f, int indent, bool gimple)
2867 {
2868   fprintf_indent (f, indent, "{\n");
2869   indent += 2;
2870   output_line_directive (f,
2871                          s->result ? s->result->location : s->match->location);
2872   if (s->capture_max >= 0)
2873     fprintf_indent (f, indent, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2874                     s->capture_max + 1);
2875
2876   for (int i = 0; i <= s->capture_max; ++i)
2877     if (indexes[i])
2878       {
2879         char opname[20];
2880         fprintf_indent (f, indent, "captures[%u] = %s;\n",
2881                         i, indexes[i]->get_name (opname));
2882       }
2883
2884   gen_1 (f, indent, gimple, s->result);
2885
2886   indent -= 2;
2887   fprintf_indent (f, indent, "}\n");
2888 }
2889
2890 /* Main entry to generate code for matching GIMPLE IL off the decision
2891    tree.  */
2892
2893 void
2894 decision_tree::gen_gimple (FILE *f)
2895 {
2896   for (unsigned n = 1; n <= 3; ++n)
2897     {
2898       fprintf (f, "\nstatic bool\n"
2899                "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2900                "                 gimple_seq *seq, tree (*valueize)(tree),\n"
2901                "                 code_helper code, tree type");
2902       for (unsigned i = 0; i < n; ++i)
2903         fprintf (f, ", tree op%d", i);
2904       fprintf (f, ")\n");
2905       fprintf (f, "{\n");
2906
2907       fprintf (f, "  switch (code.get_rep())\n"
2908                   "    {\n");
2909       for (unsigned i = 0; i < root->kids.length (); i++)
2910         {
2911           dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
2912           expr *e = static_cast<expr *>(dop->op);
2913           if (e->ops.length () != n)
2914             continue;
2915
2916           if (*e->operation == CONVERT_EXPR
2917               || *e->operation == NOP_EXPR)
2918             fprintf (f, "    CASE_CONVERT:\n");
2919           else
2920             fprintf (f, "    case %s%s:\n",
2921                      is_a <fn_id *> (e->operation) ? "-" : "",
2922                      e->operation->id);
2923           fprintf (f,   "      {\n");
2924           dop->gen_kids (f, 8, true);
2925           fprintf (f,   "        break;\n");
2926           fprintf (f,   "      }\n");
2927         }
2928       fprintf (f,       "    default:;\n"
2929                         "    }\n");
2930
2931       fprintf (f, "  return false;\n");
2932       fprintf (f, "}\n");
2933     }
2934 }
2935
2936 /* Main entry to generate code for matching GENERIC IL off the decision
2937    tree.  */
2938
2939 void
2940 decision_tree::gen_generic (FILE *f)
2941 {
2942   for (unsigned n = 1; n <= 3; ++n)
2943     {
2944       fprintf (f, "\ntree\n"
2945                "generic_simplify (location_t loc, enum tree_code code, "
2946                "tree type ATTRIBUTE_UNUSED");
2947       for (unsigned i = 0; i < n; ++i)
2948         fprintf (f, ", tree op%d", i);
2949       fprintf (f, ")\n");
2950       fprintf (f, "{\n");
2951
2952       fprintf (f, "  switch (code)\n"
2953                   "    {\n");
2954       for (unsigned i = 0; i < root->kids.length (); i++)
2955         {
2956           dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
2957           expr *e = static_cast<expr *>(dop->op);
2958           if (e->ops.length () != n
2959               /* Builtin simplifications are somewhat premature on
2960                  GENERIC.  The following drops patterns with outermost
2961                  calls.  It's easy to emit overloads for function code
2962                  though if necessary.  */
2963               || e->operation->kind != id_base::CODE)
2964             continue;
2965
2966           operator_id *op_id = static_cast <operator_id *> (e->operation);
2967           if (op_id->code == NOP_EXPR || op_id->code == CONVERT_EXPR)
2968             fprintf (f, "    CASE_CONVERT:\n");
2969           else
2970             fprintf (f, "    case %s:\n", e->operation->id);
2971           fprintf (f,   "      {\n");
2972           dop->gen_kids (f, 8, false);
2973           fprintf (f,   "        break;\n"
2974                         "      }\n");
2975         }
2976       fprintf (f, "    default:;\n"
2977                   "    }\n");
2978
2979       fprintf (f, "  return NULL_TREE;\n");
2980       fprintf (f, "}\n");
2981     }
2982 }
2983
2984 /* Output code to implement the predicate P from the decision tree DT.  */
2985
2986 void
2987 write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple)
2988 {
2989   fprintf (f, "\nbool\n"
2990            "%s%s (tree t%s%s)\n"
2991            "{\n", gimple ? "gimple_" : "tree_", p->id,
2992            p->nargs > 0 ? ", tree *res_ops" : "",
2993            gimple ? ", tree (*valueize)(tree)" : "");
2994   /* Conveniently make 'type' available.  */
2995   fprintf_indent (f, 2, "tree type = TREE_TYPE (t);\n");
2996
2997   if (!gimple)
2998     fprintf_indent (f, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2999   dt.root->gen_kids (f, 2, gimple);
3000
3001   fprintf_indent (f, 2, "return false;\n"
3002            "}\n");
3003 }
3004
3005 /* Write the common header for the GIMPLE/GENERIC IL matching routines.  */
3006
3007 static void
3008 write_header (FILE *f, const char *head)
3009 {
3010   fprintf (f, "/* Generated automatically by the program `genmatch' from\n");
3011   fprintf (f, "   a IL pattern matching and simplification description.  */\n");
3012
3013   /* Include the header instead of writing it awkwardly quoted here.  */
3014   fprintf (f, "\n#include \"%s\"\n", head);
3015 }
3016
3017
3018
3019 /* AST parsing.  */
3020
3021 class parser
3022 {
3023 public:
3024   parser (cpp_reader *);
3025
3026 private:
3027   const cpp_token *next ();
3028   const cpp_token *peek (unsigned = 1);
3029   const cpp_token *peek_ident (const char * = NULL, unsigned = 1);
3030   const cpp_token *expect (enum cpp_ttype);
3031   const cpp_token *eat_token (enum cpp_ttype);
3032   const char *get_string ();
3033   const char *get_ident ();
3034   const cpp_token *eat_ident (const char *);
3035   const char *get_number ();
3036
3037   id_base *parse_operation ();
3038   operand *parse_capture (operand *);
3039   operand *parse_expr ();
3040   c_expr *parse_c_expr (cpp_ttype);
3041   operand *parse_op ();
3042
3043   void record_operlist (source_location, user_id *);
3044
3045   void parse_pattern ();
3046   operand *parse_result (operand *, predicate_id *);
3047   void push_simplify (simplify::simplify_kind,
3048                       vec<simplify *>&, operand *, operand *);
3049   void parse_simplify (simplify::simplify_kind,
3050                        vec<simplify *>&, predicate_id *, operand *);
3051   void parse_for (source_location);
3052   void parse_if (source_location);
3053   void parse_predicates (source_location);
3054   void parse_operator_list (source_location);
3055
3056   cpp_reader *r;
3057   vec<c_expr *> active_ifs;
3058   vec<vec<user_id *> > active_fors;
3059   hash_set<user_id *> *oper_lists_set;
3060   vec<user_id *> oper_lists;
3061
3062   cid_map_t *capture_ids;
3063
3064 public:
3065   vec<simplify *> simplifiers;
3066   vec<predicate_id *> user_predicates;
3067   bool parsing_match_operand;
3068 };
3069
3070 /* Lexing helpers.  */
3071
3072 /* Read the next non-whitespace token from R.  */
3073
3074 const cpp_token *
3075 parser::next ()
3076 {
3077   const cpp_token *token;
3078   do
3079     {
3080       token = cpp_get_token (r);
3081     }
3082   while (token->type == CPP_PADDING
3083          && token->type != CPP_EOF);
3084   return token;
3085 }
3086
3087 /* Peek at the next non-whitespace token from R.  */
3088
3089 const cpp_token *
3090 parser::peek (unsigned num)
3091 {
3092   const cpp_token *token;
3093   unsigned i = 0;
3094   do
3095     {
3096       token = cpp_peek_token (r, i++);
3097     }
3098   while ((token->type == CPP_PADDING
3099           && token->type != CPP_EOF)
3100          || (--num > 0));
3101   /* If we peek at EOF this is a fatal error as it leaves the
3102      cpp_reader in unusable state.  Assume we really wanted a
3103      token and thus this EOF is unexpected.  */
3104   if (token->type == CPP_EOF)
3105     fatal_at (token, "unexpected end of file");
3106   return token;
3107 }
3108
3109 /* Peek at the next identifier token (or return NULL if the next
3110    token is not an identifier or equal to ID if supplied).  */
3111
3112 const cpp_token *
3113 parser::peek_ident (const char *id, unsigned num)
3114 {
3115   const cpp_token *token = peek (num);
3116   if (token->type != CPP_NAME)
3117     return 0;
3118
3119   if (id == 0)
3120     return token;
3121
3122   const char *t = (const char *) CPP_HASHNODE (token->val.node.node)->ident.str;
3123   if (strcmp (id, t) == 0)
3124     return token;
3125
3126   return 0;
3127 }
3128
3129 /* Read the next token from R and assert it is of type TK.  */
3130
3131 const cpp_token *
3132 parser::expect (enum cpp_ttype tk)
3133 {
3134   const cpp_token *token = next ();
3135   if (token->type != tk)
3136     fatal_at (token, "expected %s, got %s",
3137               cpp_type2name (tk, 0), cpp_type2name (token->type, 0));
3138
3139   return token;
3140 }
3141
3142 /* Consume the next token from R and assert it is of type TK.  */
3143
3144 const cpp_token *
3145 parser::eat_token (enum cpp_ttype tk)
3146 {
3147   return expect (tk);
3148 }
3149
3150 /* Read the next token from R and assert it is of type CPP_STRING and
3151    return its value.  */
3152
3153 const char *
3154 parser::get_string ()
3155 {
3156   const cpp_token *token = expect (CPP_STRING);
3157   return (const char *)token->val.str.text;
3158 }
3159
3160 /* Read the next token from R and assert it is of type CPP_NAME and
3161    return its value.  */
3162
3163 const char *
3164 parser::get_ident ()
3165 {
3166   const cpp_token *token = expect (CPP_NAME);
3167   return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str;
3168 }
3169
3170 /* Eat an identifier token with value S from R.  */
3171
3172 const cpp_token *
3173 parser::eat_ident (const char *s)
3174 {
3175   const cpp_token *token = peek ();
3176   const char *t = get_ident ();
3177   if (strcmp (s, t) != 0)
3178     fatal_at (token, "expected '%s' got '%s'\n", s, t);
3179   return token;
3180 }
3181
3182 /* Read the next token from R and assert it is of type CPP_NUMBER and
3183    return its value.  */
3184
3185 const char *
3186 parser::get_number ()
3187 {
3188   const cpp_token *token = expect (CPP_NUMBER);
3189   return (const char *)token->val.str.text;
3190 }
3191
3192
3193 /* Record an operator-list use for transparent for handling.  */
3194
3195 void
3196 parser::record_operlist (source_location loc, user_id *p)
3197 {
3198   if (!oper_lists_set->add (p))
3199     {
3200       if (!oper_lists.is_empty ()
3201           && oper_lists[0]->substitutes.length () != p->substitutes.length ())
3202         fatal_at (loc, "User-defined operator list does not have the "
3203                   "same number of entries as others used in the pattern");
3204       oper_lists.safe_push (p);
3205     }
3206 }
3207
3208 /* Parse the operator ID, special-casing convert?, convert1? and
3209    convert2?  */
3210
3211 id_base *
3212 parser::parse_operation ()
3213 {
3214   const cpp_token *id_tok = peek ();
3215   const char *id = get_ident ();
3216   const cpp_token *token = peek ();
3217   if (strcmp (id, "convert0") == 0)
3218     fatal_at (id_tok, "use 'convert?' here");
3219   else if (strcmp (id, "view_convert0") == 0)
3220     fatal_at (id_tok, "use 'view_convert?' here");
3221   if (token->type == CPP_QUERY
3222       && !(token->flags & PREV_WHITE))
3223     {
3224       if (strcmp (id, "convert") == 0)
3225         id = "convert0";
3226       else if (strcmp (id, "convert1") == 0)
3227         ;
3228       else if (strcmp (id, "convert2") == 0)
3229         ;
3230       else if (strcmp (id, "view_convert") == 0)
3231         id = "view_convert0";
3232       else if (strcmp (id, "view_convert1") == 0)
3233         ;
3234       else if (strcmp (id, "view_convert2") == 0)
3235         ;
3236       else
3237         fatal_at (id_tok, "non-convert operator conditionalized");
3238
3239       if (!parsing_match_operand)
3240         fatal_at (id_tok, "conditional convert can only be used in "
3241                   "match expression");
3242       eat_token (CPP_QUERY);
3243     }
3244   else if (strcmp (id, "convert1") == 0
3245            || strcmp (id, "convert2") == 0
3246            || strcmp (id, "view_convert1") == 0
3247            || strcmp (id, "view_convert2") == 0)
3248     fatal_at (id_tok, "expected '?' after conditional operator");
3249   id_base *op = get_operator (id);
3250   if (!op)
3251     fatal_at (id_tok, "unknown operator %s", id);
3252
3253   user_id *p = dyn_cast<user_id *> (op);
3254   if (p && p->is_oper_list)
3255     {
3256       if (active_fors.length() == 0)
3257         record_operlist (id_tok->src_loc, p);
3258       else
3259         fatal_at (id_tok, "operator-list %s cannot be exapnded inside 'for'", id);
3260     }
3261   return op;
3262 }
3263
3264 /* Parse a capture.
3265      capture = '@'<number>  */
3266
3267 struct operand *
3268 parser::parse_capture (operand *op)
3269 {
3270   source_location src_loc = eat_token (CPP_ATSIGN)->src_loc;
3271   const cpp_token *token = peek ();
3272   const char *id = NULL;
3273   if (token->type == CPP_NUMBER)
3274     id = get_number ();
3275   else if (token->type == CPP_NAME)
3276     id = get_ident ();
3277   else
3278     fatal_at (token, "expected number or identifier");
3279   unsigned next_id = capture_ids->elements ();
3280   bool existed;
3281   unsigned &num = capture_ids->get_or_insert (id, &existed);
3282   if (!existed)
3283     num = next_id;
3284   return new capture (src_loc, num, op);
3285 }
3286
3287 /* Parse an expression
3288      expr = '(' <operation>[capture][flag][type] <operand>... ')'  */
3289
3290 struct operand *
3291 parser::parse_expr ()
3292 {
3293   const cpp_token *token = peek ();
3294   expr *e = new expr (parse_operation (), token->src_loc);
3295   token = peek ();
3296   operand *op;
3297   bool is_commutative = false;
3298   bool force_capture = false;
3299   const char *expr_type = NULL;
3300
3301   if (token->type == CPP_COLON
3302       && !(token->flags & PREV_WHITE))
3303     {
3304       eat_token (CPP_COLON);
3305       token = peek ();
3306       if (token->type == CPP_NAME
3307           && !(token->flags & PREV_WHITE))
3308         {
3309           const char *s = get_ident ();
3310           if (!parsing_match_operand)
3311             expr_type = s;
3312           else
3313             {
3314               const char *sp = s;
3315               while (*sp)
3316                 {
3317                   if (*sp == 'c')
3318                     is_commutative = true;
3319                   else if (*sp == 's')
3320                     {
3321                       e->force_single_use = true;
3322                       force_capture = true;
3323                     }
3324                   else
3325                     fatal_at (token, "flag %c not recognized", *sp);
3326                   sp++;
3327                 }
3328             }
3329           token = peek ();
3330         }
3331       else
3332         fatal_at (token, "expected flag or type specifying identifier");
3333     }
3334
3335   if (token->type == CPP_ATSIGN
3336       && !(token->flags & PREV_WHITE))
3337     op = parse_capture (e);
3338   else if (force_capture)
3339     {
3340       unsigned num = capture_ids->elements ();
3341       char id[8];
3342       bool existed;
3343       sprintf (id, "__%u", num);
3344       capture_ids->get_or_insert (xstrdup (id), &existed);
3345       if (existed)
3346         fatal_at (token, "reserved capture id '%s' already used", id);
3347       op = new capture (token->src_loc, num, e);
3348     }
3349   else
3350     op = e;
3351   do
3352     {
3353       const cpp_token *token = peek ();
3354       if (token->type == CPP_CLOSE_PAREN)
3355         {
3356           if (e->operation->nargs != -1
3357               && e->operation->nargs != (int) e->ops.length ())
3358             fatal_at (token, "'%s' expects %u operands, not %u",
3359                       e->operation->id, e->operation->nargs, e->ops.length ());
3360           if (is_commutative)
3361             {
3362               if (e->ops.length () == 2)
3363                 e->is_commutative = true;
3364               else
3365                 fatal_at (token, "only binary operators or function with "
3366                           "two arguments can be marked commutative");
3367             }
3368           e->expr_type = expr_type;
3369           return op;
3370         }
3371       e->append_op (parse_op ());
3372     }
3373   while (1);
3374 }
3375
3376 /* Lex native C code delimited by START recording the preprocessing tokens
3377    for later processing.
3378      c_expr = ('{'|'(') <pp token>... ('}'|')')  */
3379
3380 c_expr *
3381 parser::parse_c_expr (cpp_ttype start)
3382 {
3383   const cpp_token *token;
3384   cpp_ttype end;
3385   unsigned opencnt;
3386   vec<cpp_token> code = vNULL;
3387   unsigned nr_stmts = 0;
3388   source_location loc = eat_token (start)->src_loc;
3389   if (start == CPP_OPEN_PAREN)
3390     end = CPP_CLOSE_PAREN;
3391   else if (start == CPP_OPEN_BRACE)
3392     end = CPP_CLOSE_BRACE;
3393   else
3394     gcc_unreachable ();
3395   opencnt = 1;
3396   do
3397     {
3398       token = next ();
3399
3400       /* Count brace pairs to find the end of the expr to match.  */
3401       if (token->type == start)
3402         opencnt++;
3403       else if (token->type == end
3404                && --opencnt == 0)
3405         break;
3406
3407       /* This is a lame way of counting the number of statements.  */
3408       if (token->type == CPP_SEMICOLON)
3409         nr_stmts++;
3410
3411       /* If this is possibly a user-defined identifier mark it used.  */
3412       if (token->type == CPP_NAME)
3413         {
3414           id_base *idb = get_operator ((const char *)CPP_HASHNODE
3415                                       (token->val.node.node)->ident.str);
3416           user_id *p;
3417           if (idb && (p = dyn_cast<user_id *> (idb)) && p->is_oper_list)
3418             record_operlist (token->src_loc, p);
3419         }
3420
3421       /* Record the token.  */
3422       code.safe_push (*token);
3423     }
3424   while (1);
3425   return new c_expr (r, loc, code, nr_stmts, vNULL, capture_ids);
3426 }
3427
3428 /* Parse an operand which is either an expression, a predicate or
3429    a standalone capture.
3430      op = predicate | expr | c_expr | capture  */
3431
3432 struct operand *
3433 parser::parse_op ()
3434 {
3435   const cpp_token *token = peek ();
3436   struct operand *op = NULL;
3437   if (token->type == CPP_OPEN_PAREN)
3438     {
3439       eat_token (CPP_OPEN_PAREN);
3440       op = parse_expr ();
3441       eat_token (CPP_CLOSE_PAREN);
3442     }
3443   else if (token->type == CPP_OPEN_BRACE)
3444     {
3445       op = parse_c_expr (CPP_OPEN_BRACE);
3446     }
3447   else
3448     {
3449       /* Remaining ops are either empty or predicates  */
3450       if (token->type == CPP_NAME)
3451         {
3452           const char *id = get_ident ();
3453           id_base *opr = get_operator (id);
3454           if (!opr)
3455             fatal_at (token, "expected predicate name");
3456           if (operator_id *code = dyn_cast <operator_id *> (opr))
3457             {
3458               if (code->nargs != 0)
3459                 fatal_at (token, "using an operator with operands as predicate");
3460               /* Parse the zero-operand operator "predicates" as
3461                  expression.  */
3462               op = new expr (opr, token->src_loc);
3463             }
3464           else if (user_id *code = dyn_cast <user_id *> (opr))
3465             {
3466               if (code->nargs != 0)
3467                 fatal_at (token, "using an operator with operands as predicate");
3468               /* Parse the zero-operand operator "predicates" as
3469                  expression.  */
3470               op = new expr (opr, token->src_loc);
3471             }
3472           else if (predicate_id *p = dyn_cast <predicate_id *> (opr))
3473             op = new predicate (p, token->src_loc);
3474           else
3475             fatal_at (token, "using an unsupported operator as predicate");
3476           if (!parsing_match_operand)
3477             fatal_at (token, "predicates are only allowed in match expression");
3478           token = peek ();
3479           if (token->flags & PREV_WHITE)
3480             return op;
3481         }
3482       else if (token->type != CPP_COLON
3483                && token->type != CPP_ATSIGN)
3484         fatal_at (token, "expected expression or predicate");
3485       /* optionally followed by a capture and a predicate.  */
3486       if (token->type == CPP_COLON)
3487         fatal_at (token, "not implemented: predicate on leaf operand");
3488       if (token->type == CPP_ATSIGN)
3489         op = parse_capture (op);
3490     }
3491
3492   return op;
3493 }
3494
3495 /* Create a new simplify from the current parsing state and MATCH,
3496    MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS.  */
3497
3498 void
3499 parser::push_simplify (simplify::simplify_kind kind,
3500                        vec<simplify *>& simplifiers,
3501                        operand *match, operand *result)
3502 {
3503   /* Build and push a temporary for operator list uses in expressions.  */
3504   if (!oper_lists.is_empty ())
3505     active_fors.safe_push (oper_lists);
3506
3507   simplifiers.safe_push
3508     (new simplify (kind, match, result,
3509                    active_fors.copy (), capture_ids));
3510
3511   if (!oper_lists.is_empty ())
3512     active_fors.pop ();
3513 }
3514
3515 /* Parse
3516      <result-op> = <op> | <if> | <with>
3517      <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3518      <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3519    and return it.  */
3520
3521 operand *
3522 parser::parse_result (operand *result, predicate_id *matcher)
3523 {
3524   const cpp_token *token = peek ();
3525   if (token->type != CPP_OPEN_PAREN)
3526     return parse_op ();
3527
3528   eat_token (CPP_OPEN_PAREN);
3529   if (peek_ident ("if"))
3530     {
3531       eat_ident ("if");
3532       if_expr *ife = new if_expr (token->src_loc);
3533       ife->cond = parse_c_expr (CPP_OPEN_PAREN);
3534       if (peek ()->type == CPP_OPEN_PAREN)
3535         {
3536           ife->trueexpr = parse_result (result, matcher);
3537           if (peek ()->type == CPP_OPEN_PAREN)
3538             ife->falseexpr = parse_result (result, matcher);
3539           else if (peek ()->type != CPP_CLOSE_PAREN)
3540             ife->falseexpr = parse_op ();
3541         }
3542       else if (peek ()->type != CPP_CLOSE_PAREN)
3543         {
3544           ife->trueexpr = parse_op ();
3545           if (peek ()->type == CPP_OPEN_PAREN)
3546             ife->falseexpr = parse_result (result, matcher);
3547           else if (peek ()->type != CPP_CLOSE_PAREN)
3548             ife->falseexpr = parse_op ();
3549         }
3550       /* If this if is immediately closed then it contains a
3551          manual matcher or is part of a predicate definition.  */
3552       else /* if (peek ()->type == CPP_CLOSE_PAREN) */
3553         {
3554           if (!matcher)
3555             fatal_at (peek (), "manual transform not implemented");
3556           ife->trueexpr = result;
3557         }
3558       eat_token (CPP_CLOSE_PAREN);
3559       return ife;
3560     }
3561   else if (peek_ident ("with"))
3562     {
3563       eat_ident ("with");
3564       with_expr *withe = new with_expr (token->src_loc);
3565       /* Parse (with c-expr expr) as (if-with (true) expr).  */
3566       withe->with = parse_c_expr (CPP_OPEN_BRACE);
3567       withe->with->nr_stmts = 0;
3568       withe->subexpr = parse_result (result, matcher);
3569       eat_token (CPP_CLOSE_PAREN);
3570       return withe;
3571     }
3572   else if (peek_ident ("switch"))
3573     {
3574       token = eat_ident ("switch");
3575       source_location ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
3576       eat_ident ("if");
3577       if_expr *ife = new if_expr (ifloc);
3578       operand *res = ife;
3579       ife->cond = parse_c_expr (CPP_OPEN_PAREN);
3580       if (peek ()->type == CPP_OPEN_PAREN)
3581         ife->trueexpr = parse_result (result, matcher);
3582       else
3583         ife->trueexpr = parse_op ();
3584       eat_token (CPP_CLOSE_PAREN);
3585       if (peek ()->type != CPP_OPEN_PAREN
3586           || !peek_ident ("if", 2))
3587         fatal_at (token, "switch can be implemented with a single if");
3588       while  (peek ()->type != CPP_CLOSE_PAREN)
3589         {
3590           if (peek ()->type == CPP_OPEN_PAREN)
3591             {
3592               if (peek_ident ("if", 2))
3593                 {
3594                   ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
3595                   eat_ident ("if");
3596                   ife->falseexpr = new if_expr (ifloc);
3597                   ife = as_a <if_expr *> (ife->falseexpr);
3598                   ife->cond = parse_c_expr (CPP_OPEN_PAREN);
3599                   if (peek ()->type == CPP_OPEN_PAREN)
3600                     ife->trueexpr = parse_result (result, matcher);
3601                   else
3602                     ife->trueexpr = parse_op ();
3603                   eat_token (CPP_CLOSE_PAREN);
3604                 }
3605               else
3606                 {
3607                   /* switch default clause */
3608                   ife->falseexpr = parse_result (result, matcher);
3609                   eat_token (CPP_CLOSE_PAREN);
3610                   return res;
3611                 }
3612             }
3613           else
3614             {
3615               /* switch default clause */
3616               ife->falseexpr = parse_op ();
3617               eat_token (CPP_CLOSE_PAREN);
3618               return res;
3619             }
3620         }
3621       eat_token (CPP_CLOSE_PAREN);
3622       return res;
3623     }
3624   else
3625     {
3626       operand *op = result;
3627       if (!matcher)
3628         op = parse_expr ();
3629       eat_token (CPP_CLOSE_PAREN);
3630       return op;
3631     }
3632 }
3633
3634 /* Parse
3635      simplify = 'simplify' <expr> <result-op>
3636    or
3637      match = 'match' <ident> <expr> [<result-op>]
3638    and fill SIMPLIFIERS with the results.  */
3639
3640 void
3641 parser::parse_simplify (simplify::simplify_kind kind,
3642                         vec<simplify *>& simplifiers, predicate_id *matcher,
3643                         operand *result)
3644 {
3645   /* Reset the capture map.  */
3646   if (!capture_ids)
3647     capture_ids = new cid_map_t;
3648   /* Reset oper_lists and set.  */
3649   hash_set <user_id *> olist;
3650   oper_lists_set = &olist;
3651   oper_lists = vNULL;
3652
3653   const cpp_token *loc = peek ();
3654   parsing_match_operand = true;
3655   struct operand *match = parse_op ();
3656   parsing_match_operand = false;
3657   if (match->type == operand::OP_CAPTURE && !matcher)
3658     fatal_at (loc, "outermost expression cannot be captured");
3659   if (match->type == operand::OP_EXPR
3660       && is_a <predicate_id *> (as_a <expr *> (match)->operation))
3661     fatal_at (loc, "outermost expression cannot be a predicate");
3662
3663   /* Splice active_ifs onto result and continue parsing the
3664      "then" expr.  */
3665   if_expr *active_if = NULL;
3666   for (int i = active_ifs.length (); i > 0; --i)
3667     {
3668       if_expr *ifc = new if_expr (active_ifs[i-1]->location);
3669       ifc->cond = active_ifs[i-1];
3670       ifc->trueexpr = active_if;
3671       active_if = ifc;
3672     }
3673   if_expr *outermost_if = active_if;
3674   while (active_if && active_if->trueexpr)
3675     active_if = as_a <if_expr *> (active_if->trueexpr);
3676
3677   const cpp_token *token = peek ();
3678
3679   /* If this if is immediately closed then it is part of a predicate
3680      definition.  Push it.  */
3681   if (token->type == CPP_CLOSE_PAREN)
3682     {
3683       if (!matcher)
3684         fatal_at (token, "expected transform expression");
3685       if (active_if)
3686         {
3687           active_if->trueexpr = result;
3688           result = outermost_if;
3689         }
3690       push_simplify (kind, simplifiers, match, result);
3691       return;
3692     }
3693
3694   operand *tem = parse_result (result, matcher);
3695   if (active_if)
3696     {
3697       active_if->trueexpr = tem;
3698       result = outermost_if;
3699     }
3700   else
3701     result = tem;
3702
3703   push_simplify (kind, simplifiers, match, result);
3704 }
3705
3706 /* Parsing of the outer control structures.  */
3707
3708 /* Parse a for expression
3709      for = '(' 'for' <subst>... <pattern> ')'
3710      subst = <ident> '(' <ident>... ')'  */
3711
3712 void
3713 parser::parse_for (source_location)
3714 {
3715   auto_vec<const cpp_token *> user_id_tokens;
3716   vec<user_id *> user_ids = vNULL;
3717   const cpp_token *token;
3718   unsigned min_n_opers = 0, max_n_opers = 0;
3719
3720   while (1)
3721     {
3722       token = peek ();
3723       if (token->type != CPP_NAME)
3724         break;
3725
3726       /* Insert the user defined operators into the operator hash.  */
3727       const char *id = get_ident ();
3728       if (get_operator (id) != NULL)
3729         fatal_at (token, "operator already defined");
3730       user_id *op = new user_id (id);
3731       id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
3732       *slot = op;
3733       user_ids.safe_push (op);
3734       user_id_tokens.safe_push (token);
3735
3736       eat_token (CPP_OPEN_PAREN);
3737
3738       int arity = -1;
3739       while ((token = peek_ident ()) != 0)
3740         {
3741           const char *oper = get_ident ();
3742           id_base *idb = get_operator (oper);
3743           if (idb == NULL)
3744             fatal_at (token, "no such operator '%s'", oper);
3745           if (*idb == CONVERT0 || *idb == CONVERT1 || *idb == CONVERT2
3746               || *idb == VIEW_CONVERT0 || *idb == VIEW_CONVERT1
3747               || *idb == VIEW_CONVERT2)
3748             fatal_at (token, "conditional operators cannot be used inside for");
3749
3750           if (arity == -1)
3751             arity = idb->nargs;
3752           else if (idb->nargs == -1)
3753             ;
3754           else if (idb->nargs != arity)
3755             fatal_at (token, "operator '%s' with arity %d does not match "
3756                       "others with arity %d", oper, idb->nargs, arity);
3757
3758           user_id *p = dyn_cast<user_id *> (idb);
3759           if (p)
3760             {
3761               if (p->is_oper_list)
3762                 op->substitutes.safe_splice (p->substitutes);
3763               else
3764                 fatal_at (token, "iterator cannot be used as operator-list");
3765             }
3766           else
3767             op->substitutes.safe_push (idb);
3768         }
3769       op->nargs = arity;
3770       token = expect (CPP_CLOSE_PAREN);
3771
3772       unsigned nsubstitutes = op->substitutes.length ();
3773       if (nsubstitutes == 0)
3774         fatal_at (token, "A user-defined operator must have at least "
3775                   "one substitution");
3776       if (max_n_opers == 0)
3777         {
3778           min_n_opers = nsubstitutes;
3779           max_n_opers = nsubstitutes;
3780         }
3781       else
3782         {
3783           if (nsubstitutes % min_n_opers != 0
3784               && min_n_opers % nsubstitutes != 0)
3785             fatal_at (token, "All user-defined identifiers must have a "
3786                       "multiple number of operator substitutions of the "
3787                       "smallest number of substitutions");
3788           if (nsubstitutes < min_n_opers)
3789             min_n_opers = nsubstitutes;
3790           else if (nsubstitutes > max_n_opers)
3791             max_n_opers = nsubstitutes;
3792         }
3793     }
3794
3795   unsigned n_ids = user_ids.length ();
3796   if (n_ids == 0)
3797     fatal_at (token, "for requires at least one user-defined identifier");
3798
3799   token = peek ();
3800   if (token->type == CPP_CLOSE_PAREN)
3801     fatal_at (token, "no pattern defined in for");
3802
3803   active_fors.safe_push (user_ids);
3804   while (1)
3805     {
3806       token = peek ();
3807       if (token->type == CPP_CLOSE_PAREN)
3808         break;
3809       parse_pattern ();
3810     }
3811   active_fors.pop ();
3812
3813   /* Remove user-defined operators from the hash again.  */
3814   for (unsigned i = 0; i < user_ids.length (); ++i)
3815     {
3816       if (!user_ids[i]->used)
3817         warning_at (user_id_tokens[i],
3818                     "operator %s defined but not used", user_ids[i]->id);
3819       operators->remove_elt (user_ids[i]);
3820     }
3821 }
3822
3823 /* Parse an identifier associated with a list of operators.
3824      oprs = '(' 'define_operator_list' <ident> <ident>... ')'  */
3825
3826 void
3827 parser::parse_operator_list (source_location)
3828 {
3829   const cpp_token *token = peek ();
3830   const char *id = get_ident ();
3831
3832   if (get_operator (id) != 0)
3833     fatal_at (token, "operator %s already defined", id);
3834
3835   user_id *op = new user_id (id, true);
3836   int arity = -1;
3837
3838   while ((token = peek_ident ()) != 0)
3839     {
3840       token = peek ();
3841       const char *oper = get_ident ();
3842       id_base *idb = get_operator (oper);
3843
3844       if (idb == 0)
3845         fatal_at (token, "no such operator '%s'", oper);
3846
3847       if (arity == -1)
3848         arity = idb->nargs;
3849       else if (idb->nargs == -1)
3850         ;
3851       else if (arity != idb->nargs)
3852         fatal_at (token, "operator '%s' with arity %d does not match "
3853                          "others with arity %d", oper, idb->nargs, arity);
3854
3855       /* We allow composition of multiple operator lists.  */
3856       if (user_id *p = dyn_cast<user_id *> (idb))
3857         op->substitutes.safe_splice (p->substitutes);
3858       else
3859         op->substitutes.safe_push (idb);
3860     }
3861
3862   // Check that there is no junk after id-list
3863   token = peek();
3864   if (token->type != CPP_CLOSE_PAREN)
3865     fatal_at (token, "expected identifier got %s", cpp_type2name (token->type, 0));
3866
3867   if (op->substitutes.length () == 0)
3868     fatal_at (token, "operator-list cannot be empty");
3869
3870   op->nargs = arity;
3871   id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
3872   *slot = op;
3873 }
3874
3875 /* Parse an outer if expression.
3876      if = '(' 'if' '(' <c-expr> ')' <pattern> ')'  */
3877
3878 void
3879 parser::parse_if (source_location)
3880 {
3881   c_expr *ifexpr = parse_c_expr (CPP_OPEN_PAREN);
3882
3883   const cpp_token *token = peek ();
3884   if (token->type == CPP_CLOSE_PAREN)
3885     fatal_at (token, "no pattern defined in if");
3886
3887   active_ifs.safe_push (ifexpr);
3888   while (1)
3889     {
3890       const cpp_token *token = peek ();
3891       if (token->type == CPP_CLOSE_PAREN)
3892         break;
3893
3894       parse_pattern ();
3895     }
3896   active_ifs.pop ();
3897 }
3898
3899 /* Parse a list of predefined predicate identifiers.
3900      preds = '(' 'define_predicates' <ident>... ')'  */
3901
3902 void
3903 parser::parse_predicates (source_location)
3904 {
3905   do
3906     {
3907       const cpp_token *token = peek ();
3908       if (token->type != CPP_NAME)
3909         break;
3910
3911       add_predicate (get_ident ());
3912     }
3913   while (1);
3914 }
3915
3916 /* Parse outer control structures.
3917      pattern = <preds>|<for>|<if>|<simplify>|<match>  */
3918
3919 void
3920 parser::parse_pattern ()
3921 {
3922   /* All clauses start with '('.  */
3923   eat_token (CPP_OPEN_PAREN);
3924   const cpp_token *token = peek ();
3925   const char *id = get_ident ();
3926   if (strcmp (id, "simplify") == 0)
3927     {
3928       parse_simplify (simplify::SIMPLIFY, simplifiers, NULL, NULL);
3929       capture_ids = NULL;
3930     }
3931   else if (strcmp (id, "match") == 0)
3932     {
3933       bool with_args = false;
3934       source_location e_loc = peek ()->src_loc;
3935       if (peek ()->type == CPP_OPEN_PAREN)
3936         {
3937           eat_token (CPP_OPEN_PAREN);
3938           with_args = true;
3939         }
3940       const char *name = get_ident ();
3941       id_base *id = get_operator (name);
3942       predicate_id *p;
3943       if (!id)
3944         {
3945           p = add_predicate (name);
3946           user_predicates.safe_push (p);
3947         }
3948       else if ((p = dyn_cast <predicate_id *> (id)))
3949         ;
3950       else
3951         fatal_at (token, "cannot add a match to a non-predicate ID");
3952       /* Parse (match <id> <arg>... (match-expr)) here.  */
3953       expr *e = NULL;
3954       if (with_args)
3955         {
3956           capture_ids = new cid_map_t;
3957           e = new expr (p, e_loc);
3958           while (peek ()->type == CPP_ATSIGN)
3959             e->append_op (parse_capture (NULL));
3960           eat_token (CPP_CLOSE_PAREN);
3961         }
3962       if (p->nargs != -1
3963           && ((e && e->ops.length () != (unsigned)p->nargs)
3964               || (!e && p->nargs != 0)))
3965         fatal_at (token, "non-matching number of match operands");
3966       p->nargs = e ? e->ops.length () : 0;
3967       parse_simplify (simplify::MATCH, p->matchers, p, e);
3968       capture_ids = NULL;
3969     }
3970   else if (strcmp (id, "for") == 0)
3971     parse_for (token->src_loc);
3972   else if (strcmp (id, "if") == 0)
3973     parse_if (token->src_loc);
3974   else if (strcmp (id, "define_predicates") == 0)
3975     {
3976       if (active_ifs.length () > 0
3977           || active_fors.length () > 0)
3978         fatal_at (token, "define_predicates inside if or for is not supported");
3979       parse_predicates (token->src_loc);
3980     }
3981   else if (strcmp (id, "define_operator_list") == 0)
3982     {
3983       if (active_ifs.length () > 0
3984           || active_fors.length () > 0)
3985         fatal_at (token, "operator-list inside if or for is not supported");
3986       parse_operator_list (token->src_loc);
3987     }
3988   else
3989     fatal_at (token, "expected %s'simplify', 'match', 'for' or 'if'",
3990               active_ifs.length () == 0 && active_fors.length () == 0
3991               ? "'define_predicates', " : "");
3992
3993   eat_token (CPP_CLOSE_PAREN);
3994 }
3995
3996 /* Main entry of the parser.  Repeatedly parse outer control structures.  */
3997
3998 parser::parser (cpp_reader *r_)
3999 {
4000   r = r_;
4001   active_ifs = vNULL;
4002   active_fors = vNULL;
4003   simplifiers = vNULL;
4004   oper_lists_set = NULL;
4005   oper_lists = vNULL;
4006   capture_ids = NULL;
4007   user_predicates = vNULL;
4008   parsing_match_operand = false;
4009
4010   const cpp_token *token = next ();
4011   while (token->type != CPP_EOF)
4012     {
4013       _cpp_backup_tokens (r, 1);
4014       parse_pattern ();
4015       token = next ();
4016     }
4017 }
4018
4019
4020 /* Helper for the linemap code.  */
4021
4022 static size_t
4023 round_alloc_size (size_t s)
4024 {
4025   return s;
4026 }
4027
4028
4029 /* The genmatch generator progam.  It reads from a pattern description
4030    and outputs GIMPLE or GENERIC IL matching and simplification routines.  */
4031
4032 int
4033 main (int argc, char **argv)
4034 {
4035   cpp_reader *r;
4036
4037   progname = "genmatch";
4038
4039   if (argc < 2)
4040     return 1;
4041
4042   bool gimple = true;
4043   bool verbose = false;
4044   char *input = argv[argc-1];
4045   for (int i = 1; i < argc - 1; ++i)
4046     {
4047       if (strcmp (argv[i], "--gimple") == 0)
4048         gimple = true;
4049       else if (strcmp (argv[i], "--generic") == 0)
4050         gimple = false;
4051       else if (strcmp (argv[i], "-v") == 0)
4052         verbose = true;
4053       else
4054         {
4055           fprintf (stderr, "Usage: genmatch "
4056                    "[--gimple] [--generic] [-v] input\n");
4057           return 1;
4058         }
4059     }
4060
4061   line_table = XCNEW (struct line_maps);
4062   linemap_init (line_table, 0);
4063   line_table->reallocator = xrealloc;
4064   line_table->round_alloc_size = round_alloc_size;
4065
4066   r = cpp_create_reader (CLK_GNUC99, NULL, line_table);
4067   cpp_callbacks *cb = cpp_get_callbacks (r);
4068   cb->error = error_cb;
4069
4070   if (!cpp_read_main_file (r, input))
4071     return 1;
4072   cpp_define (r, gimple ? "GIMPLE=1": "GENERIC=1");
4073   cpp_define (r, gimple ? "GENERIC=0": "GIMPLE=0");
4074
4075   /* Pre-seed operators.  */
4076   operators = new hash_table<id_base> (1024);
4077 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
4078   add_operator (SYM, # SYM, # TYPE, NARGS);
4079 #define END_OF_BASE_TREE_CODES
4080 #include "tree.def"
4081 add_operator (CONVERT0, "CONVERT0", "tcc_unary", 1);
4082 add_operator (CONVERT1, "CONVERT1", "tcc_unary", 1);
4083 add_operator (CONVERT2, "CONVERT2", "tcc_unary", 1);
4084 add_operator (VIEW_CONVERT0, "VIEW_CONVERT0", "tcc_unary", 1);
4085 add_operator (VIEW_CONVERT1, "VIEW_CONVERT1", "tcc_unary", 1);
4086 add_operator (VIEW_CONVERT2, "VIEW_CONVERT2", "tcc_unary", 1);
4087 #undef END_OF_BASE_TREE_CODES
4088 #undef DEFTREECODE
4089
4090   /* Pre-seed builtin functions.
4091      ???  Cannot use N (name) as that is targetm.emultls.get_address
4092      for BUILT_IN_EMUTLS_GET_ADDRESS ... */
4093 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
4094   add_builtin (ENUM, # ENUM);
4095 #include "builtins.def"
4096 #undef DEF_BUILTIN
4097
4098   /* Parse ahead!  */
4099   parser p (r);
4100
4101   if (gimple)
4102     write_header (stdout, "gimple-match-head.c");
4103   else
4104     write_header (stdout, "generic-match-head.c");
4105
4106   /* Go over all predicates defined with patterns and perform
4107      lowering and code generation.  */
4108   for (unsigned i = 0; i < p.user_predicates.length (); ++i)
4109     {
4110       predicate_id *pred = p.user_predicates[i];
4111       lower (pred->matchers, gimple);
4112
4113       if (verbose)
4114         for (unsigned i = 0; i < pred->matchers.length (); ++i)
4115           print_matches (pred->matchers[i]);
4116
4117       decision_tree dt;
4118       for (unsigned i = 0; i < pred->matchers.length (); ++i)
4119         dt.insert (pred->matchers[i], i);
4120
4121       if (verbose)
4122         dt.print (stderr);
4123
4124       write_predicate (stdout, pred, dt, gimple);
4125     }
4126
4127   /* Lower the main simplifiers and generate code for them.  */
4128   lower (p.simplifiers, gimple);
4129
4130   if (verbose)
4131     for (unsigned i = 0; i < p.simplifiers.length (); ++i)
4132       print_matches (p.simplifiers[i]);
4133
4134   decision_tree dt;
4135   for (unsigned i = 0; i < p.simplifiers.length (); ++i)
4136     dt.insert (p.simplifiers[i], i);
4137
4138   if (verbose)
4139     dt.print (stderr);
4140
4141   if (gimple)
4142     dt.gen_gimple (stdout);
4143   else
4144     dt.gen_generic (stdout);
4145
4146   /* Finalize.  */
4147   cpp_finish (r, NULL);
4148   cpp_destroy (r);
4149
4150   delete operators;
4151
4152   return 0;
4153 }