OptimizePHIs.cpp revision 327952
1327952Sdim//===- 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 15249423Sdim#include "llvm/ADT/SmallPtrSet.h" 16249423Sdim#include "llvm/ADT/Statistic.h" 17327952Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 18327952Sdim#include "llvm/CodeGen/MachineFunction.h" 19203954Srdivacky#include "llvm/CodeGen/MachineFunctionPass.h" 20203954Srdivacky#include "llvm/CodeGen/MachineInstr.h" 21327952Sdim#include "llvm/CodeGen/MachineOperand.h" 22203954Srdivacky#include "llvm/CodeGen/MachineRegisterInfo.h" 23327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 24327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 25327952Sdim#include "llvm/Pass.h" 26327952Sdim#include <cassert> 27327952Sdim 28203954Srdivackyusing namespace llvm; 29203954Srdivacky 30321369Sdim#define DEBUG_TYPE "opt-phis" 31276479Sdim 32203954SrdivackySTATISTIC(NumPHICycles, "Number of PHI cycles replaced"); 33203954SrdivackySTATISTIC(NumDeadPHICycles, "Number of dead PHI cycles"); 34203954Srdivacky 35203954Srdivackynamespace { 36327952Sdim 37203954Srdivacky class OptimizePHIs : public MachineFunctionPass { 38203954Srdivacky MachineRegisterInfo *MRI; 39203954Srdivacky const TargetInstrInfo *TII; 40203954Srdivacky 41203954Srdivacky public: 42203954Srdivacky static char ID; // Pass identification 43327952Sdim 44218893Sdim OptimizePHIs() : MachineFunctionPass(ID) { 45218893Sdim initializeOptimizePHIsPass(*PassRegistry::getPassRegistry()); 46218893Sdim } 47203954Srdivacky 48276479Sdim bool runOnMachineFunction(MachineFunction &MF) override; 49203954Srdivacky 50276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 51203954Srdivacky AU.setPreservesCFG(); 52203954Srdivacky MachineFunctionPass::getAnalysisUsage(AU); 53203954Srdivacky } 54203954Srdivacky 55203954Srdivacky private: 56327952Sdim using InstrSet = SmallPtrSet<MachineInstr *, 16>; 57327952Sdim using InstrSetIterator = SmallPtrSetIterator<MachineInstr *>; 58203954Srdivacky 59203954Srdivacky bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg, 60203954Srdivacky InstrSet &PHIsInCycle); 61203954Srdivacky bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle); 62203954Srdivacky bool OptimizeBB(MachineBasicBlock &MBB); 63203954Srdivacky }; 64203954Srdivacky 65327952Sdim} // end anonymous namespace 66327952Sdim 67203954Srdivackychar OptimizePHIs::ID = 0; 68327952Sdim 69234353Sdimchar &llvm::OptimizePHIsID = OptimizePHIs::ID; 70327952Sdim 71321369SdimINITIALIZE_PASS(OptimizePHIs, DEBUG_TYPE, 72218893Sdim "Optimize machine instruction PHIs", false, false) 73203954Srdivacky 74203954Srdivackybool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) { 75327952Sdim if (skipFunction(Fn.getFunction())) 76276479Sdim return false; 77276479Sdim 78203954Srdivacky MRI = &Fn.getRegInfo(); 79280031Sdim TII = Fn.getSubtarget().getInstrInfo(); 80203954Srdivacky 81203954Srdivacky // Find dead PHI cycles and PHI cycles that can be replaced by a single 82203954Srdivacky // value. InstCombine does these optimizations, but DAG legalization may 83203954Srdivacky // introduce new opportunities, e.g., when i64 values are split up for 84203954Srdivacky // 32-bit targets. 85203954Srdivacky bool Changed = false; 86203954Srdivacky for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 87203954Srdivacky Changed |= OptimizeBB(*I); 88203954Srdivacky 89203954Srdivacky return Changed; 90203954Srdivacky} 91203954Srdivacky 92203954Srdivacky/// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands 93203954Srdivacky/// are copies of SingleValReg, possibly via copies through other PHIs. If 94203954Srdivacky/// SingleValReg is zero on entry, it is set to the register with the single 95203954Srdivacky/// non-copy value. PHIsInCycle is a set used to keep track of the PHIs that 96203954Srdivacky/// have been scanned. 97203954Srdivackybool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI, 98203954Srdivacky unsigned &SingleValReg, 99203954Srdivacky InstrSet &PHIsInCycle) { 100203954Srdivacky assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction"); 101203954Srdivacky unsigned DstReg = MI->getOperand(0).getReg(); 102203954Srdivacky 103203954Srdivacky // See if we already saw this register. 104280031Sdim if (!PHIsInCycle.insert(MI).second) 105203954Srdivacky return true; 106203954Srdivacky 107203954Srdivacky // Don't scan crazily complex things. 108203954Srdivacky if (PHIsInCycle.size() == 16) 109203954Srdivacky return false; 110203954Srdivacky 111203954Srdivacky // Scan the PHI operands. 112203954Srdivacky for (unsigned i = 1; i != MI->getNumOperands(); i += 2) { 113203954Srdivacky unsigned SrcReg = MI->getOperand(i).getReg(); 114203954Srdivacky if (SrcReg == DstReg) 115203954Srdivacky continue; 116203954Srdivacky MachineInstr *SrcMI = MRI->getVRegDef(SrcReg); 117203954Srdivacky 118203954Srdivacky // Skip over register-to-register moves. 119212904Sdim if (SrcMI && SrcMI->isCopy() && 120212904Sdim !SrcMI->getOperand(0).getSubReg() && 121212904Sdim !SrcMI->getOperand(1).getSubReg() && 122212904Sdim TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg())) 123210299Sed SrcMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg()); 124203954Srdivacky if (!SrcMI) 125203954Srdivacky return false; 126203954Srdivacky 127203954Srdivacky if (SrcMI->isPHI()) { 128203954Srdivacky if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle)) 129203954Srdivacky return false; 130203954Srdivacky } else { 131203954Srdivacky // Fail if there is more than one non-phi/non-move register. 132203954Srdivacky if (SingleValReg != 0) 133203954Srdivacky return false; 134203954Srdivacky SingleValReg = SrcReg; 135203954Srdivacky } 136203954Srdivacky } 137203954Srdivacky return true; 138203954Srdivacky} 139203954Srdivacky 140203954Srdivacky/// IsDeadPHICycle - Check if the register defined by a PHI is only used by 141203954Srdivacky/// other PHIs in a cycle. 142203954Srdivackybool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) { 143203954Srdivacky assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction"); 144203954Srdivacky unsigned DstReg = MI->getOperand(0).getReg(); 145203954Srdivacky assert(TargetRegisterInfo::isVirtualRegister(DstReg) && 146203954Srdivacky "PHI destination is not a virtual register"); 147203954Srdivacky 148203954Srdivacky // See if we already saw this register. 149280031Sdim if (!PHIsInCycle.insert(MI).second) 150203954Srdivacky return true; 151203954Srdivacky 152203954Srdivacky // Don't scan crazily complex things. 153203954Srdivacky if (PHIsInCycle.size() == 16) 154203954Srdivacky return false; 155203954Srdivacky 156327952Sdim for (MachineInstr &UseMI : MRI->use_nodbg_instructions(DstReg)) { 157276479Sdim if (!UseMI.isPHI() || !IsDeadPHICycle(&UseMI, PHIsInCycle)) 158203954Srdivacky return false; 159203954Srdivacky } 160203954Srdivacky 161203954Srdivacky return true; 162203954Srdivacky} 163203954Srdivacky 164203954Srdivacky/// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by 165203954Srdivacky/// a single value. 166203954Srdivackybool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) { 167203954Srdivacky bool Changed = false; 168203954Srdivacky for (MachineBasicBlock::iterator 169203954Srdivacky MII = MBB.begin(), E = MBB.end(); MII != E; ) { 170203954Srdivacky MachineInstr *MI = &*MII++; 171203954Srdivacky if (!MI->isPHI()) 172203954Srdivacky break; 173203954Srdivacky 174203954Srdivacky // Check for single-value PHI cycles. 175203954Srdivacky unsigned SingleValReg = 0; 176203954Srdivacky InstrSet PHIsInCycle; 177203954Srdivacky if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) && 178203954Srdivacky SingleValReg != 0) { 179234353Sdim unsigned OldReg = MI->getOperand(0).getReg(); 180234353Sdim if (!MRI->constrainRegClass(SingleValReg, MRI->getRegClass(OldReg))) 181234353Sdim continue; 182234353Sdim 183234353Sdim MRI->replaceRegWith(OldReg, SingleValReg); 184203954Srdivacky MI->eraseFromParent(); 185203954Srdivacky ++NumPHICycles; 186203954Srdivacky Changed = true; 187203954Srdivacky continue; 188203954Srdivacky } 189203954Srdivacky 190203954Srdivacky // Check for dead PHI cycles. 191203954Srdivacky PHIsInCycle.clear(); 192203954Srdivacky if (IsDeadPHICycle(MI, PHIsInCycle)) { 193203954Srdivacky for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end(); 194203954Srdivacky PI != PE; ++PI) { 195203954Srdivacky MachineInstr *PhiMI = *PI; 196314564Sdim if (MII == PhiMI) 197203954Srdivacky ++MII; 198203954Srdivacky PhiMI->eraseFromParent(); 199203954Srdivacky } 200203954Srdivacky ++NumDeadPHICycles; 201203954Srdivacky Changed = true; 202203954Srdivacky } 203203954Srdivacky } 204203954Srdivacky return Changed; 205203954Srdivacky} 206