llvm dev - Aug 2016 - Extracting the names of the variables that creates loop-carried dependencies

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

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

On 08/05/2016 02:32 PM, Michael Kruse wrote:
> 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

2016-08-05 14:42 GMT+02:00 Miguel Aguilar <aguilar at
ice.rwth-aachen.de>:
> What is not clear to me still is how it looks like the code to extract the
> ScopArrayInfo pointer from the user part.
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