Home | History | Annotate | Download | only in compiler 
      1 // Copyright 2015 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/node-properties.h"
      6 #include "src/compiler/common-operator.h"
      7 #include "src/compiler/graph.h"
      8 #include "src/compiler/js-operator.h"
      9 #include "src/compiler/linkage.h"
     10 #include "src/compiler/node-matchers.h"
     11 #include "src/compiler/operator-properties.h"
     12 #include "src/compiler/simplified-operator.h"
     13 #include "src/compiler/verifier.h"
     14 #include "src/handles-inl.h"
     15 #include "src/objects-inl.h"
     16 
     17 namespace v8 {
     18 namespace internal {
     19 namespace compiler {
     20 
     21 // static
     22 int NodeProperties::PastValueIndex(Node* node) {
     23   return FirstValueIndex(node) + node->op()->ValueInputCount();
     24 }
     25 
     26 
     27 // static
     28 int NodeProperties::PastContextIndex(Node* node) {
     29   return FirstContextIndex(node) +
     30          OperatorProperties::GetContextInputCount(node->op());
     31 }
     32 
     33 
     34 // static
     35 int NodeProperties::PastFrameStateIndex(Node* node) {
     36   return FirstFrameStateIndex(node) +
     37          OperatorProperties::GetFrameStateInputCount(node->op());
     38 }
     39 
     40 
     41 // static
     42 int NodeProperties::PastEffectIndex(Node* node) {
     43   return FirstEffectIndex(node) + node->op()->EffectInputCount();
     44 }
     45 
     46 
     47 // static
     48 int NodeProperties::PastControlIndex(Node* node) {
     49   return FirstControlIndex(node) + node->op()->ControlInputCount();
     50 }
     51 
     52 
     53 // static
     54 Node* NodeProperties::GetValueInput(Node* node, int index) {
     55   DCHECK(0 <= index && index < node->op()->ValueInputCount());
     56   return node->InputAt(FirstValueIndex(node) + index);
     57 }
     58 
     59 
     60 // static
     61 Node* NodeProperties::GetContextInput(Node* node) {
     62   DCHECK(OperatorProperties::HasContextInput(node->op()));
     63   return node->InputAt(FirstContextIndex(node));
     64 }
     65 
     66 
     67 // static
     68 Node* NodeProperties::GetFrameStateInput(Node* node) {
     69   DCHECK_EQ(1, OperatorProperties::GetFrameStateInputCount(node->op()));
     70   return node->InputAt(FirstFrameStateIndex(node));
     71 }
     72 
     73 
     74 // static
     75 Node* NodeProperties::GetEffectInput(Node* node, int index) {
     76   DCHECK(0 <= index && index < node->op()->EffectInputCount());
     77   return node->InputAt(FirstEffectIndex(node) + index);
     78 }
     79 
     80 
     81 // static
     82 Node* NodeProperties::GetControlInput(Node* node, int index) {
     83   DCHECK(0 <= index && index < node->op()->ControlInputCount());
     84   return node->InputAt(FirstControlIndex(node) + index);
     85 }
     86 
     87 
     88 // static
     89 bool NodeProperties::IsValueEdge(Edge edge) {
     90   Node* const node = edge.from();
     91   return IsInputRange(edge, FirstValueIndex(node),
     92                       node->op()->ValueInputCount());
     93 }
     94 
     95 
     96 // static
     97 bool NodeProperties::IsContextEdge(Edge edge) {
     98   Node* const node = edge.from();
     99   return IsInputRange(edge, FirstContextIndex(node),
    100                       OperatorProperties::GetContextInputCount(node->op()));
    101 }
    102 
    103 
    104 // static
    105 bool NodeProperties::IsFrameStateEdge(Edge edge) {
    106   Node* const node = edge.from();
    107   return IsInputRange(edge, FirstFrameStateIndex(node),
    108                       OperatorProperties::GetFrameStateInputCount(node->op()));
    109 }
    110 
    111 
    112 // static
    113 bool NodeProperties::IsEffectEdge(Edge edge) {
    114   Node* const node = edge.from();
    115   return IsInputRange(edge, FirstEffectIndex(node),
    116                       node->op()->EffectInputCount());
    117 }
    118 
    119 
    120 // static
    121 bool NodeProperties::IsControlEdge(Edge edge) {
    122   Node* const node = edge.from();
    123   return IsInputRange(edge, FirstControlIndex(node),
    124                       node->op()->ControlInputCount());
    125 }
    126 
    127 
    128 // static
    129 bool NodeProperties::IsExceptionalCall(Node* node) {
    130   if (node->op()->HasProperty(Operator::kNoThrow)) return false;
    131   for (Edge const edge : node->use_edges()) {
    132     if (!NodeProperties::IsControlEdge(edge)) continue;
    133     if (edge.from()->opcode() == IrOpcode::kIfException) return true;
    134   }
    135   return false;
    136 }
    137 
    138 
    139 // static
    140 void NodeProperties::ReplaceValueInput(Node* node, Node* value, int index) {
    141   DCHECK(index < node->op()->ValueInputCount());
    142   node->ReplaceInput(FirstValueIndex(node) + index, value);
    143 }
    144 
    145 
    146 // static
    147 void NodeProperties::ReplaceValueInputs(Node* node, Node* value) {
    148   int value_input_count = node->op()->ValueInputCount();
    149   DCHECK_LE(1, value_input_count);
    150   node->ReplaceInput(0, value);
    151   while (--value_input_count > 0) {
    152     node->RemoveInput(value_input_count);
    153   }
    154 }
    155 
    156 
    157 // static
    158 void NodeProperties::ReplaceContextInput(Node* node, Node* context) {
    159   node->ReplaceInput(FirstContextIndex(node), context);
    160 }
    161 
    162 
    163 // static
    164 void NodeProperties::ReplaceControlInput(Node* node, Node* control, int index) {
    165   DCHECK(index < node->op()->ControlInputCount());
    166   node->ReplaceInput(FirstControlIndex(node) + index, control);
    167 }
    168 
    169 
    170 // static
    171 void NodeProperties::ReplaceEffectInput(Node* node, Node* effect, int index) {
    172   DCHECK(index < node->op()->EffectInputCount());
    173   return node->ReplaceInput(FirstEffectIndex(node) + index, effect);
    174 }
    175 
    176 
    177 // static
    178 void NodeProperties::ReplaceFrameStateInput(Node* node, Node* frame_state) {
    179   DCHECK_EQ(1, OperatorProperties::GetFrameStateInputCount(node->op()));
    180   node->ReplaceInput(FirstFrameStateIndex(node), frame_state);
    181 }
    182 
    183 
    184 // static
    185 void NodeProperties::RemoveNonValueInputs(Node* node) {
    186   node->TrimInputCount(node->op()->ValueInputCount());
    187 }
    188 
    189 
    190 // static
    191 void NodeProperties::RemoveValueInputs(Node* node) {
    192   int value_input_count = node->op()->ValueInputCount();
    193   while (--value_input_count >= 0) {
    194     node->RemoveInput(value_input_count);
    195   }
    196 }
    197 
    198 
    199 void NodeProperties::MergeControlToEnd(Graph* graph,
    200                                        CommonOperatorBuilder* common,
    201                                        Node* node) {
    202   graph->end()->AppendInput(graph->zone(), node);
    203   graph->end()->set_op(common->End(graph->end()->InputCount()));
    204 }
    205 
    206 
    207 // static
    208 void NodeProperties::ReplaceUses(Node* node, Node* value, Node* effect,
    209                                  Node* success, Node* exception) {
    210   // Requires distinguishing between value, effect and control edges.
    211   for (Edge edge : node->use_edges()) {
    212     if (IsControlEdge(edge)) {
    213       if (edge.from()->opcode() == IrOpcode::kIfSuccess) {
    214         DCHECK_NOT_NULL(success);
    215         edge.UpdateTo(success);
    216       } else if (edge.from()->opcode() == IrOpcode::kIfException) {
    217         DCHECK_NOT_NULL(exception);
    218         edge.UpdateTo(exception);
    219       } else {
    220         DCHECK_NOT_NULL(success);
    221         edge.UpdateTo(success);
    222       }
    223     } else if (IsEffectEdge(edge)) {
    224       DCHECK_NOT_NULL(effect);
    225       edge.UpdateTo(effect);
    226     } else {
    227       DCHECK_NOT_NULL(value);
    228       edge.UpdateTo(value);
    229     }
    230   }
    231 }
    232 
    233 
    234 // static
    235 void NodeProperties::ChangeOp(Node* node, const Operator* new_op) {
    236   node->set_op(new_op);
    237   Verifier::VerifyNode(node);
    238 }
    239 
    240 
    241 // static
    242 Node* NodeProperties::FindFrameStateBefore(Node* node) {
    243   Node* effect = NodeProperties::GetEffectInput(node);
    244   while (effect->opcode() != IrOpcode::kCheckpoint) {
    245     if (effect->opcode() == IrOpcode::kDead) return effect;
    246     DCHECK_EQ(1, effect->op()->EffectInputCount());
    247     effect = NodeProperties::GetEffectInput(effect);
    248   }
    249   Node* frame_state = GetFrameStateInput(effect);
    250   return frame_state;
    251 }
    252 
    253 // static
    254 Node* NodeProperties::FindProjection(Node* node, size_t projection_index) {
    255   for (auto use : node->uses()) {
    256     if (use->opcode() == IrOpcode::kProjection &&
    257         ProjectionIndexOf(use->op()) == projection_index) {
    258       return use;
    259     }
    260   }
    261   return nullptr;
    262 }
    263 
    264 
    265 // static
    266 void NodeProperties::CollectControlProjections(Node* node, Node** projections,
    267                                                size_t projection_count) {
    268 #ifdef DEBUG
    269   DCHECK_LE(static_cast<int>(projection_count), node->UseCount());
    270   std::memset(projections, 0, sizeof(*projections) * projection_count);
    271 #endif
    272   size_t if_value_index = 0;
    273   for (Edge const edge : node->use_edges()) {
    274     if (!IsControlEdge(edge)) continue;
    275     Node* use = edge.from();
    276     size_t index;
    277     switch (use->opcode()) {
    278       case IrOpcode::kIfTrue:
    279         DCHECK_EQ(IrOpcode::kBranch, node->opcode());
    280         index = 0;
    281         break;
    282       case IrOpcode::kIfFalse:
    283         DCHECK_EQ(IrOpcode::kBranch, node->opcode());
    284         index = 1;
    285         break;
    286       case IrOpcode::kIfSuccess:
    287         DCHECK(!node->op()->HasProperty(Operator::kNoThrow));
    288         index = 0;
    289         break;
    290       case IrOpcode::kIfException:
    291         DCHECK(!node->op()->HasProperty(Operator::kNoThrow));
    292         index = 1;
    293         break;
    294       case IrOpcode::kIfValue:
    295         DCHECK_EQ(IrOpcode::kSwitch, node->opcode());
    296         index = if_value_index++;
    297         break;
    298       case IrOpcode::kIfDefault:
    299         DCHECK_EQ(IrOpcode::kSwitch, node->opcode());
    300         index = projection_count - 1;
    301         break;
    302       default:
    303         continue;
    304     }
    305     DCHECK_LT(if_value_index, projection_count);
    306     DCHECK_LT(index, projection_count);
    307     DCHECK_NULL(projections[index]);
    308     projections[index] = use;
    309   }
    310 #ifdef DEBUG
    311   for (size_t index = 0; index < projection_count; ++index) {
    312     DCHECK_NOT_NULL(projections[index]);
    313   }
    314 #endif
    315 }
    316 
    317 // static
    318 bool NodeProperties::IsSame(Node* a, Node* b) {
    319   for (;;) {
    320     if (a->opcode() == IrOpcode::kCheckHeapObject) {
    321       a = GetValueInput(a, 0);
    322       continue;
    323     }
    324     if (b->opcode() == IrOpcode::kCheckHeapObject) {
    325       b = GetValueInput(b, 0);
    326       continue;
    327     }
    328     return a == b;
    329   }
    330 }
    331 
    332 // static
    333 NodeProperties::InferReceiverMapsResult NodeProperties::InferReceiverMaps(
    334     Node* receiver, Node* effect, ZoneHandleSet<Map>* maps_return) {
    335   HeapObjectMatcher m(receiver);
    336   if (m.HasValue()) {
    337     Handle<Map> receiver_map(m.Value()->map());
    338     if (receiver_map->is_stable()) {
    339       // The {receiver_map} is only reliable when we install a stability
    340       // code dependency.
    341       *maps_return = ZoneHandleSet<Map>(receiver_map);
    342       return kUnreliableReceiverMaps;
    343     }
    344   }
    345   InferReceiverMapsResult result = kReliableReceiverMaps;
    346   while (true) {
    347     switch (effect->opcode()) {
    348       case IrOpcode::kCheckMaps: {
    349         Node* const object = GetValueInput(effect, 0);
    350         if (IsSame(receiver, object)) {
    351           *maps_return = CheckMapsParametersOf(effect->op()).maps();
    352           return result;
    353         }
    354         break;
    355       }
    356       case IrOpcode::kJSCreate: {
    357         if (IsSame(receiver, effect)) {
    358           HeapObjectMatcher mtarget(GetValueInput(effect, 0));
    359           HeapObjectMatcher mnewtarget(GetValueInput(effect, 1));
    360           if (mtarget.HasValue() && mnewtarget.HasValue()) {
    361             Handle<JSFunction> original_constructor =
    362                 Handle<JSFunction>::cast(mnewtarget.Value());
    363             if (original_constructor->has_initial_map()) {
    364               Handle<Map> initial_map(original_constructor->initial_map());
    365               if (initial_map->constructor_or_backpointer() ==
    366                   *mtarget.Value()) {
    367                 *maps_return = ZoneHandleSet<Map>(initial_map);
    368                 return result;
    369               }
    370             }
    371           }
    372           // We reached the allocation of the {receiver}.
    373           return kNoReceiverMaps;
    374         }
    375         break;
    376       }
    377       case IrOpcode::kStoreField: {
    378         // We only care about StoreField of maps.
    379         Node* const object = GetValueInput(effect, 0);
    380         FieldAccess const& access = FieldAccessOf(effect->op());
    381         if (access.base_is_tagged == kTaggedBase &&
    382             access.offset == HeapObject::kMapOffset) {
    383           if (IsSame(receiver, object)) {
    384             Node* const value = GetValueInput(effect, 1);
    385             HeapObjectMatcher m(value);
    386             if (m.HasValue()) {
    387               *maps_return = ZoneHandleSet<Map>(Handle<Map>::cast(m.Value()));
    388               return result;
    389             }
    390           }
    391           // Without alias analysis we cannot tell whether this
    392           // StoreField[map] affects {receiver} or not.
    393           result = kUnreliableReceiverMaps;
    394         }
    395         break;
    396       }
    397       case IrOpcode::kJSStoreMessage:
    398       case IrOpcode::kJSStoreModule:
    399       case IrOpcode::kStoreElement:
    400       case IrOpcode::kStoreTypedElement: {
    401         // These never change the map of objects.
    402         break;
    403       }
    404       default: {
    405         DCHECK_EQ(1, effect->op()->EffectOutputCount());
    406         if (effect->op()->EffectInputCount() != 1) {
    407           // Didn't find any appropriate CheckMaps node.
    408           return kNoReceiverMaps;
    409         }
    410         if (!effect->op()->HasProperty(Operator::kNoWrite)) {
    411           // Without alias/escape analysis we cannot tell whether this
    412           // {effect} affects {receiver} or not.
    413           result = kUnreliableReceiverMaps;
    414         }
    415         break;
    416       }
    417     }
    418     DCHECK_EQ(1, effect->op()->EffectInputCount());
    419     effect = NodeProperties::GetEffectInput(effect);
    420   }
    421 }
    422 
    423 // static
    424 MaybeHandle<Context> NodeProperties::GetSpecializationContext(
    425     Node* node, MaybeHandle<Context> context) {
    426   switch (node->opcode()) {
    427     case IrOpcode::kHeapConstant:
    428       return Handle<Context>::cast(OpParameter<Handle<HeapObject>>(node));
    429     case IrOpcode::kParameter: {
    430       Node* const start = NodeProperties::GetValueInput(node, 0);
    431       DCHECK_EQ(IrOpcode::kStart, start->opcode());
    432       int const index = ParameterIndexOf(node->op());
    433       // The context is always the last parameter to a JavaScript function, and
    434       // {Parameter} indices start at -1, so value outputs of {Start} look like
    435       // this: closure, receiver, param0, ..., paramN, context.
    436       if (index == start->op()->ValueOutputCount() - 2) {
    437         return context;
    438       }
    439       break;
    440     }
    441     default:
    442       break;
    443   }
    444   return MaybeHandle<Context>();
    445 }
    446 
    447 
    448 // static
    449 Node* NodeProperties::GetOuterContext(Node* node, size_t* depth) {
    450   Node* context = NodeProperties::GetContextInput(node);
    451   while (*depth > 0 &&
    452          IrOpcode::IsContextChainExtendingOpcode(context->opcode())) {
    453     context = NodeProperties::GetContextInput(context);
    454     (*depth)--;
    455   }
    456   return context;
    457 }
    458 
    459 // static
    460 Type* NodeProperties::GetTypeOrAny(Node* node) {
    461   return IsTyped(node) ? node->type() : Type::Any();
    462 }
    463 
    464 
    465 // static
    466 bool NodeProperties::AllValueInputsAreTyped(Node* node) {
    467   int input_count = node->op()->ValueInputCount();
    468   for (int index = 0; index < input_count; ++index) {
    469     if (!IsTyped(GetValueInput(node, index))) return false;
    470   }
    471   return true;
    472 }
    473 
    474 
    475 // static
    476 bool NodeProperties::IsInputRange(Edge edge, int first, int num) {
    477   if (num == 0) return false;
    478   int const index = edge.index();
    479   return first <= index && index < first + num;
    480 }
    481 
    482 }  // namespace compiler
    483 }  // namespace internal
    484 }  // namespace v8
    485