===================================================================
@@ -116,7 +116,7 @@ END_BUILTINS
struct id_base : typed_free_remove<id_base>
{
- enum id_kind { CODE, FN } kind;
+ enum id_kind { CODE, FN, USER_DEFINED } kind;
id_base (id_kind, const char *);
@@ -135,6 +135,7 @@ id_base::hash (const value_type *op)
{
return op->hashval;
}
+
inline int
id_base::equal (const value_type *op1,
const compare_type *op2)
@@ -169,6 +170,7 @@ struct fn_id : public id_base
enum built_in_function fn;
};
+
static void
add_operator (enum tree_code code, const char *id,
const char *tcc, unsigned nargs)
@@ -217,7 +219,7 @@ struct predicate : public operand
};
struct e_operation {
- e_operation (const char *id, bool is_commutative_ = false);
+ e_operation (const char *id, bool is_commutative_ = false, bool add_new_id = true);
id_base *op;
bool is_commutative;
};
@@ -254,11 +256,10 @@ struct capture : public operand
virtual void gen_transform (FILE *f, const char *, bool);
};
-
-e_operation::e_operation (const char *id, bool is_commutative_)
+e_operation::e_operation (const char *id, bool is_commutative_, bool add_new_id)
{
- id_base tem (id_base::CODE, id);
is_commutative = is_commutative_;
+ id_base tem (id_base::CODE, id);
op = operators.find_with_hash (&tem, tem.hashval);
if (op)
@@ -287,19 +288,23 @@ e_operation::e_operation (const char *id
return;
}
- fatal ("expected operator, got %s", id);
+ if (add_new_id == false)
+ fatal ("%s is not an operator/built-in function", id);
+
+ op = new id_base (id_base::USER_DEFINED, id);
+ operators.find_slot_with_hash (op, op->hashval, INSERT);
}
struct simplify {
simplify (const char *name_,
- vec<operand *> matchers_, source_location match_location_,
+ operand *match_, source_location match_location_,
struct operand *ifexpr_, source_location ifexpr_location_,
struct operand *result_, source_location result_location_)
- : name (name_), matchers (matchers_), match_location (match_location_),
+ : name (name_), match (match_), match_location (match_location_),
ifexpr (ifexpr_), ifexpr_location (ifexpr_location_),
result (result_), result_location (result_location_) {}
const char *name;
- vec<operand *> matchers; // vector to hold commutative expressions
+ operand *match;
source_location match_location;
struct operand *ifexpr;
source_location ifexpr_location;
@@ -452,19 +457,9 @@ print_operand (operand *o, FILE *f = std
void
print_matches (struct simplify *s, FILE *f = stderr)
{
- if (s->matchers.length () == 1)
- return;
-
fprintf (f, "for expression: ");
- print_operand (s->matchers[0], f); // s->matchers[0] is equivalent to original expression
+ print_operand (s->match, f);
putc ('\n', f);
-
- fprintf (f, "commutative expressions:\n");
- for (unsigned i = 0; i < s->matchers.length (); ++i)
- {
- print_operand (s->matchers[i], f);
- putc ('\n', f);
- }
}
void
@@ -552,6 +547,104 @@ commutate (operand *op)
return ret;
}
+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 (s->name, matchers[i], s->match_location,
+ s->ifexpr, s->ifexpr_location,
+ s->result, s->result_location);
+ simplifiers.safe_push (ns);
+ }
+}
+
+void
+check_operator (id_base *op, unsigned n_ops, const cpp_token *token = 0)
+{
+ if (!op)
+ return;
+
+ if (op->kind != id_base::CODE)
+ return;
+
+ operator_id *opr = static_cast<operator_id *> (op);
+ if (opr->get_required_nargs () == n_ops)
+ return;
+
+ if (token)
+ fatal_at (token, "%s expects %u operands, got %u operands", opr->id, opr->get_required_nargs (), n_ops);
+ else
+ fatal ("%s expects %u operands, got %u operands", opr->id, opr->get_required_nargs (), n_ops);
+}
+
+operand *
+replace_id (operand *o, const char *user_id, const char *oper)
+{
+ if (o->type == operand::OP_CAPTURE)
+ {
+ capture *c = static_cast<capture *> (o);
+ if (!c->what)
+ return c;
+ capture *nc = new capture (c->where, replace_id (c->what, user_id, oper));
+ return nc;
+ }
+
+ if (o->type != operand::OP_EXPR)
+ return o;
+
+ expr *e = static_cast<expr *> (o);
+ expr *ne;
+
+ if (e->operation->op->kind == id_base::USER_DEFINED && strcmp (e->operation->op->id, user_id) == 0)
+ {
+ struct e_operation *operation = new e_operation (oper, e->operation->is_commutative, false);
+ check_operator (operation->op, e->ops.length ());
+ ne = new expr (operation);
+ }
+ else
+ ne = new expr (e->operation);
+
+ for (unsigned i = 0; i < e->ops.length (); ++i)
+ ne->append_op (replace_id (e->ops[i], user_id, oper));
+
+ return ne;
+}
+
+void
+check_no_user_id (operand *o)
+{
+ if (o->type == operand::OP_CAPTURE)
+ {
+ capture *c = static_cast<capture *> (o);
+ if (c->what && c->what->type == operand::OP_EXPR)
+ {
+ o = c->what;
+ goto check_expr;
+ }
+ return;
+ }
+
+ if (o->type != operand::OP_EXPR)
+ return;
+
+check_expr:
+ expr *e = static_cast<expr *> (o);
+ if (e->operation->op->kind == id_base::USER_DEFINED)
+ fatal ("%s is not defined in for", e->operation->op->id);
+
+ for (unsigned i = 0; i < e->ops.length (); ++i)
+ check_no_user_id (e->ops[i]);
+}
+
+void
+check_no_user_id (simplify *s)
+{
+ check_no_user_id (s->match);
+ check_no_user_id (s->result);
+}
+
/* Code gen off the AST. */
void
@@ -828,17 +921,14 @@ decision_tree::insert (struct simplify *
{
dt_operand *indexes[dt_simplify::capture_max];
- for (unsigned i = 0; i < s->matchers.length (); ++i)
- {
- if (s->matchers[i]->type != operand::OP_EXPR)
- continue;
+ if (s->match->type != operand::OP_EXPR)
+ return;
- for (unsigned j = 0; j < dt_simplify::capture_max; ++j)
- indexes[j] = 0;
+ for (unsigned j = 0; j < dt_simplify::capture_max; ++j)
+ indexes[j] = 0;
- dt_node *p = decision_tree::insert_operand (root, s->matchers[i], indexes);
- p->append_simplify (s, pattern_no, indexes);
- }
+ dt_node *p = decision_tree::insert_operand (root, s->match, indexes);
+ p->append_simplify (s, pattern_no, indexes);
}
void
@@ -1707,6 +1797,16 @@ get_ident (cpp_reader *r)
return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str;
}
+static void
+eat_ident (cpp_reader *r, const char *s)
+{
+ const cpp_token *token = expect (r, CPP_NAME);
+ const char *t = (const char *) CPP_HASHNODE (token->val.node.node)->ident.str;
+
+ if (strcmp (s, t))
+ 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. */
@@ -1735,6 +1835,7 @@ parse_capture (cpp_reader *r, operand *o
return new capture (get_number (r), op);
}
+
/* Parse
expr = (operation[capture] op...) */
static struct operand *
@@ -1774,13 +1875,7 @@ parse_expr (cpp_reader *r)
const cpp_token *token = peek (r);
if (token->type == CPP_CLOSE_PAREN)
{
- if (e->operation->op->kind == id_base::CODE)
- {
- operator_id *opr = static_cast <operator_id *> (e->operation->op);
- if (e->ops.length () != opr->get_required_nargs ())
- fatal_at (token, "got %d operands instead of the required %d",
- e->ops.length (), opr->get_required_nargs ());
- }
+ check_operator (e->operation->op, e->ops.length (), token);
if (is_commutative)
{
if (e->ops.length () == 2)
@@ -1877,6 +1972,7 @@ parse_op (cpp_reader *r)
return op;
}
+
/* Parse
(define_match_and_simplify "<ident>"
<op> <op>) */
@@ -1912,10 +2008,44 @@ parse_match_and_simplify (cpp_reader *r,
ifexpr = parse_c_expr (r, CPP_OPEN_PAREN);
}
token = peek (r);
- return new simplify (id, commutate (match), match_location,
+ return new simplify (id, match, match_location,
ifexpr, ifexpr_location, parse_op (r), token->src_loc);
}
+void
+parse_for (cpp_reader *r, source_location match_location, vec<simplify *>& simplifiers)
+{
+ const char *user_id = get_ident (r);
+ eat_ident (r, "in");
+ void parse_pattern (cpp_reader *, vec<simplify *>&);
+
+ vec<const char *> opers = vNULL;
+
+ while (1)
+ {
+ const cpp_token *token = peek (r);
+ if (token->type != CPP_NAME)
+ break;
+ opers.safe_push (get_ident (r));
+ }
+
+ vec<simplify *> for_simplifiers = vNULL;
+ parse_pattern (r, for_simplifiers);
+
+ for (unsigned i = 0; i < opers.length (); ++i)
+ {
+ for (unsigned j = 0; j < for_simplifiers.length (); ++j)
+ {
+ simplify *s = for_simplifiers[j];
+ operand *match_op = replace_id (s->match, user_id, opers[i]);
+ operand *result_op = replace_id (s->result, user_id, opers[i]);
+ simplify *ns = new simplify (s->name, match_op, s->match_location,
+ s->ifexpr, s->ifexpr_location,
+ result_op, s->result_location);
+ simplifiers.safe_push (ns);
+ }
+ }
+}
static size_t
round_alloc_size (size_t s)
@@ -1923,6 +2053,23 @@ round_alloc_size (size_t s)
return s;
}
+void
+parse_pattern (cpp_reader *r, vec<simplify *>& simplifiers)
+{
+ /* All clauses start with '('. */
+ eat_token (r, CPP_OPEN_PAREN);
+ const cpp_token *token = peek (r);
+ const char *id = get_ident (r);
+ if (strcmp (id, "match_and_simplify") == 0)
+ simplifiers.safe_push (parse_match_and_simplify (r, token->src_loc));
+ else if (strcmp (id, "for") == 0)
+ parse_for (r, token->src_loc, simplifiers);
+ else
+ fatal_at (token, "expected 'match_and_simplify' or 'for'");
+
+ eat_token (r, CPP_CLOSE_PAREN);
+}
+
int
main(int argc, char **argv)
{
@@ -1974,42 +2121,35 @@ main(int argc, char **argv)
vec<simplify *> simplifiers = vNULL;
- do
- {
- token = peek (r);
- if (token->type == CPP_EOF)
- break;
-
- /* All clauses start with '('. */
- eat_token (r, CPP_OPEN_PAREN);
-
- const char *id = get_ident (r);
- if (strcmp (id, "match_and_simplify") == 0)
- simplifiers.safe_push (parse_match_and_simplify (r, token->src_loc));
- else
- fatal_at (token, "expected 'match_and_simplify'");
+ while (peek (r)->type != CPP_EOF)
+ parse_pattern (r, simplifiers);
- eat_token (r, CPP_CLOSE_PAREN);
+ for (unsigned i = 0; i < simplifiers.length (); ++i)
+ {
+ fprintf (stderr, "pattern = %u\n", i);
+ check_no_user_id (simplifiers[i]);
}
- while (1);
-
+ vec<simplify *> out_simplifiers = vNULL;
for (unsigned i = 0; i < simplifiers.length (); ++i)
- print_matches (simplifiers[i]);
+ lower_commutative (simplifiers[i], out_simplifiers);
+
+ for (unsigned i = 0; i < out_simplifiers.length (); ++i)
+ print_matches (out_simplifiers[i]);
decision_tree dt;
- for (unsigned i = 0; i < simplifiers.length (); ++i)
- dt.insert (simplifiers[i], i);
+ for (unsigned i = 0; i < out_simplifiers.length (); ++i)
+ dt.insert (out_simplifiers[i], i);
dt.print (stderr);
if (gimple)
{
- write_header (stdout, simplifiers, "gimple-match-head.c");
+ write_header (stdout, out_simplifiers, "gimple-match-head.c");
dt.gen_gimple (stdout);
}
else
{
- write_header (stdout, simplifiers, "generic-match-head.c");
+ write_header (stdout, out_simplifiers, "generic-match-head.c");
dt.gen_generic (stdout);
}
===================================================================
@@ -22,29 +22,26 @@ along with GCC; see the file COPYING3.
<http://www.gnu.org/licenses/>. */
/* Simple constant foldings to substitute gimple_fold_stmt_to_constant_2. */
-(match_and_simplify
- (plus @0 integer_zerop)
- @0)
-(match_and_simplify
- (pointer_plus @0 integer_zerop)
- @0)
-(match_and_simplify
- (minus @0 integer_zerop)
- @0)
+(for op in plus pointer_plus minus bit_ior bit_xor
+ (match_and_simplify
+ (op @0 integer_zerop)
+ @0))
+
(match_and_simplify
(minus @0 @0)
{ build_zero_cst (type); })
+
(match_and_simplify
(mult @0 integer_zerop@1)
@1)
-(match_and_simplify
- (mult @0 integer_onep)
- @0)
+
/* Make sure to preserve divisions by zero. This is the reason why
we don't simplify x / x to 1 or 0 / x to 0. */
-(match_and_simplify
- (trunc_div @0 integer_onep)
- @0)
+(for op in mult trunc_div ceil_div floor_div round_div
+ (match_and_simplify
+ (op @0 integer_onep)
+ @0))
+
(match_and_simplify
(trunc_mod @0 integer_onep)
{ build_zero_cst (type); })
@@ -55,9 +52,6 @@ along with GCC; see the file COPYING3.
if (!integer_zerop (@1))
@0)
(match_and_simplify
- (bit_ior @0 integer_zerop)
- @0)
-(match_and_simplify
(bit_ior @0 integer_all_onesp@1)
@1)
(match_and_simplify
@@ -67,9 +61,6 @@ along with GCC; see the file COPYING3.
(bit_and @0 integer_zerop@1)
@1)
(match_and_simplify
- (bit_xor @0 integer_zerop)
- @0)
-(match_and_simplify
(bit_xor @0 @0)
{ build_zero_cst (type); })
/* tree-ssa/ifc-pr44710.c requires a < b ? c : d to fold to 1.
@@ -358,6 +349,15 @@ along with GCC; see the file COPYING3.
if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
{ build_int_cst (type, 0); })
+/* (x << CNT1) OP (x >> CNT2) -> x r<< CNT1 OP being +, |, ^ */
+(for op in plus bit_ior bit_xor
+(match_and_simplify
+ (op:c (lshift @0 INTEGER_CST_P@1) (rshift @0 INTEGER_CST_P@2))
+ if (tree_fits_uhwi_p (@1) && tree_fits_uhwi_p (@2)
+ && tree_to_uhwi (@1) + tree_to_uhwi (@2) == TYPE_PRECISION (type))
+ (lrotate @0 @1)))
+
+
/* ????s
We cannot reasonably match vector CONSTRUCTORs or vector constants
===================================================================
@@ -0,0 +1,44 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-forwprop1-details" } */
+
+unsigned char
+rotate_1 (unsigned char x)
+{
+ unsigned char t1 = x << 5;
+ unsigned char t2 = x >> 3;
+ unsigned char rotate_1_val = t1 + t2;
+ return rotate_1_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to rotate_1_val_\\d\+ = x_\\d\+\\(D\\) r<< 5" "forwprop1" } } */
+
+unsigned char
+rotate_2 (unsigned char x)
+{
+ unsigned char t1 = x << 4;
+ unsigned char t2 = x >> 3;
+ unsigned char rotate_2_val = t1 + t2;
+ return rotate_2_val;
+}
+/* { dg-final { scan-tree-dump-not "gimple_match_and_simplified to rotate_2_val_\\d\+ = x_\\d\+\\(D\\) r<< 5" "forwprop1" } } */
+
+unsigned char
+rotate_3 (unsigned char x)
+{
+ unsigned char t1 = x << 5;
+ unsigned char t2 = x >> 3;
+ unsigned char rotate_3_val = t1 | t2;
+ return rotate_3_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to rotate_3_val_\\d\+ = x_\\d\+\\(D\\) r<< 5" "forwprop1" } } */
+
+unsigned char
+rotate_4 (unsigned char x)
+{
+ unsigned char t1 = x << 5;
+ unsigned char t2 = x >> 3;
+ unsigned char rotate_4_val = t1 ^ t2;
+ return rotate_4_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to rotate_4_val_\\d\+ = x_\\d\+\\(D\\) r<< 5" "forwprop1" } } */
+
+/* { dg-final { cleanup-tree-dump "forwprop1" } } */