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