| 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 |
#include "source/opt/loop_unroller.h" |
| 16 |
|
| 17 |
#include <limits> |
| 18 |
#include <map> |
| 19 |
#include <memory> |
| 20 |
#include <unordered_map> |
| 21 |
#include <utility> |
| 22 |
#include <vector> |
| 23 |
|
| 24 |
#include "source/opt/ir_builder.h" |
| 25 |
#include "source/opt/loop_utils.h" |
| 26 |
|
| 27 |
// Implements loop util unrolling functionality for fully and partially |
| 28 |
// unrolling loops. Given a factor it will duplicate the loop that many times, |
| 29 |
// appending each one to the end of the old loop and removing backedges, to |
| 30 |
// create a new unrolled loop. |
| 31 |
// |
| 32 |
// 1 - User calls LoopUtils::FullyUnroll or LoopUtils::PartiallyUnroll with a |
| 33 |
// loop they wish to unroll. LoopUtils::CanPerformUnroll is used to |
| 34 |
// validate that a given loop can be unrolled. That method (along with the |
| 35 |
// constructor of loop) checks that the IR is in the expected canonicalised |
| 36 |
// format. |
| 37 |
// |
| 38 |
// 2 - The LoopUtils methods create a LoopUnrollerUtilsImpl object to actually |
| 39 |
// perform the unrolling. This implements helper methods to copy the loop basic |
| 40 |
// blocks and remap the ids of instructions used inside them. |
| 41 |
// |
| 42 |
// 3 - The core of LoopUnrollerUtilsImpl is the Unroll method, this method |
| 43 |
// actually performs the loop duplication. It does this by creating a |
| 44 |
// LoopUnrollState object and then copying the loop as given by the factor |
| 45 |
// parameter. The LoopUnrollState object retains the state of the unroller |
| 46 |
// between the loop body copies as each iteration needs information on the last |
| 47 |
// to adjust the phi induction variable, adjust the OpLoopMerge instruction in |
| 48 |
// the main loop header, and change the previous continue block to point to the |
| 49 |
// new header and the new continue block to the main loop header. |
| 50 |
// |
| 51 |
// 4 - If the loop is to be fully unrolled then it is simply closed after step |
| 52 |
// 3, with the OpLoopMerge being deleted, the backedge removed, and the |
| 53 |
// condition blocks folded. |
| 54 |
// |
| 55 |
// 5 - If it is being partially unrolled: if the unrolling factor leaves the |
| 56 |
// loop with an even number of bodies with respect to the number of loop |
| 57 |
// iterations then step 3 is all that is needed. If it is uneven then we need to |
| 58 |
// duplicate the loop completely and unroll the duplicated loop to cover the |
| 59 |
// residual part and adjust the first loop to cover only the "even" part. For |
| 60 |
// instance if you request an unroll factor of 3 on a loop with 10 iterations |
| 61 |
// then copying the body three times would leave you with three bodies in the |
| 62 |
// loop |
| 63 |
// where the loop still iterates over each 4 times. So we make two loops one |
| 64 |
// iterating once then a second loop of three iterating 3 times. |
| 65 |
|
| 66 |
namespace spvtools { |
| 67 |
namespace opt { |
| 68 |
namespace { |
| 69 |
|
| 70 |
// Loop control constant value for DontUnroll flag. |
| 71 |
static const uint32_t kLoopControlDontUnrollIndex = 2; |
| 72 |
|
| 73 |
// Operand index of the loop control parameter of the OpLoopMerge. |
| 74 |
static const uint32_t kLoopControlIndex = 2; |
| 75 |
|
| 76 |
// This utility class encapsulates some of the state we need to maintain between |
| 77 |
// loop unrolls. Specifically it maintains key blocks and the induction variable |
| 78 |
// in the current loop duplication step and the blocks from the previous one. |
| 79 |
// This is because each step of the unroll needs to use data from both the |
| 80 |
// preceding step and the original loop. |
| 81 |
struct LoopUnrollState { |
| 82 |
LoopUnrollState() |
| 83 |
: previous_phi_(nullptr), |
| 84 |
previous_latch_block_(nullptr), |
| 85 |
previous_condition_block_(nullptr), |
| 86 |
new_phi(nullptr), |
| 87 |
new_continue_block(nullptr), |
| 88 |
new_condition_block(nullptr), |
| 89 |
new_header_block(nullptr) {} |
| 90 |
|
| 91 |
// Initialize from the loop descriptor class. |
| 92 |
LoopUnrollState(Instruction* induction, BasicBlock* latch_block, |
| 93 |
BasicBlock* condition, std::vector<Instruction*>&& phis) |
| 94 |
: previous_phi_(induction), |
| 95 |
previous_latch_block_(latch_block), |
| 96 |
previous_condition_block_(condition), |
| 97 |
new_phi(nullptr), |
| 98 |
new_continue_block(nullptr), |
| 99 |
new_condition_block(nullptr), |
| 100 |
new_header_block(nullptr) { |
| 101 |
previous_phis_ = std::move(phis); |
| 102 |
} |
| 103 |
|
| 104 |
// Swap the state so that the new nodes are now the previous nodes. |
| 105 |
void NextIterationState() { |
| 106 |
previous_phi_ = new_phi; |
| 107 |
previous_latch_block_ = new_latch_block; |
| 108 |
previous_condition_block_ = new_condition_block; |
| 109 |
previous_phis_ = std::move(new_phis_); |
| 110 |
|
| 111 |
// Clear new nodes. |
| 112 |
new_phi = nullptr; |
| 113 |
new_continue_block = nullptr; |
| 114 |
new_condition_block = nullptr; |
| 115 |
new_header_block = nullptr; |
| 116 |
new_latch_block = nullptr; |
| 117 |
|
| 118 |
// Clear new block/instruction maps. |
| 119 |
new_blocks.clear(); |
| 120 |
new_inst.clear(); |
| 121 |
ids_to_new_inst.clear(); |
| 122 |
} |
| 123 |
|
| 124 |
// The induction variable from the immediately preceding loop body. |
| 125 |
Instruction* previous_phi_; |
| 126 |
|
| 127 |
// All the phi nodes from the previous loop iteration. |
| 128 |
std::vector<Instruction*> previous_phis_; |
| 129 |
|
| 130 |
std::vector<Instruction*> new_phis_; |
| 131 |
|
| 132 |
// The previous latch block. The backedge will be removed from this and |
| 133 |
// added to the new latch block. |
| 134 |
BasicBlock* previous_latch_block_; |
| 135 |
|
| 136 |
// The previous condition block. This may be folded to flatten the loop. |
| 137 |
BasicBlock* previous_condition_block_; |
| 138 |
|
| 139 |
// The new induction variable. |
| 140 |
Instruction* new_phi; |
| 141 |
|
| 142 |
// The new continue block. |
| 143 |
BasicBlock* new_continue_block; |
| 144 |
|
| 145 |
// The new condition block. |
| 146 |
BasicBlock* new_condition_block; |
| 147 |
|
| 148 |
// The new header block. |
| 149 |
BasicBlock* new_header_block; |
| 150 |
|
| 151 |
// The new latch block. |
| 152 |
BasicBlock* new_latch_block; |
| 153 |
|
| 154 |
// A mapping of new block ids to the original blocks which they were copied |
| 155 |
// from. |
| 156 |
std::unordered_map<uint32_t, BasicBlock*> new_blocks; |
| 157 |
|
| 158 |
// A mapping of the original instruction ids to the instruction ids to their |
| 159 |
// copies. |
| 160 |
std::unordered_map<uint32_t, uint32_t> new_inst; |
| 161 |
|
| 162 |
std::unordered_map<uint32_t, Instruction*> ids_to_new_inst; |
| 163 |
}; |
| 164 |
|
| 165 |
// This class implements the actual unrolling. It uses a LoopUnrollState to |
| 166 |
// maintain the state of the unrolling inbetween steps. |
| 167 |
class LoopUnrollerUtilsImpl { |
| 168 |
public: |
| 169 |
using BasicBlockListTy = std::vector<std::unique_ptr<BasicBlock>>; |
| 170 |
|
| 171 |
LoopUnrollerUtilsImpl(IRContext* c, Function* function) |
| 172 |
: context_(c), |
| 173 |
function_(*function), |
| 174 |
loop_condition_block_(nullptr), |
| 175 |
loop_induction_variable_(nullptr), |
| 176 |
number_of_loop_iterations_(0), |
| 177 |
loop_step_value_(0), |
| 178 |
loop_init_value_(0) {} |
| 179 |
|
| 180 |
// Unroll the |loop| by given |factor| by copying the whole body |factor| |
| 181 |
// times. The resulting basicblock structure will remain a loop. |
| 182 |
void PartiallyUnroll(Loop*, size_t factor); |
| 183 |
|
| 184 |
// If partially unrolling the |loop| would leave the loop with too many bodies |
| 185 |
// for its number of iterations then this method should be used. This method |
| 186 |
// will duplicate the |loop| completely, making the duplicated loop the |
| 187 |
// successor of the original's merge block. The original loop will have its |
| 188 |
// condition changed to loop over the residual part and the duplicate will be |
| 189 |
// partially unrolled. The resulting structure will be two loops. |
| 190 |
void PartiallyUnrollResidualFactor(Loop* loop, size_t factor); |
| 191 |
|
| 192 |
// Fully unroll the |loop| by copying the full body by the total number of |
| 193 |
// loop iterations, folding all conditions, and removing the backedge from the |
| 194 |
// continue block to the header. |
| 195 |
void FullyUnroll(Loop* loop); |
| 196 |
|
| 197 |
// Get the ID of the variable in the |phi| paired with |label|. |
| 198 |
uint32_t GetPhiDefID(const Instruction* phi, uint32_t label) const; |
| 199 |
|
| 200 |
// Close the loop by removing the OpLoopMerge from the |loop| header block and |
| 201 |
// making the backedge point to the merge block. |
| 202 |
void CloseUnrolledLoop(Loop* loop); |
| 203 |
|
| 204 |
// Remove the OpConditionalBranch instruction inside |conditional_block| used |
| 205 |
// to branch to either exit or continue the loop and replace it with an |
| 206 |
// unconditional OpBranch to block |new_target|. |
| 207 |
void FoldConditionBlock(BasicBlock* condtion_block, uint32_t new_target); |
| 208 |
|
| 209 |
// Add all blocks_to_add_ to function_ at the |insert_point|. |
| 210 |
void AddBlocksToFunction(const BasicBlock* insert_point); |
| 211 |
|
| 212 |
// Duplicates the |old_loop|, cloning each body and remaping the ids without |
| 213 |
// removing instructions or changing relative structure. Result will be stored |
| 214 |
// in |new_loop|. |
| 215 |
void DuplicateLoop(Loop* old_loop, Loop* new_loop); |
| 216 |
|
| 217 |
inline size_t GetLoopIterationCount() const { |
| 218 |
return number_of_loop_iterations_; |
| 219 |
} |
| 220 |
|
| 221 |
// Extracts the initial state information from the |loop|. |
| 222 |
void Init(Loop* loop); |
| 223 |
|
| 224 |
// Replace the uses of each induction variable outside the loop with the final |
| 225 |
// value of the induction variable before the loop exit. To reflect the proper |
| 226 |
// state of a fully unrolled loop. |
| 227 |
void ReplaceInductionUseWithFinalValue(Loop* loop); |
| 228 |
|
| 229 |
// Remove all the instructions in the invalidated_instructions_ vector. |
| 230 |
void RemoveDeadInstructions(); |
| 231 |
|
| 232 |
// Replace any use of induction variables outwith the loop with the final |
| 233 |
// value of the induction variable in the unrolled loop. |
| 234 |
void ReplaceOutsideLoopUseWithFinalValue(Loop* loop); |
| 235 |
|
| 236 |
// Set the LoopControl operand of the OpLoopMerge instruction to be |
| 237 |
// DontUnroll. |
| 238 |
void MarkLoopControlAsDontUnroll(Loop* loop) const; |
| 239 |
|
| 240 |
private: |
| 241 |
// Remap all the in |basic_block| to new IDs and keep the mapping of new ids |
| 242 |
// to old |
| 243 |
// ids. |loop| is used to identify special loop blocks (header, continue, |
| 244 |
// ect). |
| 245 |
void AssignNewResultIds(BasicBlock* basic_block); |
| 246 |
|
| 247 |
// Using the map built by AssignNewResultIds, replace the uses in |inst| |
| 248 |
// by the id that the use maps to. |
| 249 |
void RemapOperands(Instruction* inst); |
| 250 |
|
| 251 |
// Using the map built by AssignNewResultIds, for each instruction in |
| 252 |
// |basic_block| use |
| 253 |
// that map to substitute the IDs used by instructions (in the operands) with |
| 254 |
// the new ids. |
| 255 |
void RemapOperands(BasicBlock* basic_block); |
| 256 |
|
| 257 |
// Copy the whole body of the loop, all blocks dominated by the |loop| header |
| 258 |
// and not dominated by the |loop| merge. The copied body will be linked to by |
| 259 |
// the old |loop| continue block and the new body will link to the |loop| |
| 260 |
// header via the new continue block. |eliminate_conditions| is used to decide |
| 261 |
// whether or not to fold all the condition blocks other than the last one. |
| 262 |
void CopyBody(Loop* loop, bool eliminate_conditions); |
| 263 |
|
| 264 |
// Copy a given |block_to_copy| in the |loop| and record the mapping of the |
| 265 |
// old/new ids. |preserve_instructions| determines whether or not the method |
| 266 |
// will modify (other than result_id) instructions which are copied. |
| 267 |
void CopyBasicBlock(Loop* loop, const BasicBlock* block_to_copy, |
| 268 |
bool preserve_instructions); |
| 269 |
|
| 270 |
// The actual implementation of the unroll step. Unrolls |loop| by given |
| 271 |
// |factor| by copying the body by |factor| times. Also propagates the |
| 272 |
// induction variable value throughout the copies. |
| 273 |
void Unroll(Loop* loop, size_t factor); |
| 274 |
|
| 275 |
// Fills the loop_blocks_inorder_ field with the ordered list of basic blocks |
| 276 |
// as computed by the method ComputeLoopOrderedBlocks. |
| 277 |
void ComputeLoopOrderedBlocks(Loop* loop); |
| 278 |
|
| 279 |
// Adds the blocks_to_add_ to both the |loop| and to the parent of |loop| if |
| 280 |
// the parent exists. |
| 281 |
void AddBlocksToLoop(Loop* loop) const; |
| 282 |
|
| 283 |
// After the partially unroll step the phi instructions in the header block |
| 284 |
// will be in an illegal format. This function makes the phis legal by making |
| 285 |
// the edge from the latch block come from the new latch block and the value |
| 286 |
// to be the actual value of the phi at that point. |
| 287 |
void LinkLastPhisToStart(Loop* loop) const; |
| 288 |
|
| 289 |
// Kill all debug declaration instructions from |bb|. |
| 290 |
void KillDebugDeclares(BasicBlock* bb); |
| 291 |
|
| 292 |
// A pointer to the IRContext. Used to add/remove instructions and for usedef |
| 293 |
// chains. |
| 294 |
IRContext* context_; |
| 295 |
|
| 296 |
// A reference the function the loop is within. |
| 297 |
Function& function_; |
| 298 |
|
| 299 |
// A list of basic blocks to be added to the loop at the end of an unroll |
| 300 |
// step. |
| 301 |
BasicBlockListTy blocks_to_add_; |
| 302 |
|
| 303 |
// List of instructions which are now dead and can be removed. |
| 304 |
std::vector<Instruction*> invalidated_instructions_; |
| 305 |
|
| 306 |
// Maintains the current state of the transform between calls to unroll. |
| 307 |
LoopUnrollState state_; |
| 308 |
|
| 309 |
// An ordered list containing the loop basic blocks. |
| 310 |
std::vector<BasicBlock*> loop_blocks_inorder_; |
| 311 |
|
| 312 |
// The block containing the condition check which contains a conditional |
| 313 |
// branch to the merge and continue block. |
| 314 |
BasicBlock* loop_condition_block_; |
| 315 |
|
| 316 |
// The induction variable of the loop. |
| 317 |
Instruction* loop_induction_variable_; |
| 318 |
|
| 319 |
// Phis used in the loop need to be remapped to use the actual result values |
| 320 |
// and then be remapped at the end. |
| 321 |
std::vector<Instruction*> loop_phi_instructions_; |
| 322 |
|
| 323 |
// The number of loop iterations that the loop would preform pre-unroll. |
| 324 |
size_t number_of_loop_iterations_; |
| 325 |
|
| 326 |
// The amount that the loop steps each iteration. |
| 327 |
int64_t loop_step_value_; |
| 328 |
|
| 329 |
// The value the loop starts stepping from. |
| 330 |
int64_t loop_init_value_; |
| 331 |
}; |
| 332 |
|
| 333 |
/* |
| 334 |
* Static helper functions. |
| 335 |
*/ |
| 336 |
|
| 337 |
// Retrieve the index of the OpPhi instruction |phi| which corresponds to the |
| 338 |
// incoming |block| id. |
| 339 |
static uint32_t GetPhiIndexFromLabel(const BasicBlock* block, |
| 340 |
const Instruction* phi) { |
| 341 |
for (uint32_t i = 1; i < phi->NumInOperands(); i += 2) { |
| 342 |
if (block->id() == phi->GetSingleWordInOperand(i)) { |
| 343 |
return i; |
| 344 |
} |
| 345 |
} |
| 346 |
assert(false && "Could not find operand in instruction."); |
| 347 |
return 0; |
| 348 |
} |
| 349 |
|
| 350 |
void LoopUnrollerUtilsImpl::Init(Loop* loop) { |
| 351 |
loop_condition_block_ = loop->FindConditionBlock(); |
| 352 |
|
| 353 |
// When we reinit the second loop during PartiallyUnrollResidualFactor we need |
| 354 |
// to use the cached value from the duplicate step as the dominator tree |
| 355 |
// basded solution, loop->FindConditionBlock, requires all the nodes to be |
| 356 |
// connected up with the correct branches. They won't be at this point. |
| 357 |
if (!loop_condition_block_) { |
| 358 |
loop_condition_block_ = state_.new_condition_block; |
| 359 |
} |
| 360 |
assert(loop_condition_block_); |
| 361 |
|
| 362 |
loop_induction_variable_ = loop->FindConditionVariable(loop_condition_block_); |
| 363 |
assert(loop_induction_variable_); |
| 364 |
|
| 365 |
bool found = loop->FindNumberOfIterations( |
| 366 |
loop_induction_variable_, &*loop_condition_block_->ctail(), |
| 367 |
&number_of_loop_iterations_, &loop_step_value_, &loop_init_value_); |
| 368 |
(void)found; // To silence unused variable warning on release builds. |
| 369 |
assert(found); |
| 370 |
|
| 371 |
// Blocks are stored in an unordered set of ids in the loop class, we need to |
| 372 |
// create the dominator ordered list. |
| 373 |
ComputeLoopOrderedBlocks(loop); |
| 374 |
} |
| 375 |
|
| 376 |
// This function is used to partially unroll the loop when the factor provided |
| 377 |
// would normally lead to an illegal optimization. Instead of just unrolling the |
| 378 |
// loop it creates two loops and unrolls one and adjusts the condition on the |
| 379 |
// other. The end result being that the new loop pair iterates over the correct |
| 380 |
// number of bodies. |
| 381 |
void LoopUnrollerUtilsImpl::PartiallyUnrollResidualFactor(Loop* loop, |
| 382 |
size_t factor) { |
| 383 |
// TODO(1841): Handle id overflow. |
| 384 |
std::unique_ptr<Instruction> new_label{new Instruction( |
| 385 |
context_, SpvOp::SpvOpLabel, 0, context_->TakeNextId(), {})}; |
| 386 |
std::unique_ptr<BasicBlock> new_exit_bb{new BasicBlock(std::move(new_label))}; |
| 387 |
|
| 388 |
// Save the id of the block before we move it. |
| 389 |
uint32_t new_merge_id = new_exit_bb->id(); |
| 390 |
|
| 391 |
// Add the block the list of blocks to add, we want this merge block to be |
| 392 |
// right at the start of the new blocks. |
| 393 |
blocks_to_add_.push_back(std::move(new_exit_bb)); |
| 394 |
BasicBlock* new_exit_bb_raw = blocks_to_add_[0].get(); |
| 395 |
Instruction& original_conditional_branch = *loop_condition_block_->tail(); |
| 396 |
// Duplicate the loop, providing access to the blocks of both loops. |
| 397 |
// This is a naked new due to the VS2013 requirement of not having unique |
| 398 |
// pointers in vectors, as it will be inserted into a vector with |
| 399 |
// loop_descriptor.AddLoop. |
| 400 |
std::unique_ptr<Loop> new_loop = MakeUnique<Loop>(*loop); |
| 401 |
|
| 402 |
// Clear the basic blocks of the new loop. |
| 403 |
new_loop->ClearBlocks(); |
| 404 |
|
| 405 |
DuplicateLoop(loop, new_loop.get()); |
| 406 |
|
| 407 |
// Add the blocks to the function. |
| 408 |
AddBlocksToFunction(loop->GetMergeBlock()); |
| 409 |
blocks_to_add_.clear(); |
| 410 |
|
| 411 |
// Create a new merge block for the first loop. |
| 412 |
InstructionBuilder builder{context_, new_exit_bb_raw}; |
| 413 |
// Make the first loop branch to the second. |
| 414 |
builder.AddBranch(new_loop->GetHeaderBlock()->id()); |
| 415 |
|
| 416 |
loop_condition_block_ = state_.new_condition_block; |
| 417 |
loop_induction_variable_ = state_.new_phi; |
| 418 |
// Unroll the new loop by the factor with the usual -1 to account for the |
| 419 |
// existing block iteration. |
| 420 |
Unroll(new_loop.get(), factor); |
| 421 |
|
| 422 |
LinkLastPhisToStart(new_loop.get()); |
| 423 |
AddBlocksToLoop(new_loop.get()); |
| 424 |
|
| 425 |
// Add the new merge block to the back of the list of blocks to be added. It |
| 426 |
// needs to be the last block added to maintain dominator order in the binary. |
| 427 |
blocks_to_add_.push_back( |
| 428 |
std::unique_ptr<BasicBlock>(new_loop->GetMergeBlock())); |
| 429 |
|
| 430 |
// Add the blocks to the function. |
| 431 |
AddBlocksToFunction(loop->GetMergeBlock()); |
| 432 |
|
| 433 |
// Reset the usedef analysis. |
| 434 |
context_->InvalidateAnalysesExceptFor( |
| 435 |
IRContext::Analysis::kAnalysisLoopAnalysis); |
| 436 |
analysis::DefUseManager* def_use_manager = context_->get_def_use_mgr(); |
| 437 |
|
| 438 |
// The loop condition. |
| 439 |
Instruction* condition_check = def_use_manager->GetDef( |
| 440 |
original_conditional_branch.GetSingleWordOperand(0)); |
| 441 |
|
| 442 |
// This should have been checked by the LoopUtils::CanPerformUnroll function |
| 443 |
// before entering this. |
| 444 |
assert(loop->IsSupportedCondition(condition_check->opcode())); |
| 445 |
|
| 446 |
// We need to account for the initial body when calculating the remainder. |
| 447 |
int64_t remainder = Loop::GetResidualConditionValue( |
| 448 |
condition_check->opcode(), loop_init_value_, loop_step_value_, |
| 449 |
number_of_loop_iterations_, factor); |
| 450 |
|
| 451 |
assert(remainder > std::numeric_limits<int32_t>::min() && |
| 452 |
remainder < std::numeric_limits<int32_t>::max()); |
| 453 |
|
| 454 |
Instruction* new_constant = nullptr; |
| 455 |
|
| 456 |
// If the remainder is negative then we add a signed constant, otherwise just |
| 457 |
// add an unsigned constant. |
| 458 |
if (remainder < 0) { |
| 459 |
new_constant = builder.GetSintConstant(static_cast<int32_t>(remainder)); |
| 460 |
} else { |
| 461 |
new_constant = builder.GetUintConstant(static_cast<int32_t>(remainder)); |
| 462 |
} |
| 463 |
|
| 464 |
uint32_t constant_id = new_constant->result_id(); |
| 465 |
|
| 466 |
// Update the condition check. |
| 467 |
condition_check->SetInOperand(1, {constant_id}); |
| 468 |
|
| 469 |
// Update the next phi node. The phi will have a constant value coming in from |
| 470 |
// the preheader block. For the duplicated loop we need to update the constant |
| 471 |
// to be the amount of iterations covered by the first loop and the incoming |
| 472 |
// block to be the first loops new merge block. |
| 473 |
std::vector<Instruction*> new_inductions; |
| 474 |
new_loop->GetInductionVariables(new_inductions); |
| 475 |
|
| 476 |
std::vector<Instruction*> old_inductions; |
| 477 |
loop->GetInductionVariables(old_inductions); |
| 478 |
for (size_t index = 0; index < new_inductions.size(); ++index) { |
| 479 |
Instruction* new_induction = new_inductions[index]; |
| 480 |
Instruction* old_induction = old_inductions[index]; |
| 481 |
// Get the index of the loop initalizer, the value coming in from the |
| 482 |
// preheader. |
| 483 |
uint32_t initalizer_index = |
| 484 |
GetPhiIndexFromLabel(new_loop->GetPreHeaderBlock(), old_induction); |
| 485 |
|
| 486 |
// Replace the second loop initalizer with the phi from the first |
| 487 |
new_induction->SetInOperand(initalizer_index - 1, |
| 488 |
{old_induction->result_id()}); |
| 489 |
new_induction->SetInOperand(initalizer_index, {new_merge_id}); |
| 490 |
|
| 491 |
// If the use of the first loop induction variable is outside of the loop |
| 492 |
// then replace that use with the second loop induction variable. |
| 493 |
uint32_t second_loop_induction = new_induction->result_id(); |
| 494 |
auto replace_use_outside_of_loop = [loop, second_loop_induction]( |
| 495 |
Instruction* user, |
| 496 |
uint32_t operand_index) { |
| 497 |
if (!loop->IsInsideLoop(user)) { |
| 498 |
user->SetOperand(operand_index, {second_loop_induction}); |
| 499 |
} |
| 500 |
}; |
| 501 |
|
| 502 |
context_->get_def_use_mgr()->ForEachUse(old_induction, |
| 503 |
replace_use_outside_of_loop); |
| 504 |
} |
| 505 |
|
| 506 |
context_->InvalidateAnalysesExceptFor( |
| 507 |
IRContext::Analysis::kAnalysisLoopAnalysis); |
| 508 |
|
| 509 |
context_->ReplaceAllUsesWith(loop->GetMergeBlock()->id(), new_merge_id); |
| 510 |
|
| 511 |
LoopDescriptor& loop_descriptor = *context_->GetLoopDescriptor(&function_); |
| 512 |
|
| 513 |
loop_descriptor.AddLoop(std::move(new_loop), loop->GetParent()); |
| 514 |
|
| 515 |
RemoveDeadInstructions(); |
| 516 |
} |
| 517 |
|
| 518 |
// Mark this loop as DontUnroll as it will already be unrolled and it may not |
| 519 |
// be safe to unroll a previously partially unrolled loop. |
| 520 |
void LoopUnrollerUtilsImpl::MarkLoopControlAsDontUnroll(Loop* loop) const { |
| 521 |
Instruction* loop_merge_inst = loop->GetHeaderBlock()->GetLoopMergeInst(); |
| 522 |
assert(loop_merge_inst && |
| 523 |
"Loop merge instruction could not be found after entering unroller " |
| 524 |
"(should have exited before this)"); |
| 525 |
loop_merge_inst->SetInOperand(kLoopControlIndex, |
| 526 |
{kLoopControlDontUnrollIndex}); |
| 527 |
} |
| 528 |
|
| 529 |
// Duplicate the |loop| body |factor| - 1 number of times while keeping the loop |
| 530 |
// backedge intact. This will leave the loop with |factor| number of bodies |
| 531 |
// after accounting for the initial body. |
| 532 |
void LoopUnrollerUtilsImpl::Unroll(Loop* loop, size_t factor) { |
| 533 |
// If we unroll a loop partially it will not be safe to unroll it further. |
| 534 |
// This is due to the current method of calculating the number of loop |
| 535 |
// iterations. |
| 536 |
MarkLoopControlAsDontUnroll(loop); |
| 537 |
|
| 538 |
std::vector<Instruction*> inductions; |
| 539 |
loop->GetInductionVariables(inductions); |
| 540 |
state_ = LoopUnrollState{loop_induction_variable_, loop->GetLatchBlock(), |
| 541 |
loop_condition_block_, std::move(inductions)}; |
| 542 |
for (size_t i = 0; i < factor - 1; ++i) { |
| 543 |
CopyBody(loop, true); |
| 544 |
} |
| 545 |
} |
| 546 |
|
| 547 |
void LoopUnrollerUtilsImpl::RemoveDeadInstructions() { |
| 548 |
// Remove the dead instructions. |
| 549 |
for (Instruction* inst : invalidated_instructions_) { |
| 550 |
context_->KillInst(inst); |
| 551 |
} |
| 552 |
} |
| 553 |
|
| 554 |
void LoopUnrollerUtilsImpl::ReplaceInductionUseWithFinalValue(Loop* loop) { |
| 555 |
context_->InvalidateAnalysesExceptFor( |
| 556 |
IRContext::Analysis::kAnalysisLoopAnalysis | |
| 557 |
IRContext::Analysis::kAnalysisDefUse | |
| 558 |
IRContext::Analysis::kAnalysisInstrToBlockMapping); |
| 559 |
|
| 560 |
std::vector<Instruction*> inductions; |
| 561 |
loop->GetInductionVariables(inductions); |
| 562 |
|
| 563 |
for (size_t index = 0; index < inductions.size(); ++index) { |
| 564 |
uint32_t trip_step_id = GetPhiDefID(state_.previous_phis_[index], |
| 565 |
state_.previous_latch_block_->id()); |
| 566 |
context_->ReplaceAllUsesWith(inductions[index]->result_id(), trip_step_id); |
| 567 |
invalidated_instructions_.push_back(inductions[index]); |
| 568 |
} |
| 569 |
} |
| 570 |
|
| 571 |
// Fully unroll the loop by partially unrolling it by the number of loop |
| 572 |
// iterations minus one for the body already accounted for. |
| 573 |
void LoopUnrollerUtilsImpl::FullyUnroll(Loop* loop) { |
| 574 |
// We unroll the loop by number of iterations in the loop. |
| 575 |
Unroll(loop, number_of_loop_iterations_); |
| 576 |
|
| 577 |
// The first condition block is preserved until now so it can be copied. |
| 578 |
FoldConditionBlock(loop_condition_block_, 1); |
| 579 |
|
| 580 |
// Delete the OpLoopMerge and remove the backedge to the header. |
| 581 |
CloseUnrolledLoop(loop); |
| 582 |
|
| 583 |
// Mark the loop for later deletion. This allows us to preserve the loop |
| 584 |
// iterators but still disregard dead loops. |
| 585 |
loop->MarkLoopForRemoval(); |
| 586 |
|
| 587 |
// If the loop has a parent add the new blocks to the parent. |
| 588 |
if (loop->GetParent()) { |
| 589 |
AddBlocksToLoop(loop->GetParent()); |
| 590 |
} |
| 591 |
|
| 592 |
// Add the blocks to the function. |
| 593 |
AddBlocksToFunction(loop->GetMergeBlock()); |
| 594 |
|
| 595 |
ReplaceInductionUseWithFinalValue(loop); |
| 596 |
|
| 597 |
RemoveDeadInstructions(); |
| 598 |
// Invalidate all analyses. |
| 599 |
context_->InvalidateAnalysesExceptFor( |
| 600 |
IRContext::Analysis::kAnalysisLoopAnalysis | |
| 601 |
IRContext::Analysis::kAnalysisDefUse); |
| 602 |
} |
| 603 |
|
| 604 |
void LoopUnrollerUtilsImpl::KillDebugDeclares(BasicBlock* bb) { |
| 605 |
// We cannot kill an instruction inside BasicBlock::ForEachInst() |
| 606 |
// because it will generate dangling pointers. We use |to_be_killed| |
| 607 |
// to kill them after the loop. |
| 608 |
std::vector<Instruction*> to_be_killed; |
| 609 |
|
| 610 |
bb->ForEachInst([&to_be_killed, this](Instruction* inst) { |
| 611 |
if (context_->get_debug_info_mgr()->IsDebugDeclare(inst)) { |
| 612 |
to_be_killed.push_back(inst); |
| 613 |
} |
| 614 |
}); |
| 615 |
for (auto* inst : to_be_killed) context_->KillInst(inst); |
| 616 |
} |
| 617 |
|
| 618 |
// Copy a given basic block, give it a new result_id, and store the new block |
| 619 |
// and the id mapping in the state. |preserve_instructions| is used to determine |
| 620 |
// whether or not this function should edit instructions other than the |
| 621 |
// |result_id|. |
| 622 |
void LoopUnrollerUtilsImpl::CopyBasicBlock(Loop* loop, const BasicBlock* itr, |
| 623 |
bool preserve_instructions) { |
| 624 |
// Clone the block exactly, including the IDs. |
| 625 |
BasicBlock* basic_block = itr->Clone(context_); |
| 626 |
basic_block->SetParent(itr->GetParent()); |
| 627 |
|
| 628 |
// We do not want to duplicate DebugDeclare. |
| 629 |
KillDebugDeclares(basic_block); |
| 630 |
|
| 631 |
// Assign each result a new unique ID and keep a mapping of the old ids to |
| 632 |
// the new ones. |
| 633 |
AssignNewResultIds(basic_block); |
| 634 |
|
| 635 |
// If this is the continue block we are copying. |
| 636 |
if (itr == loop->GetContinueBlock()) { |
| 637 |
// Make the OpLoopMerge point to this block for the continue. |
| 638 |
if (!preserve_instructions) { |
| 639 |
Instruction* merge_inst = loop->GetHeaderBlock()->GetLoopMergeInst(); |
| 640 |
merge_inst->SetInOperand(1, {basic_block->id()}); |
| 641 |
context_->UpdateDefUse(merge_inst); |
| 642 |
} |
| 643 |
|
| 644 |
state_.new_continue_block = basic_block; |
| 645 |
} |
| 646 |
|
| 647 |
// If this is the header block we are copying. |
| 648 |
if (itr == loop->GetHeaderBlock()) { |
| 649 |
state_.new_header_block = basic_block; |
| 650 |
|
| 651 |
if (!preserve_instructions) { |
| 652 |
// Remove the loop merge instruction if it exists. |
| 653 |
Instruction* merge_inst = basic_block->GetLoopMergeInst(); |
| 654 |
if (merge_inst) invalidated_instructions_.push_back(merge_inst); |
| 655 |
} |
| 656 |
} |
| 657 |
|
| 658 |
// If this is the latch block being copied, record it in the state. |
| 659 |
if (itr == loop->GetLatchBlock()) state_.new_latch_block = basic_block; |
| 660 |
|
| 661 |
// If this is the condition block we are copying. |
| 662 |
if (itr == loop_condition_block_) { |
| 663 |
state_.new_condition_block = basic_block; |
| 664 |
} |
| 665 |
|
| 666 |
// Add this block to the list of blocks to add to the function at the end of |
| 667 |
// the unrolling process. |
| 668 |
blocks_to_add_.push_back(std::unique_ptr<BasicBlock>(basic_block)); |
| 669 |
|
| 670 |
// Keep tracking the old block via a map. |
| 671 |
state_.new_blocks[itr->id()] = basic_block; |
| 672 |
} |
| 673 |
|
| 674 |
void LoopUnrollerUtilsImpl::CopyBody(Loop* loop, bool eliminate_conditions) { |
| 675 |
// Copy each basic block in the loop, give them new ids, and save state |
| 676 |
// information. |
| 677 |
for (const BasicBlock* itr : loop_blocks_inorder_) { |
| 678 |
CopyBasicBlock(loop, itr, false); |
| 679 |
} |
| 680 |
|
| 681 |
// Set the previous latch block to point to the new header. |
| 682 |
Instruction* latch_branch = state_.previous_latch_block_->terminator(); |
| 683 |
latch_branch->SetInOperand(0, {state_.new_header_block->id()}); |
| 684 |
context_->UpdateDefUse(latch_branch); |
| 685 |
|
| 686 |
// As the algorithm copies the original loop blocks exactly, the tail of the |
| 687 |
// latch block on iterations after the first one will be a branch to the new |
| 688 |
// header and not the actual loop header. The last continue block in the loop |
| 689 |
// should always be a backedge to the global header. |
| 690 |
Instruction* new_latch_branch = state_.new_latch_block->terminator(); |
| 691 |
new_latch_branch->SetInOperand(0, {loop->GetHeaderBlock()->id()}); |
| 692 |
context_->AnalyzeUses(new_latch_branch); |
| 693 |
|
| 694 |
std::vector<Instruction*> inductions; |
| 695 |
loop->GetInductionVariables(inductions); |
| 696 |
for (size_t index = 0; index < inductions.size(); ++index) { |
| 697 |
Instruction* primary_copy = inductions[index]; |
| 698 |
|
| 699 |
assert(primary_copy->result_id() != 0); |
| 700 |
Instruction* induction_clone = |
| 701 |
state_.ids_to_new_inst[state_.new_inst[primary_copy->result_id()]]; |
| 702 |
|
| 703 |
state_.new_phis_.push_back(induction_clone); |
| 704 |
assert(induction_clone->result_id() != 0); |
| 705 |
|
| 706 |
if (!state_.previous_phis_.empty()) { |
| 707 |
state_.new_inst[primary_copy->result_id()] = GetPhiDefID( |
| 708 |
state_.previous_phis_[index], state_.previous_latch_block_->id()); |
| 709 |
} else { |
| 710 |
// Do not replace the first phi block ids. |
| 711 |
state_.new_inst[primary_copy->result_id()] = primary_copy->result_id(); |
| 712 |
} |
| 713 |
} |
| 714 |
|
| 715 |
if (eliminate_conditions && |
| 716 |
state_.new_condition_block != loop_condition_block_) { |
| 717 |
FoldConditionBlock(state_.new_condition_block, 1); |
| 718 |
} |
| 719 |
|
| 720 |
// Only reference to the header block is the backedge in the latch block, |
| 721 |
// don't change this. |
| 722 |
state_.new_inst[loop->GetHeaderBlock()->id()] = loop->GetHeaderBlock()->id(); |
| 723 |
|
| 724 |
for (auto& pair : state_.new_blocks) { |
| 725 |
RemapOperands(pair.second); |
| 726 |
} |
| 727 |
|
| 728 |
for (Instruction* dead_phi : state_.new_phis_) |
| 729 |
invalidated_instructions_.push_back(dead_phi); |
| 730 |
|
| 731 |
// Swap the state so the new is now the previous. |
| 732 |
state_.NextIterationState(); |
| 733 |
} |
| 734 |
|
| 735 |
uint32_t LoopUnrollerUtilsImpl::GetPhiDefID(const Instruction* phi, |
| 736 |
uint32_t label) const { |
| 737 |
for (uint32_t operand = 3; operand < phi->NumOperands(); operand += 2) { |
| 738 |
if (phi->GetSingleWordOperand(operand) == label) { |
| 739 |
return phi->GetSingleWordOperand(operand - 1); |
| 740 |
} |
| 741 |
} |
| 742 |
assert(false && "Could not find a phi index matching the provided label"); |
| 743 |
return 0; |
| 744 |
} |
| 745 |
|
| 746 |
void LoopUnrollerUtilsImpl::FoldConditionBlock(BasicBlock* condition_block, |
| 747 |
uint32_t operand_label) { |
| 748 |
// Remove the old conditional branch to the merge and continue blocks. |
| 749 |
Instruction& old_branch = *condition_block->tail(); |
| 750 |
uint32_t new_target = old_branch.GetSingleWordOperand(operand_label); |
| 751 |
|
| 752 |
DebugScope scope = old_branch.GetDebugScope(); |
| 753 |
const std::vector<Instruction> lines = old_branch.dbg_line_insts(); |
| 754 |
|
| 755 |
context_->KillInst(&old_branch); |
| 756 |
// Add the new unconditional branch to the merge block. |
| 757 |
InstructionBuilder builder( |
| 758 |
context_, condition_block, |
| 759 |
IRContext::Analysis::kAnalysisDefUse | |
| 760 |
IRContext::Analysis::kAnalysisInstrToBlockMapping); |
| 761 |
Instruction* new_branch = builder.AddBranch(new_target); |
| 762 |
|
| 763 |
new_branch->set_dbg_line_insts(lines); |
| 764 |
new_branch->SetDebugScope(scope); |
| 765 |
} |
| 766 |
|
| 767 |
void LoopUnrollerUtilsImpl::CloseUnrolledLoop(Loop* loop) { |
| 768 |
// Remove the OpLoopMerge instruction from the function. |
| 769 |
Instruction* merge_inst = loop->GetHeaderBlock()->GetLoopMergeInst(); |
| 770 |
invalidated_instructions_.push_back(merge_inst); |
| 771 |
|
| 772 |
// Remove the final backedge to the header and make it point instead to the |
| 773 |
// merge block. |
| 774 |
Instruction* latch_instruction = state_.previous_latch_block_->terminator(); |
| 775 |
latch_instruction->SetInOperand(0, {loop->GetMergeBlock()->id()}); |
| 776 |
context_->UpdateDefUse(latch_instruction); |
| 777 |
|
| 778 |
// Remove all induction variables as the phis will now be invalid. Replace all |
| 779 |
// uses with the constant initializer value (all uses of phis will be in |
| 780 |
// the first iteration with the subsequent phis already having been removed). |
| 781 |
std::vector<Instruction*> inductions; |
| 782 |
loop->GetInductionVariables(inductions); |
| 783 |
|
| 784 |
// We can use the state instruction mechanism to replace all internal loop |
| 785 |
// values within the first loop trip (as the subsequent ones will be updated |
| 786 |
// by the copy function) with the value coming in from the preheader and then |
| 787 |
// use context ReplaceAllUsesWith for the uses outside the loop with the final |
| 788 |
// trip phi value. |
| 789 |
state_.new_inst.clear(); |
| 790 |
for (Instruction* induction : inductions) { |
| 791 |
uint32_t initalizer_id = |
| 792 |
GetPhiDefID(induction, loop->GetPreHeaderBlock()->id()); |
| 793 |
|
| 794 |
state_.new_inst[induction->result_id()] = initalizer_id; |
| 795 |
} |
| 796 |
|
| 797 |
for (BasicBlock* block : loop_blocks_inorder_) { |
| 798 |
RemapOperands(block); |
| 799 |
} |
| 800 |
|
| 801 |
// Rewrite the last phis, since they may still reference the original phi. |
| 802 |
for (Instruction* last_phi : state_.previous_phis_) { |
| 803 |
RemapOperands(last_phi); |
| 804 |
} |
| 805 |
} |
| 806 |
|
| 807 |
// Uses the first loop to create a copy of the loop with new IDs. |
| 808 |
void LoopUnrollerUtilsImpl::DuplicateLoop(Loop* old_loop, Loop* new_loop) { |
| 809 |
std::vector<BasicBlock*> new_block_order; |
| 810 |
|
| 811 |
// Copy every block in the old loop. |
| 812 |
for (const BasicBlock* itr : loop_blocks_inorder_) { |
| 813 |
CopyBasicBlock(old_loop, itr, true); |
| 814 |
new_block_order.push_back(blocks_to_add_.back().get()); |
| 815 |
} |
| 816 |
|
| 817 |
// Clone the merge block, give it a new id and record it in the state. |
| 818 |
BasicBlock* new_merge = old_loop->GetMergeBlock()->Clone(context_); |
| 819 |
new_merge->SetParent(old_loop->GetMergeBlock()->GetParent()); |
| 820 |
AssignNewResultIds(new_merge); |
| 821 |
state_.new_blocks[old_loop->GetMergeBlock()->id()] = new_merge; |
| 822 |
|
| 823 |
// Remap the operands of every instruction in the loop to point to the new |
| 824 |
// copies. |
| 825 |
for (auto& pair : state_.new_blocks) { |
| 826 |
RemapOperands(pair.second); |
| 827 |
} |
| 828 |
|
| 829 |
loop_blocks_inorder_ = std::move(new_block_order); |
| 830 |
|
| 831 |
AddBlocksToLoop(new_loop); |
| 832 |
|
| 833 |
new_loop->SetHeaderBlock(state_.new_header_block); |
| 834 |
new_loop->SetContinueBlock(state_.new_continue_block); |
| 835 |
new_loop->SetLatchBlock(state_.new_latch_block); |
| 836 |
new_loop->SetMergeBlock(new_merge); |
| 837 |
} |
| 838 |
|
| 839 |
// Whenever the utility copies a block it stores it in a tempory buffer, this |
| 840 |
// function adds the buffer into the Function. The blocks will be inserted |
| 841 |
// after the block |insert_point|. |
| 842 |
void LoopUnrollerUtilsImpl::AddBlocksToFunction( |
| 843 |
const BasicBlock* insert_point) { |
| 844 |
for (auto basic_block_iterator = function_.begin(); |
| 845 |
basic_block_iterator != function_.end(); ++basic_block_iterator) { |
| 846 |
if (basic_block_iterator->id() == insert_point->id()) { |
| 847 |
basic_block_iterator.InsertBefore(&blocks_to_add_); |
| 848 |
return; |
| 849 |
} |
| 850 |
} |
| 851 |
|
| 852 |
assert( |
| 853 |
false && |
| 854 |
"Could not add basic blocks to function as insert point was not found."); |
| 855 |
} |
| 856 |
|
| 857 |
// Assign all result_ids in |basic_block| instructions to new IDs and preserve |
| 858 |
// the mapping of new ids to old ones. |
| 859 |
void LoopUnrollerUtilsImpl::AssignNewResultIds(BasicBlock* basic_block) { |
| 860 |
analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr(); |
| 861 |
|
| 862 |
// Label instructions aren't covered by normal traversal of the |
| 863 |
// instructions. |
| 864 |
// TODO(1841): Handle id overflow. |
| 865 |
uint32_t new_label_id = context_->TakeNextId(); |
| 866 |
|
| 867 |
// Assign a new id to the label. |
| 868 |
state_.new_inst[basic_block->GetLabelInst()->result_id()] = new_label_id; |
| 869 |
basic_block->GetLabelInst()->SetResultId(new_label_id); |
| 870 |
def_use_mgr->AnalyzeInstDefUse(basic_block->GetLabelInst()); |
| 871 |
|
| 872 |
for (Instruction& inst : *basic_block) { |
| 873 |
uint32_t old_id = inst.result_id(); |
| 874 |
|
| 875 |
// Ignore stores etc. |
| 876 |
if (old_id == 0) { |
| 877 |
continue; |
| 878 |
} |
| 879 |
|
| 880 |
// Give the instruction a new id. |
| 881 |
// TODO(1841): Handle id overflow. |
| 882 |
inst.SetResultId(context_->TakeNextId()); |
| 883 |
def_use_mgr->AnalyzeInstDef(&inst); |
| 884 |
|
| 885 |
// Save the mapping of old_id -> new_id. |
| 886 |
state_.new_inst[old_id] = inst.result_id(); |
| 887 |
// Check if this instruction is the induction variable. |
| 888 |
if (loop_induction_variable_->result_id() == old_id) { |
| 889 |
// Save a pointer to the new copy of it. |
| 890 |
state_.new_phi = &inst; |
| 891 |
} |
| 892 |
state_.ids_to_new_inst[inst.result_id()] = &inst; |
| 893 |
} |
| 894 |
} |
| 895 |
|
| 896 |
void LoopUnrollerUtilsImpl::RemapOperands(Instruction* inst) { |
| 897 |
auto remap_operands_to_new_ids = [this](uint32_t* id) { |
| 898 |
auto itr = state_.new_inst.find(*id); |
| 899 |
|
| 900 |
if (itr != state_.new_inst.end()) { |
| 901 |
*id = itr->second; |
| 902 |
} |
| 903 |
}; |
| 904 |
|
| 905 |
inst->ForEachInId(remap_operands_to_new_ids); |
| 906 |
context_->AnalyzeUses(inst); |
| 907 |
} |
| 908 |
|
| 909 |
void LoopUnrollerUtilsImpl::RemapOperands(BasicBlock* basic_block) { |
| 910 |
for (Instruction& inst : *basic_block) { |
| 911 |
RemapOperands(&inst); |
| 912 |
} |
| 913 |
} |
| 914 |
|
| 915 |
// Generate the ordered list of basic blocks in the |loop| and cache it for |
| 916 |
// later use. |
| 917 |
void LoopUnrollerUtilsImpl::ComputeLoopOrderedBlocks(Loop* loop) { |
| 918 |
loop_blocks_inorder_.clear(); |
| 919 |
loop->ComputeLoopStructuredOrder(&loop_blocks_inorder_); |
| 920 |
} |
| 921 |
|
| 922 |
// Adds the blocks_to_add_ to both the loop and to the parent. |
| 923 |
void LoopUnrollerUtilsImpl::AddBlocksToLoop(Loop* loop) const { |
| 924 |
// Add the blocks to this loop. |
| 925 |
for (auto& block_itr : blocks_to_add_) { |
| 926 |
loop->AddBasicBlock(block_itr.get()); |
| 927 |
} |
| 928 |
|
| 929 |
// Add the blocks to the parent as well. |
| 930 |
if (loop->GetParent()) AddBlocksToLoop(loop->GetParent()); |
| 931 |
} |
| 932 |
|
| 933 |
void LoopUnrollerUtilsImpl::LinkLastPhisToStart(Loop* loop) const { |
| 934 |
std::vector<Instruction*> inductions; |
| 935 |
loop->GetInductionVariables(inductions); |
| 936 |
|
| 937 |
for (size_t i = 0; i < inductions.size(); ++i) { |
| 938 |
Instruction* last_phi_in_block = state_.previous_phis_[i]; |
| 939 |
|
| 940 |
uint32_t phi_index = |
| 941 |
GetPhiIndexFromLabel(state_.previous_latch_block_, last_phi_in_block); |
| 942 |
uint32_t phi_variable = |
| 943 |
last_phi_in_block->GetSingleWordInOperand(phi_index - 1); |
| 944 |
uint32_t phi_label = last_phi_in_block->GetSingleWordInOperand(phi_index); |
| 945 |
|
| 946 |
Instruction* phi = inductions[i]; |
| 947 |
phi->SetInOperand(phi_index - 1, {phi_variable}); |
| 948 |
phi->SetInOperand(phi_index, {phi_label}); |
| 949 |
} |
| 950 |
} |
| 951 |
|
| 952 |
// Duplicate the |loop| body |factor| number of times while keeping the loop |
| 953 |
// backedge intact. |
| 954 |
void LoopUnrollerUtilsImpl::PartiallyUnroll(Loop* loop, size_t factor) { |
| 955 |
Unroll(loop, factor); |
| 956 |
LinkLastPhisToStart(loop); |
| 957 |
AddBlocksToLoop(loop); |
| 958 |
AddBlocksToFunction(loop->GetMergeBlock()); |
| 959 |
RemoveDeadInstructions(); |
| 960 |
} |
| 961 |
|
| 962 |
/* |
| 963 |
* End LoopUtilsImpl. |
| 964 |
*/ |
| 965 |
|
| 966 |
} // namespace |
| 967 |
|
| 968 |
/* |
| 969 |
* |
| 970 |
* Begin Utils. |
| 971 |
* |
| 972 |
* */ |
| 973 |
|
| 974 |
bool LoopUtils::CanPerformUnroll() { |
| 975 |
// The loop is expected to be in structured order. |
| 976 |
if (!loop_->GetHeaderBlock()->GetMergeInst()) { |
| 977 |
return false; |
| 978 |
} |
| 979 |
|
| 980 |
// Find check the loop has a condition we can find and evaluate. |
| 981 |
const BasicBlock* condition = loop_->FindConditionBlock(); |
| 982 |
if (!condition) return false; |
| 983 |
|
| 984 |
// Check that we can find and process the induction variable. |
| 985 |
const Instruction* induction = loop_->FindConditionVariable(condition); |
| 986 |
if (!induction || induction->opcode() != SpvOpPhi) return false; |
| 987 |
|
| 988 |
// Check that we can find the number of loop iterations. |
| 989 |
if (!loop_->FindNumberOfIterations(induction, &*condition->ctail(), nullptr)) |
| 990 |
return false; |
| 991 |
|
| 992 |
// Make sure the latch block is a unconditional branch to the header |
| 993 |
// block. |
| 994 |
const Instruction& branch = *loop_->GetLatchBlock()->ctail(); |
| 995 |
bool branching_assumption = |
| 996 |
branch.opcode() == SpvOpBranch && |
| 997 |
branch.GetSingleWordInOperand(0) == loop_->GetHeaderBlock()->id(); |
| 998 |
if (!branching_assumption) { |
| 999 |
return false; |
| 1000 |
} |
| 1001 |
|
| 1002 |
std::vector<Instruction*> inductions; |
| 1003 |
loop_->GetInductionVariables(inductions); |
| 1004 |
|
| 1005 |
// Ban breaks within the loop. |
| 1006 |
const std::vector<uint32_t>& merge_block_preds = |
| 1007 |
context_->cfg()->preds(loop_->GetMergeBlock()->id()); |
| 1008 |
if (merge_block_preds.size() != 1) { |
| 1009 |
return false; |
| 1010 |
} |
| 1011 |
|
| 1012 |
// Ban continues within the loop. |
| 1013 |
const std::vector<uint32_t>& continue_block_preds = |
| 1014 |
context_->cfg()->preds(loop_->GetContinueBlock()->id()); |
| 1015 |
if (continue_block_preds.size() != 1) { |
| 1016 |
return false; |
| 1017 |
} |
| 1018 |
|
| 1019 |
// Ban returns in the loop. |
| 1020 |
// Iterate over all the blocks within the loop and check that none of them |
| 1021 |
// exit the loop. |
| 1022 |
for (uint32_t label_id : loop_->GetBlocks()) { |
| 1023 |
const BasicBlock* block = context_->cfg()->block(label_id); |
| 1024 |
if (block->ctail()->opcode() == SpvOp::SpvOpKill || |
| 1025 |
block->ctail()->opcode() == SpvOp::SpvOpReturn || |
| 1026 |
block->ctail()->opcode() == SpvOp::SpvOpReturnValue || |
| 1027 |
block->ctail()->opcode() == SpvOp::SpvOpTerminateInvocation) { |
| 1028 |
return false; |
| 1029 |
} |
| 1030 |
} |
| 1031 |
// Can only unroll inner loops. |
| 1032 |
if (!loop_->AreAllChildrenMarkedForRemoval()) { |
| 1033 |
return false; |
| 1034 |
} |
| 1035 |
|
| 1036 |
return true; |
| 1037 |
} |
| 1038 |
|
| 1039 |
bool LoopUtils::PartiallyUnroll(size_t factor) { |
| 1040 |
if (factor == 1 || !CanPerformUnroll()) return false; |
| 1041 |
|
| 1042 |
// Create the unroller utility. |
| 1043 |
LoopUnrollerUtilsImpl unroller{context_, |
| 1044 |
loop_->GetHeaderBlock()->GetParent()}; |
| 1045 |
unroller.Init(loop_); |
| 1046 |
|
| 1047 |
// If the unrolling factor is larger than or the same size as the loop just |
| 1048 |
// fully unroll the loop. |
| 1049 |
if (factor >= unroller.GetLoopIterationCount()) { |
| 1050 |
unroller.FullyUnroll(loop_); |
| 1051 |
return true; |
| 1052 |
} |
| 1053 |
|
| 1054 |
// If the loop unrolling factor is an residual number of iterations we need to |
| 1055 |
// let run the loop for the residual part then let it branch into the unrolled |
| 1056 |
// remaining part. We add one when calucating the remainder to take into |
| 1057 |
// account the one iteration already in the loop. |
| 1058 |
if (unroller.GetLoopIterationCount() % factor != 0) { |
| 1059 |
unroller.PartiallyUnrollResidualFactor(loop_, factor); |
| 1060 |
} else { |
| 1061 |
unroller.PartiallyUnroll(loop_, factor); |
| 1062 |
} |
| 1063 |
|
| 1064 |
return true; |
| 1065 |
} |
| 1066 |
|
| 1067 |
bool LoopUtils::FullyUnroll() { |
| 1068 |
if (!CanPerformUnroll()) return false; |
| 1069 |
|
| 1070 |
std::vector<Instruction*> inductions; |
| 1071 |
loop_->GetInductionVariables(inductions); |
| 1072 |
|
| 1073 |
LoopUnrollerUtilsImpl unroller{context_, |
| 1074 |
loop_->GetHeaderBlock()->GetParent()}; |
| 1075 |
|
| 1076 |
unroller.Init(loop_); |
| 1077 |
unroller.FullyUnroll(loop_); |
| 1078 |
|
| 1079 |
return true; |
| 1080 |
} |
| 1081 |
|
| 1082 |
void LoopUtils::Finalize() { |
| 1083 |
// Clean up the loop descriptor to preserve the analysis. |
| 1084 |
|
| 1085 |
LoopDescriptor* LD = context_->GetLoopDescriptor(&function_); |
| 1086 |
LD->PostModificationCleanup(); |
| 1087 |
} |
| 1088 |
|
| 1089 |
/* |
| 1090 |
* |
| 1091 |
* Begin Pass. |
| 1092 |
* |
| 1093 |
*/ |
| 1094 |
|
| 1095 |
Pass::Status LoopUnroller::Process() { |
| 1096 |
bool changed = false; |
| 1097 |
for (Function& f : *context()->module()) { |
| 1098 |
LoopDescriptor* LD = context()->GetLoopDescriptor(&f); |
| 1099 |
for (Loop& loop : *LD) { |
| 1100 |
LoopUtils loop_utils{context(), &loop}; |
| 1101 |
if (!loop.HasUnrollLoopControl() || !loop_utils.CanPerformUnroll()) { |
| 1102 |
continue; |
| 1103 |
} |
| 1104 |
|
| 1105 |
if (fully_unroll_) { |
| 1106 |
loop_utils.FullyUnroll(); |
| 1107 |
} else { |
| 1108 |
loop_utils.PartiallyUnroll(unroll_factor_); |
| 1109 |
} |
| 1110 |
changed = true; |
| 1111 |
} |
| 1112 |
LD->PostModificationCleanup(); |
| 1113 |
} |
| 1114 |
|
| 1115 |
return changed ? Status::SuccessWithChange : Status::SuccessWithoutChange; |
| 1116 |
} |
| 1117 |
|
| 1118 |
} // namespace opt |
| 1119 |
} // namespace spvtools |