llvm dev - Jun 2006 - [LLVMdev] Removing dead code

Dear guys,

    I am working in a register allocator for LLVM, and I realized that,
after I perform register allocation, there is many move instructions that
are dead code, and can safely be removed. It is easy for the RA algorithm
to remove these instructions. It seems to me that the only instructions
with dead definitions that I should not remove are the calls. Is it true?
I would like to know if a code like this below is safe, that is, besides
call instructions, is there other instructions that must stay in the code
even if their definitions are dead?

MachineInstr * mi = iter;
opCode = // get the opcode of mi
if(!mi.isCall(opCode)) {
    mbb.remove(iter);
}

Thank you,

Fernando

On Thu, 29 Jun 2006, Fernando Magno Quintao Pereira
wrote:
>    I am working in a register allocator for LLVM, and I realized that,
> after I perform register allocation, there is many move instructions that
> are dead code, and can safely be removed. It is easy for the RA algorithm
> to remove these instructions. It seems to me that the only instructions
> with dead definitions that I should not remove are the calls. Is it true?
> I would like to know if a code like this below is safe, that is, besides
> call instructions, is there other instructions that must stay in the code
> even if their definitions are dead?
>
> MachineInstr * mi = iter;
> opCode = // get the opcode of mi
> if(!mi.isCall(opCode)) {
>    mbb.remove(iter);
> }
You can't do that unless you can prove the instructions don't have side 
effects, which you can't.  Higher-level passes will remove dead code.  Are 
you seeing a case where dead code is making it down to the codegen level?

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/

> > It seems to me that the only instructions
> > with dead definitions that I should not remove are the calls. Is it
true?
> > I would like to know if a code like this below is safe, that is,
besides
> > call instructions, is there other instructions that must stay in the
code
> > even if their definitions are dead?
> >
> > MachineInstr * mi = iter;
> > opCode = // get the opcode of mi
> > if(!mi.isCall(opCode)) {
> >    mbb.remove(iter);
> > }
>
> You can't do that unless you can prove the instructions don't have
side
> effects, which you can't.  Higher-level passes will remove dead code. 
Are
> you seeing a case where dead code is making it down to the codegen level?
>
> -Chris
>
I think so. LLVM is producing code like this one here, before RA:

----------------------------------------------------------------------------
entry (0x8605ba0, LLVM BB @0x8602d30):
        %reg1024 = OR4 %r3, %r3
        %reg1025 = OR4 %r4, %r4
        %reg1026 = LWZ 0, %reg1025
        %reg1027 = LIS <ga:.str_1>
        %reg1028 = LIS <ga:.str_2>
        %reg1029 = LBZ 0, %reg1026
        ADJCALLSTACKDOWN 56
        %reg1030 = IMPLICIT_DEF_GPR
        %reg1031 = LA %reg1027, <ga:.str_1>
        %r3 = OR4 %reg1031, %reg1031
        BL <ga:printf>, %r3
        %reg1032 = OR4 %r3, %r3      <-------------------
        %reg1033 = EXTSB %reg1029
        %reg1034 = LA %reg1028, <ga:.str_2>
        ADJCALLSTACKUP 56
        ADJCALLSTACKDOWN 56
        %r3 = OR4 %reg1034, %reg1034
        %r4 = OR4 %reg1033, %reg1033
        BL <ga:printf>, %r3, %r4
        %reg1035 = OR4 %r3, %r3
        ADJCALLSTACKUP 56
        %r3 = OR4 %reg1030, %reg1030
        BLR
----------------------------------------------------------- produced from:
#include <stdio.h>
int main(int argc, char ** argv) {
    int i;
    i = argv[0][0];
    printf("Hello, world\n");
    printf("i = %d\n", i);
}
--------------------------------------------------------------------------

where %reg1032 is dead. I'm removing these instructions. In Linear scan,
they are removed too. I'm removing all the dead
definitions from instructions that are not function calls, and the
resulting programs seem to work fine. The ratio of these instructions is
about 1:20, that is, for each 20 instructions (in PPC) the RA could remove
1 dead definition.

Fernando