Home | History | Annotate | Download | only in compiler
      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   const Node::Uses 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   const Node::Inputs 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, CheckInputs check_inputs)
     46       : zone(z), typing(typed), check_inputs(check_inputs) {}
     47 
     48   void Check(Node* node);
     49 
     50   Zone* zone;
     51   Typing typing;
     52   CheckInputs check_inputs;
     53 
     54  private:
     55   void CheckNotTyped(Node* node) {
     56     if (NodeProperties::IsTyped(node)) {
     57       std::ostringstream str;
     58       str << "TypeError: node #" << node->id() << ":" << *node->op()
     59           << " should never have a type";
     60       FATAL(str.str().c_str());
     61     }
     62   }
     63   void CheckUpperIs(Node* node, Type* type) {
     64     if (typing == TYPED && !NodeProperties::GetType(node)->Is(type)) {
     65       std::ostringstream str;
     66       str << "TypeError: node #" << node->id() << ":" << *node->op()
     67           << " type ";
     68       NodeProperties::GetType(node)->PrintTo(str);
     69       str << " is not ";
     70       type->PrintTo(str);
     71       FATAL(str.str().c_str());
     72     }
     73   }
     74   void CheckUpperMaybe(Node* node, Type* type) {
     75     if (typing == TYPED && !NodeProperties::GetType(node)->Maybe(type)) {
     76       std::ostringstream str;
     77       str << "TypeError: node #" << node->id() << ":" << *node->op()
     78           << " type ";
     79       NodeProperties::GetType(node)->PrintTo(str);
     80       str << " must intersect ";
     81       type->PrintTo(str);
     82       FATAL(str.str().c_str());
     83     }
     84   }
     85   void CheckValueInputIs(Node* node, int i, Type* type) {
     86     Node* input = NodeProperties::GetValueInput(node, i);
     87     if (typing == TYPED && !NodeProperties::GetType(input)->Is(type)) {
     88       std::ostringstream str;
     89       str << "TypeError: node #" << node->id() << ":" << *node->op()
     90           << "(input @" << i << " = " << input->opcode() << ":"
     91           << input->op()->mnemonic() << ") type ";
     92       NodeProperties::GetType(input)->PrintTo(str);
     93       str << " is not ";
     94       type->PrintTo(str);
     95       FATAL(str.str().c_str());
     96     }
     97   }
     98   void CheckOutput(Node* node, Node* use, int count, const char* kind) {
     99     if (count <= 0) {
    100       std::ostringstream str;
    101       str << "GraphError: node #" << node->id() << ":" << *node->op()
    102           << " does not produce " << kind << " output used by node #"
    103           << use->id() << ":" << *use->op();
    104       FATAL(str.str().c_str());
    105     }
    106   }
    107 };
    108 
    109 
    110 void Verifier::Visitor::Check(Node* node) {
    111   int value_count = node->op()->ValueInputCount();
    112   int context_count = OperatorProperties::GetContextInputCount(node->op());
    113   int frame_state_count =
    114       OperatorProperties::GetFrameStateInputCount(node->op());
    115   int effect_count = node->op()->EffectInputCount();
    116   int control_count = node->op()->ControlInputCount();
    117 
    118   // Verify number of inputs matches up.
    119   int input_count = value_count + context_count + frame_state_count;
    120   if (check_inputs == kAll) {
    121     input_count += effect_count + control_count;
    122   }
    123   CHECK_EQ(input_count, node->InputCount());
    124 
    125   // Verify that frame state has been inserted for the nodes that need it.
    126   for (int i = 0; i < frame_state_count; i++) {
    127     Node* frame_state = NodeProperties::GetFrameStateInput(node, i);
    128     CHECK(frame_state->opcode() == IrOpcode::kFrameState ||
    129           // kFrameState uses Start as a sentinel.
    130           (node->opcode() == IrOpcode::kFrameState &&
    131            frame_state->opcode() == IrOpcode::kStart));
    132     CHECK(IsDefUseChainLinkPresent(frame_state, node));
    133     CHECK(IsUseDefChainLinkPresent(frame_state, node));
    134   }
    135 
    136   // Verify all value inputs actually produce a value.
    137   for (int i = 0; i < value_count; ++i) {
    138     Node* value = NodeProperties::GetValueInput(node, i);
    139     CheckOutput(value, node, value->op()->ValueOutputCount(), "value");
    140     CHECK(IsDefUseChainLinkPresent(value, node));
    141     CHECK(IsUseDefChainLinkPresent(value, node));
    142     // Verify that only parameters and projections can have input nodes with
    143     // multiple outputs.
    144     CHECK(node->opcode() == IrOpcode::kParameter ||
    145           node->opcode() == IrOpcode::kProjection ||
    146           value->op()->ValueOutputCount() <= 1);
    147   }
    148 
    149   // Verify all context inputs are value nodes.
    150   for (int i = 0; i < context_count; ++i) {
    151     Node* context = NodeProperties::GetContextInput(node);
    152     CheckOutput(context, node, context->op()->ValueOutputCount(), "context");
    153     CHECK(IsDefUseChainLinkPresent(context, node));
    154     CHECK(IsUseDefChainLinkPresent(context, node));
    155   }
    156 
    157   if (check_inputs == kAll) {
    158     // Verify all effect inputs actually have an effect.
    159     for (int i = 0; i < effect_count; ++i) {
    160       Node* effect = NodeProperties::GetEffectInput(node);
    161       CheckOutput(effect, node, effect->op()->EffectOutputCount(), "effect");
    162       CHECK(IsDefUseChainLinkPresent(effect, node));
    163       CHECK(IsUseDefChainLinkPresent(effect, node));
    164     }
    165 
    166     // Verify all control inputs are control nodes.
    167     for (int i = 0; i < control_count; ++i) {
    168       Node* control = NodeProperties::GetControlInput(node, i);
    169       CheckOutput(control, node, control->op()->ControlOutputCount(),
    170                   "control");
    171       CHECK(IsDefUseChainLinkPresent(control, node));
    172       CHECK(IsUseDefChainLinkPresent(control, node));
    173     }
    174   }
    175 
    176   switch (node->opcode()) {
    177     case IrOpcode::kStart:
    178       // Start has no inputs.
    179       CHECK_EQ(0, input_count);
    180       // Type is a tuple.
    181       // TODO(rossberg): Multiple outputs are currently typed as Internal.
    182       CheckUpperIs(node, Type::Internal());
    183       break;
    184     case IrOpcode::kEnd:
    185       // End has no outputs.
    186       CHECK(node->op()->ValueOutputCount() == 0);
    187       CHECK(node->op()->EffectOutputCount() == 0);
    188       CHECK(node->op()->ControlOutputCount() == 0);
    189       // Type is empty.
    190       CheckNotTyped(node);
    191       break;
    192     case IrOpcode::kDead:
    193       // Dead is never connected to the graph.
    194       UNREACHABLE();
    195       break;
    196     case IrOpcode::kBranch: {
    197       // Branch uses are IfTrue and IfFalse.
    198       int count_true = 0, count_false = 0;
    199       for (const Node* use : node->uses()) {
    200         CHECK(use->opcode() == IrOpcode::kIfTrue ||
    201               use->opcode() == IrOpcode::kIfFalse);
    202         if (use->opcode() == IrOpcode::kIfTrue) ++count_true;
    203         if (use->opcode() == IrOpcode::kIfFalse) ++count_false;
    204       }
    205       CHECK_EQ(1, count_true);
    206       CHECK_EQ(1, count_false);
    207       // Type is empty.
    208       CheckNotTyped(node);
    209       break;
    210     }
    211     case IrOpcode::kIfTrue:
    212     case IrOpcode::kIfFalse:
    213       CHECK_EQ(IrOpcode::kBranch,
    214                NodeProperties::GetControlInput(node, 0)->opcode());
    215       // Type is empty.
    216       CheckNotTyped(node);
    217       break;
    218     case IrOpcode::kIfSuccess: {
    219       // IfSuccess and IfException continuation only on throwing nodes.
    220       Node* input = NodeProperties::GetControlInput(node, 0);
    221       CHECK(!input->op()->HasProperty(Operator::kNoThrow));
    222       // Type is empty.
    223       CheckNotTyped(node);
    224       break;
    225     }
    226     case IrOpcode::kIfException: {
    227       // IfSuccess and IfException continuation only on throwing nodes.
    228       Node* input = NodeProperties::GetControlInput(node, 0);
    229       CHECK(!input->op()->HasProperty(Operator::kNoThrow));
    230       // Type can be anything.
    231       CheckUpperIs(node, Type::Any());
    232       break;
    233     }
    234     case IrOpcode::kSwitch: {
    235       // Switch uses are Case and Default.
    236       int count_case = 0, count_default = 0;
    237       for (const Node* use : node->uses()) {
    238         switch (use->opcode()) {
    239           case IrOpcode::kIfValue: {
    240             for (const Node* user : node->uses()) {
    241               if (user != use && user->opcode() == IrOpcode::kIfValue) {
    242                 CHECK_NE(OpParameter<int32_t>(use->op()),
    243                          OpParameter<int32_t>(user->op()));
    244               }
    245             }
    246             ++count_case;
    247             break;
    248           }
    249           case IrOpcode::kIfDefault: {
    250             ++count_default;
    251             break;
    252           }
    253           default: {
    254             V8_Fatal(__FILE__, __LINE__, "Switch #%d illegally used by #%d:%s",
    255                      node->id(), use->id(), use->op()->mnemonic());
    256             break;
    257           }
    258         }
    259       }
    260       CHECK_EQ(1, count_default);
    261       CHECK_EQ(node->op()->ControlOutputCount(), count_case + count_default);
    262       // Type is empty.
    263       CheckNotTyped(node);
    264       break;
    265     }
    266     case IrOpcode::kIfValue:
    267     case IrOpcode::kIfDefault:
    268       CHECK_EQ(IrOpcode::kSwitch,
    269                NodeProperties::GetControlInput(node)->opcode());
    270       // Type is empty.
    271       CheckNotTyped(node);
    272       break;
    273     case IrOpcode::kLoop:
    274     case IrOpcode::kMerge:
    275       CHECK_EQ(control_count, input_count);
    276       // Type is empty.
    277       CheckNotTyped(node);
    278       break;
    279     case IrOpcode::kDeoptimizeIf:
    280     case IrOpcode::kDeoptimizeUnless:
    281       // Type is empty.
    282       CheckNotTyped(node);
    283       break;
    284     case IrOpcode::kDeoptimize:
    285     case IrOpcode::kReturn:
    286     case IrOpcode::kThrow:
    287       // Deoptimize, Return and Throw uses are End.
    288       for (const Node* use : node->uses()) {
    289         CHECK_EQ(IrOpcode::kEnd, use->opcode());
    290       }
    291       // Type is empty.
    292       CheckNotTyped(node);
    293       break;
    294     case IrOpcode::kTerminate:
    295       // Terminates take one loop and effect.
    296       CHECK_EQ(1, control_count);
    297       CHECK_EQ(1, effect_count);
    298       CHECK_EQ(2, input_count);
    299       CHECK_EQ(IrOpcode::kLoop,
    300                NodeProperties::GetControlInput(node)->opcode());
    301       // Terminate uses are End.
    302       for (const Node* use : node->uses()) {
    303         CHECK_EQ(IrOpcode::kEnd, use->opcode());
    304       }
    305       // Type is empty.
    306       CheckNotTyped(node);
    307       break;
    308     case IrOpcode::kOsrNormalEntry:
    309     case IrOpcode::kOsrLoopEntry:
    310       // Osr entries take one control and effect.
    311       CHECK_EQ(1, control_count);
    312       CHECK_EQ(1, effect_count);
    313       CHECK_EQ(2, input_count);
    314       // Type is empty.
    315       CheckNotTyped(node);
    316       break;
    317 
    318     // Common operators
    319     // ----------------
    320     case IrOpcode::kParameter: {
    321       // Parameters have the start node as inputs.
    322       CHECK_EQ(1, input_count);
    323       // Parameter has an input that produces enough values.
    324       int const index = ParameterIndexOf(node->op());
    325       Node* const start = NodeProperties::GetValueInput(node, 0);
    326       CHECK_EQ(IrOpcode::kStart, start->opcode());
    327       // Currently, parameter indices start at -1 instead of 0.
    328       CHECK_LE(-1, index);
    329       CHECK_LT(index + 1, start->op()->ValueOutputCount());
    330       // Type can be anything.
    331       CheckUpperIs(node, Type::Any());
    332       break;
    333     }
    334     case IrOpcode::kInt32Constant:  // TODO(rossberg): rename Word32Constant?
    335       // Constants have no inputs.
    336       CHECK_EQ(0, input_count);
    337       // Type is a 32 bit integer, signed or unsigned.
    338       CheckUpperIs(node, Type::Integral32());
    339       break;
    340     case IrOpcode::kInt64Constant:
    341       // Constants have no inputs.
    342       CHECK_EQ(0, input_count);
    343       // Type is internal.
    344       // TODO(rossberg): Introduce proper Int64 type.
    345       CheckUpperIs(node, Type::Internal());
    346       break;
    347     case IrOpcode::kFloat32Constant:
    348     case IrOpcode::kFloat64Constant:
    349     case IrOpcode::kNumberConstant:
    350       // Constants have no inputs.
    351       CHECK_EQ(0, input_count);
    352       // Type is a number.
    353       CheckUpperIs(node, Type::Number());
    354       break;
    355     case IrOpcode::kRelocatableInt32Constant:
    356     case IrOpcode::kRelocatableInt64Constant:
    357       CHECK_EQ(0, input_count);
    358       break;
    359     case IrOpcode::kHeapConstant:
    360       // Constants have no inputs.
    361       CHECK_EQ(0, input_count);
    362       // Type can be anything represented as a heap pointer.
    363       CheckUpperIs(node, Type::TaggedPointer());
    364       break;
    365     case IrOpcode::kExternalConstant:
    366       // Constants have no inputs.
    367       CHECK_EQ(0, input_count);
    368       // Type is considered internal.
    369       CheckUpperIs(node, Type::Internal());
    370       break;
    371     case IrOpcode::kOsrValue:
    372       // OSR values have a value and a control input.
    373       CHECK_EQ(1, control_count);
    374       CHECK_EQ(1, input_count);
    375       // Type is merged from other values in the graph and could be any.
    376       CheckUpperIs(node, Type::Any());
    377       break;
    378     case IrOpcode::kProjection: {
    379       // Projection has an input that produces enough values.
    380       int index = static_cast<int>(ProjectionIndexOf(node->op()));
    381       Node* input = NodeProperties::GetValueInput(node, 0);
    382       CHECK_GT(input->op()->ValueOutputCount(), index);
    383       // Type can be anything.
    384       // TODO(rossberg): Introduce tuple types for this.
    385       // TODO(titzer): Convince rossberg not to.
    386       CheckUpperIs(node, Type::Any());
    387       break;
    388     }
    389     case IrOpcode::kSelect: {
    390       CHECK_EQ(0, effect_count);
    391       CHECK_EQ(0, control_count);
    392       CHECK_EQ(3, value_count);
    393       break;
    394     }
    395     case IrOpcode::kPhi: {
    396       // Phi input count matches parent control node.
    397       CHECK_EQ(0, effect_count);
    398       CHECK_EQ(1, control_count);
    399       Node* control = NodeProperties::GetControlInput(node, 0);
    400       CHECK_EQ(value_count, control->op()->ControlInputCount());
    401       CHECK_EQ(input_count, 1 + value_count);
    402       // Type must be subsumed by all input types.
    403       // TODO(rossberg): for now at least, narrowing does not really hold.
    404       /*
    405       for (int i = 0; i < value_count; ++i) {
    406         CHECK(type_of(ValueInput(node, i))->Is(type_of(node)));
    407       }
    408       */
    409       break;
    410     }
    411     case IrOpcode::kEffectPhi: {
    412       // EffectPhi input count matches parent control node.
    413       CHECK_EQ(0, value_count);
    414       CHECK_EQ(1, control_count);
    415       Node* control = NodeProperties::GetControlInput(node, 0);
    416       CHECK_EQ(effect_count, control->op()->ControlInputCount());
    417       CHECK_EQ(input_count, 1 + effect_count);
    418       break;
    419     }
    420     case IrOpcode::kTypeGuard:
    421       // TODO(bmeurer): what are the constraints on these?
    422       break;
    423     case IrOpcode::kCheckpoint:
    424       // Type is empty.
    425       CheckNotTyped(node);
    426       break;
    427     case IrOpcode::kBeginRegion:
    428       // TODO(rossberg): what are the constraints on these?
    429       break;
    430     case IrOpcode::kFinishRegion: {
    431       // TODO(rossberg): what are the constraints on these?
    432       // Type must be subsumed by input type.
    433       if (typing == TYPED) {
    434         Node* val = NodeProperties::GetValueInput(node, 0);
    435         CHECK(NodeProperties::GetType(val)->Is(NodeProperties::GetType(node)));
    436       }
    437       break;
    438     }
    439     case IrOpcode::kFrameState: {
    440       // TODO(jarin): what are the constraints on these?
    441       CHECK_EQ(5, value_count);
    442       CHECK_EQ(0, control_count);
    443       CHECK_EQ(0, effect_count);
    444       CHECK_EQ(6, input_count);
    445       for (int i = 0; i < 3; ++i) {
    446         CHECK(NodeProperties::GetValueInput(node, i)->opcode() ==
    447                   IrOpcode::kStateValues ||
    448               NodeProperties::GetValueInput(node, i)->opcode() ==
    449                   IrOpcode::kTypedStateValues);
    450       }
    451       break;
    452     }
    453     case IrOpcode::kStateValues:
    454     case IrOpcode::kObjectState:
    455     case IrOpcode::kTypedStateValues:
    456       // TODO(jarin): what are the constraints on these?
    457       break;
    458     case IrOpcode::kCall:
    459       // TODO(rossberg): what are the constraints on these?
    460       break;
    461     case IrOpcode::kTailCall:
    462       // TODO(bmeurer): what are the constraints on these?
    463       break;
    464 
    465     // JavaScript operators
    466     // --------------------
    467     case IrOpcode::kJSEqual:
    468     case IrOpcode::kJSNotEqual:
    469     case IrOpcode::kJSStrictEqual:
    470     case IrOpcode::kJSStrictNotEqual:
    471     case IrOpcode::kJSLessThan:
    472     case IrOpcode::kJSGreaterThan:
    473     case IrOpcode::kJSLessThanOrEqual:
    474     case IrOpcode::kJSGreaterThanOrEqual:
    475       // Type is Boolean.
    476       CheckUpperIs(node, Type::Boolean());
    477       break;
    478 
    479     case IrOpcode::kJSBitwiseOr:
    480     case IrOpcode::kJSBitwiseXor:
    481     case IrOpcode::kJSBitwiseAnd:
    482     case IrOpcode::kJSShiftLeft:
    483     case IrOpcode::kJSShiftRight:
    484     case IrOpcode::kJSShiftRightLogical:
    485       // Type is 32 bit integral.
    486       CheckUpperIs(node, Type::Integral32());
    487       break;
    488     case IrOpcode::kJSAdd:
    489       // Type is Number or String.
    490       CheckUpperIs(node, Type::NumberOrString());
    491       break;
    492     case IrOpcode::kJSSubtract:
    493     case IrOpcode::kJSMultiply:
    494     case IrOpcode::kJSDivide:
    495     case IrOpcode::kJSModulus:
    496       // Type is Number.
    497       CheckUpperIs(node, Type::Number());
    498       break;
    499 
    500     case IrOpcode::kJSToBoolean:
    501       // Type is Boolean.
    502       CheckUpperIs(node, Type::Boolean());
    503       break;
    504     case IrOpcode::kJSToInteger:
    505       // Type is OrderedNumber.
    506       CheckUpperIs(node, Type::OrderedNumber());
    507       break;
    508     case IrOpcode::kJSToLength:
    509       // Type is OrderedNumber.
    510       CheckUpperIs(node, Type::OrderedNumber());
    511       break;
    512     case IrOpcode::kJSToName:
    513       // Type is Name.
    514       CheckUpperIs(node, Type::Name());
    515       break;
    516     case IrOpcode::kJSToNumber:
    517       // Type is Number.
    518       CheckUpperIs(node, Type::Number());
    519       break;
    520     case IrOpcode::kJSToString:
    521       // Type is String.
    522       CheckUpperIs(node, Type::String());
    523       break;
    524     case IrOpcode::kJSToObject:
    525       // Type is Receiver.
    526       CheckUpperIs(node, Type::Receiver());
    527       break;
    528 
    529     case IrOpcode::kJSCreate:
    530       // Type is Object.
    531       CheckUpperIs(node, Type::Object());
    532       break;
    533     case IrOpcode::kJSCreateArguments:
    534       // Type is OtherObject.
    535       CheckUpperIs(node, Type::OtherObject());
    536       break;
    537     case IrOpcode::kJSCreateArray:
    538       // Type is OtherObject.
    539       CheckUpperIs(node, Type::OtherObject());
    540       break;
    541     case IrOpcode::kJSCreateClosure:
    542       // Type is Function.
    543       CheckUpperIs(node, Type::Function());
    544       break;
    545     case IrOpcode::kJSCreateIterResultObject:
    546       // Type is OtherObject.
    547       CheckUpperIs(node, Type::OtherObject());
    548       break;
    549     case IrOpcode::kJSCreateLiteralArray:
    550     case IrOpcode::kJSCreateLiteralObject:
    551     case IrOpcode::kJSCreateLiteralRegExp:
    552       // Type is OtherObject.
    553       CheckUpperIs(node, Type::OtherObject());
    554       break;
    555     case IrOpcode::kJSLoadProperty:
    556     case IrOpcode::kJSLoadNamed:
    557     case IrOpcode::kJSLoadGlobal:
    558       // Type can be anything.
    559       CheckUpperIs(node, Type::Any());
    560       break;
    561     case IrOpcode::kJSStoreProperty:
    562     case IrOpcode::kJSStoreNamed:
    563     case IrOpcode::kJSStoreGlobal:
    564       // Type is empty.
    565       CheckNotTyped(node);
    566       break;
    567     case IrOpcode::kJSDeleteProperty:
    568     case IrOpcode::kJSHasProperty:
    569     case IrOpcode::kJSInstanceOf:
    570       // Type is Boolean.
    571       CheckUpperIs(node, Type::Boolean());
    572       break;
    573     case IrOpcode::kJSTypeOf:
    574       // Type is String.
    575       CheckUpperIs(node, Type::String());
    576       break;
    577 
    578     case IrOpcode::kJSLoadContext:
    579       // Type can be anything.
    580       CheckUpperIs(node, Type::Any());
    581       break;
    582     case IrOpcode::kJSStoreContext:
    583       // Type is empty.
    584       CheckNotTyped(node);
    585       break;
    586     case IrOpcode::kJSCreateFunctionContext:
    587     case IrOpcode::kJSCreateCatchContext:
    588     case IrOpcode::kJSCreateWithContext:
    589     case IrOpcode::kJSCreateBlockContext:
    590     case IrOpcode::kJSCreateModuleContext:
    591     case IrOpcode::kJSCreateScriptContext: {
    592       // Type is Context, and operand is Internal.
    593       Node* context = NodeProperties::GetContextInput(node);
    594       // TODO(rossberg): This should really be Is(Internal), but the typer
    595       // currently can't do backwards propagation.
    596       CheckUpperMaybe(context, Type::Internal());
    597       if (typing == TYPED) CHECK(NodeProperties::GetType(node)->IsContext());
    598       break;
    599     }
    600 
    601     case IrOpcode::kJSCallConstruct:
    602     case IrOpcode::kJSConvertReceiver:
    603       // Type is Receiver.
    604       CheckUpperIs(node, Type::Receiver());
    605       break;
    606     case IrOpcode::kJSCallFunction:
    607     case IrOpcode::kJSCallRuntime:
    608       // Type can be anything.
    609       CheckUpperIs(node, Type::Any());
    610       break;
    611 
    612     case IrOpcode::kJSForInPrepare: {
    613       // TODO(bmeurer): What are the constraints on thse?
    614       CheckUpperIs(node, Type::Any());
    615       break;
    616     }
    617     case IrOpcode::kJSForInDone: {
    618       // TODO(bmeurer): OSR breaks this invariant, although the node is not user
    619       // visible, so we know it is safe (fullcodegen has an unsigned smi there).
    620       // CheckValueInputIs(node, 0, Type::UnsignedSmall());
    621       break;
    622     }
    623     case IrOpcode::kJSForInNext: {
    624       CheckUpperIs(node, Type::Union(Type::Name(), Type::Undefined(), zone));
    625       break;
    626     }
    627     case IrOpcode::kJSForInStep: {
    628       // TODO(bmeurer): OSR breaks this invariant, although the node is not user
    629       // visible, so we know it is safe (fullcodegen has an unsigned smi there).
    630       // CheckValueInputIs(node, 0, Type::UnsignedSmall());
    631       CheckUpperIs(node, Type::UnsignedSmall());
    632       break;
    633     }
    634 
    635     case IrOpcode::kJSLoadMessage:
    636     case IrOpcode::kJSStoreMessage:
    637       break;
    638 
    639     case IrOpcode::kJSGeneratorStore:
    640       CheckNotTyped(node);
    641       break;
    642 
    643     case IrOpcode::kJSGeneratorRestoreContinuation:
    644       CheckUpperIs(node, Type::SignedSmall());
    645       break;
    646 
    647     case IrOpcode::kJSGeneratorRestoreRegister:
    648       CheckUpperIs(node, Type::Any());
    649       break;
    650 
    651     case IrOpcode::kJSStackCheck:
    652       // Type is empty.
    653       CheckNotTyped(node);
    654       break;
    655 
    656     case IrOpcode::kDebugBreak:
    657       CheckNotTyped(node);
    658       break;
    659 
    660     case IrOpcode::kComment:
    661       CheckNotTyped(node);
    662       break;
    663 
    664     // Simplified operators
    665     // -------------------------------
    666     case IrOpcode::kBooleanNot:
    667       // Boolean -> Boolean
    668       CheckValueInputIs(node, 0, Type::Boolean());
    669       CheckUpperIs(node, Type::Boolean());
    670       break;
    671     case IrOpcode::kBooleanToNumber:
    672       // Boolean -> Number
    673       CheckValueInputIs(node, 0, Type::Boolean());
    674       CheckUpperIs(node, Type::Number());
    675       break;
    676     case IrOpcode::kNumberEqual:
    677       // (Number, Number) -> Boolean
    678       CheckValueInputIs(node, 0, Type::Number());
    679       CheckValueInputIs(node, 1, Type::Number());
    680       CheckUpperIs(node, Type::Boolean());
    681       break;
    682     case IrOpcode::kNumberLessThan:
    683     case IrOpcode::kNumberLessThanOrEqual:
    684       // (Number, Number) -> Boolean
    685       CheckValueInputIs(node, 0, Type::Number());
    686       CheckValueInputIs(node, 1, Type::Number());
    687       CheckUpperIs(node, Type::Boolean());
    688       break;
    689     case IrOpcode::kSpeculativeNumberAdd:
    690     case IrOpcode::kSpeculativeNumberSubtract:
    691     case IrOpcode::kSpeculativeNumberMultiply:
    692     case IrOpcode::kSpeculativeNumberDivide:
    693     case IrOpcode::kSpeculativeNumberModulus:
    694       CheckUpperIs(node, Type::Number());
    695       break;
    696     case IrOpcode::kSpeculativeNumberEqual:
    697     case IrOpcode::kSpeculativeNumberLessThan:
    698     case IrOpcode::kSpeculativeNumberLessThanOrEqual:
    699       CheckUpperIs(node, Type::Boolean());
    700       break;
    701     case IrOpcode::kNumberAdd:
    702     case IrOpcode::kNumberSubtract:
    703     case IrOpcode::kNumberMultiply:
    704     case IrOpcode::kNumberDivide:
    705       // (Number, Number) -> Number
    706       CheckValueInputIs(node, 0, Type::Number());
    707       CheckValueInputIs(node, 1, Type::Number());
    708       CheckUpperIs(node, Type::Number());
    709       break;
    710     case IrOpcode::kNumberModulus:
    711       // (Number, Number) -> Number
    712       CheckValueInputIs(node, 0, Type::Number());
    713       CheckValueInputIs(node, 1, Type::Number());
    714       CheckUpperIs(node, Type::Number());
    715       break;
    716     case IrOpcode::kNumberBitwiseOr:
    717     case IrOpcode::kNumberBitwiseXor:
    718     case IrOpcode::kNumberBitwiseAnd:
    719       // (Signed32, Signed32) -> Signed32
    720       CheckValueInputIs(node, 0, Type::Signed32());
    721       CheckValueInputIs(node, 1, Type::Signed32());
    722       CheckUpperIs(node, Type::Signed32());
    723       break;
    724     case IrOpcode::kNumberShiftLeft:
    725     case IrOpcode::kNumberShiftRight:
    726       // (Signed32, Unsigned32) -> Signed32
    727       CheckValueInputIs(node, 0, Type::Signed32());
    728       CheckValueInputIs(node, 1, Type::Unsigned32());
    729       CheckUpperIs(node, Type::Signed32());
    730       break;
    731     case IrOpcode::kNumberShiftRightLogical:
    732       // (Unsigned32, Unsigned32) -> Unsigned32
    733       CheckValueInputIs(node, 0, Type::Unsigned32());
    734       CheckValueInputIs(node, 1, Type::Unsigned32());
    735       CheckUpperIs(node, Type::Unsigned32());
    736       break;
    737     case IrOpcode::kNumberImul:
    738       // (Unsigned32, Unsigned32) -> Signed32
    739       CheckValueInputIs(node, 0, Type::Unsigned32());
    740       CheckValueInputIs(node, 1, Type::Unsigned32());
    741       CheckUpperIs(node, Type::Signed32());
    742       break;
    743     case IrOpcode::kNumberClz32:
    744       // Unsigned32 -> Unsigned32
    745       CheckValueInputIs(node, 0, Type::Unsigned32());
    746       CheckUpperIs(node, Type::Unsigned32());
    747       break;
    748     case IrOpcode::kNumberAtan2:
    749       // (Number, Number) -> Number
    750       CheckValueInputIs(node, 0, Type::Number());
    751       CheckValueInputIs(node, 1, Type::Number());
    752       CheckUpperIs(node, Type::Number());
    753       break;
    754     case IrOpcode::kNumberAbs:
    755     case IrOpcode::kNumberCeil:
    756     case IrOpcode::kNumberFloor:
    757     case IrOpcode::kNumberFround:
    758     case IrOpcode::kNumberAtan:
    759     case IrOpcode::kNumberAtanh:
    760     case IrOpcode::kNumberCos:
    761     case IrOpcode::kNumberExp:
    762     case IrOpcode::kNumberExpm1:
    763     case IrOpcode::kNumberLog:
    764     case IrOpcode::kNumberLog1p:
    765     case IrOpcode::kNumberLog2:
    766     case IrOpcode::kNumberLog10:
    767     case IrOpcode::kNumberCbrt:
    768     case IrOpcode::kNumberRound:
    769     case IrOpcode::kNumberSin:
    770     case IrOpcode::kNumberSqrt:
    771     case IrOpcode::kNumberTan:
    772     case IrOpcode::kNumberTrunc:
    773       // Number -> Number
    774       CheckValueInputIs(node, 0, Type::Number());
    775       CheckUpperIs(node, Type::Number());
    776       break;
    777     case IrOpcode::kNumberToInt32:
    778       // Number -> Signed32
    779       CheckValueInputIs(node, 0, Type::Number());
    780       CheckUpperIs(node, Type::Signed32());
    781       break;
    782     case IrOpcode::kNumberToUint32:
    783       // Number -> Unsigned32
    784       CheckValueInputIs(node, 0, Type::Number());
    785       CheckUpperIs(node, Type::Unsigned32());
    786       break;
    787     case IrOpcode::kPlainPrimitiveToNumber:
    788       // Type is Number.
    789       CheckUpperIs(node, Type::Number());
    790       break;
    791     case IrOpcode::kPlainPrimitiveToWord32:
    792       CheckUpperIs(node, Type::Number());
    793       break;
    794     case IrOpcode::kPlainPrimitiveToFloat64:
    795       CheckUpperIs(node, Type::Number());
    796       break;
    797     case IrOpcode::kStringEqual:
    798     case IrOpcode::kStringLessThan:
    799     case IrOpcode::kStringLessThanOrEqual:
    800       // (String, String) -> Boolean
    801       CheckValueInputIs(node, 0, Type::String());
    802       CheckValueInputIs(node, 1, Type::String());
    803       CheckUpperIs(node, Type::Boolean());
    804       break;
    805     case IrOpcode::kStringFromCharCode:
    806       // Number -> String
    807       CheckValueInputIs(node, 0, Type::Number());
    808       CheckUpperIs(node, Type::String());
    809       break;
    810     case IrOpcode::kStringToNumber:
    811       // String -> Number
    812       CheckValueInputIs(node, 0, Type::String());
    813       CheckUpperIs(node, Type::Number());
    814       break;
    815     case IrOpcode::kReferenceEqual: {
    816       // (Unique, Any) -> Boolean  and
    817       // (Any, Unique) -> Boolean
    818       CheckUpperIs(node, Type::Boolean());
    819       break;
    820     }
    821     case IrOpcode::kObjectIsCallable:
    822     case IrOpcode::kObjectIsNumber:
    823     case IrOpcode::kObjectIsReceiver:
    824     case IrOpcode::kObjectIsSmi:
    825     case IrOpcode::kObjectIsString:
    826     case IrOpcode::kObjectIsUndetectable:
    827       CheckValueInputIs(node, 0, Type::Any());
    828       CheckUpperIs(node, Type::Boolean());
    829       break;
    830     case IrOpcode::kAllocate:
    831       CheckValueInputIs(node, 0, Type::PlainNumber());
    832       CheckUpperIs(node, Type::TaggedPointer());
    833       break;
    834 
    835     case IrOpcode::kChangeTaggedSignedToInt32: {
    836       // Signed32 /\ Tagged -> Signed32 /\ UntaggedInt32
    837       // TODO(neis): Activate once ChangeRepresentation works in typer.
    838       // Type* from = Type::Intersect(Type::Signed32(), Type::Tagged());
    839       // Type* to = Type::Intersect(Type::Signed32(), Type::UntaggedInt32());
    840       // CheckValueInputIs(node, 0, from));
    841       // CheckUpperIs(node, to));
    842       break;
    843     }
    844     case IrOpcode::kChangeTaggedToInt32: {
    845       // Signed32 /\ Tagged -> Signed32 /\ UntaggedInt32
    846       // TODO(neis): Activate once ChangeRepresentation works in typer.
    847       // Type* from = Type::Intersect(Type::Signed32(), Type::Tagged());
    848       // Type* to = Type::Intersect(Type::Signed32(), Type::UntaggedInt32());
    849       // CheckValueInputIs(node, 0, from));
    850       // CheckUpperIs(node, to));
    851       break;
    852     }
    853     case IrOpcode::kChangeTaggedToUint32: {
    854       // Unsigned32 /\ Tagged -> Unsigned32 /\ UntaggedInt32
    855       // TODO(neis): Activate once ChangeRepresentation works in typer.
    856       // Type* from = Type::Intersect(Type::Unsigned32(), Type::Tagged());
    857       // Type* to =Type::Intersect(Type::Unsigned32(), Type::UntaggedInt32());
    858       // CheckValueInputIs(node, 0, from));
    859       // CheckUpperIs(node, to));
    860       break;
    861     }
    862     case IrOpcode::kChangeTaggedToFloat64: {
    863       // NumberOrUndefined /\ Tagged -> Number /\ UntaggedFloat64
    864       // TODO(neis): Activate once ChangeRepresentation works in typer.
    865       // Type* from = Type::Intersect(Type::Number(), Type::Tagged());
    866       // Type* to = Type::Intersect(Type::Number(), Type::UntaggedFloat64());
    867       // CheckValueInputIs(node, 0, from));
    868       // CheckUpperIs(node, to));
    869       break;
    870     }
    871     case IrOpcode::kTruncateTaggedToFloat64: {
    872       // NumberOrUndefined /\ Tagged -> Number /\ UntaggedFloat64
    873       // TODO(neis): Activate once ChangeRepresentation works in typer.
    874       // Type* from = Type::Intersect(Type::NumberOrUndefined(),
    875       // Type::Tagged());
    876       // Type* to = Type::Intersect(Type::Number(), Type::UntaggedFloat64());
    877       // CheckValueInputIs(node, 0, from));
    878       // CheckUpperIs(node, to));
    879       break;
    880     }
    881     case IrOpcode::kChangeInt31ToTaggedSigned: {
    882       // Signed31 /\ UntaggedInt32 -> Signed31 /\ Tagged
    883       // TODO(neis): Activate once ChangeRepresentation works in typer.
    884       // Type* from =Type::Intersect(Type::Signed31(), Type::UntaggedInt32());
    885       // Type* to = Type::Intersect(Type::Signed31(), Type::Tagged());
    886       // CheckValueInputIs(node, 0, from));
    887       // CheckUpperIs(node, to));
    888       break;
    889     }
    890     case IrOpcode::kChangeInt32ToTagged: {
    891       // Signed32 /\ UntaggedInt32 -> Signed32 /\ Tagged
    892       // TODO(neis): Activate once ChangeRepresentation works in typer.
    893       // Type* from =Type::Intersect(Type::Signed32(), Type::UntaggedInt32());
    894       // Type* to = Type::Intersect(Type::Signed32(), Type::Tagged());
    895       // CheckValueInputIs(node, 0, from));
    896       // CheckUpperIs(node, to));
    897       break;
    898     }
    899     case IrOpcode::kChangeUint32ToTagged: {
    900       // Unsigned32 /\ UntaggedInt32 -> Unsigned32 /\ Tagged
    901       // TODO(neis): Activate once ChangeRepresentation works in typer.
    902       // Type* from=Type::Intersect(Type::Unsigned32(),Type::UntaggedInt32());
    903       // Type* to = Type::Intersect(Type::Unsigned32(), Type::Tagged());
    904       // CheckValueInputIs(node, 0, from));
    905       // CheckUpperIs(node, to));
    906       break;
    907     }
    908     case IrOpcode::kChangeFloat64ToTagged: {
    909       // Number /\ UntaggedFloat64 -> Number /\ Tagged
    910       // TODO(neis): Activate once ChangeRepresentation works in typer.
    911       // Type* from =Type::Intersect(Type::Number(), Type::UntaggedFloat64());
    912       // Type* to = Type::Intersect(Type::Number(), Type::Tagged());
    913       // CheckValueInputIs(node, 0, from));
    914       // CheckUpperIs(node, to));
    915       break;
    916     }
    917     case IrOpcode::kChangeTaggedToBit: {
    918       // Boolean /\ TaggedPtr -> Boolean /\ UntaggedInt1
    919       // TODO(neis): Activate once ChangeRepresentation works in typer.
    920       // Type* from = Type::Intersect(Type::Boolean(), Type::TaggedPtr());
    921       // Type* to = Type::Intersect(Type::Boolean(), Type::UntaggedInt1());
    922       // CheckValueInputIs(node, 0, from));
    923       // CheckUpperIs(node, to));
    924       break;
    925     }
    926     case IrOpcode::kChangeBitToTagged: {
    927       // Boolean /\ UntaggedInt1 -> Boolean /\ TaggedPtr
    928       // TODO(neis): Activate once ChangeRepresentation works in typer.
    929       // Type* from = Type::Intersect(Type::Boolean(), Type::UntaggedInt1());
    930       // Type* to = Type::Intersect(Type::Boolean(), Type::TaggedPtr());
    931       // CheckValueInputIs(node, 0, from));
    932       // CheckUpperIs(node, to));
    933       break;
    934     }
    935     case IrOpcode::kTruncateTaggedToWord32: {
    936       // Number /\ Tagged -> Signed32 /\ UntaggedInt32
    937       // TODO(neis): Activate once ChangeRepresentation works in typer.
    938       // Type* from = Type::Intersect(Type::Number(), Type::Tagged());
    939       // Type* to = Type::Intersect(Type::Number(), Type::UntaggedInt32());
    940       // CheckValueInputIs(node, 0, from));
    941       // CheckUpperIs(node, to));
    942       break;
    943     }
    944 
    945     case IrOpcode::kCheckBounds:
    946       CheckValueInputIs(node, 0, Type::Any());
    947       CheckValueInputIs(node, 1, Type::Unsigned31());
    948       CheckUpperIs(node, Type::Unsigned31());
    949       break;
    950     case IrOpcode::kCheckTaggedSigned:
    951       CheckValueInputIs(node, 0, Type::Any());
    952       CheckUpperIs(node, Type::TaggedSigned());
    953       break;
    954     case IrOpcode::kCheckTaggedPointer:
    955       CheckValueInputIs(node, 0, Type::Any());
    956       CheckUpperIs(node, Type::TaggedPointer());
    957       break;
    958 
    959     case IrOpcode::kCheckedInt32Add:
    960     case IrOpcode::kCheckedInt32Sub:
    961     case IrOpcode::kCheckedUint32ToInt32:
    962     case IrOpcode::kCheckedFloat64ToInt32:
    963     case IrOpcode::kCheckedTaggedToInt32:
    964     case IrOpcode::kCheckedTaggedToFloat64:
    965       break;
    966 
    967     case IrOpcode::kCheckFloat64Hole:
    968       CheckValueInputIs(node, 0, Type::Number());
    969       CheckUpperIs(node, Type::Number());
    970       break;
    971     case IrOpcode::kCheckTaggedHole:
    972       CheckValueInputIs(node, 0, Type::Any());
    973       CheckUpperIs(node, Type::Any());
    974       break;
    975 
    976     case IrOpcode::kLoadField:
    977       // Object -> fieldtype
    978       // TODO(rossberg): activate once machine ops are typed.
    979       // CheckValueInputIs(node, 0, Type::Object());
    980       // CheckUpperIs(node, FieldAccessOf(node->op()).type));
    981       break;
    982     case IrOpcode::kLoadBuffer:
    983       break;
    984     case IrOpcode::kLoadElement:
    985       // Object -> elementtype
    986       // TODO(rossberg): activate once machine ops are typed.
    987       // CheckValueInputIs(node, 0, Type::Object());
    988       // CheckUpperIs(node, ElementAccessOf(node->op()).type));
    989       break;
    990     case IrOpcode::kStoreField:
    991       // (Object, fieldtype) -> _|_
    992       // TODO(rossberg): activate once machine ops are typed.
    993       // CheckValueInputIs(node, 0, Type::Object());
    994       // CheckValueInputIs(node, 1, FieldAccessOf(node->op()).type));
    995       CheckNotTyped(node);
    996       break;
    997     case IrOpcode::kStoreBuffer:
    998       break;
    999     case IrOpcode::kStoreElement:
   1000       // (Object, elementtype) -> _|_
   1001       // TODO(rossberg): activate once machine ops are typed.
   1002       // CheckValueInputIs(node, 0, Type::Object());
   1003       // CheckValueInputIs(node, 1, ElementAccessOf(node->op()).type));
   1004       CheckNotTyped(node);
   1005       break;
   1006     case IrOpcode::kNumberSilenceNaN:
   1007       CheckValueInputIs(node, 0, Type::Number());
   1008       CheckUpperIs(node, Type::Number());
   1009       break;
   1010 
   1011     // Machine operators
   1012     // -----------------------
   1013     case IrOpcode::kLoad:
   1014     case IrOpcode::kStore:
   1015     case IrOpcode::kStackSlot:
   1016     case IrOpcode::kWord32And:
   1017     case IrOpcode::kWord32Or:
   1018     case IrOpcode::kWord32Xor:
   1019     case IrOpcode::kWord32Shl:
   1020     case IrOpcode::kWord32Shr:
   1021     case IrOpcode::kWord32Sar:
   1022     case IrOpcode::kWord32Ror:
   1023     case IrOpcode::kWord32Equal:
   1024     case IrOpcode::kWord32Clz:
   1025     case IrOpcode::kWord32Ctz:
   1026     case IrOpcode::kWord32ReverseBits:
   1027     case IrOpcode::kWord32Popcnt:
   1028     case IrOpcode::kWord64And:
   1029     case IrOpcode::kWord64Or:
   1030     case IrOpcode::kWord64Xor:
   1031     case IrOpcode::kWord64Shl:
   1032     case IrOpcode::kWord64Shr:
   1033     case IrOpcode::kWord64Sar:
   1034     case IrOpcode::kWord64Ror:
   1035     case IrOpcode::kWord64Clz:
   1036     case IrOpcode::kWord64Popcnt:
   1037     case IrOpcode::kWord64Ctz:
   1038     case IrOpcode::kWord64ReverseBits:
   1039     case IrOpcode::kWord64Equal:
   1040     case IrOpcode::kInt32Add:
   1041     case IrOpcode::kInt32AddWithOverflow:
   1042     case IrOpcode::kInt32Sub:
   1043     case IrOpcode::kInt32SubWithOverflow:
   1044     case IrOpcode::kInt32Mul:
   1045     case IrOpcode::kInt32MulHigh:
   1046     case IrOpcode::kInt32Div:
   1047     case IrOpcode::kInt32Mod:
   1048     case IrOpcode::kInt32LessThan:
   1049     case IrOpcode::kInt32LessThanOrEqual:
   1050     case IrOpcode::kUint32Div:
   1051     case IrOpcode::kUint32Mod:
   1052     case IrOpcode::kUint32MulHigh:
   1053     case IrOpcode::kUint32LessThan:
   1054     case IrOpcode::kUint32LessThanOrEqual:
   1055     case IrOpcode::kInt64Add:
   1056     case IrOpcode::kInt64AddWithOverflow:
   1057     case IrOpcode::kInt64Sub:
   1058     case IrOpcode::kInt64SubWithOverflow:
   1059     case IrOpcode::kInt64Mul:
   1060     case IrOpcode::kInt64Div:
   1061     case IrOpcode::kInt64Mod:
   1062     case IrOpcode::kInt64LessThan:
   1063     case IrOpcode::kInt64LessThanOrEqual:
   1064     case IrOpcode::kUint64Div:
   1065     case IrOpcode::kUint64Mod:
   1066     case IrOpcode::kUint64LessThan:
   1067     case IrOpcode::kUint64LessThanOrEqual:
   1068     case IrOpcode::kFloat32Add:
   1069     case IrOpcode::kFloat32Sub:
   1070     case IrOpcode::kFloat32SubPreserveNan:
   1071     case IrOpcode::kFloat32Neg:
   1072     case IrOpcode::kFloat32Mul:
   1073     case IrOpcode::kFloat32Div:
   1074     case IrOpcode::kFloat32Max:
   1075     case IrOpcode::kFloat32Min:
   1076     case IrOpcode::kFloat32Abs:
   1077     case IrOpcode::kFloat32Sqrt:
   1078     case IrOpcode::kFloat32Equal:
   1079     case IrOpcode::kFloat32LessThan:
   1080     case IrOpcode::kFloat32LessThanOrEqual:
   1081     case IrOpcode::kFloat64Add:
   1082     case IrOpcode::kFloat64Sub:
   1083     case IrOpcode::kFloat64SubPreserveNan:
   1084     case IrOpcode::kFloat64Neg:
   1085     case IrOpcode::kFloat64Mul:
   1086     case IrOpcode::kFloat64Div:
   1087     case IrOpcode::kFloat64Mod:
   1088     case IrOpcode::kFloat64Max:
   1089     case IrOpcode::kFloat64Min:
   1090     case IrOpcode::kFloat64Abs:
   1091     case IrOpcode::kFloat64Atan:
   1092     case IrOpcode::kFloat64Atan2:
   1093     case IrOpcode::kFloat64Atanh:
   1094     case IrOpcode::kFloat64Cos:
   1095     case IrOpcode::kFloat64Exp:
   1096     case IrOpcode::kFloat64Expm1:
   1097     case IrOpcode::kFloat64Log:
   1098     case IrOpcode::kFloat64Log1p:
   1099     case IrOpcode::kFloat64Log2:
   1100     case IrOpcode::kFloat64Log10:
   1101     case IrOpcode::kFloat64Cbrt:
   1102     case IrOpcode::kFloat64Sin:
   1103     case IrOpcode::kFloat64Sqrt:
   1104     case IrOpcode::kFloat64Tan:
   1105     case IrOpcode::kFloat32RoundDown:
   1106     case IrOpcode::kFloat64RoundDown:
   1107     case IrOpcode::kFloat32RoundUp:
   1108     case IrOpcode::kFloat64RoundUp:
   1109     case IrOpcode::kFloat32RoundTruncate:
   1110     case IrOpcode::kFloat64RoundTruncate:
   1111     case IrOpcode::kFloat64RoundTiesAway:
   1112     case IrOpcode::kFloat32RoundTiesEven:
   1113     case IrOpcode::kFloat64RoundTiesEven:
   1114     case IrOpcode::kFloat64Equal:
   1115     case IrOpcode::kFloat64LessThan:
   1116     case IrOpcode::kFloat64LessThanOrEqual:
   1117     case IrOpcode::kTruncateInt64ToInt32:
   1118     case IrOpcode::kRoundFloat64ToInt32:
   1119     case IrOpcode::kRoundInt32ToFloat32:
   1120     case IrOpcode::kRoundInt64ToFloat32:
   1121     case IrOpcode::kRoundInt64ToFloat64:
   1122     case IrOpcode::kRoundUint32ToFloat32:
   1123     case IrOpcode::kRoundUint64ToFloat64:
   1124     case IrOpcode::kRoundUint64ToFloat32:
   1125     case IrOpcode::kTruncateFloat64ToFloat32:
   1126     case IrOpcode::kTruncateFloat64ToWord32:
   1127     case IrOpcode::kBitcastFloat32ToInt32:
   1128     case IrOpcode::kBitcastFloat64ToInt64:
   1129     case IrOpcode::kBitcastInt32ToFloat32:
   1130     case IrOpcode::kBitcastInt64ToFloat64:
   1131     case IrOpcode::kBitcastWordToTagged:
   1132     case IrOpcode::kChangeInt32ToInt64:
   1133     case IrOpcode::kChangeUint32ToUint64:
   1134     case IrOpcode::kChangeInt32ToFloat64:
   1135     case IrOpcode::kChangeUint32ToFloat64:
   1136     case IrOpcode::kChangeFloat32ToFloat64:
   1137     case IrOpcode::kChangeFloat64ToInt32:
   1138     case IrOpcode::kChangeFloat64ToUint32:
   1139     case IrOpcode::kFloat64SilenceNaN:
   1140     case IrOpcode::kTruncateFloat64ToUint32:
   1141     case IrOpcode::kTruncateFloat32ToInt32:
   1142     case IrOpcode::kTruncateFloat32ToUint32:
   1143     case IrOpcode::kTryTruncateFloat32ToInt64:
   1144     case IrOpcode::kTryTruncateFloat64ToInt64:
   1145     case IrOpcode::kTryTruncateFloat32ToUint64:
   1146     case IrOpcode::kTryTruncateFloat64ToUint64:
   1147     case IrOpcode::kFloat64ExtractLowWord32:
   1148     case IrOpcode::kFloat64ExtractHighWord32:
   1149     case IrOpcode::kFloat64InsertLowWord32:
   1150     case IrOpcode::kFloat64InsertHighWord32:
   1151     case IrOpcode::kInt32PairAdd:
   1152     case IrOpcode::kInt32PairSub:
   1153     case IrOpcode::kInt32PairMul:
   1154     case IrOpcode::kWord32PairShl:
   1155     case IrOpcode::kWord32PairShr:
   1156     case IrOpcode::kWord32PairSar:
   1157     case IrOpcode::kLoadStackPointer:
   1158     case IrOpcode::kLoadFramePointer:
   1159     case IrOpcode::kLoadParentFramePointer:
   1160     case IrOpcode::kCheckedLoad:
   1161     case IrOpcode::kCheckedStore:
   1162     case IrOpcode::kAtomicLoad:
   1163     case IrOpcode::kAtomicStore:
   1164 
   1165 #define SIMD_MACHINE_OP_CASE(Name) case IrOpcode::k##Name:
   1166       MACHINE_SIMD_OP_LIST(SIMD_MACHINE_OP_CASE)
   1167 #undef SIMD_MACHINE_OP_CASE
   1168 
   1169       // TODO(rossberg): Check.
   1170       break;
   1171   }
   1172 }  // NOLINT(readability/fn_size)
   1173 
   1174 void Verifier::Run(Graph* graph, Typing typing, CheckInputs check_inputs) {
   1175   CHECK_NOT_NULL(graph->start());
   1176   CHECK_NOT_NULL(graph->end());
   1177   Zone zone(graph->zone()->allocator());
   1178   Visitor visitor(&zone, typing, check_inputs);
   1179   AllNodes all(&zone, graph);
   1180   for (Node* node : all.live) visitor.Check(node);
   1181 
   1182   // Check the uniqueness of projections.
   1183   for (Node* proj : all.live) {
   1184     if (proj->opcode() != IrOpcode::kProjection) continue;
   1185     Node* node = proj->InputAt(0);
   1186     for (Node* other : node->uses()) {
   1187       if (all.IsLive(other) && other != proj &&
   1188           other->opcode() == IrOpcode::kProjection &&
   1189           ProjectionIndexOf(other->op()) == ProjectionIndexOf(proj->op())) {
   1190         V8_Fatal(__FILE__, __LINE__,
   1191                  "Node #%d:%s has duplicate projections #%d and #%d",
   1192                  node->id(), node->op()->mnemonic(), proj->id(), other->id());
   1193       }
   1194     }
   1195   }
   1196 }
   1197 
   1198 
   1199 // -----------------------------------------------------------------------------
   1200 
   1201 static bool HasDominatingDef(Schedule* schedule, Node* node,
   1202                              BasicBlock* container, BasicBlock* use_block,
   1203                              int use_pos) {
   1204   BasicBlock* block = use_block;
   1205   while (true) {
   1206     while (use_pos >= 0) {
   1207       if (block->NodeAt(use_pos) == node) return true;
   1208       use_pos--;
   1209     }
   1210     block = block->dominator();
   1211     if (block == nullptr) break;
   1212     use_pos = static_cast<int>(block->NodeCount()) - 1;
   1213     if (node == block->control_input()) return true;
   1214   }
   1215   return false;
   1216 }
   1217 
   1218 
   1219 static bool Dominates(Schedule* schedule, Node* dominator, Node* dominatee) {
   1220   BasicBlock* dom = schedule->block(dominator);
   1221   BasicBlock* sub = schedule->block(dominatee);
   1222   while (sub != nullptr) {
   1223     if (sub == dom) {
   1224       return true;
   1225     }
   1226     sub = sub->dominator();
   1227   }
   1228   return false;
   1229 }
   1230 
   1231 
   1232 static void CheckInputsDominate(Schedule* schedule, BasicBlock* block,
   1233                                 Node* node, int use_pos) {
   1234   for (int j = node->op()->ValueInputCount() - 1; j >= 0; j--) {
   1235     BasicBlock* use_block = block;
   1236     if (node->opcode() == IrOpcode::kPhi) {
   1237       use_block = use_block->PredecessorAt(j);
   1238       use_pos = static_cast<int>(use_block->NodeCount()) - 1;
   1239     }
   1240     Node* input = node->InputAt(j);
   1241     if (!HasDominatingDef(schedule, node->InputAt(j), block, use_block,
   1242                           use_pos)) {
   1243       V8_Fatal(__FILE__, __LINE__,
   1244                "Node #%d:%s in B%d is not dominated by input@%d #%d:%s",
   1245                node->id(), node->op()->mnemonic(), block->rpo_number(), j,
   1246                input->id(), input->op()->mnemonic());
   1247     }
   1248   }
   1249   // Ensure that nodes are dominated by their control inputs;
   1250   // kEnd is an exception, as unreachable blocks resulting from kMerge
   1251   // are not in the RPO.
   1252   if (node->op()->ControlInputCount() == 1 &&
   1253       node->opcode() != IrOpcode::kEnd) {
   1254     Node* ctl = NodeProperties::GetControlInput(node);
   1255     if (!Dominates(schedule, ctl, node)) {
   1256       V8_Fatal(__FILE__, __LINE__,
   1257                "Node #%d:%s in B%d is not dominated by control input #%d:%s",
   1258                node->id(), node->op()->mnemonic(), block->rpo_number(),
   1259                ctl->id(), ctl->op()->mnemonic());
   1260     }
   1261   }
   1262 }
   1263 
   1264 
   1265 void ScheduleVerifier::Run(Schedule* schedule) {
   1266   const size_t count = schedule->BasicBlockCount();
   1267   Zone tmp_zone(schedule->zone()->allocator());
   1268   Zone* zone = &tmp_zone;
   1269   BasicBlock* start = schedule->start();
   1270   BasicBlockVector* rpo_order = schedule->rpo_order();
   1271 
   1272   // Verify the RPO order contains only blocks from this schedule.
   1273   CHECK_GE(count, rpo_order->size());
   1274   for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
   1275        ++b) {
   1276     CHECK_EQ((*b), schedule->GetBlockById((*b)->id()));
   1277     // All predecessors and successors should be in rpo and in this schedule.
   1278     for (BasicBlock const* predecessor : (*b)->predecessors()) {
   1279       CHECK_GE(predecessor->rpo_number(), 0);
   1280       CHECK_EQ(predecessor, schedule->GetBlockById(predecessor->id()));
   1281     }
   1282     for (BasicBlock const* successor : (*b)->successors()) {
   1283       CHECK_GE(successor->rpo_number(), 0);
   1284       CHECK_EQ(successor, schedule->GetBlockById(successor->id()));
   1285     }
   1286   }
   1287 
   1288   // Verify RPO numbers of blocks.
   1289   CHECK_EQ(start, rpo_order->at(0));  // Start should be first.
   1290   for (size_t b = 0; b < rpo_order->size(); b++) {
   1291     BasicBlock* block = rpo_order->at(b);
   1292     CHECK_EQ(static_cast<int>(b), block->rpo_number());
   1293     BasicBlock* dom = block->dominator();
   1294     if (b == 0) {
   1295       // All blocks except start should have a dominator.
   1296       CHECK_NULL(dom);
   1297     } else {
   1298       // Check that the immediate dominator appears somewhere before the block.
   1299       CHECK_NOT_NULL(dom);
   1300       CHECK_LT(dom->rpo_number(), block->rpo_number());
   1301     }
   1302   }
   1303 
   1304   // Verify that all blocks reachable from start are in the RPO.
   1305   BoolVector marked(static_cast<int>(count), false, zone);
   1306   {
   1307     ZoneQueue<BasicBlock*> queue(zone);
   1308     queue.push(start);
   1309     marked[start->id().ToSize()] = true;
   1310     while (!queue.empty()) {
   1311       BasicBlock* block = queue.front();
   1312       queue.pop();
   1313       for (size_t s = 0; s < block->SuccessorCount(); s++) {
   1314         BasicBlock* succ = block->SuccessorAt(s);
   1315         if (!marked[succ->id().ToSize()]) {
   1316           marked[succ->id().ToSize()] = true;
   1317           queue.push(succ);
   1318         }
   1319       }
   1320     }
   1321   }
   1322   // Verify marked blocks are in the RPO.
   1323   for (size_t i = 0; i < count; i++) {
   1324     BasicBlock* block = schedule->GetBlockById(BasicBlock::Id::FromSize(i));
   1325     if (marked[i]) {
   1326       CHECK_GE(block->rpo_number(), 0);
   1327       CHECK_EQ(block, rpo_order->at(block->rpo_number()));
   1328     }
   1329   }
   1330   // Verify RPO blocks are marked.
   1331   for (size_t b = 0; b < rpo_order->size(); b++) {
   1332     CHECK(marked[rpo_order->at(b)->id().ToSize()]);
   1333   }
   1334 
   1335   {
   1336     // Verify the dominance relation.
   1337     ZoneVector<BitVector*> dominators(zone);
   1338     dominators.resize(count, nullptr);
   1339 
   1340     // Compute a set of all the nodes that dominate a given node by using
   1341     // a forward fixpoint. O(n^2).
   1342     ZoneQueue<BasicBlock*> queue(zone);
   1343     queue.push(start);
   1344     dominators[start->id().ToSize()] =
   1345         new (zone) BitVector(static_cast<int>(count), zone);
   1346     while (!queue.empty()) {
   1347       BasicBlock* block = queue.front();
   1348       queue.pop();
   1349       BitVector* block_doms = dominators[block->id().ToSize()];
   1350       BasicBlock* idom = block->dominator();
   1351       if (idom != nullptr && !block_doms->Contains(idom->id().ToInt())) {
   1352         V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d",
   1353                  block->rpo_number(), idom->rpo_number());
   1354       }
   1355       for (size_t s = 0; s < block->SuccessorCount(); s++) {
   1356         BasicBlock* succ = block->SuccessorAt(s);
   1357         BitVector* succ_doms = dominators[succ->id().ToSize()];
   1358 
   1359         if (succ_doms == nullptr) {
   1360           // First time visiting the node. S.doms = B U B.doms
   1361           succ_doms = new (zone) BitVector(static_cast<int>(count), zone);
   1362           succ_doms->CopyFrom(*block_doms);
   1363           succ_doms->Add(block->id().ToInt());
   1364           dominators[succ->id().ToSize()] = succ_doms;
   1365           queue.push(succ);
   1366         } else {
   1367           // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms)
   1368           bool had = succ_doms->Contains(block->id().ToInt());
   1369           if (had) succ_doms->Remove(block->id().ToInt());
   1370           if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ);
   1371           if (had) succ_doms->Add(block->id().ToInt());
   1372         }
   1373       }
   1374     }
   1375 
   1376     // Verify the immediateness of dominators.
   1377     for (BasicBlockVector::iterator b = rpo_order->begin();
   1378          b != rpo_order->end(); ++b) {
   1379       BasicBlock* block = *b;
   1380       BasicBlock* idom = block->dominator();
   1381       if (idom == nullptr) continue;
   1382       BitVector* block_doms = dominators[block->id().ToSize()];
   1383 
   1384       for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) {
   1385         BasicBlock* dom =
   1386             schedule->GetBlockById(BasicBlock::Id::FromInt(it.Current()));
   1387         if (dom != idom &&
   1388             !dominators[idom->id().ToSize()]->Contains(dom->id().ToInt())) {
   1389           V8_Fatal(__FILE__, __LINE__,
   1390                    "Block B%d is not immediately dominated by B%d",
   1391                    block->rpo_number(), idom->rpo_number());
   1392         }
   1393       }
   1394     }
   1395   }
   1396 
   1397   // Verify phis are placed in the block of their control input.
   1398   for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
   1399        ++b) {
   1400     for (BasicBlock::const_iterator i = (*b)->begin(); i != (*b)->end(); ++i) {
   1401       Node* phi = *i;
   1402       if (phi->opcode() != IrOpcode::kPhi) continue;
   1403       // TODO(titzer): Nasty special case. Phis from RawMachineAssembler
   1404       // schedules don't have control inputs.
   1405       if (phi->InputCount() > phi->op()->ValueInputCount()) {
   1406         Node* control = NodeProperties::GetControlInput(phi);
   1407         CHECK(control->opcode() == IrOpcode::kMerge ||
   1408               control->opcode() == IrOpcode::kLoop);
   1409         CHECK_EQ((*b), schedule->block(control));
   1410       }
   1411     }
   1412   }
   1413 
   1414   // Verify that all uses are dominated by their definitions.
   1415   for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
   1416        ++b) {
   1417     BasicBlock* block = *b;
   1418 
   1419     // Check inputs to control for this block.
   1420     Node* control = block->control_input();
   1421     if (control != nullptr) {
   1422       CHECK_EQ(block, schedule->block(control));
   1423       CheckInputsDominate(schedule, block, control,
   1424                           static_cast<int>(block->NodeCount()) - 1);
   1425     }
   1426     // Check inputs for all nodes in the block.
   1427     for (size_t i = 0; i < block->NodeCount(); i++) {
   1428       Node* node = block->NodeAt(i);
   1429       CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1);
   1430     }
   1431   }
   1432 }
   1433 
   1434 
   1435 #ifdef DEBUG
   1436 
   1437 // static
   1438 void Verifier::VerifyNode(Node* node) {
   1439   CHECK_EQ(OperatorProperties::GetTotalInputCount(node->op()),
   1440            node->InputCount());
   1441   // If this node has no effect or no control outputs,
   1442   // we check that no its uses are effect or control inputs.
   1443   bool check_no_control = node->op()->ControlOutputCount() == 0;
   1444   bool check_no_effect = node->op()->EffectOutputCount() == 0;
   1445   bool check_no_frame_state = node->opcode() != IrOpcode::kFrameState;
   1446   if (check_no_effect || check_no_control) {
   1447     for (Edge edge : node->use_edges()) {
   1448       Node* const user = edge.from();
   1449       CHECK(!user->IsDead());
   1450       if (NodeProperties::IsControlEdge(edge)) {
   1451         CHECK(!check_no_control);
   1452       } else if (NodeProperties::IsEffectEdge(edge)) {
   1453         CHECK(!check_no_effect);
   1454       } else if (NodeProperties::IsFrameStateEdge(edge)) {
   1455         CHECK(!check_no_frame_state);
   1456       }
   1457     }
   1458   }
   1459   // Frame state inputs should be frame states (or sentinels).
   1460   for (int i = 0; i < OperatorProperties::GetFrameStateInputCount(node->op());
   1461        i++) {
   1462     Node* input = NodeProperties::GetFrameStateInput(node, i);
   1463     CHECK(input->opcode() == IrOpcode::kFrameState ||
   1464           input->opcode() == IrOpcode::kStart ||
   1465           input->opcode() == IrOpcode::kDead);
   1466   }
   1467   // Effect inputs should be effect-producing nodes (or sentinels).
   1468   for (int i = 0; i < node->op()->EffectInputCount(); i++) {
   1469     Node* input = NodeProperties::GetEffectInput(node, i);
   1470     CHECK(input->op()->EffectOutputCount() > 0 ||
   1471           input->opcode() == IrOpcode::kDead);
   1472   }
   1473   // Control inputs should be control-producing nodes (or sentinels).
   1474   for (int i = 0; i < node->op()->ControlInputCount(); i++) {
   1475     Node* input = NodeProperties::GetControlInput(node, i);
   1476     CHECK(input->op()->ControlOutputCount() > 0 ||
   1477           input->opcode() == IrOpcode::kDead);
   1478   }
   1479 }
   1480 
   1481 
   1482 void Verifier::VerifyEdgeInputReplacement(const Edge& edge,
   1483                                           const Node* replacement) {
   1484   // Check that the user does not misuse the replacement.
   1485   DCHECK(!NodeProperties::IsControlEdge(edge) ||
   1486          replacement->op()->ControlOutputCount() > 0);
   1487   DCHECK(!NodeProperties::IsEffectEdge(edge) ||
   1488          replacement->op()->EffectOutputCount() > 0);
   1489   DCHECK(!NodeProperties::IsFrameStateEdge(edge) ||
   1490          replacement->opcode() == IrOpcode::kFrameState);
   1491 }
   1492 
   1493 #endif  // DEBUG
   1494 
   1495 }  // namespace compiler
   1496 }  // namespace internal
   1497 }  // namespace v8
   1498