• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright 2011 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
4 // met:
5 //
6 //     * Redistributions of source code must retain the above copyright
7 //       notice, this list of conditions and the following disclaimer.
8 //     * Redistributions in binary form must reproduce the above
9 //       copyright notice, this list of conditions and the following
10 //       disclaimer in the documentation and/or other materials provided
11 //       with the distribution.
12 //     * Neither the name of Google Inc. nor the names of its
13 //       contributors may be used to endorse or promote products derived
14 //       from this software without specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
28 #include "v8.h"
29 
30 #include "ast.h"
31 #include "parser.h"
32 #include "scopes.h"
33 #include "string-stream.h"
34 #include "type-info.h"
35 
36 namespace v8 {
37 namespace internal {
38 
AstSentinels()39 AstSentinels::AstSentinels()
40     : this_proxy_(true),
41       identifier_proxy_(false),
42       valid_left_hand_side_sentinel_(),
43       this_property_(&this_proxy_, NULL, 0),
44       call_sentinel_(NULL, NULL, 0) {
45 }
46 
47 
48 // ----------------------------------------------------------------------------
49 // All the Accept member functions for each syntax tree node type.
50 
Accept(AstVisitor * v)51 void Slot::Accept(AstVisitor* v) { v->VisitSlot(this); }
52 
53 #define DECL_ACCEPT(type)                                       \
54   void type::Accept(AstVisitor* v) { v->Visit##type(this); }
AST_NODE_LIST(DECL_ACCEPT)55 AST_NODE_LIST(DECL_ACCEPT)
56 #undef DECL_ACCEPT
57 
58 
59 // ----------------------------------------------------------------------------
60 // Implementation of other node functionality.
61 
62 Assignment* ExpressionStatement::StatementAsSimpleAssignment() {
63   return (expression()->AsAssignment() != NULL &&
64           !expression()->AsAssignment()->is_compound())
65       ? expression()->AsAssignment()
66       : NULL;
67 }
68 
69 
StatementAsCountOperation()70 CountOperation* ExpressionStatement::StatementAsCountOperation() {
71   return expression()->AsCountOperation();
72 }
73 
74 
VariableProxy(Variable * var)75 VariableProxy::VariableProxy(Variable* var)
76     : name_(var->name()),
77       var_(NULL),  // Will be set by the call to BindTo.
78       is_this_(var->is_this()),
79       inside_with_(false),
80       is_trivial_(false),
81       position_(RelocInfo::kNoPosition) {
82   BindTo(var);
83 }
84 
85 
VariableProxy(Handle<String> name,bool is_this,bool inside_with,int position)86 VariableProxy::VariableProxy(Handle<String> name,
87                              bool is_this,
88                              bool inside_with,
89                              int position)
90   : name_(name),
91     var_(NULL),
92     is_this_(is_this),
93     inside_with_(inside_with),
94     is_trivial_(false),
95     position_(position) {
96   // Names must be canonicalized for fast equality checks.
97   ASSERT(name->IsSymbol());
98 }
99 
100 
VariableProxy(bool is_this)101 VariableProxy::VariableProxy(bool is_this)
102   : var_(NULL),
103     is_this_(is_this),
104     inside_with_(false),
105     is_trivial_(false) {
106 }
107 
108 
BindTo(Variable * var)109 void VariableProxy::BindTo(Variable* var) {
110   ASSERT(var_ == NULL);  // must be bound only once
111   ASSERT(var != NULL);  // must bind
112   ASSERT((is_this() && var->is_this()) || name_.is_identical_to(var->name()));
113   // Ideally CONST-ness should match. However, this is very hard to achieve
114   // because we don't know the exact semantics of conflicting (const and
115   // non-const) multiple variable declarations, const vars introduced via
116   // eval() etc.  Const-ness and variable declarations are a complete mess
117   // in JS. Sigh...
118   var_ = var;
119   var->set_is_used(true);
120 }
121 
122 
Assignment(Token::Value op,Expression * target,Expression * value,int pos)123 Assignment::Assignment(Token::Value op,
124                        Expression* target,
125                        Expression* value,
126                        int pos)
127     : op_(op),
128       target_(target),
129       value_(value),
130       pos_(pos),
131       binary_operation_(NULL),
132       compound_load_id_(kNoNumber),
133       assignment_id_(GetNextId()),
134       block_start_(false),
135       block_end_(false),
136       is_monomorphic_(false),
137       receiver_types_(NULL) {
138   ASSERT(Token::IsAssignmentOp(op));
139   if (is_compound()) {
140     binary_operation_ =
141         new BinaryOperation(binary_op(), target, value, pos + 1);
142     compound_load_id_ = GetNextId();
143   }
144 }
145 
146 
binary_op() const147 Token::Value Assignment::binary_op() const {
148   switch (op_) {
149     case Token::ASSIGN_BIT_OR: return Token::BIT_OR;
150     case Token::ASSIGN_BIT_XOR: return Token::BIT_XOR;
151     case Token::ASSIGN_BIT_AND: return Token::BIT_AND;
152     case Token::ASSIGN_SHL: return Token::SHL;
153     case Token::ASSIGN_SAR: return Token::SAR;
154     case Token::ASSIGN_SHR: return Token::SHR;
155     case Token::ASSIGN_ADD: return Token::ADD;
156     case Token::ASSIGN_SUB: return Token::SUB;
157     case Token::ASSIGN_MUL: return Token::MUL;
158     case Token::ASSIGN_DIV: return Token::DIV;
159     case Token::ASSIGN_MOD: return Token::MOD;
160     default: UNREACHABLE();
161   }
162   return Token::ILLEGAL;
163 }
164 
165 
AllowsLazyCompilation()166 bool FunctionLiteral::AllowsLazyCompilation() {
167   return scope()->AllowsLazyCompilation();
168 }
169 
170 
Property(Literal * key,Expression * value)171 ObjectLiteral::Property::Property(Literal* key, Expression* value) {
172   emit_store_ = true;
173   key_ = key;
174   value_ = value;
175   Object* k = *key->handle();
176   if (k->IsSymbol() && HEAP->Proto_symbol()->Equals(String::cast(k))) {
177     kind_ = PROTOTYPE;
178   } else if (value_->AsMaterializedLiteral() != NULL) {
179     kind_ = MATERIALIZED_LITERAL;
180   } else if (value_->AsLiteral() != NULL) {
181     kind_ = CONSTANT;
182   } else {
183     kind_ = COMPUTED;
184   }
185 }
186 
187 
Property(bool is_getter,FunctionLiteral * value)188 ObjectLiteral::Property::Property(bool is_getter, FunctionLiteral* value) {
189   emit_store_ = true;
190   key_ = new Literal(value->name());
191   value_ = value;
192   kind_ = is_getter ? GETTER : SETTER;
193 }
194 
195 
IsCompileTimeValue()196 bool ObjectLiteral::Property::IsCompileTimeValue() {
197   return kind_ == CONSTANT ||
198       (kind_ == MATERIALIZED_LITERAL &&
199        CompileTimeValue::IsCompileTimeValue(value_));
200 }
201 
202 
set_emit_store(bool emit_store)203 void ObjectLiteral::Property::set_emit_store(bool emit_store) {
204   emit_store_ = emit_store;
205 }
206 
207 
emit_store()208 bool ObjectLiteral::Property::emit_store() {
209   return emit_store_;
210 }
211 
212 
IsEqualString(void * first,void * second)213 bool IsEqualString(void* first, void* second) {
214   ASSERT((*reinterpret_cast<String**>(first))->IsString());
215   ASSERT((*reinterpret_cast<String**>(second))->IsString());
216   Handle<String> h1(reinterpret_cast<String**>(first));
217   Handle<String> h2(reinterpret_cast<String**>(second));
218   return (*h1)->Equals(*h2);
219 }
220 
221 
IsEqualNumber(void * first,void * second)222 bool IsEqualNumber(void* first, void* second) {
223   ASSERT((*reinterpret_cast<Object**>(first))->IsNumber());
224   ASSERT((*reinterpret_cast<Object**>(second))->IsNumber());
225 
226   Handle<Object> h1(reinterpret_cast<Object**>(first));
227   Handle<Object> h2(reinterpret_cast<Object**>(second));
228   if (h1->IsSmi()) {
229     return h2->IsSmi() && *h1 == *h2;
230   }
231   if (h2->IsSmi()) return false;
232   Handle<HeapNumber> n1 = Handle<HeapNumber>::cast(h1);
233   Handle<HeapNumber> n2 = Handle<HeapNumber>::cast(h2);
234   ASSERT(isfinite(n1->value()));
235   ASSERT(isfinite(n2->value()));
236   return n1->value() == n2->value();
237 }
238 
239 
CalculateEmitStore()240 void ObjectLiteral::CalculateEmitStore() {
241   HashMap properties(&IsEqualString);
242   HashMap elements(&IsEqualNumber);
243   for (int i = this->properties()->length() - 1; i >= 0; i--) {
244     ObjectLiteral::Property* property = this->properties()->at(i);
245     Literal* literal = property->key();
246     Handle<Object> handle = literal->handle();
247 
248     if (handle->IsNull()) {
249       continue;
250     }
251 
252     uint32_t hash;
253     HashMap* table;
254     void* key;
255     Factory* factory = Isolate::Current()->factory();
256     if (handle->IsSymbol()) {
257       Handle<String> name(String::cast(*handle));
258       if (name->AsArrayIndex(&hash)) {
259         Handle<Object> key_handle = factory->NewNumberFromUint(hash);
260         key = key_handle.location();
261         table = &elements;
262       } else {
263         key = name.location();
264         hash = name->Hash();
265         table = &properties;
266       }
267     } else if (handle->ToArrayIndex(&hash)) {
268       key = handle.location();
269       table = &elements;
270     } else {
271       ASSERT(handle->IsNumber());
272       double num = handle->Number();
273       char arr[100];
274       Vector<char> buffer(arr, ARRAY_SIZE(arr));
275       const char* str = DoubleToCString(num, buffer);
276       Handle<String> name = factory->NewStringFromAscii(CStrVector(str));
277       key = name.location();
278       hash = name->Hash();
279       table = &properties;
280     }
281     // If the key of a computed property is in the table, do not emit
282     // a store for the property later.
283     if (property->kind() == ObjectLiteral::Property::COMPUTED) {
284       if (table->Lookup(key, hash, false) != NULL) {
285         property->set_emit_store(false);
286       }
287     }
288     // Add key to the table.
289     table->Lookup(key, hash, true);
290   }
291 }
292 
293 
AddTarget(Label * target)294 void TargetCollector::AddTarget(Label* target) {
295   // Add the label to the collector, but discard duplicates.
296   int length = targets_->length();
297   for (int i = 0; i < length; i++) {
298     if (targets_->at(i) == target) return;
299   }
300   targets_->Add(target);
301 }
302 
303 
ResultOverwriteAllowed()304 bool UnaryOperation::ResultOverwriteAllowed() {
305   switch (op_) {
306     case Token::BIT_NOT:
307     case Token::SUB:
308       return true;
309     default:
310       return false;
311   }
312 }
313 
314 
ResultOverwriteAllowed()315 bool BinaryOperation::ResultOverwriteAllowed() {
316   switch (op_) {
317     case Token::COMMA:
318     case Token::OR:
319     case Token::AND:
320       return false;
321     case Token::BIT_OR:
322     case Token::BIT_XOR:
323     case Token::BIT_AND:
324     case Token::SHL:
325     case Token::SAR:
326     case Token::SHR:
327     case Token::ADD:
328     case Token::SUB:
329     case Token::MUL:
330     case Token::DIV:
331     case Token::MOD:
332       return true;
333     default:
334       UNREACHABLE();
335   }
336   return false;
337 }
338 
339 
BinaryOperation(Assignment * assignment)340 BinaryOperation::BinaryOperation(Assignment* assignment) {
341   ASSERT(assignment->is_compound());
342   op_ = assignment->binary_op();
343   left_ = assignment->target();
344   right_ = assignment->value();
345   pos_ = assignment->position();
346 }
347 
348 
349 // ----------------------------------------------------------------------------
350 // Inlining support
351 
IsInlineable() const352 bool Declaration::IsInlineable() const {
353   UNREACHABLE();
354   return false;
355 }
356 
357 
IsInlineable() const358 bool TargetCollector::IsInlineable() const {
359   UNREACHABLE();
360   return false;
361 }
362 
363 
IsInlineable() const364 bool Slot::IsInlineable() const {
365   UNREACHABLE();
366   return false;
367 }
368 
369 
IsInlineable() const370 bool ForInStatement::IsInlineable() const {
371   return false;
372 }
373 
374 
IsInlineable() const375 bool WithEnterStatement::IsInlineable() const {
376   return false;
377 }
378 
379 
IsInlineable() const380 bool WithExitStatement::IsInlineable() const {
381   return false;
382 }
383 
384 
IsInlineable() const385 bool SwitchStatement::IsInlineable() const {
386   return false;
387 }
388 
389 
IsInlineable() const390 bool TryStatement::IsInlineable() const {
391   return false;
392 }
393 
394 
IsInlineable() const395 bool TryCatchStatement::IsInlineable() const {
396   return false;
397 }
398 
399 
IsInlineable() const400 bool TryFinallyStatement::IsInlineable() const {
401   return false;
402 }
403 
404 
IsInlineable() const405 bool CatchExtensionObject::IsInlineable() const {
406   return false;
407 }
408 
409 
IsInlineable() const410 bool DebuggerStatement::IsInlineable() const {
411   return false;
412 }
413 
414 
IsInlineable() const415 bool Throw::IsInlineable() const {
416   // TODO(1143): Make functions containing throw inlineable.
417   return false;
418 }
419 
420 
IsInlineable() const421 bool MaterializedLiteral::IsInlineable() const {
422   // TODO(1322): Allow materialized literals.
423   return false;
424 }
425 
426 
IsInlineable() const427 bool FunctionLiteral::IsInlineable() const {
428   // TODO(1322): Allow materialized literals.
429   return false;
430 }
431 
432 
IsInlineable() const433 bool ThisFunction::IsInlineable() const {
434   return false;
435 }
436 
437 
IsInlineable() const438 bool SharedFunctionInfoLiteral::IsInlineable() const {
439   return false;
440 }
441 
442 
IsInlineable() const443 bool ValidLeftHandSideSentinel::IsInlineable() const {
444   UNREACHABLE();
445   return false;
446 }
447 
448 
IsInlineable() const449 bool ForStatement::IsInlineable() const {
450   return (init() == NULL || init()->IsInlineable())
451       && (cond() == NULL || cond()->IsInlineable())
452       && (next() == NULL || next()->IsInlineable())
453       && body()->IsInlineable();
454 }
455 
456 
IsInlineable() const457 bool WhileStatement::IsInlineable() const {
458   return cond()->IsInlineable()
459       && body()->IsInlineable();
460 }
461 
462 
IsInlineable() const463 bool DoWhileStatement::IsInlineable() const {
464   return cond()->IsInlineable()
465       && body()->IsInlineable();
466 }
467 
468 
IsInlineable() const469 bool ContinueStatement::IsInlineable() const {
470   return true;
471 }
472 
473 
IsInlineable() const474 bool BreakStatement::IsInlineable() const {
475   return true;
476 }
477 
478 
IsInlineable() const479 bool EmptyStatement::IsInlineable() const {
480   return true;
481 }
482 
483 
IsInlineable() const484 bool Literal::IsInlineable() const {
485   return true;
486 }
487 
488 
IsInlineable() const489 bool Block::IsInlineable() const {
490   const int count = statements_.length();
491   for (int i = 0; i < count; ++i) {
492     if (!statements_[i]->IsInlineable()) return false;
493   }
494   return true;
495 }
496 
497 
IsInlineable() const498 bool ExpressionStatement::IsInlineable() const {
499   return expression()->IsInlineable();
500 }
501 
502 
IsInlineable() const503 bool IfStatement::IsInlineable() const {
504   return condition()->IsInlineable()
505       && then_statement()->IsInlineable()
506       && else_statement()->IsInlineable();
507 }
508 
509 
IsInlineable() const510 bool ReturnStatement::IsInlineable() const {
511   return expression()->IsInlineable();
512 }
513 
514 
IsInlineable() const515 bool Conditional::IsInlineable() const {
516   return condition()->IsInlineable() && then_expression()->IsInlineable() &&
517       else_expression()->IsInlineable();
518 }
519 
520 
IsInlineable() const521 bool VariableProxy::IsInlineable() const {
522   return var()->is_global() || var()->IsStackAllocated();
523 }
524 
525 
IsInlineable() const526 bool Assignment::IsInlineable() const {
527   return target()->IsInlineable() && value()->IsInlineable();
528 }
529 
530 
IsInlineable() const531 bool Property::IsInlineable() const {
532   return obj()->IsInlineable() && key()->IsInlineable();
533 }
534 
535 
IsInlineable() const536 bool Call::IsInlineable() const {
537   if (!expression()->IsInlineable()) return false;
538   const int count = arguments()->length();
539   for (int i = 0; i < count; ++i) {
540     if (!arguments()->at(i)->IsInlineable()) return false;
541   }
542   return true;
543 }
544 
545 
IsInlineable() const546 bool CallNew::IsInlineable() const {
547   if (!expression()->IsInlineable()) return false;
548   const int count = arguments()->length();
549   for (int i = 0; i < count; ++i) {
550     if (!arguments()->at(i)->IsInlineable()) return false;
551   }
552   return true;
553 }
554 
555 
IsInlineable() const556 bool CallRuntime::IsInlineable() const {
557   // Don't try to inline JS runtime calls because we don't (currently) even
558   // optimize them.
559   if (is_jsruntime()) return false;
560   // Don't inline the %_ArgumentsLength or %_Arguments because their
561   // implementation will not work.  There is no stack frame to get them
562   // from.
563   if (function()->intrinsic_type == Runtime::INLINE &&
564       (name()->IsEqualTo(CStrVector("_ArgumentsLength")) ||
565        name()->IsEqualTo(CStrVector("_Arguments")))) {
566     return false;
567   }
568   const int count = arguments()->length();
569   for (int i = 0; i < count; ++i) {
570     if (!arguments()->at(i)->IsInlineable()) return false;
571   }
572   return true;
573 }
574 
575 
IsInlineable() const576 bool UnaryOperation::IsInlineable() const {
577   return expression()->IsInlineable();
578 }
579 
580 
IsInlineable() const581 bool BinaryOperation::IsInlineable() const {
582   return left()->IsInlineable() && right()->IsInlineable();
583 }
584 
585 
IsInlineable() const586 bool CompareOperation::IsInlineable() const {
587   return left()->IsInlineable() && right()->IsInlineable();
588 }
589 
590 
IsInlineable() const591 bool CompareToNull::IsInlineable() const {
592   return expression()->IsInlineable();
593 }
594 
595 
IsInlineable() const596 bool CountOperation::IsInlineable() const {
597   return expression()->IsInlineable();
598 }
599 
600 
601 // ----------------------------------------------------------------------------
602 // Recording of type feedback
603 
RecordTypeFeedback(TypeFeedbackOracle * oracle)604 void Property::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
605   // Record type feedback from the oracle in the AST.
606   is_monomorphic_ = oracle->LoadIsMonomorphic(this);
607   if (key()->IsPropertyName()) {
608     if (oracle->LoadIsBuiltin(this, Builtins::kLoadIC_ArrayLength)) {
609       is_array_length_ = true;
610     } else if (oracle->LoadIsBuiltin(this, Builtins::kLoadIC_StringLength)) {
611       is_string_length_ = true;
612     } else if (oracle->LoadIsBuiltin(this,
613                                      Builtins::kLoadIC_FunctionPrototype)) {
614       is_function_prototype_ = true;
615     } else {
616       Literal* lit_key = key()->AsLiteral();
617       ASSERT(lit_key != NULL && lit_key->handle()->IsString());
618       Handle<String> name = Handle<String>::cast(lit_key->handle());
619       ZoneMapList* types = oracle->LoadReceiverTypes(this, name);
620       receiver_types_ = types;
621     }
622   } else if (oracle->LoadIsBuiltin(this, Builtins::kKeyedLoadIC_String)) {
623     is_string_access_ = true;
624   } else if (is_monomorphic_) {
625     monomorphic_receiver_type_ = oracle->LoadMonomorphicReceiverType(this);
626     if (monomorphic_receiver_type_->has_external_array_elements()) {
627       set_external_array_type(oracle->GetKeyedLoadExternalArrayType(this));
628     }
629   }
630 }
631 
632 
RecordTypeFeedback(TypeFeedbackOracle * oracle)633 void Assignment::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
634   Property* prop = target()->AsProperty();
635   ASSERT(prop != NULL);
636   is_monomorphic_ = oracle->StoreIsMonomorphic(this);
637   if (prop->key()->IsPropertyName()) {
638     Literal* lit_key = prop->key()->AsLiteral();
639     ASSERT(lit_key != NULL && lit_key->handle()->IsString());
640     Handle<String> name = Handle<String>::cast(lit_key->handle());
641     ZoneMapList* types = oracle->StoreReceiverTypes(this, name);
642     receiver_types_ = types;
643   } else if (is_monomorphic_) {
644     // Record receiver type for monomorphic keyed loads.
645     monomorphic_receiver_type_ = oracle->StoreMonomorphicReceiverType(this);
646     if (monomorphic_receiver_type_->has_external_array_elements()) {
647       set_external_array_type(oracle->GetKeyedStoreExternalArrayType(this));
648     }
649   }
650 }
651 
652 
RecordTypeFeedback(TypeFeedbackOracle * oracle)653 void CountOperation::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
654   is_monomorphic_ = oracle->StoreIsMonomorphic(this);
655   if (is_monomorphic_) {
656     // Record receiver type for monomorphic keyed loads.
657     monomorphic_receiver_type_ = oracle->StoreMonomorphicReceiverType(this);
658     if (monomorphic_receiver_type_->has_external_array_elements()) {
659       set_external_array_type(oracle->GetKeyedStoreExternalArrayType(this));
660     }
661   }
662 }
663 
664 
RecordTypeFeedback(TypeFeedbackOracle * oracle)665 void CaseClause::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
666   TypeInfo info = oracle->SwitchType(this);
667   if (info.IsSmi()) {
668     compare_type_ = SMI_ONLY;
669   } else if (info.IsNonPrimitive()) {
670     compare_type_ = OBJECT_ONLY;
671   } else {
672     ASSERT(compare_type_ == NONE);
673   }
674 }
675 
676 
CanCallWithoutIC(Handle<JSFunction> target,int arity)677 static bool CanCallWithoutIC(Handle<JSFunction> target, int arity) {
678   SharedFunctionInfo* info = target->shared();
679   // If the number of formal parameters of the target function does
680   // not match the number of arguments we're passing, we don't want to
681   // deal with it. Otherwise, we can call it directly.
682   return !target->NeedsArgumentsAdaption() ||
683       info->formal_parameter_count() == arity;
684 }
685 
686 
ComputeTarget(Handle<Map> type,Handle<String> name)687 bool Call::ComputeTarget(Handle<Map> type, Handle<String> name) {
688   if (check_type_ == RECEIVER_MAP_CHECK) {
689     // For primitive checks the holder is set up to point to the
690     // corresponding prototype object, i.e. one step of the algorithm
691     // below has been already performed.
692     // For non-primitive checks we clear it to allow computing targets
693     // for polymorphic calls.
694     holder_ = Handle<JSObject>::null();
695   }
696   while (true) {
697     LookupResult lookup;
698     type->LookupInDescriptors(NULL, *name, &lookup);
699     // If the function wasn't found directly in the map, we start
700     // looking upwards through the prototype chain.
701     if (!lookup.IsFound() && type->prototype()->IsJSObject()) {
702       holder_ = Handle<JSObject>(JSObject::cast(type->prototype()));
703       type = Handle<Map>(holder()->map());
704     } else if (lookup.IsProperty() && lookup.type() == CONSTANT_FUNCTION) {
705       target_ = Handle<JSFunction>(lookup.GetConstantFunctionFromMap(*type));
706       return CanCallWithoutIC(target_, arguments()->length());
707     } else {
708       return false;
709     }
710   }
711 }
712 
713 
ComputeGlobalTarget(Handle<GlobalObject> global,LookupResult * lookup)714 bool Call::ComputeGlobalTarget(Handle<GlobalObject> global,
715                                LookupResult* lookup) {
716   target_ = Handle<JSFunction>::null();
717   cell_ = Handle<JSGlobalPropertyCell>::null();
718   ASSERT(lookup->IsProperty() &&
719          lookup->type() == NORMAL &&
720          lookup->holder() == *global);
721   cell_ = Handle<JSGlobalPropertyCell>(global->GetPropertyCell(lookup));
722   if (cell_->value()->IsJSFunction()) {
723     Handle<JSFunction> candidate(JSFunction::cast(cell_->value()));
724     // If the function is in new space we assume it's more likely to
725     // change and thus prefer the general IC code.
726     if (!HEAP->InNewSpace(*candidate) &&
727         CanCallWithoutIC(candidate, arguments()->length())) {
728       target_ = candidate;
729       return true;
730     }
731   }
732   return false;
733 }
734 
735 
RecordTypeFeedback(TypeFeedbackOracle * oracle)736 void Call::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
737   Property* property = expression()->AsProperty();
738   ASSERT(property != NULL);
739   // Specialize for the receiver types seen at runtime.
740   Literal* key = property->key()->AsLiteral();
741   ASSERT(key != NULL && key->handle()->IsString());
742   Handle<String> name = Handle<String>::cast(key->handle());
743   receiver_types_ = oracle->CallReceiverTypes(this, name);
744 #ifdef DEBUG
745   if (FLAG_enable_slow_asserts) {
746     if (receiver_types_ != NULL) {
747       int length = receiver_types_->length();
748       for (int i = 0; i < length; i++) {
749         Handle<Map> map = receiver_types_->at(i);
750         ASSERT(!map.is_null() && *map != NULL);
751       }
752     }
753   }
754 #endif
755   is_monomorphic_ = oracle->CallIsMonomorphic(this);
756   check_type_ = oracle->GetCallCheckType(this);
757   if (is_monomorphic_) {
758     Handle<Map> map;
759     if (receiver_types_ != NULL && receiver_types_->length() > 0) {
760       ASSERT(check_type_ == RECEIVER_MAP_CHECK);
761       map = receiver_types_->at(0);
762     } else {
763       ASSERT(check_type_ != RECEIVER_MAP_CHECK);
764       holder_ = Handle<JSObject>(
765           oracle->GetPrototypeForPrimitiveCheck(check_type_));
766       map = Handle<Map>(holder_->map());
767     }
768     is_monomorphic_ = ComputeTarget(map, name);
769   }
770 }
771 
772 
RecordTypeFeedback(TypeFeedbackOracle * oracle)773 void CompareOperation::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
774   TypeInfo info = oracle->CompareType(this);
775   if (info.IsSmi()) {
776     compare_type_ = SMI_ONLY;
777   } else if (info.IsNonPrimitive()) {
778     compare_type_ = OBJECT_ONLY;
779   } else {
780     ASSERT(compare_type_ == NONE);
781   }
782 }
783 
784 
785 // ----------------------------------------------------------------------------
786 // Implementation of AstVisitor
787 
CheckStackOverflow()788 bool AstVisitor::CheckStackOverflow() {
789   if (stack_overflow_) return true;
790   StackLimitCheck check(isolate_);
791   if (!check.HasOverflowed()) return false;
792   return (stack_overflow_ = true);
793 }
794 
795 
VisitDeclarations(ZoneList<Declaration * > * declarations)796 void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) {
797   for (int i = 0; i < declarations->length(); i++) {
798     Visit(declarations->at(i));
799   }
800 }
801 
802 
VisitStatements(ZoneList<Statement * > * statements)803 void AstVisitor::VisitStatements(ZoneList<Statement*>* statements) {
804   for (int i = 0; i < statements->length(); i++) {
805     Visit(statements->at(i));
806   }
807 }
808 
809 
VisitExpressions(ZoneList<Expression * > * expressions)810 void AstVisitor::VisitExpressions(ZoneList<Expression*>* expressions) {
811   for (int i = 0; i < expressions->length(); i++) {
812     // The variable statement visiting code may pass NULL expressions
813     // to this code. Maybe this should be handled by introducing an
814     // undefined expression or literal?  Revisit this code if this
815     // changes
816     Expression* expression = expressions->at(i);
817     if (expression != NULL) Visit(expression);
818   }
819 }
820 
821 
822 // ----------------------------------------------------------------------------
823 // Regular expressions
824 
825 #define MAKE_ACCEPT(Name)                                            \
826   void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) {   \
827     return visitor->Visit##Name(this, data);                         \
828   }
829 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT)
830 #undef MAKE_ACCEPT
831 
832 #define MAKE_TYPE_CASE(Name)                                         \
833   RegExp##Name* RegExpTree::As##Name() {                             \
834     return NULL;                                                     \
835   }                                                                  \
836   bool RegExpTree::Is##Name() { return false; }
837 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
838 #undef MAKE_TYPE_CASE
839 
840 #define MAKE_TYPE_CASE(Name)                                        \
841   RegExp##Name* RegExp##Name::As##Name() {                          \
842     return this;                                                    \
843   }                                                                 \
844   bool RegExp##Name::Is##Name() { return true; }
845 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
846 #undef MAKE_TYPE_CASE
847 
848 RegExpEmpty RegExpEmpty::kInstance;
849 
850 
ListCaptureRegisters(ZoneList<RegExpTree * > * children)851 static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) {
852   Interval result = Interval::Empty();
853   for (int i = 0; i < children->length(); i++)
854     result = result.Union(children->at(i)->CaptureRegisters());
855   return result;
856 }
857 
858 
CaptureRegisters()859 Interval RegExpAlternative::CaptureRegisters() {
860   return ListCaptureRegisters(nodes());
861 }
862 
863 
CaptureRegisters()864 Interval RegExpDisjunction::CaptureRegisters() {
865   return ListCaptureRegisters(alternatives());
866 }
867 
868 
CaptureRegisters()869 Interval RegExpLookahead::CaptureRegisters() {
870   return body()->CaptureRegisters();
871 }
872 
873 
CaptureRegisters()874 Interval RegExpCapture::CaptureRegisters() {
875   Interval self(StartRegister(index()), EndRegister(index()));
876   return self.Union(body()->CaptureRegisters());
877 }
878 
879 
CaptureRegisters()880 Interval RegExpQuantifier::CaptureRegisters() {
881   return body()->CaptureRegisters();
882 }
883 
884 
IsAnchoredAtStart()885 bool RegExpAssertion::IsAnchoredAtStart() {
886   return type() == RegExpAssertion::START_OF_INPUT;
887 }
888 
889 
IsAnchoredAtEnd()890 bool RegExpAssertion::IsAnchoredAtEnd() {
891   return type() == RegExpAssertion::END_OF_INPUT;
892 }
893 
894 
IsAnchoredAtStart()895 bool RegExpAlternative::IsAnchoredAtStart() {
896   ZoneList<RegExpTree*>* nodes = this->nodes();
897   for (int i = 0; i < nodes->length(); i++) {
898     RegExpTree* node = nodes->at(i);
899     if (node->IsAnchoredAtStart()) { return true; }
900     if (node->max_match() > 0) { return false; }
901   }
902   return false;
903 }
904 
905 
IsAnchoredAtEnd()906 bool RegExpAlternative::IsAnchoredAtEnd() {
907   ZoneList<RegExpTree*>* nodes = this->nodes();
908   for (int i = nodes->length() - 1; i >= 0; i--) {
909     RegExpTree* node = nodes->at(i);
910     if (node->IsAnchoredAtEnd()) { return true; }
911     if (node->max_match() > 0) { return false; }
912   }
913   return false;
914 }
915 
916 
IsAnchoredAtStart()917 bool RegExpDisjunction::IsAnchoredAtStart() {
918   ZoneList<RegExpTree*>* alternatives = this->alternatives();
919   for (int i = 0; i < alternatives->length(); i++) {
920     if (!alternatives->at(i)->IsAnchoredAtStart())
921       return false;
922   }
923   return true;
924 }
925 
926 
IsAnchoredAtEnd()927 bool RegExpDisjunction::IsAnchoredAtEnd() {
928   ZoneList<RegExpTree*>* alternatives = this->alternatives();
929   for (int i = 0; i < alternatives->length(); i++) {
930     if (!alternatives->at(i)->IsAnchoredAtEnd())
931       return false;
932   }
933   return true;
934 }
935 
936 
IsAnchoredAtStart()937 bool RegExpLookahead::IsAnchoredAtStart() {
938   return is_positive() && body()->IsAnchoredAtStart();
939 }
940 
941 
IsAnchoredAtStart()942 bool RegExpCapture::IsAnchoredAtStart() {
943   return body()->IsAnchoredAtStart();
944 }
945 
946 
IsAnchoredAtEnd()947 bool RegExpCapture::IsAnchoredAtEnd() {
948   return body()->IsAnchoredAtEnd();
949 }
950 
951 
952 // Convert regular expression trees to a simple sexp representation.
953 // This representation should be different from the input grammar
954 // in as many cases as possible, to make it more difficult for incorrect
955 // parses to look as correct ones which is likely if the input and
956 // output formats are alike.
957 class RegExpUnparser: public RegExpVisitor {
958  public:
959   RegExpUnparser();
960   void VisitCharacterRange(CharacterRange that);
ToString()961   SmartPointer<const char> ToString() { return stream_.ToCString(); }
962 #define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*, void* data);
963   FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
964 #undef MAKE_CASE
965  private:
stream()966   StringStream* stream() { return &stream_; }
967   HeapStringAllocator alloc_;
968   StringStream stream_;
969 };
970 
971 
RegExpUnparser()972 RegExpUnparser::RegExpUnparser() : stream_(&alloc_) {
973 }
974 
975 
VisitDisjunction(RegExpDisjunction * that,void * data)976 void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) {
977   stream()->Add("(|");
978   for (int i = 0; i <  that->alternatives()->length(); i++) {
979     stream()->Add(" ");
980     that->alternatives()->at(i)->Accept(this, data);
981   }
982   stream()->Add(")");
983   return NULL;
984 }
985 
986 
VisitAlternative(RegExpAlternative * that,void * data)987 void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) {
988   stream()->Add("(:");
989   for (int i = 0; i <  that->nodes()->length(); i++) {
990     stream()->Add(" ");
991     that->nodes()->at(i)->Accept(this, data);
992   }
993   stream()->Add(")");
994   return NULL;
995 }
996 
997 
VisitCharacterRange(CharacterRange that)998 void RegExpUnparser::VisitCharacterRange(CharacterRange that) {
999   stream()->Add("%k", that.from());
1000   if (!that.IsSingleton()) {
1001     stream()->Add("-%k", that.to());
1002   }
1003 }
1004 
1005 
1006 
VisitCharacterClass(RegExpCharacterClass * that,void * data)1007 void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that,
1008                                           void* data) {
1009   if (that->is_negated())
1010     stream()->Add("^");
1011   stream()->Add("[");
1012   for (int i = 0; i < that->ranges()->length(); i++) {
1013     if (i > 0) stream()->Add(" ");
1014     VisitCharacterRange(that->ranges()->at(i));
1015   }
1016   stream()->Add("]");
1017   return NULL;
1018 }
1019 
1020 
VisitAssertion(RegExpAssertion * that,void * data)1021 void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) {
1022   switch (that->type()) {
1023     case RegExpAssertion::START_OF_INPUT:
1024       stream()->Add("@^i");
1025       break;
1026     case RegExpAssertion::END_OF_INPUT:
1027       stream()->Add("@$i");
1028       break;
1029     case RegExpAssertion::START_OF_LINE:
1030       stream()->Add("@^l");
1031       break;
1032     case RegExpAssertion::END_OF_LINE:
1033       stream()->Add("@$l");
1034        break;
1035     case RegExpAssertion::BOUNDARY:
1036       stream()->Add("@b");
1037       break;
1038     case RegExpAssertion::NON_BOUNDARY:
1039       stream()->Add("@B");
1040       break;
1041   }
1042   return NULL;
1043 }
1044 
1045 
VisitAtom(RegExpAtom * that,void * data)1046 void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) {
1047   stream()->Add("'");
1048   Vector<const uc16> chardata = that->data();
1049   for (int i = 0; i < chardata.length(); i++) {
1050     stream()->Add("%k", chardata[i]);
1051   }
1052   stream()->Add("'");
1053   return NULL;
1054 }
1055 
1056 
VisitText(RegExpText * that,void * data)1057 void* RegExpUnparser::VisitText(RegExpText* that, void* data) {
1058   if (that->elements()->length() == 1) {
1059     that->elements()->at(0).data.u_atom->Accept(this, data);
1060   } else {
1061     stream()->Add("(!");
1062     for (int i = 0; i < that->elements()->length(); i++) {
1063       stream()->Add(" ");
1064       that->elements()->at(i).data.u_atom->Accept(this, data);
1065     }
1066     stream()->Add(")");
1067   }
1068   return NULL;
1069 }
1070 
1071 
VisitQuantifier(RegExpQuantifier * that,void * data)1072 void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) {
1073   stream()->Add("(# %i ", that->min());
1074   if (that->max() == RegExpTree::kInfinity) {
1075     stream()->Add("- ");
1076   } else {
1077     stream()->Add("%i ", that->max());
1078   }
1079   stream()->Add(that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n ");
1080   that->body()->Accept(this, data);
1081   stream()->Add(")");
1082   return NULL;
1083 }
1084 
1085 
VisitCapture(RegExpCapture * that,void * data)1086 void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) {
1087   stream()->Add("(^ ");
1088   that->body()->Accept(this, data);
1089   stream()->Add(")");
1090   return NULL;
1091 }
1092 
1093 
VisitLookahead(RegExpLookahead * that,void * data)1094 void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) {
1095   stream()->Add("(-> ");
1096   stream()->Add(that->is_positive() ? "+ " : "- ");
1097   that->body()->Accept(this, data);
1098   stream()->Add(")");
1099   return NULL;
1100 }
1101 
1102 
VisitBackReference(RegExpBackReference * that,void * data)1103 void* RegExpUnparser::VisitBackReference(RegExpBackReference* that,
1104                                          void* data) {
1105   stream()->Add("(<- %i)", that->index());
1106   return NULL;
1107 }
1108 
1109 
VisitEmpty(RegExpEmpty * that,void * data)1110 void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) {
1111   stream()->Put('%');
1112   return NULL;
1113 }
1114 
1115 
ToString()1116 SmartPointer<const char> RegExpTree::ToString() {
1117   RegExpUnparser unparser;
1118   Accept(&unparser, NULL);
1119   return unparser.ToString();
1120 }
1121 
1122 
RegExpDisjunction(ZoneList<RegExpTree * > * alternatives)1123 RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives)
1124     : alternatives_(alternatives) {
1125   ASSERT(alternatives->length() > 1);
1126   RegExpTree* first_alternative = alternatives->at(0);
1127   min_match_ = first_alternative->min_match();
1128   max_match_ = first_alternative->max_match();
1129   for (int i = 1; i < alternatives->length(); i++) {
1130     RegExpTree* alternative = alternatives->at(i);
1131     min_match_ = Min(min_match_, alternative->min_match());
1132     max_match_ = Max(max_match_, alternative->max_match());
1133   }
1134 }
1135 
1136 
RegExpAlternative(ZoneList<RegExpTree * > * nodes)1137 RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes)
1138     : nodes_(nodes) {
1139   ASSERT(nodes->length() > 1);
1140   min_match_ = 0;
1141   max_match_ = 0;
1142   for (int i = 0; i < nodes->length(); i++) {
1143     RegExpTree* node = nodes->at(i);
1144     min_match_ += node->min_match();
1145     int node_max_match = node->max_match();
1146     if (kInfinity - max_match_ < node_max_match) {
1147       max_match_ = kInfinity;
1148     } else {
1149       max_match_ += node->max_match();
1150     }
1151   }
1152 }
1153 
1154 
CaseClause(Expression * label,ZoneList<Statement * > * statements,int pos)1155 CaseClause::CaseClause(Expression* label,
1156                        ZoneList<Statement*>* statements,
1157                        int pos)
1158     : label_(label),
1159       statements_(statements),
1160       position_(pos),
1161       compare_type_(NONE),
1162       entry_id_(AstNode::GetNextId()) {
1163 }
1164 
1165 } }  // namespace v8::internal
1166