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#include "llvm/CodeGen/Passes.h" 16#include "llvm/ADT/SmallPtrSet.h" 17#include "llvm/ADT/Statistic.h" 18#include "llvm/CodeGen/MachineFunctionPass.h" 19#include "llvm/CodeGen/MachineInstr.h" 20#include "llvm/CodeGen/MachineRegisterInfo.h" 21#include "llvm/IR/Function.h" 22#include "llvm/Target/TargetInstrInfo.h" 23#include "llvm/Target/TargetSubtargetInfo.h" 24using namespace llvm; 25 26#define DEBUG_TYPE "phi-opt" 27 28STATISTIC(NumPHICycles, "Number of PHI cycles replaced"); 29STATISTIC(NumDeadPHICycles, "Number of dead PHI cycles"); 30 31namespace { 32 class OptimizePHIs : public MachineFunctionPass { 33 MachineRegisterInfo *MRI; 34 const TargetInstrInfo *TII; 35 36 public: 37 static char ID; // Pass identification 38 OptimizePHIs() : MachineFunctionPass(ID) { 39 initializeOptimizePHIsPass(*PassRegistry::getPassRegistry()); 40 } 41 42 bool runOnMachineFunction(MachineFunction &MF) override; 43 44 void getAnalysisUsage(AnalysisUsage &AU) const override { 45 AU.setPreservesCFG(); 46 MachineFunctionPass::getAnalysisUsage(AU); 47 } 48 49 private: 50 typedef SmallPtrSet<MachineInstr*, 16> InstrSet; 51 typedef SmallPtrSetIterator<MachineInstr*> InstrSetIterator; 52 53 bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg, 54 InstrSet &PHIsInCycle); 55 bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle); 56 bool OptimizeBB(MachineBasicBlock &MBB); 57 }; 58} 59 60char OptimizePHIs::ID = 0; 61char &llvm::OptimizePHIsID = OptimizePHIs::ID; 62INITIALIZE_PASS(OptimizePHIs, "opt-phis", 63 "Optimize machine instruction PHIs", false, false) 64 65bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) { 66 if (skipOptnoneFunction(*Fn.getFunction())) 67 return false; 68 69 MRI = &Fn.getRegInfo(); 70 TII = Fn.getSubtarget().getInstrInfo(); 71 72 // Find dead PHI cycles and PHI cycles that can be replaced by a single 73 // value. InstCombine does these optimizations, but DAG legalization may 74 // introduce new opportunities, e.g., when i64 values are split up for 75 // 32-bit targets. 76 bool Changed = false; 77 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 78 Changed |= OptimizeBB(*I); 79 80 return Changed; 81} 82 83/// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands 84/// are copies of SingleValReg, possibly via copies through other PHIs. If 85/// SingleValReg is zero on entry, it is set to the register with the single 86/// non-copy value. PHIsInCycle is a set used to keep track of the PHIs that 87/// have been scanned. 88bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI, 89 unsigned &SingleValReg, 90 InstrSet &PHIsInCycle) { 91 assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction"); 92 unsigned DstReg = MI->getOperand(0).getReg(); 93 94 // See if we already saw this register. 95 if (!PHIsInCycle.insert(MI).second) 96 return true; 97 98 // Don't scan crazily complex things. 99 if (PHIsInCycle.size() == 16) 100 return false; 101 102 // Scan the PHI operands. 103 for (unsigned i = 1; i != MI->getNumOperands(); i += 2) { 104 unsigned SrcReg = MI->getOperand(i).getReg(); 105 if (SrcReg == DstReg) 106 continue; 107 MachineInstr *SrcMI = MRI->getVRegDef(SrcReg); 108 109 // Skip over register-to-register moves. 110 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).second) 141 return true; 142 143 // Don't scan crazily complex things. 144 if (PHIsInCycle.size() == 16) 145 return false; 146 147 for (MachineInstr &UseMI : MRI->use_instructions(DstReg)) { 148 if (!UseMI.isPHI() || !IsDeadPHICycle(&UseMI, PHIsInCycle)) 149 return false; 150 } 151 152 return true; 153} 154 155/// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by 156/// a single value. 157bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) { 158 bool Changed = false; 159 for (MachineBasicBlock::iterator 160 MII = MBB.begin(), E = MBB.end(); MII != E; ) { 161 MachineInstr *MI = &*MII++; 162 if (!MI->isPHI()) 163 break; 164 165 // Check for single-value PHI cycles. 166 unsigned SingleValReg = 0; 167 InstrSet PHIsInCycle; 168 if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) && 169 SingleValReg != 0) { 170 unsigned OldReg = MI->getOperand(0).getReg(); 171 if (!MRI->constrainRegClass(SingleValReg, MRI->getRegClass(OldReg))) 172 continue; 173 174 MRI->replaceRegWith(OldReg, SingleValReg); 175 MI->eraseFromParent(); 176 ++NumPHICycles; 177 Changed = true; 178 continue; 179 } 180 181 // Check for dead PHI cycles. 182 PHIsInCycle.clear(); 183 if (IsDeadPHICycle(MI, PHIsInCycle)) { 184 for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end(); 185 PI != PE; ++PI) { 186 MachineInstr *PhiMI = *PI; 187 if (&*MII == PhiMI) 188 ++MII; 189 PhiMI->eraseFromParent(); 190 } 191 ++NumDeadPHICycles; 192 Changed = true; 193 } 194 } 195 return Changed; 196} 197