1218885Sdim//===-- LoopIdiomRecognize.cpp - Loop idiom recognition -------------------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// This pass implements an idiom recognizer that transforms simple loops into a 11218885Sdim// non-loop form. In cases that this kicks in, it can be a significant 12218885Sdim// performance win. 13218885Sdim// 14218885Sdim//===----------------------------------------------------------------------===// 15218885Sdim// 16218885Sdim// TODO List: 17218885Sdim// 18218885Sdim// Future loop memory idioms to recognize: 19218885Sdim// memcmp, memmove, strlen, etc. 20218885Sdim// Future floating point idioms to recognize in -ffast-math mode: 21218885Sdim// fpowi 22218885Sdim// Future integer operation idioms to recognize: 23218885Sdim// ctpop, ctlz, cttz 24218885Sdim// 25218885Sdim// Beware that isel's default lowering for ctpop is highly inefficient for 26218885Sdim// i64 and larger types when i64 is legal and the value has few bits set. It 27218885Sdim// would be good to enhance isel to emit a loop for ctpop in this case. 28218885Sdim// 29218885Sdim// We should enhance the memset/memcpy recognition to handle multiple stores in 30218885Sdim// the loop. This would handle things like: 31218885Sdim// void foo(_Complex float *P) 32218885Sdim// for (i) { __real__(*P) = 0; __imag__(*P) = 0; } 33218885Sdim// 34219077Sdim// We should enhance this to handle negative strides through memory. 35219077Sdim// Alternatively (and perhaps better) we could rely on an earlier pass to force 36219077Sdim// forward iteration through memory, which is generally better for cache 37219077Sdim// behavior. Negative strides *do* happen for memset/memcpy loops. 38219077Sdim// 39218885Sdim// This could recognize common matrix multiplies and dot product idioms and 40218885Sdim// replace them with calls to BLAS (if linked in??). 41218885Sdim// 42218885Sdim//===----------------------------------------------------------------------===// 43218885Sdim 44218885Sdim#define DEBUG_TYPE "loop-idiom" 45218885Sdim#include "llvm/Transforms/Scalar.h" 46239462Sdim#include "llvm/ADT/Statistic.h" 47218885Sdim#include "llvm/Analysis/AliasAnalysis.h" 48218885Sdim#include "llvm/Analysis/LoopPass.h" 49239462Sdim#include "llvm/Analysis/ScalarEvolutionExpander.h" 50218885Sdim#include "llvm/Analysis/ScalarEvolutionExpressions.h" 51249423Sdim#include "llvm/Analysis/TargetTransformInfo.h" 52218885Sdim#include "llvm/Analysis/ValueTracking.h" 53249423Sdim#include "llvm/IR/DataLayout.h" 54249423Sdim#include "llvm/IR/IRBuilder.h" 55249423Sdim#include "llvm/IR/IntrinsicInst.h" 56249423Sdim#include "llvm/IR/Module.h" 57239462Sdim#include "llvm/Support/Debug.h" 58239462Sdim#include "llvm/Support/raw_ostream.h" 59218885Sdim#include "llvm/Target/TargetLibraryInfo.h" 60218885Sdim#include "llvm/Transforms/Utils/Local.h" 61218885Sdimusing namespace llvm; 62218885Sdim 63218885SdimSTATISTIC(NumMemSet, "Number of memset's formed from loop stores"); 64218885SdimSTATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores"); 65218885Sdim 66218885Sdimnamespace { 67249423Sdim 68249423Sdim class LoopIdiomRecognize; 69249423Sdim 70249423Sdim /// This class defines some utility functions for loop idiom recognization. 71249423Sdim class LIRUtil { 72249423Sdim public: 73249423Sdim /// Return true iff the block contains nothing but an uncondition branch 74249423Sdim /// (aka goto instruction). 75249423Sdim static bool isAlmostEmpty(BasicBlock *); 76249423Sdim 77249423Sdim static BranchInst *getBranch(BasicBlock *BB) { 78249423Sdim return dyn_cast<BranchInst>(BB->getTerminator()); 79249423Sdim } 80249423Sdim 81249423Sdim /// Return the condition of the branch terminating the given basic block. 82249423Sdim static Value *getBrCondtion(BasicBlock *); 83249423Sdim 84249423Sdim /// Derive the precondition block (i.e the block that guards the loop 85249423Sdim /// preheader) from the given preheader. 86249423Sdim static BasicBlock *getPrecondBb(BasicBlock *PreHead); 87249423Sdim }; 88249423Sdim 89249423Sdim /// This class is to recoginize idioms of population-count conducted in 90249423Sdim /// a noncountable loop. Currently it only recognizes this pattern: 91249423Sdim /// \code 92249423Sdim /// while(x) {cnt++; ...; x &= x - 1; ...} 93249423Sdim /// \endcode 94249423Sdim class NclPopcountRecognize { 95249423Sdim LoopIdiomRecognize &LIR; 96249423Sdim Loop *CurLoop; 97249423Sdim BasicBlock *PreCondBB; 98249423Sdim 99249423Sdim typedef IRBuilder<> IRBuilderTy; 100249423Sdim 101249423Sdim public: 102249423Sdim explicit NclPopcountRecognize(LoopIdiomRecognize &TheLIR); 103249423Sdim bool recognize(); 104249423Sdim 105249423Sdim private: 106249423Sdim /// Take a glimpse of the loop to see if we need to go ahead recoginizing 107249423Sdim /// the idiom. 108249423Sdim bool preliminaryScreen(); 109249423Sdim 110249423Sdim /// Check if the given conditional branch is based on the comparison 111249423Sdim /// beween a variable and zero, and if the variable is non-zero, the 112249423Sdim /// control yeilds to the loop entry. If the branch matches the behavior, 113249423Sdim /// the variable involved in the comparion is returned. This function will 114249423Sdim /// be called to see if the precondition and postcondition of the loop 115249423Sdim /// are in desirable form. 116249423Sdim Value *matchCondition (BranchInst *Br, BasicBlock *NonZeroTarget) const; 117249423Sdim 118249423Sdim /// Return true iff the idiom is detected in the loop. and 1) \p CntInst 119249423Sdim /// is set to the instruction counting the pupulation bit. 2) \p CntPhi 120249423Sdim /// is set to the corresponding phi node. 3) \p Var is set to the value 121249423Sdim /// whose population bits are being counted. 122249423Sdim bool detectIdiom 123249423Sdim (Instruction *&CntInst, PHINode *&CntPhi, Value *&Var) const; 124249423Sdim 125249423Sdim /// Insert ctpop intrinsic function and some obviously dead instructions. 126249423Sdim void transform (Instruction *CntInst, PHINode *CntPhi, Value *Var); 127249423Sdim 128249423Sdim /// Create llvm.ctpop.* intrinsic function. 129249423Sdim CallInst *createPopcntIntrinsic(IRBuilderTy &IRB, Value *Val, DebugLoc DL); 130249423Sdim }; 131249423Sdim 132218885Sdim class LoopIdiomRecognize : public LoopPass { 133218885Sdim Loop *CurLoop; 134243830Sdim const DataLayout *TD; 135218885Sdim DominatorTree *DT; 136218885Sdim ScalarEvolution *SE; 137218885Sdim TargetLibraryInfo *TLI; 138249423Sdim const TargetTransformInfo *TTI; 139218885Sdim public: 140218885Sdim static char ID; 141218885Sdim explicit LoopIdiomRecognize() : LoopPass(ID) { 142218885Sdim initializeLoopIdiomRecognizePass(*PassRegistry::getPassRegistry()); 143249423Sdim TD = 0; DT = 0; SE = 0; TLI = 0; TTI = 0; 144218885Sdim } 145218885Sdim 146218885Sdim bool runOnLoop(Loop *L, LPPassManager &LPM); 147218885Sdim bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount, 148218885Sdim SmallVectorImpl<BasicBlock*> &ExitBlocks); 149218885Sdim 150218885Sdim bool processLoopStore(StoreInst *SI, const SCEV *BECount); 151218885Sdim bool processLoopMemSet(MemSetInst *MSI, const SCEV *BECount); 152221345Sdim 153218885Sdim bool processLoopStridedStore(Value *DestPtr, unsigned StoreSize, 154218885Sdim unsigned StoreAlignment, 155218885Sdim Value *SplatValue, Instruction *TheStore, 156218885Sdim const SCEVAddRecExpr *Ev, 157218885Sdim const SCEV *BECount); 158218885Sdim bool processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize, 159218885Sdim const SCEVAddRecExpr *StoreEv, 160218885Sdim const SCEVAddRecExpr *LoadEv, 161218885Sdim const SCEV *BECount); 162221345Sdim 163218885Sdim /// This transformation requires natural loop information & requires that 164218885Sdim /// loop preheaders be inserted into the CFG. 165218885Sdim /// 166218885Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const { 167218885Sdim AU.addRequired<LoopInfo>(); 168218885Sdim AU.addPreserved<LoopInfo>(); 169218885Sdim AU.addRequiredID(LoopSimplifyID); 170218885Sdim AU.addPreservedID(LoopSimplifyID); 171218885Sdim AU.addRequiredID(LCSSAID); 172218885Sdim AU.addPreservedID(LCSSAID); 173218885Sdim AU.addRequired<AliasAnalysis>(); 174218885Sdim AU.addPreserved<AliasAnalysis>(); 175218885Sdim AU.addRequired<ScalarEvolution>(); 176218885Sdim AU.addPreserved<ScalarEvolution>(); 177218885Sdim AU.addPreserved<DominatorTree>(); 178218885Sdim AU.addRequired<DominatorTree>(); 179218885Sdim AU.addRequired<TargetLibraryInfo>(); 180249423Sdim AU.addRequired<TargetTransformInfo>(); 181218885Sdim } 182249423Sdim 183249423Sdim const DataLayout *getDataLayout() { 184249423Sdim return TD ? TD : TD=getAnalysisIfAvailable<DataLayout>(); 185249423Sdim } 186249423Sdim 187249423Sdim DominatorTree *getDominatorTree() { 188249423Sdim return DT ? DT : (DT=&getAnalysis<DominatorTree>()); 189249423Sdim } 190249423Sdim 191249423Sdim ScalarEvolution *getScalarEvolution() { 192249423Sdim return SE ? SE : (SE = &getAnalysis<ScalarEvolution>()); 193249423Sdim } 194249423Sdim 195249423Sdim TargetLibraryInfo *getTargetLibraryInfo() { 196249423Sdim return TLI ? TLI : (TLI = &getAnalysis<TargetLibraryInfo>()); 197249423Sdim } 198249423Sdim 199249423Sdim const TargetTransformInfo *getTargetTransformInfo() { 200249423Sdim return TTI ? TTI : (TTI = &getAnalysis<TargetTransformInfo>()); 201249423Sdim } 202249423Sdim 203249423Sdim Loop *getLoop() const { return CurLoop; } 204249423Sdim 205249423Sdim private: 206249423Sdim bool runOnNoncountableLoop(); 207249423Sdim bool runOnCountableLoop(); 208218885Sdim }; 209218885Sdim} 210218885Sdim 211218885Sdimchar LoopIdiomRecognize::ID = 0; 212218885SdimINITIALIZE_PASS_BEGIN(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms", 213218885Sdim false, false) 214218885SdimINITIALIZE_PASS_DEPENDENCY(LoopInfo) 215218885SdimINITIALIZE_PASS_DEPENDENCY(DominatorTree) 216218885SdimINITIALIZE_PASS_DEPENDENCY(LoopSimplify) 217218885SdimINITIALIZE_PASS_DEPENDENCY(LCSSA) 218218885SdimINITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 219218885SdimINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 220218885SdimINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 221249423SdimINITIALIZE_AG_DEPENDENCY(TargetTransformInfo) 222218885SdimINITIALIZE_PASS_END(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms", 223218885Sdim false, false) 224218885Sdim 225218885SdimPass *llvm::createLoopIdiomPass() { return new LoopIdiomRecognize(); } 226218885Sdim 227223017Sdim/// deleteDeadInstruction - Delete this instruction. Before we do, go through 228218885Sdim/// and zero out all the operands of this instruction. If any of them become 229218885Sdim/// dead, delete them and the computation tree that feeds them. 230218885Sdim/// 231243830Sdimstatic void deleteDeadInstruction(Instruction *I, ScalarEvolution &SE, 232243830Sdim const TargetLibraryInfo *TLI) { 233218885Sdim SmallVector<Instruction*, 32> NowDeadInsts; 234221345Sdim 235218885Sdim NowDeadInsts.push_back(I); 236221345Sdim 237218885Sdim // Before we touch this instruction, remove it from SE! 238218885Sdim do { 239218885Sdim Instruction *DeadInst = NowDeadInsts.pop_back_val(); 240221345Sdim 241218885Sdim // This instruction is dead, zap it, in stages. Start by removing it from 242218885Sdim // SCEV. 243218885Sdim SE.forgetValue(DeadInst); 244221345Sdim 245218885Sdim for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { 246218885Sdim Value *Op = DeadInst->getOperand(op); 247218885Sdim DeadInst->setOperand(op, 0); 248221345Sdim 249218885Sdim // If this operand just became dead, add it to the NowDeadInsts list. 250218885Sdim if (!Op->use_empty()) continue; 251221345Sdim 252218885Sdim if (Instruction *OpI = dyn_cast<Instruction>(Op)) 253243830Sdim if (isInstructionTriviallyDead(OpI, TLI)) 254218885Sdim NowDeadInsts.push_back(OpI); 255218885Sdim } 256221345Sdim 257218885Sdim DeadInst->eraseFromParent(); 258221345Sdim 259218885Sdim } while (!NowDeadInsts.empty()); 260218885Sdim} 261218885Sdim 262223017Sdim/// deleteIfDeadInstruction - If the specified value is a dead instruction, 263223017Sdim/// delete it and any recursively used instructions. 264243830Sdimstatic void deleteIfDeadInstruction(Value *V, ScalarEvolution &SE, 265243830Sdim const TargetLibraryInfo *TLI) { 266223017Sdim if (Instruction *I = dyn_cast<Instruction>(V)) 267243830Sdim if (isInstructionTriviallyDead(I, TLI)) 268243830Sdim deleteDeadInstruction(I, SE, TLI); 269223017Sdim} 270223017Sdim 271249423Sdim//===----------------------------------------------------------------------===// 272249423Sdim// 273249423Sdim// Implementation of LIRUtil 274249423Sdim// 275249423Sdim//===----------------------------------------------------------------------===// 276221345Sdim 277249423Sdim// This fucntion will return true iff the given block contains nothing but goto. 278249423Sdim// A typical usage of this function is to check if the preheader fucntion is 279249423Sdim// "almost" empty such that generated intrinsic function can be moved across 280249423Sdim// preheader and to be placed at the end of the preconditiona block without 281249423Sdim// concerning of breaking data dependence. 282249423Sdimbool LIRUtil::isAlmostEmpty(BasicBlock *BB) { 283249423Sdim if (BranchInst *Br = getBranch(BB)) { 284249423Sdim return Br->isUnconditional() && BB->size() == 1; 285249423Sdim } 286249423Sdim return false; 287249423Sdim} 288249423Sdim 289249423SdimValue *LIRUtil::getBrCondtion(BasicBlock *BB) { 290249423Sdim BranchInst *Br = getBranch(BB); 291249423Sdim return Br ? Br->getCondition() : 0; 292249423Sdim} 293249423Sdim 294249423SdimBasicBlock *LIRUtil::getPrecondBb(BasicBlock *PreHead) { 295249423Sdim if (BasicBlock *BB = PreHead->getSinglePredecessor()) { 296249423Sdim BranchInst *Br = getBranch(BB); 297249423Sdim return Br && Br->isConditional() ? BB : 0; 298249423Sdim } 299249423Sdim return 0; 300249423Sdim} 301249423Sdim 302249423Sdim//===----------------------------------------------------------------------===// 303249423Sdim// 304249423Sdim// Implementation of NclPopcountRecognize 305249423Sdim// 306249423Sdim//===----------------------------------------------------------------------===// 307249423Sdim 308249423SdimNclPopcountRecognize::NclPopcountRecognize(LoopIdiomRecognize &TheLIR): 309249423Sdim LIR(TheLIR), CurLoop(TheLIR.getLoop()), PreCondBB(0) { 310249423Sdim} 311249423Sdim 312249423Sdimbool NclPopcountRecognize::preliminaryScreen() { 313249423Sdim const TargetTransformInfo *TTI = LIR.getTargetTransformInfo(); 314249423Sdim if (TTI->getPopcntSupport(32) != TargetTransformInfo::PSK_FastHardware) 315243830Sdim return false; 316243830Sdim 317249423Sdim // Counting population are usually conducted by few arithmetic instrutions. 318249423Sdim // Such instructions can be easilly "absorbed" by vacant slots in a 319249423Sdim // non-compact loop. Therefore, recognizing popcount idiom only makes sense 320249423Sdim // in a compact loop. 321249423Sdim 322249423Sdim // Give up if the loop has multiple blocks or multiple backedges. 323249423Sdim if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1) 324224145Sdim return false; 325224145Sdim 326249423Sdim BasicBlock *LoopBody = *(CurLoop->block_begin()); 327249423Sdim if (LoopBody->size() >= 20) { 328249423Sdim // The loop is too big, bail out. 329218885Sdim return false; 330249423Sdim } 331249423Sdim 332249423Sdim // It should have a preheader containing nothing but a goto instruction. 333249423Sdim BasicBlock *PreHead = CurLoop->getLoopPreheader(); 334249423Sdim if (!PreHead || !LIRUtil::isAlmostEmpty(PreHead)) 335249423Sdim return false; 336249423Sdim 337249423Sdim // It should have a precondition block where the generated popcount instrinsic 338249423Sdim // function will be inserted. 339249423Sdim PreCondBB = LIRUtil::getPrecondBb(PreHead); 340249423Sdim if (!PreCondBB) 341249423Sdim return false; 342249423Sdim 343249423Sdim return true; 344249423Sdim} 345249423Sdim 346249423SdimValue *NclPopcountRecognize::matchCondition (BranchInst *Br, 347249423Sdim BasicBlock *LoopEntry) const { 348249423Sdim if (!Br || !Br->isConditional()) 349249423Sdim return 0; 350249423Sdim 351249423Sdim ICmpInst *Cond = dyn_cast<ICmpInst>(Br->getCondition()); 352249423Sdim if (!Cond) 353249423Sdim return 0; 354249423Sdim 355249423Sdim ConstantInt *CmpZero = dyn_cast<ConstantInt>(Cond->getOperand(1)); 356249423Sdim if (!CmpZero || !CmpZero->isZero()) 357249423Sdim return 0; 358249423Sdim 359249423Sdim ICmpInst::Predicate Pred = Cond->getPredicate(); 360249423Sdim if ((Pred == ICmpInst::ICMP_NE && Br->getSuccessor(0) == LoopEntry) || 361249423Sdim (Pred == ICmpInst::ICMP_EQ && Br->getSuccessor(1) == LoopEntry)) 362249423Sdim return Cond->getOperand(0); 363249423Sdim 364249423Sdim return 0; 365249423Sdim} 366249423Sdim 367249423Sdimbool NclPopcountRecognize::detectIdiom(Instruction *&CntInst, 368249423Sdim PHINode *&CntPhi, 369249423Sdim Value *&Var) const { 370249423Sdim // Following code tries to detect this idiom: 371249423Sdim // 372249423Sdim // if (x0 != 0) 373249423Sdim // goto loop-exit // the precondition of the loop 374249423Sdim // cnt0 = init-val; 375249423Sdim // do { 376249423Sdim // x1 = phi (x0, x2); 377249423Sdim // cnt1 = phi(cnt0, cnt2); 378249423Sdim // 379249423Sdim // cnt2 = cnt1 + 1; 380249423Sdim // ... 381249423Sdim // x2 = x1 & (x1 - 1); 382249423Sdim // ... 383249423Sdim // } while(x != 0); 384249423Sdim // 385249423Sdim // loop-exit: 386249423Sdim // 387249423Sdim 388249423Sdim // step 1: Check to see if the look-back branch match this pattern: 389249423Sdim // "if (a!=0) goto loop-entry". 390249423Sdim BasicBlock *LoopEntry; 391249423Sdim Instruction *DefX2, *CountInst; 392249423Sdim Value *VarX1, *VarX0; 393249423Sdim PHINode *PhiX, *CountPhi; 394249423Sdim 395249423Sdim DefX2 = CountInst = 0; 396249423Sdim VarX1 = VarX0 = 0; 397249423Sdim PhiX = CountPhi = 0; 398249423Sdim LoopEntry = *(CurLoop->block_begin()); 399249423Sdim 400249423Sdim // step 1: Check if the loop-back branch is in desirable form. 401249423Sdim { 402249423Sdim if (Value *T = matchCondition (LIRUtil::getBranch(LoopEntry), LoopEntry)) 403249423Sdim DefX2 = dyn_cast<Instruction>(T); 404249423Sdim else 405249423Sdim return false; 406249423Sdim } 407249423Sdim 408249423Sdim // step 2: detect instructions corresponding to "x2 = x1 & (x1 - 1)" 409249423Sdim { 410249423Sdim if (!DefX2 || DefX2->getOpcode() != Instruction::And) 411249423Sdim return false; 412249423Sdim 413249423Sdim BinaryOperator *SubOneOp; 414249423Sdim 415249423Sdim if ((SubOneOp = dyn_cast<BinaryOperator>(DefX2->getOperand(0)))) 416249423Sdim VarX1 = DefX2->getOperand(1); 417249423Sdim else { 418249423Sdim VarX1 = DefX2->getOperand(0); 419249423Sdim SubOneOp = dyn_cast<BinaryOperator>(DefX2->getOperand(1)); 420249423Sdim } 421249423Sdim if (!SubOneOp) 422249423Sdim return false; 423249423Sdim 424249423Sdim Instruction *SubInst = cast<Instruction>(SubOneOp); 425249423Sdim ConstantInt *Dec = dyn_cast<ConstantInt>(SubInst->getOperand(1)); 426249423Sdim if (!Dec || 427249423Sdim !((SubInst->getOpcode() == Instruction::Sub && Dec->isOne()) || 428249423Sdim (SubInst->getOpcode() == Instruction::Add && Dec->isAllOnesValue()))) { 429249423Sdim return false; 430249423Sdim } 431249423Sdim } 432249423Sdim 433249423Sdim // step 3: Check the recurrence of variable X 434249423Sdim { 435249423Sdim PhiX = dyn_cast<PHINode>(VarX1); 436249423Sdim if (!PhiX || 437249423Sdim (PhiX->getOperand(0) != DefX2 && PhiX->getOperand(1) != DefX2)) { 438249423Sdim return false; 439249423Sdim } 440249423Sdim } 441249423Sdim 442249423Sdim // step 4: Find the instruction which count the population: cnt2 = cnt1 + 1 443249423Sdim { 444249423Sdim CountInst = NULL; 445249423Sdim for (BasicBlock::iterator Iter = LoopEntry->getFirstNonPHI(), 446249423Sdim IterE = LoopEntry->end(); Iter != IterE; Iter++) { 447249423Sdim Instruction *Inst = Iter; 448249423Sdim if (Inst->getOpcode() != Instruction::Add) 449249423Sdim continue; 450249423Sdim 451249423Sdim ConstantInt *Inc = dyn_cast<ConstantInt>(Inst->getOperand(1)); 452249423Sdim if (!Inc || !Inc->isOne()) 453249423Sdim continue; 454249423Sdim 455249423Sdim PHINode *Phi = dyn_cast<PHINode>(Inst->getOperand(0)); 456249423Sdim if (!Phi || Phi->getParent() != LoopEntry) 457249423Sdim continue; 458249423Sdim 459249423Sdim // Check if the result of the instruction is live of the loop. 460249423Sdim bool LiveOutLoop = false; 461249423Sdim for (Value::use_iterator I = Inst->use_begin(), E = Inst->use_end(); 462249423Sdim I != E; I++) { 463249423Sdim if ((cast<Instruction>(*I))->getParent() != LoopEntry) { 464249423Sdim LiveOutLoop = true; break; 465249423Sdim } 466249423Sdim } 467249423Sdim 468249423Sdim if (LiveOutLoop) { 469249423Sdim CountInst = Inst; 470249423Sdim CountPhi = Phi; 471249423Sdim break; 472249423Sdim } 473249423Sdim } 474249423Sdim 475249423Sdim if (!CountInst) 476249423Sdim return false; 477249423Sdim } 478249423Sdim 479249423Sdim // step 5: check if the precondition is in this form: 480249423Sdim // "if (x != 0) goto loop-head ; else goto somewhere-we-don't-care;" 481249423Sdim { 482249423Sdim BranchInst *PreCondBr = LIRUtil::getBranch(PreCondBB); 483249423Sdim Value *T = matchCondition (PreCondBr, CurLoop->getLoopPreheader()); 484249423Sdim if (T != PhiX->getOperand(0) && T != PhiX->getOperand(1)) 485249423Sdim return false; 486249423Sdim 487249423Sdim CntInst = CountInst; 488249423Sdim CntPhi = CountPhi; 489249423Sdim Var = T; 490249423Sdim } 491249423Sdim 492249423Sdim return true; 493249423Sdim} 494249423Sdim 495249423Sdimvoid NclPopcountRecognize::transform(Instruction *CntInst, 496249423Sdim PHINode *CntPhi, Value *Var) { 497249423Sdim 498249423Sdim ScalarEvolution *SE = LIR.getScalarEvolution(); 499249423Sdim TargetLibraryInfo *TLI = LIR.getTargetLibraryInfo(); 500249423Sdim BasicBlock *PreHead = CurLoop->getLoopPreheader(); 501249423Sdim BranchInst *PreCondBr = LIRUtil::getBranch(PreCondBB); 502249423Sdim const DebugLoc DL = CntInst->getDebugLoc(); 503249423Sdim 504249423Sdim // Assuming before transformation, the loop is following: 505249423Sdim // if (x) // the precondition 506249423Sdim // do { cnt++; x &= x - 1; } while(x); 507249423Sdim 508249423Sdim // Step 1: Insert the ctpop instruction at the end of the precondition block 509249423Sdim IRBuilderTy Builder(PreCondBr); 510249423Sdim Value *PopCnt, *PopCntZext, *NewCount, *TripCnt; 511249423Sdim { 512249423Sdim PopCnt = createPopcntIntrinsic(Builder, Var, DL); 513249423Sdim NewCount = PopCntZext = 514249423Sdim Builder.CreateZExtOrTrunc(PopCnt, cast<IntegerType>(CntPhi->getType())); 515249423Sdim 516249423Sdim if (NewCount != PopCnt) 517249423Sdim (cast<Instruction>(NewCount))->setDebugLoc(DL); 518249423Sdim 519249423Sdim // TripCnt is exactly the number of iterations the loop has 520249423Sdim TripCnt = NewCount; 521249423Sdim 522249423Sdim // If the popoulation counter's initial value is not zero, insert Add Inst. 523249423Sdim Value *CntInitVal = CntPhi->getIncomingValueForBlock(PreHead); 524249423Sdim ConstantInt *InitConst = dyn_cast<ConstantInt>(CntInitVal); 525249423Sdim if (!InitConst || !InitConst->isZero()) { 526249423Sdim NewCount = Builder.CreateAdd(NewCount, CntInitVal); 527249423Sdim (cast<Instruction>(NewCount))->setDebugLoc(DL); 528249423Sdim } 529249423Sdim } 530249423Sdim 531249423Sdim // Step 2: Replace the precondition from "if(x == 0) goto loop-exit" to 532249423Sdim // "if(NewCount == 0) loop-exit". Withtout this change, the intrinsic 533249423Sdim // function would be partial dead code, and downstream passes will drag 534249423Sdim // it back from the precondition block to the preheader. 535249423Sdim { 536249423Sdim ICmpInst *PreCond = cast<ICmpInst>(PreCondBr->getCondition()); 537249423Sdim 538249423Sdim Value *Opnd0 = PopCntZext; 539249423Sdim Value *Opnd1 = ConstantInt::get(PopCntZext->getType(), 0); 540249423Sdim if (PreCond->getOperand(0) != Var) 541249423Sdim std::swap(Opnd0, Opnd1); 542249423Sdim 543249423Sdim ICmpInst *NewPreCond = 544249423Sdim cast<ICmpInst>(Builder.CreateICmp(PreCond->getPredicate(), Opnd0, Opnd1)); 545249423Sdim PreCond->replaceAllUsesWith(NewPreCond); 546249423Sdim 547249423Sdim deleteDeadInstruction(PreCond, *SE, TLI); 548249423Sdim } 549249423Sdim 550249423Sdim // Step 3: Note that the population count is exactly the trip count of the 551249423Sdim // loop in question, which enble us to to convert the loop from noncountable 552249423Sdim // loop into a countable one. The benefit is twofold: 553249423Sdim // 554249423Sdim // - If the loop only counts population, the entire loop become dead after 555249423Sdim // the transformation. It is lots easier to prove a countable loop dead 556249423Sdim // than to prove a noncountable one. (In some C dialects, a infite loop 557249423Sdim // isn't dead even if it computes nothing useful. In general, DCE needs 558249423Sdim // to prove a noncountable loop finite before safely delete it.) 559249423Sdim // 560249423Sdim // - If the loop also performs something else, it remains alive. 561249423Sdim // Since it is transformed to countable form, it can be aggressively 562249423Sdim // optimized by some optimizations which are in general not applicable 563249423Sdim // to a noncountable loop. 564249423Sdim // 565249423Sdim // After this step, this loop (conceptually) would look like following: 566249423Sdim // newcnt = __builtin_ctpop(x); 567249423Sdim // t = newcnt; 568249423Sdim // if (x) 569249423Sdim // do { cnt++; x &= x-1; t--) } while (t > 0); 570249423Sdim BasicBlock *Body = *(CurLoop->block_begin()); 571249423Sdim { 572249423Sdim BranchInst *LbBr = LIRUtil::getBranch(Body); 573249423Sdim ICmpInst *LbCond = cast<ICmpInst>(LbBr->getCondition()); 574249423Sdim Type *Ty = TripCnt->getType(); 575249423Sdim 576249423Sdim PHINode *TcPhi = PHINode::Create(Ty, 2, "tcphi", Body->begin()); 577249423Sdim 578249423Sdim Builder.SetInsertPoint(LbCond); 579249423Sdim Value *Opnd1 = cast<Value>(TcPhi); 580249423Sdim Value *Opnd2 = cast<Value>(ConstantInt::get(Ty, 1)); 581249423Sdim Instruction *TcDec = 582249423Sdim cast<Instruction>(Builder.CreateSub(Opnd1, Opnd2, "tcdec", false, true)); 583249423Sdim 584249423Sdim TcPhi->addIncoming(TripCnt, PreHead); 585249423Sdim TcPhi->addIncoming(TcDec, Body); 586249423Sdim 587249423Sdim CmpInst::Predicate Pred = (LbBr->getSuccessor(0) == Body) ? 588249423Sdim CmpInst::ICMP_UGT : CmpInst::ICMP_SLE; 589249423Sdim LbCond->setPredicate(Pred); 590249423Sdim LbCond->setOperand(0, TcDec); 591249423Sdim LbCond->setOperand(1, cast<Value>(ConstantInt::get(Ty, 0))); 592249423Sdim } 593249423Sdim 594249423Sdim // Step 4: All the references to the original population counter outside 595249423Sdim // the loop are replaced with the NewCount -- the value returned from 596249423Sdim // __builtin_ctpop(). 597249423Sdim { 598249423Sdim SmallVector<Value *, 4> CntUses; 599249423Sdim for (Value::use_iterator I = CntInst->use_begin(), E = CntInst->use_end(); 600249423Sdim I != E; I++) { 601249423Sdim if (cast<Instruction>(*I)->getParent() != Body) 602249423Sdim CntUses.push_back(*I); 603249423Sdim } 604249423Sdim for (unsigned Idx = 0; Idx < CntUses.size(); Idx++) { 605249423Sdim (cast<Instruction>(CntUses[Idx]))->replaceUsesOfWith(CntInst, NewCount); 606249423Sdim } 607249423Sdim } 608249423Sdim 609249423Sdim // step 5: Forget the "non-computable" trip-count SCEV associated with the 610249423Sdim // loop. The loop would otherwise not be deleted even if it becomes empty. 611249423Sdim SE->forgetLoop(CurLoop); 612249423Sdim} 613249423Sdim 614249423SdimCallInst *NclPopcountRecognize::createPopcntIntrinsic(IRBuilderTy &IRBuilder, 615249423Sdim Value *Val, DebugLoc DL) { 616249423Sdim Value *Ops[] = { Val }; 617249423Sdim Type *Tys[] = { Val->getType() }; 618249423Sdim 619249423Sdim Module *M = (*(CurLoop->block_begin()))->getParent()->getParent(); 620249423Sdim Value *Func = Intrinsic::getDeclaration(M, Intrinsic::ctpop, Tys); 621249423Sdim CallInst *CI = IRBuilder.CreateCall(Func, Ops); 622249423Sdim CI->setDebugLoc(DL); 623249423Sdim 624249423Sdim return CI; 625249423Sdim} 626249423Sdim 627249423Sdim/// recognize - detect population count idiom in a non-countable loop. If 628249423Sdim/// detected, transform the relevant code to popcount intrinsic function 629249423Sdim/// call, and return true; otherwise, return false. 630249423Sdimbool NclPopcountRecognize::recognize() { 631249423Sdim 632249423Sdim if (!LIR.getTargetTransformInfo()) 633249423Sdim return false; 634249423Sdim 635249423Sdim LIR.getScalarEvolution(); 636249423Sdim 637249423Sdim if (!preliminaryScreen()) 638249423Sdim return false; 639249423Sdim 640249423Sdim Instruction *CntInst; 641249423Sdim PHINode *CntPhi; 642249423Sdim Value *Val; 643249423Sdim if (!detectIdiom(CntInst, CntPhi, Val)) 644249423Sdim return false; 645249423Sdim 646249423Sdim transform(CntInst, CntPhi, Val); 647249423Sdim return true; 648249423Sdim} 649249423Sdim 650249423Sdim//===----------------------------------------------------------------------===// 651249423Sdim// 652249423Sdim// Implementation of LoopIdiomRecognize 653249423Sdim// 654249423Sdim//===----------------------------------------------------------------------===// 655249423Sdim 656249423Sdimbool LoopIdiomRecognize::runOnCountableLoop() { 657249423Sdim const SCEV *BECount = SE->getBackedgeTakenCount(CurLoop); 658218885Sdim if (isa<SCEVCouldNotCompute>(BECount)) return false; 659221345Sdim 660218885Sdim // If this loop executes exactly one time, then it should be peeled, not 661218885Sdim // optimized by this pass. 662218885Sdim if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount)) 663218885Sdim if (BECst->getValue()->getValue() == 0) 664218885Sdim return false; 665221345Sdim 666218885Sdim // We require target data for now. 667249423Sdim if (!getDataLayout()) 668249423Sdim return false; 669218885Sdim 670249423Sdim // set DT 671249423Sdim (void)getDominatorTree(); 672249423Sdim 673218885Sdim LoopInfo &LI = getAnalysis<LoopInfo>(); 674218885Sdim TLI = &getAnalysis<TargetLibraryInfo>(); 675221345Sdim 676249423Sdim // set TLI 677249423Sdim (void)getTargetLibraryInfo(); 678249423Sdim 679218885Sdim SmallVector<BasicBlock*, 8> ExitBlocks; 680218885Sdim CurLoop->getUniqueExitBlocks(ExitBlocks); 681218885Sdim 682218885Sdim DEBUG(dbgs() << "loop-idiom Scanning: F[" 683249423Sdim << CurLoop->getHeader()->getParent()->getName() 684249423Sdim << "] Loop %" << CurLoop->getHeader()->getName() << "\n"); 685221345Sdim 686218885Sdim bool MadeChange = false; 687218885Sdim // Scan all the blocks in the loop that are not in subloops. 688249423Sdim for (Loop::block_iterator BI = CurLoop->block_begin(), 689249423Sdim E = CurLoop->block_end(); BI != E; ++BI) { 690218885Sdim // Ignore blocks in subloops. 691218885Sdim if (LI.getLoopFor(*BI) != CurLoop) 692218885Sdim continue; 693221345Sdim 694218885Sdim MadeChange |= runOnLoopBlock(*BI, BECount, ExitBlocks); 695218885Sdim } 696218885Sdim return MadeChange; 697218885Sdim} 698218885Sdim 699249423Sdimbool LoopIdiomRecognize::runOnNoncountableLoop() { 700249423Sdim NclPopcountRecognize Popcount(*this); 701249423Sdim if (Popcount.recognize()) 702249423Sdim return true; 703249423Sdim 704249423Sdim return false; 705249423Sdim} 706249423Sdim 707249423Sdimbool LoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) { 708249423Sdim CurLoop = L; 709249423Sdim 710249423Sdim // If the loop could not be converted to canonical form, it must have an 711249423Sdim // indirectbr in it, just give up. 712249423Sdim if (!L->getLoopPreheader()) 713249423Sdim return false; 714249423Sdim 715249423Sdim // Disable loop idiom recognition if the function's name is a common idiom. 716249423Sdim StringRef Name = L->getHeader()->getParent()->getName(); 717249423Sdim if (Name == "memset" || Name == "memcpy") 718249423Sdim return false; 719249423Sdim 720249423Sdim SE = &getAnalysis<ScalarEvolution>(); 721249423Sdim if (SE->hasLoopInvariantBackedgeTakenCount(L)) 722249423Sdim return runOnCountableLoop(); 723249423Sdim return runOnNoncountableLoop(); 724249423Sdim} 725249423Sdim 726218885Sdim/// runOnLoopBlock - Process the specified block, which lives in a counted loop 727218885Sdim/// with the specified backedge count. This block is known to be in the current 728218885Sdim/// loop and not in any subloops. 729218885Sdimbool LoopIdiomRecognize::runOnLoopBlock(BasicBlock *BB, const SCEV *BECount, 730218885Sdim SmallVectorImpl<BasicBlock*> &ExitBlocks) { 731218885Sdim // We can only promote stores in this block if they are unconditionally 732218885Sdim // executed in the loop. For a block to be unconditionally executed, it has 733218885Sdim // to dominate all the exit blocks of the loop. Verify this now. 734218885Sdim for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 735218885Sdim if (!DT->dominates(BB, ExitBlocks[i])) 736218885Sdim return false; 737221345Sdim 738218885Sdim bool MadeChange = false; 739218885Sdim for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 740218885Sdim Instruction *Inst = I++; 741218885Sdim // Look for store instructions, which may be optimized to memset/memcpy. 742218885Sdim if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 743218885Sdim WeakVH InstPtr(I); 744218885Sdim if (!processLoopStore(SI, BECount)) continue; 745218885Sdim MadeChange = true; 746221345Sdim 747218885Sdim // If processing the store invalidated our iterator, start over from the 748218885Sdim // top of the block. 749218885Sdim if (InstPtr == 0) 750218885Sdim I = BB->begin(); 751218885Sdim continue; 752218885Sdim } 753221345Sdim 754218885Sdim // Look for memset instructions, which may be optimized to a larger memset. 755218885Sdim if (MemSetInst *MSI = dyn_cast<MemSetInst>(Inst)) { 756218885Sdim WeakVH InstPtr(I); 757218885Sdim if (!processLoopMemSet(MSI, BECount)) continue; 758218885Sdim MadeChange = true; 759221345Sdim 760218885Sdim // If processing the memset invalidated our iterator, start over from the 761218885Sdim // top of the block. 762218885Sdim if (InstPtr == 0) 763218885Sdim I = BB->begin(); 764218885Sdim continue; 765218885Sdim } 766218885Sdim } 767221345Sdim 768218885Sdim return MadeChange; 769218885Sdim} 770218885Sdim 771218885Sdim 772218885Sdim/// processLoopStore - See if this store can be promoted to a memset or memcpy. 773218885Sdimbool LoopIdiomRecognize::processLoopStore(StoreInst *SI, const SCEV *BECount) { 774226633Sdim if (!SI->isSimple()) return false; 775218885Sdim 776218885Sdim Value *StoredVal = SI->getValueOperand(); 777218885Sdim Value *StorePtr = SI->getPointerOperand(); 778221345Sdim 779218885Sdim // Reject stores that are so large that they overflow an unsigned. 780218885Sdim uint64_t SizeInBits = TD->getTypeSizeInBits(StoredVal->getType()); 781218885Sdim if ((SizeInBits & 7) || (SizeInBits >> 32) != 0) 782218885Sdim return false; 783221345Sdim 784218885Sdim // See if the pointer expression is an AddRec like {base,+,1} on the current 785218885Sdim // loop, which indicates a strided store. If we have something else, it's a 786218885Sdim // random store we can't handle. 787218885Sdim const SCEVAddRecExpr *StoreEv = 788218885Sdim dyn_cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr)); 789218885Sdim if (StoreEv == 0 || StoreEv->getLoop() != CurLoop || !StoreEv->isAffine()) 790218885Sdim return false; 791218885Sdim 792218885Sdim // Check to see if the stride matches the size of the store. If so, then we 793218885Sdim // know that every byte is touched in the loop. 794221345Sdim unsigned StoreSize = (unsigned)SizeInBits >> 3; 795218885Sdim const SCEVConstant *Stride = dyn_cast<SCEVConstant>(StoreEv->getOperand(1)); 796221345Sdim 797219077Sdim if (Stride == 0 || StoreSize != Stride->getValue()->getValue()) { 798219077Sdim // TODO: Could also handle negative stride here someday, that will require 799219077Sdim // the validity check in mayLoopAccessLocation to be updated though. 800219077Sdim // Enable this to print exact negative strides. 801219077Sdim if (0 && Stride && StoreSize == -Stride->getValue()->getValue()) { 802219077Sdim dbgs() << "NEGATIVE STRIDE: " << *SI << "\n"; 803219077Sdim dbgs() << "BB: " << *SI->getParent(); 804219077Sdim } 805221345Sdim 806218885Sdim return false; 807219077Sdim } 808218885Sdim 809218885Sdim // See if we can optimize just this store in isolation. 810218885Sdim if (processLoopStridedStore(StorePtr, StoreSize, SI->getAlignment(), 811218885Sdim StoredVal, SI, StoreEv, BECount)) 812218885Sdim return true; 813218885Sdim 814218885Sdim // If the stored value is a strided load in the same loop with the same stride 815218885Sdim // this this may be transformable into a memcpy. This kicks in for stuff like 816218885Sdim // for (i) A[i] = B[i]; 817218885Sdim if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) { 818218885Sdim const SCEVAddRecExpr *LoadEv = 819218885Sdim dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LI->getOperand(0))); 820218885Sdim if (LoadEv && LoadEv->getLoop() == CurLoop && LoadEv->isAffine() && 821226633Sdim StoreEv->getOperand(1) == LoadEv->getOperand(1) && LI->isSimple()) 822218885Sdim if (processLoopStoreOfLoopLoad(SI, StoreSize, StoreEv, LoadEv, BECount)) 823218885Sdim return true; 824218885Sdim } 825218885Sdim //errs() << "UNHANDLED strided store: " << *StoreEv << " - " << *SI << "\n"; 826218885Sdim 827218885Sdim return false; 828218885Sdim} 829218885Sdim 830218885Sdim/// processLoopMemSet - See if this memset can be promoted to a large memset. 831218885Sdimbool LoopIdiomRecognize:: 832218885SdimprocessLoopMemSet(MemSetInst *MSI, const SCEV *BECount) { 833218885Sdim // We can only handle non-volatile memsets with a constant size. 834218885Sdim if (MSI->isVolatile() || !isa<ConstantInt>(MSI->getLength())) return false; 835218885Sdim 836218885Sdim // If we're not allowed to hack on memset, we fail. 837218885Sdim if (!TLI->has(LibFunc::memset)) 838218885Sdim return false; 839221345Sdim 840218885Sdim Value *Pointer = MSI->getDest(); 841221345Sdim 842218885Sdim // See if the pointer expression is an AddRec like {base,+,1} on the current 843218885Sdim // loop, which indicates a strided store. If we have something else, it's a 844218885Sdim // random store we can't handle. 845218885Sdim const SCEVAddRecExpr *Ev = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Pointer)); 846218885Sdim if (Ev == 0 || Ev->getLoop() != CurLoop || !Ev->isAffine()) 847218885Sdim return false; 848218885Sdim 849218885Sdim // Reject memsets that are so large that they overflow an unsigned. 850218885Sdim uint64_t SizeInBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue(); 851218885Sdim if ((SizeInBytes >> 32) != 0) 852218885Sdim return false; 853221345Sdim 854218885Sdim // Check to see if the stride matches the size of the memset. If so, then we 855218885Sdim // know that every byte is touched in the loop. 856218885Sdim const SCEVConstant *Stride = dyn_cast<SCEVConstant>(Ev->getOperand(1)); 857221345Sdim 858218885Sdim // TODO: Could also handle negative stride here someday, that will require the 859218885Sdim // validity check in mayLoopAccessLocation to be updated though. 860218885Sdim if (Stride == 0 || MSI->getLength() != Stride->getValue()) 861218885Sdim return false; 862221345Sdim 863218885Sdim return processLoopStridedStore(Pointer, (unsigned)SizeInBytes, 864218885Sdim MSI->getAlignment(), MSI->getValue(), 865218885Sdim MSI, Ev, BECount); 866218885Sdim} 867218885Sdim 868218885Sdim 869218885Sdim/// mayLoopAccessLocation - Return true if the specified loop might access the 870218885Sdim/// specified pointer location, which is a loop-strided access. The 'Access' 871218885Sdim/// argument specifies what the verboten forms of access are (read or write). 872218885Sdimstatic bool mayLoopAccessLocation(Value *Ptr,AliasAnalysis::ModRefResult Access, 873218885Sdim Loop *L, const SCEV *BECount, 874218885Sdim unsigned StoreSize, AliasAnalysis &AA, 875218885Sdim Instruction *IgnoredStore) { 876218885Sdim // Get the location that may be stored across the loop. Since the access is 877218885Sdim // strided positively through memory, we say that the modified location starts 878218885Sdim // at the pointer and has infinite size. 879218885Sdim uint64_t AccessSize = AliasAnalysis::UnknownSize; 880218885Sdim 881218885Sdim // If the loop iterates a fixed number of times, we can refine the access size 882218885Sdim // to be exactly the size of the memset, which is (BECount+1)*StoreSize 883218885Sdim if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount)) 884218885Sdim AccessSize = (BECst->getValue()->getZExtValue()+1)*StoreSize; 885221345Sdim 886218885Sdim // TODO: For this to be really effective, we have to dive into the pointer 887218885Sdim // operand in the store. Store to &A[i] of 100 will always return may alias 888218885Sdim // with store of &A[100], we need to StoreLoc to be "A" with size of 100, 889218885Sdim // which will then no-alias a store to &A[100]. 890218885Sdim AliasAnalysis::Location StoreLoc(Ptr, AccessSize); 891218885Sdim 892218885Sdim for (Loop::block_iterator BI = L->block_begin(), E = L->block_end(); BI != E; 893218885Sdim ++BI) 894218885Sdim for (BasicBlock::iterator I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I) 895218885Sdim if (&*I != IgnoredStore && 896218885Sdim (AA.getModRefInfo(I, StoreLoc) & Access)) 897218885Sdim return true; 898218885Sdim 899218885Sdim return false; 900218885Sdim} 901218885Sdim 902218885Sdim/// getMemSetPatternValue - If a strided store of the specified value is safe to 903218885Sdim/// turn into a memset_pattern16, return a ConstantArray of 16 bytes that should 904218885Sdim/// be passed in. Otherwise, return null. 905218885Sdim/// 906218885Sdim/// Note that we don't ever attempt to use memset_pattern8 or 4, because these 907218885Sdim/// just replicate their input array and then pass on to memset_pattern16. 908243830Sdimstatic Constant *getMemSetPatternValue(Value *V, const DataLayout &TD) { 909218885Sdim // If the value isn't a constant, we can't promote it to being in a constant 910218885Sdim // array. We could theoretically do a store to an alloca or something, but 911218885Sdim // that doesn't seem worthwhile. 912218885Sdim Constant *C = dyn_cast<Constant>(V); 913218885Sdim if (C == 0) return 0; 914221345Sdim 915218885Sdim // Only handle simple values that are a power of two bytes in size. 916218885Sdim uint64_t Size = TD.getTypeSizeInBits(V->getType()); 917218885Sdim if (Size == 0 || (Size & 7) || (Size & (Size-1))) 918218885Sdim return 0; 919221345Sdim 920218885Sdim // Don't care enough about darwin/ppc to implement this. 921218885Sdim if (TD.isBigEndian()) 922218885Sdim return 0; 923218885Sdim 924218885Sdim // Convert to size in bytes. 925218885Sdim Size /= 8; 926218885Sdim 927218885Sdim // TODO: If CI is larger than 16-bytes, we can try slicing it in half to see 928218885Sdim // if the top and bottom are the same (e.g. for vectors and large integers). 929218885Sdim if (Size > 16) return 0; 930221345Sdim 931218885Sdim // If the constant is exactly 16 bytes, just use it. 932218885Sdim if (Size == 16) return C; 933218885Sdim 934218885Sdim // Otherwise, we'll use an array of the constants. 935218885Sdim unsigned ArraySize = 16/Size; 936218885Sdim ArrayType *AT = ArrayType::get(V->getType(), ArraySize); 937218885Sdim return ConstantArray::get(AT, std::vector<Constant*>(ArraySize, C)); 938218885Sdim} 939218885Sdim 940218885Sdim 941218885Sdim/// processLoopStridedStore - We see a strided store of some value. If we can 942218885Sdim/// transform this into a memset or memset_pattern in the loop preheader, do so. 943218885Sdimbool LoopIdiomRecognize:: 944218885SdimprocessLoopStridedStore(Value *DestPtr, unsigned StoreSize, 945218885Sdim unsigned StoreAlignment, Value *StoredVal, 946218885Sdim Instruction *TheStore, const SCEVAddRecExpr *Ev, 947218885Sdim const SCEV *BECount) { 948221345Sdim 949218885Sdim // If the stored value is a byte-wise value (like i32 -1), then it may be 950218885Sdim // turned into a memset of i8 -1, assuming that all the consecutive bytes 951218885Sdim // are stored. A store of i32 0x01020304 can never be turned into a memset, 952218885Sdim // but it can be turned into memset_pattern if the target supports it. 953218885Sdim Value *SplatValue = isBytewiseValue(StoredVal); 954218885Sdim Constant *PatternValue = 0; 955221345Sdim 956218885Sdim // If we're allowed to form a memset, and the stored value would be acceptable 957218885Sdim // for memset, use it. 958218885Sdim if (SplatValue && TLI->has(LibFunc::memset) && 959218885Sdim // Verify that the stored value is loop invariant. If not, we can't 960218885Sdim // promote the memset. 961218885Sdim CurLoop->isLoopInvariant(SplatValue)) { 962218885Sdim // Keep and use SplatValue. 963218885Sdim PatternValue = 0; 964218885Sdim } else if (TLI->has(LibFunc::memset_pattern16) && 965218885Sdim (PatternValue = getMemSetPatternValue(StoredVal, *TD))) { 966218885Sdim // It looks like we can use PatternValue! 967218885Sdim SplatValue = 0; 968218885Sdim } else { 969218885Sdim // Otherwise, this isn't an idiom we can transform. For example, we can't 970226633Sdim // do anything with a 3-byte store. 971218885Sdim return false; 972218885Sdim } 973221345Sdim 974223017Sdim // The trip count of the loop and the base pointer of the addrec SCEV is 975223017Sdim // guaranteed to be loop invariant, which means that it should dominate the 976223017Sdim // header. This allows us to insert code for it in the preheader. 977223017Sdim BasicBlock *Preheader = CurLoop->getLoopPreheader(); 978223017Sdim IRBuilder<> Builder(Preheader->getTerminator()); 979224145Sdim SCEVExpander Expander(*SE, "loop-idiom"); 980224145Sdim 981218885Sdim // Okay, we have a strided store "p[i]" of a splattable value. We can turn 982218885Sdim // this into a memset in the loop preheader now if we want. However, this 983218885Sdim // would be unsafe to do if there is anything else in the loop that may read 984223017Sdim // or write to the aliased location. Check for any overlap by generating the 985223017Sdim // base pointer and checking the region. 986218885Sdim unsigned AddrSpace = cast<PointerType>(DestPtr->getType())->getAddressSpace(); 987221345Sdim Value *BasePtr = 988218885Sdim Expander.expandCodeFor(Ev->getStart(), Builder.getInt8PtrTy(AddrSpace), 989218885Sdim Preheader->getTerminator()); 990221345Sdim 991223017Sdim 992223017Sdim if (mayLoopAccessLocation(BasePtr, AliasAnalysis::ModRef, 993223017Sdim CurLoop, BECount, 994223017Sdim StoreSize, getAnalysis<AliasAnalysis>(), TheStore)){ 995223017Sdim Expander.clear(); 996223017Sdim // If we generated new code for the base pointer, clean up. 997243830Sdim deleteIfDeadInstruction(BasePtr, *SE, TLI); 998223017Sdim return false; 999223017Sdim } 1000224145Sdim 1001223017Sdim // Okay, everything looks good, insert the memset. 1002223017Sdim 1003218885Sdim // The # stored bytes is (BECount+1)*Size. Expand the trip count out to 1004218885Sdim // pointer size if it isn't already. 1005226633Sdim Type *IntPtr = TD->getIntPtrType(DestPtr->getContext()); 1006218885Sdim BECount = SE->getTruncateOrZeroExtend(BECount, IntPtr); 1007221345Sdim 1008218885Sdim const SCEV *NumBytesS = SE->getAddExpr(BECount, SE->getConstant(IntPtr, 1), 1009221345Sdim SCEV::FlagNUW); 1010218885Sdim if (StoreSize != 1) 1011218885Sdim NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtr, StoreSize), 1012221345Sdim SCEV::FlagNUW); 1013221345Sdim 1014221345Sdim Value *NumBytes = 1015218885Sdim Expander.expandCodeFor(NumBytesS, IntPtr, Preheader->getTerminator()); 1016221345Sdim 1017221345Sdim CallInst *NewCall; 1018218885Sdim if (SplatValue) 1019218885Sdim NewCall = Builder.CreateMemSet(BasePtr, SplatValue,NumBytes,StoreAlignment); 1020218885Sdim else { 1021218885Sdim Module *M = TheStore->getParent()->getParent()->getParent(); 1022218885Sdim Value *MSP = M->getOrInsertFunction("memset_pattern16", 1023218885Sdim Builder.getVoidTy(), 1024221345Sdim Builder.getInt8PtrTy(), 1025218885Sdim Builder.getInt8PtrTy(), IntPtr, 1026218885Sdim (void*)0); 1027221345Sdim 1028218885Sdim // Otherwise we should form a memset_pattern16. PatternValue is known to be 1029218885Sdim // an constant array of 16-bytes. Plop the value into a mergable global. 1030218885Sdim GlobalVariable *GV = new GlobalVariable(*M, PatternValue->getType(), true, 1031218885Sdim GlobalValue::InternalLinkage, 1032218885Sdim PatternValue, ".memset_pattern"); 1033218885Sdim GV->setUnnamedAddr(true); // Ok to merge these. 1034218885Sdim GV->setAlignment(16); 1035218885Sdim Value *PatternPtr = ConstantExpr::getBitCast(GV, Builder.getInt8PtrTy()); 1036218885Sdim NewCall = Builder.CreateCall3(MSP, BasePtr, PatternPtr, NumBytes); 1037218885Sdim } 1038221345Sdim 1039218885Sdim DEBUG(dbgs() << " Formed memset: " << *NewCall << "\n" 1040218885Sdim << " from store to: " << *Ev << " at: " << *TheStore << "\n"); 1041221345Sdim NewCall->setDebugLoc(TheStore->getDebugLoc()); 1042221345Sdim 1043218885Sdim // Okay, the memset has been formed. Zap the original store and anything that 1044218885Sdim // feeds into it. 1045243830Sdim deleteDeadInstruction(TheStore, *SE, TLI); 1046218885Sdim ++NumMemSet; 1047218885Sdim return true; 1048218885Sdim} 1049218885Sdim 1050218885Sdim/// processLoopStoreOfLoopLoad - We see a strided store whose value is a 1051218885Sdim/// same-strided load. 1052218885Sdimbool LoopIdiomRecognize:: 1053218885SdimprocessLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize, 1054218885Sdim const SCEVAddRecExpr *StoreEv, 1055218885Sdim const SCEVAddRecExpr *LoadEv, 1056218885Sdim const SCEV *BECount) { 1057218885Sdim // If we're not allowed to form memcpy, we fail. 1058218885Sdim if (!TLI->has(LibFunc::memcpy)) 1059218885Sdim return false; 1060221345Sdim 1061218885Sdim LoadInst *LI = cast<LoadInst>(SI->getValueOperand()); 1062221345Sdim 1063223017Sdim // The trip count of the loop and the base pointer of the addrec SCEV is 1064223017Sdim // guaranteed to be loop invariant, which means that it should dominate the 1065223017Sdim // header. This allows us to insert code for it in the preheader. 1066223017Sdim BasicBlock *Preheader = CurLoop->getLoopPreheader(); 1067223017Sdim IRBuilder<> Builder(Preheader->getTerminator()); 1068224145Sdim SCEVExpander Expander(*SE, "loop-idiom"); 1069224145Sdim 1070218885Sdim // Okay, we have a strided store "p[i]" of a loaded value. We can turn 1071218885Sdim // this into a memcpy in the loop preheader now if we want. However, this 1072218885Sdim // would be unsafe to do if there is anything else in the loop that may read 1073223017Sdim // or write the memory region we're storing to. This includes the load that 1074223017Sdim // feeds the stores. Check for an alias by generating the base address and 1075223017Sdim // checking everything. 1076223017Sdim Value *StoreBasePtr = 1077223017Sdim Expander.expandCodeFor(StoreEv->getStart(), 1078223017Sdim Builder.getInt8PtrTy(SI->getPointerAddressSpace()), 1079223017Sdim Preheader->getTerminator()); 1080224145Sdim 1081223017Sdim if (mayLoopAccessLocation(StoreBasePtr, AliasAnalysis::ModRef, 1082218885Sdim CurLoop, BECount, StoreSize, 1083223017Sdim getAnalysis<AliasAnalysis>(), SI)) { 1084223017Sdim Expander.clear(); 1085223017Sdim // If we generated new code for the base pointer, clean up. 1086243830Sdim deleteIfDeadInstruction(StoreBasePtr, *SE, TLI); 1087218885Sdim return false; 1088223017Sdim } 1089218885Sdim 1090218885Sdim // For a memcpy, we have to make sure that the input array is not being 1091218885Sdim // mutated by the loop. 1092221345Sdim Value *LoadBasePtr = 1093218885Sdim Expander.expandCodeFor(LoadEv->getStart(), 1094218885Sdim Builder.getInt8PtrTy(LI->getPointerAddressSpace()), 1095218885Sdim Preheader->getTerminator()); 1096221345Sdim 1097223017Sdim if (mayLoopAccessLocation(LoadBasePtr, AliasAnalysis::Mod, CurLoop, BECount, 1098223017Sdim StoreSize, getAnalysis<AliasAnalysis>(), SI)) { 1099223017Sdim Expander.clear(); 1100223017Sdim // If we generated new code for the base pointer, clean up. 1101243830Sdim deleteIfDeadInstruction(LoadBasePtr, *SE, TLI); 1102243830Sdim deleteIfDeadInstruction(StoreBasePtr, *SE, TLI); 1103223017Sdim return false; 1104223017Sdim } 1105224145Sdim 1106223017Sdim // Okay, everything is safe, we can transform this! 1107223017Sdim 1108224145Sdim 1109218885Sdim // The # stored bytes is (BECount+1)*Size. Expand the trip count out to 1110218885Sdim // pointer size if it isn't already. 1111226633Sdim Type *IntPtr = TD->getIntPtrType(SI->getContext()); 1112218885Sdim BECount = SE->getTruncateOrZeroExtend(BECount, IntPtr); 1113221345Sdim 1114218885Sdim const SCEV *NumBytesS = SE->getAddExpr(BECount, SE->getConstant(IntPtr, 1), 1115221345Sdim SCEV::FlagNUW); 1116218885Sdim if (StoreSize != 1) 1117218885Sdim NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtr, StoreSize), 1118221345Sdim SCEV::FlagNUW); 1119221345Sdim 1120218885Sdim Value *NumBytes = 1121218885Sdim Expander.expandCodeFor(NumBytesS, IntPtr, Preheader->getTerminator()); 1122221345Sdim 1123223017Sdim CallInst *NewCall = 1124218885Sdim Builder.CreateMemCpy(StoreBasePtr, LoadBasePtr, NumBytes, 1125218885Sdim std::min(SI->getAlignment(), LI->getAlignment())); 1126223017Sdim NewCall->setDebugLoc(SI->getDebugLoc()); 1127221345Sdim 1128218885Sdim DEBUG(dbgs() << " Formed memcpy: " << *NewCall << "\n" 1129218885Sdim << " from load ptr=" << *LoadEv << " at: " << *LI << "\n" 1130218885Sdim << " from store ptr=" << *StoreEv << " at: " << *SI << "\n"); 1131221345Sdim 1132224145Sdim 1133218885Sdim // Okay, the memset has been formed. Zap the original store and anything that 1134218885Sdim // feeds into it. 1135243830Sdim deleteDeadInstruction(SI, *SE, TLI); 1136218885Sdim ++NumMemCpy; 1137218885Sdim return true; 1138218885Sdim} 1139