graph-builder.cc 9.55 KB
Newer Older
1 2 3 4 5 6 7 8
// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/graph-builder.h"

#include "src/compiler.h"
#include "src/compiler/generic-graph.h"
9 10
#include "src/compiler/generic-node.h"
#include "src/compiler/generic-node-inl.h"
11 12 13 14 15 16 17 18 19 20 21
#include "src/compiler/graph-visualizer.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/node-properties-inl.h"
#include "src/compiler/operator-properties.h"
#include "src/compiler/operator-properties-inl.h"

namespace v8 {
namespace internal {
namespace compiler {


22
StructuredGraphBuilder::StructuredGraphBuilder(Zone* local_zone, Graph* graph,
23 24 25 26
                                               CommonOperatorBuilder* common)
    : GraphBuilder(graph),
      common_(common),
      environment_(NULL),
27
      local_zone_(local_zone),
28 29
      input_buffer_size_(0),
      input_buffer_(NULL),
30
      current_context_(NULL),
31 32 33 34 35 36 37 38 39 40 41 42
      exit_control_(NULL) {
  EnsureInputBufferSize(kInputBufferSizeIncrement);
}


Node** StructuredGraphBuilder::EnsureInputBufferSize(int size) {
  if (size > input_buffer_size_) {
    size += kInputBufferSizeIncrement;
    input_buffer_ = local_zone()->NewArray<Node*>(size);
  }
  return input_buffer_;
}
43 44


45 46
Node* StructuredGraphBuilder::MakeNode(const Operator* op,
                                       int value_input_count,
47
                                       Node** value_inputs, bool incomplete) {
48 49
  DCHECK(op->InputCount() == value_input_count);

50
  bool has_context = OperatorProperties::HasContextInput(op);
51
  bool has_framestate = OperatorProperties::HasFrameStateInput(op);
52 53
  bool has_control = op->ControlInputCount() == 1;
  bool has_effect = op->EffectInputCount() == 1;
54

55 56
  DCHECK(op->ControlInputCount() < 2);
  DCHECK(op->EffectInputCount() < 2);
57 58

  Node* result = NULL;
59
  if (!has_context && !has_framestate && !has_control && !has_effect) {
60
    result = graph()->NewNode(op, value_input_count, value_inputs, incomplete);
61 62 63
  } else {
    int input_count_with_deps = value_input_count;
    if (has_context) ++input_count_with_deps;
64
    if (has_framestate) ++input_count_with_deps;
65 66
    if (has_control) ++input_count_with_deps;
    if (has_effect) ++input_count_with_deps;
67
    Node** buffer = EnsureInputBufferSize(input_count_with_deps);
68 69 70 71 72
    memcpy(buffer, value_inputs, kPointerSize * value_input_count);
    Node** current_input = buffer + value_input_count;
    if (has_context) {
      *current_input++ = current_context();
    }
73 74 75 76 77 78
    if (has_framestate) {
      // The frame state will be inserted later. Here we misuse
      // the dead_control node as a sentinel to be later overwritten
      // with the real frame state.
      *current_input++ = dead_control();
    }
79 80 81 82
    if (has_effect) {
      *current_input++ = environment_->GetEffectDependency();
    }
    if (has_control) {
83
      *current_input++ = environment_->GetControlDependency();
84
    }
85
    result = graph()->NewNode(op, input_count_with_deps, buffer, incomplete);
86 87 88
    if (has_effect) {
      environment_->UpdateEffectDependency(result);
    }
89
    if (result->op()->ControlOutputCount() > 0 &&
90 91
        !environment()->IsMarkedAsUnreachable()) {
      environment_->UpdateControlDependency(result);
92 93 94 95 96 97 98 99 100
    }
  }

  return result;
}


void StructuredGraphBuilder::UpdateControlDependencyToLeaveFunction(
    Node* exit) {
101
  if (environment()->IsMarkedAsUnreachable()) return;
102 103 104
  if (exit_control() != NULL) {
    exit = MergeControl(exit_control(), exit);
  }
105
  environment()->MarkAsUnreachable();
106 107 108 109 110 111
  set_exit_control(exit);
}


StructuredGraphBuilder::Environment* StructuredGraphBuilder::CopyEnvironment(
    Environment* env) {
112
  return new (local_zone()) Environment(*env);
113 114 115 116 117 118 119 120
}


StructuredGraphBuilder::Environment::Environment(
    StructuredGraphBuilder* builder, Node* control_dependency)
    : builder_(builder),
      control_dependency_(control_dependency),
      effect_dependency_(control_dependency),
121
      values_(zone()) {}
122 123 124 125 126 127 128 129 130 131


StructuredGraphBuilder::Environment::Environment(const Environment& copy)
    : builder_(copy.builder()),
      control_dependency_(copy.control_dependency_),
      effect_dependency_(copy.effect_dependency_),
      values_(copy.values_) {}


void StructuredGraphBuilder::Environment::Merge(Environment* other) {
132
  DCHECK(values_.size() == other->values_.size());
133 134 135 136 137 138 139 140

  // Nothing to do if the other environment is dead.
  if (other->IsMarkedAsUnreachable()) return;

  // Resurrect a dead environment by copying the contents of the other one and
  // placing a singleton merge as the new control dependency.
  if (this->IsMarkedAsUnreachable()) {
    Node* other_control = other->control_dependency_;
141 142 143
    Node* inputs[] = {other_control};
    control_dependency_ =
        graph()->NewNode(common()->Merge(1), arraysize(inputs), inputs, true);
144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
    effect_dependency_ = other->effect_dependency_;
    values_ = other->values_;
    return;
  }

  // Create a merge of the control dependencies of both environments and update
  // the current environment's control dependency accordingly.
  Node* control = builder_->MergeControl(this->GetControlDependency(),
                                         other->GetControlDependency());
  UpdateControlDependency(control);

  // Create a merge of the effect dependencies of both environments and update
  // the current environment's effect dependency accordingly.
  Node* effect = builder_->MergeEffect(this->GetEffectDependency(),
                                       other->GetEffectDependency(), control);
  UpdateEffectDependency(effect);

  // Introduce Phi nodes for values that have differing input at merge points,
  // potentially extending an existing Phi node if possible.
  for (int i = 0; i < static_cast<int>(values_.size()); ++i) {
    values_[i] = builder_->MergeValue(values_[i], other->values_[i], control);
  }
}


169
void StructuredGraphBuilder::Environment::PrepareForLoop(BitVector* assigned) {
170
  Node* control = GetControlDependency();
171 172 173 174 175 176 177 178 179 180 181 182 183 184
  int size = static_cast<int>(values()->size());
  if (assigned == NULL) {
    // Assume that everything is updated in the loop.
    for (int i = 0; i < size; ++i) {
      Node* phi = builder_->NewPhi(1, values()->at(i), control);
      values()->at(i) = phi;
    }
  } else {
    // Only build phis for those locals assigned in this loop.
    for (int i = 0; i < size; ++i) {
      if (i < assigned->length() && !assigned->Contains(i)) continue;
      Node* phi = builder_->NewPhi(1, values()->at(i), control);
      values()->at(i) = phi;
    }
185 186 187 188 189 190 191
  }
  Node* effect = builder_->NewEffectPhi(1, GetEffectDependency(), control);
  UpdateEffectDependency(effect);
}


Node* StructuredGraphBuilder::NewPhi(int count, Node* input, Node* control) {
192
  const Operator* phi_op = common()->Phi(kMachAnyTagged, count);
193
  Node** buffer = EnsureInputBufferSize(count + 1);
194 195
  MemsetPointer(buffer, input, count);
  buffer[count] = control;
196
  return graph()->NewNode(phi_op, count + 1, buffer, true);
197 198 199 200 201 202
}


// TODO(mstarzinger): Revisit this once we have proper effect states.
Node* StructuredGraphBuilder::NewEffectPhi(int count, Node* input,
                                           Node* control) {
203
  const Operator* phi_op = common()->EffectPhi(count);
204
  Node** buffer = EnsureInputBufferSize(count + 1);
205 206
  MemsetPointer(buffer, input, count);
  buffer[count] = control;
207
  return graph()->NewNode(phi_op, count + 1, buffer, true);
208 209 210 211
}


Node* StructuredGraphBuilder::MergeControl(Node* control, Node* other) {
212
  int inputs = control->op()->ControlInputCount() + 1;
213 214
  if (control->opcode() == IrOpcode::kLoop) {
    // Control node for loop exists, add input.
215
    const Operator* op = common()->Loop(inputs);
216
    control->AppendInput(graph_zone(), other);
217 218 219
    control->set_op(op);
  } else if (control->opcode() == IrOpcode::kMerge) {
    // Control node for merge exists, add input.
220
    const Operator* op = common()->Merge(inputs);
221
    control->AppendInput(graph_zone(), other);
222 223 224
    control->set_op(op);
  } else {
    // Control node is a singleton, introduce a merge.
225
    const Operator* op = common()->Merge(inputs);
226 227
    Node* inputs[] = {control, other};
    control = graph()->NewNode(op, arraysize(inputs), inputs, true);
228 229 230 231 232 233 234
  }
  return control;
}


Node* StructuredGraphBuilder::MergeEffect(Node* value, Node* other,
                                          Node* control) {
235
  int inputs = control->op()->ControlInputCount();
236 237 238 239
  if (value->opcode() == IrOpcode::kEffectPhi &&
      NodeProperties::GetControlInput(value) == control) {
    // Phi already exists, add input.
    value->set_op(common()->EffectPhi(inputs));
240
    value->InsertInput(graph_zone(), inputs - 1, other);
241 242 243 244 245 246 247 248 249 250 251
  } else if (value != other) {
    // Phi does not exist yet, introduce one.
    value = NewEffectPhi(inputs, value, control);
    value->ReplaceInput(inputs - 1, other);
  }
  return value;
}


Node* StructuredGraphBuilder::MergeValue(Node* value, Node* other,
                                         Node* control) {
252
  int inputs = control->op()->ControlInputCount();
253 254 255
  if (value->opcode() == IrOpcode::kPhi &&
      NodeProperties::GetControlInput(value) == control) {
    // Phi already exists, add input.
256
    value->set_op(common()->Phi(kMachAnyTagged, inputs));
257
    value->InsertInput(graph_zone(), inputs - 1, other);
258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277
  } else if (value != other) {
    // Phi does not exist yet, introduce one.
    value = NewPhi(inputs, value, control);
    value->ReplaceInput(inputs - 1, other);
  }
  return value;
}


Node* StructuredGraphBuilder::dead_control() {
  if (!dead_control_.is_set()) {
    Node* dead_node = graph()->NewNode(common_->Dead());
    dead_control_.set(dead_node);
    return dead_node;
  }
  return dead_control_.get();
}
}
}
}  // namespace v8::internal::compiler