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