Dynamic compiler optimization techniques for MATLAB

MATLAB has gained widespread acceptance among engineers and scientists. Several aspects of the language such as dynamic loading and typing, safe updates, copy semantics for arrays, and support for higher-order functions contribute to its appeal, but at the same time provide many challenges to the compiler and virtual machine. MATLAB is a dynamic language. Traditional implementations of the language use interpreters and have been found to be too slow for large computations. More recently, researchers and software developers have been developing JIT compilers for MATLAB and other dynamic languages. This thesis is about the development of new compiler analyses and transformations for a MATLAB JIT compiler, McJIT, which is based on the LLVM JIT compiler toolkit. The new contributions include a collection of novel analyses for optimizing copying of arrays, which are performed when a function is first compiled. We designed and implemented four analyses to support an efficient implementation of array copy semantics in a MATLAB JIT compiler. Experimental results show that copy optimization is essential for performance improvement in a compiler for the MATLAB language. We also developed a variety of new dynamic analyses and code transformations for optimizing running code on-the-fly according to the current conditions of the runtime environment. LLVM does not currently support on-the-fly code transformation. So, we first developed a new on-stack replacement approach for LLVM. This capability allows the runtime stack to be modified during the execution of a function, thus enabling a continuation of the execution at a higher optimization level. We then used the on-stack replacement implementation to support selective inlining of function calls in long-running loops. Our experimental results show that function calls in long-running loops can result in high runtime overhead, and that selective dynamic inlining can be used to drastically reduce this overhead.The built-in function feval is an important MATLAB feature for certain classes of numerical programs and solvers which benefit from having functions as parameters. Programmers may pass a function name or function handle to the solver and then the solver uses feval to indirectly call the function. In this thesis, we show that although feval provides anacceptable abstraction mechanism for these types of applications, there are significant performance overheads for function calls via feval, in both MATLAB interpreters and JITs. The thesis then proposes, implements and compares two on-the-fly mechanisms for specialization of feval calls. The first approach uses our on-stack replacement technology. The second approach specializes calls of functions with feval using a combination of runtime input argument types and values. Experimental results on seven numerical solvers show that the techniques provide good performance improvements.The implementation of all the analyses and code transformations presented in this thesis has been done within the McLab virtual machine, McVM, and is available to the public as open source software.MATLAB est devenu reconnu parmi les ingénieurs et les scientifiques. Plusieurs aspects du langage comme le chargement et le typage dynamique, la mise à jour sûr, la sémantique de copie pour les tableaux, et le support des fonctions d'ordre supérieur contribuent à son attrait, mais induisent de nombreuses difficultés pour les compilateurs et les machines virtuelles. MATLAB est un langage dynamique. Les implémentations classiques du langage fonctionnent grâce à des interpréteurs et sont généralement trop lentes pour des larges calculs. Plus récemment, les chercheurs ainsi que les programmeurs ont développé des compilateurs JIT pour MATLAB et d'autres langages dynamiques. Cette thèse traite le développement de nouvelles analyses et transformations pour un compilateur JIT MATLAB, McJIT, qui est basé sur l'outil LLVM. Ces nouvelles contributions comprennent plusieurs analyses novatrices pour optimiser la copie de tableaux, qui sont exécutées quand une fonction est compilée pour la première fois. Nous avons implémenté quatre analyses pour permettre une implémentation efficace de la sémantique de copie de tableaux dans un compilateur JIT MATLAB. Les résultats expérimentaux montrent que l'optimisation de la copie est essentielle pour améliorer les performances dans un compilateur pour le langage MATLAB.Nous avons aussi développé une variété d'analyses dynamiques novatrices et des transformations de code pour optimiser du code à la volée en fonction de l'environnement d'exécution. Actuellement, LLVM ne supporte pas les transformations de code à la volée. En conséquence, nous avons d'abord développé une nouvelle approche pour faire du remplacement sur la pile avec LLVM. Cette fonctionnalité permet à la pile d'exécution d'être modifiée pendant l'exécution de la fonction, ce qui permet de continuer l'exécution à un niveau supérieur d'optimisation. Nous avons ensuite utilisé cette implémentation du remplacement sur la pile pour permettre l'en line des appels de fonctions dans les boucles. Nos résultats expérimentaux montrent que les appels de fonctions dans les boucles à long temps d'exécution peuvent induire un coût important en termes de performances, et que l'en line dynamique et sélectif peut être utilisé pour réduire drastiquement ce coût. La fonction "feval" est une fonctionnalité importante de MATLAB pour certains programmes de calcul numérique qui profitent de la possibilité de passer des fonctions comme paramètres. Les programmeurs peuvent passer le nom d'une fonction ou un pointeur de fonctions à un programme qui utilisera ensuite feval pour appeler indirectement cette fonction. Dans cette thèse, nous montrons que malgré le fait que feval soit un mécanisme d'abstraction appréciable pour certaines applications, il induit un coût significatif, à la fois pour les interpréteurs et pour les compilateurs JIT. Cette thèse propose, implémente et compare deux mécanismes à la volée pour la spécialisation des appels utilisant feval. La première méthode utilise notre mécanisme de remplacement sur la pile. La seconde méthode spécialise les appels de fonctions utilisant feval en combinant le type et la valeur des arguments à l'exécution. Les résultats expérimentaux sur sept programmes différents montrent que ces techniques permettent une bonne amélioration des performances. L'implémentation de toute les analyses et transformations de code présentées dans cette thèse a été effectué dans la machine virtuelle McLab, appelée McVM, et est disponible au public en tant que logiciel libre