dead-code-elimination.cc 13.6 KB
Newer Older
1 2 3 4 5 6 7 8
// Copyright 2015 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/dead-code-elimination.h"

#include "src/compiler/common-operator.h"
#include "src/compiler/graph.h"
9
#include "src/compiler/js-operator.h"
10 11 12 13 14 15 16 17
#include "src/compiler/node-properties.h"
#include "src/compiler/operator-properties.h"

namespace v8 {
namespace internal {
namespace compiler {

DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph,
18
                                         CommonOperatorBuilder* common,
19
                                         Zone* temp_zone)
20 21 22
    : AdvancedReducer(editor),
      graph_(graph),
      common_(common),
23
      dead_(graph->NewNode(common->Dead())),
24
      zone_(temp_zone) {
25 26
  NodeProperties::SetType(dead_, Type::None());
}
27

28 29 30 31 32 33 34 35
namespace {

// True if we can guarantee that {node} will never actually produce a value or
// effect.
bool NoReturn(Node* node) {
  return node->opcode() == IrOpcode::kDead ||
         node->opcode() == IrOpcode::kUnreachable ||
         node->opcode() == IrOpcode::kDeadValue ||
36
         NodeProperties::GetTypeOrAny(node).IsNone();
37 38
}

39
Node* FindDeadInput(Node* node) {
40
  for (Node* input : node->inputs()) {
41
    if (NoReturn(input)) return input;
42
  }
43
  return nullptr;
44 45 46 47
}

}  // namespace

48 49 50 51 52 53 54
Reduction DeadCodeElimination::Reduce(Node* node) {
  switch (node->opcode()) {
    case IrOpcode::kEnd:
      return ReduceEnd(node);
    case IrOpcode::kLoop:
    case IrOpcode::kMerge:
      return ReduceLoopOrMerge(node);
55 56
    case IrOpcode::kLoopExit:
      return ReduceLoopExit(node);
57 58 59 60 61 62
    case IrOpcode::kUnreachable:
    case IrOpcode::kIfException:
      return ReduceUnreachableOrIfException(node);
    case IrOpcode::kPhi:
      return ReducePhi(node);
    case IrOpcode::kEffectPhi:
63
      return ReduceEffectPhi(node);
64 65 66
    case IrOpcode::kDeoptimize:
    case IrOpcode::kReturn:
    case IrOpcode::kTerminate:
67 68
    case IrOpcode::kTailCall:
      return ReduceDeoptimizeOrReturnOrTerminateOrTailCall(node);
69 70 71 72 73
    case IrOpcode::kThrow:
      return PropagateDeadControl(node);
    case IrOpcode::kBranch:
    case IrOpcode::kSwitch:
      return ReduceBranchOrSwitch(node);
74 75 76 77 78 79
    default:
      return ReduceNode(node);
  }
  UNREACHABLE();
}

80 81 82 83 84 85
Reduction DeadCodeElimination::PropagateDeadControl(Node* node) {
  DCHECK_EQ(1, node->op()->ControlInputCount());
  Node* control = NodeProperties::GetControlInput(node);
  if (control->opcode() == IrOpcode::kDead) return Replace(control);
  return NoChange();
}
86 87 88

Reduction DeadCodeElimination::ReduceEnd(Node* node) {
  DCHECK_EQ(IrOpcode::kEnd, node->opcode());
89 90
  Node::Inputs inputs = node->inputs();
  DCHECK_LE(1, inputs.count());
91
  int live_input_count = 0;
92 93
  for (int i = 0; i < inputs.count(); ++i) {
    Node* const input = inputs[i];
94 95 96 97 98 99 100 101
    // Skip dead inputs.
    if (input->opcode() == IrOpcode::kDead) continue;
    // Compact live inputs.
    if (i != live_input_count) node->ReplaceInput(live_input_count, input);
    ++live_input_count;
  }
  if (live_input_count == 0) {
    return Replace(dead());
102
  } else if (live_input_count < inputs.count()) {
103
    node->TrimInputCount(live_input_count);
104
    NodeProperties::ChangeOp(node, common()->End(live_input_count));
105 106
    return Changed(node);
  }
107
  DCHECK_EQ(inputs.count(), live_input_count);
108 109 110 111 112
  return NoChange();
}

Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
  DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
113 114
  Node::Inputs inputs = node->inputs();
  DCHECK_LE(1, inputs.count());
115 116 117 118 119 120 121
  // Count the number of live inputs to {node} and compact them on the fly, also
  // compacting the inputs of the associated {Phi} and {EffectPhi} uses at the
  // same time.  We consider {Loop}s dead even if only the first control input
  // is dead.
  int live_input_count = 0;
  if (node->opcode() != IrOpcode::kLoop ||
      node->InputAt(0)->opcode() != IrOpcode::kDead) {
122 123
    for (int i = 0; i < inputs.count(); ++i) {
      Node* const input = inputs[i];
124 125 126 127 128 129 130
      // Skip dead inputs.
      if (input->opcode() == IrOpcode::kDead) continue;
      // Compact live inputs.
      if (live_input_count != i) {
        node->ReplaceInput(live_input_count, input);
        for (Node* const use : node->uses()) {
          if (NodeProperties::IsPhi(use)) {
131
            DCHECK_EQ(inputs.count() + 1, use->InputCount());
132 133 134 135 136 137 138 139 140 141
            use->ReplaceInput(live_input_count, use->InputAt(i));
          }
        }
      }
      ++live_input_count;
    }
  }
  if (live_input_count == 0) {
    return Replace(dead());
  } else if (live_input_count == 1) {
142
    NodeVector loop_exits(zone_);
143 144 145 146
    // Due to compaction above, the live input is at offset 0.
    for (Node* const use : node->uses()) {
      if (NodeProperties::IsPhi(use)) {
        Replace(use, use->InputAt(0));
147 148
      } else if (use->opcode() == IrOpcode::kLoopExit &&
                 use->InputAt(1) == node) {
149 150 151 152
        // Remember the loop exits so that we can mark their loop input dead.
        // This has to be done after the use list iteration so that we do
        // not mutate the use list while it is being iterated.
        loop_exits.push_back(use);
153 154 155 156 157
      } else if (use->opcode() == IrOpcode::kTerminate) {
        DCHECK_EQ(IrOpcode::kLoop, node->opcode());
        Replace(use, dead());
      }
    }
158 159 160 161
    for (Node* loop_exit : loop_exits) {
      loop_exit->ReplaceInput(1, dead());
      Revisit(loop_exit);
    }
162 163 164
    return Replace(node->InputAt(0));
  }
  DCHECK_LE(2, live_input_count);
165
  DCHECK_LE(live_input_count, inputs.count());
166
  // Trim input count for the {Merge} or {Loop} node.
167
  if (live_input_count < inputs.count()) {
168 169 170 171 172 173 174 175 176 177 178 179 180 181
    // Trim input counts for all phi uses and revisit them.
    for (Node* const use : node->uses()) {
      if (NodeProperties::IsPhi(use)) {
        use->ReplaceInput(live_input_count, node);
        TrimMergeOrPhi(use, live_input_count);
        Revisit(use);
      }
    }
    TrimMergeOrPhi(node, live_input_count);
    return Changed(node);
  }
  return NoChange();
}

182 183 184 185 186 187 188 189 190 191 192 193
Reduction DeadCodeElimination::RemoveLoopExit(Node* node) {
  DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
  for (Node* const use : node->uses()) {
    if (use->opcode() == IrOpcode::kLoopExitValue ||
        use->opcode() == IrOpcode::kLoopExitEffect) {
      Replace(use, use->InputAt(0));
    }
  }
  Node* control = NodeProperties::GetControlInput(node, 0);
  Replace(node, control);
  return Replace(control);
}
194 195

Reduction DeadCodeElimination::ReduceNode(Node* node) {
196 197
  DCHECK(!IrOpcode::IsGraphTerminator(node->opcode()));
  int const effect_input_count = node->op()->EffectInputCount();
198
  int const control_input_count = node->op()->ControlInputCount();
199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217
  DCHECK_LE(control_input_count, 1);
  if (control_input_count == 1) {
    Reduction reduction = PropagateDeadControl(node);
    if (reduction.Changed()) return reduction;
  }
  if (effect_input_count == 0 &&
      (control_input_count == 0 || node->op()->ControlOutputCount() == 0)) {
    return ReducePureNode(node);
  }
  if (effect_input_count > 0) {
    return ReduceEffectNode(node);
  }
  return NoChange();
}

Reduction DeadCodeElimination::ReducePhi(Node* node) {
  DCHECK_EQ(IrOpcode::kPhi, node->opcode());
  Reduction reduction = PropagateDeadControl(node);
  if (reduction.Changed()) return reduction;
218 219
  MachineRepresentation rep = PhiRepresentationOf(node->op());
  if (rep == MachineRepresentation::kNone ||
220
      NodeProperties::GetTypeOrAny(node).IsNone()) {
221 222 223 224 225 226 227 228 229
    return Replace(DeadValue(node, rep));
  }
  int input_count = node->op()->ValueInputCount();
  for (int i = 0; i < input_count; ++i) {
    Node* input = NodeProperties::GetValueInput(node, i);
    if (input->opcode() == IrOpcode::kDeadValue &&
        DeadValueRepresentationOf(input->op()) != rep) {
      NodeProperties::ReplaceValueInput(node, DeadValue(input, rep), i);
    }
230 231 232 233
  }
  return NoChange();
}

234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261
Reduction DeadCodeElimination::ReduceEffectPhi(Node* node) {
  DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
  Reduction reduction = PropagateDeadControl(node);
  if (reduction.Changed()) return reduction;

  Node* merge = NodeProperties::GetControlInput(node);
  DCHECK(merge->opcode() == IrOpcode::kMerge ||
         merge->opcode() == IrOpcode::kLoop);
  int input_count = node->op()->EffectInputCount();
  for (int i = 0; i < input_count; ++i) {
    Node* effect = NodeProperties::GetEffectInput(node, i);
    if (effect->opcode() == IrOpcode::kUnreachable) {
      // If Unreachable hits an effect phi, we can re-connect the effect chain
      // to the graph end and delete the corresponding inputs from the merge and
      // phi nodes.
      Node* control = NodeProperties::GetControlInput(merge, i);
      Node* throw_node = graph_->NewNode(common_->Throw(), effect, control);
      NodeProperties::MergeControlToEnd(graph_, common_, throw_node);
      NodeProperties::ReplaceEffectInput(node, dead_, i);
      NodeProperties::ReplaceControlInput(merge, dead_, i);
      Revisit(merge);
      Revisit(graph_->end());
      reduction = Changed(node);
    }
  }
  return reduction;
}

262 263
Reduction DeadCodeElimination::ReducePureNode(Node* node) {
  DCHECK_EQ(0, node->op()->EffectInputCount());
264 265 266
  if (node->opcode() == IrOpcode::kDeadValue) return NoChange();
  if (Node* input = FindDeadInput(node)) {
    return Replace(DeadValue(input));
267 268 269 270 271 272 273 274 275 276 277 278 279 280
  }
  return NoChange();
}

Reduction DeadCodeElimination::ReduceUnreachableOrIfException(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kUnreachable ||
         node->opcode() == IrOpcode::kIfException);
  Reduction reduction = PropagateDeadControl(node);
  if (reduction.Changed()) return reduction;
  Node* effect = NodeProperties::GetEffectInput(node, 0);
  if (effect->opcode() == IrOpcode::kDead) {
    return Replace(effect);
  }
  if (effect->opcode() == IrOpcode::kUnreachable) {
281
    return Replace(effect);
282 283 284 285 286 287 288 289 290 291
  }
  return NoChange();
}

Reduction DeadCodeElimination::ReduceEffectNode(Node* node) {
  DCHECK_EQ(1, node->op()->EffectInputCount());
  Node* effect = NodeProperties::GetEffectInput(node, 0);
  if (effect->opcode() == IrOpcode::kDead) {
    return Replace(effect);
  }
292
  if (Node* input = FindDeadInput(node)) {
293 294
    if (effect->opcode() == IrOpcode::kUnreachable) {
      RelaxEffectsAndControls(node);
295
      return Replace(DeadValue(input));
296 297 298 299 300 301 302
    }

    Node* control = node->op()->ControlInputCount() == 1
                        ? NodeProperties::GetControlInput(node, 0)
                        : graph()->start();
    Node* unreachable =
        graph()->NewNode(common()->Unreachable(), effect, control);
303 304
    NodeProperties::SetType(unreachable, Type::None());
    ReplaceWithValue(node, DeadValue(input), node, control);
305 306 307 308 309 310
    return Replace(unreachable);
  }

  return NoChange();
}

311 312
Reduction DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(
    Node* node) {
313 314
  DCHECK(node->opcode() == IrOpcode::kDeoptimize ||
         node->opcode() == IrOpcode::kReturn ||
315 316
         node->opcode() == IrOpcode::kTerminate ||
         node->opcode() == IrOpcode::kTailCall);
317 318
  Reduction reduction = PropagateDeadControl(node);
  if (reduction.Changed()) return reduction;
319 320 321 322
  // Terminate nodes are not part of actual control flow, so they should never
  // be replaced with Throw.
  if (node->opcode() != IrOpcode::kTerminate &&
      FindDeadInput(node) != nullptr) {
323 324 325 326
    Node* effect = NodeProperties::GetEffectInput(node, 0);
    Node* control = NodeProperties::GetControlInput(node, 0);
    if (effect->opcode() != IrOpcode::kUnreachable) {
      effect = graph()->NewNode(common()->Unreachable(), effect, control);
327
      NodeProperties::SetType(effect, Type::None());
328 329 330 331 332 333 334
    }
    node->TrimInputCount(2);
    node->ReplaceInput(0, effect);
    node->ReplaceInput(1, control);
    NodeProperties::ChangeOp(node, common()->Throw());
    return Changed(node);
  }
335 336 337
  return NoChange();
}

338 339 340 341 342 343 344 345 346
Reduction DeadCodeElimination::ReduceLoopExit(Node* node) {
  Node* control = NodeProperties::GetControlInput(node, 0);
  Node* loop = NodeProperties::GetControlInput(node, 1);
  if (control->opcode() == IrOpcode::kDead ||
      loop->opcode() == IrOpcode::kDead) {
    return RemoveLoopExit(node);
  }
  return NoChange();
}
347

348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368
Reduction DeadCodeElimination::ReduceBranchOrSwitch(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kBranch ||
         node->opcode() == IrOpcode::kSwitch);
  Reduction reduction = PropagateDeadControl(node);
  if (reduction.Changed()) return reduction;
  Node* condition = NodeProperties::GetValueInput(node, 0);
  if (condition->opcode() == IrOpcode::kDeadValue) {
    // Branches or switches on {DeadValue} must originate from unreachable code
    // and cannot matter. Due to schedule freedom between the effect and the
    // control chain, they might still appear in reachable code. Remove them by
    // always choosing the first projection.
    size_t const projection_cnt = node->op()->ControlOutputCount();
    Node** projections = zone_->NewArray<Node*>(projection_cnt);
    NodeProperties::CollectControlProjections(node, projections,
                                              projection_cnt);
    Replace(projections[0], NodeProperties::GetControlInput(node));
    return Replace(dead());
  }
  return NoChange();
}

369 370 371
void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) {
  const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size);
  node->TrimInputCount(OperatorProperties::GetTotalInputCount(op));
372
  NodeProperties::ChangeOp(node, op);
373 374
}

375 376 377 378 379 380 381 382 383 384
Node* DeadCodeElimination::DeadValue(Node* node, MachineRepresentation rep) {
  if (node->opcode() == IrOpcode::kDeadValue) {
    if (rep == DeadValueRepresentationOf(node->op())) return node;
    node = NodeProperties::GetValueInput(node, 0);
  }
  Node* dead_value = graph()->NewNode(common()->DeadValue(rep), node);
  NodeProperties::SetType(dead_value, Type::None());
  return dead_value;
}

385 386 387
}  // namespace compiler
}  // namespace internal
}  // namespace v8