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