LLVM  10.0.0svn
Macros | Functions | Variables
LoopUnrollPeel.cpp File Reference
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.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/Metadata.h"
#include "llvm/IR/PatternMatch.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/UnrollLoop.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
Include dependency graph for LoopUnrollPeel.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "loop-unroll"
 

Functions

 STATISTIC (NumPeeled, "Number of loops peeled")
 
static unsigned calculateIterationsToInvariance (PHINode *Phi, Loop *L, BasicBlock *BackEdge, SmallDenseMap< PHINode *, unsigned > &IterationsToInvariance)
 
static unsigned countToEliminateCompares (Loop &L, unsigned MaxPeelCount, ScalarEvolution &SE)
 
static void updateBranchWeights (BasicBlock *Header, BranchInst *LatchBR, uint64_t ExitWeight, uint64_t &FallThroughWeight)
 Update the branch weights of the latch of a peeled-off loop iteration. More...
 
static void initBranchWeights (BasicBlock *Header, BranchInst *LatchBR, uint64_t &ExitWeight, uint64_t &FallThroughWeight)
 Initialize the weights. More...
 
static void fixupBranchWeights (BasicBlock *Header, BranchInst *LatchBR, uint64_t ExitWeight, uint64_t FallThroughWeight)
 Update the weights of original Latch 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)
 Clones the body of the loop L, putting it between InsertTop and InsertBot. More...
 

Variables

static cl::opt< unsignedUnrollPeelMaxCount ("unroll-peel-max-count", cl::init(7), cl::Hidden, cl::desc("Max average trip count which will cause loop peeling."))
 
static cl::opt< unsignedUnrollForcePeelCount ("unroll-force-peel-count", cl::init(0), cl::Hidden, cl::desc("Force a peel count regardless of profiling information."))
 
static cl::opt< boolUnrollPeelMultiDeoptExit ("unroll-peel-multi-deopt-exit", cl::init(true), cl::Hidden, cl::desc("Allow peeling of loops with multiple deopt exits."))
 
static const charPeeledCountMetaData = "llvm.loop.peeled.count"
 
static const unsigned InfiniteIterationsToInvariance
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-unroll"

Definition at line 52 of file LoopUnrollPeel.cpp.

Function Documentation

◆ calculateIterationsToInvariance()

static unsigned calculateIterationsToInvariance ( PHINode Phi,
Loop L,
BasicBlock BackEdge,
SmallDenseMap< PHINode *, unsigned > &  IterationsToInvariance 
)
static

◆ 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 
)
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 468 of file LoopUnrollPeel.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), llvm::LoopBlocksDFS::beginRPO(), llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::CloneBasicBlock(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dyn_cast(), llvm::LoopBlocksDFS::endRPO(), F(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::BasicBlock::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::BasicBlock::getTerminator(), I, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Instruction::setSuccessor(), and llvm::BranchInst::setSuccessor().

Referenced by llvm::peelLoop().

◆ countToEliminateCompares()

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

◆ fixupBranchWeights()

static void fixupBranchWeights ( BasicBlock Header,
BranchInst LatchBR,
uint64_t  ExitWeight,
uint64_t  FallThroughWeight 
)
static

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

Parameters
HeaderThe header block.
LatchBRThe latch branch.
ExitWeightThe weight of the edge from Latch to Exit.
FallThroughWeightThe weight of the edge from Latch to Header.

Definition at line 441 of file LoopUnrollPeel.cpp.

References llvm::Value::getContext(), llvm::BranchInst::getSuccessor(), and llvm::Instruction::setMetadata().

Referenced by llvm::peelLoop().

◆ initBranchWeights()

static void initBranchWeights ( BasicBlock Header,
BranchInst LatchBR,
uint64_t &  ExitWeight,
uint64_t &  FallThroughWeight 
)
static

Initialize the weights.

Parameters
HeaderThe header block.
LatchBRThe latch branch.
[out]ExitWeightThe weight of the edge from Latch to Exit.
[out]FallThroughWeightThe weight of the edge from Latch to Header.

Definition at line 424 of file LoopUnrollPeel.cpp.

References llvm::Instruction::extractProfMetadata(), and llvm::BranchInst::getSuccessor().

Referenced by llvm::peelLoop().

◆ STATISTIC()

STATISTIC ( NumPeeled  ,
"Number of loops peeled"   
)

◆ updateBranchWeights()

static void updateBranchWeights ( BasicBlock Header,
BranchInst LatchBR,
uint64_t  ExitWeight,
uint64_t &  FallThroughWeight 
)
static

Update the branch weights of the latch of a peeled-off loop iteration.

This sets the branch weights for the latch of the recently peeled off loop iteration correctly. Let F is a weight of the edge from latch to header. Let E is a weight of the edge from latch to exit. F/(F+E) is a probability to go to loop and E/(F+E) is a probability to go to exit. Then, Estimated TripCount = F / E. For I-th (counting from 0) peeled off iteration we set the the weights for the peeled latch as (TC - I, 1). It gives us reasonable distribution, The probability to go to exit 1/(TC-I) increases. At the same time the estimated trip count of remaining 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).

Parameters
HeaderThe copy of the header block that belongs to next iteration.
LatchBRThe copy of the latch branch that belongs to this iteration.
[in,out]FallThroughWeightThe weight of the edge from latch to header before peeling (in) and after peeled off one iteration (out).

Definition at line 400 of file LoopUnrollPeel.cpp.

References llvm::Value::getContext(), llvm::BranchInst::getSuccessor(), and llvm::Instruction::setMetadata().

Referenced by llvm::peelLoop().

Variable Documentation

◆ InfiniteIterationsToInvariance

const unsigned InfiniteIterationsToInvariance
static
Initial value:
=
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)

Definition at line 73 of file LoopUnrollPeel.cpp.

Referenced by calculateIterationsToInvariance().

◆ PeeledCountMetaData

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

Definition at line 68 of file LoopUnrollPeel.cpp.

◆ 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().

◆ 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().

◆ UnrollPeelMultiDeoptExit

cl::opt<bool> UnrollPeelMultiDeoptExit("unroll-peel-multi-deopt-exit", cl::init(true), cl::Hidden, cl::desc("Allow peeling of loops with multiple deopt exits."))
static

Referenced by llvm::canPeel().