[Attributor] Track AA dependency using dependency graph

[bbn]

Summary

This patch added dependency graph to the attributor so that we can dump the dependencies between AAs more easily. We can also apply general graph algorithms to the graph, making it easier for us to create deep wrappers.

[jdoerfert]

Thanks for working on this. I added a first set of comments below. We'll have to rebase this once the changes to reduce memory usage are all in. We will also need to verify this does not regress memory usage too much. Finally, right now this patch needs two command line options to dump and view the dependence graph. That will also allow tests. I guess we should have a printer for the AbstractAttributes so that we print the context instruction, if present, and the underlying value, the kind and state.

llvm/include/llvm/Transforms/IPO/Attributor.h

172

You have declared DepAAVector above, maybe rename it to DepAAVectorTy and use it here. Also use a SmallVector. The pair should probably be a PointerIntPair instead. The public are not needed. You might want a private for the members.

212

Use DenseMap instead of std::map.

Do we really need to add all edges from the synthetic root into a map? We can just pretend we did, right? Maybe the graph can take a const vector& containing all abstract attributes and the root node just iterates those as children. I want to avoid the memory overhead here.

llvm/lib/Transforms/IPO/Attributor.cpp

2133

This is not a call graph.

[lebedev.ri]

In D78861#2013150, @jdoerfert wrote:

Thanks for working on this. I added a first set of comments below. We'll have to rebase this once the changes to reduce memory usage are all in. We will also need to verify this does not regress memory usage too much.

I'd like to note that unless i'm mistaken right now all this graph stuff is not actually being used for attributes, but only for printing the graph of attribute dependency.
Is there a plan to actually use the graph? If not, then the graph shouldn't be built unless there was a request to output it, i think.

Finally, right now this patch needs two command line options to dump and view the dependence graph. That will also allow tests. I guess we should have a printer for the AbstractAttributes so that we print the context instruction, if present, and the underlying value, the kind and state.

[bbn]

Is there a plan to actually use the graph? If not, then the graph shouldn't be built unless there was a request to output it, i think.

Yes, our goal is to create deep wrappers for non-exact defined functions (D63312, D63319, D76404), and if an abstract attribute depends on another non-exact definition, we are going to create deep wrappers instead of shallow wrappers. We are going to use dependency graph to track such dependencies.

[kuter]

Hi, what is the state of this ?
As of D78729 a AbstractAttribute keeps track of its own dependencies.

It is possible to implement GraphTraits without using any extra memory by
directly implementing it on the Attributor and having the NodeRef as AbstractAttribute.

I suggest that we make AADepGraph a empty (for now) wrapper that takes in a Attributor reference and implement GraphTraits on it.

[jdoerfert]

In D78861#2066299, @kuter wrote:

Hi, what is the state of this ?
As of D78729 a AbstractAttribute keeps track of its own dependencies.

It is possible to implement GraphTraits without using any extra memory by
directly implementing it on the Attributor and having the NodeRef as AbstractAttribute.

I suggest that we make AADepGraph a empty (for now) wrapper that takes in a Attributor reference and implement GraphTraits on it.

Without thinking about this too much, I think this is reasonable. If it turns out we sometimes need a "richer" representation, we can allocate extra memory in the graph too, e.g., if the user asked for visualization of some special properties. For the start I, a thin overlay would be perfect.

[bbn]

In D78861#2066299, @kuter wrote:

Hi, what is the state of this ?

Hi, I have just started my work on this.

As of D78729 a AbstractAttribute keeps track of its own dependencies.

It is possible to implement GraphTraits without using any extra memory by
directly implementing it on the Attributor and having the NodeRef as AbstractAttribute.

I suggest that we make AADepGraph a empty (for now) wrapper that takes in a Attributor reference and implement GraphTraits on it.

Thanks for the suggestion! This would make the graph lighter without any functionality loss, I will try to construct the graph in this way.

[bbn]

• Use AbstractAttribute directly as the dependency graph node
• Added opt options to dump and print the dependency graph

before the patch:

allocations:          	84727
leaked allocations:   	26
temporary allocations:	3916

bytes allocated in total (ignoring deallocations): 24.15MB (4.72MB/s)
calls to allocation functions: 84727 (16574/s)
temporary memory allocations: 4003 (783/s)
peak heap memory consumption: 6.29MB
peak RSS (including heaptrack overhead): 610.83MB
total memory leaked: 163.25K

after:

allocations:          	85031
leaked allocations:   	327
temporary allocations:	3916

bytes allocated in total (ignoring deallocations): 24.16MB (4.80MB/s)
calls to allocation functions: 85031 (16904/s)
temporary memory allocations: 4003 (795/s)
peak heap memory consumption: 6.30MB
peak RSS (including heaptrack overhead): 610.31MB
total memory leaked: 165.66KB

[jdoerfert]

We need tests so I can see how this looks ;)

[kuter]

This does not compile for me. The compiler error that I get is about creating a GraphTraits specialization outside of the llvm namespace.
When i put the GraphTraits specializations in llvm namespace it does compile.

But when I run it I get a segfault.

Stack dump:                                                                                                                                                                                                                     
0.      Program arguments: /home/user/llvm-project/build/bin/opt -passes=attributor -attributor-dump-dep-graph noreturn.ll                                                                                                      
 #0 0x000055c1d218a7ca llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/home/user/llvm-project/build/bin/opt+0x28ef7ca)                                                                                                         
 #1 0x000055c1d2188605 llvm::sys::RunSignalHandlers() (/home/user/llvm-project/build/bin/opt+0x28ed605)                                                                                                                         
 #2 0x000055c1d2188722 SignalHandler(int) (/home/user/llvm-project/build/bin/opt+0x28ed722)                                                                                                                                     
 #3 0x00007f3f634f90e0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x110e0)                                                                                                                                             
 #4 0x000055c1d1b138a5 llvm::IRPosition::getArgNo() const (/home/user/llvm-project/build/bin/opt+0x22788a5)                                                                                                                     
 #5 0x000055c1d1b1483e llvm::IRPosition::getAssociatedValue() const (/home/user/llvm-project/build/bin/opt+0x227983e)                                                                                                           
 #6 0x000055c1d1b1494c llvm::operator<<(llvm::raw_ostream&, llvm::IRPosition const&) (/home/user/llvm-project/build/bin/opt+0x227994c)                                                                                          
 #7 0x000055c1d1b14a7d llvm::AbstractAttribute::print(llvm::raw_ostream&) const (/home/user/llvm-project/build/bin/opt+0x2279a7d)                                                                                               
 #8 0x000055c1d1b15cd5 llvm::GraphWriter<llvm::AADepGraph*>::writeNode(llvm::AbstractAttribute*) (/home/user/llvm-project/build/bin/opt+0x227acd5)                                                                              
 #9 0x000055c1d1b16237 llvm::raw_ostream& llvm::WriteGraph<llvm::AADepGraph*>(llvm::raw_ostream&, llvm::AADepGraph* const&, bool, llvm::Twine const&) (/home/user/llvm-project/build/bin/opt+0x227b237)                         
#10 0x000055c1d1b2555f llvm::AADepGraph::dumpGraph() (/home/user/llvm-project/build/bin/opt+0x228a55f)                                                                                                                          
#11 0x000055c1d1b26326 runAttributorOnFunctions(llvm::InformationCache&, llvm::SetVector<llvm::Function*, std::vector<llvm::Function*, std::allocator<llvm::Function*> >, llvm::DenseSet<llvm::Function*, llvm::DenseMapInfo<llv
m::Function*> > >&, llvm::AnalysisGetter&, llvm::CallGraphUpdater&) (.isra.730) (/home/user/llvm-project/build/bin/opt+0x228b326)                                                                                               
#12 0x000055c1d1b26745 llvm::AttributorPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/user/llvm-project/build/bin/opt+0x228b745)                                                                         
#13 0x000055c1d23adf7d llvm::detail::PassModel<llvm::Module, llvm::AttributorPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/user/llvm-pro
ject/build/bin/opt+0x2b12f7d)                                                                                                                                                                                                   
#14 0x000055c1d1a9bd3f llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/user/llvm-project/build/bin/opt+0x2200d3f)                        
#15 0x000055c1d016ea68 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::opt_tool::OutputKind, llvm::opt_t
ool::VerifierKind, bool, bool, bool, bool, bool, bool) (/home/user/llvm-project/build/bin/opt+0x8d3a68)                                                                                                                         
#16 0x000055c1d00befe8 main (/home/user/llvm-project/build/bin/opt+0x823fe8)                                                                                                                                                    
#17 0x00007f3f622962e1 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e1)                                                                                                                                              
#18 0x000055c1d0163d2a _start (/home/user/llvm-project/build/bin/opt+0x8c8d2a)                                                                                                                                                  
Segmentation fault

[bbn]

In D78861#2081311, @kuter wrote:

This does not compile for me. The compiler error that I get is about creating a GraphTraits specialization outside of the llvm namespace.
When i put the GraphTraits in llvm namespace it does compile.

What do you mean by "put the GraphTraits in llvm namespace"?

But when I run it I get a segfault.

Yes, I also got this segfault when running this on assign.ll. I think this issue is related to the AbstractAttribute::print() function and is not caused by the
dependency graph. I am currently looking into this and I will write a new print function for AA.

[kuter]

In D78861#2081311, @kuter wrote:

This does not compile for me. The compiler error that I get is about creating a GraphTraits specialization outside of the llvm namespace.
When i put the GraphTraits specializations in llvm namespace it does compile.

But when I run it I get a segfault.

In D78861#2081341, @bbn wrote:

In D78861#2081311, @kuter wrote:

This does not compile for me. The compiler error that I get is about creating a GraphTraits specialization outside of the llvm namespace.
When i put the GraphTraits in llvm namespace it does compile.

What do you mean by "put the GraphTraits in llvm namespace"?

But when I run it I get a segfault.

Yes, I also got this segfault when running this on assign.ll. I think this issue is related to the AbstractAttribute::print() function and is not caused by the
dependency graph. I am currently looking into this and I will write a new print function for AA.

Hi I found out why. Your are dumping attributes after IR cleanup. IR Cleanup deletes the IR values that are no longer needed.
But they are still referenced by the Attributes.

if you look at D81022, which will be merged soon.
The dump should happen after ::runTillFixpoint().

[bbn]

Hi I found out why. Your are dumping attributes after IR cleanup. IR Cleanup deletes the IR values that are no longer needed.
But they are still referenced by the Attributes.

if you look at D81022, which will be merged soon.
The dump should happen after `::runTillFixpoint().

Thanks for the help! I will rebase my patch after this patch is merged.

[kuter]

What do you mean by "put the GraphTraits in llvm namespace"?

If I do not put your graph traits declarations inside namespace llvm {
the error that I get is:

FAILED: lib/Transforms/IPO/CMakeFiles/LLVMipo.dir/Attributor.cpp.o
/usr/bin/c++   -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib/Transforms/IPO -I/home/user/llvm-project/llvm/lib/Transforms/IPO -Iinclude -I/home/user/llv
m-project/llvm/include -fPIC -fvisibility-inlines-hidden -Werror=date-time -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wno-missing-field-initializers -pedantic -Wno-long-long -Wno-maybe-uninitialized -Wd
elete-non-virtual-dtor -Wno-comment -fdiagnostics-color -ffunction-sections -fdata-sections -O3     -fno-exceptions -fno-rtti -UNDEBUG -std=c++14 -MD -MT lib/Transforms/IPO/CMakeFiles/LLVMipo.dir/Attributor.cpp.o -MF lib/Tra
nsforms/IPO/CMakeFiles/LLVMipo.dir/Attributor.cpp.o.d -o lib/Transforms/IPO/CMakeFiles/LLVMipo.dir/Attributor.cpp.o -c /home/user/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp
/home/user/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp:2122:26: error: specialization of ‘template<class GraphType> struct llvm::GraphTraits’ in different namespace [-fpermissive]
 template <> struct llvm::GraphTraits<AbstractAttribute *> {
                          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/user/llvm-project/llvm/include/llvm/Transforms/IPO/Attributor.h:100:0,
                 from /home/user/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp:16:
/home/user/llvm-project/llvm/include/llvm/ADT/GraphTraits.h:35:8: error:   from definition of ‘template<class GraphType> struct llvm::GraphTraits’ [-fpermissive]
 struct GraphTraits {
        ^~~~~~~~~~~
/home/user/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp:2152:14: error: specialization of ‘template<class GraphType> struct llvm::GraphTraits’ in different namespace [-fpermissive]
 struct llvm::GraphTraits<AADepGraph *>
              ^~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/user/llvm-project/llvm/include/llvm/Transforms/IPO/Attributor.h:100:0,
                 from /home/user/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp:16:
/home/user/llvm-project/llvm/include/llvm/ADT/GraphTraits.h:35:8: error:   from definition of ‘template<class GraphType> struct llvm::GraphTraits’ [-fpermissive]
 struct GraphTraits {
        ^~~~~~~~~~~
/home/user/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp:2164:14: error: specialization of ‘template<class Ty> struct llvm::DOTGraphTraits’ in different namespace [-fpermissive]
 struct llvm::DOTGraphTraits<AADepGraph *> : public DefaultDOTGraphTraits {
              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /home/user/llvm-project/llvm/include/llvm/Transforms/IPO/Attributor.h:121:0,
                 from /home/user/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp:16:
/home/user/llvm-project/llvm/include/llvm/Support/DOTGraphTraits.h:160:8: error:   from definition of ‘template<class Ty> struct llvm::DOTGraphTraits’ [-fpermissive]
 struct DOTGraphTraits : public DefaultDOTGraphTraits {

[bbn]

• Added new printer function for abstract attribute
• Added getName() function to each abstract attribute which simply gets the name of the AA.
• Added print() function for dependency graph.
  
  The AADepMap::print() function iterates through the AllAbstractAttributes set in the attributor and prints out the dependencies for each AA. To test the correctness of the dependency graph, we need to find a way to iterate through all nodes in the dependency graph instead of the AllAbstractAttribute set

• Added initial test case

Benchmark

• Before the patch

total runtime: 4.56s.
bytes allocated in total (ignoring deallocations): 24.15MB (5.29MB/s)
calls to allocation functions: 84730 (18564/s)
temporary memory allocations: 4003 (877/s)
peak heap memory consumption: 6.30MB
peak RSS (including heaptrack overhead): 609.44MB
total memory leaked: 163.25KB

• After the patch

total runtime: 4.57s.
bytes allocated in total (ignoring deallocations): 24.16MB (5.28MB/s)
calls to allocation functions: 85034 (18602/s)
temporary memory allocations: 4003 (875/s)
peak heap memory consumption: 6.30MB
peak RSS (including heaptrack overhead): 609.55MB
total memory leaked: 165.66KB

[kuter]

@bbn Soo, I just realized that this way of implementing GraphTraits might be problematic with
graph iterators like (scc_iterator, df_ iterator) since they require a single entry point to correctly handle
disconnected graphs and the Attributor dependencies are disconnected. Most disconnected graphs use a "synthetic node"
because of this.

I did not tested this but if we where to df_iterator::begin(AA.DG) you would iterate over nodes that you can reach
by following the dependency edges of the first AbstractAttribute that is inside AllAbstractAttributes.
GraphWriter works well since it iterates over the nodes with ::nodes_start() and ::nodes_end().

If you do not require looking across connected components in your own work we can merge this patch like this and
I can write a separate patch that fixes this issue when I need to use the scc_iterator.

Only solution I can find for this that don't increase memory consumption, is to move the dependency tracking out of the
AbstractAttribute into a class like AADepNode and make AbstractAttribute inherit dependency tracking from that class.
If we where to move AllAbstractAttributes into the "synthetic node" we would have near zero memory overhead.

I know that this kinda like your initial implementation. sorry for the inconvenience.

[jdoerfert]

I see there is nice progress. I left two comment wrt. to test. If you want me to

llvm/include/llvm/Transforms/IPO/Attributor.h

1547

I agree that this will be a problem for unconnected graphs. How you organize the synthetic node is up to you. We need to make sure not to increase memory consumption but other than that we can move and replace the tiny Deps vectors, the AllAbstractAttribute vector, .. etc. as you see fit :)

3062

Can you add a comment to these overrides, just /// See AbstractAttribute::getName().

llvm/test/Transforms/Attributor/depgraph.ll

38

Run mem2reg on this test case please.
Also add all 4 run lines used in other tests.

[bbn]

• Use AADepGraphNode for dependence tracking and make AbstractAttribute inherent from it (thanks kuter for the advice)
• Updated testcase

[bbn]

Added missing comments

[kuter]

llvm/lib/Transforms/IPO/Attributor.cpp

2066

Aren't Deps the list of Attributes that need to be updated if this Attribute's state changes.
Isn't Deps a list of Attributes that depends on "this" Attribute ?

[sstefan1]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

683

Nit: is there a reason not to put these getName() in Attributor.h? Except for AAIsDead.

[kuter]

Hi can you rebase this.

[bbn]

1. Rebased patch
2. Replaced the AllAbstractAttributes with the syn node of the dependency graph
3. Moved getName() function to header file
4. The classof() function of the AbstractAttribute class simply returns true, because all nodes except for the syn node are of type AbstractAttribute (about classof function)

Heaptrack Benchmark:

• Before the patch:

total runtime: 5.67s.
bytes allocated in total (ignoring deallocations): 24.15MB (4.26MB/s)
calls to allocation functions: 84761 (14951/s)
temporary memory allocations: 4004 (706/s)
peak heap memory consumption: 6.30MB
peak RSS (including heaptrack overhead): 677.74MB
total memory leaked: 163.25KB

• After the patch, without replacing the AllAbstractAttribute vector and the change of classof() functon (change 2, 4)

total runtime: 6.11s.
bytes allocated in total (ignoring deallocations): 25.11MB (4.11MB/s)
calls to allocation functions: 86888 (14227/s)
temporary memory allocations: 4578 (749/s)
peak heap memory consumption: 6.49MB
peak RSS (including heaptrack overhead): 678.57MB
total memory leaked: 636.28KB

• After the patch, with change 2, without change 4:

total runtime: 6.26s.
bytes allocated in total (ignoring deallocations): 24.24MB (3.88MB/s)
calls to allocation functions: 86680 (13855/s)
temporary memory allocations: 4578 (731/s)
peak heap memory consumption: 6.23MB
peak RSS (including heaptrack overhead): 678.58MB
total memory leaked: 636.28KB

• After the patch, with all changes above

total runtime: 5.69s.
bytes allocated in total (ignoring deallocations): 24.18MB (4.25MB/s)
calls to allocation functions: 86669 (15223/s)
temporary memory allocations: 4577 (803/s)
peak heap memory consumption: 6.19MB
peak RSS (including heaptrack overhead): 675.89MB
total memory leaked: 633.87KB

[bbn]

• Added other 4 lines of test

[jdoerfert]

llvm/include/llvm/Transforms/IPO/Attributor.h

1377

Please add documentation explaining what these are. Also consider making them objects not pointers. That should remove the need to allocate them explicitly and also to deallocate them.

[bbn]

• Use references instead of pointer for the synthetic node

---

heaptrack result:

• before:

total runtime: 5.12s.
bytes allocated in total (ignoring deallocations): 24.03MB (4.69MB/s)
calls to allocation functions: 78903 (15404/s)
temporary memory allocations: 4003 (781/s)
peak heap memory consumption: 6.27MB
peak RSS (including heaptrack overhead): 628.13MB
total memory leaked: 140.33KB

• after:

total runtime: 5.53s.
bytes allocated in total (ignoring deallocations): 24.05MB (4.35MB/s)
calls to allocation functions: 80209 (14514/s)
temporary memory allocations: 4576 (828/s)
peak heap memory consumption: 6.17MB
peak RSS (including heaptrack overhead): 629.22MB
total memory leaked: 140.33KB

[kuter]

llvm/include/llvm/Transforms/IPO/Attributor.h

891

Why ?

Currently you are passing a synthetic node reference from outside
and doing
A.DG = ...
in runAttributorOnFunctions

Since the graph is now so light weight why don't we do it like Attributor::getDepGraph() ?
getDepGraph() would just return a AADepGraph with a reference to the SynDGN
Doing it this way you wouldn't have to set the DG from outside + you wouldn't need
to store a AADepGraphNode reference.

[bbn]

Move the synthetic node in to the dependency graph

[bbn]

llvm/include/llvm/Transforms/IPO/Attributor.h

891

Thanks for the idea. I have updated my patch and moved the synthetic node to the dependency graph, does that make sense?

[kuter]

llvm/include/llvm/Transforms/IPO/Attributor.h

891

From what I know the Attributor is also intended to be used as external component to make other deductions. I think it is weird for someone to pass a AADepGraph reference to the constructor that they are probably not going to use.

Also the AADepGraph just holds the SynDGN right ?
IMHO If we make it hold a pointer to the SynDGN instead we can pass it around by value.

That way we could have a

AADepGraph Attributor::getDepGraph() {
  return AADepGraph(&SynDGN);
}

Only potential problem with that would be that it would be holding a pointer to a member of the Attributor so the Attributor would have to out live the AADepGraph.

Considering that most AbstractAttribute's are not safe to print after manifestation this should not be a huge problem.
(print functions of many AbstractAttribute's print Value's that might be freed)

[bbn]

llvm/include/llvm/Transforms/IPO/Attributor.h

891

Oh, I see. What about directly declare the dep graph in the attributor struct as AADepGraph DG instead of a reference or a pointer?

[sstefan1]

llvm/include/llvm/Transforms/IPO/Attributor.h

891

I'd say definitely avoid putting it in constructor. First outside use of the Attributor is going to land soon. If reference field isn't working for you, you could at least try to make it pointer argument in the constructor and have it default to nullptr.

[kuter]

llvm/include/llvm/Transforms/IPO/Attributor.h

891

@bbn
I think it would be cleaner to just return it by value.

since the AADepGraph is just going to hold a pointer, the compiler should use a register to return it. https://godbolt.org/z/e5BkCe

[bbn]

Directly declare the dependency graph inside the Attributor struct, instead of a pointer or reference

[bbn]

llvm/include/llvm/Transforms/IPO/Attributor.h

891

@kuter
Here is my new idea: we put the dependency graph in the attributor using: AADepGraph DG, and in the dependency graph struct, we put the SyntheticRoot like AADepGraphNode SyntheticRoot.

To access the SyntheticRoot:

// use pointr
&(DG.SyntheticRoot);
 // or we can use reference
struct AADepGraphNode &getSynNode ()  {
  return DG.SyntheticRoot;
}

To access the Deps inside the SyntheticRoot:

getSynNode().Deps
// or like
&(DG.SyntheticRoot)->Deps

The reason why I prefer putting the dependency graph instead of a node is that:

1. We don't need to create the depgraph node each time we want to access it
2. This makes the code clearer and seems not to have much extra cost. (Not sure about that)

my tests: https://godbolt.org/z/ZEmwmu

[kuter]

llvm/include/llvm/Transforms/IPO/Attributor.h

891

Yes that would work. The getter function would be inlined.
But there is no cost of "creating" a new graph.

I personally think that my way is better but I don't think it matters that much.

[jdoerfert]

This looks pretty good :). Nice active review :)

I have some minor comments below. We also should add a test for the print and dot output.

llvm/include/llvm/Transforms/IPO/Attributor.h

183

Nit: no newline
Do we need print here anyway?

195

Nit: Move the DepTy definition in the node to the public definitions and use it here:
using DepTy = AADepGraphNode::DepTy

1441

This is the right way I think. The graph is essential to the operation and should be part of the Attributor.

llvm/lib/Transforms/IPO/Attributor.cpp

2073

const auto &DepAA

Maybe call this, printWithDeps or similar.

2137

Unused?

2153

Can we make this an atomic variable? Time spend here is not critical and it avoids future races.

2166

I think this sorting is not deterministic. Interestingly, the pointer relation should be. I can see that you want to group them so I suggest something like:

if (LHS->getName() == RHS->getName()) return LHS < RHS; return LSH->getName() < RHS->getName();

We probably should add a getter to all AAs to return the address of the ID they have. Then we can avoid using the name here which is weird and doesn't work if they do not implement a name. Feel free to create such a getter in a separate patch and use it here. Take a look at the way isa and (dyn_)cast work because we could even use the getter to allow those on AAs (which might be cool).

2170

Style: No braces for single statement for loops (multiple times above).

llvm/test/Transforms/Attributor/depgraph.ll

7

Hm, if we don't add the print option to the runtime above we don't need them I guess.

132

(Random thought) We should investigate if it makes sense to avoid such duplication. We need to run experiments I guess to determine that for "real code".

[bbn]

In D78861#2131573, @jdoerfert wrote:

This looks pretty good :). Nice active review :)

I have some minor comments below. We also should add a test for the print and dot output.

I need some help here:
Is there a way to test the dot output? I checked the .dot file and found it hard to write CHECK lines (see below) because we are interested in the link between different graph nodes (line 3 and line 4)

	Node0x55be15e4f7d0 [shape=record,label="{[AAValueSimplify] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{arg: [@0]\} with state simplified\n}"];
	Node0x55be15e4f810 [shape=record,label="{[AANoUnwind] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{fn:checkAndAdvance [checkAndAdvance@-1]\} with state nounwind\n}"];
	Node0x55be15e4f810 -> Node0x55be15e500b0;
	Node0x55be15e4f810 -> Node0x55be15e500b0;

I have referred to some other similar tests like the *cfg_deopt_unreach.ll*, but none of theme shows how to write check lines for such testcases.

[kuter]

In D78861#2133485, @bbn wrote:

In D78861#2131573, @jdoerfert wrote:

This looks pretty good :). Nice active review :)

I have some minor comments below. We also should add a test for the print and dot output.

I need some help here:
Is there a way to test the dot output? I checked the .dot file and found it hard to write CHECK lines (see below) because we are interested in the link between different graph nodes (line 3 and line 4)

	Node0x55be15e4f7d0 [shape=record,label="{[AAValueSimplify] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{arg: [@0]\} with state simplified\n}"];
	Node0x55be15e4f810 [shape=record,label="{[AANoUnwind] for CtxI '  %2 = load i32, i32* %0, align 4' at position \{fn:checkAndAdvance [checkAndAdvance@-1]\} with state nounwind\n}"];
	Node0x55be15e4f810 -> Node0x55be15e500b0;
	Node0x55be15e4f810 -> Node0x55be15e500b0;

I have referred to some other similar tests like the *cfg_deopt_unreach.ll*, but none of theme shows how to write check lines for such testcases.

I think something like this might work.

// CHECK-DAG: [[NODE1:Node0x[0-9a-f]+]]  ->[[NODE2]];
....

[bbn]

• Added tests for the dot file
• other style fixes

[jdoerfert]

Some minor things (below and from the last comment). LGTM otherwise. Thx :)

llvm/include/llvm/Transforms/IPO/Attributor.h

2069

Add a comment here and explain (especially) why we only return true.

llvm/lib/Transforms/IPO/Attributor.cpp

2171

Nit: use outs for print.

[kuter]

Hi @bbn when will commit this ?

[sstefan1]

I see you reverted this twice. Just curious what happened?

[fhahn]

FWIW, ideally the commit message should contain some explanation for the revert.

[bbn]

In previous diff, we use the address of the ID to sort the list of the AAs so that we can print them nicer.
But it seems that in different architectures, the address can be different, which can cause the sequence of
AAs are not deterministic and the test to fail.
So deleted the sorting part and I think now the sequence of AAs printed out should be deterministic, but I
am not sure.

Is there a way to run tests on different architectures (like the buildbot) before committing the patch, so that
I can make sure everything is working great.. (The tests passes on my x86_64 Linux machine, but I am unsure about others)

llvm/include/llvm/Transforms/IPO/Attributor.h

 //   `InformationCache::getOpcodeInstMapForFunction` interface and eliminate the
 //   need to traverse the IR repeatedly.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 
+#include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumeBundleQueries.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/AbstractCallSite.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Allocator.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/DOTGraphTraits.h"
+#include "llvm/Support/GraphWriter.h"
 #include "llvm/Transforms/Utils/CallGraphUpdater.h"
 
 namespace llvm {
 
+struct AADepGraphNode;
+struct AADepGraph;
 struct Attributor;
 struct AbstractAttribute;
 struct InformationCache;
 struct AAIsDead;
 
 class Function;
 
 /// Simple enum classes that forces properties to be spelled out explicitly.
 ///
 ///{
 enum class ChangeStatus {
   CHANGED,
   UNCHANGED,
 };
 
 ChangeStatus operator|(ChangeStatus l, ChangeStatus r);
 ChangeStatus operator&(ChangeStatus l, ChangeStatus r);
 
 enum class DepClassTy {
   REQUIRED,
   OPTIONAL,
 };
 ///}
 
+/// The data structure for the nodes of a dependency graph
+struct AADepGraphNode {
+public:
+  virtual ~AADepGraphNode(){};
+
+protected:
+  /// Set of dependency graph nodes which this one depends on.
+  /// The bit encodes if it is optional.
+  using DepTy = PointerIntPair<AADepGraphNode *, 1>;
+  TinyPtrVector<DepTy> Deps;
+
+  static AADepGraphNode *DepGetVal(DepTy &DT) { return DT.getPointer(); }
+  static AbstractAttribute *DepGetValAA(DepTy &DT) {
+    return cast<AbstractAttribute>(DT.getPointer());
+  }
+
+  operator AbstractAttribute *() { return cast<AbstractAttribute>(this); }
+
+public:
+  using iterator =
+      mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
+  using aaiterator =
+      mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetValAA)>;
+
+  aaiterator begin() { return aaiterator(Deps.begin(), &DepGetValAA); }
+  aaiterator end() { return aaiterator(Deps.end(), &DepGetValAA); }
+  iterator child_begin() { return iterator(Deps.begin(), &DepGetVal); }
+  iterator child_end() { return iterator(Deps.end(), &DepGetVal); }
+
+  virtual void print(raw_ostream &OS) const { OS << "AADepNode Impl\n"; }
+
+  TinyPtrVector<DepTy> &getDeps() { return Deps; }
+
+  friend struct Attributor;
+  friend struct AADepGraph;
+};
+
+struct AADepGraph {
+  AADepGraph() {}
+  ~AADepGraph() {}
+
+  using DepTy = PointerIntPair<AADepGraphNode *, 1>;
+  static AADepGraphNode *DepGetVal(DepTy &DT) { return DT.getPointer(); }
+  using iterator =
+      mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
+
+  /// There is no root node for the dependency graph. But the SCCIterator
+  /// requires a single entry point, so we maintain a fake("synthetic") root
+  /// node that depends on every node.
+  AADepGraphNode SyntheticRoot;
+
+  AADepGraphNode *GetEntryNode() { return &SyntheticRoot; }
+
+  iterator begin() { return SyntheticRoot.child_begin(); }
+  iterator end() { return SyntheticRoot.child_end(); }
+
+  void viewGraph();
+
+  /// Dump graph to file
+  void dumpGraph();
+
+  /// Print dependency graph
+  void print();
+};
+
 /// Helper to describe and deal with positions in the LLVM-IR.
 ///
 /// A position in the IR is described by an anchor value and an "offset" that
 /// could be the argument number, for call sites and arguments, or an indicator
 /// of the "position kind". The kinds, specified in the Kind enum below, include
 /// the locations in the attribute list, i.a., function scope and return value,
 /// as well as a distinction between call sites and functions. Finally, there
 /// are floating values that do not have a corresponding attribute list
struct Attributor {
   ///
   /// \param Functions The set of functions we are deriving attributes for.
   /// \param InfoCache Cache to hold various information accessible for
   ///                  the abstract attributes.
   /// \param CGUpdater Helper to update an underlying call graph.
   /// \param Allowed If not null, a set limiting the attribute opportunities.
   Attributor(SetVector<Function *> &Functions, InformationCache &InfoCache,
              CallGraphUpdater &CGUpdater,
              DenseSet<const char *> *Allowed = nullptr)
       : Allocator(InfoCache.Allocator), Functions(Functions),
         InfoCache(InfoCache), CGUpdater(CGUpdater), Allowed(Allowed) {}
 
   ~Attributor();
 
   /// Run the analyses until a fixpoint is reached or enforced (timeout).
   ///
   /// The attributes registered with this Attributor can be used after as long
template <typename AAType> AAType &registerAA(AAType &AA) {
     // Put the attribute in the lookup map structure and the container we use to
     // keep track of all attributes.
     const IRPosition &IRP = AA.getIRPosition();
     AbstractAttribute *&AAPtr = AAMap[{&AAType::ID, IRP}];
 
     assert(!AAPtr && "Attribute already in map!");
     AAPtr = &AA;
 
-    AllAbstractAttributes.push_back(&AA);
+    DG.SyntheticRoot.Deps.push_back(
+        AADepGraphNode::DepTy(&AA, unsigned(DepClassTy::REQUIRED)));
+
     return AA;
   }
 
   /// Return the internal information cache.
   InformationCache &getInfoCache() { return InfoCache; }
 
   /// Return true if this is a module pass, false otherwise.
   bool isModulePass() const {
struct Attributor {
   /// to memory present in the information cache and return true if \p Pred
   /// holds on all of them.
   bool checkForAllReadWriteInstructions(function_ref<bool(Instruction &)> Pred,
                                         AbstractAttribute &QueryingAA);
 
   /// Return the data layout associated with the anchor scope.
   const DataLayout &getDataLayout() const { return InfoCache.DL; }
 
+  /// Print All dependencies for every AbstractAttribute in the AA list
+  /// For debug use only.
+  void printAllDependency(raw_ostream &);
+
   /// The allocator used to allocate memory, e.g. for `AbstractAttribute`s.
   BumpPtrAllocator &Allocator;
 
 private:
   /// This method will do fixpoint iteration until fixpoint or the
   /// maximum iteration count is reached.
   ///
   /// If the maximum iteration count is reached, This method will
   /// indicate pessimistic fixpoint on attributes that transitively depend
   /// on attributes that were scheduled for an update.
   void runTillFixpoint();
 
   /// Gets called after scheduling, manifests attributes to the LLVM IR.
   ChangeStatus manifestAttributes();
bool checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred,
                             bool &AllCallSitesKnown);
 
   /// Apply all requested function signature rewrites
   /// (\see registerFunctionSignatureRewrite) and return Changed if the module
   /// was altered.
   ChangeStatus
   rewriteFunctionSignatures(SmallPtrSetImpl<Function *> &ModifiedFns);
 
-  /// The set of all abstract attributes.
-  ///{
-  using AAVector = SmallVector<AbstractAttribute *, 64>;
-  AAVector AllAbstractAttributes;
-  ///}
-
   /// A nested map to lookup abstract attributes based on the argument position
   /// on the outer level, and the addresses of the static member (AAType::ID) on
   /// the inner level.
   ///{
   using AAMapKeyTy = std::pair<const char *, IRPosition>;
   DenseMap<AAMapKeyTy, AbstractAttribute *> AAMap;
   ///}
 
   /// Map to remember all requested signature changes (= argument replacements).
   DenseMap<Function *, SmallVector<std::unique_ptr<ArgumentReplacementInfo>, 8>>
       ArgumentReplacementMap;
 
   /// The set of functions we are deriving attributes for.
   SetVector<Function *> &Functions;
 
   /// The information cache that holds pre-processed (LLVM-IR) information.
   InformationCache &InfoCache;
 
   /// Helper to update an underlying call graph.
   CallGraphUpdater &CGUpdater;
 
+  /// Abstract Attribute dependency graph
+  AADepGraph DG;
+
   /// Set of functions for which we modified the content such that it might
   /// impact the call graph.
   SmallPtrSet<Function *, 8> CGModifiedFunctions;
 
   /// Information about a dependence. If FromAA is changed ToAA needs to be
   /// updated as well.
   struct DepInfo {
     const AbstractAttribute *FromAA;
private:
 
   /// Functions, blocks, and instructions we delete after manifest is done.
   ///
   ///{
   SmallPtrSet<Function *, 8> ToBeDeletedFunctions;
   SmallPtrSet<BasicBlock *, 8> ToBeDeletedBlocks;
   SmallDenseSet<WeakVH, 8> ToBeDeletedInsts;
   ///}
+
+  friend AADepGraph;
 };
 
 /// An interface to query the internal state of an abstract attribute.
 ///
 /// The abstract state is a minimal interface that allows the Attributor to
 /// communicate with the abstract attributes about their internal state without
 /// enforcing or exposing implementation details, e.g., the (existence of an)
 /// underlying lattice.

 /// bits. Users can only add known bits and, except through adding known bits,
 /// they can only remove assumed bits. This should guarantee monotoniticy and
 /// thereby the existence of a fixpoint (if used corretly). The fixpoint is
 /// reached when the assumed and known state/bits are equal. Users can
 /// force/inidicate a fixpoint. If an optimistic one is indicated, the known
 /// state will catch up with the assumed one, for a pessimistic fixpoint it is
 /// the other way around.
 template <typename base_ty, base_ty BestState, base_ty WorstState>
 struct IntegerStateBase : public AbstractState {
   using base_t = base_ty;
 
   IntegerStateBase() {}
   IntegerStateBase(base_t Assumed) : Assumed(Assumed) {}
 
   /// Return the best possible representable state.
   static constexpr base_t getBestState() { return BestState; }
   static constexpr base_t getBestState(const IntegerStateBase &) {

 ///       optimistic information obtained through abstract attributes should
 ///       only be used at positions that precede the origin of the information
 ///       with regards to the program flow. More practically, information can
 ///       *now* be propagated from instructions to their enclosing function, but
 ///       *not* from call sites to the called function. The mechanisms to allow
 ///       both directions will be added in the future.
 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
 ///       described in the file comment.
-struct AbstractAttribute : public IRPosition {
+struct AbstractAttribute : public IRPosition, public AADepGraphNode {
   using StateType = AbstractState;
 
   AbstractAttribute(const IRPosition &IRP) : IRPosition(IRP) {}
 
   /// Virtual destructor.
   virtual ~AbstractAttribute() {}
 
+  static bool classof(const AADepGraphNode *DGN) { return true; }
+
   /// Initialize the state with the information in the Attributor \p A.
   ///
   /// This function is called by the Attributor once all abstract attributes
   /// have been identified. It can and shall be used for task like:
   ///  - identify existing knowledge in the IR and use it for the "known state"
   ///  - perform any work that is not going to change over time, e.g., determine
   ///    a subset of the IR, or attributes in-flight, that have to be looked at
   ///    in the `updateImpl` method.
   virtual void initialize(Attributor &A) {}
 
   /// Return the internal abstract state for inspection.
   virtual StateType &getState() = 0;
   virtual const StateType &getState() const = 0;
 
   /// Return an IR position, see struct IRPosition.
   const IRPosition &getIRPosition() const { return *this; };
   IRPosition &getIRPosition() { return *this; };
 
   /// Helper functions, for debug purposes only.
   ///{
   virtual void print(raw_ostream &OS) const;
+  virtual void printDeps(raw_ostream &OS) const;
   void dump() const { print(dbgs()); }
 
   /// This function should return the "summarized" assumed state as string.
   virtual const std::string getAsStr() const = 0;
 
   /// This function should return the name of the AbstractAttribute
   virtual const std::string getName() const = 0;
   ///}
protected:
   /// The actual update/transfer function which has to be implemented by the
   /// derived classes.
   ///
   /// If it is called, the environment has changed and we have to determine if
   /// the current information is still valid or adjust it otherwise.
   ///
   /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
   virtual ChangeStatus updateImpl(Attributor &A) = 0;
-
-private:
-  /// Set of abstract attributes which were queried by this one. The bit encodes
-  /// if there is an optional of required dependence.
-  using DepTy = PointerIntPair<AbstractAttribute *, 1>;
-  TinyPtrVector<DepTy> Deps;
 };
 
 /// Forward declarations of output streams for debug purposes.
 ///
 ///{
 raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA);
 raw_ostream &operator<<(raw_ostream &OS, ChangeStatus S);
 raw_ostream &operator<<(raw_ostream &OS, IRPosition::Kind);
struct AAMemoryLocation
   static AAMemoryLocation &createForPosition(const IRPosition &IRP,
                                              Attributor &A);
 
   /// See AbstractState::getAsStr().
   const std::string getAsStr() const override {
     return getMemoryLocationsAsStr(getAssumedNotAccessedLocation());
   }
 
   /// See AbstractAttribute::getName()
   const std::string getName() const override { return "AAMemoryLocation"; }
 
   /// Unique ID (due to the unique address)
   static const char ID;
 };
 
 /// An abstract interface for range value analysis.
 struct AAValueConstantRange

llvm/lib/Transforms/IPO/Attributor.cpp

 // attributes. This is done in an abstract interpretation style fixpoint
 // iteration. See the Attributor.h file comment and the class descriptions in
 // that file for more information.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/Attributor.h"
 
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/NoFolder.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/GraphWriter.h"
+#include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 
 #include <cassert>
+#include <string>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "attributor"
 
 STATISTIC(NumFnDeleted, "Number of function deleted");
 STATISTIC(NumFnWithExactDefinition,
           "Number of functions with exact definitions");
static cl::opt<bool> EnableHeapToStack("enable-heap-to-stack-conversion",
                                        cl::init(true), cl::Hidden);
 
 static cl::opt<bool>
     AllowShallowWrappers("attributor-allow-shallow-wrappers", cl::Hidden,
                          cl::desc("Allow the Attributor to create shallow "
                                   "wrappers for non-exact definitions."),
                          cl::init(false));
 
+static cl::opt<bool>
+    DumpDepGraph("attributor-dump-dep-graph", cl::Hidden,
+                 cl::desc("Dump the dependency graph to dot files."),
+                 cl::init(false));
+
+static cl::opt<bool> ViewDepGraph("attributor-view-dep-graph", cl::Hidden,
+                                  cl::desc("View the dependency graph."),
+                                  cl::init(false));
+
+static cl::opt<bool> PrintDependencies("attributor-print-dep", cl::Hidden,
+                                       cl::desc("Print attribute dependencies"),
+                                       cl::init(false));
+
 /// Logic operators for the change status enum class.
 ///
 ///{
 ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::CHANGED ? l : r;
 }
 ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::UNCHANGED ? l : r;
Attributor::getAssumedConstant(const Value &V, const AbstractAttribute &AA,
   if (CI)
     recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL);
   return CI;
 }
 
 Attributor::~Attributor() {
   // The abstract attributes are allocated via the BumpPtrAllocator Allocator,
   // thus we cannot delete them. We can, and want to, destruct them though.
-  for (AbstractAttribute *AA : AllAbstractAttributes)
+  for (auto depAA : DG.SyntheticRoot.Deps) {
+    AbstractAttribute *AA = cast<AbstractAttribute>(depAA.getPointer());
     AA->~AbstractAttribute();
   }
+}
 
 bool Attributor::isAssumedDead(const AbstractAttribute &AA,
                                const AAIsDead *FnLivenessAA,
                                bool CheckBBLivenessOnly, DepClassTy DepClass) {
   const IRPosition &IRP = AA.getIRPosition();
   if (!Functions.count(IRP.getAnchorScope()))
     return false;
   return isAssumedDead(IRP, &AA, FnLivenessAA, CheckBBLivenessOnly, DepClass);
if (!Pred(*I))
       return false;
   }
 
   return true;
 }
 
 void Attributor::runTillFixpoint() {
   LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
-                    << AllAbstractAttributes.size()
+                    << DG.SyntheticRoot.Deps.size()
                     << " abstract attributes.\n");
 
   // Now that all abstract attributes are collected and initialized we start
   // the abstract analysis.
 
   unsigned IterationCounter = 1;
 
   SmallVector<AbstractAttribute *, 32> ChangedAAs;
   SetVector<AbstractAttribute *> Worklist, InvalidAAs;
-  Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
+  Worklist.insert(DG.SyntheticRoot.begin(), DG.SyntheticRoot.end());
 
   do {
     // Remember the size to determine new attributes.
-    size_t NumAAs = AllAbstractAttributes.size();
+    size_t NumAAs = DG.SyntheticRoot.Deps.size();
     LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
                       << ", Worklist size: " << Worklist.size() << "\n");
 
     // For invalid AAs we can fix dependent AAs that have a required dependence,
     // thereby folding long dependence chains in a single step without the need
     // to run updates.
     for (unsigned u = 0; u < InvalidAAs.size(); ++u) {
       AbstractAttribute *InvalidAA = InvalidAAs[u];
 
       // Check the dependences to fast track invalidation.
       LLVM_DEBUG(dbgs() << "[Attributor] InvalidAA: " << *InvalidAA << " has "
                         << InvalidAA->Deps.size()
                         << " required & optional dependences\n");
       while (!InvalidAA->Deps.empty()) {
         const auto &Dep = InvalidAA->Deps.back();
         InvalidAA->Deps.pop_back();
-        AbstractAttribute *DepAA = Dep.getPointer();
+        AbstractAttribute *DepAA = cast<AbstractAttribute>(Dep.getPointer());
         if (Dep.getInt() == unsigned(DepClassTy::OPTIONAL)) {
           Worklist.insert(DepAA);
           continue;
         }
         DepAA->getState().indicatePessimisticFixpoint();
         assert(DepAA->getState().isAtFixpoint() && "Expected fixpoint state!");
         if (!DepAA->getState().isValidState())
           InvalidAAs.insert(DepAA);
         else
           ChangedAAs.push_back(DepAA);
       }
     }
 
     // Add all abstract attributes that are potentially dependent on one that
     // changed to the work list.
     for (AbstractAttribute *ChangedAA : ChangedAAs)
       while (!ChangedAA->Deps.empty()) {
-        Worklist.insert(ChangedAA->Deps.back().getPointer());
+        Worklist.insert(
+            cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
         ChangedAA->Deps.pop_back();
       }
 
     LLVM_DEBUG(dbgs() << "[Attributor] #Iteration: " << IterationCounter
                       << ", Worklist+Dependent size: " << Worklist.size()
                       << "\n");
 
     // Reset the changed and invalid set.
for (AbstractAttribute *AA : Worklist) {
       // Use the InvalidAAs vector to propagate invalid states fast transitively
       // without requiring updates.
       if (!AAState.isValidState())
         InvalidAAs.insert(AA);
     }
 
     // Add attributes to the changed set if they have been created in the last
     // iteration.
-    ChangedAAs.append(AllAbstractAttributes.begin() + NumAAs,
-                      AllAbstractAttributes.end());
+    ChangedAAs.append(DG.SyntheticRoot.begin() + NumAAs,
+                      DG.SyntheticRoot.end());
 
     // Reset the work list and repopulate with the changed abstract attributes.
     // Note that dependent ones are added above.
     Worklist.clear();
     Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
 
   } while (!Worklist.empty() && (IterationCounter++ < MaxFixpointIterations ||
                                  VerifyMaxFixpointIterations));
for (unsigned u = 0; u < ChangedAAs.size(); u++) {
     AbstractState &State = ChangedAA->getState();
     if (!State.isAtFixpoint()) {
       State.indicatePessimisticFixpoint();
 
       NumAttributesTimedOut++;
     }
 
     while (!ChangedAA->Deps.empty()) {
-      ChangedAAs.push_back(ChangedAA->Deps.back().getPointer());
+      ChangedAAs.push_back(
+          cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
       ChangedAA->Deps.pop_back();
     }
   }
 
   LLVM_DEBUG({
     if (!Visited.empty())
       dbgs() << "\n[Attributor] Finalized " << Visited.size()
              << " abstract attributes.\n";
   });
 
   if (VerifyMaxFixpointIterations &&
       IterationCounter != MaxFixpointIterations) {
     errs() << "\n[Attributor] Fixpoint iteration done after: "
            << IterationCounter << "/" << MaxFixpointIterations
            << " iterations\n";
     llvm_unreachable("The fixpoint was not reached with exactly the number of "
                      "specified iterations!");
   }
 }
 
 ChangeStatus Attributor::manifestAttributes() {
-  size_t NumFinalAAs = AllAbstractAttributes.size();
+  size_t NumFinalAAs = DG.SyntheticRoot.Deps.size();
 
   unsigned NumManifested = 0;
   unsigned NumAtFixpoint = 0;
   ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
-  for (AbstractAttribute *AA : AllAbstractAttributes) {
+  for (auto depAA : DG.SyntheticRoot.Deps) {
+    AbstractAttribute *AA = cast<AbstractAttribute>(depAA.getPointer());
     AbstractState &State = AA->getState();
 
     // If there is not already a fixpoint reached, we can now take the
     // optimistic state. This is correct because we enforced a pessimistic one
     // on abstract attributes that were transitively dependent on a changed one
     // already above.
     if (!State.isAtFixpoint())
       State.indicateOptimisticFixpoint();
ChangeStatus Attributor::manifestAttributes() {
   LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
                     << " arguments while " << NumAtFixpoint
                     << " were in a valid fixpoint state\n");
 
   NumAttributesManifested += NumManifested;
   NumAttributesValidFixpoint += NumAtFixpoint;
 
   (void)NumFinalAAs;
-  if (NumFinalAAs != AllAbstractAttributes.size()) {
-    for (unsigned u = NumFinalAAs; u < AllAbstractAttributes.size(); ++u)
-      errs() << "Unexpected abstract attribute: " << *AllAbstractAttributes[u]
+  if (NumFinalAAs != DG.SyntheticRoot.Deps.size()) {
+    for (unsigned u = NumFinalAAs; u < DG.SyntheticRoot.Deps.size(); ++u)
+      errs() << "Unexpected abstract attribute: "
+             << cast<AbstractAttribute>(DG.SyntheticRoot.Deps[u].getPointer())
              << " :: "
-             << AllAbstractAttributes[u]->getIRPosition().getAssociatedValue()
+             << cast<AbstractAttribute>(DG.SyntheticRoot.Deps[u].getPointer())
+                    ->getIRPosition()
+                    .getAssociatedValue()
              << "\n";
     llvm_unreachable("Expected the final number of abstract attributes to "
                      "remain unchanged!");
   }
   return ManifestChange;
 }
 
 ChangeStatus Attributor::cleanupIR() {
#ifdef EXPENSIVE_CHECKS
   }
 #endif
 
   return ManifestChange;
 }
 
 ChangeStatus Attributor::run() {
   runTillFixpoint();
+
+  // dump graphs on demand
+  if (DumpDepGraph)
+    DG.dumpGraph();
+
+  if (ViewDepGraph)
+    DG.viewGraph();
+
+  if (PrintDependencies)
+    DG.print();
+
   ChangeStatus ManifestChange = manifestAttributes();
   ChangeStatus CleanupChange = cleanupIR();
   return ManifestChange | CleanupChange;
 }
 
 ChangeStatus Attributor::updateAA(AbstractAttribute &AA) {
   // Use a new dependence vector for this update.
   DependenceVector DV;

 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
   AA.print(OS);
   return OS;
 }
 
 void AbstractAttribute::print(raw_ostream &OS) const {
-  OS << "[P: " << getIRPosition() << "][" << getAsStr() << "][S: " << getState()
-     << "]";
+  OS << "[";
+  OS << getName();
+  OS << "] for CtxI ";
+
+  if (auto *I = getCtxI()) {
+    OS << "'";
+    I->print(OS);
+    OS << "'";
+  } else
+    OS << "<<null inst>>";
+
+  OS << " at position " << getIRPosition() << " with state " << getAsStr()
+     << '\n';
+}
+
+void AbstractAttribute::printDeps(raw_ostream &OS) const {
+  print(OS);
+
+  for (const auto DepAA : Deps) {
+    auto *AA = DepAA.getPointer();
+    OS << "  updates ";
+    AA->print(OS);
+  }
+
+  OS << '\n';
 }
 ///}
 
 /// ----------------------------------------------------------------------------
 ///                       Pass (Manager) Boilerplate
 /// ----------------------------------------------------------------------------
 
 static bool runAttributorOnFunctions(InformationCache &InfoCache,
static bool runAttributorOnFunctions(InformationCache &InfoCache,
 
   for (Function *F : Functions) {
     if (F->hasExactDefinition())
       NumFnWithExactDefinition++;
     else
       NumFnWithoutExactDefinition++;
 
     // We look at internal functions only on-demand but if any use is not a
-    // direct call or outside the current set of analyzed functions, we have to
-    // do it eagerly.
+    // direct call or outside the current set of analyzed functions, we have
+    // to do it eagerly.
     if (F->hasLocalLinkage()) {
       if (llvm::all_of(F->uses(), [&Functions](const Use &U) {
             const auto *CB = dyn_cast<CallBase>(U.getUser());
             return CB && CB->isCallee(&U) &&
                    Functions.count(const_cast<Function *>(CB->getCaller()));
           }))
         continue;
     }
 
     // Populate the Attributor with abstract attribute opportunities in the
     // function and the information cache with IR information.
     A.identifyDefaultAbstractAttributes(*F);
   }
 
   ChangeStatus Changed = A.run();
+
   LLVM_DEBUG(dbgs() << "[Attributor] Done with " << Functions.size()
                     << " functions, result: " << Changed << ".\n");
   return Changed == ChangeStatus::CHANGED;
 }
 
+void Attributor::printAllDependency(raw_ostream &OS) {
+  for (auto AA : DG.SyntheticRoot.Deps) {
+    cast<AbstractAttribute>(AA.getPointer())->printDeps(OS);
+  }
+}
+
+void AADepGraph::viewGraph() { llvm::ViewGraph(this, "Dependency Graph"); }
+
+void AADepGraph::dumpGraph() {
+  static int CallTimes = 0;
+  std::string Filename = "dot_file_" + std::to_string(CallTimes) + ".dot";
+
+  errs() << "Dependency graph dump to " << Filename << ".\n";
+
+  std::error_code EC;
+
+  raw_fd_ostream File(Filename, EC, sys::fs::OF_Text);
+  if (!EC)
+    llvm::WriteGraph(File, this);
+
+  CallTimes++;
+}
+
+void AADepGraph::print() {
+  SmallVector<AbstractAttribute *, 16> AAs;
+  AAs.reserve(SyntheticRoot.Deps.size());
+
+  for (auto tAA : SyntheticRoot.Deps) {
+    AAs.push_back(cast<AbstractAttribute>(tAA.getPointer()));
+  }
+
+  llvm::sort(AAs, [](AbstractAttribute *LHS, AbstractAttribute *RHS) {
+    return LHS->getName() < RHS->getName();
+  });
+
+  for (AbstractAttribute *AA : AAs)
+    AA->printDeps(errs());
+}
+
 PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
   FunctionAnalysisManager &FAM =
       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
   AnalysisGetter AG(FAM);
 
   SetVector<Function *> Functions;
   for (Function &F : M)
     Functions.insert(&F);
PreservedAnalyses AttributorCGSCCPass::run(LazyCallGraph::SCC &C,
   InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ &Functions);
   if (runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater)) {
     // FIXME: Think about passes we will preserve and add them here.
     return PreservedAnalyses::none();
   }
   return PreservedAnalyses::all();
 }
 
+namespace llvm {
+
+template <> struct GraphTraits<AADepGraphNode *> {
+  using NodeRef = AADepGraphNode *;
+  using DepTy = PointerIntPair<AADepGraphNode *, 1>;
+  using EdgeRef = PointerIntPair<AADepGraphNode *, 1>;
+
+  static NodeRef getEntryNode(AADepGraphNode *DGN) { return DGN; }
+  static NodeRef DepGetVal(DepTy &DT) { return DT.getPointer(); }
+
+  using ChildIteratorType =
+      mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
+  using ChildEdgeIteratorType = TinyPtrVector<DepTy>::iterator;
+
+  static ChildIteratorType child_begin(NodeRef N) { return N->child_begin(); }
+
+  static ChildIteratorType child_end(NodeRef N) { return N->child_end(); }
+};
+
+template <>
+struct GraphTraits<AADepGraph *> : public GraphTraits<AADepGraphNode *> {
+  static NodeRef getEntryNode(AADepGraph *DG) { return DG->GetEntryNode(); }
+
+  using nodes_iterator =
+      mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
+
+  static nodes_iterator nodes_begin(AADepGraph *DG) { return DG->begin(); }
+
+  static nodes_iterator nodes_end(AADepGraph *DG) { return DG->end(); }
+};
+
+template <> struct DOTGraphTraits<AADepGraph *> : public DefaultDOTGraphTraits {
+  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
+
+  static std::string getNodeLabel(const AADepGraphNode *Node,
+                                  const AADepGraph *DG) {
+    std::string AAString = "";
+    raw_string_ostream O(AAString);
+    Node->print(O);
+    return AAString;
+  }
+};
+
+} // end namespace llvm
+
 namespace {
 
 struct AttributorLegacyPass : public ModulePass {
   static char ID;
 
   AttributorLegacyPass() : ModulePass(ID) {
     initializeAttributorLegacyPassPass(*PassRegistry::getPassRegistry());
   }

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

 struct AANoUnwindImpl : AANoUnwind {
   AANoUnwindImpl(const IRPosition &IRP, Attributor &A) : AANoUnwind(IRP, A) {}
 
   const std::string getAsStr() const override {
     return getAssumed() ? "nounwind" : "may-unwind";
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     auto Opcodes = {
         (unsigned)Instruction::Invoke,      (unsigned)Instruction::CallBr,
         (unsigned)Instruction::Call,        (unsigned)Instruction::CleanupRet,
         (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume};
 
     auto CheckForNoUnwind = [&](Instruction &I) {
       if (!I.mayThrow())
         return true;
if (!A.checkForAllInstructions(CheckReturnInst, *this, {Instruction::Ret}))
     return indicatePessimisticFixpoint();
 
   // Once returned values "directly" present in the code are handled we try to
   // resolve returned calls. To avoid modifications to the ReturnedValues map
   // while we iterate over it we kept record of potential new entries in a copy
   // map, NewRVsMap.
   decltype(ReturnedValues) NewRVsMap;
 
-  auto HandleReturnValue = [&](Value *RV, SmallSetVector<ReturnInst *, 4> &RIs) {
-    LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *RV
-                      << " by #" << RIs.size() << " RIs\n");
+  auto HandleReturnValue = [&](Value *RV,
+                               SmallSetVector<ReturnInst *, 4> &RIs) {
+    LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *RV << " by #"
+                      << RIs.size() << " RIs\n");
     CallBase *CB = dyn_cast<CallBase>(RV);
     if (!CB || UnresolvedCalls.count(CB))
       return;
 
     if (!CB->getCalledFunction()) {
       LLVM_DEBUG(dbgs() << "[AAReturnedValues] Unresolved call: " << *CB
                         << "\n");
       UnresolvedCalls.insert(CB);
auto VisitValueCB = [&](const Value &V, const Instruction *, DerefState &T,
         DerefBytes = Base->getPointerDereferenceableBytes(DL, CanBeNull);
         T.GlobalState.indicatePessimisticFixpoint();
       } else {
         const DerefState &DS = static_cast<const DerefState &>(AA.getState());
         DerefBytes = DS.DerefBytesState.getAssumed();
         T.GlobalState &= DS.GlobalState;
       }
 
-
       // For now we do not try to "increase" dereferenceability due to negative
       // indices as we first have to come up with code to deal with loops and
       // for overflows of the dereferenceable bytes.
       int64_t OffsetSExt = Offset.getSExtValue();
       if (OffsetSExt < 0)
         OffsetSExt = 0;
 
       T.takeAssumedDerefBytesMinimum(

llvm/test/Transforms/Attributor/depgraph.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+
+; RUN: opt -attributor -attributor-manifest-internal  -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=9 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
+; RUN: opt -aa-pipeline=basic-aa -passes=attributor -attributor-manifest-internal  -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=9 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_OPM,NOT_CGSCC_NPM,NOT_TUNIT_OPM,IS__TUNIT____,IS________NPM,IS__TUNIT_NPM
+; RUN: opt -attributor-cgscc -attributor-manifest-internal  -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_NPM,IS__CGSCC____,IS________OPM,IS__CGSCC_OPM
+; RUN: opt -aa-pipeline=basic-aa -passes=attributor-cgscc -attributor-manifest-internal  -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_OPM,IS__CGSCC____,IS________NPM,IS__CGSCC_NPM
+; RUN: opt -passes=attributor-cgscc -disable-output -attributor-print-dep < %s 2>&1 | FileCheck %s --check-prefixes=GRAPH
+
+; Test 0
+;
+; test copied from the attributor introduction video: checkAndAdvance(), and the C code is:
+; int *checkAndAdvance(int * __attribute__((aligned(16))) p) {
+;   if (*p == 0)
+;     return checkAndAdvance(p + 4);
+;   return p;
+; }
+;
+define i32* @checkAndAdvance(i32* align 16 %0) {
+; CHECK-LABEL: @checkAndAdvance(
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[TMP0:%.*]], align 16
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 0
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP7:%.*]]
+; CHECK:       4:
+; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i32, i32* [[TMP0]], i64 4
+; CHECK-NEXT:    [[TMP6:%.*]] = call nonnull align 16 i32* @checkAndAdvance(i32* nofree nonnull readonly align 16 "no-capture-maybe-returned" [[TMP5]]) #1
+; CHECK-NEXT:    br label [[TMP8:%.*]]
+; CHECK:       7:
+; CHECK-NEXT:    br label [[TMP8]]
+; CHECK:       8:
+; CHECK-NEXT:    [[DOT0:%.*]] = phi i32* [ [[TMP6]], [[TMP4]] ], [ [[TMP0]], [[TMP7]] ]
+; CHECK-NEXT:    ret i32* [[DOT0]]
+;
+  %2 = load i32, i32* %0, align 4
+  %3 = icmp eq i32 %2, 0
+  br i1 %3, label %4, label %7
+
+4:                                                ; preds = %1
+  %5 = getelementptr inbounds i32, i32* %0, i64 4
+  %6 = call i32* @checkAndAdvance(i32* %5)
+  br label %8
+
+7:                                                ; preds = %1
+  br label %8
+
+8:                                                ; preds = %7, %4
+  %.0 = phi i32* [ %6, %4 ], [ %0, %7 ]
+  ret i32* %.0
+}
+
+; GRAPH: [AAAlign] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
+; GRAPH:  updates [AAAlign] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+; GRAPH:  updates [AAAlign] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+
+; GRAPH: [AAAlign] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+; GRAPH:  updates [AAAlign] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
+
+; GRAPH: [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AAIsDead] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+
+; GRAPH: [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+
+; GRAPH: [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+; GRAPH:  updates [AAMemoryLocation] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+; GRAPH:  updates [AAMemoryLocation] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+; GRAPH:  updates [AAMemoryLocation] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+
+; GRAPH: [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+; GRAPH: updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+
+; GRAPH: [AAMemoryLocation] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AAMemoryLocation] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+
+; GRAPH: [AAMemoryLocation] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+; GRAPH:  updates [AAMemoryLocation] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AAMemoryLocation] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+
+; GRAPH: [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+
+; GRAPH: [AANoCapture] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+
+; GRAPH: [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+; GRAPH:  updates [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoFree] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AANoFree] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+
+; GRAPH: [AANoFree] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+
+; GRAPH: [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoFree] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+
+; GRAPH: [AANoSync] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+; GRAPH:  updates [AANoSync] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AANoSync] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+
+; GRAPH: [AANoSync] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AANoSync] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+
+; GRAPH: [AANoUnwind] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoUnwind] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AANoUnwind] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AANoUnwind] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; GRAPH:  updates [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+
+; GRAPH: [AANoUnwind] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; GRAPH:  updates [AAIsDead] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+; GRAPH:  updates [AAIsDead] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+; GRAPH:  updates [AANoUnwind] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+
+; GRAPH: [AANonNull] for CtxI '  %5 = getelementptr inbounds i32, i32* %0, i64 4' at position {flt: [@-1]}
+; GRAPH:  updates [AANonNull] for CtxI '  %5 = getelementptr inbounds i32, i32* %0, i64 4' at position {flt: [@-1]}
+; GRAPH:  updates [AANonNull] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+; GRAPH:  updates [AANonNull] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
+; GRAPH:  updates [AANonNull] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
+
+; GRAPH: [AANonNull] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+; GRAPH:  updates [AANonNull] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
+
+; GRAPH: [AANonNull] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
+; GRAPH:  updates [AANonNull] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+; GRAPH:  updates [AANonNull] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}