#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/CFG.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <map>
using namespace llvm;
+static cl::opt<bool>
+DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false),
+ cl::desc("Duplicate return instructions into unconditional branches"));
+
STATISTIC(NumSpeculations, "Number of speculative executed instructions");
namespace {
// If this is an icmp against a constant, handle this as one of the cases.
if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
- if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE))
- if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) {
+ if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) {
+ if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) {
Vals.push_back(C);
return I->getOperand(0);
}
+
+ // If we have "x ult 3" comparison, for example, then we can add 0,1,2 to
+ // the set.
+ ConstantRange Span =
+ ConstantRange::makeICmpRegion(ICI->getPredicate(), C->getValue());
+
+ // If this is an and/!= check then we want to optimize "x ugt 2" into
+ // x != 0 && x != 1.
+ if (!isEQ)
+ Span = Span.inverse();
+
+ // If there are a ton of values, we don't want to make a ginormous switch.
+ if (Span.getSetSize().ugt(8) || Span.isEmptySet() ||
+ // We don't handle wrapped sets yet.
+ Span.isWrappedSet())
+ return 0;
+
+ for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp)
+ Vals.push_back(ConstantInt::get(V->getContext(), Tmp));
+ return I->getOperand(0);
+ }
return 0;
}
return true;
}
-// SimplifyIndirectBrOnSelect - Replaces
-// (indirectbr (select cond, blockaddress(@fn, BlockA),
-// blockaddress(@fn, BlockB)))
-// with
-// (br cond, BlockA, BlockB).
-static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) {
- // Check that both operands of the select are block addresses.
- BlockAddress *TBA = dyn_cast<BlockAddress>(SI->getTrueValue());
- BlockAddress *FBA = dyn_cast<BlockAddress>(SI->getFalseValue());
- if (!TBA || !FBA)
- return false;
-
- // Extract the actual blocks.
- BasicBlock *TrueBB = TBA->getBasicBlock();
- BasicBlock *FalseBB = FBA->getBasicBlock();
-
+// SimplifyTerminatorOnSelect - Simplifies a terminator by replacing it with a
+// branch to TrueBB if Cond is true or to FalseBB if Cond is false.
+// Takes care of updating the successors and removing the old terminator.
+// Also makes sure not to introduce new successors by assuming that edges to
+// non-successor TrueBBs and FalseBBs aren't reachable.
+static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond,
+ BasicBlock *TrueBB, BasicBlock *FalseBB){
// Remove any superfluous successor edges from the CFG.
// First, figure out which successors to preserve.
// If TrueBB and FalseBB are equal, only try to preserve one copy of that
BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : 0;
// Then remove the rest.
- for (unsigned I = 0, E = IBI->getNumSuccessors(); I != E; ++I) {
- BasicBlock *Succ = IBI->getSuccessor(I);
+ for (unsigned I = 0, E = OldTerm->getNumSuccessors(); I != E; ++I) {
+ BasicBlock *Succ = OldTerm->getSuccessor(I);
// Make sure only to keep exactly one copy of each edge.
if (Succ == KeepEdge1)
KeepEdge1 = 0;
else if (Succ == KeepEdge2)
KeepEdge2 = 0;
else
- Succ->removePredecessor(IBI->getParent());
+ Succ->removePredecessor(OldTerm->getParent());
}
// Insert an appropriate new terminator.
if (TrueBB == FalseBB)
// We were only looking for one successor, and it was present.
// Create an unconditional branch to it.
- BranchInst::Create(TrueBB, IBI);
+ BranchInst::Create(TrueBB, OldTerm);
else
// We found both of the successors we were looking for.
// Create a conditional branch sharing the condition of the select.
- BranchInst::Create(TrueBB, FalseBB, SI->getCondition(), IBI);
+ BranchInst::Create(TrueBB, FalseBB, Cond, OldTerm);
} else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
// Neither of the selected blocks were successors, so this
- // indirectbr must be unreachable.
- new UnreachableInst(IBI->getContext(), IBI);
+ // terminator must be unreachable.
+ new UnreachableInst(OldTerm->getContext(), OldTerm);
} else {
// One of the selected values was a successor, but the other wasn't.
// Insert an unconditional branch to the one that was found;
// the edge to the one that wasn't must be unreachable.
if (KeepEdge1 == 0)
// Only TrueBB was found.
- BranchInst::Create(TrueBB, IBI);
+ BranchInst::Create(TrueBB, OldTerm);
else
// Only FalseBB was found.
- BranchInst::Create(FalseBB, IBI);
+ BranchInst::Create(FalseBB, OldTerm);
}
- EraseTerminatorInstAndDCECond(IBI);
+ EraseTerminatorInstAndDCECond(OldTerm);
return true;
}
+// SimplifyIndirectBrOnSelect - Replaces
+// (indirectbr (select cond, blockaddress(@fn, BlockA),
+// blockaddress(@fn, BlockB)))
+// with
+// (br cond, BlockA, BlockB).
+static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) {
+ // Check that both operands of the select are block addresses.
+ BlockAddress *TBA = dyn_cast<BlockAddress>(SI->getTrueValue());
+ BlockAddress *FBA = dyn_cast<BlockAddress>(SI->getFalseValue());
+ if (!TBA || !FBA)
+ return false;
+
+ // Extract the actual blocks.
+ BasicBlock *TrueBB = TBA->getBasicBlock();
+ BasicBlock *FalseBB = FBA->getBasicBlock();
+
+ // Perform the actual simplification.
+ return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB);
+}
+
/// TryToSimplifyUncondBranchWithICmpInIt - This is called when we find an icmp
/// instruction (a seteq/setne with a constant) as the only instruction in a
/// block that ends with an uncond branch. We are looking for a very specific
}
// If we found some, do the transformation!
- if (!UncondBranchPreds.empty()) {
+ if (!UncondBranchPreds.empty() && DupRet) {
while (!UncondBranchPreds.empty()) {
BasicBlock *Pred = UncondBranchPreds.pop_back_val();
DEBUG(dbgs() << "FOLDING: " << *BB
<< "INTO UNCOND BRANCH PRED: " << *Pred);
- Instruction *UncondBranch = Pred->getTerminator();
- // Clone the return and add it to the end of the predecessor.
- Instruction *NewRet = RI->clone();
- Pred->getInstList().push_back(NewRet);
-
- // 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 (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)
- *i = PN->getIncomingValueForBlock(Pred);
-
- // Update any PHI nodes in the returning block to realize that we no
- // longer branch to them.
- BB->removePredecessor(Pred);
- UncondBranch->eraseFromParent();
+ (void)FoldReturnIntoUncondBranch(RI, BB, Pred);
}
// If we eliminated all predecessors of the block, delete the block now.
projects / oota-llvm.git / blobdiff