CFL AA Tests + Minor Fix

[george.burgess.iv]

Summary

Added some functionality tests for CFL AA, and made a minor fix to CFL AA

• CFL AA fix: We used to return PartialAlias if *either* variable being queried interacted with arguments or globals. AFAICT, we can change this to only returning PartialAlias iff *both* variables being queried interacted with arguments or globals.
• Functionality tests: some basic IPA tests, checking that we give conservative responses with arguments/globals thrown in the mix, and ensuring that we trace values through stores and loads.

x interacted with arguments or globals = the Attributes of the StratifiedSet that x belongs to has any bits set.

[hfinkel]

Why does PartialAlias have anything to do with arguments or globals? We should return PartialAlias when we know that the two pointers partially overlap.

[george.burgess.iv]

We now return MayAlias instead of PartialAlias if the only thing that could make variables alias is the aliasing of arguments/globals.

[hfinkel]

lib/Analysis/CFLAliasAnalysis.cpp

989–999

Can you please add some comments here explaining what is going on? It seems like this is a significant change: Previously, we would return NoAlias only if none of the bits in either AttrsA or AttrsB were set. Now we'll return NoAlias if either of AttrsA or AttrsB have no bits set. So this seems to be doing much more than changing a PartialAlias to a MayAlias in some circumstances.

[george.burgess.iv]

Added comments as requested. I'm happy to swap the condition back if you don't agree with the change.

[hfinkel]

Okay, thanks! LGTM.

P.S. Have you had a change to look at: http://llvm.org/bugs/show_bug.cgi?id=20954

[hfinkel]

r219122.

lib/Analysis/CFLAliasAnalysis.cpp

 
   auto AttrsA = Sets.getLink(SetA.Index).Attrs;
   auto AttrsB = Sets.getLink(SetB.Index).Attrs;
-  auto CombinedAttrs = AttrsA | AttrsB;
-  if (CombinedAttrs.any())
-    return AliasAnalysis::PartialAlias;
+  // Stratified set attributes are used as markets to signify whether a member
+  // of a StratifiedSet (or a member of a set above the current set) has 
+  // interacted with either arguments or globals. "Interacted with" meaning
+  // its value may be different depending on the value of an argument or 
+  // global. The thought behind this is that, because arguments and globals
+  // may alias each other, if AttrsA and AttrsB have touched args/globals,
+  // we must conservatively say that they alias. However, if at least one of 
+  // the sets has no values that could legally be altered by changing the value 
+  // of an argument or global, then we don't have to be as conservative.
+  if (AttrsA.any() && AttrsB.any())
+    return AliasAnalysis::MayAlias;
 
   return AliasAnalysis::NoAlias;
 }

test/Analysis/CFLAliasAnalysis/arguments-globals.ll

+; This testcase ensures that CFL AA gives conservative answers on variables
+; that involve arguments.
+; (Everything should alias everything, because args can alias globals, so the
+; aliasing sets should of args+alloca+global should be combined)
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK:     Function: test
+
+@g = external global i32
+
+define void @test(i1 %c, i32* %arg1, i32* %arg2) {
+  ; CHECK: 15 Total Alias Queries Performed
+  ; CHECK: 0 no alias responses
+  %A = alloca i32, align 4
+  %B = select i1 %c, i32* %arg1, i32* %arg2
+  %C = select i1 %c, i32* @g, i32* %A
+
+  ret void
+}

test/Analysis/CFLAliasAnalysis/arguments.ll

+; This testcase ensures that CFL AA gives conservative answers on variables
+; that involve arguments.
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK:     Function: test
+
+define void @test(i1 %c, i32* %arg1, i32* %arg2) {
+  ; CHECK: 6 Total Alias Queries Performed
+  ; CHECK: 3 no alias responses
+  %a = alloca i32, align 4
+  %b = select i1 %c, i32* %arg1, i32* %arg2
+
+  ret void
+}

test/Analysis/CFLAliasAnalysis/basic-interproc-ret.ll

+; This testcase ensures that CFL AA gives conservative answers on variables
+; that involve arguments.
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK:     Function: test
+; CHECK: 4 Total Alias Queries Performed
+; CHECK: 3 no alias responses
+; ^ The 1 MayAlias is due to %arg1. Sadly, we don't currently have machinery
+; in place to check whether %arg1 aliases %a, because BasicAA takes care of 
+; that for us.
+
+define i32* @test2(i32* %arg1) {
+  store i32 0, i32* %arg1
+
+  %a = alloca i32, align 4
+  ret i32* %a
+}
+
+define void @test() {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %c = call i32* @test2(i32* %a)
+
+  ret void
+}

test/Analysis/CFLAliasAnalysis/basic-interproc.ll

+; This testcase ensures that CFL AA gives conservative answers on variables
+; that involve arguments.
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK:     Function: test
+; CHECK: 2 Total Alias Queries Performed
+; CHECK: 1 no alias responses
+; ^^ In @test2, %arg1 and %arg2 may alias
+
+define void @test2(i32* %arg1, i32* %arg2) {
+  store i32 0, i32* %arg1
+  store i32 0, i32* %arg2
+
+  ret void
+}
+
+define void @test() {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  call void @test2(i32* %a, i32* %b)
+
+  ret void
+}

test/Analysis/CFLAliasAnalysis/multilevel-combine.ll

+; This testcase ensures that CFL AA responds conservatively when we union 
+; groups of pointers together through ternary/conditional operations
+; Derived from:
+; void foo(bool c) {
+;   char a, b;
+;   char *m = c ? &a : &b;
+;   *m;
+; }
+;
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+%T = type { i32, [10 x i8] }
+
+; CHECK:     Function: test
+
+define void @test(i1 %C) {
+; CHECK: 10 Total Alias Queries Performed
+; CHECK: 4 no alias responses
+  %M = alloca %T*, align 8 ; NoAlias with %A, %B, %MS, %AP
+  %A = alloca %T, align 8
+  %B = alloca %T, align 8
+
+  %MS = select i1 %C, %T* %B, %T* %A
+
+  store %T* %MS, %T** %M
+
+  %AP = load %T** %M ; PartialAlias with %A, %B
+
+  ret void
+}

test/Analysis/CFLAliasAnalysis/multilevel.ll

+; This testcase ensures that CFL AA handles trivial cases with storing 
+; pointers in pointers appropriately.
+; Derived from:
+; char a, b;
+; char *m = &a, *n = &b;
+; *m;
+; *n;
+
+; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+%T = type { i32, [10 x i8] }
+
+; CHECK:     Function: test
+
+define void @test() {
+; CHECK: 15 Total Alias Queries Performed
+; CHECK: 13 no alias responses
+  %M = alloca %T*, align 8
+  %N = alloca %T*, align 8
+  %A = alloca %T, align 8
+  %B = alloca %T, align 8
+
+  store %T* %A, %T** %M
+  store %T* %B, %T** %N
+
+  %AP = load %T** %M ; PartialAlias with %A
+  %BP = load %T** %N ; PartialAlias with %B
+
+  ret void
+}