7

変数を定義しているときに関数が自分自身を呼び出すと、スタックオーバーフローが発生しますか? gcc に同じスタックを再利用するオプションはありますか。

void funcnew(void)
{
   int a=10;
   int b=20;
   funcnew();
   return ;
 }

関数は以前に使用したスタック フレームを再利用できますか? 末尾再帰で同じフレームを再利用する gcc のオプションは何ですか??

4

6 に答える 6

5

はい。見る

-foptimize-sibling-calls

兄弟再帰呼び出しと末尾再帰呼び出しを最適化します。

レベル -O2、-O3、-Os で有効。

関数は次のようにコンパイルされます。

funcstack:
.LFB0:
    .cfi_startproc
    xorl    %eax, %eax
    jmp func
    .cfi_endproc

（関数へのジャンプに注意してください）

関数が呼び出しで終了するときにスタック フレームを再利用すること (これには、スタックを操作してパラメーターを正しい場所に配置し、関数呼び出しを関数の先頭へのジャンプに置き換えることが含まれます) はよく知られています。 [i]テールコールの除去[/i]と呼ばれる最適化。一部の言語 (たとえばスキーム) では、再帰呼び出しが義務付けられています (再帰呼び出しは、これらの言語でループを表現する自然な方法です)。上記のように、gcc には C 用に実装された最適化がありますが、他のどのコンパイラがそれを実装しているかはわかりません。移植可能なコードには依存しません。また、どの制限があるのか​​ わからないことに注意してください-たとえば、パラメーターの型が異なる場合、gccがスタックを操作するかどうかはわかりません。

于 2010-02-12T09:37:09.747 に答える
3

パラメータを定義しなくても、stackoverflowが発生します。リターンアドレスもスタックにプッシュされるため。

（私は最近これを学びました）コンパイラがループを末尾再帰に最適化する可能性があります（これによりスタックがまったく成長しなくなります）。SOの末尾再帰の質問へのリンク

于 2010-02-12T09:33:08.273 に答える
0

いいえ、各再帰は新しいスタック フレームです。再帰が無限に深い場合、必要なスタックも無限になるため、スタック オーバーフローが発生します。

于 2010-02-12T09:24:10.680 に答える
0

他の人が指摘したように、(1) コンパイラが末尾呼び出しの最適化をサポートし、(2) 関数がそのような最適化に適している場合にのみ可能です。最適化は、既存のスタックを再利用し、CALL の代わりに JMP (つまり、アセンブリでの GOTO) を実行することです。

実際、サンプル関数は実際にそのような最適化に適しています。その理由は、関数が戻る前に最後に行うことは、それ自体を呼び出すことだからです。への最後の呼び出しの後、何もする必要はありませんfuncnew()。ただし、このような最適化を実行できるのは特定のコンパイラのみです。たとえば、GCCはそれを行います。詳細については、「末尾再帰の最適化を行う C++ コンパイラがある場合はどれですか?」を参照してください。

これに関する古典的な資料は階乗関数です。末尾呼び出し最適化 (TCO) に適さない再帰階乗関数を作成してみましょう。

int fact(int n)
{
  if ( n == 1 ) return 1;
  return n*fact(n-1);
}

n最後に、 の結果を乗算しfact(n-1)ます。この最後の操作をどうにかして排除することで、スタックを再利用できるようになります。答えを計算するアキュムレータ変数を導入しましょう。

int fact_helper(int n, int acc)
{
  if ( n == 1 ) return acc;
  return fact_helper(n-1, n*acc);
}

int fact_acc(int n)
{
  return fact_helper(n, 1);
}

関数fact_helperは作業を行いfact_accますが、アキュムレータ変数を初期化するための単なる便利な関数です。

最後fact_helperに自分自身を呼び出す方法に注意してください。この CALL は、変数の既存のスタックを再利用することで JMP に変換できます。

GCC を使用すると、生成されたアセンブリを確認することで、ジャンプに最適化されていることを確認できます。たとえば、次のようになりますgcc -c -O3 -Wa,-a,-ad fact.c。

  ...
  37                    L12:
  38 0040 0FAFC2                imull   %edx, %eax
  39 0043 83EA01                subl    $1, %edx
  40 0046 83FA01                cmpl    $1, %edx
  41 0049 75F5                  jne     L12
  ...

Schemeなどの一部のプログラミング言語は、適切な実装がそのような最適化を実行することを実際に保証します。彼らは、非再帰的な末尾呼び出しに対してもそれを行います。

于 2011-05-13T13:53:32.063 に答える
0

はい、場合によっては、コンパイラが末尾呼び出しの最適化と呼ばれるものを実行できる場合があります。コンパイラのマニュアルで確認してください。(AProgrammer は回答で GCC マニュアルを引用しているようです。)

これは、このようなコードが頻繁に発生する関数型言語などを実装する場合に不可欠な最適化です。

于 2010-02-12T09:37:44.690 に答える
0

リターンアドレスに必要なため、スタックフレームを完全になくすことはできません。末尾再帰を使用しておらず、コンパイラがそれをループに最適化している場合を除きます。しかし、完全に技術的に正直に言うと、フレーム内のすべての変数を静的にすることで取り除くことができます。しかし、これはあなたがやりたいことではないことはほぼ確実であり、何をしているのかを正確に知らずにそれを行うべきではありません。

于 2010-02-12T09:38:25.140 に答える