基于Tree-SSA优化框架的高级循环优化

ISSN 1009 -3044E-mail: xsjl@ccc.net.cnComputer Knowedge and Technology电脯知识与技术htp://www.dnzs.net.cnVol.5,No.24, August 2009, pp.7035- -7037Tel:+86- -551-5690963 5690964基于Tree--SSA优化框架的高级循环优化杨夏(湖南科技职业学院.湖南长钞410004)摘要:现代的计算机处理器和计算机系统实现了很多先进技术，要利用这些技术更需要编译器的支持以取得高性能。GCC中Tree SSA 优化框架提供了一个功能强大的程序分析框架。增强的数据依赖分析信息允许编译器变换一个算法以取得更大的局部性,提高资源的利用率以增大吞吐量,提高性能。该文对数据依赖、矩阵变换、循环变换进行了研究,分析了它们的特点,算法和性能,陈述了GCC中循环变换的现状,对以后的研究做出了一定的展望。关键词:敏据依赖;递归链;矩阵变换;循环依赖,循环变换,Tree SSA中圈分类号:TP202文献标识码:A文章编号:1009- -3044(2009)24 -7035- -03High Loop Optimization of the Tree SSA Optimization InfrastructureYANG Xia(Science and Technology Occupaion College of Hunan, Changsha 410004, China)Abstract: Modem compute processos and systemns have put many technologies into practice, while compliers make highpossible when these technologies are used.The Tree- SSA Optimization Infiastructure in GCC suppies a powerful program analysis frame-work.The enhanced data dependence analysis information allows complicrs to change the algorithm for widen locality .Whereby the uti-lizaton ratio of the tesources can be improved which leads to increasing throughput and higher performance.The study focuses on data de-pendence, matrix transform and cyclic ransformation by analyzing their features,lgorithm and performance and stating the staus quo ofGCC cyclic transfornation whereby outlook of the study has been made.Key words: data dependence; recursive chain; matix transform; cyclic transformation; Tree SSA由于GNU/Linux面临高性能科学计算和企业计算的挑战，所以GCC也面临同样的挑战。现代的计算机处理器和计算机系统都实现了很多先进技术,要利用这些特点更需要编译器的支持以取得高性能。许多之前已开发的用于向量和并行体系结构的技术，在超标量和超长指令字计算机体系结构Overview of LNO以及具有较大存储延迟、更复杂功能部件流水线、多级cache的计算机系统中有了新的应用。GCC中TreeSSA优化框架提供了-个程序分析的功能强大的框架。增强的数据依赖分析信息允许编译器变換- -个算法以取得更大的局部性,提高资源的利用皋以Laop Nest Opininer Rranch增大吞吐量,提高性能。GCC的循环嵌套优化器将功能强大的循环嵌套分析器与矩Cm阵变换引擎相结合,提供了一个可扩展的循环变换优化器,循环变换优化器进行幺模(5-变换和编放操作(ecaling operations)。数据相关分析器是基于- -个新算法来跟踪归纳变量而不局限于某一特定模式。矩阵变换功能使用一个类似积木的设计.允许利用该血Analyer3 Optinizers矩阵变换功能去实现许多通用的优化工具程序。某些专有的商业编译器中使用了类似的矩阵变换工具。图1 GCC的循环嵌套优化器图1数据依赖分析经过genericiation和gimplfcation后，被编译的语言循环结构变成了与命令式语言相同的低级结构:三地址赋值语句.goto语句,标号语句。为了从程序的GIMPIE表示形式中检索传统的循环表示,就要检测自然循环(natualloop),然后基于对包含在循环体内的语句的分析.检测循环索引和循环边界。通过分析循环中标量变量的更新属性,抽取循环的迭代次数和允许对于任一给定迭代次数可以快速计算变量的值的表示形式,有了这两者后,可能将复制常量传播遍扩展到跨循环之后,消除冗余检查。还可以进行这样的分析:抽取数组访问对存储空间的读和写的关系的表示，进行传统的数据相关分析。分析器提取的信息使用递归链来记录。这种表示形式使用牛顿插值公式.允许快速计算一个函数在一个给定的整数点的值。我们介绍递归链的基于它们的表示的直观描述.然后将递归链的记号与多项式函数联系起来。递归链所表示的主要的属性是一一个程序在存储位置上的迭代执行。每个存储点包含有一个循环的人口点。在循环执行期间,存储的值随着更新语句的操作而变化。更新表达式的描述嵌人在递归链的表示中,这样就可能从递归链的表示中检索到原来程序的表示形式。换句话说.仅选取感兴趣的标量属性,不能确定的标量属性描述成未知元素。1.1递归链递归链- -中国煤化工收稿日期:2009-04-21YHCNMHG基金项目:国家863软件专项资助(202AA1Z2101、2004AA1Z2210)作者简介:杨夏(1976-),女,湖南常德人,讲师,硕士研究生,主要研究方向为程序设计语言与编译系统。本栏目责任编辑:邀媛媛....系统软件与软件工程..7035Computer Knowledge and Technloy电脯知讽与技术第5卷第24期(2009年8月)r1=0r2=1r3=2loor2*=r3endl:递归链二r4= 9Loop(1)loop(2)r6 += r5end25 +=r4end1递归链一中寄存器r1,r2,t3初始化为递归链的系数。然后,这些寄存器的值在递归链指定的索引的循环中更新:图1中的循环中,寄存器r2的值在循环中更新,它的演化由{1,*,2}1递归链描述。r1从它的初始值0开始累加r2的后继值,因此r1由{.+{1,*,2]11}1递归链描述。递归链二中寄存器r6可以用多变量的标量演化{7,8,+,9}2| 来描述。r6 的值在循环2中累加包含在循环1中变化的rS中的值递归链(..CJ在给定整数点x的计算通过下面的公式(其系数为整系数(...).来进行(.+.+.C.}>=.2 a( )在线性递归链的特殊情况下,这个公式成为:{base,+,stepl(x)base+step*x。其中base和step是两个整数常量。递归链可以处理符号系数,但是在这种情况下，上面的计算公式不总是成立。1.2剥离递归链(peeled chres)我们提出了传统递归链表示的另一个扩展，以便可以表示对初始值在第-次迭代时就会被改写的变量。由于剥离递归链的出现,我们选择了一种与SSA phi 结点相类似的语法,由于剥离递归链的符号就是循环phi结点自己。剥离链的语义如下所示:(a.bk=[a, 当循环的第-次迭代时，lb,否则a和b是两个可能是符号形式的递归链。只要循环phi结点没有在SSA图中定义--个强连通部件就构建一个剥离递归链。2矩阵变换使用基矩阵变换而不是连续进行几次循环变换的原因很多。首先,能够以一种简单得多的方法将多个变换组合为-一个,这就使得基矩阵变换的功能很强。然而任何描述的变换能用--串简单的循环变换来表示,但是确定应用这些简单循环变換的次序以取得所要求的变换不是- -件容易的事。尽管如此,利用一个变换矩阵,能够直接生成所需要的变换。此外,确定一个给定变换的合法性是-一个简单的乘法操作。使用的算法也允许进行部分变换。D01IJGCC使用的代码生成算法是基于Li Wei的Lambda循环变換工具组件。它使用整数格作(:)为循环嵌套的模型并使用非平凡矩阵作为变换的模型。实现的算法支持任何边界可能表示为BDDO一组线性表达式的循环,其中每个线性表达式可能包括循环不变量通过应用这些变换到图27中的循环所产生的循环分别如8,9,10,11中所示。这组操作包含每个幺模运算(交换,反向,和偏斜)与缩放。将缩放加到适用的变换表示任何非平凡矩阵都能应用于循环,因为它们都能被还原为上述循环变换操作的组合。缩放在循环分片和分布存储(6;)AC:V-Vn代码生成的环境下是很有用处的。合法性测试简单地通过将循环的依赖向量乘上变换矩阵,并判断所得到的结果依赖向量Fpntopcting是否是词法序为正的。这会保证数据依赖在生成的循环嵌套中不会被改变。完整的程序允许完成包含有该循环的某部分所需变换的变换矩阵，在某种程度上与整个循环的循环依赖相- -致。3实现与应用.GCC的线性循环变换分为几个部分:- -个矩阵数学引擎,一个变换引擎,和转换器。矩阵数DOUU学引擎实现了执行变换(反向,计算Hermite形式,乘法等等)所必需的各种向量和矩阵数学子(:)" o程序。变换引擎实现了合法性测试,重写循环边界.重写循环体,以及完成部分变换。使用GCC来变换一个循环，首先需要将这个循环变换为一种代码生成算法可用的形式。ripre 1位stendbop这是一一个简单的函数,通过输人一个GCC的循环结构并产生一个变换中国煤化工(a-)构。这个循环嵌套结构由-组表示每个循环边界的线性方程组成。下来我们已提供了一个函数,输入一个循环嵌套结构和一个变换矩阵,如果HCNMHG处函数主要对于那些通过完整算法不能产生的变换有用,这是因为该组件仅产生合法变换。第m1:Rnendbop三,利用前面描述的代码生成算法重写循环嵌套结构的循环边界。最后,我们把循环嵌套结构困2循环变化图.7036”系统软件与软件工程....本栏目责任编辑;谢嫗媛第5卷第24期(2009年 8月)Computer Knolege and Technolgy电腩知识与技术转换为CIMPlE/Tree SSA代码。这个子程序接受一个循环嵌套结构并重写与之匹配的10实际的循环嵌套代码。这包含两个步骤:首先生成新的迭代变量.循环边界,和循环结束条件。其次将循环体转换为消除了之前使用的迭代变量的形式。这个过程是直观的:给定一个源迭代变量的向量Si和目标迭代变量的向量Sj,以及一个变换矩阵T,这个函数使用方程.根据月标迭代变量来计算源迭代变量。对循环中的每个语句都进行这样的计算,并且用新的语句代瞽旧的语句。基于矩阵的循环变换能用来提高并行化和向量化(通过消除阻止代人的内层循环rguar inerchenged依赖)的有效性。也能用于执行优化Cache重用的时间和空间局部性优化。这些类型的优困3矩阵循环变换有效性比较围化有潜力显普提高应用程序和benchmark的分值。研究表明,依赖于应用程序的特点,与未修改的算法相比较，存储局部性优化能产生2到50的加速比。作为加速比的一个例子，我们将利用一个众所周知的SPECTCPU2000benchmark,SWIM。SWIM将大部分时间消耗在单层循环上。通过简单地交换这个循环.可能提高七倍的性能.如图所示。新的数据依赖和矩阵变换功能允许GCC去实现循环嵌套优化以显著提升应用程序的性能。这些优化包括:循环交换,循环展开和合并.循环融台.循环分裂,循环反转,以及循环偏斜。循环交换交换循环的次序以更好地将循环操作数与系统特征匹配.比如,改善存储层次访问模式或者暴露没有依赖的循环迭代以便允许向量化。当变换后的执行安全时.优化的循环次序依赖于目标系统。依赖于所要的效果,交換能将最大相关性的循环交换到循环嵌套内的较内层的位置或者是较外层的位置。由于存在别名和数据依赖信息，优化的作用是有限的。扩展和合并变换展开一个外层循环的迭代并随后融合内层循环的拷贝以取得较大的重用价值和隐费功能单元的延迟。优化的展开因子取决于调度和寄存器压力。优化与循环交换和循环展开有关,所以,类似地,它需要准确的别名和数据依赖信息。4研究展望提出能利用初始循环变换框架实现的循环变换后,其功能将被扩展为其他众所周知的循环优化,比如循环分片,循环交错,外层扩展,以及支持三角形和梯形访问模式。高级循环变换的目标兩数取决于目标系统。将目标系统的特征传到GCC循环优化器正在进行研究中。GCC的高级循环优化框架在第--个发行版本中不会实现全部乃至大部分的循环变换-正在进展之中，但现在有了一个好的成长的开始。将来对框架的改进将向两个方向扩展其功能:实现其他优化和减小现存优化的限制。变换首先必须是对于明确定义的数值行为的应用程序是安全的。改进优化以识别更多和各种类型的循环,从而从这些技术中获益并提高应用程序的性能。CCC中有两遍循环优化,一遍是在Tree SSA.上做循环优化,另-遍是在RTL级做循环优化。RTU(寄存器转换语闻)上的循环优化1) lop -iv.c RTL级的财纳变量分析2) lop urol.循环展开和循环刺离3) lop-unswitch.ce循环unswitch4) lop- dolop.e用特定的低开销的循环指令来修改迭代次数确定的循环。Tree -SSA上的循环优化:在Tree -SSA 绪构上进行的循环变换:1) tree -saloop- -ch.c tree上的循环头结点复制2) tree saloop- im.c循环不变量的移动3) tree -s-loop-ivcanon.c 归纳变量的标准化4) lree -s-loop- -ivopts.c归纳变量优化5) te-esa-loop-manip.c高级循环操作函数6) teessa-loop- prefetch.c数组预取7) tree 8sa-loop- unswitch.c循环unswitching80 tree -oop linear.c线性 循环变换优化Tree SSA上循环优化能进行为了某些并行执行的循环交换以及循环反转,但是没有考虑cache局部性,对于访问模式与ceache中数组的存储方式不协调的嵌套循环不能变换。不能对非紧嵌套循环进行循环变换以优化性能。存在数据依赖分析不够准确、对于多归纳变量分析不准确,不能进行循环偏斜变换的问题。GNU计划在CCC3.5中加入Tree SsA优化框架，这就为在Tree SSA上的优化提出了时间表。可以考虑建立一个代价模型函数,计算变换后的效益.以决定是否进行某一特定的循环变换。 完善线性循环变换.使其能正确完成幺模变换。在以上基础上,再探讨其他收效较大的循环优化变换(集中于Tree -SSA 上的循环优化)。如循环分块,循环剥离,循环分裂,以及循环融合等等。参考文献:[1] Novillo D,Red Hat Canada, Ld Tree ssa.A New Opimization Ifrastucture for GCC [C_.tawaCaproccedings of the 2003 CCCSummit,2003.[2] Meril J.GENERIC and GIMPLE:A New Tree Representation for Entire Functions [C.tawa,Cana:proceedings of the 2003 CCC[3] Eigler F Ch.MudIlap:Pointer Use Checking for C++.C0tawa:Proceedin中国煤化工[4]} The GNU Compiler olleltion[EB//Tt://gcc.gnu.org.[5] Robert A, van Engelen,Birch J.Kyle A Callivan Aray Data Dependence:MYHC N M H Gices Agebra[J.W ashington,DC,USA:IEEE Computer Society,2004.[6] Alen R,Kennedy K.现代体系结构的优化编译器[M].张兆庆，乔如良,泽北京:机械工业出版社2004.本栏目责任编辑.谢媛媛....系统软件与软件工程.* 7037