This is the first patch in a series of N to merge from the match-and-simplify branch.
The goal of the work is to get rid of the dependence on GENERIC folding in all our GIMPLE optimizers. This means that GIMPLE no longer needs to build GENERIC to get it optimized and then re-gimplify it via force_gimple_operand. To arrive here we need to perform all simplifications the GENERIC folders do at the GIMPLE level as well (and incrementally when building larger expressions). Instead of duplicating everything for both GENERIC and GIMPLE the approach taken is that of a meta-description of IL patterns and transforms using a domain specific language. You can refer to the talk I gave at the GNU Cauldron 2014, slides available at https://gcc.gnu.org/wiki/cauldron2014. This first patch adds the infrastructure, the new generator program genmatch, building it and using it to build the autogenerated gimple-match.c and generic-match.c files. It also includes documentation for the internals manual which explains the domain specific language by example. Boostrapped on x86_64-unknown-linux-gnu. Ok for trunk? Thanks, Richard. 2014-10-15 Richard Biener <rguent...@suse.de> * Makefile.in (OBJS): Add gimple-match.o and generic-match.o. (MOSTLYCLEANFILES): Add gimple-match.c and generic-match.c. (gimple-match.c): Generate by triggering s-match. (generic-match.c): Likewise. (s-match): Rule to build gimple-match.c and generic-match.c by running the genmatch generator program. (build/hash-table.o): Dependencies to build hash-table.c for the host. (build/genmatch.o): Dependencies to build genmatch. (genprog): Add match. (build/genmatch): Likewise. (TEXI_GCCINT_FILES): Add match-and-simplify.texi. * generic-match-head.c: New file. * gimple-match-head.c: Likewise. * gimple-match.h: Likewise. * genmatch.c: Likewise. * match.pd: Likewise. * builtins.h (fold_builtin_n): Export. * builtins.c (fold_builtin_n): Likewise. * doc/match-and-simplify.texi: New file. * doc/gccint.texi: Add menu item Match and Simplify and include match-and-simplify.texi. Index: gcc/Makefile.in =================================================================== *** gcc/Makefile.in.orig 2014-10-15 12:24:05.129256239 +0200 --- gcc/Makefile.in 2014-10-15 12:45:32.180167627 +0200 *************** OBJS = \ *** 1226,1231 **** --- 1226,1233 ---- gimple-iterator.o \ gimple-fold.o \ gimple-low.o \ + gimple-match.o \ + generic-match.o \ gimple-pretty-print.o \ gimple-ssa-isolate-paths.o \ gimple-ssa-strength-reduction.o \ *************** MOSTLYCLEANFILES = insn-flags.h insn-con *** 1501,1507 **** insn-output.c insn-recog.c insn-emit.c insn-extract.c insn-peep.c \ insn-attr.h insn-attr-common.h insn-attrtab.c insn-dfatab.c \ insn-latencytab.c insn-opinit.c insn-opinit.h insn-preds.c insn-constants.h \ ! tm-preds.h tm-constrs.h checksum-options \ tree-check.h min-insn-modes.c insn-modes.c insn-modes.h \ genrtl.h gt-*.h gtype-*.h gtype-desc.c gtyp-input.list \ xgcc$(exeext) cpp$(exeext) \ --- 1503,1509 ---- insn-output.c insn-recog.c insn-emit.c insn-extract.c insn-peep.c \ insn-attr.h insn-attr-common.h insn-attrtab.c insn-dfatab.c \ insn-latencytab.c insn-opinit.c insn-opinit.h insn-preds.c insn-constants.h \ ! tm-preds.h tm-constrs.h checksum-options gimple-match.c generic-match.c \ tree-check.h min-insn-modes.c insn-modes.c insn-modes.h \ genrtl.h gt-*.h gtype-*.h gtype-desc.c gtyp-input.list \ xgcc$(exeext) cpp$(exeext) \ *************** $(common_out_object_file): $(common_out_ *** 2018,2024 **** .PRECIOUS: insn-config.h insn-flags.h insn-codes.h insn-constants.h \ insn-emit.c insn-recog.c insn-extract.c insn-output.c insn-peep.c \ insn-attr.h insn-attr-common.h insn-attrtab.c insn-dfatab.c \ ! insn-latencytab.c insn-preds.c # Dependencies for the md file. The first time through, we just assume # the md file itself and the generated dependency file (in order to get --- 2020,2026 ---- .PRECIOUS: insn-config.h insn-flags.h insn-codes.h insn-constants.h \ insn-emit.c insn-recog.c insn-extract.c insn-output.c insn-peep.c \ insn-attr.h insn-attr-common.h insn-attrtab.c insn-dfatab.c \ ! insn-latencytab.c insn-preds.c gimple-match.c generic-match.c # Dependencies for the md file. The first time through, we just assume # the md file itself and the generated dependency file (in order to get *************** s-tm-texi: build/genhooks$(build_exeext) *** 2227,2232 **** --- 2229,2248 ---- false; \ fi + gimple-match.c: s-match gimple-match-head.c ; @true + generic-match.c: s-match generic-match-head.c ; @true + + s-match: build/genmatch$(build_exeext) $(srcdir)/match.pd + $(RUN_GEN) build/genmatch$(build_exeext) -gimple $(srcdir)/match.pd \ + > tmp-gimple-match.c + $(RUN_GEN) build/genmatch$(build_exeext) -generic $(srcdir)/match.pd \ + > tmp-generic-match.c + $(SHELL) $(srcdir)/../move-if-change tmp-gimple-match.c \ + gimple-match.c + $(SHELL) $(srcdir)/../move-if-change tmp-generic-match.c \ + generic-match.c + $(STAMP) s-match + GTFILES = $(CPP_ID_DATA_H) $(srcdir)/input.h $(srcdir)/coretypes.h \ $(host_xm_file_list) \ $(tm_file_list) $(HASHTAB_H) $(SPLAY_TREE_H) $(srcdir)/bitmap.h \ *************** build/rtl.o: rtl.c $(BCONFIG_H) coretype *** 2375,2380 **** --- 2391,2398 ---- $(RTL_H) $(GGC_H) errors.h build/vec.o : vec.c $(BCONFIG_H) $(SYSTEM_H) coretypes.h $(VEC_H) \ $(GGC_H) toplev.h $(DIAGNOSTIC_CORE_H) + build/hash-table.o : hash-table.c $(BCONFIG_H) $(SYSTEM_H) coretypes.h \ + $(HASH_TABLE_H) $(GGC_H) toplev.h $(DIAGNOSTIC_CORE_H) build/gencondmd.o : build/gencondmd.c $(BCONFIG_H) $(SYSTEM_H) \ coretypes.h $(GTM_H) insn-constants.h \ $(filter-out insn-flags.h, $(RTL_H) $(TM_P_H) $(FUNCTION_H) $(REGS_H) \ *************** build/genhooks.o : genhooks.c $(TARGET_D *** 2470,2475 **** --- 2488,2495 ---- $(COMMON_TARGET_DEF) $(BCONFIG_H) $(SYSTEM_H) errors.h build/genmddump.o : genmddump.c $(RTL_BASE_H) $(BCONFIG_H) $(SYSTEM_H) \ coretypes.h $(GTM_H) errors.h $(READ_MD_H) gensupport.h + build/genmatch.o : genmatch.c $(BCONFIG_H) $(SYSTEM_H) \ + coretypes.h errors.h # Compile the programs that generate insn-* from the machine description. # They are compiled with $(COMPILER_FOR_BUILD), and associated libraries, *************** genprogerr = $(genprogmd) genrtl modes g *** 2490,2500 **** $(genprogerr:%=build/gen%$(build_exeext)): $(BUILD_ERRORS) # Remaining build programs. ! genprog = $(genprogerr) check checksum condmd # These programs need libs over and above what they get from the above list. build/genautomata$(build_exeext) : BUILD_LIBS += -lm # These programs are not linked with the MD reader. build/gengtype$(build_exeext) : build/gengtype-lex.o build/gengtype-parse.o \ build/gengtype-state.o build/version.o build/errors.o --- 2510,2523 ---- $(genprogerr:%=build/gen%$(build_exeext)): $(BUILD_ERRORS) # Remaining build programs. ! genprog = $(genprogerr) check checksum condmd match # These programs need libs over and above what they get from the above list. build/genautomata$(build_exeext) : BUILD_LIBS += -lm + build/genmatch$(build_exeext) : $(CPPLIB) $(LIBIBERTY) \ + $(BUILD_ERRORS) build/vec.o build/hash-table.o + # These programs are not linked with the MD reader. build/gengtype$(build_exeext) : build/gengtype-lex.o build/gengtype-parse.o \ build/gengtype-state.o build/version.o build/errors.o *************** TEXI_GCCINT_FILES = gccint.texi gcc-comm *** 2829,2835 **** configfiles.texi collect2.texi headerdirs.texi funding.texi \ gnu.texi gpl_v3.texi fdl.texi contrib.texi languages.texi \ sourcebuild.texi gty.texi libgcc.texi cfg.texi tree-ssa.texi \ ! loop.texi generic.texi gimple.texi plugins.texi optinfo.texi TEXI_GCCINSTALL_FILES = install.texi install-old.texi fdl.texi \ gcc-common.texi gcc-vers.texi --- 2852,2859 ---- configfiles.texi collect2.texi headerdirs.texi funding.texi \ gnu.texi gpl_v3.texi fdl.texi contrib.texi languages.texi \ sourcebuild.texi gty.texi libgcc.texi cfg.texi tree-ssa.texi \ ! loop.texi generic.texi gimple.texi plugins.texi optinfo.texi \ ! match-and-simplify.texi TEXI_GCCINSTALL_FILES = install.texi install-old.texi fdl.texi \ gcc-common.texi gcc-vers.texi Index: gcc/generic-match-head.c =================================================================== *** /dev/null 1970-01-01 00:00:00.000000000 +0000 --- gcc/generic-match-head.c 2014-10-15 12:27:41.353241352 +0200 *************** *** 0 **** --- 1,46 ---- + /* Preamble and helpers for the autogenerated generic-match.c file. + Copyright (C) 2014 Free Software Foundation, Inc. + + This file is part of GCC. + + GCC is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3, or (at your option) any later + version. + + GCC is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or + FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + + You should have received a copy of the GNU General Public License + along with GCC; see the file COPYING3. If not see + <http://www.gnu.org/licenses/>. */ + + #include "config.h" + #include "system.h" + #include "coretypes.h" + #include "tree.h" + #include "stringpool.h" + #include "stor-layout.h" + #include "flags.h" + #include "function.h" + #include "basic-block.h" + #include "tree-ssa-alias.h" + #include "internal-fn.h" + #include "gimple-expr.h" + #include "is-a.h" + #include "gimple.h" + #include "gimple-ssa.h" + #include "tree-ssanames.h" + #include "gimple-fold.h" + #include "gimple-iterator.h" + #include "expr.h" + #include "tree-dfa.h" + #include "builtins.h" + #include "tree-phinodes.h" + #include "ssa-iterators.h" + #include "dumpfile.h" + #include "gimple-match.h" + + Index: gcc/gimple-match.h =================================================================== *** /dev/null 1970-01-01 00:00:00.000000000 +0000 --- gcc/gimple-match.h 2014-10-15 12:27:41.354241352 +0200 *************** *** 0 **** --- 1,50 ---- + /* Gimple simplify definitions. + + Copyright (C) 2011-2014 Free Software Foundation, Inc. + Contributed by Richard Guenther <rguent...@suse.de> + + This file is part of GCC. + + GCC is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3, or (at your option) any later + version. + + GCC is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or + FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + + You should have received a copy of the GNU General Public License + along with GCC; see the file COPYING3. If not see + <http://www.gnu.org/licenses/>. */ + + #ifndef GCC_GIMPLE_MATCH_H + #define GCC_GIMPLE_MATCH_H + + + /* Helper to transparently allow tree codes and builtin function codes + exist in one storage entity. */ + class code_helper + { + public: + code_helper () {} + code_helper (tree_code code) : rep ((int) code) {} + code_helper (built_in_function fn) : rep (-(int) fn) {} + operator tree_code () const { return (tree_code) rep; } + operator built_in_function () const { return (built_in_function) -rep; } + bool is_tree_code () const { return rep > 0; } + bool is_fn_code () const { return rep < 0; } + int get_rep () const { return rep; } + private: + int rep; + }; + + bool gimple_simplify (gimple, code_helper *, tree *, gimple_seq *, + tree (*)(tree)); + tree maybe_push_res_to_seq (code_helper, tree, tree *, + gimple_seq *, tree res = NULL_TREE); + void maybe_build_generic_op (enum tree_code, tree, tree *, tree, tree); + + + #endif /* GCC_GIMPLE_MATCH_H */ Index: gcc/match.pd =================================================================== *** /dev/null 1970-01-01 00:00:00.000000000 +0000 --- gcc/match.pd 2014-10-15 12:27:41.354241352 +0200 *************** *** 0 **** --- 1,29 ---- + /* Match-and-simplify patterns for shared GENERIC and GIMPLE folding. + This file is consumed by genmatch which produces gimple-match.c + from it. + + Copyright (C) 2014 Free Software Foundation, Inc. + Contributed by Richard Biener <rguent...@suse.de> + + This file is part of GCC. + + GCC is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3, or (at your option) any later + version. + + GCC is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or + FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + + You should have received a copy of the GNU General Public License + along with GCC; see the file COPYING3. If not see + <http://www.gnu.org/licenses/>. */ + + + /* Generic tree predicates we inherit. */ + (define_predicates + integer_onep integer_zerop integer_all_onesp + real_zerop real_onep + CONSTANT_CLASS_P) Index: gcc/doc/match-and-simplify.texi =================================================================== *** /dev/null 1970-01-01 00:00:00.000000000 +0000 --- gcc/doc/match-and-simplify.texi 2014-10-15 12:27:41.355241352 +0200 *************** *** 0 **** --- 1,314 ---- + @c Copyright (C) 2014 Free Software Foundation, Inc. + @c Free Software Foundation, Inc. + @c This is part of the GCC manual. + @c For copying conditions, see the file gcc.texi. + + @node Match and Simplify + @chapter Match and Simplify + @cindex Match and Simplify + + The GIMPLE and GENERIC pattern matching project match-and-simplify + tries to address several issues. + + @enumerate + @item unify expression simplifications currently spread and duplicated + over separate files like fold-const.c, gimple-fold.c and builtins.c + @item allow for a cheap way to implement building and simplifying + non-trivial GIMPLE expressions, avoiding the need to go through + building and simplifying GENERIC via fold_buildN and then + gimplifying via force_gimple_operand + @end enumerate + + To address these the project introduces a simple domain specific language + to write expression simplifications from which code targeting GIMPLE + and GENERIC is auto-generated. The GENERIC variant follows the + fold_buildN API while for the GIMPLE variant and to address 2) new + APIs are introduced. + + @menu + * GIMPLE API:: + * The Language:: + @end menu + + @node GIMPLE API + @section GIMPLE API + @cindex GIMPLE API + + @deftypefn {GIMPLE function} tree gimple_simplify (enum tree_code, tree, tree, gimple_seq *, tree (*)(tree)) + @deftypefnx {GIMPLE function} tree gimple_simplify (enum tree_code, tree, tree, tree, gimple_seq *, tree (*)(tree)) + @deftypefnx {GIMPLE function} tree gimple_simplify (enum tree_code, tree, tree, tree, tree, gimple_seq *, tree (*)(tree)) + @deftypefnx {GIMPLE function} tree gimple_simplify (enum built_in_function, tree, tree, gimple_seq *, tree (*)(tree)) + @deftypefnx {GIMPLE function} tree gimple_simplify (enum built_in_function, tree, tree, tree, gimple_seq *, tree (*)(tree)) + @deftypefnx {GIMPLE function} tree gimple_simplify (enum built_in_function, tree, tree, tree, gimple_seq *, tree (*)(tree)) + The main GIMPLE API entry to the expression simplifications mimicing + that of the GENERIC fold_@{unary,binary,ternary@} functions. + @end deftypefn + + thus providing n-ary overloads for operation or function. The + additional arguments are a gimple_seq where built statements are + inserted on (if @code{NULL} then simplifications requiring new statements + are not performed) and a valueization hook that can be used to + tie simplifications to a SSA lattice. + + In addition to those APIs @code{fold_stmt} is overloaded with + a valueization hook: + + @deftypefn bool fold_stmt (gimple_stmt_iterator *, tree (*)(tree)); + @end deftypefn + + + Ontop of these a @code{fold_buildN}-like API for GIMPLE is introduced: + + @deftypefn {GIMPLE function} tree gimple_build (gimple_seq *, location_t, enum tree_code, tree, tree, tree (*valueize) (tree) = NULL); + @deftypefnx {GIMPLE function} tree gimple_build (gimple_seq *, location_t, enum tree_code, tree, tree, tree, tree (*valueize) (tree) = NULL); + @deftypefnx {GIMPLE function} tree gimple_build (gimple_seq *, location_t, enum tree_code, tree, tree, tree, tree, tree (*valueize) (tree) = NULL); + @deftypefnx {GIMPLE function} tree gimple_build (gimple_seq *, location_t, enum built_in_function, tree, tree, tree (*valueize) (tree) = NULL); + @deftypefnx {GIMPLE function} tree gimple_build (gimple_seq *, location_t, enum built_in_function, tree, tree, tree, tree (*valueize) (tree) = NULL); + @deftypefnx {GIMPLE function} tree gimple_convert (gimple_seq *, location_t, tree, tree); + @end deftypefn + + which is supposed to replace @code{force_gimple_operand (fold_buildN (...), ...)} + and calls to @code{fold_convert}. Overloads without the @code{location_t} + argument exist. Built statements are inserted on the provided sequence + and simplification is performed using the optional valueization hook. + + + @node The Language + @section The Language + @cindex The Language + + The language to write expression simplifications in resembles other + domain-specific languages GCC uses. Thus it is lispy. Lets start + with an example from the match.pd file: + + @smallexample + (simplify + (bit_and @@0 integer_all_onesp) + @@0) + @end smallexample + + This example contains all required parts of an expression simplification. + A simplification is wrapped inside a @code{(simplify ...)} expression. + That contains at least two operands - an expression that is matched + with the GIMPLE or GENERIC IL and a replacement expression that is + returned if the match was successful. + + Expressions have an operator ID, @code{bit_and} in this case. Expressions can + be lower-case tree codes with @code{_expr} stripped off or builtin + function code names in all-caps, like @code{BUILT_IN_SQRT}. + + @code{@@n} denotes a so-called capture. It captures the operand and lets + you refer to it in other places of the match-and-simplify. In the + above example it is refered to in the replacement expression. Captures + are @code{@@} followed by a number or an identifier. + + @smallexample + (simplify + (bit_xor @@0 @@0) + @{ build_zero_cst (type); @}) + @end smallexample + + In this example @code{@@0} is mentioned twice which constrains the matched + expression to have two equal operands. This example also introduces + operands written in C code. These can be used in the expression + replacements and are supposed to evaluate to a tree node which has to + be a valid GIMPLE operand (so you cannot generate expressions in C code). + + @smallexample + (simplify + (trunc_mod integer_zerop@@0 @@1) + (if (!integer_zerop (@@1))) + @@0) + @end smallexample + + Here @code{@@0} captures the first operand of the trunc_mod expression + which is also predicated with @code{integer_zerop}. Expression operands + may be either expressions, predicates or captures. Captures + can be unconstrained or capture expresions or predicates. + + This example introduces an optional operand of simplify, + the if-expression. This condition is evaluated after the + expression matched in the IL and is required to evaluate to true + to enable the replacement expression. The expression operand + of the @code{if} is a standard C expression which may contain references + to captures. + + A @code{if} expression can be used to specify a common condition + for multiple simplify patterns, avoiding the need + to repeat that multiple times: + + @smallexample + (if (!TYPE_SATURATING (type) + && !FLOAT_TYPE_P (type) && !FIXED_POINT_TYPE_P (type)) + (simplify + (minus (plus @@0 @@1) @@0) + @@1) + (simplify + (minus (minus @@0 @@1) @@0) + (negate @@1))) + @end smallexample + + Ifs can be nested. + + Captures can also be used for capturing results of sub-expressions. + + @smallexample + #if GIMPLE + (simplify + (pointer_plus (addr@@2 @@0) INTEGER_CST_P@@1) + (if (is_gimple_min_invariant (@@2))) + @{ + HOST_WIDE_INT off; + tree base = get_addr_base_and_unit_offset (@@0, &off); + off += tree_to_uhwi (@@1); + /* Now with that we should be able to simply write + (addr (mem_ref (addr @@base) (plus @@off @@1))) */ + build1 (ADDR_EXPR, type, + build2 (MEM_REF, TREE_TYPE (TREE_TYPE (@@2)), + build_fold_addr_expr (base), + build_int_cst (ptr_type_node, off))); + @}) + #endif + @end smallexample + + In the above example, @code{@@2} captures the result of the expression + @code{(addr @@0)}. For outermost expression only its type can be captured, + and the keyword @code{type} is reserved for this purpose. The above + example also gives a way to conditionalize patterns to only apply + to @code{GIMPLE} or @code{GENERIC} by means of using the pre-defined + preprocessor macros @code{GIMPLE} and @code{GENERIC} and using + preprocessor directives. + + @smallexample + (simplify + (bit_and:c integral_op_p@@0 (bit_ior:c (bit_not @@0) @@1)) + (bit_and @@1 @@0)) + @end smallexample + + Here we introduce flags on match expressions. There is currently + a single flag, @code{c}, which denotes that the expression should + be also matched commutated. Thus the above match expression + is really the following four match expressions: + + (bit_and integral_op_p@@0 (bit_ior (bit_not @@0) @@1)) + (bit_and (bit_ior (bit_not @@0) @@1) integral_op_p@@0) + (bit_and integral_op_p@@0 (bit_ior @@1 (bit_not @@0))) + (bit_and (bit_ior @@1 (bit_not @@0)) integral_op_p@@0) + + Usual canonicalizations you know from GENERIC expressions are + applied before matching, so for example constant operands always + come second in commutative expressions. + + More features exist to avoid too much repetition. + + @smallexample + (for op (plus pointer_plus minus bit_ior bit_xor) + (simplify + (op @@0 integer_zerop) + @@0)) + @end smallexample + + A @code{for} expression can be used to repeat a pattern for each + operator specified, substituting @code{op}. @code{for} can be + nested and a @code{for} can have multiple operators to iterate. + + @smallexample + (for opa (plus minus) + opb (minus plus) + (for opc (plus minus) + (simplify... + @end smallexample + + In this example the pattern will be repeated four times with + @code{opa, opb, opc} being @code{plus, minus, plus}, + @code{plus, minus, minus}, @code{minus, plus, plus}, + @code{minus, plus, minus}. + + Another building block are @code{with} expressions in the + result expression which nest the generated code in a new C block + followed by its argument: + + @smallexample + (simplify + (convert (mult @@0 @@1)) + (with @{ tree utype = unsigned_type_for (type); @} + (convert (mult (convert:utype @@0) (convert:utype @@1))))) + @end smallexample + + This allows code nested in the @code{with} to refer to the declared + variables. In the above case we use the feature to specify the + type of a generated expression with the @code{:type} syntax where + @code{type} needs to be an identifier that refers to the desired type. + Usually the types of the generated result expressions are + determined from the context, but sometimes like in the above case + it is required that you specify them explicitely. + + As intermediate conversions are often optional there is a way to + avoid the need to repeat patterns both with and without such + conversions. Namely you can mark a conversion as being optional + with a @code{?}: + + @smallexample + (simplify + (eq (convert@@0 @@1) (convert? @@2)) + (eq @@1 (convert @@2))) + @end smallexample + + which will match both @code{(eq (convert @@1) (convert @@2))} and + @code{(eq (convert @@1) @@2)}. The optional converts are supposed + to be all either present or not, thus + @code{(eq (convert? @@1) (convert? @@2))} will result in two + patterns only. If you want to match all four combinations you + have access to two additional conditional converts as in + @code{(eq (convert1? @@1) (convert2? @@2))}. + + Predicates available from the GCC middle-end need to be made + available explicitely via @code{define_predicates}: + + @smallexample + (define_predicates + integer_onep integer_zerop integer_all_onesp) + @end smallexample + + You can also define predicates using the pattern matching language + and the @code{match} form: + + @smallexample + (match negate_expr_p + INTEGER_CST + (if (TYPE_OVERFLOW_WRAPS (type) + || may_negate_without_overflow_p (t)))) + (match negate_expr_p + (negate @@0)) + @end smallexample + + This shows that for @code{match} expressions there is @code{t} + available which captures the outermost expression (something + not possible in the @code{simplify} context). As you can see + @code{match} has an identifier as first operand which is how + you refer to the predicate in patterns. Multiple @code{match} + for the same identifier add additional cases where the predicate + matches. + + Predicates can also match an expression in which case you need + to provide a template specifying the identifier and where to + get its operands from: + + @smallexample + (match (logical_inverted_value @@0) + (eq @@0 integer_zerop)) + (match (logical_inverted_value @@0) + (bit_not truth_valued_p@@0)) + @end smallexample + + You can use the above predicate like + + @smallexample + (simplify + (bit_and @@0 (logical_inverted_value @@0)) + @{ build_zero_cst (type); @}) + @end smallexample + + Which will match a bitwise and of an operand with its logical + inverted value. + Index: gcc/doc/gccint.texi =================================================================== *** gcc/doc/gccint.texi.orig 2014-10-15 12:24:05.129256239 +0200 --- gcc/doc/gccint.texi 2014-10-15 12:27:41.355241352 +0200 *************** Additional tutorial information is linke *** 123,128 **** --- 123,129 ---- * Plugins:: Extending the compiler with plugins. * LTO:: Using Link-Time Optimization. + * Match and Simplify:: How to write expression simplification patterns for GIMPLE and GENERIC * Funding:: How to help assure funding for free software. * GNU Project:: The GNU Project and GNU/Linux. *************** Additional tutorial information is linke *** 158,163 **** --- 159,165 ---- @include gty.texi @include plugins.texi @include lto.texi + @include match-and-simplify.texi @include funding.texi @include gnu.texi Index: gcc/builtins.h =================================================================== *** gcc/builtins.h.orig 2014-10-15 12:24:05.129256239 +0200 --- gcc/builtins.h 2014-10-15 12:27:41.355241352 +0200 *************** extern tree fold_fma (location_t, tree, *** 75,80 **** --- 75,81 ---- extern bool avoid_folding_inline_builtin (tree); extern tree fold_call_expr (location_t, tree, bool); extern tree fold_builtin_call_array (location_t, tree, tree, int, tree *); + extern tree fold_builtin_n (location_t, tree, tree *, int, bool); extern bool validate_gimple_arglist (const_gimple, ...); extern rtx default_expand_builtin (tree, rtx, rtx, enum machine_mode, int); extern bool fold_builtin_next_arg (tree, bool); Index: gcc/builtins.c =================================================================== *** gcc/builtins.c.orig 2014-10-15 12:24:05.129256239 +0200 --- gcc/builtins.c 2014-10-15 12:27:41.358241352 +0200 *************** static tree fold_builtin_fabs (location_ *** 176,182 **** static tree fold_builtin_abs (location_t, tree, tree); static tree fold_builtin_unordered_cmp (location_t, tree, tree, tree, enum tree_code, enum tree_code); - static tree fold_builtin_n (location_t, tree, tree *, int, bool); static tree fold_builtin_0 (location_t, tree, bool); static tree fold_builtin_1 (location_t, tree, tree, bool); static tree fold_builtin_2 (location_t, tree, tree, tree, bool); --- 176,181 ---- *************** fold_builtin_4 (location_t loc, tree fnd *** 10395,10401 **** #define MAX_ARGS_TO_FOLD_BUILTIN 4 ! static tree fold_builtin_n (location_t loc, tree fndecl, tree *args, int nargs, bool ignore) { tree ret = NULL_TREE; --- 10394,10400 ---- #define MAX_ARGS_TO_FOLD_BUILTIN 4 ! tree fold_builtin_n (location_t loc, tree fndecl, tree *args, int nargs, bool ignore) { tree ret = NULL_TREE; Index: gcc/gimple-match-head.c =================================================================== *** /dev/null 1970-01-01 00:00:00.000000000 +0000 --- gcc/gimple-match-head.c 2014-10-15 12:27:41.359241352 +0200 *************** *** 0 **** --- 1,835 ---- + /* Preamble and helpers for the autogenerated gimple-match.c file. + Copyright (C) 2014 Free Software Foundation, Inc. + + This file is part of GCC. + + GCC is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3, or (at your option) any later + version. + + GCC is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or + FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + + You should have received a copy of the GNU General Public License + along with GCC; see the file COPYING3. If not see + <http://www.gnu.org/licenses/>. */ + + #include "config.h" + #include "system.h" + #include "coretypes.h" + #include "tree.h" + #include "stringpool.h" + #include "stor-layout.h" + #include "flags.h" + #include "function.h" + #include "basic-block.h" + #include "tree-ssa-alias.h" + #include "internal-fn.h" + #include "gimple-expr.h" + #include "is-a.h" + #include "gimple.h" + #include "gimple-ssa.h" + #include "tree-ssanames.h" + #include "gimple-fold.h" + #include "gimple-iterator.h" + #include "expr.h" + #include "tree-dfa.h" + #include "builtins.h" + #include "tree-phinodes.h" + #include "ssa-iterators.h" + #include "dumpfile.h" + #include "gimple-match.h" + + + /* Forward declarations of the private auto-generated matchers. + They expect valueized operands in canonical order and do not + perform simplification of all-constant operands. */ + static bool gimple_simplify (code_helper *, tree *, + gimple_seq *, tree (*)(tree), + code_helper, tree, tree); + static bool gimple_simplify (code_helper *, tree *, + gimple_seq *, tree (*)(tree), + code_helper, tree, tree, tree); + static bool gimple_simplify (code_helper *, tree *, + gimple_seq *, tree (*)(tree), + code_helper, tree, tree, tree, tree); + + + /* Return whether T is a constant that we'll dispatch to fold to + evaluate fully constant expressions. */ + + static inline bool + constant_for_folding (tree t) + { + return (CONSTANT_CLASS_P (t) + /* The following is only interesting to string builtins. */ + || (TREE_CODE (t) == ADDR_EXPR + && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST)); + } + + + /* Helper that matches and simplifies the toplevel result from + a gimple_simplify run (where we don't want to build + a stmt in case it's used in in-place folding). Replaces + *RES_CODE and *RES_OPS with a simplified and/or canonicalized + result and returns whether any change was made. */ + + static bool + gimple_resimplify1 (gimple_seq *seq, + code_helper *res_code, tree type, tree *res_ops, + tree (*valueize)(tree)) + { + if (constant_for_folding (res_ops[0])) + { + tree tem = NULL_TREE; + if (res_code->is_tree_code ()) + tem = fold_unary_to_constant (*res_code, type, res_ops[0]); + else + { + tree decl = builtin_decl_implicit (*res_code); + if (decl) + { + tem = fold_builtin_n (UNKNOWN_LOCATION, decl, res_ops, 1, false); + if (tem) + { + /* fold_builtin_n wraps the result inside a NOP_EXPR. */ + STRIP_NOPS (tem); + tem = fold_convert (type, tem); + } + } + } + if (tem != NULL_TREE + && CONSTANT_CLASS_P (tem)) + { + res_ops[0] = tem; + res_ops[1] = NULL_TREE; + res_ops[2] = NULL_TREE; + *res_code = TREE_CODE (res_ops[0]); + return true; + } + } + + code_helper res_code2; + tree res_ops2[3] = {}; + if (gimple_simplify (&res_code2, res_ops2, seq, valueize, + *res_code, type, res_ops[0])) + { + *res_code = res_code2; + res_ops[0] = res_ops2[0]; + res_ops[1] = res_ops2[1]; + res_ops[2] = res_ops2[2]; + return true; + } + + return false; + } + + /* Helper that matches and simplifies the toplevel result from + a gimple_simplify run (where we don't want to build + a stmt in case it's used in in-place folding). Replaces + *RES_CODE and *RES_OPS with a simplified and/or canonicalized + result and returns whether any change was made. */ + + static bool + gimple_resimplify2 (gimple_seq *seq, + code_helper *res_code, tree type, tree *res_ops, + tree (*valueize)(tree)) + { + if (constant_for_folding (res_ops[0]) && constant_for_folding (res_ops[1])) + { + tree tem = NULL_TREE; + if (res_code->is_tree_code ()) + tem = fold_binary_to_constant (*res_code, type, + res_ops[0], res_ops[1]); + else + { + tree decl = builtin_decl_implicit (*res_code); + if (decl) + { + tem = fold_builtin_n (UNKNOWN_LOCATION, decl, res_ops, 2, false); + if (tem) + { + /* fold_builtin_n wraps the result inside a NOP_EXPR. */ + STRIP_NOPS (tem); + tem = fold_convert (type, tem); + } + } + } + if (tem != NULL_TREE + && CONSTANT_CLASS_P (tem)) + { + res_ops[0] = tem; + res_ops[1] = NULL_TREE; + res_ops[2] = NULL_TREE; + *res_code = TREE_CODE (res_ops[0]); + return true; + } + } + + /* Canonicalize operand order. */ + bool canonicalized = false; + if (res_code->is_tree_code () + && (TREE_CODE_CLASS ((enum tree_code) *res_code) == tcc_comparison + || commutative_tree_code (*res_code)) + && tree_swap_operands_p (res_ops[0], res_ops[1], false)) + { + tree tem = res_ops[0]; + res_ops[0] = res_ops[1]; + res_ops[1] = tem; + if (TREE_CODE_CLASS ((enum tree_code) *res_code) == tcc_comparison) + *res_code = swap_tree_comparison (*res_code); + canonicalized = true; + } + + code_helper res_code2; + tree res_ops2[3] = {}; + if (gimple_simplify (&res_code2, res_ops2, seq, valueize, + *res_code, type, res_ops[0], res_ops[1])) + { + *res_code = res_code2; + res_ops[0] = res_ops2[0]; + res_ops[1] = res_ops2[1]; + res_ops[2] = res_ops2[2]; + return true; + } + + return canonicalized; + } + + /* Helper that matches and simplifies the toplevel result from + a gimple_simplify run (where we don't want to build + a stmt in case it's used in in-place folding). Replaces + *RES_CODE and *RES_OPS with a simplified and/or canonicalized + result and returns whether any change was made. */ + + static bool + gimple_resimplify3 (gimple_seq *seq, + code_helper *res_code, tree type, tree *res_ops, + tree (*valueize)(tree)) + { + if (constant_for_folding (res_ops[0]) && constant_for_folding (res_ops[1]) + && constant_for_folding (res_ops[2])) + { + tree tem = NULL_TREE; + if (res_code->is_tree_code ()) + tem = fold_ternary/*_to_constant*/ (*res_code, type, res_ops[0], + res_ops[1], res_ops[2]); + else + { + tree decl = builtin_decl_implicit (*res_code); + if (decl) + { + tem = fold_builtin_n (UNKNOWN_LOCATION, decl, res_ops, 3, false); + if (tem) + { + /* fold_builtin_n wraps the result inside a NOP_EXPR. */ + STRIP_NOPS (tem); + tem = fold_convert (type, tem); + } + } + } + if (tem != NULL_TREE + && CONSTANT_CLASS_P (tem)) + { + res_ops[0] = tem; + res_ops[1] = NULL_TREE; + res_ops[2] = NULL_TREE; + *res_code = TREE_CODE (res_ops[0]); + return true; + } + } + + /* Canonicalize operand order. */ + bool canonicalized = false; + if (res_code->is_tree_code () + && commutative_ternary_tree_code (*res_code) + && tree_swap_operands_p (res_ops[0], res_ops[1], false)) + { + tree tem = res_ops[0]; + res_ops[0] = res_ops[1]; + res_ops[1] = tem; + canonicalized = true; + } + + code_helper res_code2; + tree res_ops2[3] = {}; + if (gimple_simplify (&res_code2, res_ops2, seq, valueize, + *res_code, type, + res_ops[0], res_ops[1], res_ops[2])) + { + *res_code = res_code2; + res_ops[0] = res_ops2[0]; + res_ops[1] = res_ops2[1]; + res_ops[2] = res_ops2[2]; + return true; + } + + return canonicalized; + } + + + /* If in GIMPLE expressions with CODE go as single-rhs build + a GENERIC tree for that expression into *OP0. */ + + void + maybe_build_generic_op (enum tree_code code, tree type, + tree *op0, tree op1, tree op2) + { + switch (code) + { + case REALPART_EXPR: + case IMAGPART_EXPR: + case VIEW_CONVERT_EXPR: + *op0 = build1 (code, type, *op0); + break; + case BIT_FIELD_REF: + *op0 = build3 (code, type, *op0, op1, op2); + break; + default:; + } + } + + /* Push the exploded expression described by RCODE, TYPE and OPS + as a statement to SEQ if necessary and return a gimple value + denoting the value of the expression. If RES is not NULL + then the result will be always RES and even gimple values are + pushed to SEQ. */ + + tree + maybe_push_res_to_seq (code_helper rcode, tree type, tree *ops, + gimple_seq *seq, tree res) + { + if (rcode.is_tree_code ()) + { + if (!res + && (TREE_CODE_LENGTH ((tree_code) rcode) == 0 + || ((tree_code) rcode) == ADDR_EXPR) + && is_gimple_val (ops[0])) + return ops[0]; + if (!seq) + return NULL_TREE; + /* Play safe and do not allow abnormals to be mentioned in + newly created statements. */ + if ((TREE_CODE (ops[0]) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[0])) + || (ops[1] + && TREE_CODE (ops[1]) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[1])) + || (ops[2] + && TREE_CODE (ops[2]) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[2]))) + return NULL_TREE; + if (!res) + res = make_ssa_name (type, NULL); + maybe_build_generic_op (rcode, type, &ops[0], ops[1], ops[2]); + gimple new_stmt = gimple_build_assign_with_ops (rcode, res, + ops[0], ops[1], ops[2]); + gimple_seq_add_stmt_without_update (seq, new_stmt); + return res; + } + else + { + if (!seq) + return NULL_TREE; + tree decl = builtin_decl_implicit (rcode); + if (!decl) + return NULL_TREE; + unsigned nargs = type_num_arguments (TREE_TYPE (decl)); + gcc_assert (nargs <= 3); + /* Play safe and do not allow abnormals to be mentioned in + newly created statements. */ + if ((TREE_CODE (ops[0]) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[0])) + || (nargs >= 2 + && TREE_CODE (ops[1]) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[1])) + || (nargs == 3 + && TREE_CODE (ops[2]) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[2]))) + return NULL_TREE; + if (!res) + res = make_ssa_name (type, NULL); + gimple new_stmt = gimple_build_call (decl, nargs, ops[0], ops[1], ops[2]); + gimple_call_set_lhs (new_stmt, res); + gimple_seq_add_stmt_without_update (seq, new_stmt); + return res; + } + } + + + /* Public API overloads follow for operation being tree_code or + built_in_function and for one to three operands or arguments. + They return NULL_TREE if nothing could be simplified or + the resulting simplified value with parts pushed to SEQ. + If SEQ is NULL then if the simplification needs to create + new stmts it will fail. If VALUEIZE is non-NULL then all + SSA names will be valueized using that hook prior to + applying simplifications. */ + + /* Unary ops. */ + + tree + gimple_simplify (enum tree_code code, tree type, + tree op0, + gimple_seq *seq, tree (*valueize)(tree)) + { + if (constant_for_folding (op0)) + { + tree res = fold_unary_to_constant (code, type, op0); + if (res != NULL_TREE + && CONSTANT_CLASS_P (res)) + return res; + } + + code_helper rcode; + tree ops[3] = {}; + if (!gimple_simplify (&rcode, ops, seq, valueize, + code, type, op0)) + return NULL_TREE; + return maybe_push_res_to_seq (rcode, type, ops, seq); + } + + /* Binary ops. */ + + tree + gimple_simplify (enum tree_code code, tree type, + tree op0, tree op1, + gimple_seq *seq, tree (*valueize)(tree)) + { + if (constant_for_folding (op0) && constant_for_folding (op1)) + { + tree res = fold_binary_to_constant (code, type, op0, op1); + if (res != NULL_TREE + && CONSTANT_CLASS_P (res)) + return res; + } + + /* Canonicalize operand order both for matching and fallback stmt + generation. */ + if ((commutative_tree_code (code) + || TREE_CODE_CLASS (code) == tcc_comparison) + && tree_swap_operands_p (op0, op1, false)) + { + tree tem = op0; + op0 = op1; + op1 = tem; + if (TREE_CODE_CLASS (code) == tcc_comparison) + code = swap_tree_comparison (code); + } + + code_helper rcode; + tree ops[3] = {}; + if (!gimple_simplify (&rcode, ops, seq, valueize, + code, type, op0, op1)) + return NULL_TREE; + return maybe_push_res_to_seq (rcode, type, ops, seq); + } + + /* Ternary ops. */ + + tree + gimple_simplify (enum tree_code code, tree type, + tree op0, tree op1, tree op2, + gimple_seq *seq, tree (*valueize)(tree)) + { + if (constant_for_folding (op0) && constant_for_folding (op1) + && constant_for_folding (op2)) + { + tree res = fold_ternary/*_to_constant */ (code, type, op0, op1, op2); + if (res != NULL_TREE + && CONSTANT_CLASS_P (res)) + return res; + } + + /* Canonicalize operand order both for matching and fallback stmt + generation. */ + if (commutative_ternary_tree_code (code) + && tree_swap_operands_p (op0, op1, false)) + { + tree tem = op0; + op0 = op1; + op1 = tem; + } + + code_helper rcode; + tree ops[3] = {}; + if (!gimple_simplify (&rcode, ops, seq, valueize, + code, type, op0, op1, op2)) + return NULL_TREE; + return maybe_push_res_to_seq (rcode, type, ops, seq); + } + + /* Builtin function with one argument. */ + + tree + gimple_simplify (enum built_in_function fn, tree type, + tree arg0, + gimple_seq *seq, tree (*valueize)(tree)) + { + if (constant_for_folding (arg0)) + { + tree decl = builtin_decl_implicit (fn); + if (decl) + { + tree res = fold_builtin_n (UNKNOWN_LOCATION, decl, &arg0, 1, false); + if (res) + { + /* fold_builtin_n wraps the result inside a NOP_EXPR. */ + STRIP_NOPS (res); + res = fold_convert (type, res); + if (CONSTANT_CLASS_P (res)) + return res; + } + } + } + + code_helper rcode; + tree ops[3] = {}; + if (!gimple_simplify (&rcode, ops, seq, valueize, + fn, type, arg0)) + return NULL_TREE; + return maybe_push_res_to_seq (rcode, type, ops, seq); + } + + /* Builtin function with two arguments. */ + + tree + gimple_simplify (enum built_in_function fn, tree type, + tree arg0, tree arg1, + gimple_seq *seq, tree (*valueize)(tree)) + { + if (constant_for_folding (arg0) + && constant_for_folding (arg1)) + { + tree decl = builtin_decl_implicit (fn); + if (decl) + { + tree args[2]; + args[0] = arg0; + args[1] = arg1; + tree res = fold_builtin_n (UNKNOWN_LOCATION, decl, args, 2, false); + if (res) + { + /* fold_builtin_n wraps the result inside a NOP_EXPR. */ + STRIP_NOPS (res); + res = fold_convert (type, res); + if (CONSTANT_CLASS_P (res)) + return res; + } + } + } + + code_helper rcode; + tree ops[3] = {}; + if (!gimple_simplify (&rcode, ops, seq, valueize, + fn, type, arg0, arg1)) + return NULL_TREE; + return maybe_push_res_to_seq (rcode, type, ops, seq); + } + + /* Builtin function with three arguments. */ + + tree + gimple_simplify (enum built_in_function fn, tree type, + tree arg0, tree arg1, tree arg2, + gimple_seq *seq, tree (*valueize)(tree)) + { + if (constant_for_folding (arg0) + && constant_for_folding (arg1) + && constant_for_folding (arg2)) + { + tree decl = builtin_decl_implicit (fn); + if (decl) + { + tree args[3]; + args[0] = arg0; + args[1] = arg1; + args[2] = arg2; + tree res = fold_builtin_n (UNKNOWN_LOCATION, decl, args, 3, false); + if (res) + { + /* fold_builtin_n wraps the result inside a NOP_EXPR. */ + STRIP_NOPS (res); + res = fold_convert (type, res); + if (CONSTANT_CLASS_P (res)) + return res; + } + } + } + + code_helper rcode; + tree ops[3] = {}; + if (!gimple_simplify (&rcode, ops, seq, valueize, + fn, type, arg0, arg1, arg2)) + return NULL_TREE; + return maybe_push_res_to_seq (rcode, type, ops, seq); + } + + + /* The main STMT based simplification entry. It is used by the fold_stmt + and the fold_stmt_to_constant APIs. */ + + bool + gimple_simplify (gimple stmt, + code_helper *rcode, tree *ops, + gimple_seq *seq, tree (*valueize)(tree)) + { + switch (gimple_code (stmt)) + { + case GIMPLE_ASSIGN: + { + enum tree_code code = gimple_assign_rhs_code (stmt); + tree type = TREE_TYPE (gimple_assign_lhs (stmt)); + switch (gimple_assign_rhs_class (stmt)) + { + case GIMPLE_SINGLE_RHS: + if (code == REALPART_EXPR + || code == IMAGPART_EXPR + || code == VIEW_CONVERT_EXPR) + { + tree op0 = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); + if (valueize && TREE_CODE (op0) == SSA_NAME) + { + tree tem = valueize (op0); + if (tem) + op0 = tem; + } + *rcode = code; + ops[0] = op0; + return gimple_resimplify1 (seq, rcode, type, ops, valueize); + } + else if (code == BIT_FIELD_REF) + { + tree rhs1 = gimple_assign_rhs1 (stmt); + tree op0 = TREE_OPERAND (rhs1, 0); + if (valueize && TREE_CODE (op0) == SSA_NAME) + { + tree tem = valueize (op0); + if (tem) + op0 = tem; + } + *rcode = code; + ops[0] = op0; + ops[1] = TREE_OPERAND (rhs1, 1); + ops[2] = TREE_OPERAND (rhs1, 2); + return gimple_resimplify3 (seq, rcode, type, ops, valueize); + } + else if (code == SSA_NAME + && valueize) + { + tree op0 = gimple_assign_rhs1 (stmt); + tree valueized = valueize (op0); + if (!valueized || op0 == valueized) + return false; + ops[0] = valueized; + *rcode = TREE_CODE (op0); + return true; + } + break; + case GIMPLE_UNARY_RHS: + { + tree rhs1 = gimple_assign_rhs1 (stmt); + if (valueize && TREE_CODE (rhs1) == SSA_NAME) + { + tree tem = valueize (rhs1); + if (tem) + rhs1 = tem; + } + *rcode = code; + ops[0] = rhs1; + return gimple_resimplify1 (seq, rcode, type, ops, valueize); + } + case GIMPLE_BINARY_RHS: + { + tree rhs1 = gimple_assign_rhs1 (stmt); + if (valueize && TREE_CODE (rhs1) == SSA_NAME) + { + tree tem = valueize (rhs1); + if (tem) + rhs1 = tem; + } + tree rhs2 = gimple_assign_rhs2 (stmt); + if (valueize && TREE_CODE (rhs2) == SSA_NAME) + { + tree tem = valueize (rhs2); + if (tem) + rhs2 = tem; + } + *rcode = code; + ops[0] = rhs1; + ops[1] = rhs2; + return gimple_resimplify2 (seq, rcode, type, ops, valueize); + } + case GIMPLE_TERNARY_RHS: + { + tree rhs1 = gimple_assign_rhs1 (stmt); + if (valueize && TREE_CODE (rhs1) == SSA_NAME) + { + tree tem = valueize (rhs1); + if (tem) + rhs1 = tem; + } + tree rhs2 = gimple_assign_rhs2 (stmt); + if (valueize && TREE_CODE (rhs2) == SSA_NAME) + { + tree tem = valueize (rhs2); + if (tem) + rhs2 = tem; + } + tree rhs3 = gimple_assign_rhs3 (stmt); + if (valueize && TREE_CODE (rhs3) == SSA_NAME) + { + tree tem = valueize (rhs3); + if (tem) + rhs3 = tem; + } + *rcode = code; + ops[0] = rhs1; + ops[1] = rhs2; + ops[2] = rhs3; + return gimple_resimplify3 (seq, rcode, type, ops, valueize); + } + default: + gcc_unreachable (); + } + break; + } + + case GIMPLE_CALL: + /* ??? This way we can't simplify calls with side-effects. */ + if (gimple_call_lhs (stmt) != NULL_TREE) + { + tree fn = gimple_call_fn (stmt); + /* ??? Internal function support missing. */ + if (!fn) + return false; + if (valueize && TREE_CODE (fn) == SSA_NAME) + { + tree tem = valueize (fn); + if (tem) + fn = tem; + } + if (!fn + || TREE_CODE (fn) != ADDR_EXPR + || TREE_CODE (TREE_OPERAND (fn, 0)) != FUNCTION_DECL + || DECL_BUILT_IN_CLASS (TREE_OPERAND (fn, 0)) != BUILT_IN_NORMAL + || !builtin_decl_implicit (DECL_FUNCTION_CODE (TREE_OPERAND (fn, 0))) + || !gimple_builtin_call_types_compatible_p (stmt, + TREE_OPERAND (fn, 0))) + return false; + + tree decl = TREE_OPERAND (fn, 0); + tree type = TREE_TYPE (gimple_call_lhs (stmt)); + switch (gimple_call_num_args (stmt)) + { + case 1: + { + tree arg1 = gimple_call_arg (stmt, 0); + if (valueize && TREE_CODE (arg1) == SSA_NAME) + { + tree tem = valueize (arg1); + if (tem) + arg1 = tem; + } + *rcode = DECL_FUNCTION_CODE (decl); + ops[0] = arg1; + return gimple_resimplify1 (seq, rcode, type, ops, valueize); + } + case 2: + { + tree arg1 = gimple_call_arg (stmt, 0); + if (valueize && TREE_CODE (arg1) == SSA_NAME) + { + tree tem = valueize (arg1); + if (tem) + arg1 = tem; + } + tree arg2 = gimple_call_arg (stmt, 1); + if (valueize && TREE_CODE (arg2) == SSA_NAME) + { + tree tem = valueize (arg2); + if (tem) + arg2 = tem; + } + *rcode = DECL_FUNCTION_CODE (decl); + ops[0] = arg1; + ops[1] = arg2; + return gimple_resimplify2 (seq, rcode, type, ops, valueize); + } + case 3: + { + tree arg1 = gimple_call_arg (stmt, 0); + if (valueize && TREE_CODE (arg1) == SSA_NAME) + { + tree tem = valueize (arg1); + if (tem) + arg1 = tem; + } + tree arg2 = gimple_call_arg (stmt, 1); + if (valueize && TREE_CODE (arg2) == SSA_NAME) + { + tree tem = valueize (arg2); + if (tem) + arg2 = tem; + } + tree arg3 = gimple_call_arg (stmt, 2); + if (valueize && TREE_CODE (arg3) == SSA_NAME) + { + tree tem = valueize (arg3); + if (tem) + arg3 = tem; + } + *rcode = DECL_FUNCTION_CODE (decl); + ops[0] = arg1; + ops[1] = arg2; + ops[2] = arg3; + return gimple_resimplify3 (seq, rcode, type, ops, valueize); + } + default: + return false; + } + } + break; + + case GIMPLE_COND: + { + tree lhs = gimple_cond_lhs (stmt); + if (valueize && TREE_CODE (lhs) == SSA_NAME) + { + tree tem = valueize (lhs); + if (tem) + lhs = tem; + } + tree rhs = gimple_cond_rhs (stmt); + if (valueize && TREE_CODE (rhs) == SSA_NAME) + { + tree tem = valueize (rhs); + if (tem) + rhs = tem; + } + *rcode = gimple_cond_code (stmt); + ops[0] = lhs; + ops[1] = rhs; + return gimple_resimplify2 (seq, rcode, boolean_type_node, ops, valueize); + } + + default: + break; + } + + return false; + } + + + /* Helper for the autogenerated code, valueize OP. */ + + inline tree + do_valueize (tree (*valueize)(tree), tree op) + { + if (valueize && TREE_CODE (op) == SSA_NAME) + return valueize (op); + return op; + } Index: gcc/genmatch.c =================================================================== *** /dev/null 1970-01-01 00:00:00.000000000 +0000 --- gcc/genmatch.c 2014-10-15 12:27:41.363241352 +0200 *************** *** 0 **** --- 1,3040 ---- + /* Generate pattern matching and transform code shared between + GENERIC and GIMPLE folding code from match-and-simplify description. + + Copyright (C) 2014 Free Software Foundation, Inc. + Contributed by Richard Biener <rguent...@suse.de> + + This file is part of GCC. + + GCC is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3, or (at your option) any later + version. + + GCC is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or + FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + + You should have received a copy of the GNU General Public License + along with GCC; see the file COPYING3. If not see + <http://www.gnu.org/licenses/>. */ + + #include "bconfig.h" + #include <new> + #include <map> + #include <utility> + #include <string> + #include "system.h" + #include "coretypes.h" + #include <cpplib.h> + #include "errors.h" + #include "hashtab.h" + #include "hash-table.h" + #include "vec.h" + #include "is-a.h" + + + /* libccp helpers. */ + + static struct line_maps *line_table; + + static bool + #if GCC_VERSION >= 4001 + __attribute__((format (printf, 6, 0))) + #endif + error_cb (cpp_reader *, int, int, source_location location, + unsigned int, const char *msg, va_list *ap) + { + const line_map *map; + linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map); + expanded_location loc = linemap_expand_location (line_table, map, location); + fprintf (stderr, "%s:%d:%d error: ", loc.file, loc.line, loc.column); + vfprintf (stderr, msg, *ap); + fprintf (stderr, "\n"); + FILE *f = fopen (loc.file, "r"); + if (f) + { + char buf[128]; + while (loc.line > 0) + { + if (!fgets (buf, 128, f)) + goto notfound; + if (buf[strlen (buf) - 1] != '\n') + { + if (loc.line > 1) + loc.line++; + } + loc.line--; + } + fprintf (stderr, "%s", buf); + for (int i = 0; i < loc.column - 1; ++i) + fputc (' ', stderr); + fputc ('^', stderr); + fputc ('\n', stderr); + notfound: + fclose (f); + } + exit (1); + } + + static void + #if GCC_VERSION >= 4001 + __attribute__((format (printf, 2, 3))) + #endif + fatal_at (const cpp_token *tk, const char *msg, ...) + { + va_list ap; + va_start (ap, msg); + error_cb (NULL, CPP_DL_FATAL, 0, tk->src_loc, 0, msg, &ap); + va_end (ap); + } + + static void + output_line_directive (FILE *f, source_location location, + bool dumpfile = false) + { + const line_map *map; + linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map); + expanded_location loc = linemap_expand_location (line_table, map, location); + if (dumpfile) + { + /* When writing to a dumpfile only dump the filename. */ + const char *file = strrchr (loc.file, DIR_SEPARATOR); + if (!file) + file = loc.file; + else + ++file; + fprintf (f, "%s:%d", file, loc.line); + } + else + /* Other gen programs really output line directives here, at least for + development it's right now more convenient to have line information + from the generated file. Still keep the directives as comment for now + to easily back-point to the meta-description. */ + fprintf (f, "/* #line %d \"%s\" */\n", loc.line, loc.file); + } + + + /* Pull in tree codes and builtin function codes from their + definition files. */ + + #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM, + enum tree_code { + #include "tree.def" + CONVERT0, + CONVERT1, + CONVERT2, + MAX_TREE_CODES + }; + #undef DEFTREECODE + + #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM, + enum built_in_function { + #include "builtins.def" + END_BUILTINS + }; + #undef DEF_BUILTIN + + + /* Base class for all identifiers the parser knows. */ + + struct id_base : typed_noop_remove<id_base> + { + enum id_kind { CODE, FN, PREDICATE, USER } kind; + + id_base (id_kind, const char *, int = -1); + + hashval_t hashval; + int nargs; + const char *id; + + /* hash_table support. */ + typedef id_base value_type; + typedef id_base compare_type; + static inline hashval_t hash (const value_type *); + static inline int equal (const value_type *, const compare_type *); + }; + + inline hashval_t + id_base::hash (const value_type *op) + { + return op->hashval; + } + + inline int + id_base::equal (const value_type *op1, + const compare_type *op2) + { + return (op1->hashval == op2->hashval + && strcmp (op1->id, op2->id) == 0); + } + + /* Hashtable of known pattern operators. This is pre-seeded from + all known tree codes and all known builtin function ids. */ + static hash_table<id_base> *operators; + + id_base::id_base (id_kind kind_, const char *id_, int nargs_) + { + kind = kind_; + id = id_; + nargs = nargs_; + hashval = htab_hash_string (id); + } + + /* Identifier that maps to a tree code. */ + + struct operator_id : public id_base + { + operator_id (enum tree_code code_, const char *id_, unsigned nargs_, + const char *tcc_) + : id_base (id_base::CODE, id_, nargs_), code (code_), tcc (tcc_) {} + enum tree_code code; + const char *tcc; + }; + + /* Identifier that maps to a builtin function code. */ + + struct fn_id : public id_base + { + fn_id (enum built_in_function fn_, const char *id_) + : id_base (id_base::FN, id_), fn (fn_) {} + enum built_in_function fn; + }; + + struct simplify; + + /* Identifier that maps to a user-defined predicate. */ + + struct predicate_id : public id_base + { + predicate_id (const char *id_) + : id_base (id_base::PREDICATE, id_), matchers (vNULL) {} + vec<simplify *> matchers; + }; + + /* Identifier that maps to a operator defined by a 'for' directive. */ + + struct user_id : public id_base + { + user_id (const char *id_) + : id_base (id_base::USER, id_), substitutes (vNULL) {} + vec<id_base *> substitutes; + }; + + template<> + template<> + inline bool + is_a_helper <fn_id *>::test (id_base *id) + { + return id->kind == id_base::FN; + } + + template<> + template<> + inline bool + is_a_helper <operator_id *>::test (id_base *id) + { + return id->kind == id_base::CODE; + } + + template<> + template<> + inline bool + is_a_helper <predicate_id *>::test (id_base *id) + { + return id->kind == id_base::PREDICATE; + } + + template<> + template<> + inline bool + is_a_helper <user_id *>::test (id_base *id) + { + return id->kind == id_base::USER; + } + + /* Add a predicate identifier to the hash. */ + + static predicate_id * + add_predicate (const char *id) + { + predicate_id *p = new predicate_id (id); + id_base **slot = operators->find_slot_with_hash (p, p->hashval, INSERT); + if (*slot) + fatal ("duplicate id definition"); + *slot = p; + return p; + } + + /* Add a tree code identifier to the hash. */ + + static void + add_operator (enum tree_code code, const char *id, + const char *tcc, unsigned nargs) + { + if (strcmp (tcc, "tcc_unary") != 0 + && strcmp (tcc, "tcc_binary") != 0 + && strcmp (tcc, "tcc_comparison") != 0 + && strcmp (tcc, "tcc_expression") != 0 + /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */ + && strcmp (tcc, "tcc_reference") != 0 + /* To have INTEGER_CST and friends as "predicate operators". */ + && strcmp (tcc, "tcc_constant") != 0) + return; + operator_id *op = new operator_id (code, id, nargs, tcc); + id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT); + if (*slot) + fatal ("duplicate id definition"); + *slot = op; + } + + /* Add a builtin identifier to the hash. */ + + static void + add_builtin (enum built_in_function code, const char *id) + { + fn_id *fn = new fn_id (code, id); + id_base **slot = operators->find_slot_with_hash (fn, fn->hashval, INSERT); + if (*slot) + fatal ("duplicate id definition"); + *slot = fn; + } + + /* Helper for easy comparing ID with tree code CODE. */ + + static bool + operator==(id_base &id, enum tree_code code) + { + if (operator_id *oid = dyn_cast <operator_id *> (&id)) + return oid->code == code; + return false; + } + + /* Lookup the identifier ID. */ + + id_base * + get_operator (const char *id) + { + id_base tem (id_base::CODE, id); + + id_base *op = operators->find_with_hash (&tem, tem.hashval); + if (op) + return op; + + /* Try all-uppercase. */ + char *id2 = xstrdup (id); + for (unsigned i = 0; i < strlen (id2); ++i) + id2[i] = TOUPPER (id2[i]); + new (&tem) id_base (id_base::CODE, id2); + op = operators->find_with_hash (&tem, tem.hashval); + if (op) + { + free (id2); + return op; + } + + /* Try _EXPR appended. */ + id2 = (char *)xrealloc (id2, strlen (id2) + sizeof ("_EXPR") + 1); + strcat (id2, "_EXPR"); + new (&tem) id_base (id_base::CODE, id2); + op = operators->find_with_hash (&tem, tem.hashval); + if (op) + { + free (id2); + return op; + } + + return 0; + } + + + + /* The AST produced by parsing of the pattern definitions. */ + + struct dt_operand; + + /* The base class for operands. */ + + struct operand { + enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR }; + operand (enum op_type type_) : type (type_) {} + enum op_type type; + virtual void gen_transform (FILE *, const char *, bool, int, + const char *, dt_operand ** = 0) + { gcc_unreachable (); } + }; + + /* A predicate operand. Predicates are leafs in the AST. */ + + struct predicate : public operand + { + predicate (predicate_id *p_) : operand (OP_PREDICATE), p (p_) {} + predicate_id *p; + }; + + /* An operand that constitutes an expression. Expressions include + function calls and user-defined predicate invocations. */ + + struct expr : public operand + { + expr (id_base *operation_, bool is_commutative_ = false) + : operand (OP_EXPR), operation (operation_), + ops (vNULL), expr_type (NULL), is_commutative (is_commutative_) {} + void append_op (operand *op) { ops.safe_push (op); } + /* The operator and its operands. */ + id_base *operation; + vec<operand *> ops; + /* An explicitely specified type - used exclusively for conversions. */ + const char *expr_type; + /* Whether the operation is to be applied commutatively. This is + later lowered to two separate patterns. */ + bool is_commutative; + virtual void gen_transform (FILE *f, const char *, bool, int, + const char *, dt_operand ** = 0); + }; + + /* An operator that is represented by native C code. This is always + a leaf operand in the AST. This class is also used to represent + the code to be generated for 'if' and 'with' expressions. */ + + struct c_expr : public operand + { + /* A mapping of an identifier and its replacement. Used to apply + 'for' lowering. */ + struct id_tab { + const char *id; + const char *oper; + id_tab (const char *id_, const char *oper_): id (id_), oper (oper_) {} + }; + + c_expr (cpp_reader *r_, vec<cpp_token> code_, unsigned nr_stmts_, + vec<id_tab> ids_, std::map<std::string, unsigned> *capture_ids_) + : operand (OP_C_EXPR), r (r_), code (code_), capture_ids (capture_ids_), + nr_stmts (nr_stmts_), ids (ids_) {} + /* cpplib tokens and state to transform this back to source. */ + cpp_reader *r; + vec<cpp_token> code; + std::map<std::string, unsigned> *capture_ids; + /* The number of statements parsed (well, the number of ';'s). */ + unsigned nr_stmts; + /* The identifier replacement vector. */ + vec<id_tab> ids; + virtual void gen_transform (FILE *f, const char *, bool, int, + const char *, dt_operand **); + }; + + /* A wrapper around another operand that captures its value. */ + + struct capture : public operand + { + capture (unsigned where_, operand *what_) + : operand (OP_CAPTURE), where (where_), what (what_) {} + /* Identifier index for the value. */ + unsigned where; + /* The captured value. */ + operand *what; + virtual void gen_transform (FILE *f, const char *, bool, int, + const char *, dt_operand ** = 0); + }; + + template<> + template<> + inline bool + is_a_helper <capture *>::test (operand *op) + { + return op->type == operand::OP_CAPTURE; + } + + template<> + template<> + inline bool + is_a_helper <predicate *>::test (operand *op) + { + return op->type == operand::OP_PREDICATE; + } + + template<> + template<> + inline bool + is_a_helper <c_expr *>::test (operand *op) + { + return op->type == operand::OP_C_EXPR; + } + + template<> + template<> + inline bool + is_a_helper <expr *>::test (operand *op) + { + return op->type == operand::OP_EXPR; + } + + /* Helper to distinguish 'if' from 'with' expressions. */ + + struct if_or_with + { + if_or_with (operand *cexpr_, source_location location_, bool is_with_) + : location (location_), cexpr (cexpr_), is_with (is_with_) {} + source_location location; + operand *cexpr; + bool is_with; + }; + + /* The main class of a pattern and its transform. This is used to + represent both (simplify ...) and (match ...) kinds. The AST + duplicates all outer 'if' and 'for' expressions here so each + simplify can exist in isolation. */ + + struct simplify + { + simplify (operand *match_, source_location match_location_, + struct operand *result_, source_location result_location_, + vec<if_or_with> ifexpr_vec_, vec<vec<user_id *> > for_vec_, + std::map<std::string, unsigned> *capture_ids_) + : match (match_), match_location (match_location_), + result (result_), result_location (result_location_), + ifexpr_vec (ifexpr_vec_), for_vec (for_vec_), + capture_ids (capture_ids_), capture_max (capture_ids_->size ()) {} + + /* The expression that is matched against the GENERIC or GIMPLE IL. */ + operand *match; + source_location match_location; + /* For a (simplify ...) the expression produced when the pattern applies. + For a (match ...) either NULL if it is a simple predicate or the + single expression specifying the matched operands. */ + struct operand *result; + source_location result_location; + /* Collected 'if' expressions that need to evaluate to true to make + the pattern apply. */ + vec<if_or_with> ifexpr_vec; + /* Collected 'for' expression operators that have to be replaced + in the lowering phase. */ + vec<vec<user_id *> > for_vec; + /* A map of capture identifiers to indexes. */ + std::map<std::string, unsigned> *capture_ids; + int capture_max; + }; + + /* Debugging routines for dumping the AST. */ + + DEBUG_FUNCTION void + print_operand (operand *o, FILE *f = stderr, bool flattened = false) + { + if (capture *c = dyn_cast<capture *> (o)) + { + fprintf (f, "@%u", c->where); + if (c->what && flattened == false) + { + putc (':', f); + print_operand (c->what, f, flattened); + putc (' ', f); + } + } + + else if (predicate *p = dyn_cast<predicate *> (o)) + fprintf (f, "%s", p->p->id); + + else if (is_a<c_expr *> (o)) + fprintf (f, "c_expr"); + + else if (expr *e = dyn_cast<expr *> (o)) + { + fprintf (f, "(%s", e->operation->id); + + if (flattened == false) + { + putc (' ', f); + for (unsigned i = 0; i < e->ops.length (); ++i) + { + print_operand (e->ops[i], f, flattened); + putc (' ', f); + } + } + putc (')', f); + } + + else + gcc_unreachable (); + } + + DEBUG_FUNCTION void + print_matches (struct simplify *s, FILE *f = stderr) + { + fprintf (f, "for expression: "); + print_operand (s->match, f); + putc ('\n', f); + } + + + /* AST lowering. */ + + /* Lowering of commutative operators. */ + + static void + cartesian_product (const vec< vec<operand *> >& ops_vector, + vec< vec<operand *> >& result, vec<operand *>& v, unsigned n) + { + if (n == ops_vector.length ()) + { + vec<operand *> xv = v.copy (); + result.safe_push (xv); + return; + } + + for (unsigned i = 0; i < ops_vector[n].length (); ++i) + { + v[n] = ops_vector[n][i]; + cartesian_product (ops_vector, result, v, n + 1); + } + } + + /* Lower OP to two operands in case it is marked as commutative. */ + + static vec<operand *> + commutate (operand *op) + { + vec<operand *> ret = vNULL; + + if (capture *c = dyn_cast <capture *> (op)) + { + if (!c->what) + { + ret.safe_push (op); + return ret; + } + vec<operand *> v = commutate (c->what); + for (unsigned i = 0; i < v.length (); ++i) + { + capture *nc = new capture (c->where, v[i]); + ret.safe_push (nc); + } + return ret; + } + + expr *e = dyn_cast <expr *> (op); + if (!e || e->ops.length () == 0) + { + ret.safe_push (op); + return ret; + } + + vec< vec<operand *> > ops_vector = vNULL; + for (unsigned i = 0; i < e->ops.length (); ++i) + ops_vector.safe_push (commutate (e->ops[i])); + + auto_vec< vec<operand *> > result; + auto_vec<operand *> v (e->ops.length ()); + v.quick_grow_cleared (e->ops.length ()); + cartesian_product (ops_vector, result, v, 0); + + + for (unsigned i = 0; i < result.length (); ++i) + { + expr *ne = new expr (e->operation); + for (unsigned j = 0; j < result[i].length (); ++j) + ne->append_op (result[i][j]); + ret.safe_push (ne); + } + + if (!e->is_commutative) + return ret; + + for (unsigned i = 0; i < result.length (); ++i) + { + expr *ne = new expr (e->operation); + // result[i].length () is 2 since e->operation is binary + for (unsigned j = result[i].length (); j; --j) + ne->append_op (result[i][j-1]); + ret.safe_push (ne); + } + + return ret; + } + + /* Lower operations marked as commutative in the AST of S and push + the resulting patterns to SIMPLIFIERS. */ + + static void + lower_commutative (simplify *s, vec<simplify *>& simplifiers) + { + vec<operand *> matchers = commutate (s->match); + for (unsigned i = 0; i < matchers.length (); ++i) + { + simplify *ns = new simplify (matchers[i], s->match_location, + s->result, s->result_location, s->ifexpr_vec, + s->for_vec, s->capture_ids); + simplifiers.safe_push (ns); + } + } + + /* Strip conditional conversios using operator OPER from O and its + children if STRIP, else replace them with an unconditional convert. */ + + operand * + lower_opt_convert (operand *o, enum tree_code oper, bool strip) + { + if (capture *c = dyn_cast<capture *> (o)) + { + if (c->what) + return new capture (c->where, lower_opt_convert (c->what, oper, strip)); + else + return c; + } + + expr *e = dyn_cast<expr *> (o); + if (!e) + return o; + + if (*e->operation == oper) + { + if (strip) + return lower_opt_convert (e->ops[0], oper, strip); + + expr *ne = new expr (get_operator ("CONVERT_EXPR")); + ne->append_op (lower_opt_convert (e->ops[0], oper, strip)); + return ne; + } + + expr *ne = new expr (e->operation, e->is_commutative); + for (unsigned i = 0; i < e->ops.length (); ++i) + ne->append_op (lower_opt_convert (e->ops[i], oper, strip)); + + return ne; + } + + /* Determine whether O or its children uses the conditional conversion + operator OPER. */ + + static bool + has_opt_convert (operand *o, enum tree_code oper) + { + if (capture *c = dyn_cast<capture *> (o)) + { + if (c->what) + return has_opt_convert (c->what, oper); + else + return false; + } + + expr *e = dyn_cast<expr *> (o); + if (!e) + return false; + + if (*e->operation == oper) + return true; + + for (unsigned i = 0; i < e->ops.length (); ++i) + if (has_opt_convert (e->ops[i], oper)) + return true; + + return false; + } + + /* Lower conditional convert operators in O, expanding it to a vector + if required. */ + + static vec<operand *> + lower_opt_convert (operand *o) + { + vec<operand *> v1 = vNULL, v2; + + v1.safe_push (o); + + enum tree_code opers[] = { CONVERT0, CONVERT1, CONVERT2 }; + + /* Conditional converts are lowered to a pattern with the + conversion and one without. The three different conditional + convert codes are lowered separately. */ + + for (unsigned i = 0; i < 3; ++i) + { + v2 = vNULL; + for (unsigned j = 0; j < v1.length (); ++j) + if (has_opt_convert (v1[j], opers[i])) + { + v2.safe_push (lower_opt_convert (v1[j], opers[i], false)); + v2.safe_push (lower_opt_convert (v1[j], opers[i], true)); + } + + if (v2 != vNULL) + { + v1 = vNULL; + for (unsigned j = 0; j < v2.length (); ++j) + v1.safe_push (v2[j]); + } + } + + return v1; + } + + /* Lower conditional convert operators in the AST of S and push + the resulting multiple patterns to SIMPLIFIERS. */ + + static void + lower_opt_convert (simplify *s, vec<simplify *>& simplifiers) + { + vec<operand *> matchers = lower_opt_convert (s->match); + for (unsigned i = 0; i < matchers.length (); ++i) + { + simplify *ns = new simplify (matchers[i], s->match_location, + s->result, s->result_location, s->ifexpr_vec, + s->for_vec, s->capture_ids); + simplifiers.safe_push (ns); + } + } + + /* In AST operand O replace operator ID with operator WITH. */ + + operand * + replace_id (operand *o, user_id *id, id_base *with) + { + /* Deep-copy captures and expressions, replacing operations as + needed. */ + if (capture *c = dyn_cast<capture *> (o)) + { + if (!c->what) + return c; + return new capture (c->where, replace_id (c->what, id, with)); + } + else if (expr *e = dyn_cast<expr *> (o)) + { + expr *ne = new expr (e->operation == id ? with : e->operation, + e->is_commutative); + for (unsigned i = 0; i < e->ops.length (); ++i) + ne->append_op (replace_id (e->ops[i], id, with)); + return ne; + } + + /* For c_expr we simply record a string replacement table which is + applied at code-generation time. */ + if (c_expr *ce = dyn_cast<c_expr *> (o)) + { + vec<c_expr::id_tab> ids = ce->ids.copy (); + ids.safe_push (c_expr::id_tab (id->id, with->id)); + return new c_expr (ce->r, ce->code, ce->nr_stmts, ids, ce->capture_ids); + } + + return o; + } + + /* Lower recorded fors for SIN and output to SIMPLIFIERS. */ + + static void + lower_for (simplify *sin, vec<simplify *>& simplifiers) + { + vec<vec<user_id *> >& for_vec = sin->for_vec; + unsigned worklist_start = 0; + auto_vec<simplify *> worklist; + worklist.safe_push (sin); + + /* Lower each recorded for separately, operating on the + set of simplifiers created by the previous one. + Lower inner-to-outer so inner for substitutes can refer + to operators replaced by outer fors. */ + for (int fi = for_vec.length () - 1; fi >= 0; --fi) + { + vec<user_id *>& ids = for_vec[fi]; + unsigned n_ids = ids.length (); + unsigned max_n_opers = 0; + for (unsigned i = 0; i < n_ids; ++i) + if (ids[i]->substitutes.length () > max_n_opers) + max_n_opers = ids[i]->substitutes.length (); + + unsigned worklist_end = worklist.length (); + for (unsigned si = worklist_start; si < worklist_end; ++si) + { + simplify *s = worklist[si]; + for (unsigned j = 0; j < max_n_opers; ++j) + { + operand *match_op = s->match; + operand *result_op = s->result; + vec<if_or_with> ifexpr_vec = s->ifexpr_vec.copy (); + + for (unsigned i = 0; i < n_ids; ++i) + { + user_id *id = ids[i]; + id_base *oper = id->substitutes[j % id->substitutes.length ()]; + match_op = replace_id (match_op, id, oper); + if (result_op) + result_op = replace_id (result_op, id, oper); + for (unsigned k = 0; k < s->ifexpr_vec.length (); ++k) + ifexpr_vec[k].cexpr = replace_id (ifexpr_vec[k].cexpr, + id, oper); + } + simplify *ns = new simplify (match_op, s->match_location, + result_op, s->result_location, + ifexpr_vec, vNULL, s->capture_ids); + worklist.safe_push (ns); + } + } + worklist_start = worklist_end; + } + + /* Copy out the result from the last for lowering. */ + for (unsigned i = worklist_start; i < worklist.length (); ++i) + simplifiers.safe_push (worklist[i]); + } + + /* Lower the AST for everything in SIMPLIFIERS. */ + + static void + lower (vec<simplify *>& simplifiers) + { + auto_vec<simplify *> out_simplifiers0; + for (unsigned i = 0; i < simplifiers.length (); ++i) + lower_opt_convert (simplifiers[i], out_simplifiers0); + + auto_vec<simplify *> out_simplifiers1; + for (unsigned i = 0; i < out_simplifiers0.length (); ++i) + lower_commutative (out_simplifiers0[i], out_simplifiers1); + + simplifiers.truncate (0); + for (unsigned i = 0; i < out_simplifiers1.length (); ++i) + lower_for (out_simplifiers1[i], simplifiers); + } + + + + + /* The decision tree built for generating GIMPLE and GENERIC pattern + matching code. It represents the 'match' expression of all + simplifies and has those as its leafs. */ + + /* Decision tree base class, used for DT_TRUE and DT_NODE. */ + + struct dt_node + { + enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY }; + + enum dt_type type; + unsigned level; + vec<dt_node *> kids; + + dt_node (enum dt_type type_): type (type_), level (0), kids (vNULL) {} + + dt_node *append_node (dt_node *); + dt_node *append_op (operand *, dt_node *parent = 0, unsigned pos = 0); + dt_node *append_true_op (dt_node *parent = 0, unsigned pos = 0); + dt_node *append_match_op (dt_operand *, dt_node *parent = 0, unsigned pos = 0); + dt_node *append_simplify (simplify *, unsigned, dt_operand **); + + virtual void gen (FILE *, bool) {} + + void gen_kids (FILE *, bool); + }; + + /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */ + + struct dt_operand : public dt_node + { + operand *op; + dt_operand *match_dop; + dt_operand *parent; + unsigned pos; + + dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_, + dt_operand *parent_ = 0, unsigned pos_ = 0) + : dt_node (type), op (op_), match_dop (match_dop_), + parent (parent_), pos (pos_) {} + + void gen (FILE *, bool); + unsigned gen_predicate (FILE *, const char *, bool); + unsigned gen_match_op (FILE *, const char *); + + unsigned gen_gimple_expr (FILE *); + unsigned gen_generic_expr (FILE *, const char *); + + char *get_name (char *); + void gen_opname (char *, unsigned); + }; + + /* Leaf node of the decision tree, used for DT_SIMPLIFY. */ + + struct dt_simplify : public dt_node + { + simplify *s; + unsigned pattern_no; + dt_operand **indexes; + + dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_) + : dt_node (DT_SIMPLIFY), s (s_), pattern_no (pattern_no_), + indexes (indexes_) {} + + void gen (FILE *f, bool); + }; + + template<> + template<> + inline bool + is_a_helper <dt_operand *>::test (dt_node *n) + { + return (n->type == dt_node::DT_OPERAND + || n->type == dt_node::DT_MATCH); + } + + /* A container for the actual decision tree. */ + + struct decision_tree + { + dt_node *root; + + void insert (struct simplify *, unsigned); + void gen_gimple (FILE *f = stderr); + void gen_generic (FILE *f = stderr); + void print (FILE *f = stderr); + + decision_tree () { root = new dt_node (dt_node::DT_NODE); } + + static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes, + unsigned pos = 0, dt_node *parent = 0); + static dt_node *find_node (vec<dt_node *>&, dt_node *); + static bool cmp_node (dt_node *, dt_node *); + static void print_node (dt_node *, FILE *f = stderr, unsigned = 0); + }; + + /* Compare two AST operands O1 and O2 and return true if they are equal. */ + + bool + cmp_operand (operand *o1, operand *o2) + { + if (!o1 || !o2 || o1->type != o2->type) + return false; + + if (o1->type == operand::OP_PREDICATE) + { + predicate *p1 = as_a<predicate *>(o1); + predicate *p2 = as_a<predicate *>(o2); + return p1->p == p2->p; + } + else if (o1->type == operand::OP_EXPR) + { + expr *e1 = static_cast<expr *>(o1); + expr *e2 = static_cast<expr *>(o2); + return e1->operation == e2->operation; + } + else + return false; + } + + /* Compare two decision tree nodes N1 and N2 and return true if they + are equal. */ + + bool + decision_tree::cmp_node (dt_node *n1, dt_node *n2) + { + if (!n1 || !n2 || n1->type != n2->type) + return false; + + if (n1 == n2 || n1->type == dt_node::DT_TRUE) + return true; + + if (n1->type == dt_node::DT_OPERAND) + return cmp_operand ((as_a<dt_operand *> (n1))->op, + (as_a<dt_operand *> (n2))->op); + else if (n1->type == dt_node::DT_MATCH) + return ((as_a<dt_operand *> (n1))->match_dop + == (as_a<dt_operand *> (n2))->match_dop); + return false; + } + + /* Search OPS for a decision tree node like P and return it if found. */ + + dt_node * + decision_tree::find_node (vec<dt_node *>& ops, dt_node *p) + { + for (unsigned i = 0; i < ops.length (); ++i) + if (decision_tree::cmp_node (ops[i], p)) + return ops[i]; + + return NULL; + } + + /* Append N to the decision tree if it there is not already an existing + identical child. */ + + dt_node * + dt_node::append_node (dt_node *n) + { + dt_node *kid; + + kid = decision_tree::find_node (kids, n); + if (kid) + return kid; + + kids.safe_push (n); + n->level = this->level + 1; + + unsigned len = kids.length (); + + if (len > 1 && kids[len - 2]->type == dt_node::DT_TRUE) + { + dt_node *p = kids[len - 2]; + kids[len - 2] = kids[len - 1]; + kids[len - 1] = p; + } + + return n; + } + + /* Append OP to the decision tree. */ + + dt_node * + dt_node::append_op (operand *op, dt_node *parent, unsigned pos) + { + dt_operand *parent_ = safe_as_a<dt_operand *> (parent); + dt_operand *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos); + return append_node (n); + } + + /* Append a DT_TRUE decision tree node. */ + + dt_node * + dt_node::append_true_op (dt_node *parent, unsigned pos) + { + dt_operand *parent_ = as_a<dt_operand *> (parent); + dt_operand *n = new dt_operand (DT_TRUE, 0, 0, parent_, pos); + return append_node (n); + } + + /* Append a DT_MATCH decision tree node. */ + + dt_node * + dt_node::append_match_op (dt_operand *match_dop, dt_node *parent, unsigned pos) + { + dt_operand *parent_ = as_a<dt_operand *> (parent); + dt_operand *n = new dt_operand (DT_MATCH, 0, match_dop, parent_, pos); + return append_node (n); + } + + /* Append S to the decision tree. */ + + dt_node * + dt_node::append_simplify (simplify *s, unsigned pattern_no, + dt_operand **indexes) + { + dt_simplify *n = new dt_simplify (s, pattern_no, indexes); + return append_node (n); + } + + /* Insert O into the decision tree and return the decision tree node found + or created. */ + + dt_node * + decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes, + unsigned pos, dt_node *parent) + { + dt_node *q, *elm = 0; + + if (capture *c = dyn_cast<capture *> (o)) + { + unsigned capt_index = c->where; + + if (indexes[capt_index] == 0) + { + if (c->what) + q = insert_operand (p, c->what, indexes, pos, parent); + else + { + q = elm = p->append_true_op (parent, pos); + goto at_assert_elm; + } + // get to the last capture + for (operand *what = c->what; + what && is_a<capture *> (what); + c = as_a<capture *> (what), what = c->what) + ; + + if (!c->what) + { + unsigned cc_index = c->where; + dt_operand *match_op = indexes[cc_index]; + + dt_operand temp (dt_node::DT_TRUE, 0, 0); + elm = decision_tree::find_node (p->kids, &temp); + + if (elm == 0) + { + dt_operand temp (dt_node::DT_MATCH, 0, match_op); + elm = decision_tree::find_node (p->kids, &temp); + } + } + else + { + dt_operand temp (dt_node::DT_OPERAND, c->what, 0); + elm = decision_tree::find_node (p->kids, &temp); + } + + at_assert_elm: + gcc_assert (elm->type == dt_node::DT_TRUE + || elm->type == dt_node::DT_OPERAND + || elm->type == dt_node::DT_MATCH); + indexes[capt_index] = static_cast<dt_operand *> (elm); + return q; + } + else + { + p = p->append_match_op (indexes[capt_index], parent, pos); + if (c->what) + return insert_operand (p, c->what, indexes, 0, p); + else + return p; + } + } + p = p->append_op (o, parent, pos); + q = p; + + if (expr *e = dyn_cast <expr *>(o)) + { + for (unsigned i = 0; i < e->ops.length (); ++i) + q = decision_tree::insert_operand (q, e->ops[i], indexes, i, p); + } + + return q; + } + + /* Insert S into the decision tree. */ + + void + decision_tree::insert (struct simplify *s, unsigned pattern_no) + { + if (s->match->type != operand::OP_EXPR) + return; + + dt_operand **indexes = XCNEWVEC (dt_operand *, s->capture_max + 1); + dt_node *p = decision_tree::insert_operand (root, s->match, indexes); + p->append_simplify (s, pattern_no, indexes); + } + + /* Debug functions to dump the decision tree. */ + + DEBUG_FUNCTION void + decision_tree::print_node (dt_node *p, FILE *f, unsigned indent) + { + if (p->type == dt_node::DT_NODE) + fprintf (f, "root"); + else + { + fprintf (f, "|"); + for (unsigned i = 0; i < indent; i++) + fprintf (f, "-"); + + if (p->type == dt_node::DT_OPERAND) + { + dt_operand *dop = static_cast<dt_operand *>(p); + print_operand (dop->op, f, true); + } + else if (p->type == dt_node::DT_TRUE) + fprintf (f, "true"); + else if (p->type == dt_node::DT_MATCH) + fprintf (f, "match (%p)", (void *)((as_a<dt_operand *>(p))->match_dop)); + else if (p->type == dt_node::DT_SIMPLIFY) + { + dt_simplify *s = static_cast<dt_simplify *> (p); + fprintf (f, "simplify_%u { ", s->pattern_no); + for (int i = 0; i <= s->s->capture_max; ++i) + fprintf (f, "%p, ", (void *) s->indexes[i]); + fprintf (f, " } "); + } + } + + fprintf (stderr, " (%p), %u, %u\n", (void *) p, p->level, p->kids.length ()); + + for (unsigned i = 0; i < p->kids.length (); ++i) + decision_tree::print_node (p->kids[i], f, indent + 2); + } + + DEBUG_FUNCTION void + decision_tree::print (FILE *f) + { + return decision_tree::print_node (root, f); + } + + + + /* Code generation off the decision tree and the refered AST nodes. */ + + bool + is_conversion (id_base *op) + { + return (*op == CONVERT_EXPR + || *op == NOP_EXPR + || *op == FLOAT_EXPR + || *op == FIX_TRUNC_EXPR + || *op == VIEW_CONVERT_EXPR); + } + + /* Get the type to be used for generating operands of OP from the + various sources. */ + + static const char * + get_operand_type (id_base *op, const char *in_type, + const char *expr_type, + const char *other_oprnd_type) + { + /* Generally operands whose type does not match the type of the + expression generated need to know their types but match and + thus can fall back to 'other_oprnd_type'. */ + if (is_conversion (op)) + return other_oprnd_type; + else if (*op == REALPART_EXPR + || *op == IMAGPART_EXPR) + return other_oprnd_type; + else if (is_a <operator_id *> (op) + && strcmp (as_a <operator_id *> (op)->tcc, "tcc_comparison") == 0) + return other_oprnd_type; + else + { + /* Otherwise all types should match - choose one in order of + preference. */ + if (expr_type) + return expr_type; + else if (in_type) + return in_type; + else + return other_oprnd_type; + } + } + + /* Generate transform code for an expression. */ + + void + expr::gen_transform (FILE *f, const char *dest, bool gimple, int depth, + const char *in_type, dt_operand **indexes) + { + bool conversion_p = is_conversion (operation); + const char *type = expr_type; + char optype[64]; + if (type) + /* If there was a type specification in the pattern use it. */ + ; + else if (conversion_p) + /* For conversions we need to build the expression using the + outer type passed in. */ + type = in_type; + else if (*operation == REALPART_EXPR + || *operation == IMAGPART_EXPR) + { + /* __real and __imag use the component type of its operand. */ + sprintf (optype, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth); + type = optype; + } + else if (is_a <operator_id *> (operation) + && !strcmp (as_a <operator_id *> (operation)->tcc, "tcc_comparison")) + { + /* comparisons use boolean_type_node (or what gets in), but + their operands need to figure out the types themselves. */ + sprintf (optype, "boolean_type_node"); + type = optype; + } + else + { + /* Other operations are of the same type as their first operand. */ + sprintf (optype, "TREE_TYPE (ops%d[0])", depth); + type = optype; + } + if (!type) + fatal ("two conversions in a row"); + + fprintf (f, "{\n"); + fprintf (f, " tree ops%d[%u], res;\n", depth, ops.length ()); + char op0type[64]; + snprintf (op0type, 64, "TREE_TYPE (ops%d[0])", depth); + for (unsigned i = 0; i < ops.length (); ++i) + { + char dest[32]; + snprintf (dest, 32, " ops%d[%u]", depth, i); + const char *optype + = get_operand_type (operation, in_type, expr_type, + i == 0 ? NULL : op0type); + ops[i]->gen_transform (f, dest, gimple, depth + 1, optype, indexes); + } + + if (gimple) + { + /* ??? Have another helper that is like gimple_build but may + fail if seq == NULL. */ + fprintf (f, " if (!seq)\n" + " {\n" + " res = gimple_simplify (%s, %s", + operation->id, type); + for (unsigned i = 0; i < ops.length (); ++i) + fprintf (f, ", ops%d[%u]", depth, i); + fprintf (f, ", seq, valueize);\n"); + fprintf (f, " if (!res) return false;\n"); + fprintf (f, " }\n"); + fprintf (f, " else\n"); + fprintf (f, " res = gimple_build (seq, UNKNOWN_LOCATION, %s, %s", + operation->id, type); + for (unsigned i = 0; i < ops.length (); ++i) + fprintf (f, ", ops%d[%u]", depth, i); + fprintf (f, ", valueize);\n"); + } + else + { + if (operation->kind == id_base::CODE) + fprintf (f, " res = fold_build%d (%s, %s", + ops.length(), operation->id, type); + else + fprintf (f, " res = build_call_expr (builtin_decl_implicit (%s), %d", + operation->id, ops.length()); + for (unsigned i = 0; i < ops.length (); ++i) + fprintf (f, ", ops%d[%u]", depth, i); + fprintf (f, ");\n"); + } + fprintf (f, " %s = res;\n", dest); + fprintf (f, "}\n"); + } + + /* Generate code for a c_expr which is either the expression inside + an if statement or a sequence of statements which computes a + result to be stored to DEST. */ + + void + c_expr::gen_transform (FILE *f, const char *dest, + bool, int, const char *, dt_operand **) + { + if (dest && nr_stmts == 1) + fprintf (f, "%s = ", dest); + + unsigned stmt_nr = 1; + for (unsigned i = 0; i < code.length (); ++i) + { + const cpp_token *token = &code[i]; + + /* Replace captures for code-gen. */ + if (token->type == CPP_ATSIGN) + { + const cpp_token *n = &code[i+1]; + if ((n->type == CPP_NUMBER + || n->type == CPP_NAME) + && !(n->flags & PREV_WHITE)) + { + if (token->flags & PREV_WHITE) + fputc (' ', f); + const char *id; + if (n->type == CPP_NUMBER) + id = (const char *)n->val.str.text; + else + id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str; + fprintf (f, "captures[%u]", (*capture_ids)[id]); + ++i; + continue; + } + } + + if (token->flags & PREV_WHITE) + fputc (' ', f); + + if (token->type == CPP_NAME) + { + const char *id = (const char *) NODE_NAME (token->val.node.node); + unsigned j; + for (j = 0; j < ids.length (); ++j) + { + if (strcmp (id, ids[j].id) == 0) + { + fprintf (f, "%s", ids[j].oper); + break; + } + } + if (j < ids.length ()) + continue; + } + + /* Output the token as string. */ + char *tk = (char *)cpp_token_as_text (r, token); + fputs (tk, f); + + if (token->type == CPP_SEMICOLON) + { + stmt_nr++; + if (dest && stmt_nr == nr_stmts) + fprintf (f, "\n %s = ", dest); + else + fputc ('\n', f); + } + } + } + + /* Generate transform code for a capture. */ + + void + capture::gen_transform (FILE *f, const char *dest, bool gimple, int depth, + const char *in_type, dt_operand **indexes) + { + if (what && is_a<expr *> (what)) + { + if (indexes[where] == 0) + { + char buf[20]; + sprintf (buf, "captures[%u]", where); + what->gen_transform (f, buf, gimple, depth, in_type, NULL); + } + } + + fprintf (f, "%s = captures[%u];\n", dest, where); + } + + /* Return the name of the operand representing the decision tree node. + Use NAME as space to generate it. */ + + char * + dt_operand::get_name (char *name) + { + if (!parent) + sprintf (name, "t"); + else if (parent->level == 1) + sprintf (name, "op%u", pos); + else if (parent->type == dt_node::DT_MATCH) + return parent->get_name (name); + else + sprintf (name, "o%u%u", parent->level, pos); + return name; + } + + /* Fill NAME with the operand name at position POS. */ + + void + dt_operand::gen_opname (char *name, unsigned pos) + { + if (!parent) + sprintf (name, "op%u", pos); + else + sprintf (name, "o%u%u", level, pos); + } + + /* Generate matching code for the decision tree operand which is + a predicate. */ + + unsigned + dt_operand::gen_predicate (FILE *f, const char *opname, bool gimple) + { + predicate *p = as_a <predicate *> (op); + + if (p->p->matchers.exists ()) + { + /* If this is a predicate generated from a pattern mangle its + name and pass on the valueize hook. */ + if (gimple) + fprintf (f, "if (gimple_%s (%s, valueize))\n", p->p->id, opname); + else + fprintf (f, "if (tree_%s (%s))\n", p->p->id, opname); + } + else + fprintf (f, "if (%s (%s))\n", p->p->id, opname); + fprintf (f, "{\n"); + return 1; + } + + /* Generate matching code for the decision tree operand which is + a capture-match. */ + + unsigned + dt_operand::gen_match_op (FILE *f, const char *opname) + { + char match_opname[20]; + match_dop->get_name (match_opname); + fprintf (f, "if (%s == %s || operand_equal_p (%s, %s, 0))\n", + opname, match_opname, opname, match_opname); + fprintf (f, "{\n"); + return 1; + } + + /* Generate GIMPLE matching code for the decision tree operand. */ + + unsigned + dt_operand::gen_gimple_expr (FILE *f) + { + expr *e = static_cast<expr *> (op); + id_base *id = e->operation; + unsigned n_ops = e->ops.length (); + + for (unsigned i = 0; i < n_ops; ++i) + { + char child_opname[20]; + gen_opname (child_opname, i); + + if (id->kind == id_base::CODE) + { + if (*id == REALPART_EXPR || *id == IMAGPART_EXPR + || *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR) + { + /* ??? If this is a memory operation we can't (and should not) + match this. The only sensible operand types are + SSA names and invariants. */ + fprintf (f, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n", + child_opname, i); + fprintf (f, "if ((TREE_CODE (%s) == SSA_NAME\n" + "|| is_gimple_min_invariant (%s))\n" + "&& (%s = do_valueize (valueize, %s)))\n" + "{\n", child_opname, child_opname, child_opname, + child_opname); + continue; + } + else + fprintf (f, "tree %s = gimple_assign_rhs%u (def_stmt);\n", + child_opname, i + 1); + } + else + fprintf (f, "tree %s = gimple_call_arg (def_stmt, %u);\n", + child_opname, i); + fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", + child_opname, child_opname); + fprintf (f, "{\n"); + } + + return n_ops; + } + + /* Generate GENERIC matching code for the decision tree operand. */ + + unsigned + dt_operand::gen_generic_expr (FILE *f, const char *opname) + { + expr *e = static_cast<expr *> (op); + unsigned n_ops = e->ops.length (); + + for (unsigned i = 0; i < n_ops; ++i) + { + char child_opname[20]; + gen_opname (child_opname, i); + + if (e->operation->kind == id_base::CODE) + fprintf (f, "tree %s = TREE_OPERAND (%s, %u);\n", + child_opname, opname, i); + else + fprintf (f, "tree %s = CALL_EXPR_ARG (%s, %u);\n", + child_opname, opname, i); + } + + return 0; + } + + /* Generate matching code for the children of the decision tree node. */ + + void + dt_node::gen_kids (FILE *f, bool gimple) + { + auto_vec<dt_operand *> gimple_exprs; + auto_vec<dt_operand *> generic_exprs; + auto_vec<dt_operand *> fns; + auto_vec<dt_operand *> generic_fns; + auto_vec<dt_operand *> preds; + auto_vec<dt_node *> others; + dt_node *true_operand = NULL; + + for (unsigned i = 0; i < kids.length (); ++i) + { + if (kids[i]->type == dt_node::DT_OPERAND) + { + dt_operand *op = as_a<dt_operand *> (kids[i]); + if (expr *e = dyn_cast <expr *> (op->op)) + { + if (e->ops.length () == 0) + generic_exprs.safe_push (op); + else if (e->operation->kind == id_base::FN) + { + if (gimple) + fns.safe_push (op); + else + generic_fns.safe_push (op); + } + else if (e->operation->kind == id_base::PREDICATE) + preds.safe_push (op); + else + { + if (gimple) + gimple_exprs.safe_push (op); + else + generic_exprs.safe_push (op); + } + } + else if (op->op->type == operand::OP_PREDICATE) + others.safe_push (kids[i]); + else + gcc_unreachable (); + } + else if (kids[i]->type == dt_node::DT_MATCH + || kids[i]->type == dt_node::DT_SIMPLIFY) + others.safe_push (kids[i]); + else if (kids[i]->type == dt_node::DT_TRUE) + true_operand = kids[i]; + else + gcc_unreachable (); + } + + char buf[128]; + char *kid_opname = buf; + + unsigned exprs_len = gimple_exprs.length (); + unsigned gexprs_len = generic_exprs.length (); + unsigned fns_len = fns.length (); + unsigned gfns_len = generic_fns.length (); + + if (exprs_len || fns_len || gexprs_len || gfns_len) + { + if (exprs_len) + gimple_exprs[0]->get_name (kid_opname); + else if (fns_len) + fns[0]->get_name (kid_opname); + else if (gfns_len) + generic_fns[0]->get_name (kid_opname); + else + generic_exprs[0]->get_name (kid_opname); + + fprintf (f, "switch (TREE_CODE (%s))\n" + "{\n", kid_opname); + } + + if (exprs_len || fns_len) + { + fprintf (f, "case SSA_NAME:\n"); + fprintf (f, "{\n"); + fprintf (f, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname); + + if (exprs_len) + { + fprintf (f, "if (is_gimple_assign (def_stmt))\n"); + fprintf (f, "switch (gimple_assign_rhs_code (def_stmt))\n" + "{\n"); + for (unsigned i = 0; i < exprs_len; ++i) + { + expr *e = as_a <expr *> (gimple_exprs[i]->op); + id_base *op = e->operation; + if (*op == CONVERT_EXPR || *op == NOP_EXPR) + fprintf (f, "CASE_CONVERT:\n"); + else + fprintf (f, "case %s:\n", op->id); + fprintf (f, "{\n"); + gimple_exprs[i]->gen (f, true); + fprintf (f, "break;\n" + "}\n"); + } + fprintf (f, "default:;\n" + "}\n"); + } + + if (fns_len) + { + if (exprs_len) + fprintf (f, "else "); + + fprintf (f, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n" + "{\n" + "tree fndecl = gimple_call_fndecl (def_stmt);\n" + "switch (DECL_FUNCTION_CODE (fndecl))\n" + "{\n"); + + for (unsigned i = 0; i < fns_len; ++i) + { + expr *e = as_a <expr *>(fns[i]->op); + fprintf (f, "case %s:\n" + "{\n", e->operation->id); + fns[i]->gen (f, true); + fprintf (f, "break;\n" + "}\n"); + } + + fprintf (f, "default:;\n" + "}\n" + "}\n"); + } + + fprintf (f, "break;\n" + "}\n"); + } + + for (unsigned i = 0; i < generic_exprs.length (); ++i) + { + expr *e = as_a <expr *>(generic_exprs[i]->op); + id_base *op = e->operation; + if (*op == CONVERT_EXPR || *op == NOP_EXPR) + fprintf (f, "CASE_CONVERT:\n"); + else + fprintf (f, "case %s:\n", op->id); + fprintf (f, "{\n"); + generic_exprs[i]->gen (f, gimple); + fprintf (f, "break;\n" + "}\n"); + } + + if (gfns_len) + { + fprintf (f, "case CALL_EXPR:\n" + "{\n" + "tree fndecl = get_callee_fndecl (%s);\n" + "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n" + "switch (DECL_FUNCTION_CODE (fndecl))\n" + "{\n", kid_opname); + + for (unsigned j = 0; j < generic_fns.length (); ++j) + { + expr *e = as_a <expr *>(generic_fns[j]->op); + gcc_assert (e->operation->kind == id_base::FN); + + fprintf (f, "case %s:\n" + "{\n", e->operation->id); + generic_fns[j]->gen (f, false); + fprintf (f, "break;\n" + "}\n"); + } + + fprintf (f, "default:;\n" + "}\n" + "break;\n" + "}\n"); + } + + /* Close switch (TREE_CODE ()). */ + if (exprs_len || fns_len || gexprs_len || gfns_len) + fprintf (f, "default:;\n" + "}\n"); + + for (unsigned i = 0; i < preds.length (); ++i) + { + expr *e = as_a <expr *> (preds[i]->op); + predicate_id *p = as_a <predicate_id *> (e->operation); + preds[i]->get_name (kid_opname); + fprintf (f, "tree %s_pops[%d];\n", kid_opname, p->nargs); + fprintf (f, "if (%s_%s (%s, %s_pops%s))\n", + gimple ? "gimple" : "tree", + p->id, kid_opname, kid_opname, + gimple ? ", valueize" : ""); + fprintf (f, "{\n"); + for (int j = 0; j < p->nargs; ++j) + { + char child_opname[20]; + preds[i]->gen_opname (child_opname, j); + fprintf (f, "tree %s = %s_pops[%d];\n", child_opname, kid_opname, j); + } + preds[i]->gen_kids (f, gimple); + fprintf (f, "}\n"); + } + + for (unsigned i = 0; i < others.length (); ++i) + others[i]->gen (f, gimple); + + if (true_operand) + true_operand->gen (f, gimple); + } + + /* Generate matching code for the decision tree operand. */ + + void + dt_operand::gen (FILE *f, bool gimple) + { + char opname[20]; + get_name (opname); + + unsigned n_braces = 0; + + if (type == DT_OPERAND) + switch (op->type) + { + case operand::OP_PREDICATE: + n_braces = gen_predicate (f, opname, gimple); + break; + + case operand::OP_EXPR: + if (gimple) + n_braces = gen_gimple_expr (f); + else + n_braces = gen_generic_expr (f, opname); + break; + + default: + gcc_unreachable (); + } + else if (type == DT_TRUE) + ; + else if (type == DT_MATCH) + n_braces = gen_match_op (f, opname); + else + gcc_unreachable (); + + gen_kids (f, gimple); + + for (unsigned i = 0; i < n_braces; ++i) + fprintf (f, "}\n"); + } + + /* Generate code for the '(if ...)', '(with ..)' and actual transform + step of a '(simplify ...)' or '(match ...)'. This handles everything + that is not part of the decision tree (simplify->match). */ + + void + dt_simplify::gen (FILE *f, bool gimple) + { + fprintf (f, "{\n"); + output_line_directive (f, s->result_location); + if (s->capture_max >= 0) + fprintf (f, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n", + s->capture_max + 1); + + for (int i = 0; i <= s->capture_max; ++i) + if (indexes[i]) + { + char opname[20]; + fprintf (f, "captures[%u] = %s;\n", i, indexes[i]->get_name (opname)); + } + + unsigned n_braces = 0; + if (s->ifexpr_vec != vNULL) + { + for (unsigned i = 0; i < s->ifexpr_vec.length (); ++i) + { + if_or_with &w = s->ifexpr_vec[i]; + if (w.is_with) + { + fprintf (f, "{\n"); + output_line_directive (f, w.location); + w.cexpr->gen_transform (f, NULL, true, 1, "type"); + n_braces++; + } + else + { + output_line_directive (f, w.location); + fprintf (f, "if ("); + if (i == s->ifexpr_vec.length () - 1 + || s->ifexpr_vec[i+1].is_with) + w.cexpr->gen_transform (f, NULL, true, 1, "type"); + else + { + unsigned j = i; + do + { + if (j != i) + { + fprintf (f, "\n"); + output_line_directive (f, s->ifexpr_vec[j].location); + fprintf (f, "&& "); + } + fprintf (f, "("); + s->ifexpr_vec[j].cexpr->gen_transform (f, NULL, + true, 1, "type"); + fprintf (f, ")"); + ++j; + } + while (j < s->ifexpr_vec.length () + && !s->ifexpr_vec[j].is_with); + i = j - 1; + } + fprintf (f, ")\n"); + } + } + fprintf (f, "{\n"); + n_braces++; + } + + fprintf (f, "if (dump_file && (dump_flags & TDF_DETAILS)) " + "fprintf (dump_file, \"Applying pattern "); + output_line_directive (f, s->result_location, true); + fprintf (f, ", %%s:%%d\\n\", __FILE__, __LINE__);\n"); + + if (!s->result) + { + /* If there is no result then this is a predicate implementation. */ + fprintf (f, "return true;\n"); + } + else if (gimple) + { + if (s->result->type == operand::OP_EXPR) + { + expr *e = as_a <expr *> (s->result); + bool is_predicate = is_a <predicate_id *> (e->operation); + if (!is_predicate) + fprintf (f, "*res_code = %s;\n", e->operation->id); + for (unsigned j = 0; j < e->ops.length (); ++j) + { + char dest[32]; + snprintf (dest, 32, " res_ops[%d]", j); + const char *optype + = get_operand_type (e->operation, + "type", e->expr_type, + j == 0 + ? NULL : "TREE_TYPE (res_ops[0])"); + e->ops[j]->gen_transform (f, dest, true, 1, optype, indexes); + } + + /* Re-fold the toplevel result. It's basically an embedded + gimple_build w/o actually building the stmt. */ + if (!is_predicate) + fprintf (f, "gimple_resimplify%d (seq, res_code, type, " + "res_ops, valueize);\n", e->ops.length ()); + } + else if (s->result->type == operand::OP_CAPTURE + || s->result->type == operand::OP_C_EXPR) + { + s->result->gen_transform (f, "res_ops[0]", true, 1, "type", indexes); + fprintf (f, "*res_code = TREE_CODE (res_ops[0]);\n"); + } + else + gcc_unreachable (); + fprintf (f, "return true;\n"); + } + else /* GENERIC */ + { + if (s->result->type == operand::OP_EXPR) + { + expr *e = as_a <expr *> (s->result); + bool is_predicate = is_a <predicate_id *> (e->operation); + for (unsigned j = 0; j < e->ops.length (); ++j) + { + char dest[32]; + if (is_predicate) + snprintf (dest, 32, "res_ops[%d]", j); + else + { + fprintf (f, " tree res_op%d;\n", j); + snprintf (dest, 32, " res_op%d", j); + } + const char *optype + = get_operand_type (e->operation, + "type", e->expr_type, + j == 0 + ? NULL : "TREE_TYPE (res_op0)"); + e->ops[j]->gen_transform (f, dest, false, 1, optype, indexes); + } + if (is_a <predicate_id *> (e->operation)) + fprintf (f, "return true;\n"); + else + { + /* Re-fold the toplevel result. */ + if (e->operation->kind == id_base::CODE) + fprintf (f, " return fold_build%d (%s, type", + e->ops.length (), e->operation->id); + else + fprintf (f, " return build_call_expr " + "(builtin_decl_implicit (%s), %d", + e->operation->id, e->ops.length()); + for (unsigned j = 0; j < e->ops.length (); ++j) + fprintf (f, ", res_op%d", j); + fprintf (f, ");\n"); + } + } + else if (s->result->type == operand::OP_CAPTURE + || s->result->type == operand::OP_C_EXPR) + { + fprintf (f, " tree res;\n"); + s->result->gen_transform (f, " res", false, 1, "type", indexes); + fprintf (f, " return res;\n"); + } + else + gcc_unreachable (); + } + + for (unsigned i = 0; i < n_braces; ++i) + fprintf (f, "}\n"); + + fprintf (f, "}\n"); + } + + /* Main entry to generate code for matching GIMPLE IL off the decision + tree. */ + + void + decision_tree::gen_gimple (FILE *f) + { + for (unsigned n = 1; n <= 3; ++n) + { + fprintf (f, "\nstatic bool\n" + "gimple_simplify (code_helper *ARG_UNUSED (res_code),\n" + " tree *ARG_UNUSED (res_ops),\n" + " gimple_seq *ARG_UNUSED (seq),\n" + " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n" + " code_helper code, tree ARG_UNUSED (type)"); + for (unsigned i = 0; i < n; ++i) + fprintf (f, ", tree ARG_UNUSED (op%d)", i); + fprintf (f, ")\n"); + fprintf (f, "{\n"); + + fprintf (f, "switch (code.get_rep())\n" + "{\n"); + for (unsigned i = 0; i < root->kids.length (); i++) + { + dt_operand *dop = static_cast<dt_operand *>(root->kids[i]); + expr *e = static_cast<expr *>(dop->op); + if (e->ops.length () != n) + continue; + + if (*e->operation == CONVERT_EXPR + || *e->operation == NOP_EXPR) + fprintf (f, "CASE_CONVERT:\n"); + else + fprintf (f, "case %s%s:\n", + is_a <fn_id *> (e->operation) ? "-" : "", + e->operation->id); + fprintf (f, "{\n"); + dop->gen_kids (f, true); + fprintf (f, "break;\n"); + fprintf (f, "}\n"); + } + fprintf (f, "default:;\n" + "}\n"); + + fprintf (f, "return false;\n"); + fprintf (f, "}\n"); + } + } + + /* Main entry to generate code for matching GENERIC IL off the decision + tree. */ + + void + decision_tree::gen_generic (FILE *f) + { + for (unsigned n = 1; n <= 3; ++n) + { + fprintf (f, "\ntree\n" + "generic_simplify (enum tree_code code, " + "tree type ATTRIBUTE_UNUSED"); + for (unsigned i = 0; i < n; ++i) + fprintf (f, ", tree op%d", i); + fprintf (f, ")\n"); + fprintf (f, "{\n"); + + /* ??? For now reject all simplifications on operands with + side-effects as we are not prepared to properly wrap + omitted parts with omit_one_operand and friends. In + principle we can do that automagically for a subset of + transforms (and only reject the remaining cases). + This fixes for example gcc.c-torture/execute/20050131-1.c. */ + fprintf (f, "if ((op0 && TREE_SIDE_EFFECTS (op0))"); + for (unsigned i = 1; i < n; ++i) + fprintf (f, "|| (op%d && TREE_SIDE_EFFECTS (op%d))", i, i); + fprintf (f, ")\n" + " return NULL_TREE;\n"); + + fprintf (f, "switch (code)\n" + "{\n"); + for (unsigned i = 0; i < root->kids.length (); i++) + { + dt_operand *dop = static_cast<dt_operand *>(root->kids[i]); + expr *e = static_cast<expr *>(dop->op); + if (e->ops.length () != n + /* Builtin simplifications are somewhat premature on + GENERIC. The following drops patterns with outermost + calls. It's easy to emit overloads for function code + though if necessary. */ + || e->operation->kind != id_base::CODE) + continue; + + operator_id *op_id = static_cast <operator_id *> (e->operation); + if (op_id->code == NOP_EXPR || op_id->code == CONVERT_EXPR) + fprintf (f, "CASE_CONVERT:\n"); + else + fprintf (f, "case %s:\n", e->operation->id); + fprintf (f, "{\n"); + dop->gen_kids (f, false); + fprintf (f, "break;\n" + "}\n"); + } + fprintf (f, "default:;\n" + "}\n"); + + fprintf (f, "return NULL_TREE;\n"); + fprintf (f, "}\n"); + } + } + + /* Output code to implement the predicate P from the decision tree DT. */ + + void + write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple) + { + fprintf (f, "\nbool\n" + "%s%s (tree t%s%s)\n" + "{\n", gimple ? "gimple_" : "tree_", p->id, + p->nargs > 0 ? ", tree *res_ops" : "", + gimple ? ", tree (*valueize)(tree)" : ""); + /* Conveniently make 'type' available. */ + fprintf (f, "tree type = TREE_TYPE (t);\n"); + + if (!gimple) + fprintf (f, "if (TREE_SIDE_EFFECTS (t)) return false;\n"); + dt.root->gen_kids (f, gimple); + + fprintf (f, "return false;\n" + "}\n"); + } + + /* Write the common header for the GIMPLE/GENERIC IL matching routines. */ + + static void + write_header (FILE *f, const char *head) + { + fprintf (f, "/* Generated automatically by the program `genmatch' from\n"); + fprintf (f, " a IL pattern matching and simplification description. */\n"); + + /* Include the header instead of writing it awkwardly quoted here. */ + fprintf (f, "\n#include \"%s\"\n", head); + } + + + + /* AST parsing. */ + + class parser + { + public: + parser (cpp_reader *); + + private: + const cpp_token *next (); + const cpp_token *peek (); + const cpp_token *peek_ident (const char * = NULL); + const cpp_token *expect (enum cpp_ttype); + void eat_token (enum cpp_ttype); + const char *get_string (); + const char *get_ident (); + void eat_ident (const char *); + const char *get_number (); + + id_base *parse_operation (); + operand *parse_capture (operand *); + operand *parse_expr (); + c_expr *parse_c_expr (cpp_ttype); + operand *parse_op (); + + void parse_pattern (); + void parse_simplify (source_location, vec<simplify *>&, predicate_id *, + expr *); + void parse_for (source_location); + void parse_if (source_location); + void parse_predicates (source_location); + + cpp_reader *r; + vec<if_or_with> active_ifs; + vec<vec<user_id *> > active_fors; + + std::map<std::string, unsigned> *capture_ids; + + public: + vec<simplify *> simplifiers; + vec<predicate_id *> user_predicates; + }; + + /* Lexing helpers. */ + + /* Read the next non-whitespace token from R. */ + + const cpp_token * + parser::next () + { + const cpp_token *token; + do + { + token = cpp_get_token (r); + } + while (token->type == CPP_PADDING + && token->type != CPP_EOF); + return token; + } + + /* Peek at the next non-whitespace token from R. */ + + const cpp_token * + parser::peek () + { + const cpp_token *token; + unsigned i = 0; + do + { + token = cpp_peek_token (r, i++); + } + while (token->type == CPP_PADDING + && token->type != CPP_EOF); + /* If we peek at EOF this is a fatal error as it leaves the + cpp_reader in unusable state. Assume we really wanted a + token and thus this EOF is unexpected. */ + if (token->type == CPP_EOF) + fatal_at (token, "unexpected end of file"); + return token; + } + + /* Peek at the next identifier token (or return NULL if the next + token is not an identifier or equal to ID if supplied). */ + + const cpp_token * + parser::peek_ident (const char *id) + { + const cpp_token *token = peek (); + if (token->type != CPP_NAME) + return 0; + + if (id == 0) + return token; + + const char *t = (const char *) CPP_HASHNODE (token->val.node.node)->ident.str; + if (strcmp (id, t) == 0) + return token; + + return 0; + } + + /* Read the next token from R and assert it is of type TK. */ + + const cpp_token * + parser::expect (enum cpp_ttype tk) + { + const cpp_token *token = next (); + if (token->type != tk) + fatal_at (token, "expected %s, got %s", + cpp_type2name (tk, 0), cpp_type2name (token->type, 0)); + + return token; + } + + /* Consume the next token from R and assert it is of type TK. */ + + void + parser::eat_token (enum cpp_ttype tk) + { + expect (tk); + } + + /* Read the next token from R and assert it is of type CPP_STRING and + return its value. */ + + const char * + parser::get_string () + { + const cpp_token *token = expect (CPP_STRING); + return (const char *)token->val.str.text; + } + + /* Read the next token from R and assert it is of type CPP_NAME and + return its value. */ + + const char * + parser::get_ident () + { + const cpp_token *token = expect (CPP_NAME); + return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str; + } + + /* Eat an identifier token with value S from R. */ + + void + parser::eat_ident (const char *s) + { + const cpp_token *token = peek (); + const char *t = get_ident (); + if (strcmp (s, t) != 0) + fatal_at (token, "expected '%s' got '%s'\n", s, t); + } + + /* Read the next token from R and assert it is of type CPP_NUMBER and + return its value. */ + + const char * + parser::get_number () + { + const cpp_token *token = expect (CPP_NUMBER); + return (const char *)token->val.str.text; + } + + + /* Parse the operator ID, special-casing convert?, convert1? and + convert2? */ + + id_base * + parser::parse_operation () + { + const cpp_token *id_tok = peek (); + const char *id = get_ident (); + const cpp_token *token = peek (); + if (strcmp (id, "convert0") == 0) + fatal_at (id_tok, "use 'convert?' here"); + if (token->type == CPP_QUERY + && !(token->flags & PREV_WHITE)) + { + if (strcmp (id, "convert") == 0) + id = "convert0"; + else if (strcmp (id, "convert1") == 0) + ; + else if (strcmp (id, "convert2") == 0) + ; + else + fatal_at (id_tok, "non-convert operator conditionalized"); + eat_token (CPP_QUERY); + } + else if (strcmp (id, "convert1") == 0 + || strcmp (id, "convert2") == 0) + fatal_at (id_tok, "expected '?' after conditional operator"); + id_base *op = get_operator (id); + if (!op) + fatal_at (id_tok, "unknown operator %s", id); + return op; + } + + /* Parse a capture. + capture = '@'<number> */ + + struct operand * + parser::parse_capture (operand *op) + { + eat_token (CPP_ATSIGN); + const cpp_token *token = peek (); + const char *id; + if (token->type == CPP_NUMBER) + id = get_number (); + else if (token->type == CPP_NAME) + id = get_ident (); + else + fatal_at (token, "expected number or identifier"); + unsigned next_id = capture_ids->size (); + std::pair<std::map<std::string, unsigned>::iterator, bool> res + = capture_ids->insert (std::pair<std::string, unsigned>(id, next_id)); + return new capture ((*res.first).second, op); + } + + /* Parse an expression + expr = '(' <operation>[capture][flag][type] <operand>... ')' */ + + struct operand * + parser::parse_expr () + { + expr *e = new expr (parse_operation ()); + const cpp_token *token = peek (); + operand *op; + bool is_commutative = false; + const char *expr_type = NULL; + + if (token->type == CPP_COLON + && !(token->flags & PREV_WHITE)) + { + eat_token (CPP_COLON); + token = peek (); + if (token->type == CPP_NAME + && !(token->flags & PREV_WHITE)) + { + const char *s = get_ident (); + if (s[0] == 'c' && !s[1]) + is_commutative = true; + else if (s[1] != '\0') + expr_type = s; + else + fatal_at (token, "flag %s not recognized", s); + token = peek (); + } + else + fatal_at (token, "expected flag or type specifying identifier"); + } + + if (token->type == CPP_ATSIGN + && !(token->flags & PREV_WHITE)) + op = parse_capture (e); + else + op = e; + do + { + const cpp_token *token = peek (); + if (token->type == CPP_CLOSE_PAREN) + { + if (e->operation->nargs != -1 + && e->operation->nargs != (int) e->ops.length ()) + fatal_at (token, "'%s' expects %u operands, not %u", + e->operation->id, e->operation->nargs, e->ops.length ()); + if (is_commutative) + { + if (e->ops.length () == 2) + e->is_commutative = true; + else + fatal_at (token, "only binary operators or function with " + "two arguments can be marked commutative"); + } + e->expr_type = expr_type; + return op; + } + e->append_op (parse_op ()); + } + while (1); + } + + /* Lex native C code delimited by START recording the preprocessing tokens + for later processing. + c_expr = ('{'|'(') <pp token>... ('}'|')') */ + + c_expr * + parser::parse_c_expr (cpp_ttype start) + { + const cpp_token *token; + cpp_ttype end; + unsigned opencnt; + vec<cpp_token> code = vNULL; + unsigned nr_stmts = 0; + eat_token (start); + if (start == CPP_OPEN_PAREN) + end = CPP_CLOSE_PAREN; + else if (start == CPP_OPEN_BRACE) + end = CPP_CLOSE_BRACE; + else + gcc_unreachable (); + opencnt = 1; + do + { + token = next (); + + /* Count brace pairs to find the end of the expr to match. */ + if (token->type == start) + opencnt++; + else if (token->type == end + && --opencnt == 0) + break; + + /* This is a lame way of counting the number of statements. */ + if (token->type == CPP_SEMICOLON) + nr_stmts++; + + /* Record the token. */ + code.safe_push (*token); + } + while (1); + return new c_expr (r, code, nr_stmts, vNULL, capture_ids); + } + + /* Parse an operand which is either an expression, a predicate or + a standalone capture. + op = predicate | expr | c_expr | capture */ + + struct operand * + parser::parse_op () + { + const cpp_token *token = peek (); + struct operand *op = NULL; + if (token->type == CPP_OPEN_PAREN) + { + eat_token (CPP_OPEN_PAREN); + op = parse_expr (); + eat_token (CPP_CLOSE_PAREN); + } + else if (token->type == CPP_OPEN_BRACE) + { + op = parse_c_expr (CPP_OPEN_BRACE); + } + else + { + /* Remaining ops are either empty or predicates */ + if (token->type == CPP_NAME) + { + const char *id = get_ident (); + id_base *opr = get_operator (id); + if (!opr) + fatal_at (token, "expected predicate name"); + if (operator_id *code = dyn_cast <operator_id *> (opr)) + { + if (code->nargs != 0) + fatal_at (token, "using an operator with operands as predicate"); + /* Parse the zero-operand operator "predicates" as + expression. */ + op = new expr (opr); + } + else if (predicate_id *p = dyn_cast <predicate_id *> (opr)) + op = new predicate (p); + else + fatal_at (token, "using an unsupported operator as predicate"); + token = peek (); + if (token->flags & PREV_WHITE) + return op; + } + else if (token->type != CPP_COLON + && token->type != CPP_ATSIGN) + fatal_at (token, "expected expression or predicate"); + /* optionally followed by a capture and a predicate. */ + if (token->type == CPP_COLON) + fatal_at (token, "not implemented: predicate on leaf operand"); + if (token->type == CPP_ATSIGN) + op = parse_capture (op); + } + + return op; + } + + /* Parse + simplify = 'simplify' <expr> <result-op> + or + match = 'match' <ident> <expr> [<result-op>] + with + <result-op> = <op> | <if> | <with> + <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')' + <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')' + and fill SIMPLIFIERS with the results. */ + + void + parser::parse_simplify (source_location match_location, + vec<simplify *>& simplifiers, predicate_id *matcher, + expr *result) + { + /* Reset the capture map. */ + capture_ids = new std::map<std::string, unsigned>; + + const cpp_token *loc = peek (); + struct operand *match = parse_op (); + if (match->type == operand::OP_CAPTURE && !matcher) + fatal_at (loc, "outermost expression cannot be captured"); + if (match->type == operand::OP_EXPR + && is_a <predicate_id *> (as_a <expr *> (match)->operation)) + fatal_at (loc, "outermost expression cannot be a predicate"); + + const cpp_token *token = peek (); + + /* If this if is immediately closed then it is part of a predicate + definition. Push it. */ + if (token->type == CPP_CLOSE_PAREN) + { + if (!matcher) + fatal_at (token, "expected transform expression"); + simplifiers.safe_push + (new simplify (match, match_location, result, token->src_loc, + active_ifs.copy (), active_fors.copy (), + capture_ids)); + return; + } + + unsigned active_ifs_len = active_ifs.length (); + while (1) + { + if (token->type == CPP_OPEN_PAREN) + { + source_location paren_loc = token->src_loc; + eat_token (CPP_OPEN_PAREN); + if (peek_ident ("if")) + { + eat_ident ("if"); + active_ifs.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN), + token->src_loc, false)); + /* If this if is immediately closed then it contains a + manual matcher or is part of a predicate definition. + Push it. */ + if (peek ()->type == CPP_CLOSE_PAREN) + { + if (!matcher) + fatal_at (token, "manual transform not implemented"); + simplifiers.safe_push + (new simplify (match, match_location, result, + paren_loc, active_ifs.copy (), + active_fors.copy (), capture_ids)); + } + } + else if (peek_ident ("with")) + { + eat_ident ("with"); + /* Parse (with c-expr expr) as (if-with (true) expr). */ + c_expr *e = parse_c_expr (CPP_OPEN_BRACE); + e->nr_stmts = 0; + active_ifs.safe_push (if_or_with (e, token->src_loc, true)); + } + else + { + operand *op = result; + if (!matcher) + op = parse_expr (); + simplifiers.safe_push + (new simplify (match, match_location, op, + token->src_loc, active_ifs.copy (), + active_fors.copy (), capture_ids)); + eat_token (CPP_CLOSE_PAREN); + /* A "default" result closes the enclosing scope. */ + if (active_ifs.length () > active_ifs_len) + { + eat_token (CPP_CLOSE_PAREN); + active_ifs.pop (); + } + else + return; + } + } + else if (token->type == CPP_CLOSE_PAREN) + { + /* Close a scope if requested. */ + if (active_ifs.length () > active_ifs_len) + { + eat_token (CPP_CLOSE_PAREN); + active_ifs.pop (); + token = peek (); + } + else + return; + } + else + { + if (matcher) + fatal_at (token, "expected match operand expression"); + simplifiers.safe_push + (new simplify (match, match_location, + matcher ? result : parse_op (), + token->src_loc, active_ifs.copy (), + active_fors.copy (), capture_ids)); + /* A "default" result closes the enclosing scope. */ + if (active_ifs.length () > active_ifs_len) + { + eat_token (CPP_CLOSE_PAREN); + active_ifs.pop (); + } + else + return; + } + token = peek (); + } + } + + /* Parsing of the outer control structures. */ + + /* Parse a for expression + for = '(' 'for' <subst>... <pattern> ')' + subst = <ident> '(' <ident>... ')' */ + + void + parser::parse_for (source_location) + { + vec<user_id *> user_ids = vNULL; + const cpp_token *token; + unsigned min_n_opers = 0, max_n_opers = 0; + + while (1) + { + token = peek_ident (); + if (token == 0) + break; + + /* Insert the user defined operators into the operator hash. */ + const char *id = get_ident (); + user_id *op = new user_id (id); + id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT); + if (*slot) + fatal_at (token, "operator already defined"); + *slot = op; + user_ids.safe_push (op); + + eat_token (CPP_OPEN_PAREN); + + int arity = -1; + while ((token = peek_ident ()) != 0) + { + const char *oper = get_ident (); + id_base *idb = get_operator (oper); + if (idb == NULL) + fatal_at (token, "no such operator '%s'", oper); + if (*idb == CONVERT0 || *idb == CONVERT1 || *idb == CONVERT2) + fatal_at (token, "conditional operators cannot be used inside for"); + + if (arity == -1) + arity = idb->nargs; + else if (idb->nargs == -1) + ; + else if (idb->nargs != arity) + fatal_at (token, "operator '%s' with arity %d does not match " + "others with arity %d", oper, idb->nargs, arity); + + op->substitutes.safe_push (idb); + } + op->nargs = arity; + token = expect (CPP_CLOSE_PAREN); + + unsigned nsubstitutes = op->substitutes.length (); + if (nsubstitutes == 0) + fatal_at (token, "A user-defined operator must have at least " + "one substitution"); + if (max_n_opers == 0) + { + min_n_opers = nsubstitutes; + max_n_opers = nsubstitutes; + } + else + { + if (nsubstitutes % min_n_opers != 0 + && min_n_opers % nsubstitutes != 0) + fatal_at (token, "All user-defined identifiers must have a " + "multiple number of operator substitutions of the " + "smallest number of substitutions"); + if (nsubstitutes < min_n_opers) + min_n_opers = nsubstitutes; + else if (nsubstitutes > max_n_opers) + max_n_opers = nsubstitutes; + } + } + + unsigned n_ids = user_ids.length (); + if (n_ids == 0) + fatal_at (token, "for requires at least one user-defined identifier"); + + token = peek (); + if (token->type == CPP_CLOSE_PAREN) + fatal_at (token, "no pattern defined in for"); + + active_fors.safe_push (user_ids); + while (1) + { + token = peek (); + if (token->type == CPP_CLOSE_PAREN) + break; + parse_pattern (); + } + active_fors.pop (); + + /* Remove user-defined operators from the hash again. */ + for (unsigned i = 0; i < user_ids.length (); ++i) + operators->remove_elt (user_ids[i]); + } + + /* Parse an outer if expression. + if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */ + + void + parser::parse_if (source_location loc) + { + operand *ifexpr = parse_c_expr (CPP_OPEN_PAREN); + + const cpp_token *token = peek (); + if (token->type == CPP_CLOSE_PAREN) + fatal_at (token, "no pattern defined in if"); + + active_ifs.safe_push (if_or_with (ifexpr, loc, false)); + while (1) + { + const cpp_token *token = peek (); + if (token->type == CPP_CLOSE_PAREN) + break; + + parse_pattern (); + } + active_ifs.pop (); + } + + /* Parse a list of predefined predicate identifiers. + preds = '(' 'define_predicates' <ident>... ')' */ + + void + parser::parse_predicates (source_location) + { + do + { + const cpp_token *token = peek (); + if (token->type != CPP_NAME) + break; + + add_predicate (get_ident ()); + } + while (1); + } + + /* Parse outer control structures. + pattern = <preds>|<for>|<if>|<simplify>|<match> */ + + void + parser::parse_pattern () + { + /* All clauses start with '('. */ + eat_token (CPP_OPEN_PAREN); + const cpp_token *token = peek (); + const char *id = get_ident (); + if (strcmp (id, "simplify") == 0) + parse_simplify (token->src_loc, simplifiers, NULL, NULL); + else if (strcmp (id, "match") == 0) + { + bool with_args = false; + if (peek ()->type == CPP_OPEN_PAREN) + { + eat_token (CPP_OPEN_PAREN); + with_args = true; + } + const char *name = get_ident (); + id_base *id = get_operator (name); + predicate_id *p; + if (!id) + { + p = add_predicate (name); + user_predicates.safe_push (p); + } + else if ((p = dyn_cast <predicate_id *> (id))) + ; + else + fatal_at (token, "cannot add a match to a non-predicate ID"); + /* Parse (match <id> <arg>... (match-expr)) here. */ + expr *e = NULL; + if (with_args) + { + e = new expr (p); + while (peek ()->type == CPP_ATSIGN) + e->append_op (parse_capture (NULL)); + eat_token (CPP_CLOSE_PAREN); + } + if (p->nargs != -1 + && ((e && e->ops.length () != (unsigned)p->nargs) + || (!e && p->nargs != 0))) + fatal_at (token, "non-matching number of match operands"); + p->nargs = e ? e->ops.length () : 0; + parse_simplify (token->src_loc, p->matchers, p, e); + } + else if (strcmp (id, "for") == 0) + parse_for (token->src_loc); + else if (strcmp (id, "if") == 0) + parse_if (token->src_loc); + else if (strcmp (id, "define_predicates") == 0) + { + if (active_ifs.length () > 0 + || active_fors.length () > 0) + fatal_at (token, "define_predicates inside if or for is not supported"); + parse_predicates (token->src_loc); + } + else + fatal_at (token, "expected %s'simplify', 'match', 'for' or 'if'", + active_ifs.length () == 0 && active_fors.length () == 0 + ? "'define_predicates', " : ""); + + eat_token (CPP_CLOSE_PAREN); + } + + /* Main entry of the parser. Repeatedly parse outer control structures. */ + + parser::parser (cpp_reader *r_) + { + r = r_; + active_ifs = vNULL; + active_fors = vNULL; + simplifiers = vNULL; + user_predicates = vNULL; + + const cpp_token *token = next (); + while (token->type != CPP_EOF) + { + _cpp_backup_tokens (r, 1); + parse_pattern (); + token = next (); + } + } + + + /* Helper for the linemap code. */ + + static size_t + round_alloc_size (size_t s) + { + return s; + } + + + /* The genmatch generator progam. It reads from a pattern description + and outputs GIMPLE or GENERIC IL matching and simplification routines. */ + + int + main(int argc, char **argv) + { + cpp_reader *r; + + progname = "genmatch"; + + if (argc < 2) + return 1; + + bool gimple = true; + bool verbose = false; + char *input = argv[argc-1]; + for (int i = 1; i < argc - 1; ++i) + { + if (strcmp (argv[i], "-gimple") == 0) + gimple = true; + else if (strcmp (argv[i], "-generic") == 0) + gimple = false; + else if (strcmp (argv[i], "-v") == 0) + verbose = true; + else + { + fprintf (stderr, "Usage: genmatch [-gimple] [-generic] [-v] input\n"); + return 1; + } + } + + line_table = XCNEW (struct line_maps); + linemap_init (line_table, 0); + line_table->reallocator = xrealloc; + line_table->round_alloc_size = round_alloc_size; + + r = cpp_create_reader (CLK_GNUC99, NULL, line_table); + cpp_callbacks *cb = cpp_get_callbacks (r); + cb->error = error_cb; + + if (!cpp_read_main_file (r, input)) + return 1; + cpp_define (r, gimple ? "GIMPLE=1": "GENERIC=1"); + cpp_define (r, gimple ? "GENERIC=0": "GIMPLE=0"); + + /* Pre-seed operators. */ + operators = new hash_table<id_base> (1024); + #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \ + add_operator (SYM, # SYM, # TYPE, NARGS); + #define END_OF_BASE_TREE_CODES + #include "tree.def" + add_operator (CONVERT0, "CONVERT0", "tcc_unary", 1); + add_operator (CONVERT1, "CONVERT1", "tcc_unary", 1); + add_operator (CONVERT2, "CONVERT2", "tcc_unary", 1); + #undef END_OF_BASE_TREE_CODES + #undef DEFTREECODE + + /* Pre-seed builtin functions. + ??? Cannot use N (name) as that is targetm.emultls.get_address + for BUILT_IN_EMUTLS_GET_ADDRESS ... */ + #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \ + add_builtin (ENUM, # ENUM); + #include "builtins.def" + #undef DEF_BUILTIN + + /* Parse ahead! */ + parser p (r); + + if (gimple) + write_header (stdout, "gimple-match-head.c"); + else + write_header (stdout, "generic-match-head.c"); + + /* Go over all predicates defined with patterns and perform + lowering and code generation. */ + for (unsigned i = 0; i < p.user_predicates.length (); ++i) + { + predicate_id *pred = p.user_predicates[i]; + lower (pred->matchers); + + if (verbose) + for (unsigned i = 0; i < pred->matchers.length (); ++i) + print_matches (pred->matchers[i]); + + decision_tree dt; + for (unsigned i = 0; i < pred->matchers.length (); ++i) + dt.insert (pred->matchers[i], i); + + if (verbose) + dt.print (stderr); + + write_predicate (stdout, pred, dt, gimple); + } + + /* Lower the main simplifiers and generate code for them. */ + lower (p.simplifiers); + + if (verbose) + for (unsigned i = 0; i < p.simplifiers.length (); ++i) + print_matches (p.simplifiers[i]); + + decision_tree dt; + for (unsigned i = 0; i < p.simplifiers.length (); ++i) + dt.insert (p.simplifiers[i], i); + + if (verbose) + dt.print (stderr); + + if (gimple) + dt.gen_gimple (stdout); + else + dt.gen_generic (stdout); + + /* Finalize. */ + cpp_finish (r, NULL); + cpp_destroy (r); + + delete operators; + + return 0; + } +
