19 #define DEBUG_TYPE "loop-unroll"
36 STATISTIC(NumCompletelyUnrolled,
"Number of loops completely unrolled");
37 STATISTIC(NumUnrolled,
"Number of loops unrolled (completely or otherwise)");
50 if (
PHINode *PN = dyn_cast<PHINode>(I)) {
51 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
54 PN->setIncomingBlock(i, cast<BasicBlock>(It->
second));
69 if (!OnlyPred)
return 0;
74 DEBUG(
dbgs() <<
"Merging: " << *BB <<
"into: " << *OnlyPred);
142 bool AllowRuntime,
unsigned TripMultiple,
146 DEBUG(
dbgs() <<
" Can't unroll; loop preheader-insertion failed.\n");
152 DEBUG(
dbgs() <<
" Can't unroll; loop exit-block-insertion failed.\n");
158 DEBUG(
dbgs() <<
" Can't unroll; Loop body cannot be cloned.\n");
168 " Can't unroll; loop not terminated by a conditional branch.\n");
175 " Won't unroll loop: address of header block is taken.\n");
180 DEBUG(
dbgs() <<
" Trip Count = " << TripCount <<
"\n");
181 if (TripMultiple != 1)
182 DEBUG(
dbgs() <<
" Trip Multiple = " << TripMultiple <<
"\n");
186 if (TripCount != 0 && Count > TripCount)
191 if (TripCount == 0 && Count < 2)
195 assert(TripMultiple > 0);
196 assert(TripCount == 0 || TripCount % TripMultiple == 0);
199 bool CompletelyUnroll = Count == TripCount;
204 bool RuntimeTripCount = (TripCount == 0 && Count > 0 && AllowRuntime);
218 unsigned BreakoutTrip = 0;
219 if (TripCount != 0) {
220 BreakoutTrip = TripCount % Count;
224 BreakoutTrip = TripMultiple =
228 if (CompletelyUnroll) {
230 <<
" with trip count " << TripCount <<
"!\n");
234 if (TripMultiple == 0 || BreakoutTrip != TripMultiple) {
235 DEBUG(
dbgs() <<
" with a breakout at trip " << BreakoutTrip);
236 }
else if (TripMultiple != 1) {
237 DEBUG(
dbgs() <<
" with " << TripMultiple <<
" trips per branch");
238 }
else if (RuntimeTripCount) {
239 DEBUG(
dbgs() <<
" with run-time trip count");
250 std::vector<PHINode*> OrigPHINode;
252 OrigPHINode.push_back(cast<PHINode>(
I));
255 std::vector<BasicBlock*> Headers;
256 std::vector<BasicBlock*> Latches;
257 Headers.push_back(Header);
258 Latches.push_back(LatchBlock);
270 for (
unsigned It = 1; It != Count; ++It) {
271 std::vector<BasicBlock*> NewBlocks;
281 for (
unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) {
282 PHINode *NewPHI = cast<PHINode>(VMap[OrigPHINode[i]]);
284 if (
Instruction *InValI = dyn_cast<Instruction>(InVal))
286 InVal = LastValueMap[InValI];
287 VMap[OrigPHINode[i]] = InVal;
292 LastValueMap[*BB] = New;
295 LastValueMap[VI->first] = VI->second;
308 if (It != LastValueMap.
end())
316 Headers.push_back(New);
317 if (*BB == LatchBlock)
318 Latches.push_back(New);
320 NewBlocks.push_back(New);
324 for (
unsigned i = 0; i < NewBlocks.size(); ++i)
326 E = NewBlocks[i]->
end();
I != E; ++
I)
331 for (
unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) {
333 if (CompletelyUnroll) {
337 else if (Count > 1) {
341 if (
Instruction *InValI = dyn_cast<Instruction>(InVal)) {
343 InVal = LastValueMap[InVal];
345 assert(Latches.back() == LastValueMap[LatchBlock] &&
"bad last latch");
352 for (
unsigned i = 0, e = Latches.size(); i != e; ++i) {
354 BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator());
357 unsigned j = (i + 1) % e;
359 bool NeedConditional =
true;
361 if (RuntimeTripCount && j != 0) {
362 NeedConditional =
false;
367 if (CompletelyUnroll && j == 0) {
369 NeedConditional =
false;
374 if (j != BreakoutTrip && (TripMultiple == 0 || j % TripMultiple != 0)) {
375 NeedConditional =
false;
378 if (NeedConditional) {
384 if (Dest != LoopExit) {
388 if (*SI == Headers[i])
403 for (
unsigned i = 0, e = Latches.size(); i != e; ++i) {
404 BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator());
408 std::replace(Latches.begin(), Latches.end(), Dest, Fold);
416 DT->runOnFunction(*L->
getHeader()->getParent());
420 if (SE && !CompletelyUnroll) {
426 while (!DeadInsts.
empty())
428 dyn_cast_or_null<Instruction>(&*DeadInsts.
pop_back_val()))
435 const std::vector<BasicBlock*> &NewLoopBlocks = L->
getBlocks();
436 for (std::vector<BasicBlock*>::const_iterator BB = NewLoopBlocks.begin(),
437 BBE = NewLoopBlocks.end(); BB != BBE; ++BB)
442 (*BB)->getInstList().erase(Inst);
446 (*BB)->getInstList().erase(Inst);
450 NumCompletelyUnrolled += CompletelyUnroll;
453 if (CompletelyUnroll && LPM != NULL)
void FoldSingleEntryPHINodes(BasicBlock *BB, Pass *P=0)
STATISTIC(NumCompletelyUnrolled,"Number of loops completely unrolled")
void addIncoming(Value *V, BasicBlock *BB)
uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B)
enable_if_c<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
unsigned getNumOperands() const
static BasicBlock * FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo *LI, LPPassManager *LPM)
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=0)
const_iterator begin(StringRef path)
Get begin iterator over path.
const Function * getParent() const
Return the enclosing method, or null if none.
const std::vector< BlockT * > & getBlocks() const
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=0, ValueMaterializer *Materializer=0)
BlockT * getHeader() const
LoopInfoBase< BlockT, LoopT > * LI
StringRef getName() const
BlockT * getLoopLatch() const
bool isUnconditional() const
void push_back(NodeTy *val)
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
AnalysisType * getAnalysisIfAvailable() const
T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val()
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=0)
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches, switches, etc. to it.
void setName(const Twine &Name)
Interval::succ_iterator succ_begin(Interval *I)
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
BasicBlock * getSuccessor(unsigned i) const
iterator find(const KeyT &Val)
bool UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool AllowRuntime, unsigned TripMultiple, LoopInfo *LI, LPPassManager *LPM)
Loop * getLoopFor(const BasicBlock *BB) const
void replaceAllUsesWith(Value *V)
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Interval::succ_iterator succ_end(Interval *I)
unsigned getNumSuccessors() const
BlockT * getLoopPreheader() const
LLVM Basic Block Representation.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=0)
bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, LPPassManager *LPM, SmallVectorImpl< WeakVH > &Dead)
bool contains(const LoopT *L) const
const InstListType & getInstList() const
Return the underlying instruction list container.
bool isSafeToClone() const
isSafeToClone - Return true if the loop body is safe to clone in practice.
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Value * getOperand(unsigned i) const
Value * SimplifyInstruction(Instruction *I, const DataLayout *TD=0, const TargetLibraryInfo *TLI=0, const DominatorTree *DT=0)
iterator erase(iterator where)
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
const BasicBlockListType & getBasicBlockList() const
void eraseFromParent()
Unlink 'this' from the containing function and delete it.
void deleteLoopFromQueue(Loop *L)
Delete loop from the loop queue and loop hierarchy (LoopInfo).
void splice(iterator where, iplist &L2)
void setOperand(unsigned i, Value *Val)
raw_ostream & dbgs()
dbgs - Return a circular-buffered debug stream.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getSinglePredecessor()
Return this block if it has a single predecessor block. Otherwise return a null pointer.
bool UnrollRuntimeLoopProlog(Loop *L, unsigned Count, LoopInfo *LI, LPPassManager *LPM)
void forgetLoop(const Loop *L)
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=0, ClonedCodeInfo *CodeInfo=0)
TerminatorInst * getTerminator()
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
void removeBlock(BasicBlock *BB)
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
LLVM Value Representation.
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
LoopInfoBase< BasicBlock, Loop > & getBase()
RPOIterator endRPO() const
bool empty() const
empty - Check if the string is empty.