succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!");
if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do
- for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
- PHINode *PN = cast<PHINode>(I);
- Value *V = PN->getIncomingValueForBlock(ExistPred);
- PN->addIncoming(V, NewPred);
- }
+ PHINode *PN;
+ for (BasicBlock::iterator I = Succ->begin();
+ (PN = dyn_cast<PHINode>(I)); ++I)
+ PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred);
}
// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an
CommonPreds.insert(*PI);
// Shortcut, if there are no common predecessors, merging is always safe
- if (CommonPreds.begin() == CommonPreds.end())
+ if (CommonPreds.empty())
return true;
// Look at all the phi nodes in Succ, to see if they present a conflict when
for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i)
if (NewSI->getSuccessor(i) == BB) {
if (InfLoopBlock == 0) {
- // Insert it at the end of the loop, because it's either code,
+ // Insert it at the end of the function, because it's either code,
// or it won't matter if it's hot. :)
InfLoopBlock = BasicBlock::Create("infloop", BB->getParent());
BranchInst::Create(InfLoopBlock, InfLoopBlock);
return true;
}
- // Otherwise, build up the result values for the new return.
- SmallVector<Value*, 4> TrueResult;
- SmallVector<Value*, 4> FalseResult;
+ // Otherwise, figure out what the true and false return values are
+ // so we can insert a new select instruction.
+ Value *TrueValue = TrueRet->getReturnValue();
+ Value *FalseValue = FalseRet->getReturnValue();
+
+ // Unwrap any PHI nodes in the return blocks.
+ if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue))
+ if (TVPN->getParent() == TrueSucc)
+ TrueValue = TVPN->getIncomingValueForBlock(BI->getParent());
+ if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue))
+ if (FVPN->getParent() == FalseSucc)
+ FalseValue = FVPN->getIncomingValueForBlock(BI->getParent());
+
+ // In order for this transformation to be safe, we must be able to
+ // unconditionally execute both operands to the return. This is
+ // normally the case, but we could have a potentially-trapping
+ // constant expression that prevents this transformation from being
+ // safe.
+ if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue))
+ if (TCV->canTrap())
+ return false;
+ if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue))
+ if (FCV->canTrap())
+ return false;
- for (unsigned i = 0, e = TrueRet->getNumOperands(); i != e; ++i) {
- // Otherwise, figure out what the true and false return values are
- // so we can insert a new select instruction.
- Value *TrueValue = TrueRet->getOperand(i);
- Value *FalseValue = FalseRet->getOperand(i);
-
- // Unwrap any PHI nodes in the return blocks.
- if (PHINode *TVPN = dyn_cast<PHINode>(TrueValue))
- if (TVPN->getParent() == TrueSucc)
- TrueValue = TVPN->getIncomingValueForBlock(BI->getParent());
- if (PHINode *FVPN = dyn_cast<PHINode>(FalseValue))
- if (FVPN->getParent() == FalseSucc)
- FalseValue = FVPN->getIncomingValueForBlock(BI->getParent());
-
- // In order for this transformation to be safe, we must be able to
- // unconditionally execute both operands to the return. This is
- // normally the case, but we could have a potentially-trapping
- // constant expression that prevents this transformation from being
- // safe.
- if (ConstantExpr *TCV = dyn_cast<ConstantExpr>(TrueValue))
- if (TCV->canTrap())
- return false;
- if (ConstantExpr *FCV = dyn_cast<ConstantExpr>(FalseValue))
- if (FCV->canTrap())
- return false;
-
- TrueResult.push_back(TrueValue);
- FalseResult.push_back(FalseValue);
- }
-
// Okay, we collected all the mapped values and checked them for sanity, and
// defined to really do this transformation. First, update the CFG.
TrueSucc->removePredecessor(BI->getParent());
// Insert select instructions where needed.
Value *BrCond = BI->getCondition();
- for (unsigned i = 0, e = TrueRet->getNumOperands(); i != e; ++i) {
+ if (TrueValue) {
// Insert a select if the results differ.
- if (TrueResult[i] == FalseResult[i] || isa<UndefValue>(FalseResult[i]))
- continue;
- if (isa<UndefValue>(TrueResult[i])) {
- TrueResult[i] = FalseResult[i];
- continue;
+ if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) {
+ } else if (isa<UndefValue>(TrueValue)) {
+ TrueValue = FalseValue;
+ } else {
+ TrueValue = SelectInst::Create(BrCond, TrueValue,
+ FalseValue, "retval", BI);
}
-
- TrueResult[i] = SelectInst::Create(BrCond, TrueResult[i],
- FalseResult[i], "retval", BI);
}
- Value *RI = ReturnInst::Create(&TrueResult[0], TrueResult.size(), BI);
+ Value *RI = !TrueValue ?
+ ReturnInst::Create(BI) :
+ ReturnInst::Create(TrueValue, BI);
DOUT << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:"
<< "\n " << *BI << "NewRet = " << *RI
/// setcc into the predecessor and use logical operations to pick the right
/// destination.
static bool FoldBranchToCommonDest(BranchInst *BI) {
+ BasicBlock *BB = BI->getParent();
Instruction *Cond = dyn_cast<Instruction>(BI->getCondition());
if (Cond == 0) return false;
- BasicBlock *BB = BI->getParent();
-
+
// Only allow this if the condition is a simple instruction that can be
// executed unconditionally. It must be in the same block as the branch, and
// must be at the front of the block.
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
BasicBlock *PredBlock = *PI;
BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
+ // Check that we have two conditional branches. If there is a PHI node in
+ // the common successor, verify that the same value flows in from both
+ // blocks.
if (PBI == 0 || PBI->isUnconditional() ||
!SafeToMergeTerminators(BI, PBI))
continue;
// Finally, if everything is ok, fold the branches to logical ops.
BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1);
- // If OtherDest *is* BB, then this is a basic block with just
- // a conditional branch in it, where one edge (OtherDesg) goes
- // back to the block. We know that the program doesn't get
- // stuck in the infinite loop, so the condition must be such
- // that OtherDest isn't branched through. Forward to CommonDest,
- // and avoid an infinite loop at optimizer time.
- if (OtherDest == BB)
- OtherDest = CommonDest;
-
DOUT << "FOLDING BRs:" << *PBI->getParent()
<< "AND: " << *BI->getParent();
+
+ // If OtherDest *is* BB, then BB is a basic block with a single conditional
+ // branch in it, where one edge (OtherDest) goes back to itself but the other
+ // exits. We don't *know* that the program avoids the infinite loop
+ // (even though that seems likely). If we do this xform naively, we'll end up
+ // recursively unpeeling the loop. Since we know that (after the xform is
+ // done) that the block *is* infinite if reached, we just make it an obviously
+ // infinite loop with no cond branch.
+ if (OtherDest == BB) {
+ // Insert it at the end of the function, because it's either code,
+ // or it won't matter if it's hot. :)
+ BasicBlock *InfLoopBlock = BasicBlock::Create("infloop", BB->getParent());
+ BranchInst::Create(InfLoopBlock, InfLoopBlock);
+ OtherDest = InfLoopBlock;
+ }
+
DOUT << *PBI->getParent()->getParent();
// BI may have other predecessors. Because of this, we leave
// pred, and if there is only one distinct successor of the predecessor, and
// if there are no PHI nodes.
//
+ if (MergeBlockIntoPredecessor(BB))
+ return true;
+
+ // Otherwise, if this block only has a single predecessor, and if that block
+ // is a conditional branch, see if we can hoist any code from this block up
+ // into our predecessor.
pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
BasicBlock *OnlyPred = *PI++;
for (; PI != PE; ++PI) // Search all predecessors, see if they are all same
OnlyPred = 0; // There are multiple different predecessors...
break;
}
-
- BasicBlock *OnlySucc = 0;
- if (OnlyPred && OnlyPred != BB && // Don't break self loops
- OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) {
- // Check to see if there is only one distinct successor...
- succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred));
- OnlySucc = BB;
- for (; SI != SE; ++SI)
- if (*SI != OnlySucc) {
- OnlySucc = 0; // There are multiple distinct successors!
- break;
- }
- }
-
- if (OnlySucc) {
- DOUT << "Merging: " << *BB << "into: " << *OnlyPred;
-
- // Resolve any PHI nodes at the start of the block. They are all
- // guaranteed to have exactly one entry if they exist, unless there are
- // multiple duplicate (but guaranteed to be equal) entries for the
- // incoming edges. This occurs when there are multiple edges from
- // OnlyPred to OnlySucc.
- //
- while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
- PN->replaceAllUsesWith(PN->getIncomingValue(0));
- BB->getInstList().pop_front(); // Delete the phi node.
- }
-
- // Delete the unconditional branch from the predecessor.
- OnlyPred->getInstList().pop_back();
-
- // Move all definitions in the successor to the predecessor.
- OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
-
- // Make all PHI nodes that referred to BB now refer to Pred as their
- // source.
- BB->replaceAllUsesWith(OnlyPred);
-
- // Inherit predecessors name if it exists.
- if (!OnlyPred->hasName())
- OnlyPred->takeName(BB);
-
- // Erase basic block from the function.
- M->getBasicBlockList().erase(BB);
-
- return true;
- }
-
- // Otherwise, if this block only has a single predecessor, and if that block
- // is a conditional branch, see if we can hoist any code from this block up
- // into our predecessor.
+
if (OnlyPred)
if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator()))
if (BI->isConditional()) {
BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB);
PI = pred_begin(OtherBB);
++PI;
+
if (PI == pred_end(OtherBB)) {
// We have a conditional branch to two blocks that are only reachable
// from the condbr. We know that the condbr dominates the two blocks,
// blocks. If so, we can hoist it up to the branching block.
Changed |= HoistThenElseCodeToIf(BI);
} else {
- OnlySucc = NULL;
+ BasicBlock* OnlySucc = NULL;
for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
SI != SE; ++SI) {
if (!OnlySucc)
projects / oota-llvm.git / blobdiff