LLVM - Liveness Analysis to remove dead code

Question

I'm trying to implement liveness analysis to remove dead instructions. I know that isInstructionTriviallyDead() exists, however, I want to learn how to remove code using def-use (or use-def) chains.

The way I am currently doing it is I am iterating through all the instructions in a block (using inst_iterator), and for each instruction, looping through all of its uses. Ultimately, if an instruction has no use, then I consider it dead, and can therefore remove it using eraseFromParent()

This looks something like:

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();
    }
}

The problem is, a return instruction has no uses assosciated with it (and I'm sure there are other definitions with no uses). However a return instruction shouldn't be removed as it'll lead to semantically incorrect code.

Is my general approach to removing instructions via liveness analysis okay? What can I do to ensure instructions like return are not removed?

Any pointers are much appreciated :)

Answer 1

You mentioned llvm::isInstructionTriviallyDead, and it's a good start to get some insights on what can be removed, and what cannot.

You already noticed that you can't remove terminator instruction.

Also, you don't want to remove instructions with no uses, but with side effects. Consider this:

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

You don't want to remove call instruction, even if it has no uses, because, it can, for example, write to stdout or change some global variable. Same thing goes for store's. Check Instruction::mayHaveSideEffects for the full list.

Your liveness analysis is too aggressive: no uses is necessary, but not sufficient condition for instruction to be considered dead.

If you do not want to use isInstructionTriviallyDead for learning purposes, I recommend you to start other way around: consider when instructions are dead for sure (for example, alloca is dead when there are no uses, so does add instruction...) and then generalize.

Additionally, simply loop through all instructions and removing dead ones is not sufficient. For example:

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

When you first encounter %2, it has a use in %3, so not dead. But after you eliminate %3 as dead, %2 becomes dead too. You can overcome this problem by iterating until no new dead instruction is found (ineffective, but simple), or by some recursive procedure.

Answer 2

I thinks before delete instruciton, you should judge its function firstly. With isa<>() to do this by

if (isa<ReturnInst>(instruction) || isa<BranchInst>(instruction) || ...) {
  deadInst = false;
}

Answer 3

also check whether the instruction is a terminator instruction (inst->isTerminator())