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.