LoopInterchange.cpp File Reference

#include "llvm/Transforms/Scalar/LoopInterchange.h"
#include "ScalarOptions.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/IR/Verifier.h"
#include "llvm/Support/Casting.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 <cstdint>
#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< LoopInterchangeRule > 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 (const ScalarOptions &Opts, 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 (const ScalarOptions &Opts, ArrayRef< Loop * > LoopList, OptimizationRemarkEmitter &ORE)
static bool	isComputableLoopNest (ScalarEvolution *SE, ArrayRef< Loop * > LoopList)
static FreezeInst *	findFreezeInReNestedBlocks (Loop *OuterLoop, Loop *InnerLoop)
static FreezeInst *	findFreezeInInnerLatchCloneSet (Loop *InnerLoop, ArrayRef< PHINode * > InnerLoopInductions)
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 *InnerLoop, ArrayRef< PHINode * > InductionPHIs)
	The transform partially clones the inner loop's latch block, but PHI nodes cannot be cloned this way.
static 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
constexpr LoopInterchangeRule	DefaultProfitabilities []

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-interchange"

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

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

areInnerLoopLatchPHIsSupported()

bool areInnerLoopLatchPHIsSupported ( Loop * InnerLoop, ArrayRef< PHINode * > InductionPHIs )

static

The transform partially clones the inner loop's latch block, but PHI nodes cannot be cloned this way.

This function follows the instruction trees that would be cloned and checks whether any PHI node other than the induction PHIs feeds them. If such a PHI is found, the interchange is rejected.

TODO: This check strongly depends on the current implementation of the transform. Ideally, the transform should be able to handle such PHI nodes in the inner loop latch.

Definition at line 1582 of file LoopInterchange.cpp.

References llvm::ArrayRef< T >::begin(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::dyn_cast(), llvm::ArrayRef< T >::end(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::BasicBlock::getTerminator(), I, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::is_contained(), llvm::isa(), llvm::User::operands(), and llvm::SetVector< T, Vector, Set, N >::size().

areOuterLoopExitPHIsSupported()

bool areOuterLoopExitPHIsSupported ( Loop * OuterLoop, Loop * InnerLoop )

static

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

References assert().

checkReductionKind()

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

static

Definition at line 1082 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(), llvm::RecurrenceDescriptor::hasUsesOutsideReductionChain(), 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().

findFreezeInInnerLatchCloneSet()

FreezeInst * findFreezeInInnerLatchCloneSet ( Loop * InnerLoop, ArrayRef< PHINode * > InnerLoopInductions )

static

Definition at line 863 of file LoopInterchange.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), llvm::BasicBlock::getTerminator(), I, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::is_contained(), llvm::none_of(), llvm::User::operands(), and llvm::SetVector< T, Vector, Set, N >::size().

findFreezeInReNestedBlocks()

FreezeInst * findFreezeInReNestedBlocks ( Loop * OuterLoop, Loop * InnerLoop )

static

Definition at line 843 of file LoopInterchange.cpp.

References llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getExitBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), and I.

findInnerReductionPhi()

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

static

Definition at line 1186 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 1072 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 )

static

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 1813 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 ( const ScalarOptions & Opts, ArrayRef< Loop * > LoopList, OptimizationRemarkEmitter & ORE )

static

Definition at line 374 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, and llvm::ArrayRef< T >::size().

interChangeDependencies()

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

static

Definition at line 299 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 106 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 400 of file LoopInterchange.cpp.

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

isLegalToInterChangeLoops()

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

static

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

References llvm::End, and 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 2331 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().

Referenced by swapBBContents().

moveLCSSAPhis()

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

static

Definition at line 2381 of file LoopInterchange.cpp.

References llvm::PHINode::addIncoming(), llvm::all_of(), assert(), llvm::dyn_cast(), followLCSSA(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::BasicBlock::getParent(), I, llvm::Instruction::insertBefore(), llvm::Loop::isLoopInvariant(), 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< LoopInterchangeRule > Rules )

static

Definition at line 82 of file LoopInterchange.cpp.

References llvm::Ignore.

populateDependencyMatrix()

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

static

Definition at line 124 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, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorTemplateCommon< T, typename >::size(), llvm::StringRef::size(), llvm::StringMap< ValueTy, AllocatorTy >::try_emplace(), and uint64_t.

populateWorklist()

void populateWorklist ( Loop & L, LoopVector & LoopList )

static

Definition at line 351 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 93 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 2513 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 2339 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 2358 of file LoopInterchange.cpp.

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

Variable Documentation

DefaultProfitabilities

LoopInterchangeRule DefaultProfitabilities[]

constexpr

Initial value:

= {
    LoopInterchangeRule::PerInstrOrderCost,
    LoopInterchangeRule::ForVectorization}

Definition at line 77 of file LoopInterchange.cpp.