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