gcc/genmatch.c

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