[SCEVExpander] Try harder to avoid introducing inttoptr

[loladiro]

Summary

This fixes introduction of an incorrect inttoptr/ptrtoint pair in
the included test case which makes use of non-integral pointers. I
suspect there are more cases like this left, but this takes care of
the one I was seeing at the moment.

[sanjoy]

lib/Analysis/ScalarEvolutionExpander.cpp

494 ↗

(On Diff #98758)

Just to be clear, this is intentionally kicking in for all pointers? If so, a test case showing that will be great.

498 ↗

(On Diff #98758)

auto *.

1322 ↗

(On Diff #98758)

s/is the/if the/

1396 ↗

(On Diff #98758)

This is annoying, but won't a non-null PostLoopScale with an ni pointer type fail here?

[loladiro]

lib/Analysis/ScalarEvolutionExpander.cpp

494 ↗

(On Diff #98758)

Yes, I think it's just generally better to attempt to do this rather than create the inttoptr/ptrtoint pairs. I'll add a test case.

1396 ↗

(On Diff #98758)

I think in the cases I saw, Result was of integer type at this point, so that would have been fine. It may be possible to get a pointer typed one, but it seems a bit weird to be multiplying something that would be pointer valued at this point (i.e. I can see multiplying an offset, but once you apply a base pointer, seem like you wouldn't be multiplying any more)?

[loladiro]

lib/Analysis/ScalarEvolutionExpander.cpp

494 ↗

(On Diff #98758)

Hmm, looks like all other callers make sure this doesn't happen in the caller, so it looks like the non-integral case is the only way to currently reach here. Doesn't mean of course that the other callers will handle the non-integral case properly. If you prefer, I can lift this check into the ptr and swap the operands there (it's a bit awkward, because one's a Value* and one's a SEC* and it may be the wrong way around), but either way is fine with me. Let me know which you think is cleaner.

[sanjoy]

lib/Analysis/ScalarEvolutionExpander.cpp

494 ↗

(On Diff #98758)

Hmm, looks like all other callers make sure this doesn't happen in the caller

Can you be more specific? "Other callers" exclusive to which one?

If ni pointers are the only case we see here, I'd suggest changing the AddExpr->getType()->isPointerTy() check to check that AddExpr->getType() is a ni pointer.

1396 ↗

(On Diff #98758)

SGTM

[loladiro]

lib/Analysis/ScalarEvolutionExpander.cpp

494 ↗

(On Diff #98758)

The one that adds PostLoopOffset in expandAddRecExprLiterally. The change I introduced there forces the offset expansion type to be an integer when before it would have probably been pointer valued.

[loladiro]

Changed the patch to do the argument re-arranging in the caller instead. I think
that's more localized to just this non-integral pointer change.

[sanjoy]

Thank you for doing this!

lib/Analysis/ScalarEvolutionExpander.cpp

1307 ↗

(On Diff #99267)

Did you consider just making this Type *ExpandTy = PostLoopScale ? IntTy : Normalized->getType();?

1392 ↗

(On Diff #99267)

This is to prevent an ptrtoint on the expansion of PostLoopOffset, right? If so, I think phrasing this in terms of the type of PostLoopOffset may be more obvious.

test/Transforms/LoopStrengthReduce/nonintegral.ll

19 ↗

(On Diff #99267)

Run -metarenamer on -instnamer on this?

Also, a C++ unit test that directly uses SCEVExpander will be more robust. This test case can become a no-op if LSR heuristics change.

[loladiro]

lib/Analysis/ScalarEvolutionExpander.cpp

1307 ↗

(On Diff #99267)

Yes, I think I tried that first. You do still want to make it match the type of S eventually at the very end.

1392 ↗

(On Diff #99267)

Well, either way. Without this, it'll try to gep (inttoptr Result to i8*), i64 (ptrtoint PostLoopOffset)

[loladiro]

Add a C++ test to make sure the SCEV code path is tested

[sanjoy]

lgtm

[GorNishanov]

llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp

917

Looks like a typo:

lvm/unittests/Analysis/ScalarEvolutionTest.cpp:917:43: error: braces around scalar initializer [-Werror,-Wbraced-scalar-init]

Value *GepBase = Builder.CreateGEP(Arg, {ConstantInt::get(T_int64, 1)});

[GorNishanov]

Fixed:

commit bdea69f0470dbc8282263f26d2b3fafbc812a010
Author: gornishanov <gornishanov@91177308-0d34-0410-b5e6-96231b3b80d8>
Date: Sat May 27 05:24:30 2017 +0000

ScalarEvolution unit test: fix typo that breaks check-all

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@304063 91177308-0d34-0410-b5e6-96231b3b80d8

[loladiro]

Thanks! I'm a little confused why the compiler is complaining there - I see this pattern used all over the place for 1-element array construction, but your fix is of course fine.

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

Normalized =
       cast<SCEVAddRecExpr>(SE.getAddRecExpr(
                              Start, Step, Normalized->getLoop(),
                              Normalized->getNoWrapFlags(SCEV::FlagNW)));
   }
 
   // Expand the core addrec. If we need post-loop scaling, force it to
   // expand to an integer type to avoid the need for additional casting.
   Type *ExpandTy = PostLoopScale ? IntTy : STy;
+  // We can't use a pointer type for the addrec if the pointer type is
+  // non-integral.
+  Type *AddRecPHIExpandTy =
+      DL.isNonIntegralPointerType(STy) ? Normalized->getType() : ExpandTy;
+
   // In some cases, we decide to reuse an existing phi node but need to truncate
   // it and/or invert the step.
   Type *TruncTy = nullptr;
   bool InvertStep = false;
-  PHINode *PN = getAddRecExprPHILiterally(Normalized, L, ExpandTy, IntTy,
-                                          TruncTy, InvertStep);
+  PHINode *PN = getAddRecExprPHILiterally(Normalized, L, AddRecPHIExpandTy,
+                                          IntTy, TruncTy, InvertStep);
 
   // Accommodate post-inc mode, if necessary.
   Value *Result;
   if (!PostIncLoops.count(L))
     Result = PN;
   else {
     // In PostInc mode, use the post-incremented value.
     BasicBlock *LatchBlock = L->getLoopLatch();
if (PostLoopScale) {
     Result = Builder.CreateMul(Result,
                                expandCodeFor(PostLoopScale, IntTy));
     rememberInstruction(Result);
   }
 
   // Re-apply any non-loop-dominating offset.
   if (PostLoopOffset) {
     if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
-      const SCEV *const OffsetArray[1] = { PostLoopOffset };
-      Result = expandAddToGEP(OffsetArray, OffsetArray+1, PTy, IntTy, Result);
+      if (Result->getType()->isIntegerTy()) {
+        Value *Base = expandCodeFor(PostLoopOffset, ExpandTy);
+        const SCEV *const OffsetArray[1] = {SE.getUnknown(Result)};
+        Result = expandAddToGEP(OffsetArray, OffsetArray + 1, PTy, IntTy, Base);
+      } else {
+        const SCEV *const OffsetArray[1] = {PostLoopOffset};
+        Result =
+            expandAddToGEP(OffsetArray, OffsetArray + 1, PTy, IntTy, Result);
+      }
     } else {
       Result = InsertNoopCastOfTo(Result, IntTy);
       Result = Builder.CreateAdd(Result,
                                  expandCodeFor(PostLoopOffset, IntTy));
       rememberInstruction(Result);
     }
   }
 

llvm/trunk/test/Transforms/LoopStrengthReduce/nonintegral.ll

+; RUN: opt -S -loop-reduce < %s | FileCheck %s
+
+; Address Space 10 is non-integral. The optimizer is not allowed to use
+; ptrtoint/inttoptr instructions. Make sure that this doesn't happen
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:10:11:12"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @japi1__unsafe_getindex_65028(i64 addrspace(10)* %arg) {
+; CHECK-NOT: inttoptr
+; CHECK-NOT: ptrtoint
+; How exactly SCEV chooses to materialize isn't all that important, as
+; long as it doesn't try to round-trip through integers. As of this writing,
+; it emits a byte-wise gep, which is fine.
+; CHECK: getelementptr i64, i64 addrspace(10)* {{.*}}, i64 {{.*}}
+top:
+  br label %L86
+
+L86:                                              ; preds = %L86, %top
+  %i.0 = phi i64 [ 0, %top ], [ %tmp, %L86 ]
+  %tmp = add i64 %i.0, 1
+  br i1 undef, label %L86, label %if29
+
+if29:                                             ; preds = %L86
+  %tmp1 = shl i64 %tmp, 1
+  %tmp2 = add i64 %tmp1, -2
+  br label %if31
+
+if31:                                             ; preds = %if38, %if29
+  %"#temp#1.sroa.0.022" = phi i64 [ 0, %if29 ], [ %tmp3, %if38 ]
+  br label %L119
+
+L119:                                             ; preds = %L119, %if31
+  %i5.0 = phi i64 [ %"#temp#1.sroa.0.022", %if31 ], [ %tmp3, %L119 ]
+  %tmp3 = add i64 %i5.0, 1
+  br i1 undef, label %L119, label %if38
+
+if38:                                             ; preds = %L119
+  %tmp4 = add i64 %tmp2, %i5.0
+  %tmp5 = getelementptr i64, i64 addrspace(10)* %arg, i64 %tmp4
+  %tmp6 = load i64, i64 addrspace(10)* %tmp5
+  br i1 undef, label %done, label %if31
+
+done:                                             ; preds = %if38
+  ret void
+}

llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp

 //===- ScalarEvolutionsTest.cpp - ScalarEvolution unit tests --------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Analysis/ScalarEvolutionExpander.h"
-#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/LoopInfo.h"
-#include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/GlobalVariable.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/LLVMContext.h"
-#include "llvm/IR/Module.h"
 #include "llvm/IR/LegacyPassManager.h"
+#include "llvm/IR/Module.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
 namespace llvm {
 namespace {
 
 // We use this fixture to ensure that we clean up ScalarEvolution before
for (int i = 0; i < Iters; i++) {
     CondBB = NextBB;
   }
   ReturnInst::Create(Context, nullptr, EndBB);
   ScalarEvolution SE = buildSE(*F);
   const SCEV *S = SE.getSCEV(Accum);
   Type *I128Ty = Type::getInt128Ty(Context);
   SE.getZeroExtendExpr(S, I128Ty);
 }
+
+// Make sure that SCEV doesn't introduce illegal ptrtoint/inttoptr instructions
+TEST_F(ScalarEvolutionsTest, SCEVZeroExtendExprNonIntegral) {
+  /*
+   * Create the following code:
+   * func(i64 addrspace(10)* %arg)
+   * top:
+   *  br label %L.ph
+   * L.ph:
+   *  br label %L
+   * L:
+   *  %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]
+   *  %add = add i64 %phi2, 1
+   *  br i1 undef, label %post, label %L2
+   * post:
+   *  %gepbase = getelementptr i64 addrspace(10)* %arg, i64 1
+   *  #= %gep = getelementptr i64 addrspace(10)* %gepbase, i64 %add =#
+   *  ret void
+   *
+   * We will create the appropriate SCEV expression for %gep and expand it,
+   * then check that no inttoptr/ptrtoint instructions got inserted.
+   */
+
+  // Create a module with non-integral pointers in it's datalayout
+  Module NIM("nonintegral", Context);
+  std::string DataLayout = M.getDataLayoutStr();
+  if (!DataLayout.empty())
+    DataLayout += "-";
+  DataLayout += "ni:10";
+  NIM.setDataLayout(DataLayout);
+
+  Type *T_int1 = Type::getInt1Ty(Context);
+  Type *T_int64 = Type::getInt64Ty(Context);
+  Type *T_pint64 = T_int64->getPointerTo(10);
+
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
+  Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy));
+
+  Argument *Arg = &*F->arg_begin();
+
+  BasicBlock *Top = BasicBlock::Create(Context, "top", F);
+  BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);
+  BasicBlock *L = BasicBlock::Create(Context, "L", F);
+  BasicBlock *Post = BasicBlock::Create(Context, "post", F);
+
+  IRBuilder<> Builder(Top);
+  Builder.CreateBr(LPh);
+
+  Builder.SetInsertPoint(LPh);
+  Builder.CreateBr(L);
+
+  Builder.SetInsertPoint(L);
+  PHINode *Phi = Builder.CreatePHI(T_int64, 2);
+  Value *Add = Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add");
+  Builder.CreateCondBr(UndefValue::get(T_int1), L, Post);
+  Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);
+  Phi->addIncoming(Add, L);
+
+  Builder.SetInsertPoint(Post);
+  Value *GepBase = Builder.CreateGEP(Arg, {ConstantInt::get(T_int64, 1)});
+  Instruction *Ret = Builder.CreateRetVoid();
+
+  ScalarEvolution SE = buildSE(*F);
+  auto *AddRec =
+      SE.getAddRecExpr(SE.getUnknown(GepBase), SE.getConstant(T_int64, 1),
+                       LI->getLoopFor(L), SCEV::FlagNUW);
+
+  SCEVExpander Exp(SE, NIM.getDataLayout(), "expander");
+  Exp.disableCanonicalMode();
+  Exp.expandCodeFor(AddRec, T_pint64, Ret);
+
+  // Make sure none of the instructions inserted were inttoptr/ptrtoint.
+  // The verifier will check this.
+  EXPECT_FALSE(verifyFunction(*F, &errs()));
+}
+
 }  // end anonymous namespace
 }  // end namespace llvm