OptimizePHIs.cpp revision 210299
1203954Srdivacky//===-- OptimizePHIs.cpp - Optimize machine instruction PHIs --------------===// 2203954Srdivacky// 3203954Srdivacky// The LLVM Compiler Infrastructure 4203954Srdivacky// 5203954Srdivacky// This file is distributed under the University of Illinois Open Source 6203954Srdivacky// License. See LICENSE.TXT for details. 7203954Srdivacky// 8203954Srdivacky//===----------------------------------------------------------------------===// 9203954Srdivacky// 10203954Srdivacky// This pass optimizes machine instruction PHIs to take advantage of 11203954Srdivacky// opportunities created during DAG legalization. 12203954Srdivacky// 13203954Srdivacky//===----------------------------------------------------------------------===// 14203954Srdivacky 15203954Srdivacky#define DEBUG_TYPE "phi-opt" 16203954Srdivacky#include "llvm/CodeGen/Passes.h" 17203954Srdivacky#include "llvm/CodeGen/MachineFunctionPass.h" 18203954Srdivacky#include "llvm/CodeGen/MachineInstr.h" 19203954Srdivacky#include "llvm/CodeGen/MachineRegisterInfo.h" 20203954Srdivacky#include "llvm/Target/TargetInstrInfo.h" 21203954Srdivacky#include "llvm/Function.h" 22203954Srdivacky#include "llvm/ADT/SmallPtrSet.h" 23203954Srdivacky#include "llvm/ADT/Statistic.h" 24203954Srdivackyusing namespace llvm; 25203954Srdivacky 26203954SrdivackySTATISTIC(NumPHICycles, "Number of PHI cycles replaced"); 27203954SrdivackySTATISTIC(NumDeadPHICycles, "Number of dead PHI cycles"); 28203954Srdivacky 29203954Srdivackynamespace { 30203954Srdivacky class OptimizePHIs : public MachineFunctionPass { 31203954Srdivacky MachineRegisterInfo *MRI; 32203954Srdivacky const TargetInstrInfo *TII; 33203954Srdivacky 34203954Srdivacky public: 35203954Srdivacky static char ID; // Pass identification 36203954Srdivacky OptimizePHIs() : MachineFunctionPass(&ID) {} 37203954Srdivacky 38203954Srdivacky virtual bool runOnMachineFunction(MachineFunction &MF); 39203954Srdivacky 40203954Srdivacky virtual void getAnalysisUsage(AnalysisUsage &AU) const { 41203954Srdivacky AU.setPreservesCFG(); 42203954Srdivacky MachineFunctionPass::getAnalysisUsage(AU); 43203954Srdivacky } 44203954Srdivacky 45203954Srdivacky private: 46203954Srdivacky typedef SmallPtrSet<MachineInstr*, 16> InstrSet; 47203954Srdivacky typedef SmallPtrSetIterator<MachineInstr*> InstrSetIterator; 48203954Srdivacky 49203954Srdivacky bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg, 50203954Srdivacky InstrSet &PHIsInCycle); 51203954Srdivacky bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle); 52203954Srdivacky bool OptimizeBB(MachineBasicBlock &MBB); 53203954Srdivacky }; 54203954Srdivacky} 55203954Srdivacky 56203954Srdivackychar OptimizePHIs::ID = 0; 57203954Srdivackystatic RegisterPass<OptimizePHIs> 58203954SrdivackyX("opt-phis", "Optimize machine instruction PHIs"); 59203954Srdivacky 60203954SrdivackyFunctionPass *llvm::createOptimizePHIsPass() { return new OptimizePHIs(); } 61203954Srdivacky 62203954Srdivackybool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) { 63203954Srdivacky MRI = &Fn.getRegInfo(); 64203954Srdivacky TII = Fn.getTarget().getInstrInfo(); 65203954Srdivacky 66203954Srdivacky // Find dead PHI cycles and PHI cycles that can be replaced by a single 67203954Srdivacky // value. InstCombine does these optimizations, but DAG legalization may 68203954Srdivacky // introduce new opportunities, e.g., when i64 values are split up for 69203954Srdivacky // 32-bit targets. 70203954Srdivacky bool Changed = false; 71203954Srdivacky for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 72203954Srdivacky Changed |= OptimizeBB(*I); 73203954Srdivacky 74203954Srdivacky return Changed; 75203954Srdivacky} 76203954Srdivacky 77203954Srdivacky/// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands 78203954Srdivacky/// are copies of SingleValReg, possibly via copies through other PHIs. If 79203954Srdivacky/// SingleValReg is zero on entry, it is set to the register with the single 80203954Srdivacky/// non-copy value. PHIsInCycle is a set used to keep track of the PHIs that 81203954Srdivacky/// have been scanned. 82203954Srdivackybool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI, 83203954Srdivacky unsigned &SingleValReg, 84203954Srdivacky InstrSet &PHIsInCycle) { 85203954Srdivacky assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction"); 86203954Srdivacky unsigned DstReg = MI->getOperand(0).getReg(); 87203954Srdivacky 88203954Srdivacky // See if we already saw this register. 89203954Srdivacky if (!PHIsInCycle.insert(MI)) 90203954Srdivacky return true; 91203954Srdivacky 92203954Srdivacky // Don't scan crazily complex things. 93203954Srdivacky if (PHIsInCycle.size() == 16) 94203954Srdivacky return false; 95203954Srdivacky 96203954Srdivacky // Scan the PHI operands. 97203954Srdivacky for (unsigned i = 1; i != MI->getNumOperands(); i += 2) { 98203954Srdivacky unsigned SrcReg = MI->getOperand(i).getReg(); 99203954Srdivacky if (SrcReg == DstReg) 100203954Srdivacky continue; 101203954Srdivacky MachineInstr *SrcMI = MRI->getVRegDef(SrcReg); 102203954Srdivacky 103203954Srdivacky // Skip over register-to-register moves. 104203954Srdivacky unsigned MvSrcReg, MvDstReg, SrcSubIdx, DstSubIdx; 105203954Srdivacky if (SrcMI && 106203954Srdivacky TII->isMoveInstr(*SrcMI, MvSrcReg, MvDstReg, SrcSubIdx, DstSubIdx) && 107203954Srdivacky SrcSubIdx == 0 && DstSubIdx == 0 && 108203954Srdivacky TargetRegisterInfo::isVirtualRegister(MvSrcReg)) 109203954Srdivacky SrcMI = MRI->getVRegDef(MvSrcReg); 110210299Sed else if (SrcMI && SrcMI->isCopy() && 111210299Sed !SrcMI->getOperand(0).getSubReg() && 112210299Sed !SrcMI->getOperand(1).getSubReg() && 113210299Sed TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg())) 114210299Sed SrcMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg()); 115203954Srdivacky if (!SrcMI) 116203954Srdivacky return false; 117203954Srdivacky 118203954Srdivacky if (SrcMI->isPHI()) { 119203954Srdivacky if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle)) 120203954Srdivacky return false; 121203954Srdivacky } else { 122203954Srdivacky // Fail if there is more than one non-phi/non-move register. 123203954Srdivacky if (SingleValReg != 0) 124203954Srdivacky return false; 125203954Srdivacky SingleValReg = SrcReg; 126203954Srdivacky } 127203954Srdivacky } 128203954Srdivacky return true; 129203954Srdivacky} 130203954Srdivacky 131203954Srdivacky/// IsDeadPHICycle - Check if the register defined by a PHI is only used by 132203954Srdivacky/// other PHIs in a cycle. 133203954Srdivackybool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) { 134203954Srdivacky assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction"); 135203954Srdivacky unsigned DstReg = MI->getOperand(0).getReg(); 136203954Srdivacky assert(TargetRegisterInfo::isVirtualRegister(DstReg) && 137203954Srdivacky "PHI destination is not a virtual register"); 138203954Srdivacky 139203954Srdivacky // See if we already saw this register. 140203954Srdivacky if (!PHIsInCycle.insert(MI)) 141203954Srdivacky return true; 142203954Srdivacky 143203954Srdivacky // Don't scan crazily complex things. 144203954Srdivacky if (PHIsInCycle.size() == 16) 145203954Srdivacky return false; 146203954Srdivacky 147203954Srdivacky for (MachineRegisterInfo::use_iterator I = MRI->use_begin(DstReg), 148203954Srdivacky E = MRI->use_end(); I != E; ++I) { 149203954Srdivacky MachineInstr *UseMI = &*I; 150203954Srdivacky if (!UseMI->isPHI() || !IsDeadPHICycle(UseMI, PHIsInCycle)) 151203954Srdivacky return false; 152203954Srdivacky } 153203954Srdivacky 154203954Srdivacky return true; 155203954Srdivacky} 156203954Srdivacky 157203954Srdivacky/// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by 158203954Srdivacky/// a single value. 159203954Srdivackybool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) { 160203954Srdivacky bool Changed = false; 161203954Srdivacky for (MachineBasicBlock::iterator 162203954Srdivacky MII = MBB.begin(), E = MBB.end(); MII != E; ) { 163203954Srdivacky MachineInstr *MI = &*MII++; 164203954Srdivacky if (!MI->isPHI()) 165203954Srdivacky break; 166203954Srdivacky 167203954Srdivacky // Check for single-value PHI cycles. 168203954Srdivacky unsigned SingleValReg = 0; 169203954Srdivacky InstrSet PHIsInCycle; 170203954Srdivacky if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) && 171203954Srdivacky SingleValReg != 0) { 172203954Srdivacky MRI->replaceRegWith(MI->getOperand(0).getReg(), SingleValReg); 173203954Srdivacky MI->eraseFromParent(); 174203954Srdivacky ++NumPHICycles; 175203954Srdivacky Changed = true; 176203954Srdivacky continue; 177203954Srdivacky } 178203954Srdivacky 179203954Srdivacky // Check for dead PHI cycles. 180203954Srdivacky PHIsInCycle.clear(); 181203954Srdivacky if (IsDeadPHICycle(MI, PHIsInCycle)) { 182203954Srdivacky for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end(); 183203954Srdivacky PI != PE; ++PI) { 184203954Srdivacky MachineInstr *PhiMI = *PI; 185203954Srdivacky if (&*MII == PhiMI) 186203954Srdivacky ++MII; 187203954Srdivacky PhiMI->eraseFromParent(); 188203954Srdivacky } 189203954Srdivacky ++NumDeadPHICycles; 190203954Srdivacky Changed = true; 191203954Srdivacky } 192203954Srdivacky } 193203954Srdivacky return Changed; 194203954Srdivacky} 195