Real-World Loops are Easy to Predict: A Case Study

Abstract : In this paper we study the relevance of fast and simple solutions to compute approximations of the number of iterations of loops (loop trip count) of imperative real-world programs. The context of this work is the use of these approximations in compiler optimizations: most of the time, the optimizations yield greater benefits for large trip counts, and are either innocuous or detrimental for small ones. In this particular work, we argue that, although predicting exactly the trip count of a loop is undecidable, most of the time, there is no need to use computationally expensive state-of-the-art methods to compute (an approximation of) it. We support our position with an actual case study. We show that a fast predictor can be used to speedup the JavaScript JIT compiler of Firefox - one of the most well-engineered runtime environments in use today. We have accurately predicted over 85% of all the interval loops found in typical JavaScript benchmarks, and in millions of lines of C code. Furthermore, we have been able to speedup several JavaScript programs by over 5%, reaching 24% of improvement in one benchmark.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [5 references]  Display  Hide  Download

https://hal.inria.fr/hal-01006208
Contributor : Laure Gonnord <>
Submitted on : Monday, March 9, 2015 - 11:14:16 AM
Last modification on : Wednesday, April 3, 2019 - 1:31:25 AM
Document(s) archivé(s) le : Wednesday, June 10, 2015 - 10:45:11 AM

File

wst_realloops_author_version.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial 4.0 International License

Identifiers

  • HAL Id : hal-01006208, version 1

Collections

Citation

Raphael Ernani Rodrigues, Péricles Alves, Fernando Pereira, Laure Gonnord. Real-World Loops are Easy to Predict: A Case Study. Workshop on Software Termination (WST'14), Jul 2014, Vienne, Austria. ⟨hal-01006208⟩

Share

Metrics

Record views

324

Files downloads

217