次のコードは、4000番地から150語 (1語は4番地分) に0を格納するコードである。プログラムの意味が変わらないように、ループ内に不要な命令をできるだけ多くループ外
(ラベルloopより前) に移動する最適化を行った後、このコードを実行したときの命令実行総数として、最も適切なものはどれか。
LDI R1, #150
LDI R2, #0
loop: LDI R3, #4000
MULI R4, R2, #4
ADD R5, R3, R4
LDI R6, #0
ST R6, (R5)
INC R2
SUB R7, R1, R2
BGZ R7, loop
各命令の意味は以下のとおりである。
LDI Rx, #Y レジスタ Rx に値 Y を格納する。
ST Rx, (Ry) Ryの内容が示す番地に Rx の値を格納する。
INC Rx Rx を 1増やす。
ADD Rx,Ry,Rz Ry+Rz を Rx に格納する。
SUB Rx,Ry,Rz Ry-Rz を Rx に格納する。
MULI Rx,Ry,#Z Ry*Z を Rx に格納する。
BGZ Rx,label Rxが0より大きければlabalに分岐する。
① 755 ② 904 ③ 1053 ④ 1202 ⑤ 1500
②
まず、ループ内に不要な命令を考える。
LDI R3, #4000 は、R3に 4000 を格納する処理であり、ループ外に移動できる。
LDI R6, #0 は、R6に 0 を格納する処理であり、ループ外に移動できる。
よって、最適化後は以下のコードとなる。
LDI R1, #150
LDI R2, #0
LDI R3, #4000
LDI R6, #0
loop: MULI R4, R2, #4
ADD R5, R3, R4
ST R6, (R5)
INC R2
SUB R7, R1, R2
BGZ R7, loop
命令実行総数は
LDI R1, #150 ・・・ R1: 150
LDI R2, #0 ・・・R1: 0, R2: 0
LDI R3, #4000 ・・・R1: 100, R2: 0, R3: 4000
LDI R6, #0 ・・・R1: 100, R2: 0, R3: 4000, R6: 0
ここまでで命令数は4である。
LOOP内は、
MULI R4, R2, #4
⇒ R1: 150, R2: 0, R3: 4000, R4: 0*4=0
ADD R5, R3, R4
⇒ R1: 150, R2: 0, R3: 4000, R4: 0, R5: 4000+0=4000
ST R6, (R5)
⇒ 4000番地に 0 を格納する。
INC R2
⇒ R1: 150, R2: 1, R3: 4000, R4: 0, R5: 4000
SUB R7, R1, R2
⇒ R1: 150, R2: 1, R3: 4000, R4: 0, R5: 4000, R7: 150-1=149
BGZ R7, loop
⇒ loopへ戻る
MULI R4, R2, #4
⇒ R1: 150, R2: 1, R3: 4000, R4: 1*4=4
ADD R5, R3, R4
⇒ R1: 150, R2: 1, R3: 4000, R4: 4, R5: 4000+4=4004
ST R6, (R5)
⇒ 4004番地に 0 を格納する。
INC R2
⇒ R1: 150, R2: 2, R3: 4000, R4: 4, R5: 4004
SUB R7, R1, R2
⇒ R1: 150, R2: 2, R3: 4000, R4: 4, R5: 4004, R7: 150-2=148
BGZ R7, loop
⇒ loopへ戻る
MULI R4, R2, #4
⇒ R1: 150, R2: 2, R3: 4000, R4: 2*4=8
ADD R5, R3, R4
⇒ R1: 150, R2: 2, R3: 4000, R4: 8, R5: 4000+8=4008
ST R6, (R5)
⇒ 4008番地に 0 を格納する。
INC R2
⇒ R1: 150, R2: 3, R3: 4000, R4: 8, R5: 4008
SUB R7, R1, R2
⇒ R1: 150, R2: 3, R3: 4000, R4: 8, R5: 4008, R7: 150-3=147
BGZ R7, loop
⇒ loopへ戻る
・・・
R7の値が149～0まで150回ループする。つまりループ内の命令数は6で、150回ループするので命令数は、6×150 ＝ 900である。
従って、ループ外で4回、ループ内で900回、命令実行総数は904回である。
| Ⅲ－１０ | 目次 | Ⅲ－１２ |