From 918ef9d712ab77bc33ffb8eb985a6fd5672602f6 Mon Sep 17 00:00:00 2001 From: "Ben L. Titzer" Date: Wed, 3 Dec 2014 16:03:16 +0100 Subject: [PATCH] Revert "[turbofan] Reuse forward fixpoint algorithm in Typer by making it a Reducer." This reverts commit a48ad24a7c258d95acf3a6ae126036953a9122dd. BUG= Review URL: https://codereview.chromium.org/763773004 Cr-Commit-Position: refs/heads/master@{#25643} --- src/compiler/node-properties-inl.h | 5 -- src/compiler/node-properties.h | 1 - src/compiler/typer.cc | 176 ++++++++++++++++++------------------- src/compiler/typer.h | 2 + 4 files changed, 90 insertions(+), 94 deletions(-) diff --git a/src/compiler/node-properties-inl.h b/src/compiler/node-properties-inl.h index 1ff0938..5fe0cb6 100644 --- a/src/compiler/node-properties-inl.h +++ b/src/compiler/node-properties-inl.h @@ -201,11 +201,6 @@ inline Bounds NodeProperties::GetBounds(Node* node) { return node->bounds(); } -inline void NodeProperties::RemoveBounds(Node* node) { - Bounds empty; - node->set_bounds(empty); -} - inline void NodeProperties::SetBounds(Node* node, Bounds b) { DCHECK(b.lower != NULL && b.upper != NULL); node->set_bounds(b); diff --git a/src/compiler/node-properties.h b/src/compiler/node-properties.h index 025be78..0f7a161 100644 --- a/src/compiler/node-properties.h +++ b/src/compiler/node-properties.h @@ -43,7 +43,6 @@ class NodeProperties { static inline bool IsTyped(Node* node); static inline Bounds GetBounds(Node* node); static inline void SetBounds(Node* node, Bounds bounds); - static inline void RemoveBounds(Node* node); static inline bool AllValueInputsAreTyped(Node* node); static inline int FirstValueIndex(Node* node); diff --git a/src/compiler/typer.cc b/src/compiler/typer.cc index e5b7b83..67b73eb 100644 --- a/src/compiler/typer.cc +++ b/src/compiler/typer.cc @@ -4,7 +4,6 @@ #include "src/bootstrapper.h" #include "src/compiler/graph-inl.h" -#include "src/compiler/graph-reducer.h" #include "src/compiler/js-operator.h" #include "src/compiler/node.h" #include "src/compiler/node-properties-inl.h" @@ -218,42 +217,10 @@ Typer::~Typer() { } -class Typer::Visitor : public Reducer { +class Typer::Visitor : public NullNodeVisitor { public: explicit Visitor(Typer* typer) : typer_(typer) {} - virtual Reduction Reduce(Node* node) OVERRIDE { - if (node->op()->ValueOutputCount() == 0) return NoChange(); - switch (node->opcode()) { -#define DECLARE_CASE(x) \ - case IrOpcode::k##x: \ - return UpdateBounds(node, TypeBinaryOp(node, x##Typer)); - JS_SIMPLE_BINOP_LIST(DECLARE_CASE) -#undef DECLARE_CASE - -#define DECLARE_CASE(x) \ - case IrOpcode::k##x: \ - return UpdateBounds(node, Type##x(node)); - DECLARE_CASE(Start) - // VALUE_OP_LIST without JS_SIMPLE_BINOP_LIST: - COMMON_OP_LIST(DECLARE_CASE) - SIMPLIFIED_OP_LIST(DECLARE_CASE) - MACHINE_OP_LIST(DECLARE_CASE) - JS_SIMPLE_UNOP_LIST(DECLARE_CASE) - JS_OBJECT_OP_LIST(DECLARE_CASE) - JS_CONTEXT_OP_LIST(DECLARE_CASE) - JS_OTHER_OP_LIST(DECLARE_CASE) -#undef DECLARE_CASE - -#define DECLARE_CASE(x) case IrOpcode::k##x: - DECLARE_CASE(End) - INNER_CONTROL_OP_LIST(DECLARE_CASE) -#undef DECLARE_CASE - break; - } - return NoChange(); - } - Bounds TypeNode(Node* node) { switch (node->opcode()) { #define DECLARE_CASE(x) \ @@ -285,10 +252,7 @@ class Typer::Visitor : public Reducer { Type* TypeConstant(Handle value); - private: - Typer* typer_; - MaybeHandle context_; - + protected: #define DECLARE_METHOD(x) inline Bounds Type##x(Node* node); DECLARE_METHOD(Start) VALUE_OP_LIST(DECLARE_METHOD) @@ -319,6 +283,10 @@ class Typer::Visitor : public Reducer { Graph* graph() { return typer_->graph(); } MaybeHandle context() { return typer_->context(); } + private: + Typer* typer_; + MaybeHandle context_; + typedef Type* (*UnaryTyperFun)(Type*, Typer* t); typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t); @@ -351,60 +319,97 @@ class Typer::Visitor : public Reducer { static Type* JSUnaryNotTyper(Type*, Typer*); static Type* JSLoadPropertyTyper(Type*, Type*, Typer*); static Type* JSCallFunctionTyper(Type*, Typer*); +}; - Reduction UpdateBounds(Node* node, Bounds current) { - if (NodeProperties::IsTyped(node)) { - // Widen the bounds of a previously typed node. - Bounds previous = NodeProperties::GetBounds(node); - // Speed up termination in the presence of range types: - current.upper = Weaken(current.upper, previous.upper); - current.lower = Weaken(current.lower, previous.lower); - - // Types should not get less precise. - DCHECK(previous.lower->Is(current.lower)); - DCHECK(previous.upper->Is(current.upper)); - - NodeProperties::SetBounds(node, current); - if (!(previous.Narrows(current) && current.Narrows(previous))) { - // If something changed, revisit all uses. - return Changed(node); - } - return NoChange(); - } else { - // No previous type, simply update the bounds. - NodeProperties::SetBounds(node, current); - return Changed(node); + +class Typer::RunVisitor : public Typer::Visitor { + public: + explicit RunVisitor(Typer* typer) + : Visitor(typer), + redo(NodeSet::key_compare(), NodeSet::allocator_type(typer->zone())) {} + + void Post(Node* node) { + if (node->op()->ValueOutputCount() > 0) { + Bounds bounds = TypeNode(node); + NodeProperties::SetBounds(node, bounds); + // Remember incompletely typed nodes for least fixpoint iteration. + if (!NodeProperties::AllValueInputsAreTyped(node)) redo.insert(node); } } + + NodeSet redo; }; -void Typer::Run() { - { - // TODO(titzer): this is a hack. Reset types for interior nodes first. - NodeDeque deque(zone()); - NodeMarker marked(graph(), 2); - deque.push_front(graph()->end()); - marked.Set(graph()->end(), true); - while (!deque.empty()) { - Node* node = deque.front(); - deque.pop_front(); - // TODO(titzer): there shouldn't be a need to retype constants. - if (node->op()->ValueOutputCount() > 0) - NodeProperties::RemoveBounds(node); - for (Node* input : node->inputs()) { - if (!marked.Get(input)) { - marked.Set(input, true); - deque.push_back(input); +class Typer::WidenVisitor : public Typer::Visitor { + public: + explicit WidenVisitor(Typer* typer) + : Visitor(typer), + local_zone_(zone()->isolate()), + enabled_(graph()->NodeCount(), true, &local_zone_), + queue_(&local_zone_) {} + + void Run(NodeSet* nodes) { + // Queue all the roots. + for (Node* node : *nodes) { + Queue(node); + } + + while (!queue_.empty()) { + Node* node = queue_.front(); + queue_.pop(); + + if (node->op()->ValueOutputCount() > 0) { + // Enable future queuing (and thus re-typing) of this node. + enabled_[node->id()] = true; + + // Compute the new type. + Bounds previous = BoundsOrNone(node); + Bounds current = TypeNode(node); + + // Speed up termination in the presence of range types: + current.upper = Weaken(current.upper, previous.upper); + current.lower = Weaken(current.lower, previous.lower); + + // Types should not get less precise. + DCHECK(previous.lower->Is(current.lower)); + DCHECK(previous.upper->Is(current.upper)); + + NodeProperties::SetBounds(node, current); + // If something changed, push all uses into the queue. + if (!(previous.Narrows(current) && current.Narrows(previous))) { + for (Node* use : node->uses()) { + Queue(use); + } } } + // If there is no value output, we deliberately leave the node disabled + // for queuing - there is no need to type it. + } + } + + void Queue(Node* node) { + // If the node is enabled for queuing, push it to the queue and disable it + // (to avoid queuing it multiple times). + if (enabled_[node->id()]) { + queue_.push(node); + enabled_[node->id()] = false; } } - Visitor visitor(this); - GraphReducer graph_reducer(graph(), zone()); - graph_reducer.AddReducer(&visitor); - graph_reducer.ReduceGraph(); + private: + Zone local_zone_; + BoolVector enabled_; + ZoneQueue queue_; +}; + + +void Typer::Run() { + RunVisitor typing(this); + graph_->VisitNodeInputsFromEnd(&typing); + // Find least fixpoint. + WidenVisitor widen(this); + widen.Run(&typing.redo); } @@ -1297,17 +1302,12 @@ Bounds Typer::Visitor::TypeJSInstanceOf(Node* node) { Bounds Typer::Visitor::TypeJSLoadContext(Node* node) { Bounds outer = Operand(node, 0); - Type* context_type = outer.upper; - if (context_type->Is(Type::None())) { - // Upper bound of context is not yet known. - return Bounds(Type::None(), Type::Any()); - } - - DCHECK(context_type->Maybe(Type::Internal())); + DCHECK(outer.upper->Maybe(Type::Internal())); // TODO(rossberg): More precisely, instead of the above assertion, we should // back-propagate the constraint that it has to be a subtype of Internal. ContextAccess access = OpParameter(node); + Type* context_type = outer.upper; MaybeHandle context; if (context_type->IsConstant()) { context = Handle::cast(context_type->AsConstant()->Value()); diff --git a/src/compiler/typer.h b/src/compiler/typer.h index 7b740e1..6c5bc1e 100644 --- a/src/compiler/typer.h +++ b/src/compiler/typer.h @@ -31,6 +31,8 @@ class Typer { private: class Visitor; + class RunVisitor; + class WidenVisitor; class Decorator; Graph* graph_; -- 2.7.4