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 |
|