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