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