LLVM  8.0.0svn
Macros | Functions | Variables
LICM.cpp File Reference
#include "llvm/Transforms/Scalar/LICM.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/PredIteratorCache.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.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 "llvm/Transforms/Utils/SSAUpdater.h"
#include <algorithm>
#include <utility>
Include dependency graph for LICM.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "licm"
 

Functions

 STATISTIC (NumSunk, "Number of instructions sunk out of loop")
 
 STATISTIC (NumHoisted, "Number of instructions hoisted out of loop")
 
 STATISTIC (NumMovedLoads, "Number of load insts hoisted or sunk")
 
 STATISTIC (NumMovedCalls, "Number of call insts hoisted or sunk")
 
 STATISTIC (NumPromoted, "Number of memory locations promoted to registers")
 
static bool inSubLoop (BasicBlock *BB, Loop *CurLoop, LoopInfo *LI)
 Little predicate that returns true if the specified basic block is in a subloop of the current one, not the current one itself. More...
 
static bool isNotUsedOrFreeInLoop (const Instruction &I, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, TargetTransformInfo *TTI, bool &FreeInLoop)
 Return true if the only users of this instruction are outside of the loop. More...
 
static void hoist (Instruction &I, const DominatorTree *DT, const Loop *CurLoop, LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE)
 When an instruction is found to only use loop invariant operands that is safe to hoist, this instruction is called to do the dirty work. More...
 
static bool sink (Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE, bool FreeInLoop)
 When an instruction is found to only be used outside of the loop, this function moves it to the exit blocks and patches up SSA form as needed. More...
 
static bool isSafeToExecuteUnconditionally (Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE, const Instruction *CtxI)
 Only sink or hoist an instruction if it is not a trapping instruction, or if the instruction is known not to trap when moved to the preheader. More...
 
static bool isInvalidatedByLoop (const MemoryLocation &MemLoc, AliasSetTracker *CurAST)
 Return true if the body of this loop may store into the memory location pointed to by V. More...
 
static InstructionCloneInstructionInExitBlock (Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI, const LoopSafetyInfo *SafetyInfo)
 
 INITIALIZE_PASS_BEGIN (LegacyLICMPass, "licm", "Loop Invariant Code Motion", false, false) INITIALIZE_PASS_END(LegacyLICMPass
 
static bool isLoadInvariantInLoop (LoadInst *LI, DominatorTree *DT, Loop *CurLoop)
 
static bool isTriviallyReplaceablePHI (const PHINode &PN, const Instruction &I)
 Returns true if a PHINode is a trivially replaceable with an Instruction. More...
 
static bool isFreeInLoop (const Instruction &I, const Loop *CurLoop, const TargetTransformInfo *TTI)
 Return true if the instruction is free in the loop. More...
 
static InstructionsinkThroughTriviallyReplaceablePHI (PHINode *TPN, Instruction *I, LoopInfo *LI, SmallDenseMap< BasicBlock *, Instruction *, 32 > &SunkCopies, const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop)
 
static bool canSplitPredecessors (PHINode *PN, LoopSafetyInfo *SafetyInfo)
 
static void splitPredecessorsOfLoopExit (PHINode *PN, DominatorTree *DT, LoopInfo *LI, const Loop *CurLoop, LoopSafetyInfo *SafetyInfo)
 

Variables

static cl::opt< boolDisablePromotion ("disable-licm-promotion", cl::Hidden, cl::init(false), cl::desc("Disable memory promotion in LICM pass"))
 Memory promotion is enabled by default. More...
 
static cl::opt< uint32_tMaxNumUsesTraversed ("licm-max-num-uses-traversed", cl::Hidden, cl::init(8), cl::desc("Max num uses visited for identifying load " "invariance in loop using invariant start (default = 8)"))
 
 licm
 
Loop Invariant Code Motion
 
Loop Invariant Code false
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "licm"

Function Documentation

◆ canSplitPredecessors()

static bool canSplitPredecessors ( PHINode PN,
LoopSafetyInfo SafetyInfo 
)
static

◆ CloneInstructionInExitBlock()

static Instruction * CloneInstructionInExitBlock ( Instruction I,
BasicBlock ExitBlock,
PHINode PN,
const LoopInfo LI,
const LoopSafetyInfo SafetyInfo 
)
static

◆ hoist()

static void hoist ( Instruction I,
const DominatorTree DT,
const Loop CurLoop,
LoopSafetyInfo SafetyInfo,
OptimizationRemarkEmitter ORE 
)
static

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( LegacyLICMPass  ,
"licm"  ,
"Loop Invariant Code Motion ,
false  ,
false   
)

Referenced by llvm::LICMPass::run().

◆ inSubLoop()

static bool inSubLoop ( BasicBlock BB,
Loop CurLoop,
LoopInfo LI 
)
static

Little predicate that returns true if the specified basic block is in a subloop of the current one, not the current one itself.

Definition at line 1584 of file LICM.cpp.

References assert(), llvm::LoopBase< BlockT, LoopT >::contains(), and llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor().

Referenced by llvm::hoistRegion(), and llvm::sinkRegion().

◆ isFreeInLoop()

static bool isFreeInLoop ( const Instruction I,
const Loop CurLoop,
const TargetTransformInfo TTI 
)
static

Return true if the instruction is free in the loop.

Definition at line 728 of file LICM.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), GEP, llvm::Instruction::getParent(), llvm::TargetTransformInfo::getUserCost(), and llvm::TargetTransformInfo::TCC_Free.

Referenced by isNotUsedOrFreeInLoop().

◆ isInvalidatedByLoop()

static bool isInvalidatedByLoop ( const MemoryLocation MemLoc,
AliasSetTracker CurAST 
)
static

Return true if the body of this loop may store into the memory location pointed to by V.

Definition at line 1575 of file LICM.cpp.

References llvm::AliasSetTracker::getAliasSetFor(), and llvm::AliasSet::isMod().

Referenced by llvm::canSinkOrHoistInst().

◆ isLoadInvariantInLoop()

static bool isLoadInvariantInLoop ( LoadInst LI,
DominatorTree DT,
Loop CurLoop 
)
static

◆ isNotUsedOrFreeInLoop()

static bool isNotUsedOrFreeInLoop ( const Instruction I,
const Loop CurLoop,
const LoopSafetyInfo SafetyInfo,
TargetTransformInfo TTI,
bool FreeInLoop 
)
static

Return true if the only users of this instruction are outside of the loop.

If this is true, we can sink the instruction to the exit blocks of the loop.

We also return true if the instruction could be folded away in lowering. (e.g., a GEP can be folded into a load as an addressing mode in the loop).

Definition at line 756 of file LICM.cpp.

References llvm::LoopSafetyInfo::BlockColors, llvm::LoopBase< BlockT, LoopT >::contains(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), isFreeInLoop(), and llvm::Value::users().

Referenced by llvm::sinkRegion().

◆ isSafeToExecuteUnconditionally()

static bool isSafeToExecuteUnconditionally ( Instruction Inst,
const DominatorTree DT,
const Loop CurLoop,
const LoopSafetyInfo SafetyInfo,
OptimizationRemarkEmitter ORE,
const Instruction CtxI 
)
static

◆ isTriviallyReplaceablePHI()

static bool isTriviallyReplaceablePHI ( const PHINode PN,
const Instruction I 
)
static

Returns true if a PHINode is a trivially replaceable with an Instruction.

This is true when all incoming values are that instruction. This pattern occurs most often with LCSSA PHI nodes.

Definition at line 719 of file LICM.cpp.

References llvm::PHINode::incoming_values().

Referenced by sink(), and sinkThroughTriviallyReplaceablePHI().

◆ sink()

static bool sink ( Instruction I,
LoopInfo LI,
DominatorTree DT,
const Loop CurLoop,
LoopSafetyInfo SafetyInfo,
OptimizationRemarkEmitter ORE,
bool  FreeInLoop 
)
static

◆ sinkThroughTriviallyReplaceablePHI()

static Instruction* sinkThroughTriviallyReplaceablePHI ( PHINode TPN,
Instruction I,
LoopInfo LI,
SmallDenseMap< BasicBlock *, Instruction *, 32 > &  SunkCopies,
const LoopSafetyInfo SafetyInfo,
const Loop CurLoop 
)
static

◆ splitPredecessorsOfLoopExit()

static void splitPredecessorsOfLoopExit ( PHINode PN,
DominatorTree DT,
LoopInfo LI,
const Loop CurLoop,
LoopSafetyInfo SafetyInfo 
)
static

◆ STATISTIC() [1/5]

STATISTIC ( NumSunk  ,
"Number of instructions sunk out of loop"   
)

◆ STATISTIC() [2/5]

STATISTIC ( NumHoisted  ,
"Number of instructions hoisted out of loop"   
)

◆ STATISTIC() [3/5]

STATISTIC ( NumMovedLoads  ,
"Number of load insts hoisted or sunk"   
)

◆ STATISTIC() [4/5]

STATISTIC ( NumMovedCalls  ,
"Number of call insts hoisted or sunk"   
)

◆ STATISTIC() [5/5]

STATISTIC ( NumPromoted  ,
"Number of memory locations promoted to registers"   
)

Variable Documentation

◆ DisablePromotion

cl::opt<bool> DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false), cl::desc("Disable memory promotion in LICM pass"))
static

Memory promotion is enabled by default.

Referenced by llvm::createLICMPass().

◆ false

Loop Invariant Code false

Definition at line 237 of file LICM.cpp.

◆ licm

licm

Definition at line 237 of file LICM.cpp.

◆ MaxNumUsesTraversed

cl::opt<uint32_t> MaxNumUsesTraversed("licm-max-num-uses-traversed", cl::Hidden, cl::init(8), cl::desc("Max num uses visited for identifying load " "invariance in loop using invariant start (default = 8)"))
static

Referenced by isLoadInvariantInLoop().

◆ Motion

Loop Invariant Code Motion

Definition at line 237 of file LICM.cpp.