//===-- 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 {
Statistic<> NumUnrolled("loop-unroll", "Number of loops completely unrolled");
cl::opt<unsigned>
- UnrollThreshold("unroll-threshold", cl::init(250), cl::Hidden,
+ UnrollThreshold("unroll-threshold", cl::init(100), cl::Hidden,
cl::desc("The cut-off point for loop unrolling"));
class LoopUnroll : public FunctionPass {
// 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)
}
// If there was more than one iteration, replace any uses of values computed
- // in the loop with values computed during last iteration of the loop.
- if (TripCount != 1)
- for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
- std::vector<User*> Users(I->use_begin(), I->use_end());
- for (unsigned i = 0, e = Users.size(); i != e; ++i) {
- Instruction *UI = cast<Instruction>(Users[i]);
- if (UI->getParent() != BB && UI->getParent() != NewBlock)
- UI->replaceUsesOfWith(I, LastValueMap[I]);
- }
+ // in the loop with values computed during the last iteration of the loop.
+ if (TripCount != 1) {
+ std::set<User*> Users;
+ for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
+ Users.insert(I->use_begin(), I->use_end());
+
+ // We don't want to reprocess entries with PHI nodes in them. For this
+ // reason, we look at each operand of each user exactly once, performing the
+ // stubstitution exactly once.
+ for (std::set<User*>::iterator UI = Users.begin(), E = Users.end(); UI != E;
+ ++UI) {
+ Instruction *I = cast<Instruction>(*UI);
+ if (I->getParent() != BB && I->getParent() != NewBlock)
+ RemapInstruction(I, LastValueMap);
}
+ }
// Now that we cloned the block as many times as we needed, stitch the new
// code into the original block and delete the temporary block.
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);
-
-
// Actually delete the blocks now.
- LoopExit->getParent()->getBasicBlockList().erase(Preheader);
- LoopExit->getParent()->getBasicBlockList().erase(BB);
+ F->getBasicBlockList().erase(Preheader);
+ F->getBasicBlockList().erase(BB);
++NumUnrolled;
return true;