- bool runOnLoop(Loop *L, LPPassManager &LPM);
- bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
- SmallVectorImpl<BasicBlock*> &ExitBlocks);
-
- bool processLoopStore(StoreInst *SI, const SCEV *BECount);
- bool processLoopMemSet(MemSetInst *MSI, const SCEV *BECount);
-
- bool processLoopStridedStore(Value *DestPtr, unsigned StoreSize,
- unsigned StoreAlignment,
- Value *SplatValue, Instruction *TheStore,
- const SCEVAddRecExpr *Ev,
- const SCEV *BECount);
- bool processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize,
- const SCEVAddRecExpr *StoreEv,
- const SCEVAddRecExpr *LoadEv,
- const SCEV *BECount);
-
- /// This transformation requires natural loop information & requires that
- /// loop preheaders be inserted into the CFG.
- ///
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.addRequired<LoopInfo>();
- AU.addPreserved<LoopInfo>();
- AU.addRequiredID(LoopSimplifyID);
- AU.addPreservedID(LoopSimplifyID);
- AU.addRequiredID(LCSSAID);
- AU.addPreservedID(LCSSAID);
- AU.addRequired<AliasAnalysis>();
- AU.addPreserved<AliasAnalysis>();
- AU.addRequired<ScalarEvolution>();
- AU.addPreserved<ScalarEvolution>();
- AU.addPreserved<DominatorTree>();
- AU.addRequired<DominatorTree>();
- AU.addRequired<TargetLibraryInfo>();
- }
- };
-}
+class LoopIdiomRecognize;
+
+/// This class defines some utility functions for loop idiom recognization.
+class LIRUtil {
+public:
+ /// Return true iff the block contains nothing but an uncondition branch
+ /// (aka goto instruction).
+ static bool isAlmostEmpty(BasicBlock *);
+
+ static BranchInst *getBranch(BasicBlock *BB) {
+ return dyn_cast<BranchInst>(BB->getTerminator());
+ }
+
+ /// Derive the precondition block (i.e the block that guards the loop
+ /// preheader) from the given preheader.
+ static BasicBlock *getPrecondBb(BasicBlock *PreHead);
+};
+
+/// This class is to recoginize idioms of population-count conducted in
+/// a noncountable loop. Currently it only recognizes this pattern:
+/// \code
+/// while(x) {cnt++; ...; x &= x - 1; ...}
+/// \endcode
+class NclPopcountRecognize {
+ LoopIdiomRecognize &LIR;
+ Loop *CurLoop;
+ BasicBlock *PreCondBB;
+
+ typedef IRBuilder<> IRBuilderTy;
+
+public:
+ explicit NclPopcountRecognize(LoopIdiomRecognize &TheLIR);
+ bool recognize();
+
+private:
+ /// Take a glimpse of the loop to see if we need to go ahead recoginizing
+ /// the idiom.
+ bool preliminaryScreen();
+
+ /// Check if the given conditional branch is based on the comparison
+ /// between a variable and zero, and if the variable is non-zero, the
+ /// control yields to the loop entry. If the branch matches the behavior,
+ /// the variable involved in the comparion is returned. This function will
+ /// be called to see if the precondition and postcondition of the loop
+ /// are in desirable form.
+ Value *matchCondition(BranchInst *Br, BasicBlock *NonZeroTarget) const;
+
+ /// Return true iff the idiom is detected in the loop. and 1) \p CntInst
+ /// is set to the instruction counting the population bit. 2) \p CntPhi
+ /// is set to the corresponding phi node. 3) \p Var is set to the value
+ /// whose population bits are being counted.
+ bool detectIdiom(Instruction *&CntInst, PHINode *&CntPhi, Value *&Var) const;
+
+ /// Insert ctpop intrinsic function and some obviously dead instructions.
+ void transform(Instruction *CntInst, PHINode *CntPhi, Value *Var);
+
+ /// Create llvm.ctpop.* intrinsic function.
+ CallInst *createPopcntIntrinsic(IRBuilderTy &IRB, Value *Val, DebugLoc DL);
+};
+
+class LoopIdiomRecognize : public LoopPass {
+ Loop *CurLoop;
+ DominatorTree *DT;
+ ScalarEvolution *SE;
+ TargetLibraryInfo *TLI;
+ const TargetTransformInfo *TTI;
+
+public:
+ static char ID;
+ explicit LoopIdiomRecognize() : LoopPass(ID) {
+ initializeLoopIdiomRecognizePass(*PassRegistry::getPassRegistry());
+ DT = nullptr;
+ SE = nullptr;
+ TLI = nullptr;
+ TTI = nullptr;
+ }
+
+ bool runOnLoop(Loop *L, LPPassManager &LPM) override;
+ bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
+ SmallVectorImpl<BasicBlock *> &ExitBlocks);
+
+ bool processLoopStore(StoreInst *SI, const SCEV *BECount);
+ bool processLoopMemSet(MemSetInst *MSI, const SCEV *BECount);
+
+ bool processLoopStridedStore(Value *DestPtr, unsigned StoreSize,
+ unsigned StoreAlignment, Value *SplatValue,
+ Instruction *TheStore, const SCEVAddRecExpr *Ev,
+ const SCEV *BECount);
+ bool processLoopStoreOfLoopLoad(StoreInst *SI, unsigned StoreSize,
+ const SCEVAddRecExpr *StoreEv,
+ const SCEVAddRecExpr *LoadEv,
+ const SCEV *BECount);
+
+ /// This transformation requires natural loop information & requires that
+ /// loop preheaders be inserted into the CFG.
+ ///
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
+ AU.addRequired<LoopInfoWrapperPass>();
+ AU.addPreserved<LoopInfoWrapperPass>();
+ AU.addRequiredID(LoopSimplifyID);
+ AU.addPreservedID(LoopSimplifyID);
+ AU.addRequiredID(LCSSAID);
+ AU.addPreservedID(LCSSAID);
+ AU.addRequired<AliasAnalysis>();
+ AU.addPreserved<AliasAnalysis>();
+ AU.addRequired<ScalarEvolution>();
+ AU.addPreserved<ScalarEvolution>();
+ AU.addPreserved<DominatorTreeWrapperPass>();
+ AU.addRequired<DominatorTreeWrapperPass>();
+ AU.addRequired<TargetLibraryInfoWrapperPass>();
+ AU.addRequired<TargetTransformInfoWrapperPass>();
+ }
+
+ DominatorTree *getDominatorTree() {
+ return DT ? DT
+ : (DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree());
+ }
+
+ ScalarEvolution *getScalarEvolution() {
+ return SE ? SE : (SE = &getAnalysis<ScalarEvolution>());
+ }
+
+ TargetLibraryInfo *getTargetLibraryInfo() {
+ if (!TLI)
+ TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+
+ return TLI;
+ }
+
+ const TargetTransformInfo *getTargetTransformInfo() {
+ return TTI ? TTI
+ : (TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
+ *CurLoop->getHeader()->getParent()));
+ }
+
+ Loop *getLoop() const { return CurLoop; }
+
+private:
+ bool runOnNoncountableLoop();
+ bool runOnCountableLoop();
+};
+
+} // End anonymous namespace.