contrib/llvm-project/llvm/lib/Target/X86/X86AvoidStoreForwardingBlocks.cpp

   1 //===- X86AvoidStoreForwardingBlockis.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // If a load follows a store and reloads data that the store has written to
  10 // memory, Intel microarchitectures can in many cases forward the data directly
  11 // from the store to the load, This "store forwarding" saves cycles by enabling
  12 // the load to directly obtain the data instead of accessing the data from
  13 // cache or memory.
  14 // A "store forward block" occurs in cases that a store cannot be forwarded to
  15 // the load. The most typical case of store forward block on Intel Core
  16 // 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 sequence
  21 // of a load and a store.
  22 //
  23 // The pass currently only handles cases where memcpy is lowered to
  24 // XMM/YMM registers, it tries to break the memcpy into smaller copies.
  25 // breaking the memcpy should be possible since there is no atomicity
  26 // guarantee for loads and stores to XMM/YMM.
  27 //
  28 // It could be better for performance to solve the problem by loading
  29 // to XMM/YMM then inserting the partial store before storing back from XMM/YMM
  30 // to memory, but this will result in a more conservative optimization since it
  31 // requires we prove that all memory accesses between the blocking store and the
  32 // load must alias/don't alias before we can move the store, whereas the
  33 // transformation done here is correct regardless to other memory accesses.
  34 //===----------------------------------------------------------------------===//
  35
  36 #include "X86InstrInfo.h"
  37 #include "X86Subtarget.h"
  38 #include "llvm/Analysis/AliasAnalysis.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/InitializePasses.h"
  50 #include "llvm/MC/MCInstrDesc.h"
  51
  52 using namespace llvm;
  53
  54 #define DEBUG_TYPE "x86-avoid-SFB"
  55
  56 static cl::opt<bool> DisableX86AvoidStoreForwardBlocks(
  57     "x86-disable-avoid-SFB", cl::Hidden,
  58     cl::desc("X86: Disable Store Forwarding Blocks fixup."), cl::init(false));
  59
  60 static 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
  66 namespace {
  67
  68 using DisplacementSizeMap = std::map<int64_t, unsigned>;
  69
  70 class X86AvoidSFBPass : public MachineFunctionPass {
  71 public:
  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
  86 private:
  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 look
  96   ///  like a memcpy.
  97   void findPotentiallylBlockedCopies(MachineFunction &MF);
  98   /// Break the memcpy's load and store into smaller copies
  99   /// such that each memory load that was blocked by a smaller store
 100   /// 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 namespace
 119
 120 char X86AvoidSFBPass::ID = 0;
 121
 122 INITIALIZE_PASS_BEGIN(X86AvoidSFBPass, DEBUG_TYPE, "Machine code sinking",
 123                       false, false)
 124 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 125 INITIALIZE_PASS_END(X86AvoidSFBPass, DEBUG_TYPE, "Machine code sinking", false,
 126                     false)
 127
 128 FunctionPass *llvm::createX86AvoidStoreForwardingBlocks() {
 129   return new X86AvoidSFBPass();
 130 }
 131
 132 static 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 }
 142 static 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
 152 static bool isPotentialBlockedMemCpyLd(unsigned Opcode) {
 153   return isXMMLoadOpcode(Opcode) || isYMMLoadOpcode(Opcode);
 154 }
 155
 156 static bool isPotentialBlockedMemCpyPair(int LdOpcode, int 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
 208 static bool isPotentialBlockingStoreInst(int Opcode, int 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
 226 static const int MOV128SZ = 16;
 227 static const int MOV64SZ = 8;
 228 static const int MOV32SZ = 4;
 229 static const int MOV16SZ = 2;
 230 static const int MOV8SZ = 1;
 231
 232 static 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
 261 static 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
 290 static int getAddrOffset(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
 298 static MachineOperand &getBaseOperand(MachineInstr *MI) {
 299   int AddrOffset = getAddrOffset(MI);
 300   return MI->getOperand(AddrOffset + X86::AddrBaseReg);
 301 }
 302
 303 static 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 immediate
 309 // displacement or frameindex and immediate displacement.
 310 // TODO: Consider expanding to other addressing modes in the future
 311 static bool isRelevantAddressingMode(MachineInstr *MI) {
 312   int AddrOffset = getAddrOffset(MI);
 313   MachineOperand &Base = getBaseOperand(MI);
 314   MachineOperand &Disp = getDispOperand(MI);
 315   MachineOperand &Scale = MI->getOperand(AddrOffset + X86::AddrScaleAmt);
 316   MachineOperand &Index = MI->getOperand(AddrOffset + X86::AddrIndexReg);
 317   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 inspect
 334 // since the effect of store block won't be visible if the store
 335 // and load instructions have enough instructions in between to
 336 // keep the core busy.
 337 static SmallVector<MachineInstr *, 2>
 338 findPotentialBlockers(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 some
 357   // coloring algorithm, but for now let's just look at the first order
 358   // predecessors.
 359   if (BlockCount < InspectionLimit) {
 360     MachineBasicBlock *MBB = LoadInst->getParent();
 361     int LimitLeft = InspectionLimit - BlockCount;
 362     for (MachineBasicBlock::pred_iterator PB = MBB->pred_begin(),
 363                                           PE = MBB->pred_end();
 364          PB != PE; ++PB) {
 365       MachineBasicBlock *PMBB = *PB;
 366       int PredCount = 0;
 367       for (MachineBasicBlock::reverse_iterator PBInst = PMBB->rbegin(),
 368                                                PME = PMBB->rend();
 369            PBInst != PME; ++PBInst) {
 370         if (PBInst->isMetaInstruction())
 371           continue;
 372         PredCount++;
 373         if (PredCount >= LimitLeft)
 374           break;
 375         if (PBInst->getDesc().isCall())
 376           break;
 377         PotentialBlockers.push_back(&*PBInst);
 378       }
 379     }
 380   }
 381   return PotentialBlockers;
 382 }
 383
 384 void X86AvoidSFBPass::buildCopy(MachineInstr *LoadInst, unsigned NLoadOpcode,
 385                                 int64_t LoadDisp, MachineInstr *StoreInst,
 386                                 unsigned NStoreOpcode, int64_t StoreDisp,
 387                                 unsigned Size, int64_t LMMOffset,
 388                                 int64_t SMMOffset) {
 389   MachineOperand &LoadBase = getBaseOperand(LoadInst);
 390   MachineOperand &StoreBase = getBaseOperand(StoreInst);
 391   MachineBasicBlock *MBB = LoadInst->getParent();
 392   MachineMemOperand *LMMO = *LoadInst->memoperands_begin();
 393   MachineMemOperand *SMMO = *StoreInst->memoperands_begin();
 394
 395   Register Reg1 = MRI->createVirtualRegister(
 396       TII->getRegClass(TII->get(NLoadOpcode), 0, TRI, *(MBB->getParent())));
 397   MachineInstr *NewLoad =
 398       BuildMI(*MBB, LoadInst, LoadInst->getDebugLoc(), TII->get(NLoadOpcode),
 399               Reg1)
 400           .add(LoadBase)
 401           .addImm(1)
 402           .addReg(X86::NoRegister)
 403           .addImm(LoadDisp)
 404           .addReg(X86::NoRegister)
 405           .addMemOperand(
 406               MBB->getParent()->getMachineMemOperand(LMMO, LMMOffset, Size));
 407   if (LoadBase.isReg())
 408     getBaseOperand(NewLoad).setIsKill(false);
 409   LLVM_DEBUG(NewLoad->dump());
 410   // If the load and store are consecutive, use the loadInst location to
 411   // reduce register pressure.
 412   MachineInstr *StInst = StoreInst;
 413   auto PrevInstrIt = skipDebugInstructionsBackward(
 414       std::prev(MachineBasicBlock::instr_iterator(StoreInst)),
 415       MBB->instr_begin());
 416   if (PrevInstrIt.getNodePtr() == LoadInst)
 417     StInst = LoadInst;
 418   MachineInstr *NewStore =
 419       BuildMI(*MBB, StInst, StInst->getDebugLoc(), TII->get(NStoreOpcode))
 420           .add(StoreBase)
 421           .addImm(1)
 422           .addReg(X86::NoRegister)
 423           .addImm(StoreDisp)
 424           .addReg(X86::NoRegister)
 425           .addReg(Reg1)
 426           .addMemOperand(
 427               MBB->getParent()->getMachineMemOperand(SMMO, SMMOffset, Size));
 428   if (StoreBase.isReg())
 429     getBaseOperand(NewStore).setIsKill(false);
 430   MachineOperand &StoreSrcVReg = StoreInst->getOperand(X86::AddrNumOperands);
 431   assert(StoreSrcVReg.isReg() && "Expected virtual register");
 432   NewStore->getOperand(X86::AddrNumOperands).setIsKill(StoreSrcVReg.isKill());
 433   LLVM_DEBUG(NewStore->dump());
 434 }
 435
 436 void X86AvoidSFBPass::buildCopies(int Size, MachineInstr *LoadInst,
 437                                   int64_t LdDispImm, MachineInstr *StoreInst,
 438                                   int64_t StDispImm, int64_t LMMOffset,
 439                                   int64_t SMMOffset) {
 440   int LdDisp = LdDispImm;
 441   int StDisp = StDispImm;
 442   while (Size > 0) {
 443     if ((Size - MOV128SZ >= 0) && isYMMLoadOpcode(LoadInst->getOpcode())) {
 444       Size = Size - MOV128SZ;
 445       buildCopy(LoadInst, getYMMtoXMMLoadOpcode(LoadInst->getOpcode()), LdDisp,
 446                 StoreInst, getYMMtoXMMStoreOpcode(StoreInst->getOpcode()),
 447                 StDisp, MOV128SZ, LMMOffset, SMMOffset);
 448       LdDisp += MOV128SZ;
 449       StDisp += MOV128SZ;
 450       LMMOffset += MOV128SZ;
 451       SMMOffset += MOV128SZ;
 452       continue;
 453     }
 454     if (Size - MOV64SZ >= 0) {
 455       Size = Size - MOV64SZ;
 456       buildCopy(LoadInst, X86::MOV64rm, LdDisp, StoreInst, X86::MOV64mr, StDisp,
 457                 MOV64SZ, LMMOffset, SMMOffset);
 458       LdDisp += MOV64SZ;
 459       StDisp += MOV64SZ;
 460       LMMOffset += MOV64SZ;
 461       SMMOffset += MOV64SZ;
 462       continue;
 463     }
 464     if (Size - MOV32SZ >= 0) {
 465       Size = Size - MOV32SZ;
 466       buildCopy(LoadInst, X86::MOV32rm, LdDisp, StoreInst, X86::MOV32mr, StDisp,
 467                 MOV32SZ, LMMOffset, SMMOffset);
 468       LdDisp += MOV32SZ;
 469       StDisp += MOV32SZ;
 470       LMMOffset += MOV32SZ;
 471       SMMOffset += MOV32SZ;
 472       continue;
 473     }
 474     if (Size - MOV16SZ >= 0) {
 475       Size = Size - MOV16SZ;
 476       buildCopy(LoadInst, X86::MOV16rm, LdDisp, StoreInst, X86::MOV16mr, StDisp,
 477                 MOV16SZ, LMMOffset, SMMOffset);
 478       LdDisp += MOV16SZ;
 479       StDisp += MOV16SZ;
 480       LMMOffset += MOV16SZ;
 481       SMMOffset += MOV16SZ;
 482       continue;
 483     }
 484     if (Size - MOV8SZ >= 0) {
 485       Size = Size - MOV8SZ;
 486       buildCopy(LoadInst, X86::MOV8rm, LdDisp, StoreInst, X86::MOV8mr, StDisp,
 487                 MOV8SZ, LMMOffset, SMMOffset);
 488       LdDisp += MOV8SZ;
 489       StDisp += MOV8SZ;
 490       LMMOffset += MOV8SZ;
 491       SMMOffset += MOV8SZ;
 492       continue;
 493     }
 494   }
 495   assert(Size == 0 && "Wrong size division");
 496 }
 497
 498 static void updateKillStatus(MachineInstr *LoadInst, MachineInstr *StoreInst) {
 499   MachineOperand &LoadBase = getBaseOperand(LoadInst);
 500   MachineOperand &StoreBase = getBaseOperand(StoreInst);
 501   auto StorePrevNonDbgInstr = skipDebugInstructionsBackward(
 502           std::prev(MachineBasicBlock::instr_iterator(StoreInst)),
 503           LoadInst->getParent()->instr_begin()).getNodePtr();
 504   if (LoadBase.isReg()) {
 505     MachineInstr *LastLoad = LoadInst->getPrevNode();
 506     // If the original load and store to xmm/ymm were consecutive
 507     // then the partial copies were also created in
 508     // a consecutive order to reduce register pressure,
 509     // and the location of the last load is before the last store.
 510     if (StorePrevNonDbgInstr == LoadInst)
 511       LastLoad = LoadInst->getPrevNode()->getPrevNode();
 512     getBaseOperand(LastLoad).setIsKill(LoadBase.isKill());
 513   }
 514   if (StoreBase.isReg()) {
 515     MachineInstr *StInst = StoreInst;
 516     if (StorePrevNonDbgInstr == LoadInst)
 517       StInst = LoadInst;
 518     getBaseOperand(StInst->getPrevNode()).setIsKill(StoreBase.isKill());
 519   }
 520 }
 521
 522 bool X86AvoidSFBPass::alias(const MachineMemOperand &Op1,
 523                             const MachineMemOperand &Op2) const {
 524   if (!Op1.getValue() || !Op2.getValue())
 525     return true;
 526
 527   int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset());
 528   int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset;
 529   int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset;
 530
 531   AliasResult AAResult =
 532       AA->alias(MemoryLocation(Op1.getValue(), Overlapa, Op1.getAAInfo()),
 533                 MemoryLocation(Op2.getValue(), Overlapb, Op2.getAAInfo()));
 534   return AAResult != NoAlias;
 535 }
 536
 537 void X86AvoidSFBPass::findPotentiallylBlockedCopies(MachineFunction &MF) {
 538   for (auto &MBB : MF)
 539     for (auto &MI : MBB) {
 540       if (!isPotentialBlockedMemCpyLd(MI.getOpcode()))
 541         continue;
 542       int DefVR = MI.getOperand(0).getReg();
 543       if (!MRI->hasOneNonDBGUse(DefVR))
 544         continue;
 545       for (auto UI = MRI->use_nodbg_begin(DefVR), UE = MRI->use_nodbg_end();
 546            UI != UE;) {
 547         MachineOperand &StoreMO = *UI++;
 548         MachineInstr &StoreMI = *StoreMO.getParent();
 549         // Skip cases where the memcpy may overlap.
 550         if (StoreMI.getParent() == MI.getParent() &&
 551             isPotentialBlockedMemCpyPair(MI.getOpcode(), StoreMI.getOpcode()) &&
 552             isRelevantAddressingMode(&MI) &&
 553             isRelevantAddressingMode(&StoreMI)) {
 554           assert(MI.hasOneMemOperand() &&
 555                  "Expected one memory operand for load instruction");
 556           assert(StoreMI.hasOneMemOperand() &&
 557                  "Expected one memory operand for store instruction");
 558           if (!alias(**MI.memoperands_begin(), **StoreMI.memoperands_begin()))
 559             BlockedLoadsStoresPairs.push_back(std::make_pair(&MI, &StoreMI));
 560         }
 561       }
 562     }
 563 }
 564
 565 unsigned X86AvoidSFBPass::getRegSizeInBytes(MachineInstr *LoadInst) {
 566   auto TRC = TII->getRegClass(TII->get(LoadInst->getOpcode()), 0, TRI,
 567                               *LoadInst->getParent()->getParent());
 568   return TRI->getRegSizeInBits(*TRC) / 8;
 569 }
 570
 571 void X86AvoidSFBPass::breakBlockedCopies(
 572     MachineInstr *LoadInst, MachineInstr *StoreInst,
 573     const DisplacementSizeMap &BlockingStoresDispSizeMap) {
 574   int64_t LdDispImm = getDispOperand(LoadInst).getImm();
 575   int64_t StDispImm = getDispOperand(StoreInst).getImm();
 576   int64_t LMMOffset = 0;
 577   int64_t SMMOffset = 0;
 578
 579   int64_t LdDisp1 = LdDispImm;
 580   int64_t LdDisp2 = 0;
 581   int64_t StDisp1 = StDispImm;
 582   int64_t StDisp2 = 0;
 583   unsigned Size1 = 0;
 584   unsigned Size2 = 0;
 585   int64_t LdStDelta = StDispImm - LdDispImm;
 586
 587   for (auto DispSizePair : BlockingStoresDispSizeMap) {
 588     LdDisp2 = DispSizePair.first;
 589     StDisp2 = DispSizePair.first + LdStDelta;
 590     Size2 = DispSizePair.second;
 591     // Avoid copying overlapping areas.
 592     if (LdDisp2 < LdDisp1) {
 593       int OverlapDelta = LdDisp1 - LdDisp2;
 594       LdDisp2 += OverlapDelta;
 595       StDisp2 += OverlapDelta;
 596       Size2 -= OverlapDelta;
 597     }
 598     Size1 = LdDisp2 - LdDisp1;
 599
 600     // Build a copy for the point until the current blocking store's
 601     // displacement.
 602     buildCopies(Size1, LoadInst, LdDisp1, StoreInst, StDisp1, LMMOffset,
 603                 SMMOffset);
 604     // Build a copy for the current blocking store.
 605     buildCopies(Size2, LoadInst, LdDisp2, StoreInst, StDisp2, LMMOffset + Size1,
 606                 SMMOffset + Size1);
 607     LdDisp1 = LdDisp2 + Size2;
 608     StDisp1 = StDisp2 + Size2;
 609     LMMOffset += Size1 + Size2;
 610     SMMOffset += Size1 + Size2;
 611   }
 612   unsigned Size3 = (LdDispImm + getRegSizeInBytes(LoadInst)) - LdDisp1;
 613   buildCopies(Size3, LoadInst, LdDisp1, StoreInst, StDisp1, LMMOffset,
 614               LMMOffset);
 615 }
 616
 617 static bool hasSameBaseOpValue(MachineInstr *LoadInst,
 618                                MachineInstr *StoreInst) {
 619   MachineOperand &LoadBase = getBaseOperand(LoadInst);
 620   MachineOperand &StoreBase = getBaseOperand(StoreInst);
 621   if (LoadBase.isReg() != StoreBase.isReg())
 622     return false;
 623   if (LoadBase.isReg())
 624     return LoadBase.getReg() == StoreBase.getReg();
 625   return LoadBase.getIndex() == StoreBase.getIndex();
 626 }
 627
 628 static bool isBlockingStore(int64_t LoadDispImm, unsigned LoadSize,
 629                             int64_t StoreDispImm, unsigned StoreSize) {
 630   return ((StoreDispImm >= LoadDispImm) &&
 631           (StoreDispImm <= LoadDispImm + (LoadSize - StoreSize)));
 632 }
 633
 634 // Keep track of all stores blocking a load
 635 static void
 636 updateBlockingStoresDispSizeMap(DisplacementSizeMap &BlockingStoresDispSizeMap,
 637                                 int64_t DispImm, unsigned Size) {
 638   if (BlockingStoresDispSizeMap.count(DispImm)) {
 639     // Choose the smallest blocking store starting at this displacement.
 640     if (BlockingStoresDispSizeMap[DispImm] > Size)
 641       BlockingStoresDispSizeMap[DispImm] = Size;
 642
 643   } else
 644     BlockingStoresDispSizeMap[DispImm] = Size;
 645 }
 646
 647 // Remove blocking stores contained in each other.
 648 static void
 649 removeRedundantBlockingStores(DisplacementSizeMap &BlockingStoresDispSizeMap) {
 650   if (BlockingStoresDispSizeMap.size() <= 1)
 651     return;
 652
 653   SmallVector<std::pair<int64_t, unsigned>, 0> DispSizeStack;
 654   for (auto DispSizePair : BlockingStoresDispSizeMap) {
 655     int64_t CurrDisp = DispSizePair.first;
 656     unsigned CurrSize = DispSizePair.second;
 657     while (DispSizeStack.size()) {
 658       int64_t PrevDisp = DispSizeStack.back().first;
 659       unsigned PrevSize = DispSizeStack.back().second;
 660       if (CurrDisp + CurrSize > PrevDisp + PrevSize)
 661         break;
 662       DispSizeStack.pop_back();
 663     }
 664     DispSizeStack.push_back(DispSizePair);
 665   }
 666   BlockingStoresDispSizeMap.clear();
 667   for (auto Disp : DispSizeStack)
 668     BlockingStoresDispSizeMap.insert(Disp);
 669 }
 670
 671 bool X86AvoidSFBPass::runOnMachineFunction(MachineFunction &MF) {
 672   bool Changed = false;
 673
 674   if (DisableX86AvoidStoreForwardBlocks || skipFunction(MF.getFunction()) ||
 675       !MF.getSubtarget<X86Subtarget>().is64Bit())
 676     return false;
 677
 678   MRI = &MF.getRegInfo();
 679   assert(MRI->isSSA() && "Expected MIR to be in SSA form");
 680   TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
 681   TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo();
 682   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 683   LLVM_DEBUG(dbgs() << "Start X86AvoidStoreForwardBlocks\n";);
 684   // Look for a load then a store to XMM/YMM which look like a memcpy
 685   findPotentiallylBlockedCopies(MF);
 686
 687   for (auto LoadStoreInstPair : BlockedLoadsStoresPairs) {
 688     MachineInstr *LoadInst = LoadStoreInstPair.first;
 689     int64_t LdDispImm = getDispOperand(LoadInst).getImm();
 690     DisplacementSizeMap BlockingStoresDispSizeMap;
 691
 692     SmallVector<MachineInstr *, 2> PotentialBlockers =
 693         findPotentialBlockers(LoadInst);
 694     for (auto PBInst : PotentialBlockers) {
 695       if (!isPotentialBlockingStoreInst(PBInst->getOpcode(),
 696                                         LoadInst->getOpcode()) ||
 697           !isRelevantAddressingMode(PBInst))
 698         continue;
 699       int64_t PBstDispImm = getDispOperand(PBInst).getImm();
 700       assert(PBInst->hasOneMemOperand() && "Expected One Memory Operand");
 701       unsigned PBstSize = (*PBInst->memoperands_begin())->getSize();
 702       // This check doesn't cover all cases, but it will suffice for now.
 703       // TODO: take branch probability into consideration, if the blocking
 704       // store is in an unreached block, breaking the memcopy could lose
 705       // performance.
 706       if (hasSameBaseOpValue(LoadInst, PBInst) &&
 707           isBlockingStore(LdDispImm, getRegSizeInBytes(LoadInst), PBstDispImm,
 708                           PBstSize))
 709         updateBlockingStoresDispSizeMap(BlockingStoresDispSizeMap, PBstDispImm,
 710                                         PBstSize);
 711     }
 712
 713     if (BlockingStoresDispSizeMap.empty())
 714       continue;
 715
 716     // We found a store forward block, break the memcpy's load and store
 717     // into smaller copies such that each smaller store that was causing
 718     // a store block would now be copied separately.
 719     MachineInstr *StoreInst = LoadStoreInstPair.second;
 720     LLVM_DEBUG(dbgs() << "Blocked load and store instructions: \n");
 721     LLVM_DEBUG(LoadInst->dump());
 722     LLVM_DEBUG(StoreInst->dump());
 723     LLVM_DEBUG(dbgs() << "Replaced with:\n");
 724     removeRedundantBlockingStores(BlockingStoresDispSizeMap);
 725     breakBlockedCopies(LoadInst, StoreInst, BlockingStoresDispSizeMap);
 726     updateKillStatus(LoadInst, StoreInst);
 727     ForRemoval.push_back(LoadInst);
 728     ForRemoval.push_back(StoreInst);
 729   }
 730   for (auto RemovedInst : ForRemoval) {
 731     RemovedInst->eraseFromParent();
 732   }
 733   ForRemoval.clear();
 734   BlockedLoadsStoresPairs.clear();
 735   LLVM_DEBUG(dbgs() << "End X86AvoidStoreForwardBlocks\n";);
 736
 737   return Changed;
 738 }