[LoopUtils] Extend the scope of getLoopEstimatedTripCount

[skatkov]

Summary

With this patch the getLoopEstimatedTripCount function will
accept also the loops where there are more than one exit but
all exits except latch block should ends up with a call to deopt.

This side exits should not impact the estimated trip count.

[lebedev.ri]

May be good to have a test.

[fhahn]

llvm/lib/Transforms/Utils/LoopUtils.cpp

624

Would it make sense to remove the restriction of having a single exit block/only deopt non latch exit by generalizing the function?

Wouldn't' it be reasonable to estimate the trip count by summing up the weights of all exit edges and dividing by the weight of the back-edge to the header? That should naturally cover the deopt cases as well, as they should have very low weights, right?

In any case, we should also update the doc-comment in the header describing the new behavior.

[skatkov]

llvm/lib/Transforms/Utils/LoopUtils.cpp

624

Hi Florian, thank you for your comment.

I think that sum of exit weights from different branches is not a good idea. We can compare/use only probabilities not the real values.

Let's consider the following case, we have a loop with two exits. One of them has weights (10, 1) and the second one (1,1). for simplicity the second number is a weight of exit.

What will be Trip Count in this case?
According to your proposed formula it is 5. Looks strange.

Moreover it is totally fine to scale the weights by some constant. For example, (1,1) is actually the same as (100, 100).
In this case according to formula trip count will be 0.

So I think that it is not incorrect and to get the right formula is not really easy task, so I just want to adjust only guard of this formula for the moment.

With respect to update the header, The header description does not mention the restriction about only one exit now. It is more general and correct. If we can provide estimated trip count we do that. With my additional guard nothing changed.

If you really want to see that details in the header, please let me know and I will update a header.

[skatkov]

In D64553#1580189, @lebedev.ri wrote:

May be good to have a test.

The tests using this functionality can be found in https://reviews.llvm.org/D63923 and https://reviews.llvm.org/D64618 or you need a separate unit test?

[reames]

LGTM w/required fix before submit.

llvm/lib/Transforms/Utils/LoopUtils.cpp

624

I'd ask that we specifically do not extend the scope of this patch. A separate patch can expand scope, but let's start with something low risk, make sure the caller code is well exercised, then increase the scope. Working in stages to reduce risk is important.

628

There's a missing correctness check here. There's no guarantee that a loop *must* have a unique latch, so you need null check the result before dereferencing. Non unique latches are non-canonical, so you can just bail on that case.

Note that unique exit implies unique latch previously.

[skatkov]

llvm/lib/Transforms/Utils/LoopUtils.cpp

628

To be honest I do not understand how unique exit implies unique latch but I can add additional check.

[efriedma]

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

640 ↗

(On Diff #209764)

I'm seeing Assertion 'L->hasDedicatedExits() && "getUniqueExitBlocks assumes the loop has canonical form exits!"' failed. with some out-of-tree code that calls getLoopEstimatedTripCount. Does this analysis really require that the loop has dedicated exits? If it does, can we guard this call so getLoopEstimatedTripCount fails gracefully for loops without dedicated exits?

I think all the in-tree users of getLoopEstimatedTripCount require dedicated exits for other reasons, so no bug report.

[skatkov]

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

640 ↗

(On Diff #209764)

Hello Eli,

getUniqueExitBlocks is written in a way that it expects that all predecessors of successor of loop's basic block is in a loop.

I totally fine to add a guard to fail gracefully. Will publish a patch in a couple of hours.

[skatkov]

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

640 ↗

(On Diff #209764)

Hi again,

It is interesting catch. It seems I introduced a bug while adding getUniqueNonLatchExitBlocks utility function.
It seems that getUniqueExitBlocksHelper is written in a way it expects that all exits's first predecessor is in a loop and no need to check others predecessors. In case I skip latch I can miss the exit if it has two predecessors: latch and non-latch.

I will try to write a test and then re-write the getUniqueExitBlocksHelper function. So assert will be eliminated from it.

Thank you for pointing to this issue.

[skatkov]

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

640 ↗

(On Diff #209764)

See D64787

llvm/lib/Transforms/Utils/LoopUtils.cpp

for (BasicBlock *BB : blocks)
       LI->removeBlock(BB);
 
     // The last step is to update LoopInfo now that we've eliminated this loop.
     LI->erase(L);
   }
 }
 
 Optional<unsigned> llvm::getLoopEstimatedTripCount(Loop *L) {
-  // Only support loops with a unique exiting block, and a latch.
-  if (!L->getExitingBlock())
-    return None;
+  // Support loops with an exiting latch and other existing exists only
+  // deoptimize.
 
   // Get the branch weights for the loop's backedge.
-  BranchInst *LatchBR =
-      dyn_cast<BranchInst>(L->getLoopLatch()->getTerminator());
-  if (!LatchBR || LatchBR->getNumSuccessors() != 2)
+  BasicBlock *Latch = L->getLoopLatch();
+  BranchInst *LatchBR = dyn_cast<BranchInst>(Latch->getTerminator());
+  if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
     return None;
 
   assert((LatchBR->getSuccessor(0) == L->getHeader() ||
           LatchBR->getSuccessor(1) == L->getHeader()) &&
          "At least one edge out of the latch must go to the header");
 
+  SmallVector<BasicBlock *, 4> ExitBlocks;
+  L->getUniqueNonLatchExitBlocks(ExitBlocks);
+  if (any_of(ExitBlocks, [](const BasicBlock *EB) {
+        return !EB->getTerminatingDeoptimizeCall();
+      }))
+    return None;
+
   // To estimate the number of times the loop body was executed, we want to
   // know the number of times the backedge was taken, vs. the number of times
   // we exited the loop.
   uint64_t TrueVal, FalseVal;
   if (!LatchBR->extractProfMetadata(TrueVal, FalseVal))
     return None;
 
   if (!TrueVal || !FalseVal)