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

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