LLVM  9.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, unsigned IterNumber, unsigned AvgIters, uint64_t &PeeledHeaderWeight)
 Update the branch weights of the latch of a peeled-off loop iteration. More...
 
static void initBranchWeights (BasicBlock *Header, BranchInst *LatchBR, unsigned AvgIters, uint64_t &ExitWeight, uint64_t &CurHeaderWeight)
 Initialize the weights. More...
 
static void fixupBranchWeights (BasicBlock *Header, BranchInst *LatchBR, uint64_t ExitWeight, uint64_t CurHeaderWeight)
 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(false), cl::Hidden, cl::desc("Allow peeling of loops with multiple deopt exits."))
 
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 461 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  CurHeaderWeight 
)
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 block.
CurHeaderWeightThe # of time the header is executed.

Definition at line 430 of file LoopUnrollPeel.cpp.

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

Referenced by llvm::peelLoop().

◆ initBranchWeights()

static void initBranchWeights ( BasicBlock Header,
BranchInst LatchBR,
unsigned  AvgIters,
uint64_t &  ExitWeight,
uint64_t &  CurHeaderWeight 
)
static

Initialize the weights.

Parameters
HeaderThe header block.
LatchBRThe latch branch.
AvgItersThe average number of iterations we expect the loop to have.
[out]ExitWeightThe # of times the edge from Latch to Exit is taken.
[out]CurHeaderWeightThe # of times the header is executed.

Definition at line 411 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,
unsigned  IterNumber,
unsigned  AvgIters,
uint64_t &  PeeledHeaderWeight 
)
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. Our goal is to make sure that: a) The total weight of all the copies of the loop body is preserved. b) The total weight of the loop exit is preserved. c) The body weight is reasonably distributed between the peeled iterations.

Parameters
HeaderThe copy of the header block that belongs to next iteration.
LatchBRThe copy of the latch branch that belongs to this iteration.
IterNumberThe serial number of the iteration that was just peeled off.
AvgItersThe average number of iterations we expect the loop to have.
[in,out]PeeledHeaderWeightThe total number of dynamic loop iterations that are unaccounted for. As an input, it represents the number of times we expect to enter the header of the iteration currently being peeled off. The output is the number of times we expect to enter the header of the next iteration.

Definition at line 382 of file LoopUnrollPeel.cpp.

References llvm::Value::getContext(), llvm::BranchInst::getSuccessor(), llvm::LLVMContext::MD_prof, 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 71 of file LoopUnrollPeel.cpp.

Referenced by calculateIterationsToInvariance().

◆ 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(false), cl::Hidden, cl::desc("Allow peeling of loops with multiple deopt exits."))
static

Referenced by llvm::canPeel().