PRE (sometimes) confuses ivopts/scev?
Daniel Berlin
dberlin@dberlin.org
Mon Jan 24 17:25:00 GMT 2005
On Mon, 24 Jan 2005, Richard Guenther wrote:
> Daniel Berlin wrote:
>>
>> Just as a followup, sebastian's patch is at (the actual patch is ta the
>> end of the message. You sahouldn't need the other two parts he's pasted in
>> front of it anymore, i believe)
>> http://gcc.gnu.org/ml/gcc-patches/2004-11/msg02444.html
>
> This patch applied, but didn't help, I'll try to get more details and
> hopefully a reduced testcase.
>
>> it should be applied because it helps us detect more simple evolutions
>> properly.
>> " during a bootstrap
>> there are about 7000 cases that are in fact just simple affine
>> evolution functions, but that are mishandled for the moment because
>> the scalar evolution analyzer was not enough smart to transform them."
>>
>> In addition, the patch to teach PRE to stop creating *more* wraparounds is
>> also in the mail archives, see
>> http://gcc.gnu.org/ml/gcc-patches/2004-11/msg02222.html
>
> This patch doesn't apply any more.
Yes, i know.
The attached should apply.
-------------- next part --------------
Index: tree-ssa-pre.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-pre.c,v
retrieving revision 2.62
diff -u -p -r2.62 tree-ssa-pre.c
--- tree-ssa-pre.c 18 Jan 2005 11:36:28 -0000 2.62
+++ tree-ssa-pre.c 24 Jan 2005 16:58:27 -0000
@@ -43,6 +43,7 @@ Boston, MA 02111-1307, USA. */
#include "flags.h"
#include "bitmap.h"
#include "langhooks.h"
+#include "cfgloop.h"
/* TODO:
@@ -55,13 +56,6 @@ Boston, MA 02111-1307, USA. */
a new value every time we see a statement with a vuse.
3. Strength reduction can be performed by anticipating expressions
we can repair later on.
- 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.
*/
/* For ease of terminology, "expression node" in the below refers to
@@ -279,6 +273,10 @@ static struct
/* The number of new PHI nodes added by PRE. */
int phis;
+
+ /* The number of values found constant. */
+ int constified;
+
} pre_stats;
@@ -1346,8 +1344,8 @@ create_expression_by_pieces (basic_block
genop2 = find_or_generate_expression (block, op2, stmts);
temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
add_referenced_tmp_var (temp);
- newexpr = build (TREE_CODE (expr), TREE_TYPE (expr),
- genop1, genop2);
+ newexpr = fold (build (TREE_CODE (expr), TREE_TYPE (expr),
+ genop1, genop2));
newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
temp, newexpr);
name = make_ssa_name (temp, newexpr);
@@ -1366,8 +1364,8 @@ create_expression_by_pieces (basic_block
genop1 = find_or_generate_expression (block, op1, stmts);
temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
add_referenced_tmp_var (temp);
- newexpr = build (TREE_CODE (expr), TREE_TYPE (expr),
- genop1);
+ newexpr = fold (build (TREE_CODE (expr), TREE_TYPE (expr),
+ genop1));
newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
temp, newexpr);
name = make_ssa_name (temp, newexpr);
@@ -1400,6 +1398,19 @@ create_expression_by_pieces (basic_block
return name;
}
+/* Return the folded version of T if T, when folded, is a gimple
+ min_invariant. Otherwise, return T. */
+
+static tree
+fully_constant_expression (tree t)
+{
+ tree folded;
+ folded = fold (t);
+ if (folded && is_gimple_min_invariant (folded))
+ return folded;
+ return t;
+}
+
/* Insert the to-be-made-available values of NODE for each predecessor, stored
in AVAIL, into the predecessors of BLOCK, and merge the result with a phi
node, given the same value handle as NODE. The prefix of the phi node is
@@ -1424,6 +1435,39 @@ insert_into_preds_of_block (basic_block
fprintf (dump_file, "\n");
}
+ /* Make sure we aren't creating an induction variable. */
+ if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
+ {
+ bool firstinsideloop = false;
+ basic_block insideloopblock = NULL;
+ bool secondinsideloop = false;
+ basic_block outsideloopblock = NULL;
+ if (flow_bb_inside_loop_p (block->loop_father,
+ EDGE_PRED (block, 0)->src))
+ {
+ firstinsideloop = true;
+ insideloopblock = EDGE_PRED (block, 0)->src;
+ outsideloopblock = EDGE_PRED (block, 1)->src;
+ }
+ if (flow_bb_inside_loop_p (block->loop_father,
+ EDGE_PRED (block, 1)->src))
+ {
+ secondinsideloop = true;
+ insideloopblock = EDGE_PRED (block, 1)->src;
+ outsideloopblock = EDGE_PRED (block, 0)->src;
+ }
+ /* Induction variables only have one edge inside the loop. */
+ if (firstinsideloop ^ secondinsideloop
+ && is_gimple_min_invariant (avail[outsideloopblock->index])
+ && !is_gimple_min_invariant (avail[insideloopblock->index]))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Skipping partial redundancy: Looks like an induction variable\n");
+ return false;
+ }
+ }
+
+
/* Make the necessary insertions. */
FOR_EACH_EDGE (pred, ei, block->preds)
{
@@ -1591,6 +1635,7 @@ insert_aux (basic_block block)
break;
}
+ eprime = fully_constant_expression (eprime);
vprime = get_value_handle (eprime);
gcc_assert (vprime);
edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
@@ -1621,7 +1666,24 @@ insert_aux (basic_block block)
"prephitmp"))
new_stuff = true;
}
-
+ /* If all edges produce the same value and that value is
+ an invariant, then the PHI has the same value on all
+ edges. Note this. */
+ else if (all_same && eprime
+ && is_gimple_min_invariant (eprime)
+ && !is_gimple_min_invariant (val))
+ {
+ value_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
+ value_set_node_t node;
+ for (node = exprset->head; node; node = node->next)
+ {
+ if (TREE_CODE (node->expr) == SSA_NAME)
+ {
+ vn_add (node->expr, eprime, NULL);
+ pre_stats.constified++;
+ }
+ }
+ }
free (avail);
}
}
@@ -1967,12 +2029,14 @@ eliminate (void)
/* Initialize data structures used by PRE. */
static void
-init_pre (void)
+init_pre (bool do_fre)
{
basic_block bb;
- connect_infinite_loops_to_exit ();
vn_init ();
+ connect_infinite_loops_to_exit ();
+ if (!do_fre)
+ current_loops = loop_optimizer_init (dump_file);
memset (&pre_stats, 0, sizeof (pre_stats));
/* If block 0 has more than one predecessor, it means that its PHI
@@ -2021,7 +2085,7 @@ init_pre (void)
/* Deallocate data structures used by PRE. */
static void
-fini_pre (void)
+fini_pre (bool do_fre)
{
basic_block bb;
unsigned int i;
@@ -2068,6 +2132,11 @@ fini_pre (void)
&& TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
SSA_NAME_VALUE (name) = NULL;
}
+ if (!do_fre && current_loops)
+ {
+ loop_optimizer_finalize (current_loops, dump_file);
+ current_loops = NULL;
+ }
}
@@ -2077,7 +2146,7 @@ fini_pre (void)
static void
execute_pre (bool do_fre)
{
- init_pre ();
+ init_pre (do_fre);
/* Collect and value number expressions computed in each basic block. */
compute_avail ();
@@ -2109,15 +2178,16 @@ execute_pre (bool do_fre)
/* Remove all the redundant expressions. */
eliminate ();
-
+
if (dump_file && (dump_flags & TDF_STATS))
{
fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions);
fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis);
fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
+ fprintf (dump_file, "Constified:%d\n", pre_stats.constified);
}
-
- fini_pre ();
+
+ fini_pre (do_fre);
}
More information about the Gcc
mailing list