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) 50 return true; 51 52 if (OpIdx == 2 && MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) 53 return true; 54 if (OpIdx == 1 && MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 55 return true; 56 return false; 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(errs() << "********** 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->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 92 unsigned Reg = MI->getOperand(0).getReg(); 93 ImpDefRegs.insert(Reg); 94 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 95 for (const unsigned *SS = tri_->getSubRegisters(Reg); *SS; ++SS) 96 ImpDefRegs.insert(*SS); 97 } 98 ImpDefMIs.push_back(MI); 99 continue; 100 } 101 102 if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) { 103 MachineOperand &MO = MI->getOperand(2); 104 if (ImpDefRegs.count(MO.getReg())) { 105 // %reg1032<def> = INSERT_SUBREG %reg1032, undef, 2 106 // This is an identity copy, eliminate it now. 107 if (MO.isKill()) { 108 LiveVariables::VarInfo& vi = lv_->getVarInfo(MO.getReg()); 109 vi.removeKill(MI); 110 } 111 MI->eraseFromParent(); 112 Changed = true; 113 continue; 114 } 115 } 116 117 bool ChangedToImpDef = false; 118 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 119 MachineOperand& MO = MI->getOperand(i); 120 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) 121 continue; 122 unsigned Reg = MO.getReg(); 123 if (!Reg) 124 continue; 125 if (!ImpDefRegs.count(Reg)) 126 continue; 127 // Use is a copy, just turn it into an implicit_def. 128 if (CanTurnIntoImplicitDef(MI, Reg, i, tii_)) { 129 bool isKill = MO.isKill(); 130 MI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF)); 131 for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j) 132 MI->RemoveOperand(j); 133 if (isKill) { 134 ImpDefRegs.erase(Reg); 135 LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg); 136 vi.removeKill(MI); 137 } 138 ChangedToImpDef = true; 139 Changed = true; 140 break; 141 } 142 143 Changed = true; 144 MO.setIsUndef(); 145 if (MO.isKill() || MI->isRegTiedToDefOperand(i)) { 146 // Make sure other uses of 147 for (unsigned j = i+1; j != e; ++j) { 148 MachineOperand &MOJ = MI->getOperand(j); 149 if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg) 150 MOJ.setIsUndef(); 151 } 152 ImpDefRegs.erase(Reg); 153 } 154 } 155 156 if (ChangedToImpDef) { 157 // Backtrack to process this new implicit_def. 158 --I; 159 } else { 160 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 161 MachineOperand& MO = MI->getOperand(i); 162 if (!MO.isReg() || !MO.isDef()) 163 continue; 164 ImpDefRegs.erase(MO.getReg()); 165 } 166 } 167 } 168 169 // Any outstanding liveout implicit_def's? 170 for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) { 171 MachineInstr *MI = ImpDefMIs[i]; 172 unsigned Reg = MI->getOperand(0).getReg(); 173 if (TargetRegisterInfo::isPhysicalRegister(Reg) || 174 !ImpDefRegs.count(Reg)) { 175 // Delete all "local" implicit_def's. That include those which define 176 // physical registers since they cannot be liveout. 177 MI->eraseFromParent(); 178 Changed = true; 179 continue; 180 } 181 182 // If there are multiple defs of the same register and at least one 183 // is not an implicit_def, do not insert implicit_def's before the 184 // uses. 185 bool Skip = false; 186 for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg), 187 DE = mri_->def_end(); DI != DE; ++DI) { 188 if (DI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) { 189 Skip = true; 190 break; 191 } 192 } 193 if (Skip) 194 continue; 195 196 // The only implicit_def which we want to keep are those that are live 197 // out of its block. 198 MI->eraseFromParent(); 199 Changed = true; 200 201 // Process each use instruction once. 202 for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg), 203 UE = mri_->use_end(); UI != UE; ++UI) { 204 MachineInstr *RMI = &*UI; 205 MachineBasicBlock *RMBB = RMI->getParent(); 206 if (RMBB == MBB) 207 continue; 208 if (ModInsts.insert(RMI)) 209 RUses.push_back(RMI); 210 } 211 212 for (unsigned i = 0, e = RUses.size(); i != e; ++i) { 213 MachineInstr *RMI = RUses[i]; 214 215 // Turn a copy use into an implicit_def. 216 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 217 if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) && 218 Reg == SrcReg) { 219 RMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF)); 220 221 bool isKill = false; 222 SmallVector<unsigned, 4> Ops; 223 for (unsigned j = 0, ee = RMI->getNumOperands(); j != ee; ++j) { 224 MachineOperand &RRMO = RMI->getOperand(j); 225 if (RRMO.isReg() && RRMO.getReg() == Reg) { 226 Ops.push_back(j); 227 if (RRMO.isKill()) 228 isKill = true; 229 } 230 } 231 // Leave the other operands along. 232 for (unsigned j = 0, ee = Ops.size(); j != ee; ++j) { 233 unsigned OpIdx = Ops[j]; 234 RMI->RemoveOperand(OpIdx-j); 235 } 236 237 // Update LiveVariables varinfo if the instruction is a kill. 238 if (isKill) { 239 LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg); 240 vi.removeKill(RMI); 241 } 242 continue; 243 } 244 245 // Replace Reg with a new vreg that's marked implicit. 246 const TargetRegisterClass* RC = mri_->getRegClass(Reg); 247 unsigned NewVReg = mri_->createVirtualRegister(RC); 248 bool isKill = true; 249 for (unsigned j = 0, ee = RMI->getNumOperands(); j != ee; ++j) { 250 MachineOperand &RRMO = RMI->getOperand(j); 251 if (RRMO.isReg() && RRMO.getReg() == Reg) { 252 RRMO.setReg(NewVReg); 253 RRMO.setIsUndef(); 254 if (isKill) { 255 // Only the first operand of NewVReg is marked kill. 256 RRMO.setIsKill(); 257 isKill = false; 258 } 259 } 260 } 261 } 262 RUses.clear(); 263 } 264 ModInsts.clear(); 265 ImpDefRegs.clear(); 266 ImpDefMIs.clear(); 267 } 268 269 return Changed; 270 } 271 272