[llvm-dev] Extracting the names of the variables that creates loop-carried dependencies

[Michael Kruse via llvm-dev]

Hi Miguel,

Polly's DependenceInfo will give you the required information. For
your example the result is

        RAW dependences:
                [A_ROW, B_COL] -> { Stmt_for_body4[i0, i1] ->
Stmt_for_body4[i0, 1 + i1] : 0 <= i0 < A_ROW and 0 <= i1 <= -3 + B_COL
}
        WAR dependences:
                [A_ROW, B_COL] -> {  }
        WAW dependences:
                [A_ROW, B_COL] -> {  }

In this case you see that it is a loop-carried dependency because in
the second dimension the instruction depends on a previous iteration
("i0 -> i0 +1"). You can check this computationally using ISL
operations by subtracting the identity map (dependences within one
iteration) from the dependence map is see whether it is empty.

Dependence can also tell which array/element triggers the dependence
using Dependences::AL_Reference/AL_Access level setting.

For all the statements in a loop, iterate over all dependence, see
whether one dimension is the loop is interested in, compare the
prefixes up to that dimension (to know whether the outermost loops are
within the iteration) and finally again compare the indices of the
dimension you are interested in.

To finally get the array name, extract the ScopArrayInfo object
pointer hidden in the user part of the tuple id.
ScopArrayInfo::getBasePtr() gives you the array's base. For instance,
it will be an llvm::Argument, but could also be any expression that
computes the basepointer, eg. doesn't necessarily have a name from the
source code.

Michael



2016-08-03 19:13 GMT+02:00 Miguel Aguilar via llvm-dev
<llvm-dev at lists.llvm.org>:
> Hi,
>
> I would like to know if it is possible to extract the source level names of
> variables that create loop-carried dependencies.
>
> For example, for the following code:
>
>     for (int i = 0; i < A_ROW; i++)
>     {
>         for (int j = 1; j < B_COL; j++)
>         {
>             a_matrix[i][j] = a_matrix[i][j - 1];
>         }
>     }
>
> I get the following  AST:
>
>       #pragma omp parallel for
>       for (int c0 = 0; c0 <= 31; c0 += 1)
>         #pragma minimal dependence distance: 1
>         for (int c1 = 0; c1 <= 30; c1 += 1)
>           Stmt_for_body5(c0, c1);
>
> As expected the second loop has a dependence distance of 1. Then, here is
> when I would like to know if
> it possible to extract the name of the variable (a_matrix) e.g. by
> developing a custom LLVM pass, based on
> Polly passes.
>
> Thanks,
> Miguel
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev