1// Copyright 2022 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/branch-condition-duplicator.h"
6
7#include "src/compiler/backend/instruction-codes.h"
8#include "src/compiler/graph.h"
9#include "src/compiler/node-properties.h"
10#include "src/compiler/opcodes.h"
11
12namespace v8 {
13namespace internal {
14namespace compiler {
15
16namespace {
17
18bool IsBranch(Node* node) { return node->opcode() == IrOpcode::kBranch; }
19
20bool CanDuplicate(Node* node) {
21  // We only allow duplication of comparisons and "cheap" binary operations
22  // (cheap = not multiplication or division). The idea is that those
23  // instructions set the ZF flag, and thus do not require a "== 0" to be added
24  // before the branch. Duplicating other nodes, on the other hand, makes little
25  // sense, because a "== 0" would need to be inserted in branches anyways.
26  switch (node->opcode()) {
27#define BRANCH_CASE(op) \
28  case IrOpcode::k##op: \
29    break;
30    MACHINE_COMPARE_BINOP_LIST(BRANCH_CASE)
31    case IrOpcode::kInt32Add:
32    case IrOpcode::kInt32Sub:
33    case IrOpcode::kWord32And:
34    case IrOpcode::kWord32Or:
35    case IrOpcode::kInt64Add:
36    case IrOpcode::kInt64Sub:
37    case IrOpcode::kWord64And:
38    case IrOpcode::kWord64Or:
39    case IrOpcode::kWord32Shl:
40    case IrOpcode::kWord32Shr:
41    case IrOpcode::kWord64Shl:
42    case IrOpcode::kWord64Shr:
43      break;
44    default:
45      return false;
46  }
47
48  // We do not duplicate nodes if all their inputs are used a single time,
49  // because this would keep those inputs alive, thus increasing register
50  // pressure.
51  int all_inputs_have_only_a_single_use = true;
52  for (Node* input : node->inputs()) {
53    if (input->UseCount() > 1) {
54      all_inputs_have_only_a_single_use = false;
55    }
56  }
57  if (all_inputs_have_only_a_single_use) {
58    return false;
59  }
60
61  return true;
62}
63
64}  // namespace
65
66Node* BranchConditionDuplicator::DuplicateNode(Node* node) {
67  return graph_->CloneNode(node);
68}
69
70void BranchConditionDuplicator::DuplicateConditionIfNeeded(Node* node) {
71  if (!IsBranch(node)) return;
72
73  Node* condNode = node->InputAt(0);
74  if (condNode->UseCount() > 1 && CanDuplicate(condNode)) {
75    node->ReplaceInput(0, DuplicateNode(condNode));
76  }
77}
78
79void BranchConditionDuplicator::Enqueue(Node* node) {
80  if (seen_.Get(node)) return;
81  seen_.Set(node, true);
82  to_visit_.push(node);
83}
84
85void BranchConditionDuplicator::VisitNode(Node* node) {
86  DuplicateConditionIfNeeded(node);
87
88  for (int i = 0; i < node->op()->ControlInputCount(); i++) {
89    Enqueue(NodeProperties::GetControlInput(node, i));
90  }
91}
92
93void BranchConditionDuplicator::ProcessGraph() {
94  Enqueue(graph_->end());
95  while (!to_visit_.empty()) {
96    Node* node = to_visit_.front();
97    to_visit_.pop();
98    VisitNode(node);
99  }
100}
101
102BranchConditionDuplicator::BranchConditionDuplicator(Zone* zone, Graph* graph)
103    : graph_(graph), to_visit_(zone), seen_(graph, 2) {}
104
105void BranchConditionDuplicator::Reduce() { ProcessGraph(); }
106
107}  // namespace compiler
108}  // namespace internal
109}  // namespace v8
110