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;
293   // A reference the function the loop is within.
296   // A list of basic blocks to be added to the loop at the end of an unroll
306   // An ordered list containing the loop basic blocks.
313   // The induction variable of the loop.
316   // Phis used in the loop need to be remapped to use the actual result values
320   // The number of loop iterations that the loop would preform pre-unroll.
323   // The amount that the loop steps each iteration.
326   // The value the loop starts stepping from.
347 void LoopUnrollerUtilsImpl::Init(Loop* loop) {  in Init()  argument
348   loop_condition_block_ = loop->FindConditionBlock();  in Init()
350   // When we reinit the second loop during PartiallyUnrollResidualFactor we need  in Init()
352   // basded solution, loop->FindConditionBlock, requires all the nodes to be  in Init()
359   loop_induction_variable_ = loop->FindConditionVariable(loop_condition_block_);  in Init()
362   bool found = loop->FindNumberOfIterations(  in Init()
368   // Blocks are stored in an unordered set of ids in the loop class, we need to  in Init()
370   ComputeLoopOrderedBlocks(loop);  in Init()
373 // This function is used to partially unroll the loop when the factor provided
375 // loop it creates two loops and unrolls one and adjusts the condition on the
376 // other. The end result being that the new loop pair iterates over the correct
378 void LoopUnrollerUtilsImpl::PartiallyUnrollResidualFactor(Loop* loop,  in PartiallyUnrollResidualFactor()  argument
393   // Duplicate the loop, providing access to the blocks of both loops.  in PartiallyUnrollResidualFactor()
397   Loop* new_loop = new Loop(*loop);  in PartiallyUnrollResidualFactor()
399   // Clear the basic blocks of the new loop.  in PartiallyUnrollResidualFactor()
402   DuplicateLoop(loop, new_loop);  in PartiallyUnrollResidualFactor()
405   AddBlocksToFunction(loop->GetMergeBlock());  in PartiallyUnrollResidualFactor()
408   // Create a new merge block for the first loop.  in PartiallyUnrollResidualFactor()
410   // Make the first loop branch to the second.  in PartiallyUnrollResidualFactor()
415   // Unroll the new loop by the factor with the usual -1 to account for the  in PartiallyUnrollResidualFactor()
428   AddBlocksToFunction(loop->GetMergeBlock());  in PartiallyUnrollResidualFactor()
435   // The loop condition.  in PartiallyUnrollResidualFactor()
441   assert(loop->IsSupportedCondition(condition_check->opcode()));  in PartiallyUnrollResidualFactor()
444   int64_t remainder = Loop::GetResidualConditionValue(  in PartiallyUnrollResidualFactor()
467   // the preheader block. For the duplicated loop we need to update the constant  in PartiallyUnrollResidualFactor()
468   // to be the amount of iterations covered by the first loop and the incoming  in PartiallyUnrollResidualFactor()
474   loop->GetInductionVariables(old_inductions);  in PartiallyUnrollResidualFactor()
478     // Get the index of the loop initalizer, the value coming in from the  in PartiallyUnrollResidualFactor()
483     // Replace the second loop initalizer with the phi from the first  in PartiallyUnrollResidualFactor()
488     // If the use of the first loop induction variable is outside of the loop  in PartiallyUnrollResidualFactor()
489     // then replace that use with the second loop induction variable.  in PartiallyUnrollResidualFactor()
491     auto replace_use_outside_of_loop = [loop, second_loop_induction](  in PartiallyUnrollResidualFactor()
494       if (!loop->IsInsideLoop(user)) {  in PartiallyUnrollResidualFactor()
506   context_->ReplaceAllUsesWith(loop->GetMergeBlock()->id(), new_merge_id);  in PartiallyUnrollResidualFactor()
510   loop_descriptor.AddLoop(new_loop, loop->GetParent());  in PartiallyUnrollResidualFactor()
515 // Mark this loop as DontUnroll as it will already be unrolled and it may not
516 // be safe to unroll a previously partially unrolled loop.
517 void LoopUnrollerUtilsImpl::MarkLoopControlAsDontUnroll(Loop* loop) const {  in MarkLoopControlAsDontUnroll()
518   Instruction* loop_merge_inst = loop->GetHeaderBlock()->GetLoopMergeInst();  in MarkLoopControlAsDontUnroll()
520          "Loop merge instruction could not be found after entering unroller "  in MarkLoopControlAsDontUnroll()
526 // Duplicate the |loop| body |factor| - 1 number of times while keeping the loop
527 // backedge intact. This will leave the loop with |factor| number of bodies
529 void LoopUnrollerUtilsImpl::Unroll(Loop* loop, size_t factor) {  in Unroll()  argument
530   // If we unroll a loop partially it will not be safe to unroll it further.  in Unroll()
531   // This is due to the current method of calculating the number of loop  in Unroll()
533   MarkLoopControlAsDontUnroll(loop);  in Unroll()
536   loop->GetInductionVariables(inductions);  in Unroll()
537   state_ = LoopUnrollState{loop_induction_variable_, loop->GetLatchBlock(),  in Unroll()
540     CopyBody(loop, true);  in Unroll()
551 void LoopUnrollerUtilsImpl::ReplaceInductionUseWithFinalValue(Loop* loop) {  in ReplaceInductionUseWithFinalValue()  argument
558   loop->GetInductionVariables(inductions);  in ReplaceInductionUseWithFinalValue()
568 // Fully unroll the loop by partially unrolling it by the number of loop
570 void LoopUnrollerUtilsImpl::FullyUnroll(Loop* loop) {  in FullyUnroll()  argument
571   // We unroll the loop by number of iterations in the loop.  in FullyUnroll()
572   Unroll(loop, number_of_loop_iterations_);  in FullyUnroll()
578   CloseUnrolledLoop(loop);  in FullyUnroll()
580   // Mark the loop for later deletion. This allows us to preserve the loop  in FullyUnroll()
582   loop->MarkLoopForRemoval();  in FullyUnroll()
584   // If the loop has a parent add the new blocks to the parent.  in FullyUnroll()
585   if (loop->GetParent()) {  in FullyUnroll()
586     AddBlocksToLoop(loop->GetParent());  in FullyUnroll()
590   AddBlocksToFunction(loop->GetMergeBlock());  in FullyUnroll()
592   ReplaceInductionUseWithFinalValue(loop);  in FullyUnroll()
605 void LoopUnrollerUtilsImpl::CopyBasicBlock(Loop* loop, const BasicBlock* itr,  in CopyBasicBlock()  argument
616   if (itr == loop->GetContinueBlock()) {  in CopyBasicBlock()
619       Instruction* merge_inst = loop->GetHeaderBlock()->GetLoopMergeInst();  in CopyBasicBlock()
628   if (itr == loop->GetHeaderBlock()) {  in CopyBasicBlock()
632       // Remove the loop merge instruction if it exists.  in CopyBasicBlock()
639   if (itr == loop->GetLatchBlock()) state_.new_latch_block = basic_block;  in CopyBasicBlock()
654 void LoopUnrollerUtilsImpl::CopyBody(Loop* loop, bool eliminate_conditions) {  in CopyBody()  argument
655   // Copy each basic block in the loop, give them new ids, and save state  in CopyBody()
658     CopyBasicBlock(loop, itr, false);  in CopyBody()
666   // As the algorithm copies the original loop blocks exactly, the tail of the  in CopyBody()
668   // header and not the actual loop header. The last continue block in the loop  in CopyBody()
671   new_latch_branch->SetInOperand(0, {loop->GetHeaderBlock()->id()});  in CopyBody()
675   loop->GetInductionVariables(inductions);  in CopyBody()
702   state_.new_inst[loop->GetHeaderBlock()->id()] = loop->GetHeaderBlock()->id();  in CopyBody()
741 void LoopUnrollerUtilsImpl::CloseUnrolledLoop(Loop* loop) {  in CloseUnrolledLoop()  argument
743   Instruction* merge_inst = loop->GetHeaderBlock()->GetLoopMergeInst();  in CloseUnrolledLoop()
749   latch_instruction->SetInOperand(0, {loop->GetMergeBlock()->id()});  in CloseUnrolledLoop()
756   loop->GetInductionVariables(inductions);  in CloseUnrolledLoop()
758   // We can use the state instruction mechanism to replace all internal loop  in CloseUnrolledLoop()
759   // values within the first loop trip (as the subsequent ones will be updated  in CloseUnrolledLoop()
761   // use context ReplaceAllUsesWith for the uses outside the loop with the final  in CloseUnrolledLoop()
766         GetPhiDefID(induction, loop->GetPreHeaderBlock()->id());  in CloseUnrolledLoop()
781 // Uses the first loop to create a copy of the loop with new IDs.
782 void LoopUnrollerUtilsImpl::DuplicateLoop(Loop* old_loop, Loop* new_loop) {  in DuplicateLoop()
785   // Copy every block in the old loop.  in DuplicateLoop()
797   // Remap the operands of every instruction in the loop to point to the new  in DuplicateLoop()
889 // Generate the ordered list of basic blocks in the |loop| and cache it for
891 void LoopUnrollerUtilsImpl::ComputeLoopOrderedBlocks(Loop* loop) {  in ComputeLoopOrderedBlocks()  argument
893   loop->ComputeLoopStructuredOrder(&loop_blocks_inorder_);  in ComputeLoopOrderedBlocks()
896 // Adds the blocks_to_add_ to both the loop and to the parent.
897 void LoopUnrollerUtilsImpl::AddBlocksToLoop(Loop* loop) const {  in AddBlocksToLoop()
898   // Add the blocks to this loop.  in AddBlocksToLoop()
900     loop->AddBasicBlock(block_itr.get());  in AddBlocksToLoop()
904   if (loop->GetParent()) AddBlocksToLoop(loop->GetParent());  in AddBlocksToLoop()
907 void LoopUnrollerUtilsImpl::LinkLastPhisToStart(Loop* loop) const {  in LinkLastPhisToStart()
909   loop->GetInductionVariables(inductions);  in LinkLastPhisToStart()
926 // Duplicate the |loop| body |factor| number of times while keeping the loop
928 void LoopUnrollerUtilsImpl::PartiallyUnroll(Loop* loop, size_t factor) {  in PartiallyUnroll()  argument
929   Unroll(loop, factor);  in PartiallyUnroll()
930   LinkLastPhisToStart(loop);  in PartiallyUnroll()
931   AddBlocksToLoop(loop);  in PartiallyUnroll()
932   AddBlocksToFunction(loop->GetMergeBlock());  in PartiallyUnroll()
949   // The loop is expected to be in structured order.  in CanPerformUnroll()
954   // Find check the loop has a condition we can find and evaluate.  in CanPerformUnroll()
962   // Check that we can find the number of loop iterations.  in CanPerformUnroll()
979   // Ban breaks within the loop.  in CanPerformUnroll()
986   // Ban continues within the loop.  in CanPerformUnroll()
993   // Ban returns in the loop.  in CanPerformUnroll()
994   // Iterate over all the blocks within the loop and check that none of them  in CanPerformUnroll()
995   // exit the loop.  in CanPerformUnroll()
1020   // If the unrolling factor is larger than or the same size as the loop just  in PartiallyUnroll()
1021   // fully unroll the loop.  in PartiallyUnroll()
1027   // If the loop unrolling factor is an residual number of iterations we need to  in PartiallyUnroll()
1028   // let run the loop for the residual part then let it branch into the unrolled  in PartiallyUnroll()
1030   // account the one iteration already in the loop.  in PartiallyUnroll()
1056   // Clean up the loop descriptor to preserve the analysis.  in Finalize()
1072     for (Loop& loop : *LD) {  in Process()
1073       LoopUtils loop_utils{context(), &loop};  in Process()
1074       if (!loop.HasUnrollLoopControl() || !loop_utils.CanPerformUnroll()) {  in Process()