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
12namespace v8 {
13namespace internal {
14
15// static
16void ICUtility::Clear(Isolate* isolate, Address address,
17                      Address constant_pool) {
18  IC::Clear(isolate, address, constant_pool);
19}
20
21
22// static
23STATIC_CONST_MEMBER_DEFINITION const int BinaryOpICState::FIRST_TOKEN;
24
25
26// static
27STATIC_CONST_MEMBER_DEFINITION const int BinaryOpICState::LAST_TOKEN;
28
29
30BinaryOpICState::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
48ExtraICState 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
62std::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
81void 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
207AstType* 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
221std::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
234void 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
284BinaryOpICState::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
314const 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
335AstType* 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
355const 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
382AstType* 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
410CompareICState::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
461CompareICState::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