循环优化概述.

什么叫做循环？循环就是程序中那些可能反复执行的代码序列。也正是由于这部分代码序列可能会被反复执行，所以在进行中间代码优化时应着重考虑循环优化，这对提高目标代码的效率起到很大的作用。为了进行循环优化，首先需要确定的是程序流图中哪些基本块构成一个循环。按照结构程序设计思想，程序员在编程时应使用高级语言所提供的结构性的循环语句来编写循环。而由高级语言的循环语句所形成的循环，是不难找出的。对于循环中的代码，可以实行代码外提、强度削弱和删除归纳变量等优化操作。一个中间代码序列的程序流图如下所示：

我们不难看出，其中B${}_2$和B${}_3$分别构成一个循环，{B${}_2$,B${}_3$,B${}_4$,B${}_5$}构成一个范围更大的循环。而我们要进行循环优化，首先需要知道循环在哪里，接下来，我们就一步步给出，整个循环优化的过程。

计算必经节点集.

【定义】：若从首结点出发到达结点N${}_j$的每一条通路都必须经过结点N${}_i$，那么我们称N${}_i$是N${}_j$的必经节点，记为N${}_i$ dom N${}_j$，其中dom是dominate的简写。那么N${}_j$所有必经节点的集合，就是N${}_j$的必经节点集，记为D(N${}_j$).

计算程序流图中必经节点集的算法也是一个不动点算法，通过每一次的迭代来计算一个结点的必经节点集。当程序流图中所有结点的迭代计算结果都不发生改变时，说明已经获得了最终的结果，算法宣布结束。下面我们给出计算必经节点集的算法：

这里我们也给出一个例题，作为计算必经节点集算法的收尾：

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

需要注意的是，该算法并不像图中那样，一次迭代计算就可以确定结果，而是需要再一次迭代确认了所有的结点都没有发生变化，才能确定最终结果的。

循环查找算法.

1.查找回边.

【定义】如果一个程序流图中存在有向边<N${}_i$→N${}_j$>，并且N${}_j$∈D(N${}_i$)，那么我们称有向边<N${}_i$→N${}_j$>是一条回边。

依旧是我们前一部分给出的实例，考察其中的回边：

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

2.查找循环.

求出了程序流图中的回边之后，我们就可以基于回边来查找循环。具体的方法是，若<N${}_i$→N${}_j$>是一条回边，那么该回边构成的循环中的结点包括：N${}_i$和N${}_j$以及所有不经过N${}_i$能够到达N${}_j$的结点。我们以上图中求出的三条回边为例，6→6确定的循环中只包括结点6；7→4确定的循环中包括结点有{4，7，5，6}；4→2确定的循环中包括的结点有{2，4，3，5，6，7}。

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

代码外提.

至此我们已经完成了查找循环包含结点的工作，接下来就是要对循环体中的中间代码进行优化了。循环中的某些代码虽然随着循环反复地执行，但其中某些运算的结果并没有发生改变，例如循环中有形如A:=B op C的代码，并且如果B和C都是常数，或者到达它们的定值点都在循环外，那么不管循环多少次，每次计算出来得到的B op C的结果都是不变的，对于这样的不变运算，我们完全可以将其外提到循环以外，避免其随着循环多次计算。如此一来，程序的结果没有发生变化，但程序的运行速率却得到了一定程度的提高，这就是代码外提。

【定义】所谓变量A在程序中某一点d的定值到达了另一点u，或者说变量A的定值点d达到另一点u，指的是程序流图中从d有一条通路到达u，并且通路上没有A的其它定值点。

实行代码外提时，我们在循环的入口结点之前建立一个新结点(基本块)，称为循环的前置结点，该前置结点以循环的入口结点为其唯一后继。并且原来流图中从循环外引到循环入口结点的有向边，都改为引到该前置结点。如下图所示：

我们考虑的循环结构，其入口结点都是唯一的，从而其前置结点也是唯一的，我们后续进行代码外提时所有外提的代码都将提到前置结点中。下面一段Pascal源程序，是我们叙述代码外提的第一个例子：

for I:=1 to 10 do
	A[I,2*J]:=A[I,2*J]+1

它对应的中间代码序列如下：

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

1. 考察序号为3和7的语句，因为循环中并没有J的定值点，所以其中J所有引用的定值点都在循环外，从而3和7都是循环不变运算；
2. 考察序号为6和10的语句，分配给数组A的首地址addr(A)的值并不会随着循环的一次次执行而改变，所以6和10也都是循环不变运算。

所以我们可以做出这样的判断：3与7、6与10都可以外提到该循环的前置节点中，进行了代码外提之后的中间代码序列如下所示：

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

那么问题又来了，是不是在任何情况下，都可以将循环不变运算进行外提呢？我们看第二个例子：

从程序流图中我们不难看出，{B${}_2$,B${}_3$,B${}_4$}构成了一个循环，并且B${}_2$是入口结点，B${}_4$是出口结点。

【定义】出口结点是指循环中具有如下性质的结点：从该结点有一条有向边引到循环外的某结点。

图中我们也不难看出，基本块B${}_3$中的I:=2语句是循环不变语句，那么我们是否可以直接将这一语句外提到循环以外的前置结点B${}_2^{\prime }$呢？我们暂且认为可以这样做，外提之后的程序流图如下所示：

我们看外提了I:=2这一语句的程序流图，执行到基本块B${}_5$时，变量I的值总会是2，从而J的值也会是2.但我们需要注意的是，在原始的、没有进行I:=2外提的程序流图中，B${}_3$并不是B${}_4$的必经结点。我们在原始流图中考虑X=30、Y=25的情况，这样的情况下B${}_3$是不会被执行的，所以执行到B${}_5$时变量I的值应该是1，从而J的值也应该是1而非2.那么很显然，我们进行了I:=2外提的程序已经改变了程序运行的结果，这必然是不允许的。问题到底出在什么地方呢？其实前面已经点出，B${}_3$并不是循环出口结点B${}_4$的必经节点，再直白一点说，B${}_3$中的代码并不一定会对B${}_4$中的代码起到作用，但如果我们将其外提到循环的前置结点，那么该外提的语句必然是会对B${}_4$产生影响的，这就导致了程序运行结果被改变的风险，我们并不允许这样的风险存在。
所以从这个例子中我们可以看到，当一个循环不变运算要外提到循环的前置结点时，要求该循环不变运算的语句所在的结点是循环的所有出口结点的必经结点。
另外，我们注意到，如果循环中变量I的所有引用点都是B${}_3$中I的定值点所能到达的，I在循环中不再有其它的定值点，并且出循环之后也不会再引用变量I的值(即在循环外的循环后继结点入口，变量I不是活跃的)，那么即使B${}_3$不是B${}_4$的必经结点，还是可以将I:=2外提到循环的前置结点，因为这样做并不会改变程序的结果。
再一个例子，如果我们将上述程序流图中的基本块B${}_2$改为：

I:=3
if X<Y goto B3

考虑B${}_2$中I:=3外提的问题。
通过计算必经结点集可以发现，B${}_2$确实是循环出口结点B${}_4$的必经结点，那么我们是否可以将I:=3进行代码外提呢？同样的论述过程，我们姑且认为可以，那么如果程序的执行过程是2-3-4-2-4-5，则执行B${}_5$时的变量I值为2，从而J的值也是2；而如果不进行外提操作，那么同样的执行过程下，I和J的值都应该是3，而非2.这一错误的原因在于，循环中除了B${}_2$以外，B${}_3$也对同一个变量进行了定值。
所以从这个例子中我们可以看到，当我们将循环不变运算A:=B op C外提时，要求循环中的其它地方不再有A的定值点。
第三个例子，也是最后一个例子，我们看下面一个程序流图：

考察基本块B${}_4$中循环不变运算I:=2这一语句的外提操作。首先，B${}_4$结点就是整个循环的出口结点，并且B${}_4$结点也是其本身的必经结点；其次整个循环{B${}_2$,B${}_3$,B${}_4$}中也没有第二个对于变量I定值的语句。那么我们是否可以将这一语句外提呢？同样的方法，我们还是暂且认为这一语句可以外提，再比较对于同一个执行过程，外提前后的执行结果。我们考虑X=0、Y=2的情况，循环的执行流程是2-3-4-2-4-5，代码外提前，程序的执行结果为J=2；而代码外提后，程序的执行结果为J=3.
通过这个例子，我们看到，当将循环不变语句A:=B op C进行代码外提时，要求循环中所有对于A的引用点都是并且仅仅是这一定值语句所能到达的。上述的例子中，能够到达A:=I+1这一对于I的引用的定值语句，不仅有B${}_4$中的I:=2，还有B${}_1$中的I:=1.
最后我们给出查找循环L中不变运算的算法：

以及代码外提算法：

强度削弱.

我们要介绍的第二种循环优化技术叫做强度削弱。强度削弱是将程序中执行时间较长的运算替换为执行时间较短的运算。例如，最常见的就是将循环中的乘法运算用递归的加法运算来代替。我们考察前面经过了代码外提的示例流图：

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

不难看出{B${}_2$,B${}_5$}是一个循环，并且B${}_2$是循环的入口结点。我们注意序号为13的语句，这里的变量I是一个递归赋值的变量，每循环一次，它增加一个常量1。另外，序号为4和8的语句在计算T${}_2$和T${}_6$时，都会使用I的值，并且T${}_2$和T${}_6$都是I的线性函数，每循环一次，它们都增加一个常量10.因此，如果把4和8外提到循环的前置结点中，并且在13号语句之后添加上为T${}_2$和T${}_6$增加常量10的语句，程序的运行结果依然不变。

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

经过上述变换，循环中原来的乘法运算4和8被替换为了在前置结点中进行一次初始化的乘法运算(计算初值)以及在循环中递归赋值的加法运算(4’)和(8’).不仅加法运算一般来说比乘法运算快，而且这种在循环前计算初值，再于循环末尾进行常量递增的运算，可以利用变址器提高运算速度，从而使运算的强度得到削弱。所以我们称这种优化技术为强度削弱。
强度削弱不仅对于乘法可以实行，对于加法也可以实行。例如上图中序号为5和9的语句，T${}_3$与T${}_7$的计算中引用到了T${}_2$和T${}_6$，并且T${}_2$和T${}_6$也是递归赋值的变量，每循环一次，它们的值就增加一个常量10.而T${}_3$与T${}_7$的另一个运算对象都是循环不变量，所以每循环一次，T${}_3$与T${}_7$的值就增加一个常量10.很自然地，我们会想到对它们进行强度削弱，即外提一个初始化语句，在循环的末尾添加常量递增语句，得到的优化结果如下所示：

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

从上面的例子中我们可以看到：

1. 如果循环中有A的递归赋值A:=A±b${}_1$，并且循环中另一个变量B的赋值运算可以写为B:=k*A±b${}_2$的形式，那么对于B的赋值运算，我们可以进行强度削弱；
2. 进行强度削弱之后，循环中可能会出现一些新的无用赋值，例如上图中的(4’)和(8’)，因为循环中不再使用T${}_2$和T${}_6$，那么如果循环出口之后它们也不是活跃变量，是完全可以删除的；
3. 循环中下标变量的地址计算是相当耗费时间的，这里介绍的方法对削弱下标变量地址计算的强度是非常有效的。前面的例子中，数组是二维的，如果我们考察一个更高维度的数组，将会进一步看到强度削弱的作用。对于下标变量地址计算来说，强度削弱实际上就是实现下标变量地址的递归计算。

删除归纳变量.

我们要介绍的最后一种循环赋值技术叫做删除归纳变量。讲述具体的流程之前，首先给出基本归纳变量以及归纳变量的定义：

【定义】基本归纳变量：循环中对于变量A的赋值只有唯一的、形如A:=A±b${}_1$的赋值，那么称A为循环中的基本归纳变量；
【定义】归纳变量：如果A是一个基本归纳变量，循环中对于B的赋值总是可以化归为A的同一个线性函数，即B:=k*A±b${}_2$，那么我们称B是一个归纳变量。

考察进行了代码外提之后的示例程序流图：

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

不难发现变量I是循环{B${}_2$,B${}_3$}的基本归纳变量，T${}_2$和T${}_6$是循环中与I同族的归纳变量，再继续发掘，T${}_3$和T${}_7$也是与I同族的归纳变量。
一个基本归纳变量除了用于自身的递归赋值以外，往往只在循环中用于计算其他的归纳变量和控制循环的进行。经过了强度削弱之后的示例程序流图如下所示：

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

关注基本块B${}_3$可以发现变量I除了用于自身的递归赋值以外，只用于控制循环的进行。这时，我们可以使用与I同族的某一个归纳变量来代替I控制循环的进行，从而删除变量I.例如，我们选取T${}_3$(T${}_7$与T${}_3$都在循环中被引用，所以是一样的，而T${}_2$和T${}_6$在循环中没有被引用)来代替I， 由于T${}_3$可以写为10*I+T1，并且循环的控制条件为I>10，所以用T${}_3$代替了I之后，控制条件变为了T3>100+T1.为了不在每一次进行判断时都计算100+T${}_1$的值，我们引入新的临时变量R:=100+T${}_1$，所以序号为2的if语句改写为：

R:=100+T1
if T3>R goto (15)

然后我们就可以删去变量I了，这一优化技术称为删除归纳变量，也叫变换循环控制条件。如果我们假定T${}_2$和T${}_6$在循环出口之后也不是活跃的，那么我们完全可以删去这两个临时变量(因为它们在循环中也没有被使用)。但如果我们在选择代替I的变量时选择了T${}_2$或T${}_6$，那么(4’)或(8’)就不能删除了，最后完成删除归纳变量的中间代码如下：

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

删除归纳变量是在强度削弱之后进行的。我们在下面统一给出强度削弱和删除归纳变量的算法：

循环是我们在写代码时经常用到的一种结构，而往往在考虑性能优化时，循环的优化能带来很大的收益，特别是当我们不得不循环多次时，如果没对性能进行优化，那毫无疑问会带来性能的负担。

循环的类型

---

1.for循环

for循环可能是我们最常用的循环，相对于其他种循环来说，for循环将初始化，判断终止条件，判断值的改变明显地写在了括号内，更为直观。

for(var i=0;i<sum;i++){
    //...
}

2.while循环

var i=0;
while(i<sum){
    // ...
    i++;
}

3.do...while循环

var i=0;
do{
    // ...
    i++;
}while(i<sum)

4.for-in

for-in循环一般用于遍历对象中的key，一般不会使用for-in，因为for-in循环会对性能有更多消耗，会在下文提及原因

for(var prop in object){
    // ...
}

5.for-of

for-of循环也可用于一个有Iterator的对象，如数组，具体可见ES6学习笔记（六）Iterator接口，与for-in不同的是，for-of可以使用break和return语句来跳出循环。然而，虽然其性能消耗比for-in少，但是其性能消耗相对于前三种来说还是更多的，将在下文提及原因

for(var val of arr){
    // ...
}

循环类型的性能

---

在对上面的几种循环遍历数组进行测试后，可以发现for-in循环和for-of循环的速度明显慢于其它三种，对于for-in来说，需要同时遍历实例和原型链，在遍历上的消耗更多，而对于for-of来说，需要去调用Symbol.iterator函数来构建一个迭代器，自动调用next()，且不向next()传入任何值，在接收到done:true之后停止，自然回比前三种方法慢。

（这里的性能测试我使用了console.time()和console.timeEnd()之间的时间差距来比对，因为会受浏览器等各种因素影响，上面的结论是我测试了多组数据后得出的结论）

let arr = [];
arr.length = 10000;
arr.fill(1);

(function() {
    console.time('for循环');
    for (var i = 0; i < arr.length; i++) {
        // ... 相同操作
    }
    console.timeEnd('for循环')
})();

(function() {
    console.time('while循环')
    var i = 0;
    while (i < arr.length) {
        // ...相同操作
        i++;
    }
    console.timeEnd('while循环')
})();

(function() {
    console.time('do-while');
    var i = 0;
    do {
        // ...相同操作
        i++;
    } while (i < arr.length)
    console.timeEnd('do-while');
})();

(function() {
    console.time('for-in');
    for (var i of arr) {
        // ...相同操作
    }
    console.timeEnd('for-in');
})();

(function() {
    console.time('for-of');
    for (var i of arr) {
        // ...相同操作
    }
    console.timeEnd('for-of');
})();

下面是其中一次的执行结果

性能优化

---

要对循环的性能进行优化，只能减少其每次循环的工作量，或者减少循环的次数

减少每次循环工作量

首先看看for遍历一个数组每次循环的工作量

for(var i=0;i<arr.length;i++){
    //...操作
}

1.查找一次arr的长度

2.比较一次i和arr.length的值

3.判断比较结果为true或false

4.执行for循环内的自增

5.i变量的自增（如果步骤3中判断结果为true的话）

存储arr.length的值

每次我们都要去查找一次length的值，那么我们为什么不先在设置初始条件时使用一个变量来存储arr的length值呢。

for(var i=0,len=arr.length;i<len;i++){
    //...操作
}

这样做的好处是，arr至少是在当前作用域链的下一个位置，如果我们把arr.length放在当前一个局部变量中，在查找该值时在作用域链上查找的步数就会减少，所以能有效地减少性能的消耗。这样上面的步骤就变为

1.比较一次i和len的值

2.判断比较结果为true或false

3.执行for循环内的自增

4.i变量的自增（如果步骤3中判断结果为true的话）

倒序循环

倒序循环是一种通用的循环优化方法，我们通过代码来理解

for(var i=arr.length;i--;){
    //...操作
}

此时每次循环的步骤变为

1.i==true的判断（i为0时等式即成立）

2.i变量的自减

3.执行循环内的操作

可以看到，倒序操作实际上就是将i和数组长度的比较和判断为true或false这两步合并，以此来得到性能上的优化。

减少循环次数

达夫设备

达夫设备实际上就是在一次循环中完成多次循环的事情，以达到减少循环次数的作用，看看下面的代码（代码源自《高性能JavaScript》）

// items为要遍历的数组，process为对数组内成员的操作方法

var i=items.length%8;
while(i){
    process(items[i--]);
}

i=Math.floor(items.length/8);

while(i){
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
}

这里通过取长度除以8的余数，先进行这个余数次数的循环，然后之后每次循环执行8次自减操作，相当于一次循环中完成八次循环的操作，以此来达到减少循环的次数的目的

基于函数的迭代

---

很多框架中都封装了迭代循环的方法，包括JavaScript本身也有原生的数组迭代方法，看看下列实例（代码原则《高性能JavaScript》）

// 原生数组方法
items.forEach(function(value, index, array) {
    process(value);
});

// YUI 3
Y.Array.each(item, function(value, index, array) {
    process(value);
});

// jQuery
jQuery.each(items, function(index, value) {
    process(value);
});

// Dojo
dojo.forEach(items, function(value, index, array) {
    process(values);
});

// prototype
items.each(function(value, index) {
    process(value);
});

// MooTools
$each(items, function(value, index) {
    process(value);
});

虽然函数迭代的方法较为方便，但从性能上来说，函数迭代需要去调用函数，性能上的消耗会比普通的循环更多，所以在追求性能的情况下不适合使用函数迭代的方法。

---

参考自《高性能JavaScript》

目录

引言

流水线定义

指令执行流水

指令流水图

循环展开优化

---

引言

详细的流水线分析大家可以参考：计算机体系结构——流水线技术（Pipelining）。本篇只是由探讨循环展开如何提高代码执行效率延申过来的，因此只说明基本的流水线定义以及关于循环展开的部分。

 

流水线定义

计算机中的流水线是把一个重复的过程分解为若干个子过程，每个子过程与其他子过程并行进行。由于这种工作方式与工厂中的生产流水线十分相似， 因此称为流水线技术，从本质上讲，流水线技术是一种时间并行技术。

 

流水线工作设计

• 基本思想：延伸重叠方式，使指令解释过程进一步细化，提高各部件的利用率，以提高指令执行速度
• 理想目标：完成任务的时间与其中某个指令执行时间无关，只与指令执行的频率有关（假设一个任务有n个指令，将完成一个指令分为m个段，每段执行时间为△t ，则理想目标是完成任务的时间是T=m△t+(n-1)△t；当n >> m时，T=(n-1)△t。 指令执行频率为  1 / △t： 即 与m无关，只和指令执行的速度△t有关）

指令执行流水

取指：

　　指令取指（InstrucTIon Fetch）是指将指令从存储器中读取出来的过程。

译码：

　　指令译码（InstrucTIon Decode）是指将存储器中取出的指令进行翻译的过程。经过译码之后得到指令需要的操作数寄存器索引，可以使用此索引从通用寄存器组（Register File，Regfile）中将操作数读出。

执行：

　　指令译码之后所需要进行的计算类型都已得知，并且已经从通用寄存器组中读取出了所需的操作数，那么接下来便进行指令执行（InstrucTIon Execute）。指令执行是指对指令进行真正运算的过程。譬如，如果指令是一条加法运算指令，则对操作数进行加法操作；如果是减法运算指令，则进行减法操作。

　　在“执行”阶段的最常见部件为算术逻辑部件运算器（ArithmeTIc Logical Unit，ALU），作为实施具体运算的硬件功能单元。

访存：

　　存储器访问指令往往是指令集中最重要的指令类型之一，访存（Memory Access）是指存储器访问指令将数据从存储器中读出，或者写入存储器的过程。

写回：

　　写回（Write-Back）是指将指令执行的结果写回通用寄存器组的过程。如果是普通运算指令，该结果值来自于“执行”阶段计算的结果；如果是存储器读指令，该结果来自于“访存”阶段从存储器中读取出来的数据。

 

指令流水图

横坐标：表示时间，即各个任务或指令在流水线中 所在该时刻所对应的子过程

纵坐标：表示某个任务或某条指令，即流水线依次 处理的任务或指令

 

循环展开优化

     在流水线中，往往因为指令顺序安排不合理而导致CPU等待空转，产生延迟，影响流水线效率。

     解决办法：循环展开和指令调度

     前提假设：假设采用MIPS的5段整数流水线：

                      分支的延迟：1个时钟周期。

                      整数load指令的延迟：1个时钟周期。

                      整数运算部件是全流水或者重复设置了足够的份数。

     从例题入手理解：

     例: 对于下面的源代码，转换成MIPS汇编语言， 在不进行指令调度和进行指令调度两种情况下，分析其代码一次循环所需的执行时间。

for (i=1024； i>=0； i--)
     x[i] = x[i] + s;

　 Loop：L.D F0,0（R1） 

     ADD.D F4,F0,F2

     S.D F4, 0（R1）

     DADDIU  R1,R1，#-8

     BNE R1,R2,Loop、

     其中：   整数寄存器R1：指向向量中的当前元素（初值为向量中最高端元素的地址）

                 浮点寄存器F2：用于保存常数s

                 第二部浮点加法需要4个周期

     分析：

     假设一个浮点计算部件需要4周期完成一个计算，若该部件不使用流水线，则延迟为 ：

循环展开：

      在上例中，只有L.D、ADD.D和S.D这3条指令是有效操作 (取、加、存) ，占用3个时钟周期。 而DADDIU、空转和BEN这3个时钟周期都是附加的循环控制开销。可以通过循环展开的方式消除冗余，减少循环控制开销。

• 循环展开技术

       把循环体的代码复制多次并按顺序排列，然后相应调整循环的结束条件

       这给编译器进行指令调度带来了更大的空间

 

     将上述例子中的循环展开3次得到4个循环体，然后对展开 后的指令序列在不调度和调度两种情况下，分析代码的性能。

     分配寄存器（不重复使用寄存器 ）：

      F0、F4：用于展开后的第1个循环体

      F2：保存常数

      F6、F8：展开后的第2个循环体

      F10、F12：第3个循环体

      F14、F16：第4个循环体

     下面分三种情况比较循环展开和指令调度节省的时间：

• 第一种情况：

     

• 第二种情况：

      对指令序列进行优化调度，以减少空转周期

      浮点加法部件采用流水指令流出时钟

 

          

 

• 第三种情况：

      对指令序列进行优化调度，以减少空转周期

      浮点运算部件不采用流水

     

• 循环展开和指令调度时要注意以下几个方面：

       保证正确性。 在循环展开和调度过程中尤其要注意两个地方的正确性：循环控制，操作数偏移量的修改。

       注意有效性。 只有能够找到不同循环体之间的无关性，才能有效 地使用循环展开。

       使用不同的寄存器。 （否则可能导致新的冲突）

       删除多余的测试指令和分支指令，并对循环结束代码和新的循环体代码进行相应的修正。

       注意对存储器数据的相关性分析     

       注意新的相关性

　　3.指令级并行

　　指令调度可以通过两种形式实现：静态调度和动态调度

• 静态调度

　　 依靠编译器（编译器需要做的很复杂，很完善）对代码进行静态调度，以减少相关和冲突。

　　 它不是在程序执行的过程中、而是在编译期间进行代码调度和优化。

　　 通过把相关的指令拉开距离来减少可能产生的停顿。

•  动态调度

　　 在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。

　　 能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器；

　　 能够使本来是面向某一流水线优化编译的代码在其他的流水线（动态调度）上也能高效地执行。

　　 以硬件复杂性的显著增加为代价