Revision: 23310
Author: [email protected]
Date: Fri Aug 22 12:37:51 2014 UTC
Log: Add ScheduleVerifier.
This adds a series of checks to the output of scheduling, including
properties
of the RPO order, the dominance relation, phi placement, and the SSA
property
that definitions dominate all their uses.
[email protected]
BUG=
Review URL: https://codereview.chromium.org/491303002
https://code.google.com/p/v8/source/detail?r=23310
Modified:
/branches/bleeding_edge/.gitignore
/branches/bleeding_edge/src/compiler/pipeline.cc
/branches/bleeding_edge/src/compiler/verifier.cc
/branches/bleeding_edge/src/compiler/verifier.h
/branches/bleeding_edge/src/data-flow.h
=======================================
--- /branches/bleeding_edge/.gitignore Thu Aug 7 12:56:53 2014 UTC
+++ /branches/bleeding_edge/.gitignore Fri Aug 22 12:37:51 2014 UTC
@@ -80,3 +80,4 @@
GSYMS
GPATH
gtags.files
+turbo*.dot
=======================================
--- /branches/bleeding_edge/src/compiler/pipeline.cc Thu Aug 21 12:40:10
2014 UTC
+++ /branches/bleeding_edge/src/compiler/pipeline.cc Fri Aug 22 12:37:51
2014 UTC
@@ -247,12 +247,10 @@
VerifyAndPrintGraph(&graph, "Lowered generic");
}
-
- // Compute a schedule.
- Schedule* schedule = ComputeSchedule(&graph);
- TraceSchedule(schedule);
{
+ // Compute a schedule.
+ Schedule* schedule = ComputeSchedule(&graph);
// Generate optimized code.
PhaseStats codegen_stats(info(), PhaseStats::CODEGEN, "codegen");
Linkage linkage(info());
@@ -278,7 +276,10 @@
Schedule* Pipeline::ComputeSchedule(Graph* graph) {
PhaseStats schedule_stats(info(), PhaseStats::CODEGEN, "scheduling");
- return Scheduler::ComputeSchedule(graph);
+ Schedule* schedule = Scheduler::ComputeSchedule(graph);
+ TraceSchedule(schedule);
+ if (VerifyGraphs()) ScheduleVerifier::Run(schedule);
+ return schedule;
}
=======================================
--- /branches/bleeding_edge/src/compiler/verifier.cc Thu Aug 21 11:56:46
2014 UTC
+++ /branches/bleeding_edge/src/compiler/verifier.cc Fri Aug 22 12:37:51
2014 UTC
@@ -4,6 +4,9 @@
#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"
@@ -14,6 +17,8 @@
#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 {
@@ -243,6 +248,205 @@
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 = schedule->dominator(block);
+ 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(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.
+ 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
=======================================
--- /branches/bleeding_edge/src/compiler/verifier.h Wed Jul 30 13:54:45
2014 UTC
+++ /branches/bleeding_edge/src/compiler/verifier.h Fri Aug 22 12:37:51
2014 UTC
@@ -7,12 +7,15 @@
#include "src/v8.h"
-#include "src/compiler/graph.h"
-
namespace v8 {
namespace internal {
namespace compiler {
+class Graph;
+class Schedule;
+
+// Verifies properties of a graph, such as the well-formedness of inputs to
+// each node, etc.
class Verifier {
public:
static void Run(Graph* graph);
@@ -21,6 +24,12 @@
class Visitor;
DISALLOW_COPY_AND_ASSIGN(Verifier);
};
+
+// Verifies properties of a schedule, such as dominance, phi placement,
etc.
+class ScheduleVerifier {
+ public:
+ static void Run(Schedule* schedule);
+};
}
}
} // namespace v8::internal::compiler
=======================================
--- /branches/bleeding_edge/src/data-flow.h Wed Aug 20 12:10:41 2014 UTC
+++ /branches/bleeding_edge/src/data-flow.h Fri Aug 22 12:37:51 2014 UTC
@@ -136,6 +136,17 @@
data_[i] &= other.data_[i];
}
}
+
+ bool IntersectIsChanged(const BitVector& other) {
+ DCHECK(other.length() == length());
+ bool changed = false;
+ for (int i = 0; i < data_length_; i++) {
+ uint32_t old_data = data_[i];
+ data_[i] &= other.data_[i];
+ if (data_[i] != old_data) changed = true;
+ }
+ return changed;
+ }
void Subtract(const BitVector& other) {
DCHECK(other.length() == length());
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
