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