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/escape-analysis-reducer.h"
      6 
      7 #include "src/compiler/all-nodes.h"
      8 #include "src/compiler/js-graph.h"
      9 #include "src/counters.h"
     10 
     11 namespace v8 {
     12 namespace internal {
     13 namespace compiler {
     14 
     15 #ifdef DEBUG
     16 #define TRACE(...)                                    \
     17   do {                                                \
     18     if (FLAG_trace_turbo_escape) PrintF(__VA_ARGS__); \
     19   } while (false)
     20 #else
     21 #define TRACE(...)
     22 #endif  // DEBUG
     23 
     24 EscapeAnalysisReducer::EscapeAnalysisReducer(Editor* editor, JSGraph* jsgraph,
     25                                              EscapeAnalysis* escape_analysis,
     26                                              Zone* zone)
     27     : AdvancedReducer(editor),
     28       jsgraph_(jsgraph),
     29       escape_analysis_(escape_analysis),
     30       zone_(zone),
     31       fully_reduced_(static_cast<int>(jsgraph->graph()->NodeCount() * 2), zone),
     32       exists_virtual_allocate_(escape_analysis->ExistsVirtualAllocate()) {}
     33 
     34 Reduction EscapeAnalysisReducer::ReduceNode(Node* node) {
     35   if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
     36       fully_reduced_.Contains(node->id())) {
     37     return NoChange();
     38   }
     39 
     40   switch (node->opcode()) {
     41     case IrOpcode::kLoadField:
     42     case IrOpcode::kLoadElement:
     43       return ReduceLoad(node);
     44     case IrOpcode::kStoreField:
     45     case IrOpcode::kStoreElement:
     46       return ReduceStore(node);
     47     case IrOpcode::kAllocate:
     48       return ReduceAllocate(node);
     49     case IrOpcode::kFinishRegion:
     50       return ReduceFinishRegion(node);
     51     case IrOpcode::kReferenceEqual:
     52       return ReduceReferenceEqual(node);
     53     case IrOpcode::kObjectIsSmi:
     54       return ReduceObjectIsSmi(node);
     55     // FrameStates and Value nodes are preprocessed here,
     56     // and visited via ReduceFrameStateUses from their user nodes.
     57     case IrOpcode::kFrameState:
     58     case IrOpcode::kStateValues: {
     59       if (node->id() >= static_cast<NodeId>(fully_reduced_.length()) ||
     60           fully_reduced_.Contains(node->id())) {
     61         break;
     62       }
     63       bool depends_on_object_state = false;
     64       for (Node* input : node->inputs()) {
     65         switch (input->opcode()) {
     66           case IrOpcode::kAllocate:
     67           case IrOpcode::kFinishRegion:
     68             depends_on_object_state =
     69                 depends_on_object_state || escape_analysis()->IsVirtual(input);
     70             break;
     71           case IrOpcode::kFrameState:
     72           case IrOpcode::kStateValues:
     73             depends_on_object_state =
     74                 depends_on_object_state ||
     75                 input->id() >= static_cast<NodeId>(fully_reduced_.length()) ||
     76                 !fully_reduced_.Contains(input->id());
     77             break;
     78           default:
     79             break;
     80         }
     81       }
     82       if (!depends_on_object_state) {
     83         fully_reduced_.Add(node->id());
     84       }
     85       return NoChange();
     86     }
     87     default:
     88       // TODO(sigurds): Change this to GetFrameStateInputCount once
     89       // it is working. For now we use EffectInputCount > 0 to determine
     90       // whether a node might have a frame state input.
     91       if (exists_virtual_allocate_ && node->op()->EffectInputCount() > 0) {
     92         return ReduceFrameStateUses(node);
     93       }
     94       break;
     95   }
     96   return NoChange();
     97 }
     98 
     99 Reduction EscapeAnalysisReducer::Reduce(Node* node) {
    100   Reduction reduction = ReduceNode(node);
    101   if (reduction.Changed() && node != reduction.replacement()) {
    102     escape_analysis()->SetReplacement(node, reduction.replacement());
    103   }
    104   return reduction;
    105 }
    106 
    107 namespace {
    108 
    109 Node* MaybeGuard(JSGraph* jsgraph, Zone* zone, Node* original,
    110                  Node* replacement) {
    111   // We might need to guard the replacement if the type of the {replacement}
    112   // node is not in a sub-type relation to the type of the the {original} node.
    113   Type* const replacement_type = NodeProperties::GetType(replacement);
    114   Type* const original_type = NodeProperties::GetType(original);
    115   if (!replacement_type->Is(original_type)) {
    116     Node* const control = NodeProperties::GetControlInput(original);
    117     replacement = jsgraph->graph()->NewNode(
    118         jsgraph->common()->TypeGuard(original_type), replacement, control);
    119     NodeProperties::SetType(replacement, original_type);
    120   }
    121   return replacement;
    122 }
    123 
    124 Node* SkipTypeGuards(Node* node) {
    125   while (node->opcode() == IrOpcode::kTypeGuard) {
    126     node = NodeProperties::GetValueInput(node, 0);
    127   }
    128   return node;
    129 }
    130 
    131 }  // namespace
    132 
    133 Reduction EscapeAnalysisReducer::ReduceLoad(Node* node) {
    134   DCHECK(node->opcode() == IrOpcode::kLoadField ||
    135          node->opcode() == IrOpcode::kLoadElement);
    136   if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
    137     fully_reduced_.Add(node->id());
    138   }
    139   if (escape_analysis()->IsVirtual(
    140           SkipTypeGuards(NodeProperties::GetValueInput(node, 0)))) {
    141     if (Node* rep = escape_analysis()->GetReplacement(node)) {
    142       TRACE("Replaced #%d (%s) with #%d (%s)\n", node->id(),
    143             node->op()->mnemonic(), rep->id(), rep->op()->mnemonic());
    144       rep = MaybeGuard(jsgraph(), zone(), node, rep);
    145       ReplaceWithValue(node, rep);
    146       return Replace(rep);
    147     }
    148   }
    149   return NoChange();
    150 }
    151 
    152 
    153 Reduction EscapeAnalysisReducer::ReduceStore(Node* node) {
    154   DCHECK(node->opcode() == IrOpcode::kStoreField ||
    155          node->opcode() == IrOpcode::kStoreElement);
    156   if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
    157     fully_reduced_.Add(node->id());
    158   }
    159   if (escape_analysis()->IsVirtual(
    160           SkipTypeGuards(NodeProperties::GetValueInput(node, 0)))) {
    161     TRACE("Removed #%d (%s) from effect chain\n", node->id(),
    162           node->op()->mnemonic());
    163     RelaxEffectsAndControls(node);
    164     return Changed(node);
    165   }
    166   return NoChange();
    167 }
    168 
    169 
    170 Reduction EscapeAnalysisReducer::ReduceAllocate(Node* node) {
    171   DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
    172   if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
    173     fully_reduced_.Add(node->id());
    174   }
    175   if (escape_analysis()->IsVirtual(node)) {
    176     RelaxEffectsAndControls(node);
    177     TRACE("Removed allocate #%d from effect chain\n", node->id());
    178     return Changed(node);
    179   }
    180   return NoChange();
    181 }
    182 
    183 
    184 Reduction EscapeAnalysisReducer::ReduceFinishRegion(Node* node) {
    185   DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
    186   Node* effect = NodeProperties::GetEffectInput(node, 0);
    187   if (effect->opcode() == IrOpcode::kBeginRegion) {
    188     // We only add it now to remove empty Begin/Finish region pairs
    189     // in the process.
    190     if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
    191       fully_reduced_.Add(node->id());
    192     }
    193     RelaxEffectsAndControls(effect);
    194     RelaxEffectsAndControls(node);
    195 #ifdef DEBUG
    196     if (FLAG_trace_turbo_escape) {
    197       PrintF("Removed region #%d / #%d from effect chain,", effect->id(),
    198              node->id());
    199       PrintF(" %d user(s) of #%d remain(s):", node->UseCount(), node->id());
    200       for (Edge edge : node->use_edges()) {
    201         PrintF(" #%d", edge.from()->id());
    202       }
    203       PrintF("\n");
    204     }
    205 #endif  // DEBUG
    206     return Changed(node);
    207   }
    208   return NoChange();
    209 }
    210 
    211 
    212 Reduction EscapeAnalysisReducer::ReduceReferenceEqual(Node* node) {
    213   DCHECK_EQ(node->opcode(), IrOpcode::kReferenceEqual);
    214   Node* left = SkipTypeGuards(NodeProperties::GetValueInput(node, 0));
    215   Node* right = SkipTypeGuards(NodeProperties::GetValueInput(node, 1));
    216   if (escape_analysis()->IsVirtual(left)) {
    217     if (escape_analysis()->IsVirtual(right) &&
    218         escape_analysis()->CompareVirtualObjects(left, right)) {
    219       ReplaceWithValue(node, jsgraph()->TrueConstant());
    220       TRACE("Replaced ref eq #%d with true\n", node->id());
    221       return Replace(jsgraph()->TrueConstant());
    222     }
    223     // Right-hand side is not a virtual object, or a different one.
    224     ReplaceWithValue(node, jsgraph()->FalseConstant());
    225     TRACE("Replaced ref eq #%d with false\n", node->id());
    226     return Replace(jsgraph()->FalseConstant());
    227   } else if (escape_analysis()->IsVirtual(right)) {
    228     // Left-hand side is not a virtual object.
    229     ReplaceWithValue(node, jsgraph()->FalseConstant());
    230     TRACE("Replaced ref eq #%d with false\n", node->id());
    231     return Replace(jsgraph()->FalseConstant());
    232   }
    233   return NoChange();
    234 }
    235 
    236 
    237 Reduction EscapeAnalysisReducer::ReduceObjectIsSmi(Node* node) {
    238   DCHECK_EQ(node->opcode(), IrOpcode::kObjectIsSmi);
    239   Node* input = SkipTypeGuards(NodeProperties::GetValueInput(node, 0));
    240   if (escape_analysis()->IsVirtual(input)) {
    241     ReplaceWithValue(node, jsgraph()->FalseConstant());
    242     TRACE("Replaced ObjectIsSmi #%d with false\n", node->id());
    243     return Replace(jsgraph()->FalseConstant());
    244   }
    245   return NoChange();
    246 }
    247 
    248 
    249 Reduction EscapeAnalysisReducer::ReduceFrameStateUses(Node* node) {
    250   DCHECK_GE(node->op()->EffectInputCount(), 1);
    251   if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
    252     fully_reduced_.Add(node->id());
    253   }
    254   bool changed = false;
    255   for (int i = 0; i < node->InputCount(); ++i) {
    256     Node* input = node->InputAt(i);
    257     if (input->opcode() == IrOpcode::kFrameState) {
    258       if (Node* ret = ReduceDeoptState(input, node, false)) {
    259         node->ReplaceInput(i, ret);
    260         changed = true;
    261       }
    262     }
    263   }
    264   if (changed) {
    265     return Changed(node);
    266   }
    267   return NoChange();
    268 }
    269 
    270 
    271 // Returns the clone if it duplicated the node, and null otherwise.
    272 Node* EscapeAnalysisReducer::ReduceDeoptState(Node* node, Node* effect,
    273                                               bool multiple_users) {
    274   DCHECK(node->opcode() == IrOpcode::kFrameState ||
    275          node->opcode() == IrOpcode::kStateValues);
    276   if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
    277       fully_reduced_.Contains(node->id())) {
    278     return nullptr;
    279   }
    280   TRACE("Reducing %s %d\n", node->op()->mnemonic(), node->id());
    281   Node* clone = nullptr;
    282   bool node_multiused = node->UseCount() > 1;
    283   bool multiple_users_rec = multiple_users || node_multiused;
    284   for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
    285     Node* input = NodeProperties::GetValueInput(node, i);
    286     if (input->opcode() == IrOpcode::kStateValues) {
    287       if (Node* ret = ReduceDeoptState(input, effect, multiple_users_rec)) {
    288         if (node_multiused || (multiple_users && !clone)) {
    289           TRACE("  Cloning #%d", node->id());
    290           node = clone = jsgraph()->graph()->CloneNode(node);
    291           TRACE(" to #%d\n", node->id());
    292           node_multiused = false;
    293         }
    294         NodeProperties::ReplaceValueInput(node, ret, i);
    295       }
    296     } else {
    297       if (Node* ret = ReduceStateValueInput(node, i, effect, node_multiused,
    298                                             clone, multiple_users)) {
    299         DCHECK_NULL(clone);
    300         node_multiused = false;  // Don't clone anymore.
    301         node = clone = ret;
    302       }
    303     }
    304   }
    305   if (node->opcode() == IrOpcode::kFrameState) {
    306     Node* outer_frame_state = NodeProperties::GetFrameStateInput(node);
    307     if (outer_frame_state->opcode() == IrOpcode::kFrameState) {
    308       if (Node* ret =
    309               ReduceDeoptState(outer_frame_state, effect, multiple_users_rec)) {
    310         if (node_multiused || (multiple_users && !clone)) {
    311           TRACE("    Cloning #%d", node->id());
    312           node = clone = jsgraph()->graph()->CloneNode(node);
    313           TRACE(" to #%d\n", node->id());
    314         }
    315         NodeProperties::ReplaceFrameStateInput(node, ret);
    316       }
    317     }
    318   }
    319   if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
    320     fully_reduced_.Add(node->id());
    321   }
    322   return clone;
    323 }
    324 
    325 
    326 // Returns the clone if it duplicated the node, and null otherwise.
    327 Node* EscapeAnalysisReducer::ReduceStateValueInput(Node* node, int node_index,
    328                                                    Node* effect,
    329                                                    bool node_multiused,
    330                                                    bool already_cloned,
    331                                                    bool multiple_users) {
    332   Node* input = SkipTypeGuards(NodeProperties::GetValueInput(node, node_index));
    333   if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
    334       fully_reduced_.Contains(node->id())) {
    335     return nullptr;
    336   }
    337   TRACE("Reducing State Input #%d (%s)\n", input->id(),
    338         input->op()->mnemonic());
    339   Node* clone = nullptr;
    340   if (input->opcode() == IrOpcode::kFinishRegion ||
    341       input->opcode() == IrOpcode::kAllocate) {
    342     if (escape_analysis()->IsVirtual(input)) {
    343       if (escape_analysis()->IsCyclicObjectState(effect, input)) {
    344         // TODO(mstarzinger): Represent cyclic object states differently to
    345         // ensure the scheduler can properly handle such object states.
    346         compilation_failed_ = true;
    347         return nullptr;
    348       }
    349       if (Node* object_state =
    350               escape_analysis()->GetOrCreateObjectState(effect, input)) {
    351         if (node_multiused || (multiple_users && !already_cloned)) {
    352           TRACE("Cloning #%d", node->id());
    353           node = clone = jsgraph()->graph()->CloneNode(node);
    354           TRACE(" to #%d\n", node->id());
    355           node_multiused = false;
    356           already_cloned = true;
    357         }
    358         NodeProperties::ReplaceValueInput(node, object_state, node_index);
    359         TRACE("Replaced state #%d input #%d with object state #%d\n",
    360               node->id(), input->id(), object_state->id());
    361       } else {
    362         TRACE("No object state replacement for #%d at effect #%d available.\n",
    363               input->id(), effect->id());
    364         UNREACHABLE();
    365       }
    366     }
    367   }
    368   return clone;
    369 }
    370 
    371 
    372 void EscapeAnalysisReducer::VerifyReplacement() const {
    373 #ifdef DEBUG
    374   AllNodes all(zone(), jsgraph()->graph());
    375   for (Node* node : all.reachable) {
    376     if (node->opcode() == IrOpcode::kAllocate) {
    377       CHECK(!escape_analysis_->IsVirtual(node));
    378     }
    379   }
    380 #endif  // DEBUG
    381 }
    382 
    383 }  // namespace compiler
    384 }  // namespace internal
    385 }  // namespace v8
    386