Patchwork alias.c: propagate information in RPO order on the CFG

login
register
mail settings
Submitter Steven Bosscher
Date Aug. 22, 2012, 9:53 a.m.
Message ID <CABu31nONTkRAh8OoCOdz=uQrN3Rrq7gK5yvvMw1_Pe7eCJ2q9g@mail.gmail.com>
Download mbox | patch
Permalink /patch/179278/
State New
Headers show

Comments

Steven Bosscher - Aug. 22, 2012, 9:53 a.m.
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.
Richard Guenther - Aug. 22, 2012, 10:06 a.m.
On Wed, Aug 22, 2012 at 11:53 AM, Steven Bosscher <stevenb.gcc@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)

Patch

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)