1 //===- X86AvoidStoreForwardingBlockis.cpp - Avoid HW Store Forward Block --===// 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 // 10 // If a load follows a store and reloads data that the store has written to 11 // memory, Intel microarchitectures can in many cases forward the data directly 12 // from the store to the load, This "store forwarding" saves cycles by enabling 13 // the load to directly obtain the data instead of accessing the data from 14 // cache or memory. 15 // A "store forward block" occurs in cases that a store cannot be forwarded to 16 // the load. The most typical case of store forward block on Intel Core 17 // microarchitecture that a small store cannot be forwarded to a large load. 18 // The estimated penalty for a store forward block is ~13 cycles. 19 // 20 // This pass tries to recognize and handle cases where "store forward block" 21 // is created by the compiler when lowering memcpy calls to a sequence 22 // of a load and a store. 23 // 24 // The pass currently only handles cases where memcpy is lowered to 25 // XMM/YMM registers, it tries to break the memcpy into smaller copies. 26 // breaking the memcpy should be possible since there is no atomicity 27 // guarantee for loads and stores to XMM/YMM. 28 // 29 // It could be better for performance to solve the problem by loading 30 // to XMM/YMM then inserting the partial store before storing back from XMM/YMM 31 // to memory, but this will result in a more conservative optimization since it 32 // requires we prove that all memory accesses between the blocking store and the 33 // load must alias/don't alias before we can move the store, whereas the 34 // transformation done here is correct regardless to other memory accesses. 35 //===----------------------------------------------------------------------===// 36 37 #include "X86InstrInfo.h" 38 #include "X86Subtarget.h" 39 #include "llvm/CodeGen/MachineBasicBlock.h" 40 #include "llvm/CodeGen/MachineFunction.h" 41 #include "llvm/CodeGen/MachineFunctionPass.h" 42 #include "llvm/CodeGen/MachineInstr.h" 43 #include "llvm/CodeGen/MachineInstrBuilder.h" 44 #include "llvm/CodeGen/MachineOperand.h" 45 #include "llvm/CodeGen/MachineRegisterInfo.h" 46 #include "llvm/IR/DebugInfoMetadata.h" 47 #include "llvm/IR/DebugLoc.h" 48 #include "llvm/IR/Function.h" 49 #include "llvm/MC/MCInstrDesc.h" 50 51 using namespace llvm; 52 53 #define DEBUG_TYPE "x86-avoid-SFB" 54 55 namespace llvm { 56 void initializeX86AvoidSFBPassPass(PassRegistry &); 57 } // end namespace llvm 58 59 static cl::opt<bool> DisableX86AvoidStoreForwardBlocks( 60 "x86-disable-avoid-SFB", cl::Hidden, 61 cl::desc("X86: Disable Store Forwarding Blocks fixup."), cl::init(false)); 62 63 static cl::opt<unsigned> X86AvoidSFBInspectionLimit( 64 "x86-sfb-inspection-limit", 65 cl::desc("X86: Number of instructions backward to " 66 "inspect for store forwarding blocks."), 67 cl::init(20), cl::Hidden); 68 69 namespace { 70 71 using DisplacementSizeMap = std::map<int64_t, unsigned>; 72 73 class X86AvoidSFBPass : public MachineFunctionPass { 74 public: 75 static char ID; 76 X86AvoidSFBPass() : MachineFunctionPass(ID) { 77 initializeX86AvoidSFBPassPass(*PassRegistry::getPassRegistry()); 78 } 79 80 StringRef getPassName() const override { 81 return "X86 Avoid Store Forwarding Blocks"; 82 } 83 84 bool runOnMachineFunction(MachineFunction &MF) override; 85 86 void getAnalysisUsage(AnalysisUsage &AU) const override { 87 MachineFunctionPass::getAnalysisUsage(AU); 88 AU.addRequired<AAResultsWrapperPass>(); 89 } 90 91 private: 92 MachineRegisterInfo *MRI; 93 const X86InstrInfo *TII; 94 const X86RegisterInfo *TRI; 95 SmallVector<std::pair<MachineInstr *, MachineInstr *>, 2> 96 BlockedLoadsStoresPairs; 97 SmallVector<MachineInstr *, 2> ForRemoval; 98 AliasAnalysis *AA; 99 100 /// Returns couples of Load then Store to memory which look 101 /// like a memcpy. 102 void findPotentiallylBlockedCopies(MachineFunction &MF); 103 /// Break the memcpy's load and store into smaller copies 104 /// such that each memory load that was blocked by a smaller store 105 /// would now be copied separately. 106 void breakBlockedCopies(MachineInstr *LoadInst, MachineInstr *StoreInst, 107 const DisplacementSizeMap &BlockingStoresDispSizeMap); 108 /// Break a copy of size Size to smaller copies. 109 void buildCopies(int Size, MachineInstr *LoadInst, int64_t LdDispImm, 110 MachineInstr *StoreInst, int64_t StDispImm, 111 int64_t LMMOffset, int64_t SMMOffset); 112 113 void buildCopy(MachineInstr *LoadInst, unsigned NLoadOpcode, int64_t LoadDisp, 114 MachineInstr *StoreInst, unsigned NStoreOpcode, 115 int64_t StoreDisp, unsigned Size, int64_t LMMOffset, 116 int64_t SMMOffset); 117 118 bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2) const; 119 120 unsigned getRegSizeInBytes(MachineInstr *Inst); 121 }; 122 123 } // end anonymous namespace 124 125 char X86AvoidSFBPass::ID = 0; 126 127 INITIALIZE_PASS_BEGIN(X86AvoidSFBPass, DEBUG_TYPE, "Machine code sinking", 128 false, false) 129 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 130 INITIALIZE_PASS_END(X86AvoidSFBPass, DEBUG_TYPE, "Machine code sinking", false, 131 false) 132 133 FunctionPass *llvm::createX86AvoidStoreForwardingBlocks() { 134 return new X86AvoidSFBPass(); 135 } 136 137 static bool isXMMLoadOpcode(unsigned Opcode) { 138 return Opcode == X86::MOVUPSrm || Opcode == X86::MOVAPSrm || 139 Opcode == X86::VMOVUPSrm || Opcode == X86::VMOVAPSrm || 140 Opcode == X86::VMOVUPDrm || Opcode == X86::VMOVAPDrm || 141 Opcode == X86::VMOVDQUrm || Opcode == X86::VMOVDQArm || 142 Opcode == X86::VMOVUPSZ128rm || Opcode == X86::VMOVAPSZ128rm || 143 Opcode == X86::VMOVUPDZ128rm || Opcode == X86::VMOVAPDZ128rm || 144 Opcode == X86::VMOVDQU64Z128rm || Opcode == X86::VMOVDQA64Z128rm || 145 Opcode == X86::VMOVDQU32Z128rm || Opcode == X86::VMOVDQA32Z128rm; 146 } 147 static bool isYMMLoadOpcode(unsigned Opcode) { 148 return Opcode == X86::VMOVUPSYrm || Opcode == X86::VMOVAPSYrm || 149 Opcode == X86::VMOVUPDYrm || Opcode == X86::VMOVAPDYrm || 150 Opcode == X86::VMOVDQUYrm || Opcode == X86::VMOVDQAYrm || 151 Opcode == X86::VMOVUPSZ256rm || Opcode == X86::VMOVAPSZ256rm || 152 Opcode == X86::VMOVUPDZ256rm || Opcode == X86::VMOVAPDZ256rm || 153 Opcode == X86::VMOVDQU64Z256rm || Opcode == X86::VMOVDQA64Z256rm || 154 Opcode == X86::VMOVDQU32Z256rm || Opcode == X86::VMOVDQA32Z256rm; 155 } 156 157 static bool isPotentialBlockedMemCpyLd(unsigned Opcode) { 158 return isXMMLoadOpcode(Opcode) || isYMMLoadOpcode(Opcode); 159 } 160 161 static bool isPotentialBlockedMemCpyPair(int LdOpcode, int StOpcode) { 162 switch (LdOpcode) { 163 case X86::MOVUPSrm: 164 case X86::MOVAPSrm: 165 return StOpcode == X86::MOVUPSmr || StOpcode == X86::MOVAPSmr; 166 case X86::VMOVUPSrm: 167 case X86::VMOVAPSrm: 168 return StOpcode == X86::VMOVUPSmr || StOpcode == X86::VMOVAPSmr; 169 case X86::VMOVUPDrm: 170 case X86::VMOVAPDrm: 171 return StOpcode == X86::VMOVUPDmr || StOpcode == X86::VMOVAPDmr; 172 case X86::VMOVDQUrm: 173 case X86::VMOVDQArm: 174 return StOpcode == X86::VMOVDQUmr || StOpcode == X86::VMOVDQAmr; 175 case X86::VMOVUPSZ128rm: 176 case X86::VMOVAPSZ128rm: 177 return StOpcode == X86::VMOVUPSZ128mr || StOpcode == X86::VMOVAPSZ128mr; 178 case X86::VMOVUPDZ128rm: 179 case X86::VMOVAPDZ128rm: 180 return StOpcode == X86::VMOVUPDZ128mr || StOpcode == X86::VMOVAPDZ128mr; 181 case X86::VMOVUPSYrm: 182 case X86::VMOVAPSYrm: 183 return StOpcode == X86::VMOVUPSYmr || StOpcode == X86::VMOVAPSYmr; 184 case X86::VMOVUPDYrm: 185 case X86::VMOVAPDYrm: 186 return StOpcode == X86::VMOVUPDYmr || StOpcode == X86::VMOVAPDYmr; 187 case X86::VMOVDQUYrm: 188 case X86::VMOVDQAYrm: 189 return StOpcode == X86::VMOVDQUYmr || StOpcode == X86::VMOVDQAYmr; 190 case X86::VMOVUPSZ256rm: 191 case X86::VMOVAPSZ256rm: 192 return StOpcode == X86::VMOVUPSZ256mr || StOpcode == X86::VMOVAPSZ256mr; 193 case X86::VMOVUPDZ256rm: 194 case X86::VMOVAPDZ256rm: 195 return StOpcode == X86::VMOVUPDZ256mr || StOpcode == X86::VMOVAPDZ256mr; 196 case X86::VMOVDQU64Z128rm: 197 case X86::VMOVDQA64Z128rm: 198 return StOpcode == X86::VMOVDQU64Z128mr || StOpcode == X86::VMOVDQA64Z128mr; 199 case X86::VMOVDQU32Z128rm: 200 case X86::VMOVDQA32Z128rm: 201 return StOpcode == X86::VMOVDQU32Z128mr || StOpcode == X86::VMOVDQA32Z128mr; 202 case X86::VMOVDQU64Z256rm: 203 case X86::VMOVDQA64Z256rm: 204 return StOpcode == X86::VMOVDQU64Z256mr || StOpcode == X86::VMOVDQA64Z256mr; 205 case X86::VMOVDQU32Z256rm: 206 case X86::VMOVDQA32Z256rm: 207 return StOpcode == X86::VMOVDQU32Z256mr || StOpcode == X86::VMOVDQA32Z256mr; 208 default: 209 return false; 210 } 211 } 212 213 static bool isPotentialBlockingStoreInst(int Opcode, int LoadOpcode) { 214 bool PBlock = false; 215 PBlock |= Opcode == X86::MOV64mr || Opcode == X86::MOV64mi32 || 216 Opcode == X86::MOV32mr || Opcode == X86::MOV32mi || 217 Opcode == X86::MOV16mr || Opcode == X86::MOV16mi || 218 Opcode == X86::MOV8mr || Opcode == X86::MOV8mi; 219 if (isYMMLoadOpcode(LoadOpcode)) 220 PBlock |= Opcode == X86::VMOVUPSmr || Opcode == X86::VMOVAPSmr || 221 Opcode == X86::VMOVUPDmr || Opcode == X86::VMOVAPDmr || 222 Opcode == X86::VMOVDQUmr || Opcode == X86::VMOVDQAmr || 223 Opcode == X86::VMOVUPSZ128mr || Opcode == X86::VMOVAPSZ128mr || 224 Opcode == X86::VMOVUPDZ128mr || Opcode == X86::VMOVAPDZ128mr || 225 Opcode == X86::VMOVDQU64Z128mr || 226 Opcode == X86::VMOVDQA64Z128mr || 227 Opcode == X86::VMOVDQU32Z128mr || Opcode == X86::VMOVDQA32Z128mr; 228 return PBlock; 229 } 230 231 static const int MOV128SZ = 16; 232 static const int MOV64SZ = 8; 233 static const int MOV32SZ = 4; 234 static const int MOV16SZ = 2; 235 static const int MOV8SZ = 1; 236 237 static unsigned getYMMtoXMMLoadOpcode(unsigned LoadOpcode) { 238 switch (LoadOpcode) { 239 case X86::VMOVUPSYrm: 240 case X86::VMOVAPSYrm: 241 return X86::VMOVUPSrm; 242 case X86::VMOVUPDYrm: 243 case X86::VMOVAPDYrm: 244 return X86::VMOVUPDrm; 245 case X86::VMOVDQUYrm: 246 case X86::VMOVDQAYrm: 247 return X86::VMOVDQUrm; 248 case X86::VMOVUPSZ256rm: 249 case X86::VMOVAPSZ256rm: 250 return X86::VMOVUPSZ128rm; 251 case X86::VMOVUPDZ256rm: 252 case X86::VMOVAPDZ256rm: 253 return X86::VMOVUPDZ128rm; 254 case X86::VMOVDQU64Z256rm: 255 case X86::VMOVDQA64Z256rm: 256 return X86::VMOVDQU64Z128rm; 257 case X86::VMOVDQU32Z256rm: 258 case X86::VMOVDQA32Z256rm: 259 return X86::VMOVDQU32Z128rm; 260 default: 261 llvm_unreachable("Unexpected Load Instruction Opcode"); 262 } 263 return 0; 264 } 265 266 static unsigned getYMMtoXMMStoreOpcode(unsigned StoreOpcode) { 267 switch (StoreOpcode) { 268 case X86::VMOVUPSYmr: 269 case X86::VMOVAPSYmr: 270 return X86::VMOVUPSmr; 271 case X86::VMOVUPDYmr: 272 case X86::VMOVAPDYmr: 273 return X86::VMOVUPDmr; 274 case X86::VMOVDQUYmr: 275 case X86::VMOVDQAYmr: 276 return X86::VMOVDQUmr; 277 case X86::VMOVUPSZ256mr: 278 case X86::VMOVAPSZ256mr: 279 return X86::VMOVUPSZ128mr; 280 case X86::VMOVUPDZ256mr: 281 case X86::VMOVAPDZ256mr: 282 return X86::VMOVUPDZ128mr; 283 case X86::VMOVDQU64Z256mr: 284 case X86::VMOVDQA64Z256mr: 285 return X86::VMOVDQU64Z128mr; 286 case X86::VMOVDQU32Z256mr: 287 case X86::VMOVDQA32Z256mr: 288 return X86::VMOVDQU32Z128mr; 289 default: 290 llvm_unreachable("Unexpected Load Instruction Opcode"); 291 } 292 return 0; 293 } 294 295 static int getAddrOffset(MachineInstr *MI) { 296 const MCInstrDesc &Descl = MI->getDesc(); 297 int AddrOffset = X86II::getMemoryOperandNo(Descl.TSFlags); 298 assert(AddrOffset != -1 && "Expected Memory Operand"); 299 AddrOffset += X86II::getOperandBias(Descl); 300 return AddrOffset; 301 } 302 303 static MachineOperand &getBaseOperand(MachineInstr *MI) { 304 int AddrOffset = getAddrOffset(MI); 305 return MI->getOperand(AddrOffset + X86::AddrBaseReg); 306 } 307 308 static MachineOperand &getDispOperand(MachineInstr *MI) { 309 int AddrOffset = getAddrOffset(MI); 310 return MI->getOperand(AddrOffset + X86::AddrDisp); 311 } 312 313 // Relevant addressing modes contain only base register and immediate 314 // displacement or frameindex and immediate displacement. 315 // TODO: Consider expanding to other addressing modes in the future 316 static bool isRelevantAddressingMode(MachineInstr *MI) { 317 int AddrOffset = getAddrOffset(MI); 318 MachineOperand &Base = getBaseOperand(MI); 319 MachineOperand &Disp = getDispOperand(MI); 320 MachineOperand &Scale = MI->getOperand(AddrOffset + X86::AddrScaleAmt); 321 MachineOperand &Index = MI->getOperand(AddrOffset + X86::AddrIndexReg); 322 MachineOperand &Segment = MI->getOperand(AddrOffset + X86::AddrSegmentReg); 323 324 if (!((Base.isReg() && Base.getReg() != X86::NoRegister) || Base.isFI())) 325 return false; 326 if (!Disp.isImm()) 327 return false; 328 if (Scale.getImm() != 1) 329 return false; 330 if (!(Index.isReg() && Index.getReg() == X86::NoRegister)) 331 return false; 332 if (!(Segment.isReg() && Segment.getReg() == X86::NoRegister)) 333 return false; 334 return true; 335 } 336 337 // Collect potentially blocking stores. 338 // Limit the number of instructions backwards we want to inspect 339 // since the effect of store block won't be visible if the store 340 // and load instructions have enough instructions in between to 341 // keep the core busy. 342 static SmallVector<MachineInstr *, 2> 343 findPotentialBlockers(MachineInstr *LoadInst) { 344 SmallVector<MachineInstr *, 2> PotentialBlockers; 345 unsigned BlockCount = 0; 346 const unsigned InspectionLimit = X86AvoidSFBInspectionLimit; 347 for (auto PBInst = std::next(MachineBasicBlock::reverse_iterator(LoadInst)), 348 E = LoadInst->getParent()->rend(); 349 PBInst != E; ++PBInst) { 350 BlockCount++; 351 if (BlockCount >= InspectionLimit) 352 break; 353 MachineInstr &MI = *PBInst; 354 if (MI.getDesc().isCall()) 355 return PotentialBlockers; 356 PotentialBlockers.push_back(&MI); 357 } 358 // If we didn't get to the instructions limit try predecessing blocks. 359 // Ideally we should traverse the predecessor blocks in depth with some 360 // coloring algorithm, but for now let's just look at the first order 361 // predecessors. 362 if (BlockCount < InspectionLimit) { 363 MachineBasicBlock *MBB = LoadInst->getParent(); 364 int LimitLeft = InspectionLimit - BlockCount; 365 for (MachineBasicBlock::pred_iterator PB = MBB->pred_begin(), 366 PE = MBB->pred_end(); 367 PB != PE; ++PB) { 368 MachineBasicBlock *PMBB = *PB; 369 int PredCount = 0; 370 for (MachineBasicBlock::reverse_iterator PBInst = PMBB->rbegin(), 371 PME = PMBB->rend(); 372 PBInst != PME; ++PBInst) { 373 PredCount++; 374 if (PredCount >= LimitLeft) 375 break; 376 if (PBInst->getDesc().isCall()) 377 break; 378 PotentialBlockers.push_back(&*PBInst); 379 } 380 } 381 } 382 return PotentialBlockers; 383 } 384 385 void X86AvoidSFBPass::buildCopy(MachineInstr *LoadInst, unsigned NLoadOpcode, 386 int64_t LoadDisp, MachineInstr *StoreInst, 387 unsigned NStoreOpcode, int64_t StoreDisp, 388 unsigned Size, int64_t LMMOffset, 389 int64_t SMMOffset) { 390 MachineOperand &LoadBase = getBaseOperand(LoadInst); 391 MachineOperand &StoreBase = getBaseOperand(StoreInst); 392 MachineBasicBlock *MBB = LoadInst->getParent(); 393 MachineMemOperand *LMMO = *LoadInst->memoperands_begin(); 394 MachineMemOperand *SMMO = *StoreInst->memoperands_begin(); 395 396 unsigned Reg1 = MRI->createVirtualRegister( 397 TII->getRegClass(TII->get(NLoadOpcode), 0, TRI, *(MBB->getParent()))); 398 MachineInstr *NewLoad = 399 BuildMI(*MBB, LoadInst, LoadInst->getDebugLoc(), TII->get(NLoadOpcode), 400 Reg1) 401 .add(LoadBase) 402 .addImm(1) 403 .addReg(X86::NoRegister) 404 .addImm(LoadDisp) 405 .addReg(X86::NoRegister) 406 .addMemOperand( 407 MBB->getParent()->getMachineMemOperand(LMMO, LMMOffset, Size)); 408 if (LoadBase.isReg()) 409 getBaseOperand(NewLoad).setIsKill(false); 410 LLVM_DEBUG(NewLoad->dump()); 411 // If the load and store are consecutive, use the loadInst location to 412 // reduce register pressure. 413 MachineInstr *StInst = StoreInst; 414 if (StoreInst->getPrevNode() == LoadInst) 415 StInst = LoadInst; 416 MachineInstr *NewStore = 417 BuildMI(*MBB, StInst, StInst->getDebugLoc(), TII->get(NStoreOpcode)) 418 .add(StoreBase) 419 .addImm(1) 420 .addReg(X86::NoRegister) 421 .addImm(StoreDisp) 422 .addReg(X86::NoRegister) 423 .addReg(Reg1) 424 .addMemOperand( 425 MBB->getParent()->getMachineMemOperand(SMMO, SMMOffset, Size)); 426 if (StoreBase.isReg()) 427 getBaseOperand(NewStore).setIsKill(false); 428 MachineOperand &StoreSrcVReg = StoreInst->getOperand(X86::AddrNumOperands); 429 assert(StoreSrcVReg.isReg() && "Expected virtual register"); 430 NewStore->getOperand(X86::AddrNumOperands).setIsKill(StoreSrcVReg.isKill()); 431 LLVM_DEBUG(NewStore->dump()); 432 } 433 434 void X86AvoidSFBPass::buildCopies(int Size, MachineInstr *LoadInst, 435 int64_t LdDispImm, MachineInstr *StoreInst, 436 int64_t StDispImm, int64_t LMMOffset, 437 int64_t SMMOffset) { 438 int LdDisp = LdDispImm; 439 int StDisp = StDispImm; 440 while (Size > 0) { 441 if ((Size - MOV128SZ >= 0) && isYMMLoadOpcode(LoadInst->getOpcode())) { 442 Size = Size - MOV128SZ; 443 buildCopy(LoadInst, getYMMtoXMMLoadOpcode(LoadInst->getOpcode()), LdDisp, 444 StoreInst, getYMMtoXMMStoreOpcode(StoreInst->getOpcode()), 445 StDisp, MOV128SZ, LMMOffset, SMMOffset); 446 LdDisp += MOV128SZ; 447 StDisp += MOV128SZ; 448 LMMOffset += MOV128SZ; 449 SMMOffset += MOV128SZ; 450 continue; 451 } 452 if (Size - MOV64SZ >= 0) { 453 Size = Size - MOV64SZ; 454 buildCopy(LoadInst, X86::MOV64rm, LdDisp, StoreInst, X86::MOV64mr, StDisp, 455 MOV64SZ, LMMOffset, SMMOffset); 456 LdDisp += MOV64SZ; 457 StDisp += MOV64SZ; 458 LMMOffset += MOV64SZ; 459 SMMOffset += MOV64SZ; 460 continue; 461 } 462 if (Size - MOV32SZ >= 0) { 463 Size = Size - MOV32SZ; 464 buildCopy(LoadInst, X86::MOV32rm, LdDisp, StoreInst, X86::MOV32mr, StDisp, 465 MOV32SZ, LMMOffset, SMMOffset); 466 LdDisp += MOV32SZ; 467 StDisp += MOV32SZ; 468 LMMOffset += MOV32SZ; 469 SMMOffset += MOV32SZ; 470 continue; 471 } 472 if (Size - MOV16SZ >= 0) { 473 Size = Size - MOV16SZ; 474 buildCopy(LoadInst, X86::MOV16rm, LdDisp, StoreInst, X86::MOV16mr, StDisp, 475 MOV16SZ, LMMOffset, SMMOffset); 476 LdDisp += MOV16SZ; 477 StDisp += MOV16SZ; 478 LMMOffset += MOV16SZ; 479 SMMOffset += MOV16SZ; 480 continue; 481 } 482 if (Size - MOV8SZ >= 0) { 483 Size = Size - MOV8SZ; 484 buildCopy(LoadInst, X86::MOV8rm, LdDisp, StoreInst, X86::MOV8mr, StDisp, 485 MOV8SZ, LMMOffset, SMMOffset); 486 LdDisp += MOV8SZ; 487 StDisp += MOV8SZ; 488 LMMOffset += MOV8SZ; 489 SMMOffset += MOV8SZ; 490 continue; 491 } 492 } 493 assert(Size == 0 && "Wrong size division"); 494 } 495 496 static void updateKillStatus(MachineInstr *LoadInst, MachineInstr *StoreInst) { 497 MachineOperand &LoadBase = getBaseOperand(LoadInst); 498 MachineOperand &StoreBase = getBaseOperand(StoreInst); 499 if (LoadBase.isReg()) { 500 MachineInstr *LastLoad = LoadInst->getPrevNode(); 501 // If the original load and store to xmm/ymm were consecutive 502 // then the partial copies were also created in 503 // a consecutive order to reduce register pressure, 504 // and the location of the last load is before the last store. 505 if (StoreInst->getPrevNode() == LoadInst) 506 LastLoad = LoadInst->getPrevNode()->getPrevNode(); 507 getBaseOperand(LastLoad).setIsKill(LoadBase.isKill()); 508 } 509 if (StoreBase.isReg()) { 510 MachineInstr *StInst = StoreInst; 511 if (StoreInst->getPrevNode() == LoadInst) 512 StInst = LoadInst; 513 getBaseOperand(StInst->getPrevNode()).setIsKill(StoreBase.isKill()); 514 } 515 } 516 517 bool X86AvoidSFBPass::alias(const MachineMemOperand &Op1, 518 const MachineMemOperand &Op2) const { 519 if (!Op1.getValue() || !Op2.getValue()) 520 return true; 521 522 int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset()); 523 int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset; 524 int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset; 525 526 AliasResult AAResult = 527 AA->alias(MemoryLocation(Op1.getValue(), Overlapa, Op1.getAAInfo()), 528 MemoryLocation(Op2.getValue(), Overlapb, Op2.getAAInfo())); 529 return AAResult != NoAlias; 530 } 531 532 void X86AvoidSFBPass::findPotentiallylBlockedCopies(MachineFunction &MF) { 533 for (auto &MBB : MF) 534 for (auto &MI : MBB) { 535 if (!isPotentialBlockedMemCpyLd(MI.getOpcode())) 536 continue; 537 int DefVR = MI.getOperand(0).getReg(); 538 if (!MRI->hasOneUse(DefVR)) 539 continue; 540 for (auto UI = MRI->use_nodbg_begin(DefVR), UE = MRI->use_nodbg_end(); 541 UI != UE;) { 542 MachineOperand &StoreMO = *UI++; 543 MachineInstr &StoreMI = *StoreMO.getParent(); 544 // Skip cases where the memcpy may overlap. 545 if (StoreMI.getParent() == MI.getParent() && 546 isPotentialBlockedMemCpyPair(MI.getOpcode(), StoreMI.getOpcode()) && 547 isRelevantAddressingMode(&MI) && 548 isRelevantAddressingMode(&StoreMI)) { 549 assert(MI.hasOneMemOperand() && 550 "Expected one memory operand for load instruction"); 551 assert(StoreMI.hasOneMemOperand() && 552 "Expected one memory operand for store instruction"); 553 if (!alias(**MI.memoperands_begin(), **StoreMI.memoperands_begin())) 554 BlockedLoadsStoresPairs.push_back(std::make_pair(&MI, &StoreMI)); 555 } 556 } 557 } 558 } 559 560 unsigned X86AvoidSFBPass::getRegSizeInBytes(MachineInstr *LoadInst) { 561 auto TRC = TII->getRegClass(TII->get(LoadInst->getOpcode()), 0, TRI, 562 *LoadInst->getParent()->getParent()); 563 return TRI->getRegSizeInBits(*TRC) / 8; 564 } 565 566 void X86AvoidSFBPass::breakBlockedCopies( 567 MachineInstr *LoadInst, MachineInstr *StoreInst, 568 const DisplacementSizeMap &BlockingStoresDispSizeMap) { 569 int64_t LdDispImm = getDispOperand(LoadInst).getImm(); 570 int64_t StDispImm = getDispOperand(StoreInst).getImm(); 571 int64_t LMMOffset = 0; 572 int64_t SMMOffset = 0; 573 574 int64_t LdDisp1 = LdDispImm; 575 int64_t LdDisp2 = 0; 576 int64_t StDisp1 = StDispImm; 577 int64_t StDisp2 = 0; 578 unsigned Size1 = 0; 579 unsigned Size2 = 0; 580 int64_t LdStDelta = StDispImm - LdDispImm; 581 582 for (auto DispSizePair : BlockingStoresDispSizeMap) { 583 LdDisp2 = DispSizePair.first; 584 StDisp2 = DispSizePair.first + LdStDelta; 585 Size2 = DispSizePair.second; 586 // Avoid copying overlapping areas. 587 if (LdDisp2 < LdDisp1) { 588 int OverlapDelta = LdDisp1 - LdDisp2; 589 LdDisp2 += OverlapDelta; 590 StDisp2 += OverlapDelta; 591 Size2 -= OverlapDelta; 592 } 593 Size1 = std::abs(std::abs(LdDisp2) - std::abs(LdDisp1)); 594 595 // Build a copy for the point until the current blocking store's 596 // displacement. 597 buildCopies(Size1, LoadInst, LdDisp1, StoreInst, StDisp1, LMMOffset, 598 SMMOffset); 599 // Build a copy for the current blocking store. 600 buildCopies(Size2, LoadInst, LdDisp2, StoreInst, StDisp2, LMMOffset + Size1, 601 SMMOffset + Size1); 602 LdDisp1 = LdDisp2 + Size2; 603 StDisp1 = StDisp2 + Size2; 604 LMMOffset += Size1 + Size2; 605 SMMOffset += Size1 + Size2; 606 } 607 unsigned Size3 = (LdDispImm + getRegSizeInBytes(LoadInst)) - LdDisp1; 608 buildCopies(Size3, LoadInst, LdDisp1, StoreInst, StDisp1, LMMOffset, 609 LMMOffset); 610 } 611 612 static bool hasSameBaseOpValue(MachineInstr *LoadInst, 613 MachineInstr *StoreInst) { 614 MachineOperand &LoadBase = getBaseOperand(LoadInst); 615 MachineOperand &StoreBase = getBaseOperand(StoreInst); 616 if (LoadBase.isReg() != StoreBase.isReg()) 617 return false; 618 if (LoadBase.isReg()) 619 return LoadBase.getReg() == StoreBase.getReg(); 620 return LoadBase.getIndex() == StoreBase.getIndex(); 621 } 622 623 static bool isBlockingStore(int64_t LoadDispImm, unsigned LoadSize, 624 int64_t StoreDispImm, unsigned StoreSize) { 625 return ((StoreDispImm >= LoadDispImm) && 626 (StoreDispImm <= LoadDispImm + (LoadSize - StoreSize))); 627 } 628 629 // Keep track of all stores blocking a load 630 static void 631 updateBlockingStoresDispSizeMap(DisplacementSizeMap &BlockingStoresDispSizeMap, 632 int64_t DispImm, unsigned Size) { 633 if (BlockingStoresDispSizeMap.count(DispImm)) { 634 // Choose the smallest blocking store starting at this displacement. 635 if (BlockingStoresDispSizeMap[DispImm] > Size) 636 BlockingStoresDispSizeMap[DispImm] = Size; 637 638 } else 639 BlockingStoresDispSizeMap[DispImm] = Size; 640 } 641 642 // Remove blocking stores contained in each other. 643 static void 644 removeRedundantBlockingStores(DisplacementSizeMap &BlockingStoresDispSizeMap) { 645 if (BlockingStoresDispSizeMap.size() <= 1) 646 return; 647 648 int64_t PrevDisp = BlockingStoresDispSizeMap.begin()->first; 649 unsigned PrevSize = BlockingStoresDispSizeMap.begin()->second; 650 SmallVector<int64_t, 2> ForRemoval; 651 for (auto DispSizePair = std::next(BlockingStoresDispSizeMap.begin()); 652 DispSizePair != BlockingStoresDispSizeMap.end(); ++DispSizePair) { 653 int64_t CurrDisp = DispSizePair->first; 654 unsigned CurrSize = DispSizePair->second; 655 if (CurrDisp + CurrSize <= PrevDisp + PrevSize) { 656 ForRemoval.push_back(PrevDisp); 657 } 658 PrevDisp = CurrDisp; 659 PrevSize = CurrSize; 660 } 661 for (auto Disp : ForRemoval) 662 BlockingStoresDispSizeMap.erase(Disp); 663 } 664 665 bool X86AvoidSFBPass::runOnMachineFunction(MachineFunction &MF) { 666 bool Changed = false; 667 668 if (DisableX86AvoidStoreForwardBlocks || skipFunction(MF.getFunction()) || 669 !MF.getSubtarget<X86Subtarget>().is64Bit()) 670 return false; 671 672 MRI = &MF.getRegInfo(); 673 assert(MRI->isSSA() && "Expected MIR to be in SSA form"); 674 TII = MF.getSubtarget<X86Subtarget>().getInstrInfo(); 675 TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo(); 676 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 677 LLVM_DEBUG(dbgs() << "Start X86AvoidStoreForwardBlocks\n";); 678 // Look for a load then a store to XMM/YMM which look like a memcpy 679 findPotentiallylBlockedCopies(MF); 680 681 for (auto LoadStoreInstPair : BlockedLoadsStoresPairs) { 682 MachineInstr *LoadInst = LoadStoreInstPair.first; 683 int64_t LdDispImm = getDispOperand(LoadInst).getImm(); 684 DisplacementSizeMap BlockingStoresDispSizeMap; 685 686 SmallVector<MachineInstr *, 2> PotentialBlockers = 687 findPotentialBlockers(LoadInst); 688 for (auto PBInst : PotentialBlockers) { 689 if (!isPotentialBlockingStoreInst(PBInst->getOpcode(), 690 LoadInst->getOpcode()) || 691 !isRelevantAddressingMode(PBInst)) 692 continue; 693 int64_t PBstDispImm = getDispOperand(PBInst).getImm(); 694 assert(PBInst->hasOneMemOperand() && "Expected One Memory Operand"); 695 unsigned PBstSize = (*PBInst->memoperands_begin())->getSize(); 696 // This check doesn't cover all cases, but it will suffice for now. 697 // TODO: take branch probability into consideration, if the blocking 698 // store is in an unreached block, breaking the memcopy could lose 699 // performance. 700 if (hasSameBaseOpValue(LoadInst, PBInst) && 701 isBlockingStore(LdDispImm, getRegSizeInBytes(LoadInst), PBstDispImm, 702 PBstSize)) 703 updateBlockingStoresDispSizeMap(BlockingStoresDispSizeMap, PBstDispImm, 704 PBstSize); 705 } 706 707 if (BlockingStoresDispSizeMap.empty()) 708 continue; 709 710 // We found a store forward block, break the memcpy's load and store 711 // into smaller copies such that each smaller store that was causing 712 // a store block would now be copied separately. 713 MachineInstr *StoreInst = LoadStoreInstPair.second; 714 LLVM_DEBUG(dbgs() << "Blocked load and store instructions: \n"); 715 LLVM_DEBUG(LoadInst->dump()); 716 LLVM_DEBUG(StoreInst->dump()); 717 LLVM_DEBUG(dbgs() << "Replaced with:\n"); 718 removeRedundantBlockingStores(BlockingStoresDispSizeMap); 719 breakBlockedCopies(LoadInst, StoreInst, BlockingStoresDispSizeMap); 720 updateKillStatus(LoadInst, StoreInst); 721 ForRemoval.push_back(LoadInst); 722 ForRemoval.push_back(StoreInst); 723 } 724 for (auto RemovedInst : ForRemoval) { 725 RemovedInst->eraseFromParent(); 726 } 727 ForRemoval.clear(); 728 BlockedLoadsStoresPairs.clear(); 729 LLVM_DEBUG(dbgs() << "End X86AvoidStoreForwardBlocks\n";); 730 731 return Changed; 732 } 733