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)
static PHINode *	findInnerReductionPhi (Loop *L, Value *V, SmallVectorImpl< Instruction * > &HasNoWrapInsts)
static bool	areInnerLoopExitPHIsSupported (Loop *InnerL, Loop *OuterL, SmallPtrSetImpl< PHINode * > &Reductions, PHINode *LcssaReduction)
static bool	areOuterLoopExitPHIsSupported (Loop *OuterLoop, Loop *InnerLoop)
static bool	areInnerLoopLatchPHIsSupported (Loop *OuterLoop, Loop *InnerLoop)
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 (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)
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 >	MaxMemInstrCount ("loop-interchange-max-meminstr-count", cl::init(64), cl::Hidden, cl::desc("Maximum number of load-store instructions that should be handled " "in the dependency matrix. 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::ZeroOrMore, 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::PerLoopCacheAnalysis, 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 * InnerL, Loop * OuterL, SmallPtrSetImpl< PHINode * > & Reductions, PHINode * LcssaReduction )

static

Definition at line 1341 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 1403 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 1370 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 1655 of file LoopInterchange.cpp.

References assert().

checkReductionKind()

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

static

Definition at line 977 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::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 )

static

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

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

Referenced by followLCSSA(), and moveLCSSAPhis().

hasSupportedLoopDepth()

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

static

Definition at line 408 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 333 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 154 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 429 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 356 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 345 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 2052 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 2102 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 130 of file LoopInterchange.cpp.

populateDependencyMatrix()

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

static

Definition at line 172 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, MaxMemInstrCount, 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 385 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 141 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 2221 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 2060 of file LoopInterchange.cpp.

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

updateSuccessor()

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

static

Definition at line 2079 of file LoopInterchange.cpp.

References assert(), Changed, llvm::count(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::User::operands(), 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().

MaxMemInstrCount

cl::opt< unsigned int > MaxMemInstrCount("loop-interchange-max-meminstr-count", cl::init(64), cl::Hidden, cl::desc( "Maximum number of load-store instructions that should be handled " "in the dependency matrix. Higher value may lead to more interchanges " "at the cost of compile-time")) ( "loop-interchange-max-meminstr-count" , cl::init(64) , cl::Hidden , cl::desc( "Maximum number of load-store instructions that should be handled " "in the dependency matrix. Higher value may lead to more interchanges " "at the cost of compile-time")  )

static

Referenced by populateDependencyMatrix(), and llvm::LoopInterchangePass::run().

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::ZeroOrMore, 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::PerLoopCacheAnalysis, 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::ZeroOrMore , 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::PerLoopCacheAnalysis, 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