#include "llvm/ADT/SmallPtrSet.h"#include "llvm/ADT/Statistic.h"#include "llvm/Analysis/AliasAnalysis.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/Metadata.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.h"#include "llvm/Transforms/Utils/BasicBlockUtils.h"#include "llvm/Transforms/Utils/Cloning.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 CreateRemainderLoop, 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 | canSafelyUnrollMultiExitLoop (Loop *L, BasicBlock *LatchExit, bool PreserveLCSSA, bool UseEpilogRemainder) |
| Returns true if we can safely unroll a multi-exit/exiting loop. More... | |
| static bool | canProfitablyUnrollMultiExitLoop (Loop *L, SmallVectorImpl< BasicBlock *> &OtherExits, BasicBlock *LatchExit, bool PreserveLCSSA, 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) |
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")) |
Macro Definition Documentation
◆ DEBUG_TYPE
| #define DEBUG_TYPE "loop-unroll" |
Definition at line 46 of file LoopUnrollRuntime.cpp.
Function Documentation
◆ canProfitablyUnrollMultiExitLoop()
|
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 463 of file LoopUnrollRuntime.cpp.
References assert(), canSafelyUnrollMultiExitLoop(), llvm::LoopBase< BlockT, LoopT >::getExitingBlocks(), llvm::SmallVectorBase< SmallVectorSizeType< T > >::size(), and UnrollRuntimeMultiExit.
Referenced by llvm::UnrollRuntimeLoopRemainder().
◆ canSafelyUnrollMultiExitLoop()
|
static |
Returns true if we can safely unroll a multi-exit/exiting loop.
OtherExits is populated with all the loop exit blocks other than the LatchExit block.
Definition at line 429 of file LoopUnrollRuntime.cpp.
References llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::BasicBlock::getSinglePredecessor(), and LLVM_DEBUG.
Referenced by canProfitablyUnrollMultiExitLoop(), and llvm::UnrollRuntimeLoopRemainder().
◆ CloneLoopBlocks()
|
static |
Create a clone of the blocks in a loop and connect them together.
If CreateRemainderLoop is false, loop structure will not be cloned, otherwise a new loop will be created including all cloned blocks, and the iterator of it switches to count NewIter down to 0. The cloned blocks should be inserted between InsertTop and InsertBot. If loop structure is cloned InsertTop should be new preheader, InsertBot new loop exit. Return the new cloned loop that is created when CreateRemainderLoop is true.
Definition at line 301 of file LoopUnrollRuntime.cpp.
References llvm::addClonedBlockToLoopInfo(), llvm::PHINode::addIncoming(), llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), assert(), llvm::BasicBlock::begin(), llvm::LoopBlocksDFS::beginRPO(), Builder, llvm::CloneBasicBlock(), llvm::PHINode::Create(), llvm::LoopBlocksDFS::endRPO(), llvm::ValueMap< KeyT, ValueT, Config >::erase(), 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::PHINode::getIncomingValueForBlock(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), 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::removeIncomingValue(), llvm::PHINode::setIncomingBlock(), llvm::PHINode::setIncomingValue(), llvm::Loop::setLoopAlreadyUnrolled(), llvm::Loop::setLoopID(), and llvm::Instruction::setSuccessor().
Referenced by llvm::UnrollRuntimeLoopRemainder().
◆ ConnectEpilog()
|
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:
- Update PHI nodes at the unrolling loop exit and epilog loop exit
- Create PHI nodes at the unrolling loop exit to combine values that exit the unrolling loop code and jump around it.
- Update PHI operands in the epilog loop by the new PHI nodes
- Branch around the epilog loop if extra iters (ModVal) is zero.
Definition at line 184 of file LoopUnrollRuntime.cpp.
References llvm::PHINode::addIncoming(), assert(), B, llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::PHINode::Create(), llvm::IRBuilderBase::CreateCondBr(), llvm::IRBuilderBase::CreateIsNotNull(), llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), llvm::UndefValue::get(), llvm::BasicBlock::getFirstNonPHI(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::BasicBlock::getTerminator(), I, llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::BasicBlock::phis(), llvm::predecessors(), llvm::PHINode::setIncomingValueForBlock(), llvm::SplitBlockPredecessors(), and llvm::successors().
Referenced by llvm::UnrollRuntimeLoopRemainder().
◆ ConnectProlog()
|
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:
- Create PHI nodes at prolog end block to combine values that exit the prolog code and jump around the prolog.
- Add a PHI operand to a PHI node at the loop exit block for values that exit the prolog and go around the loop.
- Branch around the original loop if the trip count is less than the unroll factor.
Definition at line 68 of file LoopUnrollRuntime.cpp.
References llvm::PHINode::addIncoming(), assert(), B, llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::PHINode::Create(), llvm::IRBuilderBase::CreateCondBr(), llvm::IRBuilderBase::CreateICmpULT(), llvm::Instruction::eraseFromParent(), 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::SmallVectorTemplateBase< T >::push_back(), llvm::SplitBlockPredecessors(), and llvm::successors().
Referenced by llvm::UnrollRuntimeLoopRemainder().
◆ STATISTIC()
| STATISTIC | ( | NumRuntimeUnrolled | , |
| "Number of loops unrolled with run-time trip counts" | |||
| ) |
◆ updateLatchBranchWeightsForRemainderLoop()
|
static |
Definition at line 511 of file LoopUnrollRuntime.cpp.
References assert(), llvm::Instruction::extractProfMetadata(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::BranchInst::getSuccessor(), and llvm::BasicBlock::getTerminator().
Referenced by llvm::UnrollRuntimeLoopRemainder().
