[IVUser] Limit the iterations to check whether a loop has dedicated exits for extreme large case

[wmi]

Summary

We had a case that a single loop which has 4000 exits and the average number of predecessors of each exit is > 1000. It increased the compilation time of IVUser analysis significantly. This patch adds a limit for the iterations to check whether a loop has only dedicated exits. With the patch, the time to compile our testcase reduced from 1000s to 200s (clang release build).

[skatkov]

I wonder whether the problem is in this function or in analysis itself?
If it is a problem of analysis it is better to restrict it but not an utility function.

[wmi]

In D67359#1664241, @skatkov wrote:

I wonder whether the problem is in this function or in analysis itself?
If it is a problem of analysis it is better to restrict it but not an utility function.

I feel the problem is in the utility function. Currently the problem is exposed in IVUser pass but the same can happen anywhere else if only the function is called for a huge loop with many exits and with each exit having many predecessors.

[skatkov]

In D67359#1664242, @wmi wrote:

In D67359#1664241, @skatkov wrote:

I wonder whether the problem is in this function or in analysis itself?
If it is a problem of analysis it is better to restrict it but not an utility function.

I feel the problem is in the utility function. Currently the problem is exposed in IVUser pass but the same can happen anywhere else if only the function is called for a huge loop with many exits and with each exit having many predecessors.

Can you do some measurements to ensure that the issue is really in this utility function but not in the user of it?

At the same time it makes sense to update function description to specify that with your change the function can conservatively returns no if it could not get the precise answer.

[fhahn]

Is there any chance you could provide the test case that shows the behavior? There might be something we could do in hasDedicatedExits to make it faster for large loops with a large number of exit blocks and successors.

[wmi]

In D67359#1664243, @skatkov wrote:

In D67359#1664242, @wmi wrote:

In D67359#1664241, @skatkov wrote:

I wonder whether the problem is in this function or in analysis itself?
If it is a problem of analysis it is better to restrict it but not an utility function.

I feel the problem is in the utility function. Currently the problem is exposed in IVUser pass but the same can happen anywhere else if only the function is called for a huge loop with many exits and with each exit having many predecessors.

Can you do some measurements to ensure that the issue is really in this utility function but not in the user of it?

I did that. For the huge loop, every call of hasDedicatedExits took about 3~5 seconds. hasDedicatedExits is called by isSimplifiedLoopNest which is used by IVUser pass. Indeed there is another problem that IVUser pass calls isSimplifiedLoopNest for the same loop multiple times (~200). However, IVUser is a loop analysis pass, and isSimplifiedLoopNest can be called for a loop different from the current loop analyzed. So isSimplifiedLoopNest is called for the same huge loop many times for many different invocations of IVUser pass analyzing different loops, and the cache mechanism local to IVUser doesn't work for it.

I understand it is possible to mitigate the problem in IVUser (I don't know how to do that yet. The original commit to add isSimplifiedLoopNest was r152892 in 2012 and the original bug was in rdar://problem/11049788 which I cannot read) but it seems also reasonable to put a limit in hasDedicatedExits -- For my case, the loop with 4000 exits + each exit has 1000 predecessors took 3~5 seconds for each call of hasDedicatedExits. It is already noticeable to compiler users. If the loop is larger, it will take more time even if hasDedicatedExits is called only once for it. I think it is better to put a limit for such high cost function and that is independent to improve the cache or algorithm in IVUser.

At the same time it makes sense to update function description to specify that with your change the function can conservatively returns no if it could not get the precise answer.

That makes sense. I will do that.

[wmi]

In D67359#1664487, @fhahn wrote:

Is there any chance you could provide the test case that shows the behavior? There might be something we could do in hasDedicatedExits to make it faster for large loops with a large number of exit blocks and successors.

The loop contains a huge switch case statement. I will see if I can create something showing similar behavior.

[wmi]

Sorry for taking a while to get back. Upload a testfile 1.cc:

1.cc497 KBDownload

.

~/workarea/llvm-r371746/rbuild/bin/clang -O2 -S 1.cc
Without the patch, it took 52s to compile.
With the patch, it took 2s to compile.
gcc took 9s to compile.

And for the testcase, disabling LSR didn't help much, so it is not an IVUser specific problem. It took so long mainly because of hasDedicatedExits.

[xbolva00]

Maybe you can add this test case to llvm test suite?

[wmi]

In D67359#1679956, @xbolva00 wrote:

Maybe you can add this test case to llvm test suite?

Do you know how to add a compile time testcase in testsuite usually?

Thanks,
Wei.

[xbolva00]

Probably just put it here:

https://github.com/llvm/llvm-test-suite/tree/master/SingleSource/Regression/C

[wmi]

In D67359#1679979, @xbolva00 wrote:

Probably just put it here:

https://github.com/llvm/llvm-test-suite/tree/master/SingleSource/Regression/C

Thanks, I can put the test there, but I am not sure how large should I increase the size of the test to so it will definitely timeout without the patch, and do I need to consider the test takes different time to compile on different machines? I remember there is a fixed compile time limit to build a file in testsuite but I don't remember how long it is. Do you happen to know that?

[wmi]

Address Serguei's comment: update function description.

[xbolva00]

In D67359#1679990, @wmi wrote:

In D67359#1679979, @xbolva00 wrote:

Probably just put it here:

https://github.com/llvm/llvm-test-suite/tree/master/SingleSource/Regression/C

Thanks, I can put the test there, but I am not sure how large should I increase the size of the test to so it will definitely timeout without the patch, and do I need to consider the test takes different time to compile on different machines? I remember there is a fixed compile time limit to build a file in testsuite but I don't remember how long it is. Do you happen to know that?

I dont know :( but 2s is probably okay. Maybe @fhahn can you help here..

[skatkov]

include/llvm/Analysis/LoopInfoImpl.h

88 ↗

(On Diff #221437)

I'm sorry if I was not specific but I meant the comment in LoopInfo.h file for the method hasDedicatedExits not in LoopInfoImpl.h.

[wmi]

Address Serguei's comment.

[wmi]

include/llvm/Analysis/LoopInfoImpl.h

88 ↗

(On Diff #221437)

Ah, got it, thanks. Fixed.

[wmi]

In D67359#1680004, @xbolva00 wrote:

In D67359#1679990, @wmi wrote:

In D67359#1679979, @xbolva00 wrote:

Probably just put it here:

https://github.com/llvm/llvm-test-suite/tree/master/SingleSource/Regression/C

Thanks, I can put the test there, but I am not sure how large should I increase the size of the test to so it will definitely timeout without the patch, and do I need to consider the test takes different time to compile on different machines? I remember there is a fixed compile time limit to build a file in testsuite but I don't remember how long it is. Do you happen to know that?

I dont know :( but 2s is probably okay. Maybe @fhahn can you help here..

I find the compile time limit in lnt nightly test is 500 seconds. To stably get time out without the patch, I estimate I need to increase the size of test so it takes > 30seconds to compile with the patch. I am not sure if that is ok.

[skatkov]

The last thing. Would not you like to add a test examine the max-dedicate-exit-iterations functionality?

The test can use the small number for max-dedicate-exit-iterations and ensure that the function returns false? If it is difficult examine through opt you can probably write a unit test?
It seems it may protect you from future modification of this method.

If it is difficult or impossible to do -> lgtm.

[wmi]

In D67359#1681798, @skatkov wrote:

The last thing. Would not you like to add a test examine the max-dedicate-exit-iterations functionality?

Good point. Test added.

[wmi]

Address Serguei's comment: add a unittest.

[xbolva00]

Test added.

Great.

[skatkov]

Thanks.

[wmi]

Thanks all for the review!

llvm/trunk/include/llvm/Analysis/LoopInfo.h

#endif
   void getExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
 
   /// If getExitBlocks would return exactly one block, return that block.
   /// Otherwise return null.
   BlockT *getExitBlock() const;
 
   /// Return true if no exit block for the loop has a predecessor that is
   /// outside the loop.
+  /// Return false if a non-dedicated successor is found or it cannot finish
+  /// the check within MaxDedicateExitIterations iterations so return false
+  /// conservatively.
   bool hasDedicatedExits() const;
 
   /// Return all unique successor blocks of this loop.
   /// These are the blocks _outside of the current loop_ which are branched to.
   void getUniqueExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
 
   /// Return all unique successor blocks of this loop except successors from
   /// Latch block are not considered. If the exit comes from Latch has also

llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h

 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/Dominators.h"
 
 namespace llvm {
 
+// Max number of loop iterations to check whether a loop is a dedicated
+// exit loop.
+extern cl::opt<uint64_t> MaxDedicateExitIterations;
+
 //===----------------------------------------------------------------------===//
 // APIs for simple analysis of the loop. See header notes.
 
 /// getExitingBlocks - Return all blocks inside the loop that have successors
 /// outside of the loop.  These are the blocks _inside of the current loop_
 /// which branch out.  The returned list is always unique.
 ///
 template <class BlockT, class LoopT>

 }
 
 template <class BlockT, class LoopT>
 bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
   // Each predecessor of each exit block of a normal loop is contained
   // within the loop.
   SmallVector<BlockT *, 4> ExitBlocks;
   getExitBlocks(ExitBlocks);
-  for (BlockT *EB : ExitBlocks)
-    for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
+  uint64_t Iterations = 0;
+  for (BlockT *EB : ExitBlocks) {
+    for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB)) {
       if (!contains(Predecessor))
         return false;
+      Iterations++;
+    }
+    if (Iterations > MaxDedicateExitIterations)
+      return false;
+  }
   // All the requirements are met.
   return true;
 }
 
 // Helper function to get unique loop exits. Pred is a predicate pointing to
 // BasicBlocks in a loop which should be considered to find loop exits.
 template <class BlockT, class LoopT, typename PredicateT>
 void getUniqueExitBlocksHelper(const LoopT *L,

llvm/trunk/lib/Analysis/LoopInfo.cpp

 bool llvm::VerifyLoopInfo = true;
 #else
 bool llvm::VerifyLoopInfo = false;
 #endif
 static cl::opt<bool, true>
     VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
                     cl::Hidden, cl::desc("Verify loop info (time consuming)"));
 
+namespace llvm {
+cl::opt<uint64_t> MaxDedicateExitIterations(
+    "max-dedicate-exit-iterations", cl::Hidden, cl::init(100000),
+    cl::desc("Max number of loop iterations to check whether a loop is a "
+             "dedicated exit loop. "));
+}
+
 //===----------------------------------------------------------------------===//
 // Loop implementation
 //
 
 bool Loop::isLoopInvariant(const Value *V) const {
   if (const Instruction *I = dyn_cast<Instruction>(V))
     return !contains(I);
   return true; // All non-instructions are loop invariant

llvm/trunk/test/Transforms/LICM/loop-max-dedicated-exit-iterations.ll

+; RUN: opt -S -licm -max-dedicate-exit-iterations=5 < %s | FileCheck %s
+; RUN: opt -S -licm -max-dedicate-exit-iterations=100 < %s | FileCheck %s -check-prefixes=SINK
+; RUN: opt -S -passes='require<opt-remark-emit>,loop(licm)' -max-dedicate-exit-iterations=5 < %s | FileCheck %s
+; RUN: opt -S -passes='require<opt-remark-emit>,loop(licm)' -max-dedicate-exit-iterations=100 < %s | FileCheck %s -check-prefixes=SINK
+; Code sink in LICM requires the loop has dedicated exits. Use code sink
+; in LICM to verify max-dedicate-exit-iterations is functioning.
+
+@_ZL1m = internal global i64 0, align 8
+@.str = private unnamed_addr constant [13 x i8] c"hello = %ld\0A\00", align 1
[e-mail]_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @_GLOBAL__sub_I_2.cc, i8* null }]
+
+declare dso_local i64 @_Z3goov() local_unnamed_addr #0
+
+; Function Attrs: argmemonly nounwind willreturn
+declare {}* @llvm.invariant.start.p0i8(i64 immarg, i8* nocapture)
+
+; Function Attrs: uwtable
+define dso_local void @_Z3fool(i64 %a) local_unnamed_addr {
+entry:
+  %cmp18.old.old.old.old.old = icmp slt i64 %a, 5
+  %cmp14.old.old.old.old = icmp slt i64 %a, 4
+  %cmp10.old.old.old = icmp slt i64 %a, 3
+  %cmp6.old.old = icmp slt i64 %a, 2
+  %cmp2.old = icmp slt i64 %a, 1
+  %cmp = icmp slt i64 %a, 0
+; Check load cannot be sinked out of loop when max-dedicate-exit-iterations=5
+; and hasDedicatedExits return false, so it is hoisted out of loop.
+; CHECK: load i64, i64* @_ZL1m, align 8
+; CHECK: br label %do.body
+; CHECK: do.body:
+  br label %do.body
+
+do.body:                                          ; preds = %do.body.backedge, %entry
+  %t0 = load i64, i64* @_ZL1m, align 8, !tbaa !2
+  %call = tail call i64 @_Z3goov()
+  switch i64 %call, label %do.cond [
+    i64 0, label %sw.bb
+    i64 1, label %sw.bb1
+    i64 2, label %sw.bb5
+    i64 3, label %sw.bb9
+    i64 4, label %sw.bb13
+    i64 5, label %sw.bb17
+  ]
+
+sw.bb:                                            ; preds = %do.body
+  br i1 %cmp, label %Done, label %do.body.backedge
+
+sw.bb1:                                           ; preds = %do.body
+  br i1 %cmp2.old, label %Done, label %do.body.backedge
+
+sw.bb5:                                           ; preds = %do.body
+  br i1 %cmp6.old.old, label %Done, label %do.body.backedge
+
+sw.bb9:                                           ; preds = %do.body
+  br i1 %cmp10.old.old.old, label %Done, label %do.body.backedge
+
+sw.bb13:                                          ; preds = %do.body
+  br i1 %cmp14.old.old.old.old, label %Done, label %do.body.backedge
+
+sw.bb17:                                          ; preds = %do.body
+  br i1 %cmp18.old.old.old.old.old, label %Done, label %do.body.backedge
+
+do.cond:                                          ; preds = %do.body
+  %cmp21.old.old.old.old.old.old = icmp slt i64 %call, 10000
+  br i1 %cmp21.old.old.old.old.old.old, label %do.body.backedge, label %Done
+
+do.body.backedge:                                 ; preds = %do.cond, %sw.bb17, %sw.bb13, %sw.bb9, %sw.bb5, %sw.bb1, %sw.bb
+  br label %do.body
+
+Done:                                             ; preds = %sw.bb, %sw.bb1, %sw.bb5, %sw.bb9, %sw.bb13, %sw.bb17, %do.cond
+; Check load is sinked out of loop when max-dedicate-exit-iterations=100
+; and hasDedicatedExits return true.
+; SINK: Done:
+; SINK: load i64, i64* @_ZL1m, align 8
+; SINK-NEXT: tail call {{.*}} @printf
+  %call22 = tail call i32 (i8*, ...) @printf(i8* nonnull dereferenceable(1) getelementptr inbounds ([13 x i8], [13 x i8]* @.str, i64 0, i64 0), i64 %t0)
+  ret void
+}
+
+; Function Attrs: nofree nounwind
+declare dso_local i32 @printf(i8* nocapture readonly, ...) local_unnamed_addr
+
+; Function Attrs: uwtable
+define internal void @_GLOBAL__sub_I_2.cc() section ".text.startup" {
+entry:
+  %call.i = tail call i64 @_Z3goov()
+  store i64 %call.i, i64* @_ZL1m, align 8, !tbaa !2
+  %t0 = tail call {}* @llvm.invariant.start.p0i8(i64 8, i8* bitcast (i64* @_ZL1m to i8*))
+  ret void
+}
+
+attributes #0 = { readonly }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 10.0.0 (trunk 372630) (llvm/trunk 372631)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"long", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C++ TBAA"}