LLVM  6.0.0svn
Macros | Functions | Variables
LoopUnrollPeel.cpp File Reference
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.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 <algorithm>
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 bool canPeel (Loop *L)
 
static unsigned calculateIterationsToInvariance (PHINode *Phi, Loop *L, BasicBlock *BackEdge, SmallDenseMap< PHINode *, unsigned > &IterationsToInvariance)
 
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 cloneLoopBlocks (Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot, BasicBlock *Exit, 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 const unsigned InfiniteIterationsToInvariance = UINT_MAX
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-unroll"

Definition at line 38 of file LoopUnrollPeel.cpp.

Function Documentation

◆ calculateIterationsToInvariance()

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

◆ canPeel()

static bool canPeel ( Loop L)
static

◆ cloneLoopBlocks()

static void cloneLoopBlocks ( Loop L,
unsigned  IterNumber,
BasicBlock InsertTop,
BasicBlock InsertBot,
BasicBlock Exit,
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.
ExitThe exit block of the original loop.
[out]NewBlocksA list of the 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 269 of file LoopUnrollPeel.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::PHINode::addIncoming(), llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), llvm::BasicBlock::begin(), 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, isPodLike >::push_back(), llvm::TerminatorInst::setSuccessor(), and llvm::BranchInst::setSuccessor().

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 236 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 = UINT_MAX
static

Definition at line 52 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().