This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] Track AA dependency using dependency graph
ClosedPublic

Authored by bbn on Apr 25 2020, 5:19 AM.

Details

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.

Diff Detail

Event Timeline

bbn created this revision.Apr 25 2020, 5:19 AM
Herald added a reviewer: uenoku. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript

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.

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 added a comment.Apr 30 2020, 6:42 PM

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 added a subscriber: kuter.EditedJun 1 2020, 7:10 AM

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.

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 added a comment.Jun 1 2020, 8:07 AM

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 updated this revision to Diff 268998.EditedJun 6 2020, 12:54 AM
bbn retitled this revision from [Attributor] Track AA dependency using dependency graph to [Attributor] [WIP] Track AA dependency using dependency graph.
  • 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

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

kuter added a comment.EditedJun 8 2020, 6:16 PM

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 added a comment.Jun 8 2020, 6:27 PM

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 added a comment.EditedJun 8 2020, 6:34 PM

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:

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 added a comment.Jun 8 2020, 6:43 PM

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 added a comment.EditedJun 8 2020, 6:43 PM

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 updated this revision to Diff 270057.Jun 11 2020, 1:45 AM
  • 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 added a comment.EditedJun 11 2020, 4:04 AM

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

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 updated this revision to Diff 271000.Jun 16 2020, 2:43 AM
  • Use AADepGraphNode for dependence tracking and make AbstractAttribute inherent from it (thanks kuter for the advice)
  • Updated testcase
bbn updated this revision to Diff 271011.Jun 16 2020, 3:17 AM

Added missing comments

kuter added a comment.Jun 16 2020, 3:42 AM
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 added inline comments.Jun 16 2020, 3:42 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
682

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

kuter added a comment.Jun 29 2020, 7:34 PM

Hi can you rebase this.

bbn updated this revision to Diff 274362.EditedJun 30 2020, 1:50 AM
  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 updated this revision to Diff 274381.Jun 30 2020, 2:55 AM
  • Added other 4 lines of test
bbn marked 8 inline comments as done.Jun 30 2020, 2:56 AM
jdoerfert added inline comments.Jul 2 2020, 7:53 AM
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 updated this revision to Diff 275284.Jul 2 2020, 8:58 PM
  • 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 added inline comments.Jul 2 2020, 9:21 PM
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 updated this revision to Diff 275293.Jul 2 2020, 10:19 PM

Move the synthetic node in to the dependency graph

bbn marked an inline comment as done.Jul 2 2020, 10:21 PM
bbn added inline comments.
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 added inline comments.Jul 2 2020, 11:03 PM
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 marked an inline comment as done.Jul 2 2020, 11:44 PM
bbn added inline comments.
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 added inline comments.Jul 3 2020, 12:04 AM
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 added inline comments.Jul 3 2020, 12:45 AM
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 updated this revision to Diff 275312.Jul 3 2020, 12:46 AM

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

bbn added inline comments.Jul 3 2020, 2:16 AM
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 added inline comments.Jul 4 2020, 8:29 AM
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.

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 added a comment.EditedJul 6 2020, 10:09 AM

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 added a comment.Jul 6 2020, 2:48 PM
In D78861#2133485, @bbn 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 updated this revision to Diff 275891.Jul 6 2020, 7:39 PM
  • Added tests for the dot file
  • other style fixes
bbn marked 15 inline comments as done.Jul 6 2020, 7:41 PM
jdoerfert accepted this revision.Jul 7 2020, 5:43 PM

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.

This revision is now accepted and ready to land.Jul 7 2020, 5:43 PM
bbn updated this revision to Diff 276658.Jul 9 2020, 1:26 AM
kuter added a comment.Jul 13 2020, 5:16 PM

Hi @bbn when will commit this ?

bbn updated this revision to Diff 278049.Jul 14 2020, 7:19 PM
This revision was automatically updated to reflect the committed changes.
bbn retitled this revision from [Attributor] [WIP] Track AA dependency using dependency graph to [Attributor] Track AA dependency using dependency graph.Jul 14 2020, 7:33 PM

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

fhahn added a subscriber: fhahn.Jul 19 2020, 3:18 AM

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

bbn updated this revision to Diff 279145.Jul 20 2020, 1:54 AM

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)

bbn reopened this revision.Jul 20 2020, 1:55 AM
This revision is now accepted and ready to land.Jul 20 2020, 1:55 AM
bbn updated this revision to Diff 279146.Jul 20 2020, 1:56 AM
This revision was automatically updated to reflect the committed changes.