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/loop-unrolling.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 UnrollLoop(Node* loop_node, ZoneUnorderedSet<Node*>* loop, uint32_t depth,
18                Graph* graph, 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 unrolling_count =
27      unrolling_count_heuristic(static_cast<uint32_t>(loop->size()), depth);
28  if (unrolling_count == 0) return;
29
30  uint32_t iteration_count = unrolling_count + 1;
31
32  uint32_t copied_size = static_cast<uint32_t>(loop->size()) * iteration_count;
33
34  NodeVector copies(tmp_zone);
35
36  NodeCopier copier(graph, copied_size, &copies, unrolling_count);
37  source_positions->AddDecorator();
38  copier.CopyNodes(graph, tmp_zone, graph->NewNode(common->Dead()),
39                   base::make_iterator_range(loop->begin(), loop->end()),
40                   source_positions, node_origins);
41  source_positions->RemoveDecorator();
42
43  // The terminator nodes in the copies need to get connected to the graph's end
44  // node, except Terminate nodes which will be deleted anyway.
45  for (Node* node : copies) {
46    if (IrOpcode::IsGraphTerminator(node->opcode()) &&
47        node->opcode() != IrOpcode::kTerminate && node->UseCount() == 0) {
48      NodeProperties::MergeControlToEnd(graph, common, node);
49    }
50  }
51
52#define COPY(node, n) copier.map(node, n)
53#define FOREACH_COPY_INDEX(i) for (uint32_t i = 0; i < unrolling_count; i++)
54
55  for (Node* node : loop_node->uses()) {
56    switch (node->opcode()) {
57      case IrOpcode::kBranch: {
58        /*** Step 1: Remove stack checks from all but the first iteration of the
59             loop. ***/
60        Node* stack_check = node->InputAt(0);
61        if (stack_check->opcode() != IrOpcode::kStackPointerGreaterThan) {
62          break;
63        }
64        FOREACH_COPY_INDEX(i) {
65          COPY(node, i)->ReplaceInput(0,
66                                      graph->NewNode(common->Int32Constant(1)));
67        }
68        for (Node* use : stack_check->uses()) {
69          if (use->opcode() == IrOpcode::kEffectPhi) {
70            // We now need to remove stack check and the related function call
71            // from the effect chain.
72            // The effect chain looks like this (* stand for irrelevant nodes):
73            //
74            // {replacing_effect} (effect before stack check)
75            //   *  *  |  *
76            //   |  |  |  |
77            // ( LoadFromObject )
78            //   |  |
79            // {stack_check}
80            // |   |
81            // |   *
82            // |
83            // | * *
84            // | | |
85            // {use}: EffectPhi (stack check effect that we need to replace)
86            DCHECK_EQ(use->opcode(), IrOpcode::kEffectPhi);
87            DCHECK_EQ(NodeProperties::GetEffectInput(use), stack_check);
88            DCHECK_EQ(NodeProperties::GetEffectInput(stack_check)->opcode(),
89                      IrOpcode::kLoadFromObject);
90            Node* replacing_effect = NodeProperties::GetEffectInput(
91                NodeProperties::GetEffectInput(stack_check));
92            FOREACH_COPY_INDEX(i) {
93              COPY(use, i)->ReplaceUses(COPY(replacing_effect, i));
94            }
95          }
96        }
97        break;
98      }
99
100      case IrOpcode::kLoopExit: {
101        /*** Step 2: Create merges for loop exits. ***/
102        if (node->InputAt(1) == loop_node) {
103          // Create a merge node from all iteration exits.
104          Node** merge_inputs = tmp_zone->NewArray<Node*>(iteration_count);
105          merge_inputs[0] = node;
106          for (uint32_t i = 1; i < iteration_count; i++) {
107            merge_inputs[i] = COPY(node, i - 1);
108          }
109          Node* merge_node = graph->NewNode(common->Merge(iteration_count),
110                                            iteration_count, merge_inputs);
111          // Replace all uses of the loop exit with the merge node.
112          for (Edge use_edge : node->use_edges()) {
113            Node* use = use_edge.from();
114            if (loop->count(use) == 1) {
115              // Uses within the loop will be LoopExitEffects and
116              // LoopExitValues. We need to create a phi from all loop
117              // iterations. Its merge will be the merge node for LoopExits.
118              const Operator* phi_operator;
119              if (use->opcode() == IrOpcode::kLoopExitEffect) {
120                phi_operator = common->EffectPhi(iteration_count);
121              } else {
122                DCHECK(use->opcode() == IrOpcode::kLoopExitValue);
123                phi_operator = common->Phi(
124                    LoopExitValueRepresentationOf(use->op()), iteration_count);
125              }
126              Node** phi_inputs =
127                  tmp_zone->NewArray<Node*>(iteration_count + 1);
128              phi_inputs[0] = use;
129              for (uint32_t i = 1; i < iteration_count; i++) {
130                phi_inputs[i] = COPY(use, i - 1);
131              }
132              phi_inputs[iteration_count] = merge_node;
133              Node* phi =
134                  graph->NewNode(phi_operator, iteration_count + 1, phi_inputs);
135              use->ReplaceUses(phi);
136              // Repair phi which we just broke.
137              phi->ReplaceInput(0, use);
138            } else if (use != merge_node) {
139              // For uses outside the loop, simply redirect them to the merge.
140              use->ReplaceInput(use_edge.index(), merge_node);
141            }
142          }
143        }
144        break;
145      }
146
147      case IrOpcode::kTerminate: {
148        // We only need to keep the Terminate node for the loop header of the
149        // first iteration.
150        FOREACH_COPY_INDEX(i) { COPY(node, i)->Kill(); }
151        break;
152      }
153
154      default:
155        break;
156    }
157  }
158
159  /*** Step 3: Rewire the iterations of the loop. Each iteration should flow
160       into the next one, and the last should flow into the first. ***/
161
162  // 3a) Rewire control.
163
164  // We start at index=1 assuming that index=0 is the (non-recursive) loop
165  // entry.
166  for (int input_index = 1; input_index < loop_node->InputCount();
167       input_index++) {
168    Node* last_iteration_input =
169        COPY(loop_node, unrolling_count - 1)->InputAt(input_index);
170    for (uint32_t copy_index = unrolling_count - 1; copy_index > 0;
171         copy_index--) {
172      COPY(loop_node, copy_index)
173          ->ReplaceInput(input_index,
174                         COPY(loop_node, copy_index - 1)->InputAt(input_index));
175    }
176    COPY(loop_node, 0)
177        ->ReplaceInput(input_index, loop_node->InputAt(input_index));
178    loop_node->ReplaceInput(input_index, last_iteration_input);
179  }
180  // The loop of each following iteration will become a merge. We need to remove
181  // its non-recursive input.
182  FOREACH_COPY_INDEX(i) {
183    COPY(loop_node, i)->RemoveInput(0);
184    NodeProperties::ChangeOp(COPY(loop_node, i),
185                             common->Merge(loop_node->InputCount() - 1));
186  }
187
188  // 3b) Rewire phis and loop exits.
189  for (Node* use : loop_node->uses()) {
190    if (NodeProperties::IsPhi(use)) {
191      int count = use->opcode() == IrOpcode::kPhi
192                      ? use->op()->ValueInputCount()
193                      : use->op()->EffectInputCount();
194      // Phis depending on the loop header should take their input from the
195      // previous iteration instead.
196      for (int input_index = 1; input_index < count; input_index++) {
197        Node* last_iteration_input =
198            COPY(use, unrolling_count - 1)->InputAt(input_index);
199        for (uint32_t copy_index = unrolling_count - 1; copy_index > 0;
200             copy_index--) {
201          COPY(use, copy_index)
202              ->ReplaceInput(input_index,
203                             COPY(use, copy_index - 1)->InputAt(input_index));
204        }
205        COPY(use, 0)->ReplaceInput(input_index, use->InputAt(input_index));
206        use->ReplaceInput(input_index, last_iteration_input);
207      }
208
209      // Phis in each following iteration should not depend on the
210      // (non-recursive) entry to the loop. Remove their first input.
211      FOREACH_COPY_INDEX(i) {
212        COPY(use, i)->RemoveInput(0);
213        NodeProperties::ChangeOp(
214            COPY(use, i), common->ResizeMergeOrPhi(use->op(), count - 1));
215      }
216    }
217
218    // Loop exits should point to the loop header.
219    if (use->opcode() == IrOpcode::kLoopExit) {
220      FOREACH_COPY_INDEX(i) { COPY(use, i)->ReplaceInput(1, loop_node); }
221    }
222  }
223}
224
225#undef COPY
226#undef FOREACH_COPY_INDEX
227
228}  // namespace compiler
229}  // namespace internal
230}  // namespace v8
231