the store access function A + N uses a parameter N, and the DependenceAnalysis needs to assume that N % 4 == 0 i.e., the offset N from the base address A aligns with the elements of size i32 in the array, and does not cause partial writes of two consecutive elements in the array A. The runtime predicate N % 4 == 0 is recorded as an assumption in the DependenceInfo. The loop passes that use DependenceAnalysis have been amended to avoid transform when the assumptions are not known at compilation time:
It is possible to handle those loops with a runtime check:
// FIXME: do loop versioning to keep the original loop, and transform the
// loop under the runtime assumptions.
Polly uses a similar technique to version the original scop and the generated code based on the value of the parameters.
It sounds useful to me in some case to allow DependencyAnalysis emitting runtime checks. Let me share a few thoughts.
Your implementation only stores “global” assumptions. I think it’s better to provide a method to get corresponding assumptions for each DVEntry object, e.g., define function like getNecessaryAssumption(unsigned Level) for Dependence. This would be useful for each transformation pass to do its best without versioning. Or it might be enough to distinguish analysis results that require one or more assumptions from those that don’t. However, I also think it’s asking for problems to have the callee side check every time depends method is called to see if DependencyAnalysis required any assumptions. From this perspective, I feel that maybe something like the following API would be better.
// Consider some runtime checks are necessary for Src0 and Dst0, but none are required for Src1 and Dst1.
BeforeDep0 = DI->depends(Src0, Dst0); // Returns conservative value, where an entry implies 'unknown' at all levels.
BeforeDep1 = DI->depends(Src1, Dst1); // We can analyze dependency without any runtime checks.
DI->versioning(); // Tell DependencyAnalysis that all assumptions are satisfied for now.
AfterDep0 = DI->depends(Src0, Dst0); // Dependencies under the assumptions.
AfterDep1 = DI->depends(Src1, Dst1); // Same as BeforeDep1.
There is one more thing that concerns me. When should versioning take place? That is, if multiple passes uses DependencyAnalysis and there are no caches about previous versionings, it can result to generate same runtime checks multiple times? I don’t know much about it, but does LoopAccessAnalysis have similar problem?
I agree, the loop pass may need more flexible ways to find which dependence requires the runtime assumptions. We could also attach the predicates to each Dependence relation.
The interface could be:
Dep = DI->depends(Src0, Dst0, /*underRuntimeAssumptions=*/ true); // Dependencies under the assumptions by default "true".
Dep = DI->depends(Src0, Dst0, false); // Returns conservative value, where an entry implies 'unknown' at all levels.
Assumptions = DI->getRuntimeAssumptions(Src0, Dst0); // return the assumptions for the dependence relation <Src0, Dst0>.
Assumptions = DI->getRuntimeAssumptions(); // return all assumptions for all dependence relations.