[LSR] Filter out zero factors. PR50765

[mkazantsev]

Summary

Zero factor leads to division by zero and failure of corresponding
assert as shown in PR50765. We should filter out such factors.

[lebedev.ri]

Not really familiar with this code, but sounds reasonable.

[fhahn]

This also fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=35400

[huihuiz]

Ideally we should reject early when stride is zero, but in this case we won't be able to detect this early since stride zero is in a form of add expression.

(((3 + (-1 * (74 smax (1 + %tmp3)))<nsw>)<nuw><nsw> * {(-2 + (-2 * (trunc i64 undef to i32))),+,-2}<%bb1>) + ((6 + (-2 * (74 smax (1 + %tmp3))))<nuw> * {(1 + (trunc i64 undef to i32)),+,1}<%bb1>))  // Zero stride as the LHS

After getExactSDiv pull out common factor 2 , then we get an add expression that turn out to be zero.

[reames]

LGTM to me as well.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

2713

Not a problem with this patch, but dang this code is suspicious. It appears to be wanting to check whether one factor divides another, but a) it's *asserting* the divide is exact, and b) it's discarding any remainder. That probably wasn't what was actually wanted here...

[mkazantsev]

In D104702#2833650, @huihuiz wrote:

Ideally we should reject early when stride is zero, but in this case we won't be able to detect this early since stride zero is in a form of add expression.

(((3 + (-1 * (74 smax (1 + %tmp3)))<nsw>)<nuw><nsw> * {(-2 + (-2 * (trunc i64 undef to i32))),+,-2}<%bb1>) + ((6 + (-2 * (74 smax (1 + %tmp3))))<nuw> * {(1 + (trunc i64 undef to i32)),+,1}<%bb1>))  // Zero stride as the LHS

After getExactSDiv pull out common factor 2 , then we get an add expression that turn out to be zero.

That's a point where we could try to improve SCEV. But generally, it's not correct to assume that SCEV will or will not fully simplify something. It has a lot of limitations, one of which is depth threshold which simply cuts the simplification process for sake of saving CT.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

for (SmallSetVector<const SCEV *, 4>::const_iterator NewStrideIter =
           SE.getTypeSizeInBits(NewStride->getType())) {
         if (SE.getTypeSizeInBits(OldStride->getType()) >
             SE.getTypeSizeInBits(NewStride->getType()))
           NewStride = SE.getSignExtendExpr(NewStride, OldStride->getType());
         else
           OldStride = SE.getSignExtendExpr(OldStride, NewStride->getType());
       }
       if (const SCEVConstant *Factor =
             dyn_cast_or_null<SCEVConstant>(getExactSDiv(NewStride, OldStride,
                                                         SE, true))) {
-        if (Factor->getAPInt().getMinSignedBits() <= 64)
+        if (Factor->getAPInt().getMinSignedBits() <= 64 && !Factor->isZero())
           Factors.insert(Factor->getAPInt().getSExtValue());
       } else if (const SCEVConstant *Factor =
                    dyn_cast_or_null<SCEVConstant>(getExactSDiv(OldStride,
                                                                NewStride,
                                                                SE, true))) {
-        if (Factor->getAPInt().getMinSignedBits() <= 64)
+        if (Factor->getAPInt().getMinSignedBits() <= 64 && !Factor->isZero())
           Factors.insert(Factor->getAPInt().getSExtValue());
       }
     }
 
   // If all uses use the same type, don't bother looking for truncation-based
   // reuse.
   if (Types.size() == 1)
     Types.clear();

llvm/test/Transforms/LoopStrengthReduce/pr50765.ll

 ; RUN: opt -S -loop-reduce < %s | FileCheck %s
-; XFAIL: *
-; REQUIRES: asserts
 ;
 ;This test produces zero factor that becomes a denumerator and fails an assetion.
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @test() {
 ; CHECK-LABEL: test