0

私はクラスにいて、アセンブリ言語で再帰をカバーしています/カバーしています。私は再帰を理解したように感じましたが、人々が私にそれを説明しようとすればするほど、私は再帰から遠ざかっているように感じます.

とにかく、私たちの最後のスライドには機能があり (C で?)、先生はクラスでそれをカバーすると言いましたが、クラスの残りの部分をボードに表示するよう生徒に呼びかけました。彼がずっと私を見ているような気がして、私は愚かに見えるのが怖い.

MIPS でこのコードを書き、理解するのを手伝ってくれませんか? これが難しすぎる場合はIDK

MIPS アセンブリ言語で、fix(i,x) を見つけるように記述します。ここで、fix(i, x) は次のように再帰的に定義されます。

int fix(int i, int x) // assume i > 0, x > 0
{
    if (x>0)
        return fix(i,x-1);
    else if (i>0)
        return fix(i-1, i-1)+1;
    else
        return 0;
}

みんなありがとう、私のクラスは明日です。しかし、私はこの資料を実際に理解したいと思っています。

注: これはクラス内演習であり、単位は 0 です。クラスの全員がすでにこれを行う方法を知っているように感じます。

4

3 に答える 3

2

アセンブリ言語は再帰とは何の関係もありません。再帰は、C言語と呼び出し規約および実装のためにたまたま機能します。アセンブラにCを実装するだけで、再帰は気にしないでください。ペットプロジェクトhttp://github.com/dwelch67/lsasimでこれに触れたのは、最後のレッスンでCの再帰を手動でアセンブラーに変換することを変更しない限りだと思います。それはミップではないので、これが宿題の問題であるという心配はありません。

とにかく、開始するための鍵は、アセンブリにCを実装することです。

たとえば、入力パラメータを持つ関数があります。

int fix(int i, int x)

Cを実装するには、呼び出し規約を宣言するか、既存の規約を使用する必要があります。これは、入力パラメーターをスタックにプッシュするか、レジスターに取り込むための場所が必要であることを意味します。最適化がないと仮定すると、関数全体でこれらの変数を保持し、最後にクリーンアップします。したがって、コード内の任意の場所でANY関数を呼び出す必要がある場合（再帰、同じ関数の呼び出しは、ANYの非常に小さなサブセットですが、そのカテゴリに分類され、特別ではありません）、これらの変数を保持する必要があります。呼び出し規約がこれらをスタックに取り込む場合は、すでに完了しています。呼び出し規約がこれらをレジスタに取り込む場合は、呼び出し前にそれらを保持し、後で復元する必要があります。

push i
push x
implement call to function
pop x
pop i

関数の実装を続行します。

つまり、残りはそれ自体の面倒を見るでしょう。

例として作成した関数に、この関数内の関数の呼び出し後に入力変数を保持する必要があるパスがないことに気付いた場合。そして、入力変数が変更され、次の呼び出しへの入力として使用されます。したがって、Cコードの実装の最適化は、これらの変数の保持について心配しないことです。それらを変更して渡すだけです。呼び出し規約でレジスタを使用するのが、この特定の関数に対してこれを行う最も簡単な方法です。これは、コンパイラが最適化するときにとにかく行うことです（レジスタベースの呼び出し規約を使用している場合は保持されません）。

それが呼ばれている場合は、テール最適化を行うこともできます。通常、関数を呼び出すときは、命令が通常行うことを使用して「呼び出し」を実行します。これは、どこかに戻り値が保持されているため、単純なジャンプや分岐とは異なります。そして、これを元に戻し、呼び出し後に命令に戻る、ある種のreturn関数があります。ネストされた呼び出しとは、戻り値をネストし、それらすべてを追跡することを意味します。ただし、この場合や、関数の実行パスを最後に実行するのが別の関数を呼び出す場合は、代わりに（命令セットに応じて）関数に分岐し、別の戻り値のセットをネストする必要はありません。たとえば、arm命令セットを見てください。

一部のコードは最初の関数を呼び出します。

bl firstfun：

アーム内のblはブランチリンクを意味します。レジスタ14には戻り値が入力され、プログラムカウンタには関数firstfunのアドレスが入力されます。

通常、関数から関数を呼び出す必要がある場合は、r14を保存して、このテールの最適化なしでその関数から戻ることができるようにする必要があります。

firstfun:
 ...
 push {r14}
 bl secondfun
 pop {r14}
 bx r14
 ...
secondfun:
  bx r14

bx lrは、r14のコンテンツへの分岐を意味します。この場合はリターンです。最適化は次のようになります。最初の関数では、最初の関数から戻る前に2番目の関数の呼び出しが最後に行われることに注意してください。それがこの最適化の鍵です。

firstfun:
 ...
 b secondfun
 ...
secondfun:
  bx r14

bは単に分岐を意味し、分岐リンクは単にPCを変更するだけでなく、r14やその他のレジスタやスタックを変更するものではありません。2つの実装の実行は機能的に同じであり、外部関数はfirstfunを呼び出し、適切な実行パスに戻り値（bx r14）があります。

他の人々は、元の呼び出し元をゼロに戻すので、このコードは完全に最適化されて何もない可能性があると指摘しています。

fix:
  return 0
于 2012-01-26T04:32:47.350 に答える
1

私は宿題の問題に答えを出すだけには反対ですが、これは find と同等の関数で、fix(i, x)呼び出しの例を完備しています (このバージョンは C バージョンよりも少し効率的です):

fix:
        bgtz RetI
        xor $v0, $v0, $v0
        jr $ra
RetI:
        move $v0, $a0
        jr $ra

# example of calling fix
main:
        la $a0, 42
        la $a1, 21
        jal fix

そして、これを、コーディングを試みる前に関数が何をするかを学ぶためのレッスンにしましょう :)

于 2012-01-26T00:39:33.303 に答える
1

上記の C のように 3 つに分割するだけです。値 i と x をレジスタ経由で渡し、if チェックを実行してレジスタを変更した後、自分自身を呼び出します。上記を行うには、アセンブラで 30 行以上かかることはありません。私がより優れた MIPS コーダーだったら、あなたのためにそれを行うでしょう。それは次のようになります（疑似アセンブラです）


fix:
  compare r0, 0
  branch greater than x_positive
  subtract r1,r1,1
  call fix
  return;
//  or just jump fix instead

x_positive:
  compare r1, 0
  branch greater than i_positive
  subtract r0, r0, 1
  subtract r1, r1, 1
  call fix
  return
// or just  jmp fix

i_positive:
  move return register, 0
  return

面白いことに、C で書かれているように、これは常に 0 を返します :)


  fix:
    move return_register, 0
    return
于 2012-01-26T00:44:16.650 に答える