loop-variable-optimizer.cc 12.4 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11
// Copyright 2016 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/loop-variable-optimizer.h"

#include "src/compiler/common-operator.h"
#include "src/compiler/graph.h"
#include "src/compiler/node-marker.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/node.h"
12 13
#include "src/zone/zone-containers.h"
#include "src/zone/zone.h"
14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

namespace v8 {
namespace internal {
namespace compiler {

// Macro for outputting trace information from representation inference.
#define TRACE(...)                                  \
  do {                                              \
    if (FLAG_trace_turbo_loop) PrintF(__VA_ARGS__); \
  } while (false)

LoopVariableOptimizer::LoopVariableOptimizer(Graph* graph,
                                             CommonOperatorBuilder* common,
                                             Zone* zone)
    : graph_(graph),
      common_(common),
      zone_(zone),
31
      limits_(graph->NodeCount(), zone),
32
      reduced_(graph->NodeCount(), zone),
33 34 35 36 37 38 39 40 41 42 43
      induction_vars_(zone) {}

void LoopVariableOptimizer::Run() {
  ZoneQueue<Node*> queue(zone());
  queue.push(graph()->start());
  NodeMarker<bool> queued(graph(), 2);
  while (!queue.empty()) {
    Node* node = queue.front();
    queue.pop();
    queued.Set(node, false);

44
    DCHECK(!reduced_.Get(node));
45 46 47 48 49
    bool all_inputs_visited = true;
    int inputs_end = (node->opcode() == IrOpcode::kLoop)
                         ? kFirstBackedge
                         : node->op()->ControlInputCount();
    for (int i = 0; i < inputs_end; i++) {
50
      if (!reduced_.Get(NodeProperties::GetControlInput(node, i))) {
51 52 53 54 55 56 57
        all_inputs_visited = false;
        break;
      }
    }
    if (!all_inputs_visited) continue;

    VisitNode(node);
58
    reduced_.Set(node, true);
59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

    // Queue control outputs.
    for (Edge edge : node->use_edges()) {
      if (NodeProperties::IsControlEdge(edge) &&
          edge.from()->op()->ControlOutputCount() > 0) {
        Node* use = edge.from();
        if (use->opcode() == IrOpcode::kLoop &&
            edge.index() != kAssumedLoopEntryIndex) {
          VisitBackedge(node, use);
        } else if (!queued.Get(use)) {
          queue.push(use);
          queued.Set(use, true);
        }
      }
    }
  }
}

void InductionVariable::AddUpperBound(Node* bound,
78
                                      InductionVariable::ConstraintKind kind) {
79
  if (FLAG_trace_turbo_loop) {
80 81 82
    StdoutStream{} << "New upper bound for " << phi()->id() << " (loop "
                   << NodeProperties::GetControlInput(phi())->id()
                   << "): " << *bound << std::endl;
83 84 85 86 87
  }
  upper_bounds_.push_back(Bound(bound, kind));
}

void InductionVariable::AddLowerBound(Node* bound,
88
                                      InductionVariable::ConstraintKind kind) {
89
  if (FLAG_trace_turbo_loop) {
90 91 92
    StdoutStream{} << "New lower bound for " << phi()->id() << " (loop "
                   << NodeProperties::GetControlInput(phi())->id()
                   << "): " << *bound;
93 94 95 96 97 98 99 100 101
  }
  lower_bounds_.push_back(Bound(bound, kind));
}

void LoopVariableOptimizer::VisitBackedge(Node* from, Node* loop) {
  if (loop->op()->ControlInputCount() != 2) return;

  // Go through the constraints, and update the induction variables in
  // this loop if they are involved in the constraint.
102 103 104 105
  for (Constraint constraint : limits_.Get(from)) {
    if (constraint.left->opcode() == IrOpcode::kPhi &&
        NodeProperties::GetControlInput(constraint.left) == loop) {
      auto var = induction_vars_.find(constraint.left->id());
106
      if (var != induction_vars_.end()) {
107
        var->second->AddUpperBound(constraint.right, constraint.kind);
108 109
      }
    }
110 111 112
    if (constraint.right->opcode() == IrOpcode::kPhi &&
        NodeProperties::GetControlInput(constraint.right) == loop) {
      auto var = induction_vars_.find(constraint.right->id());
113
      if (var != induction_vars_.end()) {
114
        var->second->AddLowerBound(constraint.left, constraint.kind);
115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140
      }
    }
  }
}

void LoopVariableOptimizer::VisitNode(Node* node) {
  switch (node->opcode()) {
    case IrOpcode::kMerge:
      return VisitMerge(node);
    case IrOpcode::kLoop:
      return VisitLoop(node);
    case IrOpcode::kIfFalse:
      return VisitIf(node, false);
    case IrOpcode::kIfTrue:
      return VisitIf(node, true);
    case IrOpcode::kStart:
      return VisitStart(node);
    case IrOpcode::kLoopExit:
      return VisitLoopExit(node);
    default:
      return VisitOtherControl(node);
  }
}

void LoopVariableOptimizer::VisitMerge(Node* node) {
  // Merge the limits of all incoming edges.
141
  VariableLimits merged = limits_.Get(node->InputAt(0));
142
  for (int i = 1; i < node->InputCount(); i++) {
143
    merged.ResetToCommonAncestor(limits_.Get(node->InputAt(i)));
144
  }
145
  limits_.Set(node, merged);
146 147 148 149 150 151 152 153 154 155 156
}

void LoopVariableOptimizer::VisitLoop(Node* node) {
  DetectInductionVariables(node);
  // Conservatively take the limits from the loop entry here.
  return TakeConditionsFromFirstControl(node);
}

void LoopVariableOptimizer::VisitIf(Node* node, bool polarity) {
  Node* branch = node->InputAt(0);
  Node* cond = branch->InputAt(0);
157
  VariableLimits limits = limits_.Get(branch);
158 159 160
  // Normalize to less than comparison.
  switch (cond->opcode()) {
    case IrOpcode::kJSLessThan:
161
    case IrOpcode::kNumberLessThan:
162
    case IrOpcode::kSpeculativeNumberLessThan:
163
      AddCmpToLimits(&limits, cond, InductionVariable::kStrict, polarity);
164 165
      break;
    case IrOpcode::kJSGreaterThan:
166
      AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, !polarity);
167 168
      break;
    case IrOpcode::kJSLessThanOrEqual:
169
    case IrOpcode::kNumberLessThanOrEqual:
170
    case IrOpcode::kSpeculativeNumberLessThanOrEqual:
171
      AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, polarity);
172 173
      break;
    case IrOpcode::kJSGreaterThanOrEqual:
174
      AddCmpToLimits(&limits, cond, InductionVariable::kStrict, !polarity);
175 176 177 178
      break;
    default:
      break;
  }
179
  limits_.Set(node, limits);
180 181 182 183 184 185 186 187 188
}

void LoopVariableOptimizer::AddCmpToLimits(
    VariableLimits* limits, Node* node, InductionVariable::ConstraintKind kind,
    bool polarity) {
  Node* left = node->InputAt(0);
  Node* right = node->InputAt(1);
  if (FindInductionVariable(left) || FindInductionVariable(right)) {
    if (polarity) {
189
      limits->PushFront(Constraint{left, kind, right}, zone());
190 191 192 193
    } else {
      kind = (kind == InductionVariable::kStrict)
                 ? InductionVariable::kNonStrict
                 : InductionVariable::kStrict;
194
      limits->PushFront(Constraint{right, kind, left}, zone());
195 196 197 198
    }
  }
}

199
void LoopVariableOptimizer::VisitStart(Node* node) { limits_.Set(node, {}); }
200 201 202 203 204 205 206 207 208 209 210

void LoopVariableOptimizer::VisitLoopExit(Node* node) {
  return TakeConditionsFromFirstControl(node);
}

void LoopVariableOptimizer::VisitOtherControl(Node* node) {
  DCHECK_EQ(1, node->op()->ControlInputCount());
  return TakeConditionsFromFirstControl(node);
}

void LoopVariableOptimizer::TakeConditionsFromFirstControl(Node* node) {
211
  limits_.Set(node, limits_.Get(NodeProperties::GetControlInput(node, 0)));
212 213 214 215 216 217 218 219 220 221 222 223 224
}

const InductionVariable* LoopVariableOptimizer::FindInductionVariable(
    Node* node) {
  auto var = induction_vars_.find(node->id());
  if (var != induction_vars_.end()) {
    return var->second;
  }
  return nullptr;
}

InductionVariable* LoopVariableOptimizer::TryGetInductionVariable(Node* phi) {
  DCHECK_EQ(2, phi->op()->ValueInputCount());
225 226
  Node* loop = NodeProperties::GetControlInput(phi);
  DCHECK_EQ(IrOpcode::kLoop, loop->opcode());
227 228
  Node* initial = phi->InputAt(0);
  Node* arith = phi->InputAt(1);
229
  InductionVariable::ArithmeticType arithmeticType;
230
  if (arith->opcode() == IrOpcode::kJSAdd ||
231
      arith->opcode() == IrOpcode::kNumberAdd ||
232 233
      arith->opcode() == IrOpcode::kSpeculativeNumberAdd ||
      arith->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd) {
234
    arithmeticType = InductionVariable::ArithmeticType::kAddition;
235
  } else if (arith->opcode() == IrOpcode::kJSSubtract ||
236
             arith->opcode() == IrOpcode::kNumberSubtract ||
237 238
             arith->opcode() == IrOpcode::kSpeculativeNumberSubtract ||
             arith->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract) {
239 240
    arithmeticType = InductionVariable::ArithmeticType::kSubtraction;
  } else {
241 242
    return nullptr;
  }
243

244
  // TODO(jarin) Support both sides.
245 246
  Node* input = arith->InputAt(0);
  if (input->opcode() == IrOpcode::kSpeculativeToNumber ||
247 248
      input->opcode() == IrOpcode::kJSToNumber ||
      input->opcode() == IrOpcode::kJSToNumberConvertBigInt) {
249 250 251
    input = input->InputAt(0);
  }
  if (input != phi) return nullptr;
252

253 254 255 256 257 258 259 260 261
  Node* effect_phi = nullptr;
  for (Node* use : loop->uses()) {
    if (use->opcode() == IrOpcode::kEffectPhi) {
      DCHECK_NULL(effect_phi);
      effect_phi = use;
    }
  }
  if (!effect_phi) return nullptr;

262
  Node* incr = arith->InputAt(1);
263 264
  return new (zone()) InductionVariable(phi, effect_phi, arith, incr, initial,
                                        zone(), arithmeticType);
265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313
}

void LoopVariableOptimizer::DetectInductionVariables(Node* loop) {
  if (loop->op()->ControlInputCount() != 2) return;
  TRACE("Loop variables for loop %i:", loop->id());
  for (Edge edge : loop->use_edges()) {
    if (NodeProperties::IsControlEdge(edge) &&
        edge.from()->opcode() == IrOpcode::kPhi) {
      Node* phi = edge.from();
      InductionVariable* induction_var = TryGetInductionVariable(phi);
      if (induction_var) {
        induction_vars_[phi->id()] = induction_var;
        TRACE(" %i", induction_var->phi()->id());
      }
    }
  }
  TRACE("\n");
}

void LoopVariableOptimizer::ChangeToInductionVariablePhis() {
  for (auto entry : induction_vars_) {
    // It only make sense to analyze the induction variables if
    // there is a bound.
    InductionVariable* induction_var = entry.second;
    DCHECK_EQ(MachineRepresentation::kTagged,
              PhiRepresentationOf(induction_var->phi()->op()));
    if (induction_var->upper_bounds().size() == 0 &&
        induction_var->lower_bounds().size() == 0) {
      continue;
    }
    // Insert the increment value to the value inputs.
    induction_var->phi()->InsertInput(graph()->zone(),
                                      induction_var->phi()->InputCount() - 1,
                                      induction_var->increment());
    // Insert the bound inputs to the value inputs.
    for (auto bound : induction_var->lower_bounds()) {
      induction_var->phi()->InsertInput(
          graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
    }
    for (auto bound : induction_var->upper_bounds()) {
      induction_var->phi()->InsertInput(
          graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
    }
    NodeProperties::ChangeOp(
        induction_var->phi(),
        common()->InductionVariablePhi(induction_var->phi()->InputCount() - 1));
  }
}

314
void LoopVariableOptimizer::ChangeToPhisAndInsertGuards() {
315 316 317
  for (auto entry : induction_vars_) {
    InductionVariable* induction_var = entry.second;
    if (induction_var->phi()->opcode() == IrOpcode::kInductionVariablePhi) {
318
      // Turn the induction variable phi back to normal phi.
319 320 321 322 323 324 325 326
      int value_count = 2;
      Node* control = NodeProperties::GetControlInput(induction_var->phi());
      DCHECK_EQ(value_count, control->op()->ControlInputCount());
      induction_var->phi()->TrimInputCount(value_count + 1);
      induction_var->phi()->ReplaceInput(value_count, control);
      NodeProperties::ChangeOp(
          induction_var->phi(),
          common()->Phi(MachineRepresentation::kTagged, value_count));
327 328 329 330

      // If the backedge is not a subtype of the phi's type, we insert a sigma
      // to get the typing right.
      Node* backedge_value = induction_var->phi()->InputAt(1);
331 332
      Type backedge_type = NodeProperties::GetType(backedge_value);
      Type phi_type = NodeProperties::GetType(induction_var->phi());
333
      if (!backedge_type.Is(phi_type)) {
334 335 336 337 338 339 340 341
        Node* loop = NodeProperties::GetControlInput(induction_var->phi());
        Node* backedge_control = loop->InputAt(1);
        Node* backedge_effect =
            NodeProperties::GetEffectInput(induction_var->effect_phi(), 1);
        Node* rename =
            graph()->NewNode(common()->TypeGuard(phi_type), backedge_value,
                             backedge_effect, backedge_control);
        induction_var->effect_phi()->ReplaceInput(1, rename);
342 343
        induction_var->phi()->ReplaceInput(1, rename);
      }
344 345 346 347
    }
  }
}

348 349
#undef TRACE

350 351 352
}  // namespace compiler
}  // namespace internal
}  // namespace v8