LLVM  7.0.0svn
Macros | Functions | Variables
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/CFG.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopPass.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/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GenericDomTree.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <numeric>
#include <utility>
Include dependency graph for SimpleLoopUnswitch.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "simple-loop-unswitch"
 

Functions

 STATISTIC (NumBranches, "Number of branches unswitched")
 
 STATISTIC (NumSwitches, "Number of switches unswitched")
 
 STATISTIC (NumTrivial, "Number of unswitches that are trivial")
 
static void replaceLoopUsesWithConstant (Loop &L, Value &LIC, Constant &Replacement)
 
static bool areLoopExitPHIsLoopInvariant (Loop &L, BasicBlock &ExitingBB, BasicBlock &ExitBB)
 Check that all the LCSSA PHI nodes in the loop exit block have trivial incoming values along this edge. More...
 
static void rewritePHINodesForUnswitchedExitBlock (BasicBlock &UnswitchedBB, BasicBlock &OldExitingBB, BasicBlock &OldPH)
 Rewrite the PHI nodes in an unswitched loop exit basic block. More...
 
static void rewritePHINodesForExitAndUnswitchedBlocks (BasicBlock &ExitBB, BasicBlock &UnswitchedBB, BasicBlock &OldExitingBB, BasicBlock &OldPH)
 Rewrite the PHI nodes in the loop exit basic block and the split off unswitched block. More...
 
static bool unswitchTrivialBranch (Loop &L, BranchInst &BI, DominatorTree &DT, LoopInfo &LI)
 Unswitch a trivial branch if the condition is loop invariant. More...
 
static bool unswitchTrivialSwitch (Loop &L, SwitchInst &SI, DominatorTree &DT, LoopInfo &LI)
 Unswitch a trivial switch if the condition is loop invariant. More...
 
static bool unswitchAllTrivialConditions (Loop &L, DominatorTree &DT, LoopInfo &LI)
 This routine scans the loop to find a branch or switch which occurs before any side effects occur. More...
 
static BasicBlockbuildClonedLoopBlocks (Loop &L, BasicBlock *LoopPH, BasicBlock *SplitBB, ArrayRef< BasicBlock *> ExitBlocks, BasicBlock *ParentBB, BasicBlock *UnswitchedSuccBB, BasicBlock *ContinueSuccBB, const SmallPtrSetImpl< BasicBlock *> &SkippedLoopAndExitBlocks, ValueToValueMapTy &VMap, SmallVectorImpl< DominatorTree::UpdateType > &DTUpdates, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
 Build the cloned blocks for an unswitched copy of the given loop. More...
 
static LoopcloneLoopNest (Loop &OrigRootL, Loop *RootParentL, const ValueToValueMapTy &VMap, LoopInfo &LI)
 Recursively clone the specified loop and all of its children. More...
 
static LoopbuildClonedLoops (Loop &OrigL, ArrayRef< BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap, LoopInfo &LI, SmallVectorImpl< Loop *> &NonChildClonedLoops)
 Build the cloned loops of an original loop from unswitching. More...
 
static void deleteDeadBlocksFromLoop (Loop &L, const SmallVectorImpl< BasicBlock *> &DeadBlocks, SmallVectorImpl< BasicBlock *> &ExitBlocks, DominatorTree &DT, LoopInfo &LI)
 
static SmallPtrSet< const BasicBlock *, 16 > recomputeLoopBlockSet (Loop &L, LoopInfo &LI)
 Recompute the set of blocks in a loop after unswitching. More...
 
static bool rebuildLoopAfterUnswitch (Loop &L, ArrayRef< BasicBlock *> ExitBlocks, LoopInfo &LI, SmallVectorImpl< Loop *> &HoistedLoops)
 Rebuild a loop after unswitching removes some subset of blocks and edges. More...
 
template<typename CallableT >
void visitDomSubTree (DominatorTree &DT, BasicBlock *BB, CallableT Callable)
 Helper to visit a dominator subtree, invoking a callable on each node. More...
 
static bool unswitchInvariantBranch (Loop &L, BranchInst &BI, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, function_ref< void(bool, ArrayRef< Loop *>)> NonTrivialUnswitchCB)
 Take an invariant branch that has been determined to be safe and worthwhile to unswitch despite being non-trivial to do so and perform the unswitch. More...
 
static int computeDomSubtreeCost (DomTreeNode &N, const SmallDenseMap< BasicBlock *, int, 4 > &BBCostMap, SmallDenseMap< DomTreeNode *, int, 4 > &DTCostMap)
 Recursively compute the cost of a dominator subtree based on the per-block cost map provided. More...
 
static bool unswitchLoop (Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, TargetTransformInfo &TTI, bool NonTrivial, function_ref< void(bool, ArrayRef< Loop *>)> NonTrivialUnswitchCB)
 Unswitch control flow predicated on loop invariant conditions. More...
 
 INITIALIZE_PASS_BEGIN (SimpleLoopUnswitchLegacyPass, "simple-loop-unswitch", "Simple unswitch loops", false, false) INITIALIZE_PASS_END(SimpleLoopUnswitchLegacyPass
 

Variables

static cl::opt< boolEnableNonTrivialUnswitch ("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."))
 
simple loop unswitch
 
simple loop Simple unswitch loops
 
simple loop Simple unswitch false
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "simple-loop-unswitch"

Definition at line 54 of file SimpleLoopUnswitch.cpp.

Function Documentation

◆ areLoopExitPHIsLoopInvariant()

static bool areLoopExitPHIsLoopInvariant ( Loop L,
BasicBlock ExitingBB,
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 90 of file SimpleLoopUnswitch.cpp.

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

Referenced by unswitchTrivialBranch(), and unswitchTrivialSwitch().

◆ buildClonedLoopBlocks()

static BasicBlock* buildClonedLoopBlocks ( Loop L,
BasicBlock LoopPH,
BasicBlock SplitBB,
ArrayRef< BasicBlock *>  ExitBlocks,
BasicBlock ParentBB,
BasicBlock UnswitchedSuccBB,
BasicBlock ContinueSuccBB,
const SmallPtrSetImpl< BasicBlock *> &  SkippedLoopAndExitBlocks,
ValueToValueMapTy VMap,
SmallVectorImpl< DominatorTree::UpdateType > &  DTUpdates,
AssumptionCache AC,
DominatorTree DT,
LoopInfo LI 
)
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. It skips loop and exit blocks that are not necessary based on the provided set. 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 597 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::SmallPtrSetImplBase::clear(), llvm::CloneBasicBlock(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::PHINode::Create(), llvm::BranchInst::Create(), llvm::LoopBase< BlockT, LoopT >::getNumBlocks(), llvm::Value::getType(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::make_range(), llvm::BasicBlock::moveBefore(), llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::AssumptionCache::registerAssumption(), llvm::RemapInstruction(), llvm::Value::replaceAllUsesWith(), llvm::SmallVectorImpl< T >::reserve(), llvm::RF_IgnoreMissingLocals, llvm::RF_NoModuleLevelChanges, llvm::ArrayRef< T >::size(), llvm::SplitBlock(), llvm::successors(), llvm::Value::takeName(), and llvm::zip_first().

Referenced by unswitchInvariantBranch().

◆ buildClonedLoops()

static Loop* 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 795 of file SimpleLoopUnswitch.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::LoopInfoBase< BlockT, LoopT >::addTopLevelLoop(), llvm::LoopInfoBase< BlockT, LoopT >::AllocateLoop(), assert(), llvm::LoopBase< BlockT, LoopT >::blocks(), cloneLoopNest(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::ValueMap< KeyT, ValueT, Config >::count(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::SmallVectorBase::empty(), llvm::SmallPtrSetImplBase::empty(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::SetVector< T, Vector, Set >::insert(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::makeArrayRef(), llvm::AArch64CC::PL, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::SmallVectorImpl< T >::reserve(), llvm::LoopBase< BlockT, LoopT >::reserveBlocks(), second, llvm::SmallPtrSetImplBase::size(), llvm::ArrayRef< T >::size(), and llvm::sort().

Referenced by unswitchInvariantBranch().

◆ cloneLoopNest()

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

◆ computeDomSubtreeCost()

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

◆ deleteDeadBlocksFromLoop()

static void deleteDeadBlocksFromLoop ( Loop L,
const SmallVectorImpl< BasicBlock *> &  DeadBlocks,
SmallVectorImpl< BasicBlock *> &  ExitBlocks,
DominatorTree DT,
LoopInfo LI 
)
static

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( SimpleLoopUnswitchLegacyPass  ,
"simple-loop-unswitch ,
"Simple unswitch loops ,
false  ,
false   
)

◆ rebuildLoopAfterUnswitch()

static bool rebuildLoopAfterUnswitch ( Loop L,
ArrayRef< BasicBlock *>  ExitBlocks,
LoopInfo LI,
SmallVectorImpl< Loop *> &  HoistedLoops 
)
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 1228 of file SimpleLoopUnswitch.cpp.

References llvm::LoopBase< BlockT, LoopT >::addChildLoop(), llvm::LoopInfoBase< BlockT, LoopT >::addTopLevelLoop(), assert(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::LoopInfoBase< BlockT, LoopT >::changeLoopFor(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::LoopInfoBase< BlockT, LoopT >::destroy(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::erase_if(), llvm::find(), llvm::LoopBase< BlockT, LoopT >::getBlocksSet(), llvm::LoopBase< BlockT, LoopT >::getBlocksVector(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopDepth(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::LoopBase< BlockT, LoopT >::getSubLoopsVector(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::make_range(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), recomputeLoopBlockSet(), llvm::LoopBase< BlockT, LoopT >::removeChildLoop(), llvm::LoopInfoBase< BlockT, LoopT >::removeLoop(), llvm::SmallVectorImpl< T >::reserve(), and llvm::ArrayRef< T >::size().

Referenced by unswitchInvariantBranch().

◆ recomputeLoopBlockSet()

static 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 1117 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::SmallVectorBase::empty(), llvm::SmallPtrSetImplBase::empty(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::predecessors(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

Referenced by rebuildLoopAfterUnswitch().

◆ replaceLoopUsesWithConstant()

static void replaceLoopUsesWithConstant ( Loop L,
Value LIC,
Constant Replacement 
)
static

◆ rewritePHINodesForExitAndUnswitchedBlocks()

static void rewritePHINodesForExitAndUnswitchedBlocks ( BasicBlock ExitBB,
BasicBlock UnswitchedBB,
BasicBlock OldExitingBB,
BasicBlock OldPH 
)
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 135 of file SimpleLoopUnswitch.cpp.

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

Referenced by unswitchTrivialBranch(), and unswitchTrivialSwitch().

◆ rewritePHINodesForUnswitchedExitBlock()

static 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 113 of file SimpleLoopUnswitch.cpp.

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

Referenced by unswitchTrivialBranch(), and unswitchTrivialSwitch().

◆ STATISTIC() [1/3]

STATISTIC ( NumBranches  ,
"Number of branches unswitched"   
)

◆ STATISTIC() [2/3]

STATISTIC ( NumSwitches  ,
"Number of switches unswitched"   
)

◆ STATISTIC() [3/3]

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

◆ unswitchAllTrivialConditions()

static bool unswitchAllTrivialConditions ( Loop L,
DominatorTree DT,
LoopInfo LI 
)
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).

Definition at line 490 of file SimpleLoopUnswitch.cpp.

References llvm::any_of(), assert(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BasicBlock::getTerminator(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Instruction::mayHaveSideEffects(), SI, unswitchTrivialBranch(), and unswitchTrivialSwitch().

Referenced by unswitchLoop().

◆ unswitchInvariantBranch()

static bool unswitchInvariantBranch ( Loop L,
BranchInst BI,
DominatorTree DT,
LoopInfo LI,
AssumptionCache AC,
function_ref< void(bool, ArrayRef< Loop *>)>  NonTrivialUnswitchCB 
)
static

Take an invariant branch that has been determined to be safe and worthwhile to unswitch despite being non-trivial to do so and perform the unswitch.

This directly updates the CFG to hoist the predicate out of the loop, and clone the necessary parts of the loop to maintain behavior.

It also updates both dominator tree and loopinfo based on the unswitching.

Once unswitching has been performed it runs the provided callback to report the new loops and no-longer valid loops to the caller.

Definition at line 1466 of file SimpleLoopUnswitch.cpp.

References llvm::all_of(), llvm::DominatorTreeBase< NodeT, IsPostDom >::applyUpdates(), assert(), buildClonedLoopBlocks(), buildClonedLoops(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::BranchInst::Create(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, deleteDeadBlocksFromLoop(), llvm::DominatorTree::dominates(), llvm::SmallVectorBase::empty(), llvm::CallingConv::Fast, llvm::formDedicatedExitBlocks(), llvm::formLCSSA(), llvm::BranchInst::getCondition(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::BranchInst::getSuccessor(), llvm::Loop::getUniqueExitBlocks(), llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::BranchInst::isConditional(), llvm::Loop::isLoopInvariant(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), rebuildLoopAfterUnswitch(), llvm::BranchInst::setSuccessor(), llvm::SmallVectorTemplateCommon< T >::size(), llvm::SplitEdge(), llvm::LoopInfoBase< BlockT, LoopT >::verify(), llvm::DominatorTreeBase< NodeT, IsPostDom >::verify(), and visitDomSubTree().

Referenced by unswitchLoop().

◆ unswitchLoop()

static bool unswitchLoop ( Loop L,
DominatorTree DT,
LoopInfo LI,
AssumptionCache AC,
TargetTransformInfo TTI,
bool  NonTrivial,
function_ref< void(bool, ArrayRef< Loop *>)>  NonTrivialUnswitchCB 
)
static

◆ unswitchTrivialBranch()

static bool unswitchTrivialBranch ( Loop L,
BranchInst BI,
DominatorTree DT,
LoopInfo LI 
)
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 simplify-cfg like pass.

Definition at line 184 of file SimpleLoopUnswitch.cpp.

References llvm::DominatorTreeBase< NodeT, IsPostDom >::applyUpdates(), areLoopExitPHIsLoopInvariant(), assert(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::BranchInst::Create(), llvm::dbgs(), llvm::DominatorTreeBase< NodeT, IsPostDom >::Delete, llvm::BasicBlock::end(), llvm::Instruction::eraseFromParent(), llvm::BranchInst::getCondition(), llvm::Value::getContext(), llvm::ConstantInt::getFalse(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BasicBlock::getInstList(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Instruction::getParent(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getTrue(), llvm::BasicBlock::getUniquePredecessor(), llvm::DominatorTreeBase< NodeT, IsPostDom >::Insert, llvm::BranchInst::isConditional(), llvm::Loop::isLoopInvariant(), LLVM_DEBUG, replaceLoopUsesWithConstant(), rewritePHINodesForExitAndUnswitchedBlocks(), rewritePHINodesForUnswitchedExitBlock(), llvm::BranchInst::setSuccessor(), llvm::iplist_impl< IntrusiveListT, TraitsT >::splice(), llvm::SplitBlock(), llvm::SplitEdge(), and std::swap().

Referenced by unswitchAllTrivialConditions().

◆ unswitchTrivialSwitch()

static bool unswitchTrivialSwitch ( Loop L,
SwitchInst SI,
DominatorTree DT,
LoopInfo LI 
)
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 simplify-cfg like pass.

Definition at line 293 of file SimpleLoopUnswitch.cpp.

References llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), llvm::all_of(), llvm::DominatorTreeBase< NodeT, IsPostDom >::applyUpdates(), areLoopExitPHIsLoopInvariant(), assert(), llvm::SwitchInst::case_begin(), llvm::SwitchInst::case_end(), llvm::SwitchInst::cases(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::BasicBlock::Create(), llvm::BranchInst::Create(), llvm::SwitchInst::Create(), llvm::dbgs(), llvm::DominatorTreeBase< NodeT, IsPostDom >::Delete, llvm::SmallVectorBase::empty(), llvm::Instruction::eraseFromParent(), llvm::CallingConv::Fast, llvm::BasicBlock::front(), llvm::SwitchInst::getCondition(), llvm::SwitchInst::getDefaultDest(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::SwitchInst::getNumCases(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::DominatorTreeBase< NodeT, IsPostDom >::Insert, llvm::Loop::isLoopInvariant(), LLVM_DEBUG, llvm::pred_empty(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), llvm::SwitchInst::removeCase(), llvm::SmallVectorImpl< T >::reserve(), llvm::reverse(), rewritePHINodesForExitAndUnswitchedBlocks(), rewritePHINodesForUnswitchedExitBlock(), llvm::SwitchInst::setDefaultDest(), SI, llvm::SmallVectorTemplateCommon< T, typename >::size(), llvm::SmallVectorTemplateCommon< T >::size(), llvm::SplitBlock(), llvm::SplitEdge(), and llvm::DominatorTreeBase< NodeT, IsPostDom >::verify().

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 1433 of file SimpleLoopUnswitch.cpp.

References assert(), llvm::SmallVectorBase::empty(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::SmallPtrSetImpl< PtrType >::insert(), N, llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

Referenced by unswitchInvariantBranch().

Variable Documentation

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

Referenced by unswitchLoop().

◆ false

simple loop Simple unswitch false

Definition at line 2027 of file SimpleLoopUnswitch.cpp.

◆ loops

simple loop Simple unswitch loops

Definition at line 2027 of file SimpleLoopUnswitch.cpp.

◆ unswitch

simple loop unswitch

Definition at line 2027 of file SimpleLoopUnswitch.cpp.

◆ UnswitchThreshold

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

Referenced by unswitchLoop().