]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | //===- MergedLoadStoreMotion.cpp - merge and hoist/sink load/stores -------===// |
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 | //! \file | |
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. | |
13 | // | |
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. | |
21 | // | |
22 | //===----------------------------------------------------------------------===// | |
23 | // | |
24 | // | |
25 | // Example: | |
26 | // Diamond shaped code before merge: | |
27 | // | |
28 | // header: | |
29 | // br %cond, label %if.then, label %if.else | |
30 | // + + | |
31 | // + + | |
32 | // + + | |
33 | // if.then: if.else: | |
34 | // %lt = load %addr_l %le = load %addr_l | |
35 | // <use %lt> <use %le> | |
36 | // <...> <...> | |
37 | // store %st, %addr_s store %se, %addr_s | |
38 | // br label %if.end br label %if.end | |
39 | // + + | |
40 | // + + | |
41 | // + + | |
42 | // if.end ("footer"): | |
43 | // <...> | |
44 | // | |
45 | // Diamond shaped code after merge: | |
46 | // | |
47 | // header: | |
48 | // %l = load %addr_l | |
49 | // br %cond, label %if.then, label %if.else | |
50 | // + + | |
51 | // + + | |
52 | // + + | |
53 | // if.then: if.else: | |
54 | // <use %l> <use %l> | |
55 | // <...> <...> | |
56 | // br label %if.end br label %if.end | |
57 | // + + | |
58 | // + + | |
59 | // + + | |
60 | // if.end ("footer"): | |
61 | // %s.sink = phi [%st, if.then], [%se, if.else] | |
62 | // <...> | |
63 | // store %s.sink, %addr_s | |
64 | // <...> | |
65 | // | |
66 | // | |
67 | //===----------------------- TODO -----------------------------------------===// | |
68 | // | |
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 | |
72 | // | |
73 | //===----------------------------------------------------------------------===// | |
74 | ||
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" | |
92 | #include <vector> | |
93 | using namespace llvm; | |
94 | ||
95 | #define DEBUG_TYPE "mldst-motion" | |
96 | ||
97 | //===----------------------------------------------------------------------===// | |
98 | // MergedLoadStoreMotion Pass | |
99 | //===----------------------------------------------------------------------===// | |
100 | ||
101 | namespace { | |
102 | class MergedLoadStoreMotion : public FunctionPass { | |
103 | AliasAnalysis *AA; | |
104 | MemoryDependenceAnalysis *MD; | |
105 | ||
106 | public: | |
107 | static char ID; // Pass identification, replacement for typeid | |
108 | explicit MergedLoadStoreMotion(void) | |
109 | : FunctionPass(ID), MD(nullptr), MagicCompileTimeControl(250) { | |
110 | initializeMergedLoadStoreMotionPass(*PassRegistry::getPassRegistry()); | |
111 | } | |
112 | ||
113 | bool runOnFunction(Function &F) override; | |
114 | ||
115 | private: | |
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>(); | |
122 | } | |
123 | ||
124 | // Helper routines | |
125 | ||
126 | /// | |
127 | /// \brief Remove instruction from parent and update memory dependence | |
128 | /// analysis. | |
129 | /// | |
130 | void removeInstruction(Instruction *Inst); | |
131 | BasicBlock *getDiamondTail(BasicBlock *BB); | |
132 | bool isDiamondHead(BasicBlock *BB); | |
133 | // Routines for hoisting loads | |
85aaf69f SL |
134 | bool isLoadHoistBarrierInRange(const Instruction& Start, |
135 | const Instruction& End, | |
136 | LoadInst* LI); | |
1a4d82fc JJ |
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); | |
85aaf69f SL |
146 | bool isStoreSinkBarrierInRange(const Instruction& Start, |
147 | const Instruction& End, | |
148 | AliasAnalysis::Location Loc); | |
1a4d82fc JJ |
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; | |
156 | }; | |
157 | ||
158 | char MergedLoadStoreMotion::ID = 0; | |
159 | } | |
160 | ||
161 | /// | |
162 | /// \brief createMergedLoadStoreMotionPass - The public interface to this file. | |
163 | /// | |
164 | FunctionPass *llvm::createMergedLoadStoreMotionPass() { | |
165 | return new MergedLoadStoreMotion(); | |
166 | } | |
167 | ||
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) | |
175 | ||
176 | /// | |
177 | /// \brief Remove instruction from parent and update memory dependence analysis. | |
178 | /// | |
179 | void MergedLoadStoreMotion::removeInstruction(Instruction *Inst) { | |
180 | // Notify the memory dependence analysis. | |
181 | if (MD) { | |
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); | |
187 | } | |
188 | } | |
189 | Inst->eraseFromParent(); | |
190 | } | |
191 | ||
192 | /// | |
193 | /// \brief Return tail block of a diamond. | |
194 | /// | |
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); | |
200 | return Tail; | |
201 | } | |
202 | ||
203 | /// | |
204 | /// \brief True when BB is the head of a diamond (hammock) | |
205 | /// | |
206 | bool MergedLoadStoreMotion::isDiamondHead(BasicBlock *BB) { | |
207 | if (!BB) | |
208 | return false; | |
209 | if (!isa<BranchInst>(BB->getTerminator())) | |
210 | return false; | |
211 | if (BB->getTerminator()->getNumSuccessors() != 2) | |
212 | return false; | |
213 | ||
214 | BranchInst *BI = (BranchInst *)(BB->getTerminator()); | |
215 | BasicBlock *Succ0 = BI->getSuccessor(0); | |
216 | BasicBlock *Succ1 = BI->getSuccessor(1); | |
217 | ||
218 | if (!Succ0->getSinglePredecessor() || | |
219 | Succ0->getTerminator()->getNumSuccessors() != 1) | |
220 | return false; | |
221 | if (!Succ1->getSinglePredecessor() || | |
222 | Succ1->getTerminator()->getNumSuccessors() != 1) | |
223 | return false; | |
224 | ||
225 | BasicBlock *Tail = Succ0->getTerminator()->getSuccessor(0); | |
226 | // Ignore triangles. | |
227 | if (Succ1->getTerminator()->getSuccessor(0) != Tail) | |
228 | return false; | |
229 | return true; | |
230 | } | |
231 | ||
232 | /// | |
233 | /// \brief True when instruction is a hoist barrier for a load | |
234 | /// | |
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. | |
238 | /// | |
85aaf69f SL |
239 | |
240 | bool MergedLoadStoreMotion::isLoadHoistBarrierInRange(const Instruction& Start, | |
241 | const Instruction& End, | |
242 | LoadInst* LI) { | |
243 | AliasAnalysis::Location Loc = AA->getLocation(LI); | |
244 | return AA->canInstructionRangeModRef(Start, End, Loc, AliasAnalysis::Mod); | |
1a4d82fc JJ |
245 | } |
246 | ||
247 | /// | |
248 | /// \brief Decide if a load can be hoisted | |
249 | /// | |
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. | |
253 | /// | |
85aaf69f SL |
254 | LoadInst *MergedLoadStoreMotion::canHoistFromBlock(BasicBlock *BB1, |
255 | LoadInst *Load0) { | |
1a4d82fc | 256 | |
85aaf69f | 257 | for (BasicBlock::iterator BBI = BB1->begin(), BBE = BB1->end(); BBI != BBE; |
1a4d82fc JJ |
258 | ++BBI) { |
259 | Instruction *Inst = BBI; | |
260 | ||
261 | // Only merge and hoist loads when their result in used only in BB | |
85aaf69f | 262 | if (!isa<LoadInst>(Inst) || Inst->isUsedOutsideOfBlock(BB1)) |
1a4d82fc JJ |
263 | continue; |
264 | ||
85aaf69f SL |
265 | LoadInst *Load1 = dyn_cast<LoadInst>(Inst); |
266 | BasicBlock *BB0 = Load0->getParent(); | |
267 | ||
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)) { | |
273 | return Load1; | |
1a4d82fc JJ |
274 | } |
275 | } | |
85aaf69f | 276 | return nullptr; |
1a4d82fc JJ |
277 | } |
278 | ||
279 | /// | |
280 | /// \brief Merge two equivalent instructions \p HoistCand and \p ElseInst into | |
281 | /// \p BB | |
282 | /// | |
283 | /// BB is the head of a diamond | |
284 | /// | |
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); | |
293 | ||
294 | // Intersect optional metadata. | |
295 | HoistCand->intersectOptionalDataWith(ElseInst); | |
296 | HoistCand->dropUnknownMetadata(); | |
297 | ||
298 | // Prepend point for instruction insert | |
299 | Instruction *HoistPt = BB->getTerminator(); | |
300 | ||
301 | // Merged instruction | |
302 | Instruction *HoistedInst = HoistCand->clone(); | |
303 | ||
304 | // Notify AA of the new value. | |
305 | if (isa<LoadInst>(HoistCand)) | |
306 | AA->copyValue(HoistCand, HoistedInst); | |
307 | ||
308 | // Hoist instruction. | |
309 | HoistedInst->insertBefore(HoistPt); | |
310 | ||
311 | HoistCand->replaceAllUsesWith(HoistedInst); | |
312 | removeInstruction(HoistCand); | |
313 | // Replace the else block instruction. | |
314 | ElseInst->replaceAllUsesWith(HoistedInst); | |
315 | removeInstruction(ElseInst); | |
316 | } | |
317 | ||
318 | /// | |
319 | /// \brief Return true if no operand of \p I is defined in I's parent block | |
320 | /// | |
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) | |
326 | return false; | |
327 | } | |
328 | return true; | |
329 | } | |
330 | ||
331 | /// | |
332 | /// \brief Merge two equivalent loads and GEPs and hoist into diamond head | |
333 | /// | |
334 | bool MergedLoadStoreMotion::hoistLoad(BasicBlock *BB, LoadInst *L0, | |
335 | LoadInst *L1) { | |
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); | |
348 | return true; | |
349 | } else | |
350 | return false; | |
351 | } | |
352 | ||
353 | /// | |
354 | /// \brief Try to hoist two loads to same address into diamond header | |
355 | /// | |
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. | |
358 | /// | |
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(); | |
367 | int NLoads = 0; | |
368 | for (BasicBlock::iterator BBI = Succ0->begin(), BBE = Succ0->end(); | |
369 | BBI != BBE;) { | |
370 | ||
371 | Instruction *I = BBI; | |
372 | ++BBI; | |
1a4d82fc JJ |
373 | |
374 | // Only move non-simple (atomic, volatile) loads. | |
85aaf69f SL |
375 | LoadInst *L0 = dyn_cast<LoadInst>(I); |
376 | if (!L0 || !L0->isSimple() || L0->isUsedOutsideOfBlock(Succ0)) | |
1a4d82fc JJ |
377 | continue; |
378 | ||
379 | ++NLoads; | |
380 | if (NLoads * Size1 >= MagicCompileTimeControl) | |
381 | break; | |
382 | if (LoadInst *L1 = canHoistFromBlock(Succ1, L0)) { | |
383 | bool Res = hoistLoad(BB, L0, L1); | |
384 | MergedLoads |= Res; | |
385 | // Don't attempt to hoist above loads that had not been hoisted. | |
386 | if (!Res) | |
387 | break; | |
388 | } | |
389 | } | |
390 | return MergedLoads; | |
391 | } | |
392 | ||
393 | /// | |
85aaf69f SL |
394 | /// \brief True when instruction is a sink barrier for a store |
395 | /// located in Loc | |
396 | /// | |
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. | |
400 | /// | |
401 | ||
402 | bool MergedLoadStoreMotion::isStoreSinkBarrierInRange(const Instruction& Start, | |
403 | const Instruction& End, | |
404 | AliasAnalysis::Location | |
405 | Loc) { | |
c34b1796 | 406 | return AA->canInstructionRangeModRef(Start, End, Loc, AliasAnalysis::ModRef); |
1a4d82fc JJ |
407 | } |
408 | ||
409 | /// | |
410 | /// \brief Check if \p BB contains a store to the same address as \p SI | |
411 | /// | |
412 | /// \return The store in \p when it is safe to sink. Otherwise return Null. | |
413 | /// | |
85aaf69f SL |
414 | StoreInst *MergedLoadStoreMotion::canSinkFromBlock(BasicBlock *BB1, |
415 | StoreInst *Store0) { | |
416 | DEBUG(dbgs() << "can Sink? : "; Store0->dump(); dbgs() << "\n"); | |
c34b1796 | 417 | BasicBlock *BB0 = Store0->getParent(); |
85aaf69f | 418 | for (BasicBlock::reverse_iterator RBI = BB1->rbegin(), RBE = BB1->rend(); |
1a4d82fc JJ |
419 | RBI != RBE; ++RBI) { |
420 | Instruction *Inst = &*RBI; | |
421 | ||
85aaf69f SL |
422 | if (!isa<StoreInst>(Inst)) |
423 | continue; | |
424 | ||
425 | StoreInst *Store1 = cast<StoreInst>(Inst); | |
85aaf69f SL |
426 | |
427 | AliasAnalysis::Location Loc0 = AA->getLocation(Store0); | |
428 | AliasAnalysis::Location Loc1 = AA->getLocation(Store1); | |
429 | if (AA->isMustAlias(Loc0, Loc1) && Store0->isSameOperationAs(Store1) && | |
c34b1796 AL |
430 | !isStoreSinkBarrierInRange(*(std::next(BasicBlock::iterator(Store1))), |
431 | BB1->back(), Loc1) && | |
432 | !isStoreSinkBarrierInRange(*(std::next(BasicBlock::iterator(Store0))), | |
433 | BB0->back(), Loc0)) { | |
85aaf69f | 434 | return Store1; |
1a4d82fc JJ |
435 | } |
436 | } | |
85aaf69f | 437 | return nullptr; |
1a4d82fc JJ |
438 | } |
439 | ||
440 | /// | |
441 | /// \brief Create a PHI node in BB for the operands of S0 and S1 | |
442 | /// | |
443 | PHINode *MergedLoadStoreMotion::getPHIOperand(BasicBlock *BB, StoreInst *S0, | |
444 | StoreInst *S1) { | |
445 | // Create a phi if the values mismatch. | |
446 | PHINode *NewPN = 0; | |
447 | Value *Opd1 = S0->getValueOperand(); | |
448 | Value *Opd2 = S1->getValueOperand(); | |
449 | if (Opd1 != Opd2) { | |
450 | NewPN = PHINode::Create(Opd1->getType(), 2, Opd2->getName() + ".sink", | |
451 | BB->begin()); | |
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)); | |
462 | } | |
463 | if (MD) | |
464 | MD->invalidateCachedPointerInfo(NewPN); | |
465 | } | |
466 | } | |
467 | return NewPN; | |
468 | } | |
469 | ||
470 | /// | |
471 | /// \brief Merge two stores to same address and sink into \p BB | |
472 | /// | |
473 | /// Also sinks GEP instruction computing the store address | |
474 | /// | |
475 | bool MergedLoadStoreMotion::sinkStore(BasicBlock *BB, StoreInst *S0, | |
476 | StoreInst *S1) { | |
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(); | |
491 | ||
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); | |
498 | ||
499 | assert(S0->getParent() == A0->getParent()); | |
500 | assert(S1->getParent() == A1->getParent()); | |
501 | ||
502 | PHINode *NewPN = getPHIOperand(BB, S0, S1); | |
503 | // New PHI operand? Use it. | |
504 | if (NewPN) | |
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); | |
512 | return true; | |
513 | } | |
514 | return false; | |
515 | } | |
516 | ||
517 | /// | |
518 | /// \brief True when two stores are equivalent and can sink into the footer | |
519 | /// | |
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. | |
522 | /// | |
523 | bool MergedLoadStoreMotion::mergeStores(BasicBlock *T) { | |
524 | ||
525 | bool MergedStores = false; | |
526 | assert(T && "Footer of a diamond cannot be empty"); | |
527 | ||
528 | pred_iterator PI = pred_begin(T), E = pred_end(T); | |
529 | assert(PI != E); | |
530 | BasicBlock *Pred0 = *PI; | |
531 | ++PI; | |
532 | BasicBlock *Pred1 = *PI; | |
533 | ++PI; | |
534 | // tail block of a diamond/hammock? | |
535 | if (Pred0 == Pred1) | |
536 | return false; // No. | |
537 | if (PI != E) | |
538 | return false; // No. More than 2 predecessors. | |
539 | ||
540 | // #Instructions in Succ1 for Compile Time Control | |
541 | int Size1 = Pred1->size(); | |
542 | int NStores = 0; | |
543 | ||
544 | for (BasicBlock::reverse_iterator RBI = Pred0->rbegin(), RBE = Pred0->rend(); | |
545 | RBI != RBE;) { | |
546 | ||
547 | Instruction *I = &*RBI; | |
548 | ++RBI; | |
85aaf69f | 549 | |
1a4d82fc JJ |
550 | // Sink move non-simple (atomic, volatile) stores |
551 | if (!isa<StoreInst>(I)) | |
552 | continue; | |
553 | StoreInst *S0 = (StoreInst *)I; | |
554 | if (!S0->isSimple()) | |
555 | continue; | |
556 | ||
557 | ++NStores; | |
558 | if (NStores * Size1 >= MagicCompileTimeControl) | |
559 | break; | |
560 | if (StoreInst *S1 = canSinkFromBlock(Pred1, S0)) { | |
561 | bool Res = sinkStore(T, S0, S1); | |
562 | MergedStores |= Res; | |
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. | |
567 | if (!Res) | |
568 | break; | |
569 | else { | |
570 | RBI = Pred0->rbegin(); | |
571 | RBE = Pred0->rend(); | |
572 | DEBUG(dbgs() << "Search again\n"; Instruction *I = &*RBI; I->dump()); | |
573 | } | |
574 | } | |
575 | } | |
576 | return MergedStores; | |
577 | } | |
578 | /// | |
579 | /// \brief Run the transformation for each function | |
580 | /// | |
581 | bool MergedLoadStoreMotion::runOnFunction(Function &F) { | |
582 | MD = &getAnalysis<MemoryDependenceAnalysis>(); | |
583 | AA = &getAnalysis<AliasAnalysis>(); | |
584 | ||
585 | bool Changed = false; | |
586 | DEBUG(dbgs() << "Instruction Merger\n"); | |
587 | ||
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++; | |
592 | ||
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)); | |
598 | } | |
599 | } | |
600 | return Changed; | |
601 | } |