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.
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
39 // perform the unrolling. This implements helper methods to copy the loop basic
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
46 // between the loop body copies as each iteration needs information on the last
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.
51 // 4 - If the loop is to be fully unrolled then it is simply closed after step
56 // loop with an even number of bodies with respect to the number of loop
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
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.
70 // Loop control constant value for DontUnroll flag.
73 // Operand index of the loop control parameter of the OpLoopMerge.
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.
80 // preceding step and the original loop.
91   // Initialize from the loop descriptor class.
124   // The induction variable from the immediately preceding loop body.
127   // All the phi nodes from the previous loop iteration.
136   // The previous condition block. This may be folded to flatten the loop.
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);
184   // If partially unrolling the |loop| would leave the loop with too many bodies
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
190   void PartiallyUnrollResidualFactor(Loop* loop, size_t factor);
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
195   void FullyUnroll(Loop* loop);
200   // Close the loop by removing the OpLoopMerge from the |loop| header block and
202   void CloseUnrolledLoop(Loop* loop);
205   // to branch to either exit or continue the loop and replace it with an
215   void DuplicateLoop(Loop* old_loop, Loop* new_loop);
221   // Extracts the initial state information from the |loop|.
222   void Init(Loop* loop);
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);
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);
238   void MarkLoopControlAsDontUnroll(Loop* loop) const;
243   // ids. |loop| is used to identify special loop blocks (header, continue,
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|
262   void CopyBody(Loop* loop, bool eliminate_conditions);
264   // Copy a given |block_to_copy| in the |loop| and record the mapping of the
267   void CopyBasicBlock(Loop* loop, const BasicBlock* block_to_copy,
270   // The actual implementation of the unroll step. Unrolls |loop| by given
273   void Unroll(Loop* loop, size_t factor);
277   void ComputeLoopOrderedBlocks(Loop* loop);
279   // Adds the blocks_to_add_ to both the |loop| and to the parent of |loop| if
281   void AddBlocksToLoop(Loop* loop) const;
287   void LinkLastPhisToStart(Loop* loop) const;
296   // A reference the function the loop is within.
299   // A list of basic blocks to be added to the loop at the end of an unroll
309   // An ordered list containing the loop basic blocks.
316   // The induction variable of the loop.
319   // Phis used in the loop need to be remapped to use the actual result values
323   // The number of loop iterations that the loop would perform pre-unroll.
326   // The amount that the loop steps each iteration.
329   // The value the loop starts stepping from.
350 void LoopUnrollerUtilsImpl::Init(Loop* loop) {  in Init()  argument
351   loop_condition_block_ = loop->FindConditionBlock();  in Init()
353   // When we reinit the second loop during PartiallyUnrollResidualFactor we need  in Init()
355   // basded solution, loop->FindConditionBlock, requires all the nodes to be  in Init()
362   loop_induction_variable_ = loop->FindConditionVariable(loop_condition_block_);  in Init()
365   bool found = loop->FindNumberOfIterations(  in Init()
371   // Blocks are stored in an unordered set of ids in the loop class, we need to  in Init()
373   ComputeLoopOrderedBlocks(loop);  in Init()
376 // This function is used to partially unroll the loop when the factor provided
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
381 void LoopUnrollerUtilsImpl::PartiallyUnrollResidualFactor(Loop* loop,  in PartiallyUnrollResidualFactor()  argument
397   // Duplicate the loop, providing access to the blocks of both loops.  in PartiallyUnrollResidualFactor()
401   std::unique_ptr<Loop> new_loop = MakeUnique<Loop>(*loop);  in PartiallyUnrollResidualFactor()
403   // Clear the basic blocks of the new loop.  in PartiallyUnrollResidualFactor()
406   DuplicateLoop(loop, new_loop.get());  in PartiallyUnrollResidualFactor()
409   AddBlocksToFunction(loop->GetMergeBlock());  in PartiallyUnrollResidualFactor()
412   // Create a new merge block for the first loop.  in PartiallyUnrollResidualFactor()
414   // Make the first loop branch to the second.  in PartiallyUnrollResidualFactor()
419   // Unroll the new loop by the factor with the usual -1 to account for the  in PartiallyUnrollResidualFactor()
432   AddBlocksToFunction(loop->GetMergeBlock());  in PartiallyUnrollResidualFactor()
439   // The loop condition.  in PartiallyUnrollResidualFactor()
445   assert(loop->IsSupportedCondition(condition_check->opcode()));  in PartiallyUnrollResidualFactor()
448   int64_t remainder = Loop::GetResidualConditionValue(  in PartiallyUnrollResidualFactor()
471   // the preheader block. For the duplicated loop we need to update the constant  in PartiallyUnrollResidualFactor()
472   // to be the amount of iterations covered by the first loop and the incoming  in PartiallyUnrollResidualFactor()
478   loop->GetInductionVariables(old_inductions);  in PartiallyUnrollResidualFactor()
482     // Get the index of the loop initalizer, the value coming in from the  in PartiallyUnrollResidualFactor()
487     // Replace the second loop initalizer with the phi from the first  in PartiallyUnrollResidualFactor()
492     // If the use of the first loop induction variable is outside of the loop  in PartiallyUnrollResidualFactor()
493     // then replace that use with the second loop induction variable.  in PartiallyUnrollResidualFactor()
495     auto replace_use_outside_of_loop = [loop, second_loop_induction](  in PartiallyUnrollResidualFactor()
498       if (!loop->IsInsideLoop(user)) {  in PartiallyUnrollResidualFactor()
510   context_->ReplaceAllUsesWith(loop->GetMergeBlock()->id(), new_merge_id);  in PartiallyUnrollResidualFactor()
514   loop_descriptor.AddLoop(std::move(new_loop), loop->GetParent());  in PartiallyUnrollResidualFactor()
519 // Mark this loop as DontUnroll as it will already be unrolled and it may not
520 // be safe to unroll a previously partially unrolled loop.
521 void LoopUnrollerUtilsImpl::MarkLoopControlAsDontUnroll(Loop* loop) const {  in MarkLoopControlAsDontUnroll()
522   Instruction* loop_merge_inst = loop->GetHeaderBlock()->GetLoopMergeInst();  in MarkLoopControlAsDontUnroll()
524          "Loop merge instruction could not be found after entering unroller "  in MarkLoopControlAsDontUnroll()
530 // Duplicate the |loop| body |factor| - 1 number of times while keeping the loop
531 // backedge intact. This will leave the loop with |factor| number of bodies
533 void LoopUnrollerUtilsImpl::Unroll(Loop* loop, size_t factor) {  in Unroll()  argument
534   // If we unroll a loop partially it will not be safe to unroll it further.  in Unroll()
535   // This is due to the current method of calculating the number of loop  in Unroll()
537   MarkLoopControlAsDontUnroll(loop);  in Unroll()
540   loop->GetInductionVariables(inductions);  in Unroll()
541   state_ = LoopUnrollState{loop_induction_variable_, loop->GetLatchBlock(),  in Unroll()
544     CopyBody(loop, true);  in Unroll()
555 void LoopUnrollerUtilsImpl::ReplaceInductionUseWithFinalValue(Loop* loop) {  in ReplaceInductionUseWithFinalValue()  argument
562   loop->GetInductionVariables(inductions);  in ReplaceInductionUseWithFinalValue()
572 // Fully unroll the loop by partially unrolling it by the number of loop
574 void LoopUnrollerUtilsImpl::FullyUnroll(Loop* loop) {  in FullyUnroll()  argument
575   // We unroll the loop by number of iterations in the loop.  in FullyUnroll()
576   Unroll(loop, number_of_loop_iterations_);  in FullyUnroll()
582   CloseUnrolledLoop(loop);  in FullyUnroll()
584   // Mark the loop for later deletion. This allows us to preserve the loop  in FullyUnroll()
586   loop->MarkLoopForRemoval();  in FullyUnroll()
588   // If the loop has a parent add the new blocks to the parent.  in FullyUnroll()
589   if (loop->GetParent()) {  in FullyUnroll()
590     AddBlocksToLoop(loop->GetParent());  in FullyUnroll()
594   AddBlocksToFunction(loop->GetMergeBlock());  in FullyUnroll()
596   ReplaceInductionUseWithFinalValue(loop);  in FullyUnroll()
608   // to kill them after the loop.  in KillDebugDeclares()
623 void LoopUnrollerUtilsImpl::CopyBasicBlock(Loop* loop, const BasicBlock* itr,  in CopyBasicBlock()  argument
637   if (itr == loop->GetContinueBlock()) {  in CopyBasicBlock()
640       Instruction* merge_inst = loop->GetHeaderBlock()->GetLoopMergeInst();  in CopyBasicBlock()
649   if (itr == loop->GetHeaderBlock()) {  in CopyBasicBlock()
653       // Remove the loop merge instruction if it exists.  in CopyBasicBlock()
660   if (itr == loop->GetLatchBlock()) state_.new_latch_block = basic_block;  in CopyBasicBlock()
675 void LoopUnrollerUtilsImpl::CopyBody(Loop* loop, bool eliminate_conditions) {  in CopyBody()  argument
676   // Copy each basic block in the loop, give them new ids, and save state  in CopyBody()
679     CopyBasicBlock(loop, itr, false);  in CopyBody()
687   // As the algorithm copies the original loop blocks exactly, the tail of the  in CopyBody()
689   // header and not the actual loop header. The last continue block in the loop  in CopyBody()
692   new_latch_branch->SetInOperand(0, {loop->GetHeaderBlock()->id()});  in CopyBody()
696   loop->GetInductionVariables(inductions);  in CopyBody()
723   state_.new_inst[loop->GetHeaderBlock()->id()] = loop->GetHeaderBlock()->id();  in CopyBody()
768 void LoopUnrollerUtilsImpl::CloseUnrolledLoop(Loop* loop) {  in CloseUnrolledLoop()  argument
770   Instruction* merge_inst = loop->GetHeaderBlock()->GetLoopMergeInst();  in CloseUnrolledLoop()
776   latch_instruction->SetInOperand(0, {loop->GetMergeBlock()->id()});  in CloseUnrolledLoop()
783   loop->GetInductionVariables(inductions);  in CloseUnrolledLoop()
785   // We can use the state instruction mechanism to replace all internal loop  in CloseUnrolledLoop()
786   // values within the first loop trip (as the subsequent ones will be updated  in CloseUnrolledLoop()
788   // use context ReplaceAllUsesWith for the uses outside the loop with the final  in CloseUnrolledLoop()
793         GetPhiDefID(induction, loop->GetPreHeaderBlock()->id());  in CloseUnrolledLoop()
811 // Uses the first loop to create a copy of the loop with new IDs.
812 void LoopUnrollerUtilsImpl::DuplicateLoop(Loop* old_loop, Loop* new_loop) {  in DuplicateLoop()
815   // Copy every block in the old loop.  in DuplicateLoop()
827   // Remap the operands of every instruction in the loop to point to the new  in DuplicateLoop()
923 // Generate the ordered list of basic blocks in the |loop| and cache it for
925 void LoopUnrollerUtilsImpl::ComputeLoopOrderedBlocks(Loop* loop) {  in ComputeLoopOrderedBlocks()  argument
927   loop->ComputeLoopStructuredOrder(&loop_blocks_inorder_);  in ComputeLoopOrderedBlocks()
930 // Adds the blocks_to_add_ to both the loop and to the parent.
931 void LoopUnrollerUtilsImpl::AddBlocksToLoop(Loop* loop) const {  in AddBlocksToLoop()
932   // Add the blocks to this loop.  in AddBlocksToLoop()
934     loop->AddBasicBlock(block_itr.get());  in AddBlocksToLoop()
938   if (loop->GetParent()) AddBlocksToLoop(loop->GetParent());  in AddBlocksToLoop()
941 void LoopUnrollerUtilsImpl::LinkLastPhisToStart(Loop* loop) const {  in LinkLastPhisToStart()
943   loop->GetInductionVariables(inductions);  in LinkLastPhisToStart()
960 // Duplicate the |loop| body |factor| number of times while keeping the loop
962 void LoopUnrollerUtilsImpl::PartiallyUnroll(Loop* loop, size_t factor) {  in PartiallyUnroll()  argument
963   Unroll(loop, factor);  in PartiallyUnroll()
964   LinkLastPhisToStart(loop);  in PartiallyUnroll()
965   AddBlocksToLoop(loop);  in PartiallyUnroll()
966   AddBlocksToFunction(loop->GetMergeBlock());  in PartiallyUnroll()
983   // The loop is expected to be in structured order.  in CanPerformUnroll()
988   // Find check the loop has a condition we can find and evaluate.  in CanPerformUnroll()
996   // Check that we can find the number of loop iterations.  in CanPerformUnroll()
1001   // ClusterFuzz/OSS-Fuzz is likely to yield examples with very high loop  in CanPerformUnroll()
1003   // are not classed as bugs. To avoid this noise, loop unrolling is not applied  in CanPerformUnroll()
1027   // Ban breaks within the loop.  in CanPerformUnroll()
1034   // Ban continues within the loop.  in CanPerformUnroll()
1041   // Ban returns in the loop.  in CanPerformUnroll()
1042   // Iterate over all the blocks within the loop and check that none of them  in CanPerformUnroll()
1043   // exit the loop.  in CanPerformUnroll()
1069   // If the unrolling factor is larger than or the same size as the loop just  in PartiallyUnroll()
1070   // fully unroll the loop.  in PartiallyUnroll()
1076   // If the loop unrolling factor is an residual number of iterations we need to  in PartiallyUnroll()
1077   // let run the loop for the residual part then let it branch into the unrolled  in PartiallyUnroll()
1079   // account the one iteration already in the loop.  in PartiallyUnroll()
1105   // Clean up the loop descriptor to preserve the analysis.  in Finalize()
1125     for (Loop& loop : *LD) {  in Process()
1126       LoopUtils loop_utils{context(), &loop};  in Process()
1127       if (!loop.HasUnrollLoopControl() || !loop_utils.CanPerformUnroll()) {  in Process()