Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(683)

Unified Diff: src/compiler/verifier.cc

Issue 426233002: Land the Fan (disabled) (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Review feedback, rebase and "git cl format" Created 6 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/compiler/verifier.h ('k') | src/compiler/x64/code-generator-x64.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/compiler/verifier.cc
diff --git a/src/compiler/verifier.cc b/src/compiler/verifier.cc
new file mode 100644
index 0000000000000000000000000000000000000000..64eb72e7d645b2352e02c1d2e858d2817fba1269
--- /dev/null
+++ b/src/compiler/verifier.cc
@@ -0,0 +1,232 @@
+// 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/verifier.h"
+
+#include "src/compiler/generic-algorithm.h"
+#include "src/compiler/generic-node-inl.h"
+#include "src/compiler/generic-node.h"
+#include "src/compiler/graph-inl.h"
+#include "src/compiler/graph.h"
+#include "src/compiler/node.h"
+#include "src/compiler/node-properties-inl.h"
+#include "src/compiler/node-properties.h"
+#include "src/compiler/opcodes.h"
+#include "src/compiler/operator.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+
+static bool IsDefUseChainLinkPresent(Node* def, Node* use) {
+ Node::Uses uses = def->uses();
+ for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
+ if (*it == use) return true;
+ }
+ return false;
+}
+
+
+static bool IsUseDefChainLinkPresent(Node* def, Node* use) {
+ Node::Inputs inputs = use->inputs();
+ for (Node::Inputs::iterator it = inputs.begin(); it != inputs.end(); ++it) {
+ if (*it == def) return true;
+ }
+ return false;
+}
+
+
+class Verifier::Visitor : public NullNodeVisitor {
+ public:
+ explicit Visitor(Zone* zone)
+ : reached_from_start(NodeSet::key_compare(),
+ NodeSet::allocator_type(zone)),
+ reached_from_end(NodeSet::key_compare(),
+ NodeSet::allocator_type(zone)) {}
+
+ // Fulfills the PreNodeCallback interface.
+ GenericGraphVisit::Control Pre(Node* node);
+
+ bool from_start;
+ NodeSet reached_from_start;
+ NodeSet reached_from_end;
+};
+
+
+GenericGraphVisit::Control Verifier::Visitor::Pre(Node* node) {
+ int value_count = NodeProperties::GetValueInputCount(node);
+ int context_count = NodeProperties::GetContextInputCount(node);
+ int effect_count = NodeProperties::GetEffectInputCount(node);
+ int control_count = NodeProperties::GetControlInputCount(node);
+
+ // Verify number of inputs matches up.
+ int input_count = value_count + context_count + effect_count + control_count;
+ CHECK_EQ(input_count, node->InputCount());
+
+ // Verify all value inputs actually produce a value.
+ for (int i = 0; i < value_count; ++i) {
+ Node* value = NodeProperties::GetValueInput(node, i);
+ CHECK(NodeProperties::HasValueOutput(value));
+ CHECK(IsDefUseChainLinkPresent(value, node));
+ CHECK(IsUseDefChainLinkPresent(value, node));
+ }
+
+ // Verify all context inputs are value nodes.
+ for (int i = 0; i < context_count; ++i) {
+ Node* context = NodeProperties::GetContextInput(node);
+ CHECK(NodeProperties::HasValueOutput(context));
+ CHECK(IsDefUseChainLinkPresent(context, node));
+ CHECK(IsUseDefChainLinkPresent(context, node));
+ }
+
+ // Verify all effect inputs actually have an effect.
+ for (int i = 0; i < effect_count; ++i) {
+ Node* effect = NodeProperties::GetEffectInput(node);
+ CHECK(NodeProperties::HasEffectOutput(effect));
+ CHECK(IsDefUseChainLinkPresent(effect, node));
+ CHECK(IsUseDefChainLinkPresent(effect, node));
+ }
+
+ // Verify all control inputs are control nodes.
+ for (int i = 0; i < control_count; ++i) {
+ Node* control = NodeProperties::GetControlInput(node, i);
+ CHECK(NodeProperties::HasControlOutput(control));
+ CHECK(IsDefUseChainLinkPresent(control, node));
+ CHECK(IsUseDefChainLinkPresent(control, node));
+ }
+
+ // Verify all successors are projections if multiple value outputs exist.
+ if (NodeProperties::GetValueOutputCount(node) > 1) {
+ Node::Uses uses = node->uses();
+ for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
+ CHECK(!NodeProperties::IsValueEdge(it.edge()) ||
+ (*it)->opcode() == IrOpcode::kProjection);
+ }
+ }
+
+ switch (node->opcode()) {
+ case IrOpcode::kStart:
+ // Start has no inputs.
+ CHECK_EQ(0, input_count);
+ break;
+ case IrOpcode::kEnd:
+ // End has no outputs.
+ CHECK(!NodeProperties::HasValueOutput(node));
+ CHECK(!NodeProperties::HasEffectOutput(node));
+ CHECK(!NodeProperties::HasControlOutput(node));
+ break;
+ case IrOpcode::kDead:
+ // Dead is never connected to the graph.
+ UNREACHABLE();
+ case IrOpcode::kBranch: {
+ // Branch uses are IfTrue and IfFalse.
+ Node::Uses uses = node->uses();
+ bool got_true = false, got_false = false;
+ for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
+ CHECK(((*it)->opcode() == IrOpcode::kIfTrue && !got_true) ||
+ ((*it)->opcode() == IrOpcode::kIfFalse && !got_false));
+ if ((*it)->opcode() == IrOpcode::kIfTrue) got_true = true;
+ if ((*it)->opcode() == IrOpcode::kIfFalse) got_false = true;
+ }
+ // TODO(rossberg): Currently fails for various tests.
+ // CHECK(got_true && got_false);
+ break;
+ }
+ case IrOpcode::kIfTrue:
+ case IrOpcode::kIfFalse:
+ CHECK_EQ(IrOpcode::kBranch,
+ NodeProperties::GetControlInput(node, 0)->opcode());
+ break;
+ case IrOpcode::kLoop:
+ case IrOpcode::kMerge:
+ break;
+ case IrOpcode::kReturn:
+ // TODO(rossberg): check successor is End
+ break;
+ case IrOpcode::kThrow:
+ // TODO(rossberg): what are the constraints on these?
+ break;
+ case IrOpcode::kParameter:
+ // Parameters have no inputs.
+ CHECK_EQ(0, input_count);
+ break;
+ case IrOpcode::kInt32Constant:
+ case IrOpcode::kInt64Constant:
+ case IrOpcode::kFloat64Constant:
+ case IrOpcode::kExternalConstant:
+ case IrOpcode::kNumberConstant:
+ case IrOpcode::kHeapConstant:
+ // Constants have no inputs.
+ CHECK_EQ(0, input_count);
+ break;
+ case IrOpcode::kPhi: {
+ // Phi input count matches parent control node.
+ CHECK_EQ(1, control_count);
+ Node* control = NodeProperties::GetControlInput(node, 0);
+ CHECK_EQ(value_count, NodeProperties::GetControlInputCount(control));
+ break;
+ }
+ case IrOpcode::kEffectPhi: {
+ // EffectPhi input count matches parent control node.
+ CHECK_EQ(1, control_count);
+ Node* control = NodeProperties::GetControlInput(node, 0);
+ CHECK_EQ(effect_count, NodeProperties::GetControlInputCount(control));
+ break;
+ }
+ case IrOpcode::kLazyDeoptimization:
+ // TODO(jarin): what are the constraints on these?
+ break;
+ case IrOpcode::kDeoptimize:
+ // TODO(jarin): what are the constraints on these?
+ break;
+ case IrOpcode::kFrameState:
+ // TODO(jarin): what are the constraints on these?
+ break;
+ case IrOpcode::kCall:
+ // TODO(rossberg): what are the constraints on these?
+ break;
+ case IrOpcode::kContinuation:
+ // TODO(jarin): what are the constraints on these?
+ break;
+ case IrOpcode::kProjection: {
+ // Projection has an input that produces enough values.
+ int index = static_cast<Operator1<int>*>(node->op())->parameter();
+ Node* input = NodeProperties::GetValueInput(node, 0);
+ CHECK_GT(NodeProperties::GetValueOutputCount(input), index);
+ break;
+ }
+ default:
+ // TODO(rossberg): Check other node kinds.
+ break;
+ }
+
+ if (from_start) {
+ reached_from_start.insert(node);
+ } else {
+ reached_from_end.insert(node);
+ }
+
+ return GenericGraphVisit::CONTINUE;
+}
+
+
+void Verifier::Run(Graph* graph) {
+ Visitor visitor(graph->zone());
+
+ visitor.from_start = true;
+ graph->VisitNodeUsesFromStart(&visitor);
+ visitor.from_start = false;
+ graph->VisitNodeInputsFromEnd(&visitor);
+
+ // All control nodes reachable from end are reachable from start.
+ for (NodeSet::iterator it = visitor.reached_from_end.begin();
+ it != visitor.reached_from_end.end(); ++it) {
+ CHECK(!NodeProperties::IsControl(*it) ||
+ visitor.reached_from_start.count(*it));
+ }
+}
+}
+}
+} // namespace v8::internal::compiler
« no previous file with comments | « src/compiler/verifier.h ('k') | src/compiler/x64/code-generator-x64.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698