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 capture uses as forced to have
1649          no side-effects. */
1650       if (c->what
1651           && is_a <expr *> (c->what))
1652         {
1653           info[c->where].cse_p = true;
1654           walk_result (c->what, true);
1655         }
1656     }
1657   else if (expr *e = dyn_cast <expr *> (o))
1658     {
1659       for (unsigned i = 0; i < e->ops.length (); ++i)
1660         {
1661           bool cond_p = conditional_p;
1662           if (i != 0 && *e->operation == COND_EXPR)
1663             cond_p = true;
1664           else if (*e->operation == TRUTH_ANDIF_EXPR
1665                    || *e->operation == TRUTH_ORIF_EXPR)
1666             cond_p = true;
1667           walk_result (e->ops[i], cond_p);
1668         }
1669     }
1670   else if (c_expr *e = dyn_cast <c_expr *> (o))
1671     walk_c_expr (e);
1672   else
1673     gcc_unreachable ();
1674 }
1675
1676 /* Look for captures in the C expr E.  */
1677
1678 void
1679 capture_info::walk_c_expr (c_expr *e)
1680 {
1681   /* Give up for C exprs mentioning captures not inside TREE_TYPE ().  */
1682   unsigned p_depth = 0;
1683   for (unsigned i = 0; i < e->code.length (); ++i)
1684     {
1685       const cpp_token *t = &e->code[i];
1686       const cpp_token *n = i < e->code.length () - 1 ? &e->code[i+1] : NULL;
1687       if (t->type == CPP_NAME
1688           && strcmp ((const char *)CPP_HASHNODE
1689                        (t->val.node.node)->ident.str, "TREE_TYPE") == 0
1690           && n->type == CPP_OPEN_PAREN)
1691         p_depth++;
1692       else if (t->type == CPP_CLOSE_PAREN
1693                && p_depth > 0)
1694         p_depth--;
1695       else if (p_depth == 0
1696                && t->type == CPP_ATSIGN
1697                && (n->type == CPP_NUMBER
1698                    || n->type == CPP_NAME)
1699                && !(n->flags & PREV_WHITE))
1700         {
1701           const char *id;
1702           if (n->type == CPP_NUMBER)
1703             id = (const char *)n->val.str.text;
1704           else
1705             id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
1706           info[*e->capture_ids->get(id)].force_no_side_effects_p = true;
1707         }
1708     }
1709 }
1710
1711
1712 /* Code generation off the decision tree and the refered AST nodes.  */
1713
1714 bool
1715 is_conversion (id_base *op)
1716 {
1717   return (*op == CONVERT_EXPR
1718           || *op == NOP_EXPR
1719           || *op == FLOAT_EXPR
1720           || *op == FIX_TRUNC_EXPR
1721           || *op == VIEW_CONVERT_EXPR);
1722 }
1723
1724 /* Get the type to be used for generating operands of OP from the
1725    various sources.  */
1726
1727 static const char *
1728 get_operand_type (id_base *op, const char *in_type,
1729                   const char *expr_type,
1730                   const char *other_oprnd_type)
1731 {
1732   /* Generally operands whose type does not match the type of the
1733      expression generated need to know their types but match and
1734      thus can fall back to 'other_oprnd_type'.  */
1735   if (is_conversion (op))
1736     return other_oprnd_type;
1737   else if (*op == REALPART_EXPR
1738            || *op == IMAGPART_EXPR)
1739     return other_oprnd_type;
1740   else if (is_a <operator_id *> (op)
1741            && strcmp (as_a <operator_id *> (op)->tcc, "tcc_comparison") == 0)
1742     return other_oprnd_type;
1743   else
1744     {
1745       /* Otherwise all types should match - choose one in order of
1746          preference.  */
1747       if (expr_type)
1748         return expr_type;
1749       else if (in_type)
1750         return in_type;
1751       else
1752         return other_oprnd_type;
1753     }
1754 }
1755
1756 /* Generate transform code for an expression.  */
1757
1758 void
1759 expr::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
1760                      int depth, const char *in_type, capture_info *cinfo,
1761                      dt_operand **indexes, bool)
1762 {
1763   bool conversion_p = is_conversion (operation);
1764   const char *type = expr_type;
1765   char optype[64];
1766   if (type)
1767     /* If there was a type specification in the pattern use it.  */
1768     ;
1769   else if (conversion_p)
1770     /* For conversions we need to build the expression using the
1771        outer type passed in.  */
1772     type = in_type;
1773   else if (*operation == REALPART_EXPR
1774            || *operation == IMAGPART_EXPR)
1775     {
1776       /* __real and __imag use the component type of its operand.  */
1777       sprintf (optype, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth);
1778       type = optype;
1779     }
1780   else if (is_a <operator_id *> (operation)
1781            && !strcmp (as_a <operator_id *> (operation)->tcc, "tcc_comparison"))
1782     {
1783       /* comparisons use boolean_type_node (or what gets in), but
1784          their operands need to figure out the types themselves.  */
1785       sprintf (optype, "boolean_type_node");
1786       type = optype;
1787     }
1788   else if (*operation == COND_EXPR
1789            || *operation == VEC_COND_EXPR)
1790     {
1791       /* Conditions are of the same type as their first alternative.  */
1792       sprintf (optype, "TREE_TYPE (ops%d[1])", depth);
1793       type = optype;
1794     }
1795   else
1796     {
1797       /* Other operations are of the same type as their first operand.  */
1798       sprintf (optype, "TREE_TYPE (ops%d[0])", depth);
1799       type = optype;
1800     }
1801   if (!type)
1802     fatal ("two conversions in a row");
1803
1804   fprintf_indent (f, indent, "{\n");
1805   indent += 2;
1806   fprintf_indent (f, indent, "tree ops%d[%u], res;\n", depth, ops.length ());
1807   char op0type[64];
1808   snprintf (op0type, 64, "TREE_TYPE (ops%d[0])", depth);
1809   for (unsigned i = 0; i < ops.length (); ++i)
1810     {
1811       char dest[32];
1812       snprintf (dest, 32, "ops%d[%u]", depth, i);
1813       const char *optype
1814         = get_operand_type (operation, in_type, expr_type,
1815                             i == 0 ? NULL : op0type);
1816       ops[i]->gen_transform (f, indent, dest, gimple, depth + 1, optype,
1817                              cinfo, indexes,
1818                              ((!(*operation == COND_EXPR)
1819                                && !(*operation == VEC_COND_EXPR))
1820                               || i != 0));
1821     }
1822
1823   const char *opr;
1824   if (*operation == CONVERT_EXPR)
1825     opr = "NOP_EXPR";
1826   else
1827     opr = operation->id;
1828
1829   if (gimple)
1830     {
1831       if (*operation == CONVERT_EXPR)
1832         {
1833           fprintf_indent (f, indent,
1834                           "if (%s != TREE_TYPE (ops%d[0])\n",
1835                           type, depth);
1836           fprintf_indent (f, indent,
1837                           "    && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
1838                           type, depth);
1839           fprintf_indent (f, indent + 2, "{\n");
1840           indent += 4;
1841         }
1842       /* ???  Building a stmt can fail for various reasons here, seq being
1843          NULL or the stmt referencing SSA names occuring in abnormal PHIs.
1844          So if we fail here we should continue matching other patterns.  */
1845       fprintf_indent (f, indent, "code_helper tem_code = %s;\n", opr);
1846       fprintf_indent (f, indent, "tree tem_ops[3] = { ");
1847       for (unsigned i = 0; i < ops.length (); ++i)
1848         fprintf (f, "ops%d[%u]%s", depth, i,
1849                  i == ops.length () - 1 ? " };\n" : ", ");
1850       fprintf_indent (f, indent,
1851                       "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
1852                       ops.length (), type);
1853       fprintf_indent (f, indent,
1854                       "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
1855                       type);
1856       fprintf_indent (f, indent,
1857                       "if (!res) return false;\n");
1858       if (*operation == CONVERT_EXPR)
1859         {
1860           indent -= 4;
1861           fprintf_indent (f, indent, "  }\n");
1862           fprintf_indent (f, indent, "else\n");
1863           fprintf_indent (f, indent, "  res = ops%d[0];\n", depth);
1864         }
1865     }
1866   else
1867     {
1868       if (*operation == CONVERT_EXPR)
1869         {
1870           fprintf_indent (f, indent, "if (TREE_TYPE (ops%d[0]) != %s)\n",
1871                           depth, type);
1872           indent += 2;
1873         }
1874       if (operation->kind == id_base::CODE)
1875         fprintf_indent (f, indent, "res = fold_build%d_loc (loc, %s, %s",
1876                         ops.length(), opr, type);
1877       else
1878         fprintf_indent (f, indent, "res = build_call_expr_loc (loc, "
1879                         "builtin_decl_implicit (%s), %d", opr, ops.length());
1880       for (unsigned i = 0; i < ops.length (); ++i)
1881         fprintf (f, ", ops%d[%u]", depth, i);
1882       fprintf (f, ");\n");
1883       if (*operation == CONVERT_EXPR)
1884         {
1885           indent -= 2;
1886           fprintf_indent (f, indent, "else\n");
1887           fprintf_indent (f, indent, "  res = ops%d[0];\n", depth);
1888         }
1889     }
1890   fprintf_indent (f, indent, "%s = res;\n", dest);
1891   indent -= 2;
1892   fprintf_indent (f, indent, "}\n");
1893 }
1894
1895 /* Generate code for a c_expr which is either the expression inside
1896    an if statement or a sequence of statements which computes a
1897    result to be stored to DEST.  */
1898
1899 void
1900 c_expr::gen_transform (FILE *f, int indent, const char *dest,
1901                        bool, int, const char *, capture_info *,
1902                        dt_operand **, bool)
1903 {
1904   if (dest && nr_stmts == 1)
1905     fprintf_indent (f, indent, "%s = ", dest);
1906
1907   unsigned stmt_nr = 1;
1908   for (unsigned i = 0; i < code.length (); ++i)
1909     {
1910       const cpp_token *token = &code[i];
1911
1912       /* Replace captures for code-gen.  */
1913       if (token->type == CPP_ATSIGN)
1914         {
1915           const cpp_token *n = &code[i+1];
1916           if ((n->type == CPP_NUMBER
1917                || n->type == CPP_NAME)
1918               && !(n->flags & PREV_WHITE))
1919             {
1920               if (token->flags & PREV_WHITE)
1921                 fputc (' ', f);
1922               const char *id;
1923               if (n->type == CPP_NUMBER)
1924                 id = (const char *)n->val.str.text;
1925               else
1926                 id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
1927               fprintf (f, "captures[%u]", *capture_ids->get(id));
1928               ++i;
1929               continue;
1930             }
1931         }
1932
1933       if (token->flags & PREV_WHITE)
1934         fputc (' ', f);
1935
1936       if (token->type == CPP_NAME)
1937         {
1938           const char *id = (const char *) NODE_NAME (token->val.node.node);
1939           unsigned j;
1940           for (j = 0; j < ids.length (); ++j)
1941             {
1942             if (strcmp (id, ids[j].id) == 0)
1943               {
1944                 fprintf (f, "%s", ids[j].oper);
1945                 break;
1946               }
1947             }
1948           if (j < ids.length ())
1949             continue;
1950         }
1951
1952       /* Output the token as string.  */
1953       char *tk = (char *)cpp_token_as_text (r, token);
1954       fputs (tk, f);
1955
1956       if (token->type == CPP_SEMICOLON)
1957         {
1958           stmt_nr++;
1959           fputc ('\n', f);
1960           if (dest && stmt_nr == nr_stmts)
1961             fprintf_indent (f, indent, "%s = ", dest);
1962         }
1963     }
1964 }
1965
1966 /* Generate transform code for a capture.  */
1967
1968 void
1969 capture::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
1970                         int depth, const char *in_type, capture_info *cinfo,
1971                         dt_operand **indexes, bool expand_compares)
1972 {
1973   if (what && is_a<expr *> (what))
1974     {
1975       if (indexes[where] == 0)
1976         {
1977           char buf[20];
1978           sprintf (buf, "captures[%u]", where);
1979           what->gen_transform (f, indent, buf, gimple, depth, in_type,
1980                                cinfo, NULL);
1981         }
1982     }
1983
1984   fprintf_indent (f, indent, "%s = captures[%u];\n", dest, where);
1985
1986   /* ???  Stupid tcc_comparison GENERIC trees in COND_EXPRs.  Deal
1987      with substituting a capture of that.
1988      ???  Returning false here will also not allow any other patterns
1989      to match.  */
1990   if (gimple && expand_compares
1991       && cinfo->info[where].cond_expr_cond_p)
1992     {
1993       fprintf_indent (f, indent, "if (COMPARISON_CLASS_P (%s))\n", dest);
1994       fprintf_indent (f, indent, "  {\n");
1995       fprintf_indent (f, indent, "    if (!seq) return false;\n");
1996       fprintf_indent (f, indent, "    %s = gimple_build (seq, TREE_CODE (%s),"
1997                                  " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
1998                                  " TREE_OPERAND (%s, 1));\n",
1999                                  dest, dest, dest, dest, dest);
2000       fprintf_indent (f, indent, "  }\n");
2001     }
2002 }
2003
2004 /* Return the name of the operand representing the decision tree node.
2005    Use NAME as space to generate it.  */
2006
2007 char *
2008 dt_operand::get_name (char *name)
2009 {
2010   if (!parent)
2011     sprintf (name, "t");
2012   else if (parent->level == 1)
2013     sprintf (name, "op%u", pos);
2014   else if (parent->type == dt_node::DT_MATCH)
2015     return parent->get_name (name);
2016   else
2017     sprintf (name, "o%u%u", parent->level, pos);
2018   return name;
2019 }
2020
2021 /* Fill NAME with the operand name at position POS.  */
2022
2023 void
2024 dt_operand::gen_opname (char *name, unsigned pos)
2025 {
2026   if (!parent)
2027     sprintf (name, "op%u", pos);
2028   else
2029     sprintf (name, "o%u%u", level, pos);
2030 }
2031
2032 /* Generate matching code for the decision tree operand which is
2033    a predicate.  */
2034
2035 unsigned
2036 dt_operand::gen_predicate (FILE *f, int indent, const char *opname, bool gimple)
2037 {
2038   predicate *p = as_a <predicate *> (op);
2039
2040   if (p->p->matchers.exists ())
2041     {
2042       /* If this is a predicate generated from a pattern mangle its
2043          name and pass on the valueize hook.  */
2044       if (gimple)
2045         fprintf_indent (f, indent, "if (gimple_%s (%s, valueize))\n",
2046                         p->p->id, opname);
2047       else
2048         fprintf_indent (f, indent, "if (tree_%s (%s))\n", p->p->id, opname);
2049     }
2050   else
2051     fprintf_indent (f, indent, "if (%s (%s))\n", p->p->id, opname);
2052   fprintf_indent (f, indent + 2, "{\n");
2053   return 1;
2054 }
2055
2056 /* Generate matching code for the decision tree operand which is
2057    a capture-match.  */
2058
2059 unsigned
2060 dt_operand::gen_match_op (FILE *f, int indent, const char *opname)
2061 {
2062   char match_opname[20];
2063   match_dop->get_name (match_opname);
2064   fprintf_indent (f, indent, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2065                   opname, match_opname, opname, match_opname);
2066   fprintf_indent (f, indent + 2, "{\n");
2067   return 1;
2068 }
2069
2070 /* Generate GIMPLE matching code for the decision tree operand.  */
2071
2072 unsigned
2073 dt_operand::gen_gimple_expr (FILE *f, int indent)
2074 {
2075   expr *e = static_cast<expr *> (op);
2076   id_base *id = e->operation;
2077   unsigned n_ops = e->ops.length ();
2078
2079   for (unsigned i = 0; i < n_ops; ++i)
2080     {
2081       char child_opname[20];
2082       gen_opname (child_opname, i);
2083
2084       if (id->kind == id_base::CODE)
2085         {
2086           if (e->is_generic
2087               || *id == REALPART_EXPR || *id == IMAGPART_EXPR
2088               || *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR)
2089             {
2090               /* ???  If this is a memory operation we can't (and should not)
2091                  match this.  The only sensible operand types are
2092                  SSA names and invariants.  */
2093               fprintf_indent (f, indent,
2094                               "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
2095                               child_opname, i);
2096               fprintf_indent (f, indent,
2097                               "if ((TREE_CODE (%s) == SSA_NAME\n",
2098                               child_opname);
2099               fprintf_indent (f, indent,
2100                               "     || is_gimple_min_invariant (%s))\n",
2101                               child_opname);
2102               fprintf_indent (f, indent,
2103                               "    && (%s = do_valueize (valueize, %s)))\n",
2104                               child_opname, child_opname);
2105               fprintf_indent (f, indent,
2106                               "  {\n");
2107               indent += 4;
2108               continue;
2109             }
2110           else
2111             fprintf_indent (f, indent,
2112                             "tree %s = gimple_assign_rhs%u (def_stmt);\n",
2113                             child_opname, i + 1);
2114         }
2115       else
2116         fprintf_indent (f, indent,
2117                         "tree %s = gimple_call_arg (def_stmt, %u);\n",
2118                         child_opname, i);
2119       fprintf_indent (f, indent,
2120                       "if ((%s = do_valueize (valueize, %s)))\n",
2121                       child_opname, child_opname);
2122       fprintf_indent (f, indent, "  {\n");
2123       indent += 4;
2124     }
2125   /* While the toplevel operands are canonicalized by the caller
2126      after valueizing operands of sub-expressions we have to
2127      re-canonicalize operand order.  */
2128   if (operator_id *code = dyn_cast <operator_id *> (id))
2129     {
2130       /* ???  We can't canonicalize tcc_comparison operands here
2131          because that requires changing the comparison code which
2132          we already matched...  */
2133       if (commutative_tree_code (code->code)
2134           || commutative_ternary_tree_code (code->code))
2135         {
2136           char child_opname0[20], child_opname1[20];
2137           gen_opname (child_opname0, 0);
2138           gen_opname (child_opname1, 1);
2139           fprintf_indent (f, indent,
2140                           "if (tree_swap_operands_p (%s, %s, false))\n",
2141                           child_opname0, child_opname1);
2142           fprintf_indent (f, indent,
2143                           "  std::swap (%s, %s);\n",
2144                           child_opname0, child_opname1);
2145         }
2146     }
2147
2148   return n_ops;
2149 }
2150
2151 /* Generate GENERIC matching code for the decision tree operand.  */
2152
2153 unsigned
2154 dt_operand::gen_generic_expr (FILE *f, int indent, const char *opname)
2155 {
2156   expr *e = static_cast<expr *> (op);
2157   unsigned n_ops = e->ops.length ();
2158
2159   for (unsigned i = 0; i < n_ops; ++i)
2160     {
2161       char child_opname[20];
2162       gen_opname (child_opname, i);
2163
2164       if (e->operation->kind == id_base::CODE)
2165         fprintf_indent (f, indent, "tree %s = TREE_OPERAND (%s, %u);\n",
2166                         child_opname, opname, i);
2167       else
2168         fprintf_indent (f, indent, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2169                         child_opname, opname, i);
2170     }
2171
2172   return 0;
2173 }
2174
2175 /* Generate matching code for the children of the decision tree node.  */
2176
2177 void
2178 dt_node::gen_kids (FILE *f, int indent, bool gimple)
2179 {
2180   auto_vec<dt_operand *> gimple_exprs;
2181   auto_vec<dt_operand *> generic_exprs;
2182   auto_vec<dt_operand *> fns;
2183   auto_vec<dt_operand *> generic_fns;
2184   auto_vec<dt_operand *> preds;
2185   auto_vec<dt_node *> others;
2186
2187   for (unsigned i = 0; i < kids.length (); ++i)
2188     {
2189       if (kids[i]->type == dt_node::DT_OPERAND)
2190         {
2191           dt_operand *op = as_a<dt_operand *> (kids[i]);
2192           if (expr *e = dyn_cast <expr *> (op->op))
2193             {
2194               if (e->ops.length () == 0
2195                   && (!gimple || !(*e->operation == CONSTRUCTOR)))
2196                 generic_exprs.safe_push (op);
2197               else if (e->operation->kind == id_base::FN)
2198                 {
2199                   if (gimple)
2200                     fns.safe_push (op);
2201                   else
2202                     generic_fns.safe_push (op);
2203                 }
2204               else if (e->operation->kind == id_base::PREDICATE)
2205                 preds.safe_push (op);
2206               else
2207                 {
2208                   if (gimple)
2209                     gimple_exprs.safe_push (op);
2210                   else
2211                     generic_exprs.safe_push (op);
2212                 }
2213             }
2214           else if (op->op->type == operand::OP_PREDICATE)
2215             others.safe_push (kids[i]);
2216           else
2217             gcc_unreachable ();
2218         }
2219       else if (kids[i]->type == dt_node::DT_MATCH
2220                || kids[i]->type == dt_node::DT_SIMPLIFY)
2221         others.safe_push (kids[i]);
2222       else if (kids[i]->type == dt_node::DT_TRUE)
2223         {
2224           /* A DT_TRUE operand serves as a barrier - generate code now
2225              for what we have collected sofar.  */
2226           gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2227                       fns, generic_fns, preds, others);
2228           /* And output the true operand itself.  */
2229           kids[i]->gen (f, indent, gimple);
2230           gimple_exprs.truncate (0);
2231           generic_exprs.truncate (0);
2232           fns.truncate (0);
2233           generic_fns.truncate (0);
2234           preds.truncate (0);
2235           others.truncate (0);
2236         }
2237       else
2238         gcc_unreachable ();
2239     }
2240
2241   /* Generate code for the remains.  */
2242   gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2243               fns, generic_fns, preds, others);
2244 }
2245
2246 /* Generate matching code for the children of the decision tree node.  */
2247
2248 void
2249 dt_node::gen_kids_1 (FILE *f, int indent, bool gimple,
2250                      vec<dt_operand *> gimple_exprs,
2251                      vec<dt_operand *> generic_exprs,
2252                      vec<dt_operand *> fns,
2253                      vec<dt_operand *> generic_fns,
2254                      vec<dt_operand *> preds,
2255                      vec<dt_node *> others)
2256 {
2257   char buf[128];
2258   char *kid_opname = buf;
2259
2260   unsigned exprs_len = gimple_exprs.length ();
2261   unsigned gexprs_len = generic_exprs.length ();
2262   unsigned fns_len = fns.length ();
2263   unsigned gfns_len = generic_fns.length ();
2264
2265   if (exprs_len || fns_len || gexprs_len || gfns_len)
2266     {
2267       if (exprs_len)
2268         gimple_exprs[0]->get_name (kid_opname);
2269       else if (fns_len)
2270         fns[0]->get_name (kid_opname);
2271       else if (gfns_len)
2272         generic_fns[0]->get_name (kid_opname);
2273       else
2274         generic_exprs[0]->get_name (kid_opname);
2275
2276       fprintf_indent (f, indent, "switch (TREE_CODE (%s))\n", kid_opname);
2277       fprintf_indent (f, indent, "  {\n");
2278       indent += 2;
2279     }
2280
2281   if (exprs_len || fns_len)
2282     {
2283       fprintf_indent (f, indent,
2284                       "case SSA_NAME:\n");
2285       fprintf_indent (f, indent,
2286                       "  if (do_valueize (valueize, %s) != NULL_TREE)\n",
2287                       kid_opname);
2288       fprintf_indent (f, indent,
2289                       "    {\n");
2290       fprintf_indent (f, indent,
2291                       "      gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2292                       kid_opname);
2293
2294       indent += 6;
2295       if (exprs_len)
2296         {
2297           fprintf_indent (f, indent,
2298                           "if (is_gimple_assign (def_stmt))\n");
2299           fprintf_indent (f, indent,
2300                           "  switch (gimple_assign_rhs_code (def_stmt))\n");
2301           indent += 4;
2302           fprintf_indent (f, indent, "{\n");
2303           for (unsigned i = 0; i < exprs_len; ++i)
2304             {
2305               expr *e = as_a <expr *> (gimple_exprs[i]->op);
2306               id_base *op = e->operation;
2307               if (*op == CONVERT_EXPR || *op == NOP_EXPR)
2308                 fprintf_indent (f, indent, "CASE_CONVERT:\n");
2309               else
2310                 fprintf_indent (f, indent, "case %s:\n", op->id);
2311               fprintf_indent (f, indent, "  {\n");
2312               gimple_exprs[i]->gen (f, indent + 4, true);
2313               fprintf_indent (f, indent, "    break;\n");
2314               fprintf_indent (f, indent, "  }\n");
2315             }
2316           fprintf_indent (f, indent, "default:;\n");
2317           indent -= 4;
2318           fprintf_indent (f, indent, "}\n");
2319         }
2320
2321       if (fns_len)
2322         {
2323           if (exprs_len)
2324             fprintf_indent (f, indent, "else ");
2325           else
2326             fprintf_indent (f, indent, " ");
2327
2328           fprintf (f, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n");
2329           fprintf_indent (f, indent,
2330                           "  {\n");
2331           fprintf_indent (f, indent,
2332                           "    tree fndecl = gimple_call_fndecl (def_stmt);\n");
2333           fprintf_indent (f, indent,
2334                           "    switch (DECL_FUNCTION_CODE (fndecl))\n");
2335           fprintf_indent (f, indent,
2336                           "      {\n");
2337           indent += 8;
2338
2339           for (unsigned i = 0; i < fns_len; ++i)
2340             {
2341               expr *e = as_a <expr *>(fns[i]->op);
2342               fprintf_indent (f, indent, "case %s:\n", e->operation->id);
2343               fprintf_indent (f, indent, "  {\n");
2344               fns[i]->gen (f, indent + 4, true);
2345               fprintf_indent (f, indent, "    break;\n");
2346               fprintf_indent (f, indent, "  }\n");
2347             }
2348
2349           fprintf_indent (f, indent, "default:;\n");
2350           indent -= 8;
2351           fprintf_indent (f, indent, "      }\n");
2352           fprintf_indent (f, indent, "  }\n");
2353         }
2354
2355       indent -= 6;
2356       fprintf_indent (f, indent, "    }\n");
2357       fprintf_indent (f, indent, "  break;\n");
2358     }
2359
2360   for (unsigned i = 0; i < generic_exprs.length (); ++i)
2361     {
2362       expr *e = as_a <expr *>(generic_exprs[i]->op);
2363       id_base *op = e->operation;
2364       if (*op == CONVERT_EXPR || *op == NOP_EXPR)
2365         fprintf_indent (f, indent, "CASE_CONVERT:\n");
2366       else
2367         fprintf_indent (f, indent, "case %s:\n", op->id);
2368       fprintf_indent (f, indent, "  {\n");
2369       generic_exprs[i]->gen (f, indent + 4, gimple);
2370       fprintf_indent (f, indent, "    break;\n");
2371       fprintf_indent (f, indent, "  }\n");
2372     }
2373
2374   if (gfns_len)
2375     {
2376       fprintf_indent (f, indent,
2377                       "case CALL_EXPR:\n");
2378       fprintf_indent (f, indent,
2379                       "  {\n");
2380       fprintf_indent (f, indent,
2381                       "    tree fndecl = get_callee_fndecl (%s);\n",
2382                       kid_opname);
2383       fprintf_indent (f, indent,
2384                       "    if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n");
2385       fprintf_indent (f, indent,
2386                       "      switch (DECL_FUNCTION_CODE (fndecl))\n");
2387       fprintf_indent (f, indent,
2388                       "        {\n");
2389       indent += 8;
2390
2391       for (unsigned j = 0; j < generic_fns.length (); ++j)
2392         {
2393           expr *e = as_a <expr *>(generic_fns[j]->op);
2394           gcc_assert (e->operation->kind == id_base::FN);
2395
2396           fprintf_indent (f, indent, "case %s:\n", e->operation->id);
2397           fprintf_indent (f, indent, "  {\n");
2398           generic_fns[j]->gen (f, indent + 4, false);
2399           fprintf_indent (f, indent, "    break;\n");
2400           fprintf_indent (f, indent, "  }\n");
2401         }
2402
2403       indent -= 8;
2404       fprintf_indent (f, indent, "          default:;\n");
2405       fprintf_indent (f, indent, "        }\n");
2406       fprintf_indent (f, indent, "    break;\n");
2407       fprintf_indent (f, indent, "  }\n");
2408     }
2409
2410   /* Close switch (TREE_CODE ()).  */
2411   if (exprs_len || fns_len || gexprs_len || gfns_len)
2412     {
2413       indent -= 4;
2414       fprintf_indent (f, indent, "    default:;\n");
2415       fprintf_indent (f, indent, "  }\n");
2416     }
2417
2418   for (unsigned i = 0; i < preds.length (); ++i)
2419     {
2420       expr *e = as_a <expr *> (preds[i]->op);
2421       predicate_id *p = as_a <predicate_id *> (e->operation);
2422       preds[i]->get_name (kid_opname);
2423       fprintf_indent (f, indent, "tree %s_pops[%d];\n", kid_opname, p->nargs);
2424       fprintf_indent (f, indent, "if (%s_%s (%s, %s_pops%s))\n",
2425                gimple ? "gimple" : "tree",
2426                p->id, kid_opname, kid_opname,
2427                gimple ? ", valueize" : "");
2428       fprintf_indent (f, indent, "  {\n");
2429       for (int j = 0; j < p->nargs; ++j)
2430         {
2431           char child_opname[20];
2432           preds[i]->gen_opname (child_opname, j);
2433           fprintf_indent (f, indent + 4, "tree %s = %s_pops[%d];\n",
2434                           child_opname, kid_opname, j);
2435         }
2436       preds[i]->gen_kids (f, indent + 4, gimple);
2437       fprintf (f, "}\n");
2438     }
2439
2440   for (unsigned i = 0; i < others.length (); ++i)
2441     others[i]->gen (f, indent, gimple);
2442 }
2443
2444 /* Generate matching code for the decision tree operand.  */
2445
2446 void
2447 dt_operand::gen (FILE *f, int indent, bool gimple)
2448 {
2449   char opname[20];
2450   get_name (opname);
2451
2452   unsigned n_braces = 0;
2453
2454   if (type == DT_OPERAND)
2455     switch (op->type)
2456       {
2457         case operand::OP_PREDICATE:
2458           n_braces = gen_predicate (f, indent, opname, gimple);
2459           break;
2460
2461         case operand::OP_EXPR:
2462           if (gimple)
2463             n_braces = gen_gimple_expr (f, indent);
2464           else
2465             n_braces = gen_generic_expr (f, indent, opname);
2466           break;
2467
2468         default:
2469           gcc_unreachable ();
2470       }
2471   else if (type == DT_TRUE)
2472     ;
2473   else if (type == DT_MATCH)
2474     n_braces = gen_match_op (f, indent, opname);
2475   else
2476     gcc_unreachable ();
2477
2478   indent += 4 * n_braces;
2479   gen_kids (f, indent, gimple);
2480
2481   for (unsigned i = 0; i < n_braces; ++i)
2482     {
2483       indent -= 4;
2484       if (indent < 0)
2485         indent = 0;
2486       fprintf_indent (f, indent, "  }\n");
2487     }
2488 }
2489
2490
2491
2492 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2493    step of a '(simplify ...)' or '(match ...)'.  This handles everything
2494    that is not part of the decision tree (simplify->match).  */
2495
2496 void
2497 dt_simplify::gen (FILE *f, int indent, bool gimple)
2498 {
2499   fprintf_indent (f, indent, "{\n");
2500   indent += 2;
2501   output_line_directive (f, s->result_location);
2502   if (s->capture_max >= 0)
2503     fprintf_indent (f, indent, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2504                     s->capture_max + 1);
2505
2506   for (int i = 0; i <= s->capture_max; ++i)
2507     if (indexes[i])
2508       {
2509         char opname[20];
2510         fprintf_indent (f, indent, "captures[%u] = %s;\n",
2511                         i, indexes[i]->get_name (opname));
2512       }
2513
2514   unsigned n_braces = 0;
2515   if (s->ifexpr_vec != vNULL)
2516     {
2517       for (unsigned i = 0; i < s->ifexpr_vec.length (); ++i)
2518         {
2519           if_or_with &w = s->ifexpr_vec[i];
2520           if (w.is_with)
2521             {
2522               fprintf_indent (f, indent, "{\n");
2523               indent += 4;
2524               output_line_directive (f, w.location);
2525               w.cexpr->gen_transform (f, indent, NULL, true, 1, "type", NULL);
2526               n_braces++;
2527             }
2528           else
2529             {
2530               output_line_directive (f, w.location);
2531               fprintf_indent (f, indent, "if (");
2532               if (i == s->ifexpr_vec.length () - 1
2533                   || s->ifexpr_vec[i+1].is_with)
2534                 w.cexpr->gen_transform (f, indent, NULL, true, 1, "type", NULL);
2535               else
2536                 {
2537                   unsigned j = i;
2538                   do
2539                     {
2540                       if (j != i)
2541                         {
2542                           fprintf (f, "\n");
2543                           output_line_directive (f, s->ifexpr_vec[j].location);
2544                           fprintf_indent (f, indent + 4, "&& ");
2545                         }
2546                       fprintf (f, "(");
2547                       s->ifexpr_vec[j].cexpr->gen_transform (f, 0, NULL,
2548                                                              true, 1, "type",
2549                                                              NULL);
2550                       fprintf (f, ")");
2551                       ++j;
2552                     }
2553                   while (j < s->ifexpr_vec.length ()
2554                          && !s->ifexpr_vec[j].is_with);
2555                   i = j - 1;
2556                 }
2557               fprintf (f, ")\n");
2558             }
2559         }
2560       fprintf_indent (f, indent + 2, "{\n");
2561       indent += 4;
2562       n_braces++;
2563     }
2564
2565   /* Analyze captures and perform early-outs on the incoming arguments
2566      that cover cases we cannot handle.  */
2567   capture_info cinfo (s);
2568   expr *e;
2569   if (s->result
2570       && !((e = dyn_cast <expr *> (s->result))
2571            && is_a <predicate_id *> (e->operation)))
2572     {
2573       if (!gimple)
2574         {
2575           for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
2576             if (cinfo.force_no_side_effects & (1 << i))
2577               fprintf_indent (f, indent,
2578                               "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
2579                               i);
2580           for (int i = 0; i <= s->capture_max; ++i)
2581             if (cinfo.info[i].cse_p)
2582               ;
2583             else if (cinfo.info[i].force_no_side_effects_p
2584                      && (cinfo.info[i].toplevel_msk
2585                          & cinfo.force_no_side_effects) == 0)
2586               fprintf_indent (f, indent,
2587                               "if (TREE_SIDE_EFFECTS (captures[%d])) "
2588                               "return NULL_TREE;\n", i);
2589             else if ((cinfo.info[i].toplevel_msk
2590                       & cinfo.force_no_side_effects) != 0)
2591               /* Mark capture as having no side-effects if we had to verify
2592                  that via forced toplevel operand checks.  */
2593               cinfo.info[i].force_no_side_effects_p = true;
2594         }
2595       if (gimple)
2596         {
2597           /* Force single-use restriction by only allowing simple
2598              results via setting seq to NULL.  */
2599           fprintf_indent (f, indent, "gimple_seq *lseq = seq;\n");
2600           bool first_p = true;
2601           for (int i = 0; i <= s->capture_max; ++i)
2602             if (cinfo.info[i].force_single_use)
2603               {
2604                 if (first_p)
2605                   {
2606                     fprintf_indent (f, indent, "if (lseq\n");
2607                     fprintf_indent (f, indent, "    && (");
2608                     first_p = false;
2609                   }
2610                 else
2611                   {
2612                     fprintf (f, "\n");
2613                     fprintf_indent (f, indent, "        || ");
2614                   }
2615                 fprintf (f, "!single_use (captures[%d])", i);
2616               }
2617           if (!first_p)
2618             {
2619               fprintf (f, "))\n");
2620               fprintf_indent (f, indent, "  lseq = NULL;\n");
2621             }
2622         }
2623     }
2624
2625   fprintf_indent (f, indent, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2626            "fprintf (dump_file, \"Applying pattern ");
2627   output_line_directive (f, s->result_location, true);
2628   fprintf (f, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2629
2630   operand *result = s->result;
2631   if (!result)
2632     {
2633       /* If there is no result then this is a predicate implementation.  */
2634       fprintf_indent (f, indent, "return true;\n");
2635     }
2636   else if (gimple)
2637     {
2638       /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2639          in outermost position).  */
2640       if (result->type == operand::OP_EXPR
2641           && *as_a <expr *> (result)->operation == NON_LVALUE_EXPR)
2642         result = as_a <expr *> (result)->ops[0];
2643       if (result->type == operand::OP_EXPR)
2644         {
2645           expr *e = as_a <expr *> (result);
2646           bool is_predicate = is_a <predicate_id *> (e->operation);
2647           if (!is_predicate)
2648             fprintf_indent (f, indent, "*res_code = %s;\n",
2649                             *e->operation == CONVERT_EXPR
2650                             ? "NOP_EXPR" : e->operation->id);
2651           for (unsigned j = 0; j < e->ops.length (); ++j)
2652             {
2653               char dest[32];
2654               snprintf (dest, 32, "res_ops[%d]", j);
2655               const char *optype
2656                 = get_operand_type (e->operation,
2657                                     "type", e->expr_type,
2658                                     j == 0 ? NULL : "TREE_TYPE (res_ops[0])");
2659               /* We need to expand GENERIC conditions we captured from
2660                  COND_EXPRs.  */
2661               bool expand_generic_cond_exprs_p
2662                 = (!is_predicate
2663                    /* But avoid doing that if the GENERIC condition is
2664                       valid - which it is in the first operand of COND_EXPRs
2665                       and VEC_COND_EXRPs.  */
2666                    && ((!(*e->operation == COND_EXPR)
2667                         && !(*e->operation == VEC_COND_EXPR))
2668                        || j != 0));
2669               e->ops[j]->gen_transform (f, indent, dest, true, 1, optype,
2670                                         &cinfo,
2671                                         indexes, expand_generic_cond_exprs_p);
2672             }
2673
2674           /* Re-fold the toplevel result.  It's basically an embedded
2675              gimple_build w/o actually building the stmt.  */
2676           if (!is_predicate)
2677             fprintf_indent (f, indent,
2678                             "gimple_resimplify%d (lseq, res_code, type, "
2679                             "res_ops, valueize);\n", e->ops.length ());
2680         }
2681       else if (result->type == operand::OP_CAPTURE
2682                || result->type == operand::OP_C_EXPR)
2683         {
2684           result->gen_transform (f, indent, "res_ops[0]", true, 1, "type",
2685                                  &cinfo, indexes, false);
2686           fprintf_indent (f, indent, "*res_code = TREE_CODE (res_ops[0]);\n");
2687           if (is_a <capture *> (result)
2688               && cinfo.info[as_a <capture *> (result)->where].cond_expr_cond_p)
2689             {
2690               /* ???  Stupid tcc_comparison GENERIC trees in COND_EXPRs.  Deal
2691                  with substituting a capture of that.  */
2692               fprintf_indent (f, indent,
2693                               "if (COMPARISON_CLASS_P (res_ops[0]))\n");
2694               fprintf_indent (f, indent,
2695                               "  {\n");
2696               fprintf_indent (f, indent,
2697                               "    tree tem = res_ops[0];\n");
2698               fprintf_indent (f, indent,
2699                               "    res_ops[0] = TREE_OPERAND (tem, 0);\n");
2700               fprintf_indent (f, indent,
2701                               "    res_ops[1] = TREE_OPERAND (tem, 1);\n");
2702               fprintf_indent (f, indent,
2703                               "  }\n");
2704             }
2705         }
2706       else
2707         gcc_unreachable ();
2708       fprintf_indent (f, indent, "return true;\n");
2709     }
2710   else /* GENERIC */
2711     {
2712       bool is_predicate = false;
2713       if (result->type == operand::OP_EXPR)
2714         {
2715           expr *e = as_a <expr *> (result);
2716           is_predicate = is_a <predicate_id *> (e->operation);
2717           /* Search for captures used multiple times in the result expression
2718              and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR.  */
2719           if (!is_predicate)
2720             for (int i = 0; i < s->capture_max + 1; ++i)
2721               {
2722                 if (!cinfo.info[i].force_no_side_effects_p
2723                     && cinfo.info[i].result_use_count > 1)
2724                   {
2725                     fprintf_indent (f, indent,
2726                                     "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
2727                                     i);
2728                     fprintf_indent (f, indent,
2729                                     "  captures[%d] = save_expr (captures[%d]);\n",
2730                                     i, i);
2731                   }
2732               }
2733           for (unsigned j = 0; j < e->ops.length (); ++j)
2734             {
2735               char dest[32];
2736               if (is_predicate)
2737                 snprintf (dest, 32, "res_ops[%d]", j);
2738               else
2739                 {
2740                   fprintf_indent (f, indent, "tree res_op%d;\n", j);
2741                   snprintf (dest, 32, "res_op%d", j);
2742                 }
2743               const char *optype
2744                 = get_operand_type (e->operation,
2745                                     "type", e->expr_type,
2746                                     j == 0
2747                                     ? NULL : "TREE_TYPE (res_op0)");
2748               e->ops[j]->gen_transform (f, indent, dest, false, 1, optype,
2749                                         &cinfo, indexes);
2750             }
2751           if (is_predicate)
2752             fprintf_indent (f, indent, "return true;\n");
2753           else
2754             {
2755               fprintf_indent (f, indent, "tree res;\n");
2756               /* Re-fold the toplevel result.  Use non_lvalue to
2757                  build NON_LVALUE_EXPRs so they get properly
2758                  ignored when in GIMPLE form.  */
2759               if (*e->operation == NON_LVALUE_EXPR)
2760                 fprintf_indent (f, indent,
2761                                 "res = non_lvalue_loc (loc, res_op0);\n");
2762               else
2763                 {
2764                   if (e->operation->kind == id_base::CODE)
2765                     fprintf_indent (f, indent,
2766                                     "res = fold_build%d_loc (loc, %s, type",
2767                                     e->ops.length (),
2768                                     *e->operation == CONVERT_EXPR
2769                                     ? "NOP_EXPR" : e->operation->id);
2770                   else
2771                     fprintf_indent (f, indent,
2772                                     "res = build_call_expr_loc "
2773                                     "(loc, builtin_decl_implicit (%s), %d",
2774                                     e->operation->id, e->ops.length());
2775                   for (unsigned j = 0; j < e->ops.length (); ++j)
2776                     fprintf (f, ", res_op%d", j);
2777                   fprintf (f, ");\n");
2778                 }
2779             }
2780         }
2781       else if (result->type == operand::OP_CAPTURE
2782                || result->type == operand::OP_C_EXPR)
2783
2784         {
2785           fprintf_indent (f, indent, "tree res;\n");
2786           s->result->gen_transform (f, indent, "res", false, 1, "type",
2787                                     &cinfo, indexes);
2788         }
2789       else
2790         gcc_unreachable ();
2791       if (!is_predicate)
2792         {
2793           /* Search for captures not used in the result expression and dependent
2794              on TREE_SIDE_EFFECTS emit omit_one_operand.  */
2795           for (int i = 0; i < s->capture_max + 1; ++i)
2796             {
2797               if (!cinfo.info[i].force_no_side_effects_p
2798                   && !cinfo.info[i].expr_p
2799                   && cinfo.info[i].result_use_count == 0)
2800                 {
2801                   fprintf_indent (f, indent,
2802                                   "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
2803                                   i);
2804                   fprintf_indent (f, indent + 2,
2805                                   "res = build2_loc (loc, COMPOUND_EXPR, type, "
2806                                   "fold_ignored_result (captures[%d]), res);\n",
2807                                   i);
2808                 }
2809             }
2810           fprintf_indent (f, indent, "return res;\n");
2811         }
2812     }
2813
2814   for (unsigned i = 0; i < n_braces; ++i)
2815     {
2816       fprintf_indent (f, indent - 2, "}\n");
2817       indent -= 4;
2818     }
2819
2820   indent -= 2;
2821   fprintf_indent (f, indent, "}\n");
2822 }
2823
2824 /* Main entry to generate code for matching GIMPLE IL off the decision
2825    tree.  */
2826
2827 void
2828 decision_tree::gen_gimple (FILE *f)
2829 {
2830   for (unsigned n = 1; n <= 3; ++n)
2831     {
2832       fprintf (f, "\nstatic bool\n"
2833                "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2834                "                 gimple_seq *seq, tree (*valueize)(tree),\n"
2835                "                 code_helper code, tree type");
2836       for (unsigned i = 0; i < n; ++i)
2837         fprintf (f, ", tree op%d", i);
2838       fprintf (f, ")\n");
2839       fprintf (f, "{\n");
2840
2841       fprintf (f, "  switch (code.get_rep())\n"
2842                   "    {\n");
2843       for (unsigned i = 0; i < root->kids.length (); i++)
2844         {
2845           dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
2846           expr *e = static_cast<expr *>(dop->op);
2847           if (e->ops.length () != n)
2848             continue;
2849
2850           if (*e->operation == CONVERT_EXPR
2851               || *e->operation == NOP_EXPR)
2852             fprintf (f, "    CASE_CONVERT:\n");
2853           else
2854             fprintf (f, "    case %s%s:\n",
2855                      is_a <fn_id *> (e->operation) ? "-" : "",
2856                      e->operation->id);
2857           fprintf (f,   "      {\n");
2858           dop->gen_kids (f, 8, true);
2859           fprintf (f,   "        break;\n");
2860           fprintf (f,   "      }\n");
2861         }
2862       fprintf (f,       "    default:;\n"
2863                         "  }\n");
2864
2865       fprintf (f, "  return false;\n");
2866       fprintf (f, "}\n");
2867     }
2868 }
2869
2870 /* Main entry to generate code for matching GENERIC IL off the decision
2871    tree.  */
2872
2873 void
2874 decision_tree::gen_generic (FILE *f)
2875 {
2876   for (unsigned n = 1; n <= 3; ++n)
2877     {
2878       fprintf (f, "\ntree\n"
2879                "generic_simplify (location_t loc, enum tree_code code, "
2880                "tree type ATTRIBUTE_UNUSED");
2881       for (unsigned i = 0; i < n; ++i)
2882         fprintf (f, ", tree op%d", i);
2883       fprintf (f, ")\n");
2884       fprintf (f, "{\n");
2885
2886       fprintf (f, "  switch (code)\n"
2887                   "    {\n");
2888       for (unsigned i = 0; i < root->kids.length (); i++)
2889         {
2890           dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
2891           expr *e = static_cast<expr *>(dop->op);
2892           if (e->ops.length () != n
2893               /* Builtin simplifications are somewhat premature on
2894                  GENERIC.  The following drops patterns with outermost
2895                  calls.  It's easy to emit overloads for function code
2896                  though if necessary.  */
2897               || e->operation->kind != id_base::CODE)
2898             continue;
2899
2900           operator_id *op_id = static_cast <operator_id *> (e->operation);
2901           if (op_id->code == NOP_EXPR || op_id->code == CONVERT_EXPR)
2902             fprintf (f, "    CASE_CONVERT:\n");
2903           else
2904             fprintf (f, "    case %s:\n", e->operation->id);
2905           fprintf (f,   "      {\n");
2906           dop->gen_kids (f, 8, false);
2907           fprintf (f,   "        break;\n"
2908                         "      }\n");
2909         }
2910       fprintf (f, "    default:;\n"
2911                   "    }\n");
2912
2913       fprintf (f, "  return NULL_TREE;\n");
2914       fprintf (f, "}\n");
2915     }
2916 }
2917
2918 /* Output code to implement the predicate P from the decision tree DT.  */
2919
2920 void
2921 write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple)
2922 {
2923   fprintf (f, "\nbool\n"
2924            "%s%s (tree t%s%s)\n"
2925            "{\n", gimple ? "gimple_" : "tree_", p->id,
2926            p->nargs > 0 ? ", tree *res_ops" : "",
2927            gimple ? ", tree (*valueize)(tree)" : "");
2928   /* Conveniently make 'type' available.  */
2929   fprintf_indent (f, 2, "tree type = TREE_TYPE (t);\n");
2930
2931   if (!gimple)
2932     fprintf_indent (f, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2933   dt.root->gen_kids (f, 2, gimple);
2934
2935   fprintf_indent (f, 2, "return false;\n"
2936            "}\n");
2937 }
2938
2939 /* Write the common header for the GIMPLE/GENERIC IL matching routines.  */
2940
2941 static void
2942 write_header (FILE *f, const char *head)
2943 {
2944   fprintf (f, "/* Generated automatically by the program `genmatch' from\n");
2945   fprintf (f, "   a IL pattern matching and simplification description.  */\n");
2946
2947   /* Include the header instead of writing it awkwardly quoted here.  */
2948   fprintf (f, "\n#include \"%s\"\n", head);
2949 }
2950
2951
2952
2953 /* AST parsing.  */
2954
2955 class parser
2956 {
2957 public:
2958   parser (cpp_reader *);
2959
2960 private:
2961   const cpp_token *next ();
2962   const cpp_token *peek ();
2963   const cpp_token *peek_ident (const char * = NULL);
2964   const cpp_token *expect (enum cpp_ttype);
2965   void eat_token (enum cpp_ttype);
2966   const char *get_string ();
2967   const char *get_ident ();
2968   void eat_ident (const char *);
2969   const char *get_number ();
2970
2971   id_base *parse_operation ();
2972   operand *parse_capture (operand *);
2973   operand *parse_expr ();
2974   c_expr *parse_c_expr (cpp_ttype);
2975   operand *parse_op ();
2976
2977   void record_operlist (source_location, user_id *);
2978
2979   void parse_pattern ();
2980   void push_simplify (vec<simplify *>&, operand *, source_location,
2981                       operand *, source_location);
2982   void parse_simplify (source_location, vec<simplify *>&, predicate_id *,
2983                        expr *);
2984   void parse_for (source_location);
2985   void parse_if (source_location);
2986   void parse_predicates (source_location);
2987   void parse_operator_list (source_location);
2988
2989   cpp_reader *r;
2990   vec<if_or_with> active_ifs;
2991   vec<vec<user_id *> > active_fors;
2992   hash_set<user_id *> *oper_lists_set;
2993   vec<user_id *> oper_lists;
2994
2995   cid_map_t *capture_ids;
2996
2997 public:
2998   vec<simplify *> simplifiers;
2999   vec<predicate_id *> user_predicates;
3000   bool parsing_match_operand;
3001 };
3002
3003 /* Lexing helpers.  */
3004
3005 /* Read the next non-whitespace token from R.  */
3006
3007 const cpp_token *
3008 parser::next ()
3009 {
3010   const cpp_token *token;
3011   do
3012     {
3013       token = cpp_get_token (r);
3014     }
3015   while (token->type == CPP_PADDING
3016          && token->type != CPP_EOF);
3017   return token;
3018 }
3019
3020 /* Peek at the next non-whitespace token from R.  */
3021
3022 const cpp_token *
3023 parser::peek ()
3024 {
3025   const cpp_token *token;
3026   unsigned i = 0;
3027   do
3028     {
3029       token = cpp_peek_token (r, i++);
3030     }
3031   while (token->type == CPP_PADDING
3032          && token->type != CPP_EOF);
3033   /* If we peek at EOF this is a fatal error as it leaves the
3034      cpp_reader in unusable state.  Assume we really wanted a
3035      token and thus this EOF is unexpected.  */
3036   if (token->type == CPP_EOF)
3037     fatal_at (token, "unexpected end of file");
3038   return token;
3039 }
3040
3041 /* Peek at the next identifier token (or return NULL if the next
3042    token is not an identifier or equal to ID if supplied).  */
3043
3044 const cpp_token *
3045 parser::peek_ident (const char *id)
3046 {
3047   const cpp_token *token = peek ();
3048   if (token->type != CPP_NAME)
3049     return 0;
3050
3051   if (id == 0)
3052     return token;
3053
3054   const char *t = (const char *) CPP_HASHNODE (token->val.node.node)->ident.str;
3055   if (strcmp (id, t) == 0)
3056     return token;
3057
3058   return 0;
3059 }
3060
3061 /* Read the next token from R and assert it is of type TK.  */
3062
3063 const cpp_token *
3064 parser::expect (enum cpp_ttype tk)
3065 {
3066   const cpp_token *token = next ();
3067   if (token->type != tk)
3068     fatal_at (token, "expected %s, got %s",
3069               cpp_type2name (tk, 0), cpp_type2name (token->type, 0));
3070
3071   return token;
3072 }
3073
3074 /* Consume the next token from R and assert it is of type TK.  */
3075
3076 void
3077 parser::eat_token (enum cpp_ttype tk)
3078 {
3079   expect (tk);
3080 }
3081
3082 /* Read the next token from R and assert it is of type CPP_STRING and
3083    return its value.  */
3084
3085 const char *
3086 parser::get_string ()
3087 {
3088   const cpp_token *token = expect (CPP_STRING);
3089   return (const char *)token->val.str.text;
3090 }
3091
3092 /* Read the next token from R and assert it is of type CPP_NAME and
3093    return its value.  */
3094
3095 const char *
3096 parser::get_ident ()
3097 {
3098   const cpp_token *token = expect (CPP_NAME);
3099   return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str;
3100 }
3101
3102 /* Eat an identifier token with value S from R.  */
3103
3104 void
3105 parser::eat_ident (const char *s)
3106 {
3107   const cpp_token *token = peek ();
3108   const char *t = get_ident ();
3109   if (strcmp (s, t) != 0)
3110     fatal_at (token, "expected '%s' got '%s'\n", s, t);
3111 }
3112
3113 /* Read the next token from R and assert it is of type CPP_NUMBER and
3114    return its value.  */
3115
3116 const char *
3117 parser::get_number ()
3118 {
3119   const cpp_token *token = expect (CPP_NUMBER);
3120   return (const char *)token->val.str.text;
3121 }
3122
3123
3124 /* Record an operator-list use for transparent for handling.  */
3125
3126 void
3127 parser::record_operlist (source_location loc, user_id *p)
3128 {
3129   if (!oper_lists_set->add (p))
3130     {
3131       if (!oper_lists.is_empty ()
3132           && oper_lists[0]->substitutes.length () != p->substitutes.length ())
3133         fatal_at (loc, "User-defined operator list does not have the "
3134                   "same number of entries as others used in the pattern");
3135       oper_lists.safe_push (p);
3136     }
3137 }
3138
3139 /* Parse the operator ID, special-casing convert?, convert1? and
3140    convert2?  */
3141
3142 id_base *
3143 parser::parse_operation ()
3144 {
3145   const cpp_token *id_tok = peek ();
3146   const char *id = get_ident ();
3147   const cpp_token *token = peek ();
3148   if (strcmp (id, "convert0") == 0)
3149     fatal_at (id_tok, "use 'convert?' here");
3150   else if (strcmp (id, "view_convert0") == 0)
3151     fatal_at (id_tok, "use 'view_convert?' here");
3152   if (token->type == CPP_QUERY
3153       && !(token->flags & PREV_WHITE))
3154     {
3155       if (strcmp (id, "convert") == 0)
3156         id = "convert0";
3157       else if (strcmp (id, "convert1") == 0)
3158         ;
3159       else if (strcmp (id, "convert2") == 0)
3160         ;
3161       else if (strcmp (id, "view_convert") == 0)
3162         id = "view_convert0";
3163       else if (strcmp (id, "view_convert1") == 0)
3164         ;
3165       else if (strcmp (id, "view_convert2") == 0)
3166         ;
3167       else
3168         fatal_at (id_tok, "non-convert operator conditionalized");
3169
3170       if (!parsing_match_operand)
3171         fatal_at (id_tok, "conditional convert can only be used in "
3172                   "match expression");
3173       eat_token (CPP_QUERY);
3174     }
3175   else if (strcmp (id, "convert1") == 0
3176            || strcmp (id, "convert2") == 0
3177            || strcmp (id, "view_convert1") == 0
3178            || strcmp (id, "view_convert2") == 0)
3179     fatal_at (id_tok, "expected '?' after conditional operator");
3180   id_base *op = get_operator (id);
3181   if (!op)
3182     fatal_at (id_tok, "unknown operator %s", id);
3183
3184   user_id *p = dyn_cast<user_id *> (op);
3185   if (p && p->is_oper_list)
3186     {
3187       if (active_fors.length() == 0)
3188         record_operlist (id_tok->src_loc, p);
3189       else
3190         fatal_at (id_tok, "operator-list %s cannot be exapnded inside 'for'", id);
3191     }
3192   return op;
3193 }
3194
3195 /* Parse a capture.
3196      capture = '@'<number>  */
3197
3198 struct operand *
3199 parser::parse_capture (operand *op)
3200 {
3201   eat_token (CPP_ATSIGN);
3202   const cpp_token *token = peek ();
3203   const char *id = NULL;
3204   if (token->type == CPP_NUMBER)
3205     id = get_number ();
3206   else if (token->type == CPP_NAME)
3207     id = get_ident ();
3208   else
3209     fatal_at (token, "expected number or identifier");
3210   unsigned next_id = capture_ids->elements ();
3211   bool existed;
3212   unsigned &num = capture_ids->get_or_insert (id, &existed);
3213   if (!existed)
3214     num = next_id;
3215   return new capture (num, op);
3216 }
3217
3218 /* Parse an expression
3219      expr = '(' <operation>[capture][flag][type] <operand>... ')'  */
3220
3221 struct operand *
3222 parser::parse_expr ()
3223 {
3224   expr *e = new expr (parse_operation ());
3225   const cpp_token *token = peek ();
3226   operand *op;
3227   bool is_commutative = false;
3228   bool force_capture = false;
3229   const char *expr_type = NULL;
3230
3231   if (token->type == CPP_COLON
3232       && !(token->flags & PREV_WHITE))
3233     {
3234       eat_token (CPP_COLON);
3235       token = peek ();
3236       if (token->type == CPP_NAME
3237           && !(token->flags & PREV_WHITE))
3238         {
3239           const char *s = get_ident ();
3240           if (!parsing_match_operand)
3241             expr_type = s;
3242           else
3243             {
3244               const char *sp = s;
3245               while (*sp)
3246                 {
3247                   if (*sp == 'c')
3248                     is_commutative = true;
3249                   else if (*sp == 's')
3250                     {
3251                       e->force_single_use = true;
3252                       force_capture = true;
3253                     }
3254                   else
3255                     fatal_at (token, "flag %c not recognized", *sp);
3256                   sp++;
3257                 }
3258             }
3259           token = peek ();
3260         }
3261       else
3262         fatal_at (token, "expected flag or type specifying identifier");
3263     }
3264
3265   if (token->type == CPP_ATSIGN
3266       && !(token->flags & PREV_WHITE))
3267     op = parse_capture (e);
3268   else if (force_capture)
3269     {
3270       unsigned num = capture_ids->elements ();
3271       char id[8];
3272       bool existed;
3273       sprintf (id, "__%u", num);
3274       capture_ids->get_or_insert (xstrdup (id), &existed);
3275       if (existed)
3276         fatal_at (token, "reserved capture id '%s' already used", id);
3277       op = new capture (num, e);
3278     }
3279   else
3280     op = e;
3281   do
3282     {
3283       const cpp_token *token = peek ();
3284       if (token->type == CPP_CLOSE_PAREN)
3285         {
3286           if (e->operation->nargs != -1
3287               && e->operation->nargs != (int) e->ops.length ())
3288             fatal_at (token, "'%s' expects %u operands, not %u",
3289                       e->operation->id, e->operation->nargs, e->ops.length ());
3290           if (is_commutative)
3291             {
3292               if (e->ops.length () == 2)
3293                 e->is_commutative = true;
3294               else
3295                 fatal_at (token, "only binary operators or function with "
3296                           "two arguments can be marked commutative");
3297             }
3298           e->expr_type = expr_type;
3299           return op;
3300         }
3301       e->append_op (parse_op ());
3302     }
3303   while (1);
3304 }
3305
3306 /* Lex native C code delimited by START recording the preprocessing tokens
3307    for later processing.
3308      c_expr = ('{'|'(') <pp token>... ('}'|')')  */
3309
3310 c_expr *
3311 parser::parse_c_expr (cpp_ttype start)
3312 {
3313   const cpp_token *token;
3314   cpp_ttype end;
3315   unsigned opencnt;
3316   vec<cpp_token> code = vNULL;
3317   unsigned nr_stmts = 0;
3318   eat_token (start);
3319   if (start == CPP_OPEN_PAREN)
3320     end = CPP_CLOSE_PAREN;
3321   else if (start == CPP_OPEN_BRACE)
3322     end = CPP_CLOSE_BRACE;
3323   else
3324     gcc_unreachable ();
3325   opencnt = 1;
3326   do
3327     {
3328       token = next ();
3329
3330       /* Count brace pairs to find the end of the expr to match.  */
3331       if (token->type == start)
3332         opencnt++;
3333       else if (token->type == end
3334                && --opencnt == 0)
3335         break;
3336
3337       /* This is a lame way of counting the number of statements.  */
3338       if (token->type == CPP_SEMICOLON)
3339         nr_stmts++;
3340
3341       /* If this is possibly a user-defined identifier mark it used.  */
3342       if (token->type == CPP_NAME)
3343         {
3344           id_base *idb = get_operator ((const char *)CPP_HASHNODE
3345                                       (token->val.node.node)->ident.str);
3346           user_id *p;
3347           if (idb && (p = dyn_cast<user_id *> (idb)) && p->is_oper_list)
3348             record_operlist (token->src_loc, p);
3349         }
3350
3351       /* Record the token.  */
3352       code.safe_push (*token);
3353     }
3354   while (1);
3355   return new c_expr (r, code, nr_stmts, vNULL, capture_ids);
3356 }
3357
3358 /* Parse an operand which is either an expression, a predicate or
3359    a standalone capture.
3360      op = predicate | expr | c_expr | capture  */
3361
3362 struct operand *
3363 parser::parse_op ()
3364 {
3365   const cpp_token *token = peek ();
3366   struct operand *op = NULL;
3367   if (token->type == CPP_OPEN_PAREN)
3368     {
3369       eat_token (CPP_OPEN_PAREN);
3370       op = parse_expr ();
3371       eat_token (CPP_CLOSE_PAREN);
3372     }
3373   else if (token->type == CPP_OPEN_BRACE)
3374     {
3375       op = parse_c_expr (CPP_OPEN_BRACE);
3376     }
3377   else
3378     {
3379       /* Remaining ops are either empty or predicates  */
3380       if (token->type == CPP_NAME)
3381         {
3382           const char *id = get_ident ();
3383           id_base *opr = get_operator (id);
3384           if (!opr)
3385             fatal_at (token, "expected predicate name");
3386           if (operator_id *code = dyn_cast <operator_id *> (opr))
3387             {
3388               if (code->nargs != 0)
3389                 fatal_at (token, "using an operator with operands as predicate");
3390               /* Parse the zero-operand operator "predicates" as
3391                  expression.  */
3392               op = new expr (opr);
3393             }
3394           else if (user_id *code = dyn_cast <user_id *> (opr))
3395             {
3396               if (code->nargs != 0)
3397                 fatal_at (token, "using an operator with operands as predicate");
3398               /* Parse the zero-operand operator "predicates" as
3399                  expression.  */
3400               op = new expr (opr);
3401             }
3402           else if (predicate_id *p = dyn_cast <predicate_id *> (opr))
3403             op = new predicate (p);
3404           else
3405             fatal_at (token, "using an unsupported operator as predicate");
3406           if (!parsing_match_operand)
3407             fatal_at (token, "predicates are only allowed in match expression");
3408           token = peek ();
3409           if (token->flags & PREV_WHITE)
3410             return op;
3411         }
3412       else if (token->type != CPP_COLON
3413                && token->type != CPP_ATSIGN)
3414         fatal_at (token, "expected expression or predicate");
3415       /* optionally followed by a capture and a predicate.  */
3416       if (token->type == CPP_COLON)
3417         fatal_at (token, "not implemented: predicate on leaf operand");
3418       if (token->type == CPP_ATSIGN)
3419         op = parse_capture (op);
3420     }
3421
3422   return op;
3423 }
3424
3425 /* Create a new simplify from the current parsing state and MATCH,
3426    MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS.  */
3427
3428 void
3429 parser::push_simplify (vec<simplify *>& simplifiers,
3430                        operand *match, source_location match_loc,
3431                        operand *result, source_location result_loc)
3432 {
3433   /* Build and push a temporary for for operator list uses in expressions.  */
3434   if (!oper_lists.is_empty ())
3435     active_fors.safe_push (oper_lists);
3436
3437   simplifiers.safe_push
3438     (new simplify (match, match_loc, result, result_loc,
3439                    active_ifs.copy (), active_fors.copy (), capture_ids));
3440
3441   if (!oper_lists.is_empty ())
3442     active_fors.pop ();
3443 }
3444
3445 /* Parse
3446      simplify = 'simplify' <expr> <result-op>
3447    or
3448      match = 'match' <ident> <expr> [<result-op>]
3449    with
3450      <result-op> = <op> | <if> | <with>
3451      <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3452      <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3453    and fill SIMPLIFIERS with the results.  */
3454
3455 void
3456 parser::parse_simplify (source_location match_location,
3457                         vec<simplify *>& simplifiers, predicate_id *matcher,
3458                         expr *result)
3459 {
3460   /* Reset the capture map.  */
3461   if (!capture_ids)
3462     capture_ids = new cid_map_t;
3463   /* Reset oper_lists and set.  */
3464   hash_set <user_id *> olist;
3465   oper_lists_set = &olist;
3466   oper_lists = vNULL;
3467
3468   const cpp_token *loc = peek ();
3469   parsing_match_operand = true;
3470   struct operand *match = parse_op ();
3471   parsing_match_operand = false;
3472   if (match->type == operand::OP_CAPTURE && !matcher)
3473     fatal_at (loc, "outermost expression cannot be captured");
3474   if (match->type == operand::OP_EXPR
3475       && is_a <predicate_id *> (as_a <expr *> (match)->operation))
3476     fatal_at (loc, "outermost expression cannot be a predicate");
3477
3478   const cpp_token *token = peek ();
3479
3480   /* If this if is immediately closed then it is part of a predicate
3481      definition.  Push it.  */
3482   if (token->type == CPP_CLOSE_PAREN)
3483     {
3484       if (!matcher)
3485         fatal_at (token, "expected transform expression");
3486       push_simplify (simplifiers, match, match_location,
3487                      result, token->src_loc);
3488       return;
3489     }
3490
3491   unsigned active_ifs_len = active_ifs.length ();
3492   while (1)
3493     {
3494       if (token->type == CPP_OPEN_PAREN)
3495         {
3496           source_location paren_loc = token->src_loc;
3497           eat_token (CPP_OPEN_PAREN);
3498           if (peek_ident ("if"))
3499             {
3500               eat_ident ("if");
3501               active_ifs.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN),
3502                                                 token->src_loc, false));
3503               /* If this if is immediately closed then it contains a
3504                  manual matcher or is part of a predicate definition.
3505                  Push it.  */
3506               if (peek ()->type == CPP_CLOSE_PAREN)
3507                 {
3508                   if (!matcher)
3509                     fatal_at (token, "manual transform not implemented");
3510                   push_simplify (simplifiers, match, match_location,
3511                                  result, paren_loc);
3512                 }
3513             }
3514           else if (peek_ident ("with"))
3515             {
3516               eat_ident ("with");
3517               /* Parse (with c-expr expr) as (if-with (true) expr).  */
3518               c_expr *e = parse_c_expr (CPP_OPEN_BRACE);
3519               e->nr_stmts = 0;
3520               active_ifs.safe_push (if_or_with (e, token->src_loc, true));
3521             }
3522           else
3523             {
3524               operand *op = result;
3525               if (!matcher)
3526                 op = parse_expr ();
3527               push_simplify (simplifiers, match, match_location,
3528                              op, token->src_loc);
3529               eat_token (CPP_CLOSE_PAREN);
3530               /* A "default" result closes the enclosing scope.  */
3531               if (active_ifs.length () > active_ifs_len)
3532                 {
3533                   eat_token (CPP_CLOSE_PAREN);
3534                   active_ifs.pop ();
3535                 }
3536               else
3537                 return;
3538             }
3539         }
3540       else if (token->type == CPP_CLOSE_PAREN)
3541         {
3542           /* Close a scope if requested.  */
3543           if (active_ifs.length () > active_ifs_len)
3544             {
3545               eat_token (CPP_CLOSE_PAREN);
3546               active_ifs.pop ();
3547               token = peek ();
3548             }
3549           else
3550             return;
3551         }
3552       else
3553         {
3554           if (matcher)
3555             fatal_at (token, "expected match operand expression");
3556           push_simplify (simplifiers, match, match_location,
3557                          matcher ? result : parse_op (), token->src_loc);
3558           /* A "default" result closes the enclosing scope.  */
3559           if (active_ifs.length () > active_ifs_len)
3560             {
3561               eat_token (CPP_CLOSE_PAREN);
3562               active_ifs.pop ();
3563             }
3564           else
3565             return;
3566         }
3567       token = peek ();
3568     }
3569 }
3570
3571 /* Parsing of the outer control structures.  */
3572
3573 /* Parse a for expression
3574      for = '(' 'for' <subst>... <pattern> ')'
3575      subst = <ident> '(' <ident>... ')'  */
3576
3577 void
3578 parser::parse_for (source_location)
3579 {
3580   auto_vec<const cpp_token *> user_id_tokens;
3581   vec<user_id *> user_ids = vNULL;
3582   const cpp_token *token;
3583   unsigned min_n_opers = 0, max_n_opers = 0;
3584
3585   while (1)
3586     {
3587       token = peek ();
3588       if (token->type != CPP_NAME)
3589         break;
3590
3591       /* Insert the user defined operators into the operator hash.  */
3592       const char *id = get_ident ();
3593       if (get_operator (id) != NULL)
3594         fatal_at (token, "operator already defined");
3595       user_id *op = new user_id (id);
3596       id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
3597       *slot = op;
3598       user_ids.safe_push (op);
3599       user_id_tokens.safe_push (token);
3600
3601       eat_token (CPP_OPEN_PAREN);
3602
3603       int arity = -1;
3604       while ((token = peek_ident ()) != 0)
3605         {
3606           const char *oper = get_ident ();
3607           id_base *idb = get_operator (oper);
3608           if (idb == NULL)
3609             fatal_at (token, "no such operator '%s'", oper);
3610           if (*idb == CONVERT0 || *idb == CONVERT1 || *idb == CONVERT2
3611               || *idb == VIEW_CONVERT0 || *idb == VIEW_CONVERT1
3612               || *idb == VIEW_CONVERT2)
3613             fatal_at (token, "conditional operators cannot be used inside for");
3614
3615           if (arity == -1)
3616             arity = idb->nargs;
3617           else if (idb->nargs == -1)
3618             ;
3619           else if (idb->nargs != arity)
3620             fatal_at (token, "operator '%s' with arity %d does not match "
3621                       "others with arity %d", oper, idb->nargs, arity);
3622
3623           user_id *p = dyn_cast<user_id *> (idb);
3624           if (p)
3625             {
3626               if (p->is_oper_list)
3627                 op->substitutes.safe_splice (p->substitutes);
3628               else
3629                 fatal_at (token, "iterator cannot be used as operator-list");
3630             }
3631           else
3632             op->substitutes.safe_push (idb);
3633         }
3634       op->nargs = arity;
3635       token = expect (CPP_CLOSE_PAREN);
3636
3637       unsigned nsubstitutes = op->substitutes.length ();
3638       if (nsubstitutes == 0)
3639         fatal_at (token, "A user-defined operator must have at least "
3640                   "one substitution");
3641       if (max_n_opers == 0)
3642         {
3643           min_n_opers = nsubstitutes;
3644           max_n_opers = nsubstitutes;
3645         }
3646       else
3647         {
3648           if (nsubstitutes % min_n_opers != 0
3649               && min_n_opers % nsubstitutes != 0)
3650             fatal_at (token, "All user-defined identifiers must have a "
3651                       "multiple number of operator substitutions of the "
3652                       "smallest number of substitutions");
3653           if (nsubstitutes < min_n_opers)
3654             min_n_opers = nsubstitutes;
3655           else if (nsubstitutes > max_n_opers)
3656             max_n_opers = nsubstitutes;
3657         }
3658     }
3659
3660   unsigned n_ids = user_ids.length ();
3661   if (n_ids == 0)
3662     fatal_at (token, "for requires at least one user-defined identifier");
3663
3664   token = peek ();
3665   if (token->type == CPP_CLOSE_PAREN)
3666     fatal_at (token, "no pattern defined in for");
3667
3668   active_fors.safe_push (user_ids);
3669   while (1)
3670     {
3671       token = peek ();
3672       if (token->type == CPP_CLOSE_PAREN)
3673         break;
3674       parse_pattern ();
3675     }
3676   active_fors.pop ();
3677
3678   /* Remove user-defined operators from the hash again.  */
3679   for (unsigned i = 0; i < user_ids.length (); ++i)
3680     {
3681       if (!user_ids[i]->used)
3682         warning_at (user_id_tokens[i],
3683                     "operator %s defined but not used", user_ids[i]->id);
3684       operators->remove_elt (user_ids[i]);
3685     }
3686 }
3687
3688 /* Parse an identifier associated with a list of operators.
3689      oprs = '(' 'define_operator_list' <ident> <ident>... ')'  */
3690
3691 void
3692 parser::parse_operator_list (source_location)
3693 {
3694   const cpp_token *token = peek ();
3695   const char *id = get_ident ();
3696
3697   if (get_operator (id) != 0)
3698     fatal_at (token, "operator %s already defined", id);
3699
3700   user_id *op = new user_id (id, true);
3701   int arity = -1;
3702
3703   while ((token = peek_ident ()) != 0)
3704     {
3705       token = peek ();
3706       const char *oper = get_ident ();
3707       id_base *idb = get_operator (oper);
3708
3709       if (idb == 0)
3710         fatal_at (token, "no such operator '%s'", oper);
3711
3712       if (arity == -1)
3713         arity = idb->nargs;
3714       else if (idb->nargs == -1)
3715         ;
3716       else if (arity != idb->nargs)
3717         fatal_at (token, "operator '%s' with arity %d does not match "
3718                          "others with arity %d", oper, idb->nargs, arity);
3719
3720       /* We allow composition of multiple operator lists.  */
3721       if (user_id *p = dyn_cast<user_id *> (idb))
3722         op->substitutes.safe_splice (p->substitutes);
3723       else
3724         op->substitutes.safe_push (idb);
3725     }
3726
3727   // Check that there is no junk after id-list
3728   token = peek();
3729   if (token->type != CPP_CLOSE_PAREN)
3730     fatal_at (token, "expected identifier got %s", cpp_type2name (token->type, 0));
3731
3732   if (op->substitutes.length () == 0)
3733     fatal_at (token, "operator-list cannot be empty");
3734
3735   op->nargs = arity;
3736   id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
3737   *slot = op;
3738 }
3739
3740 /* Parse an outer if expression.
3741      if = '(' 'if' '(' <c-expr> ')' <pattern> ')'  */
3742
3743 void
3744 parser::parse_if (source_location loc)
3745 {
3746   operand *ifexpr = parse_c_expr (CPP_OPEN_PAREN);
3747
3748   const cpp_token *token = peek ();
3749   if (token->type == CPP_CLOSE_PAREN)
3750     fatal_at (token, "no pattern defined in if");
3751
3752   active_ifs.safe_push (if_or_with (ifexpr, loc, false));
3753   while (1)
3754     {
3755       const cpp_token *token = peek ();
3756       if (token->type == CPP_CLOSE_PAREN)
3757         break;
3758
3759       parse_pattern ();
3760     }
3761   active_ifs.pop ();
3762 }
3763
3764 /* Parse a list of predefined predicate identifiers.
3765      preds = '(' 'define_predicates' <ident>... ')'  */
3766
3767 void
3768 parser::parse_predicates (source_location)
3769 {
3770   do
3771     {
3772       const cpp_token *token = peek ();
3773       if (token->type != CPP_NAME)
3774         break;
3775
3776       add_predicate (get_ident ());
3777     }
3778   while (1);
3779 }
3780
3781 /* Parse outer control structures.
3782      pattern = <preds>|<for>|<if>|<simplify>|<match>  */
3783
3784 void
3785 parser::parse_pattern ()
3786 {
3787   /* All clauses start with '('.  */
3788   eat_token (CPP_OPEN_PAREN);
3789   const cpp_token *token = peek ();
3790   const char *id = get_ident ();
3791   if (strcmp (id, "simplify") == 0)
3792     {
3793       parse_simplify (token->src_loc, simplifiers, NULL, NULL);
3794       capture_ids = NULL;
3795     }
3796   else if (strcmp (id, "match") == 0)
3797     {
3798       bool with_args = false;
3799       if (peek ()->type == CPP_OPEN_PAREN)
3800         {
3801           eat_token (CPP_OPEN_PAREN);
3802           with_args = true;
3803         }
3804       const char *name = get_ident ();
3805       id_base *id = get_operator (name);
3806       predicate_id *p;
3807       if (!id)
3808         {
3809           p = add_predicate (name);
3810           user_predicates.safe_push (p);
3811         }
3812       else if ((p = dyn_cast <predicate_id *> (id)))
3813         ;
3814       else
3815         fatal_at (token, "cannot add a match to a non-predicate ID");
3816       /* Parse (match <id> <arg>... (match-expr)) here.  */
3817       expr *e = NULL;
3818       if (with_args)
3819         {
3820           capture_ids = new cid_map_t;
3821           e = new expr (p);
3822           while (peek ()->type == CPP_ATSIGN)
3823             e->append_op (parse_capture (NULL));
3824           eat_token (CPP_CLOSE_PAREN);
3825         }
3826       if (p->nargs != -1
3827           && ((e && e->ops.length () != (unsigned)p->nargs)
3828               || (!e && p->nargs != 0)))
3829         fatal_at (token, "non-matching number of match operands");
3830       p->nargs = e ? e->ops.length () : 0;
3831       parse_simplify (token->src_loc, p->matchers, p, e);
3832       capture_ids = NULL;
3833     }
3834   else if (strcmp (id, "for") == 0)
3835     parse_for (token->src_loc);
3836   else if (strcmp (id, "if") == 0)
3837     parse_if (token->src_loc);
3838   else if (strcmp (id, "define_predicates") == 0)
3839     {
3840       if (active_ifs.length () > 0
3841           || active_fors.length () > 0)
3842         fatal_at (token, "define_predicates inside if or for is not supported");
3843       parse_predicates (token->src_loc);
3844     }
3845   else if (strcmp (id, "define_operator_list") == 0)
3846     {
3847       if (active_ifs.length () > 0
3848           || active_fors.length () > 0)
3849         fatal_at (token, "operator-list inside if or for is not supported");
3850       parse_operator_list (token->src_loc);
3851     }
3852   else
3853     fatal_at (token, "expected %s'simplify', 'match', 'for' or 'if'",
3854               active_ifs.length () == 0 && active_fors.length () == 0
3855               ? "'define_predicates', " : "");
3856
3857   eat_token (CPP_CLOSE_PAREN);
3858 }
3859
3860 /* Main entry of the parser.  Repeatedly parse outer control structures.  */
3861
3862 parser::parser (cpp_reader *r_)
3863 {
3864   r = r_;
3865   active_ifs = vNULL;
3866   active_fors = vNULL;
3867   simplifiers = vNULL;
3868   oper_lists_set = NULL;
3869   oper_lists = vNULL;
3870   capture_ids = NULL;
3871   user_predicates = vNULL;
3872   parsing_match_operand = false;
3873
3874   const cpp_token *token = next ();
3875   while (token->type != CPP_EOF)
3876     {
3877       _cpp_backup_tokens (r, 1);
3878       parse_pattern ();
3879       token = next ();
3880     }
3881 }
3882
3883
3884 /* Helper for the linemap code.  */
3885
3886 static size_t
3887 round_alloc_size (size_t s)
3888 {
3889   return s;
3890 }
3891
3892
3893 /* The genmatch generator progam.  It reads from a pattern description
3894    and outputs GIMPLE or GENERIC IL matching and simplification routines.  */
3895
3896 int
3897 main (int argc, char **argv)
3898 {
3899   cpp_reader *r;
3900
3901   progname = "genmatch";
3902
3903   if (argc < 2)
3904     return 1;
3905
3906   bool gimple = true;
3907   bool verbose = false;
3908   char *input = argv[argc-1];
3909   for (int i = 1; i < argc - 1; ++i)
3910     {
3911       if (strcmp (argv[i], "--gimple") == 0)
3912         gimple = true;
3913       else if (strcmp (argv[i], "--generic") == 0)
3914         gimple = false;
3915       else if (strcmp (argv[i], "-v") == 0)
3916         verbose = true;
3917       else
3918         {
3919           fprintf (stderr, "Usage: genmatch "
3920                    "[--gimple] [--generic] [-v] input\n");
3921           return 1;
3922         }
3923     }
3924
3925   line_table = XCNEW (struct line_maps);
3926   linemap_init (line_table, 0);
3927   line_table->reallocator = xrealloc;
3928   line_table->round_alloc_size = round_alloc_size;
3929
3930   r = cpp_create_reader (CLK_GNUC99, NULL, line_table);
3931   cpp_callbacks *cb = cpp_get_callbacks (r);
3932   cb->error = error_cb;
3933
3934   if (!cpp_read_main_file (r, input))
3935     return 1;
3936   cpp_define (r, gimple ? "GIMPLE=1": "GENERIC=1");
3937   cpp_define (r, gimple ? "GENERIC=0": "GIMPLE=0");
3938
3939   /* Pre-seed operators.  */
3940   operators = new hash_table<id_base> (1024);
3941 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3942   add_operator (SYM, # SYM, # TYPE, NARGS);
3943 #define END_OF_BASE_TREE_CODES
3944 #include "tree.def"
3945 add_operator (CONVERT0, "CONVERT0", "tcc_unary", 1);
3946 add_operator (CONVERT1, "CONVERT1", "tcc_unary", 1);
3947 add_operator (CONVERT2, "CONVERT2", "tcc_unary", 1);
3948 add_operator (VIEW_CONVERT0, "VIEW_CONVERT0", "tcc_unary", 1);
3949 add_operator (VIEW_CONVERT1, "VIEW_CONVERT1", "tcc_unary", 1);
3950 add_operator (VIEW_CONVERT2, "VIEW_CONVERT2", "tcc_unary", 1);
3951 #undef END_OF_BASE_TREE_CODES
3952 #undef DEFTREECODE
3953
3954   /* Pre-seed builtin functions.
3955      ???  Cannot use N (name) as that is targetm.emultls.get_address
3956      for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3957 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3958   add_builtin (ENUM, # ENUM);
3959 #include "builtins.def"
3960 #undef DEF_BUILTIN
3961
3962   /* Parse ahead!  */
3963   parser p (r);
3964
3965   if (gimple)
3966     write_header (stdout, "gimple-match-head.c");
3967   else
3968     write_header (stdout, "generic-match-head.c");
3969
3970   /* Go over all predicates defined with patterns and perform
3971      lowering and code generation.  */
3972   for (unsigned i = 0; i < p.user_predicates.length (); ++i)
3973     {
3974       predicate_id *pred = p.user_predicates[i];
3975       lower (pred->matchers, gimple);
3976
3977       if (verbose)
3978         for (unsigned i = 0; i < pred->matchers.length (); ++i)
3979           print_matches (pred->matchers[i]);
3980
3981       decision_tree dt;
3982       for (unsigned i = 0; i < pred->matchers.length (); ++i)
3983         dt.insert (pred->matchers[i], i);
3984
3985       if (verbose)
3986         dt.print (stderr);
3987
3988       write_predicate (stdout, pred, dt, gimple);
3989     }
3990
3991   /* Lower the main simplifiers and generate code for them.  */
3992   lower (p.simplifiers, gimple);
3993
3994   if (verbose)
3995     for (unsigned i = 0; i < p.simplifiers.length (); ++i)
3996       print_matches (p.simplifiers[i]);
3997
3998   decision_tree dt;
3999   for (unsigned i = 0; i < p.simplifiers.length (); ++i)
4000     dt.insert (p.simplifiers[i], i);
4001
4002   if (verbose)
4003     dt.print (stderr);
4004
4005   if (gimple)
4006     dt.gen_gimple (stdout);
4007   else
4008     dt.gen_generic (stdout);
4009
4010   /* Finalize.  */
4011   cpp_finish (r, NULL);
4012   cpp_destroy (r);
4013
4014   delete operators;
4015
4016   return 0;
4017 }