![2.13 Cプログラムの包括的な例題解説（p.132）
■ sort手続き ■ swap手続き
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}
void swap(int v[], int k)
{
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}
0 1 2 3
v[] 9 8 10 4
?
v[] 4 8 9 10](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-2-320.jpg)
![sort手続きを読み解く（１）
■ sort手続き
■ 外側のfor文のiは，0からn-1まで変化する．n回繰り返される．
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-4-320.jpg)
![sort手続きを読み解く（２）
■ sort手続き
■ j>=0が成立しなければ，v[j]>v[j+1]は評価されないで，for文を抜ける．
■ j>=0が成立したときだけ，v[j]>v[j+1]は評価される．
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}
C言語では，論理式は左から評
価する．
&&では，成立しない式があれ
ば，それ以降の式は評価されな
い．](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-5-320.jpg)
![sort手続きを読み解く（２）
■ sort手続き
■ 外側のfor文のiは，0からn-1まで変化する．n回繰り返される．
■ 内側のfor文に着目すると，変数iはjの初期化（j=i-1）にしか使われていない．
■ i=0のとき，j＝0-1=-1となり，j>=0が成立しないので，内側のfor文は抜ける．
? 質問?外側のfor文は，for(i=1;i<n;i+=1)でもよいか？
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-6-320.jpg)
![sort手続きを読み解く（３）
■ sort手続き
■ i=0 のとき j=-1 となり，j>=0が成立しないので，内側のfor文は回らない．
■ i=1 のとき j=0 となり，j>=0が成立するので，内側のfor文は，j=0 を実行する．
■ i=2 のとき j=1 となり，j>=0が成立するので，内側のfor文は，j=1，0 を実行する．
■ i=3 のとき j=2 となり，j>=0が成立するので，内側のfor文は，j=2，1，0 を実行する．
■ i=4 のとき j=3 となり，j>=0が成立するので，内側のfor文は，j=3，2，1，0 を実行する．
■ i=n-1 のとき j=n-2 となり，j>=0が成立するので，内側のfor文は，j=n-2，...，0 を実行する．
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}
外側のfor文はn回
内側のfor文は1～ n-1 回](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-7-320.jpg)
![sort手続きを読み解く（４）
■ sort手続き
■ i=0 のとき j=-1 となり，内側のfor文は回らない．
■ i=1 のとき j=0 となり，内側のfor文は j=0 を実行する．
■ i=2 のとき j=1 となり，内側のfor文は j=1，0 を実行する．
■ i=3 のとき j=2 となり，内側のfor文は j=2，1，0 を実行する．
■ i=4 のとき j=3 となり，内側のfor文は j=3，2，1，0 を実行する．
■ i=n-1 のとき j=n-2 となり，内側のfor文は j=n-2，...，0 を実行する．
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}
内側のfor文の動作が
分かったので，
v[j]>v[j+1] とswap(v,j)
について考える．](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-8-320.jpg)
![sort手続きを読み解く（５）
■ sort手続き
■ 内側のfor文は j=0 を実行する．v[0]>v[1]ならば，v[0]とv[1]の値を交換する．
■ 内側のfor文は j=1，0 を実行する．v[1]>v[2]ならば，v[1]とv[2]の値を交換する．
■ 内側のfor文は j=2，1，0 を実行する．v[2]>v[3]ならば，v[2]とv[3]の値を交換する．
■ 内側のfor文は j=3，2，1，0 を実行する．v[3]>v[4]ならば，v[3]とv[4]の値を交換する．
■ 内側のfor文は j=n-2，...，0 を実行する．v[n-2]>v[n-1]ならば，v[n-2]とv[n-1]の値を交換する．
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-9-320.jpg)
![sort手続きを読み解く（６）
■ sort手続き
■ 内側のfor文は j=0 を実行する．v[0]>v[1]ならば，v[0]とv[1]の値を交換する．
■ 内側のfor文は j=1，0 を実行する．v[1]>v[2]ならば，v[1]とv[2]の値を交換する．
■ 内側のfor文は j=2，1，0 を実行する．v[2]>v[3]ならば，v[2]とv[3]の値を交換する．
■ 内側のfor文は j=3，2，1，0 を実行する．v[3]>v[4]ならば，v[3]とv[4]の値を交換する．
■ 内側のfor文は j=n-2，...，0 を実行する．v[n-2]>v[n-1]ならば，v[n-2]とv[n-1]の値を交換する．
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}
v[0]からv[n-1]まで
ソートされる．](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-10-320.jpg)
![sort手続きを読み解く（７）
■ v[4]={9,8,10,4};
■ i=1,j=0 を実行する．
v[0]>v[1]ならば，v[0]とv[1]の値を交換する．
■ i=1，j=1，0 を実行する．
v[1]>v[2]ならば，v[1]とv[2]の値を交換する．
■ i=2，j=2，1，0 を実行する．
v[2]>v[3]ならば，v[2]とv[3]の値を交換する．
i 0 1 2 3
9 8 10 4 整列済
j 0
9 8 10 4 比較
8 9 10 4 交換](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-11-320.jpg)
![sort手続きを読み解く（８）
■ v[4]={9,8,10,4};
■ i=1，j=0 を実行する．
v[0]>v[1]ならば，v[0]とv[1]の値を交換する．
■ i=2，j=1，0 を実行する．
v[1]>v[2]ならば，v[1]とv[2]の値を交換する．
■ i=3，j=2，1，0 を実行する．
v[2]>v[3]ならば，v[2]とv[3]の値を交換する．
j 1
8 9 10 4 比較
8 9 10 4 交換
j 0
8 9 10 4 比較
8 9 10 4 交換
i 0 1 2 3
8 9 10 4 整列済
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-12-320.jpg)
![sort手続きを読み解く（９）
■ v[4]={9,8,10,4};
■ i=1，j=0 を実行する．
v[0]>v[1]ならば，v[0]とv[1]の値を交換する．
■ i=2，j=1，0 を実行する．
v[1]>v[2]ならば，v[1]とv[2]の値を交換する．
■ i=3，j=2，1，0 を実行する．
v[2]>v[3]ならば，v[2]とv[3]の値を交換する．
j 1
8 9 4 10 比較
8 4 9 10 交換
j 0
8 4 9 10 比較
4 8 9 10 交換
i 0 1 2 3
8 9 10 4 整列済
j 2
8 9 10 4 比較
8 9 4 10 交換
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-13-320.jpg)
![sort手続きを読み解く（10）
■ v[4]={9,8,10,12};
■ i=1，j=0 を実行する．
v[0]>v[1]ならば，v[0]とv[1]の値を交換する．
■ i=2，j=1，0 を実行する．
v[1]>v[2]ならば，v[1]とv[2]の値を交換する．
■ i=3，j=2，1，0 を実行する．
v[2]>v[3]ならば，v[2]とv[3]の値を交換する．
j 1
8 9 10 12 比較
8 9 10 12
j 0
8 9 10 12 比較
8 9 10 12
i 0 1 2 3
8 9 10 12 整列済
j 2
8 9 10 12 比較
8 9 10 12
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}
v[2]>v[3]でなければ交換しない](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-14-320.jpg)
![2.13 Cプログラムの包括的な例題解説（p.130）
■ sort手続き ■ swap手続き
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}
void swap(int v[], int k)
{
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-17-320.jpg)
![swap.s
■ 他の関数（リーフ関数）は呼び出さない
? $raを保存する必要はない
■ レジスタ割当ての指示がない
? 退避?復元が不要な$t0～レジスタを使う
void swap(int v[], k)
{
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}
add $a0,$s2,$zero
add $a1,$s1,$zero
jal swap
…
swap: sll $t0,$a1,2 # $t0= 4*$a1
add $t0,$a0,$t0
lw $t1,0($t0)
lw $t2,4($t0)
sw $t1,4($t0)
sw $t2,0($t0)
jr $ra](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-18-320.jpg)
![2.13 Cプログラムの包括的な例題解説（p.132）
■ sort手続き ■ swap手続き
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}
void swap(int v[], int k)
{
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-19-320.jpg)
![sort関数の構成
■ sort手続き
void sort(int v[],int n)
{
int i,j;
for( i=0; i<n; i+=1 )
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
swap(v,j);
}
■ レジスタ割当て
?引数 int v[0] : $a0
int n : $a1
?変数? i : $s0
j : $s1
外側ループ
内側ループ
関数呼出し](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-20-320.jpg)
![sortの内側ループ
for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1)
addi $s1,$s0,-1 # j=i-1
for2tst:slti $t0,$s1,0 # j < 0 goto exit2
bne $t0,$zero,exit2 #
sll $t1,$s1,2 # $t1=4*j
add $t2,$a0,$t1 # $t2=&v[j]
lw $t3,0($t2) # $t3=v[j]
lw $t4,4($t2) # $t4=v[j+1]
slt $t0,$t4,$t3???# v[j+1] < V[j] goto exit2
beq $t0,$zero,exit2 #
…
addi $s1,$s1,-1 # j=j-1
j for2tst
exit2:
j=j-1;
while(j>=0 && v[j]<v[j+1])
{
...
j=j-1;
}](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-22-320.jpg)
![レジスタ退避とswap呼出し
sort:addi $sp,$sp,-20
sw $ra,16($sp)
sw $s3,12($sp)
sw $s2,8($sp)
sw $s1,4($sp)
sw $s0,0($sp)
…
lw $s0,0($sp)
lw $s1,4($sp)
lw $s2,8($sp)
lw $s3,12($sp)
lw $ra,16($sp)
addi $sp,$sp,20
add $s2,$zero,$a0 # $s2=v[]
add $s3,$zero,$a1 # $s3=n
add $a0,$s2,$zero # $a0:v
add $a1,$s1,$zero # $a1:k
jal swap
$a0と$a1は，sortの引数としても，swapの引
数としても使われる．これらの引数を区別する
必要があるので，sort関数内では，$a0と$a1
ではなくて，$s2と$s3を使うことにする．
?引数レジスタ
$a0～$a3
の取り扱い](https://image.slidesharecdn.com/r03co12slides-210713102340/85/12-23-320.jpg)
More Related Content
What's hot (20)
Similar to 第12回计算机构成 (20)
Recently uploaded (6)
第12回计算机构成
- 1. (C)2021 TOMISAWA Masaki 第12回?計算機構成 前々回の内容 ■ 2.8 コンピュータ?ハードウェア内での手続 きのサポート ?入再帰型手続きのコンパイル ■ トレース課題 ■ 末尾呼出し（tail call） ■ 2.9 人との情報交換 ■ 2.10 32ビットの即値およびアドレスに対す るMIPSのアドレシング方式 ■ 擬似直接アドレッシング ■ PC相対アドレッシング 今回の内容 ■ 2.13 Cプログラムの包括的な例題解説 ? sort手続きの理解 ? swap.s ? sort.s ■ 配列とポインタ ■ 乗算命令と除算命令
- 2. 2.13 Cプログラムの包括的な例題解説（p.132） ■ sort手続き ■ swap手続き void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); } void swap(int v[], int k) { int temp; temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; } 0 1 2 3 v[] 9 8 10 4 ? v[] 4 8 9 10
- 4. sort手続きを読み解く（１） ■ sort手続き ■ 外側のfor文のiは，0からn-1まで変化する．n回繰り返される． void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); }
- 5. sort手続きを読み解く（２） ■ sort手続き ■ j>=0が成立しなければ，v[j]>v[j+1]は評価されないで，for文を抜ける． ■ j>=0が成立したときだけ，v[j]>v[j+1]は評価される． void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); } C言語では，論理式は左から評 価する． &&では，成立しない式があれ ば，それ以降の式は評価されな い．
- 6. sort手続きを読み解く（２） ■ sort手続き ■ 外側のfor文のiは，0からn-1まで変化する．n回繰り返される． ■ 内側のfor文に着目すると，変数iはjの初期化（j=i-1）にしか使われていない． ■ i=0のとき，j＝0-1=-1となり，j>=0が成立しないので，内側のfor文は抜ける． ? 質問?外側のfor文は，for(i=1;i<n;i+=1)でもよいか？ void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); }
- 7. sort手続きを読み解く（３） ■ sort手続き ■ i=0 のとき j=-1 となり，j>=0が成立しないので，内側のfor文は回らない． ■ i=1 のとき j=0 となり，j>=0が成立するので，内側のfor文は，j=0 を実行する． ■ i=2 のとき j=1 となり，j>=0が成立するので，内側のfor文は，j=1，0 を実行する． ■ i=3 のとき j=2 となり，j>=0が成立するので，内側のfor文は，j=2，1，0 を実行する． ■ i=4 のとき j=3 となり，j>=0が成立するので，内側のfor文は，j=3，2，1，0 を実行する． ■ i=n-1 のとき j=n-2 となり，j>=0が成立するので，内側のfor文は，j=n-2，...，0 を実行する． void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); } 外側のfor文はn回 内側のfor文は1～ n-1 回
- 8. sort手続きを読み解く（４） ■ sort手続き ■ i=0 のとき j=-1 となり，内側のfor文は回らない． ■ i=1 のとき j=0 となり，内側のfor文は j=0 を実行する． ■ i=2 のとき j=1 となり，内側のfor文は j=1，0 を実行する． ■ i=3 のとき j=2 となり，内側のfor文は j=2，1，0 を実行する． ■ i=4 のとき j=3 となり，内側のfor文は j=3，2，1，0 を実行する． ■ i=n-1 のとき j=n-2 となり，内側のfor文は j=n-2，...，0 を実行する． void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); } 内側のfor文の動作が 分かったので， v[j]>v[j+1] とswap(v,j) について考える．
- 9. sort手続きを読み解く（５） ■ sort手続き ■ 内側のfor文は j=0 を実行する．v[0]>v[1]ならば，v[0]とv[1]の値を交換する． ■ 内側のfor文は j=1，0 を実行する．v[1]>v[2]ならば，v[1]とv[2]の値を交換する． ■ 内側のfor文は j=2，1，0 を実行する．v[2]>v[3]ならば，v[2]とv[3]の値を交換する． ■ 内側のfor文は j=3，2，1，0 を実行する．v[3]>v[4]ならば，v[3]とv[4]の値を交換する． ■ 内側のfor文は j=n-2，...，0 を実行する．v[n-2]>v[n-1]ならば，v[n-2]とv[n-1]の値を交換する． void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); }
- 10. sort手続きを読み解く（６） ■ sort手続き ■ 内側のfor文は j=0 を実行する．v[0]>v[1]ならば，v[0]とv[1]の値を交換する． ■ 内側のfor文は j=1，0 を実行する．v[1]>v[2]ならば，v[1]とv[2]の値を交換する． ■ 内側のfor文は j=2，1，0 を実行する．v[2]>v[3]ならば，v[2]とv[3]の値を交換する． ■ 内側のfor文は j=3，2，1，0 を実行する．v[3]>v[4]ならば，v[3]とv[4]の値を交換する． ■ 内側のfor文は j=n-2，...，0 を実行する．v[n-2]>v[n-1]ならば，v[n-2]とv[n-1]の値を交換する． void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); } v[0]からv[n-1]まで ソートされる．
- 11. sort手続きを読み解く（７） ■ v[4]={9,8,10,4}; ■ i=1,j=0 を実行する． v[0]>v[1]ならば，v[0]とv[1]の値を交換する． ■ i=1，j=1，0 を実行する． v[1]>v[2]ならば，v[1]とv[2]の値を交換する． ■ i=2，j=2，1，0 を実行する． v[2]>v[3]ならば，v[2]とv[3]の値を交換する． i 0 1 2 3 9 8 10 4 整列済 j 0 9 8 10 4 比較 8 9 10 4 交換
- 12. sort手続きを読み解く（８） ■ v[4]={9,8,10,4}; ■ i=1，j=0 を実行する． v[0]>v[1]ならば，v[0]とv[1]の値を交換する． ■ i=2，j=1，0 を実行する． v[1]>v[2]ならば，v[1]とv[2]の値を交換する． ■ i=3，j=2，1，0 を実行する． v[2]>v[3]ならば，v[2]とv[3]の値を交換する． j 1 8 9 10 4 比較 8 9 10 4 交換 j 0 8 9 10 4 比較 8 9 10 4 交換 i 0 1 2 3 8 9 10 4 整列済 void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); }
- 13. sort手続きを読み解く（９） ■ v[4]={9,8,10,4}; ■ i=1，j=0 を実行する． v[0]>v[1]ならば，v[0]とv[1]の値を交換する． ■ i=2，j=1，0 を実行する． v[1]>v[2]ならば，v[1]とv[2]の値を交換する． ■ i=3，j=2，1，0 を実行する． v[2]>v[3]ならば，v[2]とv[3]の値を交換する． j 1 8 9 4 10 比較 8 4 9 10 交換 j 0 8 4 9 10 比較 4 8 9 10 交換 i 0 1 2 3 8 9 10 4 整列済 j 2 8 9 10 4 比較 8 9 4 10 交換 void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); }
- 14. sort手続きを読み解く（10） ■ v[4]={9,8,10,12}; ■ i=1，j=0 を実行する． v[0]>v[1]ならば，v[0]とv[1]の値を交換する． ■ i=2，j=1，0 を実行する． v[1]>v[2]ならば，v[1]とv[2]の値を交換する． ■ i=3，j=2，1，0 を実行する． v[2]>v[3]ならば，v[2]とv[3]の値を交換する． j 1 8 9 10 12 比較 8 9 10 12 j 0 8 9 10 12 比較 8 9 10 12 i 0 1 2 3 8 9 10 12 整列済 j 2 8 9 10 12 比較 8 9 10 12 void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); } v[2]>v[3]でなければ交換しない
- 15. 挿入ソートのアルゴリズム i 0 1 2 3 4 5 6 7 j 0 14 83 80 41 34 43 60 81 1 14 83 80 41 34 43 60 81 2 14 83 80 41 34 43 60 81 3 14 80 83 41 34 43 60 81 4 14 41 80 83 34 43 60 81 5 14 34 41 80 83 43 60 81 6 14 34 41 43 80 83 60 81 7 14 34 41 43 60 80 83 81 14 34 41 43 60 80 81 83 i 0 1 2 3 3 14 80 83 41 j 2 3 14 80 83 41 3 14 80 41 83 1 3 14 80 41 83 3 14 41 80 83 0 3 14 41 80 83 3 14 41 80 83 4 14 41 80 83 34
- 17. 2.13 Cプログラムの包括的な例題解説（p.130） ■ sort手続き ■ swap手続き void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); } void swap(int v[], int k) { int temp; temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; }
- 18. swap.s ■ 他の関数（リーフ関数）は呼び出さない ? $raを保存する必要はない ■ レジスタ割当ての指示がない ? 退避?復元が不要な$t0～レジスタを使う void swap(int v[], k) { int temp; temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; } add $a0,$s2,$zero add $a1,$s1,$zero jal swap … swap: sll $t0,$a1,2 # $t0= 4*$a1 add $t0,$a0,$t0 lw $t1,0($t0) lw $t2,4($t0) sw $t1,4($t0) sw $t2,0($t0) jr $ra
- 19. 2.13 Cプログラムの包括的な例題解説（p.132） ■ sort手続き ■ swap手続き void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); } void swap(int v[], int k) { int temp; temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; }
- 20. sort関数の構成 ■ sort手続き void sort(int v[],int n) { int i,j; for( i=0; i<n; i+=1 ) for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) swap(v,j); } ■ レジスタ割当て ?引数 int v[0] : $a0 int n : $a1 ?変数? i : $s0 j : $s1 外側ループ 内側ループ 関数呼出し
- 21. sortの外側ループ for( i=0; i<n; i+=1) add $s0,$zero,$zero # i=0 for1tst:slt $t0,$s0,$a1 # i < n beq $t0,$zero,exit1 # i >= n goto exit1 ?… addi $s0,$s0,1 j for1tst exit1: i=0; while(i<n) { ... i=i+1; }
- 22. sortの内側ループ for( j=i-1; j>=0 && v[j]>v[j+1]; j-=1) addi $s1,$s0,-1 # j=i-1 for2tst:slti $t0,$s1,0 # j < 0 goto exit2 bne $t0,$zero,exit2 # sll $t1,$s1,2 # $t1=4*j add $t2,$a0,$t1 # $t2=&v[j] lw $t3,0($t2) # $t3=v[j] lw $t4,4($t2) # $t4=v[j+1] slt $t0,$t4,$t3???# v[j+1] < V[j] goto exit2 beq $t0,$zero,exit2 # … addi $s1,$s1,-1 # j=j-1 j for2tst exit2: j=j-1; while(j>=0 && v[j]<v[j+1]) { ... j=j-1; }
- 23. レジスタ退避とswap呼出し sort:addi $sp,$sp,-20 sw $ra,16($sp) sw $s3,12($sp) sw $s2,8($sp) sw $s1,4($sp) sw $s0,0($sp) … lw $s0,0($sp) lw $s1,4($sp) lw $s2,8($sp) lw $s3,12($sp) lw $ra,16($sp) addi $sp,$sp,20 add $s2,$zero,$a0 # $s2=v[] add $s3,$zero,$a1 # $s3=n add $a0,$s2,$zero # $a0:v add $a1,$s1,$zero # $a1:k jal swap $a0と$a1は，sortの引数としても，swapの引 数としても使われる．これらの引数を区別する 必要があるので，sort関数内では，$a0と$a1 ではなくて，$s2と$s3を使うことにする． ?引数レジスタ $a0～$a3 の取り扱い
- 24. sort関数 sort:addi $sp,$sp,-20 sw $ra,16($sp) sw $s3,12($sp) sw $s2,8($sp) sw $s1,4($sp) sw $s0,0($sp) add $s2,$a0,$zero add $s3,$a1,$zero add $s0,$zero,$zero for1tst:slt $t0,$s0,$s3 beq $t0,$zero,exit1 addi $s1,$s0,-1 for2tst:slti $t0,$s1,$zero bne $t0,$zero,exit2 sll $t1,$s1,2 add $t2,$s2,$t1 lw $t3,0($t2) lw $t4,4($t2) slt $t0,$t4,$t3 beq $t0,$zero,exit2 add $a0,$zero,$s2 add $a1,$zero,$s1 jal swap addi $s1,$s1,-1 j for2tst exit2:addi $s0,$s0,1 j for1tst exit1:lw $s0,0($sp) lw $s1,4($sp) lw $s2,8($sp) lw $s3,12($sp) lw $ra,16($sp) addi $sp,$sp,20 jr $ra ?引数レジスタ $a0～$a3 の取り扱い