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/Analysis/TargetTransformInfo.h" 14 #include "llvm/ADT/DenseMap.h" 15 #include "llvm/CodeGen/MachineRegisterInfo.h" 16 #include "llvm/Support/Debug.h" 17 18 #define DEBUG_TYPE "localizer" 19 20 using namespace llvm; 21 22 char Localizer::ID = 0; 23 INITIALIZE_PASS_BEGIN(Localizer, DEBUG_TYPE, 24 "Move/duplicate certain instructions close to their use", 25 false, false) 26 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 27 INITIALIZE_PASS_END(Localizer, DEBUG_TYPE, 28 "Move/duplicate certain instructions close to their use", 29 false, false) 30 31 Localizer::Localizer() : MachineFunctionPass(ID) { } 32 33 void Localizer::init(MachineFunction &MF) { 34 MRI = &MF.getRegInfo(); 35 TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(MF.getFunction()); 36 } 37 38 bool Localizer::shouldLocalize(const MachineInstr &MI) { 39 // Assuming a spill and reload of a value has a cost of 1 instruction each, 40 // this helper function computes the maximum number of uses we should consider 41 // for remat. E.g. on arm64 global addresses take 2 insts to materialize. We 42 // break even in terms of code size when the original MI has 2 users vs 43 // choosing to potentially spill. Any more than 2 users we we have a net code 44 // size increase. This doesn't take into account register pressure though. 45 auto maxUses = [](unsigned RematCost) { 46 // A cost of 1 means remats are basically free. 47 if (RematCost == 1) 48 return UINT_MAX; 49 if (RematCost == 2) 50 return 2U; 51 52 // Remat is too expensive, only sink if there's one user. 53 if (RematCost > 2) 54 return 1U; 55 llvm_unreachable("Unexpected remat cost"); 56 }; 57 58 // Helper to walk through uses and terminate if we've reached a limit. Saves 59 // us spending time traversing uses if all we want to know is if it's >= min. 60 auto isUsesAtMost = [&](unsigned Reg, unsigned MaxUses) { 61 unsigned NumUses = 0; 62 auto UI = MRI->use_instr_nodbg_begin(Reg), UE = MRI->use_instr_nodbg_end(); 63 for (; UI != UE && NumUses < MaxUses; ++UI) { 64 NumUses++; 65 } 66 // If we haven't reached the end yet then there are more than MaxUses users. 67 return UI == UE; 68 }; 69 70 switch (MI.getOpcode()) { 71 default: 72 return false; 73 // Constants-like instructions should be close to their users. 74 // We don't want long live-ranges for them. 75 case TargetOpcode::G_CONSTANT: 76 case TargetOpcode::G_FCONSTANT: 77 case TargetOpcode::G_FRAME_INDEX: 78 case TargetOpcode::G_INTTOPTR: 79 return true; 80 case TargetOpcode::G_GLOBAL_VALUE: { 81 unsigned RematCost = TTI->getGISelRematGlobalCost(); 82 unsigned Reg = MI.getOperand(0).getReg(); 83 unsigned MaxUses = maxUses(RematCost); 84 if (MaxUses == UINT_MAX) 85 return true; // Remats are "free" so always localize. 86 bool B = isUsesAtMost(Reg, MaxUses); 87 return B; 88 } 89 } 90 } 91 92 void Localizer::getAnalysisUsage(AnalysisUsage &AU) const { 93 AU.addRequired<TargetTransformInfoWrapperPass>(); 94 getSelectionDAGFallbackAnalysisUsage(AU); 95 MachineFunctionPass::getAnalysisUsage(AU); 96 } 97 98 bool Localizer::isLocalUse(MachineOperand &MOUse, const MachineInstr &Def, 99 MachineBasicBlock *&InsertMBB) { 100 MachineInstr &MIUse = *MOUse.getParent(); 101 InsertMBB = MIUse.getParent(); 102 if (MIUse.isPHI()) 103 InsertMBB = MIUse.getOperand(MIUse.getOperandNo(&MOUse) + 1).getMBB(); 104 return InsertMBB == Def.getParent(); 105 } 106 107 bool Localizer::localizeInterBlock(MachineFunction &MF, 108 LocalizedSetVecT &LocalizedInstrs) { 109 bool Changed = false; 110 DenseMap<std::pair<MachineBasicBlock *, unsigned>, unsigned> MBBWithLocalDef; 111 112 // Since the IRTranslator only emits constants into the entry block, and the 113 // rest of the GISel pipeline generally emits constants close to their users, 114 // we only localize instructions in the entry block here. This might change if 115 // we start doing CSE across blocks. 116 auto &MBB = MF.front(); 117 for (auto RI = MBB.rbegin(), RE = MBB.rend(); RI != RE; ++RI) { 118 MachineInstr &MI = *RI; 119 if (!shouldLocalize(MI)) 120 continue; 121 LLVM_DEBUG(dbgs() << "Should localize: " << MI); 122 assert(MI.getDesc().getNumDefs() == 1 && 123 "More than one definition not supported yet"); 124 unsigned Reg = MI.getOperand(0).getReg(); 125 // Check if all the users of MI are local. 126 // We are going to invalidation the list of use operands, so we 127 // can't use range iterator. 128 for (auto MOIt = MRI->use_begin(Reg), MOItEnd = MRI->use_end(); 129 MOIt != MOItEnd;) { 130 MachineOperand &MOUse = *MOIt++; 131 // Check if the use is already local. 132 MachineBasicBlock *InsertMBB; 133 LLVM_DEBUG(MachineInstr &MIUse = *MOUse.getParent(); 134 dbgs() << "Checking use: " << MIUse 135 << " #Opd: " << MIUse.getOperandNo(&MOUse) << '\n'); 136 if (isLocalUse(MOUse, MI, InsertMBB)) 137 continue; 138 LLVM_DEBUG(dbgs() << "Fixing non-local use\n"); 139 Changed = true; 140 auto MBBAndReg = std::make_pair(InsertMBB, Reg); 141 auto NewVRegIt = MBBWithLocalDef.find(MBBAndReg); 142 if (NewVRegIt == MBBWithLocalDef.end()) { 143 // Create the localized instruction. 144 MachineInstr *LocalizedMI = MF.CloneMachineInstr(&MI); 145 LocalizedInstrs.insert(LocalizedMI); 146 MachineInstr &UseMI = *MOUse.getParent(); 147 if (MRI->hasOneUse(Reg) && !UseMI.isPHI()) 148 InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(UseMI), LocalizedMI); 149 else 150 InsertMBB->insert(InsertMBB->SkipPHIsAndLabels(InsertMBB->begin()), 151 LocalizedMI); 152 153 // Set a new register for the definition. 154 unsigned NewReg = MRI->createGenericVirtualRegister(MRI->getType(Reg)); 155 MRI->setRegClassOrRegBank(NewReg, MRI->getRegClassOrRegBank(Reg)); 156 LocalizedMI->getOperand(0).setReg(NewReg); 157 NewVRegIt = 158 MBBWithLocalDef.insert(std::make_pair(MBBAndReg, NewReg)).first; 159 LLVM_DEBUG(dbgs() << "Inserted: " << *LocalizedMI); 160 } 161 LLVM_DEBUG(dbgs() << "Update use with: " << printReg(NewVRegIt->second) 162 << '\n'); 163 // Update the user reg. 164 MOUse.setReg(NewVRegIt->second); 165 } 166 } 167 return Changed; 168 } 169 170 bool Localizer::localizeIntraBlock(LocalizedSetVecT &LocalizedInstrs) { 171 bool Changed = false; 172 173 // For each already-localized instruction which has multiple users, then we 174 // scan the block top down from the current position until we hit one of them. 175 176 // FIXME: Consider doing inst duplication if live ranges are very long due to 177 // many users, but this case may be better served by regalloc improvements. 178 179 for (MachineInstr *MI : LocalizedInstrs) { 180 unsigned Reg = MI->getOperand(0).getReg(); 181 MachineBasicBlock &MBB = *MI->getParent(); 182 // All of the user MIs of this reg. 183 SmallPtrSet<MachineInstr *, 32> Users; 184 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) { 185 if (!UseMI.isPHI()) 186 Users.insert(&UseMI); 187 } 188 // If all the users were PHIs then they're not going to be in our block, 189 // don't try to move this instruction. 190 if (Users.empty()) 191 continue; 192 193 MachineBasicBlock::iterator II(MI); 194 ++II; 195 while (II != MBB.end() && !Users.count(&*II)) 196 ++II; 197 198 LLVM_DEBUG(dbgs() << "Intra-block: moving " << *MI << " before " << *&*II 199 << "\n"); 200 assert(II != MBB.end() && "Didn't find the user in the MBB"); 201 MI->removeFromParent(); 202 MBB.insert(II, MI); 203 Changed = true; 204 } 205 return Changed; 206 } 207 208 bool Localizer::runOnMachineFunction(MachineFunction &MF) { 209 // If the ISel pipeline failed, do not bother running that pass. 210 if (MF.getProperties().hasProperty( 211 MachineFunctionProperties::Property::FailedISel)) 212 return false; 213 214 LLVM_DEBUG(dbgs() << "Localize instructions for: " << MF.getName() << '\n'); 215 216 init(MF); 217 218 // Keep track of the instructions we localized. We'll do a second pass of 219 // intra-block localization to further reduce live ranges. 220 LocalizedSetVecT LocalizedInstrs; 221 222 bool Changed = localizeInterBlock(MF, LocalizedInstrs); 223 return Changed |= localizeIntraBlock(LocalizedInstrs); 224 } 225