LLVM 20.0.0git
|
#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/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/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 | populateDependencyMatrix (CharMatrix &DepMatrix, unsigned Level, Loop *L, DependenceInfo *DI, ScalarEvolution *SE) |
static void | interChangeDependencies (CharMatrix &DepMatrix, unsigned FromIndx, unsigned ToIndx) |
static bool | isLexicographicallyPositive (std::vector< char > &DV) |
static bool | isLegalToInterChangeLoops (CharMatrix &DepMatrix, unsigned InnerLoopId, unsigned OuterLoopId) |
static void | populateWorklist (Loop &L, LoopVector &LoopList) |
static Value * | followLCSSA (Value *SV) |
static PHINode * | findInnerReductionPhi (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 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) |
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 const unsigned | MaxMemInstrCount = 100 |
static const unsigned | MaxLoopNestDepth = 10 |
#define DEBUG_TYPE "loop-interchange" |
Definition at line 52 of file LoopInterchange.cpp.
|
static |
Definition at line 859 of file LoopInterchange.cpp.
References llvm::any_of(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), PHI, llvm::BasicBlock::phis(), and llvm::Reductions.
Definition at line 917 of file LoopInterchange.cpp.
References 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().
Definition at line 884 of file LoopInterchange.cpp.
References 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().
Definition at line 706 of file LoopInterchange.cpp.
References llvm::RecurrenceDescriptor::getExactFPMathInst(), llvm::RecurrenceDescriptor::isReductionPHI(), and PHI.
Definition at line 695 of file LoopInterchange.cpp.
References followLCSSA(), and PHI.
Referenced by followLCSSA(), and moveLCSSAPhis().
|
static |
Definition at line 175 of file LoopInterchange.cpp.
References I, and std::swap().
|
static |
Definition at line 196 of file LoopInterchange.cpp.
References isLexicographicallyPositive(), and std::swap().
Definition at line 185 of file LoopInterchange.cpp.
Referenced by isLegalToInterChangeLoops().
|
static |
Move all instructions except the terminator from FromBB right before InsertBefore.
Definition at line 1391 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().
|
static |
Definition at line 1444 of file LoopInterchange.cpp.
References llvm::PHINode::addIncoming(), llvm::all_of(), assert(), followLCSSA(), llvm::BasicBlock::getFirstNonPHI(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::BasicBlock::getParent(), I, llvm::Instruction::insertBefore(), llvm::make_early_inc_range(), P, llvm::BasicBlock::phis(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::BasicBlock::replacePhiUsesWith(), llvm::PHINode::setIncomingBlock(), and llvm::PHINode::setIncomingValue().
|
static |
Definition at line 85 of file LoopInterchange.cpp.
References assert(), D, llvm::dbgs(), llvm::DependenceInfo::depends(), llvm::Dependence::DVEntry::EQ, llvm::Dependence::DVEntry::GE, llvm::Dependence::DVEntry::GT, I, II, llvm::Dependence::DVEntry::LE, LLVM_DEBUG, llvm::Dependence::DVEntry::LT, MaxMemInstrCount, and llvm::SmallVectorTemplateBase< T, bool >::push_back().
|
static |
Definition at line 215 of file LoopInterchange.cpp.
References assert(), llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), and LLVM_DEBUG.
STATISTIC | ( | LoopsInterchanged | , |
"Number of loops interchanged" | |||
) |
|
static |
Swap instructions between BB1
and BB2
but keep terminators intact.
Definition at line 1399 of file LoopInterchange.cpp.
References llvm::BasicBlock::getTerminator(), I, llvm::map_range(), and moveBBContents().
|
static |
Definition at line 1418 of file LoopInterchange.cpp.
References assert(), llvm::count_if(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::User::operands(), and llvm::successors().
|
static |
Definition at line 73 of file LoopInterchange.cpp.
Definition at line 70 of file LoopInterchange.cpp.
Referenced by populateDependencyMatrix().