1 // Copyright 2016 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "src/compiler/operation-typer.h" 6 7 #include "src/factory.h" 8 #include "src/isolate.h" 9 #include "src/type-cache.h" 10 #include "src/types.h" 11 12 #include "src/objects-inl.h" 13 14 namespace v8 { 15 namespace internal { 16 namespace compiler { 17 18 OperationTyper::OperationTyper(Isolate* isolate, Zone* zone) 19 : zone_(zone), cache_(TypeCache::Get()) { 20 Factory* factory = isolate->factory(); 21 singleton_false_ = Type::Constant(factory->false_value(), zone); 22 singleton_true_ = Type::Constant(factory->true_value(), zone); 23 singleton_the_hole_ = Type::Constant(factory->the_hole_value(), zone); 24 } 25 26 Type* OperationTyper::Merge(Type* left, Type* right) { 27 return Type::Union(left, right, zone()); 28 } 29 30 Type* OperationTyper::WeakenRange(Type* previous_range, Type* current_range) { 31 static const double kWeakenMinLimits[] = {0.0, 32 -1073741824.0, 33 -2147483648.0, 34 -4294967296.0, 35 -8589934592.0, 36 -17179869184.0, 37 -34359738368.0, 38 -68719476736.0, 39 -137438953472.0, 40 -274877906944.0, 41 -549755813888.0, 42 -1099511627776.0, 43 -2199023255552.0, 44 -4398046511104.0, 45 -8796093022208.0, 46 -17592186044416.0, 47 -35184372088832.0, 48 -70368744177664.0, 49 -140737488355328.0, 50 -281474976710656.0, 51 -562949953421312.0}; 52 static const double kWeakenMaxLimits[] = {0.0, 53 1073741823.0, 54 2147483647.0, 55 4294967295.0, 56 8589934591.0, 57 17179869183.0, 58 34359738367.0, 59 68719476735.0, 60 137438953471.0, 61 274877906943.0, 62 549755813887.0, 63 1099511627775.0, 64 2199023255551.0, 65 4398046511103.0, 66 8796093022207.0, 67 17592186044415.0, 68 35184372088831.0, 69 70368744177663.0, 70 140737488355327.0, 71 281474976710655.0, 72 562949953421311.0}; 73 STATIC_ASSERT(arraysize(kWeakenMinLimits) == arraysize(kWeakenMaxLimits)); 74 75 double current_min = current_range->Min(); 76 double new_min = current_min; 77 // Find the closest lower entry in the list of allowed 78 // minima (or negative infinity if there is no such entry). 79 if (current_min != previous_range->Min()) { 80 new_min = -V8_INFINITY; 81 for (double const min : kWeakenMinLimits) { 82 if (min <= current_min) { 83 new_min = min; 84 break; 85 } 86 } 87 } 88 89 double current_max = current_range->Max(); 90 double new_max = current_max; 91 // Find the closest greater entry in the list of allowed 92 // maxima (or infinity if there is no such entry). 93 if (current_max != previous_range->Max()) { 94 new_max = V8_INFINITY; 95 for (double const max : kWeakenMaxLimits) { 96 if (max >= current_max) { 97 new_max = max; 98 break; 99 } 100 } 101 } 102 103 return Type::Range(new_min, new_max, zone()); 104 } 105 106 Type* OperationTyper::Rangify(Type* type) { 107 if (type->IsRange()) return type; // Shortcut. 108 if (!type->Is(cache_.kInteger)) { 109 return type; // Give up on non-integer types. 110 } 111 double min = type->Min(); 112 double max = type->Max(); 113 // Handle the degenerate case of empty bitset types (such as 114 // OtherUnsigned31 and OtherSigned32 on 64-bit architectures). 115 if (std::isnan(min)) { 116 DCHECK(std::isnan(max)); 117 return type; 118 } 119 return Type::Range(min, max, zone()); 120 } 121 122 namespace { 123 124 // Returns the array's least element, ignoring NaN. 125 // There must be at least one non-NaN element. 126 // Any -0 is converted to 0. 127 double array_min(double a[], size_t n) { 128 DCHECK(n != 0); 129 double x = +V8_INFINITY; 130 for (size_t i = 0; i < n; ++i) { 131 if (!std::isnan(a[i])) { 132 x = std::min(a[i], x); 133 } 134 } 135 DCHECK(!std::isnan(x)); 136 return x == 0 ? 0 : x; // -0 -> 0 137 } 138 139 // Returns the array's greatest element, ignoring NaN. 140 // There must be at least one non-NaN element. 141 // Any -0 is converted to 0. 142 double array_max(double a[], size_t n) { 143 DCHECK(n != 0); 144 double x = -V8_INFINITY; 145 for (size_t i = 0; i < n; ++i) { 146 if (!std::isnan(a[i])) { 147 x = std::max(a[i], x); 148 } 149 } 150 DCHECK(!std::isnan(x)); 151 return x == 0 ? 0 : x; // -0 -> 0 152 } 153 154 } // namespace 155 156 Type* OperationTyper::AddRanger(double lhs_min, double lhs_max, double rhs_min, 157 double rhs_max) { 158 double results[4]; 159 results[0] = lhs_min + rhs_min; 160 results[1] = lhs_min + rhs_max; 161 results[2] = lhs_max + rhs_min; 162 results[3] = lhs_max + rhs_max; 163 // Since none of the inputs can be -0, the result cannot be -0 either. 164 // However, it can be nan (the sum of two infinities of opposite sign). 165 // On the other hand, if none of the "results" above is nan, then the actual 166 // result cannot be nan either. 167 int nans = 0; 168 for (int i = 0; i < 4; ++i) { 169 if (std::isnan(results[i])) ++nans; 170 } 171 if (nans == 4) return Type::NaN(); // [-inf..-inf] + [inf..inf] or vice versa 172 Type* range = 173 Type::Range(array_min(results, 4), array_max(results, 4), zone()); 174 return nans == 0 ? range : Type::Union(range, Type::NaN(), zone()); 175 // Examples: 176 // [-inf, -inf] + [+inf, +inf] = NaN 177 // [-inf, -inf] + [n, +inf] = [-inf, -inf] \/ NaN 178 // [-inf, +inf] + [n, +inf] = [-inf, +inf] \/ NaN 179 // [-inf, m] + [n, +inf] = [-inf, +inf] \/ NaN 180 } 181 182 Type* OperationTyper::SubtractRanger(RangeType* lhs, RangeType* rhs) { 183 double results[4]; 184 results[0] = lhs->Min() - rhs->Min(); 185 results[1] = lhs->Min() - rhs->Max(); 186 results[2] = lhs->Max() - rhs->Min(); 187 results[3] = lhs->Max() - rhs->Max(); 188 // Since none of the inputs can be -0, the result cannot be -0. 189 // However, it can be nan (the subtraction of two infinities of same sign). 190 // On the other hand, if none of the "results" above is nan, then the actual 191 // result cannot be nan either. 192 int nans = 0; 193 for (int i = 0; i < 4; ++i) { 194 if (std::isnan(results[i])) ++nans; 195 } 196 if (nans == 4) return Type::NaN(); // [inf..inf] - [inf..inf] (all same sign) 197 Type* range = 198 Type::Range(array_min(results, 4), array_max(results, 4), zone()); 199 return nans == 0 ? range : Type::Union(range, Type::NaN(), zone()); 200 // Examples: 201 // [-inf, +inf] - [-inf, +inf] = [-inf, +inf] \/ NaN 202 // [-inf, -inf] - [-inf, -inf] = NaN 203 // [-inf, -inf] - [n, +inf] = [-inf, -inf] \/ NaN 204 // [m, +inf] - [-inf, n] = [-inf, +inf] \/ NaN 205 } 206 207 Type* OperationTyper::ModulusRanger(RangeType* lhs, RangeType* rhs) { 208 double lmin = lhs->Min(); 209 double lmax = lhs->Max(); 210 double rmin = rhs->Min(); 211 double rmax = rhs->Max(); 212 213 double labs = std::max(std::abs(lmin), std::abs(lmax)); 214 double rabs = std::max(std::abs(rmin), std::abs(rmax)) - 1; 215 double abs = std::min(labs, rabs); 216 bool maybe_minus_zero = false; 217 double omin = 0; 218 double omax = 0; 219 if (lmin >= 0) { // {lhs} positive. 220 omin = 0; 221 omax = abs; 222 } else if (lmax <= 0) { // {lhs} negative. 223 omin = 0 - abs; 224 omax = 0; 225 maybe_minus_zero = true; 226 } else { 227 omin = 0 - abs; 228 omax = abs; 229 maybe_minus_zero = true; 230 } 231 232 Type* result = Type::Range(omin, omax, zone()); 233 if (maybe_minus_zero) result = Type::Union(result, Type::MinusZero(), zone()); 234 return result; 235 } 236 237 Type* OperationTyper::MultiplyRanger(Type* lhs, Type* rhs) { 238 double results[4]; 239 double lmin = lhs->AsRange()->Min(); 240 double lmax = lhs->AsRange()->Max(); 241 double rmin = rhs->AsRange()->Min(); 242 double rmax = rhs->AsRange()->Max(); 243 results[0] = lmin * rmin; 244 results[1] = lmin * rmax; 245 results[2] = lmax * rmin; 246 results[3] = lmax * rmax; 247 // If the result may be nan, we give up on calculating a precise type, 248 // because 249 // the discontinuity makes it too complicated. Note that even if none of 250 // the 251 // "results" above is nan, the actual result may still be, so we have to do 252 // a 253 // different check: 254 bool maybe_nan = (lhs->Maybe(cache_.kSingletonZero) && 255 (rmin == -V8_INFINITY || rmax == +V8_INFINITY)) || 256 (rhs->Maybe(cache_.kSingletonZero) && 257 (lmin == -V8_INFINITY || lmax == +V8_INFINITY)); 258 if (maybe_nan) return cache_.kIntegerOrMinusZeroOrNaN; // Giving up. 259 bool maybe_minuszero = (lhs->Maybe(cache_.kSingletonZero) && rmin < 0) || 260 (rhs->Maybe(cache_.kSingletonZero) && lmin < 0); 261 Type* range = 262 Type::Range(array_min(results, 4), array_max(results, 4), zone()); 263 return maybe_minuszero ? Type::Union(range, Type::MinusZero(), zone()) 264 : range; 265 } 266 267 Type* OperationTyper::ToNumber(Type* type) { 268 if (type->Is(Type::Number())) return type; 269 if (type->Is(Type::NullOrUndefined())) { 270 if (type->Is(Type::Null())) return cache_.kSingletonZero; 271 if (type->Is(Type::Undefined())) return Type::NaN(); 272 return Type::Union(Type::NaN(), cache_.kSingletonZero, zone()); 273 } 274 if (type->Is(Type::NumberOrUndefined())) { 275 return Type::Union(Type::Intersect(type, Type::Number(), zone()), 276 Type::NaN(), zone()); 277 } 278 if (type->Is(singleton_false_)) return cache_.kSingletonZero; 279 if (type->Is(singleton_true_)) return cache_.kSingletonOne; 280 if (type->Is(Type::Boolean())) return cache_.kZeroOrOne; 281 if (type->Is(Type::BooleanOrNumber())) { 282 return Type::Union(Type::Intersect(type, Type::Number(), zone()), 283 cache_.kZeroOrOne, zone()); 284 } 285 return Type::Number(); 286 } 287 288 Type* OperationTyper::NumericAdd(Type* lhs, Type* rhs) { 289 DCHECK(lhs->Is(Type::Number())); 290 DCHECK(rhs->Is(Type::Number())); 291 292 // We can give more precise types for integers. 293 if (!lhs->Is(cache_.kIntegerOrMinusZeroOrNaN) || 294 !rhs->Is(cache_.kIntegerOrMinusZeroOrNaN)) { 295 return Type::Number(); 296 } 297 Type* int_lhs = Type::Intersect(lhs, cache_.kInteger, zone()); 298 Type* int_rhs = Type::Intersect(rhs, cache_.kInteger, zone()); 299 Type* result = 300 AddRanger(int_lhs->Min(), int_lhs->Max(), int_rhs->Min(), int_rhs->Max()); 301 if (lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN())) { 302 result = Type::Union(result, Type::NaN(), zone()); 303 } 304 if (lhs->Maybe(Type::MinusZero()) && rhs->Maybe(Type::MinusZero())) { 305 result = Type::Union(result, Type::MinusZero(), zone()); 306 } 307 return result; 308 } 309 310 Type* OperationTyper::NumericSubtract(Type* lhs, Type* rhs) { 311 DCHECK(lhs->Is(Type::Number())); 312 DCHECK(rhs->Is(Type::Number())); 313 314 lhs = Rangify(lhs); 315 rhs = Rangify(rhs); 316 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); 317 if (lhs->IsRange() && rhs->IsRange()) { 318 return SubtractRanger(lhs->AsRange(), rhs->AsRange()); 319 } 320 // TODO(neis): Deal with numeric bitsets here and elsewhere. 321 return Type::Number(); 322 } 323 324 Type* OperationTyper::NumericMultiply(Type* lhs, Type* rhs) { 325 DCHECK(lhs->Is(Type::Number())); 326 DCHECK(rhs->Is(Type::Number())); 327 lhs = Rangify(lhs); 328 rhs = Rangify(rhs); 329 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); 330 if (lhs->IsRange() && rhs->IsRange()) { 331 return MultiplyRanger(lhs, rhs); 332 } 333 return Type::Number(); 334 } 335 336 Type* OperationTyper::NumericDivide(Type* lhs, Type* rhs) { 337 DCHECK(lhs->Is(Type::Number())); 338 DCHECK(rhs->Is(Type::Number())); 339 340 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); 341 // Division is tricky, so all we do is try ruling out nan. 342 bool maybe_nan = 343 lhs->Maybe(Type::NaN()) || rhs->Maybe(cache_.kZeroish) || 344 ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) && 345 (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY)); 346 return maybe_nan ? Type::Number() : Type::OrderedNumber(); 347 } 348 349 Type* OperationTyper::NumericModulus(Type* lhs, Type* rhs) { 350 DCHECK(lhs->Is(Type::Number())); 351 DCHECK(rhs->Is(Type::Number())); 352 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); 353 354 if (lhs->Maybe(Type::NaN()) || rhs->Maybe(cache_.kZeroish) || 355 lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) { 356 // Result maybe NaN. 357 return Type::Number(); 358 } 359 360 lhs = Rangify(lhs); 361 rhs = Rangify(rhs); 362 if (lhs->IsRange() && rhs->IsRange()) { 363 return ModulusRanger(lhs->AsRange(), rhs->AsRange()); 364 } 365 return Type::OrderedNumber(); 366 } 367 368 Type* OperationTyper::ToPrimitive(Type* type) { 369 if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) { 370 return type; 371 } 372 return Type::Primitive(); 373 } 374 375 Type* OperationTyper::Invert(Type* type) { 376 DCHECK(type->Is(Type::Boolean())); 377 DCHECK(type->IsInhabited()); 378 if (type->Is(singleton_false())) return singleton_true(); 379 if (type->Is(singleton_true())) return singleton_false(); 380 return type; 381 } 382 383 OperationTyper::ComparisonOutcome OperationTyper::Invert( 384 ComparisonOutcome outcome) { 385 ComparisonOutcome result(0); 386 if ((outcome & kComparisonUndefined) != 0) result |= kComparisonUndefined; 387 if ((outcome & kComparisonTrue) != 0) result |= kComparisonFalse; 388 if ((outcome & kComparisonFalse) != 0) result |= kComparisonTrue; 389 return result; 390 } 391 392 Type* OperationTyper::FalsifyUndefined(ComparisonOutcome outcome) { 393 if ((outcome & kComparisonFalse) != 0 || 394 (outcome & kComparisonUndefined) != 0) { 395 return (outcome & kComparisonTrue) != 0 ? Type::Boolean() 396 : singleton_false(); 397 } 398 // Type should be non empty, so we know it should be true. 399 DCHECK((outcome & kComparisonTrue) != 0); 400 return singleton_true(); 401 } 402 403 Type* OperationTyper::TypeJSAdd(Type* lhs, Type* rhs) { 404 lhs = ToPrimitive(lhs); 405 rhs = ToPrimitive(rhs); 406 if (lhs->Maybe(Type::String()) || rhs->Maybe(Type::String())) { 407 if (lhs->Is(Type::String()) || rhs->Is(Type::String())) { 408 return Type::String(); 409 } else { 410 return Type::NumberOrString(); 411 } 412 } 413 lhs = ToNumber(lhs); 414 rhs = ToNumber(rhs); 415 return NumericAdd(lhs, rhs); 416 } 417 418 Type* OperationTyper::TypeJSSubtract(Type* lhs, Type* rhs) { 419 return NumericSubtract(ToNumber(lhs), ToNumber(rhs)); 420 } 421 422 } // namespace compiler 423 } // namespace internal 424 } // namespace v8 425