Generalized Profile-Guided Iterator Recognition

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Iterators prescribe the traversal of data structures and determine loop termination, and many loop analyses and transformations require their exact identification. While recognition of iterators is a straight-forward task for affine loops, the situation is different for loops iterating over dynamic data structures or involving control flow dependent computations to determine the next data element. In this paper we propose a compiler analysis for recognizing loop iterators code for a wide class of loops. We initially develop a static analysis, which is then enhanced with profiling information to support speculative code optimizations. We have prototyped our analysis in the LLVM framework and demonstrate its capabilities using the SPEC CPU2006 benchmarks. Our approach is applicable to all loops and we show that we can recognize iterators in, on average, 88.1% of over 75,000 loops using static analysis alone, and up to 94.9% using additional profiling information. Existing techniques perform substantially worse, especially for C and C++ applications, and cover only 35–44% of the loops. Our analysis enables advanced loop optimizations such as decoupled software pipelining, commutativity analysis and source code rejuvenation for real-world applications, which escape analysis and transformation if loop iterators are not recognized accurately.
Original languageEnglish
Title of host publicationProceedings of the 27th International Conference on Compiler Construction (CC2018)
Place of PublicationVienna, Austria
PublisherACM
Pages185-195
Number of pages11
ISBN (Print)978-1-4503-5644-2
DOIs
Publication statusPublished - 24 Feb 2018
Event27th International Conference on Compiler Construction - Vienna, Austria
Duration: 24 Feb 201825 Feb 2018
https://cc-conference.github.io/18/

Conference

Conference27th International Conference on Compiler Construction
Abbreviated titleCC'18
Country/TerritoryAustria
CityVienna
Period24/02/1825/02/18
Internet address

Fingerprint

Dive into the research topics of 'Generalized Profile-Guided Iterator Recognition'. Together they form a unique fingerprint.

Cite this