From 665c45c92da23cad4de7b46bb7c3729063f9c45b Mon Sep 17 00:00:00 2001 From: "jkummerow@chromium.org" Date: Tue, 6 Aug 2013 12:57:23 +0000 Subject: [PATCH] Un-revert "Implement simple effect typing for variables" and "Handle switch effects" This re-lands r15776 and r15777, reverting the revert in r15786. R=rossberg@chromium.org Review URL: https://codereview.chromium.org/22144006 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@16071 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/ast.h | 29 ++- src/effects.h | 361 +++++++++++++++++++++++++++++ src/splay-tree-inl.h | 9 +- src/splay-tree.h | 14 +- src/types.h | 5 + src/typing.cc | 236 ++++++++++++++----- src/typing.h | 17 ++ src/zone-inl.h | 6 + src/zone.h | 3 + test/cctest/test-global-handles.cc | 2 +- tools/gyp/v8.gyp | 1 + 11 files changed, 616 insertions(+), 67 deletions(-) create mode 100644 src/effects.h diff --git a/src/ast.h b/src/ast.h index f6066e712..db8cb2e36 100644 --- a/src/ast.h +++ b/src/ast.h @@ -259,6 +259,7 @@ class Statement: public AstNode { Statement() : statement_pos_(RelocInfo::kNoPosition) {} bool IsEmpty() { return AsEmptyStatement() != NULL; } + virtual bool IsJump() const { return false; } void set_statement_pos(int statement_pos) { statement_pos_ = statement_pos; } int statement_pos() const { return statement_pos_; } @@ -388,7 +389,7 @@ class Expression: public AstNode { protected: explicit Expression(Isolate* isolate) - : bounds_(Type::None(), Type::Any(), isolate), + : bounds_(Bounds::Unbounded(isolate)), id_(GetNextId(isolate)), test_id_(GetNextId(isolate)) {} void set_to_boolean_types(byte types) { to_boolean_types_ = types; } @@ -458,6 +459,11 @@ class Block: public BreakableStatement { ZoneList* statements() { return &statements_; } bool is_initializer_block() const { return is_initializer_block_; } + virtual bool IsJump() const { + return !statements_.is_empty() && statements_.last()->IsJump() + && labels() == NULL; // Good enough as an approximation... + } + Scope* scope() const { return scope_; } void set_scope(Scope* scope) { scope_ = scope; } @@ -1008,6 +1014,7 @@ class ExpressionStatement: public Statement { void set_expression(Expression* e) { expression_ = e; } Expression* expression() const { return expression_; } + virtual bool IsJump() const { return expression_->IsThrow(); } protected: explicit ExpressionStatement(Expression* expression) @@ -1018,7 +1025,16 @@ class ExpressionStatement: public Statement { }; -class ContinueStatement: public Statement { +class JumpStatement: public Statement { + public: + virtual bool IsJump() const { return true; } + + protected: + JumpStatement() {} +}; + + +class ContinueStatement: public JumpStatement { public: DECLARE_NODE_TYPE(ContinueStatement) @@ -1033,7 +1049,7 @@ class ContinueStatement: public Statement { }; -class BreakStatement: public Statement { +class BreakStatement: public JumpStatement { public: DECLARE_NODE_TYPE(BreakStatement) @@ -1048,7 +1064,7 @@ class BreakStatement: public Statement { }; -class ReturnStatement: public Statement { +class ReturnStatement: public JumpStatement { public: DECLARE_NODE_TYPE(ReturnStatement) @@ -1167,6 +1183,11 @@ class IfStatement: public Statement { Statement* then_statement() const { return then_statement_; } Statement* else_statement() const { return else_statement_; } + virtual bool IsJump() const { + return HasThenStatement() && then_statement()->IsJump() + && HasElseStatement() && else_statement()->IsJump(); + } + BailoutId IfId() const { return if_id_; } BailoutId ThenId() const { return then_id_; } BailoutId ElseId() const { return else_id_; } diff --git a/src/effects.h b/src/effects.h new file mode 100644 index 000000000..8e8236347 --- /dev/null +++ b/src/effects.h @@ -0,0 +1,361 @@ +// Copyright 2013 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#ifndef V8_EFFECTS_H_ +#define V8_EFFECTS_H_ + +#include "v8.h" + +#include "types.h" + +namespace v8 { +namespace internal { + + +// A simple struct to represent (write) effects. A write is represented as a +// modification of type bounds (e.g. of a variable). +// +// An effect can either be definite, if the write is known to have taken place, +// or 'possible', if it was optional. The difference is relevant when composing +// effects. +// +// There are two ways to compose effects: sequentially (they happen one after +// the other) or alternatively (either one or the other happens). A definite +// effect cancels out any previous effect upon sequencing. A possible effect +// merges into a previous effect, i.e., type bounds are merged. Alternative +// composition always merges bounds. It yields a possible effect if at least +// one was only possible. +struct Effect { + enum Modality { POSSIBLE, DEFINITE }; + + Modality modality; + Bounds bounds; + + Effect() {} + Effect(Bounds b, Modality m = DEFINITE) : modality(m), bounds(b) {} + + // The unknown effect. + static Effect Unknown(Isolate* isolate) { + return Effect(Bounds::Unbounded(isolate), POSSIBLE); + } + + static Effect Forget(Isolate* isolate) { + return Effect(Bounds::Unbounded(isolate), DEFINITE); + } + + // Sequential composition, as in 'e1; e2'. + static Effect Seq(Effect e1, Effect e2, Isolate* isolate) { + if (e2.modality == DEFINITE) return e2; + return Effect(Bounds::Either(e1.bounds, e2.bounds, isolate), e1.modality); + } + + // Alternative composition, as in 'cond ? e1 : e2'. + static Effect Alt(Effect e1, Effect e2, Isolate* isolate) { + return Effect( + Bounds::Either(e1.bounds, e2.bounds, isolate), + e1.modality == POSSIBLE ? POSSIBLE : e2.modality); + } +}; + + +// Classes encapsulating sets of effects on variables. +// +// Effects maps variables to effects and supports sequential and alternative +// composition. +// +// NestedEffects is an incremental representation that supports persistence +// through functional extension. It represents the map as an adjoin of a list +// of maps, whose tail can be shared. +// +// Both classes provide similar interfaces, implemented in parts through the +// EffectsMixin below (using sandwich style, to work around the style guide's +// MI restriction). +// +// We also (ab)use Effects/NestedEffects as a representation for abstract +// store typings. In that case, only definite effects are of interest. + +template +class EffectsMixin: public Base { + public: + explicit EffectsMixin(Zone* zone) : Base(zone) {} + + Effect Lookup(Var var) { + Locator locator; + return this->Find(var, &locator) + ? locator.value() : Effect::Unknown(Base::isolate()); + } + + Bounds LookupBounds(Var var) { + Effect effect = Lookup(var); + return effect.modality == Effect::DEFINITE + ? effect.bounds : Bounds::Unbounded(Base::isolate()); + } + + // Sequential composition. + void Seq(Var var, Effect effect) { + Locator locator; + if (!this->Insert(var, &locator)) { + effect = Effect::Seq(locator.value(), effect, Base::isolate()); + } + locator.set_value(effect); + } + + void Seq(Effects that) { + SeqMerger merge = { *this }; + that.ForEach(&merge); + } + + // Alternative composition. + void Alt(Var var, Effect effect) { + Locator locator; + if (!this->Insert(var, &locator)) { + effect = Effect::Alt(locator.value(), effect, Base::isolate()); + } + locator.set_value(effect); + } + + void Alt(Effects that) { + AltWeakener weaken = { *this, that }; + this->ForEach(&weaken); + AltMerger merge = { *this }; + that.ForEach(&merge); + } + + // Invalidation. + void Forget() { + Overrider override = { + Effect::Forget(Base::isolate()), Effects(Base::zone()) }; + this->ForEach(&override); + Seq(override.effects); + } + + protected: + typedef typename Base::Locator Locator; + + template + struct SeqMerger { + void Call(Var var, Effect effect) { self.Seq(var, effect); } + Self self; + }; + + template + struct AltMerger { + void Call(Var var, Effect effect) { self.Alt(var, effect); } + Self self; + }; + + template + struct AltWeakener { + void Call(Var var, Effect effect) { + if (effect.modality == Effect::DEFINITE && !other.Contains(var)) { + effect.modality = Effect::POSSIBLE; + Locator locator; + self.Insert(var, &locator); + locator.set_value(effect); + } + } + Self self; + Effects other; + }; + + struct Overrider { + void Call(Var var, Effect effect) { effects.Seq(var, new_effect); } + Effect new_effect; + Effects effects; + }; +}; + + +template class Effects; +template class NestedEffectsBase; + +template +class EffectsBase { + public: + explicit EffectsBase(Zone* zone) : map_(new(zone) Mapping(zone)) {} + + bool IsEmpty() { return map_->is_empty(); } + + protected: + friend class NestedEffectsBase; + friend class + EffectsMixin, Effects >; + + Zone* zone() { return map_->allocator().zone(); } + Isolate* isolate() { return zone()->isolate(); } + + struct SplayTreeConfig { + typedef Var Key; + typedef Effect Value; + static const Var kNoKey = kNoVar; + static Effect NoValue() { return Effect(); } + static int Compare(int x, int y) { return y - x; } + }; + typedef ZoneSplayTree Mapping; + typedef typename Mapping::Locator Locator; + + bool Contains(Var var) { + ASSERT(var != kNoVar); + return map_->Contains(var); + } + bool Find(Var var, Locator* locator) { + ASSERT(var != kNoVar); + return map_->Find(var, locator); + } + bool Insert(Var var, Locator* locator) { + ASSERT(var != kNoVar); + return map_->Insert(var, locator); + } + + template + void ForEach(Callback* callback) { + return map_->ForEach(callback); + } + + private: + Mapping* map_; +}; + +template +const Var EffectsBase::SplayTreeConfig::kNoKey; + +template +class Effects: public + EffectsMixin, Effects > { + public: + explicit Effects(Zone* zone) + : EffectsMixin, Effects >(zone) + {} +}; + + +template +class NestedEffectsBase { + public: + explicit NestedEffectsBase(Zone* zone) : node_(new(zone) Node(zone)) {} + + template + void ForEach(Callback* callback) { + if (node_->previous) NestedEffectsBase(node_->previous).ForEach(callback); + node_->effects.ForEach(callback); + } + + Effects Top() { return node_->effects; } + + bool IsEmpty() { + for (Node* node = node_; node != NULL; node = node->previous) { + if (!node->effects.IsEmpty()) return false; + } + return true; + } + + protected: + typedef typename EffectsBase::Locator Locator; + + Zone* zone() { return node_->zone; } + Isolate* isolate() { return zone()->isolate(); } + + void push() { node_ = new(node_->zone) Node(node_->zone, node_); } + void pop() { node_ = node_->previous; } + bool is_empty() { return node_ == NULL; } + + bool Contains(Var var) { + ASSERT(var != kNoVar); + for (Node* node = node_; node != NULL; node = node->previous) { + if (node->effects.Contains(var)) return true; + } + return false; + } + + bool Find(Var var, Locator* locator) { + ASSERT(var != kNoVar); + for (Node* node = node_; node != NULL; node = node->previous) { + if (node->effects.Find(var, locator)) return true; + } + return false; + } + + bool Insert(Var var, Locator* locator); + + private: + struct Node: ZoneObject { + Zone* zone; + Effects effects; + Node* previous; + explicit Node(Zone* zone, Node* previous = NULL) + : zone(zone), effects(zone), previous(previous) {} + }; + + explicit NestedEffectsBase(Node* node) : node_(node) {} + + Node* node_; +}; + + +template +bool NestedEffectsBase::Insert(Var var, Locator* locator) { + ASSERT(var != kNoVar); + if (!node_->effects.Insert(var, locator)) return false; + Locator shadowed; + for (Node* node = node_->previous; node != NULL; node = node->previous) { + if (node->effects.Find(var, &shadowed)) { + // Initialize with shadowed entry. + locator->set_value(shadowed.value()); + return false; + } + } + return true; +} + + +template +class NestedEffects: public + EffectsMixin, Effects > { + public: + explicit NestedEffects(Zone* zone) : + EffectsMixin, Effects >( + zone) {} + + // Create an extension of the current effect set. The current set should not + // be modified while the extension is in use. + NestedEffects Push() { + NestedEffects result = *this; + result.push(); + return result; + } + + NestedEffects Pop() { + NestedEffects result = *this; + result.pop(); + ASSERT(!this->is_empty()); + return result; + } +}; + +} } // namespace v8::internal + +#endif // V8_EFFECTS_H_ diff --git a/src/splay-tree-inl.h b/src/splay-tree-inl.h index 4eca71d10..42024756e 100644 --- a/src/splay-tree-inl.h +++ b/src/splay-tree-inl.h @@ -90,6 +90,12 @@ bool SplayTree::FindInternal(const Key& key) { } +template +bool SplayTree::Contains(const Key& key) { + return FindInternal(key); +} + + template bool SplayTree::Find(const Key& key, Locator* locator) { if (FindInternal(key)) { @@ -293,9 +299,10 @@ void SplayTree::ForEach(Callback* callback) { template template void SplayTree::ForEachNode(Callback* callback) { + if (root_ == NULL) return; // Pre-allocate some space for tiny trees. List nodes_to_visit(10, allocator_); - if (root_ != NULL) nodes_to_visit.Add(root_, allocator_); + nodes_to_visit.Add(root_, allocator_); int pos = 0; while (pos < nodes_to_visit.length()) { Node* node = nodes_to_visit[pos++]; diff --git a/src/splay-tree.h b/src/splay-tree.h index 8844d8a8f..f393027a8 100644 --- a/src/splay-tree.h +++ b/src/splay-tree.h @@ -39,9 +39,9 @@ namespace internal { // // typedef Key: the key type // typedef Value: the value type -// static const kNoKey: the dummy key used when no key is set -// static const kNoValue: the dummy value used to initialize nodes -// int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function +// static const Key kNoKey: the dummy key used when no key is set +// static Value kNoValue(): the dummy value used to initialize nodes +// static int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function // // The tree is also parameterized by an allocation policy // (Allocator). The policy is used for allocating lists in the C free @@ -74,6 +74,11 @@ class SplayTree { UNREACHABLE(); } + AllocationPolicy allocator() { return allocator_; } + + // Checks if there is a mapping for the key. + bool Contains(const Key& key); + // Inserts the given key in this tree with the given value. Returns // true if a node was inserted, otherwise false. If found the locator // is enabled and provides access to the mapping for the key. @@ -104,6 +109,9 @@ class SplayTree { // Remove the node with the given key from the tree. bool Remove(const Key& key); + // Remove all keys from the tree. + void Clear() { ResetRoot(); } + bool is_empty() { return root_ == NULL; } // Perform the splay operation for the given key. Moves the node with diff --git a/src/types.h b/src/types.h index b2eb60c69..fc69c7852 100644 --- a/src/types.h +++ b/src/types.h @@ -303,6 +303,11 @@ struct Bounds { explicit Bounds(Handle t) : lower(t), upper(t) {} Bounds(Type* t, Isolate* isl) : lower(t, isl), upper(t, isl) {} + // Unrestricted bounds. + static Bounds Unbounded(Isolate* isl) { + return Bounds(Type::None(), Type::Any(), isl); + } + // Meet: both b1 and b2 are known to hold. static Bounds Both(Bounds b1, Bounds b2, Isolate* isl) { return Bounds( diff --git a/src/typing.cc b/src/typing.cc index ad4fbdb9e..0611d7e07 100644 --- a/src/typing.cc +++ b/src/typing.cc @@ -40,7 +40,8 @@ AstTyper::AstTyper(CompilationInfo* info) Handle(info->closure()->shared()->code()), Handle(info->closure()->context()->native_context()), info->isolate(), - info->zone()) { + info->zone()), + store_(info->zone()) { InitializeAstVisitor(); } @@ -79,12 +80,16 @@ void AstTyper::VisitStatements(ZoneList* stmts) { for (int i = 0; i < stmts->length(); ++i) { Statement* stmt = stmts->at(i); RECURSE(Visit(stmt)); + if (stmt->IsJump()) break; } } void AstTyper::VisitBlock(Block* stmt) { RECURSE(VisitStatements(stmt->statements())); + if (stmt->labels() != NULL) { + store_.Forget(); // Control may transfer here via 'break l'. + } } @@ -98,30 +103,41 @@ void AstTyper::VisitEmptyStatement(EmptyStatement* stmt) { void AstTyper::VisitIfStatement(IfStatement* stmt) { - RECURSE(Visit(stmt->condition())); - RECURSE(Visit(stmt->then_statement())); - RECURSE(Visit(stmt->else_statement())); - + // Collect type feedback. if (!stmt->condition()->ToBooleanIsTrue() && !stmt->condition()->ToBooleanIsFalse()) { stmt->condition()->RecordToBooleanTypeFeedback(oracle()); } + + RECURSE(Visit(stmt->condition())); + Effects then_effects = EnterEffects(); + RECURSE(Visit(stmt->then_statement())); + ExitEffects(); + Effects else_effects = EnterEffects(); + RECURSE(Visit(stmt->else_statement())); + ExitEffects(); + then_effects.Alt(else_effects); + store_.Seq(then_effects); } void AstTyper::VisitContinueStatement(ContinueStatement* stmt) { + // TODO(rossberg): is it worth having a non-termination effect? } void AstTyper::VisitBreakStatement(BreakStatement* stmt) { + // TODO(rossberg): is it worth having a non-termination effect? } void AstTyper::VisitReturnStatement(ReturnStatement* stmt) { - RECURSE(Visit(stmt->expression())); - + // Collect type feedback. // TODO(rossberg): we only need this for inlining into test contexts... stmt->expression()->RecordToBooleanTypeFeedback(oracle()); + + RECURSE(Visit(stmt->expression())); + // TODO(rossberg): is it worth having a non-termination effect? } @@ -133,14 +149,18 @@ void AstTyper::VisitWithStatement(WithStatement* stmt) { void AstTyper::VisitSwitchStatement(SwitchStatement* stmt) { RECURSE(Visit(stmt->tag())); + ZoneList* clauses = stmt->cases(); SwitchStatement::SwitchType switch_type = stmt->switch_type(); + Effects local_effects(zone()); + bool complex_effects = false; // True for label effects or fall-through. + for (int i = 0; i < clauses->length(); ++i) { CaseClause* clause = clauses->at(i); + Effects clause_effects = EnterEffects(); + if (!clause->is_default()) { Expression* label = clause->label(); - RECURSE(Visit(label)); - SwitchStatement::SwitchType label_switch_type = label->IsSmiLiteral() ? SwitchStatement::SMI_SWITCH : label->IsStringLiteral() ? SwitchStatement::STRING_SWITCH : @@ -149,13 +169,32 @@ void AstTyper::VisitSwitchStatement(SwitchStatement* stmt) { switch_type = label_switch_type; else if (switch_type != label_switch_type) switch_type = SwitchStatement::GENERIC_SWITCH; + + RECURSE(Visit(label)); + if (!clause_effects.IsEmpty()) complex_effects = true; + } + + ZoneList* stmts = clause->statements(); + RECURSE(VisitStatements(stmts)); + ExitEffects(); + if (stmts->is_empty() || stmts->last()->IsJump()) { + local_effects.Alt(clause_effects); + } else { + complex_effects = true; } - RECURSE(VisitStatements(clause->statements())); } + + if (complex_effects) { + store_.Forget(); // Reached this in unknown state. + } else { + store_.Seq(local_effects); + } + if (switch_type == SwitchStatement::UNKNOWN_SWITCH) switch_type = SwitchStatement::GENERIC_SWITCH; stmt->set_switch_type(switch_type); + // Collect type feedback. // TODO(rossberg): can we eliminate this special case and extra loop? if (switch_type == SwitchStatement::SMI_SWITCH) { for (int i = 0; i < clauses->length(); ++i) { @@ -168,22 +207,31 @@ void AstTyper::VisitSwitchStatement(SwitchStatement* stmt) { void AstTyper::VisitDoWhileStatement(DoWhileStatement* stmt) { - RECURSE(Visit(stmt->body())); - RECURSE(Visit(stmt->cond())); - + // Collect type feedback. if (!stmt->cond()->ToBooleanIsTrue()) { stmt->cond()->RecordToBooleanTypeFeedback(oracle()); } + + // TODO(rossberg): refine the unconditional Forget (here and elsewhere) by + // computing the set of variables assigned in only some of the origins of the + // control transfer (such as the loop body here). + store_.Forget(); // Control may transfer here via looping or 'continue'. + RECURSE(Visit(stmt->body())); + RECURSE(Visit(stmt->cond())); + store_.Forget(); // Control may transfer here via 'break'. } void AstTyper::VisitWhileStatement(WhileStatement* stmt) { - RECURSE(Visit(stmt->cond())); - RECURSE(Visit(stmt->body())); - + // Collect type feedback. if (!stmt->cond()->ToBooleanIsTrue()) { stmt->cond()->RecordToBooleanTypeFeedback(oracle()); } + + store_.Forget(); // Control may transfer here via looping or 'continue'. + RECURSE(Visit(stmt->cond())); + RECURSE(Visit(stmt->body())); + store_.Forget(); // Control may transfer here via termination or 'break'. } @@ -191,45 +239,65 @@ void AstTyper::VisitForStatement(ForStatement* stmt) { if (stmt->init() != NULL) { RECURSE(Visit(stmt->init())); } + store_.Forget(); // Control may transfer here via looping. if (stmt->cond() != NULL) { - RECURSE(Visit(stmt->cond())); - + // Collect type feedback. stmt->cond()->RecordToBooleanTypeFeedback(oracle()); + + RECURSE(Visit(stmt->cond())); } RECURSE(Visit(stmt->body())); + store_.Forget(); // Control may transfer here via 'continue'. if (stmt->next() != NULL) { RECURSE(Visit(stmt->next())); } + store_.Forget(); // Control may transfer here via termination or 'break'. } void AstTyper::VisitForInStatement(ForInStatement* stmt) { + // Collect type feedback. + stmt->RecordTypeFeedback(oracle()); + RECURSE(Visit(stmt->enumerable())); + store_.Forget(); // Control may transfer here via looping or 'continue'. RECURSE(Visit(stmt->body())); - - stmt->RecordTypeFeedback(oracle()); + store_.Forget(); // Control may transfer here via 'break'. } void AstTyper::VisitForOfStatement(ForOfStatement* stmt) { RECURSE(Visit(stmt->iterable())); + store_.Forget(); // Control may transfer here via looping or 'continue'. RECURSE(Visit(stmt->body())); + store_.Forget(); // Control may transfer here via 'break'. } void AstTyper::VisitTryCatchStatement(TryCatchStatement* stmt) { + Effects try_effects = EnterEffects(); RECURSE(Visit(stmt->try_block())); + ExitEffects(); + Effects catch_effects = EnterEffects(); + store_.Forget(); // Control may transfer here via 'throw'. RECURSE(Visit(stmt->catch_block())); + ExitEffects(); + try_effects.Alt(catch_effects); + store_.Seq(try_effects); + // At this point, only variables that were reassigned in the catch block are + // still remembered. } void AstTyper::VisitTryFinallyStatement(TryFinallyStatement* stmt) { RECURSE(Visit(stmt->try_block())); + store_.Forget(); // Control may transfer here via 'throw'. RECURSE(Visit(stmt->finally_block())); } void AstTyper::VisitDebuggerStatement(DebuggerStatement* stmt) { + store_.Forget(); // May do whatever. } @@ -242,11 +310,18 @@ void AstTyper::VisitSharedFunctionInfoLiteral(SharedFunctionInfoLiteral* expr) { void AstTyper::VisitConditional(Conditional* expr) { + // Collect type feedback. + expr->condition()->RecordToBooleanTypeFeedback(oracle()); + RECURSE(Visit(expr->condition())); + Effects then_effects = EnterEffects(); RECURSE(Visit(expr->then_expression())); + ExitEffects(); + Effects else_effects = EnterEffects(); RECURSE(Visit(expr->else_expression())); - - expr->condition()->RecordToBooleanTypeFeedback(oracle()); + ExitEffects(); + then_effects.Alt(else_effects); + store_.Seq(then_effects); NarrowType(expr, Bounds::Either( expr->then_expression()->bounds(), @@ -255,7 +330,10 @@ void AstTyper::VisitConditional(Conditional* expr) { void AstTyper::VisitVariableProxy(VariableProxy* expr) { - // TODO(rossberg): typing of variables + Variable* var = expr->var(); + if (var->IsStackAllocated()) { + NarrowType(expr, store_.LookupBounds(variable_index(var))); + } } @@ -274,8 +352,8 @@ void AstTyper::VisitObjectLiteral(ObjectLiteral* expr) { ZoneList* properties = expr->properties(); for (int i = 0; i < properties->length(); ++i) { ObjectLiteral::Property* prop = properties->at(i); - RECURSE(Visit(prop->value())); + // Collect type feedback. if ((prop->kind() == ObjectLiteral::Property::MATERIALIZED_LITERAL && !CompileTimeValue::IsCompileTimeValue(prop->value())) || prop->kind() == ObjectLiteral::Property::COMPUTED) { @@ -283,6 +361,8 @@ void AstTyper::VisitObjectLiteral(ObjectLiteral* expr) { prop->RecordTypeFeedback(oracle()); } } + + RECURSE(Visit(prop->value())); } NarrowType(expr, Bounds(Type::Object(), isolate_)); @@ -303,8 +383,7 @@ void AstTyper::VisitArrayLiteral(ArrayLiteral* expr) { void AstTyper::VisitAssignment(Assignment* expr) { // TODO(rossberg): Can we clean this up? if (expr->is_compound()) { - RECURSE(Visit(expr->binary_operation())); - + // Collect type feedback. Expression* target = expr->target(); Property* prop = target->AsProperty(); if (prop != NULL) { @@ -314,18 +393,25 @@ void AstTyper::VisitAssignment(Assignment* expr) { } } + RECURSE(Visit(expr->binary_operation())); + NarrowType(expr, expr->binary_operation()->bounds()); } else { - RECURSE(Visit(expr->target())); - RECURSE(Visit(expr->value())); - - if (expr->target()->AsProperty()) { + // Collect type feedback. + if (expr->target()->IsProperty()) { expr->RecordTypeFeedback(oracle(), zone()); } + RECURSE(Visit(expr->target())); + RECURSE(Visit(expr->value())); + NarrowType(expr, expr->value()->bounds()); } - // TODO(rossberg): handle target variables + + VariableProxy* proxy = expr->target()->AsVariableProxy(); + if (proxy != NULL && proxy->var()->IsStackAllocated()) { + store_.Seq(variable_index(proxy->var()), Effect(expr->bounds())); + } } @@ -333,35 +419,31 @@ void AstTyper::VisitYield(Yield* expr) { RECURSE(Visit(expr->generator_object())); RECURSE(Visit(expr->expression())); - // We don't know anything about the type. + // We don't know anything about the result type. } void AstTyper::VisitThrow(Throw* expr) { RECURSE(Visit(expr->exception())); + // TODO(rossberg): is it worth having a non-termination effect? NarrowType(expr, Bounds(Type::None(), isolate_)); } void AstTyper::VisitProperty(Property* expr) { + // Collect type feedback. + expr->RecordTypeFeedback(oracle(), zone()); + RECURSE(Visit(expr->obj())); RECURSE(Visit(expr->key())); - expr->RecordTypeFeedback(oracle(), zone()); - - // We don't know anything about the type. + // We don't know anything about the result type. } void AstTyper::VisitCall(Call* expr) { - RECURSE(Visit(expr->expression())); - ZoneList* args = expr->arguments(); - for (int i = 0; i < args->length(); ++i) { - Expression* arg = args->at(i); - RECURSE(Visit(arg)); - } - + // Collect type feedback. Expression* callee = expr->expression(); Property* prop = callee->AsProperty(); if (prop != NULL) { @@ -371,11 +453,26 @@ void AstTyper::VisitCall(Call* expr) { expr->RecordTypeFeedback(oracle(), CALL_AS_FUNCTION); } - // We don't know anything about the type. + RECURSE(Visit(expr->expression())); + ZoneList* args = expr->arguments(); + for (int i = 0; i < args->length(); ++i) { + Expression* arg = args->at(i); + RECURSE(Visit(arg)); + } + + VariableProxy* proxy = expr->expression()->AsVariableProxy(); + if (proxy != NULL && proxy->var()->is_possibly_eval(isolate())) { + store_.Forget(); // Eval could do whatever to local variables. + } + + // We don't know anything about the result type. } void AstTyper::VisitCallNew(CallNew* expr) { + // Collect type feedback. + expr->RecordTypeFeedback(oracle()); + RECURSE(Visit(expr->expression())); ZoneList* args = expr->arguments(); for (int i = 0; i < args->length(); ++i) { @@ -383,9 +480,7 @@ void AstTyper::VisitCallNew(CallNew* expr) { RECURSE(Visit(arg)); } - expr->RecordTypeFeedback(oracle()); - - // We don't know anything about the type. + // We don't know anything about the result type. } @@ -396,13 +491,11 @@ void AstTyper::VisitCallRuntime(CallRuntime* expr) { RECURSE(Visit(arg)); } - // We don't know anything about the type. + // We don't know anything about the result type. } void AstTyper::VisitUnaryOperation(UnaryOperation* expr) { - RECURSE(Visit(expr->expression())); - // Collect type feedback. Handle op_type = oracle()->UnaryType(expr->UnaryOperationFeedbackId()); NarrowLowerType(expr->expression(), op_type); @@ -411,6 +504,8 @@ void AstTyper::VisitUnaryOperation(UnaryOperation* expr) { expr->expression()->RecordToBooleanTypeFeedback(oracle()); } + RECURSE(Visit(expr->expression())); + switch (expr->op()) { case Token::NOT: case Token::DELETE: @@ -432,22 +527,25 @@ void AstTyper::VisitUnaryOperation(UnaryOperation* expr) { void AstTyper::VisitCountOperation(CountOperation* expr) { - RECURSE(Visit(expr->expression())); - + // Collect type feedback. expr->RecordTypeFeedback(oracle(), zone()); Property* prop = expr->expression()->AsProperty(); if (prop != NULL) { prop->RecordTypeFeedback(oracle(), zone()); } + RECURSE(Visit(expr->expression())); + NarrowType(expr, Bounds(Type::Smi(), Type::Number(), isolate_)); + + VariableProxy* proxy = expr->expression()->AsVariableProxy(); + if (proxy != NULL && proxy->var()->IsStackAllocated()) { + store_.Seq(variable_index(proxy->var()), Effect(expr->bounds())); + } } void AstTyper::VisitBinaryOperation(BinaryOperation* expr) { - RECURSE(Visit(expr->left())); - RECURSE(Visit(expr->right())); - // Collect type feedback. Handle type, left_type, right_type; Maybe fixed_right_arg; @@ -463,15 +561,29 @@ void AstTyper::VisitBinaryOperation(BinaryOperation* expr) { switch (expr->op()) { case Token::COMMA: + RECURSE(Visit(expr->left())); + RECURSE(Visit(expr->right())); NarrowType(expr, expr->right()->bounds()); break; case Token::OR: - case Token::AND: + case Token::AND: { + Effects left_effects = EnterEffects(); + RECURSE(Visit(expr->left())); + ExitEffects(); + Effects right_effects = EnterEffects(); + RECURSE(Visit(expr->right())); + ExitEffects(); + left_effects.Alt(right_effects); + store_.Seq(left_effects); + NarrowType(expr, Bounds::Either( expr->left()->bounds(), expr->right()->bounds(), isolate_)); break; + } case Token::BIT_OR: case Token::BIT_AND: { + RECURSE(Visit(expr->left())); + RECURSE(Visit(expr->right())); Type* upper = Type::Union( expr->left()->bounds().upper, expr->right()->bounds().upper); if (!upper->Is(Type::Signed32())) upper = Type::Signed32(); @@ -481,12 +593,18 @@ void AstTyper::VisitBinaryOperation(BinaryOperation* expr) { case Token::BIT_XOR: case Token::SHL: case Token::SAR: + RECURSE(Visit(expr->left())); + RECURSE(Visit(expr->right())); NarrowType(expr, Bounds(Type::Smi(), Type::Signed32(), isolate_)); break; case Token::SHR: + RECURSE(Visit(expr->left())); + RECURSE(Visit(expr->right())); NarrowType(expr, Bounds(Type::Smi(), Type::Unsigned32(), isolate_)); break; case Token::ADD: { + RECURSE(Visit(expr->left())); + RECURSE(Visit(expr->right())); Bounds l = expr->left()->bounds(); Bounds r = expr->right()->bounds(); Type* lower = @@ -506,6 +624,8 @@ void AstTyper::VisitBinaryOperation(BinaryOperation* expr) { case Token::MUL: case Token::DIV: case Token::MOD: + RECURSE(Visit(expr->left())); + RECURSE(Visit(expr->right())); NarrowType(expr, Bounds(Type::Smi(), Type::Number(), isolate_)); break; default: @@ -515,9 +635,6 @@ void AstTyper::VisitBinaryOperation(BinaryOperation* expr) { void AstTyper::VisitCompareOperation(CompareOperation* expr) { - RECURSE(Visit(expr->left())); - RECURSE(Visit(expr->right())); - // Collect type feedback. Handle left_type, right_type, combined_type; oracle()->CompareType(expr->CompareOperationFeedbackId(), @@ -526,6 +643,9 @@ void AstTyper::VisitCompareOperation(CompareOperation* expr) { NarrowLowerType(expr->right(), right_type); expr->set_combined_type(combined_type); + RECURSE(Visit(expr->left())); + RECURSE(Visit(expr->right())); + NarrowType(expr, Bounds(Type::Boolean(), isolate_)); } diff --git a/src/typing.h b/src/typing.h index ceef98436..c942b0063 100644 --- a/src/typing.h +++ b/src/typing.h @@ -35,6 +35,7 @@ #include "compiler.h" #include "type-info.h" #include "types.h" +#include "effects.h" #include "zone.h" #include "scopes.h" @@ -57,8 +58,13 @@ class AstTyper: public AstVisitor { private: explicit AstTyper(CompilationInfo* info); + static const int kNoVar = INT_MIN; + typedef v8::internal::Effects Effects; + typedef v8::internal::NestedEffects Store; + CompilationInfo* info_; TypeFeedbackOracle oracle_; + Store store_; TypeFeedbackOracle* oracle() { return &oracle_; } Zone* zone() const { return info_->zone(); } @@ -70,6 +76,17 @@ class AstTyper: public AstVisitor { e->set_bounds(Bounds::NarrowLower(e->bounds(), t, isolate_)); } + Effects EnterEffects() { + store_ = store_.Push(); + return store_.Top(); + } + void ExitEffects() { store_ = store_.Pop(); } + + int variable_index(Variable* var) { + return var->IsStackLocal() ? var->index() : + var->IsParameter() ? -var->index() : kNoVar; + } + void VisitDeclarations(ZoneList* declarations); void VisitStatements(ZoneList* statements); diff --git a/src/zone-inl.h b/src/zone-inl.h index 49e7626f7..f257382a2 100644 --- a/src/zone-inl.h +++ b/src/zone-inl.h @@ -109,6 +109,12 @@ void* ZoneList::operator new(size_t size, Zone* zone) { } +template +void* ZoneSplayTree::operator new(size_t size, Zone* zone) { + return zone->New(static_cast(size)); +} + + } } // namespace v8::internal #endif // V8_ZONE_INL_H_ diff --git a/src/zone.h b/src/zone.h index a12ed7931..a61099c6b 100644 --- a/src/zone.h +++ b/src/zone.h @@ -177,6 +177,7 @@ struct ZoneAllocationPolicy { explicit ZoneAllocationPolicy(Zone* zone) : zone_(zone) { } INLINE(void* New(size_t size)); INLINE(static void Delete(void *pointer)) { } + Zone* zone() { return zone_; } private: Zone* zone_; @@ -246,6 +247,8 @@ class ZoneSplayTree: public SplayTree { explicit ZoneSplayTree(Zone* zone) : SplayTree(ZoneAllocationPolicy(zone)) {} ~ZoneSplayTree(); + + INLINE(void* operator new(size_t size, Zone* zone)); }; diff --git a/test/cctest/test-global-handles.cc b/test/cctest/test-global-handles.cc index 3d79dba7a..10a1d7986 100644 --- a/test/cctest/test-global-handles.cc +++ b/test/cctest/test-global-handles.cc @@ -418,7 +418,7 @@ class RandomMutationData { int32_t offset = ++weak_offset_; object->Set(7, v8::Integer::New(offset, isolate)); v8::Persistent persistent(isolate, object); - persistent.MakeWeak(isolate, this, WeakCallback); + persistent.MakeWeak(this, WeakCallback); persistent.MarkIndependent(); Object** location = v8::Utils::OpenPersistent(persistent).location(); bool inserted = diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index 582681c1a..82b4c3fd0 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -290,6 +290,7 @@ '../../src/double.h', '../../src/dtoa.cc', '../../src/dtoa.h', + '../../src/effects.h', '../../src/elements-kind.cc', '../../src/elements-kind.h', '../../src/elements.cc', -- 2.34.1