e3bdd6066be091b9e0f3a9c0c89000b58d314bbf
[oota-llvm.git] / lib / Transforms / Utils / SimplifyCFG.cpp
1 //===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Peephole optimize the CFG.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/Transforms/Utils/Local.h"
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SetVector.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/Analysis/ConstantFolding.h"
22 #include "llvm/Analysis/InstructionSimplify.h"
23 #include "llvm/Analysis/TargetTransformInfo.h"
24 #include "llvm/Analysis/ValueTracking.h"
25 #include "llvm/IR/CFG.h"
26 #include "llvm/IR/ConstantRange.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DerivedTypes.h"
30 #include "llvm/IR/GlobalVariable.h"
31 #include "llvm/IR/IRBuilder.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/IntrinsicInst.h"
34 #include "llvm/IR/LLVMContext.h"
35 #include "llvm/IR/MDBuilder.h"
36 #include "llvm/IR/Metadata.h"
37 #include "llvm/IR/Module.h"
38 #include "llvm/IR/NoFolder.h"
39 #include "llvm/IR/Operator.h"
40 #include "llvm/IR/PatternMatch.h"
41 #include "llvm/IR/Type.h"
42 #include "llvm/Support/CommandLine.h"
43 #include "llvm/Support/Debug.h"
44 #include "llvm/Support/raw_ostream.h"
45 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
46 #include "llvm/Transforms/Utils/Local.h"
47 #include "llvm/Transforms/Utils/ValueMapper.h"
48 #include <algorithm>
49 #include <map>
50 #include <set>
51 using namespace llvm;
52 using namespace PatternMatch;
53
54 #define DEBUG_TYPE "simplifycfg"
55
56 static cl::opt<unsigned>
57 PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(1),
58    cl::desc("Control the amount of phi node folding to perform (default = 1)"));
59
60 static cl::opt<bool>
61 DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false),
62        cl::desc("Duplicate return instructions into unconditional branches"));
63
64 static cl::opt<bool>
65 SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true),
66        cl::desc("Sink common instructions down to the end block"));
67
68 static cl::opt<bool> HoistCondStores(
69     "simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true),
70     cl::desc("Hoist conditional stores if an unconditional store precedes"));
71
72 STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
73 STATISTIC(NumLinearMaps, "Number of switch instructions turned into linear mapping");
74 STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables");
75 STATISTIC(NumLookupTablesHoles, "Number of switch instructions turned into lookup tables (holes checked)");
76 STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block");
77 STATISTIC(NumSpeculations, "Number of speculative executed instructions");
78
79 namespace {
80   // The first field contains the value that the switch produces when a certain
81   // case group is selected, and the second field is a vector containing the cases
82   // composing the case group.
83   typedef SmallVector<std::pair<Constant *, SmallVector<ConstantInt *, 4>>, 2>
84     SwitchCaseResultVectorTy;
85   // The first field contains the phi node that generates a result of the switch
86   // and the second field contains the value generated for a certain case in the switch
87   // for that PHI.
88   typedef SmallVector<std::pair<PHINode *, Constant *>, 4> SwitchCaseResultsTy;
89
90   /// ValueEqualityComparisonCase - Represents a case of a switch.
91   struct ValueEqualityComparisonCase {
92     ConstantInt *Value;
93     BasicBlock *Dest;
94
95     ValueEqualityComparisonCase(ConstantInt *Value, BasicBlock *Dest)
96       : Value(Value), Dest(Dest) {}
97
98     bool operator<(ValueEqualityComparisonCase RHS) const {
99       // Comparing pointers is ok as we only rely on the order for uniquing.
100       return Value < RHS.Value;
101     }
102
103     bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; }
104   };
105
106 class SimplifyCFGOpt {
107   const TargetTransformInfo &TTI;
108   unsigned BonusInstThreshold;
109   const DataLayout *const DL;
110   AssumptionTracker *AT;
111   Value *isValueEqualityComparison(TerminatorInst *TI);
112   BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI,
113                                std::vector<ValueEqualityComparisonCase> &Cases);
114   bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
115                                                      BasicBlock *Pred,
116                                                      IRBuilder<> &Builder);
117   bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
118                                            IRBuilder<> &Builder);
119
120   bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder);
121   bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder);
122   bool SimplifyUnreachable(UnreachableInst *UI);
123   bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
124   bool SimplifyIndirectBr(IndirectBrInst *IBI);
125   bool SimplifyUncondBranch(BranchInst *BI, IRBuilder <> &Builder);
126   bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder);
127
128 public:
129   SimplifyCFGOpt(const TargetTransformInfo &TTI, unsigned BonusInstThreshold,
130                  const DataLayout *DL, AssumptionTracker *AT)
131       : TTI(TTI), BonusInstThreshold(BonusInstThreshold), DL(DL), AT(AT) {}
132   bool run(BasicBlock *BB);
133 };
134 }
135
136 /// SafeToMergeTerminators - Return true if it is safe to merge these two
137 /// terminator instructions together.
138 ///
139 static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) {
140   if (SI1 == SI2) return false;  // Can't merge with self!
141
142   // It is not safe to merge these two switch instructions if they have a common
143   // successor, and if that successor has a PHI node, and if *that* PHI node has
144   // conflicting incoming values from the two switch blocks.
145   BasicBlock *SI1BB = SI1->getParent();
146   BasicBlock *SI2BB = SI2->getParent();
147   SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
148
149   for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I)
150     if (SI1Succs.count(*I))
151       for (BasicBlock::iterator BBI = (*I)->begin();
152            isa<PHINode>(BBI); ++BBI) {
153         PHINode *PN = cast<PHINode>(BBI);
154         if (PN->getIncomingValueForBlock(SI1BB) !=
155             PN->getIncomingValueForBlock(SI2BB))
156           return false;
157       }
158
159   return true;
160 }
161
162 /// isProfitableToFoldUnconditional - Return true if it is safe and profitable
163 /// to merge these two terminator instructions together, where SI1 is an
164 /// unconditional branch. PhiNodes will store all PHI nodes in common
165 /// successors.
166 ///
167 static bool isProfitableToFoldUnconditional(BranchInst *SI1,
168                                           BranchInst *SI2,
169                                           Instruction *Cond,
170                                           SmallVectorImpl<PHINode*> &PhiNodes) {
171   if (SI1 == SI2) return false;  // Can't merge with self!
172   assert(SI1->isUnconditional() && SI2->isConditional());
173
174   // We fold the unconditional branch if we can easily update all PHI nodes in
175   // common successors:
176   // 1> We have a constant incoming value for the conditional branch;
177   // 2> We have "Cond" as the incoming value for the unconditional branch;
178   // 3> SI2->getCondition() and Cond have same operands.
179   CmpInst *Ci2 = dyn_cast<CmpInst>(SI2->getCondition());
180   if (!Ci2) return false;
181   if (!(Cond->getOperand(0) == Ci2->getOperand(0) &&
182         Cond->getOperand(1) == Ci2->getOperand(1)) &&
183       !(Cond->getOperand(0) == Ci2->getOperand(1) &&
184         Cond->getOperand(1) == Ci2->getOperand(0)))
185     return false;
186
187   BasicBlock *SI1BB = SI1->getParent();
188   BasicBlock *SI2BB = SI2->getParent();
189   SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
190   for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I)
191     if (SI1Succs.count(*I))
192       for (BasicBlock::iterator BBI = (*I)->begin();
193            isa<PHINode>(BBI); ++BBI) {
194         PHINode *PN = cast<PHINode>(BBI);
195         if (PN->getIncomingValueForBlock(SI1BB) != Cond ||
196             !isa<ConstantInt>(PN->getIncomingValueForBlock(SI2BB)))
197           return false;
198         PhiNodes.push_back(PN);
199       }
200   return true;
201 }
202
203 /// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will
204 /// now be entries in it from the 'NewPred' block.  The values that will be
205 /// flowing into the PHI nodes will be the same as those coming in from
206 /// ExistPred, an existing predecessor of Succ.
207 static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred,
208                                   BasicBlock *ExistPred) {
209   if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do
210
211   PHINode *PN;
212   for (BasicBlock::iterator I = Succ->begin();
213        (PN = dyn_cast<PHINode>(I)); ++I)
214     PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred);
215 }
216
217 /// ComputeSpeculationCost - Compute an abstract "cost" of speculating the
218 /// given instruction, which is assumed to be safe to speculate. 1 means
219 /// cheap, 2 means less cheap, and UINT_MAX means prohibitively expensive.
220 static unsigned ComputeSpeculationCost(const User *I, const DataLayout *DL) {
221   assert(isSafeToSpeculativelyExecute(I, DL) &&
222          "Instruction is not safe to speculatively execute!");
223   switch (Operator::getOpcode(I)) {
224   default:
225     // In doubt, be conservative.
226     return UINT_MAX;
227   case Instruction::GetElementPtr:
228     // GEPs are cheap if all indices are constant.
229     if (!cast<GEPOperator>(I)->hasAllConstantIndices())
230       return UINT_MAX;
231     return 1;
232   case Instruction::ExtractValue:
233   case Instruction::Load:
234   case Instruction::Add:
235   case Instruction::Sub:
236   case Instruction::And:
237   case Instruction::Or:
238   case Instruction::Xor:
239   case Instruction::Shl:
240   case Instruction::LShr:
241   case Instruction::AShr:
242   case Instruction::ICmp:
243   case Instruction::Trunc:
244   case Instruction::ZExt:
245   case Instruction::SExt:
246   case Instruction::BitCast:
247   case Instruction::ExtractElement:
248   case Instruction::InsertElement:
249     return 1; // These are all cheap.
250
251   case Instruction::Call:
252   case Instruction::Select:
253     return 2;
254   }
255 }
256
257 /// DominatesMergePoint - If we have a merge point of an "if condition" as
258 /// accepted above, return true if the specified value dominates the block.  We
259 /// don't handle the true generality of domination here, just a special case
260 /// which works well enough for us.
261 ///
262 /// If AggressiveInsts is non-null, and if V does not dominate BB, we check to
263 /// see if V (which must be an instruction) and its recursive operands
264 /// that do not dominate BB have a combined cost lower than CostRemaining and
265 /// are non-trapping.  If both are true, the instruction is inserted into the
266 /// set and true is returned.
267 ///
268 /// The cost for most non-trapping instructions is defined as 1 except for
269 /// Select whose cost is 2.
270 ///
271 /// After this function returns, CostRemaining is decreased by the cost of
272 /// V plus its non-dominating operands.  If that cost is greater than
273 /// CostRemaining, false is returned and CostRemaining is undefined.
274 static bool DominatesMergePoint(Value *V, BasicBlock *BB,
275                                 SmallPtrSetImpl<Instruction*> *AggressiveInsts,
276                                 unsigned &CostRemaining,
277                                 const DataLayout *DL) {
278   Instruction *I = dyn_cast<Instruction>(V);
279   if (!I) {
280     // Non-instructions all dominate instructions, but not all constantexprs
281     // can be executed unconditionally.
282     if (ConstantExpr *C = dyn_cast<ConstantExpr>(V))
283       if (C->canTrap())
284         return false;
285     return true;
286   }
287   BasicBlock *PBB = I->getParent();
288
289   // We don't want to allow weird loops that might have the "if condition" in
290   // the bottom of this block.
291   if (PBB == BB) return false;
292
293   // If this instruction is defined in a block that contains an unconditional
294   // branch to BB, then it must be in the 'conditional' part of the "if
295   // statement".  If not, it definitely dominates the region.
296   BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator());
297   if (!BI || BI->isConditional() || BI->getSuccessor(0) != BB)
298     return true;
299
300   // If we aren't allowing aggressive promotion anymore, then don't consider
301   // instructions in the 'if region'.
302   if (!AggressiveInsts) return false;
303
304   // If we have seen this instruction before, don't count it again.
305   if (AggressiveInsts->count(I)) return true;
306
307   // Okay, it looks like the instruction IS in the "condition".  Check to
308   // see if it's a cheap instruction to unconditionally compute, and if it
309   // only uses stuff defined outside of the condition.  If so, hoist it out.
310   if (!isSafeToSpeculativelyExecute(I, DL))
311     return false;
312
313   unsigned Cost = ComputeSpeculationCost(I, DL);
314
315   if (Cost > CostRemaining)
316     return false;
317
318   CostRemaining -= Cost;
319
320   // Okay, we can only really hoist these out if their operands do
321   // not take us over the cost threshold.
322   for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
323     if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining, DL))
324       return false;
325   // Okay, it's safe to do this!  Remember this instruction.
326   AggressiveInsts->insert(I);
327   return true;
328 }
329
330 /// GetConstantInt - Extract ConstantInt from value, looking through IntToPtr
331 /// and PointerNullValue. Return NULL if value is not a constant int.
332 static ConstantInt *GetConstantInt(Value *V, const DataLayout *DL) {
333   // Normal constant int.
334   ConstantInt *CI = dyn_cast<ConstantInt>(V);
335   if (CI || !DL || !isa<Constant>(V) || !V->getType()->isPointerTy())
336     return CI;
337
338   // This is some kind of pointer constant. Turn it into a pointer-sized
339   // ConstantInt if possible.
340   IntegerType *PtrTy = cast<IntegerType>(DL->getIntPtrType(V->getType()));
341
342   // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*).
343   if (isa<ConstantPointerNull>(V))
344     return ConstantInt::get(PtrTy, 0);
345
346   // IntToPtr const int.
347   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
348     if (CE->getOpcode() == Instruction::IntToPtr)
349       if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
350         // The constant is very likely to have the right type already.
351         if (CI->getType() == PtrTy)
352           return CI;
353         else
354           return cast<ConstantInt>
355             (ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false));
356       }
357   return nullptr;
358 }
359
360 /// GatherConstantCompares - Given a potentially 'or'd or 'and'd together
361 /// collection of icmp eq/ne instructions that compare a value against a
362 /// constant, return the value being compared, and stick the constant into the
363 /// Values vector.
364 static Value *
365 GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra,
366                        const DataLayout *DL, bool isEQ, unsigned &UsedICmps) {
367   Instruction *I = dyn_cast<Instruction>(V);
368   if (!I) return nullptr;
369
370   // If this is an icmp against a constant, handle this as one of the cases.
371   if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
372     if (ConstantInt *C = GetConstantInt(I->getOperand(1), DL)) {
373       Value *RHSVal;
374       ConstantInt *RHSC;
375
376       if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) {
377         // (x & ~2^x) == y --> x == y || x == y|2^x
378         // This undoes a transformation done by instcombine to fuse 2 compares.
379         if (match(ICI->getOperand(0),
380                   m_And(m_Value(RHSVal), m_ConstantInt(RHSC)))) {
381           APInt Not = ~RHSC->getValue();
382           if (Not.isPowerOf2()) {
383             Vals.push_back(C);
384             Vals.push_back(
385                 ConstantInt::get(C->getContext(), C->getValue() | Not));
386             UsedICmps++;
387             return RHSVal;
388           }
389         }
390
391         UsedICmps++;
392         Vals.push_back(C);
393         return I->getOperand(0);
394       }
395
396       // If we have "x ult 3" comparison, for example, then we can add 0,1,2 to
397       // the set.
398       ConstantRange Span =
399         ConstantRange::makeICmpRegion(ICI->getPredicate(), C->getValue());
400
401       // Shift the range if the compare is fed by an add. This is the range
402       // compare idiom as emitted by instcombine.
403       bool hasAdd =
404           match(I->getOperand(0), m_Add(m_Value(RHSVal), m_ConstantInt(RHSC)));
405       if (hasAdd)
406         Span = Span.subtract(RHSC->getValue());
407
408       // If this is an and/!= check then we want to optimize "x ugt 2" into
409       // x != 0 && x != 1.
410       if (!isEQ)
411         Span = Span.inverse();
412
413       // If there are a ton of values, we don't want to make a ginormous switch.
414       if (Span.getSetSize().ugt(8) || Span.isEmptySet())
415         return nullptr;
416
417       for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp)
418         Vals.push_back(ConstantInt::get(V->getContext(), Tmp));
419       UsedICmps++;
420       return hasAdd ? RHSVal : I->getOperand(0);
421     }
422     return nullptr;
423   }
424
425   // Otherwise, we can only handle an | or &, depending on isEQ.
426   if (I->getOpcode() != (isEQ ? Instruction::Or : Instruction::And))
427     return nullptr;
428
429   unsigned NumValsBeforeLHS = Vals.size();
430   unsigned UsedICmpsBeforeLHS = UsedICmps;
431   if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, DL,
432                                           isEQ, UsedICmps)) {
433     unsigned NumVals = Vals.size();
434     unsigned UsedICmpsBeforeRHS = UsedICmps;
435     if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, DL,
436                                             isEQ, UsedICmps)) {
437       if (LHS == RHS)
438         return LHS;
439       Vals.resize(NumVals);
440       UsedICmps = UsedICmpsBeforeRHS;
441     }
442
443     // The RHS of the or/and can't be folded in and we haven't used "Extra" yet,
444     // set it and return success.
445     if (Extra == nullptr || Extra == I->getOperand(1)) {
446       Extra = I->getOperand(1);
447       return LHS;
448     }
449
450     Vals.resize(NumValsBeforeLHS);
451     UsedICmps = UsedICmpsBeforeLHS;
452     return nullptr;
453   }
454
455   // If the LHS can't be folded in, but Extra is available and RHS can, try to
456   // use LHS as Extra.
457   if (Extra == nullptr || Extra == I->getOperand(0)) {
458     Value *OldExtra = Extra;
459     Extra = I->getOperand(0);
460     if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, DL,
461                                             isEQ, UsedICmps))
462       return RHS;
463     assert(Vals.size() == NumValsBeforeLHS);
464     Extra = OldExtra;
465   }
466
467   return nullptr;
468 }
469
470 static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) {
471   Instruction *Cond = nullptr;
472   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
473     Cond = dyn_cast<Instruction>(SI->getCondition());
474   } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
475     if (BI->isConditional())
476       Cond = dyn_cast<Instruction>(BI->getCondition());
477   } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(TI)) {
478     Cond = dyn_cast<Instruction>(IBI->getAddress());
479   }
480
481   TI->eraseFromParent();
482   if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond);
483 }
484
485 /// isValueEqualityComparison - Return true if the specified terminator checks
486 /// to see if a value is equal to constant integer value.
487 Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) {
488   Value *CV = nullptr;
489   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
490     // Do not permit merging of large switch instructions into their
491     // predecessors unless there is only one predecessor.
492     if (SI->getNumSuccessors()*std::distance(pred_begin(SI->getParent()),
493                                              pred_end(SI->getParent())) <= 128)
494       CV = SI->getCondition();
495   } else if (BranchInst *BI = dyn_cast<BranchInst>(TI))
496     if (BI->isConditional() && BI->getCondition()->hasOneUse())
497       if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
498         if (ICI->isEquality() && GetConstantInt(ICI->getOperand(1), DL))
499           CV = ICI->getOperand(0);
500
501   // Unwrap any lossless ptrtoint cast.
502   if (DL && CV) {
503     if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV)) {
504       Value *Ptr = PTII->getPointerOperand();
505       if (PTII->getType() == DL->getIntPtrType(Ptr->getType()))
506         CV = Ptr;
507     }
508   }
509   return CV;
510 }
511
512 /// GetValueEqualityComparisonCases - Given a value comparison instruction,
513 /// decode all of the 'cases' that it represents and return the 'default' block.
514 BasicBlock *SimplifyCFGOpt::
515 GetValueEqualityComparisonCases(TerminatorInst *TI,
516                                 std::vector<ValueEqualityComparisonCase>
517                                                                        &Cases) {
518   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
519     Cases.reserve(SI->getNumCases());
520     for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i)
521       Cases.push_back(ValueEqualityComparisonCase(i.getCaseValue(),
522                                                   i.getCaseSuccessor()));
523     return SI->getDefaultDest();
524   }
525
526   BranchInst *BI = cast<BranchInst>(TI);
527   ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
528   BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE);
529   Cases.push_back(ValueEqualityComparisonCase(GetConstantInt(ICI->getOperand(1),
530                                                              DL),
531                                               Succ));
532   return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ);
533 }
534
535
536 /// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries
537 /// in the list that match the specified block.
538 static void EliminateBlockCases(BasicBlock *BB,
539                               std::vector<ValueEqualityComparisonCase> &Cases) {
540   Cases.erase(std::remove(Cases.begin(), Cases.end(), BB), Cases.end());
541 }
542
543 /// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as
544 /// well.
545 static bool
546 ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1,
547               std::vector<ValueEqualityComparisonCase > &C2) {
548   std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
549
550   // Make V1 be smaller than V2.
551   if (V1->size() > V2->size())
552     std::swap(V1, V2);
553
554   if (V1->size() == 0) return false;
555   if (V1->size() == 1) {
556     // Just scan V2.
557     ConstantInt *TheVal = (*V1)[0].Value;
558     for (unsigned i = 0, e = V2->size(); i != e; ++i)
559       if (TheVal == (*V2)[i].Value)
560         return true;
561   }
562
563   // Otherwise, just sort both lists and compare element by element.
564   array_pod_sort(V1->begin(), V1->end());
565   array_pod_sort(V2->begin(), V2->end());
566   unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
567   while (i1 != e1 && i2 != e2) {
568     if ((*V1)[i1].Value == (*V2)[i2].Value)
569       return true;
570     if ((*V1)[i1].Value < (*V2)[i2].Value)
571       ++i1;
572     else
573       ++i2;
574   }
575   return false;
576 }
577
578 /// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a
579 /// terminator instruction and its block is known to only have a single
580 /// predecessor block, check to see if that predecessor is also a value
581 /// comparison with the same value, and if that comparison determines the
582 /// outcome of this comparison.  If so, simplify TI.  This does a very limited
583 /// form of jump threading.
584 bool SimplifyCFGOpt::
585 SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
586                                               BasicBlock *Pred,
587                                               IRBuilder<> &Builder) {
588   Value *PredVal = isValueEqualityComparison(Pred->getTerminator());
589   if (!PredVal) return false;  // Not a value comparison in predecessor.
590
591   Value *ThisVal = isValueEqualityComparison(TI);
592   assert(ThisVal && "This isn't a value comparison!!");
593   if (ThisVal != PredVal) return false;  // Different predicates.
594
595   // TODO: Preserve branch weight metadata, similarly to how
596   // FoldValueComparisonIntoPredecessors preserves it.
597
598   // Find out information about when control will move from Pred to TI's block.
599   std::vector<ValueEqualityComparisonCase> PredCases;
600   BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(),
601                                                         PredCases);
602   EliminateBlockCases(PredDef, PredCases);  // Remove default from cases.
603
604   // Find information about how control leaves this block.
605   std::vector<ValueEqualityComparisonCase> ThisCases;
606   BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
607   EliminateBlockCases(ThisDef, ThisCases);  // Remove default from cases.
608
609   // If TI's block is the default block from Pred's comparison, potentially
610   // simplify TI based on this knowledge.
611   if (PredDef == TI->getParent()) {
612     // If we are here, we know that the value is none of those cases listed in
613     // PredCases.  If there are any cases in ThisCases that are in PredCases, we
614     // can simplify TI.
615     if (!ValuesOverlap(PredCases, ThisCases))
616       return false;
617
618     if (isa<BranchInst>(TI)) {
619       // Okay, one of the successors of this condbr is dead.  Convert it to a
620       // uncond br.
621       assert(ThisCases.size() == 1 && "Branch can only have one case!");
622       // Insert the new branch.
623       Instruction *NI = Builder.CreateBr(ThisDef);
624       (void) NI;
625
626       // Remove PHI node entries for the dead edge.
627       ThisCases[0].Dest->removePredecessor(TI->getParent());
628
629       DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
630            << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");
631
632       EraseTerminatorInstAndDCECond(TI);
633       return true;
634     }
635
636     SwitchInst *SI = cast<SwitchInst>(TI);
637     // Okay, TI has cases that are statically dead, prune them away.
638     SmallPtrSet<Constant*, 16> DeadCases;
639     for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
640       DeadCases.insert(PredCases[i].Value);
641
642     DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
643                  << "Through successor TI: " << *TI);
644
645     // Collect branch weights into a vector.
646     SmallVector<uint32_t, 8> Weights;
647     MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
648     bool HasWeight = MD && (MD->getNumOperands() == 2 + SI->getNumCases());
649     if (HasWeight)
650       for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
651            ++MD_i) {
652         ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(MD_i));
653         assert(CI);
654         Weights.push_back(CI->getValue().getZExtValue());
655       }
656     for (SwitchInst::CaseIt i = SI->case_end(), e = SI->case_begin(); i != e;) {
657       --i;
658       if (DeadCases.count(i.getCaseValue())) {
659         if (HasWeight) {
660           std::swap(Weights[i.getCaseIndex()+1], Weights.back());
661           Weights.pop_back();
662         }
663         i.getCaseSuccessor()->removePredecessor(TI->getParent());
664         SI->removeCase(i);
665       }
666     }
667     if (HasWeight && Weights.size() >= 2)
668       SI->setMetadata(LLVMContext::MD_prof,
669                       MDBuilder(SI->getParent()->getContext()).
670                       createBranchWeights(Weights));
671
672     DEBUG(dbgs() << "Leaving: " << *TI << "\n");
673     return true;
674   }
675
676   // Otherwise, TI's block must correspond to some matched value.  Find out
677   // which value (or set of values) this is.
678   ConstantInt *TIV = nullptr;
679   BasicBlock *TIBB = TI->getParent();
680   for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
681     if (PredCases[i].Dest == TIBB) {
682       if (TIV)
683         return false;  // Cannot handle multiple values coming to this block.
684       TIV = PredCases[i].Value;
685     }
686   assert(TIV && "No edge from pred to succ?");
687
688   // Okay, we found the one constant that our value can be if we get into TI's
689   // BB.  Find out which successor will unconditionally be branched to.
690   BasicBlock *TheRealDest = nullptr;
691   for (unsigned i = 0, e = ThisCases.size(); i != e; ++i)
692     if (ThisCases[i].Value == TIV) {
693       TheRealDest = ThisCases[i].Dest;
694       break;
695     }
696
697   // If not handled by any explicit cases, it is handled by the default case.
698   if (!TheRealDest) TheRealDest = ThisDef;
699
700   // Remove PHI node entries for dead edges.
701   BasicBlock *CheckEdge = TheRealDest;
702   for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI)
703     if (*SI != CheckEdge)
704       (*SI)->removePredecessor(TIBB);
705     else
706       CheckEdge = nullptr;
707
708   // Insert the new branch.
709   Instruction *NI = Builder.CreateBr(TheRealDest);
710   (void) NI;
711
712   DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
713             << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");
714
715   EraseTerminatorInstAndDCECond(TI);
716   return true;
717 }
718
719 namespace {
720   /// ConstantIntOrdering - This class implements a stable ordering of constant
721   /// integers that does not depend on their address.  This is important for
722   /// applications that sort ConstantInt's to ensure uniqueness.
723   struct ConstantIntOrdering {
724     bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const {
725       return LHS->getValue().ult(RHS->getValue());
726     }
727   };
728 }
729
730 static int ConstantIntSortPredicate(ConstantInt *const *P1,
731                                     ConstantInt *const *P2) {
732   const ConstantInt *LHS = *P1;
733   const ConstantInt *RHS = *P2;
734   if (LHS->getValue().ult(RHS->getValue()))
735     return 1;
736   if (LHS->getValue() == RHS->getValue())
737     return 0;
738   return -1;
739 }
740
741 static inline bool HasBranchWeights(const Instruction* I) {
742   MDNode *ProfMD = I->getMetadata(LLVMContext::MD_prof);
743   if (ProfMD && ProfMD->getOperand(0))
744     if (MDString* MDS = dyn_cast<MDString>(ProfMD->getOperand(0)))
745       return MDS->getString().equals("branch_weights");
746
747   return false;
748 }
749
750 /// Get Weights of a given TerminatorInst, the default weight is at the front
751 /// of the vector. If TI is a conditional eq, we need to swap the branch-weight
752 /// metadata.
753 static void GetBranchWeights(TerminatorInst *TI,
754                              SmallVectorImpl<uint64_t> &Weights) {
755   MDNode *MD = TI->getMetadata(LLVMContext::MD_prof);
756   assert(MD);
757   for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) {
758     ConstantInt *CI = cast<ConstantInt>(MD->getOperand(i));
759     Weights.push_back(CI->getValue().getZExtValue());
760   }
761
762   // If TI is a conditional eq, the default case is the false case,
763   // and the corresponding branch-weight data is at index 2. We swap the
764   // default weight to be the first entry.
765   if (BranchInst* BI = dyn_cast<BranchInst>(TI)) {
766     assert(Weights.size() == 2);
767     ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
768     if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
769       std::swap(Weights.front(), Weights.back());
770   }
771 }
772
773 /// Keep halving the weights until all can fit in uint32_t.
774 static void FitWeights(MutableArrayRef<uint64_t> Weights) {
775   uint64_t Max = *std::max_element(Weights.begin(), Weights.end());
776   if (Max > UINT_MAX) {
777     unsigned Offset = 32 - countLeadingZeros(Max);
778     for (uint64_t &I : Weights)
779       I >>= Offset;
780   }
781 }
782
783 /// FoldValueComparisonIntoPredecessors - The specified terminator is a value
784 /// equality comparison instruction (either a switch or a branch on "X == c").
785 /// See if any of the predecessors of the terminator block are value comparisons
786 /// on the same value.  If so, and if safe to do so, fold them together.
787 bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
788                                                          IRBuilder<> &Builder) {
789   BasicBlock *BB = TI->getParent();
790   Value *CV = isValueEqualityComparison(TI);  // CondVal
791   assert(CV && "Not a comparison?");
792   bool Changed = false;
793
794   SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB));
795   while (!Preds.empty()) {
796     BasicBlock *Pred = Preds.pop_back_val();
797
798     // See if the predecessor is a comparison with the same value.
799     TerminatorInst *PTI = Pred->getTerminator();
800     Value *PCV = isValueEqualityComparison(PTI);  // PredCondVal
801
802     if (PCV == CV && SafeToMergeTerminators(TI, PTI)) {
803       // Figure out which 'cases' to copy from SI to PSI.
804       std::vector<ValueEqualityComparisonCase> BBCases;
805       BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
806
807       std::vector<ValueEqualityComparisonCase> PredCases;
808       BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
809
810       // Based on whether the default edge from PTI goes to BB or not, fill in
811       // PredCases and PredDefault with the new switch cases we would like to
812       // build.
813       SmallVector<BasicBlock*, 8> NewSuccessors;
814
815       // Update the branch weight metadata along the way
816       SmallVector<uint64_t, 8> Weights;
817       bool PredHasWeights = HasBranchWeights(PTI);
818       bool SuccHasWeights = HasBranchWeights(TI);
819
820       if (PredHasWeights) {
821         GetBranchWeights(PTI, Weights);
822         // branch-weight metadata is inconsistent here.
823         if (Weights.size() != 1 + PredCases.size())
824           PredHasWeights = SuccHasWeights = false;
825       } else if (SuccHasWeights)
826         // If there are no predecessor weights but there are successor weights,
827         // populate Weights with 1, which will later be scaled to the sum of
828         // successor's weights
829         Weights.assign(1 + PredCases.size(), 1);
830
831       SmallVector<uint64_t, 8> SuccWeights;
832       if (SuccHasWeights) {
833         GetBranchWeights(TI, SuccWeights);
834         // branch-weight metadata is inconsistent here.
835         if (SuccWeights.size() != 1 + BBCases.size())
836           PredHasWeights = SuccHasWeights = false;
837       } else if (PredHasWeights)
838         SuccWeights.assign(1 + BBCases.size(), 1);
839
840       if (PredDefault == BB) {
841         // If this is the default destination from PTI, only the edges in TI
842         // that don't occur in PTI, or that branch to BB will be activated.
843         std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
844         for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
845           if (PredCases[i].Dest != BB)
846             PTIHandled.insert(PredCases[i].Value);
847           else {
848             // The default destination is BB, we don't need explicit targets.
849             std::swap(PredCases[i], PredCases.back());
850
851             if (PredHasWeights || SuccHasWeights) {
852               // Increase weight for the default case.
853               Weights[0] += Weights[i+1];
854               std::swap(Weights[i+1], Weights.back());
855               Weights.pop_back();
856             }
857
858             PredCases.pop_back();
859             --i; --e;
860           }
861
862         // Reconstruct the new switch statement we will be building.
863         if (PredDefault != BBDefault) {
864           PredDefault->removePredecessor(Pred);
865           PredDefault = BBDefault;
866           NewSuccessors.push_back(BBDefault);
867         }
868
869         unsigned CasesFromPred = Weights.size();
870         uint64_t ValidTotalSuccWeight = 0;
871         for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
872           if (!PTIHandled.count(BBCases[i].Value) &&
873               BBCases[i].Dest != BBDefault) {
874             PredCases.push_back(BBCases[i]);
875             NewSuccessors.push_back(BBCases[i].Dest);
876             if (SuccHasWeights || PredHasWeights) {
877               // The default weight is at index 0, so weight for the ith case
878               // should be at index i+1. Scale the cases from successor by
879               // PredDefaultWeight (Weights[0]).
880               Weights.push_back(Weights[0] * SuccWeights[i+1]);
881               ValidTotalSuccWeight += SuccWeights[i+1];
882             }
883           }
884
885         if (SuccHasWeights || PredHasWeights) {
886           ValidTotalSuccWeight += SuccWeights[0];
887           // Scale the cases from predecessor by ValidTotalSuccWeight.
888           for (unsigned i = 1; i < CasesFromPred; ++i)
889             Weights[i] *= ValidTotalSuccWeight;
890           // Scale the default weight by SuccDefaultWeight (SuccWeights[0]).
891           Weights[0] *= SuccWeights[0];
892         }
893       } else {
894         // If this is not the default destination from PSI, only the edges
895         // in SI that occur in PSI with a destination of BB will be
896         // activated.
897         std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
898         std::map<ConstantInt*, uint64_t> WeightsForHandled;
899         for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
900           if (PredCases[i].Dest == BB) {
901             PTIHandled.insert(PredCases[i].Value);
902
903             if (PredHasWeights || SuccHasWeights) {
904               WeightsForHandled[PredCases[i].Value] = Weights[i+1];
905               std::swap(Weights[i+1], Weights.back());
906               Weights.pop_back();
907             }
908
909             std::swap(PredCases[i], PredCases.back());
910             PredCases.pop_back();
911             --i; --e;
912           }
913
914         // Okay, now we know which constants were sent to BB from the
915         // predecessor.  Figure out where they will all go now.
916         for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
917           if (PTIHandled.count(BBCases[i].Value)) {
918             // If this is one we are capable of getting...
919             if (PredHasWeights || SuccHasWeights)
920               Weights.push_back(WeightsForHandled[BBCases[i].Value]);
921             PredCases.push_back(BBCases[i]);
922             NewSuccessors.push_back(BBCases[i].Dest);
923             PTIHandled.erase(BBCases[i].Value);// This constant is taken care of
924           }
925
926         // If there are any constants vectored to BB that TI doesn't handle,
927         // they must go to the default destination of TI.
928         for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I =
929                                     PTIHandled.begin(),
930                E = PTIHandled.end(); I != E; ++I) {
931           if (PredHasWeights || SuccHasWeights)
932             Weights.push_back(WeightsForHandled[*I]);
933           PredCases.push_back(ValueEqualityComparisonCase(*I, BBDefault));
934           NewSuccessors.push_back(BBDefault);
935         }
936       }
937
938       // Okay, at this point, we know which new successor Pred will get.  Make
939       // sure we update the number of entries in the PHI nodes for these
940       // successors.
941       for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i)
942         AddPredecessorToBlock(NewSuccessors[i], Pred, BB);
943
944       Builder.SetInsertPoint(PTI);
945       // Convert pointer to int before we switch.
946       if (CV->getType()->isPointerTy()) {
947         assert(DL && "Cannot switch on pointer without DataLayout");
948         CV = Builder.CreatePtrToInt(CV, DL->getIntPtrType(CV->getType()),
949                                     "magicptr");
950       }
951
952       // Now that the successors are updated, create the new Switch instruction.
953       SwitchInst *NewSI = Builder.CreateSwitch(CV, PredDefault,
954                                                PredCases.size());
955       NewSI->setDebugLoc(PTI->getDebugLoc());
956       for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
957         NewSI->addCase(PredCases[i].Value, PredCases[i].Dest);
958
959       if (PredHasWeights || SuccHasWeights) {
960         // Halve the weights if any of them cannot fit in an uint32_t
961         FitWeights(Weights);
962
963         SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
964
965         NewSI->setMetadata(LLVMContext::MD_prof,
966                            MDBuilder(BB->getContext()).
967                            createBranchWeights(MDWeights));
968       }
969
970       EraseTerminatorInstAndDCECond(PTI);
971
972       // Okay, last check.  If BB is still a successor of PSI, then we must
973       // have an infinite loop case.  If so, add an infinitely looping block
974       // to handle the case to preserve the behavior of the code.
975       BasicBlock *InfLoopBlock = nullptr;
976       for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i)
977         if (NewSI->getSuccessor(i) == BB) {
978           if (!InfLoopBlock) {
979             // Insert it at the end of the function, because it's either code,
980             // or it won't matter if it's hot. :)
981             InfLoopBlock = BasicBlock::Create(BB->getContext(),
982                                               "infloop", BB->getParent());
983             BranchInst::Create(InfLoopBlock, InfLoopBlock);
984           }
985           NewSI->setSuccessor(i, InfLoopBlock);
986         }
987
988       Changed = true;
989     }
990   }
991   return Changed;
992 }
993
994 // isSafeToHoistInvoke - If we would need to insert a select that uses the
995 // value of this invoke (comments in HoistThenElseCodeToIf explain why we
996 // would need to do this), we can't hoist the invoke, as there is nowhere
997 // to put the select in this case.
998 static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2,
999                                 Instruction *I1, Instruction *I2) {
1000   for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
1001     PHINode *PN;
1002     for (BasicBlock::iterator BBI = SI->begin();
1003          (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
1004       Value *BB1V = PN->getIncomingValueForBlock(BB1);
1005       Value *BB2V = PN->getIncomingValueForBlock(BB2);
1006       if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) {
1007         return false;
1008       }
1009     }
1010   }
1011   return true;
1012 }
1013
1014 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I);
1015
1016 /// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and
1017 /// BB2, hoist any common code in the two blocks up into the branch block.  The
1018 /// caller of this function guarantees that BI's block dominates BB1 and BB2.
1019 static bool HoistThenElseCodeToIf(BranchInst *BI, const DataLayout *DL) {
1020   // This does very trivial matching, with limited scanning, to find identical
1021   // instructions in the two blocks.  In particular, we don't want to get into
1022   // O(M*N) situations here where M and N are the sizes of BB1 and BB2.  As
1023   // such, we currently just scan for obviously identical instructions in an
1024   // identical order.
1025   BasicBlock *BB1 = BI->getSuccessor(0);  // The true destination.
1026   BasicBlock *BB2 = BI->getSuccessor(1);  // The false destination
1027
1028   BasicBlock::iterator BB1_Itr = BB1->begin();
1029   BasicBlock::iterator BB2_Itr = BB2->begin();
1030
1031   Instruction *I1 = BB1_Itr++, *I2 = BB2_Itr++;
1032   // Skip debug info if it is not identical.
1033   DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
1034   DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
1035   if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
1036     while (isa<DbgInfoIntrinsic>(I1))
1037       I1 = BB1_Itr++;
1038     while (isa<DbgInfoIntrinsic>(I2))
1039       I2 = BB2_Itr++;
1040   }
1041   if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) ||
1042       (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)))
1043     return false;
1044
1045   BasicBlock *BIParent = BI->getParent();
1046
1047   bool Changed = false;
1048   do {
1049     // If we are hoisting the terminator instruction, don't move one (making a
1050     // broken BB), instead clone it, and remove BI.
1051     if (isa<TerminatorInst>(I1))
1052       goto HoistTerminator;
1053
1054     // For a normal instruction, we just move one to right before the branch,
1055     // then replace all uses of the other with the first.  Finally, we remove
1056     // the now redundant second instruction.
1057     BIParent->getInstList().splice(BI, BB1->getInstList(), I1);
1058     if (!I2->use_empty())
1059       I2->replaceAllUsesWith(I1);
1060     I1->intersectOptionalDataWith(I2);
1061     unsigned KnownIDs[] = {
1062       LLVMContext::MD_tbaa,
1063       LLVMContext::MD_range,
1064       LLVMContext::MD_fpmath,
1065       LLVMContext::MD_invariant_load,
1066       LLVMContext::MD_nonnull
1067     };
1068     combineMetadata(I1, I2, KnownIDs);
1069     I2->eraseFromParent();
1070     Changed = true;
1071
1072     I1 = BB1_Itr++;
1073     I2 = BB2_Itr++;
1074     // Skip debug info if it is not identical.
1075     DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
1076     DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
1077     if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
1078       while (isa<DbgInfoIntrinsic>(I1))
1079         I1 = BB1_Itr++;
1080       while (isa<DbgInfoIntrinsic>(I2))
1081         I2 = BB2_Itr++;
1082     }
1083   } while (I1->isIdenticalToWhenDefined(I2));
1084
1085   return true;
1086
1087 HoistTerminator:
1088   // It may not be possible to hoist an invoke.
1089   if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))
1090     return Changed;
1091
1092   for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
1093     PHINode *PN;
1094     for (BasicBlock::iterator BBI = SI->begin();
1095          (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
1096       Value *BB1V = PN->getIncomingValueForBlock(BB1);
1097       Value *BB2V = PN->getIncomingValueForBlock(BB2);
1098       if (BB1V == BB2V)
1099         continue;
1100
1101       // Check for passingValueIsAlwaysUndefined here because we would rather
1102       // eliminate undefined control flow then converting it to a select.
1103       if (passingValueIsAlwaysUndefined(BB1V, PN) ||
1104           passingValueIsAlwaysUndefined(BB2V, PN))
1105        return Changed;
1106
1107       if (isa<ConstantExpr>(BB1V) && !isSafeToSpeculativelyExecute(BB1V, DL))
1108         return Changed;
1109       if (isa<ConstantExpr>(BB2V) && !isSafeToSpeculativelyExecute(BB2V, DL))
1110         return Changed;
1111     }
1112   }
1113
1114   // Okay, it is safe to hoist the terminator.
1115   Instruction *NT = I1->clone();
1116   BIParent->getInstList().insert(BI, NT);
1117   if (!NT->getType()->isVoidTy()) {
1118     I1->replaceAllUsesWith(NT);
1119     I2->replaceAllUsesWith(NT);
1120     NT->takeName(I1);
1121   }
1122
1123   IRBuilder<true, NoFolder> Builder(NT);
1124   // Hoisting one of the terminators from our successor is a great thing.
1125   // Unfortunately, the successors of the if/else blocks may have PHI nodes in
1126   // them.  If they do, all PHI entries for BB1/BB2 must agree for all PHI
1127   // nodes, so we insert select instruction to compute the final result.
1128   std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects;
1129   for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
1130     PHINode *PN;
1131     for (BasicBlock::iterator BBI = SI->begin();
1132          (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
1133       Value *BB1V = PN->getIncomingValueForBlock(BB1);
1134       Value *BB2V = PN->getIncomingValueForBlock(BB2);
1135       if (BB1V == BB2V) continue;
1136
1137       // These values do not agree.  Insert a select instruction before NT
1138       // that determines the right value.
1139       SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1140       if (!SI)
1141         SI = cast<SelectInst>
1142           (Builder.CreateSelect(BI->getCondition(), BB1V, BB2V,
1143                                 BB1V->getName()+"."+BB2V->getName()));
1144
1145       // Make the PHI node use the select for all incoming values for BB1/BB2
1146       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1147         if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2)
1148           PN->setIncomingValue(i, SI);
1149     }
1150   }
1151
1152   // Update any PHI nodes in our new successors.
1153   for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI)
1154     AddPredecessorToBlock(*SI, BIParent, BB1);
1155
1156   EraseTerminatorInstAndDCECond(BI);
1157   return true;
1158 }
1159
1160 /// SinkThenElseCodeToEnd - Given an unconditional branch that goes to BBEnd,
1161 /// check whether BBEnd has only two predecessors and the other predecessor
1162 /// ends with an unconditional branch. If it is true, sink any common code
1163 /// in the two predecessors to BBEnd.
1164 static bool SinkThenElseCodeToEnd(BranchInst *BI1) {
1165   assert(BI1->isUnconditional());
1166   BasicBlock *BB1 = BI1->getParent();
1167   BasicBlock *BBEnd = BI1->getSuccessor(0);
1168
1169   // Check that BBEnd has two predecessors and the other predecessor ends with
1170   // an unconditional branch.
1171   pred_iterator PI = pred_begin(BBEnd), PE = pred_end(BBEnd);
1172   BasicBlock *Pred0 = *PI++;
1173   if (PI == PE) // Only one predecessor.
1174     return false;
1175   BasicBlock *Pred1 = *PI++;
1176   if (PI != PE) // More than two predecessors.
1177     return false;
1178   BasicBlock *BB2 = (Pred0 == BB1) ? Pred1 : Pred0;
1179   BranchInst *BI2 = dyn_cast<BranchInst>(BB2->getTerminator());
1180   if (!BI2 || !BI2->isUnconditional())
1181     return false;
1182
1183   // Gather the PHI nodes in BBEnd.
1184   std::map<Value*, std::pair<Value*, PHINode*> > MapValueFromBB1ToBB2;
1185   Instruction *FirstNonPhiInBBEnd = nullptr;
1186   for (BasicBlock::iterator I = BBEnd->begin(), E = BBEnd->end();
1187        I != E; ++I) {
1188     if (PHINode *PN = dyn_cast<PHINode>(I)) {
1189       Value *BB1V = PN->getIncomingValueForBlock(BB1);
1190       Value *BB2V = PN->getIncomingValueForBlock(BB2);
1191       MapValueFromBB1ToBB2[BB1V] = std::make_pair(BB2V, PN);
1192     } else {
1193       FirstNonPhiInBBEnd = &*I;
1194       break;
1195     }
1196   }
1197   if (!FirstNonPhiInBBEnd)
1198     return false;
1199
1200
1201   // This does very trivial matching, with limited scanning, to find identical
1202   // instructions in the two blocks.  We scan backward for obviously identical
1203   // instructions in an identical order.
1204   BasicBlock::InstListType::reverse_iterator RI1 = BB1->getInstList().rbegin(),
1205       RE1 = BB1->getInstList().rend(), RI2 = BB2->getInstList().rbegin(),
1206       RE2 = BB2->getInstList().rend();
1207   // Skip debug info.
1208   while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) ++RI1;
1209   if (RI1 == RE1)
1210     return false;
1211   while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) ++RI2;
1212   if (RI2 == RE2)
1213     return false;
1214   // Skip the unconditional branches.
1215   ++RI1;
1216   ++RI2;
1217
1218   bool Changed = false;
1219   while (RI1 != RE1 && RI2 != RE2) {
1220     // Skip debug info.
1221     while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) ++RI1;
1222     if (RI1 == RE1)
1223       return Changed;
1224     while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) ++RI2;
1225     if (RI2 == RE2)
1226       return Changed;
1227
1228     Instruction *I1 = &*RI1, *I2 = &*RI2;
1229     // I1 and I2 should have a single use in the same PHI node, and they
1230     // perform the same operation.
1231     // Cannot move control-flow-involving, volatile loads, vaarg, etc.
1232     if (isa<PHINode>(I1) || isa<PHINode>(I2) ||
1233         isa<TerminatorInst>(I1) || isa<TerminatorInst>(I2) ||
1234         isa<LandingPadInst>(I1) || isa<LandingPadInst>(I2) ||
1235         isa<AllocaInst>(I1) || isa<AllocaInst>(I2) ||
1236         I1->mayHaveSideEffects() || I2->mayHaveSideEffects() ||
1237         I1->mayReadOrWriteMemory() || I2->mayReadOrWriteMemory() ||
1238         !I1->hasOneUse() || !I2->hasOneUse() ||
1239         MapValueFromBB1ToBB2.find(I1) == MapValueFromBB1ToBB2.end() ||
1240         MapValueFromBB1ToBB2[I1].first != I2)
1241       return Changed;
1242
1243     // Check whether we should swap the operands of ICmpInst.
1244     ICmpInst *ICmp1 = dyn_cast<ICmpInst>(I1), *ICmp2 = dyn_cast<ICmpInst>(I2);
1245     bool SwapOpnds = false;
1246     if (ICmp1 && ICmp2 &&
1247         ICmp1->getOperand(0) != ICmp2->getOperand(0) &&
1248         ICmp1->getOperand(1) != ICmp2->getOperand(1) &&
1249         (ICmp1->getOperand(0) == ICmp2->getOperand(1) ||
1250          ICmp1->getOperand(1) == ICmp2->getOperand(0))) {
1251       ICmp2->swapOperands();
1252       SwapOpnds = true;
1253     }
1254     if (!I1->isSameOperationAs(I2)) {
1255       if (SwapOpnds)
1256         ICmp2->swapOperands();
1257       return Changed;
1258     }
1259
1260     // The operands should be either the same or they need to be generated
1261     // with a PHI node after sinking. We only handle the case where there is
1262     // a single pair of different operands.
1263     Value *DifferentOp1 = nullptr, *DifferentOp2 = nullptr;
1264     unsigned Op1Idx = 0;
1265     for (unsigned I = 0, E = I1->getNumOperands(); I != E; ++I) {
1266       if (I1->getOperand(I) == I2->getOperand(I))
1267         continue;
1268       // Early exit if we have more-than one pair of different operands or
1269       // the different operand is already in MapValueFromBB1ToBB2.
1270       // Early exit if we need a PHI node to replace a constant.
1271       if (DifferentOp1 ||
1272           MapValueFromBB1ToBB2.find(I1->getOperand(I)) !=
1273           MapValueFromBB1ToBB2.end() ||
1274           isa<Constant>(I1->getOperand(I)) ||
1275           isa<Constant>(I2->getOperand(I))) {
1276         // If we can't sink the instructions, undo the swapping.
1277         if (SwapOpnds)
1278           ICmp2->swapOperands();
1279         return Changed;
1280       }
1281       DifferentOp1 = I1->getOperand(I);
1282       Op1Idx = I;
1283       DifferentOp2 = I2->getOperand(I);
1284     }
1285
1286     // We insert the pair of different operands to MapValueFromBB1ToBB2 and
1287     // remove (I1, I2) from MapValueFromBB1ToBB2.
1288     if (DifferentOp1) {
1289       PHINode *NewPN = PHINode::Create(DifferentOp1->getType(), 2,
1290                                        DifferentOp1->getName() + ".sink",
1291                                        BBEnd->begin());
1292       MapValueFromBB1ToBB2[DifferentOp1] = std::make_pair(DifferentOp2, NewPN);
1293       // I1 should use NewPN instead of DifferentOp1.
1294       I1->setOperand(Op1Idx, NewPN);
1295       NewPN->addIncoming(DifferentOp1, BB1);
1296       NewPN->addIncoming(DifferentOp2, BB2);
1297       DEBUG(dbgs() << "Create PHI node " << *NewPN << "\n";);
1298     }
1299     PHINode *OldPN = MapValueFromBB1ToBB2[I1].second;
1300     MapValueFromBB1ToBB2.erase(I1);
1301
1302     DEBUG(dbgs() << "SINK common instructions " << *I1 << "\n";);
1303     DEBUG(dbgs() << "                         " << *I2 << "\n";);
1304     // We need to update RE1 and RE2 if we are going to sink the first
1305     // instruction in the basic block down.
1306     bool UpdateRE1 = (I1 == BB1->begin()), UpdateRE2 = (I2 == BB2->begin());
1307     // Sink the instruction.
1308     BBEnd->getInstList().splice(FirstNonPhiInBBEnd, BB1->getInstList(), I1);
1309     if (!OldPN->use_empty())
1310       OldPN->replaceAllUsesWith(I1);
1311     OldPN->eraseFromParent();
1312
1313     if (!I2->use_empty())
1314       I2->replaceAllUsesWith(I1);
1315     I1->intersectOptionalDataWith(I2);
1316     // TODO: Use combineMetadata here to preserve what metadata we can
1317     // (analogous to the hoisting case above).
1318     I2->eraseFromParent();
1319
1320     if (UpdateRE1)
1321       RE1 = BB1->getInstList().rend();
1322     if (UpdateRE2)
1323       RE2 = BB2->getInstList().rend();
1324     FirstNonPhiInBBEnd = I1;
1325     NumSinkCommons++;
1326     Changed = true;
1327   }
1328   return Changed;
1329 }
1330
1331 /// \brief Determine if we can hoist sink a sole store instruction out of a
1332 /// conditional block.
1333 ///
1334 /// We are looking for code like the following:
1335 ///   BrBB:
1336 ///     store i32 %add, i32* %arrayidx2
1337 ///     ... // No other stores or function calls (we could be calling a memory
1338 ///     ... // function).
1339 ///     %cmp = icmp ult %x, %y
1340 ///     br i1 %cmp, label %EndBB, label %ThenBB
1341 ///   ThenBB:
1342 ///     store i32 %add5, i32* %arrayidx2
1343 ///     br label EndBB
1344 ///   EndBB:
1345 ///     ...
1346 ///   We are going to transform this into:
1347 ///   BrBB:
1348 ///     store i32 %add, i32* %arrayidx2
1349 ///     ... //
1350 ///     %cmp = icmp ult %x, %y
1351 ///     %add.add5 = select i1 %cmp, i32 %add, %add5
1352 ///     store i32 %add.add5, i32* %arrayidx2
1353 ///     ...
1354 ///
1355 /// \return The pointer to the value of the previous store if the store can be
1356 ///         hoisted into the predecessor block. 0 otherwise.
1357 static Value *isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB,
1358                                      BasicBlock *StoreBB, BasicBlock *EndBB) {
1359   StoreInst *StoreToHoist = dyn_cast<StoreInst>(I);
1360   if (!StoreToHoist)
1361     return nullptr;
1362
1363   // Volatile or atomic.
1364   if (!StoreToHoist->isSimple())
1365     return nullptr;
1366
1367   Value *StorePtr = StoreToHoist->getPointerOperand();
1368
1369   // Look for a store to the same pointer in BrBB.
1370   unsigned MaxNumInstToLookAt = 10;
1371   for (BasicBlock::reverse_iterator RI = BrBB->rbegin(),
1372        RE = BrBB->rend(); RI != RE && (--MaxNumInstToLookAt); ++RI) {
1373     Instruction *CurI = &*RI;
1374
1375     // Could be calling an instruction that effects memory like free().
1376     if (CurI->mayHaveSideEffects() && !isa<StoreInst>(CurI))
1377       return nullptr;
1378
1379     StoreInst *SI = dyn_cast<StoreInst>(CurI);
1380     // Found the previous store make sure it stores to the same location.
1381     if (SI && SI->getPointerOperand() == StorePtr)
1382       // Found the previous store, return its value operand.
1383       return SI->getValueOperand();
1384     else if (SI)
1385       return nullptr; // Unknown store.
1386   }
1387
1388   return nullptr;
1389 }
1390
1391 /// \brief Speculate a conditional basic block flattening the CFG.
1392 ///
1393 /// Note that this is a very risky transform currently. Speculating
1394 /// instructions like this is most often not desirable. Instead, there is an MI
1395 /// pass which can do it with full awareness of the resource constraints.
1396 /// However, some cases are "obvious" and we should do directly. An example of
1397 /// this is speculating a single, reasonably cheap instruction.
1398 ///
1399 /// There is only one distinct advantage to flattening the CFG at the IR level:
1400 /// it makes very common but simplistic optimizations such as are common in
1401 /// instcombine and the DAG combiner more powerful by removing CFG edges and
1402 /// modeling their effects with easier to reason about SSA value graphs.
1403 ///
1404 ///
1405 /// An illustration of this transform is turning this IR:
1406 /// \code
1407 ///   BB:
1408 ///     %cmp = icmp ult %x, %y
1409 ///     br i1 %cmp, label %EndBB, label %ThenBB
1410 ///   ThenBB:
1411 ///     %sub = sub %x, %y
1412 ///     br label BB2
1413 ///   EndBB:
1414 ///     %phi = phi [ %sub, %ThenBB ], [ 0, %EndBB ]
1415 ///     ...
1416 /// \endcode
1417 ///
1418 /// Into this IR:
1419 /// \code
1420 ///   BB:
1421 ///     %cmp = icmp ult %x, %y
1422 ///     %sub = sub %x, %y
1423 ///     %cond = select i1 %cmp, 0, %sub
1424 ///     ...
1425 /// \endcode
1426 ///
1427 /// \returns true if the conditional block is removed.
1428 static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB,
1429                                    const DataLayout *DL) {
1430   // Be conservative for now. FP select instruction can often be expensive.
1431   Value *BrCond = BI->getCondition();
1432   if (isa<FCmpInst>(BrCond))
1433     return false;
1434
1435   BasicBlock *BB = BI->getParent();
1436   BasicBlock *EndBB = ThenBB->getTerminator()->getSuccessor(0);
1437
1438   // If ThenBB is actually on the false edge of the conditional branch, remember
1439   // to swap the select operands later.
1440   bool Invert = false;
1441   if (ThenBB != BI->getSuccessor(0)) {
1442     assert(ThenBB == BI->getSuccessor(1) && "No edge from 'if' block?");
1443     Invert = true;
1444   }
1445   assert(EndBB == BI->getSuccessor(!Invert) && "No edge from to end block");
1446
1447   // Keep a count of how many times instructions are used within CondBB when
1448   // they are candidates for sinking into CondBB. Specifically:
1449   // - They are defined in BB, and
1450   // - They have no side effects, and
1451   // - All of their uses are in CondBB.
1452   SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
1453
1454   unsigned SpeculationCost = 0;
1455   Value *SpeculatedStoreValue = nullptr;
1456   StoreInst *SpeculatedStore = nullptr;
1457   for (BasicBlock::iterator BBI = ThenBB->begin(),
1458                             BBE = std::prev(ThenBB->end());
1459        BBI != BBE; ++BBI) {
1460     Instruction *I = BBI;
1461     // Skip debug info.
1462     if (isa<DbgInfoIntrinsic>(I))
1463       continue;
1464
1465     // Only speculatively execution a single instruction (not counting the
1466     // terminator) for now.
1467     ++SpeculationCost;
1468     if (SpeculationCost > 1)
1469       return false;
1470
1471     // Don't hoist the instruction if it's unsafe or expensive.
1472     if (!isSafeToSpeculativelyExecute(I, DL) &&
1473         !(HoistCondStores &&
1474           (SpeculatedStoreValue = isSafeToSpeculateStore(I, BB, ThenBB,
1475                                                          EndBB))))
1476       return false;
1477     if (!SpeculatedStoreValue &&
1478         ComputeSpeculationCost(I, DL) > PHINodeFoldingThreshold)
1479       return false;
1480
1481     // Store the store speculation candidate.
1482     if (SpeculatedStoreValue)
1483       SpeculatedStore = cast<StoreInst>(I);
1484
1485     // Do not hoist the instruction if any of its operands are defined but not
1486     // used in BB. The transformation will prevent the operand from
1487     // being sunk into the use block.
1488     for (User::op_iterator i = I->op_begin(), e = I->op_end();
1489          i != e; ++i) {
1490       Instruction *OpI = dyn_cast<Instruction>(*i);
1491       if (!OpI || OpI->getParent() != BB ||
1492           OpI->mayHaveSideEffects())
1493         continue; // Not a candidate for sinking.
1494
1495       ++SinkCandidateUseCounts[OpI];
1496     }
1497   }
1498
1499   // Consider any sink candidates which are only used in CondBB as costs for
1500   // speculation. Note, while we iterate over a DenseMap here, we are summing
1501   // and so iteration order isn't significant.
1502   for (SmallDenseMap<Instruction *, unsigned, 4>::iterator I =
1503            SinkCandidateUseCounts.begin(), E = SinkCandidateUseCounts.end();
1504        I != E; ++I)
1505     if (I->first->getNumUses() == I->second) {
1506       ++SpeculationCost;
1507       if (SpeculationCost > 1)
1508         return false;
1509     }
1510
1511   // Check that the PHI nodes can be converted to selects.
1512   bool HaveRewritablePHIs = false;
1513   for (BasicBlock::iterator I = EndBB->begin();
1514        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
1515     Value *OrigV = PN->getIncomingValueForBlock(BB);
1516     Value *ThenV = PN->getIncomingValueForBlock(ThenBB);
1517
1518     // FIXME: Try to remove some of the duplication with HoistThenElseCodeToIf.
1519     // Skip PHIs which are trivial.
1520     if (ThenV == OrigV)
1521       continue;
1522
1523     // Don't convert to selects if we could remove undefined behavior instead.
1524     if (passingValueIsAlwaysUndefined(OrigV, PN) ||
1525         passingValueIsAlwaysUndefined(ThenV, PN))
1526       return false;
1527
1528     HaveRewritablePHIs = true;
1529     ConstantExpr *OrigCE = dyn_cast<ConstantExpr>(OrigV);
1530     ConstantExpr *ThenCE = dyn_cast<ConstantExpr>(ThenV);
1531     if (!OrigCE && !ThenCE)
1532       continue; // Known safe and cheap.
1533
1534     if ((ThenCE && !isSafeToSpeculativelyExecute(ThenCE, DL)) ||
1535         (OrigCE && !isSafeToSpeculativelyExecute(OrigCE, DL)))
1536       return false;
1537     unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE, DL) : 0;
1538     unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE, DL) : 0;
1539     if (OrigCost + ThenCost > 2 * PHINodeFoldingThreshold)
1540       return false;
1541
1542     // Account for the cost of an unfolded ConstantExpr which could end up
1543     // getting expanded into Instructions.
1544     // FIXME: This doesn't account for how many operations are combined in the
1545     // constant expression.
1546     ++SpeculationCost;
1547     if (SpeculationCost > 1)
1548       return false;
1549   }
1550
1551   // If there are no PHIs to process, bail early. This helps ensure idempotence
1552   // as well.
1553   if (!HaveRewritablePHIs && !(HoistCondStores && SpeculatedStoreValue))
1554     return false;
1555
1556   // If we get here, we can hoist the instruction and if-convert.
1557   DEBUG(dbgs() << "SPECULATIVELY EXECUTING BB" << *ThenBB << "\n";);
1558
1559   // Insert a select of the value of the speculated store.
1560   if (SpeculatedStoreValue) {
1561     IRBuilder<true, NoFolder> Builder(BI);
1562     Value *TrueV = SpeculatedStore->getValueOperand();
1563     Value *FalseV = SpeculatedStoreValue;
1564     if (Invert)
1565       std::swap(TrueV, FalseV);
1566     Value *S = Builder.CreateSelect(BrCond, TrueV, FalseV, TrueV->getName() +
1567                                     "." + FalseV->getName());
1568     SpeculatedStore->setOperand(0, S);
1569   }
1570
1571   // Hoist the instructions.
1572   BB->getInstList().splice(BI, ThenBB->getInstList(), ThenBB->begin(),
1573                            std::prev(ThenBB->end()));
1574
1575   // Insert selects and rewrite the PHI operands.
1576   IRBuilder<true, NoFolder> Builder(BI);
1577   for (BasicBlock::iterator I = EndBB->begin();
1578        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
1579     unsigned OrigI = PN->getBasicBlockIndex(BB);
1580     unsigned ThenI = PN->getBasicBlockIndex(ThenBB);
1581     Value *OrigV = PN->getIncomingValue(OrigI);
1582     Value *ThenV = PN->getIncomingValue(ThenI);
1583
1584     // Skip PHIs which are trivial.
1585     if (OrigV == ThenV)
1586       continue;
1587
1588     // Create a select whose true value is the speculatively executed value and
1589     // false value is the preexisting value. Swap them if the branch
1590     // destinations were inverted.
1591     Value *TrueV = ThenV, *FalseV = OrigV;
1592     if (Invert)
1593       std::swap(TrueV, FalseV);
1594     Value *V = Builder.CreateSelect(BrCond, TrueV, FalseV,
1595                                     TrueV->getName() + "." + FalseV->getName());
1596     PN->setIncomingValue(OrigI, V);
1597     PN->setIncomingValue(ThenI, V);
1598   }
1599
1600   ++NumSpeculations;
1601   return true;
1602 }
1603
1604 /// \returns True if this block contains a CallInst with the NoDuplicate
1605 /// attribute.
1606 static bool HasNoDuplicateCall(const BasicBlock *BB) {
1607   for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
1608     const CallInst *CI = dyn_cast<CallInst>(I);
1609     if (!CI)
1610       continue;
1611     if (CI->cannotDuplicate())
1612       return true;
1613   }
1614   return false;
1615 }
1616
1617 /// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch
1618 /// across this block.
1619 static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) {
1620   BranchInst *BI = cast<BranchInst>(BB->getTerminator());
1621   unsigned Size = 0;
1622
1623   for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) {
1624     if (isa<DbgInfoIntrinsic>(BBI))
1625       continue;
1626     if (Size > 10) return false;  // Don't clone large BB's.
1627     ++Size;
1628
1629     // We can only support instructions that do not define values that are
1630     // live outside of the current basic block.
1631     for (User *U : BBI->users()) {
1632       Instruction *UI = cast<Instruction>(U);
1633       if (UI->getParent() != BB || isa<PHINode>(UI)) return false;
1634     }
1635
1636     // Looks ok, continue checking.
1637   }
1638
1639   return true;
1640 }
1641
1642 /// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value
1643 /// that is defined in the same block as the branch and if any PHI entries are
1644 /// constants, thread edges corresponding to that entry to be branches to their
1645 /// ultimate destination.
1646 static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout *DL) {
1647   BasicBlock *BB = BI->getParent();
1648   PHINode *PN = dyn_cast<PHINode>(BI->getCondition());
1649   // NOTE: we currently cannot transform this case if the PHI node is used
1650   // outside of the block.
1651   if (!PN || PN->getParent() != BB || !PN->hasOneUse())
1652     return false;
1653
1654   // Degenerate case of a single entry PHI.
1655   if (PN->getNumIncomingValues() == 1) {
1656     FoldSingleEntryPHINodes(PN->getParent());
1657     return true;
1658   }
1659
1660   // Now we know that this block has multiple preds and two succs.
1661   if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false;
1662
1663   if (HasNoDuplicateCall(BB)) return false;
1664
1665   // Okay, this is a simple enough basic block.  See if any phi values are
1666   // constants.
1667   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1668     ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i));
1669     if (!CB || !CB->getType()->isIntegerTy(1)) continue;
1670
1671     // Okay, we now know that all edges from PredBB should be revectored to
1672     // branch to RealDest.
1673     BasicBlock *PredBB = PN->getIncomingBlock(i);
1674     BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue());
1675
1676     if (RealDest == BB) continue;  // Skip self loops.
1677     // Skip if the predecessor's terminator is an indirect branch.
1678     if (isa<IndirectBrInst>(PredBB->getTerminator())) continue;
1679
1680     // The dest block might have PHI nodes, other predecessors and other
1681     // difficult cases.  Instead of being smart about this, just insert a new
1682     // block that jumps to the destination block, effectively splitting
1683     // the edge we are about to create.
1684     BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(),
1685                                             RealDest->getName()+".critedge",
1686                                             RealDest->getParent(), RealDest);
1687     BranchInst::Create(RealDest, EdgeBB);
1688
1689     // Update PHI nodes.
1690     AddPredecessorToBlock(RealDest, EdgeBB, BB);
1691
1692     // BB may have instructions that are being threaded over.  Clone these
1693     // instructions into EdgeBB.  We know that there will be no uses of the
1694     // cloned instructions outside of EdgeBB.
1695     BasicBlock::iterator InsertPt = EdgeBB->begin();
1696     DenseMap<Value*, Value*> TranslateMap;  // Track translated values.
1697     for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) {
1698       if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
1699         TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB);
1700         continue;
1701       }
1702       // Clone the instruction.
1703       Instruction *N = BBI->clone();
1704       if (BBI->hasName()) N->setName(BBI->getName()+".c");
1705
1706       // Update operands due to translation.
1707       for (User::op_iterator i = N->op_begin(), e = N->op_end();
1708            i != e; ++i) {
1709         DenseMap<Value*, Value*>::iterator PI = TranslateMap.find(*i);
1710         if (PI != TranslateMap.end())
1711           *i = PI->second;
1712       }
1713
1714       // Check for trivial simplification.
1715       if (Value *V = SimplifyInstruction(N, DL)) {
1716         TranslateMap[BBI] = V;
1717         delete N;   // Instruction folded away, don't need actual inst
1718       } else {
1719         // Insert the new instruction into its new home.
1720         EdgeBB->getInstList().insert(InsertPt, N);
1721         if (!BBI->use_empty())
1722           TranslateMap[BBI] = N;
1723       }
1724     }
1725
1726     // Loop over all of the edges from PredBB to BB, changing them to branch
1727     // to EdgeBB instead.
1728     TerminatorInst *PredBBTI = PredBB->getTerminator();
1729     for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i)
1730       if (PredBBTI->getSuccessor(i) == BB) {
1731         BB->removePredecessor(PredBB);
1732         PredBBTI->setSuccessor(i, EdgeBB);
1733       }
1734
1735     // Recurse, simplifying any other constants.
1736     return FoldCondBranchOnPHI(BI, DL) | true;
1737   }
1738
1739   return false;
1740 }
1741
1742 /// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry
1743 /// PHI node, see if we can eliminate it.
1744 static bool FoldTwoEntryPHINode(PHINode *PN, const DataLayout *DL) {
1745   // Ok, this is a two entry PHI node.  Check to see if this is a simple "if
1746   // statement", which has a very simple dominance structure.  Basically, we
1747   // are trying to find the condition that is being branched on, which
1748   // subsequently causes this merge to happen.  We really want control
1749   // dependence information for this check, but simplifycfg can't keep it up
1750   // to date, and this catches most of the cases we care about anyway.
1751   BasicBlock *BB = PN->getParent();
1752   BasicBlock *IfTrue, *IfFalse;
1753   Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse);
1754   if (!IfCond ||
1755       // Don't bother if the branch will be constant folded trivially.
1756       isa<ConstantInt>(IfCond))
1757     return false;
1758
1759   // Okay, we found that we can merge this two-entry phi node into a select.
1760   // Doing so would require us to fold *all* two entry phi nodes in this block.
1761   // At some point this becomes non-profitable (particularly if the target
1762   // doesn't support cmov's).  Only do this transformation if there are two or
1763   // fewer PHI nodes in this block.
1764   unsigned NumPhis = 0;
1765   for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I)
1766     if (NumPhis > 2)
1767       return false;
1768
1769   // Loop over the PHI's seeing if we can promote them all to select
1770   // instructions.  While we are at it, keep track of the instructions
1771   // that need to be moved to the dominating block.
1772   SmallPtrSet<Instruction*, 4> AggressiveInsts;
1773   unsigned MaxCostVal0 = PHINodeFoldingThreshold,
1774            MaxCostVal1 = PHINodeFoldingThreshold;
1775
1776   for (BasicBlock::iterator II = BB->begin(); isa<PHINode>(II);) {
1777     PHINode *PN = cast<PHINode>(II++);
1778     if (Value *V = SimplifyInstruction(PN, DL)) {
1779       PN->replaceAllUsesWith(V);
1780       PN->eraseFromParent();
1781       continue;
1782     }
1783
1784     if (!DominatesMergePoint(PN->getIncomingValue(0), BB, &AggressiveInsts,
1785                              MaxCostVal0, DL) ||
1786         !DominatesMergePoint(PN->getIncomingValue(1), BB, &AggressiveInsts,
1787                              MaxCostVal1, DL))
1788       return false;
1789   }
1790
1791   // If we folded the first phi, PN dangles at this point.  Refresh it.  If
1792   // we ran out of PHIs then we simplified them all.
1793   PN = dyn_cast<PHINode>(BB->begin());
1794   if (!PN) return true;
1795
1796   // Don't fold i1 branches on PHIs which contain binary operators.  These can
1797   // often be turned into switches and other things.
1798   if (PN->getType()->isIntegerTy(1) &&
1799       (isa<BinaryOperator>(PN->getIncomingValue(0)) ||
1800        isa<BinaryOperator>(PN->getIncomingValue(1)) ||
1801        isa<BinaryOperator>(IfCond)))
1802     return false;
1803
1804   // If we all PHI nodes are promotable, check to make sure that all
1805   // instructions in the predecessor blocks can be promoted as well.  If
1806   // not, we won't be able to get rid of the control flow, so it's not
1807   // worth promoting to select instructions.
1808   BasicBlock *DomBlock = nullptr;
1809   BasicBlock *IfBlock1 = PN->getIncomingBlock(0);
1810   BasicBlock *IfBlock2 = PN->getIncomingBlock(1);
1811   if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) {
1812     IfBlock1 = nullptr;
1813   } else {
1814     DomBlock = *pred_begin(IfBlock1);
1815     for (BasicBlock::iterator I = IfBlock1->begin();!isa<TerminatorInst>(I);++I)
1816       if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) {
1817         // This is not an aggressive instruction that we can promote.
1818         // Because of this, we won't be able to get rid of the control
1819         // flow, so the xform is not worth it.
1820         return false;
1821       }
1822   }
1823
1824   if (cast<BranchInst>(IfBlock2->getTerminator())->isConditional()) {
1825     IfBlock2 = nullptr;
1826   } else {
1827     DomBlock = *pred_begin(IfBlock2);
1828     for (BasicBlock::iterator I = IfBlock2->begin();!isa<TerminatorInst>(I);++I)
1829       if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) {
1830         // This is not an aggressive instruction that we can promote.
1831         // Because of this, we won't be able to get rid of the control
1832         // flow, so the xform is not worth it.
1833         return false;
1834       }
1835   }
1836
1837   DEBUG(dbgs() << "FOUND IF CONDITION!  " << *IfCond << "  T: "
1838                << IfTrue->getName() << "  F: " << IfFalse->getName() << "\n");
1839
1840   // If we can still promote the PHI nodes after this gauntlet of tests,
1841   // do all of the PHI's now.
1842   Instruction *InsertPt = DomBlock->getTerminator();
1843   IRBuilder<true, NoFolder> Builder(InsertPt);
1844
1845   // Move all 'aggressive' instructions, which are defined in the
1846   // conditional parts of the if's up to the dominating block.
1847   if (IfBlock1)
1848     DomBlock->getInstList().splice(InsertPt,
1849                                    IfBlock1->getInstList(), IfBlock1->begin(),
1850                                    IfBlock1->getTerminator());
1851   if (IfBlock2)
1852     DomBlock->getInstList().splice(InsertPt,
1853                                    IfBlock2->getInstList(), IfBlock2->begin(),
1854                                    IfBlock2->getTerminator());
1855
1856   while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
1857     // Change the PHI node into a select instruction.
1858     Value *TrueVal  = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
1859     Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
1860
1861     SelectInst *NV =
1862       cast<SelectInst>(Builder.CreateSelect(IfCond, TrueVal, FalseVal, ""));
1863     PN->replaceAllUsesWith(NV);
1864     NV->takeName(PN);
1865     PN->eraseFromParent();
1866   }
1867
1868   // At this point, IfBlock1 and IfBlock2 are both empty, so our if statement
1869   // has been flattened.  Change DomBlock to jump directly to our new block to
1870   // avoid other simplifycfg's kicking in on the diamond.
1871   TerminatorInst *OldTI = DomBlock->getTerminator();
1872   Builder.SetInsertPoint(OldTI);
1873   Builder.CreateBr(BB);
1874   OldTI->eraseFromParent();
1875   return true;
1876 }
1877
1878 /// SimplifyCondBranchToTwoReturns - If we found a conditional branch that goes
1879 /// to two returning blocks, try to merge them together into one return,
1880 /// introducing a select if the return values disagree.
1881 static bool SimplifyCondBranchToTwoReturns(BranchInst *BI,
1882                                            IRBuilder<> &Builder) {
1883   assert(BI->isConditional() && "Must be a conditional branch");
1884   BasicBlock *TrueSucc = BI->getSuccessor(0);
1885   BasicBlock *FalseSucc = BI->getSuccessor(1);
1886   ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator());
1887   ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator());
1888
1889   // Check to ensure both blocks are empty (just a return) or optionally empty
1890   // with PHI nodes.  If there are other instructions, merging would cause extra
1891   // computation on one path or the other.
1892   if (!TrueSucc->getFirstNonPHIOrDbg()->isTerminator())
1893     return false;
1894   if (!FalseSucc->getFirstNonPHIOrDbg()->isTerminator())
1895     return false;
1896
1897   Builder.SetInsertPoint(BI);
1898   // Okay, we found a branch that is going to two return nodes.  If
1899   // there is no return value for this function, just change the
1900   // branch into a return.
1901   if (FalseRet->getNumOperands() == 0) {
1902     TrueSucc->removePredecessor(BI->getParent());
1903     FalseSucc->removePredecessor(BI->getParent());
1904     Builder.CreateRetVoid();
1905     EraseTerminatorInstAndDCECond(BI);
1906     return true;
1907   }
1908
1909   // Otherwise, figure out what the true and false return values are
1910   // so we can insert a new select instruction.
1911   Value *TrueValue = TrueRet->getReturnValue();
1912   Value *FalseValue = FalseRet->getReturnValue();
1913
1914   // Unwrap any PHI nodes in the return blocks.
1915   if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue))
1916     if (TVPN->getParent() == TrueSucc)
1917       TrueValue = TVPN->getIncomingValueForBlock(BI->getParent());
1918   if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue))
1919     if (FVPN->getParent() == FalseSucc)
1920       FalseValue = FVPN->getIncomingValueForBlock(BI->getParent());
1921
1922   // In order for this transformation to be safe, we must be able to
1923   // unconditionally execute both operands to the return.  This is
1924   // normally the case, but we could have a potentially-trapping
1925   // constant expression that prevents this transformation from being
1926   // safe.
1927   if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue))
1928     if (TCV->canTrap())
1929       return false;
1930   if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue))
1931     if (FCV->canTrap())
1932       return false;
1933
1934   // Okay, we collected all the mapped values and checked them for sanity, and
1935   // defined to really do this transformation.  First, update the CFG.
1936   TrueSucc->removePredecessor(BI->getParent());
1937   FalseSucc->removePredecessor(BI->getParent());
1938
1939   // Insert select instructions where needed.
1940   Value *BrCond = BI->getCondition();
1941   if (TrueValue) {
1942     // Insert a select if the results differ.
1943     if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) {
1944     } else if (isa<UndefValue>(TrueValue)) {
1945       TrueValue = FalseValue;
1946     } else {
1947       TrueValue = Builder.CreateSelect(BrCond, TrueValue,
1948                                        FalseValue, "retval");
1949     }
1950   }
1951
1952   Value *RI = !TrueValue ?
1953     Builder.CreateRetVoid() : Builder.CreateRet(TrueValue);
1954
1955   (void) RI;
1956
1957   DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:"
1958                << "\n  " << *BI << "NewRet = " << *RI
1959                << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc);
1960
1961   EraseTerminatorInstAndDCECond(BI);
1962
1963   return true;
1964 }
1965
1966 /// ExtractBranchMetadata - Given a conditional BranchInstruction, retrieve the
1967 /// probabilities of the branch taking each edge. Fills in the two APInt
1968 /// parameters and return true, or returns false if no or invalid metadata was
1969 /// found.
1970 static bool ExtractBranchMetadata(BranchInst *BI,
1971                                   uint64_t &ProbTrue, uint64_t &ProbFalse) {
1972   assert(BI->isConditional() &&
1973          "Looking for probabilities on unconditional branch?");
1974   MDNode *ProfileData = BI->getMetadata(LLVMContext::MD_prof);
1975   if (!ProfileData || ProfileData->getNumOperands() != 3) return false;
1976   ConstantInt *CITrue = dyn_cast<ConstantInt>(ProfileData->getOperand(1));
1977   ConstantInt *CIFalse = dyn_cast<ConstantInt>(ProfileData->getOperand(2));
1978   if (!CITrue || !CIFalse) return false;
1979   ProbTrue = CITrue->getValue().getZExtValue();
1980   ProbFalse = CIFalse->getValue().getZExtValue();
1981   return true;
1982 }
1983
1984 /// checkCSEInPredecessor - Return true if the given instruction is available
1985 /// in its predecessor block. If yes, the instruction will be removed.
1986 ///
1987 static bool checkCSEInPredecessor(Instruction *Inst, BasicBlock *PB) {
1988   if (!isa<BinaryOperator>(Inst) && !isa<CmpInst>(Inst))
1989     return false;
1990   for (BasicBlock::iterator I = PB->begin(), E = PB->end(); I != E; I++) {
1991     Instruction *PBI = &*I;
1992     // Check whether Inst and PBI generate the same value.
1993     if (Inst->isIdenticalTo(PBI)) {
1994       Inst->replaceAllUsesWith(PBI);
1995       Inst->eraseFromParent();
1996       return true;
1997     }
1998   }
1999   return false;
2000 }
2001
2002 /// FoldBranchToCommonDest - If this basic block is simple enough, and if a
2003 /// predecessor branches to us and one of our successors, fold the block into
2004 /// the predecessor and use logical operations to pick the right destination.
2005 bool llvm::FoldBranchToCommonDest(BranchInst *BI, const DataLayout *DL,
2006                                   unsigned BonusInstThreshold) {
2007   BasicBlock *BB = BI->getParent();
2008
2009   Instruction *Cond = nullptr;
2010   if (BI->isConditional())
2011     Cond = dyn_cast<Instruction>(BI->getCondition());
2012   else {
2013     // For unconditional branch, check for a simple CFG pattern, where
2014     // BB has a single predecessor and BB's successor is also its predecessor's
2015     // successor. If such pattern exisits, check for CSE between BB and its
2016     // predecessor.
2017     if (BasicBlock *PB = BB->getSinglePredecessor())
2018       if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator()))
2019         if (PBI->isConditional() &&
2020             (BI->getSuccessor(0) == PBI->getSuccessor(0) ||
2021              BI->getSuccessor(0) == PBI->getSuccessor(1))) {
2022           for (BasicBlock::iterator I = BB->begin(), E = BB->end();
2023                I != E; ) {
2024             Instruction *Curr = I++;
2025             if (isa<CmpInst>(Curr)) {
2026               Cond = Curr;
2027               break;
2028             }
2029             // Quit if we can't remove this instruction.
2030             if (!checkCSEInPredecessor(Curr, PB))
2031               return false;
2032           }
2033         }
2034
2035     if (!Cond)
2036       return false;
2037   }
2038
2039   if (!Cond || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) ||
2040       Cond->getParent() != BB || !Cond->hasOneUse())
2041   return false;
2042
2043   // Make sure the instruction after the condition is the cond branch.
2044   BasicBlock::iterator CondIt = Cond; ++CondIt;
2045
2046   // Ignore dbg intrinsics.
2047   while (isa<DbgInfoIntrinsic>(CondIt)) ++CondIt;
2048
2049   if (&*CondIt != BI)
2050     return false;
2051
2052   // Only allow this transformation if computing the condition doesn't involve
2053   // too many instructions and these involved instructions can be executed
2054   // unconditionally. We denote all involved instructions except the condition
2055   // as "bonus instructions", and only allow this transformation when the
2056   // number of the bonus instructions does not exceed a certain threshold.
2057   unsigned NumBonusInsts = 0;
2058   for (auto I = BB->begin(); Cond != I; ++I) {
2059     // Ignore dbg intrinsics.
2060     if (isa<DbgInfoIntrinsic>(I))
2061       continue;
2062     if (!I->hasOneUse() || !isSafeToSpeculativelyExecute(I, DL))
2063       return false;
2064     // I has only one use and can be executed unconditionally.
2065     Instruction *User = dyn_cast<Instruction>(I->user_back());
2066     if (User == nullptr || User->getParent() != BB)
2067       return false;
2068     // I is used in the same BB. Since BI uses Cond and doesn't have more slots
2069     // to use any other instruction, User must be an instruction between next(I)
2070     // and Cond.
2071     ++NumBonusInsts;
2072     // Early exits once we reach the limit.
2073     if (NumBonusInsts > BonusInstThreshold)
2074       return false;
2075   }
2076
2077   // Cond is known to be a compare or binary operator.  Check to make sure that
2078   // neither operand is a potentially-trapping constant expression.
2079   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0)))
2080     if (CE->canTrap())
2081       return false;
2082   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1)))
2083     if (CE->canTrap())
2084       return false;
2085
2086   // Finally, don't infinitely unroll conditional loops.
2087   BasicBlock *TrueDest  = BI->getSuccessor(0);
2088   BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : nullptr;
2089   if (TrueDest == BB || FalseDest == BB)
2090     return false;
2091
2092   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
2093     BasicBlock *PredBlock = *PI;
2094     BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
2095
2096     // Check that we have two conditional branches.  If there is a PHI node in
2097     // the common successor, verify that the same value flows in from both
2098     // blocks.
2099     SmallVector<PHINode*, 4> PHIs;
2100     if (!PBI || PBI->isUnconditional() ||
2101         (BI->isConditional() &&
2102          !SafeToMergeTerminators(BI, PBI)) ||
2103         (!BI->isConditional() &&
2104          !isProfitableToFoldUnconditional(BI, PBI, Cond, PHIs)))
2105       continue;
2106
2107     // Determine if the two branches share a common destination.
2108     Instruction::BinaryOps Opc = Instruction::BinaryOpsEnd;
2109     bool InvertPredCond = false;
2110
2111     if (BI->isConditional()) {
2112       if (PBI->getSuccessor(0) == TrueDest)
2113         Opc = Instruction::Or;
2114       else if (PBI->getSuccessor(1) == FalseDest)
2115         Opc = Instruction::And;
2116       else if (PBI->getSuccessor(0) == FalseDest)
2117         Opc = Instruction::And, InvertPredCond = true;
2118       else if (PBI->getSuccessor(1) == TrueDest)
2119         Opc = Instruction::Or, InvertPredCond = true;
2120       else
2121         continue;
2122     } else {
2123       if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest)
2124         continue;
2125     }
2126
2127     DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
2128     IRBuilder<> Builder(PBI);
2129
2130     // If we need to invert the condition in the pred block to match, do so now.
2131     if (InvertPredCond) {
2132       Value *NewCond = PBI->getCondition();
2133
2134       if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) {
2135         CmpInst *CI = cast<CmpInst>(NewCond);
2136         CI->setPredicate(CI->getInversePredicate());
2137       } else {
2138         NewCond = Builder.CreateNot(NewCond,
2139                                     PBI->getCondition()->getName()+".not");
2140       }
2141
2142       PBI->setCondition(NewCond);
2143       PBI->swapSuccessors();
2144     }
2145
2146     // If we have bonus instructions, clone them into the predecessor block.
2147     // Note that there may be mutliple predecessor blocks, so we cannot move
2148     // bonus instructions to a predecessor block.
2149     ValueToValueMapTy VMap; // maps original values to cloned values
2150     // We already make sure Cond is the last instruction before BI. Therefore,
2151     // every instructions before Cond other than DbgInfoIntrinsic are bonus
2152     // instructions.
2153     for (auto BonusInst = BB->begin(); Cond != BonusInst; ++BonusInst) {
2154       if (isa<DbgInfoIntrinsic>(BonusInst))
2155         continue;
2156       Instruction *NewBonusInst = BonusInst->clone();
2157       RemapInstruction(NewBonusInst, VMap,
2158                        RF_NoModuleLevelChanges | RF_IgnoreMissingEntries);
2159       VMap[BonusInst] = NewBonusInst;
2160
2161       // If we moved a load, we cannot any longer claim any knowledge about
2162       // its potential value. The previous information might have been valid
2163       // only given the branch precondition.
2164       // For an analogous reason, we must also drop all the metadata whose
2165       // semantics we don't understand.
2166       NewBonusInst->dropUnknownMetadata(LLVMContext::MD_dbg);
2167
2168       PredBlock->getInstList().insert(PBI, NewBonusInst);
2169       NewBonusInst->takeName(BonusInst);
2170       BonusInst->setName(BonusInst->getName() + ".old");
2171     }
2172
2173     // Clone Cond into the predecessor basic block, and or/and the
2174     // two conditions together.
2175     Instruction *New = Cond->clone();
2176     RemapInstruction(New, VMap,
2177                      RF_NoModuleLevelChanges | RF_IgnoreMissingEntries);
2178     PredBlock->getInstList().insert(PBI, New);
2179     New->takeName(Cond);
2180     Cond->setName(New->getName() + ".old");
2181
2182     if (BI->isConditional()) {
2183       Instruction *NewCond =
2184         cast<Instruction>(Builder.CreateBinOp(Opc, PBI->getCondition(),
2185                                             New, "or.cond"));
2186       PBI->setCondition(NewCond);
2187
2188       uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
2189       bool PredHasWeights = ExtractBranchMetadata(PBI, PredTrueWeight,
2190                                                   PredFalseWeight);
2191       bool SuccHasWeights = ExtractBranchMetadata(BI, SuccTrueWeight,
2192                                                   SuccFalseWeight);
2193       SmallVector<uint64_t, 8> NewWeights;
2194
2195       if (PBI->getSuccessor(0) == BB) {
2196         if (PredHasWeights && SuccHasWeights) {
2197           // PBI: br i1 %x, BB, FalseDest
2198           // BI:  br i1 %y, TrueDest, FalseDest
2199           //TrueWeight is TrueWeight for PBI * TrueWeight for BI.
2200           NewWeights.push_back(PredTrueWeight * SuccTrueWeight);
2201           //FalseWeight is FalseWeight for PBI * TotalWeight for BI +
2202           //               TrueWeight for PBI * FalseWeight for BI.
2203           // We assume that total weights of a BranchInst can fit into 32 bits.
2204           // Therefore, we will not have overflow using 64-bit arithmetic.
2205           NewWeights.push_back(PredFalseWeight * (SuccFalseWeight +
2206                SuccTrueWeight) + PredTrueWeight * SuccFalseWeight);
2207         }
2208         AddPredecessorToBlock(TrueDest, PredBlock, BB);
2209         PBI->setSuccessor(0, TrueDest);
2210       }
2211       if (PBI->getSuccessor(1) == BB) {
2212         if (PredHasWeights && SuccHasWeights) {
2213           // PBI: br i1 %x, TrueDest, BB
2214           // BI:  br i1 %y, TrueDest, FalseDest
2215           //TrueWeight is TrueWeight for PBI * TotalWeight for BI +
2216           //              FalseWeight for PBI * TrueWeight for BI.
2217           NewWeights.push_back(PredTrueWeight * (SuccFalseWeight +
2218               SuccTrueWeight) + PredFalseWeight * SuccTrueWeight);
2219           //FalseWeight is FalseWeight for PBI * FalseWeight for BI.
2220           NewWeights.push_back(PredFalseWeight * SuccFalseWeight);
2221         }
2222         AddPredecessorToBlock(FalseDest, PredBlock, BB);
2223         PBI->setSuccessor(1, FalseDest);
2224       }
2225       if (NewWeights.size() == 2) {
2226         // Halve the weights if any of them cannot fit in an uint32_t
2227         FitWeights(NewWeights);
2228
2229         SmallVector<uint32_t, 8> MDWeights(NewWeights.begin(),NewWeights.end());
2230         PBI->setMetadata(LLVMContext::MD_prof,
2231                          MDBuilder(BI->getContext()).
2232                          createBranchWeights(MDWeights));
2233       } else
2234         PBI->setMetadata(LLVMContext::MD_prof, nullptr);
2235     } else {
2236       // Update PHI nodes in the common successors.
2237       for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
2238         ConstantInt *PBI_C = cast<ConstantInt>(
2239           PHIs[i]->getIncomingValueForBlock(PBI->getParent()));
2240         assert(PBI_C->getType()->isIntegerTy(1));
2241         Instruction *MergedCond = nullptr;
2242         if (PBI->getSuccessor(0) == TrueDest) {
2243           // Create (PBI_Cond and PBI_C) or (!PBI_Cond and BI_Value)
2244           // PBI_C is true: PBI_Cond or (!PBI_Cond and BI_Value)
2245           //       is false: !PBI_Cond and BI_Value
2246           Instruction *NotCond =
2247             cast<Instruction>(Builder.CreateNot(PBI->getCondition(),
2248                                 "not.cond"));
2249           MergedCond =
2250             cast<Instruction>(Builder.CreateBinOp(Instruction::And,
2251                                 NotCond, New,
2252                                 "and.cond"));
2253           if (PBI_C->isOne())
2254             MergedCond =
2255               cast<Instruction>(Builder.CreateBinOp(Instruction::Or,
2256                                   PBI->getCondition(), MergedCond,
2257                                   "or.cond"));
2258         } else {
2259           // Create (PBI_Cond and BI_Value) or (!PBI_Cond and PBI_C)
2260           // PBI_C is true: (PBI_Cond and BI_Value) or (!PBI_Cond)
2261           //       is false: PBI_Cond and BI_Value
2262           MergedCond =
2263             cast<Instruction>(Builder.CreateBinOp(Instruction::And,
2264                                 PBI->getCondition(), New,
2265                                 "and.cond"));
2266           if (PBI_C->isOne()) {
2267             Instruction *NotCond =
2268               cast<Instruction>(Builder.CreateNot(PBI->getCondition(),
2269                                   "not.cond"));
2270             MergedCond =
2271               cast<Instruction>(Builder.CreateBinOp(Instruction::Or,
2272                                   NotCond, MergedCond,
2273                                   "or.cond"));
2274           }
2275         }
2276         // Update PHI Node.
2277         PHIs[i]->setIncomingValue(PHIs[i]->getBasicBlockIndex(PBI->getParent()),
2278                                   MergedCond);
2279       }
2280       // Change PBI from Conditional to Unconditional.
2281       BranchInst *New_PBI = BranchInst::Create(TrueDest, PBI);
2282       EraseTerminatorInstAndDCECond(PBI);
2283       PBI = New_PBI;
2284     }
2285
2286     // TODO: If BB is reachable from all paths through PredBlock, then we
2287     // could replace PBI's branch probabilities with BI's.
2288
2289     // Copy any debug value intrinsics into the end of PredBlock.
2290     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
2291       if (isa<DbgInfoIntrinsic>(*I))
2292         I->clone()->insertBefore(PBI);
2293
2294     return true;
2295   }
2296   return false;
2297 }
2298
2299 /// SimplifyCondBranchToCondBranch - If we have a conditional branch as a
2300 /// predecessor of another block, this function tries to simplify it.  We know
2301 /// that PBI and BI are both conditional branches, and BI is in one of the
2302 /// successor blocks of PBI - PBI branches to BI.
2303 static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) {
2304   assert(PBI->isConditional() && BI->isConditional());
2305   BasicBlock *BB = BI->getParent();
2306
2307   // If this block ends with a branch instruction, and if there is a
2308   // predecessor that ends on a branch of the same condition, make
2309   // this conditional branch redundant.
2310   if (PBI->getCondition() == BI->getCondition() &&
2311       PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
2312     // Okay, the outcome of this conditional branch is statically
2313     // knowable.  If this block had a single pred, handle specially.
2314     if (BB->getSinglePredecessor()) {
2315       // Turn this into a branch on constant.
2316       bool CondIsTrue = PBI->getSuccessor(0) == BB;
2317       BI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()),
2318                                         CondIsTrue));
2319       return true;  // Nuke the branch on constant.
2320     }
2321
2322     // Otherwise, if there are multiple predecessors, insert a PHI that merges
2323     // in the constant and simplify the block result.  Subsequent passes of
2324     // simplifycfg will thread the block.
2325     if (BlockIsSimpleEnoughToThreadThrough(BB)) {
2326       pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
2327       PHINode *NewPN = PHINode::Create(Type::getInt1Ty(BB->getContext()),
2328                                        std::distance(PB, PE),
2329                                        BI->getCondition()->getName() + ".pr",
2330                                        BB->begin());
2331       // Okay, we're going to insert the PHI node.  Since PBI is not the only
2332       // predecessor, compute the PHI'd conditional value for all of the preds.
2333       // Any predecessor where the condition is not computable we keep symbolic.
2334       for (pred_iterator PI = PB; PI != PE; ++PI) {
2335         BasicBlock *P = *PI;
2336         if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) &&
2337             PBI != BI && PBI->isConditional() &&
2338             PBI->getCondition() == BI->getCondition() &&
2339             PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
2340           bool CondIsTrue = PBI->getSuccessor(0) == BB;
2341           NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()),
2342                                               CondIsTrue), P);
2343         } else {
2344           NewPN->addIncoming(BI->getCondition(), P);
2345         }
2346       }
2347
2348       BI->setCondition(NewPN);
2349       return true;
2350     }
2351   }
2352
2353   // If this is a conditional branch in an empty block, and if any
2354   // predecessors are a conditional branch to one of our destinations,
2355   // fold the conditions into logical ops and one cond br.
2356   BasicBlock::iterator BBI = BB->begin();
2357   // Ignore dbg intrinsics.
2358   while (isa<DbgInfoIntrinsic>(BBI))
2359     ++BBI;
2360   if (&*BBI != BI)
2361     return false;
2362
2363
2364   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BI->getCondition()))
2365     if (CE->canTrap())
2366       return false;
2367
2368   int PBIOp, BIOp;
2369   if (PBI->getSuccessor(0) == BI->getSuccessor(0))
2370     PBIOp = BIOp = 0;
2371   else if (PBI->getSuccessor(0) == BI->getSuccessor(1))
2372     PBIOp = 0, BIOp = 1;
2373   else if (PBI->getSuccessor(1) == BI->getSuccessor(0))
2374     PBIOp = 1, BIOp = 0;
2375   else if (PBI->getSuccessor(1) == BI->getSuccessor(1))
2376     PBIOp = BIOp = 1;
2377   else
2378     return false;
2379
2380   // Check to make sure that the other destination of this branch
2381   // isn't BB itself.  If so, this is an infinite loop that will
2382   // keep getting unwound.
2383   if (PBI->getSuccessor(PBIOp) == BB)
2384     return false;
2385
2386   // Do not perform this transformation if it would require
2387   // insertion of a large number of select instructions. For targets
2388   // without predication/cmovs, this is a big pessimization.
2389
2390   // Also do not perform this transformation if any phi node in the common
2391   // destination block can trap when reached by BB or PBB (PR17073). In that
2392   // case, it would be unsafe to hoist the operation into a select instruction.
2393
2394   BasicBlock *CommonDest = PBI->getSuccessor(PBIOp);
2395   unsigned NumPhis = 0;
2396   for (BasicBlock::iterator II = CommonDest->begin();
2397        isa<PHINode>(II); ++II, ++NumPhis) {
2398     if (NumPhis > 2) // Disable this xform.
2399       return false;
2400
2401     PHINode *PN = cast<PHINode>(II);
2402     Value *BIV = PN->getIncomingValueForBlock(BB);
2403     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BIV))
2404       if (CE->canTrap())
2405         return false;
2406
2407     unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent());
2408     Value *PBIV = PN->getIncomingValue(PBBIdx);
2409     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(PBIV))
2410       if (CE->canTrap())
2411         return false;
2412   }
2413
2414   // Finally, if everything is ok, fold the branches to logical ops.
2415   BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1);
2416
2417   DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent()
2418                << "AND: " << *BI->getParent());
2419
2420
2421   // If OtherDest *is* BB, then BB is a basic block with a single conditional
2422   // branch in it, where one edge (OtherDest) goes back to itself but the other
2423   // exits.  We don't *know* that the program avoids the infinite loop
2424   // (even though that seems likely).  If we do this xform naively, we'll end up
2425   // recursively unpeeling the loop.  Since we know that (after the xform is
2426   // done) that the block *is* infinite if reached, we just make it an obviously
2427   // infinite loop with no cond branch.
2428   if (OtherDest == BB) {
2429     // Insert it at the end of the function, because it's either code,
2430     // or it won't matter if it's hot. :)
2431     BasicBlock *InfLoopBlock = BasicBlock::Create(BB->getContext(),
2432                                                   "infloop", BB->getParent());
2433     BranchInst::Create(InfLoopBlock, InfLoopBlock);
2434     OtherDest = InfLoopBlock;
2435   }
2436
2437   DEBUG(dbgs() << *PBI->getParent()->getParent());
2438
2439   // BI may have other predecessors.  Because of this, we leave
2440   // it alone, but modify PBI.
2441
2442   // Make sure we get to CommonDest on True&True directions.
2443   Value *PBICond = PBI->getCondition();
2444   IRBuilder<true, NoFolder> Builder(PBI);
2445   if (PBIOp)
2446     PBICond = Builder.CreateNot(PBICond, PBICond->getName()+".not");
2447
2448   Value *BICond = BI->getCondition();
2449   if (BIOp)
2450     BICond = Builder.CreateNot(BICond, BICond->getName()+".not");
2451
2452   // Merge the conditions.
2453   Value *Cond = Builder.CreateOr(PBICond, BICond, "brmerge");
2454
2455   // Modify PBI to branch on the new condition to the new dests.
2456   PBI->setCondition(Cond);
2457   PBI->setSuccessor(0, CommonDest);
2458   PBI->setSuccessor(1, OtherDest);
2459
2460   // Update branch weight for PBI.
2461   uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
2462   bool PredHasWeights = ExtractBranchMetadata(PBI, PredTrueWeight,
2463                                               PredFalseWeight);
2464   bool SuccHasWeights = ExtractBranchMetadata(BI, SuccTrueWeight,
2465                                               SuccFalseWeight);
2466   if (PredHasWeights && SuccHasWeights) {
2467     uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
2468     uint64_t PredOther = PBIOp ?PredTrueWeight : PredFalseWeight;
2469     uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
2470     uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
2471     // The weight to CommonDest should be PredCommon * SuccTotal +
2472     //                                    PredOther * SuccCommon.
2473     // The weight to OtherDest should be PredOther * SuccOther.
2474     SmallVector<uint64_t, 2> NewWeights;
2475     NewWeights.push_back(PredCommon * (SuccCommon + SuccOther) +
2476                          PredOther * SuccCommon);
2477     NewWeights.push_back(PredOther * SuccOther);
2478     // Halve the weights if any of them cannot fit in an uint32_t
2479     FitWeights(NewWeights);
2480
2481     SmallVector<uint32_t, 2> MDWeights(NewWeights.begin(),NewWeights.end());
2482     PBI->setMetadata(LLVMContext::MD_prof,
2483                      MDBuilder(BI->getContext()).
2484                      createBranchWeights(MDWeights));
2485   }
2486
2487   // OtherDest may have phi nodes.  If so, add an entry from PBI's
2488   // block that are identical to the entries for BI's block.
2489   AddPredecessorToBlock(OtherDest, PBI->getParent(), BB);
2490
2491   // We know that the CommonDest already had an edge from PBI to
2492   // it.  If it has PHIs though, the PHIs may have different
2493   // entries for BB and PBI's BB.  If so, insert a select to make
2494   // them agree.
2495   PHINode *PN;
2496   for (BasicBlock::iterator II = CommonDest->begin();
2497        (PN = dyn_cast<PHINode>(II)); ++II) {
2498     Value *BIV = PN->getIncomingValueForBlock(BB);
2499     unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent());
2500     Value *PBIV = PN->getIncomingValue(PBBIdx);
2501     if (BIV != PBIV) {
2502       // Insert a select in PBI to pick the right value.
2503       Value *NV = cast<SelectInst>
2504         (Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName()+".mux"));
2505       PN->setIncomingValue(PBBIdx, NV);
2506     }
2507   }
2508
2509   DEBUG(dbgs() << "INTO: " << *PBI->getParent());
2510   DEBUG(dbgs() << *PBI->getParent()->getParent());
2511
2512   // This basic block is probably dead.  We know it has at least
2513   // one fewer predecessor.
2514   return true;
2515 }
2516
2517 // SimplifyTerminatorOnSelect - Simplifies a terminator by replacing it with a
2518 // branch to TrueBB if Cond is true or to FalseBB if Cond is false.
2519 // Takes care of updating the successors and removing the old terminator.
2520 // Also makes sure not to introduce new successors by assuming that edges to
2521 // non-successor TrueBBs and FalseBBs aren't reachable.
2522 static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond,
2523                                        BasicBlock *TrueBB, BasicBlock *FalseBB,
2524                                        uint32_t TrueWeight,
2525                                        uint32_t FalseWeight){
2526   // Remove any superfluous successor edges from the CFG.
2527   // First, figure out which successors to preserve.
2528   // If TrueBB and FalseBB are equal, only try to preserve one copy of that
2529   // successor.
2530   BasicBlock *KeepEdge1 = TrueBB;
2531   BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : nullptr;
2532
2533   // Then remove the rest.
2534   for (unsigned I = 0, E = OldTerm->getNumSuccessors(); I != E; ++I) {
2535     BasicBlock *Succ = OldTerm->getSuccessor(I);
2536     // Make sure only to keep exactly one copy of each edge.
2537     if (Succ == KeepEdge1)
2538       KeepEdge1 = nullptr;
2539     else if (Succ == KeepEdge2)
2540       KeepEdge2 = nullptr;
2541     else
2542       Succ->removePredecessor(OldTerm->getParent());
2543   }
2544
2545   IRBuilder<> Builder(OldTerm);
2546   Builder.SetCurrentDebugLocation(OldTerm->getDebugLoc());
2547
2548   // Insert an appropriate new terminator.
2549   if (!KeepEdge1 && !KeepEdge2) {
2550     if (TrueBB == FalseBB)
2551       // We were only looking for one successor, and it was present.
2552       // Create an unconditional branch to it.
2553       Builder.CreateBr(TrueBB);
2554     else {
2555       // We found both of the successors we were looking for.
2556       // Create a conditional branch sharing the condition of the select.
2557       BranchInst *NewBI = Builder.CreateCondBr(Cond, TrueBB, FalseBB);
2558       if (TrueWeight != FalseWeight)
2559         NewBI->setMetadata(LLVMContext::MD_prof,
2560                            MDBuilder(OldTerm->getContext()).
2561                            createBranchWeights(TrueWeight, FalseWeight));
2562     }
2563   } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
2564     // Neither of the selected blocks were successors, so this
2565     // terminator must be unreachable.
2566     new UnreachableInst(OldTerm->getContext(), OldTerm);
2567   } else {
2568     // One of the selected values was a successor, but the other wasn't.
2569     // Insert an unconditional branch to the one that was found;
2570     // the edge to the one that wasn't must be unreachable.
2571     if (!KeepEdge1)
2572       // Only TrueBB was found.
2573       Builder.CreateBr(TrueBB);
2574     else
2575       // Only FalseBB was found.
2576       Builder.CreateBr(FalseBB);
2577   }
2578
2579   EraseTerminatorInstAndDCECond(OldTerm);
2580   return true;
2581 }
2582
2583 // SimplifySwitchOnSelect - Replaces
2584 //   (switch (select cond, X, Y)) on constant X, Y
2585 // with a branch - conditional if X and Y lead to distinct BBs,
2586 // unconditional otherwise.
2587 static bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select) {
2588   // Check for constant integer values in the select.
2589   ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue());
2590   ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue());
2591   if (!TrueVal || !FalseVal)
2592     return false;
2593
2594   // Find the relevant condition and destinations.
2595   Value *Condition = Select->getCondition();
2596   BasicBlock *TrueBB = SI->findCaseValue(TrueVal).getCaseSuccessor();
2597   BasicBlock *FalseBB = SI->findCaseValue(FalseVal).getCaseSuccessor();
2598
2599   // Get weight for TrueBB and FalseBB.
2600   uint32_t TrueWeight = 0, FalseWeight = 0;
2601   SmallVector<uint64_t, 8> Weights;
2602   bool HasWeights = HasBranchWeights(SI);
2603   if (HasWeights) {
2604     GetBranchWeights(SI, Weights);
2605     if (Weights.size() == 1 + SI->getNumCases()) {
2606       TrueWeight = (uint32_t)Weights[SI->findCaseValue(TrueVal).
2607                                      getSuccessorIndex()];
2608       FalseWeight = (uint32_t)Weights[SI->findCaseValue(FalseVal).
2609                                       getSuccessorIndex()];
2610     }
2611   }
2612
2613   // Perform the actual simplification.
2614   return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB,
2615                                     TrueWeight, FalseWeight);
2616 }
2617
2618 // SimplifyIndirectBrOnSelect - Replaces
2619 //   (indirectbr (select cond, blockaddress(@fn, BlockA),
2620 //                             blockaddress(@fn, BlockB)))
2621 // with
2622 //   (br cond, BlockA, BlockB).
2623 static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) {
2624   // Check that both operands of the select are block addresses.
2625   BlockAddress *TBA = dyn_cast<BlockAddress>(SI->getTrueValue());
2626   BlockAddress *FBA = dyn_cast<BlockAddress>(SI->getFalseValue());
2627   if (!TBA || !FBA)
2628     return false;
2629
2630   // Extract the actual blocks.
2631   BasicBlock *TrueBB = TBA->getBasicBlock();
2632   BasicBlock *FalseBB = FBA->getBasicBlock();
2633
2634   // Perform the actual simplification.
2635   return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB,
2636                                     0, 0);
2637 }
2638
2639 /// TryToSimplifyUncondBranchWithICmpInIt - This is called when we find an icmp
2640 /// instruction (a seteq/setne with a constant) as the only instruction in a
2641 /// block that ends with an uncond branch.  We are looking for a very specific
2642 /// pattern that occurs when "A == 1 || A == 2 || A == 3" gets simplified.  In
2643 /// this case, we merge the first two "or's of icmp" into a switch, but then the
2644 /// default value goes to an uncond block with a seteq in it, we get something
2645 /// like:
2646 ///
2647 ///   switch i8 %A, label %DEFAULT [ i8 1, label %end    i8 2, label %end ]
2648 /// DEFAULT:
2649 ///   %tmp = icmp eq i8 %A, 92
2650 ///   br label %end
2651 /// end:
2652 ///   ... = phi i1 [ true, %entry ], [ %tmp, %DEFAULT ], [ true, %entry ]
2653 ///
2654 /// We prefer to split the edge to 'end' so that there is a true/false entry to
2655 /// the PHI, merging the third icmp into the switch.
2656 static bool TryToSimplifyUncondBranchWithICmpInIt(
2657     ICmpInst *ICI, IRBuilder<> &Builder, const TargetTransformInfo &TTI,
2658     unsigned BonusInstThreshold, const DataLayout *DL, AssumptionTracker *AT) {
2659   BasicBlock *BB = ICI->getParent();
2660
2661   // If the block has any PHIs in it or the icmp has multiple uses, it is too
2662   // complex.
2663   if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) return false;
2664
2665   Value *V = ICI->getOperand(0);
2666   ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1));
2667
2668   // The pattern we're looking for is where our only predecessor is a switch on
2669   // 'V' and this block is the default case for the switch.  In this case we can
2670   // fold the compared value into the switch to simplify things.
2671   BasicBlock *Pred = BB->getSinglePredecessor();
2672   if (!Pred || !isa<SwitchInst>(Pred->getTerminator())) return false;
2673
2674   SwitchInst *SI = cast<SwitchInst>(Pred->getTerminator());
2675   if (SI->getCondition() != V)
2676     return false;
2677
2678   // If BB is reachable on a non-default case, then we simply know the value of
2679   // V in this block.  Substitute it and constant fold the icmp instruction
2680   // away.
2681   if (SI->getDefaultDest() != BB) {
2682     ConstantInt *VVal = SI->findCaseDest(BB);
2683     assert(VVal && "Should have a unique destination value");
2684     ICI->setOperand(0, VVal);
2685
2686     if (Value *V = SimplifyInstruction(ICI, DL)) {
2687       ICI->replaceAllUsesWith(V);
2688       ICI->eraseFromParent();
2689     }
2690     // BB is now empty, so it is likely to simplify away.
2691     return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
2692   }
2693
2694   // Ok, the block is reachable from the default dest.  If the constant we're
2695   // comparing exists in one of the other edges, then we can constant fold ICI
2696   // and zap it.
2697   if (SI->findCaseValue(Cst) != SI->case_default()) {
2698     Value *V;
2699     if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
2700       V = ConstantInt::getFalse(BB->getContext());
2701     else
2702       V = ConstantInt::getTrue(BB->getContext());
2703
2704     ICI->replaceAllUsesWith(V);
2705     ICI->eraseFromParent();
2706     // BB is now empty, so it is likely to simplify away.
2707     return SimplifyCFG(BB, TTI, BonusInstThreshold, DL, AT) | true;
2708   }
2709
2710   // The use of the icmp has to be in the 'end' block, by the only PHI node in
2711   // the block.
2712   BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0);
2713   PHINode *PHIUse = dyn_cast<PHINode>(ICI->user_back());
2714   if (PHIUse == nullptr || PHIUse != &SuccBlock->front() ||
2715       isa<PHINode>(++BasicBlock::iterator(PHIUse)))
2716     return false;
2717
2718   // If the icmp is a SETEQ, then the default dest gets false, the new edge gets
2719   // true in the PHI.
2720   Constant *DefaultCst = ConstantInt::getTrue(BB->getContext());
2721   Constant *NewCst     = ConstantInt::getFalse(BB->getContext());
2722
2723   if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
2724     std::swap(DefaultCst, NewCst);
2725
2726   // Replace ICI (which is used by the PHI for the default value) with true or
2727   // false depending on if it is EQ or NE.
2728   ICI->replaceAllUsesWith(DefaultCst);
2729   ICI->eraseFromParent();
2730
2731   // Okay, the switch goes to this block on a default value.  Add an edge from
2732   // the switch to the merge point on the compared value.
2733   BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "switch.edge",
2734                                          BB->getParent(), BB);
2735   SmallVector<uint64_t, 8> Weights;
2736   bool HasWeights = HasBranchWeights(SI);
2737   if (HasWeights) {
2738     GetBranchWeights(SI, Weights);
2739     if (Weights.size() == 1 + SI->getNumCases()) {
2740       // Split weight for default case to case for "Cst".
2741       Weights[0] = (Weights[0]+1) >> 1;
2742       Weights.push_back(Weights[0]);
2743
2744       SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
2745       SI->setMetadata(LLVMContext::MD_prof,
2746                       MDBuilder(SI->getContext()).
2747                       createBranchWeights(MDWeights));
2748     }
2749   }
2750   SI->addCase(Cst, NewBB);
2751
2752   // NewBB branches to the phi block, add the uncond branch and the phi entry.
2753   Builder.SetInsertPoint(NewBB);
2754   Builder.SetCurrentDebugLocation(SI->getDebugLoc());
2755   Builder.CreateBr(SuccBlock);
2756   PHIUse->addIncoming(NewCst, NewBB);
2757   return true;
2758 }
2759
2760 /// SimplifyBranchOnICmpChain - The specified branch is a conditional branch.
2761 /// Check to see if it is branching on an or/and chain of icmp instructions, and
2762 /// fold it into a switch instruction if so.
2763 static bool SimplifyBranchOnICmpChain(BranchInst *BI, const DataLayout *DL,
2764                                       IRBuilder<> &Builder) {
2765   Instruction *Cond = dyn_cast<Instruction>(BI->getCondition());
2766   if (!Cond) return false;
2767
2768
2769   // Change br (X == 0 | X == 1), T, F into a switch instruction.
2770   // If this is a bunch of seteq's or'd together, or if it's a bunch of
2771   // 'setne's and'ed together, collect them.
2772   Value *CompVal = nullptr;
2773   std::vector<ConstantInt*> Values;
2774   bool TrueWhenEqual = true;
2775   Value *ExtraCase = nullptr;
2776   unsigned UsedICmps = 0;
2777
2778   if (Cond->getOpcode() == Instruction::Or) {
2779     CompVal = GatherConstantCompares(Cond, Values, ExtraCase, DL, true,
2780                                      UsedICmps);
2781   } else if (Cond->getOpcode() == Instruction::And) {
2782     CompVal = GatherConstantCompares(Cond, Values, ExtraCase, DL, false,
2783                                      UsedICmps);
2784     TrueWhenEqual = false;
2785   }
2786
2787   // If we didn't have a multiply compared value, fail.
2788   if (!CompVal) return false;
2789
2790   // Avoid turning single icmps into a switch.
2791   if (UsedICmps <= 1)
2792     return false;
2793
2794   // There might be duplicate constants in the list, which the switch
2795   // instruction can't handle, remove them now.
2796   array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate);
2797   Values.erase(std::unique(Values.begin(), Values.end()), Values.end());
2798
2799   // If Extra was used, we require at least two switch values to do the
2800   // transformation.  A switch with one value is just an cond branch.
2801   if (ExtraCase && Values.size() < 2) return false;
2802
2803   // TODO: Preserve branch weight metadata, similarly to how
2804   // FoldValueComparisonIntoPredecessors preserves it.
2805
2806   // Figure out which block is which destination.
2807   BasicBlock *DefaultBB = BI->getSuccessor(1);
2808   BasicBlock *EdgeBB    = BI->getSuccessor(0);
2809   if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB);
2810
2811   BasicBlock *BB = BI->getParent();
2812
2813   DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size()
2814                << " cases into SWITCH.  BB is:\n" << *BB);
2815
2816   // If there are any extra values that couldn't be folded into the switch
2817   // then we evaluate them with an explicit branch first.  Split the block
2818   // right before the condbr to handle it.
2819   if (ExtraCase) {
2820     BasicBlock *NewBB = BB->splitBasicBlock(BI, "switch.early.test");
2821     // Remove the uncond branch added to the old block.
2822     TerminatorInst *OldTI = BB->getTerminator();
2823     Builder.SetInsertPoint(OldTI);
2824
2825     if (TrueWhenEqual)
2826       Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB);
2827     else
2828       Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB);
2829
2830     OldTI->eraseFromParent();
2831
2832     // If there are PHI nodes in EdgeBB, then we need to add a new entry to them
2833     // for the edge we just added.
2834     AddPredecessorToBlock(EdgeBB, BB, NewBB);
2835
2836     DEBUG(dbgs() << "  ** 'icmp' chain unhandled condition: " << *ExtraCase
2837           << "\nEXTRABB = " << *BB);
2838     BB = NewBB;
2839   }
2840
2841   Builder.SetInsertPoint(BI);
2842   // Convert pointer to int before we switch.
2843   if (CompVal->getType()->isPointerTy()) {
2844     assert(DL && "Cannot switch on pointer without DataLayout");
2845     CompVal = Builder.CreatePtrToInt(CompVal,
2846                                      DL->getIntPtrType(CompVal->getType()),
2847                                      "magicptr");
2848   }
2849
2850   // Create the new switch instruction now.
2851   SwitchInst *New = Builder.CreateSwitch(CompVal, DefaultBB, Values.size());
2852
2853   // Add all of the 'cases' to the switch instruction.
2854   for (unsigned i = 0, e = Values.size(); i != e; ++i)
2855     New->addCase(Values[i], EdgeBB);
2856
2857   // We added edges from PI to the EdgeBB.  As such, if there were any
2858   // PHI nodes in EdgeBB, they need entries to be added corresponding to
2859   // the number of edges added.
2860   for (BasicBlock::iterator BBI = EdgeBB->begin();
2861        isa<PHINode>(BBI); ++BBI) {
2862     PHINode *PN = cast<PHINode>(BBI);
2863     Value *InVal = PN->getIncomingValueForBlock(BB);
2864     for (unsigned i = 0, e = Values.size()-1; i != e; ++i)
2865       PN->addIncoming(InVal, BB);
2866   }
2867
2868   // Erase the old branch instruction.
2869   EraseTerminatorInstAndDCECond(BI);
2870
2871   DEBUG(dbgs() << "  ** 'icmp' chain result is:\n" << *BB << '\n');
2872   return true;
2873 }
2874
2875 bool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) {
2876   // If this is a trivial landing pad that just continues unwinding the caught
2877   // exception then zap the landing pad, turning its invokes into calls.
2878   BasicBlock *BB = RI->getParent();
2879   LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI());
2880   if (RI->getValue() != LPInst)
2881     // Not a landing pad, or the resume is not unwinding the exception that
2882     // caused control to branch here.
2883     return false;
2884
2885   // Check that there are no other instructions except for debug intrinsics.
2886   BasicBlock::iterator I = LPInst, E = RI;
2887   while (++I != E)
2888     if (!isa<DbgInfoIntrinsic>(I))
2889       return false;
2890
2891   // Turn all invokes that unwind here into calls and delete the basic block.
2892   bool InvokeRequiresTableEntry = false;
2893   bool Changed = false;
2894   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) {
2895     InvokeInst *II = cast<InvokeInst>((*PI++)->getTerminator());
2896
2897     if (II->hasFnAttr(Attribute::UWTable)) {
2898       // Don't remove an `invoke' instruction if the ABI requires an entry into
2899       // the table.
2900       InvokeRequiresTableEntry = true;
2901       continue;
2902     }
2903
2904     SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
2905
2906     // Insert a call instruction before the invoke.
2907     CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II);
2908     Call->takeName(II);
2909     Call->setCallingConv(II->getCallingConv());
2910     Call->setAttributes(II->getAttributes());
2911     Call->setDebugLoc(II->getDebugLoc());
2912
2913     // Anything that used the value produced by the invoke instruction now uses
2914     // the value produced by the call instruction.  Note that we do this even
2915     // for void functions and calls with no uses so that the callgraph edge is
2916     // updated.
2917     II->replaceAllUsesWith(Call);
2918     BB->removePredecessor(II->getParent());
2919
2920     // Insert a branch to the normal destination right before the invoke.
2921     BranchInst::Create(II->getNormalDest(), II);
2922
2923     // Finally, delete the invoke instruction!
2924     II->eraseFromParent();
2925     Changed = true;
2926   }
2927
2928   if (!InvokeRequiresTableEntry)
2929     // The landingpad is now unreachable.  Zap it.
2930     BB->eraseFromParent();
2931
2932   return Changed;
2933 }
2934
2935 bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) {
2936   BasicBlock *BB = RI->getParent();
2937   if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false;
2938
2939   // Find predecessors that end with branches.
2940   SmallVector<BasicBlock*, 8> UncondBranchPreds;
2941   SmallVector<BranchInst*, 8> CondBranchPreds;
2942   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
2943     BasicBlock *P = *PI;
2944     TerminatorInst *PTI = P->getTerminator();
2945     if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) {
2946       if (BI->isUnconditional())
2947         UncondBranchPreds.push_back(P);
2948       else
2949         CondBranchPreds.push_back(BI);
2950     }
2951   }
2952
2953   // If we found some, do the transformation!
2954   if (!UncondBranchPreds.empty() && DupRet) {
2955     while (!UncondBranchPreds.empty()) {
2956       BasicBlock *Pred = UncondBranchPreds.pop_back_val();
2957       DEBUG(dbgs() << "FOLDING: " << *BB
2958             << "INTO UNCOND BRANCH PRED: " << *Pred);
2959       (void)FoldReturnIntoUncondBranch(RI, BB, Pred);
2960     }
2961
2962     // If we eliminated all predecessors of the block, delete the block now.
2963     if (pred_begin(BB) == pred_end(BB))
2964       // We know there are no successors, so just nuke the block.
2965       BB->eraseFromParent();
2966
2967     return true;
2968   }
2969
2970   // Check out all of the conditional branches going to this return
2971   // instruction.  If any of them just select between returns, change the
2972   // branch itself into a select/return pair.
2973   while (!CondBranchPreds.empty()) {
2974     BranchInst *BI = CondBranchPreds.pop_back_val();
2975
2976     // Check to see if the non-BB successor is also a return block.
2977     if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) &&
2978         isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) &&
2979         SimplifyCondBranchToTwoReturns(BI, Builder))
2980       return true;
2981   }
2982   return false;
2983 }
2984
2985 bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) {
2986   BasicBlock *BB = UI->getParent();
2987
2988   bool Changed = false;
2989
2990   // If there are any instructions immediately before the unreachable that can
2991   // be removed, do so.
2992   while (UI != BB->begin()) {
2993     BasicBlock::iterator BBI = UI;
2994     --BBI;
2995     // Do not delete instructions that can have side effects which might cause
2996     // the unreachable to not be reachable; specifically, calls and volatile
2997     // operations may have this effect.
2998     if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) break;
2999
3000     if (BBI->mayHaveSideEffects()) {
3001       if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
3002         if (SI->isVolatile())
3003           break;
3004       } else if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
3005         if (LI->isVolatile())
3006           break;
3007       } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(BBI)) {
3008         if (RMWI->isVolatile())
3009           break;
3010       } else if (AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(BBI)) {
3011         if (CXI->isVolatile())
3012           break;
3013       } else if (!isa<FenceInst>(BBI) && !isa<VAArgInst>(BBI) &&
3014                  !isa<LandingPadInst>(BBI)) {
3015         break;
3016       }
3017       // Note that deleting LandingPad's here is in fact okay, although it
3018       // involves a bit of subtle reasoning. If this inst is a LandingPad,
3019       // all the predecessors of this block will be the unwind edges of Invokes,
3020       // and we can therefore guarantee this block will be erased.
3021     }
3022
3023     // Delete this instruction (any uses are guaranteed to be dead)
3024     if (!BBI->use_empty())
3025       BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
3026     BBI->eraseFromParent();
3027     Changed = true;
3028   }
3029
3030   // If the unreachable instruction is the first in the block, take a gander
3031   // at all of the predecessors of this instruction, and simplify them.
3032   if (&BB->front() != UI) return Changed;
3033
3034   SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB));
3035   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
3036     TerminatorInst *TI = Preds[i]->getTerminator();
3037     IRBuilder<> Builder(TI);
3038     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
3039       if (BI->isUnconditional()) {
3040         if (BI->getSuccessor(0) == BB) {
3041           new UnreachableInst(TI->getContext(), TI);
3042           TI->eraseFromParent();
3043           Changed = true;
3044         }
3045       } else {
3046         if (BI->getSuccessor(0) == BB) {
3047           Builder.CreateBr(BI->getSuccessor(1));
3048           EraseTerminatorInstAndDCECond(BI);
3049         } else if (BI->getSuccessor(1) == BB) {
3050           Builder.CreateBr(BI->getSuccessor(0));
3051           EraseTerminatorInstAndDCECond(BI);
3052           Changed = true;
3053         }
3054       }
3055     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
3056       for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
3057            i != e; ++i)
3058         if (i.getCaseSuccessor() == BB) {
3059           BB->removePredecessor(SI->getParent());
3060           SI->removeCase(i);
3061           --i; --e;
3062           Changed = true;
3063         }
3064       // If the default value is unreachable, figure out the most popular
3065       // destination and make it the default.
3066       if (SI->getDefaultDest() == BB) {
3067         std::map<BasicBlock*, std::pair<unsigned, unsigned> > Popularity;
3068         for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
3069              i != e; ++i) {
3070           std::pair<unsigned, unsigned> &entry =
3071               Popularity[i.getCaseSuccessor()];
3072           if (entry.first == 0) {
3073             entry.first = 1;
3074             entry.second = i.getCaseIndex();
3075           } else {
3076             entry.first++;
3077           }
3078         }
3079
3080         // Find the most popular block.
3081         unsigned MaxPop = 0;
3082         unsigned MaxIndex = 0;
3083         BasicBlock *MaxBlock = nullptr;
3084         for (std::map<BasicBlock*, std::pair<unsigned, unsigned> >::iterator
3085              I = Popularity.begin(), E = Popularity.end(); I != E; ++I) {
3086           if (I->second.first > MaxPop ||
3087               (I->second.first == MaxPop && MaxIndex > I->second.second)) {
3088             MaxPop = I->second.first;
3089             MaxIndex = I->second.second;
3090             MaxBlock = I->first;
3091           }
3092         }
3093         if (MaxBlock) {
3094           // Make this the new default, allowing us to delete any explicit
3095           // edges to it.
3096           SI->setDefaultDest(MaxBlock);
3097           Changed = true;
3098
3099           // If MaxBlock has phinodes in it, remove MaxPop-1 entries from
3100           // it.
3101           if (isa<PHINode>(MaxBlock->begin()))
3102             for (unsigned i = 0; i != MaxPop-1; ++i)
3103               MaxBlock->removePredecessor(SI->getParent());
3104
3105           for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
3106                i != e; ++i)
3107             if (i.getCaseSuccessor() == MaxBlock) {
3108               SI->removeCase(i);
3109               --i; --e;
3110             }
3111         }
3112       }
3113     } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
3114       if (II->getUnwindDest() == BB) {
3115         // Convert the invoke to a call instruction.  This would be a good
3116         // place to note that the call does not throw though.
3117         BranchInst *BI = Builder.CreateBr(II->getNormalDest());
3118         II->removeFromParent();   // Take out of symbol table
3119
3120         // Insert the call now...
3121         SmallVector<Value*, 8> Args(II->op_begin(), II->op_end()-3);
3122         Builder.SetInsertPoint(BI);
3123         CallInst *CI = Builder.CreateCall(II->getCalledValue(),
3124                                           Args, II->getName());
3125         CI->setCallingConv(II->getCallingConv());
3126         CI->setAttributes(II->getAttributes());
3127         // If the invoke produced a value, the call does now instead.
3128         II->replaceAllUsesWith(CI);
3129         delete II;
3130         Changed = true;
3131       }
3132     }
3133   }
3134
3135   // If this block is now dead, remove it.
3136   if (pred_begin(BB) == pred_end(BB) &&
3137       BB != &BB->getParent()->getEntryBlock()) {
3138     // We know there are no successors, so just nuke the block.
3139     BB->eraseFromParent();
3140     return true;
3141   }
3142
3143   return Changed;
3144 }
3145
3146 /// TurnSwitchRangeIntoICmp - Turns a switch with that contains only a
3147 /// integer range comparison into a sub, an icmp and a branch.
3148 static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) {
3149   assert(SI->getNumCases() > 1 && "Degenerate switch?");
3150
3151   // Make sure all cases point to the same destination and gather the values.
3152   SmallVector<ConstantInt *, 16> Cases;
3153   SwitchInst::CaseIt I = SI->case_begin();
3154   Cases.push_back(I.getCaseValue());
3155   SwitchInst::CaseIt PrevI = I++;
3156   for (SwitchInst::CaseIt E = SI->case_end(); I != E; PrevI = I++) {
3157     if (PrevI.getCaseSuccessor() != I.getCaseSuccessor())
3158       return false;
3159     Cases.push_back(I.getCaseValue());
3160   }
3161   assert(Cases.size() == SI->getNumCases() && "Not all cases gathered");
3162
3163   // Sort the case values, then check if they form a range we can transform.
3164   array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate);
3165   for (unsigned I = 1, E = Cases.size(); I != E; ++I) {
3166     if (Cases[I-1]->getValue() != Cases[I]->getValue()+1)
3167       return false;
3168   }
3169
3170   Constant *Offset = ConstantExpr::getNeg(Cases.back());
3171   Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases());
3172
3173   Value *Sub = SI->getCondition();
3174   if (!Offset->isNullValue())
3175     Sub = Builder.CreateAdd(Sub, Offset, Sub->getName()+".off");
3176   Value *Cmp;
3177   // If NumCases overflowed, then all possible values jump to the successor.
3178   if (NumCases->isNullValue() && SI->getNumCases() != 0)
3179     Cmp = ConstantInt::getTrue(SI->getContext());
3180   else
3181     Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch");
3182   BranchInst *NewBI = Builder.CreateCondBr(
3183       Cmp, SI->case_begin().getCaseSuccessor(), SI->getDefaultDest());
3184
3185   // Update weight for the newly-created conditional branch.
3186   SmallVector<uint64_t, 8> Weights;
3187   bool HasWeights = HasBranchWeights(SI);
3188   if (HasWeights) {
3189     GetBranchWeights(SI, Weights);
3190     if (Weights.size() == 1 + SI->getNumCases()) {
3191       // Combine all weights for the cases to be the true weight of NewBI.
3192       // We assume that the sum of all weights for a Terminator can fit into 32
3193       // bits.
3194       uint32_t NewTrueWeight = 0;
3195       for (unsigned I = 1, E = Weights.size(); I != E; ++I)
3196         NewTrueWeight += (uint32_t)Weights[I];
3197       NewBI->setMetadata(LLVMContext::MD_prof,
3198                          MDBuilder(SI->getContext()).
3199                          createBranchWeights(NewTrueWeight,
3200                                              (uint32_t)Weights[0]));
3201     }
3202   }
3203
3204   // Prune obsolete incoming values off the successor's PHI nodes.
3205   for (BasicBlock::iterator BBI = SI->case_begin().getCaseSuccessor()->begin();
3206        isa<PHINode>(BBI); ++BBI) {
3207     for (unsigned I = 0, E = SI->getNumCases()-1; I != E; ++I)
3208       cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
3209   }
3210   SI->eraseFromParent();
3211
3212   return true;
3213 }
3214
3215 /// EliminateDeadSwitchCases - Compute masked bits for the condition of a switch
3216 /// and use it to remove dead cases.
3217 static bool EliminateDeadSwitchCases(SwitchInst *SI, const DataLayout *DL,
3218                                      AssumptionTracker *AT) {
3219   Value *Cond = SI->getCondition();
3220   unsigned Bits = Cond->getType()->getIntegerBitWidth();
3221   APInt KnownZero(Bits, 0), KnownOne(Bits, 0);
3222   computeKnownBits(Cond, KnownZero, KnownOne, DL, 0, AT, SI);
3223
3224   // Gather dead cases.
3225   SmallVector<ConstantInt*, 8> DeadCases;
3226   for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) {
3227     if ((I.getCaseValue()->getValue() & KnownZero) != 0 ||
3228         (I.getCaseValue()->getValue() & KnownOne) != KnownOne) {
3229       DeadCases.push_back(I.getCaseValue());
3230       DEBUG(dbgs() << "SimplifyCFG: switch case '"
3231                    << I.getCaseValue() << "' is dead.\n");
3232     }
3233   }
3234
3235   SmallVector<uint64_t, 8> Weights;
3236   bool HasWeight = HasBranchWeights(SI);
3237   if (HasWeight) {
3238     GetBranchWeights(SI, Weights);
3239     HasWeight = (Weights.size() == 1 + SI->getNumCases());
3240   }
3241
3242   // Remove dead cases from the switch.
3243   for (unsigned I = 0, E = DeadCases.size(); I != E; ++I) {
3244     SwitchInst::CaseIt Case = SI->findCaseValue(DeadCases[I]);
3245     assert(Case != SI->case_default() &&
3246            "Case was not found. Probably mistake in DeadCases forming.");
3247     if (HasWeight) {
3248       std::swap(Weights[Case.getCaseIndex()+1], Weights.back());
3249       Weights.pop_back();
3250     }
3251
3252     // Prune unused values from PHI nodes.
3253     Case.getCaseSuccessor()->removePredecessor(SI->getParent());
3254     SI->removeCase(Case);
3255   }
3256   if (HasWeight && Weights.size() >= 2) {
3257     SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
3258     SI->setMetadata(LLVMContext::MD_prof,
3259                     MDBuilder(SI->getParent()->getContext()).
3260                     createBranchWeights(MDWeights));
3261   }
3262
3263   return !DeadCases.empty();
3264 }
3265
3266 /// FindPHIForConditionForwarding - If BB would be eligible for simplification
3267 /// by TryToSimplifyUncondBranchFromEmptyBlock (i.e. it is empty and terminated
3268 /// by an unconditional branch), look at the phi node for BB in the successor
3269 /// block and see if the incoming value is equal to CaseValue. If so, return
3270 /// the phi node, and set PhiIndex to BB's index in the phi node.
3271 static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue,
3272                                               BasicBlock *BB,
3273                                               int *PhiIndex) {
3274   if (BB->getFirstNonPHIOrDbg() != BB->getTerminator())
3275     return nullptr; // BB must be empty to be a candidate for simplification.
3276   if (!BB->getSinglePredecessor())
3277     return nullptr; // BB must be dominated by the switch.
3278
3279   BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator());
3280   if (!Branch || !Branch->isUnconditional())
3281     return nullptr; // Terminator must be unconditional branch.
3282
3283   BasicBlock *Succ = Branch->getSuccessor(0);
3284
3285   BasicBlock::iterator I = Succ->begin();
3286   while (PHINode *PHI = dyn_cast<PHINode>(I++)) {
3287     int Idx = PHI->getBasicBlockIndex(BB);
3288     assert(Idx >= 0 && "PHI has no entry for predecessor?");
3289
3290     Value *InValue = PHI->getIncomingValue(Idx);
3291     if (InValue != CaseValue) continue;
3292
3293     *PhiIndex = Idx;
3294     return PHI;
3295   }
3296
3297   return nullptr;
3298 }
3299
3300 /// ForwardSwitchConditionToPHI - Try to forward the condition of a switch
3301 /// instruction to a phi node dominated by the switch, if that would mean that
3302 /// some of the destination blocks of the switch can be folded away.
3303 /// Returns true if a change is made.
3304 static bool ForwardSwitchConditionToPHI(SwitchInst *SI) {
3305   typedef DenseMap<PHINode*, SmallVector<int,4> > ForwardingNodesMap;
3306   ForwardingNodesMap ForwardingNodes;
3307
3308   for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) {
3309     ConstantInt *CaseValue = I.getCaseValue();
3310     BasicBlock *CaseDest = I.getCaseSuccessor();
3311
3312     int PhiIndex;
3313     PHINode *PHI = FindPHIForConditionForwarding(CaseValue, CaseDest,
3314                                                  &PhiIndex);
3315     if (!PHI) continue;
3316
3317     ForwardingNodes[PHI].push_back(PhiIndex);
3318   }
3319
3320   bool Changed = false;
3321
3322   for (ForwardingNodesMap::iterator I = ForwardingNodes.begin(),
3323        E = ForwardingNodes.end(); I != E; ++I) {
3324     PHINode *Phi = I->first;
3325     SmallVectorImpl<int> &Indexes = I->second;
3326
3327     if (Indexes.size() < 2) continue;
3328
3329     for (size_t I = 0, E = Indexes.size(); I != E; ++I)
3330       Phi->setIncomingValue(Indexes[I], SI->getCondition());
3331     Changed = true;
3332   }
3333
3334   return Changed;
3335 }
3336
3337 /// ValidLookupTableConstant - Return true if the backend will be able to handle
3338 /// initializing an array of constants like C.
3339 static bool ValidLookupTableConstant(Constant *C) {
3340   if (C->isThreadDependent())