+ // 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);
+ }
+
+ if (all_same) {
+ MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
+
+ MD.removeInstruction(PN);
+ PN->replaceAllUsesWith(first);
+
+ SmallVector<BasicBlock*, 4> toRemove;
+ for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
+ E = Phis.end(); I != E; ++I)
+ if (I->second == PN)
+ toRemove.push_back(I->first);
+ for (SmallVector<BasicBlock*, 4>::iterator I = toRemove.begin(),
+ E= toRemove.end(); I != E; ++I)
+ Phis[*I] = first;
+
+ PN->eraseFromParent();
+
+ Phis[BB] = first;
+
+ return first;
+ }
+
+ phiMap[orig->getPointerOperand()].insert(PN);
+ return PN;