LLVM  8.0.0svn
Macros | Functions | Variables
LoopIdiomRecognize.cpp File Reference
#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/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Attributes.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/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/LoopIdiomRecognize.h"
#include "llvm/Transforms/Utils/BuildLibCalls.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

Go to the source code of this file.

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")
 
 INITIALIZE_PASS_BEGIN (LoopIdiomRecognizeLegacyPass, "loop-idiom", "Recognize loop idioms", false, false) INITIALIZE_PASS_END(LoopIdiomRecognizeLegacyPass
 
static void deleteDeadInstruction (Instruction *I)
 
static APInt getStoreStride (const SCEVAddRecExpr *StoreEv)
 
static ConstantgetMemSetPatternValue (Value *V, const DataLayout *DL)
 getMemSetPatternValue - If a strided store of the specified value is safe to turn into a memset_pattern16, return a ConstantArray of 16 bytes that should be passed in. More...
 
static bool mayLoopAccessLocation (Value *Ptr, ModRefInfo Access, Loop *L, const SCEV *BECount, unsigned StoreSize, AliasAnalysis &AA, SmallPtrSetImpl< Instruction *> &IgnoredStores)
 mayLoopAccessLocation - Return true if the specified loop might access the specified pointer location, which is a loop-strided access. More...
 
static const SCEVgetStartForNegStride (const SCEV *Start, const SCEV *BECount, Type *IntPtr, unsigned StoreSize, ScalarEvolution *SE)
 
static const SCEVgetNumBytes (const SCEV *BECount, Type *IntPtr, unsigned StoreSize, Loop *CurLoop, const DataLayout *DL, ScalarEvolution *SE)
 Compute the number of bytes as a SCEV from the backedge taken count. More...
 
static ValuematchCondition (BranchInst *BI, BasicBlock *LoopEntry)
 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. More...
 
static PHINodegetRecurrenceVar (Value *VarX, Instruction *DefX, BasicBlock *LoopEntry)
 
static bool detectPopcountIdiom (Loop *CurLoop, BasicBlock *PreCondBB, Instruction *&CntInst, PHINode *&CntPhi, Value *&Var)
 Return true iff the idiom is detected in the loop. More...
 
static bool detectCTLZIdiom (Loop *CurLoop, PHINode *&PhiX, Instruction *&CntInst, PHINode *&CntPhi, Instruction *&DefX)
 Return true if the idiom is detected in the loop. More...
 
static CallInstcreatePopcntIntrinsic (IRBuilder<> &IRBuilder, Value *Val, const DebugLoc &DL)
 
static CallInstcreateCTLZIntrinsic (IRBuilder<> &IRBuilder, Value *Val, const DebugLoc &DL, bool ZeroCheck)
 

Variables

static cl::opt< boolUseLIRCodeSizeHeurs ("use-lir-code-size-heurs", cl::desc("Use loop idiom recognition code size heuristics when compiling" "with -Os/-Oz"), cl::init(true), cl::Hidden)
 
loop idiom
 
loop Recognize loop idioms
 
loop Recognize loop false
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-idiom"

Definition at line 101 of file LoopIdiomRecognize.cpp.

Function Documentation

◆ createCTLZIntrinsic()

static CallInst* createCTLZIntrinsic ( IRBuilder<> &  IRBuilder,
Value Val,
const DebugLoc DL,
bool  ZeroCheck 
)
static

◆ createPopcntIntrinsic()

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

◆ deleteDeadInstruction()

static void deleteDeadInstruction ( Instruction I)
static

◆ detectCTLZIdiom()

static bool detectCTLZIdiom ( Loop CurLoop,
PHINode *&  PhiX,
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 1308 of file LoopIdiomRecognize.cpp.

References llvm::MCID::Add, llvm::AMDGPU::HSAMD::Kernel::Key::Args, llvm::LoopBase< BlockT, LoopT >::block_begin(), detectPopcountIdiom(), llvm::dyn_cast(), llvm::BasicBlock::end(), llvm::BasicBlock::front(), llvm::Value::getContext(), llvm::Instruction::getDebugLoc(), llvm::ConstantInt::getFalse(), llvm::BasicBlock::getFirstNonPHI(), llvm::PHINode::getIncomingValueForBlock(), llvm::TargetTransformInfo::getIntrinsicCost(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::TargetTransformInfo::getPopcntSupport(), getRecurrenceVar(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getTrue(), llvm::Value::getType(), llvm::isKnownNonNegative(), llvm::ConstantInt::isOne(), matchCondition(), llvm::TargetTransformInfo::PSK_FastHardware, llvm::BasicBlock::size(), llvm::TargetTransformInfo::TCC_Basic, and llvm::Value::users().

◆ detectPopcountIdiom()

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

References llvm::MCID::Add, llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::dyn_cast(), llvm::BasicBlock::end(), llvm::BasicBlock::getFirstNonPHI(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Instruction::getOpcode(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), getRecurrenceVar(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::isMinusOne(), llvm::ConstantInt::isOne(), matchCondition(), T, and llvm::Value::users().

Referenced by detectCTLZIdiom().

◆ getMemSetPatternValue()

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

getMemSetPatternValue - If a strided store of the specified value is safe to turn into a memset_pattern16, return a ConstantArray of 16 bytes that should be passed in.

Otherwise, return null.

Note that we don't ever attempt to use memset_pattern8 or 4, because these just replicate their input array and then pass on to memset_pattern16.

Definition at line 350 of file LoopIdiomRecognize.cpp.

References assert(), llvm::SetVector< T, Vector, Set >::begin(), llvm::BasicBlock::begin(), C, llvm::SmallVectorImpl< T >::clear(), llvm::SetVector< T, Vector, Set >::count(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::DominatorTree::dominates(), llvm::dyn_cast(), E, llvm::SetVector< T, Vector, Set >::end(), llvm::BasicBlock::end(), llvm::ArrayType::get(), llvm::ConstantArray::get(), llvm::StoreInst::getAlignment(), llvm::SCEVConstant::getAPInt(), llvm::MemIntrinsicBase< Derived >::getDest(), llvm::MemIntrinsicBase< Derived >::getDestAlignment(), llvm::MemIntrinsicBase< Derived >::getLength(), llvm::SCEVAddRecExpr::getLoop(), llvm::Instruction::getMetadata(), llvm::SCEVNAryExpr::getOperand(), llvm::Type::getPointerAddressSpace(), llvm::LoadInst::getPointerOperand(), llvm::StoreInst::getPointerOperand(), llvm::ScalarEvolution::getSCEV(), getStoreStride(), getType(), llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), llvm::GetUnderlyingObject(), llvm::MemSetBase< BaseCL >::getValue(), llvm::StoreInst::getValueOperand(), I, llvm::SetVector< T, Vector, Set >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SCEVAddRecExpr::isAffine(), llvm::Instruction::isAtomic(), llvm::DataLayout::isBigEndian(), llvm::isBytewiseValue(), llvm::isConsecutiveAccess(), llvm::StoreInst::isSimple(), isSimple(), llvm::LoadInst::isUnordered(), llvm::StoreInst::isUnordered(), llvm::LoadInst::isVolatile(), llvm::StoreInst::isVolatile(), llvm::MemIntrinsic::isVolatile(), llvm::LLVMContext::MD_nontemporal, llvm::No, llvm::None, llvm::SmallVectorTemplateBase< T, bool >::push_back(), SI, Size, llvm::SmallVectorBase::size(), and llvm::Yes.

Referenced by getNumBytes().

◆ getNumBytes()

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

◆ getRecurrenceVar()

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

Definition at line 1140 of file LoopIdiomRecognize.cpp.

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

Referenced by detectCTLZIdiom(), and detectPopcountIdiom().

◆ getStartForNegStride()

static const SCEV* getStartForNegStride ( const SCEV Start,
const SCEV BECount,
Type IntPtr,
unsigned  StoreSize,
ScalarEvolution SE 
)
static

Definition at line 809 of file LoopIdiomRecognize.cpp.

◆ getStoreStride()

static APInt getStoreStride ( const SCEVAddRecExpr StoreEv)
static

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( LoopIdiomRecognizeLegacyPass  ,
"loop-idiom ,
"Recognize loop idioms ,
false  ,
false   
)

◆ matchCondition()

static Value* matchCondition ( BranchInst BI,
BasicBlock LoopEntry 
)
static

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

References llvm::dyn_cast(), llvm::BranchInst::getCondition(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::BranchInst::getSuccessor(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::BranchInst::isConditional(), and llvm::ConstantInt::isZero().

Referenced by detectCTLZIdiom(), and detectPopcountIdiom().

◆ mayLoopAccessLocation()

static bool mayLoopAccessLocation ( Value Ptr,
ModRefInfo  Access,
Loop L,
const SCEV BECount,
unsigned  StoreSize,
AliasAnalysis AA,
SmallPtrSetImpl< Instruction *> &  IgnoredStores 
)
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 775 of file LoopIdiomRecognize.cpp.

References llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::LoopBase< BlockT, LoopT >::block_end(), llvm::SmallPtrSetImpl< PtrType >::count(), E, llvm::AAResults::getModRefInfo(), I, llvm::intersectModRef(), llvm::isModOrRefSet(), and llvm::MemoryLocation::UnknownSize.

◆ STATISTIC() [1/2]

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

◆ STATISTIC() [2/2]

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

Variable Documentation

◆ false

loop Recognize loop false

Definition at line 257 of file LoopIdiomRecognize.cpp.

◆ idiom

loop idiom

Definition at line 257 of file LoopIdiomRecognize.cpp.

◆ idioms

loop Recognize loop idioms

Definition at line 257 of file LoopIdiomRecognize.cpp.

◆ 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)
static

Referenced by deleteDeadInstruction().