Hello,
This both speeds up and improves RTL alias analysis by propagating the
alias chains information in a visit in topological order of the CFG.
Perhaps unsurprisingly, this is motivated again by PR
middle-end/54146, where I noticed that the loop in init_alias_analysis
terminated because the iteration count was greater than
MAX_ALIAS_LOOP_PASSES (==10), even though the maximum loop depth in
the test case is only 3 so that the minimum number of iterations
required to fully propagate all information is only 5.
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. OK if it passes?
(BTW the diff is with -bw because the inner loop needed re-indenting,
but there are no functional change in it.)
Ciao!
Steven
* alias.c (MAX_ALIAS_LOOP_PASSES): Update comment with rationale,
or rather a lack thereof.
(init_alias_analysis): Propagate the latest information across
the CFG in topological order to propagate as far as possible in
each iteration. Ignore debug insns.
Index: alias.c
===================================================================
--- alias.c (revision 190588)
+++ alias.c (working copy)
@@ -168,7 +168,10 @@ static void memory_modified_1 (rtx, cons
#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
/* Cap the number of passes we make over the insns propagating alias
- information through set chains. 10 is a completely arbitrary choice. */
+ information through set chains.
+ ??? 10 is a completely arbitrary choice. This should be based on the
+ maximum loop depth in the CFG, but we do not have this information
+ available (even if current_loops _is_ available). */
#define MAX_ALIAS_LOOP_PASSES 10
/* reg_base_value[N] gives an address to which register N is related.
@@ -2764,6 +2767,8 @@ init_alias_analysis (void)
int i;
unsigned int ui;
rtx insn, val;
+ int rpo_cnt;
+ int *rpo;
timevar_push (TV_ALIAS_ANALYSIS);
@@ -2786,6 +2791,9 @@ init_alias_analysis (void)
"constant" information from the previous pass to propagate alias
information through another level of assignments.
+ The propagation is done on the CFG in reverse post-order, to
+ propagate things forward as far as possible in each iteration.
+
This could get expensive if the assignment chains are long. Maybe
we should throttle the number of iterations, possibly based on
the optimization level or flag_expensive_optimizations.
@@ -2801,6 +2809,9 @@ init_alias_analysis (void)
The state of the arrays for the set chain in question does not matter
since the program has undefined behavior. */
+ rpo = XNEWVEC (int, n_basic_blocks);
+ rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
+
pass = 0;
do
{
@@ -2833,9 +2844,12 @@ init_alias_analysis (void)
FIRST_PSEUDO_REGISTER * sizeof (rtx));
/* Walk the insns adding values to the new_reg_base_value array. */
- for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+ for (i = 0; i < rpo_cnt; i++)
{
- if (INSN_P (insn))
+ basic_block bb = BASIC_BLOCK (rpo[i]);
+ FOR_BB_INSNS (bb, insn)
+ {
+ if (NONDEBUG_INSN_P (insn))
{
rtx note, set;
@@ -2924,7 +2938,9 @@ init_alias_analysis (void)
}
}
}
+ }
while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
+ XDELETEVEC (rpo);
/* Fill in the remaining entries. */
FOR_EACH_VEC_ELT (rtx, reg_known_value, i, val)
