[LSR] Return nullptr from getExpr if the result isn't invertible.

[fhahn]

Summary

getExpr is missing a check to make sure the result is invertible.
This can lead to incorrect results, so return nullptr in those cases
like in other places in IVUsers.

Fixes #62660.

[qcolombet]

I was wondering if we should have a separate isInvertible API and keep getExpr as is, but a glance at how getExpr is used everywhere tells me that's probably overkill.

LGTM

[nikic]

Can we change normalizeForPostIncUse() to return nullptr if it does not round trip, so that all users are forced to handle this? Pretty sure this is still going to leave holes behind.

[fhahn]

In D153202#4431951, @nikic wrote:

Can we change normalizeForPostIncUse() to return nullptr if it does not round trip, so that all users are forced to handle this? Pretty sure this is still going to leave holes behind.

This is something I tried, but the fallout seemed quite big (in terms of test changes) so I think it would be better to incrementally make things stricter.

[fhahn]

Rebased on top of current main, I am planning on landing this shortly as first step

llvm/include/llvm/Analysis/IVUsers.h

public:
   bool AddUsersIfInteresting(Instruction *I);
 
   IVStrideUse &AddUser(Instruction *User, Value *Operand);
 
   /// getReplacementExpr - Return a SCEV expression which computes the
   /// value of the OperandValToReplace of the given IVStrideUse.
   const SCEV *getReplacementExpr(const IVStrideUse &IU) const;
 
-  /// getExpr - Return the expression for the use.
+  /// getExpr - Return the expression for the use. Returns nullptr if the result
+  /// is not invertible.
   const SCEV *getExpr(const IVStrideUse &IU) const;
 
   const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const;
 
   typedef ilist<IVStrideUse>::iterator iterator;
   typedef ilist<IVStrideUse>::const_iterator const_iterator;
   iterator begin() { return IVUses.begin(); }
   iterator end()   { return IVUses.end(); }

llvm/lib/Analysis/IVUsers.cpp

 /// getReplacementExpr - Return a SCEV expression which computes the
 /// value of the OperandValToReplace.
 const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const {
   return SE->getSCEV(IU.getOperandValToReplace());
 }
 
 /// getExpr - Return the expression for the use.
 const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {
-  return normalizeForPostIncUse(getReplacementExpr(IU), IU.getPostIncLoops(),
-                                *SE);
+  const SCEV *Replacement = getReplacementExpr(IU);
+  const SCEV *Normalized =
+      normalizeForPostIncUse(Replacement, IU.getPostIncLoops(), *SE);
+  const SCEV *Denormalized =
+      denormalizeForPostIncUse(Normalized, IU.getPostIncLoops(), *SE);
+  // If the normalized expression isn't invertible.
+  if (Denormalized != Replacement)
+    return nullptr;
+  return Normalized;
 }
 
 static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
     if (AR->getLoop() == L)
       return AR;
     return findAddRecForLoop(AR->getStart(), L);
   }

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

 
 void LSRInstance::CollectInterestingTypesAndFactors() {
   SmallSetVector<const SCEV *, 4> Strides;
 
   // Collect interesting types and strides.
   SmallVector<const SCEV *, 4> Worklist;
   for (const IVStrideUse &U : IU) {
     const SCEV *Expr = IU.getExpr(U);
+    if (!Expr)
+      continue;
 
     // Collect interesting types.
     Types.insert(SE.getEffectiveSCEVType(Expr->getType()));
 
     // Add strides for mentioned loops.
     Worklist.push_back(Expr);
     do {
       const SCEV *S = Worklist.pop_back_val();
for (const IVStrideUse &U : IU) {
     LSRUse::KindType Kind = LSRUse::Basic;
     MemAccessTy AccessTy;
     if (isAddressUse(TTI, UserInst, U.getOperandValToReplace())) {
       Kind = LSRUse::Address;
       AccessTy = getAccessType(TTI, UserInst, U.getOperandValToReplace());
     }
 
     const SCEV *S = IU.getExpr(U);
+    if (!S)
+      continue;
     PostIncLoopSet TmpPostIncLoops = U.getPostIncLoops();
 
     // Equality (== and !=) ICmps are special. We can rewrite (i == N) as
     // (N - i == 0), and this allows (N - i) to be the expression that we work
     // with rather than just N or i, so we can consider the register
     // requirements for both N and i at the same time. Limiting this code to
     // equality icmps is not a problem because all interesting loops use
     // equality icmps, thanks to IndVarSimplify.

llvm/test/Transforms/LoopStrengthReduce/X86/pr62660-normalization-failure.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt -loop-reduce -verify-scev -S %s | FileCheck %s
 
-; XFAIL: *
-; REQUIRES: asserts
-
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macos"
 
 define i64 @test_pr62660() {
 ; CHECK-LABEL: define i64 @test_pr62660() {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[LSR_IV1:%.*]] = phi i32 [ [[LSR_IV_NEXT2:%.*]], [[LOOP]] ], [ 65533, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i64 [ [[LSR_IV_NEXT:%.*]], [[LOOP]] ], [ -1, [[ENTRY]] ]
+; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i64 [ [[LSR_IV_NEXT:%.*]], [[LOOP]] ], [ -1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[LSR_IV]], 1
+; CHECK-NEXT:    [[TMP:%.*]] = trunc i64 [[TMP0]] to i32
+; CHECK-NEXT:    [[CONV1:%.*]] = and i32 [[TMP]], 65535
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[IV]], -1
+; CHECK-NEXT:    [[SUB:%.*]] = add i32 [[ADD]], [[CONV1]]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[LSR_IV_NEXT]] = add nsw i64 [[LSR_IV]], 1
-; CHECK-NEXT:    [[LSR_IV_NEXT2]] = add nuw nsw i32 [[LSR_IV1]], 2
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[LSR_IV_NEXT2]], 8
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[SUB]], 8
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i64 [[LSR_IV_NEXT]]
 ;
 entry:
   br label %loop
 
 loop:

llvm/test/Transforms/LoopStrengthReduce/scaling-factor-incompat-type.ll

 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[BB4:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[T3:%.*]] = ashr i64 [[LSR_IV_NEXT:%.*]], 32
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb4:
 ; CHECK-NEXT:    [[LSR_IV1:%.*]] = phi i16 [ [[LSR_IV_NEXT2:%.*]], [[BB13:%.*]] ], [ 6, [[BB:%.*]] ]
 ; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i64 [ [[LSR_IV_NEXT]], [[BB13]] ], [ 8589934593, [[BB]] ]
+; CHECK-NEXT:    [[T5:%.*]] = phi i64 [ 2, [[BB]] ], [ [[T14:%.*]], [[BB13]] ]
+; CHECK-NEXT:    [[T6:%.*]] = add i64 [[T5]], 4
+; CHECK-NEXT:    [[T7:%.*]] = trunc i64 [[T6]] to i16
+; CHECK-NEXT:    [[T8:%.*]] = urem i16 [[T7]], 3
+; CHECK-NEXT:    [[T9:%.*]] = mul i16 [[T8]], 2
 ; CHECK-NEXT:    [[LSR_IV_NEXT]] = add nuw nsw i64 [[LSR_IV]], 25769803776
 ; CHECK-NEXT:    [[LSR_IV_NEXT2]] = add nuw nsw i16 [[LSR_IV1]], 6
-; CHECK-NEXT:    [[T10:%.*]] = icmp eq i16 1, 0
+; CHECK-NEXT:    [[T14]] = add nuw nsw i64 [[T5]], 6
+; CHECK-NEXT:    [[T10:%.*]] = icmp eq i16 [[T9]], 1
 ; CHECK-NEXT:    br i1 [[T10]], label [[BB11:%.*]], label [[BB13]]
 ; CHECK:       bb11:
 ; CHECK-NEXT:    [[T12:%.*]] = udiv i16 1, [[LSR_IV1]]
 ; CHECK-NEXT:    unreachable
 ; CHECK:       bb13:
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB4]]
 ;
 bb: