[LoopUtils] Populate sibling loops in reverse program order on new pass manager

[jaykang10]

Summary

New pass manager is populating loops in forward program order rather than legacy pass manager.

Let's see a worse case with the order of new loop pass manager as below.

loop1:
  %6 = phi i8 [ 0, %1 ], [ %9, %5 ]
  %7 = phi i32 [ 1, %ph ], [ %8, %loop1 ]
  %8 = add nuw nsw i8 %7, 1
  %9 = select i1 %4, i8 1, i8 %6
  %10 = and i8 %9, 
  %11 = icmp eq i32 %10, 0
  br i1 %11, label %loop1, label %ph2

ph2:
  %13 = phi i32 [ %8, %loop1 ]
  br label %14 

loop2:
  %15 = phi i32 [ %16, %loop2 ], [ %13, %ph2 ]
  %16 = add nsw i32 %15, -1
  %17 = icmp sgt i32 %15, 0
  br i1 %17, label %14, label %exit
...
}

The loop2 is read-only loop and the IndVarSimplify pass can delete the loop. If we use reverse program order of loops, the loop2 can be deleted and it causes loop1 is also redundant because %8 has no use any more. If we use forward program order of loops, the loop1 can not be removed because the loop2 uses %8 during optimizing loop1.

This change populates the loops in reverse program order on new pass manager like legacy pass manager.

[aeubanks]

It does make sense to me that visiting uses first could be better. I'm not sure if there was actually any specific reason to change the order in the NPM. We'll do some performance testing with this.

[aeubanks]

Actually, can you give a concrete example? The example in the description isn't clear enough

There will probably be cases where one way is better and cases where the other way is better. Might just be better to try to fix your use case directly in the passes themselves

[jaykang10]

Fixed failed tests

[jaykang10]

In D99774#2670209, @aeubanks wrote:

Actually, can you give a concrete example? The example in the description isn't clear enough

There will probably be cases where one way is better and cases where the other way is better. Might just be better to try to fix your use case directly in the passes themselves

@aeubanks Thanks for comments. Let me try to create a example for it.

[jaykang10]

Added a test

[jaykang10]

In D99774#2670925, @jaykang10 wrote:

In D99774#2670209, @aeubanks wrote:

Actually, can you give a concrete example? The example in the description isn't clear enough

There will probably be cases where one way is better and cases where the other way is better. Might just be better to try to fix your use case directly in the passes themselves

@aeubanks Thanks for comments. Let me try to create a example for it.

@aeubanks I have added a reduced example loop-order-on-new-loop-pass-manager.ll.

As you can see, the second loop is read-only loop and the IndVarSimplify pass deletes the loop. If we use reverse order of loops, the second loop is gone and the %7 and %8 are redundant on first loop. In the end, with -O2, it causes empty function. If we use forward order of loops, the first loop is not removed because the second loop uses %8 during optimizing first loop. I am not sure we can fix this issue directly in the passes because it needs to look at other sibling loops. From my opinion, it would be better to change the order of loops in reverse on new loop pass manager for dead uses.

[jaykang10]

@aeubanks Can we push this change please?

[aeubanks]

Traversing forward for the loops can cause a value in an earlier loop to be evaluated, which could help a later loop, right? I'm now not sure that it's such a clear tradeoff.
For example, scev-expander-preserve-lcssa.ll looks worse now.

It could be interesting to revisit a previous loop if a loop was deleted.

I think there are more knowledgeable people about this sort of stuff on llvm-dev, could you make a post there?

[jaykang10]

In D99774#2674608, @aeubanks wrote:

Traversing forward for the loops can cause a value in an earlier loop to be evaluated, which could help a later loop, right? I'm now not sure that it's such a clear tradeoff.
For example, scev-expander-preserve-lcssa.ll looks worse now.

It could be interesting to revisit a previous loop if a loop was deleted.

I think there are more knowledgeable people about this sort of stuff on llvm-dev, could you make a post there?

I agree with you. It could be better to discuss this issue with llvm-dev. Let me make a post to llvm-dev.

[fhahn]

llvm/test/Transforms/IndVarSimplify/scev-expander-preserve-lcssa.ll

122

This seems like a regression?

[jaykang10]

I am seeing the forward one is worse than reverse one on IRCE pass. The pass checks whether it safely calculates the bounds of a new loop using isLoopEntryGuardedByCond which climbs up the predecessor chain of loop header. If the previous loop has already been transformed with the IRCE pass, the current loop sometimes fails to calculate the bounds of a new loop.
The IRCE pass is function pass and it uses appendLoopsToWorklist which adds loops in forward program order. Can we add appendReverseLoopsToWorklist or something like that please? It is not easy to guarantee which order is always better but each pass could know which one is better. How do you think about it?

llvm/test/Transforms/IndVarSimplify/scev-expander-preserve-lcssa.ll

122

Yep, the reverse one is not always better than forward one...

[jaykang10]

@aeubanks As I mentioned on llvm-dev, how do you think about new pass manager allows each pass to choose the order of loops on new pass manager?

[aeubanks]

I think we should stick with one way unless there's specific need otherwise. This patch overall is fine, multiple people have said that we should just stick with the legacy order unless somebody has a better idea.

The description is a bit verbose with unnecessary code snippets, could you clean that up a bit?

llvm/lib/Transforms/Utils/LoopUtils.cpp

1496

this name and various comments need to be updated

[jaykang10]

llvm/lib/Transforms/Utils/LoopUtils.cpp

1496

I am sorry. I missed there is already a templated function for the forward program order. I will update code with it.

[jaykang10]

Used existing templated function for populating loops in reverse program order on new pass manager.

[jaykang10]

@aeubanks I have updated description and code. If you feel something wrong from them, please let me know.

[fhahn]

Could you share any data of the impact this change has on runtime-performance/code-size on benchmarks?

[jaykang10]

In D99774#2704838, @fhahn wrote:

Could you share any data of the impact this change has on runtime-performance/code-size on benchmarks?

I have checked exec_time/size with llvm-test-suite on x86 and the result is as below.

Tests: 2892
Metric: exec_time

/usr/local/lib/python2.7/dist-packages/scipy/stats/stats.py:308: RuntimeWarning: divide by zero encountered in log
  log_a = np.log(np.array(a, dtype=dtype))
Program                                        base   new    diff 
 test-suite...te/GCC-C-execute-980505-2.test     0.00   0.00  inf%
 test-suite...ute/GCC-C-execute-pr49768.test     0.00   0.00  inf%
 test-suite...cute/GCC-C-execute-simd-6.test     0.00   0.00  inf%
 test-suite...ute/GCC-C-execute-pr68328.test     0.00   0.00  inf%
 test-suite...d_ops_test_op_paddusw_152.test     0.00   0.00  inf%
 test-suite...te/GCC-C-execute-stkalign.test     0.00   0.00  inf%
 test-suite.../GCC-C-execute-20071216-1.test     0.00   0.00  inf%
 test-suite...ute/GCC-C-execute-pr47538.test     0.00   0.00  inf%
 test-suite...ecute/GCC-C-execute-mod-1.test     0.00   0.00  inf%
 test-suite...ute/GCC-C-execute-pr46316.test     0.00   0.00  inf%
 test-suite...md_ops_test_op_pmaxsw_177.test     0.00   0.00  inf%
 test-suite...execute-struct-aliasing-1.test     0.00   0.00  inf%
 test-suite...cute/GCC-C-execute-enum-1.test     0.00   0.00  inf%
 test-suite.../GCC-C-execute-20010114-1.test     0.00   0.00  inf%
 test-suite...ute/GCC-C-execute-pr46309.test     0.00   0.00  inf%
 Geomean difference                                           nan%
                base            new         diff
count  2876.000000    2876.000000    2874.000000
mean   485.557850     456.966905     inf        
std    13703.055405   12752.463246  NaN         
min    0.000000       0.000000      -1.000000   
25%    0.000400       0.000400      -0.250000   
50%    0.000700       0.000700       0.000000   
75%    0.010925       0.010925       0.295752   
max    526452.168000  550562.615000  inf

Tests: 2892
Metric: size

Program                                        base    new     diff 
 test-suite...ute/GCC-C-execute-pr41917.test   8016.00 8024.00  0.1%
 test-suite...ute/GCC-C-execute-pr60072.test   8016.00 8024.00  0.1%
 test-suite...ute/GCC-C-execute-pr47155.test   8040.00 8048.00  0.1%
 test-suite...ute/GCC-C-execute-pr82387.test   8048.00 8056.00  0.1%
 test-suite.../GCC-C-execute-20001009-2.test   8048.00 8056.00  0.1%
 test-suite.../GCC-C-execute-20041201-1.test   8056.00 8064.00  0.1%
 test-suite...ute/GCC-C-execute-pr57321.test   8072.00 8080.00  0.1%
 test-suite...ute/GCC-C-execute-pr58385.test   8072.00 8080.00  0.1%
 test-suite...cute/GCC-C-execute-pure-1.test   8080.00 8088.00  0.1%
 test-suite...ute/GCC-C-execute-pr81503.test   8096.00 8104.00  0.1%
 test-suite...ute/GCC-C-execute-pr48717.test   8104.00 8112.00  0.1%
 test-suite...ute/GCC-C-execute-pr65216.test   8120.00 8128.00  0.1%
 test-suite.../GCC-C-execute-20040302-1.test   8136.00 8144.00  0.1%
 test-suite...e/GCC-C-execute-pr52979-1.test   8176.00 8184.00  0.1%
 test-suite...e/GCC-C-execute-pr52979-2.test   8176.00 8184.00  0.1%
 Geomean difference                                             nan%
               base           new         diff
count  2.484000e+03  2.484000e+03  2484.000000
mean   3.340861e+04  3.340918e+04  0.000047   
std    1.803869e+05  1.803872e+05  0.000201   
min    7.992000e+03  7.992000e+03  0.000000   
25%    8.264000e+03  8.264000e+03  0.000000   
50%    8.344000e+03  8.344000e+03  0.000000   
75%    1.742200e+04  1.742200e+04  0.000000   
max    7.648424e+06  7.648432e+06  0.000998

[jaykang10]

@aeubanks Can we push this change please? If you need something more, please let me know.

[fhahn]

In D99774#2705058, @jaykang10 wrote:

In D99774#2704838, @fhahn wrote:

Could you share any data of the impact this change has on runtime-performance/code-size on benchmarks?

I have checked exec_time/size with llvm-test-suite on x86 and the result is as below.

Thanks for sharing the data, but I am not sure the excerpt you shared motivates a change? The SingleSource/short-running ones probably do not provide much insight. I think the results for MultiSource/SPEC would be more interesting. In how many binaries does the patch cause changes? How does it impact runtime performance for longer benchmarks?

[jaykang10]

In D99774#2707984, @fhahn wrote:

In D99774#2705058, @jaykang10 wrote:

In D99774#2704838, @fhahn wrote:

Could you share any data of the impact this change has on runtime-performance/code-size on benchmarks?

I have checked exec_time/size with llvm-test-suite on x86 and the result is as below.

Thanks for sharing the data, but I am not sure the excerpt you shared motivates a change? The SingleSource/short-running ones probably do not provide much insight. I think the results for MultiSource/SPEC would be more interesting. In how many binaries does the patch cause changes? How does it impact runtime performance for longer benchmarks?

On AArch64, the performance difference from spec2006 with this change is as below.

                diff(%)
400.perlbench          0
401.bzip2        1.04712
403.gcc         -0.37736
429.mcf         0.571429
445.gobmk              0
456.hmmer              0
458.sjeng              0
462.libquantum  0.615385
464.h264ref      -0.9009
471.omnetpp     0.684932
473.astar       0.571429
483.xalancbmk   -0.37453

Additionally, with this change, IRCE pass handles more cases and it helps loop vectorizer vectorize more loops. Once this change is merged, I will start discussion to turn on IRCE pass as default on new pass manager.

[aeubanks]

llvm/include/llvm/Transforms/Utils/LoopUtils.h

467 ↗

(On Diff #339183)

this is now wrong?

468–471 ↗

(On Diff #339183)

This comment is what worries me the most. The forward order was deliberately chosen with motivation.

Sorry for all the scrutiny, but this is an important change. If everybody else is ok with this change, then I'm fine too. But I would like to know what the source of your test case is. Is it from some C code?

I still think it would be nice if we could somehow, after a loop has been deleted, revisit other loops that contained defs for uses in the deleted loop. That way we still get advantages of forward traversal along with some benefit of reverse traversal. But perhaps that's not reasonable for the loop pass manager to do.

[jaykang10]

llvm/include/llvm/Transforms/Utils/LoopUtils.h

467 ↗

(On Diff #339183)

No, it is not wrong. It calls different function in this change now. The comment was for forward program order.

468–471 ↗

(On Diff #339183)

This comment is what worries me the most. The forward order was deliberately chosen with motivation.

I agree with the comment but there could be other cases get worse with forward order.

Sorry for all the scrutiny, but this is an important change. If everybody else is ok with this change, then I'm fine too. But I would like to know what the source of your test case is. Is it from some C code?

Yep, the test case comes from spec benchmark and I have reduced it.

I still think it would be nice if we could somehow, after a loop has been deleted, revisit other loops that contained defs for uses in the deleted loop. That way we still get advantages of forward traversal along with some benefit of reverse traversal. But perhaps that's not reasonable for the loop pass manager to do.

I agree with it. Each pass could re-visit the target loops.

[jaykang10]

I feel it is not easy to get agreement with this change from everyone. Let's just keep open this issue. Later, down stream folks could raise this issue again because they could meet different input on their own passes based on legacy pass manager.

llvm/lib/Transforms/Utils/LoopUtils.cpp

void llvm::setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop,
   setLoopEstimatedTripCount(RemainderLoop, RemainderAverageTripCount,
                             OrigLoopInvocationWeight);
 }
 
 /// Utility that implements appending of loops onto a worklist.
 /// Loops are added in preorder (analogous for reverse postorder for trees),
 /// and the worklist is processed LIFO.
 template <typename RangeT>
 void llvm::appendReversedLoopsToWorklist(
     RangeT &&Loops, SmallPriorityWorklist<Loop *, 4> &Worklist) {
   // We use an internal worklist to build up the preorder traversal without
   // recursion.
   SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist;
 
   // We walk the initial sequence of loops in reverse because we generally want
   // to visit defs before uses and the worklist is LIFO.
-  for (Loop *RootL : Loops) {
+  for (Loop *RootL : reverse(Loops)) {
     assert(PreOrderLoops.empty() && "Must start with an empty preorder walk.");
     assert(PreOrderWorklist.empty() &&
            "Must start with an empty preorder walk worklist.");
     PreOrderWorklist.push_back(RootL);
     do {
       Loop *L = PreOrderWorklist.pop_back_val();
       PreOrderWorklist.append(L->begin(), L->end());
       PreOrderLoops.push_back(L);

llvm/test/Analysis/LoopNestAnalysis/infinite.ll

 ; RUN: opt < %s -passes='print<loopnest>' -disable-output 2>&1 | FileCheck %s
 
 ; Test that the loop nest analysis is able to analyze an infinite loop in a loop nest.
 define void @test1(i32** %A, i1 %cond) {
+; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: for.infinite, Loops: ( for.infinite )
 ; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: for.inner, Loops: ( for.inner )
 ; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: for.outer, Loops: ( for.outer for.inner )
-; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: for.infinite, Loops: ( for.infinite )
 entry:
   br label %for.outer
 
 for.outer:
   %i = phi i64 [ 0, %entry ], [ %inc_i, %for.outer.latch ]
   br i1 %cond, label %for.inner, label %for.infinite
 
 for.inner:

llvm/test/CodeGen/AArch64/loop-micro-op-buffer-size-t99.ll

 ; REQUIRES: asserts
 ; RUN: opt -mcpu=thunderx2t99 -passes=loop-unroll --debug-only=loop-unroll --debug-only=basicblock-utils -S -unroll-allow-partial < %s 2>&1 | FileCheck %s
 
 target triple = "aarch64-unknown-linux-gnu"
 
-; CHECK: Loop Unroll: F[foo] Loop %loop.header
-; CHECK:   Loop Size = 18
-; CHECK:   Trip Count = 512
-; CHECK:   Trip Multiple = 512
-; CHECK: UNROLLING loop %loop.header by 4 with a breakout at trip 0
-; CHECK: Merging:
 ; CHECK: Loop Unroll: F[foo] Loop %loop.2.header
 ; CHECK: Loop Size = 19
 ; CHECK: Trip Count = 512
 ; CHECK: Trip Multiple = 512
 ; CHECK: UNROLLING loop %loop.2.header by 4 with a breakout at trip 0
 ; CHECK: Merging:
+; CHECK: Loop Unroll: F[foo] Loop %loop.header
+; CHECK:   Loop Size = 18
+; CHECK:   Trip Count = 512
+; CHECK:   Trip Multiple = 512
+; CHECK: UNROLLING loop %loop.header by 4 with a breakout at trip 0
+; CHECK: Merging:
 ; CHECK: %counter = phi i32 [ 0, %entry ], [ %inc.3, %loop.inc.3 ]
 ; CHECK: %val = add nuw nsw i32 %counter, 5
 ; CHECK: %val1 = add nuw nsw i32 %counter, 6
 ; CHECK: %val2 = add nuw nsw i32 %counter, 7
 ; CHECK: %val3 = add nuw nsw i32 %counter, 8
 ; CHECK: %val4 = add nuw nsw i32 %counter, 9
 ; CHECK: %val5 = add nuw nsw i32 %counter, 10
 ; CHECK-NOT: %val = add i32 %counter, 5

llvm/test/Other/loop-pass-ordering.ll

 ; RUN: opt -disable-output -debug-pass-manager \
 ; RUN:     -passes='no-op-loop' %s 2>&1 \
 ; RUN:     | FileCheck %s
 
 ;            @f()
 ;           /    \
 ;       loop.0   loop.1
 ;      /      \        \
 ; loop.0.0  loop.0.1  loop.1.0
 ;
+; CHECK: Running pass: NoOpLoopPass on Loop at depth 2 containing: %loop.1.0
+; CHECK: Running pass: NoOpLoopPass on Loop at depth 1 containing: %loop.1
 ; CHECK: Running pass: NoOpLoopPass on Loop at depth 2 containing: %loop.0.0
 ; CHECK: Running pass: NoOpLoopPass on Loop at depth 2 containing: %loop.0.1
 ; CHECK: Running pass: NoOpLoopPass on Loop at depth 1 containing: %loop.0
-; CHECK: Running pass: NoOpLoopPass on Loop at depth 2 containing: %loop.1.0
-; CHECK: Running pass: NoOpLoopPass on Loop at depth 1 containing: %loop.1
 
 define void @f() {
 entry:
   br label %loop.0
 loop.0:
   br i1 undef, label %loop.0.0, label %loop.1
 loop.0.0:
   br i1 undef, label %loop.0.0, label %loop.0.1

llvm/test/Transforms/IndVarSimplify/scev-expander-preserve-lcssa.ll

 ; CHECK-NEXT:    ]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    [[I_0_LCSSA2:%.*]] = phi i32 [ 0, [[FOR_COND]] ]
 ; CHECK-NEXT:    [[CMP8243:%.*]] = icmp sgt i32 [[I_0_LCSSA2]], 0
 ; CHECK-NEXT:    br i1 [[CMP8243]], label [[FOR_BODY84_PREHEADER:%.*]], label [[RETURN]]
 ; CHECK:       for.body84.preheader:
 ; CHECK-NEXT:    br label [[FOR_BODY84:%.*]]
 ; CHECK:       for.body84:
+; CHECK-NEXT:    [[I_144:%.*]] = phi i32 [ [[INC:%.*]], [[IF_END106:%.*]] ], [ 0, [[FOR_BODY84_PREHEADER]] ]
 ; CHECK-NEXT:    [[C_2:%.*]] = call i1 @cond()
-; CHECK-NEXT:    br i1 [[C_2]], label [[IF_END106:%.*]], label [[RETURN_LOOPEXIT:%.*]]
+; CHECK-NEXT:    br i1 [[C_2]], label [[IF_END106]], label [[RETURN_LOOPEXIT:%.*]]
 ; CHECK:       if.end106:
-; CHECK-NEXT:    br i1 false, label [[FOR_BODY84]], label [[RETURN_LOOPEXIT]]
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_144]], 1
+; CHECK-NEXT:    [[CMP82:%.*]] = icmp slt i32 [[INC]], [[I_0_LCSSA2]]
+; CHECK-NEXT:    br i1 [[CMP82]], label [[FOR_BODY84]], label [[RETURN_LOOPEXIT]]
 ; CHECK:       return.loopexit:
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       return.loopexit1:
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret void
 ;
 entry:

llvm/test/Transforms/LoopUnroll/X86/store_cost.ll

 ; REQUIRES: asserts
 ; RUN: opt -mcpu=core-avx2 -passes=loop-unroll -debug-only=loop-unroll -S -unroll-allow-partial < %s 2>&1 | FileCheck %s
 
 target triple = "x86_64-unknown-linux-gnu"
 
-; CHECK: Loop Unroll: F[foo] Loop %loop.header
-; CHECK:   Loop Size = 25
-; CHECK: UNROLLING loop %loop.header by 2 
 ; CHECK: Loop Unroll: F[foo] Loop %loop.2.header
 ; CHECK: Loop Size = 27
 ; CHECK-NOT: UNROLLING loop %loop.2.header
+; CHECK: Loop Unroll: F[foo] Loop %loop.header
+; CHECK:   Loop Size = 25
+; CHECK: UNROLLING loop %loop.header by 2
 
 define void @foo(i32 * %out) {
 entry:
   %0 = alloca [1024 x i32]
   %x0 = alloca [1024 x i32]
   %x01 = alloca [1024 x i32]
   %x02 = alloca [1024 x i32]
   %x03 = alloca [1024 x i32]

llvm/test/Transforms/LoopUnroll/unroll-loop-invalidation.ll

 ; CHECK: Finished Loop pass manager run.
 ; CHECK: Running pass: LoopUnrollPass
 ; CHECK: Clearing all analysis results for: inner2.header
 ; CHECK: Clearing all analysis results for: outer.header
 ; CHECK: Invalidating analysis: LoopAccessAnalysis on inner1.header
 ; CHECK-NOT: Invalidating analysis: LoopAccessAnalysis on inner1.header.1
 ; CHECK: Starting Loop pass manager run.
 ; CHECK: Running pass: LoopAccessInfoPrinterPass
-; CHECK: Running analysis: LoopAccessAnalysis on Loop at depth 1 containing: %inner1.header
+; CHECK: Running analysis: LoopAccessAnalysis on Loop at depth 1 containing: %inner1.header.1
 ; CHECK: Loop access info in function 'test':
-; CHECK:   inner1.header:
+; CHECK:   inner1.header.1:
 ; CHECK: Finished Loop pass manager run.
 ; CHECK: Starting Loop pass manager run.
 ; CHECK: Running pass: LoopAccessInfoPrinterPass
-; CHECK: Running analysis: LoopAccessAnalysis on Loop at depth 1 containing: %inner1.header.1
+; CHECK: Running analysis: LoopAccessAnalysis on Loop at depth 1 containing: %inner1.header
 ; CHECK: Loop access info in function 'test':
-; CHECK:   inner1.header.1:
+; CHECK:   inner1.header:
 ; CHECK: Finished Loop pass manager run.
 
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @test(i32 %inner1.count) {
 ; CHECK-LABEL: define void @test(
 bb:
   br label %outer.ph