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