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 / +354 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
#define VDA_DEBUG 1
1999
2000
#if VDA_DEBUG
2001
static FILE *vda_file;
2002
#endif
2003
2004
/* Combines MIN and MAX as follows:
2005
   MAX =   01010010101001010010
2006
   MIN =   01010010100000010010
2007
   result: 01010010100000000000
2008
   This tells us which bits are always 1 for any X in [MIN, MAX].  */
2009
2010
static double_int
2011
bits_always_set (double_int min_di, double_int max_di)
2012
{
2013
  double_int xored_di, result_di;
2014
  int bitpos;
2015
2016
  result_di.low = min_di.low & max_di.low;
2017
  result_di.high = min_di.high & max_di.high;
2018
2019
  /* Result may have lower common bits set, need to clear those.  */
2020
  /* Find bit position of highest differing bit.  */
2021
  xored_di.low = min_di.low ^ max_di.low;
2022
  xored_di.high = min_di.high ^ max_di.high;
2023
  /* Is there such bit?  */
2024
  if (xored_di.high)
2025
    {
2026
      /* Clear all bits below it (the bit itself is already 0).  */
2027
      bitpos = floor_log2 (xored_di.high);
2028
      result_di.low = 0;
2029
      result_di.high &= ~(((unsigned HOST_WIDE_INT)1 << bitpos) - 1);
2030
    }
2031
  else if (xored_di.low)
2032
    {
2033
      bitpos = floor_log2 (xored_di.low);
2034
      result_di.low &= ~(((unsigned HOST_WIDE_INT)1 << bitpos) - 1);
2035
    }
2036
#if VDA_DEBUG
2037
  if (vda_file)
2038
    {
2039
      fprintf (vda_file, "// %s(%016lx, %016lx)=%016lx\n", "bits_always_set", min_di.low, max_di.low, result_di.low);
2040
    }
2041
#endif
2042
  return result_di;
2043
}
2044
2045
/* Combines MIN and MAX as follows:
2046
   MAX =   01010010101001010010
2047
   MIN =   01010010100000010010
2048
   result: 01010010101111111111.
2049
   Zeros are bits which are always 0 for any X in [MIN, MAX].
2050
   Conversely, ones are bits can be set.  */
2051
2052
static double_int
2053
bits_maybe_set (double_int min_di, double_int max_di)
2054
{
2055
  double_int xored_di, result_di;
2056
  int bitpos;
2057
2058
  result_di.low = min_di.low | max_di.low;
2059
  result_di.high = min_di.high | max_di.high;
2060
2061
  /* Find bit position of highest differing bit.  */
2062
  xored_di.low = min_di.low ^ max_di.low;
2063
  xored_di.high = min_di.high ^ max_di.high;
2064
  if (xored_di.high)
2065
    {
2066
      bitpos = floor_log2 (xored_di.high);
2067
      /* Build a 0000001111 mask, OR it to the result.  */
2068
      result_di.low = ALL_ONES;
2069
      result_di.high |= ((unsigned HOST_WIDE_INT)1 << bitpos) - 1;
2070
#if VDA_DEBUG
2071
      if (vda_file)
2072
	{
2073
	  fprintf (vda_file, "// %s(%016lx, %016lx)=%016lx @a [%016lx:%d]\n", "bits_maybe_set", min_di.low, max_di.low, result_di.low, xored_di.low, bitpos);
2074
	}
2075
#endif
2076
    }
2077
  else if (xored_di.low & (ALL_ONES - 1))
2078
    {
2079
      bitpos = floor_log2 (xored_di.low);
2080
      result_di.low |= ((unsigned HOST_WIDE_INT)1 << bitpos) - 1;
2081
#if VDA_DEBUG
2082
      if (vda_file)
2083
	{
2084
	  fprintf (vda_file, "// %s(%016lx, %016lx)=%016lx @b [%016lx:%d]\n", "bits_maybe_set", min_di.low, max_di.low, result_di.low, xored_di.low, bitpos);
2085
	}
2086
#endif
2087
    }
2088
#if VDA_DEBUG
2089
  else if (vda_file)
2090
    {
2091
      fprintf (vda_file, "// %s(%016lx, %016lx)=%016lx @c\n", "bits_maybe_set", min_di.low, max_di.low, result_di.low);
2092
    }
2093
#endif
2094
  return result_di;
2095
}
2096
2097
/* Are both ends of this range known, are integers, and >= 0?  */
2098
2099
#if !VDA_DEBUG
2100
/* Only vr is used if not debugging.  */
2101
#define integer_nonnegative_range(vr, val, vall) integer_nonnegative_range(vr)
2102
#endif
2103
static int
2104
integer_nonnegative_range (value_range_t *vr, tree val, char vall)
2105
{
2106
  if (vr->type == VR_RANGE
2107
      && TREE_CODE (vr->min) == INTEGER_CST
2108
      && TREE_CODE (vr->max) == INTEGER_CST
2109
      && tree_int_cst_sgn (vr->min) >= 0
2110
      && tree_int_cst_sgn (vr->max) >= 0
2111
      && !TREE_OVERFLOW (vr->max))
2112
    {
2113
#if VDA_DEBUG
2114
      if (vda_file)
2115
	{ /* 'if ((uNN)a >= 0 && (uNN)a <= 27030)" */
2116
	  tree val_type = TREE_TYPE (val);
2117
	  fprintf (vda_file, "if ((%c%ld)%c >= ",
2118
		   TYPE_UNSIGNED (val_type) ? 'u' : 's',
2119
		   tree_to_double_int (TYPE_SIZE (val_type)).low,
2120
		   vall
2121
		  );
2122
	  print_generic_expr (vda_file, vr->min, 0);
2123
	  fprintf (vda_file, " && (%c%ld)%c <= ",
2124
		   TYPE_UNSIGNED (val_type) ? 'u' : 's',
2125
		   tree_to_double_int (TYPE_SIZE (val_type)).low,
2126
		   vall
2127
		  );
2128
	  print_generic_expr (vda_file, vr->max, 0);
2129
	  fprintf (vda_file, ")\n");
2130
	}
2131
#endif
2132
      return 1;
2133
    }
2134
#if VDA_DEBUG
2135
  if (vda_file)
2136
    {
2137
      fprintf (vda_file, "// %c %s(", vall, "integer_nonnegative_range");
2138
      print_generic_expr (vda_file, TREE_TYPE (val), 0);
2139
      fprintf (vda_file, " ");
2140
      print_generic_expr (vda_file, val, 0);
2141
      fprintf (vda_file, ")=0\n");
2142
    }
2143
#endif
2144
  return 0;
2145
}
1998
2146
1999
/* Extract range information from a binary expression EXPR based on
2147
/* Extract range information from a binary expression EXPR based on
2000
   the ranges of each of its operands and the expression code.  */
2148
   the ranges of each of its operands and the expression code.  */
Lines 2010-2015 extract_range_from_binary_expr (value_ra Link Here
2010
  value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2158
  value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2011
  value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2159
  value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2012
2160
2161
#if VDA_DEBUG
2162
  char typebuf[16];
2163
  static int inited;
2164
  if (!inited)
2165
    {
2166
      if (getenv ("VDA_DEBUG"))
2167
	vda_file = fopen (getenv ("VDA_DEBUG"), "a");
2168
      inited = 1;
2169
    }
2170
#endif
2171
2013
  /* Not all binary expressions can be applied to ranges in a
2172
  /* Not all binary expressions can be applied to ranges in a
2014
     meaningful way.  Handle only arithmetic operations.  */
2173
     meaningful way.  Handle only arithmetic operations.  */
2015
  if (code != PLUS_EXPR
2174
  if (code != PLUS_EXPR
Lines 2025-2030 extract_range_from_binary_expr (value_ra Link Here
2025
      && code != MIN_EXPR
2184
      && code != MIN_EXPR
2026
      && code != MAX_EXPR
2185
      && code != MAX_EXPR
2027
      && code != BIT_AND_EXPR
2186
      && code != BIT_AND_EXPR
2187
      && code != BIT_IOR_EXPR
2028
      && code != TRUTH_AND_EXPR
2188
      && code != TRUTH_AND_EXPR
2029
      && code != TRUTH_OR_EXPR)
2189
      && code != TRUTH_OR_EXPR)
2030
    {
2190
    {
Lines 2032-2037 extract_range_from_binary_expr (value_ra Link Here
2032
      return;
2192
      return;
2033
    }
2193
    }
2034
2194
2195
#if VDA_DEBUG
2196
  if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
2197
    if (vda_file)
2198
      {
2199
	sprintf (typebuf, "%c%ld",
2200
		 TYPE_UNSIGNED (expr_type) ? 'u' : 's',
2201
		 tree_to_double_int (TYPE_SIZE (expr_type)).low);
2202
	fprintf (vda_file, "// %s(%s)[%s]\n",
2203
		 "extract_range_from_binary_expr",
2204
		 code == BIT_AND_EXPR ? "AND" : "OR", typebuf);
2205
      }
2206
#endif
2207
2035
  /* Get value ranges for each operand.  For constant operands, create
2208
  /* Get value ranges for each operand.  For constant operands, create
2036
     a new value range with the operand to simplify processing.  */
2209
     a new value range with the operand to simplify processing.  */
2037
  if (TREE_CODE (op0) == SSA_NAME)
2210
  if (TREE_CODE (op0) == SSA_NAME)
Lines 2048-2053 extract_range_from_binary_expr (value_ra Link Here
2048
  else
2221
  else
2049
    set_value_range_to_varying (&vr1);
2222
    set_value_range_to_varying (&vr1);
2050
2223
2224
  /* Bitwise ops.  */
2225
  /* Width and signedness of operands is always the same here.  */
2226
  if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
2227
    {
2228
#if VDA_DEBUG
2229
      char opc = (code == BIT_AND_EXPR ? '&' : '|');
2230
#endif
2231
      if (integer_nonnegative_range (&vr0, op0, 'a'))
2232
	{
2233
	  if (integer_nonnegative_range (&vr1, op1, 'b'))
2234
	    {
2235
	      double_int always_set0, always_set1;
2236
	      double_int maybe_set0, maybe_set1;
2237
	      double_int min_di, max_di;
2238
2239
	      /* In always_setX, ones indicate "always set" bits.  */
2240
	      /* In maybe_setX, ZEROES indicate "always unset" bits,
2241
	         ones indicate bits which are "maybe set".  */
2242
	      min_di = tree_to_double_int (vr0.min);
2243
	      max_di = tree_to_double_int (vr0.max);
2244
	      always_set0 = bits_always_set (min_di, max_di);
2245
	      maybe_set0 = bits_maybe_set (min_di, max_di);
2246
	      min_di = tree_to_double_int (vr1.min);
2247
	      max_di = tree_to_double_int (vr1.max);
2248
	      always_set1 = bits_always_set (min_di, max_di);
2249
	      maybe_set1 = bits_maybe_set (min_di, max_di);
2250
	      if (code == BIT_AND_EXPR)
2251
	        {
2252
	          /* If bit is always set in a AND in b,
2253
	             it will be set in (a & b).  */
2254
	          min_di.low = always_set0.low & always_set1.low;
2255
	          min_di.high = always_set0.high & always_set1.high;
2256
	      	  /* If bit is maybe set in a AND in b,
2257
	      	     it may be set in (a & b).
2258
	      	     Example: max(010x & 10xx) = 0001
2259
	      	     (maybe_set0 = 0101, maybe_set1 = 1011).  */
2260
	          max_di.low = maybe_set0.low & maybe_set1.low;
2261
	          max_di.high = maybe_set0.high & maybe_set1.high;
2262
	        }
2263
	      else
2264
	        {
2265
	          min_di.low = always_set0.low | always_set1.low;
2266
	          min_di.high = always_set0.high | always_set1.high;
2267
	          max_di.low = maybe_set0.low | maybe_set1.low;
2268
	          max_di.high = maybe_set0.high | maybe_set1.high;
2269
	        }
2270
	      min = double_int_to_tree (expr_type, min_di);
2271
	      max = double_int_to_tree (expr_type, max_di);
2272
#if VDA_DEBUG
2273
	      if (vda_file)
2274
		{ /* "if ((a & b) < 0x0000000000000000 || (a & b) > 0x0000000000000001) err();" */
2275
		  double_int m = tree_to_double_int (max);
2276
		  if (!m.high)
2277
		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
2278
			typebuf, opc, tree_to_double_int (min).low,
2279
			typebuf, opc, m.low);
2280
		  else
2281
		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx%016lx) err();\n",
2282
			typebuf, opc, tree_to_double_int (min).low,
2283
			typebuf, opc, m.high, m.low);
2284
		}
2285
#endif
2286
	      set_value_range (vr, VR_RANGE, min, max, NULL);
2287
	      return;
2288
	    }
2289
	  /* Only op0 has nonnegative range.  */
2290
	  if (code == BIT_AND_EXPR)
2291
	    {
2292
	      /* We positively sure that (op0 & op1) can't be
2293
	         larger than vr0.max.  */
2294
	      max = vr0.max;
2295
	      min = build_int_cst (expr_type, 0);
2296
	      set_value_range (vr, VR_RANGE, min, max, NULL);
2297
#if VDA_DEBUG
2298
	      if (vda_file)
2299
		{
2300
		  double_int m = tree_to_double_int (max);
2301
		  if (!m.high)
2302
		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
2303
			typebuf, opc, tree_to_double_int (min).low,
2304
			typebuf, opc, m.low);
2305
		  else
2306
		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx%016lx) err();\n",
2307
			typebuf, opc, tree_to_double_int (min).low,
2308
			typebuf, opc, m.high, m.low);
2309
		}
2310
#endif
2311
	      return;
2312
	    }
2313
	  if (TYPE_UNSIGNED (expr_type))
2314
	    {
2315
	      /* If result is unsigned,
2316
	         we still can derive that (op0 | op1) >= op0.min.  */
2317
	      min = vr0.min;
2318
	      max = TYPE_MAX_VALUE (expr_type);
2319
	      set_value_range (vr, VR_RANGE, min, max, NULL);
2320
#if VDA_DEBUG
2321
	      if (vda_file)
2322
		{
2323
		  double_int m = tree_to_double_int (max);
2324
		  if (!m.high)
2325
		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
2326
			typebuf, opc, tree_to_double_int (min).low,
2327
			typebuf, opc, m.low);
2328
		  else
2329
		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx%016lx) err();\n",
2330
			typebuf, opc, tree_to_double_int (min).low,
2331
			typebuf, opc, m.high, m.low);
2332
		}
2333
#endif
2334
	      return;
2335
	    }
2336
#if VDA_DEBUG
2337
	  if (vda_file)
2338
	    fprintf (vda_file, " ((void)0); // %c: op0 >= 0, type is signed\n", opc);
2339
#endif
2340
	  set_value_range_to_varying (vr);
2341
	  return;
2342
	}
2343
      if (integer_nonnegative_range (&vr1, op1, 'b'))
2344
	{
2345
	  /* Only op1 has nonnegative range.  */
2346
	  if (code == BIT_AND_EXPR)
2347
	    {
2348
	      max = vr1.max;
2349
	      min = build_int_cst (expr_type, 0);
2350
#if VDA_DEBUG
2351
	      if (vda_file)
2352
		{
2353
		  double_int m = tree_to_double_int (max);
2354
		  if (!m.high)
2355
		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
2356
			typebuf, opc, tree_to_double_int (min).low,
2357
			typebuf, opc, m.low);
2358
		  else
2359
		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx%016lx) err();\n",
2360
			typebuf, opc, tree_to_double_int (min).low,
2361
			typebuf, opc, m.high, m.low);
2362
	        }
2363
#endif
2364
	      set_value_range (vr, VR_RANGE, min, max, NULL);
2365
	      return;
2366
	    }
2367
	  if (TYPE_UNSIGNED (expr_type))
2368
	    {
2369
	      min = vr1.min;
2370
	      max = TYPE_MAX_VALUE (expr_type);
2371
#if VDA_DEBUG
2372
	      if (vda_file)
2373
		{
2374
		  double_int m = tree_to_double_int (max);
2375
		  if (!m.high)
2376
		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
2377
			typebuf, opc, tree_to_double_int (min).low,
2378
			typebuf, opc, m.low);
2379
		  else
2380
		  fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx%016lx) err();\n",
2381
			typebuf, opc, tree_to_double_int (min).low,
2382
			typebuf, opc, m.high, m.low);
2383
		}
2384
#endif
2385
	      set_value_range (vr, VR_RANGE, min, max, NULL);
2386
	      return;
2387
	    }
2388
#if VDA_DEBUG
2389
	  if (vda_file)
2390
	    fprintf (vda_file, " ((void)0); // %c: op1 >= 0, type is signed\n", opc);
2391
	  set_value_range_to_varying (vr);
2392
	  return;
2393
#endif
2394
	}
2395
#if VDA_DEBUG
2396
      if (vda_file)
2397
	fprintf (vda_file, " ((void)0); // %c: none is >= 0\n", opc);
2398
#endif
2399
      set_value_range_to_varying (vr);
2400
      return;
2401
    }
2402
2051
  /* If either range is UNDEFINED, so is the result.  */
2403
  /* If either range is UNDEFINED, so is the result.  */
2052
  if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
2404
  if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
2053
    {
2405
    {
Lines 2059-2070 extract_range_from_binary_expr (value_ra Link Here
2059
  type = vr0.type;
2411
  type = vr0.type;
2060
2412
2061
  /* Refuse to operate on VARYING ranges, ranges of different kinds
2413
  /* Refuse to operate on VARYING ranges, ranges of different kinds
2062
     and symbolic ranges.  As an exception, we allow BIT_AND_EXPR
2414
     and symbolic ranges.  */
2063
     because we may be able to derive a useful range even if one of
2415
  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
2416
      && code != TRUTH_OR_EXPR
2069
      && (vr0.type == VR_VARYING
2417
      && (vr0.type == VR_VARYING
2070
	  || vr1.type == VR_VARYING
2418
	  || 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);
2690
      min = vrp_int_const_binop (code, vr0.min, vr1.max);
2343
      max = vrp_int_const_binop (code, vr0.max, vr1.min);
2691
      max = vrp_int_const_binop (code, vr0.max, vr1.min);
2344
    }
2692
    }
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
2693
  else
2373
    gcc_unreachable ();
2694
    gcc_unreachable ();
2374
2695

Return to bug 28632