LLVM
15.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/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/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) |
static void | interChangeDependencies (CharMatrix &DepMatrix, unsigned FromIndx, unsigned ToIndx) |
static bool | isOuterMostDepPositive (CharMatrix &DepMatrix, unsigned Row, unsigned Column) |
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 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 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 | |
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 54 of file LoopInterchange.cpp.
|
static |
Definition at line 883 of file LoopInterchange.cpp.
References llvm::any_of(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), and llvm::BasicBlock::phis().
Definition at line 941 of file LoopInterchange.cpp.
References llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getSubLoops(), llvm::BasicBlock::getUniquePredecessor(), and llvm::BasicBlock::phis().
Definition at line 908 of file LoopInterchange.cpp.
References llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), llvm::BasicBlock::getUniquePredecessor(), i, and llvm::BasicBlock::phis().
|
static |
Definition at line 205 of file LoopInterchange.cpp.
References i.
Referenced by validDepInterchange().
Definition at line 737 of file LoopInterchange.cpp.
References llvm::RecurrenceDescriptor::getExactFPMathInst(), llvm::RecurrenceDescriptor::isReductionPHI(), and llvm::Value::users().
Definition at line 726 of file LoopInterchange.cpp.
References llvm::PHINode::getIncomingValue(), and llvm::PHINode::getNumIncomingValues().
Referenced by moveLCSSAPhis().
INITIALIZE_PASS_BEGIN | ( | LoopInterchangeLegacyPass | , |
"loop-interchange" | , | ||
"Interchanges loops for cache reuse" | , | ||
false | , | ||
false | |||
) |
|
static |
Definition at line 184 of file LoopInterchange.cpp.
References E, I, and std::swap().
|
static |
Definition at line 253 of file LoopInterchange.cpp.
References validDepInterchange().
|
static |
Definition at line 192 of file LoopInterchange.cpp.
References i.
Referenced by validDepInterchange().
|
static |
Definition at line 1119 of file LoopInterchange.cpp.
|
static |
Move all instructions except the terminator from FromBB right before InsertBefore.
Definition at line 1365 of file LoopInterchange.cpp.
References llvm::BasicBlock::getInstList(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getParent(), and llvm::BasicBlock::getTerminator().
Referenced by swapBBContents().
|
static |
Definition at line 1419 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 87 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::SCEVConstant::getValue(), llvm::Dependence::DVEntry::GT, I, llvm::ARM_PROC::IE, llvm::ConstantInt::isNegative(), llvm::ConstantInt::isZero(), llvm::Dependence::DVEntry::LE, LLVM_DEBUG, llvm::Dependence::DVEntry::LT, and MaxMemInstrCount.
|
static |
Definition at line 269 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 1374 of file LoopInterchange.cpp.
References llvm::BasicBlock::getTerminator(), I, llvm::map_range(), and moveBBContents().
|
static |
Definition at line 1393 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().
|
static |
Definition at line 215 of file LoopInterchange.cpp.
References containsNoDependence(), and isOuterMostDepPositive().
Referenced by isLegalToInterChangeLoops().
Definition at line 1727 of file LoopInterchange.cpp.
loop interchange |
Definition at line 1726 of file LoopInterchange.cpp.
|
static |
|
static |
Definition at line 75 of file LoopInterchange.cpp.
|
static |
Definition at line 72 of file LoopInterchange.cpp.
Referenced by populateDependencyMatrix().
Definition at line 1727 of file LoopInterchange.cpp.