3

I need to make data flow graphs for C codes. By data flow graphs I mean graphs in which nodes in the graph represent operations like addition and multiplication, and edges represent operand (data) flow between nodes. My goal is to analyze parallelism and execution time of data flow graphs of compute-intensive kernels. I have used a number of tools to generate data flow graphs from C programs such as Trimaran, Oink, GCC, etc. Among those tools, the Gimple internal representation of GCC provides me with some data flow analysis for each basic block in the SSA (Static Single Assignment) form. the SSA form simplifies my analysis. Here is how I use GCC:

-fdump-tree-cfg generates a control flow graph for each function in which nodes represent basic blocks and edges represent control dependence. The data dependence in each basic block is also shown. However, it does not give a data flow graph for each basic block. I need to visualize the data dependence in order to analyze the data flow in each basic block.

As an example, if you apply -fdump-tree-cfg to the following code

for (i1=0; i1<=N1-N2; i1++)
    for (i2=0; i2<N2; i2++) //N2=31
        y[i1] = y[i1] + w[i2]*x[i1+i2];

you get this:

...
<bb 3>:
  i2 = 0;
  goto <bb 5>;

<bb 4>: //the inner-most loop, where real computation happens
  i1.0 = i1;
  i1.1 = i1;
  D.1608 = y[i1.1];
  i2.2 = i2;
  D.1610 = w[i2.2];
  D.1611 = i1 + i2;
  D.1612 = x[D.1611];
  D.1613 = D.1610 * D.1612;
  D.1614 = D.1608 + D.1613;
  y[i1.0] = D.1614;
  i2 = i2 + 1;

<bb 5>:
  if (i2 <= 31)
    goto <bb 4>;
  else
    goto <bb 6>;
...

-fdump-tree-vcg generates a control flow graph in VCG format, but does not carry any data dependence information.

However, GCC has some limitations. For example, GCC does not generate a visualized data flow graph for each basic block. I was wondering if there is any tools to generate data flow graphs for C programs? Or there might be a GCC plugin to generate data flow graphs from Gimple representation.

PS: The tools should be platform-independent and not limited to a particular architecture. For example, Gimple representation in GCC is architecture-independent.

2

1 Answer 1

2

There is no specific plugin to do so. But you can draw the graphs using "dot". As gimple representation has a specific format you can easily make a parser which takes gimple representation as input and give dot file as output. From dot file you can easily draw graphs. Just do man dot, you will get evrything. Anyway its a nice question.

2
  • I can convert vcg to ps or other formats using dot. But it can only be used for CFG. As you mentioned one could write a parser that takes the gimple representation of each basic block and generates the data flow graph for the basic block. I would hope I could rely on already-developed tools to do so. There are subtle things that makes that parser difficult such as pointer analysis. Thanks for your answer and I'll update my question to make it a little bit more clear.
    – aminfar
    Jul 19, 2012 at 19:01
  • Data flow analysis typically requires a parser as a pre-step to get near the flow facts, but it doesn't make the "parser" difficult. The parser's difficulty is determined solely by the language (and modern C, either MS, GNU, GreenHills, ... are a lot messier than "oh its plain old C" that people seem to think it is). It is true that a points-to analysis is hard to do by itself. You don't want to do this yourself; you'll never get to your actual goal.
    – Ira Baxter
    Jul 19, 2012 at 19:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.