[SCEV] Remove premature assert. PR46786

[mkazantsev]

Summary

This assert was added to verify assumption that GEP's SCEV will be of pointer type,
basing on fact that it should be a SCEVAddExpr with (at least) last operand being
pointer. Two notes:

• GEP's SCEV does not have to be a SCEVAddExpr after all simplifications;
• In current state, GEP's SCEV does not have to have at least one pointer operands (all of them can become int during the transforms).

However, we might want to be at a point where it is true. We are currently removing
this assert and will try to enumerate the cases where "is pointer" notion might be
lost during the transforms. When all of them are fixed, we can return it.

[lebedev.ri]

I'm obviously okay with dropping the assert until it actually doesn't trigger.

(copying from https://bugs.llvm.org/show_bug.cgi?id=46786#c8)

The question is, is "is pointer" a sticky bit or not?
In IR, GEP takes a pointer and produces a pointer.
In SCEV, as we can see, that's not really so.

In IR, if it ask GetUnderlyingObject() about some GEP,
it will recurse into the base pointer somewhat and return something.

In SCEV, if i ask SCEV::getPointerBase() about getSCEV(same GEP),
it will only try to recurse as long as there is exactly a single pointer operand.
So if GEP's SCEV somehow got folded in a way that obscured the fact that it produces a pointer,
i think there's an issue.

So here, i would actually think the problem is that the fix in D82633
was too narrow. Instead of fixing SCEVAddExpr::getType(), SCEVNAryExpr::getType()
should have been fixed, i believe that would resolve the assertion in this report.

[lebedev.ri]

FTR this patch was my plan forward anyways.

[mkazantsev]

I think we have some cases (related to mul) where "is pointer" notion can be lost. Maybe we can fix it. Let me try to construct some more examples of those.

Generally, the assert looks like we might have it, but first we should be certain that we ensure it is actually so. It might take some extensive work (I see some checks like "we do not work with pointer this or that" over the code).

Let me try to find more tests that fail this assert with educated guesses. Then I'll add them here, and then, when all of them are resolved, I'm fine with returning assert.

[mkazantsev]

I've updated commit message basing on our discussion. We want to be at a point when "is pointer" notion doesn't get lost. We are clearly not at this point now. We need to assess the amount of work we should do to get there, and construct more tests exercising different scenarios of this.

llvm/lib/Analysis/ScalarEvolution.cpp

if (StructType *STy = dyn_cast<StructType>(CurTy)) {
       const SCEV *LocalOffset = getMulExpr(IndexExpr, ElementSize, Wrap);
 
       // Add the element offset to the running total offset.
       TotalOffset = getAddExpr(TotalOffset, LocalOffset);
     }
   }
 
   // Add the total offset from all the GEP indices to the base.
-  auto *GEPExpr = getAddExpr(BaseExpr, TotalOffset, Wrap);
-  assert(BaseExpr->getType() == GEPExpr->getType() &&
-         "GEP should not change type mid-flight.");
-  return GEPExpr;
+  return getAddExpr(BaseExpr, TotalOffset, Wrap);
 }
 
 std::tuple<SCEV *, FoldingSetNodeID, void *>
 ScalarEvolution::findExistingSCEVInCache(int SCEVType,
                                          ArrayRef<const SCEV *> Ops) {
   FoldingSetNodeID ID;
   void *IP = nullptr;
   ID.AddInteger(SCEVType);

llvm/test/Analysis/ScalarEvolution/pr46786.ll

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt < %s -analyze -enable-new-pm=0 -scalar-evolution | FileCheck %s
+; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
+
+source_filename = "input.cpp"
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+
+; Function Attrs: nofree
+define i8* @FSE_decompress_usingDTable(i8* %arg, i32 %arg1, i32 %arg2, i32 %arg3) local_unnamed_addr #0 {
+; CHECK-LABEL: 'FSE_decompress_usingDTable'
+; CHECK-NEXT:  Classifying expressions for: @FSE_decompress_usingDTable
+; CHECK-NEXT:    %i = getelementptr inbounds i8, i8* %arg, i32 %arg2
+; CHECK-NEXT:    --> (%arg2 + %arg)<nsw> U: full-set S: full-set
+; CHECK-NEXT:    %i4 = sub nsw i32 0, %arg1
+; CHECK-NEXT:    --> (-1 * %arg1) U: full-set S: full-set
+; CHECK-NEXT:    %i5 = getelementptr inbounds i8, i8* %i, i32 %i4
+; CHECK-NEXT:    --> ((-1 * %arg1) + %arg2 + %arg) U: full-set S: full-set
+; CHECK-NEXT:    %i7 = select i1 %i6, i32 %arg2, i32 %arg1
+; CHECK-NEXT:    --> ((-1 * %arg) + (((-1 * %arg1) + %arg2 + %arg) umin %arg) + %arg1) U: full-set S: full-set
+; CHECK-NEXT:    %i8 = sub i32 %arg3, %i7
+; CHECK-NEXT:    --> ((-1 * (((-1 * %arg1) + %arg2 + %arg) umin %arg)) + (-1 * %arg1) + %arg3 + %arg) U: full-set S: full-set
+; CHECK-NEXT:    %i9 = getelementptr inbounds i8, i8* %arg, i32 %i8
+; CHECK-NEXT:    --> ((2 * %arg) + (-1 * (((-1 * %arg1) + %arg2 + %arg) umin %arg)) + (-1 * %arg1) + %arg3) U: full-set S: full-set
+; CHECK-NEXT:  Determining loop execution counts for: @FSE_decompress_usingDTable
+;
+bb:
+  %i = getelementptr inbounds i8, i8* %arg, i32 %arg2
+  %i4 = sub nsw i32 0, %arg1
+  %i5 = getelementptr inbounds i8, i8* %i, i32 %i4
+  %i6 = icmp ult i8* %i5, %arg
+  %i7 = select i1 %i6, i32 %arg2, i32 %arg1
+  %i8 = sub i32 %arg3, %i7
+  %i9 = getelementptr inbounds i8, i8* %arg, i32 %i8
+  ret i8* %i9
+}
+
+attributes #0 = { nofree }