lib/Transforms/Scalar/LoopIdiomRecognize.cpp

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