Serious performance regression -- some tree optimizer questions
Daniel Berlin
dberlin@dberlin.org
Sat Dec 18 01:10:00 GMT 2004
>>> but no pass recognizes that s2 == t2 ...
>
>> Uh, both of the value numbering passes (DOM and PRE) should recognize this.
>
> That doesn't appear to be the case; from the .t44.pre file:
>
> [snip]
> Created value VH.17 for VH.15 + VH.16
> Created value VH.18 for VH.14 + VH.17
> [snip]
> Created value VH.26 for VH.14 + VH.15
> Created value VH.27 for VH.16 + VH.26
> [snip]
>
> It doesn't recognize that VH.18 and VH.27 are really the same value.
> In fact, the comment at the head of tree-ssa-pre.c makes me think
> this is by design:
>
> 4. Our canonicalization of expressions during lookups don't take
> constants into account very well. In particular, we don't fold
> anywhere, so we can get situations where we stupidly think
> something is a new value (a + 1 + 1 vs a + 2). This is somewhat
> expensive to fix, but it does expose a lot more eliminations.
> It may or not be worth it, depending on how critical you
> consider PRE vs just plain GRE.
>
I have a patch to fix what i was talking about, but it may not be
approriate for 4.0.
However I read your message wrong as to what you wanted optimized.
You are correct, this was deliberately not done.
The identities you are looking for were expensive (compile time wise) to
implement, and nobody ever showed it was worth it.
Basically, when asked to add or lookup a value expression to the value
numbering table, you can also backsubstitute the representative values (we
know, given a value handle, the set of expressions that represent it) and add
them to /look them up in the value numbering table as well.
IE we make VH.18 be VH.14 + VH.17 and VH.14 + VH.15 + VH.16
and VH.27 be VH.16 + VH.26 and VH.16 + VH.14 + VH.15.
This is easy to implement for the simple case, but it can cost a *lot* to
fully backsubstitute and add all of the equivalences to the table.
I've attached a patch that will do the optimization you request.
The masturbation in "put_operands_in_right_order" is because both
iterative_hash_expr, *and* operand_equal_p claim VH.0 + VH.1 + VH.3 is not
the same as VH.1 + VH.0 + VH.3 because of the form of the expressions.
Note that this patch is just an example.
It would need a bunch of grunt work to be right and useful
i.e.
1. if tree-vn is going to use value_node, we should have a tree-vn.h that
defines it instead of just copying an dpasting the definitions from
tree-ssa-pre
2. We need to minimize the number of trees we build. For commutative
operations, we should be able to just swap all the trees into the right
places without building a new tree.
In the testident.c case, one of canonicalized forms is them is
<PLUS_EXPR <op0, <PLUS_EXPR, op1, op2>> and the other is
<PLUS_EXPR <PLUS_EXPR <op0, op1>>, op2>, so you actually need to move the
PLUS_EXPR to operand 0, and change its operations.
3. All of the restrictions in backsubstitute were for convenience of
demonstration (IE that the tree code of the thing we are backsubstituting
has the same tree code of the base expression we are backsubstituting
into. This restriction).
4. other obvious things.
It should, however, work for your testcase.
It works for the attached testcase, which is the same type of thing.
--Dan
-------------- next part --------------
Index: tree-vn.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vn.c,v
retrieving revision 2.3.10.4
diff -u -p -r2.3.10.4 tree-vn.c
--- tree-vn.c 17 Oct 2004 18:31:06 -0000 2.3.10.4
+++ tree-vn.c 18 Dec 2004 01:02:31 -0000
@@ -179,14 +179,154 @@ set_value_handle (tree e, tree v)
gcc_assert (is_gimple_min_invariant (e));
}
+typedef struct value_set_node
+{
+ /* An expression. */
+ tree expr;
+
+ /* A pointer to the next element of the value set. */
+ struct value_set_node *next;
+} *value_set_node_t;
+
+
+/* A value set. This is a singly linked list of value_set_node
+ elements with a possible bitmap that tells us what values exist in
+ the set. This set must be kept in topologically sorted order. */
+typedef struct value_set
+{
+ /* The head of the list. Used for iterating over the list in
+ order. */
+ value_set_node_t head;
+
+ /* The tail of the list. Used for tail insertions, which are
+ necessary to keep the set in topologically sorted order because
+ of how the set is built. */
+ value_set_node_t tail;
+
+ /* The length of the list. */
+ size_t length;
+
+ /* True if the set is indexed, which means it contains a backing
+ bitmap for quick determination of whether certain values exist in the
+ set. */
+ bool indexed;
+
+ /* The bitmap of values that exist in the set. May be NULL in an
+ empty or non-indexed set. */
+ bitmap values;
+
+} *value_set_t;
+
+/* Given a pointer to a commutative three operand expression:
+ <op0 + <op1 + op2>>,
+ rewrite the expression so that that the operands appear in the expression
+ in pointer order.
+*/
+static void
+put_operands_in_pointer_order (tree *expr)
+{
+ tree t, op0, op1, op2;
+ if (TREE_CODE (TREE_OPERAND (*expr, 0)) != VALUE_HANDLE)
+ {
+ op0 = TREE_OPERAND (*expr, 1);
+ op1 = TREE_OPERAND (*expr, 0);
+ op2 = TREE_OPERAND (op1, 1);
+ op1 = TREE_OPERAND (op1, 0);
+ }
+ else
+ {
+ op0 = TREE_OPERAND (*expr, 0);
+ op1 = TREE_OPERAND (*expr, 1);
+ op2 = TREE_OPERAND (op1, 1);
+ op1 = TREE_OPERAND (op1, 0);
+ }
+ if (op1 < op0)
+ {
+ t = op0;
+ op0 = op1;
+ op1 = t;
+ }
+ if (op2 < op1)
+ {
+ t = op1;
+ op1 = op2;
+ op2 = t;
+ }
+ if (op1 < op0)
+ {
+ t = op0;
+ op0 = op1;
+ op1 = t;
+ }
+
+ *expr = build2 (TREE_CODE (*expr), TREE_TYPE (*expr),
+ op0,
+ build2 (TREE_CODE (*expr), TREE_TYPE (*expr),
+ op1, op2));
+}
+
+
+/* Backsubstitute value handles in EXPR with a representative value handle
+ expression.
+ This is a simple implementation that just looks to see if the first known
+ equivalent expression is an expression with the same code, and if so
+ returns the result of substituting that expression into the current one,
+ and sorting the operands.
+
+ IE given
+
+ VH.2 = VH.0 + VH.1
+ VH.4 = VH.2 + VH.3
+
+ this will generate VH.0 + VH.1 + VH.3
+
+
+*/
+
+static tree
+backsubstitute_value_handle_expression (tree expr)
+{
+ value_set_node_t node;
+ tree op0, op1;
+ if (!BINARY_CLASS_P (expr) || !commutative_tree_code (TREE_CODE (expr)))
+ return NULL_TREE;
+ op0 = TREE_OPERAND (expr, 0);
+ op1 = TREE_OPERAND (expr, 1);
+ if (TREE_CODE (op0) == VALUE_HANDLE)
+ {
+ node = VALUE_HANDLE_EXPR_SET (op0)->head;
+ if (BINARY_CLASS_P (node->expr)
+ && TREE_CODE (node->expr) == TREE_CODE (expr))
+ {
+ expr = unshare_expr (expr);
+ TREE_OPERAND (expr, 0) = node->expr;
+ put_operands_in_pointer_order (&expr);
+ return expr;
+ }
+ }
+ if (TREE_CODE (op1) == VALUE_HANDLE)
+ {
+ node = VALUE_HANDLE_EXPR_SET (op1)->head;
+ if (BINARY_CLASS_P (node->expr)
+ && TREE_CODE (node->expr) == TREE_CODE (expr))
+ {
+ expr = unshare_expr (expr);
+ TREE_OPERAND (expr, 1) = node->expr;
+ put_operands_in_pointer_order (&expr);
+ return expr;
+ }
+ }
+
+ return NULL_TREE;
+}
/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
EXPR to the value set for value VAL. VUSES represent the virtual
use operands associated with EXPR (if any). They are used when
computing the hash value for EXPR. */
-void
-vn_add (tree expr, tree val, vuse_optype vuses)
+static void
+vn_add_1 (tree expr, tree val, vuse_optype vuses)
{
void **slot;
val_expr_pair_t new_pair;
@@ -205,15 +345,22 @@ vn_add (tree expr, tree val, vuse_optype
set_value_handle (expr, val);
add_to_value (val, expr);
}
-
-
+void
+vn_add (tree expr, tree val, vuse_optype vuses)
+{
+ tree bs;
+ vn_add_1 (expr, val, vuses);
+ bs = backsubstitute_value_handle_expression (expr);
+ if (bs)
+ vn_add_1 (bs, val, vuses);
+}
/* Search in VALUE_TABLE for an existing instance of expression EXPR,
and return its value, or NULL if none has been set. VUSES
represent the virtual use operands associated with EXPR (if any).
They are used when computing the hash value for EXPR. */
-tree
-vn_lookup (tree expr, vuse_optype vuses)
+static tree
+vn_lookup_1 (tree expr, vuse_optype vuses)
{
void **slot;
struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
@@ -232,6 +379,22 @@ vn_lookup (tree expr, vuse_optype vuses)
return ((val_expr_pair_t) *slot)->v;
}
+tree
+vn_lookup (tree expr, vuse_optype vuses)
+{
+ tree result;
+ result = vn_lookup_1 (expr, vuses);
+ if (result != NULL_TREE)
+ return result;
+ expr = backsubstitute_value_handle_expression (expr);
+ if (expr)
+ {
+ result = vn_lookup_1 (expr, vuses);
+ if (result != NULL_TREE)
+ return result;
+ }
+ return NULL_TREE;
+}
/* Like vn_lookup, but creates a new value for expression EXPR, if
EXPR doesn't already have a value. Return the existing/created
-------------- next part --------------
int a, b, c, d;
int main(void)
{
int e;
int f;
e = a + b;
e += c;
f = c + a;
f += b;
printf ("%d %d\n", e, f);
}
More information about the Gcc
mailing list