LLVM
15.0.0git
|
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Module.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/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include <algorithm>
Go to the source code of this file.
Macros | |
#define | DEBUG_TYPE "loop-unroll" |
Functions | |
STATISTIC (NumRuntimeUnrolled, "Number of loops unrolled with run-time trip counts") | |
static void | ConnectProlog (Loop *L, Value *BECount, unsigned Count, BasicBlock *PrologExit, BasicBlock *OriginalLoopLatchExit, BasicBlock *PreHeader, BasicBlock *NewPreHeader, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA) |
Connect the unrolling prolog code to the original loop. More... | |
static void | ConnectEpilog (Loop *L, Value *ModVal, BasicBlock *NewExit, BasicBlock *Exit, BasicBlock *PreHeader, BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA) |
Connect the unrolling epilog code to the original loop. More... | |
static Loop * | CloneLoopBlocks (Loop *L, Value *NewIter, const bool UseEpilogRemainder, const bool UnrollRemainder, BasicBlock *InsertTop, BasicBlock *InsertBot, BasicBlock *Preheader, std::vector< BasicBlock * > &NewBlocks, LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI) |
Create a clone of the blocks in a loop and connect them together. More... | |
static bool | canProfitablyUnrollMultiExitLoop (Loop *L, SmallVectorImpl< BasicBlock * > &OtherExits, BasicBlock *LatchExit, bool UseEpilogRemainder) |
Returns true if we can profitably unroll the multi-exit loop L. More... | |
static void | updateLatchBranchWeightsForRemainderLoop (Loop *OrigLoop, Loop *RemainderLoop, uint64_t UnrollFactor) |
static Value * | CreateTripRemainder (IRBuilder<> &B, Value *BECount, Value *TripCount, unsigned Count) |
Calculate ModVal = (BECount + 1) % Count on the abstract integer domain accounting for the possibility of unsigned overflow in the 2s complement domain. More... | |
Variables | |
static cl::opt< bool > | UnrollRuntimeMultiExit ("unroll-runtime-multi-exit", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolling for loops with multiple exits, when " "epilog is generated")) |
static cl::opt< bool > | UnrollRuntimeOtherExitPredictable ("unroll-runtime-other-exit-predictable", cl::init(false), cl::Hidden, cl::desc("Assume the non latch exit block to be predictable")) |
#define DEBUG_TYPE "loop-unroll" |
Definition at line 45 of file LoopUnrollRuntime.cpp.
|
static |
Returns true if we can profitably unroll the multi-exit loop L.
Currently, we return true only if UnrollRuntimeMultiExit is set to true.
Definition at line 414 of file LoopUnrollRuntime.cpp.
References llvm::LoopBase< BlockT, LoopT >::getExitingBlocks(), llvm::cl::Option::getNumOccurrences(), UnrollRuntimeMultiExit, and UnrollRuntimeOtherExitPredictable.
Referenced by llvm::UnrollRuntimeLoopRemainder().
|
static |
Create a clone of the blocks in a loop and connect them together.
A new loop will be created including all cloned blocks, and the iterator of the new loop switched to count NewIter down to 0. The cloned blocks should be inserted between InsertTop and InsertBot. InsertTop should be new preheader, InsertBot new loop exit. Returns the new cloned loop that is created.
Definition at line 309 of file LoopUnrollRuntime.cpp.
References llvm::addClonedBlockToLoopInfo(), llvm::PHINode::addIncoming(), llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), assert(), BB, llvm::BasicBlock::begin(), llvm::LoopBlocksDFS::beginRPO(), Builder, llvm::CloneBasicBlock(), llvm::PHINode::Create(), llvm::LoopBlocksDFS::endRPO(), llvm::ValueMap< KeyT, ValueT, Config >::erase(), llvm::Instruction::eraseFromParent(), F, llvm::ConstantInt::get(), llvm::PHINode::getBasicBlockIndex(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::BasicBlock::getFirstNonPHI(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::PHINode::getIncomingValue(), llvm::Loop::getLoopID(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Value::getName(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::BasicBlock::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::Optional< T >::getValue(), llvm::Optional< T >::hasValue(), I, llvm::LLVMLoopUnrollFollowupAll, llvm::LLVMLoopUnrollFollowupRemainder, llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::makeFollowupLoopID(), llvm::PHINode::setIncomingBlock(), llvm::PHINode::setIncomingValue(), llvm::Loop::setLoopAlreadyUnrolled(), llvm::Loop::setLoopID(), and llvm::Instruction::setSuccessor().
Referenced by llvm::UnrollRuntimeLoopRemainder().
|
static |
Connect the unrolling epilog code to the original loop.
The unrolling epilog code contains code to execute the 'extra' iterations if the run-time trip count modulo the unroll count is non-zero.
This function performs the following:
Definition at line 189 of file LoopUnrollRuntime.cpp.
References llvm::PHINode::addIncoming(), assert(), B, llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::PHINode::Create(), llvm::Instruction::eraseFromParent(), llvm::DominatorTreeBase< NodeT, IsPostDom >::findNearestCommonDominator(), llvm::UndefValue::get(), llvm::PHINode::getBasicBlockIndex(), llvm::BasicBlock::getFirstNonPHI(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), I, llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::BasicBlock::phis(), llvm::predecessors(), llvm::PHINode::setIncomingBlock(), llvm::PHINode::setIncomingValueForBlock(), llvm::SplitBlockPredecessors(), and llvm::successors().
Referenced by llvm::UnrollRuntimeLoopRemainder().
|
static |
Connect the unrolling prolog code to the original loop.
The unrolling prolog code contains code to execute the 'extra' iterations if the run-time trip count modulo the unroll count is non-zero.
This function performs the following:
Definition at line 70 of file LoopUnrollRuntime.cpp.
References llvm::PHINode::addIncoming(), assert(), B, llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::PHINode::Create(), llvm::Instruction::eraseFromParent(), llvm::DominatorTreeBase< NodeT, IsPostDom >::findNearestCommonDominator(), llvm::ConstantInt::get(), llvm::UndefValue::get(), llvm::BasicBlock::getFirstNonPHI(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::predecessors(), llvm::SplitBlockPredecessors(), and llvm::successors().
Referenced by llvm::UnrollRuntimeLoopRemainder().
|
static |
Calculate ModVal = (BECount + 1) % Count on the abstract integer domain accounting for the possibility of unsigned overflow in the 2s complement domain.
Preconditions: 1) TripCount = BECount + 1 (allowing overflow) 2) Log2(Count) <= BitWidth(BECount)
Definition at line 492 of file LoopUnrollRuntime.cpp.
References B, llvm::ConstantInt::get(), llvm::Value::getType(), and llvm::isPowerOf2_32().
Referenced by llvm::UnrollRuntimeLoopRemainder().
|
static |
Definition at line 463 of file LoopUnrollRuntime.cpp.
References assert(), llvm::MDBuilder::createBranchWeights(), llvm::Instruction::extractProfMetadata(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::BranchInst::getSuccessor(), and llvm::BasicBlock::getTerminator().
Referenced by llvm::UnrollRuntimeLoopRemainder().
|
static |
Referenced by canProfitablyUnrollMultiExitLoop().