Recurrence-aware value range analysis for precision tuning

Should one invest in numerical precision or sacrifice it in favor of execution speed? This trade-off naturally arises in many areas of computer science and is particularly relevant during the code compilation phase. Precision tuning addresses this problem by applying numerical analysis and conversion techniques to tolerate a limited loss of accuracy in exchange for improved performance. TAFFO is an LLVM-based framework designed to automate this process. A fundamental, yet non-trivial, aspect of precision tuning is the analysis of the ranges that program values can assume, as these ranges directly influence the correctness and effectiveness of numerical conversions. Several techniques have been proposed to address this problem, and the topic remains an active area of research. The aim of this thesis is to show how a pattern- recurrence-based approach to static range analysis can help to detect valid bounds, improve the analysis control and, as a consequence, enhance the performance benefits obtained through precision tuning.

Conviene investire nella precisione numerica o sacrificarla a favore della velocità di esecuzione? Questo compromesso si presenta in molte aree dell’informatica ed è particolarmente rilevante durante la fase di compilazione del codice. Il precision tuning affronta questo problema applicando tecniche di analisi numerica e di conversione tra rappresentazioni, tollerando una perdita di accuratezza limitata in cambio di un miglioramento delle prestazioni. TAFFO è un framework basato su LLVM progettato per automatizzare questo processo. Un aspetto fondamentale, ma tutt’altro che banale, del precision tuning è l’analisi dei range che i valori del programma possono assumere, poiché tali informazioni influenzano direttamente la correttezza e l’efficacia delle conversioni numeriche. Diverse tecniche sono state proposte per affrontare questo problema e il tema rappresenta tuttora un ambito di ricerca attivo. L’obiettivo di questa tesi è mostrare come un approccio pattern- recurrence-based applicato all'analisi statica dei range possa aiutare ad individuare bound validi, migliorare il controllo dell'analisi e, di conseguenza, incrementare i benefici prestazionali ottenibili tramite il precision tuning.