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 Constant *	getMemSetPatternValue (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 SCEV *	getStartForNegStride (const SCEV *Start, const SCEV *BECount, Type *IntPtr, unsigned StoreSize, ScalarEvolution *SE)
static const SCEV *	getNumBytes (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 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. More...
static PHINode *	getRecurrenceVar (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	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. More...
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)

Variables
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)
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

createFFSIntrinsic()

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

static

Definition at line 1539 of file LoopIdiomRecognize.cpp.

References llvm::PHINode::addIncoming(), llvm::PHINode::Create(), llvm::IRBuilder< T, Inserter >::CreateAdd(), llvm::IRBuilder< T, Inserter >::CreateCall(), llvm::IRBuilder< T, Inserter >::CreateICmp(), createPopcntIntrinsic(), llvm::IRBuilder< T, Inserter >::CreateSub(), llvm::IRBuilder< T, Inserter >::CreateZExtOrTrunc(), llvm::dyn_cast(), llvm::ScalarEvolution::forgetLoop(), llvm::BasicBlock::front(), llvm::ConstantInt::get(), llvm::Instruction::getDebugLoc(), llvm::Intrinsic::getDeclaration(), llvm::IRBuilderBase::getFalse(), llvm::PHINode::getIncomingValueForBlock(), llvm::IRBuilderBase::GetInsertBlock(), llvm::Type::getIntegerBitWidth(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::CmpInst::getPredicate(), llvm::BasicBlock::getTerminator(), llvm::IRBuilderBase::getTrue(), llvm::Value::getType(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_UGT, llvm::ConstantInt::isZero(), llvm_unreachable, llvm::RecursivelyDeleteTriviallyDeadInstructions(), llvm::Value::replaceUsesOutsideBlock(), llvm::Instruction::setDebugLoc(), llvm::IRBuilderBase::SetInsertPoint(), and std::swap().

createPopcntIntrinsic()

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

static

Definition at line 1526 of file LoopIdiomRecognize.cpp.

References llvm::IRBuilder< T, Inserter >::CreateCall(), llvm::Intrinsic::ctpop, llvm::Intrinsic::getDeclaration(), llvm::IRBuilderBase::GetInsertBlock(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::Value::getType(), and llvm::Instruction::setDebugLoc().

Referenced by createFFSIntrinsic().

deleteDeadInstruction()

static void deleteDeadInstruction ( Instruction *  I )

static

Definition at line 263 of file LoopIdiomRecognize.cpp.

References llvm::SimpleLoopSafetyInfo::anyBlockMayThrow(), assert(), llvm::SimpleLoopSafetyInfo::computeLoopSafetyInfo(), llvm::dbgs(), llvm::Instruction::eraseFromParent(), llvm::UndefValue::get(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::Value::getType(), llvm::TargetLibraryInfo::has(), llvm::ScalarEvolution::hasLoopInvariantBackedgeTakenCount(), LLVM_DEBUG, Name, llvm::Function::optForSize(), llvm::Value::replaceAllUsesWith(), and UseLIRCodeSizeHeurs.

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 1182 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 detectShiftUntilZeroIdiom().

detectShiftUntilZeroIdiom()

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

References llvm::MCID::Add, llvm::AMDGPU::HSAMD::Kernel::Key::Args, llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::Intrinsic::ctlz, llvm::Intrinsic::cttz, 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::LoopBase< BlockT, LoopT >::getLoopPreheader(), 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(), llvm::Instruction::isShift(), matchCondition(), llvm::TargetTransformInfo::PSK_FastHardware, llvm::BasicBlock::size(), llvm::TargetTransformInfo::TCC_Basic, and llvm::Value::users().

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 351 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

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

References assert(), llvm::SCEV::FlagNUW, llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getConstant(), llvm::Type::getInt8PtrTy(), getMemSetPatternValue(), llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getNegativeSCEV(), llvm::ScalarEvolution::getOne(), llvm::Type::getPointerAddressSpace(), llvm::BasicBlock::getTerminator(), llvm::ScalarEvolution::getTruncateOrZeroExtend(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), llvm::ScalarEvolution::getZeroExtendExpr(), llvm::CmpInst::ICMP_NE, llvm::isBytewiseValue(), and llvm::ScalarEvolution::isLoopEntryGuardedByCond().

Referenced by llvm::DebugLocStream::getBytes(), and llvm::DebugLocStream::getComments().

getRecurrenceVar()

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

static

Definition at line 1149 of file LoopIdiomRecognize.cpp.

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

Referenced by detectPopcountIdiom(), and detectShiftUntilZeroIdiom().

getStartForNegStride()

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

static

Definition at line 811 of file LoopIdiomRecognize.cpp.

getStoreStride()

static APInt getStoreStride ( const SCEVAddRecExpr *  StoreEv )

static

Definition at line 340 of file LoopIdiomRecognize.cpp.

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

Referenced by getMemSetPatternValue().

INITIALIZE_PASS_BEGIN()

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

Referenced by llvm::LoopIdiomRecognizePass::run().

matchCondition()

static 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 1121 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(), llvm::ConstantInt::isZero(), and std::swap().

Referenced by detectPopcountIdiom(), and detectShiftUntilZeroIdiom().

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 776 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(), llvm::LocationSize::precise(), and llvm::LocationSize::unknown().

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

idiom

loop idiom

Definition at line 258 of file LoopIdiomRecognize.cpp.

idioms

loop Recognize loop idioms

Definition at line 258 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().