[LoopUnroll] Don't try to unroll non-rotated loops

[davide]

Summary

LoopUnroll doesn't seem to be in a state to handle this, and we end discovering later, when we end up with a broken dominator :(
(see https://bugs.llvm.org/show_bug.cgi?id=28103#c3)

Fixes PR28103.

[davide]

lib/Transforms/Utils/LoopUnroll.cpp

338–348 ↗

(On Diff #95861)

A similar check is done in LSR. Once we agree this is sufficient to handle these cases, maybe we can move the logic to a common file (LoopInfo.h maybe?)

[mzolotukhin]

lib/Transforms/Utils/LoopUnroll.cpp

324–329 ↗

(On Diff #95861)

This check can probably be removed then.

test/Transforms/LoopUnroll/not-rotated.ll

4 ↗

(On Diff #95861)

Could you please add a comment explaining what we're testing here?

12 ↗

(On Diff #95861)

I'd prefer replacing i1 true with something like i1 %a, where %a is a function argument. That would make the test more stable against compiler getting smarter and optimizing these branches away in future.

[davide]

Address Michael's comments.

[efriedma]

lib/Transforms/Utils/LoopUnroll.cpp

332 ↗

(On Diff #95876)

It might be simpler to explicitly check the two successors; one should be the header, and the other outside the loop.

You also can't delete the check that BI is non-null and conditional; we specifically assume that later on.

[davide]

lib/Transforms/Utils/LoopUnroll.cpp

332 ↗

(On Diff #95876)

Thanks for the comments, I'll change that as I also believe it's simpler.
No tests are failing if I remove that check, which is slightly concerning.
I'll try to craft a test where this fails.

[Gerolf]

I don't know if this patch makes the situation better or worse. It seems to touch on the tip of an iceberg. The underlying problem is: What can or should happen when a loop is irreducible? It the answer is "don't unroll", then this is the fix your actually looking for. Obviously this loop is irreducible since it has a retreat edge from sink to body2, but body2 does not dominate sink. I'm also curious if this loop is in the source code already or if some pass in the compiler actually generated. FWIW, unless the compiler has a problem irreducible loops should be rare. And when the user writes an irreducible loop, I think it is OK when compiler optimizations turn conservative.

-Gerolf

lib/Transforms/Utils/LoopUnroll.cpp

328 ↗

(On Diff #95876)

There must be a helper routine to answer the question whether a loop is rotated or not. Otherwise each pass may end up having its own definition. I'm also wondering how one decides whether or not a loop is rotated when the loop is irreducible.

[efriedma]

The underlying problem is: What can or should happen when a loop is irreducible?

There is no "underlying problem" here. An LLVM "Loop*" always refers to a natural loop; unrolling a Loop is always a well-defined operation (unless we're dealing with something weird like indirectbr). See LoopInfo.h. Our current implementation of loop unrolling only knows how to unroll loops with exactly one latch which is a conditional branch that exits the loop, but that isn't fundamental to the algorithm. We could unroll loops with a more complicated latch, or multiple latches; it's just a matter of teaching the algorithm how to fix up the latches correctly.

[davide]

In D32261#732780, @Gerolf wrote:

I don't know if this patch makes the situation better or worse. It seems to touch on the tip of an iceberg. The underlying problem is: What can or should happen when a loop is irreducible? It the answer is "don't unroll", then this is the fix your actually looking for. Obviously this loop is irreducible since it has a retreat edge from sink to body2, but body2 does not dominate sink. I'm also curious if this loop is in the source code already or if some pass in the compiler actually generated. FWIW, unless the compiler has a problem irreducible loops should be rare. And when the user writes an irreducible loop, I think it is OK when compiler optimizations turn conservative.

-Gerolf

Unless I'm reading the test in the PR incorrectly (which I might) the input contains already the loop (and it's not generated by the compiler).
Please note that the testcase I hit internally and the PR reported upstream are both generated by a fuzzer, and looking at them they don't seem to resemble any kind of real code.
That said, I cannot make a call, but I'm under the impression that loops like this are infrequent enough that bailing out is not necessarily unreasonable. I consider not crashing (or ending up with a corrupt dominator) more important in this case, and in this sense, this patch is an improvement compared to what we have today. If we want to improve the algorithm later to handle more sophisticated latches/multiple latches, we might as well do later (and quite frankly, I wouldn't really go that route until we hit a case where this matters).
What do you think?

[mzolotukhin]

Thanks for addressing my previous remarks! The change looks good to me (modulo Eli's remark regarding the check).

I consider not crashing (or ending up with a corrupt dominator) more important in this case, and in this sense, this patch is an improvement compared to what we have today. If we want to improve the algorithm later to handle more sophisticated latches/multiple latches, we might as well do later (and quite frankly, I wouldn't really go that route until we hit a case where this matters).

Your reasoning makes perfect sense to me.

Michael

lib/Transforms/Utils/LoopUnroll.cpp

332 ↗

(On Diff #95876)

I agree that an explicit check would be simpler and easier to understand here.

[davide]

Updated the check as per Eli's suggestion. PTAL.

[efriedma]

LGTM.

lib/Transforms/Utils/LoopUnroll.cpp

337 ↗

(On Diff #96426)

Extra newline.

llvm/trunk/lib/Transforms/Utils/LoopUnroll.cpp

bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool Force,
   }
 
   // Loops with indirectbr cannot be cloned.
   if (!L->isSafeToClone()) {
     DEBUG(dbgs() << "  Can't unroll; Loop body cannot be cloned.\n");
     return false;
   }
 
+  // The current loop unroll pass can only unroll loops with a single latch
+  // that's a conditional branch exiting the loop.
+  // FIXME: The implementation can be extended to work with more complicated
+  // cases, e.g. loops with multiple latches.
   BasicBlock *Header = L->getHeader();
   BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator());
 
   if (!BI || BI->isUnconditional()) {
     // The loop-rotate pass can be helpful to avoid this in many cases.
     DEBUG(dbgs() <<
              "  Can't unroll; loop not terminated by a conditional branch.\n");
     return false;
   }
 
+  auto CheckSuccessors = [&](unsigned S1, unsigned S2) {
+    return BI->getSuccessor(S1) == Header && !L->contains(BI->getSuccessor(S2));
+
+  };
+
+  if (!CheckSuccessors(0, 1) && !CheckSuccessors(1, 0)) {
+    DEBUG(dbgs() << "Can't unroll; only loops with one conditional latch"
+                    " exiting the loop can be unrolled\n");
+    return false;
+  }
+
   if (Header->hasAddressTaken()) {
     // The loop-rotate pass can be helpful to avoid this in many cases.
     DEBUG(dbgs() <<
           "  Won't unroll loop: address of header block is taken.\n");
     return false;
   }
 
   if (TripCount != 0)

llvm/trunk/test/Transforms/LoopUnroll/not-rotated.ll

+; PR28103
+; Bail out if the two successors are not the header
+; and another bb outside of the loop. This case is not
+; properly handled by LoopUnroll, currently.
+
+; RUN: opt -loop-unroll -verify-dom-info %s
+; REQUIRE: asserts
+
+define void @tinkywinky(i1 %patatino) {
+entry:
+  br label %header1
+header1:
+  %indvars.iv = phi i64 [ 1, %body2 ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1
+  br i1 %exitcond, label %body1, label %exit
+body1:
+  br i1 %patatino, label %body2, label %sink
+body2:
+  br i1 %patatino, label %header1, label %body3
+body3:
+  br label %sink
+sink:
+  br label %body2
+exit:
+  ret void
+}