[Attributor] Track AA dependency using dependency graph

[bbn]

Summary

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

[jdoerfert]

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

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

172

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

212

Use DenseMap instead of std::map.

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

llvm/lib/Transforms/IPO/Attributor.cpp

2032

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

1466

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

2935

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

llvm/test/Transforms/Attributor/depgraph.ll

37 ↗

(On Diff #270057)

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

1990

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 ↗

(On Diff #271011)

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

1231

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

850

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

850

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

850

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

850

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

850

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

850

@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

850

@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

850

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

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

[jdoerfert]

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

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

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

183

Nit: no newline
Do we need print here anyway?

195

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

1380

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

1997

const auto &DepAA

Maybe call this, printWithDeps or similar.

2036

Unused?

2052

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

2065

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

2069

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

llvm/test/Transforms/Attributor/depgraph.ll

7 ↗

(On Diff #275312)

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

132 ↗

(On Diff #275312)

(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

1985

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

llvm/lib/Transforms/IPO/Attributor.cpp

2070

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/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"
 
+#include <vector>
+
 namespace llvm {
 
+struct AADepGraphNode;
 struct Attributor;
 struct AbstractAttribute;
 struct InformationCache;
 struct AAIsDead;
 
+class AADepGraph;
 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,
 };
 ///}
 
+/// A node in the Abstract Attribute dependency graph.
+///
+/// Typically represents an abstract attribute in the dependency graph.
+struct AADepGraphNode {
+public:
+  // A pair of the class type and the node that this node depends on
+  using DepRecord = std::pair<DepClassTy, AADepGraphNode *>;
+
+public:
+  using DepAAVector = std::vector<DepRecord>;
+
+  using iterator = std::vector<DepRecord>::iterator;
+
+  inline iterator begin() { return DepAAs.begin(); }
+  inline iterator end() { return DepAAs.end(); }
+
+  AbstractAttribute *NodeAA;
+
+  std::vector<DepRecord> DepAAs;
+
+  friend AADepGraph;
+};
+
+/// The data structure for the dependency graph
+class AADepGraph {
+  using DepMapTy = std::map<AbstractAttribute *, AADepGraphNode *>;
+
+  /// A map from \c AbstractAttribute* to \c AADepGraphNode
+  DepMapTy DepMap;
+
+  // There is no root node for the dependence graph, so we create a root node
+  // that uses every node.
+  AADepGraphNode SyntheticRoot;
+
+public:
+  AADepGraph() { SyntheticRoot.NodeAA = nullptr; }
+
+  using iterator = DepMapTy::iterator;
+
+  iterator begin() { return DepMap.begin(); }
+  iterator end() { return DepMap.end(); }
+  AADepGraphNode *getEntryNode() { return &SyntheticRoot; }
+
+  void viewGraph();
+
+  AADepGraphNode *operator[](AbstractAttribute *AA) {
+    AADepGraphNode *Node = DepMap[AA];
+    // If such node does not already exist in the graph,
+    // we need to add it first
+    if (Node == nullptr) {
+      Node = new AADepGraphNode;
+      Node->NodeAA = AA;
+      DepMap[AA] = Node;
+    }
+
+    SyntheticRoot.DepAAs.push_back(std::make_pair(DepClassTy::OPTIONAL, Node));
+    return Node;
+  }
+};
+
+template <> struct GraphTraits<AADepGraphNode *> {
+  using NodeRef = AADepGraphNode *;
+  using DGNPairTy = AADepGraphNode::DepRecord;
+  using EdgeRef = AADepGraphNode::DepRecord &;
+
+  static NodeRef getEntryNode(AADepGraphNode *DGN) { return DGN; }
+  static AADepGraphNode *DGNGetValue(DGNPairTy P) { return P.second; }
+
+  using ChildIteratorType =
+      mapped_iterator<AADepGraphNode::iterator, decltype(&DGNGetValue)>;
+  using ChildEdgeIteratorType = AADepGraphNode::iterator;
+
+  static ChildIteratorType child_begin(NodeRef N) {
+    return ChildIteratorType(N->begin(), &DGNGetValue);
+  }
+
+  static ChildIteratorType child_end(NodeRef N) {
+    return ChildIteratorType(N->end(), &DGNGetValue);
+  }
+
+  static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
+    return N->begin();
+  }
+
+  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
+};
+
+template <>
+struct GraphTraits<AADepGraph *> : public GraphTraits<AADepGraphNode *> {
+  using PairTy = std::pair<AbstractAttribute *, AADepGraphNode *>;
+
+  static AADepGraphNode *DGGetValuePtr(const PairTy &P) { return P.second; };
+
+  static NodeRef getEntryNode(AADepGraph *DG) { return DG->getEntryNode(); }
+
+  using nodes_iterator =
+      mapped_iterator<AADepGraph::iterator, decltype(&DGGetValuePtr)>;
+
+  static nodes_iterator nodes_begin(AADepGraph *DG) {
+    return nodes_iterator(DG->begin(), &DGGetValuePtr);
+  }
+
+  static nodes_iterator nodes_end(AADepGraph *DG) {
+    return nodes_iterator(DG->end(), &DGGetValuePtr);
+  }
+};
+
 /// Helper to describe and deal with positions in the LLVM-IR.
 ///
 /// A position in the IR is described by an anchor value and an "offset" that
 /// could be the argument number, for call sites and arguments, or an indicator
 /// of the "position kind". The kinds, specified in the Kind enum below, include
 /// the locations in the attribute list, i.a., function scope and return value,
 /// as well as a distinction between call sites and functions. Finally, there
 /// are floating values that do not have a corresponding attribute list
struct Attributor {
   ///
   /// \param Functions The set of functions we are deriving attributes for.
   /// \param InfoCache Cache to hold various information accessible for
   ///                  the abstract attributes.
   /// \param CGUpdater Helper to update an underlying call graph.
   /// \param 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
struct Attributor {
   /// 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;
 
 private:
   /// Check \p Pred on all call sites of \p Fn.
   ///
   /// This method will evaluate \p Pred on call sites and return
   /// true if \p Pred holds in every call sites. However, this is only possible
   /// all call sites are known, hence the function has internal linkage.
   /// If true is returned, \p AllCallSitesKnown is set if all possible call
   /// sites of the function have been visited.
   bool checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred,
                             const Function &Fn, bool RequireAllCallSites,
                             const AbstractAttribute *QueryingAA,
void clear() {
       OptionalAAs.clear();
       RequiredAAs.clear();
     }
   };
   using QueryMapTy = DenseMap<const AbstractAttribute *, QueryMapValueTy *>;
   QueryMapTy QueryMap;
   ///}
 
+  AADepGraph DG;
+
   /// Map to remember all requested signature changes (= argument replacements).
   DenseMap<Function *, SmallVector<ArgumentReplacementInfo *, 8>>
       ArgumentReplacementMap;
 
   /// The set of functions we are deriving attributes for.
   SetVector<Function *> &Functions;
 
   /// The information cache that holds pre-processed (LLVM-IR) information.
   InformationCache &InfoCache;
 
   /// Helper to update an underlying call graph.
   CallGraphUpdater &CGUpdater;
 
   /// Set of functions for which we modified the content such that it might
   /// impact the call graph.
   SmallPtrSet<Function *, 8> CGModifiedFunctions;
 
   /// Set if the attribute currently updated did query a non-fix attribute.
   bool QueriedNonFixAA;
 
   /// If not null, a set limiting the attribute opportunities.
   const DenseSet<const char *> *Whitelist;
 
   /// A set to remember the functions we already assume to be live and visited.

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

 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
 ///       described in the file comment.
 struct AbstractAttribute {
   using StateType = AbstractState;
 
   /// 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) {}
struct AAMemoryLocation
   static AAMemoryLocation &createForPosition(const IRPosition &IRP,
                                              Attributor &A);
 
   /// See AbstractState::getAsStr().
   const std::string getAsStr() const override {
     return getMemoryLocationsAsStr(getAssumedNotAccessedLocation());
   }
 
   /// Unique ID (due to the unique address)
   static const char ID;
 };
 
 /// An abstract interface for range value analysis.
 struct AAValueConstantRange : public IntegerRangeState,
                               public AbstractAttribute,
                               public IRPosition {
   AAValueConstantRange(const IRPosition &IRP, Attributor &A)

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/Statistic.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");
void Attributor::recordDependence(const AbstractAttribute &FromAA,
   if (!DepAAs)
     DepAAs = new (Allocator) QueryMapValueTy();
 
   if (DepClass == DepClassTy::REQUIRED)
     DepAAs->RequiredAAs.insert(const_cast<AbstractAttribute *>(&ToAA));
   else
     DepAAs->OptionalAAs.insert(const_cast<AbstractAttribute *>(&ToAA));
   QueriedNonFixAA = true;
+
+  // record dependence in dep graph
+  DG[const_cast<AbstractAttribute *>(&FromAA)]->DepAAs.push_back(
+      std::make_pair(DepClass, DG[const_cast<AbstractAttribute *>(&ToAA)]));
 }
 
 void Attributor::identifyDefaultAbstractAttributes(Function &F) {
   if (!VisitedFunctions.insert(&F).second)
     return;
   if (F.isDeclaration())
     return;
 

 
 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);
 
   // 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 AADepGraph::viewGraph() { llvm::ViewGraph(this, "CallGraph"); }
+
+template <> struct DOTGraphTraits<AADepGraph *> : public DefaultDOTGraphTraits {
+  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
+
+  static std::string getNodeLabel(const AADepGraphNode *Node,
+                                  const AADepGraph *DG) {
+    std::string AAString = "";
+    raw_string_ostream O(AAString);
+    Node->NodeAA->print(O);
+    return AAString;
+  }
+};
+
 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);
 
   CallGraphUpdater CGUpdater;
   BumpPtrAllocator Allocator;
   InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ nullptr);
   if (runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater)) {
     // FIXME: Think about passes we will preserve and add them here.
     return PreservedAnalyses::none();
   }
   return PreservedAnalyses::all();
 }
 
 PreservedAnalyses AttributorCGSCCPass::run(LazyCallGraph::SCC &C,
                                            CGSCCAnalysisManager &AM,
                                            LazyCallGraph &CG,
                                            CGSCCUpdateResult &UR) {
   FunctionAnalysisManager &FAM =
       AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
   AnalysisGetter AG(FAM);
 
   SetVector<Function *> Functions;
   for (LazyCallGraph::Node &N : C)
     Functions.insert(&N.getFunction());
 
   if (Functions.empty())
     return PreservedAnalyses::all();