PR opt/10766 III

[Jan Hubicka <jh at suse dot cz>]

Hi,
Without the cselib limit, the testcases explode memory wise and with the limit
it stil need 100MB to compile.  This is caused by quadratically many canon_rtx
calls producing insanely many copies of canonical form of each RTX.
Both CSE and GCSE already contain some code to reduce amount of work.  This
patch brings all three copies of same logic into sync.

I measured about 7% speedup of CSE and 80% speedup on CSELIB (so without limit
I now get everything compiled in 700 seconds) and memory peaks at about 30MB.

Most invasive changes are probably to CSELIB.  I replaced anti dependence by
output dependence.  It seems to be correct to me as we are really checking
whether later read of stored memory location would result in same value as
before the store.

I also removed the recursive walk looking for MEM exprs.  The comment in
cselib_invalidate_mem claims (correctly) that these can happen only on toplevel
and others get replaced by VALUE, so it seems to me that the recursive walk is
completely useless.

It happens only when MEM is outermost expression and we have no target alloving
nested MEMs.

Bootstrapped/regtested i386, OK?
Honza

2004-01-12  Jan Hubicka  <jh@suse.cz>
	Partial fix for PR opt/10775 
	* Makefile.in (gcse.o): Add missing dependency on cselib.h
	* cse.c (check_dependence_data): New field addr.
	(check_dependence): Use canon_true_dependence
	(invalidate): Compute addr.
	* cselib.c (cselib_mem_conflict_p): Kill.
	(new_elt_loc_list): Clear canon_loc.
	(cselib_rtx_varies_p): New.
	(cselib_invalidate_regno):  Compute
	(cselib_invalidate_mem): Use canon_true_dependnece
	* cselib.h (canon_loc): New.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1219
diff -c -3 -p -r1.1219 Makefile.in
*** Makefile.in	12 Jan 2004 09:44:12 -0000	1.1219
--- Makefile.in	12 Jan 2004 09:46:57 -0000
*************** web.o : web.c $(CONFIG_H) $(SYSTEM_H) co
*** 1653,1659 ****
  gcse.o : gcse.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(REGS_H) \
     hard-reg-set.h flags.h real.h insn-config.h $(GGC_H) $(RECOG_H) $(EXPR_H) \
     $(BASIC_BLOCK_H) function.h output.h toplev.h $(TM_P_H) $(PARAMS_H) \
!    except.h gt-gcse.h $(TREE_H)
  sibcall.o : sibcall.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(REGS_H) \
     function.h hard-reg-set.h flags.h insn-config.h $(RECOG_H) $(BASIC_BLOCK_H)
  resource.o : resource.c $(CONFIG_H) $(RTL_H) hard-reg-set.h $(SYSTEM_H) coretypes.h \
--- 1653,1659 ----
  gcse.o : gcse.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(REGS_H) \
     hard-reg-set.h flags.h real.h insn-config.h $(GGC_H) $(RECOG_H) $(EXPR_H) \
     $(BASIC_BLOCK_H) function.h output.h toplev.h $(TM_P_H) $(PARAMS_H) \
!    except.h gt-gcse.h $(TREE_H) cselib.h
  sibcall.o : sibcall.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(REGS_H) \
     function.h hard-reg-set.h flags.h insn-config.h $(RECOG_H) $(BASIC_BLOCK_H)
  resource.o : resource.c $(CONFIG_H) $(RTL_H) hard-reg-set.h $(SYSTEM_H) coretypes.h \
Index: cse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cse.c,v
retrieving revision 1.277
diff -c -3 -p -r1.277 cse.c
*** cse.c	3 Dec 2003 11:09:55 -0000	1.277
--- cse.c	12 Jan 2004 09:46:57 -0000
*************** struct check_dependence_data
*** 1768,1773 ****
--- 1768,1774 ----
  {
    enum machine_mode mode;
    rtx exp;
+   rtx addr;
  };
  
  static int
*************** check_dependence (rtx *x, void *data)
*** 1775,1781 ****
  {
    struct check_dependence_data *d = (struct check_dependence_data *) data;
    if (*x && GET_CODE (*x) == MEM)
!     return true_dependence (d->exp, d->mode, *x, cse_rtx_varies_p);
    else
      return 0;
  }
--- 1776,1783 ----
  {
    struct check_dependence_data *d = (struct check_dependence_data *) data;
    if (*x && GET_CODE (*x) == MEM)
!     return canon_true_dependence (d->exp, d->mode, d->addr, *x,
! 		    		  cse_rtx_varies_p);
    else
      return 0;
  }
*************** invalidate (rtx x, enum machine_mode ful
*** 1797,1802 ****
--- 1799,1805 ----
  {
    int i;
    struct table_elt *p;
+   rtx addr;
  
    switch (GET_CODE (x))
      {
*************** invalidate (rtx x, enum machine_mode ful
*** 1887,1892 ****
--- 1890,1896 ----
        return;
  
      case MEM:
+       addr = canon_rtx (get_addr (XEXP (x, 0)));
        /* Calculate the canonical version of X here so that
  	 true_dependence doesn't generate new RTL for X on each call.  */
        x = canon_rtx (x);
*************** invalidate (rtx x, enum machine_mode ful
*** 1914,1919 ****
--- 1918,1924 ----
  		  if (!p->canon_exp)
  		    p->canon_exp = canon_rtx (p->exp);
  		  d.exp = x;
+ 		  d.addr = addr;
  		  d.mode = full_mode;
  		  if (for_each_rtx (&p->canon_exp, check_dependence, &d))
  		    remove_from_table (p, i);
Index: cselib.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cselib.c,v
retrieving revision 1.31
diff -c -3 -p -r1.31 cselib.c
*** cselib.c	12 Jan 2004 09:44:13 -0000	1.31
--- cselib.c	12 Jan 2004 09:46:57 -0000
*************** static cselib_val *new_cselib_val (unsig
*** 58,64 ****
  static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);
  static cselib_val *cselib_lookup_mem (rtx, int);
  static void cselib_invalidate_regno (unsigned int, enum machine_mode);
- static int cselib_mem_conflict_p (rtx, rtx);
  static void cselib_invalidate_mem (rtx);
  static void cselib_invalidate_rtx (rtx, rtx, void *);
  static void cselib_record_set (rtx, cselib_val *, cselib_val *);
--- 58,63 ----
*************** new_elt_loc_list (struct elt_loc_list *n
*** 168,173 ****
--- 167,173 ----
      el = ggc_alloc (sizeof (struct elt_loc_list));
    el->next = next;
    el->loc = loc;
+   el->canon_loc = NULL;
    el->setting_insn = cselib_current_insn;
    el->in_libcall = cselib_current_insn_in_libcall;
    return el;
*************** cselib_invalidate_regno (unsigned int re
*** 1050,1109 ****
  	}
      }
  }
! 
! /* The memory at address MEM_BASE is being changed.
!    Return whether this change will invalidate VAL.  */
  
  static int
! cselib_mem_conflict_p (rtx mem_base, rtx val)
  {
!   enum rtx_code code;
!   const char *fmt;
!   int i, j;
! 
!   code = GET_CODE (val);
!   switch (code)
!     {
!       /* Get rid of a few simple cases quickly.  */
!     case REG:
!     case PC:
!     case CC0:
!     case SCRATCH:
!     case CONST:
!     case CONST_INT:
!     case CONST_DOUBLE:
!     case CONST_VECTOR:
!     case SYMBOL_REF:
!     case LABEL_REF:
!       return 0;
! 
!     case MEM:
!       if (GET_MODE (mem_base) == BLKmode
! 	  || GET_MODE (val) == BLKmode
! 	  || anti_dependence (val, mem_base))
! 	return 1;
! 
!       /* The address may contain nested MEMs.  */
!       break;
! 
!     default:
!       break;
!     }
! 
!   fmt = GET_RTX_FORMAT (code);
!   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
!     {
!       if (fmt[i] == 'e')
! 	{
! 	  if (cselib_mem_conflict_p (mem_base, XEXP (val, i)))
! 	    return 1;
! 	}
!       else if (fmt[i] == 'E')
! 	for (j = 0; j < XVECLEN (val, i); j++)
! 	  if (cselib_mem_conflict_p (mem_base, XVECEXP (val, i, j)))
! 	    return 1;
!     }
! 
    return 0;
  }
  
--- 1050,1067 ----
  	}
      }
  }
! 
! /* Return 1 if X has a value that can vary even between two
!    executions of the program.  0 means X can be compared reliably
!    against certain constants or near-constants.  */
  
  static int
! cselib_rtx_varies_p (rtx x ATTRIBUTE_UNUSED, int from_alias ATTRIBUTE_UNUSED)
  {
!   /* We actually don't need to verify very hard.  This is because
!      if X has actually changed, we invalidate the memory anyway,
!      so assume that all common memory addresses are
!      invariant.  */
    return 0;
  }
  
*************** cselib_invalidate_mem (rtx mem_rtx)
*** 1116,1121 ****
--- 1074,1083 ----
  {
    cselib_val **vp, *v, *next;
    int num_mems = 0;
+   rtx mem_addr;
+ 
+   mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
+   mem_rtx = canon_rtx (mem_rtx);
  
    vp = &first_containing_mem;
    for (v = *vp; v != &dummy_val; v = next)
*************** cselib_invalidate_mem (rtx mem_rtx)
*** 1127,1132 ****
--- 1089,1095 ----
        while (*p)
  	{
  	  rtx x = (*p)->loc;
+ 	  rtx canon_x = (*p)->canon_loc;
  	  cselib_val *addr;
  	  struct elt_list **mem_chain;
  
*************** cselib_invalidate_mem (rtx mem_rtx)
*** 1137,1144 ****
  	      p = &(*p)->next;
  	      continue;
  	    }
  	  if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
! 	      && ! cselib_mem_conflict_p (mem_rtx, x))
  	    {
  	      has_mem = true;
  	      num_mems++;
--- 1100,1110 ----
  	      p = &(*p)->next;
  	      continue;
  	    }
+ 	  if (!canon_x)
+ 	    canon_x = (*p)->canon_loc = canon_rtx (x);
  	  if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
! 	      && ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr,
! 		      			  x, cselib_rtx_varies_p))
  	    {
  	      has_mem = true;
  	      num_mems++;
Index: cselib.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cselib.h,v
retrieving revision 1.9
diff -c -3 -p -r1.9 cselib.h
*** cselib.h	29 Jun 2003 15:19:12 -0000	1.9
--- cselib.h	12 Jan 2004 09:46:57 -0000
*************** struct elt_loc_list GTY(())
*** 49,54 ****
--- 49,55 ----
    struct elt_loc_list *next;
    /* An rtl expression that holds the value.  */
    rtx loc;
+   rtx canon_loc;
    /* The insn that made the equivalence.  */
    rtx setting_insn;
    /* True when setting insn is inside libcall.  */