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	updateIncomingBlock (BasicBlock *CurrBlock, BasicBlock *OldPred, BasicBlock *NewPred)
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 *InnerLatch, BasicBlock *OuterLatch)
	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 53 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 933 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 210 of file LoopInterchange.cpp.

Referenced by validDepInterchange().

containsSafePHI()

static bool containsSafePHI ( BasicBlock *  Block, bool  isOuterLoopExitBlock  )

static

Definition at line 722 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 666 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 655 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 296 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 185 of file LoopInterchange.cpp.

Referenced by getInductionVariable().

isLegalToInterChangeLoops()

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

static

Definition at line 258 of file LoopInterchange.cpp.

References validDepInterchange().

Referenced by areLoopExitPHIsSupported().

isOuterMostDepPositive()

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

static

Definition at line 197 of file LoopInterchange.cpp.

Referenced by validDepInterchange().

isProfitableForVectorization()

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

static

Definition at line 1082 of file LoopInterchange.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBlockEntry(), llvm::LoopBase< BlockT, LoopT >::addChildLoop(), llvm::LoopBase< BlockT, LoopT >::begin(), llvm::LoopBase< BlockT, LoopT >::blocks(), 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_DEBUG, llvm_unreachable, LoopInterchangeCostThreshold, llvm::Instruction::moveBefore(), llvm::LoopBase< BlockT, LoopT >::removeBlockFromLoop(), llvm::LoopBase< BlockT, LoopT >::removeChildLoop(), 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 1275 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 *  InnerLatch, BasicBlock *  OuterLatch  )

static

Definition at line 1316 of file LoopInterchange.cpp.

References assert(), llvm::BasicBlock::begin(), llvm::dbgs(), llvm::drop_begin(), llvm::dyn_cast(), E, llvm::BasicBlock::getFirstNonPHI(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::BasicBlock::getUniquePredecessor(), llvm::BasicBlock::getUniqueSuccessor(), llvm::Use::getUser(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_DEPENDENCY, llvm::InsertPreheaderForLoop(), LLVM_DEBUG, moveBBContents(), P, llvm::BasicBlock::phis(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::Use::set(), updateIncomingBlock(), and updateSuccessor().

populateDependencyMatrix()

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

static

Definition at line 86 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 274 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"
	)

updateIncomingBlock()

static void updateIncomingBlock ( BasicBlock *  CurrBlock, BasicBlock *  OldPred, BasicBlock *  NewPred  )

static

Definition at line 1283 of file LoopInterchange.cpp.

References llvm::BasicBlock::phis().

Referenced by moveLCSSAPhis().

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 1296 of file LoopInterchange.cpp.

References assert(), llvm::count_if(), llvm::cfg::Delete, 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 220 of file LoopInterchange.cpp.

References containsNoDependence(), and isOuterMostDepPositive().

Referenced by isLegalToInterChangeLoops().

Variable Documentation

false

loop Interchanges loops for cache false

Definition at line 1528 of file LoopInterchange.cpp.

interchange

loop interchange

Definition at line 1528 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 74 of file LoopInterchange.cpp.

MaxMemInstrCount

const unsigned MaxMemInstrCount = 100

static

Definition at line 71 of file LoopInterchange.cpp.

Referenced by populateDependencyMatrix().

reuse

loop Interchanges loops for cache reuse

Definition at line 1528 of file LoopInterchange.cpp.