[CFLAA] Improving the precision of cfl-aa for inttoptr and ptrtoint

[grievejia]

Summary

Previously, pointers obtained from/to inttoptr/ptrtoint are treated like arguments and globals. According to the Pointer Aliasing Rule section in LLVM Language Reference, inttoptr-pointers can only alias with values that it depends on. Therefore, it is ok to be less conservative by handling inttoptr and ptrtoint in the same way as we handle bitcasts.

[eli.friedman]

test/Analysis/CFLAliasAnalysis/int_ptr_cast.ll

13

Consider the following testcase:

%q = alloca i64, align 8
%qint = ptrtoint i64* %q to i64
%qint2 = add i64 %n, %qint
%qint2 = sub i64 %n, %qint
%qcast = inttoptr i64 %qint2 to i64*

Suppose the function is then called with p==n. Then %qcast == %p.

Also, it's possible to propagate a dependency through comparison instructions; consider, for example:

void f(unsigned * p, unsigned n) {
  int q;
  int qint = (unsigned )&q;
  while (qint != n) ++qint;
  *(unsigned*)qint = 3; // modifies *p
}

[grievejia]

test/Analysis/CFLAliasAnalysis/int_ptr_cast.ll

13

Thank you so much for the comment!

Your first example might unveil a bug in the codes (and another bug in my test). I think the current algorithm cfl-aa uses should be able to handle that, but it didn't.

Your second example basically kills this patch. Control dependency is something that I failed to take into account. I'd like to argue that codes like that is very broken and should be fixed, but since this is permitted by the specification, for now it's not worth the pain to deal with it in any precise way.

[george.burgess.iv]

If this patch is obsolete, could you abandon it (choose "Abandon Revision" in the Action dropdown), please? :)

lib/Analysis/CFLAliasAnalysis.cpp

const StratifiedIndex StratifiedLink::SetSentinel =
     std::numeric_limits<StratifiedIndex>::max();
 
 namespace {
 /// StratifiedInfo Attribute things.
 typedef unsigned StratifiedAttr;
 LLVM_CONSTEXPR unsigned MaxStratifiedAttrIndex = NumStratifiedAttrs;
 LLVM_CONSTEXPR unsigned AttrAllIndex = 0;
 LLVM_CONSTEXPR unsigned AttrGlobalIndex = 1;
-LLVM_CONSTEXPR unsigned AttrUnknownIndex = 2;
-LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 3;
+LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 2;
 LLVM_CONSTEXPR unsigned AttrLastArgIndex = MaxStratifiedAttrIndex;
 LLVM_CONSTEXPR unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex;
 
 LLVM_CONSTEXPR StratifiedAttr AttrNone = 0;
-LLVM_CONSTEXPR StratifiedAttr AttrUnknown = 1 << AttrUnknownIndex;
 LLVM_CONSTEXPR StratifiedAttr AttrAll = ~AttrNone;
 
 /// StratifiedSets call for knowledge of "direction", so this is how we
 /// represent that locally.
 enum class Level { Same, Above, Below };
 
 /// Edges can be one of four "weights" -- each weight must have an inverse
 /// weight (Assign has Assign; Reference has Dereference).
GetEdgesVisitor(CFLAAResult &AA, SmallVectorImpl<Edge> &Output,
       : AA(AA), Output(Output), TLI(TLI) {}
 
   void visitInstruction(Instruction &) {
     llvm_unreachable("Unsupported instruction encountered");
   }
 
   void visitPtrToIntInst(PtrToIntInst &Inst) {
     auto *Ptr = Inst.getOperand(0);
-    Output.push_back(Edge(Ptr, Ptr, EdgeType::Assign, AttrUnknown));
+    Output.push_back(Edge(&Inst, Ptr, EdgeType::Assign, AttrNone));
   }
 
   void visitIntToPtrInst(IntToPtrInst &Inst) {
-    auto *Ptr = &Inst;
-    Output.push_back(Edge(Ptr, Ptr, EdgeType::Assign, AttrUnknown));
+    auto *Src = Inst.getOperand(0);
+    Output.push_back(Edge(&Inst, Src, EdgeType::Assign, AttrNone));
   }
 
   void visitCastInst(CastInst &Inst) {
     Output.push_back(
         Edge(&Inst, Inst.getOperand(0), EdgeType::Assign, AttrNone));
   }
 
   void visitBinaryOperator(BinaryOperator &Inst) {

test/Analysis/CFLAliasAnalysis/int_ptr_cast.ll

+; This testcase ensures that inttoptr pointer only aliases pointers that it depends on
+
+; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK: Function: test_value_dep
+; CHECK: NoAlias: i64* %p, i64* %qcast
+; CHECK: MayAlias: i64* %q, i64* %qcast
+define void @test_value_dep(i64* %p, i64 %n) {
+  %q = alloca i64, align 8
+  %qint = ptrtoint i64* %q to i64
+  %qint2 = add nsw i64 %qint, %n
+  %qcast = inttoptr i64 %qint2 to i64*
+  ret void
+}
+
+; CHECK: Function: test_memory_dep
+; CHECK: NoAlias: i64* %p, i64* %qcast
+; CHECK: MayAlias: i64* %q, i64* %qcast
+; CHECK: NoAlias: i64* %qcast, i64* %r
+define void @test_memory_dep(i64* %p) {
+  %q = alloca i64, align 8
+  %qint = ptrtoint i64* %q to i64
+  
+  %r = alloca i64, align 8
+  store i64 %qint, i64* %r
+
+  %qint2 = load i64, i64* %r
+  %qcast = inttoptr i64 %qint2 to i64*
+  ret void
+}