OptimizePHIs.cpp revision 04c528a0c86ddf3d6a70681f72e1b2ec07b0b53a
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 if (SrcMI && SrcMI->isCopy() && 105 !SrcMI->getOperand(0).getSubReg() && 106 !SrcMI->getOperand(1).getSubReg() && 107 TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg())) 108 SrcMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg()); 109 if (!SrcMI) 110 return false; 111 112 if (SrcMI->isPHI()) { 113 if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle)) 114 return false; 115 } else { 116 // Fail if there is more than one non-phi/non-move register. 117 if (SingleValReg != 0) 118 return false; 119 SingleValReg = SrcReg; 120 } 121 } 122 return true; 123} 124 125/// IsDeadPHICycle - Check if the register defined by a PHI is only used by 126/// other PHIs in a cycle. 127bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) { 128 assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction"); 129 unsigned DstReg = MI->getOperand(0).getReg(); 130 assert(TargetRegisterInfo::isVirtualRegister(DstReg) && 131 "PHI destination is not a virtual register"); 132 133 // See if we already saw this register. 134 if (!PHIsInCycle.insert(MI)) 135 return true; 136 137 // Don't scan crazily complex things. 138 if (PHIsInCycle.size() == 16) 139 return false; 140 141 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(DstReg), 142 E = MRI->use_end(); I != E; ++I) { 143 MachineInstr *UseMI = &*I; 144 if (!UseMI->isPHI() || !IsDeadPHICycle(UseMI, PHIsInCycle)) 145 return false; 146 } 147 148 return true; 149} 150 151/// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by 152/// a single value. 153bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) { 154 bool Changed = false; 155 for (MachineBasicBlock::iterator 156 MII = MBB.begin(), E = MBB.end(); MII != E; ) { 157 MachineInstr *MI = &*MII++; 158 if (!MI->isPHI()) 159 break; 160 161 // Check for single-value PHI cycles. 162 unsigned SingleValReg = 0; 163 InstrSet PHIsInCycle; 164 if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) && 165 SingleValReg != 0) { 166 MRI->replaceRegWith(MI->getOperand(0).getReg(), SingleValReg); 167 MI->eraseFromParent(); 168 ++NumPHICycles; 169 Changed = true; 170 continue; 171 } 172 173 // Check for dead PHI cycles. 174 PHIsInCycle.clear(); 175 if (IsDeadPHICycle(MI, PHIsInCycle)) { 176 for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end(); 177 PI != PE; ++PI) { 178 MachineInstr *PhiMI = *PI; 179 if (&*MII == PhiMI) 180 ++MII; 181 PhiMI->eraseFromParent(); 182 } 183 ++NumDeadPHICycles; 184 Changed = true; 185 } 186 } 187 return Changed; 188} 189