1d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman//===- DeadMachineInstructionElim.cpp - Remove dead machine instructions --===// 2d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman// 3d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman// The LLVM Compiler Infrastructure 4d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman// 5d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman// This file is distributed under the University of Illinois Open Source 6d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman// License. See LICENSE.TXT for details. 7d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman// 8d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman//===----------------------------------------------------------------------===// 9d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman// 10d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman// This is an extremely simple MachineInstr-level dead-code-elimination pass. 11d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman// 12d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman//===----------------------------------------------------------------------===// 13d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman 14d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman#include "llvm/CodeGen/Passes.h" 15d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 16d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman#include "llvm/CodeGen/MachineFunctionPass.h" 17d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman#include "llvm/CodeGen/MachineRegisterInfo.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h" 19723ac3720f6d983e0ed01504964fde1aa63951ffDan Gohman#include "llvm/Support/Debug.h" 209311a2283091f194f5b40490f3419cb0767a861dBill Wendling#include "llvm/Support/raw_ostream.h" 21d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman#include "llvm/Target/TargetInstrInfo.h" 22d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman#include "llvm/Target/TargetMachine.h" 23d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohmanusing namespace llvm; 24d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman 25dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "codegen-dce" 26dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 2700a99a35840451a291eb61a192a750908a4073aeEvan ChengSTATISTIC(NumDeletes, "Number of dead instructions deleted"); 2800a99a35840451a291eb61a192a750908a4073aeEvan Cheng 29d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohmannamespace { 306726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class DeadMachineInstructionElim : public MachineFunctionPass { 3136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnMachineFunction(MachineFunction &MF) override; 321df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick 333d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman const TargetRegisterInfo *TRI; 343d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman const MachineRegisterInfo *MRI; 353d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman const TargetInstrInfo *TII; 363d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman BitVector LivePhysRegs; 373d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman 38d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman public: 39d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman static char ID; // Pass identification, replacement for typeid 40081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson DeadMachineInstructionElim() : MachineFunctionPass(ID) { 41081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry()); 42081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 433d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman 443d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman private: 45d443ee68847c9af65b7c387c40e9e4038e660fdfDan Gohman bool isDead(const MachineInstr *MI) const; 46d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman }; 47d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman} 48d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohmanchar DeadMachineInstructionElim::ID = 0; 491dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::DeadMachineInstructionElimID = DeadMachineInstructionElim::ID; 50d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman 51d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(DeadMachineInstructionElim, "dead-mi-elimination", 52ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Remove dead machine instructions", false, false) 53d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman 54d443ee68847c9af65b7c387c40e9e4038e660fdfDan Gohmanbool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const { 55c36b7069b42bece963b7e6adf020353ce990ef76Evan Cheng // Technically speaking inline asm without side effects and no defs can still 56c36b7069b42bece963b7e6adf020353ce990ef76Evan Cheng // be deleted. But there is so much bad inline asm code out there, we should 57c36b7069b42bece963b7e6adf020353ce990ef76Evan Cheng // let them be. 58c36b7069b42bece963b7e6adf020353ce990ef76Evan Cheng if (MI->isInlineAsm()) 59c36b7069b42bece963b7e6adf020353ce990ef76Evan Cheng return false; 60c36b7069b42bece963b7e6adf020353ce990ef76Evan Cheng 613d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman // Don't delete instructions with side effects. 623d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman bool SawStore = false; 63dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!MI->isSafeToMove(TII, nullptr, SawStore) && !MI->isPHI()) 643d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman return false; 653d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman 663d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman // Examine each operand. 673d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 683d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman const MachineOperand &MO = MI->getOperand(i); 69d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.isDef()) { 703d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman unsigned Reg = MO.getReg(); 7139284d191af214f99736e6836be4f4ff9e8f1378Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 7239284d191af214f99736e6836be4f4ff9e8f1378Jakob Stoklund Olesen // Don't delete live physreg defs, or any reserved register defs. 73fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen if (LivePhysRegs.test(Reg) || MRI->isReserved(Reg)) 7439284d191af214f99736e6836be4f4ff9e8f1378Jakob Stoklund Olesen return false; 7539284d191af214f99736e6836be4f4ff9e8f1378Jakob Stoklund Olesen } else { 7639284d191af214f99736e6836be4f4ff9e8f1378Jakob Stoklund Olesen if (!MRI->use_nodbg_empty(Reg)) 7739284d191af214f99736e6836be4f4ff9e8f1378Jakob Stoklund Olesen // This def has a non-debug use. Don't delete the instruction! 7839284d191af214f99736e6836be4f4ff9e8f1378Jakob Stoklund Olesen return false; 793d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman } 803d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman } 813d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman } 823d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman 833d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman // If there are no defs with uses, the instruction is dead. 843d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman return true; 853d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman} 863d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman 87d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohmanbool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) { 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (skipOptnoneFunction(*MF.getFunction())) 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 91d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman bool AnyChanges = false; 923d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman MRI = &MF.getRegInfo(); 933d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman TRI = MF.getTarget().getRegisterInfo(); 943d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman TII = MF.getTarget().getInstrInfo(); 95d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman 96d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman // Loop over all instructions in all blocks, from bottom to top, so that it's 97d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman // more likely that chains of dependent but ultimately dead instructions will 98d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman // be cleaned up. 99d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman for (MachineFunction::reverse_iterator I = MF.rbegin(), E = MF.rend(); 100d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman I != E; ++I) { 101d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman MachineBasicBlock *MBB = &*I; 1028468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman 103f14a648d80bcb45fa07db35f8f1f58e47111dc9eJakob Stoklund Olesen // Start out assuming that reserved registers are live out of this block. 104fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen LivePhysRegs = MRI->getReservedRegs(); 1058468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman 106f27229ee5ad121247b9c79e7605b19fccf781d8dJakob Stoklund Olesen // Add live-ins from sucessors to LivePhysRegs. Normally, physregs are not 107f27229ee5ad121247b9c79e7605b19fccf781d8dJakob Stoklund Olesen // live across blocks, but some targets (x86) can have flags live out of a 108f27229ee5ad121247b9c79e7605b19fccf781d8dJakob Stoklund Olesen // block. 109f27229ee5ad121247b9c79e7605b19fccf781d8dJakob Stoklund Olesen for (MachineBasicBlock::succ_iterator S = MBB->succ_begin(), 110f27229ee5ad121247b9c79e7605b19fccf781d8dJakob Stoklund Olesen E = MBB->succ_end(); S != E; S++) 111f27229ee5ad121247b9c79e7605b19fccf781d8dJakob Stoklund Olesen for (MachineBasicBlock::livein_iterator LI = (*S)->livein_begin(); 112f27229ee5ad121247b9c79e7605b19fccf781d8dJakob Stoklund Olesen LI != (*S)->livein_end(); LI++) 113f27229ee5ad121247b9c79e7605b19fccf781d8dJakob Stoklund Olesen LivePhysRegs.set(*LI); 114f14a648d80bcb45fa07db35f8f1f58e47111dc9eJakob Stoklund Olesen 1158468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman // Now scan the instructions and delete dead ones, tracking physreg 1168468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman // liveness as we go. 117d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman for (MachineBasicBlock::reverse_iterator MII = MBB->rbegin(), 118d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman MIE = MBB->rend(); MII != MIE; ) { 119d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman MachineInstr *MI = &*MII; 120d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman 1213d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman // If the instruction is dead, delete it! 1223d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman if (isDead(MI)) { 12326045e25bf06a5b6476bd6f2d52a5d49da3c40d2David Greene DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI); 1242d1ec73d94941805de9f4392dbec052ce399ed58Dale Johannesen // It is possible that some DBG_VALUE instructions refer to this 1252d1ec73d94941805de9f4392dbec052ce399ed58Dale Johannesen // instruction. Examine each def operand for such references; 1262d1ec73d94941805de9f4392dbec052ce399ed58Dale Johannesen // if found, mark the DBG_VALUE as undef (but don't delete it). 1272d1ec73d94941805de9f4392dbec052ce399ed58Dale Johannesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1282d1ec73d94941805de9f4392dbec052ce399ed58Dale Johannesen const MachineOperand &MO = MI->getOperand(i); 1292d1ec73d94941805de9f4392dbec052ce399ed58Dale Johannesen if (!MO.isReg() || !MO.isDef()) 1302d1ec73d94941805de9f4392dbec052ce399ed58Dale Johannesen continue; 1312d1ec73d94941805de9f4392dbec052ce399ed58Dale Johannesen unsigned Reg = MO.getReg(); 1322d1ec73d94941805de9f4392dbec052ce399ed58Dale Johannesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1332d1ec73d94941805de9f4392dbec052ce399ed58Dale Johannesen continue; 13436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MRI->markUsesInDebugValueAsUndef(Reg); 1352d1ec73d94941805de9f4392dbec052ce399ed58Dale Johannesen } 1363d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman AnyChanges = true; 1373d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman MI->eraseFromParent(); 13800a99a35840451a291eb61a192a750908a4073aeEvan Cheng ++NumDeletes; 1393d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman MIE = MBB->rend(); 1403d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman // MII is now pointing to the next instruction to process, 1413d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman // so don't increment it. 1423d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman continue; 143d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman } 1448468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman 1458468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman // Record the physreg defs. 1468468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1478468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman const MachineOperand &MO = MI->getOperand(i); 148d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.isDef()) { 1498468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman unsigned Reg = MO.getReg(); 150c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 151b382c4dc235b78b606b305f1913fafc20eca472cDan Gohman // Check the subreg set, not the alias set, because a def 152b382c4dc235b78b606b305f1913fafc20eca472cDan Gohman // of a super-register may still be partially live after 153b382c4dc235b78b606b305f1913fafc20eca472cDan Gohman // this def. 15462c320a755ac27ac2b7f64e927892249e0f486e0Chad Rosier for (MCSubRegIterator SR(Reg, TRI,/*IncludeSelf=*/true); 15562c320a755ac27ac2b7f64e927892249e0f486e0Chad Rosier SR.isValid(); ++SR) 156396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen LivePhysRegs.reset(*SR); 1578468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman } 1586b88c180dad5eaa8361c5de2fa01c997f4f83368Jakob Stoklund Olesen } else if (MO.isRegMask()) { 1596b88c180dad5eaa8361c5de2fa01c997f4f83368Jakob Stoklund Olesen // Register mask of preserved registers. All clobbers are dead. 160478a8a02bc0f2e739ed8f4240152e99837e480b9Jakob Stoklund Olesen LivePhysRegs.clearBitsNotInMask(MO.getRegMask()); 1618468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman } 1628468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman } 1638468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman // Record the physreg uses, after the defs, in case a physreg is 1648468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman // both defined and used in the same instruction. 1658468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1668468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman const MachineOperand &MO = MI->getOperand(i); 167d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.isUse()) { 1688468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman unsigned Reg = MO.getReg(); 169c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 170f152fe8d487c46873bbdd4abab43200f783e978bJakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 171f152fe8d487c46873bbdd4abab43200f783e978bJakob Stoklund Olesen LivePhysRegs.set(*AI); 1728468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman } 1738468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman } 1748468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman } 1758468d1a84527ca5dbf0a6476b11fc0730810d2faDan Gohman 176d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman // We didn't delete the current instruction, so increment MII to 177d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman // the next one. 178d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman ++MII; 179d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman } 180d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman } 181d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman 1823d84a76917c4bb1e4d5b99009a7fb32970fb20b8Dan Gohman LivePhysRegs.clear(); 183d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman return AnyChanges; 184d3ead4329eaa46937245f5cc8402e749af2a37dcDan Gohman} 185