//
// 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 file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
#define DEBUG_TYPE "condprop"
#include "llvm/Transforms/Scalar.h"
-#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Constants.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/Pass.h"
#include "llvm/Type.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Streams.h"
using namespace llvm;
namespace {
struct VISIBILITY_HIDDEN CondProp : public FunctionPass {
- static const int ID; // Pass identifcation, replacement for typeid
- CondProp() : FunctionPass((intptr_t)&ID) {}
+ static char ID; // Pass identification, replacement for typeid
+ CondProp() : FunctionPass(&ID) {}
virtual bool runOnFunction(Function &F);
private:
bool MadeChange;
+ SmallVector<BasicBlock *, 4> DeadBlocks;
void SimplifyBlock(BasicBlock *BB);
void SimplifyPredecessors(BranchInst *BI);
void SimplifyPredecessors(SwitchInst *SI);
void RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB);
};
-
- const int CondProp::ID = 0;
- RegisterPass<CondProp> X("condprop", "Conditional Propagation");
}
+
+char CondProp::ID = 0;
+static RegisterPass<CondProp> X("condprop", "Conditional Propagation");
FunctionPass *llvm::createCondPropagationPass() {
return new CondProp();
bool CondProp::runOnFunction(Function &F) {
bool EverMadeChange = false;
+ DeadBlocks.clear();
// While we are simplifying blocks, keep iterating.
do {
MadeChange = false;
- for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
- SimplifyBlock(BB);
- EverMadeChange = MadeChange;
+ for (Function::iterator BB = F.begin(), E = F.end(); BB != E;)
+ SimplifyBlock(BB++);
+ EverMadeChange = EverMadeChange || MadeChange;
} while (MadeChange);
+
+ if (EverMadeChange) {
+ while (!DeadBlocks.empty()) {
+ BasicBlock *BB = DeadBlocks.back(); DeadBlocks.pop_back();
+ DeleteDeadBlock(BB);
+ }
+ }
return EverMadeChange;
}
BB != BI->getSuccessor(0)) {
BasicBlock *Succ = BI->getSuccessor(0);
- // If Succ has any PHI nodes, they are all single-entry PHI's.
- while (PHINode *PN = dyn_cast<PHINode>(Succ->begin())) {
- assert(PN->getNumIncomingValues() == 1 &&
- "PHI doesn't match parent block");
- PN->replaceAllUsesWith(PN->getIncomingValue(0));
- PN->eraseFromParent();
- }
+ // If Succ has any PHI nodes, they are all single-entry PHI's. Eliminate
+ // them.
+ FoldSingleEntryPHINodes(Succ);
// Remove BI.
BI->eraseFromParent();
// Succ is now dead, but we cannot delete it without potentially
// invalidating iterators elsewhere. Just insert an unreachable
- // instruction in it.
+ // instruction in it and delete this block later on.
new UnreachableInst(Succ);
+ DeadBlocks.push_back(Succ);
MadeChange = true;
}
}
// one use (the branch), and is the only instruction besides the branch in the
// block.
PHINode *PN = cast<PHINode>(BI->getCondition());
+
+ if (PN->getNumIncomingValues() == 1) {
+ // Eliminate single-entry PHI nodes.
+ FoldSingleEntryPHINodes(PN->getParent());
+ return;
+ }
+
+
if (!PN->hasOneUse()) return;
BasicBlock *BB = BI->getParent();
if (ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) {
// If we have a constant, forward the edge from its current to its
// ultimate destination.
- bool PHIGone = PN->getNumIncomingValues() == 2;
RevectorBlockTo(PN->getIncomingBlock(i-1),
BI->getSuccessor(CB->isZero()));
++NumBrThread;
- // If there were two predecessors before this simplification, the PHI node
- // will be deleted. Don't iterate through it the last time.
- if (PHIGone) return;
+ // If there were two predecessors before this simplification, or if the
+ // PHI node contained all the same value except for the one we just
+ // substituted, the PHI node may be deleted. Don't iterate through it the
+ // last time.
+ if (BI->getCondition() != PN) return;
}
}
if (ConstantInt *CI = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) {
// If we have a constant, forward the edge from its current to its
// ultimate destination.
- bool PHIGone = PN->getNumIncomingValues() == 2;
unsigned DestCase = SI->findCaseValue(CI);
RevectorBlockTo(PN->getIncomingBlock(i-1),
SI->getSuccessor(DestCase));
++NumSwThread;
RemovedPreds = true;
- // If there were two predecessors before this simplification, the PHI node
- // will be deleted. Don't iterate through it the last time.
- if (PHIGone) return;
+ // If there were two predecessors before this simplification, or if the
+ // PHI node contained all the same value except for the one we just
+ // substituted, the PHI node may be deleted. Don't iterate through it the
+ // last time.
+ if (SI->getCondition() != PN) return;
}
}
// OldSucc had multiple successors. If ToBB has multiple predecessors, then
// the edge between them would be critical, which we already took care of.
// If ToBB has single operand PHI node then take care of it here.
- while (PHINode *PN = dyn_cast<PHINode>(ToBB->begin())) {
- assert(PN->getNumIncomingValues() == 1 && "Critical Edge Found!");
- PN->replaceAllUsesWith(PN->getIncomingValue(0));
- PN->eraseFromParent();
- }
+ FoldSingleEntryPHINodes(ToBB);
// Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
OldSucc->removePredecessor(FromBB);
projects / oota-llvm.git / blobdiff