[IndVarSimplify] Eliminate zext of a signed IV when the IV is known to be non-negative

[lihuang]

Summary

[IndVarSimplify] Eliminate zext of a signed IV when widening if the IV is known to be non-negative.

This was part of a previous diff (D18777), now separated into a new diff. This change eliminates zexts of IV when IV is treated as signed and is known to be non-negative.

The change in D18777 will fail a front-end test (Frontend/optimization-remark-options.c) and this change should fix this test.

[reames]

Test case? Mandatory.

Drive by comments. I'll defer actual review to Sanjoy or someone more comfortable with this code. If you haven't gotten a review within a reasonable time frame (1 week), feel free to ping me directly and I'll take another look and rebuild my mental model of this code to be able to review..

lib/Transforms/Scalar/IndVarSimplify.cpp

1402

Remove explicit value of default param.

[lihuang]

Add a test to this change.

[mbodart]

lib/Transforms/Scalar/IndVarSimplify.cpp

1309

The new check for isa<ZExtInst> seems unnecessary.
If DU.NeverNegative is true, it means DU.WideDef will have zeroes
in its upper bits regardless of whether it was created with a Zext or Sext.

This is the first time I've looked at this code, so I don't know if you can
simply delete this part of the check, or if you must at least verify
that DU.NarrowUse is some flavor of Extend (as opposed to an
arbitrary instruction).

1402

While the change seems correct, it raises the question of why isKnownPredicate is not
catching this case. Have you looked into that?

[sanjoy]

+1 to both comments by @mbodart

Specifically with regards to the isKnownNonNegative comment: if isKnownPredicate is failing here, you might consider teaching it to use getSignedRange internally, since the range SCEV computes for %i.0 is [0,-2147483648) (all positive integers) so we should be able to use that information.

[lihuang]

Sorry for the late reply, took sick days.

I spent some time looking at the ScalarEvolution code. isKnownPredicate doesn't catch this case because when creating SCEV from an instruction, the "nsw" flag of the instruction is not propagated to the SCEV. For example, the case in the added test:

        %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
        ... 
        %add = add nsw i32 %i.0, 2
        ...
        %inc = add nsw i32 %i.0, 1

When creating SCEV for %add from "%add = add nsw i32 %i.0, 2", the "nsw" flag is lost so it's not recognized as non-negative. The code that rules out this flag is in getNoWrapFlagsFromUB(), which is introduced in http://reviews.llvm.org/D11212 . I'm not very familiar with the SCEV code, so I'm not sure if the flag propagation in SCEV is supposed to propagate "nsw" in this case. If the flag propagation is correct, then we might need to use isKnownNonNegative from ValueTracking.

What do you suggest?

[lihuang]

lib/Transforms/Scalar/IndVarSimplify.cpp

1309

You are right, the DU.WideDef's upper bits will be zeros whether it was from a Zext or Sext. Here we need to verify that DU.NarrowUse is a Zext or Sext. I changed the checks here to include the 4 possible cases:

1. DU.NarrowUse is a Sext, WideIV is signed,
2. DU.NarrowUse is a Sext, WideIV is unsigned, but DU.NeverNegative is true
3. DU.NarrowUse is a Zext, WideIV is unsigned,
4. DU.NarrowUse is a Zext, WideIV is signed, but DU.NeverNegative is true

added one more test for case 2.

[mbodart]

lib/Transforms/Scalar/IndVarSimplify.cpp

1309

This looks great.
I'll defer to the other reviewers on the isKnownPredicate issue.

[lihuang]

Ping :)

Hi Sanjoy and Philip,

For the NeverNegative issue, are you okay with using isKnownNonNegative? Or you think we should modify SCEV code to make isKnownPredicate work for this case.

Thanks!

[lihuang]

I looked at the threads on llvm-dev discussing the no-wrap flag propagation issues. It seems like this has been a problem for a while and there is not a clear agreement on when and how to propagate no-wrap flags from instructions to corresponding SCEVs.

The problem in this case could be easily solved by propagating "nsw" flag of "%add = add nsw i32 %i.0, 2" to it's SCEV. It's not possible to infer the "nsw" flag for this SCEV. As %i.0 has range [0,-2147483648), "%i.0 + 2" could cause signed-overflow.

Sanjoy, I see you are actively contributing to SCEV. Do you know the community's plan on strengthening the no-wrap flag propagation? The tests I added here might not serve as a very good motivation for the effort but I think this will generally benefit SCEV and some optimizations depending on SCEV.

Thanks!

[sanjoy]

Hi!

Firstly, apologies for letting this set for so long.

In D18867#458868, @lihuang wrote:

I looked at the threads on llvm-dev discussing the no-wrap flag
propagation issues. It seems like this has been a problem for a while
and there is not a clear agreement on when and how to propagate
no-wrap flags from instructions to corresponding SCEVs.

The problem in this case could be easily solved by propagating "nsw"
flag of "%add = add nsw i32 %i.0, 2" to it's SCEV. It's not possible
to infer the "nsw" flag for this SCEV. As %i.0 has range
[0,-2147483648), "%i.0 + 2" could cause signed-overflow.

Sanjoy, I see you are actively contributing to SCEV. Do you know the
community's plan on strengthening the no-wrap flag propagation? The
tests I added here might not serve as a very good motivation for the
effort but I think this will generally benefit SCEV and some
optimizations depending on SCEV.

You're on the right track -- in many cases SCEV cannot propagate
no-wrap flags from the instruction to the SCEV expression. However,
the test cases as written don't work with isKnownPredicate because
the loops are not in canonical form, and not because of some
fundamental reason. If I run -loop-rotate on them (possibly
followed by -loop-simplifycfg) then your patch minus the
isKnownNonNegative bit does the right thing.

So I'd suggest checking if (in your pass pipeline) you're
canonicalizing the loops before passing them to -indvars. If you
are and are still facing issues, then it is fine to use
isKnownNonNegative here (since there _is_ a shortcoming in
ScalarEvolution::isKnownPredicate) with test cases that
fundamentally require isKnownNonNegative (and don't work with
ScalarEvolution::isKnownPredicate even on rotated loops).

[lihuang]

Using -loop-rotate works for these cases, as the "%add = add nsw i32 %i.0, 2" is brought to loop header and "nsw" is propagated. Thank you Sanjoy!

[lihuang]

Removed the isKnownNonNegative part, created a new file for the 2 tests. As Sanjoy pointed out, isKnownPredicate didn't work with these cases because the loops are not in canonical form. Using loop-rotate before indvars solves the issue.

[lihuang]

Actually, adding -loop-rotate just happens to work for this case, it doesn't solve the fundamental problem. For example, adding -loop-rotate or other loop pass sequences doesn't help with the case in D21773

[lihuang]

In D18867#403728, @sanjoy wrote:

+1 to both comments by @mbodart

Specifically with regards to the isKnownNonNegative comment: if isKnownPredicate is failing here, you might consider teaching it to use getSignedRange internally, since the range SCEV computes for %i.0 is [0,-2147483648) (all positive integers) so we should be able to use that information.

Hi Sanjoy,

This thread is old but I hope you could remember, sorry about this.

For this old issue, I tried different solutions but think I really need to use isKnownNonNegative here, because isKnownPredicate doesn't work because of the discrepancy of "nsw" flag between instruction and SCEV. The "nsw" flag propagation in SCEV based on poison value analysis is very conservative and only considers full poison propagation, so it doesn't work for this case. Loosing the flag propagation condition might be controversial and potentially a lot of work. The issues here could be easily solved by using isKnownNonNegative, which also solves the issue in D21773 which blocks D18777 and r274098.

Is there a strong reason against using ValueTracking's isKnownNonNegative here?

Thanks,
Li Huang

[sanjoy]

Hi @lihuang,

Using isKnownNonNegative is fine, but please add a comment stating
why you're doing that (to work around conservatism in
ScalarEvolution around no-wrap flags).

[lihuang]

Hi Sanjoy,

Are you okay with the new change? I have added the comment as you asked. I also rebased the ValueTracking change in D18777 on the latest source.

[lihuang]

Ping :)

[sanjoy]

lgtm

lib/Transforms/Scalar/IndVarSimplify.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
if (LI->getLoopFor(UsePhi->getParent()) != L) {
         DeadInsts.emplace_back(UsePhi);
         DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi
               << " to " << *WidePhi << "\n");
       }
       return nullptr;
     }
   }
   // Our raison d'etre! Eliminate sign and zero extension.
-  if (IsSigned ? isa<SExtInst>(DU.NarrowUse) : isa<ZExtInst>(DU.NarrowUse)) {
+  if ((IsSigned ? isa<SExtInst>(DU.NarrowUse) : isa<ZExtInst>(DU.NarrowUse)) ||
+      (isa<ZExtInst>(DU.NarrowUse) && DU.NeverNegative)) {
     Value *NewDef = DU.WideDef;
     if (DU.NarrowUse->getType() != WideType) {
       unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());
       unsigned IVWidth = SE->getTypeSizeInBits(WideType);
       if (CastWidth < IVWidth) {
         // The cast isn't as wide as the IV, so insert a Trunc.
         IRBuilder<> Builder(DU.NarrowUse);
         NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());

 }
 
 /// Add eligible users of NarrowDef to NarrowIVUsers.
 ///
 void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
   const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);
   bool NeverNegative =
       SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,
-                           SE->getConstant(NarrowSCEV->getType(), 0));
+                           SE->getConstant(NarrowSCEV->getType(), 0)) ||
+      isKnownNonNegative(NarrowDef, NarrowDef->getModule()->getDataLayout());
   for (User *U : NarrowDef->users()) {
     Instruction *NarrowUser = cast<Instruction>(U);
 
     // Handle data flow merges and bizarre phi cycles.
     if (!Widened.insert(NarrowUser).second)
       continue;
 
     NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef, NeverNegative);

test/Transforms/IndVarSimplify/iv-zext.ll

 ; RUN: opt < %s -indvars -S | FileCheck %s
-; CHECK-NOT: and
-; CHECK-NOT: zext
 
 target datalayout = "p:64:64:64-n32:64"
 
 define void @foo(double* %d, i64 %n) nounwind {
+; CHECK-LABEL: @foo(
+; CHECK-NOT: and
+; CHECK-NOT: zext
 entry:
   br label %loop
 
 loop:
   %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %loop ]
   %indvar.i8 = and i64 %indvar, 255
   %t0 = getelementptr double, double* %d, i64 %indvar.i8
   %t1 = load double, double* %t0
loop:
   store double %t8, double* %t6
   %indvar.next = add i64 %indvar, 1
   %exitcond = icmp eq i64 %indvar.next, 10
   br i1 %exitcond, label %return, label %loop
 
 return:
   ret void
 }
+
+; When widening IV, trunc and zext are not needed if the 
+; original 32-bit integer is known to be non-negative
+define void @foo1(i32* %A, i32* %B, i32* %C, i32 %N) {
+; CHECK-LABEL: @foo1(
+; CHECK-NOT: trunc
+; CHECK-NOT: zext
+entry:
+  br label %for.cond
+
+for.cond:                                      
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                    
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %B, i64 %idxprom
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %i.0, 1
+  %idxprom1 = zext i32 %add to i64
+  %arrayidx2 = getelementptr inbounds i32, i32* %C, i64 %idxprom1
+  %1 = load i32, i32* %arrayidx2, align 4
+  %add3 = add nsw i32 %0, %1
+  %idxprom4 = sext i32 %i.0 to i64
+  %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %idxprom4
+  store i32 %add3, i32* %arrayidx5, align 4
+  br label %for.inc
+
+for.inc:                                    
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                    
+  ret void
+}
+