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