Data Dependence Graph in Different Compilers - openucx/ucx GitHub Wiki

##Dependency analysis in Open64/OpenUH In Open64/OpenUH compilers, the LNO (Loop Nest Optimizer) has a inter iteration dependence graph for all array statements in the program unit. There is one graph per program unit but edges only exist between two array loads/stores that share at least one common "good" DO loop. Each edge is attached to a dependence vector DEPV_ARRAY. Each load/store of an array WHIRL node is mapped to the vertex in the graph. Non-array loads/stores (i.e. LDIDs/STIDs) can be in the graph, as second class structures, if there is a dependence between an array load/store and an LDID/STID. They are second class citizens in the sense that they only appear in the graph if they are dependent on an array load/store, and there is never any edges between two LDIDs/STIDs.

Example

 for (c = 0; c < m; c++) {
  for (d = 0; d < q; d++) {
    for (k = 0; k < p; k++) {
      sum = sum + first[c][k]*second[k][d];
    }

    multiply[c][d] = sum;
    sum = 0;
  }
}

running

uhcc -O3 -Wb,-ttLNO:0x7 ex-test.c 

will dump the following dependence information:

LNO dependence graph (after transformation)
=======================================================================
Printing an ARRAY_DIRECTED_GRAPH16 of type DEPV_ARRAY 
Vertex 1 for load from Wn = first[1*loop_var0 ][1*loop_var2 ]
Vertex 2 for load from Wn = second[1*loop_var2 ][1*loop_var1 ]
Vertex 3 for store into Wn = multiply[1*loop_var0 ][1*loop_var1 ]

##Dependency analysis in PIPS Using PIPS, we can get the graphical representation of the intra and inter iteration dependences of a loop. Tpips is the line interface and scripting language of the PIPS system. The execution of the necessary passes is obtained by typing their names in the command line interpreter of PIPS, tpips. The listing below shows an example harris.tpips of applying data dependency analysis on a code harris.c and generate it corresponding data dependence graph.

# Create a workspace for the program harris .c
create harris harris .c
apply SEQUENCE_DEPENDENCE_GRAPH [main]
shell dot -Tpng harris.database/main/main_sdg.dot > main_sdg.png
shell gqview main_sdg.png

As an example, the data dependence graph generated by PIPS for the following code is given in the following image:

void main ()
{
    int a[10] , b [10];
    int i,d,c;
    c = 42;
    for(i=1;i <=10; i ++){
        a[i] = 0;
    }
    for(i=1;i <=10; i ++){
        a[i] = bar(a[i]);
        d = foo(c);
        b[i] = a[i]+d;
    }
    return ;
}

##Dependency analysis in LLVM Low Level Virtual Machine (LLVM) is a compiler infrastructure that provides modular and reusable components with a unique multi-stage optimization system for building compilers. It comprises of components that are language and target independent. Note that LLVM is a compiler infrastructure while DragonEgg and Clang are the LLVM Fortran and C front end. LLVM provides analyzes such as call graph and control flow graph in the form of dot files. However, data dependencies and alias analysis are internal analyses and cannot be viewed in a user-friendly format.