[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

171

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.

211

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

2130

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

1520

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 :)

3008

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

2060

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

682

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

1264

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

860

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

860

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

860

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

860

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

860

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

860

@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

860

@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

860

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

182

Nit: no newline
Do we need print here anyway?

194

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

1417

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

2067

const auto &DepAA

Maybe call this, printWithDeps or similar.

2134

Unused?

2150

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

2163

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).

2167

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

llvm/test/Transforms/Attributor/depgraph.ll

8

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

133

(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

2070

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

llvm/lib/Transforms/IPO/Attributor.cpp

2168

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/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:
+  enum NodeKind { NK_AA, NK_SN };
+
+  AADepGraphNode(NodeKind K) : NKind(K) {}
+  virtual ~AADepGraphNode(){};
+
+private:
+  const NodeKind NKind;
+
+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(); }
+
+public:
+  using iterator =
+      mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
+
+  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; }
+
+  NodeKind getKind() const { return NKind; }
+
+  friend struct Attributor;
+};
+
 /// 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
 /// position.
 struct IRPosition {
 
   /// The positions we distinguish in the IR.
   enum Kind : char {
     IRP_INVALID,  ///< An invalid position.
     IRP_FLOAT,    ///< A position that is not associated with a spot suitable
                   ///< for attributes. This could be any value or instruction.
     IRP_RETURNED, ///< An attribute for the function return value.
     IRP_CALL_SITE_RETURNED, ///< An attribute for a call site return value.
     IRP_FUNCTION,           ///< An attribute for a function (scope).
     IRP_CALL_SITE,          ///< An attribute for a call site (function scope).
     IRP_ARGUMENT,           ///< An attribute for a function argument.
     IRP_CALL_SITE_ARGUMENT, ///< An attribute for a call site argument.
   };
 
   /// Default constructor available to create invalid positions implicitly. All
   /// other positions need to be created explicitly through the appropriate
   /// static member function.
   IRPosition() : Enc(nullptr, ENC_VALUE) { verify(); }
 
   /// Create a position describing the value of \p V.
   static const IRPosition value(const Value &V) {
     if (auto *Arg = dyn_cast<Argument>(&V))
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 Whitelist If not null, a set limiting the attribute opportunities.
   Attributor(SetVector<Function *> &Functions, InformationCache &InfoCache,
              CallGraphUpdater &CGUpdater,
              DenseSet<const char *> *Whitelist = nullptr)
       : Allocator(InfoCache.Allocator), Functions(Functions),
         InfoCache(InfoCache), CGUpdater(CGUpdater), Whitelist(Whitelist) {}
 
   ~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) {
     // 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);
+    SymDGN->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 {
   /// Check \p Pred on all Read/Write instructions.
   ///
   /// This method will evaluate \p Pred on all instructions that read or write
   /// 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);
 
+  /// Print All dependencies for every AbstractAttribute in the AA list
+  /// For debug use only.
+  void printAllDependency(raw_ostream &);
+
   /// Return the data layout associated with the anchor scope.
   const DataLayout &getDataLayout() const { return InfoCache.DL; }
 
   /// The allocator used to allocate memory, e.g. for `AbstractAttribute`s.
   BumpPtrAllocator &Allocator;
 
+  AADepGraph *DG;
+
+  AADepGraphNode *SymDGN;
+
 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();
private:
   /// The information cache that holds pre-processed (LLVM-IR) information.
   InformationCache &InfoCache;
 
   /// Helper to update an underlying call graph.
   CallGraphUpdater &CGUpdater;
 
   /// 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;
     const AbstractAttribute *ToAA;
     DepClassTy DepClass;
   };
private:
   SmallVector<WeakVH, 16> InvokeWithDeadSuccessor;
 
   /// 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)
struct AbstractState {
   ///
   /// This will usually revert the optimistically assumed state to the known to
   /// be true state.
   ///
   /// \returns ChangeStatus::CHANGED as the assumed value may change.
   virtual ChangeStatus indicatePessimisticFixpoint() = 0;
 };
 
+/// The data structure for the dependency graph
+struct AADepGraph {
+  AADepGraph(Attributor &A) : A(A) {}
+  ~AADepGraph() {}
+
+  using DepTy = PointerIntPair<AADepGraphNode *, 1>;
+  static AADepGraphNode *DepGetVal(DepTy &DT) { return DT.getPointer(); }
+  using iterator =
+      mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
+
+  Attributor &A;
+
+  // FIXME
+  AADepGraphNode *GetEntryNode() const { return A.SymDGN; }
+
+  iterator begin() { return A.SymDGN->child_begin(); }
+  iterator end() { return A.SymDGN->child_end(); }
+
+  void viewGraph();
+
+  /// Dump graph to file
+  void dumpGraph();
+
+  /// Print dependency graph
+  void print();
+};
+
 /// Simple state with integers encoding.
 ///
 /// The interface ensures that the assumed bits are always a subset of the known
 /// 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

 ///       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) {}
+  AbstractAttribute(const IRPosition &IRP)
+      : IRPosition(IRP), AADepGraphNode(NK_AA) {}
 
   /// Virtual destructor.
   virtual ~AbstractAttribute() {}
 
   /// 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 corrsponding IR attribute name
+  virtual const std::string getName() const = 0;
   ///}
 
+  static bool classof(const AADepGraphNode *DGN) {
+    return DGN->getKind() == NK_AA;
+  }
+
   /// Allow the Attributor access to the protected methods.
   friend struct Attributor;
 
 protected:
   /// Hook for the Attributor to trigger an update of the internal state.
   ///
   /// If this attribute is already fixed, this method will return UNCHANGED,
   /// otherwise it delegates to `AbstractAttribute::updateImpl`.
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
     : public StateWrapper<IntegerRangeState, AbstractAttribute, uint32_t> {
   using Base = StateWrapper<IntegerRangeState, AbstractAttribute, uint32_t>;

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/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;
for (unsigned u = 0; u < InvalidAAs.size(); ++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 =
+            dyn_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(
+            dyn_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 (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(
+          dyn_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 (NumFinalAAs != AllAbstractAttributes.size()) {
     llvm_unreachable("Expected the final number of abstract attributes to "
                      "remain unchanged!");
   }
   return ManifestChange;
 }
 
 ChangeStatus Attributor::cleanupIR() {
   // Delete stuff at the end to avoid invalid references and a nice order.
-    LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least "
-                      << ToBeDeletedFunctions.size() << " functions and "
-                      << ToBeDeletedBlocks.size() << " blocks and "
-                      << ToBeDeletedInsts.size() << " instructions and "
-                      << ToBeChangedUses.size() << " uses\n");
 
-    SmallVector<WeakTrackingVH, 32> DeadInsts;
-    SmallVector<Instruction *, 32> TerminatorsToFold;
 
-    for (auto &It : ToBeChangedUses) {
-      Use *U = It.first;
-      Value *NewV = It.second;
-      Value *OldV = U->get();
 
-      // Do not replace uses in returns if the value is a must-tail call we will
-      // not delete.
-      if (isa<ReturnInst>(U->getUser()))
-        if (auto *CI = dyn_cast<CallInst>(OldV->stripPointerCasts()))
-          if (CI->isMustTailCall() && !ToBeDeletedInsts.count(CI))
-            continue;
 
-      LLVM_DEBUG(dbgs() << "Use " << *NewV << " in " << *U->getUser()
-                        << " instead of " << *OldV << "\n");
-      U->set(NewV);
-      // Do not modify call instructions outside the SCC.
-      if (auto *CB = dyn_cast<CallBase>(OldV))
-        if (!Functions.count(CB->getCaller()))
-          continue;
-      if (Instruction *I = dyn_cast<Instruction>(OldV)) {
-        CGModifiedFunctions.insert(I->getFunction());
-        if (!isa<PHINode>(I) && !ToBeDeletedInsts.count(I) &&
-            isInstructionTriviallyDead(I))
-          DeadInsts.push_back(I);
-      }
-      if (isa<Constant>(NewV) && isa<BranchInst>(U->getUser())) {
-        Instruction *UserI = cast<Instruction>(U->getUser());
-        if (isa<UndefValue>(NewV)) {
-          ToBeChangedToUnreachableInsts.insert(UserI);
-        } else {
-          TerminatorsToFold.push_back(UserI);
-        }
-      }
-    }
-    for (auto &V : InvokeWithDeadSuccessor)
-      if (InvokeInst *II = dyn_cast_or_null<InvokeInst>(V)) {
-        bool UnwindBBIsDead = II->hasFnAttr(Attribute::NoUnwind);
-        bool NormalBBIsDead = II->hasFnAttr(Attribute::NoReturn);
-        bool Invoke2CallAllowed =
-            !AAIsDead::mayCatchAsynchronousExceptions(*II->getFunction());
-        assert((UnwindBBIsDead || NormalBBIsDead) &&
-               "Invoke does not have dead successors!");
-        BasicBlock *BB = II->getParent();
-        BasicBlock *NormalDestBB = II->getNormalDest();
-        if (UnwindBBIsDead) {
-          Instruction *NormalNextIP = &NormalDestBB->front();
-          if (Invoke2CallAllowed) {
-            changeToCall(II);
-            NormalNextIP = BB->getTerminator();
-          }
-          if (NormalBBIsDead)
-            ToBeChangedToUnreachableInsts.insert(NormalNextIP);
-        } else {
-          assert(NormalBBIsDead && "Broken invariant!");
-          if (!NormalDestBB->getUniquePredecessor())
-            NormalDestBB = SplitBlockPredecessors(NormalDestBB, {BB}, ".dead");
-          ToBeChangedToUnreachableInsts.insert(&NormalDestBB->front());
-        }
-      }
-    for (Instruction *I : TerminatorsToFold) {
-      CGModifiedFunctions.insert(I->getFunction());
-      ConstantFoldTerminator(I->getParent());
-    }
-    for (auto &V : ToBeChangedToUnreachableInsts)
-      if (Instruction *I = dyn_cast_or_null<Instruction>(V)) {
-        CGModifiedFunctions.insert(I->getFunction());
-        changeToUnreachable(I, /* UseLLVMTrap */ false);
-      }
 
-    for (auto &V : ToBeDeletedInsts) {
-      if (Instruction *I = dyn_cast_or_null<Instruction>(V)) {
-        I->dropDroppableUses();
-        CGModifiedFunctions.insert(I->getFunction());
-        if (!I->getType()->isVoidTy())
-          I->replaceAllUsesWith(UndefValue::get(I->getType()));
-        if (!isa<PHINode>(I) && isInstructionTriviallyDead(I))
-          DeadInsts.push_back(I);
-        else
-          I->eraseFromParent();
-      }
-    }
 
-    RecursivelyDeleteTriviallyDeadInstructions(DeadInsts);
 
-    if (unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) {
-      SmallVector<BasicBlock *, 8> ToBeDeletedBBs;
-      ToBeDeletedBBs.reserve(NumDeadBlocks);
-      for (BasicBlock *BB : ToBeDeletedBlocks) {
-        CGModifiedFunctions.insert(BB->getParent());
-        ToBeDeletedBBs.push_back(BB);
-      }
-      // Actually we do not delete the blocks but squash them into a single
-      // unreachable but untangling branches that jump here is something we need
-      // to do in a more generic way.
-      DetatchDeadBlocks(ToBeDeletedBBs, nullptr);
-    }
 
-    // Identify dead internal functions and delete them. This happens outside
-    // the other fixpoint analysis as we might treat potentially dead functions
-    // as live to lower the number of iterations. If they happen to be dead, the
-    // below fixpoint loop will identify and eliminate them.
-    SmallVector<Function *, 8> InternalFns;
-    for (Function *F : Functions)
-      if (F->hasLocalLinkage())
-        InternalFns.push_back(F);
 
-    bool FoundDeadFn = true;
-    while (FoundDeadFn) {
-      FoundDeadFn = false;
-      for (unsigned u = 0, e = InternalFns.size(); u < e; ++u) {
-        Function *F = InternalFns[u];
-        if (!F)
-          continue;
 
-        bool AllCallSitesKnown;
-        if (!checkForAllCallSites(
-                [this](AbstractCallSite ACS) {
-                  return ToBeDeletedFunctions.count(
-                      ACS.getInstruction()->getFunction());
-                },
-                *F, true, nullptr, AllCallSitesKnown))
-          continue;
 
-        ToBeDeletedFunctions.insert(F);
-        InternalFns[u] = nullptr;
-        FoundDeadFn = true;
-      }
-    }
 
   // Rewrite the functions as requested during manifest.
-    ChangeStatus ManifestChange =
-        rewriteFunctionSignatures(CGModifiedFunctions);
+  ChangeStatus ManifestChange = rewriteFunctionSignatures(CGModifiedFunctions);
 
-    for (Function *Fn : CGModifiedFunctions)
-      CGUpdater.reanalyzeFunction(*Fn);
 
-    for (Function *Fn : ToBeDeletedFunctions)
-      CGUpdater.removeFunction(*Fn);
 
-    NumFnDeleted += ToBeDeletedFunctions.size();
 
 #ifdef EXPENSIVE_CHECKS
   for (Function *F : Functions) {
     if (ToBeDeletedFunctions.count(F))
       continue;
     assert(!verifyFunction(*F, &errs()) && "Module verification failed!");
   }
 #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 << "  depends on ";
+    AA->print(OS);
+  }
+
+  OS << '\n';
 }
 ///}
 
 /// ----------------------------------------------------------------------------
 ///                       Pass (Manager) Boilerplate
 /// ----------------------------------------------------------------------------
 
 static bool runAttributorOnFunctions(InformationCache &InfoCache,
                                      SetVector<Function *> &Functions,
                                      AnalysisGetter &AG,
                                      CallGraphUpdater &CGUpdater) {
   if (Functions.empty())
     return false;
 
   LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << Functions.size()
                     << " functions.\n");
 
   // Create an Attributor and initially empty information cache that is filled
   // while we identify default attribute opportunities.
   Attributor A(Functions, InfoCache, CGUpdater);
 
+  A.DG = new AADepGraph(A);
+  A.SymDGN = new AADepGraphNode(AADepGraphNode::NK_SN);
+
   // Create shallow wrappers for all functions that are not IPO amendable
   if (AllowShallowWrappers)
     for (Function *F : Functions)
       if (!A.isFunctionIPOAmendable(*F))
         createShallowWrapper(*F);
 
   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 (AbstractAttribute *AA : AllAbstractAttributes) {
+    AA->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(A.AllAbstractAttributes.size());
+
+  for (auto tAA : A.AllAbstractAttributes) {
+    AAs.push_back(tAA);
+  }
+
+  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 llvm::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 llvm::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 llvm::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::getName()
+  const std::string getName() const override { return "AANoUnwind"; }
+
   /// 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) {
public:
   /// See AbstractState::checkForAllReturnedValues(...).
   bool checkForAllReturnedValuesAndReturnInsts(
       function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred)
       const override;
 
   /// Pretty print the attribute similar to the IR representation.
   const std::string getAsStr() const override;
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAReturnedValues"; }
+
   /// See AbstractState::isAtFixpoint().
   bool isAtFixpoint() const override { return IsFixed; }
 
   /// See AbstractState::isValidState().
   bool isValidState() const override { return IsValidState; }
 
   /// See AbstractState::indicateOptimisticFixpoint(...).
   ChangeStatus indicateOptimisticFixpoint() override {
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);

 
 struct AANoSyncImpl : AANoSync {
   AANoSyncImpl(const IRPosition &IRP, Attributor &A) : AANoSync(IRP, A) {}
 
   const std::string getAsStr() const override {
     return getAssumed() ? "nosync" : "may-sync";
   }
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AANoSync"; }
+
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override;
 
   /// Helper function used to determine whether an instruction is non-relaxed
   /// atomic. In other words, if an atomic instruction does not have unordered
   /// or monotonic ordering
   static bool isNonRelaxedAtomic(Instruction *I);
 
if (!A.checkForAllCallLikeInstructions(CheckForNoFree, *this))
       return indicatePessimisticFixpoint();
     return ChangeStatus::UNCHANGED;
   }
 
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
     return getAssumed() ? "nofree" : "may-free";
   }
+
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AANoFree"; }
 };
 
 struct AANoFreeFunction final : public AANoFreeImpl {
   AANoFreeFunction(const IRPosition &IRP, Attributor &A)
       : AANoFreeImpl(IRP, A) {}
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nofree) }
bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I,
     return TrackUse;
   }
 
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
     return getAssumed() ? "nonnull" : "may-null";
   }
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AANonNull"; }
+
   /// Flag to determine if the underlying value can be null and still allow
   /// valid accesses.
   const bool NullIsDefined;
 };
 
 /// NonNull attribute for a floating value.
 struct AANonNullFloating : public AANonNullImpl {
   AANonNullFloating(const IRPosition &IRP, Attributor &A)

 
 struct AANoRecurseImpl : public AANoRecurse {
   AANoRecurseImpl(const IRPosition &IRP, Attributor &A) : AANoRecurse(IRP, A) {}
 
   /// See AbstractAttribute::getAsStr()
   const std::string getAsStr() const override {
     return getAssumed() ? "norecurse" : "may-recurse";
   }
+
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AANoRecurse"; }
 };
 
 struct AANoRecurseFunction final : AANoRecurseImpl {
   AANoRecurseFunction(const IRPosition &IRP, Attributor &A)
       : AANoRecurseImpl(IRP, A) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
ChangeStatus manifest(Attributor &A) override {
     return ChangeStatus::CHANGED;
   }
 
   /// See AbstractAttribute::getAsStr()
   const std::string getAsStr() const override {
     return getAssumed() ? "undefined-behavior" : "no-ub";
   }
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAUndefinedBehavior"; }
+
   /// Note: The correctness of this analysis depends on the fact that the
   /// following 2 sets will stop changing after some point.
   /// "Change" here means that their size changes.
   /// The size of each set is monotonically increasing
   /// (we only add items to them) and it is upper bounded by the number of
   /// instructions in the processed function (we can never save more
   /// elements in either set than this number). Hence, at some point,
   /// they will stop increasing.
ChangeStatus updateImpl(Attributor &A) override {
 
     return ChangeStatus::UNCHANGED;
   }
 
   /// See AbstractAttribute::getAsStr()
   const std::string getAsStr() const override {
     return getAssumed() ? "willreturn" : "may-noreturn";
   }
+
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAWillReturn"; }
 };
 
 struct AAWillReturnFunction final : AAWillReturnImpl {
   AAWillReturnFunction(const IRPosition &IRP, Attributor &A)
       : AAWillReturnImpl(IRP, A) {}
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(willreturn) }
struct AAReachabilityImpl : AAReachability {
   AAReachabilityImpl(const IRPosition &IRP, Attributor &A)
       : AAReachability(IRP, A) {}
 
   const std::string getAsStr() const override {
     // TODO: Return the number of reachable queries.
     return "reachable";
   }
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAReachability"; }
+
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override { indicatePessimisticFixpoint(); }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     return indicatePessimisticFixpoint();
   }
 };
struct AANoAliasImpl : AANoAlias {
   AANoAliasImpl(const IRPosition &IRP, Attributor &A) : AANoAlias(IRP, A) {
     assert(getAssociatedType()->isPointerTy() &&
            "Noalias is a pointer attribute");
   }
 
   const std::string getAsStr() const override {
     return getAssumed() ? "noalias" : "may-alias";
   }
+
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AANoAlias"; }
 };
 
 /// NoAlias attribute for a floating value.
 struct AANoAliasFloating final : AANoAliasImpl {
   AANoAliasFloating(const IRPosition &IRP, Attributor &A)
       : AANoAliasImpl(IRP, A) {}
 
   /// See AbstractAttribute::initialize(...).
bool isKnownDead(const Instruction *I) const override {
     return isAssumedDead(I) && getKnown();
   }
 
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
     return isAssumedDead() ? "assumed-dead" : "assumed-live";
   }
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAIsDeadValue"; }
+
   /// Check if all uses are assumed dead.
   bool areAllUsesAssumedDead(Attributor &A, Value &V) {
     auto UsePred = [&](const Use &U, bool &Follow) { return false; };
     // Explicitly set the dependence class to required because we want a long
     // chain of N dependent instructions to be considered live as soon as one is
     // without going through N update cycles. This is not required for
     // correctness.
     return A.checkForAllUses(UsePred, *this, V, DepClassTy::REQUIRED);
struct AAIsDeadCallSiteReturned : public AAIsDeadFloating {
 
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
     return isAssumedDead()
                ? "assumed-dead"
                : (getAssumed() ? "assumed-dead-users" : "assumed-live");
   }
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override {
+    return "AAIsDeadCallSiteReturned";
+  }
+
 private:
   bool IsAssumedSideEffectFree;
 };
 
 struct AAIsDeadReturned : public AAIsDeadValueImpl {
   AAIsDeadReturned(const IRPosition &IRP, Attributor &A)
       : AAIsDeadValueImpl(IRP, A) {}
 
struct AAIsDeadFunction : public AAIsDead {
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
     return "Live[#BB " + std::to_string(AssumedLiveBlocks.size()) + "/" +
            std::to_string(getAnchorScope()->size()) + "][#TBEP " +
            std::to_string(ToBeExploredFrom.size()) + "][#KDE " +
            std::to_string(KnownDeadEnds.size()) + "]";
   }
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAIsDeadFunction"; }
+
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     assert(getState().isValidState() &&
            "Attempted to manifest an invalid state!");
 
     ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
     Function &F = *getAnchorScope();
 
const std::string getAsStr() const override {
     if (!getAssumedDereferenceableBytes())
       return "unknown-dereferenceable";
     return std::string("dereferenceable") +
            (isAssumedNonNull() ? "" : "_or_null") +
            (isAssumedGlobal() ? "_globally" : "") + "<" +
            std::to_string(getKnownDereferenceableBytes()) + "-" +
            std::to_string(getAssumedDereferenceableBytes()) + ">";
   }
+
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AADereferenceable"; }
 };
 
 /// Dereferenceable attribute for a floating value.
 struct AADereferenceableFloating : AADereferenceableImpl {
   AADereferenceableFloating(const IRPosition &IRP, Attributor &A)
       : AADereferenceableImpl(IRP, A) {}
 
   /// See AbstractAttribute::updateImpl(...).
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(
struct AAAlignImpl : AAAlign {
   }
 
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
     return getAssumedAlign() ? ("align<" + std::to_string(getKnownAlign()) +
                                 "-" + std::to_string(getAssumedAlign()) + ">")
                              : "unknown-align";
   }
+
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAAlign"; }
 };
 
 /// Align attribute for a floating value.
 struct AAAlignFloating : AAAlignImpl {
   AAAlignFloating(const IRPosition &IRP, Attributor &A) : AAAlignImpl(IRP, A) {}
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
if (!F)
       indicatePessimisticFixpoint();
   }
 
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
     return getAssumed() ? "noreturn" : "may-return";
   }
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AANoReturn"; }
+
   /// See AbstractAttribute::updateImpl(Attributor &A).
   virtual ChangeStatus updateImpl(Attributor &A) override {
     auto CheckForNoReturn = [](Instruction &) { return false; };
     if (!A.checkForAllInstructions(CheckForNoReturn, *this,
                                    {(unsigned)Instruction::Ret}))
       return indicatePessimisticFixpoint();
     return ChangeStatus::UNCHANGED;
   }
const std::string getAsStr() const override {
     if (isAssumedNoCapture())
       return "assumed not-captured";
     if (isKnownNoCaptureMaybeReturned())
       return "known not-captured-maybe-returned";
     if (isAssumedNoCaptureMaybeReturned())
       return "assumed not-captured-maybe-returned";
     return "assumed-captured";
   }
+
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AANoCapture"; }
 };
 
 /// Attributor-aware capture tracker.
 struct AACaptureUseTracker final : public CaptureTracker {
 
   /// Create a capture tracker that can lookup in-flight abstract attributes
   /// through the Attributor \p A.
   ///
struct AAValueSimplifyImpl : AAValueSimplify {
   }
 
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
     return getAssumed() ? (getKnown() ? "simplified" : "maybe-simple")
                         : "not-simple";
   }
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAValueSimplify"; }
+
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {}
 
   /// See AAValueSimplify::getAssumedSimplifiedValue()
   Optional<Value *> getAssumedSimplifiedValue(Attributor &A) const override {
     if (!getAssumed())
       return const_cast<Value *>(&getAssociatedValue());
     return SimplifiedAssociatedValue;

 struct AAHeapToStackImpl : public AAHeapToStack {
   AAHeapToStackImpl(const IRPosition &IRP, Attributor &A)
       : AAHeapToStack(IRP, A) {}
 
   const std::string getAsStr() const override {
     return "[H2S] Mallocs: " + std::to_string(MallocCalls.size());
   }
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAHeapToStack"; }
+
   ChangeStatus manifest(Attributor &A) override {
     assert(getState().isValidState() &&
            "Attempted to manifest an invalid state!");
 
     ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
     Function *F = getAnchorScope();
     const auto *TLI = A.getInfoCache().getTargetLibraryInfoForFunction(*F);
 
struct AAPrivatizablePtrImpl : public AAPrivatizablePtr {
   Optional<Type *> getPrivatizableType() const override {
     return PrivatizableType;
   }
 
   const std::string getAsStr() const override {
     return isAssumedPrivatizablePtr() ? "[priv]" : "[no-priv]";
   }
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAPrivatizablePtr"; }
+
 protected:
   Optional<Type *> PrivatizableType;
 };
 
 // TODO: Do this for call site arguments (probably also other values) as well.
 
 struct AAPrivatizablePtrArgument final : public AAPrivatizablePtrImpl {
   AAPrivatizablePtrArgument(const IRPosition &IRP, Attributor &A)
if (isAssumedReadNone())
       return "readnone";
     if (isAssumedReadOnly())
       return "readonly";
     if (isAssumedWriteOnly())
       return "writeonly";
     return "may-read/write";
   }
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAMemoryBehavior"; }
+
   /// The set of IR attributes AAMemoryBehavior deals with.
   static const Attribute::AttrKind AttrKinds[3];
 };
 
 const Attribute::AttrKind AAMemoryBehaviorImpl::AttrKinds[] = {
     Attribute::ReadNone, Attribute::ReadOnly, Attribute::WriteOnly};
 
 /// Memory behavior attribute for a floating value.
const std::string getAsStr() const override {
     OS << "range(" << getBitWidth() << ")<";
     getKnown().print(OS);
     OS << " / ";
     getAssumed().print(OS);
     OS << ">";
     return OS.str();
   }
 
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAValueConstantRange"; }
+
   /// Helper function to get a SCEV expr for the associated value at program
   /// point \p I.
   const SCEV *getSCEV(Attributor &A, const Instruction *I = nullptr) const {
     if (!getAnchorScope())
       return nullptr;
 
     ScalarEvolution *SE =
         A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>(

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=3 -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=3 -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
+
+; 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) {
+  %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
+}
+
+;
+; AAAlign
+;
+
+; CHECK: [AAAlign] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+; CHECK:  depends on [AAAlign] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
+
+; CHECK: [AAAlign] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
+; CHECK:  depends on [AAAlign] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+; CHECK:  depends on [AAAlign] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+
+; CHECK: [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+; CHECK:  depends on [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+; CHECK:  depends on [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+
+; CHECK: [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AAMemoryBehavior] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AAMemoryBehavior] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+
+; CHECK: [AAMemoryLocation] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AAMemoryLocation] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+
+; CHECK: [AAMemoryLocation] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+; CHECK:  depends on [AAMemoryLocation] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AAMemoryLocation] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+
+; CHECK: [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+
+; CHECK: [AANoCapture] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+
+; CHECK: [AANoFree] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+
+; CHECK: [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoFree] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+
+; CHECK: [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+; CHECK:  depends on [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoFree] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoFree] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AANoFree] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+
+; CHECK: [AANoSync] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+; CHECK:  depends on [AANoSync] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AANoSync] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+
+; CHECK: [AANoSync] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AANoSync] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+
+; CHECK: [AANoUnwind] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AAIsDeadCallSiteReturned] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+; CHECK:  depends on [AAIsDeadCallSiteReturned] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+; CHECK:  depends on [AANoUnwind] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+
+; CHECK: [AANoUnwind] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn:checkAndAdvance [checkAndAdvance@-1]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoUnwind] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AANoUnwind] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AANoUnwind] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs: [@-1]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+; CHECK:  depends on [AANoCapture] for CtxI '  %2 = load i32, i32* %0, align 4' at position {arg: [@0]}
+
+; CHECK: [AANonNull] for CtxI '  %5 = getelementptr inbounds i32, i32* %0, i64 4' at position {flt: [@-1]}
+; CHECK:  depends on [AANonNull] for CtxI '  %5 = getelementptr inbounds i32, i32* %0, i64 4' at position {flt: [@-1]}
+; CHECK:  depends on [AANonNull] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_arg: [@0]}
+; CHECK:  depends on [AANonNull] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
+; CHECK:  depends on [AANonNull] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
+
+; CHECK: [AANonNull] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+; CHECK:  depends on [AANonNull] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
+
+; CHECK: [AANonNull] for CtxI '  %2 = load i32, i32* %0, align 4' at position {fn_ret:checkAndAdvance [checkAndAdvance@-1]}
+; CHECK:  depends on [AANonNull] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}
+; CHECK:  depends on [AANonNull] for CtxI '  %6 = call i32* @checkAndAdvance(i32* %5)' at position {cs_ret: [@-1]}