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