src/v8/src/compiler/verifier.cc

   1 // Copyright 2014 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/compiler/verifier.h"
   6
   7 #include <deque>
   8 #include <queue>
   9
  10 #include "src/compiler/generic-algorithm.h"
  11 #include "src/compiler/generic-node-inl.h"
  12 #include "src/compiler/generic-node.h"
  13 #include "src/compiler/graph-inl.h"
  14 #include "src/compiler/graph.h"
  15 #include "src/compiler/node.h"
  16 #include "src/compiler/node-properties-inl.h"
  17 #include "src/compiler/node-properties.h"
  18 #include "src/compiler/opcodes.h"
  19 #include "src/compiler/operator.h"
  20 #include "src/compiler/schedule.h"
  21 #include "src/data-flow.h"
  22
  23 namespace v8 {
  24 namespace internal {
  25 namespace compiler {
  26
  27
  28 static bool IsDefUseChainLinkPresent(Node* def, Node* use) {
  29   Node::Uses uses = def->uses();
  30   for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
  31     if (*it == use) return true;
  32   }
  33   return false;
  34 }
  35
  36
  37 static bool IsUseDefChainLinkPresent(Node* def, Node* use) {
  38   Node::Inputs inputs = use->inputs();
  39   for (Node::Inputs::iterator it = inputs.begin(); it != inputs.end(); ++it) {
  40     if (*it == def) return true;
  41   }
  42   return false;
  43 }
  44
  45
  46 class Verifier::Visitor : public NullNodeVisitor {
  47  public:
  48   explicit Visitor(Zone* zone)
  49       : reached_from_start(NodeSet::key_compare(),
  50                            NodeSet::allocator_type(zone)),
  51         reached_from_end(NodeSet::key_compare(),
  52                          NodeSet::allocator_type(zone)) {}
  53
  54   // Fulfills the PreNodeCallback interface.
  55   GenericGraphVisit::Control Pre(Node* node);
  56
  57   bool from_start;
  58   NodeSet reached_from_start;
  59   NodeSet reached_from_end;
  60 };
  61
  62
  63 GenericGraphVisit::Control Verifier::Visitor::Pre(Node* node) {
  64   int value_count = OperatorProperties::GetValueInputCount(node->op());
  65   int context_count = OperatorProperties::GetContextInputCount(node->op());
  66   int frame_state_count =
  67       OperatorProperties::GetFrameStateInputCount(node->op());
  68   int effect_count = OperatorProperties::GetEffectInputCount(node->op());
  69   int control_count = OperatorProperties::GetControlInputCount(node->op());
  70
  71   // Verify number of inputs matches up.
  72   int input_count = value_count + context_count + frame_state_count +
  73                     effect_count + control_count;
  74   CHECK_EQ(input_count, node->InputCount());
  75
  76   // Verify that frame state has been inserted for the nodes that need it.
  77   if (OperatorProperties::HasFrameStateInput(node->op())) {
  78     Node* frame_state = NodeProperties::GetFrameStateInput(node);
  79     CHECK(frame_state->opcode() == IrOpcode::kFrameState ||
  80           // kFrameState uses undefined as a sentinel.
  81           (node->opcode() == IrOpcode::kFrameState &&
  82            frame_state->opcode() == IrOpcode::kHeapConstant));
  83     CHECK(IsDefUseChainLinkPresent(frame_state, node));
  84     CHECK(IsUseDefChainLinkPresent(frame_state, node));
  85   }
  86
  87   // Verify all value inputs actually produce a value.
  88   for (int i = 0; i < value_count; ++i) {
  89     Node* value = NodeProperties::GetValueInput(node, i);
  90     CHECK(OperatorProperties::HasValueOutput(value->op()));
  91     CHECK(IsDefUseChainLinkPresent(value, node));
  92     CHECK(IsUseDefChainLinkPresent(value, node));
  93   }
  94
  95   // Verify all context inputs are value nodes.
  96   for (int i = 0; i < context_count; ++i) {
  97     Node* context = NodeProperties::GetContextInput(node);
  98     CHECK(OperatorProperties::HasValueOutput(context->op()));
  99     CHECK(IsDefUseChainLinkPresent(context, node));
 100     CHECK(IsUseDefChainLinkPresent(context, node));
 101   }
 102
 103   // Verify all effect inputs actually have an effect.
 104   for (int i = 0; i < effect_count; ++i) {
 105     Node* effect = NodeProperties::GetEffectInput(node);
 106     CHECK(OperatorProperties::HasEffectOutput(effect->op()));
 107     CHECK(IsDefUseChainLinkPresent(effect, node));
 108     CHECK(IsUseDefChainLinkPresent(effect, node));
 109   }
 110
 111   // Verify all control inputs are control nodes.
 112   for (int i = 0; i < control_count; ++i) {
 113     Node* control = NodeProperties::GetControlInput(node, i);
 114     CHECK(OperatorProperties::HasControlOutput(control->op()));
 115     CHECK(IsDefUseChainLinkPresent(control, node));
 116     CHECK(IsUseDefChainLinkPresent(control, node));
 117   }
 118
 119   // Verify all successors are projections if multiple value outputs exist.
 120   if (OperatorProperties::GetValueOutputCount(node->op()) > 1) {
 121     Node::Uses uses = node->uses();
 122     for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
 123       CHECK(!NodeProperties::IsValueEdge(it.edge()) ||
 124             (*it)->opcode() == IrOpcode::kProjection ||
 125             (*it)->opcode() == IrOpcode::kParameter);
 126     }
 127   }
 128
 129   switch (node->opcode()) {
 130     case IrOpcode::kStart:
 131       // Start has no inputs.
 132       CHECK_EQ(0, input_count);
 133       break;
 134     case IrOpcode::kEnd:
 135       // End has no outputs.
 136       CHECK(!OperatorProperties::HasValueOutput(node->op()));
 137       CHECK(!OperatorProperties::HasEffectOutput(node->op()));
 138       CHECK(!OperatorProperties::HasControlOutput(node->op()));
 139       break;
 140     case IrOpcode::kDead:
 141       // Dead is never connected to the graph.
 142       UNREACHABLE();
 143     case IrOpcode::kBranch: {
 144       // Branch uses are IfTrue and IfFalse.
 145       Node::Uses uses = node->uses();
 146       bool got_true = false, got_false = false;
 147       for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
 148         CHECK(((*it)->opcode() == IrOpcode::kIfTrue && !got_true) ||
 149               ((*it)->opcode() == IrOpcode::kIfFalse && !got_false));
 150         if ((*it)->opcode() == IrOpcode::kIfTrue) got_true = true;
 151         if ((*it)->opcode() == IrOpcode::kIfFalse) got_false = true;
 152       }
 153       // TODO(rossberg): Currently fails for various tests.
 154       // CHECK(got_true && got_false);
 155       break;
 156     }
 157     case IrOpcode::kIfTrue:
 158     case IrOpcode::kIfFalse:
 159       CHECK_EQ(IrOpcode::kBranch,
 160                NodeProperties::GetControlInput(node, 0)->opcode());
 161       break;
 162     case IrOpcode::kLoop:
 163     case IrOpcode::kMerge:
 164       break;
 165     case IrOpcode::kReturn:
 166       // TODO(rossberg): check successor is End
 167       break;
 168     case IrOpcode::kThrow:
 169       // TODO(rossberg): what are the constraints on these?
 170       break;
 171     case IrOpcode::kParameter: {
 172       // Parameters have the start node as inputs.
 173       CHECK_EQ(1, input_count);
 174       CHECK_EQ(IrOpcode::kStart,
 175                NodeProperties::GetValueInput(node, 0)->opcode());
 176       // Parameter has an input that produces enough values.
 177       int index = OpParameter<int>(node);
 178       Node* input = NodeProperties::GetValueInput(node, 0);
 179       // Currently, parameter indices start at -1 instead of 0.
 180       CHECK_GT(OperatorProperties::GetValueOutputCount(input->op()), index + 1);
 181       break;
 182     }
 183     case IrOpcode::kInt32Constant:
 184     case IrOpcode::kInt64Constant:
 185     case IrOpcode::kFloat64Constant:
 186     case IrOpcode::kExternalConstant:
 187     case IrOpcode::kNumberConstant:
 188     case IrOpcode::kHeapConstant:
 189       // Constants have no inputs.
 190       CHECK_EQ(0, input_count);
 191       break;
 192     case IrOpcode::kPhi: {
 193       // Phi input count matches parent control node.
 194       CHECK_EQ(1, control_count);
 195       Node* control = NodeProperties::GetControlInput(node, 0);
 196       CHECK_EQ(value_count,
 197                OperatorProperties::GetControlInputCount(control->op()));
 198       break;
 199     }
 200     case IrOpcode::kEffectPhi: {
 201       // EffectPhi input count matches parent control node.
 202       CHECK_EQ(1, control_count);
 203       Node* control = NodeProperties::GetControlInput(node, 0);
 204       CHECK_EQ(effect_count,
 205                OperatorProperties::GetControlInputCount(control->op()));
 206       break;
 207     }
 208     case IrOpcode::kFrameState:
 209       // TODO(jarin): what are the constraints on these?
 210       break;
 211     case IrOpcode::kCall:
 212       // TODO(rossberg): what are the constraints on these?
 213       break;
 214     case IrOpcode::kProjection: {
 215       // Projection has an input that produces enough values.
 216       size_t index = OpParameter<size_t>(node);
 217       Node* input = NodeProperties::GetValueInput(node, 0);
 218       CHECK_GT(OperatorProperties::GetValueOutputCount(input->op()),
 219                static_cast<int>(index));
 220       break;
 221     }
 222     default:
 223       // TODO(rossberg): Check other node kinds.
 224       break;
 225   }
 226
 227   if (from_start) {
 228     reached_from_start.insert(node);
 229   } else {
 230     reached_from_end.insert(node);
 231   }
 232
 233   return GenericGraphVisit::CONTINUE;
 234 }
 235
 236
 237 void Verifier::Run(Graph* graph) {
 238   Visitor visitor(graph->zone());
 239
 240   CHECK_NE(NULL, graph->start());
 241   visitor.from_start = true;
 242   graph->VisitNodeUsesFromStart(&visitor);
 243   CHECK_NE(NULL, graph->end());
 244   visitor.from_start = false;
 245   graph->VisitNodeInputsFromEnd(&visitor);
 246
 247   // All control nodes reachable from end are reachable from start.
 248   for (NodeSet::iterator it = visitor.reached_from_end.begin();
 249        it != visitor.reached_from_end.end(); ++it) {
 250     CHECK(!NodeProperties::IsControl(*it) ||
 251           visitor.reached_from_start.count(*it));
 252   }
 253 }
 254
 255
 256 static bool HasDominatingDef(Schedule* schedule, Node* node,
 257                              BasicBlock* container, BasicBlock* use_block,
 258                              int use_pos) {
 259   BasicBlock* block = use_block;
 260   while (true) {
 261     while (use_pos >= 0) {
 262       if (block->nodes_[use_pos] == node) return true;
 263       use_pos--;
 264     }
 265     block = block->dominator_;
 266     if (block == NULL) break;
 267     use_pos = static_cast<int>(block->nodes_.size()) - 1;
 268     if (node == block->control_input_) return true;
 269   }
 270   return false;
 271 }
 272
 273
 274 static void CheckInputsDominate(Schedule* schedule, BasicBlock* block,
 275                                 Node* node, int use_pos) {
 276   for (int j = OperatorProperties::GetValueInputCount(node->op()) - 1; j >= 0;
 277        j--) {
 278     BasicBlock* use_block = block;
 279     if (node->opcode() == IrOpcode::kPhi) {
 280       use_block = use_block->PredecessorAt(j);
 281       use_pos = static_cast<int>(use_block->nodes_.size()) - 1;
 282     }
 283     Node* input = node->InputAt(j);
 284     if (!HasDominatingDef(schedule, node->InputAt(j), block, use_block,
 285                           use_pos)) {
 286       V8_Fatal(__FILE__, __LINE__,
 287                "Node #%d:%s in B%d is not dominated by input@%d #%d:%s",
 288                node->id(), node->op()->mnemonic(), block->id(), j, input->id(),
 289                input->op()->mnemonic());
 290     }
 291   }
 292 }
 293
 294
 295 void ScheduleVerifier::Run(Schedule* schedule) {
 296   const int count = schedule->BasicBlockCount();
 297   Zone tmp_zone(schedule->zone()->isolate());
 298   Zone* zone = &tmp_zone;
 299   BasicBlock* start = schedule->start();
 300   BasicBlockVector* rpo_order = schedule->rpo_order();
 301
 302   // Verify the RPO order contains only blocks from this schedule.
 303   CHECK_GE(count, static_cast<int>(rpo_order->size()));
 304   for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
 305        ++b) {
 306     CHECK_EQ((*b), schedule->GetBlockById((*b)->id()));
 307   }
 308
 309   // Verify RPO numbers of blocks.
 310   CHECK_EQ(start, rpo_order->at(0));  // Start should be first.
 311   for (size_t b = 0; b < rpo_order->size(); b++) {
 312     BasicBlock* block = rpo_order->at(b);
 313     CHECK_EQ(static_cast<int>(b), block->rpo_number_);
 314     BasicBlock* dom = block->dominator_;
 315     if (b == 0) {
 316       // All blocks except start should have a dominator.
 317       CHECK_EQ(NULL, dom);
 318     } else {
 319       // Check that the immediate dominator appears somewhere before the block.
 320       CHECK_NE(NULL, dom);
 321       CHECK_LT(dom->rpo_number_, block->rpo_number_);
 322     }
 323   }
 324
 325   // Verify that all blocks reachable from start are in the RPO.
 326   BoolVector marked(count, false, zone);
 327   {
 328     ZoneQueue<BasicBlock*> queue(zone);
 329     queue.push(start);
 330     marked[start->id()] = true;
 331     while (!queue.empty()) {
 332       BasicBlock* block = queue.front();
 333       queue.pop();
 334       for (int s = 0; s < block->SuccessorCount(); s++) {
 335         BasicBlock* succ = block->SuccessorAt(s);
 336         if (!marked[succ->id()]) {
 337           marked[succ->id()] = true;
 338           queue.push(succ);
 339         }
 340       }
 341     }
 342   }
 343   // Verify marked blocks are in the RPO.
 344   for (int i = 0; i < count; i++) {
 345     BasicBlock* block = schedule->GetBlockById(i);
 346     if (marked[i]) {
 347       CHECK_GE(block->rpo_number_, 0);
 348       CHECK_EQ(block, rpo_order->at(block->rpo_number_));
 349     }
 350   }
 351   // Verify RPO blocks are marked.
 352   for (size_t b = 0; b < rpo_order->size(); b++) {
 353     CHECK(marked[rpo_order->at(b)->id()]);
 354   }
 355
 356   {
 357     // Verify the dominance relation.
 358     ZoneList<BitVector*> dominators(count, zone);
 359     dominators.Initialize(count, zone);
 360     dominators.AddBlock(NULL, count, zone);
 361
 362     // Compute a set of all the nodes that dominate a given node by using
 363     // a forward fixpoint. O(n^2).
 364     ZoneQueue<BasicBlock*> queue(zone);
 365     queue.push(start);
 366     dominators[start->id()] = new (zone) BitVector(count, zone);
 367     while (!queue.empty()) {
 368       BasicBlock* block = queue.front();
 369       queue.pop();
 370       BitVector* block_doms = dominators[block->id()];
 371       BasicBlock* idom = block->dominator_;
 372       if (idom != NULL && !block_doms->Contains(idom->id())) {
 373         V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d",
 374                  block->id(), idom->id());
 375       }
 376       for (int s = 0; s < block->SuccessorCount(); s++) {
 377         BasicBlock* succ = block->SuccessorAt(s);
 378         BitVector* succ_doms = dominators[succ->id()];
 379
 380         if (succ_doms == NULL) {
 381           // First time visiting the node. S.doms = B U B.doms
 382           succ_doms = new (zone) BitVector(count, zone);
 383           succ_doms->CopyFrom(*block_doms);
 384           succ_doms->Add(block->id());
 385           dominators[succ->id()] = succ_doms;
 386           queue.push(succ);
 387         } else {
 388           // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms)
 389           bool had = succ_doms->Contains(block->id());
 390           if (had) succ_doms->Remove(block->id());
 391           if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ);
 392           if (had) succ_doms->Add(block->id());
 393         }
 394       }
 395     }
 396
 397     // Verify the immediateness of dominators.
 398     for (BasicBlockVector::iterator b = rpo_order->begin();
 399          b != rpo_order->end(); ++b) {
 400       BasicBlock* block = *b;
 401       BasicBlock* idom = block->dominator_;
 402       if (idom == NULL) continue;
 403       BitVector* block_doms = dominators[block->id()];
 404
 405       for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) {
 406         BasicBlock* dom = schedule->GetBlockById(it.Current());
 407         if (dom != idom && !dominators[idom->id()]->Contains(dom->id())) {
 408           V8_Fatal(__FILE__, __LINE__,
 409                    "Block B%d is not immediately dominated by B%d", block->id(),
 410                    idom->id());
 411         }
 412       }
 413     }
 414   }
 415
 416   // Verify phis are placed in the block of their control input.
 417   for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
 418        ++b) {
 419     for (BasicBlock::const_iterator i = (*b)->begin(); i != (*b)->end(); ++i) {
 420       Node* phi = *i;
 421       if (phi->opcode() != IrOpcode::kPhi) continue;
 422       // TODO(titzer): Nasty special case. Phis from RawMachineAssembler
 423       // schedules don't have control inputs.
 424       if (phi->InputCount() >
 425           OperatorProperties::GetValueInputCount(phi->op())) {
 426         Node* control = NodeProperties::GetControlInput(phi);
 427         CHECK(control->opcode() == IrOpcode::kMerge ||
 428               control->opcode() == IrOpcode::kLoop);
 429         CHECK_EQ((*b), schedule->block(control));
 430       }
 431     }
 432   }
 433
 434   // Verify that all uses are dominated by their definitions.
 435   for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
 436        ++b) {
 437     BasicBlock* block = *b;
 438
 439     // Check inputs to control for this block.
 440     Node* control = block->control_input_;
 441     if (control != NULL) {
 442       CHECK_EQ(block, schedule->block(control));
 443       CheckInputsDominate(schedule, block, control,
 444                           static_cast<int>(block->nodes_.size()) - 1);
 445     }
 446     // Check inputs for all nodes in the block.
 447     for (size_t i = 0; i < block->nodes_.size(); i++) {
 448       Node* node = block->nodes_[i];
 449       CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1);
 450     }
 451   }
 452 }
 453 }
 454 }
 455 }  // namespace v8::internal::compiler