[LLVMdev] Graphviz and LLVM-TV

[Török Edwin]

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.

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

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

>
>
> thanks,
> Ioannis
>
>
>
> PS: By the way. How come and you guys are not using Graphviz's library
> API? Avoiding the dependency?
>

Writing out a graph for dot is easy enough to do ;)

Best regards,
--Edwin