1 //===- MergedLoadStoreMotion.cpp - merge and hoist/sink load/stores -------===//
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 //! \file
10 //! This pass performs merges of loads and stores on both sides of a
11 //  diamond (hammock). It hoists the loads and sinks the stores.
12 //
13 // The algorithm iteratively hoists two loads to the same address out of a
14 // diamond (hammock) and merges them into a single load in the header. Similar
15 // it sinks and merges two stores to the tail block (footer). The algorithm
16 // iterates over the instructions of one side of the diamond and attempts to
17 // find a matching load/store on the other side. New tail/footer block may be
18 // insterted if the tail/footer block has more predecessors (not only the two
19 // predecessors that are forming the diamond). It hoists / sinks when it thinks
20 // it safe to do so.  This optimization helps with eg. hiding load latencies,
21 // triggering if-conversion, and reducing static code size.
22 //
23 // NOTE: This code no longer performs load hoisting, it is subsumed by GVNHoist.
24 //
25 //===----------------------------------------------------------------------===//
26 //
27 //
28 // Example:
29 // Diamond shaped code before merge:
30 //
31 //            header:
32 //                     br %cond, label %if.then, label %if.else
33 //                        +                    +
34 //                       +                      +
35 //                      +                        +
36 //            if.then:                         if.else:
37 //               %lt = load %addr_l               %le = load %addr_l
38 //               <use %lt>                        <use %le>
39 //               <...>                            <...>
40 //               store %st, %addr_s               store %se, %addr_s
41 //               br label %if.end                 br label %if.end
42 //                     +                         +
43 //                      +                       +
44 //                       +                     +
45 //            if.end ("footer"):
46 //                     <...>
47 //
48 // Diamond shaped code after merge:
49 //
50 //            header:
51 //                     %l = load %addr_l
52 //                     br %cond, label %if.then, label %if.else
53 //                        +                    +
54 //                       +                      +
55 //                      +                        +
56 //            if.then:                         if.else:
57 //               <use %l>                         <use %l>
58 //               <...>                            <...>
59 //               br label %if.end                 br label %if.end
60 //                      +                        +
61 //                       +                      +
62 //                        +                    +
63 //            if.end ("footer"):
64 //                     %s.sink = phi [%st, if.then], [%se, if.else]
65 //                     <...>
66 //                     store %s.sink, %addr_s
67 //                     <...>
68 //
69 //
70 //===----------------------- TODO -----------------------------------------===//
71 //
72 // 1) Generalize to regions other than diamonds
73 // 2) Be more aggressive merging memory operations
74 // Note that both changes require register pressure control
75 //
76 //===----------------------------------------------------------------------===//
77 
78 #include "llvm/Transforms/Scalar/MergedLoadStoreMotion.h"
79 #include "llvm/Analysis/AliasAnalysis.h"
80 #include "llvm/Analysis/GlobalsModRef.h"
81 #include "llvm/IR/Instructions.h"
82 #include "llvm/InitializePasses.h"
83 #include "llvm/Support/Debug.h"
84 #include "llvm/Support/raw_ostream.h"
85 #include "llvm/Transforms/Scalar.h"
86 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
87 
88 using namespace llvm;
89 
90 #define DEBUG_TYPE "mldst-motion"
91 
92 namespace {
93 //===----------------------------------------------------------------------===//
94 //                         MergedLoadStoreMotion Pass
95 //===----------------------------------------------------------------------===//
96 class MergedLoadStoreMotion {
97   AliasAnalysis *AA = nullptr;
98 
99   // The mergeLoad/Store algorithms could have Size0 * Size1 complexity,
100   // where Size0 and Size1 are the #instructions on the two sides of
101   // the diamond. The constant chosen here is arbitrary. Compiler Time
102   // Control is enforced by the check Size0 * Size1 < MagicCompileTimeControl.
103   const int MagicCompileTimeControl = 250;
104 
105   const bool SplitFooterBB;
106 public:
107   MergedLoadStoreMotion(bool SplitFooterBB) : SplitFooterBB(SplitFooterBB) {}
108   bool run(Function &F, AliasAnalysis &AA);
109 
110 private:
111   BasicBlock *getDiamondTail(BasicBlock *BB);
112   bool isDiamondHead(BasicBlock *BB);
113   // Routines for sinking stores
114   StoreInst *canSinkFromBlock(BasicBlock *BB, StoreInst *SI);
115   PHINode *getPHIOperand(BasicBlock *BB, StoreInst *S0, StoreInst *S1);
116   bool isStoreSinkBarrierInRange(const Instruction &Start,
117                                  const Instruction &End, MemoryLocation Loc);
118   bool canSinkStoresAndGEPs(StoreInst *S0, StoreInst *S1) const;
119   void sinkStoresAndGEPs(BasicBlock *BB, StoreInst *SinkCand,
120                          StoreInst *ElseInst);
121   bool mergeStores(BasicBlock *BB);
122 };
123 } // end anonymous namespace
124 
125 ///
126 /// Return tail block of a diamond.
127 ///
128 BasicBlock *MergedLoadStoreMotion::getDiamondTail(BasicBlock *BB) {
129   assert(isDiamondHead(BB) && "Basic block is not head of a diamond");
130   return BB->getTerminator()->getSuccessor(0)->getSingleSuccessor();
131 }
132 
133 ///
134 /// True when BB is the head of a diamond (hammock)
135 ///
136 bool MergedLoadStoreMotion::isDiamondHead(BasicBlock *BB) {
137   if (!BB)
138     return false;
139   auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
140   if (!BI || !BI->isConditional())
141     return false;
142 
143   BasicBlock *Succ0 = BI->getSuccessor(0);
144   BasicBlock *Succ1 = BI->getSuccessor(1);
145 
146   if (!Succ0->getSinglePredecessor())
147     return false;
148   if (!Succ1->getSinglePredecessor())
149     return false;
150 
151   BasicBlock *Succ0Succ = Succ0->getSingleSuccessor();
152   BasicBlock *Succ1Succ = Succ1->getSingleSuccessor();
153   // Ignore triangles.
154   if (!Succ0Succ || !Succ1Succ || Succ0Succ != Succ1Succ)
155     return false;
156   return true;
157 }
158 
159 
160 ///
161 /// True when instruction is a sink barrier for a store
162 /// located in Loc
163 ///
164 /// Whenever an instruction could possibly read or modify the
165 /// value being stored or protect against the store from
166 /// happening it is considered a sink barrier.
167 ///
168 bool MergedLoadStoreMotion::isStoreSinkBarrierInRange(const Instruction &Start,
169                                                       const Instruction &End,
170                                                       MemoryLocation Loc) {
171   for (const Instruction &Inst :
172        make_range(Start.getIterator(), End.getIterator()))
173     if (Inst.mayThrow())
174       return true;
175   return AA->canInstructionRangeModRef(Start, End, Loc, ModRefInfo::ModRef);
176 }
177 
178 ///
179 /// Check if \p BB contains a store to the same address as \p SI
180 ///
181 /// \return The store in \p  when it is safe to sink. Otherwise return Null.
182 ///
183 StoreInst *MergedLoadStoreMotion::canSinkFromBlock(BasicBlock *BB1,
184                                                    StoreInst *Store0) {
185   LLVM_DEBUG(dbgs() << "can Sink? : "; Store0->dump(); dbgs() << "\n");
186   BasicBlock *BB0 = Store0->getParent();
187   for (Instruction &Inst : reverse(*BB1)) {
188     auto *Store1 = dyn_cast<StoreInst>(&Inst);
189     if (!Store1)
190       continue;
191 
192     MemoryLocation Loc0 = MemoryLocation::get(Store0);
193     MemoryLocation Loc1 = MemoryLocation::get(Store1);
194     if (AA->isMustAlias(Loc0, Loc1) && Store0->isSameOperationAs(Store1) &&
195         !isStoreSinkBarrierInRange(*Store1->getNextNode(), BB1->back(), Loc1) &&
196         !isStoreSinkBarrierInRange(*Store0->getNextNode(), BB0->back(), Loc0)) {
197       return Store1;
198     }
199   }
200   return nullptr;
201 }
202 
203 ///
204 /// Create a PHI node in BB for the operands of S0 and S1
205 ///
206 PHINode *MergedLoadStoreMotion::getPHIOperand(BasicBlock *BB, StoreInst *S0,
207                                               StoreInst *S1) {
208   // Create a phi if the values mismatch.
209   Value *Opd1 = S0->getValueOperand();
210   Value *Opd2 = S1->getValueOperand();
211   if (Opd1 == Opd2)
212     return nullptr;
213 
214   auto *NewPN = PHINode::Create(Opd1->getType(), 2, Opd2->getName() + ".sink",
215                                 &BB->front());
216   NewPN->applyMergedLocation(S0->getDebugLoc(), S1->getDebugLoc());
217   NewPN->addIncoming(Opd1, S0->getParent());
218   NewPN->addIncoming(Opd2, S1->getParent());
219   return NewPN;
220 }
221 
222 ///
223 /// Check if 2 stores can be sunk together with corresponding GEPs
224 ///
225 bool MergedLoadStoreMotion::canSinkStoresAndGEPs(StoreInst *S0,
226                                                  StoreInst *S1) const {
227   auto *A0 = dyn_cast<Instruction>(S0->getPointerOperand());
228   auto *A1 = dyn_cast<Instruction>(S1->getPointerOperand());
229   return A0 && A1 && A0->isIdenticalTo(A1) && A0->hasOneUse() &&
230          (A0->getParent() == S0->getParent()) && A1->hasOneUse() &&
231          (A1->getParent() == S1->getParent()) && isa<GetElementPtrInst>(A0);
232 }
233 
234 ///
235 /// Merge two stores to same address and sink into \p BB
236 ///
237 /// Also sinks GEP instruction computing the store address
238 ///
239 void MergedLoadStoreMotion::sinkStoresAndGEPs(BasicBlock *BB, StoreInst *S0,
240                                               StoreInst *S1) {
241   // Only one definition?
242   auto *A0 = dyn_cast<Instruction>(S0->getPointerOperand());
243   auto *A1 = dyn_cast<Instruction>(S1->getPointerOperand());
244   LLVM_DEBUG(dbgs() << "Sink Instruction into BB \n"; BB->dump();
245              dbgs() << "Instruction Left\n"; S0->dump(); dbgs() << "\n";
246              dbgs() << "Instruction Right\n"; S1->dump(); dbgs() << "\n");
247   // Hoist the instruction.
248   BasicBlock::iterator InsertPt = BB->getFirstInsertionPt();
249   // Intersect optional metadata.
250   S0->andIRFlags(S1);
251   S0->dropUnknownNonDebugMetadata();
252 
253   // Create the new store to be inserted at the join point.
254   StoreInst *SNew = cast<StoreInst>(S0->clone());
255   Instruction *ANew = A0->clone();
256   SNew->insertBefore(&*InsertPt);
257   ANew->insertBefore(SNew);
258 
259   assert(S0->getParent() == A0->getParent());
260   assert(S1->getParent() == A1->getParent());
261 
262   // New PHI operand? Use it.
263   if (PHINode *NewPN = getPHIOperand(BB, S0, S1))
264     SNew->setOperand(0, NewPN);
265   S0->eraseFromParent();
266   S1->eraseFromParent();
267   A0->replaceAllUsesWith(ANew);
268   A0->eraseFromParent();
269   A1->replaceAllUsesWith(ANew);
270   A1->eraseFromParent();
271 }
272 
273 ///
274 /// True when two stores are equivalent and can sink into the footer
275 ///
276 /// Starting from a diamond head block, iterate over the instructions in one
277 /// successor block and try to match a store in the second successor.
278 ///
279 bool MergedLoadStoreMotion::mergeStores(BasicBlock *HeadBB) {
280 
281   bool MergedStores = false;
282   BasicBlock *TailBB = getDiamondTail(HeadBB);
283   BasicBlock *SinkBB = TailBB;
284   assert(SinkBB && "Footer of a diamond cannot be empty");
285 
286   succ_iterator SI = succ_begin(HeadBB);
287   assert(SI != succ_end(HeadBB) && "Diamond head cannot have zero successors");
288   BasicBlock *Pred0 = *SI;
289   ++SI;
290   assert(SI != succ_end(HeadBB) && "Diamond head cannot have single successor");
291   BasicBlock *Pred1 = *SI;
292   // tail block  of a diamond/hammock?
293   if (Pred0 == Pred1)
294     return false; // No.
295   // bail out early if we can not merge into the footer BB
296   if (!SplitFooterBB && TailBB->hasNPredecessorsOrMore(3))
297     return false;
298   // #Instructions in Pred1 for Compile Time Control
299   auto InstsNoDbg = Pred1->instructionsWithoutDebug();
300   int Size1 = std::distance(InstsNoDbg.begin(), InstsNoDbg.end());
301   int NStores = 0;
302 
303   for (BasicBlock::reverse_iterator RBI = Pred0->rbegin(), RBE = Pred0->rend();
304        RBI != RBE;) {
305 
306     Instruction *I = &*RBI;
307     ++RBI;
308 
309     // Don't sink non-simple (atomic, volatile) stores.
310     auto *S0 = dyn_cast<StoreInst>(I);
311     if (!S0 || !S0->isSimple())
312       continue;
313 
314     ++NStores;
315     if (NStores * Size1 >= MagicCompileTimeControl)
316       break;
317     if (StoreInst *S1 = canSinkFromBlock(Pred1, S0)) {
318       if (!canSinkStoresAndGEPs(S0, S1))
319         // Don't attempt to sink below stores that had to stick around
320         // But after removal of a store and some of its feeding
321         // instruction search again from the beginning since the iterator
322         // is likely stale at this point.
323         break;
324 
325       if (SinkBB == TailBB && TailBB->hasNPredecessorsOrMore(3)) {
326         // We have more than 2 predecessors. Insert a new block
327         // postdominating 2 predecessors we're going to sink from.
328         SinkBB = SplitBlockPredecessors(TailBB, {Pred0, Pred1}, ".sink.split");
329         if (!SinkBB)
330           break;
331       }
332 
333       MergedStores = true;
334       sinkStoresAndGEPs(SinkBB, S0, S1);
335       RBI = Pred0->rbegin();
336       RBE = Pred0->rend();
337       LLVM_DEBUG(dbgs() << "Search again\n"; Instruction *I = &*RBI; I->dump());
338     }
339   }
340   return MergedStores;
341 }
342 
343 bool MergedLoadStoreMotion::run(Function &F, AliasAnalysis &AA) {
344   this->AA = &AA;
345 
346   bool Changed = false;
347   LLVM_DEBUG(dbgs() << "Instruction Merger\n");
348 
349   // Merge unconditional branches, allowing PRE to catch more
350   // optimization opportunities.
351   // This loop doesn't care about newly inserted/split blocks
352   // since they never will be diamond heads.
353   for (BasicBlock &BB : make_early_inc_range(F))
354     // Hoist equivalent loads and sink stores
355     // outside diamonds when possible
356     if (isDiamondHead(&BB))
357       Changed |= mergeStores(&BB);
358   return Changed;
359 }
360 
361 namespace {
362 class MergedLoadStoreMotionLegacyPass : public FunctionPass {
363   const bool SplitFooterBB;
364 public:
365   static char ID; // Pass identification, replacement for typeid
366   MergedLoadStoreMotionLegacyPass(bool SplitFooterBB = false)
367       : FunctionPass(ID), SplitFooterBB(SplitFooterBB) {
368     initializeMergedLoadStoreMotionLegacyPassPass(
369         *PassRegistry::getPassRegistry());
370   }
371 
372   ///
373   /// Run the transformation for each function
374   ///
375   bool runOnFunction(Function &F) override {
376     if (skipFunction(F))
377       return false;
378     MergedLoadStoreMotion Impl(SplitFooterBB);
379     return Impl.run(F, getAnalysis<AAResultsWrapperPass>().getAAResults());
380   }
381 
382 private:
383   void getAnalysisUsage(AnalysisUsage &AU) const override {
384     if (!SplitFooterBB)
385       AU.setPreservesCFG();
386     AU.addRequired<AAResultsWrapperPass>();
387     AU.addPreserved<GlobalsAAWrapperPass>();
388   }
389 };
390 
391 char MergedLoadStoreMotionLegacyPass::ID = 0;
392 } // anonymous namespace
393 
394 ///
395 /// createMergedLoadStoreMotionPass - The public interface to this file.
396 ///
397 FunctionPass *llvm::createMergedLoadStoreMotionPass(bool SplitFooterBB) {
398   return new MergedLoadStoreMotionLegacyPass(SplitFooterBB);
399 }
400 
401 INITIALIZE_PASS_BEGIN(MergedLoadStoreMotionLegacyPass, "mldst-motion",
402                       "MergedLoadStoreMotion", false, false)
403 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
404 INITIALIZE_PASS_END(MergedLoadStoreMotionLegacyPass, "mldst-motion",
405                     "MergedLoadStoreMotion", false, false)
406 
407 PreservedAnalyses
408 MergedLoadStoreMotionPass::run(Function &F, FunctionAnalysisManager &AM) {
409   MergedLoadStoreMotion Impl(Options.SplitFooterBB);
410   auto &AA = AM.getResult<AAManager>(F);
411   if (!Impl.run(F, AA))
412     return PreservedAnalyses::all();
413 
414   PreservedAnalyses PA;
415   if (!Options.SplitFooterBB)
416     PA.preserveSet<CFGAnalyses>();
417   return PA;
418 }
419 
420 void MergedLoadStoreMotionPass::printPipeline(
421     raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
422   static_cast<PassInfoMixin<MergedLoadStoreMotionPass> *>(this)->printPipeline(
423       OS, MapClassName2PassName);
424   OS << "<";
425   OS << (Options.SplitFooterBB ? "" : "no-") << "split-footer-bb";
426   OS << ">";
427 }
428