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