+static Value *getReplacementOrValue(Value *V, RegionInfo &RI) {
+ if (const ValueInfo *VI = RI.requestValueInfo(V))
+ if (Value *Repl = VI->getReplacement())
+ return Repl;
+ return V;
+}
+
+/// ForwardSuccessorTo - We have found that we can forward successor # 'SuccNo'
+/// of Terminator 'TI' to the 'Dest' BasicBlock. This method performs the
+/// mechanics of updating SSA information and revectoring the branch.
+///
+void CEE::ForwardSuccessorTo(TerminatorInst *TI, unsigned SuccNo,
+ BasicBlock *Dest, RegionInfo &RI) {
+ // If there are any PHI nodes in the Dest BB, we must duplicate the entry
+ // in the PHI node for the old successor to now include an entry from the
+ // current basic block.
+ //
+ BasicBlock *OldSucc = TI->getSuccessor(SuccNo);
+ BasicBlock *BB = TI->getParent();
+
+ DEBUG(std::cerr << "Forwarding branch in basic block %" << BB->getName()
+ << " from block %" << OldSucc->getName() << " to block %"
+ << Dest->getName() << "\n");
+
+ DEBUG(std::cerr << "Before forwarding: " << *BB->getParent());
+
+ // Because we know that there cannot be critical edges in the flow graph, and
+ // that OldSucc has multiple outgoing edges, this means that Dest cannot have
+ // multiple incoming edges.
+ //
+#ifndef NDEBUG
+ pred_iterator DPI = pred_begin(Dest); ++DPI;
+ assert(DPI == pred_end(Dest) && "Critical edge found!!");
+#endif
+
+ // Loop over any PHI nodes in the destination, eliminating them, because they
+ // may only have one input.
+ //
+ while (PHINode *PN = dyn_cast<PHINode>(&Dest->front())) {
+ assert(PN->getNumIncomingValues() == 1 && "Crit edge found!");
+ // Eliminate the PHI node
+ PN->replaceAllUsesWith(PN->getIncomingValue(0));
+ Dest->getInstList().erase(PN);
+ }
+
+ // If there are values defined in the "OldSucc" basic block, we need to insert
+ // PHI nodes in the regions we are dealing with to emulate them. This can
+ // insert dead phi nodes, but it is more trouble to see if they are used than
+ // to just blindly insert them.
+ //
+ if (DS->dominates(OldSucc, Dest)) {
+ // RegionExitBlocks - Find all of the blocks that are not dominated by Dest,
+ // but have predecessors that are. Additionally, prune down the set to only
+ // include blocks that are dominated by OldSucc as well.
+ //
+ std::vector<BasicBlock*> RegionExitBlocks;
+ CalculateRegionExitBlocks(Dest, OldSucc, RegionExitBlocks);
+
+ for (BasicBlock::iterator I = OldSucc->begin(), E = OldSucc->end();
+ I != E; ++I)
+ if (I->getType() != Type::VoidTy) {
+ // Create and insert the PHI node into the top of Dest.
+ PHINode *NewPN = new PHINode(I->getType(), I->getName()+".fw_merge",
+ Dest->begin());
+ // There is definitely an edge from OldSucc... add the edge now
+ NewPN->addIncoming(I, OldSucc);
+
+ // There is also an edge from BB now, add the edge with the calculated
+ // value from the RI.
+ NewPN->addIncoming(getReplacementOrValue(I, RI), BB);
+
+ // Make everything in the Dest region use the new PHI node now...
+ ReplaceUsesOfValueInRegion(I, NewPN, Dest);
+
+ // Make sure that exits out of the region dominated by NewPN get PHI
+ // nodes that merge the values as appropriate.
+ InsertRegionExitMerges(NewPN, I, RegionExitBlocks);
+ }
+ }
+
+ // If there were PHI nodes in OldSucc, we need to remove the entry for this
+ // edge from the PHI node, and we need to replace any references to the PHI
+ // node with a new value.
+ //
+ for (BasicBlock::iterator I = OldSucc->begin();
+ PHINode *PN = dyn_cast<PHINode>(&*I); ) {
+
+ // Get the value flowing across the old edge and remove the PHI node entry
+ // for this edge: we are about to remove the edge! Don't remove the PHI
+ // node yet though if this is the last edge into it.
+ Value *EdgeValue = PN->removeIncomingValue(BB, false);
+
+ // Make sure that anything that used to use PN now refers to EdgeValue
+ ReplaceUsesOfValueInRegion(PN, EdgeValue, Dest);
+
+ // If there is only one value left coming into the PHI node, replace the PHI
+ // node itself with the one incoming value left.
+ //
+ if (PN->getNumIncomingValues() == 1) {
+ assert(PN->getNumIncomingValues() == 1);
+ PN->replaceAllUsesWith(PN->getIncomingValue(0));
+ PN->getParent()->getInstList().erase(PN);
+ I = OldSucc->begin();
+ } else if (PN->getNumIncomingValues() == 0) { // Nuke the PHI
+ // If we removed the last incoming value to this PHI, nuke the PHI node
+ // now.
+ PN->replaceAllUsesWith(Constant::getNullValue(PN->getType()));
+ PN->getParent()->getInstList().erase(PN);
+ I = OldSucc->begin();
+ } else {
+ ++I; // Otherwise, move on to the next PHI node
+ }
+ }
+
+ // Actually revector the branch now...
+ TI->setSuccessor(SuccNo, Dest);
+
+ // If we just introduced a critical edge in the flow graph, make sure to break
+ // it right away...
+ if (isCriticalEdge(TI, SuccNo))
+ SplitCriticalEdge(TI, SuccNo, this);
+
+ // Make sure that we don't introduce critical edges from oldsucc now!
+ for (unsigned i = 0, e = OldSucc->getTerminator()->getNumSuccessors();
+ i != e; ++i)
+ if (isCriticalEdge(OldSucc->getTerminator(), i))
+ SplitCriticalEdge(OldSucc->getTerminator(), i, this);
+
+ // Since we invalidated the CFG, recalculate the dominator set so that it is
+ // useful for later processing!
+ // FIXME: This is much worse than it really should be!
+ //DS->recalculate();
+
+ DEBUG(std::cerr << "After forwarding: " << *BB->getParent());
+}
+
+/// ReplaceUsesOfValueInRegion - This method replaces all uses of Orig with uses
+/// of New. It only affects instructions that are defined in basic blocks that
+/// are dominated by Head.
+///
+void CEE::ReplaceUsesOfValueInRegion(Value *Orig, Value *New,
+ BasicBlock *RegionDominator) {
+ assert(Orig != New && "Cannot replace value with itself");
+ std::vector<Instruction*> InstsToChange;
+ std::vector<PHINode*> PHIsToChange;
+ InstsToChange.reserve(Orig->use_size());
+
+ // Loop over instructions adding them to InstsToChange vector, this allows us
+ // an easy way to avoid invalidating the use_iterator at a bad time.
+ for (Value::use_iterator I = Orig->use_begin(), E = Orig->use_end();
+ I != E; ++I)
+ if (Instruction *User = dyn_cast<Instruction>(*I))
+ if (DS->dominates(RegionDominator, User->getParent()))
+ InstsToChange.push_back(User);
+ else if (PHINode *PN = dyn_cast<PHINode>(User)) {
+ PHIsToChange.push_back(PN);
+ }
+
+ // PHIsToChange contains PHI nodes that use Orig that do not live in blocks
+ // dominated by orig. If the block the value flows in from is dominated by
+ // RegionDominator, then we rewrite the PHI
+ for (unsigned i = 0, e = PHIsToChange.size(); i != e; ++i) {
+ PHINode *PN = PHIsToChange[i];
+ for (unsigned j = 0, e = PN->getNumIncomingValues(); j != e; ++j)
+ if (PN->getIncomingValue(j) == Orig &&
+ DS->dominates(RegionDominator, PN->getIncomingBlock(j)))
+ PN->setIncomingValue(j, New);
+ }
+
+ // Loop over the InstsToChange list, replacing all uses of Orig with uses of
+ // New. This list contains all of the instructions in our region that use
+ // Orig.
+ for (unsigned i = 0, e = InstsToChange.size(); i != e; ++i)
+ if (PHINode *PN = dyn_cast<PHINode>(InstsToChange[i])) {
+ // PHINodes must be handled carefully. If the PHI node itself is in the
+ // region, we have to make sure to only do the replacement for incoming
+ // values that correspond to basic blocks in the region.
+ for (unsigned j = 0, e = PN->getNumIncomingValues(); j != e; ++j)
+ if (PN->getIncomingValue(j) == Orig &&
+ DS->dominates(RegionDominator, PN->getIncomingBlock(j)))
+ PN->setIncomingValue(j, New);
+
+ } else {
+ InstsToChange[i]->replaceUsesOfWith(Orig, New);
+ }
+}
+
+static void CalcRegionExitBlocks(BasicBlock *Header, BasicBlock *BB,
+ std::set<BasicBlock*> &Visited,
+ DominatorSet &DS,
+ std::vector<BasicBlock*> &RegionExitBlocks) {
+ if (Visited.count(BB)) return;
+ Visited.insert(BB);
+
+ if (DS.dominates(Header, BB)) { // Block in the region, recursively traverse
+ for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
+ CalcRegionExitBlocks(Header, *I, Visited, DS, RegionExitBlocks);
+ } else {
+ // Header does not dominate this block, but we have a predecessor that does
+ // dominate us. Add ourself to the list.
+ RegionExitBlocks.push_back(BB);
+ }
+}
+
+/// CalculateRegionExitBlocks - Find all of the blocks that are not dominated by
+/// BB, but have predecessors that are. Additionally, prune down the set to
+/// only include blocks that are dominated by OldSucc as well.
+///
+void CEE::CalculateRegionExitBlocks(BasicBlock *BB, BasicBlock *OldSucc,
+ std::vector<BasicBlock*> &RegionExitBlocks){
+ std::set<BasicBlock*> Visited; // Don't infinite loop
+
+ // Recursively calculate blocks we are interested in...
+ CalcRegionExitBlocks(BB, BB, Visited, *DS, RegionExitBlocks);
+
+ // Filter out blocks that are not dominated by OldSucc...
+ for (unsigned i = 0; i != RegionExitBlocks.size(); ) {
+ if (DS->dominates(OldSucc, RegionExitBlocks[i]))
+ ++i; // Block is ok, keep it.
+ else {
+ // Move to end of list...
+ std::swap(RegionExitBlocks[i], RegionExitBlocks.back());
+ RegionExitBlocks.pop_back(); // Nuke the end
+ }
+ }
+}
+
+void CEE::InsertRegionExitMerges(PHINode *BBVal, Instruction *OldVal,
+ const std::vector<BasicBlock*> &RegionExitBlocks) {
+ assert(BBVal->getType() == OldVal->getType() && "Should be derived values!");
+ BasicBlock *BB = BBVal->getParent();
+ BasicBlock *OldSucc = OldVal->getParent();
+
+ // Loop over all of the blocks we have to place PHIs in, doing it.
+ for (unsigned i = 0, e = RegionExitBlocks.size(); i != e; ++i) {
+ BasicBlock *FBlock = RegionExitBlocks[i]; // Block on the frontier
+
+ // Create the new PHI node
+ PHINode *NewPN = new PHINode(BBVal->getType(),
+ OldVal->getName()+".fw_frontier",
+ FBlock->begin());
+
+ // Add an incoming value for every predecessor of the block...
+ for (pred_iterator PI = pred_begin(FBlock), PE = pred_end(FBlock);
+ PI != PE; ++PI) {
+ // If the incoming edge is from the region dominated by BB, use BBVal,
+ // otherwise use OldVal.
+ NewPN->addIncoming(DS->dominates(BB, *PI) ? BBVal : OldVal, *PI);
+ }
+
+ // Now make everyone dominated by this block use this new value!
+ ReplaceUsesOfValueInRegion(OldVal, NewPN, FBlock);
+ }
+}
+
+
+