LLVM  6.0.0svn
Macros | Functions | Variables
LoopInterchange.cpp File Reference
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/LoopInfo.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/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

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, SmallVector< LoopVector, 8 > &V)
 
static PHINodegetInductionVariable (Loop *L, ScalarEvolution *SE)
 
static bool containsSafePHI (BasicBlock *Block, bool isOuterLoopExitBlock)
 
static BasicBlockgetLoopLatchExitBlock (BasicBlock *LatchBlock, BasicBlock *LoopHeader)
 
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...
 
 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

◆ 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

◆ getInductionVariable()

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

Definition at line 296 of file LoopInterchange.cpp.

References llvm::AnalysisUsage::addRequired(), llvm::AnalysisUsage::addRequiredID(), llvm::BasicBlock::begin(), llvm::dbgs(), DEBUG, DEBUG_TYPE, llvm::dyn_cast(), E, llvm::OptimizationRemarkEmitter::emit(), llvm::SmallVectorBase::empty(), llvm::BasicBlock::end(), F(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::Loop::getCanonicalInductionVariable(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValueNumForOperand(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPredecessor(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::PassRegistry::getPassRegistry(), llvm::ScalarEvolution::getSCEV(), llvm::Loop::getStartLoc(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, llvm::initializeLoopInterchangePass(), llvm::MipsISD::Ins, interChangeDependencies(), llvm::SCEVAddRecExpr::isAffine(), llvm::InductionDescriptor::isInductionPHI(), llvm::Loop::isLoopInvariant(), llvm::RecurrenceDescriptor::isReductionPHI(), llvm::LCSSAID, llvm::LoopSimplifyID, llvm::none_of(), llvm::SmallVectorImpl< T >::pop_back_val(), populateDependencyMatrix(), populateWorklist(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::DominatorTreeBase< NodeT, IsPostDom >::recalculate(), runOnFunction(), llvm::SmallVectorTemplateCommon< T >::size(), llvm::TerminatorInst::successors(), std::swap(), llvm::transform(), and llvm::Value::users().

Referenced by isProfitableForVectorization().

◆ getLoopLatchExitBlock()

static BasicBlock* getLoopLatchExitBlock ( BasicBlock LatchBlock,
BasicBlock LoopHeader 
)
static

◆ INITIALIZE_PASS_BEGIN()

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

Referenced by moveBBContents().

◆ 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 getLoopLatchExitBlock().

◆ 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

◆ populateDependencyMatrix()

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

◆ populateWorklist()

static void populateWorklist ( Loop L,
SmallVector< LoopVector, 8 > &  V 
)
static

◆ 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 1424 of file LoopInterchange.cpp.

◆ interchange

loop interchange

Definition at line 1424 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 70 of file LoopInterchange.cpp.

◆ MaxMemInstrCount

const unsigned MaxMemInstrCount = 100
static

Definition at line 67 of file LoopInterchange.cpp.

Referenced by populateDependencyMatrix().

◆ reuse

loop Interchanges loops for cache reuse

Definition at line 1424 of file LoopInterchange.cpp.