+ BasicBlock *BB = TI->getParent();
+
+ // Get the destination block of this edge...
+ BasicBlock *OldSucc = TI->getSuccessor(SuccNo);
+
+ // Make sure that the block ends with a conditional branch and is simple
+ // enough for use to be able to revector over.
+ BranchInst *BI = dyn_cast<BranchInst>(OldSucc->getTerminator());
+ if (BI == 0 || !BI->isConditional() || !isBlockSimpleEnough(OldSucc))
+ return false;
+
+ // We can only forward the branch over the block if the block ends with a
+ // setcc we can determine the outcome for.
+ //
+ // FIXME: we can make this more generic. Code below already handles more
+ // generic case.
+ SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition());
+ if (SCI == 0) return false;
+
+ // Make a new RegionInfo structure so that we can simulate the effect of the
+ // PHI nodes in the block we are skipping over...
+ //
+ RegionInfo NewRI(RI);
+
+ // Remove value information for all of the values we are simulating... to make
+ // sure we don't have any stale information.
+ for (BasicBlock::iterator I = OldSucc->begin(), E = OldSucc->end(); I!=E; ++I)
+ if (I->getType() != Type::VoidTy)
+ NewRI.removeValueInfo(I);
+
+ // Put the newly discovered information into the RegionInfo...
+ for (BasicBlock::iterator I = OldSucc->begin(), E = OldSucc->end(); I!=E; ++I)
+ if (PHINode *PN = dyn_cast<PHINode>(&*I)) {
+ int OpNum = PN->getBasicBlockIndex(BB);
+ assert(OpNum != -1 && "PHI doesn't have incoming edge for predecessor!?");
+ PropagateEquality(PN, PN->getIncomingValue(OpNum), NewRI);
+ } else if (SetCondInst *SCI = dyn_cast<SetCondInst>(&*I)) {
+ Relation::KnownResult Res = getSetCCResult(SCI, NewRI);
+ if (Res == Relation::Unknown) return false;
+ PropagateEquality(SCI, ConstantBool::get(Res), NewRI);
+ } else {
+ assert(isa<BranchInst>(*I) && "Unexpected instruction type!");
+ }
+
+ // Compute the facts implied by what we have discovered...
+ ComputeReplacements(NewRI);
+
+ ValueInfo &PredicateVI = NewRI.getValueInfo(BI->getCondition());
+ if (PredicateVI.getReplacement() &&
+ isa<Constant>(PredicateVI.getReplacement())) {
+ ConstantBool *CB = cast<ConstantBool>(PredicateVI.getReplacement());
+
+ // Forward to the successor that corresponds to the branch we will take.
+ ForwardSuccessorTo(TI, SuccNo, BI->getSuccessor(!CB->getValue()), NewRI);
+ return true;
+ }
+
+ return false;
+}
+
+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