LLVM  16.0.0git
Classes | Macros | Functions | Variables
LoopPeel.cpp File Reference
#include "llvm/Transforms/Utils/LoopPeel.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/BasicBlock.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/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <optional>
Include dependency graph for LoopPeel.cpp:

Go to the source code of this file.

Classes

struct  WeightInfo
 

Macros

#define DEBUG_TYPE   "loop-peel"
 

Functions

 STATISTIC (NumPeeled, "Number of loops peeled")
 
static unsigned peelToTurnInvariantLoadsDerefencebale (Loop &L, DominatorTree &DT, AssumptionCache *AC)
 
static unsigned countToEliminateCompares (Loop &L, unsigned MaxPeelCount, ScalarEvolution &SE)
 
static bool violatesLegacyMultiExitLoopCheck (Loop *L)
 This "heuristic" exactly matches implicit behavior which used to exist inside getLoopEstimatedTripCount. More...
 
static void updateBranchWeights (Instruction *Term, WeightInfo &Info)
 Update the branch weights of an exiting block of a peeled-off loop iteration. More...
 
static void initBranchWeights (DenseMap< Instruction *, WeightInfo > &WeightInfos, Loop *L)
 Initialize the weights for all exiting blocks. More...
 
static void fixupBranchWeights (Instruction *Term, const WeightInfo &Info)
 Update the weights of original exiting block after peeling off all iterations. More...
 
static void cloneLoopBlocks (Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot, SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * >> &ExitEdges, SmallVectorImpl< BasicBlock * > &NewBlocks, LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT, LoopInfo *LI, ArrayRef< MDNode * > LoopLocalNoAliasDeclScopes, ScalarEvolution &SE)
 Clones the body of the loop L, putting it between InsertTop and InsertBot. More...
 

Variables

static cl::opt< unsigned > UnrollPeelCount ("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes"))
 
static cl::opt< bool > UnrollAllowPeeling ("unroll-allow-peeling", cl::init(true), cl::Hidden, cl::desc("Allows loops to be peeled when the dynamic " "trip count is known to be low."))
 
static cl::opt< bool > UnrollAllowLoopNestsPeeling ("unroll-allow-loop-nests-peeling", cl::init(false), cl::Hidden, cl::desc("Allows loop nests to be peeled."))
 
static cl::opt< unsigned > UnrollPeelMaxCount ("unroll-peel-max-count", cl::init(7), cl::Hidden, cl::desc("Max average trip count which will cause loop peeling."))
 
static cl::opt< unsigned > UnrollForcePeelCount ("unroll-force-peel-count", cl::init(0), cl::Hidden, cl::desc("Force a peel count regardless of profiling information."))
 
static cl::opt< bool > DisableAdvancedPeeling ("disable-advanced-peeling", cl::init(false), cl::Hidden, cl::desc("Disable advance peeling. Issues for convergent targets (D134803)."))
 
static const char * PeeledCountMetaData = "llvm.loop.peeled.count"
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-peel"

Definition at line 50 of file LoopPeel.cpp.

Function Documentation

◆ cloneLoopBlocks()

static void cloneLoopBlocks ( Loop L,
unsigned  IterNumber,
BasicBlock InsertTop,
BasicBlock InsertBot,
SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * >> &  ExitEdges,
SmallVectorImpl< BasicBlock * > &  NewBlocks,
LoopBlocksDFS LoopBlocks,
ValueToValueMapTy VMap,
ValueToValueMapTy LVMap,
DominatorTree DT,
LoopInfo LI,
ArrayRef< MDNode * >  LoopLocalNoAliasDeclScopes,
ScalarEvolution SE 
)
static

Clones the body of the loop L, putting it between InsertTop and InsertBot.

Parameters
IterNumberThe serial number of the iteration currently being peeled off.
ExitEdgesThe exit edges of the original loop.
[out]NewBlocksA list of the blocks in the newly created clone
[out]VMapThe value map between the loop and the new clone.
LoopBlocksA helper for DFS-traversal of the loop.
LVMapA value-map that maps instructions from the original loop to instructions in the last peeled-off iteration.

Definition at line 675 of file LoopPeel.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), BB, llvm::LoopBlocksDFS::beginRPO(), llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::cloneAndAdaptNoAliasScopes(), llvm::CloneBasicBlock(), llvm::cloneLoop(), llvm::numbers::e, llvm::LoopBlocksDFS::endRPO(), llvm::Instruction::eraseFromParent(), llvm::MipsISD::Ext, F, llvm::ScalarEvolution::forgetValue(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::BasicBlock::getTerminator(), I, PHI, and llvm::Instruction::setSuccessor().

Referenced by llvm::peelLoop().

◆ countToEliminateCompares()

static unsigned countToEliminateCompares ( Loop L,
unsigned  MaxPeelCount,
ScalarEvolution SE 
)
static

◆ fixupBranchWeights()

static void fixupBranchWeights ( Instruction Term,
const WeightInfo Info 
)
static

Update the weights of original exiting block after peeling off all iterations.

Definition at line 659 of file LoopPeel.cpp.

References llvm::MDBuilder::createBranchWeights(), Info, and llvm::M68kBeads::Term.

Referenced by llvm::peelLoop().

◆ initBranchWeights()

static void initBranchWeights ( DenseMap< Instruction *, WeightInfo > &  WeightInfos,
Loop L 
)
static

◆ peelToTurnInvariantLoadsDerefencebale()

static unsigned peelToTurnInvariantLoadsDerefencebale ( Loop L,
DominatorTree DT,
AssumptionCache AC 
)
static

◆ STATISTIC()

STATISTIC ( NumPeeled  ,
"Number of loops peeled"   
)

◆ updateBranchWeights()

static void updateBranchWeights ( Instruction Term,
WeightInfo Info 
)
static

Update the branch weights of an exiting block of a peeled-off loop iteration.

Let F is a weight of the edge to continue (fallthrough) into the loop. Let E is a weight of the edge to an exit. F/(F+E) is a probability to go to loop and E/(F+E) is a probability to go to exit. Then, Estimated ExitCount = F / E. For I-th (counting from 0) peeled off iteration we set the the weights for the peeled exit as (EC - I, 1). It gives us reasonable distribution, The probability to go to exit 1/(EC-I) increases. At the same time the estimated exit count in the remainder loop reduces by I. To avoid dealing with division rounding we can just multiple both part of weights to E and use weight as (F - I * E, E).

Definition at line 602 of file LoopPeel.cpp.

References llvm::MDBuilder::createBranchWeights(), llvm::enumerate(), Info, and llvm::M68kBeads::Term.

Referenced by llvm::peelLoop().

◆ violatesLegacyMultiExitLoopCheck()

static bool violatesLegacyMultiExitLoopCheck ( Loop L)
static

This "heuristic" exactly matches implicit behavior which used to exist inside getLoopEstimatedTripCount.

It was added here to keep an improvement inside that API from causing peeling to become more aggressive. This should probably be removed.

Definition at line 436 of file LoopPeel.cpp.

References llvm::any_of(), assert(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::BranchInst::getNumSuccessors(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminatingDeoptimizeCall(), llvm::BasicBlock::getTerminator(), llvm::LoopBase< BlockT, LoopT >::getUniqueNonLatchExitBlocks(), and llvm::LoopBase< BlockT, LoopT >::isLoopExiting().

Referenced by llvm::computePeelCount().

Variable Documentation

◆ DisableAdvancedPeeling

cl::opt<bool> DisableAdvancedPeeling("disable-advanced-peeling", cl::init(false), cl::Hidden, cl::desc( "Disable advance peeling. Issues for convergent targets (D134803)."))
static

Referenced by llvm::canPeel().

◆ PeeledCountMetaData

const char* PeeledCountMetaData = "llvm.loop.peeled.count"
static

Definition at line 81 of file LoopPeel.cpp.

Referenced by llvm::computePeelCount(), and llvm::peelLoop().

◆ UnrollAllowLoopNestsPeeling

cl::opt<bool> UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling", cl::init(false), cl::Hidden, cl::desc("Allows loop nests to be peeled."))
static

◆ UnrollAllowPeeling

cl::opt<bool> UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden, cl::desc("Allows loops to be peeled when the dynamic " "trip count is known to be low."))
static

◆ UnrollForcePeelCount

cl::opt<unsigned> UnrollForcePeelCount("unroll-force-peel-count", cl::init(0), cl::Hidden, cl::desc("Force a peel count regardless of profiling information."))
static

Referenced by llvm::computePeelCount().

◆ UnrollPeelCount

cl::opt<unsigned> UnrollPeelCount("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes"))
static

◆ UnrollPeelMaxCount

cl::opt<unsigned> UnrollPeelMaxCount("unroll-peel-max-count", cl::init(7), cl::Hidden, cl::desc("Max average trip count which will cause loop peeling."))
static

Referenced by llvm::computePeelCount().