1 //===---------------------- ProcessImplicitDefs.cpp -----------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #define DEBUG_TYPE "processimplicitdefs" 11 12 #include "llvm/ADT/SetVector.h" 13 #include "llvm/Analysis/AliasAnalysis.h" 14 #include "llvm/CodeGen/MachineFunctionPass.h" 15 #include "llvm/CodeGen/MachineInstr.h" 16 #include "llvm/CodeGen/MachineRegisterInfo.h" 17 #include "llvm/CodeGen/Passes.h" 18 #include "llvm/Support/Debug.h" 19 #include "llvm/Support/raw_ostream.h" 20 #include "llvm/Target/TargetInstrInfo.h" 21 22 using namespace llvm; 23 24 namespace { 25 /// Process IMPLICIT_DEF instructions and make sure there is one implicit_def 26 /// for each use. Add isUndef marker to implicit_def defs and their uses. 27 class ProcessImplicitDefs : public MachineFunctionPass { 28 const TargetInstrInfo *TII; 29 const TargetRegisterInfo *TRI; 30 MachineRegisterInfo *MRI; 31 32 SmallSetVector<MachineInstr*, 16> WorkList; 33 34 void processImplicitDef(MachineInstr *MI); 35 bool canTurnIntoImplicitDef(MachineInstr *MI); 36 37 public: 38 static char ID; 39 40 ProcessImplicitDefs() : MachineFunctionPass(ID) { 41 initializeProcessImplicitDefsPass(*PassRegistry::getPassRegistry()); 42 } 43 44 virtual void getAnalysisUsage(AnalysisUsage &au) const; 45 46 virtual bool runOnMachineFunction(MachineFunction &fn); 47 }; 48 } // end anonymous namespace 49 50 char ProcessImplicitDefs::ID = 0; 51 char &llvm::ProcessImplicitDefsID = ProcessImplicitDefs::ID; 52 53 INITIALIZE_PASS_BEGIN(ProcessImplicitDefs, "processimpdefs", 54 "Process Implicit Definitions", false, false) 55 INITIALIZE_PASS_END(ProcessImplicitDefs, "processimpdefs", 56 "Process Implicit Definitions", false, false) 57 58 void ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const { 59 AU.setPreservesCFG(); 60 AU.addPreserved<AliasAnalysis>(); 61 MachineFunctionPass::getAnalysisUsage(AU); 62 } 63 64 bool ProcessImplicitDefs::canTurnIntoImplicitDef(MachineInstr *MI) { 65 if (!MI->isCopyLike() && 66 !MI->isInsertSubreg() && 67 !MI->isRegSequence() && 68 !MI->isPHI()) 69 return false; 70 for (MIOperands MO(MI); MO.isValid(); ++MO) 71 if (MO->isReg() && MO->isUse() && MO->readsReg()) 72 return false; 73 return true; 74 } 75 76 void ProcessImplicitDefs::processImplicitDef(MachineInstr *MI) { 77 DEBUG(dbgs() << "Processing " << *MI); 78 unsigned Reg = MI->getOperand(0).getReg(); 79 80 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 81 // For virtual regiusters, mark all uses as <undef>, and convert users to 82 // implicit-def when possible. 83 for (MachineRegisterInfo::use_nodbg_iterator UI = 84 MRI->use_nodbg_begin(Reg), 85 UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 86 MachineOperand &MO = UI.getOperand(); 87 MO.setIsUndef(); 88 MachineInstr *UserMI = MO.getParent(); 89 if (!canTurnIntoImplicitDef(UserMI)) 90 continue; 91 DEBUG(dbgs() << "Converting to IMPLICIT_DEF: " << *UserMI); 92 UserMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); 93 WorkList.insert(UserMI); 94 } 95 MI->eraseFromParent(); 96 return; 97 } 98 99 // This is a physreg implicit-def. 100 // Look for the first instruction to use or define an alias. 101 MachineBasicBlock::instr_iterator UserMI = MI; 102 MachineBasicBlock::instr_iterator UserE = MI->getParent()->instr_end(); 103 bool Found = false; 104 for (++UserMI; UserMI != UserE; ++UserMI) { 105 for (MIOperands MO(UserMI); MO.isValid(); ++MO) { 106 if (!MO->isReg()) 107 continue; 108 unsigned UserReg = MO->getReg(); 109 if (!TargetRegisterInfo::isPhysicalRegister(UserReg) || 110 !TRI->regsOverlap(Reg, UserReg)) 111 continue; 112 // UserMI uses or redefines Reg. Set <undef> flags on all uses. 113 Found = true; 114 if (MO->isUse()) 115 MO->setIsUndef(); 116 } 117 if (Found) 118 break; 119 } 120 121 // If we found the using MI, we can erase the IMPLICIT_DEF. 122 if (Found) { 123 DEBUG(dbgs() << "Physreg user: " << *UserMI); 124 MI->eraseFromParent(); 125 return; 126 } 127 128 // Using instr wasn't found, it could be in another block. 129 // Leave the physreg IMPLICIT_DEF, but trim any extra operands. 130 for (unsigned i = MI->getNumOperands() - 1; i; --i) 131 MI->RemoveOperand(i); 132 DEBUG(dbgs() << "Keeping physreg: " << *MI); 133 } 134 135 /// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into 136 /// <undef> operands. 137 bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &MF) { 138 139 DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n" 140 << "********** Function: " << MF.getName() << '\n'); 141 142 bool Changed = false; 143 144 TII = MF.getTarget().getInstrInfo(); 145 TRI = MF.getTarget().getRegisterInfo(); 146 MRI = &MF.getRegInfo(); 147 assert(MRI->isSSA() && "ProcessImplicitDefs only works on SSA form."); 148 assert(WorkList.empty() && "Inconsistent worklist state"); 149 150 for (MachineFunction::iterator MFI = MF.begin(), MFE = MF.end(); 151 MFI != MFE; ++MFI) { 152 // Scan the basic block for implicit defs. 153 for (MachineBasicBlock::instr_iterator MBBI = MFI->instr_begin(), 154 MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) 155 if (MBBI->isImplicitDef()) 156 WorkList.insert(MBBI); 157 158 if (WorkList.empty()) 159 continue; 160 161 DEBUG(dbgs() << "BB#" << MFI->getNumber() << " has " << WorkList.size() 162 << " implicit defs.\n"); 163 Changed = true; 164 165 // Drain the WorkList to recursively process any new implicit defs. 166 do processImplicitDef(WorkList.pop_back_val()); 167 while (!WorkList.empty()); 168 } 169 return Changed; 170 } 171
