ProcessImplicitDefs.cpp revision 208954
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 && SrcSubReg == 0 && DstSubReg == 0) 50 return true; 51 52 if (OpIdx == 2 && MI->isSubregToReg()) 53 return true; 54 if (OpIdx == 1 && MI->isExtractSubreg()) 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. 62bool 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 if (MI->isInsertSubreg()) { 105 MachineOperand &MO = MI->getOperand(2); 106 if (ImpDefRegs.count(MO.getReg())) { 107 // %reg1032<def> = INSERT_SUBREG %reg1032, undef, 2 108 // This is an identity copy, eliminate it now. 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.isUse() || 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 if (MO.isKill() || MI->isRegTiedToDefOperand(i)) { 148 // Make sure other uses of 149 for (unsigned j = i+1; j != e; ++j) { 150 MachineOperand &MOJ = MI->getOperand(j); 151 if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg) 152 MOJ.setIsUndef(); 153 } 154 ImpDefRegs.erase(Reg); 155 } 156 } 157 158 if (ChangedToImpDef) { 159 // Backtrack to process this new implicit_def. 160 --I; 161 } else { 162 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 163 MachineOperand& MO = MI->getOperand(i); 164 if (!MO.isReg() || !MO.isDef()) 165 continue; 166 ImpDefRegs.erase(MO.getReg()); 167 } 168 } 169 } 170 171 // Any outstanding liveout implicit_def's? 172 for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) { 173 MachineInstr *MI = ImpDefMIs[i]; 174 unsigned Reg = MI->getOperand(0).getReg(); 175 if (TargetRegisterInfo::isPhysicalRegister(Reg) || 176 !ImpDefRegs.count(Reg)) { 177 // Delete all "local" implicit_def's. That include those which define 178 // physical registers since they cannot be liveout. 179 MI->eraseFromParent(); 180 Changed = true; 181 continue; 182 } 183 184 // If there are multiple defs of the same register and at least one 185 // is not an implicit_def, do not insert implicit_def's before the 186 // uses. 187 bool Skip = false; 188 SmallVector<MachineInstr*, 4> DeadImpDefs; 189 for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg), 190 DE = mri_->def_end(); DI != DE; ++DI) { 191 MachineInstr *DeadImpDef = &*DI; 192 if (!DeadImpDef->isImplicitDef()) { 193 Skip = true; 194 break; 195 } 196 DeadImpDefs.push_back(DeadImpDef); 197 } 198 if (Skip) 199 continue; 200 201 // The only implicit_def which we want to keep are those that are live 202 // out of its block. 203 for (unsigned j = 0, ee = DeadImpDefs.size(); j != ee; ++j) 204 DeadImpDefs[j]->eraseFromParent(); 205 Changed = true; 206 207 // Process each use instruction once. 208 for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg), 209 UE = mri_->use_end(); UI != UE; ++UI) { 210 if (UI.getOperand().isUndef()) 211 continue; 212 MachineInstr *RMI = &*UI; 213 if (ModInsts.insert(RMI)) 214 RUses.push_back(RMI); 215 } 216 217 for (unsigned i = 0, e = RUses.size(); i != e; ++i) { 218 MachineInstr *RMI = RUses[i]; 219 220 // Turn a copy use into an implicit_def. 221 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 222 if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) && 223 Reg == SrcReg && SrcSubReg == 0 && DstSubReg == 0) { 224 RMI->setDesc(tii_->get(TargetOpcode::IMPLICIT_DEF)); 225 226 bool isKill = false; 227 SmallVector<unsigned, 4> Ops; 228 for (unsigned j = 0, ee = RMI->getNumOperands(); j != ee; ++j) { 229 MachineOperand &RRMO = RMI->getOperand(j); 230 if (RRMO.isReg() && RRMO.getReg() == Reg) { 231 Ops.push_back(j); 232 if (RRMO.isKill()) 233 isKill = true; 234 } 235 } 236 // Leave the other operands along. 237 for (unsigned j = 0, ee = Ops.size(); j != ee; ++j) { 238 unsigned OpIdx = Ops[j]; 239 RMI->RemoveOperand(OpIdx-j); 240 } 241 242 // Update LiveVariables varinfo if the instruction is a kill. 243 if (isKill) { 244 LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg); 245 vi.removeKill(RMI); 246 } 247 continue; 248 } 249 250 // Replace Reg with a new vreg that's marked implicit. 251 const TargetRegisterClass* RC = mri_->getRegClass(Reg); 252 unsigned NewVReg = mri_->createVirtualRegister(RC); 253 bool isKill = true; 254 for (unsigned j = 0, ee = RMI->getNumOperands(); j != ee; ++j) { 255 MachineOperand &RRMO = RMI->getOperand(j); 256 if (RRMO.isReg() && RRMO.getReg() == Reg) { 257 RRMO.setReg(NewVReg); 258 RRMO.setIsUndef(); 259 if (isKill) { 260 // Only the first operand of NewVReg is marked kill. 261 RRMO.setIsKill(); 262 isKill = false; 263 } 264 } 265 } 266 } 267 RUses.clear(); 268 ModInsts.clear(); 269 } 270 ImpDefRegs.clear(); 271 ImpDefMIs.clear(); 272 } 273 274 return Changed; 275} 276 277