SimpleLoopUnswitch.cpp File Reference

#include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GuardUtils.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/MustExecute.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/ScalarEvolution.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/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/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GenericDomTree.h"
#include "llvm/Support/InstructionCost.h"
#include "llvm/Support/raw_ostream.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 <iterator>
#include <numeric>
#include <optional>
#include <utility>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "simple-loop-unswitch"
	===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow ------—===//

Functions
	STATISTIC (NumBranches, "Number of branches unswitched")
	STATISTIC (NumSwitches, "Number of switches unswitched")
	STATISTIC (NumSelects, "Number of selects turned into branches for unswitching")
	STATISTIC (NumGuards, "Number of guards turned into branches for unswitching")
	STATISTIC (NumTrivial, "Number of unswitches that are trivial")
	STATISTIC (NumCostMultiplierSkipped, "Number of unswitch candidates that had their cost multiplier skipped")
	STATISTIC (NumInvariantConditionsInjected, "Number of invariant conditions injected and unswitched")
static Value *	skipTrivialSelect (Value *Cond)
static TinyPtrVector< Value * >	collectHomogenousInstGraphLoopInvariants (const Loop &L, Instruction &Root, const LoopInfo &LI)
	Collect all of the loop invariant input values transitively used by the homogeneous instruction graph from a given root.
static void	replaceLoopInvariantUses (const Loop &L, Value *Invariant, Constant &Replacement)
static bool	areLoopExitPHIsLoopInvariant (const Loop &L, const BasicBlock &ExitingBB, const BasicBlock &ExitBB)
	Check that all the LCSSA PHI nodes in the loop exit block have trivial incoming values along this edge.
static void	buildPartialUnswitchConditionalBranch (BasicBlock &BB, ArrayRef< Value * > Invariants, bool Direction, BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, bool InsertFreeze, const Instruction *I, AssumptionCache *AC, const DominatorTree &DT)
	Copy a set of loop invariant values ToDuplicate and insert them at the end of BB and conditionally branch on the copied condition.
static void	buildPartialInvariantUnswitchConditionalBranch (BasicBlock &BB, ArrayRef< Value * > ToDuplicate, bool Direction, BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, Loop &L, MemorySSAUpdater *MSSAU)
	Copy a set of loop invariant values, and conditionally branch on them.
static void	rewritePHINodesForUnswitchedExitBlock (BasicBlock &UnswitchedBB, BasicBlock &OldExitingBB, BasicBlock &OldPH)
	Rewrite the PHI nodes in an unswitched loop exit basic block.
static void	rewritePHINodesForExitAndUnswitchedBlocks (BasicBlock &ExitBB, BasicBlock &UnswitchedBB, BasicBlock &OldExitingBB, BasicBlock &OldPH, bool FullUnswitch)
	Rewrite the PHI nodes in the loop exit basic block and the split off unswitched block.
static void	hoistLoopToNewParent (Loop &L, BasicBlock &Preheader, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution *SE)
	Hoist the current loop up to the innermost loop containing a remaining exit.
static Loop *	getTopMostExitingLoop (const BasicBlock *ExitBB, const LoopInfo &LI)
static bool	unswitchTrivialBranch (Loop &L, BranchInst &BI, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU)
	Unswitch a trivial branch if the condition is loop invariant.
static bool	unswitchTrivialSwitch (Loop &L, SwitchInst &SI, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU)
	Unswitch a trivial switch if the condition is loop invariant.
static bool	unswitchAllTrivialConditions (Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU)
	This routine scans the loop to find a branch or switch which occurs before any side effects occur.
static BasicBlock *	buildClonedLoopBlocks (Loop &L, BasicBlock *LoopPH, BasicBlock *SplitBB, ArrayRef< BasicBlock * > ExitBlocks, BasicBlock *ParentBB, BasicBlock *UnswitchedSuccBB, BasicBlock *ContinueSuccBB, const SmallDenseMap< BasicBlock *, BasicBlock *, 16 > &DominatingSucc, ValueToValueMapTy &VMap, SmallVectorImpl< DominatorTree::UpdateType > &DTUpdates, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution *SE)
	Build the cloned blocks for an unswitched copy of the given loop.
static Loop *	cloneLoopNest (Loop &OrigRootL, Loop *RootParentL, const ValueToValueMapTy &VMap, LoopInfo &LI)
	Recursively clone the specified loop and all of its children.
static void	buildClonedLoops (Loop &OrigL, ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VMap, LoopInfo &LI, SmallVectorImpl< Loop * > &NonChildClonedLoops)
	Build the cloned loops of an original loop from unswitching.
static void	deleteDeadClonedBlocks (Loop &L, ArrayRef< BasicBlock * > ExitBlocks, ArrayRef< std::unique_ptr< ValueToValueMapTy > > VMaps, DominatorTree &DT, MemorySSAUpdater *MSSAU)
static void	deleteDeadBlocksFromLoop (Loop &L, SmallVectorImpl< BasicBlock * > &ExitBlocks, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution *SE, LPMUpdater &LoopUpdater)
static SmallPtrSet< const BasicBlock *, 16 >	recomputeLoopBlockSet (Loop &L, LoopInfo &LI)
	Recompute the set of blocks in a loop after unswitching.
static bool	rebuildLoopAfterUnswitch (Loop &L, ArrayRef< BasicBlock * > ExitBlocks, LoopInfo &LI, SmallVectorImpl< Loop * > &HoistedLoops, ScalarEvolution *SE)
	Rebuild a loop after unswitching removes some subset of blocks and edges.
template<typename CallableT>
void	visitDomSubTree (DominatorTree &DT, BasicBlock *BB, CallableT Callable)
	Helper to visit a dominator subtree, invoking a callable on each node.
void	postUnswitch (Loop &L, LPMUpdater &U, StringRef LoopName, bool CurrentLoopValid, bool PartiallyInvariant, bool InjectedCondition, ArrayRef< Loop * > NewLoops)
static void	unswitchNontrivialInvariants (Loop &L, Instruction &TI, ArrayRef< Value * > Invariants, IVConditionInfo &PartialIVInfo, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, LPMUpdater &LoopUpdater, bool InsertFreeze, bool InjectedCondition)
static InstructionCost	computeDomSubtreeCost (DomTreeNode &N, const SmallDenseMap< BasicBlock *, InstructionCost, 4 > &BBCostMap, SmallDenseMap< DomTreeNode *, InstructionCost, 4 > &DTCostMap)
	Recursively compute the cost of a dominator subtree based on the per-block cost map provided.
static BranchInst *	turnSelectIntoBranch (SelectInst *SI, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, AssumptionCache *AC)
	Turns a select instruction into implicit control flow branch, making the following replacement:
static BranchInst *	turnGuardIntoBranch (IntrinsicInst *GI, Loop &L, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU)
	Turns a llvm.experimental.guard intrinsic into implicit control flow branch, making the following replacement:
static int	CalculateUnswitchCostMultiplier (const Instruction &TI, const Loop &L, const LoopInfo &LI, const DominatorTree &DT, ArrayRef< NonTrivialUnswitchCandidate > UnswitchCandidates)
	Cost multiplier is a way to limit potentially exponential behavior of loop-unswitch.
static bool	collectUnswitchCandidates (SmallVectorImpl< NonTrivialUnswitchCandidate > &UnswitchCandidates, IVConditionInfo &PartialIVInfo, Instruction *&PartialIVCondBranch, const Loop &L, const LoopInfo &LI, AAResults &AA, const MemorySSAUpdater *MSSAU)
static void	canonicalizeForInvariantConditionInjection (CmpPredicate &Pred, Value *&LHS, Value *&RHS, BasicBlock *&IfTrue, BasicBlock *&IfFalse, const Loop &L)
	Tries to canonicalize condition described by:
static bool	shouldTryInjectInvariantCondition (const ICmpInst::Predicate Pred, const Value *LHS, const Value *RHS, const BasicBlock *IfTrue, const BasicBlock *IfFalse, const Loop &L)
	Returns true, if predicate described by ( Pred, LHS, RHS ) succeeding into blocks ( IfTrue, IfFalse) can be optimized by injecting a loop-invariant condition.
bool	shouldTryInjectBasingOnMetadata (const BranchInst *BI, const BasicBlock *TakenSucc)
	Returns true, if metadata on BI allows us to optimize branching into TakenSucc via injection of invariant conditions.
static NonTrivialUnswitchCandidate	injectPendingInvariantConditions (NonTrivialUnswitchCandidate Candidate, Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, MemorySSAUpdater *MSSAU)
	Materialize pending invariant condition of the given candidate into IR.
static bool	insertCandidatesWithPendingInjections (SmallVectorImpl< NonTrivialUnswitchCandidate > &UnswitchCandidates, Loop &L, ICmpInst::Predicate Pred, ArrayRef< CompareDesc > Compares, const DominatorTree &DT)
	Given chain of loop branch conditions looking like: br (Variant < Invariant1) br (Variant < Invariant2) br (Variant < Invariant3) ... collect set of invariant conditions on which we want to unswitch, which look like: Invariant1 <= Invariant2 Invariant2 <= Invariant3 ... Though they might not immediately exist in the IR, we can still inject them.
static bool	collectUnswitchCandidatesWithInjections (SmallVectorImpl< NonTrivialUnswitchCandidate > &UnswitchCandidates, IVConditionInfo &PartialIVInfo, Instruction *&PartialIVCondBranch, Loop &L, const DominatorTree &DT, const LoopInfo &LI, AAResults &AA, const MemorySSAUpdater *MSSAU)
	Collect unswitch candidates by invariant conditions that are not immediately present in the loop.
static bool	isSafeForNoNTrivialUnswitching (Loop &L, LoopInfo &LI)
static NonTrivialUnswitchCandidate	findBestNonTrivialUnswitchCandidate (ArrayRef< NonTrivialUnswitchCandidate > UnswitchCandidates, const Loop &L, const DominatorTree &DT, const LoopInfo &LI, AssumptionCache &AC, const TargetTransformInfo &TTI, const IVConditionInfo &PartialIVInfo)
static bool	shouldInsertFreeze (Loop &L, Instruction &TI, DominatorTree &DT, AssumptionCache &AC)
static bool	unswitchBestCondition (Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, AAResults &AA, TargetTransformInfo &TTI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, LPMUpdater &LoopUpdater)
static bool	unswitchLoop (Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, AAResults &AA, TargetTransformInfo &TTI, bool Trivial, bool NonTrivial, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI, LPMUpdater &LoopUpdater)
	Unswitch control flow predicated on loop invariant conditions.

Variables
static cl::opt< bool >	EnableNonTrivialUnswitch ("enable-nontrivial-unswitch", cl::init(false), cl::Hidden, cl::desc("Forcibly enables non-trivial loop unswitching rather than " "following the configuration passed into the pass."))
static cl::opt< int >	UnswitchThreshold ("unswitch-threshold", cl::init(50), cl::Hidden, cl::desc("The cost threshold for unswitching a loop."))
static cl::opt< bool >	EnableUnswitchCostMultiplier ("enable-unswitch-cost-multiplier", cl::init(true), cl::Hidden, cl::desc("Enable unswitch cost multiplier that prohibits exponential " "explosion in nontrivial unswitch."))
static cl::opt< int >	UnswitchSiblingsToplevelDiv ("unswitch-siblings-toplevel-div", cl::init(2), cl::Hidden, cl::desc("Toplevel siblings divisor for cost multiplier."))
static cl::opt< int >	UnswitchParentBlocksDiv ("unswitch-parent-blocks-div", cl::init(8), cl::Hidden, cl::desc("Outer loop size divisor for cost multiplier."))
static cl::opt< int >	UnswitchNumInitialUnscaledCandidates ("unswitch-num-initial-unscaled-candidates", cl::init(8), cl::Hidden, cl::desc("Number of unswitch candidates that are ignored when calculating " "cost multiplier."))
static cl::opt< bool >	UnswitchGuards ("simple-loop-unswitch-guards", cl::init(true), cl::Hidden, cl::desc("If enabled, simple loop unswitching will also consider " "llvm.experimental.guard intrinsics as unswitch candidates."))
static cl::opt< bool >	DropNonTrivialImplicitNullChecks ("simple-loop-unswitch-drop-non-trivial-implicit-null-checks", cl::init(false), cl::Hidden, cl::desc("If enabled, drop make.implicit metadata in unswitched implicit " "null checks to save time analyzing if we can keep it."))
static cl::opt< unsigned >	MSSAThreshold ("simple-loop-unswitch-memoryssa-threshold", cl::desc("Max number of memory uses to explore during " "partial unswitching analysis"), cl::init(100), cl::Hidden)
static cl::opt< bool >	FreezeLoopUnswitchCond ("freeze-loop-unswitch-cond", cl::init(true), cl::Hidden, cl::desc("If enabled, the freeze instruction will be added to condition " "of loop unswitch to prevent miscompilation."))
static cl::opt< bool >	InjectInvariantConditions ("simple-loop-unswitch-inject-invariant-conditions", cl::Hidden, cl::desc("Whether we should inject new invariants and unswitch them to " "eliminate some existing (non-invariant) conditions."), cl::init(true))
static cl::opt< unsigned >	InjectInvariantConditionHotnesThreshold ("simple-loop-unswitch-inject-invariant-condition-hotness-threshold", cl::Hidden, cl::desc("Only try to inject loop invariant conditions and " "unswitch on them to eliminate branches that are " "not-taken 1/<this option> times or less."), cl::init(16))

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "simple-loop-unswitch"

===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow ------—===//

Definition at line 69 of file SimpleLoopUnswitch.cpp.

Function Documentation

areLoopExitPHIsLoopInvariant()

bool areLoopExitPHIsLoopInvariant ( const Loop & L, const BasicBlock & ExitingBB, const BasicBlock & ExitBB )

static

Check that all the LCSSA PHI nodes in the loop exit block have trivial incoming values along this edge.

Definition at line 255 of file SimpleLoopUnswitch.cpp.

References llvm::dyn_cast(), I, and llvm_unreachable.

Referenced by unswitchTrivialBranch(), and unswitchTrivialSwitch().

buildClonedLoopBlocks()

BasicBlock * buildClonedLoopBlocks ( Loop & L, BasicBlock * LoopPH, BasicBlock * SplitBB, ArrayRef< BasicBlock * > ExitBlocks, BasicBlock * ParentBB, BasicBlock * UnswitchedSuccBB, BasicBlock * ContinueSuccBB, const SmallDenseMap< BasicBlock *, BasicBlock *, 16 > & DominatingSucc, ValueToValueMapTy & VMap, SmallVectorImpl< DominatorTree::UpdateType > & DTUpdates, AssumptionCache & AC, DominatorTree & DT, LoopInfo & LI, MemorySSAUpdater * MSSAU, ScalarEvolution * SE )

static

Build the cloned blocks for an unswitched copy of the given loop.

The cloned blocks are inserted before the loop preheader (LoopPH) and after the split block (SplitBB) that will be used to select between the cloned and original loop.

This routine handles cloning all of the necessary loop blocks and exit blocks including rewriting their instructions and the relevant PHI nodes. Any loop blocks or exit blocks which are dominated by a different successor than the one for this clone of the loop blocks can be trivially skipped. We use the DominatingSucc map to determine whether a block satisfies that property with a simple map lookup.

It also correctly creates the unconditional branch in the cloned unswitched parent block to only point at the unswitched successor.

This does not handle most of the necessary updates to LoopInfo. Only exit block splitting is correctly reflected in LoopInfo, essentially all of the cloned blocks (and their loops) are left without full LoopInfo updates. This also doesn't fully update DominatorTree. It adds the cloned blocks to them but doesn't create the cloned DominatorTree structure and instead the caller must recompute an accurate DT. It does correctly update the AssumptionCache provided in AC.

Definition at line 1175 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::cast(), llvm::cast_or_null(), llvm::SmallPtrSetImplBase::clear(), llvm::CloneBasicBlock(), llvm::BranchInst::Create(), llvm::PHINode::Create(), llvm::dyn_cast(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::Instruction::eraseFromParent(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::ScalarEvolution::forgetLcssaPhiWithNewPredecessor(), llvm::Instruction::getDebugLoc(), I, II, llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::make_range(), llvm::BasicBlock::moveBefore(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::RecursivelyDeleteTriviallyDeadInstructions(), llvm::AssumptionCache::registerAssumption(), llvm::RemapDbgRecordRange(), llvm::RemapInstruction(), llvm::SmallVectorImpl< T >::reserve(), llvm::RF_IgnoreMissingLocals, llvm::RF_NoModuleLevelChanges, llvm::Instruction::setDebugLoc(), llvm::ArrayRef< T >::size(), llvm::SplitBlock(), llvm::successors(), and llvm::zip_first().

Referenced by unswitchNontrivialInvariants().

buildClonedLoops()

void buildClonedLoops ( Loop & OrigL, ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy & VMap, LoopInfo & LI, SmallVectorImpl< Loop * > & NonChildClonedLoops )

static

Build the cloned loops of an original loop from unswitching.

Because unswitching simplifies the CFG of the loop, this isn't a trivial operation. We need to re-verify that there even is a loop (as the backedge may not have been cloned), and even if there are remaining backedges the backedge set may be different. However, we know that each child loop is undisturbed, we only need to find where to place each child loop within either any parent loop or within a cloned version of the original loop.

Because child loops may end up cloned outside of any cloned version of the original loop, multiple cloned sibling loops may be created. All of them are returned so that the newly introduced loop nest roots can be identified.

Definition at line 1431 of file SimpleLoopUnswitch.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::LoopBase< BlockT, LoopT >::addChildLoop(), llvm::LoopInfoBase< BlockT, LoopT >::addTopLevelLoop(), llvm::LoopInfoBase< BlockT, LoopT >::AllocateLoop(), llvm::ArrayRef(), assert(), llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::cast(), llvm::cast_or_null(), cloneLoopNest(), llvm::concat(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::SetVector< T, Vector, Set, N >::count(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::ValueMap< KeyT, ValueT, Config >::count(), llvm::SmallPtrSetImplBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SetVector< T, Vector, Set, N >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), LHS, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorImpl< T >::reserve(), llvm::LoopBase< BlockT, LoopT >::reserveBlocks(), RHS, llvm::ArrayRef< T >::size(), llvm::SmallPtrSetImplBase::size(), and llvm::sort().

Referenced by unswitchNontrivialInvariants().

buildPartialInvariantUnswitchConditionalBranch()

void buildPartialInvariantUnswitchConditionalBranch ( BasicBlock & BB, ArrayRef< Value * > ToDuplicate, bool Direction, BasicBlock & UnswitchedSucc, BasicBlock & NormalSucc, Loop & L, MemorySSAUpdater * MSSAU )

static

Copy a set of loop invariant values, and conditionally branch on them.

Definition at line 296 of file SimpleLoopUnswitch.cpp.

References llvm::MemorySSA::BeforeTerminator, llvm::cast(), llvm::Instruction::clone(), Cond, llvm::IRBuilderBase::CreateCondBr(), llvm::MemorySSAUpdater::createMemoryAccessInBB(), DL, llvm::dyn_cast(), llvm::dyn_cast_or_null(), llvm::BasicBlock::end(), llvm::DebugLoc::getCompilerGenerated(), llvm::Instruction::getDebugLoc(), llvm::MemorySSA::getMemoryAccess(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::Instruction::insertInto(), llvm::mapAtomInstance(), llvm::RemapInstruction(), llvm::reverse(), llvm::RF_IgnoreMissingLocals, llvm::RF_NoModuleLevelChanges, and llvm::IRBuilderBase::SetCurrentDebugLocation().

Referenced by unswitchNontrivialInvariants().

buildPartialUnswitchConditionalBranch()

void buildPartialUnswitchConditionalBranch ( BasicBlock & BB, ArrayRef< Value * > Invariants, bool Direction, BasicBlock & UnswitchedSucc, BasicBlock & NormalSucc, bool InsertFreeze, const Instruction * I, AssumptionCache * AC, const DominatorTree & DT )

static

Copy a set of loop invariant values ToDuplicate and insert them at the end of BB and conditionally branch on the copied condition.

We only branch on a single value.

Definition at line 275 of file SimpleLoopUnswitch.cpp.

References Cond, llvm::IRBuilderBase::CreateAnd(), llvm::IRBuilderBase::CreateCondBr(), llvm::IRBuilderBase::CreateFreeze(), llvm::IRBuilderBase::CreateOr(), llvm::DebugLoc::getCompilerGenerated(), I, llvm::isGuaranteedNotToBeUndefOrPoison(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::IRBuilderBase::SetCurrentDebugLocation().

Referenced by unswitchNontrivialInvariants(), and unswitchTrivialBranch().

CalculateUnswitchCostMultiplier()

int CalculateUnswitchCostMultiplier ( const Instruction & TI, const Loop & L, const LoopInfo & LI, const DominatorTree & DT, ArrayRef< NonTrivialUnswitchCandidate > UnswitchCandidates )

static

Cost multiplier is a way to limit potentially exponential behavior of loop-unswitch.

Cost is multiplied in proportion of 2^number of unswitch candidates available. Also consider the number of "sibling" loops with the idea of accounting for previous unswitches that already happened on this cluster of loops. There was an attempt to keep this formula simple, just enough to limit the worst case behavior. Even if it is not that simple now it is still not an attempt to provide a detailed heuristic size prediction.

TODO: Make a proper accounting of "explosion" effect for all kinds of unswitch candidates, making adequate predictions instead of wild guesses. That requires knowing not just the number of "remaining" candidates but also costs of unswitching for each of these candidates.

Definition at line 2827 of file SimpleLoopUnswitch.cpp.

References llvm::LoopInfoBase< BlockT, LoopT >::begin(), llvm::count_if(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::LoopInfoBase< BlockT, LoopT >::end(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::isa(), llvm::isGuard(), llvm::Instruction::isTerminator(), LLVM_DEBUG, llvm::Log2_32(), llvm::size(), llvm::successors(), UnswitchNumInitialUnscaledCandidates, UnswitchParentBlocksDiv, UnswitchSiblingsToplevelDiv, and UnswitchThreshold.

Referenced by findBestNonTrivialUnswitchCandidate().

canonicalizeForInvariantConditionInjection()

void canonicalizeForInvariantConditionInjection ( CmpPredicate & Pred, Value *& LHS, Value *& RHS, BasicBlock *& IfTrue, BasicBlock *& IfFalse, const Loop & L )

static

Tries to canonicalize condition described by:

br (LHS pred RHS), label IfTrue, label IfFalse

into its equivalent where Pred is something that we support for injected invariants (so far it is limited to ult), LHS in canonicalized form is non-invariant and RHS is an invariant.

Definition at line 3016 of file SimpleLoopUnswitch.cpp.

References llvm::CmpInst::getInversePredicate(), llvm::APInt::getSignedMinValue(), llvm::CmpInst::getSwappedPredicate(), llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_ULT, LHS, llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), RHS, and std::swap().

Referenced by collectUnswitchCandidatesWithInjections().

cloneLoopNest()

Loop * cloneLoopNest ( Loop & OrigRootL, Loop * RootParentL, const ValueToValueMapTy & VMap, LoopInfo & LI )

static

Recursively clone the specified loop and all of its children.

The target parent loop for the clone should be provided, or can be null if the clone is a top-level loop. While cloning, all the blocks are mapped with the provided value map. The entire original loop must be present in the value map. The cloned loop is returned.

Definition at line 1372 of file SimpleLoopUnswitch.cpp.

References llvm::LoopBase< BlockT, LoopT >::addChildLoop(), llvm::LoopInfoBase< BlockT, LoopT >::addTopLevelLoop(), llvm::LoopInfoBase< BlockT, LoopT >::AllocateLoop(), assert(), llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::cast(), llvm::LoopInfoBase< BlockT, LoopT >::changeLoopFor(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getNumBlocks(), llvm::LoopBase< BlockT, LoopT >::isInnermost(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::reverse().

Referenced by buildClonedLoops().

collectHomogenousInstGraphLoopInvariants()

TinyPtrVector< Value * > collectHomogenousInstGraphLoopInvariants ( const Loop & L, Instruction & Root, const LoopInfo & LI )

static

Collect all of the loop invariant input values transitively used by the homogeneous instruction graph from a given root.

This essentially walks from a root recursively through loop variant operands which have perform the same logical operation (AND or OR) and finds all inputs which are loop invariant. For some operations these can be re-associated and unswitched out of the loop entirely.

Definition at line 196 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), llvm::PatternMatch::m_LogicalAnd(), llvm::PatternMatch::m_LogicalOr(), llvm::PatternMatch::match(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::TinyPtrVector< EltTy >::push_back(), and skipTrivialSelect().

Referenced by collectUnswitchCandidates(), and unswitchTrivialBranch().

collectUnswitchCandidates()

bool collectUnswitchCandidates ( SmallVectorImpl< NonTrivialUnswitchCandidate > & UnswitchCandidates, IVConditionInfo & PartialIVInfo, Instruction *& PartialIVCondBranch, const Loop & L, const LoopInfo & LI, AAResults & AA, const MemorySSAUpdater * MSSAU )

static

Definition at line 2920 of file SimpleLoopUnswitch.cpp.

References llvm::any_of(), llvm::append_range(), assert(), llvm::cast(), collectHomogenousInstGraphLoopInvariants(), Cond, llvm::dbgs(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::TinyPtrVector< EltTy >::empty(), llvm::findOptionMDForLoop(), llvm::Intrinsic::getDeclarationIfExists(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::hasPartialIVCondition(), I, Info, llvm::isa(), llvm::isGuard(), LLVM_DEBUG, llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_LogicalAnd(), llvm::PatternMatch::m_LogicalOr(), llvm::PatternMatch::match(), MSSAThreshold, llvm::SmallVectorTemplateBase< T, bool >::push_back(), skipTrivialSelect(), and UnswitchGuards.

Referenced by unswitchBestCondition().

collectUnswitchCandidatesWithInjections()

bool collectUnswitchCandidatesWithInjections ( SmallVectorImpl< NonTrivialUnswitchCandidate > & UnswitchCandidates, IVConditionInfo & PartialIVInfo, Instruction *& PartialIVCondBranch, Loop & L, const DominatorTree & DT, const LoopInfo & LI, AAResults & AA, const MemorySSAUpdater * MSSAU )

static

Collect unswitch candidates by invariant conditions that are not immediately present in the loop.

However, they can be injected into the code if we decide it's profitable. An example of such conditions is following:

for (...) { x = load ... if (! x <u C1) break; if (! x <u C2) break; <do something> }

We can unswitch by condition "C1 <=u C2". If that is true, then "x <u C1 <= C2" automatically implies "x <u C2", so we can get rid of one of loop-variant checks in unswitched loop version.

Definition at line 3242 of file SimpleLoopUnswitch.cpp.

References assert(), canonicalizeForInvariantConditionInjection(), llvm::cast(), llvm::dyn_cast(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::CmpInst::ICMP_ULT, InjectInvariantConditions, insertCandidatesWithPendingInjections(), llvm::DominatorTree::isReachableFromEntry(), LHS, llvm::PatternMatch::m_BasicBlock(), llvm::PatternMatch::m_Br(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), RHS, shouldTryInjectBasingOnMetadata(), and shouldTryInjectInvariantCondition().

Referenced by unswitchBestCondition().

computeDomSubtreeCost()

InstructionCost computeDomSubtreeCost ( DomTreeNode & N, const SmallDenseMap< BasicBlock *, InstructionCost, 4 > & BBCostMap, SmallDenseMap< DomTreeNode *, InstructionCost, 4 > & DTCostMap )

static

Recursively compute the cost of a dominator subtree based on the per-block cost map provided.

The recursive computation is memozied into the provided DT-indexed cost map to allow querying it for most nodes in the domtree without it becoming quadratic.

Definition at line 2670 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), and N.

Referenced by findBestNonTrivialUnswitchCandidate().

deleteDeadBlocksFromLoop()

void deleteDeadBlocksFromLoop ( Loop & L, SmallVectorImpl< BasicBlock * > & ExitBlocks, DominatorTree & DT, LoopInfo & LI, MemorySSAUpdater * MSSAU, ScalarEvolution * SE, LPMUpdater & LoopUpdater )

static

Definition at line 1710 of file SimpleLoopUnswitch.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SetVector< T, Vector, Set, N >::count(), llvm::LoopInfoBase< BlockT, LoopT >::destroy(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::erase_if(), llvm::ScalarEvolution::forgetBlockAndLoopDispositions(), llvm::Loop::getName(), llvm::SetVector< T, Vector, Set, N >::insert(), llvm::DominatorTree::isReachableFromEntry(), llvm::LPMUpdater::markLoopAsDeleted(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::MemorySSAUpdater::removeBlocks(), and llvm::successors().

Referenced by unswitchNontrivialInvariants().

deleteDeadClonedBlocks()

void deleteDeadClonedBlocks ( Loop & L, ArrayRef< BasicBlock * > ExitBlocks, ArrayRef< std::unique_ptr< ValueToValueMapTy > > VMaps, DominatorTree & DT, MemorySSAUpdater * MSSAU )

static

Definition at line 1681 of file SimpleLoopUnswitch.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::cast_or_null(), llvm::concat(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::DominatorTree::isReachableFromEntry(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::MemorySSAUpdater::removeBlocks(), and llvm::successors().

Referenced by unswitchNontrivialInvariants().

findBestNonTrivialUnswitchCandidate()

NonTrivialUnswitchCandidate findBestNonTrivialUnswitchCandidate ( ArrayRef< NonTrivialUnswitchCandidate > UnswitchCandidates, const Loop & L, const DominatorTree & DT, const LoopInfo & LI, AssumptionCache & AC, const TargetTransformInfo & TTI, const IVConditionInfo & PartialIVInfo )

static

Definition at line 3340 of file SimpleLoopUnswitch.cpp.

References llvm::all_of(), assert(), CalculateUnswitchCostMultiplier(), llvm::cast(), llvm::CodeMetrics::collectEphemeralValues(), computeDomSubtreeCost(), Cond, CostKind, llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::dyn_cast(), EnableUnswitchCostMultiplier, llvm::BranchInst::getCondition(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), llvm::isGuard(), llvm::Constant::isOneValue(), llvm::IVConditionInfo::KnownValue, LLVM_DEBUG, llvm::PatternMatch::m_LogicalAnd(), llvm::PatternMatch::m_LogicalOr(), llvm::PatternMatch::match(), llvm::predecessors(), llvm::ArrayRef< T >::size(), llvm::SmallPtrSetImplBase::size(), skipTrivialSelect(), llvm::successors(), llvm::TargetTransformInfo::TCK_CodeSize, llvm::TargetTransformInfo::TCK_SizeAndLatency, and UnswitchThreshold.

Referenced by unswitchBestCondition().

getTopMostExitingLoop()

Loop * getTopMostExitingLoop ( const BasicBlock * ExitBB, const LoopInfo & LI )

static

Definition at line 489 of file SimpleLoopUnswitch.cpp.

References llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), and llvm::LoopBase< BlockT, LoopT >::isLoopExiting().

Referenced by unswitchNontrivialInvariants(), unswitchTrivialBranch(), and unswitchTrivialSwitch().

hoistLoopToNewParent()

void hoistLoopToNewParent ( Loop & L, BasicBlock & Preheader, DominatorTree & DT, LoopInfo & LI, MemorySSAUpdater * MSSAU, ScalarEvolution * SE )

static

Hoist the current loop up to the innermost loop containing a remaining exit.

Because we've removed an exit from the loop, we may have changed the set of loops reachable and need to move the current loop up the loop nest or even to an entirely separate nest.

Definition at line 418 of file SimpleLoopUnswitch.cpp.

References llvm::LoopBase< BlockT, LoopT >::addChildLoop(), llvm::LoopInfoBase< BlockT, LoopT >::addTopLevelLoop(), assert(), llvm::LoopInfoBase< BlockT, LoopT >::changeLoopFor(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::erase_if(), llvm::formDedicatedExitBlocks(), llvm::formLCSSA(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), and llvm::LoopBase< BlockT, LoopT >::removeChildLoop().

Referenced by unswitchTrivialBranch(), and unswitchTrivialSwitch().

injectPendingInvariantConditions()

NonTrivialUnswitchCandidate injectPendingInvariantConditions ( NonTrivialUnswitchCandidate Candidate, Loop & L, DominatorTree & DT, LoopInfo & LI, AssumptionCache & AC, MemorySSAUpdater * MSSAU )

static

Materialize pending invariant condition of the given candidate into IR.

The injected loop-invariant condition implies the original loop-variant branch condition, so the materialization turns

loop_block: ... br i1 variant_cond, label InLoopSucc, label OutOfLoopSucc

into

preheader: invariant_cond = LHS pred RHS ... loop_block: br i1 invariant_cond, label InLoopSucc, label OriginalCheck OriginalCheck: br i1 variant_cond, label InLoopSucc, label OutOfLoopSucc ...

Definition at line 3106 of file SimpleLoopUnswitch.cpp.

References llvm::DominatorTreeBase< NodeT, IsPostDom >::applyUpdates(), llvm::MemorySSAUpdater::applyUpdates(), assert(), llvm::cast(), llvm::BasicBlock::Create(), llvm::CmpInst::Create(), llvm::dbgs(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::dyn_cast(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getTerminator(), I, llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::CmpInst::isUnsigned(), LHS, LLVM_DEBUG, RHS, llvm::DominatorTreeBase< NodeT, IsPostDom >::verify(), llvm::LoopInfoBase< BlockT, LoopT >::verify(), llvm::VerifyMemorySSA, and llvm::MemorySSA::verifyMemorySSA().

Referenced by unswitchBestCondition().

insertCandidatesWithPendingInjections()

bool insertCandidatesWithPendingInjections ( SmallVectorImpl< NonTrivialUnswitchCandidate > & UnswitchCandidates, Loop & L, ICmpInst::Predicate Pred, ArrayRef< CompareDesc > Compares, const DominatorTree & DT )

static

Given chain of loop branch conditions looking like: br (Variant < Invariant1) br (Variant < Invariant2) br (Variant < Invariant3) ... collect set of invariant conditions on which we want to unswitch, which look like: Invariant1 <= Invariant2 Invariant2 <= Invariant3 ... Though they might not immediately exist in the IR, we can still inject them.

Definition at line 3204 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::ArrayRef< T >::begin(), llvm::ArrayRef< T >::end(), llvm::CmpInst::getNonStrictPredicate(), llvm::ICmpInst::isRelational(), llvm::CmpInst::isStrictPredicate(), LHS, llvm::Next, llvm::SmallVectorTemplateBase< T, bool >::push_back(), RHS, and llvm::ArrayRef< T >::size().

Referenced by collectUnswitchCandidatesWithInjections().

isSafeForNoNTrivialUnswitching()

bool isSafeForNoNTrivialUnswitching ( Loop & L, LoopInfo & LI )

static

Definition at line 3297 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::containsIrreducibleCFG(), llvm::dbgs(), llvm::dyn_cast(), I, llvm::isa(), LLVM_DEBUG, and llvm::LoopBlocksRPO::perform().

Referenced by unswitchLoop().

postUnswitch()

void postUnswitch	(	Loop &	L,
		LPMUpdater &	U,
		StringRef	LoopName,
		bool	CurrentLoopValid,
		bool	PartiallyInvariant,
		bool	InjectedCondition,
		ArrayRef< Loop * >	NewLoops )

Definition at line 2147 of file SimpleLoopUnswitch.cpp.

References llvm::ArrayRef< T >::empty(), llvm::MDNode::get(), llvm::MDString::get(), and llvm::makePostTransformationMetadata().

Referenced by unswitchLoop(), and unswitchNontrivialInvariants().

rebuildLoopAfterUnswitch()

bool rebuildLoopAfterUnswitch ( Loop & L, ArrayRef< BasicBlock * > ExitBlocks, LoopInfo & LI, SmallVectorImpl< Loop * > & HoistedLoops, ScalarEvolution * SE )

static

Rebuild a loop after unswitching removes some subset of blocks and edges.

The removal may have removed some child loops entirely but cannot have disturbed any remaining child loops. However, they may need to be hoisted to the parent loop (or to be top-level loops). The original loop may be completely removed.

The sibling loops resulting from this update are returned. If the original loop remains a valid loop, it will be the first entry in this list with all of the newly sibling loops following it.

Returns true if the loop remains a loop after unswitching, and false if it is no longer a loop after unswitching (and should not continue to be referenced).

Definition at line 1915 of file SimpleLoopUnswitch.cpp.

References llvm::LoopBase< BlockT, LoopT >::addChildLoop(), llvm::LoopInfoBase< BlockT, LoopT >::addTopLevelLoop(), assert(), llvm::LoopInfoBase< BlockT, LoopT >::changeLoopFor(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::LoopInfoBase< BlockT, LoopT >::destroy(), llvm::SmallPtrSetImplBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::erase_if(), llvm::find(), llvm::ScalarEvolution::forgetBlockAndLoopDispositions(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopDepth(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::SmallPtrSetImpl< PtrType >::insert(), LHS, llvm::make_range(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), recomputeLoopBlockSet(), llvm::LoopBase< BlockT, LoopT >::removeChildLoop(), llvm::LoopInfoBase< BlockT, LoopT >::removeLoop(), llvm::SmallVectorImpl< T >::reserve(), RHS, llvm::ArrayRef< T >::size(), and llvm::stable_sort().

Referenced by unswitchNontrivialInvariants().

recomputeLoopBlockSet()

SmallPtrSet< const BasicBlock *, 16 > recomputeLoopBlockSet ( Loop & L, LoopInfo & LI )

static

Recompute the set of blocks in a loop after unswitching.

This walks from the original headers predecessors to rebuild the loop. We take advantage of the fact that new blocks can't have been added, and so we filter by the original loop's blocks. This also handles potentially unreachable code that we don't want to explore but might be found examining the predecessors of the header.

If the original loop is no longer a loop, this will return an empty set. If it remains a loop, all the blocks within it will be added to the set (including those blocks in inner loops).

Definition at line 1804 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::SmallPtrSetImplBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::predecessors(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by rebuildLoopAfterUnswitch().

replaceLoopInvariantUses()

void replaceLoopInvariantUses ( const Loop & L, Value * Invariant, Constant & Replacement )

static

Definition at line 238 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::dyn_cast(), llvm::isa(), llvm::make_early_inc_range(), and llvm::Value::uses().

Referenced by unswitchTrivialBranch().

rewritePHINodesForExitAndUnswitchedBlocks()

void rewritePHINodesForExitAndUnswitchedBlocks ( BasicBlock & ExitBB, BasicBlock & UnswitchedBB, BasicBlock & OldExitingBB, BasicBlock & OldPH, bool FullUnswitch )

static

Rewrite the PHI nodes in the loop exit basic block and the split off unswitched block.

Because the exit block remains an exit from the loop, this rewrites the LCSSA PHI nodes in it to remove the unswitched edge and introduces PHI nodes into the unswitched basic block to select between the value in the old preheader and the loop exit.

Definition at line 372 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::BasicBlock::begin(), llvm::PHINode::Create(), and llvm::BasicBlock::phis().

Referenced by unswitchTrivialBranch(), and unswitchTrivialSwitch().

rewritePHINodesForUnswitchedExitBlock()

void rewritePHINodesForUnswitchedExitBlock ( BasicBlock & UnswitchedBB, BasicBlock & OldExitingBB, BasicBlock & OldPH )

static

Rewrite the PHI nodes in an unswitched loop exit basic block.

Requires that the loop exit and unswitched basic block are the same, and that the exiting block was a unique predecessor of that block. Rewrites the PHI nodes in that block such that what were LCSSA PHI nodes become trivial PHI nodes from the old preheader that now contains the unswitched terminator.

Definition at line 350 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::BasicBlock::phis(), and llvm::seq().

Referenced by unswitchTrivialBranch(), and unswitchTrivialSwitch().

shouldInsertFreeze()

bool shouldInsertFreeze ( Loop & L, Instruction & TI, DominatorTree & DT, AssumptionCache & AC )

static

Definition at line 3497 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::cast(), llvm::ICFLoopSafetyInfo::computeLoopSafetyInfo(), Cond, llvm::dyn_cast(), FreezeLoopUnswitchCond, llvm::isa(), llvm::isGuaranteedNotToBeUndefOrPoison(), llvm::ICFLoopSafetyInfo::isGuaranteedToExecute(), and skipTrivialSelect().

Referenced by unswitchBestCondition().

shouldTryInjectBasingOnMetadata()

bool shouldTryInjectBasingOnMetadata	(	const BranchInst *	BI,
		const BasicBlock *	TakenSucc )

Returns true, if metadata on BI allows us to optimize branching into TakenSucc via injection of invariant conditions.

The branch should be not enough and not previously unswitched, the information about this comes from the metadata.

Definition at line 3066 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::extractBranchWeights(), llvm::BranchInst::getSuccessor(), InjectInvariantConditionHotnesThreshold, llvm::SmallVectorTemplateCommon< T, typename >::size(), and T.

Referenced by collectUnswitchCandidatesWithInjections().

shouldTryInjectInvariantCondition()

bool shouldTryInjectInvariantCondition ( const ICmpInst::Predicate Pred, const Value * LHS, const Value * RHS, const BasicBlock * IfTrue, const BasicBlock * IfFalse, const Loop & L )

static

Returns true, if predicate described by ( Pred, LHS, RHS ) succeeding into blocks ( IfTrue, IfFalse) can be optimized by injecting a loop-invariant condition.

Definition at line 3044 of file SimpleLoopUnswitch.cpp.

References llvm::CmpInst::ICMP_ULT, LHS, and RHS.

Referenced by collectUnswitchCandidatesWithInjections().

skipTrivialSelect()

Value * skipTrivialSelect ( Value * Cond )

static

Definition at line 181 of file SimpleLoopUnswitch.cpp.

References Cond, llvm::PatternMatch::m_One(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Zero(), and llvm::PatternMatch::match().

Referenced by collectHomogenousInstGraphLoopInvariants(), collectUnswitchCandidates(), findBestNonTrivialUnswitchCandidate(), shouldInsertFreeze(), unswitchAllTrivialConditions(), unswitchNontrivialInvariants(), and unswitchTrivialBranch().

STATISTIC() [1/7]

STATISTIC	(	NumBranches	,
		"Number of branches unswitched"	)

STATISTIC() [2/7]

STATISTIC	(	NumCostMultiplierSkipped	,
		"Number of unswitch candidates that had their cost multiplier skipped"	)

STATISTIC() [3/7]

STATISTIC	(	NumGuards	,
		"Number of guards turned into branches for unswitching"	)

STATISTIC() [4/7]

STATISTIC	(	NumInvariantConditionsInjected	,
		"Number of invariant conditions injected and unswitched"	)

STATISTIC() [5/7]

STATISTIC	(	NumSelects	,
		"Number of selects turned into branches for unswitching"	)

STATISTIC() [6/7]

STATISTIC	(	NumSwitches	,
		"Number of switches unswitched"	)

STATISTIC() [7/7]

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

turnGuardIntoBranch()

BranchInst * turnGuardIntoBranch ( IntrinsicInst * GI, Loop & L, DominatorTree & DT, LoopInfo & LI, MemorySSAUpdater * MSSAU )

static

Turns a llvm.experimental.guard intrinsic into implicit control flow branch, making the following replacement:

–code before guard– call void (i1, ...) @llvm.experimental.guard(i1 cond) [ "deopt"() ] –code after guard–

into

–code before guard– br i1 cond, label guarded, label deopt

guarded: –code after guard–

deopt: call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ] unreachable

It also makes all relevant DT and LI updates, so that all structures are in valid state after this transform.

Definition at line 2772 of file SimpleLoopUnswitch.cpp.

References llvm::MemorySSA::BeforeTerminator, llvm::cast(), llvm::dbgs(), llvm::CallBase::getArgOperand(), llvm::Value::getContext(), llvm::ConstantInt::getFalse(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::MemorySSA::getMemoryAccess(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::Instruction::getMetadata(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), LLVM_DEBUG, llvm::MemorySSAUpdater::moveAllAfterSpliceBlocks(), llvm::Instruction::moveBefore(), llvm::MemorySSAUpdater::moveToPlace(), llvm::CallBase::setArgOperand(), llvm::Value::setName(), llvm::SplitBlockAndInsertIfThen(), llvm::BranchInst::swapSuccessors(), llvm::LoopInfoBase< BlockT, LoopT >::verify(), llvm::VerifyLoopInfo, llvm::VerifyMemorySSA, and llvm::MemorySSA::verifyMemorySSA().

Referenced by unswitchBestCondition().

turnSelectIntoBranch()

BranchInst * turnSelectIntoBranch ( SelectInst * SI, DominatorTree & DT, LoopInfo & LI, MemorySSAUpdater * MSSAU, AssumptionCache * AC )

static

Turns a select instruction into implicit control flow branch, making the following replacement:

head: –code before select– select cond, trueval, falseval –code after select–

into

head: –code before select– br i1 cond, label then, label tail

then: br tail

tail: phi [ trueval, then ], [ falseval, head] unreachable

It also makes all relevant DT and LI updates, so that all structures are in valid state after this transform.

Definition at line 2721 of file SimpleLoopUnswitch.cpp.

References llvm::cast(), llvm::PHINode::Create(), llvm::dbgs(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::BasicBlock::getTerminator(), LLVM_DEBUG, llvm::MemorySSAUpdater::moveAllAfterSpliceBlocks(), llvm::SplitBlockAndInsertIfThen(), llvm::VerifyMemorySSA, and llvm::MemorySSA::verifyMemorySSA().

Referenced by unswitchBestCondition().

unswitchAllTrivialConditions()

bool unswitchAllTrivialConditions ( Loop & L, DominatorTree & DT, LoopInfo & LI, ScalarEvolution * SE, MemorySSAUpdater * MSSAU )

static

This routine scans the loop to find a branch or switch which occurs before any side effects occur.

These can potentially be unswitched without duplicating the loop. If a branch or switch is successfully unswitched the scanning continues to see if subsequent branches or switches have become trivial. Once all trivial candidates have been unswitched, this routine returns.

The return value indicates whether anything was unswitched (and therefore changed).

If SE is not null, it will be updated based on the potential loop SCEVs invalidated by this.

Definition at line 1056 of file SimpleLoopUnswitch.cpp.

References llvm::any_of(), llvm::cast(), Changed, llvm::dyn_cast(), llvm::MemorySSA::getBlockDefs(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::BasicBlock::getTerminator(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), skipTrivialSelect(), unswitchTrivialBranch(), and unswitchTrivialSwitch().

Referenced by unswitchLoop().

unswitchBestCondition()

bool unswitchBestCondition ( Loop & L, DominatorTree & DT, LoopInfo & LI, AssumptionCache & AC, AAResults & AA, TargetTransformInfo & TTI, ScalarEvolution * SE, MemorySSAUpdater * MSSAU, LPMUpdater & LoopUpdater )

static

Definition at line 3517 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::cast(), collectUnswitchCandidates(), collectUnswitchCandidatesWithInjections(), llvm::dbgs(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), findBestNonTrivialUnswitchCandidate(), llvm::findOptionMDForLoop(), injectPendingInvariantConditions(), llvm::IVConditionInfo::InstToDuplicate, llvm::isGuaranteedNotToBeUndefOrPoison(), llvm::isGuard(), LLVM_DEBUG, shouldInsertFreeze(), llvm::SmallVectorTemplateCommon< T, typename >::size(), turnGuardIntoBranch(), turnSelectIntoBranch(), unswitchNontrivialInvariants(), and UnswitchThreshold.

Referenced by unswitchLoop().

unswitchLoop()

bool unswitchLoop ( Loop & L, DominatorTree & DT, LoopInfo & LI, AssumptionCache & AC, AAResults & AA, TargetTransformInfo & TTI, bool Trivial, bool NonTrivial, ScalarEvolution * SE, MemorySSAUpdater * MSSAU, ProfileSummaryInfo * PSI, BlockFrequencyInfo * BFI, LPMUpdater & LoopUpdater )

static

Unswitch control flow predicated on loop invariant conditions.

This first hoists all branches or switches which are trivial (IE, do not require duplicating any part of the loop) out of the loop body. It then looks at other loop invariant control flows and tries to unswitch those as well by cloning the loop if the result is small enough.

The DT, LI, AC, AA, TTI parameters are required analyses that are also updated based on the unswitch. The MSSA analysis is also updated if valid (i.e. its use is enabled).

If either NonTrivial is true or the flag EnableNonTrivialUnswitch is true, we will attempt to do non-trivial unswitching as well as trivial unswitching.

The postUnswitch function will be run after unswitching is complete with information on whether or not the provided loop remains a loop and a list of new sibling loops created.

If SE is non-null, we will update that analysis based on the unswitching done.

Definition at line 3610 of file SimpleLoopUnswitch.cpp.

References llvm::append_range(), assert(), llvm::dbgs(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), EnableNonTrivialUnswitch, F, llvm::ProfileSummaryInfo::hasProfileSummary(), llvm::ProfileSummaryInfo::isColdBlock(), isSafeForNoNTrivialUnswitching(), LLVM_DEBUG, llvm::SmallVectorImpl< T >::pop_back_val(), postUnswitch(), unswitchAllTrivialConditions(), and unswitchBestCondition().

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

unswitchNontrivialInvariants()

void unswitchNontrivialInvariants ( Loop & L, Instruction & TI, ArrayRef< Value * > Invariants, IVConditionInfo & PartialIVInfo, DominatorTree & DT, LoopInfo & LI, AssumptionCache & AC, ScalarEvolution * SE, MemorySSAUpdater * MSSAU, LPMUpdater & LoopUpdater, bool InsertFreeze, bool InjectedCondition )

static

Definition at line 2184 of file SimpleLoopUnswitch.cpp.

References llvm::all_of(), llvm::DominatorTreeBase< NodeT, IsPostDom >::applyUpdates(), llvm::ArrayRef(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::begin(), llvm::SetVector< T, Vector, Set, N >::begin(), buildClonedLoopBlocks(), buildClonedLoops(), buildPartialInvariantUnswitchConditionalBranch(), buildPartialUnswitchConditionalBranch(), llvm::SwitchInst::cases(), llvm::cast(), llvm::SmallVectorImpl< T >::clear(), llvm::Instruction::clone(), llvm::ICFLoopSafetyInfo::computeLoopSafetyInfo(), llvm::concat(), Cond, llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SetVector< T, Vector, Set, N >::count(), llvm::BranchInst::Create(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, deleteDeadBlocksFromLoop(), deleteDeadClonedBlocks(), llvm::DominatorTree::dominates(), llvm::Instruction::dropLocation(), DropNonTrivialImplicitNullChecks, llvm::dyn_cast(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::BasicBlock::end(), llvm::Instruction::eraseFromParent(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::ScalarEvolution::forgetBlockAndLoopDispositions(), llvm::ScalarEvolution::forgetLoop(), llvm::ScalarEvolution::forgetTopmostLoop(), llvm::formDedicatedExitBlocks(), llvm::formLCSSA(), FreezeLoopUnswitchCond, llvm::BranchInst::getCondition(), llvm::Value::getContext(), llvm::Instruction::getDebugLoc(), llvm::SwitchInst::getDefaultDest(), llvm::DebugLoc::getDropped(), llvm::ConstantInt::getFalse(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::Instruction::getMetadata(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), getTopMostExitingLoop(), llvm::ConstantInt::getTrue(), llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::Instruction::insertInto(), llvm::IVConditionInfo::InstToDuplicate, llvm::isa(), llvm::BranchInst::isConditional(), llvm::ICFLoopSafetyInfo::isGuaranteedToExecute(), llvm::Constant::isOneValue(), llvm::IVConditionInfo::KnownValue, llvm::PatternMatch::m_LogicalAnd(), llvm::PatternMatch::m_LogicalOr(), llvm::make_early_inc_range(), llvm::PatternMatch::match(), llvm::Instruction::moveBefore(), llvm::LoopBlocksRPO::perform(), postUnswitch(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), rebuildLoopAfterUnswitch(), llvm::MemorySSAUpdater::removeDuplicatePhiEdgesBetween(), llvm::MemorySSAUpdater::removeEdge(), llvm::BasicBlock::removePredecessor(), llvm::SmallVectorImpl< T >::reserve(), llvm::BranchInst::setCondition(), llvm::Instruction::setDebugLoc(), llvm::Instruction::setMetadata(), llvm::BranchInst::setSuccessor(), llvm::ArrayRef< T >::size(), llvm::SetVector< T, Vector, Set, N >::size(), skipTrivialSelect(), llvm::SplitEdge(), llvm::MemorySSAUpdater::updateExitBlocksForClonedLoop(), llvm::MemorySSAUpdater::updateForClonedLoop(), llvm::DominatorTreeBase< NodeT, IsPostDom >::verify(), llvm::LoopInfoBase< BlockT, LoopT >::verify(), llvm::VerifyMemorySSA, llvm::MemorySSA::verifyMemorySSA(), and visitDomSubTree().

Referenced by unswitchBestCondition().

unswitchTrivialBranch()

bool unswitchTrivialBranch ( Loop & L, BranchInst & BI, DominatorTree & DT, LoopInfo & LI, ScalarEvolution * SE, MemorySSAUpdater * MSSAU )

static

Unswitch a trivial branch if the condition is loop invariant.

This routine should only be called when loop code leading to the branch has been validated as trivial (no side effects). This routine checks if the condition is invariant and one of the successors is a loop exit. This allows us to unswitch without duplicating the loop, making it trivial.

If this routine fails to unswitch the branch it returns false.

If the branch can be unswitched, this routine splits the preheader and hoists the branch above that split. Preserves loop simplified form (splitting the exit block as necessary). It simplifies the branch within the loop to an unconditional branch but doesn't remove it entirely. Further cleanup can be done with some simplifycfg like pass.

If SE is not null, it will be updated based on the potential loop SCEVs invalidated by this.

Definition at line 518 of file SimpleLoopUnswitch.cpp.

References llvm::MemorySSAUpdater::applyInsertUpdates(), areLoopExitPHIsLoopInvariant(), assert(), buildPartialUnswitchConditionalBranch(), llvm::Instruction::clone(), collectHomogenousInstGraphLoopInvariants(), Cond, llvm::BranchInst::Create(), llvm::dbgs(), llvm::DominatorTreeBase< NodeT, IsPostDom >::deleteEdge(), llvm::dyn_cast(), llvm::TinyPtrVector< EltTy >::empty(), llvm::BasicBlock::end(), llvm::Instruction::eraseFromParent(), llvm::ScalarEvolution::forgetBlockAndLoopDispositions(), llvm::ScalarEvolution::forgetLoop(), llvm::ScalarEvolution::forgetTopmostLoop(), FreezeLoopUnswitchCond, llvm::BranchInst::getCondition(), llvm::Value::getContext(), llvm::Instruction::getDebugLoc(), llvm::ConstantInt::getFalse(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), getTopMostExitingLoop(), llvm::ConstantInt::getTrue(), hoistLoopToNewParent(), llvm::cfg::Insert, llvm::DominatorTreeBase< NodeT, IsPostDom >::insertEdge(), llvm::Instruction::insertInto(), llvm::BranchInst::isConditional(), LLVM_DEBUG, llvm::PatternMatch::m_LogicalAnd(), llvm::PatternMatch::m_LogicalAnd(), llvm::PatternMatch::m_LogicalOr(), llvm::PatternMatch::m_LogicalOr(), llvm::PatternMatch::match(), llvm::Instruction::moveBefore(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::TinyPtrVector< EltTy >::push_back(), llvm::MemorySSAUpdater::removeEdge(), replaceLoopInvariantUses(), rewritePHINodesForExitAndUnswitchedBlocks(), rewritePHINodesForUnswitchedExitBlock(), llvm::BranchInst::setCondition(), llvm::Instruction::setDebugLoc(), llvm::BranchInst::setSuccessor(), skipTrivialSelect(), llvm::SplitBlock(), llvm::SplitEdge(), llvm::VerifyMemorySSA, and llvm::MemorySSA::verifyMemorySSA().

Referenced by unswitchAllTrivialConditions().

unswitchTrivialSwitch()

bool unswitchTrivialSwitch ( Loop & L, SwitchInst & SI, DominatorTree & DT, LoopInfo & LI, ScalarEvolution * SE, MemorySSAUpdater * MSSAU )

static

Unswitch a trivial switch if the condition is loop invariant.

This routine should only be called when loop code leading to the switch has been validated as trivial (no side effects). This routine checks if the condition is invariant and that at least one of the successors is a loop exit. This allows us to unswitch without duplicating the loop, making it trivial.

If this routine fails to unswitch the switch it returns false.

If the switch can be unswitched, this routine splits the preheader and copies the switch above that split. If the default case is one of the exiting cases, it copies the non-exiting cases and points them at the new preheader. If the default case is not exiting, it copies the exiting cases and points the default at the preheader. It preserves loop simplified form (splitting the exit blocks as necessary). It simplifies the switch within the loop by removing now-dead cases. If the default case is one of those unswitched, it replaces its destination with a new basic block containing only unreachable. Such basic blocks, while technically loop exits, are not considered for unswitching so this is a stable transform and the same switch will not be revisited. If after unswitching there is only a single in-loop successor, the switch is further simplified to an unconditional branch. Still more cleanup can be done with some simplifycfg like pass.

If SE is not null, it will be updated based on the potential loop SCEVs invalidated by this.

Definition at line 752 of file SimpleLoopUnswitch.cpp.

References llvm::SwitchInstProfUpdateWrapper::addCase(), llvm::all_of(), llvm::DominatorTreeBase< NodeT, IsPostDom >::applyUpdates(), llvm::MemorySSAUpdater::applyUpdates(), areLoopExitPHIsLoopInvariant(), assert(), llvm::BasicBlock::begin(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::BranchInst::Create(), llvm::SwitchInst::Create(), llvm::dbgs(), llvm::DominatorTreeBase< NodeT, IsPostDom >::Delete, llvm::drop_begin(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::Instruction::eraseFromParent(), llvm::SwitchInstProfUpdateWrapper::eraseFromParent(), llvm::ScalarEvolution::forgetLoop(), llvm::ScalarEvolution::forgetTopmostLoop(), llvm::SwitchInst::CaseHandleImpl< SwitchInstT, ConstantIntT, BasicBlockT >::getCaseSuccessor(), llvm::SwitchInst::CaseHandleImpl< SwitchInstT, ConstantIntT, BasicBlockT >::getCaseValue(), llvm::Instruction::getDebugLoc(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::SwitchInst::CaseHandleImpl< SwitchInstT, ConstantIntT, BasicBlockT >::getSuccessorIndex(), llvm::SwitchInstProfUpdateWrapper::getSuccessorWeight(), llvm::BasicBlock::getTerminator(), getTopMostExitingLoop(), hoistLoopToNewParent(), llvm::DominatorTreeBase< NodeT, IsPostDom >::Insert, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), LLVM_DEBUG, llvm::pred_empty(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SwitchInstProfUpdateWrapper::removeCase(), llvm::BasicBlock::removePredecessor(), llvm::reverse(), rewritePHINodesForExitAndUnswitchedBlocks(), rewritePHINodesForUnswitchedExitBlock(), llvm::Instruction::setDebugLoc(), llvm::SwitchInst::setDefaultDest(), llvm::SwitchInstProfUpdateWrapper::setSuccessorWeight(), llvm::BasicBlock::size(), llvm::SmallVectorTemplateCommon< T, typename >::size(), llvm::SplitBlock(), llvm::SplitEdge(), llvm::DominatorTreeBase< NodeT, IsPostDom >::verify(), llvm::VerifyMemorySSA, and llvm::MemorySSA::verifyMemorySSA().

Referenced by unswitchAllTrivialConditions().

visitDomSubTree()

template<typename CallableT>

void visitDomSubTree	(	DominatorTree &	DT,
		BasicBlock *	BB,
		CallableT	Callable )

Helper to visit a dominator subtree, invoking a callable on each node.

Returning false at any point will stop walking past that node of the tree.

Definition at line 2124 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::SmallPtrSetImpl< PtrType >::insert(), N, llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by unswitchNontrivialInvariants().

Variable Documentation

DropNonTrivialImplicitNullChecks

cl::opt< bool > DropNonTrivialImplicitNullChecks("simple-loop-unswitch-drop-non-trivial-implicit-null-checks", cl::init(false), cl::Hidden, cl::desc("If enabled, drop make.implicit metadata in unswitched implicit " "null checks to save time analyzing if we can keep it.")) ( "simple-loop-unswitch-drop-non-trivial-implicit-null-checks" , cl::init(false) , cl::Hidden , cl::desc("If enabled, drop make.implicit metadata in unswitched implicit " "null checks to save time analyzing if we can keep it.")  )

static

Referenced by unswitchNontrivialInvariants().

EnableNonTrivialUnswitch

cl::opt< bool > EnableNonTrivialUnswitch("enable-nontrivial-unswitch", cl::init(false), cl::Hidden, cl::desc("Forcibly enables non-trivial loop unswitching rather than " "following the configuration passed into the pass.")) ( "enable-nontrivial-unswitch" , cl::init(false) , cl::Hidden , cl::desc("Forcibly enables non-trivial loop unswitching rather than " "following the configuration passed into the pass.")  )

static

Referenced by unswitchLoop().

EnableUnswitchCostMultiplier

cl::opt< bool > EnableUnswitchCostMultiplier("enable-unswitch-cost-multiplier", cl::init(true), cl::Hidden, cl::desc("Enable unswitch cost multiplier that prohibits exponential " "explosion in nontrivial unswitch.")) ( "enable-unswitch-cost-multiplier" , cl::init(true) , cl::Hidden , cl::desc("Enable unswitch cost multiplier that prohibits exponential " "explosion in nontrivial unswitch.")  )

static

Referenced by findBestNonTrivialUnswitchCandidate().

FreezeLoopUnswitchCond

cl::opt< bool > FreezeLoopUnswitchCond("freeze-loop-unswitch-cond", cl::init(true), cl::Hidden, cl::desc("If enabled, the freeze instruction will be added to condition " "of loop unswitch to prevent miscompilation.")) ( "freeze-loop-unswitch-cond" , cl::init(true) , cl::Hidden , cl::desc("If enabled, the freeze instruction will be added to condition " "of loop unswitch to prevent miscompilation.")  )

static

Referenced by shouldInsertFreeze(), unswitchNontrivialInvariants(), and unswitchTrivialBranch().

InjectInvariantConditionHotnesThreshold

cl::opt< unsigned > InjectInvariantConditionHotnesThreshold("simple-loop-unswitch-inject-invariant-condition-hotness-threshold", cl::Hidden, cl::desc("Only try to inject loop invariant conditions and " "unswitch on them to eliminate branches that are " "not-taken 1/<this option> times or less."), cl::init(16)) ( "simple-loop-unswitch-inject-invariant-condition-hotness-threshold" , cl::Hidden , cl::desc("Only try to inject loop invariant conditions and " "unswitch on them to eliminate branches that are " "not-taken 1/<this option> times or less.") , cl::init(16)  )

static

Referenced by shouldTryInjectBasingOnMetadata().

InjectInvariantConditions

cl::opt< bool > InjectInvariantConditions("simple-loop-unswitch-inject-invariant-conditions", cl::Hidden, cl::desc("Whether we should inject new invariants and unswitch them to " "eliminate some existing (non-invariant) conditions."), cl::init(true)) ( "simple-loop-unswitch-inject-invariant-conditions" , cl::Hidden , cl::desc("Whether we should inject new invariants and unswitch them to " "eliminate some existing (non-invariant) conditions.") , cl::init(true)  )

static

Referenced by collectUnswitchCandidatesWithInjections().

MSSAThreshold

cl::opt< unsigned > MSSAThreshold("simple-loop-unswitch-memoryssa-threshold", cl::desc("Max number of memory uses to explore during " "partial unswitching analysis"), cl::init(100), cl::Hidden) ( "simple-loop-unswitch-memoryssa-threshold" , cl::desc("Max number of memory uses to explore during " "partial unswitching analysis") , cl::init(100) , cl::Hidden  )

static

Referenced by collectUnswitchCandidates(), and llvm::hasPartialIVCondition().

UnswitchGuards

cl::opt< bool > UnswitchGuards("simple-loop-unswitch-guards", cl::init(true), cl::Hidden, cl::desc("If enabled, simple loop unswitching will also consider " "llvm.experimental.guard intrinsics as unswitch candidates.")) ( "simple-loop-unswitch-guards" , cl::init(true) , cl::Hidden , cl::desc("If enabled, simple loop unswitching will also consider " "llvm.experimental.guard intrinsics as unswitch candidates.")  )

static

Referenced by collectUnswitchCandidates().

UnswitchNumInitialUnscaledCandidates

cl::opt< int > UnswitchNumInitialUnscaledCandidates("unswitch-num-initial-unscaled-candidates", cl::init(8), cl::Hidden, cl::desc("Number of unswitch candidates that are ignored when calculating " "cost multiplier.")) ( "unswitch-num-initial-unscaled-candidates" , cl::init(8) , cl::Hidden , cl::desc("Number of unswitch candidates that are ignored when calculating " "cost multiplier.")  )

static

Referenced by CalculateUnswitchCostMultiplier().

UnswitchParentBlocksDiv

cl::opt< int > UnswitchParentBlocksDiv("unswitch-parent-blocks-div", cl::init(8), cl::Hidden, cl::desc("Outer loop size divisor for cost multiplier.")) ( "unswitch-parent-blocks-div" , cl::init(8) , cl::Hidden , cl::desc("Outer loop size divisor for cost multiplier.")  )

static

Referenced by CalculateUnswitchCostMultiplier().

UnswitchSiblingsToplevelDiv

cl::opt< int > UnswitchSiblingsToplevelDiv("unswitch-siblings-toplevel-div", cl::init(2), cl::Hidden, cl::desc("Toplevel siblings divisor for cost multiplier.")) ( "unswitch-siblings-toplevel-div" , cl::init(2) , cl::Hidden , cl::desc("Toplevel siblings divisor for cost multiplier.")  )

static

Referenced by CalculateUnswitchCostMultiplier().

UnswitchThreshold

cl::opt< int > UnswitchThreshold("unswitch-threshold", cl::init(50), cl::Hidden, cl::desc("The cost threshold for unswitching a loop.")) ( "unswitch-threshold" , cl::init(50) , cl::Hidden , cl::desc("The cost threshold for unswitching a loop.")  )

static

Referenced by CalculateUnswitchCostMultiplier(), findBestNonTrivialUnswitchCandidate(), and unswitchBestCondition().