1// Copyright 2013 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/crankshaft/typing.h"
6
7#include "src/ast/compile-time-value.h"
8#include "src/ast/scopes.h"
9#include "src/ast/variables.h"
10#include "src/frames-inl.h"
11#include "src/frames.h"
12#include "src/ostreams.h"
13#include "src/splay-tree-inl.h"
14
15namespace v8 {
16namespace internal {
17
18AstTyper::AstTyper(Isolate* isolate, Zone* zone, Handle<JSFunction> closure,
19                   DeclarationScope* scope, BailoutId osr_ast_id,
20                   FunctionLiteral* root, AstTypeBounds* bounds)
21    : isolate_(isolate),
22      zone_(zone),
23      closure_(closure),
24      scope_(scope),
25      osr_ast_id_(osr_ast_id),
26      root_(root),
27      oracle_(isolate, zone, handle(closure->shared()->code()),
28              handle(closure->feedback_vector()),
29              handle(closure->context()->native_context())),
30      store_(zone),
31      bounds_(bounds) {
32  InitializeAstVisitor(isolate);
33}
34
35
36#ifdef OBJECT_PRINT
37static void PrintObserved(Variable* var, Object* value, AstType* type) {
38  OFStream os(stdout);
39  os << "  observed " << (var->IsParameter() ? "param" : "local") << "  ";
40  var->name()->Print(os);
41  os << " : " << Brief(value) << " -> ";
42  type->PrintTo(os);
43  os << std::endl;
44  }
45#endif  // OBJECT_PRINT
46
47
48Effect AstTyper::ObservedOnStack(Object* value) {
49  AstType* lower = AstType::NowOf(value, zone());
50  return Effect(AstBounds(lower, AstType::Any()));
51}
52
53
54void AstTyper::ObserveTypesAtOsrEntry(IterationStatement* stmt) {
55  if (stmt->OsrEntryId() != osr_ast_id_) return;
56
57  DisallowHeapAllocation no_gc;
58  JavaScriptFrameIterator it(isolate_);
59  JavaScriptFrame* frame = it.frame();
60
61  // Assert that the frame on the stack belongs to the function we want to OSR.
62  DCHECK_EQ(*closure_, frame->function());
63
64  int params = scope_->num_parameters();
65  int locals = scope_->StackLocalCount();
66
67  // Use sequential composition to achieve desired narrowing.
68  // The receiver is a parameter with index -1.
69  store_.Seq(parameter_index(-1), ObservedOnStack(frame->receiver()));
70  for (int i = 0; i < params; i++) {
71    store_.Seq(parameter_index(i), ObservedOnStack(frame->GetParameter(i)));
72  }
73
74  for (int i = 0; i < locals; i++) {
75    store_.Seq(stack_local_index(i), ObservedOnStack(frame->GetExpression(i)));
76  }
77
78#ifdef OBJECT_PRINT
79  if (FLAG_trace_osr && FLAG_print_scopes) {
80    PrintObserved(scope_->receiver(), frame->receiver(),
81                  store_.LookupBounds(parameter_index(-1)).lower);
82
83    for (int i = 0; i < params; i++) {
84      PrintObserved(scope_->parameter(i), frame->GetParameter(i),
85                    store_.LookupBounds(parameter_index(i)).lower);
86    }
87
88    int local_index = 0;
89    for (Variable* var : *scope_->locals()) {
90      if (var->IsStackLocal()) {
91        PrintObserved(
92            var, frame->GetExpression(local_index),
93            store_.LookupBounds(stack_local_index(local_index)).lower);
94        local_index++;
95      }
96    }
97  }
98#endif  // OBJECT_PRINT
99}
100
101
102#define RECURSE(call)                \
103  do {                               \
104    DCHECK(!HasStackOverflow());     \
105    call;                            \
106    if (HasStackOverflow()) return;  \
107  } while (false)
108
109
110void AstTyper::Run() {
111  RECURSE(VisitDeclarations(scope_->declarations()));
112  RECURSE(VisitStatements(root_->body()));
113}
114
115
116void AstTyper::VisitStatements(ZoneList<Statement*>* stmts) {
117  for (int i = 0; i < stmts->length(); ++i) {
118    Statement* stmt = stmts->at(i);
119    RECURSE(Visit(stmt));
120    if (stmt->IsJump()) break;
121  }
122}
123
124
125void AstTyper::VisitBlock(Block* stmt) {
126  RECURSE(VisitStatements(stmt->statements()));
127  if (stmt->labels() != NULL) {
128    store_.Forget();  // Control may transfer here via 'break l'.
129  }
130}
131
132
133void AstTyper::VisitExpressionStatement(ExpressionStatement* stmt) {
134  RECURSE(Visit(stmt->expression()));
135}
136
137
138void AstTyper::VisitEmptyStatement(EmptyStatement* stmt) {
139}
140
141
142void AstTyper::VisitSloppyBlockFunctionStatement(
143    SloppyBlockFunctionStatement* stmt) {
144  Visit(stmt->statement());
145}
146
147
148void AstTyper::VisitIfStatement(IfStatement* stmt) {
149  // Collect type feedback.
150  if (!stmt->condition()->ToBooleanIsTrue() &&
151      !stmt->condition()->ToBooleanIsFalse()) {
152    stmt->condition()->RecordToBooleanTypeFeedback(oracle());
153  }
154
155  RECURSE(Visit(stmt->condition()));
156  Effects then_effects = EnterEffects();
157  RECURSE(Visit(stmt->then_statement()));
158  ExitEffects();
159  Effects else_effects = EnterEffects();
160  RECURSE(Visit(stmt->else_statement()));
161  ExitEffects();
162  then_effects.Alt(else_effects);
163  store_.Seq(then_effects);
164}
165
166
167void AstTyper::VisitContinueStatement(ContinueStatement* stmt) {
168  // TODO(rossberg): is it worth having a non-termination effect?
169}
170
171
172void AstTyper::VisitBreakStatement(BreakStatement* stmt) {
173  // TODO(rossberg): is it worth having a non-termination effect?
174}
175
176
177void AstTyper::VisitReturnStatement(ReturnStatement* stmt) {
178  // Collect type feedback.
179  // TODO(rossberg): we only need this for inlining into test contexts...
180  stmt->expression()->RecordToBooleanTypeFeedback(oracle());
181
182  RECURSE(Visit(stmt->expression()));
183  // TODO(rossberg): is it worth having a non-termination effect?
184}
185
186
187void AstTyper::VisitWithStatement(WithStatement* stmt) {
188  RECURSE(stmt->expression());
189  RECURSE(stmt->statement());
190}
191
192
193void AstTyper::VisitSwitchStatement(SwitchStatement* stmt) {
194  RECURSE(Visit(stmt->tag()));
195
196  ZoneList<CaseClause*>* clauses = stmt->cases();
197  Effects local_effects(zone());
198  bool complex_effects = false;  // True for label effects or fall-through.
199
200  for (int i = 0; i < clauses->length(); ++i) {
201    CaseClause* clause = clauses->at(i);
202
203    Effects clause_effects = EnterEffects();
204
205    if (!clause->is_default()) {
206      Expression* label = clause->label();
207      // Collect type feedback.
208      AstType* tag_type;
209      AstType* label_type;
210      AstType* combined_type;
211      oracle()->CompareType(clause->CompareId(),
212                            clause->CompareOperationFeedbackSlot(), &tag_type,
213                            &label_type, &combined_type);
214      NarrowLowerType(stmt->tag(), tag_type);
215      NarrowLowerType(label, label_type);
216      clause->set_compare_type(combined_type);
217
218      RECURSE(Visit(label));
219      if (!clause_effects.IsEmpty()) complex_effects = true;
220    }
221
222    ZoneList<Statement*>* stmts = clause->statements();
223    RECURSE(VisitStatements(stmts));
224    ExitEffects();
225    if (stmts->is_empty() || stmts->last()->IsJump()) {
226      local_effects.Alt(clause_effects);
227    } else {
228      complex_effects = true;
229    }
230  }
231
232  if (complex_effects) {
233    store_.Forget();  // Reached this in unknown state.
234  } else {
235    store_.Seq(local_effects);
236  }
237}
238
239
240void AstTyper::VisitCaseClause(CaseClause* clause) {
241  UNREACHABLE();
242}
243
244
245void AstTyper::VisitDoWhileStatement(DoWhileStatement* stmt) {
246  // Collect type feedback.
247  if (!stmt->cond()->ToBooleanIsTrue()) {
248    stmt->cond()->RecordToBooleanTypeFeedback(oracle());
249  }
250
251  // TODO(rossberg): refine the unconditional Forget (here and elsewhere) by
252  // computing the set of variables assigned in only some of the origins of the
253  // control transfer (such as the loop body here).
254  store_.Forget();  // Control may transfer here via looping or 'continue'.
255  ObserveTypesAtOsrEntry(stmt);
256  RECURSE(Visit(stmt->body()));
257  RECURSE(Visit(stmt->cond()));
258  store_.Forget();  // Control may transfer here via 'break'.
259}
260
261
262void AstTyper::VisitWhileStatement(WhileStatement* stmt) {
263  // Collect type feedback.
264  if (!stmt->cond()->ToBooleanIsTrue()) {
265    stmt->cond()->RecordToBooleanTypeFeedback(oracle());
266  }
267
268  store_.Forget();  // Control may transfer here via looping or 'continue'.
269  RECURSE(Visit(stmt->cond()));
270  ObserveTypesAtOsrEntry(stmt);
271  RECURSE(Visit(stmt->body()));
272  store_.Forget();  // Control may transfer here via termination or 'break'.
273}
274
275
276void AstTyper::VisitForStatement(ForStatement* stmt) {
277  if (stmt->init() != NULL) {
278    RECURSE(Visit(stmt->init()));
279  }
280  store_.Forget();  // Control may transfer here via looping.
281  if (stmt->cond() != NULL) {
282    // Collect type feedback.
283    stmt->cond()->RecordToBooleanTypeFeedback(oracle());
284
285    RECURSE(Visit(stmt->cond()));
286  }
287  ObserveTypesAtOsrEntry(stmt);
288  RECURSE(Visit(stmt->body()));
289  if (stmt->next() != NULL) {
290    store_.Forget();  // Control may transfer here via 'continue'.
291    RECURSE(Visit(stmt->next()));
292  }
293  store_.Forget();  // Control may transfer here via termination or 'break'.
294}
295
296
297void AstTyper::VisitForInStatement(ForInStatement* stmt) {
298  // Collect type feedback.
299  stmt->set_for_in_type(static_cast<ForInStatement::ForInType>(
300      oracle()->ForInType(stmt->ForInFeedbackSlot())));
301
302  RECURSE(Visit(stmt->enumerable()));
303  store_.Forget();  // Control may transfer here via looping or 'continue'.
304  ObserveTypesAtOsrEntry(stmt);
305  RECURSE(Visit(stmt->body()));
306  store_.Forget();  // Control may transfer here via 'break'.
307}
308
309void AstTyper::VisitForOfStatement(ForOfStatement* stmt) {}
310
311void AstTyper::VisitTryCatchStatement(TryCatchStatement* stmt) {
312  Effects try_effects = EnterEffects();
313  RECURSE(Visit(stmt->try_block()));
314  ExitEffects();
315  Effects catch_effects = EnterEffects();
316  store_.Forget();  // Control may transfer here via 'throw'.
317  RECURSE(Visit(stmt->catch_block()));
318  ExitEffects();
319  try_effects.Alt(catch_effects);
320  store_.Seq(try_effects);
321  // At this point, only variables that were reassigned in the catch block are
322  // still remembered.
323}
324
325
326void AstTyper::VisitTryFinallyStatement(TryFinallyStatement* stmt) {
327  RECURSE(Visit(stmt->try_block()));
328  store_.Forget();  // Control may transfer here via 'throw'.
329  RECURSE(Visit(stmt->finally_block()));
330}
331
332
333void AstTyper::VisitDebuggerStatement(DebuggerStatement* stmt) {
334  store_.Forget();  // May do whatever.
335}
336
337
338void AstTyper::VisitFunctionLiteral(FunctionLiteral* expr) {}
339
340
341void AstTyper::VisitClassLiteral(ClassLiteral* expr) {}
342
343
344void AstTyper::VisitNativeFunctionLiteral(NativeFunctionLiteral* expr) {
345}
346
347
348void AstTyper::VisitDoExpression(DoExpression* expr) {
349  RECURSE(VisitBlock(expr->block()));
350  RECURSE(VisitVariableProxy(expr->result()));
351  NarrowType(expr, bounds_->get(expr->result()));
352}
353
354
355void AstTyper::VisitConditional(Conditional* expr) {
356  // Collect type feedback.
357  expr->condition()->RecordToBooleanTypeFeedback(oracle());
358
359  RECURSE(Visit(expr->condition()));
360  Effects then_effects = EnterEffects();
361  RECURSE(Visit(expr->then_expression()));
362  ExitEffects();
363  Effects else_effects = EnterEffects();
364  RECURSE(Visit(expr->else_expression()));
365  ExitEffects();
366  then_effects.Alt(else_effects);
367  store_.Seq(then_effects);
368
369  NarrowType(expr,
370             AstBounds::Either(bounds_->get(expr->then_expression()),
371                               bounds_->get(expr->else_expression()), zone()));
372}
373
374
375void AstTyper::VisitVariableProxy(VariableProxy* expr) {
376  Variable* var = expr->var();
377  if (var->IsStackAllocated()) {
378    NarrowType(expr, store_.LookupBounds(variable_index(var)));
379  }
380}
381
382
383void AstTyper::VisitLiteral(Literal* expr) {
384  AstType* type = AstType::Constant(expr->value(), zone());
385  NarrowType(expr, AstBounds(type));
386}
387
388
389void AstTyper::VisitRegExpLiteral(RegExpLiteral* expr) {
390  // TODO(rossberg): Reintroduce RegExp type.
391  NarrowType(expr, AstBounds(AstType::Object()));
392}
393
394
395void AstTyper::VisitObjectLiteral(ObjectLiteral* expr) {
396  ZoneList<ObjectLiteral::Property*>* properties = expr->properties();
397  for (int i = 0; i < properties->length(); ++i) {
398    ObjectLiteral::Property* prop = properties->at(i);
399
400    // Collect type feedback.
401    if ((prop->kind() == ObjectLiteral::Property::MATERIALIZED_LITERAL &&
402        !CompileTimeValue::IsCompileTimeValue(prop->value())) ||
403        prop->kind() == ObjectLiteral::Property::COMPUTED) {
404      if (!prop->is_computed_name() &&
405          prop->key()->AsLiteral()->value()->IsInternalizedString() &&
406          prop->emit_store()) {
407        // Record type feed back for the property.
408        FeedbackVectorSlot slot = prop->GetSlot();
409        SmallMapList maps;
410        oracle()->CollectReceiverTypes(slot, &maps);
411        prop->set_receiver_type(maps.length() == 1 ? maps.at(0)
412                                                   : Handle<Map>::null());
413      }
414    }
415
416    RECURSE(Visit(prop->value()));
417  }
418
419  NarrowType(expr, AstBounds(AstType::Object()));
420}
421
422
423void AstTyper::VisitArrayLiteral(ArrayLiteral* expr) {
424  ZoneList<Expression*>* values = expr->values();
425  for (int i = 0; i < values->length(); ++i) {
426    Expression* value = values->at(i);
427    RECURSE(Visit(value));
428  }
429
430  NarrowType(expr, AstBounds(AstType::Object()));
431}
432
433
434void AstTyper::VisitAssignment(Assignment* expr) {
435  // Collect type feedback.
436  Property* prop = expr->target()->AsProperty();
437  if (prop != NULL) {
438    FeedbackVectorSlot slot = expr->AssignmentSlot();
439    expr->set_is_uninitialized(oracle()->StoreIsUninitialized(slot));
440    if (!expr->IsUninitialized()) {
441      SmallMapList* receiver_types = expr->GetReceiverTypes();
442      if (prop->key()->IsPropertyName()) {
443        Literal* lit_key = prop->key()->AsLiteral();
444        DCHECK(lit_key != NULL && lit_key->value()->IsString());
445        Handle<String> name = Handle<String>::cast(lit_key->value());
446        oracle()->AssignmentReceiverTypes(slot, name, receiver_types);
447      } else {
448        KeyedAccessStoreMode store_mode;
449        IcCheckType key_type;
450        oracle()->KeyedAssignmentReceiverTypes(slot, receiver_types,
451                                               &store_mode, &key_type);
452        expr->set_store_mode(store_mode);
453        expr->set_key_type(key_type);
454      }
455    }
456  }
457
458  Expression* rhs =
459      expr->is_compound() ? expr->binary_operation() : expr->value();
460  RECURSE(Visit(expr->target()));
461  RECURSE(Visit(rhs));
462  NarrowType(expr, bounds_->get(rhs));
463
464  VariableProxy* proxy = expr->target()->AsVariableProxy();
465  if (proxy != NULL && proxy->var()->IsStackAllocated()) {
466    store_.Seq(variable_index(proxy->var()), Effect(bounds_->get(expr)));
467  }
468}
469
470
471void AstTyper::VisitYield(Yield* expr) {
472  RECURSE(Visit(expr->generator_object()));
473  RECURSE(Visit(expr->expression()));
474
475  // We don't know anything about the result type.
476}
477
478
479void AstTyper::VisitThrow(Throw* expr) {
480  RECURSE(Visit(expr->exception()));
481  // TODO(rossberg): is it worth having a non-termination effect?
482
483  NarrowType(expr, AstBounds(AstType::None()));
484}
485
486
487void AstTyper::VisitProperty(Property* expr) {
488  // Collect type feedback.
489  FeedbackVectorSlot slot = expr->PropertyFeedbackSlot();
490  expr->set_inline_cache_state(oracle()->LoadInlineCacheState(slot));
491
492  if (!expr->IsUninitialized()) {
493    if (expr->key()->IsPropertyName()) {
494      Literal* lit_key = expr->key()->AsLiteral();
495      DCHECK(lit_key != NULL && lit_key->value()->IsString());
496      Handle<String> name = Handle<String>::cast(lit_key->value());
497      oracle()->PropertyReceiverTypes(slot, name, expr->GetReceiverTypes());
498    } else {
499      bool is_string;
500      IcCheckType key_type;
501      oracle()->KeyedPropertyReceiverTypes(slot, expr->GetReceiverTypes(),
502                                           &is_string, &key_type);
503      expr->set_is_string_access(is_string);
504      expr->set_key_type(key_type);
505    }
506  }
507
508  RECURSE(Visit(expr->obj()));
509  RECURSE(Visit(expr->key()));
510
511  // We don't know anything about the result type.
512}
513
514
515void AstTyper::VisitCall(Call* expr) {
516  // Collect type feedback.
517  RECURSE(Visit(expr->expression()));
518  FeedbackVectorSlot slot = expr->CallFeedbackICSlot();
519  bool is_uninitialized = oracle()->CallIsUninitialized(slot);
520  if (!expr->expression()->IsProperty() && oracle()->CallIsMonomorphic(slot)) {
521    expr->set_target(oracle()->GetCallTarget(slot));
522    Handle<AllocationSite> site = oracle()->GetCallAllocationSite(slot);
523    expr->set_allocation_site(site);
524  }
525
526  expr->set_is_uninitialized(is_uninitialized);
527
528  ZoneList<Expression*>* args = expr->arguments();
529  for (int i = 0; i < args->length(); ++i) {
530    Expression* arg = args->at(i);
531    RECURSE(Visit(arg));
532  }
533
534  if (expr->is_possibly_eval()) {
535    store_.Forget();  // Eval could do whatever to local variables.
536  }
537
538  // We don't know anything about the result type.
539}
540
541
542void AstTyper::VisitCallNew(CallNew* expr) {
543  // Collect type feedback.
544  FeedbackVectorSlot allocation_site_feedback_slot =
545      expr->CallNewFeedbackSlot();
546  expr->set_allocation_site(
547      oracle()->GetCallNewAllocationSite(allocation_site_feedback_slot));
548  bool monomorphic =
549      oracle()->CallNewIsMonomorphic(expr->CallNewFeedbackSlot());
550  expr->set_is_monomorphic(monomorphic);
551  if (monomorphic) {
552    expr->set_target(oracle()->GetCallNewTarget(expr->CallNewFeedbackSlot()));
553  }
554
555  RECURSE(Visit(expr->expression()));
556  ZoneList<Expression*>* args = expr->arguments();
557  for (int i = 0; i < args->length(); ++i) {
558    Expression* arg = args->at(i);
559    RECURSE(Visit(arg));
560  }
561
562  NarrowType(expr, AstBounds(AstType::None(), AstType::Receiver()));
563}
564
565
566void AstTyper::VisitCallRuntime(CallRuntime* expr) {
567  ZoneList<Expression*>* args = expr->arguments();
568  for (int i = 0; i < args->length(); ++i) {
569    Expression* arg = args->at(i);
570    RECURSE(Visit(arg));
571  }
572
573  // We don't know anything about the result type.
574}
575
576
577void AstTyper::VisitUnaryOperation(UnaryOperation* expr) {
578  // Collect type feedback.
579  if (expr->op() == Token::NOT) {
580    // TODO(rossberg): only do in test or value context.
581    expr->expression()->RecordToBooleanTypeFeedback(oracle());
582  }
583
584  RECURSE(Visit(expr->expression()));
585
586  switch (expr->op()) {
587    case Token::NOT:
588    case Token::DELETE:
589      NarrowType(expr, AstBounds(AstType::Boolean()));
590      break;
591    case Token::VOID:
592      NarrowType(expr, AstBounds(AstType::Undefined()));
593      break;
594    case Token::TYPEOF:
595      NarrowType(expr, AstBounds(AstType::InternalizedString()));
596      break;
597    default:
598      UNREACHABLE();
599  }
600}
601
602
603void AstTyper::VisitCountOperation(CountOperation* expr) {
604  // Collect type feedback.
605  FeedbackVectorSlot slot = expr->CountSlot();
606  KeyedAccessStoreMode store_mode;
607  IcCheckType key_type;
608  oracle()->GetStoreModeAndKeyType(slot, &store_mode, &key_type);
609  oracle()->CountReceiverTypes(slot, expr->GetReceiverTypes());
610  expr->set_store_mode(store_mode);
611  expr->set_key_type(key_type);
612  expr->set_type(oracle()->CountType(expr->CountBinOpFeedbackId(),
613                                     expr->CountBinaryOpFeedbackSlot()));
614  // TODO(rossberg): merge the count type with the generic expression type.
615
616  RECURSE(Visit(expr->expression()));
617
618  NarrowType(expr, AstBounds(AstType::SignedSmall(), AstType::Number()));
619
620  VariableProxy* proxy = expr->expression()->AsVariableProxy();
621  if (proxy != NULL && proxy->var()->IsStackAllocated()) {
622    store_.Seq(variable_index(proxy->var()), Effect(bounds_->get(expr)));
623  }
624}
625
626void AstTyper::VisitBinaryOperation(BinaryOperation* expr) {
627  // Collect type feedback.
628  AstType* type;
629  AstType* left_type;
630  AstType* right_type;
631  Maybe<int> fixed_right_arg = Nothing<int>();
632  Handle<AllocationSite> allocation_site;
633  oracle()->BinaryType(expr->BinaryOperationFeedbackId(),
634                       expr->BinaryOperationFeedbackSlot(), &left_type,
635                       &right_type, &type, &fixed_right_arg, &allocation_site,
636                       expr->op());
637
638  NarrowLowerType(expr, type);
639  NarrowLowerType(expr->left(), left_type);
640  NarrowLowerType(expr->right(), right_type);
641  expr->set_allocation_site(allocation_site);
642  expr->set_fixed_right_arg(fixed_right_arg);
643  if (expr->op() == Token::OR || expr->op() == Token::AND) {
644    expr->left()->RecordToBooleanTypeFeedback(oracle());
645  }
646
647  switch (expr->op()) {
648    case Token::COMMA:
649      RECURSE(Visit(expr->left()));
650      RECURSE(Visit(expr->right()));
651      NarrowType(expr, bounds_->get(expr->right()));
652      break;
653    case Token::OR:
654    case Token::AND: {
655      Effects left_effects = EnterEffects();
656      RECURSE(Visit(expr->left()));
657      ExitEffects();
658      Effects right_effects = EnterEffects();
659      RECURSE(Visit(expr->right()));
660      ExitEffects();
661      left_effects.Alt(right_effects);
662      store_.Seq(left_effects);
663
664      NarrowType(expr, AstBounds::Either(bounds_->get(expr->left()),
665                                         bounds_->get(expr->right()), zone()));
666      break;
667    }
668    case Token::BIT_OR:
669    case Token::BIT_AND: {
670      RECURSE(Visit(expr->left()));
671      RECURSE(Visit(expr->right()));
672      AstType* upper =
673          AstType::Union(bounds_->get(expr->left()).upper,
674                         bounds_->get(expr->right()).upper, zone());
675      if (!upper->Is(AstType::Signed32())) upper = AstType::Signed32();
676      AstType* lower =
677          AstType::Intersect(AstType::SignedSmall(), upper, zone());
678      NarrowType(expr, AstBounds(lower, upper));
679      break;
680    }
681    case Token::BIT_XOR:
682    case Token::SHL:
683    case Token::SAR:
684      RECURSE(Visit(expr->left()));
685      RECURSE(Visit(expr->right()));
686      NarrowType(expr, AstBounds(AstType::SignedSmall(), AstType::Signed32()));
687      break;
688    case Token::SHR:
689      RECURSE(Visit(expr->left()));
690      RECURSE(Visit(expr->right()));
691      // TODO(rossberg): The upper bound would be Unsigned32, but since there
692      // is no 'positive Smi' type for the lower bound, we use the smallest
693      // union of Smi and Unsigned32 as upper bound instead.
694      NarrowType(expr, AstBounds(AstType::SignedSmall(), AstType::Number()));
695      break;
696    case Token::ADD: {
697      RECURSE(Visit(expr->left()));
698      RECURSE(Visit(expr->right()));
699      AstBounds l = bounds_->get(expr->left());
700      AstBounds r = bounds_->get(expr->right());
701      AstType* lower =
702          !l.lower->IsInhabited() || !r.lower->IsInhabited()
703              ? AstType::None()
704              : l.lower->Is(AstType::String()) || r.lower->Is(AstType::String())
705                    ? AstType::String()
706                    : l.lower->Is(AstType::Number()) &&
707                              r.lower->Is(AstType::Number())
708                          ? AstType::SignedSmall()
709                          : AstType::None();
710      AstType* upper =
711          l.upper->Is(AstType::String()) || r.upper->Is(AstType::String())
712              ? AstType::String()
713              : l.upper->Is(AstType::Number()) && r.upper->Is(AstType::Number())
714                    ? AstType::Number()
715                    : AstType::NumberOrString();
716      NarrowType(expr, AstBounds(lower, upper));
717      break;
718    }
719    case Token::SUB:
720    case Token::MUL:
721    case Token::DIV:
722    case Token::MOD:
723      RECURSE(Visit(expr->left()));
724      RECURSE(Visit(expr->right()));
725      NarrowType(expr, AstBounds(AstType::SignedSmall(), AstType::Number()));
726      break;
727    default:
728      UNREACHABLE();
729  }
730}
731
732
733void AstTyper::VisitCompareOperation(CompareOperation* expr) {
734  // Collect type feedback.
735  AstType* left_type;
736  AstType* right_type;
737  AstType* combined_type;
738  oracle()->CompareType(expr->CompareOperationFeedbackId(),
739                        expr->CompareOperationFeedbackSlot(), &left_type,
740                        &right_type, &combined_type);
741  NarrowLowerType(expr->left(), left_type);
742  NarrowLowerType(expr->right(), right_type);
743  expr->set_combined_type(combined_type);
744
745  RECURSE(Visit(expr->left()));
746  RECURSE(Visit(expr->right()));
747
748  NarrowType(expr, AstBounds(AstType::Boolean()));
749}
750
751
752void AstTyper::VisitSpread(Spread* expr) { UNREACHABLE(); }
753
754
755void AstTyper::VisitEmptyParentheses(EmptyParentheses* expr) {
756  UNREACHABLE();
757}
758
759
760void AstTyper::VisitThisFunction(ThisFunction* expr) {}
761
762
763void AstTyper::VisitSuperPropertyReference(SuperPropertyReference* expr) {}
764
765
766void AstTyper::VisitSuperCallReference(SuperCallReference* expr) {}
767
768
769void AstTyper::VisitRewritableExpression(RewritableExpression* expr) {
770  Visit(expr->expression());
771}
772
773int AstTyper::variable_index(Variable* var) {
774  // Stack locals have the range [0 .. l]
775  // Parameters have the range [-1 .. p]
776  // We map this to [-p-2 .. -1, 0 .. l]
777  return var->IsStackLocal()
778             ? stack_local_index(var->index())
779             : var->IsParameter() ? parameter_index(var->index()) : kNoVar;
780}
781
782void AstTyper::VisitDeclarations(Declaration::List* decls) {
783  for (Declaration* decl : *decls) {
784    RECURSE(Visit(decl));
785  }
786}
787
788
789void AstTyper::VisitVariableDeclaration(VariableDeclaration* declaration) {
790}
791
792
793void AstTyper::VisitFunctionDeclaration(FunctionDeclaration* declaration) {
794  RECURSE(Visit(declaration->fun()));
795}
796
797
798}  // namespace internal
799}  // namespace v8
800