1// Copyright (c) 2018 Google LLC.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#ifndef SOURCE_OPT_LOOP_UTILS_H_
16#define SOURCE_OPT_LOOP_UTILS_H_
17
18#include <list>
19#include <memory>
20#include <unordered_map>
21#include <vector>
22
23#include "source/opt/ir_context.h"
24#include "source/opt/loop_descriptor.h"
25
26namespace spvtools {
27
28namespace opt {
29
30// Class to gather some metrics about a Region Of Interest (ROI).
31// So far it counts the number of instructions in a ROI (excluding debug
32// and label instructions) per basic block and in total.
33struct CodeMetrics {
34 void Analyze(const Loop& loop);
35
36 // The number of instructions per basic block in the ROI.
37 std::unordered_map<uint32_t, size_t> block_sizes_;
38
39 // Number of instruction in the ROI.
40 size_t roi_size_;
41};
42
43// LoopUtils is used to encapsulte loop optimizations and from the passes which
44// use them. Any pass which needs a loop optimization should do it through this
45// or through a pass which is using this.
46class LoopUtils {
47 public:
48 // Holds a auxiliary results of the loop cloning procedure.
49 struct LoopCloningResult {
50 using ValueMapTy = std::unordered_map<uint32_t, uint32_t>;
51 using BlockMapTy = std::unordered_map<uint32_t, BasicBlock*>;
52 using PtrMap = std::unordered_map<Instruction*, Instruction*>;
53
54 PtrMap ptr_map_;
55
56 // Mapping between the original loop ids and the new one.
57 ValueMapTy value_map_;
58 // Mapping between original loop blocks to the cloned one.
59 BlockMapTy old_to_new_bb_;
60 // Mapping between the cloned loop blocks to original one.
61 BlockMapTy new_to_old_bb_;
62 // List of cloned basic block.
63 std::vector<std::unique_ptr<BasicBlock>> cloned_bb_;
64 };
65
66 LoopUtils(IRContext* context, Loop* loop)
67 : context_(context),
68 loop_desc_(
69 context->GetLoopDescriptor(loop->GetHeaderBlock()->GetParent())),
70 loop_(loop),
71 function_(*loop_->GetHeaderBlock()->GetParent()) {}
72
73 // The converts the current loop to loop closed SSA form.
74 // In the loop closed SSA, all loop exiting values go through a dedicated Phi
75 // instruction. For instance:
76 //
77 // for (...) {
78 // A1 = ...
79 // if (...)
80 // A2 = ...
81 // A = phi A1, A2
82 // }
83 // ... = op A ...
84 //
85 // Becomes
86 //
87 // for (...) {
88 // A1 = ...
89 // if (...)
90 // A2 = ...
91 // A = phi A1, A2
92 // }
93 // C = phi A
94 // ... = op C ...
95 //
96 // This makes some loop transformations (such as loop unswitch) simpler
97 // (removes the needs to take care of exiting variables).
98 void MakeLoopClosedSSA();
99
100 // Create dedicate exit basic block. This ensure all exit basic blocks has the
101 // loop as sole predecessors.
102 // By construction, structured control flow already has a dedicated exit
103 // block.
104 // Preserves: CFG, def/use and instruction to block mapping.
105 void CreateLoopDedicatedExits();
106
107 // Clone |loop_| and remap its instructions. Newly created blocks
108 // will be added to the |cloning_result.cloned_bb_| list, correctly ordered to
109 // be inserted into a function.
110 // It is assumed that |ordered_loop_blocks| is compatible with the result of
111 // |Loop::ComputeLoopStructuredOrder|. If the preheader and merge block are in
112 // the list they will also be cloned. If not, the resulting loop will share
113 // them with the original loop.
114 // The function preserves the def/use, cfg and instr to block analyses.
115 // The cloned loop nest will be added to the loop descriptor and will have
116 // ownership.
117 Loop* CloneLoop(LoopCloningResult* cloning_result,
118 const std::vector<BasicBlock*>& ordered_loop_blocks) const;
119 // Clone |loop_| and remap its instructions, as above. Overload to compute
120 // loop block ordering within method rather than taking in as parameter.
121 Loop* CloneLoop(LoopCloningResult* cloning_result) const;
122
123 // Clone the |loop_| and make the new loop branch to the second loop on exit.
124 Loop* CloneAndAttachLoopToHeader(LoopCloningResult* cloning_result);
125
126 // Perfom a partial unroll of |loop| by given |factor|. This will copy the
127 // body of the loop |factor| times. So a |factor| of one would give a new loop
128 // with the original body plus one unrolled copy body.
129 bool PartiallyUnroll(size_t factor);
130
131 // Fully unroll |loop|.
132 bool FullyUnroll();
133
134 // This function validates that |loop| meets the assumptions made by the
135 // implementation of the loop unroller. As the implementation accommodates
136 // more types of loops this function can reduce its checks.
137 //
138 // The conditions checked to ensure the loop can be unrolled are as follows:
139 // 1. That the loop is in structured order.
140 // 2. That the continue block is a branch to the header.
141 // 3. That the only phi used in the loop is the induction variable.
142 // TODO(stephen@codeplay.com): This is a temporary mesure, after the loop is
143 // converted into LCSAA form and has a single entry and exit we can rewrite
144 // the other phis.
145 // 4. That this is an inner most loop, or that loops contained within this
146 // loop have already been fully unrolled.
147 // 5. That each instruction in the loop is only used within the loop.
148 // (Related to the above phi condition).
149 bool CanPerformUnroll();
150
151 // Maintains the loop descriptor object after the unroll functions have been
152 // called, otherwise the analysis should be invalidated.
153 void Finalize();
154
155 // Returns the context associate to |loop_|.
156 IRContext* GetContext() { return context_; }
157 // Returns the loop descriptor owning |loop_|.
158 LoopDescriptor* GetLoopDescriptor() { return loop_desc_; }
159 // Returns the loop on which the object operates on.
160 Loop* GetLoop() const { return loop_; }
161 // Returns the function that |loop_| belong to.
162 Function* GetFunction() const { return &function_; }
163
164 private:
165 IRContext* context_;
166 LoopDescriptor* loop_desc_;
167 Loop* loop_;
168 Function& function_;
169
170 // Populates the loop nest of |new_loop| according to |loop_| nest.
171 void PopulateLoopNest(Loop* new_loop,
172 const LoopCloningResult& cloning_result) const;
173
174 // Populates |new_loop| descriptor according to |old_loop|'s one.
175 void PopulateLoopDesc(Loop* new_loop, Loop* old_loop,
176 const LoopCloningResult& cloning_result) const;
177};
178
179} // namespace opt
180} // namespace spvtools
181
182#endif // SOURCE_OPT_LOOP_UTILS_H_
183