LLVM
15.0.0git
|
#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/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>
Go to the source code of this file.
Macros | |
#define | DEBUG_TYPE "loop-peel" |
Functions | |
STATISTIC (NumPeeled, "Number of loops peeled") | |
static Optional< unsigned > | calculateIterationsToInvariance (PHINode *Phi, Loop *L, BasicBlock *BackEdge, SmallDenseMap< PHINode *, Optional< unsigned > > &IterationsToInvariance) |
static unsigned | peelToTurnInvariantLoadsDerefencebale (Loop &L, DominatorTree &DT) |
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 (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, ArrayRef< MDNode * > LoopLocalNoAliasDeclScopes) |
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 const char * | PeeledCountMetaData = "llvm.loop.peeled.count" |
#define DEBUG_TYPE "loop-peel" |
Definition at line 48 of file LoopPeel.cpp.
|
static |
Definition at line 120 of file LoopPeel.cpp.
References assert(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getParent(), I, llvm::Loop::isLoopInvariant(), and llvm::None.
Referenced by llvm::computePeelCount().
|
static |
Clones the body of the loop L, putting it between InsertTop
and InsertBot
.
IterNumber | The serial number of the iteration currently being peeled off. | |
ExitEdges | The exit edges of the original loop. | |
[out] | NewBlocks | A list of the blocks in the newly created clone |
[out] | VMap | The value map between the loop and the new clone. |
LoopBlocks | A helper for DFS-traversal of the loop. | |
LVMap | A value-map that maps instructions from the original loop to instructions in the last peeled-off iteration. |
Definition at line 575 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::MipsISD::Ext, F, llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::BasicBlock::getContext(), 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::BranchInst::getNumSuccessors(), llvm::BasicBlock::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), I, llvm::Instruction::setSuccessor(), and llvm::BranchInst::setSuccessor().
Referenced by llvm::peelLoop().
|
static |
Definition at line 228 of file LoopPeel.cpp.
References assert(), BB, llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::SCEVAddRecExpr::evaluateAtIteration(), llvm::ScalarEvolution::evaluatePredicate(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getConstant(), llvm::CmpInst::getInversePredicate(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::ScalarEvolution::getMonotonicPredicateType(), llvm::ScalarEvolution::getSCEV(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::CmpInst::getSwappedPredicate(), llvm::SCEV::getType(), llvm::SCEVNAryExpr::hasNoSelfWrap(), llvm::SCEVAddRecExpr::isAffine(), llvm::ICmpInst::isEquality(), llvm::ScalarEvolution::isKnownPredicate(), llvm::Loop::isLoopSimplifyForm(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::max(), and std::swap().
Referenced by llvm::computePeelCount().
|
static |
Update the weights of original Latch block after peeling off all iterations.
Header | The header block. |
LatchBR | The latch branch. |
ExitWeight | The weight of the edge from Latch to Exit. |
FallThroughWeight | The weight of the edge from Latch to Header. |
Definition at line 548 of file LoopPeel.cpp.
References llvm::MDBuilder::createBranchWeights(), llvm::Value::getContext(), llvm::BranchInst::getSuccessor(), and llvm::Instruction::setMetadata().
Referenced by llvm::peelLoop().
|
static |
Initialize the weights.
Header | The header block. | |
LatchBR | The latch branch. | |
[out] | ExitWeight | The weight of the edge from Latch to Exit. |
[out] | FallThroughWeight | The weight of the edge from Latch to Header. |
Definition at line 531 of file LoopPeel.cpp.
References llvm::Instruction::extractProfMetadata(), and llvm::BranchInst::getSuccessor().
Referenced by llvm::peelLoop().
|
static |
Definition at line 162 of file LoopPeel.cpp.
References llvm::any_of(), BB, llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::SmallPtrSetImpl< PtrType >::contains(), DL, llvm::DominatorTree::dominates(), llvm::SmallPtrSetImpl< PtrType >::end(), llvm::SmallPtrSetImpl< PtrType >::find(), llvm::Module::getDataLayout(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::LoopBase< BlockT, LoopT >::getExitingBlocks(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::BasicBlock::getModule(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::LoopBase< BlockT, LoopT >::getUniqueNonLatchExitBlocks(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isDereferenceablePointer(), and llvm::Loop::isLoopInvariant().
Referenced by llvm::computePeelCount().
|
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).
Header | The copy of the header block that belongs to next iteration. | |
LatchBR | The copy of the latch branch that belongs to this iteration. | |
[in,out] | FallThroughWeight | The weight of the edge from latch to header before peeling (in) and after peeled off one iteration (out). |
Definition at line 507 of file LoopPeel.cpp.
References llvm::MDBuilder::createBranchWeights(), llvm::Value::getContext(), llvm::BranchInst::getSuccessor(), and llvm::Instruction::setMetadata().
Referenced by llvm::peelLoop().
|
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 agressive. This should probably be removed.
Definition at line 335 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().
|
static |
Definition at line 74 of file LoopPeel.cpp.
Referenced by llvm::computePeelCount(), and llvm::peelLoop().
|
static |
Referenced by llvm::gatherPeelingPreferences().
|
static |
Referenced by llvm::gatherPeelingPreferences().
|
static |
Referenced by llvm::computePeelCount().
|
static |
Referenced by llvm::gatherPeelingPreferences().
|
static |
Referenced by llvm::computePeelCount().