[MemoryBuiltins] Determine the size of a global w/o initializer

[jdoerfert]

Summary

NOTE: This is a patch to help start a discussion in response to http://lists.llvm.org/pipermail/llvm-dev/2020-January/138725.html

The idea is that a initializer is not necessary if we know the
definition is exact and it is not an empty object.

[merge_guards_bot]

Unit tests: pass. 62318 tests passed, 0 failed and 838 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[george.burgess.iv]

Thanks for this!

It's been a while since I've worked with memory-ish things in LLVM. Please forgive my questions if they're silly :)

This approach looks good to me, with the caveat that I'm not an expert in all of the creative, "supported" tricks that exist for lying to the compiler about object sizes.

Please also add a test for a zero-sized and nonzero-sized global (llvm.objectsize might be a good hammer for that?). Otherwise, I'm happy when Hal is

llvm/test/Analysis/BasicAA/bug.23540.ll

11

Can you expand a bit on why PartialAlias is the correct answer here, please?

I'd naively expect this to be either MustAlias (both pointers are to a 32 bit object, and there're only 32 bits in this allocation; derefing anything else is UB), or MayAlias (there're only 32 bits here, but maaaaybe you're pointing to ((int*)&c + 1), and that's OK.)

[jdoerfert]

In D73679#1850893, @george.burgess.iv wrote:

Please also add a test for a zero-sized and nonzero-sized global (llvm.objectsize might be a good hammer for that?).

So there are existing test with 0 sized objects that would fail if we do not have the Size != 0 check but I'll add a few more to nail down what we expect as soon as I find the time. It might take a week or two though.

llvm/test/Analysis/BasicAA/bug.23540.ll

11

My reasoning is that arrayidx6 points right after c and arrayidx points somewhere based on c. There are no accesses so the alias query is done with an unspecified size on the access part which should mean the two accesses can very well overlap.

[george.burgess.iv]

So there are existing test with 0 sized objects that would fail if we do not have the Size != 0 check but I'll add a few more to nail down what we expect as soon as I find the time. It might take a week or two though.

SGTM -- thanks!

llvm/test/Analysis/BasicAA/bug.23540.ll

11

I don't quite agree with the unspecified size part: if the access size were entirely unknown, we could only correctly return PartialAlias in cases with provably identical object offsets, since PartialAlias *guarantees* the two accesses will overlap somehow.

Experimentally, we report NoAlias for (%b, %c) in:

define void @f() {
  %a = alloca i32
  %b = bitcast i32* %a to i8*
  %c = getelementptr i8, i8* %b, i64 1
  ret void
}

So I think the sizes here should be 4 bytes. If that's the case, MustAlias seems like the optimal answer, which means that PartialAlias is also correct. sizeof(access) == sizeof(underlying_object) in both cases means there's really no room for nonzero object offsets. :)

If this sounds correct, please update the newly-added comment.

[jdoerfert]

llvm/test/Analysis/BasicAA/bug.23540.ll

11

So I added a d = gep %b, undef which is closer to the test case that changed and which results in a MayAlias: https://godbolt.org/z/KT4F5z

I don't follow the MustAlias argument. There is no access here, so we talk about pointers only.
The pointers are based on the same thing with an unknown offset from each other (at least that seems to me how undef is interpreted here).

I'll come up with more tests asap.

[george.burgess.iv]

llvm/test/Analysis/BasicAA/bug.23540.ll

11

There is no access here, so we talk about pointers only.

Correct; I was just interpreting

There are no accesses so the alias query is done with an unspecified size on the access part

as "the alias queries get handed LocationSizes that don't hasValue()." If the sizes were unspecified, we'd get MayAlias instead of NoAlias for the (%b, %c) query on your godbolt link.

The MustAlias argument is based on this, but is honestly more of a tangent than anything. Referring again to the godbolt link, the only derefable (in a well-defined way) i32* we can form from %a must point directly to %a. So if we have two i32*s based on %a, ISTM inferring MustAlias would be valid, since MustAlias doesn't imply pointer equality.

In any case, we both now agree that PartialAlias is OK here, so I'm happy to call this resolved unless you wanna dive further into this :)

llvm/lib/Analysis/MemoryBuiltins.cpp

 
 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) {
   if (GA.isInterposable())
     return unknown();
   return compute(GA.getAliasee());
 }
 
 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){
-  if (!GV.hasDefinitiveInitializer())
+  // Make sure we have an exact definition that cannot be changed.
+  if (!GV.isDefinitionExact())
     return unknown();
-
+  // Weed out any flexible array types.
   APInt Size(IntTyBits, DL.getTypeAllocSize(GV.getValueType()));
+  if (Size.isNullValue())
+    return unknown();
   return std::make_pair(align(Size, GV.getAlignment()), Zero);
 }
 
 SizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) {
   // clueless
   return unknown();
 }
 

llvm/test/Analysis/BasicAA/bug.23540.ll

 ; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @c = external global i32
 
+; Since there are no sizes and both accesses are based on the same global they
+; (can) partially overlap.
+
 ; CHECK-LABEL: f
-; CHECK: MayAlias: i32* %arrayidx, i32* %arrayidx6
+; CHECK: PartialAlias: i32* %arrayidx, i32* %arrayidx6
 define void @f() {
   %idxprom = zext i32 undef to i64
   %add4 = add i32 0, 1
   %idxprom5 = zext i32 %add4 to i64
   %arrayidx6 = getelementptr inbounds i32, i32* @c, i64 %idxprom5
   %arrayidx = getelementptr inbounds i32, i32* @c, i64 %idxprom
   ret void
 }