On Wed, Aug 22, 2012 at 11:53 AM, Steven Bosscher <stevenb....@gmail.com> wrote:
> 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.)
Ok.
Thanks,
Richard.
> 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)
