LoopUnswitch.cpp File Reference

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LegacyDivergenceAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.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/Module.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/LoopPassManager.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <map>
#include <set>
#include <tuple>
#include <utility>
#include <vector>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "loop-unswitch"

Enumerations
enum	OperatorChain { OC_OpChainNone, OC_OpChainOr, OC_OpChainAnd, OC_OpChainMixed }
	Operator chain lattice. More...

Functions
	STATISTIC (NumBranches, "Number of branches unswitched")
	STATISTIC (NumSwitches, "Number of switches unswitched")
	STATISTIC (NumGuards, "Number of guards unswitched")
	STATISTIC (NumSelects, "Number of selects unswitched")
	STATISTIC (NumTrivial, "Number of unswitches that are trivial")
	STATISTIC (NumSimplify, "Number of simplifications of unswitched code")
	STATISTIC (TotalInsts, "Total number of instructions analyzed")
	INITIALIZE_PASS_BEGIN (LoopUnswitch, "loop-unswitch", "Unswitch loops", false, false) INITIALIZE_PASS_END(LoopUnswitch
static Value *	FindLIVLoopCondition (Value *Cond, Loop *L, bool &Changed, OperatorChain &ParentChain, DenseMap< Value *, Value *> &Cache)
	Cond is a condition that occurs in L. More...
static std::pair< Value *, OperatorChain >	FindLIVLoopCondition (Value *Cond, Loop *L, bool &Changed)
	Cond is a condition that occurs in L. More...
static bool	EqualityPropUnSafe (Value &LoopCond)
	FIXME: Remove this workaround when freeze related patches are done. More...
static bool	isTrivialLoopExitBlockHelper (Loop *L, BasicBlock *BB, BasicBlock *&ExitBB, std::set< BasicBlock *> &Visited)
	Check to see if all paths from BB exit the loop with no side effects (including infinite loops). More...
static BasicBlock *	isTrivialLoopExitBlock (Loop *L, BasicBlock *BB)
	Return true if the specified block unconditionally leads to an exit from the specified loop, and has no side-effects in the process. More...
static Loop *	CloneLoop (Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)
	Recursively clone the specified loop and all of its children, mapping the blocks with the specified map. More...
static void	RemoveFromWorklist (Instruction *I, std::vector< Instruction *> &Worklist)
	Remove all instances of I from the worklist vector specified. More...
static void	ReplaceUsesOfWith (Instruction *I, Value *V, std::vector< Instruction *> &Worklist, Loop *L, LPPassManager *LPM)
	When we find that I really equals V, remove I from the program, replacing all uses with V and update the worklist. More...

Variables
static cl::opt< unsigned >	Threshold ("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
loop	unswitch
loop Unswitch	loops
loop Unswitch	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-unswitch"

Definition at line 85 of file LoopUnswitch.cpp.

Enumeration Type Documentation

OperatorChain

enum OperatorChain

Operator chain lattice.

Enumerator
OC_OpChainNone	There is no operator.
OC_OpChainOr	There are only ORs.
OC_OpChainAnd	There are only ANDs.
OC_OpChainMixed	There are ANDs and ORs.

Definition at line 404 of file LoopUnswitch.cpp.

Function Documentation

CloneLoop()

static Loop* CloneLoop ( Loop *  L, Loop *  PL, ValueToValueMapTy &  VM, LoopInfo *  LI, LPPassManager *  LPM  )

static

Recursively clone the specified loop and all of its children, mapping the blocks with the specified map.

Definition at line 904 of file LoopUnswitch.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::LoopBase< BlockT, LoopT >::addChildLoop(), llvm::PHINode::addIncoming(), llvm::LPPassManager::addLoop(), llvm::LoopInfoBase< BlockT, LoopT >::addTopLevelLoop(), llvm::LoopInfoBase< BlockT, LoopT >::AllocateLoop(), llvm::DominatorTreeBase< NodeT, IsPostDom >::applyUpdates(), assert(), llvm::Intrinsic::assume, llvm::SmallVectorTemplateCommon< T >::begin(), llvm::BasicBlock::begin(), llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::LoopBase< BlockT, LoopT >::block_end(), llvm::SwitchInst::cases(), llvm::SmallVectorImpl< T >::clear(), llvm::CloneBasicBlock(), llvm::LPPassManager::cloneBasicBlockSimpleAnalysis(), llvm::LoopBase< BlockT, LoopT >::contains(), Context, llvm::PHINode::Create(), llvm::dbgs(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::LPPassManager::deleteSimpleAnalysisValue(), llvm::dyn_cast(), E, llvm::SmallVectorTemplateCommon< T >::end(), llvm::ValueMap< KeyT, ValueT, Config >::end(), llvm::Function::end(), EqualityPropUnSafe(), F(), llvm::ValueMap< KeyT, ValueT, Config >::find(), llvm::SwitchInst::findCaseValue(), FindLIVLoopCondition(), first, llvm::BasicBlock::front(), llvm::Function::getBasicBlockList(), llvm::LoopBase< BlockT, LoopT >::getBlocks(), llvm::SwitchInst::getCondition(), llvm::BasicBlock::getContext(), llvm::Value::getContext(), llvm::ConstantInt::getFalse(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Type::getInt1Ty(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::BasicBlock::getLandingPadInst(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::Value::getName(), llvm::Instruction::getNumSuccessors(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::Instruction::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getTrue(), llvm::Value::getType(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlocks(), I, llvm::CmpInst::ICMP_EQ, llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::SmallPtrSetImpl< PtrType >::insert(), isTrivialLoopExitBlock(), llvm::BranchInst::isUnconditional(), LLVM_DEBUG, llvm::LoopBlocksRPO::perform(), llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::AssumptionCache::registerAssumption(), llvm::RemapInstruction(), llvm::Instruction::removeFromParent(), llvm::Value::replaceAllUsesWith(), llvm::RF_IgnoreMissingLocals, llvm::RF_NoModuleLevelChanges, llvm::ValueMapIterator< DenseMapT, KeyT >::ValueTypeProxy::second, llvm::SmallVectorBase::size(), llvm::iplist_impl< IntrusiveListT, TraitsT >::splice(), llvm::SplitBlock(), llvm::SplitBlockPredecessors(), llvm::SplitCriticalEdge(), llvm::SplitEdge(), std::swap(), llvm::Instruction::swapProfMetadata(), llvm::VerifyMemorySSA, and llvm::MemorySSA::verifyMemorySSA().

EqualityPropUnSafe()

static bool EqualityPropUnSafe ( Value &  LoopCond )

static

FIXME: Remove this workaround when freeze related patches are done.

LoopUnswitch and Equality propagation in GVN have discrepancy about whether branch on undef/poison has undefine behavior. Here it is to rule out some common cases that we found such discrepancy already causing problems. Detail could be found in PR31652. Note if the func returns true, it is unsafe. But if it is false, it doesn't mean it is necessarily safe.

Definition at line 593 of file LoopUnswitch.cpp.

References assert(), llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::LoopBase< BlockT, LoopT >::block_end(), llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::SwitchInst::cases(), Context, llvm::Attribute::Convergent, llvm::dyn_cast(), E, llvm::Intrinsic::experimental_guard, FindLIVLoopCondition(), first, llvm::Constant::getAllOnesValue(), llvm::SwitchInst::getCondition(), llvm::BasicBlock::getContext(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Constant::getNullValue(), llvm::SwitchInst::getNumCases(), llvm::User::getOperand(), llvm::BasicBlock::getParent(), llvm::ConstantInt::getTrue(), llvm::Value::getType(), llvm::LoopBase< BlockT, LoopT >::hasDedicatedExits(), llvm::Function::hasFnAttribute(), I, llvm::ICmpInst::isEquality(), llvm::SimpleLoopSafetyInfo::isGuaranteedToExecute(), llvm::Loop::isSafeToClone(), OC_OpChainAnd, OC_OpChainNone, OC_OpChainOr, llvm::Attribute::OptimizeForSize, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::PPCISD::SC, and SI.

Referenced by CloneLoop().

FindLIVLoopCondition() [1/2]

static Value* FindLIVLoopCondition ( Value *  Cond, Loop *  L, bool &  Changed, OperatorChain &  ParentChain, DenseMap< Value *, Value *> &  Cache  )

static

Cond is a condition that occurs in L.

If it is invariant in the loop, or has an invariant piece, return the invariant. Otherwise, return null. NOTE: FindLIVLoopCondition will not return a partial LIV by walking up a mixed operator chain, as we can not reliably find a value which will simplify the operator chain. If the chain is AND-only or OR-only, we can use 0 or ~0 to simplify the chain.

NOTE: In case a partial LIV and a mixed operator chain, we may be able to simplify the condition itself to a loop variant condition, but at the cost of creating an entirely new loop.

Definition at line 422 of file LoopUnswitch.cpp.

References llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::Value::getType(), if(), llvm::Type::isVectorTy(), llvm::Loop::makeLoopInvariant(), OC_OpChainAnd, OC_OpChainMixed, OC_OpChainNone, and OC_OpChainOr.

Referenced by CloneLoop(), EqualityPropUnSafe(), and FindLIVLoopCondition().

FindLIVLoopCondition() [2/2]

static std::pair<Value *, OperatorChain> FindLIVLoopCondition ( Value *  Cond, Loop *  L, bool &  Changed  )

static

Cond is a condition that occurs in L.

If it is invariant in the loop, or has an invariant piece, return the invariant along with the operator chain type. Otherwise, return null.

Definition at line 504 of file LoopUnswitch.cpp.

References assert(), llvm::SimpleLoopSafetyInfo::computeLoopSafetyInfo(), llvm::EnableMSSALoopDependency, F(), FindLIVLoopCondition(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BasicBlock::getParent(), llvm::Function::hasFnAttribute(), llvm::Loop::isLCSSAForm(), OC_OpChainMixed, OC_OpChainNone, llvm::Attribute::SanitizeMemory, llvm::VerifyMemorySSA, and llvm::MemorySSA::verifyMemorySSA().

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	LoopUnswitch	,
		"loop-unswitch"	,
		"Unswitch loops"	,
		false	,
		false
	)

isTrivialLoopExitBlock()

static BasicBlock* isTrivialLoopExitBlock ( Loop *  L, BasicBlock *  BB  )

static

Return true if the specified block unconditionally leads to an exit from the specified loop, and has no side-effects in the process.

If so, return the block that is exited to, otherwise return null.

Definition at line 865 of file LoopUnswitch.cpp.

References llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Value::getName(), isTrivialLoopExitBlockHelper(), and LLVM_DEBUG.

Referenced by CloneLoop().

isTrivialLoopExitBlockHelper()

static bool isTrivialLoopExitBlockHelper ( Loop *  L, BasicBlock *  BB, BasicBlock *&  ExitBB, std::set< BasicBlock *> &  Visited  )

static

Check to see if all paths from BB exit the loop with no side effects (including infinite loops).

If true, we return true and set ExitBB to the block we exit through.

Definition at line 830 of file LoopUnswitch.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), E, I, SI, llvm::succ_begin(), and llvm::succ_end().

Referenced by isTrivialLoopExitBlock().

RemoveFromWorklist()

static void RemoveFromWorklist ( Instruction *  I, std::vector< Instruction *> &  Worklist  )

static

Remove all instances of I from the worklist vector specified.

Definition at line 1398 of file LoopUnswitch.cpp.

References I, and llvm::sys::fs::remove().

Referenced by ReplaceUsesOfWith().

ReplaceUsesOfWith()

static void ReplaceUsesOfWith ( Instruction *  I, Value *  V, std::vector< Instruction *> &  Worklist, Loop *  L, LPPassManager *  LPM  )

static

When we find that I really equals V, remove I from the program, replacing all uses with V and update the worklist.

Definition at line 1407 of file LoopUnswitch.cpp.

References llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), assert(), llvm::BasicBlock::begin(), llvm::SwitchInst::case_default(), llvm::LoopBase< BlockT, LoopT >::contains(), Context, llvm::BasicBlock::Create(), llvm::BranchInst::Create(), llvm::dbgs(), llvm::LPPassManager::deleteSimpleAnalysisValue(), llvm::DominatorTree::dominates(), llvm::dyn_cast(), llvm::BasicBlock::end(), llvm::Instruction::eraseFromParent(), llvm::BasicBlock::eraseFromParent(), llvm::SwitchInst::findCaseDest(), llvm::SwitchInst::findCaseValue(), llvm::ConstantInt::get(), llvm::UndefValue::get(), llvm::SwitchInst::CaseHandleImpl< SwitchInstT, ConstantIntT, BasicBlockT >::getCaseSuccessor(), llvm::Value::getContext(), llvm::Module::getDataLayout(), llvm::ConstantInt::getFalse(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BasicBlock::getInstList(), llvm::Type::getInt1Ty(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::BasicBlock::getModule(), llvm::Value::getName(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::CmpInst::getPredicate(), llvm::BasicBlock::getSinglePredecessor(), llvm::ConstantInt::getTrue(), llvm::Value::getType(), I, llvm::CmpInst::ICMP_EQ, llvm::ICmpInst::isEquality(), llvm::isInstructionTriviallyDead(), llvm::Type::isIntegerTy(), LLVM_DEBUG, llvm::Instruction::mayHaveSideEffects(), llvm::LoopInfoBase< BlockT, LoopT >::removeBlock(), RemoveFromWorklist(), llvm::Value::replaceAllUsesWith(), llvm::LoopInfo::replacementPreservesLCSSAForm(), llvm::User::replaceUsesOfWith(), llvm::SimplifyInstruction(), llvm::iplist_impl< IntrusiveListT, TraitsT >::splice(), llvm::SplitEdge(), llvm::succ_begin(), and llvm::Value::users().

STATISTIC() [1/7]

STATISTIC	(	NumBranches	,
		"Number of branches unswitched"
	)

STATISTIC() [2/7]

STATISTIC	(	NumSwitches	,
		"Number of switches unswitched"
	)

STATISTIC() [3/7]

STATISTIC	(	NumGuards	,
		"Number of guards unswitched"
	)

STATISTIC() [4/7]

STATISTIC	(	NumSelects	,
		"Number of selects unswitched"
	)

STATISTIC() [5/7]

STATISTIC	(	NumTrivial	,
		"Number of unswitches that are trivial"
	)

STATISTIC() [6/7]

STATISTIC	(	NumSimplify	,
		"Number of simplifications of unswitched code"
	)

STATISTIC() [7/7]

STATISTIC	(	TotalInsts	,
		"Total number of instructions analyzed"
	)

Variable Documentation

false

loop Unswitch false

Definition at line 396 of file LoopUnswitch.cpp.

loops

loop Unswitch loops

Definition at line 396 of file LoopUnswitch.cpp.

Threshold

cl::opt<unsigned> Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)

static

Referenced by checkBias(), computeImportForFunction(), ComputeImportForModule(), llvm::createX86PadShortFunctions(), llvm::emitThumbRegPlusImmediate(), llvm::BitstreamWriter::EmitVBR(), llvm::BitstreamWriter::EmitVBR64(), llvm::sampleprof::FunctionSamples::findInlinedFunctions(), llvm::HexagonFrameLowering::getAlignaInstr(), getBranchHint(), llvm::ARMBaseInstrInfo::getOperandLatency(), llvm::InlineCost::getThreshold(), llvm::AMDGPUTTIImpl::getUnrollingPreferences(), IncorporateWeight(), isPointerValueDeadOnEntryToFunction(), llvm::LoopRotation(), mayLoopAccessLocation(), llvm::InlineCost::operator bool(), llvm::LoopRotatePass::run(), llvm::SimplifyCFGPass::run(), selectCallee(), llvm::LLVMContext::setDiagnosticsHotnessThreshold(), and tryToUnrollLoop().

unswitch

loop unswitch

Definition at line 396 of file LoopUnswitch.cpp.