X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FDeadMachineInstructionElim.cpp;h=f3be2abacd70529b4bb8421ccb7ce38d98515cf0;hb=fe0bf8fbf9d401a67a1842da6cefbb58aa8975a3;hp=8b9cf05d675223a346bfa19eaf3bcadadbc4ab46;hpb=e251b1529f40131ce5931420448a1e847f42e4af;p=oota-llvm.git diff --git a/lib/CodeGen/DeadMachineInstructionElim.cpp b/lib/CodeGen/DeadMachineInstructionElim.cpp index 8b9cf05d675..f3be2abacd7 100644 --- a/lib/CodeGen/DeadMachineInstructionElim.cpp +++ b/lib/CodeGen/DeadMachineInstructionElim.cpp @@ -12,39 +12,88 @@ //===----------------------------------------------------------------------===// #include "llvm/CodeGen/Passes.h" -#include "llvm/Pass.h" +#include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/Support/Compiler.h" +#include "llvm/Pass.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetSubtargetInfo.h" + using namespace llvm; +#define DEBUG_TYPE "codegen-dce" + +STATISTIC(NumDeletes, "Number of dead instructions deleted"); + namespace { - class VISIBILITY_HIDDEN DeadMachineInstructionElim : - public MachineFunctionPass { - virtual bool runOnMachineFunction(MachineFunction &MF); - + class DeadMachineInstructionElim : public MachineFunctionPass { + bool runOnMachineFunction(MachineFunction &MF) override; + + const TargetRegisterInfo *TRI; + const MachineRegisterInfo *MRI; + const TargetInstrInfo *TII; + BitVector LivePhysRegs; + public: static char ID; // Pass identification, replacement for typeid - DeadMachineInstructionElim() : MachineFunctionPass(&ID) {} + DeadMachineInstructionElim() : MachineFunctionPass(ID) { + initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry()); + } + + private: + bool isDead(const MachineInstr *MI) const; }; } char DeadMachineInstructionElim::ID = 0; +char &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID; + +INITIALIZE_PASS(DeadMachineInstructionElim, "dead-mi-elimination", + "Remove dead machine instructions", false, false) -static RegisterPass -Y("dead-mi-elimination", - "Remove dead machine instructions"); +bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const { + // Technically speaking inline asm without side effects and no defs can still + // be deleted. But there is so much bad inline asm code out there, we should + // let them be. + if (MI->isInlineAsm()) + return false; -FunctionPass *llvm::createDeadMachineInstructionElimPass() { - return new DeadMachineInstructionElim(); + // Don't delete instructions with side effects. + bool SawStore = false; + if (!MI->isSafeToMove(TII, nullptr, SawStore) && !MI->isPHI()) + return false; + + // Examine each operand. + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (MO.isReg() && MO.isDef()) { + unsigned Reg = MO.getReg(); + if (TargetRegisterInfo::isPhysicalRegister(Reg)) { + // Don't delete live physreg defs, or any reserved register defs. + if (LivePhysRegs.test(Reg) || MRI->isReserved(Reg)) + return false; + } else { + if (!MRI->use_nodbg_empty(Reg)) + // This def has a non-debug use. Don't delete the instruction! + return false; + } + } + } + + // If there are no defs with uses, the instruction is dead. + return true; } bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) { + if (skipOptnoneFunction(*MF.getFunction())) + return false; + bool AnyChanges = false; - const MachineRegisterInfo &MRI = MF.getRegInfo(); - const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo(); - bool SawStore = true; + MRI = &MF.getRegInfo(); + TRI = MF.getSubtarget().getRegisterInfo(); + TII = MF.getSubtarget().getInstrInfo(); // Loop over all instructions in all blocks, from bottom to top, so that it's // more likely that chains of dependent but ultimately dead instructions will @@ -52,49 +101,77 @@ bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) { for (MachineFunction::reverse_iterator I = MF.rbegin(), E = MF.rend(); I != E; ++I) { MachineBasicBlock *MBB = &*I; + + // Start out assuming that reserved registers are live out of this block. + LivePhysRegs = MRI->getReservedRegs(); + + // Add live-ins from sucessors to LivePhysRegs. Normally, physregs are not + // live across blocks, but some targets (x86) can have flags live out of a + // block. + for (MachineBasicBlock::succ_iterator S = MBB->succ_begin(), + E = MBB->succ_end(); S != E; S++) + for (MachineBasicBlock::livein_iterator LI = (*S)->livein_begin(); + LI != (*S)->livein_end(); LI++) + LivePhysRegs.set(*LI); + + // Now scan the instructions and delete dead ones, tracking physreg + // liveness as we go. for (MachineBasicBlock::reverse_iterator MII = MBB->rbegin(), MIE = MBB->rend(); MII != MIE; ) { MachineInstr *MI = &*MII; - // Don't delete instructions with side effects. - if (MI->isSafeToMove(&TII, SawStore)) { - // Examine each operand. - bool AllDefsDead = true; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); - if (MO.isRegister() && MO.isDef()) { - unsigned Reg = MO.getReg(); - if ((!MO.isImplicit() && - TargetRegisterInfo::isPhysicalRegister(Reg)) || - !MRI.use_empty(Reg)) { - // This def has a use. Don't delete the instruction! - AllDefsDead = false; - break; - } + // If the instruction is dead, delete it! + if (isDead(MI)) { + DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI); + // It is possible that some DBG_VALUE instructions refer to this + // instruction. They get marked as undef and will be deleted + // in the live debug variable analysis. + MI->eraseFromParentAndMarkDBGValuesForRemoval(); + AnyChanges = true; + ++NumDeletes; + MIE = MBB->rend(); + // MII is now pointing to the next instruction to process, + // so don't increment it. + continue; + } + + // Record the physreg defs. + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (MO.isReg() && MO.isDef()) { + unsigned Reg = MO.getReg(); + if (TargetRegisterInfo::isPhysicalRegister(Reg)) { + // Check the subreg set, not the alias set, because a def + // of a super-register may still be partially live after + // this def. + for (MCSubRegIterator SR(Reg, TRI,/*IncludeSelf=*/true); + SR.isValid(); ++SR) + LivePhysRegs.reset(*SR); } + } else if (MO.isRegMask()) { + // Register mask of preserved registers. All clobbers are dead. + LivePhysRegs.clearBitsNotInMask(MO.getRegMask()); } - - // If there are no defs with uses, the instruction is dead. - if (AllDefsDead) { - // Clear out the operands to take the registers out of their - // use chains. - while (unsigned Num = MI->getNumOperands()) - MI->RemoveOperand(Num-1); - - // Delete the actual instruction. - AnyChanges = true; - MI->eraseFromParent(); - MIE = MBB->rend(); - // MII is now pointing to the next instruction to process, - // so don't increment it. - continue; + } + // Record the physreg uses, after the defs, in case a physreg is + // both defined and used in the same instruction. + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (MO.isReg() && MO.isUse()) { + unsigned Reg = MO.getReg(); + if (TargetRegisterInfo::isPhysicalRegister(Reg)) { + for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) + LivePhysRegs.set(*AI); + } } } + // We didn't delete the current instruction, so increment MII to // the next one. ++MII; } } + LivePhysRegs.clear(); return AnyChanges; }