Extracting the names of the variables that creates loop-carried dependencies

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

Extracting things like variable names can be done in a best-effort basis by examining debug info metadata/intrinsics in the LLVM IR - but, as I said, it’s totally best-effort (which is really “not much effort” when it comes to optimized code) so it may not be present, accurate, etc.

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

I just realized this is a crossposting llvm-dev/polly-dev. It has
already been answered on the polly-dev side. Sorry for the redundant
answer.

Michael

Hi Michael,

Thanks for your answer. Checking the indexes looks as an another
straightforward approach to identify the actual loop-carried dependencies.

What is not clear to me still is how it looks like the code to extract the
ScopArrayInfo pointer from the user part.

Miguel

isl_union_map RAW; // The flow dependence map of format { Stmt -> Stmt }
// foreach Map in RAW:
isl_id *Id = isl_map_get_tuple_id(Map);
ScopArrayInfo *SAI = (ScopArrayInfo*)isl_id_get_user(Id);

This one is for if you are using Dependences::AL_Reference.

Michael