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/CodeGen/ProcessImplicitDefs.h" 13 14 #include "llvm/ADT/DepthFirstIterator.h" 15 #include "llvm/ADT/SmallSet.h" 16 #include "llvm/Analysis/AliasAnalysis.h" 17 #include "llvm/CodeGen/LiveVariables.h" 18 #include "llvm/CodeGen/MachineInstr.h" 19 #include "llvm/CodeGen/MachineRegisterInfo.h" 20 #include "llvm/CodeGen/Passes.h" 21 #include "llvm/Support/Debug.h" 22 #include "llvm/Target/TargetInstrInfo.h" 23 #include "llvm/Target/TargetRegisterInfo.h" 24 25 26 using namespace llvm; 27 28 char ProcessImplicitDefs::ID = 0; 29 static RegisterPass<ProcessImplicitDefs> X("processimpdefs", 30 "Process Implicit Definitions."); 31 32 void ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const { 33 AU.setPreservesCFG(); 34 AU.addPreserved<AliasAnalysis>(); 35 AU.addPreserved<LiveVariables>(); 36 AU.addRequired<LiveVariables>(); 37 AU.addPreservedID(MachineLoopInfoID); 38 AU.addPreservedID(MachineDominatorsID); 39 AU.addPreservedID(TwoAddressInstructionPassID); 40 AU.addPreservedID(PHIEliminationID); 41 MachineFunctionPass::getAnalysisUsage(AU); 42 } 43 44 bool ProcessImplicitDefs::CanTurnIntoImplicitDef(MachineInstr *MI, 45 unsigned Reg, unsigned OpIdx, 46 const TargetInstrInfo *tii_) { 47 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 48 if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) && 49 Reg == SrcReg && DstSubReg == 0) 50 return true; 51 52 switch(OpIdx) { 53 case 1: return MI->isCopy() && MI->getOperand(0).getSubReg() == 0; 54 case 2: return MI->isSubregToReg() && MI->getOperand(0).getSubReg() == 0; 55 default: return false; 56 } 57 } 58 59 /// processImplicitDefs - Process IMPLICIT_DEF instructions and make sure 60 /// there is one implicit_def for each use. Add isUndef marker to 61 /// implicit_def defs and their uses. 62 bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &fn) { 63 64 DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n" 65 << "********** Function: " 66 << ((Value*)fn.getFunction())->getName() << '\n'); 67 68 bool Changed = false; 69 70 const TargetInstrInfo *tii_ = fn.getTarget().getInstrInfo(); 71 const TargetRegisterInfo *tri_ = fn.getTarget().getRegisterInfo(); 72 MachineRegisterInfo *mri_ = &fn.getRegInfo(); 73 74 LiveVariables *lv_ = &getAnalysis<LiveVariables>(); 75 76 SmallSet<unsigned, 8> ImpDefRegs; 77 SmallVector<MachineInstr*, 8> ImpDefMIs; 78 SmallVector<MachineInstr*, 4> RUses; 79 SmallPtrSet<MachineBasicBlock*,16> Visited; 80 SmallPtrSet<MachineInstr*, 8> ModInsts; 81 82 MachineBasicBlock *Entry = fn.begin(); 83 for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > 84 DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); 85 DFI != E; ++DFI) { 86 MachineBasicBlock *MBB = *DFI; 87 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 88 I != E; ) { 89 MachineInstr *MI = &*I; 90 ++I; 91 if (MI->isImplicitDef()) { 92 if (MI->getOperand(0).getSubReg()) 93 continue; 94 unsigned Reg = MI->getOperand(0).getReg(); 95 ImpDefRegs.insert(Reg); 96 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 97 for (const unsigned *SS = tri_->getSubRegisters(Reg); *SS; ++SS) 98 ImpDefRegs.insert(*SS); 99 } 100 ImpDefMIs.push_back(MI); 101 continue; 102 } 103 104 // Eliminate %reg1032:sub<def> = COPY undef. 105 if (MI->isCopy() && MI->getOperand(0).getSubReg()) { 106 MachineOperand &MO = MI->getOperand(1); 107 if (ImpDefRegs.count(MO.getReg())) { 108 if (MO.isKill()) { 109 LiveVariables::VarInfo& vi = lv_->getVarInfo(MO.getReg()); 110 vi.removeKill(MI); 111 } 112 MI->eraseFromParent(); 113 Changed = true; 114 continue; 115 } 116 } 117 118 bool ChangedToImpDef = false; 119 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 120 MachineOperand& MO = MI->getOperand(i); 121 if (!MO.isReg() || (MO.isDef() && !MO.getSubReg()) || MO.isUndef()) 122 continue; 123 unsigned Reg = MO.getReg(); 124 if (!Reg) 125 continue; 126 if (!ImpDefRegs.count(Reg)) 127 continue; 128 // Use is a copy, just turn it into an implicit_def. 129 if (CanTurnIntoImplicitDef(MI, Reg, i, tii_)) { 130 bool isKill = MO.isKill(); 131 MI->setDesc(tii_->get(TargetOpcode::IMPLICIT_DEF)); 132 for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j) 133 MI->RemoveOperand(j); 134 if (isKill) { 135 ImpDefRegs.erase(Reg); 136 LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg); 137 vi.removeKill(MI); 138 } 139 ChangedToImpDef = true; 140 Changed = true; 141 break; 142 } 143 144 Changed = true; 145 MO.setIsUndef(); 146 // This is a partial register redef of an implicit def. 147 // Make sure the whole register is defined by the instruction. 148 if (MO.isDef()) { 149 MI->addRegisterDefined(Reg); 150 continue; 151 } 152 if (MO.isKill() || MI->isRegTiedToDefOperand(i)) { 153 // Make sure other uses of 154 for (unsigned j = i+1; j != e; ++j) { 155 MachineOperand &MOJ = MI->getOperand(j); 156 if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg) 157 MOJ.setIsUndef(); 158 } 159 ImpDefRegs.erase(Reg); 160 } 161 } 162 163 if (ChangedToImpDef) { 164 // Backtrack to process this new implicit_def. 165 --I; 166 } else { 167 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 168 MachineOperand& MO = MI->getOperand(i); 169 if (!MO.isReg() || !MO.isDef()) 170 continue; 171 ImpDefRegs.erase(MO.getReg()); 172 } 173 } 174 } 175 176 // Any outstanding liveout implicit_def's? 177 for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) { 178 MachineInstr *MI = ImpDefMIs[i]; 179 unsigned Reg = MI->getOperand(0).getReg(); 180 if (TargetRegisterInfo::isPhysicalRegister(Reg) || 181 !ImpDefRegs.count(Reg)) { 182 // Delete all "local" implicit_def's. That include those which define 183 // physical registers since they cannot be liveout. 184 MI->eraseFromParent(); 185 Changed = true; 186 continue; 187 } 188 189 // If there are multiple defs of the same register and at least one 190 // is not an implicit_def, do not insert implicit_def's before the 191 // uses. 192 bool Skip = false; 193 SmallVector<MachineInstr*, 4> DeadImpDefs; 194 for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg), 195 DE = mri_->def_end(); DI != DE; ++DI) { 196 MachineInstr *DeadImpDef = &*DI; 197 if (!DeadImpDef->isImplicitDef()) { 198 Skip = true; 199 break; 200 } 201 DeadImpDefs.push_back(DeadImpDef); 202 } 203 if (Skip) 204 continue; 205 206 // The only implicit_def which we want to keep are those that are live 207 // out of its block. 208 for (unsigned j = 0, ee = DeadImpDefs.size(); j != ee; ++j) 209 DeadImpDefs[j]->eraseFromParent(); 210 Changed = true; 211 212 // Process each use instruction once. 213 for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg), 214 UE = mri_->use_end(); UI != UE; ++UI) { 215 if (UI.getOperand().isUndef()) 216 continue; 217 MachineInstr *RMI = &*UI; 218 if (ModInsts.insert(RMI)) 219 RUses.push_back(RMI); 220 } 221 222 for (unsigned i = 0, e = RUses.size(); i != e; ++i) { 223 MachineInstr *RMI = RUses[i]; 224 225 // Turn a copy use into an implicit_def. 226 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 227 if ((RMI->isCopy() && RMI->getOperand(1).getReg() == Reg && 228 RMI->getOperand(0).getSubReg() == 0) || 229 (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) && 230 Reg == SrcReg && DstSubReg == 0)) { 231 RMI->setDesc(tii_->get(TargetOpcode::IMPLICIT_DEF)); 232 233 bool isKill = false; 234 SmallVector<unsigned, 4> Ops; 235 for (unsigned j = 0, ee = RMI->getNumOperands(); j != ee; ++j) { 236 MachineOperand &RRMO = RMI->getOperand(j); 237 if (RRMO.isReg() && RRMO.getReg() == Reg) { 238 Ops.push_back(j); 239 if (RRMO.isKill()) 240 isKill = true; 241 } 242 } 243 // Leave the other operands along. 244 for (unsigned j = 0, ee = Ops.size(); j != ee; ++j) { 245 unsigned OpIdx = Ops[j]; 246 RMI->RemoveOperand(OpIdx-j); 247 } 248 249 // Update LiveVariables varinfo if the instruction is a kill. 250 if (isKill) { 251 LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg); 252 vi.removeKill(RMI); 253 } 254 continue; 255 } 256 257 // Replace Reg with a new vreg that's marked implicit. 258 const TargetRegisterClass* RC = mri_->getRegClass(Reg); 259 unsigned NewVReg = mri_->createVirtualRegister(RC); 260 bool isKill = true; 261 for (unsigned j = 0, ee = RMI->getNumOperands(); j != ee; ++j) { 262 MachineOperand &RRMO = RMI->getOperand(j); 263 if (RRMO.isReg() && RRMO.getReg() == Reg) { 264 RRMO.setReg(NewVReg); 265 RRMO.setIsUndef(); 266 if (isKill) { 267 // Only the first operand of NewVReg is marked kill. 268 RRMO.setIsKill(); 269 isKill = false; 270 } 271 } 272 } 273 } 274 RUses.clear(); 275 ModInsts.clear(); 276 } 277 ImpDefRegs.clear(); 278 ImpDefMIs.clear(); 279 } 280 281 return Changed; 282 } 283 284