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   for (int i = 0; i < frame_state_count; i++) {
 129     Node* frame_state = NodeProperties::GetFrameStateInput(node, i);
 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::kIfSuccess:
 232     case IrOpcode::kIfException: {
 233       // IfSuccess and IfException continuation only on throwing nodes.
 234       Node* input = NodeProperties::GetControlInput(node, 0);
 235       CHECK(!input->op()->HasProperty(Operator::kNoThrow));
 236       // Type is empty.
 237       CheckNotTyped(node);
 238       break;
 239     }
 240     case IrOpcode::kSwitch: {
 241       // Switch uses are Case and Default.
 242       int count_case = 0, count_default = 0;
 243       for (auto use : node->uses()) {
 244         switch (use->opcode()) {
 245           case IrOpcode::kIfValue: {
 246             for (auto user : node->uses()) {
 247               if (user != use && user->opcode() == IrOpcode::kIfValue) {
 248                 CHECK_NE(OpParameter<int32_t>(use->op()),
 249                          OpParameter<int32_t>(user->op()));
 250               }
 251             }
 252             ++count_case;
 253             break;
 254           }
 255           case IrOpcode::kIfDefault: {
 256             ++count_default;
 257             break;
 258           }
 259           default: {
 260             UNREACHABLE();
 261             break;
 262           }
 263         }
 264       }
 265       CHECK_LE(1, count_case);
 266       CHECK_EQ(1, count_default);
 267       CHECK_EQ(node->op()->ControlOutputCount(), count_case + count_default);
 268       // Type is empty.
 269       CheckNotTyped(node);
 270       break;
 271     }
 272     case IrOpcode::kIfValue:
 273     case IrOpcode::kIfDefault:
 274       CHECK_EQ(IrOpcode::kSwitch,
 275                NodeProperties::GetControlInput(node)->opcode());
 276       // Type is empty.
 277       CheckNotTyped(node);
 278       break;
 279     case IrOpcode::kLoop:
 280     case IrOpcode::kMerge:
 281       CHECK_EQ(control_count, input_count);
 282       // Type is empty.
 283       CheckNotTyped(node);
 284       break;
 285     case IrOpcode::kDeoptimize:
 286       // TODO(rossberg): check successor is End
 287       // Type is empty.
 288       CheckNotTyped(node);
 289     case IrOpcode::kReturn:
 290       // TODO(rossberg): check successor is End
 291       // Type is empty.
 292       CheckNotTyped(node);
 293       break;
 294     case IrOpcode::kThrow:
 295       // TODO(rossberg): what are the constraints on these?
 296       // Type is empty.
 297       CheckNotTyped(node);
 298       break;
 299     case IrOpcode::kOsrNormalEntry:
 300     case IrOpcode::kOsrLoopEntry:
 301       // Osr entries have
 302       CHECK_EQ(1, effect_count);
 303       CHECK_EQ(1, control_count);
 304       // Type is empty.
 305       CheckNotTyped(node);
 306       break;
 307
 308     // Common operators
 309     // ----------------
 310     case IrOpcode::kParameter: {
 311       // Parameters have the start node as inputs.
 312       CHECK_EQ(1, input_count);
 313       CHECK_EQ(IrOpcode::kStart,
 314                NodeProperties::GetValueInput(node, 0)->opcode());
 315       // Parameter has an input that produces enough values.
 316       int index = OpParameter<int>(node);
 317       Node* input = NodeProperties::GetValueInput(node, 0);
 318       // Currently, parameter indices start at -1 instead of 0.
 319       CHECK_GT(input->op()->ValueOutputCount(), index + 1);
 320       // Type can be anything.
 321       CheckUpperIs(node, Type::Any());
 322       break;
 323     }
 324     case IrOpcode::kInt32Constant:  // TODO(rossberg): rename Word32Constant?
 325       // Constants have no inputs.
 326       CHECK_EQ(0, input_count);
 327       // Type is a 32 bit integer, signed or unsigned.
 328       CheckUpperIs(node, Type::Integral32());
 329       break;
 330     case IrOpcode::kInt64Constant:
 331       // Constants have no inputs.
 332       CHECK_EQ(0, input_count);
 333       // Type is internal.
 334       // TODO(rossberg): Introduce proper Int64 type.
 335       CheckUpperIs(node, Type::Internal());
 336       break;
 337     case IrOpcode::kFloat32Constant:
 338     case IrOpcode::kFloat64Constant:
 339     case IrOpcode::kNumberConstant:
 340       // Constants have no inputs.
 341       CHECK_EQ(0, input_count);
 342       // Type is a number.
 343       CheckUpperIs(node, Type::Number());
 344       break;
 345     case IrOpcode::kHeapConstant:
 346       // Constants have no inputs.
 347       CHECK_EQ(0, input_count);
 348       // Type can be anything represented as a heap pointer.
 349       CheckUpperIs(node, Type::TaggedPointer());
 350       break;
 351     case IrOpcode::kExternalConstant:
 352       // Constants have no inputs.
 353       CHECK_EQ(0, input_count);
 354       // Type is considered internal.
 355       CheckUpperIs(node, Type::Internal());
 356       break;
 357     case IrOpcode::kOsrValue:
 358       // OSR values have a value and a control input.
 359       CHECK_EQ(1, control_count);
 360       CHECK_EQ(1, input_count);
 361       // Type is merged from other values in the graph and could be any.
 362       CheckUpperIs(node, Type::Any());
 363       break;
 364     case IrOpcode::kProjection: {
 365       // Projection has an input that produces enough values.
 366       int index = static_cast<int>(ProjectionIndexOf(node->op()));
 367       Node* input = NodeProperties::GetValueInput(node, 0);
 368       CHECK_GT(input->op()->ValueOutputCount(), index);
 369       // Type can be anything.
 370       // TODO(rossberg): Introduce tuple types for this.
 371       // TODO(titzer): Convince rossberg not to.
 372       CheckUpperIs(node, Type::Any());
 373       break;
 374     }
 375     case IrOpcode::kSelect: {
 376       CHECK_EQ(0, effect_count);
 377       CHECK_EQ(0, control_count);
 378       CHECK_EQ(3, value_count);
 379       break;
 380     }
 381     case IrOpcode::kPhi: {
 382       // Phi input count matches parent control node.
 383       CHECK_EQ(0, effect_count);
 384       CHECK_EQ(1, control_count);
 385       Node* control = NodeProperties::GetControlInput(node, 0);
 386       CHECK_EQ(value_count, control->op()->ControlInputCount());
 387       CHECK_EQ(input_count, 1 + value_count);
 388       // Type must be subsumed by all input types.
 389       // TODO(rossberg): for now at least, narrowing does not really hold.
 390       /*
 391       for (int i = 0; i < value_count; ++i) {
 392         // TODO(rossberg, jarin): Figure out what to do about lower bounds.
 393         // CHECK(bounds(node).lower->Is(bounds(ValueInput(node, i)).lower));
 394         CHECK(bounds(ValueInput(node, i)).upper->Is(bounds(node).upper));
 395       }
 396       */
 397       break;
 398     }
 399     case IrOpcode::kEffectPhi: {
 400       // EffectPhi input count matches parent control node.
 401       CHECK_EQ(0, value_count);
 402       CHECK_EQ(1, control_count);
 403       Node* control = NodeProperties::GetControlInput(node, 0);
 404       CHECK_EQ(effect_count, control->op()->ControlInputCount());
 405       CHECK_EQ(input_count, 1 + effect_count);
 406       break;
 407     }
 408     case IrOpcode::kEffectSet: {
 409       CHECK_EQ(0, value_count);
 410       CHECK_EQ(0, control_count);
 411       CHECK_LT(1, effect_count);
 412       break;
 413     }
 414     case IrOpcode::kValueEffect:
 415       // TODO(rossberg): what are the constraints on these?
 416       break;
 417     case IrOpcode::kFinish: {
 418       // TODO(rossberg): what are the constraints on these?
 419       // Type must be subsumed by input type.
 420       if (typing == TYPED) {
 421         CHECK(bounds(ValueInput(node)).lower->Is(bounds(node).lower));
 422         CHECK(bounds(ValueInput(node)).upper->Is(bounds(node).upper));
 423       }
 424       break;
 425     }
 426     case IrOpcode::kFrameState:
 427       // TODO(jarin): what are the constraints on these?
 428       break;
 429     case IrOpcode::kStateValues:
 430     case IrOpcode::kTypedStateValues:
 431       // TODO(jarin): what are the constraints on these?
 432       break;
 433     case IrOpcode::kCall:
 434       // TODO(rossberg): what are the constraints on these?
 435       break;
 436
 437     // JavaScript operators
 438     // --------------------
 439     case IrOpcode::kJSEqual:
 440     case IrOpcode::kJSNotEqual:
 441     case IrOpcode::kJSStrictEqual:
 442     case IrOpcode::kJSStrictNotEqual:
 443     case IrOpcode::kJSLessThan:
 444     case IrOpcode::kJSGreaterThan:
 445     case IrOpcode::kJSLessThanOrEqual:
 446     case IrOpcode::kJSGreaterThanOrEqual:
 447     case IrOpcode::kJSUnaryNot:
 448       // Type is Boolean.
 449       CheckUpperIs(node, Type::Boolean());
 450       break;
 451
 452     case IrOpcode::kJSBitwiseOr:
 453     case IrOpcode::kJSBitwiseXor:
 454     case IrOpcode::kJSBitwiseAnd:
 455     case IrOpcode::kJSShiftLeft:
 456     case IrOpcode::kJSShiftRight:
 457     case IrOpcode::kJSShiftRightLogical:
 458       // Type is 32 bit integral.
 459       CheckUpperIs(node, Type::Integral32());
 460       break;
 461     case IrOpcode::kJSAdd:
 462       // Type is Number or String.
 463       CheckUpperIs(node, Type::NumberOrString());
 464       break;
 465     case IrOpcode::kJSSubtract:
 466     case IrOpcode::kJSMultiply:
 467     case IrOpcode::kJSDivide:
 468     case IrOpcode::kJSModulus:
 469       // Type is Number.
 470       CheckUpperIs(node, Type::Number());
 471       break;
 472
 473     case IrOpcode::kJSToBoolean:
 474       // Type is Boolean.
 475       CheckUpperIs(node, Type::Boolean());
 476       break;
 477     case IrOpcode::kJSToNumber:
 478       // Type is Number.
 479       CheckUpperIs(node, Type::Number());
 480       break;
 481     case IrOpcode::kJSToString:
 482       // Type is String.
 483       CheckUpperIs(node, Type::String());
 484       break;
 485     case IrOpcode::kJSToName:
 486       // Type is Name.
 487       CheckUpperIs(node, Type::Name());
 488       break;
 489     case IrOpcode::kJSToObject:
 490       // Type is Receiver.
 491       CheckUpperIs(node, Type::Receiver());
 492       break;
 493
 494     case IrOpcode::kJSCreate:
 495       // Type is Object.
 496       CheckUpperIs(node, Type::Object());
 497       break;
 498     case IrOpcode::kJSLoadProperty:
 499     case IrOpcode::kJSLoadNamed:
 500       // Type can be anything.
 501       CheckUpperIs(node, Type::Any());
 502       break;
 503     case IrOpcode::kJSStoreProperty:
 504     case IrOpcode::kJSStoreNamed:
 505       // Type is empty.
 506       CheckNotTyped(node);
 507       break;
 508     case IrOpcode::kJSDeleteProperty:
 509     case IrOpcode::kJSHasProperty:
 510     case IrOpcode::kJSInstanceOf:
 511       // Type is Boolean.
 512       CheckUpperIs(node, Type::Boolean());
 513       break;
 514     case IrOpcode::kJSTypeOf:
 515       // Type is String.
 516       CheckUpperIs(node, Type::String());
 517       break;
 518
 519     case IrOpcode::kJSLoadContext:
 520       // Type can be anything.
 521       CheckUpperIs(node, Type::Any());
 522       break;
 523     case IrOpcode::kJSStoreContext:
 524       // Type is empty.
 525       CheckNotTyped(node);
 526       break;
 527     case IrOpcode::kJSCreateFunctionContext:
 528     case IrOpcode::kJSCreateCatchContext:
 529     case IrOpcode::kJSCreateWithContext:
 530     case IrOpcode::kJSCreateBlockContext:
 531     case IrOpcode::kJSCreateModuleContext:
 532     case IrOpcode::kJSCreateScriptContext: {
 533       // Type is Context, and operand is Internal.
 534       Node* context = NodeProperties::GetContextInput(node);
 535       // TODO(rossberg): This should really be Is(Internal), but the typer
 536       // currently can't do backwards propagation.
 537       CheckUpperMaybe(context, Type::Internal());
 538       if (typing == TYPED) CHECK(bounds(node).upper->IsContext());
 539       break;
 540     }
 541
 542     case IrOpcode::kJSCallConstruct:
 543       // Type is Receiver.
 544       CheckUpperIs(node, Type::Receiver());
 545       break;
 546     case IrOpcode::kJSCallFunction:
 547     case IrOpcode::kJSCallRuntime:
 548     case IrOpcode::kJSYield:
 549       // Type can be anything.
 550       CheckUpperIs(node, Type::Any());
 551       break;
 552
 553     case IrOpcode::kJSStackCheck:
 554       // Type is empty.
 555       CheckNotTyped(node);
 556       break;
 557
 558     // Simplified operators
 559     // -------------------------------
 560     case IrOpcode::kBooleanNot:
 561       // Boolean -> Boolean
 562       CheckValueInputIs(node, 0, Type::Boolean());
 563       CheckUpperIs(node, Type::Boolean());
 564       break;
 565     case IrOpcode::kBooleanToNumber:
 566       // Boolean -> Number
 567       CheckValueInputIs(node, 0, Type::Boolean());
 568       CheckUpperIs(node, Type::Number());
 569       break;
 570     case IrOpcode::kNumberEqual:
 571     case IrOpcode::kNumberLessThan:
 572     case IrOpcode::kNumberLessThanOrEqual:
 573       // (Number, Number) -> Boolean
 574       CheckValueInputIs(node, 0, Type::Number());
 575       CheckValueInputIs(node, 1, Type::Number());
 576       CheckUpperIs(node, Type::Boolean());
 577       break;
 578     case IrOpcode::kNumberAdd:
 579     case IrOpcode::kNumberSubtract:
 580     case IrOpcode::kNumberMultiply:
 581     case IrOpcode::kNumberDivide:
 582     case IrOpcode::kNumberModulus:
 583       // (Number, Number) -> Number
 584       CheckValueInputIs(node, 0, Type::Number());
 585       CheckValueInputIs(node, 1, Type::Number());
 586       // TODO(rossberg): activate once we retype after opcode changes.
 587       // CheckUpperIs(node, Type::Number());
 588       break;
 589     case IrOpcode::kNumberToInt32:
 590       // Number -> Signed32
 591       CheckValueInputIs(node, 0, Type::Number());
 592       CheckUpperIs(node, Type::Signed32());
 593       break;
 594     case IrOpcode::kNumberToUint32:
 595       // Number -> Unsigned32
 596       CheckValueInputIs(node, 0, Type::Number());
 597       CheckUpperIs(node, Type::Unsigned32());
 598       break;
 599     case IrOpcode::kPlainPrimitiveToNumber:
 600       // PlainPrimitive -> Number
 601       CheckValueInputIs(node, 0, Type::PlainPrimitive());
 602       CheckUpperIs(node, Type::Number());
 603       break;
 604     case IrOpcode::kStringEqual:
 605     case IrOpcode::kStringLessThan:
 606     case IrOpcode::kStringLessThanOrEqual:
 607       // (String, String) -> Boolean
 608       CheckValueInputIs(node, 0, Type::String());
 609       CheckValueInputIs(node, 1, Type::String());
 610       CheckUpperIs(node, Type::Boolean());
 611       break;
 612     case IrOpcode::kStringAdd:
 613       // (String, String) -> String
 614       CheckValueInputIs(node, 0, Type::String());
 615       CheckValueInputIs(node, 1, Type::String());
 616       CheckUpperIs(node, Type::String());
 617       break;
 618     case IrOpcode::kReferenceEqual: {
 619       // (Unique, Any) -> Boolean  and
 620       // (Any, Unique) -> Boolean
 621       CheckUpperIs(node, Type::Boolean());
 622       break;
 623     }
 624     case IrOpcode::kObjectIsSmi:
 625       CheckValueInputIs(node, 0, Type::Any());
 626       CheckUpperIs(node, Type::Boolean());
 627       break;
 628     case IrOpcode::kObjectIsNonNegativeSmi:
 629       CheckValueInputIs(node, 0, Type::Any());
 630       CheckUpperIs(node, Type::Boolean());
 631       break;
 632
 633     case IrOpcode::kChangeTaggedToInt32: {
 634       // Signed32 /\ Tagged -> Signed32 /\ UntaggedInt32
 635       // TODO(neis): Activate once ChangeRepresentation works in typer.
 636       // Type* from = Type::Intersect(Type::Signed32(), Type::Tagged());
 637       // Type* to = Type::Intersect(Type::Signed32(), Type::UntaggedInt32());
 638       // CheckValueInputIs(node, 0, from));
 639       // CheckUpperIs(node, to));
 640       break;
 641     }
 642     case IrOpcode::kChangeTaggedToUint32: {
 643       // Unsigned32 /\ Tagged -> Unsigned32 /\ UntaggedInt32
 644       // TODO(neis): Activate once ChangeRepresentation works in typer.
 645       // Type* from = Type::Intersect(Type::Unsigned32(), Type::Tagged());
 646       // Type* to =Type::Intersect(Type::Unsigned32(), Type::UntaggedInt32());
 647       // CheckValueInputIs(node, 0, from));
 648       // CheckUpperIs(node, to));
 649       break;
 650     }
 651     case IrOpcode::kChangeTaggedToFloat64: {
 652       // Number /\ Tagged -> Number /\ UntaggedFloat64
 653       // TODO(neis): Activate once ChangeRepresentation works in typer.
 654       // Type* from = Type::Intersect(Type::Number(), Type::Tagged());
 655       // Type* to = Type::Intersect(Type::Number(), Type::UntaggedFloat64());
 656       // CheckValueInputIs(node, 0, from));
 657       // CheckUpperIs(node, to));
 658       break;
 659     }
 660     case IrOpcode::kChangeInt32ToTagged: {
 661       // Signed32 /\ UntaggedInt32 -> Signed32 /\ Tagged
 662       // TODO(neis): Activate once ChangeRepresentation works in typer.
 663       // Type* from =Type::Intersect(Type::Signed32(), Type::UntaggedInt32());
 664       // Type* to = Type::Intersect(Type::Signed32(), Type::Tagged());
 665       // CheckValueInputIs(node, 0, from));
 666       // CheckUpperIs(node, to));
 667       break;
 668     }
 669     case IrOpcode::kChangeUint32ToTagged: {
 670       // Unsigned32 /\ UntaggedInt32 -> Unsigned32 /\ Tagged
 671       // TODO(neis): Activate once ChangeRepresentation works in typer.
 672       // Type* from=Type::Intersect(Type::Unsigned32(),Type::UntaggedInt32());
 673       // Type* to = Type::Intersect(Type::Unsigned32(), Type::Tagged());
 674       // CheckValueInputIs(node, 0, from));
 675       // CheckUpperIs(node, to));
 676       break;
 677     }
 678     case IrOpcode::kChangeFloat64ToTagged: {
 679       // Number /\ UntaggedFloat64 -> Number /\ Tagged
 680       // TODO(neis): Activate once ChangeRepresentation works in typer.
 681       // Type* from =Type::Intersect(Type::Number(), Type::UntaggedFloat64());
 682       // Type* to = Type::Intersect(Type::Number(), Type::Tagged());
 683       // CheckValueInputIs(node, 0, from));
 684       // CheckUpperIs(node, to));
 685       break;
 686     }
 687     case IrOpcode::kChangeBoolToBit: {
 688       // Boolean /\ TaggedPtr -> Boolean /\ UntaggedInt1
 689       // TODO(neis): Activate once ChangeRepresentation works in typer.
 690       // Type* from = Type::Intersect(Type::Boolean(), Type::TaggedPtr());
 691       // Type* to = Type::Intersect(Type::Boolean(), Type::UntaggedInt1());
 692       // CheckValueInputIs(node, 0, from));
 693       // CheckUpperIs(node, to));
 694       break;
 695     }
 696     case IrOpcode::kChangeBitToBool: {
 697       // Boolean /\ UntaggedInt1 -> Boolean /\ TaggedPtr
 698       // TODO(neis): Activate once ChangeRepresentation works in typer.
 699       // Type* from = Type::Intersect(Type::Boolean(), Type::UntaggedInt1());
 700       // Type* to = Type::Intersect(Type::Boolean(), Type::TaggedPtr());
 701       // CheckValueInputIs(node, 0, from));
 702       // CheckUpperIs(node, to));
 703       break;
 704     }
 705
 706     case IrOpcode::kLoadField:
 707       // Object -> fieldtype
 708       // TODO(rossberg): activate once machine ops are typed.
 709       // CheckValueInputIs(node, 0, Type::Object());
 710       // CheckUpperIs(node, Field(node).type));
 711       break;
 712     case IrOpcode::kLoadBuffer:
 713       break;
 714     case IrOpcode::kLoadElement:
 715       // Object -> elementtype
 716       // TODO(rossberg): activate once machine ops are typed.
 717       // CheckValueInputIs(node, 0, Type::Object());
 718       // CheckUpperIs(node, Element(node).type));
 719       break;
 720     case IrOpcode::kStoreField:
 721       // (Object, fieldtype) -> _|_
 722       // TODO(rossberg): activate once machine ops are typed.
 723       // CheckValueInputIs(node, 0, Type::Object());
 724       // CheckValueInputIs(node, 1, Field(node).type));
 725       CheckNotTyped(node);
 726       break;
 727     case IrOpcode::kStoreBuffer:
 728       break;
 729     case IrOpcode::kStoreElement:
 730       // (Object, elementtype) -> _|_
 731       // TODO(rossberg): activate once machine ops are typed.
 732       // CheckValueInputIs(node, 0, Type::Object());
 733       // CheckValueInputIs(node, 1, Element(node).type));
 734       CheckNotTyped(node);
 735       break;
 736
 737     // Machine operators
 738     // -----------------------
 739     case IrOpcode::kLoad:
 740     case IrOpcode::kStore:
 741     case IrOpcode::kWord32And:
 742     case IrOpcode::kWord32Or:
 743     case IrOpcode::kWord32Xor:
 744     case IrOpcode::kWord32Shl:
 745     case IrOpcode::kWord32Shr:
 746     case IrOpcode::kWord32Sar:
 747     case IrOpcode::kWord32Ror:
 748     case IrOpcode::kWord32Equal:
 749     case IrOpcode::kWord32Clz:
 750     case IrOpcode::kWord64And:
 751     case IrOpcode::kWord64Or:
 752     case IrOpcode::kWord64Xor:
 753     case IrOpcode::kWord64Shl:
 754     case IrOpcode::kWord64Shr:
 755     case IrOpcode::kWord64Sar:
 756     case IrOpcode::kWord64Ror:
 757     case IrOpcode::kWord64Equal:
 758     case IrOpcode::kInt32Add:
 759     case IrOpcode::kInt32AddWithOverflow:
 760     case IrOpcode::kInt32Sub:
 761     case IrOpcode::kInt32SubWithOverflow:
 762     case IrOpcode::kInt32Mul:
 763     case IrOpcode::kInt32MulHigh:
 764     case IrOpcode::kInt32Div:
 765     case IrOpcode::kInt32Mod:
 766     case IrOpcode::kInt32LessThan:
 767     case IrOpcode::kInt32LessThanOrEqual:
 768     case IrOpcode::kUint32Div:
 769     case IrOpcode::kUint32Mod:
 770     case IrOpcode::kUint32MulHigh:
 771     case IrOpcode::kUint32LessThan:
 772     case IrOpcode::kUint32LessThanOrEqual:
 773     case IrOpcode::kInt64Add:
 774     case IrOpcode::kInt64Sub:
 775     case IrOpcode::kInt64Mul:
 776     case IrOpcode::kInt64Div:
 777     case IrOpcode::kInt64Mod:
 778     case IrOpcode::kInt64LessThan:
 779     case IrOpcode::kInt64LessThanOrEqual:
 780     case IrOpcode::kUint64Div:
 781     case IrOpcode::kUint64Mod:
 782     case IrOpcode::kUint64LessThan:
 783     case IrOpcode::kFloat64Add:
 784     case IrOpcode::kFloat64Sub:
 785     case IrOpcode::kFloat64Mul:
 786     case IrOpcode::kFloat64Div:
 787     case IrOpcode::kFloat64Mod:
 788     case IrOpcode::kFloat64Max:
 789     case IrOpcode::kFloat64Min:
 790     case IrOpcode::kFloat64Sqrt:
 791     case IrOpcode::kFloat64RoundDown:
 792     case IrOpcode::kFloat64RoundTruncate:
 793     case IrOpcode::kFloat64RoundTiesAway:
 794     case IrOpcode::kFloat64Equal:
 795     case IrOpcode::kFloat64LessThan:
 796     case IrOpcode::kFloat64LessThanOrEqual:
 797     case IrOpcode::kTruncateInt64ToInt32:
 798     case IrOpcode::kTruncateFloat64ToFloat32:
 799     case IrOpcode::kTruncateFloat64ToInt32:
 800     case IrOpcode::kChangeInt32ToInt64:
 801     case IrOpcode::kChangeUint32ToUint64:
 802     case IrOpcode::kChangeInt32ToFloat64:
 803     case IrOpcode::kChangeUint32ToFloat64:
 804     case IrOpcode::kChangeFloat32ToFloat64:
 805     case IrOpcode::kChangeFloat64ToInt32:
 806     case IrOpcode::kChangeFloat64ToUint32:
 807     case IrOpcode::kFloat64ExtractLowWord32:
 808     case IrOpcode::kFloat64ExtractHighWord32:
 809     case IrOpcode::kFloat64InsertLowWord32:
 810     case IrOpcode::kFloat64InsertHighWord32:
 811     case IrOpcode::kLoadStackPointer:
 812     case IrOpcode::kCheckedLoad:
 813     case IrOpcode::kCheckedStore:
 814       // TODO(rossberg): Check.
 815       break;
 816   }
 817 }  // NOLINT(readability/fn_size)
 818
 819
 820 void Verifier::Run(Graph* graph, Typing typing) {
 821   CHECK_NOT_NULL(graph->start());
 822   CHECK_NOT_NULL(graph->end());
 823   Zone zone;
 824   Visitor visitor(&zone, typing);
 825   AllNodes all(&zone, graph);
 826   for (Node* node : all.live) visitor.Check(node);
 827
 828   // Check the uniqueness of projections.
 829   for (Node* proj : all.live) {
 830     if (proj->opcode() != IrOpcode::kProjection) continue;
 831     Node* node = proj->InputAt(0);
 832     for (Node* other : node->uses()) {
 833       if (all.IsLive(other) && other != proj &&
 834           other->opcode() == IrOpcode::kProjection &&
 835           ProjectionIndexOf(other->op()) == ProjectionIndexOf(proj->op())) {
 836         V8_Fatal(__FILE__, __LINE__,
 837                  "Node #%d:%s has duplicate projections #%d and #%d",
 838                  node->id(), node->op()->mnemonic(), proj->id(), other->id());
 839       }
 840     }
 841   }
 842 }
 843
 844
 845 // -----------------------------------------------------------------------------
 846
 847 static bool HasDominatingDef(Schedule* schedule, Node* node,
 848                              BasicBlock* container, BasicBlock* use_block,
 849                              int use_pos) {
 850   BasicBlock* block = use_block;
 851   while (true) {
 852     while (use_pos >= 0) {
 853       if (block->NodeAt(use_pos) == node) return true;
 854       use_pos--;
 855     }
 856     block = block->dominator();
 857     if (block == NULL) break;
 858     use_pos = static_cast<int>(block->NodeCount()) - 1;
 859     if (node == block->control_input()) return true;
 860   }
 861   return false;
 862 }
 863
 864
 865 static bool Dominates(Schedule* schedule, Node* dominator, Node* dominatee) {
 866   BasicBlock* dom = schedule->block(dominator);
 867   BasicBlock* sub = schedule->block(dominatee);
 868   while (sub != NULL) {
 869     if (sub == dom) {
 870       return true;
 871     }
 872     sub = sub->dominator();
 873   }
 874   return false;
 875 }
 876
 877
 878 static void CheckInputsDominate(Schedule* schedule, BasicBlock* block,
 879                                 Node* node, int use_pos) {
 880   for (int j = node->op()->ValueInputCount() - 1; j >= 0; j--) {
 881     BasicBlock* use_block = block;
 882     if (node->opcode() == IrOpcode::kPhi) {
 883       use_block = use_block->PredecessorAt(j);
 884       use_pos = static_cast<int>(use_block->NodeCount()) - 1;
 885     }
 886     Node* input = node->InputAt(j);
 887     if (!HasDominatingDef(schedule, node->InputAt(j), block, use_block,
 888                           use_pos)) {
 889       V8_Fatal(__FILE__, __LINE__,
 890                "Node #%d:%s in B%d is not dominated by input@%d #%d:%s",
 891                node->id(), node->op()->mnemonic(), block->rpo_number(), j,
 892                input->id(), input->op()->mnemonic());
 893     }
 894   }
 895   // Ensure that nodes are dominated by their control inputs;
 896   // kEnd is an exception, as unreachable blocks resulting from kMerge
 897   // are not in the RPO.
 898   if (node->op()->ControlInputCount() == 1 &&
 899       node->opcode() != IrOpcode::kEnd) {
 900     Node* ctl = NodeProperties::GetControlInput(node);
 901     if (!Dominates(schedule, ctl, node)) {
 902       V8_Fatal(__FILE__, __LINE__,
 903                "Node #%d:%s in B%d is not dominated by control input #%d:%s",
 904                node->id(), node->op()->mnemonic(), block->rpo_number(),
 905                ctl->id(), ctl->op()->mnemonic());
 906     }
 907   }
 908 }
 909
 910
 911 void ScheduleVerifier::Run(Schedule* schedule) {
 912   const size_t count = schedule->BasicBlockCount();
 913   Zone tmp_zone;
 914   Zone* zone = &tmp_zone;
 915   BasicBlock* start = schedule->start();
 916   BasicBlockVector* rpo_order = schedule->rpo_order();
 917
 918   // Verify the RPO order contains only blocks from this schedule.
 919   CHECK_GE(count, rpo_order->size());
 920   for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
 921        ++b) {
 922     CHECK_EQ((*b), schedule->GetBlockById((*b)->id()));
 923     // All predecessors and successors should be in rpo and in this schedule.
 924     for (BasicBlock const* predecessor : (*b)->predecessors()) {
 925       CHECK_GE(predecessor->rpo_number(), 0);
 926       CHECK_EQ(predecessor, schedule->GetBlockById(predecessor->id()));
 927     }
 928     for (BasicBlock const* successor : (*b)->successors()) {
 929       CHECK_GE(successor->rpo_number(), 0);
 930       CHECK_EQ(successor, schedule->GetBlockById(successor->id()));
 931     }
 932   }
 933
 934   // Verify RPO numbers of blocks.
 935   CHECK_EQ(start, rpo_order->at(0));  // Start should be first.
 936   for (size_t b = 0; b < rpo_order->size(); b++) {
 937     BasicBlock* block = rpo_order->at(b);
 938     CHECK_EQ(static_cast<int>(b), block->rpo_number());
 939     BasicBlock* dom = block->dominator();
 940     if (b == 0) {
 941       // All blocks except start should have a dominator.
 942       CHECK_NULL(dom);
 943     } else {
 944       // Check that the immediate dominator appears somewhere before the block.
 945       CHECK_NOT_NULL(dom);
 946       CHECK_LT(dom->rpo_number(), block->rpo_number());
 947     }
 948   }
 949
 950   // Verify that all blocks reachable from start are in the RPO.
 951   BoolVector marked(static_cast<int>(count), false, zone);
 952   {
 953     ZoneQueue<BasicBlock*> queue(zone);
 954     queue.push(start);
 955     marked[start->id().ToSize()] = true;
 956     while (!queue.empty()) {
 957       BasicBlock* block = queue.front();
 958       queue.pop();
 959       for (size_t s = 0; s < block->SuccessorCount(); s++) {
 960         BasicBlock* succ = block->SuccessorAt(s);
 961         if (!marked[succ->id().ToSize()]) {
 962           marked[succ->id().ToSize()] = true;
 963           queue.push(succ);
 964         }
 965       }
 966     }
 967   }
 968   // Verify marked blocks are in the RPO.
 969   for (size_t i = 0; i < count; i++) {
 970     BasicBlock* block = schedule->GetBlockById(BasicBlock::Id::FromSize(i));
 971     if (marked[i]) {
 972       CHECK_GE(block->rpo_number(), 0);
 973       CHECK_EQ(block, rpo_order->at(block->rpo_number()));
 974     }
 975   }
 976   // Verify RPO blocks are marked.
 977   for (size_t b = 0; b < rpo_order->size(); b++) {
 978     CHECK(marked[rpo_order->at(b)->id().ToSize()]);
 979   }
 980
 981   {
 982     // Verify the dominance relation.
 983     ZoneVector<BitVector*> dominators(zone);
 984     dominators.resize(count, NULL);
 985
 986     // Compute a set of all the nodes that dominate a given node by using
 987     // a forward fixpoint. O(n^2).
 988     ZoneQueue<BasicBlock*> queue(zone);
 989     queue.push(start);
 990     dominators[start->id().ToSize()] =
 991         new (zone) BitVector(static_cast<int>(count), zone);
 992     while (!queue.empty()) {
 993       BasicBlock* block = queue.front();
 994       queue.pop();
 995       BitVector* block_doms = dominators[block->id().ToSize()];
 996       BasicBlock* idom = block->dominator();
 997       if (idom != NULL && !block_doms->Contains(idom->id().ToInt())) {
 998         V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d",
 999                  block->rpo_number(), idom->rpo_number());
1000       }
1001       for (size_t s = 0; s < block->SuccessorCount(); s++) {
1002         BasicBlock* succ = block->SuccessorAt(s);
1003         BitVector* succ_doms = dominators[succ->id().ToSize()];
1004
1005         if (succ_doms == NULL) {
1006           // First time visiting the node. S.doms = B U B.doms
1007           succ_doms = new (zone) BitVector(static_cast<int>(count), zone);
1008           succ_doms->CopyFrom(*block_doms);
1009           succ_doms->Add(block->id().ToInt());
1010           dominators[succ->id().ToSize()] = succ_doms;
1011           queue.push(succ);
1012         } else {
1013           // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms)
1014           bool had = succ_doms->Contains(block->id().ToInt());
1015           if (had) succ_doms->Remove(block->id().ToInt());
1016           if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ);
1017           if (had) succ_doms->Add(block->id().ToInt());
1018         }
1019       }
1020     }
1021
1022     // Verify the immediateness of dominators.
1023     for (BasicBlockVector::iterator b = rpo_order->begin();
1024          b != rpo_order->end(); ++b) {
1025       BasicBlock* block = *b;
1026       BasicBlock* idom = block->dominator();
1027       if (idom == NULL) continue;
1028       BitVector* block_doms = dominators[block->id().ToSize()];
1029
1030       for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) {
1031         BasicBlock* dom =
1032             schedule->GetBlockById(BasicBlock::Id::FromInt(it.Current()));
1033         if (dom != idom &&
1034             !dominators[idom->id().ToSize()]->Contains(dom->id().ToInt())) {
1035           V8_Fatal(__FILE__, __LINE__,
1036                    "Block B%d is not immediately dominated by B%d",
1037                    block->rpo_number(), idom->rpo_number());
1038         }
1039       }
1040     }
1041   }
1042
1043   // Verify phis are placed in the block of their control input.
1044   for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
1045        ++b) {
1046     for (BasicBlock::const_iterator i = (*b)->begin(); i != (*b)->end(); ++i) {
1047       Node* phi = *i;
1048       if (phi->opcode() != IrOpcode::kPhi) continue;
1049       // TODO(titzer): Nasty special case. Phis from RawMachineAssembler
1050       // schedules don't have control inputs.
1051       if (phi->InputCount() > phi->op()->ValueInputCount()) {
1052         Node* control = NodeProperties::GetControlInput(phi);
1053         CHECK(control->opcode() == IrOpcode::kMerge ||
1054               control->opcode() == IrOpcode::kLoop);
1055         CHECK_EQ((*b), schedule->block(control));
1056       }
1057     }
1058   }
1059
1060   // Verify that all uses are dominated by their definitions.
1061   for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
1062        ++b) {
1063     BasicBlock* block = *b;
1064
1065     // Check inputs to control for this block.
1066     Node* control = block->control_input();
1067     if (control != NULL) {
1068       CHECK_EQ(block, schedule->block(control));
1069       CheckInputsDominate(schedule, block, control,
1070                           static_cast<int>(block->NodeCount()) - 1);
1071     }
1072     // Check inputs for all nodes in the block.
1073     for (size_t i = 0; i < block->NodeCount(); i++) {
1074       Node* node = block->NodeAt(i);
1075       CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1);
1076     }
1077   }
1078 }
1079 }
1080 }
1081 }  // namespace v8::internal::compiler