Re: [patch] Remove requirement on loop numbering

[Dorit Nuzman <DORIT at il dot ibm dot com>]

> Index: tree-vectorizer.c
> ===================================================================
> *** tree-vectorizer.c   (revision 121034)
> --- tree-vectorizer.c   (working copy)
> *************** vectorize_loops (void)
> *** 2175,2181 ****
>        than all previously defined loops. This fact allows us to run
>        only over initial loops skipping newly generated ones.  */
>     vect_loops_num = number_of_loops ();
> !   FOR_EACH_LOOP (li, loop, LI_ONLY_OLD)
>       {
>         loop_vec_info loop_vinfo;
>
> --- 2175,2181 ----
>        than all previously defined loops. This fact allows us to run
>        only over initial loops skipping newly generated ones.  */
>     vect_loops_num = number_of_loops ();
> !   FOR_EACH_LOOP (li, loop, 0)
>       {
>         loop_vec_info loop_vinfo;
>

just to make sure - does this still guarantee that we iterate only though
"old" loops (i.e. not through newly created loops during this loop
traversal) ?

thanks,
dorit

> Hello,
>
> at the moment, we guarantee the following properties regarding the loop
> numbering:
>
> 1) number assigned to a loop never changes
> 2) subloop of a loop has higher number than the loop
>
> The problem is that preserving both of these properties is impossible
> during some transformations (anything that causes a new loop inserted
> in the middle of the loop tree).  At the moment, we do not have any
> such transformations, as most of our optimizers work only for innermost
> loops.  However, this restriction might become problematic when
> we implement more advanced transformations (like loop tiling and loop
> splitting).
>
> I run into this restriction in much simpler case -- I am trying to
> separate disambiguation of loops with multiple latch edges from loop
> discovery; and in the case that we decide that one of the latch edges
> corresponds to a subloop of the loop, we need to insert the new loop
> as a subloop of a (possibly) noninnermost loop.
>
> Therefore, I think it is necessary to remove one of these properties.
> I consider 1) more important -- chrecs refer to a loop by its number,
> which would be problematic if the numbers might change; also, keeping
> the number fixed makes it simpler to understand what's going on in
> dumps, and to mark the loops in a bitmap.
>
> The patch makes us avoid using the property 2), and removes the
> restriction from the documentation.  The only place where we now use the
> ordering of the loop numbers (I think) are the loop iterators, that
> needed to be rewritten.
>
> Bootstrapped and regtested on i686.  Unless anyone protests, I will
> commit the patch tomorrow.
>
> Zdenek
>
>    * cfgloop.h (enum li_flags): Remove LI_ONLY_OLD.
>    (loop_iterator): Changed.
>    (fel_next, fel_init): Iterate over loop tree.
>    (FOR_EACH_LOOP_BREAK): New macro.
>    * loop-unswitch.c (unswitch_loops): Do not pass LI_ONLY_OLD to
>    FOR_EACH_LOOP.
>    * tree-ssa-loop-unswitch.c (tree_ssa_unswitch_loops): Ditto.
>    * modulo-sched.c (sms_schedule): Ditto.
>    * tree-vectorizer.c (vectorize_loops): Ditto.
>    * doc/loop.texi: Update information on loop numbering and behavior of
>    FOR_EACH_LOOP wrto new loops.
>
> Index: loop-unswitch.c
> ===================================================================
> *** loop-unswitch.c   (revision 121034)
> --- loop-unswitch.c   (working copy)
> *************** unswitch_loops (void)
> *** 143,149 ****
>
>     /* Go through inner loops (only original ones).  */
>
> !   FOR_EACH_LOOP (li, loop, LI_ONLY_OLD | LI_ONLY_INNERMOST)
>       {
>         unswitch_single_loop (loop, NULL_RTX, 0);
>   #ifdef ENABLE_CHECKING
> --- 143,149 ----
>
>     /* Go through inner loops (only original ones).  */
>
> !   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
>       {
>         unswitch_single_loop (loop, NULL_RTX, 0);
>   #ifdef ENABLE_CHECKING
> Index: doc/loop.texi
> ===================================================================
> *** doc/loop.texi   (revision 121034)
> --- doc/loop.texi   (working copy)
> *************** function.  Each of the loops is represen
> *** 64,80 ****
>   structure.  Each loop is assigned an index (@code{num} field of the
>   @code{struct loop} structure), and the pointer to the loop is stored in
>   the corresponding field of the @code{larray} vector in the loops
> ! structure.  Index of a sub-loop is always greater than the index of its
> ! super-loop.  The indices do not have to be continuous, there may be
>   empty (@code{NULL}) entries in the @code{larray} created by deleting
> ! loops.  The index of a loop never changes.
>
>   The entries of the @code{larray} field should not be accessed directly.
>   The function @code{get_loop} returns the loop description for a loop
with
>   the given index.  @code{number_of_loops} function returns number of
>   loops in the function.  To traverse all loops, use @code{FOR_EACH_LOOP}
>   macro.  The @code{flags} argument of the macro is used to determine
> ! the direction of traversal and the set of loops visited.
>
>   Each basic block contains the reference to the innermost loop it
belongs
>   to (@code{loop_father}).  For this reason, it is only possible to have
> --- 64,87 ----
>   structure.  Each loop is assigned an index (@code{num} field of the
>   @code{struct loop} structure), and the pointer to the loop is stored in
>   the corresponding field of the @code{larray} vector in the loops
> ! structure.  The indices do not have to be continuous, there may be
>   empty (@code{NULL}) entries in the @code{larray} created by deleting
> ! loops.  Also, there is no guarantee on the relative order of a loop
> ! and its subloops in the numbering.  The index of a loop never changes.
>
>   The entries of the @code{larray} field should not be accessed directly.
>   The function @code{get_loop} returns the loop description for a loop
with
>   the given index.  @code{number_of_loops} function returns number of
>   loops in the function.  To traverse all loops, use @code{FOR_EACH_LOOP}
>   macro.  The @code{flags} argument of the macro is used to determine
> ! the direction of traversal and the set of loops visited.  Each loop is
> ! guaranteed to be visited exactly once, regardless of the changes to the
> ! loop tree, and the loops may be removed during the traversal.  The
newly
> ! created loops are never traversed, if they need to be visited, this
> ! must be done separately after their creation.  The @code{FOR_EACH_LOOP}
> ! macro allocates temporary variables.  If the @code{FOR_EACH_LOOP} loop
> ! were ended using break or goto, they would not be released;
> ! @code{FOR_EACH_LOOP_BREAK} macro must be used instead.
>
>   Each basic block contains the reference to the innermost loop it
belongs
>   to (@code{loop_father}).  For this reason, it is only possible to have
> Index: tree-ssa-loop-unswitch.c
> ===================================================================
> *** tree-ssa-loop-unswitch.c   (revision 121034)
> --- tree-ssa-loop-unswitch.c   (working copy)
> *************** tree_ssa_unswitch_loops (void)
> *** 87,93 ****
>     bool changed = false;
>
>     /* Go through inner loops (only original ones).  */
> !   FOR_EACH_LOOP (li, loop, LI_ONLY_OLD | LI_ONLY_INNERMOST)
>       {
>         changed |= tree_unswitch_single_loop (loop, 0);
>       }
> --- 87,93 ----
>     bool changed = false;
>
>     /* Go through inner loops (only original ones).  */
> !   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
>       {
>         changed |= tree_unswitch_single_loop (loop, 0);
>       }
> Index: modulo-sched.c
> ===================================================================
> *** modulo-sched.c   (revision 121034)
> --- modulo-sched.c   (working copy)
> *************** sms_schedule (void)
> *** 1028,1034 ****
>     df = NULL;
>
>     /* We don't want to perform SMS on new loops - created by versioning.
*/
> !   FOR_EACH_LOOP (li, loop, LI_ONLY_OLD)
>       {
>         rtx head, tail;
>         rtx count_reg, count_init;
> --- 1028,1034 ----
>     df = NULL;
>
>     /* We don't want to perform SMS on new loops - created by versioning.
*/
> !   FOR_EACH_LOOP (li, loop, 0)
>       {
>         rtx head, tail;
>         rtx count_reg, count_init;
> Index: tree-vectorizer.c
> ===================================================================
> *** tree-vectorizer.c   (revision 121034)
> --- tree-vectorizer.c   (working copy)
> *************** vectorize_loops (void)
> *** 2175,2181 ****
>        than all previously defined loops. This fact allows us to run
>        only over initial loops skipping newly generated ones.  */
>     vect_loops_num = number_of_loops ();
> !   FOR_EACH_LOOP (li, loop, LI_ONLY_OLD)
>       {
>         loop_vec_info loop_vinfo;
>
> --- 2175,2181 ----
>        than all previously defined loops. This fact allows us to run
>        only over initial loops skipping newly generated ones.  */
>     vect_loops_num = number_of_loops ();
> !   FOR_EACH_LOOP (li, loop, 0)
>       {
>         loop_vec_info loop_vinfo;
>
> Index: cfgloop.h
> ===================================================================
> *** cfgloop.h   (revision 121034)
> --- cfgloop.h   (working copy)
> *************** number_of_loops (void)
> *** 424,507 ****
>
>   enum li_flags
>   {
> !   LI_INCLUDE_ROOT = 1,   /* Include the fake root of the loop tree.  */
> !   LI_FROM_INNERMOST = 2,/* Iterate over the loops in the reverse order,
> !             starting from innermost ones.  */
> !   LI_ONLY_INNERMOST = 4,/* Iterate only over innermost loops.  */
> !   LI_ONLY_OLD = 8   /* Do not traverse the loops created during the
> !             traversal (this is the default behavior with
> !             LI_FROM_INNERMOST).  */
>   };
>
>   /* The iterator for loops.  */
>
>   typedef struct
>   {
> !   int idx;      /* Index of the actual loop.  */
> !   int end;      /* Only loops before end should be traversed.  */
>   } loop_iterator;
>
>   static inline void
> ! fel_next (loop_iterator *li, loop_p *loop, unsigned flags)
>   {
> !   if (flags & LI_FROM_INNERMOST)
> !     {
> !       li->idx--;
> !       for (; li->idx > li->end; li->idx--)
> !    {
> !      *loop = VEC_index (loop_p, current_loops->larray, li->idx);
> !      if (*loop
> !          && (!(flags & LI_ONLY_INNERMOST)
> !         || (*loop)->inner == NULL))
> !        return;
> !    }
> !     }
> !   else
>       {
> !       if (!(flags & LI_ONLY_OLD))
> !    li->end = number_of_loops ();
> !       li->idx++;
> !       for (; li->idx < li->end; li->idx++)
> !    {
> !      *loop = VEC_index (loop_p, current_loops->larray, li->idx);
> !      if (*loop
> !          && (!(flags & LI_ONLY_INNERMOST)
> !         || (*loop)->inner == NULL))
> !        return;
> !    }
>       }
> !
> !   *loop = NULL;
>   }
>
>   static inline void
>   fel_init (loop_iterator *li, loop_p *loop, unsigned flags)
>   {
>     if (!current_loops)
>       {
> !       li->idx = 0;
> !       li->end = 0;
>         *loop = NULL;
>         return;
>       }
>
> !   if (flags & LI_FROM_INNERMOST)
>       {
> !       li->idx = number_of_loops ();
> !       li->end = (flags & LI_INCLUDE_ROOT) ? -1 : 0;
>       }
>     else
>       {
> !       li->idx = (flags & LI_INCLUDE_ROOT) ? -1 : 0;
> !       li->end = number_of_loops ();
>       }
> !   fel_next (li, loop, flags);
>   }
>
>   #define FOR_EACH_LOOP(LI, LOOP, FLAGS) \
>     for (fel_init (&(LI), &(LOOP), FLAGS); \
>          (LOOP); \
> !        fel_next (&(LI), &(LOOP), FLAGS))
>
>   /* The properties of the target.  */
>
> --- 424,544 ----
>
>   enum li_flags
>   {
> !   LI_INCLUDE_ROOT = 1,      /* Include the fake root of the loop tree.
*/
> !   LI_FROM_INNERMOST = 2,   /* Iterate over the loops in the reverse
order,
> !                starting from innermost ones.  */
> !   LI_ONLY_INNERMOST = 4      /* Iterate only over innermost loops.  */
>   };
>
>   /* The iterator for loops.  */
>
>   typedef struct
>   {
> !   /* The list of loops to visit.  */
> !   VEC (loop_p, heap) *to_visit;
> !
> !   /* The index of the actual loop.  */
> !   unsigned idx;
>   } loop_iterator;
>
>   static inline void
> ! fel_next (loop_iterator *li, loop_p *loop)
>   {
> !   if (!VEC_iterate (loop_p, li->to_visit, li->idx, *loop))
>       {
> !       VEC_free (loop_p, heap, li->to_visit);
> !       *loop = NULL;
>       }
> !   li->idx++;
>   }
>
>   static inline void
>   fel_init (loop_iterator *li, loop_p *loop, unsigned flags)
>   {
> +   struct loop *aloop;
> +   unsigned i;
> +   int mn;
> +
> +   li->idx = 0;
>     if (!current_loops)
>       {
> !       li->to_visit = NULL;
>         *loop = NULL;
>         return;
>       }
>
> !   li->to_visit = VEC_alloc (loop_p, heap, number_of_loops ());
> !   mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1;
> !
> !   if (flags & LI_ONLY_INNERMOST)
>       {
> !       for (i = 0; VEC_iterate (loop_p, current_loops->larray, i,
> aloop); i++)
> !    if (aloop != NULL
> !        && aloop->inner == NULL
> !        && aloop->num >= mn)
> !      VEC_quick_push (loop_p, li->to_visit, aloop);
> !     }
> !   else if (flags & LI_FROM_INNERMOST)
> !     {
> !       /* Push the loops to LI->TO_VISIT in postorder.  */
> !       for (aloop = current_loops->tree_root;
> !       aloop->inner != NULL;
> !       aloop = aloop->inner)
> !    continue;
> !
> !       while (1)
> !    {
> !      if (aloop->num >= mn)
> !        VEC_quick_push (loop_p, li->to_visit, aloop);
> !
> !      if (aloop->next)
> !        {
> !          for (aloop = aloop->next;
> !          aloop->inner != NULL;
> !          aloop = aloop->inner)
> !       continue;
> !        }
> !      else if (!aloop->outer)
> !        break;
> !      else
> !        aloop = aloop->outer;
> !    }
>       }
>     else
>       {
> !       /* Push the loops to LI->TO_VISIT in preorder.  */
> !       aloop = current_loops->tree_root;
> !       while (1)
> !    {
> !      if (aloop->num >= mn)
> !        VEC_quick_push (loop_p, li->to_visit, aloop);
> !
> !      if (aloop->inner != NULL)
> !        aloop = aloop->inner;
> !      else
> !        {
> !          while (aloop != NULL && aloop->next == NULL)
> !       aloop = aloop->outer;
> !          if (aloop == NULL)
> !       break;
> !          aloop = aloop->next;
> !        }
> !    }
>       }
> !
> !   fel_next (li, loop);
>   }
>
>   #define FOR_EACH_LOOP(LI, LOOP, FLAGS) \
>     for (fel_init (&(LI), &(LOOP), FLAGS); \
>          (LOOP); \
> !        fel_next (&(LI), &(LOOP)))
> !
> ! #define FOR_EACH_LOOP_BREAK(LI) \
> !   { \
> !     VEC_free (loop_p, heap, (LI)->to_visit); \
> !     break; \
> !   }
>
>   /* The properties of the target.  */
>