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

[Michael Kruse via llvm-dev]

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

2016-08-05 14:25 GMT+02:00 Michael Kruse <llvmdev at meinersbur.de>:
> 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