基于符号运算的归纳变量识别与约化.pdf

36 24 2010 12 Vol.36 No.24 Computer Engineering December 2010 ·· 2010 A TP311 ( 200240) Induction Variable Recognition and Reduction Based on Symbolic Operation ZHOU Lei, CHEN Ke-fei (Department of Computer Science and Engineering, Shanghai Jiaotong University, Shanghai 200240, China) AbstractBased on symbolic operation, a novel approach is proposed to recognize and reduce Induction Variables(IV). It replaces all l-values in assignments by the original variables which can represent the iteration and dependence relationships among them, and constructs variable dependence digraphs to recognize IV. It establishes recursive equation sets to solve the problems based on symbolic operations, and gets their independent expressions composed of iteration number. Experimental results show that the method fits with different kinds of IV and overcomes the shortages of current methods. Key wordsstatic detection; program analysis; code optimization; symbolic operation 1 1 (Induction Variable, IV) 1: DO i=0,n 2: t=a 3: a=b 4: b=c+2*b-t+2 [1] 5: c=c+d 6: d=d+i [2] 7: ENDDO [3] 1 [4] 1 t