LLVM  8.0.0svn
SimplifyCFG.cpp
Go to the documentation of this file.
1 //===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Peephole optimize the CFG.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/ADT/APInt.h"
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/Optional.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SetOperations.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/ADT/StringRef.h"
32 #include "llvm/IR/Attributes.h"
33 #include "llvm/IR/BasicBlock.h"
34 #include "llvm/IR/CFG.h"
35 #include "llvm/IR/CallSite.h"
36 #include "llvm/IR/Constant.h"
37 #include "llvm/IR/ConstantRange.h"
38 #include "llvm/IR/Constants.h"
39 #include "llvm/IR/DataLayout.h"
40 #include "llvm/IR/DerivedTypes.h"
41 #include "llvm/IR/Function.h"
42 #include "llvm/IR/GlobalValue.h"
43 #include "llvm/IR/GlobalVariable.h"
44 #include "llvm/IR/IRBuilder.h"
45 #include "llvm/IR/InstrTypes.h"
46 #include "llvm/IR/Instruction.h"
47 #include "llvm/IR/Instructions.h"
48 #include "llvm/IR/IntrinsicInst.h"
49 #include "llvm/IR/Intrinsics.h"
50 #include "llvm/IR/LLVMContext.h"
51 #include "llvm/IR/MDBuilder.h"
52 #include "llvm/IR/Metadata.h"
53 #include "llvm/IR/Module.h"
54 #include "llvm/IR/NoFolder.h"
55 #include "llvm/IR/Operator.h"
56 #include "llvm/IR/PatternMatch.h"
57 #include "llvm/IR/Type.h"
58 #include "llvm/IR/Use.h"
59 #include "llvm/IR/User.h"
60 #include "llvm/IR/Value.h"
61 #include "llvm/Support/Casting.h"
63 #include "llvm/Support/Debug.h"
65 #include "llvm/Support/KnownBits.h"
70 #include <algorithm>
71 #include <cassert>
72 #include <climits>
73 #include <cstddef>
74 #include <cstdint>
75 #include <iterator>
76 #include <map>
77 #include <set>
78 #include <tuple>
79 #include <utility>
80 #include <vector>
81 
82 using namespace llvm;
83 using namespace PatternMatch;
84 
85 #define DEBUG_TYPE "simplifycfg"
86 
87 // Chosen as 2 so as to be cheap, but still to have enough power to fold
88 // a select, so the "clamp" idiom (of a min followed by a max) will be caught.
89 // To catch this, we need to fold a compare and a select, hence '2' being the
90 // minimum reasonable default.
92  "phi-node-folding-threshold", cl::Hidden, cl::init(2),
93  cl::desc(
94  "Control the amount of phi node folding to perform (default = 2)"));
95 
96 static cl::opt<bool> DupRet(
97  "simplifycfg-dup-ret", cl::Hidden, cl::init(false),
98  cl::desc("Duplicate return instructions into unconditional branches"));
99 
100 static cl::opt<bool>
101  SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true),
102  cl::desc("Sink common instructions down to the end block"));
103 
105  "simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true),
106  cl::desc("Hoist conditional stores if an unconditional store precedes"));
107 
109  "simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true),
110  cl::desc("Hoist conditional stores even if an unconditional store does not "
111  "precede - hoist multiple conditional stores into a single "
112  "predicated store"));
113 
115  "simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false),
116  cl::desc("When merging conditional stores, do so even if the resultant "
117  "basic blocks are unlikely to be if-converted as a result"));
118 
120  "speculate-one-expensive-inst", cl::Hidden, cl::init(true),
121  cl::desc("Allow exactly one expensive instruction to be speculatively "
122  "executed"));
123 
125  "max-speculation-depth", cl::Hidden, cl::init(10),
126  cl::desc("Limit maximum recursion depth when calculating costs of "
127  "speculatively executed instructions"));
128 
129 STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
130 STATISTIC(NumLinearMaps,
131  "Number of switch instructions turned into linear mapping");
132 STATISTIC(NumLookupTables,
133  "Number of switch instructions turned into lookup tables");
134 STATISTIC(
135  NumLookupTablesHoles,
136  "Number of switch instructions turned into lookup tables (holes checked)");
137 STATISTIC(NumTableCmpReuses, "Number of reused switch table lookup compares");
138 STATISTIC(NumSinkCommons,
139  "Number of common instructions sunk down to the end block");
140 STATISTIC(NumSpeculations, "Number of speculative executed instructions");
141 
142 namespace {
143 
144 // The first field contains the value that the switch produces when a certain
145 // case group is selected, and the second field is a vector containing the
146 // cases composing the case group.
147 using SwitchCaseResultVectorTy =
149 
150 // The first field contains the phi node that generates a result of the switch
151 // and the second field contains the value generated for a certain case in the
152 // switch for that PHI.
153 using SwitchCaseResultsTy = SmallVector<std::pair<PHINode *, Constant *>, 4>;
154 
155 /// ValueEqualityComparisonCase - Represents a case of a switch.
156 struct ValueEqualityComparisonCase {
158  BasicBlock *Dest;
159 
160  ValueEqualityComparisonCase(ConstantInt *Value, BasicBlock *Dest)
161  : Value(Value), Dest(Dest) {}
162 
163  bool operator<(ValueEqualityComparisonCase RHS) const {
164  // Comparing pointers is ok as we only rely on the order for uniquing.
165  return Value < RHS.Value;
166  }
167 
168  bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; }
169 };
170 
171 class SimplifyCFGOpt {
172  const TargetTransformInfo &TTI;
173  const DataLayout &DL;
174  SmallPtrSetImpl<BasicBlock *> *LoopHeaders;
175  const SimplifyCFGOptions &Options;
176 
177  Value *isValueEqualityComparison(TerminatorInst *TI);
178  BasicBlock *GetValueEqualityComparisonCases(
179  TerminatorInst *TI, std::vector<ValueEqualityComparisonCase> &Cases);
180  bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
181  BasicBlock *Pred,
182  IRBuilder<> &Builder);
183  bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
184  IRBuilder<> &Builder);
185 
186  bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder);
187  bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder);
188  bool SimplifySingleResume(ResumeInst *RI);
189  bool SimplifyCommonResume(ResumeInst *RI);
190  bool SimplifyCleanupReturn(CleanupReturnInst *RI);
191  bool SimplifyUnreachable(UnreachableInst *UI);
192  bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
193  bool SimplifyIndirectBr(IndirectBrInst *IBI);
194  bool SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder);
195  bool SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder);
196 
197 public:
198  SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL,
199  SmallPtrSetImpl<BasicBlock *> *LoopHeaders,
200  const SimplifyCFGOptions &Opts)
201  : TTI(TTI), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {}
202 
203  bool run(BasicBlock *BB);
204 };
205 
206 } // end anonymous namespace
207 
208 /// Return true if it is safe to merge these two
209 /// terminator instructions together.
210 static bool
212  SmallSetVector<BasicBlock *, 4> *FailBlocks = nullptr) {
213  if (SI1 == SI2)
214  return false; // Can't merge with self!
215 
216  // It is not safe to merge these two switch instructions if they have a common
217  // successor, and if that successor has a PHI node, and if *that* PHI node has
218  // conflicting incoming values from the two switch blocks.
219  BasicBlock *SI1BB = SI1->getParent();
220  BasicBlock *SI2BB = SI2->getParent();
221 
222  SmallPtrSet<BasicBlock *, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
223  bool Fail = false;
224  for (BasicBlock *Succ : successors(SI2BB))
225  if (SI1Succs.count(Succ))
226  for (BasicBlock::iterator BBI = Succ->begin(); isa<PHINode>(BBI); ++BBI) {
227  PHINode *PN = cast<PHINode>(BBI);
228  if (PN->getIncomingValueForBlock(SI1BB) !=
229  PN->getIncomingValueForBlock(SI2BB)) {
230  if (FailBlocks)
231  FailBlocks->insert(Succ);
232  Fail = true;
233  }
234  }
235 
236  return !Fail;
237 }
238 
239 /// Return true if it is safe and profitable to merge these two terminator
240 /// instructions together, where SI1 is an unconditional branch. PhiNodes will
241 /// store all PHI nodes in common successors.
242 static bool
244  Instruction *Cond,
245  SmallVectorImpl<PHINode *> &PhiNodes) {
246  if (SI1 == SI2)
247  return false; // Can't merge with self!
248  assert(SI1->isUnconditional() && SI2->isConditional());
249 
250  // We fold the unconditional branch if we can easily update all PHI nodes in
251  // common successors:
252  // 1> We have a constant incoming value for the conditional branch;
253  // 2> We have "Cond" as the incoming value for the unconditional branch;
254  // 3> SI2->getCondition() and Cond have same operands.
255  CmpInst *Ci2 = dyn_cast<CmpInst>(SI2->getCondition());
256  if (!Ci2)
257  return false;
258  if (!(Cond->getOperand(0) == Ci2->getOperand(0) &&
259  Cond->getOperand(1) == Ci2->getOperand(1)) &&
260  !(Cond->getOperand(0) == Ci2->getOperand(1) &&
261  Cond->getOperand(1) == Ci2->getOperand(0)))
262  return false;
263 
264  BasicBlock *SI1BB = SI1->getParent();
265  BasicBlock *SI2BB = SI2->getParent();
266  SmallPtrSet<BasicBlock *, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
267  for (BasicBlock *Succ : successors(SI2BB))
268  if (SI1Succs.count(Succ))
269  for (BasicBlock::iterator BBI = Succ->begin(); isa<PHINode>(BBI); ++BBI) {
270  PHINode *PN = cast<PHINode>(BBI);
271  if (PN->getIncomingValueForBlock(SI1BB) != Cond ||
272  !isa<ConstantInt>(PN->getIncomingValueForBlock(SI2BB)))
273  return false;
274  PhiNodes.push_back(PN);
275  }
276  return true;
277 }
278 
279 /// Update PHI nodes in Succ to indicate that there will now be entries in it
280 /// from the 'NewPred' block. The values that will be flowing into the PHI nodes
281 /// will be the same as those coming in from ExistPred, an existing predecessor
282 /// of Succ.
283 static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred,
284  BasicBlock *ExistPred) {
285  for (PHINode &PN : Succ->phis())
286  PN.addIncoming(PN.getIncomingValueForBlock(ExistPred), NewPred);
287 }
288 
289 /// Compute an abstract "cost" of speculating the given instruction,
290 /// which is assumed to be safe to speculate. TCC_Free means cheap,
291 /// TCC_Basic means less cheap, and TCC_Expensive means prohibitively
292 /// expensive.
293 static unsigned ComputeSpeculationCost(const User *I,
294  const TargetTransformInfo &TTI) {
296  "Instruction is not safe to speculatively execute!");
297  return TTI.getUserCost(I);
298 }
299 
300 /// If we have a merge point of an "if condition" as accepted above,
301 /// return true if the specified value dominates the block. We
302 /// don't handle the true generality of domination here, just a special case
303 /// which works well enough for us.
304 ///
305 /// If AggressiveInsts is non-null, and if V does not dominate BB, we check to
306 /// see if V (which must be an instruction) and its recursive operands
307 /// that do not dominate BB have a combined cost lower than CostRemaining and
308 /// are non-trapping. If both are true, the instruction is inserted into the
309 /// set and true is returned.
310 ///
311 /// The cost for most non-trapping instructions is defined as 1 except for
312 /// Select whose cost is 2.
313 ///
314 /// After this function returns, CostRemaining is decreased by the cost of
315 /// V plus its non-dominating operands. If that cost is greater than
316 /// CostRemaining, false is returned and CostRemaining is undefined.
318  SmallPtrSetImpl<Instruction *> *AggressiveInsts,
319  unsigned &CostRemaining,
320  const TargetTransformInfo &TTI,
321  unsigned Depth = 0) {
322  // It is possible to hit a zero-cost cycle (phi/gep instructions for example),
323  // so limit the recursion depth.
324  // TODO: While this recursion limit does prevent pathological behavior, it
325  // would be better to track visited instructions to avoid cycles.
326  if (Depth == MaxSpeculationDepth)
327  return false;
328 
330  if (!I) {
331  // Non-instructions all dominate instructions, but not all constantexprs
332  // can be executed unconditionally.
333  if (ConstantExpr *C = dyn_cast<ConstantExpr>(V))
334  if (C->canTrap())
335  return false;
336  return true;
337  }
338  BasicBlock *PBB = I->getParent();
339 
340  // We don't want to allow weird loops that might have the "if condition" in
341  // the bottom of this block.
342  if (PBB == BB)
343  return false;
344 
345  // If this instruction is defined in a block that contains an unconditional
346  // branch to BB, then it must be in the 'conditional' part of the "if
347  // statement". If not, it definitely dominates the region.
349  if (!BI || BI->isConditional() || BI->getSuccessor(0) != BB)
350  return true;
351 
352  // If we aren't allowing aggressive promotion anymore, then don't consider
353  // instructions in the 'if region'.
354  if (!AggressiveInsts)
355  return false;
356 
357  // If we have seen this instruction before, don't count it again.
358  if (AggressiveInsts->count(I))
359  return true;
360 
361  // Okay, it looks like the instruction IS in the "condition". Check to
362  // see if it's a cheap instruction to unconditionally compute, and if it
363  // only uses stuff defined outside of the condition. If so, hoist it out.
365  return false;
366 
367  unsigned Cost = ComputeSpeculationCost(I, TTI);
368 
369  // Allow exactly one instruction to be speculated regardless of its cost
370  // (as long as it is safe to do so).
371  // This is intended to flatten the CFG even if the instruction is a division
372  // or other expensive operation. The speculation of an expensive instruction
373  // is expected to be undone in CodeGenPrepare if the speculation has not
374  // enabled further IR optimizations.
375  if (Cost > CostRemaining &&
376  (!SpeculateOneExpensiveInst || !AggressiveInsts->empty() || Depth > 0))
377  return false;
378 
379  // Avoid unsigned wrap.
380  CostRemaining = (Cost > CostRemaining) ? 0 : CostRemaining - Cost;
381 
382  // Okay, we can only really hoist these out if their operands do
383  // not take us over the cost threshold.
384  for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
385  if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining, TTI,
386  Depth + 1))
387  return false;
388  // Okay, it's safe to do this! Remember this instruction.
389  AggressiveInsts->insert(I);
390  return true;
391 }
392 
393 /// Extract ConstantInt from value, looking through IntToPtr
394 /// and PointerNullValue. Return NULL if value is not a constant int.
395 static ConstantInt *GetConstantInt(Value *V, const DataLayout &DL) {
396  // Normal constant int.
397  ConstantInt *CI = dyn_cast<ConstantInt>(V);
398  if (CI || !isa<Constant>(V) || !V->getType()->isPointerTy())
399  return CI;
400 
401  // This is some kind of pointer constant. Turn it into a pointer-sized
402  // ConstantInt if possible.
403  IntegerType *PtrTy = cast<IntegerType>(DL.getIntPtrType(V->getType()));
404 
405  // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*).
406  if (isa<ConstantPointerNull>(V))
407  return ConstantInt::get(PtrTy, 0);
408 
409  // IntToPtr const int.
410  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
411  if (CE->getOpcode() == Instruction::IntToPtr)
412  if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
413  // The constant is very likely to have the right type already.
414  if (CI->getType() == PtrTy)
415  return CI;
416  else
417  return cast<ConstantInt>(
418  ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false));
419  }
420  return nullptr;
421 }
422 
423 namespace {
424 
425 /// Given a chain of or (||) or and (&&) comparison of a value against a
426 /// constant, this will try to recover the information required for a switch
427 /// structure.
428 /// It will depth-first traverse the chain of comparison, seeking for patterns
429 /// like %a == 12 or %a < 4 and combine them to produce a set of integer
430 /// representing the different cases for the switch.
431 /// Note that if the chain is composed of '||' it will build the set of elements
432 /// that matches the comparisons (i.e. any of this value validate the chain)
433 /// while for a chain of '&&' it will build the set elements that make the test
434 /// fail.
435 struct ConstantComparesGatherer {
436  const DataLayout &DL;
437 
438  /// Value found for the switch comparison
439  Value *CompValue = nullptr;
440 
441  /// Extra clause to be checked before the switch
442  Value *Extra = nullptr;
443 
444  /// Set of integers to match in switch
446 
447  /// Number of comparisons matched in the and/or chain
448  unsigned UsedICmps = 0;
449 
450  /// Construct and compute the result for the comparison instruction Cond
451  ConstantComparesGatherer(Instruction *Cond, const DataLayout &DL) : DL(DL) {
452  gather(Cond);
453  }
454 
455  ConstantComparesGatherer(const ConstantComparesGatherer &) = delete;
456  ConstantComparesGatherer &
457  operator=(const ConstantComparesGatherer &) = delete;
458 
459 private:
460  /// Try to set the current value used for the comparison, it succeeds only if
461  /// it wasn't set before or if the new value is the same as the old one
462  bool setValueOnce(Value *NewVal) {
463  if (CompValue && CompValue != NewVal)
464  return false;
465  CompValue = NewVal;
466  return (CompValue != nullptr);
467  }
468 
469  /// Try to match Instruction "I" as a comparison against a constant and
470  /// populates the array Vals with the set of values that match (or do not
471  /// match depending on isEQ).
472  /// Return false on failure. On success, the Value the comparison matched
473  /// against is placed in CompValue.
474  /// If CompValue is already set, the function is expected to fail if a match
475  /// is found but the value compared to is different.
476  bool matchInstruction(Instruction *I, bool isEQ) {
477  // If this is an icmp against a constant, handle this as one of the cases.
478  ICmpInst *ICI;
479  ConstantInt *C;
480  if (!((ICI = dyn_cast<ICmpInst>(I)) &&
481  (C = GetConstantInt(I->getOperand(1), DL)))) {
482  return false;
483  }
484 
485  Value *RHSVal;
486  const APInt *RHSC;
487 
488  // Pattern match a special case
489  // (x & ~2^z) == y --> x == y || x == y|2^z
490  // This undoes a transformation done by instcombine to fuse 2 compares.
491  if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) {
492  // It's a little bit hard to see why the following transformations are
493  // correct. Here is a CVC3 program to verify them for 64-bit values:
494 
495  /*
496  ONE : BITVECTOR(64) = BVZEROEXTEND(0bin1, 63);
497  x : BITVECTOR(64);
498  y : BITVECTOR(64);
499  z : BITVECTOR(64);
500  mask : BITVECTOR(64) = BVSHL(ONE, z);
501  QUERY( (y & ~mask = y) =>
502  ((x & ~mask = y) <=> (x = y OR x = (y | mask)))
503  );
504  QUERY( (y | mask = y) =>
505  ((x | mask = y) <=> (x = y OR x = (y & ~mask)))
506  );
507  */
508 
509  // Please note that each pattern must be a dual implication (<--> or
510  // iff). One directional implication can create spurious matches. If the
511  // implication is only one-way, an unsatisfiable condition on the left
512  // side can imply a satisfiable condition on the right side. Dual
513  // implication ensures that satisfiable conditions are transformed to
514  // other satisfiable conditions and unsatisfiable conditions are
515  // transformed to other unsatisfiable conditions.
516 
517  // Here is a concrete example of a unsatisfiable condition on the left
518  // implying a satisfiable condition on the right:
519  //
520  // mask = (1 << z)
521  // (x & ~mask) == y --> (x == y || x == (y | mask))
522  //
523  // Substituting y = 3, z = 0 yields:
524  // (x & -2) == 3 --> (x == 3 || x == 2)
525 
526  // Pattern match a special case:
527  /*
528  QUERY( (y & ~mask = y) =>
529  ((x & ~mask = y) <=> (x = y OR x = (y | mask)))
530  );
531  */
532  if (match(ICI->getOperand(0),
533  m_And(m_Value(RHSVal), m_APInt(RHSC)))) {
534  APInt Mask = ~*RHSC;
535  if (Mask.isPowerOf2() && (C->getValue() & ~Mask) == C->getValue()) {
536  // If we already have a value for the switch, it has to match!
537  if (!setValueOnce(RHSVal))
538  return false;
539 
540  Vals.push_back(C);
541  Vals.push_back(
543  C->getValue() | Mask));
544  UsedICmps++;
545  return true;
546  }
547  }
548 
549  // Pattern match a special case:
550  /*
551  QUERY( (y | mask = y) =>
552  ((x | mask = y) <=> (x = y OR x = (y & ~mask)))
553  );
554  */
555  if (match(ICI->getOperand(0),
556  m_Or(m_Value(RHSVal), m_APInt(RHSC)))) {
557  APInt Mask = *RHSC;
558  if (Mask.isPowerOf2() && (C->getValue() | Mask) == C->getValue()) {
559  // If we already have a value for the switch, it has to match!
560  if (!setValueOnce(RHSVal))
561  return false;
562 
563  Vals.push_back(C);
565  C->getValue() & ~Mask));
566  UsedICmps++;
567  return true;
568  }
569  }
570 
571  // If we already have a value for the switch, it has to match!
572  if (!setValueOnce(ICI->getOperand(0)))
573  return false;
574 
575  UsedICmps++;
576  Vals.push_back(C);
577  return ICI->getOperand(0);
578  }
579 
580  // If we have "x ult 3", for example, then we can add 0,1,2 to the set.
582  ICI->getPredicate(), C->getValue());
583 
584  // Shift the range if the compare is fed by an add. This is the range
585  // compare idiom as emitted by instcombine.
586  Value *CandidateVal = I->getOperand(0);
587  if (match(I->getOperand(0), m_Add(m_Value(RHSVal), m_APInt(RHSC)))) {
588  Span = Span.subtract(*RHSC);
589  CandidateVal = RHSVal;
590  }
591 
592  // If this is an and/!= check, then we are looking to build the set of
593  // value that *don't* pass the and chain. I.e. to turn "x ugt 2" into
594  // x != 0 && x != 1.
595  if (!isEQ)
596  Span = Span.inverse();
597 
598  // If there are a ton of values, we don't want to make a ginormous switch.
599  if (Span.isSizeLargerThan(8) || Span.isEmptySet()) {
600  return false;
601  }
602 
603  // If we already have a value for the switch, it has to match!
604  if (!setValueOnce(CandidateVal))
605  return false;
606 
607  // Add all values from the range to the set
608  for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp)
609  Vals.push_back(ConstantInt::get(I->getContext(), Tmp));
610 
611  UsedICmps++;
612  return true;
613  }
614 
615  /// Given a potentially 'or'd or 'and'd together collection of icmp
616  /// eq/ne/lt/gt instructions that compare a value against a constant, extract
617  /// the value being compared, and stick the list constants into the Vals
618  /// vector.
619  /// One "Extra" case is allowed to differ from the other.
620  void gather(Value *V) {
622  bool isEQ = (I->getOpcode() == Instruction::Or);
623 
624  // Keep a stack (SmallVector for efficiency) for depth-first traversal
626  SmallPtrSet<Value *, 8> Visited;
627 
628  // Initialize
629  Visited.insert(V);
630  DFT.push_back(V);
631 
632  while (!DFT.empty()) {
633  V = DFT.pop_back_val();
634 
635  if (Instruction *I = dyn_cast<Instruction>(V)) {
636  // If it is a || (or && depending on isEQ), process the operands.
637  if (I->getOpcode() == (isEQ ? Instruction::Or : Instruction::And)) {
638  if (Visited.insert(I->getOperand(1)).second)
639  DFT.push_back(I->getOperand(1));
640  if (Visited.insert(I->getOperand(0)).second)
641  DFT.push_back(I->getOperand(0));
642  continue;
643  }
644 
645  // Try to match the current instruction
646  if (matchInstruction(I, isEQ))
647  // Match succeed, continue the loop
648  continue;
649  }
650 
651  // One element of the sequence of || (or &&) could not be match as a
652  // comparison against the same value as the others.
653  // We allow only one "Extra" case to be checked before the switch
654  if (!Extra) {
655  Extra = V;
656  continue;
657  }
658  // Failed to parse a proper sequence, abort now
659  CompValue = nullptr;
660  break;
661  }
662  }
663 };
664 
665 } // end anonymous namespace
666 
668  Instruction *Cond = nullptr;
669  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
670  Cond = dyn_cast<Instruction>(SI->getCondition());
671  } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
672  if (BI->isConditional())
673  Cond = dyn_cast<Instruction>(BI->getCondition());
674  } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(TI)) {
675  Cond = dyn_cast<Instruction>(IBI->getAddress());
676  }
677 
678  TI->eraseFromParent();
679  if (Cond)
681 }
682 
683 /// Return true if the specified terminator checks
684 /// to see if a value is equal to constant integer value.
685 Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) {
686  Value *CV = nullptr;
687  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
688  // Do not permit merging of large switch instructions into their
689  // predecessors unless there is only one predecessor.
690  if (SI->getNumSuccessors() * pred_size(SI->getParent()) <= 128)
691  CV = SI->getCondition();
692  } else if (BranchInst *BI = dyn_cast<BranchInst>(TI))
693  if (BI->isConditional() && BI->getCondition()->hasOneUse())
694  if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
695  if (ICI->isEquality() && GetConstantInt(ICI->getOperand(1), DL))
696  CV = ICI->getOperand(0);
697  }
698 
699  // Unwrap any lossless ptrtoint cast.
700  if (CV) {
701  if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV)) {
702  Value *Ptr = PTII->getPointerOperand();
703  if (PTII->getType() == DL.getIntPtrType(Ptr->getType()))
704  CV = Ptr;
705  }
706  }
707  return CV;
708 }
709 
710 /// Given a value comparison instruction,
711 /// decode all of the 'cases' that it represents and return the 'default' block.
712 BasicBlock *SimplifyCFGOpt::GetValueEqualityComparisonCases(
713  TerminatorInst *TI, std::vector<ValueEqualityComparisonCase> &Cases) {
714  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
715  Cases.reserve(SI->getNumCases());
716  for (auto Case : SI->cases())
717  Cases.push_back(ValueEqualityComparisonCase(Case.getCaseValue(),
718  Case.getCaseSuccessor()));
719  return SI->getDefaultDest();
720  }
721 
722  BranchInst *BI = cast<BranchInst>(TI);
723  ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
724  BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE);
725  Cases.push_back(ValueEqualityComparisonCase(
726  GetConstantInt(ICI->getOperand(1), DL), Succ));
727  return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ);
728 }
729 
730 /// Given a vector of bb/value pairs, remove any entries
731 /// in the list that match the specified block.
732 static void
734  std::vector<ValueEqualityComparisonCase> &Cases) {
735  Cases.erase(std::remove(Cases.begin(), Cases.end(), BB), Cases.end());
736 }
737 
738 /// Return true if there are any keys in C1 that exist in C2 as well.
739 static bool ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1,
740  std::vector<ValueEqualityComparisonCase> &C2) {
741  std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
742 
743  // Make V1 be smaller than V2.
744  if (V1->size() > V2->size())
745  std::swap(V1, V2);
746 
747  if (V1->empty())
748  return false;
749  if (V1->size() == 1) {
750  // Just scan V2.
751  ConstantInt *TheVal = (*V1)[0].Value;
752  for (unsigned i = 0, e = V2->size(); i != e; ++i)
753  if (TheVal == (*V2)[i].Value)
754  return true;
755  }
756 
757  // Otherwise, just sort both lists and compare element by element.
758  array_pod_sort(V1->begin(), V1->end());
759  array_pod_sort(V2->begin(), V2->end());
760  unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
761  while (i1 != e1 && i2 != e2) {
762  if ((*V1)[i1].Value == (*V2)[i2].Value)
763  return true;
764  if ((*V1)[i1].Value < (*V2)[i2].Value)
765  ++i1;
766  else
767  ++i2;
768  }
769  return false;
770 }
771 
772 // Set branch weights on SwitchInst. This sets the metadata if there is at
773 // least one non-zero weight.
775  // Check that there is at least one non-zero weight. Otherwise, pass
776  // nullptr to setMetadata which will erase the existing metadata.
777  MDNode *N = nullptr;
778  if (llvm::any_of(Weights, [](uint32_t W) { return W != 0; }))
779  N = MDBuilder(SI->getParent()->getContext()).createBranchWeights(Weights);
781 }
782 
783 // Similar to the above, but for branch and select instructions that take
784 // exactly 2 weights.
785 static void setBranchWeights(Instruction *I, uint32_t TrueWeight,
786  uint32_t FalseWeight) {
787  assert(isa<BranchInst>(I) || isa<SelectInst>(I));
788  // Check that there is at least one non-zero weight. Otherwise, pass
789  // nullptr to setMetadata which will erase the existing metadata.
790  MDNode *N = nullptr;
791  if (TrueWeight || FalseWeight)
792  N = MDBuilder(I->getParent()->getContext())
793  .createBranchWeights(TrueWeight, FalseWeight);
795 }
796 
797 /// If TI is known to be a terminator instruction and its block is known to
798 /// only have a single predecessor block, check to see if that predecessor is
799 /// also a value comparison with the same value, and if that comparison
800 /// determines the outcome of this comparison. If so, simplify TI. This does a
801 /// very limited form of jump threading.
802 bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor(
803  TerminatorInst *TI, BasicBlock *Pred, IRBuilder<> &Builder) {
804  Value *PredVal = isValueEqualityComparison(Pred->getTerminator());
805  if (!PredVal)
806  return false; // Not a value comparison in predecessor.
807 
808  Value *ThisVal = isValueEqualityComparison(TI);
809  assert(ThisVal && "This isn't a value comparison!!");
810  if (ThisVal != PredVal)
811  return false; // Different predicates.
812 
813  // TODO: Preserve branch weight metadata, similarly to how
814  // FoldValueComparisonIntoPredecessors preserves it.
815 
816  // Find out information about when control will move from Pred to TI's block.
817  std::vector<ValueEqualityComparisonCase> PredCases;
818  BasicBlock *PredDef =
819  GetValueEqualityComparisonCases(Pred->getTerminator(), PredCases);
820  EliminateBlockCases(PredDef, PredCases); // Remove default from cases.
821 
822  // Find information about how control leaves this block.
823  std::vector<ValueEqualityComparisonCase> ThisCases;
824  BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
825  EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases.
826 
827  // If TI's block is the default block from Pred's comparison, potentially
828  // simplify TI based on this knowledge.
829  if (PredDef == TI->getParent()) {
830  // If we are here, we know that the value is none of those cases listed in
831  // PredCases. If there are any cases in ThisCases that are in PredCases, we
832  // can simplify TI.
833  if (!ValuesOverlap(PredCases, ThisCases))
834  return false;
835 
836  if (isa<BranchInst>(TI)) {
837  // Okay, one of the successors of this condbr is dead. Convert it to a
838  // uncond br.
839  assert(ThisCases.size() == 1 && "Branch can only have one case!");
840  // Insert the new branch.
841  Instruction *NI = Builder.CreateBr(ThisDef);
842  (void)NI;
843 
844  // Remove PHI node entries for the dead edge.
845  ThisCases[0].Dest->removePredecessor(TI->getParent());
846 
847  LLVM_DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
848  << "Through successor TI: " << *TI << "Leaving: " << *NI
849  << "\n");
850 
852  return true;
853  }
854 
855  SwitchInst *SI = cast<SwitchInst>(TI);
856  // Okay, TI has cases that are statically dead, prune them away.
857  SmallPtrSet<Constant *, 16> DeadCases;
858  for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
859  DeadCases.insert(PredCases[i].Value);
860 
861  LLVM_DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
862  << "Through successor TI: " << *TI);
863 
864  // Collect branch weights into a vector.
865  SmallVector<uint32_t, 8> Weights;
867  bool HasWeight = MD && (MD->getNumOperands() == 2 + SI->getNumCases());
868  if (HasWeight)
869  for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
870  ++MD_i) {
871  ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(MD_i));
872  Weights.push_back(CI->getValue().getZExtValue());
873  }
874  for (SwitchInst::CaseIt i = SI->case_end(), e = SI->case_begin(); i != e;) {
875  --i;
876  if (DeadCases.count(i->getCaseValue())) {
877  if (HasWeight) {
878  std::swap(Weights[i->getCaseIndex() + 1], Weights.back());
879  Weights.pop_back();
880  }
881  i->getCaseSuccessor()->removePredecessor(TI->getParent());
882  SI->removeCase(i);
883  }
884  }
885  if (HasWeight && Weights.size() >= 2)
886  setBranchWeights(SI, Weights);
887 
888  LLVM_DEBUG(dbgs() << "Leaving: " << *TI << "\n");
889  return true;
890  }
891 
892  // Otherwise, TI's block must correspond to some matched value. Find out
893  // which value (or set of values) this is.
894  ConstantInt *TIV = nullptr;
895  BasicBlock *TIBB = TI->getParent();
896  for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
897  if (PredCases[i].Dest == TIBB) {
898  if (TIV)
899  return false; // Cannot handle multiple values coming to this block.
900  TIV = PredCases[i].Value;
901  }
902  assert(TIV && "No edge from pred to succ?");
903 
904  // Okay, we found the one constant that our value can be if we get into TI's
905  // BB. Find out which successor will unconditionally be branched to.
906  BasicBlock *TheRealDest = nullptr;
907  for (unsigned i = 0, e = ThisCases.size(); i != e; ++i)
908  if (ThisCases[i].Value == TIV) {
909  TheRealDest = ThisCases[i].Dest;
910  break;
911  }
912 
913  // If not handled by any explicit cases, it is handled by the default case.
914  if (!TheRealDest)
915  TheRealDest = ThisDef;
916 
917  // Remove PHI node entries for dead edges.
918  BasicBlock *CheckEdge = TheRealDest;
919  for (BasicBlock *Succ : successors(TIBB))
920  if (Succ != CheckEdge)
921  Succ->removePredecessor(TIBB);
922  else
923  CheckEdge = nullptr;
924 
925  // Insert the new branch.
926  Instruction *NI = Builder.CreateBr(TheRealDest);
927  (void)NI;
928 
929  LLVM_DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
930  << "Through successor TI: " << *TI << "Leaving: " << *NI
931  << "\n");
932 
934  return true;
935 }
936 
937 namespace {
938 
939 /// This class implements a stable ordering of constant
940 /// integers that does not depend on their address. This is important for
941 /// applications that sort ConstantInt's to ensure uniqueness.
942 struct ConstantIntOrdering {
943  bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const {
944  return LHS->getValue().ult(RHS->getValue());
945  }
946 };
947 
948 } // end anonymous namespace
949 
950 static int ConstantIntSortPredicate(ConstantInt *const *P1,
951  ConstantInt *const *P2) {
952  const ConstantInt *LHS = *P1;
953  const ConstantInt *RHS = *P2;
954  if (LHS == RHS)
955  return 0;
956  return LHS->getValue().ult(RHS->getValue()) ? 1 : -1;
957 }
958 
959 static inline bool HasBranchWeights(const Instruction *I) {
961  if (ProfMD && ProfMD->getOperand(0))
962  if (MDString *MDS = dyn_cast<MDString>(ProfMD->getOperand(0)))
963  return MDS->getString().equals("branch_weights");
964 
965  return false;
966 }
967 
968 /// Get Weights of a given TerminatorInst, the default weight is at the front
969 /// of the vector. If TI is a conditional eq, we need to swap the branch-weight
970 /// metadata.
972  SmallVectorImpl<uint64_t> &Weights) {
974  assert(MD);
975  for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) {
976  ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(i));
977  Weights.push_back(CI->getValue().getZExtValue());
978  }
979 
980  // If TI is a conditional eq, the default case is the false case,
981  // and the corresponding branch-weight data is at index 2. We swap the
982  // default weight to be the first entry.
983  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
984  assert(Weights.size() == 2);
985  ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
986  if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
987  std::swap(Weights.front(), Weights.back());
988  }
989 }
990 
991 /// Keep halving the weights until all can fit in uint32_t.
992 static void FitWeights(MutableArrayRef<uint64_t> Weights) {
993  uint64_t Max = *std::max_element(Weights.begin(), Weights.end());
994  if (Max > UINT_MAX) {
995  unsigned Offset = 32 - countLeadingZeros(Max);
996  for (uint64_t &I : Weights)
997  I >>= Offset;
998  }
999 }
1000 
1001 /// The specified terminator is a value equality comparison instruction
1002 /// (either a switch or a branch on "X == c").
1003 /// See if any of the predecessors of the terminator block are value comparisons
1004 /// on the same value. If so, and if safe to do so, fold them together.
1005 bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
1006  IRBuilder<> &Builder) {
1007  BasicBlock *BB = TI->getParent();
1008  Value *CV = isValueEqualityComparison(TI); // CondVal
1009  assert(CV && "Not a comparison?");
1010  bool Changed = false;
1011 
1013  while (!Preds.empty()) {
1014  BasicBlock *Pred = Preds.pop_back_val();
1015 
1016  // See if the predecessor is a comparison with the same value.
1017  TerminatorInst *PTI = Pred->getTerminator();
1018  Value *PCV = isValueEqualityComparison(PTI); // PredCondVal
1019 
1020  if (PCV == CV && TI != PTI) {
1021  SmallSetVector<BasicBlock*, 4> FailBlocks;
1022  if (!SafeToMergeTerminators(TI, PTI, &FailBlocks)) {
1023  for (auto *Succ : FailBlocks) {
1024  if (!SplitBlockPredecessors(Succ, TI->getParent(), ".fold.split"))
1025  return false;
1026  }
1027  }
1028 
1029  // Figure out which 'cases' to copy from SI to PSI.
1030  std::vector<ValueEqualityComparisonCase> BBCases;
1031  BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
1032 
1033  std::vector<ValueEqualityComparisonCase> PredCases;
1034  BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
1035 
1036  // Based on whether the default edge from PTI goes to BB or not, fill in
1037  // PredCases and PredDefault with the new switch cases we would like to
1038  // build.
1039  SmallVector<BasicBlock *, 8> NewSuccessors;
1040 
1041  // Update the branch weight metadata along the way
1042  SmallVector<uint64_t, 8> Weights;
1043  bool PredHasWeights = HasBranchWeights(PTI);
1044  bool SuccHasWeights = HasBranchWeights(TI);
1045 
1046  if (PredHasWeights) {
1047  GetBranchWeights(PTI, Weights);
1048  // branch-weight metadata is inconsistent here.
1049  if (Weights.size() != 1 + PredCases.size())
1050  PredHasWeights = SuccHasWeights = false;
1051  } else if (SuccHasWeights)
1052  // If there are no predecessor weights but there are successor weights,
1053  // populate Weights with 1, which will later be scaled to the sum of
1054  // successor's weights
1055  Weights.assign(1 + PredCases.size(), 1);
1056 
1057  SmallVector<uint64_t, 8> SuccWeights;
1058  if (SuccHasWeights) {
1059  GetBranchWeights(TI, SuccWeights);
1060  // branch-weight metadata is inconsistent here.
1061  if (SuccWeights.size() != 1 + BBCases.size())
1062  PredHasWeights = SuccHasWeights = false;
1063  } else if (PredHasWeights)
1064  SuccWeights.assign(1 + BBCases.size(), 1);
1065 
1066  if (PredDefault == BB) {
1067  // If this is the default destination from PTI, only the edges in TI
1068  // that don't occur in PTI, or that branch to BB will be activated.
1069  std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1070  for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
1071  if (PredCases[i].Dest != BB)
1072  PTIHandled.insert(PredCases[i].Value);
1073  else {
1074  // The default destination is BB, we don't need explicit targets.
1075  std::swap(PredCases[i], PredCases.back());
1076 
1077  if (PredHasWeights || SuccHasWeights) {
1078  // Increase weight for the default case.
1079  Weights[0] += Weights[i + 1];
1080  std::swap(Weights[i + 1], Weights.back());
1081  Weights.pop_back();
1082  }
1083 
1084  PredCases.pop_back();
1085  --i;
1086  --e;
1087  }
1088 
1089  // Reconstruct the new switch statement we will be building.
1090  if (PredDefault != BBDefault) {
1091  PredDefault->removePredecessor(Pred);
1092  PredDefault = BBDefault;
1093  NewSuccessors.push_back(BBDefault);
1094  }
1095 
1096  unsigned CasesFromPred = Weights.size();
1097  uint64_t ValidTotalSuccWeight = 0;
1098  for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
1099  if (!PTIHandled.count(BBCases[i].Value) &&
1100  BBCases[i].Dest != BBDefault) {
1101  PredCases.push_back(BBCases[i]);
1102  NewSuccessors.push_back(BBCases[i].Dest);
1103  if (SuccHasWeights || PredHasWeights) {
1104  // The default weight is at index 0, so weight for the ith case
1105  // should be at index i+1. Scale the cases from successor by
1106  // PredDefaultWeight (Weights[0]).
1107  Weights.push_back(Weights[0] * SuccWeights[i + 1]);
1108  ValidTotalSuccWeight += SuccWeights[i + 1];
1109  }
1110  }
1111 
1112  if (SuccHasWeights || PredHasWeights) {
1113  ValidTotalSuccWeight += SuccWeights[0];
1114  // Scale the cases from predecessor by ValidTotalSuccWeight.
1115  for (unsigned i = 1; i < CasesFromPred; ++i)
1116  Weights[i] *= ValidTotalSuccWeight;
1117  // Scale the default weight by SuccDefaultWeight (SuccWeights[0]).
1118  Weights[0] *= SuccWeights[0];
1119  }
1120  } else {
1121  // If this is not the default destination from PSI, only the edges
1122  // in SI that occur in PSI with a destination of BB will be
1123  // activated.
1124  std::set<ConstantInt *, ConstantIntOrdering> PTIHandled;
1125  std::map<ConstantInt *, uint64_t> WeightsForHandled;
1126  for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
1127  if (PredCases[i].Dest == BB) {
1128  PTIHandled.insert(PredCases[i].Value);
1129 
1130  if (PredHasWeights || SuccHasWeights) {
1131  WeightsForHandled[PredCases[i].Value] = Weights[i + 1];
1132  std::swap(Weights[i + 1], Weights.back());
1133  Weights.pop_back();
1134  }
1135 
1136  std::swap(PredCases[i], PredCases.back());
1137  PredCases.pop_back();
1138  --i;
1139  --e;
1140  }
1141 
1142  // Okay, now we know which constants were sent to BB from the
1143  // predecessor. Figure out where they will all go now.
1144  for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
1145  if (PTIHandled.count(BBCases[i].Value)) {
1146  // If this is one we are capable of getting...
1147  if (PredHasWeights || SuccHasWeights)
1148  Weights.push_back(WeightsForHandled[BBCases[i].Value]);
1149  PredCases.push_back(BBCases[i]);
1150  NewSuccessors.push_back(BBCases[i].Dest);
1151  PTIHandled.erase(
1152  BBCases[i].Value); // This constant is taken care of
1153  }
1154 
1155  // If there are any constants vectored to BB that TI doesn't handle,
1156  // they must go to the default destination of TI.
1157  for (ConstantInt *I : PTIHandled) {
1158  if (PredHasWeights || SuccHasWeights)
1159  Weights.push_back(WeightsForHandled[I]);
1160  PredCases.push_back(ValueEqualityComparisonCase(I, BBDefault));
1161  NewSuccessors.push_back(BBDefault);
1162  }
1163  }
1164 
1165  // Okay, at this point, we know which new successor Pred will get. Make
1166  // sure we update the number of entries in the PHI nodes for these
1167  // successors.
1168  for (BasicBlock *NewSuccessor : NewSuccessors)
1169  AddPredecessorToBlock(NewSuccessor, Pred, BB);
1170 
1171  Builder.SetInsertPoint(PTI);
1172  // Convert pointer to int before we switch.
1173  if (CV->getType()->isPointerTy()) {
1174  CV = Builder.CreatePtrToInt(CV, DL.getIntPtrType(CV->getType()),
1175  "magicptr");
1176  }
1177 
1178  // Now that the successors are updated, create the new Switch instruction.
1179  SwitchInst *NewSI =
1180  Builder.CreateSwitch(CV, PredDefault, PredCases.size());
1181  NewSI->setDebugLoc(PTI->getDebugLoc());
1182  for (ValueEqualityComparisonCase &V : PredCases)
1183  NewSI->addCase(V.Value, V.Dest);
1184 
1185  if (PredHasWeights || SuccHasWeights) {
1186  // Halve the weights if any of them cannot fit in an uint32_t
1187  FitWeights(Weights);
1188 
1189  SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
1190 
1191  setBranchWeights(NewSI, MDWeights);
1192  }
1193 
1195 
1196  // Okay, last check. If BB is still a successor of PSI, then we must
1197  // have an infinite loop case. If so, add an infinitely looping block
1198  // to handle the case to preserve the behavior of the code.
1199  BasicBlock *InfLoopBlock = nullptr;
1200  for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i)
1201  if (NewSI->getSuccessor(i) == BB) {
1202  if (!InfLoopBlock) {
1203  // Insert it at the end of the function, because it's either code,
1204  // or it won't matter if it's hot. :)
1205  InfLoopBlock = BasicBlock::Create(BB->getContext(), "infloop",
1206  BB->getParent());
1207  BranchInst::Create(InfLoopBlock, InfLoopBlock);
1208  }
1209  NewSI->setSuccessor(i, InfLoopBlock);
1210  }
1211 
1212  Changed = true;
1213  }
1214  }
1215  return Changed;
1216 }
1217 
1218 // If we would need to insert a select that uses the value of this invoke
1219 // (comments in HoistThenElseCodeToIf explain why we would need to do this), we
1220 // can't hoist the invoke, as there is nowhere to put the select in this case.
1222  Instruction *I1, Instruction *I2) {
1223  for (BasicBlock *Succ : successors(BB1)) {
1224  for (const PHINode &PN : Succ->phis()) {
1225  Value *BB1V = PN.getIncomingValueForBlock(BB1);
1226  Value *BB2V = PN.getIncomingValueForBlock(BB2);
1227  if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
1228  return false;
1229  }
1230  }
1231  }
1232  return true;
1233 }
1234 
1236 
1237 /// Given a conditional branch that goes to BB1 and BB2, hoist any common code
1238 /// in the two blocks up into the branch block. The caller of this function
1239 /// guarantees that BI's block dominates BB1 and BB2.
1241  const TargetTransformInfo &TTI) {
1242  // This does very trivial matching, with limited scanning, to find identical
1243  // instructions in the two blocks. In particular, we don't want to get into
1244  // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As
1245  // such, we currently just scan for obviously identical instructions in an
1246  // identical order.
1247  BasicBlock *BB1 = BI->getSuccessor(0); // The true destination.
1248  BasicBlock *BB2 = BI->getSuccessor(1); // The false destination
1249 
1250  BasicBlock::iterator BB1_Itr = BB1->begin();
1251  BasicBlock::iterator BB2_Itr = BB2->begin();
1252 
1253  Instruction *I1 = &*BB1_Itr++, *I2 = &*BB2_Itr++;
1254  // Skip debug info if it is not identical.
1257  if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
1258  while (isa<DbgInfoIntrinsic>(I1))
1259  I1 = &*BB1_Itr++;
1260  while (isa<DbgInfoIntrinsic>(I2))
1261  I2 = &*BB2_Itr++;
1262  }
1263  if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) ||
1264  (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)))
1265  return false;
1266 
1267  BasicBlock *BIParent = BI->getParent();
1268 
1269  bool Changed = false;
1270  do {
1271  // If we are hoisting the terminator instruction, don't move one (making a
1272  // broken BB), instead clone it, and remove BI.
1273  if (isa<TerminatorInst>(I1))
1274  goto HoistTerminator;
1275 
1276  // If we're going to hoist a call, make sure that the two instructions we're
1277  // commoning/hoisting are both marked with musttail, or neither of them is
1278  // marked as such. Otherwise, we might end up in a situation where we hoist
1279  // from a block where the terminator is a `ret` to a block where the terminator
1280  // is a `br`, and `musttail` calls expect to be followed by a return.
1281  auto *C1 = dyn_cast<CallInst>(I1);
1282  auto *C2 = dyn_cast<CallInst>(I2);
1283  if (C1 && C2)
1284  if (C1->isMustTailCall() != C2->isMustTailCall())
1285  return Changed;
1286 
1287  if (!TTI.isProfitableToHoist(I1) || !TTI.isProfitableToHoist(I2))
1288  return Changed;
1289 
1290  if (isa<DbgInfoIntrinsic>(I1) || isa<DbgInfoIntrinsic>(I2)) {
1291  assert (isa<DbgInfoIntrinsic>(I1) && isa<DbgInfoIntrinsic>(I2));
1292  // The debug location is an integral part of a debug info intrinsic
1293  // and can't be separated from it or replaced. Instead of attempting
1294  // to merge locations, simply hoist both copies of the intrinsic.
1295  BIParent->getInstList().splice(BI->getIterator(),
1296  BB1->getInstList(), I1);
1297  BIParent->getInstList().splice(BI->getIterator(),
1298  BB2->getInstList(), I2);
1299  Changed = true;
1300  } else {
1301  // For a normal instruction, we just move one to right before the branch,
1302  // then replace all uses of the other with the first. Finally, we remove
1303  // the now redundant second instruction.
1304  BIParent->getInstList().splice(BI->getIterator(),
1305  BB1->getInstList(), I1);
1306  if (!I2->use_empty())
1307  I2->replaceAllUsesWith(I1);
1308  I1->andIRFlags(I2);
1309  unsigned KnownIDs[] = {LLVMContext::MD_tbaa,
1319  combineMetadata(I1, I2, KnownIDs);
1320 
1321  // I1 and I2 are being combined into a single instruction. Its debug
1322  // location is the merged locations of the original instructions.
1323  I1->applyMergedLocation(I1->getDebugLoc(), I2->getDebugLoc());
1324 
1325  I2->eraseFromParent();
1326  Changed = true;
1327  }
1328 
1329  I1 = &*BB1_Itr++;
1330  I2 = &*BB2_Itr++;
1331  // Skip debug info if it is not identical.
1334  if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
1335  while (isa<DbgInfoIntrinsic>(I1))
1336  I1 = &*BB1_Itr++;
1337  while (isa<DbgInfoIntrinsic>(I2))
1338  I2 = &*BB2_Itr++;
1339  }
1340  } while (I1->isIdenticalToWhenDefined(I2));
1341 
1342  return true;
1343 
1344 HoistTerminator:
1345  // It may not be possible to hoist an invoke.
1346  if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))
1347  return Changed;
1348 
1349  for (BasicBlock *Succ : successors(BB1)) {
1350  for (PHINode &PN : Succ->phis()) {
1351  Value *BB1V = PN.getIncomingValueForBlock(BB1);
1352  Value *BB2V = PN.getIncomingValueForBlock(BB2);
1353  if (BB1V == BB2V)
1354  continue;
1355 
1356  // Check for passingValueIsAlwaysUndefined here because we would rather
1357  // eliminate undefined control flow then converting it to a select.
1358  if (passingValueIsAlwaysUndefined(BB1V, &PN) ||
1359  passingValueIsAlwaysUndefined(BB2V, &PN))
1360  return Changed;
1361 
1362  if (isa<ConstantExpr>(BB1V) && !isSafeToSpeculativelyExecute(BB1V))
1363  return Changed;
1364  if (isa<ConstantExpr>(BB2V) && !isSafeToSpeculativelyExecute(BB2V))
1365  return Changed;
1366  }
1367  }
1368 
1369  // Okay, it is safe to hoist the terminator.
1370  Instruction *NT = I1->clone();
1371  BIParent->getInstList().insert(BI->getIterator(), NT);
1372  if (!NT->getType()->isVoidTy()) {
1373  I1->replaceAllUsesWith(NT);
1374  I2->replaceAllUsesWith(NT);
1375  NT->takeName(I1);
1376  }
1377 
1378  IRBuilder<NoFolder> Builder(NT);
1379  // Hoisting one of the terminators from our successor is a great thing.
1380  // Unfortunately, the successors of the if/else blocks may have PHI nodes in
1381  // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI
1382  // nodes, so we insert select instruction to compute the final result.
1383  std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
1384  for (BasicBlock *Succ : successors(BB1)) {
1385  for (PHINode &PN : Succ->phis()) {
1386  Value *BB1V = PN.getIncomingValueForBlock(BB1);
1387  Value *BB2V = PN.getIncomingValueForBlock(BB2);
1388  if (BB1V == BB2V)
1389  continue;
1390 
1391  // These values do not agree. Insert a select instruction before NT
1392  // that determines the right value.
1393  SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1394  if (!SI)
1395  SI = cast<SelectInst>(
1396  Builder.CreateSelect(BI->getCondition(), BB1V, BB2V,
1397  BB1V->getName() + "." + BB2V->getName(), BI));
1398 
1399  // Make the PHI node use the select for all incoming values for BB1/BB2
1400  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1401  if (PN.getIncomingBlock(i) == BB1 || PN.getIncomingBlock(i) == BB2)
1402  PN.setIncomingValue(i, SI);
1403  }
1404  }
1405 
1406  // Update any PHI nodes in our new successors.
1407  for (BasicBlock *Succ : successors(BB1))
1408  AddPredecessorToBlock(Succ, BIParent, BB1);
1409 
1411  return true;
1412 }
1413 
1414 // All instructions in Insts belong to different blocks that all unconditionally
1415 // branch to a common successor. Analyze each instruction and return true if it
1416 // would be possible to sink them into their successor, creating one common
1417 // instruction instead. For every value that would be required to be provided by
1418 // PHI node (because an operand varies in each input block), add to PHIOperands.
1421  DenseMap<Instruction *, SmallVector<Value *, 4>> &PHIOperands) {
1422  // Prune out obviously bad instructions to move. Any non-store instruction
1423  // must have exactly one use, and we check later that use is by a single,
1424  // common PHI instruction in the successor.
1425  for (auto *I : Insts) {
1426  // These instructions may change or break semantics if moved.
1427  if (isa<PHINode>(I) || I->isEHPad() || isa<AllocaInst>(I) ||
1428  I->getType()->isTokenTy())
1429  return false;
1430 
1431  // Conservatively return false if I is an inline-asm instruction. Sinking
1432  // and merging inline-asm instructions can potentially create arguments
1433  // that cannot satisfy the inline-asm constraints.
1434  if (const auto *C = dyn_cast<CallInst>(I))
1435  if (C->isInlineAsm())
1436  return false;
1437 
1438  // Everything must have only one use too, apart from stores which
1439  // have no uses.
1440  if (!isa<StoreInst>(I) && !I->hasOneUse())
1441  return false;
1442  }
1443 
1444  const Instruction *I0 = Insts.front();
1445  for (auto *I : Insts)
1446  if (!I->isSameOperationAs(I0))
1447  return false;
1448 
1449  // All instructions in Insts are known to be the same opcode. If they aren't
1450  // stores, check the only user of each is a PHI or in the same block as the
1451  // instruction, because if a user is in the same block as an instruction
1452  // we're contemplating sinking, it must already be determined to be sinkable.
1453  if (!isa<StoreInst>(I0)) {
1454  auto *PNUse = dyn_cast<PHINode>(*I0->user_begin());
1455  auto *Succ = I0->getParent()->getTerminator()->getSuccessor(0);
1456  if (!all_of(Insts, [&PNUse,&Succ](const Instruction *I) -> bool {
1457  auto *U = cast<Instruction>(*I->user_begin());
1458  return (PNUse &&
1459  PNUse->getParent() == Succ &&
1460  PNUse->getIncomingValueForBlock(I->getParent()) == I) ||
1461  U->getParent() == I->getParent();
1462  }))
1463  return false;
1464  }
1465 
1466  // Because SROA can't handle speculating stores of selects, try not
1467  // to sink loads or stores of allocas when we'd have to create a PHI for
1468  // the address operand. Also, because it is likely that loads or stores
1469  // of allocas will disappear when Mem2Reg/SROA is run, don't sink them.
1470  // This can cause code churn which can have unintended consequences down
1471  // the line - see https://llvm.org/bugs/show_bug.cgi?id=30244.
1472  // FIXME: This is a workaround for a deficiency in SROA - see
1473  // https://llvm.org/bugs/show_bug.cgi?id=30188
1474  if (isa<StoreInst>(I0) && any_of(Insts, [](const Instruction *I) {
1475  return isa<AllocaInst>(I->getOperand(1));
1476  }))
1477  return false;
1478  if (isa<LoadInst>(I0) && any_of(Insts, [](const Instruction *I) {
1479  return isa<AllocaInst>(I->getOperand(0));
1480  }))
1481  return false;
1482 
1483  for (unsigned OI = 0, OE = I0->getNumOperands(); OI != OE; ++OI) {
1484  if (I0->getOperand(OI)->getType()->isTokenTy())
1485  // Don't touch any operand of token type.
1486  return false;
1487 
1488  auto SameAsI0 = [&I0, OI](const Instruction *I) {
1489  assert(I->getNumOperands() == I0->getNumOperands());
1490  return I->getOperand(OI) == I0->getOperand(OI);
1491  };
1492  if (!all_of(Insts, SameAsI0)) {
1493  if (!canReplaceOperandWithVariable(I0, OI))
1494  // We can't create a PHI from this GEP.
1495  return false;
1496  // Don't create indirect calls! The called value is the final operand.
1497  if ((isa<CallInst>(I0) || isa<InvokeInst>(I0)) && OI == OE - 1) {
1498  // FIXME: if the call was *already* indirect, we should do this.
1499  return false;
1500  }
1501  for (auto *I : Insts)
1502  PHIOperands[I].push_back(I->getOperand(OI));
1503  }
1504  }
1505  return true;
1506 }
1507 
1508 // Assuming canSinkLastInstruction(Blocks) has returned true, sink the last
1509 // instruction of every block in Blocks to their common successor, commoning
1510 // into one instruction.
1512  auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
1513 
1514  // canSinkLastInstruction returning true guarantees that every block has at
1515  // least one non-terminator instruction.
1517  for (auto *BB : Blocks) {
1518  Instruction *I = BB->getTerminator();
1519  do {
1520  I = I->getPrevNode();
1521  } while (isa<DbgInfoIntrinsic>(I) && I != &BB->front());
1522  if (!isa<DbgInfoIntrinsic>(I))
1523  Insts.push_back(I);
1524  }
1525 
1526  // The only checking we need to do now is that all users of all instructions
1527  // are the same PHI node. canSinkLastInstruction should have checked this but
1528  // it is slightly over-aggressive - it gets confused by commutative instructions
1529  // so double-check it here.
1530  Instruction *I0 = Insts.front();
1531  if (!isa<StoreInst>(I0)) {
1532  auto *PNUse = dyn_cast<PHINode>(*I0->user_begin());
1533  if (!all_of(Insts, [&PNUse](const Instruction *I) -> bool {
1534  auto *U = cast<Instruction>(*I->user_begin());
1535  return U == PNUse;
1536  }))
1537  return false;
1538  }
1539 
1540  // We don't need to do any more checking here; canSinkLastInstruction should
1541  // have done it all for us.
1542  SmallVector<Value*, 4> NewOperands;
1543  for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O) {
1544  // This check is different to that in canSinkLastInstruction. There, we
1545  // cared about the global view once simplifycfg (and instcombine) have
1546  // completed - it takes into account PHIs that become trivially
1547  // simplifiable. However here we need a more local view; if an operand
1548  // differs we create a PHI and rely on instcombine to clean up the very
1549  // small mess we may make.
1550  bool NeedPHI = any_of(Insts, [&I0, O](const Instruction *I) {
1551  return I->getOperand(O) != I0->getOperand(O);
1552  });
1553  if (!NeedPHI) {
1554  NewOperands.push_back(I0->getOperand(O));
1555  continue;
1556  }
1557 
1558  // Create a new PHI in the successor block and populate it.
1559  auto *Op = I0->getOperand(O);
1560  assert(!Op->getType()->isTokenTy() && "Can't PHI tokens!");
1561  auto *PN = PHINode::Create(Op->getType(), Insts.size(),
1562  Op->getName() + ".sink", &BBEnd->front());
1563  for (auto *I : Insts)
1564  PN->addIncoming(I->getOperand(O), I->getParent());
1565  NewOperands.push_back(PN);
1566  }
1567 
1568  // Arbitrarily use I0 as the new "common" instruction; remap its operands
1569  // and move it to the start of the successor block.
1570  for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O)
1571  I0->getOperandUse(O).set(NewOperands[O]);
1572  I0->moveBefore(&*BBEnd->getFirstInsertionPt());
1573 
1574  // Update metadata and IR flags, and merge debug locations.
1575  for (auto *I : Insts)
1576  if (I != I0) {
1577  // The debug location for the "common" instruction is the merged locations
1578  // of all the commoned instructions. We start with the original location
1579  // of the "common" instruction and iteratively merge each location in the
1580  // loop below.
1581  // This is an N-way merge, which will be inefficient if I0 is a CallInst.
1582  // However, as N-way merge for CallInst is rare, so we use simplified API
1583  // instead of using complex API for N-way merge.
1584  I0->applyMergedLocation(I0->getDebugLoc(), I->getDebugLoc());
1585  combineMetadataForCSE(I0, I);
1586  I0->andIRFlags(I);
1587  }
1588 
1589  if (!isa<StoreInst>(I0)) {
1590  // canSinkLastInstruction checked that all instructions were used by
1591  // one and only one PHI node. Find that now, RAUW it to our common
1592  // instruction and nuke it.
1593  assert(I0->hasOneUse());
1594  auto *PN = cast<PHINode>(*I0->user_begin());
1595  PN->replaceAllUsesWith(I0);
1596  PN->eraseFromParent();
1597  }
1598 
1599  // Finally nuke all instructions apart from the common instruction.
1600  for (auto *I : Insts)
1601  if (I != I0)
1602  I->eraseFromParent();
1603 
1604  return true;
1605 }
1606 
1607 namespace {
1608 
1609  // LockstepReverseIterator - Iterates through instructions
1610  // in a set of blocks in reverse order from the first non-terminator.
1611  // For example (assume all blocks have size n):
1612  // LockstepReverseIterator I([B1, B2, B3]);
1613  // *I-- = [B1[n], B2[n], B3[n]];
1614  // *I-- = [B1[n-1], B2[n-1], B3[n-1]];
1615  // *I-- = [B1[n-2], B2[n-2], B3[n-2]];
1616  // ...
1617  class LockstepReverseIterator {
1618  ArrayRef<BasicBlock*> Blocks;
1620  bool Fail;
1621 
1622  public:
1623  LockstepReverseIterator(ArrayRef<BasicBlock*> Blocks) : Blocks(Blocks) {
1624  reset();
1625  }
1626 
1627  void reset() {
1628  Fail = false;
1629  Insts.clear();
1630  for (auto *BB : Blocks) {
1631  Instruction *Inst = BB->getTerminator();
1632  for (Inst = Inst->getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
1633  Inst = Inst->getPrevNode();
1634  if (!Inst) {
1635  // Block wasn't big enough.
1636  Fail = true;
1637  return;
1638  }
1639  Insts.push_back(Inst);
1640  }
1641  }
1642 
1643  bool isValid() const {
1644  return !Fail;
1645  }
1646 
1647  void operator--() {
1648  if (Fail)
1649  return;
1650  for (auto *&Inst : Insts) {
1651  for (Inst = Inst->getPrevNode(); Inst && isa<DbgInfoIntrinsic>(Inst);)
1652  Inst = Inst->getPrevNode();
1653  // Already at beginning of block.
1654  if (!Inst) {
1655  Fail = true;
1656  return;
1657  }
1658  }
1659  }
1660 
1662  return Insts;
1663  }
1664  };
1665 
1666 } // end anonymous namespace
1667 
1668 /// Check whether BB's predecessors end with unconditional branches. If it is
1669 /// true, sink any common code from the predecessors to BB.
1670 /// We also allow one predecessor to end with conditional branch (but no more
1671 /// than one).
1673  // We support two situations:
1674  // (1) all incoming arcs are unconditional
1675  // (2) one incoming arc is conditional
1676  //
1677  // (2) is very common in switch defaults and
1678  // else-if patterns;
1679  //
1680  // if (a) f(1);
1681  // else if (b) f(2);
1682  //
1683  // produces:
1684  //
1685  // [if]
1686  // / \
1687  // [f(1)] [if]
1688  // | | \
1689  // | | |
1690  // | [f(2)]|
1691  // \ | /
1692  // [ end ]
1693  //
1694  // [end] has two unconditional predecessor arcs and one conditional. The
1695  // conditional refers to the implicit empty 'else' arc. This conditional
1696  // arc can also be caused by an empty default block in a switch.
1697  //
1698  // In this case, we attempt to sink code from all *unconditional* arcs.
1699  // If we can sink instructions from these arcs (determined during the scan
1700  // phase below) we insert a common successor for all unconditional arcs and
1701  // connect that to [end], to enable sinking:
1702  //
1703  // [if]
1704  // / \
1705  // [x(1)] [if]
1706  // | | \
1707  // | | \
1708  // | [x(2)] |
1709  // \ / |
1710  // [sink.split] |
1711  // \ /
1712  // [ end ]
1713  //
1714  SmallVector<BasicBlock*,4> UnconditionalPreds;
1715  Instruction *Cond = nullptr;
1716  for (auto *B : predecessors(BB)) {
1717  auto *T = B->getTerminator();
1718  if (isa<BranchInst>(T) && cast<BranchInst>(T)->isUnconditional())
1719  UnconditionalPreds.push_back(B);
1720  else if ((isa<BranchInst>(T) || isa<SwitchInst>(T)) && !Cond)
1721  Cond = T;
1722  else
1723  return false;
1724  }
1725  if (UnconditionalPreds.size() < 2)
1726  return false;
1727 
1728  bool Changed = false;
1729  // We take a two-step approach to tail sinking. First we scan from the end of
1730  // each block upwards in lockstep. If the n'th instruction from the end of each
1731  // block can be sunk, those instructions are added to ValuesToSink and we
1732  // carry on. If we can sink an instruction but need to PHI-merge some operands
1733  // (because they're not identical in each instruction) we add these to
1734  // PHIOperands.
1735  unsigned ScanIdx = 0;
1736  SmallPtrSet<Value*,4> InstructionsToSink;
1738  LockstepReverseIterator LRI(UnconditionalPreds);
1739  while (LRI.isValid() &&
1740  canSinkInstructions(*LRI, PHIOperands)) {
1741  LLVM_DEBUG(dbgs() << "SINK: instruction can be sunk: " << *(*LRI)[0]
1742  << "\n");
1743  InstructionsToSink.insert((*LRI).begin(), (*LRI).end());
1744  ++ScanIdx;
1745  --LRI;
1746  }
1747 
1748  auto ProfitableToSinkInstruction = [&](LockstepReverseIterator &LRI) {
1749  unsigned NumPHIdValues = 0;
1750  for (auto *I : *LRI)
1751  for (auto *V : PHIOperands[I])
1752  if (InstructionsToSink.count(V) == 0)
1753  ++NumPHIdValues;
1754  LLVM_DEBUG(dbgs() << "SINK: #phid values: " << NumPHIdValues << "\n");
1755  unsigned NumPHIInsts = NumPHIdValues / UnconditionalPreds.size();
1756  if ((NumPHIdValues % UnconditionalPreds.size()) != 0)
1757  NumPHIInsts++;
1758 
1759  return NumPHIInsts <= 1;
1760  };
1761 
1762  if (ScanIdx > 0 && Cond) {
1763  // Check if we would actually sink anything first! This mutates the CFG and
1764  // adds an extra block. The goal in doing this is to allow instructions that
1765  // couldn't be sunk before to be sunk - obviously, speculatable instructions
1766  // (such as trunc, add) can be sunk and predicated already. So we check that
1767  // we're going to sink at least one non-speculatable instruction.
1768  LRI.reset();
1769  unsigned Idx = 0;
1770  bool Profitable = false;
1771  while (ProfitableToSinkInstruction(LRI) && Idx < ScanIdx) {
1772  if (!isSafeToSpeculativelyExecute((*LRI)[0])) {
1773  Profitable = true;
1774  break;
1775  }
1776  --LRI;
1777  ++Idx;
1778  }
1779  if (!Profitable)
1780  return false;
1781 
1782  LLVM_DEBUG(dbgs() << "SINK: Splitting edge\n");
1783  // We have a conditional edge and we're going to sink some instructions.
1784  // Insert a new block postdominating all blocks we're going to sink from.
1785  if (!SplitBlockPredecessors(BB, UnconditionalPreds, ".sink.split"))
1786  // Edges couldn't be split.
1787  return false;
1788  Changed = true;
1789  }
1790 
1791  // Now that we've analyzed all potential sinking candidates, perform the
1792  // actual sink. We iteratively sink the last non-terminator of the source
1793  // blocks into their common successor unless doing so would require too
1794  // many PHI instructions to be generated (currently only one PHI is allowed
1795  // per sunk instruction).
1796  //
1797  // We can use InstructionsToSink to discount values needing PHI-merging that will
1798  // actually be sunk in a later iteration. This allows us to be more
1799  // aggressive in what we sink. This does allow a false positive where we
1800  // sink presuming a later value will also be sunk, but stop half way through
1801  // and never actually sink it which means we produce more PHIs than intended.
1802  // This is unlikely in practice though.
1803  for (unsigned SinkIdx = 0; SinkIdx != ScanIdx; ++SinkIdx) {
1804  LLVM_DEBUG(dbgs() << "SINK: Sink: "
1805  << *UnconditionalPreds[0]->getTerminator()->getPrevNode()
1806  << "\n");
1807 
1808  // Because we've sunk every instruction in turn, the current instruction to
1809  // sink is always at index 0.
1810  LRI.reset();
1811  if (!ProfitableToSinkInstruction(LRI)) {
1812  // Too many PHIs would be created.
1813  LLVM_DEBUG(
1814  dbgs() << "SINK: stopping here, too many PHIs would be created!\n");
1815  break;
1816  }
1817 
1818  if (!sinkLastInstruction(UnconditionalPreds))
1819  return Changed;
1820  NumSinkCommons++;
1821  Changed = true;
1822  }
1823  return Changed;
1824 }
1825 
1826 /// Determine if we can hoist sink a sole store instruction out of a
1827 /// conditional block.
1828 ///
1829 /// We are looking for code like the following:
1830 /// BrBB:
1831 /// store i32 %add, i32* %arrayidx2
1832 /// ... // No other stores or function calls (we could be calling a memory
1833 /// ... // function).
1834 /// %cmp = icmp ult %x, %y
1835 /// br i1 %cmp, label %EndBB, label %ThenBB
1836 /// ThenBB:
1837 /// store i32 %add5, i32* %arrayidx2
1838 /// br label EndBB
1839 /// EndBB:
1840 /// ...
1841 /// We are going to transform this into:
1842 /// BrBB:
1843 /// store i32 %add, i32* %arrayidx2
1844 /// ... //
1845 /// %cmp = icmp ult %x, %y
1846 /// %add.add5 = select i1 %cmp, i32 %add, %add5
1847 /// store i32 %add.add5, i32* %arrayidx2
1848 /// ...
1849 ///
1850 /// \return The pointer to the value of the previous store if the store can be
1851 /// hoisted into the predecessor block. 0 otherwise.
1853  BasicBlock *StoreBB, BasicBlock *EndBB) {
1854  StoreInst *StoreToHoist = dyn_cast<StoreInst>(I);
1855  if (!StoreToHoist)
1856  return nullptr;
1857 
1858  // Volatile or atomic.
1859  if (!StoreToHoist->isSimple())
1860  return nullptr;
1861 
1862  Value *StorePtr = StoreToHoist->getPointerOperand();
1863 
1864  // Look for a store to the same pointer in BrBB.
1865  unsigned MaxNumInstToLookAt = 9;
1866  for (Instruction &CurI : reverse(BrBB->instructionsWithoutDebug())) {
1867  if (!MaxNumInstToLookAt)
1868  break;
1869  --MaxNumInstToLookAt;
1870 
1871  // Could be calling an instruction that affects memory like free().
1872  if (CurI.mayHaveSideEffects() && !isa<StoreInst>(CurI))
1873  return nullptr;
1874 
1875  if (auto *SI = dyn_cast<StoreInst>(&CurI)) {
1876  // Found the previous store make sure it stores to the same location.
1877  if (SI->getPointerOperand() == StorePtr)
1878  // Found the previous store, return its value operand.
1879  return SI->getValueOperand();
1880  return nullptr; // Unknown store.
1881  }
1882  }
1883 
1884  return nullptr;
1885 }
1886 
1887 /// Speculate a conditional basic block flattening the CFG.
1888 ///
1889 /// Note that this is a very risky transform currently. Speculating
1890 /// instructions like this is most often not desirable. Instead, there is an MI
1891 /// pass which can do it with full awareness of the resource constraints.
1892 /// However, some cases are "obvious" and we should do directly. An example of
1893 /// this is speculating a single, reasonably cheap instruction.
1894 ///
1895 /// There is only one distinct advantage to flattening the CFG at the IR level:
1896 /// it makes very common but simplistic optimizations such as are common in
1897 /// instcombine and the DAG combiner more powerful by removing CFG edges and
1898 /// modeling their effects with easier to reason about SSA value graphs.
1899 ///
1900 ///
1901 /// An illustration of this transform is turning this IR:
1902 /// \code
1903 /// BB:
1904 /// %cmp = icmp ult %x, %y
1905 /// br i1 %cmp, label %EndBB, label %ThenBB
1906 /// ThenBB:
1907 /// %sub = sub %x, %y
1908 /// br label BB2
1909 /// EndBB:
1910 /// %phi = phi [ %sub, %ThenBB ], [ 0, %EndBB ]
1911 /// ...
1912 /// \endcode
1913 ///
1914 /// Into this IR:
1915 /// \code
1916 /// BB:
1917 /// %cmp = icmp ult %x, %y
1918 /// %sub = sub %x, %y
1919 /// %cond = select i1 %cmp, 0, %sub
1920 /// ...
1921 /// \endcode
1922 ///
1923 /// \returns true if the conditional block is removed.
1925  const TargetTransformInfo &TTI) {
1926  // Be conservative for now. FP select instruction can often be expensive.
1927  Value *BrCond = BI->getCondition();
1928  if (isa<FCmpInst>(BrCond))
1929  return false;
1930 
1931  BasicBlock *BB = BI->getParent();
1932  BasicBlock *EndBB = ThenBB->getTerminator()->getSuccessor(0);
1933 
1934  // If ThenBB is actually on the false edge of the conditional branch, remember
1935  // to swap the select operands later.
1936  bool Invert = false;
1937  if (ThenBB != BI->getSuccessor(0)) {
1938  assert(ThenBB == BI->getSuccessor(1) && "No edge from 'if' block?");
1939  Invert = true;
1940  }
1941  assert(EndBB == BI->getSuccessor(!Invert) && "No edge from to end block");
1942 
1943  // Keep a count of how many times instructions are used within CondBB when
1944  // they are candidates for sinking into CondBB. Specifically:
1945  // - They are defined in BB, and
1946  // - They have no side effects, and
1947  // - All of their uses are in CondBB.
1948  SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
1949 
1950  SmallVector<Instruction *, 4> SpeculatedDbgIntrinsics;
1951 
1952  unsigned SpeculationCost = 0;
1953  Value *SpeculatedStoreValue = nullptr;
1954  StoreInst *SpeculatedStore = nullptr;
1955  for (BasicBlock::iterator BBI = ThenBB->begin(),
1956  BBE = std::prev(ThenBB->end());
1957  BBI != BBE; ++BBI) {
1958  Instruction *I = &*BBI;
1959  // Skip debug info.
1960  if (isa<DbgInfoIntrinsic>(I)) {
1961  SpeculatedDbgIntrinsics.push_back(I);
1962  continue;
1963  }
1964 
1965  // Only speculatively execute a single instruction (not counting the
1966  // terminator) for now.
1967  ++SpeculationCost;
1968  if (SpeculationCost > 1)
1969  return false;
1970 
1971  // Don't hoist the instruction if it's unsafe or expensive.
1972  if (!isSafeToSpeculativelyExecute(I) &&
1973  !(HoistCondStores && (SpeculatedStoreValue = isSafeToSpeculateStore(
1974  I, BB, ThenBB, EndBB))))
1975  return false;
1976  if (!SpeculatedStoreValue &&
1977  ComputeSpeculationCost(I, TTI) >
1979  return false;
1980 
1981  // Store the store speculation candidate.
1982  if (SpeculatedStoreValue)
1983  SpeculatedStore = cast<StoreInst>(I);
1984 
1985  // Do not hoist the instruction if any of its operands are defined but not
1986  // used in BB. The transformation will prevent the operand from
1987  // being sunk into the use block.
1988  for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) {
1989  Instruction *OpI = dyn_cast<Instruction>(*i);
1990  if (!OpI || OpI->getParent() != BB || OpI->mayHaveSideEffects())
1991  continue; // Not a candidate for sinking.
1992 
1993  ++SinkCandidateUseCounts[OpI];
1994  }
1995  }
1996 
1997  // Consider any sink candidates which are only used in CondBB as costs for
1998  // speculation. Note, while we iterate over a DenseMap here, we are summing
1999  // and so iteration order isn't significant.
2001  I = SinkCandidateUseCounts.begin(),
2002  E = SinkCandidateUseCounts.end();
2003  I != E; ++I)
2004  if (I->first->getNumUses() == I->second) {
2005  ++SpeculationCost;
2006  if (SpeculationCost > 1)
2007  return false;
2008  }
2009 
2010  // Check that the PHI nodes can be converted to selects.
2011  bool HaveRewritablePHIs = false;
2012  for (PHINode &PN : EndBB->phis()) {
2013  Value *OrigV = PN.getIncomingValueForBlock(BB);
2014  Value *ThenV = PN.getIncomingValueForBlock(ThenBB);
2015 
2016  // FIXME: Try to remove some of the duplication with HoistThenElseCodeToIf.
2017  // Skip PHIs which are trivial.
2018  if (ThenV == OrigV)
2019  continue;
2020 
2021  // Don't convert to selects if we could remove undefined behavior instead.
2022  if (passingValueIsAlwaysUndefined(OrigV, &PN) ||
2023  passingValueIsAlwaysUndefined(ThenV, &PN))
2024  return false;
2025 
2026  HaveRewritablePHIs = true;
2027  ConstantExpr *OrigCE = dyn_cast<ConstantExpr>(OrigV);
2028  ConstantExpr *ThenCE = dyn_cast<ConstantExpr>(ThenV);
2029  if (!OrigCE && !ThenCE)
2030  continue; // Known safe and cheap.
2031 
2032  if ((ThenCE && !isSafeToSpeculativelyExecute(ThenCE)) ||
2033  (OrigCE && !isSafeToSpeculativelyExecute(OrigCE)))
2034  return false;
2035  unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE, TTI) : 0;
2036  unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE, TTI) : 0;
2037  unsigned MaxCost =
2039  if (OrigCost + ThenCost > MaxCost)
2040  return false;
2041 
2042  // Account for the cost of an unfolded ConstantExpr which could end up
2043  // getting expanded into Instructions.
2044  // FIXME: This doesn't account for how many operations are combined in the
2045  // constant expression.
2046  ++SpeculationCost;
2047  if (SpeculationCost > 1)
2048  return false;
2049  }
2050 
2051  // If there are no PHIs to process, bail early. This helps ensure idempotence
2052  // as well.
2053  if (!HaveRewritablePHIs && !(HoistCondStores && SpeculatedStoreValue))
2054  return false;
2055 
2056  // If we get here, we can hoist the instruction and if-convert.
2057  LLVM_DEBUG(dbgs() << "SPECULATIVELY EXECUTING BB" << *ThenBB << "\n";);
2058 
2059  // Insert a select of the value of the speculated store.
2060  if (SpeculatedStoreValue) {
2061  IRBuilder<NoFolder> Builder(BI);
2062  Value *TrueV = SpeculatedStore->getValueOperand();
2063  Value *FalseV = SpeculatedStoreValue;
2064  if (Invert)
2065  std::swap(TrueV, FalseV);
2066  Value *S = Builder.CreateSelect(
2067  BrCond, TrueV, FalseV, "spec.store.select", BI);
2068  SpeculatedStore->setOperand(0, S);
2069  SpeculatedStore->applyMergedLocation(BI->getDebugLoc(),
2070  SpeculatedStore->getDebugLoc());
2071  }
2072 
2073  // Metadata can be dependent on the condition we are hoisting above.
2074  // Conservatively strip all metadata on the instruction.
2075  for (auto &I : *ThenBB)
2077 
2078  // Hoist the instructions.
2079  BB->getInstList().splice(BI->getIterator(), ThenBB->getInstList(),
2080  ThenBB->begin(), std::prev(ThenBB->end()));
2081 
2082  // Insert selects and rewrite the PHI operands.
2083  IRBuilder<NoFolder> Builder(BI);
2084  for (PHINode &PN : EndBB->phis()) {
2085  unsigned OrigI = PN.getBasicBlockIndex(BB);
2086  unsigned ThenI = PN.getBasicBlockIndex(ThenBB);
2087  Value *OrigV = PN.getIncomingValue(OrigI);
2088  Value *ThenV = PN.getIncomingValue(ThenI);
2089 
2090  // Skip PHIs which are trivial.
2091  if (OrigV == ThenV)
2092  continue;
2093 
2094  // Create a select whose true value is the speculatively executed value and
2095  // false value is the preexisting value. Swap them if the branch
2096  // destinations were inverted.
2097  Value *TrueV = ThenV, *FalseV = OrigV;
2098  if (Invert)
2099  std::swap(TrueV, FalseV);
2100  Value *V = Builder.CreateSelect(
2101  BrCond, TrueV, FalseV, "spec.select", BI);
2102  PN.setIncomingValue(OrigI, V);
2103  PN.setIncomingValue(ThenI, V);
2104  }
2105 
2106  // Remove speculated dbg intrinsics.
2107  // FIXME: Is it possible to do this in a more elegant way? Moving/merging the
2108  // dbg value for the different flows and inserting it after the select.
2109  for (Instruction *I : SpeculatedDbgIntrinsics)
2110  I->eraseFromParent();
2111 
2112  ++NumSpeculations;
2113  return true;
2114 }
2115 
2116 /// Return true if we can thread a branch across this block.
2118  unsigned Size = 0;
2119 
2120  for (Instruction &I : BB->instructionsWithoutDebug()) {
2121  if (Size > 10)
2122  return false; // Don't clone large BB's.
2123  ++Size;
2124 
2125  // We can only support instructions that do not define values that are
2126  // live outside of the current basic block.
2127  for (User *U : I.users()) {
2128  Instruction *UI = cast<Instruction>(U);
2129  if (UI->getParent() != BB || isa<PHINode>(UI))
2130  return false;
2131  }
2132 
2133  // Looks ok, continue checking.
2134  }
2135 
2136  return true;
2137 }
2138 
2139 /// If we have a conditional branch on a PHI node value that is defined in the
2140 /// same block as the branch and if any PHI entries are constants, thread edges
2141 /// corresponding to that entry to be branches to their ultimate destination.
2142 static bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout &DL,
2143  AssumptionCache *AC) {
2144  BasicBlock *BB = BI->getParent();
2145  PHINode *PN = dyn_cast<PHINode>(BI->getCondition());
2146  // NOTE: we currently cannot transform this case if the PHI node is used
2147  // outside of the block.
2148  if (!PN || PN->getParent() != BB || !PN->hasOneUse())
2149  return false;
2150 
2151  // Degenerate case of a single entry PHI.
2152  if (PN->getNumIncomingValues() == 1) {
2154  return true;
2155  }
2156 
2157  // Now we know that this block has multiple preds and two succs.
2159  return false;
2160 
2161  // Can't fold blocks that contain noduplicate or convergent calls.
2162  if (any_of(*BB, [](const Instruction &I) {
2163  const CallInst *CI = dyn_cast<CallInst>(&I);
2164  return CI && (CI->cannotDuplicate() || CI->isConvergent());
2165  }))
2166  return false;
2167 
2168  // Okay, this is a simple enough basic block. See if any phi values are
2169  // constants.
2170  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
2172  if (!CB || !CB->getType()->isIntegerTy(1))
2173  continue;
2174 
2175  // Okay, we now know that all edges from PredBB should be revectored to
2176  // branch to RealDest.
2177  BasicBlock *PredBB = PN->getIncomingBlock(i);
2178  BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue());
2179 
2180  if (RealDest == BB)
2181  continue; // Skip self loops.
2182  // Skip if the predecessor's terminator is an indirect branch.
2183  if (isa<IndirectBrInst>(PredBB->getTerminator()))
2184  continue;
2185 
2186  // The dest block might have PHI nodes, other predecessors and other
2187  // difficult cases. Instead of being smart about this, just insert a new
2188  // block that jumps to the destination block, effectively splitting
2189  // the edge we are about to create.
2190  BasicBlock *EdgeBB =
2191  BasicBlock::Create(BB->getContext(), RealDest->getName() + ".critedge",
2192  RealDest->getParent(), RealDest);
2193  BranchInst::Create(RealDest, EdgeBB);
2194 
2195  // Update PHI nodes.
2196  AddPredecessorToBlock(RealDest, EdgeBB, BB);
2197 
2198  // BB may have instructions that are being threaded over. Clone these
2199  // instructions into EdgeBB. We know that there will be no uses of the
2200  // cloned instructions outside of EdgeBB.
2201  BasicBlock::iterator InsertPt = EdgeBB->begin();
2202  DenseMap<Value *, Value *> TranslateMap; // Track translated values.
2203  for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) {
2204  if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
2205  TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB);
2206  continue;
2207  }
2208  // Clone the instruction.
2209  Instruction *N = BBI->clone();
2210  if (BBI->hasName())
2211  N->setName(BBI->getName() + ".c");
2212 
2213  // Update operands due to translation.
2214  for (User::op_iterator i = N->op_begin(), e = N->op_end(); i != e; ++i) {
2215  DenseMap<Value *, Value *>::iterator PI = TranslateMap.find(*i);
2216  if (PI != TranslateMap.end())
2217  *i = PI->second;
2218  }
2219 
2220  // Check for trivial simplification.
2221  if (Value *V = SimplifyInstruction(N, {DL, nullptr, nullptr, AC})) {
2222  if (!BBI->use_empty())
2223  TranslateMap[&*BBI] = V;
2224  if (!N->mayHaveSideEffects()) {
2225  N->deleteValue(); // Instruction folded away, don't need actual inst
2226  N = nullptr;
2227  }
2228  } else {
2229  if (!BBI->use_empty())
2230  TranslateMap[&*BBI] = N;
2231  }
2232  // Insert the new instruction into its new home.
2233  if (N)
2234  EdgeBB->getInstList().insert(InsertPt, N);
2235 
2236  // Register the new instruction with the assumption cache if necessary.
2237  if (auto *II = dyn_cast_or_null<IntrinsicInst>(N))
2238  if (II->getIntrinsicID() == Intrinsic::assume)
2239  AC->registerAssumption(II);
2240  }
2241 
2242  // Loop over all of the edges from PredBB to BB, changing them to branch
2243  // to EdgeBB instead.
2244  TerminatorInst *PredBBTI = PredBB->getTerminator();
2245  for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i)
2246  if (PredBBTI->getSuccessor(i) == BB) {
2247  BB->removePredecessor(PredBB);
2248  PredBBTI->setSuccessor(i, EdgeBB);
2249  }
2250 
2251  // Recurse, simplifying any other constants.
2252  return FoldCondBranchOnPHI(BI, DL, AC) | true;
2253  }
2254 
2255  return false;
2256 }
2257 
2258 /// Given a BB that starts with the specified two-entry PHI node,
2259 /// see if we can eliminate it.
2261  const DataLayout &DL) {
2262  // Ok, this is a two entry PHI node. Check to see if this is a simple "if
2263  // statement", which has a very simple dominance structure. Basically, we
2264  // are trying to find the condition that is being branched on, which
2265  // subsequently causes this merge to happen. We really want control
2266  // dependence information for this check, but simplifycfg can't keep it up
2267  // to date, and this catches most of the cases we care about anyway.
2268  BasicBlock *BB = PN->getParent();
2269  const Function *Fn = BB->getParent();
2270  if (Fn && Fn->hasFnAttribute(Attribute::OptForFuzzing))
2271  return false;
2272 
2273  BasicBlock *IfTrue, *IfFalse;
2274  Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse);
2275  if (!IfCond ||
2276  // Don't bother if the branch will be constant folded trivially.
2277  isa<ConstantInt>(IfCond))
2278  return false;
2279 
2280  // Okay, we found that we can merge this two-entry phi node into a select.
2281  // Doing so would require us to fold *all* two entry phi nodes in this block.
2282  // At some point this becomes non-profitable (particularly if the target
2283  // doesn't support cmov's). Only do this transformation if there are two or
2284  // fewer PHI nodes in this block.
2285  unsigned NumPhis = 0;
2286  for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I)
2287  if (NumPhis > 2)
2288  return false;
2289 
2290  // Loop over the PHI's seeing if we can promote them all to select
2291  // instructions. While we are at it, keep track of the instructions
2292  // that need to be moved to the dominating block.
2293  SmallPtrSet<Instruction *, 4> AggressiveInsts;
2294  unsigned MaxCostVal0 = PHINodeFoldingThreshold,
2295  MaxCostVal1 = PHINodeFoldingThreshold;
2296  MaxCostVal0 *= TargetTransformInfo::TCC_Basic;
2297  MaxCostVal1 *= TargetTransformInfo::TCC_Basic;
2298 
2299  for (BasicBlock::iterator II = BB->begin(); isa<PHINode>(II);) {
2300  PHINode *PN = cast<PHINode>(II++);
2301  if (Value *V = SimplifyInstruction(PN, {DL, PN})) {
2302  PN->replaceAllUsesWith(V);
2303  PN->eraseFromParent();
2304  continue;
2305  }
2306 
2307  if (!DominatesMergePoint(PN->getIncomingValue(0), BB, &AggressiveInsts,
2308  MaxCostVal0, TTI) ||
2309  !DominatesMergePoint(PN->getIncomingValue(1), BB, &AggressiveInsts,
2310  MaxCostVal1, TTI))
2311  return false;
2312  }
2313 
2314  // If we folded the first phi, PN dangles at this point. Refresh it. If
2315  // we ran out of PHIs then we simplified them all.
2316  PN = dyn_cast<PHINode>(BB->begin());
2317  if (!PN)
2318  return true;
2319 
2320  // Don't fold i1 branches on PHIs which contain binary operators. These can
2321  // often be turned into switches and other things.
2322  if (PN->getType()->isIntegerTy(1) &&
2323  (isa<BinaryOperator>(PN->getIncomingValue(0)) ||
2324  isa<BinaryOperator>(PN->getIncomingValue(1)) ||
2325  isa<BinaryOperator>(IfCond)))
2326  return false;
2327 
2328  // If all PHI nodes are promotable, check to make sure that all instructions
2329  // in the predecessor blocks can be promoted as well. If not, we won't be able
2330  // to get rid of the control flow, so it's not worth promoting to select
2331  // instructions.
2332  BasicBlock *DomBlock = nullptr;
2333  BasicBlock *IfBlock1 = PN->getIncomingBlock(0);
2334  BasicBlock *IfBlock2 = PN->getIncomingBlock(1);
2335  if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) {
2336  IfBlock1 = nullptr;
2337  } else {
2338  DomBlock = *pred_begin(IfBlock1);
2339  for (BasicBlock::iterator I = IfBlock1->begin(); !isa<TerminatorInst>(I);
2340  ++I)
2341  if (!AggressiveInsts.count(&*I) && !isa<DbgInfoIntrinsic>(I)) {
2342  // This is not an aggressive instruction that we can promote.
2343  // Because of this, we won't be able to get rid of the control flow, so
2344  // the xform is not worth it.
2345  return false;
2346  }
2347  }
2348 
2349  if (cast<BranchInst>(IfBlock2->getTerminator())->isConditional()) {
2350  IfBlock2 = nullptr;
2351  } else {
2352  DomBlock = *pred_begin(IfBlock2);
2353  for (BasicBlock::iterator I = IfBlock2->begin(); !isa<TerminatorInst>(I);
2354  ++I)
2355  if (!AggressiveInsts.count(&*I) && !isa<DbgInfoIntrinsic>(I)) {
2356  // This is not an aggressive instruction that we can promote.
2357  // Because of this, we won't be able to get rid of the control flow, so
2358  // the xform is not worth it.
2359  return false;
2360  }
2361  }
2362 
2363  LLVM_DEBUG(dbgs() << "FOUND IF CONDITION! " << *IfCond
2364  << " T: " << IfTrue->getName()
2365  << " F: " << IfFalse->getName() << "\n");
2366 
2367  // If we can still promote the PHI nodes after this gauntlet of tests,
2368  // do all of the PHI's now.
2369  Instruction *InsertPt = DomBlock->getTerminator();
2370  IRBuilder<NoFolder> Builder(InsertPt);
2371 
2372  // Move all 'aggressive' instructions, which are defined in the
2373  // conditional parts of the if's up to the dominating block.
2374  if (IfBlock1) {
2375  for (auto &I : *IfBlock1)
2377  DomBlock->getInstList().splice(InsertPt->getIterator(),
2378  IfBlock1->getInstList(), IfBlock1->begin(),
2379  IfBlock1->getTerminator()->getIterator());
2380  }
2381  if (IfBlock2) {
2382  for (auto &I : *IfBlock2)
2384  DomBlock->getInstList().splice(InsertPt->getIterator(),
2385  IfBlock2->getInstList(), IfBlock2->begin(),
2386  IfBlock2->getTerminator()->getIterator());
2387  }
2388 
2389  while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
2390  // Change the PHI node into a select instruction.
2391  Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
2392  Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
2393 
2394  Value *Sel = Builder.CreateSelect(IfCond, TrueVal, FalseVal, "", InsertPt);
2395  PN->replaceAllUsesWith(Sel);
2396  Sel->takeName(PN);
2397  PN->eraseFromParent();
2398  }
2399 
2400  // At this point, IfBlock1 and IfBlock2 are both empty, so our if statement
2401  // has been flattened. Change DomBlock to jump directly to our new block to
2402  // avoid other simplifycfg's kicking in on the diamond.
2403  TerminatorInst *OldTI = DomBlock->getTerminator();
2404  Builder.SetInsertPoint(OldTI);
2405  Builder.CreateBr(BB);
2406  OldTI->eraseFromParent();
2407  return true;
2408 }
2409 
2410 /// If we found a conditional branch that goes to two returning blocks,
2411 /// try to merge them together into one return,
2412 /// introducing a select if the return values disagree.
2414  IRBuilder<> &Builder) {
2415  assert(BI->isConditional() && "Must be a conditional branch");
2416  BasicBlock *TrueSucc = BI->getSuccessor(0);
2417  BasicBlock *FalseSucc = BI->getSuccessor(1);
2418  ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator());
2419  ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator());
2420 
2421  // Check to ensure both blocks are empty (just a return) or optionally empty
2422  // with PHI nodes. If there are other instructions, merging would cause extra
2423  // computation on one path or the other.
2424  if (!TrueSucc->getFirstNonPHIOrDbg()->isTerminator())
2425  return false;
2426  if (!FalseSucc->getFirstNonPHIOrDbg()->isTerminator())
2427  return false;
2428 
2429  Builder.SetInsertPoint(BI);
2430  // Okay, we found a branch that is going to two return nodes. If
2431  // there is no return value for this function, just change the
2432  // branch into a return.
2433  if (FalseRet->getNumOperands() == 0) {
2434  TrueSucc->removePredecessor(BI->getParent());
2435  FalseSucc->removePredecessor(BI->getParent());
2436  Builder.CreateRetVoid();
2438  return true;
2439  }
2440 
2441  // Otherwise, figure out what the true and false return values are
2442  // so we can insert a new select instruction.
2443  Value *TrueValue = TrueRet->getReturnValue();
2444  Value *FalseValue = FalseRet->getReturnValue();
2445 
2446  // Unwrap any PHI nodes in the return blocks.
2447  if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue))
2448  if (TVPN->getParent() == TrueSucc)
2449  TrueValue = TVPN->getIncomingValueForBlock(BI->getParent());
2450  if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue))
2451  if (FVPN->getParent() == FalseSucc)
2452  FalseValue = FVPN->getIncomingValueForBlock(BI->getParent());
2453 
2454  // In order for this transformation to be safe, we must be able to
2455  // unconditionally execute both operands to the return. This is
2456  // normally the case, but we could have a potentially-trapping
2457  // constant expression that prevents this transformation from being
2458  // safe.
2459  if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue))
2460  if (TCV->canTrap())
2461  return false;
2462  if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue))
2463  if (FCV->canTrap())
2464  return false;
2465 
2466  // Okay, we collected all the mapped values and checked them for sanity, and
2467  // defined to really do this transformation. First, update the CFG.
2468  TrueSucc->removePredecessor(BI->getParent());
2469  FalseSucc->removePredecessor(BI->getParent());
2470 
2471  // Insert select instructions where needed.
2472  Value *BrCond = BI->getCondition();
2473  if (TrueValue) {
2474  // Insert a select if the results differ.
2475  if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) {
2476  } else if (isa<UndefValue>(TrueValue)) {
2477  TrueValue = FalseValue;
2478  } else {
2479  TrueValue =
2480  Builder.CreateSelect(BrCond, TrueValue, FalseValue, "retval", BI);
2481  }
2482  }
2483 
2484  Value *RI =
2485  !TrueValue ? Builder.CreateRetVoid() : Builder.CreateRet(TrueValue);
2486 
2487  (void)RI;
2488 
2489  LLVM_DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:"
2490  << "\n " << *BI << "NewRet = " << *RI << "TRUEBLOCK: "
2491  << *TrueSucc << "FALSEBLOCK: " << *FalseSucc);
2492 
2494 
2495  return true;
2496 }
2497 
2498 /// Return true if the given instruction is available
2499 /// in its predecessor block. If yes, the instruction will be removed.
2501  if (!isa<BinaryOperator>(Inst) && !isa<CmpInst>(Inst))
2502  return false;
2503  for (Instruction &I : *PB) {
2504  Instruction *PBI = &I;
2505  // Check whether Inst and PBI generate the same value.
2506  if (Inst->isIdenticalTo(PBI)) {
2507  Inst->replaceAllUsesWith(PBI);
2508  Inst->eraseFromParent();
2509  return true;
2510  }
2511  }
2512  return false;
2513 }
2514 
2515 /// Return true if either PBI or BI has branch weight available, and store
2516 /// the weights in {Pred|Succ}{True|False}Weight. If one of PBI and BI does
2517 /// not have branch weight, use 1:1 as its weight.
2519  uint64_t &PredTrueWeight,
2520  uint64_t &PredFalseWeight,
2521  uint64_t &SuccTrueWeight,
2522  uint64_t &SuccFalseWeight) {
2523  bool PredHasWeights =
2524  PBI->extractProfMetadata(PredTrueWeight, PredFalseWeight);
2525  bool SuccHasWeights =
2526  BI->extractProfMetadata(SuccTrueWeight, SuccFalseWeight);
2527  if (PredHasWeights || SuccHasWeights) {
2528  if (!PredHasWeights)
2529  PredTrueWeight = PredFalseWeight = 1;
2530  if (!SuccHasWeights)
2531  SuccTrueWeight = SuccFalseWeight = 1;
2532  return true;
2533  } else {
2534  return false;
2535  }
2536 }
2537 
2538 /// If this basic block is simple enough, and if a predecessor branches to us
2539 /// and one of our successors, fold the block into the predecessor and use
2540 /// logical operations to pick the right destination.
2541 bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) {
2542  BasicBlock *BB = BI->getParent();
2543 
2544  Instruction *Cond = nullptr;
2545  if (BI->isConditional())
2546  Cond = dyn_cast<Instruction>(BI->getCondition());
2547  else {
2548  // For unconditional branch, check for a simple CFG pattern, where
2549  // BB has a single predecessor and BB's successor is also its predecessor's
2550  // successor. If such pattern exists, check for CSE between BB and its
2551  // predecessor.
2552  if (BasicBlock *PB = BB->getSinglePredecessor())
2553  if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator()))
2554  if (PBI->isConditional() &&
2555  (BI->getSuccessor(0) == PBI->getSuccessor(0) ||
2556  BI->getSuccessor(0) == PBI->getSuccessor(1))) {
2557  for (auto I = BB->instructionsWithoutDebug().begin(),
2558  E = BB->instructionsWithoutDebug().end();
2559  I != E;) {
2560  Instruction *Curr = &*I++;
2561  if (isa<CmpInst>(Curr)) {
2562  Cond = Curr;
2563  break;
2564  }
2565  // Quit if we can't remove this instruction.
2566  if (!tryCSEWithPredecessor(Curr, PB))
2567  return false;
2568  }
2569  }
2570 
2571  if (!Cond)
2572  return false;
2573  }
2574 
2575  if (!Cond || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) ||
2576  Cond->getParent() != BB || !Cond->hasOneUse())
2577  return false;
2578 
2579  // Make sure the instruction after the condition is the cond branch.
2580  BasicBlock::iterator CondIt = ++Cond->getIterator();
2581 
2582  // Ignore dbg intrinsics.
2583  while (isa<DbgInfoIntrinsic>(CondIt))
2584  ++CondIt;
2585 
2586  if (&*CondIt != BI)
2587  return false;
2588 
2589  // Only allow this transformation if computing the condition doesn't involve
2590  // too many instructions and these involved instructions can be executed
2591  // unconditionally. We denote all involved instructions except the condition
2592  // as "bonus instructions", and only allow this transformation when the
2593  // number of the bonus instructions does not exceed a certain threshold.
2594  unsigned NumBonusInsts = 0;
2595  for (auto I = BB->begin(); Cond != &*I; ++I) {
2596  // Ignore dbg intrinsics.
2597  if (isa<DbgInfoIntrinsic>(I))
2598  continue;
2599  if (!I->hasOneUse() || !isSafeToSpeculativelyExecute(&*I))
2600  return false;
2601  // I has only one use and can be executed unconditionally.
2603  if (User == nullptr || User->getParent() != BB)
2604  return false;
2605  // I is used in the same BB. Since BI uses Cond and doesn't have more slots
2606  // to use any other instruction, User must be an instruction between next(I)
2607  // and Cond.
2608  ++NumBonusInsts;
2609  // Early exits once we reach the limit.
2610  if (NumBonusInsts > BonusInstThreshold)
2611  return false;
2612  }
2613 
2614  // Cond is known to be a compare or binary operator. Check to make sure that
2615  // neither operand is a potentially-trapping constant expression.
2616  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0)))
2617  if (CE->canTrap())
2618  return false;
2619  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1)))
2620  if (CE->canTrap())
2621  return false;
2622 
2623  // Finally, don't infinitely unroll conditional loops.
2624  BasicBlock *TrueDest = BI->getSuccessor(0);
2625  BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : nullptr;
2626  if (TrueDest == BB || FalseDest == BB)
2627  return false;
2628 
2629  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
2630  BasicBlock *PredBlock = *PI;
2631  BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
2632 
2633  // Check that we have two conditional branches. If there is a PHI node in
2634  // the common successor, verify that the same value flows in from both
2635  // blocks.
2637  if (!PBI || PBI->isUnconditional() ||
2638  (BI->isConditional() && !SafeToMergeTerminators(BI, PBI)) ||
2639  (!BI->isConditional() &&
2640  !isProfitableToFoldUnconditional(BI, PBI, Cond, PHIs)))
2641  continue;
2642 
2643  // Determine if the two branches share a common destination.
2644  Instruction::BinaryOps Opc = Instruction::BinaryOpsEnd;
2645  bool InvertPredCond = false;
2646 
2647  if (BI->isConditional()) {
2648  if (PBI->getSuccessor(0) == TrueDest) {
2649  Opc = Instruction::Or;
2650  } else if (PBI->getSuccessor(1) == FalseDest) {
2651  Opc = Instruction::And;
2652  } else if (PBI->getSuccessor(0) == FalseDest) {
2653  Opc = Instruction::And;
2654  InvertPredCond = true;
2655  } else if (PBI->getSuccessor(1) == TrueDest) {
2656  Opc = Instruction::Or;
2657  InvertPredCond = true;
2658  } else {
2659  continue;
2660  }
2661  } else {
2662  if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest)
2663  continue;
2664  }
2665 
2666  LLVM_DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
2667  IRBuilder<> Builder(PBI);
2668 
2669  // If we need to invert the condition in the pred block to match, do so now.
2670  if (InvertPredCond) {
2671  Value *NewCond = PBI->getCondition();
2672 
2673  if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) {
2674  CmpInst *CI = cast<CmpInst>(NewCond);
2675  CI->setPredicate(CI->getInversePredicate());
2676  } else {
2677  NewCond =
2678  Builder.CreateNot(NewCond, PBI->getCondition()->getName() + ".not");
2679  }
2680 
2681  PBI->setCondition(NewCond);
2682  PBI->swapSuccessors();
2683  }
2684 
2685  // If we have bonus instructions, clone them into the predecessor block.
2686  // Note that there may be multiple predecessor blocks, so we cannot move
2687  // bonus instructions to a predecessor block.
2688  ValueToValueMapTy VMap; // maps original values to cloned values
2689  // We already make sure Cond is the last instruction before BI. Therefore,
2690  // all instructions before Cond other than DbgInfoIntrinsic are bonus
2691  // instructions.
2692  for (auto BonusInst = BB->begin(); Cond != &*BonusInst; ++BonusInst) {
2693  if (isa<DbgInfoIntrinsic>(BonusInst))
2694  continue;
2695  Instruction *NewBonusInst = BonusInst->clone();
2696  RemapInstruction(NewBonusInst, VMap,
2698  VMap[&*BonusInst] = NewBonusInst;
2699 
2700  // If we moved a load, we cannot any longer claim any knowledge about
2701  // its potential value. The previous information might have been valid
2702  // only given the branch precondition.
2703  // For an analogous reason, we must also drop all the metadata whose
2704  // semantics we don't understand.
2705  NewBonusInst->dropUnknownNonDebugMetadata();
2706 
2707  PredBlock->getInstList().insert(PBI->getIterator(), NewBonusInst);
2708  NewBonusInst->takeName(&*BonusInst);
2709  BonusInst->setName(BonusInst->getName() + ".old");
2710  }
2711 
2712  // Clone Cond into the predecessor basic block, and or/and the
2713  // two conditions together.
2714  Instruction *New = Cond->clone();
2715  RemapInstruction(New, VMap,
2717  PredBlock->getInstList().insert(PBI->getIterator(), New);
2718  New->takeName(Cond);
2719  Cond->setName(New->getName() + ".old");
2720 
2721  if (BI->isConditional()) {
2722  Instruction *NewCond = cast<Instruction>(
2723  Builder.CreateBinOp(Opc, PBI->getCondition(), New, "or.cond"));
2724  PBI->setCondition(NewCond);
2725 
2726  uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
2727  bool HasWeights =
2728  extractPredSuccWeights(PBI, BI, PredTrueWeight, PredFalseWeight,
2729  SuccTrueWeight, SuccFalseWeight);
2730  SmallVector<uint64_t, 8> NewWeights;
2731 
2732  if (PBI->getSuccessor(0) == BB) {
2733  if (HasWeights) {
2734  // PBI: br i1 %x, BB, FalseDest
2735  // BI: br i1 %y, TrueDest, FalseDest
2736  // TrueWeight is TrueWeight for PBI * TrueWeight for BI.
2737  NewWeights.push_back(PredTrueWeight * SuccTrueWeight);
2738  // FalseWeight is FalseWeight for PBI * TotalWeight for BI +
2739  // TrueWeight for PBI * FalseWeight for BI.
2740  // We assume that total weights of a BranchInst can fit into 32 bits.
2741  // Therefore, we will not have overflow using 64-bit arithmetic.
2742  NewWeights.push_back(PredFalseWeight *
2743  (SuccFalseWeight + SuccTrueWeight) +
2744  PredTrueWeight * SuccFalseWeight);
2745  }
2746  AddPredecessorToBlock(TrueDest, PredBlock, BB);
2747  PBI->setSuccessor(0, TrueDest);
2748  }
2749  if (PBI->getSuccessor(1) == BB) {
2750  if (HasWeights) {
2751  // PBI: br i1 %x, TrueDest, BB
2752  // BI: br i1 %y, TrueDest, FalseDest
2753  // TrueWeight is TrueWeight for PBI * TotalWeight for BI +
2754  // FalseWeight for PBI * TrueWeight for BI.
2755  NewWeights.push_back(PredTrueWeight *
2756  (SuccFalseWeight + SuccTrueWeight) +
2757  PredFalseWeight * SuccTrueWeight);
2758  // FalseWeight is FalseWeight for PBI * FalseWeight for BI.
2759  NewWeights.push_back(PredFalseWeight * SuccFalseWeight);
2760  }
2761  AddPredecessorToBlock(FalseDest, PredBlock, BB);
2762  PBI->setSuccessor(1, FalseDest);
2763  }
2764  if (NewWeights.size() == 2) {
2765  // Halve the weights if any of them cannot fit in an uint32_t
2766  FitWeights(NewWeights);
2767 
2768  SmallVector<uint32_t, 8> MDWeights(NewWeights.begin(),
2769  NewWeights.end());
2770  setBranchWeights(PBI, MDWeights[0], MDWeights[1]);
2771  } else
2772  PBI->setMetadata(LLVMContext::MD_prof, nullptr);
2773  } else {
2774  // Update PHI nodes in the common successors.
2775  for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
2776  ConstantInt *PBI_C = cast<ConstantInt>(
2777  PHIs[i]->getIncomingValueForBlock(PBI->getParent()));
2778  assert(PBI_C->getType()->isIntegerTy(1));
2779  Instruction *MergedCond = nullptr;
2780  if (PBI->getSuccessor(0) == TrueDest) {
2781  // Create (PBI_Cond and PBI_C) or (!PBI_Cond and BI_Value)
2782  // PBI_C is true: PBI_Cond or (!PBI_Cond and BI_Value)
2783  // is false: !PBI_Cond and BI_Value
2784  Instruction *NotCond = cast<Instruction>(
2785  Builder.CreateNot(PBI->getCondition(), "not.cond"));
2786  MergedCond = cast<Instruction>(
2787  Builder.CreateBinOp(Instruction::And, NotCond, New, "and.cond"));
2788  if (PBI_C->isOne())
2789  MergedCond = cast<Instruction>(Builder.CreateBinOp(
2790  Instruction::Or, PBI->getCondition(), MergedCond, "or.cond"));
2791  } else {
2792  // Create (PBI_Cond and BI_Value) or (!PBI_Cond and PBI_C)
2793  // PBI_C is true: (PBI_Cond and BI_Value) or (!PBI_Cond)
2794  // is false: PBI_Cond and BI_Value
2795  MergedCond = cast<Instruction>(Builder.CreateBinOp(
2796  Instruction::And, PBI->getCondition(), New, "and.cond"));
2797  if (PBI_C->isOne()) {
2798  Instruction *NotCond = cast<Instruction>(
2799  Builder.CreateNot(PBI->getCondition(), "not.cond"));
2800  MergedCond = cast<Instruction>(Builder.CreateBinOp(
2801  Instruction::Or, NotCond, MergedCond, "or.cond"));
2802  }
2803  }
2804  // Update PHI Node.
2805  PHIs[i]->setIncomingValue(PHIs[i]->getBasicBlockIndex(PBI->getParent()),
2806  MergedCond);
2807  }
2808  // Change PBI from Conditional to Unconditional.
2809  BranchInst *New_PBI = BranchInst::Create(TrueDest, PBI);
2811  PBI = New_PBI;
2812  }
2813 
2814  // If BI was a loop latch, it may have had associated loop metadata.
2815  // We need to copy it to the new latch, that is, PBI.
2816  if (MDNode *LoopMD = BI->getMetadata(LLVMContext::MD_loop))
2817  PBI->setMetadata(LLVMContext::MD_loop, LoopMD);
2818 
2819  // TODO: If BB is reachable from all paths through PredBlock, then we
2820  // could replace PBI's branch probabilities with BI's.
2821 
2822  // Copy any debug value intrinsics into the end of PredBlock.
2823  for (Instruction &I : *BB)
2824  if (isa<DbgInfoIntrinsic>(I))
2825  I.clone()->insertBefore(PBI);
2826 
2827  return true;
2828  }
2829  return false;
2830 }
2831 
2832 // If there is only one store in BB1 and BB2, return it, otherwise return
2833 // nullptr.
2835  StoreInst *S = nullptr;
2836  for (auto *BB : {BB1, BB2}) {
2837  if (!BB)
2838  continue;
2839  for (auto &I : *BB)
2840  if (auto *SI = dyn_cast<StoreInst>(&I)) {
2841  if (S)
2842  // Multiple stores seen.
2843  return nullptr;
2844  else
2845  S = SI;
2846  }
2847  }
2848  return S;
2849 }
2850 
2852  Value *AlternativeV = nullptr) {
2853  // PHI is going to be a PHI node that allows the value V that is defined in
2854  // BB to be referenced in BB's only successor.
2855  //
2856  // If AlternativeV is nullptr, the only value we care about in PHI is V. It
2857  // doesn't matter to us what the other operand is (it'll never get used). We
2858  // could just create a new PHI with an undef incoming value, but that could
2859  // increase register pressure if EarlyCSE/InstCombine can't fold it with some
2860  // other PHI. So here we directly look for some PHI in BB's successor with V
2861  // as an incoming operand. If we find one, we use it, else we create a new
2862  // one.
2863  //
2864  // If AlternativeV is not nullptr, we care about both incoming values in PHI.
2865  // PHI must be exactly: phi <ty> [ %BB, %V ], [ %OtherBB, %AlternativeV]
2866  // where OtherBB is the single other predecessor of BB's only successor.
2867  PHINode *PHI = nullptr;
2868  BasicBlock *Succ = BB->getSingleSuccessor();
2869 
2870  for (auto I = Succ->begin(); isa<PHINode>(I); ++I)
2871  if (cast<PHINode>(I)->getIncomingValueForBlock(BB) == V) {
2872  PHI = cast<PHINode>(I);
2873  if (!AlternativeV)
2874  break;
2875 
2876  assert(pred_size(Succ) == 2);
2877  auto PredI = pred_begin(Succ);
2878  BasicBlock *OtherPredBB = *PredI == BB ? *++PredI : *PredI;
2879  if (PHI->getIncomingValueForBlock(OtherPredBB) == AlternativeV)
2880  break;
2881  PHI = nullptr;
2882  }
2883  if (PHI)
2884  return PHI;
2885 
2886  // If V is not an instruction defined in BB, just return it.
2887  if (!AlternativeV &&
2888  (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != BB))
2889  return V;
2890 
2891  PHI = PHINode::Create(V->getType(), 2, "simplifycfg.merge", &Succ->front());
2892  PHI->addIncoming(V, BB);
2893  for (BasicBlock *PredBB : predecessors(Succ))
2894  if (PredBB != BB)
2895  PHI->addIncoming(
2896  AlternativeV ? AlternativeV : UndefValue::get(V->getType()), PredBB);
2897  return PHI;
2898 }
2899 
2901  BasicBlock *QTB, BasicBlock *QFB,
2902  BasicBlock *PostBB, Value *Address,
2903  bool InvertPCond, bool InvertQCond,
2904  const DataLayout &DL) {
2905  auto IsaBitcastOfPointerType = [](const Instruction &I) {
2906  return Operator::getOpcode(&I) == Instruction::BitCast &&
2907  I.getType()->isPointerTy();
2908  };
2909 
2910  // If we're not in aggressive mode, we only optimize if we have some
2911  // confidence that by optimizing we'll allow P and/or Q to be if-converted.
2912  auto IsWorthwhile = [&](BasicBlock *BB) {
2913  if (!BB)
2914  return true;
2915  // Heuristic: if the block can be if-converted/phi-folded and the
2916  // instructions inside are all cheap (arithmetic/GEPs), it's worthwhile to
2917  // thread this store.
2918  unsigned N = 0;
2919  for (auto &I : BB->instructionsWithoutDebug()) {
2920  // Cheap instructions viable for folding.
2921  if (isa<BinaryOperator>(I) || isa<GetElementPtrInst>(I) ||
2922  isa<StoreInst>(I))
2923  ++N;
2924  // Free instructions.
2925  else if (isa<TerminatorInst>(I) || IsaBitcastOfPointerType(I))
2926  continue;
2927  else
2928  return false;
2929  }
2930  // The store we want to merge is counted in N, so add 1 to make sure
2931  // we're counting the instructions that would be left.
2932  return N <= (PHINodeFoldingThreshold + 1);
2933  };
2934 
2936  (!IsWorthwhile(PTB) || !IsWorthwhile(PFB) || !IsWorthwhile(QTB) ||
2937  !IsWorthwhile(QFB)))
2938  return false;
2939 
2940  // For every pointer, there must be exactly two stores, one coming from
2941  // PTB or PFB, and the other from QTB or QFB. We don't support more than one
2942  // store (to any address) in PTB,PFB or QTB,QFB.
2943  // FIXME: We could relax this restriction with a bit more work and performance
2944  // testing.
2945  StoreInst *PStore = findUniqueStoreInBlocks(PTB, PFB);
2946  StoreInst *QStore = findUniqueStoreInBlocks(QTB, QFB);
2947  if (!PStore || !QStore)
2948  return false;
2949 
2950  // Now check the stores are compatible.
2951  if (!QStore->isUnordered() || !PStore->isUnordered())
2952  return false;
2953 
2954  // Check that sinking the store won't cause program behavior changes. Sinking
2955  // the store out of the Q blocks won't change any behavior as we're sinking
2956  // from a block to its unconditional successor. But we're moving a store from
2957  // the P blocks down through the middle block (QBI) and past both QFB and QTB.
2958  // So we need to check that there are no aliasing loads or stores in
2959  // QBI, QTB and QFB. We also need to check there are no conflicting memory
2960  // operations between PStore and the end of its parent block.
2961  //
2962  // The ideal way to do this is to query AliasAnalysis, but we don't
2963  // preserve AA currently so that is dangerous. Be super safe and just
2964  // check there are no other memory operations at all.
2965  for (auto &I : *QFB->getSinglePredecessor())
2966  if (I.mayReadOrWriteMemory())
2967  return false;
2968  for (auto &I : *QFB)
2969  if (&I != QStore && I.mayReadOrWriteMemory())
2970  return false;
2971  if (QTB)
2972  for (auto &I : *QTB)
2973  if (&I != QStore && I.mayReadOrWriteMemory())
2974  return false;
2975  for (auto I = BasicBlock::iterator(PStore), E = PStore->getParent()->end();
2976  I != E; ++I)
2977  if (&*I != PStore && I->mayReadOrWriteMemory())
2978  return false;
2979 
2980  // If PostBB has more than two predecessors, we need to split it so we can
2981  // sink the store.
2982  if (std::next(pred_begin(PostBB), 2) != pred_end(PostBB)) {
2983  // We know that QFB's only successor is PostBB. And QFB has a single
2984  // predecessor. If QTB exists, then its only successor is also PostBB.
2985  // If QTB does not exist, then QFB's only predecessor has a conditional
2986  // branch to QFB and PostBB.
2987  BasicBlock *TruePred = QTB ? QTB : QFB->getSinglePredecessor();
2988  BasicBlock *NewBB = SplitBlockPredecessors(PostBB, { QFB, TruePred},
2989  "condstore.split");
2990  if (!NewBB)
2991  return false;
2992  PostBB = NewBB;
2993  }
2994 
2995  // OK, we're going to sink the stores to PostBB. The store has to be
2996  // conditional though, so first create the predicate.
2997  Value *PCond = cast<BranchInst>(PFB->getSinglePredecessor()->getTerminator())
2998  ->getCondition();
2999  Value *QCond = cast<BranchInst>(QFB->getSinglePredecessor()->getTerminator())
3000  ->getCondition();
3001 
3003  PStore->getParent());
3005  QStore->getParent(), PPHI);
3006 
3007  IRBuilder<> QB(&*PostBB->getFirstInsertionPt());
3008 
3009  Value *PPred = PStore->getParent() == PTB ? PCond : QB.CreateNot(PCond);
3010  Value *QPred = QStore->getParent() == QTB ? QCond : QB.CreateNot(QCond);
3011 
3012  if (InvertPCond)
3013  PPred = QB.CreateNot(PPred);
3014  if (InvertQCond)
3015  QPred = QB.CreateNot(QPred);
3016  Value *CombinedPred = QB.CreateOr(PPred, QPred);
3017 
3018  auto *T =
3019  SplitBlockAndInsertIfThen(CombinedPred, &*QB.GetInsertPoint(), false);
3020  QB.SetInsertPoint(T);
3021  StoreInst *SI = cast<StoreInst>(QB.CreateStore(QPHI, Address));
3022  AAMDNodes AAMD;
3023  PStore->getAAMetadata(AAMD, /*Merge=*/false);
3024  PStore->getAAMetadata(AAMD, /*Merge=*/true);
3025  SI->setAAMetadata(AAMD);
3026  unsigned PAlignment = PStore->getAlignment();
3027  unsigned QAlignment = QStore->getAlignment();
3028  unsigned TypeAlignment =
3030  unsigned MinAlignment;
3031  unsigned MaxAlignment;
3032  std::tie(MinAlignment, MaxAlignment) = std::minmax(PAlignment, QAlignment);
3033  // Choose the minimum alignment. If we could prove both stores execute, we
3034  // could use biggest one. In this case, though, we only know that one of the
3035  // stores executes. And we don't know it's safe to take the alignment from a
3036  // store that doesn't execute.
3037  if (MinAlignment != 0) {
3038  // Choose the minimum of all non-zero alignments.
3039  SI->setAlignment(MinAlignment);
3040  } else if (MaxAlignment != 0) {
3041  // Choose the minimal alignment between the non-zero alignment and the ABI
3042  // default alignment for the type of the stored value.
3043  SI->setAlignment(std::min(MaxAlignment, TypeAlignment));
3044  } else {
3045  // If both alignments are zero, use ABI default alignment for the type of
3046  // the stored value.
3047  SI->setAlignment(TypeAlignment);
3048  }
3049 
3050  QStore->eraseFromParent();
3051  PStore->eraseFromParent();
3052 
3053  return true;
3054 }
3055 
3057  const DataLayout &DL) {
3058  // The intention here is to find diamonds or triangles (see below) where each
3059  // conditional block contains a store to the same address. Both of these
3060  // stores are conditional, so they can't be unconditionally sunk. But it may
3061  // be profitable to speculatively sink the stores into one merged store at the
3062  // end, and predicate the merged store on the union of the two conditions of
3063  // PBI and QBI.
3064  //
3065  // This can reduce the number of stores executed if both of the conditions are
3066  // true, and can allow the blocks to become small enough to be if-converted.
3067  // This optimization will also chain, so that ladders of test-and-set
3068  // sequences can be if-converted away.
3069  //
3070  // We only deal with simple diamonds or triangles:
3071  //
3072  // PBI or PBI or a combination of the two
3073  // / \ | \
3074  // PTB PFB | PFB
3075  // \ / | /
3076  // QBI QBI
3077  // / \ | \
3078  // QTB QFB | QFB
3079  // \ / | /
3080  // PostBB PostBB
3081  //
3082  // We model triangles as a type of diamond with a nullptr "true" block.
3083  // Triangles are canonicalized so that the fallthrough edge is represented by
3084  // a true condition, as in the diagram above.
3085  BasicBlock *PTB = PBI->getSuccessor(0);
3086  BasicBlock *PFB = PBI->getSuccessor(1);
3087  BasicBlock *QTB = QBI->getSuccessor(0);
3088  BasicBlock *QFB = QBI->getSuccessor(1);
3089  BasicBlock *PostBB = QFB->getSingleSuccessor();
3090 
3091  // Make sure we have a good guess for PostBB. If QTB's only successor is
3092  // QFB, then QFB is a better PostBB.
3093  if (QTB->getSingleSuccessor() == QFB)
3094  PostBB = QFB;
3095 
3096  // If we couldn't find a good PostBB, stop.
3097  if (!PostBB)
3098  return false;
3099 
3100  bool InvertPCond = false, InvertQCond = false;
3101  // Canonicalize fallthroughs to the true branches.
3102  if (PFB == QBI->getParent()) {
3103  std::swap(PFB, PTB);
3104  InvertPCond = true;
3105  }
3106  if (QFB == PostBB) {
3107  std::swap(QFB, QTB);
3108  InvertQCond = true;
3109  }
3110 
3111  // From this point on we can assume PTB or QTB may be fallthroughs but PFB
3112  // and QFB may not. Model fallthroughs as a nullptr block.
3113  if (PTB == QBI->getParent())
3114  PTB = nullptr;
3115  if (QTB == PostBB)
3116  QTB = nullptr;
3117 
3118  // Legality bailouts. We must have at least the non-fallthrough blocks and
3119  // the post-dominating block, and the non-fallthroughs must only have one
3120  // predecessor.
3121  auto HasOnePredAndOneSucc = [](BasicBlock *BB, BasicBlock *P, BasicBlock *S) {
3122  return BB->getSinglePredecessor() == P && BB->getSingleSuccessor() == S;
3123  };
3124  if (!HasOnePredAndOneSucc(PFB, PBI->getParent(), QBI->getParent()) ||
3125  !HasOnePredAndOneSucc(QFB, QBI->getParent(), PostBB))
3126  return false;
3127  if ((PTB && !HasOnePredAndOneSucc(PTB, PBI->getParent(), QBI->getParent())) ||
3128  (QTB && !HasOnePredAndOneSucc(QTB, QBI->getParent(), PostBB)))
3129  return false;
3130  if (!QBI->getParent()->hasNUses(2))
3131  return false;
3132 
3133  // OK, this is a sequence of two diamonds or triangles.
3134  // Check if there are stores in PTB or PFB that are repeated in QTB or QFB.
3135  SmallPtrSet<Value *, 4> PStoreAddresses, QStoreAddresses;
3136  for (auto *BB : {PTB, PFB}) {
3137  if (!BB)
3138  continue;
3139  for (auto &I : *BB)
3140  if (StoreInst *SI = dyn_cast<StoreInst>(&I))
3141  PStoreAddresses.insert(SI->getPointerOperand());
3142  }
3143  for (auto *BB : {QTB, QFB}) {
3144  if (!BB)
3145  continue;
3146  for (auto &I : *BB)
3147  if (StoreInst *SI = dyn_cast<StoreInst>(&I))
3148  QStoreAddresses.insert(SI->getPointerOperand());
3149  }
3150 
3151  set_intersect(PStoreAddresses, QStoreAddresses);
3152  // set_intersect mutates PStoreAddresses in place. Rename it here to make it
3153  // clear what it contains.
3154  auto &CommonAddresses = PStoreAddresses;
3155 
3156  bool Changed = false;
3157  for (auto *Address : CommonAddresses)
3158  Changed |= mergeConditionalStoreToAddress(
3159  PTB, PFB, QTB, QFB, PostBB, Address, InvertPCond, InvertQCond, DL);
3160  return Changed;
3161 }
3162 
3163 /// If we have a conditional branch as a predecessor of another block,
3164 /// this function tries to simplify it. We know
3165 /// that PBI and BI are both conditional branches, and BI is in one of the
3166 /// successor blocks of PBI - PBI branches to BI.
3168  const DataLayout &DL) {
3169  assert(PBI->isConditional() && BI->isConditional());
3170  BasicBlock *BB = BI->getParent();
3171 
3172  // If this block ends with a branch instruction, and if there is a
3173  // predecessor that ends on a branch of the same condition, make
3174  // this conditional branch redundant.
3175  if (PBI->getCondition() == BI->getCondition() &&
3176  PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
3177  // Okay, the outcome of this conditional branch is statically
3178  // knowable. If this block had a single pred, handle specially.
3179  if (BB->getSinglePredecessor()) {
3180  // Turn this into a branch on constant.
3181  bool CondIsTrue = PBI->getSuccessor(0) == BB;
3182  BI->setCondition(
3183  ConstantInt::get(Type::getInt1Ty(BB->getContext()), CondIsTrue));
3184  return true; // Nuke the branch on constant.
3185  }
3186 
3187  // Otherwise, if there are multiple predecessors, insert a PHI that merges
3188  // in the constant and simplify the block result. Subsequent passes of
3189  // simplifycfg will thread the block.
3191  pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
3192  PHINode *NewPN = PHINode::Create(
3193  Type::getInt1Ty(BB->getContext()), std::distance(PB, PE),
3194  BI->getCondition()->getName() + ".pr", &BB->front());
3195  // Okay, we're going to insert the PHI node. Since PBI is not the only
3196  // predecessor, compute the PHI'd conditional value for all of the preds.
3197  // Any predecessor where the condition is not computable we keep symbolic.
3198  for (pred_iterator PI = PB; PI != PE; ++PI) {
3199  BasicBlock *P = *PI;
3200  if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) && PBI != BI &&
3201  PBI->isConditional() && PBI->getCondition() == BI->getCondition() &&
3202  PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
3203  bool CondIsTrue = PBI->getSuccessor(0) == BB;
3204  NewPN->addIncoming(
3205  ConstantInt::get(Type::getInt1Ty(BB->getContext()), CondIsTrue),
3206  P);
3207  } else {
3208  NewPN->addIncoming(BI->getCondition(), P);
3209  }
3210  }
3211 
3212  BI->setCondition(NewPN);
3213  return true;
3214  }
3215  }
3216 
3217  if (auto *CE = dyn_cast<ConstantExpr>(BI->getCondition()))
3218  if (CE->canTrap())
3219  return false;
3220 
3221  // If both branches are conditional and both contain stores to the same
3222  // address, remove the stores from the conditionals and create a conditional
3223  // merged store at the end.
3224  if (MergeCondStores && mergeConditionalStores(PBI, BI, DL))
3225  return true;
3226 
3227  // If this is a conditional branch in an empty block, and if any
3228  // predecessors are a conditional branch to one of our destinations,
3229  // fold the conditions into logical ops and one cond br.
3230 
3231  // Ignore dbg intrinsics.
3232  if (&*BB->instructionsWithoutDebug().begin() != BI)
3233  return false;
3234 
3235  int PBIOp, BIOp;
3236  if (PBI->getSuccessor(0) == BI->getSuccessor(0)) {
3237  PBIOp = 0;
3238  BIOp = 0;
3239  } else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) {
3240  PBIOp = 0;
3241  BIOp = 1;
3242  } else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) {
3243  PBIOp = 1;
3244  BIOp = 0;
3245  } else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) {
3246  PBIOp = 1;
3247  BIOp = 1;
3248  } else {
3249  return false;
3250  }
3251 
3252  // Check to make sure that the other destination of this branch
3253  // isn't BB itself. If so, this is an infinite loop that will
3254  // keep getting unwound.
3255  if (PBI->getSuccessor(PBIOp) == BB)
3256  return false;
3257 
3258  // Do not perform this transformation if it would require
3259  // insertion of a large number of select instructions. For targets
3260  // without predication/cmovs, this is a big pessimization.
3261 
3262  // Also do not perform this transformation if any phi node in the common
3263  // destination block can trap when reached by BB or PBB (PR17073). In that
3264  // case, it would be unsafe to hoist the operation into a select instruction.
3265 
3266  BasicBlock *CommonDest = PBI->getSuccessor(PBIOp);
3267  unsigned NumPhis = 0;
3268  for (BasicBlock::iterator II = CommonDest->begin(); isa<PHINode>(II);
3269  ++II, ++NumPhis) {
3270  if (NumPhis > 2) // Disable this xform.
3271  return false;
3272 
3273  PHINode *PN = cast<PHINode>(II);
3274  Value *BIV = PN->getIncomingValueForBlock(BB);
3275  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BIV))
3276  if (CE->canTrap())
3277  return false;
3278 
3279  unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent());
3280  Value *PBIV = PN->getIncomingValue(PBBIdx);
3281  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(PBIV))
3282  if (CE->canTrap())
3283  return false;
3284  }
3285 
3286  // Finally, if everything is ok, fold the branches to logical ops.
3287  BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1);
3288 
3289  LLVM_DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent()
3290  << "AND: " << *BI->getParent());
3291 
3292  // If OtherDest *is* BB, then BB is a basic block with a single conditional
3293  // branch in it, where one edge (OtherDest) goes back to itself but the other
3294  // exits. We don't *know* that the program avoids the infinite loop
3295  // (even though that seems likely). If we do this xform naively, we'll end up
3296  // recursively unpeeling the loop. Since we know that (after the xform is
3297  // done) that the block *is* infinite if reached, we just make it an obviously
3298  // infinite loop with no cond branch.
3299  if (OtherDest == BB) {
3300  // Insert it at the end of the function, because it's either code,
3301  // or it won't matter if it's hot. :)
3302  BasicBlock *InfLoopBlock =
3303  BasicBlock::Create(BB->getContext(), "infloop", BB->getParent());
3304  BranchInst::Create(InfLoopBlock, InfLoopBlock);
3305  OtherDest = InfLoopBlock;
3306  }
3307 
3308  LLVM_DEBUG(dbgs() << *PBI->getParent()->getParent());
3309 
3310  // BI may have other predecessors. Because of this, we leave
3311  // it alone, but modify PBI.
3312 
3313  // Make sure we get to CommonDest on True&True directions.
3314  Value *PBICond = PBI->getCondition();
3315  IRBuilder<NoFolder> Builder(PBI);
3316  if (PBIOp)
3317  PBICond = Builder.CreateNot(PBICond, PBICond->getName() + ".not");
3318 
3319  Value *BICond = BI->getCondition();
3320  if (BIOp)
3321  BICond = Builder.CreateNot(BICond, BICond->getName() + ".not");
3322 
3323  // Merge the conditions.
3324  Value *Cond = Builder.CreateOr(PBICond, BICond, "brmerge");
3325 
3326  // Modify PBI to branch on the new condition to the new dests.
3327  PBI->setCondition(Cond);
3328  PBI->setSuccessor(0, CommonDest);
3329  PBI->setSuccessor(1, OtherDest);
3330 
3331  // Update branch weight for PBI.
3332  uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
3333  uint64_t PredCommon, PredOther, SuccCommon, SuccOther;
3334  bool HasWeights =
3335  extractPredSuccWeights(PBI, BI, PredTrueWeight, PredFalseWeight,
3336  SuccTrueWeight, SuccFalseWeight);
3337  if (HasWeights) {
3338  PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
3339  PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
3340  SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
3341  SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
3342  // The weight to CommonDest should be PredCommon * SuccTotal +
3343  // PredOther * SuccCommon.
3344  // The weight to OtherDest should be PredOther * SuccOther.
3345  uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther) +
3346  PredOther * SuccCommon,
3347  PredOther * SuccOther};
3348  // Halve the weights if any of them cannot fit in an uint32_t
3349  FitWeights(NewWeights);
3350 
3351  setBranchWeights(PBI, NewWeights[0], NewWeights[1]);
3352  }
3353 
3354  // OtherDest may have phi nodes. If so, add an entry from PBI's
3355  // block that are identical to the entries for BI's block.
3356  AddPredecessorToBlock(OtherDest, PBI->getParent(), BB);
3357 
3358  // We know that the CommonDest already had an edge from PBI to
3359  // it. If it has PHIs though, the PHIs may have different
3360  // entries for BB and PBI's BB. If so, insert a select to make
3361  // them agree.
3362  for (PHINode &PN : CommonDest->phis()) {
3363  Value *BIV = PN.getIncomingValueForBlock(BB);
3364  unsigned PBBIdx = PN.getBasicBlockIndex(PBI->getParent());
3365  Value *PBIV = PN.getIncomingValue(PBBIdx);
3366  if (BIV != PBIV) {
3367  // Insert a select in PBI to pick the right value.
3368  SelectInst *NV = cast<SelectInst>(
3369  Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName() + ".mux"));
3370  PN.setIncomingValue(PBBIdx, NV);
3371  // Although the select has the same condition as PBI, the original branch
3372  // weights for PBI do not apply to the new select because the select's
3373  // 'logical' edges are incoming edges of the phi that is eliminated, not
3374  // the outgoing edges of PBI.
3375  if (HasWeights) {
3376  uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight;
3377  uint64_t PredOther = PBIOp ? PredTrueWeight : PredFalseWeight;
3378  uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight;
3379  uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight;
3380  // The weight to PredCommonDest should be PredCommon * SuccTotal.
3381  // The weight to PredOtherDest should be PredOther * SuccCommon.
3382  uint64_t NewWeights[2] = {PredCommon * (SuccCommon + SuccOther),
3383  PredOther * SuccCommon};
3384 
3385  FitWeights(NewWeights);
3386 
3387  setBranchWeights(NV, NewWeights[0], NewWeights[1]);
3388  }
3389  }
3390  }
3391 
3392  LLVM_DEBUG(dbgs() << "INTO: " << *PBI->getParent());
3393  LLVM_DEBUG(dbgs() << *PBI->getParent()->getParent());
3394 
3395  // This basic block is probably dead. We know it has at least
3396  // one fewer predecessor.
3397  return true;
3398 }
3399 
3400 // Simplifies a terminator by replacing it with a branch to TrueBB if Cond is
3401 // true or to FalseBB if Cond is false.
3402 // Takes care of updating the successors and removing the old terminator.
3403 // Also makes sure not to introduce new successors by assuming that edges to
3404 // non-successor TrueBBs and FalseBBs aren't reachable.
3406  BasicBlock *TrueBB, BasicBlock *FalseBB,
3407  uint32_t TrueWeight,
3408  uint32_t FalseWeight) {
3409  // Remove any superfluous successor edges from the CFG.
3410  // First, figure out which successors to preserve.
3411  // If TrueBB and FalseBB are equal, only try to preserve one copy of that
3412  // successor.
3413  BasicBlock *KeepEdge1 = TrueBB;
3414  BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : nullptr;
3415 
3416  // Then remove the rest.
3417  for (BasicBlock *Succ : OldTerm->successors()) {
3418  // Make sure only to keep exactly one copy of each edge.
3419  if (Succ == KeepEdge1)
3420  KeepEdge1 = nullptr;
3421  else if (Succ == KeepEdge2)
3422  KeepEdge2 = nullptr;
3423  else
3424  Succ->removePredecessor(OldTerm->getParent(),
3425  /*DontDeleteUselessPHIs=*/true);
3426  }
3427 
3428  IRBuilder<> Builder(OldTerm);
3429  Builder.SetCurrentDebugLocation(OldTerm->getDebugLoc());
3430 
3431  // Insert an appropriate new terminator.
3432  if (!KeepEdge1 && !KeepEdge2) {
3433  if (TrueBB == FalseBB)
3434  // We were only looking for one successor, and it was present.
3435  // Create an unconditional branch to it.
3436  Builder.CreateBr(TrueBB);
3437  else {
3438  // We found both of the successors we were looking for.
3439  // Create a conditional branch sharing the condition of the select.
3440  BranchInst *NewBI = Builder.CreateCondBr(Cond, TrueBB, FalseBB);
3441  if (TrueWeight != FalseWeight)
3442  setBranchWeights(NewBI, TrueWeight, FalseWeight);
3443  }
3444  } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
3445  // Neither of the selected blocks were successors, so this
3446  // terminator must be unreachable.
3447  new UnreachableInst(OldTerm->getContext(), OldTerm);
3448  } else {
3449  // One of the selected values was a successor, but the other wasn't.
3450  // Insert an unconditional branch to the one that was found;
3451  // the edge to the one that wasn't must be unreachable.
3452  if (!KeepEdge1)
3453  // Only TrueBB was found.
3454  Builder.CreateBr(TrueBB);
3455  else
3456  // Only FalseBB was found.
3457  Builder.CreateBr(FalseBB);
3458  }
3459 
3461  return true;
3462 }
3463 
3464 // Replaces
3465 // (switch (select cond, X, Y)) on constant X, Y
3466 // with a branch - conditional if X and Y lead to distinct BBs,
3467 // unconditional otherwise.
3469  // Check for constant integer values in the select.
3470  ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue());
3471  ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue());
3472  if (!TrueVal || !FalseVal)
3473  return false;
3474 
3475  // Find the relevant condition and destinations.
3476  Value *Condition = Select->getCondition();
3477  BasicBlock *TrueBB = SI->findCaseValue(TrueVal)->getCaseSuccessor();
3478  BasicBlock *FalseBB = SI->findCaseValue(FalseVal)->getCaseSuccessor();
3479 
3480  // Get weight for TrueBB and FalseBB.
3481  uint32_t TrueWeight = 0, FalseWeight = 0;
3482  SmallVector<uint64_t, 8> Weights;
3483  bool HasWeights = HasBranchWeights(SI);
3484  if (HasWeights) {
3485  GetBranchWeights(SI, Weights);
3486  if (Weights.size() == 1 + SI->getNumCases()) {
3487  TrueWeight =
3488  (uint32_t)Weights[SI->findCaseValue(TrueVal)->getSuccessorIndex()];
3489  FalseWeight =
3490  (uint32_t)Weights[SI->findCaseValue(FalseVal)->getSuccessorIndex()];
3491  }
3492  }
3493 
3494  // Perform the actual simplification.
3495  return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
3496  FalseWeight);
3497 }
3498 
3499 // Replaces
3500 // (indirectbr (select cond, blockaddress(@fn, BlockA),
3501 // blockaddress(@fn, BlockB)))
3502 // with
3503 // (br cond, BlockA, BlockB).
3505  // Check that both operands of the select are block addresses.
3508  if (!TBA || !FBA)
3509  return false;
3510 
3511  // Extract the actual blocks.
3512  BasicBlock *TrueBB = TBA->getBasicBlock();
3513  BasicBlock *FalseBB = FBA->getBasicBlock();
3514 
3515  // Perform the actual simplification.
3516  return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB, 0,
3517  0);
3518 }
3519 
3520 /// This is called when we find an icmp instruction
3521 /// (a seteq/setne with a constant) as the only instruction in a
3522 /// block that ends with an uncond branch. We are looking for a very specific
3523 /// pattern that occurs when "A == 1 || A == 2 || A == 3" gets simplified. In
3524 /// this case, we merge the first two "or's of icmp" into a switch, but then the
3525 /// default value goes to an uncond block with a seteq in it, we get something
3526 /// like:
3527 ///
3528 /// switch i8 %A, label %DEFAULT [ i8 1, label %end i8 2, label %end ]
3529 /// DEFAULT:
3530 /// %tmp = icmp eq i8 %A, 92
3531 /// br label %end
3532 /// end:
3533 /// ... = phi i1 [ true, %entry ], [ %tmp, %DEFAULT ], [ true, %entry ]
3534 ///
3535 /// We prefer to split the edge to 'end' so that there is a true/false entry to
3536 /// the PHI, merging the third icmp into the switch.
3538  ICmpInst *ICI, IRBuilder<> &Builder, const DataLayout &DL,
3539  const TargetTransformInfo &TTI, const SimplifyCFGOptions &Options) {
3540  BasicBlock *BB = ICI->getParent();
3541 
3542  // If the block has any PHIs in it or the icmp has multiple uses, it is too
3543  // complex.
3544  if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse())
3545  return false;
3546 
3547  Value *V = ICI->getOperand(0);
3548  ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1));
3549 
3550  // The pattern we're looking for is where our only predecessor is a switch on
3551  // 'V' and this block is the default case for the switch. In this case we can
3552  // fold the compared value into the switch to simplify things.
3553  BasicBlock *Pred = BB->getSinglePredecessor();
3554  if (!Pred || !isa<SwitchInst>(Pred->getTerminator()))
3555  return false;
3556 
3557  SwitchInst *SI = cast<SwitchInst>(Pred->getTerminator());
3558  if (SI->getCondition() != V)
3559  return false;
3560 
3561  // If BB is reachable on a non-default case, then we simply know the value of
3562  // V in this block. Substitute it and constant fold the icmp instruction
3563  // away.
3564  if (SI->getDefaultDest() != BB) {
3565  ConstantInt *VVal = SI->findCaseDest(BB);
3566  assert(VVal && "Should have a unique destination value");
3567  ICI->setOperand(0, VVal);
3568 
3569  if (Value *V = SimplifyInstruction(ICI, {DL, ICI})) {
3570  ICI->replaceAllUsesWith(V);
3571  ICI->eraseFromParent();
3572  }
3573  // BB is now empty, so it is likely to simplify away.
3574  return simplifyCFG(BB, TTI, Options) | true;
3575  }
3576 
3577  // Ok, the block is reachable from the default dest. If the constant we're
3578  // comparing exists in one of the other edges, then we can constant fold ICI
3579  // and zap it.
3580  if (SI->findCaseValue(Cst) != SI->case_default()) {
3581  Value *V;
3582  if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
3583  V = ConstantInt::getFalse(BB->getContext());
3584  else
3585  V = ConstantInt::getTrue(BB->getContext());
3586 
3587  ICI->replaceAllUsesWith(V);
3588  ICI->eraseFromParent();
3589  // BB is now empty, so it is likely to simplify away.
3590  return simplifyCFG(BB, TTI, Options) | true;
3591  }
3592 
3593  // The use of the icmp has to be in the 'end' block, by the only PHI node in
3594  // the block.
3595  BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0);
3596  PHINode *PHIUse = dyn_cast<PHINode>(ICI->user_back());
3597  if (PHIUse == nullptr || PHIUse != &SuccBlock->front() ||
3598  isa<PHINode>(++BasicBlock::iterator(PHIUse)))
3599  return false;
3600 
3601  // If the icmp is a SETEQ, then the default dest gets false, the new edge gets
3602  // true in the PHI.
3603  Constant *DefaultCst = ConstantInt::getTrue(BB->getContext());
3604  Constant *NewCst = ConstantInt::getFalse(BB->getContext());
3605 
3606  if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
3607  std::swap(DefaultCst, NewCst);
3608 
3609  // Replace ICI (which is used by the PHI for the default value) with true or
3610  // false depending on if it is EQ or NE.
3611  ICI->replaceAllUsesWith(DefaultCst);
3612  ICI->eraseFromParent();
3613 
3614  // Okay, the switch goes to this block on a default value. Add an edge from
3615  // the switch to the merge point on the compared value.
3616  BasicBlock *NewBB =
3617  BasicBlock::Create(BB->getContext(), "switch.edge", BB->getParent(), BB);
3618  SmallVector<uint64_t, 8> Weights;
3619  bool HasWeights = HasBranchWeights(SI);
3620  if (HasWeights) {
3621  GetBranchWeights(SI, Weights);
3622  if (Weights.size() == 1 + SI->getNumCases()) {
3623  // Split weight for default case to case for "Cst".
3624  Weights[0] = (Weights[0] + 1) >> 1;
3625  Weights.push_back(Weights[0]);
3626 
3627  SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
3628  setBranchWeights(SI, MDWeights);
3629  }
3630  }
3631  SI->addCase(Cst, NewBB);
3632 
3633  // NewBB branches to the phi block, add the uncond branch and the phi entry.
3634  Builder.SetInsertPoint(NewBB);
3635  Builder.SetCurrentDebugLocation(SI->getDebugLoc());
3636  Builder.CreateBr(SuccBlock);
3637  PHIUse->addIncoming(NewCst, NewBB);
3638  return true;
3639 }
3640 
3641 /// The specified branch is a conditional branch.
3642 /// Check to see if it is branching on an or/and chain of icmp instructions, and
3643 /// fold it into a switch instruction if so.
3645  const DataLayout &DL) {
3646  Instruction *Cond = dyn_cast<Instruction>(BI->getCondition());
3647  if (!Cond)
3648  return false;
3649 
3650  // Change br (X == 0 | X == 1), T, F into a switch instruction.
3651  // If this is a bunch of seteq's or'd together, or if it's a bunch of
3652  // 'setne's and'ed together, collect them.
3653 
3654  // Try to gather values from a chain of and/or to be turned into a switch
3655  ConstantComparesGatherer ConstantCompare(Cond, DL);
3656  // Unpack the result
3657  SmallVectorImpl<ConstantInt *> &Values = ConstantCompare.Vals;
3658  Value *CompVal = ConstantCompare.CompValue;
3659  unsigned UsedICmps = ConstantCompare.UsedICmps;
3660  Value *ExtraCase = ConstantCompare.Extra;
3661 
3662  // If we didn't have a multiply compared value, fail.
3663  if (!CompVal)
3664  return false;
3665 
3666  // Avoid turning single icmps into a switch.
3667  if (UsedICmps <= 1)
3668  return false;
3669 
3670  bool TrueWhenEqual = (Cond->getOpcode() == Instruction::Or);
3671 
3672  // There might be duplicate constants in the list, which the switch
3673  // instruction can't handle, remove them now.
3674  array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate);
3675  Values.erase(std::unique(Values.begin(), Values.end()), Values.end());
3676 
3677  // If Extra was used, we require at least two switch values to do the
3678  // transformation. A switch with one value is just a conditional branch.
3679  if (ExtraCase && Values.size() < 2)
3680  return false;
3681 
3682  // TODO: Preserve branch weight metadata, similarly to how
3683  // FoldValueComparisonIntoPredecessors preserves it.
3684 
3685  // Figure out which block is which destination.
3686  BasicBlock *DefaultBB = BI->getSuccessor(1);
3687  BasicBlock *EdgeBB = BI->getSuccessor(0);
3688  if (!TrueWhenEqual)
3689  std::swap(DefaultBB, EdgeBB);
3690 
3691  BasicBlock *BB = BI->getParent();
3692 
3693  LLVM_DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size()
3694  << " cases into SWITCH. BB is:\n"
3695  << *BB);
3696 
3697  // If there are any extra values that couldn't be folded into the switch
3698  // then we evaluate them with an explicit branch first. Split the block
3699  // right before the condbr to handle it.
3700  if (ExtraCase) {
3701  BasicBlock *NewBB =
3702  BB->splitBasicBlock(BI->getIterator(), "switch.early.test");
3703  // Remove the uncond branch added to the old block.
3704  TerminatorInst *OldTI = BB->getTerminator();
3705  Builder.SetInsertPoint(OldTI);
3706 
3707  if (TrueWhenEqual)
3708  Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB);
3709  else
3710  Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB);
3711 
3712  OldTI->eraseFromParent();
3713 
3714  // If there are PHI nodes in EdgeBB, then we need to add a new entry to them
3715  // for the edge we just added.
3716  AddPredecessorToBlock(EdgeBB, BB, NewBB);
3717 
3718  LLVM_DEBUG(dbgs() << " ** 'icmp' chain unhandled condition: " << *ExtraCase
3719  << "\nEXTRABB = " << *BB);
3720  BB = NewBB;
3721  }
3722 
3723  Builder.SetInsertPoint(BI);
3724  // Convert pointer to int before we switch.
3725  if (CompVal->getType()->isPointerTy()) {
3726  CompVal = Builder.CreatePtrToInt(
3727  CompVal, DL.getIntPtrType(CompVal->getType()), "magicptr");
3728  }
3729 
3730  // Create the new switch instruction now.
3731  SwitchInst *New = Builder.CreateSwitch(CompVal, DefaultBB, Values.size());
3732 
3733  // Add all of the 'cases' to the switch instruction.
3734  for (unsigned i = 0, e = Values.size(); i != e; ++i)
3735  New->addCase(Values[i], EdgeBB);
3736 
3737  // We added edges from PI to the EdgeBB. As such, if there were any
3738  // PHI nodes in EdgeBB, they need entries to be added corresponding to
3739  // the number of edges added.
3740  for (BasicBlock::iterator BBI = EdgeBB->begin(); isa<PHINode>(BBI); ++BBI) {
3741  PHINode *PN = cast<PHINode>(BBI);
3742  Value *InVal = PN->getIncomingValueForBlock(BB);
3743  for (unsigned i = 0, e = Values.size() - 1; i != e; ++i)
3744  PN->addIncoming(InVal, BB);
3745  }
3746 
3747  // Erase the old branch instruction.
3749 
3750  LLVM_DEBUG(dbgs() << " ** 'icmp' chain result is:\n" << *BB << '\n');
3751  return true;
3752 }
3753 
3754 bool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) {
3755  if (isa<PHINode>(RI->getValue()))
3756  return SimplifyCommonResume(RI);
3757  else if (isa<LandingPadInst>(RI->getParent()->getFirstNonPHI()) &&
3758  RI->getValue() == RI->getParent()->getFirstNonPHI())
3759  // The resume must unwind the exception that caused control to branch here.
3760  return SimplifySingleResume(RI);
3761 
3762  return false;
3763 }
3764 
3765 // Simplify resume that is shared by several landing pads (phi of landing pad).
3766 bool SimplifyCFGOpt::SimplifyCommonResume(ResumeInst *RI) {
3767  BasicBlock *BB = RI->getParent();
3768 
3769  // Check that there are no other instructions except for debug intrinsics
3770  // between the phi of landing pads (RI->getValue()) and resume instruction.
3771  BasicBlock::iterator I = cast<Instruction>(RI->getValue())->getIterator(),
3772  E = RI->getIterator();
3773  while (++I != E)
3774  if (!isa<DbgInfoIntrinsic>(I))
3775  return false;
3776 
3777  SmallSetVector<BasicBlock *, 4> TrivialUnwindBlocks;
3778  auto *PhiLPInst = cast<PHINode>(RI->getValue());
3779 
3780  // Check incoming blocks to see if any of them are trivial.
3781  for (unsigned Idx = 0, End = PhiLPInst->getNumIncomingValues(); Idx != End;
3782  Idx++) {
3783  auto *IncomingBB = PhiLPInst->getIncomingBlock(Idx);
3784  auto *IncomingValue = PhiLPInst->getIncomingValue(Idx);
3785 
3786  // If the block has other successors, we can not delete it because
3787  // it has other dependents.
3788  if (IncomingBB->getUniqueSuccessor() != BB)
3789  continue;
3790 
3791  auto *LandingPad = dyn_cast<LandingPadInst>(IncomingBB->getFirstNonPHI());
3792  // Not the landing pad that caused the control to branch here.
3793  if (IncomingValue != LandingPad)
3794  continue;
3795 
3796  bool isTrivial = true;
3797 
3798  I = IncomingBB->getFirstNonPHI()->getIterator();
3799  E = IncomingBB->getTerminator()->getIterator();
3800  while (++I != E)
3801  if (!isa<DbgInfoIntrinsic>(I)) {
3802  isTrivial = false;
3803  break;
3804  }
3805 
3806  if (isTrivial)
3807  TrivialUnwindBlocks.insert(IncomingBB);
3808  }
3809 
3810  // If no trivial unwind blocks, don't do any simplifications.
3811  if (TrivialUnwindBlocks.empty())
3812  return false;
3813 
3814  // Turn all invokes that unwind here into calls.
3815  for (auto *TrivialBB : TrivialUnwindBlocks) {
3816  // Blocks that will be simplified should be removed from the phi node.
3817  // Note there could be multiple edges to the resume block, and we need
3818  // to remove them all.
3819  while (PhiLPInst->getBasicBlockIndex(TrivialBB) != -1)
3820  BB->removePredecessor(TrivialBB, true);
3821 
3822  for (pred_iterator PI = pred_begin(TrivialBB), PE = pred_end(TrivialBB);
3823  PI != PE;) {
3824  BasicBlock *Pred = *PI++;
3825  removeUnwindEdge(Pred);
3826  }
3827 
3828  // In each SimplifyCFG run, only the current processed block can be erased.
3829  // Otherwise, it will break the iteration of SimplifyCFG pass. So instead
3830  // of erasing TrivialBB, we only remove the branch to the common resume
3831  // block so that we can later erase the resume block since it has no
3832  // predecessors.
3833  TrivialBB->getTerminator()->eraseFromParent();
3834  new UnreachableInst(RI->getContext(), TrivialBB);
3835  }
3836 
3837  // Delete the resume block if all its predecessors have been removed.
3838  if (pred_empty(BB))
3839  BB->eraseFromParent();
3840 
3841  return !TrivialUnwindBlocks.empty();
3842 }
3843 
3844 // Simplify resume that is only used by a single (non-phi) landing pad.
3845 bool SimplifyCFGOpt::SimplifySingleResume(ResumeInst *RI) {
3846  BasicBlock *BB = RI->getParent();
3848  assert(RI->getValue() == LPInst &&
3849  "Resume must unwind the exception that caused control to here");
3850 
3851  // Check that there are no other instructions except for debug intrinsics.
3852  BasicBlock::iterator I = LPInst->getIterator(), E = RI->getIterator();
3853  while (++I != E)
3854  if (!isa<DbgInfoIntrinsic>(I))
3855  return false;
3856 
3857  // Turn all invokes that unwind here into calls and delete the basic block.
3858  for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) {
3859  BasicBlock *Pred = *PI++;
3860  removeUnwindEdge(Pred);
3861  }
3862 
3863  // The landingpad is now unreachable. Zap it.
3864  BB->eraseFromParent();
3865  if (LoopHeaders)
3866  LoopHeaders->erase(BB);
3867  return true;
3868 }
3869 
3871  // If this is a trivial cleanup pad that executes no instructions, it can be
3872  // eliminated. If the cleanup pad continues to the caller, any predecessor
3873  // that is an EH pad will be updated to continue to the caller and any
3874  // predecessor that terminates with an invoke instruction will have its invoke
3875  // instruction converted to a call instruction. If the cleanup pad being
3876  // simplified does not continue to the caller, each predecessor will be
3877  // updated to continue to the unwind destination of the cleanup pad being
3878  // simplified.
3879  BasicBlock *BB = RI->getParent();
3880  CleanupPadInst *CPInst = RI->getCleanupPad();
3881  if (CPInst->getParent() != BB)
3882  // This isn't an empty cleanup.
3883  return false;
3884 
3885  // We cannot kill the pad if it has multiple uses. This typically arises
3886  // from unreachable basic blocks.
3887  if (!CPInst->hasOneUse())
3888  return false;
3889 
3890  // Check that there are no other instructions except for benign intrinsics.
3891  BasicBlock::iterator I = CPInst->getIterator(), E = RI->getIterator();
3892  while (++I != E) {
3893  auto *II = dyn_cast<IntrinsicInst>(I);
3894  if (!II)
3895  return false;
3896 
3897  Intrinsic::ID IntrinsicID = II->getIntrinsicID();
3898  switch (IntrinsicID) {
3899  case Intrinsic::dbg_declare:
3900  case Intrinsic::dbg_value:
3901  case Intrinsic::dbg_label:
3902  case Intrinsic::lifetime_end:
3903  break;
3904  default:
3905  return false;
3906  }
3907  }
3908 
3909  // If the cleanup return we are simplifying unwinds to the caller, this will
3910  // set UnwindDest to nullptr.
3911  BasicBlock *UnwindDest = RI->getUnwindDest();
3912  Instruction *DestEHPad = UnwindDest ? UnwindDest->getFirstNonPHI() : nullptr;
3913 
3914  // We're about to remove BB from the control flow. Before we do, sink any
3915  // PHINodes into the unwind destination. Doing this before changing the
3916  // control flow avoids some potentially slow checks, since we can currently
3917  // be certain that UnwindDest and BB have no common predecessors (since they
3918  // are both EH pads).
3919  if (UnwindDest) {
3920  // First, go through the PHI nodes in UnwindDest and update any nodes that
3921  // reference the block we are removing
3922  for (BasicBlock::iterator I = UnwindDest->begin(),
3923  IE = DestEHPad->getIterator();
3924  I != IE; ++I) {
3925  PHINode *DestPN = cast<PHINode>(I);
3926 
3927  int Idx = DestPN->getBasicBlockIndex(BB);
3928  // Since BB unwinds to UnwindDest, it has to be in the PHI node.
3929  assert(Idx != -1);
3930  // This PHI node has an incoming value that corresponds to a control
3931  // path through the cleanup pad we are removing. If the incoming
3932  // value is in the cleanup pad, it must be a PHINode (because we
3933  // verified above that the block is otherwise empty). Otherwise, the
3934  // value is either a constant or a value that dominates the cleanup
3935  // pad being removed.
3936  //
3937  // Because BB and UnwindDest are both EH pads, all of their
3938  // predecessors must unwind to these blocks, and since no instruction
3939  // can have multiple unwind destinations, there will be no overlap in
3940  // incoming blocks between SrcPN and DestPN.
3941  Value *SrcVal = DestPN->getIncomingValue(Idx);
3942  PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
3943 
3944  // Remove the entry for the block we are deleting.
3945  DestPN->removeIncomingValue(Idx, false);
3946 
3947  if (SrcPN && SrcPN->getParent() == BB) {
3948  // If the incoming value was a PHI node in the cleanup pad we are
3949  // removing, we need to merge that PHI node's incoming values into
3950  // DestPN.
3951  for (unsigned SrcIdx = 0, SrcE = SrcPN->getNumIncomingValues();
3952  SrcIdx != SrcE; ++SrcIdx) {
3953  DestPN->addIncoming(SrcPN->getIncomingValue(SrcIdx),
3954  SrcPN->getIncomingBlock(SrcIdx));
3955  }
3956  } else {
3957  // Otherwise, the incoming value came from above BB and
3958  // so we can just reuse it. We must associate all of BB's
3959  // predecessors with this value.
3960  for (auto *pred : predecessors(BB)) {
3961  DestPN->addIncoming(SrcVal, pred);
3962  }
3963  }
3964  }
3965 
3966  // Sink any remaining PHI nodes directly into UnwindDest.
3967  Instruction *InsertPt = DestEHPad;
3968  for (BasicBlock::iterator I = BB->begin(),
3969  IE = BB->getFirstNonPHI()->getIterator();
3970  I != IE;) {
3971  // The iterator must be incremented here because the instructions are
3972  // being moved to another block.
3973  PHINode *PN = cast<PHINode>(I++);
3974  if (PN->use_empty())
3975  // If the PHI node has no uses, just leave it. It will be erased
3976  // when we erase BB below.
3977  continue;
3978 
3979  // Otherwise, sink this PHI node into UnwindDest.
3980  // Any predecessors to UnwindDest which are not already represented
3981  // must be back edges which inherit the value from the path through
3982  // BB. In this case, the PHI value must reference itself.
3983  for (auto *pred : predecessors(UnwindDest))
3984  if (pred != BB)
3985  PN->addIncoming(PN, pred);
3986  PN->moveBefore(InsertPt);
3987  }
3988  }
3989 
3990  for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) {
3991  // The iterator must be updated here because we are removing this pred.
3992  BasicBlock *PredBB = *PI++;
3993  if (UnwindDest == nullptr) {
3994  removeUnwindEdge(PredBB);
3995  } else {
3996  TerminatorInst *TI = PredBB->getTerminator();
3997  TI->replaceUsesOfWith(BB, UnwindDest);
3998  }
3999  }
4000 
4001  // The cleanup pad is now unreachable. Zap it.
4002  BB->eraseFromParent();
4003  return true;
4004 }
4005 
4006 // Try to merge two cleanuppads together.
4008  // Skip any cleanuprets which unwind to caller, there is nothing to merge
4009  // with.
4010  BasicBlock *UnwindDest = RI->getUnwindDest();
4011  if (!UnwindDest)
4012  return false;
4013 
4014  // This cleanupret isn't the only predecessor of this cleanuppad, it wouldn't
4015  // be safe to merge without code duplication.
4016  if (UnwindDest->getSinglePredecessor() != RI->getParent())
4017  return false;
4018 
4019  // Verify that our cleanuppad's unwind destination is another cleanuppad.
4020  auto *SuccessorCleanupPad = dyn_cast<CleanupPadInst>(&UnwindDest->front());
4021  if (!SuccessorCleanupPad)
4022  return false;
4023 
4024  CleanupPadInst *PredecessorCleanupPad = RI->getCleanupPad();
4025  // Replace any uses of the successor cleanupad with the predecessor pad
4026  // The only cleanuppad uses should be this cleanupret, it's cleanupret and
4027  // funclet bundle operands.
4028  SuccessorCleanupPad->replaceAllUsesWith(PredecessorCleanupPad);
4029  // Remove the old cleanuppad.
4030  SuccessorCleanupPad->eraseFromParent();
4031  // Now, we simply replace the cleanupret with a branch to the unwind
4032  // destination.
4033  BranchInst::Create(UnwindDest, RI->getParent());
4034  RI->eraseFromParent();
4035 
4036  return true;
4037 }
4038 
4039 bool SimplifyCFGOpt::SimplifyCleanupReturn(CleanupReturnInst *RI) {
4040  // It is possible to transiantly have an undef cleanuppad operand because we
4041  // have deleted some, but not all, dead blocks.
4042  // Eventually, this block will be deleted.
4043  if (isa<UndefValue>(RI->getOperand(0)))
4044  return false;
4045 
4046  if (mergeCleanupPad(RI))
4047  return true;
4048 
4049  if (removeEmptyCleanup(RI))
4050  return true;
4051 
4052  return false;
4053 }
4054 
4055 bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) {
4056  BasicBlock *BB = RI->getParent();
4057  if (!BB->getFirstNonPHIOrDbg()->isTerminator())
4058  return false;
4059 
4060  // Find predecessors that end with branches.
4061  SmallVector<BasicBlock *, 8> UncondBranchPreds;
4062  SmallVector<BranchInst *, 8> CondBranchPreds;
4063  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
4064  BasicBlock *P = *PI;
4065  TerminatorInst *PTI = P->getTerminator();
4066  if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) {
4067  if (BI->isUnconditional())
4068  UncondBranchPreds.push_back(P);
4069  else
4070  CondBranchPreds.push_back(BI);
4071  }
4072  }
4073 
4074  // If we found some, do the transformation!
4075  if (!UncondBranchPreds.empty() && DupRet) {
4076  while (!UncondBranchPreds.empty()) {
4077  BasicBlock *Pred = UncondBranchPreds.pop_back_val();
4078  LLVM_DEBUG(dbgs() << "FOLDING: " << *BB
4079  << "INTO UNCOND BRANCH PRED: " << *Pred);
4080  (void)FoldReturnIntoUncondBranch(RI, BB, Pred);
4081  }
4082 
4083  // If we eliminated all predecessors of the block, delete the block now.
4084  if (pred_empty(BB)) {
4085  // We know there are no successors, so just nuke the block.
4086  BB->eraseFromParent();
4087  if (LoopHeaders)
4088  LoopHeaders->erase(BB);
4089  }
4090 
4091  return true;
4092  }
4093 
4094  // Check out all of the conditional branches going to this return
4095  // instruction. If any of them just select between returns, change the
4096  // branch itself into a select/return pair.
4097  while (!CondBranchPreds.empty()) {
4098  BranchInst *BI = CondBranchPreds.pop_back_val();
4099 
4100  // Check to see if the non-BB successor is also a return block.
4101  if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) &&
4102  isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) &&
4103  SimplifyCondBranchToTwoReturns(BI, Builder))
4104  return true;
4105  }
4106  return false;
4107 }
4108 
4109 bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) {
4110  BasicBlock *BB = UI->getParent();
4111 
4112  bool Changed = false;
4113 
4114  // If there are any instructions immediately before the unreachable that can
4115  // be removed, do so.
4116  while (UI->getIterator() != BB->begin()) {
4117  BasicBlock::iterator BBI = UI->getIterator();
4118  --BBI;
4119  // Do not delete instructions that can have side effects which might cause
4120  // the unreachable to not be reachable; specifically, calls and volatile
4121  // operations may have this effect.
4122  if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI))
4123  break;
4124 
4125  if (BBI->mayHaveSideEffects()) {
4126  if (auto *SI = dyn_cast<StoreInst>(BBI)) {
4127  if (SI->isVolatile())
4128  break;
4129  } else if (auto *LI = dyn_cast<LoadInst>(BBI)) {
4130  if (LI->isVolatile())
4131  break;
4132  } else if (auto *RMWI = dyn_cast<AtomicRMWInst>(BBI)) {
4133  if (RMWI->isVolatile())
4134  break;
4135  } else if (auto *CXI = dyn_cast<AtomicCmpXchgInst>(BBI)) {
4136  if (CXI->isVolatile())
4137  break;
4138  } else if (isa<CatchPadInst>(BBI)) {
4139  // A catchpad may invoke exception object constructors and such, which
4140  // in some languages can be arbitrary code, so be conservative by
4141  // default.
4142  // For CoreCLR, it just involves a type test, so can be removed.
4145  break;
4146  } else if (!isa<FenceInst>(BBI) && !isa<VAArgInst>(BBI) &&
4147  !isa<LandingPadInst>(BBI)) {
4148  break;
4149  }
4150  // Note that deleting LandingPad's here is in fact okay, although it
4151  // involves a bit of subtle reasoning. If this inst is a LandingPad,
4152  // all the predecessors of this block will be the unwind edges of Invokes,
4153  // and we can therefore guarantee this block will be erased.
4154  }
4155 
4156  // Delete this instruction (any uses are guaranteed to be dead)
4157  if (!BBI->use_empty())
4158  BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
4159  BBI->eraseFromParent();
4160  Changed = true;
4161  }
4162 
4163  // If the unreachable instruction is the first in the block, take a gander
4164  // at all of the predecessors of this instruction, and simplify them.
4165  if (&BB->front() != UI)
4166  return Changed;
4167 
4169  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
4170  TerminatorInst *TI = Preds[i]->getTerminator();
4171  IRBuilder<> Builder(TI);
4172  if (auto *BI = dyn_cast<BranchInst>(TI)) {
4173  if (BI->isUnconditional()) {
4174  if (BI->getSuccessor(0) == BB) {
4175  new UnreachableInst(TI->getContext(), TI);
4176  TI->eraseFromParent();
4177  Changed = true;
4178  }
4179  } else {
4180  if (BI->getSuccessor(0) == BB) {
4181  Builder.CreateBr(BI->getSuccessor(1));
4183  } else if (BI->getSuccessor(1) == BB) {
4184  Builder.CreateBr(BI->getSuccessor(0));
4186  Changed = true;
4187  }
4188  }
4189  } else if (auto *SI = dyn_cast<SwitchInst>(TI)) {
4190  for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
4191  if (i->getCaseSuccessor() != BB) {
4192  ++i;
4193  continue;
4194  }
4195  BB->removePredecessor(SI->getParent());
4196  i = SI->removeCase(i);
4197  e = SI->case_end();
4198  Changed = true;
4199  }
4200  } else if (auto *II = dyn_cast<InvokeInst>(TI)) {
4201  if (II->getUnwindDest() == BB) {
4202  removeUnwindEdge(TI->getParent());
4203  Changed = true;
4204  }
4205  } else if (auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
4206  if (CSI->getUnwindDest() == BB) {
4207  removeUnwindEdge(TI->getParent());
4208  Changed = true;
4209  continue;
4210  }
4211 
4212  for (CatchSwitchInst::handler_iterator I = CSI->handler_begin(),
4213  E = CSI->handler_end();
4214  I != E; ++I) {
4215  if (*I == BB) {
4216  CSI->removeHandler(I);
4217  --I;
4218  --E;
4219  Changed = true;
4220  }
4221  }
4222  if (CSI->getNumHandlers() == 0) {
4223  BasicBlock *CatchSwitchBB = CSI->getParent();
4224  if (CSI->hasUnwindDest()) {
4225  // Redirect preds to the unwind dest
4226  CatchSwitchBB->replaceAllUsesWith(CSI->getUnwindDest());
4227  } else {
4228  // Rewrite all preds to unwind to caller (or from invoke to call).
4229  SmallVector<BasicBlock *, 8> EHPreds(predecessors(CatchSwitchBB));
4230  for (BasicBlock *EHPred : EHPreds)
4231  removeUnwindEdge(EHPred);
4232  }
4233  // The catchswitch is no longer reachable.
4234  new UnreachableInst(CSI->getContext(), CSI);
4235  CSI->eraseFromParent();
4236  Changed = true;
4237  }
4238  } else if (isa<CleanupReturnInst>(TI)) {
4239  new UnreachableInst(TI->getContext(), TI);
4240  TI->eraseFromParent();
4241  Changed = true;
4242  }
4243  }
4244 
4245  // If this block is now dead, remove it.
4246  if (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) {
4247  // We know there are no successors, so just nuke the block.
4248  BB->eraseFromParent();
4249  if (LoopHeaders)
4250  LoopHeaders->erase(BB);
4251  return true;
4252  }
4253 
4254  return Changed;
4255 }
4256 
4258  assert(Cases.size() >= 1);
4259 
4260  array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate);
4261  for (size_t I = 1, E = Cases.size(); I != E; ++I) {
4262  if (Cases[I - 1]->getValue() != Cases[I]->getValue() + 1)
4263  return false;
4264  }
4265  return true;
4266 }
4267 
4268 /// Turn a switch with two reachable destinations into an integer range
4269 /// comparison and branch.
4271  assert(SI->getNumCases() > 1 && "Degenerate switch?");
4272 
4273  bool HasDefault =
4274  !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
4275 
4276  // Partition the cases into two sets with different destinations.
4277  BasicBlock *DestA = HasDefault ? SI->getDefaultDest() : nullptr;
4278  BasicBlock *DestB = nullptr;
4281 
4282  for (auto Case : SI->cases()) {
4283  BasicBlock *Dest = Case.getCaseSuccessor();
4284  if (!DestA)
4285  DestA = Dest;
4286  if (Dest == DestA) {
4287  CasesA.push_back(Case.getCaseValue());
4288  continue;
4289  }
4290  if (!DestB)
4291  DestB = Dest;
4292  if (Dest == DestB) {
4293  CasesB.push_back(Case.getCaseValue());
4294  continue;
4295  }
4296  return false; // More than two destinations.
4297  }
4298 
4299  assert(DestA && DestB &&
4300  "Single-destination switch should have been folded.");
4301  assert(DestA != DestB);
4302  assert(DestB != SI->getDefaultDest());
4303  assert(!CasesB.empty() && "There must be non-default cases.");
4304  assert(!CasesA.empty() || HasDefault);
4305 
4306  // Figure out if one of the sets of cases form a contiguous range.
4307  SmallVectorImpl<ConstantInt *> *ContiguousCases = nullptr;
4308  BasicBlock *ContiguousDest = nullptr;
4309  BasicBlock *OtherDest = nullptr;
4310  if (!CasesA.empty() && CasesAreContiguous(CasesA)) {
4311  ContiguousCases = &CasesA;
4312  ContiguousDest = DestA;
4313  OtherDest = DestB;
4314  } else if (CasesAreContiguous(CasesB)) {
4315  ContiguousCases = &CasesB;
4316  ContiguousDest = DestB;
4317  OtherDest = DestA;
4318  } else
4319  return false;
4320 
4321  // Start building the compare and branch.
4322 
4323  Constant *Offset = ConstantExpr::getNeg(ContiguousCases->back());
4324  Constant *NumCases =
4325  ConstantInt::get(Offset->getType(), ContiguousCases->size());
4326 
4327  Value *Sub = SI->getCondition();
4328  if (!Offset->isNullValue())
4329  Sub = Builder.CreateAdd(Sub, Offset, Sub->getName() + ".off");
4330 
4331  Value *Cmp;
4332  // If NumCases overflowed, then all possible values jump to the successor.
4333  if (NumCases->isNullValue() && !ContiguousCases->empty())
4334  Cmp = ConstantInt::getTrue(SI->getContext());
4335  else
4336  Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch");
4337  BranchInst *NewBI = Builder.CreateCondBr(Cmp, ContiguousDest, OtherDest);
4338 
4339  // Update weight for the newly-created conditional branch.
4340  if (HasBranchWeights(SI)) {
4341  SmallVector<uint64_t, 8> Weights;
4342  GetBranchWeights(SI, Weights);
4343  if (Weights.size() == 1 + SI->getNumCases()) {
4344  uint64_t TrueWeight = 0;
4345  uint64_t FalseWeight = 0;
4346  for (size_t I = 0, E = Weights.size(); I != E; ++I) {
4347  if (SI->getSuccessor(I) == ContiguousDest)
4348  TrueWeight += Weights[I];
4349  else
4350  FalseWeight += Weights[I];
4351  }
4352  while (TrueWeight > UINT32_MAX || FalseWeight > UINT32_MAX) {
4353  TrueWeight /= 2;
4354  FalseWeight /= 2;
4355  }
4356  setBranchWeights(NewBI, TrueWeight, FalseWeight);
4357  }
4358  }
4359 
4360  // Prune obsolete incoming values off the successors' PHI nodes.
4361  for (auto BBI = ContiguousDest->begin(); isa<PHINode>(BBI); ++BBI) {
4362  unsigned PreviousEdges = ContiguousCases->size();
4363  if (ContiguousDest == SI->getDefaultDest())
4364  ++PreviousEdges;
4365  for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I)
4366  cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
4367  }
4368  for (auto BBI = OtherDest->begin(); isa<PHINode>(BBI); ++BBI) {
4369  unsigned PreviousEdges = SI->getNumCases() - ContiguousCases->size();
4370  if (OtherDest == SI->getDefaultDest())
4371  ++PreviousEdges;
4372  for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I)
4373  cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
4374  }
4375 
4376  // Drop the switch.
4377  SI->eraseFromParent();
4378 
4379  return true;
4380 }
4381 
4382 /// Compute masked bits for the condition of a switch
4383 /// and use it to remove dead cases.
4385  const DataLayout &DL) {
4386  Value *Cond = SI->getCondition();
4387  unsigned Bits = Cond->getType()->getIntegerBitWidth();
4388  KnownBits Known = computeKnownBits(Cond, DL, 0, AC, SI);
4389 
4390  // We can also eliminate cases by determining that their values are outside of
4391  // the limited range of the condition based on how many significant (non-sign)
4392  // bits are in the condition value.
4393  unsigned ExtraSignBits = ComputeNumSignBits(Cond, DL, 0, AC, SI) - 1;
4394  unsigned MaxSignificantBitsInCond = Bits - ExtraSignBits;
4395 
4396  // Gather dead cases.
4398  for (auto &Case : SI->cases()) {
4399  const APInt &CaseVal = Case.getCaseValue()->getValue();
4400  if (Known.Zero.intersects(CaseVal) || !Known.One.isSubsetOf(CaseVal) ||
4401  (CaseVal.getMinSignedBits() > MaxSignificantBitsInCond)) {
4402  DeadCases.push_back(Case.getCaseValue());
4403  LLVM_DEBUG(dbgs() << "SimplifyCFG: switch case " << CaseVal
4404  << " is dead.\n");
4405  }
4406  }
4407 
4408  // If we can prove that the cases must cover all possible values, the
4409  // default destination becomes dead and we can remove it. If we know some
4410  // of the bits in the value, we can use that to more precisely compute the
4411  // number of possible unique case values.
4412  bool HasDefault =
4413  !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
4414  const unsigned NumUnknownBits =
4415  Bits - (Known.Zero | Known.One).countPopulation();
4416  assert(NumUnknownBits <= Bits);
4417  if (HasDefault && DeadCases.empty() &&
4418  NumUnknownBits < 64 /* avoid overflow */ &&
4419  SI->getNumCases() == (1ULL << NumUnknownBits)) {
4420  LLVM_DEBUG(dbgs() << "SimplifyCFG: switch default is dead.\n");
4421  BasicBlock *NewDefault =
4423  SI->setDefaultDest(&*NewDefault);
4424  SplitBlock(&*NewDefault, &NewDefault->front());
4425  auto *OldTI = NewDefault->getTerminator();
4426  new UnreachableInst(SI->getContext(), OldTI);
4428  return true;
4429  }
4430 
4431  SmallVector<uint64_t, 8> Weights;
4432  bool HasWeight = HasBranchWeights(SI);
4433  if (HasWeight) {
4434  GetBranchWeights(SI, Weights);
4435  HasWeight = (Weights.size() == 1 + SI->getNumCases());
4436  }
4437 
4438  // Remove dead cases from the switch.
4439  for (ConstantInt *DeadCase : DeadCases) {
4440  SwitchInst::CaseIt CaseI = SI->findCaseValue(DeadCase);
4441  assert(CaseI != SI->case_default() &&
4442  "Case was not found. Probably mistake in DeadCases forming.");
4443  if (HasWeight) {
4444  std::swap(Weights[CaseI->getCaseIndex() + 1], Weights.back());
4445  Weights.pop_back();
4446  }
4447 
4448  // Prune unused values from PHI nodes.
4449  CaseI->getCaseSuccessor()->removePredecessor(SI->getParent());
4450  SI->removeCase(CaseI);
4451  }
4452  if (HasWeight && Weights.size() >= 2) {
4453  SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
4454  setBranchWeights(SI, MDWeights);
4455  }
4456 
4457  return !DeadCases.empty();
4458 }
4459 
4460 /// If BB would be eligible for simplification by
4461 /// TryToSimplifyUncondBranchFromEmptyBlock (i.e. it is empty and terminated
4462 /// by an unconditional branch), look at the phi node for BB in the successor
4463 /// block and see if the incoming value is equal to CaseValue. If so, return
4464 /// the phi node, and set PhiIndex to BB's index in the phi node.
4466  BasicBlock *BB, int *PhiIndex) {
4467  if (BB->getFirstNonPHIOrDbg() != BB->getTerminator())
4468  return nullptr; // BB must be empty to be a candidate for simplification.
4469  if (!BB->getSinglePredecessor())
4470  return nullptr; // BB must be dominated by the switch.
4471 
4473  if (!Branch || !Branch->isUnconditional())
4474  return nullptr; // Terminator must be unconditional branch.
4475 
4476  BasicBlock *Succ = Branch->getSuccessor(0);
4477 
4478  for (PHINode &PHI : Succ->phis()) {
4479  int Idx = PHI.getBasicBlockIndex(BB);
4480  assert(Idx >= 0 && "PHI has no entry for predecessor?");
4481 
4482  Value *InValue = PHI.getIncomingValue(Idx);
4483  if (InValue != CaseValue)
4484  continue;
4485 
4486  *PhiIndex = Idx;
4487  return &PHI;
4488  }
4489 
4490  return nullptr;
4491 }
4492 
4493 /// Try to forward the condition of a switch instruction to a phi node
4494 /// dominated by the switch, if that would mean that some of the destination
4495 /// blocks of the switch can be folded away. Return true if a change is made.
4497  using ForwardingNodesMap = DenseMap<PHINode *, SmallVector<int, 4>>;
4498 
4499  ForwardingNodesMap ForwardingNodes;
4500  BasicBlock *SwitchBlock = SI->getParent();
4501  bool Changed = false;
4502  for (auto &Case : SI->cases()) {
4503  ConstantInt *CaseValue = Case.getCaseValue();
4504  BasicBlock *CaseDest = Case.getCaseSuccessor();
4505 
4506  // Replace phi operands in successor blocks that are using the constant case
4507  // value rather than the switch condition variable:
4508  // switchbb:
4509  // switch i32 %x, label %default [
4510  // i32 17, label %succ
4511  // ...
4512  // succ:
4513  // %r = phi i32 ... [ 17, %switchbb ] ...
4514  // -->
4515  // %r = phi i32 ... [ %x, %switchbb ] ...
4516 
4517  for (PHINode &Phi : CaseDest->phis()) {
4518  // This only works if there is exactly 1 incoming edge from the switch to
4519  // a phi. If there is >1, that means multiple cases of the switch map to 1
4520  // value in the phi, and that phi value is not the switch condition. Thus,
4521  // this transform would not make sense (the phi would be invalid because
4522  // a phi can't have different incoming values from the same block).
4523  int SwitchBBIdx = Phi.getBasicBlockIndex(SwitchBlock);
4524  if (Phi.getIncomingValue(SwitchBBIdx) == CaseValue &&
4525  count(Phi.blocks(), SwitchBlock) == 1) {
4526  Phi.setIncomingValue(SwitchBBIdx, SI->getCondition());
4527  Changed = true;
4528  }
4529  }
4530 
4531  // Collect phi nodes that are indirectly using this switch's case constants.
4532  int PhiIdx;
4533  if (auto *Phi = FindPHIForConditionForwarding(CaseValue, CaseDest, &PhiIdx))
4534  ForwardingNodes[Phi].push_back(PhiIdx);
4535  }
4536 
4537  for (auto &ForwardingNode : ForwardingNodes) {
4538  PHINode *Phi = ForwardingNode.first;
4539  SmallVectorImpl<int> &Indexes = ForwardingNode.second;
4540  if (Indexes.size() < 2)
4541  continue;
4542 
4543  for (int Index : Indexes)
4544  Phi->setIncomingValue(Index, SI->getCondition());
4545  Changed = true;
4546  }
4547 
4548  return Changed;
4549 }
4550 
4551 /// Return true if the backend will be able to handle
4552 /// initializing an array of constants like C.
4554  if (C->isThreadDependent())
4555  return false;
4556  if (C->isDLLImportDependent())
4557  return false;
4558 
4559  if (!isa<ConstantFP>(C) && !isa<ConstantInt>(C) &&
4560  !isa<ConstantPointerNull>(C) && !isa<GlobalValue>(C) &&
4561  !isa<UndefValue>(C) && !isa<ConstantExpr>(C))
4562  return false;
4563 
4564  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
4565  if (!CE->isGEPWithNoNotionalOverIndexing())
4566  return false;
4567  if (!ValidLookupTableConstant(CE->getOperand(0), TTI))
4568  return false;
4569  }
4570 
4572  return false;
4573 
4574  return true;
4575 }
4576 
4577 /// If V is a Constant, return it. Otherwise, try to look up
4578 /// its constant value in ConstantPool, returning 0 if it's not there.
4579 static Constant *
4582  if (Constant *C = dyn_cast<Constant>(V))
4583  return C;
4584  return ConstantPool.lookup(V);
4585 }
4586 
4587 /// Try to fold instruction I into a constant. This works for
4588 /// simple instructions such as binary operations where both operands are
4589 /// constant or can be replaced by constants from the ConstantPool. Returns the
4590 /// resulting constant on success, 0 otherwise.
4591 static Constant *
4594  if (SelectInst *Select = dyn_cast<SelectInst>(I)) {
4595  Constant *A = LookupConstant(Select->getCondition(), ConstantPool);
4596  if (!A)
4597  return nullptr;
4598  if (A->isAllOnesValue())
4599  return LookupConstant(Select->getTrueValue(), ConstantPool);
4600  if (A->isNullValue())
4601  return LookupConstant(Select->getFalseValue(), ConstantPool);
4602  return nullptr;
4603  }
4604 
4606  for (unsigned N = 0, E = I->getNumOperands(); N != E; ++N) {
4608  COps.push_back(A);
4609  else
4610  return nullptr;
4611  }
4612 
4613  if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) {
4614  return ConstantFoldCompareInstOperands(Cmp->getPredicate(), COps[0],
4615  COps[1], DL);
4616  }
4617 
4618  return ConstantFoldInstOperands(I, COps, DL);
4619 }
4620 
4621 /// Try to determine the resulting constant values in phi nodes
4622 /// at the common destination basic block, *CommonDest, for one of the case
4623 /// destionations CaseDest corresponding to value CaseVal (0 for the default
4624 /// case), of a switch instruction SI.
4625 static bool
4627  BasicBlock **CommonDest,
4628  SmallVectorImpl<std::pair<PHINode *, Constant *>> &Res,
4629  const DataLayout &DL, const TargetTransformInfo &TTI) {
4630  // The block from which we enter the common destination.
4631  BasicBlock *Pred = SI->getParent();
4632 
4633  // If CaseDest is empty except for some side-effect free instructions through
4634  // which we can constant-propagate the CaseVal, continue to its successor.
4636  ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
4637  for (Instruction &I :CaseDest->instructionsWithoutDebug()) {
4638  if (TerminatorInst *T = dyn_cast<TerminatorInst>(&I)) {
4639  // If the terminator is a simple branch, continue to the next block.
4640  if (T->getNumSuccessors() != 1 || T->isExceptional())
4641  return false;
4642  Pred = CaseDest;
4643  CaseDest = T->getSuccessor(0);
4644  } else if (Constant *C = ConstantFold(&I, DL, ConstantPool)) {
4645  // Instruction is side-effect free and constant.
4646 
4647  // If the instruction has uses outside this block or a phi node slot for
4648  // the block, it is not safe to bypass the instruction since it would then
4649  // no longer dominate all its uses.
4650  for (auto &Use : I.uses()) {
4651  User *User = Use.getUser();
4652  if (Instruction *I = dyn_cast<Instruction>(User))
4653  if (I->getParent() == CaseDest)
4654  continue;
4655  if (PHINode *Phi = dyn_cast<PHINode>(User))
4656  if (Phi->getIncomingBlock(Use) == CaseDest)
4657  continue;
4658  return false;
4659  }
4660 
4661  ConstantPool.insert(std::make_pair(&I, C));
4662  } else {
4663  break;
4664  }
4665  }
4666 
4667  // If we did not have a CommonDest before, use the current one.
4668  if (!*CommonDest)
4669  *CommonDest = CaseDest;
4670  // If the destination isn't the common one, abort.
4671  if (CaseDest != *CommonDest)
4672  return false;
4673 
4674  // Get the values for this case from phi nodes in the destination block.
4675  for (PHINode &PHI : (*CommonDest)->phis()) {
4676  int Idx = PHI.getBasicBlockIndex(Pred);
4677  if (Idx == -1)
4678  continue;
4679 
4680  Constant *ConstVal =
4681  LookupConstant(PHI.getIncomingValue(Idx), ConstantPool);
4682  if (!ConstVal)
4683  return false;
4684 
4685  // Be conservative about which kinds of constants we support.
4686  if (!ValidLookupTableConstant(ConstVal, TTI))
4687  return false;
4688 
4689  Res.push_back(std::make_pair(&PHI, ConstVal));
4690  }
4691 
4692  return Res.size() > 0;
4693 }
4694 
4695 // Helper function used to add CaseVal to the list of cases that generate
4696 // Result. Returns the updated number of cases that generate this result.
4697 static uintptr_t MapCaseToResult(ConstantInt *CaseVal,
4698  SwitchCaseResultVectorTy &UniqueResults,
4699  Constant *Result) {
4700  for (auto &I : UniqueResults) {
4701  if (I.first == Result) {
4702  I.second.push_back(CaseVal);
4703  return I.second.size();
4704  }
4705  }
4706  UniqueResults.push_back(
4707  std::make_pair(Result, SmallVector<ConstantInt *, 4>(1, CaseVal)));
4708  return 1;
4709 }
4710 
4711 // Helper function that initializes a map containing
4712 // results for the PHI node of the common destination block for a switch
4713 // instruction. Returns false if multiple PHI nodes have been found or if
4714 // there is not a common destination block for the switch.
4715 static bool
4717  SwitchCaseResultVectorTy &UniqueResults,
4718  Constant *&DefaultResult, const DataLayout &DL,
4719  const TargetTransformInfo &TTI,
4720  uintptr_t MaxUniqueResults, uintptr_t MaxCasesPerResult) {
4721  for (auto &I : SI->cases()) {
4722  ConstantInt *CaseVal = I.getCaseValue();
4723 
4724  // Resulting value at phi nodes for this case value.
4725  SwitchCaseResultsTy Results;
4726  if (!GetCaseResults(SI, CaseVal, I.getCaseSuccessor(), &CommonDest, Results,
4727  DL, TTI))
4728  return false;
4729 
4730  // Only one value per case is permitted.
4731  if (Results.size() > 1)
4732  return false;
4733 
4734  // Add the case->result mapping to UniqueResults.
4735  const uintptr_t NumCasesForResult =
4736  MapCaseToResult(CaseVal, UniqueResults, Results.begin()->second);
4737 
4738  // Early out if there are too many cases for this result.
4739  if (NumCasesForResult > MaxCasesPerResult)
4740  return false;
4741 
4742  // Early out if there are too many unique results.
4743  if (UniqueResults.size() > MaxUniqueResults)
4744  return false;
4745 
4746  // Check the PHI consistency.
4747  if (!PHI)
4748  PHI = Results[0].first;
4749  else if (PHI != Results[0].first)
4750  return false;
4751  }
4752  // Find the default result value.
4754  BasicBlock *DefaultDest = SI->getDefaultDest();
4755  GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
4756  DL, TTI);
4757  // If the default value is not found abort unless the default destination
4758  // is unreachable.
4759  DefaultResult =
4760  DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr;
4761  if ((!DefaultResult &&
4762  !isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg())))
4763  return false;
4764 
4765  return true;
4766 }
4767 
4768 // Helper function that checks if it is possible to transform a switch with only
4769 // two cases (or two cases + default) that produces a result into a select.
4770 // Example:
4771 // switch (a) {
4772 // case 10: %0 = icmp eq i32 %a, 10
4773 // return 10; %1 = select i1 %0, i32 10, i32 4
4774 // case 20: ----> %2 = icmp eq i32 %a, 20
4775 // return 2; %3 = select i1 %2, i32 2, i32 %1
4776 // default:
4777 // return 4;
4778 // }
4779 static Value *ConvertTwoCaseSwitch(const SwitchCaseResultVectorTy &ResultVector,
4780  Constant *DefaultResult, Value *Condition,
4781  IRBuilder<> &Builder) {
4782  assert(ResultVector.size() == 2 &&
4783  "We should have exactly two unique results at this point");
4784  // If we are selecting between only two cases transform into a simple
4785  // select or a two-way select if default is possible.
4786  if (ResultVector[0].second.size() == 1 &&
4787  ResultVector[1].second.size() == 1) {
4788  ConstantInt *const FirstCase = ResultVector[0].second[0];
4789  ConstantInt *const SecondCase = ResultVector[1].second[0];
4790 
4791  bool DefaultCanTrigger = DefaultResult;
4792  Value *SelectValue = ResultVector[1].first;
4793  if (DefaultCanTrigger) {
4794  Value *const ValueCompare =
4795  Builder.CreateICmpEQ(Condition, SecondCase, "switch.selectcmp");
4796  SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
4797  DefaultResult, "switch.select");
4798  }
4799  Value *const ValueCompare =
4800  Builder.CreateICmpEQ(Condition, FirstCase, "switch.selectcmp");
4801  return Builder.CreateSelect(ValueCompare, ResultVector[0].first,
4802  SelectValue, "switch.select");
4803  }
4804 
4805  return nullptr;
4806 }
4807 
4808 // Helper function to cleanup a switch instruction that has been converted into
4809 // a select, fixing up PHI nodes and basic blocks.
4811  Value *SelectValue,
4812  IRBuilder<> &Builder) {
4813  BasicBlock *SelectBB = SI->getParent();
4814  while (PHI->getBasicBlockIndex(SelectBB) >= 0)
4815  PHI->removeIncomingValue(SelectBB);
4816  PHI->addIncoming(SelectValue, SelectBB);
4817 
4818  Builder.CreateBr(PHI->getParent());
4819 
4820  // Remove the switch.
4821  for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
4822  BasicBlock *Succ = SI->getSuccessor(i);
4823 
4824  if (Succ == PHI->getParent())
4825  continue;
4826  Succ->removePredecessor(SelectBB);
4827  }
4828  SI->eraseFromParent();
4829 }
4830 
4831 /// If the switch is only used to initialize one or more
4832 /// phi nodes in a common successor block with only two different
4833 /// constant values, replace the switch with select.
4834 static bool switchToSelect(SwitchInst *SI, IRBuilder<> &Builder,
4835  const DataLayout &DL,
4836  const TargetTransformInfo &TTI) {
4837  Value *const Cond = SI->getCondition();
4838  PHINode *PHI = nullptr;
4839  BasicBlock *CommonDest = nullptr;
4840  Constant *DefaultResult;
4841  SwitchCaseResultVectorTy UniqueResults;
4842  // Collect all the cases that will deliver the same value from the switch.
4843  if (!InitializeUniqueCases(SI, PHI, CommonDest, UniqueResults, DefaultResult,
4844  DL, TTI, 2, 1))
4845  return false;
4846  // Selects choose between maximum two values.
4847  if (UniqueResults.size() != 2)
4848  return false;
4849  assert(PHI != nullptr && "PHI for value select not found");
4850 
4851  Builder.SetInsertPoint(SI);
4852  Value *SelectValue =
4853  ConvertTwoCaseSwitch(UniqueResults, DefaultResult, Cond, Builder);
4854  if (SelectValue) {
4855  RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, Builder);
4856  return true;
4857  }
4858  // The switch couldn't be converted into a select.
4859  return false;
4860 }
4861 
4862 namespace {
4863 
4864 /// This class represents a lookup table that can be used to replace a switch.
4865 class SwitchLookupTable {
4866 public:
4867  /// Create a lookup table to use as a switch replacement with the contents
4868  /// of Values, using DefaultValue to fill any holes in the table.
4869  SwitchLookupTable(
4870  Module &M, uint64_t TableSize, ConstantInt *Offset,
4871  const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
4872  Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName);
4873 
4874  /// Build instructions with Builder to retrieve the value at
4875  /// the position given by Index in the lookup table.
4876  Value *BuildLookup(Value *Index, IRBuilder<> &Builder);
4877 
4878  /// Return true if a table with TableSize elements of
4879  /// type ElementType would fit in a target-legal register.
4880  static bool WouldFitInRegister(const DataLayout &DL, uint64_t TableSize,
4881  Type *ElementType);
4882 
4883 private:
4884  // Depending on the contents of the table, it can be represented in
4885  // different ways.
4886  enum {
4887  // For tables where each element contains the same value, we just have to
4888  // store that single value and return it for each lookup.
4889  SingleValueKind,
4890 
4891  // For tables where there is a linear relationship between table index
4892  // and values. We calculate the result with a simple multiplication
4893  // and addition instead of a table lookup.
4894  LinearMapKind,
4895 
4896  // For small tables with integer elements, we can pack them into a bitmap
4897  // that fits into a target-legal register. Values are retrieved by
4898  // shift and mask operations.
4899  BitMapKind,
4900 
4901  // The table is stored as an array of values. Values are retrieved by load
4902  // instructions from the table.
4903  ArrayKind
4904  } Kind;
4905 
4906  // For SingleValueKind, this is the single value.
4907  Constant *SingleValue = nullptr;
4908 
4909  // For BitMapKind, this is the bitmap.
4910  ConstantInt *BitMap = nullptr;
4911  IntegerType *BitMapElementTy = nullptr;
4912 
4913  // For LinearMapKind, these are the constants used to derive the value.
4914  ConstantInt *LinearOffset = nullptr;
4915  ConstantInt *LinearMultiplier = nullptr;
4916 
4917  // For ArrayKind, this is the array.
4918  GlobalVariable *Array = nullptr;
4919 };
4920 
4921 } // end anonymous namespace
4922 
4923 SwitchLookupTable::SwitchLookupTable(
4924  Module &M, uint64_t TableSize, ConstantInt *Offset,
4925  const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
4926  Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName) {
4927  assert(Values.size() && "Can't build lookup table without values!");
4928  assert(TableSize >= Values.size() && "Can't fit values in table!");
4929 
4930  // If all values in the table are equal, this is that value.
4931  SingleValue = Values.begin()->second;
4932 
4933  Type *ValueType = Values.begin()->second->getType();
4934 
4935  // Build up the table contents.
4936  SmallVector<Constant *, 64> TableContents(TableSize);
4937  for (size_t I = 0, E = Values.size(); I != E; ++I) {
4938  ConstantInt *CaseVal = Values[I].first;
4939  Constant *CaseRes = Values[I].second;
4940  assert(CaseRes->getType() == ValueType);
4941 
4942  uint64_t Idx = (CaseVal->getValue() - Offset->getValue()).getLimitedValue();
4943  TableContents[Idx] = CaseRes;
4944 
4945  if (CaseRes != SingleValue)
4946  SingleValue = nullptr;
4947  }
4948 
4949  // Fill in any holes in the table with the default result.
4950  if (Values.size() < TableSize) {
4951  assert(DefaultValue &&
4952  "Need a default value to fill the lookup table holes.");
4953  assert(DefaultValue->getType() == ValueType);
4954  for (uint64_t I = 0; I < TableSize; ++I) {
4955  if (!TableContents[I])
4956  TableContents[I] = DefaultValue;
4957  }
4958 
4959  if (DefaultValue != SingleValue)
4960  SingleValue = nullptr;
4961  }
4962 
4963  // If each element in the table contains the same value, we only need to store
4964  // that single value.
4965  if (SingleValue) {
4966  Kind = SingleValueKind;
4967  return;
4968  }
4969 
4970  // Check if we can derive the value with a linear transformation from the
4971  // table index.
4972  if (isa<IntegerType>(ValueType)) {
4973  bool LinearMappingPossible = true;
4974  APInt PrevVal;
4975  APInt DistToPrev;
4976  assert(TableSize >= 2 && "Should be a SingleValue table.");
4977  // Check if there is the same distance between two consecutive values.
4978  for (uint64_t I = 0; I < TableSize; ++I) {
4979  ConstantInt *ConstVal = dyn_cast<ConstantInt>(TableContents[I]);
4980  if (!ConstVal) {
4981  // This is an undef. We could deal with it, but undefs in lookup tables
4982  // are very seldom. It's probably not worth the additional complexity.
4983  LinearMappingPossible = false;
4984  break;
4985  }
4986  const APInt &Val = ConstVal->getValue();
4987  if (I != 0) {
4988  APInt Dist = Val - PrevVal;
4989  if (I == 1) {
4990  DistToPrev = Dist;
4991  } else if (Dist != DistToPrev) {
4992  LinearMappingPossible = false;
4993  break;
4994  }
4995  }
4996  PrevVal = Val;
4997  }
4998  if (LinearMappingPossible) {
4999  LinearOffset = cast<ConstantInt>(TableContents[0]);
5000  LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
5001  Kind = LinearMapKind;
5002  ++NumLinearMaps;
5003  return;
5004  }
5005  }
5006 
5007  // If the type is integer and the table fits in a register, build a bitmap.
5008  if (WouldFitInRegister(DL, TableSize, ValueType)) {
5009  IntegerType *IT = cast<IntegerType>(ValueType);
5010  APInt TableInt(TableSize * IT->getBitWidth(), 0);
5011  for (uint64_t I = TableSize; I > 0; --I) {
5012  TableInt <<= IT->getBitWidth();
5013  // Insert values into the bitmap. Undef values are set to zero.
5014  if (!isa<UndefValue>(TableContents[I - 1])) {
5015  ConstantInt *Val = cast<ConstantInt>(TableContents[I - 1]);
5016  TableInt |= Val->getValue().zext(TableInt.getBitWidth());
5017  }
5018  }
5019  BitMap = ConstantInt::get(M.getContext(), TableInt);
5020  BitMapElementTy = IT;
5021  Kind = BitMapKind;
5022  ++NumBitMaps;
5023  return;
5024  }
5025 
5026  // Store the table in an array.
5027  ArrayType *ArrayTy = ArrayType::get(ValueType, TableSize);
5028  Constant *Initializer = ConstantArray::get(ArrayTy, TableContents);
5029 
5030  Array = new GlobalVariable(M, ArrayTy, /*constant=*/true,
5031  GlobalVariable::PrivateLinkage, Initializer,
5032  "switch.table." + FuncName);
5033  Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
5034  Kind = ArrayKind;
5035 }
5036 
5037 Value *SwitchLookupTable::BuildLookup(Value *Index, IRBuilder<> &Builder) {
5038  switch (Kind) {
5039  case SingleValueKind:
5040  return SingleValue;
5041  case LinearMapKind: {
5042  // Derive the result value from the input value.
5043  Value *Result = Builder.CreateIntCast(Index, LinearMultiplier->getType(),
5044  false, "switch.idx.cast");
5045  if (!LinearMultiplier->isOne())
5046  Result = Builder.CreateMul(Result, LinearMultiplier, "switch.idx.mult");
5047  if (!LinearOffset->isZero())
5048  Result = Builder.CreateAdd(Result, LinearOffset, "switch.offset");
5049  return Result;
5050  }
5051  case BitMapKind: {
5052  // Type of the bitmap (e.g. i59).
5053  IntegerType *MapTy = BitMap->getType();
5054 
5055  // Cast Index to the same type as the bitmap.
5056  // Note: The Index is <= the number of elements in the table, so
5057  // truncating it to the width of the bitmask is safe.
5058  Value *ShiftAmt = Builder.CreateZExtOrTrunc(Index, MapTy, "switch.cast");
5059 
5060  // Multiply the shift amount by the element width.
5061  ShiftAmt = Builder.CreateMul(
5062  ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
5063  "switch.shiftamt");
5064 
5065  // Shift down.
5066  Value *DownShifted =
5067  Builder.CreateLShr(BitMap, ShiftAmt, "switch.downshift");
5068  // Mask off.
5069  return Builder.CreateTrunc(DownShifted, BitMapElementTy, "switch.masked");
5070  }
5071  case ArrayKind: {
5072  // Make sure the table index will not overflow when treated as signed.
5073  IntegerType *IT = cast<IntegerType>(Index->getType());
5074  uint64_t TableSize =
5075  Array->getInitializer()->getType()->getArrayNumElements();
5076  if (TableSize > (1ULL << (IT->getBitWidth() - 1)))
5077  Index = Builder.CreateZExt(
5078  Index, IntegerType::get(IT->getContext(), IT->getBitWidth() + 1),
5079  "switch.tableidx.zext");
5080 
5081  Value *GEPIndices[] = {Builder.getInt32(0), Index};
5082  Value *GEP = Builder.CreateInBoundsGEP(Array->getValueType(), Array,
5083  GEPIndices, "switch.gep");
5084  return Builder.CreateLoad(GEP, "switch.load");
5085  }
5086  }
5087  llvm_unreachable("Unknown lookup table kind!");
5088 }
5089 
5090 bool SwitchLookupTable::WouldFitInRegister(const DataLayout &DL,
5091  uint64_t TableSize,
5092  Type *ElementType) {
5093  auto *IT = dyn_cast<IntegerType>(ElementType);
5094  if (!IT)
5095  return false;
5096  // FIXME: If the type is wider than it needs to be, e.g. i8 but all values
5097  // are <= 15, we could try to narrow the type.
5098 
5099  // Avoid overflow, fitsInLegalInteger uses unsigned int for the width.
5100  if (TableSize >= UINT_MAX / IT->getBitWidth())
5101  return false;
5102  return DL.fitsInLegalInteger(TableSize * IT->getBitWidth());
5103 }
5104 
5105 /// Determine whether a lookup table should be built for this switch, based on
5106 /// the number of cases, size of the table, and the types of the results.
5107 static bool
5108 ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize,
5109  const TargetTransformInfo &TTI, const DataLayout &DL,
5110  const SmallDenseMap<PHINode *, Type *> &ResultTypes) {
5111  if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10)
5112  return false; // TableSize overflowed, or mul below might overflow.
5113 
5114  bool AllTablesFitInRegister = true;
5115  bool HasIllegalType = false;
5116  for (const auto &I : ResultTypes) {
5117  Type *Ty = I.second;
5118 
5119  // Saturate this flag to true.
5120  HasIllegalType = HasIllegalType || !TTI.isTypeLegal(Ty);
5121 
5122  // Saturate this flag to false.
5123  AllTablesFitInRegister =
5124  AllTablesFitInRegister &&
5125  SwitchLookupTable::WouldFitInRegister(DL, TableSize, Ty);
5126 
5127  // If both flags saturate, we're done. NOTE: This *only* works with
5128  // saturating flags, and all flags have to saturate first due to the
5129  // non-deterministic behavior of iterating over a dense map.
5130  if (HasIllegalType && !AllTablesFitInRegister)
5131  break;
5132  }
5133 
5134  // If each table would fit in a register, we should build it anyway.
5135  if (AllTablesFitInRegister)
5136  return true;
5137 
5138  // Don't build a table that doesn't fit in-register if it has illegal types.
5139  if (HasIllegalType)
5140  return false;
5141 
5142  // The table density should be at least 40%. This is the same criterion as for
5143  // jump tables, see SelectionDAGBuilder::handleJTSwitchCase.
5144  // FIXME: Find the best cut-off.
5145  return SI->getNumCases() * 10 >= TableSize * 4;
5146 }
5147 
5148 /// Try to reuse the switch table index compare. Following pattern:
5149 /// \code
5150 /// if (idx < tablesize)
5151 /// r = table[idx]; // table does not contain default_value
5152 /// else
5153 /// r = default_value;
5154 /// if (r != default_value)
5155 /// ...
5156 /// \endcode
5157 /// Is optimized to:
5158 /// \code
5159 /// cond = idx < tablesize;
5160 /// if (cond)
5161 /// r = table[idx];
5162 /// else
5163 /// r = default_value;
5164 /// if (cond)
5165 /// ...
5166 /// \endcode
5167 /// Jump threading will then eliminate the second if(cond).
5168 static void reuseTableCompare(
5169  User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch,
5170  Constant *DefaultValue,
5171  const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values) {
5172  ICmpInst *CmpInst = dyn_cast<ICmpInst>(PhiUser);
5173  if (!CmpInst)
5174  return;
5175 
5176  // We require that the compare is in the same block as the phi so that jump
5177  // threading can do its work afterwards.
5178  if (CmpInst->getParent() != PhiBlock)
5179  return;
5180 
5181  Constant *CmpOp1 = dyn_cast<Constant>(CmpInst->getOperand(1));
5182  if (!CmpOp1)
5183  return;
5184 
5185  Value *RangeCmp = RangeCheckBranch->getCondition();
5186  Constant *TrueConst = ConstantInt::getTrue(RangeCmp->getType());
5187  Constant *FalseConst = ConstantInt::getFalse(RangeCmp->getType());
5188 
5189  // Check if the compare with the default value is constant true or false.
5190  Constant *DefaultConst = ConstantExpr::getICmp(CmpInst->getPredicate(),
5191  DefaultValue, CmpOp1, true);
5192  if (DefaultConst != TrueConst && DefaultConst != FalseConst)
5193  return;
5194 
5195  // Check if the compare with the case values is distinct from the default
5196  // compare result.
5197  for (auto ValuePair : Values) {
5198  Constant *CaseConst = ConstantExpr::getICmp(CmpInst->getPredicate(),
5199  ValuePair.second, CmpOp1, true);
5200  if (!CaseConst || CaseConst == DefaultConst || isa<UndefValue>(CaseConst))
5201  return;
5202  assert((CaseConst == TrueConst || CaseConst == FalseConst) &&
5203  "Expect true or false as compare result.");
5204  }
5205 
5206  // Check if the branch instruction dominates the phi node. It's a simple
5207  // dominance check, but sufficient for our needs.
5208  // Although this check is invariant in the calling loops, it's better to do it
5209  // at this late stage. Practically we do it at most once for a switch.
5210  BasicBlock *BranchBlock = RangeCheckBranch->getParent();
5211  for (auto PI = pred_begin(PhiBlock), E = pred_end(PhiBlock); PI != E; ++PI) {
5212  BasicBlock *Pred = *PI;
5213  if (Pred != BranchBlock && Pred->getUniquePredecessor() != BranchBlock)
5214  return;
5215  }
5216 
5217  if (DefaultConst == FalseConst) {
5218  // The compare yields the same result. We can replace it.
5219  CmpInst->replaceAllUsesWith(RangeCmp);
5220  ++NumTableCmpReuses;
5221  } else {
5222  // The compare yields the same result, just inverted. We can replace it.
5223  Value *InvertedTableCmp = BinaryOperator::CreateXor(
5224  RangeCmp, ConstantInt::get(RangeCmp->getType(), 1), "inverted.cmp",
5225  RangeCheckBranch);
5226  CmpInst->replaceAllUsesWith(InvertedTableCmp);
5227  ++NumTableCmpReuses;
5228  }
5229 }
5230 
5231 /// If the switch is only used to initialize one or more phi nodes in a common
5232 /// successor block with different constant values, replace the switch with
5233 /// lookup tables.
5235  const DataLayout &DL,
5236  const TargetTransformInfo &TTI) {
5237  assert(SI->getNumCases() > 1 && "Degenerate switch?");
5238 
5239  Function *Fn = SI->getParent()->getParent();
5240  // Only build lookup table when we have a target that supports it or the
5241  // attribute is not set.
5242  if (!TTI.shouldBuildLookupTables() ||
5243  (Fn->getFnAttribute("no-jump-tables").getValueAsString() == "true"))
5244  return false;
5245 
5246  // FIXME: If the switch is too sparse for a lookup table, perhaps we could
5247  // split off a dense part and build a lookup table for that.
5248 
5249  // FIXME: This creates arrays of GEPs to constant strings, which means each
5250  // GEP needs a runtime relocation in PIC code. We should just build one big
5251  // string and lookup indices into that.
5252 
5253  // Ignore switches with less than three cases. Lookup tables will not make
5254  // them faster, so we don't analyze them.
5255  if (SI->getNumCases() < 3)
5256  return false;
5257 
5258  // Figure out the corresponding result for each case value and phi node in the
5259  // common destination, as well as the min and max case values.
5260  assert(SI->case_begin() != SI->case_end());
5261  SwitchInst::CaseIt CI = SI->case_begin();
5262  ConstantInt *MinCaseVal = CI->getCaseValue();
5263  ConstantInt *MaxCaseVal = CI->getCaseValue();
5264 
5265  BasicBlock *CommonDest = nullptr;
5266 
5267  using ResultListTy = SmallVector<std::pair<ConstantInt *, Constant *>, 4>;
5269 
5270  SmallDenseMap<PHINode *, Constant *> DefaultResults;
5273 
5274  for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) {
5275  ConstantInt *CaseVal = CI->getCaseValue();
5276  if (CaseVal->getValue().slt(MinCaseVal->getValue()))
5277  MinCaseVal = CaseVal;
5278  if (CaseVal->getValue().sgt(MaxCaseVal->getValue()))
5279  MaxCaseVal = CaseVal;
5280 
5281  // Resulting value at phi nodes for this case value.
5282  using ResultsTy = SmallVector<std::pair<PHINode *, Constant *>, 4>;
5283  ResultsTy Results;
5284  if (!GetCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
5285  Results, DL, TTI))
5286  return false;
5287 
5288  // Append the result from this case to the list for each phi.
5289  for (const auto &I : Results) {
5290  PHINode *PHI = I.first;
5291  Constant *Value = I.second;
5292  if (!ResultLists.count(PHI))
5293  PHIs.push_back(PHI);
5294  ResultLists[PHI].push_back(std::make_pair(CaseVal, Value));
5295  }
5296  }
5297 
5298  // Keep track of the result types.
5299  for (PHINode *PHI : PHIs) {
5300  ResultTypes[PHI] = ResultLists[PHI][0].second->getType();
5301  }
5302 
5303  uint64_t NumResults = ResultLists[PHIs[0]].size();
5304  APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue();
5305  uint64_t TableSize = RangeSpread.getLimitedValue() + 1;
5306  bool TableHasHoles = (NumResults < TableSize);
5307 
5308  // If the table has holes, we need a constant result for the default case
5309  // or a bitmask that fits in a register.
5310  SmallVector<std::pair<PHINode *, Constant *>, 4> DefaultResultsList;
5311  bool HasDefaultResults =
5312  GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest,
5313  DefaultResultsList, DL, TTI);
5314 
5315  bool NeedMask = (TableHasHoles && !HasDefaultResults);
5316  if (NeedMask) {
5317  // As an extra penalty for the validity test we require more cases.
5318  if (SI->getNumCases() < 4) // FIXME: Find best threshold value (benchmark).
5319  return false;
5320  if (!DL.fitsInLegalInteger(TableSize))
5321  return false;
5322  }
5323 
5324  for (const auto &I : DefaultResultsList) {
5325  PHINode *PHI = I.first;
5326  Constant *Result = I.second;
5327  DefaultResults[PHI] = Result;
5328  }
5329 
5330  if (!ShouldBuildLookupTable(SI, TableSize, TTI, DL, ResultTypes))
5331  return false;
5332 
5333  // Create the BB that does the lookups.
5334  Module &Mod = *CommonDest->getParent()->getParent();
5335  BasicBlock *LookupBB = BasicBlock::Create(
5336  Mod.getContext(), "switch.lookup", CommonDest->getParent(), CommonDest);
5337 
5338  // Compute the table index value.
5339  Builder.SetInsertPoint(SI);
5340  Value *TableIndex;
5341  if (MinCaseVal->isNullValue())
5342  TableIndex = SI->getCondition();
5343  else
5344  TableIndex = Builder.CreateSub(SI->getCondition(), MinCaseVal,
5345  "switch.tableidx");
5346 
5347  // Compute the maximum table size representable by the integer type we are
5348  // switching upon.
5349  unsigned CaseSize = MinCaseVal->getType()->getPrimitiveSizeInBits();
5350  uint64_t MaxTableSize = CaseSize > 63 ? UINT64_MAX : 1ULL << CaseSize;
5351  assert(MaxTableSize >= TableSize &&
5352  "It is impossible for a switch to have more entries than the max "
5353  "representable value of its input integer type's size.");
5354 
5355  // If the default destination is unreachable, or if the lookup table covers
5356  // all values of the conditional variable, branch directly to the lookup table
5357  // BB. Otherwise, check that the condition is within the case range.
5358  const bool DefaultIsReachable =
5359  !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
5360  const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
5361  BranchInst *RangeCheckBranch = nullptr;
5362 
5363  if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
5364  Builder.CreateBr(LookupBB);
5365  // Note: We call removeProdecessor later since we need to be able to get the
5366  // PHI value for the default case in case we're using a bit mask.
5367  } else {
5368  Value *Cmp = Builder.CreateICmpULT(
5369  TableIndex, ConstantInt::get(MinCaseVal->getType(), TableSize));
5370  RangeCheckBranch =
5371  Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
5372  }
5373 
5374  // Populate the BB that does the lookups.
5375  Builder.SetInsertPoint(LookupBB);
5376 
5377  if (NeedMask) {
5378  // Before doing the lookup, we do the hole check. The LookupBB is therefore
5379  // re-purposed to do the hole check, and we create a new LookupBB.
5380  BasicBlock *MaskBB = LookupBB;
5381  MaskBB->setName("switch.hole_check");
5382  LookupBB = BasicBlock::Create(Mod.getContext(), "switch.lookup",
5383  CommonDest->getParent(), CommonDest);
5384 
5385  // Make the mask's bitwidth at least 8-bit and a power-of-2 to avoid
5386  // unnecessary illegal types.
5387  uint64_t TableSizePowOf2 = NextPowerOf2(std::max(7ULL, TableSize - 1ULL));
5388  APInt MaskInt(TableSizePowOf2, 0);
5389  APInt One(TableSizePowOf2, 1);
5390  // Build bitmask; fill in a 1 bit for every case.
5391  const ResultListTy &ResultList = ResultLists[PHIs[0]];
5392  for (size_t I = 0, E = ResultList.size(); I != E; ++I) {
5393  uint64_t Idx = (ResultList[I].first->getValue() - MinCaseVal->getValue())
5394  .getLimitedValue();
5395  MaskInt |= One << Idx;
5396  }
5397  ConstantInt *TableMask = ConstantInt::get(Mod.getContext(), MaskInt);
5398 
5399  // Get the TableIndex'th bit of the bitmask.
5400  // If this bit is 0 (meaning hole) jump to the default destination,
5401  // else continue with table lookup.
5402  IntegerType *MapTy = TableMask->getType();
5403  Value *MaskIndex =
5404  Builder.CreateZExtOrTrunc(TableIndex, MapTy, "switch.maskindex");
5405  Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex, "switch.shifted");
5406  Value *LoBit = Builder.CreateTrunc(
5407  Shifted, Type::getInt1Ty(Mod.getContext()), "switch.lobit");
5408  Builder.CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
5409 
5410  Builder.SetInsertPoint(LookupBB);
5411  AddPredecessorToBlock(SI->getDefaultDest(), MaskBB, SI->getParent());
5412  }
5413 
5414  if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
5415  // We cached PHINodes in PHIs. To avoid accessing deleted PHINodes later,
5416  // do not delete PHINodes here.
5418  /*DontDeleteUselessPHIs=*/true);
5419  }
5420 
5421  bool ReturnedEarly = false;
5422  for (PHINode *PHI : PHIs) {
5423  const ResultListTy &ResultList = ResultLists[PHI];
5424 
5425  // If using a bitmask, use any value to fill the lookup table holes.
5426  Constant *DV = NeedMask ? ResultLists[PHI][0].second : DefaultResults[PHI];
5427  StringRef FuncName = Fn->getName();
5428  SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultList, DV, DL,
5429  FuncName);
5430 
5431  Value *Result = Table.BuildLookup(TableIndex, Builder);
5432 
5433  // If the result is used to return immediately from the function, we want to
5434  // do that right here.
5435  if (PHI->hasOneUse() && isa<ReturnInst>(*PHI->user_begin()) &&
5436  PHI->user_back() == CommonDest->getFirstNonPHIOrDbg()) {
5437  Builder.CreateRet(Result);
5438  ReturnedEarly = true;
5439  break;
5440  }
5441 
5442  // Do a small peephole optimization: re-use the switch table compare if
5443  // possible.
5444  if (!TableHasHoles && HasDefaultResults && RangeCheckBranch) {
5445  BasicBlock *PhiBlock = PHI->getParent();
5446  // Search for compare instructions which use the phi.
5447  for (auto *User : PHI->users()) {
5448  reuseTableCompare(User, PhiBlock, RangeCheckBranch, DV, ResultList);
5449  }
5450  }
5451 
5452  PHI->addIncoming(Result, LookupBB);
5453  }
5454 
5455  if (!ReturnedEarly)
5456  Builder.CreateBr(CommonDest);
5457 
5458  // Remove the switch.
5459  for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
5460  BasicBlock *Succ = SI->getSuccessor(i);
5461 
5462  if (Succ == SI->getDefaultDest())
5463  continue;
5464  Succ->removePredecessor(SI->getParent());
5465  }
5466  SI->eraseFromParent();
5467 
5468  ++NumLookupTables;
5469  if (NeedMask)
5470  ++NumLookupTablesHoles;
5471  return true;
5472 }
5473 
5474 static bool isSwitchDense(ArrayRef<int64_t> Values) {
5475  // See also SelectionDAGBuilder::isDense(), which this function was based on.
5476  uint64_t Diff = (uint64_t)Values.back() - (uint64_t)Values.front();
5477  uint64_t Range = Diff + 1;
5478  uint64_t NumCases = Values.size();
5479  // 40% is the default density for building a jump table in optsize/minsize mode.
5480  uint64_t MinDensity = 40;
5481 
5482  return NumCases * 100 >= Range * MinDensity;
5483 }
5484 
5485 /// Try to transform a switch that has "holes" in it to a contiguous sequence
5486 /// of cases.
5487 ///
5488 /// A switch such as: switch(i) {case 5: case 9: case 13: case 17:} can be
5489 /// range-reduced to: switch ((i-5) / 4) {case 0: case 1: case 2: case 3:}.
5490 ///
5491 /// This converts a sparse switch into a dense switch which allows better
5492 /// lowering and could also allow transforming into a lookup table.
5494  const DataLayout &DL,
5495  const TargetTransformInfo &TTI) {
5496  auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
5497  if (CondTy->getIntegerBitWidth() > 64 ||
5498  !DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
5499  return false;
5500  // Only bother with this optimization if there are more than 3 switch cases;
5501  // SDAG will only bother creating jump tables for 4 or more cases.
5502  if (SI->getNumCases() < 4)
5503  return false;
5504 
5505  // This transform is agnostic to the signedness of the input or case values. We
5506  // can treat the case values as signed or unsigned. We can optimize more common
5507  // cases such as a sequence crossing zero {-4,0,4,8} if we interpret case values
5508  // as signed.
5509  SmallVector<int64_t,4> Values;
5510  for (auto &C : SI->cases())
5511  Values.push_back(C.getCaseValue()->getValue().getSExtValue());
5512  llvm::sort(Values.begin(), Values.end());
5513 
5514  // If the switch is already dense, there's nothing useful to do here.
5515  if (isSwitchDense(Values))
5516  return false;
5517 
5518  // First, transform the values such that they start at zero and ascend.
5519  int64_t Base = Values[0];
5520  for (auto &V : Values)
5521  V -= (uint64_t)(Base);
5522 
5523  // Now we have signed numbers that have been shifted so that, given enough
5524  // precision, there are no negative values. Since the rest of the transform
5525  // is bitwise only, we switch now to an unsigned representation.
5526  uint64_t GCD = 0;
5527  for (auto &V : Values)
5528  GCD = GreatestCommonDivisor64(GCD, (uint64_t)V);
5529 
5530  // This transform can be done speculatively because it is so cheap - it results
5531  // in a single rotate operation being inserted. This can only happen if the
5532  // factor extracted is a power of 2.
5533  // FIXME: If the GCD is an odd number we can multiply by the multiplicative
5534  // inverse of GCD and then perform this transform.
5535  // FIXME: It's possible that optimizing a switch on powers of two might also
5536  // be beneficial - flag values are often powers of two and we could use a CLZ
5537  // as the key function.
5538  if (GCD <= 1 || !isPowerOf2_64(GCD))
5539  // No common divisor found or too expensive to compute key function.
5540  return false;
5541 
5542  unsigned Shift = Log2_64(GCD);
5543  for (auto &V : Values)
5544  V = (int64_t)((uint64_t)V >> Shift);
5545 
5546  if (!isSwitchDense(Values))
5547  // Transform didn't create a dense switch.
5548  return false;
5549 
5550  // The obvious transform is to shift the switch condition right and emit a
5551  // check that the condition actually cleanly divided by GCD, i.e.
5552  // C & (1 << Shift - 1) == 0
5553  // inserting a new CFG edge to handle the case where it didn't divide cleanly.
5554  //
5555  // A cheaper way of doing this is a simple ROTR(C, Shift). This performs the
5556  // shift and puts the shifted-off bits in the uppermost bits. If any of these
5557  // are nonzero then the switch condition will be very large and will hit the
5558  // default case.
5559 
5560  auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
5561  Builder.SetInsertPoint(SI);
5562  auto *ShiftC = ConstantInt::get(Ty, Shift);
5563  auto *Sub = Builder.CreateSub(SI->getCondition(), ConstantInt::get(Ty, Base));
5564  auto *LShr = Builder.CreateLShr(Sub, ShiftC);
5565  auto *Shl = Builder.CreateShl(Sub, Ty->getBitWidth() - Shift);
5566  auto *Rot = Builder.CreateOr(LShr, Shl);
5567  SI->replaceUsesOfWith(SI->getCondition(), Rot);
5568 
5569  for (auto Case : SI->cases()) {
5570  auto *Orig = Case.getCaseValue();
5571  auto Sub = Orig->getValue() - APInt(Ty->getBitWidth(), Base);
5572  Case.setValue(
5573  cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(ShiftC->getValue()))));
5574  }
5575  return true;
5576 }
5577 
5578 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
5579  BasicBlock *BB = SI->getParent();
5580 
5581  if (isValueEqualityComparison(SI)) {
5582  // If we only have one predecessor, and if it is a branch on this value,