[patch] for PR 27735

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

this PR is a problem in the code that updates EDGE_IRREDUCIBLE_LOOP
flags during loop unswitching (more precisely, in the code that removes
edge and all the dominated basic blocks from cfg).  The concrete problem
is that a loop of form

for (;;)
  {
    something ();
    if (invariant_condition)
      {
        if (something ())
	  break;
      }
  }

is unswitched.  This loop additionally is a part of irreducible region,
thus its entry and exit edges are marked.  However, in the resulting code, we have

if (invariant_condition)
  {
    for (;;)
      something ();
  }
else
  {
    for (;;)
      {
        something ();
	if (something ())
	  break;
      }
  }

The first loop now does not have an exit to the irreducible region, but
we keep its entry edge marked with EDGE_IRREDUCIBLE_LOOP, which causes
the ice in the verification code.

This would be fairly easy to fix by handling this special case;
nevertheless, the problem with the code for updating the EDGE_IRREDUCIBLE_LOOP flag is
that it is fairly complicated, and at the same time, it handles a quite
rare case, so it does not really get a decent testing coverage.  I thus
consider it safer to propose the following patch that makes us simply
recompute the flag from scratch whenever we detect that
EDGE_IRREDUCIBLE_LOOP information might get invalidated.  In particular,
that will never happen for programs without irreducible loops, so this
should cause no compile time slowdowns except for very rare cases (where
the situation still should not be too bad, as mark_irreducible_loops is
quite fast and opportunities for loop unswitching are not too common).
Additionally, this code should disappear completely once the tree alias
analysis related problems (e.g., PRs 13761 and 14784) are fixed (so that
tree-level loop unswitching is able to handle most of the cases).

Bootstrapped (with -O3) & regtested on i686 and ppc64.

Zdenek

	PR rtl-optimization/27735
	* cfgloop.h (fix_loop_placement): Declaration removed.
	* loop-unswitch.c (unswitch_loop): Do not call fix_loop_placement.
	* cfgloopmanip.c (fix_loop_placements, fix_bb_placements, unloop):
	Keep track of whether an irreducible region was affected.
	(fix_irreducible_loops): Removed.
	(remove_path): Call mark_irreducible_loops if EDGE_IRREDUCIBLE_LOOP
	flags were invalidated.
	(fix_loop_placement): Return type changed to bool.

	* gcc.dg/pr27735.c: New test.

Index: loop-unswitch.c
===================================================================
*** loop-unswitch.c	(revision 114016)
--- loop-unswitch.c	(working copy)
*************** unswitch_loop (struct loops *loops, stru
*** 474,484 ****
    remove_path (loops, true_edge);
    remove_path (loops, false_edge);
  
-   /* One of created loops do not have to be subloop of the outer loop now,
-      so fix its placement in loop data structure.  */
-   fix_loop_placement (loop);
-   fix_loop_placement (nloop);
- 
    /* Preserve the simple loop preheaders.  */
    loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
    loop_split_edge_with (loop_preheader_edge (nloop), NULL_RTX);
--- 474,479 ----
Index: cfgloopmanip.c
===================================================================
*** cfgloopmanip.c	(revision 114016)
--- cfgloopmanip.c	(working copy)
*************** static bool rpe_enum_p (basic_block, voi
*** 41,54 ****
  static int find_path (edge, basic_block **);
  static bool alp_enum_p (basic_block, void *);
  static void add_loop (struct loops *, struct loop *);
! static void fix_loop_placements (struct loops *, struct loop *);
  static bool fix_bb_placement (struct loops *, basic_block);
! static void fix_bb_placements (struct loops *, basic_block);
  static void place_new_loop (struct loops *, struct loop *);
  static void scale_loop_frequencies (struct loop *, int, int);
  static basic_block create_preheader (struct loop *, int);
! static void fix_irreducible_loops (basic_block);
! static void unloop (struct loops *, struct loop *);
  
  #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
  
--- 41,54 ----
  static int find_path (edge, basic_block **);
  static bool alp_enum_p (basic_block, void *);
  static void add_loop (struct loops *, struct loop *);
! static void fix_loop_placements (struct loops *, struct loop *, bool *);
  static bool fix_bb_placement (struct loops *, basic_block);
! static void fix_bb_placements (struct loops *, basic_block, bool *);
  static void place_new_loop (struct loops *, struct loop *);
  static void scale_loop_frequencies (struct loop *, int, int);
  static basic_block create_preheader (struct loop *, int);
! static void unloop (struct loops *, struct loop *, bool *);
! static bool fix_loop_placement (struct loop *);
  
  #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
  
*************** fix_bb_placement (struct loops *loops, b
*** 133,141 ****
     its predecessors that may change if placement of FROM changed.  Also fix
     placement of subloops of FROM->loop_father, that might also be altered due
     to this change; the condition for them is similar, except that instead of
!    successors we consider edges coming out of the loops.  */
  static void
! fix_bb_placements (struct loops *loops, basic_block from)
  {
    sbitmap in_queue;
    basic_block *queue, *qtop, *qbeg, *qend;
--- 133,145 ----
     its predecessors that may change if placement of FROM changed.  Also fix
     placement of subloops of FROM->loop_father, that might also be altered due
     to this change; the condition for them is similar, except that instead of
!    successors we consider edges coming out of the loops.
!  
!    If the changes may invalidate the information about irreducible regions,
!    UPDATE_IRRED is set to true.  */
! 
  static void
! fix_bb_placements (struct loops *loops, basic_block from, bool *update_irred)
  {
    sbitmap in_queue;
    basic_block *queue, *qtop, *qbeg, *qend;
*************** fix_bb_placements (struct loops *loops, 
*** 187,198 ****
--- 191,211 ----
  	    continue;
  	}
  
+       FOR_EACH_EDGE (e, ei, from->succs)
+ 	{
+ 	  if (e->flags & EDGE_IRREDUCIBLE_LOOP)
+ 	    *update_irred = true;
+ 	}
+ 
        /* Something has changed, insert predecessors into queue.  */
        FOR_EACH_EDGE (e, ei, from->preds)
  	{
  	  basic_block pred = e->src;
  	  struct loop *nca;
  
+ 	  if (e->flags & EDGE_IRREDUCIBLE_LOOP)
+ 	    *update_irred = true;
+ 
  	  if (TEST_BIT (in_queue, pred->index))
  	    continue;
  
*************** fix_bb_placements (struct loops *loops, 
*** 225,300 ****
    free (queue);
  }
  
- /* Basic block from has lost one or more of its predecessors, so it might
-    mo longer be part irreducible loop.  Fix it and proceed recursively
-    for its successors if needed.  */
- static void
- fix_irreducible_loops (basic_block from)
- {
-   basic_block bb;
-   basic_block *stack;
-   int stack_top;
-   sbitmap on_stack;
-   edge *edges, e;
-   unsigned num_edges, i;
- 
-   if (!(from->flags & BB_IRREDUCIBLE_LOOP))
-     return;
- 
-   on_stack = sbitmap_alloc (last_basic_block);
-   sbitmap_zero (on_stack);
-   SET_BIT (on_stack, from->index);
-   stack = XNEWVEC (basic_block, from->loop_father->num_nodes);
-   stack[0] = from;
-   stack_top = 1;
- 
-   while (stack_top)
-     {
-       edge_iterator ei;
-       bb = stack[--stack_top];
-       RESET_BIT (on_stack, bb->index);
- 
-       FOR_EACH_EDGE (e, ei, bb->preds)
- 	if (e->flags & EDGE_IRREDUCIBLE_LOOP)
- 	  break;
-       if (e)
- 	continue;
- 
-       bb->flags &= ~BB_IRREDUCIBLE_LOOP;
-       if (bb->loop_father->header == bb)
- 	edges = get_loop_exit_edges (bb->loop_father, &num_edges);
-       else
- 	{
- 	  num_edges = EDGE_COUNT (bb->succs);
- 	  edges = XNEWVEC (edge, num_edges);
- 	  FOR_EACH_EDGE (e, ei, bb->succs)
- 	    edges[ei.index] = e;
- 	}
- 
-       for (i = 0; i < num_edges; i++)
- 	{
- 	  e = edges[i];
- 
- 	  if (e->flags & EDGE_IRREDUCIBLE_LOOP)
- 	    {
- 	      if (!flow_bb_inside_loop_p (from->loop_father, e->dest))
- 		continue;
- 
- 	      e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
- 	      if (TEST_BIT (on_stack, e->dest->index))
- 		continue;
- 
- 	      SET_BIT (on_stack, e->dest->index);
- 	      stack[stack_top++] = e->dest;
- 	    }
- 	}
-       free (edges);
-     }
- 
-   free (on_stack);
-   free (stack);
- }
- 
  /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
     and update loop structure stored in LOOPS and dominators.  Return true if
     we were able to remove the path, false otherwise (and nothing is affected
--- 238,243 ----
*************** remove_path (struct loops *loops, edge e
*** 306,316 ****
    basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
    int i, nrem, n_bord_bbs, n_dom_bbs;
    sbitmap seen;
!   bool deleted;
  
    if (!loop_delete_branch_edge (e, 0))
      return false;
  
    /* We need to check whether basic blocks are dominated by the edge
       e, but we only have basic block dominators.  This is easy to
       fix -- when e->dest has exactly one predecessor, this corresponds
--- 249,267 ----
    basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
    int i, nrem, n_bord_bbs, n_dom_bbs;
    sbitmap seen;
!   bool deleted, update_irred = false;
  
    if (!loop_delete_branch_edge (e, 0))
      return false;
  
+   /* Keep track of whether we need to update information about irreducible
+      regions.  This is the case if the removed area is a part of the
+      irreducible region, or if the set of basic blocks that belong to a loop
+      that is inside an irreducible region is changed, or if such a loop is
+      removed.  */
+   if (e->flags & EDGE_IRREDUCIBLE_LOOP)
+     update_irred = true;
+ 
    /* We need to check whether basic blocks are dominated by the edge
       e, but we only have basic block dominators.  This is easy to
       fix -- when e->dest has exactly one predecessor, this corresponds
*************** remove_path (struct loops *loops, edge e
*** 325,331 ****
    while (e->src->loop_father->outer
  	 && dominated_by_p (CDI_DOMINATORS,
  			    e->src->loop_father->latch, e->dest))
!     unloop (loops, e->src->loop_father);
  
    /* Identify the path.  */
    nrem = find_path (e, &rem_bbs);
--- 276,282 ----
    while (e->src->loop_father->outer
  	 && dominated_by_p (CDI_DOMINATORS,
  			    e->src->loop_father->latch, e->dest))
!     unloop (loops, e->src->loop_father, &update_irred);
  
    /* Identify the path.  */
    nrem = find_path (e, &rem_bbs);
*************** remove_path (struct loops *loops, edge e
*** 347,352 ****
--- 298,306 ----
  	  {
  	    SET_BIT (seen, ae->dest->index);
  	    bord_bbs[n_bord_bbs++] = ae->dest;
+ 	  
+ 	    if (ae->flags & EDGE_IRREDUCIBLE_LOOP)
+ 	      update_irred = true;
  	  }
      }
  
*************** remove_path (struct loops *loops, edge e
*** 388,404 ****
    /* Recount dominators.  */
    iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
    free (dom_bbs);
- 
-   /* These blocks have lost some predecessor(s), thus their irreducible
-      status could be changed.  */
-   for (i = 0; i < n_bord_bbs; i++)
-     fix_irreducible_loops (bord_bbs[i]);
    free (bord_bbs);
  
    /* Fix placements of basic blocks inside loops and the placement of
       loops in the loop tree.  */
!   fix_bb_placements (loops, from);
!   fix_loop_placements (loops, from->loop_father);
  
    return true;
  }
--- 342,357 ----
    /* Recount dominators.  */
    iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
    free (dom_bbs);
    free (bord_bbs);
  
    /* Fix placements of basic blocks inside loops and the placement of
       loops in the loop tree.  */
!   fix_bb_placements (loops, from, &update_irred);
!   fix_loop_placements (loops, from->loop_father, &update_irred);
! 
!   if (update_irred
!       && (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) != 0)
!     mark_irreducible_loops (loops);
  
    return true;
  }
*************** loopify (struct loops *loops, edge latch
*** 549,564 ****
  
  /* Remove the latch edge of a LOOP and update LOOPS tree to indicate that
     the LOOP was removed.  After this function, original loop latch will
!    have no successor, which caller is expected to fix somehow.  */
  static void
! unloop (struct loops *loops, struct loop *loop)
  {
    basic_block *body;
    struct loop *ploop;
    unsigned i, n;
    basic_block latch = loop->latch;
!   edge *edges;
!   unsigned num_edges;
  
    /* This is relatively straightforward.  The dominators are unchanged, as
       loop header dominates loop latch, so the only thing we have to care of
--- 502,523 ----
  
  /* Remove the latch edge of a LOOP and update LOOPS tree to indicate that
     the LOOP was removed.  After this function, original loop latch will
!    have no successor, which caller is expected to fix somehow.
! 
!    If this may cause the information about irreducible regions become
!    invalid, UPDATE_IRRED is set to true.  */
! 
  static void
! unloop (struct loops *loops, struct loop *loop, bool *update_irred)
  {
    basic_block *body;
    struct loop *ploop;
    unsigned i, n;
    basic_block latch = loop->latch;
!   bool dummy = false;
! 
!   if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
!     *update_irred = true;
  
    /* This is relatively straightforward.  The dominators are unchanged, as
       loop header dominates loop latch, so the only thing we have to care of
*************** unloop (struct loops *loops, struct loop
*** 567,573 ****
       its work.  */
  
    body = get_loop_body (loop);
-   edges = get_loop_exit_edges (loop, &num_edges);
    n = loop->num_nodes;
    for (i = 0; i < n; i++)
      if (body[i]->loop_father == loop)
--- 526,531 ----
*************** unloop (struct loops *loops, struct loop
*** 590,614 ****
    flow_loop_free (loop);
  
    remove_edge (single_succ_edge (latch));
-   fix_bb_placements (loops, latch);
  
!   /* If the loop was inside an irreducible region, we would have to somehow
!      update the irreducible marks inside its body.  While it is certainly
!      possible to do, it is a bit complicated and this situation should be
!      very rare, so we just remark all loops in this case.  */
!   for (i = 0; i < num_edges; i++)
!     if (edges[i]->flags & EDGE_IRREDUCIBLE_LOOP)
!       break;
!   if (i != num_edges)
!     mark_irreducible_loops (loops);
!   free (edges);
  }
  
  /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
     FATHER of LOOP such that all of the edges coming out of LOOP belong to
!    FATHER, and set it as outer loop of LOOP.  Return 1 if placement of
     LOOP changed.  */
! int
  fix_loop_placement (struct loop *loop)
  {
    basic_block *body;
--- 548,566 ----
    flow_loop_free (loop);
  
    remove_edge (single_succ_edge (latch));
  
!   /* We do not pass UPDATE_IRRED to fix_bb_placements here, as even if
!      there is an irreducible region inside the cancelled loop, the flags will
!      be still correct.  */
!   fix_bb_placements (loops, latch, &dummy);
  }
  
  /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
     FATHER of LOOP such that all of the edges coming out of LOOP belong to
!    FATHER, and set it as outer loop of LOOP.  Return true if placement of
     LOOP changed.  */
! 
! static bool
  fix_loop_placement (struct loop *loop)
  {
    basic_block *body;
*************** fix_loop_placement (struct loop *loop)
*** 634,650 ****
  	act->num_nodes -= loop->num_nodes;
        flow_loop_tree_node_remove (loop);
        flow_loop_tree_node_add (father, loop);
!       return 1;
      }
!   return 0;
  }
  
  /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
     condition stated in description of fix_loop_placement holds for them.
     It is used in case when we removed some edges coming out of LOOP, which
!    may cause the right placement of LOOP inside loop tree to change.  */
  static void
! fix_loop_placements (struct loops *loops, struct loop *loop)
  {
    struct loop *outer;
  
--- 586,606 ----
  	act->num_nodes -= loop->num_nodes;
        flow_loop_tree_node_remove (loop);
        flow_loop_tree_node_add (father, loop);
!       return true;
      }
!   return false;
  }
  
  /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
     condition stated in description of fix_loop_placement holds for them.
     It is used in case when we removed some edges coming out of LOOP, which
!    may cause the right placement of LOOP inside loop tree to change.
!  
!    UPDATE_IRRED is set to true if a change in the loop structures might
!    invalidate the information about irreducible regions.  */
! 
  static void
! fix_loop_placements (struct loops *loops, struct loop *loop, bool *update_irred)
  {
    struct loop *outer;
  
*************** fix_loop_placements (struct loops *loops
*** 659,665 ****
  	 for its preheader, because the successor is the header and belongs
  	 to the loop.  So call fix_bb_placements to fix up the placement
  	 of the preheader and (possibly) of its predecessors.  */
!       fix_bb_placements (loops, loop_preheader_edge (loop)->src);
        loop = outer;
      }
  }
--- 615,621 ----
  	 for its preheader, because the successor is the header and belongs
  	 to the loop.  So call fix_bb_placements to fix up the placement
  	 of the preheader and (possibly) of its predecessors.  */
!       fix_bb_placements (loops, loop_preheader_edge (loop)->src, update_irred);
        loop = outer;
      }
  }
Index: testsuite/gcc.dg/pr27735.c
===================================================================
*** testsuite/gcc.dg/pr27735.c	(revision 0)
--- testsuite/gcc.dg/pr27735.c	(revision 0)
***************
*** 0 ****
--- 1,33 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -funswitch-loops" } */
+ 
+ void set_color(void);
+ void xml_colorize_line(unsigned int *p, int state)
+ {
+   int c;
+   switch(state) 
+     {
+     case 1:
+       goto parse_tag;
+     case 2:
+       goto parse_comment;
+     }
+ 
+   for(;;) 
+     {
+       c = *p;  
+       if (c == '<' && state == 0) 
+ 	{
+ parse_comment: ;
+ 	  while (*p != '\n') 
+ 	    state = 3;
+ parse_tag: ;
+ 	  while (*p != '\n') 
+ 	    state = 0;
+ 	  set_color();
+ 	}
+       else
+ 	p++;
+     }
+ }
+ 
Index: cfgloop.h
===================================================================
*** cfgloop.h	(revision 114016)
--- cfgloop.h	(working copy)
*************** extern void remove_bb_from_loops (basic_
*** 221,227 ****
  extern void cancel_loop_tree (struct loops *, struct loop *);
  
  extern basic_block loop_split_edge_with (edge, rtx);
- extern int fix_loop_placement (struct loop *);
  
  enum
  {
--- 221,226 ----