[CFLAA] Remove redundant aliasing relation between GEP indices and GEP result

[grievejia]

Summary

As shown in the diff, if cfl-aa encounters a GEP instructions y = gep x, z, we used to treat y and z as potential aliases. However, according to the "Pointer Aliasing Rule" section of LLVM Language Reference, this decision turns out to be overly defensive.

[• dberlin]

Hey Jia,
You need to add testcases for this :)

[grievejia]

In D20775#443337, @dberlin wrote:

Hey Jia,
You need to add testcases for this :)

I tried and found it pretty hard to come up with a test case that can target this particular patch specifically.

The issue here is that the gep indices must be integers. To test for aliasing relation between a gep result and another pointer that acts like a gep index, there must be a ptr-to-int cast or an int-to-ptr cast. Cfl-aa is currently very conservative about both inttoptr and ptrtoint. Therefore as long as the inttoptr/ptrtoint handling stays the same, it's not possible for this patch to alter the behavior of cfl-aa in any observable way!

I'll try to upload another patch later that fix this issue by making cfl-aa treats ptrtoint as a no-op. Is it ok if I attach the test cases to that patch instead?

[george.burgess.iv]

I would think (read: haven't tried it yet :) ) that something like:

define void @foo(i32 %n) {
  %a = alloca [2 x i32], align 4
  %b = alloca [2 x i32], align 4
  %c = getelementptr inbounds [2 x i32]* %a, i32 0, i32 %n
  %d = getelementptr inbounds [2 x i32]* %b, i32 0, i32 %n
  ret void
}

Would work as a test case for this (used to alias before, doesn't alias now). Does it not?

[grievejia]

Good point!

I start to wonder why I haven't thought about this earlier...

[grievejia]

Added test case

[george.burgess.iv]

LGTM; will commit. Thanks for the patch :)

lib/Analysis/CFLAliasAnalysis.cpp

public:
   void visitPHINode(PHINode &Inst) {
     for (Value *Val : Inst.incoming_values())
       Output.push_back(Edge(&Inst, Val, EdgeType::Assign, AttrNone));
   }
 
   void visitGetElementPtrInst(GetElementPtrInst &Inst) {
     auto *Op = Inst.getPointerOperand();
     Output.push_back(Edge(&Inst, Op, EdgeType::Assign, AttrNone));
-    for (auto I = Inst.idx_begin(), E = Inst.idx_end(); I != E; ++I)
-      Output.push_back(Edge(&Inst, *I, EdgeType::Assign, AttrNone));
   }
 
   void visitSelectInst(SelectInst &Inst) {
     // Condition is not processed here (The actual statement producing
     // the condition result is processed elsewhere). For select, the
     // condition is evaluated, but not loaded, stored, or assigned
     // simply as a result of being the condition of a select.
 

test/Analysis/CFLAliasAnalysis/gep-index-no-alias.ll

+; This testcase ensures that gep result does not alias gep indices
+
+; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK: Function: foo
+; CHECK: [2 x i32]* %a, [2 x i32]* %b
+define void @foo(i32 %n) {
+  %a = alloca [2 x i32], align 4
+  %b = alloca [2 x i32], align 4
+  %c = getelementptr inbounds [2 x i32], [2 x i32]* %a, i32 0, i32 %n
+  %d = getelementptr inbounds [2 x i32], [2 x i32]* %b, i32 0, i32 %n
+  ret void
+}
 No newline at end of file