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