PRE (sometimes) confuses ivopts/scev?
Daniel Berlin
dberlin@dberlin.org
Wed Jan 26 07:14:00 GMT 2005
On Tue, 25 Jan 2005, Richard Guenther wrote:
> On Tue, 25 Jan 2005, Daniel Berlin wrote:
>
>>> I created PR tree-optimization/19624 with my testcase (took a day to
>>> reduce...).
>>>
>>
>> Okay, i think i've got it going now.
>> Can you two test a patch for me if i send it to you?
>
> Yes, of course.
>
> Richard.
Give this a spin.
It should avoid insertion of the partial redundancy temporary phi node,
but not avoid lifting invariant code.
(Note that it may insert dead code in the predecessors in this case,
there's not much i can do about this, at least right now. The easiest fix
is to just run DCE after PRE, which we were planning to do anyway because
casts sometimes cause dead code insertion).
--Dan
-------------- 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 26 Jan 2005 02:29:01 -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
@@ -1411,6 +1422,8 @@ insert_into_preds_of_block (basic_block
{
tree val = get_value_handle (node->expr);
edge pred;
+ bool insertions = false;
+ bool nophi = false;
basic_block bprime;
tree eprime;
edge_iterator ei;
@@ -1424,6 +1437,25 @@ 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;
+ bool secondinsideloop = false;
+ firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
+ EDGE_PRED (block, 0)->src);
+ secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
+ EDGE_PRED (block, 1)->src);
+ /* Induction variables only have one edge inside the loop. */
+ if (firstinsideloop ^ secondinsideloop)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
+ nophi = true;
+ }
+ }
+
+
/* Make the necessary insertions. */
FOR_EACH_EDGE (pred, ei, block->preds)
{
@@ -1439,8 +1471,14 @@ insert_into_preds_of_block (basic_block
stmts);
bsi_insert_on_edge (pred, stmts);
avail[bprime->index] = builtexpr;
+ insertions = true;
}
}
+ if (nophi && insertions)
+ return true;
+ else if (nophi && !insertions)
+ return false;
+
/* Now build a phi for the new variable. */
temp = create_tmp_var (type, tmpname);
add_referenced_tmp_var (temp);
@@ -1591,6 +1629,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 +1660,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 +2023,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 ();
+ if (!do_fre)
+ current_loops = loop_optimizer_init (dump_file);
+ connect_infinite_loops_to_exit ();
memset (&pre_stats, 0, sizeof (pre_stats));
/* If block 0 has more than one predecessor, it means that its PHI
@@ -2021,7 +2079,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 +2126,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 +2140,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 +2172,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