1 // Copyright 2021 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/wasm-loop-peeling.h"
6
7 #include "src/base/small-vector.h"
8 #include "src/codegen/tick-counter.h"
9 #include "src/compiler/common-operator.h"
10 #include "src/compiler/loop-analysis.h"
11 #include "src/compiler/loop-peeling.h"
12
13 namespace v8 {
14 namespace internal {
15 namespace compiler {
16
PeelWasmLoop(Node * loop_node,ZoneUnorderedSet<Node * > * loop,Graph * graph,CommonOperatorBuilder * common,Zone * tmp_zone,SourcePositionTable * source_positions,NodeOriginTable * node_origins)17 void PeelWasmLoop(Node* loop_node, ZoneUnorderedSet<Node*>* loop, Graph* graph,
18 CommonOperatorBuilder* common, Zone* tmp_zone,
19 SourcePositionTable* source_positions,
20 NodeOriginTable* node_origins) {
21 DCHECK_EQ(loop_node->opcode(), IrOpcode::kLoop);
22 DCHECK_NOT_NULL(loop);
23 // No back-jump to the loop header means this is not really a loop.
24 if (loop_node->InputCount() < 2) return;
25
26 uint32_t copied_size = static_cast<uint32_t>(loop->size()) * 2;
27
28 NodeVector copied_nodes(tmp_zone);
29
30 NodeCopier copier(graph, copied_size, &copied_nodes, 1);
31 source_positions->AddDecorator();
32 copier.CopyNodes(graph, tmp_zone, graph->NewNode(common->Dead()),
33 base::make_iterator_range(loop->begin(), loop->end()),
34 source_positions, node_origins);
35 source_positions->RemoveDecorator();
36
37 Node* peeled_iteration_header = copier.map(loop_node);
38
39 // The terminator nodes in the copies need to get connected to the graph's end
40 // node, except Terminate nodes which will be deleted anyway.
41 for (Node* node : copied_nodes) {
42 if (IrOpcode::IsGraphTerminator(node->opcode()) &&
43 node->opcode() != IrOpcode::kTerminate && node->UseCount() == 0) {
44 NodeProperties::MergeControlToEnd(graph, common, node);
45 }
46 }
47
48 // Step 1: Create merges for loop exits.
49 for (Node* node : loop_node->uses()) {
50 // We do not need the Terminate node for the peeled iteration.
51 if (node->opcode() == IrOpcode::kTerminate) {
52 copier.map(node)->Kill();
53 continue;
54 }
55 if (node->opcode() != IrOpcode::kLoopExit) continue;
56 DCHECK_EQ(node->InputAt(1), loop_node);
57 // Create a merge node for the peeled iteration and main loop. Skip the
58 // LoopExit node in the peeled iteration, use its control input instead.
59 Node* merge_node =
60 graph->NewNode(common->Merge(2), node, copier.map(node)->InputAt(0));
61 // Replace all uses of the loop exit with the merge node.
62 for (Edge use_edge : node->use_edges()) {
63 Node* use = use_edge.from();
64 if (loop->count(use) == 1) {
65 // Uses within the loop will be LoopExitEffects and LoopExitValues.
66 // Those are used by nodes outside the loop. We need to create phis from
67 // the main loop and peeled iteration to replace loop exits.
68 DCHECK(use->opcode() == IrOpcode::kLoopExitEffect ||
69 use->opcode() == IrOpcode::kLoopExitValue);
70 const Operator* phi_operator =
71 use->opcode() == IrOpcode::kLoopExitEffect
72 ? common->EffectPhi(2)
73 : common->Phi(LoopExitValueRepresentationOf(use->op()), 2);
74 Node* phi = graph->NewNode(phi_operator, use,
75 copier.map(use)->InputAt(0), merge_node);
76 use->ReplaceUses(phi);
77 // Fix the input of phi we just broke.
78 phi->ReplaceInput(0, use);
79 copier.map(use)->Kill();
80 } else if (use != merge_node) {
81 // For uses outside the loop, simply redirect them to the merge.
82 use->ReplaceInput(use_edge.index(), merge_node);
83 }
84 }
85 copier.map(node)->Kill();
86 }
87
88 // Step 2: The peeled iteration is not a loop anymore. Any control uses of
89 // its loop header should now point to its non-recursive input. Any phi uses
90 // should use the value coming from outside the loop.
91 for (Edge use_edge : peeled_iteration_header->use_edges()) {
92 if (NodeProperties::IsPhi(use_edge.from())) {
93 use_edge.from()->ReplaceUses(use_edge.from()->InputAt(0));
94 } else {
95 use_edge.UpdateTo(loop_node->InputAt(0));
96 }
97 }
98
99 // We are now left with an unconnected subgraph of the peeled Loop node and
100 // its phi uses.
101
102 // Step 3: Rewire the peeled iteration to flow into the main loop.
103
104 // We are reusing the Loop node of the peeled iteration and its phis as the
105 // merge and phis which flow from the peeled iteration into the main loop.
106 // First, remove the non-recursive input.
107 peeled_iteration_header->RemoveInput(0);
108 NodeProperties::ChangeOp(
109 peeled_iteration_header,
110 common->Merge(peeled_iteration_header->InputCount()));
111
112 // Remove the non-recursive input.
113 for (Edge use_edge : peeled_iteration_header->use_edges()) {
114 DCHECK(NodeProperties::IsPhi(use_edge.from()));
115 use_edge.from()->RemoveInput(0);
116 const Operator* phi = common->ResizeMergeOrPhi(
117 use_edge.from()->op(),
118 use_edge.from()->InputCount() - /* control input */ 1);
119 NodeProperties::ChangeOp(use_edge.from(), phi);
120 }
121
122 // In the main loop, change inputs to the merge and phis above.
123 loop_node->ReplaceInput(0, peeled_iteration_header);
124 for (Edge use_edge : loop_node->use_edges()) {
125 if (NodeProperties::IsPhi(use_edge.from())) {
126 use_edge.from()->ReplaceInput(0, copier.map(use_edge.from()));
127 }
128 }
129 }
130
131 } // namespace compiler
132 } // namespace internal
133 } // namespace v8
134