[SCEVExpander] Support expanding nonintegral pointers with constant base.

[fhahn]

Summary

Currently SCEVExpander creates inttoptr for non-integral pointers if the
base is a null constant for example. This results in invalid IR.

This patch changes InsertNoopCastOfTo to emit a GEP to convert to a
non-integral pointer. The GEP uses null as base. The original value is
converted to an index by dividing by the alloc size of the type.

Note that this requires the original value to be divisible by the alloc
size, otherwise the pointer value will be changed. I am not sure if that
is an issue in practice (ideally the expander would only be used for
expanding pointer arithmetic that keeps the result divisible by the
alloc size) and there is not much we could do otherwise.

I guess we could instead try to create a pointer with alloc size of 1
byte, create a GEP with the original value as index and bitcast to the
target type. I am not sure if we can always do that, but I guess we
could add an assertion if that happens.

This was exposed by D71539.

[arsenm]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

134

It seems broken that getCastOpcode would return IntToPtr in a situation where it's illegal

[fhahn]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

134

Yes, that seems a rather big hole in getCastOpcode unfortunately and should probably also be changed.

But I think the key question is how to best deal with the problem during SCEV expansion here, because AFAIK we do not have a way to indicate that we failed to expand an expression in the expander.

Is it enough to emit a GEP with a computed index? Or should we better try to get a type with an alloc size of 1 byte and use that? I guess there could be configurations which do not have such a type, not sure what to do then.

[efriedma]

I have a proposal in https://bugs.llvm.org/show_bug.cgi?id=46786#c20 which would solve this, among other issues. Not sure when I'll get around to actually implementing it.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

134

In general, for non-null pointers, SCEVExpander uses a GEP over i8* (in the appropriate address space). We should do that even if the implicit null is missing. The offset isn't necessarily divisible by the element type: SCEV looks through bitcasts.

I guess there could be configurations which do not have such a type

i8 is always one byte. (This should be true even with an out-of-tree patchset that makes bytes bigger than 8 bits: it would just be a non-byte-sized type, similar to i1.)

[fhahn]

Change generated code to use bitcast (GEP i8* null, %v) to Ty. Also adds an assertion that i8 has an alloc size of 1 byte.

[fhahn]

In D87827#2280309, @efriedma wrote:

I have a proposal in https://bugs.llvm.org/show_bug.cgi?id=46786#c20 which would solve this, among other issues. Not sure when I'll get around to actually implementing it.

This looks very interesting, but like a non-trivial amount of work. The expander problem is currently blocking the re-landing of D71539 and it seems the fix in the expander is relatively small/straight-forward and it would be great to unblock that change :)

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

134

In general, for non-null pointers, SCEVExpander uses a GEP over i8* (in the appropriate address space). We should do that even if the implicit null is missing. The offset isn't necessarily divisible by the element type: SCEV looks through bitcasts.

I guess there could be configurations which do not have such a type

i8 is always one byte. (This should be true even with an out-of-tree patchset that makes bytes bigger than 8 bits: it would just be a non-byte-sized type, similar to i1.)

Oh, I thought there might be out-of-tree targets that have i8 with different alloc sizes, but if that is nothing to worry about we can just emit a GEP with i8* null as base pointer. I updated the code and added an extra assertion to make things blow up if the assumption is broken.

[efriedma]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

131

It's probably worth noting the reason we know this is safe. Semantically, a GEP from null is quite different from an inttoptr: a GEP from null can't be used to access memory. I guess the reason this is safe is that we know the original IR must also have been a GEP from null.

[fhahn]

expand comment stating why it should be safe to use GEP of null instead of inttoptr as Eli suggested, thanks!

[fhahn]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

131

Updated, thanks! I think in theory the user could also use expandCodeFor to expand a SCEV expression that does not originate from a pointer and force the result to be casted to a pointer (e.g. expandCodeFor(2, PtrTy)), but this seems like an invalid use of the API to me. (Which we unfortunately cannot easily catch/detect)

[efriedma]

LGTM

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) {
   Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false);
   assert((Op == Instruction::BitCast ||
           Op == Instruction::PtrToInt ||
           Op == Instruction::IntToPtr) &&
          "InsertNoopCastOfTo cannot perform non-noop casts!");
   assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) &&
          "InsertNoopCastOfTo cannot change sizes!");
 
+  auto *PtrTy = dyn_cast<PointerType>(Ty);
+  // inttoptr only works for integral pointers. For non-integral pointers, we
+  // can create a GEP on i8* null  with the integral value as index. Note that
+  // it is safe to use GEP of null instead of inttoptr here, because only
+  // expressions already based on a GEP of null should be converted to pointers
+  // during expansion.
+  if (Op == Instruction::IntToPtr && DL.isNonIntegralPointerType(PtrTy)) {
+    auto *Int8PtrTy = Builder.getInt8PtrTy(PtrTy->getAddressSpace());
+    assert(DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 &&
+           "alloc size of i8 must by 1 byte for the GEP to be correct");
+    auto *GEP = Builder.CreateGEP(
+        Builder.getInt8Ty(), Constant::getNullValue(Int8PtrTy), V, "uglygep");
+    return Builder.CreateBitCast(GEP, Ty);
+  }
   // Short-circuit unnecessary bitcasts.
   if (Op == Instruction::BitCast) {
     if (V->getType() == Ty)
       return V;
     if (CastInst *CI = dyn_cast<CastInst>(V)) {
       if (CI->getOperand(0)->getType() == Ty)
         return CI->getOperand(0);
     }

llvm/unittests/Transforms/Utils/ScalarEvolutionExpanderTest.cpp

 #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/PatternMatch.h"
 #include "llvm/IR/Verifier.h"
 #include "gtest/gtest.h"
 
 namespace llvm {
 
+using namespace PatternMatch;
+
 // We use this fixture to ensure that we clean up ScalarEvolution before
 // deleting the PassManager.
 class ScalarEvolutionExpanderTest : public testing::Test {
 protected:
   LLVMContext Context;
   Module M;
   TargetLibraryInfoImpl TLII;
   TargetLibraryInfo TLI;
SmallVector<const SCEV *, 5> Ops = {SE.getConstant(APInt(ARBitWidth, 5)),
                                         SE.getOne(ARType), SE.getOne(ARType)};
     return cast<SCEVAddRecExpr>(SE.getAddRecExpr(Ops, L, SCEV::FlagAnyWrap));
   };
   TestNoCanonicalIV(GetAR5);
   TestNarrowCanonicalIV(GetAR5);
   TestMatchingCanonicalIV(GetAR5, ARBitWidth);
 }
 
+TEST_F(ScalarEvolutionExpanderTest, ExpandNonIntegralPtrWithNullBase) {
+  LLVMContext C;
+  SMDiagnostic Err;
+
+  std::unique_ptr<Module> M =
+      parseAssemblyString("target datalayout = "
+                          "\"e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:"
+                          "128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2\""
+                          "define float addrspace(1)* @test(i64 %offset) { "
+                          "  %ptr = getelementptr inbounds float, float "
+                          "addrspace(1)* null, i64 %offset"
+                          "  ret float addrspace(1)* %ptr"
+                          "}",
+                          Err, C);
+
+  assert(M && "Could not parse module?");
+  assert(!verifyModule(*M) && "Must have been well formed!");
+
+  runWithSE(*M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+    auto &I = GetInstByName(F, "ptr");
+    auto PtrPlus1 =
+        SE.getAddExpr(SE.getSCEV(&I), SE.getConstant(I.getType(), 1));
+    SCEVExpander Exp(SE, M->getDataLayout(), "expander");
+
+    Value *V = Exp.expandCodeFor(PtrPlus1, I.getType(), &I);
+    I.replaceAllUsesWith(V);
+
+    // Check the expander created bitcast (gep i8* null, %offset).
+    auto *Cast = dyn_cast<BitCastInst>(V);
+    EXPECT_TRUE(Cast);
+    EXPECT_EQ(Cast->getType(), I.getType());
+    auto *GEP = dyn_cast<GetElementPtrInst>(Cast->getOperand(0));
+    EXPECT_TRUE(GEP);
+    EXPECT_TRUE(cast<Constant>(GEP->getPointerOperand())->isNullValue());
+    EXPECT_EQ(cast<PointerType>(GEP->getPointerOperand()->getType())
+                  ->getAddressSpace(),
+              cast<PointerType>(I.getType())->getAddressSpace());
+
+    // Check the expander created the expected index computation: add (shl
+    // %offset, 2), 1.
+    Value *Arg;
+    EXPECT_TRUE(
+        match(GEP->getOperand(1),
+              m_Add(m_Shl(m_Value(Arg), m_SpecificInt(2)), m_SpecificInt(1))));
+    EXPECT_EQ(Arg, &*F.arg_begin());
+    EXPECT_FALSE(verifyFunction(F, &errs()));
+  });
+}
+
 } // end namespace llvm