1 //===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Peephole optimize the CFG.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "simplifycfg"
15 #include "llvm/Transforms/Utils/Local.h"
16 #include "llvm/Constants.h"
17 #include "llvm/DerivedTypes.h"
18 #include "llvm/GlobalVariable.h"
19 #include "llvm/IRBuilder.h"
20 #include "llvm/Instructions.h"
21 #include "llvm/IntrinsicInst.h"
22 #include "llvm/LLVMContext.h"
23 #include "llvm/MDBuilder.h"
24 #include "llvm/Metadata.h"
25 #include "llvm/Operator.h"
26 #include "llvm/Type.h"
27 #include "llvm/ADT/DenseMap.h"
28 #include "llvm/ADT/STLExtras.h"
29 #include "llvm/ADT/SetVector.h"
30 #include "llvm/ADT/SmallPtrSet.h"
31 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/ADT/Statistic.h"
33 #include "llvm/Analysis/InstructionSimplify.h"
34 #include "llvm/Analysis/ValueTracking.h"
35 #include "llvm/Support/CFG.h"
36 #include "llvm/Support/CommandLine.h"
37 #include "llvm/Support/ConstantRange.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/NoFolder.h"
40 #include "llvm/Support/raw_ostream.h"
41 #include "llvm/Target/TargetData.h"
42 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
48 static cl::opt<unsigned>
49 PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(1),
50 cl::desc("Control the amount of phi node folding to perform (default = 1)"));
53 DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false),
54 cl::desc("Duplicate return instructions into unconditional branches"));
56 STATISTIC(NumSpeculations, "Number of speculative executed instructions");
59 /// ValueEqualityComparisonCase - Represents a case of a switch.
60 struct ValueEqualityComparisonCase {
64 ValueEqualityComparisonCase(ConstantInt *Value, BasicBlock *Dest)
65 : Value(Value), Dest(Dest) {}
67 bool operator<(ValueEqualityComparisonCase RHS) const {
68 // Comparing pointers is ok as we only rely on the order for uniquing.
69 return Value < RHS.Value;
73 class SimplifyCFGOpt {
74 const TargetData *const TD;
76 Value *isValueEqualityComparison(TerminatorInst *TI);
77 BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI,
78 std::vector<ValueEqualityComparisonCase> &Cases);
79 bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
81 IRBuilder<> &Builder);
82 bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
83 IRBuilder<> &Builder);
85 bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder);
86 bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder);
87 bool SimplifyUnreachable(UnreachableInst *UI);
88 bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
89 bool SimplifyIndirectBr(IndirectBrInst *IBI);
90 bool SimplifyUncondBranch(BranchInst *BI, IRBuilder <> &Builder);
91 bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder);
94 explicit SimplifyCFGOpt(const TargetData *td) : TD(td) {}
95 bool run(BasicBlock *BB);
99 /// SafeToMergeTerminators - Return true if it is safe to merge these two
100 /// terminator instructions together.
102 static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) {
103 if (SI1 == SI2) return false; // Can't merge with self!
105 // It is not safe to merge these two switch instructions if they have a common
106 // successor, and if that successor has a PHI node, and if *that* PHI node has
107 // conflicting incoming values from the two switch blocks.
108 BasicBlock *SI1BB = SI1->getParent();
109 BasicBlock *SI2BB = SI2->getParent();
110 SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
112 for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I)
113 if (SI1Succs.count(*I))
114 for (BasicBlock::iterator BBI = (*I)->begin();
115 isa<PHINode>(BBI); ++BBI) {
116 PHINode *PN = cast<PHINode>(BBI);
117 if (PN->getIncomingValueForBlock(SI1BB) !=
118 PN->getIncomingValueForBlock(SI2BB))
125 /// isProfitableToFoldUnconditional - Return true if it is safe and profitable
126 /// to merge these two terminator instructions together, where SI1 is an
127 /// unconditional branch. PhiNodes will store all PHI nodes in common
130 static bool isProfitableToFoldUnconditional(BranchInst *SI1,
133 SmallVectorImpl<PHINode*> &PhiNodes) {
134 if (SI1 == SI2) return false; // Can't merge with self!
135 assert(SI1->isUnconditional() && SI2->isConditional());
137 // We fold the unconditional branch if we can easily update all PHI nodes in
138 // common successors:
139 // 1> We have a constant incoming value for the conditional branch;
140 // 2> We have "Cond" as the incoming value for the unconditional branch;
141 // 3> SI2->getCondition() and Cond have same operands.
142 CmpInst *Ci2 = dyn_cast<CmpInst>(SI2->getCondition());
143 if (!Ci2) return false;
144 if (!(Cond->getOperand(0) == Ci2->getOperand(0) &&
145 Cond->getOperand(1) == Ci2->getOperand(1)) &&
146 !(Cond->getOperand(0) == Ci2->getOperand(1) &&
147 Cond->getOperand(1) == Ci2->getOperand(0)))
150 BasicBlock *SI1BB = SI1->getParent();
151 BasicBlock *SI2BB = SI2->getParent();
152 SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
153 for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I)
154 if (SI1Succs.count(*I))
155 for (BasicBlock::iterator BBI = (*I)->begin();
156 isa<PHINode>(BBI); ++BBI) {
157 PHINode *PN = cast<PHINode>(BBI);
158 if (PN->getIncomingValueForBlock(SI1BB) != Cond ||
159 !isa<ConstantInt>(PN->getIncomingValueForBlock(SI2BB)))
161 PhiNodes.push_back(PN);
166 /// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will
167 /// now be entries in it from the 'NewPred' block. The values that will be
168 /// flowing into the PHI nodes will be the same as those coming in from
169 /// ExistPred, an existing predecessor of Succ.
170 static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred,
171 BasicBlock *ExistPred) {
172 if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do
175 for (BasicBlock::iterator I = Succ->begin();
176 (PN = dyn_cast<PHINode>(I)); ++I)
177 PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred);
181 /// GetIfCondition - Given a basic block (BB) with two predecessors (and at
182 /// least one PHI node in it), check to see if the merge at this block is due
183 /// to an "if condition". If so, return the boolean condition that determines
184 /// which entry into BB will be taken. Also, return by references the block
185 /// that will be entered from if the condition is true, and the block that will
186 /// be entered if the condition is false.
188 /// This does no checking to see if the true/false blocks have large or unsavory
189 /// instructions in them.
190 static Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
191 BasicBlock *&IfFalse) {
192 PHINode *SomePHI = cast<PHINode>(BB->begin());
193 assert(SomePHI->getNumIncomingValues() == 2 &&
194 "Function can only handle blocks with 2 predecessors!");
195 BasicBlock *Pred1 = SomePHI->getIncomingBlock(0);
196 BasicBlock *Pred2 = SomePHI->getIncomingBlock(1);
198 // We can only handle branches. Other control flow will be lowered to
199 // branches if possible anyway.
200 BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
201 BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
202 if (Pred1Br == 0 || Pred2Br == 0)
205 // Eliminate code duplication by ensuring that Pred1Br is conditional if
207 if (Pred2Br->isConditional()) {
208 // If both branches are conditional, we don't have an "if statement". In
209 // reality, we could transform this case, but since the condition will be
210 // required anyway, we stand no chance of eliminating it, so the xform is
211 // probably not profitable.
212 if (Pred1Br->isConditional())
215 std::swap(Pred1, Pred2);
216 std::swap(Pred1Br, Pred2Br);
219 if (Pred1Br->isConditional()) {
220 // The only thing we have to watch out for here is to make sure that Pred2
221 // doesn't have incoming edges from other blocks. If it does, the condition
222 // doesn't dominate BB.
223 if (Pred2->getSinglePredecessor() == 0)
226 // If we found a conditional branch predecessor, make sure that it branches
227 // to BB and Pred2Br. If it doesn't, this isn't an "if statement".
228 if (Pred1Br->getSuccessor(0) == BB &&
229 Pred1Br->getSuccessor(1) == Pred2) {
232 } else if (Pred1Br->getSuccessor(0) == Pred2 &&
233 Pred1Br->getSuccessor(1) == BB) {
237 // We know that one arm of the conditional goes to BB, so the other must
238 // go somewhere unrelated, and this must not be an "if statement".
242 return Pred1Br->getCondition();
245 // Ok, if we got here, both predecessors end with an unconditional branch to
246 // BB. Don't panic! If both blocks only have a single (identical)
247 // predecessor, and THAT is a conditional branch, then we're all ok!
248 BasicBlock *CommonPred = Pred1->getSinglePredecessor();
249 if (CommonPred == 0 || CommonPred != Pred2->getSinglePredecessor())
252 // Otherwise, if this is a conditional branch, then we can use it!
253 BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
254 if (BI == 0) return 0;
256 assert(BI->isConditional() && "Two successors but not conditional?");
257 if (BI->getSuccessor(0) == Pred1) {
264 return BI->getCondition();
267 /// ComputeSpeculuationCost - Compute an abstract "cost" of speculating the
268 /// given instruction, which is assumed to be safe to speculate. 1 means
269 /// cheap, 2 means less cheap, and UINT_MAX means prohibitively expensive.
270 static unsigned ComputeSpeculationCost(const User *I) {
271 assert(isSafeToSpeculativelyExecute(I) &&
272 "Instruction is not safe to speculatively execute!");
273 switch (Operator::getOpcode(I)) {
275 // In doubt, be conservative.
277 case Instruction::GetElementPtr:
278 // GEPs are cheap if all indices are constant.
279 if (!cast<GEPOperator>(I)->hasAllConstantIndices())
282 case Instruction::Load:
283 case Instruction::Add:
284 case Instruction::Sub:
285 case Instruction::And:
286 case Instruction::Or:
287 case Instruction::Xor:
288 case Instruction::Shl:
289 case Instruction::LShr:
290 case Instruction::AShr:
291 case Instruction::ICmp:
292 case Instruction::Trunc:
293 case Instruction::ZExt:
294 case Instruction::SExt:
295 return 1; // These are all cheap.
297 case Instruction::Call:
298 case Instruction::Select:
303 /// DominatesMergePoint - If we have a merge point of an "if condition" as
304 /// accepted above, return true if the specified value dominates the block. We
305 /// don't handle the true generality of domination here, just a special case
306 /// which works well enough for us.
308 /// If AggressiveInsts is non-null, and if V does not dominate BB, we check to
309 /// see if V (which must be an instruction) and its recursive operands
310 /// that do not dominate BB have a combined cost lower than CostRemaining and
311 /// are non-trapping. If both are true, the instruction is inserted into the
312 /// set and true is returned.
314 /// The cost for most non-trapping instructions is defined as 1 except for
315 /// Select whose cost is 2.
317 /// After this function returns, CostRemaining is decreased by the cost of
318 /// V plus its non-dominating operands. If that cost is greater than
319 /// CostRemaining, false is returned and CostRemaining is undefined.
320 static bool DominatesMergePoint(Value *V, BasicBlock *BB,
321 SmallPtrSet<Instruction*, 4> *AggressiveInsts,
322 unsigned &CostRemaining) {
323 Instruction *I = dyn_cast<Instruction>(V);
325 // Non-instructions all dominate instructions, but not all constantexprs
326 // can be executed unconditionally.
327 if (ConstantExpr *C = dyn_cast<ConstantExpr>(V))
332 BasicBlock *PBB = I->getParent();
334 // We don't want to allow weird loops that might have the "if condition" in
335 // the bottom of this block.
336 if (PBB == BB) return false;
338 // If this instruction is defined in a block that contains an unconditional
339 // branch to BB, then it must be in the 'conditional' part of the "if
340 // statement". If not, it definitely dominates the region.
341 BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator());
342 if (BI == 0 || BI->isConditional() || BI->getSuccessor(0) != BB)
345 // If we aren't allowing aggressive promotion anymore, then don't consider
346 // instructions in the 'if region'.
347 if (AggressiveInsts == 0) return false;
349 // If we have seen this instruction before, don't count it again.
350 if (AggressiveInsts->count(I)) return true;
352 // Okay, it looks like the instruction IS in the "condition". Check to
353 // see if it's a cheap instruction to unconditionally compute, and if it
354 // only uses stuff defined outside of the condition. If so, hoist it out.
355 if (!isSafeToSpeculativelyExecute(I))
358 unsigned Cost = ComputeSpeculationCost(I);
360 if (Cost > CostRemaining)
363 CostRemaining -= Cost;
365 // Okay, we can only really hoist these out if their operands do
366 // not take us over the cost threshold.
367 for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
368 if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining))
370 // Okay, it's safe to do this! Remember this instruction.
371 AggressiveInsts->insert(I);
375 /// GetConstantInt - Extract ConstantInt from value, looking through IntToPtr
376 /// and PointerNullValue. Return NULL if value is not a constant int.
377 static ConstantInt *GetConstantInt(Value *V, const TargetData *TD) {
378 // Normal constant int.
379 ConstantInt *CI = dyn_cast<ConstantInt>(V);
380 if (CI || !TD || !isa<Constant>(V) || !V->getType()->isPointerTy())
383 // This is some kind of pointer constant. Turn it into a pointer-sized
384 // ConstantInt if possible.
385 IntegerType *PtrTy = TD->getIntPtrType(V->getContext());
387 // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*).
388 if (isa<ConstantPointerNull>(V))
389 return ConstantInt::get(PtrTy, 0);
391 // IntToPtr const int.
392 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
393 if (CE->getOpcode() == Instruction::IntToPtr)
394 if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) {
395 // The constant is very likely to have the right type already.
396 if (CI->getType() == PtrTy)
399 return cast<ConstantInt>
400 (ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false));
405 /// GatherConstantCompares - Given a potentially 'or'd or 'and'd together
406 /// collection of icmp eq/ne instructions that compare a value against a
407 /// constant, return the value being compared, and stick the constant into the
410 GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra,
411 const TargetData *TD, bool isEQ, unsigned &UsedICmps) {
412 Instruction *I = dyn_cast<Instruction>(V);
413 if (I == 0) return 0;
415 // If this is an icmp against a constant, handle this as one of the cases.
416 if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
417 if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) {
418 if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) {
421 return I->getOperand(0);
424 // If we have "x ult 3" comparison, for example, then we can add 0,1,2 to
427 ConstantRange::makeICmpRegion(ICI->getPredicate(), C->getValue());
429 // If this is an and/!= check then we want to optimize "x ugt 2" into
432 Span = Span.inverse();
434 // If there are a ton of values, we don't want to make a ginormous switch.
435 if (Span.getSetSize().ugt(8) || Span.isEmptySet())
438 for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp)
439 Vals.push_back(ConstantInt::get(V->getContext(), Tmp));
441 return I->getOperand(0);
446 // Otherwise, we can only handle an | or &, depending on isEQ.
447 if (I->getOpcode() != (isEQ ? Instruction::Or : Instruction::And))
450 unsigned NumValsBeforeLHS = Vals.size();
451 unsigned UsedICmpsBeforeLHS = UsedICmps;
452 if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, TD,
454 unsigned NumVals = Vals.size();
455 unsigned UsedICmpsBeforeRHS = UsedICmps;
456 if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD,
460 Vals.resize(NumVals);
461 UsedICmps = UsedICmpsBeforeRHS;
464 // The RHS of the or/and can't be folded in and we haven't used "Extra" yet,
465 // set it and return success.
466 if (Extra == 0 || Extra == I->getOperand(1)) {
467 Extra = I->getOperand(1);
471 Vals.resize(NumValsBeforeLHS);
472 UsedICmps = UsedICmpsBeforeLHS;
476 // If the LHS can't be folded in, but Extra is available and RHS can, try to
478 if (Extra == 0 || Extra == I->getOperand(0)) {
479 Value *OldExtra = Extra;
480 Extra = I->getOperand(0);
481 if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD,
484 assert(Vals.size() == NumValsBeforeLHS);
491 static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) {
492 Instruction *Cond = 0;
493 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
494 Cond = dyn_cast<Instruction>(SI->getCondition());
495 } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
496 if (BI->isConditional())
497 Cond = dyn_cast<Instruction>(BI->getCondition());
498 } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(TI)) {
499 Cond = dyn_cast<Instruction>(IBI->getAddress());
502 TI->eraseFromParent();
503 if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond);
506 /// isValueEqualityComparison - Return true if the specified terminator checks
507 /// to see if a value is equal to constant integer value.
508 Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) {
510 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
511 // Do not permit merging of large switch instructions into their
512 // predecessors unless there is only one predecessor.
513 if (SI->getNumSuccessors()*std::distance(pred_begin(SI->getParent()),
514 pred_end(SI->getParent())) <= 128)
515 CV = SI->getCondition();
516 } else if (BranchInst *BI = dyn_cast<BranchInst>(TI))
517 if (BI->isConditional() && BI->getCondition()->hasOneUse())
518 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
519 if ((ICI->getPredicate() == ICmpInst::ICMP_EQ ||
520 ICI->getPredicate() == ICmpInst::ICMP_NE) &&
521 GetConstantInt(ICI->getOperand(1), TD))
522 CV = ICI->getOperand(0);
524 // Unwrap any lossless ptrtoint cast.
525 if (TD && CV && CV->getType() == TD->getIntPtrType(CV->getContext()))
526 if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV))
527 CV = PTII->getOperand(0);
531 /// GetValueEqualityComparisonCases - Given a value comparison instruction,
532 /// decode all of the 'cases' that it represents and return the 'default' block.
533 BasicBlock *SimplifyCFGOpt::
534 GetValueEqualityComparisonCases(TerminatorInst *TI,
535 std::vector<ValueEqualityComparisonCase>
537 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
538 Cases.reserve(SI->getNumCases());
539 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i)
540 Cases.push_back(ValueEqualityComparisonCase(i.getCaseValue(),
541 i.getCaseSuccessor()));
542 return SI->getDefaultDest();
545 BranchInst *BI = cast<BranchInst>(TI);
546 ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
547 BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE);
548 Cases.push_back(ValueEqualityComparisonCase(GetConstantInt(ICI->getOperand(1),
551 return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ);
555 /// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries
556 /// in the list that match the specified block.
557 static void EliminateBlockCases(BasicBlock *BB,
558 std::vector<ValueEqualityComparisonCase> &Cases) {
559 for (unsigned i = 0, e = Cases.size(); i != e; ++i)
560 if (Cases[i].Dest == BB) {
561 Cases.erase(Cases.begin()+i);
566 /// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as
569 ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1,
570 std::vector<ValueEqualityComparisonCase > &C2) {
571 std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
573 // Make V1 be smaller than V2.
574 if (V1->size() > V2->size())
577 if (V1->size() == 0) return false;
578 if (V1->size() == 1) {
580 ConstantInt *TheVal = (*V1)[0].Value;
581 for (unsigned i = 0, e = V2->size(); i != e; ++i)
582 if (TheVal == (*V2)[i].Value)
586 // Otherwise, just sort both lists and compare element by element.
587 array_pod_sort(V1->begin(), V1->end());
588 array_pod_sort(V2->begin(), V2->end());
589 unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
590 while (i1 != e1 && i2 != e2) {
591 if ((*V1)[i1].Value == (*V2)[i2].Value)
593 if ((*V1)[i1].Value < (*V2)[i2].Value)
601 /// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a
602 /// terminator instruction and its block is known to only have a single
603 /// predecessor block, check to see if that predecessor is also a value
604 /// comparison with the same value, and if that comparison determines the
605 /// outcome of this comparison. If so, simplify TI. This does a very limited
606 /// form of jump threading.
607 bool SimplifyCFGOpt::
608 SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
610 IRBuilder<> &Builder) {
611 Value *PredVal = isValueEqualityComparison(Pred->getTerminator());
612 if (!PredVal) return false; // Not a value comparison in predecessor.
614 Value *ThisVal = isValueEqualityComparison(TI);
615 assert(ThisVal && "This isn't a value comparison!!");
616 if (ThisVal != PredVal) return false; // Different predicates.
618 // TODO: Preserve branch weight metadata, similarly to how
619 // FoldValueComparisonIntoPredecessors preserves it.
621 // Find out information about when control will move from Pred to TI's block.
622 std::vector<ValueEqualityComparisonCase> PredCases;
623 BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(),
625 EliminateBlockCases(PredDef, PredCases); // Remove default from cases.
627 // Find information about how control leaves this block.
628 std::vector<ValueEqualityComparisonCase> ThisCases;
629 BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
630 EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases.
632 // If TI's block is the default block from Pred's comparison, potentially
633 // simplify TI based on this knowledge.
634 if (PredDef == TI->getParent()) {
635 // If we are here, we know that the value is none of those cases listed in
636 // PredCases. If there are any cases in ThisCases that are in PredCases, we
638 if (!ValuesOverlap(PredCases, ThisCases))
641 if (isa<BranchInst>(TI)) {
642 // Okay, one of the successors of this condbr is dead. Convert it to a
644 assert(ThisCases.size() == 1 && "Branch can only have one case!");
645 // Insert the new branch.
646 Instruction *NI = Builder.CreateBr(ThisDef);
649 // Remove PHI node entries for the dead edge.
650 ThisCases[0].Dest->removePredecessor(TI->getParent());
652 DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
653 << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");
655 EraseTerminatorInstAndDCECond(TI);
659 SwitchInst *SI = cast<SwitchInst>(TI);
660 // Okay, TI has cases that are statically dead, prune them away.
661 SmallPtrSet<Constant*, 16> DeadCases;
662 for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
663 DeadCases.insert(PredCases[i].Value);
665 DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
666 << "Through successor TI: " << *TI);
668 for (SwitchInst::CaseIt i = SI->case_end(), e = SI->case_begin(); i != e;) {
670 if (DeadCases.count(i.getCaseValue())) {
671 i.getCaseSuccessor()->removePredecessor(TI->getParent());
676 DEBUG(dbgs() << "Leaving: " << *TI << "\n");
680 // Otherwise, TI's block must correspond to some matched value. Find out
681 // which value (or set of values) this is.
682 ConstantInt *TIV = 0;
683 BasicBlock *TIBB = TI->getParent();
684 for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
685 if (PredCases[i].Dest == TIBB) {
687 return false; // Cannot handle multiple values coming to this block.
688 TIV = PredCases[i].Value;
690 assert(TIV && "No edge from pred to succ?");
692 // Okay, we found the one constant that our value can be if we get into TI's
693 // BB. Find out which successor will unconditionally be branched to.
694 BasicBlock *TheRealDest = 0;
695 for (unsigned i = 0, e = ThisCases.size(); i != e; ++i)
696 if (ThisCases[i].Value == TIV) {
697 TheRealDest = ThisCases[i].Dest;
701 // If not handled by any explicit cases, it is handled by the default case.
702 if (TheRealDest == 0) TheRealDest = ThisDef;
704 // Remove PHI node entries for dead edges.
705 BasicBlock *CheckEdge = TheRealDest;
706 for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI)
707 if (*SI != CheckEdge)
708 (*SI)->removePredecessor(TIBB);
712 // Insert the new branch.
713 Instruction *NI = Builder.CreateBr(TheRealDest);
716 DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
717 << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");
719 EraseTerminatorInstAndDCECond(TI);
724 /// ConstantIntOrdering - This class implements a stable ordering of constant
725 /// integers that does not depend on their address. This is important for
726 /// applications that sort ConstantInt's to ensure uniqueness.
727 struct ConstantIntOrdering {
728 bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const {
729 return LHS->getValue().ult(RHS->getValue());
734 static int ConstantIntSortPredicate(const void *P1, const void *P2) {
735 const ConstantInt *LHS = *(const ConstantInt*const*)P1;
736 const ConstantInt *RHS = *(const ConstantInt*const*)P2;
737 if (LHS->getValue().ult(RHS->getValue()))
739 if (LHS->getValue() == RHS->getValue())
744 static inline bool HasBranchWeights(const Instruction* I) {
745 MDNode* ProfMD = I->getMetadata(LLVMContext::MD_prof);
746 if (ProfMD && ProfMD->getOperand(0))
747 if (MDString* MDS = dyn_cast<MDString>(ProfMD->getOperand(0)))
748 return MDS->getString().equals("branch_weights");
753 /// Tries to get a branch weight for the given instruction, returns NULL if it
754 /// can't. Pos starts at 0.
755 static ConstantInt* GetWeight(Instruction* I, int Pos) {
756 MDNode* ProfMD = I->getMetadata(LLVMContext::MD_prof);
757 if (ProfMD && ProfMD->getOperand(0)) {
758 if (MDString* MDS = dyn_cast<MDString>(ProfMD->getOperand(0))) {
759 if (MDS->getString().equals("branch_weights")) {
760 assert(ProfMD->getNumOperands() >= 3);
761 return dyn_cast<ConstantInt>(ProfMD->getOperand(1 + Pos));
769 /// Scale the given weights based on the successor TI's metadata. Scaling is
770 /// done by multiplying every weight by the sum of the successor's weights.
771 static void ScaleWeights(Instruction* STI, MutableArrayRef<uint64_t> Weights) {
772 // Sum the successor's weights
773 assert(HasBranchWeights(STI));
775 MDNode* ProfMD = STI->getMetadata(LLVMContext::MD_prof);
776 for (unsigned i = 1; i < ProfMD->getNumOperands(); ++i) {
777 ConstantInt* CI = dyn_cast<ConstantInt>(ProfMD->getOperand(i));
779 Scale += CI->getValue().getZExtValue();
782 // Skip default, as it's replaced during the folding
783 for (unsigned i = 1; i < Weights.size(); ++i) {
788 /// Sees if any of the weights are too big for a uint32_t, and halves all the
789 /// weights if any are.
790 static void FitWeights(MutableArrayRef<uint64_t> Weights) {
792 for (unsigned i = 0; i < Weights.size(); ++i)
793 if (Weights[i] > UINT_MAX) {
801 for (unsigned i = 0; i < Weights.size(); ++i)
805 /// FoldValueComparisonIntoPredecessors - The specified terminator is a value
806 /// equality comparison instruction (either a switch or a branch on "X == c").
807 /// See if any of the predecessors of the terminator block are value comparisons
808 /// on the same value. If so, and if safe to do so, fold them together.
809 bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
810 IRBuilder<> &Builder) {
811 BasicBlock *BB = TI->getParent();
812 Value *CV = isValueEqualityComparison(TI); // CondVal
813 assert(CV && "Not a comparison?");
814 bool Changed = false;
816 SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB));
817 while (!Preds.empty()) {
818 BasicBlock *Pred = Preds.pop_back_val();
820 // See if the predecessor is a comparison with the same value.
821 TerminatorInst *PTI = Pred->getTerminator();
822 Value *PCV = isValueEqualityComparison(PTI); // PredCondVal
824 if (PCV == CV && SafeToMergeTerminators(TI, PTI)) {
825 // Figure out which 'cases' to copy from SI to PSI.
826 std::vector<ValueEqualityComparisonCase> BBCases;
827 BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
829 std::vector<ValueEqualityComparisonCase> PredCases;
830 BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
832 // Based on whether the default edge from PTI goes to BB or not, fill in
833 // PredCases and PredDefault with the new switch cases we would like to
835 SmallVector<BasicBlock*, 8> NewSuccessors;
837 // Update the branch weight metadata along the way
838 SmallVector<uint64_t, 8> Weights;
839 uint64_t PredDefaultWeight = 0;
840 bool PredHasWeights = HasBranchWeights(PTI);
841 bool SuccHasWeights = HasBranchWeights(TI);
843 if (PredHasWeights) {
844 MDNode* MD = PTI->getMetadata(LLVMContext::MD_prof);
846 for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) {
847 ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(i));
849 Weights.push_back(CI->getValue().getZExtValue());
852 // If the predecessor is a conditional eq, then swap the default weight
853 // to be the first entry.
854 if (BranchInst* BI = dyn_cast<BranchInst>(PTI)) {
855 assert(Weights.size() == 2);
856 ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
858 if (ICI->getPredicate() == ICmpInst::ICMP_EQ) {
859 std::swap(Weights.front(), Weights.back());
863 PredDefaultWeight = Weights.front();
864 } else if (SuccHasWeights) {
865 // If there are no predecessor weights but there are successor weights,
866 // populate Weights with 1, which will later be scaled to the sum of
867 // successor's weights
868 Weights.assign(1 + PredCases.size(), 1);
869 PredDefaultWeight = 1;
872 uint64_t SuccDefaultWeight = 0;
873 if (SuccHasWeights) {
875 if (BranchInst* BI = dyn_cast<BranchInst>(TI)) {
876 ICmpInst* ICI = dyn_cast<ICmpInst>(BI->getCondition());
879 if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
883 SuccDefaultWeight = GetWeight(TI, Index)->getValue().getZExtValue();
886 if (PredDefault == BB) {
887 // If this is the default destination from PTI, only the edges in TI
888 // that don't occur in PTI, or that branch to BB will be activated.
889 std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
890 for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
891 if (PredCases[i].Dest != BB)
892 PTIHandled.insert(PredCases[i].Value);
894 // The default destination is BB, we don't need explicit targets.
895 std::swap(PredCases[i], PredCases.back());
897 if (PredHasWeights) {
898 std::swap(Weights[i+1], Weights.back());
902 PredCases.pop_back();
906 // Reconstruct the new switch statement we will be building.
907 if (PredDefault != BBDefault) {
908 PredDefault->removePredecessor(Pred);
909 PredDefault = BBDefault;
910 NewSuccessors.push_back(BBDefault);
913 if (SuccHasWeights) {
914 ScaleWeights(TI, Weights);
915 Weights.front() *= SuccDefaultWeight;
916 } else if (PredHasWeights) {
917 Weights.front() /= (1 + BBCases.size());
920 for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
921 if (!PTIHandled.count(BBCases[i].Value) &&
922 BBCases[i].Dest != BBDefault) {
923 PredCases.push_back(BBCases[i]);
924 NewSuccessors.push_back(BBCases[i].Dest);
925 if (SuccHasWeights) {
926 Weights.push_back(PredDefaultWeight *
927 GetWeight(TI, i)->getValue().getZExtValue());
928 } else if (PredHasWeights) {
929 // Split the old default's weight amongst the children
930 assert(PredDefaultWeight != 0);
931 Weights.push_back(PredDefaultWeight / (1 + BBCases.size()));
936 // FIXME: preserve branch weight metadata, similarly to the 'then'
937 // above. For now, drop it.
938 PredHasWeights = false;
939 SuccHasWeights = false;
941 // If this is not the default destination from PSI, only the edges
942 // in SI that occur in PSI with a destination of BB will be
944 std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
945 for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
946 if (PredCases[i].Dest == BB) {
947 PTIHandled.insert(PredCases[i].Value);
948 std::swap(PredCases[i], PredCases.back());
949 PredCases.pop_back();
953 // Okay, now we know which constants were sent to BB from the
954 // predecessor. Figure out where they will all go now.
955 for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
956 if (PTIHandled.count(BBCases[i].Value)) {
957 // If this is one we are capable of getting...
958 PredCases.push_back(BBCases[i]);
959 NewSuccessors.push_back(BBCases[i].Dest);
960 PTIHandled.erase(BBCases[i].Value);// This constant is taken care of
963 // If there are any constants vectored to BB that TI doesn't handle,
964 // they must go to the default destination of TI.
965 for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I =
967 E = PTIHandled.end(); I != E; ++I) {
968 PredCases.push_back(ValueEqualityComparisonCase(*I, BBDefault));
969 NewSuccessors.push_back(BBDefault);
973 // Okay, at this point, we know which new successor Pred will get. Make
974 // sure we update the number of entries in the PHI nodes for these
976 for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i)
977 AddPredecessorToBlock(NewSuccessors[i], Pred, BB);
979 Builder.SetInsertPoint(PTI);
980 // Convert pointer to int before we switch.
981 if (CV->getType()->isPointerTy()) {
982 assert(TD && "Cannot switch on pointer without TargetData");
983 CV = Builder.CreatePtrToInt(CV, TD->getIntPtrType(CV->getContext()),
987 // Now that the successors are updated, create the new Switch instruction.
988 SwitchInst *NewSI = Builder.CreateSwitch(CV, PredDefault,
990 NewSI->setDebugLoc(PTI->getDebugLoc());
991 for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
992 NewSI->addCase(PredCases[i].Value, PredCases[i].Dest);
994 if (PredHasWeights || SuccHasWeights) {
995 // Halve the weights if any of them cannot fit in an uint32_t
998 SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
1000 NewSI->setMetadata(LLVMContext::MD_prof,
1001 MDBuilder(BB->getContext()).
1002 createBranchWeights(MDWeights));
1005 EraseTerminatorInstAndDCECond(PTI);
1007 // Okay, last check. If BB is still a successor of PSI, then we must
1008 // have an infinite loop case. If so, add an infinitely looping block
1009 // to handle the case to preserve the behavior of the code.
1010 BasicBlock *InfLoopBlock = 0;
1011 for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i)
1012 if (NewSI->getSuccessor(i) == BB) {
1013 if (InfLoopBlock == 0) {
1014 // Insert it at the end of the function, because it's either code,
1015 // or it won't matter if it's hot. :)
1016 InfLoopBlock = BasicBlock::Create(BB->getContext(),
1017 "infloop", BB->getParent());
1018 BranchInst::Create(InfLoopBlock, InfLoopBlock);
1020 NewSI->setSuccessor(i, InfLoopBlock);
1029 // isSafeToHoistInvoke - If we would need to insert a select that uses the
1030 // value of this invoke (comments in HoistThenElseCodeToIf explain why we
1031 // would need to do this), we can't hoist the invoke, as there is nowhere
1032 // to put the select in this case.
1033 static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2,
1034 Instruction *I1, Instruction *I2) {
1035 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
1037 for (BasicBlock::iterator BBI = SI->begin();
1038 (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
1039 Value *BB1V = PN->getIncomingValueForBlock(BB1);
1040 Value *BB2V = PN->getIncomingValueForBlock(BB2);
1041 if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) {
1049 /// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and
1050 /// BB2, hoist any common code in the two blocks up into the branch block. The
1051 /// caller of this function guarantees that BI's block dominates BB1 and BB2.
1052 static bool HoistThenElseCodeToIf(BranchInst *BI) {
1053 // This does very trivial matching, with limited scanning, to find identical
1054 // instructions in the two blocks. In particular, we don't want to get into
1055 // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As
1056 // such, we currently just scan for obviously identical instructions in an
1058 BasicBlock *BB1 = BI->getSuccessor(0); // The true destination.
1059 BasicBlock *BB2 = BI->getSuccessor(1); // The false destination
1061 BasicBlock::iterator BB1_Itr = BB1->begin();
1062 BasicBlock::iterator BB2_Itr = BB2->begin();
1064 Instruction *I1 = BB1_Itr++, *I2 = BB2_Itr++;
1065 // Skip debug info if it is not identical.
1066 DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
1067 DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
1068 if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
1069 while (isa<DbgInfoIntrinsic>(I1))
1071 while (isa<DbgInfoIntrinsic>(I2))
1074 if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) ||
1075 (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)))
1078 // If we get here, we can hoist at least one instruction.
1079 BasicBlock *BIParent = BI->getParent();
1082 // If we are hoisting the terminator instruction, don't move one (making a
1083 // broken BB), instead clone it, and remove BI.
1084 if (isa<TerminatorInst>(I1))
1085 goto HoistTerminator;
1087 // For a normal instruction, we just move one to right before the branch,
1088 // then replace all uses of the other with the first. Finally, we remove
1089 // the now redundant second instruction.
1090 BIParent->getInstList().splice(BI, BB1->getInstList(), I1);
1091 if (!I2->use_empty())
1092 I2->replaceAllUsesWith(I1);
1093 I1->intersectOptionalDataWith(I2);
1094 I2->eraseFromParent();
1098 // Skip debug info if it is not identical.
1099 DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);
1100 DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2);
1101 if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) {
1102 while (isa<DbgInfoIntrinsic>(I1))
1104 while (isa<DbgInfoIntrinsic>(I2))
1107 } while (I1->isIdenticalToWhenDefined(I2));
1112 // It may not be possible to hoist an invoke.
1113 if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))
1116 // Okay, it is safe to hoist the terminator.
1117 Instruction *NT = I1->clone();
1118 BIParent->getInstList().insert(BI, NT);
1119 if (!NT->getType()->isVoidTy()) {
1120 I1->replaceAllUsesWith(NT);
1121 I2->replaceAllUsesWith(NT);
1125 IRBuilder<true, NoFolder> Builder(NT);
1126 // Hoisting one of the terminators from our successor is a great thing.
1127 // Unfortunately, the successors of the if/else blocks may have PHI nodes in
1128 // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI
1129 // nodes, so we insert select instruction to compute the final result.
1130 std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects;
1131 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) {
1133 for (BasicBlock::iterator BBI = SI->begin();
1134 (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
1135 Value *BB1V = PN->getIncomingValueForBlock(BB1);
1136 Value *BB2V = PN->getIncomingValueForBlock(BB2);
1137 if (BB1V == BB2V) continue;
1139 // These values do not agree. Insert a select instruction before NT
1140 // that determines the right value.
1141 SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
1143 SI = cast<SelectInst>
1144 (Builder.CreateSelect(BI->getCondition(), BB1V, BB2V,
1145 BB1V->getName()+"."+BB2V->getName()));
1147 // Make the PHI node use the select for all incoming values for BB1/BB2
1148 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1149 if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2)
1150 PN->setIncomingValue(i, SI);
1154 // Update any PHI nodes in our new successors.
1155 for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI)
1156 AddPredecessorToBlock(*SI, BIParent, BB1);
1158 EraseTerminatorInstAndDCECond(BI);
1162 /// SpeculativelyExecuteBB - Given a conditional branch that goes to BB1
1163 /// and an BB2 and the only successor of BB1 is BB2, hoist simple code
1164 /// (for now, restricted to a single instruction that's side effect free) from
1165 /// the BB1 into the branch block to speculatively execute it.
1170 /// br i1 %t1, label %BB1, label %BB2
1172 /// %t3 = add %t2, c
1178 /// %t4 = add %t2, c
1179 /// %t3 = select i1 %t1, %t2, %t3
1180 static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) {
1181 // Only speculatively execution a single instruction (not counting the
1182 // terminator) for now.
1183 Instruction *HInst = NULL;
1184 Instruction *Term = BB1->getTerminator();
1185 for (BasicBlock::iterator BBI = BB1->begin(), BBE = BB1->end();
1186 BBI != BBE; ++BBI) {
1187 Instruction *I = BBI;
1189 if (isa<DbgInfoIntrinsic>(I)) continue;
1190 if (I == Term) break;
1197 BasicBlock *BIParent = BI->getParent();
1199 // Check the instruction to be hoisted, if there is one.
1201 // Don't hoist the instruction if it's unsafe or expensive.
1202 if (!isSafeToSpeculativelyExecute(HInst))
1204 if (ComputeSpeculationCost(HInst) > PHINodeFoldingThreshold)
1207 // Do not hoist the instruction if any of its operands are defined but not
1208 // used in this BB. The transformation will prevent the operand from
1209 // being sunk into the use block.
1210 for (User::op_iterator i = HInst->op_begin(), e = HInst->op_end();
1212 Instruction *OpI = dyn_cast<Instruction>(*i);
1213 if (OpI && OpI->getParent() == BIParent &&
1214 !OpI->mayHaveSideEffects() &&
1215 !OpI->isUsedInBasicBlock(BIParent))
1220 // Be conservative for now. FP select instruction can often be expensive.
1221 Value *BrCond = BI->getCondition();
1222 if (isa<FCmpInst>(BrCond))
1225 // If BB1 is actually on the false edge of the conditional branch, remember
1226 // to swap the select operands later.
1227 bool Invert = false;
1228 if (BB1 != BI->getSuccessor(0)) {
1229 assert(BB1 == BI->getSuccessor(1) && "No edge from 'if' block?");
1233 // Collect interesting PHIs, and scan for hazards.
1234 SmallSetVector<std::pair<Value *, Value *>, 4> PHIs;
1235 BasicBlock *BB2 = BB1->getTerminator()->getSuccessor(0);
1236 for (BasicBlock::iterator I = BB2->begin();
1237 PHINode *PN = dyn_cast<PHINode>(I); ++I) {
1238 Value *BB1V = PN->getIncomingValueForBlock(BB1);
1239 Value *BIParentV = PN->getIncomingValueForBlock(BIParent);
1241 // Skip PHIs which are trivial.
1242 if (BB1V == BIParentV)
1245 // Check for saftey.
1246 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BB1V)) {
1247 // An unfolded ConstantExpr could end up getting expanded into
1248 // Instructions. Don't speculate this and another instruction at
1252 if (!isSafeToSpeculativelyExecute(CE))
1254 if (ComputeSpeculationCost(CE) > PHINodeFoldingThreshold)
1258 // Ok, we may insert a select for this PHI.
1259 PHIs.insert(std::make_pair(BB1V, BIParentV));
1262 // If there are no PHIs to process, bail early. This helps ensure idempotence
1267 // If we get here, we can hoist the instruction and if-convert.
1268 DEBUG(dbgs() << "SPECULATIVELY EXECUTING BB" << *BB1 << "\n";);
1270 // Hoist the instruction.
1272 BIParent->getInstList().splice(BI, BB1->getInstList(), HInst);
1274 // Insert selects and rewrite the PHI operands.
1275 IRBuilder<true, NoFolder> Builder(BI);
1276 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
1277 Value *TrueV = PHIs[i].first;
1278 Value *FalseV = PHIs[i].second;
1280 // Create a select whose true value is the speculatively executed value and
1281 // false value is the previously determined FalseV.
1284 SI = cast<SelectInst>
1285 (Builder.CreateSelect(BrCond, FalseV, TrueV,
1286 FalseV->getName() + "." + TrueV->getName()));
1288 SI = cast<SelectInst>
1289 (Builder.CreateSelect(BrCond, TrueV, FalseV,
1290 TrueV->getName() + "." + FalseV->getName()));
1292 // Make the PHI node use the select for all incoming values for "then" and
1294 for (BasicBlock::iterator I = BB2->begin();
1295 PHINode *PN = dyn_cast<PHINode>(I); ++I) {
1296 unsigned BB1I = PN->getBasicBlockIndex(BB1);
1297 unsigned BIParentI = PN->getBasicBlockIndex(BIParent);
1298 Value *BB1V = PN->getIncomingValue(BB1I);
1299 Value *BIParentV = PN->getIncomingValue(BIParentI);
1300 if (TrueV == BB1V && FalseV == BIParentV) {
1301 PN->setIncomingValue(BB1I, SI);
1302 PN->setIncomingValue(BIParentI, SI);
1311 /// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch
1312 /// across this block.
1313 static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) {
1314 BranchInst *BI = cast<BranchInst>(BB->getTerminator());
1317 for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) {
1318 if (isa<DbgInfoIntrinsic>(BBI))
1320 if (Size > 10) return false; // Don't clone large BB's.
1323 // We can only support instructions that do not define values that are
1324 // live outside of the current basic block.
1325 for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end();
1327 Instruction *U = cast<Instruction>(*UI);
1328 if (U->getParent() != BB || isa<PHINode>(U)) return false;
1331 // Looks ok, continue checking.
1337 /// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value
1338 /// that is defined in the same block as the branch and if any PHI entries are
1339 /// constants, thread edges corresponding to that entry to be branches to their
1340 /// ultimate destination.
1341 static bool FoldCondBranchOnPHI(BranchInst *BI, const TargetData *TD) {
1342 BasicBlock *BB = BI->getParent();
1343 PHINode *PN = dyn_cast<PHINode>(BI->getCondition());
1344 // NOTE: we currently cannot transform this case if the PHI node is used
1345 // outside of the block.
1346 if (!PN || PN->getParent() != BB || !PN->hasOneUse())
1349 // Degenerate case of a single entry PHI.
1350 if (PN->getNumIncomingValues() == 1) {
1351 FoldSingleEntryPHINodes(PN->getParent());
1355 // Now we know that this block has multiple preds and two succs.
1356 if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false;
1358 // Okay, this is a simple enough basic block. See if any phi values are
1360 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1361 ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i));
1362 if (CB == 0 || !CB->getType()->isIntegerTy(1)) continue;
1364 // Okay, we now know that all edges from PredBB should be revectored to
1365 // branch to RealDest.
1366 BasicBlock *PredBB = PN->getIncomingBlock(i);
1367 BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue());
1369 if (RealDest == BB) continue; // Skip self loops.
1370 // Skip if the predecessor's terminator is an indirect branch.
1371 if (isa<IndirectBrInst>(PredBB->getTerminator())) continue;
1373 // The dest block might have PHI nodes, other predecessors and other
1374 // difficult cases. Instead of being smart about this, just insert a new
1375 // block that jumps to the destination block, effectively splitting
1376 // the edge we are about to create.
1377 BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(),
1378 RealDest->getName()+".critedge",
1379 RealDest->getParent(), RealDest);
1380 BranchInst::Create(RealDest, EdgeBB);
1382 // Update PHI nodes.
1383 AddPredecessorToBlock(RealDest, EdgeBB, BB);
1385 // BB may have instructions that are being threaded over. Clone these
1386 // instructions into EdgeBB. We know that there will be no uses of the
1387 // cloned instructions outside of EdgeBB.
1388 BasicBlock::iterator InsertPt = EdgeBB->begin();
1389 DenseMap<Value*, Value*> TranslateMap; // Track translated values.
1390 for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) {
1391 if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
1392 TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB);
1395 // Clone the instruction.
1396 Instruction *N = BBI->clone();
1397 if (BBI->hasName()) N->setName(BBI->getName()+".c");
1399 // Update operands due to translation.
1400 for (User::op_iterator i = N->op_begin(), e = N->op_end();
1402 DenseMap<Value*, Value*>::iterator PI = TranslateMap.find(*i);
1403 if (PI != TranslateMap.end())
1407 // Check for trivial simplification.
1408 if (Value *V = SimplifyInstruction(N, TD)) {
1409 TranslateMap[BBI] = V;
1410 delete N; // Instruction folded away, don't need actual inst
1412 // Insert the new instruction into its new home.
1413 EdgeBB->getInstList().insert(InsertPt, N);
1414 if (!BBI->use_empty())
1415 TranslateMap[BBI] = N;
1419 // Loop over all of the edges from PredBB to BB, changing them to branch
1420 // to EdgeBB instead.
1421 TerminatorInst *PredBBTI = PredBB->getTerminator();
1422 for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i)
1423 if (PredBBTI->getSuccessor(i) == BB) {
1424 BB->removePredecessor(PredBB);
1425 PredBBTI->setSuccessor(i, EdgeBB);
1428 // Recurse, simplifying any other constants.
1429 return FoldCondBranchOnPHI(BI, TD) | true;
1435 /// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry
1436 /// PHI node, see if we can eliminate it.
1437 static bool FoldTwoEntryPHINode(PHINode *PN, const TargetData *TD) {
1438 // Ok, this is a two entry PHI node. Check to see if this is a simple "if
1439 // statement", which has a very simple dominance structure. Basically, we
1440 // are trying to find the condition that is being branched on, which
1441 // subsequently causes this merge to happen. We really want control
1442 // dependence information for this check, but simplifycfg can't keep it up
1443 // to date, and this catches most of the cases we care about anyway.
1444 BasicBlock *BB = PN->getParent();
1445 BasicBlock *IfTrue, *IfFalse;
1446 Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse);
1448 // Don't bother if the branch will be constant folded trivially.
1449 isa<ConstantInt>(IfCond))
1452 // Okay, we found that we can merge this two-entry phi node into a select.
1453 // Doing so would require us to fold *all* two entry phi nodes in this block.
1454 // At some point this becomes non-profitable (particularly if the target
1455 // doesn't support cmov's). Only do this transformation if there are two or
1456 // fewer PHI nodes in this block.
1457 unsigned NumPhis = 0;
1458 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I)
1462 // Loop over the PHI's seeing if we can promote them all to select
1463 // instructions. While we are at it, keep track of the instructions
1464 // that need to be moved to the dominating block.
1465 SmallPtrSet<Instruction*, 4> AggressiveInsts;
1466 unsigned MaxCostVal0 = PHINodeFoldingThreshold,
1467 MaxCostVal1 = PHINodeFoldingThreshold;
1469 for (BasicBlock::iterator II = BB->begin(); isa<PHINode>(II);) {
1470 PHINode *PN = cast<PHINode>(II++);
1471 if (Value *V = SimplifyInstruction(PN, TD)) {
1472 PN->replaceAllUsesWith(V);
1473 PN->eraseFromParent();
1477 if (!DominatesMergePoint(PN->getIncomingValue(0), BB, &AggressiveInsts,
1479 !DominatesMergePoint(PN->getIncomingValue(1), BB, &AggressiveInsts,
1484 // If we folded the first phi, PN dangles at this point. Refresh it. If
1485 // we ran out of PHIs then we simplified them all.
1486 PN = dyn_cast<PHINode>(BB->begin());
1487 if (PN == 0) return true;
1489 // Don't fold i1 branches on PHIs which contain binary operators. These can
1490 // often be turned into switches and other things.
1491 if (PN->getType()->isIntegerTy(1) &&
1492 (isa<BinaryOperator>(PN->getIncomingValue(0)) ||
1493 isa<BinaryOperator>(PN->getIncomingValue(1)) ||
1494 isa<BinaryOperator>(IfCond)))
1497 // If we all PHI nodes are promotable, check to make sure that all
1498 // instructions in the predecessor blocks can be promoted as well. If
1499 // not, we won't be able to get rid of the control flow, so it's not
1500 // worth promoting to select instructions.
1501 BasicBlock *DomBlock = 0;
1502 BasicBlock *IfBlock1 = PN->getIncomingBlock(0);
1503 BasicBlock *IfBlock2 = PN->getIncomingBlock(1);
1504 if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) {
1507 DomBlock = *pred_begin(IfBlock1);
1508 for (BasicBlock::iterator I = IfBlock1->begin();!isa<TerminatorInst>(I);++I)
1509 if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) {
1510 // This is not an aggressive instruction that we can promote.
1511 // Because of this, we won't be able to get rid of the control
1512 // flow, so the xform is not worth it.
1517 if (cast<BranchInst>(IfBlock2->getTerminator())->isConditional()) {
1520 DomBlock = *pred_begin(IfBlock2);
1521 for (BasicBlock::iterator I = IfBlock2->begin();!isa<TerminatorInst>(I);++I)
1522 if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) {
1523 // This is not an aggressive instruction that we can promote.
1524 // Because of this, we won't be able to get rid of the control
1525 // flow, so the xform is not worth it.
1530 DEBUG(dbgs() << "FOUND IF CONDITION! " << *IfCond << " T: "
1531 << IfTrue->getName() << " F: " << IfFalse->getName() << "\n");
1533 // If we can still promote the PHI nodes after this gauntlet of tests,
1534 // do all of the PHI's now.
1535 Instruction *InsertPt = DomBlock->getTerminator();
1536 IRBuilder<true, NoFolder> Builder(InsertPt);
1538 // Move all 'aggressive' instructions, which are defined in the
1539 // conditional parts of the if's up to the dominating block.
1541 DomBlock->getInstList().splice(InsertPt,
1542 IfBlock1->getInstList(), IfBlock1->begin(),
1543 IfBlock1->getTerminator());
1545 DomBlock->getInstList().splice(InsertPt,
1546 IfBlock2->getInstList(), IfBlock2->begin(),
1547 IfBlock2->getTerminator());
1549 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
1550 // Change the PHI node into a select instruction.
1551 Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
1552 Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
1555 cast<SelectInst>(Builder.CreateSelect(IfCond, TrueVal, FalseVal, ""));
1556 PN->replaceAllUsesWith(NV);
1558 PN->eraseFromParent();
1561 // At this point, IfBlock1 and IfBlock2 are both empty, so our if statement
1562 // has been flattened. Change DomBlock to jump directly to our new block to
1563 // avoid other simplifycfg's kicking in on the diamond.
1564 TerminatorInst *OldTI = DomBlock->getTerminator();
1565 Builder.SetInsertPoint(OldTI);
1566 Builder.CreateBr(BB);
1567 OldTI->eraseFromParent();
1571 /// SimplifyCondBranchToTwoReturns - If we found a conditional branch that goes
1572 /// to two returning blocks, try to merge them together into one return,
1573 /// introducing a select if the return values disagree.
1574 static bool SimplifyCondBranchToTwoReturns(BranchInst *BI,
1575 IRBuilder<> &Builder) {
1576 assert(BI->isConditional() && "Must be a conditional branch");
1577 BasicBlock *TrueSucc = BI->getSuccessor(0);
1578 BasicBlock *FalseSucc = BI->getSuccessor(1);
1579 ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator());
1580 ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator());
1582 // Check to ensure both blocks are empty (just a return) or optionally empty
1583 // with PHI nodes. If there are other instructions, merging would cause extra
1584 // computation on one path or the other.
1585 if (!TrueSucc->getFirstNonPHIOrDbg()->isTerminator())
1587 if (!FalseSucc->getFirstNonPHIOrDbg()->isTerminator())
1590 Builder.SetInsertPoint(BI);
1591 // Okay, we found a branch that is going to two return nodes. If
1592 // there is no return value for this function, just change the
1593 // branch into a return.
1594 if (FalseRet->getNumOperands() == 0) {
1595 TrueSucc->removePredecessor(BI->getParent());
1596 FalseSucc->removePredecessor(BI->getParent());
1597 Builder.CreateRetVoid();
1598 EraseTerminatorInstAndDCECond(BI);
1602 // Otherwise, figure out what the true and false return values are
1603 // so we can insert a new select instruction.
1604 Value *TrueValue = TrueRet->getReturnValue();
1605 Value *FalseValue = FalseRet->getReturnValue();
1607 // Unwrap any PHI nodes in the return blocks.
1608 if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue))
1609 if (TVPN->getParent() == TrueSucc)
1610 TrueValue = TVPN->getIncomingValueForBlock(BI->getParent());
1611 if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue))
1612 if (FVPN->getParent() == FalseSucc)
1613 FalseValue = FVPN->getIncomingValueForBlock(BI->getParent());
1615 // In order for this transformation to be safe, we must be able to
1616 // unconditionally execute both operands to the return. This is
1617 // normally the case, but we could have a potentially-trapping
1618 // constant expression that prevents this transformation from being
1620 if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue))
1623 if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue))
1627 // Okay, we collected all the mapped values and checked them for sanity, and
1628 // defined to really do this transformation. First, update the CFG.
1629 TrueSucc->removePredecessor(BI->getParent());
1630 FalseSucc->removePredecessor(BI->getParent());
1632 // Insert select instructions where needed.
1633 Value *BrCond = BI->getCondition();
1635 // Insert a select if the results differ.
1636 if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) {
1637 } else if (isa<UndefValue>(TrueValue)) {
1638 TrueValue = FalseValue;
1640 TrueValue = Builder.CreateSelect(BrCond, TrueValue,
1641 FalseValue, "retval");
1645 Value *RI = !TrueValue ?
1646 Builder.CreateRetVoid() : Builder.CreateRet(TrueValue);
1650 DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:"
1651 << "\n " << *BI << "NewRet = " << *RI
1652 << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc);
1654 EraseTerminatorInstAndDCECond(BI);
1659 /// ExtractBranchMetadata - Given a conditional BranchInstruction, retrieve the
1660 /// probabilities of the branch taking each edge. Fills in the two APInt
1661 /// parameters and return true, or returns false if no or invalid metadata was
1663 static bool ExtractBranchMetadata(BranchInst *BI,
1664 APInt &ProbTrue, APInt &ProbFalse) {
1665 assert(BI->isConditional() &&
1666 "Looking for probabilities on unconditional branch?");
1667 MDNode *ProfileData = BI->getMetadata(LLVMContext::MD_prof);
1668 if (!ProfileData || ProfileData->getNumOperands() != 3) return false;
1669 ConstantInt *CITrue = dyn_cast<ConstantInt>(ProfileData->getOperand(1));
1670 ConstantInt *CIFalse = dyn_cast<ConstantInt>(ProfileData->getOperand(2));
1671 if (!CITrue || !CIFalse) return false;
1672 ProbTrue = CITrue->getValue();
1673 ProbFalse = CIFalse->getValue();
1674 assert(ProbTrue.getBitWidth() == 32 && ProbFalse.getBitWidth() == 32 &&
1675 "Branch probability metadata must be 32-bit integers");
1679 /// MultiplyAndLosePrecision - Multiplies A and B, then returns the result. In
1680 /// the event of overflow, logically-shifts all four inputs right until the
1682 static APInt MultiplyAndLosePrecision(APInt &A, APInt &B, APInt &C, APInt &D,
1683 unsigned &BitsLost) {
1685 bool Overflow = false;
1686 APInt Result = A.umul_ov(B, Overflow);
1688 APInt MaxB = APInt::getMaxValue(A.getBitWidth()).udiv(A);
1692 } while (B.ugt(MaxB));
1693 A = A.lshr(BitsLost);
1694 C = C.lshr(BitsLost);
1695 D = D.lshr(BitsLost);
1701 /// checkCSEInPredecessor - Return true if the given instruction is available
1702 /// in its predecessor block. If yes, the instruction will be removed.
1704 static bool checkCSEInPredecessor(Instruction *Inst, BasicBlock *PB) {
1705 if (!isa<BinaryOperator>(Inst) && !isa<CmpInst>(Inst))
1707 for (BasicBlock::iterator I = PB->begin(), E = PB->end(); I != E; I++) {
1708 Instruction *PBI = &*I;
1709 // Check whether Inst and PBI generate the same value.
1710 if (Inst->isIdenticalTo(PBI)) {
1711 Inst->replaceAllUsesWith(PBI);
1712 Inst->eraseFromParent();
1719 /// FoldBranchToCommonDest - If this basic block is simple enough, and if a
1720 /// predecessor branches to us and one of our successors, fold the block into
1721 /// the predecessor and use logical operations to pick the right destination.
1722 bool llvm::FoldBranchToCommonDest(BranchInst *BI) {
1723 BasicBlock *BB = BI->getParent();
1725 Instruction *Cond = 0;
1726 if (BI->isConditional())
1727 Cond = dyn_cast<Instruction>(BI->getCondition());
1729 // For unconditional branch, check for a simple CFG pattern, where
1730 // BB has a single predecessor and BB's successor is also its predecessor's
1731 // successor. If such pattern exisits, check for CSE between BB and its
1733 if (BasicBlock *PB = BB->getSinglePredecessor())
1734 if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator()))
1735 if (PBI->isConditional() &&
1736 (BI->getSuccessor(0) == PBI->getSuccessor(0) ||
1737 BI->getSuccessor(0) == PBI->getSuccessor(1))) {
1738 for (BasicBlock::iterator I = BB->begin(), E = BB->end();
1740 Instruction *Curr = I++;
1741 if (isa<CmpInst>(Curr)) {
1745 // Quit if we can't remove this instruction.
1746 if (!checkCSEInPredecessor(Curr, PB))
1755 if (Cond == 0 || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) ||
1756 Cond->getParent() != BB || !Cond->hasOneUse())
1759 // Only allow this if the condition is a simple instruction that can be
1760 // executed unconditionally. It must be in the same block as the branch, and
1761 // must be at the front of the block.
1762 BasicBlock::iterator FrontIt = BB->front();
1764 // Ignore dbg intrinsics.
1765 while (isa<DbgInfoIntrinsic>(FrontIt)) ++FrontIt;
1767 // Allow a single instruction to be hoisted in addition to the compare
1768 // that feeds the branch. We later ensure that any values that _it_ uses
1769 // were also live in the predecessor, so that we don't unnecessarily create
1770 // register pressure or inhibit out-of-order execution.
1771 Instruction *BonusInst = 0;
1772 if (&*FrontIt != Cond &&
1773 FrontIt->hasOneUse() && *FrontIt->use_begin() == Cond &&
1774 isSafeToSpeculativelyExecute(FrontIt)) {
1775 BonusInst = &*FrontIt;
1778 // Ignore dbg intrinsics.
1779 while (isa<DbgInfoIntrinsic>(FrontIt)) ++FrontIt;
1782 // Only a single bonus inst is allowed.
1783 if (&*FrontIt != Cond)
1786 // Make sure the instruction after the condition is the cond branch.
1787 BasicBlock::iterator CondIt = Cond; ++CondIt;
1789 // Ingore dbg intrinsics.
1790 while (isa<DbgInfoIntrinsic>(CondIt)) ++CondIt;
1795 // Cond is known to be a compare or binary operator. Check to make sure that
1796 // neither operand is a potentially-trapping constant expression.
1797 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0)))
1800 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1)))
1804 // Finally, don't infinitely unroll conditional loops.
1805 BasicBlock *TrueDest = BI->getSuccessor(0);
1806 BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : 0;
1807 if (TrueDest == BB || FalseDest == BB)
1810 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
1811 BasicBlock *PredBlock = *PI;
1812 BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
1814 // Check that we have two conditional branches. If there is a PHI node in
1815 // the common successor, verify that the same value flows in from both
1817 SmallVector<PHINode*, 4> PHIs;
1818 if (PBI == 0 || PBI->isUnconditional() ||
1819 (BI->isConditional() &&
1820 !SafeToMergeTerminators(BI, PBI)) ||
1821 (!BI->isConditional() &&
1822 !isProfitableToFoldUnconditional(BI, PBI, Cond, PHIs)))
1825 // Determine if the two branches share a common destination.
1826 Instruction::BinaryOps Opc;
1827 bool InvertPredCond = false;
1829 if (BI->isConditional()) {
1830 if (PBI->getSuccessor(0) == TrueDest)
1831 Opc = Instruction::Or;
1832 else if (PBI->getSuccessor(1) == FalseDest)
1833 Opc = Instruction::And;
1834 else if (PBI->getSuccessor(0) == FalseDest)
1835 Opc = Instruction::And, InvertPredCond = true;
1836 else if (PBI->getSuccessor(1) == TrueDest)
1837 Opc = Instruction::Or, InvertPredCond = true;
1841 if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest)
1845 // Ensure that any values used in the bonus instruction are also used
1846 // by the terminator of the predecessor. This means that those values
1847 // must already have been resolved, so we won't be inhibiting the
1848 // out-of-order core by speculating them earlier.
1850 // Collect the values used by the bonus inst
1851 SmallPtrSet<Value*, 4> UsedValues;
1852 for (Instruction::op_iterator OI = BonusInst->op_begin(),
1853 OE = BonusInst->op_end(); OI != OE; ++OI) {
1855 if (!isa<Constant>(V))
1856 UsedValues.insert(V);
1859 SmallVector<std::pair<Value*, unsigned>, 4> Worklist;
1860 Worklist.push_back(std::make_pair(PBI->getOperand(0), 0));
1862 // Walk up to four levels back up the use-def chain of the predecessor's
1863 // terminator to see if all those values were used. The choice of four
1864 // levels is arbitrary, to provide a compile-time-cost bound.
1865 while (!Worklist.empty()) {
1866 std::pair<Value*, unsigned> Pair = Worklist.back();
1867 Worklist.pop_back();
1869 if (Pair.second >= 4) continue;
1870 UsedValues.erase(Pair.first);
1871 if (UsedValues.empty()) break;
1873 if (Instruction *I = dyn_cast<Instruction>(Pair.first)) {
1874 for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end();
1876 Worklist.push_back(std::make_pair(OI->get(), Pair.second+1));
1880 if (!UsedValues.empty()) return false;
1883 DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
1884 IRBuilder<> Builder(PBI);
1886 // If we need to invert the condition in the pred block to match, do so now.
1887 if (InvertPredCond) {
1888 Value *NewCond = PBI->getCondition();
1890 if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) {
1891 CmpInst *CI = cast<CmpInst>(NewCond);
1892 CI->setPredicate(CI->getInversePredicate());
1894 NewCond = Builder.CreateNot(NewCond,
1895 PBI->getCondition()->getName()+".not");
1898 PBI->setCondition(NewCond);
1899 PBI->swapSuccessors();
1902 // If we have a bonus inst, clone it into the predecessor block.
1903 Instruction *NewBonus = 0;
1905 NewBonus = BonusInst->clone();
1906 PredBlock->getInstList().insert(PBI, NewBonus);
1907 NewBonus->takeName(BonusInst);
1908 BonusInst->setName(BonusInst->getName()+".old");
1911 // Clone Cond into the predecessor basic block, and or/and the
1912 // two conditions together.
1913 Instruction *New = Cond->clone();
1914 if (BonusInst) New->replaceUsesOfWith(BonusInst, NewBonus);
1915 PredBlock->getInstList().insert(PBI, New);
1916 New->takeName(Cond);
1917 Cond->setName(New->getName()+".old");
1919 if (BI->isConditional()) {
1920 Instruction *NewCond =
1921 cast<Instruction>(Builder.CreateBinOp(Opc, PBI->getCondition(),
1923 PBI->setCondition(NewCond);
1925 if (PBI->getSuccessor(0) == BB) {
1926 AddPredecessorToBlock(TrueDest, PredBlock, BB);
1927 PBI->setSuccessor(0, TrueDest);
1929 if (PBI->getSuccessor(1) == BB) {
1930 AddPredecessorToBlock(FalseDest, PredBlock, BB);
1931 PBI->setSuccessor(1, FalseDest);
1934 // Update PHI nodes in the common successors.
1935 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
1936 ConstantInt *PBI_C = cast<ConstantInt>(
1937 PHIs[i]->getIncomingValueForBlock(PBI->getParent()));
1938 assert(PBI_C->getType()->isIntegerTy(1));
1939 Instruction *MergedCond = 0;
1940 if (PBI->getSuccessor(0) == TrueDest) {
1941 // Create (PBI_Cond and PBI_C) or (!PBI_Cond and BI_Value)
1942 // PBI_C is true: PBI_Cond or (!PBI_Cond and BI_Value)
1943 // is false: !PBI_Cond and BI_Value
1944 Instruction *NotCond =
1945 cast<Instruction>(Builder.CreateNot(PBI->getCondition(),
1948 cast<Instruction>(Builder.CreateBinOp(Instruction::And,
1953 cast<Instruction>(Builder.CreateBinOp(Instruction::Or,
1954 PBI->getCondition(), MergedCond,
1957 // Create (PBI_Cond and BI_Value) or (!PBI_Cond and PBI_C)
1958 // PBI_C is true: (PBI_Cond and BI_Value) or (!PBI_Cond)
1959 // is false: PBI_Cond and BI_Value
1961 cast<Instruction>(Builder.CreateBinOp(Instruction::And,
1962 PBI->getCondition(), New,
1964 if (PBI_C->isOne()) {
1965 Instruction *NotCond =
1966 cast<Instruction>(Builder.CreateNot(PBI->getCondition(),
1969 cast<Instruction>(Builder.CreateBinOp(Instruction::Or,
1970 NotCond, MergedCond,
1975 PHIs[i]->setIncomingValue(PHIs[i]->getBasicBlockIndex(PBI->getParent()),
1978 // Change PBI from Conditional to Unconditional.
1979 BranchInst *New_PBI = BranchInst::Create(TrueDest, PBI);
1980 EraseTerminatorInstAndDCECond(PBI);
1984 // TODO: If BB is reachable from all paths through PredBlock, then we
1985 // could replace PBI's branch probabilities with BI's.
1987 // Merge probability data into PredBlock's branch.
1989 if (PBI->isConditional() && BI->isConditional() &&
1990 ExtractBranchMetadata(PBI, C, D) && ExtractBranchMetadata(BI, A, B)) {
1991 // Given IR which does:
1993 // br i1 %x, label %bbB, label %bbC
1995 // br i1 %y, label %bbD, label %bbC
1996 // Let's call the probability that we take the edge from %bbA to %bbB
1997 // 'a', from %bbA to %bbC, 'b', from %bbB to %bbD 'c' and from %bbB to
1998 // %bbC probability 'd'.
2000 // We transform the IR into:
2002 // br i1 %z, label %bbD, label %bbC
2003 // where the probability of going to %bbD is (a*c) and going to bbC is
2006 // Probabilities aren't stored as ratios directly. Using branch weights,
2008 // (a*c)% = A*C, (b+(a*d))% = A*D+B*C+B*D.
2010 // In the event of overflow, we want to drop the LSB of the input
2014 // Ignore overflow result on ProbTrue.
2015 APInt ProbTrue = MultiplyAndLosePrecision(A, C, B, D, BitsLost);
2017 APInt Tmp1 = MultiplyAndLosePrecision(B, D, A, C, BitsLost);
2019 ProbTrue = ProbTrue.lshr(BitsLost*2);
2022 APInt Tmp2 = MultiplyAndLosePrecision(A, D, C, B, BitsLost);
2024 ProbTrue = ProbTrue.lshr(BitsLost*2);
2025 Tmp1 = Tmp1.lshr(BitsLost*2);
2028 APInt Tmp3 = MultiplyAndLosePrecision(B, C, A, D, BitsLost);
2030 ProbTrue = ProbTrue.lshr(BitsLost*2);
2031 Tmp1 = Tmp1.lshr(BitsLost*2);
2032 Tmp2 = Tmp2.lshr(BitsLost*2);
2035 bool Overflow1 = false, Overflow2 = false;
2036 APInt Tmp4 = Tmp2.uadd_ov(Tmp3, Overflow1);
2037 APInt ProbFalse = Tmp4.uadd_ov(Tmp1, Overflow2);
2039 if (Overflow1 || Overflow2) {
2040 ProbTrue = ProbTrue.lshr(1);
2041 Tmp1 = Tmp1.lshr(1);
2042 Tmp2 = Tmp2.lshr(1);
2043 Tmp3 = Tmp3.lshr(1);
2045 ProbFalse = Tmp4 + Tmp1;
2048 // The sum of branch weights must fit in 32-bits.
2049 if (ProbTrue.isNegative() && ProbFalse.isNegative()) {
2050 ProbTrue = ProbTrue.lshr(1);
2051 ProbFalse = ProbFalse.lshr(1);
2054 if (ProbTrue != ProbFalse) {
2055 // Normalize the result.
2056 APInt GCD = APIntOps::GreatestCommonDivisor(ProbTrue, ProbFalse);
2057 ProbTrue = ProbTrue.udiv(GCD);
2058 ProbFalse = ProbFalse.udiv(GCD);
2060 MDBuilder MDB(BI->getContext());
2061 MDNode *N = MDB.createBranchWeights(ProbTrue.getZExtValue(),
2062 ProbFalse.getZExtValue());
2063 PBI->setMetadata(LLVMContext::MD_prof, N);
2065 PBI->setMetadata(LLVMContext::MD_prof, NULL);
2068 PBI->setMetadata(LLVMContext::MD_prof, NULL);
2071 // Copy any debug value intrinsics into the end of PredBlock.
2072 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
2073 if (isa<DbgInfoIntrinsic>(*I))
2074 I->clone()->insertBefore(PBI);
2081 /// SimplifyCondBranchToCondBranch - If we have a conditional branch as a
2082 /// predecessor of another block, this function tries to simplify it. We know
2083 /// that PBI and BI are both conditional branches, and BI is in one of the
2084 /// successor blocks of PBI - PBI branches to BI.
2085 static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) {
2086 assert(PBI->isConditional() && BI->isConditional());
2087 BasicBlock *BB = BI->getParent();
2089 // If this block ends with a branch instruction, and if there is a
2090 // predecessor that ends on a branch of the same condition, make
2091 // this conditional branch redundant.
2092 if (PBI->getCondition() == BI->getCondition() &&
2093 PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
2094 // Okay, the outcome of this conditional branch is statically
2095 // knowable. If this block had a single pred, handle specially.
2096 if (BB->getSinglePredecessor()) {
2097 // Turn this into a branch on constant.
2098 bool CondIsTrue = PBI->getSuccessor(0) == BB;
2099 BI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()),
2101 return true; // Nuke the branch on constant.
2104 // Otherwise, if there are multiple predecessors, insert a PHI that merges
2105 // in the constant and simplify the block result. Subsequent passes of
2106 // simplifycfg will thread the block.
2107 if (BlockIsSimpleEnoughToThreadThrough(BB)) {
2108 pred_iterator PB = pred_begin(BB), PE = pred_end(BB);
2109 PHINode *NewPN = PHINode::Create(Type::getInt1Ty(BB->getContext()),
2110 std::distance(PB, PE),
2111 BI->getCondition()->getName() + ".pr",
2113 // Okay, we're going to insert the PHI node. Since PBI is not the only
2114 // predecessor, compute the PHI'd conditional value for all of the preds.
2115 // Any predecessor where the condition is not computable we keep symbolic.
2116 for (pred_iterator PI = PB; PI != PE; ++PI) {
2117 BasicBlock *P = *PI;
2118 if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) &&
2119 PBI != BI && PBI->isConditional() &&
2120 PBI->getCondition() == BI->getCondition() &&
2121 PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
2122 bool CondIsTrue = PBI->getSuccessor(0) == BB;
2123 NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()),
2126 NewPN->addIncoming(BI->getCondition(), P);
2130 BI->setCondition(NewPN);
2135 // If this is a conditional branch in an empty block, and if any
2136 // predecessors is a conditional branch to one of our destinations,
2137 // fold the conditions into logical ops and one cond br.
2138 BasicBlock::iterator BBI = BB->begin();
2139 // Ignore dbg intrinsics.
2140 while (isa<DbgInfoIntrinsic>(BBI))
2146 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BI->getCondition()))
2151 if (PBI->getSuccessor(0) == BI->getSuccessor(0))
2153 else if (PBI->getSuccessor(0) == BI->getSuccessor(1))
2154 PBIOp = 0, BIOp = 1;
2155 else if (PBI->getSuccessor(1) == BI->getSuccessor(0))
2156 PBIOp = 1, BIOp = 0;
2157 else if (PBI->getSuccessor(1) == BI->getSuccessor(1))
2162 // Check to make sure that the other destination of this branch
2163 // isn't BB itself. If so, this is an infinite loop that will
2164 // keep getting unwound.
2165 if (PBI->getSuccessor(PBIOp) == BB)
2168 // Do not perform this transformation if it would require
2169 // insertion of a large number of select instructions. For targets
2170 // without predication/cmovs, this is a big pessimization.
2171 BasicBlock *CommonDest = PBI->getSuccessor(PBIOp);
2173 unsigned NumPhis = 0;
2174 for (BasicBlock::iterator II = CommonDest->begin();
2175 isa<PHINode>(II); ++II, ++NumPhis)
2176 if (NumPhis > 2) // Disable this xform.
2179 // Finally, if everything is ok, fold the branches to logical ops.
2180 BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1);
2182 DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent()
2183 << "AND: " << *BI->getParent());
2186 // If OtherDest *is* BB, then BB is a basic block with a single conditional
2187 // branch in it, where one edge (OtherDest) goes back to itself but the other
2188 // exits. We don't *know* that the program avoids the infinite loop
2189 // (even though that seems likely). If we do this xform naively, we'll end up
2190 // recursively unpeeling the loop. Since we know that (after the xform is
2191 // done) that the block *is* infinite if reached, we just make it an obviously
2192 // infinite loop with no cond branch.
2193 if (OtherDest == BB) {
2194 // Insert it at the end of the function, because it's either code,
2195 // or it won't matter if it's hot. :)
2196 BasicBlock *InfLoopBlock = BasicBlock::Create(BB->getContext(),
2197 "infloop", BB->getParent());
2198 BranchInst::Create(InfLoopBlock, InfLoopBlock);
2199 OtherDest = InfLoopBlock;
2202 DEBUG(dbgs() << *PBI->getParent()->getParent());
2204 // BI may have other predecessors. Because of this, we leave
2205 // it alone, but modify PBI.
2207 // Make sure we get to CommonDest on True&True directions.
2208 Value *PBICond = PBI->getCondition();
2209 IRBuilder<true, NoFolder> Builder(PBI);
2211 PBICond = Builder.CreateNot(PBICond, PBICond->getName()+".not");
2213 Value *BICond = BI->getCondition();
2215 BICond = Builder.CreateNot(BICond, BICond->getName()+".not");
2217 // Merge the conditions.
2218 Value *Cond = Builder.CreateOr(PBICond, BICond, "brmerge");
2220 // Modify PBI to branch on the new condition to the new dests.
2221 PBI->setCondition(Cond);
2222 PBI->setSuccessor(0, CommonDest);
2223 PBI->setSuccessor(1, OtherDest);
2225 // OtherDest may have phi nodes. If so, add an entry from PBI's
2226 // block that are identical to the entries for BI's block.
2227 AddPredecessorToBlock(OtherDest, PBI->getParent(), BB);
2229 // We know that the CommonDest already had an edge from PBI to
2230 // it. If it has PHIs though, the PHIs may have different
2231 // entries for BB and PBI's BB. If so, insert a select to make
2234 for (BasicBlock::iterator II = CommonDest->begin();
2235 (PN = dyn_cast<PHINode>(II)); ++II) {
2236 Value *BIV = PN->getIncomingValueForBlock(BB);
2237 unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent());
2238 Value *PBIV = PN->getIncomingValue(PBBIdx);
2240 // Insert a select in PBI to pick the right value.
2241 Value *NV = cast<SelectInst>
2242 (Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName()+".mux"));
2243 PN->setIncomingValue(PBBIdx, NV);
2247 DEBUG(dbgs() << "INTO: " << *PBI->getParent());
2248 DEBUG(dbgs() << *PBI->getParent()->getParent());
2250 // This basic block is probably dead. We know it has at least
2251 // one fewer predecessor.
2255 // SimplifyTerminatorOnSelect - Simplifies a terminator by replacing it with a
2256 // branch to TrueBB if Cond is true or to FalseBB if Cond is false.
2257 // Takes care of updating the successors and removing the old terminator.
2258 // Also makes sure not to introduce new successors by assuming that edges to
2259 // non-successor TrueBBs and FalseBBs aren't reachable.
2260 static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond,
2261 BasicBlock *TrueBB, BasicBlock *FalseBB){
2262 // Remove any superfluous successor edges from the CFG.
2263 // First, figure out which successors to preserve.
2264 // If TrueBB and FalseBB are equal, only try to preserve one copy of that
2266 BasicBlock *KeepEdge1 = TrueBB;
2267 BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : 0;
2269 // Then remove the rest.
2270 for (unsigned I = 0, E = OldTerm->getNumSuccessors(); I != E; ++I) {
2271 BasicBlock *Succ = OldTerm->getSuccessor(I);
2272 // Make sure only to keep exactly one copy of each edge.
2273 if (Succ == KeepEdge1)
2275 else if (Succ == KeepEdge2)
2278 Succ->removePredecessor(OldTerm->getParent());
2281 IRBuilder<> Builder(OldTerm);
2282 Builder.SetCurrentDebugLocation(OldTerm->getDebugLoc());
2284 // Insert an appropriate new terminator.
2285 if ((KeepEdge1 == 0) && (KeepEdge2 == 0)) {
2286 if (TrueBB == FalseBB)
2287 // We were only looking for one successor, and it was present.
2288 // Create an unconditional branch to it.
2289 Builder.CreateBr(TrueBB);
2291 // We found both of the successors we were looking for.
2292 // Create a conditional branch sharing the condition of the select.
2293 Builder.CreateCondBr(Cond, TrueBB, FalseBB);
2294 } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) {
2295 // Neither of the selected blocks were successors, so this
2296 // terminator must be unreachable.
2297 new UnreachableInst(OldTerm->getContext(), OldTerm);
2299 // One of the selected values was a successor, but the other wasn't.
2300 // Insert an unconditional branch to the one that was found;
2301 // the edge to the one that wasn't must be unreachable.
2303 // Only TrueBB was found.
2304 Builder.CreateBr(TrueBB);
2306 // Only FalseBB was found.
2307 Builder.CreateBr(FalseBB);
2310 EraseTerminatorInstAndDCECond(OldTerm);
2314 // SimplifySwitchOnSelect - Replaces
2315 // (switch (select cond, X, Y)) on constant X, Y
2316 // with a branch - conditional if X and Y lead to distinct BBs,
2317 // unconditional otherwise.
2318 static bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select) {
2319 // Check for constant integer values in the select.
2320 ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue());
2321 ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue());
2322 if (!TrueVal || !FalseVal)
2325 // Find the relevant condition and destinations.
2326 Value *Condition = Select->getCondition();
2327 BasicBlock *TrueBB = SI->findCaseValue(TrueVal).getCaseSuccessor();
2328 BasicBlock *FalseBB = SI->findCaseValue(FalseVal).getCaseSuccessor();
2330 // Perform the actual simplification.
2331 return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB);
2334 // SimplifyIndirectBrOnSelect - Replaces
2335 // (indirectbr (select cond, blockaddress(@fn, BlockA),
2336 // blockaddress(@fn, BlockB)))
2338 // (br cond, BlockA, BlockB).
2339 static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) {
2340 // Check that both operands of the select are block addresses.
2341 BlockAddress *TBA = dyn_cast<BlockAddress>(SI->getTrueValue());
2342 BlockAddress *FBA = dyn_cast<BlockAddress>(SI->getFalseValue());
2346 // Extract the actual blocks.
2347 BasicBlock *TrueBB = TBA->getBasicBlock();
2348 BasicBlock *FalseBB = FBA->getBasicBlock();
2350 // Perform the actual simplification.
2351 return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB);
2354 /// TryToSimplifyUncondBranchWithICmpInIt - This is called when we find an icmp
2355 /// instruction (a seteq/setne with a constant) as the only instruction in a
2356 /// block that ends with an uncond branch. We are looking for a very specific
2357 /// pattern that occurs when "A == 1 || A == 2 || A == 3" gets simplified. In
2358 /// this case, we merge the first two "or's of icmp" into a switch, but then the
2359 /// default value goes to an uncond block with a seteq in it, we get something
2362 /// switch i8 %A, label %DEFAULT [ i8 1, label %end i8 2, label %end ]
2364 /// %tmp = icmp eq i8 %A, 92
2367 /// ... = phi i1 [ true, %entry ], [ %tmp, %DEFAULT ], [ true, %entry ]
2369 /// We prefer to split the edge to 'end' so that there is a true/false entry to
2370 /// the PHI, merging the third icmp into the switch.
2371 static bool TryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
2372 const TargetData *TD,
2373 IRBuilder<> &Builder) {
2374 BasicBlock *BB = ICI->getParent();
2376 // If the block has any PHIs in it or the icmp has multiple uses, it is too
2378 if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) return false;
2380 Value *V = ICI->getOperand(0);
2381 ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1));
2383 // The pattern we're looking for is where our only predecessor is a switch on
2384 // 'V' and this block is the default case for the switch. In this case we can
2385 // fold the compared value into the switch to simplify things.
2386 BasicBlock *Pred = BB->getSinglePredecessor();
2387 if (Pred == 0 || !isa<SwitchInst>(Pred->getTerminator())) return false;
2389 SwitchInst *SI = cast<SwitchInst>(Pred->getTerminator());
2390 if (SI->getCondition() != V)
2393 // If BB is reachable on a non-default case, then we simply know the value of
2394 // V in this block. Substitute it and constant fold the icmp instruction
2396 if (SI->getDefaultDest() != BB) {
2397 ConstantInt *VVal = SI->findCaseDest(BB);
2398 assert(VVal && "Should have a unique destination value");
2399 ICI->setOperand(0, VVal);
2401 if (Value *V = SimplifyInstruction(ICI, TD)) {
2402 ICI->replaceAllUsesWith(V);
2403 ICI->eraseFromParent();
2405 // BB is now empty, so it is likely to simplify away.
2406 return SimplifyCFG(BB) | true;
2409 // Ok, the block is reachable from the default dest. If the constant we're
2410 // comparing exists in one of the other edges, then we can constant fold ICI
2412 if (SI->findCaseValue(Cst) != SI->case_default()) {
2414 if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
2415 V = ConstantInt::getFalse(BB->getContext());
2417 V = ConstantInt::getTrue(BB->getContext());
2419 ICI->replaceAllUsesWith(V);
2420 ICI->eraseFromParent();
2421 // BB is now empty, so it is likely to simplify away.
2422 return SimplifyCFG(BB) | true;
2425 // The use of the icmp has to be in the 'end' block, by the only PHI node in
2427 BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0);
2428 PHINode *PHIUse = dyn_cast<PHINode>(ICI->use_back());
2429 if (PHIUse == 0 || PHIUse != &SuccBlock->front() ||
2430 isa<PHINode>(++BasicBlock::iterator(PHIUse)))
2433 // If the icmp is a SETEQ, then the default dest gets false, the new edge gets
2435 Constant *DefaultCst = ConstantInt::getTrue(BB->getContext());
2436 Constant *NewCst = ConstantInt::getFalse(BB->getContext());
2438 if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
2439 std::swap(DefaultCst, NewCst);
2441 // Replace ICI (which is used by the PHI for the default value) with true or
2442 // false depending on if it is EQ or NE.
2443 ICI->replaceAllUsesWith(DefaultCst);
2444 ICI->eraseFromParent();
2446 // Okay, the switch goes to this block on a default value. Add an edge from
2447 // the switch to the merge point on the compared value.
2448 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "switch.edge",
2449 BB->getParent(), BB);
2450 SI->addCase(Cst, NewBB);
2452 // NewBB branches to the phi block, add the uncond branch and the phi entry.
2453 Builder.SetInsertPoint(NewBB);
2454 Builder.SetCurrentDebugLocation(SI->getDebugLoc());
2455 Builder.CreateBr(SuccBlock);
2456 PHIUse->addIncoming(NewCst, NewBB);
2460 /// SimplifyBranchOnICmpChain - The specified branch is a conditional branch.
2461 /// Check to see if it is branching on an or/and chain of icmp instructions, and
2462 /// fold it into a switch instruction if so.
2463 static bool SimplifyBranchOnICmpChain(BranchInst *BI, const TargetData *TD,
2464 IRBuilder<> &Builder) {
2465 Instruction *Cond = dyn_cast<Instruction>(BI->getCondition());
2466 if (Cond == 0) return false;
2469 // Change br (X == 0 | X == 1), T, F into a switch instruction.
2470 // If this is a bunch of seteq's or'd together, or if it's a bunch of
2471 // 'setne's and'ed together, collect them.
2473 std::vector<ConstantInt*> Values;
2474 bool TrueWhenEqual = true;
2475 Value *ExtraCase = 0;
2476 unsigned UsedICmps = 0;
2478 if (Cond->getOpcode() == Instruction::Or) {
2479 CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, true,
2481 } else if (Cond->getOpcode() == Instruction::And) {
2482 CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, false,
2484 TrueWhenEqual = false;
2487 // If we didn't have a multiply compared value, fail.
2488 if (CompVal == 0) return false;
2490 // Avoid turning single icmps into a switch.
2494 // There might be duplicate constants in the list, which the switch
2495 // instruction can't handle, remove them now.
2496 array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate);
2497 Values.erase(std::unique(Values.begin(), Values.end()), Values.end());
2499 // If Extra was used, we require at least two switch values to do the
2500 // transformation. A switch with one value is just an cond branch.
2501 if (ExtraCase && Values.size() < 2) return false;
2503 // TODO: Preserve branch weight metadata, similarly to how
2504 // FoldValueComparisonIntoPredecessors preserves it.
2506 // Figure out which block is which destination.
2507 BasicBlock *DefaultBB = BI->getSuccessor(1);
2508 BasicBlock *EdgeBB = BI->getSuccessor(0);
2509 if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB);
2511 BasicBlock *BB = BI->getParent();
2513 DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size()
2514 << " cases into SWITCH. BB is:\n" << *BB);
2516 // If there are any extra values that couldn't be folded into the switch
2517 // then we evaluate them with an explicit branch first. Split the block
2518 // right before the condbr to handle it.
2520 BasicBlock *NewBB = BB->splitBasicBlock(BI, "switch.early.test");
2521 // Remove the uncond branch added to the old block.
2522 TerminatorInst *OldTI = BB->getTerminator();
2523 Builder.SetInsertPoint(OldTI);
2526 Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB);
2528 Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB);
2530 OldTI->eraseFromParent();
2532 // If there are PHI nodes in EdgeBB, then we need to add a new entry to them
2533 // for the edge we just added.
2534 AddPredecessorToBlock(EdgeBB, BB, NewBB);
2536 DEBUG(dbgs() << " ** 'icmp' chain unhandled condition: " << *ExtraCase
2537 << "\nEXTRABB = " << *BB);
2541 Builder.SetInsertPoint(BI);
2542 // Convert pointer to int before we switch.
2543 if (CompVal->getType()->isPointerTy()) {
2544 assert(TD && "Cannot switch on pointer without TargetData");
2545 CompVal = Builder.CreatePtrToInt(CompVal,
2546 TD->getIntPtrType(CompVal->getContext()),
2550 // Create the new switch instruction now.
2551 SwitchInst *New = Builder.CreateSwitch(CompVal, DefaultBB, Values.size());
2553 // Add all of the 'cases' to the switch instruction.
2554 for (unsigned i = 0, e = Values.size(); i != e; ++i)
2555 New->addCase(Values[i], EdgeBB);
2557 // We added edges from PI to the EdgeBB. As such, if there were any
2558 // PHI nodes in EdgeBB, they need entries to be added corresponding to
2559 // the number of edges added.
2560 for (BasicBlock::iterator BBI = EdgeBB->begin();
2561 isa<PHINode>(BBI); ++BBI) {
2562 PHINode *PN = cast<PHINode>(BBI);
2563 Value *InVal = PN->getIncomingValueForBlock(BB);
2564 for (unsigned i = 0, e = Values.size()-1; i != e; ++i)
2565 PN->addIncoming(InVal, BB);
2568 // Erase the old branch instruction.
2569 EraseTerminatorInstAndDCECond(BI);
2571 DEBUG(dbgs() << " ** 'icmp' chain result is:\n" << *BB << '\n');
2575 bool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) {
2576 // If this is a trivial landing pad that just continues unwinding the caught
2577 // exception then zap the landing pad, turning its invokes into calls.
2578 BasicBlock *BB = RI->getParent();
2579 LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI());
2580 if (RI->getValue() != LPInst)
2581 // Not a landing pad, or the resume is not unwinding the exception that
2582 // caused control to branch here.
2585 // Check that there are no other instructions except for debug intrinsics.
2586 BasicBlock::iterator I = LPInst, E = RI;
2588 if (!isa<DbgInfoIntrinsic>(I))
2591 // Turn all invokes that unwind here into calls and delete the basic block.
2592 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) {
2593 InvokeInst *II = cast<InvokeInst>((*PI++)->getTerminator());
2594 SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
2595 // Insert a call instruction before the invoke.
2596 CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II);
2598 Call->setCallingConv(II->getCallingConv());
2599 Call->setAttributes(II->getAttributes());
2600 Call->setDebugLoc(II->getDebugLoc());
2602 // Anything that used the value produced by the invoke instruction now uses
2603 // the value produced by the call instruction. Note that we do this even
2604 // for void functions and calls with no uses so that the callgraph edge is
2606 II->replaceAllUsesWith(Call);
2607 BB->removePredecessor(II->getParent());
2609 // Insert a branch to the normal destination right before the invoke.
2610 BranchInst::Create(II->getNormalDest(), II);
2612 // Finally, delete the invoke instruction!
2613 II->eraseFromParent();
2616 // The landingpad is now unreachable. Zap it.
2617 BB->eraseFromParent();
2621 bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) {
2622 BasicBlock *BB = RI->getParent();
2623 if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false;
2625 // Find predecessors that end with branches.
2626 SmallVector<BasicBlock*, 8> UncondBranchPreds;
2627 SmallVector<BranchInst*, 8> CondBranchPreds;
2628 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
2629 BasicBlock *P = *PI;
2630 TerminatorInst *PTI = P->getTerminator();
2631 if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) {
2632 if (BI->isUnconditional())
2633 UncondBranchPreds.push_back(P);
2635 CondBranchPreds.push_back(BI);
2639 // If we found some, do the transformation!
2640 if (!UncondBranchPreds.empty() && DupRet) {
2641 while (!UncondBranchPreds.empty()) {
2642 BasicBlock *Pred = UncondBranchPreds.pop_back_val();
2643 DEBUG(dbgs() << "FOLDING: " << *BB
2644 << "INTO UNCOND BRANCH PRED: " << *Pred);
2645 (void)FoldReturnIntoUncondBranch(RI, BB, Pred);
2648 // If we eliminated all predecessors of the block, delete the block now.
2649 if (pred_begin(BB) == pred_end(BB))
2650 // We know there are no successors, so just nuke the block.
2651 BB->eraseFromParent();
2656 // Check out all of the conditional branches going to this return
2657 // instruction. If any of them just select between returns, change the
2658 // branch itself into a select/return pair.
2659 while (!CondBranchPreds.empty()) {
2660 BranchInst *BI = CondBranchPreds.pop_back_val();
2662 // Check to see if the non-BB successor is also a return block.
2663 if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) &&
2664 isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) &&
2665 SimplifyCondBranchToTwoReturns(BI, Builder))
2671 bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) {
2672 BasicBlock *BB = UI->getParent();
2674 bool Changed = false;
2676 // If there are any instructions immediately before the unreachable that can
2677 // be removed, do so.
2678 while (UI != BB->begin()) {
2679 BasicBlock::iterator BBI = UI;
2681 // Do not delete instructions that can have side effects which might cause
2682 // the unreachable to not be reachable; specifically, calls and volatile
2683 // operations may have this effect.
2684 if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) break;
2686 if (BBI->mayHaveSideEffects()) {
2687 if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
2688 if (SI->isVolatile())
2690 } else if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
2691 if (LI->isVolatile())
2693 } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(BBI)) {
2694 if (RMWI->isVolatile())
2696 } else if (AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(BBI)) {
2697 if (CXI->isVolatile())
2699 } else if (!isa<FenceInst>(BBI) && !isa<VAArgInst>(BBI) &&
2700 !isa<LandingPadInst>(BBI)) {
2703 // Note that deleting LandingPad's here is in fact okay, although it
2704 // involves a bit of subtle reasoning. If this inst is a LandingPad,
2705 // all the predecessors of this block will be the unwind edges of Invokes,
2706 // and we can therefore guarantee this block will be erased.
2709 // Delete this instruction (any uses are guaranteed to be dead)
2710 if (!BBI->use_empty())
2711 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
2712 BBI->eraseFromParent();
2716 // If the unreachable instruction is the first in the block, take a gander
2717 // at all of the predecessors of this instruction, and simplify them.
2718 if (&BB->front() != UI) return Changed;
2720 SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB));
2721 for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
2722 TerminatorInst *TI = Preds[i]->getTerminator();
2723 IRBuilder<> Builder(TI);
2724 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
2725 if (BI->isUnconditional()) {
2726 if (BI->getSuccessor(0) == BB) {
2727 new UnreachableInst(TI->getContext(), TI);
2728 TI->eraseFromParent();
2732 if (BI->getSuccessor(0) == BB) {
2733 Builder.CreateBr(BI->getSuccessor(1));
2734 EraseTerminatorInstAndDCECond(BI);
2735 } else if (BI->getSuccessor(1) == BB) {
2736 Builder.CreateBr(BI->getSuccessor(0));
2737 EraseTerminatorInstAndDCECond(BI);
2741 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
2742 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
2744 if (i.getCaseSuccessor() == BB) {
2745 BB->removePredecessor(SI->getParent());
2750 // If the default value is unreachable, figure out the most popular
2751 // destination and make it the default.
2752 if (SI->getDefaultDest() == BB) {
2753 std::map<BasicBlock*, std::pair<unsigned, unsigned> > Popularity;
2754 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
2756 std::pair<unsigned, unsigned> &entry =
2757 Popularity[i.getCaseSuccessor()];
2758 if (entry.first == 0) {
2760 entry.second = i.getCaseIndex();
2766 // Find the most popular block.
2767 unsigned MaxPop = 0;
2768 unsigned MaxIndex = 0;
2769 BasicBlock *MaxBlock = 0;
2770 for (std::map<BasicBlock*, std::pair<unsigned, unsigned> >::iterator
2771 I = Popularity.begin(), E = Popularity.end(); I != E; ++I) {
2772 if (I->second.first > MaxPop ||
2773 (I->second.first == MaxPop && MaxIndex > I->second.second)) {
2774 MaxPop = I->second.first;
2775 MaxIndex = I->second.second;
2776 MaxBlock = I->first;
2780 // Make this the new default, allowing us to delete any explicit
2782 SI->setDefaultDest(MaxBlock);
2785 // If MaxBlock has phinodes in it, remove MaxPop-1 entries from
2787 if (isa<PHINode>(MaxBlock->begin()))
2788 for (unsigned i = 0; i != MaxPop-1; ++i)
2789 MaxBlock->removePredecessor(SI->getParent());
2791 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
2793 if (i.getCaseSuccessor() == MaxBlock) {
2799 } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
2800 if (II->getUnwindDest() == BB) {
2801 // Convert the invoke to a call instruction. This would be a good
2802 // place to note that the call does not throw though.
2803 BranchInst *BI = Builder.CreateBr(II->getNormalDest());
2804 II->removeFromParent(); // Take out of symbol table
2806 // Insert the call now...
2807 SmallVector<Value*, 8> Args(II->op_begin(), II->op_end()-3);
2808 Builder.SetInsertPoint(BI);
2809 CallInst *CI = Builder.CreateCall(II->getCalledValue(),
2810 Args, II->getName());
2811 CI->setCallingConv(II->getCallingConv());
2812 CI->setAttributes(II->getAttributes());
2813 // If the invoke produced a value, the call does now instead.
2814 II->replaceAllUsesWith(CI);
2821 // If this block is now dead, remove it.
2822 if (pred_begin(BB) == pred_end(BB) &&
2823 BB != &BB->getParent()->getEntryBlock()) {
2824 // We know there are no successors, so just nuke the block.
2825 BB->eraseFromParent();
2832 /// TurnSwitchRangeIntoICmp - Turns a switch with that contains only a
2833 /// integer range comparison into a sub, an icmp and a branch.
2834 static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) {
2835 assert(SI->getNumCases() > 1 && "Degenerate switch?");
2837 // Make sure all cases point to the same destination and gather the values.
2838 SmallVector<ConstantInt *, 16> Cases;
2839 SwitchInst::CaseIt I = SI->case_begin();
2840 Cases.push_back(I.getCaseValue());
2841 SwitchInst::CaseIt PrevI = I++;
2842 for (SwitchInst::CaseIt E = SI->case_end(); I != E; PrevI = I++) {
2843 if (PrevI.getCaseSuccessor() != I.getCaseSuccessor())
2845 Cases.push_back(I.getCaseValue());
2847 assert(Cases.size() == SI->getNumCases() && "Not all cases gathered");
2849 // Sort the case values, then check if they form a range we can transform.
2850 array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate);
2851 for (unsigned I = 1, E = Cases.size(); I != E; ++I) {
2852 if (Cases[I-1]->getValue() != Cases[I]->getValue()+1)
2856 Constant *Offset = ConstantExpr::getNeg(Cases.back());
2857 Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases());
2859 Value *Sub = SI->getCondition();
2860 if (!Offset->isNullValue())
2861 Sub = Builder.CreateAdd(Sub, Offset, Sub->getName()+".off");
2862 Value *Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch");
2863 Builder.CreateCondBr(
2864 Cmp, SI->case_begin().getCaseSuccessor(), SI->getDefaultDest());
2866 // Prune obsolete incoming values off the successor's PHI nodes.
2867 for (BasicBlock::iterator BBI = SI->case_begin().getCaseSuccessor()->begin();
2868 isa<PHINode>(BBI); ++BBI) {
2869 for (unsigned I = 0, E = SI->getNumCases()-1; I != E; ++I)
2870 cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
2872 SI->eraseFromParent();
2877 /// EliminateDeadSwitchCases - Compute masked bits for the condition of a switch
2878 /// and use it to remove dead cases.
2879 static bool EliminateDeadSwitchCases(SwitchInst *SI) {
2880 Value *Cond = SI->getCondition();
2881 unsigned Bits = cast<IntegerType>(Cond->getType())->getBitWidth();
2882 APInt KnownZero(Bits, 0), KnownOne(Bits, 0);
2883 ComputeMaskedBits(Cond, KnownZero, KnownOne);
2885 // Gather dead cases.
2886 SmallVector<ConstantInt*, 8> DeadCases;
2887 for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) {
2888 if ((I.getCaseValue()->getValue() & KnownZero) != 0 ||
2889 (I.getCaseValue()->getValue() & KnownOne) != KnownOne) {
2890 DeadCases.push_back(I.getCaseValue());
2891 DEBUG(dbgs() << "SimplifyCFG: switch case '"
2892 << I.getCaseValue() << "' is dead.\n");
2896 // Remove dead cases from the switch.
2897 for (unsigned I = 0, E = DeadCases.size(); I != E; ++I) {
2898 SwitchInst::CaseIt Case = SI->findCaseValue(DeadCases[I]);
2899 assert(Case != SI->case_default() &&
2900 "Case was not found. Probably mistake in DeadCases forming.");
2901 // Prune unused values from PHI nodes.
2902 Case.getCaseSuccessor()->removePredecessor(SI->getParent());
2903 SI->removeCase(Case);
2906 return !DeadCases.empty();
2909 /// FindPHIForConditionForwarding - If BB would be eligible for simplification
2910 /// by TryToSimplifyUncondBranchFromEmptyBlock (i.e. it is empty and terminated
2911 /// by an unconditional branch), look at the phi node for BB in the successor
2912 /// block and see if the incoming value is equal to CaseValue. If so, return
2913 /// the phi node, and set PhiIndex to BB's index in the phi node.
2914 static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue,
2917 if (BB->getFirstNonPHIOrDbg() != BB->getTerminator())
2918 return NULL; // BB must be empty to be a candidate for simplification.
2919 if (!BB->getSinglePredecessor())
2920 return NULL; // BB must be dominated by the switch.
2922 BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator());
2923 if (!Branch || !Branch->isUnconditional())
2924 return NULL; // Terminator must be unconditional branch.
2926 BasicBlock *Succ = Branch->getSuccessor(0);
2928 BasicBlock::iterator I = Succ->begin();
2929 while (PHINode *PHI = dyn_cast<PHINode>(I++)) {
2930 int Idx = PHI->getBasicBlockIndex(BB);
2931 assert(Idx >= 0 && "PHI has no entry for predecessor?");
2933 Value *InValue = PHI->getIncomingValue(Idx);
2934 if (InValue != CaseValue) continue;
2943 /// ForwardSwitchConditionToPHI - Try to forward the condition of a switch
2944 /// instruction to a phi node dominated by the switch, if that would mean that
2945 /// some of the destination blocks of the switch can be folded away.
2946 /// Returns true if a change is made.
2947 static bool ForwardSwitchConditionToPHI(SwitchInst *SI) {
2948 typedef DenseMap<PHINode*, SmallVector<int,4> > ForwardingNodesMap;
2949 ForwardingNodesMap ForwardingNodes;
2951 for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) {
2952 ConstantInt *CaseValue = I.getCaseValue();
2953 BasicBlock *CaseDest = I.getCaseSuccessor();
2956 PHINode *PHI = FindPHIForConditionForwarding(CaseValue, CaseDest,
2960 ForwardingNodes[PHI].push_back(PhiIndex);
2963 bool Changed = false;
2965 for (ForwardingNodesMap::iterator I = ForwardingNodes.begin(),
2966 E = ForwardingNodes.end(); I != E; ++I) {
2967 PHINode *Phi = I->first;
2968 SmallVector<int,4> &Indexes = I->second;
2970 if (Indexes.size() < 2) continue;
2972 for (size_t I = 0, E = Indexes.size(); I != E; ++I)
2973 Phi->setIncomingValue(Indexes[I], SI->getCondition());
2980 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
2981 // If this switch is too complex to want to look at, ignore it.
2982 if (!isValueEqualityComparison(SI))
2985 BasicBlock *BB = SI->getParent();
2987 // If we only have one predecessor, and if it is a branch on this value,
2988 // see if that predecessor totally determines the outcome of this switch.
2989 if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
2990 if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
2991 return SimplifyCFG(BB) | true;
2993 Value *Cond = SI->getCondition();
2994 if (SelectInst *Select = dyn_cast<SelectInst>(Cond))
2995 if (SimplifySwitchOnSelect(SI, Select))
2996 return SimplifyCFG(BB) | true;
2998 // If the block only contains the switch, see if we can fold the block
2999 // away into any preds.
3000 BasicBlock::iterator BBI = BB->begin();
3001 // Ignore dbg intrinsics.
3002 while (isa<DbgInfoIntrinsic>(BBI))
3005 if (FoldValueComparisonIntoPredecessors(SI, Builder))
3006 return SimplifyCFG(BB) | true;
3008 // Try to transform the switch into an icmp and a branch.
3009 if (TurnSwitchRangeIntoICmp(SI, Builder))
3010 return SimplifyCFG(BB) | true;
3012 // Remove unreachable cases.
3013 if (EliminateDeadSwitchCases(SI))
3014 return SimplifyCFG(BB) | true;
3016 if (ForwardSwitchConditionToPHI(SI))
3017 return SimplifyCFG(BB) | true;
3022 bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) {
3023 BasicBlock *BB = IBI->getParent();
3024 bool Changed = false;
3026 // Eliminate redundant destinations.
3027 SmallPtrSet<Value *, 8> Succs;
3028 for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
3029 BasicBlock *Dest = IBI->getDestination(i);
3030 if (!Dest->hasAddressTaken() || !Succs.insert(Dest)) {
3031 Dest->removePredecessor(BB);
3032 IBI->removeDestination(i);
3038 if (IBI->getNumDestinations() == 0) {
3039 // If the indirectbr has no successors, change it to unreachable.
3040 new UnreachableInst(IBI->getContext(), IBI);
3041 EraseTerminatorInstAndDCECond(IBI);
3045 if (IBI->getNumDestinations() == 1) {
3046 // If the indirectbr has one successor, change it to a direct branch.
3047 BranchInst::Create(IBI->getDestination(0), IBI);
3048 EraseTerminatorInstAndDCECond(IBI);
3052 if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) {
3053 if (SimplifyIndirectBrOnSelect(IBI, SI))
3054 return SimplifyCFG(BB) | true;
3059 bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){
3060 BasicBlock *BB = BI->getParent();
3062 // If the Terminator is the only non-phi instruction, simplify the block.
3063 BasicBlock::iterator I = BB->getFirstNonPHIOrDbgOrLifetime();
3064 if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() &&
3065 TryToSimplifyUncondBranchFromEmptyBlock(BB))
3068 // If the only instruction in the block is a seteq/setne comparison
3069 // against a constant, try to simplify the block.
3070 if (ICmpInst *ICI = dyn_cast<ICmpInst>(I))
3071 if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) {
3072 for (++I; isa<DbgInfoIntrinsic>(I); ++I)
3074 if (I->isTerminator() &&
3075 TryToSimplifyUncondBranchWithICmpInIt(ICI, TD, Builder))
3079 // If this basic block is ONLY a compare and a branch, and if a predecessor
3080 // branches to us and our successor, fold the comparison into the
3081 // predecessor and use logical operations to update the incoming value
3082 // for PHI nodes in common successor.
3083 if (FoldBranchToCommonDest(BI))
3084 return SimplifyCFG(BB) | true;
3089 bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
3090 BasicBlock *BB = BI->getParent();
3092 // Conditional branch
3093 if (isValueEqualityComparison(BI)) {
3094 // If we only have one predecessor, and if it is a branch on this value,
3095 // see if that predecessor totally determines the outcome of this
3097 if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
3098 if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
3099 return SimplifyCFG(BB) | true;
3101 // This block must be empty, except for the setcond inst, if it exists.
3102 // Ignore dbg intrinsics.
3103 BasicBlock::iterator I = BB->begin();
3104 // Ignore dbg intrinsics.
3105 while (isa<DbgInfoIntrinsic>(I))
3108 if (FoldValueComparisonIntoPredecessors(BI, Builder))
3109 return SimplifyCFG(BB) | true;
3110 } else if (&*I == cast<Instruction>(BI->getCondition())){
3112 // Ignore dbg intrinsics.
3113 while (isa<DbgInfoIntrinsic>(I))
3115 if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
3116 return SimplifyCFG(BB) | true;
3120 // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction.
3121 if (SimplifyBranchOnICmpChain(BI, TD, Builder))
3124 // If this basic block is ONLY a compare and a branch, and if a predecessor
3125 // branches to us and one of our successors, fold the comparison into the
3126 // predecessor and use logical operations to pick the right destination.
3127 if (FoldBranchToCommonDest(BI))
3128 return SimplifyCFG(BB) | true;
3130 // We have a conditional branch to two blocks that are only reachable
3131 // from BI. We know that the condbr dominates the two blocks, so see if
3132 // there is any identical code in the "then" and "else" blocks. If so, we
3133 // can hoist it up to the branching block.
3134 if (BI->getSuccessor(0)->getSinglePredecessor() != 0) {
3135 if (BI->getSuccessor(1)->getSinglePredecessor() != 0) {
3136 if (HoistThenElseCodeToIf(BI))
3137 return SimplifyCFG(BB) | true;
3139 // If Successor #1 has multiple preds, we may be able to conditionally
3140 // execute Successor #0 if it branches to successor #1.
3141 TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator();
3142 if (Succ0TI->getNumSuccessors() == 1 &&
3143 Succ0TI->getSuccessor(0) == BI->getSuccessor(1))
3144 if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0)))
3145 return SimplifyCFG(BB) | true;
3147 } else if (BI->getSuccessor(1)->getSinglePredecessor() != 0) {
3148 // If Successor #0 has multiple preds, we may be able to conditionally
3149 // execute Successor #1 if it branches to successor #0.
3150 TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator();
3151 if (Succ1TI->getNumSuccessors() == 1 &&
3152 Succ1TI->getSuccessor(0) == BI->getSuccessor(0))
3153 if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1)))
3154 return SimplifyCFG(BB) | true;
3157 // If this is a branch on a phi node in the current block, thread control
3158 // through this block if any PHI node entries are constants.
3159 if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition()))
3160 if (PN->getParent() == BI->getParent())
3161 if (FoldCondBranchOnPHI(BI, TD))
3162 return SimplifyCFG(BB) | true;
3164 // Scan predecessor blocks for conditional branches.
3165 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
3166 if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
3167 if (PBI != BI && PBI->isConditional())
3168 if (SimplifyCondBranchToCondBranch(PBI, BI))
3169 return SimplifyCFG(BB) | true;
3174 /// Check if passing a value to an instruction will cause undefined behavior.
3175 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) {
3176 Constant *C = dyn_cast<Constant>(V);
3180 if (!I->hasOneUse()) // Only look at single-use instructions, for compile time
3183 if (C->isNullValue()) {
3184 Instruction *Use = I->use_back();
3186 // Now make sure that there are no instructions in between that can alter
3187 // control flow (eg. calls)
3188 for (BasicBlock::iterator i = ++BasicBlock::iterator(I); &*i != Use; ++i)
3189 if (i == I->getParent()->end() || i->mayHaveSideEffects())
3192 // Look through GEPs. A load from a GEP derived from NULL is still undefined
3193 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Use))
3194 if (GEP->getPointerOperand() == I)
3195 return passingValueIsAlwaysUndefined(V, GEP);
3197 // Look through bitcasts.
3198 if (BitCastInst *BC = dyn_cast<BitCastInst>(Use))
3199 return passingValueIsAlwaysUndefined(V, BC);
3201 // Load from null is undefined.
3202 if (LoadInst *LI = dyn_cast<LoadInst>(Use))
3203 return LI->getPointerAddressSpace() == 0;
3205 // Store to null is undefined.
3206 if (StoreInst *SI = dyn_cast<StoreInst>(Use))
3207 return SI->getPointerAddressSpace() == 0 && SI->getPointerOperand() == I;
3212 /// If BB has an incoming value that will always trigger undefined behavior
3213 /// (eg. null pointer dereference), remove the branch leading here.
3214 static bool removeUndefIntroducingPredecessor(BasicBlock *BB) {
3215 for (BasicBlock::iterator i = BB->begin();
3216 PHINode *PHI = dyn_cast<PHINode>(i); ++i)
3217 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
3218 if (passingValueIsAlwaysUndefined(PHI->getIncomingValue(i), PHI)) {
3219 TerminatorInst *T = PHI->getIncomingBlock(i)->getTerminator();
3220 IRBuilder<> Builder(T);
3221 if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
3222 BB->removePredecessor(PHI->getIncomingBlock(i));
3223 // Turn uncoditional branches into unreachables and remove the dead
3224 // destination from conditional branches.
3225 if (BI->isUnconditional())
3226 Builder.CreateUnreachable();
3228 Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) :
3229 BI->getSuccessor(0));
3230 BI->eraseFromParent();
3233 // TODO: SwitchInst.
3239 bool SimplifyCFGOpt::run(BasicBlock *BB) {
3240 bool Changed = false;
3242 assert(BB && BB->getParent() && "Block not embedded in function!");
3243 assert(BB->getTerminator() && "Degenerate basic block encountered!");
3245 // Remove basic blocks that have no predecessors (except the entry block)...
3246 // or that just have themself as a predecessor. These are unreachable.
3247 if ((pred_begin(BB) == pred_end(BB) &&
3248 BB != &BB->getParent()->getEntryBlock()) ||
3249 BB->getSinglePredecessor() == BB) {
3250 DEBUG(dbgs() << "Removing BB: \n" << *BB);
3251 DeleteDeadBlock(BB);
3255 // Check to see if we can constant propagate this terminator instruction
3257 Changed |= ConstantFoldTerminator(BB, true);
3259 // Check for and eliminate duplicate PHI nodes in this block.
3260 Changed |= EliminateDuplicatePHINodes(BB);
3262 // Check for and remove branches that will always cause undefined behavior.
3263 Changed |= removeUndefIntroducingPredecessor(BB);
3265 // Merge basic blocks into their predecessor if there is only one distinct
3266 // pred, and if there is only one distinct successor of the predecessor, and
3267 // if there are no PHI nodes.
3269 if (MergeBlockIntoPredecessor(BB))
3272 IRBuilder<> Builder(BB);
3274 // If there is a trivial two-entry PHI node in this basic block, and we can
3275 // eliminate it, do so now.
3276 if (PHINode *PN = dyn_cast<PHINode>(BB->begin()))
3277 if (PN->getNumIncomingValues() == 2)
3278 Changed |= FoldTwoEntryPHINode(PN, TD);
3280 Builder.SetInsertPoint(BB->getTerminator());
3281 if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
3282 if (BI->isUnconditional()) {
3283 if (SimplifyUncondBranch(BI, Builder)) return true;
3285 if (SimplifyCondBranch(BI, Builder)) return true;
3287 } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
3288 if (SimplifyReturn(RI, Builder)) return true;
3289 } else if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) {
3290 if (SimplifyResume(RI, Builder)) return true;
3291 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
3292 if (SimplifySwitch(SI, Builder)) return true;
3293 } else if (UnreachableInst *UI =
3294 dyn_cast<UnreachableInst>(BB->getTerminator())) {
3295 if (SimplifyUnreachable(UI)) return true;
3296 } else if (IndirectBrInst *IBI =
3297 dyn_cast<IndirectBrInst>(BB->getTerminator())) {
3298 if (SimplifyIndirectBr(IBI)) return true;
3304 /// SimplifyCFG - This function is used to do simplification of a CFG. For
3305 /// example, it adjusts branches to branches to eliminate the extra hop, it
3306 /// eliminates unreachable basic blocks, and does other "peephole" optimization
3307 /// of the CFG. It returns true if a modification was made.
3309 bool llvm::SimplifyCFG(BasicBlock *BB, const TargetData *TD) {
3310 return SimplifyCFGOpt(TD).run(BB);