Стек =4 в байт-коде Java. Как компилятор Java вычисляет значение 4? (глубина стека)

Question

Java-код:

public class SimpleRecursion {

    public int factorial(int n) {
        if (n == 0) {
            return 1;
        }
        return n*factorial(n - 1);
    }

}

Дает следующий байт-код для факториального метода (я выполнил javap для его генерации):

public int factorial(int); 
descriptor: (I)I 
flags: ACC_PUBLIC 
Code:   
  stack=4, locals=2, args_size=2
     0: iload_1
     1: ifne          6
     4: iconst_1
     5: ireturn
     6: iload_1
     7: aload_0
     8: iload_1
     9: iconst_1
    10: isub
    11: invokevirtual #2                  // Method factorial:(I)I
    14: imul
    15: ireturn   
  LineNumberTable:
    line 4: 0
    line 5: 4
    line 7: 6   
  StackMapTable: number_of_entries = 1
    frame_type = 6 /* same */

Я понимаю, что в пятой строке в приведенном выше блоке стек =4 означает, что в стеке может быть не более 4 объектов.

Но как компилятор вычисляет это?

Answer 1

Поскольку начальное состояние стека, а также влияние каждой инструкции на него хорошо известно, вы можете точно предсказать, какой тип элементов будет в стеке операндов в любое время:

[ ]            // initially empty
[ I ]          0: iload_1
[ ]            1: ifne          6
[ I ]          4: iconst_1
[ ]            5: ireturn
[ I ]          6: iload_1
[ I O ]        7: aload_0
[ I O I ]      8: iload_1
[ I O I I ]    9: iconst_1
[ I O I ]     10: isub
[ I I ]       11: invokevirtual #2   // Method factorial:(I)I
[ I ]         14: imul
[ ]           15: ireturn   

Верификатор JVM будет делать именно это, прогнозируя содержимое стека после каждой инструкции, чтобы проверить, подходит ли он в качестве ввода следующей инструкции. Но здесь полезно иметь объявленный максимальный размер, поэтому верификатору не нужно поддерживать динамически растущую структуру данных или предварительно выделять память для теоретически возможных записей стека 64 КБ. С объявленным максимальным размером он может остановиться при обнаружении инструкции, которая будет выдвигать больше, чем это, поэтому ему никогда не нужно больше памяти, чем объявлено.

Как видите, заявленный максимальный размер стека достигается ровно один раз, сразу после iconst_1 инструкция по указателю 9.

Это, однако, не означает, что компилятор должен будет выполнять такой анализ команд. Компилятор имеет модель более высокого уровня кода, полученного из исходного кода, известного как Абстрактное синтаксическое дерево.

Эта структура будет использоваться для генерации результирующего байт-кода, и она также может уже предсказывать требуемый размер стека на этом уровне. Но то, как на самом деле это делает компилятор, зависит от реализации.