LLVM  16.0.0git
Macros | Functions | Variables
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.


#define DEBUG_TYPE   "loop-interchange"


 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 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 void populateWorklist (Loop &L, LoopVector &LoopList)
static ValuefollowLCSSA (Value *SV)
static PHINodefindInnerReductionPhi (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


static cl::opt< intLoopInterchangeCostThreshold ("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


#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 

◆ areInnerLoopLatchPHIsSupported()

static bool areInnerLoopLatchPHIsSupported ( Loop OuterLoop,
Loop InnerLoop 

◆ areOuterLoopExitPHIsSupported()

static bool areOuterLoopExitPHIsSupported ( Loop OuterLoop,
Loop InnerLoop 

◆ containsNoDependence()

static bool containsNoDependence ( CharMatrix &  DepMatrix,
unsigned  Row,
unsigned  Column 

Definition at line 186 of file LoopInterchange.cpp.

References i.

Referenced by validDepInterchange().

◆ findInnerReductionPhi()

static PHINode* findInnerReductionPhi ( Loop L,
Value V 

◆ followLCSSA()

static Value* followLCSSA ( Value SV)

Definition at line 720 of file LoopInterchange.cpp.

References PHI.

Referenced by moveLCSSAPhis().


INITIALIZE_PASS_BEGIN ( LoopInterchangeLegacyPass  ,
"loop-interchange ,
"Interchanges loops for cache reuse ,
false  ,

◆ interChangeDependencies()

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

Definition at line 179 of file LoopInterchange.cpp.

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

◆ isLegalToInterChangeLoops()

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

Definition at line 231 of file LoopInterchange.cpp.

References validDepInterchange().

◆ isProfitableForVectorization()

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

Definition at line 1113 of file LoopInterchange.cpp.

◆ moveBBContents()

static void moveBBContents ( BasicBlock FromBB,
Instruction InsertBefore 

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

Definition at line 1371 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 

◆ populateDependencyMatrix()

static bool populateDependencyMatrix ( CharMatrix &  DepMatrix,
unsigned  Level,
Loop L,
DependenceInfo DI,
ScalarEvolution SE 

◆ populateWorklist()

static void populateWorklist ( Loop L,
LoopVector &  LoopList 


STATISTIC ( LoopsInterchanged  ,
"Number of loops interchanged"   

◆ swapBBContents()

static void swapBBContents ( BasicBlock BB1,
BasicBlock BB2 

Swap instructions between BB1 and BB2 but keep terminators intact.

Definition at line 1380 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 

◆ validDepInterchange()

static bool validDepInterchange ( CharMatrix &  DepMatrix,
unsigned  Row,
unsigned  OuterLoopId,
char  InnerDep,
char  OuterDep 

Definition at line 196 of file LoopInterchange.cpp.

References containsNoDependence().

Referenced by isLegalToInterChangeLoops().

Variable Documentation

◆ false

loop Interchanges loops for cache false

Definition at line 1733 of file LoopInterchange.cpp.

◆ interchange

loop interchange

Definition at line 1732 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"))

◆ MaxLoopNestDepth

const unsigned MaxLoopNestDepth = 10

Definition at line 77 of file LoopInterchange.cpp.

◆ MaxMemInstrCount

const unsigned MaxMemInstrCount = 100

Definition at line 74 of file LoopInterchange.cpp.

Referenced by populateDependencyMatrix().

◆ reuse

loop Interchanges loops for cache reuse

Definition at line 1733 of file LoopInterchange.cpp.