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" 17249423Sdim#include "llvm/ADT/SmallPtrSet.h" 18249423Sdim#include "llvm/ADT/Statistic.h" 19203954Srdivacky#include "llvm/CodeGen/MachineFunctionPass.h" 20203954Srdivacky#include "llvm/CodeGen/MachineInstr.h" 21203954Srdivacky#include "llvm/CodeGen/MachineRegisterInfo.h" 22249423Sdim#include "llvm/IR/Function.h" 23203954Srdivacky#include "llvm/Target/TargetInstrInfo.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 36218893Sdim OptimizePHIs() : MachineFunctionPass(ID) { 37218893Sdim initializeOptimizePHIsPass(*PassRegistry::getPassRegistry()); 38218893Sdim } 39203954Srdivacky 40203954Srdivacky virtual bool runOnMachineFunction(MachineFunction &MF); 41203954Srdivacky 42203954Srdivacky virtual void getAnalysisUsage(AnalysisUsage &AU) const { 43203954Srdivacky AU.setPreservesCFG(); 44203954Srdivacky MachineFunctionPass::getAnalysisUsage(AU); 45203954Srdivacky } 46203954Srdivacky 47203954Srdivacky private: 48203954Srdivacky typedef SmallPtrSet<MachineInstr*, 16> InstrSet; 49203954Srdivacky typedef SmallPtrSetIterator<MachineInstr*> InstrSetIterator; 50203954Srdivacky 51203954Srdivacky bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg, 52203954Srdivacky InstrSet &PHIsInCycle); 53203954Srdivacky bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle); 54203954Srdivacky bool OptimizeBB(MachineBasicBlock &MBB); 55203954Srdivacky }; 56203954Srdivacky} 57203954Srdivacky 58203954Srdivackychar OptimizePHIs::ID = 0; 59234353Sdimchar &llvm::OptimizePHIsID = OptimizePHIs::ID; 60212904SdimINITIALIZE_PASS(OptimizePHIs, "opt-phis", 61218893Sdim "Optimize machine instruction PHIs", false, false) 62203954Srdivacky 63203954Srdivackybool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) { 64203954Srdivacky MRI = &Fn.getRegInfo(); 65203954Srdivacky TII = Fn.getTarget().getInstrInfo(); 66203954Srdivacky 67203954Srdivacky // Find dead PHI cycles and PHI cycles that can be replaced by a single 68203954Srdivacky // value. InstCombine does these optimizations, but DAG legalization may 69203954Srdivacky // introduce new opportunities, e.g., when i64 values are split up for 70203954Srdivacky // 32-bit targets. 71203954Srdivacky bool Changed = false; 72203954Srdivacky for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 73203954Srdivacky Changed |= OptimizeBB(*I); 74203954Srdivacky 75203954Srdivacky return Changed; 76203954Srdivacky} 77203954Srdivacky 78203954Srdivacky/// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands 79203954Srdivacky/// are copies of SingleValReg, possibly via copies through other PHIs. If 80203954Srdivacky/// SingleValReg is zero on entry, it is set to the register with the single 81203954Srdivacky/// non-copy value. PHIsInCycle is a set used to keep track of the PHIs that 82203954Srdivacky/// have been scanned. 83203954Srdivackybool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI, 84203954Srdivacky unsigned &SingleValReg, 85203954Srdivacky InstrSet &PHIsInCycle) { 86203954Srdivacky assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction"); 87203954Srdivacky unsigned DstReg = MI->getOperand(0).getReg(); 88203954Srdivacky 89203954Srdivacky // See if we already saw this register. 90203954Srdivacky if (!PHIsInCycle.insert(MI)) 91203954Srdivacky return true; 92203954Srdivacky 93203954Srdivacky // Don't scan crazily complex things. 94203954Srdivacky if (PHIsInCycle.size() == 16) 95203954Srdivacky return false; 96203954Srdivacky 97203954Srdivacky // Scan the PHI operands. 98203954Srdivacky for (unsigned i = 1; i != MI->getNumOperands(); i += 2) { 99203954Srdivacky unsigned SrcReg = MI->getOperand(i).getReg(); 100203954Srdivacky if (SrcReg == DstReg) 101203954Srdivacky continue; 102203954Srdivacky MachineInstr *SrcMI = MRI->getVRegDef(SrcReg); 103203954Srdivacky 104203954Srdivacky // Skip over register-to-register moves. 105212904Sdim if (SrcMI && SrcMI->isCopy() && 106212904Sdim !SrcMI->getOperand(0).getSubReg() && 107212904Sdim !SrcMI->getOperand(1).getSubReg() && 108212904Sdim TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg())) 109210299Sed SrcMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg()); 110203954Srdivacky if (!SrcMI) 111203954Srdivacky return false; 112203954Srdivacky 113203954Srdivacky if (SrcMI->isPHI()) { 114203954Srdivacky if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle)) 115203954Srdivacky return false; 116203954Srdivacky } else { 117203954Srdivacky // Fail if there is more than one non-phi/non-move register. 118203954Srdivacky if (SingleValReg != 0) 119203954Srdivacky return false; 120203954Srdivacky SingleValReg = SrcReg; 121203954Srdivacky } 122203954Srdivacky } 123203954Srdivacky return true; 124203954Srdivacky} 125203954Srdivacky 126203954Srdivacky/// IsDeadPHICycle - Check if the register defined by a PHI is only used by 127203954Srdivacky/// other PHIs in a cycle. 128203954Srdivackybool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) { 129203954Srdivacky assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction"); 130203954Srdivacky unsigned DstReg = MI->getOperand(0).getReg(); 131203954Srdivacky assert(TargetRegisterInfo::isVirtualRegister(DstReg) && 132203954Srdivacky "PHI destination is not a virtual register"); 133203954Srdivacky 134203954Srdivacky // See if we already saw this register. 135203954Srdivacky if (!PHIsInCycle.insert(MI)) 136203954Srdivacky return true; 137203954Srdivacky 138203954Srdivacky // Don't scan crazily complex things. 139203954Srdivacky if (PHIsInCycle.size() == 16) 140203954Srdivacky return false; 141203954Srdivacky 142203954Srdivacky for (MachineRegisterInfo::use_iterator I = MRI->use_begin(DstReg), 143203954Srdivacky E = MRI->use_end(); I != E; ++I) { 144203954Srdivacky MachineInstr *UseMI = &*I; 145203954Srdivacky if (!UseMI->isPHI() || !IsDeadPHICycle(UseMI, PHIsInCycle)) 146203954Srdivacky return false; 147203954Srdivacky } 148203954Srdivacky 149203954Srdivacky return true; 150203954Srdivacky} 151203954Srdivacky 152203954Srdivacky/// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by 153203954Srdivacky/// a single value. 154203954Srdivackybool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) { 155203954Srdivacky bool Changed = false; 156203954Srdivacky for (MachineBasicBlock::iterator 157203954Srdivacky MII = MBB.begin(), E = MBB.end(); MII != E; ) { 158203954Srdivacky MachineInstr *MI = &*MII++; 159203954Srdivacky if (!MI->isPHI()) 160203954Srdivacky break; 161203954Srdivacky 162203954Srdivacky // Check for single-value PHI cycles. 163203954Srdivacky unsigned SingleValReg = 0; 164203954Srdivacky InstrSet PHIsInCycle; 165203954Srdivacky if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) && 166203954Srdivacky SingleValReg != 0) { 167234353Sdim unsigned OldReg = MI->getOperand(0).getReg(); 168234353Sdim if (!MRI->constrainRegClass(SingleValReg, MRI->getRegClass(OldReg))) 169234353Sdim continue; 170234353Sdim 171234353Sdim MRI->replaceRegWith(OldReg, SingleValReg); 172203954Srdivacky MI->eraseFromParent(); 173203954Srdivacky ++NumPHICycles; 174203954Srdivacky Changed = true; 175203954Srdivacky continue; 176203954Srdivacky } 177203954Srdivacky 178203954Srdivacky // Check for dead PHI cycles. 179203954Srdivacky PHIsInCycle.clear(); 180203954Srdivacky if (IsDeadPHICycle(MI, PHIsInCycle)) { 181203954Srdivacky for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end(); 182203954Srdivacky PI != PE; ++PI) { 183203954Srdivacky MachineInstr *PhiMI = *PI; 184203954Srdivacky if (&*MII == PhiMI) 185203954Srdivacky ++MII; 186203954Srdivacky PhiMI->eraseFromParent(); 187203954Srdivacky } 188203954Srdivacky ++NumDeadPHICycles; 189203954Srdivacky Changed = true; 190203954Srdivacky } 191203954Srdivacky } 192203954Srdivacky return Changed; 193203954Srdivacky} 194