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