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

[sidbav]

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.

[Whitney]

Add a lit test?

[Whitney]

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]

Forgot to add testcase

[sidbav]

Minor updates from the previous diff

[dmgreen]

llvm/test/Transforms/LoopUnrollAndJam/no_exit_block.ll

1 ↗

(On Diff #320546)

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

16 ↗

(On Diff #320546)

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 ↗

(On Diff #320546)

This can likely be removed too.

[sidbav]

Update test case as per feedback

[sidbav]

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]

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]

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

6

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

14

Is this function used?

59

This is also not used.

[sidbav]

Updates based on feedback

[sidbav]

llvm/test/Transforms/LoopUnrollAndJam/multiple_exit_blocks.ll

6

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]

llvm/test/Transforms/LoopUnrollAndJam/multiple_exit_blocks.ll

6

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]

llvm/test/Transforms/LoopUnrollAndJam/multiple_exit_blocks.ll

6

Now I remember, we did simplifyLoop in tryToUnrollAndJamLoop.

[Meinersbur]

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]

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

6

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]

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

6

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]

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

6

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().

[Meinersbur]

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

[Whitney]

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]

llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp

842

Added this comment in the committed change.

llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp

if (Root.getSubLoops().size() != 1)
     return false;
 
   const Loop *L = &Root;
   do {
     // All loops in Root need to be in simplify and rotated form.
     if (!L->isLoopSimplifyForm())
       return false;
 
     if (!L->isRotatedForm())
       return false;
 
     if (L->getHeader()->hasAddressTaken()) {
       LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Address taken\n");
       return false;
     }
 
     unsigned SubLoopsSize = L->getSubLoops().size();
     if (SubLoopsSize == 0)
       return true;
 
     // Only one child is allowed.
     if (SubLoopsSize != 1)
       return false;
 
+    // Only loops with a single exit block can be unrolled and jammed.
+    // The function getExitBlock() is used for this check, rather than
+    // getUniqueExitBlock() to ensure loops with mulitple exit edges are
+    // disallowed.
+    if (!L->getExitBlock()) {
+      LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; only loops with single exit "
+                           "blocks can be unrolled and jammed.\n");
+      return false;
+    }
+
+    // Only loops with a single exiting block can be unrolled and jammed.
+    if (!L->getExitingBlock()) {
+      LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; only loops with single "
+                           "exiting blocks can be unrolled and jammed.\n");
+      return false;
+    }
+
     L = L->getSubLoops()[0];
   } while (L);
 
   return true;
 }
 
 static Loop *getInnerMostLoop(Loop *L) {
   while (!L->getSubLoops().empty())

llvm/test/Transforms/LoopUnrollAndJam/multiple_exit_blocks.ll

+; REQUIRES: asserts
+; RUN: opt -debug-only=loop-unroll-and-jam -passes="loop-unroll-and-jam" -enable-unroll-and-jam -allow-unroll-and-jam -unroll-and-jam-count=8 -disable-output %s 2>&1 | FileCheck %s
+
+; CHECK: Loop Unroll and Jam: F[h] Loop %bb8
+; CHECK: Won't unroll-and-jam; only loops with single exit blocks can be unrolled and jammed
+
+@a = external global i16, align 2
+@e = external global i32, align 4
+@f = external global i16, align 2
+@b = external global i16, align 2
+@c = external global i64, align 8
+
+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 label %bb24
+
+bb24:                                             ; preds = %bb43, %bb8
+  %storemerge312 = phi i16 [ 0, %bb8 ], [ %i45, %bb43 ]
+  br i1 %i17, label %bb46.preheader, label %bb43
+
+bb46.preheader:                                   ; preds = %bb24
+  store i16 %storemerge312, i16* @f, align 2
+  br label %bb46
+
+bb43:                                             ; preds = %bb24
+  %i45 = add nuw nsw i16 %storemerge312, 1
+  %i13 = icmp ult i16 %storemerge312, 7
+  br i1 %i13, label %bb24, label %bb47
+
+bb46:                                             ; preds = %bb46.preheader, %bb46
+  br label %bb46
+
+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
+  store i16 %i45, i16* @f, align 2
+  ret void
+}