Add ScheduleVerifier.

src/compiler/verifier.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/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;
@@ skipping 206 matching lines @@
   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 FindDominatingDef(Schedule* schedule, Node* node,

[Jarin, 2014/08/22 11:55:32]

FindDominatingDef suggests that it returns the dominating def. How about
HasDominatingDef?

[titzer, 2014/08/22 12:18:35]

Done.

+                              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;

[Jarin, 2014/08/22 11:55:32]

It looks like the verifier would be happy if I connect a node's input to its
output. Is that ok?

[Jarin, 2014/08/22 12:05:20]

Ah, as discussed offline, ignore this comment. I have been confused.

+      use_pos--;
+    }
+    block = schedule->dominator(block);
+    if (block == NULL) break;
+    use_pos = block->nodes_.size() - 1;

[Jarin, 2014/08/22 11:55:31]

I guess this will not compile on Win64. Perhaps use (reverse) iterator instead
of int? Or cast...

[titzer, 2014/08/22 12:18:35]

Done.

+    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 = use_block->nodes_.size() - 1;

[Jarin, 2014/08/22 11:55:31]

Again, this will not compile on Win64.

[titzer, 2014/08/22 12:18:35]

Done.

+    }
+    Node* input = node->InputAt(j);
+    if (!FindDominatingDef(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(b, block->rpo_number_);
+    BasicBlock* dom = schedule->dominator(block);
+    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, BoolVector::allocator_type(zone));
+  {
+    std::queue<BasicBlock*> queue;
+    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).
+    std::queue<BasicBlock*> queue;
+    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 = schedule->dominator(block);
+      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.vec = B U B.vec
+          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.vec = S.vec ^ (B U B.vec)
+          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 = schedule->dominator(block);
+      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.

[Jarin, 2014/08/22 11:55:31]

Note: At some point we will have to fix RawMachineAssembler to produce regular
graphs (connect control and effect inputs).

[titzer, 2014/08/22 12:18:35]

Yeah, I know.

+      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