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 MachineBasicBlock *Entry = fn.begin(); 79 SmallPtrSet<MachineBasicBlock*,16> Visited; 80 81 for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > 82 DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); 83 DFI != E; ++DFI) { 84 MachineBasicBlock *MBB = *DFI; 85 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 86 I != E; ) { 87 MachineInstr *MI = &*I; 88 ++I; 89 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 90 unsigned Reg = MI->getOperand(0).getReg(); 91 ImpDefRegs.insert(Reg); 92 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 93 for (const unsigned *SS = tri_->getSubRegisters(Reg); *SS; ++SS) 94 ImpDefRegs.insert(*SS); 95 } 96 ImpDefMIs.push_back(MI); 97 continue; 98 } 99 100 if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) { 101 MachineOperand &MO = MI->getOperand(2); 102 if (ImpDefRegs.count(MO.getReg())) { 103 // %reg1032<def> = INSERT_SUBREG %reg1032, undef, 2 104 // This is an identity copy, eliminate it now. 105 if (MO.isKill()) { 106 LiveVariables::VarInfo& vi = lv_->getVarInfo(MO.getReg()); 107 vi.removeKill(MI); 108 } 109 MI->eraseFromParent(); 110 Changed = true; 111 continue; 112 } 113 } 114 115 bool ChangedToImpDef = false; 116 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 117 MachineOperand& MO = MI->getOperand(i); 118 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) 119 continue; 120 unsigned Reg = MO.getReg(); 121 if (!Reg) 122 continue; 123 if (!ImpDefRegs.count(Reg)) 124 continue; 125 // Use is a copy, just turn it into an implicit_def. 126 if (CanTurnIntoImplicitDef(MI, Reg, i, tii_)) { 127 bool isKill = MO.isKill(); 128 MI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF)); 129 for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j) 130 MI->RemoveOperand(j); 131 if (isKill) { 132 ImpDefRegs.erase(Reg); 133 LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg); 134 vi.removeKill(MI); 135 } 136 ChangedToImpDef = true; 137 Changed = true; 138 break; 139 } 140 141 Changed = true; 142 MO.setIsUndef(); 143 if (MO.isKill() || MI->isRegTiedToDefOperand(i)) { 144 // Make sure other uses of 145 for (unsigned j = i+1; j != e; ++j) { 146 MachineOperand &MOJ = MI->getOperand(j); 147 if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg) 148 MOJ.setIsUndef(); 149 } 150 ImpDefRegs.erase(Reg); 151 } 152 } 153 154 if (ChangedToImpDef) { 155 // Backtrack to process this new implicit_def. 156 --I; 157 } else { 158 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 159 MachineOperand& MO = MI->getOperand(i); 160 if (!MO.isReg() || !MO.isDef()) 161 continue; 162 ImpDefRegs.erase(MO.getReg()); 163 } 164 } 165 } 166 167 // Any outstanding liveout implicit_def's? 168 for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) { 169 MachineInstr *MI = ImpDefMIs[i]; 170 unsigned Reg = MI->getOperand(0).getReg(); 171 if (TargetRegisterInfo::isPhysicalRegister(Reg) || 172 !ImpDefRegs.count(Reg)) { 173 // Delete all "local" implicit_def's. That include those which define 174 // physical registers since they cannot be liveout. 175 MI->eraseFromParent(); 176 Changed = true; 177 continue; 178 } 179 180 // If there are multiple defs of the same register and at least one 181 // is not an implicit_def, do not insert implicit_def's before the 182 // uses. 183 bool Skip = false; 184 for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg), 185 DE = mri_->def_end(); DI != DE; ++DI) { 186 if (DI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) { 187 Skip = true; 188 break; 189 } 190 } 191 if (Skip) 192 continue; 193 194 // The only implicit_def which we want to keep are those that are live 195 // out of its block. 196 MI->eraseFromParent(); 197 Changed = true; 198 199 for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg), 200 UE = mri_->use_end(); UI != UE; ) { 201 MachineOperand &RMO = UI.getOperand(); 202 MachineInstr *RMI = &*UI; 203 ++UI; 204 MachineBasicBlock *RMBB = RMI->getParent(); 205 if (RMBB == MBB) 206 continue; 207 208 // Turn a copy use into an implicit_def. 209 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 210 if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) && 211 Reg == SrcReg) { 212 if (RMO.isKill()) { 213 LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg); 214 vi.removeKill(RMI); 215 } 216 RMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF)); 217 for (int j = RMI->getNumOperands() - 1, ee = 0; j > ee; --j) 218 RMI->RemoveOperand(j); 219 continue; 220 } 221 222 const TargetRegisterClass* RC = mri_->getRegClass(Reg); 223 unsigned NewVReg = mri_->createVirtualRegister(RC); 224 RMO.setReg(NewVReg); 225 RMO.setIsUndef(); 226 RMO.setIsKill(); 227 } 228 } 229 ImpDefRegs.clear(); 230 ImpDefMIs.clear(); 231 } 232 233 return Changed; 234 } 235 236