LoopUnrollRuntime.cpp File Reference

#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/Analysis/ValueTracking.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/ProfDataUtils.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, ScalarEvolution &SE)
	Connect the unrolling prolog code to the original loop.
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, ScalarEvolution &SE, unsigned Count)
	Connect the unrolling epilog code to the original loop.
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, unsigned Count)
	Create a clone of the blocks in a loop and connect them together.
static bool	canProfitablyUnrollMultiExitLoop (Loop *L, SmallVectorImpl< BasicBlock * > &OtherExits, BasicBlock *LatchExit, bool UseEpilogRemainder)
	Returns true if we can profitably unroll the multi-exit loop L.
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.

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"))
static const uint32_t	UnrolledLoopHeaderWeights [] = {1, 127}
static const uint32_t	EpilogHeaderWeights [] = {1, 127}

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-unroll"

Definition at line 47 of file LoopUnrollRuntime.cpp.

Function Documentation

canProfitablyUnrollMultiExitLoop()

static bool canProfitablyUnrollMultiExitLoop ( Loop *  L, SmallVectorImpl< BasicBlock * > &  OtherExits, BasicBlock *  LatchExit, bool  UseEpilogRemainder  )

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 465 of file LoopUnrollRuntime.cpp.

References llvm::SmallVectorBase< Size_T >::size(), UnrollRuntimeMultiExit, and UnrollRuntimeOtherExitPredictable.

Referenced by llvm::UnrollRuntimeLoopRemainder().

CloneLoopBlocks()

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, unsigned  Count  )

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 339 of file LoopUnrollRuntime.cpp.

References llvm::addClonedBlockToLoopInfo(), llvm::PHINode::addIncoming(), llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), assert(), llvm::LoopBlocksDFS::beginRPO(), llvm::CloneBasicBlock(), llvm::PHINode::Create(), llvm::IRBuilderBase::CreateAdd(), llvm::MDBuilder::createBranchWeights(), llvm::IRBuilderBase::CreateCondBr(), llvm::IRBuilderBase::CreateICmpNE(), llvm::LoopBlocksDFS::endRPO(), llvm::ValueMap< KeyT, ValueT, Config >::erase(), llvm::Instruction::eraseFromParent(), F, llvm::PHINode::getBasicBlockIndex(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::IRBuilderBase::getContext(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::PHINode::getIncomingValue(), llvm::Loop::getLoopID(), llvm::Value::getName(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::hasBranchWeightMD(), I, llvm::Instruction::insertBefore(), 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().

ConnectEpilog()

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, ScalarEvolution &  SE, unsigned  Count  )

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 211 of file LoopUnrollRuntime.cpp.

References llvm::PHINode::addIncoming(), assert(), B, llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::PHINode::Create(), llvm::MDBuilder::createBranchWeights(), llvm::Instruction::eraseFromParent(), llvm::DominatorTree::findNearestCommonDominator(), llvm::ScalarEvolution::forgetValue(), llvm::PoisonValue::get(), llvm::PHINode::getBasicBlockIndex(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getTerminator(), llvm::hasBranchWeightMD(), I, llvm::Instruction::insertBefore(), 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().

ConnectProlog()

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, ScalarEvolution &  SE  )

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 83 of file LoopUnrollRuntime.cpp.

References llvm::PHINode::addIncoming(), assert(), B, llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::PHINode::Create(), llvm::MDBuilder::createBranchWeights(), llvm::Instruction::eraseFromParent(), llvm::DominatorTree::findNearestCommonDominator(), llvm::ScalarEvolution::forgetValue(), llvm::PoisonValue::get(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::hasBranchWeightMD(), I, llvm::Instruction::insertBefore(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SplitBlockPredecessors(), llvm::successors(), and UnrolledLoopHeaderWeights.

Referenced by llvm::UnrollRuntimeLoopRemainder().

CreateTripRemainder()

static Value * CreateTripRemainder ( IRBuilder<> &  B, Value *  BECount, Value *  TripCount, unsigned  Count  )

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 517 of file LoopUnrollRuntime.cpp.

References B, llvm::Value::getType(), and llvm::isPowerOf2_32().

Referenced by llvm::UnrollRuntimeLoopRemainder().

STATISTIC()

STATISTIC	(	NumRuntimeUnrolled	,
		"Number of loops unrolled with run-time trip counts"
	)

Variable Documentation

EpilogHeaderWeights

const uint32_t EpilogHeaderWeights[] = {1, 127}

static

Definition at line 68 of file LoopUnrollRuntime.cpp.

Referenced by llvm::UnrollRuntimeLoopRemainder().

UnrolledLoopHeaderWeights

const uint32_t UnrolledLoopHeaderWeights[] = {1, 127}

static

Definition at line 63 of file LoopUnrollRuntime.cpp.

Referenced by ConnectProlog().

UnrollRuntimeMultiExit

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")) ( "unroll-runtime-multi-exit"  , cl::init(false)  , cl::Hidden  , cl::desc("Allow runtime unrolling for loops with multiple exits, when " "epilog is generated")    )

static

Referenced by canProfitablyUnrollMultiExitLoop().

UnrollRuntimeOtherExitPredictable

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")) ( "unroll-runtime-other-exit-predictable"  , cl::init(false)  , cl::Hidden  , cl::desc("Assume the non latch exit block to be predictable")    )

static

Referenced by canProfitablyUnrollMultiExitLoop().