225 lines · cpp
1//===- Localizer.cpp ---------------------- Localize some instrs -*- C++ -*-==//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/// \file9/// This file implements the Localizer class.10//===----------------------------------------------------------------------===//11 12#include "llvm/CodeGen/GlobalISel/Localizer.h"13#include "llvm/ADT/DenseMap.h"14#include "llvm/ADT/STLExtras.h"15#include "llvm/Analysis/TargetTransformInfo.h"16#include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"17#include "llvm/CodeGen/GlobalISel/Utils.h"18#include "llvm/CodeGen/MachineRegisterInfo.h"19#include "llvm/CodeGen/TargetLowering.h"20#include "llvm/InitializePasses.h"21#include "llvm/Support/Debug.h"22 23#define DEBUG_TYPE "localizer"24 25using namespace llvm;26 27char Localizer::ID = 0;28INITIALIZE_PASS_BEGIN(Localizer, DEBUG_TYPE,29 "Move/duplicate certain instructions close to their use",30 false, false)31INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)32INITIALIZE_PASS_END(Localizer, DEBUG_TYPE,33 "Move/duplicate certain instructions close to their use",34 false, false)35 36Localizer::Localizer(std::function<bool(const MachineFunction &)> F)37 : MachineFunctionPass(ID), DoNotRunPass(F) {}38 39Localizer::Localizer()40 : Localizer([](const MachineFunction &) { return false; }) {}41 42void Localizer::init(MachineFunction &MF) {43 MRI = &MF.getRegInfo();44 TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(MF.getFunction());45}46 47void Localizer::getAnalysisUsage(AnalysisUsage &AU) const {48 AU.addRequired<TargetTransformInfoWrapperPass>();49 getSelectionDAGFallbackAnalysisUsage(AU);50 MachineFunctionPass::getAnalysisUsage(AU);51}52 53bool Localizer::isLocalUse(MachineOperand &MOUse, const MachineInstr &Def,54 MachineBasicBlock *&InsertMBB) {55 MachineInstr &MIUse = *MOUse.getParent();56 InsertMBB = MIUse.getParent();57 if (MIUse.isPHI())58 InsertMBB = MIUse.getOperand(MOUse.getOperandNo() + 1).getMBB();59 return InsertMBB == Def.getParent();60}61 62unsigned Localizer::getNumPhiUses(MachineOperand &Op) const {63 auto *MI = dyn_cast<GPhi>(&*Op.getParent());64 if (!MI)65 return 0;66 67 Register SrcReg = Op.getReg();68 unsigned NumUses = 0;69 for (unsigned I = 0, NumVals = MI->getNumIncomingValues(); I < NumVals; ++I) {70 if (MI->getIncomingValue(I) == SrcReg)71 ++NumUses;72 }73 return NumUses;74}75 76bool Localizer::localizeInterBlock(MachineFunction &MF,77 LocalizedSetVecT &LocalizedInstrs) {78 bool Changed = false;79 DenseMap<std::pair<MachineBasicBlock *, Register>, Register> MBBWithLocalDef;80 81 // Since the IRTranslator only emits constants into the entry block, and the82 // rest of the GISel pipeline generally emits constants close to their users,83 // we only localize instructions in the entry block here. This might change if84 // we start doing CSE across blocks.85 auto &MBB = MF.front();86 auto &TL = *MF.getSubtarget().getTargetLowering();87 for (MachineInstr &MI : llvm::reverse(MBB)) {88 if (!TL.shouldLocalize(MI, TTI))89 continue;90 LLVM_DEBUG(dbgs() << "Should localize: " << MI);91 assert(MI.getDesc().getNumDefs() == 1 &&92 "More than one definition not supported yet");93 Register Reg = MI.getOperand(0).getReg();94 // Check if all the users of MI are local.95 // We are going to invalidation the list of use operands, so we96 // can't use range iterator.97 for (MachineOperand &MOUse :98 llvm::make_early_inc_range(MRI->use_operands(Reg))) {99 // Check if the use is already local.100 MachineBasicBlock *InsertMBB;101 LLVM_DEBUG(MachineInstr &MIUse = *MOUse.getParent();102 dbgs() << "Checking use: " << MIUse103 << " #Opd: " << MOUse.getOperandNo() << '\n');104 if (isLocalUse(MOUse, MI, InsertMBB)) {105 // Even if we're in the same block, if the block is very large we could106 // still have many long live ranges. Try to do intra-block localization107 // too.108 LocalizedInstrs.insert(&MI);109 continue;110 }111 112 // PHIs look like a single user but can use the same register in multiple113 // edges, causing remat into each predecessor. Allow this to a certain114 // extent.115 unsigned NumPhiUses = getNumPhiUses(MOUse);116 const unsigned PhiThreshold = 2; // FIXME: Tune this more.117 if (NumPhiUses > PhiThreshold)118 continue;119 120 LLVM_DEBUG(dbgs() << "Fixing non-local use\n");121 Changed = true;122 auto MBBAndReg = std::make_pair(InsertMBB, Reg);123 auto NewVRegIt = MBBWithLocalDef.find(MBBAndReg);124 if (NewVRegIt == MBBWithLocalDef.end()) {125 // Create the localized instruction.126 MachineInstr *LocalizedMI = MF.CloneMachineInstr(&MI);127 LocalizedInstrs.insert(LocalizedMI);128 MachineInstr &UseMI = *MOUse.getParent();129 if (MRI->hasOneUse(Reg) && !UseMI.isPHI())130 InsertMBB->insert(UseMI, LocalizedMI);131 else132 InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(InsertMBB->begin()),133 LocalizedMI);134 135 // Set a new register for the definition.136 Register NewReg = MRI->cloneVirtualRegister(Reg);137 LocalizedMI->getOperand(0).setReg(NewReg);138 NewVRegIt =139 MBBWithLocalDef.try_emplace(MBBAndReg, NewReg).first;140 LLVM_DEBUG(dbgs() << "Inserted: " << *LocalizedMI);141 }142 LLVM_DEBUG(dbgs() << "Update use with: " << printReg(NewVRegIt->second)143 << '\n');144 // Update the user reg.145 MOUse.setReg(NewVRegIt->second);146 }147 }148 return Changed;149}150 151bool Localizer::localizeIntraBlock(LocalizedSetVecT &LocalizedInstrs) {152 bool Changed = false;153 154 // For each already-localized instruction which has multiple users, then we155 // scan the block top down from the current position until we hit one of them.156 157 // FIXME: Consider doing inst duplication if live ranges are very long due to158 // many users, but this case may be better served by regalloc improvements.159 160 for (MachineInstr *MI : LocalizedInstrs) {161 Register Reg = MI->getOperand(0).getReg();162 MachineBasicBlock &MBB = *MI->getParent();163 // All of the user MIs of this reg.164 SmallPtrSet<MachineInstr *, 32> Users;165 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {166 if (!UseMI.isPHI())167 Users.insert(&UseMI);168 }169 MachineBasicBlock::iterator II(MI);170 // If all the users were PHIs then they're not going to be in our block, we171 // may still benefit from sinking, especially since the value might be live172 // across a call.173 if (Users.empty()) {174 // Make sure we don't sink in between two terminator sequences by scanning175 // forward, not backward.176 II = MBB.getFirstTerminatorForward();177 LLVM_DEBUG(dbgs() << "Only phi users: moving inst to end: " << *MI);178 } else {179 ++II;180 while (II != MBB.end() && !Users.count(&*II))181 ++II;182 assert(II != MBB.end() && "Didn't find the user in the MBB");183 LLVM_DEBUG(dbgs() << "Intra-block: moving " << *MI << " before " << *II);184 }185 186 MI->removeFromParent();187 MBB.insert(II, MI);188 Changed = true;189 190 // If the instruction (constant) being localized has single user, we can191 // propagate debug location from user.192 if (Users.size() == 1) {193 const auto &DefDL = MI->getDebugLoc();194 const auto &UserDL = (*Users.begin())->getDebugLoc();195 196 if ((!DefDL || DefDL.getLine() == 0) && UserDL && UserDL.getLine() != 0) {197 MI->setDebugLoc(UserDL);198 }199 }200 }201 return Changed;202}203 204bool Localizer::runOnMachineFunction(MachineFunction &MF) {205 // If the ISel pipeline failed, do not bother running that pass.206 if (MF.getProperties().hasFailedISel())207 return false;208 209 // Don't run the pass if the target asked so.210 if (DoNotRunPass(MF))211 return false;212 213 LLVM_DEBUG(dbgs() << "Localize instructions for: " << MF.getName() << '\n');214 215 init(MF);216 217 // Keep track of the instructions we localized. We'll do a second pass of218 // intra-block localization to further reduce live ranges.219 LocalizedSetVecT LocalizedInstrs;220 221 bool Changed = localizeInterBlock(MF, LocalizedInstrs);222 Changed |= localizeIntraBlock(LocalizedInstrs);223 return Changed;224}225