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