LoopInterchange.cpp File Reference

#include "llvm/Transforms/Scalar/LoopInterchange.h"
#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/LoopNestAnalysis.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/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.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/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 void	populateWorklist (Loop &L, LoopVector &LoopList)
static Value *	followLCSSA (Value *SV)
static PHINode *	findInnerReductionPhi (Loop *L, Value *V)
static bool	areInnerLoopExitPHIsSupported (Loop *InnerL, Loop *OuterL, SmallPtrSetImpl< PHINode * > &Reductions)
static bool	areOuterLoopExitPHIsSupported (Loop *OuterLoop, Loop *InnerLoop)
static bool	areInnerLoopLatchPHIsSupported (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	swapBBContents (BasicBlock *BB1, BasicBlock *BB2)
	Swap instructions between BB1 and BB2 but keep terminators intact. More...
static void	updateSuccessor (BranchInst *BI, BasicBlock *OldBB, BasicBlock *NewBB, std::vector< DominatorTree::UpdateType > &DTUpdates, bool MustUpdateOnce=true)
static void	moveLCSSAPhis (BasicBlock *InnerExit, BasicBlock *InnerHeader, BasicBlock *InnerLatch, BasicBlock *OuterHeader, BasicBlock *OuterLatch, BasicBlock *OuterExit, Loop *InnerLoop, LoopInfo *LI)
	INITIALIZE_PASS_BEGIN (LoopInterchangeLegacyPass, "loop-interchange", "Interchanges loops for cache reuse", false, false) INITIALIZE_PASS_END(LoopInterchangeLegacyPass

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

Function Documentation

areInnerLoopExitPHIsSupported()

static bool areInnerLoopExitPHIsSupported ( Loop *  InnerL, Loop *  OuterL, SmallPtrSetImpl< PHINode * > &  Reductions  )

static

Definition at line 883 of file LoopInterchange.cpp.

References llvm::any_of(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), and llvm::BasicBlock::phis().

areInnerLoopLatchPHIsSupported()

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

static

Definition at line 941 of file LoopInterchange.cpp.

References llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), llvm::BasicBlock::getUniquePredecessor(), and llvm::BasicBlock::phis().

areOuterLoopExitPHIsSupported()

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

static

Definition at line 908 of file LoopInterchange.cpp.

References llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), llvm::BasicBlock::getUniquePredecessor(), i, and llvm::BasicBlock::phis().

containsNoDependence()

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

static

Definition at line 205 of file LoopInterchange.cpp.

References i.

Referenced by validDepInterchange().

findInnerReductionPhi()

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

static

Definition at line 737 of file LoopInterchange.cpp.

References llvm::RecurrenceDescriptor::getExactFPMathInst(), llvm::RecurrenceDescriptor::isReductionPHI(), and llvm::Value::users().

followLCSSA()

static Value* followLCSSA ( Value *  SV )

static

Definition at line 726 of file LoopInterchange.cpp.

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

Referenced by moveLCSSAPhis().

INITIALIZE_PASS_BEGIN()

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

interChangeDependencies()

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

static

Definition at line 184 of file LoopInterchange.cpp.

References E, I, and std::swap().

isLegalToInterChangeLoops()

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

static

Definition at line 253 of file LoopInterchange.cpp.

References validDepInterchange().

isOuterMostDepPositive()

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

static

Definition at line 192 of file LoopInterchange.cpp.

References i.

Referenced by validDepInterchange().

isProfitableForVectorization()

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

static

Definition at line 1119 of file LoopInterchange.cpp.

moveBBContents()

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

static

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

Definition at line 1365 of file LoopInterchange.cpp.

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

Referenced by swapBBContents().

moveLCSSAPhis()

static void moveLCSSAPhis ( BasicBlock *  InnerExit, BasicBlock *  InnerHeader, BasicBlock *  InnerLatch, BasicBlock *  OuterHeader, BasicBlock *  OuterLatch, BasicBlock *  OuterExit, Loop *  InnerLoop, LoopInfo *  LI  )

static

Definition at line 1419 of file LoopInterchange.cpp.

References llvm::PHINode::addIncoming(), llvm::all_of(), assert(), followLCSSA(), llvm::BasicBlock::getFirstNonPHI(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::BasicBlock::getParent(), I, llvm::Instruction::insertBefore(), llvm::make_early_inc_range(), P, llvm::BasicBlock::phis(), llvm::predecessors(), llvm::BasicBlock::replacePhiUsesWith(), llvm::PHINode::setIncomingBlock(), and llvm::PHINode::setIncomingValue().

populateDependencyMatrix()

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

static

Definition at line 87 of file LoopInterchange.cpp.

References assert(), BB, 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, and MaxMemInstrCount.

populateWorklist()

static void populateWorklist ( Loop &  L, LoopVector &  LoopList  )

static

Definition at line 269 of file LoopInterchange.cpp.

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

STATISTIC()

STATISTIC	(	LoopsInterchanged	,
		"Number of loops interchanged"
	)

swapBBContents()

static void swapBBContents ( BasicBlock *  BB1, BasicBlock *  BB2  )

static

Swap instructions between BB1 and BB2 but keep terminators intact.

Definition at line 1374 of file LoopInterchange.cpp.

References llvm::BasicBlock::getTerminator(), I, llvm::map_range(), and moveBBContents().

updateSuccessor()

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

static

Definition at line 1393 of file LoopInterchange.cpp.

References assert(), BB, llvm::count_if(), llvm::cfg::Delete, llvm::Instruction::getParent(), llvm::cfg::Insert, llvm::User::operands(), and llvm::successors().

validDepInterchange()

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

static

Definition at line 215 of file LoopInterchange.cpp.

References containsNoDependence(), and isOuterMostDepPositive().

Referenced by isLegalToInterChangeLoops().

Variable Documentation

false

loop Interchanges loops for cache false

Definition at line 1727 of file LoopInterchange.cpp.

interchange

loop interchange

Definition at line 1726 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

MaxLoopNestDepth

const unsigned MaxLoopNestDepth = 10

static

Definition at line 75 of file LoopInterchange.cpp.

MaxMemInstrCount

const unsigned MaxMemInstrCount = 100

static

Definition at line 72 of file LoopInterchange.cpp.

Referenced by populateDependencyMatrix().

reuse

loop Interchanges loops for cache reuse

Definition at line 1727 of file LoopInterchange.cpp.