17d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// Copyright 2014 the V8 project authors. All rights reserved. 27d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// Use of this source code is governed by a BSD-style license that can be 37d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// found in the LICENSE file. 47d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 57d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/verifier.h" 67d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 7a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org#include <deque> 8a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org#include <queue> 9a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 107d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/generic-algorithm.h" 117d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/generic-node-inl.h" 127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/generic-node.h" 137d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/graph-inl.h" 147d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/graph.h" 157d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/node.h" 167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/node-properties-inl.h" 177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/node-properties.h" 187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/opcodes.h" 197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/operator.h" 20a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org#include "src/compiler/schedule.h" 21a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org#include "src/data-flow.h" 227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgnamespace v8 { 247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgnamespace internal { 257d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgnamespace compiler { 267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstatic bool IsDefUseChainLinkPresent(Node* def, Node* use) { 297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node::Uses uses = def->uses(); 307d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) { 317d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (*it == use) return true; 327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 337d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return false; 347d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 357d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 367d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 377d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstatic bool IsUseDefChainLinkPresent(Node* def, Node* use) { 387d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node::Inputs inputs = use->inputs(); 397d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (Node::Inputs::iterator it = inputs.begin(); it != inputs.end(); ++it) { 407d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (*it == def) return true; 417d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 427d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return false; 437d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 447d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 457d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 467d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgclass Verifier::Visitor : public NullNodeVisitor { 477d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org public: 487d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org explicit Visitor(Zone* zone) 497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org : reached_from_start(NodeSet::key_compare(), 507d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org NodeSet::allocator_type(zone)), 517d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org reached_from_end(NodeSet::key_compare(), 527d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org NodeSet::allocator_type(zone)) {} 537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 547d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Fulfills the PreNodeCallback interface. 557d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org GenericGraphVisit::Control Pre(Node* node); 567d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 577d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org bool from_start; 587d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org NodeSet reached_from_start; 597d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org NodeSet reached_from_end; 607d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org}; 617d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 627d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 637d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgGenericGraphVisit::Control Verifier::Visitor::Pre(Node* node) { 648640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org int value_count = OperatorProperties::GetValueInputCount(node->op()); 658640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org int context_count = OperatorProperties::GetContextInputCount(node->op()); 66a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org int frame_state_count = 67a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org OperatorProperties::GetFrameStateInputCount(node->op()); 688640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org int effect_count = OperatorProperties::GetEffectInputCount(node->op()); 698640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org int control_count = OperatorProperties::GetControlInputCount(node->op()); 707d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 717d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Verify number of inputs matches up. 72a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org int input_count = value_count + context_count + frame_state_count + 73a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org effect_count + control_count; 747d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK_EQ(input_count, node->InputCount()); 757d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 7621d700eedcdd6570eff22ece724b63a5eefe78cbmachenbach@chromium.org // Verify that frame state has been inserted for the nodes that need it. 7721d700eedcdd6570eff22ece724b63a5eefe78cbmachenbach@chromium.org if (OperatorProperties::HasFrameStateInput(node->op())) { 7821d700eedcdd6570eff22ece724b63a5eefe78cbmachenbach@chromium.org Node* frame_state = NodeProperties::GetFrameStateInput(node); 799aaa825cf89e1bcfece269a453300ebf4a26d64dmachenbach@chromium.org CHECK(frame_state->opcode() == IrOpcode::kFrameState || 809aaa825cf89e1bcfece269a453300ebf4a26d64dmachenbach@chromium.org // kFrameState uses undefined as a sentinel. 819aaa825cf89e1bcfece269a453300ebf4a26d64dmachenbach@chromium.org (node->opcode() == IrOpcode::kFrameState && 829aaa825cf89e1bcfece269a453300ebf4a26d64dmachenbach@chromium.org frame_state->opcode() == IrOpcode::kHeapConstant)); 8321d700eedcdd6570eff22ece724b63a5eefe78cbmachenbach@chromium.org CHECK(IsDefUseChainLinkPresent(frame_state, node)); 8421d700eedcdd6570eff22ece724b63a5eefe78cbmachenbach@chromium.org CHECK(IsUseDefChainLinkPresent(frame_state, node)); 8521d700eedcdd6570eff22ece724b63a5eefe78cbmachenbach@chromium.org } 8621d700eedcdd6570eff22ece724b63a5eefe78cbmachenbach@chromium.org 877d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Verify all value inputs actually produce a value. 887d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (int i = 0; i < value_count; ++i) { 897d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node* value = NodeProperties::GetValueInput(node, i); 908640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org CHECK(OperatorProperties::HasValueOutput(value->op())); 917d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK(IsDefUseChainLinkPresent(value, node)); 927d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK(IsUseDefChainLinkPresent(value, node)); 937d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 947d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 957d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Verify all context inputs are value nodes. 967d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (int i = 0; i < context_count; ++i) { 977d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node* context = NodeProperties::GetContextInput(node); 988640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org CHECK(OperatorProperties::HasValueOutput(context->op())); 997d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK(IsDefUseChainLinkPresent(context, node)); 1007d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK(IsUseDefChainLinkPresent(context, node)); 1017d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1027d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1037d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Verify all effect inputs actually have an effect. 1047d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (int i = 0; i < effect_count; ++i) { 1057d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node* effect = NodeProperties::GetEffectInput(node); 1068640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org CHECK(OperatorProperties::HasEffectOutput(effect->op())); 1077d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK(IsDefUseChainLinkPresent(effect, node)); 1087d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK(IsUseDefChainLinkPresent(effect, node)); 1097d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1107d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1117d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Verify all control inputs are control nodes. 1127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (int i = 0; i < control_count; ++i) { 1137d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node* control = NodeProperties::GetControlInput(node, i); 1148640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org CHECK(OperatorProperties::HasControlOutput(control->op())); 1157d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK(IsDefUseChainLinkPresent(control, node)); 1167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK(IsUseDefChainLinkPresent(control, node)); 1177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Verify all successors are projections if multiple value outputs exist. 1208640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org if (OperatorProperties::GetValueOutputCount(node->op()) > 1) { 1217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node::Uses uses = node->uses(); 1227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) { 1237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK(!NodeProperties::IsValueEdge(it.edge()) || 1243e3d253bd8018d7627422bf55a5c7bb7e7d6ad7emachenbach@chromium.org (*it)->opcode() == IrOpcode::kProjection || 1253e3d253bd8018d7627422bf55a5c7bb7e7d6ad7emachenbach@chromium.org (*it)->opcode() == IrOpcode::kParameter); 1267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org switch (node->opcode()) { 1307d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kStart: 1317d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Start has no inputs. 1327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK_EQ(0, input_count); 1337d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 1347d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kEnd: 1357d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // End has no outputs. 1368640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org CHECK(!OperatorProperties::HasValueOutput(node->op())); 1378640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org CHECK(!OperatorProperties::HasEffectOutput(node->op())); 1388640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org CHECK(!OperatorProperties::HasControlOutput(node->op())); 1397d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 1407d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kDead: 1417d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Dead is never connected to the graph. 1427d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org UNREACHABLE(); 1437d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kBranch: { 1447d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Branch uses are IfTrue and IfFalse. 1457d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node::Uses uses = node->uses(); 1467d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org bool got_true = false, got_false = false; 1477d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) { 1487d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK(((*it)->opcode() == IrOpcode::kIfTrue && !got_true) || 1497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org ((*it)->opcode() == IrOpcode::kIfFalse && !got_false)); 1507d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if ((*it)->opcode() == IrOpcode::kIfTrue) got_true = true; 1517d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if ((*it)->opcode() == IrOpcode::kIfFalse) got_false = true; 1527d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // TODO(rossberg): Currently fails for various tests. 1547d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // CHECK(got_true && got_false); 1557d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 1567d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1577d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kIfTrue: 1587d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kIfFalse: 1597d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK_EQ(IrOpcode::kBranch, 1607d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org NodeProperties::GetControlInput(node, 0)->opcode()); 1617d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 1627d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kLoop: 1637d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kMerge: 1647d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 1657d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kReturn: 1667d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // TODO(rossberg): check successor is End 1677d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 1687d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kThrow: 1697d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // TODO(rossberg): what are the constraints on these? 1707d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 1713e3d253bd8018d7627422bf55a5c7bb7e7d6ad7emachenbach@chromium.org case IrOpcode::kParameter: { 1723e3d253bd8018d7627422bf55a5c7bb7e7d6ad7emachenbach@chromium.org // Parameters have the start node as inputs. 1733e3d253bd8018d7627422bf55a5c7bb7e7d6ad7emachenbach@chromium.org CHECK_EQ(1, input_count); 1743e3d253bd8018d7627422bf55a5c7bb7e7d6ad7emachenbach@chromium.org CHECK_EQ(IrOpcode::kStart, 1753e3d253bd8018d7627422bf55a5c7bb7e7d6ad7emachenbach@chromium.org NodeProperties::GetValueInput(node, 0)->opcode()); 1763e3d253bd8018d7627422bf55a5c7bb7e7d6ad7emachenbach@chromium.org // Parameter has an input that produces enough values. 1771af4d9551ad496a28c342004b1a4e2a3840228f7machenbach@chromium.org int index = OpParameter<int>(node); 1783e3d253bd8018d7627422bf55a5c7bb7e7d6ad7emachenbach@chromium.org Node* input = NodeProperties::GetValueInput(node, 0); 1793e3d253bd8018d7627422bf55a5c7bb7e7d6ad7emachenbach@chromium.org // Currently, parameter indices start at -1 instead of 0. 1808640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org CHECK_GT(OperatorProperties::GetValueOutputCount(input->op()), index + 1); 1817d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 1823e3d253bd8018d7627422bf55a5c7bb7e7d6ad7emachenbach@chromium.org } 1837d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kInt32Constant: 1847d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kInt64Constant: 1857d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kFloat64Constant: 1867d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kExternalConstant: 1877d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kNumberConstant: 1887d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kHeapConstant: 1897d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Constants have no inputs. 1907d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK_EQ(0, input_count); 1917d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 1927d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kPhi: { 1937d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Phi input count matches parent control node. 1947d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK_EQ(1, control_count); 1957d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node* control = NodeProperties::GetControlInput(node, 0); 1968640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org CHECK_EQ(value_count, 1978640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org OperatorProperties::GetControlInputCount(control->op())); 1987d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 1997d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2007d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kEffectPhi: { 2017d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // EffectPhi input count matches parent control node. 2027d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK_EQ(1, control_count); 2037d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node* control = NodeProperties::GetControlInput(node, 0); 2048640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org CHECK_EQ(effect_count, 2058640107360766c74218cf16d51b714b1f2138839machenbach@chromium.org OperatorProperties::GetControlInputCount(control->op())); 2067d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 2077d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2087d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kFrameState: 2097d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // TODO(jarin): what are the constraints on these? 2107d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 2117d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kCall: 2127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // TODO(rossberg): what are the constraints on these? 2137d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 2147d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org case IrOpcode::kProjection: { 2157d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Projection has an input that produces enough values. 216e20e19efeef112c26d0e63b1e5118e695b42d855machenbach@chromium.org size_t index = OpParameter<size_t>(node); 2177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node* input = NodeProperties::GetValueInput(node, 0); 218e20e19efeef112c26d0e63b1e5118e695b42d855machenbach@chromium.org CHECK_GT(OperatorProperties::GetValueOutputCount(input->op()), 219e20e19efeef112c26d0e63b1e5118e695b42d855machenbach@chromium.org static_cast<int>(index)); 2207d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 2217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org default: 2237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // TODO(rossberg): Check other node kinds. 2247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 2257d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (from_start) { 2287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org reached_from_start.insert(node); 2297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } else { 2307d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org reached_from_end.insert(node); 2317d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2337d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return GenericGraphVisit::CONTINUE; 2347d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 2357d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2367d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2377d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgvoid Verifier::Run(Graph* graph) { 2387d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Visitor visitor(graph->zone()); 2397d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2403e3d253bd8018d7627422bf55a5c7bb7e7d6ad7emachenbach@chromium.org CHECK_NE(NULL, graph->start()); 2417d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org visitor.from_start = true; 2427d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org graph->VisitNodeUsesFromStart(&visitor); 2433e3d253bd8018d7627422bf55a5c7bb7e7d6ad7emachenbach@chromium.org CHECK_NE(NULL, graph->end()); 2447d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org visitor.from_start = false; 2457d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org graph->VisitNodeInputsFromEnd(&visitor); 2467d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2477d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // All control nodes reachable from end are reachable from start. 2487d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (NodeSet::iterator it = visitor.reached_from_end.begin(); 2497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org it != visitor.reached_from_end.end(); ++it) { 2507d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CHECK(!NodeProperties::IsControl(*it) || 2517d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org visitor.reached_from_start.count(*it)); 2527d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 254a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 255a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 256a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.orgstatic bool HasDominatingDef(Schedule* schedule, Node* node, 257a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlock* container, BasicBlock* use_block, 258a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org int use_pos) { 259a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlock* block = use_block; 260a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org while (true) { 261a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org while (use_pos >= 0) { 262a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (block->nodes_[use_pos] == node) return true; 263a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org use_pos--; 264a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 265fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org block = block->dominator_; 266a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (block == NULL) break; 267a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org use_pos = static_cast<int>(block->nodes_.size()) - 1; 268a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (node == block->control_input_) return true; 269a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 270a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org return false; 271a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org} 272a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 273a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 274a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.orgstatic void CheckInputsDominate(Schedule* schedule, BasicBlock* block, 275a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Node* node, int use_pos) { 276a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org for (int j = OperatorProperties::GetValueInputCount(node->op()) - 1; j >= 0; 277a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org j--) { 278a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlock* use_block = block; 279a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (node->opcode() == IrOpcode::kPhi) { 280a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org use_block = use_block->PredecessorAt(j); 281a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org use_pos = static_cast<int>(use_block->nodes_.size()) - 1; 282a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 283a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Node* input = node->InputAt(j); 284a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (!HasDominatingDef(schedule, node->InputAt(j), block, use_block, 285a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org use_pos)) { 286a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org V8_Fatal(__FILE__, __LINE__, 287a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org "Node #%d:%s in B%d is not dominated by input@%d #%d:%s", 288a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org node->id(), node->op()->mnemonic(), block->id(), j, input->id(), 289a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org input->op()->mnemonic()); 290a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 291a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 292a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org} 293a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 294a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 295a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.orgvoid ScheduleVerifier::Run(Schedule* schedule) { 296a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org const int count = schedule->BasicBlockCount(); 297a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Zone tmp_zone(schedule->zone()->isolate()); 298a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Zone* zone = &tmp_zone; 299a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlock* start = schedule->start(); 300a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlockVector* rpo_order = schedule->rpo_order(); 301a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 302a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Verify the RPO order contains only blocks from this schedule. 303a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CHECK_GE(count, static_cast<int>(rpo_order->size())); 304a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); 305a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org ++b) { 306a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CHECK_EQ((*b), schedule->GetBlockById((*b)->id())); 307a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 308a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 309a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Verify RPO numbers of blocks. 310a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CHECK_EQ(start, rpo_order->at(0)); // Start should be first. 311a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org for (size_t b = 0; b < rpo_order->size(); b++) { 312a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlock* block = rpo_order->at(b); 313a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CHECK_EQ(static_cast<int>(b), block->rpo_number_); 314fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org BasicBlock* dom = block->dominator_; 315a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (b == 0) { 316a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // All blocks except start should have a dominator. 317a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CHECK_EQ(NULL, dom); 318a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } else { 319a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Check that the immediate dominator appears somewhere before the block. 320a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CHECK_NE(NULL, dom); 321a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CHECK_LT(dom->rpo_number_, block->rpo_number_); 322a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 323a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 324a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 325a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Verify that all blocks reachable from start are in the RPO. 326fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org BoolVector marked(count, false, zone); 327a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org { 328fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org ZoneQueue<BasicBlock*> queue(zone); 329a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org queue.push(start); 330a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org marked[start->id()] = true; 331a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org while (!queue.empty()) { 332a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlock* block = queue.front(); 333a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org queue.pop(); 334a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org for (int s = 0; s < block->SuccessorCount(); s++) { 335a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlock* succ = block->SuccessorAt(s); 336a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (!marked[succ->id()]) { 337a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org marked[succ->id()] = true; 338a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org queue.push(succ); 339a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 340a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 341a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 342a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 343a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Verify marked blocks are in the RPO. 344a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org for (int i = 0; i < count; i++) { 345a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlock* block = schedule->GetBlockById(i); 346a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (marked[i]) { 347a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CHECK_GE(block->rpo_number_, 0); 348a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CHECK_EQ(block, rpo_order->at(block->rpo_number_)); 349a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 350a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 351a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Verify RPO blocks are marked. 352a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org for (size_t b = 0; b < rpo_order->size(); b++) { 353a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CHECK(marked[rpo_order->at(b)->id()]); 354a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 355a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 356a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org { 357a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Verify the dominance relation. 358a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org ZoneList<BitVector*> dominators(count, zone); 359a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org dominators.Initialize(count, zone); 360a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org dominators.AddBlock(NULL, count, zone); 361a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 362a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Compute a set of all the nodes that dominate a given node by using 363a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // a forward fixpoint. O(n^2). 364fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org ZoneQueue<BasicBlock*> queue(zone); 365a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org queue.push(start); 366a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org dominators[start->id()] = new (zone) BitVector(count, zone); 367a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org while (!queue.empty()) { 368a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlock* block = queue.front(); 369a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org queue.pop(); 370a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BitVector* block_doms = dominators[block->id()]; 371fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org BasicBlock* idom = block->dominator_; 372a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (idom != NULL && !block_doms->Contains(idom->id())) { 373a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d", 374a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org block->id(), idom->id()); 375a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 376a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org for (int s = 0; s < block->SuccessorCount(); s++) { 377a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlock* succ = block->SuccessorAt(s); 378a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BitVector* succ_doms = dominators[succ->id()]; 379a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 380a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (succ_doms == NULL) { 381fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // First time visiting the node. S.doms = B U B.doms 382a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org succ_doms = new (zone) BitVector(count, zone); 383a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org succ_doms->CopyFrom(*block_doms); 384a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org succ_doms->Add(block->id()); 385a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org dominators[succ->id()] = succ_doms; 386a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org queue.push(succ); 387a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } else { 388fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms) 389a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org bool had = succ_doms->Contains(block->id()); 390a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (had) succ_doms->Remove(block->id()); 391a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ); 392a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (had) succ_doms->Add(block->id()); 393a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 394a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 395a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 396a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 397a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Verify the immediateness of dominators. 398a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org for (BasicBlockVector::iterator b = rpo_order->begin(); 399a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org b != rpo_order->end(); ++b) { 400a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlock* block = *b; 401fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org BasicBlock* idom = block->dominator_; 402a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (idom == NULL) continue; 403a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BitVector* block_doms = dominators[block->id()]; 404a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 405a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) { 406a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlock* dom = schedule->GetBlockById(it.Current()); 407a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (dom != idom && !dominators[idom->id()]->Contains(dom->id())) { 408a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org V8_Fatal(__FILE__, __LINE__, 409a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org "Block B%d is not immediately dominated by B%d", block->id(), 410a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org idom->id()); 411a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 412a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 413a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 414a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 415a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 416a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Verify phis are placed in the block of their control input. 417a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); 418a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org ++b) { 419a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org for (BasicBlock::const_iterator i = (*b)->begin(); i != (*b)->end(); ++i) { 420a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Node* phi = *i; 421a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (phi->opcode() != IrOpcode::kPhi) continue; 422a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // TODO(titzer): Nasty special case. Phis from RawMachineAssembler 423a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // schedules don't have control inputs. 424a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (phi->InputCount() > 425a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org OperatorProperties::GetValueInputCount(phi->op())) { 426a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Node* control = NodeProperties::GetControlInput(phi); 427a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CHECK(control->opcode() == IrOpcode::kMerge || 428a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org control->opcode() == IrOpcode::kLoop); 429a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CHECK_EQ((*b), schedule->block(control)); 430a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 431a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 432a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 433a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 434a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Verify that all uses are dominated by their definitions. 435a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); 436a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org ++b) { 437a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org BasicBlock* block = *b; 438a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org 439a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Check inputs to control for this block. 440a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Node* control = block->control_input_; 441a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org if (control != NULL) { 442a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CHECK_EQ(block, schedule->block(control)); 443a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CheckInputsDominate(schedule, block, control, 444a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org static_cast<int>(block->nodes_.size()) - 1); 445a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 446a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org // Check inputs for all nodes in the block. 447a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org for (size_t i = 0; i < block->nodes_.size(); i++) { 448a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org Node* node = block->nodes_[i]; 449a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1); 450a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 451a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org } 452a8702c210b949f35c64d8e4aa01bb6d525086c85machenbach@chromium.org} 4537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 4547d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 4557d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} // namespace v8::internal::compiler 456