Revert "[turbofan] Reuse forward fixpoint algorithm in Typer by making it a Reducer."

src/compiler/typer.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #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"
 #include "src/compiler/node-properties.h"
 #include "src/compiler/simplified-operator.h"
 #include "src/compiler/typer.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
@@ skipping 193 matching lines @@
   decorator_ = new (zone) Decorator(this);
   graph_->AddDecorator(decorator_);
 }
 
 
 Typer::~Typer() {
   graph_->RemoveDecorator(decorator_);
 }
 
 
-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) \
       case IrOpcode::k##x: return TypeBinaryOp(node, x##Typer);
       JS_SIMPLE_BINOP_LIST(DECLARE_CASE)
 #undef DECLARE_CASE
 
 #define DECLARE_CASE(x) case IrOpcode::k##x: return Type##x(node);
       DECLARE_CASE(Start)
       // VALUE_OP_LIST without JS_SIMPLE_BINOP_LIST:
@@ skipping 11 matching lines @@
       INNER_CONTROL_OP_LIST(DECLARE_CASE)
 #undef DECLARE_CASE
       break;
     }
     UNREACHABLE();
     return Bounds();
   }
 
   Type* TypeConstant(Handle<Object> value);
 
- private:
-  Typer* typer_;
-  MaybeHandle<Context> context_;
-
+ protected:
 #define DECLARE_METHOD(x) inline Bounds Type##x(Node* node);
   DECLARE_METHOD(Start)
   VALUE_OP_LIST(DECLARE_METHOD)
 #undef DECLARE_METHOD
 
   Bounds BoundsOrNone(Node* node) {
     return NodeProperties::IsTyped(node) ? NodeProperties::GetBounds(node)
                                          : Bounds(Type::None());
   }
 
@@ skipping 10 matching lines @@
     return result;
   }
 
   Type* Weaken(Type* current_type, Type* previous_type);
 
   Zone* zone() { return typer_->zone(); }
   Isolate* isolate() { return typer_->isolate(); }
   Graph* graph() { return typer_->graph(); }
   MaybeHandle<Context> context() { return typer_->context(); }
 
+ private:
+  Typer* typer_;
+  MaybeHandle<Context> context_;
+
   typedef Type* (*UnaryTyperFun)(Type*, Typer* t);
   typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t);
 
   Bounds TypeUnaryOp(Node* node, UnaryTyperFun);
   Bounds TypeBinaryOp(Node* node, BinaryTyperFun);
 
   static Type* Invert(Type*, Typer*);
   static Type* FalsifyUndefined(Type*, Typer*);
   static Type* Rangify(Type*, Typer*);
 
@@ skipping 12 matching lines @@
 
   static Type* JSCompareTyper(Type*, Type*, Typer*);
 
 #define DECLARE_METHOD(x) static Type* x##Typer(Type*, Type*, Typer*);
   JS_SIMPLE_BINOP_LIST(DECLARE_METHOD)
 #undef DECLARE_METHOD
 
   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));
+class Typer::RunVisitor : public Typer::Visitor {
+ public:
+  explicit RunVisitor(Typer* typer)
+      : Visitor(typer),
+        redo(NodeSet::key_compare(), NodeSet::allocator_type(typer->zone())) {}
 
-      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);
+  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;
+};
+
+
+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;
+    }
+  }
+
+ private:
+  Zone local_zone_;
+  BoolVector enabled_;
+  ZoneQueue<Node*> queue_;
 };
 
 
 void Typer::Run() {
-  {
-    // TODO(titzer): this is a hack. Reset types for interior nodes first.
-    NodeDeque deque(zone());
-    NodeMarker<bool> 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);
-        }
-      }
-    }
-  }
-
-  Visitor visitor(this);
-  GraphReducer graph_reducer(graph(), zone());
-  graph_reducer.AddReducer(&visitor);
-  graph_reducer.ReduceGraph();
+  RunVisitor typing(this);
+  graph_->VisitNodeInputsFromEnd(&typing);
+  // Find least fixpoint.
+  WidenVisitor widen(this);
+  widen.Run(&typing.redo);
 }
 
 
 void Typer::Decorator::Decorate(Node* node) {
   if (node->op()->ValueOutputCount() > 0) {
     // Only eagerly type-decorate nodes with known input types.
     // Other cases will generally require a proper fixpoint iteration with Run.
     bool is_typed = NodeProperties::IsTyped(node);
     if (is_typed || NodeProperties::AllValueInputsAreTyped(node)) {
       Visitor typing(typer_);
@@ skipping 872 matching lines @@
 Bounds Typer::Visitor::TypeJSInstanceOf(Node* node) {
   return Bounds(Type::None(zone()), Type::Boolean(zone()));
 }
 
 
 // JS context operators.
 
 
 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<ContextAccess>(node);
+  Type* context_type = outer.upper;
   MaybeHandle<Context> context;
   if (context_type->IsConstant()) {
     context = Handle<Context>::cast(context_type->AsConstant()->Value());
   }
   // Walk context chain (as far as known), mirroring dynamic lookup.
   // Since contexts are mutable, the information is only useful as a lower
   // bound.
   // TODO(rossberg): Could use scope info to fix upper bounds for constant
   // bindings if we know that this code is never shared.
   for (size_t i = access.depth(); i > 0; --i) {
@@ skipping 753 matching lines @@
         return typer_->cache_->Get(kFloat64ArrayFunc);
       }
     }
   }
   return Type::Constant(value, zone());
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8