LoopIdiomRecognize.cpp File Reference (original) (raw)

Go to the source code of this file.

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.

Macros
#define	DEBUG_TYPE "loop-idiom"

Functions
	STATISTIC (NumMemSet, "Number of memset's formed from loop stores")
	STATISTIC (NumMemCpy, "Number of memcpy's formed from loop load+stores")
	STATISTIC (NumMemMove, "Number of memmove's formed from loop load+stores")
	STATISTIC (NumStrLen, "Number of strlen's and wcslen's formed from loop loads")
	STATISTIC (NumShiftUntilBitTest, "Number of uncountable loops recognized as 'shift until bitttest' idiom")
	STATISTIC (NumShiftUntilZero, "Number of uncountable loops recognized as 'shift until zero' idiom")
static void	deleteDeadInstruction (Instruction *I)
static APInt	getStoreStride (const SCEVAddRecExpr *StoreEv)
static Constant *	getMemSetPatternValue (Value V, const DataLayout DL)
	getMemSetPatternValue - If a strided store of the specified value is safe to turn into a memset.patternn intrinsic, return the Constant that should be passed in.
static bool	mayLoopAccessLocation (Value Ptr, ModRefInfo Access, Loop L, const SCEV BECount, const SCEV StoreSizeSCEV, AliasAnalysis &AA, SmallPtrSetImpl< Instruction * > &IgnoredInsts)
	mayLoopAccessLocation - Return true if the specified loop might access the specified pointer location, which is a loop-strided access.
static const SCEV *	getStartForNegStride (const SCEV Start, const SCEV BECount, Type IntPtr, const SCEV StoreSizeSCEV, ScalarEvolution *SE)
static const SCEV *	getNumBytes (const SCEV BECount, Type IntPtr, const SCEV StoreSizeSCEV, Loop CurLoop, const DataLayout DL, ScalarEvolution SE)
	Compute the number of bytes as a SCEV from the backedge taken count.
static Value *	matchCondition (BranchInst BI, BasicBlock LoopEntry, bool JmpOnZero=false)
	Check if the given conditional branch is based on the comparison between a variable and zero, and if the variable is non-zero or zero (JmpOnZero is true), the control yields to the loop entry.
static Value *	matchShiftULTCondition (BranchInst BI, BasicBlock LoopEntry, APInt &Threshold)
	Check if the given conditional branch is based on an unsigned less-than comparison between a variable and a constant, and if the comparison is false the control yields to the loop entry.
static PHINode *	getRecurrenceVar (Value VarX, Instruction DefX, BasicBlock *LoopEntry)
static bool	detectShiftUntilLessThanIdiom (Loop CurLoop, const DataLayout &DL, Intrinsic::ID &IntrinID, Value &InitX, Instruction &CntInst, PHINode &CntPhi, Instruction *&DefX, APInt &Threshold)
	Return true if the idiom is detected in the loop.
static bool	detectPopcountIdiom (Loop CurLoop, BasicBlock PreCondBB, Instruction &CntInst, PHINode &CntPhi, Value *&Var)
	Return true iff the idiom is detected in the loop.
static bool	detectShiftUntilZeroIdiom (Loop CurLoop, const DataLayout &DL, Intrinsic::ID &IntrinID, Value &InitX, Instruction &CntInst, PHINode &CntPhi, Instruction *&DefX)
	Return true if the idiom is detected in the loop.
static CallInst *	createPopcntIntrinsic (IRBuilder<> &IRBuilder, Value *Val, const DebugLoc &DL)
static CallInst *	createFFSIntrinsic (IRBuilder<> &IRBuilder, Value *Val, const DebugLoc &DL, bool ZeroCheck, Intrinsic::ID IID)
template
match_LoopInvariant< Ty >	m_LoopInvariant (const Ty &M, const Loop *L)
	Matches if the value is loop-invariant.
static bool	detectShiftUntilBitTestIdiom (Loop CurLoop, Value &BaseX, Value &BitMask, Value &BitPos, Value &CurrX, Instruction &NextX)
	Return true if the idiom is detected in the loop.
static bool	detectShiftUntilZeroIdiom (Loop CurLoop, ScalarEvolution SE, Instruction &ValShiftedIsZero, Intrinsic::ID &IntrinID, Instruction &IV, Value &Start, Value &Val, const SCEV *&ExtraOffsetExpr, bool &InvertedCond)
	Return true if the idiom is detected in the loop.

Variables
static cl::opt< bool, true >	llvm::DisableLIRPAll ("disable-" DEBUG_TYPE "-all", cl::desc("Options to disable Loop Idiom Recognize Pass."), cl::location(DisableLIRP::All), cl::init(false), cl::ReallyHidden)
static cl::opt< bool, true >	llvm::DisableLIRPMemset ("disable-" DEBUG_TYPE "-memset", cl::desc("Proceed with loop idiom recognize pass, but do " "not convert loop(s) to memset."), cl::location(DisableLIRP::Memset), cl::init(false), cl::ReallyHidden)
static cl::opt< bool, true >	llvm::DisableLIRPMemcpy ("disable-" DEBUG_TYPE "-memcpy", cl::desc("Proceed with loop idiom recognize pass, but do " "not convert loop(s) to memcpy."), cl::location(DisableLIRP::Memcpy), cl::init(false), cl::ReallyHidden)
static cl::opt< bool, true >	llvm::DisableLIRPStrlen ("disable-loop-idiom-strlen", cl::desc("Proceed with loop idiom recognize pass, but do " "not convert loop(s) to strlen."), cl::location(DisableLIRP::Strlen), cl::init(false), cl::ReallyHidden)
static cl::opt< bool, true >	llvm::EnableLIRPWcslen ("disable-loop-idiom-wcslen", cl::desc("Proceed with loop idiom recognize pass, " "enable conversion of loop(s) to wcslen."), cl::location(DisableLIRP::Wcslen), cl::init(false), cl::ReallyHidden)
static cl::opt< bool, true >	llvm::DisableLIRPHashRecognize ("disable-" DEBUG_TYPE "-hashrecognize", cl::desc("Proceed with loop idiom recognize pass, " "but do not optimize CRC loops."), cl::location(DisableLIRP::HashRecognize), cl::init(false), cl::ReallyHidden)
static cl::opt< bool >	llvm::UseLIRCodeSizeHeurs ("use-lir-code-size-heurs", cl::desc("Use loop idiom recognition code size heuristics when compiling " "with -Os/-Oz"), cl::init(true), cl::Hidden)
static cl::opt< bool >	llvm::ForceMemsetPatternIntrinsic ("loop-idiom-force-memset-pattern-intrinsic", cl::desc("Use memset.pattern intrinsic whenever possible"), cl::init(false), cl::Hidden)

◆ DEBUG_TYPE

#define DEBUG_TYPE "loop-idiom"

◆ createFFSIntrinsic()

◆ createPopcntIntrinsic()

◆ deleteDeadInstruction()

◆ detectPopcountIdiom()

Return true iff the idiom is detected in the loop.

Additionally: 1) CntInst is set to the instruction counting the population bit. 2) CntPhi is set to the corresponding phi node. 3) Var is set to the value whose population bits are being counted.

The core idiom we are trying to detect is:

if (x0 != 0)

goto loop-exit

cnt0 = init-val;

do {

x1 = phi (x0, x2);

cnt1 = phi(cnt0, cnt2);

cnt2 = cnt1 + 1;

...

x2 = x1 & (x1 - 1);

...

} while(x != 0);

loop-exit:

Definition at line 2175 of file LoopIdiomRecognize.cpp.

References llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::cast(), llvm::dyn_cast(), llvm::BasicBlock::end(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::BinaryOperator::getOpcode(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), getParent(), getRecurrenceVar(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::isMinusOne(), llvm::ConstantInt::isOne(), llvm::make_range(), matchCondition(), T, and llvm::Value::users().

◆ detectShiftUntilBitTestIdiom()

Return true if the idiom is detected in the loop.

The core idiom we are trying to detect is:

entry:

<...>

%bitmask = shl i32 1, %bitpos

br label %loop

loop:

%x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]

%x.curr.bitmasked = and i32 %x.curr, %bitmask

%x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0

%x.next = shl i32 %x.curr, 1

<...>

br i1 %x.curr.isbitunset, label %loop, label %end

end:

%x.curr.res = phi i32 [ %x.curr, %loop ] <...>

%x.next.res = phi i32 [ %x.next, %loop ] <...>

<...>

Definition at line 2899 of file LoopIdiomRecognize.cpp.

◆ detectShiftUntilLessThanIdiom()

Return true if the idiom is detected in the loop.

Additionally: 1) CntInst is set to the instruction Counting Leading Zeros (CTLZ) or nullptr if there is no such. 2) CntPhi is set to the corresponding phi node or nullptr if there is no such. 3) InitX is set to the value whose CTLZ could be used. 4) DefX is set to the instruction calculating Loop exit condition. 5) Threshold is set to the constant involved in the unsigned less-than comparison.

The core idiom we are trying to detect is:

if (x0 < 2)

goto loop-exit

cnt0 = init-val

do {

x = phi (x0, x.next);

cnt = phi (cnt0, cnt.next)

cnt.next = cnt + 1;

...

x.next = x >> 1;

} while (x >= 4)

loop-exit:

Definition at line 2077 of file LoopIdiomRecognize.cpp.

References llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::cast(), DL, llvm::dyn_cast(), llvm::BasicBlock::end(), llvm::PHINode::getBasicBlockIndex(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), getRecurrenceVar(), llvm::BasicBlock::getTerminator(), llvm::isa(), llvm::ConstantInt::isMinusOne(), llvm::ConstantInt::isOne(), llvm::make_range(), matchShiftULTCondition(), and T.

◆ detectShiftUntilZeroIdiom() [1/2]

Return true if the idiom is detected in the loop.

Additionally: 1) CntInst is set to the instruction Counting Leading Zeros (CTLZ) or nullptr if there is no such. 2) CntPhi is set to the corresponding phi node or nullptr if there is no such. 3) Var is set to the value whose CTLZ could be used. 4) DefX is set to the instruction calculating Loop exit condition.

The core idiom we are trying to detect is:

if (x0 == 0)

goto loop-exit

cnt0 = init-val;

do {

x = phi (x0, x.next);

cnt = phi(cnt0, cnt.next);

cnt.next = cnt + 1;

...

x.next = x >> 1;

...

} while(x.next != 0);

loop-exit:

Definition at line 2308 of file LoopIdiomRecognize.cpp.

References llvm::LoopBase< BlockT, LoopT >::block_begin(), DL, llvm::dyn_cast(), llvm::BasicBlock::end(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), getRecurrenceVar(), llvm::BasicBlock::getTerminator(), llvm::isKnownNonNegative(), llvm::ConstantInt::isMinusOne(), llvm::ConstantInt::isOne(), llvm::Instruction::isShift(), llvm::make_range(), matchCondition(), and T.

◆ detectShiftUntilZeroIdiom() [2/2]

Return true if the idiom is detected in the loop.

The core idiom we are trying to detect is:

entry:

<...>

%start = <...>

%extraoffset = <...>

<...>

br label %for.cond

loop:

%iv = phi i8 [ %start, %entry ], [ %iv.next, %for.cond ]

%nbits = add nsw i8 %iv, %extraoffset

%val.shifted = {{l,a}shr,shl} i8 %val, %nbits

%val.shifted.iszero = icmp eq i8 %val.shifted, 0

%iv.next = add i8 %iv, 1

<...>

br i1 %val.shifted.iszero, label %end, label %loop

%iv.res = phi i8 [ %iv, %loop ] <...>

%nbits.res = phi i8 [ %nbits, %loop ] <...>

%val.shifted.res = phi i8 [ %val.shifted, %loop ] <...>

%val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ] <...>

%iv.next.res = phi i8 [ %iv.next, %loop ] <...>

<...>

Definition at line 3268 of file LoopIdiomRecognize.cpp.

◆ getMemSetPatternValue()

◆ getNumBytes()

◆ getRecurrenceVar()

◆ getStartForNegStride()

◆ getStoreStride()

◆ m_LoopInvariant()

◆ matchCondition()

Check if the given conditional branch is based on the comparison between a variable and zero, and if the variable is non-zero or zero (JmpOnZero is true), the control yields to the loop entry.

If the branch matches the behavior, the variable involved in the comparison is returned. This function will be called to see if the precondition and postcondition of the loop are in desirable form.

Definition at line 1709 of file LoopIdiomRecognize.cpp.

References Cond, llvm::dyn_cast(), llvm::BranchInst::getCondition(), llvm::BranchInst::getSuccessor(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::BranchInst::isConditional(), and std::swap().

Referenced by detectPopcountIdiom(), and detectShiftUntilZeroIdiom().

◆ matchShiftULTCondition()

◆ mayLoopAccessLocation()

mayLoopAccessLocation - Return true if the specified loop might access the specified pointer location, which is a loop-strided access.

The 'Access' argument specifies what the verboten forms of access are (read or write).

Definition at line 975 of file LoopIdiomRecognize.cpp.

References Access, llvm::LocationSize::afterPointer(), B(), llvm::SmallPtrSetImpl< PtrType >::contains(), I, llvm::isModOrRefSet(), llvm::SCEVPatternMatch::m_scev_APInt(), llvm::PatternMatch::match(), llvm::LocationSize::precise(), and llvm::APInt::tryZExtValue().

◆ STATISTIC() [1/6]

STATISTIC	(	NumMemCpy	,
"Number of memcpy's formed from loop load+stores"	)

◆ STATISTIC() [2/6]

STATISTIC	(	NumMemMove	,
"Number of memmove's formed from loop load+stores"	)

◆ STATISTIC() [3/6]

STATISTIC	(	NumMemSet	,
"Number of memset's formed from loop stores"	)

◆ STATISTIC() [4/6]

STATISTIC	(	NumShiftUntilBitTest	,
"Number of uncountable loops recognized as 'shift until bitttest' idiom"	)

◆ STATISTIC() [5/6]

STATISTIC	(	NumShiftUntilZero	,
"Number of uncountable loops recognized as 'shift until zero' idiom"	)

◆ STATISTIC() [6/6]

STATISTIC	(	NumStrLen	,
"Number of strlen's and wcslen's formed from loop loads"	)