LLVM  14.0.0git
Macros | Typedefs | Functions
LoopUnrollAndJam.cpp File Reference
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/MustExecute.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/ValueMap.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GenericDomTree.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <assert.h>
#include <memory>
#include <type_traits>
#include <vector>
Include dependency graph for LoopUnrollAndJam.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "loop-unroll-and-jam"
 

Typedefs

typedef SmallPtrSet< BasicBlock *, 4 > BasicBlockSet
 

Functions

 STATISTIC (NumUnrolledAndJammed, "Number of loops unroll and jammed")
 
 STATISTIC (NumCompletelyUnrolledAndJammed, "Number of loops unroll and jammed")
 
static bool partitionLoopBlocks (Loop &L, BasicBlockSet &ForeBlocks, BasicBlockSet &AftBlocks, DominatorTree &DT)
 
static bool partitionOuterLoopBlocks (Loop &Root, Loop &JamLoop, BasicBlockSet &JamLoopBlocks, DenseMap< Loop *, BasicBlockSet > &ForeBlocksMap, DenseMap< Loop *, BasicBlockSet > &AftBlocksMap, DominatorTree &DT)
 Partition blocks in a loop nest into blocks before and after each inner loop. More...
 
static bool partitionOuterLoopBlocks (Loop *L, Loop *SubLoop, BasicBlockSet &ForeBlocks, BasicBlockSet &SubLoopBlocks, BasicBlockSet &AftBlocks, DominatorTree *DT)
 
template<typename T >
static bool processHeaderPhiOperands (BasicBlock *Header, BasicBlock *Latch, BasicBlockSet &AftBlocks, T Visit)
 
static void moveHeaderPhiOperandsToForeBlocks (BasicBlock *Header, BasicBlock *Latch, Instruction *InsertLoc, BasicBlockSet &AftBlocks)
 
static bool getLoadsAndStores (BasicBlockSet &Blocks, SmallVector< Instruction *, 4 > &MemInstr)
 
static bool preservesForwardDependence (Instruction *Src, Instruction *Dst, unsigned UnrollLevel, unsigned JamLevel, bool Sequentialized, Dependence *D)
 
static bool preservesBackwardDependence (Instruction *Src, Instruction *Dst, unsigned UnrollLevel, unsigned JamLevel, bool Sequentialized, Dependence *D)
 
static bool checkDependency (Instruction *Src, Instruction *Dst, unsigned UnrollLevel, unsigned JamLevel, bool Sequentialized, DependenceInfo &DI)
 
static bool checkDependencies (Loop &Root, const BasicBlockSet &SubLoopBlocks, const DenseMap< Loop *, BasicBlockSet > &ForeBlocksMap, const DenseMap< Loop *, BasicBlockSet > &AftBlocksMap, DependenceInfo &DI, LoopInfo &LI)
 
static bool isEligibleLoopForm (const Loop &Root)
 
static LoopgetInnerMostLoop (Loop *L)
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-unroll-and-jam"

Definition at line 64 of file LoopUnrollAndJam.cpp.

Typedef Documentation

◆ BasicBlockSet

Definition at line 69 of file LoopUnrollAndJam.cpp.

Function Documentation

◆ checkDependencies()

static bool checkDependencies ( Loop Root,
const BasicBlockSet SubLoopBlocks,
const DenseMap< Loop *, BasicBlockSet > &  ForeBlocksMap,
const DenseMap< Loop *, BasicBlockSet > &  AftBlocksMap,
DependenceInfo DI,
LoopInfo LI 
)
static

◆ checkDependency()

static bool checkDependency ( Instruction Src,
Instruction Dst,
unsigned  UnrollLevel,
unsigned  JamLevel,
bool  Sequentialized,
DependenceInfo DI 
)
static

◆ getInnerMostLoop()

static Loop* getInnerMostLoop ( Loop L)
static

◆ getLoadsAndStores()

static bool getLoadsAndStores ( BasicBlockSet Blocks,
SmallVector< Instruction *, 4 > &  MemInstr 
)
static

Definition at line 631 of file LoopUnrollAndJam.cpp.

References BB, and I.

Referenced by checkDependencies().

◆ isEligibleLoopForm()

static bool isEligibleLoopForm ( const Loop Root)
static

◆ moveHeaderPhiOperandsToForeBlocks()

static void moveHeaderPhiOperandsToForeBlocks ( BasicBlock Header,
BasicBlock Latch,
Instruction InsertLoc,
BasicBlockSet AftBlocks 
)
static

◆ partitionLoopBlocks()

static bool partitionLoopBlocks ( Loop L,
BasicBlockSet ForeBlocks,
BasicBlockSet AftBlocks,
DominatorTree DT 
)
static

◆ partitionOuterLoopBlocks() [1/2]

static bool partitionOuterLoopBlocks ( Loop Root,
Loop JamLoop,
BasicBlockSet JamLoopBlocks,
DenseMap< Loop *, BasicBlockSet > &  ForeBlocksMap,
DenseMap< Loop *, BasicBlockSet > &  AftBlocksMap,
DominatorTree DT 
)
static

◆ partitionOuterLoopBlocks() [2/2]

static bool partitionOuterLoopBlocks ( Loop L,
Loop SubLoop,
BasicBlockSet ForeBlocks,
BasicBlockSet SubLoopBlocks,
BasicBlockSet AftBlocks,
DominatorTree DT 
)
static

◆ preservesBackwardDependence()

static bool preservesBackwardDependence ( Instruction Src,
Instruction Dst,
unsigned  UnrollLevel,
unsigned  JamLevel,
bool  Sequentialized,
Dependence D 
)
static

Definition at line 671 of file LoopUnrollAndJam.cpp.

References D, llvm::Dependence::DVEntry::GT, and llvm::Dependence::DVEntry::LT.

Referenced by checkDependency().

◆ preservesForwardDependence()

static bool preservesForwardDependence ( Instruction Src,
Instruction Dst,
unsigned  UnrollLevel,
unsigned  JamLevel,
bool  Sequentialized,
Dependence D 
)
static

Definition at line 653 of file LoopUnrollAndJam.cpp.

References D, llvm::Dependence::DVEntry::GT, and llvm::Dependence::DVEntry::LT.

Referenced by checkDependency().

◆ processHeaderPhiOperands()

template<typename T >
static bool processHeaderPhiOperands ( BasicBlock Header,
BasicBlock Latch,
BasicBlockSet AftBlocks,
T  Visit 
)
static

◆ STATISTIC() [1/2]

STATISTIC ( NumCompletelyUnrolledAndJammed  ,
"Number of loops unroll and jammed"   
)

◆ STATISTIC() [2/2]

STATISTIC ( NumUnrolledAndJammed  ,
"Number of loops unroll and jammed"   
)