Create a getelementptr instead of sub expr for ValueOffsetPair if the value is a pointer

[wmi]

Summary

This patch is to fix https://llvm.org/bugs/show_bug.cgi?id=30213

When composing an expr for ValueOffsetPair, if the value is of pointer type, we can only create a getelementptr instead of sub expr.

[sanjoy]

lib/Analysis/ScalarEvolutionExpander.cpp

1711 ↗

(On Diff #69871)

I'm not sure it is correct to use getScalarSizeInBits here -- what if ETy is i16 * on a 64 bit machine? Won't getScalarSizeInBits return 16 when it should have returned 64? I think you need to use ScalarEvolution::getTypeSizeInBits.

Secondly, you also need to handle the case when Offset is not divisible by the byte size of ETy (that is, say offset is 6 bytes and ETy is an i32). In that case you'll need to cast V to an i8*, do a byte gep on that value, and then cast the result back to V->getType().

[wmi]

lib/Analysis/ScalarEvolutionExpander.cpp

1711 ↗

(On Diff #69871)

Nice catches. I think you are right for both issues. Will fix them.

[wmi]

Address Sanjoy's comments. I wanted to find a testcase to test the case that the offset is not divisible by the byte size of ETy but didn't succeed, so I forced the code to go through that branch and eyeball the output.

[sanjoy]

I wanted to find a testcase to test the case that the offset is not divisible by the byte size of ETy but didn't succeed, so I forced the code to go through that branch and eyeball the output.

Have you tried writing a C++ test case (in unittests/Analysis)?

lib/Analysis/ScalarEvolutionExpander.cpp

1708 ↗

(On Diff #70971)

More idiomatic is

if (PointerType *VTy = dyn_cast<PointerType>(V->getType())) {
}

1714 ↗

(On Diff #70971)

s/SE.getTypeSizeInBits(Ety)/ESize/

Also, for sanity, I'd suggest making the association on -Offset * 8 / SE.getTypeSizeInBits(Ety) a 100% obvious (i.e. -(Offset * 8) / ESize).

1722 ↗

(On Diff #70971)

In this case I'd s/"scevgep"/"uglygep"/: http://llvm.org/docs/GetElementPtr.html#what-s-an-uglygep

[sanjoy]

.

[wmi]

I didn't try writing a C++ test case. What I tried was to add an assertion in the branch and run a lot of C/C++ benchmarks but I didn't catch such testcase. What's your idea about writting a C++ testcase?

lib/Analysis/ScalarEvolutionExpander.cpp

1708 ↗

(On Diff #70971)

Fixed.

1714 ↗

(On Diff #70971)

Fixed.

1722 ↗

(On Diff #70971)

Fixed.

[sanjoy]

What's your idea about writting a C++ testcase?

[sanjoy]

What's your idea about writting a C++ testcase?

Sorry, fat fingered the previous response. By a C++ test case, I meant writing some C++ code that makes the right calls to getSCEV and SCEVExpander::expand to trigger the bad behavior. I'm not sure if that will be easy or even possible, but it is worth a try.

[wmi]

I never wrote such unittest before, but I just looked at unittests/Analysis/ScalarEvolutionTest.cpp and felt it was indeed more promising to achieve an expected testcase than writing .ll unitest. I will give it a shot. Thanks for the good suggestion.

[wmi]

Create a C++ unittest to exercise the branch where the offset is not divisible by the elem type size of value.

[sanjoy]

lgtm with some comments inline.

unittests/Analysis/ScalarEvolutionTest.cpp

281

You don't need to "manually" create an llvm::Function here. Take a look at how other C++ tests use parseAssemblyString and instruction names to avoid this kind of boilerplate.

Having said that, I don't really mind what you have here, it is just under the level of complexity where using parseAssemblyString would pay off.

293

s/bitcase/bitcast/

302

LLVM style is CastA and CastB.

327

Use EXPECT_TRUE(isa<BitCastInst>(...)) here.

[wmi]

unittests/Analysis/ScalarEvolutionTest.cpp

281

I manually create the function to be consistent with other func in the file and the complexity is not too high. I admit using parseAssemblyString will be simpler, but since it doesn't affect the readability much I tend to be lazy and keep it.

293

Fixed.

302

Ok, fixed.

327

Fixed.

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/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/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
TEST_F(ScalarEvolutionsTest, SimplifiedPHI) {
 
   // At some point, only the first call to getSCEV returned the simplified
   // SCEVConstant and later calls just returned a SCEVUnknown referencing the
   // PHI node.
   EXPECT_EQ(S1, ZeroConst);
   EXPECT_EQ(S1, S2);
 }
 
+TEST_F(ScalarEvolutionsTest, ExpandPtrTypeSCEV) {
+  // It is to test the fix for PR30213. It exercises the branch in scev
+  // expansion when the value in ValueOffsetPair is a ptr and the offset
+  // is not divisible by the elem type size of value.
+  auto *I8Ty = Type::getInt8Ty(Context);
+  auto *I8PtrTy = Type::getInt8PtrTy(Context);
+  auto *I32Ty = Type::getInt32Ty(Context);
+  auto *I32PtrTy = Type::getInt32PtrTy(Context);
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false);
+  Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
+  BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
+  BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);
+  BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);
+  BranchInst::Create(LoopBB, EntryBB);
+  ReturnInst::Create(Context, nullptr, ExitBB);
+
+  // loop:                            ; preds = %loop, %entry
+  //   %alloca = alloca i32
+  //   %gep0 = getelementptr i32, i32* %alloca, i32 1
+  //   %bitcast1 = bitcast i32* %gep0 to i8*
+  //   %gep1 = getelementptr i8, i8* %bitcast1, i32 1
+  //   %gep2 = getelementptr i8, i8* undef, i32 1
+  //   %cmp = icmp ult i8* undef, %bitcast1
+  //   %select = select i1 %cmp, i8* %gep1, i8* %gep2
+  //   %bitcase2 = bitcast i8* %select to i32*
+  //   br i1 undef, label %loop, label %exit
+
+  BranchInst *Br = BranchInst::Create(
+      LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB);
+  AllocaInst *Alloca = new AllocaInst(I32Ty, "alloca", Br);
+  ConstantInt *Ci32 = ConstantInt::get(Context, APInt(32, 1));
+  GetElementPtrInst *Gep0 =
+      GetElementPtrInst::Create(I32Ty, Alloca, Ci32, "gep0", Br);
+  CastInst *Casta =
+      CastInst::CreateBitOrPointerCast(Gep0, I8PtrTy, "bitcast1", Br);
+  GetElementPtrInst *Gep1 =
+      GetElementPtrInst::Create(I8Ty, Casta, Ci32, "gep1", Br);
+  GetElementPtrInst *Gep2 = GetElementPtrInst::Create(
+      I8Ty, UndefValue::get(I8PtrTy), Ci32, "gep2", Br);
+  CmpInst *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_ULT,
+                                 UndefValue::get(I8PtrTy), Casta, "cmp", Br);
+  SelectInst *Sel = SelectInst::Create(Cmp, Gep1, Gep2, "select", Br);
+  CastInst *Castb =
+      CastInst::CreateBitOrPointerCast(Sel, I32PtrTy, "bitcase2", Br);
+
+  ScalarEvolution SE = buildSE(*F);
+  auto *S = SE.getSCEV(Castb);
+  SCEVExpander Exp(SE, M.getDataLayout(), "expander");
+  Value *V =
+      Exp.expandCodeFor(cast<SCEVAddExpr>(S)->getOperand(1), nullptr, Br);
+
+  // Expect the expansion code contains:
+  //   %0 = bitcast i32* %bitcase2 to i8*
+  //   %uglygep = getelementptr i8, i8* %0, i64 -1
+  //   %1 = bitcast i8* %uglygep to i32*
+  BitCastInst *Exp2 = dyn_cast<BitCastInst>(V);
+  GetElementPtrInst *Exp1 = dyn_cast<GetElementPtrInst>(Exp2->getPrevNode());
+  ConstantInt *Cint = dyn_cast<ConstantInt>(Exp1->getOperand(1));
+  EXPECT_NE(dyn_cast<BitCastInst>(Exp1->getPrevNode()), nullptr);
+  EXPECT_NE(Exp1, nullptr);
+  EXPECT_NE(Cint, nullptr);
+  EXPECT_EQ(Cint->getSExtValue(), -1);
+  EXPECT_NE(Exp2, nullptr);
+}
+
 }  // end anonymous namespace
 }  // end namespace llvm