| 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 |
|
| 26 |
namespace spvtools { |
| 27 |
|
| 28 |
namespace 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. |
| 33 |
struct 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. |
| 46 |
class 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([email protected]): 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_ |