1336809Sdim//===- X86AvoidStoreForwardingBlockis.cpp - Avoid HW Store Forward Block --===// 2336809Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6336809Sdim// 7336809Sdim//===----------------------------------------------------------------------===// 8336809Sdim// 9336809Sdim// If a load follows a store and reloads data that the store has written to 10336809Sdim// memory, Intel microarchitectures can in many cases forward the data directly 11336809Sdim// from the store to the load, This "store forwarding" saves cycles by enabling 12336809Sdim// the load to directly obtain the data instead of accessing the data from 13336809Sdim// cache or memory. 14336809Sdim// A "store forward block" occurs in cases that a store cannot be forwarded to 15336809Sdim// the load. The most typical case of store forward block on Intel Core 16336809Sdim// microarchitecture that a small store cannot be forwarded to a large load. 17336809Sdim// The estimated penalty for a store forward block is ~13 cycles. 18336809Sdim// 19336809Sdim// This pass tries to recognize and handle cases where "store forward block" 20336809Sdim// is created by the compiler when lowering memcpy calls to a sequence 21336809Sdim// of a load and a store. 22336809Sdim// 23336809Sdim// The pass currently only handles cases where memcpy is lowered to 24336809Sdim// XMM/YMM registers, it tries to break the memcpy into smaller copies. 25336809Sdim// breaking the memcpy should be possible since there is no atomicity 26336809Sdim// guarantee for loads and stores to XMM/YMM. 27336809Sdim// 28336809Sdim// It could be better for performance to solve the problem by loading 29336809Sdim// to XMM/YMM then inserting the partial store before storing back from XMM/YMM 30336809Sdim// to memory, but this will result in a more conservative optimization since it 31336809Sdim// requires we prove that all memory accesses between the blocking store and the 32336809Sdim// load must alias/don't alias before we can move the store, whereas the 33336809Sdim// transformation done here is correct regardless to other memory accesses. 34336809Sdim//===----------------------------------------------------------------------===// 35336809Sdim 36336809Sdim#include "X86InstrInfo.h" 37336809Sdim#include "X86Subtarget.h" 38360784Sdim#include "llvm/Analysis/AliasAnalysis.h" 39336809Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 40336809Sdim#include "llvm/CodeGen/MachineFunction.h" 41336809Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 42336809Sdim#include "llvm/CodeGen/MachineInstr.h" 43336809Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 44336809Sdim#include "llvm/CodeGen/MachineOperand.h" 45336809Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 46336809Sdim#include "llvm/IR/DebugInfoMetadata.h" 47336809Sdim#include "llvm/IR/DebugLoc.h" 48336809Sdim#include "llvm/IR/Function.h" 49360784Sdim#include "llvm/InitializePasses.h" 50336809Sdim#include "llvm/MC/MCInstrDesc.h" 51336809Sdim 52336809Sdimusing namespace llvm; 53336809Sdim 54336809Sdim#define DEBUG_TYPE "x86-avoid-SFB" 55336809Sdim 56336809Sdimstatic cl::opt<bool> DisableX86AvoidStoreForwardBlocks( 57336809Sdim "x86-disable-avoid-SFB", cl::Hidden, 58336809Sdim cl::desc("X86: Disable Store Forwarding Blocks fixup."), cl::init(false)); 59336809Sdim 60336809Sdimstatic cl::opt<unsigned> X86AvoidSFBInspectionLimit( 61336809Sdim "x86-sfb-inspection-limit", 62336809Sdim cl::desc("X86: Number of instructions backward to " 63336809Sdim "inspect for store forwarding blocks."), 64336809Sdim cl::init(20), cl::Hidden); 65336809Sdim 66336809Sdimnamespace { 67336809Sdim 68336809Sdimusing DisplacementSizeMap = std::map<int64_t, unsigned>; 69336809Sdim 70336809Sdimclass X86AvoidSFBPass : public MachineFunctionPass { 71336809Sdimpublic: 72336809Sdim static char ID; 73353358Sdim X86AvoidSFBPass() : MachineFunctionPass(ID) { } 74336809Sdim 75336809Sdim StringRef getPassName() const override { 76336809Sdim return "X86 Avoid Store Forwarding Blocks"; 77336809Sdim } 78336809Sdim 79336809Sdim bool runOnMachineFunction(MachineFunction &MF) override; 80336809Sdim 81336809Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 82336809Sdim MachineFunctionPass::getAnalysisUsage(AU); 83336809Sdim AU.addRequired<AAResultsWrapperPass>(); 84336809Sdim } 85336809Sdim 86336809Sdimprivate: 87360784Sdim MachineRegisterInfo *MRI = nullptr; 88360784Sdim const X86InstrInfo *TII = nullptr; 89360784Sdim const X86RegisterInfo *TRI = nullptr; 90336809Sdim SmallVector<std::pair<MachineInstr *, MachineInstr *>, 2> 91336809Sdim BlockedLoadsStoresPairs; 92336809Sdim SmallVector<MachineInstr *, 2> ForRemoval; 93360784Sdim AliasAnalysis *AA = nullptr; 94336809Sdim 95336809Sdim /// Returns couples of Load then Store to memory which look 96336809Sdim /// like a memcpy. 97336809Sdim void findPotentiallylBlockedCopies(MachineFunction &MF); 98336809Sdim /// Break the memcpy's load and store into smaller copies 99336809Sdim /// such that each memory load that was blocked by a smaller store 100336809Sdim /// would now be copied separately. 101336809Sdim void breakBlockedCopies(MachineInstr *LoadInst, MachineInstr *StoreInst, 102336809Sdim const DisplacementSizeMap &BlockingStoresDispSizeMap); 103336809Sdim /// Break a copy of size Size to smaller copies. 104336809Sdim void buildCopies(int Size, MachineInstr *LoadInst, int64_t LdDispImm, 105336809Sdim MachineInstr *StoreInst, int64_t StDispImm, 106336809Sdim int64_t LMMOffset, int64_t SMMOffset); 107336809Sdim 108336809Sdim void buildCopy(MachineInstr *LoadInst, unsigned NLoadOpcode, int64_t LoadDisp, 109336809Sdim MachineInstr *StoreInst, unsigned NStoreOpcode, 110336809Sdim int64_t StoreDisp, unsigned Size, int64_t LMMOffset, 111336809Sdim int64_t SMMOffset); 112336809Sdim 113336809Sdim bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2) const; 114336809Sdim 115336809Sdim unsigned getRegSizeInBytes(MachineInstr *Inst); 116336809Sdim}; 117336809Sdim 118336809Sdim} // end anonymous namespace 119336809Sdim 120336809Sdimchar X86AvoidSFBPass::ID = 0; 121336809Sdim 122336809SdimINITIALIZE_PASS_BEGIN(X86AvoidSFBPass, DEBUG_TYPE, "Machine code sinking", 123336809Sdim false, false) 124336809SdimINITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 125336809SdimINITIALIZE_PASS_END(X86AvoidSFBPass, DEBUG_TYPE, "Machine code sinking", false, 126336809Sdim false) 127336809Sdim 128336809SdimFunctionPass *llvm::createX86AvoidStoreForwardingBlocks() { 129336809Sdim return new X86AvoidSFBPass(); 130336809Sdim} 131336809Sdim 132336809Sdimstatic bool isXMMLoadOpcode(unsigned Opcode) { 133336809Sdim return Opcode == X86::MOVUPSrm || Opcode == X86::MOVAPSrm || 134336809Sdim Opcode == X86::VMOVUPSrm || Opcode == X86::VMOVAPSrm || 135336809Sdim Opcode == X86::VMOVUPDrm || Opcode == X86::VMOVAPDrm || 136336809Sdim Opcode == X86::VMOVDQUrm || Opcode == X86::VMOVDQArm || 137336809Sdim Opcode == X86::VMOVUPSZ128rm || Opcode == X86::VMOVAPSZ128rm || 138336809Sdim Opcode == X86::VMOVUPDZ128rm || Opcode == X86::VMOVAPDZ128rm || 139336809Sdim Opcode == X86::VMOVDQU64Z128rm || Opcode == X86::VMOVDQA64Z128rm || 140336809Sdim Opcode == X86::VMOVDQU32Z128rm || Opcode == X86::VMOVDQA32Z128rm; 141336809Sdim} 142336809Sdimstatic bool isYMMLoadOpcode(unsigned Opcode) { 143336809Sdim return Opcode == X86::VMOVUPSYrm || Opcode == X86::VMOVAPSYrm || 144336809Sdim Opcode == X86::VMOVUPDYrm || Opcode == X86::VMOVAPDYrm || 145336809Sdim Opcode == X86::VMOVDQUYrm || Opcode == X86::VMOVDQAYrm || 146336809Sdim Opcode == X86::VMOVUPSZ256rm || Opcode == X86::VMOVAPSZ256rm || 147336809Sdim Opcode == X86::VMOVUPDZ256rm || Opcode == X86::VMOVAPDZ256rm || 148336809Sdim Opcode == X86::VMOVDQU64Z256rm || Opcode == X86::VMOVDQA64Z256rm || 149336809Sdim Opcode == X86::VMOVDQU32Z256rm || Opcode == X86::VMOVDQA32Z256rm; 150336809Sdim} 151336809Sdim 152336809Sdimstatic bool isPotentialBlockedMemCpyLd(unsigned Opcode) { 153336809Sdim return isXMMLoadOpcode(Opcode) || isYMMLoadOpcode(Opcode); 154336809Sdim} 155336809Sdim 156336809Sdimstatic bool isPotentialBlockedMemCpyPair(int LdOpcode, int StOpcode) { 157336809Sdim switch (LdOpcode) { 158336809Sdim case X86::MOVUPSrm: 159336809Sdim case X86::MOVAPSrm: 160336809Sdim return StOpcode == X86::MOVUPSmr || StOpcode == X86::MOVAPSmr; 161336809Sdim case X86::VMOVUPSrm: 162336809Sdim case X86::VMOVAPSrm: 163336809Sdim return StOpcode == X86::VMOVUPSmr || StOpcode == X86::VMOVAPSmr; 164336809Sdim case X86::VMOVUPDrm: 165336809Sdim case X86::VMOVAPDrm: 166336809Sdim return StOpcode == X86::VMOVUPDmr || StOpcode == X86::VMOVAPDmr; 167336809Sdim case X86::VMOVDQUrm: 168336809Sdim case X86::VMOVDQArm: 169336809Sdim return StOpcode == X86::VMOVDQUmr || StOpcode == X86::VMOVDQAmr; 170336809Sdim case X86::VMOVUPSZ128rm: 171336809Sdim case X86::VMOVAPSZ128rm: 172336809Sdim return StOpcode == X86::VMOVUPSZ128mr || StOpcode == X86::VMOVAPSZ128mr; 173336809Sdim case X86::VMOVUPDZ128rm: 174336809Sdim case X86::VMOVAPDZ128rm: 175336809Sdim return StOpcode == X86::VMOVUPDZ128mr || StOpcode == X86::VMOVAPDZ128mr; 176336809Sdim case X86::VMOVUPSYrm: 177336809Sdim case X86::VMOVAPSYrm: 178336809Sdim return StOpcode == X86::VMOVUPSYmr || StOpcode == X86::VMOVAPSYmr; 179336809Sdim case X86::VMOVUPDYrm: 180336809Sdim case X86::VMOVAPDYrm: 181336809Sdim return StOpcode == X86::VMOVUPDYmr || StOpcode == X86::VMOVAPDYmr; 182336809Sdim case X86::VMOVDQUYrm: 183336809Sdim case X86::VMOVDQAYrm: 184336809Sdim return StOpcode == X86::VMOVDQUYmr || StOpcode == X86::VMOVDQAYmr; 185336809Sdim case X86::VMOVUPSZ256rm: 186336809Sdim case X86::VMOVAPSZ256rm: 187336809Sdim return StOpcode == X86::VMOVUPSZ256mr || StOpcode == X86::VMOVAPSZ256mr; 188336809Sdim case X86::VMOVUPDZ256rm: 189336809Sdim case X86::VMOVAPDZ256rm: 190336809Sdim return StOpcode == X86::VMOVUPDZ256mr || StOpcode == X86::VMOVAPDZ256mr; 191336809Sdim case X86::VMOVDQU64Z128rm: 192336809Sdim case X86::VMOVDQA64Z128rm: 193336809Sdim return StOpcode == X86::VMOVDQU64Z128mr || StOpcode == X86::VMOVDQA64Z128mr; 194336809Sdim case X86::VMOVDQU32Z128rm: 195336809Sdim case X86::VMOVDQA32Z128rm: 196336809Sdim return StOpcode == X86::VMOVDQU32Z128mr || StOpcode == X86::VMOVDQA32Z128mr; 197336809Sdim case X86::VMOVDQU64Z256rm: 198336809Sdim case X86::VMOVDQA64Z256rm: 199336809Sdim return StOpcode == X86::VMOVDQU64Z256mr || StOpcode == X86::VMOVDQA64Z256mr; 200336809Sdim case X86::VMOVDQU32Z256rm: 201336809Sdim case X86::VMOVDQA32Z256rm: 202336809Sdim return StOpcode == X86::VMOVDQU32Z256mr || StOpcode == X86::VMOVDQA32Z256mr; 203336809Sdim default: 204336809Sdim return false; 205336809Sdim } 206336809Sdim} 207336809Sdim 208336809Sdimstatic bool isPotentialBlockingStoreInst(int Opcode, int LoadOpcode) { 209336809Sdim bool PBlock = false; 210336809Sdim PBlock |= Opcode == X86::MOV64mr || Opcode == X86::MOV64mi32 || 211336809Sdim Opcode == X86::MOV32mr || Opcode == X86::MOV32mi || 212336809Sdim Opcode == X86::MOV16mr || Opcode == X86::MOV16mi || 213336809Sdim Opcode == X86::MOV8mr || Opcode == X86::MOV8mi; 214336809Sdim if (isYMMLoadOpcode(LoadOpcode)) 215336809Sdim PBlock |= Opcode == X86::VMOVUPSmr || Opcode == X86::VMOVAPSmr || 216336809Sdim Opcode == X86::VMOVUPDmr || Opcode == X86::VMOVAPDmr || 217336809Sdim Opcode == X86::VMOVDQUmr || Opcode == X86::VMOVDQAmr || 218336809Sdim Opcode == X86::VMOVUPSZ128mr || Opcode == X86::VMOVAPSZ128mr || 219336809Sdim Opcode == X86::VMOVUPDZ128mr || Opcode == X86::VMOVAPDZ128mr || 220336809Sdim Opcode == X86::VMOVDQU64Z128mr || 221336809Sdim Opcode == X86::VMOVDQA64Z128mr || 222336809Sdim Opcode == X86::VMOVDQU32Z128mr || Opcode == X86::VMOVDQA32Z128mr; 223336809Sdim return PBlock; 224336809Sdim} 225336809Sdim 226336809Sdimstatic const int MOV128SZ = 16; 227336809Sdimstatic const int MOV64SZ = 8; 228336809Sdimstatic const int MOV32SZ = 4; 229336809Sdimstatic const int MOV16SZ = 2; 230336809Sdimstatic const int MOV8SZ = 1; 231336809Sdim 232336809Sdimstatic unsigned getYMMtoXMMLoadOpcode(unsigned LoadOpcode) { 233336809Sdim switch (LoadOpcode) { 234336809Sdim case X86::VMOVUPSYrm: 235336809Sdim case X86::VMOVAPSYrm: 236336809Sdim return X86::VMOVUPSrm; 237336809Sdim case X86::VMOVUPDYrm: 238336809Sdim case X86::VMOVAPDYrm: 239336809Sdim return X86::VMOVUPDrm; 240336809Sdim case X86::VMOVDQUYrm: 241336809Sdim case X86::VMOVDQAYrm: 242336809Sdim return X86::VMOVDQUrm; 243336809Sdim case X86::VMOVUPSZ256rm: 244336809Sdim case X86::VMOVAPSZ256rm: 245336809Sdim return X86::VMOVUPSZ128rm; 246336809Sdim case X86::VMOVUPDZ256rm: 247336809Sdim case X86::VMOVAPDZ256rm: 248336809Sdim return X86::VMOVUPDZ128rm; 249336809Sdim case X86::VMOVDQU64Z256rm: 250336809Sdim case X86::VMOVDQA64Z256rm: 251336809Sdim return X86::VMOVDQU64Z128rm; 252336809Sdim case X86::VMOVDQU32Z256rm: 253336809Sdim case X86::VMOVDQA32Z256rm: 254336809Sdim return X86::VMOVDQU32Z128rm; 255336809Sdim default: 256336809Sdim llvm_unreachable("Unexpected Load Instruction Opcode"); 257336809Sdim } 258336809Sdim return 0; 259336809Sdim} 260336809Sdim 261336809Sdimstatic unsigned getYMMtoXMMStoreOpcode(unsigned StoreOpcode) { 262336809Sdim switch (StoreOpcode) { 263336809Sdim case X86::VMOVUPSYmr: 264336809Sdim case X86::VMOVAPSYmr: 265336809Sdim return X86::VMOVUPSmr; 266336809Sdim case X86::VMOVUPDYmr: 267336809Sdim case X86::VMOVAPDYmr: 268336809Sdim return X86::VMOVUPDmr; 269336809Sdim case X86::VMOVDQUYmr: 270336809Sdim case X86::VMOVDQAYmr: 271336809Sdim return X86::VMOVDQUmr; 272336809Sdim case X86::VMOVUPSZ256mr: 273336809Sdim case X86::VMOVAPSZ256mr: 274336809Sdim return X86::VMOVUPSZ128mr; 275336809Sdim case X86::VMOVUPDZ256mr: 276336809Sdim case X86::VMOVAPDZ256mr: 277336809Sdim return X86::VMOVUPDZ128mr; 278336809Sdim case X86::VMOVDQU64Z256mr: 279336809Sdim case X86::VMOVDQA64Z256mr: 280336809Sdim return X86::VMOVDQU64Z128mr; 281336809Sdim case X86::VMOVDQU32Z256mr: 282336809Sdim case X86::VMOVDQA32Z256mr: 283336809Sdim return X86::VMOVDQU32Z128mr; 284336809Sdim default: 285336809Sdim llvm_unreachable("Unexpected Load Instruction Opcode"); 286336809Sdim } 287336809Sdim return 0; 288336809Sdim} 289336809Sdim 290336809Sdimstatic int getAddrOffset(MachineInstr *MI) { 291336809Sdim const MCInstrDesc &Descl = MI->getDesc(); 292336809Sdim int AddrOffset = X86II::getMemoryOperandNo(Descl.TSFlags); 293336809Sdim assert(AddrOffset != -1 && "Expected Memory Operand"); 294336809Sdim AddrOffset += X86II::getOperandBias(Descl); 295336809Sdim return AddrOffset; 296336809Sdim} 297336809Sdim 298336809Sdimstatic MachineOperand &getBaseOperand(MachineInstr *MI) { 299336809Sdim int AddrOffset = getAddrOffset(MI); 300336809Sdim return MI->getOperand(AddrOffset + X86::AddrBaseReg); 301336809Sdim} 302336809Sdim 303336809Sdimstatic MachineOperand &getDispOperand(MachineInstr *MI) { 304336809Sdim int AddrOffset = getAddrOffset(MI); 305336809Sdim return MI->getOperand(AddrOffset + X86::AddrDisp); 306336809Sdim} 307336809Sdim 308336809Sdim// Relevant addressing modes contain only base register and immediate 309336809Sdim// displacement or frameindex and immediate displacement. 310336809Sdim// TODO: Consider expanding to other addressing modes in the future 311336809Sdimstatic bool isRelevantAddressingMode(MachineInstr *MI) { 312336809Sdim int AddrOffset = getAddrOffset(MI); 313336809Sdim MachineOperand &Base = getBaseOperand(MI); 314336809Sdim MachineOperand &Disp = getDispOperand(MI); 315336809Sdim MachineOperand &Scale = MI->getOperand(AddrOffset + X86::AddrScaleAmt); 316336809Sdim MachineOperand &Index = MI->getOperand(AddrOffset + X86::AddrIndexReg); 317336809Sdim MachineOperand &Segment = MI->getOperand(AddrOffset + X86::AddrSegmentReg); 318336809Sdim 319336809Sdim if (!((Base.isReg() && Base.getReg() != X86::NoRegister) || Base.isFI())) 320336809Sdim return false; 321336809Sdim if (!Disp.isImm()) 322336809Sdim return false; 323336809Sdim if (Scale.getImm() != 1) 324336809Sdim return false; 325336809Sdim if (!(Index.isReg() && Index.getReg() == X86::NoRegister)) 326336809Sdim return false; 327336809Sdim if (!(Segment.isReg() && Segment.getReg() == X86::NoRegister)) 328336809Sdim return false; 329336809Sdim return true; 330336809Sdim} 331336809Sdim 332336809Sdim// Collect potentially blocking stores. 333336809Sdim// Limit the number of instructions backwards we want to inspect 334336809Sdim// since the effect of store block won't be visible if the store 335336809Sdim// and load instructions have enough instructions in between to 336336809Sdim// keep the core busy. 337336809Sdimstatic SmallVector<MachineInstr *, 2> 338336809SdimfindPotentialBlockers(MachineInstr *LoadInst) { 339336809Sdim SmallVector<MachineInstr *, 2> PotentialBlockers; 340336809Sdim unsigned BlockCount = 0; 341336809Sdim const unsigned InspectionLimit = X86AvoidSFBInspectionLimit; 342336809Sdim for (auto PBInst = std::next(MachineBasicBlock::reverse_iterator(LoadInst)), 343336809Sdim E = LoadInst->getParent()->rend(); 344336809Sdim PBInst != E; ++PBInst) { 345353358Sdim if (PBInst->isMetaInstruction()) 346353358Sdim continue; 347336809Sdim BlockCount++; 348336809Sdim if (BlockCount >= InspectionLimit) 349336809Sdim break; 350336809Sdim MachineInstr &MI = *PBInst; 351336809Sdim if (MI.getDesc().isCall()) 352336809Sdim return PotentialBlockers; 353336809Sdim PotentialBlockers.push_back(&MI); 354336809Sdim } 355336809Sdim // If we didn't get to the instructions limit try predecessing blocks. 356336809Sdim // Ideally we should traverse the predecessor blocks in depth with some 357336809Sdim // coloring algorithm, but for now let's just look at the first order 358336809Sdim // predecessors. 359336809Sdim if (BlockCount < InspectionLimit) { 360336809Sdim MachineBasicBlock *MBB = LoadInst->getParent(); 361336809Sdim int LimitLeft = InspectionLimit - BlockCount; 362336809Sdim for (MachineBasicBlock::pred_iterator PB = MBB->pred_begin(), 363336809Sdim PE = MBB->pred_end(); 364336809Sdim PB != PE; ++PB) { 365336809Sdim MachineBasicBlock *PMBB = *PB; 366336809Sdim int PredCount = 0; 367336809Sdim for (MachineBasicBlock::reverse_iterator PBInst = PMBB->rbegin(), 368336809Sdim PME = PMBB->rend(); 369336809Sdim PBInst != PME; ++PBInst) { 370353358Sdim if (PBInst->isMetaInstruction()) 371353358Sdim continue; 372336809Sdim PredCount++; 373336809Sdim if (PredCount >= LimitLeft) 374336809Sdim break; 375336809Sdim if (PBInst->getDesc().isCall()) 376336809Sdim break; 377336809Sdim PotentialBlockers.push_back(&*PBInst); 378336809Sdim } 379336809Sdim } 380336809Sdim } 381336809Sdim return PotentialBlockers; 382336809Sdim} 383336809Sdim 384336809Sdimvoid X86AvoidSFBPass::buildCopy(MachineInstr *LoadInst, unsigned NLoadOpcode, 385336809Sdim int64_t LoadDisp, MachineInstr *StoreInst, 386336809Sdim unsigned NStoreOpcode, int64_t StoreDisp, 387336809Sdim unsigned Size, int64_t LMMOffset, 388336809Sdim int64_t SMMOffset) { 389336809Sdim MachineOperand &LoadBase = getBaseOperand(LoadInst); 390336809Sdim MachineOperand &StoreBase = getBaseOperand(StoreInst); 391336809Sdim MachineBasicBlock *MBB = LoadInst->getParent(); 392336809Sdim MachineMemOperand *LMMO = *LoadInst->memoperands_begin(); 393336809Sdim MachineMemOperand *SMMO = *StoreInst->memoperands_begin(); 394336809Sdim 395360784Sdim Register Reg1 = MRI->createVirtualRegister( 396336809Sdim TII->getRegClass(TII->get(NLoadOpcode), 0, TRI, *(MBB->getParent()))); 397336809Sdim MachineInstr *NewLoad = 398336809Sdim BuildMI(*MBB, LoadInst, LoadInst->getDebugLoc(), TII->get(NLoadOpcode), 399336809Sdim Reg1) 400336809Sdim .add(LoadBase) 401336809Sdim .addImm(1) 402336809Sdim .addReg(X86::NoRegister) 403336809Sdim .addImm(LoadDisp) 404336809Sdim .addReg(X86::NoRegister) 405336809Sdim .addMemOperand( 406336809Sdim MBB->getParent()->getMachineMemOperand(LMMO, LMMOffset, Size)); 407336809Sdim if (LoadBase.isReg()) 408336809Sdim getBaseOperand(NewLoad).setIsKill(false); 409336809Sdim LLVM_DEBUG(NewLoad->dump()); 410336809Sdim // If the load and store are consecutive, use the loadInst location to 411336809Sdim // reduce register pressure. 412336809Sdim MachineInstr *StInst = StoreInst; 413353358Sdim auto PrevInstrIt = skipDebugInstructionsBackward( 414353358Sdim std::prev(MachineBasicBlock::instr_iterator(StoreInst)), 415353358Sdim MBB->instr_begin()); 416353358Sdim if (PrevInstrIt.getNodePtr() == LoadInst) 417336809Sdim StInst = LoadInst; 418336809Sdim MachineInstr *NewStore = 419336809Sdim BuildMI(*MBB, StInst, StInst->getDebugLoc(), TII->get(NStoreOpcode)) 420336809Sdim .add(StoreBase) 421336809Sdim .addImm(1) 422336809Sdim .addReg(X86::NoRegister) 423336809Sdim .addImm(StoreDisp) 424336809Sdim .addReg(X86::NoRegister) 425336809Sdim .addReg(Reg1) 426336809Sdim .addMemOperand( 427336809Sdim MBB->getParent()->getMachineMemOperand(SMMO, SMMOffset, Size)); 428336809Sdim if (StoreBase.isReg()) 429336809Sdim getBaseOperand(NewStore).setIsKill(false); 430336809Sdim MachineOperand &StoreSrcVReg = StoreInst->getOperand(X86::AddrNumOperands); 431336809Sdim assert(StoreSrcVReg.isReg() && "Expected virtual register"); 432336809Sdim NewStore->getOperand(X86::AddrNumOperands).setIsKill(StoreSrcVReg.isKill()); 433336809Sdim LLVM_DEBUG(NewStore->dump()); 434336809Sdim} 435336809Sdim 436336809Sdimvoid X86AvoidSFBPass::buildCopies(int Size, MachineInstr *LoadInst, 437336809Sdim int64_t LdDispImm, MachineInstr *StoreInst, 438336809Sdim int64_t StDispImm, int64_t LMMOffset, 439336809Sdim int64_t SMMOffset) { 440336809Sdim int LdDisp = LdDispImm; 441336809Sdim int StDisp = StDispImm; 442336809Sdim while (Size > 0) { 443336809Sdim if ((Size - MOV128SZ >= 0) && isYMMLoadOpcode(LoadInst->getOpcode())) { 444336809Sdim Size = Size - MOV128SZ; 445336809Sdim buildCopy(LoadInst, getYMMtoXMMLoadOpcode(LoadInst->getOpcode()), LdDisp, 446336809Sdim StoreInst, getYMMtoXMMStoreOpcode(StoreInst->getOpcode()), 447336809Sdim StDisp, MOV128SZ, LMMOffset, SMMOffset); 448336809Sdim LdDisp += MOV128SZ; 449336809Sdim StDisp += MOV128SZ; 450336809Sdim LMMOffset += MOV128SZ; 451336809Sdim SMMOffset += MOV128SZ; 452336809Sdim continue; 453336809Sdim } 454336809Sdim if (Size - MOV64SZ >= 0) { 455336809Sdim Size = Size - MOV64SZ; 456336809Sdim buildCopy(LoadInst, X86::MOV64rm, LdDisp, StoreInst, X86::MOV64mr, StDisp, 457336809Sdim MOV64SZ, LMMOffset, SMMOffset); 458336809Sdim LdDisp += MOV64SZ; 459336809Sdim StDisp += MOV64SZ; 460336809Sdim LMMOffset += MOV64SZ; 461336809Sdim SMMOffset += MOV64SZ; 462336809Sdim continue; 463336809Sdim } 464336809Sdim if (Size - MOV32SZ >= 0) { 465336809Sdim Size = Size - MOV32SZ; 466336809Sdim buildCopy(LoadInst, X86::MOV32rm, LdDisp, StoreInst, X86::MOV32mr, StDisp, 467336809Sdim MOV32SZ, LMMOffset, SMMOffset); 468336809Sdim LdDisp += MOV32SZ; 469336809Sdim StDisp += MOV32SZ; 470336809Sdim LMMOffset += MOV32SZ; 471336809Sdim SMMOffset += MOV32SZ; 472336809Sdim continue; 473336809Sdim } 474336809Sdim if (Size - MOV16SZ >= 0) { 475336809Sdim Size = Size - MOV16SZ; 476336809Sdim buildCopy(LoadInst, X86::MOV16rm, LdDisp, StoreInst, X86::MOV16mr, StDisp, 477336809Sdim MOV16SZ, LMMOffset, SMMOffset); 478336809Sdim LdDisp += MOV16SZ; 479336809Sdim StDisp += MOV16SZ; 480336809Sdim LMMOffset += MOV16SZ; 481336809Sdim SMMOffset += MOV16SZ; 482336809Sdim continue; 483336809Sdim } 484336809Sdim if (Size - MOV8SZ >= 0) { 485336809Sdim Size = Size - MOV8SZ; 486336809Sdim buildCopy(LoadInst, X86::MOV8rm, LdDisp, StoreInst, X86::MOV8mr, StDisp, 487336809Sdim MOV8SZ, LMMOffset, SMMOffset); 488336809Sdim LdDisp += MOV8SZ; 489336809Sdim StDisp += MOV8SZ; 490336809Sdim LMMOffset += MOV8SZ; 491336809Sdim SMMOffset += MOV8SZ; 492336809Sdim continue; 493336809Sdim } 494336809Sdim } 495336809Sdim assert(Size == 0 && "Wrong size division"); 496336809Sdim} 497336809Sdim 498336809Sdimstatic void updateKillStatus(MachineInstr *LoadInst, MachineInstr *StoreInst) { 499336809Sdim MachineOperand &LoadBase = getBaseOperand(LoadInst); 500336809Sdim MachineOperand &StoreBase = getBaseOperand(StoreInst); 501353358Sdim auto StorePrevNonDbgInstr = skipDebugInstructionsBackward( 502353358Sdim std::prev(MachineBasicBlock::instr_iterator(StoreInst)), 503353358Sdim LoadInst->getParent()->instr_begin()).getNodePtr(); 504336809Sdim if (LoadBase.isReg()) { 505336809Sdim MachineInstr *LastLoad = LoadInst->getPrevNode(); 506336809Sdim // If the original load and store to xmm/ymm were consecutive 507336809Sdim // then the partial copies were also created in 508336809Sdim // a consecutive order to reduce register pressure, 509336809Sdim // and the location of the last load is before the last store. 510353358Sdim if (StorePrevNonDbgInstr == LoadInst) 511336809Sdim LastLoad = LoadInst->getPrevNode()->getPrevNode(); 512336809Sdim getBaseOperand(LastLoad).setIsKill(LoadBase.isKill()); 513336809Sdim } 514336809Sdim if (StoreBase.isReg()) { 515336809Sdim MachineInstr *StInst = StoreInst; 516353358Sdim if (StorePrevNonDbgInstr == LoadInst) 517336809Sdim StInst = LoadInst; 518336809Sdim getBaseOperand(StInst->getPrevNode()).setIsKill(StoreBase.isKill()); 519336809Sdim } 520336809Sdim} 521336809Sdim 522336809Sdimbool X86AvoidSFBPass::alias(const MachineMemOperand &Op1, 523336809Sdim const MachineMemOperand &Op2) const { 524336809Sdim if (!Op1.getValue() || !Op2.getValue()) 525336809Sdim return true; 526336809Sdim 527336809Sdim int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset()); 528336809Sdim int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset; 529336809Sdim int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset; 530336809Sdim 531336809Sdim AliasResult AAResult = 532336809Sdim AA->alias(MemoryLocation(Op1.getValue(), Overlapa, Op1.getAAInfo()), 533336809Sdim MemoryLocation(Op2.getValue(), Overlapb, Op2.getAAInfo())); 534336809Sdim return AAResult != NoAlias; 535336809Sdim} 536336809Sdim 537336809Sdimvoid X86AvoidSFBPass::findPotentiallylBlockedCopies(MachineFunction &MF) { 538336809Sdim for (auto &MBB : MF) 539336809Sdim for (auto &MI : MBB) { 540336809Sdim if (!isPotentialBlockedMemCpyLd(MI.getOpcode())) 541336809Sdim continue; 542336809Sdim int DefVR = MI.getOperand(0).getReg(); 543353358Sdim if (!MRI->hasOneNonDBGUse(DefVR)) 544336809Sdim continue; 545336809Sdim for (auto UI = MRI->use_nodbg_begin(DefVR), UE = MRI->use_nodbg_end(); 546336809Sdim UI != UE;) { 547336809Sdim MachineOperand &StoreMO = *UI++; 548336809Sdim MachineInstr &StoreMI = *StoreMO.getParent(); 549336809Sdim // Skip cases where the memcpy may overlap. 550336809Sdim if (StoreMI.getParent() == MI.getParent() && 551336809Sdim isPotentialBlockedMemCpyPair(MI.getOpcode(), StoreMI.getOpcode()) && 552336809Sdim isRelevantAddressingMode(&MI) && 553336809Sdim isRelevantAddressingMode(&StoreMI)) { 554336809Sdim assert(MI.hasOneMemOperand() && 555336809Sdim "Expected one memory operand for load instruction"); 556336809Sdim assert(StoreMI.hasOneMemOperand() && 557336809Sdim "Expected one memory operand for store instruction"); 558336809Sdim if (!alias(**MI.memoperands_begin(), **StoreMI.memoperands_begin())) 559336809Sdim BlockedLoadsStoresPairs.push_back(std::make_pair(&MI, &StoreMI)); 560336809Sdim } 561336809Sdim } 562336809Sdim } 563336809Sdim} 564336809Sdim 565336809Sdimunsigned X86AvoidSFBPass::getRegSizeInBytes(MachineInstr *LoadInst) { 566336809Sdim auto TRC = TII->getRegClass(TII->get(LoadInst->getOpcode()), 0, TRI, 567336809Sdim *LoadInst->getParent()->getParent()); 568336809Sdim return TRI->getRegSizeInBits(*TRC) / 8; 569336809Sdim} 570336809Sdim 571336809Sdimvoid X86AvoidSFBPass::breakBlockedCopies( 572336809Sdim MachineInstr *LoadInst, MachineInstr *StoreInst, 573336809Sdim const DisplacementSizeMap &BlockingStoresDispSizeMap) { 574336809Sdim int64_t LdDispImm = getDispOperand(LoadInst).getImm(); 575336809Sdim int64_t StDispImm = getDispOperand(StoreInst).getImm(); 576336809Sdim int64_t LMMOffset = 0; 577336809Sdim int64_t SMMOffset = 0; 578336809Sdim 579336809Sdim int64_t LdDisp1 = LdDispImm; 580336809Sdim int64_t LdDisp2 = 0; 581336809Sdim int64_t StDisp1 = StDispImm; 582336809Sdim int64_t StDisp2 = 0; 583336809Sdim unsigned Size1 = 0; 584336809Sdim unsigned Size2 = 0; 585336809Sdim int64_t LdStDelta = StDispImm - LdDispImm; 586336809Sdim 587336809Sdim for (auto DispSizePair : BlockingStoresDispSizeMap) { 588336809Sdim LdDisp2 = DispSizePair.first; 589336809Sdim StDisp2 = DispSizePair.first + LdStDelta; 590336809Sdim Size2 = DispSizePair.second; 591336809Sdim // Avoid copying overlapping areas. 592336809Sdim if (LdDisp2 < LdDisp1) { 593336809Sdim int OverlapDelta = LdDisp1 - LdDisp2; 594336809Sdim LdDisp2 += OverlapDelta; 595336809Sdim StDisp2 += OverlapDelta; 596336809Sdim Size2 -= OverlapDelta; 597336809Sdim } 598344779Sdim Size1 = LdDisp2 - LdDisp1; 599336809Sdim 600336809Sdim // Build a copy for the point until the current blocking store's 601336809Sdim // displacement. 602336809Sdim buildCopies(Size1, LoadInst, LdDisp1, StoreInst, StDisp1, LMMOffset, 603336809Sdim SMMOffset); 604336809Sdim // Build a copy for the current blocking store. 605336809Sdim buildCopies(Size2, LoadInst, LdDisp2, StoreInst, StDisp2, LMMOffset + Size1, 606336809Sdim SMMOffset + Size1); 607336809Sdim LdDisp1 = LdDisp2 + Size2; 608336809Sdim StDisp1 = StDisp2 + Size2; 609336809Sdim LMMOffset += Size1 + Size2; 610336809Sdim SMMOffset += Size1 + Size2; 611336809Sdim } 612336809Sdim unsigned Size3 = (LdDispImm + getRegSizeInBytes(LoadInst)) - LdDisp1; 613336809Sdim buildCopies(Size3, LoadInst, LdDisp1, StoreInst, StDisp1, LMMOffset, 614336809Sdim LMMOffset); 615336809Sdim} 616336809Sdim 617336809Sdimstatic bool hasSameBaseOpValue(MachineInstr *LoadInst, 618336809Sdim MachineInstr *StoreInst) { 619336809Sdim MachineOperand &LoadBase = getBaseOperand(LoadInst); 620336809Sdim MachineOperand &StoreBase = getBaseOperand(StoreInst); 621336809Sdim if (LoadBase.isReg() != StoreBase.isReg()) 622336809Sdim return false; 623336809Sdim if (LoadBase.isReg()) 624336809Sdim return LoadBase.getReg() == StoreBase.getReg(); 625336809Sdim return LoadBase.getIndex() == StoreBase.getIndex(); 626336809Sdim} 627336809Sdim 628336809Sdimstatic bool isBlockingStore(int64_t LoadDispImm, unsigned LoadSize, 629336809Sdim int64_t StoreDispImm, unsigned StoreSize) { 630336809Sdim return ((StoreDispImm >= LoadDispImm) && 631336809Sdim (StoreDispImm <= LoadDispImm + (LoadSize - StoreSize))); 632336809Sdim} 633336809Sdim 634336809Sdim// Keep track of all stores blocking a load 635336809Sdimstatic void 636336809SdimupdateBlockingStoresDispSizeMap(DisplacementSizeMap &BlockingStoresDispSizeMap, 637336809Sdim int64_t DispImm, unsigned Size) { 638336809Sdim if (BlockingStoresDispSizeMap.count(DispImm)) { 639336809Sdim // Choose the smallest blocking store starting at this displacement. 640336809Sdim if (BlockingStoresDispSizeMap[DispImm] > Size) 641336809Sdim BlockingStoresDispSizeMap[DispImm] = Size; 642336809Sdim 643336809Sdim } else 644336809Sdim BlockingStoresDispSizeMap[DispImm] = Size; 645336809Sdim} 646336809Sdim 647336809Sdim// Remove blocking stores contained in each other. 648336809Sdimstatic void 649336809SdimremoveRedundantBlockingStores(DisplacementSizeMap &BlockingStoresDispSizeMap) { 650336809Sdim if (BlockingStoresDispSizeMap.size() <= 1) 651336809Sdim return; 652336809Sdim 653344779Sdim SmallVector<std::pair<int64_t, unsigned>, 0> DispSizeStack; 654344779Sdim for (auto DispSizePair : BlockingStoresDispSizeMap) { 655344779Sdim int64_t CurrDisp = DispSizePair.first; 656344779Sdim unsigned CurrSize = DispSizePair.second; 657344779Sdim while (DispSizeStack.size()) { 658344779Sdim int64_t PrevDisp = DispSizeStack.back().first; 659344779Sdim unsigned PrevSize = DispSizeStack.back().second; 660344779Sdim if (CurrDisp + CurrSize > PrevDisp + PrevSize) 661344779Sdim break; 662344779Sdim DispSizeStack.pop_back(); 663336809Sdim } 664344779Sdim DispSizeStack.push_back(DispSizePair); 665336809Sdim } 666344779Sdim BlockingStoresDispSizeMap.clear(); 667344779Sdim for (auto Disp : DispSizeStack) 668344779Sdim BlockingStoresDispSizeMap.insert(Disp); 669336809Sdim} 670336809Sdim 671336809Sdimbool X86AvoidSFBPass::runOnMachineFunction(MachineFunction &MF) { 672336809Sdim bool Changed = false; 673336809Sdim 674336809Sdim if (DisableX86AvoidStoreForwardBlocks || skipFunction(MF.getFunction()) || 675336809Sdim !MF.getSubtarget<X86Subtarget>().is64Bit()) 676336809Sdim return false; 677336809Sdim 678336809Sdim MRI = &MF.getRegInfo(); 679336809Sdim assert(MRI->isSSA() && "Expected MIR to be in SSA form"); 680336809Sdim TII = MF.getSubtarget<X86Subtarget>().getInstrInfo(); 681336809Sdim TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo(); 682336809Sdim AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 683336809Sdim LLVM_DEBUG(dbgs() << "Start X86AvoidStoreForwardBlocks\n";); 684336809Sdim // Look for a load then a store to XMM/YMM which look like a memcpy 685336809Sdim findPotentiallylBlockedCopies(MF); 686336809Sdim 687336809Sdim for (auto LoadStoreInstPair : BlockedLoadsStoresPairs) { 688336809Sdim MachineInstr *LoadInst = LoadStoreInstPair.first; 689336809Sdim int64_t LdDispImm = getDispOperand(LoadInst).getImm(); 690336809Sdim DisplacementSizeMap BlockingStoresDispSizeMap; 691336809Sdim 692336809Sdim SmallVector<MachineInstr *, 2> PotentialBlockers = 693336809Sdim findPotentialBlockers(LoadInst); 694336809Sdim for (auto PBInst : PotentialBlockers) { 695336809Sdim if (!isPotentialBlockingStoreInst(PBInst->getOpcode(), 696336809Sdim LoadInst->getOpcode()) || 697336809Sdim !isRelevantAddressingMode(PBInst)) 698336809Sdim continue; 699336809Sdim int64_t PBstDispImm = getDispOperand(PBInst).getImm(); 700336809Sdim assert(PBInst->hasOneMemOperand() && "Expected One Memory Operand"); 701336809Sdim unsigned PBstSize = (*PBInst->memoperands_begin())->getSize(); 702336809Sdim // This check doesn't cover all cases, but it will suffice for now. 703336809Sdim // TODO: take branch probability into consideration, if the blocking 704336809Sdim // store is in an unreached block, breaking the memcopy could lose 705336809Sdim // performance. 706336809Sdim if (hasSameBaseOpValue(LoadInst, PBInst) && 707336809Sdim isBlockingStore(LdDispImm, getRegSizeInBytes(LoadInst), PBstDispImm, 708336809Sdim PBstSize)) 709336809Sdim updateBlockingStoresDispSizeMap(BlockingStoresDispSizeMap, PBstDispImm, 710336809Sdim PBstSize); 711336809Sdim } 712336809Sdim 713336809Sdim if (BlockingStoresDispSizeMap.empty()) 714336809Sdim continue; 715336809Sdim 716336809Sdim // We found a store forward block, break the memcpy's load and store 717336809Sdim // into smaller copies such that each smaller store that was causing 718336809Sdim // a store block would now be copied separately. 719336809Sdim MachineInstr *StoreInst = LoadStoreInstPair.second; 720336809Sdim LLVM_DEBUG(dbgs() << "Blocked load and store instructions: \n"); 721336809Sdim LLVM_DEBUG(LoadInst->dump()); 722336809Sdim LLVM_DEBUG(StoreInst->dump()); 723336809Sdim LLVM_DEBUG(dbgs() << "Replaced with:\n"); 724336809Sdim removeRedundantBlockingStores(BlockingStoresDispSizeMap); 725336809Sdim breakBlockedCopies(LoadInst, StoreInst, BlockingStoresDispSizeMap); 726336809Sdim updateKillStatus(LoadInst, StoreInst); 727336809Sdim ForRemoval.push_back(LoadInst); 728336809Sdim ForRemoval.push_back(StoreInst); 729336809Sdim } 730336809Sdim for (auto RemovedInst : ForRemoval) { 731336809Sdim RemovedInst->eraseFromParent(); 732336809Sdim } 733336809Sdim ForRemoval.clear(); 734336809Sdim BlockedLoadsStoresPairs.clear(); 735336809Sdim LLVM_DEBUG(dbgs() << "End X86AvoidStoreForwardBlocks\n";); 736336809Sdim 737336809Sdim return Changed; 738336809Sdim} 739