Google Git
Sign in
gnu / gcc / refs/tags/releases/gcc-8.2.0 / . / gcc / genmatch.c
blob: be6efe3bf1274acdb6ab3519f4ffdf3c2f42360a [file] [log] [blame]
/* Generate pattern matching and transform code shared between
GENERIC and GIMPLE folding code from match-and-simplify description.
Copyright (C) 2014-2018 Free Software Foundation, Inc.
Contributed by Richard Biener <rguenther@suse.de>
and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
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 "system.h"
#include "coretypes.h"
#include <cpplib.h>
#include "errors.h"
#include "hash-table.h"
#include "hash-set.h"
#include "is-a.h"
/* Stubs for GGC referenced through instantiations triggered by hash-map. */
void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
size_t, size_t MEM_STAT_DECL)
{
return NULL;
}
void ggc_free (void *)
{
}
/* Global state. */
/* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
unsigned verbose;
/* libccp helpers. */
static struct line_maps *line_table;
/* The rich_location class within libcpp requires a way to expand
source_location instances, and relies on the client code
providing a symbol named
linemap_client_expand_location_to_spelling_point
to do this.
This is the implementation for genmatch. */
expanded_location
linemap_client_expand_location_to_spelling_point (source_location loc,
enum location_aspect)
{
const struct line_map_ordinary *map;
loc = linemap_resolve_location (line_table, loc, LRK_SPELLING_LOCATION, &map);
return linemap_expand_location (line_table, map, loc);
}
static bool
#if GCC_VERSION >= 4001
__attribute__((format (printf, 5, 0)))
#endif
error_cb (cpp_reader *, int errtype, int, rich_location *richloc,
const char *msg, va_list *ap)
{
const line_map_ordinary *map;
source_location location = richloc->get_loc ();
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 %s: ", loc.file, loc.line, loc.column,
(errtype == CPP_DL_WARNING) ? "warning" : "error");
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);
}
if (errtype == CPP_DL_FATAL)
exit (1);
return false;
}
static void
#if GCC_VERSION >= 4001
__attribute__((format (printf, 2, 3)))
#endif
fatal_at (const cpp_token *tk, const char *msg, ...)
{
rich_location richloc (line_table, tk->src_loc);
va_list ap;
va_start (ap, msg);
error_cb (NULL, CPP_DL_FATAL, 0, &richloc, msg, &ap);
va_end (ap);
}
static void
#if GCC_VERSION >= 4001
__attribute__((format (printf, 2, 3)))
#endif
fatal_at (source_location loc, const char *msg, ...)
{
rich_location richloc (line_table, loc);
va_list ap;
va_start (ap, msg);
error_cb (NULL, CPP_DL_FATAL, 0, &richloc, msg, &ap);
va_end (ap);
}
static void
#if GCC_VERSION >= 4001
__attribute__((format (printf, 2, 3)))
#endif
warning_at (const cpp_token *tk, const char *msg, ...)
{
rich_location richloc (line_table, tk->src_loc);
va_list ap;
va_start (ap, msg);
error_cb (NULL, CPP_DL_WARNING, 0, &richloc, msg, &ap);
va_end (ap);
}
static void
#if GCC_VERSION >= 4001
__attribute__((format (printf, 2, 3)))
#endif
warning_at (source_location loc, const char *msg, ...)
{
rich_location richloc (line_table, loc);
va_list ap;
va_start (ap, msg);
error_cb (NULL, CPP_DL_WARNING, 0, &richloc, msg, &ap);
va_end (ap);
}
/* Like fprintf, but print INDENT spaces at the beginning. */
static void
#if GCC_VERSION >= 4001
__attribute__((format (printf, 3, 4)))
#endif
fprintf_indent (FILE *f, unsigned int indent, const char *format, ...)
{
va_list ap;
for (; indent >= 8; indent -= 8)
fputc ('\t', f);
fprintf (f, "%*s", indent, "");
va_start (ap, format);
vfprintf (f, format, ap);
va_end (ap);
}
static void
output_line_directive (FILE *f, source_location location,
bool dumpfile = false)
{
const line_map_ordinary *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 defined(DIR_SEPARATOR_2)
const char *pos2 = strrchr (loc.file, DIR_SEPARATOR_2);
if (pos2 && (!file || (pos2 > file)))
file = pos2;
#endif
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,
VIEW_CONVERT0,
VIEW_CONVERT1,
VIEW_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
};
#define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
enum internal_fn {
#include "internal-fn.def"
IFN_LAST
};
/* Return true if CODE represents a commutative tree code. Otherwise
return false. */
bool
commutative_tree_code (enum tree_code code)
{
switch (code)
{
case PLUS_EXPR:
case MULT_EXPR:
case MULT_HIGHPART_EXPR:
case MIN_EXPR:
case MAX_EXPR:
case BIT_IOR_EXPR:
case BIT_XOR_EXPR:
case BIT_AND_EXPR:
case NE_EXPR:
case EQ_EXPR:
case UNORDERED_EXPR:
case ORDERED_EXPR:
case UNEQ_EXPR:
case LTGT_EXPR:
case TRUTH_AND_EXPR:
case TRUTH_XOR_EXPR:
case TRUTH_OR_EXPR:
case WIDEN_MULT_EXPR:
case VEC_WIDEN_MULT_HI_EXPR:
case VEC_WIDEN_MULT_LO_EXPR:
case VEC_WIDEN_MULT_EVEN_EXPR:
case VEC_WIDEN_MULT_ODD_EXPR:
return true;
default:
break;
}
return false;
}
/* Return true if CODE represents a ternary tree code for which the
first two operands are commutative. Otherwise return false. */
bool
commutative_ternary_tree_code (enum tree_code code)
{
switch (code)
{
case WIDEN_MULT_PLUS_EXPR:
case WIDEN_MULT_MINUS_EXPR:
case DOT_PROD_EXPR:
case FMA_EXPR:
return true;
default:
break;
}
return false;
}
/* Return true if CODE is a comparison. */
bool
comparison_code_p (enum tree_code code)
{
switch (code)
{
case EQ_EXPR:
case NE_EXPR:
case ORDERED_EXPR:
case UNORDERED_EXPR:
case LTGT_EXPR:
case UNEQ_EXPR:
case GT_EXPR:
case GE_EXPR:
case LT_EXPR:
case LE_EXPR:
case UNGT_EXPR:
case UNGE_EXPR:
case UNLT_EXPR:
case UNLE_EXPR:
return true;
default:
break;
}
return false;
}
/* Base class for all identifiers the parser knows. */
struct id_base : nofree_ptr_hash<id_base>
{
enum id_kind { CODE, FN, PREDICATE, USER, NULL_ID } kind;
id_base (id_kind, const char *, int = -1);
hashval_t hashval;
int nargs;
const char *id;
/* hash_table support. */
static inline hashval_t hash (const id_base *);
static inline int equal (const id_base *, const id_base *);
};
inline hashval_t
id_base::hash (const id_base *op)
{
return op->hashval;
}
inline int
id_base::equal (const id_base *op1,
const id_base *op2)
{
return (op1->hashval == op2->hashval
&& strcmp (op1->id, op2->id) == 0);
}
/* The special id "null", which matches nothing. */
static id_base *null_id;
/* 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 or internal 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_) {}
fn_id (enum internal_fn fn_, const char *id_)
: id_base (id_base::FN, id_), fn (int (END_BUILTINS) + int (fn_)) {}
unsigned int 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_, bool is_oper_list_ = false)
: id_base (id_base::USER, id_), substitutes (vNULL),
used (false), is_oper_list (is_oper_list_) {}
vec<id_base *> substitutes;
bool used;
bool is_oper_list;
};
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
/* And allow CONSTRUCTOR for vector initializers. */
&& !(code == CONSTRUCTOR)
/* Allow SSA_NAME as predicate operator. */
&& !(code == SSA_NAME))
return;
/* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
if (code == ADDR_EXPR)
nargs = 0;
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 built-in or internal function identifier to the hash. ID is
the name of its CFN_* enumeration value. */
template <typename T>
static void
add_function (T 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. Allow "null" if ALLOW_NULL. */
id_base *
get_operator (const char *id, bool allow_null = false)
{
if (allow_null && strcmp (id, "null") == 0)
return null_id;
id_base tem (id_base::CODE, id);
id_base *op = operators->find_with_hash (&tem, tem.hashval);
if (op)
{
/* If this is a user-defined identifier track whether it was used. */
if (user_id *uid = dyn_cast<user_id *> (op))
uid->used = true;
return op;
}
char *id2;
bool all_upper = true;
bool all_lower = true;
for (unsigned int i = 0; id[i]; ++i)
if (ISUPPER (id[i]))
all_lower = false;
else if (ISLOWER (id[i]))
all_upper = false;
if (all_lower)
{
/* Try in caps with _EXPR appended. */
id2 = ACONCAT ((id, "_EXPR", NULL));
for (unsigned int i = 0; id2[i]; ++i)
id2[i] = TOUPPER (id2[i]);
}
else if (all_upper && strncmp (id, "IFN_", 4) == 0)
/* Try CFN_ instead of IFN_. */
id2 = ACONCAT (("CFN_", id + 4, NULL));
else if (all_upper && strncmp (id, "BUILT_IN_", 9) == 0)
/* Try prepending CFN_. */
id2 = ACONCAT (("CFN_", id, NULL));
else
return NULL;
new (&tem) id_base (id_base::CODE, id2);
return operators->find_with_hash (&tem, tem.hashval);
}
/* Return the comparison operators that results if the operands are
swapped. This is safe for floating-point. */
id_base *
swap_tree_comparison (operator_id *p)
{
switch (p->code)
{
case EQ_EXPR:
case NE_EXPR:
case ORDERED_EXPR:
case UNORDERED_EXPR:
case LTGT_EXPR:
case UNEQ_EXPR:
return p;
case GT_EXPR:
return get_operator ("LT_EXPR");
case GE_EXPR:
return get_operator ("LE_EXPR");
case LT_EXPR:
return get_operator ("GT_EXPR");
case LE_EXPR:
return get_operator ("GE_EXPR");
case UNGT_EXPR:
return get_operator ("UNLT_EXPR");
case UNGE_EXPR:
return get_operator ("UNLE_EXPR");
case UNLT_EXPR:
return get_operator ("UNGT_EXPR");
case UNLE_EXPR:
return get_operator ("UNGE_EXPR");
default:
gcc_unreachable ();
}
}
typedef hash_map<nofree_string_hash, unsigned> cid_map_t;
/* The AST produced by parsing of the pattern definitions. */
struct dt_operand;
struct capture_info;
/* The base class for operands. */
struct operand {
enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR, OP_IF, OP_WITH };
operand (enum op_type type_, source_location loc_)
: type (type_), location (loc_) {}
enum op_type type;
source_location location;
virtual void gen_transform (FILE *, int, const char *, bool, int,
const char *, capture_info *,
dt_operand ** = 0,
int = 0)
{ gcc_unreachable (); }
};
/* A predicate operand. Predicates are leafs in the AST. */
struct predicate : public operand
{
predicate (predicate_id *p_, source_location loc)
: operand (OP_PREDICATE, loc), 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_, source_location loc, bool is_commutative_ = false)
: operand (OP_EXPR, loc), operation (operation_),
ops (vNULL), expr_type (NULL), is_commutative (is_commutative_),
is_generic (false), force_single_use (false) {}
expr (expr *e)
: operand (OP_EXPR, e->location), operation (e->operation),
ops (vNULL), expr_type (e->expr_type), is_commutative (e->is_commutative),
is_generic (e->is_generic), force_single_use (e->force_single_use) {}
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;
/* Whether the expression is expected to be in GENERIC form. */
bool is_generic;
/* Whether pushing any stmt to the sequence should be conditional
on this expression having a single-use. */
bool force_single_use;
virtual void gen_transform (FILE *f, int, const char *, bool, int,
const char *, capture_info *,
dt_operand ** = 0, int = 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_, source_location loc,
vec<cpp_token> code_, unsigned nr_stmts_,
vec<id_tab> ids_, cid_map_t *capture_ids_)
: operand (OP_C_EXPR, loc), 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;
cid_map_t *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, int, const char *, bool, int,
const char *, capture_info *,
dt_operand ** = 0, int = 0);
};
/* A wrapper around another operand that captures its value. */
struct capture : public operand
{
capture (source_location loc, unsigned where_, operand *what_, bool value_)
: operand (OP_CAPTURE, loc), where (where_), value_match (value_),
what (what_) {}
/* Identifier index for the value. */
unsigned where;
/* Whether in a match of two operands the compare should be for
equal values rather than equal atoms (boils down to a type
check or not). */
bool value_match;
/* The captured value. */
operand *what;
virtual void gen_transform (FILE *f, int, const char *, bool, int,
const char *, capture_info *,
dt_operand ** = 0, int = 0);
};
/* if expression. */
struct if_expr : public operand
{
if_expr (source_location loc)
: operand (OP_IF, loc), cond (NULL), trueexpr (NULL), falseexpr (NULL) {}
c_expr *cond;
operand *trueexpr;
operand *falseexpr;
};
/* with expression. */
struct with_expr : public operand
{
with_expr (source_location loc)
: operand (OP_WITH, loc), with (NULL), subexpr (NULL) {}
c_expr *with;
operand *subexpr;
};
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;
}
template<>
template<>
inline bool
is_a_helper <if_expr *>::test (operand *op)
{
return op->type == operand::OP_IF;
}
template<>
template<>
inline bool
is_a_helper <with_expr *>::test (operand *op)
{
return op->type == operand::OP_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
{
enum simplify_kind { SIMPLIFY, MATCH };
simplify (simplify_kind kind_, unsigned id_, operand *match_,
operand *result_, vec<vec<user_id *> > for_vec_,
cid_map_t *capture_ids_)
: kind (kind_), id (id_), match (match_), result (result_),
for_vec (for_vec_), for_subst_vec (vNULL),
capture_ids (capture_ids_), capture_max (capture_ids_->elements () - 1) {}
simplify_kind kind;
/* ID. This is kept to easily associate related simplifies expanded
from the same original one. */
unsigned id;
/* The expression that is matched against the GENERIC or GIMPLE IL. */
operand *match;
/* For a (simplify ...) an expression with ifs and withs with the expression
produced when the pattern applies in the leafs.
For a (match ...) the leafs are either empty if it is a simple predicate
or the single expression specifying the matched operands. */
struct operand *result;
/* Collected 'for' expression operators that have to be replaced
in the lowering phase. */
vec<vec<user_id *> > for_vec;
vec<std::pair<user_id *, id_base *> > for_subst_vec;
/* A map of capture identifiers to indexes. */
cid_map_t *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))
{
if (c->what && flattened == false)
print_operand (c->what, f, flattened);
fprintf (f, "@%u", c->where);
}
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))
{
if (e->ops.length () == 0)
fprintf (f, "%s", e->operation->id);
else
{
fprintf (f, "(%s", e->operation->id);
if (flattened == false)
{
for (unsigned i = 0; i < e->ops.length (); ++i)
{
putc (' ', f);
print_operand (e->ops[i], f, flattened);
}
}
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<vec<user_id *> > &for_vec)
{
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_vec);
for (unsigned i = 0; i < v.length (); ++i)
{
capture *nc = new capture (c->location, c->where, v[i],
c->value_match);
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], for_vec));
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);
ne->is_commutative = false;
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);
if (operator_id *p = dyn_cast <operator_id *> (ne->operation))
{
if (comparison_code_p (p->code))
ne->operation = swap_tree_comparison (p);
}
else if (user_id *p = dyn_cast <user_id *> (ne->operation))
{
bool found_compare = false;
for (unsigned j = 0; j < p->substitutes.length (); ++j)
if (operator_id *q = dyn_cast <operator_id *> (p->substitutes[j]))
{
if (comparison_code_p (q->code)
&& swap_tree_comparison (q) != q)
{
found_compare = true;
break;
}
}
if (found_compare)
{
user_id *newop = new user_id ("<internal>");
for (unsigned j = 0; j < p->substitutes.length (); ++j)
{
id_base *subst = p->substitutes[j];
if (operator_id *q = dyn_cast <operator_id *> (subst))
{
if (comparison_code_p (q->code))
subst = swap_tree_comparison (q);
}
newop->substitutes.safe_push (subst);
}
ne->operation = newop;
/* Search for 'p' inside the for vector and push 'newop'
to the same level. */
for (unsigned j = 0; newop && j < for_vec.length (); ++j)
for (unsigned k = 0; k < for_vec[j].length (); ++k)
if (for_vec[j][k] == p)
{
for_vec[j].safe_push (newop);
newop = NULL;
break;
}
}
}
ne->is_commutative = false;
// 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, s->for_vec);
for (unsigned i = 0; i < matchers.length (); ++i)
{
simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
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,
enum tree_code to_oper, bool strip)
{
if (capture *c = dyn_cast<capture *> (o))
{
if (c->what)
return new capture (c->location, c->where,
lower_opt_convert (c->what, oper, to_oper, strip),
c->value_match);
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, to_oper, strip);
expr *ne = new expr (e);
ne->operation = (to_oper == CONVERT_EXPR
? get_operator ("CONVERT_EXPR")
: get_operator ("VIEW_CONVERT_EXPR"));
ne->append_op (lower_opt_convert (e->ops[0], oper, to_oper, strip));
return ne;
}
expr *ne = new expr (e);
for (unsigned i = 0; i < e->ops.length (); ++i)
ne->append_op (lower_opt_convert (e->ops[i], oper, to_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, CONVERT_EXPR,
CONVERT1, CONVERT_EXPR,
CONVERT2, CONVERT_EXPR,
VIEW_CONVERT0, VIEW_CONVERT_EXPR,
VIEW_CONVERT1, VIEW_CONVERT_EXPR,
VIEW_CONVERT2, VIEW_CONVERT_EXPR };
/* 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 < sizeof (opers) / sizeof (enum tree_code); i += 2)
{
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], opers[i+1], false));
v2.safe_push (lower_opt_convert (v1[j],
opers[i], opers[i+1], 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 (s->kind, s->id, matchers[i], s->result,
s->for_vec, s->capture_ids);
simplifiers.safe_push (ns);
}
}
/* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
GENERIC and a GIMPLE variant. */
static vec<operand *>
lower_cond (operand *o)
{
vec<operand *> ro = vNULL;
if (capture *c = dyn_cast<capture *> (o))
{
if (c->what)
{
vec<operand *> lop = vNULL;
lop = lower_cond (c->what);
for (unsigned i = 0; i < lop.length (); ++i)
ro.safe_push (new capture (c->location, c->where, lop[i],
c->value_match));
return ro;
}
}
expr *e = dyn_cast<expr *> (o);
if (!e || e->ops.length () == 0)
{
ro.safe_push (o);
return ro;
}
vec< vec<operand *> > ops_vector = vNULL;
for (unsigned i = 0; i < e->ops.length (); ++i)
ops_vector.safe_push (lower_cond (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);
for (unsigned j = 0; j < result[i].length (); ++j)
ne->append_op (result[i][j]);
ro.safe_push (ne);
/* If this is a COND with a captured expression or an
expression with two operands then also match a GENERIC
form on the compare. */
if ((*e->operation == COND_EXPR
|| *e->operation == VEC_COND_EXPR)
&& ((is_a <capture *> (e->ops[0])
&& as_a <capture *> (e->ops[0])->what
&& is_a <expr *> (as_a <capture *> (e->ops[0])->what)
&& as_a <expr *>
(as_a <capture *> (e->ops[0])->what)->ops.length () == 2)
|| (is_a <expr *> (e->ops[0])
&& as_a <expr *> (e->ops[0])->ops.length () == 2)))
{
expr *ne = new expr (e);
for (unsigned j = 0; j < result[i].length (); ++j)
ne->append_op (result[i][j]);
if (capture *c = dyn_cast <capture *> (ne->ops[0]))
{
expr *ocmp = as_a <expr *> (c->what);
expr *cmp = new expr (ocmp);
for (unsigned j = 0; j < ocmp->ops.length (); ++j)
cmp->append_op (ocmp->ops[j]);
cmp->is_generic = true;
ne->ops[0] = new capture (c->location, c->where, cmp,
c->value_match);
}
else
{
expr *ocmp = as_a <expr *> (ne->ops[0]);
expr *cmp = new expr (ocmp);
for (unsigned j = 0; j < ocmp->ops.length (); ++j)
cmp->append_op (ocmp->ops[j]);
cmp->is_generic = true;
ne->ops[0] = cmp;
}
ro.safe_push (ne);
}
}
return ro;
}
/* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
GENERIC and a GIMPLE variant. */
static void
lower_cond (simplify *s, vec<simplify *>& simplifiers)
{
vec<operand *> matchers = lower_cond (s->match);
for (unsigned i = 0; i < matchers.length (); ++i)
{
simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
s->for_vec, s->capture_ids);
simplifiers.safe_push (ns);
}
}
/* Return true if O refers to ID. */
bool
contains_id (operand *o, user_id *id)
{
if (capture *c = dyn_cast<capture *> (o))
return c->what && contains_id (c->what, id);
if (expr *e = dyn_cast<expr *> (o))
{
if (e->operation == id)
return true;
for (unsigned i = 0; i < e->ops.length (); ++i)
if (contains_id (e->ops[i], id))
return true;
return false;
}
if (with_expr *w = dyn_cast <with_expr *> (o))
return (contains_id (w->with, id)
|| contains_id (w->subexpr, id));
if (if_expr *ife = dyn_cast <if_expr *> (o))
return (contains_id (ife->cond, id)
|| contains_id (ife->trueexpr, id)
|| (ife->falseexpr && contains_id (ife->falseexpr, id)));
if (c_expr *ce = dyn_cast<c_expr *> (o))
return ce->capture_ids && ce->capture_ids->get (id->id);
return false;
}
/* 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->location, c->where,
replace_id (c->what, id, with), c->value_match);
}
else if (expr *e = dyn_cast<expr *> (o))
{
expr *ne = new expr (e);
if (e->operation == id)
ne->operation = with;
for (unsigned i = 0; i < e->ops.length (); ++i)
ne->append_op (replace_id (e->ops[i], id, with));
return ne;
}
else if (with_expr *w = dyn_cast <with_expr *> (o))
{
with_expr *nw = new with_expr (w->location);
nw->with = as_a <c_expr *> (replace_id (w->with, id, with));
nw->subexpr = replace_id (w->subexpr, id, with);
return nw;
}
else if (if_expr *ife = dyn_cast <if_expr *> (o))
{
if_expr *nife = new if_expr (ife->location);
nife->cond = as_a <c_expr *> (replace_id (ife->cond, id, with));
nife->trueexpr = replace_id (ife->trueexpr, id, with);
if (ife->falseexpr)
nife->falseexpr = replace_id (ife->falseexpr, id, with);
return nife;
}
/* 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->location,
ce->code, ce->nr_stmts, ids, ce->capture_ids);
}
return o;
}
/* Return true if the binary operator OP is ok for delayed substitution
during for lowering. */
static bool
binary_ok (operator_id *op)
{
switch (op->code)
{
case PLUS_EXPR:
case MINUS_EXPR:
case MULT_EXPR:
case TRUNC_DIV_EXPR:
case CEIL_DIV_EXPR:
case FLOOR_DIV_EXPR:
case ROUND_DIV_EXPR:
case TRUNC_MOD_EXPR:
case CEIL_MOD_EXPR:
case FLOOR_MOD_EXPR:
case ROUND_MOD_EXPR:
case RDIV_EXPR:
case EXACT_DIV_EXPR:
case MIN_EXPR:
case MAX_EXPR:
case BIT_IOR_EXPR:
case BIT_XOR_EXPR:
case BIT_AND_EXPR:
return true;
default:
return false;
}
}
/* 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;
bool can_delay_subst = (sin->kind == simplify::SIMPLIFY);
for (unsigned i = 0; i < n_ids; ++i)
{
if (ids[i]->substitutes.length () > max_n_opers)
max_n_opers = ids[i]->substitutes.length ();
/* Require that all substitutes are of the same kind so that
if we delay substitution to the result op code generation
can look at the first substitute for deciding things like
types of operands. */
enum id_base::id_kind kind = ids[i]->substitutes[0]->kind;
for (unsigned j = 0; j < ids[i]->substitutes.length (); ++j)
if (ids[i]->substitutes[j]->kind != kind)
can_delay_subst = false;
else if (operator_id *op
= dyn_cast <operator_id *> (ids[i]->substitutes[j]))
{
operator_id *op0
= as_a <operator_id *> (ids[i]->substitutes[0]);
if (strcmp (op->tcc, "tcc_comparison") == 0
&& strcmp (op0->tcc, "tcc_comparison") == 0)
;
/* Unfortunately we can't just allow all tcc_binary. */
else if (strcmp (op->tcc, "tcc_binary") == 0
&& strcmp (op0->tcc, "tcc_binary") == 0
&& binary_ok (op)
&& binary_ok (op0))
;
else if ((strcmp (op->id + 1, "SHIFT_EXPR") == 0
|| strcmp (op->id + 1, "ROTATE_EXPR") == 0)
&& (strcmp (op0->id + 1, "SHIFT_EXPR") == 0
|| strcmp (op0->id + 1, "ROTATE_EXPR") == 0))
;
else
can_delay_subst = false;
}
else if (is_a <fn_id *> (ids[i]->substitutes[j]))
;
else
can_delay_subst = false;
}
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;
auto_vec<std::pair<user_id *, id_base *> > subst (n_ids);
bool skip = false;
for (unsigned i = 0; i < n_ids; ++i)
{
user_id *id = ids[i];
id_base *oper = id->substitutes[j % id->substitutes.length ()];
if (oper == null_id
&& (contains_id (match_op, id)
|| contains_id (result_op, id)))
{
skip = true;
break;
}
subst.quick_push (std::make_pair (id, oper));
match_op = replace_id (match_op, id, oper);
if (result_op
&& !can_delay_subst)
result_op = replace_id (result_op, id, oper);
}
if (skip)
continue;
simplify *ns = new simplify (s->kind, s->id, match_op, result_op,
vNULL, s->capture_ids);
ns->for_subst_vec.safe_splice (s->for_subst_vec);
if (result_op
&& can_delay_subst)
ns->for_subst_vec.safe_splice (subst);
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, bool gimple)
{
auto_vec<simplify *> out_simplifiers;
for (unsigned i = 0; i < simplifiers.length (); ++i)
lower_opt_convert (simplifiers[i], out_simplifiers);
simplifiers.truncate (0);
for (unsigned i = 0; i < out_simplifiers.length (); ++i)
lower_commutative (out_simplifiers[i], simplifiers);
out_simplifiers.truncate (0);
if (gimple)
for (unsigned i = 0; i < simplifiers.length (); ++i)
lower_cond (simplifiers[i], out_simplifiers);
else
out_simplifiers.safe_splice (simplifiers);
simplifiers.truncate (0);
for (unsigned i = 0; i < out_simplifiers.length (); ++i)
lower_for (out_simplifiers[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. */
struct dt_simplify;
/* A hash-map collecting semantically equivalent leafs in the decision
tree for splitting out to separate functions. */
struct sinfo
{
dt_simplify *s;
const char *fname;
unsigned cnt;
};
struct sinfo_hashmap_traits : simple_hashmap_traits<pointer_hash<dt_simplify>,
sinfo *>
{
static inline hashval_t hash (const key_type &);
static inline bool equal_keys (const key_type &, const key_type &);
template <typename T> static inline void remove (T &) {}
};
typedef hash_map<void * /* unused */, sinfo *, sinfo_hashmap_traits>
sinfo_map_t;
/* Current simplifier ID we are processing during insertion into the
decision tree. */
static unsigned current_id;
/* Decision tree base class, used for DT_NODE. */
struct dt_node
{
enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
enum dt_type type;
unsigned level;
dt_node *parent;
vec<dt_node *> kids;
/* Statistics. */
unsigned num_leafs;
unsigned total_size;
unsigned max_level;
dt_node (enum dt_type type_, dt_node *parent_)
: type (type_), level (0), parent (parent_), kids (vNULL) {}
dt_node *append_node (dt_node *);
dt_node *append_op (operand *, dt_node *parent, unsigned pos);
dt_node *append_true_op (operand *, dt_node *parent, unsigned pos);
dt_node *append_match_op (operand *, dt_operand *, dt_node *parent,
unsigned pos);
dt_node *append_simplify (simplify *, unsigned, dt_operand **);
virtual void gen (FILE *, int, bool) {}
void gen_kids (FILE *, int, bool);
void gen_kids_1 (FILE *, int, bool,
vec<dt_operand *>, vec<dt_operand *>, vec<dt_operand *>,
vec<dt_operand *>, vec<dt_operand *>, vec<dt_node *>);
void analyze (sinfo_map_t &);
};
/* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
struct dt_operand : public dt_node
{
operand *op;
dt_operand *match_dop;
unsigned pos;
bool value_match;
unsigned for_id;
dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_,
dt_operand *parent_, unsigned pos_)
: dt_node (type, parent_), op (op_), match_dop (match_dop_),
pos (pos_), value_match (false), for_id (current_id) {}
void gen (FILE *, int, bool);
unsigned gen_predicate (FILE *, int, const char *, bool);
unsigned gen_match_op (FILE *, int, const char *, bool);
unsigned gen_gimple_expr (FILE *, int);
unsigned gen_generic_expr (FILE *, int, 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;
sinfo *info;
dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
: dt_node (DT_SIMPLIFY, NULL), s (s_), pattern_no (pattern_no_),
indexes (indexes_), info (NULL) {}
void gen_1 (FILE *, int, bool, operand *);
void gen (FILE *f, int, 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
|| n->type == dt_node::DT_TRUE);
}
template<>
template<>
inline bool
is_a_helper <dt_simplify *>::test (dt_node *n)
{
return n->type == dt_node::DT_SIMPLIFY;
}
/* A container for the actual decision tree. */
struct decision_tree
{
dt_node *root;
void insert (struct simplify *, unsigned);
void gen (FILE *f, bool gimple);
void print (FILE *f = stderr);
decision_tree () { root = new dt_node (dt_node::DT_NODE, NULL); }
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
&& e1->is_generic == e2->is_generic);
}
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)
return true;
if (n1->type == dt_node::DT_TRUE)
return false;
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)
&& ((as_a<dt_operand *> (n1))->value_match
== (as_a<dt_operand *> (n2))->value_match));
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)
{
/* We can merge adjacent DT_TRUE. */
if (p->type == dt_node::DT_TRUE
&& !ops.is_empty ()
&& ops.last ()->type == dt_node::DT_TRUE)
return ops.last ();
dt_operand *true_node = NULL;
for (int i = ops.length () - 1; i >= 0; --i)
{
/* But we can't merge across DT_TRUE nodes as they serve as
pattern order barriers to make sure that patterns apply
in order of appearance in case multiple matches are possible. */
if (ops[i]->type == dt_node::DT_TRUE)
{
if (! true_node
|| as_a <dt_operand *> (ops[i])->for_id > true_node->for_id)
true_node = as_a <dt_operand *> (ops[i]);
}
if (decision_tree::cmp_node (ops[i], p))
{
/* Unless we are processing the same pattern or the blocking
pattern is before the one we are going to merge with. */
if (true_node
&& true_node->for_id != current_id
&& true_node->for_id > as_a <dt_operand *> (ops[i])->for_id)
{
if (verbose >= 1)
{
source_location p_loc = 0;
if (p->type == dt_node::DT_OPERAND)
p_loc = as_a <dt_operand *> (p)->op->location;
source_location op_loc = 0;
if (ops[i]->type == dt_node::DT_OPERAND)
op_loc = as_a <dt_operand *> (ops[i])->op->location;
source_location true_loc = 0;
true_loc = true_node->op->location;
warning_at (p_loc,
"failed to merge decision tree node");
warning_at (op_loc,
"with the following");
warning_at (true_loc,
"because of the following which serves as ordering "
"barrier");
}
return NULL;
}
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;
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 (operand *op, dt_node *parent, unsigned pos)
{
dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
dt_operand *n = new dt_operand (DT_TRUE, op, 0, parent_, pos);
return append_node (n);
}
/* Append a DT_MATCH decision tree node. */
dt_node *
dt_node::append_match_op (operand *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, op, 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);
for (unsigned i = 0; i < kids.length (); ++i)
if (dt_simplify *s2 = dyn_cast <dt_simplify *> (kids[i]))
{
warning_at (s->match->location, "duplicate pattern");
warning_at (s2->s->match->location, "previous pattern defined here");
print_operand (s->match, stderr);
fprintf (stderr, "\n");
}
return append_node (n);
}
/* Analyze the node and its children. */
void
dt_node::analyze (sinfo_map_t &map)
{
num_leafs = 0;
total_size = 1;
max_level = level;
if (type == DT_SIMPLIFY)
{
/* Populate the map of equivalent simplifies. */
dt_simplify *s = as_a <dt_simplify *> (this);
bool existed;
sinfo *&si = map.get_or_insert (s, &existed);
if (!existed)
{
si = new sinfo;
si->s = s;
si->cnt = 1;
si->fname = NULL;
}
else
si->cnt++;
s->info = si;
num_leafs = 1;
return;
}
for (unsigned i = 0; i < kids.length (); ++i)
{
kids[i]->analyze (map);
num_leafs += kids[i]->num_leafs;
total_size += kids[i]->total_size;
max_level = MAX (max_level, kids[i]->max_level);
}
}
/* 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 (o, 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, 0, 0);
elm = decision_tree::find_node (p->kids, &temp);
if (elm == 0)
{
dt_operand temp (dt_node::DT_MATCH, 0, match_op, 0, 0);
temp.value_match = c->value_match;
elm = decision_tree::find_node (p->kids, &temp);
}
}
else
{
dt_operand temp (dt_node::DT_OPERAND, c->what, 0, 0, 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 (o, indexes[capt_index], parent, pos);
as_a <dt_operand *>(p)->value_match = c->value_match;
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)
{
current_id = s->id;
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, " } ");
}
if (is_a <dt_operand *> (p))
fprintf (f, " [%u]", as_a <dt_operand *> (p)->for_id);
}
fprintf (stderr, " (%p, %p), %u, %u\n",
(void *) p, (void *) p->parent, 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);
}
/* For GENERIC we have to take care of wrapping multiple-used
expressions with side-effects in save_expr and preserve side-effects
of expressions with omit_one_operand. Analyze captures in
match, result and with expressions and perform early-outs
on the outermost match expression operands for cases we cannot
handle. */
struct capture_info
{
capture_info (simplify *s, operand *, bool);
void walk_match (operand *o, unsigned toplevel_arg, bool, bool);
bool walk_result (operand *o, bool, operand *);
void walk_c_expr (c_expr *);
struct cinfo
{
bool expr_p;
bool cse_p;
bool force_no_side_effects_p;
bool force_single_use;
bool cond_expr_cond_p;
unsigned long toplevel_msk;
unsigned match_use_count;
unsigned result_use_count;
unsigned same_as;
capture *c;
};
auto_vec<cinfo> info;
unsigned long force_no_side_effects;
bool gimple;
};
/* Analyze captures in S. */
capture_info::capture_info (simplify *s, operand *result, bool gimple_)
{
gimple = gimple_;
expr *e;
if (s->kind == simplify::MATCH)
{
force_no_side_effects = -1;
return;
}
force_no_side_effects = 0;
info.safe_grow_cleared (s->capture_max + 1);
for (int i = 0; i <= s->capture_max; ++i)
info[i].same_as = i;
e = as_a <expr *> (s->match);
for (unsigned i = 0; i < e->ops.length (); ++i)
walk_match (e->ops[i], i,
(i != 0 && *e->operation == COND_EXPR)
|| *e->operation == TRUTH_ANDIF_EXPR
|| *e->operation == TRUTH_ORIF_EXPR,
i == 0
&& (*e->operation == COND_EXPR
|| *e->operation == VEC_COND_EXPR));
walk_result (s->result, false, result);
}
/* Analyze captures in the match expression piece O. */
void
capture_info::walk_match (operand *o, unsigned toplevel_arg,
bool conditional_p, bool cond_expr_cond_p)
{
if (capture *c = dyn_cast <capture *> (o))
{
unsigned where = c->where;
info[where].match_use_count++;
info[where].toplevel_msk |= 1 << toplevel_arg;
info[where].force_no_side_effects_p |= conditional_p;
info[where].cond_expr_cond_p |= cond_expr_cond_p;
if (!info[where].c)
info[where].c = c;
if (!c->what)
return;
/* Recurse to exprs and captures. */
if (is_a <capture *> (c->what)
|| is_a <expr *> (c->what))
walk_match (c->what, toplevel_arg, conditional_p, false);
/* We need to look past multiple captures to find a captured
expression as with conditional converts two captures
can be collapsed onto the same expression. Also collect
what captures capture the same thing. */
while (c->what && is_a <capture *> (c->what))
{
c = as_a <capture *> (c->what);
if (info[c->where].same_as != c->where
&& info[c->where].same_as != info[where].same_as)
fatal_at (c->location, "cannot handle this collapsed capture");
info[c->where].same_as = info[where].same_as;
}
/* Mark expr (non-leaf) captures and forced single-use exprs. */
expr *e;
if (c->what
&& (e = dyn_cast <expr *> (c->what)))
{
/* Zero-operand expression captures like ADDR_EXPR@0 are
similar as predicates -- if they are not mentioned in
the result we have to force them to have no side-effects. */
if (e->ops.length () != 0)
info[where].expr_p = true;
info[where].force_single_use |= e->force_single_use;
}
}
else if (expr *e = dyn_cast <expr *> (o))
{
for (unsigned i = 0; i < e->ops.length (); ++i)
{
bool cond_p = conditional_p;
bool cond_expr_cond_p = false;
if (i != 0 && *e->operation == COND_EXPR)
cond_p = true;
else if (*e->operation == TRUTH_ANDIF_EXPR
|| *e->operation == TRUTH_ORIF_EXPR)
cond_p = true;
if (i == 0
&& (*e->operation == COND_EXPR
|| *e->operation == VEC_COND_EXPR))
cond_expr_cond_p = true;
walk_match (e->ops[i], toplevel_arg, cond_p, cond_expr_cond_p);
}
}
else if (is_a <predicate *> (o))
{
/* Mark non-captured leafs toplevel arg for checking. */
force_no_side_effects |= 1 << toplevel_arg;
if (verbose >= 1
&& !gimple)
warning_at (o->location,
"forcing no side-effects on possibly lost leaf");
}
else
gcc_unreachable ();
}
/* Analyze captures in the result expression piece O. Return true
if RESULT was visited in one of the children. Only visit
non-if/with children if they are rooted on RESULT. */
bool
capture_info::walk_result (operand *o, bool conditional_p, operand *result)
{
if (capture *c = dyn_cast <capture *> (o))
{
unsigned where = info[c->where].same_as;
info[where].result_use_count++;
/* If we substitute an expression capture we don't know
which captures this will end up using (well, we don't
compute that). Force the uses to be side-effect free
which means forcing the toplevels that reach the
expression side-effect free. */
if (info[where].expr_p)
force_no_side_effects |= info[where].toplevel_msk;
/* Mark CSE capture uses as forced to have no side-effects. */
if (c->what
&& is_a <expr *> (c->what))
{
info[where].cse_p = true;
walk_result (c->what, true, result);
}
}
else if (expr *e = dyn_cast <expr *> (o))
{
id_base *opr = e->operation;
if (user_id *uid = dyn_cast <user_id *> (opr))
opr = uid->substitutes[0];
for (unsigned i = 0; i < e->ops.length (); ++i)
{
bool cond_p = conditional_p;
if (i != 0 && *e->operation == COND_EXPR)
cond_p = true;
else if (*e->operation == TRUTH_ANDIF_EXPR
|| *e->operation == TRUTH_ORIF_EXPR)
cond_p = true;
walk_result (e->ops[i], cond_p, result);
}
}
else if (if_expr *e = dyn_cast <if_expr *> (o))
{
/* 'if' conditions should be all fine. */
if (e->trueexpr == result)
{
walk_result (e->trueexpr, false, result);
return true;
}
if (e->falseexpr == result)
{
walk_result (e->falseexpr, false, result);
return true;
}
bool res = false;
if (is_a <if_expr *> (e->trueexpr)
|| is_a <with_expr *> (e->trueexpr))
res |= walk_result (e->trueexpr, false, result);
if (e->falseexpr
&& (is_a <if_expr *> (e->falseexpr)
|| is_a <with_expr *> (e->falseexpr)))
res |= walk_result (e->falseexpr, false, result);
return res;
}
else if (with_expr *e = dyn_cast <with_expr *> (o))
{
bool res = (e->subexpr == result);
if (res
|| is_a <if_expr *> (e->subexpr)
|| is_a <with_expr *> (e->subexpr))
res |= walk_result (e->subexpr, false, result);
if (res)
walk_c_expr (e->with);
return res;
}
else if (c_expr *e = dyn_cast <c_expr *> (o))
walk_c_expr (e);
else
gcc_unreachable ();
return false;
}
/* Look for captures in the C expr E. */
void
capture_info::walk_c_expr (c_expr *e)
{
/* Give up for C exprs mentioning captures not inside TREE_TYPE,
TREE_REAL_CST, TREE_CODE or a predicate where they cannot
really escape through. */
unsigned p_depth = 0;
for (unsigned i = 0; i < e->code.length (); ++i)
{
const cpp_token *t = &e->code[i];
const cpp_token *n = i < e->code.length () - 1 ? &e->code[i+1] : NULL;
id_base *id;
if (t->type == CPP_NAME
&& (strcmp ((const char *)CPP_HASHNODE
(t->val.node.node)->ident.str, "TREE_TYPE") == 0
|| strcmp ((const char *)CPP_HASHNODE
(t->val.node.node)->ident.str, "TREE_CODE") == 0
|| strcmp ((const char *)CPP_HASHNODE
(t->val.node.node)->ident.str, "TREE_REAL_CST") == 0
|| ((id = get_operator ((const char *)CPP_HASHNODE
(t->val.node.node)->ident.str))
&& is_a <predicate_id *> (id)))
&& n->type == CPP_OPEN_PAREN)
p_depth++;
else if (t->type == CPP_CLOSE_PAREN
&& p_depth > 0)
p_depth--;
else if (p_depth == 0
&& t->type == CPP_ATSIGN
&& (n->type == CPP_NUMBER
|| n->type == CPP_NAME)
&& !(n->flags & PREV_WHITE))
{
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;
unsigned *where = e->capture_ids->get(id);
if (! where)
fatal_at (n, "unknown capture id '%s'", id);
info[info[*where].same_as].force_no_side_effects_p = true;
if (verbose >= 1
&& !gimple)
warning_at (t, "capture escapes");
}
}
}
/* 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 operand POS of OP from the
various sources. */
static const char *
get_operand_type (id_base *op, unsigned pos,
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 if (*op == COND_EXPR
&& pos == 0)
return "boolean_type_node";
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, int indent, const char *dest, bool gimple,
int depth, const char *in_type, capture_info *cinfo,
dt_operand **indexes, int)
{
id_base *opr = operation;
/* When we delay operator substituting during lowering of fors we
make sure that for code-gen purposes the effects of each substitute
are the same. Thus just look at that. */
if (user_id *uid = dyn_cast <user_id *> (opr))
opr = uid->substitutes[0];
bool conversion_p = is_conversion (opr);
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 (*opr == REALPART_EXPR
|| *opr == 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 *> (opr)
&& !strcmp (as_a <operator_id *> (opr)->tcc, "tcc_comparison"))
{
/* comparisons use boolean_type_node (or what gets in), but
their operands need to figure out the types themselves. */
if (in_type)
type = in_type;
else
{
sprintf (optype, "boolean_type_node");
type = optype;
}
in_type = NULL;
}
else if (*opr == COND_EXPR
|| *opr == VEC_COND_EXPR)
{
/* Conditions are of the same type as their first alternative. */
sprintf (optype, "TREE_TYPE (ops%d[1])", depth);
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_at (location, "cannot determine type of operand");
fprintf_indent (f, indent, "{\n");
indent += 2;
fprintf_indent (f, indent, "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 (opr, i, in_type, expr_type,
i == 0 ? NULL : op0type);
ops[i]->gen_transform (f, indent, dest, gimple, depth + 1, optype,
cinfo, indexes,
(*opr == COND_EXPR
|| *opr == VEC_COND_EXPR) && i == 0 ? 1 : 2);
}
const char *opr_name;
if (*operation == CONVERT_EXPR)
opr_name = "NOP_EXPR";
else
opr_name = operation->id;
if (gimple)
{
if (*opr == CONVERT_EXPR)
{
fprintf_indent (f, indent,
"if (%s != TREE_TYPE (ops%d[0])\n",
type, depth);
fprintf_indent (f, indent,
" && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
type, depth);
fprintf_indent (f, indent + 2, "{\n");
indent += 4;
}
/* ??? Building a stmt can fail for various reasons here, seq being
NULL or the stmt referencing SSA names occuring in abnormal PHIs.
So if we fail here we should continue matching other patterns. */
fprintf_indent (f, indent, "code_helper tem_code = %s;\n", opr_name);
fprintf_indent (f, indent, "tree tem_ops[3] = { ");
for (unsigned i = 0; i < ops.length (); ++i)
fprintf (f, "ops%d[%u]%s", depth, i,
i == ops.length () - 1 ? " };\n" : ", ");
fprintf_indent (f, indent,
"gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
ops.length (), type);
fprintf_indent (f, indent,
"res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
type);
fprintf_indent (f, indent,
"if (!res) return false;\n");
if (*opr == CONVERT_EXPR)
{
indent -= 4;
fprintf_indent (f, indent, " }\n");
fprintf_indent (f, indent, "else\n");
fprintf_indent (f, indent, " res = ops%d[0];\n", depth);
}
}
else
{
if (*opr == CONVERT_EXPR)
{
fprintf_indent (f, indent, "if (TREE_TYPE (ops%d[0]) != %s)\n",
depth, type);
indent += 2;
}
if (opr->kind == id_base::CODE)
fprintf_indent (f, indent, "res = fold_build%d_loc (loc, %s, %s",
ops.length(), opr_name, type);
else
{
fprintf_indent (f, indent, "{\n");
fprintf_indent (f, indent, " res = maybe_build_call_expr_loc (loc, "
"%s, %s, %d", opr_name, type, ops.length());
}
for (unsigned i = 0; i < ops.length (); ++i)
fprintf (f, ", ops%d[%u]", depth, i);
fprintf (f, ");\n");
if (opr->kind != id_base::CODE)
{
fprintf_indent (f, indent, " if (!res)\n");
fprintf_indent (f, indent, " return NULL_TREE;\n");
fprintf_indent (f, indent, "}\n");
}
if (*opr == CONVERT_EXPR)
{
indent -= 2;
fprintf_indent (f, indent, "else\n");
fprintf_indent (f, indent, " res = ops%d[0];\n", depth);
}
}
fprintf_indent (f, indent, "%s = res;\n", dest);
indent -= 2;
fprintf_indent (f, indent, "}\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, int indent, const char *dest,
bool, int, const char *, capture_info *,
dt_operand **, int)
{
if (dest && nr_stmts == 1)
fprintf_indent (f, indent, "%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;
unsigned *cid = capture_ids->get (id);
if (!cid)
fatal_at (token, "unknown capture id");
fprintf (f, "captures[%u]", *cid);
++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++;
fputc ('\n', f);
if (dest && stmt_nr == nr_stmts)
fprintf_indent (f, indent, "%s = ", dest);
}
}
}
/* Generate transform code for a capture. */
void
capture::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
int depth, const char *in_type, capture_info *cinfo,
dt_operand **indexes, int cond_handling)
{
if (what && is_a<expr *> (what))
{
if (indexes[where] == 0)
{
char buf[20];
sprintf (buf, "captures[%u]", where);
what->gen_transform (f, indent, buf, gimple, depth, in_type,
cinfo, NULL);
}
}
/* If in GENERIC some capture is used multiple times, unshare it except
when emitting the last use. */
if (!gimple
&& cinfo->info.exists ()
&& cinfo->info[cinfo->info[where].same_as].result_use_count > 1)
{
fprintf_indent (f, indent, "%s = unshare_expr (captures[%u]);\n",
dest, where);
cinfo->info[cinfo->info[where].same_as].result_use_count--;
}
else
fprintf_indent (f, indent, "%s = captures[%u];\n", dest, where);
/* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
with substituting a capture of that. */
if (gimple
&& cond_handling != 0
&& cinfo->info[where].cond_expr_cond_p)
{
/* If substituting into a cond_expr condition, unshare. */
if (cond_handling == 1)
fprintf_indent (f, indent, "%s = unshare_expr (%s);\n", dest, dest);
/* If substituting elsewhere we might need to decompose it. */
else if (cond_handling == 2)
{
/* ??? Returning false here will also not allow any other patterns
to match unless this generator was split out. */
fprintf_indent (f, indent, "if (COMPARISON_CLASS_P (%s))\n", dest);
fprintf_indent (f, indent, " {\n");
fprintf_indent (f, indent, " if (!seq) return false;\n");
fprintf_indent (f, indent, " %s = gimple_build (seq,"
" TREE_CODE (%s),"
" TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
" TREE_OPERAND (%s, 1));\n",
dest, dest, dest, dest, dest);
fprintf_indent (f, indent, " }\n");
}
}
}
/* 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 as_a <dt_operand *> (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, int indent, 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_indent (f, indent, "if (gimple_%s (%s, valueize))\n",
p->p->id, opname);
else
fprintf_indent (f, indent, "if (tree_%s (%s))\n", p->p->id, opname);
}
else
fprintf_indent (f, indent, "if (%s (%s))\n", p->p->id, opname);
fprintf_indent (f, indent + 2, "{\n");
return 1;
}
/* Generate matching code for the decision tree operand which is
a capture-match. */
unsigned
dt_operand::gen_match_op (FILE *f, int indent, const char *opname, bool)
{
char match_opname[20];
match_dop->get_name (match_opname);
if (value_match)
fprintf_indent (f, indent, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
opname, match_opname, opname, match_opname);
else
fprintf_indent (f, indent, "if (%s == %s || (operand_equal_p (%s, %s, 0) "
"&& types_match (%s, %s)))\n",
opname, match_opname, opname, match_opname,
opname, match_opname);
fprintf_indent (f, indent + 2, "{\n");
return 1;
}
/* Generate GIMPLE matching code for the decision tree operand. */
unsigned
dt_operand::gen_gimple_expr (FILE *f, int indent)
{
expr *e = static_cast<expr *> (op);
id_base *id = e->operation;
unsigned n_ops = e->ops.length ();
unsigned n_braces = 0;
for (unsigned i = 0; i < n_ops; ++i)
{
char child_opname[20];
gen_opname (child_opname, i);
if (id->kind == id_base::CODE)
{
if (e->is_generic
|| *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. */
if (e->is_generic)
{
char opname[20];
get_name (opname);
fprintf_indent (f, indent,
"tree %s = TREE_OPERAND (%s, %i);\n",
child_opname, opname, i);
}
else
fprintf_indent (f, indent,
"tree %s = TREE_OPERAND "
"(gimple_assign_rhs1 (def), %i);\n",
child_opname, i);
fprintf_indent (f, indent,
"if ((TREE_CODE (%s) == SSA_NAME\n",
child_opname);
fprintf_indent (f, indent,
" || is_gimple_min_invariant (%s)))\n",
child_opname);
fprintf_indent (f, indent,
" {\n");
indent += 4;
n_braces++;
fprintf_indent (f, indent,
"%s = do_valueize (valueize, %s);\n",
child_opname, child_opname);
continue;
}
else
fprintf_indent (f, indent,
"tree %s = gimple_assign_rhs%u (def);\n",
child_opname, i + 1);
}
else
fprintf_indent (f, indent,
"tree %s = gimple_call_arg (def, %u);\n",
child_opname, i);
fprintf_indent (f, indent,
"%s = do_valueize (valueize, %s);\n",
child_opname, child_opname);
}
/* While the toplevel operands are canonicalized by the caller
after valueizing operands of sub-expressions we have to
re-canonicalize operand order. */
if (operator_id *code = dyn_cast <operator_id *> (id))
{
/* ??? We can't canonicalize tcc_comparison operands here
because that requires changing the comparison code which
we already matched... */
if (commutative_tree_code (code->code)
|| commutative_ternary_tree_code (code->code))
{
char child_opname0[20], child_opname1[20];
gen_opname (child_opname0, 0);
gen_opname (child_opname1, 1);
fprintf_indent (f, indent,
"if (tree_swap_operands_p (%s, %s))\n",
child_opname0, child_opname1);
fprintf_indent (f, indent,
" std::swap (%s, %s);\n",
child_opname0, child_opname1);
}
}
return n_braces;
}
/* Generate GENERIC matching code for the decision tree operand. */
unsigned
dt_operand::gen_generic_expr (FILE *f, int indent, 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_indent (f, indent, "tree %s = TREE_OPERAND (%s, %u);\n",
child_opname, opname, i);
else
fprintf_indent (f, indent, "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, int indent, 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;
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
&& (!gimple || !(*e->operation == CONSTRUCTOR)))
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 && !e->is_generic)
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_SIMPLIFY)
others.safe_push (kids[i]);
else if (kids[i]->type == dt_node::DT_MATCH
|| kids[i]->type == dt_node::DT_TRUE)
{
/* A DT_TRUE operand serves as a barrier - generate code now
for what we have collected sofar.
Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
dependent matches to get out-of-order. Generate code now
for what we have collected sofar. */
gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
fns, generic_fns, preds, others);
/* And output the true operand itself. */
kids[i]->gen (f, indent, gimple);
gimple_exprs.truncate (0);
generic_exprs.truncate (0);
fns.truncate (0);
generic_fns.truncate (0);
preds.truncate (0);
others.truncate (0);
}
else
gcc_unreachable ();
}
/* Generate code for the remains. */
gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
fns, generic_fns, preds, others);
}
/* Generate matching code for the children of the decision tree node. */
void
dt_node::gen_kids_1 (FILE *f, int indent, bool gimple,
vec<dt_operand *> gimple_exprs,
vec