1 // Copyright 2014 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/ic/ic-state.h" 6 7 #include "src/ast/ast-types.h" 8 #include "src/feedback-vector.h" 9 #include "src/ic/ic.h" 10 #include "src/objects-inl.h" 11 12 namespace v8 { 13 namespace internal { 14 15 // static 16 void ICUtility::Clear(Isolate* isolate, Address address, 17 Address constant_pool) { 18 IC::Clear(isolate, address, constant_pool); 19 } 20 21 22 // static 23 STATIC_CONST_MEMBER_DEFINITION const int BinaryOpICState::FIRST_TOKEN; 24 25 26 // static 27 STATIC_CONST_MEMBER_DEFINITION const int BinaryOpICState::LAST_TOKEN; 28 29 30 BinaryOpICState::BinaryOpICState(Isolate* isolate, ExtraICState extra_ic_state) 31 : fixed_right_arg_( 32 HasFixedRightArgField::decode(extra_ic_state) 33 ? Just(1 << FixedRightArgValueField::decode(extra_ic_state)) 34 : Nothing<int>()), 35 isolate_(isolate) { 36 op_ = 37 static_cast<Token::Value>(FIRST_TOKEN + OpField::decode(extra_ic_state)); 38 left_kind_ = LeftKindField::decode(extra_ic_state); 39 right_kind_ = fixed_right_arg_.IsJust() 40 ? (Smi::IsValid(fixed_right_arg_.FromJust()) ? SMI : INT32) 41 : RightKindField::decode(extra_ic_state); 42 result_kind_ = ResultKindField::decode(extra_ic_state); 43 DCHECK_LE(FIRST_TOKEN, op_); 44 DCHECK_LE(op_, LAST_TOKEN); 45 } 46 47 48 ExtraICState BinaryOpICState::GetExtraICState() const { 49 ExtraICState extra_ic_state = 50 OpField::encode(op_ - FIRST_TOKEN) | LeftKindField::encode(left_kind_) | 51 ResultKindField::encode(result_kind_) | 52 HasFixedRightArgField::encode(fixed_right_arg_.IsJust()); 53 if (fixed_right_arg_.IsJust()) { 54 extra_ic_state = FixedRightArgValueField::update( 55 extra_ic_state, WhichPowerOf2(fixed_right_arg_.FromJust())); 56 } else { 57 extra_ic_state = RightKindField::update(extra_ic_state, right_kind_); 58 } 59 return extra_ic_state; 60 } 61 62 std::string BinaryOpICState::ToString() const { 63 std::string ret = "("; 64 ret += Token::Name(op_); 65 if (CouldCreateAllocationMementos()) ret += "_CreateAllocationMementos"; 66 ret += ":"; 67 ret += BinaryOpICState::KindToString(left_kind_); 68 ret += "*"; 69 if (fixed_right_arg_.IsJust()) { 70 ret += fixed_right_arg_.FromJust(); 71 } else { 72 ret += BinaryOpICState::KindToString(right_kind_); 73 } 74 ret += "->"; 75 ret += BinaryOpICState::KindToString(result_kind_); 76 ret += ")"; 77 return ret; 78 } 79 80 // static 81 void BinaryOpICState::GenerateAheadOfTime( 82 Isolate* isolate, void (*Generate)(Isolate*, const BinaryOpICState&)) { 83 // TODO(olivf) We should investigate why adding stubs to the snapshot is so 84 // expensive at runtime. When solved we should be able to add most binops to 85 // the snapshot instead of hand-picking them. 86 // Generated list of commonly used stubs 87 #define GENERATE(op, left_kind, right_kind, result_kind) \ 88 do { \ 89 BinaryOpICState state(isolate, op); \ 90 state.left_kind_ = left_kind; \ 91 state.fixed_right_arg_ = Nothing<int>(); \ 92 state.right_kind_ = right_kind; \ 93 state.result_kind_ = result_kind; \ 94 Generate(isolate, state); \ 95 } while (false) 96 GENERATE(Token::ADD, INT32, INT32, INT32); 97 GENERATE(Token::ADD, INT32, INT32, NUMBER); 98 GENERATE(Token::ADD, INT32, NUMBER, NUMBER); 99 GENERATE(Token::ADD, INT32, SMI, INT32); 100 GENERATE(Token::ADD, NUMBER, INT32, NUMBER); 101 GENERATE(Token::ADD, NUMBER, NUMBER, NUMBER); 102 GENERATE(Token::ADD, NUMBER, SMI, NUMBER); 103 GENERATE(Token::ADD, SMI, INT32, INT32); 104 GENERATE(Token::ADD, SMI, INT32, NUMBER); 105 GENERATE(Token::ADD, SMI, NUMBER, NUMBER); 106 GENERATE(Token::ADD, SMI, SMI, INT32); 107 GENERATE(Token::ADD, SMI, SMI, SMI); 108 GENERATE(Token::BIT_AND, INT32, INT32, INT32); 109 GENERATE(Token::BIT_AND, INT32, INT32, SMI); 110 GENERATE(Token::BIT_AND, INT32, SMI, INT32); 111 GENERATE(Token::BIT_AND, INT32, SMI, SMI); 112 GENERATE(Token::BIT_AND, NUMBER, INT32, INT32); 113 GENERATE(Token::BIT_AND, NUMBER, SMI, SMI); 114 GENERATE(Token::BIT_AND, SMI, INT32, INT32); 115 GENERATE(Token::BIT_AND, SMI, INT32, SMI); 116 GENERATE(Token::BIT_AND, SMI, NUMBER, SMI); 117 GENERATE(Token::BIT_AND, SMI, SMI, SMI); 118 GENERATE(Token::BIT_OR, INT32, INT32, INT32); 119 GENERATE(Token::BIT_OR, INT32, INT32, SMI); 120 GENERATE(Token::BIT_OR, INT32, SMI, INT32); 121 GENERATE(Token::BIT_OR, INT32, SMI, SMI); 122 GENERATE(Token::BIT_OR, NUMBER, SMI, INT32); 123 GENERATE(Token::BIT_OR, NUMBER, SMI, SMI); 124 GENERATE(Token::BIT_OR, SMI, INT32, INT32); 125 GENERATE(Token::BIT_OR, SMI, INT32, SMI); 126 GENERATE(Token::BIT_OR, SMI, SMI, SMI); 127 GENERATE(Token::BIT_XOR, INT32, INT32, INT32); 128 GENERATE(Token::BIT_XOR, INT32, INT32, SMI); 129 GENERATE(Token::BIT_XOR, INT32, NUMBER, SMI); 130 GENERATE(Token::BIT_XOR, INT32, SMI, INT32); 131 GENERATE(Token::BIT_XOR, NUMBER, INT32, INT32); 132 GENERATE(Token::BIT_XOR, NUMBER, SMI, INT32); 133 GENERATE(Token::BIT_XOR, NUMBER, SMI, SMI); 134 GENERATE(Token::BIT_XOR, SMI, INT32, INT32); 135 GENERATE(Token::BIT_XOR, SMI, INT32, SMI); 136 GENERATE(Token::BIT_XOR, SMI, SMI, SMI); 137 GENERATE(Token::DIV, INT32, INT32, INT32); 138 GENERATE(Token::DIV, INT32, INT32, NUMBER); 139 GENERATE(Token::DIV, INT32, NUMBER, NUMBER); 140 GENERATE(Token::DIV, INT32, SMI, INT32); 141 GENERATE(Token::DIV, INT32, SMI, NUMBER); 142 GENERATE(Token::DIV, NUMBER, INT32, NUMBER); 143 GENERATE(Token::DIV, NUMBER, NUMBER, NUMBER); 144 GENERATE(Token::DIV, NUMBER, SMI, NUMBER); 145 GENERATE(Token::DIV, SMI, INT32, INT32); 146 GENERATE(Token::DIV, SMI, INT32, NUMBER); 147 GENERATE(Token::DIV, SMI, NUMBER, NUMBER); 148 GENERATE(Token::DIV, SMI, SMI, NUMBER); 149 GENERATE(Token::DIV, SMI, SMI, SMI); 150 GENERATE(Token::MOD, NUMBER, SMI, NUMBER); 151 GENERATE(Token::MOD, SMI, SMI, SMI); 152 GENERATE(Token::MUL, INT32, INT32, INT32); 153 GENERATE(Token::MUL, INT32, INT32, NUMBER); 154 GENERATE(Token::MUL, INT32, NUMBER, NUMBER); 155 GENERATE(Token::MUL, INT32, SMI, INT32); 156 GENERATE(Token::MUL, INT32, SMI, NUMBER); 157 GENERATE(Token::MUL, NUMBER, INT32, NUMBER); 158 GENERATE(Token::MUL, NUMBER, NUMBER, NUMBER); 159 GENERATE(Token::MUL, NUMBER, SMI, NUMBER); 160 GENERATE(Token::MUL, SMI, INT32, INT32); 161 GENERATE(Token::MUL, SMI, INT32, NUMBER); 162 GENERATE(Token::MUL, SMI, NUMBER, NUMBER); 163 GENERATE(Token::MUL, SMI, SMI, INT32); 164 GENERATE(Token::MUL, SMI, SMI, NUMBER); 165 GENERATE(Token::MUL, SMI, SMI, SMI); 166 GENERATE(Token::SAR, INT32, SMI, INT32); 167 GENERATE(Token::SAR, INT32, SMI, SMI); 168 GENERATE(Token::SAR, NUMBER, SMI, SMI); 169 GENERATE(Token::SAR, SMI, SMI, SMI); 170 GENERATE(Token::SHL, INT32, SMI, INT32); 171 GENERATE(Token::SHL, INT32, SMI, SMI); 172 GENERATE(Token::SHL, NUMBER, SMI, SMI); 173 GENERATE(Token::SHL, SMI, SMI, INT32); 174 GENERATE(Token::SHL, SMI, SMI, SMI); 175 GENERATE(Token::SHR, INT32, SMI, SMI); 176 GENERATE(Token::SHR, NUMBER, SMI, INT32); 177 GENERATE(Token::SHR, NUMBER, SMI, SMI); 178 GENERATE(Token::SHR, SMI, SMI, SMI); 179 GENERATE(Token::SUB, INT32, INT32, INT32); 180 GENERATE(Token::SUB, INT32, NUMBER, NUMBER); 181 GENERATE(Token::SUB, INT32, SMI, INT32); 182 GENERATE(Token::SUB, NUMBER, INT32, NUMBER); 183 GENERATE(Token::SUB, NUMBER, NUMBER, NUMBER); 184 GENERATE(Token::SUB, NUMBER, SMI, NUMBER); 185 GENERATE(Token::SUB, SMI, INT32, INT32); 186 GENERATE(Token::SUB, SMI, NUMBER, NUMBER); 187 GENERATE(Token::SUB, SMI, SMI, SMI); 188 #undef GENERATE 189 #define GENERATE(op, left_kind, fixed_right_arg_value, result_kind) \ 190 do { \ 191 BinaryOpICState state(isolate, op); \ 192 state.left_kind_ = left_kind; \ 193 state.fixed_right_arg_ = Just(fixed_right_arg_value); \ 194 state.right_kind_ = SMI; \ 195 state.result_kind_ = result_kind; \ 196 Generate(isolate, state); \ 197 } while (false) 198 GENERATE(Token::MOD, SMI, 2, SMI); 199 GENERATE(Token::MOD, SMI, 4, SMI); 200 GENERATE(Token::MOD, SMI, 8, SMI); 201 GENERATE(Token::MOD, SMI, 16, SMI); 202 GENERATE(Token::MOD, SMI, 32, SMI); 203 GENERATE(Token::MOD, SMI, 2048, SMI); 204 #undef GENERATE 205 } 206 207 AstType* BinaryOpICState::GetResultType() const { 208 Kind result_kind = result_kind_; 209 if (HasSideEffects()) { 210 result_kind = NONE; 211 } else if (result_kind == GENERIC && op_ == Token::ADD) { 212 return AstType::NumberOrString(); 213 } else if (result_kind == NUMBER && op_ == Token::SHR) { 214 return AstType::Unsigned32(); 215 } 216 DCHECK_NE(GENERIC, result_kind); 217 return KindToType(result_kind); 218 } 219 220 221 std::ostream& operator<<(std::ostream& os, const BinaryOpICState& s) { 222 os << "(" << Token::Name(s.op_); 223 if (s.CouldCreateAllocationMementos()) os << "_CreateAllocationMementos"; 224 os << ":" << BinaryOpICState::KindToString(s.left_kind_) << "*"; 225 if (s.fixed_right_arg_.IsJust()) { 226 os << s.fixed_right_arg_.FromJust(); 227 } else { 228 os << BinaryOpICState::KindToString(s.right_kind_); 229 } 230 return os << "->" << BinaryOpICState::KindToString(s.result_kind_) << ")"; 231 } 232 233 234 void BinaryOpICState::Update(Handle<Object> left, Handle<Object> right, 235 Handle<Object> result) { 236 ExtraICState old_extra_ic_state = GetExtraICState(); 237 238 left_kind_ = UpdateKind(left, left_kind_); 239 right_kind_ = UpdateKind(right, right_kind_); 240 241 int32_t fixed_right_arg_value = 0; 242 bool has_fixed_right_arg = 243 op_ == Token::MOD && right->ToInt32(&fixed_right_arg_value) && 244 fixed_right_arg_value > 0 && 245 base::bits::IsPowerOfTwo32(fixed_right_arg_value) && 246 FixedRightArgValueField::is_valid(WhichPowerOf2(fixed_right_arg_value)) && 247 (left_kind_ == SMI || left_kind_ == INT32) && 248 (result_kind_ == NONE || !fixed_right_arg_.IsJust()); 249 fixed_right_arg_ = 250 has_fixed_right_arg ? Just(fixed_right_arg_value) : Nothing<int32_t>(); 251 result_kind_ = UpdateKind(result, result_kind_); 252 253 if (!Token::IsTruncatingBinaryOp(op_)) { 254 Kind input_kind = Max(left_kind_, right_kind_); 255 if (result_kind_ < input_kind && input_kind <= NUMBER) { 256 result_kind_ = input_kind; 257 } 258 } 259 260 // We don't want to distinguish INT32 and NUMBER for string add (because 261 // NumberToString can't make use of this anyway). 262 if (left_kind_ == STRING && right_kind_ == INT32) { 263 DCHECK_EQ(STRING, result_kind_); 264 DCHECK_EQ(Token::ADD, op_); 265 right_kind_ = NUMBER; 266 } else if (right_kind_ == STRING && left_kind_ == INT32) { 267 DCHECK_EQ(STRING, result_kind_); 268 DCHECK_EQ(Token::ADD, op_); 269 left_kind_ = NUMBER; 270 } 271 272 if (old_extra_ic_state == GetExtraICState()) { 273 // Tagged operations can lead to non-truncating HChanges 274 if (left->IsOddball()) { 275 left_kind_ = GENERIC; 276 } else { 277 DCHECK(right->IsOddball()); 278 right_kind_ = GENERIC; 279 } 280 } 281 } 282 283 284 BinaryOpICState::Kind BinaryOpICState::UpdateKind(Handle<Object> object, 285 Kind kind) const { 286 Kind new_kind = GENERIC; 287 bool is_truncating = Token::IsTruncatingBinaryOp(op()); 288 if (object->IsOddball() && is_truncating) { 289 // Oddballs will be automatically truncated by HChange. 290 new_kind = INT32; 291 } else if (object->IsUndefined(isolate_)) { 292 // Undefined will be automatically truncated by HChange. 293 new_kind = is_truncating ? INT32 : NUMBER; 294 } else if (object->IsSmi()) { 295 new_kind = SMI; 296 } else if (object->IsHeapNumber()) { 297 double value = Handle<HeapNumber>::cast(object)->value(); 298 new_kind = IsInt32Double(value) ? INT32 : NUMBER; 299 } else if (object->IsString() && op() == Token::ADD) { 300 new_kind = STRING; 301 } 302 if (new_kind == INT32 && SmiValuesAre32Bits()) { 303 new_kind = NUMBER; 304 } 305 if (kind != NONE && ((new_kind <= NUMBER && kind > NUMBER) || 306 (new_kind > NUMBER && kind <= NUMBER))) { 307 new_kind = GENERIC; 308 } 309 return Max(kind, new_kind); 310 } 311 312 313 // static 314 const char* BinaryOpICState::KindToString(Kind kind) { 315 switch (kind) { 316 case NONE: 317 return "None"; 318 case SMI: 319 return "Smi"; 320 case INT32: 321 return "Int32"; 322 case NUMBER: 323 return "Number"; 324 case STRING: 325 return "String"; 326 case GENERIC: 327 return "Generic"; 328 } 329 UNREACHABLE(); 330 return NULL; 331 } 332 333 334 // static 335 AstType* BinaryOpICState::KindToType(Kind kind) { 336 switch (kind) { 337 case NONE: 338 return AstType::None(); 339 case SMI: 340 return AstType::SignedSmall(); 341 case INT32: 342 return AstType::Signed32(); 343 case NUMBER: 344 return AstType::Number(); 345 case STRING: 346 return AstType::String(); 347 case GENERIC: 348 return AstType::Any(); 349 } 350 UNREACHABLE(); 351 return NULL; 352 } 353 354 355 const char* CompareICState::GetStateName(State state) { 356 switch (state) { 357 case UNINITIALIZED: 358 return "UNINITIALIZED"; 359 case BOOLEAN: 360 return "BOOLEAN"; 361 case SMI: 362 return "SMI"; 363 case NUMBER: 364 return "NUMBER"; 365 case INTERNALIZED_STRING: 366 return "INTERNALIZED_STRING"; 367 case STRING: 368 return "STRING"; 369 case UNIQUE_NAME: 370 return "UNIQUE_NAME"; 371 case RECEIVER: 372 return "RECEIVER"; 373 case KNOWN_RECEIVER: 374 return "KNOWN_RECEIVER"; 375 case GENERIC: 376 return "GENERIC"; 377 } 378 UNREACHABLE(); 379 return NULL; 380 } 381 382 AstType* CompareICState::StateToType(Zone* zone, State state, Handle<Map> map) { 383 switch (state) { 384 case UNINITIALIZED: 385 return AstType::None(); 386 case BOOLEAN: 387 return AstType::Boolean(); 388 case SMI: 389 return AstType::SignedSmall(); 390 case NUMBER: 391 return AstType::Number(); 392 case STRING: 393 return AstType::String(); 394 case INTERNALIZED_STRING: 395 return AstType::InternalizedString(); 396 case UNIQUE_NAME: 397 return AstType::UniqueName(); 398 case RECEIVER: 399 return AstType::Receiver(); 400 case KNOWN_RECEIVER: 401 return map.is_null() ? AstType::Receiver() : AstType::Class(map, zone); 402 case GENERIC: 403 return AstType::Any(); 404 } 405 UNREACHABLE(); 406 return NULL; 407 } 408 409 410 CompareICState::State CompareICState::NewInputState(State old_state, 411 Handle<Object> value) { 412 switch (old_state) { 413 case UNINITIALIZED: 414 if (value->IsBoolean()) return BOOLEAN; 415 if (value->IsSmi()) return SMI; 416 if (value->IsHeapNumber()) return NUMBER; 417 if (value->IsInternalizedString()) return INTERNALIZED_STRING; 418 if (value->IsString()) return STRING; 419 if (value->IsSymbol()) return UNIQUE_NAME; 420 if (value->IsJSReceiver() && !value->IsUndetectable()) { 421 return RECEIVER; 422 } 423 break; 424 case BOOLEAN: 425 if (value->IsBoolean()) return BOOLEAN; 426 break; 427 case SMI: 428 if (value->IsSmi()) return SMI; 429 if (value->IsHeapNumber()) return NUMBER; 430 break; 431 case NUMBER: 432 if (value->IsNumber()) return NUMBER; 433 break; 434 case INTERNALIZED_STRING: 435 if (value->IsInternalizedString()) return INTERNALIZED_STRING; 436 if (value->IsString()) return STRING; 437 if (value->IsSymbol()) return UNIQUE_NAME; 438 break; 439 case STRING: 440 if (value->IsString()) return STRING; 441 break; 442 case UNIQUE_NAME: 443 if (value->IsUniqueName()) return UNIQUE_NAME; 444 break; 445 case RECEIVER: 446 if (value->IsJSReceiver() && !value->IsUndetectable()) { 447 return RECEIVER; 448 } 449 break; 450 case GENERIC: 451 break; 452 case KNOWN_RECEIVER: 453 UNREACHABLE(); 454 break; 455 } 456 return GENERIC; 457 } 458 459 460 // static 461 CompareICState::State CompareICState::TargetState( 462 Isolate* isolate, State old_state, State old_left, State old_right, 463 Token::Value op, bool has_inlined_smi_code, Handle<Object> x, 464 Handle<Object> y) { 465 switch (old_state) { 466 case UNINITIALIZED: 467 if (x->IsBoolean() && y->IsBoolean()) return BOOLEAN; 468 if (x->IsSmi() && y->IsSmi()) return SMI; 469 if (x->IsNumber() && y->IsNumber()) return NUMBER; 470 if (Token::IsOrderedRelationalCompareOp(op)) { 471 // Ordered comparisons treat undefined as NaN, so the 472 // NUMBER stub will do the right thing. 473 if ((x->IsNumber() && y->IsUndefined(isolate)) || 474 (y->IsNumber() && x->IsUndefined(isolate))) { 475 return NUMBER; 476 } 477 } 478 if (x->IsInternalizedString() && y->IsInternalizedString()) { 479 // We compare internalized strings as plain ones if we need to determine 480 // the order in a non-equality compare. 481 return Token::IsEqualityOp(op) ? INTERNALIZED_STRING : STRING; 482 } 483 if (x->IsString() && y->IsString()) return STRING; 484 if (x->IsJSReceiver() && y->IsJSReceiver()) { 485 if (x->IsUndetectable() || y->IsUndetectable()) { 486 return GENERIC; 487 } 488 if (Handle<JSReceiver>::cast(x)->map() == 489 Handle<JSReceiver>::cast(y)->map()) { 490 return KNOWN_RECEIVER; 491 } else { 492 return Token::IsEqualityOp(op) ? RECEIVER : GENERIC; 493 } 494 } 495 if (!Token::IsEqualityOp(op)) return GENERIC; 496 if (x->IsUniqueName() && y->IsUniqueName()) return UNIQUE_NAME; 497 return GENERIC; 498 case SMI: 499 return x->IsNumber() && y->IsNumber() ? NUMBER : GENERIC; 500 case INTERNALIZED_STRING: 501 DCHECK(Token::IsEqualityOp(op)); 502 if (x->IsString() && y->IsString()) return STRING; 503 if (x->IsUniqueName() && y->IsUniqueName()) return UNIQUE_NAME; 504 return GENERIC; 505 case NUMBER: 506 // If the failure was due to one side changing from smi to heap number, 507 // then keep the state (if other changed at the same time, we will get 508 // a second miss and then go to generic). 509 if (old_left == SMI && x->IsHeapNumber()) return NUMBER; 510 if (old_right == SMI && y->IsHeapNumber()) return NUMBER; 511 return GENERIC; 512 case KNOWN_RECEIVER: 513 if (x->IsJSReceiver() && y->IsJSReceiver()) { 514 return Token::IsEqualityOp(op) ? RECEIVER : GENERIC; 515 } 516 return GENERIC; 517 case BOOLEAN: 518 case STRING: 519 case UNIQUE_NAME: 520 case RECEIVER: 521 case GENERIC: 522 return GENERIC; 523 } 524 UNREACHABLE(); 525 return GENERIC; // Make the compiler happy. 526 } 527 528 } // namespace internal 529 } // namespace v8 530
