This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Fix PR optimization/13985


This is the failure of gcc.c-torture/compile/930621-1.c on i386 at -O3, a 
regression present on 3.4 branch and mainline.

The compiler aborts on the sanity check in get_loop_body that tests whether 
the number of BBs in the the loop counted through backward depth-first 
search from the latch is equal to the number of BBs previously recorded.  
The difference is 1, the former method giving the lower (correct) result.  
This means that the BB count was not correctly updated at some point.

The big loop in the testcase gets unswitched 3 times.  Then, in the process 
of unswitching it a 4th time, the compiler remarks that one of the edges of 
the branch it is going to split is always executed.  So it simply calls 
remove_path on the other edge.

Remove_path does it job and eventually calls fix_bb_placements on the BB 
source of the removed edge to fix up its placement in the loop tree.  But 
fix_bb_placements works only locally, by recursively propagating the changes 
to the predecessors of the BB if necessary.  In the present case, there is 
nothing to fix for the BB so fix_bb_placements does nothing.  Then 
fix_loop_placements is called to fix up the placement of the loop to which 
BB belongs (the base loop) and its parents.  

Removing the edge has introduced a global modification in the CFG: the base 
loop is not the child of its parent loop anymore.  So fix_loop_placement 
detects it and reparents the base loop, executing 

     for (act = loop->outer; act != father; act = act->outer)
	act->num_nodes -= loop->num_nodes;

to update the BB count of its former parents.  The problem is that the 
formula doesn't take into account the (empty) preheader introduced by 
unswitch_loop: it is not counted in loop->num_nodes so is not removed from 
the parent's BB count.  But it is of course not backward reachable anymore 
from the parent loop's latch, so it is not counted in get_loop_body.

Patching fix_loop_placement to include the preheader (if any) in the count 
cures the ICE in get_loop_body, but only to stumble upon another ICE in 
verify_loop_structure: the preheader is not counted as belonging to the 
right loop.

Therefore I think the problem is that fix_bb_placements can't fix up the 
global changes introduced by remove_path in the CFG.  Since visiting every 
BB would be wasteful, I think a good fix is to use the information returned 
by fix_loop_placement to call fix_bb_placement on the preheader of loops 
that have been reparented because of the changes.

Bootstrapped/regtested on i586-redhat-linux (3.4 branch).  OK for mainline 
and 3.4 branch?

2004-03-07  Eric Botcazou  <>

        PR optimization/13985
        * cfgloopmanip.c (fix_loop_placements): New prototype.
	Call fix_bb_placements on the preheader of loops that have
	been reparented.
	(remove_path): Adjust call to fix_loop_placements.

2004-03-07  Eric Botcazou  <>

        * gcc.dg/loop-3.c: New test.

Eric Botcazou
/* PR optimization/13985 */
/* Copied from gcc.c-torture/compile/930621-1.c */

/* { dg-do compile } */
/* { dg-options "-O3" } */
/* { dg-options "-O3 -mtune=i386" { target i?86-*-* x86_64-*-* } } */

#if defined(STACK_SIZE) && (STACK_SIZE < 65536)
# define BYTEMEM_SIZE 10000L

# define BYTEMEM_SIZE 45000L

int bytestart[5000 + 1];
unsigned char modtext[400 + 1];
unsigned char bytemem[2][BYTEMEM_SIZE + 1];

modlookup (int l)
  signed char c;
  long j;
  long k;
  signed char w;
  long p;
  while (p != 0)
      while ((k < bytestart[p + 2]) && (j <= l) && (modtext[j] == bytemem[w][k]))
	  k = k + 1;
	  j = j + 1;
      if (k == bytestart[p + 2])
	if (j > l)
	  c = 1;
	else c = 4;
      else if (j > l)
	c = 3;
      else if (modtext[j] < bytemem[w][k])
	c = 0;
      else c = 2;
Index: cfgloopmanip.c
RCS file: /cvs/gcc/gcc/gcc/cfgloopmanip.c,v
retrieving revision 1.19
diff -u -p -r1.19 cfgloopmanip.c
--- cfgloopmanip.c	30 Dec 2003 10:40:51 -0000	1.19
+++ cfgloopmanip.c	7 Mar 2004 09:48:24 -0000
@@ -41,7 +41,7 @@ static bool rpe_enum_p (basic_block, voi
 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 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 *);
@@ -417,7 +417,7 @@ remove_path (struct loops *loops, edge e
   /* Fix placements of basic blocks inside loops and the placement of
      loops in the loop tree.  */
   fix_bb_placements (loops, from);
-  fix_loop_placements (from->loop_father);
+  fix_loop_placements (loops, from->loop_father);
   return true;
@@ -668,7 +668,7 @@ fix_loop_placement (struct loop *loop)
    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 loop *loop)
+fix_loop_placements (struct loops *loops, struct loop *loop)
   struct loop *outer;
@@ -677,6 +677,10 @@ fix_loop_placements (struct loop *loop)
       outer = loop->outer;
       if (!fix_loop_placement (loop))
+      /* Changing the placement of a loop in the loop tree may have an
+	 effect on its preheader with regard to the condition stated in
+	 the description of fix_bb_placement.  */
+      fix_bb_placements (loops, loop_preheader_edge (loop)->src);
       loop = outer;

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]