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