gcc/genmatch.c

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