LoopInterchange.cpp File Reference

#include "llvm/Transforms/Scalar/LoopInterchange.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringMap.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/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/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/LoopPassManager.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <cassert>
#include <utility>
#include <vector>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "loop-interchange"

Functions
	STATISTIC (LoopsInterchanged, "Number of loops interchanged")
static bool	noDuplicateRulesAndIgnore (ArrayRef< RuleTy > Rules)
static void	printDepMatrix (CharMatrix &DepMatrix)
static bool	inThisOrder (const Instruction *Src, const Instruction *Dst)
	Return true if Src appears before Dst in the same basic block.
static bool	populateDependencyMatrix (CharMatrix &DepMatrix, unsigned Level, Loop *L, DependenceInfo *DI, ScalarEvolution *SE, OptimizationRemarkEmitter *ORE)
static void	interChangeDependencies (CharMatrix &DepMatrix, unsigned FromIndx, unsigned ToIndx)
static std::optional< bool >	isLexicographicallyPositive (ArrayRef< char > DV, unsigned Begin, unsigned End)
static bool	isLegalToInterChangeLoops (CharMatrix &DepMatrix, unsigned InnerLoopId, unsigned OuterLoopId)
static void	populateWorklist (Loop &L, LoopVector &LoopList)
static bool	hasSupportedLoopDepth (ArrayRef< Loop * > LoopList, OptimizationRemarkEmitter &ORE)
static bool	isComputableLoopNest (ScalarEvolution *SE, ArrayRef< Loop * > LoopList)
static Value *	followLCSSA (Value *SV)
static bool	checkReductionKind (Loop *L, PHINode *PHI, SmallVectorImpl< Instruction * > &HasNoWrapInsts, SmallVectorImpl< Instruction * > &HasNoInfInsts)
static PHINode *	findInnerReductionPhi (Loop *L, Value *V, SmallVectorImpl< Instruction * > &HasNoWrapInsts, SmallVectorImpl< Instruction * > &HasNoInfInsts)
static bool	areInnerLoopExitPHIsSupported (Loop *OuterL, Loop *InnerL, SmallPtrSetImpl< PHINode * > &Reductions, PHINode *LcssaReduction)
	We currently only support LCSSA PHI nodes in the inner loop exit if their users are either of the following:
static bool	areOuterLoopExitPHIsSupported (Loop *OuterLoop, Loop *InnerLoop)
static bool	areInnerLoopLatchPHIsSupported (Loop *OuterLoop, Loop *InnerLoop)
std::optional< const SCEV * >	getAddRecCoefficient (ScalarEvolution &SE, const SCEV *S, const Loop *L)
	If \S contains an affine addrec for L, return the step recurrence of it.
static bool	canVectorize (const CharMatrix &DepMatrix, unsigned LoopId)
	Return true if we can vectorize the loop specified by LoopId.
static void	moveBBContents (BasicBlock *FromBB, Instruction *InsertBefore)
	Move all instructions except the terminator from FromBB right before InsertBefore.
static void	swapBBContents (BasicBlock *BB1, BasicBlock *BB2)
	Swap instructions between BB1 and BB2 but keep terminators intact.
static void	updateSuccessor (Instruction *Term, 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)
static void	simplifyLCSSAPhis (Loop *OuterLoop, Loop *InnerLoop)
	This deals with a corner case when a LCSSA phi node appears in a non-exit block: the outer loop latch block does not need to be exit block of the inner loop.

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 cl::opt< unsigned int >	MaxMemInstrRatio ("loop-interchange-max-mem-instr-ratio", cl::init(4), cl::Hidden, cl::desc("Maximum number of load/store instructions squared in relation to " "the total number of instructions. Higher value may lead to more " "interchanges at the cost of compile-time"))
static cl::opt< unsigned int >	MinLoopNestDepth ("loop-interchange-min-loop-nest-depth", cl::init(2), cl::Hidden, cl::desc("Minimum depth of loop nest considered for the transform"))
static cl::opt< unsigned int >	MaxLoopNestDepth ("loop-interchange-max-loop-nest-depth", cl::init(10), cl::Hidden, cl::desc("Maximum depth of loop nest considered for the transform"))
static cl::list< RuleTy >	Profitabilities ("loop-interchange-profitabilities", cl::MiscFlags::CommaSeparated, cl::Hidden, cl::desc("List of profitability heuristics to be used. They are applied in " "the given order"), cl::list_init< RuleTy >({RuleTy::PerInstrOrderCost, RuleTy::ForVectorization}), cl::values(clEnumValN(RuleTy::PerLoopCacheAnalysis, "cache", "Prioritize loop cache cost"), clEnumValN(RuleTy::PerInstrOrderCost, "instorder", "Prioritize the IVs order of each instruction"), clEnumValN(RuleTy::ForVectorization, "vectorize", "Prioritize vectorization"), clEnumValN(RuleTy::Ignore, "ignore", "Ignore profitability, force interchange (does not " "work with other options)")))
static cl::opt< bool >	EnableReduction2Memory ("loop-interchange-reduction-to-mem", cl::init(false), cl::Hidden, cl::desc("Support for the inner-loop reduction pattern."))

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-interchange"

Definition at line 55 of file LoopInterchange.cpp.

Function Documentation

areInnerLoopExitPHIsSupported()

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

static

We currently only support LCSSA PHI nodes in the inner loop exit if their users are either of the following:

• Reduction PHIs
• PHIs outside the outer loop
• PHIs belonging to the latch of the outer loop

These conditions mean that we are only interested in the final value after the inner loop.

Definition at line 1367 of file LoopInterchange.cpp.

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

areInnerLoopLatchPHIsSupported()

bool areInnerLoopLatchPHIsSupported ( Loop * OuterLoop, Loop * InnerLoop )

static

Definition at line 1434 of file LoopInterchange.cpp.

References llvm::cast(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), llvm::BasicBlock::getUniquePredecessor(), PHI, and llvm::BasicBlock::phis().

areOuterLoopExitPHIsSupported()

bool areOuterLoopExitPHIsSupported ( Loop * OuterLoop, Loop * InnerLoop )

static

Definition at line 1401 of file LoopInterchange.cpp.

References llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), llvm::BasicBlock::getUniquePredecessor(), PHI, and llvm::BasicBlock::phis().

canVectorize()

bool canVectorize ( const CharMatrix & DepMatrix, unsigned LoopId )

static

Return true if we can vectorize the loop specified by LoopId.

Definition at line 1734 of file LoopInterchange.cpp.

References assert().

checkReductionKind()

bool checkReductionKind ( Loop * L, PHINode * PHI, SmallVectorImpl< Instruction * > & HasNoWrapInsts, SmallVectorImpl< Instruction * > & HasNoInfInsts )

static

Definition at line 985 of file LoopInterchange.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, llvm::Add, llvm::And, llvm::AnyOf, assert(), llvm::FAdd, llvm::FMax, llvm::FMaximum, llvm::FMaximumNum, llvm::FMin, llvm::FMinimum, llvm::FMinimumNum, llvm::FMul, llvm::FMulAdd, llvm::RecurrenceDescriptor::getExactFPMathInst(), llvm::RecurrenceDescriptor::getOpcode(), llvm::RecurrenceDescriptor::getRecurrenceKind(), llvm::RecurrenceDescriptor::getReductionOpChain(), I, llvm::isa(), llvm::RecurrenceDescriptor::isReductionPHI(), llvm::Mul, llvm::Or, PHI, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SMax, llvm::SMin, llvm::UMax, llvm::UMin, and llvm::Xor.

Referenced by findInnerReductionPhi().

findInnerReductionPhi()

PHINode * findInnerReductionPhi ( Loop * L, Value * V, SmallVectorImpl< Instruction * > & HasNoWrapInsts, SmallVectorImpl< Instruction * > & HasNoInfInsts )

static

Definition at line 1069 of file LoopInterchange.cpp.

References checkReductionKind(), llvm::dyn_cast(), llvm::isa(), PHI, and llvm::Value::users().

followLCSSA()

Value * followLCSSA ( Value * SV )

static

Definition at line 975 of file LoopInterchange.cpp.

References llvm::dyn_cast(), followLCSSA(), and PHI.

Referenced by followLCSSA(), and moveLCSSAPhis().

getAddRecCoefficient()

std::optional< const SCEV * > getAddRecCoefficient	(	ScalarEvolution &	SE,
		const SCEV *	S,
		const Loop *	L )

If \S contains an affine addrec for L, return the step recurrence of it.

If \S is loop invariant with respect to L, return nullptr. Otherwise, return std::nullopt, which indicates we cannot determine the coefficient of the addrec for L in \S. TODO: Handle more complex cases. Maybe using SCEVTraversal is a good way to do that.

Definition at line 1615 of file LoopInterchange.cpp.

References assert(), llvm::dbgs(), llvm::dyn_cast(), getAddRecCoefficient(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEVAddRecExpr::isAffine(), llvm::ScalarEvolution::isLoopInvariant(), and LLVM_DEBUG.

Referenced by getAddRecCoefficient().

hasSupportedLoopDepth()

bool hasSupportedLoopDepth ( ArrayRef< Loop * > LoopList, OptimizationRemarkEmitter & ORE )

static

Definition at line 414 of file LoopInterchange.cpp.

References llvm::dbgs(), DEBUG_TYPE, llvm::OptimizationRemarkEmitter::emit(), llvm::ArrayRef< T >::front(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Loop::getStartLoc(), LLVM_DEBUG, MaxLoopNestDepth, MinLoopNestDepth, and llvm::ArrayRef< T >::size().

Referenced by llvm::LoopInterchangePass::run().

interChangeDependencies()

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

static

Definition at line 339 of file LoopInterchange.cpp.

References std::swap().

inThisOrder()

bool inThisOrder ( const Instruction * Src, const Instruction * Dst )

static

Return true if Src appears before Dst in the same basic block.

Precondition: Src and \Dst are distinct instructions within the same basic block.

Definition at line 151 of file LoopInterchange.cpp.

References assert(), I, and llvm_unreachable.

Referenced by populateDependencyMatrix().

isComputableLoopNest()

bool isComputableLoopNest ( ScalarEvolution * SE, ArrayRef< Loop * > LoopList )

static

Definition at line 435 of file LoopInterchange.cpp.

References llvm::dbgs(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::isa(), and LLVM_DEBUG.

Referenced by llvm::LoopInterchangePass::run().

isLegalToInterChangeLoops()

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

static

Definition at line 362 of file LoopInterchange.cpp.

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

isLexicographicallyPositive()

std::optional< bool > isLexicographicallyPositive ( ArrayRef< char > DV, unsigned Begin, unsigned End )

static

Definition at line 351 of file LoopInterchange.cpp.

References llvm::ArrayRef< T >::slice().

Referenced by isLegalToInterChangeLoops().

moveBBContents()

void moveBBContents ( BasicBlock * FromBB, Instruction * InsertBefore )

static

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

Definition at line 2139 of file LoopInterchange.cpp.

References llvm::BasicBlock::begin(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getTerminator(), and llvm::BasicBlock::splice().

moveLCSSAPhis()

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

static

Definition at line 2189 of file LoopInterchange.cpp.

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

noDuplicateRulesAndIgnore()

bool noDuplicateRulesAndIgnore ( ArrayRef< RuleTy > Rules )

static

Definition at line 127 of file LoopInterchange.cpp.

populateDependencyMatrix()

bool populateDependencyMatrix ( CharMatrix & DepMatrix, unsigned Level, Loop * L, DependenceInfo * DI, ScalarEvolution * SE, OptimizationRemarkEmitter * ORE )

static

Definition at line 169 of file LoopInterchange.cpp.

References llvm::all_of(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::cast(), D(), llvm::dbgs(), DEBUG_TYPE, llvm::DependenceInfo::depends(), llvm::dyn_cast(), llvm::OptimizationRemarkEmitter::emit(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::Dependence::DVEntry::EQ, llvm::equal_to(), llvm::Dependence::DVEntry::GT, I, II, inThisOrder(), llvm::isa(), LLVM_DEBUG, llvm::Dependence::DVEntry::LT, MaxMemInstrRatio, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorTemplateCommon< T, typename >::size(), llvm::StringRef::size(), and llvm::StringMap< ValueTy, AllocatorTy >::try_emplace().

populateWorklist()

void populateWorklist ( Loop & L, LoopVector & LoopList )

static

Definition at line 391 of file LoopInterchange.cpp.

References assert(), llvm::dbgs(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), LLVM_DEBUG, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

printDepMatrix()

void printDepMatrix ( CharMatrix & DepMatrix )

static

Definition at line 138 of file LoopInterchange.cpp.

References D(), llvm::dbgs(), llvm::drop_end(), and LLVM_DEBUG.

simplifyLCSSAPhis()

void simplifyLCSSAPhis ( Loop * OuterLoop, Loop * InnerLoop )

static

This deals with a corner case when a LCSSA phi node appears in a non-exit block: the outer loop latch block does not need to be exit block of the inner loop.

Consider a loop that was in LCSSA form, but then some transformation like loop-unswitch comes along and creates an empty block, where BB5 in this example is the outer loop latch block:

BB4: br label BB5 BB5: old.cond.lcssa = phi i16 [ cond, BB4 ] br outer.header

Interchange then brings it in LCSSA form again resulting in this chain of single-input phi nodes:

BB4: new.cond.lcssa = phi i16 [ cond, BB3 ] br label BB5 BB5: old.cond.lcssa = phi i16 [ new.cond.lcssa, BB4 ]

The problem is that interchange can reoder blocks BB4 and BB5 placing the use before the def if we don't check this. The solution is to simplify lcssa phi nodes (remove) if they appear in non-exit blocks.

Definition at line 2308 of file LoopInterchange.cpp.

References assert(), llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::getExitBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), LLVM_DEBUG, llvm::make_pointer_range(), and llvm::BasicBlock::phis().

STATISTIC()

STATISTIC	(	LoopsInterchanged	,
		"Number of loops interchanged"	)

swapBBContents()

void swapBBContents ( BasicBlock * BB1, BasicBlock * BB2 )

static

Swap instructions between BB1 and BB2 but keep terminators intact.

Definition at line 2147 of file LoopInterchange.cpp.

References llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::BasicBlock::getTerminator(), I, llvm::map_range(), and moveBBContents().

updateSuccessor()

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

static

Definition at line 2166 of file LoopInterchange.cpp.

References assert(), Changed, llvm::count(), and llvm::successors().

Variable Documentation

EnableReduction2Memory

cl::opt< bool > EnableReduction2Memory("loop-interchange-reduction-to-mem", cl::init(false), cl::Hidden, cl::desc("Support for the inner-loop reduction pattern.")) ( "loop-interchange-reduction-to-mem" , cl::init(false) , cl::Hidden , cl::desc("Support for the inner-loop reduction pattern.")  )

static

LoopInterchangeCostThreshold

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

static

MaxLoopNestDepth

cl::opt< unsigned int > MaxLoopNestDepth("loop-interchange-max-loop-nest-depth", cl::init(10), cl::Hidden, cl::desc("Maximum depth of loop nest considered for the transform")) ( "loop-interchange-max-loop-nest-depth" , cl::init(10) , cl::Hidden , cl::desc("Maximum depth of loop nest considered for the transform")  )

static

Referenced by hasSupportedLoopDepth().

MaxMemInstrRatio

cl::opt< unsigned int > MaxMemInstrRatio("loop-interchange-max-mem-instr-ratio", cl::init(4), cl::Hidden, cl::desc("Maximum number of load/store instructions squared in relation to " "the total number of instructions. Higher value may lead to more " "interchanges at the cost of compile-time")) ( "loop-interchange-max-mem-instr-ratio" , cl::init(4) , cl::Hidden , cl::desc("Maximum number of load/store instructions squared in relation to " "the total number of instructions. Higher value may lead to more " "interchanges at the cost of compile-time")  )

static

Referenced by populateDependencyMatrix().

MinLoopNestDepth

cl::opt< unsigned int > MinLoopNestDepth("loop-interchange-min-loop-nest-depth", cl::init(2), cl::Hidden, cl::desc("Minimum depth of loop nest considered for the transform")) ( "loop-interchange-min-loop-nest-depth" , cl::init(2) , cl::Hidden , cl::desc("Minimum depth of loop nest considered for the transform")  )

static

Referenced by hasSupportedLoopDepth().

Profitabilities

cl::list< RuleTy > Profitabilities("loop-interchange-profitabilities", cl::MiscFlags::CommaSeparated, cl::Hidden, cl::desc("List of profitability heuristics to be used. They are applied in " "the given order"), cl::list_init< RuleTy >({RuleTy::PerInstrOrderCost, RuleTy::ForVectorization}), cl::values(clEnumValN(RuleTy::PerLoopCacheAnalysis, "cache", "Prioritize loop cache cost"), clEnumValN(RuleTy::PerInstrOrderCost, "instorder", "Prioritize the IVs order of each instruction"), clEnumValN(RuleTy::ForVectorization, "vectorize", "Prioritize vectorization"), clEnumValN(RuleTy::Ignore, "ignore", "Ignore profitability, force interchange (does not " "work with other options)"))) ( "loop-interchange-profitabilities" , cl::MiscFlags::CommaSeparated , cl::Hidden , cl::desc("List of profitability heuristics to be used. They are applied in " "the given order") , cl::list_init< RuleTy > {RuleTy::PerInstrOrderCost, RuleTy::ForVectorization}, cl::values(clEnumValN(RuleTy::PerLoopCacheAnalysis, "cache", "Prioritize loop cache cost"), clEnumValN(RuleTy::PerInstrOrderCost, "instorder", "Prioritize the IVs order of each instruction"), clEnumValN(RuleTy::ForVectorization, "vectorize", "Prioritize vectorization"), clEnumValN(RuleTy::Ignore, "ignore", "Ignore profitability, force interchange (does not " "work with other options)"))  )

static