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 struct dt_simplify;
1224
1225 /* A hash-map collecting semantically equivalent leafs in the decision
1226    tree for splitting out to separate functions.  */
1227 struct sinfo
1228 {
1229   dt_simplify *s;
1230
1231   const char *fname;
1232   unsigned cnt;
1233 };
1234
1235 struct sinfo_hashmap_traits : simple_hashmap_traits <pointer_hash <dt_simplify> >
1236 {
1237   static inline hashval_t hash (const key_type &);
1238   static inline bool equal_keys (const key_type &, const key_type &);
1239   template <typename T> static inline void remove (T &) {}
1240 };
1241
1242 typedef hash_map<void * /* unused */, sinfo *, sinfo_hashmap_traits>
1243   sinfo_map_t;
1244
1245
1246 /* Decision tree base class, used for DT_TRUE and DT_NODE.  */
1247
1248 struct dt_node
1249 {
1250   enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
1251
1252   enum dt_type type;
1253   unsigned level;
1254   vec<dt_node *> kids;
1255
1256   /* Statistics.  */
1257   unsigned num_leafs;
1258   unsigned total_size;
1259   unsigned max_level;
1260
1261   dt_node (enum dt_type type_): type (type_), level (0), kids (vNULL) {}
1262
1263   dt_node *append_node (dt_node *);
1264   dt_node *append_op (operand *, dt_node *parent = 0, unsigned pos = 0);
1265   dt_node *append_true_op (dt_node *parent = 0, unsigned pos = 0);
1266   dt_node *append_match_op (dt_operand *, dt_node *parent = 0, unsigned pos = 0);
1267   dt_node *append_simplify (simplify *, unsigned, dt_operand **);
1268
1269   virtual void gen (FILE *, int, bool) {}
1270
1271   void gen_kids (FILE *, int, bool);
1272   void gen_kids_1 (FILE *, int, bool,
1273                    vec<dt_operand *>, vec<dt_operand *>, vec<dt_operand *>,
1274                    vec<dt_operand *>, vec<dt_operand *>, vec<dt_node *>);
1275
1276   void analyze (sinfo_map_t &);
1277 };
1278
1279 /* Generic decision tree node used for DT_OPERAND and DT_MATCH.  */
1280
1281 struct dt_operand : public dt_node
1282 {
1283   operand *op;
1284   dt_operand *match_dop;
1285   dt_operand *parent;
1286   unsigned pos;
1287
1288   dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_,
1289               dt_operand *parent_ = 0, unsigned pos_ = 0)
1290       : dt_node (type), op (op_), match_dop (match_dop_),
1291       parent (parent_), pos (pos_) {}
1292
1293   void gen (FILE *, int, bool);
1294   unsigned gen_predicate (FILE *, int, const char *, bool);
1295   unsigned gen_match_op (FILE *, int, const char *);
1296
1297   unsigned gen_gimple_expr (FILE *, int);
1298   unsigned gen_generic_expr (FILE *, int, const char *);
1299
1300   char *get_name (char *);
1301   void gen_opname (char *, unsigned);
1302 };
1303
1304 /* Leaf node of the decision tree, used for DT_SIMPLIFY.  */
1305
1306 struct dt_simplify : public dt_node
1307 {
1308   simplify *s;
1309   unsigned pattern_no;
1310   dt_operand **indexes;
1311   sinfo *info;
1312
1313   dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
1314         : dt_node (DT_SIMPLIFY), s (s_), pattern_no (pattern_no_),
1315           indexes (indexes_), info (NULL)  {}
1316
1317   void gen_1 (FILE *, int, bool, operand *);
1318   void gen (FILE *f, int, bool);
1319 };
1320
1321 template<>
1322 template<>
1323 inline bool
1324 is_a_helper <dt_operand *>::test (dt_node *n)
1325 {
1326   return (n->type == dt_node::DT_OPERAND
1327           || n->type == dt_node::DT_MATCH);
1328 }
1329
1330 template<>
1331 template<>
1332 inline bool
1333 is_a_helper <dt_simplify *>::test (dt_node *n)
1334 {
1335   return n->type == dt_node::DT_SIMPLIFY;
1336 }
1337
1338
1339
1340 /* A container for the actual decision tree.  */
1341
1342 struct decision_tree
1343 {
1344   dt_node *root;
1345
1346   void insert (struct simplify *, unsigned);
1347   void gen (FILE *f, bool gimple);
1348   void print (FILE *f = stderr);
1349
1350   decision_tree () { root = new dt_node (dt_node::DT_NODE); }
1351
1352   static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes,
1353                                   unsigned pos = 0, dt_node *parent = 0);
1354   static dt_node *find_node (vec<dt_node *>&, dt_node *);
1355   static bool cmp_node (dt_node *, dt_node *);
1356   static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
1357 };
1358
1359 /* Compare two AST operands O1 and O2 and return true if they are equal.  */
1360
1361 bool
1362 cmp_operand (operand *o1, operand *o2)
1363 {
1364   if (!o1 || !o2 || o1->type != o2->type)
1365     return false;
1366
1367   if (o1->type == operand::OP_PREDICATE)
1368     {
1369       predicate *p1 = as_a<predicate *>(o1);
1370       predicate *p2 = as_a<predicate *>(o2);
1371       return p1->p == p2->p;
1372     }
1373   else if (o1->type == operand::OP_EXPR)
1374     {
1375       expr *e1 = static_cast<expr *>(o1);
1376       expr *e2 = static_cast<expr *>(o2);
1377       return (e1->operation == e2->operation
1378               && e1->is_generic == e2->is_generic);
1379     }
1380   else
1381     return false;
1382 }
1383
1384 /* Compare two decision tree nodes N1 and N2 and return true if they
1385    are equal.  */
1386
1387 bool
1388 decision_tree::cmp_node (dt_node *n1, dt_node *n2)
1389 {
1390   if (!n1 || !n2 || n1->type != n2->type)
1391     return false;
1392
1393   if (n1 == n2)
1394     return true;
1395
1396   if (n1->type == dt_node::DT_TRUE)
1397     return false;
1398
1399   if (n1->type == dt_node::DT_OPERAND)
1400     return cmp_operand ((as_a<dt_operand *> (n1))->op,
1401                         (as_a<dt_operand *> (n2))->op);
1402   else if (n1->type == dt_node::DT_MATCH)
1403     return ((as_a<dt_operand *> (n1))->match_dop
1404             == (as_a<dt_operand *> (n2))->match_dop);
1405   return false;
1406 }
1407
1408 /* Search OPS for a decision tree node like P and return it if found.  */
1409
1410 dt_node *
1411 decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
1412 {
1413   /* We can merge adjacent DT_TRUE.  */
1414   if (p->type == dt_node::DT_TRUE
1415       && !ops.is_empty ()
1416       && ops.last ()->type == dt_node::DT_TRUE)
1417     return ops.last ();
1418   for (int i = ops.length () - 1; i >= 0; --i)
1419     {
1420       /* But we can't merge across DT_TRUE nodes as they serve as
1421          pattern order barriers to make sure that patterns apply
1422          in order of appearance in case multiple matches are possible.  */
1423       if (ops[i]->type == dt_node::DT_TRUE)
1424         return NULL;
1425       if (decision_tree::cmp_node (ops[i], p))
1426         return ops[i];
1427     }
1428   return NULL;
1429 }
1430
1431 /* Append N to the decision tree if it there is not already an existing
1432    identical child.  */
1433
1434 dt_node *
1435 dt_node::append_node (dt_node *n)
1436 {
1437   dt_node *kid;
1438
1439   kid = decision_tree::find_node (kids, n);
1440   if (kid)
1441     return kid;
1442
1443   kids.safe_push (n);
1444   n->level = this->level + 1;
1445
1446   return n;
1447 }
1448
1449 /* Append OP to the decision tree.  */
1450
1451 dt_node *
1452 dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
1453 {
1454   dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1455   dt_operand *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos);
1456   return append_node (n);
1457 }
1458
1459 /* Append a DT_TRUE decision tree node.  */
1460
1461 dt_node *
1462 dt_node::append_true_op (dt_node *parent, unsigned pos)
1463 {
1464   dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1465   dt_operand *n = new dt_operand (DT_TRUE, 0, 0, parent_, pos);
1466   return append_node (n);
1467 }
1468
1469 /* Append a DT_MATCH decision tree node.  */
1470
1471 dt_node *
1472 dt_node::append_match_op (dt_operand *match_dop, dt_node *parent, unsigned pos)
1473 {
1474   dt_operand *parent_ = as_a<dt_operand *> (parent);
1475   dt_operand *n = new dt_operand (DT_MATCH, 0, match_dop, parent_, pos);
1476   return append_node (n);
1477 }
1478
1479 /* Append S to the decision tree.  */
1480
1481 dt_node *
1482 dt_node::append_simplify (simplify *s, unsigned pattern_no,
1483                           dt_operand **indexes)
1484 {
1485   dt_simplify *n = new dt_simplify (s, pattern_no, indexes);
1486   return append_node (n);
1487 }
1488
1489 /* Analyze the node and its children.  */
1490
1491 void
1492 dt_node::analyze (sinfo_map_t &map)
1493 {
1494   num_leafs = 0;
1495   total_size = 1;
1496   max_level = level;
1497
1498   if (type == DT_SIMPLIFY)
1499     {
1500       /* Populate the map of equivalent simplifies.  */
1501       dt_simplify *s = as_a <dt_simplify *> (this);
1502       bool existed;
1503       sinfo *&si = map.get_or_insert (s, &existed);
1504       if (!existed)
1505         {
1506           si = new sinfo;
1507           si->s = s;
1508           si->cnt = 1;
1509           si->fname = NULL;
1510         }
1511       else
1512         si->cnt++;
1513       s->info = si;
1514       num_leafs = 1;
1515       return;
1516     }
1517
1518   for (unsigned i = 0; i < kids.length (); ++i)
1519     {
1520       kids[i]->analyze (map);
1521       num_leafs += kids[i]->num_leafs;
1522       total_size += kids[i]->total_size;
1523       max_level = MAX (max_level, kids[i]->max_level);
1524     }
1525 }
1526
1527 /* Insert O into the decision tree and return the decision tree node found
1528    or created.  */
1529
1530 dt_node *
1531 decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
1532                                unsigned pos, dt_node *parent)
1533 {
1534   dt_node *q, *elm = 0;
1535
1536   if (capture *c = dyn_cast<capture *> (o))
1537     {
1538       unsigned capt_index = c->where;
1539
1540       if (indexes[capt_index] == 0)
1541         {
1542           if (c->what)
1543             q = insert_operand (p, c->what, indexes, pos, parent);
1544           else
1545             {
1546               q = elm = p->append_true_op (parent, pos);
1547               goto at_assert_elm;
1548             }
1549           // get to the last capture
1550           for (operand *what = c->what;
1551                what && is_a<capture *> (what);
1552                c = as_a<capture *> (what), what = c->what)
1553             ;
1554
1555           if (!c->what)
1556             {
1557               unsigned cc_index = c->where;
1558               dt_operand *match_op = indexes[cc_index];
1559
1560               dt_operand temp (dt_node::DT_TRUE, 0, 0);
1561               elm = decision_tree::find_node (p->kids, &temp);
1562
1563               if (elm == 0)
1564                 {
1565                   dt_operand temp (dt_node::DT_MATCH, 0, match_op);
1566                   elm = decision_tree::find_node (p->kids, &temp);
1567                 }
1568             }
1569           else
1570             {
1571               dt_operand temp (dt_node::DT_OPERAND, c->what, 0);
1572               elm = decision_tree::find_node (p->kids, &temp);
1573             }
1574
1575 at_assert_elm:
1576           gcc_assert (elm->type == dt_node::DT_TRUE
1577                       || elm->type == dt_node::DT_OPERAND
1578                       || elm->type == dt_node::DT_MATCH);
1579           indexes[capt_index] = static_cast<dt_operand *> (elm);
1580           return q;
1581         }
1582       else
1583         {
1584           p = p->append_match_op (indexes[capt_index], parent, pos);
1585           if (c->what)
1586             return insert_operand (p, c->what, indexes, 0, p);
1587           else
1588             return p;
1589         }
1590     }
1591   p = p->append_op (o, parent, pos);
1592   q = p;
1593
1594   if (expr *e = dyn_cast <expr *>(o))
1595     {
1596       for (unsigned i = 0; i < e->ops.length (); ++i)
1597         q = decision_tree::insert_operand (q, e->ops[i], indexes, i, p);
1598     }
1599
1600   return q;
1601 }
1602
1603 /* Insert S into the decision tree.  */
1604
1605 void
1606 decision_tree::insert (struct simplify *s, unsigned pattern_no)
1607 {
1608   dt_operand **indexes = XCNEWVEC (dt_operand *, s->capture_max + 1);
1609   dt_node *p = decision_tree::insert_operand (root, s->match, indexes);
1610   p->append_simplify (s, pattern_no, indexes);
1611 }
1612
1613 /* Debug functions to dump the decision tree.  */
1614
1615 DEBUG_FUNCTION void
1616 decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
1617 {
1618   if (p->type == dt_node::DT_NODE)
1619     fprintf (f, "root");
1620   else
1621     {
1622       fprintf (f, "|");
1623       for (unsigned i = 0; i < indent; i++)
1624         fprintf (f, "-");
1625
1626       if (p->type == dt_node::DT_OPERAND)
1627         {
1628           dt_operand *dop = static_cast<dt_operand *>(p);
1629           print_operand (dop->op, f, true);
1630         }
1631       else if (p->type == dt_node::DT_TRUE)
1632         fprintf (f, "true");
1633       else if (p->type == dt_node::DT_MATCH)
1634         fprintf (f, "match (%p)", (void *)((as_a<dt_operand *>(p))->match_dop));
1635       else if (p->type == dt_node::DT_SIMPLIFY)
1636         {
1637           dt_simplify *s = static_cast<dt_simplify *> (p);
1638           fprintf (f, "simplify_%u { ", s->pattern_no);
1639           for (int i = 0; i <= s->s->capture_max; ++i)
1640             fprintf (f, "%p, ", (void *) s->indexes[i]);
1641           fprintf (f, " } ");
1642         }
1643     }
1644
1645   fprintf (stderr, " (%p), %u, %u\n", (void *) p, p->level, p->kids.length ());
1646
1647   for (unsigned i = 0; i < p->kids.length (); ++i)
1648     decision_tree::print_node (p->kids[i], f, indent + 2);
1649 }
1650
1651 DEBUG_FUNCTION void
1652 decision_tree::print (FILE *f)
1653 {
1654   return decision_tree::print_node (root, f);
1655 }
1656
1657
1658 /* For GENERIC we have to take care of wrapping multiple-used
1659    expressions with side-effects in save_expr and preserve side-effects
1660    of expressions with omit_one_operand.  Analyze captures in
1661    match, result and with expressions and perform early-outs
1662    on the outermost match expression operands for cases we cannot
1663    handle.  */
1664
1665 struct capture_info
1666 {
1667   capture_info (simplify *s, operand *, bool);
1668   void walk_match (operand *o, unsigned toplevel_arg, bool, bool);
1669   bool walk_result (operand *o, bool, operand *);
1670   void walk_c_expr (c_expr *);
1671
1672   struct cinfo
1673     {
1674       bool expr_p;
1675       bool cse_p;
1676       bool force_no_side_effects_p;
1677       bool force_single_use;
1678       bool cond_expr_cond_p;
1679       unsigned long toplevel_msk;
1680       int result_use_count;
1681       unsigned same_as;
1682       capture *c;
1683     };
1684
1685   auto_vec<cinfo> info;
1686   unsigned long force_no_side_effects;
1687   bool gimple;
1688 };
1689
1690 /* Analyze captures in S.  */
1691
1692 capture_info::capture_info (simplify *s, operand *result, bool gimple_)
1693 {
1694   gimple = gimple_;
1695
1696   expr *e;
1697   if (s->kind == simplify::MATCH)
1698     {
1699       force_no_side_effects = -1;
1700       return;
1701     }
1702
1703   force_no_side_effects = 0;
1704   info.safe_grow_cleared (s->capture_max + 1);
1705   for (int i = 0; i <= s->capture_max; ++i)
1706     info[i].same_as = i;
1707
1708   e = as_a <expr *> (s->match);
1709   for (unsigned i = 0; i < e->ops.length (); ++i)
1710     walk_match (e->ops[i], i,
1711                 (i != 0 && *e->operation == COND_EXPR)
1712                 || *e->operation == TRUTH_ANDIF_EXPR
1713                 || *e->operation == TRUTH_ORIF_EXPR,
1714                 i == 0
1715                 && (*e->operation == COND_EXPR
1716                     || *e->operation == VEC_COND_EXPR));
1717
1718   walk_result (s->result, false, result);
1719 }
1720
1721 /* Analyze captures in the match expression piece O.  */
1722
1723 void
1724 capture_info::walk_match (operand *o, unsigned toplevel_arg,
1725                           bool conditional_p, bool cond_expr_cond_p)
1726 {
1727   if (capture *c = dyn_cast <capture *> (o))
1728     {
1729       unsigned where = c->where;
1730       info[where].toplevel_msk |= 1 << toplevel_arg;
1731       info[where].force_no_side_effects_p |= conditional_p;
1732       info[where].cond_expr_cond_p |= cond_expr_cond_p;
1733       if (!info[where].c)
1734         info[where].c = c;
1735       if (!c->what)
1736         return;
1737       /* Recurse to exprs and captures.  */
1738       if (is_a <capture *> (c->what)
1739           || is_a <expr *> (c->what))
1740         walk_match (c->what, toplevel_arg, conditional_p, false);
1741       /* We need to look past multiple captures to find a captured
1742          expression as with conditional converts two captures
1743          can be collapsed onto the same expression.  Also collect
1744          what captures capture the same thing.  */
1745       while (c->what && is_a <capture *> (c->what))
1746         {
1747           c = as_a <capture *> (c->what);
1748           if (info[c->where].same_as != c->where
1749               && info[c->where].same_as != info[where].same_as)
1750             fatal_at (c->location, "cannot handle this collapsed capture");
1751           info[c->where].same_as = info[where].same_as;
1752         }
1753       /* Mark expr (non-leaf) captures and forced single-use exprs.  */
1754       expr *e;
1755       if (c->what
1756           && (e = dyn_cast <expr *> (c->what)))
1757         {
1758           info[where].expr_p = true;
1759           info[where].force_single_use |= e->force_single_use;
1760         }
1761     }
1762   else if (expr *e = dyn_cast <expr *> (o))
1763     {
1764       for (unsigned i = 0; i < e->ops.length (); ++i)
1765         {
1766           bool cond_p = conditional_p;
1767           bool cond_expr_cond_p = false;
1768           if (i != 0 && *e->operation == COND_EXPR)
1769             cond_p = true;
1770           else if (*e->operation == TRUTH_ANDIF_EXPR
1771                    || *e->operation == TRUTH_ORIF_EXPR)
1772             cond_p = true;
1773           if (i == 0
1774               && (*e->operation == COND_EXPR
1775                   || *e->operation == VEC_COND_EXPR))
1776             cond_expr_cond_p = true;
1777           walk_match (e->ops[i], toplevel_arg, cond_p, cond_expr_cond_p);
1778         }
1779     }
1780   else if (is_a <predicate *> (o))
1781     {
1782       /* Mark non-captured leafs toplevel arg for checking.  */
1783       force_no_side_effects |= 1 << toplevel_arg;
1784       if (verbose >= 1
1785           && !gimple)
1786         warning_at (o->location,
1787                     "forcing no side-effects on possibly lost leaf");
1788     }
1789   else
1790     gcc_unreachable ();
1791 }
1792
1793 /* Analyze captures in the result expression piece O.  Return true
1794    if RESULT was visited in one of the children.  Only visit
1795    non-if/with children if they are rooted on RESULT.  */
1796
1797 bool
1798 capture_info::walk_result (operand *o, bool conditional_p, operand *result)
1799 {
1800   if (capture *c = dyn_cast <capture *> (o))
1801     {
1802       unsigned where = info[c->where].same_as;
1803       info[where].result_use_count++;
1804       /* If we substitute an expression capture we don't know
1805          which captures this will end up using (well, we don't
1806          compute that).  Force the uses to be side-effect free
1807          which means forcing the toplevels that reach the
1808          expression side-effect free.  */
1809       if (info[where].expr_p)
1810         force_no_side_effects |= info[where].toplevel_msk;
1811       /* Mark CSE capture uses as forced to have no side-effects. */
1812       if (c->what
1813           && is_a <expr *> (c->what))
1814         {
1815           info[where].cse_p = true;
1816           walk_result (c->what, true, result);
1817         }
1818     }
1819   else if (expr *e = dyn_cast <expr *> (o))
1820     {
1821       for (unsigned i = 0; i < e->ops.length (); ++i)
1822         {
1823           bool cond_p = conditional_p;
1824           if (i != 0 && *e->operation == COND_EXPR)
1825             cond_p = true;
1826           else if (*e->operation == TRUTH_ANDIF_EXPR
1827                    || *e->operation == TRUTH_ORIF_EXPR)
1828             cond_p = true;
1829           walk_result (e->ops[i], cond_p, result);
1830         }
1831     }
1832   else if (if_expr *e = dyn_cast <if_expr *> (o))
1833     {
1834       /* 'if' conditions should be all fine.  */
1835       if (e->trueexpr == result)
1836         {
1837           walk_result (e->trueexpr, false, result);
1838           return true;
1839         }
1840       if (e->falseexpr == result)
1841         {
1842           walk_result (e->falseexpr, false, result);
1843           return true;
1844         }
1845       bool res = false;
1846       if (is_a <if_expr *> (e->trueexpr)
1847           || is_a <with_expr *> (e->trueexpr))
1848         res |= walk_result (e->trueexpr, false, result);
1849       if (e->falseexpr
1850           && (is_a <if_expr *> (e->falseexpr)
1851               || is_a <with_expr *> (e->falseexpr)))
1852         res |= walk_result (e->falseexpr, false, result);
1853       return res;
1854     }
1855   else if (with_expr *e = dyn_cast <with_expr *> (o))
1856     {
1857       bool res = (e->subexpr == result);
1858       if (res
1859           || is_a <if_expr *> (e->subexpr)
1860           || is_a <with_expr *> (e->subexpr))
1861         res |= walk_result (e->subexpr, false, result);
1862       if (res)
1863         walk_c_expr (e->with);
1864       return res;
1865     }
1866   else if (c_expr *e = dyn_cast <c_expr *> (o))
1867     walk_c_expr (e);
1868   else
1869     gcc_unreachable ();
1870
1871   return false;
1872 }
1873
1874 /* Look for captures in the C expr E.  */
1875
1876 void
1877 capture_info::walk_c_expr (c_expr *e)
1878 {
1879   /* Give up for C exprs mentioning captures not inside TREE_TYPE,
1880      TREE_REAL_CST, TREE_CODE or a predicate where they cannot
1881      really escape through.  */
1882   unsigned p_depth = 0;
1883   for (unsigned i = 0; i < e->code.length (); ++i)
1884     {
1885       const cpp_token *t = &e->code[i];
1886       const cpp_token *n = i < e->code.length () - 1 ? &e->code[i+1] : NULL;
1887       id_base *id;
1888       if (t->type == CPP_NAME
1889           && (strcmp ((const char *)CPP_HASHNODE
1890                       (t->val.node.node)->ident.str, "TREE_TYPE") == 0
1891               || strcmp ((const char *)CPP_HASHNODE
1892                          (t->val.node.node)->ident.str, "TREE_CODE") == 0
1893               || strcmp ((const char *)CPP_HASHNODE
1894                          (t->val.node.node)->ident.str, "TREE_REAL_CST") == 0
1895               || ((id = get_operator ((const char *)CPP_HASHNODE
1896                                       (t->val.node.node)->ident.str))
1897                   && is_a <predicate_id *> (id)))
1898           && n->type == CPP_OPEN_PAREN)
1899         p_depth++;
1900       else if (t->type == CPP_CLOSE_PAREN
1901                && p_depth > 0)
1902         p_depth--;
1903       else if (p_depth == 0
1904                && t->type == CPP_ATSIGN
1905                && (n->type == CPP_NUMBER
1906                    || n->type == CPP_NAME)
1907                && !(n->flags & PREV_WHITE))
1908         {
1909           const char *id;
1910           if (n->type == CPP_NUMBER)
1911             id = (const char *)n->val.str.text;
1912           else
1913             id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
1914           unsigned where = *e->capture_ids->get(id);
1915           info[info[where].same_as].force_no_side_effects_p = true;
1916           if (verbose >= 1
1917               && !gimple)
1918             warning_at (t, "capture escapes");
1919         }
1920     }
1921 }
1922
1923
1924 /* Code generation off the decision tree and the refered AST nodes.  */
1925
1926 bool
1927 is_conversion (id_base *op)
1928 {
1929   return (*op == CONVERT_EXPR
1930           || *op == NOP_EXPR
1931           || *op == FLOAT_EXPR
1932           || *op == FIX_TRUNC_EXPR
1933           || *op == VIEW_CONVERT_EXPR);
1934 }
1935
1936 /* Get the type to be used for generating operands of OP from the
1937    various sources.  */
1938
1939 static const char *
1940 get_operand_type (id_base *op, const char *in_type,
1941                   const char *expr_type,
1942                   const char *other_oprnd_type)
1943 {
1944   /* Generally operands whose type does not match the type of the
1945      expression generated need to know their types but match and
1946      thus can fall back to 'other_oprnd_type'.  */
1947   if (is_conversion (op))
1948     return other_oprnd_type;
1949   else if (*op == REALPART_EXPR
1950            || *op == IMAGPART_EXPR)
1951     return other_oprnd_type;
1952   else if (is_a <operator_id *> (op)
1953            && strcmp (as_a <operator_id *> (op)->tcc, "tcc_comparison") == 0)
1954     return other_oprnd_type;
1955   else
1956     {
1957       /* Otherwise all types should match - choose one in order of
1958          preference.  */
1959       if (expr_type)
1960         return expr_type;
1961       else if (in_type)
1962         return in_type;
1963       else
1964         return other_oprnd_type;
1965     }
1966 }
1967
1968 /* Generate transform code for an expression.  */
1969
1970 void
1971 expr::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
1972                      int depth, const char *in_type, capture_info *cinfo,
1973                      dt_operand **indexes, bool)
1974 {
1975   bool conversion_p = is_conversion (operation);
1976   const char *type = expr_type;
1977   char optype[64];
1978   if (type)
1979     /* If there was a type specification in the pattern use it.  */
1980     ;
1981   else if (conversion_p)
1982     /* For conversions we need to build the expression using the
1983        outer type passed in.  */
1984     type = in_type;
1985   else if (*operation == REALPART_EXPR
1986            || *operation == IMAGPART_EXPR)
1987     {
1988       /* __real and __imag use the component type of its operand.  */
1989       sprintf (optype, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth);
1990       type = optype;
1991     }
1992   else if (is_a <operator_id *> (operation)
1993            && !strcmp (as_a <operator_id *> (operation)->tcc, "tcc_comparison"))
1994     {
1995       /* comparisons use boolean_type_node (or what gets in), but
1996          their operands need to figure out the types themselves.  */
1997       sprintf (optype, "boolean_type_node");
1998       type = optype;
1999     }
2000   else if (*operation == COND_EXPR
2001            || *operation == VEC_COND_EXPR)
2002     {
2003       /* Conditions are of the same type as their first alternative.  */
2004       sprintf (optype, "TREE_TYPE (ops%d[1])", depth);
2005       type = optype;
2006     }
2007   else
2008     {
2009       /* Other operations are of the same type as their first operand.  */
2010       sprintf (optype, "TREE_TYPE (ops%d[0])", depth);
2011       type = optype;
2012     }
2013   if (!type)
2014     fatal_at (location, "cannot determine type of operand");
2015
2016   fprintf_indent (f, indent, "{\n");
2017   indent += 2;
2018   fprintf_indent (f, indent, "tree ops%d[%u], res;\n", depth, ops.length ());
2019   char op0type[64];
2020   snprintf (op0type, 64, "TREE_TYPE (ops%d[0])", depth);
2021   for (unsigned i = 0; i < ops.length (); ++i)
2022     {
2023       char dest[32];
2024       snprintf (dest, 32, "ops%d[%u]", depth, i);
2025       const char *optype
2026         = get_operand_type (operation, in_type, expr_type,
2027                             i == 0 ? NULL : op0type);
2028       ops[i]->gen_transform (f, indent, dest, gimple, depth + 1, optype,
2029                              cinfo, indexes,
2030                              ((!(*operation == COND_EXPR)
2031                                && !(*operation == VEC_COND_EXPR))
2032                               || i != 0));
2033     }
2034
2035   const char *opr;
2036   if (*operation == CONVERT_EXPR)
2037     opr = "NOP_EXPR";
2038   else
2039     opr = operation->id;
2040
2041   if (gimple)
2042     {
2043       if (*operation == CONVERT_EXPR)
2044         {
2045           fprintf_indent (f, indent,
2046                           "if (%s != TREE_TYPE (ops%d[0])\n",
2047                           type, depth);
2048           fprintf_indent (f, indent,
2049                           "    && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2050                           type, depth);
2051           fprintf_indent (f, indent + 2, "{\n");
2052           indent += 4;
2053         }
2054       /* ???  Building a stmt can fail for various reasons here, seq being
2055          NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2056          So if we fail here we should continue matching other patterns.  */
2057       fprintf_indent (f, indent, "code_helper tem_code = %s;\n", opr);
2058       fprintf_indent (f, indent, "tree tem_ops[3] = { ");
2059       for (unsigned i = 0; i < ops.length (); ++i)
2060         fprintf (f, "ops%d[%u]%s", depth, i,
2061                  i == ops.length () - 1 ? " };\n" : ", ");
2062       fprintf_indent (f, indent,
2063                       "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
2064                       ops.length (), type);
2065       fprintf_indent (f, indent,
2066                       "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
2067                       type);
2068       fprintf_indent (f, indent,
2069                       "if (!res) return false;\n");
2070       if (*operation == CONVERT_EXPR)
2071         {
2072           indent -= 4;
2073           fprintf_indent (f, indent, "  }\n");
2074           fprintf_indent (f, indent, "else\n");
2075           fprintf_indent (f, indent, "  res = ops%d[0];\n", depth);
2076         }
2077     }
2078   else
2079     {
2080       if (*operation == CONVERT_EXPR)
2081         {
2082           fprintf_indent (f, indent, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2083                           depth, type);
2084           indent += 2;
2085         }
2086       if (operation->kind == id_base::CODE)
2087         fprintf_indent (f, indent, "res = fold_build%d_loc (loc, %s, %s",
2088                         ops.length(), opr, type);
2089       else
2090         fprintf_indent (f, indent, "res = build_call_expr_loc (loc, "
2091                         "builtin_decl_implicit (%s), %d", opr, ops.length());
2092       for (unsigned i = 0; i < ops.length (); ++i)
2093         fprintf (f, ", ops%d[%u]", depth, i);
2094       fprintf (f, ");\n");
2095       if (*operation == CONVERT_EXPR)
2096         {
2097           indent -= 2;
2098           fprintf_indent (f, indent, "else\n");
2099           fprintf_indent (f, indent, "  res = ops%d[0];\n", depth);
2100         }
2101     }
2102   fprintf_indent (f, indent, "%s = res;\n", dest);
2103   indent -= 2;
2104   fprintf_indent (f, indent, "}\n");
2105 }
2106
2107 /* Generate code for a c_expr which is either the expression inside
2108    an if statement or a sequence of statements which computes a
2109    result to be stored to DEST.  */
2110
2111 void
2112 c_expr::gen_transform (FILE *f, int indent, const char *dest,
2113                        bool, int, const char *, capture_info *,
2114                        dt_operand **, bool)
2115 {
2116   if (dest && nr_stmts == 1)
2117     fprintf_indent (f, indent, "%s = ", dest);
2118
2119   unsigned stmt_nr = 1;
2120   for (unsigned i = 0; i < code.length (); ++i)
2121     {
2122       const cpp_token *token = &code[i];
2123
2124       /* Replace captures for code-gen.  */
2125       if (token->type == CPP_ATSIGN)
2126         {
2127           const cpp_token *n = &code[i+1];
2128           if ((n->type == CPP_NUMBER
2129                || n->type == CPP_NAME)
2130               && !(n->flags & PREV_WHITE))
2131             {
2132               if (token->flags & PREV_WHITE)
2133                 fputc (' ', f);
2134               const char *id;
2135               if (n->type == CPP_NUMBER)
2136                 id = (const char *)n->val.str.text;
2137               else
2138                 id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2139               unsigned *cid = capture_ids->get (id);
2140               if (!cid)
2141                 fatal_at (token, "unknown capture id");
2142               fprintf (f, "captures[%u]", *cid);
2143               ++i;
2144               continue;
2145             }
2146         }
2147
2148       if (token->flags & PREV_WHITE)
2149         fputc (' ', f);
2150
2151       if (token->type == CPP_NAME)
2152         {
2153           const char *id = (const char *) NODE_NAME (token->val.node.node);
2154           unsigned j;
2155           for (j = 0; j < ids.length (); ++j)
2156             {
2157             if (strcmp (id, ids[j].id) == 0)
2158               {
2159                 fprintf (f, "%s", ids[j].oper);
2160                 break;
2161               }
2162             }
2163           if (j < ids.length ())
2164             continue;
2165         }
2166
2167       /* Output the token as string.  */
2168       char *tk = (char *)cpp_token_as_text (r, token);
2169       fputs (tk, f);
2170
2171       if (token->type == CPP_SEMICOLON)
2172         {
2173           stmt_nr++;
2174           fputc ('\n', f);
2175           if (dest && stmt_nr == nr_stmts)
2176             fprintf_indent (f, indent, "%s = ", dest);
2177         }
2178     }
2179 }
2180
2181 /* Generate transform code for a capture.  */
2182
2183 void
2184 capture::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2185                         int depth, const char *in_type, capture_info *cinfo,
2186                         dt_operand **indexes, bool expand_compares)
2187 {
2188   if (what && is_a<expr *> (what))
2189     {
2190       if (indexes[where] == 0)
2191         {
2192           char buf[20];
2193           sprintf (buf, "captures[%u]", where);
2194           what->gen_transform (f, indent, buf, gimple, depth, in_type,
2195                                cinfo, NULL);
2196         }
2197     }
2198
2199   fprintf_indent (f, indent, "%s = captures[%u];\n", dest, where);
2200
2201   /* ???  Stupid tcc_comparison GENERIC trees in COND_EXPRs.  Deal
2202      with substituting a capture of that.
2203      ???  Returning false here will also not allow any other patterns
2204      to match.  */
2205   if (gimple && expand_compares
2206       && cinfo->info[where].cond_expr_cond_p)
2207     {
2208       fprintf_indent (f, indent, "if (COMPARISON_CLASS_P (%s))\n", dest);
2209       fprintf_indent (f, indent, "  {\n");
2210       fprintf_indent (f, indent, "    if (!seq) return false;\n");
2211       fprintf_indent (f, indent, "    %s = gimple_build (seq, TREE_CODE (%s),"
2212                                  " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2213                                  " TREE_OPERAND (%s, 1));\n",
2214                                  dest, dest, dest, dest, dest);
2215       fprintf_indent (f, indent, "  }\n");
2216     }
2217 }
2218
2219 /* Return the name of the operand representing the decision tree node.
2220    Use NAME as space to generate it.  */
2221
2222 char *
2223 dt_operand::get_name (char *name)
2224 {
2225   if (!parent)
2226     sprintf (name, "t");
2227   else if (parent->level == 1)
2228     sprintf (name, "op%u", pos);
2229   else if (parent->type == dt_node::DT_MATCH)
2230     return parent->get_name (name);
2231   else
2232     sprintf (name, "o%u%u", parent->level, pos);
2233   return name;
2234 }
2235
2236 /* Fill NAME with the operand name at position POS.  */
2237
2238 void
2239 dt_operand::gen_opname (char *name, unsigned pos)
2240 {
2241   if (!parent)
2242     sprintf (name, "op%u", pos);
2243   else
2244     sprintf (name, "o%u%u", level, pos);
2245 }
2246
2247 /* Generate matching code for the decision tree operand which is
2248    a predicate.  */
2249
2250 unsigned
2251 dt_operand::gen_predicate (FILE *f, int indent, const char *opname, bool gimple)
2252 {
2253   predicate *p = as_a <predicate *> (op);
2254
2255   if (p->p->matchers.exists ())
2256     {
2257       /* If this is a predicate generated from a pattern mangle its
2258          name and pass on the valueize hook.  */
2259       if (gimple)
2260         fprintf_indent (f, indent, "if (gimple_%s (%s, valueize))\n",
2261                         p->p->id, opname);
2262       else
2263         fprintf_indent (f, indent, "if (tree_%s (%s))\n", p->p->id, opname);
2264     }
2265   else
2266     fprintf_indent (f, indent, "if (%s (%s))\n", p->p->id, opname);
2267   fprintf_indent (f, indent + 2, "{\n");
2268   return 1;
2269 }
2270
2271 /* Generate matching code for the decision tree operand which is
2272    a capture-match.  */
2273
2274 unsigned
2275 dt_operand::gen_match_op (FILE *f, int indent, const char *opname)
2276 {
2277   char match_opname[20];
2278   match_dop->get_name (match_opname);
2279   fprintf_indent (f, indent, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2280                   opname, match_opname, opname, match_opname);
2281   fprintf_indent (f, indent + 2, "{\n");
2282   return 1;
2283 }
2284
2285 /* Generate GIMPLE matching code for the decision tree operand.  */
2286
2287 unsigned
2288 dt_operand::gen_gimple_expr (FILE *f, int indent)
2289 {
2290   expr *e = static_cast<expr *> (op);
2291   id_base *id = e->operation;
2292   unsigned n_ops = e->ops.length ();
2293
2294   for (unsigned i = 0; i < n_ops; ++i)
2295     {
2296       char child_opname[20];
2297       gen_opname (child_opname, i);
2298
2299       if (id->kind == id_base::CODE)
2300         {
2301           if (e->is_generic
2302               || *id == REALPART_EXPR || *id == IMAGPART_EXPR
2303               || *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR)
2304             {
2305               /* ???  If this is a memory operation we can't (and should not)
2306                  match this.  The only sensible operand types are
2307                  SSA names and invariants.  */
2308               fprintf_indent (f, indent,
2309                               "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
2310                               child_opname, i);
2311               fprintf_indent (f, indent,
2312                               "if ((TREE_CODE (%s) == SSA_NAME\n",
2313                               child_opname);
2314               fprintf_indent (f, indent,
2315                               "     || is_gimple_min_invariant (%s))\n",
2316                               child_opname);
2317               fprintf_indent (f, indent,
2318                               "    && (%s = do_valueize (valueize, %s)))\n",
2319                               child_opname, child_opname);
2320               fprintf_indent (f, indent,
2321                               "  {\n");
2322               indent += 4;
2323               continue;
2324             }
2325           else
2326             fprintf_indent (f, indent,
2327                             "tree %s = gimple_assign_rhs%u (def_stmt);\n",
2328                             child_opname, i + 1);
2329         }
2330       else
2331         fprintf_indent (f, indent,
2332                         "tree %s = gimple_call_arg (def_stmt, %u);\n",
2333                         child_opname, i);
2334       fprintf_indent (f, indent,
2335                       "if ((%s = do_valueize (valueize, %s)))\n",
2336                       child_opname, child_opname);
2337       fprintf_indent (f, indent, "  {\n");
2338       indent += 4;
2339     }
2340   /* While the toplevel operands are canonicalized by the caller
2341      after valueizing operands of sub-expressions we have to
2342      re-canonicalize operand order.  */
2343   if (operator_id *code = dyn_cast <operator_id *> (id))
2344     {
2345       /* ???  We can't canonicalize tcc_comparison operands here
2346          because that requires changing the comparison code which
2347          we already matched...  */
2348       if (commutative_tree_code (code->code)
2349           || commutative_ternary_tree_code (code->code))
2350         {
2351           char child_opname0[20], child_opname1[20];
2352           gen_opname (child_opname0, 0);
2353           gen_opname (child_opname1, 1);
2354           fprintf_indent (f, indent,
2355                           "if (tree_swap_operands_p (%s, %s, false))\n",
2356                           child_opname0, child_opname1);
2357           fprintf_indent (f, indent,
2358                           "  std::swap (%s, %s);\n",
2359                           child_opname0, child_opname1);
2360         }
2361     }
2362
2363   return n_ops;
2364 }
2365
2366 /* Generate GENERIC matching code for the decision tree operand.  */
2367
2368 unsigned
2369 dt_operand::gen_generic_expr (FILE *f, int indent, const char *opname)
2370 {
2371   expr *e = static_cast<expr *> (op);
2372   unsigned n_ops = e->ops.length ();
2373
2374   for (unsigned i = 0; i < n_ops; ++i)
2375     {
2376       char child_opname[20];
2377       gen_opname (child_opname, i);
2378
2379       if (e->operation->kind == id_base::CODE)
2380         fprintf_indent (f, indent, "tree %s = TREE_OPERAND (%s, %u);\n",
2381                         child_opname, opname, i);
2382       else
2383         fprintf_indent (f, indent, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2384                         child_opname, opname, i);
2385     }
2386
2387   return 0;
2388 }
2389
2390 /* Generate matching code for the children of the decision tree node.  */
2391
2392 void
2393 dt_node::gen_kids (FILE *f, int indent, bool gimple)
2394 {
2395   auto_vec<dt_operand *> gimple_exprs;
2396   auto_vec<dt_operand *> generic_exprs;
2397   auto_vec<dt_operand *> fns;
2398   auto_vec<dt_operand *> generic_fns;
2399   auto_vec<dt_operand *> preds;
2400   auto_vec<dt_node *> others;
2401
2402   for (unsigned i = 0; i < kids.length (); ++i)
2403     {
2404       if (kids[i]->type == dt_node::DT_OPERAND)
2405         {
2406           dt_operand *op = as_a<dt_operand *> (kids[i]);
2407           if (expr *e = dyn_cast <expr *> (op->op))
2408             {
2409               if (e->ops.length () == 0
2410                   && (!gimple || !(*e->operation == CONSTRUCTOR)))
2411                 generic_exprs.safe_push (op);
2412               else if (e->operation->kind == id_base::FN)
2413                 {
2414                   if (gimple)
2415                     fns.safe_push (op);
2416                   else
2417                     generic_fns.safe_push (op);
2418                 }
2419               else if (e->operation->kind == id_base::PREDICATE)
2420                 preds.safe_push (op);
2421               else
2422                 {
2423                   if (gimple)
2424                     gimple_exprs.safe_push (op);
2425                   else
2426                     generic_exprs.safe_push (op);
2427                 }
2428             }
2429           else if (op->op->type == operand::OP_PREDICATE)
2430             others.safe_push (kids[i]);
2431           else
2432             gcc_unreachable ();
2433         }
2434       else if (kids[i]->type == dt_node::DT_MATCH
2435                || kids[i]->type == dt_node::DT_SIMPLIFY)
2436         others.safe_push (kids[i]);
2437       else if (kids[i]->type == dt_node::DT_TRUE)
2438         {
2439           /* A DT_TRUE operand serves as a barrier - generate code now
2440              for what we have collected sofar.  */
2441           gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2442                       fns, generic_fns, preds, others);
2443           /* And output the true operand itself.  */
2444           kids[i]->gen (f, indent, gimple);
2445           gimple_exprs.truncate (0);
2446           generic_exprs.truncate (0);
2447           fns.truncate (0);
2448           generic_fns.truncate (0);
2449           preds.truncate (0);
2450           others.truncate (0);
2451         }
2452       else
2453         gcc_unreachable ();
2454     }
2455
2456   /* Generate code for the remains.  */
2457   gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2458               fns, generic_fns, preds, others);
2459 }
2460
2461 /* Generate matching code for the children of the decision tree node.  */
2462
2463 void
2464 dt_node::gen_kids_1 (FILE *f, int indent, bool gimple,
2465                      vec<dt_operand *> gimple_exprs,
2466                      vec<dt_operand *> generic_exprs,
2467                      vec<dt_operand *> fns,
2468                      vec<dt_operand *> generic_fns,
2469                      vec<dt_operand *> preds,
2470                      vec<dt_node *> others)
2471 {
2472   char buf[128];
2473   char *kid_opname = buf;
2474
2475   unsigned exprs_len = gimple_exprs.length ();
2476   unsigned gexprs_len = generic_exprs.length ();
2477   unsigned fns_len = fns.length ();
2478   unsigned gfns_len = generic_fns.length ();
2479
2480   if (exprs_len || fns_len || gexprs_len || gfns_len)
2481     {
2482       if (exprs_len)
2483         gimple_exprs[0]->get_name (kid_opname);
2484       else if (fns_len)
2485         fns[0]->get_name (kid_opname);
2486       else if (gfns_len)
2487         generic_fns[0]->get_name (kid_opname);
2488       else
2489         generic_exprs[0]->get_name (kid_opname);
2490
2491       fprintf_indent (f, indent, "switch (TREE_CODE (%s))\n", kid_opname);
2492       fprintf_indent (f, indent, "  {\n");
2493       indent += 2;
2494     }
2495
2496   if (exprs_len || fns_len)
2497     {
2498       fprintf_indent (f, indent,
2499                       "case SSA_NAME:\n");
2500       fprintf_indent (f, indent,
2501                       "  if (do_valueize (valueize, %s) != NULL_TREE)\n",
2502                       kid_opname);
2503       fprintf_indent (f, indent,
2504                       "    {\n");
2505       fprintf_indent (f, indent,
2506                       "      gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2507                       kid_opname);
2508
2509       indent += 6;
2510       if (exprs_len)
2511         {
2512           fprintf_indent (f, indent,
2513                           "if (is_gimple_assign (def_stmt))\n");
2514           fprintf_indent (f, indent,
2515                           "  switch (gimple_assign_rhs_code (def_stmt))\n");
2516           indent += 4;
2517           fprintf_indent (f, indent, "{\n");
2518           for (unsigned i = 0; i < exprs_len; ++i)
2519             {
2520               expr *e = as_a <expr *> (gimple_exprs[i]->op);
2521               id_base *op = e->operation;
2522               if (*op == CONVERT_EXPR || *op == NOP_EXPR)
2523                 fprintf_indent (f, indent, "CASE_CONVERT:\n");
2524               else
2525                 fprintf_indent (f, indent, "case %s:\n", op->id);
2526               fprintf_indent (f, indent, "  {\n");
2527               gimple_exprs[i]->gen (f, indent + 4, true);
2528               fprintf_indent (f, indent, "    break;\n");
2529               fprintf_indent (f, indent, "  }\n");
2530             }
2531           fprintf_indent (f, indent, "default:;\n");
2532           fprintf_indent (f, indent, "}\n");
2533           indent -= 4;
2534         }
2535
2536       if (fns_len)
2537         {
2538           if (exprs_len)
2539             fprintf_indent (f, indent, "else ");
2540           else
2541             fprintf_indent (f, indent, " ");
2542
2543           fprintf (f, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n");
2544           fprintf_indent (f, indent,
2545                           "  {\n");
2546           fprintf_indent (f, indent,
2547                           "    tree fndecl = gimple_call_fndecl (def_stmt);\n");
2548           fprintf_indent (f, indent,
2549                           "    switch (DECL_FUNCTION_CODE (fndecl))\n");
2550           fprintf_indent (f, indent,
2551                           "      {\n");
2552
2553           indent += 6;
2554           for (unsigned i = 0; i < fns_len; ++i)
2555             {
2556               expr *e = as_a <expr *>(fns[i]->op);
2557               fprintf_indent (f, indent, "case %s:\n", e->operation->id);
2558               fprintf_indent (f, indent, "  {\n");
2559               fns[i]->gen (f, indent + 4, true);
2560               fprintf_indent (f, indent, "    break;\n");
2561               fprintf_indent (f, indent, "  }\n");
2562             }
2563
2564           fprintf_indent (f, indent, "default:;\n");
2565           fprintf_indent (f, indent, "}\n");
2566           indent -= 6;
2567           fprintf_indent (f, indent, "  }\n");
2568         }
2569
2570       indent -= 6;
2571       fprintf_indent (f, indent, "    }\n");
2572       fprintf_indent (f, indent, "  break;\n");
2573     }
2574
2575   for (unsigned i = 0; i < generic_exprs.length (); ++i)
2576     {
2577       expr *e = as_a <expr *>(generic_exprs[i]->op);
2578       id_base *op = e->operation;
2579       if (*op == CONVERT_EXPR || *op == NOP_EXPR)
2580         fprintf_indent (f, indent, "CASE_CONVERT:\n");
2581       else
2582         fprintf_indent (f, indent, "case %s:\n", op->id);
2583       fprintf_indent (f, indent, "  {\n");
2584       generic_exprs[i]->gen (f, indent + 4, gimple);
2585       fprintf_indent (f, indent, "    break;\n");
2586       fprintf_indent (f, indent, "  }\n");
2587     }
2588
2589   if (gfns_len)
2590     {
2591       fprintf_indent (f, indent,
2592                       "case CALL_EXPR:\n");
2593       fprintf_indent (f, indent,
2594                       "  {\n");
2595       fprintf_indent (f, indent,
2596                       "    tree fndecl = get_callee_fndecl (%s);\n",
2597                       kid_opname);
2598       fprintf_indent (f, indent,
2599                       "    if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n");
2600       fprintf_indent (f, indent,
2601                       "      switch (DECL_FUNCTION_CODE (fndecl))\n");
2602       fprintf_indent (f, indent,
2603                       "        {\n");
2604       indent += 8;
2605
2606       for (unsigned j = 0; j < generic_fns.length (); ++j)
2607         {
2608           expr *e = as_a <expr *>(generic_fns[j]->op);
2609           gcc_assert (e->operation->kind == id_base::FN);
2610
2611           fprintf_indent (f, indent, "case %s:\n", e->operation->id);
2612           fprintf_indent (f, indent, "  {\n");
2613           generic_fns[j]->gen (f, indent + 4, false);
2614           fprintf_indent (f, indent, "    break;\n");
2615           fprintf_indent (f, indent, "  }\n");
2616         }
2617
2618       indent -= 8;
2619       fprintf_indent (f, indent, "          default:;\n");
2620       fprintf_indent (f, indent, "        }\n");
2621       fprintf_indent (f, indent, "    break;\n");
2622       fprintf_indent (f, indent, "  }\n");
2623     }
2624
2625   /* Close switch (TREE_CODE ()).  */
2626   if (exprs_len || fns_len || gexprs_len || gfns_len)
2627     {
2628       indent -= 4;
2629       fprintf_indent (f, indent, "    default:;\n");
2630       fprintf_indent (f, indent, "    }\n");
2631     }
2632
2633   for (unsigned i = 0; i < preds.length (); ++i)
2634     {
2635       expr *e = as_a <expr *> (preds[i]->op);
2636       predicate_id *p = as_a <predicate_id *> (e->operation);
2637       preds[i]->get_name (kid_opname);
2638       fprintf_indent (f, indent, "tree %s_pops[%d];\n", kid_opname, p->nargs);
2639       fprintf_indent (f, indent, "if (%s_%s (%s, %s_pops%s))\n",
2640                gimple ? "gimple" : "tree",
2641                p->id, kid_opname, kid_opname,
2642                gimple ? ", valueize" : "");
2643       fprintf_indent (f, indent, "  {\n");
2644       for (int j = 0; j < p->nargs; ++j)
2645         {
2646           char child_opname[20];
2647           preds[i]->gen_opname (child_opname, j);
2648           fprintf_indent (f, indent + 4, "tree %s = %s_pops[%d];\n",
2649                           child_opname, kid_opname, j);
2650         }
2651       preds[i]->gen_kids (f, indent + 4, gimple);
2652       fprintf (f, "}\n");
2653     }
2654
2655   for (unsigned i = 0; i < others.length (); ++i)
2656     others[i]->gen (f, indent, gimple);
2657 }
2658
2659 /* Generate matching code for the decision tree operand.  */
2660
2661 void
2662 dt_operand::gen (FILE *f, int indent, bool gimple)
2663 {
2664   char opname[20];
2665   get_name (opname);
2666
2667   unsigned n_braces = 0;
2668
2669   if (type == DT_OPERAND)
2670     switch (op->type)
2671       {
2672         case operand::OP_PREDICATE:
2673           n_braces = gen_predicate (f, indent, opname, gimple);
2674           break;
2675
2676         case operand::OP_EXPR:
2677           if (gimple)
2678             n_braces = gen_gimple_expr (f, indent);
2679           else
2680             n_braces = gen_generic_expr (f, indent, opname);
2681           break;
2682
2683         default:
2684           gcc_unreachable ();
2685       }
2686   else if (type == DT_TRUE)
2687     ;
2688   else if (type == DT_MATCH)
2689     n_braces = gen_match_op (f, indent, opname);
2690   else
2691     gcc_unreachable ();
2692
2693   indent += 4 * n_braces;
2694   gen_kids (f, indent, gimple);
2695
2696   for (unsigned i = 0; i < n_braces; ++i)
2697     {
2698       indent -= 4;
2699       if (indent < 0)
2700         indent = 0;
2701       fprintf_indent (f, indent, "  }\n");
2702     }
2703 }
2704
2705
2706 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2707    step of a '(simplify ...)' or '(match ...)'.  This handles everything
2708    that is not part of the decision tree (simplify->match).
2709    Main recursive worker.  */
2710
2711 void
2712 dt_simplify::gen_1 (FILE *f, int indent, bool gimple, operand *result)
2713 {
2714   if (result)
2715     {
2716       if (with_expr *w = dyn_cast <with_expr *> (result))
2717         {
2718           fprintf_indent (f, indent, "{\n");
2719           indent += 4;
2720           output_line_directive (f, w->location);
2721           w->with->gen_transform (f, indent, NULL, true, 1, "type", NULL);
2722           gen_1 (f, indent, gimple, w->subexpr);
2723           indent -= 4;
2724           fprintf_indent (f, indent, "}\n");
2725           return;
2726         }
2727       else if (if_expr *ife = dyn_cast <if_expr *> (result))
2728         {
2729           output_line_directive (f, ife->location);
2730           fprintf_indent (f, indent, "if (");
2731           ife->cond->gen_transform (f, indent, NULL, true, 1, "type", NULL);
2732           fprintf (f, ")\n");
2733           fprintf_indent (f, indent + 2, "{\n");
2734           indent += 4;
2735           gen_1 (f, indent, gimple, ife->trueexpr);
2736           indent -= 4;
2737           fprintf_indent (f, indent + 2, "}\n");
2738           if (ife->falseexpr)
2739             {
2740               fprintf_indent (f, indent, "else\n");
2741               fprintf_indent (f, indent + 2, "{\n");
2742               indent += 4;
2743               gen_1 (f, indent, gimple, ife->falseexpr);
2744               indent -= 4;
2745               fprintf_indent (f, indent + 2, "}\n");
2746             }
2747           return;
2748         }
2749     }
2750
2751   /* Analyze captures and perform early-outs on the incoming arguments
2752      that cover cases we cannot handle.  */
2753   capture_info cinfo (s, result, gimple);
2754   if (s->kind == simplify::SIMPLIFY)
2755     {
2756       if (!gimple)
2757         {
2758           for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
2759             if (cinfo.force_no_side_effects & (1 << i))
2760               {
2761                 fprintf_indent (f, indent,
2762                                 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
2763                                 i);
2764                 if (verbose >= 1)
2765                   warning_at (as_a <expr *> (s->match)->ops[i]->location,
2766                               "forcing toplevel operand to have no "
2767                               "side-effects");
2768               }
2769           for (int i = 0; i <= s->capture_max; ++i)
2770             if (cinfo.info[i].cse_p)
2771               ;
2772             else if (cinfo.info[i].force_no_side_effects_p
2773                      && (cinfo.info[i].toplevel_msk
2774                          & cinfo.force_no_side_effects) == 0)
2775               {
2776                 fprintf_indent (f, indent,
2777                                 "if (TREE_SIDE_EFFECTS (captures[%d])) "
2778                                 "return NULL_TREE;\n", i);
2779                 if (verbose >= 1)
2780                   warning_at (cinfo.info[i].c->location,
2781                               "forcing captured operand to have no "
2782                               "side-effects");
2783               }
2784             else if ((cinfo.info[i].toplevel_msk
2785                       & cinfo.force_no_side_effects) != 0)
2786               /* Mark capture as having no side-effects if we had to verify
2787                  that via forced toplevel operand checks.  */
2788               cinfo.info[i].force_no_side_effects_p = true;
2789         }
2790       if (gimple)
2791         {
2792           /* Force single-use restriction by only allowing simple
2793              results via setting seq to NULL.  */
2794           fprintf_indent (f, indent, "gimple_seq *lseq = seq;\n");
2795           bool first_p = true;
2796           for (int i = 0; i <= s->capture_max; ++i)
2797             if (cinfo.info[i].force_single_use)
2798               {
2799                 if (first_p)
2800                   {
2801                     fprintf_indent (f, indent, "if (lseq\n");
2802                     fprintf_indent (f, indent, "    && (");
2803                     first_p = false;
2804                   }
2805                 else
2806                   {
2807                     fprintf (f, "\n");
2808                     fprintf_indent (f, indent, "        || ");
2809                   }
2810                 fprintf (f, "!single_use (captures[%d])", i);
2811               }
2812           if (!first_p)
2813             {
2814               fprintf (f, "))\n");
2815               fprintf_indent (f, indent, "  lseq = NULL;\n");
2816             }
2817         }
2818     }
2819
2820   fprintf_indent (f, indent, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2821            "fprintf (dump_file, \"Applying pattern ");
2822   output_line_directive (f,
2823                          result ? result->location : s->match->location, true);
2824   fprintf (f, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2825
2826   if (!result)
2827     {
2828       /* If there is no result then this is a predicate implementation.  */
2829       fprintf_indent (f, indent, "return true;\n");
2830     }
2831   else if (gimple)
2832     {
2833       /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2834          in outermost position).  */
2835       if (result->type == operand::OP_EXPR
2836           && *as_a <expr *> (result)->operation == NON_LVALUE_EXPR)
2837         result = as_a <expr *> (result)->ops[0];
2838       if (result->type == operand::OP_EXPR)
2839         {
2840           expr *e = as_a <expr *> (result);
2841           bool is_predicate = is_a <predicate_id *> (e->operation);
2842           if (!is_predicate)
2843             fprintf_indent (f, indent, "*res_code = %s;\n",
2844                             *e->operation == CONVERT_EXPR
2845                             ? "NOP_EXPR" : e->operation->id);
2846           for (unsigned j = 0; j < e->ops.length (); ++j)
2847             {
2848               char dest[32];
2849               snprintf (dest, 32, "res_ops[%d]", j);
2850               const char *optype
2851                 = get_operand_type (e->operation,
2852                                     "type", e->expr_type,
2853                                     j == 0 ? NULL : "TREE_TYPE (res_ops[0])");
2854               /* We need to expand GENERIC conditions we captured from
2855                  COND_EXPRs.  */
2856               bool expand_generic_cond_exprs_p
2857                 = (!is_predicate
2858                    /* But avoid doing that if the GENERIC condition is
2859                       valid - which it is in the first operand of COND_EXPRs
2860                       and VEC_COND_EXRPs.  */
2861                    && ((!(*e->operation == COND_EXPR)
2862                         && !(*e->operation == VEC_COND_EXPR))
2863                        || j != 0));
2864               e->ops[j]->gen_transform (f, indent, dest, true, 1, optype,
2865                                         &cinfo,
2866                                         indexes, expand_generic_cond_exprs_p);
2867             }
2868
2869           /* Re-fold the toplevel result.  It's basically an embedded
2870              gimple_build w/o actually building the stmt.  */
2871           if (!is_predicate)
2872             fprintf_indent (f, indent,
2873                             "gimple_resimplify%d (lseq, res_code, type, "
2874                             "res_ops, valueize);\n", e->ops.length ());
2875         }
2876       else if (result->type == operand::OP_CAPTURE
2877                || result->type == operand::OP_C_EXPR)
2878         {
2879           result->gen_transform (f, indent, "res_ops[0]", true, 1, "type",
2880                                  &cinfo, indexes, false);
2881           fprintf_indent (f, indent, "*res_code = TREE_CODE (res_ops[0]);\n");
2882           if (is_a <capture *> (result)
2883               && cinfo.info[as_a <capture *> (result)->where].cond_expr_cond_p)
2884             {
2885               /* ???  Stupid tcc_comparison GENERIC trees in COND_EXPRs.  Deal
2886                  with substituting a capture of that.  */
2887               fprintf_indent (f, indent,
2888                               "if (COMPARISON_CLASS_P (res_ops[0]))\n");
2889               fprintf_indent (f, indent,
2890                               "  {\n");
2891               fprintf_indent (f, indent,
2892                               "    tree tem = res_ops[0];\n");
2893               fprintf_indent (f, indent,
2894                               "    res_ops[0] = TREE_OPERAND (tem, 0);\n");
2895               fprintf_indent (f, indent,
2896                               "    res_ops[1] = TREE_OPERAND (tem, 1);\n");
2897               fprintf_indent (f, indent,
2898                               "  }\n");
2899             }
2900         }
2901       else
2902         gcc_unreachable ();
2903       fprintf_indent (f, indent, "return true;\n");
2904     }
2905   else /* GENERIC */
2906     {
2907       bool is_predicate = false;
2908       if (result->type == operand::OP_EXPR)
2909         {
2910           expr *e = as_a <expr *> (result);
2911           is_predicate = is_a <predicate_id *> (e->operation);
2912           /* Search for captures used multiple times in the result expression
2913              and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR.  */
2914           if (!is_predicate)
2915             for (int i = 0; i < s->capture_max + 1; ++i)
2916               {
2917                 if (cinfo.info[i].same_as != (unsigned)i)
2918                   continue;
2919                 if (!cinfo.info[i].force_no_side_effects_p
2920                     && cinfo.info[i].result_use_count > 1)
2921                   {
2922                     fprintf_indent (f, indent,
2923                                     "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
2924                                     i);
2925                     fprintf_indent (f, indent,
2926                                     "  captures[%d] = save_expr (captures[%d]);\n",
2927                                     i, i);
2928                   }
2929               }
2930           for (unsigned j = 0; j < e->ops.length (); ++j)
2931             {
2932               char dest[32];
2933               if (is_predicate)
2934                 snprintf (dest, 32, "res_ops[%d]", j);
2935               else
2936                 {
2937                   fprintf_indent (f, indent, "tree res_op%d;\n", j);
2938                   snprintf (dest, 32, "res_op%d", j);
2939                 }
2940               const char *optype
2941                 = get_operand_type (e->operation,
2942                                     "type", e->expr_type,
2943                                     j == 0
2944                                     ? NULL : "TREE_TYPE (res_op0)");
2945               e->ops[j]->gen_transform (f, indent, dest, false, 1, optype,
2946                                         &cinfo, indexes);
2947             }
2948           if (is_predicate)
2949             fprintf_indent (f, indent, "return true;\n");
2950           else
2951             {
2952               fprintf_indent (f, indent, "tree res;\n");
2953               /* Re-fold the toplevel result.  Use non_lvalue to
2954                  build NON_LVALUE_EXPRs so they get properly
2955                  ignored when in GIMPLE form.  */
2956               if (*e->operation == NON_LVALUE_EXPR)
2957                 fprintf_indent (f, indent,
2958                                 "res = non_lvalue_loc (loc, res_op0);\n");
2959               else
2960                 {
2961                   if (e->operation->kind == id_base::CODE)
2962                     fprintf_indent (f, indent,
2963                                     "res = fold_build%d_loc (loc, %s, type",
2964                                     e->ops.length (),
2965                                     *e->operation == CONVERT_EXPR
2966                                     ? "NOP_EXPR" : e->operation->id);
2967                   else
2968                     fprintf_indent (f, indent,
2969                                     "res = build_call_expr_loc "
2970                                     "(loc, builtin_decl_implicit (%s), %d",
2971                                     e->operation->id, e->ops.length());
2972                   for (unsigned j = 0; j < e->ops.length (); ++j)
2973                     fprintf (f, ", res_op%d", j);
2974                   fprintf (f, ");\n");
2975                 }
2976             }
2977         }
2978       else if (result->type == operand::OP_CAPTURE
2979                || result->type == operand::OP_C_EXPR)
2980
2981         {
2982           fprintf_indent (f, indent, "tree res;\n");
2983           result->gen_transform (f, indent, "res", false, 1, "type",
2984                                     &cinfo, indexes);
2985         }
2986       else
2987         gcc_unreachable ();
2988       if (!is_predicate)
2989         {
2990           /* Search for captures not used in the result expression and dependent
2991              on TREE_SIDE_EFFECTS emit omit_one_operand.  */
2992           for (int i = 0; i < s->capture_max + 1; ++i)
2993             {
2994               if (cinfo.info[i].same_as != (unsigned)i)
2995                 continue;
2996               if (!cinfo.info[i].force_no_side_effects_p
2997                   && !cinfo.info[i].expr_p
2998                   && cinfo.info[i].result_use_count == 0)
2999                 {
3000                   fprintf_indent (f, indent,
3001                                   "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3002                                   i);
3003                   fprintf_indent (f, indent + 2,
3004                                   "res = build2_loc (loc, COMPOUND_EXPR, type, "
3005                                   "fold_ignored_result (captures[%d]), res);\n",
3006                                   i);
3007                 }
3008             }
3009           fprintf_indent (f, indent, "return res;\n");
3010         }
3011     }
3012 }
3013
3014 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3015    step of a '(simplify ...)' or '(match ...)'.  This handles everything
3016    that is not part of the decision tree (simplify->match).  */
3017
3018 void
3019 dt_simplify::gen (FILE *f, int indent, bool gimple)
3020 {
3021   fprintf_indent (f, indent, "{\n");
3022   indent += 2;
3023   output_line_directive (f,
3024                          s->result ? s->result->location : s->match->location);
3025   if (s->capture_max >= 0)
3026     fprintf_indent (f, indent, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
3027                     s->capture_max + 1);
3028
3029   for (int i = 0; i <= s->capture_max; ++i)
3030     if (indexes[i])
3031       {
3032         char opname[20];
3033         fprintf_indent (f, indent, "captures[%u] = %s;\n",
3034                         i, indexes[i]->get_name (opname));
3035       }
3036
3037   /* If we have a split-out function for the actual transform, call it.  */
3038   if (info && info->fname)
3039     {
3040       if (gimple)
3041         {
3042           fprintf_indent (f, indent, "if (%s (res_code, res_ops, seq, "
3043                           "valueize, type, captures))\n", info->fname);
3044           fprintf_indent (f, indent, "  return true;\n");
3045         }
3046       else
3047         {
3048           fprintf_indent (f, indent, "tree res = %s (loc, type",
3049                           info->fname);
3050           for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
3051             fprintf (f, ", op%d", i);
3052           fprintf (f, ", captures);\n");
3053           fprintf_indent (f, indent, "if (res) return res;\n");
3054         }
3055     }
3056   else
3057     gen_1 (f, indent, gimple, s->result);
3058
3059   indent -= 2;
3060   fprintf_indent (f, indent, "}\n");
3061 }
3062
3063
3064 /* Hash function for finding equivalent transforms.  */
3065
3066 hashval_t
3067 sinfo_hashmap_traits::hash (const key_type &v)
3068 {
3069   /* Only bother to compare those originating from the same source pattern.  */
3070   return v->s->result->location;
3071 }
3072
3073 /* Compare function for finding equivalent transforms.  */
3074
3075 static bool
3076 compare_op (operand *o1, simplify *s1, operand *o2, simplify *s2)
3077 {
3078   if (o1->type != o2->type)
3079     return false;
3080
3081   switch (o1->type)
3082     {
3083     case operand::OP_IF:
3084       {
3085         if_expr *if1 = as_a <if_expr *> (o1);
3086         if_expr *if2 = as_a <if_expr *> (o2);
3087         /* ???  Properly compare c-exprs.  */
3088         if (if1->cond != if2->cond)
3089           return false;
3090         if (!compare_op (if1->trueexpr, s1, if2->trueexpr, s2))
3091           return false;
3092         if (if1->falseexpr != if2->falseexpr
3093             || (if1->falseexpr
3094                 && !compare_op (if1->falseexpr, s1, if2->falseexpr, s2)))
3095           return false;
3096         return true;
3097       }
3098     case operand::OP_WITH:
3099       {
3100         with_expr *with1 = as_a <with_expr *> (o1);
3101         with_expr *with2 = as_a <with_expr *> (o2);
3102         if (with1->with != with2->with)
3103           return false;
3104         return compare_op (with1->subexpr, s1, with2->subexpr, s2);
3105       }
3106     default:;
3107     }
3108
3109   /* We've hit a result.  Time to compare capture-infos - this is required
3110      in addition to the conservative pointer-equivalency of the result IL.  */
3111   capture_info cinfo1 (s1, o1, true);
3112   capture_info cinfo2 (s2, o2, true);
3113
3114   if (cinfo1.force_no_side_effects != cinfo2.force_no_side_effects
3115       || cinfo1.info.length () != cinfo2.info.length ())
3116     return false;
3117
3118   for (unsigned i = 0; i < cinfo1.info.length (); ++i)
3119     {
3120       if (cinfo1.info[i].expr_p != cinfo2.info[i].expr_p
3121           || cinfo1.info[i].cse_p != cinfo2.info[i].cse_p
3122           || (cinfo1.info[i].force_no_side_effects_p
3123               != cinfo2.info[i].force_no_side_effects_p)
3124           || cinfo1.info[i].force_single_use != cinfo2.info[i].force_single_use
3125           || cinfo1.info[i].cond_expr_cond_p != cinfo2.info[i].cond_expr_cond_p
3126           /* toplevel_msk is an optimization */
3127           || cinfo1.info[i].result_use_count != cinfo2.info[i].result_use_count
3128           || cinfo1.info[i].same_as != cinfo2.info[i].same_as
3129           /* the pointer back to the capture is for diagnostics only */)
3130         return false;
3131     }
3132
3133   /* ???  Deep-compare the actual result.  */
3134   return o1 == o2;
3135 }
3136
3137 bool
3138 sinfo_hashmap_traits::equal_keys (const key_type &v,
3139                                   const key_type &candidate)
3140 {
3141   return compare_op (v->s->result, v->s, candidate->s->result, candidate->s);
3142 }
3143
3144
3145 /* Main entry to generate code for matching GIMPLE IL off the decision
3146    tree.  */
3147
3148 void
3149 decision_tree::gen (FILE *f, bool gimple)
3150 {
3151   sinfo_map_t si;
3152
3153   root->analyze (si);
3154
3155   fprintf (stderr, "%s decision tree has %u leafs, maximum depth %u and "
3156            "a total number of %u nodes\n",
3157            gimple ? "GIMPLE" : "GENERIC",
3158            root->num_leafs, root->max_level, root->total_size);
3159
3160   /* First split out the transform part of equal leafs.  */
3161   unsigned rcnt = 0;
3162   unsigned fcnt = 1;
3163   for (sinfo_map_t::iterator iter = si.begin ();
3164        iter != si.end (); ++iter)
3165     {
3166       sinfo *s = (*iter).second;
3167       /* Do not split out single uses.  */
3168       if (s->cnt <= 1)
3169         continue;
3170
3171       rcnt += s->cnt - 1;
3172       if (verbose >= 1)
3173         {
3174           fprintf (stderr, "found %u uses of", s->cnt);
3175           output_line_directive (stderr, s->s->s->result->location);
3176         }
3177
3178       /* Generate a split out function with the leaf transform code.  */
3179       s->fname = xasprintf ("%s_simplify_%u", gimple ? "gimple" : "generic",
3180                             fcnt++);
3181       if (gimple)
3182         fprintf (f, "\nstatic bool\n"
3183                  "%s (code_helper *res_code, tree *res_ops,\n"
3184                  "                 gimple_seq *seq, tree (*valueize)(tree) "
3185                  "ATTRIBUTE_UNUSED,\n"
3186                  "                 tree ARG_UNUSED (type), tree *ARG_UNUSED "
3187                  "(captures))\n",
3188                  s->fname);
3189       else
3190         {
3191           fprintf (f, "\nstatic tree\n"
3192                    "%s (location_t ARG_UNUSED (loc), tree ARG_UNUSED (type),\n",
3193                    (*iter).second->fname);
3194           for (unsigned i = 0;
3195                i < as_a <expr *>(s->s->s->match)->ops.length (); ++i)
3196             fprintf (f, " tree ARG_UNUSED (op%d),", i);
3197           fprintf (f, " tree *captures)\n");
3198         }
3199
3200       fprintf (f, "{\n");
3201       s->s->gen_1 (f, 2, gimple, s->s->s->result);
3202       if (gimple)
3203         fprintf (f, "  return false;\n");
3204       else
3205         fprintf (f, "  return NULL_TREE;\n");
3206       fprintf (f, "}\n");
3207     }
3208   fprintf (stderr, "removed %u duplicate tails\n", rcnt);
3209
3210   for (unsigned n = 1; n <= 3; ++n)
3211     {
3212       /* First generate split-out functions.  */
3213       for (unsigned i = 0; i < root->kids.length (); i++)
3214         {
3215           dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
3216           expr *e = static_cast<expr *>(dop->op);
3217           if (e->ops.length () != n
3218               /* Builtin simplifications are somewhat premature on
3219                  GENERIC.  The following drops patterns with outermost
3220                  calls.  It's easy to emit overloads for function code
3221                  though if necessary.  */
3222               || (!gimple
3223                   && e->operation->kind != id_base::CODE))
3224             continue;
3225
3226           if (gimple)
3227             fprintf (f, "\nstatic bool\n"
3228                      "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n"
3229                      "                 gimple_seq *seq, tree (*valueize)(tree) "
3230                      "ATTRIBUTE_UNUSED,\n"
3231                      "                 code_helper ARG_UNUSED (code), tree "
3232                      "ARG_UNUSED (type)\n",
3233                      e->operation->id);
3234           else
3235             fprintf (f, "\nstatic tree\n"
3236                      "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3237                      "tree_code ARG_UNUSED (code), tree ARG_UNUSED (type)",
3238                      e->operation->id);
3239           for (unsigned i = 0; i < n; ++i)
3240             fprintf (f, ", tree op%d", i);
3241           fprintf (f, ")\n");
3242           fprintf (f, "{\n");
3243           dop->gen_kids (f, 2, gimple);
3244           if (gimple)
3245             fprintf (f, "  return false;\n");
3246           else
3247             fprintf (f, "  return NULL_TREE;\n");
3248           fprintf (f, "}\n");
3249         }
3250
3251       /* Then generate the main entry with the outermost switch and
3252          tail-calls to the split-out functions.  */
3253       if (gimple)
3254         fprintf (f, "\nstatic bool\n"
3255                  "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
3256                  "                 gimple_seq *seq, tree (*valueize)(tree),\n"
3257                  "                 code_helper code, tree type");
3258       else
3259         fprintf (f, "\ntree\n"
3260                  "generic_simplify (location_t loc, enum tree_code code, "
3261                  "tree type ATTRIBUTE_UNUSED");
3262       for (unsigned i = 0; i < n; ++i)
3263         fprintf (f, ", tree op%d", i);
3264       fprintf (f, ")\n");
3265       fprintf (f, "{\n");
3266
3267       if (gimple)
3268         fprintf (f, "  switch (code.get_rep())\n"
3269                  "    {\n");
3270       else
3271         fprintf (f, "  switch (code)\n"
3272                  "    {\n");
3273       for (unsigned i = 0; i < root->kids.length (); i++)
3274         {
3275           dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
3276           expr *e = static_cast<expr *>(dop->op);
3277           if (e->ops.length () != n
3278               /* Builtin simplifications are somewhat premature on
3279                  GENERIC.  The following drops patterns with outermost
3280                  calls.  It's easy to emit overloads for function code
3281                  though if necessary.  */
3282               || (!gimple
3283                   && e->operation->kind != id_base::CODE))
3284             continue;
3285
3286           if (*e->operation == CONVERT_EXPR
3287               || *e->operation == NOP_EXPR)
3288             fprintf (f, "    CASE_CONVERT:\n");
3289           else
3290             fprintf (f, "    case %s%s:\n",
3291                      is_a <fn_id *> (e->operation) ? "-" : "",
3292                      e->operation->id);
3293           if (gimple)
3294             fprintf (f, "      return gimple_simplify_%s (res_code, res_ops, "
3295                      "seq, valueize, code, type", e->operation->id);
3296           else
3297             fprintf (f, "      return generic_simplify_%s (loc, code, type",
3298                      e->operation->id);
3299           for (unsigned i = 0; i < n; ++i)
3300             fprintf (f, ", op%d", i);
3301           fprintf (f, ");\n");
3302         }
3303       fprintf (f,       "    default:;\n"
3304                         "    }\n");
3305
3306       if (gimple)
3307         fprintf (f, "  return false;\n");
3308       else
3309         fprintf (f, "  return NULL_TREE;\n");
3310       fprintf (f, "}\n");
3311     }
3312 }
3313
3314 /* Output code to implement the predicate P from the decision tree DT.  */
3315
3316 void
3317 write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple)
3318 {
3319   fprintf (f, "\nbool\n"
3320            "%s%s (tree t%s%s)\n"
3321            "{\n", gimple ? "gimple_" : "tree_", p->id,
3322            p->nargs > 0 ? ", tree *res_ops" : "",
3323            gimple ? ", tree (*valueize)(tree)" : "");
3324   /* Conveniently make 'type' available.  */
3325   fprintf_indent (f, 2, "tree type = TREE_TYPE (t);\n");
3326
3327   if (!gimple)
3328     fprintf_indent (f, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3329   dt.root->gen_kids (f, 2, gimple);
3330
3331   fprintf_indent (f, 2, "return false;\n"
3332            "}\n");
3333 }
3334
3335 /* Write the common header for the GIMPLE/GENERIC IL matching routines.  */
3336
3337 static void
3338 write_header (FILE *f, const char *head)
3339 {
3340   fprintf (f, "/* Generated automatically by the program `genmatch' from\n");
3341   fprintf (f, "   a IL pattern matching and simplification description.  */\n");
3342
3343   /* Include the header instead of writing it awkwardly quoted here.  */
3344   fprintf (f, "\n#include \"%s\"\n", head);
3345 }
3346
3347
3348
3349 /* AST parsing.  */
3350
3351 class parser
3352 {
3353 public:
3354   parser (cpp_reader *);
3355
3356 private:
3357   const cpp_token *next ();
3358   const cpp_token *peek (unsigned = 1);
3359   const cpp_token *peek_ident (const char * = NULL, unsigned = 1);
3360   const cpp_token *expect (enum cpp_ttype);
3361   const cpp_token *eat_token (enum cpp_ttype);
3362   const char *get_string ();
3363   const char *get_ident ();
3364   const cpp_token *eat_ident (const char *);
3365   const char *get_number ();
3366
3367   id_base *parse_operation ();
3368   operand *parse_capture (operand *, bool);
3369   operand *parse_expr ();
3370   c_expr *parse_c_expr (cpp_ttype);
3371   operand *parse_op ();
3372
3373   void record_operlist (source_location, user_id *);
3374
3375   void parse_pattern ();
3376   operand *parse_result (operand *, predicate_id *);
3377   void push_simplify (simplify::simplify_kind,
3378                       vec<simplify *>&, operand *, operand *);
3379   void parse_simplify (simplify::simplify_kind,
3380                        vec<simplify *>&, predicate_id *, operand *);
3381   void parse_for (source_location);
3382   void parse_if (source_location);
3383   void parse_predicates (source_location);
3384   void parse_operator_list (source_location);
3385
3386   cpp_reader *r;
3387   vec<c_expr *> active_ifs;
3388   vec<vec<user_id *> > active_fors;
3389   hash_set<user_id *> *oper_lists_set;
3390   vec<user_id *> oper_lists;
3391
3392   cid_map_t *capture_ids;
3393
3394 public:
3395   vec<simplify *> simplifiers;
3396   vec<predicate_id *> user_predicates;
3397   bool parsing_match_operand;
3398 };
3399
3400 /* Lexing helpers.  */
3401
3402 /* Read the next non-whitespace token from R.  */
3403
3404 const cpp_token *
3405 parser::next ()
3406 {
3407   const cpp_token *token;
3408   do
3409     {
3410       token = cpp_get_token (r);
3411     }
3412   while (token->type == CPP_PADDING
3413          && token->type != CPP_EOF);
3414   return token;
3415 }
3416
3417 /* Peek at the next non-whitespace token from R.  */
3418
3419 const cpp_token *
3420 parser::peek (unsigned num)
3421 {
3422   const cpp_token *token;
3423   unsigned i = 0;
3424   do
3425     {
3426       token = cpp_peek_token (r, i++);
3427     }
3428   while ((token->type == CPP_PADDING
3429           && token->type != CPP_EOF)
3430          || (--num > 0));
3431   /* If we peek at EOF this is a fatal error as it leaves the
3432      cpp_reader in unusable state.  Assume we really wanted a
3433      token and thus this EOF is unexpected.  */
3434   if (token->type == CPP_EOF)
3435     fatal_at (token, "unexpected end of file");
3436   return token;
3437 }
3438
3439 /* Peek at the next identifier token (or return NULL if the next
3440    token is not an identifier or equal to ID if supplied).  */
3441
3442 const cpp_token *
3443 parser::peek_ident (const char *id, unsigned num)
3444 {
3445   const cpp_token *token = peek (num);
3446   if (token->type != CPP_NAME)
3447     return 0;
3448
3449   if (id == 0)
3450     return token;
3451
3452   const char *t = (const char *) CPP_HASHNODE (token->val.node.node)->ident.str;
3453   if (strcmp (id, t) == 0)
3454     return token;
3455
3456   return 0;
3457 }
3458
3459 /* Read the next token from R and assert it is of type TK.  */
3460
3461 const cpp_token *
3462 parser::expect (enum cpp_ttype tk)
3463 {
3464   const cpp_token *token = next ();
3465   if (token->type != tk)
3466     fatal_at (token, "expected %s, got %s",
3467               cpp_type2name (tk, 0), cpp_type2name (token->type, 0));
3468
3469   return token;
3470 }
3471
3472 /* Consume the next token from R and assert it is of type TK.  */
3473
3474 const cpp_token *
3475 parser::eat_token (enum cpp_ttype tk)
3476 {
3477   return expect (tk);
3478 }
3479
3480 /* Read the next token from R and assert it is of type CPP_STRING and
3481    return its value.  */
3482
3483 const char *
3484 parser::get_string ()
3485 {
3486   const cpp_token *token = expect (CPP_STRING);
3487   return (const char *)token->val.str.text;
3488 }
3489
3490 /* Read the next token from R and assert it is of type CPP_NAME and
3491    return its value.  */
3492
3493 const char *
3494 parser::get_ident ()
3495 {
3496   const cpp_token *token = expect (CPP_NAME);
3497   return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str;
3498 }
3499
3500 /* Eat an identifier token with value S from R.  */
3501
3502 const cpp_token *
3503 parser::eat_ident (const char *s)
3504 {
3505   const cpp_token *token = peek ();
3506   const char *t = get_ident ();
3507   if (strcmp (s, t) != 0)
3508     fatal_at (token, "expected '%s' got '%s'\n", s, t);
3509   return token;
3510 }
3511
3512 /* Read the next token from R and assert it is of type CPP_NUMBER and
3513    return its value.  */
3514
3515 const char *
3516 parser::get_number ()
3517 {
3518   const cpp_token *token = expect (CPP_NUMBER);
3519   return (const char *)token->val.str.text;
3520 }
3521
3522
3523 /* Record an operator-list use for transparent for handling.  */
3524
3525 void
3526 parser::record_operlist (source_location loc, user_id *p)
3527 {
3528   if (!oper_lists_set->add (p))
3529     {
3530       if (!oper_lists.is_empty ()
3531           && oper_lists[0]->substitutes.length () != p->substitutes.length ())
3532         fatal_at (loc, "User-defined operator list does not have the "
3533                   "same number of entries as others used in the pattern");
3534       oper_lists.safe_push (p);
3535     }
3536 }
3537
3538 /* Parse the operator ID, special-casing convert?, convert1? and
3539    convert2?  */
3540
3541 id_base *
3542 parser::parse_operation ()
3543 {
3544   const cpp_token *id_tok = peek ();
3545   const char *id = get_ident ();
3546   const cpp_token *token = peek ();
3547   if (strcmp (id, "convert0") == 0)
3548     fatal_at (id_tok, "use 'convert?' here");
3549   else if (strcmp (id, "view_convert0") == 0)
3550     fatal_at (id_tok, "use 'view_convert?' here");
3551   if (token->type == CPP_QUERY
3552       && !(token->flags & PREV_WHITE))
3553     {
3554       if (strcmp (id, "convert") == 0)
3555         id = "convert0";
3556       else if (strcmp (id, "convert1") == 0)
3557         ;
3558       else if (strcmp (id, "convert2") == 0)
3559         ;
3560       else if (strcmp (id, "view_convert") == 0)
3561         id = "view_convert0";
3562       else if (strcmp (id, "view_convert1") == 0)
3563         ;
3564       else if (strcmp (id, "view_convert2") == 0)
3565         ;
3566       else
3567         fatal_at (id_tok, "non-convert operator conditionalized");
3568
3569       if (!parsing_match_operand)
3570         fatal_at (id_tok, "conditional convert can only be used in "
3571                   "match expression");
3572       eat_token (CPP_QUERY);
3573     }
3574   else if (strcmp (id, "convert1") == 0
3575            || strcmp (id, "convert2") == 0
3576            || strcmp (id, "view_convert1") == 0
3577            || strcmp (id, "view_convert2") == 0)
3578     fatal_at (id_tok, "expected '?' after conditional operator");
3579   id_base *op = get_operator (id);
3580   if (!op)
3581     fatal_at (id_tok, "unknown operator %s", id);
3582
3583   user_id *p = dyn_cast<user_id *> (op);
3584   if (p && p->is_oper_list)
3585     {
3586       if (active_fors.length() == 0)
3587         record_operlist (id_tok->src_loc, p);
3588       else
3589         fatal_at (id_tok, "operator-list %s cannot be exapnded inside 'for'", id);
3590     }
3591   return op;
3592 }
3593
3594 /* Parse a capture.
3595      capture = '@'<number>  */
3596
3597 struct operand *
3598 parser::parse_capture (operand *op, bool require_existing)
3599 {
3600   source_location src_loc = eat_token (CPP_ATSIGN)->src_loc;
3601   const cpp_token *token = peek ();
3602   const char *id = NULL;
3603   if (token->type == CPP_NUMBER)
3604     id = get_number ();
3605   else if (token->type == CPP_NAME)
3606     id = get_ident ();
3607   else
3608     fatal_at (token, "expected number or identifier");
3609   unsigned next_id = capture_ids->elements ();
3610   bool existed;
3611   unsigned &num = capture_ids->get_or_insert (id, &existed);
3612   if (!existed)
3613     {
3614       if (require_existing)
3615         fatal_at (src_loc, "unknown capture id");
3616       num = next_id;
3617     }
3618   return new capture (src_loc, num, op);
3619 }
3620
3621 /* Parse an expression
3622      expr = '(' <operation>[capture][flag][type] <operand>... ')'  */
3623
3624 struct operand *
3625 parser::parse_expr ()
3626 {
3627   const cpp_token *token = peek ();
3628   expr *e = new expr (parse_operation (), token->src_loc);
3629   token = peek ();
3630   operand *op;
3631   bool is_commutative = false;
3632   bool force_capture = false;
3633   const char *expr_type = NULL;
3634
3635   if (token->type == CPP_COLON
3636       && !(token->flags & PREV_WHITE))
3637     {
3638       eat_token (CPP_COLON);
3639       token = peek ();
3640       if (token->type == CPP_NAME
3641           && !(token->flags & PREV_WHITE))
3642         {
3643           const char *s = get_ident ();
3644           if (!parsing_match_operand)
3645             expr_type = s;
3646           else
3647             {
3648               const char *sp = s;
3649               while (*sp)
3650                 {
3651                   if (*sp == 'c')
3652                     is_commutative = true;
3653                   else if (*sp == 's')
3654                     {
3655                       e->force_single_use = true;
3656                       force_capture = true;
3657                     }
3658                   else
3659                     fatal_at (token, "flag %c not recognized", *sp);
3660                   sp++;
3661                 }
3662             }
3663           token = peek ();
3664         }
3665       else
3666         fatal_at (token, "expected flag or type specifying identifier");
3667     }
3668
3669   if (token->type == CPP_ATSIGN
3670       && !(token->flags & PREV_WHITE))
3671     op = parse_capture (e, !parsing_match_operand);
3672   else if (force_capture)
3673     {
3674       unsigned num = capture_ids->elements ();
3675       char id[8];
3676       bool existed;
3677       sprintf (id, "__%u", num);
3678       capture_ids->get_or_insert (xstrdup (id), &existed);
3679       if (existed)
3680         fatal_at (token, "reserved capture id '%s' already used", id);
3681       op = new capture (token->src_loc, num, e);
3682     }
3683   else
3684     op = e;
3685   do
3686     {
3687       const cpp_token *token = peek ();
3688       if (token->type == CPP_CLOSE_PAREN)
3689         {
3690           if (e->operation->nargs != -1
3691               && e->operation->nargs != (int) e->ops.length ())
3692             fatal_at (token, "'%s' expects %u operands, not %u",
3693                       e->operation->id, e->operation->nargs, e->ops.length ());
3694           if (is_commutative)
3695             {
3696               if (e->ops.length () == 2)
3697                 e->is_commutative = true;
3698               else
3699                 fatal_at (token, "only binary operators or function with "
3700                           "two arguments can be marked commutative");
3701             }
3702           e->expr_type = expr_type;
3703           return op;
3704         }
3705       e->append_op (parse_op ());
3706     }
3707   while (1);
3708 }
3709
3710 /* Lex native C code delimited by START recording the preprocessing tokens
3711    for later processing.
3712      c_expr = ('{'|'(') <pp token>... ('}'|')')  */
3713
3714 c_expr *
3715 parser::parse_c_expr (cpp_ttype start)
3716 {
3717   const cpp_token *token;
3718   cpp_ttype end;
3719   unsigned opencnt;
3720   vec<cpp_token> code = vNULL;
3721   unsigned nr_stmts = 0;
3722   source_location loc = eat_token (start)->src_loc;
3723   if (start == CPP_OPEN_PAREN)
3724     end = CPP_CLOSE_PAREN;
3725   else if (start == CPP_OPEN_BRACE)
3726     end = CPP_CLOSE_BRACE;
3727   else
3728     gcc_unreachable ();
3729   opencnt = 1;
3730   do
3731     {
3732       token = next ();
3733
3734       /* Count brace pairs to find the end of the expr to match.  */
3735       if (token->type == start)
3736         opencnt++;
3737       else if (token->type == end
3738                && --opencnt == 0)
3739         break;
3740
3741       /* This is a lame way of counting the number of statements.  */
3742       if (token->type == CPP_SEMICOLON)
3743         nr_stmts++;
3744
3745       /* If this is possibly a user-defined identifier mark it used.  */
3746       if (token->type == CPP_NAME)
3747         {
3748           id_base *idb = get_operator ((const char *)CPP_HASHNODE
3749                                       (token->val.node.node)->ident.str);
3750           user_id *p;
3751           if (idb && (p = dyn_cast<user_id *> (idb)) && p->is_oper_list)
3752             record_operlist (token->src_loc, p);
3753         }
3754
3755       /* Record the token.  */
3756       code.safe_push (*token);
3757     }
3758   while (1);
3759   return new c_expr (r, loc, code, nr_stmts, vNULL, capture_ids);
3760 }
3761
3762 /* Parse an operand which is either an expression, a predicate or
3763    a standalone capture.
3764      op = predicate | expr | c_expr | capture  */
3765
3766 struct operand *
3767 parser::parse_op ()
3768 {
3769   const cpp_token *token = peek ();
3770   struct operand *op = NULL;
3771   if (token->type == CPP_OPEN_PAREN)
3772     {
3773       eat_token (CPP_OPEN_PAREN);
3774       op = parse_expr ();
3775       eat_token (CPP_CLOSE_PAREN);
3776     }
3777   else if (token->type == CPP_OPEN_BRACE)
3778     {
3779       op = parse_c_expr (CPP_OPEN_BRACE);
3780     }
3781   else
3782     {
3783       /* Remaining ops are either empty or predicates  */
3784       if (token->type == CPP_NAME)
3785         {
3786           const char *id = get_ident ();
3787           id_base *opr = get_operator (id);
3788           if (!opr)
3789             fatal_at (token, "expected predicate name");
3790           if (operator_id *code = dyn_cast <operator_id *> (opr))
3791             {
3792               if (code->nargs != 0)
3793                 fatal_at (token, "using an operator with operands as predicate");
3794               /* Parse the zero-operand operator "predicates" as
3795                  expression.  */
3796               op = new expr (opr, token->src_loc);
3797             }
3798           else if (user_id *code = dyn_cast <user_id *> (opr))
3799             {
3800               if (code->nargs != 0)
3801                 fatal_at (token, "using an operator with operands as predicate");
3802               /* Parse the zero-operand operator "predicates" as
3803                  expression.  */
3804               op = new expr (opr, token->src_loc);
3805             }
3806           else if (predicate_id *p = dyn_cast <predicate_id *> (opr))
3807             op = new predicate (p, token->src_loc);
3808           else
3809             fatal_at (token, "using an unsupported operator as predicate");
3810           if (!parsing_match_operand)
3811             fatal_at (token, "predicates are only allowed in match expression");
3812           token = peek ();
3813           if (token->flags & PREV_WHITE)
3814             return op;
3815         }
3816       else if (token->type != CPP_COLON
3817                && token->type != CPP_ATSIGN)
3818         fatal_at (token, "expected expression or predicate");
3819       /* optionally followed by a capture and a predicate.  */
3820       if (token->type == CPP_COLON)
3821         fatal_at (token, "not implemented: predicate on leaf operand");
3822       if (token->type == CPP_ATSIGN)
3823         op = parse_capture (op, !parsing_match_operand);
3824     }
3825
3826   return op;
3827 }
3828
3829 /* Create a new simplify from the current parsing state and MATCH,
3830    MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS.  */
3831
3832 void
3833 parser::push_simplify (simplify::simplify_kind kind,
3834                        vec<simplify *>& simplifiers,
3835                        operand *match, operand *result)
3836 {
3837   /* Build and push a temporary for operator list uses in expressions.  */
3838   if (!oper_lists.is_empty ())
3839     active_fors.safe_push (oper_lists);
3840
3841   simplifiers.safe_push
3842     (new simplify (kind, match, result,
3843                    active_fors.copy (), capture_ids));
3844
3845   if (!oper_lists.is_empty ())
3846     active_fors.pop ();
3847 }
3848
3849 /* Parse
3850      <result-op> = <op> | <if> | <with>
3851      <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3852      <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3853    and return it.  */
3854
3855 operand *
3856 parser::parse_result (operand *result, predicate_id *matcher)
3857 {
3858   const cpp_token *token = peek ();
3859   if (token->type != CPP_OPEN_PAREN)
3860     return parse_op ();
3861
3862   eat_token (CPP_OPEN_PAREN);
3863   if (peek_ident ("if"))
3864     {
3865       eat_ident ("if");
3866       if_expr *ife = new if_expr (token->src_loc);
3867       ife->cond = parse_c_expr (CPP_OPEN_PAREN);
3868       if (peek ()->type == CPP_OPEN_PAREN)
3869         {
3870           ife->trueexpr = parse_result (result, matcher);
3871           if (peek ()->type == CPP_OPEN_PAREN)
3872             ife->falseexpr = parse_result (result, matcher);
3873           else if (peek ()->type != CPP_CLOSE_PAREN)
3874             ife->falseexpr = parse_op ();
3875         }
3876       else if (peek ()->type != CPP_CLOSE_PAREN)
3877         {
3878           ife->trueexpr = parse_op ();
3879           if (peek ()->type == CPP_OPEN_PAREN)
3880             ife->falseexpr = parse_result (result, matcher);
3881           else if (peek ()->type != CPP_CLOSE_PAREN)
3882             ife->falseexpr = parse_op ();
3883         }
3884       /* If this if is immediately closed then it contains a
3885          manual matcher or is part of a predicate definition.  */
3886       else /* if (peek ()->type == CPP_CLOSE_PAREN) */
3887         {
3888           if (!matcher)
3889             fatal_at (peek (), "manual transform not implemented");
3890           ife->trueexpr = result;
3891         }
3892       eat_token (CPP_CLOSE_PAREN);
3893       return ife;
3894     }
3895   else if (peek_ident ("with"))
3896     {
3897       eat_ident ("with");
3898       with_expr *withe = new with_expr (token->src_loc);
3899       /* Parse (with c-expr expr) as (if-with (true) expr).  */
3900       withe->with = parse_c_expr (CPP_OPEN_BRACE);
3901       withe->with->nr_stmts = 0;
3902       withe->subexpr = parse_result (result, matcher);
3903       eat_token (CPP_CLOSE_PAREN);
3904       return withe;
3905     }
3906   else if (peek_ident ("switch"))
3907     {
3908       token = eat_ident ("switch");
3909       source_location ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
3910       eat_ident ("if");
3911       if_expr *ife = new if_expr (ifloc);
3912       operand *res = ife;
3913       ife->cond = parse_c_expr (CPP_OPEN_PAREN);
3914       if (peek ()->type == CPP_OPEN_PAREN)
3915         ife->trueexpr = parse_result (result, matcher);
3916       else
3917         ife->trueexpr = parse_op ();
3918       eat_token (CPP_CLOSE_PAREN);
3919       if (peek ()->type != CPP_OPEN_PAREN
3920           || !peek_ident ("if", 2))
3921         fatal_at (token, "switch can be implemented with a single if");
3922       while  (peek ()->type != CPP_CLOSE_PAREN)
3923         {
3924           if (peek ()->type == CPP_OPEN_PAREN)
3925             {
3926               if (peek_ident ("if", 2))
3927                 {
3928                   ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
3929                   eat_ident ("if");
3930                   ife->falseexpr = new if_expr (ifloc);
3931                   ife = as_a <if_expr *> (ife->falseexpr);
3932                   ife->cond = parse_c_expr (CPP_OPEN_PAREN);
3933                   if (peek ()->type == CPP_OPEN_PAREN)
3934                     ife->trueexpr = parse_result (result, matcher);
3935                   else
3936                     ife->trueexpr = parse_op ();
3937                   eat_token (CPP_CLOSE_PAREN);
3938                 }
3939               else
3940                 {
3941                   /* switch default clause */
3942                   ife->falseexpr = parse_result (result, matcher);
3943                   eat_token (CPP_CLOSE_PAREN);
3944                   return res;
3945                 }
3946             }
3947           else
3948             {
3949               /* switch default clause */
3950               ife->falseexpr = parse_op ();
3951               eat_token (CPP_CLOSE_PAREN);
3952               return res;
3953             }
3954         }
3955       eat_token (CPP_CLOSE_PAREN);
3956       return res;
3957     }
3958   else
3959     {
3960       operand *op = result;
3961       if (!matcher)
3962         op = parse_expr ();
3963       eat_token (CPP_CLOSE_PAREN);
3964       return op;
3965     }
3966 }
3967
3968 /* Parse
3969      simplify = 'simplify' <expr> <result-op>
3970    or
3971      match = 'match' <ident> <expr> [<result-op>]
3972    and fill SIMPLIFIERS with the results.  */
3973
3974 void
3975 parser::parse_simplify (simplify::simplify_kind kind,
3976                         vec<simplify *>& simplifiers, predicate_id *matcher,
3977                         operand *result)
3978 {
3979   /* Reset the capture map.  */
3980   if (!capture_ids)
3981     capture_ids = new cid_map_t;
3982   /* Reset oper_lists and set.  */
3983   hash_set <user_id *> olist;
3984   oper_lists_set = &olist;
3985   oper_lists = vNULL;
3986
3987   const cpp_token *loc = peek ();
3988   parsing_match_operand = true;
3989   struct operand *match = parse_op ();
3990   parsing_match_operand = false;
3991   if (match->type == operand::OP_CAPTURE && !matcher)
3992     fatal_at (loc, "outermost expression cannot be captured");
3993   if (match->type == operand::OP_EXPR
3994       && is_a <predicate_id *> (as_a <expr *> (match)->operation))
3995     fatal_at (loc, "outermost expression cannot be a predicate");
3996
3997   /* Splice active_ifs onto result and continue parsing the
3998      "then" expr.  */
3999   if_expr *active_if = NULL;
4000   for (int i = active_ifs.length (); i > 0; --i)
4001     {
4002       if_expr *ifc = new if_expr (active_ifs[i-1]->location);
4003       ifc->cond = active_ifs[i-1];
4004       ifc->trueexpr = active_if;
4005       active_if = ifc;
4006     }
4007   if_expr *outermost_if = active_if;
4008   while (active_if && active_if->trueexpr)
4009     active_if = as_a <if_expr *> (active_if->trueexpr);
4010
4011   const cpp_token *token = peek ();
4012
4013   /* If this if is immediately closed then it is part of a predicate
4014      definition.  Push it.  */
4015   if (token->type == CPP_CLOSE_PAREN)
4016     {
4017       if (!matcher)
4018         fatal_at (token, "expected transform expression");
4019       if (active_if)
4020         {
4021           active_if->trueexpr = result;
4022           result = outermost_if;
4023         }
4024       push_simplify (kind, simplifiers, match, result);
4025       return;
4026     }
4027
4028   operand *tem = parse_result (result, matcher);
4029   if (active_if)
4030     {
4031       active_if->trueexpr = tem;
4032       result = outermost_if;
4033     }
4034   else
4035     result = tem;
4036
4037   push_simplify (kind, simplifiers, match, result);
4038 }
4039
4040 /* Parsing of the outer control structures.  */
4041
4042 /* Parse a for expression
4043      for = '(' 'for' <subst>... <pattern> ')'
4044      subst = <ident> '(' <ident>... ')'  */
4045
4046 void
4047 parser::parse_for (source_location)
4048 {
4049   auto_vec<const cpp_token *> user_id_tokens;
4050   vec<user_id *> user_ids = vNULL;
4051   const cpp_token *token;
4052   unsigned min_n_opers = 0, max_n_opers = 0;
4053
4054   while (1)
4055     {
4056       token = peek ();
4057       if (token->type != CPP_NAME)
4058         break;
4059
4060       /* Insert the user defined operators into the operator hash.  */
4061       const char *id = get_ident ();
4062       if (get_operator (id) != NULL)
4063         fatal_at (token, "operator already defined");
4064       user_id *op = new user_id (id);
4065       id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
4066       *slot = op;
4067       user_ids.safe_push (op);
4068       user_id_tokens.safe_push (token);
4069
4070       eat_token (CPP_OPEN_PAREN);
4071
4072       int arity = -1;
4073       while ((token = peek_ident ()) != 0)
4074         {
4075           const char *oper = get_ident ();
4076           id_base *idb = get_operator (oper);
4077           if (idb == NULL)
4078             fatal_at (token, "no such operator '%s'", oper);
4079           if (*idb == CONVERT0 || *idb == CONVERT1 || *idb == CONVERT2
4080               || *idb == VIEW_CONVERT0 || *idb == VIEW_CONVERT1
4081               || *idb == VIEW_CONVERT2)
4082             fatal_at (token, "conditional operators cannot be used inside for");
4083
4084           if (arity == -1)
4085             arity = idb->nargs;
4086           else if (idb->nargs == -1)
4087             ;
4088           else if (idb->nargs != arity)
4089             fatal_at (token, "operator '%s' with arity %d does not match "
4090                       "others with arity %d", oper, idb->nargs, arity);
4091
4092           user_id *p = dyn_cast<user_id *> (idb);
4093           if (p)
4094             {
4095               if (p->is_oper_list)
4096                 op->substitutes.safe_splice (p->substitutes);
4097               else
4098                 fatal_at (token, "iterator cannot be used as operator-list");
4099             }
4100           else
4101             op->substitutes.safe_push (idb);
4102         }
4103       op->nargs = arity;
4104       token = expect (CPP_CLOSE_PAREN);
4105
4106       unsigned nsubstitutes = op->substitutes.length ();
4107       if (nsubstitutes == 0)
4108         fatal_at (token, "A user-defined operator must have at least "
4109                   "one substitution");
4110       if (max_n_opers == 0)
4111         {
4112           min_n_opers = nsubstitutes;
4113           max_n_opers = nsubstitutes;
4114         }
4115       else
4116         {
4117           if (nsubstitutes % min_n_opers != 0
4118               && min_n_opers % nsubstitutes != 0)
4119             fatal_at (token, "All user-defined identifiers must have a "
4120                       "multiple number of operator substitutions of the "
4121                       "smallest number of substitutions");
4122           if (nsubstitutes < min_n_opers)
4123             min_n_opers = nsubstitutes;
4124           else if (nsubstitutes > max_n_opers)
4125             max_n_opers = nsubstitutes;
4126         }
4127     }
4128
4129   unsigned n_ids = user_ids.length ();
4130   if (n_ids == 0)
4131     fatal_at (token, "for requires at least one user-defined identifier");
4132
4133   token = peek ();
4134   if (token->type == CPP_CLOSE_PAREN)
4135     fatal_at (token, "no pattern defined in for");
4136
4137   active_fors.safe_push (user_ids);
4138   while (1)
4139     {
4140       token = peek ();
4141       if (token->type == CPP_CLOSE_PAREN)
4142         break;
4143       parse_pattern ();
4144     }
4145   active_fors.pop ();
4146
4147   /* Remove user-defined operators from the hash again.  */
4148   for (unsigned i = 0; i < user_ids.length (); ++i)
4149     {
4150       if (!user_ids[i]->used)
4151         warning_at (user_id_tokens[i],
4152                     "operator %s defined but not used", user_ids[i]->id);
4153       operators->remove_elt (user_ids[i]);
4154     }
4155 }
4156
4157 /* Parse an identifier associated with a list of operators.
4158      oprs = '(' 'define_operator_list' <ident> <ident>... ')'  */
4159
4160 void
4161 parser::parse_operator_list (source_location)
4162 {
4163   const cpp_token *token = peek ();
4164   const char *id = get_ident ();
4165
4166   if (get_operator (id) != 0)
4167     fatal_at (token, "operator %s already defined", id);
4168
4169   user_id *op = new user_id (id, true);
4170   int arity = -1;
4171
4172   while ((token = peek_ident ()) != 0)
4173     {
4174       token = peek ();
4175       const char *oper = get_ident ();
4176       id_base *idb = get_operator (oper);
4177
4178       if (idb == 0)
4179         fatal_at (token, "no such operator '%s'", oper);
4180
4181       if (arity == -1)
4182         arity = idb->nargs;
4183       else if (idb->nargs == -1)
4184         ;
4185       else if (arity != idb->nargs)
4186         fatal_at (token, "operator '%s' with arity %d does not match "
4187                          "others with arity %d", oper, idb->nargs, arity);
4188
4189       /* We allow composition of multiple operator lists.  */
4190       if (user_id *p = dyn_cast<user_id *> (idb))
4191         op->substitutes.safe_splice (p->substitutes);
4192       else
4193         op->substitutes.safe_push (idb);
4194     }
4195
4196   // Check that there is no junk after id-list
4197   token = peek();
4198   if (token->type != CPP_CLOSE_PAREN)
4199     fatal_at (token, "expected identifier got %s", cpp_type2name (token->type, 0));
4200
4201   if (op->substitutes.length () == 0)
4202     fatal_at (token, "operator-list cannot be empty");
4203
4204   op->nargs = arity;
4205   id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
4206   *slot = op;
4207 }
4208
4209 /* Parse an outer if expression.
4210      if = '(' 'if' '(' <c-expr> ')' <pattern> ')'  */
4211
4212 void
4213 parser::parse_if (source_location)
4214 {
4215   c_expr *ifexpr = parse_c_expr (CPP_OPEN_PAREN);
4216
4217   const cpp_token *token = peek ();
4218   if (token->type == CPP_CLOSE_PAREN)
4219     fatal_at (token, "no pattern defined in if");
4220
4221   active_ifs.safe_push (ifexpr);
4222   while (1)
4223     {
4224       const cpp_token *token = peek ();
4225       if (token->type == CPP_CLOSE_PAREN)
4226         break;
4227
4228       parse_pattern ();
4229     }
4230   active_ifs.pop ();
4231 }
4232
4233 /* Parse a list of predefined predicate identifiers.
4234      preds = '(' 'define_predicates' <ident>... ')'  */
4235
4236 void
4237 parser::parse_predicates (source_location)
4238 {
4239   do
4240     {
4241       const cpp_token *token = peek ();
4242       if (token->type != CPP_NAME)
4243         break;
4244
4245       add_predicate (get_ident ());
4246     }
4247   while (1);
4248 }
4249
4250 /* Parse outer control structures.
4251      pattern = <preds>|<for>|<if>|<simplify>|<match>  */
4252
4253 void
4254 parser::parse_pattern ()
4255 {
4256   /* All clauses start with '('.  */
4257   eat_token (CPP_OPEN_PAREN);
4258   const cpp_token *token = peek ();
4259   const char *id = get_ident ();
4260   if (strcmp (id, "simplify") == 0)
4261     {
4262       parse_simplify (simplify::SIMPLIFY, simplifiers, NULL, NULL);
4263       capture_ids = NULL;
4264     }
4265   else if (strcmp (id, "match") == 0)
4266     {
4267       bool with_args = false;
4268       source_location e_loc = peek ()->src_loc;
4269       if (peek ()->type == CPP_OPEN_PAREN)
4270         {
4271           eat_token (CPP_OPEN_PAREN);
4272           with_args = true;
4273         }
4274       const char *name = get_ident ();
4275       id_base *id = get_operator (name);
4276       predicate_id *p;
4277       if (!id)
4278         {
4279           p = add_predicate (name);
4280           user_predicates.safe_push (p);
4281         }
4282       else if ((p = dyn_cast <predicate_id *> (id)))
4283         ;
4284       else
4285         fatal_at (token, "cannot add a match to a non-predicate ID");
4286       /* Parse (match <id> <arg>... (match-expr)) here.  */
4287       expr *e = NULL;
4288       if (with_args)
4289         {
4290           capture_ids = new cid_map_t;
4291           e = new expr (p, e_loc);
4292           while (peek ()->type == CPP_ATSIGN)
4293             e->append_op (parse_capture (NULL, false));
4294           eat_token (CPP_CLOSE_PAREN);
4295         }
4296       if (p->nargs != -1
4297           && ((e && e->ops.length () != (unsigned)p->nargs)
4298               || (!e && p->nargs != 0)))
4299         fatal_at (token, "non-matching number of match operands");
4300       p->nargs = e ? e->ops.length () : 0;
4301       parse_simplify (simplify::MATCH, p->matchers, p, e);
4302       capture_ids = NULL;
4303     }
4304   else if (strcmp (id, "for") == 0)
4305     parse_for (token->src_loc);
4306   else if (strcmp (id, "if") == 0)
4307     parse_if (token->src_loc);
4308   else if (strcmp (id, "define_predicates") == 0)
4309     {
4310       if (active_ifs.length () > 0
4311           || active_fors.length () > 0)
4312         fatal_at (token, "define_predicates inside if or for is not supported");
4313       parse_predicates (token->src_loc);
4314     }
4315   else if (strcmp (id, "define_operator_list") == 0)
4316     {
4317       if (active_ifs.length () > 0
4318           || active_fors.length () > 0)
4319         fatal_at (token, "operator-list inside if or for is not supported");
4320       parse_operator_list (token->src_loc);
4321     }
4322   else
4323     fatal_at (token, "expected %s'simplify', 'match', 'for' or 'if'",
4324               active_ifs.length () == 0 && active_fors.length () == 0
4325               ? "'define_predicates', " : "");
4326
4327   eat_token (CPP_CLOSE_PAREN);
4328 }
4329
4330 /* Main entry of the parser.  Repeatedly parse outer control structures.  */
4331
4332 parser::parser (cpp_reader *r_)
4333 {
4334   r = r_;
4335   active_ifs = vNULL;
4336   active_fors = vNULL;
4337   simplifiers = vNULL;
4338   oper_lists_set = NULL;
4339   oper_lists = vNULL;
4340   capture_ids = NULL;
4341   user_predicates = vNULL;
4342   parsing_match_operand = false;
4343
4344   const cpp_token *token = next ();
4345   while (token->type != CPP_EOF)
4346     {
4347       _cpp_backup_tokens (r, 1);
4348       parse_pattern ();
4349       token = next ();
4350     }
4351 }
4352
4353
4354 /* Helper for the linemap code.  */
4355
4356 static size_t
4357 round_alloc_size (size_t s)
4358 {
4359   return s;
4360 }
4361
4362
4363 /* The genmatch generator progam.  It reads from a pattern description
4364    and outputs GIMPLE or GENERIC IL matching and simplification routines.  */
4365
4366 int
4367 main (int argc, char **argv)
4368 {
4369   cpp_reader *r;
4370
4371   progname = "genmatch";
4372
4373   if (argc < 2)
4374     return 1;
4375
4376   bool gimple = true;
4377   char *input = argv[argc-1];
4378   for (int i = 1; i < argc - 1; ++i)
4379     {
4380       if (strcmp (argv[i], "--gimple") == 0)
4381         gimple = true;
4382       else if (strcmp (argv[i], "--generic") == 0)
4383         gimple = false;
4384       else if (strcmp (argv[i], "-v") == 0)
4385         verbose = 1;
4386       else if (strcmp (argv[i], "-vv") == 0)
4387         verbose = 2;
4388       else
4389         {
4390           fprintf (stderr, "Usage: genmatch "
4391                    "[--gimple] [--generic] [-v[v]] input\n");
4392           return 1;
4393         }
4394     }
4395
4396   line_table = XCNEW (struct line_maps);
4397   linemap_init (line_table, 0);
4398   line_table->reallocator = xrealloc;
4399   line_table->round_alloc_size = round_alloc_size;
4400
4401   r = cpp_create_reader (CLK_GNUC99, NULL, line_table);
4402   cpp_callbacks *cb = cpp_get_callbacks (r);
4403   cb->error = error_cb;
4404
4405   if (!cpp_read_main_file (r, input))
4406     return 1;
4407   cpp_define (r, gimple ? "GIMPLE=1": "GENERIC=1");
4408   cpp_define (r, gimple ? "GENERIC=0": "GIMPLE=0");
4409
4410   /* Pre-seed operators.  */
4411   operators = new hash_table<id_base> (1024);
4412 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
4413   add_operator (SYM, # SYM, # TYPE, NARGS);
4414 #define END_OF_BASE_TREE_CODES
4415 #include "tree.def"
4416 add_operator (CONVERT0, "CONVERT0", "tcc_unary", 1);
4417 add_operator (CONVERT1, "CONVERT1", "tcc_unary", 1);
4418 add_operator (CONVERT2, "CONVERT2", "tcc_unary", 1);
4419 add_operator (VIEW_CONVERT0, "VIEW_CONVERT0", "tcc_unary", 1);
4420 add_operator (VIEW_CONVERT1, "VIEW_CONVERT1", "tcc_unary", 1);
4421 add_operator (VIEW_CONVERT2, "VIEW_CONVERT2", "tcc_unary", 1);
4422 #undef END_OF_BASE_TREE_CODES
4423 #undef DEFTREECODE
4424
4425   /* Pre-seed builtin functions.
4426      ???  Cannot use N (name) as that is targetm.emultls.get_address
4427      for BUILT_IN_EMUTLS_GET_ADDRESS ... */
4428 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
4429   add_builtin (ENUM, # ENUM);
4430 #include "builtins.def"
4431 #undef DEF_BUILTIN
4432
4433   /* Parse ahead!  */
4434   parser p (r);
4435
4436   if (gimple)
4437     write_header (stdout, "gimple-match-head.c");
4438   else
4439     write_header (stdout, "generic-match-head.c");
4440
4441   /* Go over all predicates defined with patterns and perform
4442      lowering and code generation.  */
4443   for (unsigned i = 0; i < p.user_predicates.length (); ++i)
4444     {
4445       predicate_id *pred = p.user_predicates[i];
4446       lower (pred->matchers, gimple);
4447
4448       if (verbose == 2)
4449         for (unsigned i = 0; i < pred->matchers.length (); ++i)
4450           print_matches (pred->matchers[i]);
4451
4452       decision_tree dt;
4453       for (unsigned i = 0; i < pred->matchers.length (); ++i)
4454         dt.insert (pred->matchers[i], i);
4455
4456       if (verbose == 2)
4457         dt.print (stderr);
4458
4459       write_predicate (stdout, pred, dt, gimple);
4460     }
4461
4462   /* Lower the main simplifiers and generate code for them.  */
4463   lower (p.simplifiers, gimple);
4464
4465   if (verbose == 2)
4466     for (unsigned i = 0; i < p.simplifiers.length (); ++i)
4467       print_matches (p.simplifiers[i]);
4468
4469   decision_tree dt;
4470   for (unsigned i = 0; i < p.simplifiers.length (); ++i)
4471     dt.insert (p.simplifiers[i], i);
4472
4473   if (verbose == 2)
4474     dt.print (stderr);
4475
4476   dt.gen (stdout, gimple);
4477
4478   /* Finalize.  */
4479   cpp_finish (r, NULL);
4480   cpp_destroy (r);
4481
4482   delete operators;
4483
4484   return 0;
4485 }