> > 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
On Fri, 2006-06-30 at 10:26 -0700, Fernando Magno Quintao Pereira wrote:> > > > 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:That is because the physical register has to be copied to a virtual register. Without the copy, physical registers could be alive across basic blocks. There is a function you can call for each target to tell you if an instruction is a copy. Andrew> ---------------------------------------------------------------------------- > 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 > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
On Fri, 30 Jun 2006, Fernando Magno Quintao Pereira wrote:> where %reg1032 is dead.Right. One of the jobs of the register allocator is to coallesce register copies. Once coallesced, they can be removed.> 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 ratioI suggest you do more testing. For copies, this is clearly fine, but for general instructions, it isn't.> of these instructions is about 1:20, that is, for each 20 instructions > (in PPC) the RA could remove 1 dead definition.Again, how many of these are copies? We expect that the register allocator will make copies dead and remove them. Are you removing any non-copy instructions? -Chris -- http://nondot.org/sabre/ http://llvm.org/
> > where %reg1032 is dead. > > Right. One of the jobs of the register allocator is to coallesce register > copies. Once coallesced, they can be removed. > > > 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 > > I suggest you do more testing. For copies, this is clearly fine, but for > general instructions, it isn't. > > Again, how many of these are copies? We expect that the register > allocator will make copies dead and remove them. Are you removing any > non-copy instructions? >I think this is not a coalescing issue. The coalesced copies are removed by the code generator of LLVM, and do not appear in the final assembly code. I think that these dead definitions are due to function calls that return void. In the programs that I tested, the only dead definitions were in copy instructions (but I am not able yet to run the RA in big programs). I will do as you guys suggested and will replace the test for non-function call for a test for copy instructions. Actually, there are other instructions besides CALLs that can also produce side effects, such as DIVs. Fernando