OptimizePHIs.cpp revision 210299
1//===-- OptimizePHIs.cpp - Optimize machine instruction PHIs --------------===// 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// This pass optimizes machine instruction PHIs to take advantage of 11// opportunities created during DAG legalization. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "phi-opt" 16#include "llvm/CodeGen/Passes.h" 17#include "llvm/CodeGen/MachineFunctionPass.h" 18#include "llvm/CodeGen/MachineInstr.h" 19#include "llvm/CodeGen/MachineRegisterInfo.h" 20#include "llvm/Target/TargetInstrInfo.h" 21#include "llvm/Function.h" 22#include "llvm/ADT/SmallPtrSet.h" 23#include "llvm/ADT/Statistic.h" 24using namespace llvm; 25 26STATISTIC(NumPHICycles, "Number of PHI cycles replaced"); 27STATISTIC(NumDeadPHICycles, "Number of dead PHI cycles"); 28 29namespace { 30 class OptimizePHIs : public MachineFunctionPass { 31 MachineRegisterInfo *MRI; 32 const TargetInstrInfo *TII; 33 34 public: 35 static char ID; // Pass identification 36 OptimizePHIs() : MachineFunctionPass(&ID) {} 37 38 virtual bool runOnMachineFunction(MachineFunction &MF); 39 40 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 41 AU.setPreservesCFG(); 42 MachineFunctionPass::getAnalysisUsage(AU); 43 } 44 45 private: 46 typedef SmallPtrSet<MachineInstr*, 16> InstrSet; 47 typedef SmallPtrSetIterator<MachineInstr*> InstrSetIterator; 48 49 bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg, 50 InstrSet &PHIsInCycle); 51 bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle); 52 bool OptimizeBB(MachineBasicBlock &MBB); 53 }; 54} 55 56char OptimizePHIs::ID = 0; 57static RegisterPass<OptimizePHIs> 58X("opt-phis", "Optimize machine instruction PHIs"); 59 60FunctionPass *llvm::createOptimizePHIsPass() { return new OptimizePHIs(); } 61 62bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) { 63 MRI = &Fn.getRegInfo(); 64 TII = Fn.getTarget().getInstrInfo(); 65 66 // Find dead PHI cycles and PHI cycles that can be replaced by a single 67 // value. InstCombine does these optimizations, but DAG legalization may 68 // introduce new opportunities, e.g., when i64 values are split up for 69 // 32-bit targets. 70 bool Changed = false; 71 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 72 Changed |= OptimizeBB(*I); 73 74 return Changed; 75} 76 77/// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands 78/// are copies of SingleValReg, possibly via copies through other PHIs. If 79/// SingleValReg is zero on entry, it is set to the register with the single 80/// non-copy value. PHIsInCycle is a set used to keep track of the PHIs that 81/// have been scanned. 82bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI, 83 unsigned &SingleValReg, 84 InstrSet &PHIsInCycle) { 85 assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction"); 86 unsigned DstReg = MI->getOperand(0).getReg(); 87 88 // See if we already saw this register. 89 if (!PHIsInCycle.insert(MI)) 90 return true; 91 92 // Don't scan crazily complex things. 93 if (PHIsInCycle.size() == 16) 94 return false; 95 96 // Scan the PHI operands. 97 for (unsigned i = 1; i != MI->getNumOperands(); i += 2) { 98 unsigned SrcReg = MI->getOperand(i).getReg(); 99 if (SrcReg == DstReg) 100 continue; 101 MachineInstr *SrcMI = MRI->getVRegDef(SrcReg); 102 103 // Skip over register-to-register moves. 104 unsigned MvSrcReg, MvDstReg, SrcSubIdx, DstSubIdx; 105 if (SrcMI && 106 TII->isMoveInstr(*SrcMI, MvSrcReg, MvDstReg, SrcSubIdx, DstSubIdx) && 107 SrcSubIdx == 0 && DstSubIdx == 0 && 108 TargetRegisterInfo::isVirtualRegister(MvSrcReg)) 109 SrcMI = MRI->getVRegDef(MvSrcReg); 110 else if (SrcMI && SrcMI->isCopy() && 111 !SrcMI->getOperand(0).getSubReg() && 112 !SrcMI->getOperand(1).getSubReg() && 113 TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg())) 114 SrcMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg()); 115 if (!SrcMI) 116 return false; 117 118 if (SrcMI->isPHI()) { 119 if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle)) 120 return false; 121 } else { 122 // Fail if there is more than one non-phi/non-move register. 123 if (SingleValReg != 0) 124 return false; 125 SingleValReg = SrcReg; 126 } 127 } 128 return true; 129} 130 131/// IsDeadPHICycle - Check if the register defined by a PHI is only used by 132/// other PHIs in a cycle. 133bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) { 134 assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction"); 135 unsigned DstReg = MI->getOperand(0).getReg(); 136 assert(TargetRegisterInfo::isVirtualRegister(DstReg) && 137 "PHI destination is not a virtual register"); 138 139 // See if we already saw this register. 140 if (!PHIsInCycle.insert(MI)) 141 return true; 142 143 // Don't scan crazily complex things. 144 if (PHIsInCycle.size() == 16) 145 return false; 146 147 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(DstReg), 148 E = MRI->use_end(); I != E; ++I) { 149 MachineInstr *UseMI = &*I; 150 if (!UseMI->isPHI() || !IsDeadPHICycle(UseMI, PHIsInCycle)) 151 return false; 152 } 153 154 return true; 155} 156 157/// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by 158/// a single value. 159bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) { 160 bool Changed = false; 161 for (MachineBasicBlock::iterator 162 MII = MBB.begin(), E = MBB.end(); MII != E; ) { 163 MachineInstr *MI = &*MII++; 164 if (!MI->isPHI()) 165 break; 166 167 // Check for single-value PHI cycles. 168 unsigned SingleValReg = 0; 169 InstrSet PHIsInCycle; 170 if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) && 171 SingleValReg != 0) { 172 MRI->replaceRegWith(MI->getOperand(0).getReg(), SingleValReg); 173 MI->eraseFromParent(); 174 ++NumPHICycles; 175 Changed = true; 176 continue; 177 } 178 179 // Check for dead PHI cycles. 180 PHIsInCycle.clear(); 181 if (IsDeadPHICycle(MI, PHIsInCycle)) { 182 for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end(); 183 PI != PE; ++PI) { 184 MachineInstr *PhiMI = *PI; 185 if (&*MII == PhiMI) 186 ++MII; 187 PhiMI->eraseFromParent(); 188 } 189 ++NumDeadPHICycles; 190 Changed = true; 191 } 192 } 193 return Changed; 194} 195