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 #include <sstream>
  10 #include <string>
  11
  12 #include "src/bit-vector.h"
  13 #include "src/compiler/generic-algorithm.h"
  14 #include "src/compiler/generic-node-inl.h"
  15 #include "src/compiler/generic-node.h"
  16 #include "src/compiler/graph-inl.h"
  17 #include "src/compiler/graph.h"
  18 #include "src/compiler/node.h"
  19 #include "src/compiler/node-properties-inl.h"
  20 #include "src/compiler/node-properties.h"
  21 #include "src/compiler/opcodes.h"
  22 #include "src/compiler/operator.h"
  23 #include "src/compiler/schedule.h"
  24 #include "src/compiler/simplified-operator.h"
  25 #include "src/ostreams.h"
  26
  27 namespace v8 {
  28 namespace internal {
  29 namespace compiler {
  30
  31
  32 static bool IsDefUseChainLinkPresent(Node* def, Node* use) {
  33   Node::Uses uses = def->uses();
  34   for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
  35     if (*it == use) return true;
  36   }
  37   return false;
  38 }
  39
  40
  41 static bool IsUseDefChainLinkPresent(Node* def, Node* use) {
  42   Node::Inputs inputs = use->inputs();
  43   for (Node::Inputs::iterator it = inputs.begin(); it != inputs.end(); ++it) {
  44     if (*it == def) return true;
  45   }
  46   return false;
  47 }
  48
  49
  50 class Verifier::Visitor : public NullNodeVisitor {
  51  public:
  52   Visitor(Zone* z, Typing typed) : zone(z), typing(typed) {}
  53
  54   // Fulfills the PreNodeCallback interface.
  55   void Pre(Node* node);
  56
  57   Zone* zone;
  58   Typing typing;
  59
  60  private:
  61   // TODO(rossberg): Get rid of these once we got rid of NodeProperties.
  62   Bounds bounds(Node* node) { return NodeProperties::GetBounds(node); }
  63   Node* ValueInput(Node* node, int i = 0) {
  64     return NodeProperties::GetValueInput(node, i);
  65   }
  66   FieldAccess Field(Node* node) {
  67     DCHECK(node->opcode() == IrOpcode::kLoadField ||
  68            node->opcode() == IrOpcode::kStoreField);
  69     return OpParameter<FieldAccess>(node);
  70   }
  71   ElementAccess Element(Node* node) {
  72     DCHECK(node->opcode() == IrOpcode::kLoadElement ||
  73            node->opcode() == IrOpcode::kStoreElement);
  74     return OpParameter<ElementAccess>(node);
  75   }
  76   void CheckNotTyped(Node* node) {
  77     if (NodeProperties::IsTyped(node)) {
  78       std::ostringstream str;
  79       str << "TypeError: node #" << node->opcode() << ":"
  80           << node->op()->mnemonic() << " should never have a type";
  81       V8_Fatal(__FILE__, __LINE__, str.str().c_str());
  82     }
  83   }
  84   void CheckUpperIs(Node* node, Type* type) {
  85     if (typing == TYPED && !bounds(node).upper->Is(type)) {
  86       std::ostringstream str;
  87       str << "TypeError: node #" << node->opcode() << ":"
  88           << node->op()->mnemonic() << " upper bound ";
  89       bounds(node).upper->PrintTo(str);
  90       str << " is not ";
  91       type->PrintTo(str);
  92       V8_Fatal(__FILE__, __LINE__, str.str().c_str());
  93     }
  94   }
  95   void CheckUpperMaybe(Node* node, Type* type) {
  96     if (typing == TYPED && !bounds(node).upper->Maybe(type)) {
  97       std::ostringstream str;
  98       str << "TypeError: node #" << node->opcode() << ":"
  99           << node->op()->mnemonic() << " upper bound ";
 100       bounds(node).upper->PrintTo(str);
 101       str << " must intersect ";
 102       type->PrintTo(str);
 103       V8_Fatal(__FILE__, __LINE__, str.str().c_str());
 104     }
 105   }
 106   void CheckValueInputIs(Node* node, int i, Type* type) {
 107     Node* input = ValueInput(node, i);
 108     if (typing == TYPED && !bounds(input).upper->Is(type)) {
 109       std::ostringstream str;
 110       str << "TypeError: node #" << node->opcode() << ":"
 111           << node->op()->mnemonic() << "(input @" << i << " = "
 112           << input->opcode() << ":" << input->op()->mnemonic()
 113           << ") upper bound ";
 114       bounds(input).upper->PrintTo(str);
 115       str << " is not ";
 116       type->PrintTo(str);
 117       V8_Fatal(__FILE__, __LINE__, str.str().c_str());
 118     }
 119   }
 120 };
 121
 122
 123 void Verifier::Visitor::Pre(Node* node) {
 124   int value_count = node->op()->ValueInputCount();
 125   int context_count = OperatorProperties::GetContextInputCount(node->op());
 126   int frame_state_count =
 127       OperatorProperties::GetFrameStateInputCount(node->op());
 128   int effect_count = node->op()->EffectInputCount();
 129   int control_count = node->op()->ControlInputCount();
 130
 131   // Verify number of inputs matches up.
 132   int input_count = value_count + context_count + frame_state_count +
 133                     effect_count + control_count;
 134   CHECK_EQ(input_count, node->InputCount());
 135
 136   // Verify that frame state has been inserted for the nodes that need it.
 137   if (OperatorProperties::HasFrameStateInput(node->op())) {
 138     Node* frame_state = NodeProperties::GetFrameStateInput(node);
 139     CHECK(frame_state->opcode() == IrOpcode::kFrameState ||
 140           // kFrameState uses undefined as a sentinel.
 141           (node->opcode() == IrOpcode::kFrameState &&
 142            frame_state->opcode() == IrOpcode::kHeapConstant));
 143     CHECK(IsDefUseChainLinkPresent(frame_state, node));
 144     CHECK(IsUseDefChainLinkPresent(frame_state, node));
 145   }
 146
 147   // Verify all value inputs actually produce a value.
 148   for (int i = 0; i < value_count; ++i) {
 149     Node* value = NodeProperties::GetValueInput(node, i);
 150     CHECK(value->op()->ValueOutputCount() > 0);
 151     CHECK(IsDefUseChainLinkPresent(value, node));
 152     CHECK(IsUseDefChainLinkPresent(value, node));
 153   }
 154
 155   // Verify all context inputs are value nodes.
 156   for (int i = 0; i < context_count; ++i) {
 157     Node* context = NodeProperties::GetContextInput(node);
 158     CHECK(context->op()->ValueOutputCount() > 0);
 159     CHECK(IsDefUseChainLinkPresent(context, node));
 160     CHECK(IsUseDefChainLinkPresent(context, node));
 161   }
 162
 163   // Verify all effect inputs actually have an effect.
 164   for (int i = 0; i < effect_count; ++i) {
 165     Node* effect = NodeProperties::GetEffectInput(node);
 166     CHECK(effect->op()->EffectOutputCount() > 0);
 167     CHECK(IsDefUseChainLinkPresent(effect, node));
 168     CHECK(IsUseDefChainLinkPresent(effect, node));
 169   }
 170
 171   // Verify all control inputs are control nodes.
 172   for (int i = 0; i < control_count; ++i) {
 173     Node* control = NodeProperties::GetControlInput(node, i);
 174     CHECK(control->op()->ControlOutputCount() > 0);
 175     CHECK(IsDefUseChainLinkPresent(control, node));
 176     CHECK(IsUseDefChainLinkPresent(control, node));
 177   }
 178
 179   // Verify all successors are projections if multiple value outputs exist.
 180   if (node->op()->ValueOutputCount() > 1) {
 181     Node::Uses uses = node->uses();
 182     for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
 183       CHECK(!NodeProperties::IsValueEdge(it.edge()) ||
 184             (*it)->opcode() == IrOpcode::kProjection ||
 185             (*it)->opcode() == IrOpcode::kParameter);
 186     }
 187   }
 188
 189   switch (node->opcode()) {
 190     case IrOpcode::kStart:
 191       // Start has no inputs.
 192       CHECK_EQ(0, input_count);
 193       // Type is a tuple.
 194       // TODO(rossberg): Multiple outputs are currently typed as Internal.
 195       CheckUpperIs(node, Type::Internal());
 196       break;
 197     case IrOpcode::kEnd:
 198       // End has no outputs.
 199       CHECK(node->op()->ValueOutputCount() == 0);
 200       CHECK(node->op()->EffectOutputCount() == 0);
 201       CHECK(node->op()->ControlOutputCount() == 0);
 202       // Type is empty.
 203       CheckNotTyped(node);
 204       break;
 205     case IrOpcode::kDead:
 206       // Dead is never connected to the graph.
 207       UNREACHABLE();
 208     case IrOpcode::kBranch: {
 209       // Branch uses are IfTrue and IfFalse.
 210       Node::Uses uses = node->uses();
 211       int count_true = 0, count_false = 0;
 212       for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
 213         CHECK((*it)->opcode() == IrOpcode::kIfTrue ||
 214               (*it)->opcode() == IrOpcode::kIfFalse);
 215         if ((*it)->opcode() == IrOpcode::kIfTrue) ++count_true;
 216         if ((*it)->opcode() == IrOpcode::kIfFalse) ++count_false;
 217       }
 218       CHECK(count_true == 1 && count_false == 1);
 219       // Type is empty.
 220       CheckNotTyped(node);
 221       break;
 222     }
 223     case IrOpcode::kIfTrue:
 224     case IrOpcode::kIfFalse:
 225       CHECK_EQ(IrOpcode::kBranch,
 226                NodeProperties::GetControlInput(node, 0)->opcode());
 227       // Type is empty.
 228       CheckNotTyped(node);
 229       break;
 230     case IrOpcode::kLoop:
 231     case IrOpcode::kMerge:
 232       CHECK_EQ(control_count, input_count);
 233       // Type is empty.
 234       CheckNotTyped(node);
 235       break;
 236     case IrOpcode::kReturn:
 237       // TODO(rossberg): check successor is End
 238       // Type is empty.
 239       CheckNotTyped(node);
 240       break;
 241     case IrOpcode::kThrow:
 242       // TODO(rossberg): what are the constraints on these?
 243       // Type is empty.
 244       CheckNotTyped(node);
 245       break;
 246     case IrOpcode::kTerminate:
 247       // Type is empty.
 248       CheckNotTyped(node);
 249       CHECK_EQ(1, control_count);
 250       CHECK_EQ(input_count, 1 + effect_count);
 251       break;
 252
 253     // Common operators
 254     // ----------------
 255     case IrOpcode::kParameter: {
 256       // Parameters have the start node as inputs.
 257       CHECK_EQ(1, input_count);
 258       CHECK_EQ(IrOpcode::kStart,
 259                NodeProperties::GetValueInput(node, 0)->opcode());
 260       // Parameter has an input that produces enough values.
 261       int index = OpParameter<int>(node);
 262       Node* input = NodeProperties::GetValueInput(node, 0);
 263       // Currently, parameter indices start at -1 instead of 0.
 264       CHECK_GT(input->op()->ValueOutputCount(), index + 1);
 265       // Type can be anything.
 266       CheckUpperIs(node, Type::Any());
 267       break;
 268     }
 269     case IrOpcode::kInt32Constant:  // TODO(rossberg): rename Word32Constant?
 270       // Constants have no inputs.
 271       CHECK_EQ(0, input_count);
 272       // Type is a 32 bit integer, signed or unsigned.
 273       CheckUpperIs(node, Type::Integral32());
 274       break;
 275     case IrOpcode::kInt64Constant:
 276       // Constants have no inputs.
 277       CHECK_EQ(0, input_count);
 278       // Type is internal.
 279       // TODO(rossberg): Introduce proper Int64 type.
 280       CheckUpperIs(node, Type::Internal());
 281       break;
 282     case IrOpcode::kFloat32Constant:
 283     case IrOpcode::kFloat64Constant:
 284     case IrOpcode::kNumberConstant:
 285       // Constants have no inputs.
 286       CHECK_EQ(0, input_count);
 287       // Type is a number.
 288       CheckUpperIs(node, Type::Number());
 289       break;
 290     case IrOpcode::kHeapConstant:
 291       // Constants have no inputs.
 292       CHECK_EQ(0, input_count);
 293       // Type can be anything represented as a heap pointer.
 294       CheckUpperIs(node, Type::TaggedPtr());
 295       break;
 296     case IrOpcode::kExternalConstant:
 297       // Constants have no inputs.
 298       CHECK_EQ(0, input_count);
 299       // Type is considered internal.
 300       CheckUpperIs(node, Type::Internal());
 301       break;
 302     case IrOpcode::kProjection: {
 303       // Projection has an input that produces enough values.
 304       int index = static_cast<int>(OpParameter<size_t>(node->op()));
 305       Node* input = NodeProperties::GetValueInput(node, 0);
 306       CHECK_GT(input->op()->ValueOutputCount(), index);
 307       // Type can be anything.
 308       // TODO(rossberg): Introduce tuple types for this.
 309       // TODO(titzer): Convince rossberg not to.
 310       CheckUpperIs(node, Type::Any());
 311       break;
 312     }
 313     case IrOpcode::kSelect: {
 314       CHECK_EQ(0, effect_count);
 315       CHECK_EQ(0, control_count);
 316       CHECK_EQ(3, value_count);
 317       break;
 318     }
 319     case IrOpcode::kPhi: {
 320       // Phi input count matches parent control node.
 321       CHECK_EQ(0, effect_count);
 322       CHECK_EQ(1, control_count);
 323       Node* control = NodeProperties::GetControlInput(node, 0);
 324       CHECK_EQ(value_count, control->op()->ControlInputCount());
 325       CHECK_EQ(input_count, 1 + value_count);
 326       // Type must be subsumed by all input types.
 327       // TODO(rossberg): for now at least, narrowing does not really hold.
 328       /*
 329       for (int i = 0; i < value_count; ++i) {
 330         // TODO(rossberg, jarin): Figure out what to do about lower bounds.
 331         // CHECK(bounds(node).lower->Is(bounds(ValueInput(node, i)).lower));
 332         CHECK(bounds(ValueInput(node, i)).upper->Is(bounds(node).upper));
 333       }
 334       */
 335       break;
 336     }
 337     case IrOpcode::kEffectPhi: {
 338       // EffectPhi input count matches parent control node.
 339       CHECK_EQ(0, value_count);
 340       CHECK_EQ(1, control_count);
 341       Node* control = NodeProperties::GetControlInput(node, 0);
 342       CHECK_EQ(effect_count, control->op()->ControlInputCount());
 343       CHECK_EQ(input_count, 1 + effect_count);
 344       break;
 345     }
 346     case IrOpcode::kValueEffect:
 347       // TODO(rossberg): what are the constraints on these?
 348       break;
 349     case IrOpcode::kFinish: {
 350       // TODO(rossberg): what are the constraints on these?
 351       // Type must be subsumed by input type.
 352       if (typing == TYPED) {
 353         CHECK(bounds(ValueInput(node)).lower->Is(bounds(node).lower));
 354         CHECK(bounds(ValueInput(node)).upper->Is(bounds(node).upper));
 355       }
 356       break;
 357     }
 358     case IrOpcode::kFrameState:
 359       // TODO(jarin): what are the constraints on these?
 360       break;
 361     case IrOpcode::kStateValues:
 362       // TODO(jarin): what are the constraints on these?
 363       break;
 364     case IrOpcode::kCall:
 365       // TODO(rossberg): what are the constraints on these?
 366       break;
 367
 368     // JavaScript operators
 369     // --------------------
 370     case IrOpcode::kJSEqual:
 371     case IrOpcode::kJSNotEqual:
 372     case IrOpcode::kJSStrictEqual:
 373     case IrOpcode::kJSStrictNotEqual:
 374     case IrOpcode::kJSLessThan:
 375     case IrOpcode::kJSGreaterThan:
 376     case IrOpcode::kJSLessThanOrEqual:
 377     case IrOpcode::kJSGreaterThanOrEqual:
 378     case IrOpcode::kJSUnaryNot:
 379       // Type is Boolean.
 380       CheckUpperIs(node, Type::Boolean());
 381       break;
 382
 383     case IrOpcode::kJSBitwiseOr:
 384     case IrOpcode::kJSBitwiseXor:
 385     case IrOpcode::kJSBitwiseAnd:
 386     case IrOpcode::kJSShiftLeft:
 387     case IrOpcode::kJSShiftRight:
 388     case IrOpcode::kJSShiftRightLogical:
 389       // Type is 32 bit integral.
 390       CheckUpperIs(node, Type::Integral32());
 391       break;
 392     case IrOpcode::kJSAdd:
 393       // Type is Number or String.
 394       CheckUpperIs(node, Type::NumberOrString());
 395       break;
 396     case IrOpcode::kJSSubtract:
 397     case IrOpcode::kJSMultiply:
 398     case IrOpcode::kJSDivide:
 399     case IrOpcode::kJSModulus:
 400       // Type is Number.
 401       CheckUpperIs(node, Type::Number());
 402       break;
 403
 404     case IrOpcode::kJSToBoolean:
 405       // Type is Boolean.
 406       CheckUpperIs(node, Type::Boolean());
 407       break;
 408     case IrOpcode::kJSToNumber:
 409       // Type is Number.
 410       CheckUpperIs(node, Type::Number());
 411       break;
 412     case IrOpcode::kJSToString:
 413       // Type is String.
 414       CheckUpperIs(node, Type::String());
 415       break;
 416     case IrOpcode::kJSToName:
 417       // Type is Name.
 418       CheckUpperIs(node, Type::Name());
 419       break;
 420     case IrOpcode::kJSToObject:
 421       // Type is Receiver.
 422       CheckUpperIs(node, Type::Receiver());
 423       break;
 424
 425     case IrOpcode::kJSCreate:
 426       // Type is Object.
 427       CheckUpperIs(node, Type::Object());
 428       break;
 429     case IrOpcode::kJSLoadProperty:
 430     case IrOpcode::kJSLoadNamed:
 431       // Type can be anything.
 432       CheckUpperIs(node, Type::Any());
 433       break;
 434     case IrOpcode::kJSStoreProperty:
 435     case IrOpcode::kJSStoreNamed:
 436       // Type is empty.
 437       CheckNotTyped(node);
 438       break;
 439     case IrOpcode::kJSDeleteProperty:
 440     case IrOpcode::kJSHasProperty:
 441     case IrOpcode::kJSInstanceOf:
 442       // Type is Boolean.
 443       CheckUpperIs(node, Type::Boolean());
 444       break;
 445     case IrOpcode::kJSTypeOf:
 446       // Type is String.
 447       CheckUpperIs(node, Type::String());
 448       break;
 449
 450     case IrOpcode::kJSLoadContext:
 451       // Type can be anything.
 452       CheckUpperIs(node, Type::Any());
 453       break;
 454     case IrOpcode::kJSStoreContext:
 455       // Type is empty.
 456       CheckNotTyped(node);
 457       break;
 458     case IrOpcode::kJSCreateFunctionContext:
 459     case IrOpcode::kJSCreateCatchContext:
 460     case IrOpcode::kJSCreateWithContext:
 461     case IrOpcode::kJSCreateBlockContext:
 462     case IrOpcode::kJSCreateModuleContext:
 463     case IrOpcode::kJSCreateGlobalContext: {
 464       // Type is Context, and operand is Internal.
 465       Node* context = NodeProperties::GetContextInput(node);
 466       // TODO(rossberg): This should really be Is(Internal), but the typer
 467       // currently can't do backwards propagation.
 468       CheckUpperMaybe(context, Type::Internal());
 469       if (typing == TYPED) CHECK(bounds(node).upper->IsContext());
 470       break;
 471     }
 472
 473     case IrOpcode::kJSCallConstruct:
 474       // Type is Receiver.
 475       CheckUpperIs(node, Type::Receiver());
 476       break;
 477     case IrOpcode::kJSCallFunction:
 478     case IrOpcode::kJSCallRuntime:
 479     case IrOpcode::kJSYield:
 480     case IrOpcode::kJSDebugger:
 481       // Type can be anything.
 482       CheckUpperIs(node, Type::Any());
 483       break;
 484
 485     // Simplified operators
 486     // -------------------------------
 487     case IrOpcode::kBooleanNot:
 488       // Boolean -> Boolean
 489       CheckValueInputIs(node, 0, Type::Boolean());
 490       CheckUpperIs(node, Type::Boolean());
 491       break;
 492     case IrOpcode::kBooleanToNumber:
 493       // Boolean -> Number
 494       CheckValueInputIs(node, 0, Type::Boolean());
 495       CheckUpperIs(node, Type::Number());
 496       break;
 497     case IrOpcode::kNumberEqual:
 498     case IrOpcode::kNumberLessThan:
 499     case IrOpcode::kNumberLessThanOrEqual:
 500       // (Number, Number) -> Boolean
 501       CheckValueInputIs(node, 0, Type::Number());
 502       CheckValueInputIs(node, 1, Type::Number());
 503       CheckUpperIs(node, Type::Boolean());
 504       break;
 505     case IrOpcode::kNumberAdd:
 506     case IrOpcode::kNumberSubtract:
 507     case IrOpcode::kNumberMultiply:
 508     case IrOpcode::kNumberDivide:
 509     case IrOpcode::kNumberModulus:
 510       // (Number, Number) -> Number
 511       CheckValueInputIs(node, 0, Type::Number());
 512       CheckValueInputIs(node, 1, Type::Number());
 513       // TODO(rossberg): activate once we retype after opcode changes.
 514       // CheckUpperIs(node, Type::Number());
 515       break;
 516     case IrOpcode::kNumberToInt32:
 517       // Number -> Signed32
 518       CheckValueInputIs(node, 0, Type::Number());
 519       CheckUpperIs(node, Type::Signed32());
 520       break;
 521     case IrOpcode::kNumberToUint32:
 522       // Number -> Unsigned32
 523       CheckValueInputIs(node, 0, Type::Number());
 524       CheckUpperIs(node, Type::Unsigned32());
 525       break;
 526     case IrOpcode::kStringEqual:
 527     case IrOpcode::kStringLessThan:
 528     case IrOpcode::kStringLessThanOrEqual:
 529       // (String, String) -> Boolean
 530       CheckValueInputIs(node, 0, Type::String());
 531       CheckValueInputIs(node, 1, Type::String());
 532       CheckUpperIs(node, Type::Boolean());
 533       break;
 534     case IrOpcode::kStringAdd:
 535       // (String, String) -> String
 536       CheckValueInputIs(node, 0, Type::String());
 537       CheckValueInputIs(node, 1, Type::String());
 538       CheckUpperIs(node, Type::String());
 539       break;
 540     case IrOpcode::kReferenceEqual: {
 541       // (Unique, Any) -> Boolean  and
 542       // (Any, Unique) -> Boolean
 543       if (typing == TYPED) {
 544         CHECK(bounds(ValueInput(node, 0)).upper->Is(Type::Unique()) ||
 545               bounds(ValueInput(node, 1)).upper->Is(Type::Unique()));
 546       }
 547       CheckUpperIs(node, Type::Boolean());
 548       break;
 549     }
 550     case IrOpcode::kObjectIsSmi:
 551       CheckValueInputIs(node, 0, Type::Any());
 552       CheckUpperIs(node, Type::Boolean());
 553       break;
 554     case IrOpcode::kObjectIsNonNegativeSmi:
 555       CheckValueInputIs(node, 0, Type::Any());
 556       CheckUpperIs(node, Type::Boolean());
 557       break;
 558
 559     case IrOpcode::kChangeTaggedToInt32: {
 560       // Signed32 /\ Tagged -> Signed32 /\ UntaggedInt32
 561       // TODO(neis): Activate once ChangeRepresentation works in typer.
 562       // Type* from = Type::Intersect(Type::Signed32(), Type::Tagged());
 563       // Type* to = Type::Intersect(Type::Signed32(), Type::UntaggedInt32());
 564       // CheckValueInputIs(node, 0, from));
 565       // CheckUpperIs(node, to));
 566       break;
 567     }
 568     case IrOpcode::kChangeTaggedToUint32: {
 569       // Unsigned32 /\ Tagged -> Unsigned32 /\ UntaggedInt32
 570       // TODO(neis): Activate once ChangeRepresentation works in typer.
 571       // Type* from = Type::Intersect(Type::Unsigned32(), Type::Tagged());
 572       // Type* to =Type::Intersect(Type::Unsigned32(), Type::UntaggedInt32());
 573       // CheckValueInputIs(node, 0, from));
 574       // CheckUpperIs(node, to));
 575       break;
 576     }
 577     case IrOpcode::kChangeTaggedToFloat64: {
 578       // Number /\ Tagged -> Number /\ UntaggedFloat64
 579       // TODO(neis): Activate once ChangeRepresentation works in typer.
 580       // Type* from = Type::Intersect(Type::Number(), Type::Tagged());
 581       // Type* to = Type::Intersect(Type::Number(), Type::UntaggedFloat64());
 582       // CheckValueInputIs(node, 0, from));
 583       // CheckUpperIs(node, to));
 584       break;
 585     }
 586     case IrOpcode::kChangeInt32ToTagged: {
 587       // Signed32 /\ UntaggedInt32 -> Signed32 /\ Tagged
 588       // TODO(neis): Activate once ChangeRepresentation works in typer.
 589       // Type* from =Type::Intersect(Type::Signed32(), Type::UntaggedInt32());
 590       // Type* to = Type::Intersect(Type::Signed32(), Type::Tagged());
 591       // CheckValueInputIs(node, 0, from));
 592       // CheckUpperIs(node, to));
 593       break;
 594     }
 595     case IrOpcode::kChangeUint32ToTagged: {
 596       // Unsigned32 /\ UntaggedInt32 -> Unsigned32 /\ Tagged
 597       // TODO(neis): Activate once ChangeRepresentation works in typer.
 598       // Type* from=Type::Intersect(Type::Unsigned32(),Type::UntaggedInt32());
 599       // Type* to = Type::Intersect(Type::Unsigned32(), Type::Tagged());
 600       // CheckValueInputIs(node, 0, from));
 601       // CheckUpperIs(node, to));
 602       break;
 603     }
 604     case IrOpcode::kChangeFloat64ToTagged: {
 605       // Number /\ UntaggedFloat64 -> Number /\ Tagged
 606       // TODO(neis): Activate once ChangeRepresentation works in typer.
 607       // Type* from =Type::Intersect(Type::Number(), Type::UntaggedFloat64());
 608       // Type* to = Type::Intersect(Type::Number(), Type::Tagged());
 609       // CheckValueInputIs(node, 0, from));
 610       // CheckUpperIs(node, to));
 611       break;
 612     }
 613     case IrOpcode::kChangeBoolToBit: {
 614       // Boolean /\ TaggedPtr -> Boolean /\ UntaggedInt1
 615       // TODO(neis): Activate once ChangeRepresentation works in typer.
 616       // Type* from = Type::Intersect(Type::Boolean(), Type::TaggedPtr());
 617       // Type* to = Type::Intersect(Type::Boolean(), Type::UntaggedInt1());
 618       // CheckValueInputIs(node, 0, from));
 619       // CheckUpperIs(node, to));
 620       break;
 621     }
 622     case IrOpcode::kChangeBitToBool: {
 623       // Boolean /\ UntaggedInt1 -> Boolean /\ TaggedPtr
 624       // TODO(neis): Activate once ChangeRepresentation works in typer.
 625       // Type* from = Type::Intersect(Type::Boolean(), Type::UntaggedInt1());
 626       // Type* to = Type::Intersect(Type::Boolean(), Type::TaggedPtr());
 627       // CheckValueInputIs(node, 0, from));
 628       // CheckUpperIs(node, to));
 629       break;
 630     }
 631
 632     case IrOpcode::kLoadField:
 633       // Object -> fieldtype
 634       // TODO(rossberg): activate once machine ops are typed.
 635       // CheckValueInputIs(node, 0, Type::Object());
 636       // CheckUpperIs(node, Field(node).type));
 637       break;
 638     case IrOpcode::kLoadElement:
 639       // Object -> elementtype
 640       // TODO(rossberg): activate once machine ops are typed.
 641       // CheckValueInputIs(node, 0, Type::Object());
 642       // CheckUpperIs(node, Element(node).type));
 643       break;
 644     case IrOpcode::kStoreField:
 645       // (Object, fieldtype) -> _|_
 646       // TODO(rossberg): activate once machine ops are typed.
 647       // CheckValueInputIs(node, 0, Type::Object());
 648       // CheckValueInputIs(node, 1, Field(node).type));
 649       CheckNotTyped(node);
 650       break;
 651     case IrOpcode::kStoreElement:
 652       // (Object, elementtype) -> _|_
 653       // TODO(rossberg): activate once machine ops are typed.
 654       // CheckValueInputIs(node, 0, Type::Object());
 655       // CheckValueInputIs(node, 1, Element(node).type));
 656       CheckNotTyped(node);
 657       break;
 658
 659     // Machine operators
 660     // -----------------------
 661     case IrOpcode::kLoad:
 662     case IrOpcode::kStore:
 663     case IrOpcode::kWord32And:
 664     case IrOpcode::kWord32Or:
 665     case IrOpcode::kWord32Xor:
 666     case IrOpcode::kWord32Shl:
 667     case IrOpcode::kWord32Shr:
 668     case IrOpcode::kWord32Sar:
 669     case IrOpcode::kWord32Ror:
 670     case IrOpcode::kWord32Equal:
 671     case IrOpcode::kWord64And:
 672     case IrOpcode::kWord64Or:
 673     case IrOpcode::kWord64Xor:
 674     case IrOpcode::kWord64Shl:
 675     case IrOpcode::kWord64Shr:
 676     case IrOpcode::kWord64Sar:
 677     case IrOpcode::kWord64Ror:
 678     case IrOpcode::kWord64Equal:
 679     case IrOpcode::kInt32Add:
 680     case IrOpcode::kInt32AddWithOverflow:
 681     case IrOpcode::kInt32Sub:
 682     case IrOpcode::kInt32SubWithOverflow:
 683     case IrOpcode::kInt32Mul:
 684     case IrOpcode::kInt32MulHigh:
 685     case IrOpcode::kInt32Div:
 686     case IrOpcode::kInt32Mod:
 687     case IrOpcode::kInt32LessThan:
 688     case IrOpcode::kInt32LessThanOrEqual:
 689     case IrOpcode::kUint32Div:
 690     case IrOpcode::kUint32Mod:
 691     case IrOpcode::kUint32MulHigh:
 692     case IrOpcode::kUint32LessThan:
 693     case IrOpcode::kUint32LessThanOrEqual:
 694     case IrOpcode::kInt64Add:
 695     case IrOpcode::kInt64Sub:
 696     case IrOpcode::kInt64Mul:
 697     case IrOpcode::kInt64Div:
 698     case IrOpcode::kInt64Mod:
 699     case IrOpcode::kInt64LessThan:
 700     case IrOpcode::kInt64LessThanOrEqual:
 701     case IrOpcode::kUint64Div:
 702     case IrOpcode::kUint64Mod:
 703     case IrOpcode::kUint64LessThan:
 704     case IrOpcode::kFloat64Add:
 705     case IrOpcode::kFloat64Sub:
 706     case IrOpcode::kFloat64Mul:
 707     case IrOpcode::kFloat64Div:
 708     case IrOpcode::kFloat64Mod:
 709     case IrOpcode::kFloat64Sqrt:
 710     case IrOpcode::kFloat64Floor:
 711     case IrOpcode::kFloat64Ceil:
 712     case IrOpcode::kFloat64RoundTruncate:
 713     case IrOpcode::kFloat64RoundTiesAway:
 714     case IrOpcode::kFloat64Equal:
 715     case IrOpcode::kFloat64LessThan:
 716     case IrOpcode::kFloat64LessThanOrEqual:
 717     case IrOpcode::kTruncateInt64ToInt32:
 718     case IrOpcode::kTruncateFloat64ToFloat32:
 719     case IrOpcode::kTruncateFloat64ToInt32:
 720     case IrOpcode::kChangeInt32ToInt64:
 721     case IrOpcode::kChangeUint32ToUint64:
 722     case IrOpcode::kChangeInt32ToFloat64:
 723     case IrOpcode::kChangeUint32ToFloat64:
 724     case IrOpcode::kChangeFloat32ToFloat64:
 725     case IrOpcode::kChangeFloat64ToInt32:
 726     case IrOpcode::kChangeFloat64ToUint32:
 727     case IrOpcode::kLoadStackPointer:
 728       // TODO(rossberg): Check.
 729       break;
 730   }
 731 }
 732
 733
 734 void Verifier::Run(Graph* graph, Typing typing) {
 735   Visitor visitor(graph->zone(), typing);
 736   CHECK_NE(NULL, graph->start());
 737   CHECK_NE(NULL, graph->end());
 738   graph->VisitNodeInputsFromEnd(&visitor);
 739 }
 740
 741
 742 // -----------------------------------------------------------------------------
 743
 744 static bool HasDominatingDef(Schedule* schedule, Node* node,
 745                              BasicBlock* container, BasicBlock* use_block,
 746                              int use_pos) {
 747   BasicBlock* block = use_block;
 748   while (true) {
 749     while (use_pos >= 0) {
 750       if (block->NodeAt(use_pos) == node) return true;
 751       use_pos--;
 752     }
 753     block = block->dominator();
 754     if (block == NULL) break;
 755     use_pos = static_cast<int>(block->NodeCount()) - 1;
 756     if (node == block->control_input()) return true;
 757   }
 758   return false;
 759 }
 760
 761
 762 static bool Dominates(Schedule* schedule, Node* dominator, Node* dominatee) {
 763   BasicBlock* dom = schedule->block(dominator);
 764   BasicBlock* sub = schedule->block(dominatee);
 765   while (sub != NULL) {
 766     if (sub == dom) {
 767       return true;
 768     }
 769     sub = sub->dominator();
 770   }
 771   return false;
 772 }
 773
 774
 775 static void CheckInputsDominate(Schedule* schedule, BasicBlock* block,
 776                                 Node* node, int use_pos) {
 777   for (int j = node->op()->ValueInputCount() - 1; j >= 0; j--) {
 778     BasicBlock* use_block = block;
 779     if (node->opcode() == IrOpcode::kPhi) {
 780       use_block = use_block->PredecessorAt(j);
 781       use_pos = static_cast<int>(use_block->NodeCount()) - 1;
 782     }
 783     Node* input = node->InputAt(j);
 784     if (!HasDominatingDef(schedule, node->InputAt(j), block, use_block,
 785                           use_pos)) {
 786       V8_Fatal(__FILE__, __LINE__,
 787                "Node #%d:%s in B%d is not dominated by input@%d #%d:%s",
 788                node->id(), node->op()->mnemonic(), block->id().ToInt(), j,
 789                input->id(), input->op()->mnemonic());
 790     }
 791   }
 792   // Ensure that nodes are dominated by their control inputs;
 793   // kEnd is an exception, as unreachable blocks resulting from kMerge
 794   // are not in the RPO.
 795   if (node->op()->ControlInputCount() == 1 &&
 796       node->opcode() != IrOpcode::kEnd) {
 797     Node* ctl = NodeProperties::GetControlInput(node);
 798     if (!Dominates(schedule, ctl, node)) {
 799       V8_Fatal(__FILE__, __LINE__,
 800                "Node #%d:%s in B%d is not dominated by control input #%d:%s",
 801                node->id(), node->op()->mnemonic(), block->id(), ctl->id(),
 802                ctl->op()->mnemonic());
 803     }
 804   }
 805 }
 806
 807
 808 void ScheduleVerifier::Run(Schedule* schedule) {
 809   const size_t count = schedule->BasicBlockCount();
 810   Zone tmp_zone(schedule->zone()->isolate());
 811   Zone* zone = &tmp_zone;
 812   BasicBlock* start = schedule->start();
 813   BasicBlockVector* rpo_order = schedule->rpo_order();
 814
 815   // Verify the RPO order contains only blocks from this schedule.
 816   CHECK_GE(count, rpo_order->size());
 817   for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
 818        ++b) {
 819     CHECK_EQ((*b), schedule->GetBlockById((*b)->id()));
 820     // All predecessors and successors should be in rpo and in this schedule.
 821     for (BasicBlock::Predecessors::iterator j = (*b)->predecessors_begin();
 822          j != (*b)->predecessors_end(); ++j) {
 823       CHECK_GE((*j)->rpo_number(), 0);
 824       CHECK_EQ((*j), schedule->GetBlockById((*j)->id()));
 825     }
 826     for (BasicBlock::Successors::iterator j = (*b)->successors_begin();
 827          j != (*b)->successors_end(); ++j) {
 828       CHECK_GE((*j)->rpo_number(), 0);
 829       CHECK_EQ((*j), schedule->GetBlockById((*j)->id()));
 830     }
 831   }
 832
 833   // Verify RPO numbers of blocks.
 834   CHECK_EQ(start, rpo_order->at(0));  // Start should be first.
 835   for (size_t b = 0; b < rpo_order->size(); b++) {
 836     BasicBlock* block = rpo_order->at(b);
 837     CHECK_EQ(static_cast<int>(b), block->rpo_number());
 838     BasicBlock* dom = block->dominator();
 839     if (b == 0) {
 840       // All blocks except start should have a dominator.
 841       CHECK_EQ(NULL, dom);
 842     } else {
 843       // Check that the immediate dominator appears somewhere before the block.
 844       CHECK_NE(NULL, dom);
 845       CHECK_LT(dom->rpo_number(), block->rpo_number());
 846     }
 847   }
 848
 849   // Verify that all blocks reachable from start are in the RPO.
 850   BoolVector marked(static_cast<int>(count), false, zone);
 851   {
 852     ZoneQueue<BasicBlock*> queue(zone);
 853     queue.push(start);
 854     marked[start->id().ToSize()] = true;
 855     while (!queue.empty()) {
 856       BasicBlock* block = queue.front();
 857       queue.pop();
 858       for (size_t s = 0; s < block->SuccessorCount(); s++) {
 859         BasicBlock* succ = block->SuccessorAt(s);
 860         if (!marked[succ->id().ToSize()]) {
 861           marked[succ->id().ToSize()] = true;
 862           queue.push(succ);
 863         }
 864       }
 865     }
 866   }
 867   // Verify marked blocks are in the RPO.
 868   for (size_t i = 0; i < count; i++) {
 869     BasicBlock* block = schedule->GetBlockById(BasicBlock::Id::FromSize(i));
 870     if (marked[i]) {
 871       CHECK_GE(block->rpo_number(), 0);
 872       CHECK_EQ(block, rpo_order->at(block->rpo_number()));
 873     }
 874   }
 875   // Verify RPO blocks are marked.
 876   for (size_t b = 0; b < rpo_order->size(); b++) {
 877     CHECK(marked[rpo_order->at(b)->id().ToSize()]);
 878   }
 879
 880   {
 881     // Verify the dominance relation.
 882     ZoneVector<BitVector*> dominators(zone);
 883     dominators.resize(count, NULL);
 884
 885     // Compute a set of all the nodes that dominate a given node by using
 886     // a forward fixpoint. O(n^2).
 887     ZoneQueue<BasicBlock*> queue(zone);
 888     queue.push(start);
 889     dominators[start->id().ToSize()] =
 890         new (zone) BitVector(static_cast<int>(count), zone);
 891     while (!queue.empty()) {
 892       BasicBlock* block = queue.front();
 893       queue.pop();
 894       BitVector* block_doms = dominators[block->id().ToSize()];
 895       BasicBlock* idom = block->dominator();
 896       if (idom != NULL && !block_doms->Contains(idom->id().ToInt())) {
 897         V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d",
 898                  block->id().ToInt(), idom->id().ToInt());
 899       }
 900       for (size_t s = 0; s < block->SuccessorCount(); s++) {
 901         BasicBlock* succ = block->SuccessorAt(s);
 902         BitVector* succ_doms = dominators[succ->id().ToSize()];
 903
 904         if (succ_doms == NULL) {
 905           // First time visiting the node. S.doms = B U B.doms
 906           succ_doms = new (zone) BitVector(static_cast<int>(count), zone);
 907           succ_doms->CopyFrom(*block_doms);
 908           succ_doms->Add(block->id().ToInt());
 909           dominators[succ->id().ToSize()] = succ_doms;
 910           queue.push(succ);
 911         } else {
 912           // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms)
 913           bool had = succ_doms->Contains(block->id().ToInt());
 914           if (had) succ_doms->Remove(block->id().ToInt());
 915           if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ);
 916           if (had) succ_doms->Add(block->id().ToInt());
 917         }
 918       }
 919     }
 920
 921     // Verify the immediateness of dominators.
 922     for (BasicBlockVector::iterator b = rpo_order->begin();
 923          b != rpo_order->end(); ++b) {
 924       BasicBlock* block = *b;
 925       BasicBlock* idom = block->dominator();
 926       if (idom == NULL) continue;
 927       BitVector* block_doms = dominators[block->id().ToSize()];
 928
 929       for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) {
 930         BasicBlock* dom =
 931             schedule->GetBlockById(BasicBlock::Id::FromInt(it.Current()));
 932         if (dom != idom &&
 933             !dominators[idom->id().ToSize()]->Contains(dom->id().ToInt())) {
 934           V8_Fatal(__FILE__, __LINE__,
 935                    "Block B%d is not immediately dominated by B%d",
 936                    block->id().ToInt(), idom->id().ToInt());
 937         }
 938       }
 939     }
 940   }
 941
 942   // Verify phis are placed in the block of their control input.
 943   for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
 944        ++b) {
 945     for (BasicBlock::const_iterator i = (*b)->begin(); i != (*b)->end(); ++i) {
 946       Node* phi = *i;
 947       if (phi->opcode() != IrOpcode::kPhi) continue;
 948       // TODO(titzer): Nasty special case. Phis from RawMachineAssembler
 949       // schedules don't have control inputs.
 950       if (phi->InputCount() > phi->op()->ValueInputCount()) {
 951         Node* control = NodeProperties::GetControlInput(phi);
 952         CHECK(control->opcode() == IrOpcode::kMerge ||
 953               control->opcode() == IrOpcode::kLoop);
 954         CHECK_EQ((*b), schedule->block(control));
 955       }
 956     }
 957   }
 958
 959   // Verify that all uses are dominated by their definitions.
 960   for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
 961        ++b) {
 962     BasicBlock* block = *b;
 963
 964     // Check inputs to control for this block.
 965     Node* control = block->control_input();
 966     if (control != NULL) {
 967       CHECK_EQ(block, schedule->block(control));
 968       CheckInputsDominate(schedule, block, control,
 969                           static_cast<int>(block->NodeCount()) - 1);
 970     }
 971     // Check inputs for all nodes in the block.
 972     for (size_t i = 0; i < block->NodeCount(); i++) {
 973       Node* node = block->NodeAt(i);
 974       CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1);
 975     }
 976   }
 977 }
 978 }
 979 }
 980 }  // namespace v8::internal::compiler