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