-Value *GVN::performPHIConstruction(BasicBlock *BB, LoadInst* orig,
- DenseMap<BasicBlock*, Value*> &Phis,
- SmallPtrSet<BasicBlock*, 4>& visited) {
- DenseMap<BasicBlock*, Value*>::iterator DI = Phis.find(BB);
- if (DI != Phis.end())
- return DI->second;
-
- unsigned numPreds = std::distance(pred_begin(BB), pred_end(BB));
+/// GetValueForBlock - Get the value to use within the specified basic block.
+/// available values are in Phis.
+Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
+ DenseMap<BasicBlock*, Value*> &Phis,
+ bool top_level) {
+
+ // If we have already computed this value, return the previously computed val.
+ DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB);
+ if (V != Phis.end() && !top_level) return V->second;
+
+ BasicBlock* singlePred = BB->getSinglePredecessor();
+ if (singlePred) {
+ Value *ret = GetValueForBlock(singlePred, orig, Phis);
+ Phis[BB] = ret;
+ return ret;
+ }
+ // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so
+ // now, then get values to fill in the incoming values for the PHI.
+ PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle",
+ BB->begin());
+ PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB)));
+
+ if (Phis.count(BB) == 0)
+ Phis.insert(std::make_pair(BB, PN));
+
+ bool all_same = true;
+ Value* first = 0;
+
+ // Fill in the incoming values for the block.
+ for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+ Value* val = GetValueForBlock(*PI, orig, Phis);
+ if (first == 0)
+ first = val;
+ else if (all_same && first != val)
+ all_same = false;
+
+ PN->addIncoming(val, *PI);
+ }