[turbofan] Allow non-speculative operators to consume feedback types.

src/compiler/simplified-lowering.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/compiler/simplified-lowering.h"
 
 #include <limits>
 
 #include "src/address-map.h"
 #include "src/base/bits.h"
@@ skipping 33 matching lines @@
   // 1.) PROPAGATE: Traverse the graph from the end, pushing usage information
   //     backwards from uses to definitions, around cycles in phis, according
   //     to local rules for each operator.
   //     During this phase, the usage information for a node determines the best
   //     possible lowering for each operator so far, and that in turn determines
   //     the output representation.
   //     Therefore, to be correct, this phase must iterate to a fixpoint before
   //     the next phase can begin.
   PROPAGATE,
 
-  // 2.) LOWER: perform lowering for all {Simplified} nodes by replacing some
+  // 2.) RETYPE: Traverse the graph from the end, propagating types from type
+  //     feedback forwards.

[Jarin, 2016/07/12 08:51:49]

Just say "Propagate types from type feedback forwards."

The traverse from end part is just to get an RPO order, and thus make
convergence faster.

[Benedikt Meurer, 2016/07/12 09:43:48]

Done.

+  RETYPE,
+
+  // 3.) LOWER: perform lowering for all {Simplified} nodes by replacing some
   //     operators for some nodes, expanding some nodes to multiple nodes, or
   //     removing some (redundant) nodes.
   //     During this phase, use the {RepresentationChanger} to insert
   //     representation changes between uses that demand a particular
   //     representation and nodes that produce a different representation.
   LOWER
 };
 
-
 namespace {
 
 
 UseInfo TruncatingUseInfoFromRepresentation(MachineRepresentation rep) {
   switch (rep) {
     case MachineRepresentation::kTagged:
       return UseInfo::AnyTagged();
     case MachineRepresentation::kFloat64:
       return UseInfo::TruncatingFloat64();
     case MachineRepresentation::kFloat32:
@@ skipping 165 matching lines @@
         changer_(changer),
         queue_(zone),
         typing_stack_(zone),
         source_positions_(source_positions),
         type_cache_(TypeCache::Get()),
         op_typer_(jsgraph->isolate(), graph_zone()) {
   }
 
   // Forward propagation of types from type feedback.
   void RunTypePropagationPhase() {
+    // Run type propagation.
+    TRACE("--{Type propagation phase}--\n");
+    phase_ = RETYPE;
+    ResetNodeInfoState();
+
     DCHECK(typing_stack_.empty());
-
     typing_stack_.push({graph()->end(), 0});
     GetInfo(graph()->end())->set_pushed();
     while (!typing_stack_.empty()) {
       NodeState& current = typing_stack_.top();
 
       // If there is an unvisited input, push it and continue.
       bool pushed_unvisited = false;
       while (current.input_index < current.node->InputCount()) {
         Node* input = current.node->InputAt(current.input_index);
         NodeInfo* input_info = GetInfo(input);
         current.input_index++;
         if (input_info->unvisited()) {
           input_info->set_pushed();
           typing_stack_.push({input, 0});
           pushed_unvisited = true;
           break;
         }
       }
       if (pushed_unvisited) continue;
 
       // Process the top of the stack.
       Node* node = current.node;
       typing_stack_.pop();
       NodeInfo* info = GetInfo(node);
       info->set_visited();
       bool updated = UpdateFeedbackType(node);
+      TRACE(" visit #%d: %s\n", node->id(), node->op()->mnemonic());
+      VisitNode(node, info->truncation(), nullptr);

[Jarin, 2016/07/12 08:51:49]

Hmm, not too happy about uselessly invoking the input truncation propagation
machinery. You only really need to set the representation here.

[Benedikt Meurer, 2016/07/12 09:43:48]

Acknowledged.

       if (updated) {
         for (Node* const user : node->uses()) {
           if (GetInfo(user)->visited()) {
             GetInfo(user)->set_queued();
             queue_.push(user);
           }
         }
       }
     }
 
     // Process the revisit queue.
     while (!queue_.empty()) {
       Node* node = queue_.front();
       queue_.pop();
       NodeInfo* info = GetInfo(node);
       info->set_visited();
       bool updated = UpdateFeedbackType(node);
+      TRACE(" visit #%d: %s\n", node->id(), node->op()->mnemonic());
+      VisitNode(node, info->truncation(), nullptr);
       if (updated) {
         for (Node* const user : node->uses()) {
           if (GetInfo(user)->visited()) {
             GetInfo(user)->set_queued();
             queue_.push(user);
           }
         }
       }
     }
   }
@@ skipping 65 matching lines @@
     }
 
     switch (node->opcode()) {
       case IrOpcode::kSpeculativeNumberAdd: {
         // TODO(jarin) The ToNumber conversion is too conservative here,
         // e.g. it will treat true as 1 even though the number check will
         // fail on a boolean. OperationTyper should have a function that
         // computes a more precise type.
         Type* lhs = op_typer_.ToNumber(FeedbackTypeOf(node->InputAt(0)));
         Type* rhs = op_typer_.ToNumber(FeedbackTypeOf(node->InputAt(1)));
-        Type* static_type = op_typer_.NumericAdd(lhs, rhs);
+        Type* static_type = op_typer_.NumberAdd(lhs, rhs);
         if (info->type_check() == TypeCheckKind::kNone) {
           new_type = static_type;
         } else {
           Type* feedback_type = TypeOfSpeculativeOp(info->type_check());
           new_type = Type::Intersect(static_type, feedback_type, graph_zone());
         }
         break;
       }
 
       case IrOpcode::kSpeculativeNumberSubtract: {
         // TODO(jarin) The ToNumber conversion is too conservative here,
         // e.g. it will treat true as 1 even though the number check will
         // fail on a boolean. OperationTyper should have a function that
         // computes a more precise type.
         Type* lhs = op_typer_.ToNumber(FeedbackTypeOf(node->InputAt(0)));
         Type* rhs = op_typer_.ToNumber(FeedbackTypeOf(node->InputAt(1)));
-        Type* static_type = op_typer_.NumericSubtract(lhs, rhs);
+        Type* static_type = op_typer_.NumberSubtract(lhs, rhs);
         if (info->type_check() == TypeCheckKind::kNone) {
           new_type = static_type;
         } else {
           Type* feedback_type = TypeOfSpeculativeOp(info->type_check());
           new_type = Type::Intersect(static_type, feedback_type, graph_zone());
         }
         break;
       }
 
       case IrOpcode::kSpeculativeNumberMultiply: {
         // TODO(jarin) The ToNumber conversion is too conservative here,
         // e.g. it will treat true as 1 even though the number check will
         // fail on a boolean. OperationTyper should have a function that
         // computes a more precise type.
         Type* lhs = op_typer_.ToNumber(FeedbackTypeOf(node->InputAt(0)));
         Type* rhs = op_typer_.ToNumber(FeedbackTypeOf(node->InputAt(1)));
-        Type* static_type = op_typer_.NumericMultiply(lhs, rhs);
+        Type* static_type = op_typer_.NumberMultiply(lhs, rhs);
         if (info->type_check() == TypeCheckKind::kNone) {
           new_type = static_type;
         } else {
           Type* feedback_type = TypeOfSpeculativeOp(info->type_check());
           new_type = Type::Intersect(static_type, feedback_type, graph_zone());
         }
         break;
       }
 
       case IrOpcode::kSpeculativeNumberDivide: {
         // TODO(jarin) The ToNumber conversion is too conservative here,
         // e.g. it will treat true as 1 even though the number check will
         // fail on a boolean. OperationTyper should have a function that
         // computes a more precise type.
         Type* lhs = op_typer_.ToNumber(FeedbackTypeOf(node->InputAt(0)));
         Type* rhs = op_typer_.ToNumber(FeedbackTypeOf(node->InputAt(1)));
-        Type* static_type = op_typer_.NumericDivide(lhs, rhs);
+        Type* static_type = op_typer_.NumberDivide(lhs, rhs);
         if (info->type_check() == TypeCheckKind::kNone) {
           new_type = static_type;
         } else {
           Type* feedback_type = TypeOfSpeculativeOp(info->type_check());
           new_type = Type::Intersect(static_type, feedback_type, graph_zone());
         }
         break;
       }
 
       case IrOpcode::kSpeculativeNumberModulus: {
         // TODO(jarin) The ToNumber conversion is too conservative here,
         // e.g. it will treat true as 1 even though the number check will
         // fail on a boolean. OperationTyper should have a function that
         // computes a more precise type.
         Type* lhs = op_typer_.ToNumber(FeedbackTypeOf(node->InputAt(0)));
         Type* rhs = op_typer_.ToNumber(FeedbackTypeOf(node->InputAt(1)));
-        Type* static_type = op_typer_.NumericModulus(lhs, rhs);
+        Type* static_type = op_typer_.NumberModulus(lhs, rhs);
         if (info->type_check() == TypeCheckKind::kNone) {
           new_type = static_type;
         } else {
           Type* feedback_type = TypeOfSpeculativeOp(info->type_check());
           new_type = Type::Intersect(static_type, feedback_type, graph_zone());
         }
         break;
       }
 
+      case IrOpcode::kNumberAbs: {
+        new_type = op_typer_.NumberAbs(FeedbackTypeOf(node->InputAt(0)));
+        break;
+      }
+
       case IrOpcode::kPhi: {
         new_type = TypePhi(node);
         if (type != nullptr) {
           new_type = Weaken(node, type, new_type);
         }
-        // Recompute the phi representation based on the new type.
-        MachineRepresentation output =
-            GetOutputInfoForPhi(node, GetInfo(node)->truncation(), new_type);
-        ResetOutput(node, output);
         break;
       }
 
       case IrOpcode::kSelect: {
         new_type = TypeSelect(node);
-        // Recompute representation based on the new type.
-        MachineRepresentation output =
-            GetOutputInfoForPhi(node, GetInfo(node)->truncation(), new_type);
-        ResetOutput(node, output);
         break;
       }
 
       default:
         // Shortcut for operations that we do not handle.
         if (type == nullptr) {
           GetInfo(node)->set_feedback_type(NodeProperties::GetType(node));
           return true;
         }
         return false;
@@ skipping 77 matching lines @@
       VisitNode(node, info->truncation(), nullptr);
       TRACE("  ==> output ");
       PrintOutputInfo(info);
       TRACE("\n");
     }
   }
 
   void Run(SimplifiedLowering* lowering) {
     RunTruncationPropagationPhase();
 
-    // Run type propagation.
-    ResetNodeInfoState();
     RunTypePropagationPhase();
 
     // Run lowering and change insertion phase.
     TRACE("--{Simplified lowering phase}--\n");
     phase_ = LOWER;
     // Process nodes from the collected {nodes_} vector.
     for (NodeVector::iterator i = nodes_.begin(); i != nodes_.end(); ++i) {
       Node* node = *i;
       NodeInfo* info = GetInfo(node);
       TRACE(" visit #%d: %s\n", node->id(), node->op()->mnemonic());
@@ skipping 56 matching lines @@
         queue_.push(node);
         info->set_queued();
         TRACE("   added: ");
       } else {
         TRACE(" inqueue: ");
       }
       PrintTruncation(info->truncation());
     }
   }
 
-  bool lower() { return phase_ == LOWER; }
-  bool propagate() { return phase_ == PROPAGATE; }
+  bool lower() const { return phase_ == LOWER; }
+  bool retype() const { return phase_ == RETYPE; }
+  bool propagate() const { return phase_ == PROPAGATE; }
 
   void SetOutput(Node* node, MachineRepresentation representation,
                  TypeCheckKind type_check = TypeCheckKind::kNone) {
-    DCHECK(MachineRepresentationIsSubtype(GetInfo(node)->representation(),
-                                          representation));
-    ResetOutput(node, representation, type_check);
+    NodeInfo* const info = GetInfo(node);
+    switch (phase_) {
+      case PROPAGATE:
+        info->set_type_check(type_check);
+        break;
+      case RETYPE:
+        DCHECK_EQ(info->type_check(), type_check);
+        DCHECK(MachineRepresentationIsSubtype(info->representation(),
+                                              representation));

[Jarin, 2016/07/12 08:51:49]

I am not sure the subtyping check is really needed here. Convergence does not
really depend on this.

[Benedikt Meurer, 2016/07/12 09:43:48]

Done.

+        info->set_output(representation);
+        break;
+      case LOWER:
+        DCHECK_EQ(info->type_check(), type_check);
+        DCHECK(MachineRepresentationIsSubtype(info->representation(),
+                                              representation));

[Jarin, 2016/07/12 08:51:49]

In this case, the representation should also be the same, not just a subtype.
Otherwise, we could insert a wrong conversion.

[Benedikt Meurer, 2016/07/12 09:43:48]

Done.

+        break;
+    }
   }
 
   void ResetOutput(Node* node, MachineRepresentation representation,
                    TypeCheckKind type_check = TypeCheckKind::kNone) {
     NodeInfo* info = GetInfo(node);
     info->set_output(representation);
     info->set_type_check(type_check);
   }
 
   Type* GetUpperBound(Node* node) { return NodeProperties::GetType(node); }
@@ skipping 40 matching lines @@
       TRACE(" to ");
       PrintUseInfo(use);
       TRACE("\n");
       Node* n = changer_->GetRepresentationFor(
           input, input_info->representation(), TypeOf(input), node, use);
       node->ReplaceInput(index, n);
     }
   }
 
   void ProcessInput(Node* node, int index, UseInfo use) {
-    if (phase_ == PROPAGATE) {
-      EnqueueInput(node, index, use);
-    } else {
-      ConvertInput(node, index, use);
+    switch (phase_) {
+      case PROPAGATE:
+        EnqueueInput(node, index, use);
+        break;
+      case RETYPE:
+        break;
+      case LOWER:
+        ConvertInput(node, index, use);
+        break;
     }
   }
 
   void ProcessRemainingInputs(Node* node, int index) {
     DCHECK_GE(index, NodeProperties::PastValueIndex(node));
     DCHECK_GE(index, NodeProperties::PastContextIndex(node));
     for (int i = std::max(index, NodeProperties::FirstEffectIndex(node));
          i < NodeProperties::PastEffectIndex(node); ++i) {
       EnqueueInput(node, i);  // Effect inputs: just visit
     }
@@ skipping 88 matching lines @@
     VisitBinop(node, UseInfo::TruncatingWord32(), MachineRepresentation::kBit);
   }
   void VisitInt64Cmp(Node* node) {
     VisitBinop(node, UseInfo::TruncatingWord64(), MachineRepresentation::kBit);
   }
   void VisitUint64Cmp(Node* node) {
     VisitBinop(node, UseInfo::TruncatingWord64(), MachineRepresentation::kBit);
   }
 
   // Infer representation for phi-like nodes.
-  MachineRepresentation GetOutputInfoForPhi(Node* node, Truncation use,
-                                            Type* type = nullptr) {
+  MachineRepresentation GetOutputInfoForPhi(Node* node, Truncation use) {
     // Compute the representation.
-    if (type == nullptr) {
-      type = TypeOf(node);
-    }
+    Type* type = TypeOf(node);
     if (type->Is(Type::None())) {
       return MachineRepresentation::kNone;
     } else if (type->Is(Type::Signed32()) || type->Is(Type::Unsigned32())) {
       return MachineRepresentation::kWord32;
     } else if (use.TruncatesToWord32()) {
       return MachineRepresentation::kWord32;
     } else if (type->Is(Type::Boolean())) {
       return MachineRepresentation::kBit;
     } else if (type->Is(Type::Number())) {
       return MachineRepresentation::kFloat64;
@@ skipping 96 matching lines @@
     if (type->Is(Type::Signed32())) {
       return MachineSemantic::kInt32;
     } else if (type->Is(Type::Unsigned32())) {
       return MachineSemantic::kUint32;
     } else {
       return MachineSemantic::kAny;
     }
   }
 
   void VisitStateValues(Node* node) {
     if (phase_ == PROPAGATE) {

[Jarin, 2016/07/12 08:51:49]

if (propagate()) {

[Benedikt Meurer, 2016/07/12 09:43:48]

Done.

       for (int i = 0; i < node->InputCount(); i++) {
         EnqueueInput(node, i, UseInfo::Any());
       }
-    } else {
+    } else if (phase_ == LOWER) {

[Jarin, 2016/07/12 08:51:49]

} else if (lower()) {

[Benedikt Meurer, 2016/07/12 09:43:48]

Done.

       Zone* zone = jsgraph_->zone();
       ZoneVector<MachineType>* types =
           new (zone->New(sizeof(ZoneVector<MachineType>)))
               ZoneVector<MachineType>(node->InputCount(), zone);
       for (int i = 0; i < node->InputCount(); i++) {
         Node* input = node->InputAt(i);
         NodeInfo* input_info = GetInfo(input);
         MachineType machine_type(input_info->representation(),
                                  DeoptValueSemanticOf(TypeOf(input)));
         DCHECK(machine_type.representation() !=
@@ skipping 622 matching lines @@
       case IrOpcode::kNumberShiftRightLogical: {
         Type* rhs_type = GetUpperBound(node->InputAt(1));
         VisitBinop(node, UseInfo::TruncatingWord32(),
                    UseInfo::TruncatingWord32(), MachineRepresentation::kWord32);
         if (lower()) {
           lowering->DoShift(node, lowering->machine()->Word32Shr(), rhs_type);
         }
         return;
       }
       case IrOpcode::kNumberAbs: {
-        if (InputIs(node, Type::Unsigned32())) {
+        if (TypeOf(node->InputAt(0))->Is(Type::Unsigned32())) {
           VisitUnop(node, UseInfo::TruncatingWord32(),
                     MachineRepresentation::kWord32);
           if (lower()) DeferReplacement(node, node->InputAt(0));
-        } else if (InputIs(node, Type::Signed32())) {
+        } else if (TypeOf(node->InputAt(0))->Is(Type::Signed32())) {
           VisitUnop(node, UseInfo::TruncatingWord32(),
                     MachineRepresentation::kWord32);
           if (lower()) DeferReplacement(node, lowering->Int32Abs(node));
-        } else if (InputIs(node,
-                           type_cache_.kPositiveIntegerOrMinusZeroOrNaN)) {
+        } else if (TypeOf(node->InputAt(0))
+                       ->Is(type_cache_.kPositiveIntegerOrMinusZeroOrNaN)) {
           VisitUnop(node, UseInfo::TruncatingFloat64(),
                     MachineRepresentation::kFloat64);
           if (lower()) DeferReplacement(node, node->InputAt(0));
         } else {
           VisitUnop(node, UseInfo::TruncatingFloat64(),
                     MachineRepresentation::kFloat64);
           if (lower()) NodeProperties::ChangeOp(node, Float64Op(node));
         }
         return;
       }
@@ skipping 1667 matching lines @@
         isolate(), graph()->zone(), callable.descriptor(), 0, flags,
         Operator::kNoProperties);
     to_number_operator_.set(common()->Call(desc));
   }
   return to_number_operator_.get();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8