llvm dev - Aug 2016 - 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.

On Wed, Aug 3, 2016 at 10:16 AM Miguel Aguilar via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160804/a15e9024/attachment.html>

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

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