Page MenuHomePhabricator

CFL Alias Analysis
ClosedPublic

Authored by george.burgess.iv on Aug 28 2014, 10:32 AM.

Details

Summary

The algorithms for CFLAA + data structures all in one! (Read: Internship over, so I no longer have access to my gbiv@ email, which I used to make the old revisions).

Old reviews:

This patch contains the algorithm for the CFL Alias Analysis described here: https://docs.google.com/document/d/1nGFKMmr-HbdEiag9G1GeWurgOV0CweSUjLXFr3LAwqg/edit . Currently, we don't have any extremely fancy features, sans some interprocedural analysis (i.e. no field sensitivity, etc.), and we do best sitting behind BasicAA + TBAA.


Diff notes:

Merged WeightedBidirectionalGraph into CFLAliasAnalysis.cpp
Addressed all other feedback, except hfinkel@415. I don't want to stop scanning inside of IPA if we hit noalias/byval because of the following:

int foo(long a, int* b) { *(int**)a = b; }

If the consensus is that such code shouldn't be an issue, then I'll happily speed IPA up a bit.

Sorry for the hurried message -- I have a flight soon. :)
George

Diff Detail

Event Timeline

george.burgess.iv retitled this revision from to CFL Alias Analysis.
george.burgess.iv updated this object.
george.burgess.iv edited the test plan for this revision. (Show Details)
george.burgess.iv added subscribers: sanjoy, Unknown Object (MLST), Jiangning.
hfinkel edited edge metadata.Sep 2 2014, 11:06 AM
  • Original Message -----

From: "George Burgess IV" <george.burgess.iv@gmail.com>
To: "george burgess iv" <george.burgess.iv@gmail.com>, chandlerc@gmail.com, dberlin@dberlin.org, hfinkel@anl.gov,
nlewycky@google.com
Cc: liujiangning1@gmail.com, llvm-commits@cs.uiuc.edu, sanjoy@playingwithpointers.com
Sent: Thursday, August 28, 2014 12:32:19 PM
Subject: [PATCH] CFL Alias Analysis

Hi chandlerc, dberlin, hfinkel, nlewycky,

The algorithms for CFLAA + data structures all in one! (Read:
Internship over, so I no longer have access to my gbiv@ email, which
I used to make the old revisions).

Old reviews:

This patch contains the algorithm for the CFL Alias Analysis
described here:
https://docs.google.com/document/d/1nGFKMmr-HbdEiag9G1GeWurgOV0CweSUjLXFr3LAwqg/edit
. Currently, we don't have any extremely fancy features, sans some
interprocedural analysis (i.e. no field sensitivity, etc.), and we
do best sitting behind BasicAA + TBAA.


Diff notes:

Merged WeightedBidirectionalGraph into CFLAliasAnalysis.cpp
Addressed all other feedback, except hfinkel@415. I don't want to
stop scanning inside of IPA if we hit noalias/byval because of the
following:

int foo(long a, int* b) { *(int**)a = b; }

If the consensus is that such code shouldn't be an issue, then I'll
happily speed IPA up a bit.

I don't understand your comment. Nevertheless, I agree with you for noalias for the following reason: noalias guarantees that pointer values based on the argument do not alias pointer values that are not based on it. Imagine a function that takes two noalias pointers, both with the same value, but the function only accesses odd elements using the first pointer and even elements using the second. This abides by the restriction even though the pointer arguments themselves alias.

However, you can skip the check for byval arguments. For byval, the code generator actually guarantees a unique pointer (because it makes the copy and generates a new pointer at the call site). And so that pointer value cannot flow though any other argument (in any well-defined way). This can be fixed in a follow-up commit.

I'm assuming you don't have commit access; I'll commit this for you later today.

Thanks again,
Hal

Sorry for the hurried message -- I have a flight soon. :)
George

http://reviews.llvm.org/D5106

Files:

include/llvm/Analysis/Passes.h
include/llvm/InitializePasses.h
include/llvm/LinkAllPasses.h
lib/Analysis/CFLAliasAnalysis.cpp
lib/Analysis/CMakeLists.txt
lib/Analysis/StratifiedSets.h
hfinkel accepted this revision.Sep 2 2014, 2:54 PM
hfinkel edited edge metadata.

I committed this as r216970. I adapted some of the BasicAA tests to give us an initial set of regression tests -- we really need some targeted tests as well.

This revision is now accepted and ready to land.Sep 2 2014, 2:54 PM