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