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

[Miguel Aguilar via 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