Hi, everyone. I've been examining llvm for a while and been duly
impressed. I'd like to contribute in the area of dependence analysis, and a good place to start seems to be in the transformation of pointers to explicit array accesses. Is anyone else working on this? If not, does this seem a plausible place to start and how would be the best way to go about it? Thanks, Naftali _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
On Mon, 18 Jul 2005, Naftali Schwartz wrote:
> Hi, everyone. I've been examining llvm for a while and been duly impressed. > I'd like to contribute in the area of dependence analysis, and a good place > to start seems to be in the transformation of pointers to explicit array > accesses. Is anyone else working on this? If not, does this seem a > plausible place to start and how would be the best way to go about it? LLVM already includes this: the -indvars pass. It turns things like this: int *P = for (...; ... ; ++P) *P to: int *P = ... for (int i = 0; ... ; ++i) P[i] If you're interested in dependence analysis, the next important step is to start analyzing distance and direction vectors. -Chris -- http://nondot.org/sabre/ http://llvm.org/ _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
> LLVM already includes this: the -indvars pass. It turns things like this: > > int *P = for (...; ... ; ++P) > *P > > to: > > int *P = ... > for (int i = 0; ... ; ++i) > P[i] > > If you're interested in dependence analysis, the next important step is to > start analyzing distance and direction vectors. You can check out lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp It uses Alias Analysis and Scalar Evolution to figure out dependences and distances for single dimensional arrays. It needs more work, but its a start. Its not used by anyone currently. I wrote it for my ModuloScheduling work. -Tanya _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
In reply to this post by Naftali Schwartz
Naftali,
Tanya Lattner has already made a start on the dependence analysis itself but is not working on it any more. That is a much bigger project than the pointer-to-array-indexing conversion. If you are interested in picking up on that, we should discuss it (probably offline). There are some algorithmic choices that I think are important here, to combine speed and generality. --Vikram http://www.cs.uiuc.edu/~vadve http://llvm.cs.uiuc.edu/ On Jul 17, 2005, at 11:53 PM, Naftali Schwartz wrote: > Hi, everyone. I've been examining llvm for a while and been duly > impressed. I'd like to contribute in the area of dependence > analysis, and a good place to start seems to be in the > transformation of pointers to explicit array accesses. Is anyone > else working on this? If not, does this seem a plausible place to > start and how would be the best way to go about it? > > Thanks, > Naftali > > _______________________________________________ > LLVM Developers mailing list > [hidden email] http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
In reply to this post by Tanya Lattner-2
On 7/20/05, Tanya Lattner <[hidden email]> wrote:
> > > LLVM already includes this: the -indvars pass. It turns things like this: > > > > int *P = for (...; ... ; ++P) > > *P > > > > to: > > > > int *P = ... > > for (int i = 0; ... ; ++i) > > P[i] > > > > If you're interested in dependence analysis, the next important step is to > > start analyzing distance and direction vectors. > > You can check out > lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp > > It uses Alias Analysis and Scalar Evolution to figure out dependences and > distances for single dimensional arrays. It needs more work, but its a > start. Its not used by anyone currently. I wrote it for my > ModuloScheduling work. > vectors recently and was thinking of giving this a shot in LLVM as well (in my copious spare time). Naftali, if you're interested in working on this, perhaps we could coordinate our efforts. -bw _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
In reply to this post by Naftali Schwartz
> LLVM already includes this: the -indvars pass. It turns things like
this: > > int *P = for (...; ... ; ++P) > *P > > to: > > int *P = ... > for (int i = 0; ... ; ++i) > P[i] > > If you're interested in dependence analysis, the next important step is > start analyzing distance and direction vectors. Well, specifically, I was thinking of a mechanism to turn this: int A[100], B[100], C[100], X, Y, Z; int *p_a = &A[0]; int *p_b = &B[0]; int *p_c = &C[0]; int i, j, k, f; for ( k = 0; k < Z; k++ ) { p_a = &A[0]; for ( i = 0; i < X; i++ ) { p_b = &B[k*Y]; *p_c = *p_a++ * *p_b++; for ( f = 0; f < Y-2; f++ ) *p_c += *p_a++ * *p_b++; *p_c++ += *p_a++ * *p_b++; } } ...into: int A[100], B[100], C[100], X, Y, Z; int i, j, k, f; for ( k = 0; k < Z; k++ ) for ( i = 0; i < X; i++ ) { C[X*k+i] = A[Y*i] * B[Y*k]; for (f = 0; f < Y-2; f++ ) C[X*k+i] += A[Y*i+f+1] * B[Y*k+f+1]; C[X*k+i] += A[Y*i+Y-1] * B[Y*k+Y-1]; } a la Frank and O'Boyle, which -indvars seems not to be able to handle (unless I'm doing something wrong...) Naftali _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
This may sound like a dumb question but for those who do not follow either
:- "why do you want to turn pointers into indexes ?" Aaron _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
In reply to this post by Naftali Schwartz
On Thu, 21 Jul 2005, Naftali Schwartz wrote:
>> If you're interested in dependence analysis, the next important step is > to >> start analyzing distance and direction vectors. > > Well, specifically, I was thinking of a mechanism to turn this: The indvars pass is *intentionally* restricted to only promoting affine expressions to array subscripts, not arbitrary expressions. To enable this, remove the two if's at IndVarSimplify.cpp:647 (unconditionally pushing the discovered indvar on the IndVars list). See the comments in that code for a justification. -Chris > int A[100], B[100], C[100], X, Y, Z; > > int *p_a = &A[0]; > int *p_b = &B[0]; > int *p_c = &C[0]; > > int i, j, k, f; > for ( k = 0; k < Z; k++ ) > { > p_a = &A[0]; > for ( i = 0; i < X; i++ ) > { > p_b = &B[k*Y]; > *p_c = *p_a++ * *p_b++; > for ( f = 0; f < Y-2; f++ ) > *p_c += *p_a++ * *p_b++; > *p_c++ += *p_a++ * *p_b++; > } > } > > ...into: > > int A[100], B[100], C[100], X, Y, Z; > > int i, j, k, f; > for ( k = 0; k < Z; k++ ) > for ( i = 0; i < X; i++ ) > { > C[X*k+i] = A[Y*i] * B[Y*k]; > for (f = 0; f < Y-2; f++ ) > C[X*k+i] += A[Y*i+f+1] * B[Y*k+f+1]; > C[X*k+i] += A[Y*i+Y-1] * B[Y*k+Y-1]; > } > > a la Frank and O'Boyle, which -indvars seems not to be able to handle (unless > I'm doing something wrong...) > > Naftali > > _______________________________________________ > LLVM Developers mailing list > [hidden email] http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > -Chris -- http://nondot.org/sabre/ http://llvm.org/ _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
In reply to this post by AaronNGray
Well, dependence analysis depends on the ability to compare memory
accesses to determine whether or not they may overlap, and under what circumstances such overlap may occur. If all memory referencs are expressed as a displacement from a base, then it becomes trivial to decide whether or not two references may overlap (do they have the same base?) and we can concentrate our symbolic analysis on the question of under what circumstances such overlap may occur. Naftali On Thu, 21 Jul 2005, Aaron Gray wrote: > This may sound like a dumb question but for those who do not follow either :- > > "why do you want to turn pointers into indexes ?" > > Aaron > > _______________________________________________ > LLVM Developers mailing list > [hidden email] http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
In reply to this post by AaronNGray
On Thu, 21 Jul 2005, Aaron Gray wrote:
> This may sound like a dumb question but for those who do not follow either :- > "why do you want to turn pointers into indexes ?" It makes the code far easier to perform dependence analysis on. For example, this code: int A[100]; int *B; for (B = &A[1]; ... ; ++i, ++B) *B = A[i]; If you turn that into: for (; ... ; ++i, ++B) A[i+1] = A[i]; ... it is much easier for analyzers to understand. -Chris -- http://nondot.org/sabre/ http://llvm.org/ _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
In reply to this post by Chris Lattner
OK, I've tried this, and it does convert the p_b's to B[] references. How
would I get this to work for the p_a and p_c references? Naftali On Thu, 21 Jul 2005, Chris Lattner wrote: > On Thu, 21 Jul 2005, Naftali Schwartz wrote: >>> If you're interested in dependence analysis, the next important step is >> to >>> start analyzing distance and direction vectors. >> >> Well, specifically, I was thinking of a mechanism to turn this: > > The indvars pass is *intentionally* restricted to only promoting affine > expressions to array subscripts, not arbitrary expressions. To enable this, > remove the two if's at IndVarSimplify.cpp:647 (unconditionally pushing the > discovered indvar on the IndVars list). > > See the comments in that code for a justification. > > -Chris > >> int A[100], B[100], C[100], X, Y, Z; >> >> int *p_a = &A[0]; >> int *p_b = &B[0]; >> int *p_c = &C[0]; >> >> int i, j, k, f; >> for ( k = 0; k < Z; k++ ) >> { >> p_a = &A[0]; >> for ( i = 0; i < X; i++ ) >> { >> p_b = &B[k*Y]; >> *p_c = *p_a++ * *p_b++; >> for ( f = 0; f < Y-2; f++ ) >> *p_c += *p_a++ * *p_b++; >> *p_c++ += *p_a++ * *p_b++; >> } >> } >> >> ...into: >> >> int A[100], B[100], C[100], X, Y, Z; >> >> int i, j, k, f; >> for ( k = 0; k < Z; k++ ) >> for ( i = 0; i < X; i++ ) >> { >> C[X*k+i] = A[Y*i] * B[Y*k]; >> for (f = 0; f < Y-2; f++ ) >> C[X*k+i] += A[Y*i+f+1] * B[Y*k+f+1]; >> C[X*k+i] += A[Y*i+Y-1] * B[Y*k+Y-1]; >> } >> >> a la Frank and O'Boyle, which -indvars seems not to be able to handle >> (unless I'm doing something wrong...) >> >> Naftali >> >> _______________________________________________ >> LLVM Developers mailing list >> [hidden email] http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> > > -Chris > > -- > http://nondot.org/sabre/ > http://llvm.org/ > > _______________________________________________ > LLVM Developers mailing list > [hidden email] http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > _______________________________________________ LLVM Developers mailing list [hidden email] http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev |
Free forum by Nabble | Edit this page |