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