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
Clear(Isolate * isolate,Address address,Address constant_pool)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
BinaryOpICState(Isolate * isolate,ExtraICState extra_ic_state)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
GetExtraICState() const48 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
ToString() const62 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
GenerateAheadOfTime(Isolate * isolate,void (* Generate)(Isolate *,const BinaryOpICState &))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
GetResultType() const207 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
operator <<(std::ostream & os,const BinaryOpICState & s)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
Update(Handle<Object> left,Handle<Object> right,Handle<Object> result)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
UpdateKind(Handle<Object> object,Kind kind) const284 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
KindToString(Kind kind)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
KindToType(Kind kind)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
GetStateName(State state)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
StateToType(Zone * zone,State state,Handle<Map> map)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
NewInputState(State old_state,Handle<Object> value)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
TargetState(Isolate * isolate,State old_state,State old_left,State old_right,Token::Value op,bool has_inlined_smi_code,Handle<Object> x,Handle<Object> y)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