[PowerPC] Don't transform to CTR loop if the decrement branch instr. would end up in a different loop

[nemanjai]

Summary

This fixes PR37229.

Basically, we don't want to transform a loop to a CTR loop if the decrement-and-branch instruction would end up in an exiting block that is also part of another nested loop. Previously this couldn't happen because of how SCEV computed the trip count. However, the check is fundamentally needed.

[chandlerc]

test/CodeGen/PowerPC/no-ctr-loop-if-exit-in-nested-loop.ll

1–4 ↗

(On Diff #144250)

I'm really worried that this test is overreduced.

I think you should craft an IR test that directly forms the pattern you describe where an outer loop has an exiting block shared with an inner loop, but the trip count can only be computed for the outer loop.

I'd also encourage you to not have any undef in the branches. Instead, you really just want to have a "real" (if minimal) loop structure.

[efriedma]

lib/Target/PowerPC/PPCCTRLoops.cpp

579 ↗

(On Diff #144250)

The actual condition you need to check is whether the branch executes exactly once per iteration.

For most code, this check is equivalent, but it's possible to have an irreducible "loop" which is not an LLVM Loop.

[nemanjai]

lib/Target/PowerPC/PPCCTRLoops.cpp

579 ↗

(On Diff #144250)

Sorry if this is a naive question, but would adding a check that this loop's header dominates the exit block suffice for such a case?

I don't really know what an irreducible loop looks like, but with this question, I'm making the assumption that for such a loop, there would have to be a path to the exit block that doesn't go through the header. Of course, if this assumption is wrong, please correct me.

test/CodeGen/PowerPC/no-ctr-loop-if-exit-in-nested-loop.ll

1–4 ↗

(On Diff #144250)

Yeah, I took the easy approach of unleashing bugpoint on the original test case. I'll reduce it manually to keep the original structure in the test.

[nemanjai]

I've produced a test case that closely resembles the original CFG. Also updated the condition to hopefully address the valid point that @efriedma brought up.
Please let me know if this is sufficient.

[mkazantsev]

lib/Target/PowerPC/PPCCTRLoops.cpp

578 ↗

(On Diff #144271)

By definition, loop header dominates all blocks of this loop. So once you've checked that LI->getLoop(*I) is L, it will automatically give you the second part of the check. I think you can assert that DT->dominates(L->getHeader(), *I)) if the first part is true.

[nemanjai]

lib/Target/PowerPC/PPCCTRLoops.cpp

578 ↗

(On Diff #144271)

Ah, OK. That makes sense. So clearly my condition isn't sufficient to address Eli's comment. If either you or Eli can suggest how I might modify this condition to also address irreducible loops completely nested in the outer loop, I would really appreciate it.

[hfinkel]

lib/Target/PowerPC/PPCCTRLoops.cpp

579 ↗

(On Diff #144250)

We have a utility for this. ShrinkWrapping uses it:

if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *MLI)) {

as does the loop vectorizer:

if (!containsIrreducibleCFG<const BasicBlock *>(RPOT, *LI)) {

I think that you want to do something here very similar to what the loop vectorizer does:

static void collectSupportedLoops(Loop &L, LoopInfo *LI,

                                OptimizationRemarkEmitter *ORE,
                                SmallVectorImpl<Loop *> &V) {
// Collect inner loops and outer loops without irreducible control flow. For
// now, only collect outer loops that have explicit vectorization hints.
if (L.empty() || (EnableVPlanNativePath && isExplicitVecOuterLoop(&L, ORE))) {
  LoopBlocksRPO RPOT(&L);
  RPOT.perform(LI);
  if (!containsIrreducibleCFG<const BasicBlock *>(RPOT, *LI)) {
    V.push_back(&L);
    // TODO: Collect inner loops inside marked outer loops in case
    // vectorization fails for the outer loop. Do not invoke
    // 'containsIrreducibleCFG' again for inner loops when the outer loop is
    // already known to be reducible. We can use an inherited attribute for
    // that.
    return;
  }
}
for (Loop *InnerL : L)
  collectSupportedLoops(*InnerL, LI, ORE, V);

}

[mkazantsev]

lib/Target/PowerPC/PPCCTRLoops.cpp

578 ↗

(On Diff #144271)

I don't think that SCEV will be able to calculate iteration count for a loop with irreducible control flow. Do you have a test when you really need to support it?

[mkazantsev]

lib/Target/PowerPC/PPCCTRLoops.cpp

578 ↗

(On Diff #144271)

Unless there is a reason why you need it, I would suggest just to limit this transform to the loops that have a single backedge since it's the canonical form.

[efriedma]

lib/Target/PowerPC/PPCCTRLoops.cpp

578 ↗

(On Diff #144271)

SCEV can compute the trip count for a loop which contains irreducible control flow. For example:

define void @foo(i1 %z) {
entry:
  br label %loophead

loophead:
  %i = phi i32 [ 0, %entry ], [ %inc, %irr_exit ]
  br i1 %z, label %irr_head1, label %irr_head2

irr_head1:
  br label %exiting

irr_head2:
  br label %exiting

exiting:
  %inc = add nuw nsw i32 %i, 1
  %exitcond = icmp eq i32 %inc, 100000
  br i1 %exitcond, label %exit, label %irr_cont

irr_cont:
  br i1 %z, label %irr_cont2, label %irr_exit

irr_cont2:
  br i1 %z, label %irr_head1, label %irr_head2

irr_exit:
  br label %loophead

exit:
  ret void
}

[nemanjai]

Added a check for irreducible CFG within the loop being considered for transformation - thanks for the pointers @efriedma and @hfinkel.
We simply bail out of the transformation if the loop has irreducible control flow rather than analyzing said control flow. This results in a total reduction of 2 loops out of 25,432 that are transformed in a bootstrap build.

[hfinkel]

LGTM

llvm/trunk/lib/Target/PowerPC/PPCCTRLoops.cpp

 
 #include "PPC.h"
 #include "PPCSubtarget.h"
 #include "PPCTargetMachine.h"
 #include "PPCTargetTransformInfo.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/Utils/Local.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/CodeGen/TargetSchedule.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
     MadeChange |= convertToCTRLoop(*I);
     DEBUG(dbgs() << "Nested loop converted\n");
   }
 
   // If a nested loop has been converted, then we can't convert this loop.
   if (MadeChange)
     return MadeChange;
 
+  // Bail out if the loop has irreducible control flow.
+  LoopBlocksRPO RPOT(L);
+  RPOT.perform(LI);
+  if (containsIrreducibleCFG<const BasicBlock *>(RPOT, *LI))
+    return false;
+
 #ifndef NDEBUG
   // Stop trying after reaching the limit (if any).
   int Limit = CTRLoopLimit;
   if (Limit >= 0) {
     if (Counter >= CTRLoopLimit)
       return false;
     Counter++;
   }
if (const SCEVConstant *ConstEC = dyn_cast<SCEVConstant>(EC)) {
       if (ConstEC->getValue()->isZero())
         continue;
     } else if (!SE->isLoopInvariant(EC, L))
       continue;
 
     if (SE->getTypeSizeInBits(EC->getType()) > (TM->isPPC64() ? 64 : 32))
       continue;
 
+    // If this exiting block is contained in a nested loop, it is not eligible
+    // for insertion of the branch-and-decrement since the inner loop would
+    // end up messing up the value in the CTR.
+    if (LI->getLoopFor(*I) != L)
+      continue;
+
     // We now have a loop-invariant count of loop iterations (which is not the
     // constant zero) for which we know that this loop will not exit via this
     // exisiting block.
 
     // We need to make sure that this block will run on every loop iteration.
     // For this to be true, we must dominate all blocks with backedges. Such
     // blocks are in-loop predecessors to the header block.
     bool NotAlways = false;

llvm/trunk/test/CodeGen/PowerPC/no-ctr-loop-if-exit-in-nested-loop.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mcpu=pwr8 -mtriple=powerpc64le-unknown-unknown \
+; RUN:   -verify-machineinstrs < %s | FileCheck %s
+define signext i32 @test(i32* noalias %PtrA, i32* noalias %PtrB, i32 signext %LenA, i32 signext %LenB) #0 {
+; CHECK-LABEL: test:
+; CHECK-NOT: mtctr
+; CHECK-NOT: bdnz
+; CHECK-NOT: bdz
+; CHECK:     blr
+entry:
+  br label %block2
+
+block2:                                           ; preds = %entry
+  br label %block3
+
+block3:                                           ; preds = %block8, %block2
+  %OuterInd.0 = phi i32 [ 0, %block2 ], [ %inc, %block8 ]
+  %InnerInd.0 = phi i32 [ 0, %block2 ], [ %inc1, %block8 ]
+  %inc = add nsw i32 %OuterInd.0, 1
+  br label %block4
+
+block4:                                           ; preds = %if.then4, %block3
+  %InnerInd.1 = phi i32 [ %InnerInd.0, %block3 ], [ %inc1, %if.then4 ]
+  %cmp = icmp sge i32 %inc, %LenA
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %block4
+  %sub = sub nsw i32 %inc, 1
+  %idxprom = sext i32 %sub to i64
+  %arrayidx = getelementptr inbounds i32, i32* %PtrA, i64 %idxprom
+  %0 = load i32, i32* %arrayidx, align 4
+  ret i32 %0
+
+if.end:                                           ; preds = %block4
+  br label %block5
+
+block5:                                           ; preds = %if.end
+  %inc1 = add nsw i32 %InnerInd.1, 1
+  %idxprom2 = sext i32 %InnerInd.1 to i64
+  %arrayidx3 = getelementptr inbounds i32, i32* %PtrB, i64 %idxprom2
+  %1 = load i32, i32* %arrayidx3, align 4
+  %tobool = icmp ne i32 %1, 0
+  br i1 %tobool, label %if.then4, label %if.end9
+
+if.then4:                                         ; preds = %block5
+  %idxprom5 = sext i32 %inc to i64
+  %arrayidx6 = getelementptr inbounds i32, i32* %PtrA, i64 %idxprom5
+  %2 = load i32, i32* %arrayidx6, align 4
+  %idxprom7 = sext i32 %inc1 to i64
+  %arrayidx8 = getelementptr inbounds i32, i32* %PtrB, i64 %idxprom7
+  store i32 %2, i32* %arrayidx8, align 4
+  br label %block4
+
+if.end9:                                          ; preds = %block5
+  br label %block6
+
+block6:                                           ; preds = %if.end9
+  %idxprom10 = sext i32 %inc to i64
+  %arrayidx11 = getelementptr inbounds i32, i32* %PtrA, i64 %idxprom10
+  %3 = load i32, i32* %arrayidx11, align 4
+  %inc12 = add nsw i32 %3, 1
+  store i32 %inc12, i32* %arrayidx11, align 4
+  br label %block8
+
+block8:                                           ; preds = %block6
+  br label %block3
+}