Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 1 | //===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===// |
Misha Brukman | b1c9317 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | 482202a | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | f3ebc3f | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Misha Brukman | b1c9317 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | 482202a | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 9 | // |
Chris Lattner | c051768 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 10 | // This pass performs loop invariant code motion, attempting to remove as much |
| 11 | // code from the body of a loop as possible. It does this by either hoisting |
| 12 | // code into the preheader block, or by sinking code to the exit blocks if it is |
| 13 | // safe. This pass also promotes must-aliased memory locations in the loop to |
Chris Lattner | 547192d6 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 14 | // live in registers, thus hoisting and sinking "invariant" loads and stores. |
Chris Lattner | c051768 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 15 | // |
| 16 | // This pass uses alias analysis for two purposes: |
Chris Lattner | 45d67d6 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 17 | // |
Chris Lattner | 289ba2a | 2004-05-23 21:20:19 +0000 | [diff] [blame] | 18 | // 1. Moving loop invariant loads and calls out of loops. If we can determine |
| 19 | // that a load or call inside of a loop never aliases anything stored to, |
| 20 | // we can hoist it or sink it like any other instruction. |
Chris Lattner | 45d67d6 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 21 | // 2. Scalar Promotion of Memory - If there is a store instruction inside of |
| 22 | // the loop, we try to move the store to happen AFTER the loop instead of |
| 23 | // inside of the loop. This can only happen if a few conditions are true: |
| 24 | // A. The pointer stored through is loop invariant |
| 25 | // B. There are no stores or loads in the loop which _may_ alias the |
| 26 | // pointer. There are no calls in the loop which mod/ref the pointer. |
| 27 | // If these conditions are true, we can promote the loads and stores in the |
| 28 | // loop of the pointer to use a temporary alloca'd variable. We then use |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 29 | // the SSAUpdater to construct the appropriate SSA form for the value. |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 30 | // |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 31 | //===----------------------------------------------------------------------===// |
| 32 | |
| 33 | #include "llvm/Transforms/Scalar.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 34 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | a51fa88 | 2002-08-22 21:39:55 +0000 | [diff] [blame] | 35 | #include "llvm/Analysis/AliasAnalysis.h" |
Chris Lattner | 0592bb7 | 2003-03-03 23:32:45 +0000 | [diff] [blame] | 36 | #include "llvm/Analysis/AliasSetTracker.h" |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 37 | #include "llvm/Analysis/BasicAliasAnalysis.h" |
Philip Reames | b54c8e6 | 2016-03-09 22:59:30 +0000 | [diff] [blame] | 38 | #include "llvm/Analysis/CaptureTracking.h" |
Chris Lattner | 030f020 | 2010-08-31 23:00:16 +0000 | [diff] [blame] | 39 | #include "llvm/Analysis/ConstantFolding.h" |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 40 | #include "llvm/Analysis/GlobalsModRef.h" |
Philip Reames | e0a5454 | 2016-03-09 23:07:53 +0000 | [diff] [blame^] | 41 | #include "llvm/Analysis/Loads.h" |
Chris Lattner | 030f020 | 2010-08-31 23:00:16 +0000 | [diff] [blame] | 42 | #include "llvm/Analysis/LoopInfo.h" |
| 43 | #include "llvm/Analysis/LoopPass.h" |
Philip Reames | b54c8e6 | 2016-03-09 22:59:30 +0000 | [diff] [blame] | 44 | #include "llvm/Analysis/MemoryBuiltins.h" |
Chandler Carruth | abfa3e5 | 2014-01-24 01:59:49 +0000 | [diff] [blame] | 45 | #include "llvm/Analysis/ScalarEvolution.h" |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 46 | #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" |
Benjamin Kramer | 799003b | 2015-03-23 19:32:43 +0000 | [diff] [blame] | 47 | #include "llvm/Analysis/TargetLibraryInfo.h" |
Dan Gohman | 75d7d5e | 2011-12-14 23:49:11 +0000 | [diff] [blame] | 48 | #include "llvm/Analysis/ValueTracking.h" |
Chandler Carruth | 1305dc3 | 2014-03-04 11:45:46 +0000 | [diff] [blame] | 49 | #include "llvm/IR/CFG.h" |
Chandler Carruth | 9fb823b | 2013-01-02 11:36:10 +0000 | [diff] [blame] | 50 | #include "llvm/IR/Constants.h" |
| 51 | #include "llvm/IR/DataLayout.h" |
| 52 | #include "llvm/IR/DerivedTypes.h" |
Chandler Carruth | 5ad5f15 | 2014-01-13 09:26:24 +0000 | [diff] [blame] | 53 | #include "llvm/IR/Dominators.h" |
Chandler Carruth | 9fb823b | 2013-01-02 11:36:10 +0000 | [diff] [blame] | 54 | #include "llvm/IR/Instructions.h" |
| 55 | #include "llvm/IR/IntrinsicInst.h" |
| 56 | #include "llvm/IR/LLVMContext.h" |
Chris Lattner | 473988c | 2013-01-05 16:44:07 +0000 | [diff] [blame] | 57 | #include "llvm/IR/Metadata.h" |
Chandler Carruth | aa0ab63 | 2014-03-04 12:09:19 +0000 | [diff] [blame] | 58 | #include "llvm/IR/PredIteratorCache.h" |
Reid Spencer | 7c16caa | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 59 | #include "llvm/Support/CommandLine.h" |
| 60 | #include "llvm/Support/Debug.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 61 | #include "llvm/Support/raw_ostream.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 62 | #include "llvm/Transforms/Utils/Local.h" |
Chandler Carruth | 8765cf7 | 2014-01-25 04:07:24 +0000 | [diff] [blame] | 63 | #include "llvm/Transforms/Utils/LoopUtils.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 64 | #include "llvm/Transforms/Utils/SSAUpdater.h" |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 65 | #include <algorithm> |
Chris Lattner | c051768 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 66 | using namespace llvm; |
Brian Gaeke | 960707c | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 67 | |
Chandler Carruth | 964daaa | 2014-04-22 02:55:47 +0000 | [diff] [blame] | 68 | #define DEBUG_TYPE "licm" |
| 69 | |
Chris Lattner | 79a42ac | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 70 | STATISTIC(NumSunk , "Number of instructions sunk out of loop"); |
| 71 | STATISTIC(NumHoisted , "Number of instructions hoisted out of loop"); |
| 72 | STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk"); |
| 73 | STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk"); |
| 74 | STATISTIC(NumPromoted , "Number of memory locations promoted to registers"); |
| 75 | |
Dan Gohman | d78c400 | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 76 | static cl::opt<bool> |
| 77 | DisablePromotion("disable-licm-promotion", cl::Hidden, |
| 78 | cl::desc("Disable memory promotion in LICM pass")); |
Chris Lattner | 45d67d6 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 79 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 80 | static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI); |
David Majnemer | 42a0730 | 2016-01-04 03:37:39 +0000 | [diff] [blame] | 81 | static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop, |
| 82 | const LICMSafetyInfo *SafetyInfo); |
Sanjoy Das | 7a2e2be | 2016-01-28 15:51:58 +0000 | [diff] [blame] | 83 | static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, |
| 84 | const LICMSafetyInfo *SafetyInfo); |
Pete Cooper | 0cabcf2 | 2015-05-13 01:12:18 +0000 | [diff] [blame] | 85 | static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT, |
David Majnemer | 42a0730 | 2016-01-04 03:37:39 +0000 | [diff] [blame] | 86 | const Loop *CurLoop, AliasSetTracker *CurAST, |
| 87 | const LICMSafetyInfo *SafetyInfo); |
Pete Cooper | 0cabcf2 | 2015-05-13 01:12:18 +0000 | [diff] [blame] | 88 | static bool isGuaranteedToExecute(const Instruction &Inst, |
| 89 | const DominatorTree *DT, |
| 90 | const Loop *CurLoop, |
| 91 | const LICMSafetyInfo *SafetyInfo); |
| 92 | static bool isSafeToExecuteUnconditionally(const Instruction &Inst, |
| 93 | const DominatorTree *DT, |
Sanjoy Das | f8a0db5 | 2015-05-18 18:07:00 +0000 | [diff] [blame] | 94 | const TargetLibraryInfo *TLI, |
Pete Cooper | 0cabcf2 | 2015-05-13 01:12:18 +0000 | [diff] [blame] | 95 | const Loop *CurLoop, |
Philip Reames | b47b9c2 | 2015-05-22 02:14:05 +0000 | [diff] [blame] | 96 | const LICMSafetyInfo *SafetyInfo, |
| 97 | const Instruction *CtxI = nullptr); |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 98 | static bool pointerInvalidatedByLoop(Value *V, uint64_t Size, |
| 99 | const AAMDNodes &AAInfo, |
| 100 | AliasSetTracker *CurAST); |
David Majnemer | 42a0730 | 2016-01-04 03:37:39 +0000 | [diff] [blame] | 101 | static Instruction * |
| 102 | CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN, |
| 103 | const LoopInfo *LI, |
| 104 | const LICMSafetyInfo *SafetyInfo); |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 105 | static bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, |
Sanjoy Das | f8a0db5 | 2015-05-18 18:07:00 +0000 | [diff] [blame] | 106 | DominatorTree *DT, TargetLibraryInfo *TLI, |
| 107 | Loop *CurLoop, AliasSetTracker *CurAST, |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 108 | LICMSafetyInfo *SafetyInfo); |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 109 | |
Dan Gohman | d78c400 | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 110 | namespace { |
Chris Lattner | 2dd09db | 2009-09-02 06:11:42 +0000 | [diff] [blame] | 111 | struct LICM : public LoopPass { |
Nick Lewycky | e7da2d6 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 112 | static char ID; // Pass identification, replacement for typeid |
Owen Anderson | 6c18d1a | 2010-10-19 17:21:58 +0000 | [diff] [blame] | 113 | LICM() : LoopPass(ID) { |
| 114 | initializeLICMPass(*PassRegistry::getPassRegistry()); |
| 115 | } |
Devang Patel | 09f162c | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 116 | |
Craig Topper | 3e4c697 | 2014-03-05 09:10:37 +0000 | [diff] [blame] | 117 | bool runOnLoop(Loop *L, LPPassManager &LPM) override; |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 118 | |
Chris Lattner | f64f2d3 | 2002-09-26 16:52:07 +0000 | [diff] [blame] | 119 | /// This transformation requires natural loop information & requires that |
| 120 | /// loop preheaders be inserted into the CFG... |
| 121 | /// |
Craig Topper | 3e4c697 | 2014-03-05 09:10:37 +0000 | [diff] [blame] | 122 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
Chris Lattner | 820d971 | 2002-10-21 20:00:28 +0000 | [diff] [blame] | 123 | AU.setPreservesCFG(); |
Chandler Carruth | b98f63d | 2015-01-15 10:41:28 +0000 | [diff] [blame] | 124 | AU.addRequired<TargetLibraryInfoWrapperPass>(); |
Chandler Carruth | 31088a9 | 2016-02-19 10:45:18 +0000 | [diff] [blame] | 125 | getLoopAnalysisUsage(AU); |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 126 | } |
| 127 | |
Matt Beaumont-Gay | abfc446 | 2012-12-04 05:41:27 +0000 | [diff] [blame] | 128 | using llvm::Pass::doFinalization; |
| 129 | |
Craig Topper | 3e4c697 | 2014-03-05 09:10:37 +0000 | [diff] [blame] | 130 | bool doFinalization() override { |
Chris Lattner | cc9cbc6 | 2010-08-29 17:46:00 +0000 | [diff] [blame] | 131 | assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets"); |
Devang Patel | 69730c9 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 132 | return false; |
| 133 | } |
| 134 | |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 135 | private: |
Chris Lattner | 45d67d6 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 136 | AliasAnalysis *AA; // Current AliasAnalysis information |
Chris Lattner | c051768 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 137 | LoopInfo *LI; // Current LoopInfo |
Chris Lattner | abe61ef | 2010-08-29 06:49:44 +0000 | [diff] [blame] | 138 | DominatorTree *DT; // Dominator Tree for the current Loop. |
Chris Lattner | c051768 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 139 | |
Chad Rosier | 43a3306 | 2011-12-02 01:26:24 +0000 | [diff] [blame] | 140 | TargetLibraryInfo *TLI; // TargetLibraryInfo for constant folding. |
| 141 | |
Chris Lattner | cc9cbc6 | 2010-08-29 17:46:00 +0000 | [diff] [blame] | 142 | // State that is updated as we process loops. |
Chris Lattner | 45d67d6 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 143 | bool Changed; // Set to true when we change anything. |
| 144 | BasicBlock *Preheader; // The preheader block of the current loop... |
| 145 | Loop *CurLoop; // The current loop we are working on... |
Chris Lattner | 0592bb7 | 2003-03-03 23:32:45 +0000 | [diff] [blame] | 146 | AliasSetTracker *CurAST; // AliasSet information for the current loop... |
Chris Lattner | cc9cbc6 | 2010-08-29 17:46:00 +0000 | [diff] [blame] | 147 | DenseMap<Loop*, AliasSetTracker*> LoopToAliasSetMap; |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 148 | |
Devang Patel | b98a097 | 2007-07-31 08:01:41 +0000 | [diff] [blame] | 149 | /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. |
Craig Topper | 3e4c697 | 2014-03-05 09:10:37 +0000 | [diff] [blame] | 150 | void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, |
| 151 | Loop *L) override; |
Devang Patel | b98a097 | 2007-07-31 08:01:41 +0000 | [diff] [blame] | 152 | |
| 153 | /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias |
| 154 | /// set. |
Craig Topper | 3e4c697 | 2014-03-05 09:10:37 +0000 | [diff] [blame] | 155 | void deleteAnalysisValue(Value *V, Loop *L) override; |
Devang Patel | b98a097 | 2007-07-31 08:01:41 +0000 | [diff] [blame] | 156 | |
David Peixotto | 0d4d5e6 | 2014-09-24 16:48:31 +0000 | [diff] [blame] | 157 | /// Simple Analysis hook. Delete loop L from alias set map. |
| 158 | void deleteAnalysisLoop(Loop *L) override; |
Roman Gareev | 036c088 | 2016-02-15 14:48:50 +0000 | [diff] [blame] | 159 | |
Chandler Carruth | ad8cb38 | 2016-02-27 04:34:07 +0000 | [diff] [blame] | 160 | AliasSetTracker *collectAliasInfoForLoop(Loop *L); |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 161 | }; |
Alexander Kornienko | f00654e | 2015-06-23 09:49:53 +0000 | [diff] [blame] | 162 | } |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 163 | |
Dan Gohman | d78c400 | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 164 | char LICM::ID = 0; |
Owen Anderson | 8ac477f | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 165 | INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false) |
Chandler Carruth | 31088a9 | 2016-02-19 10:45:18 +0000 | [diff] [blame] | 166 | INITIALIZE_PASS_DEPENDENCY(LoopPass) |
Chandler Carruth | b98f63d | 2015-01-15 10:41:28 +0000 | [diff] [blame] | 167 | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) |
Owen Anderson | 8ac477f | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 168 | INITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false) |
Dan Gohman | d78c400 | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 169 | |
Daniel Dunbar | 7f39e2d | 2008-10-22 23:32:42 +0000 | [diff] [blame] | 170 | Pass *llvm::createLICMPass() { return new LICM(); } |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 171 | |
Devang Patel | d8b1ceb | 2007-07-31 16:52:25 +0000 | [diff] [blame] | 172 | /// Hoist expressions out of the specified loop. Note, alias info for inner |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 173 | /// loop is not preserved so it is not a good idea to run LICM multiple |
Devang Patel | d8b1ceb | 2007-07-31 16:52:25 +0000 | [diff] [blame] | 174 | /// times on one loop. |
Chris Lattner | f64f2d3 | 2002-09-26 16:52:07 +0000 | [diff] [blame] | 175 | /// |
Devang Patel | 69730c9 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 176 | bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { |
Paul Robinson | af4e64d | 2014-02-06 00:07:05 +0000 | [diff] [blame] | 177 | if (skipOptnoneFunction(L)) |
| 178 | return false; |
| 179 | |
Chris Lattner | 45d67d6 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 180 | Changed = false; |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 181 | |
Chris Lattner | 45d67d6 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 182 | // Get our Loop and Alias Analysis information... |
Chandler Carruth | 4f8f307 | 2015-01-17 14:16:18 +0000 | [diff] [blame] | 183 | LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 184 | AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); |
Chandler Carruth | 7352302 | 2014-01-13 13:07:17 +0000 | [diff] [blame] | 185 | DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
Chris Lattner | a51fa88 | 2002-08-22 21:39:55 +0000 | [diff] [blame] | 186 | |
Chandler Carruth | b98f63d | 2015-01-15 10:41:28 +0000 | [diff] [blame] | 187 | TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); |
Chad Rosier | 43a3306 | 2011-12-02 01:26:24 +0000 | [diff] [blame] | 188 | |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 189 | assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form."); |
| 190 | |
Chandler Carruth | ad8cb38 | 2016-02-27 04:34:07 +0000 | [diff] [blame] | 191 | CurAST = collectAliasInfoForLoop(L); |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 192 | |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 193 | CurLoop = L; |
| 194 | |
Chris Lattner | d57f3f5 | 2002-09-26 19:40:25 +0000 | [diff] [blame] | 195 | // Get the preheader block to move instructions into... |
| 196 | Preheader = L->getLoopPreheader(); |
Chris Lattner | d57f3f5 | 2002-09-26 19:40:25 +0000 | [diff] [blame] | 197 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 198 | // Compute loop safety information. |
| 199 | LICMSafetyInfo SafetyInfo; |
| 200 | computeLICMSafetyInfo(&SafetyInfo, CurLoop); |
Nadav Rotem | 03dcd85 | 2012-09-04 10:25:04 +0000 | [diff] [blame] | 201 | |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 202 | // We want to visit all of the instructions in this loop... that are not parts |
| 203 | // of our subloops (they have already had their invariants hoisted out of |
| 204 | // their loop, into this loop, so there is no need to process the BODIES of |
| 205 | // the subloops). |
| 206 | // |
Chris Lattner | 6443769 | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 207 | // Traverse the body of the loop in depth first order on the dominator tree so |
| 208 | // that we are guaranteed to see definitions before we see uses. This allows |
Nick Lewycky | a0d49da | 2007-08-18 15:08:56 +0000 | [diff] [blame] | 209 | // us to sink instructions in one pass, without iteration. After sinking |
Chris Lattner | 547192d6 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 210 | // instructions, we perform another pass to hoist them out of the loop. |
Chris Lattner | 6443769 | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 211 | // |
Dan Gohman | a83ac2d | 2009-11-05 21:11:53 +0000 | [diff] [blame] | 212 | if (L->hasDedicatedExits()) |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 213 | Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, CurLoop, |
| 214 | CurAST, &SafetyInfo); |
Dan Gohman | a83ac2d | 2009-11-05 21:11:53 +0000 | [diff] [blame] | 215 | if (Preheader) |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 216 | Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 217 | CurLoop, CurAST, &SafetyInfo); |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 218 | |
Chris Lattner | 45d67d6 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 219 | // Now that all loop invariants have been removed from the loop, promote any |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 220 | // memory references to scalars that we can. |
Chandler Carruth | cc497b6 | 2014-01-24 02:24:47 +0000 | [diff] [blame] | 221 | if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) { |
Dan Gohman | b948736 | 2012-08-08 00:00:26 +0000 | [diff] [blame] | 222 | SmallVector<BasicBlock *, 8> ExitBlocks; |
| 223 | SmallVector<Instruction *, 8> InsertPts; |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 224 | PredIteratorCache PIC; |
Dan Gohman | b948736 | 2012-08-08 00:00:26 +0000 | [diff] [blame] | 225 | |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 226 | // Loop over all of the alias sets in the tracker object. |
Sanjay Patel | 9f088ab | 2016-01-08 22:59:42 +0000 | [diff] [blame] | 227 | for (AliasSet &AS : *CurAST) |
| 228 | Changed |= promoteLoopAccessesToScalars(AS, ExitBlocks, InsertPts, |
Philip Reames | b54c8e6 | 2016-03-09 22:59:30 +0000 | [diff] [blame] | 229 | PIC, LI, DT, TLI, CurLoop, |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 230 | CurAST, &SafetyInfo); |
Chandler Carruth | 1665152 | 2014-02-01 13:35:14 +0000 | [diff] [blame] | 231 | |
| 232 | // Once we have promoted values across the loop body we have to recursively |
| 233 | // reform LCSSA as any nested loop may now have values defined within the |
| 234 | // loop used in the outer loop. |
| 235 | // FIXME: This is really heavy handed. It would be a bit better to use an |
| 236 | // SSAUpdater strategy during promotion that was LCSSA aware and reformed |
| 237 | // it as it went. |
Chandler Carruth | 2f1fd16 | 2015-08-17 02:08:17 +0000 | [diff] [blame] | 238 | if (Changed) { |
| 239 | auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>(); |
| 240 | formLCSSARecursively(*L, *DT, LI, SEWP ? &SEWP->getSE() : nullptr); |
| 241 | } |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 242 | } |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 243 | |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 244 | // Check that neither this loop nor its parent have had LCSSA broken. LICM is |
| 245 | // specifically moving instructions across the loop boundary and so it is |
| 246 | // especially in need of sanity checking here. |
| 247 | assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!"); |
| 248 | assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) && |
| 249 | "Parent loop not left in LCSSA form after LICM!"); |
Chandler Carruth | 8765cf7 | 2014-01-25 04:07:24 +0000 | [diff] [blame] | 250 | |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 251 | // Clear out loops state information for the next iteration |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 252 | CurLoop = nullptr; |
| 253 | Preheader = nullptr; |
Devang Patel | 69730c9 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 254 | |
Chris Lattner | cc9cbc6 | 2010-08-29 17:46:00 +0000 | [diff] [blame] | 255 | // If this loop is nested inside of another one, save the alias information |
| 256 | // for when we process the outer loop. |
| 257 | if (L->getParentLoop()) |
| 258 | LoopToAliasSetMap[L] = CurAST; |
| 259 | else |
| 260 | delete CurAST; |
Devang Patel | 69730c9 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 261 | return Changed; |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 262 | } |
| 263 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 264 | /// Walk the specified region of the CFG (defined by all blocks dominated by |
| 265 | /// the specified block, and that are in the current loop) in reverse depth |
| 266 | /// first order w.r.t the DominatorTree. This allows us to visit uses before |
| 267 | /// definitions, allowing us to sink a loop body in one pass without iteration. |
Chris Lattner | 547192d6 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 268 | /// |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 269 | bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI, |
| 270 | DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop, |
| 271 | AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) { |
Chris Lattner | 547192d6 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 272 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 273 | // Verify inputs. |
| 274 | assert(N != nullptr && AA != nullptr && LI != nullptr && |
| 275 | DT != nullptr && CurLoop != nullptr && CurAST != nullptr && |
| 276 | SafetyInfo != nullptr && "Unexpected input to sinkRegion"); |
| 277 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 278 | BasicBlock *BB = N->getBlock(); |
Chris Lattner | 547192d6 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 279 | // If this subregion is not in the top level loop at all, exit. |
Sanjay Patel | 9913322 | 2016-01-13 23:01:57 +0000 | [diff] [blame] | 280 | if (!CurLoop->contains(BB)) return false; |
Chris Lattner | 547192d6 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 281 | |
Chris Lattner | 263f804 | 2010-08-29 18:22:25 +0000 | [diff] [blame] | 282 | // We are processing blocks in reverse dfo, so process children first. |
Sanjay Patel | 9913322 | 2016-01-13 23:01:57 +0000 | [diff] [blame] | 283 | bool Changed = false; |
Devang Patel | bdd1aae | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 284 | const std::vector<DomTreeNode*> &Children = N->getChildren(); |
Sanjay Patel | 9f088ab | 2016-01-08 22:59:42 +0000 | [diff] [blame] | 285 | for (DomTreeNode *Child : Children) |
| 286 | Changed |= sinkRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo); |
| 287 | |
Chris Lattner | 547192d6 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 288 | // Only need to process the contents of this block if it is not part of a |
| 289 | // subloop (which would already have been processed). |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 290 | if (inSubLoop(BB,CurLoop,LI)) return Changed; |
Chris Lattner | 547192d6 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 291 | |
Chris Lattner | 9184601 | 2003-12-19 08:18:16 +0000 | [diff] [blame] | 292 | for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) { |
| 293 | Instruction &I = *--II; |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 294 | |
Chris Lattner | 263f804 | 2010-08-29 18:22:25 +0000 | [diff] [blame] | 295 | // If the instruction is dead, we would try to sink it because it isn't used |
| 296 | // in the loop, instead, just delete it. |
Benjamin Kramer | 8bcc971 | 2012-08-29 15:32:21 +0000 | [diff] [blame] | 297 | if (isInstructionTriviallyDead(&I, TLI)) { |
Chris Lattner | f58382e | 2010-08-29 18:42:23 +0000 | [diff] [blame] | 298 | DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n'); |
Chris Lattner | 263f804 | 2010-08-29 18:22:25 +0000 | [diff] [blame] | 299 | ++II; |
| 300 | CurAST->deleteValue(&I); |
| 301 | I.eraseFromParent(); |
| 302 | Changed = true; |
| 303 | continue; |
| 304 | } |
Misha Brukman | b1c9317 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 305 | |
Chris Lattner | 547192d6 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 306 | // Check to see if we can sink this instruction to the exit blocks |
| 307 | // of the loop. We can do this if the all users of the instruction are |
| 308 | // outside of the loop. In this case, it doesn't even matter if the |
| 309 | // operands of the instruction are loop invariant. |
| 310 | // |
David Majnemer | 42a0730 | 2016-01-04 03:37:39 +0000 | [diff] [blame] | 311 | if (isNotUsedInLoop(I, CurLoop, SafetyInfo) && |
Sanjoy Das | f8a0db5 | 2015-05-18 18:07:00 +0000 | [diff] [blame] | 312 | canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo)) { |
Chris Lattner | 9184601 | 2003-12-19 08:18:16 +0000 | [diff] [blame] | 313 | ++II; |
David Majnemer | 42a0730 | 2016-01-04 03:37:39 +0000 | [diff] [blame] | 314 | Changed |= sink(I, LI, DT, CurLoop, CurAST, SafetyInfo); |
Chris Lattner | 9184601 | 2003-12-19 08:18:16 +0000 | [diff] [blame] | 315 | } |
Chris Lattner | 547192d6 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 316 | } |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 317 | return Changed; |
Chris Lattner | 547192d6 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 318 | } |
| 319 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 320 | /// Walk the specified region of the CFG (defined by all blocks dominated by |
| 321 | /// the specified block, and that are in the current loop) in depth first |
| 322 | /// order w.r.t the DominatorTree. This allows us to visit definitions before |
| 323 | /// uses, allowing us to hoist a loop body in one pass without iteration. |
Chris Lattner | 6443769 | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 324 | /// |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 325 | bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI, |
| 326 | DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop, |
| 327 | AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) { |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 328 | // Verify inputs. |
| 329 | assert(N != nullptr && AA != nullptr && LI != nullptr && |
| 330 | DT != nullptr && CurLoop != nullptr && CurAST != nullptr && |
| 331 | SafetyInfo != nullptr && "Unexpected input to hoistRegion"); |
Sanjay Patel | 9913322 | 2016-01-13 23:01:57 +0000 | [diff] [blame] | 332 | |
Owen Anderson | c24701e | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 333 | BasicBlock *BB = N->getBlock(); |
Sanjay Patel | 9913322 | 2016-01-13 23:01:57 +0000 | [diff] [blame] | 334 | |
Chris Lattner | 05e8630 | 2002-09-29 22:26:07 +0000 | [diff] [blame] | 335 | // If this subregion is not in the top level loop at all, exit. |
Sanjay Patel | 9913322 | 2016-01-13 23:01:57 +0000 | [diff] [blame] | 336 | if (!CurLoop->contains(BB)) return false; |
| 337 | |
Chris Lattner | aaaea51 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 338 | // Only need to process the contents of this block if it is not part of a |
| 339 | // subloop (which would already have been processed). |
Sanjay Patel | 9913322 | 2016-01-13 23:01:57 +0000 | [diff] [blame] | 340 | bool Changed = false; |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 341 | if (!inSubLoop(BB, CurLoop, LI)) |
Chris Lattner | aaaea51 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 342 | for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) { |
| 343 | Instruction &I = *II++; |
Chris Lattner | 030f020 | 2010-08-31 23:00:16 +0000 | [diff] [blame] | 344 | // Try constant folding this instruction. If all the operands are |
| 345 | // constants, it is technically hoistable, but it would be better to just |
| 346 | // fold it. |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 347 | if (Constant *C = ConstantFoldInstruction( |
| 348 | &I, I.getModule()->getDataLayout(), TLI)) { |
Chris Lattner | 030f020 | 2010-08-31 23:00:16 +0000 | [diff] [blame] | 349 | DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n'); |
| 350 | CurAST->copyValue(&I, C); |
| 351 | CurAST->deleteValue(&I); |
| 352 | I.replaceAllUsesWith(C); |
| 353 | I.eraseFromParent(); |
| 354 | continue; |
| 355 | } |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 356 | |
Chris Lattner | 547192d6 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 357 | // Try hoisting the instruction out to the preheader. We can only do this |
| 358 | // if all of the operands of the instruction are loop invariant and if it |
| 359 | // is safe to hoist the instruction. |
| 360 | // |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 361 | if (CurLoop->hasLoopInvariantOperands(&I) && |
Sanjoy Das | f8a0db5 | 2015-05-18 18:07:00 +0000 | [diff] [blame] | 362 | canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) && |
Philip Reames | b47b9c2 | 2015-05-22 02:14:05 +0000 | [diff] [blame] | 363 | isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo, |
| 364 | CurLoop->getLoopPreheader()->getTerminator())) |
Sanjoy Das | 7a2e2be | 2016-01-28 15:51:58 +0000 | [diff] [blame] | 365 | Changed |= hoist(I, DT, CurLoop, SafetyInfo); |
Chris Lattner | 030f020 | 2010-08-31 23:00:16 +0000 | [diff] [blame] | 366 | } |
Chris Lattner | 6443769 | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 367 | |
Devang Patel | bdd1aae | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 368 | const std::vector<DomTreeNode*> &Children = N->getChildren(); |
Sanjay Patel | 9f088ab | 2016-01-08 22:59:42 +0000 | [diff] [blame] | 369 | for (DomTreeNode *Child : Children) |
| 370 | Changed |= hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo); |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 371 | return Changed; |
| 372 | } |
| 373 | |
| 374 | /// Computes loop safety information, checks loop body & header |
Benjamin Kramer | df005cb | 2015-08-08 18:27:36 +0000 | [diff] [blame] | 375 | /// for the possibility of may throw exception. |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 376 | /// |
| 377 | void llvm::computeLICMSafetyInfo(LICMSafetyInfo * SafetyInfo, Loop * CurLoop) { |
| 378 | assert(CurLoop != nullptr && "CurLoop cant be null"); |
| 379 | BasicBlock *Header = CurLoop->getHeader(); |
| 380 | // Setting default safety values. |
| 381 | SafetyInfo->MayThrow = false; |
| 382 | SafetyInfo->HeaderMayThrow = false; |
Benjamin Kramer | df005cb | 2015-08-08 18:27:36 +0000 | [diff] [blame] | 383 | // Iterate over header and compute safety info. |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 384 | for (BasicBlock::iterator I = Header->begin(), E = Header->end(); |
| 385 | (I != E) && !SafetyInfo->HeaderMayThrow; ++I) |
| 386 | SafetyInfo->HeaderMayThrow |= I->mayThrow(); |
| 387 | |
| 388 | SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow; |
| 389 | // Iterate over loop instructions and compute safety info. |
| 390 | for (Loop::block_iterator BB = CurLoop->block_begin(), |
| 391 | BBE = CurLoop->block_end(); (BB != BBE) && !SafetyInfo->MayThrow ; ++BB) |
| 392 | for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); |
| 393 | (I != E) && !SafetyInfo->MayThrow; ++I) |
| 394 | SafetyInfo->MayThrow |= I->mayThrow(); |
David Majnemer | 42a0730 | 2016-01-04 03:37:39 +0000 | [diff] [blame] | 395 | |
| 396 | // Compute funclet colors if we might sink/hoist in a function with a funclet |
| 397 | // personality routine. |
| 398 | Function *Fn = CurLoop->getHeader()->getParent(); |
| 399 | if (Fn->hasPersonalityFn()) |
| 400 | if (Constant *PersonalityFn = Fn->getPersonalityFn()) |
| 401 | if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn))) |
| 402 | SafetyInfo->BlockColors = colorEHFunclets(*Fn); |
Chris Lattner | 6443769 | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 403 | } |
| 404 | |
Chris Lattner | aaaea51 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 405 | /// canSinkOrHoistInst - Return true if the hoister and sinker can handle this |
| 406 | /// instruction. |
| 407 | /// |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 408 | bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, DominatorTree *DT, |
Sanjoy Das | f8a0db5 | 2015-05-18 18:07:00 +0000 | [diff] [blame] | 409 | TargetLibraryInfo *TLI, Loop *CurLoop, |
| 410 | AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) { |
Chris Lattner | 65c1193 | 2003-12-09 19:32:44 +0000 | [diff] [blame] | 411 | // Loads have extra constraints we have to verify before we can hoist them. |
| 412 | if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { |
Eli Friedman | 91386c7 | 2011-08-15 20:52:09 +0000 | [diff] [blame] | 413 | if (!LI->isUnordered()) |
| 414 | return false; // Don't hoist volatile/atomic loads! |
Chris Lattner | 65c1193 | 2003-12-09 19:32:44 +0000 | [diff] [blame] | 415 | |
Chris Lattner | 8a8fb90 | 2008-07-23 05:06:28 +0000 | [diff] [blame] | 416 | // Loads from constant memory are always safe to move, even if they end up |
| 417 | // in the same alias set as something that ends up being modified. |
Dan Gohman | cbc6ebb | 2009-11-19 19:00:10 +0000 | [diff] [blame] | 418 | if (AA->pointsToConstantMemory(LI->getOperand(0))) |
Chris Lattner | 8a8fb90 | 2008-07-23 05:06:28 +0000 | [diff] [blame] | 419 | return true; |
Philip Reames | 5a3f5f7 | 2014-10-21 00:13:20 +0000 | [diff] [blame] | 420 | if (LI->getMetadata(LLVMContext::MD_invariant_load)) |
Pete Cooper | 9ee2209 | 2011-11-08 19:30:00 +0000 | [diff] [blame] | 421 | return true; |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 422 | |
Chris Lattner | 65c1193 | 2003-12-09 19:32:44 +0000 | [diff] [blame] | 423 | // Don't hoist loads which have may-aliased stores in loop. |
Dan Gohman | f372cf8 | 2010-10-19 22:54:46 +0000 | [diff] [blame] | 424 | uint64_t Size = 0; |
Chris Lattner | b137409 | 2004-11-26 21:20:09 +0000 | [diff] [blame] | 425 | if (LI->getType()->isSized()) |
Chandler Carruth | 50fee93 | 2015-08-06 02:05:46 +0000 | [diff] [blame] | 426 | Size = I.getModule()->getDataLayout().getTypeStoreSize(LI->getType()); |
Hal Finkel | cc39b67 | 2014-07-24 12:16:19 +0000 | [diff] [blame] | 427 | |
| 428 | AAMDNodes AAInfo; |
| 429 | LI->getAAMetadata(AAInfo); |
| 430 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 431 | return !pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST); |
Chris Lattner | 20cda26 | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 432 | } else if (CallInst *CI = dyn_cast<CallInst>(&I)) { |
Eli Friedman | 942e1c1 | 2011-05-27 18:37:52 +0000 | [diff] [blame] | 433 | // Don't sink or hoist dbg info; it's legal, but not useful. |
| 434 | if (isa<DbgInfoIntrinsic>(I)) |
| 435 | return false; |
| 436 | |
David Majnemer | 42a0730 | 2016-01-04 03:37:39 +0000 | [diff] [blame] | 437 | // Don't sink calls which can throw. |
| 438 | if (CI->mayThrow()) |
| 439 | return false; |
| 440 | |
Eli Friedman | 942e1c1 | 2011-05-27 18:37:52 +0000 | [diff] [blame] | 441 | // Handle simple cases by querying alias analysis. |
Chandler Carruth | 194f59c | 2015-07-22 23:15:57 +0000 | [diff] [blame] | 442 | FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI); |
| 443 | if (Behavior == FMRB_DoesNotAccessMemory) |
Duncan Sands | 68b6f50 | 2007-12-01 07:51:45 +0000 | [diff] [blame] | 444 | return true; |
Dan Gohman | 0f17507 | 2010-11-09 19:58:21 +0000 | [diff] [blame] | 445 | if (AliasAnalysis::onlyReadsMemory(Behavior)) { |
Philip Reames | 5f99423 | 2015-09-21 22:27:59 +0000 | [diff] [blame] | 446 | // A readonly argmemonly function only reads from memory pointed to by |
| 447 | // it's arguments with arbitrary offsets. If we can prove there are no |
| 448 | // writes to this memory in the loop, we can hoist or sink. |
| 449 | if (AliasAnalysis::onlyAccessesArgPointees(Behavior)) { |
| 450 | for (Value *Op : CI->arg_operands()) |
| 451 | if (Op->getType()->isPointerTy() && |
| 452 | pointerInvalidatedByLoop(Op, MemoryLocation::UnknownSize, |
| 453 | AAMDNodes(), CurAST)) |
| 454 | return false; |
| 455 | return true; |
| 456 | } |
Duncan Sands | 68b6f50 | 2007-12-01 07:51:45 +0000 | [diff] [blame] | 457 | // If this call only reads from memory and there are no writes to memory |
| 458 | // in the loop, we can hoist or sink the call as appropriate. |
| 459 | bool FoundMod = false; |
Sanjay Patel | 9f088ab | 2016-01-08 22:59:42 +0000 | [diff] [blame] | 460 | for (AliasSet &AS : *CurAST) { |
Duncan Sands | 68b6f50 | 2007-12-01 07:51:45 +0000 | [diff] [blame] | 461 | if (!AS.isForwardingAliasSet() && AS.isMod()) { |
| 462 | FoundMod = true; |
| 463 | break; |
Chris Lattner | 20cda26 | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 464 | } |
Chris Lattner | 20cda26 | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 465 | } |
Duncan Sands | 68b6f50 | 2007-12-01 07:51:45 +0000 | [diff] [blame] | 466 | if (!FoundMod) return true; |
Chris Lattner | 20cda26 | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 467 | } |
| 468 | |
Nadav Rotem | 03dcd85 | 2012-09-04 10:25:04 +0000 | [diff] [blame] | 469 | // FIXME: This should use mod/ref information to see if we can hoist or |
| 470 | // sink the call. |
Misha Brukman | b1c9317 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 471 | |
Chris Lattner | 20cda26 | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 472 | return false; |
Chris Lattner | 65c1193 | 2003-12-09 19:32:44 +0000 | [diff] [blame] | 473 | } |
| 474 | |
Nadav Rotem | 03dcd85 | 2012-09-04 10:25:04 +0000 | [diff] [blame] | 475 | // Only these instructions are hoistable/sinkable. |
Benjamin Kramer | 130fcde | 2013-01-09 18:12:03 +0000 | [diff] [blame] | 476 | if (!isa<BinaryOperator>(I) && !isa<CastInst>(I) && !isa<SelectInst>(I) && |
| 477 | !isa<GetElementPtrInst>(I) && !isa<CmpInst>(I) && |
| 478 | !isa<InsertElementInst>(I) && !isa<ExtractElementInst>(I) && |
| 479 | !isa<ShuffleVectorInst>(I) && !isa<ExtractValueInst>(I) && |
| 480 | !isa<InsertValueInst>(I)) |
| 481 | return false; |
Nadav Rotem | 03dcd85 | 2012-09-04 10:25:04 +0000 | [diff] [blame] | 482 | |
Philip Reames | b47b9c2 | 2015-05-22 02:14:05 +0000 | [diff] [blame] | 483 | // TODO: Plumb the context instruction through to make hoisting and sinking |
| 484 | // more powerful. Hoisting of loads already works due to the special casing |
| 485 | // above. |
| 486 | return isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo, |
| 487 | nullptr); |
Chris Lattner | aaaea51 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 488 | } |
| 489 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 490 | /// Returns true if a PHINode is a trivially replaceable with an |
Chandler Carruth | 8765cf7 | 2014-01-25 04:07:24 +0000 | [diff] [blame] | 491 | /// Instruction. |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 492 | /// This is true when all incoming values are that instruction. |
| 493 | /// This pattern occurs most often with LCSSA PHI nodes. |
Chandler Carruth | 8765cf7 | 2014-01-25 04:07:24 +0000 | [diff] [blame] | 494 | /// |
Pete Cooper | 47e80cd | 2015-05-12 20:05:20 +0000 | [diff] [blame] | 495 | static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I) { |
Pete Cooper | 833f34d | 2015-05-12 20:05:31 +0000 | [diff] [blame] | 496 | for (const Value *IncValue : PN.incoming_values()) |
| 497 | if (IncValue != &I) |
Chandler Carruth | 8765cf7 | 2014-01-25 04:07:24 +0000 | [diff] [blame] | 498 | return false; |
| 499 | |
| 500 | return true; |
| 501 | } |
| 502 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 503 | /// Return true if the only users of this instruction are outside of |
| 504 | /// the loop. If this is true, we can sink the instruction to the exit |
| 505 | /// blocks of the loop. |
Chris Lattner | aaaea51 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 506 | /// |
David Majnemer | 42a0730 | 2016-01-04 03:37:39 +0000 | [diff] [blame] | 507 | static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop, |
| 508 | const LICMSafetyInfo *SafetyInfo) { |
| 509 | const auto &BlockColors = SafetyInfo->BlockColors; |
Pete Cooper | 0cabcf2 | 2015-05-13 01:12:18 +0000 | [diff] [blame] | 510 | for (const User *U : I.users()) { |
| 511 | const Instruction *UI = cast<Instruction>(U); |
| 512 | if (const PHINode *PN = dyn_cast<PHINode>(UI)) { |
David Majnemer | 42a0730 | 2016-01-04 03:37:39 +0000 | [diff] [blame] | 513 | const BasicBlock *BB = PN->getParent(); |
| 514 | // We cannot sink uses in catchswitches. |
| 515 | if (isa<CatchSwitchInst>(BB->getTerminator())) |
| 516 | return false; |
| 517 | |
| 518 | // We need to sink a callsite to a unique funclet. Avoid sinking if the |
| 519 | // phi use is too muddled. |
| 520 | if (isa<CallInst>(I)) |
| 521 | if (!BlockColors.empty() && |
| 522 | BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1) |
| 523 | return false; |
| 524 | |
Chandler Carruth | 8765cf7 | 2014-01-25 04:07:24 +0000 | [diff] [blame] | 525 | // A PHI node where all of the incoming values are this instruction are |
| 526 | // special -- they can just be RAUW'ed with the instruction and thus |
| 527 | // don't require a use in the predecessor. This is a particular important |
| 528 | // special case because it is the pattern found in LCSSA form. |
| 529 | if (isTriviallyReplacablePHI(*PN, I)) { |
| 530 | if (CurLoop->contains(PN)) |
| 531 | return false; |
| 532 | else |
| 533 | continue; |
| 534 | } |
| 535 | |
| 536 | // Otherwise, PHI node uses occur in predecessor blocks if the incoming |
| 537 | // values. Check for such a use being inside the loop. |
Chris Lattner | 34399dd | 2003-12-11 22:23:32 +0000 | [diff] [blame] | 538 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) |
| 539 | if (PN->getIncomingValue(i) == &I) |
| 540 | if (CurLoop->contains(PN->getIncomingBlock(i))) |
| 541 | return false; |
Chandler Carruth | 8765cf7 | 2014-01-25 04:07:24 +0000 | [diff] [blame] | 542 | |
| 543 | continue; |
Chris Lattner | 34399dd | 2003-12-11 22:23:32 +0000 | [diff] [blame] | 544 | } |
Chandler Carruth | 8765cf7 | 2014-01-25 04:07:24 +0000 | [diff] [blame] | 545 | |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 546 | if (CurLoop->contains(UI)) |
Chandler Carruth | 8765cf7 | 2014-01-25 04:07:24 +0000 | [diff] [blame] | 547 | return false; |
Chris Lattner | 34399dd | 2003-12-11 22:23:32 +0000 | [diff] [blame] | 548 | } |
Chris Lattner | aaaea51 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 549 | return true; |
| 550 | } |
| 551 | |
David Majnemer | 42a0730 | 2016-01-04 03:37:39 +0000 | [diff] [blame] | 552 | static Instruction * |
| 553 | CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN, |
| 554 | const LoopInfo *LI, |
| 555 | const LICMSafetyInfo *SafetyInfo) { |
| 556 | Instruction *New; |
| 557 | if (auto *CI = dyn_cast<CallInst>(&I)) { |
| 558 | const auto &BlockColors = SafetyInfo->BlockColors; |
| 559 | |
| 560 | // Sinking call-sites need to be handled differently from other |
| 561 | // instructions. The cloned call-site needs a funclet bundle operand |
| 562 | // appropriate for it's location in the CFG. |
| 563 | SmallVector<OperandBundleDef, 1> OpBundles; |
| 564 | for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles(); |
| 565 | BundleIdx != BundleEnd; ++BundleIdx) { |
| 566 | OperandBundleUse Bundle = CI->getOperandBundleAt(BundleIdx); |
| 567 | if (Bundle.getTagID() == LLVMContext::OB_funclet) |
| 568 | continue; |
| 569 | |
| 570 | OpBundles.emplace_back(Bundle); |
| 571 | } |
| 572 | |
| 573 | if (!BlockColors.empty()) { |
| 574 | const ColorVector &CV = BlockColors.find(&ExitBlock)->second; |
| 575 | assert(CV.size() == 1 && "non-unique color for exit block!"); |
| 576 | BasicBlock *BBColor = CV.front(); |
| 577 | Instruction *EHPad = BBColor->getFirstNonPHI(); |
| 578 | if (EHPad->isEHPad()) |
| 579 | OpBundles.emplace_back("funclet", EHPad); |
| 580 | } |
| 581 | |
| 582 | New = CallInst::Create(CI, OpBundles); |
| 583 | } else { |
| 584 | New = I.clone(); |
| 585 | } |
| 586 | |
Evgeniy Stepanov | d99cca2 | 2014-06-25 09:17:21 +0000 | [diff] [blame] | 587 | ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New); |
| 588 | if (!I.getName().empty()) New->setName(I.getName() + ".le"); |
| 589 | |
| 590 | // Build LCSSA PHI nodes for any in-loop operands. Note that this is |
| 591 | // particularly cheap because we can rip off the PHI node that we're |
| 592 | // replacing for the number and blocks of the predecessors. |
| 593 | // OPT: If this shows up in a profile, we can instead finish sinking all |
| 594 | // invariant instructions, and then walk their operands to re-establish |
| 595 | // LCSSA. That will eliminate creating PHI nodes just to nuke them when |
| 596 | // sinking bottom-up. |
| 597 | for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE; |
| 598 | ++OI) |
| 599 | if (Instruction *OInst = dyn_cast<Instruction>(*OI)) |
| 600 | if (Loop *OLoop = LI->getLoopFor(OInst->getParent())) |
| 601 | if (!OLoop->contains(&PN)) { |
| 602 | PHINode *OpPN = |
| 603 | PHINode::Create(OInst->getType(), PN.getNumIncomingValues(), |
Duncan P. N. Exon Smith | be4d8cb | 2015-10-13 19:26:58 +0000 | [diff] [blame] | 604 | OInst->getName() + ".lcssa", &ExitBlock.front()); |
Evgeniy Stepanov | d99cca2 | 2014-06-25 09:17:21 +0000 | [diff] [blame] | 605 | for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) |
| 606 | OpPN->addIncoming(OInst, PN.getIncomingBlock(i)); |
| 607 | *OI = OpPN; |
| 608 | } |
| 609 | return New; |
| 610 | } |
| 611 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 612 | /// When an instruction is found to only be used outside of the loop, this |
| 613 | /// function moves it to the exit blocks and patches up SSA form as needed. |
Chris Lattner | 9184601 | 2003-12-19 08:18:16 +0000 | [diff] [blame] | 614 | /// This method is guaranteed to remove the original instruction from its |
| 615 | /// position, and may either delete it or move it to outside of the loop. |
Chris Lattner | aaaea51 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 616 | /// |
Pete Cooper | 0cabcf2 | 2015-05-13 01:12:18 +0000 | [diff] [blame] | 617 | static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT, |
David Majnemer | 42a0730 | 2016-01-04 03:37:39 +0000 | [diff] [blame] | 618 | const Loop *CurLoop, AliasSetTracker *CurAST, |
| 619 | const LICMSafetyInfo *SafetyInfo) { |
Nick Lewycky | 299c6df | 2010-07-30 20:27:01 +0000 | [diff] [blame] | 620 | DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n"); |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 621 | bool Changed = false; |
Chris Lattner | 55c2113 | 2003-12-10 20:43:29 +0000 | [diff] [blame] | 622 | if (isa<LoadInst>(I)) ++NumMovedLoads; |
Chris Lattner | 20cda26 | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 623 | else if (isa<CallInst>(I)) ++NumMovedCalls; |
Chris Lattner | 55c2113 | 2003-12-10 20:43:29 +0000 | [diff] [blame] | 624 | ++NumSunk; |
| 625 | Changed = true; |
| 626 | |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 627 | #ifndef NDEBUG |
| 628 | SmallVector<BasicBlock *, 32> ExitBlocks; |
| 629 | CurLoop->getUniqueExitBlocks(ExitBlocks); |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 630 | SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(), |
| 631 | ExitBlocks.end()); |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 632 | #endif |
Chandler Carruth | 8765cf7 | 2014-01-25 04:07:24 +0000 | [diff] [blame] | 633 | |
Evgeniy Stepanov | 10280da | 2014-06-25 07:54:58 +0000 | [diff] [blame] | 634 | // Clones of this instruction. Don't create more than one per exit block! |
| 635 | SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies; |
| 636 | |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 637 | // If this instruction is only used outside of the loop, then all users are |
| 638 | // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of |
| 639 | // the instruction. |
| 640 | while (!I.use_empty()) { |
David Majnemer | 6bc83e0 | 2015-07-12 03:53:05 +0000 | [diff] [blame] | 641 | Value::user_iterator UI = I.user_begin(); |
| 642 | auto *User = cast<Instruction>(*UI); |
David Majnemer | 4942810 | 2014-09-02 16:22:00 +0000 | [diff] [blame] | 643 | if (!DT->isReachableFromEntry(User->getParent())) { |
| 644 | User->replaceUsesOfWith(&I, UndefValue::get(I.getType())); |
| 645 | continue; |
| 646 | } |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 647 | // The user must be a PHI node. |
David Majnemer | 4942810 | 2014-09-02 16:22:00 +0000 | [diff] [blame] | 648 | PHINode *PN = cast<PHINode>(User); |
Chris Lattner | cc9cbc6 | 2010-08-29 17:46:00 +0000 | [diff] [blame] | 649 | |
David Majnemer | 6bc83e0 | 2015-07-12 03:53:05 +0000 | [diff] [blame] | 650 | // Surprisingly, instructions can be used outside of loops without any |
| 651 | // exits. This can only happen in PHI nodes if the incoming block is |
| 652 | // unreachable. |
| 653 | Use &U = UI.getUse(); |
| 654 | BasicBlock *BB = PN->getIncomingBlock(U); |
| 655 | if (!DT->isReachableFromEntry(BB)) { |
| 656 | U = UndefValue::get(I.getType()); |
| 657 | continue; |
| 658 | } |
| 659 | |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 660 | BasicBlock *ExitBlock = PN->getParent(); |
| 661 | assert(ExitBlockSet.count(ExitBlock) && |
| 662 | "The LCSSA PHI is not in an exit block!"); |
| 663 | |
Evgeniy Stepanov | 10280da | 2014-06-25 07:54:58 +0000 | [diff] [blame] | 664 | Instruction *New; |
| 665 | auto It = SunkCopies.find(ExitBlock); |
Evgeniy Stepanov | d99cca2 | 2014-06-25 09:17:21 +0000 | [diff] [blame] | 666 | if (It != SunkCopies.end()) |
Evgeniy Stepanov | 10280da | 2014-06-25 07:54:58 +0000 | [diff] [blame] | 667 | New = It->second; |
Evgeniy Stepanov | d99cca2 | 2014-06-25 09:17:21 +0000 | [diff] [blame] | 668 | else |
| 669 | New = SunkCopies[ExitBlock] = |
David Majnemer | 42a0730 | 2016-01-04 03:37:39 +0000 | [diff] [blame] | 670 | CloneInstructionInExitBlock(I, *ExitBlock, *PN, LI, SafetyInfo); |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 671 | |
| 672 | PN->replaceAllUsesWith(New); |
| 673 | PN->eraseFromParent(); |
Chris Lattner | cd96b4d | 2010-08-29 04:28:20 +0000 | [diff] [blame] | 674 | } |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 675 | |
Chris Lattner | 1a1ed69 | 2010-08-29 18:00:00 +0000 | [diff] [blame] | 676 | CurAST->deleteValue(&I); |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 677 | I.eraseFromParent(); |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 678 | return Changed; |
Chris Lattner | aaaea51 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 679 | } |
Chris Lattner | 6443769 | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 680 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 681 | /// When an instruction is found to only use loop invariant operands that |
| 682 | /// is safe to hoist, this instruction is called to do the dirty work. |
Chris Lattner | f64f2d3 | 2002-09-26 16:52:07 +0000 | [diff] [blame] | 683 | /// |
Sanjoy Das | 7a2e2be | 2016-01-28 15:51:58 +0000 | [diff] [blame] | 684 | static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, |
| 685 | const LICMSafetyInfo *SafetyInfo) { |
| 686 | auto *Preheader = CurLoop->getLoopPreheader(); |
David Greene | 0fd8622 | 2010-01-05 01:27:30 +0000 | [diff] [blame] | 687 | DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " |
Evan Cheng | f815861 | 2009-10-12 22:25:23 +0000 | [diff] [blame] | 688 | << I << "\n"); |
Sanjoy Das | 7a2e2be | 2016-01-28 15:51:58 +0000 | [diff] [blame] | 689 | |
| 690 | // Metadata can be dependent on conditions we are hoisting above. |
| 691 | // Conservatively strip all metadata on the instruction unless we were |
| 692 | // guaranteed to execute I if we entered the loop, in which case the metadata |
| 693 | // is valid in the loop preheader. |
| 694 | if (I.hasMetadataOtherThanDebugLoc() && |
| 695 | // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning |
| 696 | // time in isGuaranteedToExecute if we don't actually have anything to |
| 697 | // drop. It is a compile time optimization, not required for correctness. |
| 698 | !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo)) |
| 699 | I.dropUnknownNonDebugMetadata(); |
| 700 | |
Chris Lattner | 6ac0659 | 2010-08-29 18:18:40 +0000 | [diff] [blame] | 701 | // Move the new node to the Preheader, before its terminator. |
| 702 | I.moveBefore(Preheader->getTerminator()); |
Misha Brukman | b1c9317 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 703 | |
Chris Lattner | aaaea51 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 704 | if (isa<LoadInst>(I)) ++NumMovedLoads; |
Chris Lattner | 20cda26 | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 705 | else if (isa<CallInst>(I)) ++NumMovedCalls; |
Chris Lattner | 718b221 | 2002-09-26 16:38:03 +0000 | [diff] [blame] | 706 | ++NumHoisted; |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 707 | return true; |
Chris Lattner | 6ec05f5 | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 708 | } |
| 709 | |
Sanjoy Das | f8a0db5 | 2015-05-18 18:07:00 +0000 | [diff] [blame] | 710 | /// Only sink or hoist an instruction if it is not a trapping instruction, |
| 711 | /// or if the instruction is known not to trap when moved to the preheader. |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 712 | /// or if it is a trapping instruction and is guaranteed to execute. |
Sanjoy Das | f8a0db5 | 2015-05-18 18:07:00 +0000 | [diff] [blame] | 713 | static bool isSafeToExecuteUnconditionally(const Instruction &Inst, |
Pete Cooper | 0cabcf2 | 2015-05-13 01:12:18 +0000 | [diff] [blame] | 714 | const DominatorTree *DT, |
Sanjoy Das | f8a0db5 | 2015-05-18 18:07:00 +0000 | [diff] [blame] | 715 | const TargetLibraryInfo *TLI, |
Pete Cooper | 0cabcf2 | 2015-05-13 01:12:18 +0000 | [diff] [blame] | 716 | const Loop *CurLoop, |
Philip Reames | b47b9c2 | 2015-05-22 02:14:05 +0000 | [diff] [blame] | 717 | const LICMSafetyInfo *SafetyInfo, |
| 718 | const Instruction *CtxI) { |
Sanjoy Das | f8a0db5 | 2015-05-18 18:07:00 +0000 | [diff] [blame] | 719 | if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT, TLI)) |
Eli Friedman | b8f6a4f | 2009-07-17 04:28:42 +0000 | [diff] [blame] | 720 | return true; |
Misha Brukman | b1c9317 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 721 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 722 | return isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo); |
Eli Friedman | 0cdc148 | 2011-07-20 21:37:47 +0000 | [diff] [blame] | 723 | } |
| 724 | |
Pete Cooper | 0cabcf2 | 2015-05-13 01:12:18 +0000 | [diff] [blame] | 725 | static bool isGuaranteedToExecute(const Instruction &Inst, |
| 726 | const DominatorTree *DT, |
| 727 | const Loop *CurLoop, |
| 728 | const LICMSafetyInfo * SafetyInfo) { |
Nadav Rotem | 03dcd85 | 2012-09-04 10:25:04 +0000 | [diff] [blame] | 729 | |
Philip Reames | b35f46c | 2014-12-29 23:00:57 +0000 | [diff] [blame] | 730 | // We have to check to make sure that the instruction dominates all |
Chris Lattner | c051768 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 731 | // of the exit blocks. If it doesn't, then there is a path out of the loop |
| 732 | // which does not execute this instruction, so we can't hoist it. |
Tanya Lattner | 57c03df | 2003-08-05 18:45:46 +0000 | [diff] [blame] | 733 | |
Chris Lattner | c051768 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 734 | // If the instruction is in the header block for the loop (which is very |
| 735 | // common), it is always guaranteed to dominate the exit blocks. Since this |
| 736 | // is a common case, and can save some work, check it now. |
Chris Lattner | aaaea51 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 737 | if (Inst.getParent() == CurLoop->getHeader()) |
Philip Reames | b35f46c | 2014-12-29 23:00:57 +0000 | [diff] [blame] | 738 | // If there's a throw in the header block, we can't guarantee we'll reach |
| 739 | // Inst. |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 740 | return !SafetyInfo->HeaderMayThrow; |
Philip Reames | b35f46c | 2014-12-29 23:00:57 +0000 | [diff] [blame] | 741 | |
| 742 | // Somewhere in this loop there is an instruction which may throw and make us |
| 743 | // exit the loop. |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 744 | if (SafetyInfo->MayThrow) |
Philip Reames | b35f46c | 2014-12-29 23:00:57 +0000 | [diff] [blame] | 745 | return false; |
Tanya Lattner | 57c03df | 2003-08-05 18:45:46 +0000 | [diff] [blame] | 746 | |
Chris Lattner | c051768 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 747 | // Get the exit blocks for the current loop. |
Devang Patel | b5933bb | 2007-08-21 00:31:24 +0000 | [diff] [blame] | 748 | SmallVector<BasicBlock*, 8> ExitBlocks; |
Chris Lattner | 35eaa55 | 2004-04-18 22:15:13 +0000 | [diff] [blame] | 749 | CurLoop->getExitBlocks(ExitBlocks); |
Chris Lattner | c051768 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 750 | |
Chris Lattner | 27497ec | 2011-01-02 18:45:39 +0000 | [diff] [blame] | 751 | // Verify that the block dominates each of the exit blocks of the loop. |
Sanjay Patel | 9f088ab | 2016-01-08 22:59:42 +0000 | [diff] [blame] | 752 | for (BasicBlock *ExitBlock : ExitBlocks) |
| 753 | if (!DT->dominates(Inst.getParent(), ExitBlock)) |
Chris Lattner | aaaea51 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 754 | return false; |
Misha Brukman | b1c9317 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 755 | |
Nick Lewycky | 78ee67e | 2012-05-01 04:03:01 +0000 | [diff] [blame] | 756 | // As a degenerate case, if the loop is statically infinite then we haven't |
| 757 | // proven anything since there are no exit blocks. |
| 758 | if (ExitBlocks.empty()) |
| 759 | return false; |
| 760 | |
Tanya Lattner | 57c03df | 2003-08-05 18:45:46 +0000 | [diff] [blame] | 761 | return true; |
| 762 | } |
| 763 | |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 764 | namespace { |
| 765 | class LoopPromoter : public LoadAndStorePromoter { |
| 766 | Value *SomePtr; // Designated pointer to store to. |
Craig Topper | 71b7b68 | 2014-08-21 05:55:13 +0000 | [diff] [blame] | 767 | SmallPtrSetImpl<Value*> &PointerMustAliases; |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 768 | SmallVectorImpl<BasicBlock*> &LoopExitBlocks; |
Dan Gohman | b948736 | 2012-08-08 00:00:26 +0000 | [diff] [blame] | 769 | SmallVectorImpl<Instruction*> &LoopInsertPts; |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 770 | PredIteratorCache &PredCache; |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 771 | AliasSetTracker &AST; |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 772 | LoopInfo &LI; |
Eli Friedman | ddf7f55 | 2011-05-27 20:31:51 +0000 | [diff] [blame] | 773 | DebugLoc DL; |
Tobias Grosser | 4a5d9a9 | 2011-07-06 19:19:55 +0000 | [diff] [blame] | 774 | int Alignment; |
Hal Finkel | cc39b67 | 2014-07-24 12:16:19 +0000 | [diff] [blame] | 775 | AAMDNodes AATags; |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 776 | |
| 777 | Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const { |
| 778 | if (Instruction *I = dyn_cast<Instruction>(V)) |
| 779 | if (Loop *L = LI.getLoopFor(I->getParent())) |
| 780 | if (!L->contains(BB)) { |
| 781 | // We need to create an LCSSA PHI node for the incoming value and |
| 782 | // store that. |
Duncan P. N. Exon Smith | be4d8cb | 2015-10-13 19:26:58 +0000 | [diff] [blame] | 783 | PHINode *PN = |
| 784 | PHINode::Create(I->getType(), PredCache.size(BB), |
| 785 | I->getName() + ".lcssa", &BB->front()); |
Daniel Berlin | b4e7a4a | 2015-04-21 21:11:50 +0000 | [diff] [blame] | 786 | for (BasicBlock *Pred : PredCache.get(BB)) |
| 787 | PN->addIncoming(I, Pred); |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 788 | return PN; |
| 789 | } |
| 790 | return V; |
| 791 | } |
| 792 | |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 793 | public: |
Pete Cooper | 41e0ee3 | 2015-05-13 01:12:16 +0000 | [diff] [blame] | 794 | LoopPromoter(Value *SP, |
| 795 | ArrayRef<const Instruction *> Insts, |
Craig Topper | 71b7b68 | 2014-08-21 05:55:13 +0000 | [diff] [blame] | 796 | SSAUpdater &S, SmallPtrSetImpl<Value *> &PMA, |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 797 | SmallVectorImpl<BasicBlock *> &LEB, |
| 798 | SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC, |
| 799 | AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment, |
Hal Finkel | cc39b67 | 2014-07-24 12:16:19 +0000 | [diff] [blame] | 800 | const AAMDNodes &AATags) |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 801 | : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA), |
| 802 | LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast), |
Hal Finkel | cc39b67 | 2014-07-24 12:16:19 +0000 | [diff] [blame] | 803 | LI(li), DL(dl), Alignment(alignment), AATags(AATags) {} |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 804 | |
Craig Topper | 3e4c697 | 2014-03-05 09:10:37 +0000 | [diff] [blame] | 805 | bool isInstInList(Instruction *I, |
| 806 | const SmallVectorImpl<Instruction*> &) const override { |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 807 | Value *Ptr; |
| 808 | if (LoadInst *LI = dyn_cast<LoadInst>(I)) |
| 809 | Ptr = LI->getOperand(0); |
| 810 | else |
| 811 | Ptr = cast<StoreInst>(I)->getPointerOperand(); |
| 812 | return PointerMustAliases.count(Ptr); |
| 813 | } |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 814 | |
Craig Topper | 3e4c697 | 2014-03-05 09:10:37 +0000 | [diff] [blame] | 815 | void doExtraRewritesBeforeFinalDeletion() const override { |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 816 | // Insert stores after in the loop exit blocks. Each exit block gets a |
| 817 | // store of the live-out values that feed them. Since we've already told |
| 818 | // the SSA updater about the defs in the loop and the preheader |
| 819 | // definition, it is all set and we can start using it. |
| 820 | for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) { |
| 821 | BasicBlock *ExitBlock = LoopExitBlocks[i]; |
| 822 | Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock); |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 823 | LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock); |
| 824 | Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock); |
Dan Gohman | b948736 | 2012-08-08 00:00:26 +0000 | [diff] [blame] | 825 | Instruction *InsertPos = LoopInsertPts[i]; |
Chandler Carruth | fc25854 | 2014-02-11 12:52:27 +0000 | [diff] [blame] | 826 | StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos); |
Tobias Grosser | 4a5d9a9 | 2011-07-06 19:19:55 +0000 | [diff] [blame] | 827 | NewSI->setAlignment(Alignment); |
Eli Friedman | ddf7f55 | 2011-05-27 20:31:51 +0000 | [diff] [blame] | 828 | NewSI->setDebugLoc(DL); |
Hal Finkel | cc39b67 | 2014-07-24 12:16:19 +0000 | [diff] [blame] | 829 | if (AATags) NewSI->setAAMetadata(AATags); |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 830 | } |
| 831 | } |
| 832 | |
Craig Topper | 3e4c697 | 2014-03-05 09:10:37 +0000 | [diff] [blame] | 833 | void replaceLoadWithValue(LoadInst *LI, Value *V) const override { |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 834 | // Update alias analysis. |
| 835 | AST.copyValue(LI, V); |
| 836 | } |
Craig Topper | 3e4c697 | 2014-03-05 09:10:37 +0000 | [diff] [blame] | 837 | void instructionDeleted(Instruction *I) const override { |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 838 | AST.deleteValue(I); |
| 839 | } |
| 840 | }; |
Alexander Kornienko | f00654e | 2015-06-23 09:49:53 +0000 | [diff] [blame] | 841 | } // end anon namespace |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 842 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 843 | /// Try to promote memory values to scalars by sinking stores out of the |
| 844 | /// loop and moving loads to before the loop. We do this by looping over |
| 845 | /// the stores in the loop, looking for stores to Must pointers which are |
| 846 | /// loop invariant. |
Chris Lattner | 45d67d6 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 847 | /// |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 848 | bool llvm::promoteLoopAccessesToScalars(AliasSet &AS, |
| 849 | SmallVectorImpl<BasicBlock*>&ExitBlocks, |
| 850 | SmallVectorImpl<Instruction*>&InsertPts, |
| 851 | PredIteratorCache &PIC, LoopInfo *LI, |
Philip Reames | b54c8e6 | 2016-03-09 22:59:30 +0000 | [diff] [blame] | 852 | DominatorTree *DT, |
| 853 | const TargetLibraryInfo *TLI, |
| 854 | Loop *CurLoop, |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 855 | AliasSetTracker *CurAST, |
| 856 | LICMSafetyInfo * SafetyInfo) { |
| 857 | // Verify inputs. |
| 858 | assert(LI != nullptr && DT != nullptr && |
| 859 | CurLoop != nullptr && CurAST != nullptr && |
| 860 | SafetyInfo != nullptr && |
| 861 | "Unexpected Input to promoteLoopAccessesToScalars"); |
Sanjay Patel | 9913322 | 2016-01-13 23:01:57 +0000 | [diff] [blame] | 862 | |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 863 | // We can promote this alias set if it has a store, if it is a "Must" alias |
| 864 | // set, if the pointer is loop invariant, and if we are not eliminating any |
| 865 | // volatile loads or stores. |
| 866 | if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() || |
| 867 | AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue())) |
Sanjay Patel | 9913322 | 2016-01-13 23:01:57 +0000 | [diff] [blame] | 868 | return false; |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 869 | |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 870 | assert(!AS.empty() && |
| 871 | "Must alias set should have at least one pointer element in it!"); |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 872 | |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 873 | Value *SomePtr = AS.begin()->getValue(); |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 874 | BasicBlock * Preheader = CurLoop->getLoopPreheader(); |
Chris Lattner | 45d67d6 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 875 | |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 876 | // It isn't safe to promote a load/store from the loop if the load/store is |
| 877 | // conditional. For example, turning: |
Chris Lattner | 45d67d6 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 878 | // |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 879 | // for () { if (c) *P += 1; } |
Chris Lattner | 45d67d6 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 880 | // |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 881 | // into: |
| 882 | // |
| 883 | // tmp = *P; for () { if (c) tmp +=1; } *P = tmp; |
| 884 | // |
| 885 | // is not safe, because *P may only be valid to access if 'c' is true. |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 886 | // |
Philip Reames | b54c8e6 | 2016-03-09 22:59:30 +0000 | [diff] [blame] | 887 | // The safety property divides into two parts: |
| 888 | // 1) The memory may not be dereferenceable on entry to the loop. In this |
| 889 | // case, we can't insert the required load in the preheader. |
| 890 | // 2) The memory model does not allow us to insert a store along any dynamic |
| 891 | // path which did not originally have one. |
| 892 | // |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 893 | // It is safe to promote P if all uses are direct load/stores and if at |
| 894 | // least one is guaranteed to be executed. |
| 895 | bool GuaranteedToExecute = false; |
Tobias Grosser | 4a5d9a9 | 2011-07-06 19:19:55 +0000 | [diff] [blame] | 896 | |
Philip Reames | b54c8e6 | 2016-03-09 22:59:30 +0000 | [diff] [blame] | 897 | // It is also safe to promote P if we can prove that speculating a load into |
| 898 | // the preheader is safe (i.e. proving dereferenceability on all |
| 899 | // paths through the loop), and that the memory can be proven thread local |
| 900 | // (so that the memory model requirement doesn't apply.) We first establish |
| 901 | // the former, and then run a capture analysis below to establish the later. |
| 902 | // We can use any access within the alias set to prove dereferenceability |
| 903 | // since they're all must alias. |
| 904 | bool CanSpeculateLoad = false; |
| 905 | |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 906 | SmallVector<Instruction*, 64> LoopUses; |
| 907 | SmallPtrSet<Value*, 4> PointerMustAliases; |
Chris Lattner | 45d67d6 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 908 | |
Tobias Grosser | 4a5d9a9 | 2011-07-06 19:19:55 +0000 | [diff] [blame] | 909 | // We start with an alignment of one and try to find instructions that allow |
| 910 | // us to prove better alignment. |
| 911 | unsigned Alignment = 1; |
Hal Finkel | cc39b67 | 2014-07-24 12:16:19 +0000 | [diff] [blame] | 912 | AAMDNodes AATags; |
Bruno Cardoso Lopes | 46d5bf2 | 2014-11-28 19:47:46 +0000 | [diff] [blame] | 913 | bool HasDedicatedExits = CurLoop->hasDedicatedExits(); |
Tobias Grosser | 4a5d9a9 | 2011-07-06 19:19:55 +0000 | [diff] [blame] | 914 | |
Philip Reames | b54c8e6 | 2016-03-09 22:59:30 +0000 | [diff] [blame] | 915 | // Don't sink stores from loops without dedicated block exits. Exits |
| 916 | // containing indirect branches are not transformed by loop simplify, |
| 917 | // make sure we catch that. An additional load may be generated in the |
| 918 | // preheader for SSA updater, so also avoid sinking when no preheader |
| 919 | // is available. |
| 920 | if (!HasDedicatedExits || !Preheader) |
| 921 | return false; |
| 922 | |
| 923 | const DataLayout &MDL = Preheader->getModule()->getDataLayout(); |
| 924 | |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 925 | // Check that all of the pointers in the alias set have the same type. We |
| 926 | // cannot (yet) promote a memory location that is loaded and stored in |
Hal Finkel | cc39b67 | 2014-07-24 12:16:19 +0000 | [diff] [blame] | 927 | // different sizes. While we are at it, collect alignment and AA info. |
Sanjay Patel | 9913322 | 2016-01-13 23:01:57 +0000 | [diff] [blame] | 928 | bool Changed = false; |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 929 | for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) { |
| 930 | Value *ASIV = ASI->getValue(); |
| 931 | PointerMustAliases.insert(ASIV); |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 932 | |
Chris Lattner | f12c08d | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 933 | // Check that all of the pointers in the alias set have the same type. We |
| 934 | // cannot (yet) promote a memory location that is loaded and stored in |
| 935 | // different sizes. |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 936 | if (SomePtr->getType() != ASIV->getType()) |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 937 | return Changed; |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 938 | |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 939 | for (User *U : ASIV->users()) { |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 940 | // Ignore instructions that are outside the loop. |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 941 | Instruction *UI = dyn_cast<Instruction>(U); |
| 942 | if (!UI || !CurLoop->contains(UI)) |
Chris Lattner | f12c08d | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 943 | continue; |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 944 | |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 945 | // If there is an non-load/store instruction in the loop, we can't promote |
| 946 | // it. |
Sanjay Patel | 9f49b68 | 2016-01-08 22:05:03 +0000 | [diff] [blame] | 947 | if (const LoadInst *Load = dyn_cast<LoadInst>(UI)) { |
| 948 | assert(!Load->isVolatile() && "AST broken"); |
| 949 | if (!Load->isSimple()) |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 950 | return Changed; |
Philip Reames | b54c8e6 | 2016-03-09 22:59:30 +0000 | [diff] [blame] | 951 | |
| 952 | if (!GuaranteedToExecute && !CanSpeculateLoad) |
| 953 | CanSpeculateLoad = |
| 954 | isSafeToExecuteUnconditionally(*Load, DT, TLI, CurLoop, |
| 955 | SafetyInfo, |
| 956 | Preheader->getTerminator()); |
Sanjay Patel | 9f49b68 | 2016-01-08 22:05:03 +0000 | [diff] [blame] | 957 | } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) { |
Chris Lattner | 408a684 | 2010-12-19 05:57:25 +0000 | [diff] [blame] | 958 | // Stores *of* the pointer are not interesting, only stores *to* the |
| 959 | // pointer. |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 960 | if (UI->getOperand(1) != ASIV) |
Chris Lattner | 408a684 | 2010-12-19 05:57:25 +0000 | [diff] [blame] | 961 | continue; |
Sanjay Patel | 9f49b68 | 2016-01-08 22:05:03 +0000 | [diff] [blame] | 962 | assert(!Store->isVolatile() && "AST broken"); |
| 963 | if (!Store->isSimple()) |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 964 | return Changed; |
Eli Friedman | 0cdc148 | 2011-07-20 21:37:47 +0000 | [diff] [blame] | 965 | |
| 966 | // Note that we only check GuaranteedToExecute inside the store case |
| 967 | // so that we do not introduce stores where they did not exist before |
| 968 | // (which would break the LLVM concurrency model). |
| 969 | |
| 970 | // If the alignment of this instruction allows us to specify a more |
| 971 | // restrictive (and performant) alignment and if we are sure this |
| 972 | // instruction will be executed, update the alignment. |
| 973 | // Larger is better, with the exception of 0 being the best alignment. |
Sanjay Patel | 9f49b68 | 2016-01-08 22:05:03 +0000 | [diff] [blame] | 974 | unsigned InstAlignment = Store->getAlignment(); |
Chris Lattner | f5cca68 | 2012-12-31 08:37:17 +0000 | [diff] [blame] | 975 | if ((InstAlignment > Alignment || InstAlignment == 0) && Alignment != 0) |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 976 | if (isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo)) { |
Eli Friedman | 0cdc148 | 2011-07-20 21:37:47 +0000 | [diff] [blame] | 977 | GuaranteedToExecute = true; |
| 978 | Alignment = InstAlignment; |
| 979 | } |
| 980 | |
| 981 | if (!GuaranteedToExecute) |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 982 | GuaranteedToExecute = isGuaranteedToExecute(*UI, DT, |
| 983 | CurLoop, SafetyInfo); |
Eli Friedman | 0cdc148 | 2011-07-20 21:37:47 +0000 | [diff] [blame] | 984 | |
Philip Reames | b54c8e6 | 2016-03-09 22:59:30 +0000 | [diff] [blame] | 985 | |
| 986 | if (!GuaranteedToExecute && !CanSpeculateLoad) { |
| 987 | CanSpeculateLoad = |
| 988 | isDereferenceableAndAlignedPointer(Store->getPointerOperand(), |
| 989 | Store->getAlignment(), MDL, |
| 990 | Preheader->getTerminator(), |
| 991 | DT, TLI); |
| 992 | } |
Chris Lattner | be90190 | 2010-09-06 05:11:24 +0000 | [diff] [blame] | 993 | } else |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 994 | return Changed; // Not a load or store. |
Tobias Grosser | 4a5d9a9 | 2011-07-06 19:19:55 +0000 | [diff] [blame] | 995 | |
Hal Finkel | cc39b67 | 2014-07-24 12:16:19 +0000 | [diff] [blame] | 996 | // Merge the AA tags. |
Chris Lattner | f5cca68 | 2012-12-31 08:37:17 +0000 | [diff] [blame] | 997 | if (LoopUses.empty()) { |
Hal Finkel | cc39b67 | 2014-07-24 12:16:19 +0000 | [diff] [blame] | 998 | // On the first load/store, just take its AA tags. |
| 999 | UI->getAAMetadata(AATags); |
| 1000 | } else if (AATags) { |
| 1001 | UI->getAAMetadata(AATags, /* Merge = */ true); |
Chris Lattner | f5cca68 | 2012-12-31 08:37:17 +0000 | [diff] [blame] | 1002 | } |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 1003 | |
| 1004 | LoopUses.push_back(UI); |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 1005 | } |
| 1006 | } |
Tobias Grosser | 4a5d9a9 | 2011-07-06 19:19:55 +0000 | [diff] [blame] | 1007 | |
Philip Reames | b54c8e6 | 2016-03-09 22:59:30 +0000 | [diff] [blame] | 1008 | // Check legality per comment above. Otherwise, we can't promote. |
| 1009 | bool PromotionIsLegal = GuaranteedToExecute; |
| 1010 | if (!PromotionIsLegal && CanSpeculateLoad) { |
| 1011 | // If this is a thread local location, then we can insert stores along |
| 1012 | // paths which originally didn't have them without violating the memory |
| 1013 | // model. |
| 1014 | Value *Object = GetUnderlyingObject(SomePtr, MDL); |
| 1015 | PromotionIsLegal = isAllocLikeFn(Object, TLI) && |
| 1016 | !PointerMayBeCaptured(Object, true, true); |
| 1017 | } |
| 1018 | if (!PromotionIsLegal) |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 1019 | return Changed; |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 1020 | |
David Majnemer | 219055f | 2016-01-04 17:42:19 +0000 | [diff] [blame] | 1021 | // Figure out the loop exits and their insertion points, if this is the |
| 1022 | // first promotion. |
| 1023 | if (ExitBlocks.empty()) { |
| 1024 | CurLoop->getUniqueExitBlocks(ExitBlocks); |
| 1025 | InsertPts.clear(); |
| 1026 | InsertPts.reserve(ExitBlocks.size()); |
David Majnemer | b33f3a2 | 2016-01-04 23:16:22 +0000 | [diff] [blame] | 1027 | for (BasicBlock *ExitBlock : ExitBlocks) |
David Majnemer | 219055f | 2016-01-04 17:42:19 +0000 | [diff] [blame] | 1028 | InsertPts.push_back(&*ExitBlock->getFirstInsertionPt()); |
David Majnemer | 219055f | 2016-01-04 17:42:19 +0000 | [diff] [blame] | 1029 | } |
| 1030 | |
David Majnemer | b33f3a2 | 2016-01-04 23:16:22 +0000 | [diff] [blame] | 1031 | // Can't insert into a catchswitch. |
| 1032 | for (BasicBlock *ExitBlock : ExitBlocks) |
| 1033 | if (isa<CatchSwitchInst>(ExitBlock->getTerminator())) |
| 1034 | return Changed; |
| 1035 | |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 1036 | // Otherwise, this is safe to promote, lets do it! |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 1037 | DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " <<*SomePtr<<'\n'); |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 1038 | Changed = true; |
| 1039 | ++NumPromoted; |
| 1040 | |
Eli Friedman | ddf7f55 | 2011-05-27 20:31:51 +0000 | [diff] [blame] | 1041 | // Grab a debug location for the inserted loads/stores; given that the |
| 1042 | // inserted loads/stores have little relation to the original loads/stores, |
| 1043 | // this code just arbitrarily picks a location from one, since any debug |
| 1044 | // location is better than none. |
| 1045 | DebugLoc DL = LoopUses[0]->getDebugLoc(); |
| 1046 | |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 1047 | // We use the SSAUpdater interface to insert phi nodes as required. |
| 1048 | SmallVector<PHINode*, 16> NewPHIs; |
| 1049 | SSAUpdater SSA(&NewPHIs); |
Pete Cooper | 7c4d7b8 | 2015-05-13 22:43:09 +0000 | [diff] [blame] | 1050 | LoopPromoter Promoter(SomePtr, LoopUses, SSA, |
Pete Cooper | 41e0ee3 | 2015-05-13 01:12:16 +0000 | [diff] [blame] | 1051 | PointerMustAliases, ExitBlocks, |
Hal Finkel | cc39b67 | 2014-07-24 12:16:19 +0000 | [diff] [blame] | 1052 | InsertPts, PIC, *CurAST, *LI, DL, Alignment, AATags); |
Tobias Grosser | a3928f5 | 2011-07-06 19:20:02 +0000 | [diff] [blame] | 1053 | |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 1054 | // Set up the preheader to have a definition of the value. It is the live-out |
| 1055 | // value from the preheader that uses in the loop will use. |
| 1056 | LoadInst *PreheaderLoad = |
| 1057 | new LoadInst(SomePtr, SomePtr->getName()+".promoted", |
| 1058 | Preheader->getTerminator()); |
Tobias Grosser | 4a5d9a9 | 2011-07-06 19:19:55 +0000 | [diff] [blame] | 1059 | PreheaderLoad->setAlignment(Alignment); |
Eli Friedman | ddf7f55 | 2011-05-27 20:31:51 +0000 | [diff] [blame] | 1060 | PreheaderLoad->setDebugLoc(DL); |
Hal Finkel | cc39b67 | 2014-07-24 12:16:19 +0000 | [diff] [blame] | 1061 | if (AATags) PreheaderLoad->setAAMetadata(AATags); |
Chris Lattner | 1dc98b4 | 2010-08-29 06:43:52 +0000 | [diff] [blame] | 1062 | SSA.AddAvailableValue(Preheader, PreheaderLoad); |
| 1063 | |
Chris Lattner | b68ec5c | 2011-01-15 00:12:35 +0000 | [diff] [blame] | 1064 | // Rewrite all the loads in the loop and remember all the definitions from |
| 1065 | // stores in the loop. |
| 1066 | Promoter.run(LoopUses); |
Eli Friedman | c5f22a7 | 2011-04-07 01:35:06 +0000 | [diff] [blame] | 1067 | |
| 1068 | // If the SSAUpdater didn't use the load in the preheader, just zap it now. |
| 1069 | if (PreheaderLoad->use_empty()) |
| 1070 | PreheaderLoad->eraseFromParent(); |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 1071 | |
| 1072 | return Changed; |
Chris Lattner | a51fa88 | 2002-08-22 21:39:55 +0000 | [diff] [blame] | 1073 | } |
Devang Patel | b98a097 | 2007-07-31 08:01:41 +0000 | [diff] [blame] | 1074 | |
Roman Gareev | 036c088 | 2016-02-15 14:48:50 +0000 | [diff] [blame] | 1075 | /// Returns an owning pointer to an alias set which incorporates aliasing info |
Chandler Carruth | ad8cb38 | 2016-02-27 04:34:07 +0000 | [diff] [blame] | 1076 | /// from L and all subloops of L. |
| 1077 | AliasSetTracker *LICM::collectAliasInfoForLoop(Loop *L) { |
Roman Gareev | 036c088 | 2016-02-15 14:48:50 +0000 | [diff] [blame] | 1078 | AliasSetTracker *CurAST = nullptr; |
Chandler Carruth | ad8cb38 | 2016-02-27 04:34:07 +0000 | [diff] [blame] | 1079 | SmallVector<Loop *, 4> RecomputeLoops; |
Roman Gareev | 036c088 | 2016-02-15 14:48:50 +0000 | [diff] [blame] | 1080 | for (Loop *InnerL : L->getSubLoops()) { |
Chandler Carruth | ad8cb38 | 2016-02-27 04:34:07 +0000 | [diff] [blame] | 1081 | auto MapI = LoopToAliasSetMap.find(InnerL); |
| 1082 | // If the AST for this inner loop is missing it may have been merged into |
| 1083 | // some other loop's AST and then that loop unrolled, and so we need to |
| 1084 | // recompute it. |
| 1085 | if (MapI == LoopToAliasSetMap.end()) { |
| 1086 | RecomputeLoops.push_back(InnerL); |
| 1087 | continue; |
| 1088 | } |
| 1089 | AliasSetTracker *InnerAST = MapI->second; |
Roman Gareev | 036c088 | 2016-02-15 14:48:50 +0000 | [diff] [blame] | 1090 | |
| 1091 | if (CurAST != nullptr) { |
| 1092 | // What if InnerLoop was modified by other passes ? |
| 1093 | CurAST->add(*InnerAST); |
| 1094 | |
| 1095 | // Once we've incorporated the inner loop's AST into ours, we don't need |
| 1096 | // the subloop's anymore. |
| 1097 | delete InnerAST; |
| 1098 | } else { |
| 1099 | CurAST = InnerAST; |
| 1100 | } |
Chandler Carruth | ad8cb38 | 2016-02-27 04:34:07 +0000 | [diff] [blame] | 1101 | LoopToAliasSetMap.erase(MapI); |
Roman Gareev | 036c088 | 2016-02-15 14:48:50 +0000 | [diff] [blame] | 1102 | } |
| 1103 | if (CurAST == nullptr) |
| 1104 | CurAST = new AliasSetTracker(*AA); |
Chandler Carruth | ad8cb38 | 2016-02-27 04:34:07 +0000 | [diff] [blame] | 1105 | |
| 1106 | auto mergeLoop = [&](Loop *L) { |
| 1107 | // Loop over the body of this loop, looking for calls, invokes, and stores. |
| 1108 | // Because subloops have already been incorporated into AST, we skip blocks |
| 1109 | // in subloops. |
| 1110 | for (BasicBlock *BB : L->blocks()) |
| 1111 | if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops. |
| 1112 | CurAST->add(*BB); // Incorporate the specified basic block |
| 1113 | }; |
| 1114 | |
| 1115 | // Add everything from the sub loops that are no longer directly available. |
| 1116 | for (Loop *InnerL : RecomputeLoops) |
| 1117 | mergeLoop(InnerL); |
| 1118 | |
| 1119 | // And merge in this loop. |
| 1120 | mergeLoop(L); |
| 1121 | |
Roman Gareev | 036c088 | 2016-02-15 14:48:50 +0000 | [diff] [blame] | 1122 | return CurAST; |
| 1123 | } |
| 1124 | |
Ashutosh Nema | 4780262 | 2015-08-13 11:18:35 +0000 | [diff] [blame] | 1125 | /// Simple analysis hook. Clone alias set info. |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 1126 | /// |
Devang Patel | b98a097 | 2007-07-31 08:01:41 +0000 | [diff] [blame] | 1127 | void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) { |
Chris Lattner | cc9cbc6 | 2010-08-29 17:46:00 +0000 | [diff] [blame] | 1128 | AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); |
Devang Patel | b98a097 | 2007-07-31 08:01:41 +0000 | [diff] [blame] | 1129 | if (!AST) |
| 1130 | return; |
| 1131 | |
| 1132 | AST->copyValue(From, To); |
| 1133 | } |
| 1134 | |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 1135 | /// Simple Analysis hook. Delete value V from alias set |
| 1136 | /// |
Devang Patel | b98a097 | 2007-07-31 08:01:41 +0000 | [diff] [blame] | 1137 | void LICM::deleteAnalysisValue(Value *V, Loop *L) { |
Chris Lattner | cc9cbc6 | 2010-08-29 17:46:00 +0000 | [diff] [blame] | 1138 | AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); |
Devang Patel | b98a097 | 2007-07-31 08:01:41 +0000 | [diff] [blame] | 1139 | if (!AST) |
| 1140 | return; |
| 1141 | |
| 1142 | AST->deleteValue(V); |
| 1143 | } |
David Peixotto | 0d4d5e6 | 2014-09-24 16:48:31 +0000 | [diff] [blame] | 1144 | |
| 1145 | /// Simple Analysis hook. Delete value L from alias set map. |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 1146 | /// |
David Peixotto | 0d4d5e6 | 2014-09-24 16:48:31 +0000 | [diff] [blame] | 1147 | void LICM::deleteAnalysisLoop(Loop *L) { |
| 1148 | AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); |
| 1149 | if (!AST) |
| 1150 | return; |
| 1151 | |
| 1152 | delete AST; |
| 1153 | LoopToAliasSetMap.erase(L); |
| 1154 | } |
Hal Finkel | 3d4269a | 2015-02-22 18:35:32 +0000 | [diff] [blame] | 1155 | |
| 1156 | |
| 1157 | /// Return true if the body of this loop may store into the memory |
| 1158 | /// location pointed to by V. |
| 1159 | /// |
| 1160 | static bool pointerInvalidatedByLoop(Value *V, uint64_t Size, |
| 1161 | const AAMDNodes &AAInfo, |
| 1162 | AliasSetTracker *CurAST) { |
| 1163 | // Check to see if any of the basic blocks in CurLoop invalidate *V. |
| 1164 | return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod(); |
| 1165 | } |
| 1166 | |
| 1167 | /// Little predicate that returns true if the specified basic block is in |
| 1168 | /// a subloop of the current one, not the current one itself. |
| 1169 | /// |
| 1170 | static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) { |
| 1171 | assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); |
| 1172 | return LI->getLoopFor(BB) != CurLoop; |
| 1173 | } |
| 1174 | |