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/LoopCacheAnalysis.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/Scalar/LoopPassManager.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, ScalarEvolution *SE)
static void	interChangeDependencies (CharMatrix &DepMatrix, unsigned FromIndx, unsigned ToIndx)
static bool	isLexicographicallyPositive (std::vector< char > &DV)
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 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 865 of file LoopInterchange.cpp.

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

areInnerLoopLatchPHIsSupported()

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

static

Definition at line 923 of file LoopInterchange.cpp.

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

areOuterLoopExitPHIsSupported()

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

static

Definition at line 890 of file LoopInterchange.cpp.

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

findInnerReductionPhi()

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

static

Definition at line 711 of file LoopInterchange.cpp.

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

followLCSSA()

static Value* followLCSSA ( Value *  SV )

static

Definition at line 700 of file LoopInterchange.cpp.

References PHI.

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

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

isLegalToInterChangeLoops()

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

static

Definition at line 201 of file LoopInterchange.cpp.

References isLexicographicallyPositive(), and std::swap().

isLexicographicallyPositive()

static bool isLexicographicallyPositive ( std::vector< char > &  DV )

static

Definition at line 189 of file LoopInterchange.cpp.

Referenced by isLegalToInterChangeLoops().

moveBBContents()

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

static

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

Definition at line 1398 of file LoopInterchange.cpp.

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

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 1451 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, ScalarEvolution *  SE  )

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::Dependence::DVEntry::GT, I, llvm::ARM_PROC::IE, llvm::Dependence::DVEntry::LE, LLVM_DEBUG, llvm::Dependence::DVEntry::LT, and MaxMemInstrCount.

populateWorklist()

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

static

Definition at line 220 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 1406 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 1425 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().

Variable Documentation

false

loop Interchanges loops for cache false

Definition at line 1759 of file LoopInterchange.cpp.

interchange

loop interchange

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