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