Резервные базовые блоки в llvm IR - PullRequest
Новая
       12

Резервные базовые блоки в llvm IR

0 голосов
/ 12 ноября 2018

Я просто играл с программой и смотрел ее ИК в llvm, и я заметил некоторые основные блоки, которые не имеют смысла для меня. Мой код: 

void proc()
{
    int i, j, k, m, n, l;
    k = 119;
    for (i = 20; i < 200; i++)
    {
        for (j = 13; j < 130; j++)
        {
                l = 80;
        }
    }
}

Соответствующий ИК: 

 store i32 119, i32* %3, align 4
  store i32 20, i32* %1, align 4
  br label %7

; <label>:7:                                      ; preds = %19, %0
  %8 = load i32, i32* %1, align 4
  %9 = icmp slt i32 %8, 200
  br i1 %9, label %10, label %22

; <label>:10:                                     ; preds = %7
  store i32 13, i32* %2, align 4
  br label %11

; <label>:11:                                     ; preds = %15, %10
  %12 = load i32, i32* %2, align 4
  %13 = icmp slt i32 %12, 130
  br i1 %13, label %14, label %18

; <label>:14:                                     ; preds = %11
  store i32 80, i32* %6, align 4
  br label %15

; <label>:15:                                     ; preds = %14
  %16 = load i32, i32* %2, align 4
  %17 = add nsw i32 %16, 1
  store i32 %17, i32* %2, align 4
  br label %11

; <label>:18:                                     ; preds = %11
  br label %19

; <label>:19:                                     ; preds = %18
  %20 = load i32, i32* %1, align 4
  %21 = add nsw i32 %20, 1
  store i32 %21, i32* %1, align 4
  br label %7

; <label>:22:                                     ; preds = %7
  ret void

Моя проблема с метками 14 и 15. Похоже, что у метки 15 есть только один предшественник, 14. Учитывая это, почему мы не можем просто объединить ее с меткой 14? Я предполагаю, что базовое построение блока выполняется по алгоритму, указанному здесь .

1 Ответ

0 голосов
/ 14 ноября 2018

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

Код LLVM всегда структурирован в базовые блоки, а типы, используемые для представления кода LLVM в API, уже образуют граф потока управления. Не может быть неструктурированной формы LLVM без базовых блоков и, следовательно, нет процесса преобразования неструктурированной LLVM в CFG. Clang напрямую переводит C AST в LLVM. Таким образом, он не находит основные блоки в неструктурированном трехадресном коде, он находит основные блоки при переводе из C в LLVM за один шаг. Поэтому алгоритм из Википедии не применяется.

То, что происходит вместо этого, суммируется следующим сильно упрощенным псевдокодом, свободно основанным на CodeGenFunction :: EmitForStmt в CodeGen / CGStmt.cpp . Это логика для перевода утверждения вида for(init; cond; incr) body. Для простоты мы предполагаем, что ни cond, ни incr не пусты и что cond является выражением, а не объявлением.

  • Создание новых базовых блоков: conditionBlock, bodyBlock, incrBlock и exitBlock
  • добавить код для init к текущему базовому блоку с последующим переходом к conditionBlock
  • добавить код для cond до conditionBlock, затем br i1 %cond, label %bodyBlock, label %exitBlock
  • Нажмите {break: exitBlock, continue: incrBlock} на стек прерывания / продолжения
  • добавить код для body в bodyBlock, после чего перейти к conditionBlock
  • Вставить стек перерыв / продолжить
  • Установить exitBlock в качестве текущего базового блока

Чтобы получить результат, который вы ожидали, он должен будет выдать код для incr в bodyBlock вместо того, чтобы иметь отдельный блок для него. Но тогда он не мог вставить incrBlock в стек прерывания / продолжения. Конечно, это не имеет значения в вашем случае, так как ваш код не содержит никаких операторов continue, но в общем случае компилятору нужен стек break / continue, чтобы знать, куда переходить в случае break s или continue s.

Таким образом, компилятор просто всегда генерирует эти блоки, а затем ненужные блоки объединяются на этапе оптимизации.

...