LoopRotationUtils.cpp File Reference

#include "llvm/Transforms/Utils/LoopRotationUtils.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/MDBuilder.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/SSAUpdater.h"
#include "llvm/Transforms/Utils/ValueMapper.h"

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "loop-rotate"

Functions
	STATISTIC (NumNotRotatedDueToHeaderSize, "Number of loops not rotated due to the header size")
	STATISTIC (NumInstrsHoisted, "Number of instructions hoisted into loop preheader")
	STATISTIC (NumInstrsDuplicated, "Number of instructions cloned into loop preheader")
	STATISTIC (NumRotated, "Number of loops rotated")
static void	InsertNewValueIntoMap (ValueToValueMapTy &VM, Value *K, Value *V)
	Insert (K, V) pair into the ValueToValueMap, and verify the key did not previously exist in the map, and the value was inserted.
static void	RewriteUsesOfClonedInstructions (BasicBlock *OrigHeader, BasicBlock *OrigPreheader, ValueToValueMapTy &ValueMap, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *InsertedPHIs)
	RewriteUsesOfClonedInstructions - We just cloned the instructions from the old header into the preheader.
static bool	profitableToRotateLoopExitingLatch (Loop *L)
static bool	canRotateDeoptimizingLatchExit (Loop *L)
static void	updateBranchWeights (BranchInst &PreHeaderBI, BranchInst &LoopBI, bool HasConditionalPreHeader, bool SuccsSwapped)
static bool	shouldSpeculateInstrs (BasicBlock::iterator Begin, BasicBlock::iterator End, Loop *L)
	Determine whether the instructions in this range may be safely and cheaply speculated.

Variables
static cl::opt< bool >	MultiRotate ("loop-rotate-multi", cl::init(false), cl::Hidden, cl::desc("Allow loop rotation multiple times in order to reach " "a better latch exit"))
static constexpr uint32_t	ZeroTripCountWeights [] = {1, 127}

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-rotate"

Definition at line 40 of file LoopRotationUtils.cpp.

Function Documentation

canRotateDeoptimizingLatchExit()

bool canRotateDeoptimizingLatchExit ( Loop * L )

static

Definition at line 215 of file LoopRotationUtils.cpp.

References llvm::any_of(), assert(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::BasicBlock::getPostdominatingDeoptimizeCall(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), and llvm::BranchInst::isConditional().

InsertNewValueIntoMap()

void InsertNewValueIntoMap ( ValueToValueMapTy & VM, Value * K, Value * V )

static

Insert (K, V) pair into the ValueToValueMap, and verify the key did not previously exist in the map, and the value was inserted.

Definition at line 92 of file LoopRotationUtils.cpp.

References assert(), and llvm::ValueMap< KeyT, ValueT, Config >::insert().

profitableToRotateLoopExitingLatch()

bool profitableToRotateLoopExitingLatch ( Loop * L )

static

Definition at line 190 of file LoopRotationUtils.cpp.

References llvm::any_of(), assert(), llvm::dyn_cast(), llvm::BranchInst::getSuccessor(), and llvm::BranchInst::isConditional().

RewriteUsesOfClonedInstructions()

void RewriteUsesOfClonedInstructions ( BasicBlock * OrigHeader, BasicBlock * OrigPreheader, ValueToValueMapTy & ValueMap, ScalarEvolution * SE, SmallVectorImpl< PHINode * > * InsertedPHIs )

static

RewriteUsesOfClonedInstructions - We just cloned the instructions from the old header into the preheader.

If there were uses of the values produced by these instruction that were outside of the loop, we have to insert PHI nodes to merge the two values. Do this now.

Definition at line 101 of file LoopRotationUtils.cpp.

References llvm::BasicBlock::begin(), llvm::cast(), llvm::dyn_cast(), E(), llvm::BasicBlock::end(), llvm::findDbgValues(), llvm::ScalarEvolution::forgetValue(), llvm::PoisonValue::get(), llvm::BasicBlock::getMarker(), llvm::Value::getName(), llvm::DbgMarker::getParent(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::Value::getType(), I, llvm::isa(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::make_early_inc_range(), SSA, llvm::Value::use_empty(), and llvm::Value::uses().

shouldSpeculateInstrs()

bool shouldSpeculateInstrs ( BasicBlock::iterator Begin, BasicBlock::iterator End, Loop * L )

static

Determine whether the instructions in this range may be safely and cheaply speculated.

This is not an important enough situation to develop complex heuristics. We handle a single arithmetic instruction along with any type conversions.

Definition at line 898 of file LoopRotationUtils.cpp.

References llvm::cast(), I, llvm::isa(), llvm::isSafeToSpeculativelyExecute(), and llvm::Value::users().

STATISTIC() [1/4]

STATISTIC	(	NumInstrsDuplicated	,
		"Number of instructions cloned into loop preheader"	)

STATISTIC() [2/4]

STATISTIC	(	NumInstrsHoisted	,
		"Number of instructions hoisted into loop preheader"	)

STATISTIC() [3/4]

STATISTIC	(	NumNotRotatedDueToHeaderSize	,
		"Number of loops not rotated due to the header size"	)

STATISTIC() [4/4]

STATISTIC	(	NumRotated	,
		"Number of loops rotated"	)

updateBranchWeights()

void updateBranchWeights ( BranchInst & PreHeaderBI, BranchInst & LoopBI, bool HasConditionalPreHeader, bool SuccsSwapped )

static

Definition at line 253 of file LoopRotationUtils.cpp.

References assert(), llvm::extractFromBranchWeightMD32(), llvm::getBranchWeightMDNode(), llvm::setBranchWeights(), llvm::SmallVectorTemplateCommon< T, typename >::size(), std::swap(), and ZeroTripCountWeights.

Variable Documentation

MultiRotate

cl::opt< bool > MultiRotate("loop-rotate-multi", cl::init(false), cl::Hidden, cl::desc("Allow loop rotation multiple times in order to reach " "a better latch exit")) ( "loop-rotate-multi" , cl::init(false) , cl::Hidden , cl::desc("Allow loop rotation multiple times in order to reach " "a better latch exit")  )

static

ZeroTripCountWeights

uint32_t ZeroTripCountWeights[] = {1, 127}

staticconstexpr

Definition at line 56 of file LoopRotationUtils.cpp.

Referenced by updateBranchWeights().