> LLVM already includes this: the -indvars pass. It turns things likethis:> > 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 isto> 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
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
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 > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-Chris -- http://nondot.org/sabre/ http://llvm.org/
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 > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >
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/
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 >> LLVMdev at cs.uiuc.edu 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 > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >