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