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

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

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

More idiomatic is

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

1714

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

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

Fixed.

1714

Fixed.

1722

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 ↗

(On Diff #71398)

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 ↗

(On Diff #71398)

s/bitcase/bitcast/

302 ↗

(On Diff #71398)

LLVM style is CastA and CastB.

327 ↗

(On Diff #71398)

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

[wmi]

unittests/Analysis/ScalarEvolutionTest.cpp

281 ↗

(On Diff #71398)

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 ↗

(On Diff #71398)

Fixed.

302 ↗

(On Diff #71398)

Ok, fixed.

327 ↗

(On Diff #71398)

Fixed.

lib/Analysis/ScalarEvolutionExpander.cpp

Value *SCEVExpander::expand(const SCEV *S) {
   Builder.SetInsertPoint(InsertPt);
 
   // Expand the expression into instructions.
   ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, InsertPt);
   Value *V = VO.first;
 
   if (!V)
     V = visit(S);
-  else if (VO.second)
+  else if (VO.second) {
+    if (V->getType()->isPointerTy()) {
+      Type *Ety = V->getType()->getPointerElementType();
+      int64_t Offset = VO.second->getSExtValue();
+      ConstantInt *Idx = ConstantInt::getSigned(
+          VO.second->getType(), -Offset * 8 / Ety->getScalarSizeInBits());
+      V = Builder.CreateGEP(Ety, V, Idx, "scevgep");
+    } else {
       V = Builder.CreateSub(V, VO.second);
-
+    }
+  }
   // Remember the expanded value for this SCEV at this location.
   //
   // This is independent of PostIncLoops. The mapped value simply materializes
   // the expression at this insertion point. If the mapped value happened to be
   // a postinc expansion, it could be reused by a non-postinc user, but only if
   // its insertion point was already at the head of the loop.
   InsertedExpressions[std::make_pair(S, InsertPt)] = V;
   return V;
 }
 
 void SCEVExpander::rememberInstruction(Value *I) {
   if (!PostIncLoops.empty())
     InsertedPostIncValues.insert(I);
   else

test/Analysis/ScalarEvolution/pr30213.ll

+; PR30213
+; RUN: opt < %s -loop-reduce -S | FileCheck %s
+
+; CHECK: %ptr4.ptr1 = select i1 %cmp.i, i8* %ptr4, i8* %ptr1
+; CHECK-NEXT: %scevgep = getelementptr i8, i8* %ptr4.ptr1, i32 1
+; CHECK-NEXT: br label %while.cond.i
+
+target datalayout = "e-m:o-p:32:32-f64:32:64-f80:128-n8:16:32-S128"
+target triple = "i386-apple-macosx10.12.0"
+
+; Function Attrs: nounwind optsize ssp
+define void @Foo() {
+entry:
+  switch i2 undef, label %sw.epilog102 [
+    i2 -2, label %sw.bb28
+  ]
+
+sw.bb28:                                          ; preds = %entry
+  %0 = load i8*, i8** undef, align 2
+  %ptr1 = getelementptr inbounds i8, i8* undef, i32 -1
+  %ptr4 = getelementptr inbounds i8, i8* %0, i32 -1
+  %cmp.i = icmp ult i8* undef, %0
+  %ptr4.ptr1 = select i1 %cmp.i, i8* %ptr4, i8* %ptr1
+  br label %while.cond.i
+
+while.cond.i:                                     ; preds = %while.cond.i, %sw.bb28
+  %currPtr.1.i = phi i8* [ %incdec.ptr.i, %while.cond.i ], [ %ptr4.ptr1, %sw.bb28 ]
+  %incdec.ptr.i = getelementptr inbounds i8, i8* %currPtr.1.i, i32 1
+  %1 = load i8, i8* %incdec.ptr.i, align 1
+  br label %while.cond.i
+
+sw.epilog102:                                     ; preds = %entry
+  unreachable
+}
+