LLVM
15.0.0git
|
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.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>
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 Loop * | getInnerMostLoop (Loop *L) |
Definition at line 63 of file LoopUnrollAndJam.cpp.
typedef SmallPtrSet<BasicBlock *, 4> BasicBlockSet |
Definition at line 68 of file LoopUnrollAndJam.cpp.
|
static |
Definition at line 760 of file LoopUnrollAndJam.cpp.
References llvm::SmallVectorImpl< T >::append(), checkDependency(), llvm::SmallVectorImpl< T >::clear(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find(), getLoadsAndStores(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopsInPreorder(), I, llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup(), and llvm::min().
Referenced by llvm::isSafeToUnrollAndJam().
|
static |
Definition at line 696 of file LoopUnrollAndJam.cpp.
References assert(), D, llvm::dbgs(), llvm::DependenceInfo::depends(), llvm::Dependence::DVEntry::EQ, llvm::Dependence::DVEntry::GT, LLVM_DEBUG, llvm::Dependence::DVEntry::LT, preservesBackwardDependence(), and preservesForwardDependence().
Referenced by checkDependencies().
Definition at line 860 of file LoopUnrollAndJam.cpp.
References llvm::LoopBase< BlockT, LoopT >::getSubLoops().
Referenced by llvm::isSafeToUnrollAndJam().
|
static |
Definition at line 630 of file LoopUnrollAndJam.cpp.
Referenced by checkDependencies().
Definition at line 810 of file LoopUnrollAndJam.cpp.
References llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::getExitBlock(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), llvm::BasicBlock::hasAddressTaken(), llvm::Loop::isLoopSimplifyForm(), llvm::Loop::isRotatedForm(), and LLVM_DEBUG.
Referenced by llvm::isSafeToUnrollAndJam().
|
static |
Definition at line 167 of file LoopUnrollAndJam.cpp.
References llvm::SmallPtrSetImpl< PtrType >::count(), llvm::Instruction::getParent(), I, processHeaderPhiOperands(), and llvm::reverse().
Referenced by llvm::UnrollAndJamLoop().
|
static |
Definition at line 72 of file LoopUnrollAndJam.cpp.
References BB, llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::DominatorTree::dominates(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), llvm::SmallPtrSetImpl< PtrType >::insert(), and llvm::successors().
Referenced by partitionOuterLoopBlocks().
|
static |
Partition blocks in a loop nest into blocks before and after each inner loop.
Definition at line 103 of file LoopUnrollAndJam.cpp.
References llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::LoopBase< BlockT, LoopT >::block_end(), llvm::LoopBase< BlockT, LoopT >::getLoopsInPreorder(), llvm::SmallPtrSetImpl< PtrType >::insert(), and partitionLoopBlocks().
Referenced by llvm::isSafeToUnrollAndJam(), and llvm::UnrollAndJamLoop().
|
static |
Definition at line 122 of file LoopUnrollAndJam.cpp.
References llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::LoopBase< BlockT, LoopT >::block_end(), llvm::SmallPtrSetImpl< PtrType >::insert(), and partitionLoopBlocks().
|
static |
Definition at line 670 of file LoopUnrollAndJam.cpp.
References D, llvm::Dependence::DVEntry::GT, and llvm::Dependence::DVEntry::LT.
Referenced by checkDependency().
|
static |
Definition at line 652 of file LoopUnrollAndJam.cpp.
References D, llvm::Dependence::DVEntry::GT, and llvm::Dependence::DVEntry::LT.
Referenced by checkDependency().
|
static |
Definition at line 140 of file LoopUnrollAndJam.cpp.
References llvm::SmallPtrSetImpl< PtrType >::count(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::BasicBlock::phis(), and llvm::SmallVectorImpl< T >::pop_back_val().
Referenced by llvm::isSafeToUnrollAndJam(), and moveHeaderPhiOperandsToForeBlocks().