令和2年度 III-11

解説

この問題で問われていること

ループの繰返しによって値が変化しない命令(ループ不変)を見つけて、ループ外へ出したときの命令実行数を数える問題。

解き方

① 実行総数=ループ前の命令数+ループ内の命令数×繰返し回数。定数を代入するだけの命令はループ外へ移せる
② ループ外へ移せるのはLDI R3とLDI R6 → ループ前は4命令、ループ内は6命令。R2が0→150で150回
③ 4+6×150=904(②)

正解が正しい理由

ループ内の命令を確認する。LDI R3,#4000は、定数を代入するだけで繰返しに依存しないため、ループ不変で、ループ外へ移動できる。MULI R4,R2,#4は、R2(ループごとに増える)に依存するため、移動できない。ADD R5,R3,R4も、R4に依存するため、移動できない。LDI R6,#0は、定数の代入で、ループ不変であり、移動できる。ST、INC、SUB、BGZは、ループごとに値が変化する(または副作用がある)ため、移動できない。最適化後、ループ前の命令は、LDI R1、LDI R2に、移動した2命令(LDI R3、LDI R6)を加えた4命令。ループ内は、MULI、ADD、ST、INC、SUB、BGZの6命令で、R2が0から150になるまで、150回繰り返す。実行総数は、4+6×150=904となり、②が正しい。

この問題で必要な基礎

■ ループの繰り返し回数
loopから最後のBGZまでが繰り返し部分です。R2は0から始まり、1周ごとにINCで1増えます。SUBでR7=150−R2を計算し、BGZは「R7が0より大きければloopに戻る」ので、R2が150になった周(150周目)で繰り返しが終わります。

■ ループの外に出せる命令
「毎回同じ値を代入するだけで、繰り返しの中で変わる値を使っていない命令」は、ループの前で1回だけ実行しても結果が変わりません。LDI R3,#4000 や LDI R6,#0 がこれにあたります。一方、R2の値を使う命令(MULIなど)や、毎回実行する必要がある命令(ST、INCなど)は外に出せません。

各選択肢について

• ① 755は、繰返し回数や、ループ内の命令数の数え方を誤った場合の値で、正しい計算では得られない。
• ② 4+6×150=904で、正しい。これが正答。
• ③ 1053は、最適化前後の数え方を誤った場合の値で、正しくない。
• ④ 1202は、ループ内の命令を、8命令とし、150回繰り返したときの値(2+8×150=1202)で、最適化前の実行総数。
• ⑤ 1500は、最適化後の命令数の数え方を誤った値で、正しくない。

覚えるべきポイント

ループ不変式の移動は、繰返しごとに値が変わらない計算(定数の代入など)をループ外へ出す最適化。命令実行数=ループ前の命令数+ループ内の命令数×繰返し回数。