A case for a fast trip count predictor

Autor: Rafael Martins de Sousa, Péricles Alves, Raphael Ernani Rodrigues, Fernando Magno Quintão Pereira
Rok vydání: 2015
Předmět:
Zdroj: Information Processing Letters. 115:146-150
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2014.08.008
Popis: A fast heuristic to predict the trip count of loops.The heuristic predicts correctly the majority of the loops in SPEC 2006.The heuristic is O ( 1 ) .The heuristic allows us to invoke the Firefox JIT compiler earlier.The heuristics speeds up some JavaScript benchmarks by 5% to 27% in Firefox. The Trip Count of a loop determines how many iterations this loop performs. Predicting this value is important for several compiler optimizations, which yield greater benefits for large trip counts, and are either innocuous or detrimental for small ones. However, finding an exact prediction, in general, is an undecidable problem. Such problems are usually approached via methods which tend to be computationally expensive. In this paper we make a case for a cheap trip count prediction heuristic, which is O ( 1 ) on the size of the loop. We argue that our technique is useful to just-in-time compilers. If we predict that a loop will iterate for a long time, then we invoke the JIT compiler earlier. Even though straightforward, our observation is novel. We show how this idea speeds up JavaScript programs, by implementing it in Mozilla Firefox. We can apply our heuristic in 79.9% of the loops found in typical JavaScript benchmarks. For these loops, we obtain exact predictions in 91% of cases. We get similar results when analyzing the C programs of SPEC CPU 2006. A more elaborate technique, linear on the size of the loop, improves our O ( 1 ) technique only marginally. As a consequence of this work, we have been able to speed up several JavaScript programs by over 5%, reaching 24% of improvement in one benchmark.
Databáze: OpenAIRE
Externí odkaz: