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