View | Details | Return to bug 28632 | Differences between
and this patch

Collapse All | Expand All

(-)gcc-4.4.svn.0/gcc/tree-vrp.c (-33 / +177 lines)
Lines 1995-2000 vrp_int_const_binop (enum tree_code code Link Here
1995
  return res;
1995
  return res;
1996
}
1996
}
1997
1997
1998
/* Combines MIN and MAX as follows:
1999
   MIN =   01010010101001010010
2000
   MAX =   01010010100000010010
2001
   result: 01010010100000000000
2002
   This tells us which bits are always 1 for any X in [MIN, MAX].  */
2003
2004
static tree
2005
bits_always_set (tree min, tree max)
2006
{
2007
  tree xored, shift, result;
2008
  int xor_hi;
2009
2010
  result = int_const_binop (BIT_AND_EXPR, min, max, 0);
2011
2012
  /* Result may have lower common bits set, need to clear those.  */
2013
  /* Find bit position of highest differing bit.  */
2014
  xored = int_const_binop (BIT_XOR_EXPR, min, max, 0);
2015
  xor_hi = tree_floor_log2 (xored);
2016
  /* Is there such bit?  */
2017
  if (xor_hi >= 0)
2018
    {
2019
      shift = build_int_cst (NULL_TREE, xor_hi + 1);
2020
      /* Shift right, then left, clearing this bit and all lower bits too.  */
2021
      result = int_const_binop (RSHIFT_EXPR, result, shift, 0);
2022
      result = int_const_binop (LSHIFT_EXPR, result, shift, 0);
2023
    }
2024
  return result;
2025
}
2026
2027
/* Combines MIN and MAX as follows:
2028
   MAX =   01010010101001010010
2029
   MIN =   01010010100000010010
2030
   result: 01010010101111111111.
2031
   Zeros tell us which bits are always 0 for any X in [MIN, MAX].
2032
   Conversely, ones show which bits can be set.  */
2033
2034
static tree
2035
bits_maybe_set (tree min, tree max)
2036
{
2037
  tree xored, shift, result, one, mask;
2038
  int xor_hi;
2039
2040
  result = int_const_binop (BIT_IOR_EXPR, min, max, 0);
2041
  /* Find bit position of highest differing bit.  */
2042
  xored = int_const_binop (BIT_XOR_EXPR, min, max, 0);
2043
  xor_hi = tree_floor_log2 (xored);
2044
  /* Is there such bit and it's not bit 0?  */
2045
  if (xor_hi > 0)
2046
    {
2047
      /* Build a 0000001111 mask.  */
2048
      shift = build_int_cst (NULL_TREE, xor_hi);
2049
      one = build_int_cst (TREE_TYPE (max), 1);
2050
      mask = int_const_binop (LSHIFT_EXPR, one, shift, 0);
2051
      mask = int_const_binop (MINUS_EXPR, mask, one, 0);
2052
      /* OR it to the result.  */
2053
      result = int_const_binop (BIT_IOR_EXPR, result, mask, 0);
2054
    }
2055
  return result;
2056
}
2057
2058
static int
2059
integer_nonnegative_range (value_range_t *vr)
2060
{
2061
  if (vr->type == VR_RANGE
2062
      && TREE_CODE (vr->min) == INTEGER_CST
2063
      && TREE_CODE (vr->max) == INTEGER_CST
2064
      && tree_int_cst_sgn (vr->min) >= 0
2065
      && tree_int_cst_sgn (vr->max) >= 0
2066
      && !TREE_OVERFLOW (vr->max))
2067
    {
2068
      return 1;
2069
    }
2070
  return 0;
2071
}
1998
2072
1999
/* Extract range information from a binary expression EXPR based on
2073
/* Extract range information from a binary expression EXPR based on
2000
   the ranges of each of its operands and the expression code.  */
2074
   the ranges of each of its operands and the expression code.  */
Lines 2007-2012 extract_range_from_binary_expr (value_ra Link Here
2007
  enum value_range_type type;
2081
  enum value_range_type type;
2008
  tree min, max;
2082
  tree min, max;
2009
  int cmp;
2083
  int cmp;
2084
  tree always_set0, always_set1;
2085
  tree maybe_set0, maybe_set1;
2010
  value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2086
  value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2011
  value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2087
  value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2012
2088
Lines 2025-2030 extract_range_from_binary_expr (value_ra Link Here
2025
      && code != MIN_EXPR
2101
      && code != MIN_EXPR
2026
      && code != MAX_EXPR
2102
      && code != MAX_EXPR
2027
      && code != BIT_AND_EXPR
2103
      && code != BIT_AND_EXPR
2104
      && code != BIT_IOR_EXPR
2028
      && code != TRUTH_AND_EXPR
2105
      && code != TRUTH_AND_EXPR
2029
      && code != TRUTH_OR_EXPR)
2106
      && code != TRUTH_OR_EXPR)
2030
    {
2107
    {
Lines 2048-2053 extract_range_from_binary_expr (value_ra Link Here
2048
  else
2125
  else
2049
    set_value_range_to_varying (&vr1);
2126
    set_value_range_to_varying (&vr1);
2050
2127
2128
  /* Bitwise ops.  */
2129
  /* Width and signedness of operands is always the same here.  */
2130
  if (code == BIT_AND_EXPR)
2131
    {
2132
      if (integer_nonnegative_range (&vr0))
2133
	{
2134
	  if (integer_nonnegative_range (&vr1))
2135
	    {
2136
	      /* In always_setX, ones indicate "always set" bits.  */
2137
	      always_set0 = bits_always_set (vr0.min, vr0.max);
2138
	      always_set1 = bits_always_set (vr1.min, vr1.max);
2139
	      /* In maybe_setX, ZEROES indicate "always unset" bits,
2140
	         ones indicate bits which are "maybe set".  */
2141
	      maybe_set0 = bits_maybe_set (vr0.min, vr0.max);
2142
	      maybe_set1 = bits_maybe_set (vr1.min, vr1.max);
2143
	      /* If bit is always set in a AND in b,
2144
	         it will be set in (a & b).  */
2145
	      min = int_const_binop (BIT_AND_EXPR,
2146
				     always_set0, always_set1, 0);
2147
	      /* If bit is maybe set in a AND in b,
2148
	         it may be set in (a & b).
2149
	         Example: max(010x & 10xx) = 0001
2150
	         (maybe_set0 = 0101, maybe_set1 = 1011).  */
2151
	      max = int_const_binop (BIT_AND_EXPR, maybe_set0, maybe_set1, 0);
2152
	      set_value_range (vr, VR_RANGE, min, max, NULL);
2153
	      return;
2154
	    }
2155
	  /* Only op0 has nonnegative range.
2156
	     We positively sure that result of (op0 & op1) can't be
2157
	     larger than vr0.max.  */
2158
	  max = vr0.max;
2159
	  min = build_int_cst (expr_type, 0);
2160
	  set_value_range (vr, VR_RANGE, min, max, NULL);
2161
	  return;
2162
	}
2163
      if (integer_nonnegative_range (&vr1))
2164
	{
2165
	  /* Only op1 has nonnegative range.  */
2166
	  max = vr1.max;
2167
	  min = build_int_cst (expr_type, 0);
2168
	  set_value_range (vr, VR_RANGE, min, max, NULL);
2169
	  return;
2170
	}
2171
      set_value_range_to_varying (vr);
2172
      return;
2173
    }
2174
2175
  if (code == BIT_IOR_EXPR)
2176
    {
2177
      if (integer_nonnegative_range (&vr0))
2178
	{
2179
	  if (integer_nonnegative_range (&vr1))
2180
	    {
2181
	      always_set0 = bits_always_set (vr0.min, vr0.max);
2182
	      always_set1 = bits_always_set (vr1.min, vr1.max);
2183
	      maybe_set0 = bits_maybe_set (vr0.min, vr0.max);
2184
	      maybe_set1 = bits_maybe_set (vr1.min, vr1.max);
2185
	      /* If bit is always set in a OR in b,
2186
	         it will be set in (a | b).  */
2187
	      min = int_const_binop (BIT_IOR_EXPR,
2188
				     always_set0, always_set1, 0);
2189
	      /* If bit is maybe set in a OR in b,
2190
	         it may be set in (a | b).
2191
	         Example: max(101x | 01xx) = 1111.  */
2192
	      max = int_const_binop (BIT_IOR_EXPR, maybe_set0, maybe_set1, 0);
2193
	      set_value_range (vr, VR_RANGE, min, max, NULL);
2194
	      return;
2195
	    }
2196
	  /* Only op0 has nonnegative range.  If result is unsigned,
2197
	     we still can derive that (op0|op1) >= op0.min.  */
2198
	  if (TYPE_UNSIGNED (expr_type))
2199
	    {
2200
	      min = vr0.min;
2201
	      max = TYPE_MAX_VALUE (expr_type);
2202
	      set_value_range (vr, VR_RANGE, min, max, NULL);
2203
	      set_value_range (vr, VR_RANGE, min, max, NULL);
2204
	      return;
2205
	    }
2206
	  /* TODO: signed type has antirange because (op0|op1) never falls
2207
	     into [0..vr0.min-1]. antirange is [-inf,-1]..[vr0.min,+inf].  */
2208
	  set_value_range_to_varying (vr);
2209
	  return;
2210
	}
2211
      if (integer_nonnegative_range (&vr1))
2212
	{
2213
	  /* Only op1 has nonnegative range.  */
2214
	  if (TYPE_UNSIGNED (expr_type))
2215
	    {
2216
	      min = vr1.min;
2217
	      max = TYPE_MAX_VALUE (expr_type);
2218
	      set_value_range (vr, VR_RANGE, min, max, NULL);
2219
	      return;
2220
	    }
2221
	}
2222
      set_value_range_to_varying (vr);
2223
      return;
2224
    }
2225
2051
  /* If either range is UNDEFINED, so is the result.  */
2226
  /* If either range is UNDEFINED, so is the result.  */
2052
  if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
2227
  if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
2053
    {
2228
    {
Lines 2059-2070 extract_range_from_binary_expr (value_ra Link Here
2059
  type = vr0.type;
2234
  type = vr0.type;
2060
2235
2061
  /* Refuse to operate on VARYING ranges, ranges of different kinds
2236
  /* Refuse to operate on VARYING ranges, ranges of different kinds
2062
     and symbolic ranges.  As an exception, we allow BIT_AND_EXPR
2237
     and symbolic ranges.  */
2063
     because we may be able to derive a useful range even if one of
2238
  if (code != TRUTH_AND_EXPR
2064
     the operands is VR_VARYING or symbolic range.  TODO, we may be
2065
     able to derive anti-ranges in some cases.  */
2066
  if (code != BIT_AND_EXPR
2067
      && code != TRUTH_AND_EXPR
2068
      && code != TRUTH_OR_EXPR
2239
      && code != TRUTH_OR_EXPR
2069
      && (vr0.type == VR_VARYING
2240
      && (vr0.type == VR_VARYING
2070
	  || vr1.type == VR_VARYING
2241
	  || vr1.type == VR_VARYING
Lines 2342-2374 extract_range_from_binary_expr (value_ra Link Here
2342
      min = vrp_int_const_binop (code, vr0.min, vr1.max);
2513
      min = vrp_int_const_binop (code, vr0.min, vr1.max);
2343
      max = vrp_int_const_binop (code, vr0.max, vr1.min);
2514
      max = vrp_int_const_binop (code, vr0.max, vr1.min);
2344
    }
2515
    }
2345
  else if (code == BIT_AND_EXPR)
2346
    {
2347
      if (vr0.type == VR_RANGE
2348
	  && vr0.min == vr0.max
2349
	  && TREE_CODE (vr0.max) == INTEGER_CST
2350
	  && !TREE_OVERFLOW (vr0.max)
2351
	  && tree_int_cst_sgn (vr0.max) >= 0)
2352
	{
2353
	  min = build_int_cst (expr_type, 0);
2354
	  max = vr0.max;
2355
	}
2356
      else if (vr1.type == VR_RANGE
2357
	       && vr1.min == vr1.max
2358
	       && TREE_CODE (vr1.max) == INTEGER_CST
2359
	       && !TREE_OVERFLOW (vr1.max)
2360
	       && tree_int_cst_sgn (vr1.max) >= 0)
2361
	{
2362
	  type = VR_RANGE;
2363
	  min = build_int_cst (expr_type, 0);
2364
	  max = vr1.max;
2365
	}
2366
      else
2367
	{
2368
	  set_value_range_to_varying (vr);
2369
	  return;
2370
	}
2371
    }
2372
  else
2516
  else
2373
    gcc_unreachable ();
2517
    gcc_unreachable ();
2374
2518

Return to bug 28632