依赖分析与循环变换

1、 依赖分析是指令调度和数据cache优化的一个重要的工具。依赖关系决定了保证程序正常执行时的指令顺序。其中包含对于两个给定的寄存器或者内存引用是否访问了统一区域，和指令之间的资源冲突。依赖分析也用于程序的向量化和并行化等利用调整语句顺序来提高性能的工作中。 依赖分类 控制依赖 数据依赖 S1 a = b +cS2if a 10 goto L1S3d = b * c;S4e = d + 1;S5 L1: d = e / 2; 流依赖 ：如果 S1 S2 并且前面的语句定值后面的语句使用那个值，这种就叫做流依赖，表示为 S1 f S2。 反依赖 ：如果S1 S2 并且S1使用S2设定的值，我们就说

2、这里存在反依赖，写作S1 a S2 。 输出依赖 ：如果S1 S2 并且它们都对同样的变量赋值，我们就说这里存在输出依赖，写作S1 o S2 。 输入依赖 ：如果S1 S2 并且它们都读取同样的值，我们就说这里存在输入依赖，写作S1 i S2。有一点要注意的就是输入依赖对语句并没有限制语句的执行顺序，但是它对数组元素的标量替换有用。 一组依赖关系集合可以用一个有向图来表示，我们把这图叫做依赖图。在图中节点表示语句边表示依赖关系。每条边都被标记来表示依赖类型，除了流依赖未被标记。控制依赖通常被忽略掉除非控制依赖是两个节点之间的唯一依赖关系。 S1 a = b +cS2if a 10 goto L

3、1S3d = b * c;S4e = d + 1;S5 L1: d = e / 2;在依赖DAG中节点表示机器指令或者低等级的中间代码，它的边表示指令之间的依赖关系。一条从I1到I2的边可能有如下几种依赖关系：I1对一个I2用的寄存器或者地址写值，I1 f I2；I1使用一个I2改变了值的地址或者寄存器；I1和I2对同一个地址或者寄存器赋值；我们不能确定I1是否能移动到I2前，例如用不同寄存器r11和r1212访问地址。除非我们可以肯定它们指向不同的地址，否则我们就认定它们之间存在依赖关系。 如果I2必须等到I1执行一些时钟周期后才能执行我们就说在DAG中I1是I2的前驱。在DAG中我们忽略掉

4、依赖边的类型。而是用I1和I2之间正确执行的最小时钟周期间隔来标记边。例如I2必须等到I1执行2个时钟周期后才能执行，我们就标记这条边为1。在例子中我们假设一个load指令要两个周期完成 1 r3 = r15 (4)2 r4 = r15+4 (4)3 r2 = r3 r44 r5 = r125 r12 = r12 + 46 r6 = r3 * r57 r15+4 = r38 r5 = r6 + 2在例子中指令1和2是相互独立的，因为他们访问的是不同的地址。指令3必须在它们后面，因为它用到了指令1，2赋值的寄存器。指令4和1，2是独立的，它们是给不同的寄存器赋值。指令7必须在指令1 2 4 后面

5、，因为它使用了1的结果存在2访问的地址并且有可能和4访问的地址别名。4到8的边是多余的因为有一条从4到6的边和一条6到8的边。但是如果4到8的边如果是4个延迟那么这条边就不算是多余的，因为1，2，4，5，6，7，8，3和1，2，4，5，6，8，7，3都是可行的，但是第一个要8个时钟周期但是第二个需要9个时钟周期。 为了对基本块建立DAG我们需要两个函数 Latency: LIRInst x integer x LIRInst x integer - integer 和 Conflict: LIRInst x LIRInst - Boolean 定义如下 Latency(I1, n1, I2,

6、n2) 执行I1的第n1个周期到开始执行I2的第n2个周期的延迟。 和true I1I2Conflict(I1,I2) =false 如果 必须在 前执行其他情况true I1I2Conflict(I1,I2) =false 如果必须在前执行其他情况true I1I2Conflict(I1,I2) =false 如果必须在前执行其他情况 我们使用资源向量。一个指令的资源向量就是一个指令执行时连续用到的资源的数组。例如MIPS R4000浮点运算有7个资源：A（mantissa Add）E(Exception test ), M（Multiplier first）N（Multiplier sec

7、ond stage）, R (Adder Round) , S (operand Shift), U (Unpack)。单精度的浮点加法 add (add.s)和乘法指令multiply (mul.s)有如下的资源向量 1234567Add.s US,AA,RR,SMul.s UMMMNN,AR例如计算Latency（mul.s, 4, add.s, 1）我们有下面的资源向量I1RV1 =MI2RV1 = UI1RV2 =NI2RV2 = S,AI1RV3 =N,AI2RV3 = A,RI1RV4 =RI2RV4 = R,SI1RV5 =I2RV5 = I1RV6 =I2RV6 = 可以计算得

8、到它们之间得延迟为2 循环的规范形式：每个循环的索引值从1开始每次递增1到整数n.,并且语句只存在于最内层循环里面 迭代空间：k层循环的k维离散笛卡尔空间称为迭代空间。 1.n1 X 1.n2 X.X 1.nk for i1=1 to n1 dofor i2 to n2 do.for ik to nk do语句endfor.endforendfor 字典序 (lexicographical order):用来表示，例如： i11,.,ik1 i12,.,ik2当且仅当：j, 1 = j =k, i11 = i12, ., i(j-1)1 = i(j-1)2并且ij1 ij2 在迭代向量i11,

9、.,ik1是i12,.,ik2的前驱，当且仅当i11,.,ik1 i12,.,ik2 for i = 1 to 3 dofor j = 1 to 4 doS1t =x+y;S2ai,j = bi,j +ci,j;S3bi,j = ai,j * di+1,j + t;EndforEndfor在例子中语句的执行次序如下：S2i, j-1 S3 i,jS2i,j S3i,j对应的依赖关系如下：S2i, j-1 f S3 i,jS2i,j a S3i,j 距离向量:d = .这里di是整数，也就表示对于每一个索引向量i 有依赖距离d那么使用索引向量id的都依赖向量i； 方向向量：用来粗略的表示距离向量

10、和它的整数范围，两种常用的表示如下： 0,01,-,-1-, +=+-+=* 在我们进行循环变化的时候最重要得一点就是要考虑循环内两个迭代之间是否存在依赖关系，如果有就需要知道那么它是那一种依赖关系。 依赖测试目的：证明循环内没有依赖存在，如果不能证明就要尽可能精确的却定依赖类型for i =1 to 4 dobi = a3*i -5 +2.0a2*i +1 = 1.0/iendfor求同一迭代中是否存在依赖 ：2*i + 1= 3 *i -5且1= i =4 不动迭代中是否存在迭代 ：2*i1 +1 = 3 *i2 -5且1=i1=4 1=i2=4 通常测试循环中是否存在依赖关系的问题可以看

11、作求解丢番图方程，也就是满足整数系数的给定不等式的整数解，这是一个NP完全问题。幸运的是在实际执行程序中下标表达式通常比较简单。 循环内数组元素之间的依赖问题可以描述为:S: Xf1(i), , fd(i) S: X f1(i), , fd(i)测试在循环界限内是否存在i, i, 使fk(i) = fk(i), k1:d 通常我们限定f()为线性函数 循环存在依赖关系当且仅当下面等式： 0,10,211*nnjjjjjjaaibbi和下面不等式：,11jjibi 且 ,21jjibi 对于j1,.,n同时满足。依赖的类型是由具体数组X是被使用或者被定值所决定的。 for i = 2, 100

12、for j = 1, 100 s: ai+3j = s: = a2*ji+1 endforendfor 求解等式：i1+3 = 2*j2且 j1=i2+1；2 x 1001 yi2, j1=j2i1=i2, j1 1X -5 当在不同迭代的时候： gcd(3,2) X (-5 1 + 3 - 2) - 1X -5 for i =1 to 4 dobi = a3*i -5 +2.0a2*i +1 = 1.0/iendfor当在同一迭代，也就是方向“=”时：gcd(4-2) X (-5 1 + 3 - 2) - 2X -5 当在不同迭代的时候： gcd(4,2) X (-5 1 + 3 - 2)

13、- 2X -5 for i =1 to 4 dobi = a4*i +2.0a2*i +1 = 1.0/iendfor 可分性和弱可分性是实际程序中常遇见的两种访问类型。依赖方程只有一个变量时, 可分性测试是一种精确测试方法 例如:f(i, j) = 2 * j - 2f(i, j) = 5 * j -7可进行可分性测试可分性测试条件下的依赖测试：a1*ij1 a2*ij2 = b2-b1l=ij1=u 且 l=ij2=u f(i, j) = i - 2f(i, j) = j -3不能进行可分性测试 可分性测试满足a1 = a2时，下标表达式必须要满足下面条件其中一个： a1=a2=0 并且

14、b1 = b2 (b1- b2)/a = U 符合可分性测试a1 = a2 并且符合第一种情况 a1 = a2 = 0 对于 s1 s2: b1 = b2 存在依赖 对于 s1 s3: b1 b2 不存在依赖 对于 s2 s3: b1 b2 不存在依赖for i = 1, 100 s1: a(2) = s2: = a(2) s3: a(5) = endfor 符合可分性测试a1=a2(-5-1)/3 = -2 4 满足条件 (b1- b2)/a = U 所以 S1 S2存在依赖。for i =1 to 4 do.S1:bi = a3*i -5 +2.0S2:a3*i +1 = 1.0/i.en

15、dfor 对于弱可分性测试，下标变量的线性表达式都有a1a2。 对于只有一个下标等式的，可以建立有两个未知数的线性等式。那么循环存在依赖关系当且仅当 gcd(a1,a2)|(b2-b1),并且解要在循环界限内。 当有两个等式集合a1,1*y = a2,1*x +(b2,1-b1,1)和a1,2*y = a2,2*x +(b2,2-b1,2） 如果a2,1/a1,1 = a2,2 /a1,2，那么当且仅当(b2,1-b1,1)/a1,1 = (b2,1 b1,2)/a1,2 时原等式有解 如果a2,1/a1,1 a2,2/a1,2 那么这里存在一个解 上面两种情况解都要满足循环边界的不等式限制

16、有n（n=3）个等式集合的时候,那么n-2个等式是多余的，提供了冗余的决策信息对于数组g 我们要解两个独立的等式 2*x = y+1z = 3 *w可以求得当n=3时候有解对数组h 我们必须同时满足两个等式x= y+2x=2*y-2求得唯一解 x= 6 y= 4所以当且仅当n=6时h有依赖关系for i= 1, n for j =1 , n fi=g2*i,j+1.0 gi+1,3*j=hi,j 1.5 hi+2,2*i - 2 = 1.0/i endforendfor其他测试方法：扩展GCD测试强SIV和 弱SIV测试Delta测试Acyclic测试Power测试简单循环剩余测试Fourie

17、r-Motzkin测试Constraint-Matrix测试Omega测试相同点保守不同点复杂度不同精确度不同 程序依赖图PDG是由控制依赖图和数据依赖图构成的，PDG中的节点可以是基本块也可以是语句或者其他等级的表示。我们在前面已经介绍了数据依赖图，下面我们主要讲控制依赖图。 在控制依赖图中用带谓词的程序作为它的根节点或者中间节点，无谓词的作为它的叶节点。节点n控制依赖节点m当且仅当： 存在一条控制流路径从m到n ，路径上的节点除了m外都被n 后支配。 n 不后支配m。 构建CDG基本步骤： 在程序流图的入口节点entry上加入start节点，它的“Y”边走向entry，“N”边到达exit

18、。我们叫这图为G+ 建立G+的后支配图，建立边集合S 其中m-n 是n没有后支配m的 找出m和n的在后支配树上的最早公共前驱l 那么所有从l到n的路径上的节点除了l以外都控制依赖m。后支配图S集合 ：start- entry, B1-B2, B1-B3, B4-B6startB1R1B3B4B5R3R2YB6B2YNYregion节点：把有同一种控 制依赖的放在一块。 循环变换被用来重新排列程序语句和循环迭代的顺序。变换必须保证程序原来的行为不变，使得循环有助于做其他优化。 循环变换最重要的两点就是合法性和变换的效果。 循环变换的主要目的 ： 程序获取更多的优化机会 提高程序的指令局部性和数据

19、局部性 改变程序的依赖关系发掘更多的并行机会使程序向量化 主要是将循环内的条件判断语句外提。优点是减少了条件判断语句的执行频率。缺点是使得循环结构变得更加复杂。使代码膨胀。DO I = 1 , NIF test THEN statements DO I = 1 , N IF test THEN statements then statements then statements ELSE more statements else statements ENDDO ENDIFELSE more statements DO I = 1 , NENDDO statements else statem

20、ents more statements ENDDOEND IF 将一个循环按索引集分成两部分，移去循环中对索引值的条件测试。增加程序的并行性 DO I = 1 , N A(I) = A(I) + A(5) ENDDO 将上面循环分裂为两个 DO I = 1 , 5A(I) = A(I) + A(5) ENDDO DOALL I = 6 , NA(I) = A(I) + A(5) ENDDO 当标量在循环中先被赋值然后又在后面的语句中被使用的时候就会形成流依赖，并且从使用到赋值又可以形成反依赖。这种反依赖会使得其他循环变换变得困难。标量扩展就是将循环中的标量扩展成为向量，改变程序的依赖性有利于

21、进行其他循环变换。for i = 1 to n dot = ai + bic i= t + 1/tendfor变换后if n1 thenallocate txnfor i = 1 to n dotxi = ai + bic i= txi + 1/txiendfort = txnendif 循环剥皮：去掉循环的第一次或者最后一次迭代。 对于某些循环第一次或者最后一次迭代的计算过程与其它的迭代不同 可以去掉循环里面的对索引值的条件语句 有利于实施循环合并等其他循环变化DO I = 1 , NIF (I 1) A(I) = 1 continueA(I) = A(I-1)*2ENDDO 循环剥皮 A(

22、1) = 1DO I = 2, NA(I) = A(I-1)*2ENDDO 将两个循环合并成为一个循环，减小循环的控制开销。for j= .dobody1endforfor j= . dobody2endfor 循环合并后:for j=. dobody1body2endforfor i =1 ,99 doai = bi +1endforfor i = 1 ,98 doci = ai+1 *2endfor进行循环剥皮ai = b i +1for i = 2, 99 doai = bi +1 endforfor i = 1 ,98 doci = ai +1*2endfor循环合并i =1ai =

23、bi +1for ib =0 , 97i = ib +2ai = bi +1i = ib +1ci = ai +1*2endforid 1 = iu 循环合并必须要满足条件： 两个循环是相邻的 并且两循环的控制条件要一致（如不一致可以通过循环变换实现一致） 两个循环语句间没有方向为 的依赖 把一个循环分割成两个或者更多的小循环，这个是循环合并的逆过程。通过变成更小的循环可以减少指令cache的压力，可以提高内存的局部性。循环分割要保证原有的环状依赖关系不能被破坏。在原循环的依赖图中的强连通子图上的节点应该被分割到同一子循环中去。 DO I = 1 , NS1: A(I) = B(I + 2)

24、+ 1S2: C(I) = B(I - 1) + F(I)S3: B(I) = A(I - 1) + 2S4: D(I) = D(I + 1) + B(I - 1)ENDDO进行循环分割后：DO I = 1, NS1: A(I) = B(I-2) + 1S3: B(I) = A(I-1) + 2ENDDODO I = 1, NS2: C(I) = B(I-1) + F(I)ENDDODO I = 1, NS4: D(I) = D(I+1) + B(I-1)ENDDO 利用幺模矩阵进行循环变换,进行变换的时候必须保证幺模矩阵T和循环中的距离向量d 有 Td0。 幺模变换可以进行循环反转，交换，倾

25、斜 将循环内外层交换位置。有助于发现程序的并行性，将可并行化的循环交换到外层。还能使程序向量化，将可向量化的循环交换到内层。提高程序的数据局部性。有助于实施其他循环变换 For i = . doFor j = . doBody1Endfor Endfor 变化矩阵为 For j = . doFor i = . doBody1Endfor Endfor0110 循环反转是改变循环的执行顺序，让其反转执行。循环反转的合法性：对于forall, dopar, dosingle类型的循环进行反转一直都是合法的，但是对于串行循环只有在循环的迭代空间没有依赖关系时才能进行循环反转变换。循环反转可以增加循环

26、合并的机会。DO I = 1 , N A(I) = B(I) + 1 C(I) = A(I) /2 ENDDO DO I = 1 , N D(I) = 1 / C(I+1)ENDDO变换矩阵DO I = N, 1 A(I) = B(I) + 1 C(I) = A(I) /2 D(I) = 1 / C(I+1)ENDDO 1001 循环倾斜是为了改变循环中存在的依赖关系的方向，发掘更多的并行性，为其它循环变换提供便利 幺模矩阵： 或 f 为倾斜因子，考虑到倾斜效果，倾斜因子一般用1或 2 循环倾斜仅改变循环迭代空间的形状，但不改变循环执行的次序101f101f DO I=1，N DO J=1，N

27、S: A（I，J）=A（I-1，J）+A（I，J-1） ENDDO ENDDO使用么模变换矩阵 后循环迭代空间的形状被改变 DO I = 1，N DO J = I+1，I+NS: A(I,J-I) = A( I-1,J-I) + A(I,J-I-1) ENDDO ENDDO 1011 循环分段：将一个单层循环分成两个嵌套循环 外层循环把原迭代空间分成几个不同的段，一个段中含有多个原循环的迭代 内层循环则执行原循环的迭代for I = 1 , N for Is = 1 , N , sbody(I) for I = Is , min(N , Is + s 1)endforbody(I) endfo

28、r endfor 循环分段特性： 循环分段总是合法的，分段后保持原循环的可向量化（并行化）特性。 对该循环的外层循环或内层循环存在的依赖关系不产生影响对依赖关系的影响：设依赖距离为d，分段的大小为 如果d和s是常数：变换后的依赖距离为(d div s, d mod s)，如果d mod s 还有一个依赖距离为(d div s + 1, -(s d) mod s); 如果d和s不是常数：原依赖方向新依赖方向( , *) (= , ( , *) (= , ) 循环分段作用： 并行优化，将迭代次数多的可并行循环分段，在内外层分别实施不同的并行优化。 向量优化，使分段后内层循环长度恰为向量长度，有助向

29、量代码的生成 提高数据局部性 与循环分段差异： 循环分段： 用于单层循环 每段的起点是由段长和原循环的索引值下界确定的 循环分块： 用于嵌套循环 每块的起点独立于原循环的索引值下界 分块： It块循环， I基本循环, ts是分块大小， to 偏移值for I = l0 , hi for It = floor(l0 to)/ ts) * ts + to , floor(hi to)/ ts) * ts + to for I = max(l0 , It) , min(hi , It + ts- 1)原循环：for I = 1 , 50 for J = I , 60 A(I , J) = A(I , J) + 1 endforendfor循环分块后：块大小ts = 20,偏移t0 = 5for It = -15