[PATCH] Fix loop_iterations mishandling of multiple conditionalized exit tests

[Franz Sirl <Franz dot Sirl-kernel at lauterbach dot com>]

Hi,

the attached stripped down testcase from Berkeley DB-3.2.9 aborts if compiled 
with gcc-2.96-RH and gcc-3.0.x. It illustrates a longstanding bug in 
loop_iterations, the test for multiple back edges is too simple. If the jumps 
to the loop top have differing CODE_LABEL targets, the LABEL_NUSES>1 test 
won't trigger and loop_iterations would hapilly deduce that the loop will 
always iterate 1 time only, which causes later code to completely remopve the 
loop.

The attached patch fixes this by checking if there multiple jumps back into 
the loop body.

Even though I'm sure about the analysis, I'm not 100% sure about the patch, 
eg. is the uid_luid array always correctly initialized at this point? Do I 
need to loosen/strengthen some conditions? What about slightely different 
loop constructs with eg. VTOP?

The patch was bootstrapped/regtested on the branch with x86/ppc-linux-gnu. OK 
to commit to mainline & branch?

The reason why I consider this patch as a high priority candidate for the 
branch is the affected library db3. It's a major database library either 
linked to or compiled into a lot of open source applications and the bug 
causes database corruption (the bug was uncovered by the mysql testsuite) if 
the library was compiled with the recommended optimization -O2.

Franz.


	* unroll.c (loop_iterations): Extend check for multiple back edges.
Index: gcc/unroll.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/unroll.c,v
retrieving revision 1.125.4.1
diff -u -p -r1.125.4.1 unroll.c
--- gcc/unroll.c	2001/04/21 18:43:40	1.125.4.1
+++ gcc/unroll.c	2001/10/04 11:31:00
@@ -3498,6 +3498,27 @@ loop_iterations (loop)
       return 0;
     }
 
+  /* If there are multiple conditionalized loop exit tests, they may jump
+     back to differing CODE_LABELs.  */
+  if (loop->top && loop->cont)
+    {
+      rtx temp = PREV_INSN (last_loop_insn);
+
+      do
+	{
+	  if (GET_CODE (temp) == JUMP_INSN
+	      && INSN_LUID (JUMP_LABEL (temp)) > INSN_LUID (loop->top)
+	      && INSN_LUID (JUMP_LABEL (temp)) < INSN_LUID (loop->cont))
+	    {
+	      if (loop_dump_stream)
+		fprintf (loop_dump_stream,
+			 "Loop iterations: Loop has multiple back edges.\n");
+	      return 0;
+	    }
+	}
+      while ((temp = PREV_INSN (temp)) != loop->cont);
+    }
+
   /* Find the iteration variable.  If the last insn is a conditional
      branch, and the insn before tests a register value, make that the
      iteration variable.  */
extern void exit (int);
extern void abort (void);

typedef unsigned int u_int32_t;
typedef unsigned char u_int8_t;
typedef int int32_t;

typedef enum {
        TXNLIST_DELETE,
        TXNLIST_LSN,
        TXNLIST_TXNID,
        TXNLIST_PGNO
} db_txnlist_type;

struct __db_lsn; typedef struct __db_lsn DB_LSN;
struct __db_lsn {
        u_int32_t file;
        u_int32_t offset;
};
struct __db_txnlist; typedef struct __db_txnlist DB_TXNLIST;

struct __db_txnlist {
        db_txnlist_type type;
        struct { struct __db_txnlist *le_next; struct __db_txnlist **le_prev; } links;
        union {
                struct {
                        u_int32_t txnid;
                        int32_t generation;
                        int32_t aborted;
                } t;
                struct {


                        u_int32_t flags;
                        int32_t fileid;
                        u_int32_t count;
                        char *fname;
                } d;
                struct {
                        int32_t ntxns;
                        int32_t maxn;
                        DB_LSN *lsn_array;
                } l;
                struct {
                        int32_t nentries;
                        int32_t maxentry;
                        char *fname;
                        int32_t fileid;
                        void *pgno_array;
                        u_int8_t uid[20];
                } p;
        } u;
};

int log_compare (const DB_LSN *a, const DB_LSN *b)
{
  return 1;
}


int
__db_txnlist_lsnadd(int val, DB_TXNLIST *elp, DB_LSN *lsnp, u_int32_t flags)
{
   int i;
 
   for (i = 0; i < (!(flags & (0x1)) ? 1 : elp->u.l.ntxns); i++)
     {
	int __j;
	DB_LSN __tmp;
	val++; 
	for (__j = 0; __j < elp->u.l.ntxns - 1; __j++)
	  if (log_compare(&elp->u.l.lsn_array[__j], &elp->u.l.lsn_array[__j + 1]) < 0)
	  {
	     __tmp = elp->u.l.lsn_array[__j];
	     elp->u.l.lsn_array[__j] = elp->u.l.lsn_array[__j + 1];
	     elp->u.l.lsn_array[__j + 1] = __tmp;
	  }
     }

   *lsnp = elp->u.l.lsn_array[0];
   return val;
}

int main (void)
{
  DB_TXNLIST el;
  DB_LSN lsn;
  
  el.u.l.ntxns = 1234;
  
  if (__db_txnlist_lsnadd (0, &el, &lsn, 0) != 1)
    abort ();
  
  if (__db_txnlist_lsnadd (0, &el, &lsn, 1) != 1234)
    abort ();
  
  exit (0);
}