From 1f9bd09f3666b2afc0fe46a6bfdb23c714a8e7a6 Mon Sep 17 00:00:00 2001 From: "titzer@chromium.org" Date: Fri, 22 Aug 2014 12:37:51 +0000 Subject: [PATCH] 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. R=jarin@chromium.org BUG= Review URL: https://codereview.chromium.org/491303002 git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23310 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- .gitignore | 1 + src/compiler/pipeline.cc | 11 +-- src/compiler/verifier.cc | 204 +++++++++++++++++++++++++++++++++++++++++++++++ src/compiler/verifier.h | 13 ++- src/data-flow.h | 11 +++ 5 files changed, 233 insertions(+), 7 deletions(-) diff --git a/.gitignore b/.gitignore index d0d4b43..e26a13f 100644 --- a/.gitignore +++ b/.gitignore @@ -80,3 +80,4 @@ GRTAGS GSYMS GPATH gtags.files +turbo*.dot \ No newline at end of file diff --git a/src/compiler/pipeline.cc b/src/compiler/pipeline.cc index aefe173..bd99944 100644 --- a/src/compiler/pipeline.cc +++ b/src/compiler/pipeline.cc @@ -248,11 +248,9 @@ Handle Pipeline::GenerateCode() { 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 @@ Handle Pipeline::GenerateCode() { 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; } diff --git a/src/compiler/verifier.cc b/src/compiler/verifier.cc index 291ecb0..4453671 100644 --- a/src/compiler/verifier.cc +++ b/src/compiler/verifier.cc @@ -4,6 +4,9 @@ #include "src/compiler/verifier.h" +#include +#include + #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 @@ void Verifier::Run(Graph* graph) { 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(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(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(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 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 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 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(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(i) - 1); + } + } +} } } } // namespace v8::internal::compiler diff --git a/src/compiler/verifier.h b/src/compiler/verifier.h index 788c6a5..b5c028e 100644 --- a/src/compiler/verifier.h +++ b/src/compiler/verifier.h @@ -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 Verifier { 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 diff --git a/src/data-flow.h b/src/data-flow.h index ad96c2c..bfd238d 100644 --- a/src/data-flow.h +++ b/src/data-flow.h @@ -137,6 +137,17 @@ class BitVector: public ZoneObject { } } + 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()); for (int i = 0; i < data_length_; i++) { -- 2.7.4