26 // Implements loop util unrolling functionality for fully and partially
27 // unrolling loops. Given a factor it will duplicate the loop that many times,
28 // appending each one to the end of the old loop and removing backedges, to
29 // create a new unrolled loop.
32 // loop they wish to unroll. LoopUtils::CanPerformUnroll is used to
33 // validate that a given loop can be unrolled. That method (along with the
34 // constructor of loop) checks that the IR is in the expected canonicalised
38 // perform the unrolling. This implements helper methods to copy the loop basic
42 // actually performs the loop duplication. It does this by creating a
43 // LoopUnrollState object and then copying the loop as given by the factor
45 // between the loop body copies as each iteration needs information on the last
47 // the main loop header, and change the previous continue block to point to the
48 // new header and the new continue block to the main loop header.
50 // 4 - If the loop is to be fully unrolled then it is simply closed after step
55 // loop with an even number of bodies with respect to the number of loop
57 // duplicate the loop completely and unroll the duplicated loop to cover the
58 // residual part and adjust the first loop to cover only the "even" part. For
59 // instance if you request an unroll factor of 3 on a loop with 10 iterations
61 // loop
62 // where the loop still iterates over each 4 times. So we make two loops one
63 // iterating once then a second loop of three iterating 3 times.
69 // Loop control constant value for DontUnroll flag.
72 // Operand index of the loop control parameter of the OpLoopMerge.
76 // loop unrolls. Specifically it maintains key blocks and the induction variable
77 // in the current loop duplication step and the blocks from the previous one.
79 // preceding step and the original loop.
90   // Initialize from the loop descriptor class.
123   // The induction variable from the immediately preceding loop body.
126   // All the phi nodes from the previous loop iteration.
135   // The previous condition block. This may be folded to flatten the loop.
179   // Unroll the |loop| by given |factor| by copying the whole body |factor|
180   // times. The resulting basicblock structure will remain a loop.
181   void PartiallyUnroll(Loop*, size_t factor);
183   // If partially unrolling the |loop| would leave the loop with too many bodies
185   // will duplicate the |loop| completely, making the duplicated loop the
186   // successor of the original's merge block. The original loop will have its
187   // condition changed to loop over the residual part and the duplicate will be
189   void PartiallyUnrollResidualFactor(Loop* loop, size_t factor);
191   // Fully unroll the |loop| by copying the full body by the total number of
192   // loop iterations, folding all conditions, and removing the backedge from the
194   void FullyUnroll(Loop* loop);
199   // Close the loop by removing the OpLoopMerge from the |loop| header block and
201   void CloseUnrolledLoop(Loop* loop);
204   // to branch to either exit or continue the loop and replace it with an
214   void DuplicateLoop(Loop* old_loop, Loop* new_loop);
220   // Extracts the initial state information from the |loop|.
221   void Init(Loop* loop);
223   // Replace the uses of each induction variable outside the loop with the final
224   // value of the induction variable before the loop exit. To reflect the proper
225   // state of a fully unrolled loop.
226   void ReplaceInductionUseWithFinalValue(Loop* loop);
231   // Replace any use of induction variables outwith the loop with the final
232   // value of the induction variable in the unrolled loop.
233   void ReplaceOutsideLoopUseWithFinalValue(Loop* loop);
237   void MarkLoopControlAsDontUnroll(Loop* loop) const;
242   // ids. |loop| is used to identify special loop blocks (header, continue,
256   // Copy the whole body of the loop, all blocks dominated by the |loop| header
257   // and not dominated by the |loop| merge. The copied body will be linked to by
258   // the old |loop| continue block and the new body will link to the |loop|
261   void CopyBody(Loop* loop, bool eliminate_conditions);
263   // Copy a given |block_to_copy| in the |loop| and record the mapping of the
266   void CopyBasicBlock(Loop* loop, const BasicBlock* block_to_copy,
269   // The actual implementation of the unroll step. Unrolls |loop| by given
272   void Unroll(Loop* loop, size_t factor);
276   void ComputeLoopOrderedBlocks(Loop* loop);
278   // Adds the blocks_to_add_ to both the |loop| and to the parent of |loop| if
280   void AddBlocksToLoop(Loop* loop) const;
286   void LinkLastPhisToStart(Loop* loop) const;
295   // A reference the function the loop is within.
298   // A list of basic blocks to be added to the loop at the end of an unroll
308   // An ordered list containing the loop basic blocks.
315   // The induction variable of the loop.
318   // Phis used in the loop need to be remapped to use the actual result values
322   // The number of loop iterations that the loop would perform pre-unroll.
325   // The amount that the loop steps each iteration.
328   // The value the loop starts stepping from.
348 void LoopUnrollerUtilsImpl::Init(Loop* loop) {  in Init()  argument
349   loop_condition_block_ = loop->FindConditionBlock();  in Init()
351   // When we reinit the second loop during PartiallyUnrollResidualFactor we need  in Init()
353   // basded solution, loop->FindConditionBlock, requires all the nodes to be  in Init()
360   loop_induction_variable_ = loop->FindConditionVariable(loop_condition_block_);  in Init()
363   bool found = loop->FindNumberOfIterations(  in Init()
369   // Blocks are stored in an unordered set of ids in the loop class, we need to  in Init()
371   ComputeLoopOrderedBlocks(loop);  in Init()
374 // This function is used to partially unroll the loop when the factor provided
376 // loop it creates two loops and unrolls one and adjusts the condition on the
377 // other. The end result being that the new loop pair iterates over the correct
379 void LoopUnrollerUtilsImpl::PartiallyUnrollResidualFactor(Loop* loop,  in PartiallyUnrollResidualFactor()  argument
395   // Duplicate the loop, providing access to the blocks of both loops.  in PartiallyUnrollResidualFactor()
399   std::unique_ptr<Loop> new_loop = MakeUnique<Loop>(*loop);  in PartiallyUnrollResidualFactor()
401   // Clear the basic blocks of the new loop.  in PartiallyUnrollResidualFactor()
404   DuplicateLoop(loop, new_loop.get());  in PartiallyUnrollResidualFactor()
407   AddBlocksToFunction(loop->GetMergeBlock());  in PartiallyUnrollResidualFactor()
410   // Create a new merge block for the first loop.  in PartiallyUnrollResidualFactor()
412   // Make the first loop branch to the second.  in PartiallyUnrollResidualFactor()
417   // Unroll the new loop by the factor with the usual -1 to account for the  in PartiallyUnrollResidualFactor()
430   AddBlocksToFunction(loop->GetMergeBlock());  in PartiallyUnrollResidualFactor()
437   // The loop condition.  in PartiallyUnrollResidualFactor()
443   assert(loop->IsSupportedCondition(condition_check->opcode()));  in PartiallyUnrollResidualFactor()
446   int64_t remainder = Loop::GetResidualConditionValue(  in PartiallyUnrollResidualFactor()
469   // the preheader block. For the duplicated loop we need to update the constant  in PartiallyUnrollResidualFactor()
470   // to be the amount of iterations covered by the first loop and the incoming  in PartiallyUnrollResidualFactor()
476   loop->GetInductionVariables(old_inductions);  in PartiallyUnrollResidualFactor()
480     // Get the index of the loop initalizer, the value coming in from the  in PartiallyUnrollResidualFactor()
485     // Replace the second loop initalizer with the phi from the first  in PartiallyUnrollResidualFactor()
490     // If the use of the first loop induction variable is outside of the loop  in PartiallyUnrollResidualFactor()
491     // then replace that use with the second loop induction variable.  in PartiallyUnrollResidualFactor()
493     auto replace_use_outside_of_loop = [loop, second_loop_induction](  in PartiallyUnrollResidualFactor()
496       if (!loop->IsInsideLoop(user)) {  in PartiallyUnrollResidualFactor()
508   context_->ReplaceAllUsesWith(loop->GetMergeBlock()->id(), new_merge_id);  in PartiallyUnrollResidualFactor()
512   loop_descriptor.AddLoop(std::move(new_loop), loop->GetParent());  in PartiallyUnrollResidualFactor()
517 // Mark this loop as DontUnroll as it will already be unrolled and it may not
518 // be safe to unroll a previously partially unrolled loop.
519 void LoopUnrollerUtilsImpl::MarkLoopControlAsDontUnroll(Loop* loop) const {  in MarkLoopControlAsDontUnroll()
520   Instruction* loop_merge_inst = loop->GetHeaderBlock()->GetLoopMergeInst();  in MarkLoopControlAsDontUnroll()
522          "Loop merge instruction could not be found after entering unroller "  in MarkLoopControlAsDontUnroll()
528 // Duplicate the |loop| body |factor| - 1 number of times while keeping the loop
529 // backedge intact. This will leave the loop with |factor| number of bodies
531 void LoopUnrollerUtilsImpl::Unroll(Loop* loop, size_t factor) {  in Unroll()  argument
532   // If we unroll a loop partially it will not be safe to unroll it further.  in Unroll()
533   // This is due to the current method of calculating the number of loop  in Unroll()
535   MarkLoopControlAsDontUnroll(loop);  in Unroll()
538   loop->GetInductionVariables(inductions);  in Unroll()
539   state_ = LoopUnrollState{loop_induction_variable_, loop->GetLatchBlock(),  in Unroll()
542     CopyBody(loop, true);  in Unroll()
553 void LoopUnrollerUtilsImpl::ReplaceInductionUseWithFinalValue(Loop* loop) {  in ReplaceInductionUseWithFinalValue()  argument
560   loop->GetInductionVariables(inductions);  in ReplaceInductionUseWithFinalValue()
570 // Fully unroll the loop by partially unrolling it by the number of loop
572 void LoopUnrollerUtilsImpl::FullyUnroll(Loop* loop) {  in FullyUnroll()  argument
573   // We unroll the loop by number of iterations in the loop.  in FullyUnroll()
574   Unroll(loop, number_of_loop_iterations_);  in FullyUnroll()
580   CloseUnrolledLoop(loop);  in FullyUnroll()
582   // Mark the loop for later deletion. This allows us to preserve the loop  in FullyUnroll()
584   loop->MarkLoopForRemoval();  in FullyUnroll()
586   // If the loop has a parent add the new blocks to the parent.  in FullyUnroll()
587   if (loop->GetParent()) {  in FullyUnroll()
588     AddBlocksToLoop(loop->GetParent());  in FullyUnroll()
592   AddBlocksToFunction(loop->GetMergeBlock());  in FullyUnroll()
594   ReplaceInductionUseWithFinalValue(loop);  in FullyUnroll()
606   // to kill them after the loop.  in KillDebugDeclares()
621 void LoopUnrollerUtilsImpl::CopyBasicBlock(Loop* loop, const BasicBlock* itr,  in CopyBasicBlock()  argument
635   if (itr == loop->GetContinueBlock()) {  in CopyBasicBlock()
638       Instruction* merge_inst = loop->GetHeaderBlock()->GetLoopMergeInst();  in CopyBasicBlock()
647   if (itr == loop->GetHeaderBlock()) {  in CopyBasicBlock()
651       // Remove the loop merge instruction if it exists.  in CopyBasicBlock()
658   if (itr == loop->GetLatchBlock()) state_.new_latch_block = basic_block;  in CopyBasicBlock()
673 void LoopUnrollerUtilsImpl::CopyBody(Loop* loop, bool eliminate_conditions) {  in CopyBody()  argument
674   // Copy each basic block in the loop, give them new ids, and save state  in CopyBody()
677     CopyBasicBlock(loop, itr, false);  in CopyBody()
685   // As the algorithm copies the original loop blocks exactly, the tail of the  in CopyBody()
687   // header and not the actual loop header. The last continue block in the loop  in CopyBody()
690   new_latch_branch->SetInOperand(0, {loop->GetHeaderBlock()->id()});  in CopyBody()
694   loop->GetInductionVariables(inductions);  in CopyBody()
721   state_.new_inst[loop->GetHeaderBlock()->id()] = loop->GetHeaderBlock()->id();  in CopyBody()
766 void LoopUnrollerUtilsImpl::CloseUnrolledLoop(Loop* loop) {  in CloseUnrolledLoop()  argument
768   Instruction* merge_inst = loop->GetHeaderBlock()->GetLoopMergeInst();  in CloseUnrolledLoop()
774   latch_instruction->SetInOperand(0, {loop->GetMergeBlock()->id()});  in CloseUnrolledLoop()
781   loop->GetInductionVariables(inductions);  in CloseUnrolledLoop()
783   // We can use the state instruction mechanism to replace all internal loop  in CloseUnrolledLoop()
784   // values within the first loop trip (as the subsequent ones will be updated  in CloseUnrolledLoop()
786   // use context ReplaceAllUsesWith for the uses outside the loop with the final  in CloseUnrolledLoop()
791         GetPhiDefID(induction, loop->GetPreHeaderBlock()->id());  in CloseUnrolledLoop()
809 // Uses the first loop to create a copy of the loop with new IDs.
810 void LoopUnrollerUtilsImpl::DuplicateLoop(Loop* old_loop, Loop* new_loop) {  in DuplicateLoop()
813   // Copy every block in the old loop.  in DuplicateLoop()
825   // Remap the operands of every instruction in the loop to point to the new  in DuplicateLoop()
921 // Generate the ordered list of basic blocks in the |loop| and cache it for
923 void LoopUnrollerUtilsImpl::ComputeLoopOrderedBlocks(Loop* loop) {  in ComputeLoopOrderedBlocks()  argument
925   loop->ComputeLoopStructuredOrder(&loop_blocks_inorder_);  in ComputeLoopOrderedBlocks()
928 // Adds the blocks_to_add_ to both the loop and to the parent.
929 void LoopUnrollerUtilsImpl::AddBlocksToLoop(Loop* loop) const {  in AddBlocksToLoop()
930   // Add the blocks to this loop.  in AddBlocksToLoop()
932     loop->AddBasicBlock(block_itr.get());  in AddBlocksToLoop()
936   if (loop->GetParent()) AddBlocksToLoop(loop->GetParent());  in AddBlocksToLoop()
939 void LoopUnrollerUtilsImpl::LinkLastPhisToStart(Loop* loop) const {  in LinkLastPhisToStart()
941   loop->GetInductionVariables(inductions);  in LinkLastPhisToStart()
958 // Duplicate the |loop| body |factor| number of times while keeping the loop
960 void LoopUnrollerUtilsImpl::PartiallyUnroll(Loop* loop, size_t factor) {  in PartiallyUnroll()  argument
961   Unroll(loop, factor);  in PartiallyUnroll()
962   LinkLastPhisToStart(loop);  in PartiallyUnroll()
963   AddBlocksToLoop(loop);  in PartiallyUnroll()
964   AddBlocksToFunction(loop->GetMergeBlock());  in PartiallyUnroll()
981   // The loop is expected to be in structured order.  in CanPerformUnroll()
986   // Find check the loop has a condition we can find and evaluate.  in CanPerformUnroll()
994   // Check that we can find the number of loop iterations.  in CanPerformUnroll()
999   // ClusterFuzz/OSS-Fuzz is likely to yield examples with very high loop  in CanPerformUnroll()
1001   // are not classed as bugs. To avoid this noise, loop unrolling is not applied  in CanPerformUnroll()
1025   // Ban breaks within the loop.  in CanPerformUnroll()
1032   // Ban continues within the loop.  in CanPerformUnroll()
1039   // Ban returns in the loop.  in CanPerformUnroll()
1040   // Iterate over all the blocks within the loop and check that none of them  in CanPerformUnroll()
1041   // exit the loop.  in CanPerformUnroll()
1067   // If the unrolling factor is larger than or the same size as the loop just  in PartiallyUnroll()
1068   // fully unroll the loop.  in PartiallyUnroll()
1074   // If the loop unrolling factor is an residual number of iterations we need to  in PartiallyUnroll()
1075   // let run the loop for the residual part then let it branch into the unrolled  in PartiallyUnroll()
1077   // account the one iteration already in the loop.  in PartiallyUnroll()
1103   // Clean up the loop descriptor to preserve the analysis.  in Finalize()
1123     for (Loop& loop : *LD) {  in Process()
1124       LoopUtils loop_utils{context(), &loop};  in Process()
1125       if (!loop.HasUnrollLoopControl() || !loop_utils.CanPerformUnroll()) {  in Process()