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/Type.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.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	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 56 of file LoopInterchange.cpp.

Function Documentation

areInnerLoopExitPHIsSupported()

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

static

Definition at line 970 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 1033 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 995 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 209 of file LoopInterchange.cpp.

References i.

Referenced by validDepInterchange().

findInnerReductionPhi()

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

static

Definition at line 734 of file LoopInterchange.cpp.

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

followLCSSA()

static Value* followLCSSA ( Value *  SV )

static

Definition at line 723 of file LoopInterchange.cpp.

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

getInductionVariable()

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

static

Definition at line 295 of file LoopInterchange.cpp.

References llvm::BasicBlock::begin(), llvm::Loop::getCanonicalInductionVariable(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPredecessor(), llvm::ScalarEvolution::getSCEV(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::Value::getType(), I, llvm::SCEVAddRecExpr::isAffine(), llvm::Type::isFloatingPointTy(), llvm::Type::isIntegerTy(), and llvm::Type::isPointerTy().

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

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

isLegalToInterChangeLoops()

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

static

Definition at line 257 of file LoopInterchange.cpp.

References validDepInterchange().

isOuterMostDepPositive()

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

static

Definition at line 196 of file LoopInterchange.cpp.

References i.

Referenced by validDepInterchange().

isProfitableForVectorization()

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

static

Definition at line 1206 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 1450 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 1504 of file LoopInterchange.cpp.

References llvm::PHINode::addIncoming(), llvm::all_of(), assert(), 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 89 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 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.

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 1459 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 1478 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 219 of file LoopInterchange.cpp.

References containsNoDependence(), and isOuterMostDepPositive().

Referenced by isLegalToInterChangeLoops().

Variable Documentation

false

loop Interchanges loops for cache false

Definition at line 1806 of file LoopInterchange.cpp.

interchange

loop interchange

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

MaxMemInstrCount

const unsigned MaxMemInstrCount = 100

static

Definition at line 74 of file LoopInterchange.cpp.

Referenced by populateDependencyMatrix().

reuse

loop Interchanges loops for cache reuse

Definition at line 1806 of file LoopInterchange.cpp.