LLVM  9.0.0svn
Macros | Functions | Variables
LoopInterchange.cpp File Reference
#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/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/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.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.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <cassert>
#include <utility>
#include <vector>
Include dependency graph for LoopInterchange.cpp:

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 LoopVector populateWorklist (Loop &L)
 
static PHINodegetInductionVariable (Loop *L, ScalarEvolution *SE)
 
static ValuefollowLCSSA (Value *SV)
 
static PHINodefindInnerReductionPhi (Loop *L, Value *V)
 
static bool containsSafePHI (BasicBlock *Block, bool isOuterLoopExitBlock)
 
static bool areLoopExitPHIsSupported (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 updateIncomingBlock (BasicBlock *CurrBlock, BasicBlock *OldPred, BasicBlock *NewPred)
 
static void updateSuccessor (BranchInst *BI, BasicBlock *OldBB, BasicBlock *NewBB, std::vector< DominatorTree::UpdateType > &DTUpdates)
 Update BI to jump to NewBB instead of OldBB. More...
 
static void moveLCSSAPhis (BasicBlock *InnerExit, BasicBlock *InnerLatch, BasicBlock *OuterLatch)
 
 INITIALIZE_PASS_BEGIN (LoopInterchange, "loop-interchange", "Interchanges loops for cache reuse", false, false) INITIALIZE_PASS_END(LoopInterchange
 

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
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-interchange"

Function Documentation

◆ areLoopExitPHIsSupported()

static bool areLoopExitPHIsSupported ( Loop OuterLoop,
Loop InnerLoop 
)
static

◆ containsNoDependence()

static bool containsNoDependence ( CharMatrix &  DepMatrix,
unsigned  Row,
unsigned  Column 
)
static

Definition at line 209 of file LoopInterchange.cpp.

Referenced by validDepInterchange().

◆ containsSafePHI()

static bool containsSafePHI ( BasicBlock Block,
bool  isOuterLoopExitBlock 
)
static

◆ findInnerReductionPhi()

static PHINode* findInnerReductionPhi ( Loop L,
Value V 
)
static

◆ followLCSSA()

static Value* followLCSSA ( Value SV)
static

◆ getInductionVariable()

static PHINode* getInductionVariable ( Loop L,
ScalarEvolution SE 
)
static

Definition at line 295 of file LoopInterchange.cpp.

References llvm::AnalysisUsage::addRequired(), llvm::any_of(), llvm::BasicBlock::begin(), llvm::dbgs(), DEBUG_TYPE, llvm::dyn_cast(), llvm::OptimizationRemarkEmitter::emit(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::Loop::getCanonicalInductionVariable(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::LoopBase< BlockT, LoopT >::getExitBlock(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValueNumForOperand(), llvm::getLoopAnalysisUsage(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPredecessor(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::LoopBase< BlockT, LoopT >::getNumBackEdges(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::PassRegistry::getPassRegistry(), llvm::ScalarEvolution::getSCEV(), llvm::Loop::getStartLoc(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, llvm::initializeLoopInterchangePass(), interChangeDependencies(), llvm::SCEVAddRecExpr::isAffine(), llvm::Loop::isLoopInvariant(), LLVM_DEBUG, llvm::Instruction::mayHaveSideEffects(), llvm::Instruction::mayReadFromMemory(), populateDependencyMatrix(), populateWorklist(), llvm::successors(), std::swap(), and llvm::transform().

Referenced by isProfitableForVectorization().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( LoopInterchange  ,
"loop-interchange ,
"Interchanges loops for cache reuse ,
false  ,
false   
)

Referenced by moveLCSSAPhis().

◆ interChangeDependencies()

static void interChangeDependencies ( CharMatrix &  DepMatrix,
unsigned  FromIndx,
unsigned  ToIndx 
)
static

Definition at line 184 of file LoopInterchange.cpp.

Referenced by getInductionVariable().

◆ isLegalToInterChangeLoops()

static bool isLegalToInterChangeLoops ( CharMatrix &  DepMatrix,
unsigned  InnerLoopId,
unsigned  OuterLoopId 
)
static

Definition at line 257 of file LoopInterchange.cpp.

References validDepInterchange().

Referenced by areLoopExitPHIsSupported().

◆ isOuterMostDepPositive()

static bool isOuterMostDepPositive ( CharMatrix &  DepMatrix,
unsigned  Row,
unsigned  Column 
)
static

Definition at line 196 of file LoopInterchange.cpp.

Referenced by validDepInterchange().

◆ isProfitableForVectorization()

static bool isProfitableForVectorization ( unsigned  InnerLoopId,
unsigned  OuterLoopId,
CharMatrix &  DepMatrix 
)
static

◆ moveBBContents()

static void moveBBContents ( BasicBlock FromBB,
Instruction InsertBefore 
)
static

◆ moveLCSSAPhis()

static void moveLCSSAPhis ( BasicBlock InnerExit,
BasicBlock InnerLatch,
BasicBlock OuterLatch 
)
static

◆ populateDependencyMatrix()

static bool populateDependencyMatrix ( CharMatrix &  DepMatrix,
unsigned  Level,
Loop L,
DependenceInfo DI 
)
static

◆ populateWorklist()

static LoopVector populateWorklist ( Loop L)
static

◆ STATISTIC()

STATISTIC ( LoopsInterchanged  ,
"Number of loops interchanged"   
)

◆ updateIncomingBlock()

static void updateIncomingBlock ( BasicBlock CurrBlock,
BasicBlock OldPred,
BasicBlock NewPred 
)
static

Definition at line 1282 of file LoopInterchange.cpp.

References llvm::BasicBlock::phis().

Referenced by moveLCSSAPhis().

◆ updateSuccessor()

static void updateSuccessor ( BranchInst BI,
BasicBlock OldBB,
BasicBlock NewBB,
std::vector< DominatorTree::UpdateType > &  DTUpdates 
)
static

Update BI to jump to NewBB instead of OldBB.

Records updates to the dominator tree in DTUpdates, if DT should be preserved.

Definition at line 1295 of file LoopInterchange.cpp.

References assert(), llvm::count_if(), llvm::cfg::Delete, llvm::BranchInst::getNumSuccessors(), llvm::Instruction::getParent(), llvm::BranchInst::getSuccessor(), llvm::cfg::Insert, llvm::BranchInst::setSuccessor(), and llvm::successors().

Referenced by moveLCSSAPhis().

◆ validDepInterchange()

static bool validDepInterchange ( CharMatrix &  DepMatrix,
unsigned  Row,
unsigned  OuterLoopId,
char  InnerDep,
char  OuterDep 
)
static

Definition at line 219 of file LoopInterchange.cpp.

References containsNoDependence(), and isOuterMostDepPositive().

Referenced by isLegalToInterChangeLoops().

Variable Documentation

◆ false

loop Interchanges loops for cache false

Definition at line 1527 of file LoopInterchange.cpp.

◆ interchange

loop interchange

Definition at line 1527 of file LoopInterchange.cpp.

◆ LoopInterchangeCostThreshold

cl::opt<int> LoopInterchangeCostThreshold("loop-interchange-threshold", cl::init(0), cl::Hidden, cl::desc("Interchange if you gain more than this number"))
static

◆ MaxLoopNestDepth

const unsigned MaxLoopNestDepth = 10
static

Definition at line 73 of file LoopInterchange.cpp.

◆ MaxMemInstrCount

const unsigned MaxMemInstrCount = 100
static

Definition at line 70 of file LoopInterchange.cpp.

Referenced by populateDependencyMatrix().

◆ reuse

loop Interchanges loops for cache reuse

Definition at line 1527 of file LoopInterchange.cpp.