]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp
1 //===- MergedLoadStoreMotion.cpp - merge and hoist/sink load/stores -------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 //! \brief This pass performs merges of loads and stores on both sides of a
12 // diamond (hammock). It hoists the loads and sinks the stores.
14 // The algorithm iteratively hoists two loads to the same address out of a
15 // diamond (hammock) and merges them into a single load in the header. Similar
16 // it sinks and merges two stores to the tail block (footer). The algorithm
17 // iterates over the instructions of one side of the diamond and attempts to
18 // find a matching load/store on the other side. It hoists / sinks when it
19 // thinks it safe to do so. This optimization helps with eg. hiding load
20 // latencies, triggering if-conversion, and reducing static code size.
22 //===----------------------------------------------------------------------===//
26 // Diamond shaped code before merge:
29 // br %cond, label %if.then, label %if.else
34 // %lt = load %addr_l %le = load %addr_l
35 // <use %lt> <use %le>
37 // store %st, %addr_s store %se, %addr_s
38 // br label %if.end br label %if.end
45 // Diamond shaped code after merge:
49 // br %cond, label %if.then, label %if.else
56 // br label %if.end br label %if.end
61 // %s.sink = phi [%st, if.then], [%se, if.else]
63 // store %s.sink, %addr_s
67 //===----------------------- TODO -----------------------------------------===//
69 // 1) Generalize to regions other than diamonds
70 // 2) Be more aggressive merging memory operations
71 // Note that both changes require register pressure control
73 //===----------------------------------------------------------------------===//
75 #include "llvm/Transforms/Scalar.h"
76 #include "llvm/ADT/SetVector.h"
77 #include "llvm/ADT/SmallPtrSet.h"
78 #include "llvm/ADT/Statistic.h"
79 #include "llvm/Analysis/AliasAnalysis.h"
80 #include "llvm/Analysis/CFG.h"
81 #include "llvm/Analysis/Loads.h"
82 #include "llvm/Analysis/MemoryBuiltins.h"
83 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
84 #include "llvm/IR/Metadata.h"
85 #include "llvm/IR/PatternMatch.h"
86 #include "llvm/Support/Allocator.h"
87 #include "llvm/Support/CommandLine.h"
88 #include "llvm/Support/Debug.h"
89 #include "llvm/Target/TargetLibraryInfo.h"
90 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
91 #include "llvm/Transforms/Utils/SSAUpdater.h"
95 #define DEBUG_TYPE "mldst-motion"
97 //===----------------------------------------------------------------------===//
98 // MergedLoadStoreMotion Pass
99 //===----------------------------------------------------------------------===//
102 class MergedLoadStoreMotion
: public FunctionPass
{
104 MemoryDependenceAnalysis
*MD
;
107 static char ID
; // Pass identification, replacement for typeid
108 explicit MergedLoadStoreMotion(void)
109 : FunctionPass(ID
), MD(nullptr), MagicCompileTimeControl(250) {
110 initializeMergedLoadStoreMotionPass(*PassRegistry::getPassRegistry());
113 bool runOnFunction(Function
&F
) override
;
116 // This transformation requires dominator postdominator info
117 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
118 AU
.addRequired
<TargetLibraryInfo
>();
119 AU
.addRequired
<MemoryDependenceAnalysis
>();
120 AU
.addRequired
<AliasAnalysis
>();
121 AU
.addPreserved
<AliasAnalysis
>();
127 /// \brief Remove instruction from parent and update memory dependence
130 void removeInstruction(Instruction
*Inst
);
131 BasicBlock
*getDiamondTail(BasicBlock
*BB
);
132 bool isDiamondHead(BasicBlock
*BB
);
133 // Routines for hoisting loads
134 bool isLoadHoistBarrierInRange(const Instruction
& Start
,
135 const Instruction
& End
,
137 LoadInst
*canHoistFromBlock(BasicBlock
*BB
, LoadInst
*LI
);
138 void hoistInstruction(BasicBlock
*BB
, Instruction
*HoistCand
,
139 Instruction
*ElseInst
);
140 bool isSafeToHoist(Instruction
*I
) const;
141 bool hoistLoad(BasicBlock
*BB
, LoadInst
*HoistCand
, LoadInst
*ElseInst
);
142 bool mergeLoads(BasicBlock
*BB
);
143 // Routines for sinking stores
144 StoreInst
*canSinkFromBlock(BasicBlock
*BB
, StoreInst
*SI
);
145 PHINode
*getPHIOperand(BasicBlock
*BB
, StoreInst
*S0
, StoreInst
*S1
);
146 bool isStoreSinkBarrierInRange(const Instruction
& Start
,
147 const Instruction
& End
,
148 AliasAnalysis::Location Loc
);
149 bool sinkStore(BasicBlock
*BB
, StoreInst
*SinkCand
, StoreInst
*ElseInst
);
150 bool mergeStores(BasicBlock
*BB
);
151 // The mergeLoad/Store algorithms could have Size0 * Size1 complexity,
152 // where Size0 and Size1 are the #instructions on the two sides of
153 // the diamond. The constant chosen here is arbitrary. Compiler Time
154 // Control is enforced by the check Size0 * Size1 < MagicCompileTimeControl.
155 const int MagicCompileTimeControl
;
158 char MergedLoadStoreMotion::ID
= 0;
162 /// \brief createMergedLoadStoreMotionPass - The public interface to this file.
164 FunctionPass
*llvm::createMergedLoadStoreMotionPass() {
165 return new MergedLoadStoreMotion();
168 INITIALIZE_PASS_BEGIN(MergedLoadStoreMotion
, "mldst-motion",
169 "MergedLoadStoreMotion", false, false)
170 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis
)
171 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo
)
172 INITIALIZE_AG_DEPENDENCY(AliasAnalysis
)
173 INITIALIZE_PASS_END(MergedLoadStoreMotion
, "mldst-motion",
174 "MergedLoadStoreMotion", false, false)
177 /// \brief Remove instruction from parent and update memory dependence analysis.
179 void MergedLoadStoreMotion::removeInstruction(Instruction
*Inst
) {
180 // Notify the memory dependence analysis.
182 MD
->removeInstruction(Inst
);
183 if (LoadInst
*LI
= dyn_cast
<LoadInst
>(Inst
))
184 MD
->invalidateCachedPointerInfo(LI
->getPointerOperand());
185 if (Inst
->getType()->getScalarType()->isPointerTy()) {
186 MD
->invalidateCachedPointerInfo(Inst
);
189 Inst
->eraseFromParent();
193 /// \brief Return tail block of a diamond.
195 BasicBlock
*MergedLoadStoreMotion::getDiamondTail(BasicBlock
*BB
) {
196 assert(isDiamondHead(BB
) && "Basic block is not head of a diamond");
197 BranchInst
*BI
= (BranchInst
*)(BB
->getTerminator());
198 BasicBlock
*Succ0
= BI
->getSuccessor(0);
199 BasicBlock
*Tail
= Succ0
->getTerminator()->getSuccessor(0);
204 /// \brief True when BB is the head of a diamond (hammock)
206 bool MergedLoadStoreMotion::isDiamondHead(BasicBlock
*BB
) {
209 if (!isa
<BranchInst
>(BB
->getTerminator()))
211 if (BB
->getTerminator()->getNumSuccessors() != 2)
214 BranchInst
*BI
= (BranchInst
*)(BB
->getTerminator());
215 BasicBlock
*Succ0
= BI
->getSuccessor(0);
216 BasicBlock
*Succ1
= BI
->getSuccessor(1);
218 if (!Succ0
->getSinglePredecessor() ||
219 Succ0
->getTerminator()->getNumSuccessors() != 1)
221 if (!Succ1
->getSinglePredecessor() ||
222 Succ1
->getTerminator()->getNumSuccessors() != 1)
225 BasicBlock
*Tail
= Succ0
->getTerminator()->getSuccessor(0);
227 if (Succ1
->getTerminator()->getSuccessor(0) != Tail
)
233 /// \brief True when instruction is a hoist barrier for a load
235 /// Whenever an instruction could possibly modify the value
236 /// being loaded or protect against the load from happening
237 /// it is considered a hoist barrier.
240 bool MergedLoadStoreMotion::isLoadHoistBarrierInRange(const Instruction
& Start
,
241 const Instruction
& End
,
243 AliasAnalysis::Location Loc
= AA
->getLocation(LI
);
244 return AA
->canInstructionRangeModRef(Start
, End
, Loc
, AliasAnalysis::Mod
);
248 /// \brief Decide if a load can be hoisted
250 /// When there is a load in \p BB to the same address as \p LI
251 /// and it can be hoisted from \p BB, return that load.
252 /// Otherwise return Null.
254 LoadInst
*MergedLoadStoreMotion::canHoistFromBlock(BasicBlock
*BB1
,
257 for (BasicBlock::iterator BBI
= BB1
->begin(), BBE
= BB1
->end(); BBI
!= BBE
;
259 Instruction
*Inst
= BBI
;
261 // Only merge and hoist loads when their result in used only in BB
262 if (!isa
<LoadInst
>(Inst
) || Inst
->isUsedOutsideOfBlock(BB1
))
265 LoadInst
*Load1
= dyn_cast
<LoadInst
>(Inst
);
266 BasicBlock
*BB0
= Load0
->getParent();
268 AliasAnalysis::Location Loc0
= AA
->getLocation(Load0
);
269 AliasAnalysis::Location Loc1
= AA
->getLocation(Load1
);
270 if (AA
->isMustAlias(Loc0
, Loc1
) && Load0
->isSameOperationAs(Load1
) &&
271 !isLoadHoistBarrierInRange(BB1
->front(), *Load1
, Load1
) &&
272 !isLoadHoistBarrierInRange(BB0
->front(), *Load0
, Load0
)) {
280 /// \brief Merge two equivalent instructions \p HoistCand and \p ElseInst into
283 /// BB is the head of a diamond
285 void MergedLoadStoreMotion::hoistInstruction(BasicBlock
*BB
,
286 Instruction
*HoistCand
,
287 Instruction
*ElseInst
) {
288 DEBUG(dbgs() << " Hoist Instruction into BB \n"; BB
->dump();
289 dbgs() << "Instruction Left\n"; HoistCand
->dump(); dbgs() << "\n";
290 dbgs() << "Instruction Right\n"; ElseInst
->dump(); dbgs() << "\n");
291 // Hoist the instruction.
292 assert(HoistCand
->getParent() != BB
);
294 // Intersect optional metadata.
295 HoistCand
->intersectOptionalDataWith(ElseInst
);
296 HoistCand
->dropUnknownMetadata();
298 // Prepend point for instruction insert
299 Instruction
*HoistPt
= BB
->getTerminator();
301 // Merged instruction
302 Instruction
*HoistedInst
= HoistCand
->clone();
304 // Notify AA of the new value.
305 if (isa
<LoadInst
>(HoistCand
))
306 AA
->copyValue(HoistCand
, HoistedInst
);
308 // Hoist instruction.
309 HoistedInst
->insertBefore(HoistPt
);
311 HoistCand
->replaceAllUsesWith(HoistedInst
);
312 removeInstruction(HoistCand
);
313 // Replace the else block instruction.
314 ElseInst
->replaceAllUsesWith(HoistedInst
);
315 removeInstruction(ElseInst
);
319 /// \brief Return true if no operand of \p I is defined in I's parent block
321 bool MergedLoadStoreMotion::isSafeToHoist(Instruction
*I
) const {
322 BasicBlock
*Parent
= I
->getParent();
323 for (unsigned i
= 0, e
= I
->getNumOperands(); i
!= e
; ++i
) {
324 Instruction
*Instr
= dyn_cast
<Instruction
>(I
->getOperand(i
));
325 if (Instr
&& Instr
->getParent() == Parent
)
332 /// \brief Merge two equivalent loads and GEPs and hoist into diamond head
334 bool MergedLoadStoreMotion::hoistLoad(BasicBlock
*BB
, LoadInst
*L0
,
336 // Only one definition?
337 Instruction
*A0
= dyn_cast
<Instruction
>(L0
->getPointerOperand());
338 Instruction
*A1
= dyn_cast
<Instruction
>(L1
->getPointerOperand());
339 if (A0
&& A1
&& A0
->isIdenticalTo(A1
) && isSafeToHoist(A0
) &&
340 A0
->hasOneUse() && (A0
->getParent() == L0
->getParent()) &&
341 A1
->hasOneUse() && (A1
->getParent() == L1
->getParent()) &&
342 isa
<GetElementPtrInst
>(A0
)) {
343 DEBUG(dbgs() << "Hoist Instruction into BB \n"; BB
->dump();
344 dbgs() << "Instruction Left\n"; L0
->dump(); dbgs() << "\n";
345 dbgs() << "Instruction Right\n"; L1
->dump(); dbgs() << "\n");
346 hoistInstruction(BB
, A0
, A1
);
347 hoistInstruction(BB
, L0
, L1
);
354 /// \brief Try to hoist two loads to same address into diamond header
356 /// Starting from a diamond head block, iterate over the instructions in one
357 /// successor block and try to match a load in the second successor.
359 bool MergedLoadStoreMotion::mergeLoads(BasicBlock
*BB
) {
360 bool MergedLoads
= false;
361 assert(isDiamondHead(BB
));
362 BranchInst
*BI
= dyn_cast
<BranchInst
>(BB
->getTerminator());
363 BasicBlock
*Succ0
= BI
->getSuccessor(0);
364 BasicBlock
*Succ1
= BI
->getSuccessor(1);
365 // #Instructions in Succ1 for Compile Time Control
366 int Size1
= Succ1
->size();
368 for (BasicBlock::iterator BBI
= Succ0
->begin(), BBE
= Succ0
->end();
371 Instruction
*I
= BBI
;
374 // Only move non-simple (atomic, volatile) loads.
375 LoadInst
*L0
= dyn_cast
<LoadInst
>(I
);
376 if (!L0
|| !L0
->isSimple() || L0
->isUsedOutsideOfBlock(Succ0
))
380 if (NLoads
* Size1
>= MagicCompileTimeControl
)
382 if (LoadInst
*L1
= canHoistFromBlock(Succ1
, L0
)) {
383 bool Res
= hoistLoad(BB
, L0
, L1
);
385 // Don't attempt to hoist above loads that had not been hoisted.
394 /// \brief True when instruction is a sink barrier for a store
397 /// Whenever an instruction could possibly read or modify the
398 /// value being stored or protect against the store from
399 /// happening it is considered a sink barrier.
402 bool MergedLoadStoreMotion::isStoreSinkBarrierInRange(const Instruction
& Start
,
403 const Instruction
& End
,
404 AliasAnalysis::Location
406 return AA
->canInstructionRangeModRef(Start
, End
, Loc
, AliasAnalysis::ModRef
);
410 /// \brief Check if \p BB contains a store to the same address as \p SI
412 /// \return The store in \p when it is safe to sink. Otherwise return Null.
414 StoreInst
*MergedLoadStoreMotion::canSinkFromBlock(BasicBlock
*BB1
,
416 DEBUG(dbgs() << "can Sink? : "; Store0
->dump(); dbgs() << "\n");
417 BasicBlock
*BB0
= Store0
->getParent();
418 for (BasicBlock::reverse_iterator RBI
= BB1
->rbegin(), RBE
= BB1
->rend();
420 Instruction
*Inst
= &*RBI
;
422 if (!isa
<StoreInst
>(Inst
))
425 StoreInst
*Store1
= cast
<StoreInst
>(Inst
);
427 AliasAnalysis::Location Loc0
= AA
->getLocation(Store0
);
428 AliasAnalysis::Location Loc1
= AA
->getLocation(Store1
);
429 if (AA
->isMustAlias(Loc0
, Loc1
) && Store0
->isSameOperationAs(Store1
) &&
430 !isStoreSinkBarrierInRange(*(std::next(BasicBlock::iterator(Store1
))),
431 BB1
->back(), Loc1
) &&
432 !isStoreSinkBarrierInRange(*(std::next(BasicBlock::iterator(Store0
))),
433 BB0
->back(), Loc0
)) {
441 /// \brief Create a PHI node in BB for the operands of S0 and S1
443 PHINode
*MergedLoadStoreMotion::getPHIOperand(BasicBlock
*BB
, StoreInst
*S0
,
445 // Create a phi if the values mismatch.
447 Value
*Opd1
= S0
->getValueOperand();
448 Value
*Opd2
= S1
->getValueOperand();
450 NewPN
= PHINode::Create(Opd1
->getType(), 2, Opd2
->getName() + ".sink",
452 NewPN
->addIncoming(Opd1
, S0
->getParent());
453 NewPN
->addIncoming(Opd2
, S1
->getParent());
454 if (NewPN
->getType()->getScalarType()->isPointerTy()) {
455 // Notify AA of the new value.
456 AA
->copyValue(Opd1
, NewPN
);
457 AA
->copyValue(Opd2
, NewPN
);
458 // AA needs to be informed when a PHI-use of the pointer value is added
459 for (unsigned I
= 0, E
= NewPN
->getNumIncomingValues(); I
!= E
; ++I
) {
460 unsigned J
= PHINode::getOperandNumForIncomingValue(I
);
461 AA
->addEscapingUse(NewPN
->getOperandUse(J
));
464 MD
->invalidateCachedPointerInfo(NewPN
);
471 /// \brief Merge two stores to same address and sink into \p BB
473 /// Also sinks GEP instruction computing the store address
475 bool MergedLoadStoreMotion::sinkStore(BasicBlock
*BB
, StoreInst
*S0
,
477 // Only one definition?
478 Instruction
*A0
= dyn_cast
<Instruction
>(S0
->getPointerOperand());
479 Instruction
*A1
= dyn_cast
<Instruction
>(S1
->getPointerOperand());
480 if (A0
&& A1
&& A0
->isIdenticalTo(A1
) && A0
->hasOneUse() &&
481 (A0
->getParent() == S0
->getParent()) && A1
->hasOneUse() &&
482 (A1
->getParent() == S1
->getParent()) && isa
<GetElementPtrInst
>(A0
)) {
483 DEBUG(dbgs() << "Sink Instruction into BB \n"; BB
->dump();
484 dbgs() << "Instruction Left\n"; S0
->dump(); dbgs() << "\n";
485 dbgs() << "Instruction Right\n"; S1
->dump(); dbgs() << "\n");
486 // Hoist the instruction.
487 BasicBlock::iterator InsertPt
= BB
->getFirstInsertionPt();
488 // Intersect optional metadata.
489 S0
->intersectOptionalDataWith(S1
);
490 S0
->dropUnknownMetadata();
492 // Create the new store to be inserted at the join point.
493 StoreInst
*SNew
= (StoreInst
*)(S0
->clone());
494 Instruction
*ANew
= A0
->clone();
495 AA
->copyValue(S0
, SNew
);
496 SNew
->insertBefore(InsertPt
);
497 ANew
->insertBefore(SNew
);
499 assert(S0
->getParent() == A0
->getParent());
500 assert(S1
->getParent() == A1
->getParent());
502 PHINode
*NewPN
= getPHIOperand(BB
, S0
, S1
);
503 // New PHI operand? Use it.
505 SNew
->setOperand(0, NewPN
);
506 removeInstruction(S0
);
507 removeInstruction(S1
);
508 A0
->replaceAllUsesWith(ANew
);
509 removeInstruction(A0
);
510 A1
->replaceAllUsesWith(ANew
);
511 removeInstruction(A1
);
518 /// \brief True when two stores are equivalent and can sink into the footer
520 /// Starting from a diamond tail block, iterate over the instructions in one
521 /// predecessor block and try to match a store in the second predecessor.
523 bool MergedLoadStoreMotion::mergeStores(BasicBlock
*T
) {
525 bool MergedStores
= false;
526 assert(T
&& "Footer of a diamond cannot be empty");
528 pred_iterator PI
= pred_begin(T
), E
= pred_end(T
);
530 BasicBlock
*Pred0
= *PI
;
532 BasicBlock
*Pred1
= *PI
;
534 // tail block of a diamond/hammock?
538 return false; // No. More than 2 predecessors.
540 // #Instructions in Succ1 for Compile Time Control
541 int Size1
= Pred1
->size();
544 for (BasicBlock::reverse_iterator RBI
= Pred0
->rbegin(), RBE
= Pred0
->rend();
547 Instruction
*I
= &*RBI
;
550 // Sink move non-simple (atomic, volatile) stores
551 if (!isa
<StoreInst
>(I
))
553 StoreInst
*S0
= (StoreInst
*)I
;
558 if (NStores
* Size1
>= MagicCompileTimeControl
)
560 if (StoreInst
*S1
= canSinkFromBlock(Pred1
, S0
)) {
561 bool Res
= sinkStore(T
, S0
, S1
);
563 // Don't attempt to sink below stores that had to stick around
564 // But after removal of a store and some of its feeding
565 // instruction search again from the beginning since the iterator
566 // is likely stale at this point.
570 RBI
= Pred0
->rbegin();
572 DEBUG(dbgs() << "Search again\n"; Instruction
*I
= &*RBI
; I
->dump());
579 /// \brief Run the transformation for each function
581 bool MergedLoadStoreMotion::runOnFunction(Function
&F
) {
582 MD
= &getAnalysis
<MemoryDependenceAnalysis
>();
583 AA
= &getAnalysis
<AliasAnalysis
>();
585 bool Changed
= false;
586 DEBUG(dbgs() << "Instruction Merger\n");
588 // Merge unconditional branches, allowing PRE to catch more
589 // optimization opportunities.
590 for (Function::iterator FI
= F
.begin(), FE
= F
.end(); FI
!= FE
;) {
591 BasicBlock
*BB
= FI
++;
593 // Hoist equivalent loads and sink stores
594 // outside diamonds when possible
595 if (isDiamondHead(BB
)) {
596 Changed
|= mergeLoads(BB
);
597 Changed
|= mergeStores(getDiamondTail(BB
));