Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LoopIdiomRecognize.cpp - Loop idiom recognition --------------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This pass implements an idiom recognizer that transforms simple loops into a
10
// non-loop form.  In cases that this kicks in, it can be a significant
11
// performance win.
12
//
13
// If compiling for code size we avoid idiom recognition if the resulting
14
// code could be larger than the code for the original loop. One way this could
15
// happen is if the loop is not removable after idiom recognition due to the
16
// presence of non-idiom instructions. The initial implementation of the
17
// heuristics applies to idioms in multi-block loops.
18
//
19
//===----------------------------------------------------------------------===//
20
//
21
// TODO List:
22
//
23
// Future loop memory idioms to recognize:
24
//   memcmp, memmove, strlen, etc.
25
// Future floating point idioms to recognize in -ffast-math mode:
26
//   fpowi
27
// Future integer operation idioms to recognize:
28
//   ctpop
29
//
30
// Beware that isel's default lowering for ctpop is highly inefficient for
31
// i64 and larger types when i64 is legal and the value has few bits set.  It
32
// would be good to enhance isel to emit a loop for ctpop in this case.
33
//
34
// This could recognize common matrix multiplies and dot product idioms and
35
// replace them with calls to BLAS (if linked in??).
36
//
37
//===----------------------------------------------------------------------===//
38
39
#include "llvm/Transforms/Scalar/LoopIdiomRecognize.h"
40
#include "llvm/ADT/APInt.h"
41
#include "llvm/ADT/ArrayRef.h"
42
#include "llvm/ADT/DenseMap.h"
43
#include "llvm/ADT/MapVector.h"
44
#include "llvm/ADT/SetVector.h"
45
#include "llvm/ADT/SmallPtrSet.h"
46
#include "llvm/ADT/SmallVector.h"
47
#include "llvm/ADT/Statistic.h"
48
#include "llvm/ADT/StringRef.h"
49
#include "llvm/Analysis/AliasAnalysis.h"
50
#include "llvm/Analysis/LoopAccessAnalysis.h"
51
#include "llvm/Analysis/LoopInfo.h"
52
#include "llvm/Analysis/LoopPass.h"
53
#include "llvm/Analysis/MemoryLocation.h"
54
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
55
#include "llvm/Analysis/ScalarEvolution.h"
56
#include "llvm/Analysis/ScalarEvolutionExpander.h"
57
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
58
#include "llvm/Analysis/TargetLibraryInfo.h"
59
#include "llvm/Analysis/TargetTransformInfo.h"
60
#include "llvm/Analysis/ValueTracking.h"
61
#include "llvm/IR/Attributes.h"
62
#include "llvm/IR/BasicBlock.h"
63
#include "llvm/IR/Constant.h"
64
#include "llvm/IR/Constants.h"
65
#include "llvm/IR/DataLayout.h"
66
#include "llvm/IR/DebugLoc.h"
67
#include "llvm/IR/DerivedTypes.h"
68
#include "llvm/IR/Dominators.h"
69
#include "llvm/IR/GlobalValue.h"
70
#include "llvm/IR/GlobalVariable.h"
71
#include "llvm/IR/IRBuilder.h"
72
#include "llvm/IR/InstrTypes.h"
73
#include "llvm/IR/Instruction.h"
74
#include "llvm/IR/Instructions.h"
75
#include "llvm/IR/IntrinsicInst.h"
76
#include "llvm/IR/Intrinsics.h"
77
#include "llvm/IR/LLVMContext.h"
78
#include "llvm/IR/Module.h"
79
#include "llvm/IR/PassManager.h"
80
#include "llvm/IR/Type.h"
81
#include "llvm/IR/User.h"
82
#include "llvm/IR/Value.h"
83
#include "llvm/IR/ValueHandle.h"
84
#include "llvm/Pass.h"
85
#include "llvm/Support/Casting.h"
86
#include "llvm/Support/CommandLine.h"
87
#include "llvm/Support/Debug.h"
88
#include "llvm/Support/raw_ostream.h"
89
#include "llvm/Transforms/Scalar.h"
90
#include "llvm/Transforms/Utils/BuildLibCalls.h"
91
#include "llvm/Transforms/Utils/Local.h"
92
#include "llvm/Transforms/Utils/LoopUtils.h"
93
#include <algorithm>
94
#include <cassert>
95
#include <cstdint>
96
#include <utility>
97
#include <vector>
98
99
using namespace llvm;
100
101
2
#define DEBUG_TYPE "loop-idiom"
102
103
STATISTIC(NumMemSet, "Number of memset's formed from loop stores");
104
STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores");
105
106
static cl::opt<bool> UseLIRCodeSizeHeurs(
107
    "use-lir-code-size-heurs",
108
    cl::desc("Use loop idiom recognition code size heuristics when compiling"
109
             "with -Os/-Oz"),
110
    cl::init(true), cl::Hidden);
111
112
namespace {
113
114
class LoopIdiomRecognize {
115
  Loop *CurLoop = nullptr;
116
  AliasAnalysis *AA;
117
  DominatorTree *DT;
118
  LoopInfo *LI;
119
  ScalarEvolution *SE;
120
  TargetLibraryInfo *TLI;
121
  const TargetTransformInfo *TTI;
122
  const DataLayout *DL;
123
  OptimizationRemarkEmitter &ORE;
124
  bool ApplyCodeSizeHeuristics;
125
126
public:
127
  explicit LoopIdiomRecognize(AliasAnalysis *AA, DominatorTree *DT,
128
                              LoopInfo *LI, ScalarEvolution *SE,
129
                              TargetLibraryInfo *TLI,
130
                              const TargetTransformInfo *TTI,
131
                              const DataLayout *DL,
132
                              OptimizationRemarkEmitter &ORE)
133
219k
      : AA(AA), DT(DT), LI(LI), SE(SE), TLI(TLI), TTI(TTI), DL(DL), ORE(ORE) {}
134
135
  bool runOnLoop(Loop *L);
136
137
private:
138
  using StoreList = SmallVector<StoreInst *, 8>;
139
  using StoreListMap = MapVector<Value *, StoreList>;
140
141
  StoreListMap StoreRefsForMemset;
142
  StoreListMap StoreRefsForMemsetPattern;
143
  StoreList StoreRefsForMemcpy;
144
  bool HasMemset;
145
  bool HasMemsetPattern;
146
  bool HasMemcpy;
147
148
  /// Return code for isLegalStore()
149
  enum LegalStoreKind {
150
    None = 0,
151
    Memset,
152
    MemsetPattern,
153
    Memcpy,
154
    UnorderedAtomicMemcpy,
155
    DontUse // Dummy retval never to be used. Allows catching errors in retval
156
            // handling.
157
  };
158
159
  /// \name Countable Loop Idiom Handling
160
  /// @{
161
162
  bool runOnCountableLoop();
163
  bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
164
                      SmallVectorImpl<BasicBlock *> &ExitBlocks);
165
166
  void collectStores(BasicBlock *BB);
167
  LegalStoreKind isLegalStore(StoreInst *SI);
168
  enum class ForMemset { No, Yes };
169
  bool processLoopStores(SmallVectorImpl<StoreInst *> &SL, const SCEV *BECount,
170
                         ForMemset For);
171
  bool processLoopMemSet(MemSetInst *MSI, const SCEV *BECount);
172
173
  bool processLoopStridedStore(Value *DestPtr, unsigned StoreSize,
174
                               unsigned StoreAlignment, Value *StoredVal,
175
                               Instruction *TheStore,
176
                               SmallPtrSetImpl<Instruction *> &Stores,
177
                               const SCEVAddRecExpr *Ev, const SCEV *BECount,
178
                               bool NegStride, bool IsLoopMemset = false);
179
  bool processLoopStoreOfLoopLoad(StoreInst *SI, const SCEV *BECount);
180
  bool avoidLIRForMultiBlockLoop(bool IsMemset = false,
181
                                 bool IsLoopMemset = false);
182
183
  /// @}
184
  /// \name Noncountable Loop Idiom Handling
185
  /// @{
186
187
  bool runOnNoncountableLoop();
188
189
  bool recognizePopcount();
190
  void transformLoopToPopcount(BasicBlock *PreCondBB, Instruction *CntInst,
191
                               PHINode *CntPhi, Value *Var);
192
  bool recognizeAndInsertFFS();  /// Find First Set: ctlz or cttz
193
  void transformLoopToCountable(Intrinsic::ID IntrinID, BasicBlock *PreCondBB,
194
                                Instruction *CntInst, PHINode *CntPhi,
195
                                Value *Var, Instruction *DefX,
196
                                const DebugLoc &DL, bool ZeroCheck,
197
                                bool IsCntPhiUsedOutsideLoop);
198
199
  /// @}
200
};
201
202
class LoopIdiomRecognizeLegacyPass : public LoopPass {
203
public:
204
  static char ID;
205
206
12.9k
  explicit LoopIdiomRecognizeLegacyPass() : LoopPass(ID) {
207
12.9k
    initializeLoopIdiomRecognizeLegacyPassPass(
208
12.9k
        *PassRegistry::getPassRegistry());
209
12.9k
  }
210
211
219k
  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
212
219k
    if (skipLoop(L))
213
16
      return false;
214
219k
215
219k
    AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
216
219k
    DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
217
219k
    LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
218
219k
    ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
219
219k
    TargetLibraryInfo *TLI =
220
219k
        &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
221
219k
    const TargetTransformInfo *TTI =
222
219k
        &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
223
219k
            *L->getHeader()->getParent());
224
219k
    const DataLayout *DL = &L->getHeader()->getModule()->getDataLayout();
225
219k
226
219k
    // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
227
219k
    // pass.  Function analyses need to be preserved across loop transformations
228
219k
    // but ORE cannot be preserved (see comment before the pass definition).
229
219k
    OptimizationRemarkEmitter ORE(L->getHeader()->getParent());
230
219k
231
219k
    LoopIdiomRecognize LIR(AA, DT, LI, SE, TLI, TTI, DL, ORE);
232
219k
    return LIR.runOnLoop(L);
233
219k
  }
234
235
  /// This transformation requires natural loop information & requires that
236
  /// loop preheaders be inserted into the CFG.
237
12.9k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
238
12.9k
    AU.addRequired<TargetLibraryInfoWrapperPass>();
239
12.9k
    AU.addRequired<TargetTransformInfoWrapperPass>();
240
12.9k
    getLoopAnalysisUsage(AU);
241
12.9k
  }
242
};
243
244
} // end anonymous namespace
245
246
char LoopIdiomRecognizeLegacyPass::ID = 0;
247
248
PreservedAnalyses LoopIdiomRecognizePass::run(Loop &L, LoopAnalysisManager &AM,
249
                                              LoopStandardAnalysisResults &AR,
250
73
                                              LPMUpdater &) {
251
73
  const auto *DL = &L.getHeader()->getModule()->getDataLayout();
252
73
253
73
  const auto &FAM =
254
73
      AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
255
73
  Function *F = L.getHeader()->getParent();
256
73
257
73
  auto *ORE = FAM.getCachedResult<OptimizationRemarkEmitterAnalysis>(*F);
258
73
  // FIXME: This should probably be optional rather than required.
259
73
  if (!ORE)
260
0
    report_fatal_error(
261
0
        "LoopIdiomRecognizePass: OptimizationRemarkEmitterAnalysis not cached "
262
0
        "at a higher level");
263
73
264
73
  LoopIdiomRecognize LIR(&AR.AA, &AR.DT, &AR.LI, &AR.SE, &AR.TLI, &AR.TTI, DL,
265
73
                         *ORE);
266
73
  if (!LIR.runOnLoop(&L))
267
72
    return PreservedAnalyses::all();
268
1
269
1
  return getLoopPassPreservedAnalyses();
270
1
}
271
272
48.6k
INITIALIZE_PASS_BEGIN(LoopIdiomRecognizeLegacyPass, "loop-idiom",
273
48.6k
                      "Recognize loop idioms", false, false)
274
48.6k
INITIALIZE_PASS_DEPENDENCY(LoopPass)
275
48.6k
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
276
48.6k
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
277
48.6k
INITIALIZE_PASS_END(LoopIdiomRecognizeLegacyPass, "loop-idiom",
278
                    "Recognize loop idioms", false, false)
279
280
12.9k
Pass *llvm::createLoopIdiomPass() { return new LoopIdiomRecognizeLegacyPass(); }
281
282
12.2k
static void deleteDeadInstruction(Instruction *I) {
283
12.2k
  I->replaceAllUsesWith(UndefValue::get(I->getType()));
284
12.2k
  I->eraseFromParent();
285
12.2k
}
286
287
//===----------------------------------------------------------------------===//
288
//
289
//          Implementation of LoopIdiomRecognize
290
//
291
//===----------------------------------------------------------------------===//
292
293
219k
bool LoopIdiomRecognize::runOnLoop(Loop *L) {
294
219k
  CurLoop = L;
295
219k
  // If the loop could not be converted to canonical form, it must have an
296
219k
  // indirectbr in it, just give up.
297
219k
  if (!L->getLoopPreheader())
298
1
    return false;
299
219k
300
219k
  // Disable loop idiom recognition if the function's name is a common idiom.
301
219k
  StringRef Name = L->getHeader()->getParent()->getName();
302
219k
  if (Name == "memset" || 
Name == "memcpy"219k
)
303
1
    return false;
304
219k
305
219k
  // Determine if code size heuristics need to be applied.
306
219k
  ApplyCodeSizeHeuristics =
307
219k
      L->getHeader()->getParent()->hasOptSize() && 
UseLIRCodeSizeHeurs67
;
308
219k
309
219k
  HasMemset = TLI->has(LibFunc_memset);
310
219k
  HasMemsetPattern = TLI->has(LibFunc_memset_pattern16);
311
219k
  HasMemcpy = TLI->has(LibFunc_memcpy);
312
219k
313
219k
  if (HasMemset || 
HasMemsetPattern21.4k
||
HasMemcpy21.4k
)
314
198k
    if (SE->hasLoopInvariantBackedgeTakenCount(L))
315
78.4k
      return runOnCountableLoop();
316
141k
317
141k
  return runOnNoncountableLoop();
318
141k
}
319
320
78.4k
bool LoopIdiomRecognize::runOnCountableLoop() {
321
78.4k
  const SCEV *BECount = SE->getBackedgeTakenCount(CurLoop);
322
78.4k
  assert(!isa<SCEVCouldNotCompute>(BECount) &&
323
78.4k
         "runOnCountableLoop() called on a loop without a predictable"
324
78.4k
         "backedge-taken count");
325
78.4k
326
78.4k
  // If this loop executes exactly one time, then it should be peeled, not
327
78.4k
  // optimized by this pass.
328
78.4k
  if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount))
329
31.0k
    if (BECst->getAPInt() == 0)
330
417
      return false;
331
78.0k
332
78.0k
  SmallVector<BasicBlock *, 8> ExitBlocks;
333
78.0k
  CurLoop->getUniqueExitBlocks(ExitBlocks);
334
78.0k
335
78.0k
  LLVM_DEBUG(dbgs() << DEBUG_TYPE " Scanning: F["
336
78.0k
                    << CurLoop->getHeader()->getParent()->getName()
337
78.0k
                    << "] Countable Loop %" << CurLoop->getHeader()->getName()
338
78.0k
                    << "\n");
339
78.0k
340
78.0k
  bool MadeChange = false;
341
78.0k
342
78.0k
  // The following transforms hoist stores/memsets into the loop pre-header.
343
78.0k
  // Give up if the loop has instructions may throw.
344
78.0k
  SimpleLoopSafetyInfo SafetyInfo;
345
78.0k
  SafetyInfo.computeLoopSafetyInfo(CurLoop);
346
78.0k
  if (SafetyInfo.anyBlockMayThrow())
347
16.9k
    return MadeChange;
348
61.0k
349
61.0k
  // Scan all the blocks in the loop that are not in subloops.
350
112k
  
for (auto *BB : CurLoop->getBlocks())61.0k
{
351
112k
    // Ignore blocks in subloops.
352
112k
    if (LI->getLoopFor(BB) != CurLoop)
353
17.9k
      continue;
354
94.6k
355
94.6k
    MadeChange |= runOnLoopBlock(BB, BECount, ExitBlocks);
356
94.6k
  }
357
61.0k
  return MadeChange;
358
61.0k
}
359
360
124k
static APInt getStoreStride(const SCEVAddRecExpr *StoreEv) {
361
124k
  const SCEVConstant *ConstStride = cast<SCEVConstant>(StoreEv->getOperand(1));
362
124k
  return ConstStride->getAPInt();
363
124k
}
364
365
/// getMemSetPatternValue - If a strided store of the specified value is safe to
366
/// turn into a memset_pattern16, return a ConstantArray of 16 bytes that should
367
/// be passed in.  Otherwise, return null.
368
///
369
/// Note that we don't ever attempt to use memset_pattern8 or 4, because these
370
/// just replicate their input array and then pass on to memset_pattern16.
371
55.1k
static Constant *getMemSetPatternValue(Value *V, const DataLayout *DL) {
372
55.1k
  // FIXME: This could check for UndefValue because it can be merged into any
373
55.1k
  // other valid pattern.
374
55.1k
375
55.1k
  // If the value isn't a constant, we can't promote it to being in a constant
376
55.1k
  // array.  We could theoretically do a store to an alloca or something, but
377
55.1k
  // that doesn't seem worthwhile.
378
55.1k
  Constant *C = dyn_cast<Constant>(V);
379
55.1k
  if (!C)
380
40.6k
    return nullptr;
381
14.5k
382
14.5k
  // Only handle simple values that are a power of two bytes in size.
383
14.5k
  uint64_t Size = DL->getTypeSizeInBits(V->getType());
384
14.5k
  if (Size == 0 || (Size & 7) || (Size & (Size - 1)))
385
1
    return nullptr;
386
14.5k
387
14.5k
  // Don't care enough about darwin/ppc to implement this.
388
14.5k
  if (DL->isBigEndian())
389
0
    return nullptr;
390
14.5k
391
14.5k
  // Convert to size in bytes.
392
14.5k
  Size /= 8;
393
14.5k
394
14.5k
  // TODO: If CI is larger than 16-bytes, we can try slicing it in half to see
395
14.5k
  // if the top and bottom are the same (e.g. for vectors and large integers).
396
14.5k
  if (Size > 16)
397
0
    return nullptr;
398
14.5k
399
14.5k
  // If the constant is exactly 16 bytes, just use it.
400
14.5k
  if (Size == 16)
401
0
    return C;
402
14.5k
403
14.5k
  // Otherwise, we'll use an array of the constants.
404
14.5k
  unsigned ArraySize = 16 / Size;
405
14.5k
  ArrayType *AT = ArrayType::get(V->getType(), ArraySize);
406
14.5k
  return ConstantArray::get(AT, std::vector<Constant *>(ArraySize, C));
407
14.5k
}
408
409
LoopIdiomRecognize::LegalStoreKind
410
87.1k
LoopIdiomRecognize::isLegalStore(StoreInst *SI) {
411
87.1k
  // Don't touch volatile stores.
412
87.1k
  if (SI->isVolatile())
413
0
    return LegalStoreKind::None;
414
87.1k
  // We only want simple or unordered-atomic stores.
415
87.1k
  if (!SI->isUnordered())
416
1
    return LegalStoreKind::None;
417
87.1k
418
87.1k
  // Don't convert stores of non-integral pointer types to memsets (which stores
419
87.1k
  // integers).
420
87.1k
  if (DL->isNonIntegralPointerType(SI->getValueOperand()->getType()))
421
1
    return LegalStoreKind::None;
422
87.1k
423
87.1k
  // Avoid merging nontemporal stores.
424
87.1k
  if (SI->getMetadata(LLVMContext::MD_nontemporal))
425
4
    return LegalStoreKind::None;
426
87.0k
427
87.0k
  Value *StoredVal = SI->getValueOperand();
428
87.0k
  Value *StorePtr = SI->getPointerOperand();
429
87.0k
430
87.0k
  // Reject stores that are so large that they overflow an unsigned.
431
87.0k
  uint64_t SizeInBits = DL->getTypeSizeInBits(StoredVal->getType());
432
87.0k
  if ((SizeInBits & 7) || 
(SizeInBits >> 32) != 087.0k
)
433
2
    return LegalStoreKind::None;
434
87.0k
435
87.0k
  // See if the pointer expression is an AddRec like {base,+,1} on the current
436
87.0k
  // loop, which indicates a strided store.  If we have something else, it's a
437
87.0k
  // random store we can't handle.
438
87.0k
  const SCEVAddRecExpr *StoreEv =
439
87.0k
      dyn_cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
440
87.0k
  if (!StoreEv || 
StoreEv->getLoop() != CurLoop77.4k
||
!StoreEv->isAffine()77.2k
)
441
9.80k
    return LegalStoreKind::None;
442
77.2k
443
77.2k
  // Check to see if we have a constant stride.
444
77.2k
  if (!isa<SCEVConstant>(StoreEv->getOperand(1)))
445
11.6k
    return LegalStoreKind::None;
446
65.6k
447
65.6k
  // See if the store can be turned into a memset.
448
65.6k
449
65.6k
  // If the stored value is a byte-wise value (like i32 -1), then it may be
450
65.6k
  // turned into a memset of i8 -1, assuming that all the consecutive bytes
451
65.6k
  // are stored.  A store of i32 0x01020304 can never be turned into a memset,
452
65.6k
  // but it can be turned into memset_pattern if the target supports it.
453
65.6k
  Value *SplatValue = isBytewiseValue(StoredVal, *DL);
454
65.6k
  Constant *PatternValue = nullptr;
455
65.6k
456
65.6k
  // Note: memset and memset_pattern on unordered-atomic is yet not supported
457
65.6k
  bool UnorderedAtomic = SI->isUnordered() && !SI->isSimple();
458
65.6k
459
65.6k
  // If we're allowed to form a memset, and the stored value would be
460
65.6k
  // acceptable for memset, use it.
461
65.6k
  if (!UnorderedAtomic && 
HasMemset65.6k
&&
SplatValue65.6k
&&
462
65.6k
      // Verify that the stored value is loop invariant.  If not, we can't
463
65.6k
      // promote the memset.
464
65.6k
      
CurLoop->isLoopInvariant(SplatValue)24.4k
) {
465
18.2k
    // It looks like we can use SplatValue.
466
18.2k
    return LegalStoreKind::Memset;
467
47.4k
  } else if (!UnorderedAtomic && 
HasMemsetPattern47.3k
&&
468
47.4k
             // Don't create memset_pattern16s with address spaces.
469
47.4k
             
StorePtr->getType()->getPointerAddressSpace() == 047.3k
&&
470
47.4k
             
(PatternValue = getMemSetPatternValue(StoredVal, DL))47.3k
) {
471
6.65k
    // It looks like we can use PatternValue!
472
6.65k
    return LegalStoreKind::MemsetPattern;
473
6.65k
  }
474
40.7k
475
40.7k
  // Otherwise, see if the store can be turned into a memcpy.
476
40.7k
  if (HasMemcpy) {
477
40.7k
    // Check to see if the stride matches the size of the store.  If so, then we
478
40.7k
    // know that every byte is touched in the loop.
479
40.7k
    APInt Stride = getStoreStride(StoreEv);
480
40.7k
    unsigned StoreSize = DL->getTypeStoreSize(SI->getValueOperand()->getType());
481
40.7k
    if (StoreSize != Stride && 
StoreSize != -Stride16.8k
)
482
14.9k
      return LegalStoreKind::None;
483
25.8k
484
25.8k
    // The store must be feeding a non-volatile load.
485
25.8k
    LoadInst *LI = dyn_cast<LoadInst>(SI->getValueOperand());
486
25.8k
487
25.8k
    // Only allow non-volatile loads
488
25.8k
    if (!LI || 
LI->isVolatile()8.79k
)
489
17.0k
      return LegalStoreKind::None;
490
8.79k
    // Only allow simple or unordered-atomic loads
491
8.79k
    if (!LI->isUnordered())
492
1
      return LegalStoreKind::None;
493
8.79k
494
8.79k
    // See if the pointer expression is an AddRec like {base,+,1} on the current
495
8.79k
    // loop, which indicates a strided load.  If we have something else, it's a
496
8.79k
    // random load we can't handle.
497
8.79k
    const SCEVAddRecExpr *LoadEv =
498
8.79k
        dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LI->getPointerOperand()));
499
8.79k
    if (!LoadEv || 
LoadEv->getLoop() != CurLoop7.98k
||
!LoadEv->isAffine()7.96k
)
500
832
      return LegalStoreKind::None;
501
7.96k
502
7.96k
    // The store and load must share the same stride.
503
7.96k
    if (StoreEv->getOperand(1) != LoadEv->getOperand(1))
504
170
      return LegalStoreKind::None;
505
7.79k
506
7.79k
    // Success.  This store can be converted into a memcpy.
507
7.79k
    UnorderedAtomic = UnorderedAtomic || 
LI->isAtomic()7.78k
;
508
7.79k
    return UnorderedAtomic ? 
LegalStoreKind::UnorderedAtomicMemcpy15
509
7.79k
                           : 
LegalStoreKind::Memcpy7.77k
;
510
7.79k
  }
511
0
  // This store can't be transformed into a memset/memcpy.
512
0
  return LegalStoreKind::None;
513
0
}
514
515
75.1k
void LoopIdiomRecognize::collectStores(BasicBlock *BB) {
516
75.1k
  StoreRefsForMemset.clear();
517
75.1k
  StoreRefsForMemsetPattern.clear();
518
75.1k
  StoreRefsForMemcpy.clear();
519
814k
  for (Instruction &I : *BB) {
520
814k
    StoreInst *SI = dyn_cast<StoreInst>(&I);
521
814k
    if (!SI)
522
727k
      continue;
523
87.1k
524
87.1k
    // Make sure this is a strided store with a constant stride.
525
87.1k
    switch (isLegalStore(SI)) {
526
87.1k
    case LegalStoreKind::None:
527
54.4k
      // Nothing to do
528
54.4k
      break;
529
87.1k
    case LegalStoreKind::Memset: {
530
18.2k
      // Find the base pointer.
531
18.2k
      Value *Ptr = GetUnderlyingObject(SI->getPointerOperand(), *DL);
532
18.2k
      StoreRefsForMemset[Ptr].push_back(SI);
533
18.2k
    } break;
534
87.1k
    case LegalStoreKind::MemsetPattern: {
535
6.65k
      // Find the base pointer.
536
6.65k
      Value *Ptr = GetUnderlyingObject(SI->getPointerOperand(), *DL);
537
6.65k
      StoreRefsForMemsetPattern[Ptr].push_back(SI);
538
6.65k
    } break;
539
87.1k
    case LegalStoreKind::Memcpy:
540
7.79k
    case LegalStoreKind::UnorderedAtomicMemcpy:
541
7.79k
      StoreRefsForMemcpy.push_back(SI);
542
7.79k
      break;
543
7.79k
    default:
544
0
      assert(false && "unhandled return value");
545
0
      break;
546
87.1k
    }
547
87.1k
  }
548
75.1k
}
549
550
/// runOnLoopBlock - Process the specified block, which lives in a counted loop
551
/// with the specified backedge count.  This block is known to be in the current
552
/// loop and not in any subloops.
553
bool LoopIdiomRecognize::runOnLoopBlock(
554
    BasicBlock *BB, const SCEV *BECount,
555
94.6k
    SmallVectorImpl<BasicBlock *> &ExitBlocks) {
556
94.6k
  // We can only promote stores in this block if they are unconditionally
557
94.6k
  // executed in the loop.  For a block to be unconditionally executed, it has
558
94.6k
  // to dominate all the exit blocks of the loop.  Verify this now.
559
169k
  for (unsigned i = 0, e = ExitBlocks.size(); i != e; 
++i75.1k
)
560
94.7k
    if (!DT->dominates(BB, ExitBlocks[i]))
561
19.5k
      return false;
562
94.6k
563
94.6k
  bool MadeChange = false;
564
75.1k
  // Look for store instructions, which may be optimized to memset/memcpy.
565
75.1k
  collectStores(BB);
566
75.1k
567
75.1k
  // Look for a single store or sets of stores with a common base, which can be
568
75.1k
  // optimized into a memset (memset_pattern).  The latter most commonly happens
569
75.1k
  // with structs and handunrolled loops.
570
75.1k
  for (auto &SL : StoreRefsForMemset)
571
7.74k
    MadeChange |= processLoopStores(SL.second, BECount, ForMemset::Yes);
572
75.1k
573
75.1k
  for (auto &SL : StoreRefsForMemsetPattern)
574
6.38k
    MadeChange |= processLoopStores(SL.second, BECount, ForMemset::No);
575
75.1k
576
75.1k
  // Optimize the store into a memcpy, if it feeds an similarly strided load.
577
75.1k
  for (auto &SI : StoreRefsForMemcpy)
578
7.79k
    MadeChange |= processLoopStoreOfLoopLoad(SI, BECount);
579
75.1k
580
877k
  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
581
802k
    Instruction *Inst = &*I++;
582
802k
    // Look for memset instructions, which may be optimized to a larger memset.
583
802k
    if (MemSetInst *MSI = dyn_cast<MemSetInst>(Inst)) {
584
1.04k
      WeakTrackingVH InstPtr(&*I);
585
1.04k
      if (!processLoopMemSet(MSI, BECount))
586
841
        continue;
587
206
      MadeChange = true;
588
206
589
206
      // If processing the memset invalidated our iterator, start over from the
590
206
      // top of the block.
591
206
      if (!InstPtr)
592
0
        I = BB->begin();
593
206
      continue;
594
206
    }
595
802k
  }
596
75.1k
597
75.1k
  return MadeChange;
598
94.6k
}
599
600
/// See if this store(s) can be promoted to a memset.
601
bool LoopIdiomRecognize::processLoopStores(SmallVectorImpl<StoreInst *> &SL,
602
14.1k
                                           const SCEV *BECount, ForMemset For) {
603
14.1k
  // Try to find consecutive stores that can be transformed into memsets.
604
14.1k
  SetVector<StoreInst *> Heads, Tails;
605
14.1k
  SmallDenseMap<StoreInst *, StoreInst *> ConsecutiveChain;
606
14.1k
607
14.1k
  // Do a quadratic search on all of the given stores and find
608
14.1k
  // all of the pairs of stores that follow each other.
609
14.1k
  SmallVector<unsigned, 16> IndexQueue;
610
38.9k
  for (unsigned i = 0, e = SL.size(); i < e; 
++i24.8k
) {
611
24.8k
    assert(SL[i]->isSimple() && "Expected only non-volatile stores.");
612
24.8k
613
24.8k
    Value *FirstStoredVal = SL[i]->getValueOperand();
614
24.8k
    Value *FirstStorePtr = SL[i]->getPointerOperand();
615
24.8k
    const SCEVAddRecExpr *FirstStoreEv =
616
24.8k
        cast<SCEVAddRecExpr>(SE->getSCEV(FirstStorePtr));
617
24.8k
    APInt FirstStride = getStoreStride(FirstStoreEv);
618
24.8k
    unsigned FirstStoreSize = DL->getTypeStoreSize(SL[i]->getValueOperand()->getType());
619
24.8k
620
24.8k
    // See if we can optimize just this store in isolation.
621
24.8k
    if (FirstStride == FirstStoreSize || 
-FirstStride == FirstStoreSize12.8k
) {
622
12.1k
      Heads.insert(SL[i]);
623
12.1k
      continue;
624
12.1k
    }
625
12.7k
626
12.7k
    Value *FirstSplatValue = nullptr;
627
12.7k
    Constant *FirstPatternValue = nullptr;
628
12.7k
629
12.7k
    if (For == ForMemset::Yes)
630
12.1k
      FirstSplatValue = isBytewiseValue(FirstStoredVal, *DL);
631
613
    else
632
613
      FirstPatternValue = getMemSetPatternValue(FirstStoredVal, DL);
633
12.7k
634
12.7k
    assert((FirstSplatValue || FirstPatternValue) &&
635
12.7k
           "Expected either splat value or pattern value.");
636
12.7k
637
12.7k
    IndexQueue.clear();
638
12.7k
    // If a store has multiple consecutive store candidates, search Stores
639
12.7k
    // array according to the sequence: from i+1 to e, then from i-1 to 0.
640
12.7k
    // This is because usually pairing with immediate succeeding or preceding
641
12.7k
    // candidate create the best chance to find memset opportunity.
642
12.7k
    unsigned j = 0;
643
58.1k
    for (j = i + 1; j < e; 
++j45.4k
)
644
45.4k
      IndexQueue.push_back(j);
645
57.9k
    for (j = i; j > 0; 
--j45.2k
)
646
45.2k
      IndexQueue.push_back(j - 1);
647
12.7k
648
37.2k
    for (auto &k : IndexQueue) {
649
37.2k
      assert(SL[k]->isSimple() && "Expected only non-volatile stores.");
650
37.2k
      Value *SecondStorePtr = SL[k]->getPointerOperand();
651
37.2k
      const SCEVAddRecExpr *SecondStoreEv =
652
37.2k
          cast<SCEVAddRecExpr>(SE->getSCEV(SecondStorePtr));
653
37.2k
      APInt SecondStride = getStoreStride(SecondStoreEv);
654
37.2k
655
37.2k
      if (FirstStride != SecondStride)
656
14
        continue;
657
37.2k
658
37.2k
      Value *SecondStoredVal = SL[k]->getValueOperand();
659
37.2k
      Value *SecondSplatValue = nullptr;
660
37.2k
      Constant *SecondPatternValue = nullptr;
661
37.2k
662
37.2k
      if (For == ForMemset::Yes)
663
36.0k
        SecondSplatValue = isBytewiseValue(SecondStoredVal, *DL);
664
1.20k
      else
665
1.20k
        SecondPatternValue = getMemSetPatternValue(SecondStoredVal, DL);
666
37.2k
667
37.2k
      assert((SecondSplatValue || SecondPatternValue) &&
668
37.2k
             "Expected either splat value or pattern value.");
669
37.2k
670
37.2k
      if (isConsecutiveAccess(SL[i], SL[k], *DL, *SE, false)) {
671
8.99k
        if (For == ForMemset::Yes) {
672
8.79k
          if (isa<UndefValue>(FirstSplatValue))
673
0
            FirstSplatValue = SecondSplatValue;
674
8.79k
          if (FirstSplatValue != SecondSplatValue)
675
63
            continue;
676
204
        } else {
677
204
          if (isa<UndefValue>(FirstPatternValue))
678
0
            FirstPatternValue = SecondPatternValue;
679
204
          if (FirstPatternValue != SecondPatternValue)
680
125
            continue;
681
8.81k
        }
682
8.81k
        Tails.insert(SL[k]);
683
8.81k
        Heads.insert(SL[i]);
684
8.81k
        ConsecutiveChain[SL[i]] = SL[k];
685
8.81k
        break;
686
8.81k
      }
687
37.2k
    }
688
12.7k
  }
689
14.1k
690
14.1k
  // We may run into multiple chains that merge into a single chain. We mark the
691
14.1k
  // stores that we transformed so that we don't visit the same store twice.
692
14.1k
  SmallPtrSet<Value *, 16> TransformedStores;
693
14.1k
  bool Changed = false;
694
14.1k
695
14.1k
  // For stores that start but don't end a link in the chain:
696
14.1k
  for (SetVector<StoreInst *>::iterator it = Heads.begin(), e = Heads.end();
697
35.0k
       it != e; 
++it20.9k
) {
698
20.9k
    if (Tails.count(*it))
699
7.21k
      continue;
700
13.7k
701
13.7k
    // We found a store instr that starts a chain. Now follow the chain and try
702
13.7k
    // to transform it.
703
13.7k
    SmallPtrSet<Instruction *, 8> AdjacentStores;
704
13.7k
    StoreInst *I = *it;
705
13.7k
706
13.7k
    StoreInst *HeadStore = I;
707
13.7k
    unsigned StoreSize = 0;
708
13.7k
709
13.7k
    // Collect the chain into a list.
710
36.3k
    while (Tails.count(I) || 
Heads.count(I)27.4k
) {
711
22.5k
      if (TransformedStores.count(I))
712
0
        break;
713
22.5k
      AdjacentStores.insert(I);
714
22.5k
715
22.5k
      StoreSize += DL->getTypeStoreSize(I->getValueOperand()->getType());
716
22.5k
      // Move to the next value in the chain.
717
22.5k
      I = ConsecutiveChain[I];
718
22.5k
    }
719
13.7k
720
13.7k
    Value *StoredVal = HeadStore->getValueOperand();
721
13.7k
    Value *StorePtr = HeadStore->getPointerOperand();
722
13.7k
    const SCEVAddRecExpr *StoreEv = cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
723
13.7k
    APInt Stride = getStoreStride(StoreEv);
724
13.7k
725
13.7k
    // Check to see if the stride matches the size of the stores.  If so, then
726
13.7k
    // we know that every byte is touched in the loop.
727
13.7k
    if (StoreSize != Stride && 
StoreSize != -Stride1.62k
)
728
1.49k
      continue;
729
12.2k
730
12.2k
    bool NegStride = StoreSize == -Stride;
731
12.2k
732
12.2k
    if (processLoopStridedStore(StorePtr, StoreSize, HeadStore->getAlignment(),
733
12.2k
                                StoredVal, HeadStore, AdjacentStores, StoreEv,
734
12.2k
                                BECount, NegStride)) {
735
11.7k
      TransformedStores.insert(AdjacentStores.begin(), AdjacentStores.end());
736
11.7k
      Changed = true;
737
11.7k
    }
738
12.2k
  }
739
14.1k
740
14.1k
  return Changed;
741
14.1k
}
742
743
/// processLoopMemSet - See if this memset can be promoted to a large memset.
744
bool LoopIdiomRecognize::processLoopMemSet(MemSetInst *MSI,
745
1.04k
                                           const SCEV *BECount) {
746
1.04k
  // We can only handle non-volatile memsets with a constant size.
747
1.04k
  if (MSI->isVolatile() || !isa<ConstantInt>(MSI->getLength()))
748
51
    return false;
749
996
750
996
  // If we're not allowed to hack on memset, we fail.
751
996
  if (!HasMemset)
752
0
    return false;
753
996
754
996
  Value *Pointer = MSI->getDest();
755
996
756
996
  // See if the pointer expression is an AddRec like {base,+,1} on the current
757
996
  // loop, which indicates a strided store.  If we have something else, it's a
758
996
  // random store we can't handle.
759
996
  const SCEVAddRecExpr *Ev = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Pointer));
760
996
  if (!Ev || 
Ev->getLoop() != CurLoop652
||
!Ev->isAffine()652
)
761
344
    return false;
762
652
763
652
  // Reject memsets that are so large that they overflow an unsigned.
764
652
  uint64_t SizeInBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue();
765
652
  if ((SizeInBytes >> 32) != 0)
766
0
    return false;
767
652
768
652
  // Check to see if the stride matches the size of the memset.  If so, then we
769
652
  // know that every byte is touched in the loop.
770
652
  const SCEVConstant *ConstStride = dyn_cast<SCEVConstant>(Ev->getOperand(1));
771
652
  if (!ConstStride)
772
0
    return false;
773
652
774
652
  APInt Stride = ConstStride->getAPInt();
775
652
  if (SizeInBytes != Stride && 
SizeInBytes != -Stride444
)
776
331
    return false;
777
321
778
321
  // Verify that the memset value is loop invariant.  If not, we can't promote
779
321
  // the memset.
780
321
  Value *SplatValue = MSI->getValue();
781
321
  if (!SplatValue || !CurLoop->isLoopInvariant(SplatValue))
782
0
    return false;
783
321
784
321
  SmallPtrSet<Instruction *, 1> MSIs;
785
321
  MSIs.insert(MSI);
786
321
  bool NegStride = SizeInBytes == -Stride;
787
321
  return processLoopStridedStore(Pointer, (unsigned)SizeInBytes,
788
321
                                 MSI->getDestAlignment(), SplatValue, MSI, MSIs,
789
321
                                 Ev, BECount, NegStride, /*IsLoopMemset=*/true);
790
321
}
791
792
/// mayLoopAccessLocation - Return true if the specified loop might access the
793
/// specified pointer location, which is a loop-strided access.  The 'Access'
794
/// argument specifies what the verboten forms of access are (read or write).
795
static bool
796
mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L,
797
                      const SCEV *BECount, unsigned StoreSize,
798
                      AliasAnalysis &AA,
799
20.5k
                      SmallPtrSetImpl<Instruction *> &IgnoredStores) {
800
20.5k
  // Get the location that may be stored across the loop.  Since the access is
801
20.5k
  // strided positively through memory, we say that the modified location starts
802
20.5k
  // at the pointer and has infinite size.
803
20.5k
  LocationSize AccessSize = LocationSize::unknown();
804
20.5k
805
20.5k
  // If the loop iterates a fixed number of times, we can refine the access size
806
20.5k
  // to be exactly the size of the memset, which is (BECount+1)*StoreSize
807
20.5k
  if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount))
808
9.22k
    AccessSize = LocationSize::precise((BECst->getValue()->getZExtValue() + 1) *
809
9.22k
                                       StoreSize);
810
20.5k
811
20.5k
  // TODO: For this to be really effective, we have to dive into the pointer
812
20.5k
  // operand in the store.  Store to &A[i] of 100 will always return may alias
813
20.5k
  // with store of &A[100], we need to StoreLoc to be "A" with size of 100,
814
20.5k
  // which will then no-alias a store to &A[100].
815
20.5k
  MemoryLocation StoreLoc(Ptr, AccessSize);
816
20.5k
817
33.4k
  for (Loop::block_iterator BI = L->block_begin(), E = L->block_end(); BI != E;
818
20.5k
       
++BI12.8k
)
819
21.1k
    for (Instruction &I : **BI)
820
121k
      if (IgnoredStores.count(&I) == 0 &&
821
121k
          isModOrRefSet(
822
109k
              intersectModRef(AA.getModRefInfo(&I, StoreLoc), Access)))
823
8.26k
        return true;
824
20.5k
825
20.5k
  
return false12.2k
;
826
20.5k
}
827
828
// If we have a negative stride, Start refers to the end of the memory location
829
// we're trying to memset.  Therefore, we need to recompute the base pointer,
830
// which is just Start - BECount*Size.
831
static const SCEV *getStartForNegStride(const SCEV *Start, const SCEV *BECount,
832
                                        Type *IntPtr, unsigned StoreSize,
833
326
                                        ScalarEvolution *SE) {
834
326
  const SCEV *Index = SE->getTruncateOrZeroExtend(BECount, IntPtr);
835
326
  if (StoreSize != 1)
836
232
    Index = SE->getMulExpr(Index, SE->getConstant(IntPtr, StoreSize),
837
232
                           SCEV::FlagNUW);
838
326
  return SE->getMinusSCEV(Start, Index);
839
326
}
840
841
/// Compute the number of bytes as a SCEV from the backedge taken count.
842
///
843
/// This also maps the SCEV into the provided type and tries to handle the
844
/// computation in a way that will fold cleanly.
845
static const SCEV *getNumBytes(const SCEV *BECount, Type *IntPtr,
846
                               unsigned StoreSize, Loop *CurLoop,
847
12.1k
                               const DataLayout *DL, ScalarEvolution *SE) {
848
12.1k
  const SCEV *NumBytesS;
849
12.1k
  // The # stored bytes is (BECount+1)*Size.  Expand the trip count out to
850
12.1k
  // pointer size if it isn't already.
851
12.1k
  //
852
12.1k
  // If we're going to need to zero extend the BE count, check if we can add
853
12.1k
  // one to it prior to zero extending without overflow. Provided this is safe,
854
12.1k
  // it allows better simplification of the +1.
855
12.1k
  if (DL->getTypeSizeInBits(BECount->getType()) <
856
12.1k
          DL->getTypeSizeInBits(IntPtr) &&
857
12.1k
      SE->isLoopEntryGuardedByCond(
858
1.15k
          CurLoop, ICmpInst::ICMP_NE, BECount,
859
1.15k
          SE->getNegativeSCEV(SE->getOne(BECount->getType())))) {
860
1.08k
    NumBytesS = SE->getZeroExtendExpr(
861
1.08k
        SE->getAddExpr(BECount, SE->getOne(BECount->getType()), SCEV::FlagNUW),
862
1.08k
        IntPtr);
863
11.0k
  } else {
864
11.0k
    NumBytesS = SE->getAddExpr(SE->getTruncateOrZeroExtend(BECount, IntPtr),
865
11.0k
                               SE->getOne(IntPtr), SCEV::FlagNUW);
866
11.0k
  }
867
12.1k
868
12.1k
  // And scale it based on the store size.
869
12.1k
  if (StoreSize != 1) {
870
10.4k
    NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtr, StoreSize),
871
10.4k
                               SCEV::FlagNUW);
872
10.4k
  }
873
12.1k
  return NumBytesS;
874
12.1k
}
875
876
/// processLoopStridedStore - We see a strided store of some value.  If we can
877
/// transform this into a memset or memset_pattern in the loop preheader, do so.
878
bool LoopIdiomRecognize::processLoopStridedStore(
879
    Value *DestPtr, unsigned StoreSize, unsigned StoreAlignment,
880
    Value *StoredVal, Instruction *TheStore,
881
    SmallPtrSetImpl<Instruction *> &Stores, const SCEVAddRecExpr *Ev,
882
12.5k
    const SCEV *BECount, bool NegStride, bool IsLoopMemset) {
883
12.5k
  Value *SplatValue = isBytewiseValue(StoredVal, *DL);
884
12.5k
  Constant *PatternValue = nullptr;
885
12.5k
886
12.5k
  if (!SplatValue)
887
6.05k
    PatternValue = getMemSetPatternValue(StoredVal, DL);
888
12.5k
889
12.5k
  assert((SplatValue || PatternValue) &&
890
12.5k
         "Expected either splat value or pattern value.");
891
12.5k
892
12.5k
  // The trip count of the loop and the base pointer of the addrec SCEV is
893
12.5k
  // guaranteed to be loop invariant, which means that it should dominate the
894
12.5k
  // header.  This allows us to insert code for it in the preheader.
895
12.5k
  unsigned DestAS = DestPtr->getType()->getPointerAddressSpace();
896
12.5k
  BasicBlock *Preheader = CurLoop->getLoopPreheader();
897
12.5k
  IRBuilder<> Builder(Preheader->getTerminator());
898
12.5k
  SCEVExpander Expander(*SE, *DL, "loop-idiom");
899
12.5k
900
12.5k
  Type *DestInt8PtrTy = Builder.getInt8PtrTy(DestAS);
901
12.5k
  Type *IntPtr = Builder.getIntPtrTy(*DL, DestAS);
902
12.5k
903
12.5k
  const SCEV *Start = Ev->getStart();
904
12.5k
  // Handle negative strided loops.
905
12.5k
  if (NegStride)
906
239
    Start = getStartForNegStride(Start, BECount, IntPtr, StoreSize, SE);
907
12.5k
908
12.5k
  // TODO: ideally we should still be able to generate memset if SCEV expander
909
12.5k
  // is taught to generate the dependencies at the latest point.
910
12.5k
  if (!isSafeToExpand(Start, *SE))
911
1
    return false;
912
12.5k
913
12.5k
  // Okay, we have a strided store "p[i]" of a splattable value.  We can turn
914
12.5k
  // this into a memset in the loop preheader now if we want.  However, this
915
12.5k
  // would be unsafe to do if there is anything else in the loop that may read
916
12.5k
  // or write to the aliased location.  Check for any overlap by generating the
917
12.5k
  // base pointer and checking the region.
918
12.5k
  Value *BasePtr =
919
12.5k
      Expander.expandCodeFor(Start, DestInt8PtrTy, Preheader->getTerminator());
920
12.5k
  if (mayLoopAccessLocation(BasePtr, ModRefInfo::ModRef, CurLoop, BECount,
921
12.5k
                            StoreSize, *AA, Stores)) {
922
662
    Expander.clear();
923
662
    // If we generated new code for the base pointer, clean up.
924
662
    RecursivelyDeleteTriviallyDeadInstructions(BasePtr, TLI);
925
662
    return false;
926
662
  }
927
11.9k
928
11.9k
  if (avoidLIRForMultiBlockLoop(/*IsMemset=*/true, IsLoopMemset))
929
1
    return false;
930
11.9k
931
11.9k
  // Okay, everything looks good, insert the memset.
932
11.9k
933
11.9k
  const SCEV *NumBytesS =
934
11.9k
      getNumBytes(BECount, IntPtr, StoreSize, CurLoop, DL, SE);
935
11.9k
936
11.9k
  // TODO: ideally we should still be able to generate memset if SCEV expander
937
11.9k
  // is taught to generate the dependencies at the latest point.
938
11.9k
  if (!isSafeToExpand(NumBytesS, *SE))
939
1
    return false;
940
11.9k
941
11.9k
  Value *NumBytes =
942
11.9k
      Expander.expandCodeFor(NumBytesS, IntPtr, Preheader->getTerminator());
943
11.9k
944
11.9k
  CallInst *NewCall;
945
11.9k
  if (SplatValue) {
946
5.90k
    NewCall =
947
5.90k
        Builder.CreateMemSet(BasePtr, SplatValue, NumBytes, StoreAlignment);
948
5.99k
  } else {
949
5.99k
    // Everything is emitted in default address space
950
5.99k
    Type *Int8PtrTy = DestInt8PtrTy;
951
5.99k
952
5.99k
    Module *M = TheStore->getModule();
953
5.99k
    StringRef FuncName = "memset_pattern16";
954
5.99k
    FunctionCallee MSP = M->getOrInsertFunction(FuncName, Builder.getVoidTy(),
955
5.99k
                                                Int8PtrTy, Int8PtrTy, IntPtr);
956
5.99k
    inferLibFuncAttributes(M, FuncName, *TLI);
957
5.99k
958
5.99k
    // Otherwise we should form a memset_pattern16.  PatternValue is known to be
959
5.99k
    // an constant array of 16-bytes.  Plop the value into a mergable global.
960
5.99k
    GlobalVariable *GV = new GlobalVariable(*M, PatternValue->getType(), true,
961
5.99k
                                            GlobalValue::PrivateLinkage,
962
5.99k
                                            PatternValue, ".memset_pattern");
963
5.99k
    GV->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); // Ok to merge these.
964
5.99k
    GV->setAlignment(16);
965
5.99k
    Value *PatternPtr = ConstantExpr::getBitCast(GV, Int8PtrTy);
966
5.99k
    NewCall = Builder.CreateCall(MSP, {BasePtr, PatternPtr, NumBytes});
967
5.99k
  }
968
11.9k
969
11.9k
  LLVM_DEBUG(dbgs() << "  Formed memset: " << *NewCall << "\n"
970
11.9k
                    << "    from store to: " << *Ev << " at: " << *TheStore
971
11.9k
                    << "\n");
972
11.9k
  NewCall->setDebugLoc(TheStore->getDebugLoc());
973
11.9k
974
11.9k
  ORE.emit([&]() {
975
1
    return OptimizationRemark(DEBUG_TYPE, "ProcessLoopStridedStore",
976
1
                              NewCall->getDebugLoc(), Preheader)
977
1
           << "Transformed loop-strided store into a call to "
978
1
           << ore::NV("NewFunction", NewCall->getCalledFunction())
979
1
           << "() function";
980
1
  });
981
11.9k
982
11.9k
  // Okay, the memset has been formed.  Zap the original store and anything that
983
11.9k
  // feeds into it.
984
11.9k
  for (auto *I : Stores)
985
12.0k
    deleteDeadInstruction(I);
986
11.9k
  ++NumMemSet;
987
11.9k
  return true;
988
11.9k
}
989
990
/// If the stored value is a strided load in the same loop with the same stride
991
/// this may be transformable into a memcpy.  This kicks in for stuff like
992
/// for (i) A[i] = B[i];
993
bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
994
7.79k
                                                    const SCEV *BECount) {
995
7.79k
  assert(SI->isUnordered() && "Expected only non-volatile non-ordered stores.");
996
7.79k
997
7.79k
  Value *StorePtr = SI->getPointerOperand();
998
7.79k
  const SCEVAddRecExpr *StoreEv = cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
999
7.79k
  APInt Stride = getStoreStride(StoreEv);
1000
7.79k
  unsigned StoreSize = DL->getTypeStoreSize(SI->getValueOperand()->getType());
1001
7.79k
  bool NegStride = StoreSize == -Stride;
1002
7.79k
1003
7.79k
  // The store must be feeding a non-volatile load.
1004
7.79k
  LoadInst *LI = cast<LoadInst>(SI->getValueOperand());
1005
7.79k
  assert(LI->isUnordered() && "Expected only non-volatile non-ordered loads.");
1006
7.79k
1007
7.79k
  // See if the pointer expression is an AddRec like {base,+,1} on the current
1008
7.79k
  // loop, which indicates a strided load.  If we have something else, it's a
1009
7.79k
  // random load we can't handle.
1010
7.79k
  const SCEVAddRecExpr *LoadEv =
1011
7.79k
      cast<SCEVAddRecExpr>(SE->getSCEV(LI->getPointerOperand()));
1012
7.79k
1013
7.79k
  // The trip count of the loop and the base pointer of the addrec SCEV is
1014
7.79k
  // guaranteed to be loop invariant, which means that it should dominate the
1015
7.79k
  // header.  This allows us to insert code for it in the preheader.
1016
7.79k
  BasicBlock *Preheader = CurLoop->getLoopPreheader();
1017
7.79k
  IRBuilder<> Builder(Preheader->getTerminator());
1018
7.79k
  SCEVExpander Expander(*SE, *DL, "loop-idiom");
1019
7.79k
1020
7.79k
  const SCEV *StrStart = StoreEv->getStart();
1021
7.79k
  unsigned StrAS = SI->getPointerAddressSpace();
1022
7.79k
  Type *IntPtrTy = Builder.getIntPtrTy(*DL, StrAS);
1023
7.79k
1024
7.79k
  // Handle negative strided loops.
1025
7.79k
  if (NegStride)
1026
84
    StrStart = getStartForNegStride(StrStart, BECount, IntPtrTy, StoreSize, SE);
1027
7.79k
1028
7.79k
  // Okay, we have a strided store "p[i]" of a loaded value.  We can turn
1029
7.79k
  // this into a memcpy in the loop preheader now if we want.  However, this
1030
7.79k
  // would be unsafe to do if there is anything else in the loop that may read
1031
7.79k
  // or write the memory region we're storing to.  This includes the load that
1032
7.79k
  // feeds the stores.  Check for an alias by generating the base address and
1033
7.79k
  // checking everything.
1034
7.79k
  Value *StoreBasePtr = Expander.expandCodeFor(
1035
7.79k
      StrStart, Builder.getInt8PtrTy(StrAS), Preheader->getTerminator());
1036
7.79k
1037
7.79k
  SmallPtrSet<Instruction *, 1> Stores;
1038
7.79k
  Stores.insert(SI);
1039
7.79k
  if (mayLoopAccessLocation(StoreBasePtr, ModRefInfo::ModRef, CurLoop, BECount,
1040
7.79k
                            StoreSize, *AA, Stores)) {
1041
7.59k
    Expander.clear();
1042
7.59k
    // If we generated new code for the base pointer, clean up.
1043
7.59k
    RecursivelyDeleteTriviallyDeadInstructions(StoreBasePtr, TLI);
1044
7.59k
    return false;
1045
7.59k
  }
1046
196
1047
196
  const SCEV *LdStart = LoadEv->getStart();
1048
196
  unsigned LdAS = LI->getPointerAddressSpace();
1049
196
1050
196
  // Handle negative strided loops.
1051
196
  if (NegStride)
1052
3
    LdStart = getStartForNegStride(LdStart, BECount, IntPtrTy, StoreSize, SE);
1053
196
1054
196
  // For a memcpy, we have to make sure that the input array is not being
1055
196
  // mutated by the loop.
1056
196
  Value *LoadBasePtr = Expander.expandCodeFor(
1057
196
      LdStart, Builder.getInt8PtrTy(LdAS), Preheader->getTerminator());
1058
196
1059
196
  if (mayLoopAccessLocation(LoadBasePtr, ModRefInfo::Mod, CurLoop, BECount,
1060
196
                            StoreSize, *AA, Stores)) {
1061
3
    Expander.clear();
1062
3
    // If we generated new code for the base pointer, clean up.
1063
3
    RecursivelyDeleteTriviallyDeadInstructions(LoadBasePtr, TLI);
1064
3
    RecursivelyDeleteTriviallyDeadInstructions(StoreBasePtr, TLI);
1065
3
    return false;
1066
3
  }
1067
193
1068
193
  if (avoidLIRForMultiBlockLoop())
1069
0
    return false;
1070
193
1071
193
  // Okay, everything is safe, we can transform this!
1072
193
1073
193
  const SCEV *NumBytesS =
1074
193
      getNumBytes(BECount, IntPtrTy, StoreSize, CurLoop, DL, SE);
1075
193
1076
193
  Value *NumBytes =
1077
193
      Expander.expandCodeFor(NumBytesS, IntPtrTy, Preheader->getTerminator());
1078
193
1079
193
  CallInst *NewCall = nullptr;
1080
193
  // Check whether to generate an unordered atomic memcpy:
1081
193
  //  If the load or store are atomic, then they must necessarily be unordered
1082
193
  //  by previous checks.
1083
193
  if (!SI->isAtomic() && 
!LI->isAtomic()182
)
1084
178
    NewCall = Builder.CreateMemCpy(StoreBasePtr, SI->getAlignment(),
1085
178
                                   LoadBasePtr, LI->getAlignment(), NumBytes);
1086
15
  else {
1087
15
    // We cannot allow unaligned ops for unordered load/store, so reject
1088
15
    // anything where the alignment isn't at least the element size.
1089
15
    unsigned Align = std::min(SI->getAlignment(), LI->getAlignment());
1090
15
    if (Align < StoreSize)
1091
6
      return false;
1092
9
1093
9
    // If the element.atomic memcpy is not lowered into explicit
1094
9
    // loads/stores later, then it will be lowered into an element-size
1095
9
    // specific lib call. If the lib call doesn't exist for our store size, then
1096
9
    // we shouldn't generate the memcpy.
1097
9
    if (StoreSize > TTI->getAtomicMemIntrinsicMaxElementSize())
1098
2
      return false;
1099
7
1100
7
    // Create the call.
1101
7
    // Note that unordered atomic loads/stores are *required* by the spec to
1102
7
    // have an alignment but non-atomic loads/stores may not.
1103
7
    NewCall = Builder.CreateElementUnorderedAtomicMemCpy(
1104
7
        StoreBasePtr, SI->getAlignment(), LoadBasePtr, LI->getAlignment(),
1105
7
        NumBytes, StoreSize);
1106
7
  }
1107
193
  NewCall->setDebugLoc(SI->getDebugLoc());
1108
185
1109
185
  LLVM_DEBUG(dbgs() << "  Formed memcpy: " << *NewCall << "\n"
1110
185
                    << "    from load ptr=" << *LoadEv << " at: " << *LI << "\n"
1111
185
                    << "    from store ptr=" << *StoreEv << " at: " << *SI
1112
185
                    << "\n");
1113
185
1114
185
  ORE.emit([&]() {
1115
1
    return OptimizationRemark(DEBUG_TYPE, "ProcessLoopStoreOfLoopLoad",
1116
1
                              NewCall->getDebugLoc(), Preheader)
1117
1
           << "Formed a call to "
1118
1
           << ore::NV("NewFunction", NewCall->getCalledFunction())
1119
1
           << "() function";
1120
1
  });
1121
185
1122
185
  // Okay, the memcpy has been formed.  Zap the original store and anything that
1123
185
  // feeds into it.
1124
185
  deleteDeadInstruction(SI);
1125
185
  ++NumMemCpy;
1126
185
  return true;
1127
193
}
1128
1129
// When compiling for codesize we avoid idiom recognition for a multi-block loop
1130
// unless it is a loop_memset idiom or a memset/memcpy idiom in a nested loop.
1131
//
1132
bool LoopIdiomRecognize::avoidLIRForMultiBlockLoop(bool IsMemset,
1133
12.1k
                                                   bool IsLoopMemset) {
1134
12.1k
  if (ApplyCodeSizeHeuristics && 
CurLoop->getNumBlocks() > 14
) {
1135
4
    if (!CurLoop->getParentLoop() && 
(3
!IsMemset3
||
!IsLoopMemset3
)) {
1136
1
      LLVM_DEBUG(dbgs() << "  " << CurLoop->getHeader()->getParent()->getName()
1137
1
                        << " : LIR " << (IsMemset ? "Memset" : "Memcpy")
1138
1
                        << " avoided: multi-block top-level loop\n");
1139
1
      return true;
1140
1
    }
1141
12.1k
  }
1142
12.1k
1143
12.1k
  return false;
1144
12.1k
}
1145
1146
141k
bool LoopIdiomRecognize::runOnNoncountableLoop() {
1147
141k
  LLVM_DEBUG(dbgs() << DEBUG_TYPE " Scanning: F["
1148
141k
                    << CurLoop->getHeader()->getParent()->getName()
1149
141k
                    << "] Noncountable Loop %"
1150
141k
                    << CurLoop->getHeader()->getName() << "\n");
1151
141k
1152
141k
  return recognizePopcount() || 
recognizeAndInsertFFS()141k
;
1153
141k
}
1154
1155
/// Check if the given conditional branch is based on the comparison between
1156
/// a variable and zero, and if the variable is non-zero or zero (JmpOnZero is
1157
/// true), the control yields to the loop entry. If the branch matches the
1158
/// behavior, the variable involved in the comparison is returned. This function
1159
/// will be called to see if the precondition and postcondition of the loop are
1160
/// in desirable form.
1161
static Value *matchCondition(BranchInst *BI, BasicBlock *LoopEntry,
1162
90.9k
                             bool JmpOnZero = false) {
1163
90.9k
  if (!BI || 
!BI->isConditional()90.6k
)
1164
338
    return nullptr;
1165
90.5k
1166
90.5k
  ICmpInst *Cond = dyn_cast<ICmpInst>(BI->getCondition());
1167
90.5k
  if (!Cond)
1168
16.6k
    return nullptr;
1169
73.9k
1170
73.9k
  ConstantInt *CmpZero = dyn_cast<ConstantInt>(Cond->getOperand(1));
1171
73.9k
  if (!CmpZero || 
!CmpZero->isZero()26.9k
)
1172
60.8k
    return nullptr;
1173
13.0k
1174
13.0k
  BasicBlock *TrueSucc = BI->getSuccessor(0);
1175
13.0k
  BasicBlock *FalseSucc = BI->getSuccessor(1);
1176
13.0k
  if (JmpOnZero)
1177
0
    std::swap(TrueSucc, FalseSucc);
1178
13.0k
1179
13.0k
  ICmpInst::Predicate Pred = Cond->getPredicate();
1180
13.0k
  if ((Pred == ICmpInst::ICMP_NE && 
TrueSucc == LoopEntry2
) ||
1181
13.0k
      
(13.0k
Pred == ICmpInst::ICMP_EQ13.0k
&&
FalseSucc == LoopEntry12.7k
))
1182
12.1k
    return Cond->getOperand(0);
1183
939
1184
939
  return nullptr;
1185
939
}
1186
1187
// Check if the recurrence variable `VarX` is in the right form to create
1188
// the idiom. Returns the value coerced to a PHINode if so.
1189
static PHINode *getRecurrenceVar(Value *VarX, Instruction *DefX,
1190
175
                                 BasicBlock *LoopEntry) {
1191
175
  auto *PhiX = dyn_cast<PHINode>(VarX);
1192
175
  if (PhiX && 
PhiX->getParent() == LoopEntry172
&&
1193
175
      
(172
PhiX->getOperand(0) == DefX172
||
PhiX->getOperand(1) == DefX67
))
1194
172
    return PhiX;
1195
3
  return nullptr;
1196
3
}
1197
1198
/// Return true iff the idiom is detected in the loop.
1199
///
1200
/// Additionally:
1201
/// 1) \p CntInst is set to the instruction counting the population bit.
1202
/// 2) \p CntPhi is set to the corresponding phi node.
1203
/// 3) \p Var is set to the value whose population bits are being counted.
1204
///
1205
/// The core idiom we are trying to detect is:
1206
/// \code
1207
///    if (x0 != 0)
1208
///      goto loop-exit // the precondition of the loop
1209
///    cnt0 = init-val;
1210
///    do {
1211
///       x1 = phi (x0, x2);
1212
///       cnt1 = phi(cnt0, cnt2);
1213
///
1214
///       cnt2 = cnt1 + 1;
1215
///        ...
1216
///       x2 = x1 & (x1 - 1);
1217
///        ...
1218
///    } while(x != 0);
1219
///
1220
/// loop-exit:
1221
/// \endcode
1222
static bool detectPopcountIdiom(Loop *CurLoop, BasicBlock *PreCondBB,
1223
                                Instruction *&CntInst, PHINode *&CntPhi,
1224
32.4k
                                Value *&Var) {
1225
32.4k
  // step 1: Check to see if the look-back branch match this pattern:
1226
32.4k
  //    "if (a!=0) goto loop-entry".
1227
32.4k
  BasicBlock *LoopEntry;
1228
32.4k
  Instruction *DefX2, *CountInst;
1229
32.4k
  Value *VarX1, *VarX0;
1230
32.4k
  PHINode *PhiX, *CountPhi;
1231
32.4k
1232
32.4k
  DefX2 = CountInst = nullptr;
1233
32.4k
  VarX1 = VarX0 = nullptr;
1234
32.4k
  PhiX = CountPhi = nullptr;
1235
32.4k
  LoopEntry = *(CurLoop->block_begin());
1236
32.4k
1237
32.4k
  // step 1: Check if the loop-back branch is in desirable form.
1238
32.4k
  {
1239
32.4k
    if (Value *T = matchCondition(
1240
408
            dyn_cast<BranchInst>(LoopEntry->getTerminator()), LoopEntry))
1241
408
      DefX2 = dyn_cast<Instruction>(T);
1242
32.0k
    else
1243
32.0k
      return false;
1244
408
  }
1245
408
1246
408
  // step 2: detect instructions corresponding to "x2 = x1 & (x1 - 1)"
1247
408
  {
1248
408
    if (!DefX2 || 
DefX2->getOpcode() != Instruction::And405
)
1249
392
      return false;
1250
16
1251
16
    BinaryOperator *SubOneOp;
1252
16
1253
16
    if ((SubOneOp = dyn_cast<BinaryOperator>(DefX2->getOperand(0))))
1254
12
      VarX1 = DefX2->getOperand(1);
1255
4
    else {
1256
4
      VarX1 = DefX2->getOperand(0);
1257
4
      SubOneOp = dyn_cast<BinaryOperator>(DefX2->getOperand(1));
1258
4
    }
1259
16
    if (!SubOneOp || 
SubOneOp->getOperand(0) != VarX113
)
1260
6
      return false;
1261
10
1262
10
    ConstantInt *Dec = dyn_cast<ConstantInt>(SubOneOp->getOperand(1));
1263
10
    if (!Dec ||
1264
10
        !((SubOneOp->getOpcode() == Instruction::Sub && 
Dec->isOne()0
) ||
1265
10
          (SubOneOp->getOpcode() == Instruction::Add &&
1266
10
           Dec->isMinusOne()))) {
1267
0
      return false;
1268
0
    }
1269
10
  }
1270
10
1271
10
  // step 3: Check the recurrence of variable X
1272
10
  PhiX = getRecurrenceVar(VarX1, DefX2, LoopEntry);
1273
10
  if (!PhiX)
1274
0
    return false;
1275
10
1276
10
  // step 4: Find the instruction which count the population: cnt2 = cnt1 + 1
1277
10
  {
1278
10
    CountInst = nullptr;
1279
10
    for (BasicBlock::iterator Iter = LoopEntry->getFirstNonPHI()->getIterator(),
1280
10
                              IterE = LoopEntry->end();
1281
18
         Iter != IterE; 
Iter++8
) {
1282
17
      Instruction *Inst = &*Iter;
1283
17
      if (Inst->getOpcode() != Instruction::Add)
1284
4
        continue;
1285
13
1286
13
      ConstantInt *Inc = dyn_cast<ConstantInt>(Inst->getOperand(1));
1287
13
      if (!Inc || 
!Inc->isOne()12
)
1288
3
        continue;
1289
10
1290
10
      PHINode *Phi = getRecurrenceVar(Inst->getOperand(0), Inst, LoopEntry);
1291
10
      if (!Phi)
1292
1
        continue;
1293
9
1294
9
      // Check if the result of the instruction is live of the loop.
1295
9
      bool LiveOutLoop = false;
1296
9
      for (User *U : Inst->users()) {
1297
9
        if ((cast<Instruction>(U))->getParent() != LoopEntry) {
1298
9
          LiveOutLoop = true;
1299
9
          break;
1300
9
        }
1301
9
      }
1302
9
1303
9
      if (LiveOutLoop) {
1304
9
        CountInst = Inst;
1305
9
        CountPhi = Phi;
1306
9
        break;
1307
9
      }
1308
9
    }
1309
10
1310
10
    if (!CountInst)
1311
1
      return false;
1312
9
  }
1313
9
1314
9
  // step 5: check if the precondition is in this form:
1315
9
  //   "if (x != 0) goto loop-head ; else goto somewhere-we-don't-care;"
1316
9
  {
1317
9
    auto *PreCondBr = dyn_cast<BranchInst>(PreCondBB->getTerminator());
1318
9
    Value *T = matchCondition(PreCondBr, CurLoop->getLoopPreheader());
1319
9
    if (T != PhiX->getOperand(0) && 
T != PhiX->getOperand(1)8
)
1320
0
      return false;
1321
9
1322
9
    CntInst = CountInst;
1323
9
    CntPhi = CountPhi;
1324
9
    Var = T;
1325
9
  }
1326
9
1327
9
  return true;
1328
9
}
1329
1330
/// Return true if the idiom is detected in the loop.
1331
///
1332
/// Additionally:
1333
/// 1) \p CntInst is set to the instruction Counting Leading Zeros (CTLZ)
1334
///       or nullptr if there is no such.
1335
/// 2) \p CntPhi is set to the corresponding phi node
1336
///       or nullptr if there is no such.
1337
/// 3) \p Var is set to the value whose CTLZ could be used.
1338
/// 4) \p DefX is set to the instruction calculating Loop exit condition.
1339
///
1340
/// The core idiom we are trying to detect is:
1341
/// \code
1342
///    if (x0 == 0)
1343
///      goto loop-exit // the precondition of the loop
1344
///    cnt0 = init-val;
1345
///    do {
1346
///       x = phi (x0, x.next);   //PhiX
1347
///       cnt = phi(cnt0, cnt.next);
1348
///
1349
///       cnt.next = cnt + 1;
1350
///        ...
1351
///       x.next = x >> 1;   // DefX
1352
///        ...
1353
///    } while(x.next != 0);
1354
///
1355
/// loop-exit:
1356
/// \endcode
1357
static bool detectShiftUntilZeroIdiom(Loop *CurLoop, const DataLayout &DL,
1358
                                      Intrinsic::ID &IntrinID, Value *&InitX,
1359
                                      Instruction *&CntInst, PHINode *&CntPhi,
1360
58.4k
                                      Instruction *&DefX) {
1361
58.4k
  BasicBlock *LoopEntry;
1362
58.4k
  Value *VarX = nullptr;
1363
58.4k
1364
58.4k
  DefX = nullptr;
1365
58.4k
  CntInst = nullptr;
1366
58.4k
  CntPhi = nullptr;
1367
58.4k
  LoopEntry = *(CurLoop->block_begin());
1368
58.4k
1369
58.4k
  // step 1: Check if the loop-back branch is in desirable form.
1370
58.4k
  if (Value *T = matchCondition(
1371
11.7k
          dyn_cast<BranchInst>(LoopEntry->getTerminator()), LoopEntry))
1372
11.7k
    DefX = dyn_cast<Instruction>(T);
1373
46.7k
  else
1374
46.7k
    return false;
1375
11.7k
1376
11.7k
  // step 2: detect instructions corresponding to "x.next = x >> 1 or x << 1"
1377
11.7k
  if (!DefX || 
!DefX->isShift()11.7k
)
1378
11.5k
    return false;
1379
118
  IntrinID = DefX->getOpcode() == Instruction::Shl ? 
Intrinsic::cttz4
:
1380
118
                                                     
Intrinsic::ctlz114
;
1381
118
  ConstantInt *Shft = dyn_cast<ConstantInt>(DefX->getOperand(1));
1382
118
  if (!Shft || 
!Shft->isOne()115
)
1383
18
    return false;
1384
100
  VarX = DefX->getOperand(0);
1385
100
1386
100
  // step 3: Check the recurrence of variable X
1387
100
  PHINode *PhiX = getRecurrenceVar(VarX, DefX, LoopEntry);
1388
100
  if (!PhiX)
1389
2
    return false;
1390
98
1391
98
  InitX = PhiX->getIncomingValueForBlock(CurLoop->getLoopPreheader());
1392
98
1393
98
  // Make sure the initial value can't be negative otherwise the ashr in the
1394
98
  // loop might never reach zero which would make the loop infinite.
1395
98
  if (DefX->getOpcode() == Instruction::AShr && 
!isKnownNonNegative(InitX, DL)49
)
1396
17
    return false;
1397
81
1398
81
  // step 4: Find the instruction which count the CTLZ: cnt.next = cnt + 1
1399
81
  // TODO: We can skip the step. If loop trip count is known (CTLZ),
1400
81
  //       then all uses of "cnt.next" could be optimized to the trip count
1401
81
  //       plus "cnt0". Currently it is not optimized.
1402
81
  //       This step could be used to detect POPCNT instruction:
1403
81
  //       cnt.next = cnt + (x.next & 1)
1404
81
  for (BasicBlock::iterator Iter = LoopEntry->getFirstNonPHI()->getIterator(),
1405
81
                            IterE = LoopEntry->end();
1406
427
       Iter != IterE; 
Iter++346
) {
1407
401
    Instruction *Inst = &*Iter;
1408
401
    if (Inst->getOpcode() != Instruction::Add)
1409
313
      continue;
1410
88
1411
88
    ConstantInt *Inc = dyn_cast<ConstantInt>(Inst->getOperand(1));
1412
88
    if (!Inc || 
!Inc->isOne()85
)
1413
33
      continue;
1414
55
1415
55
    PHINode *Phi = getRecurrenceVar(Inst->getOperand(0), Inst, LoopEntry);
1416
55
    if (!Phi)
1417
0
      continue;
1418
55
1419
55
    CntInst = Inst;
1420
55
    CntPhi = Phi;
1421
55
    break;
1422
55
  }
1423
81
  if (!CntInst)
1424
26
    return false;
1425
55
1426
55
  return true;
1427
55
}
1428
1429
/// Recognize CTLZ or CTTZ idiom in a non-countable loop and convert the loop
1430
/// to countable (with CTLZ / CTTZ trip count). If CTLZ / CTTZ inserted as a new
1431
/// trip count returns true; otherwise, returns false.
1432
141k
bool LoopIdiomRecognize::recognizeAndInsertFFS() {
1433
141k
  // Give up if the loop has multiple blocks or multiple backedges.
1434
141k
  if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1)
1435
82.9k
    return false;
1436
58.4k
1437
58.4k
  Intrinsic::ID IntrinID;
1438
58.4k
  Value *InitX;
1439
58.4k
  Instruction *DefX = nullptr;
1440
58.4k
  PHINode *CntPhi = nullptr;
1441
58.4k
  Instruction *CntInst = nullptr;
1442
58.4k
  // Help decide if transformation is profitable. For ShiftUntilZero idiom,
1443
58.4k
  // this is always 6.
1444
58.4k
  size_t IdiomCanonicalSize = 6;
1445
58.4k
1446
58.4k
  if (!detectShiftUntilZeroIdiom(CurLoop, *DL, IntrinID, InitX,
1447
58.4k
                                 CntInst, CntPhi, DefX))
1448
58.3k
    return false;
1449
55
1450
55
  bool IsCntPhiUsedOutsideLoop = false;
1451
55
  for (User *U : CntPhi->users())
1452
63
    if (!CurLoop->contains(cast<Instruction>(U))) {
1453
26
      IsCntPhiUsedOutsideLoop = true;
1454
26
      break;
1455
26
    }
1456
55
  bool IsCntInstUsedOutsideLoop = false;
1457
55
  for (User *U : CntInst->users())
1458
55
    if (!CurLoop->contains(cast<Instruction>(U))) {
1459
29
      IsCntInstUsedOutsideLoop = true;
1460
29
      break;
1461
29
    }
1462
55
  // If both CntInst and CntPhi are used outside the loop the profitability
1463
55
  // is questionable.
1464
55
  if (IsCntInstUsedOutsideLoop && 
IsCntPhiUsedOutsideLoop29
)
1465
0
    return false;
1466
55
1467
55
  // For some CPUs result of CTLZ(X) intrinsic is undefined
1468
55
  // when X is 0. If we can not guarantee X != 0, we need to check this
1469
55
  // when expand.
1470
55
  bool ZeroCheck = false;
1471
55
  // It is safe to assume Preheader exist as it was checked in
1472
55
  // parent function RunOnLoop.
1473
55
  BasicBlock *PH = CurLoop->getLoopPreheader();
1474
55
1475
55
  // If we are using the count instruction outside the loop, make sure we
1476
55
  // have a zero check as a precondition. Without the check the loop would run
1477
55
  // one iteration for before any check of the input value. This means 0 and 1
1478
55
  // would have identical behavior in the original loop and thus
1479
55
  if (!IsCntPhiUsedOutsideLoop) {
1480
29
    auto *PreCondBB = PH->getSinglePredecessor();
1481
29
    if (!PreCondBB)
1482
2
      return false;
1483
27
    auto *PreCondBI = dyn_cast<BranchInst>(PreCondBB->getTerminator());
1484
27
    if (!PreCondBI)
1485
0
      return false;
1486
27
    if (matchCondition(PreCondBI, PH) != InitX)
1487
2
      return false;
1488
25
    ZeroCheck = true;
1489
25
  }
1490
55
1491
55
  // Check if CTLZ / CTTZ intrinsic is profitable. Assume it is always
1492
55
  // profitable if we delete the loop.
1493
55
1494
55
  // the loop has only 6 instructions:
1495
55
  //  %n.addr.0 = phi [ %n, %entry ], [ %shr, %while.cond ]
1496
55
  //  %i.0 = phi [ %i0, %entry ], [ %inc, %while.cond ]
1497
55
  //  %shr = ashr %n.addr.0, 1
1498
55
  //  %tobool = icmp eq %shr, 0
1499
55
  //  %inc = add nsw %i.0, 1
1500
55
  //  br i1 %tobool
1501
55
1502
55
  const Value *Args[] =
1503
51
      {InitX, ZeroCheck ? 
ConstantInt::getTrue(InitX->getContext())25
1504
51
                        : 
ConstantInt::getFalse(InitX->getContext())26
};
1505
51
1506
51
  // @llvm.dbg doesn't count as they have no semantic effect.
1507
51
  auto InstWithoutDebugIt = CurLoop->getHeader()->instructionsWithoutDebug();
1508
51
  uint32_t HeaderSize =
1509
51
      std::distance(InstWithoutDebugIt.begin(), InstWithoutDebugIt.end());
1510
51
1511
51
  if (HeaderSize != IdiomCanonicalSize &&
1512
51
      TTI->getIntrinsicCost(IntrinID, InitX->getType(), Args) >
1513
4
          TargetTransformInfo::TCC_Basic)
1514
2
    return false;
1515
49
1516
49
  transformLoopToCountable(IntrinID, PH, CntInst, CntPhi, InitX, DefX,
1517
49
                           DefX->getDebugLoc(), ZeroCheck,
1518
49
                           IsCntPhiUsedOutsideLoop);
1519
49
  return true;
1520
49
}
1521
1522
/// Recognizes a population count idiom in a non-countable loop.
1523
///
1524
/// If detected, transforms the relevant code to issue the popcount intrinsic
1525
/// function call, and returns true; otherwise, returns false.
1526
141k
bool LoopIdiomRecognize::recognizePopcount() {
1527
141k
  if (TTI->getPopcntSupport(32) != TargetTransformInfo::PSK_FastHardware)
1528
13.6k
    return false;
1529
127k
1530
127k
  // Counting population are usually conducted by few arithmetic instructions.
1531
127k
  // Such instructions can be easily "absorbed" by vacant slots in a
1532
127k
  // non-compact loop. Therefore, recognizing popcount idiom only makes sense
1533
127k
  // in a compact loop.
1534
127k
1535
127k
  // Give up if the loop has multiple blocks or multiple backedges.
1536
127k
  if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1)
1537
74.1k
    return false;
1538
53.5k
1539
53.5k
  BasicBlock *LoopBody = *(CurLoop->block_begin());
1540
53.5k
  if (LoopBody->size() >= 20) {
1541
1.22k
    // The loop is too big, bail out.
1542
1.22k
    return false;
1543
1.22k
  }
1544
52.3k
1545
52.3k
  // It should have a preheader containing nothing but an unconditional branch.
1546
52.3k
  BasicBlock *PH = CurLoop->getLoopPreheader();
1547
52.3k
  if (!PH || &PH->front() != PH->getTerminator())
1548
13.8k
    return false;
1549
38.4k
  auto *EntryBI = dyn_cast<BranchInst>(PH->getTerminator());
1550
38.4k
  if (!EntryBI || EntryBI->isConditional())
1551
0
    return false;
1552
38.4k
1553
38.4k
  // It should have a precondition block where the generated popcount intrinsic
1554
38.4k
  // function can be inserted.
1555
38.4k
  auto *PreCondBB = PH->getSinglePredecessor();
1556
38.4k
  if (!PreCondBB)
1557
5.95k
    return false;
1558
32.5k
  auto *PreCondBI = dyn_cast<BranchInst>(PreCondBB->getTerminator());
1559
32.5k
  if (!PreCondBI || 
PreCondBI->isUnconditional()32.4k
)
1560
65
    return false;
1561
32.4k
1562
32.4k
  Instruction *CntInst;
1563
32.4k
  PHINode *CntPhi;
1564
32.4k
  Value *Val;
1565
32.4k
  if (!detectPopcountIdiom(CurLoop, PreCondBB, CntInst, CntPhi, Val))
1566
32.4k
    return false;
1567
9
1568
9
  transformLoopToPopcount(PreCondBB, CntInst, CntPhi, Val);
1569
9
  return true;
1570
9
}
1571
1572
static CallInst *createPopcntIntrinsic(IRBuilder<> &IRBuilder, Value *Val,
1573
9
                                       const DebugLoc &DL) {
1574
9
  Value *Ops[] = {Val};
1575
9
  Type *Tys[] = {Val->getType()};
1576
9
1577
9
  Module *M = IRBuilder.GetInsertBlock()->getParent()->getParent();
1578
9
  Function *Func = Intrinsic::getDeclaration(M, Intrinsic::ctpop, Tys);
1579
9
  CallInst *CI = IRBuilder.CreateCall(Func, Ops);
1580
9
  CI->setDebugLoc(DL);
1581
9
1582
9
  return CI;
1583
9
}
1584
1585
static CallInst *createFFSIntrinsic(IRBuilder<> &IRBuilder, Value *Val,
1586
                                    const DebugLoc &DL, bool ZeroCheck,
1587
49
                                    Intrinsic::ID IID) {
1588
49
  Value *Ops[] = {Val, ZeroCheck ? 
IRBuilder.getTrue()23
:
IRBuilder.getFalse()26
};
1589
49
  Type *Tys[] = {Val->getType()};
1590
49
1591
49
  Module *M = IRBuilder.GetInsertBlock()->getParent()->getParent();
1592
49
  Function *Func = Intrinsic::getDeclaration(M, IID, Tys);
1593
49
  CallInst *CI = IRBuilder.CreateCall(Func, Ops);
1594
49
  CI->setDebugLoc(DL);
1595
49
1596
49
  return CI;
1597
49
}
1598
1599
/// Transform the following loop (Using CTLZ, CTTZ is similar):
1600
/// loop:
1601
///   CntPhi = PHI [Cnt0, CntInst]
1602
///   PhiX = PHI [InitX, DefX]
1603
///   CntInst = CntPhi + 1
1604
///   DefX = PhiX >> 1
1605
///   LOOP_BODY
1606
///   Br: loop if (DefX != 0)
1607
/// Use(CntPhi) or Use(CntInst)
1608
///
1609
/// Into:
1610
/// If CntPhi used outside the loop:
1611
///   CountPrev = BitWidth(InitX) - CTLZ(InitX >> 1)
1612
///   Count = CountPrev + 1
1613
/// else
1614
///   Count = BitWidth(InitX) - CTLZ(InitX)
1615
/// loop:
1616
///   CntPhi = PHI [Cnt0, CntInst]
1617
///   PhiX = PHI [InitX, DefX]
1618
///   PhiCount = PHI [Count, Dec]
1619
///   CntInst = CntPhi + 1
1620
///   DefX = PhiX >> 1
1621
///   Dec = PhiCount - 1
1622
///   LOOP_BODY
1623
///   Br: loop if (Dec != 0)
1624
/// Use(CountPrev + Cnt0) // Use(CntPhi)
1625
/// or
1626
/// Use(Count + Cnt0) // Use(CntInst)
1627
///
1628
/// If LOOP_BODY is empty the loop will be deleted.
1629
/// If CntInst and DefX are not used in LOOP_BODY they will be removed.
1630
void LoopIdiomRecognize::transformLoopToCountable(
1631
    Intrinsic::ID IntrinID, BasicBlock *Preheader, Instruction *CntInst,
1632
    PHINode *CntPhi, Value *InitX, Instruction *DefX, const DebugLoc &DL,
1633
49
    bool ZeroCheck, bool IsCntPhiUsedOutsideLoop) {
1634
49
  BranchInst *PreheaderBr = cast<BranchInst>(Preheader->getTerminator());
1635
49
1636
49
  // Step 1: Insert the CTLZ/CTTZ instruction at the end of the preheader block
1637
49
  IRBuilder<> Builder(PreheaderBr);
1638
49
  Builder.SetCurrentDebugLocation(DL);
1639
49
  Value *FFS, *Count, *CountPrev, *NewCount, *InitXNext;
1640
49
1641
49
  //   Count = BitWidth - CTLZ(InitX);
1642
49
  // If there are uses of CntPhi create:
1643
49
  //   CountPrev = BitWidth - CTLZ(InitX >> 1);
1644
49
  if (IsCntPhiUsedOutsideLoop) {
1645
26
    if (DefX->getOpcode() == Instruction::AShr)
1646
16
      InitXNext =
1647
16
          Builder.CreateAShr(InitX, ConstantInt::get(InitX->getType(), 1));
1648
10
    else if (DefX->getOpcode() == Instruction::LShr)
1649
8
      InitXNext =
1650
8
          Builder.CreateLShr(InitX, ConstantInt::get(InitX->getType(), 1));
1651
2
    else if (DefX->getOpcode() == Instruction::Shl) // cttz
1652
2
      InitXNext =
1653
2
          Builder.CreateShl(InitX, ConstantInt::get(InitX->getType(), 1));
1654
2
    else
1655
2
      
llvm_unreachable0
("Unexpected opcode!");
1656
26
  } else
1657
23
    InitXNext = InitX;
1658
49
  FFS = createFFSIntrinsic(Builder, InitXNext, DL, ZeroCheck, IntrinID);
1659
49
  Count = Builder.CreateSub(
1660
49
      ConstantInt::get(FFS->getType(),
1661
49
                       FFS->getType()->getIntegerBitWidth()),
1662
49
      FFS);
1663
49
  if (IsCntPhiUsedOutsideLoop) {
1664
26
    CountPrev = Count;
1665
26
    Count = Builder.CreateAdd(
1666
26
        CountPrev,
1667
26
        ConstantInt::get(CountPrev->getType(), 1));
1668
26
  }
1669
49
1670
49
  NewCount = Builder.CreateZExtOrTrunc(
1671
49
                      IsCntPhiUsedOutsideLoop ? 
CountPrev26
:
Count23
,
1672
49
                      cast<IntegerType>(CntInst->getType()));
1673
49
1674
49
  // If the counter's initial value is not zero, insert Add Inst.
1675
49
  Value *CntInitVal = CntPhi->getIncomingValueForBlock(Preheader);
1676
49
  ConstantInt *InitConst = dyn_cast<ConstantInt>(CntInitVal);
1677
49
  if (!InitConst || 
!InitConst->isZero()43
)
1678
10
    NewCount = Builder.CreateAdd(NewCount, CntInitVal);
1679
49
1680
49
  // Step 2: Insert new IV and loop condition:
1681
49
  // loop:
1682
49
  //   ...
1683
49
  //   PhiCount = PHI [Count, Dec]
1684
49
  //   ...
1685
49
  //   Dec = PhiCount - 1
1686
49
  //   ...
1687
49
  //   Br: loop if (Dec != 0)
1688
49
  BasicBlock *Body = *(CurLoop->block_begin());
1689
49
  auto *LbBr = cast<BranchInst>(Body->getTerminator());
1690
49
  ICmpInst *LbCond = cast<ICmpInst>(LbBr->getCondition());
1691
49
  Type *Ty = Count->getType();
1692
49
1693
49
  PHINode *TcPhi = PHINode::Create(Ty, 2, "tcphi", &Body->front());
1694
49
1695
49
  Builder.SetInsertPoint(LbCond);
1696
49
  Instruction *TcDec = cast<Instruction>(
1697
49
      Builder.CreateSub(TcPhi, ConstantInt::get(Ty, 1),
1698
49
                        "tcdec", false, true));
1699
49
1700
49
  TcPhi->addIncoming(Count, Preheader);
1701
49
  TcPhi->addIncoming(TcDec, Body);
1702
49
1703
49
  CmpInst::Predicate Pred =
1704
49
      (LbBr->getSuccessor(0) == Body) ? 
CmpInst::ICMP_NE0
: CmpInst::ICMP_EQ;
1705
49
  LbCond->setPredicate(Pred);
1706
49
  LbCond->setOperand(0, TcDec);
1707
49
  LbCond->setOperand(1, ConstantInt::get(Ty, 0));
1708
49
1709
49
  // Step 3: All the references to the original counter outside
1710
49
  //  the loop are replaced with the NewCount
1711
49
  if (IsCntPhiUsedOutsideLoop)
1712
26
    CntPhi->replaceUsesOutsideBlock(NewCount, Body);
1713
23
  else
1714
23
    CntInst->replaceUsesOutsideBlock(NewCount, Body);
1715
49
1716
49
  // step 4: Forget the "non-computable" trip-count SCEV associated with the
1717
49
  //   loop. The loop would otherwise not be deleted even if it becomes empty.
1718
49
  SE->forgetLoop(CurLoop);
1719
49
}
1720
1721
void LoopIdiomRecognize::transformLoopToPopcount(BasicBlock *PreCondBB,
1722
                                                 Instruction *CntInst,
1723
9
                                                 PHINode *CntPhi, Value *Var) {
1724
9
  BasicBlock *PreHead = CurLoop->getLoopPreheader();
1725
9
  auto *PreCondBr = cast<BranchInst>(PreCondBB->getTerminator());
1726
9
  const DebugLoc &DL = CntInst->getDebugLoc();
1727
9
1728
9
  // Assuming before transformation, the loop is following:
1729
9
  //  if (x) // the precondition
1730
9
  //     do { cnt++; x &= x - 1; } while(x);
1731
9
1732
9
  // Step 1: Insert the ctpop instruction at the end of the precondition block
1733
9
  IRBuilder<> Builder(PreCondBr);
1734
9
  Value *PopCnt, *PopCntZext, *NewCount, *TripCnt;
1735
9
  {
1736
9
    PopCnt = createPopcntIntrinsic(Builder, Var, DL);
1737
9
    NewCount = PopCntZext =
1738
9
        Builder.CreateZExtOrTrunc(PopCnt, cast<IntegerType>(CntPhi->getType()));
1739
9
1740
9
    if (NewCount != PopCnt)
1741
7
      (cast<Instruction>(NewCount))->setDebugLoc(DL);
1742
9
1743
9
    // TripCnt is exactly the number of iterations the loop has
1744
9
    TripCnt = NewCount;
1745
9
1746
9
    // If the population counter's initial value is not zero, insert Add Inst.
1747
9
    Value *CntInitVal = CntPhi->getIncomingValueForBlock(PreHead);
1748
9
    ConstantInt *InitConst = dyn_cast<ConstantInt>(CntInitVal);
1749
9
    if (!InitConst || 
!InitConst->isZero()8
) {
1750
1
      NewCount = Builder.CreateAdd(NewCount, CntInitVal);
1751
1
      (cast<Instruction>(NewCount))->setDebugLoc(DL);
1752
1
    }
1753
9
  }
1754
9
1755
9
  // Step 2: Replace the precondition from "if (x == 0) goto loop-exit" to
1756
9
  //   "if (NewCount == 0) loop-exit". Without this change, the intrinsic
1757
9
  //   function would be partial dead code, and downstream passes will drag
1758
9
  //   it back from the precondition block to the preheader.
1759
9
  {
1760
9
    ICmpInst *PreCond = cast<ICmpInst>(PreCondBr->getCondition());
1761
9
1762
9
    Value *Opnd0 = PopCntZext;
1763
9
    Value *Opnd1 = ConstantInt::get(PopCntZext->getType(), 0);
1764
9
    if (PreCond->getOperand(0) != Var)
1765
0
      std::swap(Opnd0, Opnd1);
1766
9
1767
9
    ICmpInst *NewPreCond = cast<ICmpInst>(
1768
9
        Builder.CreateICmp(PreCond->getPredicate(), Opnd0, Opnd1));
1769
9
    PreCondBr->setCondition(NewPreCond);
1770
9
1771
9
    RecursivelyDeleteTriviallyDeadInstructions(PreCond, TLI);
1772
9
  }
1773
9
1774
9
  // Step 3: Note that the population count is exactly the trip count of the
1775
9
  // loop in question, which enable us to convert the loop from noncountable
1776
9
  // loop into a countable one. The benefit is twofold:
1777
9
  //
1778
9
  //  - If the loop only counts population, the entire loop becomes dead after
1779
9
  //    the transformation. It is a lot easier to prove a countable loop dead
1780
9
  //    than to prove a noncountable one. (In some C dialects, an infinite loop
1781
9
  //    isn't dead even if it computes nothing useful. In general, DCE needs
1782
9
  //    to prove a noncountable loop finite before safely delete it.)
1783
9
  //
1784
9
  //  - If the loop also performs something else, it remains alive.
1785
9
  //    Since it is transformed to countable form, it can be aggressively
1786
9
  //    optimized by some optimizations which are in general not applicable
1787
9
  //    to a noncountable loop.
1788
9
  //
1789
9
  // After this step, this loop (conceptually) would look like following:
1790
9
  //   newcnt = __builtin_ctpop(x);
1791
9
  //   t = newcnt;
1792
9
  //   if (x)
1793
9
  //     do { cnt++; x &= x-1; t--) } while (t > 0);
1794
9
  BasicBlock *Body = *(CurLoop->block_begin());
1795
9
  {
1796
9
    auto *LbBr = cast<BranchInst>(Body->getTerminator());
1797
9
    ICmpInst *LbCond = cast<ICmpInst>(LbBr->getCondition());
1798
9
    Type *Ty = TripCnt->getType();
1799
9
1800
9
    PHINode *TcPhi = PHINode::Create(Ty, 2, "tcphi", &Body->front());
1801
9
1802
9
    Builder.SetInsertPoint(LbCond);
1803
9
    Instruction *TcDec = cast<Instruction>(
1804
9
        Builder.CreateSub(TcPhi, ConstantInt::get(Ty, 1),
1805
9
                          "tcdec", false, true));
1806
9
1807
9
    TcPhi->addIncoming(TripCnt, PreHead);
1808
9
    TcPhi->addIncoming(TcDec, Body);
1809
9
1810
9
    CmpInst::Predicate Pred =
1811
9
        (LbBr->getSuccessor(0) == Body) ? 
CmpInst::ICMP_UGT1
:
CmpInst::ICMP_SLE8
;
1812
9
    LbCond->setPredicate(Pred);
1813
9
    LbCond->setOperand(0, TcDec);
1814
9
    LbCond->setOperand(1, ConstantInt::get(Ty, 0));
1815
9
  }
1816
9
1817
9
  // Step 4: All the references to the original population counter outside
1818
9
  //  the loop are replaced with the NewCount -- the value returned from
1819
9
  //  __builtin_ctpop().
1820
9
  CntInst->replaceUsesOutsideBlock(NewCount, Body);
1821
9
1822
9
  // step 5: Forget the "non-computable" trip-count SCEV associated with the
1823
9
  //   loop. The loop would otherwise not be deleted even if it becomes empty.
1824
9
  SE->forgetLoop(CurLoop);
1825
9
}