#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
-#include "llvm/LLVMContext.h"
#include "llvm/Type.h"
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
return true;
// Okay, it is safe to hoist the terminator.
- Instruction *NT = I1->clone(BB1->getContext());
+ Instruction *NT = I1->clone();
BIParent->getInstList().insert(BI, NT);
if (NT->getType() != Type::getVoidTy(BB1->getContext())) {
I1->replaceAllUsesWith(NT);
/// ultimate destination.
static bool FoldCondBranchOnPHI(BranchInst *BI) {
BasicBlock *BB = BI->getParent();
- LLVMContext &Context = BB->getContext();
PHINode *PN = dyn_cast<PHINode>(BI->getCondition());
// NOTE: we currently cannot transform this case if the PHI node is used
// outside of the block.
TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB);
} else {
// Clone the instruction.
- Instruction *N = BBI->clone(Context);
+ Instruction *N = BBI->clone();
if (BBI->hasName()) N->setName(BBI->getName()+".c");
// Update operands due to translation.
}
// Check for trivial simplification.
- if (Constant *C = ConstantFoldInstruction(N, Context)) {
+ if (Constant *C = ConstantFoldInstruction(N, BB->getContext())) {
TranslateMap[BBI] = C;
delete N; // Constant folded away, don't need actual inst
} else {
// Clone Cond into the predecessor basic block, and or/and the
// two conditions together.
- Instruction *New = Cond->clone(BB->getContext());
+ Instruction *New = Cond->clone();
PredBlock->getInstList().insert(PBI, New);
New->takeName(Cond);
Cond->setName(New->getName()+".old");
return true;
}
+/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
+/// nodes in this block. This doesn't try to be clever about PHI nodes
+/// which differ only in the order of the incoming values, but instcombine
+/// orders them so it usually won't matter.
+///
+static bool EliminateDuplicatePHINodes(BasicBlock *BB) {
+ bool Changed = false;
+
+ // This implementation doesn't currently consider undef operands
+ // specially. Theroetically, two phis which are identical except for
+ // one having an undef where the other doesn't could be collapsed.
+
+ // Map from PHI hash values to PHI nodes. If multiple PHIs have
+ // the same hash value, the element is the first PHI in the
+ // linked list in CollisionMap.
+ DenseMap<uintptr_t, PHINode *> HashMap;
+
+ // Maintain linked lists of PHI nodes with common hash values.
+ DenseMap<PHINode *, PHINode *> CollisionMap;
+
+ // Examine each PHI.
+ for (BasicBlock::iterator I = BB->begin();
+ PHINode *PN = dyn_cast<PHINode>(I++); ) {
+ // Compute a hash value on the operands. Instcombine will likely have sorted
+ // them, which helps expose duplicates, but we have to check all the
+ // operands to be safe in case instcombine hasn't run.
+ uintptr_t Hash = 0;
+ for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) {
+ // This hash algorithm is quite weak as hash functions go, but it seems
+ // to do a good enough job for this particular purpose, and is very quick.
+ Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I));
+ Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7));
+ }
+ // If we've never seen this hash value before, it's a unique PHI.
+ std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair =
+ HashMap.insert(std::make_pair(Hash, PN));
+ if (Pair.second) continue;
+ // Otherwise it's either a duplicate or a hash collision.
+ for (PHINode *OtherPN = Pair.first->second; ; ) {
+ if (OtherPN->isIdenticalTo(PN)) {
+ // A duplicate. Replace this PHI with its duplicate.
+ PN->replaceAllUsesWith(OtherPN);
+ PN->eraseFromParent();
+ Changed = true;
+ break;
+ }
+ // A non-duplicate hash collision.
+ DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN);
+ if (I == CollisionMap.end()) {
+ // Set this PHI to be the head of the linked list of colliding PHIs.
+ PHINode *Old = Pair.first->second;
+ Pair.first->second = PN;
+ CollisionMap[PN] = Old;
+ break;
+ }
+ // Procede to the next PHI in the list.
+ OtherPN = I->second;
+ }
+ }
+
+ return Changed;
+}
/// SimplifyCFG - This function is used to do simplification of a CFG. For
/// example, it adjusts branches to branches to eliminate the extra hop, it
// away...
Changed |= ConstantFoldTerminator(BB);
+ // Check for and eliminate duplicate PHI nodes in this block.
+ Changed |= EliminateDuplicatePHINodes(BB);
+
// If there is a trivial two-entry PHI node in this basic block, and we can
// eliminate it, do so now.
if (PHINode *PN = dyn_cast<PHINode>(BB->begin()))
<< "INTO UNCOND BRANCH PRED: " << *Pred);
Instruction *UncondBranch = Pred->getTerminator();
// Clone the return and add it to the end of the predecessor.
- Instruction *NewRet = RI->clone(BB->getContext());
+ Instruction *NewRet = RI->clone();
Pred->getInstList().push_back(NewRet);
BasicBlock::iterator BBI = RI;
} else if (isa<UnwindInst>(BB->begin())) {
// Check to see if the first instruction in this block is just an unwind.
// If so, replace any invoke instructions which use this as an exception
- // destination with call instructions, and any unconditional branch
- // predecessor with an unwind.
+ // destination with call instructions.
//
SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB));
while (!Preds.empty()) {
BasicBlock *Pred = Preds.back();
- if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) {
- if (BI->isUnconditional()) {
- Pred->getInstList().pop_back(); // nuke uncond branch
- new UnwindInst(Pred->getContext(), Pred); // Use unwind.
- Changed = true;
- }
- } else if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator()))
+ if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator()))
if (II->getUnwindDest() == BB) {
// Insert a new branch instruction before the invoke, because this
- // is now a fall through...
+ // is now a fall through.
BranchInst *BI = BranchInst::Create(II->getNormalDest(), II);
Pred->getInstList().remove(II); // Take out of symbol table
- // Insert the call now...
+ // Insert the call now.
SmallVector<Value*,8> Args(II->op_begin()+3, II->op_end());
CallInst *CI = CallInst::Create(II->getCalledValue(),
Args.begin(), Args.end(),
II->getName(), BI);
CI->setCallingConv(II->getCallingConv());
CI->setAttributes(II->getAttributes());
- // If the invoke produced a value, the Call now does instead
+ // If the invoke produced a value, the Call now does instead.
II->replaceAllUsesWith(CI);
delete II;
Changed = true;
projects / oota-llvm.git / blobdiff