This is an archive of the discontinued LLVM Phabricator instance.

[LoopUnrollAndJam] Do not allows loops which have no exit(ing) blocks or multiple exit(ing) blocks
ClosedPublic

Authored by sidbav on Feb 1 2021, 11:14 AM.

Details

Summary

This resolves an issue posted on Bugzilla. https://bugs.llvm.org/show_bug.cgi?id=48764

This issue took place because loops which did not have an exit block were allowed to unrolled and jam.

This patch ensures that loops which only have an exit block will be allowed to be unrolled and jammed.

Update:
The loop had multiple exit blocks, which resulted in the function getExitBlock to return a nullptr.
This patch ensures that loops which only have one exit block as allowed to be unrolled and jammed.

Diff Detail

Event Timeline

sidbav created this revision.Feb 1 2021, 11:14 AM
sidbav requested review of this revision.Feb 1 2021, 11:14 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 1 2021, 11:14 AM

Add a lit test?

Whitney added inline comments.Feb 1 2021, 11:24 AM
llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
818
bool isRotatedForm() const {
  assert(!isInvalid() && "Loop not in a valid state!");
  BasicBlock *Latch = getLoopLatch();
  return Latch && isLoopExiting(Latch);
}

So shouldn't one of latch successor be an exit block?

sidbav updated this revision to Diff 320546.Feb 1 2021, 11:47 AM

Forgot to add testcase

sidbav updated this revision to Diff 320555.Feb 1 2021, 12:05 PM

Minor updates from the previous diff

dmgreen added inline comments.Feb 1 2021, 12:24 PM
llvm/test/Transforms/LoopUnrollAndJam/no_exit_block.ll
1

This test will need REQUIRES: asserts, otherwise it will fail on release (or at least no-assert) builds.

16

You can likely remove the dso_local and maybe the # attributes.

Also maybe this function isn't needed? It could just be a declaration. And it may be possible to simplify h if the problem is an inner infinite loop.

118

This can likely be removed too.

sidbav updated this revision to Diff 320854.Feb 2 2021, 11:02 AM

Update test case as per feedback

sidbav marked 3 inline comments as done.Feb 2 2021, 11:05 AM
sidbav added inline comments.
llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
818

Yeah you are correct. What is strange that when using this specific target triple and data layout, for what ever reason L->getExitBlock() gets set to nullptr, which was the reason that error took place.
I am currently investigating why this takes place for this specific target triple/layout.

sidbav updated this revision to Diff 320913.Feb 2 2021, 2:49 PM
sidbav retitled this revision from [LoopUnrollAndJam] Check if the loops have an Exit Block to [LoopUnrollAndJam] Do not allows loops which have no exit(ing) blocks or multiple exit(ing) blocks.
sidbav edited the summary of this revision. (Show Details)

Update the test case such that it is not specific to a target.

Also, I dug a little deeper into the definition of getExitBlock. This function will return a nullptr if the loop has 2 or more exit blocks, or the loop does not have an exit block. This is why the isLoopExiting(Latch) does not return a nullptr in the function isRotatedForm.
The function getExitingBlock has the same behaviour as getExitBlock

Updated the test case to not allow loops which have multiple exit or exiting blocks.

Whitney added inline comments.Feb 2 2021, 3:50 PM
llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
835

nit: sentence ends with a period.

842

How about:
Only single exiting block is allowed.

843

nit: sentence ends with a period.

llvm/test/Transforms/LoopUnrollAndJam/multiple_exit_blocks.ll
5 ↗(On Diff #320913)

Can you please add a testcase with single exit block, but multiple exiting blocks?

13 ↗(On Diff #320913)

Is this function used?

58 ↗(On Diff #320913)

This is also not used.

sidbav updated this revision to Diff 321148.Feb 3 2021, 10:23 AM

Updates based on feedback

sidbav marked 5 inline comments as done.Feb 3 2021, 10:28 AM
sidbav added inline comments.
llvm/test/Transforms/LoopUnrollAndJam/multiple_exit_blocks.ll
5 ↗(On Diff #320913)

The reason that I have not added this test case is when the a loop has a single exit block with multiple exiting blocks, is before checking if the loops qualify for unrolling and jamming, all of the loops are simplified. This results the loop have multiple exiting and exit blocks, which is essentially the same test case as this one.

Whitney added inline comments.Feb 3 2021, 11:02 AM
llvm/test/Transforms/LoopUnrollAndJam/multiple_exit_blocks.ll
5 ↗(On Diff #320913)

Who is doing the simplification? A loop with a single exit block and multiple exiting blocks can still be considered as in simplified form.

Whitney added inline comments.Feb 3 2021, 11:05 AM
llvm/test/Transforms/LoopUnrollAndJam/multiple_exit_blocks.ll
5 ↗(On Diff #320913)

Now I remember, we did simplifyLoop in tryToUnrollAndJamLoop.

Meinersbur added inline comments.Feb 3 2021, 11:33 AM
llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
842

It is possible for a single exiting block to have multiple outgoing edges (likely with a switch terminator). Do you intend to allow this/is it checked somewhere else already?

sidbav added inline comments.Feb 3 2021, 1:48 PM
llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
842

Yes, this should be allowed (assuming such a loop is following all other unroll and jam requirements) as long as there is only 1 edge going to an exit block. If a loop has multiple exit blocks, this will be caught in the above check.

llvm/test/Transforms/LoopUnrollAndJam/multiple_exit_blocks.ll
5 ↗(On Diff #320913)

Who is doing the simplification? A loop with a single exit block and multiple exiting blocks can still be considered as in simplified form.

Yes that is correct. I have come up with a new test case (in simplified form).

define void @h() {                                                                  
bb:                                                                                 
  store i32 4, i32* @e, align 4                                                     
  %i15 = load i16, i16* @b, align 2                                                 
  %i17 = icmp slt i16 %i15, 1                                                       
  br label %bb8                                                                     
                                                                                    
bb8:                                              ; preds = %bb, %bb47              
  %storemerge15 = phi i32 [ 4, %bb ], [ %i49, %bb47 ]                               
  br i1 %i17, label %bb50, label %bb23

bb23:
  br label %bb24                 
                                                                                    
bb24:                                             ; preds = %bb43, %bb23            
  %storemerge312 = phi i16 [ 0, %bb23 ], [ %i45, %bb43 ]                             
  br label %bb43                                                                    
                                                                                    
bb43:                                             ; preds = %bb24                   
  %i45 = add nuw nsw i16 %storemerge312, 1                                          
  %i13 = icmp ult i16 %storemerge312, 7                                             
  br i1 %i13, label %bb24, label %bb47                                              
                                                                                    
bb47:                                             ; preds = %bb43                   
  %i49 = add nsw i32 %storemerge15, -1                                              
  store i32 %i49, i32* @e, align 4                                                  
  %i7.not = icmp eq i32 %i49, 0                                                     
  br i1 %i7.not, label %bb50, label %bb8                                            
                                                                                    
bb50:                                             ; preds = %bb47                   
  ret void                                                                          
}

Although looking at this we can that bb50 is the exit block, and both bb47 and bb8 the exiting blocks for the loop with header bb8, this test case is still considered to have 2 exit blocks.

Currently the function getExitBlocks(ExitBlocksVector) (defined in llvm/include/llvm/Analysis/LoopInfoImpl.h), which the function getExitBlock() calls, does not check if a basicblock is already added to the vector. It allows for basicblocks to repeated.

In order to consider a test case like this (a single exit block, multiple exiting blocks), we would have to update getExitBlocks(ExitBlocksVector), and any other similar functions, to use a Set.

Meinersbur added inline comments.Feb 3 2021, 6:41 PM
llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
842

The "there is only 1 edge going to an exit block" is exactly what I was wondering. Consider:

header:
  br label %exiting

exiting:
   switch i32 %a, label %header [
      i32 0, label %exit
      i32 1, label %exit
   ]

exit:
  ret void

This loop has one exiting block, one exit block. but two exiting edges. My question is whether this is either handled correctly by UnrollAndJam or if there is something else checking for this.

L->getExitingBlock() does return %exiting in this case, but it looks like L->getExitBlock() returns nullptr for this case (getUniqueExitBlock() would return %exit), so seems I answered my own question.

llvm/test/Transforms/LoopUnrollAndJam/multiple_exit_blocks.ll
5 ↗(On Diff #320913)

Did you have a look at getUniqueExitBlocks()?

As far as I understand, multiple exiting edges are not supported at all, even if pointing to the same exit block, so the use if !getExitBlock() seems correct.

sidbav marked 3 inline comments as done.Feb 4 2021, 8:02 AM
sidbav added inline comments.
llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
842

This is similar test case which I described below (unique exit, but multiple exit edges)... this would not be handled.

llvm/test/Transforms/LoopUnrollAndJam/multiple_exit_blocks.ll
5 ↗(On Diff #320913)

Did you have a look at getUniqueExitBlocks()?

As far as I understand, multiple exiting edges are not supported at all, even if pointing to the same exit block, so the use if !getExitBlock() seems correct.

Yeah I agree, don't think there is a need to change the code to use getUniqueExitBlocks().

sidbav marked 2 inline comments as done.Feb 4 2021, 8:02 AM
Meinersbur accepted this revision.Feb 4 2021, 2:38 PM

LGTM, but please wait a bit to give @Whitney a chance to respond too.

This revision is now accepted and ready to land.Feb 4 2021, 2:38 PM
Whitney accepted this revision.Feb 4 2021, 5:21 PM

minor comment

llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
842

Can you edit the comment to indicate that we intentionally use getExitBlock to disallow multiple exit edges?

sidbav marked an inline comment as done.Feb 5 2021, 8:17 AM
sidbav added inline comments.
llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
842

Added this comment in the committed change.