#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Support/CFG.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/Statistic.h"
#include <cstdio>
#include <set>
#include <algorithm>
-#include <iostream>
using namespace llvm;
namespace {
- Statistic<> NumUnrolled("loop-unroll", "Number of loops completely unrolled");
+ Statistic NumUnrolled("loop-unroll", "Number of loops completely unrolled");
cl::opt<unsigned>
UnrollThreshold("unroll-threshold", cl::init(100), cl::Hidden,
public:
virtual bool runOnFunction(Function &F);
bool visitLoop(Loop *L);
+ BasicBlock* FoldBlockIntoPredecessor(BasicBlock* BB);
/// This transformation requires natural loop information & requires that
/// loop preheaders be inserted into the CFG...
// 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)) {
+ } else if (isa<DbgInfoIntrinsic>(I)) {
// Ignore debug instructions
} else {
++Size;
}
}
+// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it
+// only has one predecessor, and that predecessor only has one successor.
+// Returns the new combined block.
+BasicBlock* LoopUnroll::FoldBlockIntoPredecessor(BasicBlock* BB) {
+ // Merge basic blocks into their predecessor if there is only one distinct
+ // pred, and if there is only one distinct successor of the predecessor, and
+ // if there are no PHI nodes.
+ //
+ BasicBlock *OnlyPred = BB->getSinglePredecessor();
+ if (!OnlyPred) return 0;
+
+ if (OnlyPred->getTerminator()->getNumSuccessors() != 1)
+ return 0;
+
+ DOUT << "Merging: " << *BB << "into: " << *OnlyPred;
+
+ // Resolve any PHI nodes at the start of the block. They are all
+ // guaranteed to have exactly one entry if they exist, unless there are
+ // multiple duplicate (but guaranteed to be equal) entries for the
+ // incoming edges. This occurs when there are multiple edges from
+ // OnlyPred to OnlySucc.
+ //
+ while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
+ PN->replaceAllUsesWith(PN->getIncomingValue(0));
+ BB->getInstList().pop_front(); // Delete the phi node...
+ }
+
+ // Delete the unconditional branch from the predecessor...
+ OnlyPred->getInstList().pop_back();
+
+ // Move all definitions in the successor to the predecessor...
+ OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
+
+ // Make all PHI nodes that referred to BB now refer to Pred as their
+ // source...
+ BB->replaceAllUsesWith(OnlyPred);
+
+ std::string OldName = BB->getName();
+
+ // Erase basic block from the function...
+ LI->removeBlock(BB);
+ BB->eraseFromParent();
+
+ // Inherit predecessors name if it exists...
+ if (!OldName.empty() && !OnlyPred->hasName())
+ OnlyPred->setName(OldName);
+
+ return OnlyPred;
+}
+
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!
- uint64_t TripCountFull = TripCountC->getRawValue();
- if (TripCountFull != TripCountC->getRawValue() || TripCountFull == 0)
+ uint64_t TripCountFull = TripCountC->getZExtValue();
+ if (TripCountFull != TripCountC->getZExtValue() || TripCountFull == 0)
return Changed; // More than 2^32 iterations???
unsigned LoopSize = ApproximateLoopSize(L);
- DEBUG(std::cerr << "Loop Unroll: F[" << Header->getParent()->getName()
- << "] Loop %" << Header->getName() << " Loop Size = "
- << LoopSize << " Trip Count = " << TripCountFull << " - ");
+ DOUT << "Loop Unroll: F[" << Header->getParent()->getName()
+ << "] Loop %" << Header->getName() << " Loop Size = "
+ << LoopSize << " Trip Count = " << TripCountFull << " - ";
uint64_t Size = (uint64_t)LoopSize*TripCountFull;
if (Size > UnrollThreshold) {
- DEBUG(std::cerr << "TOO LARGE: " << Size << ">" << UnrollThreshold << "\n");
+ DOUT << "TOO LARGE: " << Size << ">" << UnrollThreshold << "\n";
return Changed;
}
- DEBUG(std::cerr << "UNROLLING!\n");
+ DOUT << "UNROLLING!\n";
std::vector<BasicBlock*> LoopBlocks = L->getBlocks();
RemapInstruction(I, LastValueMap);
}
- // Insert the branches that link the different iterations together
- for (unsigned i = 0; i < Latches.size()-1; ++i)
- new BranchInst(Headers[i+1], Latches[i]);
- // Finally, add an unconditional branch to the block to continue into the exit
- // block.
- new BranchInst(LoopExit, Latches[Latches.size()-1]);
// Update PHI nodes that reference the final latch block
if (TripCount > 1) {
PHINode *PN = OrigPHINode[i];
PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));
Header->getInstList().erase(PN);
- }
-
+ }
+
+ // Insert the branches that link the different iterations together
+ for (unsigned i = 0; i < Latches.size()-1; ++i) {
+ new BranchInst(Headers[i+1], Latches[i]);
+ if(BasicBlock* Fold = FoldBlockIntoPredecessor(Headers[i+1])) {
+ std::replace(Latches.begin(), Latches.end(), Headers[i+1], Fold);
+ std::replace(Headers.begin(), Headers.end(), Headers[i+1], Fold);
+ }
+ }
+
+ // Finally, add an unconditional branch to the block to continue into the exit
+ // block.
+ new BranchInst(LoopExit, Latches[Latches.size()-1]);
+ FoldBlockIntoPredecessor(LoopExit);
+
// At this point, the code is well formed. We now do a quick sweep over the
// inserted code, doing constant propagation and dead code elimination as we
// go.
const std::vector<BasicBlock*> &NewLoopBlocks = L->getBlocks();
for (std::vector<BasicBlock*>::const_iterator BB = NewLoopBlocks.begin(),
- E = NewLoopBlocks.end(); BB != E; ++BB)
+ BBE = NewLoopBlocks.end(); BB != BBE; ++BB)
for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ) {
Instruction *Inst = I++;
projects / oota-llvm.git / blobdiff