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