This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Copy prop into virtual operands
- From: law at redhat dot com
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 29 Jul 2003 08:56:50 -0600
- Subject: [tree-ssa] Copy prop into virtual operands
- Reply-to: law at redhat dot com
This patch implements copy propagation into virtual operands. Copy
propagation into virtual operands allows us to detect a number of
redundant loads that we were missing.
Here's one of the more interesting cases (20030710-1.c):
void
record_component_aliases (type)
tree type;
{
if (type->type.binfo->vec.length)
abort ();
for (; ((
{
const tree __z = type->type.binfo;
if (type->type.binfo->vec.length)
abort ();
type->type.binfo->vec.a[4];}
)->vec.length);)
{
if (4 >= type->type.binfo->vec.length)
abort ();
blah ();
}
}
Which looks like this just before optimization:
record_component_aliases (type)
{
union tree_node * T.1;
int T.2;
union tree_node * retval.3;
int T.4;
extern abort;
# BLOCK 0 (j.c:24). PRED: -1. SUCC: 2 1.
# VUSE <.GLOBAL_VAR_4>;
T.1_5 = type_3->type.binfo;
# VUSE <.GLOBAL_VAR_4>;
T.2_6 = T.1_5->vec.length;
if (T.2_6 != 0)
{
# BLOCK 1 (j.c:25). PRED: 0. SUCC:.
abort ()
}
else
{
# BLOCK 2. PRED: 0. SUCC: 3.
(void)0
};
# BLOCK 3 (j.c:26). PRED: 2. SUCC: 4.
while (1)
{
# BLOCK 4 (j.c:28). PRED: 14 3. SUCC: 6 5.
# .GLOBAL_VAR_1 = PHI <.GLOBAL_VAR_4(3), .GLOBAL_VAR_16(14)>;
# retval.3_2 = PHI <retval.3_7(3), retval.3_12(14)>;
{
union tree_node * const __z;
# VUSE <.GLOBAL_VAR_1>;
__z_8 = type_3->type.binfo;
# VUSE <.GLOBAL_VAR_1>;
T.1_9 = type_3->type.binfo;
# VUSE <.GLOBAL_VAR_1>;
T.2_10 = T.1_9->vec.length;
if (T.2_10 != 0)
{
# BLOCK 5 (j.c:30). PRED: 4. SUCC:.
abort ()
}
else
{
# BLOCK 6. PRED: 4. SUCC: 7.
(void)0
};
# BLOCK 7 (j.c:31). PRED: 6. SUCC: 8.
# VUSE <.GLOBAL_VAR_1>;
T.1_11 = type_3->type.binfo;
# VUSE <.GLOBAL_VAR_1>;
retval.3_12 = T.1_11->vec.a[4]
};
# BLOCK 8 (j.c:31). PRED: 7. SUCC: 10 9.
# VUSE <.GLOBAL_VAR_1>;
T.4_13 = retval.3_12->vec.length;
if (T.4_13 == 0)
{
# BLOCK 9 (j.c:31). PRED: 8. SUCC: 15.
goto <ULe380>;
}
else
{
# BLOCK 10. PRED: 8. SUCC: 11.
(void)0
};
# BLOCK 11 (j.c:34). PRED: 10. SUCC: 13 12.
{
extern blah;
# VUSE <.GLOBAL_VAR_1>;
T.1_14 = type_3->type.binfo;
# VUSE <.GLOBAL_VAR_1>;
T.2_15 = T.1_14->vec.length;
if (T.2_15 <= 4)
{
# BLOCK 12 (j.c:35). PRED: 11. SUCC:.
abort ()
}
else
{
# BLOCK 13. PRED: 11. SUCC: 14.
(void)0
};
# BLOCK 14 (j.c:36). PRED: 13. SUCC: 4.
# .GLOBAL_VAR_16 = VDEF <.GLOBAL_VAR_1>;
blah ()
}
};
# BLOCK 15. PRED: 9. SUCC: -2.
<ULe380>:;
}
OK. Now here's the steps necessary to remove all the redundant crud out
of this testcase. First you have to detect that the last conditional
is redundant with the first conditional inside the while loop and that
the call to "blah" can never be executed (it's unreachable). That will
result in the following:
record_component_aliases (type)
{
union tree_node * T.1;
int T.2;
union tree_node * retval.3;
int T.4;
extern abort;
# BLOCK 0 (j.c:24). PRED: -1. SUCC: 2 1.
# VUSE <.GLOBAL_VAR_4>;
T.1_5 = type_3->type.binfo;
# VUSE <.GLOBAL_VAR_4>;
T.2_6 = T.1_5->vec.length;
if (T.2_6 != 0)
{
# BLOCK 1 (j.c:25). PRED: 0. SUCC:.
abort ()
}
else
{
# BLOCK 2. PRED: 0. SUCC: 3.
(void)0
};
# BLOCK 3 (j.c:26). PRED: 2. SUCC: 4.
while (1)
{
# BLOCK 4 (j.c:28). PRED: 3. SUCC: 6 5.
# .GLOBAL_VAR_1 = PHI <.GLOBAL_VAR_4(3)>;
# retval.3_2 = PHI <retval.3_7(3)>;
{
union tree_node * const __z;
# VUSE <.GLOBAL_VAR_1>;
__z_8 = type_3->type.binfo;
# VUSE <.GLOBAL_VAR_1>;
T.1_9 = __z_8;
# VUSE <.GLOBAL_VAR_1>;
T.2_10 = __z_8->vec.length;
if (T.2_10 != 0)
{
# BLOCK 5 (j.c:30). PRED: 4. SUCC:.
abort ()
}
else
{
# BLOCK 6. PRED: 4. SUCC: 7.
(void)0
};
# BLOCK 7 (j.c:31). PRED: 6. SUCC: 8.
# VUSE <.GLOBAL_VAR_1>;
T.1_11 = __z_8;
# VUSE <.GLOBAL_VAR_1>;
retval.3_12 = __z_8->vec.a[4]
};
# BLOCK 8 (j.c:31). PRED: 7. SUCC: 10 9.
# VUSE <.GLOBAL_VAR_1>;
T.4_13 = retval.3_12->vec.length;
if (T.4_13 == 0)
{
# BLOCK 9 (j.c:31). PRED: 8. SUCC: 15.
goto <ULe380>;
}
else
{
# BLOCK 10. PRED: 8. SUCC: 11.
(void)0
};
# BLOCK 11 (j.c:34). PRED: 10. SUCC: 12.
{
extern blah;
# VUSE <.GLOBAL_VAR_1>;
T.1_14 = __z_8;
# VUSE <.GLOBAL_VAR_1>;
T.2_15 = 0;
if (1)
{
# BLOCK 12 (j.c:35). PRED: 11. SUCC:.
abort ()
}
else
{
# BLOCK 13. PRED:. SUCC:.
(void)0
};
# BLOCK 14 (j.c:36). PRED:. SUCC:.
# .GLOBAL_VAR_16 = VDEF <.GLOBAL_VAR_1>;
blah ()
}
};
# BLOCK 15. PRED: 9. SUCC: -2.
<ULe380>:;
Note that with the call to "blah" now unreachable, we should be able to
determine that the first conditional inside the while loop is redundant
with the conditional outside the while loop. But we fail to detect
that because the memory load outside the loop uses a different version
of GLOBAL_VAR than the memory load inside the loop.
[ For those not familiar -- different versions effectively say that something
modified global memory between those two points. That "something" was
the call to "blah" that we have proved is unreachable. ]
So if you look at the top of the while loop, you'll see that the PHI nodes
both have a single RHS argument. That effectively means that the PHI
is just a copy and we can replace occurences of the LHS with the RHS.
Once we do that the memory loads inside the loop become redundant with
those outside the loop (since they load from the same location and they
use the same version of GLOBAL_VAR).
That in turn means that T.2_6 will have the same value as T.2_10 and that
the first IF statement inside the loop is redundant with the IF statement
outside the loop.
In all this fixes a half-dozen or so of the tree-ssa tests by exposing more
redundant memory loads.
The only "tricky" parts of this patch are:
1. We only propagate SSA_NAMEs in the VUSES/VDEFs. Propagating a constant
into a virtual operand seems extremely wrong to me.
2. We don't allow the base variable to change when propagating into
vitual operands. ie, we only allow a version # change. Otherwise if
we later modify the statement it becomes impossible to recover the
virtual operands.
3. We don't bother setting the modified bit for a virtual operand
propagation.
The patch is simpler than it looks -- there's a goodly amount of the diff
that is simply reindention in the affected code.
Whee.
* tree-ssa-dom.c (optimize_stmt): Propagate copies into VUSEs and
the RHS of VDEFs.
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.12
diff -c -3 -p -r1.1.2.12 tree-ssa-dom.c
*** tree-ssa-dom.c 28 Jul 2003 23:17:14 -0000 1.1.2.12
--- tree-ssa-dom.c 29 Jul 2003 14:53:58 -0000
*************** optimize_stmt (block_stmt_iterator si, v
*** 435,441 ****
size_t i;
stmt_ann_t ann;
tree stmt;
! varray_type defs, uses, vuses, vdefs;
bool may_optimize_p;
stmt = bsi_stmt (si);
--- 435,441 ----
size_t i;
stmt_ann_t ann;
tree stmt;
! varray_type defs, uses, vuses, vdefs, operand_tables[4], *table;
bool may_optimize_p;
stmt = bsi_stmt (si);
*************** optimize_stmt (block_stmt_iterator si, v
*** 457,513 ****
vuses = vuse_ops (stmt);
vdefs = vdef_ops (stmt);
! /* Const/copy propagate into USES. */
! for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
! {
! tree val;
! tree *op_p = (tree *) VARRAY_GENERIC_PTR (uses, i);
!
! if (! SSA_VAR_P (*op_p))
! continue;
!
! /* If the operand has a known constant value or it is known to be a
! copy of some other variable, use the value or copy stored in
! CONST_AND_COPIES. */
! opt_stats.num_exprs_considered++;
! val = get_value_for (*op_p, const_and_copies);
! if (val)
! {
! /* Make sure that copy propagation can be done here. */
! if (TREE_CODE (val) == SSA_NAME
! && !may_propagate_copy (*op_p, val))
! continue;
!
! /* Gather statistics. */
! if (is_unchanging_value (val)
! || is_optimizable_addr_expr (val))
! opt_stats.num_const_prop++;
! else
! opt_stats.num_copy_prop++;
!
! /* Replace the operand with its known constant value or copy. */
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! fprintf (dump_file, " Replaced '");
! print_generic_expr (dump_file, *op_p, 0);
! fprintf (dump_file, "' with %s '",
! TREE_CODE (val) == SSA_NAME ? "constant" : "variable");
! print_generic_expr (dump_file, val, 0);
! fprintf (dump_file, "'\n");
! }
!
! /* If VAL is an ADDR_EXPR, notify that we may need to have a
! second SSA pass to rename variables exposed by the folding of
! *&VAR expressions. */
! if (TREE_CODE (val) == ADDR_EXPR)
! addr_expr_propagated_p = true;
!
! if (TREE_CODE (val) == SSA_NAME)
! propagate_copy (op_p, val);
! else
! *op_p = val;
!
! ann->modified = 1;
}
}
--- 457,544 ----
vuses = vuse_ops (stmt);
vdefs = vdef_ops (stmt);
! /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
! operand_tables[0] = uses;
! operand_tables[1] = vuses;
! operand_tables[2] = vdefs;
! operand_tables[3] = NULL;
! for (table = operand_tables; *table; table++)
! for (i = 0; *table && i < VARRAY_ACTIVE_SIZE (*table); i++)
! {
! tree val;
! tree *op_p;
!
! /* Get a pointer to the operand we want to const/copy propagate
! into. Each table has a slightly different structure. */
! if (*table == uses)
! op_p = (tree *) VARRAY_GENERIC_PTR (uses, i);
! else if (*table == vuses)
! op_p = (tree *) &VARRAY_TREE (vuses, i);
! else
! op_p = (tree *) &VDEF_OP (VARRAY_TREE (vdefs, i));
!
! /* If the operand is not an ssa variable, then there is nothing
! to do. */
! if (! SSA_VAR_P (*op_p))
! continue;
!
! /* If the operand has a known constant value or it is known to be a
! copy of some other variable, use the value or copy stored in
! CONST_AND_COPIES. */
! opt_stats.num_exprs_considered++;
! val = get_value_for (*op_p, const_and_copies);
! if (val)
! {
! /* Do not change the base variable in the virtual operand
! tables. That would make it impossible to reconstruct
! the renamed virtual operand if we later modify this
! statement. Also only allow the new value to be an SSA_NAME
! for propagation into virtual operands. */
! if ((*table == vuses || *table == vdefs)
! && (get_virtual_var (val) != get_virtual_var (*op_p)
! || TREE_CODE (val) != SSA_NAME))
! continue;
!
! /* Certain operands are not allowed to be copy propagated due
! to their interaction with exception handling and some
! GCC extensions. */
! if (TREE_CODE (val) == SSA_NAME
! && !may_propagate_copy (*op_p, val))
! continue;
!
! /* Gather statistics. */
! if (is_unchanging_value (val) || is_optimizable_addr_expr (val))
! opt_stats.num_const_prop++;
! else
! opt_stats.num_copy_prop++;
!
! /* Dump details. */
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! fprintf (dump_file, " Replaced '");
! print_generic_expr (dump_file, *op_p, 0);
! fprintf (dump_file, "' with %s '",
! (TREE_CODE (val) != SSA_NAME
! ? "constant" : "variable"));
! print_generic_expr (dump_file, val, 0);
! fprintf (dump_file, "'\n");
! }
!
! /* If VAL is an ADDR_EXPR, note that we may need to have a
! second SSA pass to rename variables exposed by the folding of
! *&VAR expressions. */
! if (TREE_CODE (val) == ADDR_EXPR)
! addr_expr_propagated_p = true;
!
! if (TREE_CODE (val) == SSA_NAME)
! propagate_copy (op_p, val);
! else
! *op_p = val;
!
! /* If we only update virtual operands, then we should not
! consider this statement as modified. */
! if (*table != vuses && *table != vdefs)
! ann->modified = 1;
}
}