[MemoryBuiltins] Allow truncation in visitAllocaInst()

[uabelho]

Summary

Solves PR33689.

If the pointer size is less than the size of the type used for the array
size in an alloca (the <ty> type below) then we could trigger the assert in
the PR. In that example we have pointer size i16 and <ty> is i32.

<result> = alloca [inalloca] <type> [, <ty> <NumElements>] [, align <alignment>]

Handle the situation by allowing truncation as well as zero extension in
ObjectSizeOffsetVisitor::visitAllocaInst().

Also, we now detect overflow in visitAllocaInst(), similar to how it was
already done in visitCallSite().

[uabelho]

If the truncation actually truncates something (and not just changes e.g. an i32 1 to an i16 1)
then we are not in a good spot, but then I suppose we have already messed up since then we
would have something like

%foo = alloca i16 , i32 1000000

with pointers being 16b wide so the allocated temporary wouldn't fit in memory
anyway.

I don't know this code very well though so if you think there is a more reasonable fix for this
please let me know.

[george.burgess.iv]

Thanks for this! One nit, and I think it looks good.

lib/Analysis/MemoryBuiltins.cpp

518 ↗

(On Diff #105241)

Addressing your comment: I realize that this is an existing inconsistency, but we try to return unknown() if an overflow happens (e.g. on line 597). While we're in the area, can we make this test for overflow too, please?

[uabelho]

Thanks for the comments!

lib/Analysis/MemoryBuiltins.cpp

518 ↗

(On Diff #105241)

So you want me to detect if overflow actually happens and if so return unknown(), and add a testcase for the overflow case as well?

If so, yes I'll try.

[george.burgess.iv]

lib/Analysis/MemoryBuiltins.cpp

518 ↗

(On Diff #105241)

Yes, please.

I'm not 100% sure if testing this will be straightforward, though. If it seems nontrivial, just let me know. Since it's my nit, I'm happy to try to make a test for overflow and commit it after this lands. :)

[uabelho]

lib/Analysis/MemoryBuiltins.cpp

518 ↗

(On Diff #105241)

Ok I will!

Yes the testing I don't know since I think the test case I have already is pretty non-straightforward.. The i64 is being converted to a [2 x i32] and I think it's that "2" that I will truncate.

So for overflow to happen with just small modifications of my existing test I'll need my %i64_t to be something huge. I'll give it a try though.

[uabelho]

Added overflow checks to visitAllocaInst.

To avoid some code duplication I pulled out the CheckedZextOrTrunc lambda from visitCallSite
and made a member function of it.

[uabelho]

lib/Analysis/MemoryBuiltins.cpp

518 ↗

(On Diff #105241)

Added overflow checks. Something like this is what you had in mind?

For the testcase, if I change
%i64_t = type i64
to
%i64_t = type i6488888
then the overflow checks trigger, but the end result from instcombine is still the same
as without overflow checks so I don't have any nice output change to check for.

If you know this code then I suppose you'll be able to make a testcase for it.

[george.burgess.iv]

LGTM after a few stylistic nits are addressed. Thanks again!

lib/Analysis/MemoryBuiltins.cpp

511 ↗

(On Diff #105810)

I think it's \p I, though I'm admittedly not great with doxygen.

522 ↗

(On Diff #105810)

Please remove the trailing ;

535 ↗

(On Diff #105810)

Please remove the brackets, since this is a single-statement if

518 ↗

(On Diff #105241)

Something like this is what you had in mind?

Yup!

If you know this code then I suppose you'll be able to make a testcase for it

Will do. :)

[uabelho]

Addressed the few remaining issues.

(Totally idiotic to not see them myself to begin with. Sorry and thanks!)

Updated the summary so it now has a few words about the new overflow
checks in visitAllocaInst().

[uabelho]

Thanks!

[george.burgess.iv]

LGTM!

Totally idiotic to not see them myself to begin with. Sorry and thanks!

Not a problem :)

[uabelho]

Apparently I accidentally dropped the test case between two revisions of this patch so I submitted it
now in https://reviews.llvm.org/rL307887

llvm/trunk/include/llvm/Analysis/MemoryBuiltins.h

public:
   SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
   SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
   SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
   SizeOffsetType visitLoadInst(LoadInst &I);
   SizeOffsetType visitPHINode(PHINode&);
   SizeOffsetType visitSelectInst(SelectInst &I);
   SizeOffsetType visitUndefValue(UndefValue&);
   SizeOffsetType visitInstruction(Instruction &I);
+
+private:
+  bool CheckedZextOrTrunc(APInt &I);
 };
 
 typedef std::pair<Value*, Value*> SizeOffsetEvalType;
 
 
 /// \brief Evaluate the size and offset of an object pointed to by a Value*.
 /// May create code to compute the result at run-time.
 class ObjectSizeOffsetEvaluator

llvm/trunk/lib/Analysis/MemoryBuiltins.cpp

if (CE->getOpcode() == Instruction::GetElementPtr)
       return visitGEPOperator(cast<GEPOperator>(*CE));
   }
 
   DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V
         << '\n');
   return unknown();
 }
 
+/// When we're compiling N-bit code, and the user uses parameters that are
+/// greater than N bits (e.g. uint64_t on a 32-bit build), we can run into
+/// trouble with APInt size issues. This function handles resizing + overflow
+/// checks for us. Check and zext or trunc \p I depending on IntTyBits and
+/// I's value.
+bool ObjectSizeOffsetVisitor::CheckedZextOrTrunc(APInt &I) {
+  // More bits than we can handle. Checking the bit width isn't necessary, but
+  // it's faster than checking active bits, and should give `false` in the
+  // vast majority of cases.
+  if (I.getBitWidth() > IntTyBits && I.getActiveBits() > IntTyBits)
+    return false;
+  if (I.getBitWidth() != IntTyBits)
+    I = I.zextOrTrunc(IntTyBits);
+  return true;
+}
+
 SizeOffsetType ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) {
   if (!I.getAllocatedType()->isSized())
     return unknown();
 
   APInt Size(IntTyBits, DL.getTypeAllocSize(I.getAllocatedType()));
   if (!I.isArrayAllocation())
     return std::make_pair(align(Size, I.getAlignment()), Zero);
 
   Value *ArraySize = I.getArraySize();
   if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) {
-    Size *= C->getValue().zextOrSelf(IntTyBits);
-    return std::make_pair(align(Size, I.getAlignment()), Zero);
+    APInt NumElems = C->getValue();
+    if (!CheckedZextOrTrunc(NumElems))
+      return unknown();
+
+    bool Overflow;
+    Size = Size.umul_ov(NumElems, Overflow);
+    return Overflow ? unknown() : std::make_pair(align(Size, I.getAlignment()),
+                                                 Zero);
   }
   return unknown();
 }
 
 SizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) {
   // No interprocedural analysis is done at the moment.
   if (!A.hasByValOrInAllocaAttr()) {
     ++ObjectVisitorArgument;
if (FnData->AllocTy == StrDupLike) {
     }
     return std::make_pair(Size, Zero);
   }
 
   ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
   if (!Arg)
     return unknown();
 
-  // When we're compiling N-bit code, and the user uses parameters that are
-  // greater than N bits (e.g. uint64_t on a 32-bit build), we can run into
-  // trouble with APInt size issues. This function handles resizing + overflow
-  // checks for us.
-  auto CheckedZextOrTrunc = [&](APInt &I) {
-    // More bits than we can handle. Checking the bit width isn't necessary, but
-    // it's faster than checking active bits, and should give `false` in the
-    // vast majority of cases.
-    if (I.getBitWidth() > IntTyBits && I.getActiveBits() > IntTyBits)
-      return false;
-    if (I.getBitWidth() != IntTyBits)
-      I = I.zextOrTrunc(IntTyBits);
-    return true;
-  };
-
   APInt Size = Arg->getValue();
   if (!CheckedZextOrTrunc(Size))
     return unknown();
 
   // Size is determined by just 1 parameter.
   if (FnData->SndParam < 0)
     return std::make_pair(Size, Zero);