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.
Type de document :
Communication dans un congrès
Workshop on Software Termination (WST'14), Jul 2014, Vienne, Austria. 2014
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger
Contributeur : Laure Gonnord <>
Soumis le : lundi 9 mars 2015 - 11:14:16
Dernière modification le : vendredi 20 avril 2018 - 15:44:25
Document(s) archivé(s) le : mercredi 10 juin 2015 - 10:45:11


Fichiers produits par l'(les) auteur(s)


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale 4.0 International License


  • HAL Id : hal-01006208, version 1



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. 2014. 〈hal-01006208〉



Consultations de la notice


Téléchargements de fichiers