1327952Sdim//===- OptimizePHIs.cpp - Optimize machine instruction PHIs ---------------===// 2203954Srdivacky// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6203954Srdivacky// 7203954Srdivacky//===----------------------------------------------------------------------===// 8203954Srdivacky// 9203954Srdivacky// This pass optimizes machine instruction PHIs to take advantage of 10203954Srdivacky// opportunities created during DAG legalization. 11203954Srdivacky// 12203954Srdivacky//===----------------------------------------------------------------------===// 13203954Srdivacky 14249423Sdim#include "llvm/ADT/SmallPtrSet.h" 15249423Sdim#include "llvm/ADT/Statistic.h" 16327952Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 17327952Sdim#include "llvm/CodeGen/MachineFunction.h" 18203954Srdivacky#include "llvm/CodeGen/MachineFunctionPass.h" 19203954Srdivacky#include "llvm/CodeGen/MachineInstr.h" 20327952Sdim#include "llvm/CodeGen/MachineOperand.h" 21203954Srdivacky#include "llvm/CodeGen/MachineRegisterInfo.h" 22327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 23327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 24360784Sdim#include "llvm/InitializePasses.h" 25327952Sdim#include "llvm/Pass.h" 26327952Sdim#include <cassert> 27327952Sdim 28203954Srdivackyusing namespace llvm; 29203954Srdivacky 30321369Sdim#define DEBUG_TYPE "opt-phis" 31276479Sdim 32203954SrdivackySTATISTIC(NumPHICycles, "Number of PHI cycles replaced"); 33203954SrdivackySTATISTIC(NumDeadPHICycles, "Number of dead PHI cycles"); 34203954Srdivacky 35203954Srdivackynamespace { 36327952Sdim 37203954Srdivacky class OptimizePHIs : public MachineFunctionPass { 38203954Srdivacky MachineRegisterInfo *MRI; 39203954Srdivacky const TargetInstrInfo *TII; 40203954Srdivacky 41203954Srdivacky public: 42203954Srdivacky static char ID; // Pass identification 43327952Sdim 44218893Sdim OptimizePHIs() : MachineFunctionPass(ID) { 45218893Sdim initializeOptimizePHIsPass(*PassRegistry::getPassRegistry()); 46218893Sdim } 47203954Srdivacky 48341825Sdim bool runOnMachineFunction(MachineFunction &Fn) override; 49203954Srdivacky 50276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 51203954Srdivacky AU.setPreservesCFG(); 52203954Srdivacky MachineFunctionPass::getAnalysisUsage(AU); 53203954Srdivacky } 54203954Srdivacky 55203954Srdivacky private: 56327952Sdim using InstrSet = SmallPtrSet<MachineInstr *, 16>; 57327952Sdim using InstrSetIterator = SmallPtrSetIterator<MachineInstr *>; 58203954Srdivacky 59203954Srdivacky bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg, 60203954Srdivacky InstrSet &PHIsInCycle); 61203954Srdivacky bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle); 62203954Srdivacky bool OptimizeBB(MachineBasicBlock &MBB); 63203954Srdivacky }; 64203954Srdivacky 65327952Sdim} // end anonymous namespace 66327952Sdim 67203954Srdivackychar OptimizePHIs::ID = 0; 68327952Sdim 69234353Sdimchar &llvm::OptimizePHIsID = OptimizePHIs::ID; 70327952Sdim 71321369SdimINITIALIZE_PASS(OptimizePHIs, DEBUG_TYPE, 72218893Sdim "Optimize machine instruction PHIs", false, false) 73203954Srdivacky 74203954Srdivackybool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) { 75327952Sdim if (skipFunction(Fn.getFunction())) 76276479Sdim return false; 77276479Sdim 78203954Srdivacky MRI = &Fn.getRegInfo(); 79280031Sdim TII = Fn.getSubtarget().getInstrInfo(); 80203954Srdivacky 81203954Srdivacky // Find dead PHI cycles and PHI cycles that can be replaced by a single 82203954Srdivacky // value. InstCombine does these optimizations, but DAG legalization may 83203954Srdivacky // introduce new opportunities, e.g., when i64 values are split up for 84203954Srdivacky // 32-bit targets. 85203954Srdivacky bool Changed = false; 86203954Srdivacky for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 87203954Srdivacky Changed |= OptimizeBB(*I); 88203954Srdivacky 89203954Srdivacky return Changed; 90203954Srdivacky} 91203954Srdivacky 92203954Srdivacky/// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands 93344779Sdim/// are copies of SingleValReg, possibly via copies through other PHIs. If 94203954Srdivacky/// SingleValReg is zero on entry, it is set to the register with the single 95344779Sdim/// non-copy value. PHIsInCycle is a set used to keep track of the PHIs that 96344779Sdim/// have been scanned. PHIs may be grouped by cycle, several cycles or chains. 97203954Srdivackybool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI, 98203954Srdivacky unsigned &SingleValReg, 99203954Srdivacky InstrSet &PHIsInCycle) { 100203954Srdivacky assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction"); 101360784Sdim Register DstReg = MI->getOperand(0).getReg(); 102203954Srdivacky 103203954Srdivacky // See if we already saw this register. 104280031Sdim if (!PHIsInCycle.insert(MI).second) 105203954Srdivacky return true; 106203954Srdivacky 107203954Srdivacky // Don't scan crazily complex things. 108203954Srdivacky if (PHIsInCycle.size() == 16) 109203954Srdivacky return false; 110203954Srdivacky 111203954Srdivacky // Scan the PHI operands. 112203954Srdivacky for (unsigned i = 1; i != MI->getNumOperands(); i += 2) { 113360784Sdim Register SrcReg = MI->getOperand(i).getReg(); 114203954Srdivacky if (SrcReg == DstReg) 115203954Srdivacky continue; 116203954Srdivacky MachineInstr *SrcMI = MRI->getVRegDef(SrcReg); 117203954Srdivacky 118203954Srdivacky // Skip over register-to-register moves. 119360784Sdim if (SrcMI && SrcMI->isCopy() && !SrcMI->getOperand(0).getSubReg() && 120212904Sdim !SrcMI->getOperand(1).getSubReg() && 121360784Sdim Register::isVirtualRegister(SrcMI->getOperand(1).getReg())) { 122344779Sdim SrcReg = SrcMI->getOperand(1).getReg(); 123344779Sdim SrcMI = MRI->getVRegDef(SrcReg); 124344779Sdim } 125203954Srdivacky if (!SrcMI) 126203954Srdivacky return false; 127203954Srdivacky 128203954Srdivacky if (SrcMI->isPHI()) { 129203954Srdivacky if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle)) 130203954Srdivacky return false; 131203954Srdivacky } else { 132203954Srdivacky // Fail if there is more than one non-phi/non-move register. 133344779Sdim if (SingleValReg != 0 && SingleValReg != SrcReg) 134203954Srdivacky return false; 135203954Srdivacky SingleValReg = SrcReg; 136203954Srdivacky } 137203954Srdivacky } 138203954Srdivacky return true; 139203954Srdivacky} 140203954Srdivacky 141203954Srdivacky/// IsDeadPHICycle - Check if the register defined by a PHI is only used by 142203954Srdivacky/// other PHIs in a cycle. 143203954Srdivackybool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) { 144203954Srdivacky assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction"); 145360784Sdim Register DstReg = MI->getOperand(0).getReg(); 146360784Sdim assert(Register::isVirtualRegister(DstReg) && 147203954Srdivacky "PHI destination is not a virtual register"); 148203954Srdivacky 149203954Srdivacky // See if we already saw this register. 150280031Sdim if (!PHIsInCycle.insert(MI).second) 151203954Srdivacky return true; 152203954Srdivacky 153203954Srdivacky // Don't scan crazily complex things. 154203954Srdivacky if (PHIsInCycle.size() == 16) 155203954Srdivacky return false; 156203954Srdivacky 157327952Sdim for (MachineInstr &UseMI : MRI->use_nodbg_instructions(DstReg)) { 158276479Sdim if (!UseMI.isPHI() || !IsDeadPHICycle(&UseMI, PHIsInCycle)) 159203954Srdivacky return false; 160203954Srdivacky } 161203954Srdivacky 162203954Srdivacky return true; 163203954Srdivacky} 164203954Srdivacky 165203954Srdivacky/// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by 166203954Srdivacky/// a single value. 167203954Srdivackybool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) { 168203954Srdivacky bool Changed = false; 169203954Srdivacky for (MachineBasicBlock::iterator 170203954Srdivacky MII = MBB.begin(), E = MBB.end(); MII != E; ) { 171203954Srdivacky MachineInstr *MI = &*MII++; 172203954Srdivacky if (!MI->isPHI()) 173203954Srdivacky break; 174203954Srdivacky 175203954Srdivacky // Check for single-value PHI cycles. 176203954Srdivacky unsigned SingleValReg = 0; 177203954Srdivacky InstrSet PHIsInCycle; 178203954Srdivacky if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) && 179203954Srdivacky SingleValReg != 0) { 180360784Sdim Register OldReg = MI->getOperand(0).getReg(); 181234353Sdim if (!MRI->constrainRegClass(SingleValReg, MRI->getRegClass(OldReg))) 182234353Sdim continue; 183234353Sdim 184353358Sdim MRI->replaceRegWith(OldReg, SingleValReg); 185353358Sdim MI->eraseFromParent(); 186353358Sdim 187353358Sdim // The kill flags on OldReg and SingleValReg may no longer be correct. 188344779Sdim MRI->clearKillFlags(SingleValReg); 189344779Sdim 190203954Srdivacky ++NumPHICycles; 191203954Srdivacky Changed = true; 192203954Srdivacky continue; 193203954Srdivacky } 194203954Srdivacky 195203954Srdivacky // Check for dead PHI cycles. 196203954Srdivacky PHIsInCycle.clear(); 197203954Srdivacky if (IsDeadPHICycle(MI, PHIsInCycle)) { 198203954Srdivacky for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end(); 199203954Srdivacky PI != PE; ++PI) { 200203954Srdivacky MachineInstr *PhiMI = *PI; 201314564Sdim if (MII == PhiMI) 202203954Srdivacky ++MII; 203203954Srdivacky PhiMI->eraseFromParent(); 204203954Srdivacky } 205203954Srdivacky ++NumDeadPHICycles; 206203954Srdivacky Changed = true; 207203954Srdivacky } 208203954Srdivacky } 209203954Srdivacky return Changed; 210203954Srdivacky} 211