Michael Kruse via llvm-dev
2016-Aug-05 12:32 UTC
[llvm-dev] 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
Miguel Aguilar via llvm-dev
2016-Aug-05 12:42 UTC
[llvm-dev] Extracting the names of the variables that creates loop-carried dependencies
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
Michael Kruse via llvm-dev
2016-Aug-05 12:56 UTC
[llvm-dev] Extracting the names of the variables that creates loop-carried dependencies
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