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
12 namespace v8 {
13 namespace internal {
14 namespace compiler {
15
16 namespace {
17
IsBranch(Node * node)18 bool IsBranch(Node* node) { return node->opcode() == IrOpcode::kBranch; }
19
CanDuplicate(Node * node)20 bool 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
DuplicateNode(Node * node)66 Node* BranchConditionDuplicator::DuplicateNode(Node* node) {
67 return graph_->CloneNode(node);
68 }
69
DuplicateConditionIfNeeded(Node * node)70 void 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
Enqueue(Node * node)79 void BranchConditionDuplicator::Enqueue(Node* node) {
80 if (seen_.Get(node)) return;
81 seen_.Set(node, true);
82 to_visit_.push(node);
83 }
84
VisitNode(Node * node)85 void 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
ProcessGraph()93 void 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
BranchConditionDuplicator(Zone * zone,Graph * graph)102 BranchConditionDuplicator::BranchConditionDuplicator(Zone* zone, Graph* graph)
103 : graph_(graph), to_visit_(zone), seen_(graph, 2) {}
104
Reduce()105 void BranchConditionDuplicator::Reduce() { ProcessGraph(); }
106
107 } // namespace compiler
108 } // namespace internal
109 } // namespace v8
110