[InstCombine]: Add tests for icmp ne non-zero power of 2; NFC

[nikic]

Generally looks fine, but I would omit most of the tests on different bitwidths. Sometime we have one test for a different bitwidth (picking something weird like i13) to show that it doesn't matter, but otherwise testing just a single small bitwidth like i8 or i16 is enough (small bitwidth preferred to avoid alive2 timeouts). Not going to insist though.

I'm assuming the non-constant tests are there for the sake of completeness, and there is no intent to support them.

llvm/test/Transforms/InstCombine/icmp-ne-pow2.ll

332 ↗

(On Diff #487888)

Not sure I understand the significance of this test. It seems like the same as the previous with this extra assume, but why is it relevant?

354 ↗

(On Diff #487888)

Doing something like ule 1 would be more meaningful, in that it is "nearly" pow2.

[goldstein.w.n]

Add ule ctpop test case

[goldstein.w.n]

In D141412#4041223, @nikic wrote:

Generally looks fine, but I would omit most of the tests on different bitwidths. Sometime we have one test for a different bitwidth (picking something weird like i13) to show that it doesn't matter, but otherwise testing just a single small bitwidth like i8 or i16 is enough (small bitwidth preferred to avoid alive2 timeouts). Not going to insist though.

Prefer more tests for the simple cases, the patch to not-break sign-extension by shrinking bitwidth "passing" b.c
tests lacked variety in constants / type has pretty much convinced its worth over testing with slight variation. So,
if its all the same would like to keep. But your the maintainer so LMK.

I'm assuming the non-constant tests are there for the sake of completeness, and there is no intent to support them.

Nothing in the works to support them now, but I think they should be supportable. They aren't going to be covered by
any of the patches I have out now but plan to revisit. Since they cover the same logic okay to keep?

llvm/test/Transforms/InstCombine/icmp-ne-pow2.ll

332 ↗

(On Diff #487888)

Not sure I understand the significance of this test. It seems like the same as the previous with this extra assume, but why is it relevant?

if (Pow2(Y) && Y > X)
   X & Y -> 0

354 ↗

(On Diff #487888)

Doing something like ule 1 would be more meaningful, in that it is "nearly" pow2.

Adding as seperate test. See: pow2_or_zero_32_nonconst_assume_br

That changes the evaluation.

if (Pow2OrZero(Y) && (Y & X) != 0)
    X & Y -> Y

whereas just ne 1 can't modify Y & X

[nikic]

In D141412#4041351, @goldstein.w.n wrote:

In D141412#4041223, @nikic wrote:

Generally looks fine, but I would omit most of the tests on different bitwidths. Sometime we have one test for a different bitwidth (picking something weird like i13) to show that it doesn't matter, but otherwise testing just a single small bitwidth like i8 or i16 is enough (small bitwidth preferred to avoid alive2 timeouts). Not going to insist though.

Prefer more tests for the simple cases, the patch to not-break sign-extension by shrinking bitwidth "passing" b.c
tests lacked variety in constants / type has pretty much convinced its worth over testing with slight variation. So,
if its all the same would like to keep. But your the maintainer so LMK.

Fair enough.

I'm assuming the non-constant tests are there for the sake of completeness, and there is no intent to support them.

Nothing in the works to support them now, but I think they should be supportable. They aren't going to be covered by
any of the patches I have out now but plan to revisit. Since they cover the same logic okay to keep?

Sure, having the tests makes sense. But unless there's an actual motivating case, I don't think supporting those is worthwhile.

llvm/test/Transforms/InstCombine/icmp-ne-pow2.ll

332 ↗

(On Diff #487888)

In that case, shouldn't the assume below this be dropped? Otherwise that's a contradiction.

354 ↗

(On Diff #487888)

Good point.

[goldstein.w.n]

Fix inconsistent test

[goldstein.w.n]

Fix inconsisntent test (forgot to apply last time)

[goldstein.w.n]

llvm/test/Transforms/InstCombine/icmp-ne-pow2.ll

332 ↗

(On Diff #487888)

In that case, shouldn't the assume below this be dropped? Otherwise that's a contradiction.

You're right, done in V3.

[goldstein.w.n]

Assume for for ule as well

[nikic]

Landed as 8c9f13bd4c0fddacfea2d3dfd5af532c40656505.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

if (PHINode *PN = dyn_cast<PHINode>(LF.UserInst)) {
     else
       LF.UserInst->replaceUsesOfWith(LF.OperandValToReplace, FullV);
   }
 
   if (auto *OperandIsInstr = dyn_cast<Instruction>(LF.OperandValToReplace))
     DeadInsts.emplace_back(OperandIsInstr);
 }
 
-// Trying to hoist the IVInc to loop header if all IVInc users are in
-// the loop header. It will help backend to generate post index load/store
-// when the latch block is different from loop header block.
-static bool canHoistIVInc(const TargetTransformInfo &TTI, const LSRFixup &Fixup,
-                          const LSRUse &LU, Instruction *IVIncInsertPos,
-                          Loop *L) {
-  if (LU.Kind != LSRUse::Address)
-    return false;
-
-  // For now this code do the conservative optimization, only work for
-  // the header block. Later we can hoist the IVInc to the block post
-  // dominate all users.
-  BasicBlock *LHeader = L->getHeader();
-  if (IVIncInsertPos->getParent() == LHeader)
-    return false;
-
-  if (!Fixup.OperandValToReplace ||
-      any_of(Fixup.OperandValToReplace->users(), [&LHeader](User *U) {
-        Instruction *UI = cast<Instruction>(U);
-        return UI->getParent() != LHeader;
-      }))
-    return false;
-
-  Instruction *I = Fixup.UserInst;
-  return (isa<LoadInst>(I) &&
-          TTI.isIndexedLoadLegal(TTI.MIM_PostInc, I->getType())) ||
-         (isa<StoreInst>(I) &&
-          TTI.isIndexedStoreLegal(TTI.MIM_PostInc, I->getType()));
-}
-
 /// Rewrite all the fixup locations with new values, following the chosen
 /// solution.
 void LSRInstance::ImplementSolution(
     const SmallVectorImpl<const Formula *> &Solution) {
   // Keep track of instructions we may have made dead, so that
   // we can remove them after we are done working.
   SmallVector<WeakTrackingVH, 16> DeadInsts;
 
+  Rewriter.setIVIncInsertPos(L, IVIncInsertPos);
+
   // Mark phi nodes that terminate chains so the expander tries to reuse them.
   for (const IVChain &Chain : IVChainVec) {
     if (PHINode *PN = dyn_cast<PHINode>(Chain.tailUserInst()))
       Rewriter.setChainedPhi(PN);
   }
 
   // Expand the new value definitions and update the users.
   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx)
     for (const LSRFixup &Fixup : Uses[LUIdx].Fixups) {
-      Instruction *InsertPos =
-          canHoistIVInc(TTI, Fixup, Uses[LUIdx], IVIncInsertPos, L)
-              ? L->getHeader()->getTerminator()
-              : IVIncInsertPos;
-      Rewriter.setIVIncInsertPos(L, InsertPos);
       Rewrite(Uses[LUIdx], Fixup, *Solution[LUIdx], DeadInsts);
       Changed = true;
     }
 
   for (const IVChain &Chain : IVChainVec) {
     GenerateIVChain(Chain, DeadInsts);
     Changed = true;
   }

llvm/test/Transforms/LoopStrengthReduce/AArch64/pr53625.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=aarch64-unknown-unknown | FileCheck %s
 
 target datalayout = "e-m:w-p:64:64-i32:32-i64:64-i128:128-n32:64-S128"
 
 ; we need to generate post index load for this case
 define i32 @test(i32 %c, ptr %a, ptr %b) {
 ; CHECK-LABEL: test:
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    cmp w0, #1
 ; CHECK-NEXT:    b.lt .LBB0_4
 ; CHECK-NEXT:  // %bb.1: // %for.body.preheader
 ; CHECK-NEXT:    mov w8, w0
 ; CHECK-NEXT:  .LBB0_2: // %for.body
 ; CHECK-NEXT:    // =>This Inner Loop Header: Depth=1
-; CHECK-NEXT:    ldr w9, [x1], #4
+; CHECK-NEXT:    ldr w9, [x1]
 ; CHECK-NEXT:    cbnz w9, .LBB0_5
 ; CHECK-NEXT:  // %bb.3: // %for.cond
 ; CHECK-NEXT:    // in Loop: Header=BB0_2 Depth=1
+; CHECK-NEXT:    add x1, x1, #4
 ; CHECK-NEXT:    subs x8, x8, #1
 ; CHECK-NEXT:    b.ne .LBB0_2
 ; CHECK-NEXT:  .LBB0_4:
 ; CHECK-NEXT:    mov w0, wzr
 ; CHECK-NEXT:    ret
 ; CHECK-NEXT:  .LBB0_5:
 ; CHECK-NEXT:    mov w0, #1
 ; CHECK-NEXT:    ret
 entry:
   %cmp13 = icmp sgt i32 %c, 0
   br i1 %cmp13, label %for.body.preheader, label %return
 
 for.body.preheader:                               ; preds = %entry
   %wide.trip.count = zext i32 %c to i64
   br label %for.body
 
 for.cond:                                         ; preds = %for.body
-  %iv.next = add nuw nsw i64 %iv, 1
-  %exitcond.not = icmp eq i64 %iv.next, %wide.trip.count
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond.not = icmp eq i64 %indvars.iv.next, %wide.trip.count
   br i1 %exitcond.not, label %return, label %for.body
 
 for.body:                                         ; preds = %for.body.preheader, %for.cond
-  %iv = phi i64 [ 0, %for.body.preheader ], [ %iv.next, %for.cond ]
-  %arrayidx = getelementptr inbounds i32, ptr %a, i64 %iv
+  %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.cond ]
+  %arrayidx = getelementptr inbounds i32, ptr %a, i64 %indvars.iv
   %val = load i32, ptr %arrayidx, align 4
   %tobool3.not = icmp eq i32 %val, 0
   br i1 %tobool3.not, label %for.cond, label %return
 
 return:                                           ; preds = %for.cond, %for.body, %entry
   %retval.1 = phi i32 [ 0, %entry ], [ 0, %for.cond ], [ 1, %for.body ]
   ret i32 %retval.1
 }
-
-; negative case: %arrayidx.b is not in header
-
-define i64 @IVIncHoist_not_all_user_in_header(i32 %c, ptr %a, ptr %b) {
-; CHECK-LABEL: IVIncHoist_not_all_user_in_header:
-; CHECK:       // %bb.0: // %entry
-; CHECK-NEXT:    cmp w0, #1
-; CHECK-NEXT:    b.lt .LBB1_5
-; CHECK-NEXT:  // %bb.1: // %for.body.preheader
-; CHECK-NEXT:    mov x8, xzr
-; CHECK-NEXT:    mov w9, w0
-; CHECK-NEXT:    add x10, x1, #4
-; CHECK-NEXT:    add x11, x2, #8
-; CHECK-NEXT:    mov w0, #1
-; CHECK-NEXT:  .LBB1_2: // %for.body
-; CHECK-NEXT:    // =>This Inner Loop Header: Depth=1
-; CHECK-NEXT:    ldr w12, [x10, x8, lsl #2]
-; CHECK-NEXT:    cbnz w12, .LBB1_7
-; CHECK-NEXT:  // %bb.3: // %if.then
-; CHECK-NEXT:    // in Loop: Header=BB1_2 Depth=1
-; CHECK-NEXT:    ldr w12, [x11, x8, lsl #2]
-; CHECK-NEXT:    cbnz w12, .LBB1_6
-; CHECK-NEXT:  // %bb.4: // %for.cond
-; CHECK-NEXT:    // in Loop: Header=BB1_2 Depth=1
-; CHECK-NEXT:    add x8, x8, #1
-; CHECK-NEXT:    cmp x9, x8
-; CHECK-NEXT:    b.ne .LBB1_2
-; CHECK-NEXT:  .LBB1_5:
-; CHECK-NEXT:    mov x0, xzr
-; CHECK-NEXT:    ret
-; CHECK-NEXT:  .LBB1_6: // %if.then.return.loopexit_crit_edge
-; CHECK-NEXT:    add x0, x8, #3
-; CHECK-NEXT:  .LBB1_7: // %return
-; CHECK-NEXT:    ret
-entry:
-  %cmp13 = icmp sgt i32 %c, 0
-  br i1 %cmp13, label %for.body.preheader, label %return
-
-for.body.preheader:                               ; preds = %entry
-  %wide.trip.count = zext i32 %c to i64
-  br label %for.body
-
-for.cond:                                         ; preds = %for.body
-  %iv.next = add nuw nsw i64 %iv, 1
-  %exitcond.not = icmp eq i64 %iv.next, %wide.trip.count
-  br i1 %exitcond.not, label %return, label %for.body
-
-for.body:                                         ; preds = %for.body.preheader, %for.cond
-  %iv = phi i64 [ 0, %for.body.preheader ], [ %iv.next, %for.cond ]
-  %iv.a = phi i64 [ 1, %for.body.preheader ], [ %iv.next.a, %for.cond ]
-  %iv.b = phi i64 [ 2, %for.body.preheader ], [ %iv.next.b, %for.cond ]
-  %arrayidx.a = getelementptr inbounds i32, ptr %a, i64 %iv.a
-  %iv.next.a = add nuw nsw i64 %iv.a, 1
-  %val.a = load i32, ptr %arrayidx.a, align 4
-  %tobool3.not = icmp eq i32 %val.a, 0
-  br i1 %tobool3.not, label %if.then, label %return
-
-if.then:
-  %arrayidx.b = getelementptr inbounds i32, ptr %b, i64 %iv.b
-  %iv.next.b = add nuw nsw i64 %iv.b, 1
-  %val.b = load i32, ptr %arrayidx.b, align 4
-  %tobool4.not = icmp eq i32 %val.b, 0
-  br i1 %tobool4.not, label %for.cond, label %return
-
-return:                                           ; preds = %for.cond, %for.body, %entry
-  %retval.1 = phi i64 [ 0, %entry ], [ 0, %for.cond ], [ 1, %for.body ], [ %iv.next.b, %if.then ]
-  ret i64 %retval.1
-}