Качество компилятора

Сравнивая статистику операций со стеком, порождаемую скомпилированным кодом, с такой же статистикой для интерпретатора, ведущего то же самое вычисление, можно определить, насколько компилятор оптимизирует работу со стеком, как по скорости (уменьшая общее число стековых операций), так и по памяти (уменьшая максимальную глубину стека). Сравнение той же статистики с результатами работы специализированной машины, предназначенной для того же вычисления, дает некоторое представление о качестве компилятора.

а. В упражнении 5.27 от Вас требовалось определить как функцию от n число сохранений и максимальную глубину стека, которые требуются вычислителю для того, чтобы получить n! с помощью указанной факториальной процедуры. В упражнении 5.14 Вас просили провести те же измерения для специализированной факториальной машины, показанной на рисунке 5.11. Проведите теперь тот же анализ для скомпилированной процедуры factorial .

Возьмем отношение числа сохранений в скомпилированной версии к числу сохранений в интерпретируемой версии и проделаем то же для максимальной глубины стека. Поскольку число операций и глубина стека при вычислении n! линейно зависят от n , эти отношения должны приближаться к константам при росте n . Чему равны эти константы? Найдите также отношения показателей использования стека в специализированной машине к показателям интерпретируемой версии.

Сравните отношения специализированной версии к интерпретируемой и отношения скомпилированной версии к интерпретируемой. Вы должны увидеть, что специализированная машина работает намного лучше скомпилированного кода, поскольку настроенный вручную код контроллера должен быть намного лучше, чем результаты работы нашего рудиментарного компилятора общего назначения.

б. Можете ли Вы предложить изменения в компиляторе, помогающие ему порождать код, который приблизится к показателям версии, построенной вручную?

(controller
   (assign continue (label fact-done))     ; set up final return address
 fact-loop
   (test (op =) (reg n) (const 1))
   (branch (label base-case))
   ;; Set up for the recursive call by saving n and continue.
   ;; Set up continue so that the computation will continue
   ;; at after-fact when the subroutine returns.
   (save continue)
   (save n)
   (assign n (op -) (reg n) (const 1))
   (assign continue (label after-fact))
   (goto (label fact-loop))
 after-fact
   (restore n)
   (restore continue)
   (assign val (op *) (reg n) (reg val))   ; val now contains n(n - 1)!
   (goto (reg continue))                   ; return to caller
 base-case
   (assign val (const 1))                  ; base case: 1! = 1
   (goto (reg continue))                   ; return to caller
 fact-done)

Рис. 5.11. Рекурсивная факториальная машина.

---