[LLVMdev] Graphviz and LLVM-TV

[Ioannis Nousias]

Edwin,

thanks, it starts making sense

inline comments...

Török Edwin wrote:
> On 2009-09-06 19:57, Ioannis Nousias wrote:
>   
>> Edwin,
>>
>> thank you for your effort, but I'm not sure I understand.
>> Are you describing a graph traversal problem? Is the data model stored
>> in a predecessor/successor fashion, which requires you to 'walk' the
>> graph in order to visit all nodes? (and what happens when you have
>> disjointed DFGs?).
>>     
>
> Sorry for the confusion, it was only an example on how to use the
> dataflow graphs from DataFlow.h, you don't need depth-first iteration to
> implement dot graphs for DFGs.
>
> Disjoint DFGs are the reason I mentioned the need to walk all
> instructions/arguments in order to get all DFGs.
> If you are only interested in a DFG starting from a particular Value*,
> then forget about the iteration I mentioned.
>
> I think your fundamental problem was that there is already a Graph for
> Function*, the CFG, and you want a DFG Graph.
>
>   
yes that's right, the CFG is getting in the way

> I think you could do something like this:
> template <typename T>
> class DFG {
> private:
>   T p;
> public:
>   DFG(T t) : p(t) {}
>   T operator*() { return p; }
> };
> template <> struct GraphTraits<DFG<Function*> > : public
> GraphTraits<Value*> {
>   typedef inst_iterator nodes_iterator;
>   static nodes_iterator nodes_begin(DFG<Function *> F) {
>     return inst_begin(*F);
>   }
>   static nodes_iterator nodes_end(DFG<Function *> F) {
>     return inst_end(*F);
>   }
> };
>
> ...
>   ViewGraph(DFG<Function*>(F), "test");
>
> Then you could implement a DOTGraphTraits for DFG<Function*>.
>
>   
ok I'll give it a try.

>> inline comments follow...
>>
>> Török Edwin wrote:
>>     
>>> On 2009-09-06 17:30, Ioannis Nousias wrote:
>>>  
>>>       
>>>> I've tried to write a DFGPrinter based on the CFGPrinter, as you
>>>> suggested, but encountered problems.
>>>>
>>>> The GraphWriter expects
>>>> GraphTraits<GraphType>::nodes_begin()/nodes_end(). The way this is
>>>> implemented in CFG.h, a function is a graph of basic blocks. A
>>>> GraphTraits<Function*>  inherits from GraphTraits<BasicBlock*>, and
>>>> implements those nodes_begin()/nodes_end() wrapper functions. Should
>>>> I modify CFG.h and make now BasicBlock a graph of Instruction(s) ?
>>>>
>>>> The DataFlow.h deals with Value and User. Now BasicBlock is derived
>>>> from Value and Instruction from User, but I don't understand how
>>>> that helps.
>>>>
>>>> It's a bit confusing to be honest. Can you help?
>>>>       
>>>>         
>>> Here are some examples on how to use the dataflow graphs:
>>>
>>> Value *V = ...
>>> for(df_iterator<Value*> UI = df_begin(V), UE = df_end(V); UI != UE;
>>> ++UI) {
>>> ...
>>> }
>>>
>>>
>>> typedef SmallPtrSet<const Value*, 16> SmallValueSet;
>>> SmallValueSet DFSet;
>>> const User* U = ...;
>>> for (idf_ext_iterator<const User*, SmallValueSet> I=idf_ext_begin(U,
>>> DFSet), E=idf_ext_end(U, DFSet); I != E; ++I) {
>>> ..
>>> }
>>>
>>>
>>>   
>>>       
>> I don't understand why I'd need a depth-first iterator.
>>     
>
> It was just an example to show something that uses the GraphTraits from
> DataFlow.h.
>
>   
>>     
>>> There is no common root for the dataflow graph from which you can
>>> enumerate all dataflows, but you could take
>>> each instruction in a function that you're interested in, and output a
>>> dataflow graph rooted at that instruction,
>>> unless that instruction was part of some other dataflow graph already.
>>>
>>>   
>>>       
>> from this I'm getting that you suggest finding all "root" instructions
>> and traverse each chain of instruction (data-flow) separately.
>> Considering that most dataflows are not simple expanding trees, and
>> are instead merging and spliting at several points, I'm not sure what
>> good that would do.
>>     
>
> int foo(int b, int c)
> {
> int a = b+4;
> int z = a+c;
> int y = c+1;
> ..
> }
>
> If you start writing out the dataflow for 'b', then the graph contains
> only 'a' and 'z'. If you start at 'c' the graph will contain only 'z'
> and 'y'.
> This is unlike CFG graphs where the entrypoint in a function is the root
> of the CFG for that function, the DFG graphs are disjoint in this case.
>
>   
>>> Perhaps something like:
>>>
>>> SmallValueSet PrintedSet;
>>> for (Function::arg_iterator I=F.arg_begin(), E=F.arg_end(); I != E;
>>> ++I) {
>>>        if (!PrintedSet.count(*I)) {
>>>              ... print graph rooted at V, add each node printed to
>>> PrintedSet
>>>       }   }
>>> for (inst_iterator I=inst_begin(F), E=inst_end(F); I != E; ++I) {
>>>        if (!PrintedSet.count(*I)) {
>>>              ... print graph rooted at V, add each node printed to
>>> PrintedSet
>>>       }   }
>>>
>>> Best regards,
>>> --Edwin
>>>   
>>>       
>> Most likely I'm missing some information here. There's probably some
>> internal structure, probably how the data-model is build, that
>> requires this sort of traversal. Can you elaborate please.
>>
>> What I'm looking for, to start with, is something rather simple (or at
>> least it should be). A per BasicBlock view of their DFGs. I'm not
>> interested in the inter-BasicBlock connections, for now. I'm tempted
>> to just iterate through the instructions container of each BasicBlock
>> and output the graphviz manually. However, I'd prefer using any
>> facilities present. The way I see it, all I need to do is iterate
>> through the instructions of the BasicBlock, enumerate them to the
>> graphviz data model, then iterate through them once more, checking
>> their predecessor/successor instructions (inputs/outputs), to register
>> their connectivity (edges). Right?
>>     
>
>
> Well the GraphTraits in DataFlow.h are really simple, LLVM's graph
> algorithms expect
> a child_begin()/child_end(), so DataFlow.h only maps
> child_begin/child_end to use_begin/use_end, and op_begin/op_end for the
> Def-Use, and Use-Def graphs respectively.
> That however doesn't know of any basicblock boundaries, it enumerates
> *all* uses of a value, so I think that writing out a full DFG is easier
> than writing out a partial one.
>
>   
ok I see


thanks,
Ioannis