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