[PATCH] Reduce memory footprint of VRP

[Richard Guenther <rguenther at suse dot de>]

This reduces memory footprint of VRP by not allocating the equiv
bitmaps in advance but only if they are needed.  With this patch
we can also turn off recording equivalences by making add_equivalence ()
just do nothing (such VRP might be cheap enough for -O1).

Bootstrapped on x86_64-unknown-linux-gnu, testing still in progress.

I plan to commit this tomorrow if there are no objections.

Thanks,
Richard.


2007-04-30  Richard Guenther  <rguenther@suse.de>

	* tree-vrp.c (set_value_range): Do not allocate equiv bitmap
	if it is not about to be set.
	(get_value_range): Do not pre-allocate equiv bitmap.
	(update_value_range): No need to clear equiv field.
	(add_equivalence): Change prototype to get bitmap pointer.
	Allocate bitmap here if it is not already.
	(extract_range_from_assert): Do not allocate bitmap here.
	Update callers to add_equivalence.
	(extract_range_from_ssa_name): Likewise.
	(get_vr_for_comparison): New static helper.
	(compare_name_with_value): Handle NULL equiv bitmap by
	peeling the first iteration of the comparison loop.
	Use get_vr_for_comparison.
	(compare_names): Handle NULL equiv bitmaps by using fake
	ones.  Use get_vr_for_comparison.

Index: tree-vrp.c
===================================================================
*** tree-vrp.c.orig	2007-04-30 22:53:19.000000000 +0200
--- tree-vrp.c	2007-05-01 00:11:17.000000000 +0200
*************** set_value_range (value_range_t *vr, enum
*** 291,297 ****
  
    /* Since updating the equivalence set involves deep copying the
       bitmaps, only do it if absolutely necessary.  */
!   if (vr->equiv == NULL)
      vr->equiv = BITMAP_ALLOC (NULL);
  
    if (equiv != vr->equiv)
--- 291,298 ----
  
    /* Since updating the equivalence set involves deep copying the
       bitmaps, only do it if absolutely necessary.  */
!   if (vr->equiv == NULL
!       && equiv != NULL)
      vr->equiv = BITMAP_ALLOC (NULL);
  
    if (equiv != vr->equiv)
*************** get_value_range (tree var)
*** 436,443 ****
    /* Create a default value range.  */
    vr_value[ver] = vr = XCNEW (value_range_t);
  
!   /* Allocate an equivalence set.  */
!   vr->equiv = BITMAP_ALLOC (NULL);
  
    /* If VAR is a default definition, the variable can take any value
       in VAR's type.  */
--- 437,444 ----
    /* Create a default value range.  */
    vr_value[ver] = vr = XCNEW (value_range_t);
  
!   /* Defer allocating the equivalence set.  */
!   vr->equiv = NULL;
  
    /* If VAR is a default definition, the variable can take any value
       in VAR's type.  */
*************** update_value_range (tree var, value_rang
*** 510,532 ****
  	             new_vr->equiv);
  
    BITMAP_FREE (new_vr->equiv);
-   new_vr->equiv = NULL;
  
    return is_new;
  }
  
  
! /* Add VAR and VAR's equivalence set to EQUIV.  */
  
  static void
! add_equivalence (bitmap equiv, tree var)
  {
    unsigned ver = SSA_NAME_VERSION (var);
    value_range_t *vr = vr_value[ver];
  
!   bitmap_set_bit (equiv, ver);
    if (vr && vr->equiv)
!     bitmap_ior_into (equiv, vr->equiv);
  }
  
  
--- 511,535 ----
  	             new_vr->equiv);
  
    BITMAP_FREE (new_vr->equiv);
  
    return is_new;
  }
  
  
! /* Add VAR and VAR's equivalence set to EQUIV.  This is the central
!    point where equivalence processing can be turned on/off.  */
  
  static void
! add_equivalence (bitmap *equiv, tree var)
  {
    unsigned ver = SSA_NAME_VERSION (var);
    value_range_t *vr = vr_value[ver];
  
!   if (*equiv == NULL)
!     *equiv = BITMAP_ALLOC (NULL);
!   bitmap_set_bit (*equiv, ver);
    if (vr && vr->equiv)
!     bitmap_ior_into (*equiv, vr->equiv);
  }
  
  
*************** extract_range_from_assert (value_range_t
*** 1095,1102 ****
       predicates, we will need to trim the set of equivalences before
       we are done.  */
    gcc_assert (vr_p->equiv == NULL);
!   vr_p->equiv = BITMAP_ALLOC (NULL);
!   add_equivalence (vr_p->equiv, var);
  
    /* Extract a new range based on the asserted comparison for VAR and
       LIMIT's value range.  Notice that if LIMIT has an anti-range, we
--- 1098,1104 ----
       predicates, we will need to trim the set of equivalences before
       we are done.  */
    gcc_assert (vr_p->equiv == NULL);
!   add_equivalence (&vr_p->equiv, var);
  
    /* Extract a new range based on the asserted comparison for VAR and
       LIMIT's value range.  Notice that if LIMIT has an anti-range, we
*************** extract_range_from_assert (value_range_t
*** 1130,1136 ****
  	 SSA name, the new range will also inherit the equivalence set
  	 from LIMIT.  */
        if (TREE_CODE (limit) == SSA_NAME)
! 	add_equivalence (vr_p->equiv, limit);
      }
    else if (cond_code == NE_EXPR)
      {
--- 1132,1138 ----
  	 SSA name, the new range will also inherit the equivalence set
  	 from LIMIT.  */
        if (TREE_CODE (limit) == SSA_NAME)
! 	add_equivalence (&vr_p->equiv, limit);
      }
    else if (cond_code == NE_EXPR)
      {
*************** extract_range_from_ssa_name (value_range
*** 1478,1484 ****
    else
      set_value_range (vr, VR_RANGE, var, var, NULL);
  
!   add_equivalence (vr->equiv, var);
  }
  
  
--- 1480,1486 ----
    else
      set_value_range (vr, VR_RANGE, var, var, NULL);
  
!   add_equivalence (&vr->equiv, var);
  }
  
  
*************** vrp_visit_assignment (tree stmt, tree *o
*** 4582,4587 ****
--- 4584,4610 ----
    return SSA_PROP_VARYING;
  }
  
+ /* Helper that gets the value range of the SSA_NAME with version I
+    or a symbolic range contaning the SSA_NAME only if the value range
+    is varying or undefined.  */
+ 
+ static inline value_range_t
+ get_vr_for_comparison (int i)
+ {
+   value_range_t vr = *(vr_value[i]);
+ 
+   /* If name N_i does not have a valid range, use N_i as its own
+      range.  This allows us to compare against names that may
+      have N_i in their ranges.  */
+   if (vr.type == VR_VARYING || vr.type == VR_UNDEFINED)
+     {
+       vr.type = VR_RANGE;
+       vr.min = ssa_name (i);
+       vr.max = ssa_name (i);
+     }
+ 
+   return vr;
+ }
  
  /* Compare all the value ranges for names equivalent to VAR with VAL
     using comparison code COMP.  Return the same value returned by
*************** compare_name_with_value (enum tree_code 
*** 4597,4633 ****
    bitmap e;
    tree retval, t;
    int used_strict_overflow;
!   
!   t = retval = NULL_TREE;
  
    /* Get the set of equivalences for VAR.  */
    e = get_value_range (var)->equiv;
  
-   /* Add VAR to its own set of equivalences so that VAR's value range
-      is processed by this loop (otherwise, we would have to replicate
-      the body of the loop just to check VAR's value range).  */
-   bitmap_set_bit (e, SSA_NAME_VERSION (var));
- 
    /* Start at -1.  Set it to 0 if we do a comparison without relying
       on overflow, or 1 if all comparisons rely on overflow.  */
    used_strict_overflow = -1;
  
!   EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
!     {
!       bool sop;
! 
!       value_range_t equiv_vr = *(vr_value[i]);
  
!       /* If name N_i does not have a valid range, use N_i as its own
! 	 range.  This allows us to compare against names that may
! 	 have N_i in their ranges.  */
!       if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED)
! 	{
! 	  equiv_vr.type = VR_RANGE;
! 	  equiv_vr.min = ssa_name (i);
! 	  equiv_vr.max = ssa_name (i);
! 	}
  
        sop = false;
        t = compare_range_with_value (comp, &equiv_vr, val, &sop);
        if (t)
--- 4620,4654 ----
    bitmap e;
    tree retval, t;
    int used_strict_overflow;
!   bool sop;
!   value_range_t equiv_vr;
  
    /* Get the set of equivalences for VAR.  */
    e = get_value_range (var)->equiv;
  
    /* Start at -1.  Set it to 0 if we do a comparison without relying
       on overflow, or 1 if all comparisons rely on overflow.  */
    used_strict_overflow = -1;
  
!   /* Compare vars' value range with val.  */
!   equiv_vr = get_vr_for_comparison (SSA_NAME_VERSION (var));
!   sop = false;
!   retval = compare_range_with_value (comp, &equiv_vr, val, &sop);
!   if (sop)
!     used_strict_overflow = 1;
  
!   /* If the equiv set is empty we have done all work we need to do.  */
!   if (e == NULL)
!     {
!       if (retval
! 	  && used_strict_overflow > 0)
! 	*strict_overflow_p = true;
!       return retval;
!     }
  
+   EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
+     {
+       equiv_vr = get_vr_for_comparison (i);
        sop = false;
        t = compare_range_with_value (comp, &equiv_vr, val, &sop);
        if (t)
*************** compare_name_with_value (enum tree_code 
*** 4651,4668 ****
  	}
      }
  
!   /* Remove VAR from its own equivalence set.  */
!   bitmap_clear_bit (e, SSA_NAME_VERSION (var));
  
!   if (retval)
!     {
!       if (used_strict_overflow > 0)
! 	*strict_overflow_p = true;
!       return retval;
!     }
! 
!   /* We couldn't find a non-NULL value for the predicate.  */
!   return NULL_TREE;
  }
  
  
--- 4672,4682 ----
  	}
      }
  
!   if (retval
!       && used_strict_overflow > 0)
!     *strict_overflow_p = true;
  
!   return retval;
  }
  
  
*************** compare_names (enum tree_code comp, tree
*** 4682,4693 ****
--- 4696,4722 ----
    bitmap_iterator bi1, bi2;
    unsigned i1, i2;
    int used_strict_overflow;
+   static bitmap_obstack *s_obstack = NULL;
+   static bitmap s_e1 = NULL, s_e2 = NULL;
  
    /* Compare the ranges of every name equivalent to N1 against the
       ranges of every name equivalent to N2.  */
    e1 = get_value_range (n1)->equiv;
    e2 = get_value_range (n2)->equiv;
  
+   /* Use the fake bitmaps if e1 or e2 are not available.  */
+   if (s_obstack == NULL)
+     {
+       s_obstack = XNEW (bitmap_obstack);
+       bitmap_obstack_initialize (s_obstack);
+       s_e1 = BITMAP_ALLOC (s_obstack);
+       s_e2 = BITMAP_ALLOC (s_obstack);
+     }
+   if (e1 == NULL)
+     e1 = s_e1;
+   if (e2 == NULL)
+     e2 = s_e2;
+ 
    /* Add N1 and N2 to their own set of equivalences to avoid
       duplicating the body of the loop just to check N1 and N2
       ranges.  */
*************** compare_names (enum tree_code comp, tree
*** 4715,4743 ****
       of the loop just to check N1 and N2 ranges.  */
    EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
      {
!       value_range_t vr1 = *(vr_value[i1]);
! 
!       /* If the range is VARYING or UNDEFINED, use the name itself.  */
!       if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED)
! 	{
! 	  vr1.type = VR_RANGE;
! 	  vr1.min = ssa_name (i1);
! 	  vr1.max = ssa_name (i1);
! 	}
  
        t = retval = NULL_TREE;
        EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
  	{
  	  bool sop;
  
! 	  value_range_t vr2 = *(vr_value[i2]);
! 
! 	  if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED)
! 	    {
! 	      vr2.type = VR_RANGE;
! 	      vr2.min = ssa_name (i2);
! 	      vr2.max = ssa_name (i2);
! 	    }
  
  	  t = compare_ranges (comp, &vr1, &vr2, &sop);
  	  if (t)
--- 4744,4757 ----
       of the loop just to check N1 and N2 ranges.  */
    EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
      {
!       value_range_t vr1 = get_vr_for_comparison (i1);
  
        t = retval = NULL_TREE;
        EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
  	{
  	  bool sop;
  
! 	  value_range_t vr2 = get_vr_for_comparison (i2);
  
  	  t = compare_ranges (comp, &vr1, &vr2, &sop);
  	  if (t)