Interprocedurally Valid Relations in Affine Prog rams
Interprocedurally Valid Relations in Affine Prog rams
复制标题
仿射程序中的过程间有效关系
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Markus Müller
中科院分区：
文献类型：
--
作者：
Markus Müller
我们考虑一个抽象的程序，保持仿射分配，而保守地处理与其他转让和忽略条件的分支。我们提出了一个过程间的分析，这样的抽象程序，为每一个程序点v确定了一套所有的仿射关系之间的程序变量是有效的，当reachingv。该算法的运行时间是线性的程序大小和多项式的出现变量的数量。我们将这个结果推广到多项式时间算法，它为每一个程序点确定有界次数的程序变量之间的所有有效多项式关系的集合。
We consider an abstraction of programs which preserves affine assignments exactly while conservatively dealing wi th other assignments and ignoring conditions at branches. We present an interprocedural analysis of such abstracted pro grams which for every program point v determines the set of all affine relationsbetween program variables which are valid when reachingv. The runtime of this algorithm is linear in the program size and polynomial in the number of occurring variables. We extend this result to a polynomialtime algorithm which determines for every program point the set of all validpolynomial relationsbetween program variables of bounded degree.