LLVM
17.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/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>
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. 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 | |
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 |
loop | interchange |
loop Interchanges loops for cache | reuse |
loop Interchanges loops for cache | false |
#define DEBUG_TYPE "loop-interchange" |
Definition at line 56 of file LoopInterchange.cpp.
|
static |
Definition at line 865 of file LoopInterchange.cpp.
References llvm::any_of(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), PHI, and llvm::BasicBlock::phis().
Definition at line 923 of file LoopInterchange.cpp.
References llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), llvm::BasicBlock::getUniquePredecessor(), PHI, and llvm::BasicBlock::phis().
Definition at line 890 of file LoopInterchange.cpp.
References llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), llvm::BasicBlock::getUniquePredecessor(), i, PHI, and llvm::BasicBlock::phis().
Definition at line 711 of file LoopInterchange.cpp.
References llvm::RecurrenceDescriptor::getExactFPMathInst(), llvm::RecurrenceDescriptor::isReductionPHI(), PHI, and llvm::Value::users().
INITIALIZE_PASS_BEGIN | ( | LoopInterchangeLegacyPass | , |
"loop-interchange" | , | ||
"Interchanges loops for cache reuse" | , | ||
false | , | ||
false | |||
) |
|
static |
Definition at line 179 of file LoopInterchange.cpp.
References E, I, and std::swap().
|
static |
Definition at line 201 of file LoopInterchange.cpp.
References isLexicographicallyPositive(), and std::swap().
|
static |
Definition at line 189 of file LoopInterchange.cpp.
Referenced by isLegalToInterChangeLoops().
|
static |
Move all instructions except the terminator from FromBB right before InsertBefore.
Definition at line 1398 of file LoopInterchange.cpp.
References llvm::BasicBlock::begin(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), and llvm::BasicBlock::splice().
Referenced by swapBBContents().
|
static |
Definition at line 1451 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::BasicBlock::replacePhiUsesWith(), llvm::PHINode::setIncomingBlock(), and llvm::PHINode::setIncomingValue().
|
static |
Definition at line 89 of file LoopInterchange.cpp.
References assert(), BB, llvm::LoopBase< BlockT, LoopT >::blocks(), D, llvm::dbgs(), llvm::DependenceInfo::depends(), llvm::Dependence::DVEntry::EQ, llvm::Dependence::DVEntry::GE, llvm::Dependence::DVEntry::GT, I, llvm::ARM_PROC::IE, llvm::Dependence::DVEntry::LE, LLVM_DEBUG, llvm::Dependence::DVEntry::LT, and MaxMemInstrCount.
|
static |
Definition at line 220 of file LoopInterchange.cpp.
References assert(), llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), and LLVM_DEBUG.
|
static |
Swap instructions between BB1
and BB2
but keep terminators intact.
Definition at line 1406 of file LoopInterchange.cpp.
References llvm::BasicBlock::getTerminator(), I, llvm::map_range(), and moveBBContents().
|
static |
Definition at line 1425 of file LoopInterchange.cpp.
References assert(), BB, llvm::count_if(), llvm::cfg::Delete, llvm::Instruction::getParent(), llvm::cfg::Insert, llvm::User::operands(), and llvm::successors().
Definition at line 1759 of file LoopInterchange.cpp.
loop interchange |
Definition at line 1758 of file LoopInterchange.cpp.
|
static |
|
static |
Definition at line 77 of file LoopInterchange.cpp.
|
static |
Definition at line 74 of file LoopInterchange.cpp.
Referenced by populateDependencyMatrix().
Definition at line 1759 of file LoopInterchange.cpp.