Add a new pass "Loop Interchange"
This pass interchanges loops to provide a more cache-friendly memory access.
For e.g. given a loop like -
for(int i=0;i<N;i++) for(int j=0;j<N;j++) A[j][i] = A[j][i]+B[j][i];
is interchanged to -
for(int j=0;j<N;j++) for(int i=0;i<N;i++) A[j][i] = A[j][i]+B[j][i];
This pass is currently disabled by default.
To give a brief introduction it consists of 3 stages-
LoopInterchangeLegality : Checks the legality of loop interchange based on Dependency matrix.
LoopInterchangeProfitability: A very basic heuristic has been added to check for profitibility. This will evolve over time.
LoopInterchangeTransform : Which does the actual transform.
LNT Performance tests shows improvement in Polybench/linear-algebra/kernels/mvt and Polybench/linear-algebra/kernels/gemver becnmarks.
- Add support for reductions and lcssa phi.
- Improve profitability model.
- Improve loop selection algorithm to select best loop for interchange. Currently the innermost loop is selected for interchange.
- Improve compile time regression found in llvm lnt due to this pass.
- Fix issues in Dependency Analysis module.
A special thanks to Hal for reviewing this code.