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   /// \brief Returns couples of Load then Store to memory which look
101   ///  like a memcpy.
102   void findPotentiallylBlockedCopies(MachineFunction &MF);
103   /// \brief 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   /// \brief 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   BuildMI(*MBB, LoadInst, LoadInst->getDebugLoc(), TII->get(NLoadOpcode), 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   DEBUG(LoadInst->getPrevNode()->dump());
407   // If the load and store are consecutive, use the loadInst location to
408   // reduce register pressure.
409   MachineInstr *StInst = StoreInst;
410   if (StoreInst->getPrevNode() == LoadInst)
411     StInst = LoadInst;
412   BuildMI(*MBB, StInst, StInst->getDebugLoc(), TII->get(NStoreOpcode))
413       .add(StoreBase)
414       .addImm(1)
415       .addReg(X86::NoRegister)
416       .addImm(StoreDisp)
417       .addReg(X86::NoRegister)
418       .addReg(Reg1)
419       .addMemOperand(
420           MBB->getParent()->getMachineMemOperand(SMMO, SMMOffset, Size));
421   DEBUG(StInst->getPrevNode()->dump());
422 }
423 
424 void X86AvoidSFBPass::buildCopies(int Size, MachineInstr *LoadInst,
425                                   int64_t LdDispImm, MachineInstr *StoreInst,
426                                   int64_t StDispImm, int64_t LMMOffset,
427                                   int64_t SMMOffset) {
428   int LdDisp = LdDispImm;
429   int StDisp = StDispImm;
430   while (Size > 0) {
431     if ((Size - MOV128SZ >= 0) && isYMMLoadOpcode(LoadInst->getOpcode())) {
432       Size = Size - MOV128SZ;
433       buildCopy(LoadInst, getYMMtoXMMLoadOpcode(LoadInst->getOpcode()), LdDisp,
434                 StoreInst, getYMMtoXMMStoreOpcode(StoreInst->getOpcode()),
435                 StDisp, MOV128SZ, LMMOffset, SMMOffset);
436       LdDisp += MOV128SZ;
437       StDisp += MOV128SZ;
438       LMMOffset += MOV128SZ;
439       SMMOffset += MOV128SZ;
440       continue;
441     }
442     if (Size - MOV64SZ >= 0) {
443       Size = Size - MOV64SZ;
444       buildCopy(LoadInst, X86::MOV64rm, LdDisp, StoreInst, X86::MOV64mr, StDisp,
445                 MOV64SZ, LMMOffset, SMMOffset);
446       LdDisp += MOV64SZ;
447       StDisp += MOV64SZ;
448       LMMOffset += MOV64SZ;
449       SMMOffset += MOV64SZ;
450       continue;
451     }
452     if (Size - MOV32SZ >= 0) {
453       Size = Size - MOV32SZ;
454       buildCopy(LoadInst, X86::MOV32rm, LdDisp, StoreInst, X86::MOV32mr, StDisp,
455                 MOV32SZ, LMMOffset, SMMOffset);
456       LdDisp += MOV32SZ;
457       StDisp += MOV32SZ;
458       LMMOffset += MOV32SZ;
459       SMMOffset += MOV32SZ;
460       continue;
461     }
462     if (Size - MOV16SZ >= 0) {
463       Size = Size - MOV16SZ;
464       buildCopy(LoadInst, X86::MOV16rm, LdDisp, StoreInst, X86::MOV16mr, StDisp,
465                 MOV16SZ, LMMOffset, SMMOffset);
466       LdDisp += MOV16SZ;
467       StDisp += MOV16SZ;
468       LMMOffset += MOV16SZ;
469       SMMOffset += MOV16SZ;
470       continue;
471     }
472     if (Size - MOV8SZ >= 0) {
473       Size = Size - MOV8SZ;
474       buildCopy(LoadInst, X86::MOV8rm, LdDisp, StoreInst, X86::MOV8mr, StDisp,
475                 MOV8SZ, LMMOffset, SMMOffset);
476       LdDisp += MOV8SZ;
477       StDisp += MOV8SZ;
478       LMMOffset += MOV8SZ;
479       SMMOffset += MOV8SZ;
480       continue;
481     }
482   }
483   assert(Size == 0 && "Wrong size division");
484 }
485 
486 static void updateKillStatus(MachineInstr *LoadInst, MachineInstr *StoreInst) {
487   MachineOperand &LoadBase = getBaseOperand(LoadInst);
488   MachineOperand &StoreBase = getBaseOperand(StoreInst);
489   if (LoadBase.isReg()) {
490     MachineInstr *LastLoad = LoadInst->getPrevNode();
491     // If the original load and store to xmm/ymm were consecutive
492     // then the partial copies were also created in
493     // a consecutive order to reduce register pressure,
494     // and the location of the last load is before the last store.
495     if (StoreInst->getPrevNode() == LoadInst)
496       LastLoad = LoadInst->getPrevNode()->getPrevNode();
497     getBaseOperand(LastLoad).setIsKill(LoadBase.isKill());
498   }
499   if (StoreBase.isReg()) {
500     MachineInstr *StInst = StoreInst;
501     if (StoreInst->getPrevNode() == LoadInst)
502       StInst = LoadInst;
503     getBaseOperand(StInst->getPrevNode()).setIsKill(StoreBase.isKill());
504   }
505 }
506 
507 bool X86AvoidSFBPass::alias(const MachineMemOperand &Op1,
508                             const MachineMemOperand &Op2) const {
509   if (!Op1.getValue() || !Op2.getValue())
510     return true;
511 
512   int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset());
513   int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset;
514   int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset;
515 
516   AliasResult AAResult =
517       AA->alias(MemoryLocation(Op1.getValue(), Overlapa, Op1.getAAInfo()),
518                 MemoryLocation(Op2.getValue(), Overlapb, Op2.getAAInfo()));
519   return AAResult != NoAlias;
520 }
521 
522 void X86AvoidSFBPass::findPotentiallylBlockedCopies(MachineFunction &MF) {
523   for (auto &MBB : MF)
524     for (auto &MI : MBB) {
525       if (!isPotentialBlockedMemCpyLd(MI.getOpcode()))
526         continue;
527       int DefVR = MI.getOperand(0).getReg();
528       if (!MRI->hasOneUse(DefVR))
529         continue;
530       for (auto UI = MRI->use_nodbg_begin(DefVR), UE = MRI->use_nodbg_end();
531            UI != UE;) {
532         MachineOperand &StoreMO = *UI++;
533         MachineInstr &StoreMI = *StoreMO.getParent();
534         // Skip cases where the memcpy may overlap.
535         if (StoreMI.getParent() == MI.getParent() &&
536             isPotentialBlockedMemCpyPair(MI.getOpcode(), StoreMI.getOpcode()) &&
537             isRelevantAddressingMode(&MI) &&
538             isRelevantAddressingMode(&StoreMI)) {
539           assert(MI.hasOneMemOperand() &&
540                  "Expected one memory operand for load instruction");
541           assert(StoreMI.hasOneMemOperand() &&
542                  "Expected one memory operand for store instruction");
543           if (!alias(**MI.memoperands_begin(), **StoreMI.memoperands_begin()))
544             BlockedLoadsStoresPairs.push_back(std::make_pair(&MI, &StoreMI));
545         }
546       }
547     }
548 }
549 
550 unsigned X86AvoidSFBPass::getRegSizeInBytes(MachineInstr *LoadInst) {
551   auto TRC = TII->getRegClass(TII->get(LoadInst->getOpcode()), 0, TRI,
552                               *LoadInst->getParent()->getParent());
553   return TRI->getRegSizeInBits(*TRC) / 8;
554 }
555 
556 void X86AvoidSFBPass::breakBlockedCopies(
557     MachineInstr *LoadInst, MachineInstr *StoreInst,
558     const DisplacementSizeMap &BlockingStoresDispSizeMap) {
559   int64_t LdDispImm = getDispOperand(LoadInst).getImm();
560   int64_t StDispImm = getDispOperand(StoreInst).getImm();
561   int64_t LMMOffset = (*LoadInst->memoperands_begin())->getOffset();
562   int64_t SMMOffset = (*StoreInst->memoperands_begin())->getOffset();
563 
564   int64_t LdDisp1 = LdDispImm;
565   int64_t LdDisp2 = 0;
566   int64_t StDisp1 = StDispImm;
567   int64_t StDisp2 = 0;
568   unsigned Size1 = 0;
569   unsigned Size2 = 0;
570   int64_t LdStDelta = StDispImm - LdDispImm;
571 
572   for (auto DispSizePair : BlockingStoresDispSizeMap) {
573     LdDisp2 = DispSizePair.first;
574     StDisp2 = DispSizePair.first + LdStDelta;
575     Size2 = DispSizePair.second;
576     // Avoid copying overlapping areas.
577     if (LdDisp2 < LdDisp1) {
578       int OverlapDelta = LdDisp1 - LdDisp2;
579       LdDisp2 += OverlapDelta;
580       StDisp2 += OverlapDelta;
581       Size2 -= OverlapDelta;
582     }
583     Size1 = std::abs(std::abs(LdDisp2) - std::abs(LdDisp1));
584 
585     // Build a copy for the point until the current blocking store's
586     // displacement.
587     buildCopies(Size1, LoadInst, LdDisp1, StoreInst, StDisp1, LMMOffset,
588                 SMMOffset);
589     // Build a copy for the current blocking store.
590     buildCopies(Size2, LoadInst, LdDisp2, StoreInst, StDisp2, LMMOffset + Size1,
591                 SMMOffset + Size1);
592     LdDisp1 = LdDisp2 + Size2;
593     StDisp1 = StDisp2 + Size2;
594     LMMOffset += Size1 + Size2;
595     SMMOffset += Size1 + Size2;
596   }
597   unsigned Size3 = (LdDispImm + getRegSizeInBytes(LoadInst)) - LdDisp1;
598   buildCopies(Size3, LoadInst, LdDisp1, StoreInst, StDisp1, LMMOffset,
599               LMMOffset);
600 }
601 
602 static bool hasSameBaseOpValue(MachineInstr *LoadInst,
603                                MachineInstr *StoreInst) {
604   MachineOperand &LoadBase = getBaseOperand(LoadInst);
605   MachineOperand &StoreBase = getBaseOperand(StoreInst);
606   if (LoadBase.isReg() != StoreBase.isReg())
607     return false;
608   if (LoadBase.isReg())
609     return LoadBase.getReg() == StoreBase.getReg();
610   return LoadBase.getIndex() == StoreBase.getIndex();
611 }
612 
613 static bool isBlockingStore(int64_t LoadDispImm, unsigned LoadSize,
614                             int64_t StoreDispImm, unsigned StoreSize) {
615   return ((StoreDispImm >= LoadDispImm) &&
616           (StoreDispImm <= LoadDispImm + (LoadSize - StoreSize)));
617 }
618 
619 // Keep track of all stores blocking a load
620 static void
621 updateBlockingStoresDispSizeMap(DisplacementSizeMap &BlockingStoresDispSizeMap,
622                                 int64_t DispImm, unsigned Size) {
623   if (BlockingStoresDispSizeMap.count(DispImm)) {
624     // Choose the smallest blocking store starting at this displacement.
625     if (BlockingStoresDispSizeMap[DispImm] > Size)
626       BlockingStoresDispSizeMap[DispImm] = Size;
627 
628   } else
629     BlockingStoresDispSizeMap[DispImm] = Size;
630 }
631 
632 // Remove blocking stores contained in each other.
633 static void
634 removeRedundantBlockingStores(DisplacementSizeMap &BlockingStoresDispSizeMap) {
635   if (BlockingStoresDispSizeMap.size() <= 1)
636     return;
637 
638   int64_t PrevDisp = BlockingStoresDispSizeMap.begin()->first;
639   unsigned PrevSize = BlockingStoresDispSizeMap.begin()->second;
640   SmallVector<int64_t, 2> ForRemoval;
641   for (auto DispSizePair = std::next(BlockingStoresDispSizeMap.begin());
642        DispSizePair != BlockingStoresDispSizeMap.end(); ++DispSizePair) {
643     int64_t CurrDisp = DispSizePair->first;
644     unsigned CurrSize = DispSizePair->second;
645     if (CurrDisp + CurrSize <= PrevDisp + PrevSize) {
646       ForRemoval.push_back(PrevDisp);
647     }
648     PrevDisp = CurrDisp;
649     PrevSize = CurrSize;
650   }
651   for (auto Disp : ForRemoval)
652     BlockingStoresDispSizeMap.erase(Disp);
653 }
654 
655 bool X86AvoidSFBPass::runOnMachineFunction(MachineFunction &MF) {
656   bool Changed = false;
657 
658   if (DisableX86AvoidStoreForwardBlocks || skipFunction(MF.getFunction()) ||
659       !MF.getSubtarget<X86Subtarget>().is64Bit())
660     return false;
661 
662   MRI = &MF.getRegInfo();
663   assert(MRI->isSSA() && "Expected MIR to be in SSA form");
664   TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
665   TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo();
666   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
667   DEBUG(dbgs() << "Start X86AvoidStoreForwardBlocks\n";);
668   // Look for a load then a store to XMM/YMM which look like a memcpy
669   findPotentiallylBlockedCopies(MF);
670 
671   for (auto LoadStoreInstPair : BlockedLoadsStoresPairs) {
672     MachineInstr *LoadInst = LoadStoreInstPair.first;
673     int64_t LdDispImm = getDispOperand(LoadInst).getImm();
674     DisplacementSizeMap BlockingStoresDispSizeMap;
675 
676     SmallVector<MachineInstr *, 2> PotentialBlockers =
677         findPotentialBlockers(LoadInst);
678     for (auto PBInst : PotentialBlockers) {
679       if (!isPotentialBlockingStoreInst(PBInst->getOpcode(),
680                                         LoadInst->getOpcode()) ||
681           !isRelevantAddressingMode(PBInst))
682         continue;
683       int64_t PBstDispImm = getDispOperand(PBInst).getImm();
684       assert(PBInst->hasOneMemOperand() && "Expected One Memory Operand");
685       unsigned PBstSize = (*PBInst->memoperands_begin())->getSize();
686       // This check doesn't cover all cases, but it will suffice for now.
687       // TODO: take branch probability into consideration, if the blocking
688       // store is in an unreached block, breaking the memcopy could lose
689       // performance.
690       if (hasSameBaseOpValue(LoadInst, PBInst) &&
691           isBlockingStore(LdDispImm, getRegSizeInBytes(LoadInst), PBstDispImm,
692                           PBstSize))
693         updateBlockingStoresDispSizeMap(BlockingStoresDispSizeMap, PBstDispImm,
694                                         PBstSize);
695     }
696 
697     if (BlockingStoresDispSizeMap.empty())
698       continue;
699 
700     // We found a store forward block, break the memcpy's load and store
701     // into smaller copies such that each smaller store that was causing
702     // a store block would now be copied separately.
703     MachineInstr *StoreInst = LoadStoreInstPair.second;
704     DEBUG(dbgs() << "Blocked load and store instructions: \n");
705     DEBUG(LoadInst->dump());
706     DEBUG(StoreInst->dump());
707     DEBUG(dbgs() << "Replaced with:\n");
708     removeRedundantBlockingStores(BlockingStoresDispSizeMap);
709     breakBlockedCopies(LoadInst, StoreInst, BlockingStoresDispSizeMap);
710     updateKillStatus(LoadInst, StoreInst);
711     ForRemoval.push_back(LoadInst);
712     ForRemoval.push_back(StoreInst);
713   }
714   for (auto RemovedInst : ForRemoval) {
715     RemovedInst->eraseFromParent();
716   }
717   ForRemoval.clear();
718   BlockedLoadsStoresPairs.clear();
719   DEBUG(dbgs() << "End X86AvoidStoreForwardBlocks\n";);
720 
721   return Changed;
722 }
723