//===-- LoopUnroll.cpp - Loop unroller pass -------------------------------===//
-//
+//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
+//
//===----------------------------------------------------------------------===//
//
// This pass implements a simple loop unroller. It works best when loops have
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
-#include "Support/CommandLine.h"
-#include "Support/Debug.h"
-#include "Support/Statistic.h"
-#include "Support/STLExtras.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/IntrinsicInst.h"
#include <cstdio>
+#include <set>
+#include <algorithm>
+
using namespace llvm;
namespace {
// Ignore PHI nodes in the header.
} else if (I->hasOneUse() && I->use_back() == Term) {
// Ignore instructions only used by the loop terminator.
+ } else if (DbgInfoIntrinsic *DbgI = dyn_cast<DbgInfoIntrinsic>(I)) {
+ // Ignore debug instructions
} else {
++Size;
}
return Size;
}
-// RemapInstruction - Convert the instruction operands from referencing the
+// RemapInstruction - Convert the instruction operands from referencing the
// current values into those specified by ValueMap.
//
-static inline void RemapInstruction(Instruction *I,
+static inline void RemapInstruction(Instruction *I,
std::map<const Value *, Value*> &ValueMap) {
for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) {
Value *Op = I->getOperand(op);
}
}
-static void ChangeExitBlocksFromTo(Loop::iterator I, Loop::iterator E,
- BasicBlock *Old, BasicBlock *New) {
- for (; I != E; ++I) {
- Loop *L = *I;
- if (L->hasExitBlock(Old)) {
- L->changeExitBlock(Old, New);
- ChangeExitBlocksFromTo(L->begin(), L->end(), Old, New);
- }
- }
-}
-
-
bool LoopUnroll::visitLoop(Loop *L) {
bool Changed = false;
ConstantInt *TripCountC = dyn_cast_or_null<ConstantInt>(L->getTripCount());
if (!TripCountC) return Changed; // Must have constant trip count!
- unsigned TripCount = TripCountC->getRawValue();
- if (TripCount != TripCountC->getRawValue())
+ uint64_t TripCountFull = TripCountC->getRawValue();
+ if (TripCountFull != TripCountC->getRawValue() || TripCountFull == 0)
return Changed; // More than 2^32 iterations???
unsigned LoopSize = ApproximateLoopSize(L);
DEBUG(std::cerr << "Loop Unroll: F[" << BB->getParent()->getName()
<< "] Loop %" << BB->getName() << " Loop Size = " << LoopSize
- << " Trip Count = " << TripCount << " - ");
- if (LoopSize*TripCount > UnrollThreshold) {
- DEBUG(std::cerr << "TOO LARGE: " << LoopSize*TripCount << ">"
- << UnrollThreshold << "\n");
+ << " Trip Count = " << TripCountFull << " - ");
+ uint64_t Size = (uint64_t)LoopSize*TripCountFull;
+ if (Size > UnrollThreshold) {
+ DEBUG(std::cerr << "TOO LARGE: " << Size << ">" << UnrollThreshold << "\n");
return Changed;
}
DEBUG(std::cerr << "UNROLLING!\n");
-
- assert(L->getExitBlocks().size() == 1 && "Must have exactly one exit block!");
- BasicBlock *LoopExit = L->getExitBlocks()[0];
+
+ unsigned TripCount = (unsigned)TripCountFull;
+
+ BasicBlock *LoopExit = BI->getSuccessor(L->contains(BI->getSuccessor(0)));
// Create a new basic block to temporarily hold all of the cloned code.
BasicBlock *NewBlock = new BasicBlock();
// PHI nodes. Insert associations now.
std::map<const Value*, Value*> LastValueMap;
std::vector<PHINode*> OrigPHINode;
- for (BasicBlock::iterator I = BB->begin();
- PHINode *PN = dyn_cast<PHINode>(I); ++I) {
+ for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) {
+ PHINode *PN = cast<PHINode>(I);
OrigPHINode.push_back(PN);
if (Instruction *I =dyn_cast<Instruction>(PN->getIncomingValueForBlock(BB)))
if (I->getParent() == BB)
PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));
BB->getInstList().erase(PN);
}
-
+
// Finally, add an unconditional branch to the block to continue into the exit
// block.
new BranchInst(LoopExit, BB);
// go.
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
Instruction *Inst = I++;
-
+
if (isInstructionTriviallyDead(Inst))
BB->getInstList().erase(Inst);
else if (Constant *C = ConstantFoldInstruction(Inst)) {
// Preheader.
Preheader->replaceAllUsesWith(LoopExit);
+ Function *F = LoopExit->getParent();
+ if (Parent) {
+ // Otherwise, if this is a sub-loop, and the preheader was the loop header
+ // of the parent loop, move the exit block to be the new parent loop header.
+ if (Parent->getHeader() == Preheader) {
+ assert(Parent->contains(LoopExit) &&
+ "Exit block isn't contained in parent?");
+ Parent->moveToHeader(LoopExit);
+ }
+ } else {
+ // If the preheader was the entry block of this function, move the exit
+ // block to be the new entry of the function.
+ if (Preheader == &F->front())
+ F->getBasicBlockList().splice(F->begin(),
+ F->getBasicBlockList(), LoopExit);
+ }
+
// Remove BB and LoopExit from our analyses.
LI->removeBlock(Preheader);
LI->removeBlock(BB);
- // If any loops used Preheader as an exit block, update them to use LoopExit.
- if (Parent)
- ChangeExitBlocksFromTo(Parent->begin(), Parent->end(),
- Preheader, LoopExit);
- else
- ChangeExitBlocksFromTo(LI->begin(), LI->end(),
- Preheader, LoopExit);
-
- // If the preheader was the entry block of this function, move the exit block
- // to be the new entry of the loop.
- Function *F = LoopExit->getParent();
- if (Preheader == &F->front())
- F->getBasicBlockList().splice(F->begin(), F->getBasicBlockList(), LoopExit);
-
// Actually delete the blocks now.
F->getBasicBlockList().erase(Preheader);
F->getBasicBlockList().erase(BB);
projects / oota-llvm.git / blobdiff