Home | History | Annotate | Download | only in compiler 
      1 // Copyright 2013 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/graph-builder.h"
      6 
      7 #include "src/compiler.h"
      8 #include "src/compiler/generic-graph.h"
      9 #include "src/compiler/generic-node.h"
     10 #include "src/compiler/generic-node-inl.h"
     11 #include "src/compiler/graph-visualizer.h"
     12 #include "src/compiler/node-properties.h"
     13 #include "src/compiler/node-properties-inl.h"
     14 #include "src/compiler/operator-properties.h"
     15 #include "src/compiler/operator-properties-inl.h"
     16 
     17 namespace v8 {
     18 namespace internal {
     19 namespace compiler {
     20 
     21 
     22 StructuredGraphBuilder::StructuredGraphBuilder(Graph* graph,
     23                                                CommonOperatorBuilder* common)
     24     : GraphBuilder(graph),
     25       common_(common),
     26       environment_(NULL),
     27       current_context_(NULL),
     28       exit_control_(NULL) {}
     29 
     30 
     31 Node* StructuredGraphBuilder::MakeNode(const Operator* op,
     32                                        int value_input_count,
     33                                        Node** value_inputs) {
     34   DCHECK(op->InputCount() == value_input_count);
     35 
     36   bool has_context = OperatorProperties::HasContextInput(op);
     37   bool has_framestate = OperatorProperties::HasFrameStateInput(op);
     38   bool has_control = OperatorProperties::GetControlInputCount(op) == 1;
     39   bool has_effect = OperatorProperties::GetEffectInputCount(op) == 1;
     40 
     41   DCHECK(OperatorProperties::GetControlInputCount(op) < 2);
     42   DCHECK(OperatorProperties::GetEffectInputCount(op) < 2);
     43 
     44   Node* result = NULL;
     45   if (!has_context && !has_framestate && !has_control && !has_effect) {
     46     result = graph()->NewNode(op, value_input_count, value_inputs);
     47   } else {
     48     int input_count_with_deps = value_input_count;
     49     if (has_context) ++input_count_with_deps;
     50     if (has_framestate) ++input_count_with_deps;
     51     if (has_control) ++input_count_with_deps;
     52     if (has_effect) ++input_count_with_deps;
     53     Node** buffer = zone()->NewArray<Node*>(input_count_with_deps);
     54     memcpy(buffer, value_inputs, kPointerSize * value_input_count);
     55     Node** current_input = buffer + value_input_count;
     56     if (has_context) {
     57       *current_input++ = current_context();
     58     }
     59     if (has_framestate) {
     60       // The frame state will be inserted later. Here we misuse
     61       // the dead_control node as a sentinel to be later overwritten
     62       // with the real frame state.
     63       *current_input++ = dead_control();
     64     }
     65     if (has_effect) {
     66       *current_input++ = environment_->GetEffectDependency();
     67     }
     68     if (has_control) {
     69       *current_input++ = environment_->GetControlDependency();
     70     }
     71     result = graph()->NewNode(op, input_count_with_deps, buffer);
     72     if (has_effect) {
     73       environment_->UpdateEffectDependency(result);
     74     }
     75     if (OperatorProperties::HasControlOutput(result->op()) &&
     76         !environment()->IsMarkedAsUnreachable()) {
     77       environment_->UpdateControlDependency(result);
     78     }
     79   }
     80 
     81   return result;
     82 }
     83 
     84 
     85 void StructuredGraphBuilder::UpdateControlDependencyToLeaveFunction(
     86     Node* exit) {
     87   if (environment()->IsMarkedAsUnreachable()) return;
     88   if (exit_control() != NULL) {
     89     exit = MergeControl(exit_control(), exit);
     90   }
     91   environment()->MarkAsUnreachable();
     92   set_exit_control(exit);
     93 }
     94 
     95 
     96 StructuredGraphBuilder::Environment* StructuredGraphBuilder::CopyEnvironment(
     97     Environment* env) {
     98   return new (zone()) Environment(*env);
     99 }
    100 
    101 
    102 StructuredGraphBuilder::Environment::Environment(
    103     StructuredGraphBuilder* builder, Node* control_dependency)
    104     : builder_(builder),
    105       control_dependency_(control_dependency),
    106       effect_dependency_(control_dependency),
    107       values_(zone()) {}
    108 
    109 
    110 StructuredGraphBuilder::Environment::Environment(const Environment& copy)
    111     : builder_(copy.builder()),
    112       control_dependency_(copy.control_dependency_),
    113       effect_dependency_(copy.effect_dependency_),
    114       values_(copy.values_) {}
    115 
    116 
    117 void StructuredGraphBuilder::Environment::Merge(Environment* other) {
    118   DCHECK(values_.size() == other->values_.size());
    119 
    120   // Nothing to do if the other environment is dead.
    121   if (other->IsMarkedAsUnreachable()) return;
    122 
    123   // Resurrect a dead environment by copying the contents of the other one and
    124   // placing a singleton merge as the new control dependency.
    125   if (this->IsMarkedAsUnreachable()) {
    126     Node* other_control = other->control_dependency_;
    127     control_dependency_ = graph()->NewNode(common()->Merge(1), other_control);
    128     effect_dependency_ = other->effect_dependency_;
    129     values_ = other->values_;
    130     return;
    131   }
    132 
    133   // Create a merge of the control dependencies of both environments and update
    134   // the current environment's control dependency accordingly.
    135   Node* control = builder_->MergeControl(this->GetControlDependency(),
    136                                          other->GetControlDependency());
    137   UpdateControlDependency(control);
    138 
    139   // Create a merge of the effect dependencies of both environments and update
    140   // the current environment's effect dependency accordingly.
    141   Node* effect = builder_->MergeEffect(this->GetEffectDependency(),
    142                                        other->GetEffectDependency(), control);
    143   UpdateEffectDependency(effect);
    144 
    145   // Introduce Phi nodes for values that have differing input at merge points,
    146   // potentially extending an existing Phi node if possible.
    147   for (int i = 0; i < static_cast<int>(values_.size()); ++i) {
    148     values_[i] = builder_->MergeValue(values_[i], other->values_[i], control);
    149   }
    150 }
    151 
    152 
    153 void StructuredGraphBuilder::Environment::PrepareForLoop() {
    154   Node* control = GetControlDependency();
    155   for (int i = 0; i < static_cast<int>(values()->size()); ++i) {
    156     Node* phi = builder_->NewPhi(1, values()->at(i), control);
    157     values()->at(i) = phi;
    158   }
    159   Node* effect = builder_->NewEffectPhi(1, GetEffectDependency(), control);
    160   UpdateEffectDependency(effect);
    161 }
    162 
    163 
    164 Node* StructuredGraphBuilder::NewPhi(int count, Node* input, Node* control) {
    165   const Operator* phi_op = common()->Phi(kMachAnyTagged, count);
    166   Node** buffer = zone()->NewArray<Node*>(count + 1);
    167   MemsetPointer(buffer, input, count);
    168   buffer[count] = control;
    169   return graph()->NewNode(phi_op, count + 1, buffer);
    170 }
    171 
    172 
    173 // TODO(mstarzinger): Revisit this once we have proper effect states.
    174 Node* StructuredGraphBuilder::NewEffectPhi(int count, Node* input,
    175                                            Node* control) {
    176   const Operator* phi_op = common()->EffectPhi(count);
    177   Node** buffer = zone()->NewArray<Node*>(count + 1);
    178   MemsetPointer(buffer, input, count);
    179   buffer[count] = control;
    180   return graph()->NewNode(phi_op, count + 1, buffer);
    181 }
    182 
    183 
    184 Node* StructuredGraphBuilder::MergeControl(Node* control, Node* other) {
    185   int inputs = OperatorProperties::GetControlInputCount(control->op()) + 1;
    186   if (control->opcode() == IrOpcode::kLoop) {
    187     // Control node for loop exists, add input.
    188     const Operator* op = common()->Loop(inputs);
    189     control->AppendInput(zone(), other);
    190     control->set_op(op);
    191   } else if (control->opcode() == IrOpcode::kMerge) {
    192     // Control node for merge exists, add input.
    193     const Operator* op = common()->Merge(inputs);
    194     control->AppendInput(zone(), other);
    195     control->set_op(op);
    196   } else {
    197     // Control node is a singleton, introduce a merge.
    198     const Operator* op = common()->Merge(inputs);
    199     control = graph()->NewNode(op, control, other);
    200   }
    201   return control;
    202 }
    203 
    204 
    205 Node* StructuredGraphBuilder::MergeEffect(Node* value, Node* other,
    206                                           Node* control) {
    207   int inputs = OperatorProperties::GetControlInputCount(control->op());
    208   if (value->opcode() == IrOpcode::kEffectPhi &&
    209       NodeProperties::GetControlInput(value) == control) {
    210     // Phi already exists, add input.
    211     value->set_op(common()->EffectPhi(inputs));
    212     value->InsertInput(zone(), inputs - 1, other);
    213   } else if (value != other) {
    214     // Phi does not exist yet, introduce one.
    215     value = NewEffectPhi(inputs, value, control);
    216     value->ReplaceInput(inputs - 1, other);
    217   }
    218   return value;
    219 }
    220 
    221 
    222 Node* StructuredGraphBuilder::MergeValue(Node* value, Node* other,
    223                                          Node* control) {
    224   int inputs = OperatorProperties::GetControlInputCount(control->op());
    225   if (value->opcode() == IrOpcode::kPhi &&
    226       NodeProperties::GetControlInput(value) == control) {
    227     // Phi already exists, add input.
    228     value->set_op(common()->Phi(kMachAnyTagged, inputs));
    229     value->InsertInput(zone(), inputs - 1, other);
    230   } else if (value != other) {
    231     // Phi does not exist yet, introduce one.
    232     value = NewPhi(inputs, value, control);
    233     value->ReplaceInput(inputs - 1, other);
    234   }
    235   return value;
    236 }
    237 
    238 
    239 Node* StructuredGraphBuilder::dead_control() {
    240   if (!dead_control_.is_set()) {
    241     Node* dead_node = graph()->NewNode(common_->Dead());
    242     dead_control_.set(dead_node);
    243     return dead_node;
    244   }
    245   return dead_control_.get();
    246 }
    247 }
    248 }
    249 }  // namespace v8::internal::compiler
    250