[turbofan] Checking monotonicity of representation inference outputs and inputs.

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/base/bits.h"
 #include "src/code-factory.h"
@@ skipping 136 matching lines @@
 
 UseInfo UseInfoForBasePointer(const FieldAccess& access) {
   return access.tag() != 0 ? UseInfo::AnyTagged() : UseInfo::PointerInt();
 }
 
 
 UseInfo UseInfoForBasePointer(const ElementAccess& access) {
   return access.tag() != 0 ? UseInfo::AnyTagged() : UseInfo::PointerInt();
 }
 
+
+#ifdef DEBUG
+// Helpers for monotonicity checking.
+
+bool MachineTypeIsSubtype(MachineType t1, MachineType t2) {
+  switch (t1) {
+    case kMachNone:
+      return true;
+    case kTypeBool:
+      return t2 == kTypeBool || t2 == kTypeNumber || t2 == kTypeAny;
+    case kTypeInt32:
+      return t2 == kTypeInt32 || t2 == kTypeNumber || t2 == kTypeAny;
+    case kTypeUint32:
+      return t2 == kTypeUint32 || t2 == kTypeNumber || t2 == kTypeAny;
+    case kTypeInt64:
+      return t2 == kTypeInt64;
+    case kTypeUint64:
+      return t2 == kTypeUint64;
+    case kTypeNumber:
+      return t2 == kTypeNumber || t2 == kTypeAny;
+    case kTypeAny:
+      return t2 == kTypeAny;
+    default:
+      break;
+  }
+  UNREACHABLE();
+  return false;
+}
+
+
+bool MachineRepresentationIsSubtype(MachineType r1, MachineType r2) {
+  switch (r1) {
+    case kMachNone:
+      return true;
+    case kRepBit:
+      return r2 == kRepBit || r2 == kRepTagged;
+    case kRepWord8:
+      return r2 == kRepWord8 || r2 == kRepWord16 || r2 == kRepWord32 ||
+             r2 == kRepWord64 || r2 == kRepFloat32 || r2 == kRepFloat64 ||
+             r2 == kRepTagged;
+    case kRepWord16:
+      return r2 == kRepWord16 || r2 == kRepWord32 || r2 == kRepWord64 ||
+             r2 == kRepFloat32 || r2 == kRepFloat64 || r2 == kRepTagged;
+    case kRepWord32:
+      return r2 == kRepWord32 || r2 == kRepWord64 || r2 == kRepFloat64 ||
+             r2 == kRepTagged;
+    case kRepWord64:
+      return r2 == kRepWord64;
+    case kRepFloat32:
+      return r2 == kRepFloat32 || r2 == kRepFloat64 || r2 == kRepTagged;
+    case kRepFloat64:
+      return r2 == kRepFloat64 || r2 == kRepTagged;
+    case kRepTagged:
+      return r2 == kRepTagged;
+    default:
+      break;
+  }
+  UNREACHABLE();
+  return false;
+}
+
+
+bool MachineTypeRepIsSubtype(MachineTypeUnion m1, MachineTypeUnion m2) {
+  return MachineTypeIsSubtype(static_cast<MachineType>(m1 & kTypeMask),
+                              static_cast<MachineType>(m2 & kTypeMask)) &&
+         MachineRepresentationIsSubtype(
+             static_cast<MachineType>(m1 & kRepMask),
+             static_cast<MachineType>(m2 & kRepMask));
+}
+
+
+class InputUseInfos {
+ public:
+  explicit InputUseInfos(Zone* zone) : input_use_infos_(zone) {}
+
+  void SetAndCheckInput(Node* node, int index, UseInfo use_info) {
+    if (input_use_infos_.empty()) {
+      input_use_infos_.resize(node->InputCount(), UseInfo::None());
+    }
+    // Check that the new use informatin is a super-type of the old
+    // one.
+    CHECK(IsUseLessGeneral(input_use_infos_[index], use_info));
+    input_use_infos_[index] = use_info;
+  }
+
+ private:
+  ZoneVector<UseInfo> input_use_infos_;
+
+  static bool IsUseLessGeneral(UseInfo use1, UseInfo use2) {
+    return MachineRepresentationIsSubtype(use1.preferred(), use2.preferred()) &&
+           use1.truncation().IsLessGeneralThan(use2.truncation());
+  }
+};
+
+#endif  // DEBUG
+
 }  // namespace
 
 
 class RepresentationSelector {
  public:
   // Information for each node tracked during the fixpoint.
   class NodeInfo {
    public:
     // Adds new use to the node. Returns true if something has changed
     // and the node has to be requeued.
@@ skipping 17 matching lines @@
     MachineTypeUnion output_ = kMachNone;  // Output type of the node.
     Truncation truncation_ = Truncation::None();  // Information about uses.
   };
 
   RepresentationSelector(JSGraph* jsgraph, Zone* zone,
                          RepresentationChanger* changer,
                          SourcePositionTable* source_positions)
       : jsgraph_(jsgraph),
         count_(jsgraph->graph()->NodeCount()),
         info_(count_, zone),
+#ifdef DEBUG
+        node_input_use_infos_(count_, InputUseInfos(zone), zone),
+#endif
         nodes_(zone),
         replacements_(zone),
         phase_(PROPAGATE),
         changer_(changer),
         queue_(zone),
         source_positions_(source_positions),
-        type_cache_(TypeCache::Get()) {}
+        type_cache_(TypeCache::Get()) {
+  }
 
   void Run(SimplifiedLowering* lowering) {
     // Run propagation phase to a fixpoint.
     TRACE("--{Propagation phase}--\n");
     phase_ = PROPAGATE;
-    Enqueue(jsgraph_->graph()->end());
+    EnqueueInitial(jsgraph_->graph()->end());
     // Process nodes from the queue until it is empty.
     while (!queue_.empty()) {
       Node* node = queue_.front();
       NodeInfo* info = GetInfo(node);
       queue_.pop();
       info->set_queued(false);
       TRACE(" visit #%d: %s\n", node->id(), node->op()->mnemonic());
       VisitNode(node, info->truncation(), NULL);
       TRACE("  ==> output ");
       PrintInfo(info->output_type());
@@ skipping 21 matching lines @@
       Node* replacement = *(++i);
       node->ReplaceUses(replacement);
       // We also need to replace the node in the rest of the vector.
       for (NodeVector::iterator j = i + 1; j != replacements_.end(); ++j) {
         ++j;
         if (*j == node) *j = replacement;
       }
     }
   }
 
-  // Enqueue {node} if the {use} contains new information for that node.
-  // Add {node} to {nodes_} if this is the first time it's been visited.
-  void Enqueue(Node* node, UseInfo use_info = UseInfo::None()) {
+  void EnqueueInitial(Node* node) {
+    NodeInfo* info = GetInfo(node);
+    info->set_visited();
+    info->set_queued(true);
+    nodes_.push_back(node);
+    queue_.push(node);
+  }
+
+  // Enqueue {use_node}'s {index} input if the {use} contains new information
+  // for that input node. Add the input to {nodes_} if this is the first time
+  // it's been visited.
+  void EnqueueInput(Node* use_node, int index,
+                    UseInfo use_info = UseInfo::None()) {
+    Node* node = use_node->InputAt(index);
     if (phase_ != PROPAGATE) return;
     NodeInfo* info = GetInfo(node);
+#ifdef DEBUG
+    // Check monotonicity of input requirements.
+    node_input_use_infos_[use_node->id()].SetAndCheckInput(use_node, index,
+                                                           use_info);
+#endif  // DEBUG
     if (!info->visited()) {
       // First visit of this node.
       info->set_visited();
       info->set_queued(true);
       nodes_.push_back(node);
       queue_.push(node);
       TRACE("  initial: ");
       info->AddUse(use_info);
       PrintTruncation(info->truncation());
       return;
@@ skipping 14 matching lines @@
   }
 
   bool lower() { return phase_ == LOWER; }
 
   void SetOutput(Node* node, MachineTypeUnion output) {
     // Every node should have at most one output representation. Note that
     // phis can have 0, if they have not been used in a representation-inducing
     // instruction.
     DCHECK((output & kRepMask) == 0 ||
            base::bits::IsPowerOfTwo32(output & kRepMask));
-    GetInfo(node)->set_output_type(output);
+    NodeInfo* info = GetInfo(node);
+    DCHECK(MachineTypeRepIsSubtype(info->output_type(), output));
+    info->set_output_type(output);
   }
 
   bool BothInputsAre(Node* node, Type* type) {
     DCHECK_EQ(2, node->InputCount());
     return NodeProperties::GetType(node->InputAt(0))->Is(type) &&
            NodeProperties::GetType(node->InputAt(1))->Is(type);
   }
 
-  void EnqueueInputUse(Node* node, int index, UseInfo use) {
-    Enqueue(node->InputAt(index), use);
-  }
-
   void ConvertInput(Node* node, int index, UseInfo use) {
     Node* input = node->InputAt(index);
     // In the change phase, insert a change before the use if necessary.
     if (use.preferred() == kMachNone)
       return;  // No input requirement on the use.
     MachineTypeUnion output = GetInfo(input)->output_type();
     if ((output & kRepMask) != use.preferred()) {
       // Output representation doesn't match usage.
       TRACE("  change: #%d:%s(@%d #%d:%s) ", node->id(), node->op()->mnemonic(),
             index, input->id(), input->op()->mnemonic());
       TRACE(" from ");
       PrintInfo(output);
       TRACE(" to ");
       PrintUseInfo(use);
       TRACE("\n");
       Node* n = changer_->GetRepresentationFor(input, output, use.preferred(),
                                                use.truncation());
       node->ReplaceInput(index, n);
     }
   }
 
   void ProcessInput(Node* node, int index, UseInfo use) {
     if (phase_ == PROPAGATE) {
-      EnqueueInputUse(node, index, use);
+      EnqueueInput(node, index, use);
     } else {
       ConvertInput(node, index, use);
     }
   }
 
   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) {
-      Enqueue(node->InputAt(i));  // Effect inputs: just visit
+      EnqueueInput(node, i);  // Effect inputs: just visit
     }
     for (int i = std::max(index, NodeProperties::FirstControlIndex(node));
          i < NodeProperties::PastControlIndex(node); ++i) {
-      Enqueue(node->InputAt(i));  // Control inputs: just visit
+      EnqueueInput(node, i);  // Control inputs: just visit
     }
   }
 
   // The default, most general visitation case. For {node}, process all value,
   // context, frame state, effect, and control inputs, assuming that value
   // inputs should have {kRepTagged} representation and can observe all output
   // values {kTypeAny}.
   void VisitInputs(Node* node) {
     int tagged_count = node->op()->ValueInputCount() +
                        OperatorProperties::GetContextInputCount(node->op());
     // Visit value and context inputs as tagged.
     for (int i = 0; i < tagged_count; i++) {
       ProcessInput(node, i, UseInfo::AnyTagged());
     }
     // Only enqueue other inputs (framestates, effects, control).
     for (int i = tagged_count; i < node->InputCount(); i++) {
-      Enqueue(node->InputAt(i));
+      EnqueueInput(node, i);
     }
-    // Assume the output is tagged.
-    SetOutput(node, kMachAnyTagged);
   }
 
   // Helper for binops of the R x L -> O variety.
   void VisitBinop(Node* node, UseInfo left_use, UseInfo right_use,
                   MachineTypeUnion output) {
     DCHECK_EQ(2, node->op()->ValueInputCount());
     ProcessInput(node, 0, left_use);
     ProcessInput(node, 1, right_use);
     for (int i = 2; i < node->InputCount(); i++) {
-      Enqueue(node->InputAt(i));
+      EnqueueInput(node, i);
     }
     SetOutput(node, output);
   }
 
   // Helper for binops of the I x I -> O variety.
   void VisitBinop(Node* node, UseInfo input_use, MachineTypeUnion output) {
     VisitBinop(node, input_use, input_use, output);
   }
 
   // Helper for unops of the I -> O variety.
@@ skipping 137 matching lines @@
     if (sig->return_count() > 0) {
       SetOutput(node, desc->GetMachineSignature()->GetReturn());
     } else {
       SetOutput(node, kMachAnyTagged);
     }
   }
 
   void VisitStateValues(Node* node) {
     if (phase_ == PROPAGATE) {
       for (int i = 0; i < node->InputCount(); i++) {
-        Enqueue(node->InputAt(i), UseInfo::Any());
+        EnqueueInput(node, i, UseInfo::Any());
       }
     } else {
       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++) {
         MachineTypeUnion input_type = GetInfo(node->InputAt(i))->output_type();
         (*types)[i] = static_cast<MachineType>(input_type);
       }
@@ skipping 69 matching lines @@
         return VisitLeaf(node, kRepFloat64);
       case IrOpcode::kExternalConstant:
         return VisitLeaf(node, kMachPtr);
       case IrOpcode::kNumberConstant:
         return VisitLeaf(node, kRepTagged);
       case IrOpcode::kHeapConstant:
         return VisitLeaf(node, kRepTagged);
 
       case IrOpcode::kBranch:
         ProcessInput(node, 0, UseInfo::Bool());
-        Enqueue(NodeProperties::GetControlInput(node, 0));
+        EnqueueInput(node, NodeProperties::FirstControlIndex(node));
         break;
       case IrOpcode::kSwitch:
         ProcessInput(node, 0, UseInfo::TruncatingWord32());
-        Enqueue(NodeProperties::GetControlInput(node, 0));
+        EnqueueInput(node, NodeProperties::FirstControlIndex(node));
         break;
       case IrOpcode::kSelect:
         return VisitSelect(node, truncation, lowering);
       case IrOpcode::kPhi:
         return VisitPhi(node, truncation, lowering);
       case IrOpcode::kCall:
         return VisitCall(node, lowering);
 
 //------------------------------------------------------------------
 // JavaScript operators.
@@ skipping 466 matching lines @@
         return VisitBinop(node, UseInfo::Float64(), UseInfo::TruncatingWord32(),
                           kMachFloat64);
       case IrOpcode::kLoadStackPointer:
       case IrOpcode::kLoadFramePointer:
         return VisitLeaf(node, kMachPtr);
       case IrOpcode::kStateValues:
         VisitStateValues(node);
         break;
       default:
         VisitInputs(node);
+        // Assume the output is tagged.
+        SetOutput(node, kMachAnyTagged);
         break;
     }
   }
 
   void DeferReplacement(Node* node, Node* replacement) {
     TRACE("defer replacement #%d:%s with #%d:%s\n", node->id(),
           node->op()->mnemonic(), replacement->id(),
           replacement->op()->mnemonic());
 
     if (replacement->id() < count_ &&
@@ skipping 30 matching lines @@
     if (FLAG_trace_representation) {
       OFStream os(stdout);
       os << info.preferred() << ":" << info.truncation().description();
     }
   }
 
  private:
   JSGraph* jsgraph_;
   size_t const count_;              // number of nodes in the graph
   ZoneVector<NodeInfo> info_;       // node id -> usage information
+#ifdef DEBUG
+  ZoneVector<InputUseInfos> node_input_use_infos_;  // Debug information about
+                                                    // requirements on inputs.
+#endif                                              // DEBUG
   NodeVector nodes_;                // collected nodes
   NodeVector replacements_;         // replacements to be done after lowering
   Phase phase_;                     // current phase of algorithm
   RepresentationChanger* changer_;  // for inserting representation changes
   ZoneQueue<Node*> queue_;          // queue for traversing the graph
   // TODO(danno): RepresentationSelector shouldn't know anything about the
   // source positions table, but must for now since there currently is no other
   // way to pass down source position information to nodes created during
   // lowering. Once this phase becomes a vanilla reducer, it should get source
   // position information via the SourcePositionWrapper like all other reducers.
@@ skipping 443 matching lines @@
   ReplaceEffectUses(node, comparison);
   node->ReplaceInput(0, comparison);
   node->ReplaceInput(1, jsgraph()->SmiConstant(EQUAL));
   node->TrimInputCount(2);
   NodeProperties::ChangeOp(node, machine()->IntLessThanOrEqual());
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8