SimplifyCFG.cpp

//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Peephole optimize the CFG.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "simplifycfg"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Type.h"
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#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/IRBuilder.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <set>
#include <map>
using namespace llvm;

static cl::opt<unsigned>
PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(1),
   cl::desc("Control the amount of phi node folding to perform (default = 1)"));

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 {
class SimplifyCFGOpt {
  const TargetData *const TD;

  Value *isValueEqualityComparison(TerminatorInst *TI);
  BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI,
    std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases);
  bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
                                                     BasicBlock *Pred);
  bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI);

  bool SimplifyReturn(ReturnInst *RI);
  bool SimplifyUnwind(UnwindInst *UI);
  bool SimplifyUnreachable(UnreachableInst *UI);
  bool SimplifySwitch(SwitchInst *SI);
  bool SimplifyIndirectBr(IndirectBrInst *IBI);
  bool SimplifyUncondBranch(BranchInst *BI, IRBuilder <> &Builder);
  bool SimplifyCondBranch(BranchInst *BI);

public:
  explicit SimplifyCFGOpt(const TargetData *td) : TD(td) {}
  bool run(BasicBlock *BB);
};
}

/// SafeToMergeTerminators - Return true if it is safe to merge these two
/// terminator instructions together.
///
static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) {
  if (SI1 == SI2) return false;  // Can't merge with self!
  
  // It is not safe to merge these two switch instructions if they have a common
  // successor, and if that successor has a PHI node, and if *that* PHI node has
  // conflicting incoming values from the two switch blocks.
  BasicBlock *SI1BB = SI1->getParent();
  BasicBlock *SI2BB = SI2->getParent();
  SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
  
  for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I)
    if (SI1Succs.count(*I))
      for (BasicBlock::iterator BBI = (*I)->begin();
           isa<PHINode>(BBI); ++BBI) {
        PHINode *PN = cast<PHINode>(BBI);
        if (PN->getIncomingValueForBlock(SI1BB) !=
            PN->getIncomingValueForBlock(SI2BB))
          return false;
      }
        
  return true;
}

/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will
/// now be entries in it from the 'NewPred' block.  The values that will be
/// flowing into the PHI nodes will be the same as those coming in from
/// ExistPred, an existing predecessor of Succ.
static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred,
                                  BasicBlock *ExistPred) {
  if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do
  
  PHINode *PN;
  for (BasicBlock::iterator I = Succ->begin();
       (PN = dyn_cast<PHINode>(I)); ++I)
    PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred);
}


/// GetIfCondition - Given a basic block (BB) with two predecessors (and at
/// least one PHI node in it), check to see if the merge at this block is due
/// to an "if condition".  If so, return the boolean condition that determines
/// which entry into BB will be taken.  Also, return by references the block
/// that will be entered from if the condition is true, and the block that will
/// be entered if the condition is false.
///
/// This does no checking to see if the true/false blocks have large or unsavory
/// instructions in them.
static Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
                             BasicBlock *&IfFalse) {
  PHINode *SomePHI = cast<PHINode>(BB->begin());
  assert(SomePHI->getNumIncomingValues() == 2 &&
         "Function can only handle blocks with 2 predecessors!");
  BasicBlock *Pred1 = SomePHI->getIncomingBlock(0);
  BasicBlock *Pred2 = SomePHI->getIncomingBlock(1);

  // We can only handle branches.  Other control flow will be lowered to
  // branches if possible anyway.
  BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
  BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
  if (Pred1Br == 0 || Pred2Br == 0)
    return 0;

  // Eliminate code duplication by ensuring that Pred1Br is conditional if
  // either are.
  if (Pred2Br->isConditional()) {
    // If both branches are conditional, we don't have an "if statement".  In
    // reality, we could transform this case, but since the condition will be
    // required anyway, we stand no chance of eliminating it, so the xform is
    // probably not profitable.
    if (Pred1Br->isConditional())
      return 0;

    std::swap(Pred1, Pred2);
    std::swap(Pred1Br, Pred2Br);
  }

  if (Pred1Br->isConditional()) {
    // The only thing we have to watch out for here is to make sure that Pred2
    // doesn't have incoming edges from other blocks.  If it does, the condition
    // doesn't dominate BB.
    if (Pred2->getSinglePredecessor() == 0)
      return 0;
    
    // If we found a conditional branch predecessor, make sure that it branches
    // to BB and Pred2Br.  If it doesn't, this isn't an "if statement".
    if (Pred1Br->getSuccessor(0) == BB &&
        Pred1Br->getSuccessor(1) == Pred2) {
      IfTrue = Pred1;
      IfFalse = Pred2;
    } else if (Pred1Br->getSuccessor(0) == Pred2 &&
               Pred1Br->getSuccessor(1) == BB) {
      IfTrue = Pred2;
      IfFalse = Pred1;
    } else {
      // We know that one arm of the conditional goes to BB, so the other must
      // go somewhere unrelated, and this must not be an "if statement".
      return 0;
    }

    return Pred1Br->getCondition();
  }

  // Ok, if we got here, both predecessors end with an unconditional branch to
  // BB.  Don't panic!  If both blocks only have a single (identical)
  // predecessor, and THAT is a conditional branch, then we're all ok!
  BasicBlock *CommonPred = Pred1->getSinglePredecessor();
  if (CommonPred == 0 || CommonPred != Pred2->getSinglePredecessor())
    return 0;

  // Otherwise, if this is a conditional branch, then we can use it!
  BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
  if (BI == 0) return 0;
  
  assert(BI->isConditional() && "Two successors but not conditional?");
  if (BI->getSuccessor(0) == Pred1) {
    IfTrue = Pred1;
    IfFalse = Pred2;
  } else {
    IfTrue = Pred2;
    IfFalse = Pred1;
  }
  return BI->getCondition();
}

/// DominatesMergePoint - If we have a merge point of an "if condition" as
/// accepted above, return true if the specified value dominates the block.  We
/// don't handle the true generality of domination here, just a special case
/// which works well enough for us.
///
/// If AggressiveInsts is non-null, and if V does not dominate BB, we check to
/// see if V (which must be an instruction) and its recursive operands
/// that do not dominate BB have a combined cost lower than CostRemaining and
/// are non-trapping.  If both are true, the instruction is inserted into the
/// set and true is returned.
///
/// The cost for most non-trapping instructions is defined as 1 except for
/// Select whose cost is 2.
///
/// After this function returns, CostRemaining is decreased by the cost of
/// V plus its non-dominating operands.  If that cost is greater than
/// CostRemaining, false is returned and CostRemaining is undefined.
static bool DominatesMergePoint(Value *V, BasicBlock *BB,
                                SmallPtrSet<Instruction*, 4> *AggressiveInsts,
                                unsigned &CostRemaining) {
  Instruction *I = dyn_cast<Instruction>(V);
  if (!I) {
    // Non-instructions all dominate instructions, but not all constantexprs
    // can be executed unconditionally.
    if (ConstantExpr *C = dyn_cast<ConstantExpr>(V))
      if (C->canTrap())
        return false;
    return true;
  }
  BasicBlock *PBB = I->getParent();

  // We don't want to allow weird loops that might have the "if condition" in
  // the bottom of this block.
  if (PBB == BB) return false;

  // If this instruction is defined in a block that contains an unconditional
  // branch to BB, then it must be in the 'conditional' part of the "if
  // statement".  If not, it definitely dominates the region.
  BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator());
  if (BI == 0 || BI->isConditional() || BI->getSuccessor(0) != BB)
    return true;

  // If we aren't allowing aggressive promotion anymore, then don't consider
  // instructions in the 'if region'.
  if (AggressiveInsts == 0) return false;
  
  // If we have seen this instruction before, don't count it again.
  if (AggressiveInsts->count(I)) return true;

  // Okay, it looks like the instruction IS in the "condition".  Check to
  // see if it's a cheap instruction to unconditionally compute, and if it
  // only uses stuff defined outside of the condition.  If so, hoist it out.
  if (!I->isSafeToSpeculativelyExecute())
    return false;

  unsigned Cost = 0;

  switch (I->getOpcode()) {
  default: return false;  // Cannot hoist this out safely.
  case Instruction::Load:
    // We have to check to make sure there are no instructions before the
    // load in its basic block, as we are going to hoist the load out to its
    // predecessor.
    if (PBB->getFirstNonPHIOrDbg() != I)
      return false;
    Cost = 1;
    break;
  case Instruction::GetElementPtr:
    // GEPs are cheap if all indices are constant.
    if (!cast<GetElementPtrInst>(I)->hasAllConstantIndices())
      return false;
    Cost = 1;
    break;
  case Instruction::Add:
  case Instruction::Sub:
  case Instruction::And:
  case Instruction::Or:
  case Instruction::Xor:
  case Instruction::Shl:
  case Instruction::LShr:
  case Instruction::AShr:
  case Instruction::ICmp:
  case Instruction::Trunc:
  case Instruction::ZExt:
  case Instruction::SExt:
    Cost = 1;
    break;   // These are all cheap and non-trapping instructions.

  case Instruction::Select:
    Cost = 2;
    break;
  }

  if (Cost > CostRemaining)
    return false;

  CostRemaining -= Cost;

  // Okay, we can only really hoist these out if their operands do
  // not take us over the cost threshold.
  for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
    if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining))
      return false;
  // Okay, it's safe to do this!  Remember this instruction.
  AggressiveInsts->insert(I);
  return true;
}

/// GetConstantInt - Extract ConstantInt from value, looking through IntToPtr
/// and PointerNullValue. Return NULL if value is not a constant int.
static ConstantInt *GetConstantInt(Value *V, const TargetData *TD) {
  // Normal constant int.
  ConstantInt *CI = dyn_cast<ConstantInt>(V);
  if (CI || !TD || !isa<Constant>(V) || !V->getType()->isPointerTy())
    return CI;

  // This is some kind of pointer constant. Turn it into a pointer-sized
  // ConstantInt if possible.
  const IntegerType *PtrTy = TD->getIntPtrType(V->getContext());

  // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*).
  if (isa<ConstantPointerNull>(V))
    return ConstantInt::get(PtrTy, 0);

  // IntToPtr const int.
  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
    if (CE->getOpcode() == Instruction::IntToPtr)
      if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
        // The constant is very likely to have the right type already.
        if (CI->getType() == PtrTy)
          return CI;
        else
          return cast<ConstantInt>
            (ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false));
      }
  return 0;
}

/// GatherConstantCompares - Given a potentially 'or'd or 'and'd together
/// collection of icmp eq/ne instructions that compare a value against a
/// constant, return the value being compared, and stick the constant into the
/// Values vector.
static Value *
GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra,
                       const TargetData *TD, bool isEQ, unsigned &UsedICmps) {
  Instruction *I = dyn_cast<Instruction>(V);
  if (I == 0) return 0;
  
  // If this is an icmp against a constant, handle this as one of the cases.
  if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
    if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) {
      if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) {
        UsedICmps++;
        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));
      UsedICmps++;
      return I->getOperand(0);
    }
    return 0;
  }
  
  // Otherwise, we can only handle an | or &, depending on isEQ.
  if (I->getOpcode() != (isEQ ? Instruction::Or : Instruction::And))
    return 0;
  
  unsigned NumValsBeforeLHS = Vals.size();
  unsigned UsedICmpsBeforeLHS = UsedICmps;
  if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, TD,
                                          isEQ, UsedICmps)) {
    unsigned NumVals = Vals.size();
    unsigned UsedICmpsBeforeRHS = UsedICmps;
    if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD,
                                            isEQ, UsedICmps)) {
      if (LHS == RHS)
        return LHS;
      Vals.resize(NumVals);
      UsedICmps = UsedICmpsBeforeRHS;
    }

    // The RHS of the or/and can't be folded in and we haven't used "Extra" yet,
    // set it and return success.
    if (Extra == 0 || Extra == I->getOperand(1)) {
      Extra = I->getOperand(1);
      return LHS;
    }
    
    Vals.resize(NumValsBeforeLHS);
    UsedICmps = UsedICmpsBeforeLHS;
    return 0;
  }
  
  // If the LHS can't be folded in, but Extra is available and RHS can, try to
  // use LHS as Extra.
  if (Extra == 0 || Extra == I->getOperand(0)) {
    Value *OldExtra = Extra;
    Extra = I->getOperand(0);
    if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD,
                                            isEQ, UsedICmps))
      return RHS;
    assert(Vals.size() == NumValsBeforeLHS);
    Extra = OldExtra;
  }
  
  return 0;
}
      
static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) {
  Instruction* Cond = 0;
  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
    Cond = dyn_cast<Instruction>(SI->getCondition());
  } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
    if (BI->isConditional())
      Cond = dyn_cast<Instruction>(BI->getCondition());
  } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(TI)) {
    Cond = dyn_cast<Instruction>(IBI->getAddress());
  }

  TI->eraseFromParent();
  if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond);
}

/// isValueEqualityComparison - Return true if the specified terminator checks
/// to see if a value is equal to constant integer value.
Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) {
  Value *CV = 0;
  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
    // Do not permit merging of large switch instructions into their
    // predecessors unless there is only one predecessor.
    if (SI->getNumSuccessors()*std::distance(pred_begin(SI->getParent()),
                                             pred_end(SI->getParent())) <= 128)
      CV = SI->getCondition();
  } else if (BranchInst *BI = dyn_cast<BranchInst>(TI))
    if (BI->isConditional() && BI->getCondition()->hasOneUse())
      if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
        if ((ICI->getPredicate() == ICmpInst::ICMP_EQ ||
             ICI->getPredicate() == ICmpInst::ICMP_NE) &&
            GetConstantInt(ICI->getOperand(1), TD))
          CV = ICI->getOperand(0);

  // Unwrap any lossless ptrtoint cast.
  if (TD && CV && CV->getType() == TD->getIntPtrType(CV->getContext()))
    if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV))
      CV = PTII->getOperand(0);
  return CV;
}

/// GetValueEqualityComparisonCases - Given a value comparison instruction,
/// decode all of the 'cases' that it represents and return the 'default' block.
BasicBlock *SimplifyCFGOpt::
GetValueEqualityComparisonCases(TerminatorInst *TI,
                                std::vector<std::pair<ConstantInt*,
                                                      BasicBlock*> > &Cases) {
  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
    Cases.reserve(SI->getNumCases());
    for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i)
      Cases.push_back(std::make_pair(SI->getCaseValue(i), SI->getSuccessor(i)));
    return SI->getDefaultDest();
  }

  BranchInst *BI = cast<BranchInst>(TI);
  ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
  Cases.push_back(std::make_pair(GetConstantInt(ICI->getOperand(1), TD),
                                 BI->getSuccessor(ICI->getPredicate() ==
                                                  ICmpInst::ICMP_NE)));
  return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ);
}


/// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries
/// in the list that match the specified block.
static void EliminateBlockCases(BasicBlock *BB,
               std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases) {
  for (unsigned i = 0, e = Cases.size(); i != e; ++i)
    if (Cases[i].second == BB) {
      Cases.erase(Cases.begin()+i);
      --i; --e;
    }
}

/// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as
/// well.
static bool
ValuesOverlap(std::vector<std::pair<ConstantInt*, BasicBlock*> > &C1,
              std::vector<std::pair<ConstantInt*, BasicBlock*> > &C2) {
  std::vector<std::pair<ConstantInt*, BasicBlock*> > *V1 = &C1, *V2 = &C2;

  // Make V1 be smaller than V2.
  if (V1->size() > V2->size())
    std::swap(V1, V2);

  if (V1->size() == 0) return false;
  if (V1->size() == 1) {
    // Just scan V2.
    ConstantInt *TheVal = (*V1)[0].first;
    for (unsigned i = 0, e = V2->size(); i != e; ++i)
      if (TheVal == (*V2)[i].first)
        return true;
  }

  // Otherwise, just sort both lists and compare element by element.
  array_pod_sort(V1->begin(), V1->end());
  array_pod_sort(V2->begin(), V2->end());
  unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
  while (i1 != e1 && i2 != e2) {
    if ((*V1)[i1].first == (*V2)[i2].first)
      return true;
    if ((*V1)[i1].first < (*V2)[i2].first)
      ++i1;
    else
      ++i2;
  }
  return false;
}

/// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a
/// terminator instruction and its block is known to only have a single
/// predecessor block, check to see if that predecessor is also a value
/// comparison with the same value, and if that comparison determines the
/// outcome of this comparison.  If so, simplify TI.  This does a very limited
/// form of jump threading.
bool SimplifyCFGOpt::
SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
                                              BasicBlock *Pred) {
  Value *PredVal = isValueEqualityComparison(Pred->getTerminator());
  if (!PredVal) return false;  // Not a value comparison in predecessor.

  Value *ThisVal = isValueEqualityComparison(TI);
  assert(ThisVal && "This isn't a value comparison!!");
  if (ThisVal != PredVal) return false;  // Different predicates.

  // Find out information about when control will move from Pred to TI's block.
  std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases;
  BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(),
                                                        PredCases);
  EliminateBlockCases(PredDef, PredCases);  // Remove default from cases.

  // Find information about how control leaves this block.
  std::vector<std::pair<ConstantInt*, BasicBlock*> > ThisCases;
  BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
  EliminateBlockCases(ThisDef, ThisCases);  // Remove default from cases.

  // If TI's block is the default block from Pred's comparison, potentially
  // simplify TI based on this knowledge.
  if (PredDef == TI->getParent()) {
    // If we are here, we know that the value is none of those cases listed in
    // PredCases.  If there are any cases in ThisCases that are in PredCases, we
    // can simplify TI.
    if (!ValuesOverlap(PredCases, ThisCases))
      return false;
    
    if (isa<BranchInst>(TI)) {
      // Okay, one of the successors of this condbr is dead.  Convert it to a
      // uncond br.
      assert(ThisCases.size() == 1 && "Branch can only have one case!");
      // Insert the new branch.
      Instruction *NI = BranchInst::Create(ThisDef, TI);
      (void) NI;

      // Remove PHI node entries for the dead edge.
      ThisCases[0].second->removePredecessor(TI->getParent());

      DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
           << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");

      EraseTerminatorInstAndDCECond(TI);
      return true;
    }
      
    SwitchInst *SI = cast<SwitchInst>(TI);
    // Okay, TI has cases that are statically dead, prune them away.
    SmallPtrSet<Constant*, 16> DeadCases;
    for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
      DeadCases.insert(PredCases[i].first);

    DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
                 << "Through successor TI: " << *TI);

    for (unsigned i = SI->getNumCases()-1; i != 0; --i)
      if (DeadCases.count(SI->getCaseValue(i))) {
        SI->getSuccessor(i)->removePredecessor(TI->getParent());
        SI->removeCase(i);
      }

    DEBUG(dbgs() << "Leaving: " << *TI << "\n");
    return true;
  }
  
  // Otherwise, TI's block must correspond to some matched value.  Find out
  // which value (or set of values) this is.
  ConstantInt *TIV = 0;
  BasicBlock *TIBB = TI->getParent();
  for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
    if (PredCases[i].second == TIBB) {
      if (TIV != 0)
        return false;  // Cannot handle multiple values coming to this block.
      TIV = PredCases[i].first;
    }
  assert(TIV && "No edge from pred to succ?");

  // Okay, we found the one constant that our value can be if we get into TI's
  // BB.  Find out which successor will unconditionally be branched to.
  BasicBlock *TheRealDest = 0;
  for (unsigned i = 0, e = ThisCases.size(); i != e; ++i)
    if (ThisCases[i].first == TIV) {
      TheRealDest = ThisCases[i].second;
      break;
    }

  // If not handled by any explicit cases, it is handled by the default case.
  if (TheRealDest == 0) TheRealDest = ThisDef;

  // Remove PHI node entries for dead edges.
  BasicBlock *CheckEdge = TheRealDest;
  for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI)
    if (*SI != CheckEdge)
      (*SI)->removePredecessor(TIBB);
    else
      CheckEdge = 0;

  // Insert the new branch.
  Instruction *NI = BranchInst::Create(TheRealDest, TI);
  (void) NI;

  DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
            << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");

  EraseTerminatorInstAndDCECond(TI);
  return true;
}

namespace {
  /// ConstantIntOrdering - This class implements a stable ordering of constant
  /// integers that does not depend on their address.  This is important for
  /// applications that sort ConstantInt's to ensure uniqueness.
  struct ConstantIntOrdering {
    bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const {
      return LHS->getValue().ult(RHS->getValue());
    }
  };
}

static int ConstantIntSortPredicate(const void *P1, const void *P2) {
  const ConstantInt *LHS = *(const ConstantInt**)P1;
  const ConstantInt *RHS = *(const ConstantInt**)P2;
  if (LHS->getValue().ult(RHS->getValue()))
    return 1;
  if (LHS->getValue() == RHS->getValue())
    return 0;
  return -1;
}

/// FoldValueComparisonIntoPredecessors - The specified terminator is a value
/// equality comparison instruction (either a switch or a branch on "X == c").
/// See if any of the predecessors of the terminator block are value comparisons
/// on the same value.  If so, and if safe to do so, fold them together.
bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI) {
  BasicBlock *BB = TI->getParent();
  Value *CV = isValueEqualityComparison(TI);  // CondVal
  assert(CV && "Not a comparison?");
  bool Changed = false;

  SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB));
  while (!Preds.empty()) {
    BasicBlock *Pred = Preds.pop_back_val();

    // See if the predecessor is a comparison with the same value.
    TerminatorInst *PTI = Pred->getTerminator();
    Value *PCV = isValueEqualityComparison(PTI);  // PredCondVal

    if (PCV == CV && SafeToMergeTerminators(TI, PTI)) {
      // Figure out which 'cases' to copy from SI to PSI.
      std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases;
      BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);

      std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases;
      BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);

      // Based on whether the default edge from PTI goes to BB or not, fill in
      // PredCases and PredDefault with the new switch cases we would like to
      // build.
      SmallVector<BasicBlock*, 8> NewSuccessors;

      if (PredDefault == BB) {
        // If this is the default destination from PTI, only the edges in TI
        // that don't occur in PTI, or that branch to BB will be activated.
        std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
        for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
          if (PredCases[i].second != BB)
            PTIHandled.insert(PredCases[i].first);
          else {
            // The default destination is BB, we don't need explicit targets.
            std::swap(PredCases[i], PredCases.back());
            PredCases.pop_back();
            --i; --e;
          }

        // Reconstruct the new switch statement we will be building.
        if (PredDefault != BBDefault) {
          PredDefault->removePredecessor(Pred);
          PredDefault = BBDefault;
          NewSuccessors.push_back(BBDefault);
        }
        for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
          if (!PTIHandled.count(BBCases[i].first) &&
              BBCases[i].second != BBDefault) {
            PredCases.push_back(BBCases[i]);
            NewSuccessors.push_back(BBCases[i].second);
          }

      } else {
        // If this is not the default destination from PSI, only the edges
        // in SI that occur in PSI with a destination of BB will be
        // activated.
        std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
        for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
          if (PredCases[i].second == BB) {
            PTIHandled.insert(PredCases[i].first);
            std::swap(PredCases[i], PredCases.back());
            PredCases.pop_back();
            --i; --e;
          }

        // Okay, now we know which constants were sent to BB from the
        // predecessor.  Figure out where they will all go now.
        for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
          if (PTIHandled.count(BBCases[i].first)) {
            // If this is one we are capable of getting...
            PredCases.push_back(BBCases[i]);
            NewSuccessors.push_back(BBCases[i].second);
            PTIHandled.erase(BBCases[i].first);// This constant is taken care of
          }

        // If there are any constants vectored to BB that TI doesn't handle,
        // they must go to the default destination of TI.
        for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I = 
                                    PTIHandled.begin(),
               E = PTIHandled.end(); I != E; ++I) {
          PredCases.push_back(std::make_pair(*I, BBDefault));
          NewSuccessors.push_back(BBDefault);
        }
      }

      // Okay, at this point, we know which new successor Pred will get.  Make
      // sure we update the number of entries in the PHI nodes for these
      // successors.
      for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i)
        AddPredecessorToBlock(NewSuccessors[i], Pred, BB);

      // Convert pointer to int before we switch.
      if (CV->getType()->isPointerTy()) {
        assert(TD && "Cannot switch on pointer without TargetData");
        CV = new PtrToIntInst(CV, TD->getIntPtrType(CV->getContext()),
                              "magicptr", PTI);
        cast<PtrToIntInst>(CV)->setDebugLoc(PTI->getDebugLoc());
      }

      // Now that the successors are updated, create the new Switch instruction.
      SwitchInst *NewSI = SwitchInst::Create(CV, PredDefault,
                                             PredCases.size(), PTI);
      NewSI->setDebugLoc(PTI->getDebugLoc());
      for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
        NewSI->addCase(PredCases[i].first, PredCases[i].second);

      EraseTerminatorInstAndDCECond(PTI);

      // Okay, last check.  If BB is still a successor of PSI, then we must
      // have an infinite loop case.  If so, add an infinitely looping block
      // to handle the case to preserve the behavior of the code.
      BasicBlock *InfLoopBlock = 0;
      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 function, because it's either code,
            // or it won't matter if it's hot. :)
            InfLoopBlock = BasicBlock::Create(BB->getContext(),
                                              "infloop", BB->getParent());
            BranchInst::Create(InfLoopBlock, InfLoopBlock);
          }
          NewSI->setSuccessor(i, InfLoopBlock);
        }

      Changed = true;
    }
  }
  return Changed;
}

// isSafeToHoistInvoke - If we would need to insert a select that uses the
// value of this invoke (comments in HoistThenElseCodeToIf explain why we
// would need to do this), we can't hoist the invoke, as there is nowhere
// to put the select in this case.
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2,
                                Instruction *I1, Instruction *I2) {
  for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
    PHINode *PN;
    for (BasicBlock::iterator BBI = SI->begin();
         (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
      Value *BB1V = PN->getIncomingValueForBlock(BB1);
      Value *BB2V = PN->getIncomingValueForBlock(BB2);
      if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) {
        return false;
      }
    }
  }
  return true;
}

/// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and
/// BB2, hoist any common code in the two blocks up into the branch block.  The
/// caller of this function guarantees that BI's block dominates BB1 and BB2.
static bool HoistThenElseCodeToIf(BranchInst *BI) {
  // This does very trivial matching, with limited scanning, to find identical
  // instructions in the two blocks.  In particular, we don't want to get into
  // O(M*N) situations here where M and N are the sizes of BB1 and BB2.  As
  // such, we currently just scan for obviously identical instructions in an
  // identical order.
  BasicBlock *BB1 = BI->getSuccessor(0);  // The true destination.
  BasicBlock *BB2 = BI->getSuccessor(1);  // The false destination

  BasicBlock::iterator BB1_Itr = BB1->begin();
  BasicBlock::iterator BB2_Itr = BB2->begin();

  Instruction *I1 = BB1_Itr++, *I2 = BB2_Itr++;
  // Skip debug info if it is not identical.
  DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
  DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
  if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
    while (isa<DbgInfoIntrinsic>(I1))
      I1 = BB1_Itr++;
    while (isa<DbgInfoIntrinsic>(I2))
      I2 = BB2_Itr++;
  }
  if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) ||
      (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)))
    return false;

  // If we get here, we can hoist at least one instruction.
  BasicBlock *BIParent = BI->getParent();

  do {
    // If we are hoisting the terminator instruction, don't move one (making a
    // broken BB), instead clone it, and remove BI.
    if (isa<TerminatorInst>(I1))
      goto HoistTerminator;

    // For a normal instruction, we just move one to right before the branch,
    // then replace all uses of the other with the first.  Finally, we remove
    // the now redundant second instruction.
    BIParent->getInstList().splice(BI, BB1->getInstList(), I1);
    if (!I2->use_empty())
      I2->replaceAllUsesWith(I1);
    I1->intersectOptionalDataWith(I2);
    I2->eraseFromParent();

    I1 = BB1_Itr++;
    I2 = BB2_Itr++;
    // Skip debug info if it is not identical.
    DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
    DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
    if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
      while (isa<DbgInfoIntrinsic>(I1))
        I1 = BB1_Itr++;
      while (isa<DbgInfoIntrinsic>(I2))
        I2 = BB2_Itr++;
    }
  } while (I1->isIdenticalToWhenDefined(I2));

  return true;

HoistTerminator:
  // It may not be possible to hoist an invoke.
  if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))
    return true;

  // Okay, it is safe to hoist the terminator.
  Instruction *NT = I1->clone();
  BIParent->getInstList().insert(BI, NT);
  if (!NT->getType()->isVoidTy()) {
    I1->replaceAllUsesWith(NT);
    I2->replaceAllUsesWith(NT);
    NT->takeName(I1);
  }

  // Hoisting one of the terminators from our successor is a great thing.
  // Unfortunately, the successors of the if/else blocks may have PHI nodes in
  // them.  If they do, all PHI entries for BB1/BB2 must agree for all PHI
  // nodes, so we insert select instruction to compute the final result.
  std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects;
  for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
    PHINode *PN;
    for (BasicBlock::iterator BBI = SI->begin();
         (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
      Value *BB1V = PN->getIncomingValueForBlock(BB1);
      Value *BB2V = PN->getIncomingValueForBlock(BB2);
      if (BB1V == BB2V) continue;
      
      // These values do not agree.  Insert a select instruction before NT
      // that determines the right value.
      SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
      if (SI == 0) {
        SI = SelectInst::Create(BI->getCondition(), BB1V, BB2V,
                                BB1V->getName()+"."+BB2V->getName(), NT);
        SI->setDebugLoc(BI->getDebugLoc());
      }
      // Make the PHI node use the select for all incoming values for BB1/BB2
      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
        if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2)
          PN->setIncomingValue(i, SI);
    }
  }

  // Update any PHI nodes in our new successors.
  for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI)
    AddPredecessorToBlock(*SI, BIParent, BB1);

  EraseTerminatorInstAndDCECond(BI);
  return true;
}

/// SpeculativelyExecuteBB - Given a conditional branch that goes to BB1
/// and an BB2 and the only successor of BB1 is BB2, hoist simple code
/// (for now, restricted to a single instruction that's side effect free) from
/// the BB1 into the branch block to speculatively execute it.
static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) {
  // Only speculatively execution a single instruction (not counting the
  // terminator) for now.
  Instruction *HInst = NULL;
  Instruction *Term = BB1->getTerminator();
  for (BasicBlock::iterator BBI = BB1->begin(), BBE = BB1->end();
       BBI != BBE; ++BBI) {
    Instruction *I = BBI;
    // Skip debug info.
    if (isa<DbgInfoIntrinsic>(I)) continue;
    if (I == Term) break;

    if (HInst)
      return false;
    HInst = I;
  }
  if (!HInst)
    return false;

  // Be conservative for now. FP select instruction can often be expensive.
  Value *BrCond = BI->getCondition();
  if (isa<FCmpInst>(BrCond))
    return false;

  // If BB1 is actually on the false edge of the conditional branch, remember
  // to swap the select operands later.
  bool Invert = false;
  if (BB1 != BI->getSuccessor(0)) {
    assert(BB1 == BI->getSuccessor(1) && "No edge from 'if' block?");
    Invert = true;
  }

  // Turn
  // BB:
  //     %t1 = icmp
  //     br i1 %t1, label %BB1, label %BB2
  // BB1:
  //     %t3 = add %t2, c
  //     br label BB2
  // BB2:
  // =>
  // BB:
  //     %t1 = icmp
  //     %t4 = add %t2, c
  //     %t3 = select i1 %t1, %t2, %t3
  switch (HInst->getOpcode()) {
  default: return false;  // Not safe / profitable to hoist.
  case Instruction::Add:
  case Instruction::Sub:
    // Not worth doing for vector ops.
    if (HInst->getType()->isVectorTy())
      return false;
    break;
  case Instruction::And: