Upgrade to 3.29
Update V8 to 3.29.88.17 and update makefiles to support building on
all the relevant platforms.
Bug: 17370214
Change-Id: Ia3407c157fd8d72a93e23d8318ccaf6ecf77fa4e
diff --git a/src/compiler/verifier.cc b/src/compiler/verifier.cc
new file mode 100644
index 0000000..23cec7a
--- /dev/null
+++ b/src/compiler/verifier.cc
@@ -0,0 +1,455 @@
+// 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 <deque>
+#include <queue>
+
+#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"
+#include "src/compiler/schedule.h"
+#include "src/data-flow.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 = OperatorProperties::GetValueInputCount(node->op());
+ int context_count = OperatorProperties::GetContextInputCount(node->op());
+ int frame_state_count =
+ OperatorProperties::GetFrameStateInputCount(node->op());
+ int effect_count = OperatorProperties::GetEffectInputCount(node->op());
+ int control_count = OperatorProperties::GetControlInputCount(node->op());
+
+ // Verify number of inputs matches up.
+ int input_count = value_count + context_count + frame_state_count +
+ effect_count + control_count;
+ CHECK_EQ(input_count, node->InputCount());
+
+ // Verify that frame state has been inserted for the nodes that need it.
+ if (OperatorProperties::HasFrameStateInput(node->op())) {
+ Node* frame_state = NodeProperties::GetFrameStateInput(node);
+ CHECK(frame_state->opcode() == IrOpcode::kFrameState ||
+ // kFrameState uses undefined as a sentinel.
+ (node->opcode() == IrOpcode::kFrameState &&
+ frame_state->opcode() == IrOpcode::kHeapConstant));
+ CHECK(IsDefUseChainLinkPresent(frame_state, node));
+ CHECK(IsUseDefChainLinkPresent(frame_state, node));
+ }
+
+ // Verify all value inputs actually produce a value.
+ for (int i = 0; i < value_count; ++i) {
+ Node* value = NodeProperties::GetValueInput(node, i);
+ CHECK(OperatorProperties::HasValueOutput(value->op()));
+ 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(OperatorProperties::HasValueOutput(context->op()));
+ 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(OperatorProperties::HasEffectOutput(effect->op()));
+ 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(OperatorProperties::HasControlOutput(control->op()));
+ CHECK(IsDefUseChainLinkPresent(control, node));
+ CHECK(IsUseDefChainLinkPresent(control, node));
+ }
+
+ // Verify all successors are projections if multiple value outputs exist.
+ if (OperatorProperties::GetValueOutputCount(node->op()) > 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 ||
+ (*it)->opcode() == IrOpcode::kParameter);
+ }
+ }
+
+ switch (node->opcode()) {
+ case IrOpcode::kStart:
+ // Start has no inputs.
+ CHECK_EQ(0, input_count);
+ break;
+ case IrOpcode::kEnd:
+ // End has no outputs.
+ CHECK(!OperatorProperties::HasValueOutput(node->op()));
+ CHECK(!OperatorProperties::HasEffectOutput(node->op()));
+ CHECK(!OperatorProperties::HasControlOutput(node->op()));
+ 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 the start node as inputs.
+ CHECK_EQ(1, input_count);
+ CHECK_EQ(IrOpcode::kStart,
+ NodeProperties::GetValueInput(node, 0)->opcode());
+ // Parameter has an input that produces enough values.
+ int index = OpParameter<int>(node);
+ Node* input = NodeProperties::GetValueInput(node, 0);
+ // Currently, parameter indices start at -1 instead of 0.
+ CHECK_GT(OperatorProperties::GetValueOutputCount(input->op()), index + 1);
+ 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,
+ OperatorProperties::GetControlInputCount(control->op()));
+ 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,
+ OperatorProperties::GetControlInputCount(control->op()));
+ 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::kProjection: {
+ // Projection has an input that produces enough values.
+ size_t index = OpParameter<size_t>(node);
+ Node* input = NodeProperties::GetValueInput(node, 0);
+ CHECK_GT(OperatorProperties::GetValueOutputCount(input->op()),
+ static_cast<int>(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());
+
+ CHECK_NE(NULL, graph->start());
+ visitor.from_start = true;
+ graph->VisitNodeUsesFromStart(&visitor);
+ CHECK_NE(NULL, graph->end());
+ 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));
+ }
+}
+
+
+static bool HasDominatingDef(Schedule* schedule, Node* node,
+ BasicBlock* container, BasicBlock* use_block,
+ int use_pos) {
+ BasicBlock* block = use_block;
+ while (true) {
+ while (use_pos >= 0) {
+ if (block->nodes_[use_pos] == node) return true;
+ use_pos--;
+ }
+ block = block->dominator_;
+ if (block == NULL) break;
+ use_pos = static_cast<int>(block->nodes_.size()) - 1;
+ if (node == block->control_input_) return true;
+ }
+ return false;
+}
+
+
+static void CheckInputsDominate(Schedule* schedule, BasicBlock* block,
+ Node* node, int use_pos) {
+ for (int j = OperatorProperties::GetValueInputCount(node->op()) - 1; j >= 0;
+ j--) {
+ BasicBlock* use_block = block;
+ if (node->opcode() == IrOpcode::kPhi) {
+ use_block = use_block->PredecessorAt(j);
+ use_pos = static_cast<int>(use_block->nodes_.size()) - 1;
+ }
+ Node* input = node->InputAt(j);
+ if (!HasDominatingDef(schedule, node->InputAt(j), block, use_block,
+ use_pos)) {
+ V8_Fatal(__FILE__, __LINE__,
+ "Node #%d:%s in B%d is not dominated by input@%d #%d:%s",
+ node->id(), node->op()->mnemonic(), block->id(), j, input->id(),
+ input->op()->mnemonic());
+ }
+ }
+}
+
+
+void ScheduleVerifier::Run(Schedule* schedule) {
+ const int count = schedule->BasicBlockCount();
+ Zone tmp_zone(schedule->zone()->isolate());
+ Zone* zone = &tmp_zone;
+ BasicBlock* start = schedule->start();
+ BasicBlockVector* rpo_order = schedule->rpo_order();
+
+ // Verify the RPO order contains only blocks from this schedule.
+ CHECK_GE(count, static_cast<int>(rpo_order->size()));
+ for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
+ ++b) {
+ CHECK_EQ((*b), schedule->GetBlockById((*b)->id()));
+ }
+
+ // Verify RPO numbers of blocks.
+ CHECK_EQ(start, rpo_order->at(0)); // Start should be first.
+ for (size_t b = 0; b < rpo_order->size(); b++) {
+ BasicBlock* block = rpo_order->at(b);
+ CHECK_EQ(static_cast<int>(b), block->rpo_number_);
+ BasicBlock* dom = block->dominator_;
+ if (b == 0) {
+ // All blocks except start should have a dominator.
+ CHECK_EQ(NULL, dom);
+ } else {
+ // Check that the immediate dominator appears somewhere before the block.
+ CHECK_NE(NULL, dom);
+ CHECK_LT(dom->rpo_number_, block->rpo_number_);
+ }
+ }
+
+ // Verify that all blocks reachable from start are in the RPO.
+ BoolVector marked(count, false, zone);
+ {
+ ZoneQueue<BasicBlock*> queue(zone);
+ queue.push(start);
+ marked[start->id()] = true;
+ while (!queue.empty()) {
+ BasicBlock* block = queue.front();
+ queue.pop();
+ for (int s = 0; s < block->SuccessorCount(); s++) {
+ BasicBlock* succ = block->SuccessorAt(s);
+ if (!marked[succ->id()]) {
+ marked[succ->id()] = true;
+ queue.push(succ);
+ }
+ }
+ }
+ }
+ // Verify marked blocks are in the RPO.
+ for (int i = 0; i < count; i++) {
+ BasicBlock* block = schedule->GetBlockById(i);
+ if (marked[i]) {
+ CHECK_GE(block->rpo_number_, 0);
+ CHECK_EQ(block, rpo_order->at(block->rpo_number_));
+ }
+ }
+ // Verify RPO blocks are marked.
+ for (size_t b = 0; b < rpo_order->size(); b++) {
+ CHECK(marked[rpo_order->at(b)->id()]);
+ }
+
+ {
+ // Verify the dominance relation.
+ ZoneList<BitVector*> dominators(count, zone);
+ dominators.Initialize(count, zone);
+ dominators.AddBlock(NULL, count, zone);
+
+ // Compute a set of all the nodes that dominate a given node by using
+ // a forward fixpoint. O(n^2).
+ ZoneQueue<BasicBlock*> queue(zone);
+ queue.push(start);
+ dominators[start->id()] = new (zone) BitVector(count, zone);
+ while (!queue.empty()) {
+ BasicBlock* block = queue.front();
+ queue.pop();
+ BitVector* block_doms = dominators[block->id()];
+ BasicBlock* idom = block->dominator_;
+ if (idom != NULL && !block_doms->Contains(idom->id())) {
+ V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d",
+ block->id(), idom->id());
+ }
+ for (int s = 0; s < block->SuccessorCount(); s++) {
+ BasicBlock* succ = block->SuccessorAt(s);
+ BitVector* succ_doms = dominators[succ->id()];
+
+ if (succ_doms == NULL) {
+ // First time visiting the node. S.doms = B U B.doms
+ succ_doms = new (zone) BitVector(count, zone);
+ succ_doms->CopyFrom(*block_doms);
+ succ_doms->Add(block->id());
+ dominators[succ->id()] = succ_doms;
+ queue.push(succ);
+ } else {
+ // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms)
+ bool had = succ_doms->Contains(block->id());
+ if (had) succ_doms->Remove(block->id());
+ if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ);
+ if (had) succ_doms->Add(block->id());
+ }
+ }
+ }
+
+ // Verify the immediateness of dominators.
+ for (BasicBlockVector::iterator b = rpo_order->begin();
+ b != rpo_order->end(); ++b) {
+ BasicBlock* block = *b;
+ BasicBlock* idom = block->dominator_;
+ if (idom == NULL) continue;
+ BitVector* block_doms = dominators[block->id()];
+
+ for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) {
+ BasicBlock* dom = schedule->GetBlockById(it.Current());
+ if (dom != idom && !dominators[idom->id()]->Contains(dom->id())) {
+ V8_Fatal(__FILE__, __LINE__,
+ "Block B%d is not immediately dominated by B%d", block->id(),
+ idom->id());
+ }
+ }
+ }
+ }
+
+ // Verify phis are placed in the block of their control input.
+ for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
+ ++b) {
+ for (BasicBlock::const_iterator i = (*b)->begin(); i != (*b)->end(); ++i) {
+ Node* phi = *i;
+ if (phi->opcode() != IrOpcode::kPhi) continue;
+ // TODO(titzer): Nasty special case. Phis from RawMachineAssembler
+ // schedules don't have control inputs.
+ if (phi->InputCount() >
+ OperatorProperties::GetValueInputCount(phi->op())) {
+ Node* control = NodeProperties::GetControlInput(phi);
+ CHECK(control->opcode() == IrOpcode::kMerge ||
+ control->opcode() == IrOpcode::kLoop);
+ CHECK_EQ((*b), schedule->block(control));
+ }
+ }
+ }
+
+ // Verify that all uses are dominated by their definitions.
+ for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
+ ++b) {
+ BasicBlock* block = *b;
+
+ // Check inputs to control for this block.
+ Node* control = block->control_input_;
+ if (control != NULL) {
+ CHECK_EQ(block, schedule->block(control));
+ CheckInputsDominate(schedule, block, control,
+ static_cast<int>(block->nodes_.size()) - 1);
+ }
+ // Check inputs for all nodes in the block.
+ for (size_t i = 0; i < block->nodes_.size(); i++) {
+ Node* node = block->nodes_[i];
+ CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1);
+ }
+ }
+}
+}
+}
+} // namespace v8::internal::compiler