LLVM API Documentation

SimplifyCFG.cpp
Go to the documentation of this file.
00001 //===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Peephole optimize the CFG.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/Transforms/Utils/Local.h"
00015 #include "llvm/ADT/DenseMap.h"
00016 #include "llvm/ADT/STLExtras.h"
00017 #include "llvm/ADT/SetVector.h"
00018 #include "llvm/ADT/SmallPtrSet.h"
00019 #include "llvm/ADT/SmallVector.h"
00020 #include "llvm/ADT/Statistic.h"
00021 #include "llvm/Analysis/ConstantFolding.h"
00022 #include "llvm/Analysis/InstructionSimplify.h"
00023 #include "llvm/Analysis/TargetTransformInfo.h"
00024 #include "llvm/Analysis/ValueTracking.h"
00025 #include "llvm/IR/CFG.h"
00026 #include "llvm/IR/ConstantRange.h"
00027 #include "llvm/IR/Constants.h"
00028 #include "llvm/IR/DataLayout.h"
00029 #include "llvm/IR/DerivedTypes.h"
00030 #include "llvm/IR/GlobalVariable.h"
00031 #include "llvm/IR/IRBuilder.h"
00032 #include "llvm/IR/Instructions.h"
00033 #include "llvm/IR/IntrinsicInst.h"
00034 #include "llvm/IR/LLVMContext.h"
00035 #include "llvm/IR/MDBuilder.h"
00036 #include "llvm/IR/Metadata.h"
00037 #include "llvm/IR/Module.h"
00038 #include "llvm/IR/NoFolder.h"
00039 #include "llvm/IR/Operator.h"
00040 #include "llvm/IR/PatternMatch.h"
00041 #include "llvm/IR/Type.h"
00042 #include "llvm/Support/CommandLine.h"
00043 #include "llvm/Support/Debug.h"
00044 #include "llvm/Support/raw_ostream.h"
00045 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00046 #include "llvm/Transforms/Utils/Local.h"
00047 #include "llvm/Transforms/Utils/ValueMapper.h"
00048 #include <algorithm>
00049 #include <map>
00050 #include <set>
00051 using namespace llvm;
00052 using namespace PatternMatch;
00053 
00054 #define DEBUG_TYPE "simplifycfg"
00055 
00056 static cl::opt<unsigned>
00057 PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(1),
00058    cl::desc("Control the amount of phi node folding to perform (default = 1)"));
00059 
00060 static cl::opt<bool>
00061 DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false),
00062        cl::desc("Duplicate return instructions into unconditional branches"));
00063 
00064 static cl::opt<bool>
00065 SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true),
00066        cl::desc("Sink common instructions down to the end block"));
00067 
00068 static cl::opt<bool> HoistCondStores(
00069     "simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true),
00070     cl::desc("Hoist conditional stores if an unconditional store precedes"));
00071 
00072 STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
00073 STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables");
00074 STATISTIC(NumLookupTablesHoles, "Number of switch instructions turned into lookup tables (holes checked)");
00075 STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block");
00076 STATISTIC(NumSpeculations, "Number of speculative executed instructions");
00077 
00078 namespace {
00079   /// ValueEqualityComparisonCase - Represents a case of a switch.
00080   struct ValueEqualityComparisonCase {
00081     ConstantInt *Value;
00082     BasicBlock *Dest;
00083 
00084     ValueEqualityComparisonCase(ConstantInt *Value, BasicBlock *Dest)
00085       : Value(Value), Dest(Dest) {}
00086 
00087     bool operator<(ValueEqualityComparisonCase RHS) const {
00088       // Comparing pointers is ok as we only rely on the order for uniquing.
00089       return Value < RHS.Value;
00090     }
00091 
00092     bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; }
00093   };
00094 
00095 class SimplifyCFGOpt {
00096   const TargetTransformInfo &TTI;
00097   unsigned BonusInstThreshold;
00098   const DataLayout *const DL;
00099   AssumptionTracker *AT;
00100   Value *isValueEqualityComparison(TerminatorInst *TI);
00101   BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI,
00102                                std::vector<ValueEqualityComparisonCase> &Cases);
00103   bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
00104                                                      BasicBlock *Pred,
00105                                                      IRBuilder<> &Builder);
00106   bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
00107                                            IRBuilder<> &Builder);
00108 
00109   bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder);
00110   bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder);
00111   bool SimplifyUnreachable(UnreachableInst *UI);
00112   bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
00113   bool SimplifyIndirectBr(IndirectBrInst *IBI);
00114   bool SimplifyUncondBranch(BranchInst *BI, IRBuilder <> &Builder);
00115   bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder);
00116 
00117 public:
00118   SimplifyCFGOpt(const TargetTransformInfo &TTI, unsigned BonusInstThreshold,
00119                  const DataLayout *DL, AssumptionTracker *AT)
00120       : TTI(TTI), BonusInstThreshold(BonusInstThreshold), DL(DL), AT(AT) {}
00121   bool run(BasicBlock *BB);
00122 };
00123 }
00124 
00125 /// SafeToMergeTerminators - Return true if it is safe to merge these two
00126 /// terminator instructions together.
00127 ///
00128 static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) {
00129   if (SI1 == SI2) return false;  // Can't merge with self!
00130 
00131   // It is not safe to merge these two switch instructions if they have a common
00132   // successor, and if that successor has a PHI node, and if *that* PHI node has
00133   // conflicting incoming values from the two switch blocks.
00134   BasicBlock *SI1BB = SI1->getParent();
00135   BasicBlock *SI2BB = SI2->getParent();
00136   SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
00137 
00138   for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I)
00139     if (SI1Succs.count(*I))
00140       for (BasicBlock::iterator BBI = (*I)->begin();
00141            isa<PHINode>(BBI); ++BBI) {
00142         PHINode *PN = cast<PHINode>(BBI);
00143         if (PN->getIncomingValueForBlock(SI1BB) !=
00144             PN->getIncomingValueForBlock(SI2BB))
00145           return false;
00146       }
00147 
00148   return true;
00149 }
00150 
00151 /// isProfitableToFoldUnconditional - Return true if it is safe and profitable
00152 /// to merge these two terminator instructions together, where SI1 is an
00153 /// unconditional branch. PhiNodes will store all PHI nodes in common
00154 /// successors.
00155 ///
00156 static bool isProfitableToFoldUnconditional(BranchInst *SI1,
00157                                           BranchInst *SI2,
00158                                           Instruction *Cond,
00159                                           SmallVectorImpl<PHINode*> &PhiNodes) {
00160   if (SI1 == SI2) return false;  // Can't merge with self!
00161   assert(SI1->isUnconditional() && SI2->isConditional());
00162 
00163   // We fold the unconditional branch if we can easily update all PHI nodes in
00164   // common successors:
00165   // 1> We have a constant incoming value for the conditional branch;
00166   // 2> We have "Cond" as the incoming value for the unconditional branch;
00167   // 3> SI2->getCondition() and Cond have same operands.
00168   CmpInst *Ci2 = dyn_cast<CmpInst>(SI2->getCondition());
00169   if (!Ci2) return false;
00170   if (!(Cond->getOperand(0) == Ci2->getOperand(0) &&
00171         Cond->getOperand(1) == Ci2->getOperand(1)) &&
00172       !(Cond->getOperand(0) == Ci2->getOperand(1) &&
00173         Cond->getOperand(1) == Ci2->getOperand(0)))
00174     return false;
00175 
00176   BasicBlock *SI1BB = SI1->getParent();
00177   BasicBlock *SI2BB = SI2->getParent();
00178   SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
00179   for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I)
00180     if (SI1Succs.count(*I))
00181       for (BasicBlock::iterator BBI = (*I)->begin();
00182            isa<PHINode>(BBI); ++BBI) {
00183         PHINode *PN = cast<PHINode>(BBI);
00184         if (PN->getIncomingValueForBlock(SI1BB) != Cond ||
00185             !isa<ConstantInt>(PN->getIncomingValueForBlock(SI2BB)))
00186           return false;
00187         PhiNodes.push_back(PN);
00188       }
00189   return true;
00190 }
00191 
00192 /// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will
00193 /// now be entries in it from the 'NewPred' block.  The values that will be
00194 /// flowing into the PHI nodes will be the same as those coming in from
00195 /// ExistPred, an existing predecessor of Succ.
00196 static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred,
00197                                   BasicBlock *ExistPred) {
00198   if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do
00199 
00200   PHINode *PN;
00201   for (BasicBlock::iterator I = Succ->begin();
00202        (PN = dyn_cast<PHINode>(I)); ++I)
00203     PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred);
00204 }
00205 
00206 /// ComputeSpeculationCost - Compute an abstract "cost" of speculating the
00207 /// given instruction, which is assumed to be safe to speculate. 1 means
00208 /// cheap, 2 means less cheap, and UINT_MAX means prohibitively expensive.
00209 static unsigned ComputeSpeculationCost(const User *I, const DataLayout *DL) {
00210   assert(isSafeToSpeculativelyExecute(I, DL) &&
00211          "Instruction is not safe to speculatively execute!");
00212   switch (Operator::getOpcode(I)) {
00213   default:
00214     // In doubt, be conservative.
00215     return UINT_MAX;
00216   case Instruction::GetElementPtr:
00217     // GEPs are cheap if all indices are constant.
00218     if (!cast<GEPOperator>(I)->hasAllConstantIndices())
00219       return UINT_MAX;
00220     return 1;
00221   case Instruction::ExtractValue:
00222   case Instruction::Load:
00223   case Instruction::Add:
00224   case Instruction::Sub:
00225   case Instruction::And:
00226   case Instruction::Or:
00227   case Instruction::Xor:
00228   case Instruction::Shl:
00229   case Instruction::LShr:
00230   case Instruction::AShr:
00231   case Instruction::ICmp:
00232   case Instruction::Trunc:
00233   case Instruction::ZExt:
00234   case Instruction::SExt:
00235   case Instruction::BitCast:
00236   case Instruction::ExtractElement:
00237   case Instruction::InsertElement:
00238     return 1; // These are all cheap.
00239 
00240   case Instruction::Call:
00241   case Instruction::Select:
00242     return 2;
00243   }
00244 }
00245 
00246 /// DominatesMergePoint - If we have a merge point of an "if condition" as
00247 /// accepted above, return true if the specified value dominates the block.  We
00248 /// don't handle the true generality of domination here, just a special case
00249 /// which works well enough for us.
00250 ///
00251 /// If AggressiveInsts is non-null, and if V does not dominate BB, we check to
00252 /// see if V (which must be an instruction) and its recursive operands
00253 /// that do not dominate BB have a combined cost lower than CostRemaining and
00254 /// are non-trapping.  If both are true, the instruction is inserted into the
00255 /// set and true is returned.
00256 ///
00257 /// The cost for most non-trapping instructions is defined as 1 except for
00258 /// Select whose cost is 2.
00259 ///
00260 /// After this function returns, CostRemaining is decreased by the cost of
00261 /// V plus its non-dominating operands.  If that cost is greater than
00262 /// CostRemaining, false is returned and CostRemaining is undefined.
00263 static bool DominatesMergePoint(Value *V, BasicBlock *BB,
00264                                 SmallPtrSetImpl<Instruction*> *AggressiveInsts,
00265                                 unsigned &CostRemaining,
00266                                 const DataLayout *DL) {
00267   Instruction *I = dyn_cast<Instruction>(V);
00268   if (!I) {
00269     // Non-instructions all dominate instructions, but not all constantexprs
00270     // can be executed unconditionally.
00271     if (ConstantExpr *C = dyn_cast<ConstantExpr>(V))
00272       if (C->canTrap())
00273         return false;
00274     return true;
00275   }
00276   BasicBlock *PBB = I->getParent();
00277 
00278   // We don't want to allow weird loops that might have the "if condition" in
00279   // the bottom of this block.
00280   if (PBB == BB) return false;
00281 
00282   // If this instruction is defined in a block that contains an unconditional
00283   // branch to BB, then it must be in the 'conditional' part of the "if
00284   // statement".  If not, it definitely dominates the region.
00285   BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator());
00286   if (!BI || BI->isConditional() || BI->getSuccessor(0) != BB)
00287     return true;
00288 
00289   // If we aren't allowing aggressive promotion anymore, then don't consider
00290   // instructions in the 'if region'.
00291   if (!AggressiveInsts) return false;
00292 
00293   // If we have seen this instruction before, don't count it again.
00294   if (AggressiveInsts->count(I)) return true;
00295 
00296   // Okay, it looks like the instruction IS in the "condition".  Check to
00297   // see if it's a cheap instruction to unconditionally compute, and if it
00298   // only uses stuff defined outside of the condition.  If so, hoist it out.
00299   if (!isSafeToSpeculativelyExecute(I, DL))
00300     return false;
00301 
00302   unsigned Cost = ComputeSpeculationCost(I, DL);
00303 
00304   if (Cost > CostRemaining)
00305     return false;
00306 
00307   CostRemaining -= Cost;
00308 
00309   // Okay, we can only really hoist these out if their operands do
00310   // not take us over the cost threshold.
00311   for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
00312     if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining, DL))
00313       return false;
00314   // Okay, it's safe to do this!  Remember this instruction.
00315   AggressiveInsts->insert(I);
00316   return true;
00317 }
00318 
00319 /// GetConstantInt - Extract ConstantInt from value, looking through IntToPtr
00320 /// and PointerNullValue. Return NULL if value is not a constant int.
00321 static ConstantInt *GetConstantInt(Value *V, const DataLayout *DL) {
00322   // Normal constant int.
00323   ConstantInt *CI = dyn_cast<ConstantInt>(V);
00324   if (CI || !DL || !isa<Constant>(V) || !V->getType()->isPointerTy())
00325     return CI;
00326 
00327   // This is some kind of pointer constant. Turn it into a pointer-sized
00328   // ConstantInt if possible.
00329   IntegerType *PtrTy = cast<IntegerType>(DL->getIntPtrType(V->getType()));
00330 
00331   // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*).
00332   if (isa<ConstantPointerNull>(V))
00333     return ConstantInt::get(PtrTy, 0);
00334 
00335   // IntToPtr const int.
00336   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
00337     if (CE->getOpcode() == Instruction::IntToPtr)
00338       if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
00339         // The constant is very likely to have the right type already.
00340         if (CI->getType() == PtrTy)
00341           return CI;
00342         else
00343           return cast<ConstantInt>
00344             (ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false));
00345       }
00346   return nullptr;
00347 }
00348 
00349 /// GatherConstantCompares - Given a potentially 'or'd or 'and'd together
00350 /// collection of icmp eq/ne instructions that compare a value against a
00351 /// constant, return the value being compared, and stick the constant into the
00352 /// Values vector.
00353 static Value *
00354 GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra,
00355                        const DataLayout *DL, bool isEQ, unsigned &UsedICmps) {
00356   Instruction *I = dyn_cast<Instruction>(V);
00357   if (!I) return nullptr;
00358 
00359   // If this is an icmp against a constant, handle this as one of the cases.
00360   if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
00361     if (ConstantInt *C = GetConstantInt(I->getOperand(1), DL)) {
00362       Value *RHSVal;
00363       ConstantInt *RHSC;
00364 
00365       if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) {
00366         // (x & ~2^x) == y --> x == y || x == y|2^x
00367         // This undoes a transformation done by instcombine to fuse 2 compares.
00368         if (match(ICI->getOperand(0),
00369                   m_And(m_Value(RHSVal), m_ConstantInt(RHSC)))) {
00370           APInt Not = ~RHSC->getValue();
00371           if (Not.isPowerOf2()) {
00372             Vals.push_back(C);
00373             Vals.push_back(
00374                 ConstantInt::get(C->getContext(), C->getValue() | Not));
00375             UsedICmps++;
00376             return RHSVal;
00377           }
00378         }
00379 
00380         UsedICmps++;
00381         Vals.push_back(C);
00382         return I->getOperand(0);
00383       }
00384 
00385       // If we have "x ult 3" comparison, for example, then we can add 0,1,2 to
00386       // the set.
00387       ConstantRange Span =
00388         ConstantRange::makeICmpRegion(ICI->getPredicate(), C->getValue());
00389 
00390       // Shift the range if the compare is fed by an add. This is the range
00391       // compare idiom as emitted by instcombine.
00392       bool hasAdd =
00393           match(I->getOperand(0), m_Add(m_Value(RHSVal), m_ConstantInt(RHSC)));
00394       if (hasAdd)
00395         Span = Span.subtract(RHSC->getValue());
00396 
00397       // If this is an and/!= check then we want to optimize "x ugt 2" into
00398       // x != 0 && x != 1.
00399       if (!isEQ)
00400         Span = Span.inverse();
00401 
00402       // If there are a ton of values, we don't want to make a ginormous switch.
00403       if (Span.getSetSize().ugt(8) || Span.isEmptySet())
00404         return nullptr;
00405 
00406       for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp)
00407         Vals.push_back(ConstantInt::get(V->getContext(), Tmp));
00408       UsedICmps++;
00409       return hasAdd ? RHSVal : I->getOperand(0);
00410     }
00411     return nullptr;
00412   }
00413 
00414   // Otherwise, we can only handle an | or &, depending on isEQ.
00415   if (I->getOpcode() != (isEQ ? Instruction::Or : Instruction::And))
00416     return nullptr;
00417 
00418   unsigned NumValsBeforeLHS = Vals.size();
00419   unsigned UsedICmpsBeforeLHS = UsedICmps;
00420   if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, DL,
00421                                           isEQ, UsedICmps)) {
00422     unsigned NumVals = Vals.size();
00423     unsigned UsedICmpsBeforeRHS = UsedICmps;
00424     if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, DL,
00425                                             isEQ, UsedICmps)) {
00426       if (LHS == RHS)
00427         return LHS;
00428       Vals.resize(NumVals);
00429       UsedICmps = UsedICmpsBeforeRHS;
00430     }
00431 
00432     // The RHS of the or/and can't be folded in and we haven't used "Extra" yet,
00433     // set it and return success.
00434     if (Extra == nullptr || Extra == I->getOperand(1)) {
00435       Extra = I->getOperand(1);
00436       return LHS;
00437     }
00438 
00439     Vals.resize(NumValsBeforeLHS);
00440     UsedICmps = UsedICmpsBeforeLHS;
00441     return nullptr;
00442   }
00443 
00444   // If the LHS can't be folded in, but Extra is available and RHS can, try to
00445   // use LHS as Extra.
00446   if (Extra == nullptr || Extra == I->getOperand(0)) {
00447     Value *OldExtra = Extra;
00448     Extra = I->getOperand(0);
00449     if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, DL,
00450                                             isEQ, UsedICmps))
00451       return RHS;
00452     assert(Vals.size() == NumValsBeforeLHS);
00453     Extra = OldExtra;
00454   }
00455 
00456   return nullptr;
00457 }
00458 
00459 static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) {
00460   Instruction *Cond = nullptr;
00461   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
00462     Cond = dyn_cast<Instruction>(SI->getCondition());
00463   } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
00464     if (BI->isConditional())
00465       Cond = dyn_cast<Instruction>(BI->getCondition());
00466   } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(TI)) {
00467     Cond = dyn_cast<Instruction>(IBI->getAddress());
00468   }
00469 
00470   TI->eraseFromParent();
00471   if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond);
00472 }
00473 
00474 /// isValueEqualityComparison - Return true if the specified terminator checks
00475 /// to see if a value is equal to constant integer value.
00476 Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) {
00477   Value *CV = nullptr;
00478   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
00479     // Do not permit merging of large switch instructions into their
00480     // predecessors unless there is only one predecessor.
00481     if (SI->getNumSuccessors()*std::distance(pred_begin(SI->getParent()),
00482                                              pred_end(SI->getParent())) <= 128)
00483       CV = SI->getCondition();
00484   } else if (BranchInst *BI = dyn_cast<BranchInst>(TI))
00485     if (BI->isConditional() && BI->getCondition()->hasOneUse())
00486       if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
00487         if (ICI->isEquality() && GetConstantInt(ICI->getOperand(1), DL))
00488           CV = ICI->getOperand(0);
00489 
00490   // Unwrap any lossless ptrtoint cast.
00491   if (DL && CV) {
00492     if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV)) {
00493       Value *Ptr = PTII->getPointerOperand();
00494       if (PTII->getType() == DL->getIntPtrType(Ptr->getType()))
00495         CV = Ptr;
00496     }
00497   }
00498   return CV;
00499 }
00500 
00501 /// GetValueEqualityComparisonCases - Given a value comparison instruction,
00502 /// decode all of the 'cases' that it represents and return the 'default' block.
00503 BasicBlock *SimplifyCFGOpt::
00504 GetValueEqualityComparisonCases(TerminatorInst *TI,
00505                                 std::vector<ValueEqualityComparisonCase>
00506                                                                        &Cases) {
00507   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
00508     Cases.reserve(SI->getNumCases());
00509     for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i)
00510       Cases.push_back(ValueEqualityComparisonCase(i.getCaseValue(),
00511                                                   i.getCaseSuccessor()));
00512     return SI->getDefaultDest();
00513   }
00514 
00515   BranchInst *BI = cast<BranchInst>(TI);
00516   ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
00517   BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE);
00518   Cases.push_back(ValueEqualityComparisonCase(GetConstantInt(ICI->getOperand(1),
00519                                                              DL),
00520                                               Succ));
00521   return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ);
00522 }
00523 
00524 
00525 /// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries
00526 /// in the list that match the specified block.
00527 static void EliminateBlockCases(BasicBlock *BB,
00528                               std::vector<ValueEqualityComparisonCase> &Cases) {
00529   Cases.erase(std::remove(Cases.begin(), Cases.end(), BB), Cases.end());
00530 }
00531 
00532 /// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as
00533 /// well.
00534 static bool
00535 ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1,
00536               std::vector<ValueEqualityComparisonCase > &C2) {
00537   std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
00538 
00539   // Make V1 be smaller than V2.
00540   if (V1->size() > V2->size())
00541     std::swap(V1, V2);
00542 
00543   if (V1->size() == 0) return false;
00544   if (V1->size() == 1) {
00545     // Just scan V2.
00546     ConstantInt *TheVal = (*V1)[0].Value;
00547     for (unsigned i = 0, e = V2->size(); i != e; ++i)
00548       if (TheVal == (*V2)[i].Value)
00549         return true;
00550   }
00551 
00552   // Otherwise, just sort both lists and compare element by element.
00553   array_pod_sort(V1->begin(), V1->end());
00554   array_pod_sort(V2->begin(), V2->end());
00555   unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
00556   while (i1 != e1 && i2 != e2) {
00557     if ((*V1)[i1].Value == (*V2)[i2].Value)
00558       return true;
00559     if ((*V1)[i1].Value < (*V2)[i2].Value)
00560       ++i1;
00561     else
00562       ++i2;
00563   }
00564   return false;
00565 }
00566 
00567 /// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a
00568 /// terminator instruction and its block is known to only have a single
00569 /// predecessor block, check to see if that predecessor is also a value
00570 /// comparison with the same value, and if that comparison determines the
00571 /// outcome of this comparison.  If so, simplify TI.  This does a very limited
00572 /// form of jump threading.
00573 bool SimplifyCFGOpt::
00574 SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
00575                                               BasicBlock *Pred,
00576                                               IRBuilder<> &Builder) {
00577   Value *PredVal = isValueEqualityComparison(Pred->getTerminator());
00578   if (!PredVal) return false;  // Not a value comparison in predecessor.
00579 
00580   Value *ThisVal = isValueEqualityComparison(TI);
00581   assert(ThisVal && "This isn't a value comparison!!");
00582   if (ThisVal != PredVal) return false;  // Different predicates.
00583 
00584   // TODO: Preserve branch weight metadata, similarly to how
00585   // FoldValueComparisonIntoPredecessors preserves it.
00586 
00587   // Find out information about when control will move from Pred to TI's block.
00588   std::vector<ValueEqualityComparisonCase> PredCases;
00589   BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(),
00590                                                         PredCases);
00591   EliminateBlockCases(PredDef, PredCases);  // Remove default from cases.
00592 
00593   // Find information about how control leaves this block.
00594   std::vector<ValueEqualityComparisonCase> ThisCases;
00595   BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
00596   EliminateBlockCases(ThisDef, ThisCases);  // Remove default from cases.
00597 
00598   // If TI's block is the default block from Pred's comparison, potentially
00599   // simplify TI based on this knowledge.
00600   if (PredDef == TI->getParent()) {
00601     // If we are here, we know that the value is none of those cases listed in
00602     // PredCases.  If there are any cases in ThisCases that are in PredCases, we
00603     // can simplify TI.
00604     if (!ValuesOverlap(PredCases, ThisCases))
00605       return false;
00606 
00607     if (isa<BranchInst>(TI)) {
00608       // Okay, one of the successors of this condbr is dead.  Convert it to a
00609       // uncond br.
00610       assert(ThisCases.size() == 1 && "Branch can only have one case!");
00611       // Insert the new branch.
00612       Instruction *NI = Builder.CreateBr(ThisDef);
00613       (void) NI;
00614 
00615       // Remove PHI node entries for the dead edge.
00616       ThisCases[0].Dest->removePredecessor(TI->getParent());
00617 
00618       DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
00619            << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");
00620 
00621       EraseTerminatorInstAndDCECond(TI);
00622       return true;
00623     }
00624 
00625     SwitchInst *SI = cast<SwitchInst>(TI);
00626     // Okay, TI has cases that are statically dead, prune them away.
00627     SmallPtrSet<Constant*, 16> DeadCases;
00628     for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
00629       DeadCases.insert(PredCases[i].Value);
00630 
00631     DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
00632                  << "Through successor TI: " << *TI);
00633 
00634     // Collect branch weights into a vector.
00635     SmallVector<uint32_t, 8> Weights;
00636     MDNode* MD = SI->getMetadata(LLVMContext::MD_prof);
00637     bool HasWeight = MD && (MD->getNumOperands() == 2 + SI->getNumCases());
00638     if (HasWeight)
00639       for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
00640            ++MD_i) {
00641         ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(MD_i));
00642         assert(CI);
00643         Weights.push_back(CI->getValue().getZExtValue());
00644       }
00645     for (SwitchInst::CaseIt i = SI->case_end(), e = SI->case_begin(); i != e;) {
00646       --i;
00647       if (DeadCases.count(i.getCaseValue())) {
00648         if (HasWeight) {
00649           std::swap(Weights[i.getCaseIndex()+1], Weights.back());
00650           Weights.pop_back();
00651         }
00652         i.getCaseSuccessor()->removePredecessor(TI->getParent());
00653         SI->removeCase(i);
00654       }
00655     }
00656     if (HasWeight && Weights.size() >= 2)
00657       SI->setMetadata(LLVMContext::MD_prof,
00658                       MDBuilder(SI->getParent()->getContext()).
00659                       createBranchWeights(Weights));
00660 
00661     DEBUG(dbgs() << "Leaving: " << *TI << "\n");
00662     return true;
00663   }
00664 
00665   // Otherwise, TI's block must correspond to some matched value.  Find out
00666   // which value (or set of values) this is.
00667   ConstantInt *TIV = nullptr;
00668   BasicBlock *TIBB = TI->getParent();
00669   for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
00670     if (PredCases[i].Dest == TIBB) {
00671       if (TIV)
00672         return false;  // Cannot handle multiple values coming to this block.
00673       TIV = PredCases[i].Value;
00674     }
00675   assert(TIV && "No edge from pred to succ?");
00676 
00677   // Okay, we found the one constant that our value can be if we get into TI's
00678   // BB.  Find out which successor will unconditionally be branched to.
00679   BasicBlock *TheRealDest = nullptr;
00680   for (unsigned i = 0, e = ThisCases.size(); i != e; ++i)
00681     if (ThisCases[i].Value == TIV) {
00682       TheRealDest = ThisCases[i].Dest;
00683       break;
00684     }
00685 
00686   // If not handled by any explicit cases, it is handled by the default case.
00687   if (!TheRealDest) TheRealDest = ThisDef;
00688 
00689   // Remove PHI node entries for dead edges.
00690   BasicBlock *CheckEdge = TheRealDest;
00691   for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI)
00692     if (*SI != CheckEdge)
00693       (*SI)->removePredecessor(TIBB);
00694     else
00695       CheckEdge = nullptr;
00696 
00697   // Insert the new branch.
00698   Instruction *NI = Builder.CreateBr(TheRealDest);
00699   (void) NI;
00700 
00701   DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
00702             << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");
00703 
00704   EraseTerminatorInstAndDCECond(TI);
00705   return true;
00706 }
00707 
00708 namespace {
00709   /// ConstantIntOrdering - This class implements a stable ordering of constant
00710   /// integers that does not depend on their address.  This is important for
00711   /// applications that sort ConstantInt's to ensure uniqueness.
00712   struct ConstantIntOrdering {
00713     bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const {
00714       return LHS->getValue().ult(RHS->getValue());
00715     }
00716   };
00717 }
00718 
00719 static int ConstantIntSortPredicate(ConstantInt *const *P1,
00720                                     ConstantInt *const *P2) {
00721   const ConstantInt *LHS = *P1;
00722   const ConstantInt *RHS = *P2;
00723   if (LHS->getValue().ult(RHS->getValue()))
00724     return 1;
00725   if (LHS->getValue() == RHS->getValue())
00726     return 0;
00727   return -1;
00728 }
00729 
00730 static inline bool HasBranchWeights(const Instruction* I) {
00731   MDNode* ProfMD = I->getMetadata(LLVMContext::MD_prof);
00732   if (ProfMD && ProfMD->getOperand(0))
00733     if (MDString* MDS = dyn_cast<MDString>(ProfMD->getOperand(0)))
00734       return MDS->getString().equals("branch_weights");
00735 
00736   return false;
00737 }
00738 
00739 /// Get Weights of a given TerminatorInst, the default weight is at the front
00740 /// of the vector. If TI is a conditional eq, we need to swap the branch-weight
00741 /// metadata.
00742 static void GetBranchWeights(TerminatorInst *TI,
00743                              SmallVectorImpl<uint64_t> &Weights) {
00744   MDNode* MD = TI->getMetadata(LLVMContext::MD_prof);
00745   assert(MD);
00746   for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) {
00747     ConstantInt *CI = cast<ConstantInt>(MD->getOperand(i));
00748     Weights.push_back(CI->getValue().getZExtValue());
00749   }
00750 
00751   // If TI is a conditional eq, the default case is the false case,
00752   // and the corresponding branch-weight data is at index 2. We swap the
00753   // default weight to be the first entry.
00754   if (BranchInst* BI = dyn_cast<BranchInst>(TI)) {
00755     assert(Weights.size() == 2);
00756     ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
00757     if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
00758       std::swap(Weights.front(), Weights.back());
00759   }
00760 }
00761 
00762 /// Keep halving the weights until all can fit in uint32_t.
00763 static void FitWeights(MutableArrayRef<uint64_t> Weights) {
00764   uint64_t Max = *std::max_element(Weights.begin(), Weights.end());
00765   if (Max > UINT_MAX) {
00766     unsigned Offset = 32 - countLeadingZeros(Max);
00767     for (uint64_t &I : Weights)
00768       I >>= Offset;
00769   }
00770 }
00771 
00772 /// FoldValueComparisonIntoPredecessors - The specified terminator is a value
00773 /// equality comparison instruction (either a switch or a branch on "X == c").
00774 /// See if any of the predecessors of the terminator block are value comparisons
00775 /// on the same value.  If so, and if safe to do so, fold them together.
00776 bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
00777                                                          IRBuilder<> &Builder) {
00778   BasicBlock *BB = TI->getParent();
00779   Value *CV = isValueEqualityComparison(TI);  // CondVal
00780   assert(CV && "Not a comparison?");
00781   bool Changed = false;
00782 
00783   SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB));
00784   while (!Preds.empty()) {
00785     BasicBlock *Pred = Preds.pop_back_val();
00786 
00787     // See if the predecessor is a comparison with the same value.
00788     TerminatorInst *PTI = Pred->getTerminator();
00789     Value *PCV = isValueEqualityComparison(PTI);  // PredCondVal
00790 
00791     if (PCV == CV && SafeToMergeTerminators(TI, PTI)) {
00792       // Figure out which 'cases' to copy from SI to PSI.
00793       std::vector<ValueEqualityComparisonCase> BBCases;
00794       BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
00795 
00796       std::vector<ValueEqualityComparisonCase> PredCases;
00797       BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
00798 
00799       // Based on whether the default edge from PTI goes to BB or not, fill in
00800       // PredCases and PredDefault with the new switch cases we would like to
00801       // build.
00802       SmallVector<BasicBlock*, 8> NewSuccessors;
00803 
00804       // Update the branch weight metadata along the way
00805       SmallVector<uint64_t, 8> Weights;
00806       bool PredHasWeights = HasBranchWeights(PTI);
00807       bool SuccHasWeights = HasBranchWeights(TI);
00808 
00809       if (PredHasWeights) {
00810         GetBranchWeights(PTI, Weights);
00811         // branch-weight metadata is inconsistent here.
00812         if (Weights.size() != 1 + PredCases.size())
00813           PredHasWeights = SuccHasWeights = false;
00814       } else if (SuccHasWeights)
00815         // If there are no predecessor weights but there are successor weights,
00816         // populate Weights with 1, which will later be scaled to the sum of
00817         // successor's weights
00818         Weights.assign(1 + PredCases.size(), 1);
00819 
00820       SmallVector<uint64_t, 8> SuccWeights;
00821       if (SuccHasWeights) {
00822         GetBranchWeights(TI, SuccWeights);
00823         // branch-weight metadata is inconsistent here.
00824         if (SuccWeights.size() != 1 + BBCases.size())
00825           PredHasWeights = SuccHasWeights = false;
00826       } else if (PredHasWeights)
00827         SuccWeights.assign(1 + BBCases.size(), 1);
00828 
00829       if (PredDefault == BB) {
00830         // If this is the default destination from PTI, only the edges in TI
00831         // that don't occur in PTI, or that branch to BB will be activated.
00832         std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
00833         for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
00834           if (PredCases[i].Dest != BB)
00835             PTIHandled.insert(PredCases[i].Value);
00836           else {
00837             // The default destination is BB, we don't need explicit targets.
00838             std::swap(PredCases[i], PredCases.back());
00839 
00840             if (PredHasWeights || SuccHasWeights) {
00841               // Increase weight for the default case.
00842               Weights[0] += Weights[i+1];
00843               std::swap(Weights[i+1], Weights.back());
00844               Weights.pop_back();
00845             }
00846 
00847             PredCases.pop_back();
00848             --i; --e;
00849           }
00850 
00851         // Reconstruct the new switch statement we will be building.
00852         if (PredDefault != BBDefault) {
00853           PredDefault->removePredecessor(Pred);
00854           PredDefault = BBDefault;
00855           NewSuccessors.push_back(BBDefault);
00856         }
00857 
00858         unsigned CasesFromPred = Weights.size();
00859         uint64_t ValidTotalSuccWeight = 0;
00860         for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
00861           if (!PTIHandled.count(BBCases[i].Value) &&
00862               BBCases[i].Dest != BBDefault) {
00863             PredCases.push_back(BBCases[i]);
00864             NewSuccessors.push_back(BBCases[i].Dest);
00865             if (SuccHasWeights || PredHasWeights) {
00866               // The default weight is at index 0, so weight for the ith case
00867               // should be at index i+1. Scale the cases from successor by
00868               // PredDefaultWeight (Weights[0]).
00869               Weights.push_back(Weights[0] * SuccWeights[i+1]);
00870               ValidTotalSuccWeight += SuccWeights[i+1];
00871             }
00872           }
00873 
00874         if (SuccHasWeights || PredHasWeights) {
00875           ValidTotalSuccWeight += SuccWeights[0];
00876           // Scale the cases from predecessor by ValidTotalSuccWeight.
00877           for (unsigned i = 1; i < CasesFromPred; ++i)
00878             Weights[i] *= ValidTotalSuccWeight;
00879           // Scale the default weight by SuccDefaultWeight (SuccWeights[0]).
00880           Weights[0] *= SuccWeights[0];
00881         }
00882       } else {
00883         // If this is not the default destination from PSI, only the edges
00884         // in SI that occur in PSI with a destination of BB will be
00885         // activated.
00886         std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
00887         std::map<ConstantInt*, uint64_t> WeightsForHandled;
00888         for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
00889           if (PredCases[i].Dest == BB) {
00890             PTIHandled.insert(PredCases[i].Value);
00891 
00892             if (PredHasWeights || SuccHasWeights) {
00893               WeightsForHandled[PredCases[i].Value] = Weights[i+1];
00894               std::swap(Weights[i+1], Weights.back());
00895               Weights.pop_back();
00896             }
00897 
00898             std::swap(PredCases[i], PredCases.back());
00899             PredCases.pop_back();
00900             --i; --e;
00901           }
00902 
00903         // Okay, now we know which constants were sent to BB from the
00904         // predecessor.  Figure out where they will all go now.
00905         for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
00906           if (PTIHandled.count(BBCases[i].Value)) {
00907             // If this is one we are capable of getting...
00908             if (PredHasWeights || SuccHasWeights)
00909               Weights.push_back(WeightsForHandled[BBCases[i].Value]);
00910             PredCases.push_back(BBCases[i]);
00911             NewSuccessors.push_back(BBCases[i].Dest);
00912             PTIHandled.erase(BBCases[i].Value);// This constant is taken care of
00913           }
00914 
00915         // If there are any constants vectored to BB that TI doesn't handle,
00916         // they must go to the default destination of TI.
00917         for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I =
00918                                     PTIHandled.begin(),
00919                E = PTIHandled.end(); I != E; ++I) {
00920           if (PredHasWeights || SuccHasWeights)
00921             Weights.push_back(WeightsForHandled[*I]);
00922           PredCases.push_back(ValueEqualityComparisonCase(*I, BBDefault));
00923           NewSuccessors.push_back(BBDefault);
00924         }
00925       }
00926 
00927       // Okay, at this point, we know which new successor Pred will get.  Make
00928       // sure we update the number of entries in the PHI nodes for these
00929       // successors.
00930       for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i)
00931         AddPredecessorToBlock(NewSuccessors[i], Pred, BB);
00932 
00933       Builder.SetInsertPoint(PTI);
00934       // Convert pointer to int before we switch.
00935       if (CV->getType()->isPointerTy()) {
00936         assert(DL && "Cannot switch on pointer without DataLayout");
00937         CV = Builder.CreatePtrToInt(CV, DL->getIntPtrType(CV->getType()),
00938                                     "magicptr");
00939       }
00940 
00941       // Now that the successors are updated, create the new Switch instruction.
00942       SwitchInst *NewSI = Builder.CreateSwitch(CV, PredDefault,
00943                                                PredCases.size());
00944       NewSI->setDebugLoc(PTI->getDebugLoc());
00945       for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
00946         NewSI->addCase(PredCases[i].Value, PredCases[i].Dest);
00947 
00948       if (PredHasWeights || SuccHasWeights) {
00949         // Halve the weights if any of them cannot fit in an uint32_t
00950         FitWeights(Weights);
00951 
00952         SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
00953 
00954         NewSI->setMetadata(LLVMContext::MD_prof,
00955                            MDBuilder(BB->getContext()).
00956                            createBranchWeights(MDWeights));
00957       }
00958 
00959       EraseTerminatorInstAndDCECond(PTI);
00960 
00961       // Okay, last check.  If BB is still a successor of PSI, then we must
00962       // have an infinite loop case.  If so, add an infinitely looping block
00963       // to handle the case to preserve the behavior of the code.
00964       BasicBlock *InfLoopBlock = nullptr;
00965       for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i)
00966         if (NewSI->getSuccessor(i) == BB) {
00967           if (!InfLoopBlock) {
00968             // Insert it at the end of the function, because it's either code,
00969             // or it won't matter if it's hot. :)
00970             InfLoopBlock = BasicBlock::Create(BB->getContext(),
00971                                               "infloop", BB->getParent());
00972             BranchInst::Create(InfLoopBlock, InfLoopBlock);
00973           }
00974           NewSI->setSuccessor(i, InfLoopBlock);
00975         }
00976 
00977       Changed = true;
00978     }
00979   }
00980   return Changed;
00981 }
00982 
00983 // isSafeToHoistInvoke - If we would need to insert a select that uses the
00984 // value of this invoke (comments in HoistThenElseCodeToIf explain why we
00985 // would need to do this), we can't hoist the invoke, as there is nowhere
00986 // to put the select in this case.
00987 static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2,
00988                                 Instruction *I1, Instruction *I2) {
00989   for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
00990     PHINode *PN;
00991     for (BasicBlock::iterator BBI = SI->begin();
00992          (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
00993       Value *BB1V = PN->getIncomingValueForBlock(BB1);
00994       Value *BB2V = PN->getIncomingValueForBlock(BB2);
00995       if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) {
00996         return false;
00997       }
00998     }
00999   }
01000   return true;
01001 }
01002 
01003 /// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and
01004 /// BB2, hoist any common code in the two blocks up into the branch block.  The
01005 /// caller of this function guarantees that BI's block dominates BB1 and BB2.
01006 static bool HoistThenElseCodeToIf(BranchInst *BI, const DataLayout *DL) {
01007   // This does very trivial matching, with limited scanning, to find identical
01008   // instructions in the two blocks.  In particular, we don't want to get into
01009   // O(M*N) situations here where M and N are the sizes of BB1 and BB2.  As
01010   // such, we currently just scan for obviously identical instructions in an
01011   // identical order.
01012   BasicBlock *BB1 = BI->getSuccessor(0);  // The true destination.
01013   BasicBlock *BB2 = BI->getSuccessor(1);  // The false destination
01014 
01015   BasicBlock::iterator BB1_Itr = BB1->begin();
01016   BasicBlock::iterator BB2_Itr = BB2->begin();
01017 
01018   Instruction *I1 = BB1_Itr++, *I2 = BB2_Itr++;
01019   // Skip debug info if it is not identical.
01020   DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
01021   DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
01022   if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
01023     while (isa<DbgInfoIntrinsic>(I1))
01024       I1 = BB1_Itr++;
01025     while (isa<DbgInfoIntrinsic>(I2))
01026       I2 = BB2_Itr++;
01027   }
01028   if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) ||
01029       (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)))
01030     return false;
01031 
01032   BasicBlock *BIParent = BI->getParent();
01033 
01034   bool Changed = false;
01035   do {
01036     // If we are hoisting the terminator instruction, don't move one (making a
01037     // broken BB), instead clone it, and remove BI.
01038     if (isa<TerminatorInst>(I1))
01039       goto HoistTerminator;
01040 
01041     // For a normal instruction, we just move one to right before the branch,
01042     // then replace all uses of the other with the first.  Finally, we remove
01043     // the now redundant second instruction.
01044     BIParent->getInstList().splice(BI, BB1->getInstList(), I1);
01045     if (!I2->use_empty())
01046       I2->replaceAllUsesWith(I1);
01047     I1->intersectOptionalDataWith(I2);
01048     unsigned KnownIDs[] = {
01049       LLVMContext::MD_tbaa,
01050       LLVMContext::MD_range,
01051       LLVMContext::MD_fpmath,
01052       LLVMContext::MD_invariant_load
01053     };
01054     combineMetadata(I1, I2, KnownIDs);
01055     I2->eraseFromParent();
01056     Changed = true;
01057 
01058     I1 = BB1_Itr++;
01059     I2 = BB2_Itr++;
01060     // Skip debug info if it is not identical.
01061     DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
01062     DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
01063     if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
01064       while (isa<DbgInfoIntrinsic>(I1))
01065         I1 = BB1_Itr++;
01066       while (isa<DbgInfoIntrinsic>(I2))
01067         I2 = BB2_Itr++;
01068     }
01069   } while (I1->isIdenticalToWhenDefined(I2));
01070 
01071   return true;
01072 
01073 HoistTerminator:
01074   // It may not be possible to hoist an invoke.
01075   if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))
01076     return Changed;
01077 
01078   for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
01079     PHINode *PN;
01080     for (BasicBlock::iterator BBI = SI->begin();
01081          (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
01082       Value *BB1V = PN->getIncomingValueForBlock(BB1);
01083       Value *BB2V = PN->getIncomingValueForBlock(BB2);
01084       if (BB1V == BB2V)
01085         continue;
01086 
01087       if (isa<ConstantExpr>(BB1V) && !isSafeToSpeculativelyExecute(BB1V, DL))
01088         return Changed;
01089       if (isa<ConstantExpr>(BB2V) && !isSafeToSpeculativelyExecute(BB2V, DL))
01090         return Changed;
01091     }
01092   }
01093 
01094   // Okay, it is safe to hoist the terminator.
01095   Instruction *NT = I1->clone();
01096   BIParent->getInstList().insert(BI, NT);
01097   if (!NT->getType()->isVoidTy()) {
01098     I1->replaceAllUsesWith(NT);
01099     I2->replaceAllUsesWith(NT);
01100     NT->takeName(I1);
01101   }
01102 
01103   IRBuilder<true, NoFolder> Builder(NT);
01104   // Hoisting one of the terminators from our successor is a great thing.
01105   // Unfortunately, the successors of the if/else blocks may have PHI nodes in
01106   // them.  If they do, all PHI entries for BB1/BB2 must agree for all PHI
01107   // nodes, so we insert select instruction to compute the final result.
01108   std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects;
01109   for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
01110     PHINode *PN;
01111     for (BasicBlock::iterator BBI = SI->begin();
01112          (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
01113       Value *BB1V = PN->getIncomingValueForBlock(BB1);
01114       Value *BB2V = PN->getIncomingValueForBlock(BB2);
01115       if (BB1V == BB2V) continue;
01116 
01117       // These values do not agree.  Insert a select instruction before NT
01118       // that determines the right value.
01119       SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
01120       if (!SI)
01121         SI = cast<SelectInst>
01122           (Builder.CreateSelect(BI->getCondition(), BB1V, BB2V,
01123                                 BB1V->getName()+"."+BB2V->getName()));
01124 
01125       // Make the PHI node use the select for all incoming values for BB1/BB2
01126       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
01127         if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2)
01128           PN->setIncomingValue(i, SI);
01129     }
01130   }
01131 
01132   // Update any PHI nodes in our new successors.
01133   for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI)
01134     AddPredecessorToBlock(*SI, BIParent, BB1);
01135 
01136   EraseTerminatorInstAndDCECond(BI);
01137   return true;
01138 }
01139 
01140 /// SinkThenElseCodeToEnd - Given an unconditional branch that goes to BBEnd,
01141 /// check whether BBEnd has only two predecessors and the other predecessor
01142 /// ends with an unconditional branch. If it is true, sink any common code
01143 /// in the two predecessors to BBEnd.
01144 static bool SinkThenElseCodeToEnd(BranchInst *BI1) {
01145   assert(BI1->isUnconditional());
01146   BasicBlock *BB1 = BI1->getParent();
01147   BasicBlock *BBEnd = BI1->getSuccessor(0);
01148 
01149   // Check that BBEnd has two predecessors and the other predecessor ends with
01150   // an unconditional branch.
01151   pred_iterator PI = pred_begin(BBEnd), PE = pred_end(BBEnd);
01152   BasicBlock *Pred0 = *PI++;
01153   if (PI == PE) // Only one predecessor.
01154     return false;
01155   BasicBlock *Pred1 = *PI++;
01156   if (PI != PE) // More than two predecessors.
01157     return false;
01158   BasicBlock *BB2 = (Pred0 == BB1) ? Pred1 : Pred0;
01159   BranchInst *BI2 = dyn_cast<BranchInst>(BB2->getTerminator());
01160   if (!BI2 || !BI2->isUnconditional())
01161     return false;
01162 
01163   // Gather the PHI nodes in BBEnd.
01164   std::map<Value*, std::pair<Value*, PHINode*> > MapValueFromBB1ToBB2;
01165   Instruction *FirstNonPhiInBBEnd = nullptr;
01166   for (BasicBlock::iterator I = BBEnd->begin(), E = BBEnd->end();
01167        I != E; ++I) {
01168     if (PHINode *PN = dyn_cast<PHINode>(I)) {
01169       Value *BB1V = PN->getIncomingValueForBlock(BB1);
01170       Value *BB2V = PN->getIncomingValueForBlock(BB2);
01171       MapValueFromBB1ToBB2[BB1V] = std::make_pair(BB2V, PN);
01172     } else {
01173       FirstNonPhiInBBEnd = &*I;
01174       break;
01175     }
01176   }
01177   if (!FirstNonPhiInBBEnd)
01178     return false;
01179 
01180 
01181   // This does very trivial matching, with limited scanning, to find identical
01182   // instructions in the two blocks.  We scan backward for obviously identical
01183   // instructions in an identical order.
01184   BasicBlock::InstListType::reverse_iterator RI1 = BB1->getInstList().rbegin(),
01185       RE1 = BB1->getInstList().rend(), RI2 = BB2->getInstList().rbegin(),
01186       RE2 = BB2->getInstList().rend();
01187   // Skip debug info.
01188   while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) ++RI1;
01189   if (RI1 == RE1)
01190     return false;
01191   while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) ++RI2;
01192   if (RI2 == RE2)
01193     return false;
01194   // Skip the unconditional branches.
01195   ++RI1;
01196   ++RI2;
01197 
01198   bool Changed = false;
01199   while (RI1 != RE1 && RI2 != RE2) {
01200     // Skip debug info.
01201     while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) ++RI1;
01202     if (RI1 == RE1)
01203       return Changed;
01204     while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) ++RI2;
01205     if (RI2 == RE2)
01206       return Changed;
01207 
01208     Instruction *I1 = &*RI1, *I2 = &*RI2;
01209     // I1 and I2 should have a single use in the same PHI node, and they
01210     // perform the same operation.
01211     // Cannot move control-flow-involving, volatile loads, vaarg, etc.
01212     if (isa<PHINode>(I1) || isa<PHINode>(I2) ||
01213         isa<TerminatorInst>(I1) || isa<TerminatorInst>(I2) ||
01214         isa<LandingPadInst>(I1) || isa<LandingPadInst>(I2) ||
01215         isa<AllocaInst>(I1) || isa<AllocaInst>(I2) ||
01216         I1->mayHaveSideEffects() || I2->mayHaveSideEffects() ||
01217         I1->mayReadOrWriteMemory() || I2->mayReadOrWriteMemory() ||
01218         !I1->hasOneUse() || !I2->hasOneUse() ||
01219         MapValueFromBB1ToBB2.find(I1) == MapValueFromBB1ToBB2.end() ||
01220         MapValueFromBB1ToBB2[I1].first != I2)
01221       return Changed;
01222 
01223     // Check whether we should swap the operands of ICmpInst.
01224     ICmpInst *ICmp1 = dyn_cast<ICmpInst>(I1), *ICmp2 = dyn_cast<ICmpInst>(I2);
01225     bool SwapOpnds = false;
01226     if (ICmp1 && ICmp2 &&
01227         ICmp1->getOperand(0) != ICmp2->getOperand(0) &&
01228         ICmp1->getOperand(1) != ICmp2->getOperand(1) &&
01229         (ICmp1->getOperand(0) == ICmp2->getOperand(1) ||
01230          ICmp1->getOperand(1) == ICmp2->getOperand(0))) {
01231       ICmp2->swapOperands();
01232       SwapOpnds = true;
01233     }
01234     if (!I1->isSameOperationAs(I2)) {
01235       if (SwapOpnds)
01236         ICmp2->swapOperands();
01237       return Changed;
01238     }
01239 
01240     // The operands should be either the same or they need to be generated
01241     // with a PHI node after sinking. We only handle the case where there is
01242     // a single pair of different operands.
01243     Value *DifferentOp1 = nullptr, *DifferentOp2 = nullptr;
01244     unsigned Op1Idx = 0;
01245     for (unsigned I = 0, E = I1->getNumOperands(); I != E; ++I) {
01246       if (I1->getOperand(I) == I2->getOperand(I))
01247         continue;
01248       // Early exit if we have more-than one pair of different operands or
01249       // the different operand is already in MapValueFromBB1ToBB2.
01250       // Early exit if we need a PHI node to replace a constant.
01251       if (DifferentOp1 ||
01252           MapValueFromBB1ToBB2.find(I1->getOperand(I)) !=
01253           MapValueFromBB1ToBB2.end() ||
01254           isa<Constant>(I1->getOperand(I)) ||
01255           isa<Constant>(I2->getOperand(I))) {
01256         // If we can't sink the instructions, undo the swapping.
01257         if (SwapOpnds)
01258           ICmp2->swapOperands();
01259         return Changed;
01260       }
01261       DifferentOp1 = I1->getOperand(I);
01262       Op1Idx = I;
01263       DifferentOp2 = I2->getOperand(I);
01264     }
01265 
01266     // We insert the pair of different operands to MapValueFromBB1ToBB2 and
01267     // remove (I1, I2) from MapValueFromBB1ToBB2.
01268     if (DifferentOp1) {
01269       PHINode *NewPN = PHINode::Create(DifferentOp1->getType(), 2,
01270                                        DifferentOp1->getName() + ".sink",
01271                                        BBEnd->begin());
01272       MapValueFromBB1ToBB2[DifferentOp1] = std::make_pair(DifferentOp2, NewPN);
01273       // I1 should use NewPN instead of DifferentOp1.
01274       I1->setOperand(Op1Idx, NewPN);
01275       NewPN->addIncoming(DifferentOp1, BB1);
01276       NewPN->addIncoming(DifferentOp2, BB2);
01277       DEBUG(dbgs() << "Create PHI node " << *NewPN << "\n";);
01278     }
01279     PHINode *OldPN = MapValueFromBB1ToBB2[I1].second;
01280     MapValueFromBB1ToBB2.erase(I1);
01281 
01282     DEBUG(dbgs() << "SINK common instructions " << *I1 << "\n";);
01283     DEBUG(dbgs() << "                         " << *I2 << "\n";);
01284     // We need to update RE1 and RE2 if we are going to sink the first
01285     // instruction in the basic block down.
01286     bool UpdateRE1 = (I1 == BB1->begin()), UpdateRE2 = (I2 == BB2->begin());
01287     // Sink the instruction.
01288     BBEnd->getInstList().splice(FirstNonPhiInBBEnd, BB1->getInstList(), I1);
01289     if (!OldPN->use_empty())
01290       OldPN->replaceAllUsesWith(I1);
01291     OldPN->eraseFromParent();
01292 
01293     if (!I2->use_empty())
01294       I2->replaceAllUsesWith(I1);
01295     I1->intersectOptionalDataWith(I2);
01296     I2->eraseFromParent();
01297 
01298     if (UpdateRE1)
01299       RE1 = BB1->getInstList().rend();
01300     if (UpdateRE2)
01301       RE2 = BB2->getInstList().rend();
01302     FirstNonPhiInBBEnd = I1;
01303     NumSinkCommons++;
01304     Changed = true;
01305   }
01306   return Changed;
01307 }
01308 
01309 /// \brief Determine if we can hoist sink a sole store instruction out of a
01310 /// conditional block.
01311 ///
01312 /// We are looking for code like the following:
01313 ///   BrBB:
01314 ///     store i32 %add, i32* %arrayidx2
01315 ///     ... // No other stores or function calls (we could be calling a memory
01316 ///     ... // function).
01317 ///     %cmp = icmp ult %x, %y
01318 ///     br i1 %cmp, label %EndBB, label %ThenBB
01319 ///   ThenBB:
01320 ///     store i32 %add5, i32* %arrayidx2
01321 ///     br label EndBB
01322 ///   EndBB:
01323 ///     ...
01324 ///   We are going to transform this into:
01325 ///   BrBB:
01326 ///     store i32 %add, i32* %arrayidx2
01327 ///     ... //
01328 ///     %cmp = icmp ult %x, %y
01329 ///     %add.add5 = select i1 %cmp, i32 %add, %add5
01330 ///     store i32 %add.add5, i32* %arrayidx2
01331 ///     ...
01332 ///
01333 /// \return The pointer to the value of the previous store if the store can be
01334 ///         hoisted into the predecessor block. 0 otherwise.
01335 static Value *isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB,
01336                                      BasicBlock *StoreBB, BasicBlock *EndBB) {
01337   StoreInst *StoreToHoist = dyn_cast<StoreInst>(I);
01338   if (!StoreToHoist)
01339     return nullptr;
01340 
01341   // Volatile or atomic.
01342   if (!StoreToHoist->isSimple())
01343     return nullptr;
01344 
01345   Value *StorePtr = StoreToHoist->getPointerOperand();
01346 
01347   // Look for a store to the same pointer in BrBB.
01348   unsigned MaxNumInstToLookAt = 10;
01349   for (BasicBlock::reverse_iterator RI = BrBB->rbegin(),
01350        RE = BrBB->rend(); RI != RE && (--MaxNumInstToLookAt); ++RI) {
01351     Instruction *CurI = &*RI;
01352 
01353     // Could be calling an instruction that effects memory like free().
01354     if (CurI->mayHaveSideEffects() && !isa<StoreInst>(CurI))
01355       return nullptr;
01356 
01357     StoreInst *SI = dyn_cast<StoreInst>(CurI);
01358     // Found the previous store make sure it stores to the same location.
01359     if (SI && SI->getPointerOperand() == StorePtr)
01360       // Found the previous store, return its value operand.
01361       return SI->getValueOperand();
01362     else if (SI)
01363       return nullptr; // Unknown store.
01364   }
01365 
01366   return nullptr;
01367 }
01368 
01369 /// \brief Speculate a conditional basic block flattening the CFG.
01370 ///
01371 /// Note that this is a very risky transform currently. Speculating
01372 /// instructions like this is most often not desirable. Instead, there is an MI
01373 /// pass which can do it with full awareness of the resource constraints.
01374 /// However, some cases are "obvious" and we should do directly. An example of
01375 /// this is speculating a single, reasonably cheap instruction.
01376 ///
01377 /// There is only one distinct advantage to flattening the CFG at the IR level:
01378 /// it makes very common but simplistic optimizations such as are common in
01379 /// instcombine and the DAG combiner more powerful by removing CFG edges and
01380 /// modeling their effects with easier to reason about SSA value graphs.
01381 ///
01382 ///
01383 /// An illustration of this transform is turning this IR:
01384 /// \code
01385 ///   BB:
01386 ///     %cmp = icmp ult %x, %y
01387 ///     br i1 %cmp, label %EndBB, label %ThenBB
01388 ///   ThenBB:
01389 ///     %sub = sub %x, %y
01390 ///     br label BB2
01391 ///   EndBB:
01392 ///     %phi = phi [ %sub, %ThenBB ], [ 0, %EndBB ]
01393 ///     ...
01394 /// \endcode
01395 ///
01396 /// Into this IR:
01397 /// \code
01398 ///   BB:
01399 ///     %cmp = icmp ult %x, %y
01400 ///     %sub = sub %x, %y
01401 ///     %cond = select i1 %cmp, 0, %sub
01402 ///     ...
01403 /// \endcode
01404 ///
01405 /// \returns true if the conditional block is removed.
01406 static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB,
01407                                    const DataLayout *DL) {
01408   // Be conservative for now. FP select instruction can often be expensive.
01409   Value *BrCond = BI->getCondition();
01410   if (isa<FCmpInst>(BrCond))
01411     return false;
01412 
01413   BasicBlock *BB = BI->getParent();
01414   BasicBlock *EndBB = ThenBB->getTerminator()->getSuccessor(0);
01415 
01416   // If ThenBB is actually on the false edge of the conditional branch, remember
01417   // to swap the select operands later.
01418   bool Invert = false;
01419   if (ThenBB != BI->getSuccessor(0)) {
01420     assert(ThenBB == BI->getSuccessor(1) && "No edge from 'if' block?");
01421     Invert = true;
01422   }
01423   assert(EndBB == BI->getSuccessor(!Invert) && "No edge from to end block");
01424 
01425   // Keep a count of how many times instructions are used within CondBB when
01426   // they are candidates for sinking into CondBB. Specifically:
01427   // - They are defined in BB, and
01428   // - They have no side effects, and
01429   // - All of their uses are in CondBB.
01430   SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
01431 
01432   unsigned SpeculationCost = 0;
01433   Value *SpeculatedStoreValue = nullptr;
01434   StoreInst *SpeculatedStore = nullptr;
01435   for (BasicBlock::iterator BBI = ThenBB->begin(),
01436                             BBE = std::prev(ThenBB->end());
01437        BBI != BBE; ++BBI) {
01438     Instruction *I = BBI;
01439     // Skip debug info.
01440     if (isa<DbgInfoIntrinsic>(I))
01441       continue;
01442 
01443     // Only speculatively execution a single instruction (not counting the
01444     // terminator) for now.
01445     ++SpeculationCost;
01446     if (SpeculationCost > 1)
01447       return false;
01448 
01449     // Don't hoist the instruction if it's unsafe or expensive.
01450     if (!isSafeToSpeculativelyExecute(I, DL) &&
01451         !(HoistCondStores &&
01452           (SpeculatedStoreValue = isSafeToSpeculateStore(I, BB, ThenBB,
01453                                                          EndBB))))
01454       return false;
01455     if (!SpeculatedStoreValue &&
01456         ComputeSpeculationCost(I, DL) > PHINodeFoldingThreshold)
01457       return false;
01458 
01459     // Store the store speculation candidate.
01460     if (SpeculatedStoreValue)
01461       SpeculatedStore = cast<StoreInst>(I);
01462 
01463     // Do not hoist the instruction if any of its operands are defined but not
01464     // used in BB. The transformation will prevent the operand from
01465     // being sunk into the use block.
01466     for (User::op_iterator i = I->op_begin(), e = I->op_end();
01467          i != e; ++i) {
01468       Instruction *OpI = dyn_cast<Instruction>(*i);
01469       if (!OpI || OpI->getParent() != BB ||
01470           OpI->mayHaveSideEffects())
01471         continue; // Not a candidate for sinking.
01472 
01473       ++SinkCandidateUseCounts[OpI];
01474     }
01475   }
01476 
01477   // Consider any sink candidates which are only used in CondBB as costs for
01478   // speculation. Note, while we iterate over a DenseMap here, we are summing
01479   // and so iteration order isn't significant.
01480   for (SmallDenseMap<Instruction *, unsigned, 4>::iterator I =
01481            SinkCandidateUseCounts.begin(), E = SinkCandidateUseCounts.end();
01482        I != E; ++I)
01483     if (I->first->getNumUses() == I->second) {
01484       ++SpeculationCost;
01485       if (SpeculationCost > 1)
01486         return false;
01487     }
01488 
01489   // Check that the PHI nodes can be converted to selects.
01490   bool HaveRewritablePHIs = false;
01491   for (BasicBlock::iterator I = EndBB->begin();
01492        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
01493     Value *OrigV = PN->getIncomingValueForBlock(BB);
01494     Value *ThenV = PN->getIncomingValueForBlock(ThenBB);
01495 
01496     // FIXME: Try to remove some of the duplication with HoistThenElseCodeToIf.
01497     // Skip PHIs which are trivial.
01498     if (ThenV == OrigV)
01499       continue;
01500 
01501     HaveRewritablePHIs = true;
01502     ConstantExpr *OrigCE = dyn_cast<ConstantExpr>(OrigV);
01503     ConstantExpr *ThenCE = dyn_cast<ConstantExpr>(ThenV);
01504     if (!OrigCE && !ThenCE)
01505       continue; // Known safe and cheap.
01506 
01507     if ((ThenCE && !isSafeToSpeculativelyExecute(ThenCE, DL)) ||
01508         (OrigCE && !isSafeToSpeculativelyExecute(OrigCE, DL)))
01509       return false;
01510     unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE, DL) : 0;
01511     unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE, DL) : 0;
01512     if (OrigCost + ThenCost > 2 * PHINodeFoldingThreshold)
01513       return false;
01514 
01515     // Account for the cost of an unfolded ConstantExpr which could end up
01516     // getting expanded into Instructions.
01517     // FIXME: This doesn't account for how many operations are combined in the
01518     // constant expression.
01519     ++SpeculationCost;
01520     if (SpeculationCost > 1)
01521       return false;
01522   }
01523 
01524   // If there are no PHIs to process, bail early. This helps ensure idempotence
01525   // as well.
01526   if (!HaveRewritablePHIs && !(HoistCondStores && SpeculatedStoreValue))
01527     return false;
01528 
01529   // If we get here, we can hoist the instruction and if-convert.
01530   DEBUG(dbgs() << "SPECULATIVELY EXECUTING BB" << *ThenBB << "\n";);
01531 
01532   // Insert a select of the value of the speculated store.
01533   if (SpeculatedStoreValue) {
01534     IRBuilder<true, NoFolder> Builder(BI);
01535     Value *TrueV = SpeculatedStore->getValueOperand();
01536     Value *FalseV = SpeculatedStoreValue;
01537     if (Invert)
01538       std::swap(TrueV, FalseV);
01539     Value *S = Builder.CreateSelect(BrCond, TrueV, FalseV, TrueV->getName() +
01540                                     "." + FalseV->getName());
01541     SpeculatedStore->setOperand(0, S);
01542   }
01543 
01544   // Hoist the instructions.
01545   BB->getInstList().splice(BI, ThenBB->getInstList(), ThenBB->begin(),
01546                            std::prev(ThenBB->end()));
01547 
01548   // Insert selects and rewrite the PHI operands.
01549   IRBuilder<true, NoFolder> Builder(BI);
01550   for (BasicBlock::iterator I = EndBB->begin();
01551        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
01552     unsigned OrigI = PN->getBasicBlockIndex(BB);
01553     unsigned ThenI = PN->getBasicBlockIndex(ThenBB);
01554     Value *OrigV = PN->getIncomingValue(OrigI);
01555     Value *ThenV = PN->getIncomingValue(ThenI);
01556 
01557     // Skip PHIs which are trivial.
01558     if (OrigV == ThenV)
01559       continue;
01560 
01561     // Create a select whose true value is the speculatively executed value and
01562     // false value is the preexisting value. Swap them if the branch
01563     // destinations were inverted.
01564     Value *TrueV = ThenV, *FalseV = OrigV;
01565     if (Invert)
01566       std::swap(TrueV, FalseV);
01567     Value *V = Builder.CreateSelect(BrCond, TrueV, FalseV,
01568                                     TrueV->getName() + "." + FalseV->getName());
01569     PN->setIncomingValue(OrigI, V);
01570     PN->setIncomingValue(ThenI, V);
01571   }
01572 
01573   ++NumSpeculations;
01574   return true;
01575 }
01576 
01577 /// \returns True if this block contains a CallInst with the NoDuplicate
01578 /// attribute.
01579 static bool HasNoDuplicateCall(const BasicBlock *BB) {
01580   for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
01581     const CallInst *CI = dyn_cast<CallInst>(I);
01582     if (!CI)
01583       continue;
01584     if (CI->cannotDuplicate())
01585       return true;
01586   }
01587   return false;
01588 }
01589 
01590 /// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch
01591 /// across this block.
01592 static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) {
01593   BranchInst *BI = cast<BranchInst>(BB->getTerminator());
01594   unsigned Size = 0;
01595 
01596   for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) {
01597     if (isa<DbgInfoIntrinsic>(BBI))
01598       continue;
01599     if (Size > 10) return false;  // Don't clone large BB's.
01600     ++Size;
01601 
01602     // We can only support instructions that do not define values that are
01603     // live outside of the current basic block.
01604     for (User *U : BBI->users()) {
01605       Instruction *UI = cast<Instruction>(U);
01606       if (UI->getParent() != BB || isa<PHINode>(UI)) return false;
01607     }
01608 
01609     // Looks ok, continue checking.
01610   }
01611 
01612   return true;
01613 }
01614 
01615 /// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value
01616 /// that is defined in the same block as the branch and if any PHI entries are
01617 /// constants, thread edges corresponding to that entry to be branches to their
01618 /// ultimate destination.
01619 static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout *DL) {
01620   BasicBlock *BB = BI->getParent();
01621   PHINode *PN = dyn_cast<PHINode>(BI->getCondition());
01622   // NOTE: we currently cannot transform this case if the PHI node is used
01623   // outside of the block.
01624   if (!PN || PN->getParent() != BB || !PN->hasOneUse())
01625     return false;
01626 
01627   // Degenerate case of a single entry PHI.
01628   if (PN->getNumIncomingValues() == 1) {
01629     FoldSingleEntryPHINodes(PN->getParent());
01630     return true;
01631   }
01632 
01633   // Now we know that this block has multiple preds and two succs.
01634   if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false;
01635 
01636   if (HasNoDuplicateCall(BB)) return false;
01637 
01638   // Okay, this is a simple enough basic block.  See if any phi values are
01639   // constants.
01640   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
01641     ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i));
01642     if (!CB || !CB->getType()->isIntegerTy(1)) continue;
01643 
01644     // Okay, we now know that all edges from PredBB should be revectored to
01645     // branch to RealDest.
01646     BasicBlock *PredBB = PN->getIncomingBlock(i);
01647     BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue());
01648 
01649     if (RealDest == BB) continue;  // Skip self loops.
01650     // Skip if the predecessor's terminator is an indirect branch.
01651     if (isa<IndirectBrInst>(PredBB->getTerminator())) continue;
01652 
01653     // The dest block might have PHI nodes, other predecessors and other
01654     // difficult cases.  Instead of being smart about this, just insert a new
01655     // block that jumps to the destination block, effectively splitting
01656     // the edge we are about to create.
01657     BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(),
01658                                             RealDest->getName()+".critedge",
01659                                             RealDest->getParent(), RealDest);
01660     BranchInst::Create(RealDest, EdgeBB);
01661 
01662     // Update PHI nodes.
01663     AddPredecessorToBlock(RealDest, EdgeBB, BB);
01664 
01665     // BB may have instructions that are being threaded over.  Clone these
01666     // instructions into EdgeBB.  We know that there will be no uses of the
01667     // cloned instructions outside of EdgeBB.
01668     BasicBlock::iterator InsertPt = EdgeBB->begin();
01669     DenseMap<Value*, Value*> TranslateMap;  // Track translated values.
01670     for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) {
01671       if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
01672         TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB);
01673         continue;
01674       }
01675       // Clone the instruction.
01676       Instruction *N = BBI->clone();
01677       if (BBI->hasName()) N->setName(BBI->getName()+".c");
01678 
01679       // Update operands due to translation.
01680       for (User::op_iterator i = N->op_begin(), e = N->op_end();
01681            i != e; ++i) {
01682         DenseMap<Value*, Value*>::iterator PI = TranslateMap.find(*i);
01683         if (PI != TranslateMap.end())
01684           *i = PI->second;
01685       }
01686 
01687       // Check for trivial simplification.
01688       if (Value *V = SimplifyInstruction(N, DL)) {
01689         TranslateMap[BBI] = V;
01690         delete N;   // Instruction folded away, don't need actual inst
01691       } else {
01692         // Insert the new instruction into its new home.
01693         EdgeBB->getInstList().insert(InsertPt, N);
01694         if (!BBI->use_empty())
01695           TranslateMap[BBI] = N;
01696       }
01697     }
01698 
01699     // Loop over all of the edges from PredBB to BB, changing them to branch
01700     // to EdgeBB instead.
01701     TerminatorInst *PredBBTI = PredBB->getTerminator();
01702     for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i)
01703       if (PredBBTI->getSuccessor(i) == BB) {
01704         BB->removePredecessor(PredBB);
01705         PredBBTI->setSuccessor(i, EdgeBB);
01706       }
01707 
01708     // Recurse, simplifying any other constants.
01709     return FoldCondBranchOnPHI(BI, DL) | true;
01710   }
01711 
01712   return false;
01713 }
01714 
01715 /// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry
01716 /// PHI node, see if we can eliminate it.
01717 static bool FoldTwoEntryPHINode(PHINode *PN, const DataLayout *DL) {
01718   // Ok, this is a two entry PHI node.  Check to see if this is a simple "if
01719   // statement", which has a very simple dominance structure.  Basically, we
01720   // are trying to find the condition that is being branched on, which
01721   // subsequently causes this merge to happen.  We really want control
01722   // dependence information for this check, but simplifycfg can't keep it up
01723   // to date, and this catches most of the cases we care about anyway.
01724   BasicBlock *BB = PN->getParent();
01725   BasicBlock *IfTrue, *IfFalse;
01726   Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse);
01727   if (!IfCond ||
01728       // Don't bother if the branch will be constant folded trivially.
01729       isa<ConstantInt>(IfCond))
01730     return false;
01731 
01732   // Okay, we found that we can merge this two-entry phi node into a select.
01733   // Doing so would require us to fold *all* two entry phi nodes in this block.
01734   // At some point this becomes non-profitable (particularly if the target
01735   // doesn't support cmov's).  Only do this transformation if there are two or
01736   // fewer PHI nodes in this block.
01737   unsigned NumPhis = 0;
01738   for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I)
01739     if (NumPhis > 2)
01740       return false;
01741 
01742   // Loop over the PHI's seeing if we can promote them all to select
01743   // instructions.  While we are at it, keep track of the instructions
01744   // that need to be moved to the dominating block.
01745   SmallPtrSet<Instruction*, 4> AggressiveInsts;
01746   unsigned MaxCostVal0 = PHINodeFoldingThreshold,
01747            MaxCostVal1 = PHINodeFoldingThreshold;
01748 
01749   for (BasicBlock::iterator II = BB->begin(); isa<PHINode>(II);) {
01750     PHINode *PN = cast<PHINode>(II++);
01751     if (Value *V = SimplifyInstruction(PN, DL)) {
01752       PN->replaceAllUsesWith(V);
01753       PN->eraseFromParent();
01754       continue;
01755     }
01756 
01757     if (!DominatesMergePoint(PN->getIncomingValue(0), BB, &AggressiveInsts,
01758                              MaxCostVal0, DL) ||
01759         !DominatesMergePoint(PN->getIncomingValue(1), BB, &AggressiveInsts,
01760                              MaxCostVal1, DL))
01761       return false;
01762   }
01763 
01764   // If we folded the first phi, PN dangles at this point.  Refresh it.  If
01765   // we ran out of PHIs then we simplified them all.
01766   PN = dyn_cast<PHINode>(BB->begin());
01767   if (!PN) return true;
01768 
01769   // Don't fold i1 branches on PHIs which contain binary operators.  These can
01770   // often be turned into switches and other things.
01771   if (PN->getType()->isIntegerTy(1) &&
01772       (isa<BinaryOperator>(PN->getIncomingValue(0)) ||
01773        isa<BinaryOperator>(PN->getIncomingValue(1)) ||
01774        isa<BinaryOperator>(IfCond)))
01775     return false;
01776 
01777   // If we all PHI nodes are promotable, check to make sure that all
01778   // instructions in the predecessor blocks can be promoted as well.  If
01779   // not, we won't be able to get rid of the control flow, so it's not
01780   // worth promoting to select instructions.
01781   BasicBlock *DomBlock = nullptr;
01782   BasicBlock *IfBlock1 = PN->getIncomingBlock(0);
01783   BasicBlock *IfBlock2 = PN->getIncomingBlock(1);
01784   if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) {
01785     IfBlock1 = nullptr;
01786   } else {
01787     DomBlock = *pred_begin(IfBlock1);
01788     for (BasicBlock::iterator I = IfBlock1->begin();!isa<TerminatorInst>(I);++I)
01789       if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) {
01790         // This is not an aggressive instruction that we can promote.
01791         // Because of this, we won't be able to get rid of the control
01792         // flow, so the xform is not worth it.
01793         return false;
01794       }
01795   }
01796 
01797   if (cast<BranchInst>(IfBlock2->getTerminator())->isConditional()) {
01798     IfBlock2 = nullptr;
01799   } else {
01800     DomBlock = *pred_begin(IfBlock2);
01801     for (BasicBlock::iterator I = IfBlock2->begin();!isa<TerminatorInst>(I);++I)
01802       if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) {
01803         // This is not an aggressive instruction that we can promote.
01804         // Because of this, we won't be able to get rid of the control
01805         // flow, so the xform is not worth it.
01806         return false;
01807       }
01808   }
01809 
01810   DEBUG(dbgs() << "FOUND IF CONDITION!  " << *IfCond << "  T: "
01811                << IfTrue->getName() << "  F: " << IfFalse->getName() << "\n");
01812 
01813   // If we can still promote the PHI nodes after this gauntlet of tests,
01814   // do all of the PHI's now.
01815   Instruction *InsertPt = DomBlock->getTerminator();
01816   IRBuilder<true, NoFolder> Builder(InsertPt);
01817 
01818   // Move all 'aggressive' instructions, which are defined in the
01819   // conditional parts of the if's up to the dominating block.
01820   if (IfBlock1)
01821     DomBlock->getInstList().splice(InsertPt,
01822                                    IfBlock1->getInstList(), IfBlock1->begin(),
01823                                    IfBlock1->getTerminator());
01824   if (IfBlock2)
01825     DomBlock->getInstList().splice(InsertPt,
01826                                    IfBlock2->getInstList(), IfBlock2->begin(),
01827                                    IfBlock2->getTerminator());
01828 
01829   while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
01830     // Change the PHI node into a select instruction.
01831     Value *TrueVal  = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
01832     Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
01833 
01834     SelectInst *NV =
01835       cast<SelectInst>(Builder.CreateSelect(IfCond, TrueVal, FalseVal, ""));
01836     PN->replaceAllUsesWith(NV);
01837     NV->takeName(PN);
01838     PN->eraseFromParent();
01839   }
01840 
01841   // At this point, IfBlock1 and IfBlock2 are both empty, so our if statement
01842   // has been flattened.  Change DomBlock to jump directly to our new block to
01843   // avoid other simplifycfg's kicking in on the diamond.
01844   TerminatorInst *OldTI = DomBlock->getTerminator();
01845   Builder.SetInsertPoint(OldTI);
01846   Builder.CreateBr(BB);
01847   OldTI->eraseFromParent();
01848   return true;
01849 }
01850 
01851 /// SimplifyCondBranchToTwoReturns - If we found a conditional branch that goes
01852 /// to two returning blocks, try to merge them together into one return,
01853 /// introducing a select if the return values disagree.
01854 static bool SimplifyCondBranchToTwoReturns(BranchInst *BI,
01855                                            IRBuilder<> &Builder) {
01856   assert(BI->isConditional() && "Must be a conditional branch");
01857   BasicBlock *TrueSucc = BI->getSuccessor(0);
01858   BasicBlock *FalseSucc = BI->getSuccessor(1);
01859   ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator());
01860   ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator());
01861 
01862   // Check to ensure both blocks are empty (just a return) or optionally empty
01863   // with PHI nodes.  If there are other instructions, merging would cause extra
01864   // computation on one path or the other.
01865   if (!TrueSucc->getFirstNonPHIOrDbg()->isTerminator())
01866     return false;
01867   if (!FalseSucc->getFirstNonPHIOrDbg()->isTerminator())
01868     return false;
01869 
01870   Builder.SetInsertPoint(BI);
01871   // Okay, we found a branch that is going to two return nodes.  If
01872   // there is no return value for this function, just change the
01873   // branch into a return.
01874   if (FalseRet->getNumOperands() == 0) {
01875     TrueSucc->removePredecessor(BI->getParent());
01876     FalseSucc->removePredecessor(BI->getParent());
01877     Builder.CreateRetVoid();
01878     EraseTerminatorInstAndDCECond(BI);
01879     return true;
01880   }
01881 
01882   // Otherwise, figure out what the true and false return values are
01883   // so we can insert a new select instruction.
01884   Value *TrueValue = TrueRet->getReturnValue();
01885   Value *FalseValue = FalseRet->getReturnValue();
01886 
01887   // Unwrap any PHI nodes in the return blocks.
01888   if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue))
01889     if (TVPN->getParent() == TrueSucc)
01890       TrueValue = TVPN->getIncomingValueForBlock(BI->getParent());
01891   if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue))
01892     if (FVPN->getParent() == FalseSucc)
01893       FalseValue = FVPN->getIncomingValueForBlock(BI->getParent());
01894 
01895   // In order for this transformation to be safe, we must be able to
01896   // unconditionally execute both operands to the return.  This is
01897   // normally the case, but we could have a potentially-trapping
01898   // constant expression that prevents this transformation from being
01899   // safe.
01900   if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue))
01901     if (TCV->canTrap())
01902       return false;
01903   if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue))
01904     if (FCV->canTrap())
01905       return false;
01906 
01907   // Okay, we collected all the mapped values and checked them for sanity, and
01908   // defined to really do this transformation.  First, update the CFG.
01909   TrueSucc->removePredecessor(BI->getParent());
01910   FalseSucc->removePredecessor(BI->getParent());
01911 
01912   // Insert select instructions where needed.
01913   Value *BrCond = BI->getCondition();
01914   if (TrueValue) {
01915     // Insert a select if the results differ.
01916     if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) {
01917     } else if (isa<UndefValue>(TrueValue)) {
01918       TrueValue = FalseValue;
01919     } else {
01920       TrueValue = Builder.CreateSelect(BrCond, TrueValue,
01921                                        FalseValue, "retval");
01922     }
01923   }
01924 
01925   Value *RI = !TrueValue ?
01926     Builder.CreateRetVoid() : Builder.CreateRet(TrueValue);
01927 
01928   (void) RI;
01929 
01930   DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:"
01931                << "\n  " << *BI << "NewRet = " << *RI
01932                << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc);
01933 
01934   EraseTerminatorInstAndDCECond(BI);
01935 
01936   return true;
01937 }
01938 
01939 /// ExtractBranchMetadata - Given a conditional BranchInstruction, retrieve the
01940 /// probabilities of the branch taking each edge. Fills in the two APInt
01941 /// parameters and return true, or returns false if no or invalid metadata was
01942 /// found.
01943 static bool ExtractBranchMetadata(BranchInst *BI,
01944                                   uint64_t &ProbTrue, uint64_t &ProbFalse) {
01945   assert(BI->isConditional() &&
01946          "Looking for probabilities on unconditional branch?");
01947   MDNode *ProfileData = BI->getMetadata(LLVMContext::MD_prof);
01948   if (!ProfileData || ProfileData->getNumOperands() != 3) return false;
01949   ConstantInt *CITrue = dyn_cast<ConstantInt>(ProfileData->getOperand(1));
01950   ConstantInt *CIFalse = dyn_cast<ConstantInt>(ProfileData->getOperand(2));
01951   if (!CITrue || !CIFalse) return false;
01952   ProbTrue = CITrue->getValue().getZExtValue();
01953   ProbFalse = CIFalse->getValue().getZExtValue();
01954   return true;
01955 }
01956 
01957 /// checkCSEInPredecessor - Return true if the given instruction is available
01958 /// in its predecessor block. If yes, the instruction will be removed.
01959 ///
01960 static bool checkCSEInPredecessor(Instruction *Inst, BasicBlock *PB) {
01961   if (!isa<BinaryOperator>(Inst) && !isa<CmpInst>(Inst))
01962     return false;
01963   for (BasicBlock::iterator I = PB->begin(), E = PB->end(); I != E; I++) {
01964     Instruction *PBI = &*I;
01965     // Check whether Inst and PBI generate the same value.
01966     if (Inst->isIdenticalTo(PBI)) {
01967       Inst->replaceAllUsesWith(PBI);
01968       Inst->eraseFromParent();
01969       return true;
01970     }
01971   }
01972   return false;
01973 }
01974 
01975 /// FoldBranchToCommonDest - If this basic block is simple enough, and if a
01976 /// predecessor branches to us and one of our successors, fold the block into
01977 /// the predecessor and use logical operations to pick the right destination.
01978 bool llvm::FoldBranchToCommonDest(BranchInst *BI, const DataLayout *DL,
01979                                   unsigned BonusInstThreshold) {
01980   BasicBlock *BB = BI->getParent();
01981 
01982   Instruction *Cond = nullptr;
01983   if (BI->isConditional())
01984     Cond = dyn_cast<Instruction>(BI->getCondition());
01985   else {
01986     // For unconditional branch, check for a simple CFG pattern, where
01987     // BB has a single predecessor and BB's successor is also its predecessor's
01988     // successor. If such pattern exisits, check for CSE between BB and its
01989     // predecessor.
01990     if (BasicBlock *PB = BB->getSinglePredecessor())
01991       if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator()))
01992         if (PBI->isConditional() &&
01993             (BI->getSuccessor(0) == PBI->getSuccessor(0) ||
01994              BI->getSuccessor(0) == PBI->getSuccessor(1))) {
01995           for (BasicBlock::iterator I = BB->begin(), E = BB->end();
01996                I != E; ) {
01997             Instruction *Curr = I++;
01998             if (isa<CmpInst>(Curr)) {
01999               Cond = Curr;
02000               break;
02001             }
02002             // Quit if we can't remove this instruction.
02003             if (!checkCSEInPredecessor(Curr, PB))
02004               return false;
02005           }
02006         }
02007 
02008     if (!Cond)
02009       return false;
02010   }
02011 
02012   if (!Cond || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) ||
02013       Cond->getParent() != BB || !Cond->hasOneUse())
02014   return false;
02015 
02016   // Make sure the instruction after the condition is the cond branch.
02017   BasicBlock::iterator CondIt = Cond; ++CondIt;
02018 
02019   // Ignore dbg intrinsics.
02020   while (isa<DbgInfoIntrinsic>(CondIt)) ++CondIt;
02021 
02022   if (&*CondIt != BI)
02023     return false;
02024 
02025   // Only allow this transformation if computing the condition doesn't involve
02026   // too many instructions and these involved instructions can be executed
02027   // unconditionally. We denote all involved instructions except the condition
02028   // as "bonus instructions", and only allow this transformation when the
02029   // number of the bonus instructions does not exceed a certain threshold.
02030   unsigned NumBonusInsts = 0;
02031   for (auto I = BB->begin(); Cond != I; ++I) {
02032     // Ignore dbg intrinsics.
02033     if (isa<DbgInfoIntrinsic>(I))
02034       continue;
02035     if (!I->hasOneUse() || !isSafeToSpeculativelyExecute(I, DL))
02036       return false;
02037     // I has only one use and can be executed unconditionally.
02038     Instruction *User = dyn_cast<Instruction>(I->user_back());
02039     if (User == nullptr || User->getParent() != BB)
02040       return false;
02041     // I is used in the same BB. Since BI uses Cond and doesn't have more slots
02042     // to use any other instruction, User must be an instruction between next(I)
02043     // and Cond.
02044     ++NumBonusInsts;
02045     // Early exits once we reach the limit.
02046     if (NumBonusInsts > BonusInstThreshold)
02047       return false;
02048   }
02049 
02050   // Cond is known to be a compare or binary operator.  Check to make sure that
02051   // neither operand is a potentially-trapping constant expression.
02052   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0)))
02053     if (CE->canTrap())
02054       return false;
02055   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1)))
02056     if (CE->canTrap())
02057       return false;
02058 
02059   // Finally, don't infinitely unroll conditional loops.
02060   BasicBlock *TrueDest  = BI->getSuccessor(0);
02061   BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : nullptr;
02062   if (TrueDest == BB || FalseDest == BB)
02063     return false;
02064 
02065   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
02066     BasicBlock *PredBlock = *PI;
02067     BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
02068 
02069     // Check that we have two conditional branches.  If there is a PHI node in
02070     // the common successor, verify that the same value flows in from both
02071     // blocks.
02072     SmallVector<PHINode*, 4> PHIs;
02073     if (!PBI || PBI->isUnconditional() ||
02074         (BI->isConditional() &&
02075          !SafeToMergeTerminators(BI, PBI)) ||
02076         (!BI->isConditional() &&
02077          !isProfitableToFoldUnconditional(BI, PBI, Cond, PHIs)))
02078       continue;
02079 
02080     // Determine if the two branches share a common destination.
02081     Instruction::BinaryOps Opc = Instruction::BinaryOpsEnd;
02082     bool InvertPredCond = false;
02083 
02084     if (BI->isConditional()) {
02085       if (PBI->getSuccessor(0) == TrueDest)
02086         Opc = Instruction::Or;
02087       else if (PBI->getSuccessor(1) == FalseDest)
02088         Opc = Instruction::And;
02089       else if (PBI->getSuccessor(0) == FalseDest)
02090         Opc = Instruction::And, InvertPredCond = true;
02091       else if (PBI->getSuccessor(1) == TrueDest)
02092         Opc = Instruction::Or, InvertPredCond = true;
02093       else
02094         continue;
02095     } else {
02096       if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest)
02097         continue;
02098     }
02099 
02100     DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
02101     IRBuilder<> Builder(PBI);
02102 
02103     // If we need to invert the condition in the pred block to match, do so now.
02104     if (InvertPredCond) {
02105       Value *NewCond = PBI->getCondition();
02106 
02107       if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) {
02108         CmpInst *CI = cast<CmpInst>(NewCond);
02109         CI->setPredicate(CI->getInversePredicate());
02110       } else {
02111         NewCond = Builder.CreateNot(NewCond,
02112                                     PBI->getCondition()->getName()+".not");
02113       }
02114 
02115       PBI->setCondition(NewCond);
02116       PBI->swapSuccessors();
02117     }
02118 
02119     // If we have bonus instructions, clone them into the predecessor block.
02120     // Note that there may be mutliple predecessor blocks, so we cannot move
02121     // bonus instructions to a predecessor block.
02122     ValueToValueMapTy VMap; // maps original values to cloned values
02123     // We already make sure Cond is the last instruction before BI. Therefore,
02124     // every instructions before Cond other than DbgInfoIntrinsic are bonus
02125     // instructions.
02126     for (auto BonusInst = BB->begin(); Cond != BonusInst; ++BonusInst) {
02127       if (isa<DbgInfoIntrinsic>(BonusInst))
02128         continue;
02129       Instruction *NewBonusInst = BonusInst->clone();
02130       RemapInstruction(NewBonusInst, VMap,
02131                        RF_NoModuleLevelChanges | RF_IgnoreMissingEntries);
02132       VMap[BonusInst] = NewBonusInst;
02133 
02134       // If we moved a load, we cannot any longer claim any knowledge about
02135       // its potential value. The previous information might have been valid
02136       // only given the branch precondition.
02137       // For an analogous reason, we must also drop all the metadata whose
02138       // semantics we don't understand.
02139       NewBonusInst->dropUnknownMetadata(LLVMContext::MD_dbg);
02140 
02141       PredBlock->getInstList().insert(PBI, NewBonusInst);
02142       NewBonusInst->takeName(BonusInst);
02143       BonusInst->setName(BonusInst->getName() + ".old");
02144     }
02145 
02146     // Clone Cond into the predecessor basic block, and or/and the
02147     // two conditions together.
02148     Instruction *New = Cond->clone();
02149     RemapInstruction(New, VMap,
02150                      RF_NoModuleLevelChanges | RF_IgnoreMissingEntries);
02151     PredBlock->getInstList().insert(PBI, New);
02152     New->takeName(Cond);
02153     Cond->setName(New->getName() + ".old");
02154 
02155     if (BI->isConditional()) {
02156       Instruction *NewCond =
02157         cast<Instruction>(Builder.CreateBinOp(Opc, PBI->getCondition(),
02158                                             New, "or.cond"));
02159       PBI->setCondition(NewCond);
02160 
02161       uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
02162       bool PredHasWeights = ExtractBranchMetadata(PBI, PredTrueWeight,
02163                                                   PredFalseWeight);
02164       bool SuccHasWeights = ExtractBranchMetadata(BI, SuccTrueWeight,
02165                                                   SuccFalseWeight);
02166       SmallVector<uint64_t, 8> NewWeights;
02167 
02168       if (PBI->getSuccessor(0) == BB) {
02169         if (PredHasWeights && SuccHasWeights) {
02170           // PBI: br i1 %x, BB, FalseDest
02171           // BI:  br i1 %y, TrueDest, FalseDest
02172           //TrueWeight is TrueWeight for PBI * TrueWeight for BI.
02173           NewWeights.push_back(PredTrueWeight * SuccTrueWeight);
02174           //FalseWeight is FalseWeight for PBI * TotalWeight for BI +
02175           //               TrueWeight for PBI * FalseWeight for BI.
02176           // We assume that total weights of a BranchInst can fit into 32 bits.
02177           // Therefore, we will not have overflow using 64-bit arithmetic.
02178           NewWeights.push_back(PredFalseWeight * (SuccFalseWeight +
02179                SuccTrueWeight) + PredTrueWeight * SuccFalseWeight);
02180         }
02181         AddPredecessorToBlock(TrueDest, PredBlock, BB);
02182         PBI->setSuccessor(0, TrueDest);
02183       }
02184       if (PBI->getSuccessor(1) == BB) {
02185         if (PredHasWeights && SuccHasWeights) {
02186           // PBI: br i1 %x, TrueDest, BB
02187           // BI:  br i1 %y, TrueDest, FalseDest
02188           //TrueWeight is TrueWeight for PBI * TotalWeight for BI +
02189           //              FalseWeight for PBI * TrueWeight for BI.
02190           NewWeights.push_back(PredTrueWeight * (SuccFalseWeight +
02191               SuccTrueWeight) + PredFalseWeight * SuccTrueWeight);
02192           //FalseWeight is FalseWeight for PBI * FalseWeight for BI.
02193           NewWeights.push_back(PredFalseWeight * SuccFalseWeight);
02194         }
02195         AddPredecessorToBlock(FalseDest, PredBlock, BB);
02196         PBI->setSuccessor(1, FalseDest);
02197       }
02198       if (NewWeights.size() == 2) {
02199         // Halve the weights if any of them cannot fit in an uint32_t
02200         FitWeights(NewWeights);
02201 
02202         SmallVector<uint32_t, 8> MDWeights(NewWeights.begin(),NewWeights.end());
02203         PBI->setMetadata(LLVMContext::MD_prof,
02204                          MDBuilder(BI->getContext()).
02205                          createBranchWeights(MDWeights));
02206       } else
02207         PBI->setMetadata(LLVMContext::MD_prof, nullptr);
02208     } else {
02209       // Update PHI nodes in the common successors.
02210       for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
02211         ConstantInt *PBI_C = cast<ConstantInt>(
02212           PHIs[i]->getIncomingValueForBlock(PBI->getParent()));
02213         assert(PBI_C->getType()->isIntegerTy(1));
02214         Instruction *MergedCond = nullptr;
02215         if (PBI->getSuccessor(0) == TrueDest) {
02216           // Create (PBI_Cond and PBI_C) or (!PBI_Cond and BI_Value)
02217           // PBI_C is true: PBI_Cond or (!PBI_Cond and BI_Value)
02218           //       is false: !PBI_Cond and BI_Value
02219           Instruction *NotCond =
02220             cast<Instruction>(Builder.CreateNot(PBI->getCondition(),
02221                                 "not.cond"));
02222           MergedCond =
02223             cast<Instruction>(Builder.CreateBinOp(Instruction::And,
02224                                 NotCond, New,
02225                                 "and.cond"));
02226           if (PBI_C->isOne())
02227             MergedCond =
02228               cast<Instruction>(Builder.CreateBinOp(Instruction::Or,
02229                                   PBI->getCondition(), MergedCond,
02230                                   "or.cond"));
02231         } else {
02232           // Create (PBI_Cond and BI_Value) or (!PBI_Cond and PBI_C)
02233           // PBI_C is true: (PBI_Cond and BI_Value) or (!PBI_Cond)
02234           //       is false: PBI_Cond and BI_Value
02235           MergedCond =
02236             cast<Instruction>(Builder.CreateBinOp(Instruction::And,
02237                                 PBI->getCondition(), New,
02238                                 "and.cond"));
02239           if (PBI_C->isOne()) {
02240             Instruction *NotCond =
02241               cast<Instruction>(Builder.CreateNot(PBI->getCondition(),
02242                                   "not.cond"));
02243             MergedCond =
02244               cast<Instruction>(Builder.CreateBinOp(Instruction::Or,
02245                                   NotCond, MergedCond,
02246                                   "or.cond"));
02247           }
02248         }
02249         // Update PHI Node.
02250         PHIs[i]->setIncomingValue(PHIs[i]->getBasicBlockIndex(PBI->getParent()),
02251                                   MergedCond);
02252       }
02253       // Change PBI from Conditional to Unconditional.
02254       BranchInst *New_PBI = BranchInst::Create(TrueDest, PBI);
02255       EraseTerminatorInstAndDCECond(PBI);
02256       PBI = New_PBI;
02257     }
02258 
02259     // TODO: If BB is reachable from all paths through PredBlock, then we
02260     // could replace PBI's branch probabilities with BI's.
02261 
02262     // Copy any debug value intrinsics into the end of PredBlock.
02263     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
02264       if (isa<DbgInfoIntrinsic>(*I))
02265         I->clone()->insertBefore(PBI);
02266 
02267     return true;
02268   }
02269   return false;
02270 }
02271 
02272 /// SimplifyCondBranchToCondBranch - If we have a conditional branch as a
02273 /// predecessor of another block, this function tries to simplify it.  We know
02274 /// that PBI and BI are both conditional branches, and BI is in one of the
02275 /// successor blocks of PBI - PBI branches to BI.
02276 static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) {
02277   assert(PBI->isConditional() && BI->isConditional());
02278   BasicBlock *BB = BI->getParent();
02279 
02280   // If this block ends with a branch instruction, and if there is a
02281   // predecessor that ends on a branch of the same condition, make
02282   // this conditional branch redundant.
02283   if (PBI->getCondition() == BI->getCondition() &&
02284       PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
02285     // Okay, the outcome of this conditional branch is statically
02286     // knowable.  If this block had a single pred, handle specially.
02287     if (BB->getSinglePredecessor()) {
02288       // Turn this into a branch on constant.
02289       bool CondIsTrue = PBI->getSuccessor(0) == BB;
02290       BI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()),
02291                                         CondIsTrue));
02292       return true;  // Nuke the branch on constant.
02293     }
02294 
02295     // Otherwise, if there are multiple predecessors, insert a PHI that merges
02296     // in the constant and simplify the block result.  Subsequent passes of
02297     // simplifycfg will thread the block.
02298     if (BlockIsSimpleEnoughToThreadThrough(BB)) {
02299       pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
02300       PHINode *NewPN = PHINode::Create(Type::getInt1Ty(BB->getContext()),
02301                                        std::distance(PB, PE),
02302                                        BI->getCondition()->getName() + ".pr",
02303                                        BB->begin());
02304       // Okay, we're going to insert the PHI node.  Since PBI is not the only
02305       // predecessor, compute the PHI'd conditional value for all of the preds.
02306       // Any predecessor where the condition is not computable we keep symbolic.
02307       for (pred_iterator PI = PB; PI != PE; ++PI) {
02308         BasicBlock *P = *PI;
02309         if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) &&
02310             PBI != BI && PBI->isConditional() &&
02311             PBI->getCondition() == BI->getCondition() &&
02312             PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
02313           bool CondIsTrue = PBI->getSuccessor(0) == BB;
02314           NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()),
02315                                               CondIsTrue), P);
02316         } else {
02317           NewPN->addIncoming(BI->getCondition(), P);
02318         }
02319       }
02320 
02321       BI->setCondition(NewPN);
02322       return true;
02323     }
02324   }
02325 
02326   // If this is a conditional branch in an empty block, and if any
02327   // predecessors are a conditional branch to one of our destinations,
02328   // fold the conditions into logical ops and one cond br.
02329   BasicBlock::iterator BBI = BB->begin();
02330   // Ignore dbg intrinsics.
02331   while (isa<DbgInfoIntrinsic>(BBI))
02332     ++BBI;
02333   if (&*BBI != BI)
02334     return false;
02335 
02336 
02337   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BI->getCondition()))
02338     if (CE->canTrap())
02339       return false;
02340 
02341   int PBIOp, BIOp;
02342   if (PBI->getSuccessor(0) == BI->getSuccessor(0))
02343     PBIOp = BIOp = 0;
02344   else if (PBI->getSuccessor(0) == BI->getSuccessor(1))
02345     PBIOp = 0, BIOp = 1;
02346   else if (PBI->getSuccessor(1) == BI->getSuccessor(0))
02347     PBIOp = 1, BIOp = 0;
02348   else if (PBI->getSuccessor(1) == BI->getSuccessor(1))
02349     PBIOp = BIOp = 1;
02350   else
02351     return false;
02352 
02353   // Check to make sure that the other destination of this branch
02354   // isn't BB itself.  If so, this is an infinite loop that will
02355   // keep getting unwound.
02356   if (PBI->getSuccessor(PBIOp) == BB)
02357     return false;
02358 
02359   // Do not perform this transformation if it would require
02360   // insertion of a large number of select instructions. For targets
02361   // without predication/cmovs, this is a big pessimization.
02362 
02363   // Also do not perform this transformation if any phi node in the common
02364   // destination block can trap when reached by BB or PBB (PR17073). In that
02365   // case, it would be unsafe to hoist the operation into a select instruction.
02366 
02367   BasicBlock *CommonDest = PBI->getSuccessor(PBIOp);
02368   unsigned NumPhis = 0;
02369   for (BasicBlock::iterator II = CommonDest->begin();
02370        isa<PHINode>(II); ++II, ++NumPhis) {
02371     if (NumPhis > 2) // Disable this xform.
02372       return false;
02373 
02374     PHINode *PN = cast<PHINode>(II);
02375     Value *BIV = PN->getIncomingValueForBlock(BB);
02376     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BIV))
02377       if (CE->canTrap())
02378         return false;
02379 
02380     unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent());
02381     Value *PBIV = PN->getIncomingValue(PBBIdx);
02382     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(PBIV))
02383       if (CE->canTrap())
02384         return false;
02385   }
02386 
02387   // Finally, if everything is ok, fold the branches to logical ops.
02388   BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1);
02389 
02390   DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent()
02391                << "AND: " << *BI->getParent());
02392 
02393 
02394   // If OtherDest *is* BB, then BB is a basic block with a single conditional
02395   // branch in it, where one edge (OtherDest) goes back to itself but the other
02396   // exits.  We don't *know* that the program avoids the infinite loop
02397   // (even though that seems likely).  If we do this xform naively, we'll end up
02398   // recursively unpeeling the loop.  Since we know that (after the xform is
02399   // done) that the block *is* infinite if reached, we just make it an obviously
02400   // infinite loop with no cond branch.
02401   if (OtherDest == BB) {
02402     // Insert it at the end of the function, because it's either code,
02403     // or it won't matter if it's hot. :)
02404     BasicBlock *InfLoopBlock = BasicBlock::Create(BB->getContext(),
02405                                                   "infloop", BB->getParent());
02406     BranchInst::Create(InfLoopBlock, InfLoopBlock);
02407     OtherDest = InfLoopBlock;
02408   }
02409 
02410   DEBUG(dbgs() << *PBI->getParent()->getParent());
02411 
02412   // BI may have other predecessors.  Because of this, we leave
02413   // it alone, but modify PBI.
02414 
02415   // Make sure we get to CommonDest on True&True directions.
02416   Value *PBICond = PBI->getCondition();
02417   IRBuilder<true, NoFolder> Builder(PBI);
02418   if (PBIOp)
02419     PBICond = Builder.CreateNot(PBICond, PBICond->getName()+".not");
02420 
02421   Value *BICond = BI->getCondition();
02422   if (BIOp)
02423     BICond = Builder.CreateNot(BICond, BICond->getName()+".not");
02424 
02425   // Merge the conditions.
02426   Value *Cond = Builder.CreateOr(PBICond, BICond, "brmerge");
02427 
02428   // Modify PBI to branch on the new condition to the new dests.
02429   PBI->setCondition(Cond);
02430   PBI->setSuccessor(0, CommonDest);
02431   PBI->setSuccessor(1, OtherDest);
02432 
02433   // Update branch weight for PBI.
02434   uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
02435   bool PredHasWeights = ExtractBranchMetadata(PBI, PredTrueWeight,
02436                                               PredFalseWeight);
02437   bool SuccHasWeights = ExtractBranchMetadata(BI, SuccTrueWeight,
02438                                               SuccFalseWeight);
02439   if (PredHasWeights && SuccHasWeights) {
02440     uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
02441     uint64_t PredOther = PBIOp ?PredTrueWeight : PredFalseWeight;
02442     uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
02443     uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
02444     // The weight to CommonDest should be PredCommon * SuccTotal +
02445     //                                    PredOther * SuccCommon.
02446     // The weight to OtherDest should be PredOther * SuccOther.
02447     SmallVector<uint64_t, 2> NewWeights;
02448     NewWeights.push_back(PredCommon * (SuccCommon + SuccOther) +
02449                          PredOther * SuccCommon);
02450     NewWeights.push_back(PredOther * SuccOther);
02451     // Halve the weights if any of them cannot fit in an uint32_t
02452     FitWeights(NewWeights);
02453 
02454     SmallVector<uint32_t, 2> MDWeights(NewWeights.begin(),NewWeights.end());
02455     PBI->setMetadata(LLVMContext::MD_prof,
02456                      MDBuilder(BI->getContext()).
02457                      createBranchWeights(MDWeights));
02458   }
02459 
02460   // OtherDest may have phi nodes.  If so, add an entry from PBI's
02461   // block that are identical to the entries for BI's block.
02462   AddPredecessorToBlock(OtherDest, PBI->getParent(), BB);
02463 
02464   // We know that the CommonDest already had an edge from PBI to
02465   // it.  If it has PHIs though, the PHIs may have different
02466   // entries for BB and PBI's BB.  If so, insert a select to make
02467   // them agree.
02468   PHINode *PN;
02469   for (BasicBlock::iterator II = CommonDest->begin();
02470        (PN = dyn_cast<PHINode>(II)); ++II) {
02471     Value *BIV = PN->getIncomingValueForBlock(BB);
02472     unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent());
02473     Value *PBIV = PN->getIncomingValue(PBBIdx);
02474     if (BIV != PBIV) {
02475       // Insert a select in PBI to pick the right value.
02476       Value *NV = cast<SelectInst>
02477         (Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName()+".mux"));
02478       PN->setIncomingValue(PBBIdx, NV);
02479     }
02480   }
02481 
02482   DEBUG(dbgs() << "INTO: " << *PBI->getParent());
02483   DEBUG(dbgs() << *PBI->getParent()->getParent());
02484 
02485   // This basic block is probably dead.  We know it has at least
02486   // one fewer predecessor.
02487   return true;
02488 }
02489 
02490 // SimplifyTerminatorOnSelect - Simplifies a terminator by replacing it with a
02491 // branch to TrueBB if Cond is true or to FalseBB if Cond is false.
02492 // Takes care of updating the successors and removing the old terminator.
02493 // Also makes sure not to introduce new successors by assuming that edges to
02494 // non-successor TrueBBs and FalseBBs aren't reachable.
02495 static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond,
02496                                        BasicBlock *TrueBB, BasicBlock *FalseBB,
02497                                        uint32_t TrueWeight,
02498                                        uint32_t FalseWeight){
02499   // Remove any superfluous successor edges from the CFG.
02500   // First, figure out which successors to preserve.
02501   // If TrueBB and FalseBB are equal, only try to preserve one copy of that
02502   // successor.
02503   BasicBlock *KeepEdge1 = TrueBB;
02504   BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : nullptr;
02505 
02506   // Then remove the rest.
02507   for (unsigned I = 0, E = OldTerm->getNumSuccessors(); I != E; ++I) {
02508     BasicBlock *Succ = OldTerm->getSuccessor(I);
02509     // Make sure only to keep exactly one copy of each edge.
02510     if (Succ == KeepEdge1)
02511       KeepEdge1 = nullptr;
02512     else if (Succ == KeepEdge2)
02513       KeepEdge2 = nullptr;
02514     else
02515       Succ->removePredecessor(OldTerm->getParent());
02516   }
02517 
02518   IRBuilder<> Builder(OldTerm);
02519   Builder.SetCurrentDebugLocation(OldTerm->getDebugLoc());
02520 
02521   // Insert an appropriate new terminator.
02522   if (!KeepEdge1 && !KeepEdge2) {
02523     if (TrueBB == FalseBB)
02524       // We were only looking for one successor, and it was present.
02525       // Create an unconditional branch to it.
02526       Builder.CreateBr(TrueBB);
02527     else {
02528       // We found both of the successors we were looking for.
02529       // Create a conditional branch sharing the condition of the select.
02530       BranchInst *NewBI = Builder.CreateCondBr(Cond, TrueBB, FalseBB);
02531       if (TrueWeight != FalseWeight)
02532         NewBI->setMetadata(LLVMContext::MD_prof,
02533                            MDBuilder(OldTerm->getContext()).
02534                            createBranchWeights(TrueWeight, FalseWeight));
02535     }
02536   } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
02537     // Neither of the selected blocks were successors, so this
02538     // terminator must be unreachable.
02539     new UnreachableInst(OldTerm->getContext(), OldTerm);
02540   } else {
02541     // One of the selected values was a successor, but the other wasn't.
02542     // Insert an unconditional branch to the one that was found;
02543     // the edge to the one that wasn't must be unreachable.
02544     if (!KeepEdge1)
02545       // Only TrueBB was found.
02546       Builder.CreateBr(TrueBB);
02547     else
02548       // Only FalseBB was found.
02549       Builder.CreateBr(FalseBB);
02550   }
02551 
02552   EraseTerminatorInstAndDCECond(OldTerm);
02553   return true;
02554 }
02555 
02556 // SimplifySwitchOnSelect - Replaces
02557 //   (switch (select cond, X, Y)) on constant X, Y
02558 // with a branch - conditional if X and Y lead to distinct BBs,
02559 // unconditional otherwise.
02560 static bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select) {
02561   // Check for constant integer values in the select.
02562   ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue());
02563   ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue());
02564   if (!TrueVal || !FalseVal)
02565     return false;
02566 
02567   // Find the relevant condition and destinations.
02568   Value *Condition = Select->getCondition();
02569   BasicBlock *TrueBB = SI->findCaseValue(TrueVal).getCaseSuccessor();
02570   BasicBlock *FalseBB = SI->findCaseValue(FalseVal).getCaseSuccessor();
02571 
02572   // Get weight for TrueBB and FalseBB.
02573   uint32_t TrueWeight = 0, FalseWeight = 0;
02574   SmallVector<uint64_t, 8> Weights;
02575   bool HasWeights = HasBranchWeights(SI);
02576   if (HasWeights) {
02577     GetBranchWeights(SI, Weights);
02578     if (Weights.size() == 1 + SI->getNumCases()) {
02579       TrueWeight = (uint32_t)Weights[SI->findCaseValue(TrueVal).
02580                                      getSuccessorIndex()];
02581       FalseWeight = (uint32_t)Weights[SI->findCaseValue(FalseVal).
02582                                       getSuccessorIndex()];
02583     }
02584   }
02585 
02586   // Perform the actual simplification.
02587   return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB,
02588                                     TrueWeight, FalseWeight);
02589 }
02590 
02591 // SimplifyIndirectBrOnSelect - Replaces
02592 //   (indirectbr (select cond, blockaddress(@fn, BlockA),
02593 //                             blockaddress(@fn, BlockB)))
02594 // with
02595 //   (br cond, BlockA, BlockB).
02596 static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) {
02597   // Check that both operands of the select are block addresses.
02598   BlockAddress *TBA = dyn_cast<BlockAddress>(SI->getTrueValue());
02599   BlockAddress *FBA = dyn_cast<BlockAddress>(SI->getFalseValue());
02600   if (!TBA || !FBA)
02601     return false;
02602 
02603   // Extract the actual blocks.
02604   BasicBlock *TrueBB = TBA->getBasicBlock();
02605   BasicBlock *FalseBB = FBA->getBasicBlock();
02606 
02607   // Perform the actual simplification.
02608   return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB,
02609                                     0, 0);
02610 }
02611 
02612 /// TryToSimplifyUncondBranchWithICmpInIt - This is called when we find an icmp
02613 /// instruction (a seteq/setne with a constant) as the only instruction in a
02614 /// block that ends with an uncond branch.  We are looking for a very specific
02615 /// pattern that occurs when "A == 1 || A == 2 || A == 3" gets simplified.  In
02616 /// this case, we merge the first two "or's of icmp" into a switch, but then the
02617 /// default value goes to an uncond block with a seteq in it, we get something
02618 /// like:
02619 ///
02620 ///   switch i8 %A, label %DEFAULT [ i8 1, label %end    i8 2, label %end ]
02621 /// DEFAULT:
02622 ///   %tmp = icmp eq i8 %A, 92
02623 ///   br label %end
02624 /// end:
02625 ///   ... = phi i1 [ true, %entry ], [ %tmp, %DEFAULT ], [ true, %entry ]
02626 ///
02627 /// We prefer to split the edge to 'end' so that there is a true/false entry to
02628 /// the PHI, merging the third icmp into the switch.
02629 static bool TryToSimplifyUncondBranchWithICmpInIt(
02630     ICmpInst *ICI, IRBuilder<> &Builder, const TargetTransformInfo &TTI,
02631     unsigned BonusInstThreshold, const DataLayout *DL, AssumptionTracker *AT) {
02632   BasicBlock *BB = ICI->getParent();
02633 
02634   // If the block has any PHIs in it or the icmp has multiple uses, it is too
02635   // complex.
02636   if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) return false;
02637 
02638   Value *V = ICI->getOperand(0);
02639   ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1));
02640 
02641   // The pattern we're looking for is where our only predecessor is a switch on
02642   // 'V' and this block is the default case for the switch.  In this case we can
02643   // fold the compared value into the switch to simplify things.
02644   BasicBlock *Pred = BB->getSinglePredecessor();
02645   if (!Pred || !isa<SwitchInst>(Pred->getTerminator())) return false;
02646 
02647   SwitchInst *SI = cast<SwitchInst>(Pred->getTerminator());
02648   if (SI->getCondition() != V)
02649     return false;
02650 
02651   // If BB is reachable on a non-default case, then we simply know the value of
02652   // V in this block.  Substitute it and constant fold the icmp instruction
02653   // away.
02654   if (SI->getDefaultDest() != BB) {
02655     ConstantInt *VVal = SI->findCaseDest(BB);
02656     assert(VVal && "Should have a unique destination value");
02657     ICI->setOperand(0, VVal);
02658 
02659     if (Value *V = SimplifyInstruction(ICI, DL)) {
02660       ICI->replaceAllUsesWith(V);
02661       ICI->eraseFromParent();
02662     }
02663     // BB is now empty, so it is likely to simplify away.
02664     return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
02665   }
02666 
02667   // Ok, the block is reachable from the default dest.  If the constant we're
02668   // comparing exists in one of the other edges, then we can constant fold ICI
02669   // and zap it.
02670   if (SI->findCaseValue(Cst) != SI->case_default()) {
02671     Value *V;
02672     if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
02673       V = ConstantInt::getFalse(BB->getContext());
02674     else
02675       V = ConstantInt::getTrue(BB->getContext());
02676 
02677     ICI->replaceAllUsesWith(V);
02678     ICI->eraseFromParent();
02679     // BB is now empty, so it is likely to simplify away.
02680     return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
02681   }
02682 
02683   // The use of the icmp has to be in the 'end' block, by the only PHI node in
02684   // the block.
02685   BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0);
02686   PHINode *PHIUse = dyn_cast<PHINode>(ICI->user_back());
02687   if (PHIUse == nullptr || PHIUse != &SuccBlock->front() ||
02688       isa<PHINode>(++BasicBlock::iterator(PHIUse)))
02689     return false;
02690 
02691   // If the icmp is a SETEQ, then the default dest gets false, the new edge gets
02692   // true in the PHI.
02693   Constant *DefaultCst = ConstantInt::getTrue(BB->getContext());
02694   Constant *NewCst     = ConstantInt::getFalse(BB->getContext());
02695 
02696   if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
02697     std::swap(DefaultCst, NewCst);
02698 
02699   // Replace ICI (which is used by the PHI for the default value) with true or
02700   // false depending on if it is EQ or NE.
02701   ICI->replaceAllUsesWith(DefaultCst);
02702   ICI->eraseFromParent();
02703 
02704   // Okay, the switch goes to this block on a default value.  Add an edge from
02705   // the switch to the merge point on the compared value.
02706   BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "switch.edge",
02707                                          BB->getParent(), BB);
02708   SmallVector<uint64_t, 8> Weights;
02709   bool HasWeights = HasBranchWeights(SI);
02710   if (HasWeights) {
02711     GetBranchWeights(SI, Weights);
02712     if (Weights.size() == 1 + SI->getNumCases()) {
02713       // Split weight for default case to case for "Cst".
02714       Weights[0] = (Weights[0]+1) >> 1;
02715       Weights.push_back(Weights[0]);
02716 
02717       SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
02718       SI->setMetadata(LLVMContext::MD_prof,
02719                       MDBuilder(SI->getContext()).
02720                       createBranchWeights(MDWeights));
02721     }
02722   }
02723   SI->addCase(Cst, NewBB);
02724 
02725   // NewBB branches to the phi block, add the uncond branch and the phi entry.
02726   Builder.SetInsertPoint(NewBB);
02727   Builder.SetCurrentDebugLocation(SI->getDebugLoc());
02728   Builder.CreateBr(SuccBlock);
02729   PHIUse->addIncoming(NewCst, NewBB);
02730   return true;
02731 }
02732 
02733 /// SimplifyBranchOnICmpChain - The specified branch is a conditional branch.
02734 /// Check to see if it is branching on an or/and chain of icmp instructions, and
02735 /// fold it into a switch instruction if so.
02736 static bool SimplifyBranchOnICmpChain(BranchInst *BI, const DataLayout *DL,
02737                                       IRBuilder<> &Builder) {
02738   Instruction *Cond = dyn_cast<Instruction>(BI->getCondition());
02739   if (!Cond) return false;
02740 
02741 
02742   // Change br (X == 0 | X == 1), T, F into a switch instruction.
02743   // If this is a bunch of seteq's or'd together, or if it's a bunch of
02744   // 'setne's and'ed together, collect them.
02745   Value *CompVal = nullptr;
02746   std::vector<ConstantInt*> Values;
02747   bool TrueWhenEqual = true;
02748   Value *ExtraCase = nullptr;
02749   unsigned UsedICmps = 0;
02750 
02751   if (Cond->getOpcode() == Instruction::Or) {
02752     CompVal = GatherConstantCompares(Cond, Values, ExtraCase, DL, true,
02753                                      UsedICmps);
02754   } else if (Cond->getOpcode() == Instruction::And) {
02755     CompVal = GatherConstantCompares(Cond, Values, ExtraCase, DL, false,
02756                                      UsedICmps);
02757     TrueWhenEqual = false;
02758   }
02759 
02760   // If we didn't have a multiply compared value, fail.
02761   if (!CompVal) return false;
02762 
02763   // Avoid turning single icmps into a switch.
02764   if (UsedICmps <= 1)
02765     return false;
02766 
02767   // There might be duplicate constants in the list, which the switch
02768   // instruction can't handle, remove them now.
02769   array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate);
02770   Values.erase(std::unique(Values.begin(), Values.end()), Values.end());
02771 
02772   // If Extra was used, we require at least two switch values to do the
02773   // transformation.  A switch with one value is just an cond branch.
02774   if (ExtraCase && Values.size() < 2) return false;
02775 
02776   // TODO: Preserve branch weight metadata, similarly to how
02777   // FoldValueComparisonIntoPredecessors preserves it.
02778 
02779   // Figure out which block is which destination.
02780   BasicBlock *DefaultBB = BI->getSuccessor(1);
02781   BasicBlock *EdgeBB    = BI->getSuccessor(0);
02782   if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB);
02783 
02784   BasicBlock *BB = BI->getParent();
02785 
02786   DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size()
02787                << " cases into SWITCH.  BB is:\n" << *BB);
02788 
02789   // If there are any extra values that couldn't be folded into the switch
02790   // then we evaluate them with an explicit branch first.  Split the block
02791   // right before the condbr to handle it.
02792   if (ExtraCase) {
02793     BasicBlock *NewBB = BB->splitBasicBlock(BI, "switch.early.test");
02794     // Remove the uncond branch added to the old block.
02795     TerminatorInst *OldTI = BB->getTerminator();
02796     Builder.SetInsertPoint(OldTI);
02797 
02798     if (TrueWhenEqual)
02799       Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB);
02800     else
02801       Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB);
02802 
02803     OldTI->eraseFromParent();
02804 
02805     // If there are PHI nodes in EdgeBB, then we need to add a new entry to them
02806     // for the edge we just added.
02807     AddPredecessorToBlock(EdgeBB, BB, NewBB);
02808 
02809     DEBUG(dbgs() << "  ** 'icmp' chain unhandled condition: " << *ExtraCase
02810           << "\nEXTRABB = " << *BB);
02811     BB = NewBB;
02812   }
02813 
02814   Builder.SetInsertPoint(BI);
02815   // Convert pointer to int before we switch.
02816   if (CompVal->getType()->isPointerTy()) {
02817     assert(DL && "Cannot switch on pointer without DataLayout");
02818     CompVal = Builder.CreatePtrToInt(CompVal,
02819                                      DL->getIntPtrType(CompVal->getType()),
02820                                      "magicptr");
02821   }
02822 
02823   // Create the new switch instruction now.
02824   SwitchInst *New = Builder.CreateSwitch(CompVal, DefaultBB, Values.size());
02825 
02826   // Add all of the 'cases' to the switch instruction.
02827   for (unsigned i = 0, e = Values.size(); i != e; ++i)
02828     New->addCase(Values[i], EdgeBB);
02829 
02830   // We added edges from PI to the EdgeBB.  As such, if there were any
02831   // PHI nodes in EdgeBB, they need entries to be added corresponding to
02832   // the number of edges added.
02833   for (BasicBlock::iterator BBI = EdgeBB->begin();
02834        isa<PHINode>(BBI); ++BBI) {
02835     PHINode *PN = cast<PHINode>(BBI);
02836     Value *InVal = PN->getIncomingValueForBlock(BB);
02837     for (unsigned i = 0, e = Values.size()-1; i != e; ++i)
02838       PN->addIncoming(InVal, BB);
02839   }
02840 
02841   // Erase the old branch instruction.
02842   EraseTerminatorInstAndDCECond(BI);
02843 
02844   DEBUG(dbgs() << "  ** 'icmp' chain result is:\n" << *BB << '\n');
02845   return true;
02846 }
02847 
02848 bool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) {
02849   // If this is a trivial landing pad that just continues unwinding the caught
02850   // exception then zap the landing pad, turning its invokes into calls.
02851   BasicBlock *BB = RI->getParent();
02852   LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI());
02853   if (RI->getValue() != LPInst)
02854     // Not a landing pad, or the resume is not unwinding the exception that
02855     // caused control to branch here.
02856     return false;
02857 
02858   // Check that there are no other instructions except for debug intrinsics.
02859   BasicBlock::iterator I = LPInst, E = RI;
02860   while (++I != E)
02861     if (!isa<DbgInfoIntrinsic>(I))
02862       return false;
02863 
02864   // Turn all invokes that unwind here into calls and delete the basic block.
02865   bool InvokeRequiresTableEntry = false;
02866   bool Changed = false;
02867   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) {
02868     InvokeInst *II = cast<InvokeInst>((*PI++)->getTerminator());
02869 
02870     if (II->hasFnAttr(Attribute::UWTable)) {
02871       // Don't remove an `invoke' instruction if the ABI requires an entry into
02872       // the table.
02873       InvokeRequiresTableEntry = true;
02874       continue;
02875     }
02876 
02877     SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
02878 
02879     // Insert a call instruction before the invoke.
02880     CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II);
02881     Call->takeName(II);
02882     Call->setCallingConv(II->getCallingConv());
02883     Call->setAttributes(II->getAttributes());
02884     Call->setDebugLoc(II->getDebugLoc());
02885 
02886     // Anything that used the value produced by the invoke instruction now uses
02887     // the value produced by the call instruction.  Note that we do this even
02888     // for void functions and calls with no uses so that the callgraph edge is
02889     // updated.
02890     II->replaceAllUsesWith(Call);
02891     BB->removePredecessor(II->getParent());
02892 
02893     // Insert a branch to the normal destination right before the invoke.
02894     BranchInst::Create(II->getNormalDest(), II);
02895 
02896     // Finally, delete the invoke instruction!
02897     II->eraseFromParent();
02898     Changed = true;
02899   }
02900 
02901   if (!InvokeRequiresTableEntry)
02902     // The landingpad is now unreachable.  Zap it.
02903     BB->eraseFromParent();
02904 
02905   return Changed;
02906 }
02907 
02908 bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) {
02909   BasicBlock *BB = RI->getParent();
02910   if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false;
02911 
02912   // Find predecessors that end with branches.
02913   SmallVector<BasicBlock*, 8> UncondBranchPreds;
02914   SmallVector<BranchInst*, 8> CondBranchPreds;
02915   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
02916     BasicBlock *P = *PI;
02917     TerminatorInst *PTI = P->getTerminator();
02918     if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) {
02919       if (BI->isUnconditional())
02920         UncondBranchPreds.push_back(P);
02921       else
02922         CondBranchPreds.push_back(BI);
02923     }
02924   }
02925 
02926   // If we found some, do the transformation!
02927   if (!UncondBranchPreds.empty() && DupRet) {
02928     while (!UncondBranchPreds.empty()) {
02929       BasicBlock *Pred = UncondBranchPreds.pop_back_val();
02930       DEBUG(dbgs() << "FOLDING: " << *BB
02931             << "INTO UNCOND BRANCH PRED: " << *Pred);
02932       (void)FoldReturnIntoUncondBranch(RI, BB, Pred);
02933     }
02934 
02935     // If we eliminated all predecessors of the block, delete the block now.
02936     if (pred_begin(BB) == pred_end(BB))
02937       // We know there are no successors, so just nuke the block.
02938       BB->eraseFromParent();
02939 
02940     return true;
02941   }
02942 
02943   // Check out all of the conditional branches going to this return
02944   // instruction.  If any of them just select between returns, change the
02945   // branch itself into a select/return pair.
02946   while (!CondBranchPreds.empty()) {
02947     BranchInst *BI = CondBranchPreds.pop_back_val();
02948 
02949     // Check to see if the non-BB successor is also a return block.
02950     if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) &&
02951         isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) &&
02952         SimplifyCondBranchToTwoReturns(BI, Builder))
02953       return true;
02954   }
02955   return false;
02956 }
02957 
02958 bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) {
02959   BasicBlock *BB = UI->getParent();
02960 
02961   bool Changed = false;
02962 
02963   // If there are any instructions immediately before the unreachable that can
02964   // be removed, do so.
02965   while (UI != BB->begin()) {
02966     BasicBlock::iterator BBI = UI;
02967     --BBI;
02968     // Do not delete instructions that can have side effects which might cause
02969     // the unreachable to not be reachable; specifically, calls and volatile
02970     // operations may have this effect.
02971     if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) break;
02972 
02973     if (BBI->mayHaveSideEffects()) {
02974       if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
02975         if (SI->isVolatile())
02976           break;
02977       } else if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
02978         if (LI->isVolatile())
02979           break;
02980       } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(BBI)) {
02981         if (RMWI->isVolatile())
02982           break;
02983       } else if (AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(BBI)) {
02984         if (CXI->isVolatile())
02985           break;
02986       } else if (!isa<FenceInst>(BBI) && !isa<VAArgInst>(BBI) &&
02987                  !isa<LandingPadInst>(BBI)) {
02988         break;
02989       }
02990       // Note that deleting LandingPad's here is in fact okay, although it
02991       // involves a bit of subtle reasoning. If this inst is a LandingPad,
02992       // all the predecessors of this block will be the unwind edges of Invokes,
02993       // and we can therefore guarantee this block will be erased.
02994     }
02995 
02996     // Delete this instruction (any uses are guaranteed to be dead)
02997     if (!BBI->use_empty())
02998       BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
02999     BBI->eraseFromParent();
03000     Changed = true;
03001   }
03002 
03003   // If the unreachable instruction is the first in the block, take a gander
03004   // at all of the predecessors of this instruction, and simplify them.
03005   if (&BB->front() != UI) return Changed;
03006 
03007   SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB));
03008   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
03009     TerminatorInst *TI = Preds[i]->getTerminator();
03010     IRBuilder<> Builder(TI);
03011     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
03012       if (BI->isUnconditional()) {
03013         if (BI->getSuccessor(0) == BB) {
03014           new UnreachableInst(TI->getContext(), TI);
03015           TI->eraseFromParent();
03016           Changed = true;
03017         }
03018       } else {
03019         if (BI->getSuccessor(0) == BB) {
03020           Builder.CreateBr(BI->getSuccessor(1));
03021           EraseTerminatorInstAndDCECond(BI);
03022         } else if (BI->getSuccessor(1) == BB) {
03023           Builder.CreateBr(BI->getSuccessor(0));
03024           EraseTerminatorInstAndDCECond(BI);
03025           Changed = true;
03026         }
03027       }
03028     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
03029       for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
03030            i != e; ++i)
03031         if (i.getCaseSuccessor() == BB) {
03032           BB->removePredecessor(SI->getParent());
03033           SI->removeCase(i);
03034           --i; --e;
03035           Changed = true;
03036         }
03037       // If the default value is unreachable, figure out the most popular
03038       // destination and make it the default.
03039       if (SI->getDefaultDest() == BB) {
03040         std::map<BasicBlock*, std::pair<unsigned, unsigned> > Popularity;
03041         for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
03042              i != e; ++i) {
03043           std::pair<unsigned, unsigned> &entry =
03044               Popularity[i.getCaseSuccessor()];
03045           if (entry.first == 0) {
03046             entry.first = 1;
03047             entry.second = i.getCaseIndex();
03048           } else {
03049             entry.first++;
03050           }
03051         }
03052 
03053         // Find the most popular block.
03054         unsigned MaxPop = 0;
03055         unsigned MaxIndex = 0;
03056         BasicBlock *MaxBlock = nullptr;
03057         for (std::map<BasicBlock*, std::pair<unsigned, unsigned> >::iterator
03058              I = Popularity.begin(), E = Popularity.end(); I != E; ++I) {
03059           if (I->second.first > MaxPop ||
03060               (I->second.first == MaxPop && MaxIndex > I->second.second)) {
03061             MaxPop = I->second.first;
03062             MaxIndex = I->second.second;
03063             MaxBlock = I->first;
03064           }
03065         }
03066         if (MaxBlock) {
03067           // Make this the new default, allowing us to delete any explicit
03068           // edges to it.
03069           SI->setDefaultDest(MaxBlock);
03070           Changed = true;
03071 
03072           // If MaxBlock has phinodes in it, remove MaxPop-1 entries from
03073           // it.
03074           if (isa<PHINode>(MaxBlock->begin()))
03075             for (unsigned i = 0; i != MaxPop-1; ++i)
03076               MaxBlock->removePredecessor(SI->getParent());
03077 
03078           for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
03079                i != e; ++i)
03080             if (i.getCaseSuccessor() == MaxBlock) {
03081               SI->removeCase(i);
03082               --i; --e;
03083             }
03084         }
03085       }
03086     } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
03087       if (II->getUnwindDest() == BB) {
03088         // Convert the invoke to a call instruction.  This would be a good
03089         // place to note that the call does not throw though.
03090         BranchInst *BI = Builder.CreateBr(II->getNormalDest());
03091         II->removeFromParent();   // Take out of symbol table
03092 
03093         // Insert the call now...
03094         SmallVector<Value*, 8> Args(II->op_begin(), II->op_end()-3);
03095         Builder.SetInsertPoint(BI);
03096         CallInst *CI = Builder.CreateCall(II->getCalledValue(),
03097                                           Args, II->getName());
03098         CI->setCallingConv(II->getCallingConv());
03099         CI->setAttributes(II->getAttributes());
03100         // If the invoke produced a value, the call does now instead.
03101         II->replaceAllUsesWith(CI);
03102         delete II;
03103         Changed = true;
03104       }
03105     }
03106   }
03107 
03108   // If this block is now dead, remove it.
03109   if (pred_begin(BB) == pred_end(BB) &&
03110       BB != &BB->getParent()->getEntryBlock()) {
03111     // We know there are no successors, so just nuke the block.
03112     BB->eraseFromParent();
03113     return true;
03114   }
03115 
03116   return Changed;
03117 }
03118 
03119 /// TurnSwitchRangeIntoICmp - Turns a switch with that contains only a
03120 /// integer range comparison into a sub, an icmp and a branch.
03121 static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) {
03122   assert(SI->getNumCases() > 1 && "Degenerate switch?");
03123 
03124   // Make sure all cases point to the same destination and gather the values.
03125   SmallVector<ConstantInt *, 16> Cases;
03126   SwitchInst::CaseIt I = SI->case_begin();
03127   Cases.push_back(I.getCaseValue());
03128   SwitchInst::CaseIt PrevI = I++;
03129   for (SwitchInst::CaseIt E = SI->case_end(); I != E; PrevI = I++) {
03130     if (PrevI.getCaseSuccessor() != I.getCaseSuccessor())
03131       return false;
03132     Cases.push_back(I.getCaseValue());
03133   }
03134   assert(Cases.size() == SI->getNumCases() && "Not all cases gathered");
03135 
03136   // Sort the case values, then check if they form a range we can transform.
03137   array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate);
03138   for (unsigned I = 1, E = Cases.size(); I != E; ++I) {
03139     if (Cases[I-1]->getValue() != Cases[I]->getValue()+1)
03140       return false;
03141   }
03142 
03143   Constant *Offset = ConstantExpr::getNeg(Cases.back());
03144   Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases());
03145 
03146   Value *Sub = SI->getCondition();
03147   if (!Offset->isNullValue())
03148     Sub = Builder.CreateAdd(Sub, Offset, Sub->getName()+".off");
03149   Value *Cmp;
03150   // If NumCases overflowed, then all possible values jump to the successor.
03151   if (NumCases->isNullValue() && SI->getNumCases() != 0)
03152     Cmp = ConstantInt::getTrue(SI->getContext());
03153   else
03154     Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch");
03155   BranchInst *NewBI = Builder.CreateCondBr(
03156       Cmp, SI->case_begin().getCaseSuccessor(), SI->getDefaultDest());
03157 
03158   // Update weight for the newly-created conditional branch.
03159   SmallVector<uint64_t, 8> Weights;
03160   bool HasWeights = HasBranchWeights(SI);
03161   if (HasWeights) {
03162     GetBranchWeights(SI, Weights);
03163     if (Weights.size() == 1 + SI->getNumCases()) {
03164       // Combine all weights for the cases to be the true weight of NewBI.
03165       // We assume that the sum of all weights for a Terminator can fit into 32
03166       // bits.
03167       uint32_t NewTrueWeight = 0;
03168       for (unsigned I = 1, E = Weights.size(); I != E; ++I)
03169         NewTrueWeight += (uint32_t)Weights[I];
03170       NewBI->setMetadata(LLVMContext::MD_prof,
03171                          MDBuilder(SI->getContext()).
03172                          createBranchWeights(NewTrueWeight,
03173                                              (uint32_t)Weights[0]));
03174     }
03175   }
03176 
03177   // Prune obsolete incoming values off the successor's PHI nodes.
03178   for (BasicBlock::iterator BBI = SI->case_begin().getCaseSuccessor()->begin();
03179        isa<PHINode>(BBI); ++BBI) {
03180     for (unsigned I = 0, E = SI->getNumCases()-1; I != E; ++I)
03181       cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
03182   }
03183   SI->eraseFromParent();
03184 
03185   return true;
03186 }
03187 
03188 /// EliminateDeadSwitchCases - Compute masked bits for the condition of a switch
03189 /// and use it to remove dead cases.
03190 static bool EliminateDeadSwitchCases(SwitchInst *SI, const DataLayout *DL,
03191                                      AssumptionTracker *AT) {
03192   Value *Cond = SI->getCondition();
03193   unsigned Bits = Cond->getType()->getIntegerBitWidth();
03194   APInt KnownZero(Bits, 0), KnownOne(Bits, 0);
03195   computeKnownBits(Cond, KnownZero, KnownOne, DL, 0, AT, SI);
03196 
03197   // Gather dead cases.
03198   SmallVector<ConstantInt*, 8> DeadCases;
03199   for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) {
03200     if ((I.getCaseValue()->getValue() & KnownZero) != 0 ||
03201         (I.getCaseValue()->getValue() & KnownOne) != KnownOne) {
03202       DeadCases.push_back(I.getCaseValue());
03203       DEBUG(dbgs() << "SimplifyCFG: switch case '"
03204                    << I.getCaseValue() << "' is dead.\n");
03205     }
03206   }
03207 
03208   SmallVector<uint64_t, 8> Weights;
03209   bool HasWeight = HasBranchWeights(SI);
03210   if (HasWeight) {
03211     GetBranchWeights(SI, Weights);
03212     HasWeight = (Weights.size() == 1 + SI->getNumCases());
03213   }
03214 
03215   // Remove dead cases from the switch.
03216   for (unsigned I = 0, E = DeadCases.size(); I != E; ++I) {
03217     SwitchInst::CaseIt Case = SI->findCaseValue(DeadCases[I]);
03218     assert(Case != SI->case_default() &&
03219            "Case was not found. Probably mistake in DeadCases forming.");
03220     if (HasWeight) {
03221       std::swap(Weights[Case.getCaseIndex()+1], Weights.back());
03222       Weights.pop_back();
03223     }
03224 
03225     // Prune unused values from PHI nodes.
03226     Case.getCaseSuccessor()->removePredecessor(SI->getParent());
03227     SI->removeCase(Case);
03228   }
03229   if (HasWeight && Weights.size() >= 2) {
03230     SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
03231     SI->setMetadata(LLVMContext::MD_prof,
03232                     MDBuilder(SI->getParent()->getContext()).
03233                     createBranchWeights(MDWeights));
03234   }
03235 
03236   return !DeadCases.empty();
03237 }
03238 
03239 /// FindPHIForConditionForwarding - If BB would be eligible for simplification
03240 /// by TryToSimplifyUncondBranchFromEmptyBlock (i.e. it is empty and terminated
03241 /// by an unconditional branch), look at the phi node for BB in the successor
03242 /// block and see if the incoming value is equal to CaseValue. If so, return
03243 /// the phi node, and set PhiIndex to BB's index in the phi node.
03244 static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue,
03245                                               BasicBlock *BB,
03246                                               int *PhiIndex) {
03247   if (BB->getFirstNonPHIOrDbg() != BB->getTerminator())
03248     return nullptr; // BB must be empty to be a candidate for simplification.
03249   if (!BB->getSinglePredecessor())
03250     return nullptr; // BB must be dominated by the switch.
03251 
03252   BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator());
03253   if (!Branch || !Branch->isUnconditional())
03254     return nullptr; // Terminator must be unconditional branch.
03255 
03256   BasicBlock *Succ = Branch->getSuccessor(0);
03257 
03258   BasicBlock::iterator I = Succ->begin();
03259   while (PHINode *PHI = dyn_cast<PHINode>(I++)) {
03260     int Idx = PHI->getBasicBlockIndex(BB);
03261     assert(Idx >= 0 && "PHI has no entry for predecessor?");
03262 
03263     Value *InValue = PHI->getIncomingValue(Idx);
03264     if (InValue != CaseValue) continue;
03265 
03266     *PhiIndex = Idx;
03267     return PHI;
03268   }
03269 
03270   return nullptr;
03271 }
03272 
03273 /// ForwardSwitchConditionToPHI - Try to forward the condition of a switch
03274 /// instruction to a phi node dominated by the switch, if that would mean that
03275 /// some of the destination blocks of the switch can be folded away.
03276 /// Returns true if a change is made.
03277 static bool ForwardSwitchConditionToPHI(SwitchInst *SI) {
03278   typedef DenseMap<PHINode*, SmallVector<int,4> > ForwardingNodesMap;
03279   ForwardingNodesMap ForwardingNodes;
03280 
03281   for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) {
03282     ConstantInt *CaseValue = I.getCaseValue();
03283     BasicBlock *CaseDest = I.getCaseSuccessor();
03284 
03285     int PhiIndex;
03286     PHINode *PHI = FindPHIForConditionForwarding(CaseValue, CaseDest,
03287                                                  &PhiIndex);
03288     if (!PHI) continue;
03289 
03290     ForwardingNodes[PHI].push_back(PhiIndex);
03291   }
03292 
03293   bool Changed = false;
03294 
03295   for (ForwardingNodesMap::iterator I = ForwardingNodes.begin(),
03296        E = ForwardingNodes.end(); I != E; ++I) {
03297     PHINode *Phi = I->first;
03298     SmallVectorImpl<int> &Indexes = I->second;
03299 
03300     if (Indexes.size() < 2) continue;
03301 
03302     for (size_t I = 0, E = Indexes.size(); I != E; ++I)
03303       Phi->setIncomingValue(Indexes[I], SI->getCondition());
03304     Changed = true;
03305   }
03306 
03307   return Changed;
03308 }
03309 
03310 /// ValidLookupTableConstant - Return true if the backend will be able to handle
03311 /// initializing an array of constants like C.
03312 static bool ValidLookupTableConstant(Constant *C) {
03313   if (C->isThreadDependent())
03314     return false;
03315   if (C->isDLLImportDependent())
03316     return false;
03317 
03318   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
03319     return CE->isGEPWithNoNotionalOverIndexing();
03320 
03321   return isa<ConstantFP>(C) ||
03322       isa<ConstantInt>(C) ||
03323       isa<ConstantPointerNull>(C) ||
03324       isa<GlobalValue>(C) ||
03325       isa<UndefValue>(C);
03326 }
03327 
03328 /// LookupConstant - If V is a Constant, return it. Otherwise, try to look up
03329 /// its constant value in ConstantPool, returning 0 if it's not there.
03330 static Constant *LookupConstant(Value *V,
03331                          const SmallDenseMap<Value*, Constant*>& ConstantPool) {
03332   if (Constant *C = dyn_cast<Constant>(V))
03333     return C;
03334   return ConstantPool.lookup(V);
03335 }
03336 
03337 /// ConstantFold - Try to fold instruction I into a constant. This works for
03338 /// simple instructions such as binary operations where both operands are
03339 /// constant or can be replaced by constants from the ConstantPool. Returns the
03340 /// resulting constant on success, 0 otherwise.
03341 static Constant *
03342 ConstantFold(Instruction *I,
03343              const SmallDenseMap<Value *, Constant *> &ConstantPool,
03344              const DataLayout *DL) {
03345   if (SelectInst *Select = dyn_cast<SelectInst>(I)) {
03346     Constant *A = LookupConstant(Select->getCondition(), ConstantPool);
03347     if (!A)
03348       return nullptr;
03349     if (A->isAllOnesValue())
03350       return LookupConstant(Select->getTrueValue(), ConstantPool);
03351     if (A->isNullValue())
03352       return LookupConstant(Select->getFalseValue(), ConstantPool);
03353     return nullptr;
03354   }
03355 
03356   SmallVector<Constant *, 4> COps;
03357   for (unsigned N = 0, E = I->getNumOperands(); N != E; ++N) {
03358     if (Constant *A = LookupConstant(I->getOperand(N), ConstantPool))
03359       COps.push_back(A);
03360     else
03361       return nullptr;
03362   }
03363 
03364   if (CmpInst *Cmp = dyn_cast<CmpInst>(I))
03365     return ConstantFoldCompareInstOperands(Cmp->getPredicate(), COps[0],
03366                                            COps[1], DL);
03367 
03368   return ConstantFoldInstOperands(I->getOpcode(), I->getType(), COps, DL);
03369 }
03370 
03371 /// GetCaseResults - Try to determine the resulting constant values in phi nodes
03372 /// at the common destination basic block, *CommonDest, for one of the case
03373 /// destionations CaseDest corresponding to value CaseVal (0 for the default
03374 /// case), of a switch instruction SI.
03375 static bool
03376 GetCaseResults(SwitchInst *SI,
03377                ConstantInt *CaseVal,
03378                BasicBlock *CaseDest,
03379                BasicBlock **CommonDest,
03380                SmallVectorImpl<std::pair<PHINode *, Constant *> > &Res,
03381                const DataLayout *DL) {
03382   // The block from which we enter the common destination.
03383   BasicBlock *Pred = SI->getParent();
03384 
03385   // If CaseDest is empty except for some side-effect free instructions through
03386   // which we can constant-propagate the CaseVal, continue to its successor.
03387   SmallDenseMap<Value*, Constant*> ConstantPool;
03388   ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
03389   for (BasicBlock::iterator I = CaseDest->begin(), E = CaseDest->end(); I != E;
03390        ++I) {
03391     if (TerminatorInst *T = dyn_cast<TerminatorInst>(I)) {
03392       // If the terminator is a simple branch, continue to the next block.
03393       if (T->getNumSuccessors() != 1)
03394         return false;
03395       Pred = CaseDest;
03396       CaseDest = T->getSuccessor(0);
03397     } else if (isa<DbgInfoIntrinsic>(I)) {
03398       // Skip debug intrinsic.
03399       continue;
03400     } else if (Constant *C = ConstantFold(I, ConstantPool, DL)) {
03401       // Instruction is side-effect free and constant.
03402       ConstantPool.insert(std::make_pair(I, C));
03403     } else {
03404       break;
03405     }
03406   }
03407 
03408   // If we did not have a CommonDest before, use the current one.
03409   if (!*CommonDest)
03410     *CommonDest = CaseDest;
03411   // If the destination isn't the common one, abort.
03412   if (CaseDest != *CommonDest)
03413     return false;
03414 
03415   // Get the values for this case from phi nodes in the destination block.
03416   BasicBlock::iterator I = (*CommonDest)->begin();
03417   while (PHINode *PHI = dyn_cast<PHINode>(I++)) {
03418     int Idx = PHI->getBasicBlockIndex(Pred);
03419     if (Idx == -1)
03420       continue;
03421 
03422     Constant *ConstVal = LookupConstant(PHI->getIncomingValue(Idx),
03423                                         ConstantPool);
03424     if (!ConstVal)
03425       return false;
03426 
03427     // Note: If the constant comes from constant-propagating the case value
03428     // through the CaseDest basic block, it will be safe to remove the
03429     // instructions in that block. They cannot be used (except in the phi nodes
03430     // we visit) outside CaseDest, because that block does not dominate its
03431     // successor. If it did, we would not be in this phi node.
03432 
03433     // Be conservative about which kinds of constants we support.
03434     if (!ValidLookupTableConstant(ConstVal))
03435       return false;
03436 
03437     Res.push_back(std::make_pair(PHI, ConstVal));
03438   }
03439 
03440   return Res.size() > 0;
03441 }
03442 
03443 namespace {
03444   /// SwitchLookupTable - This class represents a lookup table that can be used
03445   /// to replace a switch.
03446   class SwitchLookupTable {
03447   public:
03448     /// SwitchLookupTable - Create a lookup table to use as a switch replacement
03449     /// with the contents of Values, using DefaultValue to fill any holes in the
03450     /// table.
03451     SwitchLookupTable(Module &M,
03452                       uint64_t TableSize,
03453                       ConstantInt *Offset,
03454              const SmallVectorImpl<std::pair<ConstantInt*, Constant*> >& Values,
03455                       Constant *DefaultValue,
03456                       const DataLayout *DL);
03457 
03458     /// BuildLookup - Build instructions with Builder to retrieve the value at
03459     /// the position given by Index in the lookup table.
03460     Value *BuildLookup(Value *Index, IRBuilder<> &Builder);
03461 
03462     /// WouldFitInRegister - Return true if a table with TableSize elements of
03463     /// type ElementType would fit in a target-legal register.
03464     static bool WouldFitInRegister(const DataLayout *DL,
03465                                    uint64_t TableSize,
03466                                    const Type *ElementType);
03467 
03468   private:
03469     // Depending on the contents of the table, it can be represented in
03470     // different ways.
03471     enum {
03472       // For tables where each element contains the same value, we just have to
03473       // store that single value and return it for each lookup.
03474       SingleValueKind,
03475 
03476       // For small tables with integer elements, we can pack them into a bitmap
03477       // that fits into a target-legal register. Values are retrieved by
03478       // shift and mask operations.
03479       BitMapKind,
03480 
03481       // The table is stored as an array of values. Values are retrieved by load
03482       // instructions from the table.
03483       ArrayKind
03484     } Kind;
03485 
03486     // For SingleValueKind, this is the single value.
03487     Constant *SingleValue;
03488 
03489     // For BitMapKind, this is the bitmap.
03490     ConstantInt *BitMap;
03491     IntegerType *BitMapElementTy;
03492 
03493     // For ArrayKind, this is the array.
03494     GlobalVariable *Array;
03495   };
03496 }
03497 
03498 SwitchLookupTable::SwitchLookupTable(Module &M,
03499                                      uint64_t TableSize,
03500                                      ConstantInt *Offset,
03501              const SmallVectorImpl<std::pair<ConstantInt*, Constant*> >& Values,
03502                                      Constant *DefaultValue,
03503                                      const DataLayout *DL)
03504     : SingleValue(nullptr), BitMap(nullptr), BitMapElementTy(nullptr),
03505       Array(nullptr) {
03506   assert(Values.size() && "Can't build lookup table without values!");
03507   assert(TableSize >= Values.size() && "Can't fit values in table!");
03508 
03509   // If all values in the table are equal, this is that value.
03510   SingleValue = Values.begin()->second;
03511 
03512   Type *ValueType = Values.begin()->second->getType();
03513 
03514   // Build up the table contents.
03515   SmallVector<Constant*, 64> TableContents(TableSize);
03516   for (size_t I = 0, E = Values.size(); I != E; ++I) {
03517     ConstantInt *CaseVal = Values[I].first;
03518     Constant *CaseRes = Values[I].second;
03519     assert(CaseRes->getType() == ValueType);
03520 
03521     uint64_t Idx = (CaseVal->getValue() - Offset->getValue())
03522                    .getLimitedValue();
03523     TableContents[Idx] = CaseRes;
03524 
03525     if (CaseRes != SingleValue)
03526       SingleValue = nullptr;
03527   }
03528 
03529   // Fill in any holes in the table with the default result.
03530   if (Values.size() < TableSize) {
03531     assert(DefaultValue &&
03532            "Need a default value to fill the lookup table holes.");
03533     assert(DefaultValue->getType() == ValueType);
03534     for (uint64_t I = 0; I < TableSize; ++I) {
03535       if (!TableContents[I])
03536         TableContents[I] = DefaultValue;
03537     }
03538 
03539     if (DefaultValue != SingleValue)
03540       SingleValue = nullptr;
03541   }
03542 
03543   // If each element in the table contains the same value, we only need to store
03544   // that single value.
03545   if (SingleValue) {
03546     Kind = SingleValueKind;
03547     return;
03548   }
03549 
03550   // If the type is integer and the table fits in a register, build a bitmap.
03551   if (WouldFitInRegister(DL, TableSize, ValueType)) {
03552     IntegerType *IT = cast<IntegerType>(ValueType);
03553     APInt TableInt(TableSize * IT->getBitWidth(), 0);
03554     for (uint64_t I = TableSize; I > 0; --I) {
03555       TableInt <<= IT->getBitWidth();
03556       // Insert values into the bitmap. Undef values are set to zero.
03557       if (!isa<UndefValue>(TableContents[I - 1])) {
03558         ConstantInt *Val = cast<ConstantInt>(TableContents[I - 1]);
03559         TableInt |= Val->getValue().zext(TableInt.getBitWidth());
03560       }
03561     }
03562     BitMap = ConstantInt::get(M.getContext(), TableInt);
03563     BitMapElementTy = IT;
03564     Kind = BitMapKind;
03565     ++NumBitMaps;
03566     return;
03567   }
03568 
03569   // Store the table in an array.
03570   ArrayType *ArrayTy = ArrayType::get(ValueType, TableSize);
03571   Constant *Initializer = ConstantArray::get(ArrayTy, TableContents);
03572 
03573   Array = new GlobalVariable(M, ArrayTy, /*constant=*/ true,
03574                              GlobalVariable::PrivateLinkage,
03575                              Initializer,
03576                              "switch.table");
03577   Array->setUnnamedAddr(true);
03578   Kind = ArrayKind;
03579 }
03580 
03581 Value *SwitchLookupTable::BuildLookup(Value *Index, IRBuilder<> &Builder) {
03582   switch (Kind) {
03583     case SingleValueKind:
03584       return SingleValue;
03585     case BitMapKind: {
03586       // Type of the bitmap (e.g. i59).
03587       IntegerType *MapTy = BitMap->getType();
03588 
03589       // Cast Index to the same type as the bitmap.
03590       // Note: The Index is <= the number of elements in the table, so
03591       // truncating it to the width of the bitmask is safe.
03592       Value *ShiftAmt = Builder.CreateZExtOrTrunc(Index, MapTy, "switch.cast");
03593 
03594       // Multiply the shift amount by the element width.
03595       ShiftAmt = Builder.CreateMul(ShiftAmt,
03596                       ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
03597                                    "switch.shiftamt");
03598 
03599       // Shift down.
03600       Value *DownShifted = Builder.CreateLShr(BitMap, ShiftAmt,
03601                                               "switch.downshift");
03602       // Mask off.
03603       return Builder.CreateTrunc(DownShifted, BitMapElementTy,
03604                                  "switch.masked");
03605     }
03606     case ArrayKind: {
03607       // Make sure the table index will not overflow when treated as signed.
03608       IntegerType *IT = cast<IntegerType>(Index->getType());
03609       uint64_t TableSize = Array->getInitializer()->getType()
03610                                 ->getArrayNumElements();
03611       if (TableSize > (1ULL << (IT->getBitWidth() - 1)))
03612         Index = Builder.CreateZExt(Index,
03613                                    IntegerType::get(IT->getContext(),
03614                                                     IT->getBitWidth() + 1),
03615                                    "switch.tableidx.zext");
03616 
03617       Value *GEPIndices[] = { Builder.getInt32(0), Index };
03618       Value *GEP = Builder.CreateInBoundsGEP(Array, GEPIndices,
03619                                              "switch.gep");
03620       return Builder.CreateLoad(GEP, "switch.load");
03621     }
03622   }
03623   llvm_unreachable("Unknown lookup table kind!");
03624 }
03625 
03626 bool SwitchLookupTable::WouldFitInRegister(const DataLayout *DL,
03627                                            uint64_t TableSize,
03628                                            const Type *ElementType) {
03629   if (!DL)
03630     return false;
03631   const IntegerType *IT = dyn_cast<IntegerType>(ElementType);
03632   if (!IT)
03633     return false;
03634   // FIXME: If the type is wider than it needs to be, e.g. i8 but all values
03635   // are <= 15, we could try to narrow the type.
03636 
03637   // Avoid overflow, fitsInLegalInteger uses unsigned int for the width.
03638   if (TableSize >= UINT_MAX/IT->getBitWidth())
03639     return false;
03640   return DL->fitsInLegalInteger(TableSize * IT->getBitWidth());
03641 }
03642 
03643 /// ShouldBuildLookupTable - Determine whether a lookup table should be built
03644 /// for this switch, based on the number of cases, size of the table and the
03645 /// types of the results.
03646 static bool ShouldBuildLookupTable(SwitchInst *SI,
03647                                    uint64_t TableSize,
03648                                    const TargetTransformInfo &TTI,
03649                                    const DataLayout *DL,
03650                             const SmallDenseMap<PHINode*, Type*>& ResultTypes) {
03651   if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10)
03652     return false; // TableSize overflowed, or mul below might overflow.
03653 
03654   bool AllTablesFitInRegister = true;
03655   bool HasIllegalType = false;
03656   for (SmallDenseMap<PHINode*, Type*>::const_iterator I = ResultTypes.begin(),
03657        E = ResultTypes.end(); I != E; ++I) {
03658     Type *Ty = I->second;
03659 
03660     // Saturate this flag to true.
03661     HasIllegalType = HasIllegalType || !TTI.isTypeLegal(Ty);
03662 
03663     // Saturate this flag to false.
03664     AllTablesFitInRegister = AllTablesFitInRegister &&
03665       SwitchLookupTable::WouldFitInRegister(DL, TableSize, Ty);
03666 
03667     // If both flags saturate, we're done. NOTE: This *only* works with
03668     // saturating flags, and all flags have to saturate first due to the
03669     // non-deterministic behavior of iterating over a dense map.
03670     if (HasIllegalType && !AllTablesFitInRegister)
03671       break;
03672   }
03673 
03674   // If each table would fit in a register, we should build it anyway.
03675   if (AllTablesFitInRegister)
03676     return true;
03677 
03678   // Don't build a table that doesn't fit in-register if it has illegal types.
03679   if (HasIllegalType)
03680     return false;
03681 
03682   // The table density should be at least 40%. This is the same criterion as for
03683   // jump tables, see SelectionDAGBuilder::handleJTSwitchCase.
03684   // FIXME: Find the best cut-off.
03685   return SI->getNumCases() * 10 >= TableSize * 4;
03686 }
03687 
03688 /// SwitchToLookupTable - If the switch is only used to initialize one or more
03689 /// phi nodes in a common successor block with different constant values,
03690 /// replace the switch with lookup tables.
03691 static bool SwitchToLookupTable(SwitchInst *SI,
03692                                 IRBuilder<> &Builder,
03693                                 const TargetTransformInfo &TTI,
03694                                 const DataLayout* DL) {
03695   assert(SI->getNumCases() > 1 && "Degenerate switch?");
03696 
03697   // Only build lookup table when we have a target that supports it.
03698   if (!TTI.shouldBuildLookupTables())
03699     return false;
03700 
03701   // FIXME: If the switch is too sparse for a lookup table, perhaps we could
03702   // split off a dense part and build a lookup table for that.
03703 
03704   // FIXME: This creates arrays of GEPs to constant strings, which means each
03705   // GEP needs a runtime relocation in PIC code. We should just build one big
03706   // string and lookup indices into that.
03707 
03708   // Ignore switches with less than three cases. Lookup tables will not make them
03709   // faster, so we don't analyze them.
03710   if (SI->getNumCases() < 3)
03711     return false;
03712 
03713   // Figure out the corresponding result for each case value and phi node in the
03714   // common destination, as well as the the min and max case values.
03715   assert(SI->case_begin() != SI->case_end());
03716   SwitchInst::CaseIt CI = SI->case_begin();
03717   ConstantInt *MinCaseVal = CI.getCaseValue();
03718   ConstantInt *MaxCaseVal = CI.getCaseValue();
03719 
03720   BasicBlock *CommonDest = nullptr;
03721   typedef SmallVector<std::pair<ConstantInt*, Constant*>, 4> ResultListTy;
03722   SmallDenseMap<PHINode*, ResultListTy> ResultLists;
03723   SmallDenseMap<PHINode*, Constant*> DefaultResults;
03724   SmallDenseMap<PHINode*, Type*> ResultTypes;
03725   SmallVector<PHINode*, 4> PHIs;
03726 
03727   for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) {
03728     ConstantInt *CaseVal = CI.getCaseValue();
03729     if (CaseVal->getValue().slt(MinCaseVal->getValue()))
03730       MinCaseVal = CaseVal;
03731     if (CaseVal->getValue().sgt(MaxCaseVal->getValue()))
03732       MaxCaseVal = CaseVal;
03733 
03734     // Resulting value at phi nodes for this case value.
03735     typedef SmallVector<std::pair<PHINode*, Constant*>, 4> ResultsTy;
03736     ResultsTy Results;
03737     if (!GetCaseResults(SI, CaseVal, CI.getCaseSuccessor(), &CommonDest,
03738                         Results, DL))
03739       return false;
03740 
03741     // Append the result from this case to the list for each phi.
03742     for (ResultsTy::iterator I = Results.begin(), E = Results.end(); I!=E; ++I) {
03743       if (!ResultLists.count(I->first))
03744         PHIs.push_back(I->first);
03745       ResultLists[I->first].push_back(std::make_pair(CaseVal, I->second));
03746     }
03747   }
03748 
03749   // Keep track of the result types.
03750   for (size_t I = 0, E = PHIs.size(); I != E; ++I) {
03751     PHINode *PHI = PHIs[I];
03752     ResultTypes[PHI] = ResultLists[PHI][0].second->getType();
03753   }
03754 
03755   uint64_t NumResults = ResultLists[PHIs[0]].size();
03756   APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue();
03757   uint64_t TableSize = RangeSpread.getLimitedValue() + 1;
03758   bool TableHasHoles = (NumResults < TableSize);
03759 
03760   // If the table has holes, we need a constant result for the default case
03761   // or a bitmask that fits in a register.
03762   SmallVector<std::pair<PHINode*, Constant*>, 4> DefaultResultsList;
03763   bool HasDefaultResults = false;
03764   if (TableHasHoles) {
03765     HasDefaultResults = GetCaseResults(SI, nullptr, SI->getDefaultDest(),
03766                                        &CommonDest, DefaultResultsList, DL);
03767   }
03768   bool NeedMask = (TableHasHoles && !HasDefaultResults);
03769   if (NeedMask) {
03770     // As an extra penalty for the validity test we require more cases.
03771     if (SI->getNumCases() < 4)  // FIXME: Find best threshold value (benchmark).
03772       return false;
03773     if (!(DL && DL->fitsInLegalInteger(TableSize)))
03774       return false;
03775   }
03776 
03777   for (size_t I = 0, E = DefaultResultsList.size(); I != E; ++I) {
03778     PHINode *PHI = DefaultResultsList[I].first;
03779     Constant *Result = DefaultResultsList[I].second;
03780     DefaultResults[PHI] = Result;
03781   }
03782 
03783   if (!ShouldBuildLookupTable(SI, TableSize, TTI, DL, ResultTypes))
03784     return false;
03785 
03786   // Create the BB that does the lookups.
03787   Module &Mod = *CommonDest->getParent()->getParent();
03788   BasicBlock *LookupBB = BasicBlock::Create(Mod.getContext(),
03789                                             "switch.lookup",
03790                                             CommonDest->getParent(),
03791                                             CommonDest);
03792 
03793   // Compute the table index value.
03794   Builder.SetInsertPoint(SI);
03795   Value *TableIndex = Builder.CreateSub(SI->getCondition(), MinCaseVal,
03796                                         "switch.tableidx");
03797 
03798   // Compute the maximum table size representable by the integer type we are
03799   // switching upon.
03800   unsigned CaseSize = MinCaseVal->getType()->getPrimitiveSizeInBits();
03801   uint64_t MaxTableSize = CaseSize > 63 ? UINT64_MAX : 1ULL << CaseSize;
03802   assert(MaxTableSize >= TableSize &&
03803          "It is impossible for a switch to have more entries than the max "
03804          "representable value of its input integer type's size.");
03805 
03806   // If we have a fully covered lookup table, unconditionally branch to the
03807   // lookup table BB. Otherwise, check if the condition value is within the case
03808   // range. If it is so, branch to the new BB. Otherwise branch to SI's default
03809   // destination.
03810   const bool GeneratingCoveredLookupTable = MaxTableSize == TableSize;
03811   if (GeneratingCoveredLookupTable) {
03812     Builder.CreateBr(LookupBB);
03813     // We cached PHINodes in PHIs, to avoid accessing deleted PHINodes later,
03814     // do not delete PHINodes here.
03815     SI->getDefaultDest()->removePredecessor(SI->getParent(),
03816                                             true/*DontDeleteUselessPHIs*/);
03817   } else {
03818     Value *Cmp = Builder.CreateICmpULT(TableIndex, ConstantInt::get(
03819                                        MinCaseVal->getType(), TableSize));
03820     Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
03821   }
03822 
03823   // Populate the BB that does the lookups.
03824   Builder.SetInsertPoint(LookupBB);
03825 
03826   if (NeedMask) {
03827     // Before doing the lookup we do the hole check.
03828     // The LookupBB is therefore re-purposed to do the hole check
03829     // and we create a new LookupBB.
03830     BasicBlock *MaskBB = LookupBB;
03831     MaskBB->setName("switch.hole_check");
03832     LookupBB = BasicBlock::Create(Mod.getContext(),
03833                                   "switch.lookup",
03834                                   CommonDest->getParent(),
03835                                   CommonDest);
03836 
03837     // Build bitmask; fill in a 1 bit for every case.
03838     APInt MaskInt(TableSize, 0);
03839     APInt One(TableSize, 1);
03840     const ResultListTy &ResultList = ResultLists[PHIs[0]];
03841     for (size_t I = 0, E = ResultList.size(); I != E; ++I) {
03842       uint64_t Idx = (ResultList[I].first->getValue() -
03843                       MinCaseVal->getValue()).getLimitedValue();
03844       MaskInt |= One << Idx;
03845     }
03846     ConstantInt *TableMask = ConstantInt::get(Mod.getContext(), MaskInt);
03847 
03848     // Get the TableIndex'th bit of the bitmask.
03849     // If this bit is 0 (meaning hole) jump to the default destination,
03850     // else continue with table lookup.
03851     IntegerType *MapTy = TableMask->getType();
03852     Value *MaskIndex = Builder.CreateZExtOrTrunc(TableIndex, MapTy,
03853                                                  "switch.maskindex");
03854     Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
03855                                         "switch.shifted");
03856     Value *LoBit = Builder.CreateTrunc(Shifted,
03857                                        Type::getInt1Ty(Mod.getContext()),
03858                                        "switch.lobit");
03859     Builder.CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
03860 
03861     Builder.SetInsertPoint(LookupBB);
03862     AddPredecessorToBlock(SI->getDefaultDest(), MaskBB, SI->getParent());
03863   }
03864 
03865   bool ReturnedEarly = false;
03866   for (size_t I = 0, E = PHIs.size(); I != E; ++I) {
03867     PHINode *PHI = PHIs[I];
03868 
03869     // If using a bitmask, use any value to fill the lookup table holes.
03870     Constant *DV = NeedMask ? ResultLists[PHI][0].second : DefaultResults[PHI];
03871     SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultLists[PHI],
03872                             DV, DL);
03873 
03874     Value *Result = Table.BuildLookup(TableIndex, Builder);
03875 
03876     // If the result is used to return immediately from the function, we want to
03877     // do that right here.
03878     if (PHI->hasOneUse() && isa<ReturnInst>(*PHI->user_begin()) &&
03879         PHI->user_back() == CommonDest->getFirstNonPHIOrDbg()) {
03880       Builder.CreateRet(Result);
03881       ReturnedEarly = true;
03882       break;
03883     }
03884 
03885     PHI->addIncoming(Result, LookupBB);
03886   }
03887 
03888   if (!ReturnedEarly)
03889     Builder.CreateBr(CommonDest);
03890 
03891   // Remove the switch.
03892   for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
03893     BasicBlock *Succ = SI->getSuccessor(i);
03894 
03895     if (Succ == SI->getDefaultDest())
03896       continue;
03897     Succ->removePredecessor(SI->getParent());
03898   }
03899   SI->eraseFromParent();
03900 
03901   ++NumLookupTables;
03902   if (NeedMask)
03903     ++NumLookupTablesHoles;
03904   return true;
03905 }
03906 
03907 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
03908   BasicBlock *BB = SI->getParent();
03909 
03910   if (isValueEqualityComparison(SI)) {
03911     // If we only have one predecessor, and if it is a branch on this value,
03912     // see if that predecessor totally determines the outcome of this switch.
03913     if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
03914       if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
03915         return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
03916 
03917     Value *Cond = SI->getCondition();
03918     if (SelectInst *Select = dyn_cast<SelectInst>(Cond))
03919       if (SimplifySwitchOnSelect(SI, Select))
03920         return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
03921 
03922     // If the block only contains the switch, see if we can fold the block
03923     // away into any preds.
03924     BasicBlock::iterator BBI = BB->begin();
03925     // Ignore dbg intrinsics.
03926     while (isa<DbgInfoIntrinsic>(BBI))
03927       ++BBI;
03928     if (SI == &*BBI)
03929       if (FoldValueComparisonIntoPredecessors(SI, Builder))
03930         return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
03931   }
03932 
03933   // Try to transform the switch into an icmp and a branch.
03934   if (TurnSwitchRangeIntoICmp(SI, Builder))
03935     return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
03936 
03937   // Remove unreachable cases.
03938   if (EliminateDeadSwitchCases(SI, DL, AT))
03939     return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
03940 
03941   if (ForwardSwitchConditionToPHI(SI))
03942     return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
03943 
03944   if (SwitchToLookupTable(SI, Builder, TTI, DL))
03945     return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
03946 
03947   return false;
03948 }
03949 
03950 bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) {
03951   BasicBlock *BB = IBI->getParent();
03952   bool Changed = false;
03953 
03954   // Eliminate redundant destinations.
03955   SmallPtrSet<Value *, 8> Succs;
03956   for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
03957     BasicBlock *Dest = IBI->getDestination(i);
03958     if (!Dest->hasAddressTaken() || !Succs.insert(Dest)) {
03959       Dest->removePredecessor(BB);
03960       IBI->removeDestination(i);
03961       --i; --e;
03962       Changed = true;
03963     }
03964   }
03965 
03966   if (IBI->getNumDestinations() == 0) {
03967     // If the indirectbr has no successors, change it to unreachable.
03968     new UnreachableInst(IBI->getContext(), IBI);
03969     EraseTerminatorInstAndDCECond(IBI);
03970     return true;
03971   }
03972 
03973   if (IBI->getNumDestinations() == 1) {
03974     // If the indirectbr has one successor, change it to a direct branch.
03975     BranchInst::Create(IBI->getDestination(0), IBI);
03976     EraseTerminatorInstAndDCECond(IBI);
03977     return true;
03978   }
03979 
03980   if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) {
03981     if (SimplifyIndirectBrOnSelect(IBI, SI))
03982       return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
03983   }
03984   return Changed;
03985 }
03986 
03987 bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){
03988   BasicBlock *BB = BI->getParent();
03989 
03990   if (SinkCommon && SinkThenElseCodeToEnd(BI))
03991     return true;
03992 
03993   // If the Terminator is the only non-phi instruction, simplify the block.
03994   BasicBlock::iterator I = BB->getFirstNonPHIOrDbg();
03995   if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() &&
03996       TryToSimplifyUncondBranchFromEmptyBlock(BB))
03997     return true;
03998 
03999   // If the only instruction in the block is a seteq/setne comparison
04000   // against a constant, try to simplify the block.
04001   if (ICmpInst *ICI = dyn_cast<ICmpInst>(I))
04002     if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) {
04003       for (++I; isa<DbgInfoIntrinsic>(I); ++I)
04004         ;
04005       if (I->isTerminator() &&
04006           TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, TTI,
04007                                                 BonusInstThreshold, DL, AT))
04008         return true;
04009     }
04010 
04011   // If this basic block is ONLY a compare and a branch, and if a predecessor
04012   // branches to us and our successor, fold the comparison into the
04013   // predecessor and use logical operations to update the incoming value
04014   // for PHI nodes in common successor.
04015   if (FoldBranchToCommonDest(BI, DL, BonusInstThreshold))
04016     return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
04017   return false;
04018 }
04019 
04020 
04021 bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
04022   BasicBlock *BB = BI->getParent();
04023 
04024   // Conditional branch
04025   if (isValueEqualityComparison(BI)) {
04026     // If we only have one predecessor, and if it is a branch on this value,
04027     // see if that predecessor totally determines the outcome of this
04028     // switch.
04029     if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
04030       if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
04031         return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
04032 
04033     // This block must be empty, except for the setcond inst, if it exists.
04034     // Ignore dbg intrinsics.
04035     BasicBlock::iterator I = BB->begin();
04036     // Ignore dbg intrinsics.
04037     while (isa<DbgInfoIntrinsic>(I))
04038       ++I;
04039     if (&*I == BI) {
04040       if (FoldValueComparisonIntoPredecessors(BI, Builder))
04041         return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
04042     } else if (&*I == cast<Instruction>(BI->getCondition())){
04043       ++I;
04044       // Ignore dbg intrinsics.
04045       while (isa<DbgInfoIntrinsic>(I))
04046         ++I;
04047       if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
04048         return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
04049     }
04050   }
04051 
04052   // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction.
04053   if (SimplifyBranchOnICmpChain(BI, DL, Builder))
04054     return true;
04055 
04056   // If this basic block is ONLY a compare and a branch, and if a predecessor
04057   // branches to us and one of our successors, fold the comparison into the
04058   // predecessor and use logical operations to pick the right destination.
04059   if (FoldBranchToCommonDest(BI, DL, BonusInstThreshold))
04060     return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
04061 
04062   // We have a conditional branch to two blocks that are only reachable
04063   // from BI.  We know that the condbr dominates the two blocks, so see if
04064   // there is any identical code in the "then" and "else" blocks.  If so, we
04065   // can hoist it up to the branching block.
04066   if (BI->getSuccessor(0)->getSinglePredecessor()) {
04067     if (BI->getSuccessor(1)->getSinglePredecessor()) {
04068       if (HoistThenElseCodeToIf(BI, DL))
04069         return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
04070     } else {
04071       // If Successor #1 has multiple preds, we may be able to conditionally
04072       // execute Successor #0 if it branches to Successor #1.
04073       TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator();
04074       if (Succ0TI->getNumSuccessors() == 1 &&
04075           Succ0TI->getSuccessor(0) == BI->getSuccessor(1))
04076         if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0), DL))
04077           return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
04078     }
04079   } else if (BI->getSuccessor(1)->getSinglePredecessor()) {
04080     // If Successor #0 has multiple preds, we may be able to conditionally
04081     // execute Successor #1 if it branches to Successor #0.
04082     TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator();
04083     if (Succ1TI->getNumSuccessors() == 1 &&
04084         Succ1TI->getSuccessor(0) == BI->getSuccessor(0))
04085       if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1), DL))
04086         return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
04087   }
04088 
04089   // If this is a branch on a phi node in the current block, thread control
04090   // through this block if any PHI node entries are constants.
04091   if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition()))
04092     if (PN->getParent() == BI->getParent())
04093       if (FoldCondBranchOnPHI(BI, DL))
04094         return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
04095 
04096   // Scan predecessor blocks for conditional branches.
04097   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
04098     if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
04099       if (PBI != BI && PBI->isConditional())
04100         if (SimplifyCondBranchToCondBranch(PBI, BI))
04101           return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
04102 
04103   return false;
04104 }
04105 
04106 /// Check if passing a value to an instruction will cause undefined behavior.
04107 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) {
04108   Constant *C = dyn_cast<Constant>(V);
04109   if (!C)
04110     return false;
04111 
04112   if (I->use_empty())
04113     return false;
04114 
04115   if (C->isNullValue()) {
04116     // Only look at the first use, avoid hurting compile time with long uselists
04117     User *Use = *I->user_begin();
04118 
04119     // Now make sure that there are no instructions in between that can alter
04120     // control flow (eg. calls)
04121     for (BasicBlock::iterator i = ++BasicBlock::iterator(I); &*i != Use; ++i)
04122       if (i == I->getParent()->end() || i->mayHaveSideEffects())
04123         return false;
04124 
04125     // Look through GEPs. A load from a GEP derived from NULL is still undefined
04126     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Use))
04127       if (GEP->getPointerOperand() == I)
04128         return passingValueIsAlwaysUndefined(V, GEP);
04129 
04130     // Look through bitcasts.
04131     if (BitCastInst *BC = dyn_cast<BitCastInst>(Use))
04132       return passingValueIsAlwaysUndefined(V, BC);
04133 
04134     // Load from null is undefined.
04135     if (LoadInst *LI = dyn_cast<LoadInst>(Use))
04136       if (!LI->isVolatile())
04137         return LI->getPointerAddressSpace() == 0;
04138 
04139     // Store to null is undefined.
04140     if (StoreInst *SI = dyn_cast<StoreInst>(Use))
04141       if (!SI->isVolatile())
04142         return SI->getPointerAddressSpace() == 0 && SI->getPointerOperand() == I;
04143   }
04144   return false;
04145 }
04146 
04147 /// If BB has an incoming value that will always trigger undefined behavior
04148 /// (eg. null pointer dereference), remove the branch leading here.
04149 static bool removeUndefIntroducingPredecessor(BasicBlock *BB) {
04150   for (BasicBlock::iterator i = BB->begin();
04151        PHINode *PHI = dyn_cast<PHINode>(i); ++i)
04152     for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
04153       if (passingValueIsAlwaysUndefined(PHI->getIncomingValue(i), PHI)) {
04154         TerminatorInst *T = PHI->getIncomingBlock(i)->getTerminator();
04155         IRBuilder<> Builder(T);
04156         if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
04157           BB->removePredecessor(PHI->getIncomingBlock(i));
04158           // Turn uncoditional branches into unreachables and remove the dead
04159           // destination from conditional branches.
04160           if (BI->isUnconditional())
04161             Builder.CreateUnreachable();
04162           else
04163             Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) :
04164                                                          BI->getSuccessor(0));
04165           BI->eraseFromParent();
04166           return true;
04167         }
04168         // TODO: SwitchInst.
04169       }
04170 
04171   return false;
04172 }
04173 
04174 bool SimplifyCFGOpt::run(BasicBlock *BB) {
04175   bool Changed = false;
04176 
04177   assert(BB && BB->getParent() && "Block not embedded in function!");
04178   assert(BB->getTerminator() && "Degenerate basic block encountered!");
04179 
04180   // Remove basic blocks that have no predecessors (except the entry block)...
04181   // or that just have themself as a predecessor.  These are unreachable.
04182   if ((pred_begin(BB) == pred_end(BB) &&
04183        BB != &BB->getParent()->getEntryBlock()) ||
04184       BB->getSinglePredecessor() == BB) {
04185     DEBUG(dbgs() << "Removing BB: \n" << *BB);
04186     DeleteDeadBlock(BB);
04187     return true;
04188   }
04189 
04190   // Check to see if we can constant propagate this terminator instruction
04191   // away...
04192   Changed |= ConstantFoldTerminator(BB, true);
04193 
04194   // Check for and eliminate duplicate PHI nodes in this block.
04195   Changed |= EliminateDuplicatePHINodes(BB);
04196 
04197   // Check for and remove branches that will always cause undefined behavior.
04198   Changed |= removeUndefIntroducingPredecessor(BB);
04199 
04200   // Merge basic blocks into their predecessor if there is only one distinct
04201   // pred, and if there is only one distinct successor of the predecessor, and
04202   // if there are no PHI nodes.
04203   //
04204   if (MergeBlockIntoPredecessor(BB))
04205     return true;
04206 
04207   IRBuilder<> Builder(BB);
04208 
04209   // If there is a trivial two-entry PHI node in this basic block, and we can
04210   // eliminate it, do so now.
04211   if (PHINode *PN = dyn_cast<PHINode>(BB->begin()))
04212     if (PN->getNumIncomingValues() == 2)
04213       Changed |= FoldTwoEntryPHINode(PN, DL);
04214 
04215   Builder.SetInsertPoint(BB->getTerminator());
04216   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
04217     if (BI->isUnconditional()) {
04218       if (SimplifyUncondBranch(BI, Builder)) return true;
04219     } else {
04220       if (SimplifyCondBranch(BI, Builder)) return true;
04221     }
04222   } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
04223     if (SimplifyReturn(RI, Builder)) return true;
04224   } else if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) {
04225     if (SimplifyResume(RI, Builder)) return true;
04226   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
04227     if (SimplifySwitch(SI, Builder)) return true;
04228   } else if (UnreachableInst *UI =
04229                dyn_cast<UnreachableInst>(BB->getTerminator())) {
04230     if (SimplifyUnreachable(UI)) return true;
04231   } else if (IndirectBrInst *IBI =
04232                dyn_cast<IndirectBrInst>(BB->getTerminator())) {
04233     if (SimplifyIndirectBr(IBI)) return true;
04234   }
04235 
04236   return Changed;
04237 }
04238 
04239 /// SimplifyCFG - This function is used to do simplification of a CFG.  For
04240 /// example, it adjusts branches to branches to eliminate the extra hop, it
04241 /// eliminates unreachable basic blocks, and does other "peephole" optimization
04242 /// of the CFG.  It returns true if a modification was made.
04243 ///
04244 bool llvm::SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
04245                        unsigned BonusInstThreshold,
04246                        const DataLayout *DL, AssumptionTracker *AT) {
04247   return SimplifyCFGOpt(TTI, BonusInstThreshold, DL, AT).run(BB);
04248 }