LoopIdiomRecognize.cpp File Reference

#include "llvm/Transforms/Scalar/LoopIdiomRecognize.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CmpInstAnalysis.h"
#include "llvm/Analysis/HashRecognize.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/MustExecute.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/InstructionCost.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BuildLibCalls.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>

Go to the source code of this file.

Classes
struct	match_LoopInvariant< SubPattern_t >
	Match loop-invariant value. More...

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<typename Ty>
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 >	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 >	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 >	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 >	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 >	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 >	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 >	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 >	ForceMemsetPatternIntrinsic ("loop-idiom-force-memset-pattern-intrinsic", cl::desc("Use memset.pattern intrinsic whenever possible"), cl::init(false), cl::Hidden)

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-idiom"

Definition at line 96 of file LoopIdiomRecognize.cpp.

Function Documentation

createFFSIntrinsic()

CallInst * createFFSIntrinsic ( IRBuilder<> & IRBuilder, Value * Val, const DebugLoc & DL, bool ZeroCheck, Intrinsic::ID IID )

static

Definition at line 2613 of file LoopIdiomRecognize.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, llvm::IRBuilderBase::CreateIntrinsic(), DL, llvm::IRBuilderBase::getInt1(), llvm::Value::getType(), and llvm::Instruction::setDebugLoc().

createPopcntIntrinsic()

CallInst * createPopcntIntrinsic ( IRBuilder<> & IRBuilder, Value * Val, const DebugLoc & DL )

static

Definition at line 2602 of file LoopIdiomRecognize.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, llvm::IRBuilderBase::CreateIntrinsic(), DL, llvm::Value::getType(), and llvm::Instruction::setDebugLoc().

deleteDeadInstruction()

void deleteDeadInstruction ( Instruction * I )

static

Definition at line 313 of file LoopIdiomRecognize.cpp.

References llvm::PoisonValue::get(), and I.

detectPopcountIdiom()

bool detectPopcountIdiom ( Loop * CurLoop, BasicBlock * PreCondBB, Instruction *& CntInst, PHINode *& CntPhi, Value *& Var )

static

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 // the precondition of the loop
   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 2174 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()

bool detectShiftUntilBitTestIdiom ( Loop * CurLoop, Value *& BaseX, Value *& BitMask, Value *& BitPos, Value *& CurrX, Instruction *& NextX )

static

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 2898 of file LoopIdiomRecognize.cpp.

References assert(), llvm::dbgs(), DEBUG_TYPE, llvm::decomposeBitTestICmp(), llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::CmpInst::getInversePredicate(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::LoopBase< BlockT, LoopT >::getNumBackEdges(), llvm::LoopBase< BlockT, LoopT >::getNumBlocks(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::CmpInst::ICMP_EQ, llvm::ICmpInst::isEquality(), llvm::ICmpInst::isEquality(), llvm::Loop::isLoopInvariant(), LLVM_DEBUG, llvm::PatternMatch::m_BasicBlock(), llvm::PatternMatch::m_Br(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_CombineAnd(), llvm::PatternMatch::m_ICmp(), m_LoopInvariant(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), and std::swap().

detectShiftUntilLessThanIdiom()

bool detectShiftUntilLessThanIdiom ( Loop * CurLoop, const DataLayout & DL, Intrinsic::ID & IntrinID, Value *& InitX, Instruction *& CntInst, PHINode *& CntPhi, Instruction *& DefX, APInt & Threshold )

static

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 // the precondition of the loop
   cnt0 = init-val
   do {
     x = phi (x0, x.next);   //PhiX
     cnt = phi (cnt0, cnt.next)
 
     cnt.next = cnt + 1;
      ...
     x.next = x >> 1;   // DefX
   } while (x >= 4)
loop-exit:

Definition at line 2076 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]

bool detectShiftUntilZeroIdiom ( Loop * CurLoop, const DataLayout & DL, Intrinsic::ID & IntrinID, Value *& InitX, Instruction *& CntInst, PHINode *& CntPhi, Instruction *& DefX )

static

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 // the precondition of the loop
   cnt0 = init-val;
   do {
      x = phi (x0, x.next);   //PhiX
      cnt = phi(cnt0, cnt.next);
 
      cnt.next = cnt + 1;
       ...
      x.next = x >> 1;   // DefX
       ...
   } while(x.next != 0);
 
loop-exit:

Definition at line 2307 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]

bool detectShiftUntilZeroIdiom ( Loop * CurLoop, ScalarEvolution * SE, Instruction *& ValShiftedIsZero, Intrinsic::ID & IntrinID, Instruction *& IV, Value *& Start, Value *& Val, const SCEV *& ExtraOffsetExpr, bool & InvertedCond )

static

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
 
end:
  %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 3253 of file LoopIdiomRecognize.cpp.

References assert(), llvm::dbgs(), DEBUG_TYPE, llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::CmpInst::getInversePredicate(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::ScalarEvolution::getNegativeSCEV(), llvm::LoopBase< BlockT, LoopT >::getNumBackEdges(), llvm::LoopBase< BlockT, LoopT >::getNumBlocks(), llvm::Instruction::getOpcode(), llvm::ScalarEvolution::getSCEV(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::ScalarEvolution::getZero(), llvm::Instruction::hasNoSignedWrap(), llvm::Instruction::hasNoUnsignedWrap(), llvm::CmpInst::ICMP_EQ, llvm::ICmpInst::isEquality(), llvm::ScalarEvolution::isKnownNonNegative(), llvm::isMustProgress(), IV, LLVM_DEBUG, llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_BasicBlock(), llvm::PatternMatch::m_Br(), llvm::PatternMatch::m_c_Add(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Instruction(), m_LoopInvariant(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_Shift(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), and std::swap().

getMemSetPatternValue()

Constant * getMemSetPatternValue ( Value * V, const DataLayout * DL )

static

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.

Otherwise, return null.

TODO this function could allow more constants than it does today (e.g. those over 16 bytes) now it has transitioned to being used for the memset.pattern intrinsic rather than directly the memset_pattern16 libcall.

Definition at line 417 of file LoopIdiomRecognize.cpp.

References llvm::CallingConv::C, DL, llvm::dyn_cast(), llvm::isa(), llvm::Type::isFloatingPointTy(), llvm::Type::isIntOrPtrTy(), and Size.

getNumBytes()

const SCEV * getNumBytes ( const SCEV * BECount, Type * IntPtr, const SCEV * StoreSizeSCEV, Loop * CurLoop, const DataLayout * DL, ScalarEvolution * SE )

static

Compute the number of bytes as a SCEV from the backedge taken count.

This also maps the SCEV into the provided type and tries to handle the computation in a way that will fold cleanly.

Definition at line 1027 of file LoopIdiomRecognize.cpp.

References DL, llvm::SCEV::FlagNUW, llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getTripCountFromExitCount(), and llvm::ScalarEvolution::getTruncateOrZeroExtend().

Referenced by llvm::DebugLocStream::getBytes().

getRecurrenceVar()

PHINode * getRecurrenceVar ( Value * VarX, Instruction * DefX, BasicBlock * LoopEntry )

static

Definition at line 2040 of file LoopIdiomRecognize.cpp.

References llvm::dyn_cast(), and llvm::User::getOperand().

Referenced by detectPopcountIdiom(), detectShiftUntilLessThanIdiom(), and detectShiftUntilZeroIdiom().

getStartForNegStride()

const SCEV * getStartForNegStride ( const SCEV * Start, const SCEV * BECount, Type * IntPtr, const SCEV * StoreSizeSCEV, ScalarEvolution * SE )

static

Definition at line 1009 of file LoopIdiomRecognize.cpp.

References llvm::SCEV::FlagNUW, llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getTruncateOrZeroExtend(), and llvm::SCEV::isOne().

getStoreStride()

APInt getStoreStride ( const SCEVAddRecExpr * StoreEv )

static

Definition at line 404 of file LoopIdiomRecognize.cpp.

References llvm::cast(), llvm::SCEVConstant::getAPInt(), and llvm::SCEVNAryExpr::getOperand().

m_LoopInvariant()

template<typename Ty>

match_LoopInvariant< Ty > m_LoopInvariant ( const Ty & M, const Loop * L )

inline

Matches if the value is loop-invariant.

Definition at line 2872 of file LoopIdiomRecognize.cpp.

Referenced by detectShiftUntilBitTestIdiom(), and detectShiftUntilZeroIdiom().

matchCondition()

Value * matchCondition ( BranchInst * BI, BasicBlock * LoopEntry, bool JmpOnZero = false )

static

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 1708 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()

Value * matchShiftULTCondition ( BranchInst * BI, BasicBlock * LoopEntry, APInt & Threshold )

static

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.

If the branch matches the behaviour, the variable involved in the comparison is returned.

Definition at line 2014 of file LoopIdiomRecognize.cpp.

References Cond, llvm::dyn_cast(), llvm::BranchInst::getCondition(), llvm::BranchInst::getSuccessor(), llvm::ConstantInt::getValue(), llvm::CmpInst::ICMP_ULT, and llvm::BranchInst::isConditional().

Referenced by detectShiftUntilLessThanIdiom().

mayLoopAccessLocation()

bool mayLoopAccessLocation ( Value * Ptr, ModRefInfo Access, Loop * L, const SCEV * BECount, const SCEV * StoreSizeSCEV, AliasAnalysis & AA, SmallPtrSetImpl< Instruction * > & IgnoredInsts )

static

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 971 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(), Ptr, 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"	)

References llvm::DisableLIRP::All.

STATISTIC() [6/6]

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

Variable Documentation

DisableLIRPAll

cl::opt< bool, true > DisableLIRPAll("disable-" DEBUG_TYPE "-all", cl::desc("Options to disable Loop Idiom Recognize Pass."), cl::location(DisableLIRP::All), cl::init(false), cl::ReallyHidden) ( "disable-" DEBUG_TYPE "-all" , cl::desc("Options to disable Loop Idiom Recognize Pass.") , cl::location(DisableLIRP::All) , cl::init(false) , cl::ReallyHidden  )

static

DisableLIRPHashRecognize

cl::opt< bool, true > 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) ( "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

DisableLIRPMemcpy

cl::opt< bool, true > 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) ( "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

DisableLIRPMemset

cl::opt< bool, true > 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) ( "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

DisableLIRPStrlen

cl::opt< bool, true > 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) ( "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

EnableLIRPWcslen

cl::opt< bool, true > 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) ( "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

ForceMemsetPatternIntrinsic

cl::opt< bool > ForceMemsetPatternIntrinsic("loop-idiom-force-memset-pattern-intrinsic", cl::desc("Use memset.pattern intrinsic whenever possible"), cl::init(false), cl::Hidden) ( "loop-idiom-force-memset-pattern-intrinsic" , cl::desc("Use memset.pattern intrinsic whenever possible") , cl::init(false) , cl::Hidden  )

static

UseLIRCodeSizeHeurs

cl::opt< bool > 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) ( "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