#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/Statistic.h"
#include <algorithm>
#include <functional>
#include <set>
#include <map>
using namespace llvm;
+STATISTIC(NumSpeculations, "Number of speculative executed instructions");
+
/// SafeToMergeTerminators - Return true if it is safe to merge these two
/// terminator instructions together.
///
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
// Okay, we can only really hoist these out if their operands are not
// defined in the conditional region.
- for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
- if (!DominatesMergePoint(I->getOperand(i), BB, 0))
+ for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
+ if (!DominatesMergePoint(*i, BB, 0))
return false;
// Okay, it's safe to do this! Remember this instruction.
AggressiveInsts->insert(I);
}
// Add operands of dead instruction to worklist.
- for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
- if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i)))
+ for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
+ if (Instruction *OpI = dyn_cast<Instruction>(*i))
InstrsToInspect.push_back(OpI);
// Remove dead instruction.
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);
static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) {
// Only speculatively execution a single instruction (not counting the
// terminator) for now.
- if (BB1->size() != 2)
+ BasicBlock::iterator BBI = BB1->begin();
+ ++BBI; // must have at least a terminator
+ if (BBI == BB1->end()) return false; // only one inst
+ ++BBI;
+ if (BBI != BB1->end()) return false; // more than 2 insts.
+
+ // Be conservative for now. FP select instruction can often be expensive.
+ Value *BrCond = BI->getCondition();
+ if (isa<Instruction>(BrCond) &&
+ cast<Instruction>(BrCond)->getOpcode() == Instruction::FCmp)
return false;
// If BB1 is actually on the false edge of the conditional branch, remember
case Instruction::Shl:
case Instruction::LShr:
case Instruction::AShr:
- if (I->getOperand(0)->getType()->isFPOrFPVector())
- return false; // FP arithmetic might trap.
+ if (!I->getOperand(0)->getType()->isInteger())
+ // FP arithmetic might trap. Not worth doing for vector ops.
+ return false;
break; // These are all cheap and non-trapping instructions.
}
if (!FalseV) // Can this happen?
return false;
+ // Do not hoist the instruction if any of its operands are defined but not
+ // used in this BB. The transformation will prevent the operand from
+ // being sunk into the use block.
+ for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) {
+ Instruction *OpI = dyn_cast<Instruction>(*i);
+ if (OpI && OpI->getParent() == BIParent &&
+ !OpI->isUsedInBasicBlock(BIParent))
+ return false;
+ }
+
// If we get here, we can hoist the instruction. Try to place it before the
- // icmp / fcmp instruction preceeding the conditional branch.
+ // icmp instruction preceeding the conditional branch.
BasicBlock::iterator InsertPos = BI;
if (InsertPos != BIParent->begin())
--InsertPos;
- if (InsertPos->getOpcode() == Instruction::ICmp ||
- InsertPos->getOpcode() == Instruction::FCmp)
+ if (InsertPos == BrCond && !isa<PHINode>(BrCond))
BIParent->getInstList().splice(InsertPos, BB1->getInstList(), I);
else
BIParent->getInstList().splice(BI, BB1->getInstList(), I);
// false value is the previously determined FalseV.
SelectInst *SI;
if (Invert)
- SI = SelectInst::Create(BI->getCondition(), FalseV, I,
+ SI = SelectInst::Create(BrCond, FalseV, I,
FalseV->getName() + "." + I->getName(), BI);
else
- SI = SelectInst::Create(BI->getCondition(), I, FalseV,
+ SI = SelectInst::Create(BrCond, I, FalseV,
I->getName() + "." + FalseV->getName(), BI);
// Make the PHI node use the select for all incoming values for "then" and
PN->setIncomingValue(j, SI);
}
+ ++NumSpeculations;
return true;
}
if (BBI->hasName()) N->setName(BBI->getName()+".c");
// Update operands due to translation.
- for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
+ for (User::op_iterator i = N->op_begin(), e = N->op_end();
+ i != e; ++i) {
std::map<Value*, Value*>::iterator PI =
- TranslateMap.find(N->getOperand(i));
+ TranslateMap.find(*i);
if (PI != TranslateMap.end())
- N->setOperand(i, PI->second);
+ *i = PI->second;
}
// Check for trivial simplification.
return true;
}
+/// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch,
+/// and if a predecessor branches to us and one of our successors, fold the
+/// 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;
+
+
+ // 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.
+ if ((!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) ||
+ Cond->getParent() != BB || &BB->front() != Cond || !Cond->hasOneUse())
+ return false;
+
+ // Make sure the instruction after the condition is the cond branch.
+ BasicBlock::iterator CondIt = Cond; ++CondIt;
+ if (&*CondIt != BI)
+ return false;
+
+ // Finally, don't infinitely unroll conditional loops.
+ BasicBlock *TrueDest = BI->getSuccessor(0);
+ BasicBlock *FalseDest = BI->getSuccessor(1);
+ if (TrueDest == BB || FalseDest == BB)
+ return false;
+
+ 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;
+
+ Instruction::BinaryOps Opc;
+ bool InvertPredCond = false;
+
+ if (PBI->getSuccessor(0) == TrueDest)
+ Opc = Instruction::Or;
+ else if (PBI->getSuccessor(1) == FalseDest)
+ Opc = Instruction::And;
+ else if (PBI->getSuccessor(0) == FalseDest)
+ Opc = Instruction::And, InvertPredCond = true;
+ else if (PBI->getSuccessor(1) == TrueDest)
+ Opc = Instruction::Or, InvertPredCond = true;
+ else
+ continue;
+
+ // If we need to invert the condition in the pred block to match, do so now.
+ if (InvertPredCond) {
+ Value *NewCond =
+ BinaryOperator::CreateNot(PBI->getCondition(),
+ PBI->getCondition()->getName()+".not", PBI);
+ PBI->setCondition(NewCond);
+ BasicBlock *OldTrue = PBI->getSuccessor(0);
+ BasicBlock *OldFalse = PBI->getSuccessor(1);
+ PBI->setSuccessor(0, OldFalse);
+ PBI->setSuccessor(1, OldTrue);
+ }
+
+ // Clone Cond into the predecessor basic block, and or/and the
+ // two conditions together.
+ Instruction *New = Cond->clone();
+ PredBlock->getInstList().insert(PBI, New);
+ New->takeName(Cond);
+ Cond->setName(New->getName()+".old");
+
+ Value *NewCond = BinaryOperator::Create(Opc, PBI->getCondition(),
+ New, "or.cond", PBI);
+ PBI->setCondition(NewCond);
+ if (PBI->getSuccessor(0) == BB) {
+ AddPredecessorToBlock(TrueDest, PredBlock, BB);
+ PBI->setSuccessor(0, TrueDest);
+ }
+ if (PBI->getSuccessor(1) == BB) {
+ AddPredecessorToBlock(FalseDest, PredBlock, BB);
+ PBI->setSuccessor(1, FalseDest);
+ }
+ return true;
+ }
+ return false;
+}
+
+/// SimplifyCondBranchToCondBranch - If we have a conditional branch as a
+/// predecessor of another block, this function tries to simplify it. We know
+/// that PBI and BI are both conditional branches, and BI is in one of the
+/// successor blocks of PBI - PBI branches to BI.
+static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) {
+ assert(PBI->isConditional() && BI->isConditional());
+ BasicBlock *BB = BI->getParent();
+
+ // If this block ends with a branch instruction, and if there is a
+ // predecessor that ends on a branch of the same condition, make
+ // this conditional branch redundant.
+ if (PBI->getCondition() == BI->getCondition() &&
+ PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
+ // Okay, the outcome of this conditional branch is statically
+ // knowable. If this block had a single pred, handle specially.
+ if (BB->getSinglePredecessor()) {
+ // Turn this into a branch on constant.
+ bool CondIsTrue = PBI->getSuccessor(0) == BB;
+ BI->setCondition(ConstantInt::get(Type::Int1Ty, CondIsTrue));
+ return true; // Nuke the branch on constant.
+ }
+
+ // Otherwise, if there are multiple predecessors, insert a PHI that merges
+ // in the constant and simplify the block result. Subsequent passes of
+ // simplifycfg will thread the block.
+ if (BlockIsSimpleEnoughToThreadThrough(BB)) {
+ PHINode *NewPN = PHINode::Create(Type::Int1Ty,
+ BI->getCondition()->getName() + ".pr",
+ BB->begin());
+ // Okay, we're going to insert the PHI node. Since PBI is not the only
+ // predecessor, compute the PHI'd conditional value for all of the preds.
+ // Any predecessor where the condition is not computable we keep symbolic.
+ for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
+ if ((PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) &&
+ PBI != BI && PBI->isConditional() &&
+ PBI->getCondition() == BI->getCondition() &&
+ PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
+ bool CondIsTrue = PBI->getSuccessor(0) == BB;
+ NewPN->addIncoming(ConstantInt::get(Type::Int1Ty,
+ CondIsTrue), *PI);
+ } else {
+ NewPN->addIncoming(BI->getCondition(), *PI);
+ }
+
+ BI->setCondition(NewPN);
+ return true;
+ }
+ }
+
+ // If this is a conditional branch in an empty block, and if any
+ // predecessors is a conditional branch to one of our destinations,
+ // fold the conditions into logical ops and one cond br.
+ if (&BB->front() != BI)
+ return false;
+
+ int PBIOp, BIOp;
+ if (PBI->getSuccessor(0) == BI->getSuccessor(0))
+ PBIOp = BIOp = 0;
+ else if (PBI->getSuccessor(0) == BI->getSuccessor(1))
+ PBIOp = 0, BIOp = 1;
+ else if (PBI->getSuccessor(1) == BI->getSuccessor(0))
+ PBIOp = 1, BIOp = 0;
+ else if (PBI->getSuccessor(1) == BI->getSuccessor(1))
+ PBIOp = BIOp = 1;
+ else
+ return false;
+
+ // Check to make sure that the other destination of this branch
+ // isn't BB itself. If so, this is an infinite loop that will
+ // keep getting unwound.
+ if (PBI->getSuccessor(PBIOp) == BB)
+ return false;
+
+ // Do not perform this transformation if it would require
+ // insertion of a large number of select instructions. For targets
+ // without predication/cmovs, this is a big pessimization.
+ BasicBlock *CommonDest = PBI->getSuccessor(PBIOp);
+
+ unsigned NumPhis = 0;
+ for (BasicBlock::iterator II = CommonDest->begin();
+ isa<PHINode>(II); ++II, ++NumPhis)
+ if (NumPhis > 2) // Disable this xform.
+ return false;
+
+ // Finally, if everything is ok, fold the branches to logical ops.
+ BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1);
+
+ 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
+ // it alone, but modify PBI.
+
+ // Make sure we get to CommonDest on True&True directions.
+ Value *PBICond = PBI->getCondition();
+ if (PBIOp)
+ PBICond = BinaryOperator::CreateNot(PBICond,
+ PBICond->getName()+".not",
+ PBI);
+ Value *BICond = BI->getCondition();
+ if (BIOp)
+ BICond = BinaryOperator::CreateNot(BICond,
+ BICond->getName()+".not",
+ PBI);
+ // Merge the conditions.
+ Value *Cond = BinaryOperator::CreateOr(PBICond, BICond, "brmerge", PBI);
+
+ // Modify PBI to branch on the new condition to the new dests.
+ PBI->setCondition(Cond);
+ PBI->setSuccessor(0, CommonDest);
+ PBI->setSuccessor(1, OtherDest);
+
+ // OtherDest may have phi nodes. If so, add an entry from PBI's
+ // block that are identical to the entries for BI's block.
+ PHINode *PN;
+ for (BasicBlock::iterator II = OtherDest->begin();
+ (PN = dyn_cast<PHINode>(II)); ++II) {
+ Value *V = PN->getIncomingValueForBlock(BB);
+ PN->addIncoming(V, PBI->getParent());
+ }
+
+ // We know that the CommonDest already had an edge from PBI to
+ // it. If it has PHIs though, the PHIs may have different
+ // entries for BB and PBI's BB. If so, insert a select to make
+ // them agree.
+ for (BasicBlock::iterator II = CommonDest->begin();
+ (PN = dyn_cast<PHINode>(II)); ++II) {
+ Value *BIV = PN->getIncomingValueForBlock(BB);
+ unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent());
+ Value *PBIV = PN->getIncomingValue(PBBIdx);
+ if (BIV != PBIV) {
+ // Insert a select in PBI to pick the right value.
+ Value *NV = SelectInst::Create(PBICond, PBIV, BIV,
+ PBIV->getName()+".mux", PBI);
+ PN->setIncomingValue(PBBIdx, NV);
+ }
+ }
+
+ DOUT << "INTO: " << *PBI->getParent();
+
+ DOUT << *PBI->getParent()->getParent();
+
+ // This basic block is probably dead. We know it has at least
+ // one fewer predecessor.
+ return true;
+}
+
namespace {
/// ConstantIntOrdering - This class implements a stable ordering of constant
// If the return instruction returns a value, and if the value was a
// PHI node in "BB", propagate the right value into the return.
- for (unsigned i = 0, e = NewRet->getNumOperands(); i != e; ++i)
- if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(i)))
+ for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end();
+ i != e; ++i)
+ if (PHINode *PN = dyn_cast<PHINode>(*i))
if (PN->getParent() == BB)
- NewRet->setOperand(i, PN->getIncomingValueForBlock(Pred));
+ *i = PN->getIncomingValueForBlock(Pred);
// Update any PHI nodes in the returning block to realize that we no
// longer branch to them.
// Insert the call now...
SmallVector<Value*,8> Args(II->op_begin()+3, II->op_end());
CallInst *CI = CallInst::Create(II->getCalledValue(),
- Args.begin(), Args.end(), II->getName(), BI);
+ Args.begin(), Args.end(),
+ II->getName(), BI);
CI->setCallingConv(II->getCallingConv());
CI->setParamAttrs(II->getParamAttrs());
// If the invoke produced a value, the Call now does instead
if (BBI->isTerminator() && // Terminator is the only non-phi instruction!
Succ != BB) // Don't hurt infinite loops!
if (TryToSimplifyUncondBranchFromEmptyBlock(BB, Succ))
- return 1;
+ return true;
} else { // Conditional branch
if (isValueEqualityComparison(BI)) {
// If this basic block is ONLY a setcc and a branch, and if a predecessor
// branches to us and one of our successors, fold the setcc into the
// predecessor and use logical operations to pick the right destination.
- BasicBlock *TrueDest = BI->getSuccessor(0);
- BasicBlock *FalseDest = BI->getSuccessor(1);
- if (Instruction *Cond = dyn_cast<Instruction>(BI->getCondition())) {
- BasicBlock::iterator CondIt = Cond;
- if ((isa<CmpInst>(Cond) || isa<BinaryOperator>(Cond)) &&
- Cond->getParent() == BB && &BB->front() == Cond &&
- &*++CondIt == BI && Cond->hasOneUse() &&
- TrueDest != BB && FalseDest != BB)
- for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI!=E; ++PI)
- if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
- if (PBI->isConditional() && SafeToMergeTerminators(BI, PBI)) {
- BasicBlock *PredBlock = *PI;
- if (PBI->getSuccessor(0) == FalseDest ||
- PBI->getSuccessor(1) == TrueDest) {
- // Invert the predecessors condition test (xor it with true),
- // which allows us to write this code once.
- Value *NewCond =
- BinaryOperator::CreateNot(PBI->getCondition(),
- PBI->getCondition()->getName()+".not", PBI);
- PBI->setCondition(NewCond);
- BasicBlock *OldTrue = PBI->getSuccessor(0);
- BasicBlock *OldFalse = PBI->getSuccessor(1);
- PBI->setSuccessor(0, OldFalse);
- PBI->setSuccessor(1, OldTrue);
- }
+ if (FoldBranchToCommonDest(BI))
+ return SimplifyCFG(BB) | 1;
- if ((PBI->getSuccessor(0) == TrueDest && FalseDest != BB) ||
- (PBI->getSuccessor(1) == FalseDest && TrueDest != BB)) {
- // Clone Cond into the predecessor basic block, and or/and the
- // two conditions together.
- Instruction *New = Cond->clone();
- PredBlock->getInstList().insert(PBI, New);
- New->takeName(Cond);
- Cond->setName(New->getName()+".old");
- Instruction::BinaryOps Opcode =
- PBI->getSuccessor(0) == TrueDest ?
- Instruction::Or : Instruction::And;
- Value *NewCond =
- BinaryOperator::Create(Opcode, PBI->getCondition(),
- New, "bothcond", PBI);
- PBI->setCondition(NewCond);
- if (PBI->getSuccessor(0) == BB) {
- AddPredecessorToBlock(TrueDest, PredBlock, BB);
- PBI->setSuccessor(0, TrueDest);
- }
- if (PBI->getSuccessor(1) == BB) {
- AddPredecessorToBlock(FalseDest, PredBlock, BB);
- PBI->setSuccessor(1, FalseDest);
- }
- return SimplifyCFG(BB) | 1;
- }
- }
- }
- // Scan predessor blocks for conditional branches.
+ // Scan predecessor blocks for conditional branches.
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
- if (PBI != BI && PBI->isConditional()) {
-
- // If this block ends with a branch instruction, and if there is a
- // predecessor that ends on a branch of the same condition, make
- // this conditional branch redundant.
- if (PBI->getCondition() == BI->getCondition() &&
- PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
- // Okay, the outcome of this conditional branch is statically
- // knowable. If this block had a single pred, handle specially.
- if (BB->getSinglePredecessor()) {
- // Turn this into a branch on constant.
- bool CondIsTrue = PBI->getSuccessor(0) == BB;
- BI->setCondition(ConstantInt::get(Type::Int1Ty, CondIsTrue));
- return SimplifyCFG(BB); // Nuke the branch on constant.
- }
-
- // Otherwise, if there are multiple predecessors, insert a PHI
- // that merges in the constant and simplify the block result.
- if (BlockIsSimpleEnoughToThreadThrough(BB)) {
- PHINode *NewPN = PHINode::Create(Type::Int1Ty,
- BI->getCondition()->getName()+".pr",
- BB->begin());
- for (PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
- if ((PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) &&
- PBI != BI && PBI->isConditional() &&
- PBI->getCondition() == BI->getCondition() &&
- PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
- bool CondIsTrue = PBI->getSuccessor(0) == BB;
- NewPN->addIncoming(ConstantInt::get(Type::Int1Ty,
- CondIsTrue), *PI);
- } else {
- NewPN->addIncoming(BI->getCondition(), *PI);
- }
-
- BI->setCondition(NewPN);
- // This will thread the branch.
- return SimplifyCFG(BB) | true;
- }
- }
-
- // If this is a conditional branch in an empty block, and if any
- // predecessors is a conditional branch to one of our destinations,
- // fold the conditions into logical ops and one cond br.
- if (&BB->front() == BI) {
- int PBIOp, BIOp;
- if (PBI->getSuccessor(0) == BI->getSuccessor(0)) {
- PBIOp = BIOp = 0;
- } else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) {
- PBIOp = 0; BIOp = 1;
- } else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) {
- PBIOp = 1; BIOp = 0;
- } else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) {
- PBIOp = BIOp = 1;
- } else {
- PBIOp = BIOp = -1;
- }
-
- // Check to make sure that the other destination of this branch
- // isn't BB itself. If so, this is an infinite loop that will
- // keep getting unwound.
- if (PBIOp != -1 && PBI->getSuccessor(PBIOp) == BB)
- PBIOp = BIOp = -1;
-
- // Do not perform this transformation if it would require
- // insertion of a large number of select instructions. For targets
- // without predication/cmovs, this is a big pessimization.
- if (PBIOp != -1) {
- BasicBlock *CommonDest = PBI->getSuccessor(PBIOp);
-
- unsigned NumPhis = 0;
- for (BasicBlock::iterator II = CommonDest->begin();
- isa<PHINode>(II); ++II, ++NumPhis) {
- if (NumPhis > 2) {
- // Disable this xform.
- PBIOp = -1;
- break;
- }
- }
- }
-
- // Finally, if everything is ok, fold the branches to logical ops.
- if (PBIOp != -1) {
- BasicBlock *CommonDest = PBI->getSuccessor(PBIOp);
- 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();
-
- // BI may have other predecessors. Because of this, we leave
- // it alone, but modify PBI.
-
- // Make sure we get to CommonDest on True&True directions.
- Value *PBICond = PBI->getCondition();
- if (PBIOp)
- PBICond = BinaryOperator::CreateNot(PBICond,
- PBICond->getName()+".not",
- PBI);
- Value *BICond = BI->getCondition();
- if (BIOp)
- BICond = BinaryOperator::CreateNot(BICond,
- BICond->getName()+".not",
- PBI);
- // Merge the conditions.
- Value *Cond =
- BinaryOperator::CreateOr(PBICond, BICond, "brmerge", PBI);
-
- // Modify PBI to branch on the new condition to the new dests.
- PBI->setCondition(Cond);
- PBI->setSuccessor(0, CommonDest);
- PBI->setSuccessor(1, OtherDest);
-
- // OtherDest may have phi nodes. If so, add an entry from PBI's
- // block that are identical to the entries for BI's block.
- PHINode *PN;
- for (BasicBlock::iterator II = OtherDest->begin();
- (PN = dyn_cast<PHINode>(II)); ++II) {
- Value *V = PN->getIncomingValueForBlock(BB);
- PN->addIncoming(V, PBI->getParent());
- }
-
- // We know that the CommonDest already had an edge from PBI to
- // it. If it has PHIs though, the PHIs may have different
- // entries for BB and PBI's BB. If so, insert a select to make
- // them agree.
- for (BasicBlock::iterator II = CommonDest->begin();
- (PN = dyn_cast<PHINode>(II)); ++II) {
- Value * BIV = PN->getIncomingValueForBlock(BB);
- unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent());
- Value *PBIV = PN->getIncomingValue(PBBIdx);
- if (BIV != PBIV) {
- // Insert a select in PBI to pick the right value.
- Value *NV = SelectInst::Create(PBICond, PBIV, BIV,
- PBIV->getName()+".mux", PBI);
- PN->setIncomingValue(PBBIdx, NV);
- }
- }
-
- DOUT << "INTO: " << *PBI->getParent();
-
- // This basic block is probably dead. We know it has at least
- // one fewer predecessor.
- return SimplifyCFG(BB) | true;
- }
- }
- }
+ if (PBI != BI && PBI->isConditional())
+ if (SimplifyCondBranchToCondBranch(PBI, BI))
+ return SimplifyCFG(BB) | true;
}
} else if (isa<UnreachableInst>(BB->getTerminator())) {
// If there are any instructions immediately before the unreachable that can
// 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