This is the mail archive of the gcc-patches@gcc.gnu.org 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]

Re: VRP speedup


Hi,
this is patch with cummulated changes as you and Paolo suggested.  I am
keeping the testcase around, at least until we can fix the O(n^2) issues
with our propagation engine.

I am still testing, but the changes are cosmetic, so hope it will still
pass (the change to -2 passed since morning).

My overall plan with VRP is after this patch avoid more of the direct
folder calls (first they tend to be wrong comparing boolean_true_node
and they are mostly convertible to the new comparsion thingy.), rewrite
the ranges_intersect_p predicate so it does two comparsions instead of 6
and then try to reorg the propagation engine to avoid propagating over
unchanges PHI edges.

I did the plan few months ago and got VRP to basically no time on the
testcase as well as some others (like insn-attrtab).

I am still not quite decided how to deal with the last change properly.
My previous patch simply changed priority of taking big PHI nodes to
later time reducing number of times they are visited.  This seems to
work well in practice (ie I don't know about testcase where it doesn't)
but it is still non-linear in theory.
Proper forumlation of the algorithm propagate over SSA edges, so we
might have function that is called for particular PHI operand merging
the operand in.  This might have some negative effect on number of
latice points we produce making common case slower, but I guess I should
try, since it don't need to be bad.
(I am not quite sure how to cheaply manage the queue of PHI operands
since we don't have convenient place to stick 'in queue' bit to. But if
the complexity issues are gone, the particular implementation details
probably should not matter too much either).

Thanks,
Honza

	* tree-vrp.c (operand_less_p): New.
	(compare_values, value_inside_range): Rewrite in terms of
	operand_less_p.

Index: tree-vrp.c
===================================================================
*** tree-vrp.c	(revision 119454)
--- tree-vrp.c	(working copy)
*************** valid_value_p (tree expr)
*** 442,447 ****
--- 442,470 ----
    return is_gimple_min_invariant (expr);
  }
  
+ /* Return 
+    1 if VAL < VAL2
+    0 if !(VAL < VAL2)
+    -2 if those are incomparable.  */
+ static inline int
+ operand_less_p (tree val, tree val2)
+ {
+   tree tcmp;
+   /* LT is folded faster than GE and others.  Inline the common case.  */
+   if (TREE_CODE (val) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST)
+     {
+       if (TYPE_UNSIGNED (TREE_TYPE (val)))
+ 	return INT_CST_LT_UNSIGNED (val, val2);
+       else
+ 	return INT_CST_LT (val, val2);
+     }
+   else
+     tcmp = fold_binary_to_constant (LT_EXPR, boolean_type_node, val, val2);
+   if (!tcmp)
+     return -2;
+   return !integer_zerop (tcmp);
+ }
+ 
  /* Compare two values VAL1 and VAL2.  Return
     
     	-2 if VAL1 and VAL2 cannot be compared at compile-time,
*************** compare_values (tree val1, tree val2)
*** 590,602 ****
  	return 0;
        
        /* If VAL1 is a lower address than VAL2, return -1.  */
!       t = fold_binary (LT_EXPR, boolean_type_node, val1, val2);
!       if (t == boolean_true_node)
  	return -1;
  
        /* If VAL1 is a higher address than VAL2, return +1.  */
!       t = fold_binary (GT_EXPR, boolean_type_node, val1, val2);
!       if (t == boolean_true_node)
  	return 1;
  
        /* If VAL1 is different than VAL2, return +2.  */
--- 613,623 ----
  	return 0;
        
        /* If VAL1 is a lower address than VAL2, return -1.  */
!       if (operand_less_p (val1, val2) == 1)
  	return -1;
  
        /* If VAL1 is a higher address than VAL2, return +1.  */
!       if (operand_less_p (val2, val1) == 1)
  	return 1;
  
        /* If VAL1 is different than VAL2, return +2.  */
*************** compare_values (tree val1, tree val2)
*** 627,653 ****
  	  This also applies to value_ranges_intersect_p and
  	  range_includes_zero_p.  The semantics of VR_RANGE and
  	  VR_ANTI_RANGE should be encoded here, but that also means
! 	  adapting the users of these functions to the new semantics.  */
  
  static inline int
! value_inside_range (tree val, value_range_t *vr)
  {
!   tree cmp1, cmp2;
  
!   cmp1 = fold_binary_to_constant (GE_EXPR, boolean_type_node, val, vr->min);
!   if (!cmp1)
      return -2;
  
!   cmp2 = fold_binary_to_constant (LE_EXPR, boolean_type_node, val, vr->max);
!   if (!cmp2)
      return -2;
  
!   return cmp1 == boolean_true_node && cmp2 == boolean_true_node;
  }
  
  
  /* Return true if value ranges VR0 and VR1 have a non-empty
!    intersection.  */
  
  static inline bool
  value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)
--- 647,682 ----
  	  This also applies to value_ranges_intersect_p and
  	  range_includes_zero_p.  The semantics of VR_RANGE and
  	  VR_ANTI_RANGE should be encoded here, but that also means
! 	  adapting the users of these functions to the new semantics.  
! 
!    Benchmark compile/20001226-1.c compilation time after changing this
!    function.  */
  
  static inline int
! value_inside_range (tree val, value_range_t * vr)
  {
!   int cmp1, cmp2;
  
!   cmp1 = operand_less_p (val, vr->min);
!   if (cmp1 == -2)
      return -2;
+   if (cmp1 == 1)
+     return 0;
  
!   cmp2 = operand_less_p (vr->max, val);
!   if (cmp2 == -2)
      return -2;
  
!   return !cmp2;
  }
  
  
  /* Return true if value ranges VR0 and VR1 have a non-empty
!    intersection.  
!    
!    Benchmark compile/20001226-1.c compilation time after changing this
!    function.
!    */
  
  static inline bool
  value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)


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