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