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
}
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.
Loop *getLoop() const { return CurLoop; }
private:
- bool runOnNoncountableLoop();
+ /// \name Countable Loop Idiom Handling
+ /// @{
+
bool runOnCountableLoop();
+ 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);
+
+ /// @}
+ /// \name Noncountable Loop Idiom Handling
+ /// @{
+
+ bool runOnNoncountableLoop();
+
+ /// @}
};
} // End anonymous namespace.
RecursivelyDeleteTriviallyDeadInstructions(Op, TLI);
}
-//===----------------------------------------------------------------------===//
-//
-// Implementation of LIRUtil
-//
-//===----------------------------------------------------------------------===//
-
-// This function will return true iff the given block contains nothing but goto.
-// A typical usage of this function is to check if the preheader function is
-// "almost" empty such that generated intrinsic functions can be moved across
-// the preheader and be placed at the end of the precondition block without
-// the concern of breaking data dependence.
-bool LIRUtil::isAlmostEmpty(BasicBlock *BB) {
- if (BranchInst *Br = getBranch(BB)) {
- return Br->isUnconditional() && Br == BB->begin();
- }
- return false;
-}
-
-BasicBlock *LIRUtil::getPrecondBb(BasicBlock *PreHead) {
- if (BasicBlock *BB = PreHead->getSinglePredecessor()) {
- BranchInst *Br = getBranch(BB);
- return Br && Br->isConditional() ? BB : nullptr;
- }
- return nullptr;
-}
-
//===----------------------------------------------------------------------===//
//
// Implementation of NclPopcountRecognize
return false;
}
- // It should have a preheader containing nothing but a goto instruction.
- BasicBlock *PreHead = CurLoop->getLoopPreheader();
- if (!PreHead || !LIRUtil::isAlmostEmpty(PreHead))
+ // It should have a preheader containing nothing but an unconditional branch.
+ BasicBlock *PH = CurLoop->getLoopPreheader();
+ if (!PH)
+ return false;
+ if (&PH->front() != PH->getTerminator())
+ return false;
+ auto *EntryBI = dyn_cast<BranchInst>(PH->getTerminator());
+ if (!EntryBI || EntryBI->isConditional())
return false;
// It should have a precondition block where the generated popcount instrinsic
- // function will be inserted.
- PreCondBB = LIRUtil::getPrecondBb(PreHead);
+ // function can be inserted.
+ PreCondBB = PH->getSinglePredecessor();
if (!PreCondBB)
return false;
+ auto *PreCondBI = dyn_cast<BranchInst>(PreCondBB->getTerminator());
+ if (!PreCondBI || PreCondBI->isUnconditional())
+ return false;
return true;
}
// step 1: Check if the loop-back branch is in desirable form.
{
- if (Value *T = matchCondition(LIRUtil::getBranch(LoopEntry), LoopEntry))
+ if (Value *T = matchCondition(
+ dyn_cast<BranchInst>(LoopEntry->getTerminator()), LoopEntry))
DefX2 = dyn_cast<Instruction>(T);
else
return false;
// step 5: check if the precondition is in this form:
// "if (x != 0) goto loop-head ; else goto somewhere-we-don't-care;"
{
- BranchInst *PreCondBr = LIRUtil::getBranch(PreCondBB);
+ auto *PreCondBr = dyn_cast<BranchInst>(PreCondBB->getTerminator());
Value *T = matchCondition(PreCondBr, CurLoop->getLoopPreheader());
if (T != PhiX->getOperand(0) && T != PhiX->getOperand(1))
return false;
ScalarEvolution *SE = LIR.getScalarEvolution();
TargetLibraryInfo *TLI = LIR.getTargetLibraryInfo();
BasicBlock *PreHead = CurLoop->getLoopPreheader();
- BranchInst *PreCondBr = LIRUtil::getBranch(PreCondBB);
+ auto *PreCondBr = dyn_cast<BranchInst>(PreCondBB->getTerminator());
const DebugLoc DL = CntInst->getDebugLoc();
// Assuming before transformation, the loop is following:
// do { cnt++; x &= x-1; t--) } while (t > 0);
BasicBlock *Body = *(CurLoop->block_begin());
{
- BranchInst *LbBr = LIRUtil::getBranch(Body);
+ auto *LbBr = dyn_cast<BranchInst>(Body->getTerminator());
ICmpInst *LbCond = cast<ICmpInst>(LbBr->getCondition());
Type *Ty = TripCnt->getType();
/// detected, transform the relevant code to popcount intrinsic function
/// call, and return true; otherwise, return false.
bool NclPopcountRecognize::recognize() {
-
if (!LIR.getTargetTransformInfo())
return false;
//
//===----------------------------------------------------------------------===//
+bool LoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) {
+ if (skipOptnoneFunction(L))
+ return false;
+
+ 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();
+}
+
bool LoopIdiomRecognize::runOnCountableLoop() {
const SCEV *BECount = SE->getBackedgeTakenCount(CurLoop);
assert(!isa<SCEVCouldNotCompute>(BECount) &&
return MadeChange;
}
-bool LoopIdiomRecognize::runOnNoncountableLoop() {
- NclPopcountRecognize Popcount(*this);
- if (Popcount.recognize())
- return true;
-
- return false;
-}
-
-bool LoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) {
- if (skipOptnoneFunction(L))
- return false;
-
- 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.
++NumMemCpy;
return true;
}
+
+bool LoopIdiomRecognize::runOnNoncountableLoop() {
+ NclPopcountRecognize Popcount(*this);
+ if (Popcount.recognize())
+ return true;
+
+ return false;
+}