[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

496

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

500

auto *.

1308

s/is the/if the/

1382

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

[loladiro]

lib/Analysis/ScalarEvolutionExpander.cpp

496

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.

1382

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

496

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

496

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.

1382

SGTM

[loladiro]

lib/Analysis/ScalarEvolutionExpander.cpp

496

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

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

1392

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

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

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

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 ↗

(On Diff #100519)

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.

lib/Analysis/ScalarEvolutionExpander.cpp

Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin,
   // better than ptrtoint+arithmetic+inttoptr at least.
   if (!AnyNonZeroIndices) {
     // Cast the base to i8*.
     V = InsertNoopCastOfTo(V,
        Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace()));
 
     assert(!isa<Instruction>(V) ||
            SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint()));
 
     // Expand the operands for a plain byte offset.
     Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty);
 
     // Fold a GEP with constant operands.
     if (Constant *CLHS = dyn_cast<Constant>(V))
       if (Constant *CRHS = dyn_cast<Constant>(Idx))
         return ConstantExpr::getGetElementPtr(Type::getInt8Ty(Ty->getContext()),
                                               CLHS, CRHS);
 
     // Do a quick scan to see if we have this GEP nearby.  If so, reuse it.
     unsigned ScanLimit = 6;
     BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
if (!SE.dominates(Step, L->getHeader())) {
     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 (InvertStep) {
                                  Result);
       rememberInstruction(Result);
     }
   }
 
   // Re-apply any non-loop-dominating scale.
   if (PostLoopScale) {
     assert(S->isAffine() && "Can't linearly scale non-affine recurrences.");
     Result = InsertNoopCastOfTo(Result, IntTy);
     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);
     }
   }
 

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 i8, i8 addrspace(10)* {{.*}}, i64 {{.*}}
+top:
+  br label %L86
+
+L86:                                              ; preds = %L86, %top
+  %i.0 = phi i64 [ 0, %top ], [ %0, %L86 ]
+  %0 = add i64 %i.0, 1
+  br i1 undef, label %L86, label %if29
+
+if29:                                             ; preds = %L86
+  %1 = shl i64 %0, 1
+  %2 = add i64 %1, -2
+  br label %if31
+
+if31:                                             ; preds = %if38, %if29
+  %"#temp#1.sroa.0.022" = phi i64 [ 0, %if29 ], [ %3, %if38 ]
+  br label %L119
+
+L119:                                             ; preds = %L119, %if31
+  %i5.0 = phi i64 [ %"#temp#1.sroa.0.022", %if31 ], [ %3, %L119 ]
+  %3 = add i64 %i5.0, 1
+  br i1 undef, label %L119, label %if38
+
+if38:                                             ; preds = %L119
+  %4 = add i64 %2, %i5.0
+  %5 = getelementptr i64, i64 addrspace(10)* %arg, i64 %4
+  %6 = load i64, i64 addrspace(10)* %5
+  br i1 undef, label %done, label %if31
+
+done:
+  ret void
+}