[ScalarEvolution] Strictly enforce pointer/int type rules.

[efriedma]

Summary

Rules:

1. SCEVUnknown is a pointer if and only if the LLVM IR value is a pointer.
2. SCEVPtrToInt is never a pointer.
3. If any other SCEV expression has no pointer operands, the result is an integer.
4. If a SCEVAddExpr has exactly one pointer operand, the result is a pointer.
5. If a SCEVAddRecExpr's first operand is a pointer, and it has no other pointer operands, the result is a pointer.
6. If a SCEVMinMaxExpr has all pointer operands, the result is a pointer.
7. Otherwise, the SCEV expression is invalid.

I'm not sure how useful rule 6 is in practice. If we exclude it, we can guarantee that ScalarEvolution::getPointerBase always returns a SCEVUnknown, which might be a helpful property. Anyway, I'll leave that for a followup.

This is basically mop-up at this point; all the changes with significant functional effects have landed. Some of the remaining changes could be split off, but I don't see much point.

[efriedma]

Fix an assertion failure I found through extra testing.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

10600

It looks like it filters out such simple case as (LHS == RHS ) => (RHS== LHS) (if LHS = FoundRHS and RHS = FoundLHS). Could you please add a unit test to ensure it's not broken with this patch?

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

10600

This is inside the if (getTypeSizeInBits(LHS->getType()) < getTypeSizeInBits(FoundLHS->getType())). Since you can't extend/trunc a pointer, this means FoundLHS is not a pointer. I can't see how isImpliedCond could return any useful information in that case.

[mkazantsev]

Looks fine!

llvm/lib/Analysis/ScalarEvolution.cpp

10600

Err, you are right.

[kripken]

This caused assertions to be hit on some tests as well as real-world code that we run. Here is a testcase:

https://gist.github.com/kripken/a557a324095a96f3bc87f19bd3ed648f

That is the preprocessed output of test_atomic_cxx in emscripten. To see the crash, the build must have assertions enabled, and then run

clang++ a.cpp -target wasm32-unknown-unknown -c -O1

The crash is

clang++: llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:1888: const llvm::SCEV* llvm::ScalarEvolution::getSignExtendExpr(const llvm::SCEV*, llvm::Type*, unsigned int): Assertion `!Op->getType()->isPointerTy() && "Can't extend pointer!"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: build/bin/clang++ build/a.cpp -target wasm32-unknown-unknown -c -O1
1.      <eof> parser at end of file
2.      Optimizer
 #0 0x0000557c55c39ff0 PrintStackTraceSignalHandler(void*) Signals.cpp:0:0
 #1 0x0000557c55c37e54 llvm::sys::CleanupOnSignal(unsigned long) (build/bin/clang+++0x2184e54)
 #2 0x0000557c55b929a8 CrashRecoverySignalHandler(int) CrashRecoveryContext.cpp:0:0
 #3 0x00007f82f0f40140 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x14140)
 #4 0x00007f82f0a23ce1 raise ./signal/../sysdeps/unix/sysv/linux/raise.c:51:1
 #5 0x00007f82f0a0d537 abort ./stdlib/abort.c:81:7
 #6 0x00007f82f0a0d40f get_sysdep_segment_value ./intl/loadmsgcat.c:509:8
 #7 0x00007f82f0a0d40f _nl_load_domain ./intl/loadmsgcat.c:970:34
 #8 0x00007f82f0a1c662 (/lib/x86_64-linux-gnu/libc.so.6+0x34662)
 #9 0x0000557c54d53d6f llvm::ScalarEvolution::getSignExtendExpr(llvm::SCEV const*, llvm::Type*, unsigned int) (build/bin/clang+++0x12a0d6f)
#10 0x0000557c55dbc194 WidenIV::getWideRecurrence(WidenIV::NarrowIVDefUse) (build/bin/clang+++0x2309194)
#11 0x0000557c55dc6ffc WidenIV::widenIVUse(WidenIV::NarrowIVDefUse, llvm::SCEVExpander&) (build/bin/clang+++0x2313ffc)
#12 0x0000557c55dc79d7 WidenIV::createWideIV(llvm::SCEVExpander&) (build/bin/clang+++0x23149d7)
#13 0x0000557c55dc8143 llvm::createWideIV(llvm::WideIVInfo const&, llvm::LoopInfo*, llvm::ScalarEvolution*, llvm::SCEVExpander&, llvm::DominatorTree*, llvm::SmallVectorImpl<llvm::WeakTrackingVH>&, unsigned int&, unsigned int&, bool, bool) (build/bin/clang+++0x2315143)
#14 0x0000557c559b5180 (anonymous namespace)::IndVarSimplify::run(llvm::Loop*) IndVarSimplify.cpp:0:0
#15 0x0000557c559b6eab llvm::IndVarSimplifyPass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (build/bin/clang+++0x1f03eab)
#16 0x0000557c56d51ebe llvm::detail::PassModel<llvm::Loop, llvm::IndVarSimplifyPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (build/bin/clang+++0x329eebe)
#17 0x0000557c570687ca llvm::Optional<llvm::PreservedAnalyses> llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runSinglePass<llvm::Loop, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > > >(llvm::Loop&, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > >&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&, llvm::PassInstrumentation&) (.isra.0) LoopPassManager.cpp:0:0
#18 0x0000557c57069d50 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runWithoutLoopNestPasses(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (build/bin/clang+++0x35b6d50)
#19 0x0000557c57069ef9 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (build/bin/clang+++0x35b6ef9)
#20 0x0000557c5706bcf3 llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (build/bin/clang+++0x35b8cf3)
#21 0x0000557c56d51b0e llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (build/bin/clang+++0x329eb0e)

This change also causes a crash on building SQLite (but that is much larger - I can provide it as well, however, if that would be useful).

[efriedma]

In D105510#2870088, @kripken wrote:

This caused assertions to be hit on some tests as well as real-world code that we run.

Do all the failures you're seeing involve WidenIV::getWideRecurrence()? (If there are different callers of getSignExtendExpr triggering the same crash, I'll need to look at them separately.)

[kripken]

In D105510#2870147, @efriedma wrote:

In D105510#2870088, @kripken wrote:

This caused assertions to be hit on some tests as well as real-world code that we run.

Do all the failures you're seeing involve WidenIV::getWideRecurrence()?

Yes, it looks like they all go through there.

Here are the full logs for -Os and -O3:

https://logs.chromium.org/logs/emscripten-releases/buildbucket/cr-buildbucket.appspot.com/8841972864714597632/+/steps/Emscripten_testsuite__upstream__wasms_/0/stdout

https://logs.chromium.org/logs/emscripten-releases/buildbucket/cr-buildbucket.appspot.com/8841972864714597632/+/steps/Emscripten_testsuite__upstream__wasm3_/0/stdout

All 8 crashes mention WidenIV::getWideRecurrence.

[efriedma]

Crash should be fixed by rG6144085c29b3

[kripken]

In D105510#2870173, @efriedma wrote:

Crash should be fixed by rG6144085c29b3

Thanks for the quick fix!

That looks right to me, but I'm not an LLVM expert.

[uabelho]

Hi,
I see one of the new asserts blow when SCEV is used from LoopReroll:

clang-13: ../lib/Analysis/ScalarEvolution.cpp:2983: const llvm::SCEV *llvm::ScalarEvolution::getMulExpr(SmallVectorImpl<const llvm::SCEV *> &, SCEV::NoWrapFlags, unsigned int): Assertion `!ETy->isPointerTy()' failed.
[...]
1.      <eof> parser at end of file
2.      Per-module optimization passes
3.      Running pass 'CallGraph Pass Manager' on module 'thvs3.c'.
4.      Running pass 'Loop Pass Manager' on function '@test'
5.      Running pass 'Reroll loops' on basic block '%for.body42.3.1'
 #0 0x0000000002d679e8 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/repo/uabelho/llvm-project/llvm/build-all/bin/clang-13+0x2d679e8)
 #1 0x0000000002d6569e llvm::sys::RunSignalHandlers() (/repo/uabelho/llvm-project/llvm/build-all/bin/clang-13+0x2d6569e)
 #2 0x0000000002d68086 SignalHandler(int) Signals.cpp:0:0
 #3 0x00007fdf151ab630 __restore_rt sigaction.c:0:0
 #4 0x00007fdf128de387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007fdf128dfa78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007fdf128d71a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007fdf128d7252 (/lib64/libc.so.6+0x2f252)
 #8 0x0000000001efa418 llvm::ScalarEvolution::getMulExpr(llvm::SmallVectorImpl<llvm::SCEV const*>&, llvm::SCEV::NoWrapFlags, unsigned int) (/repo/uabelho/llvm-project/llvm/build-all/bin/clang-13+0x1efa418)
 #9 0x0000000002b4f73f (anonymous namespace)::LoopReroll::DAGRootTracker::validateRootSet((anonymous namespace)::LoopReroll::DAGRootSet&) LoopRerollPass.cpp:0:0
#10 0x0000000002b4f288 (anonymous namespace)::LoopReroll::DAGRootTracker::findRootsBase(llvm::Instruction*, llvm::SmallPtrSet<llvm::Instruction*, 16u>) LoopRerollPass.cpp:0:0
#11 0x0000000002b4e51e (anonymous namespace)::LoopReroll::DAGRootTracker::findRootsRecursive(llvm::Instruction*, llvm::SmallPtrSet<llvm::Instruction*, 16u>) LoopRerollPass.cpp:0:0
#12 0x0000000002b4e694 (anonymous namespace)::LoopReroll::DAGRootTracker::findRootsRecursive(llvm::Instruction*, llvm::SmallPtrSet<llvm::Instruction*, 16u>) LoopRerollPass.cpp:0:0
#13 0x0000000002b4e694 (anonymous namespace)::LoopReroll::DAGRootTracker::findRootsRecursive(llvm::Instruction*, llvm::SmallPtrSet<llvm::Instruction*, 16u>) LoopRerollPass.cpp:0:0
#14 0x0000000002b46b71 (anonymous namespace)::LoopReroll::runOnLoop(llvm::Loop*) LoopRerollPass.cpp:0:0
#15 0x0000000002b491d2 (anonymous namespace)::LoopRerollLegacyPass::runOnLoop(llvm::Loop*, llvm::LPPassManager&) LoopRerollPass.cpp:0:0

[uabelho]

In D105510#2873305, @uabelho wrote:

Hi,
I see one of the new asserts blow when SCEV is used from LoopReroll:

clang-13: ../lib/Analysis/ScalarEvolution.cpp:2983: const llvm::SCEV *llvm::ScalarEvolution::getMulExpr(SmallVectorImpl<const llvm::SCEV *> &, SCEV::NoWrapFlags, unsigned int): Assertion `!ETy->isPointerTy()' failed.
[...]
1.      <eof> parser at end of file
2.      Per-module optimization passes
3.      Running pass 'CallGraph Pass Manager' on module 'thvs3.c'.
4.      Running pass 'Loop Pass Manager' on function '@test'
5.      Running pass 'Reroll loops' on basic block '%for.body42.3.1'
 #0 0x0000000002d679e8 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/repo/uabelho/llvm-project/llvm/build-all/bin/clang-13+0x2d679e8)
 #1 0x0000000002d6569e llvm::sys::RunSignalHandlers() (/repo/uabelho/llvm-project/llvm/build-all/bin/clang-13+0x2d6569e)
 #2 0x0000000002d68086 SignalHandler(int) Signals.cpp:0:0
 #3 0x00007fdf151ab630 __restore_rt sigaction.c:0:0
 #4 0x00007fdf128de387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007fdf128dfa78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007fdf128d71a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007fdf128d7252 (/lib64/libc.so.6+0x2f252)
 #8 0x0000000001efa418 llvm::ScalarEvolution::getMulExpr(llvm::SmallVectorImpl<llvm::SCEV const*>&, llvm::SCEV::NoWrapFlags, unsigned int) (/repo/uabelho/llvm-project/llvm/build-all/bin/clang-13+0x1efa418)
 #9 0x0000000002b4f73f (anonymous namespace)::LoopReroll::DAGRootTracker::validateRootSet((anonymous namespace)::LoopReroll::DAGRootSet&) LoopRerollPass.cpp:0:0
#10 0x0000000002b4f288 (anonymous namespace)::LoopReroll::DAGRootTracker::findRootsBase(llvm::Instruction*, llvm::SmallPtrSet<llvm::Instruction*, 16u>) LoopRerollPass.cpp:0:0
#11 0x0000000002b4e51e (anonymous namespace)::LoopReroll::DAGRootTracker::findRootsRecursive(llvm::Instruction*, llvm::SmallPtrSet<llvm::Instruction*, 16u>) LoopRerollPass.cpp:0:0
#12 0x0000000002b4e694 (anonymous namespace)::LoopReroll::DAGRootTracker::findRootsRecursive(llvm::Instruction*, llvm::SmallPtrSet<llvm::Instruction*, 16u>) LoopRerollPass.cpp:0:0
#13 0x0000000002b4e694 (anonymous namespace)::LoopReroll::DAGRootTracker::findRootsRecursive(llvm::Instruction*, llvm::SmallPtrSet<llvm::Instruction*, 16u>) LoopRerollPass.cpp:0:0
#14 0x0000000002b46b71 (anonymous namespace)::LoopReroll::runOnLoop(llvm::Loop*) LoopRerollPass.cpp:0:0
#15 0x0000000002b491d2 (anonymous namespace)::LoopRerollLegacyPass::runOnLoop(llvm::Loop*, llvm::LPPassManager&) LoopRerollPass.cpp:0:0

Reduced opt reproducer:

opt -loop-reroll loop-reroll.ll -S -o /dev/null

loop-reroll.ll885 BDownload

[efriedma]

LoopReroll should be fixed by 5d1ba534

[uabelho]

In D105510#2875089, @efriedma wrote:

LoopReroll should be fixed by 5d1ba534

Yep, thanks!

llvm/lib/Analysis/ScalarEvolution.cpp

 }
 
 const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, Type *Ty,
                                              unsigned Depth) {
   assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
          "This is not a truncating conversion!");
   assert(isSCEVable(Ty) &&
          "This is not a conversion to a SCEVable type!");
+  assert(!Op->getType()->isPointerTy() && "Can't truncate pointer!");
   Ty = getEffectiveSCEVType(Ty);
 
   FoldingSetNodeID ID;
   ID.AddInteger(scTruncate);
   ID.AddPointer(Op);
   ID.AddPointer(Ty);
   void *IP = nullptr;
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;

 }
 
 const SCEV *
 ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
          "This is not an extending conversion!");
   assert(isSCEVable(Ty) &&
          "This is not a conversion to a SCEVable type!");
+  assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
   Ty = getEffectiveSCEVType(Ty);
 
   // Fold if the operand is constant.
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
     return getConstant(
       cast<ConstantInt>(ConstantExpr::getZExt(SC->getValue(), Ty)));
 
   // zext(zext(x)) --> zext(x)

 }
 
 const SCEV *
 ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
          "This is not an extending conversion!");
   assert(isSCEVable(Ty) &&
          "This is not a conversion to a SCEVable type!");
+  assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
   Ty = getEffectiveSCEVType(Ty);
 
   // Fold if the operand is constant.
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
     return getConstant(
       cast<ConstantInt>(ConstantExpr::getSExt(SC->getValue(), Ty)));
 
   // sext(sext(x)) --> sext(x)
assert(!(OrigFlags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) &&
          "only nuw or nsw allowed");
   assert(!Ops.empty() && "Cannot get empty add!");
   if (Ops.size() == 1) return Ops[0];
 #ifndef NDEBUG
   Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
     assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
            "SCEVAddExpr operand types don't match!");
+  unsigned NumPtrs = count_if(
+      Ops, [](const SCEV *Op) { return Op->getType()->isPointerTy(); });
+  assert(NumPtrs <= 1 && "add has at most one pointer operand");
 #endif
 
   // Sort by complexity, this groups all similar expression types together.
   GroupByComplexity(Ops, &LI, DT);
 
   // If there are any constants, fold them together.
   unsigned Idx = 0;
   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
if (CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
       // to avoid multiplying by the same constant scale multiple times.
       std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
       for (const SCEV *NewOp : NewOps)
         MulOpLists[M.find(NewOp)->second].push_back(NewOp);
       // Re-generate the operands list.
       Ops.clear();
       if (AccumulatedConstant != 0)
         Ops.push_back(getConstant(AccumulatedConstant));
-      for (auto &MulOp : MulOpLists)
-        if (MulOp.first != 0)
+      for (auto &MulOp : MulOpLists) {
+        if (MulOp.first == 1) {
+          Ops.push_back(getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1));
+        } else if (MulOp.first != 0) {
           Ops.push_back(getMulExpr(
               getConstant(MulOp.first),
               getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1),
               SCEV::FlagAnyWrap, Depth + 1));
+        }
+      }
       if (Ops.empty())
         return getZero(Ty);
       if (Ops.size() == 1)
         return Ops[0];
       return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
     }
   }
 

 const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
                                         SCEV::NoWrapFlags OrigFlags,
                                         unsigned Depth) {
   assert(OrigFlags == maskFlags(OrigFlags, SCEV::FlagNUW | SCEV::FlagNSW) &&
          "only nuw or nsw allowed");
   assert(!Ops.empty() && "Cannot get empty mul!");
   if (Ops.size() == 1) return Ops[0];
 #ifndef NDEBUG
-  Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
+  Type *ETy = Ops[0]->getType();
+  assert(!ETy->isPointerTy());
   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
-    assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
+    assert(Ops[i]->getType() == ETy &&
            "SCEVMulExpr operand types don't match!");
 #endif
 
   // Sort by complexity, this groups all similar expression types together.
   GroupByComplexity(Ops, &LI, DT);
 
   // If there are any constants, fold them together.
   unsigned Idx = 0;
const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS,
   const SCEV *Mult = getMulExpr(UDiv, RHS, SCEV::FlagNUW);
   return getMinusSCEV(LHS, Mult, SCEV::FlagNUW);
 }
 
 /// Get a canonical unsigned division expression, or something simpler if
 /// possible.
 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
                                          const SCEV *RHS) {
-  assert(getEffectiveSCEVType(LHS->getType()) ==
-         getEffectiveSCEVType(RHS->getType()) &&
+  assert(!LHS->getType()->isPointerTy() &&
+         "SCEVUDivExpr operand can't be pointer!");
+  assert(LHS->getType() == RHS->getType() &&
          "SCEVUDivExpr operand types don't match!");
 
   FoldingSetNodeID ID;
   ID.AddInteger(scUDivExpr);
   ID.AddPointer(LHS);
   ID.AddPointer(RHS);
   void *IP = nullptr;
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))

 /// Get an add recurrence expression for the specified loop.  Simplify the
 /// expression as much as possible.
 const SCEV *
 ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
                                const Loop *L, SCEV::NoWrapFlags Flags) {
   if (Operands.size() == 1) return Operands[0];
 #ifndef NDEBUG
   Type *ETy = getEffectiveSCEVType(Operands[0]->getType());
-  for (unsigned i = 1, e = Operands.size(); i != e; ++i)
+  for (unsigned i = 1, e = Operands.size(); i != e; ++i) {
     assert(getEffectiveSCEVType(Operands[i]->getType()) == ETy &&
            "SCEVAddRecExpr operand types don't match!");
+    assert(!Operands[i]->getType()->isPointerTy() && "Step must be integer");
+  }
   for (unsigned i = 0, e = Operands.size(); i != e; ++i)
     assert(isLoopInvariant(Operands[i], L) &&
            "SCEVAddRecExpr operand is not loop-invariant!");
 #endif
 
   if (Operands.back()->isZero()) {
     Operands.pop_back();
     return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0}  -->  X

 }
 
 const SCEV *ScalarEvolution::getMinMaxExpr(SCEVTypes Kind,
                                            SmallVectorImpl<const SCEV *> &Ops) {
   assert(!Ops.empty() && "Cannot get empty (u|s)(min|max)!");
   if (Ops.size() == 1) return Ops[0];
 #ifndef NDEBUG
   Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
-  for (unsigned i = 1, e = Ops.size(); i != e; ++i)
+  for (unsigned i = 1, e = Ops.size(); i != e; ++i) {
     assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
            "Operand types don't match!");
+    assert(Ops[0]->getType()->isPointerTy() ==
+               Ops[i]->getType()->isPointerTy() &&
+           "min/max should be consistently pointerish");
+  }
 #endif
 
   bool IsSigned = Kind == scSMaxExpr || Kind == scSMinExpr;
   bool IsMax = Kind == scSMaxExpr || Kind == scUMaxExpr;
 
   // Sort by complexity, this groups all similar expression types together.
   GroupByComplexity(Ops, &LI, DT);
 
if (!CmpInst::isSigned(FoundPred)) {
         const SCEV *TruncFoundLHS = getTruncateExpr(FoundLHS, NarrowType);
         const SCEV *TruncFoundRHS = getTruncateExpr(FoundRHS, NarrowType);
         if (isImpliedCondBalancedTypes(Pred, LHS, RHS, FoundPred, TruncFoundLHS,
                                        TruncFoundRHS, Context))
           return true;
       }
     }
 
+    if (LHS->getType()->isPointerTy())
+      return false;
     if (CmpInst::isSigned(Pred)) {
       LHS = getSignExtendExpr(LHS, FoundLHS->getType());
       RHS = getSignExtendExpr(RHS, FoundLHS->getType());
     } else {
       LHS = getZeroExtendExpr(LHS, FoundLHS->getType());
       RHS = getZeroExtendExpr(RHS, FoundLHS->getType());
     }
   } else if (getTypeSizeInBits(LHS->getType()) >
       getTypeSizeInBits(FoundLHS->getType())) {
+    if (FoundLHS->getType()->isPointerTy())
+      return false;
     if (CmpInst::isSigned(FoundPred)) {
       FoundLHS = getSignExtendExpr(FoundLHS, LHS->getType());
       FoundRHS = getSignExtendExpr(FoundRHS, LHS->getType());
     } else {
       FoundLHS = getZeroExtendExpr(FoundLHS, LHS->getType());
       FoundRHS = getZeroExtendExpr(FoundRHS, LHS->getType());
     }
   }

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

if (LHS == RHS)
     return SE.getConstant(LHS->getType(), 1);
 
   // Handle a few RHS special cases.
   const SCEVConstant *RC = dyn_cast<SCEVConstant>(RHS);
   if (RC) {
     const APInt &RA = RC->getAPInt();
     // Handle x /s -1 as x * -1, to give ScalarEvolution a chance to do
     // some folding.
-    if (RA.isAllOnesValue())
+    if (RA.isAllOnesValue()) {
+      if (LHS->getType()->isPointerTy())
+        return nullptr;
       return SE.getMulExpr(LHS, RC);
+    }
     // Handle x /s 1 as x.
     if (RA == 1)
       return LHS;
   }
 
   // Check for a division of a constant by a constant.
   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(LHS)) {
     if (!RC)

 /// Generate reuse formulae from different IV types.
 void LSRInstance::GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base) {
   // Don't bother truncating symbolic values.
   if (Base.BaseGV) return;
 
   // Determine the integer type for the base formula.
   Type *DstTy = Base.getType();
   if (!DstTy) return;
-  DstTy = SE.getEffectiveSCEVType(DstTy);
+  if (DstTy->isPointerTy())
+    return;
 
   for (Type *SrcTy : Types) {
     if (SrcTy != DstTy && TTI.isTruncateFree(SrcTy, DstTy)) {
       Formula F = Base;
 
       // Sometimes SCEV is able to prove zero during ext transform. It may
       // happen if SCEV did not do all possible transforms while creating the
       // initial node (maybe due to depth limitations), but it can do them while
if (LU.Kind == LSRUse::ICmpZero) {
       Ops.push_back(ScaledS);
     }
   }
 
   // Expand the GV portion.
   if (F.BaseGV) {
     // Flush the operand list to suppress SCEVExpander hoisting.
     if (!Ops.empty()) {
-      Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty);
+      Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), IntTy);
       Ops.clear();
       Ops.push_back(SE.getUnknown(FullV));
     }
     Ops.push_back(SE.getUnknown(F.BaseGV));
   }
 
   // Flush the operand list to suppress SCEVExpander hoisting of both folded and
   // unfolded offsets. LSR assumes they both live next to their uses.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

 }
 
 /// Check whether we can cheaply express the requested SCEV in terms of
 /// the available PHI SCEV by truncation and/or inversion of the step.
 static bool canBeCheaplyTransformed(ScalarEvolution &SE,
                                     const SCEVAddRecExpr *Phi,
                                     const SCEVAddRecExpr *Requested,
                                     bool &InvertStep) {
+  // We can't transform to match a pointer PHI.
+  if (Phi->getType()->isPointerTy())
+    return false;
+
   Type *PhiTy = SE.getEffectiveSCEVType(Phi->getType());
   Type *RequestedTy = SE.getEffectiveSCEVType(Requested->getType());
 
   if (RequestedTy->getIntegerBitWidth() > PhiTy->getIntegerBitWidth())
     return false;
 
   // Try truncate it if necessary.
   Phi = dyn_cast<SCEVAddRecExpr>(SE.getTruncateOrNoop(Phi, RequestedTy));
   if (!Phi)
     return false;
 
   // Check whether truncation will help.
   if (Phi == Requested) {
     InvertStep = false;
     return true;
   }
 
   // Check whether inverting will help: {R,+,-1} == R - {0,+,1}.
-  if (SE.getAddExpr(Requested->getStart(),
-                    SE.getNegativeSCEV(Requested)) == Phi) {
+  if (SE.getMinusSCEV(Requested->getStart(), Requested) == Phi) {
     InvertStep = true;
     return true;
   }
 
   return false;
 }
 
 static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
   PHINode *CanonicalIV = nullptr;
   if (PHINode *PN = L->getCanonicalInductionVariable())
     if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty))
       CanonicalIV = PN;
 
   // Rewrite an AddRec in terms of the canonical induction variable, if
   // its type is more narrow.
   if (CanonicalIV &&
-      SE.getTypeSizeInBits(CanonicalIV->getType()) >
-      SE.getTypeSizeInBits(Ty)) {
+      SE.getTypeSizeInBits(CanonicalIV->getType()) > SE.getTypeSizeInBits(Ty) &&
+      !S->getType()->isPointerTy()) {
     SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());
     for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
       NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
     Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
                                        S->getNoWrapFlags(SCEV::FlagNW)));
     BasicBlock::iterator NewInsertPt =
         findInsertPointAfter(cast<Instruction>(V), &*Builder.GetInsertPoint());
     V = expandCodeForImpl(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

TEST_F(ScalarEvolutionsTest, SCEVUnknownRAUW) {
   Value *V2 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V2");
 
   ScalarEvolution SE = buildSE(*F);
 
   const SCEV *S0 = SE.getSCEV(V0);
   const SCEV *S1 = SE.getSCEV(V1);
   const SCEV *S2 = SE.getSCEV(V2);
 
-  const SCEV *P0 = SE.getAddExpr(S0, S0);
-  const SCEV *P1 = SE.getAddExpr(S1, S1);
-  const SCEV *P2 = SE.getAddExpr(S2, S2);
-
-  const SCEVMulExpr *M0 = cast<SCEVMulExpr>(P0);
-  const SCEVMulExpr *M1 = cast<SCEVMulExpr>(P1);
-  const SCEVMulExpr *M2 = cast<SCEVMulExpr>(P2);
+  const SCEV *P0 = SE.getAddExpr(S0, SE.getConstant(S0->getType(), 2));
+  const SCEV *P1 = SE.getAddExpr(S1, SE.getConstant(S0->getType(), 2));
+  const SCEV *P2 = SE.getAddExpr(S2, SE.getConstant(S0->getType(), 2));
+
+  auto *M0 = cast<SCEVAddExpr>(P0);
+  auto *M1 = cast<SCEVAddExpr>(P1);
+  auto *M2 = cast<SCEVAddExpr>(P2);
 
   EXPECT_EQ(cast<SCEVConstant>(M0->getOperand(0))->getValue()->getZExtValue(),
             2u);
   EXPECT_EQ(cast<SCEVConstant>(M1->getOperand(0))->getValue()->getZExtValue(),
             2u);
   EXPECT_EQ(cast<SCEVConstant>(M2->getOperand(0))->getValue()->getZExtValue(),
             2u);
 
for (int i = 0; i < Iters; i++) {
     Accum = GetElementPtrInst::Create(I8Ty, Accum, PN, "gep", EndBB);
 
     PrevBB = CondBB;
     CondBB = NextBB;
   }
   ReturnInst::Create(Context, nullptr, EndBB);
   ScalarEvolution SE = buildSE(*F);
   const SCEV *S = SE.getSCEV(Accum);
+  S = SE.getLosslessPtrToIntExpr(S);
   Type *I128Ty = Type::getInt128Ty(Context);
   SE.getZeroExtendExpr(S, I128Ty);
 }
 
 // Make sure that SCEV invalidates exit limits after invalidating the values it
 // depends on when we forget a loop.
 TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetLoop) {
   /*