首页 > 试题广场 >

针对如下 C 程序片段 ： (1) 给出层 最内层 j 循环

[问答题]
针对如下 C 程序片段 ：
int d[10][10];
for(int k = 0; k < 10; k++)
for(int i = 0; i < 10; i++)
for(int j = 0; j < 10; j++)
if(d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];
(1) 给出层 最内层 j 循环的 三地址代码；
(2) 直接在该 C 源程序上进行循环优化（包括循环不变计算外提 ，强度消弱等）。
查看答案及解析
添加回答
阿奻_头像 阿奻_
（1）假设三地址代码从 100 开始编号：

（2）首先，进行循环不变计算外提：
for(int k = 0; k < 10; k++) {
t2 = addr(d[k]);
for(int i = 0; i < 10; i++){
t1 = addr(d[i]);
t3 = t1[k];
for(int j = 0; j < 10; j++){
if(t1[j] > t3 + t2[j])
t1[j] = t3 + t2[j]
} //for-j
}//for-i
}//for-k
然后考虑强度消弱：首先， 将数组 地址计算展开：
addr(d[k]) = d + k * 40 , 为 为 k 族归纳表达式
addr(d[i]) = d + i * 40 , 为 为 i 族归纳表达式
t1[k] 的地址为：t1+k*4 //k*4 为 i －循环不变式，提到 k 循环后成为 k 族归纳表达式
t1[j] 的地址为：t1+j*4
t2[j] 的地址为：t2+j*4
此时程序为：
t4 = d; // d + k * 40 的初值；
t9 = 0; //k*4 的初值,k 族归纳表达式
for(int k = 0; k < 10; k++) {
t2 = t4;
t5 = d; // d + i * 40 的初值
t8 = t9;
for(int i = 0; i < 10; i++){
t1 = t5;
t3 = *(t1+t8);
t6 = t1;//t1[j] 的地址初值
t7 = t2;//t2[j] 的地址初值
for(int j = 0; j < 10; j++){
if( *t6 > t3 + *t7)
*t6 = t3 + *t7;
t6 = t6 + 4;
t7 = t7 + 4;
} //for-j
t5 = t5 + 40;
}//for-i
t4 = t4 + 40;
t9 = t9 + 4;
}//for-k
接着，量 复写传播消除变量 t1 、t2 、t8 ：
察 并考察 t5 和 和 t6, 以及 t4 和 和 t7 的关系，最后得到优化后程序如下：
t7 = d;
t9 = 0;
for(int k = 0; k < 10; k++) {
t6 = d;
for(int i = 0; i < 10; i++){
t3 = *(t6+t9);
for(int j = 0; j < 10; j++){
if( *t6 > t3 + *t7)
*t6 = t3 + *t7;
t6 = t6 + 4;
t7 = t7 + 4;
} //for-j
}//for-i
t9 = t9 + 4;
}//for-k
发表于 2017-05-02 13:02:01 回复(0)
阿奻_头像 阿奻_
（1）假设三地址代码从 100 开始编号：

（2）首先，进行循环不变计算外提：
for(int k = 0; k < 10; k++) {
t2 = addr(d[k]);
for(int i = 0; i < 10; i++){
t1 = addr(d[i]);
t3 = t1[k];
for(int j = 0; j < 10; j++){
if(t1[j] > t3 + t2[j])
t1[j] = t3 + t2[j]
} //for-j
}//for-i
}//for-k
然后考虑强度消弱：首先， 将数组 地址计算展开：
addr(d[k]) = d + k * 40 , 为 为 k 族归纳表达式
addr(d[i]) = d + i * 40 , 为 为 i 族归纳表达式
t1[k] 的地址为：t1+k*4 //k*4 为 i －循环不变式，提到 k 循环后成为 k 族归纳表达式
t1[j] 的地址为：t1+j*4
t2[j] 的地址为：t2+j*4
此时程序为：
t4 = d; // d + k * 40 的初值；
t9 = 0; //k*4 的初值,k 族归纳表达式
for(int k = 0; k < 10; k++) {
t2 = t4;
t5 = d; // d + i * 40 的初值
t8 = t9;
for(int i = 0; i < 10; i++){
t1 = t5;
t3 = *(t1+t8);
t6 = t1;//t1[j] 的地址初值
t7 = t2;//t2[j] 的地址初值
for(int j = 0; j < 10; j++){
if( *t6 > t3 + *t7)
*t6 = t3 + *t7;
t6 = t6 + 4;
t7 = t7 + 4;
} //for-j
t5 = t5 + 40;
}//for-i
t4 = t4 + 40;
t9 = t9 + 4;
}//for-k
接着，量 复写传播消除变量 t1 、t2 、t8 ：
察 并考察 t5 和 和 t6, 以及 t4 和 和 t7 的关系，最后得到优化后程序如下：
t7 = d;
t9 = 0;
for(int k = 0; k < 10; k++) {
t6 = d;
for(int i = 0; i < 10; i++){
t3 = *(t6+t9);
for(int j = 0; j < 10; j++){
if( *t6 > t3 + *t7)
*t6 = t3 + *t7;
t6 = t6 + 4;
t7 = t7 + 4;
} //for-j
}//for-i
t9 = t9 + 4;
}//for-k
发表于 2017-05-02 13:02:01 回复(0)
提交观点

问题信息

编译和体系结构
上传者：阿奻_
难度：
2条回答 2391浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号