Chris Lattner | 81ae3f2 | 2010-12-26 19:39:38 +0000 | [diff] [blame] | 1 | //===-- LoopIdiomRecognize.cpp - Loop idiom recognition -------------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This pass implements an idiom recognizer that transforms simple loops into a |
| 11 | // non-loop form. In cases that this kicks in, it can be a significant |
| 12 | // performance win. |
| 13 | // |
| 14 | //===----------------------------------------------------------------------===// |
Chris Lattner | 0469e01 | 2011-01-02 18:32:09 +0000 | [diff] [blame] | 15 | // |
| 16 | // TODO List: |
| 17 | // |
| 18 | // Future loop memory idioms to recognize: |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 19 | // memcmp, memmove, strlen, etc. |
Chris Lattner | 0469e01 | 2011-01-02 18:32:09 +0000 | [diff] [blame] | 20 | // Future floating point idioms to recognize in -ffast-math mode: |
| 21 | // fpowi |
| 22 | // Future integer operation idioms to recognize: |
| 23 | // ctpop, ctlz, cttz |
| 24 | // |
| 25 | // Beware that isel's default lowering for ctpop is highly inefficient for |
| 26 | // i64 and larger types when i64 is legal and the value has few bits set. It |
| 27 | // would be good to enhance isel to emit a loop for ctpop in this case. |
| 28 | // |
| 29 | // We should enhance the memset/memcpy recognition to handle multiple stores in |
| 30 | // the loop. This would handle things like: |
| 31 | // void foo(_Complex float *P) |
| 32 | // for (i) { __real__(*P) = 0; __imag__(*P) = 0; } |
Chris Lattner | 8fac5db | 2011-01-02 23:19:45 +0000 | [diff] [blame] | 33 | // |
Chris Lattner | bc661d6 | 2011-02-21 02:08:54 +0000 | [diff] [blame] | 34 | // We should enhance this to handle negative strides through memory. |
| 35 | // Alternatively (and perhaps better) we could rely on an earlier pass to force |
| 36 | // forward iteration through memory, which is generally better for cache |
| 37 | // behavior. Negative strides *do* happen for memset/memcpy loops. |
| 38 | // |
Chris Lattner | 02a9776 | 2011-01-03 01:10:08 +0000 | [diff] [blame] | 39 | // This could recognize common matrix multiplies and dot product idioms and |
Chris Lattner | 8fac5db | 2011-01-02 23:19:45 +0000 | [diff] [blame] | 40 | // replace them with calls to BLAS (if linked in??). |
| 41 | // |
Chris Lattner | 0469e01 | 2011-01-02 18:32:09 +0000 | [diff] [blame] | 42 | //===----------------------------------------------------------------------===// |
Chris Lattner | 81ae3f2 | 2010-12-26 19:39:38 +0000 | [diff] [blame] | 43 | |
Chris Lattner | 81ae3f2 | 2010-12-26 19:39:38 +0000 | [diff] [blame] | 44 | #include "llvm/Transforms/Scalar.h" |
Chandler Carruth | aafe091 | 2012-06-29 12:38:19 +0000 | [diff] [blame] | 45 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | cb18bfa | 2010-12-27 18:39:08 +0000 | [diff] [blame] | 46 | #include "llvm/Analysis/AliasAnalysis.h" |
Chris Lattner | 81ae3f2 | 2010-12-26 19:39:38 +0000 | [diff] [blame] | 47 | #include "llvm/Analysis/LoopPass.h" |
Chris Lattner | 29e14ed | 2010-12-26 23:42:51 +0000 | [diff] [blame] | 48 | #include "llvm/Analysis/ScalarEvolutionExpander.h" |
Chandler Carruth | aafe091 | 2012-06-29 12:38:19 +0000 | [diff] [blame] | 49 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
Benjamin Kramer | 799003b | 2015-03-23 19:32:43 +0000 | [diff] [blame] | 50 | #include "llvm/Analysis/TargetLibraryInfo.h" |
Chandler Carruth | d3e7355 | 2013-01-07 03:08:10 +0000 | [diff] [blame] | 51 | #include "llvm/Analysis/TargetTransformInfo.h" |
Chris Lattner | 7c5f9c3 | 2010-12-26 20:45:45 +0000 | [diff] [blame] | 52 | #include "llvm/Analysis/ValueTracking.h" |
Chandler Carruth | 9fb823b | 2013-01-02 11:36:10 +0000 | [diff] [blame] | 53 | #include "llvm/IR/DataLayout.h" |
Chandler Carruth | 5ad5f15 | 2014-01-13 09:26:24 +0000 | [diff] [blame] | 54 | #include "llvm/IR/Dominators.h" |
Chandler Carruth | 9fb823b | 2013-01-02 11:36:10 +0000 | [diff] [blame] | 55 | #include "llvm/IR/IRBuilder.h" |
| 56 | #include "llvm/IR/IntrinsicInst.h" |
| 57 | #include "llvm/IR/Module.h" |
Chandler Carruth | aafe091 | 2012-06-29 12:38:19 +0000 | [diff] [blame] | 58 | #include "llvm/Support/Debug.h" |
| 59 | #include "llvm/Support/raw_ostream.h" |
Chris Lattner | b9fe685 | 2010-12-27 00:03:23 +0000 | [diff] [blame] | 60 | #include "llvm/Transforms/Utils/Local.h" |
Chris Lattner | 81ae3f2 | 2010-12-26 19:39:38 +0000 | [diff] [blame] | 61 | using namespace llvm; |
| 62 | |
Chandler Carruth | 964daaa | 2014-04-22 02:55:47 +0000 | [diff] [blame] | 63 | #define DEBUG_TYPE "loop-idiom" |
| 64 | |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 65 | STATISTIC(NumMemSet, "Number of memset's formed from loop stores"); |
| 66 | STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores"); |
Chris Lattner | 81ae3f2 | 2010-12-26 19:39:38 +0000 | [diff] [blame] | 67 | |
| 68 | namespace { |
Shuxin Yang | 95de7c3 | 2012-12-09 03:12:46 +0000 | [diff] [blame] | 69 | |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 70 | class LoopIdiomRecognize : public LoopPass { |
| 71 | Loop *CurLoop; |
| 72 | DominatorTree *DT; |
Chandler Carruth | 18c2669 | 2015-08-13 09:27:01 +0000 | [diff] [blame^] | 73 | LoopInfo *LI; |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 74 | ScalarEvolution *SE; |
| 75 | TargetLibraryInfo *TLI; |
| 76 | const TargetTransformInfo *TTI; |
Chris Lattner | 81ae3f2 | 2010-12-26 19:39:38 +0000 | [diff] [blame] | 77 | |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 78 | public: |
| 79 | static char ID; |
| 80 | explicit LoopIdiomRecognize() : LoopPass(ID) { |
| 81 | initializeLoopIdiomRecognizePass(*PassRegistry::getPassRegistry()); |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 82 | } |
Chris Lattner | 81ae3f2 | 2010-12-26 19:39:38 +0000 | [diff] [blame] | 83 | |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 84 | bool runOnLoop(Loop *L, LPPassManager &LPM) override; |
Shuxin Yang | 95de7c3 | 2012-12-09 03:12:46 +0000 | [diff] [blame] | 85 | |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 86 | /// This transformation requires natural loop information & requires that |
| 87 | /// loop preheaders be inserted into the CFG. |
| 88 | /// |
| 89 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
| 90 | AU.addRequired<LoopInfoWrapperPass>(); |
| 91 | AU.addPreserved<LoopInfoWrapperPass>(); |
| 92 | AU.addRequiredID(LoopSimplifyID); |
| 93 | AU.addPreservedID(LoopSimplifyID); |
| 94 | AU.addRequiredID(LCSSAID); |
| 95 | AU.addPreservedID(LCSSAID); |
| 96 | AU.addRequired<AliasAnalysis>(); |
| 97 | AU.addPreserved<AliasAnalysis>(); |
| 98 | AU.addRequired<ScalarEvolution>(); |
| 99 | AU.addPreserved<ScalarEvolution>(); |
| 100 | AU.addPreserved<DominatorTreeWrapperPass>(); |
| 101 | AU.addRequired<DominatorTreeWrapperPass>(); |
| 102 | AU.addRequired<TargetLibraryInfoWrapperPass>(); |
| 103 | AU.addRequired<TargetTransformInfoWrapperPass>(); |
| 104 | } |
Shuxin Yang | 95de7c3 | 2012-12-09 03:12:46 +0000 | [diff] [blame] | 105 | |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 106 | private: |
Chandler Carruth | d9c6070 | 2015-08-13 00:10:03 +0000 | [diff] [blame] | 107 | /// \name Countable Loop Idiom Handling |
| 108 | /// @{ |
| 109 | |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 110 | bool runOnCountableLoop(); |
Chandler Carruth | d9c6070 | 2015-08-13 00:10:03 +0000 | [diff] [blame] | 111 | bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount, |
| 112 | SmallVectorImpl<BasicBlock *> &ExitBlocks); |
| 113 | |
| 114 | bool processLoopStore(StoreInst *SI, const SCEV *BECount); |
| 115 | bool processLoopMemSet(MemSetInst *MSI, const SCEV *BECount); |
| 116 | |
| 117 | bool processLoopStridedStore(Value *DestPtr, unsigned StoreSize, |
| 118 | unsigned StoreAlignment, Value *SplatValue, |
| 119 | Instruction *TheStore, const SCEVAddRecExpr *Ev, |
| 120 | const SCEV *BECount); |
| 121 | bool processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize, |
| 122 | const SCEVAddRecExpr *StoreEv, |
| 123 | const SCEVAddRecExpr *LoadEv, |
| 124 | const SCEV *BECount); |
| 125 | |
| 126 | /// @} |
| 127 | /// \name Noncountable Loop Idiom Handling |
| 128 | /// @{ |
| 129 | |
| 130 | bool runOnNoncountableLoop(); |
| 131 | |
Chandler Carruth | 8219a50 | 2015-08-13 00:44:29 +0000 | [diff] [blame] | 132 | bool recognizePopcount(); |
| 133 | void transformLoopToPopcount(BasicBlock *PreCondBB, Instruction *CntInst, |
| 134 | PHINode *CntPhi, Value *Var); |
| 135 | |
Chandler Carruth | d9c6070 | 2015-08-13 00:10:03 +0000 | [diff] [blame] | 136 | /// @} |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 137 | }; |
| 138 | |
| 139 | } // End anonymous namespace. |
Chris Lattner | 81ae3f2 | 2010-12-26 19:39:38 +0000 | [diff] [blame] | 140 | |
| 141 | char LoopIdiomRecognize::ID = 0; |
| 142 | INITIALIZE_PASS_BEGIN(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms", |
| 143 | false, false) |
Chandler Carruth | 4f8f307 | 2015-01-17 14:16:18 +0000 | [diff] [blame] | 144 | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) |
Chandler Carruth | 7352302 | 2014-01-13 13:07:17 +0000 | [diff] [blame] | 145 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
Chris Lattner | 81ae3f2 | 2010-12-26 19:39:38 +0000 | [diff] [blame] | 146 | INITIALIZE_PASS_DEPENDENCY(LoopSimplify) |
| 147 | INITIALIZE_PASS_DEPENDENCY(LCSSA) |
| 148 | INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) |
Chandler Carruth | b98f63d | 2015-01-15 10:41:28 +0000 | [diff] [blame] | 149 | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) |
Chris Lattner | cb18bfa | 2010-12-27 18:39:08 +0000 | [diff] [blame] | 150 | INITIALIZE_AG_DEPENDENCY(AliasAnalysis) |
Chandler Carruth | 705b185 | 2015-01-31 03:43:40 +0000 | [diff] [blame] | 151 | INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) |
Chris Lattner | 81ae3f2 | 2010-12-26 19:39:38 +0000 | [diff] [blame] | 152 | INITIALIZE_PASS_END(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms", |
| 153 | false, false) |
| 154 | |
| 155 | Pass *llvm::createLoopIdiomPass() { return new LoopIdiomRecognize(); } |
| 156 | |
Chris Lattner | c4ca7ab | 2011-05-22 17:39:56 +0000 | [diff] [blame] | 157 | /// deleteDeadInstruction - Delete this instruction. Before we do, go through |
Chris Lattner | b9fe685 | 2010-12-27 00:03:23 +0000 | [diff] [blame] | 158 | /// and zero out all the operands of this instruction. If any of them become |
| 159 | /// dead, delete them and the computation tree that feeds them. |
| 160 | /// |
Benjamin Kramer | f094d77 | 2015-02-07 21:37:08 +0000 | [diff] [blame] | 161 | static void deleteDeadInstruction(Instruction *I, |
Benjamin Kramer | 8bcc971 | 2012-08-29 15:32:21 +0000 | [diff] [blame] | 162 | const TargetLibraryInfo *TLI) { |
Benjamin Kramer | f094d77 | 2015-02-07 21:37:08 +0000 | [diff] [blame] | 163 | SmallVector<Value *, 16> Operands(I->value_op_begin(), I->value_op_end()); |
| 164 | I->replaceAllUsesWith(UndefValue::get(I->getType())); |
| 165 | I->eraseFromParent(); |
| 166 | for (Value *Op : Operands) |
| 167 | RecursivelyDeleteTriviallyDeadInstructions(Op, TLI); |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 168 | } |
| 169 | |
Shuxin Yang | 95de7c3 | 2012-12-09 03:12:46 +0000 | [diff] [blame] | 170 | //===----------------------------------------------------------------------===// |
| 171 | // |
Shuxin Yang | 95de7c3 | 2012-12-09 03:12:46 +0000 | [diff] [blame] | 172 | // Implementation of LoopIdiomRecognize |
| 173 | // |
| 174 | //===----------------------------------------------------------------------===// |
| 175 | |
Chandler Carruth | d9c6070 | 2015-08-13 00:10:03 +0000 | [diff] [blame] | 176 | bool LoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) { |
| 177 | if (skipOptnoneFunction(L)) |
| 178 | return false; |
| 179 | |
| 180 | CurLoop = L; |
Chandler Carruth | d9c6070 | 2015-08-13 00:10:03 +0000 | [diff] [blame] | 181 | // If the loop could not be converted to canonical form, it must have an |
| 182 | // indirectbr in it, just give up. |
| 183 | if (!L->getLoopPreheader()) |
| 184 | return false; |
| 185 | |
| 186 | // Disable loop idiom recognition if the function's name is a common idiom. |
| 187 | StringRef Name = L->getHeader()->getParent()->getName(); |
| 188 | if (Name == "memset" || Name == "memcpy") |
| 189 | return false; |
| 190 | |
Chandler Carruth | dc29832 | 2015-08-13 01:03:26 +0000 | [diff] [blame] | 191 | DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
Chandler Carruth | 18c2669 | 2015-08-13 09:27:01 +0000 | [diff] [blame^] | 192 | LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
Chandler Carruth | d9c6070 | 2015-08-13 00:10:03 +0000 | [diff] [blame] | 193 | SE = &getAnalysis<ScalarEvolution>(); |
Chandler Carruth | dc29832 | 2015-08-13 01:03:26 +0000 | [diff] [blame] | 194 | TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); |
| 195 | TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI( |
| 196 | *CurLoop->getHeader()->getParent()); |
| 197 | |
Chandler Carruth | d9c6070 | 2015-08-13 00:10:03 +0000 | [diff] [blame] | 198 | if (SE->hasLoopInvariantBackedgeTakenCount(L)) |
| 199 | return runOnCountableLoop(); |
Chandler Carruth | dc29832 | 2015-08-13 01:03:26 +0000 | [diff] [blame] | 200 | |
Chandler Carruth | d9c6070 | 2015-08-13 00:10:03 +0000 | [diff] [blame] | 201 | return runOnNoncountableLoop(); |
| 202 | } |
| 203 | |
Shuxin Yang | 95de7c3 | 2012-12-09 03:12:46 +0000 | [diff] [blame] | 204 | bool LoopIdiomRecognize::runOnCountableLoop() { |
| 205 | const SCEV *BECount = SE->getBackedgeTakenCount(CurLoop); |
Davide Italiano | 8ed0446 | 2015-05-11 21:02:34 +0000 | [diff] [blame] | 206 | assert(!isa<SCEVCouldNotCompute>(BECount) && |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 207 | "runOnCountableLoop() called on a loop without a predictable" |
| 208 | "backedge-taken count"); |
Shuxin Yang | 95de7c3 | 2012-12-09 03:12:46 +0000 | [diff] [blame] | 209 | |
| 210 | // If this loop executes exactly one time, then it should be peeled, not |
| 211 | // optimized by this pass. |
| 212 | if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount)) |
| 213 | if (BECst->getValue()->getValue() == 0) |
| 214 | return false; |
| 215 | |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 216 | SmallVector<BasicBlock *, 8> ExitBlocks; |
Shuxin Yang | 95de7c3 | 2012-12-09 03:12:46 +0000 | [diff] [blame] | 217 | CurLoop->getUniqueExitBlocks(ExitBlocks); |
| 218 | |
| 219 | DEBUG(dbgs() << "loop-idiom Scanning: F[" |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 220 | << CurLoop->getHeader()->getParent()->getName() << "] Loop %" |
| 221 | << CurLoop->getHeader()->getName() << "\n"); |
Shuxin Yang | 95de7c3 | 2012-12-09 03:12:46 +0000 | [diff] [blame] | 222 | |
| 223 | bool MadeChange = false; |
| 224 | // Scan all the blocks in the loop that are not in subloops. |
Davide Italiano | 95a77e8 | 2015-05-14 21:52:12 +0000 | [diff] [blame] | 225 | for (auto *BB : CurLoop->getBlocks()) { |
Shuxin Yang | 95de7c3 | 2012-12-09 03:12:46 +0000 | [diff] [blame] | 226 | // Ignore blocks in subloops. |
Chandler Carruth | 18c2669 | 2015-08-13 09:27:01 +0000 | [diff] [blame^] | 227 | if (LI->getLoopFor(BB) != CurLoop) |
Shuxin Yang | 95de7c3 | 2012-12-09 03:12:46 +0000 | [diff] [blame] | 228 | continue; |
| 229 | |
Davide Italiano | 80625af | 2015-05-13 19:51:21 +0000 | [diff] [blame] | 230 | MadeChange |= runOnLoopBlock(BB, BECount, ExitBlocks); |
Shuxin Yang | 95de7c3 | 2012-12-09 03:12:46 +0000 | [diff] [blame] | 231 | } |
| 232 | return MadeChange; |
| 233 | } |
| 234 | |
Chris Lattner | 8455b6e | 2011-01-02 19:01:03 +0000 | [diff] [blame] | 235 | /// runOnLoopBlock - Process the specified block, which lives in a counted loop |
| 236 | /// with the specified backedge count. This block is known to be in the current |
| 237 | /// loop and not in any subloops. |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 238 | bool LoopIdiomRecognize::runOnLoopBlock( |
| 239 | BasicBlock *BB, const SCEV *BECount, |
| 240 | SmallVectorImpl<BasicBlock *> &ExitBlocks) { |
Chris Lattner | 8455b6e | 2011-01-02 19:01:03 +0000 | [diff] [blame] | 241 | // We can only promote stores in this block if they are unconditionally |
| 242 | // executed in the loop. For a block to be unconditionally executed, it has |
| 243 | // to dominate all the exit blocks of the loop. Verify this now. |
| 244 | for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) |
| 245 | if (!DT->dominates(BB, ExitBlocks[i])) |
| 246 | return false; |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 247 | |
Chris Lattner | 7c5f9c3 | 2010-12-26 20:45:45 +0000 | [diff] [blame] | 248 | bool MadeChange = false; |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 249 | for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) { |
Chris Lattner | a62b01d | 2011-01-04 07:27:30 +0000 | [diff] [blame] | 250 | Instruction *Inst = I++; |
| 251 | // Look for store instructions, which may be optimized to memset/memcpy. |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 252 | if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { |
Chris Lattner | a62b01d | 2011-01-04 07:27:30 +0000 | [diff] [blame] | 253 | WeakVH InstPtr(I); |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 254 | if (!processLoopStore(SI, BECount)) |
| 255 | continue; |
Chris Lattner | a62b01d | 2011-01-04 07:27:30 +0000 | [diff] [blame] | 256 | MadeChange = true; |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 257 | |
Chris Lattner | a62b01d | 2011-01-04 07:27:30 +0000 | [diff] [blame] | 258 | // If processing the store invalidated our iterator, start over from the |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 259 | // top of the block. |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 260 | if (!InstPtr) |
Chris Lattner | a62b01d | 2011-01-04 07:27:30 +0000 | [diff] [blame] | 261 | I = BB->begin(); |
| 262 | continue; |
| 263 | } |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 264 | |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 265 | // Look for memset instructions, which may be optimized to a larger memset. |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 266 | if (MemSetInst *MSI = dyn_cast<MemSetInst>(Inst)) { |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 267 | WeakVH InstPtr(I); |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 268 | if (!processLoopMemSet(MSI, BECount)) |
| 269 | continue; |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 270 | MadeChange = true; |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 271 | |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 272 | // If processing the memset invalidated our iterator, start over from the |
| 273 | // top of the block. |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 274 | if (!InstPtr) |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 275 | I = BB->begin(); |
| 276 | continue; |
| 277 | } |
Chris Lattner | 7c5f9c3 | 2010-12-26 20:45:45 +0000 | [diff] [blame] | 278 | } |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 279 | |
Chris Lattner | 7c5f9c3 | 2010-12-26 20:45:45 +0000 | [diff] [blame] | 280 | return MadeChange; |
Chris Lattner | 81ae3f2 | 2010-12-26 19:39:38 +0000 | [diff] [blame] | 281 | } |
| 282 | |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 283 | /// processLoopStore - See if this store can be promoted to a memset or memcpy. |
Chris Lattner | 7c5f9c3 | 2010-12-26 20:45:45 +0000 | [diff] [blame] | 284 | bool LoopIdiomRecognize::processLoopStore(StoreInst *SI, const SCEV *BECount) { |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 285 | if (!SI->isSimple()) |
| 286 | return false; |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 287 | |
Chris Lattner | 7c5f9c3 | 2010-12-26 20:45:45 +0000 | [diff] [blame] | 288 | Value *StoredVal = SI->getValueOperand(); |
Chris Lattner | 29e14ed | 2010-12-26 23:42:51 +0000 | [diff] [blame] | 289 | Value *StorePtr = SI->getPointerOperand(); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 290 | |
Chris Lattner | 65a699d | 2010-12-28 18:53:48 +0000 | [diff] [blame] | 291 | // Reject stores that are so large that they overflow an unsigned. |
Mehdi Amini | 46a4355 | 2015-03-04 18:43:29 +0000 | [diff] [blame] | 292 | auto &DL = CurLoop->getHeader()->getModule()->getDataLayout(); |
| 293 | uint64_t SizeInBits = DL.getTypeSizeInBits(StoredVal->getType()); |
Chris Lattner | 65a699d | 2010-12-28 18:53:48 +0000 | [diff] [blame] | 294 | if ((SizeInBits & 7) || (SizeInBits >> 32) != 0) |
Chris Lattner | 7c5f9c3 | 2010-12-26 20:45:45 +0000 | [diff] [blame] | 295 | return false; |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 296 | |
Chris Lattner | 7c5f9c3 | 2010-12-26 20:45:45 +0000 | [diff] [blame] | 297 | // See if the pointer expression is an AddRec like {base,+,1} on the current |
| 298 | // loop, which indicates a strided store. If we have something else, it's a |
| 299 | // random store we can't handle. |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 300 | const SCEVAddRecExpr *StoreEv = |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 301 | dyn_cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr)); |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 302 | if (!StoreEv || StoreEv->getLoop() != CurLoop || !StoreEv->isAffine()) |
Chris Lattner | 7c5f9c3 | 2010-12-26 20:45:45 +0000 | [diff] [blame] | 303 | return false; |
| 304 | |
| 305 | // Check to see if the stride matches the size of the store. If so, then we |
| 306 | // know that every byte is touched in the loop. |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 307 | unsigned StoreSize = (unsigned)SizeInBits >> 3; |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 308 | const SCEVConstant *Stride = dyn_cast<SCEVConstant>(StoreEv->getOperand(1)); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 309 | |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 310 | if (!Stride || StoreSize != Stride->getValue()->getValue()) { |
Chris Lattner | bc661d6 | 2011-02-21 02:08:54 +0000 | [diff] [blame] | 311 | // TODO: Could also handle negative stride here someday, that will require |
| 312 | // the validity check in mayLoopAccessLocation to be updated though. |
| 313 | // Enable this to print exact negative strides. |
Chris Lattner | 2333ac2 | 2011-02-21 17:02:55 +0000 | [diff] [blame] | 314 | if (0 && Stride && StoreSize == -Stride->getValue()->getValue()) { |
Chris Lattner | bc661d6 | 2011-02-21 02:08:54 +0000 | [diff] [blame] | 315 | dbgs() << "NEGATIVE STRIDE: " << *SI << "\n"; |
| 316 | dbgs() << "BB: " << *SI->getParent(); |
| 317 | } |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 318 | |
Chris Lattner | 7c5f9c3 | 2010-12-26 20:45:45 +0000 | [diff] [blame] | 319 | return false; |
Chris Lattner | bc661d6 | 2011-02-21 02:08:54 +0000 | [diff] [blame] | 320 | } |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 321 | |
| 322 | // See if we can optimize just this store in isolation. |
| 323 | if (processLoopStridedStore(StorePtr, StoreSize, SI->getAlignment(), |
| 324 | StoredVal, SI, StoreEv, BECount)) |
| 325 | return true; |
Chris Lattner | 29e14ed | 2010-12-26 23:42:51 +0000 | [diff] [blame] | 326 | |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 327 | // If the stored value is a strided load in the same loop with the same stride |
| 328 | // this this may be transformable into a memcpy. This kicks in for stuff like |
| 329 | // for (i) A[i] = B[i]; |
| 330 | if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) { |
| 331 | const SCEVAddRecExpr *LoadEv = |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 332 | dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LI->getOperand(0))); |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 333 | if (LoadEv && LoadEv->getLoop() == CurLoop && LoadEv->isAffine() && |
Eli Friedman | 7c5dc12 | 2011-09-12 20:23:13 +0000 | [diff] [blame] | 334 | StoreEv->getOperand(1) == LoadEv->getOperand(1) && LI->isSimple()) |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 335 | if (processLoopStoreOfLoopLoad(SI, StoreSize, StoreEv, LoadEv, BECount)) |
| 336 | return true; |
| 337 | } |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 338 | // errs() << "UNHANDLED strided store: " << *StoreEv << " - " << *SI << "\n"; |
Chris Lattner | 7c5f9c3 | 2010-12-26 20:45:45 +0000 | [diff] [blame] | 339 | |
Chris Lattner | 81ae3f2 | 2010-12-26 19:39:38 +0000 | [diff] [blame] | 340 | return false; |
| 341 | } |
| 342 | |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 343 | /// processLoopMemSet - See if this memset can be promoted to a large memset. |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 344 | bool LoopIdiomRecognize::processLoopMemSet(MemSetInst *MSI, |
| 345 | const SCEV *BECount) { |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 346 | // We can only handle non-volatile memsets with a constant size. |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 347 | if (MSI->isVolatile() || !isa<ConstantInt>(MSI->getLength())) |
| 348 | return false; |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 349 | |
Chris Lattner | e6b261f | 2011-02-18 22:22:15 +0000 | [diff] [blame] | 350 | // If we're not allowed to hack on memset, we fail. |
| 351 | if (!TLI->has(LibFunc::memset)) |
| 352 | return false; |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 353 | |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 354 | Value *Pointer = MSI->getDest(); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 355 | |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 356 | // See if the pointer expression is an AddRec like {base,+,1} on the current |
| 357 | // loop, which indicates a strided store. If we have something else, it's a |
| 358 | // random store we can't handle. |
| 359 | const SCEVAddRecExpr *Ev = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Pointer)); |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 360 | if (!Ev || Ev->getLoop() != CurLoop || !Ev->isAffine()) |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 361 | return false; |
| 362 | |
| 363 | // Reject memsets that are so large that they overflow an unsigned. |
| 364 | uint64_t SizeInBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue(); |
| 365 | if ((SizeInBytes >> 32) != 0) |
| 366 | return false; |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 367 | |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 368 | // Check to see if the stride matches the size of the memset. If so, then we |
| 369 | // know that every byte is touched in the loop. |
| 370 | const SCEVConstant *Stride = dyn_cast<SCEVConstant>(Ev->getOperand(1)); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 371 | |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 372 | // TODO: Could also handle negative stride here someday, that will require the |
| 373 | // validity check in mayLoopAccessLocation to be updated though. |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 374 | if (!Stride || MSI->getLength() != Stride->getValue()) |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 375 | return false; |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 376 | |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 377 | return processLoopStridedStore(Pointer, (unsigned)SizeInBytes, |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 378 | MSI->getAlignment(), MSI->getValue(), MSI, Ev, |
| 379 | BECount); |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 380 | } |
| 381 | |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 382 | /// mayLoopAccessLocation - Return true if the specified loop might access the |
| 383 | /// specified pointer location, which is a loop-strided access. The 'Access' |
| 384 | /// argument specifies what the verboten forms of access are (read or write). |
Chandler Carruth | 194f59c | 2015-07-22 23:15:57 +0000 | [diff] [blame] | 385 | static bool mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L, |
| 386 | const SCEV *BECount, unsigned StoreSize, |
| 387 | AliasAnalysis &AA, |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 388 | Instruction *IgnoredStore) { |
| 389 | // Get the location that may be stored across the loop. Since the access is |
| 390 | // strided positively through memory, we say that the modified location starts |
| 391 | // at the pointer and has infinite size. |
Chandler Carruth | ecbd168 | 2015-06-17 07:21:38 +0000 | [diff] [blame] | 392 | uint64_t AccessSize = MemoryLocation::UnknownSize; |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 393 | |
| 394 | // If the loop iterates a fixed number of times, we can refine the access size |
| 395 | // to be exactly the size of the memset, which is (BECount+1)*StoreSize |
| 396 | if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount)) |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 397 | AccessSize = (BECst->getValue()->getZExtValue() + 1) * StoreSize; |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 398 | |
| 399 | // TODO: For this to be really effective, we have to dive into the pointer |
| 400 | // operand in the store. Store to &A[i] of 100 will always return may alias |
| 401 | // with store of &A[100], we need to StoreLoc to be "A" with size of 100, |
| 402 | // which will then no-alias a store to &A[100]. |
Chandler Carruth | ac80dc7 | 2015-06-17 07:18:54 +0000 | [diff] [blame] | 403 | MemoryLocation StoreLoc(Ptr, AccessSize); |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 404 | |
| 405 | for (Loop::block_iterator BI = L->block_begin(), E = L->block_end(); BI != E; |
| 406 | ++BI) |
| 407 | for (BasicBlock::iterator I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I) |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 408 | if (&*I != IgnoredStore && (AA.getModRefInfo(I, StoreLoc) & Access)) |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 409 | return true; |
| 410 | |
| 411 | return false; |
| 412 | } |
| 413 | |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 414 | /// getMemSetPatternValue - If a strided store of the specified value is safe to |
| 415 | /// turn into a memset_pattern16, return a ConstantArray of 16 bytes that should |
| 416 | /// be passed in. Otherwise, return null. |
| 417 | /// |
| 418 | /// Note that we don't ever attempt to use memset_pattern8 or 4, because these |
| 419 | /// just replicate their input array and then pass on to memset_pattern16. |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 420 | static Constant *getMemSetPatternValue(Value *V, const DataLayout &DL) { |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 421 | // If the value isn't a constant, we can't promote it to being in a constant |
| 422 | // array. We could theoretically do a store to an alloca or something, but |
| 423 | // that doesn't seem worthwhile. |
| 424 | Constant *C = dyn_cast<Constant>(V); |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 425 | if (!C) |
| 426 | return nullptr; |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 427 | |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 428 | // Only handle simple values that are a power of two bytes in size. |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 429 | uint64_t Size = DL.getTypeSizeInBits(V->getType()); |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 430 | if (Size == 0 || (Size & 7) || (Size & (Size - 1))) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 431 | return nullptr; |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 432 | |
Chris Lattner | 72a35fb | 2011-02-19 19:56:44 +0000 | [diff] [blame] | 433 | // Don't care enough about darwin/ppc to implement this. |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 434 | if (DL.isBigEndian()) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 435 | return nullptr; |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 436 | |
| 437 | // Convert to size in bytes. |
| 438 | Size /= 8; |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 439 | |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 440 | // TODO: If CI is larger than 16-bytes, we can try slicing it in half to see |
Chris Lattner | 72a35fb | 2011-02-19 19:56:44 +0000 | [diff] [blame] | 441 | // if the top and bottom are the same (e.g. for vectors and large integers). |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 442 | if (Size > 16) |
| 443 | return nullptr; |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 444 | |
Chris Lattner | 72a35fb | 2011-02-19 19:56:44 +0000 | [diff] [blame] | 445 | // If the constant is exactly 16 bytes, just use it. |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 446 | if (Size == 16) |
| 447 | return C; |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 448 | |
Chris Lattner | 72a35fb | 2011-02-19 19:56:44 +0000 | [diff] [blame] | 449 | // Otherwise, we'll use an array of the constants. |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 450 | unsigned ArraySize = 16 / Size; |
Chris Lattner | 72a35fb | 2011-02-19 19:56:44 +0000 | [diff] [blame] | 451 | ArrayType *AT = ArrayType::get(V->getType(), ArraySize); |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 452 | return ConstantArray::get(AT, std::vector<Constant *>(ArraySize, C)); |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 453 | } |
| 454 | |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 455 | /// processLoopStridedStore - We see a strided store of some value. If we can |
| 456 | /// transform this into a memset or memset_pattern in the loop preheader, do so. |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 457 | bool LoopIdiomRecognize::processLoopStridedStore( |
| 458 | Value *DestPtr, unsigned StoreSize, unsigned StoreAlignment, |
| 459 | Value *StoredVal, Instruction *TheStore, const SCEVAddRecExpr *Ev, |
| 460 | const SCEV *BECount) { |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 461 | |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 462 | // If the stored value is a byte-wise value (like i32 -1), then it may be |
| 463 | // turned into a memset of i8 -1, assuming that all the consecutive bytes |
| 464 | // are stored. A store of i32 0x01020304 can never be turned into a memset, |
| 465 | // but it can be turned into memset_pattern if the target supports it. |
| 466 | Value *SplatValue = isBytewiseValue(StoredVal); |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 467 | Constant *PatternValue = nullptr; |
Mehdi Amini | 46a4355 | 2015-03-04 18:43:29 +0000 | [diff] [blame] | 468 | auto &DL = CurLoop->getHeader()->getModule()->getDataLayout(); |
Matt Arsenault | 009faed | 2013-09-11 05:09:42 +0000 | [diff] [blame] | 469 | unsigned DestAS = DestPtr->getType()->getPointerAddressSpace(); |
| 470 | |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 471 | // If we're allowed to form a memset, and the stored value would be acceptable |
| 472 | // for memset, use it. |
| 473 | if (SplatValue && TLI->has(LibFunc::memset) && |
| 474 | // Verify that the stored value is loop invariant. If not, we can't |
| 475 | // promote the memset. |
| 476 | CurLoop->isLoopInvariant(SplatValue)) { |
| 477 | // Keep and use SplatValue. |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 478 | PatternValue = nullptr; |
Mehdi Amini | 46a4355 | 2015-03-04 18:43:29 +0000 | [diff] [blame] | 479 | } else if (DestAS == 0 && TLI->has(LibFunc::memset_pattern16) && |
| 480 | (PatternValue = getMemSetPatternValue(StoredVal, DL))) { |
Matt Arsenault | 009faed | 2013-09-11 05:09:42 +0000 | [diff] [blame] | 481 | // Don't create memset_pattern16s with address spaces. |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 482 | // It looks like we can use PatternValue! |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 483 | SplatValue = nullptr; |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 484 | } else { |
| 485 | // Otherwise, this isn't an idiom we can transform. For example, we can't |
Eli Friedman | a93ab13 | 2011-09-13 00:44:16 +0000 | [diff] [blame] | 486 | // do anything with a 3-byte store. |
Chris Lattner | a351444 | 2011-01-01 20:12:04 +0000 | [diff] [blame] | 487 | return false; |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 488 | } |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 489 | |
Chris Lattner | c4ca7ab | 2011-05-22 17:39:56 +0000 | [diff] [blame] | 490 | // The trip count of the loop and the base pointer of the addrec SCEV is |
| 491 | // guaranteed to be loop invariant, which means that it should dominate the |
| 492 | // header. This allows us to insert code for it in the preheader. |
| 493 | BasicBlock *Preheader = CurLoop->getLoopPreheader(); |
| 494 | IRBuilder<> Builder(Preheader->getTerminator()); |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 495 | SCEVExpander Expander(*SE, DL, "loop-idiom"); |
Andrew Trick | 60ab3ef | 2011-06-28 05:04:16 +0000 | [diff] [blame] | 496 | |
Matt Arsenault | 009faed | 2013-09-11 05:09:42 +0000 | [diff] [blame] | 497 | Type *DestInt8PtrTy = Builder.getInt8PtrTy(DestAS); |
| 498 | |
Chris Lattner | 29e14ed | 2010-12-26 23:42:51 +0000 | [diff] [blame] | 499 | // Okay, we have a strided store "p[i]" of a splattable value. We can turn |
Benjamin Kramer | f77f224 | 2012-10-21 19:31:16 +0000 | [diff] [blame] | 500 | // this into a memset in the loop preheader now if we want. However, this |
| 501 | // would be unsafe to do if there is anything else in the loop that may read |
Chandler Carruth | 7ec5085 | 2012-11-01 08:07:29 +0000 | [diff] [blame] | 502 | // or write to the aliased location. Check for any overlap by generating the |
| 503 | // base pointer and checking the region. |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 504 | Value *BasePtr = Expander.expandCodeFor(Ev->getStart(), DestInt8PtrTy, |
| 505 | Preheader->getTerminator()); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 506 | |
Chandler Carruth | 194f59c | 2015-07-22 23:15:57 +0000 | [diff] [blame] | 507 | if (mayLoopAccessLocation(BasePtr, MRI_ModRef, CurLoop, BECount, StoreSize, |
| 508 | getAnalysis<AliasAnalysis>(), TheStore)) { |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 509 | Expander.clear(); |
| 510 | // If we generated new code for the base pointer, clean up. |
Benjamin Kramer | f094d77 | 2015-02-07 21:37:08 +0000 | [diff] [blame] | 511 | RecursivelyDeleteTriviallyDeadInstructions(BasePtr, TLI); |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 512 | return false; |
| 513 | } |
| 514 | |
Chris Lattner | c4ca7ab | 2011-05-22 17:39:56 +0000 | [diff] [blame] | 515 | // Okay, everything looks good, insert the memset. |
| 516 | |
Chris Lattner | 29e14ed | 2010-12-26 23:42:51 +0000 | [diff] [blame] | 517 | // The # stored bytes is (BECount+1)*Size. Expand the trip count out to |
| 518 | // pointer size if it isn't already. |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 519 | Type *IntPtr = Builder.getIntPtrTy(DL, DestAS); |
Chris Lattner | 0ba473c | 2011-01-04 00:06:55 +0000 | [diff] [blame] | 520 | BECount = SE->getTruncateOrZeroExtend(BECount, IntPtr); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 521 | |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 522 | const SCEV *NumBytesS = |
| 523 | SE->getAddExpr(BECount, SE->getConstant(IntPtr, 1), SCEV::FlagNUW); |
Matt Arsenault | 5df49bd | 2013-09-11 05:09:35 +0000 | [diff] [blame] | 524 | if (StoreSize != 1) { |
Chris Lattner | 29e14ed | 2010-12-26 23:42:51 +0000 | [diff] [blame] | 525 | NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtr, StoreSize), |
Andrew Trick | 8b55b73 | 2011-03-14 16:50:06 +0000 | [diff] [blame] | 526 | SCEV::FlagNUW); |
Matt Arsenault | 5df49bd | 2013-09-11 05:09:35 +0000 | [diff] [blame] | 527 | } |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 528 | |
| 529 | Value *NumBytes = |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 530 | Expander.expandCodeFor(NumBytesS, IntPtr, Preheader->getTerminator()); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 531 | |
Devang Patel | d00c628 | 2011-03-07 22:43:45 +0000 | [diff] [blame] | 532 | CallInst *NewCall; |
Matt Arsenault | 5df49bd | 2013-09-11 05:09:35 +0000 | [diff] [blame] | 533 | if (SplatValue) { |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 534 | NewCall = |
| 535 | Builder.CreateMemSet(BasePtr, SplatValue, NumBytes, StoreAlignment); |
Matt Arsenault | 5df49bd | 2013-09-11 05:09:35 +0000 | [diff] [blame] | 536 | } else { |
Matt Arsenault | 009faed | 2013-09-11 05:09:42 +0000 | [diff] [blame] | 537 | // Everything is emitted in default address space |
| 538 | Type *Int8PtrTy = DestInt8PtrTy; |
| 539 | |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 540 | Module *M = TheStore->getParent()->getParent()->getParent(); |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 541 | Value *MSP = |
| 542 | M->getOrInsertFunction("memset_pattern16", Builder.getVoidTy(), |
| 543 | Int8PtrTy, Int8PtrTy, IntPtr, (void *)nullptr); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 544 | |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 545 | // Otherwise we should form a memset_pattern16. PatternValue is known to be |
| 546 | // an constant array of 16-bytes. Plop the value into a mergable global. |
| 547 | GlobalVariable *GV = new GlobalVariable(*M, PatternValue->getType(), true, |
Benjamin Kramer | 838752d | 2015-03-03 00:17:09 +0000 | [diff] [blame] | 548 | GlobalValue::PrivateLinkage, |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 549 | PatternValue, ".memset_pattern"); |
| 550 | GV->setUnnamedAddr(true); // Ok to merge these. |
| 551 | GV->setAlignment(16); |
Matt Arsenault | 009faed | 2013-09-11 05:09:42 +0000 | [diff] [blame] | 552 | Value *PatternPtr = ConstantExpr::getBitCast(GV, Int8PtrTy); |
David Blaikie | ff6409d | 2015-05-18 22:13:54 +0000 | [diff] [blame] | 553 | NewCall = Builder.CreateCall(MSP, {BasePtr, PatternPtr, NumBytes}); |
Chris Lattner | 0f4a640 | 2011-02-19 19:31:39 +0000 | [diff] [blame] | 554 | } |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 555 | |
Chris Lattner | 29e14ed | 2010-12-26 23:42:51 +0000 | [diff] [blame] | 556 | DEBUG(dbgs() << " Formed memset: " << *NewCall << "\n" |
Chris Lattner | 8643810 | 2011-01-04 07:46:33 +0000 | [diff] [blame] | 557 | << " from store to: " << *Ev << " at: " << *TheStore << "\n"); |
Devang Patel | d00c628 | 2011-03-07 22:43:45 +0000 | [diff] [blame] | 558 | NewCall->setDebugLoc(TheStore->getDebugLoc()); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 559 | |
Chris Lattner | b9fe685 | 2010-12-27 00:03:23 +0000 | [diff] [blame] | 560 | // Okay, the memset has been formed. Zap the original store and anything that |
| 561 | // feeds into it. |
Benjamin Kramer | f094d77 | 2015-02-07 21:37:08 +0000 | [diff] [blame] | 562 | deleteDeadInstruction(TheStore, TLI); |
Chris Lattner | 12f91be | 2011-01-02 07:36:44 +0000 | [diff] [blame] | 563 | ++NumMemSet; |
Chris Lattner | 29e14ed | 2010-12-26 23:42:51 +0000 | [diff] [blame] | 564 | return true; |
| 565 | } |
| 566 | |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 567 | /// processLoopStoreOfLoopLoad - We see a strided store whose value is a |
| 568 | /// same-strided load. |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 569 | bool LoopIdiomRecognize::processLoopStoreOfLoopLoad( |
| 570 | StoreInst *SI, unsigned StoreSize, const SCEVAddRecExpr *StoreEv, |
| 571 | const SCEVAddRecExpr *LoadEv, const SCEV *BECount) { |
Chris Lattner | e6b261f | 2011-02-18 22:22:15 +0000 | [diff] [blame] | 572 | // If we're not allowed to form memcpy, we fail. |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 573 | if (!TLI->has(LibFunc::memcpy)) |
Chris Lattner | e6b261f | 2011-02-18 22:22:15 +0000 | [diff] [blame] | 574 | return false; |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 575 | |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 576 | LoadInst *LI = cast<LoadInst>(SI->getValueOperand()); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 577 | |
Chris Lattner | c4ca7ab | 2011-05-22 17:39:56 +0000 | [diff] [blame] | 578 | // The trip count of the loop and the base pointer of the addrec SCEV is |
| 579 | // guaranteed to be loop invariant, which means that it should dominate the |
| 580 | // header. This allows us to insert code for it in the preheader. |
| 581 | BasicBlock *Preheader = CurLoop->getLoopPreheader(); |
| 582 | IRBuilder<> Builder(Preheader->getTerminator()); |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 583 | const DataLayout &DL = Preheader->getModule()->getDataLayout(); |
| 584 | SCEVExpander Expander(*SE, DL, "loop-idiom"); |
Andrew Trick | 60ab3ef | 2011-06-28 05:04:16 +0000 | [diff] [blame] | 585 | |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 586 | // Okay, we have a strided store "p[i]" of a loaded value. We can turn |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 587 | // this into a memcpy in the loop preheader now if we want. However, this |
| 588 | // would be unsafe to do if there is anything else in the loop that may read |
| 589 | // or write the memory region we're storing to. This includes the load that |
| 590 | // feeds the stores. Check for an alias by generating the base address and |
| 591 | // checking everything. |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 592 | Value *StoreBasePtr = Expander.expandCodeFor( |
| 593 | StoreEv->getStart(), Builder.getInt8PtrTy(SI->getPointerAddressSpace()), |
| 594 | Preheader->getTerminator()); |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 595 | |
Chandler Carruth | 194f59c | 2015-07-22 23:15:57 +0000 | [diff] [blame] | 596 | if (mayLoopAccessLocation(StoreBasePtr, MRI_ModRef, CurLoop, BECount, |
| 597 | StoreSize, getAnalysis<AliasAnalysis>(), SI)) { |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 598 | Expander.clear(); |
| 599 | // If we generated new code for the base pointer, clean up. |
Benjamin Kramer | f094d77 | 2015-02-07 21:37:08 +0000 | [diff] [blame] | 600 | RecursivelyDeleteTriviallyDeadInstructions(StoreBasePtr, TLI); |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 601 | return false; |
| 602 | } |
| 603 | |
| 604 | // For a memcpy, we have to make sure that the input array is not being |
| 605 | // mutated by the loop. |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 606 | Value *LoadBasePtr = Expander.expandCodeFor( |
| 607 | LoadEv->getStart(), Builder.getInt8PtrTy(LI->getPointerAddressSpace()), |
| 608 | Preheader->getTerminator()); |
Chris Lattner | c4ca7ab | 2011-05-22 17:39:56 +0000 | [diff] [blame] | 609 | |
Chandler Carruth | 194f59c | 2015-07-22 23:15:57 +0000 | [diff] [blame] | 610 | if (mayLoopAccessLocation(LoadBasePtr, MRI_Mod, CurLoop, BECount, StoreSize, |
| 611 | getAnalysis<AliasAnalysis>(), SI)) { |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 612 | Expander.clear(); |
| 613 | // If we generated new code for the base pointer, clean up. |
Benjamin Kramer | f094d77 | 2015-02-07 21:37:08 +0000 | [diff] [blame] | 614 | RecursivelyDeleteTriviallyDeadInstructions(LoadBasePtr, TLI); |
| 615 | RecursivelyDeleteTriviallyDeadInstructions(StoreBasePtr, TLI); |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 616 | return false; |
| 617 | } |
| 618 | |
Chris Lattner | c4ca7ab | 2011-05-22 17:39:56 +0000 | [diff] [blame] | 619 | // Okay, everything is safe, we can transform this! |
Andrew Trick | 60ab3ef | 2011-06-28 05:04:16 +0000 | [diff] [blame] | 620 | |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 621 | // The # stored bytes is (BECount+1)*Size. Expand the trip count out to |
| 622 | // pointer size if it isn't already. |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 623 | Type *IntPtrTy = Builder.getIntPtrTy(DL, SI->getPointerAddressSpace()); |
Matt Arsenault | 009faed | 2013-09-11 05:09:42 +0000 | [diff] [blame] | 624 | BECount = SE->getTruncateOrZeroExtend(BECount, IntPtrTy); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 625 | |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 626 | const SCEV *NumBytesS = |
| 627 | SE->getAddExpr(BECount, SE->getConstant(IntPtrTy, 1), SCEV::FlagNUW); |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 628 | if (StoreSize != 1) |
Matt Arsenault | 009faed | 2013-09-11 05:09:42 +0000 | [diff] [blame] | 629 | NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtrTy, StoreSize), |
Andrew Trick | 8b55b73 | 2011-03-14 16:50:06 +0000 | [diff] [blame] | 630 | SCEV::FlagNUW); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 631 | |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 632 | Value *NumBytes = |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 633 | Expander.expandCodeFor(NumBytesS, IntPtrTy, Preheader->getTerminator()); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 634 | |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 635 | CallInst *NewCall = |
Chandler Carruth | bad690e | 2015-08-12 23:06:37 +0000 | [diff] [blame] | 636 | Builder.CreateMemCpy(StoreBasePtr, LoadBasePtr, NumBytes, |
| 637 | std::min(SI->getAlignment(), LI->getAlignment())); |
Devang Patel | 0daa07e | 2011-05-04 21:37:05 +0000 | [diff] [blame] | 638 | NewCall->setDebugLoc(SI->getDebugLoc()); |
Andrew Trick | 328b223 | 2011-03-14 16:48:10 +0000 | [diff] [blame] | 639 | |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 640 | DEBUG(dbgs() << " Formed memcpy: " << *NewCall << "\n" |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 641 | << " from load ptr=" << *LoadEv << " at: " << *LI << "\n" |
| 642 | << " from store ptr=" << *StoreEv << " at: " << *SI << "\n"); |
Andrew Trick | 60ab3ef | 2011-06-28 05:04:16 +0000 | [diff] [blame] | 643 | |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 644 | // Okay, the memset has been formed. Zap the original store and anything that |
| 645 | // feeds into it. |
Benjamin Kramer | f094d77 | 2015-02-07 21:37:08 +0000 | [diff] [blame] | 646 | deleteDeadInstruction(SI, TLI); |
Chandler Carruth | 099f5cb0 | 2012-11-02 08:33:25 +0000 | [diff] [blame] | 647 | ++NumMemCpy; |
Chris Lattner | 85b6d81 | 2011-01-02 03:37:56 +0000 | [diff] [blame] | 648 | return true; |
| 649 | } |
Chandler Carruth | d9c6070 | 2015-08-13 00:10:03 +0000 | [diff] [blame] | 650 | |
| 651 | bool LoopIdiomRecognize::runOnNoncountableLoop() { |
Chandler Carruth | 8219a50 | 2015-08-13 00:44:29 +0000 | [diff] [blame] | 652 | if (recognizePopcount()) |
Chandler Carruth | d9c6070 | 2015-08-13 00:10:03 +0000 | [diff] [blame] | 653 | return true; |
| 654 | |
| 655 | return false; |
| 656 | } |
Chandler Carruth | 8219a50 | 2015-08-13 00:44:29 +0000 | [diff] [blame] | 657 | |
| 658 | /// Check if the given conditional branch is based on the comparison between |
| 659 | /// a variable and zero, and if the variable is non-zero, the control yields to |
| 660 | /// the loop entry. If the branch matches the behavior, the variable involved |
| 661 | /// in the comparion is returned. This function will be called to see if the |
| 662 | /// precondition and postcondition of the loop are in desirable form. |
| 663 | static Value *matchCondition(BranchInst *BI, BasicBlock *LoopEntry) { |
| 664 | if (!BI || !BI->isConditional()) |
| 665 | return nullptr; |
| 666 | |
| 667 | ICmpInst *Cond = dyn_cast<ICmpInst>(BI->getCondition()); |
| 668 | if (!Cond) |
| 669 | return nullptr; |
| 670 | |
| 671 | ConstantInt *CmpZero = dyn_cast<ConstantInt>(Cond->getOperand(1)); |
| 672 | if (!CmpZero || !CmpZero->isZero()) |
| 673 | return nullptr; |
| 674 | |
| 675 | ICmpInst::Predicate Pred = Cond->getPredicate(); |
| 676 | if ((Pred == ICmpInst::ICMP_NE && BI->getSuccessor(0) == LoopEntry) || |
| 677 | (Pred == ICmpInst::ICMP_EQ && BI->getSuccessor(1) == LoopEntry)) |
| 678 | return Cond->getOperand(0); |
| 679 | |
| 680 | return nullptr; |
| 681 | } |
| 682 | |
| 683 | /// Return true iff the idiom is detected in the loop. |
| 684 | /// |
| 685 | /// Additionally: |
| 686 | /// 1) \p CntInst is set to the instruction counting the population bit. |
| 687 | /// 2) \p CntPhi is set to the corresponding phi node. |
| 688 | /// 3) \p Var is set to the value whose population bits are being counted. |
| 689 | /// |
| 690 | /// The core idiom we are trying to detect is: |
| 691 | /// \code |
| 692 | /// if (x0 != 0) |
| 693 | /// goto loop-exit // the precondition of the loop |
| 694 | /// cnt0 = init-val; |
| 695 | /// do { |
| 696 | /// x1 = phi (x0, x2); |
| 697 | /// cnt1 = phi(cnt0, cnt2); |
| 698 | /// |
| 699 | /// cnt2 = cnt1 + 1; |
| 700 | /// ... |
| 701 | /// x2 = x1 & (x1 - 1); |
| 702 | /// ... |
| 703 | /// } while(x != 0); |
| 704 | /// |
| 705 | /// loop-exit: |
| 706 | /// \endcode |
| 707 | static bool detectPopcountIdiom(Loop *CurLoop, BasicBlock *PreCondBB, |
| 708 | Instruction *&CntInst, PHINode *&CntPhi, |
| 709 | Value *&Var) { |
| 710 | // step 1: Check to see if the look-back branch match this pattern: |
| 711 | // "if (a!=0) goto loop-entry". |
| 712 | BasicBlock *LoopEntry; |
| 713 | Instruction *DefX2, *CountInst; |
| 714 | Value *VarX1, *VarX0; |
| 715 | PHINode *PhiX, *CountPhi; |
| 716 | |
| 717 | DefX2 = CountInst = nullptr; |
| 718 | VarX1 = VarX0 = nullptr; |
| 719 | PhiX = CountPhi = nullptr; |
| 720 | LoopEntry = *(CurLoop->block_begin()); |
| 721 | |
| 722 | // step 1: Check if the loop-back branch is in desirable form. |
| 723 | { |
| 724 | if (Value *T = matchCondition( |
| 725 | dyn_cast<BranchInst>(LoopEntry->getTerminator()), LoopEntry)) |
| 726 | DefX2 = dyn_cast<Instruction>(T); |
| 727 | else |
| 728 | return false; |
| 729 | } |
| 730 | |
| 731 | // step 2: detect instructions corresponding to "x2 = x1 & (x1 - 1)" |
| 732 | { |
| 733 | if (!DefX2 || DefX2->getOpcode() != Instruction::And) |
| 734 | return false; |
| 735 | |
| 736 | BinaryOperator *SubOneOp; |
| 737 | |
| 738 | if ((SubOneOp = dyn_cast<BinaryOperator>(DefX2->getOperand(0)))) |
| 739 | VarX1 = DefX2->getOperand(1); |
| 740 | else { |
| 741 | VarX1 = DefX2->getOperand(0); |
| 742 | SubOneOp = dyn_cast<BinaryOperator>(DefX2->getOperand(1)); |
| 743 | } |
| 744 | if (!SubOneOp) |
| 745 | return false; |
| 746 | |
| 747 | Instruction *SubInst = cast<Instruction>(SubOneOp); |
| 748 | ConstantInt *Dec = dyn_cast<ConstantInt>(SubInst->getOperand(1)); |
| 749 | if (!Dec || |
| 750 | !((SubInst->getOpcode() == Instruction::Sub && Dec->isOne()) || |
| 751 | (SubInst->getOpcode() == Instruction::Add && |
| 752 | Dec->isAllOnesValue()))) { |
| 753 | return false; |
| 754 | } |
| 755 | } |
| 756 | |
| 757 | // step 3: Check the recurrence of variable X |
| 758 | { |
| 759 | PhiX = dyn_cast<PHINode>(VarX1); |
| 760 | if (!PhiX || |
| 761 | (PhiX->getOperand(0) != DefX2 && PhiX->getOperand(1) != DefX2)) { |
| 762 | return false; |
| 763 | } |
| 764 | } |
| 765 | |
| 766 | // step 4: Find the instruction which count the population: cnt2 = cnt1 + 1 |
| 767 | { |
| 768 | CountInst = nullptr; |
| 769 | for (BasicBlock::iterator Iter = LoopEntry->getFirstNonPHI(), |
| 770 | IterE = LoopEntry->end(); |
| 771 | Iter != IterE; Iter++) { |
| 772 | Instruction *Inst = Iter; |
| 773 | if (Inst->getOpcode() != Instruction::Add) |
| 774 | continue; |
| 775 | |
| 776 | ConstantInt *Inc = dyn_cast<ConstantInt>(Inst->getOperand(1)); |
| 777 | if (!Inc || !Inc->isOne()) |
| 778 | continue; |
| 779 | |
| 780 | PHINode *Phi = dyn_cast<PHINode>(Inst->getOperand(0)); |
| 781 | if (!Phi || Phi->getParent() != LoopEntry) |
| 782 | continue; |
| 783 | |
| 784 | // Check if the result of the instruction is live of the loop. |
| 785 | bool LiveOutLoop = false; |
| 786 | for (User *U : Inst->users()) { |
| 787 | if ((cast<Instruction>(U))->getParent() != LoopEntry) { |
| 788 | LiveOutLoop = true; |
| 789 | break; |
| 790 | } |
| 791 | } |
| 792 | |
| 793 | if (LiveOutLoop) { |
| 794 | CountInst = Inst; |
| 795 | CountPhi = Phi; |
| 796 | break; |
| 797 | } |
| 798 | } |
| 799 | |
| 800 | if (!CountInst) |
| 801 | return false; |
| 802 | } |
| 803 | |
| 804 | // step 5: check if the precondition is in this form: |
| 805 | // "if (x != 0) goto loop-head ; else goto somewhere-we-don't-care;" |
| 806 | { |
| 807 | auto *PreCondBr = dyn_cast<BranchInst>(PreCondBB->getTerminator()); |
| 808 | Value *T = matchCondition(PreCondBr, CurLoop->getLoopPreheader()); |
| 809 | if (T != PhiX->getOperand(0) && T != PhiX->getOperand(1)) |
| 810 | return false; |
| 811 | |
| 812 | CntInst = CountInst; |
| 813 | CntPhi = CountPhi; |
| 814 | Var = T; |
| 815 | } |
| 816 | |
| 817 | return true; |
| 818 | } |
| 819 | |
| 820 | /// Recognizes a population count idiom in a non-countable loop. |
| 821 | /// |
| 822 | /// If detected, transforms the relevant code to issue the popcount intrinsic |
| 823 | /// function call, and returns true; otherwise, returns false. |
| 824 | bool LoopIdiomRecognize::recognizePopcount() { |
Chandler Carruth | 8219a50 | 2015-08-13 00:44:29 +0000 | [diff] [blame] | 825 | if (TTI->getPopcntSupport(32) != TargetTransformInfo::PSK_FastHardware) |
| 826 | return false; |
| 827 | |
| 828 | // Counting population are usually conducted by few arithmetic instructions. |
| 829 | // Such instructions can be easilly "absorbed" by vacant slots in a |
| 830 | // non-compact loop. Therefore, recognizing popcount idiom only makes sense |
| 831 | // in a compact loop. |
| 832 | |
| 833 | // Give up if the loop has multiple blocks or multiple backedges. |
| 834 | if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1) |
| 835 | return false; |
| 836 | |
| 837 | BasicBlock *LoopBody = *(CurLoop->block_begin()); |
| 838 | if (LoopBody->size() >= 20) { |
| 839 | // The loop is too big, bail out. |
| 840 | return false; |
| 841 | } |
| 842 | |
| 843 | // It should have a preheader containing nothing but an unconditional branch. |
| 844 | BasicBlock *PH = CurLoop->getLoopPreheader(); |
| 845 | if (!PH) |
| 846 | return false; |
| 847 | if (&PH->front() != PH->getTerminator()) |
| 848 | return false; |
| 849 | auto *EntryBI = dyn_cast<BranchInst>(PH->getTerminator()); |
| 850 | if (!EntryBI || EntryBI->isConditional()) |
| 851 | return false; |
| 852 | |
| 853 | // It should have a precondition block where the generated popcount instrinsic |
| 854 | // function can be inserted. |
| 855 | auto *PreCondBB = PH->getSinglePredecessor(); |
| 856 | if (!PreCondBB) |
| 857 | return false; |
| 858 | auto *PreCondBI = dyn_cast<BranchInst>(PreCondBB->getTerminator()); |
| 859 | if (!PreCondBI || PreCondBI->isUnconditional()) |
| 860 | return false; |
| 861 | |
| 862 | Instruction *CntInst; |
| 863 | PHINode *CntPhi; |
| 864 | Value *Val; |
| 865 | if (!detectPopcountIdiom(CurLoop, PreCondBB, CntInst, CntPhi, Val)) |
| 866 | return false; |
| 867 | |
| 868 | transformLoopToPopcount(PreCondBB, CntInst, CntPhi, Val); |
| 869 | return true; |
| 870 | } |
| 871 | |
| 872 | static CallInst *createPopcntIntrinsic(IRBuilder<> &IRBuilder, Value *Val, |
| 873 | DebugLoc DL) { |
| 874 | Value *Ops[] = {Val}; |
| 875 | Type *Tys[] = {Val->getType()}; |
| 876 | |
| 877 | Module *M = IRBuilder.GetInsertBlock()->getParent()->getParent(); |
| 878 | Value *Func = Intrinsic::getDeclaration(M, Intrinsic::ctpop, Tys); |
| 879 | CallInst *CI = IRBuilder.CreateCall(Func, Ops); |
| 880 | CI->setDebugLoc(DL); |
| 881 | |
| 882 | return CI; |
| 883 | } |
| 884 | |
| 885 | void LoopIdiomRecognize::transformLoopToPopcount(BasicBlock *PreCondBB, |
| 886 | Instruction *CntInst, |
| 887 | PHINode *CntPhi, Value *Var) { |
| 888 | BasicBlock *PreHead = CurLoop->getLoopPreheader(); |
| 889 | auto *PreCondBr = dyn_cast<BranchInst>(PreCondBB->getTerminator()); |
| 890 | const DebugLoc DL = CntInst->getDebugLoc(); |
| 891 | |
| 892 | // Assuming before transformation, the loop is following: |
| 893 | // if (x) // the precondition |
| 894 | // do { cnt++; x &= x - 1; } while(x); |
| 895 | |
| 896 | // Step 1: Insert the ctpop instruction at the end of the precondition block |
| 897 | IRBuilder<> Builder(PreCondBr); |
| 898 | Value *PopCnt, *PopCntZext, *NewCount, *TripCnt; |
| 899 | { |
| 900 | PopCnt = createPopcntIntrinsic(Builder, Var, DL); |
| 901 | NewCount = PopCntZext = |
| 902 | Builder.CreateZExtOrTrunc(PopCnt, cast<IntegerType>(CntPhi->getType())); |
| 903 | |
| 904 | if (NewCount != PopCnt) |
| 905 | (cast<Instruction>(NewCount))->setDebugLoc(DL); |
| 906 | |
| 907 | // TripCnt is exactly the number of iterations the loop has |
| 908 | TripCnt = NewCount; |
| 909 | |
| 910 | // If the population counter's initial value is not zero, insert Add Inst. |
| 911 | Value *CntInitVal = CntPhi->getIncomingValueForBlock(PreHead); |
| 912 | ConstantInt *InitConst = dyn_cast<ConstantInt>(CntInitVal); |
| 913 | if (!InitConst || !InitConst->isZero()) { |
| 914 | NewCount = Builder.CreateAdd(NewCount, CntInitVal); |
| 915 | (cast<Instruction>(NewCount))->setDebugLoc(DL); |
| 916 | } |
| 917 | } |
| 918 | |
| 919 | // Step 2: Replace the precondition from "if(x == 0) goto loop-exit" to |
| 920 | // "if(NewCount == 0) loop-exit". Withtout this change, the intrinsic |
| 921 | // function would be partial dead code, and downstream passes will drag |
| 922 | // it back from the precondition block to the preheader. |
| 923 | { |
| 924 | ICmpInst *PreCond = cast<ICmpInst>(PreCondBr->getCondition()); |
| 925 | |
| 926 | Value *Opnd0 = PopCntZext; |
| 927 | Value *Opnd1 = ConstantInt::get(PopCntZext->getType(), 0); |
| 928 | if (PreCond->getOperand(0) != Var) |
| 929 | std::swap(Opnd0, Opnd1); |
| 930 | |
| 931 | ICmpInst *NewPreCond = cast<ICmpInst>( |
| 932 | Builder.CreateICmp(PreCond->getPredicate(), Opnd0, Opnd1)); |
| 933 | PreCondBr->setCondition(NewPreCond); |
| 934 | |
| 935 | RecursivelyDeleteTriviallyDeadInstructions(PreCond, TLI); |
| 936 | } |
| 937 | |
| 938 | // Step 3: Note that the population count is exactly the trip count of the |
| 939 | // loop in question, which enble us to to convert the loop from noncountable |
| 940 | // loop into a countable one. The benefit is twofold: |
| 941 | // |
| 942 | // - If the loop only counts population, the entire loop become dead after |
| 943 | // the transformation. It is lots easier to prove a countable loop dead |
| 944 | // than to prove a noncountable one. (In some C dialects, a infite loop |
| 945 | // isn't dead even if it computes nothing useful. In general, DCE needs |
| 946 | // to prove a noncountable loop finite before safely delete it.) |
| 947 | // |
| 948 | // - If the loop also performs something else, it remains alive. |
| 949 | // Since it is transformed to countable form, it can be aggressively |
| 950 | // optimized by some optimizations which are in general not applicable |
| 951 | // to a noncountable loop. |
| 952 | // |
| 953 | // After this step, this loop (conceptually) would look like following: |
| 954 | // newcnt = __builtin_ctpop(x); |
| 955 | // t = newcnt; |
| 956 | // if (x) |
| 957 | // do { cnt++; x &= x-1; t--) } while (t > 0); |
| 958 | BasicBlock *Body = *(CurLoop->block_begin()); |
| 959 | { |
| 960 | auto *LbBr = dyn_cast<BranchInst>(Body->getTerminator()); |
| 961 | ICmpInst *LbCond = cast<ICmpInst>(LbBr->getCondition()); |
| 962 | Type *Ty = TripCnt->getType(); |
| 963 | |
| 964 | PHINode *TcPhi = PHINode::Create(Ty, 2, "tcphi", Body->begin()); |
| 965 | |
| 966 | Builder.SetInsertPoint(LbCond); |
| 967 | Value *Opnd1 = cast<Value>(TcPhi); |
| 968 | Value *Opnd2 = cast<Value>(ConstantInt::get(Ty, 1)); |
| 969 | Instruction *TcDec = cast<Instruction>( |
| 970 | Builder.CreateSub(Opnd1, Opnd2, "tcdec", false, true)); |
| 971 | |
| 972 | TcPhi->addIncoming(TripCnt, PreHead); |
| 973 | TcPhi->addIncoming(TcDec, Body); |
| 974 | |
| 975 | CmpInst::Predicate Pred = |
| 976 | (LbBr->getSuccessor(0) == Body) ? CmpInst::ICMP_UGT : CmpInst::ICMP_SLE; |
| 977 | LbCond->setPredicate(Pred); |
| 978 | LbCond->setOperand(0, TcDec); |
| 979 | LbCond->setOperand(1, cast<Value>(ConstantInt::get(Ty, 0))); |
| 980 | } |
| 981 | |
| 982 | // Step 4: All the references to the original population counter outside |
| 983 | // the loop are replaced with the NewCount -- the value returned from |
| 984 | // __builtin_ctpop(). |
| 985 | CntInst->replaceUsesOutsideBlock(NewCount, Body); |
| 986 | |
| 987 | // step 5: Forget the "non-computable" trip-count SCEV associated with the |
| 988 | // loop. The loop would otherwise not be deleted even if it becomes empty. |
| 989 | SE->forgetLoop(CurLoop); |
| 990 | } |