src/v8/src/compiler/verifier.cc

   1 // Copyright 2014 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/compiler/verifier.h"
   6
   7 #include "src/compiler/generic-algorithm.h"
   8 #include "src/compiler/generic-node-inl.h"
   9 #include "src/compiler/generic-node.h"
  10 #include "src/compiler/graph-inl.h"
  11 #include "src/compiler/graph.h"
  12 #include "src/compiler/node.h"
  13 #include "src/compiler/node-properties-inl.h"
  14 #include "src/compiler/node-properties.h"
  15 #include "src/compiler/opcodes.h"
  16 #include "src/compiler/operator.h"
  17
  18 namespace v8 {
  19 namespace internal {
  20 namespace compiler {
  21
  22
  23 static bool IsDefUseChainLinkPresent(Node* def, Node* use) {
  24   Node::Uses uses = def->uses();
  25   for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
  26     if (*it == use) return true;
  27   }
  28   return false;
  29 }
  30
  31
  32 static bool IsUseDefChainLinkPresent(Node* def, Node* use) {
  33   Node::Inputs inputs = use->inputs();
  34   for (Node::Inputs::iterator it = inputs.begin(); it != inputs.end(); ++it) {
  35     if (*it == def) return true;
  36   }
  37   return false;
  38 }
  39
  40
  41 class Verifier::Visitor : public NullNodeVisitor {
  42  public:
  43   explicit Visitor(Zone* zone)
  44       : reached_from_start(NodeSet::key_compare(),
  45                            NodeSet::allocator_type(zone)),
  46         reached_from_end(NodeSet::key_compare(),
  47                          NodeSet::allocator_type(zone)) {}
  48
  49   // Fulfills the PreNodeCallback interface.
  50   GenericGraphVisit::Control Pre(Node* node);
  51
  52   bool from_start;
  53   NodeSet reached_from_start;
  54   NodeSet reached_from_end;
  55 };
  56
  57
  58 GenericGraphVisit::Control Verifier::Visitor::Pre(Node* node) {
  59   int value_count = OperatorProperties::GetValueInputCount(node->op());
  60   int context_count = OperatorProperties::GetContextInputCount(node->op());
  61   int effect_count = OperatorProperties::GetEffectInputCount(node->op());
  62   int control_count = OperatorProperties::GetControlInputCount(node->op());
  63
  64   // Verify number of inputs matches up.
  65   int input_count = value_count + context_count + effect_count + control_count;
  66   CHECK_EQ(input_count, node->InputCount());
  67
  68   // Verify all value inputs actually produce a value.
  69   for (int i = 0; i < value_count; ++i) {
  70     Node* value = NodeProperties::GetValueInput(node, i);
  71     CHECK(OperatorProperties::HasValueOutput(value->op()));
  72     CHECK(IsDefUseChainLinkPresent(value, node));
  73     CHECK(IsUseDefChainLinkPresent(value, node));
  74   }
  75
  76   // Verify all context inputs are value nodes.
  77   for (int i = 0; i < context_count; ++i) {
  78     Node* context = NodeProperties::GetContextInput(node);
  79     CHECK(OperatorProperties::HasValueOutput(context->op()));
  80     CHECK(IsDefUseChainLinkPresent(context, node));
  81     CHECK(IsUseDefChainLinkPresent(context, node));
  82   }
  83
  84   // Verify all effect inputs actually have an effect.
  85   for (int i = 0; i < effect_count; ++i) {
  86     Node* effect = NodeProperties::GetEffectInput(node);
  87     CHECK(OperatorProperties::HasEffectOutput(effect->op()));
  88     CHECK(IsDefUseChainLinkPresent(effect, node));
  89     CHECK(IsUseDefChainLinkPresent(effect, node));
  90   }
  91
  92   // Verify all control inputs are control nodes.
  93   for (int i = 0; i < control_count; ++i) {
  94     Node* control = NodeProperties::GetControlInput(node, i);
  95     CHECK(OperatorProperties::HasControlOutput(control->op()));
  96     CHECK(IsDefUseChainLinkPresent(control, node));
  97     CHECK(IsUseDefChainLinkPresent(control, node));
  98   }
  99
 100   // Verify all successors are projections if multiple value outputs exist.
 101   if (OperatorProperties::GetValueOutputCount(node->op()) > 1) {
 102     Node::Uses uses = node->uses();
 103     for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
 104       CHECK(!NodeProperties::IsValueEdge(it.edge()) ||
 105             (*it)->opcode() == IrOpcode::kProjection ||
 106             (*it)->opcode() == IrOpcode::kParameter);
 107     }
 108   }
 109
 110   switch (node->opcode()) {
 111     case IrOpcode::kStart:
 112       // Start has no inputs.
 113       CHECK_EQ(0, input_count);
 114       break;
 115     case IrOpcode::kEnd:
 116       // End has no outputs.
 117       CHECK(!OperatorProperties::HasValueOutput(node->op()));
 118       CHECK(!OperatorProperties::HasEffectOutput(node->op()));
 119       CHECK(!OperatorProperties::HasControlOutput(node->op()));
 120       break;
 121     case IrOpcode::kDead:
 122       // Dead is never connected to the graph.
 123       UNREACHABLE();
 124     case IrOpcode::kBranch: {
 125       // Branch uses are IfTrue and IfFalse.
 126       Node::Uses uses = node->uses();
 127       bool got_true = false, got_false = false;
 128       for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
 129         CHECK(((*it)->opcode() == IrOpcode::kIfTrue && !got_true) ||
 130               ((*it)->opcode() == IrOpcode::kIfFalse && !got_false));
 131         if ((*it)->opcode() == IrOpcode::kIfTrue) got_true = true;
 132         if ((*it)->opcode() == IrOpcode::kIfFalse) got_false = true;
 133       }
 134       // TODO(rossberg): Currently fails for various tests.
 135       // CHECK(got_true && got_false);
 136       break;
 137     }
 138     case IrOpcode::kIfTrue:
 139     case IrOpcode::kIfFalse:
 140       CHECK_EQ(IrOpcode::kBranch,
 141                NodeProperties::GetControlInput(node, 0)->opcode());
 142       break;
 143     case IrOpcode::kLoop:
 144     case IrOpcode::kMerge:
 145       break;
 146     case IrOpcode::kReturn:
 147       // TODO(rossberg): check successor is End
 148       break;
 149     case IrOpcode::kThrow:
 150       // TODO(rossberg): what are the constraints on these?
 151       break;
 152     case IrOpcode::kParameter: {
 153       // Parameters have the start node as inputs.
 154       CHECK_EQ(1, input_count);
 155       CHECK_EQ(IrOpcode::kStart,
 156                NodeProperties::GetValueInput(node, 0)->opcode());
 157       // Parameter has an input that produces enough values.
 158       int index = static_cast<Operator1<int>*>(node->op())->parameter();
 159       Node* input = NodeProperties::GetValueInput(node, 0);
 160       // Currently, parameter indices start at -1 instead of 0.
 161       CHECK_GT(OperatorProperties::GetValueOutputCount(input->op()), index + 1);
 162       break;
 163     }
 164     case IrOpcode::kInt32Constant:
 165     case IrOpcode::kInt64Constant:
 166     case IrOpcode::kFloat64Constant:
 167     case IrOpcode::kExternalConstant:
 168     case IrOpcode::kNumberConstant:
 169     case IrOpcode::kHeapConstant:
 170       // Constants have no inputs.
 171       CHECK_EQ(0, input_count);
 172       break;
 173     case IrOpcode::kPhi: {
 174       // Phi input count matches parent control node.
 175       CHECK_EQ(1, control_count);
 176       Node* control = NodeProperties::GetControlInput(node, 0);
 177       CHECK_EQ(value_count,
 178                OperatorProperties::GetControlInputCount(control->op()));
 179       break;
 180     }
 181     case IrOpcode::kEffectPhi: {
 182       // EffectPhi input count matches parent control node.
 183       CHECK_EQ(1, control_count);
 184       Node* control = NodeProperties::GetControlInput(node, 0);
 185       CHECK_EQ(effect_count,
 186                OperatorProperties::GetControlInputCount(control->op()));
 187       break;
 188     }
 189     case IrOpcode::kLazyDeoptimization:
 190       // TODO(jarin): what are the constraints on these?
 191       break;
 192     case IrOpcode::kDeoptimize:
 193       // TODO(jarin): what are the constraints on these?
 194       break;
 195     case IrOpcode::kFrameState:
 196       // TODO(jarin): what are the constraints on these?
 197       break;
 198     case IrOpcode::kCall:
 199       // TODO(rossberg): what are the constraints on these?
 200       break;
 201     case IrOpcode::kContinuation:
 202       // TODO(jarin): what are the constraints on these?
 203       break;
 204     case IrOpcode::kProjection: {
 205       // Projection has an input that produces enough values.
 206       int index = static_cast<Operator1<int>*>(node->op())->parameter();
 207       Node* input = NodeProperties::GetValueInput(node, 0);
 208       CHECK_GT(OperatorProperties::GetValueOutputCount(input->op()), index);
 209       break;
 210     }
 211     default:
 212       // TODO(rossberg): Check other node kinds.
 213       break;
 214   }
 215
 216   if (from_start) {
 217     reached_from_start.insert(node);
 218   } else {
 219     reached_from_end.insert(node);
 220   }
 221
 222   return GenericGraphVisit::CONTINUE;
 223 }
 224
 225
 226 void Verifier::Run(Graph* graph) {
 227   Visitor visitor(graph->zone());
 228
 229   CHECK_NE(NULL, graph->start());
 230   visitor.from_start = true;
 231   graph->VisitNodeUsesFromStart(&visitor);
 232   CHECK_NE(NULL, graph->end());
 233   visitor.from_start = false;
 234   graph->VisitNodeInputsFromEnd(&visitor);
 235
 236   // All control nodes reachable from end are reachable from start.
 237   for (NodeSet::iterator it = visitor.reached_from_end.begin();
 238        it != visitor.reached_from_end.end(); ++it) {
 239     CHECK(!NodeProperties::IsControl(*it) ||
 240           visitor.reached_from_start.count(*it));
 241   }
 242 }
 243 }
 244 }
 245 }  // namespace v8::internal::compiler