Improving Symbolic Analysis of Restructuring Compilers

点击翻译按钮获取中文摘要

The proposed research investigates new methods for symbolic analysis toimprove various restructuring compiler optimizations. A new algebra onfunctions is investigated to manipulate, simplify, and derive normal forms ofscalar functions and (generalized) induction variables in multi-dimensionalloops. The derivation of normal forms for intermediate program constructsenables reasoning about the semantics of a program under analysis. This isextremely useful to improve various compiler optimizations to effectively dealwith symbolic expressions in real-world applications. More specifically, theproposed research aims to improve symbolic analysis methods such asgeneralized induction variable recognition, linear and non-linear datadependence analysis, value range analysis, global value propagation, andcounting the number of solutions to systems of constraints. The effectivenessof parallelizing compilers depends heavily on the accuracy of these methods.The research will result in the ability of compilers to more effectivelyhandle symbolic expressions and constraints. Current methods are not alwayseffective, resulting in considerable performance losses caused by worst-caseassumptions or when program analysis has to be performed at execution time.