X86AvoidStoreForwardingBlocks.cpp revision 360784 
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
52using namespace llvm;
53
54#define DEBUG_TYPE "x86-avoid-SFB"
55
56static cl::opt<bool> DisableX86AvoidStoreForwardBlocks(
57    "x86-disable-avoid-SFB", cl::Hidden,
58    cl::desc("X86: Disable Store Forwarding Blocks fixup."), cl::init(false));
59
60static cl::opt<unsigned> X86AvoidSFBInspectionLimit(
61    "x86-sfb-inspection-limit",
62    cl::desc("X86: Number of instructions backward to "
63             "inspect for store forwarding blocks."),
64    cl::init(20), cl::Hidden);
65
66namespace {
67
68using DisplacementSizeMap = std::map<int64_t, unsigned>;
69
70class X86AvoidSFBPass : public MachineFunctionPass {
71public:
72  static char ID;
73  X86AvoidSFBPass() : MachineFunctionPass(ID) { }
74
75  StringRef getPassName() const override {
76    return "X86 Avoid Store Forwarding Blocks";
77  }
78
79  bool runOnMachineFunction(MachineFunction &MF) override;
80
81  void getAnalysisUsage(AnalysisUsage &AU) const override {
82    MachineFunctionPass::getAnalysisUsage(AU);
83    AU.addRequired<AAResultsWrapperPass>();
84  }
85
86private:
87  MachineRegisterInfo *MRI = nullptr;
88  const X86InstrInfo *TII = nullptr;
89  const X86RegisterInfo *TRI = nullptr;
90  SmallVector<std::pair<MachineInstr *, MachineInstr *>, 2>
91      BlockedLoadsStoresPairs;
92  SmallVector<MachineInstr *, 2> ForRemoval;
93  AliasAnalysis *AA = nullptr;
94
95  /// Returns couples of Load then Store to memory which 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
120char X86AvoidSFBPass::ID = 0;
121
122INITIALIZE_PASS_BEGIN(X86AvoidSFBPass, DEBUG_TYPE, "Machine code sinking",
123                      false, false)
124INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
125INITIALIZE_PASS_END(X86AvoidSFBPass, DEBUG_TYPE, "Machine code sinking", false,
126                    false)
127
128FunctionPass *llvm::createX86AvoidStoreForwardingBlocks() {
129  return new X86AvoidSFBPass();
130}
131
132static bool isXMMLoadOpcode(unsigned Opcode) {
133  return Opcode == X86::MOVUPSrm || Opcode == X86::MOVAPSrm ||
134         Opcode == X86::VMOVUPSrm || Opcode == X86::VMOVAPSrm ||
135         Opcode == X86::VMOVUPDrm || Opcode == X86::VMOVAPDrm ||
136         Opcode == X86::VMOVDQUrm || Opcode == X86::VMOVDQArm ||
137         Opcode == X86::VMOVUPSZ128rm || Opcode == X86::VMOVAPSZ128rm ||
138         Opcode == X86::VMOVUPDZ128rm || Opcode == X86::VMOVAPDZ128rm ||
139         Opcode == X86::VMOVDQU64Z128rm || Opcode == X86::VMOVDQA64Z128rm ||
140         Opcode == X86::VMOVDQU32Z128rm || Opcode == X86::VMOVDQA32Z128rm;
141}
142static bool isYMMLoadOpcode(unsigned Opcode) {
143  return Opcode == X86::VMOVUPSYrm || Opcode == X86::VMOVAPSYrm ||
144         Opcode == X86::VMOVUPDYrm || Opcode == X86::VMOVAPDYrm ||
145         Opcode == X86::VMOVDQUYrm || Opcode == X86::VMOVDQAYrm ||
146         Opcode == X86::VMOVUPSZ256rm || Opcode == X86::VMOVAPSZ256rm ||
147         Opcode == X86::VMOVUPDZ256rm || Opcode == X86::VMOVAPDZ256rm ||
148         Opcode == X86::VMOVDQU64Z256rm || Opcode == X86::VMOVDQA64Z256rm ||
149         Opcode == X86::VMOVDQU32Z256rm || Opcode == X86::VMOVDQA32Z256rm;
150}
151
152static bool isPotentialBlockedMemCpyLd(unsigned Opcode) {
153  return isXMMLoadOpcode(Opcode) || isYMMLoadOpcode(Opcode);
154}
155
156static bool isPotentialBlockedMemCpyPair(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
208static 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
226static const int MOV128SZ = 16;
227static const int MOV64SZ = 8;
228static const int MOV32SZ = 4;
229static const int MOV16SZ = 2;
230static const int MOV8SZ = 1;
231
232static unsigned getYMMtoXMMLoadOpcode(unsigned LoadOpcode) {
233  switch (LoadOpcode) {
234  case X86::VMOVUPSYrm:
235  case X86::VMOVAPSYrm:
236    return X86::VMOVUPSrm;
237  case X86::VMOVUPDYrm:
238  case X86::VMOVAPDYrm:
239    return X86::VMOVUPDrm;
240  case X86::VMOVDQUYrm:
241  case X86::VMOVDQAYrm:
242    return X86::VMOVDQUrm;
243  case X86::VMOVUPSZ256rm:
244  case X86::VMOVAPSZ256rm:
245    return X86::VMOVUPSZ128rm;
246  case X86::VMOVUPDZ256rm:
247  case X86::VMOVAPDZ256rm:
248    return X86::VMOVUPDZ128rm;
249  case X86::VMOVDQU64Z256rm:
250  case X86::VMOVDQA64Z256rm:
251    return X86::VMOVDQU64Z128rm;
252  case X86::VMOVDQU32Z256rm:
253  case X86::VMOVDQA32Z256rm:
254    return X86::VMOVDQU32Z128rm;
255  default:
256    llvm_unreachable("Unexpected Load Instruction Opcode");
257  }
258  return 0;
259}
260
261static unsigned getYMMtoXMMStoreOpcode(unsigned StoreOpcode) {
262  switch (StoreOpcode) {
263  case X86::VMOVUPSYmr:
264  case X86::VMOVAPSYmr:
265    return X86::VMOVUPSmr;
266  case X86::VMOVUPDYmr:
267  case X86::VMOVAPDYmr:
268    return X86::VMOVUPDmr;
269  case X86::VMOVDQUYmr:
270  case X86::VMOVDQAYmr:
271    return X86::VMOVDQUmr;
272  case X86::VMOVUPSZ256mr:
273  case X86::VMOVAPSZ256mr:
274    return X86::VMOVUPSZ128mr;
275  case X86::VMOVUPDZ256mr:
276  case X86::VMOVAPDZ256mr:
277    return X86::VMOVUPDZ128mr;
278  case X86::VMOVDQU64Z256mr:
279  case X86::VMOVDQA64Z256mr:
280    return X86::VMOVDQU64Z128mr;
281  case X86::VMOVDQU32Z256mr:
282  case X86::VMOVDQA32Z256mr:
283    return X86::VMOVDQU32Z128mr;
284  default:
285    llvm_unreachable("Unexpected Load Instruction Opcode");
286  }
287  return 0;
288}
289
290static int getAddrOffset(MachineInstr *MI) {
291  const MCInstrDesc &Descl = MI->getDesc();
292  int AddrOffset = X86II::getMemoryOperandNo(Descl.TSFlags);
293  assert(AddrOffset != -1 && "Expected Memory Operand");
294  AddrOffset += X86II::getOperandBias(Descl);
295  return AddrOffset;
296}
297
298static MachineOperand &getBaseOperand(MachineInstr *MI) {
299  int AddrOffset = getAddrOffset(MI);
300  return MI->getOperand(AddrOffset + X86::AddrBaseReg);
301}
302
303static MachineOperand &getDispOperand(MachineInstr *MI) {
304  int AddrOffset = getAddrOffset(MI);
305  return MI->getOperand(AddrOffset + X86::AddrDisp);
306}
307
308// Relevant addressing modes contain only base register and immediate
309// displacement or frameindex and immediate displacement.
310// TODO: Consider expanding to other addressing modes in the future
311static 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.
337static SmallVector<MachineInstr *, 2>
338findPotentialBlockers(MachineInstr *LoadInst) {
339  SmallVector<MachineInstr *, 2> PotentialBlockers;
340  unsigned BlockCount = 0;
341  const unsigned InspectionLimit = X86AvoidSFBInspectionLimit;
342  for (auto PBInst = std::next(MachineBasicBlock::reverse_iterator(LoadInst)),
343            E = LoadInst->getParent()->rend();
344       PBInst != E; ++PBInst) {
345    if (PBInst->isMetaInstruction())
346      continue;
347    BlockCount++;
348    if (BlockCount >= InspectionLimit)
349      break;
350    MachineInstr &MI = *PBInst;
351    if (MI.getDesc().isCall())
352      return PotentialBlockers;
353    PotentialBlockers.push_back(&MI);
354  }
355  // If we didn't get to the instructions limit try predecessing blocks.
356  // Ideally we should traverse the predecessor blocks in depth with 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
384void 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
436void 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
498static 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
522bool 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
537void 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
565unsigned 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
571void 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
617static 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
628static 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
635static void
636updateBlockingStoresDispSizeMap(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.
648static void
649removeRedundantBlockingStores(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
671bool 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}
739