1 //===-- lib/CodeGen/GlobalISel/GICombinerHelper.cpp -----------------------===// 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 #include "llvm/CodeGen/GlobalISel/CombinerHelper.h" 9 #include "llvm/CodeGen/GlobalISel/Combiner.h" 10 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h" 11 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h" 12 #include "llvm/CodeGen/GlobalISel/Utils.h" 13 #include "llvm/CodeGen/MachineInstr.h" 14 #include "llvm/CodeGen/MachineRegisterInfo.h" 15 #include "llvm/CodeGen/TargetInstrInfo.h" 16 17 #define DEBUG_TYPE "gi-combiner" 18 19 using namespace llvm; 20 21 CombinerHelper::CombinerHelper(GISelChangeObserver &Observer, 22 MachineIRBuilder &B) 23 : Builder(B), MRI(Builder.getMF().getRegInfo()), Observer(Observer) {} 24 25 void CombinerHelper::replaceRegWith(MachineRegisterInfo &MRI, unsigned FromReg, 26 unsigned ToReg) const { 27 Observer.changingAllUsesOfReg(MRI, FromReg); 28 29 if (MRI.constrainRegAttrs(ToReg, FromReg)) 30 MRI.replaceRegWith(FromReg, ToReg); 31 else 32 Builder.buildCopy(ToReg, FromReg); 33 34 Observer.finishedChangingAllUsesOfReg(); 35 } 36 37 void CombinerHelper::replaceRegOpWith(MachineRegisterInfo &MRI, 38 MachineOperand &FromRegOp, 39 unsigned ToReg) const { 40 assert(FromRegOp.getParent() && "Expected an operand in an MI"); 41 Observer.changingInstr(*FromRegOp.getParent()); 42 43 FromRegOp.setReg(ToReg); 44 45 Observer.changedInstr(*FromRegOp.getParent()); 46 } 47 48 bool CombinerHelper::tryCombineCopy(MachineInstr &MI) { 49 if (MI.getOpcode() != TargetOpcode::COPY) 50 return false; 51 unsigned DstReg = MI.getOperand(0).getReg(); 52 unsigned SrcReg = MI.getOperand(1).getReg(); 53 LLT DstTy = MRI.getType(DstReg); 54 LLT SrcTy = MRI.getType(SrcReg); 55 // Simple Copy Propagation. 56 // a(sx) = COPY b(sx) -> Replace all uses of a with b. 57 if (DstTy.isValid() && SrcTy.isValid() && DstTy == SrcTy) { 58 MI.eraseFromParent(); 59 replaceRegWith(MRI, DstReg, SrcReg); 60 return true; 61 } 62 return false; 63 } 64 65 namespace { 66 struct PreferredTuple { 67 LLT Ty; // The result type of the extend. 68 unsigned ExtendOpcode; // G_ANYEXT/G_SEXT/G_ZEXT 69 MachineInstr *MI; 70 }; 71 72 /// Select a preference between two uses. CurrentUse is the current preference 73 /// while *ForCandidate is attributes of the candidate under consideration. 74 PreferredTuple ChoosePreferredUse(PreferredTuple &CurrentUse, 75 const LLT &TyForCandidate, 76 unsigned OpcodeForCandidate, 77 MachineInstr *MIForCandidate) { 78 if (!CurrentUse.Ty.isValid()) { 79 if (CurrentUse.ExtendOpcode == OpcodeForCandidate || 80 CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT) 81 return {TyForCandidate, OpcodeForCandidate, MIForCandidate}; 82 return CurrentUse; 83 } 84 85 // We permit the extend to hoist through basic blocks but this is only 86 // sensible if the target has extending loads. If you end up lowering back 87 // into a load and extend during the legalizer then the end result is 88 // hoisting the extend up to the load. 89 90 // Prefer defined extensions to undefined extensions as these are more 91 // likely to reduce the number of instructions. 92 if (OpcodeForCandidate == TargetOpcode::G_ANYEXT && 93 CurrentUse.ExtendOpcode != TargetOpcode::G_ANYEXT) 94 return CurrentUse; 95 else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT && 96 OpcodeForCandidate != TargetOpcode::G_ANYEXT) 97 return {TyForCandidate, OpcodeForCandidate, MIForCandidate}; 98 99 // Prefer sign extensions to zero extensions as sign-extensions tend to be 100 // more expensive. 101 if (CurrentUse.Ty == TyForCandidate) { 102 if (CurrentUse.ExtendOpcode == TargetOpcode::G_SEXT && 103 OpcodeForCandidate == TargetOpcode::G_ZEXT) 104 return CurrentUse; 105 else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ZEXT && 106 OpcodeForCandidate == TargetOpcode::G_SEXT) 107 return {TyForCandidate, OpcodeForCandidate, MIForCandidate}; 108 } 109 110 // This is potentially target specific. We've chosen the largest type 111 // because G_TRUNC is usually free. One potential catch with this is that 112 // some targets have a reduced number of larger registers than smaller 113 // registers and this choice potentially increases the live-range for the 114 // larger value. 115 if (TyForCandidate.getSizeInBits() > CurrentUse.Ty.getSizeInBits()) { 116 return {TyForCandidate, OpcodeForCandidate, MIForCandidate}; 117 } 118 return CurrentUse; 119 } 120 121 /// Find a suitable place to insert some instructions and insert them. This 122 /// function accounts for special cases like inserting before a PHI node. 123 /// The current strategy for inserting before PHI's is to duplicate the 124 /// instructions for each predecessor. However, while that's ok for G_TRUNC 125 /// on most targets since it generally requires no code, other targets/cases may 126 /// want to try harder to find a dominating block. 127 static void InsertInsnsWithoutSideEffectsBeforeUse( 128 MachineIRBuilder &Builder, MachineInstr &DefMI, MachineOperand &UseMO, 129 std::function<void(MachineBasicBlock *, MachineBasicBlock::iterator)> 130 Inserter) { 131 MachineInstr &UseMI = *UseMO.getParent(); 132 133 MachineBasicBlock *InsertBB = UseMI.getParent(); 134 135 // If the use is a PHI then we want the predecessor block instead. 136 if (UseMI.isPHI()) { 137 MachineOperand *PredBB = std::next(&UseMO); 138 InsertBB = PredBB->getMBB(); 139 } 140 141 // If the block is the same block as the def then we want to insert just after 142 // the def instead of at the start of the block. 143 if (InsertBB == DefMI.getParent()) { 144 MachineBasicBlock::iterator InsertPt = &DefMI; 145 Inserter(InsertBB, std::next(InsertPt)); 146 return; 147 } 148 149 // Otherwise we want the start of the BB 150 Inserter(InsertBB, InsertBB->getFirstNonPHI()); 151 } 152 } // end anonymous namespace 153 154 bool CombinerHelper::tryCombineExtendingLoads(MachineInstr &MI) { 155 struct InsertionPoint { 156 MachineOperand *UseMO; 157 MachineBasicBlock *InsertIntoBB; 158 MachineBasicBlock::iterator InsertBefore; 159 InsertionPoint(MachineOperand *UseMO, MachineBasicBlock *InsertIntoBB, 160 MachineBasicBlock::iterator InsertBefore) 161 : UseMO(UseMO), InsertIntoBB(InsertIntoBB), InsertBefore(InsertBefore) { 162 } 163 }; 164 165 // We match the loads and follow the uses to the extend instead of matching 166 // the extends and following the def to the load. This is because the load 167 // must remain in the same position for correctness (unless we also add code 168 // to find a safe place to sink it) whereas the extend is freely movable. 169 // It also prevents us from duplicating the load for the volatile case or just 170 // for performance. 171 172 if (MI.getOpcode() != TargetOpcode::G_LOAD && 173 MI.getOpcode() != TargetOpcode::G_SEXTLOAD && 174 MI.getOpcode() != TargetOpcode::G_ZEXTLOAD) 175 return false; 176 177 auto &LoadValue = MI.getOperand(0); 178 assert(LoadValue.isReg() && "Result wasn't a register?"); 179 180 LLT LoadValueTy = MRI.getType(LoadValue.getReg()); 181 if (!LoadValueTy.isScalar()) 182 return false; 183 184 // Find the preferred type aside from the any-extends (unless it's the only 185 // one) and non-extending ops. We'll emit an extending load to that type and 186 // and emit a variant of (extend (trunc X)) for the others according to the 187 // relative type sizes. At the same time, pick an extend to use based on the 188 // extend involved in the chosen type. 189 unsigned PreferredOpcode = MI.getOpcode() == TargetOpcode::G_LOAD 190 ? TargetOpcode::G_ANYEXT 191 : MI.getOpcode() == TargetOpcode::G_SEXTLOAD 192 ? TargetOpcode::G_SEXT 193 : TargetOpcode::G_ZEXT; 194 PreferredTuple Preferred = {LLT(), PreferredOpcode, nullptr}; 195 for (auto &UseMI : MRI.use_instructions(LoadValue.getReg())) { 196 if (UseMI.getOpcode() == TargetOpcode::G_SEXT || 197 UseMI.getOpcode() == TargetOpcode::G_ZEXT || 198 UseMI.getOpcode() == TargetOpcode::G_ANYEXT) { 199 Preferred = ChoosePreferredUse(Preferred, 200 MRI.getType(UseMI.getOperand(0).getReg()), 201 UseMI.getOpcode(), &UseMI); 202 } 203 } 204 205 // There were no extends 206 if (!Preferred.MI) 207 return false; 208 // It should be impossible to chose an extend without selecting a different 209 // type since by definition the result of an extend is larger. 210 assert(Preferred.Ty != LoadValueTy && "Extending to same type?"); 211 212 LLVM_DEBUG(dbgs() << "Preferred use is: " << *Preferred.MI); 213 214 // Rewrite the load to the chosen extending load. 215 unsigned ChosenDstReg = Preferred.MI->getOperand(0).getReg(); 216 Observer.changingInstr(MI); 217 MI.setDesc( 218 Builder.getTII().get(Preferred.ExtendOpcode == TargetOpcode::G_SEXT 219 ? TargetOpcode::G_SEXTLOAD 220 : Preferred.ExtendOpcode == TargetOpcode::G_ZEXT 221 ? TargetOpcode::G_ZEXTLOAD 222 : TargetOpcode::G_LOAD)); 223 224 // Rewrite all the uses to fix up the types. 225 SmallVector<MachineInstr *, 1> ScheduleForErase; 226 SmallVector<InsertionPoint, 4> ScheduleForInsert; 227 for (auto &UseMO : MRI.use_operands(LoadValue.getReg())) { 228 MachineInstr *UseMI = UseMO.getParent(); 229 230 // If the extend is compatible with the preferred extend then we should fix 231 // up the type and extend so that it uses the preferred use. 232 if (UseMI->getOpcode() == Preferred.ExtendOpcode || 233 UseMI->getOpcode() == TargetOpcode::G_ANYEXT) { 234 unsigned UseDstReg = UseMI->getOperand(0).getReg(); 235 MachineOperand &UseSrcMO = UseMI->getOperand(1); 236 const LLT &UseDstTy = MRI.getType(UseDstReg); 237 if (UseDstReg != ChosenDstReg) { 238 if (Preferred.Ty == UseDstTy) { 239 // If the use has the same type as the preferred use, then merge 240 // the vregs and erase the extend. For example: 241 // %1:_(s8) = G_LOAD ... 242 // %2:_(s32) = G_SEXT %1(s8) 243 // %3:_(s32) = G_ANYEXT %1(s8) 244 // ... = ... %3(s32) 245 // rewrites to: 246 // %2:_(s32) = G_SEXTLOAD ... 247 // ... = ... %2(s32) 248 replaceRegWith(MRI, UseDstReg, ChosenDstReg); 249 ScheduleForErase.push_back(UseMO.getParent()); 250 } else if (Preferred.Ty.getSizeInBits() < UseDstTy.getSizeInBits()) { 251 // If the preferred size is smaller, then keep the extend but extend 252 // from the result of the extending load. For example: 253 // %1:_(s8) = G_LOAD ... 254 // %2:_(s32) = G_SEXT %1(s8) 255 // %3:_(s64) = G_ANYEXT %1(s8) 256 // ... = ... %3(s64) 257 /// rewrites to: 258 // %2:_(s32) = G_SEXTLOAD ... 259 // %3:_(s64) = G_ANYEXT %2:_(s32) 260 // ... = ... %3(s64) 261 replaceRegOpWith(MRI, UseSrcMO, ChosenDstReg); 262 } else { 263 // If the preferred size is large, then insert a truncate. For 264 // example: 265 // %1:_(s8) = G_LOAD ... 266 // %2:_(s64) = G_SEXT %1(s8) 267 // %3:_(s32) = G_ZEXT %1(s8) 268 // ... = ... %3(s32) 269 /// rewrites to: 270 // %2:_(s64) = G_SEXTLOAD ... 271 // %4:_(s8) = G_TRUNC %2:_(s32) 272 // %3:_(s64) = G_ZEXT %2:_(s8) 273 // ... = ... %3(s64) 274 InsertInsnsWithoutSideEffectsBeforeUse( 275 Builder, MI, UseMO, 276 [&](MachineBasicBlock *InsertIntoBB, 277 MachineBasicBlock::iterator InsertBefore) { 278 ScheduleForInsert.emplace_back(&UseMO, InsertIntoBB, InsertBefore); 279 }); 280 } 281 continue; 282 } 283 // The use is (one of) the uses of the preferred use we chose earlier. 284 // We're going to update the load to def this value later so just erase 285 // the old extend. 286 ScheduleForErase.push_back(UseMO.getParent()); 287 continue; 288 } 289 290 // The use isn't an extend. Truncate back to the type we originally loaded. 291 // This is free on many targets. 292 InsertInsnsWithoutSideEffectsBeforeUse( 293 Builder, MI, UseMO, 294 [&](MachineBasicBlock *InsertIntoBB, 295 MachineBasicBlock::iterator InsertBefore) { 296 ScheduleForInsert.emplace_back(&UseMO, InsertIntoBB, InsertBefore); 297 }); 298 } 299 300 DenseMap<MachineBasicBlock *, MachineInstr *> EmittedInsns; 301 for (auto &InsertionInfo : ScheduleForInsert) { 302 MachineOperand *UseMO = InsertionInfo.UseMO; 303 MachineBasicBlock *InsertIntoBB = InsertionInfo.InsertIntoBB; 304 MachineBasicBlock::iterator InsertBefore = InsertionInfo.InsertBefore; 305 306 MachineInstr *PreviouslyEmitted = EmittedInsns.lookup(InsertIntoBB); 307 if (PreviouslyEmitted) { 308 Observer.changingInstr(*UseMO->getParent()); 309 UseMO->setReg(PreviouslyEmitted->getOperand(0).getReg()); 310 Observer.changedInstr(*UseMO->getParent()); 311 continue; 312 } 313 314 Builder.setInsertPt(*InsertIntoBB, InsertBefore); 315 unsigned NewDstReg = MRI.cloneVirtualRegister(MI.getOperand(0).getReg()); 316 MachineInstr *NewMI = Builder.buildTrunc(NewDstReg, ChosenDstReg); 317 EmittedInsns[InsertIntoBB] = NewMI; 318 replaceRegOpWith(MRI, *UseMO, NewDstReg); 319 } 320 for (auto &EraseMI : ScheduleForErase) { 321 Observer.erasingInstr(*EraseMI); 322 EraseMI->eraseFromParent(); 323 } 324 MI.getOperand(0).setReg(ChosenDstReg); 325 Observer.changedInstr(MI); 326 327 return true; 328 } 329 330 bool CombinerHelper::tryCombine(MachineInstr &MI) { 331 if (tryCombineCopy(MI)) 332 return true; 333 return tryCombineExtendingLoads(MI); 334 } 335