LLVM  10.0.0svn
X86AvoidStoreForwardingBlocks.cpp
Go to the documentation of this file.
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"
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 
56  "x86-disable-avoid-SFB", cl::Hidden,
57  cl::desc("X86: Disable Store Forwarding Blocks fixup."), cl::init(false));
58 
60  "x86-sfb-inspection-limit",
61  cl::desc("X86: Number of instructions backward to "
62  "inspect for store forwarding blocks."),
63  cl::init(20), cl::Hidden);
64 
65 namespace {
66 
67 using DisplacementSizeMap = std::map<int64_t, unsigned>;
68 
69 class X86AvoidSFBPass : public MachineFunctionPass {
70 public:
71  static char ID;
72  X86AvoidSFBPass() : MachineFunctionPass(ID) { }
73 
74  StringRef getPassName() const override {
75  return "X86 Avoid Store Forwarding Blocks";
76  }
77 
78  bool runOnMachineFunction(MachineFunction &MF) override;
79 
80  void getAnalysisUsage(AnalysisUsage &AU) const override {
83  }
84 
85 private:
87  const X86InstrInfo *TII;
88  const X86RegisterInfo *TRI;
90  BlockedLoadsStoresPairs;
92  AliasAnalysis *AA;
93 
94  /// Returns couples of Load then Store to memory which look
95  /// like a memcpy.
96  void findPotentiallylBlockedCopies(MachineFunction &MF);
97  /// Break the memcpy's load and store into smaller copies
98  /// such that each memory load that was blocked by a smaller store
99  /// would now be copied separately.
100  void breakBlockedCopies(MachineInstr *LoadInst, MachineInstr *StoreInst,
101  const DisplacementSizeMap &BlockingStoresDispSizeMap);
102  /// Break a copy of size Size to smaller copies.
103  void buildCopies(int Size, MachineInstr *LoadInst, int64_t LdDispImm,
104  MachineInstr *StoreInst, int64_t StDispImm,
105  int64_t LMMOffset, int64_t SMMOffset);
106 
107  void buildCopy(MachineInstr *LoadInst, unsigned NLoadOpcode, int64_t LoadDisp,
108  MachineInstr *StoreInst, unsigned NStoreOpcode,
109  int64_t StoreDisp, unsigned Size, int64_t LMMOffset,
110  int64_t SMMOffset);
111 
112  bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2) const;
113 
114  unsigned getRegSizeInBytes(MachineInstr *Inst);
115 };
116 
117 } // end anonymous namespace
118 
119 char X86AvoidSFBPass::ID = 0;
120 
121 INITIALIZE_PASS_BEGIN(X86AvoidSFBPass, DEBUG_TYPE, "Machine code sinking",
122  false, false)
125  false)
126 
128  return new X86AvoidSFBPass();
129 }
130 
131 static bool isXMMLoadOpcode(unsigned Opcode) {
132  return Opcode == X86::MOVUPSrm || Opcode == X86::MOVAPSrm ||
133  Opcode == X86::VMOVUPSrm || Opcode == X86::VMOVAPSrm ||
134  Opcode == X86::VMOVUPDrm || Opcode == X86::VMOVAPDrm ||
135  Opcode == X86::VMOVDQUrm || Opcode == X86::VMOVDQArm ||
136  Opcode == X86::VMOVUPSZ128rm || Opcode == X86::VMOVAPSZ128rm ||
137  Opcode == X86::VMOVUPDZ128rm || Opcode == X86::VMOVAPDZ128rm ||
138  Opcode == X86::VMOVDQU64Z128rm || Opcode == X86::VMOVDQA64Z128rm ||
139  Opcode == X86::VMOVDQU32Z128rm || Opcode == X86::VMOVDQA32Z128rm;
140 }
141 static bool isYMMLoadOpcode(unsigned Opcode) {
142  return Opcode == X86::VMOVUPSYrm || Opcode == X86::VMOVAPSYrm ||
143  Opcode == X86::VMOVUPDYrm || Opcode == X86::VMOVAPDYrm ||
144  Opcode == X86::VMOVDQUYrm || Opcode == X86::VMOVDQAYrm ||
145  Opcode == X86::VMOVUPSZ256rm || Opcode == X86::VMOVAPSZ256rm ||
146  Opcode == X86::VMOVUPDZ256rm || Opcode == X86::VMOVAPDZ256rm ||
147  Opcode == X86::VMOVDQU64Z256rm || Opcode == X86::VMOVDQA64Z256rm ||
148  Opcode == X86::VMOVDQU32Z256rm || Opcode == X86::VMOVDQA32Z256rm;
149 }
150 
151 static bool isPotentialBlockedMemCpyLd(unsigned Opcode) {
152  return isXMMLoadOpcode(Opcode) || isYMMLoadOpcode(Opcode);
153 }
154 
155 static bool isPotentialBlockedMemCpyPair(int LdOpcode, int StOpcode) {
156  switch (LdOpcode) {
157  case X86::MOVUPSrm:
158  case X86::MOVAPSrm:
159  return StOpcode == X86::MOVUPSmr || StOpcode == X86::MOVAPSmr;
160  case X86::VMOVUPSrm:
161  case X86::VMOVAPSrm:
162  return StOpcode == X86::VMOVUPSmr || StOpcode == X86::VMOVAPSmr;
163  case X86::VMOVUPDrm:
164  case X86::VMOVAPDrm:
165  return StOpcode == X86::VMOVUPDmr || StOpcode == X86::VMOVAPDmr;
166  case X86::VMOVDQUrm:
167  case X86::VMOVDQArm:
168  return StOpcode == X86::VMOVDQUmr || StOpcode == X86::VMOVDQAmr;
169  case X86::VMOVUPSZ128rm:
170  case X86::VMOVAPSZ128rm:
171  return StOpcode == X86::VMOVUPSZ128mr || StOpcode == X86::VMOVAPSZ128mr;
172  case X86::VMOVUPDZ128rm:
173  case X86::VMOVAPDZ128rm:
174  return StOpcode == X86::VMOVUPDZ128mr || StOpcode == X86::VMOVAPDZ128mr;
175  case X86::VMOVUPSYrm:
176  case X86::VMOVAPSYrm:
177  return StOpcode == X86::VMOVUPSYmr || StOpcode == X86::VMOVAPSYmr;
178  case X86::VMOVUPDYrm:
179  case X86::VMOVAPDYrm:
180  return StOpcode == X86::VMOVUPDYmr || StOpcode == X86::VMOVAPDYmr;
181  case X86::VMOVDQUYrm:
182  case X86::VMOVDQAYrm:
183  return StOpcode == X86::VMOVDQUYmr || StOpcode == X86::VMOVDQAYmr;
184  case X86::VMOVUPSZ256rm:
185  case X86::VMOVAPSZ256rm:
186  return StOpcode == X86::VMOVUPSZ256mr || StOpcode == X86::VMOVAPSZ256mr;
187  case X86::VMOVUPDZ256rm:
188  case X86::VMOVAPDZ256rm:
189  return StOpcode == X86::VMOVUPDZ256mr || StOpcode == X86::VMOVAPDZ256mr;
190  case X86::VMOVDQU64Z128rm:
191  case X86::VMOVDQA64Z128rm:
192  return StOpcode == X86::VMOVDQU64Z128mr || StOpcode == X86::VMOVDQA64Z128mr;
193  case X86::VMOVDQU32Z128rm:
194  case X86::VMOVDQA32Z128rm:
195  return StOpcode == X86::VMOVDQU32Z128mr || StOpcode == X86::VMOVDQA32Z128mr;
196  case X86::VMOVDQU64Z256rm:
197  case X86::VMOVDQA64Z256rm:
198  return StOpcode == X86::VMOVDQU64Z256mr || StOpcode == X86::VMOVDQA64Z256mr;
199  case X86::VMOVDQU32Z256rm:
200  case X86::VMOVDQA32Z256rm:
201  return StOpcode == X86::VMOVDQU32Z256mr || StOpcode == X86::VMOVDQA32Z256mr;
202  default:
203  return false;
204  }
205 }
206 
207 static bool isPotentialBlockingStoreInst(int Opcode, int LoadOpcode) {
208  bool PBlock = false;
209  PBlock |= Opcode == X86::MOV64mr || Opcode == X86::MOV64mi32 ||
210  Opcode == X86::MOV32mr || Opcode == X86::MOV32mi ||
211  Opcode == X86::MOV16mr || Opcode == X86::MOV16mi ||
212  Opcode == X86::MOV8mr || Opcode == X86::MOV8mi;
213  if (isYMMLoadOpcode(LoadOpcode))
214  PBlock |= Opcode == X86::VMOVUPSmr || Opcode == X86::VMOVAPSmr ||
215  Opcode == X86::VMOVUPDmr || Opcode == X86::VMOVAPDmr ||
216  Opcode == X86::VMOVDQUmr || Opcode == X86::VMOVDQAmr ||
217  Opcode == X86::VMOVUPSZ128mr || Opcode == X86::VMOVAPSZ128mr ||
218  Opcode == X86::VMOVUPDZ128mr || Opcode == X86::VMOVAPDZ128mr ||
219  Opcode == X86::VMOVDQU64Z128mr ||
220  Opcode == X86::VMOVDQA64Z128mr ||
221  Opcode == X86::VMOVDQU32Z128mr || Opcode == X86::VMOVDQA32Z128mr;
222  return PBlock;
223 }
224 
225 static const int MOV128SZ = 16;
226 static const int MOV64SZ = 8;
227 static const int MOV32SZ = 4;
228 static const int MOV16SZ = 2;
229 static const int MOV8SZ = 1;
230 
231 static unsigned getYMMtoXMMLoadOpcode(unsigned LoadOpcode) {
232  switch (LoadOpcode) {
233  case X86::VMOVUPSYrm:
234  case X86::VMOVAPSYrm:
235  return X86::VMOVUPSrm;
236  case X86::VMOVUPDYrm:
237  case X86::VMOVAPDYrm:
238  return X86::VMOVUPDrm;
239  case X86::VMOVDQUYrm:
240  case X86::VMOVDQAYrm:
241  return X86::VMOVDQUrm;
242  case X86::VMOVUPSZ256rm:
243  case X86::VMOVAPSZ256rm:
244  return X86::VMOVUPSZ128rm;
245  case X86::VMOVUPDZ256rm:
246  case X86::VMOVAPDZ256rm:
247  return X86::VMOVUPDZ128rm;
248  case X86::VMOVDQU64Z256rm:
249  case X86::VMOVDQA64Z256rm:
250  return X86::VMOVDQU64Z128rm;
251  case X86::VMOVDQU32Z256rm:
252  case X86::VMOVDQA32Z256rm:
253  return X86::VMOVDQU32Z128rm;
254  default:
255  llvm_unreachable("Unexpected Load Instruction Opcode");
256  }
257  return 0;
258 }
259 
260 static unsigned getYMMtoXMMStoreOpcode(unsigned StoreOpcode) {
261  switch (StoreOpcode) {
262  case X86::VMOVUPSYmr:
263  case X86::VMOVAPSYmr:
264  return X86::VMOVUPSmr;
265  case X86::VMOVUPDYmr:
266  case X86::VMOVAPDYmr:
267  return X86::VMOVUPDmr;
268  case X86::VMOVDQUYmr:
269  case X86::VMOVDQAYmr:
270  return X86::VMOVDQUmr;
271  case X86::VMOVUPSZ256mr:
272  case X86::VMOVAPSZ256mr:
273  return X86::VMOVUPSZ128mr;
274  case X86::VMOVUPDZ256mr:
275  case X86::VMOVAPDZ256mr:
276  return X86::VMOVUPDZ128mr;
277  case X86::VMOVDQU64Z256mr:
278  case X86::VMOVDQA64Z256mr:
279  return X86::VMOVDQU64Z128mr;
280  case X86::VMOVDQU32Z256mr:
281  case X86::VMOVDQA32Z256mr:
282  return X86::VMOVDQU32Z128mr;
283  default:
284  llvm_unreachable("Unexpected Load Instruction Opcode");
285  }
286  return 0;
287 }
288 
290  const MCInstrDesc &Descl = MI->getDesc();
291  int AddrOffset = X86II::getMemoryOperandNo(Descl.TSFlags);
292  assert(AddrOffset != -1 && "Expected Memory Operand");
293  AddrOffset += X86II::getOperandBias(Descl);
294  return AddrOffset;
295 }
296 
298  int AddrOffset = getAddrOffset(MI);
299  return MI->getOperand(AddrOffset + X86::AddrBaseReg);
300 }
301 
303  int AddrOffset = getAddrOffset(MI);
304  return MI->getOperand(AddrOffset + X86::AddrDisp);
305 }
306 
307 // Relevant addressing modes contain only base register and immediate
308 // displacement or frameindex and immediate displacement.
309 // TODO: Consider expanding to other addressing modes in the future
311  int AddrOffset = getAddrOffset(MI);
313  MachineOperand &Disp = getDispOperand(MI);
314  MachineOperand &Scale = MI->getOperand(AddrOffset + X86::AddrScaleAmt);
315  MachineOperand &Index = MI->getOperand(AddrOffset + X86::AddrIndexReg);
316  MachineOperand &Segment = MI->getOperand(AddrOffset + X86::AddrSegmentReg);
317 
318  if (!((Base.isReg() && Base.getReg() != X86::NoRegister) || Base.isFI()))
319  return false;
320  if (!Disp.isImm())
321  return false;
322  if (Scale.getImm() != 1)
323  return false;
324  if (!(Index.isReg() && Index.getReg() == X86::NoRegister))
325  return false;
326  if (!(Segment.isReg() && Segment.getReg() == X86::NoRegister))
327  return false;
328  return true;
329 }
330 
331 // Collect potentially blocking stores.
332 // Limit the number of instructions backwards we want to inspect
333 // since the effect of store block won't be visible if the store
334 // and load instructions have enough instructions in between to
335 // keep the core busy.
338  SmallVector<MachineInstr *, 2> PotentialBlockers;
339  unsigned BlockCount = 0;
340  const unsigned InspectionLimit = X86AvoidSFBInspectionLimit;
341  for (auto PBInst = std::next(MachineBasicBlock::reverse_iterator(LoadInst)),
342  E = LoadInst->getParent()->rend();
343  PBInst != E; ++PBInst) {
344  if (PBInst->isMetaInstruction())
345  continue;
346  BlockCount++;
347  if (BlockCount >= InspectionLimit)
348  break;
349  MachineInstr &MI = *PBInst;
350  if (MI.getDesc().isCall())
351  return PotentialBlockers;
352  PotentialBlockers.push_back(&MI);
353  }
354  // If we didn't get to the instructions limit try predecessing blocks.
355  // Ideally we should traverse the predecessor blocks in depth with some
356  // coloring algorithm, but for now let's just look at the first order
357  // predecessors.
358  if (BlockCount < InspectionLimit) {
359  MachineBasicBlock *MBB = LoadInst->getParent();
360  int LimitLeft = InspectionLimit - BlockCount;
362  PE = MBB->pred_end();
363  PB != PE; ++PB) {
364  MachineBasicBlock *PMBB = *PB;
365  int PredCount = 0;
366  for (MachineBasicBlock::reverse_iterator PBInst = PMBB->rbegin(),
367  PME = PMBB->rend();
368  PBInst != PME; ++PBInst) {
369  if (PBInst->isMetaInstruction())
370  continue;
371  PredCount++;
372  if (PredCount >= LimitLeft)
373  break;
374  if (PBInst->getDesc().isCall())
375  break;
376  PotentialBlockers.push_back(&*PBInst);
377  }
378  }
379  }
380  return PotentialBlockers;
381 }
382 
383 void X86AvoidSFBPass::buildCopy(MachineInstr *LoadInst, unsigned NLoadOpcode,
384  int64_t LoadDisp, MachineInstr *StoreInst,
385  unsigned NStoreOpcode, int64_t StoreDisp,
386  unsigned Size, int64_t LMMOffset,
387  int64_t SMMOffset) {
388  MachineOperand &LoadBase = getBaseOperand(LoadInst);
389  MachineOperand &StoreBase = getBaseOperand(StoreInst);
390  MachineBasicBlock *MBB = LoadInst->getParent();
391  MachineMemOperand *LMMO = *LoadInst->memoperands_begin();
392  MachineMemOperand *SMMO = *StoreInst->memoperands_begin();
393 
394  Register Reg1 = MRI->createVirtualRegister(
395  TII->getRegClass(TII->get(NLoadOpcode), 0, TRI, *(MBB->getParent())));
396  MachineInstr *NewLoad =
397  BuildMI(*MBB, LoadInst, LoadInst->getDebugLoc(), TII->get(NLoadOpcode),
398  Reg1)
399  .add(LoadBase)
400  .addImm(1)
401  .addReg(X86::NoRegister)
402  .addImm(LoadDisp)
403  .addReg(X86::NoRegister)
404  .addMemOperand(
405  MBB->getParent()->getMachineMemOperand(LMMO, LMMOffset, Size));
406  if (LoadBase.isReg())
407  getBaseOperand(NewLoad).setIsKill(false);
408  LLVM_DEBUG(NewLoad->dump());
409  // If the load and store are consecutive, use the loadInst location to
410  // reduce register pressure.
411  MachineInstr *StInst = StoreInst;
412  auto PrevInstrIt = skipDebugInstructionsBackward(
413  std::prev(MachineBasicBlock::instr_iterator(StoreInst)),
414  MBB->instr_begin());
415  if (PrevInstrIt.getNodePtr() == LoadInst)
416  StInst = LoadInst;
417  MachineInstr *NewStore =
418  BuildMI(*MBB, StInst, StInst->getDebugLoc(), TII->get(NStoreOpcode))
419  .add(StoreBase)
420  .addImm(1)
421  .addReg(X86::NoRegister)
422  .addImm(StoreDisp)
423  .addReg(X86::NoRegister)
424  .addReg(Reg1)
425  .addMemOperand(
426  MBB->getParent()->getMachineMemOperand(SMMO, SMMOffset, Size));
427  if (StoreBase.isReg())
428  getBaseOperand(NewStore).setIsKill(false);
429  MachineOperand &StoreSrcVReg = StoreInst->getOperand(X86::AddrNumOperands);
430  assert(StoreSrcVReg.isReg() && "Expected virtual register");
431  NewStore->getOperand(X86::AddrNumOperands).setIsKill(StoreSrcVReg.isKill());
432  LLVM_DEBUG(NewStore->dump());
433 }
434 
435 void X86AvoidSFBPass::buildCopies(int Size, MachineInstr *LoadInst,
436  int64_t LdDispImm, MachineInstr *StoreInst,
437  int64_t StDispImm, int64_t LMMOffset,
438  int64_t SMMOffset) {
439  int LdDisp = LdDispImm;
440  int StDisp = StDispImm;
441  while (Size > 0) {
442  if ((Size - MOV128SZ >= 0) && isYMMLoadOpcode(LoadInst->getOpcode())) {
443  Size = Size - MOV128SZ;
444  buildCopy(LoadInst, getYMMtoXMMLoadOpcode(LoadInst->getOpcode()), LdDisp,
445  StoreInst, getYMMtoXMMStoreOpcode(StoreInst->getOpcode()),
446  StDisp, MOV128SZ, LMMOffset, SMMOffset);
447  LdDisp += MOV128SZ;
448  StDisp += MOV128SZ;
449  LMMOffset += MOV128SZ;
450  SMMOffset += MOV128SZ;
451  continue;
452  }
453  if (Size - MOV64SZ >= 0) {
454  Size = Size - MOV64SZ;
455  buildCopy(LoadInst, X86::MOV64rm, LdDisp, StoreInst, X86::MOV64mr, StDisp,
456  MOV64SZ, LMMOffset, SMMOffset);
457  LdDisp += MOV64SZ;
458  StDisp += MOV64SZ;
459  LMMOffset += MOV64SZ;
460  SMMOffset += MOV64SZ;
461  continue;
462  }
463  if (Size - MOV32SZ >= 0) {
464  Size = Size - MOV32SZ;
465  buildCopy(LoadInst, X86::MOV32rm, LdDisp, StoreInst, X86::MOV32mr, StDisp,
466  MOV32SZ, LMMOffset, SMMOffset);
467  LdDisp += MOV32SZ;
468  StDisp += MOV32SZ;
469  LMMOffset += MOV32SZ;
470  SMMOffset += MOV32SZ;
471  continue;
472  }
473  if (Size - MOV16SZ >= 0) {
474  Size = Size - MOV16SZ;
475  buildCopy(LoadInst, X86::MOV16rm, LdDisp, StoreInst, X86::MOV16mr, StDisp,
476  MOV16SZ, LMMOffset, SMMOffset);
477  LdDisp += MOV16SZ;
478  StDisp += MOV16SZ;
479  LMMOffset += MOV16SZ;
480  SMMOffset += MOV16SZ;
481  continue;
482  }
483  if (Size - MOV8SZ >= 0) {
484  Size = Size - MOV8SZ;
485  buildCopy(LoadInst, X86::MOV8rm, LdDisp, StoreInst, X86::MOV8mr, StDisp,
486  MOV8SZ, LMMOffset, SMMOffset);
487  LdDisp += MOV8SZ;
488  StDisp += MOV8SZ;
489  LMMOffset += MOV8SZ;
490  SMMOffset += MOV8SZ;
491  continue;
492  }
493  }
494  assert(Size == 0 && "Wrong size division");
495 }
496 
497 static void updateKillStatus(MachineInstr *LoadInst, MachineInstr *StoreInst) {
498  MachineOperand &LoadBase = getBaseOperand(LoadInst);
499  MachineOperand &StoreBase = getBaseOperand(StoreInst);
500  auto StorePrevNonDbgInstr = skipDebugInstructionsBackward(
501  std::prev(MachineBasicBlock::instr_iterator(StoreInst)),
502  LoadInst->getParent()->instr_begin()).getNodePtr();
503  if (LoadBase.isReg()) {
504  MachineInstr *LastLoad = LoadInst->getPrevNode();
505  // If the original load and store to xmm/ymm were consecutive
506  // then the partial copies were also created in
507  // a consecutive order to reduce register pressure,
508  // and the location of the last load is before the last store.
509  if (StorePrevNonDbgInstr == LoadInst)
510  LastLoad = LoadInst->getPrevNode()->getPrevNode();
511  getBaseOperand(LastLoad).setIsKill(LoadBase.isKill());
512  }
513  if (StoreBase.isReg()) {
514  MachineInstr *StInst = StoreInst;
515  if (StorePrevNonDbgInstr == LoadInst)
516  StInst = LoadInst;
517  getBaseOperand(StInst->getPrevNode()).setIsKill(StoreBase.isKill());
518  }
519 }
520 
521 bool X86AvoidSFBPass::alias(const MachineMemOperand &Op1,
522  const MachineMemOperand &Op2) const {
523  if (!Op1.getValue() || !Op2.getValue())
524  return true;
525 
526  int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset());
527  int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset;
528  int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset;
529 
530  AliasResult AAResult =
531  AA->alias(MemoryLocation(Op1.getValue(), Overlapa, Op1.getAAInfo()),
532  MemoryLocation(Op2.getValue(), Overlapb, Op2.getAAInfo()));
533  return AAResult != NoAlias;
534 }
535 
536 void X86AvoidSFBPass::findPotentiallylBlockedCopies(MachineFunction &MF) {
537  for (auto &MBB : MF)
538  for (auto &MI : MBB) {
539  if (!isPotentialBlockedMemCpyLd(MI.getOpcode()))
540  continue;
541  int DefVR = MI.getOperand(0).getReg();
542  if (!MRI->hasOneNonDBGUse(DefVR))
543  continue;
544  for (auto UI = MRI->use_nodbg_begin(DefVR), UE = MRI->use_nodbg_end();
545  UI != UE;) {
546  MachineOperand &StoreMO = *UI++;
547  MachineInstr &StoreMI = *StoreMO.getParent();
548  // Skip cases where the memcpy may overlap.
549  if (StoreMI.getParent() == MI.getParent() &&
550  isPotentialBlockedMemCpyPair(MI.getOpcode(), StoreMI.getOpcode()) &&
552  isRelevantAddressingMode(&StoreMI)) {
553  assert(MI.hasOneMemOperand() &&
554  "Expected one memory operand for load instruction");
555  assert(StoreMI.hasOneMemOperand() &&
556  "Expected one memory operand for store instruction");
557  if (!alias(**MI.memoperands_begin(), **StoreMI.memoperands_begin()))
558  BlockedLoadsStoresPairs.push_back(std::make_pair(&MI, &StoreMI));
559  }
560  }
561  }
562 }
563 
564 unsigned X86AvoidSFBPass::getRegSizeInBytes(MachineInstr *LoadInst) {
565  auto TRC = TII->getRegClass(TII->get(LoadInst->getOpcode()), 0, TRI,
566  *LoadInst->getParent()->getParent());
567  return TRI->getRegSizeInBits(*TRC) / 8;
568 }
569 
570 void X86AvoidSFBPass::breakBlockedCopies(
571  MachineInstr *LoadInst, MachineInstr *StoreInst,
572  const DisplacementSizeMap &BlockingStoresDispSizeMap) {
573  int64_t LdDispImm = getDispOperand(LoadInst).getImm();
574  int64_t StDispImm = getDispOperand(StoreInst).getImm();
575  int64_t LMMOffset = 0;
576  int64_t SMMOffset = 0;
577 
578  int64_t LdDisp1 = LdDispImm;
579  int64_t LdDisp2 = 0;
580  int64_t StDisp1 = StDispImm;
581  int64_t StDisp2 = 0;
582  unsigned Size1 = 0;
583  unsigned Size2 = 0;
584  int64_t LdStDelta = StDispImm - LdDispImm;
585 
586  for (auto DispSizePair : BlockingStoresDispSizeMap) {
587  LdDisp2 = DispSizePair.first;
588  StDisp2 = DispSizePair.first + LdStDelta;
589  Size2 = DispSizePair.second;
590  // Avoid copying overlapping areas.
591  if (LdDisp2 < LdDisp1) {
592  int OverlapDelta = LdDisp1 - LdDisp2;
593  LdDisp2 += OverlapDelta;
594  StDisp2 += OverlapDelta;
595  Size2 -= OverlapDelta;
596  }
597  Size1 = LdDisp2 - LdDisp1;
598 
599  // Build a copy for the point until the current blocking store's
600  // displacement.
601  buildCopies(Size1, LoadInst, LdDisp1, StoreInst, StDisp1, LMMOffset,
602  SMMOffset);
603  // Build a copy for the current blocking store.
604  buildCopies(Size2, LoadInst, LdDisp2, StoreInst, StDisp2, LMMOffset + Size1,
605  SMMOffset + Size1);
606  LdDisp1 = LdDisp2 + Size2;
607  StDisp1 = StDisp2 + Size2;
608  LMMOffset += Size1 + Size2;
609  SMMOffset += Size1 + Size2;
610  }
611  unsigned Size3 = (LdDispImm + getRegSizeInBytes(LoadInst)) - LdDisp1;
612  buildCopies(Size3, LoadInst, LdDisp1, StoreInst, StDisp1, LMMOffset,
613  LMMOffset);
614 }
615 
616 static bool hasSameBaseOpValue(MachineInstr *LoadInst,
617  MachineInstr *StoreInst) {
618  MachineOperand &LoadBase = getBaseOperand(LoadInst);
619  MachineOperand &StoreBase = getBaseOperand(StoreInst);
620  if (LoadBase.isReg() != StoreBase.isReg())
621  return false;
622  if (LoadBase.isReg())
623  return LoadBase.getReg() == StoreBase.getReg();
624  return LoadBase.getIndex() == StoreBase.getIndex();
625 }
626 
627 static bool isBlockingStore(int64_t LoadDispImm, unsigned LoadSize,
628  int64_t StoreDispImm, unsigned StoreSize) {
629  return ((StoreDispImm >= LoadDispImm) &&
630  (StoreDispImm <= LoadDispImm + (LoadSize - StoreSize)));
631 }
632 
633 // Keep track of all stores blocking a load
634 static void
635 updateBlockingStoresDispSizeMap(DisplacementSizeMap &BlockingStoresDispSizeMap,
636  int64_t DispImm, unsigned Size) {
637  if (BlockingStoresDispSizeMap.count(DispImm)) {
638  // Choose the smallest blocking store starting at this displacement.
639  if (BlockingStoresDispSizeMap[DispImm] > Size)
640  BlockingStoresDispSizeMap[DispImm] = Size;
641 
642  } else
643  BlockingStoresDispSizeMap[DispImm] = Size;
644 }
645 
646 // Remove blocking stores contained in each other.
647 static void
648 removeRedundantBlockingStores(DisplacementSizeMap &BlockingStoresDispSizeMap) {
649  if (BlockingStoresDispSizeMap.size() <= 1)
650  return;
651 
653  for (auto DispSizePair : BlockingStoresDispSizeMap) {
654  int64_t CurrDisp = DispSizePair.first;
655  unsigned CurrSize = DispSizePair.second;
656  while (DispSizeStack.size()) {
657  int64_t PrevDisp = DispSizeStack.back().first;
658  unsigned PrevSize = DispSizeStack.back().second;
659  if (CurrDisp + CurrSize > PrevDisp + PrevSize)
660  break;
661  DispSizeStack.pop_back();
662  }
663  DispSizeStack.push_back(DispSizePair);
664  }
665  BlockingStoresDispSizeMap.clear();
666  for (auto Disp : DispSizeStack)
667  BlockingStoresDispSizeMap.insert(Disp);
668 }
669 
670 bool X86AvoidSFBPass::runOnMachineFunction(MachineFunction &MF) {
671  bool Changed = false;
672 
673  if (DisableX86AvoidStoreForwardBlocks || skipFunction(MF.getFunction()) ||
675  return false;
676 
677  MRI = &MF.getRegInfo();
678  assert(MRI->isSSA() && "Expected MIR to be in SSA form");
679  TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
680  TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo();
681  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
682  LLVM_DEBUG(dbgs() << "Start X86AvoidStoreForwardBlocks\n";);
683  // Look for a load then a store to XMM/YMM which look like a memcpy
684  findPotentiallylBlockedCopies(MF);
685 
686  for (auto LoadStoreInstPair : BlockedLoadsStoresPairs) {
687  MachineInstr *LoadInst = LoadStoreInstPair.first;
688  int64_t LdDispImm = getDispOperand(LoadInst).getImm();
689  DisplacementSizeMap BlockingStoresDispSizeMap;
690 
691  SmallVector<MachineInstr *, 2> PotentialBlockers =
692  findPotentialBlockers(LoadInst);
693  for (auto PBInst : PotentialBlockers) {
694  if (!isPotentialBlockingStoreInst(PBInst->getOpcode(),
695  LoadInst->getOpcode()) ||
696  !isRelevantAddressingMode(PBInst))
697  continue;
698  int64_t PBstDispImm = getDispOperand(PBInst).getImm();
699  assert(PBInst->hasOneMemOperand() && "Expected One Memory Operand");
700  unsigned PBstSize = (*PBInst->memoperands_begin())->getSize();
701  // This check doesn't cover all cases, but it will suffice for now.
702  // TODO: take branch probability into consideration, if the blocking
703  // store is in an unreached block, breaking the memcopy could lose
704  // performance.
705  if (hasSameBaseOpValue(LoadInst, PBInst) &&
706  isBlockingStore(LdDispImm, getRegSizeInBytes(LoadInst), PBstDispImm,
707  PBstSize))
708  updateBlockingStoresDispSizeMap(BlockingStoresDispSizeMap, PBstDispImm,
709  PBstSize);
710  }
711 
712  if (BlockingStoresDispSizeMap.empty())
713  continue;
714 
715  // We found a store forward block, break the memcpy's load and store
716  // into smaller copies such that each smaller store that was causing
717  // a store block would now be copied separately.
718  MachineInstr *StoreInst = LoadStoreInstPair.second;
719  LLVM_DEBUG(dbgs() << "Blocked load and store instructions: \n");
720  LLVM_DEBUG(LoadInst->dump());
721  LLVM_DEBUG(StoreInst->dump());
722  LLVM_DEBUG(dbgs() << "Replaced with:\n");
723  removeRedundantBlockingStores(BlockingStoresDispSizeMap);
724  breakBlockedCopies(LoadInst, StoreInst, BlockingStoresDispSizeMap);
725  updateKillStatus(LoadInst, StoreInst);
726  ForRemoval.push_back(LoadInst);
727  ForRemoval.push_back(StoreInst);
728  }
729  for (auto RemovedInst : ForRemoval) {
730  RemovedInst->eraseFromParent();
731  }
732  ForRemoval.clear();
733  BlockedLoadsStoresPairs.clear();
734  LLVM_DEBUG(dbgs() << "End X86AvoidStoreForwardBlocks\n";);
735 
736  return Changed;
737 }
bool is64Bit() const
Is this x86_64? (disregarding specific ABI / programming model)
Definition: X86Subtarget.h:548
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
static bool isYMMLoadOpcode(unsigned Opcode)
instr_iterator instr_begin()
static void updateKillStatus(MachineInstr *LoadInst, MachineInstr *StoreInst)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:384
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:179
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
uint64_t getSize() const
Return the size in bytes of the memory reference.
unsigned const TargetRegisterInfo * TRI
An instruction for reading from memory.
Definition: Instructions.h:169
static void removeRedundantBlockingStores(DisplacementSizeMap &BlockingStoresDispSizeMap)
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
static cl::opt< bool > DisableX86AvoidStoreForwardBlocks("x86-disable-avoid-SFB", cl::Hidden, cl::desc("X86: Disable Store Forwarding Blocks fixup."), cl::init(false))
static void updateBlockingStoresDispSizeMap(DisplacementSizeMap &BlockingStoresDispSizeMap, int64_t DispImm, unsigned Size)
AddrNumOperands - Total number of operands in a memory reference.
Definition: X86BaseInfo.h:41
AAMDNodes getAAInfo() const
Return the AA tags for the memory reference.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
A description of a memory reference used in the backend.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
static bool hasSameBaseOpValue(MachineInstr *LoadInst, MachineInstr *StoreInst)
MachineBasicBlock iterator that automatically skips over MIs that are inside bundles (i...
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:410
MachineMemOperand * getMachineMemOperand(MachinePointerInfo PtrInfo, MachineMemOperand::Flags f, uint64_t s, unsigned base_alignment, const AAMDNodes &AAInfo=AAMDNodes(), const MDNode *Ranges=nullptr, SyncScope::ID SSID=SyncScope::System, AtomicOrdering Ordering=AtomicOrdering::NotAtomic, AtomicOrdering FailureOrdering=AtomicOrdering::NotAtomic)
getMachineMemOperand - Allocate a new MachineMemOperand.
static bool isBlockingStore(int64_t LoadDispImm, unsigned LoadSize, int64_t StoreDispImm, unsigned StoreSize)
static bool isPotentialBlockingStoreInst(int Opcode, int LoadOpcode)
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:407
static const int MOV16SZ
static const int MOV32SZ
An instruction for storing to memory.
Definition: Instructions.h:325
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:365
reverse_iterator rend()
reverse_iterator rbegin()
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:78
const Value * getValue() const
Return the base address of the memory access.
static cl::opt< unsigned > X86AvoidSFBInspectionLimit("x86-sfb-inspection-limit", cl::desc("X86: Number of instructions backward to " "inspect for store forwarding blocks."), cl::init(20), cl::Hidden)
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static int getAddrOffset(MachineInstr *MI)
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static unsigned getYMMtoXMMStoreOpcode(unsigned StoreOpcode)
Represent the analysis usage information of a pass.
bool hasOneMemOperand() const
Return true if this instruction has exactly one MachineMemOperand.
Definition: MachineInstr.h:566
static bool isPotentialBlockedMemCpyLd(unsigned Opcode)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
unsigned getOperandBias(const MCInstrDesc &Desc)
getOperandBias - compute whether all of the def operands are repeated in the uses and therefore shoul...
Definition: X86BaseInfo.h:721
std::vector< MachineBasicBlock * >::iterator pred_iterator
AddrSegmentReg - The operand # of the segment in the memory operand.
Definition: X86BaseInfo.h:38
static const int MOV128SZ
size_t size() const
Definition: SmallVector.h:52
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setIsKill(bool Val=true)
Representation for a specific memory location.
Iterator for intrusive lists based on ilist_node.
mmo_iterator memoperands_begin() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:551
static uint64_t add(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:215
static SmallVector< MachineInstr *, 2 > findPotentialBlockers(MachineInstr *LoadInst)
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
static MachineOperand & getBaseOperand(MachineInstr *MI)
int64_t getImm() const
IterT skipDebugInstructionsBackward(IterT It, IterT Begin)
Decrement It until it points to a non-debug instruction or to Begin and return the resulting iterator...
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static MachineOperand & getDispOperand(MachineInstr *MI)
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:255
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:63
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
static bool isRelevantAddressingMode(MachineInstr *MI)
INITIALIZE_PASS_BEGIN(X86AvoidSFBPass, DEBUG_TYPE, "Machine code sinking", false, false) INITIALIZE_PASS_END(X86AvoidSFBPass
bool isFI() const
isFI - Tests if this is a MO_FrameIndex operand.
bool isCall() const
Return true if the instruction is a call.
Definition: MCInstrDesc.h:277
static bool isXMMLoadOpcode(unsigned Opcode)
Machine code sinking
uint32_t Size
Definition: Profile.cpp:46
bool isReg() const
isReg - Tests if this is a MO_Register operand.
static const int MOV64SZ
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
int64_t getOffset() const
For normal values, this is a byte offset added to the base address.
static const int MOV8SZ
FunctionPass * createX86AvoidStoreForwardingBlocks()
Return a pass that avoids creating store forward block issues in the hardware.
static unsigned getYMMtoXMMLoadOpcode(unsigned LoadOpcode)
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
static bool isPotentialBlockedMemCpyPair(int LdOpcode, int StOpcode)
Register getReg() const
getReg - Returns the register number.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
int getMemoryOperandNo(uint64_t TSFlags)
getMemoryOperandNo - The function returns the MCInst operand # for the first field of the memory oper...
Definition: X86BaseInfo.h:761