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