Вопрос или проблема
Я компилирую простую программу на C, реализующую функцию обхода дерева в симметричном порядке:
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
Затем я компилирую .c файл с помощью: gcc inorder.c -O2 -o inorder_O2
Когда я пытаюсь декомпилировать файл inorder_O2 с помощью BinaryNinja, я получаю версию этой функции на высоком уровне IL:
void inorderTraversal(int32_t* arg1){
int32_t* i_1 = arg1
if (arg1 != 0)
int32_t* i
do
int32_t* j_2 = *(i_1 + 8)
int32_t* j_1 = j_2
if (j_2 != 0)
int32_t* j
do
int32_t* k_2 = *(j_1 + 8)
int32_t* k_1 = k_2
if (k_2 != 0)
int32_t* k
do
int32_t* r15_1 = *(k_1 + 8)
if (r15_1 != 0)
do
int32_t* rbx_1 = *(r15_1 + 8)
if (rbx_1 != 0)
do
int32_t* r13_1 = *(rbx_1 + 8)
if (r13_1 != 0)
do
int32_t* r12_1 = *(r13_1 + 8)
if (r12_1 != 0)
do
int32_t* r14_1 = *(r12_1 + 8)
if (r14_1 != 0)
do
int32_t* r9_1 = *(r14_1 + 8)
if (r9_1 != 0)
do
inorderTraversal(*(r9_1 + 8))
__printf_chk(flag: 1, format: &data_2004, zx.q(*r9_1))
r9_1 = *(r9_1 + 0x10)
while (r9_1 != 0)
__printf_chk(flag: 1, format: &data_2004, zx.q(*r14_1))
r14_1 = *(r14_1 + 0x10)
while (r14_1 != 0)
__printf_chk(flag: 1, format: &data_2004, zx.q(*r12_1))
r12_1 = *(r12_1 + 0x10)
while (r12_1 != 0)
__printf_chk(flag: 1, format: &data_2004, zx.q(*r13_1))
r13_1 = *(r13_1 + 0x10)
while (r13_1 != 0)
__printf_chk(flag: 1, format: &data_2004, zx.q(*rbx_1))
rbx_1 = *(rbx_1 + 0x10)
while (rbx_1 != 0)
__printf_chk(flag: 1, format: &data_2004, zx.q(*r15_1))
r15_1 = *(r15_1 + 0x10)
while (r15_1 != 0)
__printf_chk(flag: 1, format: &data_2004, zx.q(*k_1))
k = *(k_1 + 0x10)
k_1 = k
while (k != 0)
__printf_chk(flag: 1, format: &data_2004, zx.q(*j_1))
j = *(j_1 + 0x10)
j_1 = j
while (j != 0)
__printf_chk(flag: 1, format: &data_2004, zx.q(*i_1))
i = *(i_1 + 0x10)
i_1 = i
while (i != 0)
}
Я предполагаю, что проводится устранение хвостовой рекурсии, поскольку остался только один рекурсивный вызов. Что я не знаю, так это то, что делает функцию таким большим количеством вложенных циклов? Есть ли точное название оптимизации компилятора для этого?
То есть, я в основном хочу знать название или описание техники, а не параметр компилятора, чтобы включить или отключить это.
Ответ или решение
Ваша программа на C реализует обход дерева в глубину с использованием рекурсии. При компиляции с оптимизацией уровня O2 компилятор GCC применяет несколько улучшений для оптимизации представленного кода. Как вы правильно заметили, происходит устранение хвостовой рекурсии, однако, помимо этого, компилятор применяет некоторые другие техники, которые могут объяснить преобразование рекурсивных вызовов в вложенные циклы.
Оптимизация "Рекурсивная распаковка"
Одной из ключевых оптимизаций, применяемых компилятором в данном случае, является "рекурсивная распаковка" (или "recursion unrolling"). При использовании этой оптимизации компилятор преобразует рекурсивные вызовы в эквивалентные циклы, что позволяет устранить накладные расходы на вызовы функций и увеличить производительность.
В вашем случае, из-за того что функция реализует обход дерева, компилятор распаковывает рекурсию, так как структура дерева может быть динамически изменена, и с помощью циклов, представляющих логику обхода, можно избежать множества накладных расходов, связанных с вызовами функций при рекурсии.
Другие техники оптимизации
-
Инлинеаризация: В зависимости от ситуации, компилятор может применять инлайнинг для функций, особенно в случае простых (и используемых многократно) рекурсивных вызовов.
-
Удаление ненужных проверок: Компилятор может также оптимизировать проверки на
NULL, если обнаружит, что эти проверки всегда будут истинными или ложными при определенных условиях. - Оптимизация обращений к памяти: Визуально удается наблюдать, что обращения к указателям (особенно в функции
inorderTraversal) оптимизированы для улучшения производительности, чтобы минимизировать количество обращений к памяти.
Заключение
Таким образом, основная причина, по которой рекурсивные вызовы были преобразованы в длинные циклы, связана с оптимизацией рекурсивной распаковки. Это позволяет улучшить производительность программы, снизив накладные расходы на стек вызовов и увеличивая скорость выполнения программы. Каждая из вышеперечисленных техник может играть свою роль в этом процессе, но именно "рекурсивная распаковка" лежит в основе преобразования рекурсивных вызовов в циклы в вашем коде.