[LoopFlatten] Loop limit invariant checks

[SjoerdMeijer]

Summary

If the loop limit is not invariant don't directly bail out, but try to make it invariant with makeLoopInvariant.
I precommitted the test case for this in rG20c7ab87a78c.

[dmgreen]

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

439

All these return false now need to return Changed, I think.

llvm/test/Transforms/LoopFlatten/limit-not-invariant.ll

14

These tests don't then flatten?

[SjoerdMeijer]

llvm/test/Transforms/LoopFlatten/limit-not-invariant.ll

14

Well spotted. This patch was part of my grand master plan to support different phi types, and this patch was to get the first little obstacle out of the way. But because of changes in D88880, the input IR and test case might not be so relevant anymore, so I will look at that first now because I still think this is little change is useful.

[fhahn]

(marking as changes requested to clear up review queue as there are outstanding comments)

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

431

Update the comment saying we try to make it invariant?

432

does this need to be initialized? I think there might be some code paths in makeLoopInvariant that do not set Changed.

llvm/lib/Transforms/Scalar/LoopFlatten.cpp

static bool FlattenLoopPair(Loop *OuterLoop, Loop *InnerLoop, DominatorTree *DT,
   if (!findLoopComponents(InnerLoop, IterationInstructions, InnerInductionPHI,
                           InnerLimit, InnerIncrement, InnerBranch, SE))
     return false;
   if (!findLoopComponents(OuterLoop, IterationInstructions, OuterInductionPHI,
                           OuterLimit, OuterIncrement, OuterBranch, SE))
     return false;
 
   // Both of the loop limit values must be invariant in the outer loop
   // (non-instructions are all inherently invariant).
-  if (!OuterLoop->isLoopInvariant(InnerLimit)) {
+  bool Changed;
+  if (!OuterLoop->makeLoopInvariant(InnerLimit, Changed)) {
     LLVM_DEBUG(dbgs() << "inner loop limit not invariant\n");
     return false;
   }
-  if (!OuterLoop->isLoopInvariant(OuterLimit)) {
+  if (!OuterLoop->makeLoopInvariant(OuterLimit, Changed)) {
     LLVM_DEBUG(dbgs() << "outer loop limit not invariant\n");
     return false;
   }
 
   SmallPtrSet<PHINode *, 4> InnerPHIsToTransform;
   if (!checkPHIs(OuterLoop, InnerLoop, InnerPHIsToTransform, InnerInductionPHI,
                  OuterInductionPHI, TTI))
     return false;
 
   // FIXME: it should be possible to handle different types correctly.

llvm/test/Transforms/LoopFlatten/limit-not-invariant.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 
 ; RUN: opt < %s -S -loop-flatten -verify-loop-info -verify-dom-info -verify-scev -verify | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 
 define dso_local void @inner_limit_not_invariant(i32 %N, i32* nocapture %C, i16* nocapture readonly %A, i16 %val) {
 ; CHECK-LABEL: @inner_limit_not_invariant(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP26_NOT:%.*]] = icmp eq i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP26_NOT]], label [[FOR_END12:%.*]], label [[FOR_COND1_PREHEADER_LR_PH:%.*]]
 ; CHECK:       for.cond1.preheader.lr.ph:
 ; CHECK-NEXT:    [[CONV4:%.*]] = sext i16 [[VAL:%.*]] to i32
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
 ; CHECK-NEXT:    br label [[FOR_COND1_PREHEADER_US:%.*]]
 ; CHECK:       for.cond1.preheader.us:
 ; CHECK-NEXT:    [[I_027_US:%.*]] = phi i32 [ 0, [[FOR_COND1_PREHEADER_LR_PH]] ], [ [[INC11_US:%.*]], [[FOR_COND1_FOR_INC10_CRIT_EDGE_US:%.*]] ]
 ; CHECK-NEXT:    [[MUL_US:%.*]] = mul i32 [[I_027_US]], [[N]]
-; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
 ; CHECK-NEXT:    br label [[FOR_BODY3_US:%.*]]
 ; CHECK:       for.body3.us:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[FOR_COND1_PREHEADER_US]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY3_US]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 [[INDVARS_IV]] to i32
 ; CHECK-NEXT:    [[ADD_US:%.*]] = add i32 [[TMP0]], [[MUL_US]]
 ; CHECK-NEXT:    [[IDXPROM_US:%.*]] = zext i32 [[ADD_US]] to i64
 ; CHECK-NEXT:    [[ARRAYIDX_US:%.*]] = getelementptr inbounds i16, i16* [[A:%.*]], i64 [[IDXPROM_US]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i16, i16* [[ARRAYIDX_US]], align 2

 
 define dso_local void @outer_limit_not_invariant(i32 %N, i32* nocapture %C, i16* nocapture readonly %A, i16 %val, i64 %M) {
 ; CHECK-LABEL: @outer_limit_not_invariant(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP26_NOT:%.*]] = icmp eq i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP26_NOT]], label [[FOR_END12:%.*]], label [[FOR_COND1_PREHEADER_LR_PH:%.*]]
 ; CHECK:       for.cond1.preheader.lr.ph:
 ; CHECK-NEXT:    [[CONV4:%.*]] = sext i16 [[VAL:%.*]] to i32
+; CHECK-NEXT:    [[TRUNC_TRIP_COUNT:%.*]] = trunc i64 [[M:%.*]] to i32
 ; CHECK-NEXT:    br label [[FOR_COND1_PREHEADER_US:%.*]]
 ; CHECK:       for.cond1.preheader.us:
 ; CHECK-NEXT:    [[I_027_US:%.*]] = phi i32 [ 0, [[FOR_COND1_PREHEADER_LR_PH]] ], [ [[INC11_US:%.*]], [[FOR_COND1_FOR_INC10_CRIT_EDGE_US:%.*]] ]
 ; CHECK-NEXT:    [[MUL_US:%.*]] = mul i32 [[I_027_US]], [[N]]
-; CHECK-NEXT:    [[TRUNC_TRIP_COUNT:%.*]] = trunc i64 [[M:%.*]] to i32
 ; CHECK-NEXT:    br label [[FOR_BODY3_US:%.*]]
 ; CHECK:       for.body3.us:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[FOR_COND1_PREHEADER_US]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY3_US]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 [[INDVARS_IV]] to i32
 ; CHECK-NEXT:    [[ADD_US:%.*]] = add i32 [[TMP0]], [[MUL_US]]
 ; CHECK-NEXT:    [[IDXPROM_US:%.*]] = zext i32 [[ADD_US]] to i64
 ; CHECK-NEXT:    [[ARRAYIDX_US:%.*]] = getelementptr inbounds i16, i16* [[A:%.*]], i64 [[IDXPROM_US]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i16, i16* [[ARRAYIDX_US]], align 2