LLVM 22.0.0git
|
#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/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 > | 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) |
#define DEBUG_TYPE "loop-idiom" |
Definition at line 95 of file LoopIdiomRecognize.cpp.
|
static |
Definition at line 2439 of file LoopIdiomRecognize.cpp.
References llvm::IRBuilderBase::CreateIntrinsic(), DL, llvm::IRBuilderBase::getInt1(), llvm::Value::getType(), and llvm::Instruction::setDebugLoc().
|
static |
Definition at line 2428 of file LoopIdiomRecognize.cpp.
References llvm::IRBuilderBase::CreateIntrinsic(), DL, llvm::Value::getType(), and llvm::Instruction::setDebugLoc().
|
static |
Definition at line 301 of file LoopIdiomRecognize.cpp.
References llvm::PoisonValue::get(), and I.
|
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:
Definition at line 2000 of file LoopIdiomRecognize.cpp.
References llvm::LoopBase< BlockT, LoopT >::block_begin(), 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(), and llvm::Value::users().
|
static |
Return true if the idiom is detected in the loop.
The core idiom we are trying to detect is:
Definition at line 2724 of file LoopIdiomRecognize.cpp.
References assert(), llvm::dbgs(), DEBUG_TYPE, llvm::decomposeBitTestICmp(), 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::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().
|
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:
Definition at line 1902 of file LoopIdiomRecognize.cpp.
References llvm::LoopBase< BlockT, LoopT >::block_begin(), 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(), Idx, llvm::ConstantInt::isMinusOne(), llvm::ConstantInt::isOne(), llvm::make_range(), and matchShiftULTCondition().
|
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:
Definition at line 2133 of file LoopIdiomRecognize.cpp.
References llvm::LoopBase< BlockT, LoopT >::block_begin(), DL, 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(), and matchCondition().
|
static |
Return true if the idiom is detected in the loop.
The core idiom we are trying to detect is:
Definition at line 3079 of file LoopIdiomRecognize.cpp.
References assert(), llvm::dbgs(), DEBUG_TYPE, 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().
|
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 397 of file LoopIdiomRecognize.cpp.
References llvm::CallingConv::C, DL, llvm::Type::isFloatingPointTy(), llvm::Type::isIntOrPtrTy(), and Size.
|
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 1007 of file LoopIdiomRecognize.cpp.
References llvm::SCEV::FlagNUW, llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getTripCountFromExitCount(), and llvm::ScalarEvolution::getTruncateOrZeroExtend().
Referenced by llvm::DebugLocStream::getBytes().
|
static |
Definition at line 1866 of file LoopIdiomRecognize.cpp.
References llvm::User::getOperand().
Referenced by detectPopcountIdiom(), detectShiftUntilLessThanIdiom(), and detectShiftUntilZeroIdiom().
|
static |
Definition at line 989 of file LoopIdiomRecognize.cpp.
References llvm::SCEV::FlagNUW, llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getTruncateOrZeroExtend(), and llvm::SCEV::isOne().
|
static |
Definition at line 384 of file LoopIdiomRecognize.cpp.
References llvm::SCEVConstant::getAPInt(), and llvm::SCEVNAryExpr::getOperand().
|
inline |
Matches if the value is loop-invariant.
Definition at line 2698 of file LoopIdiomRecognize.cpp.
Referenced by detectShiftUntilBitTestIdiom(), and detectShiftUntilZeroIdiom().
|
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 1534 of file LoopIdiomRecognize.cpp.
References Cond, 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().
|
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 1840 of file LoopIdiomRecognize.cpp.
References Cond, llvm::BranchInst::getCondition(), llvm::BranchInst::getSuccessor(), llvm::ConstantInt::getValue(), llvm::CmpInst::ICMP_ULT, and llvm::BranchInst::isConditional().
Referenced by detectShiftUntilLessThanIdiom().
|
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 951 of file LoopIdiomRecognize.cpp.
References Access, llvm::LocationSize::afterPointer(), B, llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::AAResults::getModRefInfo(), I, llvm::isModOrRefSet(), llvm::SCEVPatternMatch::m_scev_APInt(), llvm::PatternMatch::match(), llvm::LocationSize::precise(), Ptr, and llvm::APInt::tryZExtValue().
STATISTIC | ( | NumMemCpy | , |
"Number of memcpy's formed from loop load+stores" | |||
) |
STATISTIC | ( | NumMemMove | , |
"Number of memmove's formed from loop load+stores" | |||
) |
STATISTIC | ( | NumMemSet | , |
"Number of memset's formed from loop stores" | |||
) |
STATISTIC | ( | NumShiftUntilBitTest | , |
"Number of uncountable loops recognized as 'shift until bitttest' idiom" | |||
) |
STATISTIC | ( | NumShiftUntilZero | , |
"Number of uncountable loops recognized as 'shift until zero' idiom" | |||
) |
STATISTIC | ( | NumStrLen | , |
"Number of strlen's and wcslen's formed from loop loads" | |||
) |
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |