LLVM CFL Alias Analysis -- Algorithm

[george.burgess.iv]

Summary

Note: WeightedBidirectedGraph and StratifiedSets are in their own patch titled "LLVM CFL Alias Analysis -- Supporting Data Structures".

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 (no interprocedural analysis, no field sensitivity, etc.), and we do best sitting behind BasicAA + TBAA. In such a configuration, we take ~0.6-0.8% of total compile time, and give ~7-8% NoAlias responses to queries TBAA and BasicAA couldn't answer when bootstrapping LLVM. In testing this on other projects, we've seen up to 10.5% of queries dropped by BasicAA+TBAA answered with NoAlias by this algorithm. While an extensive investigation hasn't been conducted, the code being compiled ran properly + passed the unit tests we ran. So, the bugs remaining are probably super subtle. :)

WRT design quirks:

This is implemented as an ImmutablePass that holds its own state. Upon making this a FunctionPass, it gets constructed, but nothing ever calls it.

Other notes:

Chandler had the idea of making a simple FunctionPass that drops the StratifiedSets cache after inlining. Because AFAICT most of our sets are realized prior to inlining, we'll probably be able to give back better results if we do this.
I still have ~3.5 weeks of my internship, during which the code will change more, and I'll do extensive testing/profiling. Places I plan to change are noted in the code.

[• dberlin]

Some preliminary comments on this one as well

lib/Analysis/CFLAliasAnalysis.cpp

122

Unless i'm miscounting braces, doesn't this cause this function to always return MayAlias?
I assume this was just debugging code that was left in when you were running final numbers, since i've seen the actual numbers :)

143

AssignTo appears unused, and could you add a comment about what type of statement you expect each to represent.

294

Can you talk a bit about why the Insert* calls are Reference edges, instead of say, assignto?

[• gbiv]

lib/Analysis/CFLAliasAnalysis.cpp

122

Yup, it's from testing timing/etc. My apologies/will be removed in the next revision.. :)

143

It's meant to be the counterpart for AssignFrom, because we're using a bidirected graph. Will add comments and will condense AssignFrom/AssignTo down to Assign if the From/To ends up giving us nothing.

294

Good point! Fixed in next rev.

[• gbiv]

+hfinkel

Addressed Danny's comments, fixed a bug where we wouldn't properly handle exceptions, (i.e. in try {} catch (Foo& f) {}, f would be ignored, when it really needs to be treated like an aliasing external.) and added an extra field to Edge so interprocedural is easier to integrate.

[hfinkel]

Hi again,

+ algorithm. It does not depend on types The algorithm is a mixture of the one
+ described here: www.cs.cornell.edu/~rugina/papers/popl08.pdf and here:
+// www.cse.cuhk.edu.hk/lyu/_media/paper/pldi2013.pdf -- to summarize the papers,

Again, actual references please.

+static bool getPossibleTargets(Inst *, SmallVectorImpl<Function *> *);

Why is this not SmallVectorImpl<Function *> & ?

+ There are certain instructions (i.e. FenceInst, etc.) that we ignore.
+ This detects those.
+static bool hasUsefulEdges(Instruction *inst);

This returns true when we don't ignore the instruction?

+ // TODO: Maybe merge this with AssignFrom if it carries no benefit.

Please place this comment near the relevant code.

+ // TODO: Rename this + Reference

Okay, please do.

+ %b = load %a (%b Dereference %a)
+ %b = extractelement %a, 0 (%b Dereference %a)

I suppose this second item is what motivates the renaming?

+ /// If a function's sets arecurrently being built, it is marked

are currently

+struct CFLAliasAnalysis : public ImmutablePass, public AliasAnalysis {
+private:
...
+ DenseMap<Function *, Optional<StratifiedSets<Value *>>> cache;

This is an ImmutablePass and keeps a cache of Function* -- This is dangerous because a function would be deleted and new one created at the same address. You probably want to use a CallbackVH from llvm/IR/ValueHandle.h so that you can get notified if the Fuction is removed and remove it from the cache. (The ScalarEvolution analysis does something like this).

+ // This should be covered by BasicAA, but it's super cheap to check.

As a genral note, you must not constuct an AA pass assuming that BasicAA will filter for you. Your pass must independently return correct answers for all cases.

+ Currently everything returns an Optional<bool> because it makes life easier
+ to be able to selectively disable support for instructions and troubleshoot
+ our coverage of the instructions we'll get. I plan to remove this as this AA
+ gets tested more/nearer finalization.

Alright, please add a FIXME, an assert, an llvm_unreachable, or something.

+// Nothing - Unknown instruction. Program should die.

Let's leave dying for another day.

(Actually, if you're ready to remove the Optional now, please do).

+ CFLAliasAnalysis *aa;
+ SmallVectorImpl<Edge> *output;

These can be refeences?

+ Optional<bool> visitInstruction(Instruction &) { return NoneType(); }

llvm_unreachable("CFL AA does not know about this kind of instruction");

+ Optional<bool> visitBinaryOperator(BinaryOperator &inst) {
+ auto *op1 = inst.getOperand(0);
+ auto *op2 = inst.getOperand(1);
+ output->push_back({&inst, op1, EdgeWeight::AssignFrom, false});
+ output->push_back({&inst, op2, EdgeWeight::AssignFrom, false});

Do we actually need edges for all binary operators, or only those that could be part of pointer arithmetic? Meaning, can we exclude the floating-point operators, for example?

+ for (unsigned i = 0, e = inst.getNumIncomingValues(); i < e; ++i) {
+ Value *val = inst.getIncomingValue(i);
+ output->push_back({&inst, val, EdgeWeight::AssignFrom, false});
+ }

Does it matter if you add duplicate edges here? A funny property of LLVM phis is that they can have duplicate entries for the same predecessor block so long as the values also match.

+ static bool isFunctionExternal(Function *fn) {
+ return fn->getBasicBlockList().empty();
+ }

This is not the correct way to test for this. I think you want !fn->isDeclaration() && fn->hasLocalLinkage().

+ bool onlyReadMemory =
+ std::all_of(fns.begin(), fns.end(),
+ [](const Function *fn) { return fn->onlyReadsMemory(); });

What does this check have to do with IPA? If this property is true, then it is true regardless of whether the function is local or not. This is how it is defined (it is definitional, not speculative).

+ for (Value *v : inst.arg_operands()) {
+ output->push_back({&inst, v, EdgeWeight::AssignFrom, true});
+ }

Do you need this for calls returning void?

+ Optional<bool> visitShuffleVectorInst(ShuffleVectorInst &inst) {
+ auto *from1 = inst.getOperand(0);
+ auto *from2 = inst.getOperand(1);
+ output->push_back({&inst, from1, EdgeWeight::AssignFrom, false});
+ output->push_back({&inst, from2, EdgeWeight::AssignFrom, false});
+ return true;
+ }

Many vector shuffles have an Undef second operand, I assume you don't need an edge for those. On that thought, you should probably filter out edges from undef everywhere.

+class GetTargetValueVisitor
+ : public InstVisitor<GetTargetValueVisitor, Optional<Value *>> {
+public:
+ Optional<Value *> visitInstruction(Instruction &) { return NoneType(); }
+ Optional<Value *> visitCastInst(CastInst &inst) { return &inst; }
+ Optional<Value *> visitBinaryOperator(BinaryOperator &inst) { return &inst; }
+ Optional<Value *> visitLoadInst(LoadInst &inst) { return &inst; }
+ Optional<Value *> visitSelectInst(SelectInst &inst) { return &inst; }
+ Optional<Value *> visitAllocaInst(AllocaInst &inst) { return &inst; }
+ Optional<Value *> visitPHINode(PHINode &inst) { return &inst; }
+ Optional<Value *> visitCallInst(CallInst &inst) { return &inst; }
+ Optional<Value *> visitInvokeInst(InvokeInst &inst) { return &inst; }
+ Optional<Value *> visitShuffleVectorInst(ShuffleVectorInst &inst) {
+ return &inst;
+ }
...

Just provide a default using visitInstruction only override the special cases.

+ edges. True if we could, false if we couldn't. If you hand this function an
+ instruction it didn't expect, we break. Yay. (For more information on what it
+// expects/how to add instruction support, see GetEdgesVisitor)

Make sure you handle all instructions, obviously, then remove the latter part of this comment.

+===----------------------------------------------------------------------===
+ Definitions of static functions declared at the top/middle of the file
+===----------------------------------------------------------------------===//

This comment is unnecessary.

+// TODO: Make this look at virtual calls, etc.

Exactly what do you have in mind?

+ bool isExcitingTerminator =
+ isa<InvokeInst>(inst) || isa<LandingPadInst>(inst);

Exciting! Just fold this into the return conditional.

+static bool isAliasingExternal(Value *val) {
+ bool isGlobal = isa<GlobalValue>(val);
+ auto *arg = dyn_cast<Argument>(val);
+ bool isAliasArg = arg != nullptr && !arg->hasNoAliasAttr();
+ return isGlobal || isAliasArg;
+}

You're missing handling for byval arguments. Look at isIdentifiedObject and friends in AliasAnalysis.cpp

+ Aside: We may remove graph construction entirely, because it doesn't really
+ buy us much that we don't already have. I'd like to add interprocedural

Can you please be more specific about what it does or does not buy us?

+ if (!maybeFnA.hasValue() && !maybeFnB.hasValue()) {
+ llvm_unreachable("Can't find Funcation A or Function B");
+ }

Funcation -> Function; also be more specific, how about "Don't know how to extract the parent function from this value".

+ // Ensure we're looking at the same function for both variables.
+ assert(!maybeFnB.hasValue() || *maybeFnB == *maybeFnA);

() && "Interprocedural queries not supported"

+ if (!maybeA.hasValue()) {
+ return NoneType();
+ }
+
+ auto maybeB = sets.find(valB);
+ if (!maybeB.hasValue()) {
+ return NoneType();
+ }

I see no reason to use Optional here. Just return MayAlias.

Thanks again,
Hal

• Original Message -----

From: "George Burgess IV" <[e-mail]>
To: [e-mail], [e-mail], [e-mail], [e-mail], [e-mail]
Cc: [e-mail]
Sent: Friday, July 25, 2014 3:14:14 PM
Subject: Re: [PATCH] LLVM CFL Alias Analysis -- Algorithm

+hfinkel

Addressed Danny's comments, fixed a bug where we wouldn't properly
handle exceptions, (i.e. in try {} catch (Foo& f) {}, f would be
ignored, when it really needs to be treated like an aliasing
external.) and added an extra field to Edge so interprocedural is
easier to integrate.

http://reviews.llvm.org/D4551

Files:

include/llvm/Analysis/Passes.h
include/llvm/InitializePasses.h
include/llvm/LinkAllPasses.h
lib/Analysis/CFLAliasAnalysis.cpp
lib/Analysis/CMakeLists.txt

[sanjoy]

Few comments inline.

lib/Analysis/CFLAliasAnalysis.cpp

49

This might be better named as parentFunctionOfValue. valueToFunction sounds a lot like it just does dyn_cast<Function>(va).

57

Can this use the CallSite class?

304

It may be possible to use CallSite here too.

340

Are you sure this is correct? In the comment on enum class EdgeWeight you have:

// The edge used when our edge goes from a value to a handle that may have
// contained it at some point. Examples:
// %b = load %a              (%a Reference %b)
// %b = extractelement %a, 0 (%a Reference %b)
Reference

but here

Optional<bool> visitExtractElementInst(ExtractElementInst &inst) {
  // inst :: %b = extractelementinst %a, 0
  auto *ptr = inst.getVectorOperand();   // ptr = %a
  auto *val = &inst;   // val = %b
  // new edge = (val -> ptr, Reference) => (%b Reference %a)
  output->push_back({val, ptr, EdgeWeight::Reference, false});
  return true;
}

I may be totally missing something though, so please feel free to assert the correctness of this function without a specific reason -- I'll rebuild my understand then. :)

[• gbiv]

Thanks to everyone who's reviewed this so far. :)

Addressing comments:
hfinkel:
I'm aware that some of the code examples are sketchy, but they are "valid" C++ that turns into "valid" LLVM IR. So we technically need to support it.

Do we actually need edges for all binary operators, or only those that could be part of pointer arithmetic? Meaning, can we exclude the floating-point operators, for example?

Can floats not be a part of pointer arithmetic with -fno-strict-aliasing on?
int* a = new int;
int* b = (int*)((float)a + 1.0);

Does it matter if you add duplicate edges here? A funny property of LLVM phis is that they can have duplicate entries for the same predecessor block so long as the values also match.

Duplicate edges cause a little bit more memory and a few more CPU cycles to be taken during set construction. After the StratifiedSets are constructed, it makes no difference if we have one or ten of the same edge.

What does this check have to do with IPA? If this property is true, then it is true regardless of whether the function is local or not. This is how it is defined (it is definitional, not speculative).

Good catch -- that method was more of a stub than anything; I renamed it, but keep in mind that part of IPA is ridding ourselves of it.

Do you need this for calls returning void?

Yes. It unifies all of the arguments into one set for us, which is useful with e.g. std::swap(T&, T&);

Many vector shuffles have an Undef second operand, I assume you don't need an edge for those. On that thought, you should probably filter out edges from undef everywhere.

AFAIK, Undef isa<Constant> && !isAliasingExternal, so they're filtered out for free in buildSetsFrom. :)

Exactly what do you have in mind?

Updated TODO to be more descriptive; for indirect calls, we may be able to figure out all possible targets of the call, and just try IPA on all of them.

Exciting!

I think so too.

You're missing handling for byval arguments. Look at isIdentifiedObject and friends in AliasAnalysis.cpp

Will add in next rev

Can you please be more specific about what it does or does not buy us?

AFAICT, graph construction at the moment just replicates the use graph we already get for free from Value*, and tags each edge with an extra attribute or two. Theoretically, it shouldn't be *too* hard to remove the graph and calculate Weights/AliasingExternals on the fly, which would save us the time+memory of building the graph.

sanjoy:

Can this use the CallSite class?

I might have missed something, but I don't see what the CallSite class would really buy us here -- the goal of that method is to grab us one or more (in the case of a call through a function pointer, or similar) of the functions that can be called for a given CallInst/InvokeInst. All I can see for CallSite is the same functionality that we get from Inst->getCalledFunction().

Are you sure this is correct

Excellent catch! :) The docs on EdgeWeight were flipped -- my mistake.

[• dberlin]

I don't have any additional comments on this one, so again, you should
wait for hal (or someone else) to give you a final okay so you can be
sure everyone's issues have been addressed.

[• gbiv]

+Personal account (internship ends on Friday)

Added some interprocedural analysis into the algorithm, changed from StratifiedSets<Value*> to FunctionInfo everywhere, and added support for StratifiedAttrs.

[Jiangning]

Hi George,

Will this new design supporting "strict aliasing" finally?

Kevin posted this http://comments.gmane.org/gmane.comp.compilers.llvm.devel/75298.

For that case, if we use "gcc -fno-strict-aliasing -O2", the case behaves correctly. But by default gcc is enabling -strict-aliasing.

Any thoughts?

Thanks,
-Jiangning

[• gbiv]

Hi! Thanks for your comments :)

Kevin posted this http://comments.gmane.org/gmane.comp.compilers.llvm.devel/75298.

AFAICT, that's not a valid C program. The C89 standard section 3.1.2.6 says "All declarations that refer to the same object or function shall have compatible type; otherwise the behavior is undefined." In this case, the types int and struct heap are not compatible. So, undefined behavior results. For more on type compatibility in C89, see section 3.1.2.6 of the standard. Compiling the executable with -fno-strict-aliasing -O2 on gcc 4.8.2 & clang 3.4.1, it seems that they both produce *very* similar assembly. In terms of pure instruction count, clang actually "wins" by a single instruction.

Will this new design supporting "strict aliasing" finally?

This AA algorithm entirely ignores types at the moment. That being said, if we have an API that allows us to extract C/C++ types from LLVM IR, I don't see adding type sensitivity being a necessarily difficult task. (If you're only looking for a pass that deals with types, then you may find that the TypeBasedAliasAnalysis pass interesting.)

Thanks again,
George

[Jiangning]

Hi George,

Thanks for your answer!

I'm asking this question, because the feature -strict-aliasing can improve
benchmark performance a lot. And even one of spec2000 benchmarks, I can see
~6% performance improvement.

I simplified one of the cases as below,

{code}
$ cat alias.c
typedef struct {int x; int y;} S;
S **ps;
int i;
main()
{

do {
  ps[i]->x = i;
  i++;
} while (i);

}
$ ~/llvm/build/bin/clang --target=aarch64-linux-gnuabi alias.c -S -O2
alias.c:4:1: warning: type specifier missing, defaults to 'int'
[-Wimplicit-int]
main()
^
1 warning generated.
$ cat alias.s
.text
.file "alias.c"
.globl main
.align 2
.type main,@function
main: @main
BB#0: %entry
adrp x9, ps
adrp x8, i
ldr x9, [x9, :lo12:ps]
ldr w10, [x8, :lo12:i]
.LBB0_1: %do.body

// =>This Inner Loop Header: Depth=1

ldr x11, [x9, w10, sxtw #3]
str w10, [x11]

• ldr w10, [x8, :lo12:i] // inside the loop*

add w10, w10, #1 // =1

• str w10, [x8, :lo12:i] // inside the loop *

cbnz w10, .LBB0_1
BB#2: %do.end
mov w0, wzr
ret
.Ltmp1:
.size main, .Ltmp1-main

.type i,@object @i
.comm i,4,4
.type ps,@object @ps
.comm ps,8,8

.ident "clang version 3.6.0 "
$ aarch64-linux-gnu-gcc alias.c -S -O2
$ cat alias.s
.cpu generic
.file "alias.c"
.section .text.startup,"ax",%progbits
.align 2
.global main
.type main, %function
main:
adrp x4, i
adrp x1, ps

• ldr w0, [x4,#:lo12:i] // hoisted out loop*

ldr x1, [x1,#:lo12:ps]
add x1, x1, x0, sxtw 3
b .L3
.L5:
mov w0, w2
.L3:
ldr x3, [x1],8
adds w2, w0, 1
str w0, [x3]
bne .L5
*str w2, [x4,#:lo12:i] // sink out of loop*
ret
.size main, .-main
.comm i,4,4
.comm ps,8,8
.ident "GCC: (Ubuntu/Linaro 4.8.1-10ubuntu7) 4.8.1"
{code}

So for this case, gcc can hoist/sink load/store out of loop, but llvm can't.

Is the goal of your new design to replace the current "BasicAA+TBAA"?

Sorry for my off topic discussion, but I want to understand what is going
to happen around this. Our stakeholders really want performance improvement.

Based on your last reply, my understanding is we should improve TBAA, but
will it still work together with your new design? Should we pay effort on
current TBAA pass to solve the problem?

Thanks,
-Jiangning

2014-08-08 2:40 GMT+08:00 George Burgess IV <[e-mail]>:

Hi! Thanks for your comments :)

Kevin posted this

http://comments.gmane.org/gmane.comp.compilers.llvm.devel/75298.
AFAICT, that's not a valid C program. The C89 standard section 3.1.2.6
says "All declarations that refer to the same object or function shall have
compatible type; otherwise the behavior is undefined." In this case, the
types int and struct heap are not compatible. So, undefined behavior
results. For more on type compatibility in C89, see section 3.1.2.6 of the
standard. Compiling the executable with -fno-strict-aliasing -O2 on gcc
4.8.2 & clang 3.4.1, it seems that they both produce *very* similar
assembly. In terms of pure instruction count, clang actually "wins" by a
single instruction.

Will this new design supporting "strict aliasing" finally?

This AA algorithm entirely ignores types at the moment. That being said,
if we have an API that allows us to extract C/C++ types from LLVM IR, I
don't see adding type sensitivity being a necessarily difficult task. (If
you're only looking for a pass that deals with types, then you may find
that the TypeBasedAliasAnalysis pass interesting.)

Thanks again,
George

http://reviews.llvm.org/D4551

[• dberlin]

Just wanted to ping this since George is on his way back to school.
I'd appreciate it if folks who made comments would confirm/deny that they
are satisfied those are addressed and are okay with this being committed.

[nlewycky]

I think this is worth landing and any bug fixes can be incremental development?

lib/Analysis/CFLAliasAnalysis.cpp

170

handles -> Handles, I think>

241–242

"disabled while trying to find a bug"? An example that explains when this comes up in production use would be better. Unless it really is a debugging feature?

280

"I < E" is usually "I != E" in llvm, though that causes no particular benefit here.

286–289

What about the index arguments? Suppose you have

inty = ptrtoint ptry
GEP (ptrx-ptry), inty

?

291–296

Only the true and false values but not the condition, eh. You wanna hear something horrible?

void foo(char *p) {
  uintptr_t x = 0;
  uintptr_t y = (uintptr_t)p;
  for (int i = 0; i < 8*sizeof(char*); ++i, x <<= 1) {
    int bit = (y>>(8*sizeof(char*)-1)) & 1;
    x += bit ? 1 : 0;  // SelectInst here.
  }
  char *q = (char*)x;
  // don't answer noalias(p, q).
}

312–314

Eh? I would've expected it's external if declaration || !hasLocalLinkage. Is this function the negative of its name?

386

Does RetVals change size inside this loop? If not, the "for (unsigned X = 0, XE = RetVals.size(); X != XE; ++X) {" formulation makes that clear.

(Oh and again at line 381 for Parameters, 415 for Arguments.)

406–407

You could also check Fn->isVarArgs() way up in the early exit detection code instead? If it's not varargs then #params = #args? Unless the call is indirect (ie., through a bitcast).

414

Typo, "extermely" -> "extremely".

738–739

auto Node = Worklist.pop_back_val()?

793

"Lengthy"?

[hfinkel]

I agree with Nick; once current comments are addressed, I think this can go in and we'll work on it from there.

lib/Analysis/CFLAliasAnalysis.cpp

11

Missing '.' after types.

63

I think this is fine, but FYI, there is another way of doing it. Instead of taking an Inst* you could take a const CallSite & (which can automatically be constructed by either). If someone else has a preference here, feel free to say so.

95

I don't like the term "weight" here -- the different weights here are really unordered edge types. Can we call this EdgeType instead?

220

I think this deserves a comment. This will catch all GlobalVariable comparisons. Maybe something like:
// Comparisons between global variables and other constants should be handled by BasicAA.

415

It feels like there should be an early-backedge in this loop for parameters that are noalias/byval somewhere.

678

Remove "all"

793

Also, what is lengthy about them? This is really the query interface.

798

It is not obvious what this assert means. Please make this:

assert(DummyPair.second && "Here is what this means");

[george.burgess.iv]

Commandeering to abandon; this went in a long time ago as part of D5106.

include/llvm/Analysis/Passes.h

 
   //===--------------------------------------------------------------------===//
   //
+  // createCFLAliasAnalysisPass - This pass implements a set-based approach to
+  // alias analysis.
+  //
+  ImmutablePass *createCFLAliasAnalysisPass();
+
+  //===--------------------------------------------------------------------===//
+  //
   /// createLibCallAliasAnalysisPass - Create an alias analysis pass that knows
   /// about the semantics of a set of libcalls specified by LCI.  The newly
   /// constructed pass takes ownership of the pointer that is provided.

include/llvm/InitializePasses.h

 void initializeCFGOnlyViewerPass(PassRegistry&);
 void initializeCFGPrinterPass(PassRegistry&);
 void initializeCFGSimplifyPassPass(PassRegistry&);
+void initializeCFLAliasAnalysisPass(PassRegistry&);
 void initializeFlattenCFGPassPass(PassRegistry&);
 void initializeStructurizeCFGPass(PassRegistry&);
 void initializeCFGViewerPass(PassRegistry&);

include/llvm/LinkAllPasses.h

       (void) llvm::createCallGraphPrinterPass();
       (void) llvm::createCallGraphViewerPass();
       (void) llvm::createCFGSimplificationPass();
+      (void) llvm::createCFLAliasAnalysisPass();
       (void) llvm::createStructurizeCFGPass();
       (void) llvm::createConstantMergePass();
       (void) llvm::createConstantPropagationPass();

lib/Analysis/CFLAliasAnalysis.cpp

+//===- CFLAliasAnalysis.cpp - CFL-Based Alias Analysis Implementation ------==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a CFL-based context-insensitive alias analysis
+// algorithm. It does not depend on types The algorithm is a mixture of the one
+// described in "Demand-driven alias analysis for C" by Xin Zheng and Radu
+// Rugina, and "Fast algorithms for Dyck-CFL-reachability with applications to
+// Alias Analysis" by Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the
+// papers, we build a graph of the uses of a variable, where each node is a
+// memory location, and each edge is an action that happened on that memory
+// location.  The "actions" can be one of Dereference, Reference, Assign, or
+// Assign.
+//
+// Two variables are considered as aliasing iff you can reach one value's node
+// from the other value's node and the language formed by concatenating all of
+// the edge labels (actions) conforms to a context-free grammar.
+//
+// Because this algorithm requires a graph search on each query, we execute the
+// algorithm outlined in "Fast algorithms..." (mentioned above)
+// in order to transform the graph into sets of variables that may alias in
+// ~nlogn time (n = number of variables.), which makes queries take constant
+// time.
+//===----------------------------------------------------------------------===//
+
+#include "StratifiedSets.h"
+#include "WeightedBidirectedGraph.h"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/None.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/InstVisitor.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <algorithm>
+#include <cassert>
+#include <forward_list>
+#include <tuple>
+
+using namespace llvm;
+
+// Try to go from a Value* to a Function*. Never returns nullptr.
+static Optional<Function *> parentFunctionOfValue(Value *);
+
+// Returns possible functions called by the Inst* into the given
+// SmallVectorImpl. Returns true if targets found, false otherwise.
+// This is templated because InvokeInst/CallInst give us the same
+// set of functions that we care about, and I don't like repeating
+// myself.
+template <typename Inst>
+static bool getPossibleTargets(Inst *, SmallVectorImpl<Function *> &);
+
+// Some instructions need to have their users tracked. Instructions like
+// `add` require you to get the users of the Instruction* itself, other
+// instructions like `store` require you to get the users of the first
+// operand. This function gets the "proper" value to track for each
+// type of instruction we support.
+static Optional<Value *> getTargetValue(Instruction *);
+
+// There are certain instructions (i.e. FenceInst, etc.) that we ignore.
+// This notes that we should ignore those.
+static bool hasUsefulEdges(Instruction *);
+
+namespace {
+// StratifiedInfo Attribute things.
+typedef unsigned StratifiedAttr;
+constexpr unsigned MaxStratifiedAttrIndex = NumStratifiedAttrs;
+constexpr unsigned AttrAllIndex = 0;
+constexpr unsigned AttrGlobalIndex = 1;
+constexpr unsigned AttrFirstArgIndex = 2;
+constexpr unsigned AttrLastArgIndex = MaxStratifiedAttrIndex;
+constexpr unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex;
+
+constexpr StratifiedAttr AttrNone = 0;
+constexpr StratifiedAttr AttrAll = ~AttrNone;
+
+// \brief StratifiedSets call for knowledge of "direction", so this is how we
+// represent that locally.
+enum class Level { Same, Above, Below };
+
+// \brief Edges can be one of four "weights" -- each weight must have an inverse
+// weight (Assign has Assign; Reference has Dereference).
+enum class EdgeWeight {
+  // The weight assigned when assigning from or to a value. For example, in:
+  // %b = getelementptr %a, 0
+  // ...The relationships are %b assign %a, and %a assign %b. This used to be
+  // two edges, but having a distinction bought us nothing.
+  Assign,
+
+  // The edge used when we have an edge going from some handle to a Value.
+  // Examples of this include:
+  // %b = load %a              (%b Dereference %a)
+  // %b = extractelement %a, 0 (%a Dereference %b)
+  Dereference,
+
+  // The edge used when our edge goes from a value to a handle that may have
+  // contained it at some point. Examples:
+  // %b = load %a              (%a Reference %b)
+  // %b = extractelement %a, 0 (%b Reference %a)
+  Reference
+};
+
+// \brief Encodes the notion of a "use"
+struct Edge {
+  // \brief Which value the edge is coming from
+  Value *From;
+
+  // \brief Which value the edge is pointing to
+  Value *To;
+
+  // \brief Edge weight
+  EdgeWeight Weight;
+
+  // \brief Whether we aliased any external values along the way that may be
+  // invisible to the analysis (i.e. landingpad for exceptions, calls for
+  // interprocedural analysis, etc.)
+  StratifiedAttrs AdditionalAttrs;
+
+  Edge(Value *From, Value *To, EdgeWeight W, StratifiedAttrs A)
+      : From(From), To(To), Weight(W), AdditionalAttrs(A) {}
+};
+
+// \brief Information we have about a function and would like to keep around
+struct FunctionInfo {
+  StratifiedSets<Value *> Sets;
+  // Lots of functions have < 4 returns. Adjust as necessary.
+  SmallVector<Value *, 4> ReturnedValues;
+};
+
+struct CFLAliasAnalysis;
+
+struct FunctionHandle : public CallbackVH {
+  FunctionHandle(Function *Fn, CFLAliasAnalysis *CFLAA)
+      : CallbackVH(Fn), CFLAA(CFLAA) {
+    assert(Fn != nullptr);
+    assert(CFLAA != nullptr);
+  }
+
+  virtual ~FunctionHandle() {}
+
+  virtual void deleted() override { removeSelfFromCache(); }
+  virtual void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
+
+private:
+  CFLAliasAnalysis *CFLAA;
+
+  void removeSelfFromCache();
+};
+
+struct CFLAliasAnalysis : public ImmutablePass, public AliasAnalysis {
+private:
+  /// \brief Cached mapping of Functions to their StratifiedSets.
+  /// If a function's sets are currently being built, it is marked
+  /// in the cache as an Optional without a value. This way, if we
+  /// have any kind of recursion, it is discernable from a function
+  /// that simply has empty sets.
+  DenseMap<Function *, Optional<FunctionInfo>> Cache;
+  std::forward_list<FunctionHandle> handles;
+
+public:
+  static char ID;
+
+  CFLAliasAnalysis() : ImmutablePass(ID) {
+    initializeCFLAliasAnalysisPass(*PassRegistry::getPassRegistry());
+  }
+
+  virtual ~CFLAliasAnalysis() {}
+
+  void getAnalysisUsage(AnalysisUsage &AU) const {
+    AliasAnalysis::getAnalysisUsage(AU);
+  }
+
+  void *getAdjustedAnalysisPointer(const void *ID) override {
+    if (ID == &AliasAnalysis::ID)
+      return (AliasAnalysis *)this;
+    return this;
+  }
+
+  /// \brief Inserts the given Function into the cache.
+  void scan(Function *Fn);
+
+  void evict(Function *Fn) { Cache.erase(Fn); }
+
+  /// \brief Ensures that the given function is available in the cache.
+  /// Returns the appropriate entry from the cache.
+  const Optional<FunctionInfo> &ensureCached(Function *Fn) {
+    auto Iter = Cache.find(Fn);
+    if (Iter == Cache.end()) {
+      scan(Fn);
+      Iter = Cache.find(Fn);
+      assert(Iter != Cache.end());
+      assert(Iter->second.hasValue());
+    }
+    return Iter->second;
+  }
+
+  AliasResult query(const Location &LocA, const Location &LocB);
+
+  AliasResult alias(const Location &LocA, const Location &LocB) override {
+    if (LocA.Ptr == LocB.Ptr) {
+      if (LocA.Size == LocB.Size) {
+        return MustAlias;
+      } else {
+        return PartialAlias;
+      }
+    }
+
+    if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr)) {
+      return MayAlias;
+    }
+
+    return query(LocA, LocB);
+  }
+
+  void initializePass() override { InitializeAliasAnalysis(this); }
+};
+
+void FunctionHandle::removeSelfFromCache() {
+  assert(CFLAA != nullptr);
+  auto *Val = getValPtr();
+  CFLAA->evict(cast<Function>(Val));
+  setValPtr(nullptr);
+}
+
+// \brief Gets the edges our graph should have, based on an Instruction*
+//
+// Return values:
+//    Nothing     - Unknown instruction. Program should die.
+//    Just(false) - Known instruction, but not supported (probably disabled
+//      while trying to find a bug). Discard results from GetEdgesVisitor.
+//    Just(true)  - Known instruction, results are valid. Continue as normal.
+class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
+  CFLAliasAnalysis &AA;
+  SmallVectorImpl<Edge> &Output;
+
+public:
+  GetEdgesVisitor(CFLAliasAnalysis &AA, SmallVectorImpl<Edge> &Output)
+      : AA(AA), Output(Output) {}
+
+  void visitInstruction(Instruction &) {
+    llvm_unreachable("Unsupported instruction encountered");
+  }
+
+  void visitCastInst(CastInst &Inst) {
+    Output.push_back({&Inst, Inst.getOperand(0), EdgeWeight::Assign, AttrNone});
+  }
+
+  void visitBinaryOperator(BinaryOperator &Inst) {
+    auto *Op1 = Inst.getOperand(0);
+    auto *Op2 = Inst.getOperand(1);
+    Output.push_back({&Inst, Op1, EdgeWeight::Assign, AttrNone});
+    Output.push_back({&Inst, Op2, EdgeWeight::Assign, AttrNone});
+  }
+
+  void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
+    auto *Ptr = Inst.getPointerOperand();
+    auto *Val = Inst.getNewValOperand();
+    Output.push_back({Ptr, Val, EdgeWeight::Dereference, AttrNone});
+  }
+
+  void visitAtomicRMWInst(AtomicRMWInst &Inst) {
+    auto *Ptr = Inst.getPointerOperand();
+    auto *Val = Inst.getValOperand();
+    Output.push_back({Ptr, Val, EdgeWeight::Dereference, AttrNone});
+  }
+
+  void visitPHINode(PHINode &Inst) {
+    for (unsigned I = 0, E = Inst.getNumIncomingValues(); I < E; ++I) {
+      Value *Val = Inst.getIncomingValue(I);
+      Output.push_back({&Inst, Val, EdgeWeight::Assign, AttrNone});
+    }
+  }
+
+  void visitGetElementPtrInst(GetElementPtrInst &Inst) {
+    Value *Op = Inst.getPointerOperand();
+    Output.push_back({&Inst, Op, EdgeWeight::Assign, AttrNone});
+  }
+
+  void visitSelectInst(SelectInst &Inst) {
+    auto *TrueVal = Inst.getTrueValue();
+    auto *FalseVal = Inst.getFalseValue();
+    Output.push_back({&Inst, TrueVal, EdgeWeight::Assign, AttrNone});
+    Output.push_back({&Inst, FalseVal, EdgeWeight::Assign, AttrNone});
+  }
+
+  void visitAllocaInst(AllocaInst &) {}
+
+  void visitLoadInst(LoadInst &Inst) {
+    auto *Ptr = Inst.getPointerOperand();
+    auto *Val = &Inst;
+    Output.push_back({Val, Ptr, EdgeWeight::Reference, AttrNone});
+  }
+
+  void visitStoreInst(StoreInst &Inst) {
+    auto *Ptr = Inst.getPointerOperand();
+    auto *Val = Inst.getValueOperand();
+    Output.push_back({Ptr, Val, EdgeWeight::Dereference, AttrNone});
+  }
+
+  static bool isFunctionExternal(Function *Fn) {
+    return !Fn->isDeclaration() && Fn->hasLocalLinkage();
+  }
+
+  // Gets whether the sets at Index1 above, below, or equal to the sets at
+  // Index2. Returns None if they are not in the same set chain.
+  static Optional<Level> getIndexRelation(const StratifiedSets<Value *> &Sets,
+                                          StratifiedIndex Index1,
+                                          StratifiedIndex Index2) {
+    if (Index1 == Index2)
+      return Level::Same;
+
+    const auto *Current = &Sets.getLink(Index1);
+    while (Current->hasBelow()) {
+      if (Current->Below == Index2)
+        return Level::Below;
+      Current = &Sets.getLink(Current->Below);
+    }
+
+    Current = &Sets.getLink(Index1);
+    while (Current->hasAbove()) {
+      if (Current->Above == Index2)
+        return Level::Above;
+      Current = &Sets.getLink(Current->Above);
+    }
+
+    return NoneType();
+  }
+
+  bool
+  tryInterproceduralAnalysis(const SmallVectorImpl<Function *> &Fns,
+                             Value *FuncValue,
+                             const iterator_range<User::op_iterator> &Args) {
+    constexpr unsigned ExpectedMaxArgs = 8;
+    constexpr unsigned MaxSupportedArgs = 50;
+    assert(Fns.size() > 0);
+
+    // I put this here to give us an upper bound on time taken by IPA. Is it
+    // really (realistically) needed? Keep in mind that we do have an n^2 algo.
+    if (std::distance(Args.begin(), Args.end()) > MaxSupportedArgs)
+      return false;
+
+    // Exit early if we'll fail anyway
+    for (auto *Fn : Fns) {
+      if (isFunctionExternal(Fn))
+        return false;
+      auto &MaybeInfo = AA.ensureCached(Fn);
+      if (!MaybeInfo.hasValue())
+        return false;
+    }
+
+    SmallVector<Value *, ExpectedMaxArgs> Arguments(Args.begin(), Args.end());
+    SmallVector<StratifiedInfo, ExpectedMaxArgs> Parameters;
+    for (auto *Fn : Fns) {
+      auto &Info = *AA.ensureCached(Fn);
+      auto &Sets = Info.Sets;
+      auto &RetVals = Info.ReturnedValues;
+
+      Parameters.clear();
+      for (auto &Param : Fn->args()) {
+        auto MaybeInfo = Sets.find(&Param);
+        // Did a new parameter somehow get added to the function/slip by?
+        if (!MaybeInfo.hasValue())
+          return false;
+        Parameters.push_back(*MaybeInfo);
+      }
+
+      // Adding an edge from argument -> return value for each parameter that
+      // may alias the return value
+      for (unsigned I = 0; I < Parameters.size(); ++I) {
+        auto &ParamInfo = Parameters[I];
+        auto &ArgVal = Arguments[I];
+        bool AddEdge = false;
+        StratifiedAttrs Externals;
+        for (unsigned X = 0; X < RetVals.size(); ++X) {
+          auto MaybeInfo = Sets.find(RetVals[X]);
+          if (!MaybeInfo.hasValue())
+            return false;
+
+          auto &RetInfo = *MaybeInfo;
+          auto RetAttrs = Sets.getLink(RetInfo.Index).Attrs;
+          auto ParamAttrs = Sets.getLink(ParamInfo.Index).Attrs;
+          auto MaybeRelation =
+              getIndexRelation(Sets, ParamInfo.Index, RetInfo.Index);
+          if (MaybeRelation.hasValue()) {
+            AddEdge = true;
+            Externals |= RetAttrs | ParamAttrs;
+          }
+        }
+        if (AddEdge)
+          Output.push_back({FuncValue, ArgVal, EdgeWeight::Assign,
+                            StratifiedAttrs().flip()});
+      }
+
+      if (Parameters.size() != Arguments.size())
+        return false;
+
+      // Adding edges between arguments for arguments that may end up aliasing
+      // each other. This is necessary for functions such as
+      // void foo(int** a, int** b) { *a = *b; }
+      // (Technically, the proper sets for this would be those below
+      // Arguments[I] and Arguments[X], but our algorithm will produce
+      // extermely similar, and equally correct, results either way)
+      for (unsigned I = 0; I < Arguments.size(); ++I) {
+        auto &MainInfo = Parameters[I];
+        auto &MainVal = Arguments[I];
+        auto &MainAttrs = Sets.getLink(MainInfo.Index).Attrs;
+        for (unsigned X = I + 1; X < Arguments.size(); ++X) {
+          auto &SubInfo = Parameters[X];
+          auto &SubVal = Arguments[X];
+          auto &SubAttrs = Sets.getLink(SubInfo.Index).Attrs;
+          auto MaybeRelation =
+              getIndexRelation(Sets, MainInfo.Index, SubInfo.Index);
+
+          if (!MaybeRelation.hasValue())
+            continue;
+
+          auto NewAttrs = SubAttrs | MainAttrs;
+          Output.push_back({MainVal, SubVal, EdgeWeight::Assign, NewAttrs});
+        }
+      }
+    }
+    return true;
+  }
+
+  template <typename InstT> void visitCallLikeInst(InstT &Inst) {
+    SmallVector<Function *, 4> Targets;
+    if (getPossibleTargets(&Inst, Targets)) {
+      if (tryInterproceduralAnalysis(Targets, &Inst, Inst.arg_operands()))
+        return;
+      // Cleanup from interprocedural analysis
+      Output.clear();
+    }
+
+    for (Value *V : Inst.arg_operands())
+      Output.push_back({&Inst, V, EdgeWeight::Assign, AttrAll});
+  }
+
+  void visitCallInst(CallInst &Inst) { visitCallLikeInst(Inst); }
+
+  void visitInvokeInst(InvokeInst &Inst) { visitCallLikeInst(Inst); }
+
+  // Because vectors/aggregates are immutable and unaddressable,
+  // there's nothing we can do to coax a value out of them, other
+  // than calling Extract{Element,Value}. We can effectively treat
+  // them as pointers to arbitrary memory locations we can store in
+  // and load from.
+  void visitExtractElementInst(ExtractElementInst &Inst) {
+    auto *Ptr = Inst.getVectorOperand();
+    auto *Val = &Inst;
+    Output.push_back({Val, Ptr, EdgeWeight::Reference, AttrNone});
+  }
+
+  void visitInsertElementInst(InsertElementInst &Inst) {
+    auto *Vec = Inst.getOperand(0);
+    auto *Val = Inst.getOperand(1);
+    Output.push_back({&Inst, Vec, EdgeWeight::Assign, AttrNone});
+    Output.push_back({&Inst, Val, EdgeWeight::Dereference, AttrNone});
+  }
+
+  void visitLandingPadInst(LandingPadInst &Inst) {
+    // Exceptions come from "nowhere", from our analysis' perspective.
+    // So we place the instruction its own group, noting that said group may
+    // alias externals
+    Output.push_back({&Inst, &Inst, EdgeWeight::Assign, AttrAll});
+  }
+
+  void visitInsertValueInst(InsertValueInst &Inst) {
+    auto *Agg = Inst.getOperand(0);
+    auto *Val = Inst.getOperand(1);
+    Output.push_back({&Inst, Agg, EdgeWeight::Assign, AttrNone});
+    Output.push_back({&Inst, Val, EdgeWeight::Dereference, AttrNone});
+  }
+
+  void visitExtractValueInst(ExtractValueInst &Inst) {
+    auto *Ptr = Inst.getAggregateOperand();
+    Output.push_back({&Inst, Ptr, EdgeWeight::Reference, AttrNone});
+  }
+
+  void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
+    auto *From1 = Inst.getOperand(0);
+    auto *From2 = Inst.getOperand(1);
+    Output.push_back({&Inst, From1, EdgeWeight::Assign, AttrNone});
+    Output.push_back({&Inst, From2, EdgeWeight::Assign, AttrNone});
+  }
+};
+
+// For a given instruction, we need to know which Value* to get the
+// users of in order to build our graph. In some cases (i.e. add),
+// we simply need the Instruction*. In other cases (i.e. store),
+// finding the users of the Instruction* is useless; we need to find
+// the users of the first operand. This handles determining which
+// value to follow for us.
+//
+// Note: we *need* to keep this in sync with GetEdgesVisitor. Add
+// something to GetEdgesVisitor, add it here -- remove something from
+// GetEdgesVisitor, remove it here.
+class GetTargetValueVisitor
+    : public InstVisitor<GetTargetValueVisitor, Value *> {
+public:
+  Value *visitInstruction(Instruction &Inst) { return &Inst; }
+
+  Value *visitStoreInst(StoreInst &Inst) { return Inst.getPointerOperand(); }
+
+  Value *visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
+    return Inst.getPointerOperand();
+  }
+
+  Value *visitAtomicRMWInst(AtomicRMWInst &Inst) {
+    return Inst.getPointerOperand();
+  }
+
+  Value *visitInsertElementInst(InsertElementInst &Inst) {
+    return Inst.getOperand(0);
+  }
+
+  Value *visitInsertValueInst(InsertValueInst &Inst) {
+    return Inst.getAggregateOperand();
+  }
+};
+
+typedef WeightedBidirectedGraph<std::pair<EdgeWeight, StratifiedAttrs>> GraphT;
+typedef DenseMap<Value *, GraphT::Node> NodeMapT;
+}
+
+// -- Setting up/registering CFLAA pass -- //
+char CFLAliasAnalysis::ID = 0;
+
+INITIALIZE_AG_PASS(CFLAliasAnalysis, AliasAnalysis, "cfl-aa",
+                   "CFL-Based AA implementation", false, true, false)
+
+ImmutablePass *llvm::createCFLAliasAnalysisPass() {
+  return new CFLAliasAnalysis();
+}
+
+//===----------------------------------------------------------------------===//
+// Function declarations that require types defined in the namespace above
+//===----------------------------------------------------------------------===//
+
+// Given an argument number, returns the appropriate Attr index to set.
+static StratifiedAttr argNumberToAttrIndex(StratifiedAttr);
+
+// Given a Value, potentially return which AttrIndex it maps to.
+static Optional<StratifiedAttr> valueToAttrIndex(Value *Val);
+
+// Gets the inverse of a given EdgeWeight.
+static EdgeWeight flipWeight(EdgeWeight);
+
+// Gets edges of the given Instruction*, writing them to the SmallVector*.
+static void argsToEdges(CFLAliasAnalysis &, Instruction *,
+                        SmallVectorImpl<Edge> &);
+
+// Gets the "Level" that one should travel in StratifiedSets
+// given an EdgeWeight.
+static Level directionOfEdgeWeight(EdgeWeight);
+
+// Builds the graph needed for constructing the StratifiedSets for the
+// given function
+static void buildGraphFrom(CFLAliasAnalysis &, Function *,
+                           SmallVectorImpl<Value *> &, NodeMapT &, GraphT &);
+
+// Builds the graph + StratifiedSets for a function.
+static FunctionInfo buildSetsFrom(CFLAliasAnalysis &, Function *);
+
+static Optional<Function *> parentFunctionOfValue(Value *Val) {
+  if (auto *Inst = dyn_cast<Instruction>(Val)) {
+    auto *Bb = Inst->getParent();
+    return Bb->getParent();
+  }
+
+  if (auto *Arg = dyn_cast<Argument>(Val))
+    return Arg->getParent();
+  return NoneType();
+}
+
+template <typename Inst>
+static bool getPossibleTargets(Inst *Call,
+                               SmallVectorImpl<Function *> &Output) {
+  if (auto *Fn = Call->getCalledFunction()) {
+    Output.push_back(Fn);
+    return true;
+  }
+
+  // TODO: If the call is indirect, we might be able to enumerate all potential
+  // targets of the call and return them, rather than just failing.
+  return false;
+}
+
+static Optional<Value *> getTargetValue(Instruction *Inst) {
+  GetTargetValueVisitor V;
+  return V.visit(Inst);
+}
+
+static bool hasUsefulEdges(Instruction *Inst) {
+  bool IsNonInvokeTerminator =
+      isa<TerminatorInst>(Inst) && !isa<InvokeInst>(Inst);
+  return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) && !IsNonInvokeTerminator;
+}
+
+static Optional<StratifiedAttr> valueToAttrIndex(Value *Val) {
+  if (isa<GlobalValue>(Val))
+    return AttrGlobalIndex;
+
+  if (auto *Arg = dyn_cast<Argument>(Val))
+    if (!Arg->hasNoAliasAttr())
+      return argNumberToAttrIndex(Arg->getArgNo());
+  return NoneType();
+}
+
+static StratifiedAttr argNumberToAttrIndex(unsigned ArgNum) {
+  if (ArgNum > AttrMaxNumArgs)
+    return AttrAllIndex;
+  return ArgNum + AttrFirstArgIndex;
+}
+
+static EdgeWeight flipWeight(EdgeWeight Initial) {
+  switch (Initial) {
+  case EdgeWeight::Assign:
+    return EdgeWeight::Assign;
+  case EdgeWeight::Dereference:
+    return EdgeWeight::Reference;
+  case EdgeWeight::Reference:
+    return EdgeWeight::Dereference;
+  }
+  llvm_unreachable("Incomplete coverage of EdgeWeight enum");
+}
+
+static void argsToEdges(CFLAliasAnalysis &Analysis, Instruction *Inst,
+                        SmallVectorImpl<Edge> &Output) {
+  GetEdgesVisitor v(Analysis, Output);
+  v.visit(Inst);
+}
+
+static Level directionOfEdgeWeight(EdgeWeight Weight) {
+  switch (Weight) {
+  case EdgeWeight::Reference:
+    return Level::Above;
+  case EdgeWeight::Dereference:
+    return Level::Below;
+  case EdgeWeight::Assign:
+    return Level::Same;
+  }
+  llvm_unreachable("Incomplete switch coverage");
+}
+
+// Aside: We may remove graph construction entirely, because it doesn't really
+// buy us much that we don't already have. I'd like to add interprocedural
+// analysis prior to this however, in case that somehow requires the graph
+// produced by this for efficient execution
+static void buildGraphFrom(CFLAliasAnalysis &Analysis, Function *Fn,
+                           SmallVectorImpl<Value *> &ReturnedValues,
+                           NodeMapT &Map, GraphT &Graph) {
+  const auto findOrInsertNode = [&Map, &Graph](Value *Val) {
+    auto Pair = Map.insert(std::make_pair(Val, GraphT::Node()));
+    auto &Iter = Pair.first;
+    if (Pair.second) {
+      auto NewNode = Graph.addNode();
+      Iter->second = NewNode;
+    }
+    return Iter->second;
+  };
+
+  SmallVector<Edge, 8> Edges;
+  for (auto &Bb : Fn->getBasicBlockList()) {
+    for (auto &Inst : Bb.getInstList()) {
+      // We don't want the edges of most "return" instructions, but we *do* want
+      // to know what all can be returned.
+      if (auto *Ret = dyn_cast<ReturnInst>(&Inst))
+        ReturnedValues.push_back(Ret);
+
+      if (!hasUsefulEdges(&Inst))
+        continue;
+
+      Edges.clear();
+      argsToEdges(Analysis, &Inst, Edges);
+
+      // In the case of an unused alloca (or similar), edges may be empty. Note
+      // that it exists so we can potentially answer NoAlias.
+      if (Edges.empty()) {
+        auto MaybeVal = getTargetValue(&Inst);
+        assert(MaybeVal.hasValue());
+        auto *Target = *MaybeVal;
+        findOrInsertNode(Target);
+        continue;
+      }
+
+      for (const Edge &E : Edges) {
+        auto To = findOrInsertNode(E.To);
+        auto From = findOrInsertNode(E.From);
+        auto FlippedWeight = flipWeight(E.Weight);
+        auto Attrs = E.AdditionalAttrs;
+        Graph.addEdge(From, To, {E.Weight, Attrs}, {FlippedWeight, Attrs});
+      }
+    }
+  }
+}
+
+static FunctionInfo buildSetsFrom(CFLAliasAnalysis &Analysis, Function *Fn) {
+  NodeMapT Map;
+  GraphT Graph;
+  SmallVector<Value *, 4> ReturnedValues;
+
+  buildGraphFrom(Analysis, Fn, ReturnedValues, Map, Graph);
+
+  DenseMap<GraphT::Node, Value *> NodeValueMap;
+  NodeValueMap.resize(Map.size());
+  for (const auto &Pair : Map)
+    NodeValueMap.insert({Pair.second, Pair.first});
+
+  const auto findValueOrDie = [&NodeValueMap](GraphT::Node Node) {
+    auto ValIter = NodeValueMap.find(Node);
+    assert(ValIter != NodeValueMap.end());
+    return ValIter->second;
+  };
+
+  StratifiedSetsBuilder<Value *> Builder;
+
+  SmallVector<GraphT::Node, 16> Worklist;
+  for (auto &Pair : Map) {
+    Worklist.clear();
+
+    auto *Value = Pair.first;
+    Builder.add(Value);
+    auto InitialNode = Pair.second;
+    Worklist.push_back(InitialNode);
+    while (!Worklist.empty()) {
+      auto Node = Worklist.back();
+      Worklist.pop_back();
+
+      auto *CurValue = findValueOrDie(Node);
+      if (isa<Constant>(CurValue) && !isa<GlobalValue>(CurValue))
+        continue;
+
+      for (const auto &EdgeTuple : Graph.edgesFor(Node)) {
+        auto Weight = std::get<0>(EdgeTuple);
+        auto Label = Weight.first;
+        auto &OtherNode = std::get<1>(EdgeTuple);
+        auto *OtherValue = findValueOrDie(OtherNode);
+
+        if (isa<Constant>(OtherValue) && !isa<GlobalValue>(OtherValue))
+          continue;
+
+        bool Added;
+        switch (directionOfEdgeWeight(Label)) {
+        case Level::Above:
+          Added = Builder.addAbove(CurValue, OtherValue);
+          break;
+        case Level::Below:
+          Added = Builder.addBelow(CurValue, OtherValue);
+          break;
+        case Level::Same:
+          Added = Builder.addWith(CurValue, OtherValue);
+          break;
+        }
+
+        if (Added) {
+          auto Aliasing = Weight.second;
+          if (auto MaybeCurIndex = valueToAttrIndex(CurValue))
+            Aliasing.set(*MaybeCurIndex);
+          if (auto MaybeOtherIndex = valueToAttrIndex(OtherValue))
+            Aliasing.set(*MaybeOtherIndex);
+          Builder.noteAttributes(CurValue, Aliasing);
+          Builder.noteAttributes(OtherValue, Aliasing);
+          Worklist.push_back(OtherNode);
+        }
+      }
+    }
+  }
+
+  // There are times when we end up with parameters not in our graph (i.e. if
+  // it's only used as the condition of a branch). Other bits of code depend on
+  // things that were present during construction being present in the graph.
+  // So, we add all present arguments here.
+  for (auto &Arg : Fn->args()) {
+    Builder.add(&Arg);
+  }
+
+  return {Builder.build(), std::move(ReturnedValues)};
+}
+
+//===----------------------------------------------------------------------===//
+// Lengthy CFL AA methods
+//===----------------------------------------------------------------------===//
+void CFLAliasAnalysis::scan(Function *Fn) {
+  auto DummyPair = Cache.insert({Fn, Optional<FunctionInfo>()});
+  (void)DummyPair;
+  assert(DummyPair.second);
+
+  FunctionInfo Info(buildSetsFrom(*this, Fn));
+  Cache[Fn] = std::move(Info);
+  handles.push_front(FunctionHandle(Fn, this));
+}
+
+AliasAnalysis::AliasResult
+CFLAliasAnalysis::query(const AliasAnalysis::Location &LocA,
+                        const AliasAnalysis::Location &LocB) {
+  auto *ValA = const_cast<Value *>(LocA.Ptr);
+  auto *ValB = const_cast<Value *>(LocB.Ptr);
+
+  Function *Fn = nullptr;
+  auto MaybeFnA = parentFunctionOfValue(ValA);
+  auto MaybeFnB = parentFunctionOfValue(ValB);
+  if (!MaybeFnA.hasValue() && !MaybeFnB.hasValue()) {
+    llvm_unreachable("Don't know how to extract the parent function "
+                     "from values A or B");
+  }
+
+  if (MaybeFnA.hasValue()) {
+    Fn = *MaybeFnA;
+    assert((!MaybeFnB.hasValue() || *MaybeFnB == *MaybeFnA) &&
+           "Interprocedural queries not supported");
+  } else {
+    Fn = *MaybeFnB;
+  }
+
+  assert(Fn != nullptr);
+  auto &MaybeInfo = ensureCached(Fn);
+  assert(MaybeInfo.hasValue());
+
+  auto &Sets = MaybeInfo->Sets;
+  auto MaybeA = Sets.find(ValA);
+  if (!MaybeA.hasValue())
+    return AliasAnalysis::MayAlias;
+
+  auto MaybeB = Sets.find(ValB);
+  if (!MaybeB.hasValue())
+    return AliasAnalysis::MayAlias;
+
+  auto SetA = *MaybeA;
+  auto SetB = *MaybeB;
+
+  if (SetA.Index == SetB.Index)
+    return AliasAnalysis::PartialAlias;
+
+  auto AttrsA = Sets.getLink(SetA.Index).Attrs;
+  auto AttrsB = Sets.getLink(SetB.Index).Attrs;
+  auto CombinedAttrs = AttrsA | AttrsB;
+  if (CombinedAttrs.any())
+    return AliasAnalysis::PartialAlias;
+
+  return AliasAnalysis::NoAlias;
+}

lib/Analysis/CMakeLists.txt

   BranchProbabilityInfo.cpp
   CFG.cpp
   CFGPrinter.cpp
+  CFLAliasAnalysis.cpp
   CGSCCPassManager.cpp
   CaptureTracking.cpp
   CostModel.cpp