- // Step 1: Insert the ctpop instruction at the end of the precondition block
- IRBuilderTy Builder(PreCondBr);
- Value *PopCnt, *PopCntZext, *NewCount, *TripCnt;
- {
- PopCnt = createPopcntIntrinsic(Builder, Var, DL);
- NewCount = PopCntZext =
- Builder.CreateZExtOrTrunc(PopCnt, cast<IntegerType>(CntPhi->getType()));
-
- if (NewCount != PopCnt)
- (cast<Instruction>(NewCount))->setDebugLoc(DL);
-
- // TripCnt is exactly the number of iterations the loop has
- TripCnt = NewCount;
-
- // If the popoulation counter's initial value is not zero, insert Add Inst.
- Value *CntInitVal = CntPhi->getIncomingValueForBlock(PreHead);
- ConstantInt *InitConst = dyn_cast<ConstantInt>(CntInitVal);
- if (!InitConst || !InitConst->isZero()) {
- NewCount = Builder.CreateAdd(NewCount, CntInitVal);
- (cast<Instruction>(NewCount))->setDebugLoc(DL);
- }
- }
-
- // Step 2: Replace the precondition from "if(x == 0) goto loop-exit" to
- // "if(NewCount == 0) loop-exit". Withtout this change, the intrinsic
- // function would be partial dead code, and downstream passes will drag
- // it back from the precondition block to the preheader.
- {
- ICmpInst *PreCond = cast<ICmpInst>(PreCondBr->getCondition());
-
- Value *Opnd0 = PopCntZext;
- Value *Opnd1 = ConstantInt::get(PopCntZext->getType(), 0);
- if (PreCond->getOperand(0) != Var)
- std::swap(Opnd0, Opnd1);
-
- ICmpInst *NewPreCond =
- cast<ICmpInst>(Builder.CreateICmp(PreCond->getPredicate(), Opnd0, Opnd1));
- PreCond->replaceAllUsesWith(NewPreCond);
-
- deleteDeadInstruction(PreCond, *SE, TLI);
- }
-
- // Step 3: Note that the population count is exactly the trip count of the
- // loop in question, which enble us to to convert the loop from noncountable
- // loop into a countable one. The benefit is twofold:
- //
- // - If the loop only counts population, the entire loop become dead after
- // the transformation. It is lots easier to prove a countable loop dead
- // than to prove a noncountable one. (In some C dialects, a infite loop
- // isn't dead even if it computes nothing useful. In general, DCE needs
- // to prove a noncountable loop finite before safely delete it.)
- //
- // - If the loop also performs something else, it remains alive.
- // Since it is transformed to countable form, it can be aggressively
- // optimized by some optimizations which are in general not applicable
- // to a noncountable loop.
- //
- // After this step, this loop (conceptually) would look like following:
- // newcnt = __builtin_ctpop(x);
- // t = newcnt;
- // if (x)
- // do { cnt++; x &= x-1; t--) } while (t > 0);
- BasicBlock *Body = *(CurLoop->block_begin());
- {
- BranchInst *LbBr = LIRUtil::getBranch(Body);
- ICmpInst *LbCond = cast<ICmpInst>(LbBr->getCondition());
- Type *Ty = TripCnt->getType();
-
- PHINode *TcPhi = PHINode::Create(Ty, 2, "tcphi", Body->begin());
-
- Builder.SetInsertPoint(LbCond);
- Value *Opnd1 = cast<Value>(TcPhi);
- Value *Opnd2 = cast<Value>(ConstantInt::get(Ty, 1));
- Instruction *TcDec =
- cast<Instruction>(Builder.CreateSub(Opnd1, Opnd2, "tcdec", false, true));
-
- TcPhi->addIncoming(TripCnt, PreHead);
- TcPhi->addIncoming(TcDec, Body);
-
- CmpInst::Predicate Pred = (LbBr->getSuccessor(0) == Body) ?
- CmpInst::ICMP_UGT : CmpInst::ICMP_SLE;
- LbCond->setPredicate(Pred);
- LbCond->setOperand(0, TcDec);
- LbCond->setOperand(1, cast<Value>(ConstantInt::get(Ty, 0)));
- }
-
- // Step 4: All the references to the original population counter outside
- // the loop are replaced with the NewCount -- the value returned from
- // __builtin_ctpop().
- {
- SmallVector<Value *, 4> CntUses;
- for (Value::use_iterator I = CntInst->use_begin(), E = CntInst->use_end();
- I != E; I++) {
- if (cast<Instruction>(*I)->getParent() != Body)
- CntUses.push_back(*I);
- }
- for (unsigned Idx = 0; Idx < CntUses.size(); Idx++) {
- (cast<Instruction>(CntUses[Idx]))->replaceUsesOfWith(CntInst, NewCount);
- }
- }
-
- // step 5: Forget the "non-computable" trip-count SCEV associated with the
- // loop. The loop would otherwise not be deleted even if it becomes empty.
- SE->forgetLoop(CurLoop);
-}
-
-CallInst *NclPopcountRecognize::createPopcntIntrinsic(IRBuilderTy &IRBuilder,
- Value *Val, DebugLoc DL) {
- Value *Ops[] = { Val };
- Type *Tys[] = { Val->getType() };
-
- Module *M = (*(CurLoop->block_begin()))->getParent()->getParent();
- Value *Func = Intrinsic::getDeclaration(M, Intrinsic::ctpop, Tys);
- CallInst *CI = IRBuilder.CreateCall(Func, Ops);
- CI->setDebugLoc(DL);
-
- return CI;
-}
-
-/// recognize - detect population count idiom in a non-countable loop. If
-/// detected, transform the relevant code to popcount intrinsic function
-/// call, and return true; otherwise, return false.
-bool NclPopcountRecognize::recognize() {
-
- if (!LIR.getTargetTransformInfo())
- return false;
-
- LIR.getScalarEvolution();
-
- if (!preliminaryScreen())
- return false;
-
- Instruction *CntInst;
- PHINode *CntPhi;
- Value *Val;
- if (!detectIdiom(CntInst, CntPhi, Val))
- return false;
-
- transform(CntInst, CntPhi, Val);
- return true;
-}
-
-//===----------------------------------------------------------------------===//
-//
-// Implementation of LoopIdiomRecognize
-//
-//===----------------------------------------------------------------------===//
-
-bool LoopIdiomRecognize::runOnCountableLoop() {
- const SCEV *BECount = SE->getBackedgeTakenCount(CurLoop);
- if (isa<SCEVCouldNotCompute>(BECount)) return false;
-
- // If this loop executes exactly one time, then it should be peeled, not
- // optimized by this pass.
- if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount))
- if (BECst->getValue()->getValue() == 0)
- return false;
-
- // We require target data for now.
- if (!getDataLayout())
- return false;
-
- // set DT
- (void)getDominatorTree();
-
- LoopInfo &LI = getAnalysis<LoopInfo>();
- TLI = &getAnalysis<TargetLibraryInfo>();
-
- // set TLI
- (void)getTargetLibraryInfo();
-
- SmallVector<BasicBlock*, 8> ExitBlocks;
- CurLoop->getUniqueExitBlocks(ExitBlocks);
-
- DEBUG(dbgs() << "loop-idiom Scanning: F["
- << CurLoop->getHeader()->getParent()->getName()
- << "] Loop %" << CurLoop->getHeader()->getName() << "\n");
-
- bool MadeChange = false;
- // Scan all the blocks in the loop that are not in subloops.
- for (Loop::block_iterator BI = CurLoop->block_begin(),
- E = CurLoop->block_end(); BI != E; ++BI) {
- // Ignore blocks in subloops.
- if (LI.getLoopFor(*BI) != CurLoop)
- continue;
-
- MadeChange |= runOnLoopBlock(*BI, BECount, ExitBlocks);
- }
- return MadeChange;
-}
-
-bool LoopIdiomRecognize::runOnNoncountableLoop() {
- NclPopcountRecognize Popcount(*this);
- if (Popcount.recognize())
- return true;
-
- return false;
-}
-
-bool LoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) {
- CurLoop = L;
-
- // If the loop could not be converted to canonical form, it must have an
- // indirectbr in it, just give up.
- if (!L->getLoopPreheader())
- return false;
-
- // Disable loop idiom recognition if the function's name is a common idiom.
- StringRef Name = L->getHeader()->getParent()->getName();
- if (Name == "memset" || Name == "memcpy")
- return false;
-
- SE = &getAnalysis<ScalarEvolution>();
- if (SE->hasLoopInvariantBackedgeTakenCount(L))
- return runOnCountableLoop();
- return runOnNoncountableLoop();
-}
-
-/// runOnLoopBlock - Process the specified block, which lives in a counted loop
-/// with the specified backedge count. This block is known to be in the current
-/// loop and not in any subloops.
-bool LoopIdiomRecognize::runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
- SmallVectorImpl<BasicBlock*> &ExitBlocks) {
- // We can only promote stores in this block if they are unconditionally
- // executed in the loop. For a block to be unconditionally executed, it has
- // to dominate all the exit blocks of the loop. Verify this now.
- for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
- if (!DT->dominates(BB, ExitBlocks[i]))
- return false;
-
- bool MadeChange = false;
- for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
- Instruction *Inst = I++;
- // Look for store instructions, which may be optimized to memset/memcpy.
- if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
- WeakVH InstPtr(I);
- if (!processLoopStore(SI, BECount)) continue;
- MadeChange = true;
-
- // If processing the store invalidated our iterator, start over from the
- // top of the block.
- if (InstPtr == 0)
- I = BB->begin();
- continue;
- }
-
- // Look for memset instructions, which may be optimized to a larger memset.
- if (MemSetInst *MSI = dyn_cast<MemSetInst>(Inst)) {
- WeakVH InstPtr(I);
- if (!processLoopMemSet(MSI, BECount)) continue;
- MadeChange = true;
-
- // If processing the memset invalidated our iterator, start over from the
- // top of the block.
- if (InstPtr == 0)
- I = BB->begin();
- continue;
- }
- }
-
- return MadeChange;
-}
-
-
-/// processLoopStore - See if this store can be promoted to a memset or memcpy.
-bool LoopIdiomRecognize::processLoopStore(StoreInst *SI, const SCEV *BECount) {
- if (!SI->isSimple()) return false;
-
- Value *StoredVal = SI->getValueOperand();
- Value *StorePtr = SI->getPointerOperand();
-
- // Reject stores that are so large that they overflow an unsigned.
- uint64_t SizeInBits = TD->getTypeSizeInBits(StoredVal->getType());
- if ((SizeInBits & 7) || (SizeInBits >> 32) != 0)
- return false;
-
- // See if the pointer expression is an AddRec like {base,+,1} on the current
- // loop, which indicates a strided store. If we have something else, it's a
- // random store we can't handle.
- const SCEVAddRecExpr *StoreEv =
- dyn_cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
- if (StoreEv == 0 || StoreEv->getLoop() != CurLoop || !StoreEv->isAffine())
- return false;
-
- // Check to see if the stride matches the size of the store. If so, then we
- // know that every byte is touched in the loop.
- unsigned StoreSize = (unsigned)SizeInBits >> 3;
- const SCEVConstant *Stride = dyn_cast<SCEVConstant>(StoreEv->getOperand(1));
-
- if (Stride == 0 || StoreSize != Stride->getValue()->getValue()) {
- // TODO: Could also handle negative stride here someday, that will require
- // the validity check in mayLoopAccessLocation to be updated though.
- // Enable this to print exact negative strides.
- if (0 && Stride && StoreSize == -Stride->getValue()->getValue()) {
- dbgs() << "NEGATIVE STRIDE: " << *SI << "\n";
- dbgs() << "BB: " << *SI->getParent();
- }
-
- return false;
- }
-
- // See if we can optimize just this store in isolation.
- if (processLoopStridedStore(StorePtr, StoreSize, SI->getAlignment(),
- StoredVal, SI, StoreEv, BECount))
- return true;
-
- // If the stored value is a strided load in the same loop with the same stride
- // this this may be transformable into a memcpy. This kicks in for stuff like
- // for (i) A[i] = B[i];
- if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
- const SCEVAddRecExpr *LoadEv =
- dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LI->getOperand(0)));
- if (LoadEv && LoadEv->getLoop() == CurLoop && LoadEv->isAffine() &&
- StoreEv->getOperand(1) == LoadEv->getOperand(1) && LI->isSimple())
- if (processLoopStoreOfLoopLoad(SI, StoreSize, StoreEv, LoadEv, BECount))
- return true;
- }
- //errs() << "UNHANDLED strided store: " << *StoreEv << " - " << *SI << "\n";
-
- return false;
-}
-
-/// processLoopMemSet - See if this memset can be promoted to a large memset.
-bool LoopIdiomRecognize::
-processLoopMemSet(MemSetInst *MSI, const SCEV *BECount) {
- // We can only handle non-volatile memsets with a constant size.
- if (MSI->isVolatile() || !isa<ConstantInt>(MSI->getLength())) return false;
-
- // If we're not allowed to hack on memset, we fail.
- if (!TLI->has(LibFunc::memset))
- return false;
-
- Value *Pointer = MSI->getDest();