LLVM - Анализ Liveness для удаления мертвого кода

Question

Я пытаюсь реализовать анализ активности, чтобы удалить мертвые инструкции. Я знаю, что существует isInstructionTriviallyDead(), но я хочу узнать, как удалить код, используя def-use (или use-def) цепочки.

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

Это выглядит примерно так:

for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 
    bool deadInst = true; 
    Instruction *inst = &*I; 


    for (User* pUser : inst->users()) { 
     // If we enter this loop, we have at least one use, so instruction isn't dead 
     deadInst = false; 
    } 

    // deadInst is true if we didn't enter the loop, so has no uses 
    if (deadInst) { 
     inst->eraseFromParent(); 
    } 
} 

Проблема есть, команда возврата не имеет применения assosciated с это (и я уверен, что есть другие определения без использования). Однако команда возврата не должна удаляться, так как это приведет к получению семантически неправильного кода.

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

Все указатели очень ценятся :)

Answer 1

также проверить инструкция является ли инструкция терминатор (inst->isTerminator())

Answer 2

Вы упомянули llvm::isInstructionTriviallyDead, и это хорошее начало, чтобы получить некоторое представление о том, что могут быть удалены, и что не может.

Вы уже заметили, что вы не можете удалить инструкцию терминатора.

Кроме того, вы не хотите удалять инструкции без использования, но с побочными эффектами. Рассмотрим это:

define void @bar()() { 
    call void @foo()() 
    ret void 
} 

Вы не хотите, чтобы удалить call инструкцию, даже если он не имеет пользы, потому что, он может, например, записать на стандартный вывод или изменить некоторые глобальные переменные. То же самое касается store. Для получения полного списка проверьте Instruction::mayHaveSideEffects.

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

Если вы не хотите использовать isInstructionTriviallyDead для целей обучения, я рекомендую вам начать наоборот: рассмотреть, когда инструкции мертвы наверняка (например, alloca мертв, когда нет использования, так что делает add инструкции. ..), а затем обобщить.

Кроме того, просто выполнить все инструкции и удалить мертвые недостаточно. Например:

%2 = add i32 3, %1 
%3 = add i32 3, %2 

При первой встречи %2, имеет применение в %3, так что не умер. Но после того, как вы устраните %3 как мертвый, %2 тоже будет мертв. Вы можете преодолеть эту проблему, итерации до тех пор, пока не будет найдена новая мертвая инструкция (неэффективная, но простая) или какой-либо рекурсивной процедурой.