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
13namespace v8 {
14namespace internal {
15namespace compiler {
16
17void 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