LoopInterchange.cpp File Reference

#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <cassert>
#include <utility>
#include <vector>

Include dependency graph for LoopInterchange.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "loop-interchange"

Functions
	STATISTIC (LoopsInterchanged, "Number of loops interchanged")
static bool	populateDependencyMatrix (CharMatrix &DepMatrix, unsigned Level, Loop *L, DependenceInfo *DI)
static void	interChangeDependencies (CharMatrix &DepMatrix, unsigned FromIndx, unsigned ToIndx)
static bool	isOuterMostDepPositive (CharMatrix &DepMatrix, unsigned Row, unsigned Column)
static bool	containsNoDependence (CharMatrix &DepMatrix, unsigned Row, unsigned Column)
static bool	validDepInterchange (CharMatrix &DepMatrix, unsigned Row, unsigned OuterLoopId, char InnerDep, char OuterDep)
static bool	isLegalToInterChangeLoops (CharMatrix &DepMatrix, unsigned InnerLoopId, unsigned OuterLoopId)
static LoopVector	populateWorklist (Loop &L)
static PHINode *	getInductionVariable (Loop *L, ScalarEvolution *SE)
static Value *	followLCSSA (Value *SV)
static PHINode *	findInnerReductionPhi (Loop *L, Value *V)
static bool	containsSafePHI (BasicBlock *Block, bool isOuterLoopExitBlock)
static bool	areLoopExitPHIsSupported (Loop *OuterLoop, Loop *InnerLoop)
static bool	isProfitableForVectorization (unsigned InnerLoopId, unsigned OuterLoopId, CharMatrix &DepMatrix)
static void	moveBBContents (BasicBlock *FromBB, Instruction *InsertBefore)
	Move all instructions except the terminator from FromBB right before InsertBefore. More...
static void	updateSuccessor (BranchInst *BI, BasicBlock *OldBB, BasicBlock *NewBB, std::vector< DominatorTree::UpdateType > &DTUpdates)
	Update BI to jump to NewBB instead of OldBB. More...
static void	moveLCSSAPhis (BasicBlock *InnerExit, BasicBlock *InnerHeader, BasicBlock *InnerLatch, BasicBlock *OuterHeader, BasicBlock *OuterLatch, BasicBlock *OuterExit)
	INITIALIZE_PASS_BEGIN (LoopInterchange, "loop-interchange", "Interchanges loops for cache reuse", false, false) INITIALIZE_PASS_END(LoopInterchange

Variables
static cl::opt< int >	LoopInterchangeCostThreshold ("loop-interchange-threshold", cl::init(0), cl::Hidden, cl::desc("Interchange if you gain more than this number"))
static const unsigned	MaxMemInstrCount = 100
static const unsigned	MaxLoopNestDepth = 10
loop	interchange
loop Interchanges loops for cache	reuse
loop Interchanges loops for cache	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-interchange"

Definition at line 52 of file LoopInterchange.cpp.

Referenced by areLoopExitPHIsSupported(), containsSafePHI(), getInductionVariable(), and isProfitableForVectorization().

Function Documentation

areLoopExitPHIsSupported()

static bool areLoopExitPHIsSupported ( Loop *  OuterLoop, Loop *  InnerLoop  )

static

Definition at line 930 of file LoopInterchange.cpp.

References llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::dbgs(), DEBUG_TYPE, llvm::dyn_cast(), GEP, llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getParent(), llvm::Loop::getStartLoc(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), llvm::BasicBlock::getUniquePredecessor(), I, llvm::MipsISD::Ins, llvm::BasicBlock::instructionsWithoutDebug(), isLegalToInterChangeLoops(), LLVM_DEBUG, and llvm::BasicBlock::phis().

containsNoDependence()

static bool containsNoDependence ( CharMatrix &  DepMatrix, unsigned  Row, unsigned  Column  )

static

Definition at line 209 of file LoopInterchange.cpp.

Referenced by validDepInterchange().

containsSafePHI()

static bool containsSafePHI ( BasicBlock *  Block, bool  isOuterLoopExitBlock  )

static

Definition at line 719 of file LoopInterchange.cpp.

References llvm::SmallVectorImpl< T >::clear(), llvm::dbgs(), DEBUG_TYPE, llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getExitBlock(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Loop::getStartLoc(), llvm::BasicBlock::getTerminator(), I, llvm::MipsISD::Ins, llvm::BasicBlock::instructionsWithoutDebug(), LLVM_DEBUG, llvm::BasicBlock::phis(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::reverse(), and llvm::SmallVectorBase::size().

findInnerReductionPhi()

static PHINode* findInnerReductionPhi ( Loop *  L, Value *  V  )

static

Definition at line 663 of file LoopInterchange.cpp.

References llvm::any_of(), assert(), llvm::dbgs(), followLCSSA(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPredecessor(), llvm::PHINode::incoming_values(), llvm::InductionDescriptor::isInductionPHI(), llvm::RecurrenceDescriptor::isReductionPHI(), LLVM_DEBUG, llvm::BasicBlock::phis(), llvm::SmallVectorTemplateBase< T >::push_back(), and llvm::Value::users().

followLCSSA()

static Value* followLCSSA ( Value *  SV )

static

Definition at line 652 of file LoopInterchange.cpp.

References llvm::dyn_cast(), llvm::PHINode::getIncomingValue(), and llvm::PHINode::getNumIncomingValues().

Referenced by findInnerReductionPhi().

getInductionVariable()

static PHINode* getInductionVariable ( Loop *  L, ScalarEvolution *  SE  )

static

Definition at line 295 of file LoopInterchange.cpp.

References llvm::AnalysisUsage::addRequired(), llvm::any_of(), llvm::BasicBlock::begin(), llvm::dbgs(), DEBUG_TYPE, llvm::dyn_cast(), llvm::OptimizationRemarkEmitter::emit(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::Loop::getCanonicalInductionVariable(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::LoopBase< BlockT, LoopT >::getExitBlock(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValueNumForOperand(), llvm::getLoopAnalysisUsage(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPredecessor(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::LoopBase< BlockT, LoopT >::getNumBackEdges(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::PassRegistry::getPassRegistry(), llvm::ScalarEvolution::getSCEV(), llvm::Loop::getStartLoc(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, llvm::initializeLoopInterchangePass(), interChangeDependencies(), llvm::SCEVAddRecExpr::isAffine(), llvm::Loop::isLoopInvariant(), LLVM_DEBUG, llvm::Instruction::mayHaveSideEffects(), llvm::Instruction::mayReadFromMemory(), populateDependencyMatrix(), populateWorklist(), llvm::successors(), std::swap(), and llvm::transform().

Referenced by isProfitableForVectorization().

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	LoopInterchange	,
		"loop-interchange"	,
		"Interchanges loops for cache reuse"	,
		false	,
		false
	)

Referenced by moveLCSSAPhis().

interChangeDependencies()

static void interChangeDependencies ( CharMatrix &  DepMatrix, unsigned  FromIndx, unsigned  ToIndx  )

static

Definition at line 184 of file LoopInterchange.cpp.

Referenced by getInductionVariable().

isLegalToInterChangeLoops()

static bool isLegalToInterChangeLoops ( CharMatrix &  DepMatrix, unsigned  InnerLoopId, unsigned  OuterLoopId  )

static

Definition at line 257 of file LoopInterchange.cpp.

References validDepInterchange().

Referenced by areLoopExitPHIsSupported().

isOuterMostDepPositive()

static bool isOuterMostDepPositive ( CharMatrix &  DepMatrix, unsigned  Row, unsigned  Column  )

static

Definition at line 196 of file LoopInterchange.cpp.

Referenced by validDepInterchange().

isProfitableForVectorization()

static bool isProfitableForVectorization ( unsigned  InnerLoopId, unsigned  OuterLoopId, CharMatrix &  DepMatrix  )

static

Definition at line 1079 of file LoopInterchange.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBlockEntry(), llvm::LoopBase< BlockT, LoopT >::addChildLoop(), assert(), llvm::LoopBase< BlockT, LoopT >::begin(), llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::Instruction::clone(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dbgs(), DEBUG_TYPE, llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::empty(), llvm::BasicBlock::front(), llvm::BasicBlock::getFirstNonPHI(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), getInductionVariable(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::Loop::getStartLoc(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), llvm::BasicBlock::getTerminator(), llvm::Use::getUser(), llvm::Instruction::insertBefore(), LLVM_DEBUG, llvm_unreachable, LoopInterchangeCostThreshold, llvm::Instruction::mayHaveSideEffects(), llvm::Instruction::moveBefore(), llvm::LoopBase< BlockT, LoopT >::removeBlockFromLoop(), llvm::LoopBase< BlockT, LoopT >::removeChildLoop(), llvm::Use::set(), llvm::SplitBlock(), and llvm::transform().

moveBBContents()

static void moveBBContents ( BasicBlock *  FromBB, Instruction *  InsertBefore  )

static

Move all instructions except the terminator from FromBB right before InsertBefore.

Definition at line 1310 of file LoopInterchange.cpp.

References llvm::BasicBlock::getInstList(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), and llvm::iplist_impl< IntrusiveListT, TraitsT >::splice().

Referenced by moveLCSSAPhis().

moveLCSSAPhis()

static void moveLCSSAPhis ( BasicBlock *  InnerExit, BasicBlock *  InnerHeader, BasicBlock *  InnerLatch, BasicBlock *  OuterHeader, BasicBlock *  OuterLatch, BasicBlock *  OuterExit  )

static

Definition at line 1340 of file LoopInterchange.cpp.

References llvm::all_of(), assert(), llvm::BasicBlock::begin(), llvm::dbgs(), llvm::drop_begin(), llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getExitBlock(), llvm::BasicBlock::getFirstNonPHI(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::BasicBlock::getParent(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::BasicBlock::getUniquePredecessor(), llvm::BasicBlock::getUniqueSuccessor(), I, INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_DEPENDENCY, llvm::Instruction::insertBefore(), llvm::InsertPreheaderForLoop(), LLVM_DEBUG, llvm::make_early_inc_range(), moveBBContents(), P, llvm::BasicBlock::phis(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::BasicBlock::replacePhiUsesWith(), llvm::PHINode::setIncomingBlock(), llvm::PHINode::setIncomingValue(), and updateSuccessor().

populateDependencyMatrix()

static bool populateDependencyMatrix ( CharMatrix &  DepMatrix, unsigned  Level, Loop *  L, DependenceInfo *  DI  )

static

Definition at line 85 of file LoopInterchange.cpp.

References assert(), llvm::LoopBase< BlockT, LoopT >::blocks(), D, llvm::dbgs(), llvm::DependenceInfo::depends(), llvm::Dependence::DVEntry::EQ, llvm::Dependence::DVEntry::GE, llvm::SCEVConstant::getValue(), llvm::Dependence::DVEntry::GT, I, llvm::ARM_PROC::IE, llvm::ConstantInt::isNegative(), llvm::ConstantInt::isZero(), llvm::Dependence::DVEntry::LE, LLVM_DEBUG, llvm::Dependence::DVEntry::LT, MaxMemInstrCount, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by getInductionVariable().

populateWorklist()

static LoopVector populateWorklist ( Loop &  L )

static

Definition at line 273 of file LoopInterchange.cpp.

References llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), and LLVM_DEBUG.

Referenced by getInductionVariable().

STATISTIC()

STATISTIC	(	LoopsInterchanged	,
		"Number of loops interchanged"
	)

updateSuccessor()

static void updateSuccessor ( BranchInst *  BI, BasicBlock *  OldBB, BasicBlock *  NewBB, std::vector< DominatorTree::UpdateType > &  DTUpdates  )

static

Update BI to jump to NewBB instead of OldBB.

Records updates to the dominator tree in DTUpdates, if DT should be preserved.

Definition at line 1320 of file LoopInterchange.cpp.

References assert(), llvm::count_if(), llvm::cfg::Delete, llvm::numbers::e, llvm::BranchInst::getNumSuccessors(), llvm::Instruction::getParent(), llvm::BranchInst::getSuccessor(), llvm::cfg::Insert, llvm::BranchInst::setSuccessor(), and llvm::successors().

Referenced by moveLCSSAPhis().

validDepInterchange()

static bool validDepInterchange ( CharMatrix &  DepMatrix, unsigned  Row, unsigned  OuterLoopId, char  InnerDep, char  OuterDep  )

static

Definition at line 219 of file LoopInterchange.cpp.

References containsNoDependence(), and isOuterMostDepPositive().

Referenced by isLegalToInterChangeLoops().

Variable Documentation

false

loop Interchanges loops for cache false

Definition at line 1596 of file LoopInterchange.cpp.

interchange

loop interchange

Definition at line 1596 of file LoopInterchange.cpp.

LoopInterchangeCostThreshold

cl::opt<int> LoopInterchangeCostThreshold("loop-interchange-threshold", cl::init(0), cl::Hidden, cl::desc("Interchange if you gain more than this number"))

static

Referenced by isProfitableForVectorization().

MaxLoopNestDepth

const unsigned MaxLoopNestDepth = 10

static

Definition at line 73 of file LoopInterchange.cpp.

MaxMemInstrCount

const unsigned MaxMemInstrCount = 100

static

Definition at line 70 of file LoopInterchange.cpp.

Referenced by populateDependencyMatrix().

reuse

loop Interchanges loops for cache reuse

Definition at line 1596 of file LoopInterchange.cpp.