[SCEV] Introduce SCEVPtrToIntExpr (PR46786)

And use it to model LLVM IR's `ptrtoint` cast.

This is essentially an alternative to D88806, but with no chance for
all the problems it caused due to having the cast as implicit there.
(see rG7ee6c402474a2f5fd21c403e7529f97f6362fdb3)

As we've established by now, there are at least two reasons why we want this:
* It will allow SCEV to actually model the `ptrtoint` casts
  and their operands, instead of treating them as `SCEVUnknown`
* It should help with initial problem of PR46786 - this should eventually allow us
  to not loose pointer-ness of an expression in more cases

As discussed in [[ https://bugs.llvm.org/show_bug.cgi?id=46786 | PR46786 ]], in principle,
we could just extend `SCEVUnknown` with a `is ptrtoint` cast, because `ScalarEvolution::getPtrToIntExpr()`
should sink the cast as far down into the expression as possible,
so in the end we should always end up with `SCEVPtrToIntExpr` of `SCEVUnknown`.

But i think that it isn't the best solution, because it doesn't really matter
from memory consumption side - there probably won't be *that* many `SCEVPtrToIntExpr`s
for it to matter, and it allows for much better discoverability.

Reviewed By: mkazantsev

Differential Revision: https://reviews.llvm.org/D89456

7 files changed, 40 insertions, 22 deletions

diff --git a/polly/include/polly/Support/SCEVAffinator.h b/polly/include/polly/Support/SCEVAffinator.h
index 018630a0378f..f5d771188571 100644
--- a/polly/include/polly/Support/SCEVAffinator.h
+++ b/polly/include/polly/Support/SCEVAffinator.h
@@ -99,6 +99,7 @@ private:
 
   PWACtx visit(const llvm::SCEV *E);
   PWACtx visitConstant(const llvm::SCEVConstant *E);
+  PWACtx visitPtrToIntExpr(const llvm::SCEVPtrToIntExpr *E);
   PWACtx visitTruncateExpr(const llvm::SCEVTruncateExpr *E);
   PWACtx visitZeroExtendExpr(const llvm::SCEVZeroExtendExpr *E);
   PWACtx visitSignExtendExpr(const llvm::SCEVSignExtendExpr *E);
diff --git a/polly/lib/Support/SCEVAffinator.cpp b/polly/lib/Support/SCEVAffinator.cpp
index 2c7dc8fa415f..9d2e7d9a6fcb 100644
--- a/polly/lib/Support/SCEVAffinator.cpp
+++ b/polly/lib/Support/SCEVAffinator.cpp
@@ -266,6 +266,10 @@ PWACtx SCEVAffinator::visitConstant(const SCEVConstant *Expr) {
       isl::manage(isl_pw_aff_from_aff(isl_aff_val_on_domain(ls, v))));
 }
 
+PWACtx SCEVAffinator::visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr) {
+  return visit(Expr->getOperand(0));
+}
+
 PWACtx SCEVAffinator::visitTruncateExpr(const SCEVTruncateExpr *Expr) {
   // Truncate operations are basically modulo operations, thus we can
   // model them that way. However, for large types we assume the operand
@@ -538,8 +542,6 @@ PWACtx SCEVAffinator::visitUnknown(const SCEVUnknown *Expr) {
     switch (I->getOpcode()) {
     case Instruction::IntToPtr:
       return visit(SE.getSCEVAtScope(I->getOperand(0), getScope()));
-    case Instruction::PtrToInt:
-      return visit(SE.getSCEVAtScope(I->getOperand(0), getScope()));
     case Instruction::SDiv:
       return visitSDivInstruction(I);
     case Instruction::SRem:
diff --git a/polly/lib/Support/SCEVValidator.cpp b/polly/lib/Support/SCEVValidator.cpp
index 501d7645831c..94b55167a9b4 100644
--- a/polly/lib/Support/SCEVValidator.cpp
+++ b/polly/lib/Support/SCEVValidator.cpp
@@ -161,6 +161,10 @@ public:
     return ValidatorResult(SCEVType::PARAM, Expr);
   }
 
+  class ValidatorResult visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr) {
+    return visit(Expr->getOperand());
+  }
+
   class ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) {
     return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
   }
@@ -444,8 +448,6 @@ public:
       switch (I->getOpcode()) {
       case Instruction::IntToPtr:
         return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
-      case Instruction::PtrToInt:
-        return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
       case Instruction::Load:
         return visitLoadInstruction(I, Expr);
       case Instruction::SDiv:
diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp
index bf2d82e44660..a2010476b7be 100644
--- a/polly/lib/Support/ScopHelper.cpp
+++ b/polly/lib/Support/ScopHelper.cpp
@@ -341,6 +341,9 @@ private:
   ///
   ///{
   const SCEV *visitConstant(const SCEVConstant *E) { return E; }
+  const SCEV *visitPtrToIntExpr(const SCEVPtrToIntExpr *E) {
+    return SE.getPtrToIntExpr(visit(E->getOperand()), E->getType());
+  }
   const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) {
     return SE.getTruncateExpr(visit(E->getOperand()), E->getType());
   }
diff --git a/polly/test/Isl/CodeGen/ptrtoint_as_parameter.ll b/polly/test/Isl/CodeGen/ptrtoint_as_parameter.ll
index a673ac77f4fb..7e69560d0df8 100644
--- a/polly/test/Isl/CodeGen/ptrtoint_as_parameter.ll
+++ b/polly/test/Isl/CodeGen/ptrtoint_as_parameter.ll
@@ -1,7 +1,12 @@
 ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
 ;
-; CHECK:      polly.split_new_and_old:
-; CHECK-NEXT:   %pollysub.ptr.lhs.cast263 = ptrtoint i8* inttoptr (i64 1 to i8*) to i64
+; CHECK:      if.then260:
+; CHECK-NEXT:   %p.4 = getelementptr inbounds i8, i8* null, i64 1
+; CHECK-NEXT:   %sub.ptr.lhs.cast263 = ptrtoint i8* %p.4 to i64
+; CHECK-NEXT:   %sub.ptr.sub265 = sub i64 %sub.ptr.lhs.cast263, 0
+; CHECK-NEXT:   %div = udiv i64 0, %sub.ptr.sub265
+; CHECK-NEXT:   %cmp268 = icmp ult i64 0, %div
+; CHECK-NEXT:   br i1 %cmp268, label %cond.true270, label %while.cond.region_exiting
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
diff --git a/polly/test/ScopInfo/int2ptr_ptr2int.ll b/polly/test/ScopInfo/int2ptr_ptr2int.ll
index 350e6401d1f5..9618ea068e1b 100644
--- a/polly/test/ScopInfo/int2ptr_ptr2int.ll
+++ b/polly/test/ScopInfo/int2ptr_ptr2int.ll
@@ -17,21 +17,24 @@
 ; CHECK-NEXT:       [val, ptr] -> { Stmt_for_body[i0] -> MemRef_A[9 + ptr] };
 ;
 ; IR:      polly.stmt.for.body:
-; IR-NEXT:   %p_tmp = ptrtoint i64* %scevgep to i64
-; IR-NEXT:   %p_add = add nsw i64 %p_tmp, 1
-; IR-NEXT:   %p_tmp1 = inttoptr i64 %[[r1:[a-zA-Z0-9]*]] to i64*
+; IR-NEXT:   %p_tmp1 = inttoptr i64 %0 to i64*
 ; IR-NEXT:   %p_add.ptr2 = getelementptr inbounds i64, i64* %p_tmp1, i64 1
 ; IR-NEXT:   %p_tmp2 = ptrtoint i64* %p_add.ptr2 to i64
 ; IR-NEXT:   %p_arrayidx = getelementptr inbounds i64, i64* %A, i64 %p_tmp2
-; IR-NEXT:   %tmp3_p_scalar_ = load i64, i64* %p_arrayidx
-; IR-NEXT:   %p_arrayidx3 = getelementptr inbounds i64, i64* %A, i64 %p_add
-; IR-NEXT:   %tmp4_p_scalar_ = load i64, i64* %p_arrayidx3
+; IR-NEXT:   %tmp3_p_scalar_ = load i64, i64* %p_arrayidx, align 8, !alias.scope !0, !noalias !2
+; IR-NEXT:   %tmp4_p_scalar_ = load i64, i64* %scevgep1, align 8, !alias.scope !0, !noalias !2
 ; IR-NEXT:   %p_add4 = add nsw i64 %tmp4_p_scalar_, %tmp3_p_scalar_
-; IR-NEXT:   store i64 %p_add4, i64* %p_arrayidx3
+; IR-NEXT:   store i64 %p_add4, i64* %scevgep1, align 8, !alias.scope !0, !noalias !2
+; IR-NEXT:   %polly.indvar_next = add nsw i64 %polly.indvar, 1
+; IR-NEXT:   %polly.loop_cond = icmp sle i64 %polly.indvar_next, 99
+; IR-NEXT:   br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit
 ;
 ; IR:      polly.loop_preheader:
+; IR-NEXT:   %0 = add i64 %val, 1
 ; IR-NEXT:   %scevgep = getelementptr i64, i64* %ptr, i32 1
-; IR-NEXT:   %[[r1]] = add i64 %val, 1
+; IR-NEXT:   %1 = ptrtoint i64* %scevgep to i32
+; IR-NEXT:   %2 = add i32 %1, 1
+; IR-NEXT:   %scevgep1 = getelementptr i64, i64* %A, i32 %2
 ; IR-NEXT:   br label %polly.loop_header
 ;
 target datalayout = "e-p:32:32:32-m:e-i64:64-f80:128-n8:16:32:64-S128"
diff --git a/polly/test/ScopInfo/int2ptr_ptr2int_2.ll b/polly/test/ScopInfo/int2ptr_ptr2int_2.ll
index 951f4930b68c..894f5f308a07 100644
--- a/polly/test/ScopInfo/int2ptr_ptr2int_2.ll
+++ b/polly/test/ScopInfo/int2ptr_ptr2int_2.ll
@@ -21,19 +21,21 @@
 ; CHECK-NEXT:       [val, ptr] -> { Stmt_for_body[i0] -> MemRef_A[9 + ptr] };
 ;
 ; IR:      polly.stmt.for.body:
-; IR-NEXT:  %p_tmp = ptrtoint i64* %scevgep to i16
-; IR-NEXT:  %p_add = add nsw i16 %p_tmp, 1
-; IR-NEXT:  %p_arrayidx3 = getelementptr inbounds i64, i64* %A, i16 %p_add
-; IR-NEXT:  %tmp4_p_scalar_ = load i64, i64* %p_arrayidx3
-; IR-NEXT:  %p_add4 = add nsw i64 %tmp4_p_scalar_, %polly.preload.tmp3.merge
-; IR-NEXT:  store i64 %p_add4, i64* %p_arrayidx3
+; IR-NEXT:   %tmp4_p_scalar_ = load i64, i64* %scevgep13, align 8, !alias.scope !3, !noalias !4
+; IR-NEXT:   %p_add4 = add nsw i64 %tmp4_p_scalar_, %polly.preload.tmp3.merge
+; IR-NEXT:   store i64 %p_add4, i64* %scevgep13, align 8, !alias.scope !3, !noalias !4
+; IR-NEXT:   %polly.indvar_next = add nsw i64 %polly.indvar, 1
+; IR-NEXT:   %polly.loop_cond = icmp sle i64 %polly.indvar_next, 99
+; IR-NEXT:   br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit
 ;
 ; IR:      polly.loop_preheader:
-; IR-NEXT:   %scevgep = getelementptr i64, i64* %ptr, i16 1
 ; IR-NEXT:   %35 = add i16 %val, 1
+; IR-NEXT:   %scevgep = getelementptr i64, i64* %ptr, i16 1
+; IR-NEXT:   %36 = ptrtoint i64* %scevgep to i16
+; IR-NEXT:   %37 = add i16 %36, 1
+; IR-NEXT:   %scevgep13 = getelementptr i64, i64* %A, i16 %37
 ; IR-NEXT:   br label %polly.loop_header
 ;
-;
 target datalayout = "e-p:16:16:16-m:e-i64:64-f80:128-n8:16:16:64-S128"
 
 define void @f(i64* %A, i64* %B, i64* %ptr, i16 %val) {