LLVM  6.0.0svn
Macros | Functions | Variables
LoopUnroll.cpp File Reference
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
Include dependency graph for LoopUnroll.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "loop-unroll"
 

Functions

 STATISTIC (NumCompletelyUnrolled, "Number of loops completely unrolled")
 
 STATISTIC (NumUnrolled, "Number of loops unrolled (completely or otherwise)")
 
static void remapInstruction (Instruction *I, ValueToValueMapTy &VMap)
 Convert the instruction operands from referencing the current values into those specified by VMap. More...
 
static BasicBlockfoldBlockIntoPredecessor (BasicBlock *BB, LoopInfo *LI, ScalarEvolution *SE, SmallPtrSetImpl< Loop *> &ForgottenLoops, DominatorTree *DT)
 Folds a basic block into its predecessor if it only has one predecessor, and that predecessor only has one successor. More...
 
static bool needToInsertPhisForLCSSA (Loop *L, std::vector< BasicBlock *> Blocks, LoopInfo *LI)
 Check if unrolling created a situation where we need to insert phi nodes to preserve LCSSA form. More...
 
static bool isEpilogProfitable (Loop *L)
 The function chooses which type of unroll (epilog or prolog) is more profitabale. More...
 

Variables

static cl::opt< boolUnrollRuntimeEpilog ("unroll-runtime-epilog", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolled loops to be unrolled " "with epilog instead of prolog."))
 
static cl::opt< boolUnrollVerifyDomtree ("unroll-verify-domtree", cl::Hidden, cl::desc("Verify domtree after unrolling"), cl::init(true))
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-unroll"

Definition at line 44 of file LoopUnroll.cpp.

Referenced by llvm::UnrollLoop().

Function Documentation

◆ foldBlockIntoPredecessor()

static BasicBlock* foldBlockIntoPredecessor ( BasicBlock BB,
LoopInfo LI,
ScalarEvolution SE,
SmallPtrSetImpl< Loop *> &  ForgottenLoops,
DominatorTree DT 
)
static

Folds a basic block into its predecessor if it only has one predecessor, and that predecessor only has one successor.

The LoopInfo Analysis that is passed will be kept consistent. If folding is successful references to the containing loop must be removed from ScalarEvolution by calling ScalarEvolution::forgetLoop because SE may have references to the eliminated BB. The argument ForgottenLoops contains a set of loops that have already been forgotten to prevent redundant, expensive calls to ScalarEvolution::forgetLoop. Returns the new combined block.

Definition at line 94 of file LoopUnroll.cpp.

References llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::dbgs(), DEBUG, llvm::StringRef::empty(), llvm::BasicBlock::end(), llvm::BasicBlock::eraseFromParent(), llvm::DominatorTreeBase< NodeT, IsPostDom >::eraseNode(), llvm::FoldSingleEntryPHINodes(), llvm::ScalarEvolution::forgetLoop(), llvm::BasicBlock::getInstList(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::Value::getName(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::TerminatorInst::getNumSuccessors(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlock::getTerminator(), llvm::Value::hasName(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::iplist_impl< IntrusiveListT, TraitsT >::pop_back(), llvm::LoopInfoBase< BlockT, LoopT >::removeBlock(), llvm::Value::replaceAllUsesWith(), llvm::Value::setName(), and llvm::iplist_impl< IntrusiveListT, TraitsT >::splice().

Referenced by llvm::UnrollLoop().

◆ isEpilogProfitable()

static bool isEpilogProfitable ( Loop L)
static

The function chooses which type of unroll (epilog or prolog) is more profitabale.

Epilog unroll is more profitable when there is PHI that starts from constant. In this case epilog will leave PHI start from constant, but prolog will convert it to non-constant.

loop: PN = PHI [I, Latch], [CI, PreHeader] I = foo(PN) ...

Epilog unroll case. loop: PN = PHI [I2, Latch], [CI, PreHeader] I1 = foo(PN) I2 = foo(I1) ... Prolog unroll case. NewPN = PHI [PrologI, Prolog], [CI, PreHeader] loop: PN = PHI [I2, Latch], [NewPN, PreHeader] I1 = foo(PN) I2 = foo(I1) ...

Definition at line 244 of file LoopUnroll.cpp.

References assert(), llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), and llvm::LoopBase< BlockT, LoopT >::getLoopPreheader().

Referenced by llvm::UnrollLoop().

◆ needToInsertPhisForLCSSA()

static bool needToInsertPhisForLCSSA ( Loop L,
std::vector< BasicBlock *>  Blocks,
LoopInfo LI 
)
static

Check if unrolling created a situation where we need to insert phi nodes to preserve LCSSA form.

Parameters
Blocksis a vector of basic blocks representing unrolled loop.
Lis the outer loop. It's possible that some of the blocks are in L, and some are not. In this case, if there is a use is outside L, and definition is inside L, we need to insert a phi-node, otherwise LCSSA will be broken. The function is just a helper function for llvm::UnrollLoop that returns true if this situation occurs, indicating that LCSSA needs to be fixed.

Definition at line 166 of file LoopUnroll.cpp.

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

Referenced by llvm::UnrollLoop().

◆ remapInstruction()

static void remapInstruction ( Instruction I,
ValueToValueMapTy VMap 
)
inlinestatic

◆ STATISTIC() [1/2]

STATISTIC ( NumCompletelyUnrolled  ,
"Number of loops completely unrolled"   
)

◆ STATISTIC() [2/2]

STATISTIC ( NumUnrolled  ,
"Number of loops unrolled (completely or otherwise)"   
)

Variable Documentation

◆ UnrollRuntimeEpilog

cl::opt<bool> UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolled loops to be unrolled " "with epilog instead of prolog."))
static

Referenced by llvm::UnrollLoop().

◆ UnrollVerifyDomtree

cl::opt<bool> UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden, cl::desc("Verify domtree after unrolling"), cl::init(true))
static

Referenced by llvm::UnrollLoop().