LoopRotationUtils.cpp File Reference

#include "llvm/Transforms/Utils/LoopRotationUtils.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DomTreeUpdater.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IntrinsicInst.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/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include "llvm/Transforms/Utils/ValueMapper.h"

Include dependency graph for LoopRotationUtils.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "loop-rotate"

Functions
	STATISTIC (NumRotated, "Number of loops rotated")
static void	RewriteUsesOfClonedInstructions (BasicBlock *OrigHeader, BasicBlock *OrigPreheader, ValueToValueMapTy &ValueMap, SmallVectorImpl< PHINode *> *InsertedPHIs)
	RewriteUsesOfClonedInstructions - We just cloned the instructions from the old header into the preheader. More...
static bool	shouldRotateLoopExitingLatch (Loop *L)
static bool	shouldSpeculateInstrs (BasicBlock::iterator Begin, BasicBlock::iterator End, Loop *L)
	Determine whether the instructions in this range may be safely and cheaply speculated. More...

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-rotate"

Definition at line 46 of file LoopRotationUtils.cpp.

Function Documentation

RewriteUsesOfClonedInstructions()

static void RewriteUsesOfClonedInstructions ( BasicBlock *  OrigHeader, BasicBlock *  OrigPreheader, ValueToValueMapTy &  ValueMap, 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 84 of file LoopRotationUtils.cpp.

References llvm::SSAUpdater::AddAvailableValue(), llvm::BasicBlock::begin(), llvm::dyn_cast(), E, llvm::BasicBlock::end(), llvm::findDbgValues(), llvm::MetadataAsValue::get(), llvm::ValueAsMetadata::get(), llvm::UndefValue::get(), llvm::PHINode::getBasicBlockIndex(), llvm::Value::getContext(), llvm::Value::getName(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::Value::getType(), llvm::Use::getUser(), llvm::SSAUpdater::GetValueInMiddleOfBlock(), llvm::SSAUpdater::HasValueForBlock(), I, llvm::SSAUpdater::Initialize(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::PHINode::removeIncomingValue(), llvm::SSAUpdater::RewriteUse(), llvm::User::setOperand(), SSA, llvm::Value::use_begin(), llvm::Value::use_empty(), and llvm::Value::use_end().

Referenced by shouldRotateLoopExitingLatch().

shouldRotateLoopExitingLatch()

static bool shouldRotateLoopExitingLatch ( Loop *  L )

static

Definition at line 177 of file LoopRotationUtils.cpp.

References llvm::PHINode::addIncoming(), llvm::CodeMetrics::analyzeBasicBlock(), llvm::any_of(), assert(), llvm::Intrinsic::assume, llvm::BasicBlock::begin(), C, llvm::Instruction::clone(), llvm::CodeMetrics::collectEphemeralValues(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::CodeMetrics::convergent, llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, InlineBuckets, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::count(), llvm::BranchInst::Create(), D, llvm::dbgs(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::Value::deleteValue(), llvm::Loop::dump(), llvm::dyn_cast(), E, llvm::DomTreeUpdater::Eager, llvm::SmallVectorBase::empty(), llvm::BasicBlock::end(), llvm::Instruction::eraseFromParent(), llvm::FoldSingleEntryPHINodes(), llvm::LoopBase< BlockT, LoopT >::getBlocks(), llvm::BranchInst::getCondition(), llvm::Instruction::getDebugLoc(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Value::getName(), getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::Instruction::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::LoopBase< BlockT, LoopT >::hasDedicatedExits(), llvm::Loop::hasLoopInvariantOperands(), I, llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, InlineBuckets, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::insert(), llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::Instruction::insertBefore(), llvm::insertDebugValuesForPHIs(), llvm::BranchInst::isConditional(), llvm::LoopBase< BlockT, LoopT >::isLoopExiting(), llvm::Instruction::isTerminator(), llvm::BranchInst::isUnconditional(), isZero(), LLVM_DEBUG, llvm::Instruction::mayHaveSideEffects(), llvm::Instruction::mayReadFromMemory(), llvm::Instruction::mayWriteToMemory(), llvm::MergeBlockIntoPredecessor(), Metrics, llvm::Instruction::moveBefore(), llvm::BasicBlock::moveBefore(), llvm::LoopBase< BlockT, LoopT >::moveToHeader(), llvm::CodeMetrics::notDuplicatable, llvm::CodeMetrics::NumInsts, llvm::BasicBlock::phis(), llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::BasicBlock::rbegin(), llvm::RemapInstruction(), llvm::BasicBlock::removePredecessor(), llvm::BasicBlock::rend(), RewriteUsesOfClonedInstructions(), llvm::RF_IgnoreMissingLocals, llvm::RF_NoModuleLevelChanges, llvm::Instruction::setDebugLoc(), llvm::Value::setName(), llvm::SimplifyInstruction(), llvm::SplitCriticalEdge(), llvm::successors(), std::swap(), and llvm::VerifyMemorySSA.

shouldSpeculateInstrs()

static 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 520 of file LoopRotationUtils.cpp.

STATISTIC()

STATISTIC	(	NumRotated	,
		"Number of loops rotated"
	)