v8::internal::compiler::ScheduleVerifier Class Reference

#include <verifier.h>

Collaboration diagram for v8::internal::compiler::ScheduleVerifier:

Static Public Member Functions
static void	Run (Schedule *schedule)

Detailed Description

Definition at line 29 of file verifier.h.

Member Function Documentation

Run()

void v8::internal::compiler::ScheduleVerifier::Run ( Schedule *  schedule )

static

Definition at line 295 of file verifier.cc.

                                             {
  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);
    }
  }
}

References v8::internal::BitVector::Add(), v8::internal::List< T, AllocationPolicy >::AddBlock(), v8::internal::compiler::Schedule::BasicBlockCount(), v8::internal::compiler::Schedule::block(), CHECK, CHECK_EQ, CHECK_GE, CHECK_LT, CHECK_NE, v8::internal::compiler::CheckInputsDominate(), v8::internal::List< T, AllocationPolicy >::Contains(), v8::internal::BitVector::Contains(), v8::internal::BitVector::CopyFrom(), v8::internal::compiler::Schedule::GetBlockById(), v8::internal::compiler::NodeProperties::GetControlInput(), v8::internal::compiler::OperatorProperties::GetValueInputCount(), v8::internal::BitVector::IntersectIsChanged(), v8::internal::Zone::isolate(), NULL, v8::internal::BitVector::Remove(), v8::internal::compiler::Schedule::rpo_order(), v8::internal::compiler::GenericGraph< V >::start(), V8_Fatal(), and v8::internal::compiler::GenericGraphBase::zone().

Referenced by v8::internal::compiler::Pipeline::ComputeSchedule().

Here is the call graph for this function:

Here is the caller graph for this function:

---

The documentation for this class was generated from the following files:

• /mnt/V8SourceCode/src/compiler/verifier.h
• /mnt/V8SourceCode/src/compiler/verifier.cc