This patch enhances FRE by recording equivalences generated by conditional statements, so that we can find more optimize opportunities in situations like following two cases:
case 1:
void f (unsigned int a, unsigned int b)
{
if (a == b)
{
for (unsigned i = 0; i < a; i++)
{
if (i == b)
foo (); /* Unreachable */
}
}
}
The "i == b" condition is always false, yet original FRE cannot predict this.
Because VN only stores "i < a" and "a == b", so there won't be "i == b"'s
result. (Moreover, VRP can't infer "i == b" is false either, as its boundary
calculation is hindered by the "unsigned" modifier.)
case 2:
Consider GIMPLE code:
<bb 2> :
if (a != 0)
goto <bb 3>; [INV]
else
goto <bb 4>; [INV]
<bb 3> :
<bb 4> :
# c = PHI <y(2), x(3)>
if (a != 0)
goto <bb 5>; [INV]
else
goto <bb 7>; [INV]
<bb 5> :
if (c > x)
goto <bb 6>; [INV]
else
goto <bb 8>; [INV]
<bb 6> :
__builtin_puts (&"Unreachable!"[0]);
<bb 7> :
__builtin_puts (&"a"[0]);
<bb 8> :
...
The result of "if (c > x)" in bb4 is unknown. However bb2 and bb4 have the same
conditional statement, meanwhile bb2 dominates bb4, so it is predictable that
c==x at bb5 and c==y at bb7. Keeping record of this might bring further
optimizations, such as removing the conditional in bb5.
The basic idea is to use a hashmap to record additional equivalence information
generated by conditional statements.
Insert to the map:
1. When recording an EQ_EXPR=true predicate, e.g. "x==y is true", record
the equivalence of x and y at edge destiny in the map.
2. Consider case 2 above, when we fail to predict the result of a
conditional expression (at bb4), if following conditions be satisfied:
a. There is a previous corresponding predicate. In this case, it
will
be "a != 0 is true" at bb3.
b. bb3's single predecessor bb2 dominates bb4.
c. bb3's conditional statement's predicate code (or inverted
code) is
identical with that of bb4. (This condition can be relaxed.)
Then we can try to find a PHI operation along A's true and false edge, and
record the equivalence of PHI operation's result and arguments at bb4's
true and false destinations. Regarding this case, "c==x at bb5" and
"c==y at bb7" will be recorded.
Use the map:
When we cannot find a prediction result for a conditional statement by
original process, replace conditional expression's operands with qualified
equivalence and try again.
As searching predicates and the ssa names to record are based on
value numbering, we need to "unwind" the equivalence map for iteration.
Bootstrapped and tested on x86_64-pc-linux-gnu and aarch64-unknown-linux-gnu.
Regards,
Di Zhao
Extend FRE with an "equivalence map" for condition prediction.
2021-06-24 Di Zhao <diz...@os.amperecomputing.com>
gcc/ChangeLog:
PR tree-optimization/101186
* tree-ssa-sccvn.c (vn_tracking_edge): Extracted utility function.
(dominated_by_p_w_unex): Moved upward, no change.
(vn_nary_op_get_predicated_value): Moved upward, no change.
(struct val_equiv_hasher): Hasher for the "equivalence map".
(compute_single_op_hash): Compute hashcode from ssa name.
(is_vn_qualified_at_bb): Check if vn_pval is valid at BB.
(val_equiv_insert): Insert into "equivalence map".
(vn_lookup_cond_result): Lookup conditional expression's result by VN.
(find_predicated_value_by_equiv): Search for predicated value,
utilizing equivalences that we have recorded.
(record_equiv_from_previous_edge): Record equivalence relation from a
previouse edge on current edge.
(record_equiv_from_previous_cond): Search for equivalences generated by
previous conditional statements, and record them on current BB's
successors.
(vn_nary_op_insert_pieces_predicated): Extract utility function. Insert
into the "equivalence map" for predicate like "x==y is true".
(free_rpo_vn): Free the "equivalence map".
(process_bb): Insert into & lookup from the "equivalence map".
(struct unwind_state): Add "equivalence map" unwind state.
(do_unwind): Unwind the "equivalence map".
(do_rpo_vn): Update "equivalence map" unwind state.
gcc/testsuite/ChangeLog:
PR tree-optimization/101186
* gcc.dg/tree-ssa/vrp03.c: Disable fre.
* gcc.dg/tree-ssa/ssa-fre-95.c: New test.
* gcc.dg/tree-ssa/ssa-fre-96.c: New test.
tree-optimization-101186.patch
Description: tree-optimization-101186.patch
