[llvm-dev] [Proposal][RFC] Cache aware Loop Cost Analysis

Vikram TV via llvm-dev llvm-dev at lists.llvm.org
Wed Jun 8 00:58:17 PDT 2016


This is a proposal about implementing an analysis that calculates loop cost
based on cache data. The primary motivation for implementing this is to
write profitability measures for cache related optimizations like
interchange, fusion, fission, pre-fetching and others.

I have implemented a prototypical version at http://reviews.llvm.org/D21124.
The patch basically creates groups of references that would lie in the same
cache line. Each group is then analysed with respect to innermost loops
considering cache lines. Penalty for the reference is:
a. 1, if the reference is invariant with the innermost loop,
b. TripCount for non-unit stride access,
c. TripCount / CacheLineSize for a unit-stride access.
Loop Cost is then calculated as the sum of the reference penalties times
the product of the loop bounds of the outer loops. This loop cost can then
be used as a profitability measure for cache reuse related optimizations.
This is just a brief description; please refer to [1] for more details.

A primary drawback in the above patch is the static use of Cache Line Size.
I wish to get this data from tblgen/TTI and I am happy to submit patches on

Finally, if the community is interested in the above work, I have the
following work-plan:
a. Update loop cost patch to a consistent, commit-able state.
b. Add cache data information to tblgen/TTI.
c. Rewrite Loop Interchange profitability to start using Loop Cost.

Please share your valuable thoughts.

Thank you.

[1] [Carr-McKinley-Tseng]


Good time...
Vikram TV
CompilerTree Technologies
Mysore, Karnataka, INDIA
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160608/d904ebb4/attachment.html>

More information about the llvm-dev mailing list