1 //===- DFAJumpThreading.cpp - Threads a switch statement inside a loop ----===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Transform each threading path to effectively jump thread the DFA. For 10 // example, the CFG below could be transformed as follows, where the cloned 11 // blocks unconditionally branch to the next correct case based on what is 12 // identified in the analysis. 13 // 14 // sw.bb sw.bb 15 // / | \ / | \ 16 // case1 case2 case3 case1 case2 case3 17 // \ | / | | | 18 // determinator det.2 det.3 det.1 19 // br sw.bb / | \ 20 // sw.bb.2 sw.bb.3 sw.bb.1 21 // br case2 br case3 br case1§ 22 // 23 // Definitions and Terminology: 24 // 25 // * Threading path: 26 // a list of basic blocks, the exit state, and the block that determines 27 // the next state, for which the following notation will be used: 28 // < path of BBs that form a cycle > [ state, determinator ] 29 // 30 // * Predictable switch: 31 // The switch variable is always a known constant so that all conditional 32 // jumps based on switch variable can be converted to unconditional jump. 33 // 34 // * Determinator: 35 // The basic block that determines the next state of the DFA. 36 // 37 // Representing the optimization in C-like pseudocode: the code pattern on the 38 // left could functionally be transformed to the right pattern if the switch 39 // condition is predictable. 40 // 41 // X = A goto A 42 // for (...) A: 43 // switch (X) ... 44 // case A goto B 45 // X = B B: 46 // case B ... 47 // X = C goto C 48 // 49 // The pass first checks that switch variable X is decided by the control flow 50 // path taken in the loop; for example, in case B, the next value of X is 51 // decided to be C. It then enumerates through all paths in the loop and labels 52 // the basic blocks where the next state is decided. 53 // 54 // Using this information it creates new paths that unconditionally branch to 55 // the next case. This involves cloning code, so it only gets triggered if the 56 // amount of code duplicated is below a threshold. 57 // 58 //===----------------------------------------------------------------------===// 59 60 #include "llvm/Transforms/Scalar/DFAJumpThreading.h" 61 #include "llvm/ADT/APInt.h" 62 #include "llvm/ADT/DenseMap.h" 63 #include "llvm/ADT/SmallSet.h" 64 #include "llvm/ADT/Statistic.h" 65 #include "llvm/Analysis/AssumptionCache.h" 66 #include "llvm/Analysis/CodeMetrics.h" 67 #include "llvm/Analysis/DomTreeUpdater.h" 68 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 69 #include "llvm/Analysis/TargetTransformInfo.h" 70 #include "llvm/IR/CFG.h" 71 #include "llvm/IR/Constants.h" 72 #include "llvm/IR/IntrinsicInst.h" 73 #include "llvm/Support/CommandLine.h" 74 #include "llvm/Support/Debug.h" 75 #include "llvm/Transforms/Utils/Cloning.h" 76 #include "llvm/Transforms/Utils/SSAUpdaterBulk.h" 77 #include "llvm/Transforms/Utils/ValueMapper.h" 78 #include <algorithm> 79 #include <deque> 80 81 #ifdef EXPENSIVE_CHECKS 82 #include "llvm/IR/Verifier.h" 83 #endif 84 85 using namespace llvm; 86 87 #define DEBUG_TYPE "dfa-jump-threading" 88 89 STATISTIC(NumTransforms, "Number of transformations done"); 90 STATISTIC(NumCloned, "Number of blocks cloned"); 91 STATISTIC(NumPaths, "Number of individual paths threaded"); 92 93 static cl::opt<bool> 94 ClViewCfgBefore("dfa-jump-view-cfg-before", 95 cl::desc("View the CFG before DFA Jump Threading"), 96 cl::Hidden, cl::init(false)); 97 98 static cl::opt<unsigned> MaxPathLength( 99 "dfa-max-path-length", 100 cl::desc("Max number of blocks searched to find a threading path"), 101 cl::Hidden, cl::init(20)); 102 103 static cl::opt<unsigned> 104 MaxNumPaths("dfa-max-num-paths", 105 cl::desc("Max number of paths enumerated around a switch"), 106 cl::Hidden, cl::init(200)); 107 108 static cl::opt<unsigned> 109 CostThreshold("dfa-cost-threshold", 110 cl::desc("Maximum cost accepted for the transformation"), 111 cl::Hidden, cl::init(50)); 112 113 namespace { 114 115 class SelectInstToUnfold { 116 SelectInst *SI; 117 PHINode *SIUse; 118 119 public: 120 SelectInstToUnfold(SelectInst *SI, PHINode *SIUse) : SI(SI), SIUse(SIUse) {} 121 122 SelectInst *getInst() { return SI; } 123 PHINode *getUse() { return SIUse; } 124 125 explicit operator bool() const { return SI && SIUse; } 126 }; 127 128 void unfold(DomTreeUpdater *DTU, SelectInstToUnfold SIToUnfold, 129 std::vector<SelectInstToUnfold> *NewSIsToUnfold, 130 std::vector<BasicBlock *> *NewBBs); 131 132 class DFAJumpThreading { 133 public: 134 DFAJumpThreading(AssumptionCache *AC, DominatorTree *DT, 135 TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE) 136 : AC(AC), DT(DT), TTI(TTI), ORE(ORE) {} 137 138 bool run(Function &F); 139 140 private: 141 void 142 unfoldSelectInstrs(DominatorTree *DT, 143 const SmallVector<SelectInstToUnfold, 4> &SelectInsts) { 144 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); 145 SmallVector<SelectInstToUnfold, 4> Stack; 146 for (SelectInstToUnfold SIToUnfold : SelectInsts) 147 Stack.push_back(SIToUnfold); 148 149 while (!Stack.empty()) { 150 SelectInstToUnfold SIToUnfold = Stack.pop_back_val(); 151 152 std::vector<SelectInstToUnfold> NewSIsToUnfold; 153 std::vector<BasicBlock *> NewBBs; 154 unfold(&DTU, SIToUnfold, &NewSIsToUnfold, &NewBBs); 155 156 // Put newly discovered select instructions into the work list. 157 for (const SelectInstToUnfold &NewSIToUnfold : NewSIsToUnfold) 158 Stack.push_back(NewSIToUnfold); 159 } 160 } 161 162 AssumptionCache *AC; 163 DominatorTree *DT; 164 TargetTransformInfo *TTI; 165 OptimizationRemarkEmitter *ORE; 166 }; 167 168 } // end anonymous namespace 169 170 namespace { 171 172 /// Create a new basic block and sink \p SIToSink into it. 173 void createBasicBlockAndSinkSelectInst( 174 DomTreeUpdater *DTU, SelectInst *SI, PHINode *SIUse, SelectInst *SIToSink, 175 BasicBlock *EndBlock, StringRef NewBBName, BasicBlock **NewBlock, 176 BranchInst **NewBranch, std::vector<SelectInstToUnfold> *NewSIsToUnfold, 177 std::vector<BasicBlock *> *NewBBs) { 178 assert(SIToSink->hasOneUse()); 179 assert(NewBlock); 180 assert(NewBranch); 181 *NewBlock = BasicBlock::Create(SI->getContext(), NewBBName, 182 EndBlock->getParent(), EndBlock); 183 NewBBs->push_back(*NewBlock); 184 *NewBranch = BranchInst::Create(EndBlock, *NewBlock); 185 SIToSink->moveBefore(*NewBranch); 186 NewSIsToUnfold->push_back(SelectInstToUnfold(SIToSink, SIUse)); 187 DTU->applyUpdates({{DominatorTree::Insert, *NewBlock, EndBlock}}); 188 } 189 190 /// Unfold the select instruction held in \p SIToUnfold by replacing it with 191 /// control flow. 192 /// 193 /// Put newly discovered select instructions into \p NewSIsToUnfold. Put newly 194 /// created basic blocks into \p NewBBs. 195 /// 196 /// TODO: merge it with CodeGenPrepare::optimizeSelectInst() if possible. 197 void unfold(DomTreeUpdater *DTU, SelectInstToUnfold SIToUnfold, 198 std::vector<SelectInstToUnfold> *NewSIsToUnfold, 199 std::vector<BasicBlock *> *NewBBs) { 200 SelectInst *SI = SIToUnfold.getInst(); 201 PHINode *SIUse = SIToUnfold.getUse(); 202 BasicBlock *StartBlock = SI->getParent(); 203 BasicBlock *EndBlock = SIUse->getParent(); 204 BranchInst *StartBlockTerm = 205 dyn_cast<BranchInst>(StartBlock->getTerminator()); 206 207 assert(StartBlockTerm && StartBlockTerm->isUnconditional()); 208 assert(SI->hasOneUse()); 209 210 // These are the new basic blocks for the conditional branch. 211 // At least one will become an actual new basic block. 212 BasicBlock *TrueBlock = nullptr; 213 BasicBlock *FalseBlock = nullptr; 214 BranchInst *TrueBranch = nullptr; 215 BranchInst *FalseBranch = nullptr; 216 217 // Sink select instructions to be able to unfold them later. 218 if (SelectInst *SIOp = dyn_cast<SelectInst>(SI->getTrueValue())) { 219 createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock, 220 "si.unfold.true", &TrueBlock, &TrueBranch, 221 NewSIsToUnfold, NewBBs); 222 } 223 if (SelectInst *SIOp = dyn_cast<SelectInst>(SI->getFalseValue())) { 224 createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock, 225 "si.unfold.false", &FalseBlock, 226 &FalseBranch, NewSIsToUnfold, NewBBs); 227 } 228 229 // If there was nothing to sink, then arbitrarily choose the 'false' side 230 // for a new input value to the PHI. 231 if (!TrueBlock && !FalseBlock) { 232 FalseBlock = BasicBlock::Create(SI->getContext(), "si.unfold.false", 233 EndBlock->getParent(), EndBlock); 234 NewBBs->push_back(FalseBlock); 235 BranchInst::Create(EndBlock, FalseBlock); 236 DTU->applyUpdates({{DominatorTree::Insert, FalseBlock, EndBlock}}); 237 } 238 239 // Insert the real conditional branch based on the original condition. 240 // If we did not create a new block for one of the 'true' or 'false' paths 241 // of the condition, it means that side of the branch goes to the end block 242 // directly and the path originates from the start block from the point of 243 // view of the new PHI. 244 BasicBlock *TT = EndBlock; 245 BasicBlock *FT = EndBlock; 246 if (TrueBlock && FalseBlock) { 247 // A diamond. 248 TT = TrueBlock; 249 FT = FalseBlock; 250 251 // Update the phi node of SI. 252 SIUse->addIncoming(SI->getTrueValue(), TrueBlock); 253 SIUse->addIncoming(SI->getFalseValue(), FalseBlock); 254 255 // Update any other PHI nodes in EndBlock. 256 for (PHINode &Phi : EndBlock->phis()) { 257 if (&Phi != SIUse) { 258 Value *OrigValue = Phi.getIncomingValueForBlock(StartBlock); 259 Phi.addIncoming(OrigValue, TrueBlock); 260 Phi.addIncoming(OrigValue, FalseBlock); 261 } 262 263 // Remove incoming place of original StartBlock, which comes in a indirect 264 // way (through TrueBlock and FalseBlock) now. 265 Phi.removeIncomingValue(StartBlock, /* DeletePHIIfEmpty = */ false); 266 } 267 } else { 268 BasicBlock *NewBlock = nullptr; 269 Value *SIOp1 = SI->getTrueValue(); 270 Value *SIOp2 = SI->getFalseValue(); 271 272 // A triangle pointing right. 273 if (!TrueBlock) { 274 NewBlock = FalseBlock; 275 FT = FalseBlock; 276 } 277 // A triangle pointing left. 278 else { 279 NewBlock = TrueBlock; 280 TT = TrueBlock; 281 std::swap(SIOp1, SIOp2); 282 } 283 284 // Update the phi node of SI. 285 for (unsigned Idx = 0; Idx < SIUse->getNumIncomingValues(); ++Idx) { 286 if (SIUse->getIncomingBlock(Idx) == StartBlock) 287 SIUse->setIncomingValue(Idx, SIOp1); 288 } 289 SIUse->addIncoming(SIOp2, NewBlock); 290 291 // Update any other PHI nodes in EndBlock. 292 for (auto II = EndBlock->begin(); PHINode *Phi = dyn_cast<PHINode>(II); 293 ++II) { 294 if (Phi != SIUse) 295 Phi->addIncoming(Phi->getIncomingValueForBlock(StartBlock), NewBlock); 296 } 297 } 298 StartBlockTerm->eraseFromParent(); 299 BranchInst::Create(TT, FT, SI->getCondition(), StartBlock); 300 DTU->applyUpdates({{DominatorTree::Insert, StartBlock, TT}, 301 {DominatorTree::Insert, StartBlock, FT}}); 302 303 // The select is now dead. 304 assert(SI->use_empty() && "Select must be dead now"); 305 SI->eraseFromParent(); 306 } 307 308 struct ClonedBlock { 309 BasicBlock *BB; 310 APInt State; ///< \p State corresponds to the next value of a switch stmnt. 311 }; 312 313 typedef std::deque<BasicBlock *> PathType; 314 typedef std::vector<PathType> PathsType; 315 typedef SmallPtrSet<const BasicBlock *, 8> VisitedBlocks; 316 typedef std::vector<ClonedBlock> CloneList; 317 318 // This data structure keeps track of all blocks that have been cloned. If two 319 // different ThreadingPaths clone the same block for a certain state it should 320 // be reused, and it can be looked up in this map. 321 typedef DenseMap<BasicBlock *, CloneList> DuplicateBlockMap; 322 323 // This map keeps track of all the new definitions for an instruction. This 324 // information is needed when restoring SSA form after cloning blocks. 325 typedef MapVector<Instruction *, std::vector<Instruction *>> DefMap; 326 327 inline raw_ostream &operator<<(raw_ostream &OS, const PathType &Path) { 328 OS << "< "; 329 for (const BasicBlock *BB : Path) { 330 std::string BBName; 331 if (BB->hasName()) 332 raw_string_ostream(BBName) << BB->getName(); 333 else 334 raw_string_ostream(BBName) << BB; 335 OS << BBName << " "; 336 } 337 OS << ">"; 338 return OS; 339 } 340 341 /// ThreadingPath is a path in the control flow of a loop that can be threaded 342 /// by cloning necessary basic blocks and replacing conditional branches with 343 /// unconditional ones. A threading path includes a list of basic blocks, the 344 /// exit state, and the block that determines the next state. 345 struct ThreadingPath { 346 /// Exit value is DFA's exit state for the given path. 347 APInt getExitValue() const { return ExitVal; } 348 void setExitValue(const ConstantInt *V) { 349 ExitVal = V->getValue(); 350 IsExitValSet = true; 351 } 352 bool isExitValueSet() const { return IsExitValSet; } 353 354 /// Determinator is the basic block that determines the next state of the DFA. 355 const BasicBlock *getDeterminatorBB() const { return DBB; } 356 void setDeterminator(const BasicBlock *BB) { DBB = BB; } 357 358 /// Path is a list of basic blocks. 359 const PathType &getPath() const { return Path; } 360 void setPath(const PathType &NewPath) { Path = NewPath; } 361 362 void print(raw_ostream &OS) const { 363 OS << Path << " [ " << ExitVal << ", " << DBB->getName() << " ]"; 364 } 365 366 private: 367 PathType Path; 368 APInt ExitVal; 369 const BasicBlock *DBB = nullptr; 370 bool IsExitValSet = false; 371 }; 372 373 #ifndef NDEBUG 374 inline raw_ostream &operator<<(raw_ostream &OS, const ThreadingPath &TPath) { 375 TPath.print(OS); 376 return OS; 377 } 378 #endif 379 380 struct MainSwitch { 381 MainSwitch(SwitchInst *SI, OptimizationRemarkEmitter *ORE) { 382 if (isCandidate(SI)) { 383 Instr = SI; 384 } else { 385 ORE->emit([&]() { 386 return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable", SI) 387 << "Switch instruction is not predictable."; 388 }); 389 } 390 } 391 392 virtual ~MainSwitch() = default; 393 394 SwitchInst *getInstr() const { return Instr; } 395 const SmallVector<SelectInstToUnfold, 4> getSelectInsts() { 396 return SelectInsts; 397 } 398 399 private: 400 /// Do a use-def chain traversal starting from the switch condition to see if 401 /// \p SI is a potential condidate. 402 /// 403 /// Also, collect select instructions to unfold. 404 bool isCandidate(const SwitchInst *SI) { 405 std::deque<Value *> Q; 406 SmallSet<Value *, 16> SeenValues; 407 SelectInsts.clear(); 408 409 Value *SICond = SI->getCondition(); 410 LLVM_DEBUG(dbgs() << "\tSICond: " << *SICond << "\n"); 411 if (!isa<PHINode>(SICond)) 412 return false; 413 414 addToQueue(SICond, Q, SeenValues); 415 416 while (!Q.empty()) { 417 Value *Current = Q.front(); 418 Q.pop_front(); 419 420 if (auto *Phi = dyn_cast<PHINode>(Current)) { 421 for (Value *Incoming : Phi->incoming_values()) { 422 addToQueue(Incoming, Q, SeenValues); 423 } 424 LLVM_DEBUG(dbgs() << "\tphi: " << *Phi << "\n"); 425 } else if (SelectInst *SelI = dyn_cast<SelectInst>(Current)) { 426 if (!isValidSelectInst(SelI)) 427 return false; 428 addToQueue(SelI->getTrueValue(), Q, SeenValues); 429 addToQueue(SelI->getFalseValue(), Q, SeenValues); 430 LLVM_DEBUG(dbgs() << "\tselect: " << *SelI << "\n"); 431 if (auto *SelIUse = dyn_cast<PHINode>(SelI->user_back())) 432 SelectInsts.push_back(SelectInstToUnfold(SelI, SelIUse)); 433 } else if (isa<Constant>(Current)) { 434 LLVM_DEBUG(dbgs() << "\tconst: " << *Current << "\n"); 435 continue; 436 } else { 437 LLVM_DEBUG(dbgs() << "\tother: " << *Current << "\n"); 438 // Allow unpredictable values. The hope is that those will be the 439 // initial switch values that can be ignored (they will hit the 440 // unthreaded switch) but this assumption will get checked later after 441 // paths have been enumerated (in function getStateDefMap). 442 continue; 443 } 444 } 445 446 return true; 447 } 448 449 void addToQueue(Value *Val, std::deque<Value *> &Q, 450 SmallSet<Value *, 16> &SeenValues) { 451 if (SeenValues.contains(Val)) 452 return; 453 Q.push_back(Val); 454 SeenValues.insert(Val); 455 } 456 457 bool isValidSelectInst(SelectInst *SI) { 458 if (!SI->hasOneUse()) 459 return false; 460 461 Instruction *SIUse = dyn_cast<Instruction>(SI->user_back()); 462 // The use of the select inst should be either a phi or another select. 463 if (!SIUse && !(isa<PHINode>(SIUse) || isa<SelectInst>(SIUse))) 464 return false; 465 466 BasicBlock *SIBB = SI->getParent(); 467 468 // Currently, we can only expand select instructions in basic blocks with 469 // one successor. 470 BranchInst *SITerm = dyn_cast<BranchInst>(SIBB->getTerminator()); 471 if (!SITerm || !SITerm->isUnconditional()) 472 return false; 473 474 // Only fold the select coming from directly where it is defined. 475 PHINode *PHIUser = dyn_cast<PHINode>(SIUse); 476 if (PHIUser && PHIUser->getIncomingBlock(*SI->use_begin()) != SIBB) 477 return false; 478 479 // If select will not be sunk during unfolding, and it is in the same basic 480 // block as another state defining select, then cannot unfold both. 481 for (SelectInstToUnfold SIToUnfold : SelectInsts) { 482 SelectInst *PrevSI = SIToUnfold.getInst(); 483 if (PrevSI->getTrueValue() != SI && PrevSI->getFalseValue() != SI && 484 PrevSI->getParent() == SI->getParent()) 485 return false; 486 } 487 488 return true; 489 } 490 491 SwitchInst *Instr = nullptr; 492 SmallVector<SelectInstToUnfold, 4> SelectInsts; 493 }; 494 495 struct AllSwitchPaths { 496 AllSwitchPaths(const MainSwitch *MSwitch, OptimizationRemarkEmitter *ORE) 497 : Switch(MSwitch->getInstr()), SwitchBlock(Switch->getParent()), 498 ORE(ORE) {} 499 500 std::vector<ThreadingPath> &getThreadingPaths() { return TPaths; } 501 unsigned getNumThreadingPaths() { return TPaths.size(); } 502 SwitchInst *getSwitchInst() { return Switch; } 503 BasicBlock *getSwitchBlock() { return SwitchBlock; } 504 505 void run() { 506 VisitedBlocks Visited; 507 PathsType LoopPaths = paths(SwitchBlock, Visited, /* PathDepth = */ 1); 508 StateDefMap StateDef = getStateDefMap(LoopPaths); 509 510 if (StateDef.empty()) { 511 ORE->emit([&]() { 512 return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable", 513 Switch) 514 << "Switch instruction is not predictable."; 515 }); 516 return; 517 } 518 519 for (PathType Path : LoopPaths) { 520 ThreadingPath TPath; 521 522 const BasicBlock *PrevBB = Path.back(); 523 for (const BasicBlock *BB : Path) { 524 if (StateDef.contains(BB)) { 525 const PHINode *Phi = dyn_cast<PHINode>(StateDef[BB]); 526 assert(Phi && "Expected a state-defining instr to be a phi node."); 527 528 const Value *V = Phi->getIncomingValueForBlock(PrevBB); 529 if (const ConstantInt *C = dyn_cast<const ConstantInt>(V)) { 530 TPath.setExitValue(C); 531 TPath.setDeterminator(BB); 532 TPath.setPath(Path); 533 } 534 } 535 536 // Switch block is the determinator, this is the final exit value. 537 if (TPath.isExitValueSet() && BB == Path.front()) 538 break; 539 540 PrevBB = BB; 541 } 542 543 if (TPath.isExitValueSet() && isSupported(TPath)) 544 TPaths.push_back(TPath); 545 } 546 } 547 548 private: 549 // Value: an instruction that defines a switch state; 550 // Key: the parent basic block of that instruction. 551 typedef DenseMap<const BasicBlock *, const PHINode *> StateDefMap; 552 553 PathsType paths(BasicBlock *BB, VisitedBlocks &Visited, 554 unsigned PathDepth) const { 555 PathsType Res; 556 557 // Stop exploring paths after visiting MaxPathLength blocks 558 if (PathDepth > MaxPathLength) { 559 ORE->emit([&]() { 560 return OptimizationRemarkAnalysis(DEBUG_TYPE, "MaxPathLengthReached", 561 Switch) 562 << "Exploration stopped after visiting MaxPathLength=" 563 << ore::NV("MaxPathLength", MaxPathLength) << " blocks."; 564 }); 565 return Res; 566 } 567 568 Visited.insert(BB); 569 570 // Some blocks have multiple edges to the same successor, and this set 571 // is used to prevent a duplicate path from being generated 572 SmallSet<BasicBlock *, 4> Successors; 573 for (BasicBlock *Succ : successors(BB)) { 574 if (!Successors.insert(Succ).second) 575 continue; 576 577 // Found a cycle through the SwitchBlock 578 if (Succ == SwitchBlock) { 579 Res.push_back({BB}); 580 continue; 581 } 582 583 // We have encountered a cycle, do not get caught in it 584 if (Visited.contains(Succ)) 585 continue; 586 587 PathsType SuccPaths = paths(Succ, Visited, PathDepth + 1); 588 for (const PathType &Path : SuccPaths) { 589 PathType NewPath(Path); 590 NewPath.push_front(BB); 591 Res.push_back(NewPath); 592 if (Res.size() >= MaxNumPaths) { 593 return Res; 594 } 595 } 596 } 597 // This block could now be visited again from a different predecessor. Note 598 // that this will result in exponential runtime. Subpaths could possibly be 599 // cached but it takes a lot of memory to store them. 600 Visited.erase(BB); 601 return Res; 602 } 603 604 /// Walk the use-def chain and collect all the state-defining instructions. 605 /// 606 /// Return an empty map if unpredictable values encountered inside the basic 607 /// blocks of \p LoopPaths. 608 StateDefMap getStateDefMap(const PathsType &LoopPaths) const { 609 StateDefMap Res; 610 611 // Basic blocks belonging to any of the loops around the switch statement. 612 SmallPtrSet<BasicBlock *, 16> LoopBBs; 613 for (const PathType &Path : LoopPaths) { 614 for (BasicBlock *BB : Path) 615 LoopBBs.insert(BB); 616 } 617 618 Value *FirstDef = Switch->getOperand(0); 619 620 assert(isa<PHINode>(FirstDef) && "The first definition must be a phi."); 621 622 SmallVector<PHINode *, 8> Stack; 623 Stack.push_back(dyn_cast<PHINode>(FirstDef)); 624 SmallSet<Value *, 16> SeenValues; 625 626 while (!Stack.empty()) { 627 PHINode *CurPhi = Stack.pop_back_val(); 628 629 Res[CurPhi->getParent()] = CurPhi; 630 SeenValues.insert(CurPhi); 631 632 for (BasicBlock *IncomingBB : CurPhi->blocks()) { 633 Value *Incoming = CurPhi->getIncomingValueForBlock(IncomingBB); 634 bool IsOutsideLoops = LoopBBs.count(IncomingBB) == 0; 635 if (Incoming == FirstDef || isa<ConstantInt>(Incoming) || 636 SeenValues.contains(Incoming) || IsOutsideLoops) { 637 continue; 638 } 639 640 // Any unpredictable value inside the loops means we must bail out. 641 if (!isa<PHINode>(Incoming)) 642 return StateDefMap(); 643 644 Stack.push_back(cast<PHINode>(Incoming)); 645 } 646 } 647 648 return Res; 649 } 650 651 /// The determinator BB should precede the switch-defining BB. 652 /// 653 /// Otherwise, it is possible that the state defined in the determinator block 654 /// defines the state for the next iteration of the loop, rather than for the 655 /// current one. 656 /// 657 /// Currently supported paths: 658 /// \code 659 /// < switch bb1 determ def > [ 42, determ ] 660 /// < switch_and_def bb1 determ > [ 42, determ ] 661 /// < switch_and_def_and_determ bb1 > [ 42, switch_and_def_and_determ ] 662 /// \endcode 663 /// 664 /// Unsupported paths: 665 /// \code 666 /// < switch bb1 def determ > [ 43, determ ] 667 /// < switch_and_determ bb1 def > [ 43, switch_and_determ ] 668 /// \endcode 669 bool isSupported(const ThreadingPath &TPath) { 670 Instruction *SwitchCondI = dyn_cast<Instruction>(Switch->getCondition()); 671 assert(SwitchCondI); 672 if (!SwitchCondI) 673 return false; 674 675 const BasicBlock *SwitchCondDefBB = SwitchCondI->getParent(); 676 const BasicBlock *SwitchCondUseBB = Switch->getParent(); 677 const BasicBlock *DeterminatorBB = TPath.getDeterminatorBB(); 678 679 assert( 680 SwitchCondUseBB == TPath.getPath().front() && 681 "The first BB in a threading path should have the switch instruction"); 682 if (SwitchCondUseBB != TPath.getPath().front()) 683 return false; 684 685 // Make DeterminatorBB the first element in Path. 686 PathType Path = TPath.getPath(); 687 auto ItDet = llvm::find(Path, DeterminatorBB); 688 std::rotate(Path.begin(), ItDet, Path.end()); 689 690 bool IsDetBBSeen = false; 691 bool IsDefBBSeen = false; 692 bool IsUseBBSeen = false; 693 for (BasicBlock *BB : Path) { 694 if (BB == DeterminatorBB) 695 IsDetBBSeen = true; 696 if (BB == SwitchCondDefBB) 697 IsDefBBSeen = true; 698 if (BB == SwitchCondUseBB) 699 IsUseBBSeen = true; 700 if (IsDetBBSeen && IsUseBBSeen && !IsDefBBSeen) 701 return false; 702 } 703 704 return true; 705 } 706 707 SwitchInst *Switch; 708 BasicBlock *SwitchBlock; 709 OptimizationRemarkEmitter *ORE; 710 std::vector<ThreadingPath> TPaths; 711 }; 712 713 struct TransformDFA { 714 TransformDFA(AllSwitchPaths *SwitchPaths, DominatorTree *DT, 715 AssumptionCache *AC, TargetTransformInfo *TTI, 716 OptimizationRemarkEmitter *ORE, 717 SmallPtrSet<const Value *, 32> EphValues) 718 : SwitchPaths(SwitchPaths), DT(DT), AC(AC), TTI(TTI), ORE(ORE), 719 EphValues(EphValues) {} 720 721 void run() { 722 if (isLegalAndProfitableToTransform()) { 723 createAllExitPaths(); 724 NumTransforms++; 725 } 726 } 727 728 private: 729 /// This function performs both a legality check and profitability check at 730 /// the same time since it is convenient to do so. It iterates through all 731 /// blocks that will be cloned, and keeps track of the duplication cost. It 732 /// also returns false if it is illegal to clone some required block. 733 bool isLegalAndProfitableToTransform() { 734 CodeMetrics Metrics; 735 SwitchInst *Switch = SwitchPaths->getSwitchInst(); 736 737 // Don't thread switch without multiple successors. 738 if (Switch->getNumSuccessors() <= 1) 739 return false; 740 741 // Note that DuplicateBlockMap is not being used as intended here. It is 742 // just being used to ensure (BB, State) pairs are only counted once. 743 DuplicateBlockMap DuplicateMap; 744 745 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) { 746 PathType PathBBs = TPath.getPath(); 747 APInt NextState = TPath.getExitValue(); 748 const BasicBlock *Determinator = TPath.getDeterminatorBB(); 749 750 // Update Metrics for the Switch block, this is always cloned 751 BasicBlock *BB = SwitchPaths->getSwitchBlock(); 752 BasicBlock *VisitedBB = getClonedBB(BB, NextState, DuplicateMap); 753 if (!VisitedBB) { 754 Metrics.analyzeBasicBlock(BB, *TTI, EphValues); 755 DuplicateMap[BB].push_back({BB, NextState}); 756 } 757 758 // If the Switch block is the Determinator, then we can continue since 759 // this is the only block that is cloned and we already counted for it. 760 if (PathBBs.front() == Determinator) 761 continue; 762 763 // Otherwise update Metrics for all blocks that will be cloned. If any 764 // block is already cloned and would be reused, don't double count it. 765 auto DetIt = llvm::find(PathBBs, Determinator); 766 for (auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) { 767 BB = *BBIt; 768 VisitedBB = getClonedBB(BB, NextState, DuplicateMap); 769 if (VisitedBB) 770 continue; 771 Metrics.analyzeBasicBlock(BB, *TTI, EphValues); 772 DuplicateMap[BB].push_back({BB, NextState}); 773 } 774 775 if (Metrics.notDuplicatable) { 776 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains " 777 << "non-duplicatable instructions.\n"); 778 ORE->emit([&]() { 779 return OptimizationRemarkMissed(DEBUG_TYPE, "NonDuplicatableInst", 780 Switch) 781 << "Contains non-duplicatable instructions."; 782 }); 783 return false; 784 } 785 786 if (Metrics.convergent) { 787 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains " 788 << "convergent instructions.\n"); 789 ORE->emit([&]() { 790 return OptimizationRemarkMissed(DEBUG_TYPE, "ConvergentInst", Switch) 791 << "Contains convergent instructions."; 792 }); 793 return false; 794 } 795 796 if (!Metrics.NumInsts.isValid()) { 797 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains " 798 << "instructions with invalid cost.\n"); 799 ORE->emit([&]() { 800 return OptimizationRemarkMissed(DEBUG_TYPE, "ConvergentInst", Switch) 801 << "Contains instructions with invalid cost."; 802 }); 803 return false; 804 } 805 } 806 807 InstructionCost DuplicationCost = 0; 808 809 unsigned JumpTableSize = 0; 810 TTI->getEstimatedNumberOfCaseClusters(*Switch, JumpTableSize, nullptr, 811 nullptr); 812 if (JumpTableSize == 0) { 813 // Factor in the number of conditional branches reduced from jump 814 // threading. Assume that lowering the switch block is implemented by 815 // using binary search, hence the LogBase2(). 816 unsigned CondBranches = 817 APInt(32, Switch->getNumSuccessors()).ceilLogBase2(); 818 assert(CondBranches > 0 && 819 "The threaded switch must have multiple branches"); 820 DuplicationCost = Metrics.NumInsts / CondBranches; 821 } else { 822 // Compared with jump tables, the DFA optimizer removes an indirect branch 823 // on each loop iteration, thus making branch prediction more precise. The 824 // more branch targets there are, the more likely it is for the branch 825 // predictor to make a mistake, and the more benefit there is in the DFA 826 // optimizer. Thus, the more branch targets there are, the lower is the 827 // cost of the DFA opt. 828 DuplicationCost = Metrics.NumInsts / JumpTableSize; 829 } 830 831 LLVM_DEBUG(dbgs() << "\nDFA Jump Threading: Cost to jump thread block " 832 << SwitchPaths->getSwitchBlock()->getName() 833 << " is: " << DuplicationCost << "\n\n"); 834 835 if (DuplicationCost > CostThreshold) { 836 LLVM_DEBUG(dbgs() << "Not jump threading, duplication cost exceeds the " 837 << "cost threshold.\n"); 838 ORE->emit([&]() { 839 return OptimizationRemarkMissed(DEBUG_TYPE, "NotProfitable", Switch) 840 << "Duplication cost exceeds the cost threshold (cost=" 841 << ore::NV("Cost", DuplicationCost) 842 << ", threshold=" << ore::NV("Threshold", CostThreshold) << ")."; 843 }); 844 return false; 845 } 846 847 ORE->emit([&]() { 848 return OptimizationRemark(DEBUG_TYPE, "JumpThreaded", Switch) 849 << "Switch statement jump-threaded."; 850 }); 851 852 return true; 853 } 854 855 /// Transform each threading path to effectively jump thread the DFA. 856 void createAllExitPaths() { 857 DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Eager); 858 859 // Move the switch block to the end of the path, since it will be duplicated 860 BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock(); 861 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) { 862 LLVM_DEBUG(dbgs() << TPath << "\n"); 863 PathType NewPath(TPath.getPath()); 864 NewPath.push_back(SwitchBlock); 865 TPath.setPath(NewPath); 866 } 867 868 // Transform the ThreadingPaths and keep track of the cloned values 869 DuplicateBlockMap DuplicateMap; 870 DefMap NewDefs; 871 872 SmallSet<BasicBlock *, 16> BlocksToClean; 873 for (BasicBlock *BB : successors(SwitchBlock)) 874 BlocksToClean.insert(BB); 875 876 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) { 877 createExitPath(NewDefs, TPath, DuplicateMap, BlocksToClean, &DTU); 878 NumPaths++; 879 } 880 881 // After all paths are cloned, now update the last successor of the cloned 882 // path so it skips over the switch statement 883 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) 884 updateLastSuccessor(TPath, DuplicateMap, &DTU); 885 886 // For each instruction that was cloned and used outside, update its uses 887 updateSSA(NewDefs); 888 889 // Clean PHI Nodes for the newly created blocks 890 for (BasicBlock *BB : BlocksToClean) 891 cleanPhiNodes(BB); 892 } 893 894 /// For a specific ThreadingPath \p Path, create an exit path starting from 895 /// the determinator block. 896 /// 897 /// To remember the correct destination, we have to duplicate blocks 898 /// corresponding to each state. Also update the terminating instruction of 899 /// the predecessors, and phis in the successor blocks. 900 void createExitPath(DefMap &NewDefs, ThreadingPath &Path, 901 DuplicateBlockMap &DuplicateMap, 902 SmallSet<BasicBlock *, 16> &BlocksToClean, 903 DomTreeUpdater *DTU) { 904 APInt NextState = Path.getExitValue(); 905 const BasicBlock *Determinator = Path.getDeterminatorBB(); 906 PathType PathBBs = Path.getPath(); 907 908 // Don't select the placeholder block in front 909 if (PathBBs.front() == Determinator) 910 PathBBs.pop_front(); 911 912 auto DetIt = llvm::find(PathBBs, Determinator); 913 // When there is only one BB in PathBBs, the determinator takes itself as a 914 // direct predecessor. 915 BasicBlock *PrevBB = PathBBs.size() == 1 ? *DetIt : *std::prev(DetIt); 916 for (auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) { 917 BasicBlock *BB = *BBIt; 918 BlocksToClean.insert(BB); 919 920 // We already cloned BB for this NextState, now just update the branch 921 // and continue. 922 BasicBlock *NextBB = getClonedBB(BB, NextState, DuplicateMap); 923 if (NextBB) { 924 updatePredecessor(PrevBB, BB, NextBB, DTU); 925 PrevBB = NextBB; 926 continue; 927 } 928 929 // Clone the BB and update the successor of Prev to jump to the new block 930 BasicBlock *NewBB = cloneBlockAndUpdatePredecessor( 931 BB, PrevBB, NextState, DuplicateMap, NewDefs, DTU); 932 DuplicateMap[BB].push_back({NewBB, NextState}); 933 BlocksToClean.insert(NewBB); 934 PrevBB = NewBB; 935 } 936 } 937 938 /// Restore SSA form after cloning blocks. 939 /// 940 /// Each cloned block creates new defs for a variable, and the uses need to be 941 /// updated to reflect this. The uses may be replaced with a cloned value, or 942 /// some derived phi instruction. Note that all uses of a value defined in the 943 /// same block were already remapped when cloning the block. 944 void updateSSA(DefMap &NewDefs) { 945 SSAUpdaterBulk SSAUpdate; 946 SmallVector<Use *, 16> UsesToRename; 947 948 for (const auto &KV : NewDefs) { 949 Instruction *I = KV.first; 950 BasicBlock *BB = I->getParent(); 951 std::vector<Instruction *> Cloned = KV.second; 952 953 // Scan all uses of this instruction to see if it is used outside of its 954 // block, and if so, record them in UsesToRename. 955 for (Use &U : I->uses()) { 956 Instruction *User = cast<Instruction>(U.getUser()); 957 if (PHINode *UserPN = dyn_cast<PHINode>(User)) { 958 if (UserPN->getIncomingBlock(U) == BB) 959 continue; 960 } else if (User->getParent() == BB) { 961 continue; 962 } 963 964 UsesToRename.push_back(&U); 965 } 966 967 // If there are no uses outside the block, we're done with this 968 // instruction. 969 if (UsesToRename.empty()) 970 continue; 971 LLVM_DEBUG(dbgs() << "DFA-JT: Renaming non-local uses of: " << *I 972 << "\n"); 973 974 // We found a use of I outside of BB. Rename all uses of I that are 975 // outside its block to be uses of the appropriate PHI node etc. See 976 // ValuesInBlocks with the values we know. 977 unsigned VarNum = SSAUpdate.AddVariable(I->getName(), I->getType()); 978 SSAUpdate.AddAvailableValue(VarNum, BB, I); 979 for (Instruction *New : Cloned) 980 SSAUpdate.AddAvailableValue(VarNum, New->getParent(), New); 981 982 while (!UsesToRename.empty()) 983 SSAUpdate.AddUse(VarNum, UsesToRename.pop_back_val()); 984 985 LLVM_DEBUG(dbgs() << "\n"); 986 } 987 // SSAUpdater handles phi placement and renaming uses with the appropriate 988 // value. 989 SSAUpdate.RewriteAllUses(DT); 990 } 991 992 /// Clones a basic block, and adds it to the CFG. 993 /// 994 /// This function also includes updating phi nodes in the successors of the 995 /// BB, and remapping uses that were defined locally in the cloned BB. 996 BasicBlock *cloneBlockAndUpdatePredecessor(BasicBlock *BB, BasicBlock *PrevBB, 997 const APInt &NextState, 998 DuplicateBlockMap &DuplicateMap, 999 DefMap &NewDefs, 1000 DomTreeUpdater *DTU) { 1001 ValueToValueMapTy VMap; 1002 BasicBlock *NewBB = CloneBasicBlock( 1003 BB, VMap, ".jt" + std::to_string(NextState.getLimitedValue()), 1004 BB->getParent()); 1005 NewBB->moveAfter(BB); 1006 NumCloned++; 1007 1008 for (Instruction &I : *NewBB) { 1009 // Do not remap operands of PHINode in case a definition in BB is an 1010 // incoming value to a phi in the same block. This incoming value will 1011 // be renamed later while restoring SSA. 1012 if (isa<PHINode>(&I)) 1013 continue; 1014 RemapInstruction(&I, VMap, 1015 RF_IgnoreMissingLocals | RF_NoModuleLevelChanges); 1016 if (AssumeInst *II = dyn_cast<AssumeInst>(&I)) 1017 AC->registerAssumption(II); 1018 } 1019 1020 updateSuccessorPhis(BB, NewBB, NextState, VMap, DuplicateMap); 1021 updatePredecessor(PrevBB, BB, NewBB, DTU); 1022 updateDefMap(NewDefs, VMap); 1023 1024 // Add all successors to the DominatorTree 1025 SmallPtrSet<BasicBlock *, 4> SuccSet; 1026 for (auto *SuccBB : successors(NewBB)) { 1027 if (SuccSet.insert(SuccBB).second) 1028 DTU->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}}); 1029 } 1030 SuccSet.clear(); 1031 return NewBB; 1032 } 1033 1034 /// Update the phi nodes in BB's successors. 1035 /// 1036 /// This means creating a new incoming value from NewBB with the new 1037 /// instruction wherever there is an incoming value from BB. 1038 void updateSuccessorPhis(BasicBlock *BB, BasicBlock *ClonedBB, 1039 const APInt &NextState, ValueToValueMapTy &VMap, 1040 DuplicateBlockMap &DuplicateMap) { 1041 std::vector<BasicBlock *> BlocksToUpdate; 1042 1043 // If BB is the last block in the path, we can simply update the one case 1044 // successor that will be reached. 1045 if (BB == SwitchPaths->getSwitchBlock()) { 1046 SwitchInst *Switch = SwitchPaths->getSwitchInst(); 1047 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState); 1048 BlocksToUpdate.push_back(NextCase); 1049 BasicBlock *ClonedSucc = getClonedBB(NextCase, NextState, DuplicateMap); 1050 if (ClonedSucc) 1051 BlocksToUpdate.push_back(ClonedSucc); 1052 } 1053 // Otherwise update phis in all successors. 1054 else { 1055 for (BasicBlock *Succ : successors(BB)) { 1056 BlocksToUpdate.push_back(Succ); 1057 1058 // Check if a successor has already been cloned for the particular exit 1059 // value. In this case if a successor was already cloned, the phi nodes 1060 // in the cloned block should be updated directly. 1061 BasicBlock *ClonedSucc = getClonedBB(Succ, NextState, DuplicateMap); 1062 if (ClonedSucc) 1063 BlocksToUpdate.push_back(ClonedSucc); 1064 } 1065 } 1066 1067 // If there is a phi with an incoming value from BB, create a new incoming 1068 // value for the new predecessor ClonedBB. The value will either be the same 1069 // value from BB or a cloned value. 1070 for (BasicBlock *Succ : BlocksToUpdate) { 1071 for (auto II = Succ->begin(); PHINode *Phi = dyn_cast<PHINode>(II); 1072 ++II) { 1073 Value *Incoming = Phi->getIncomingValueForBlock(BB); 1074 if (Incoming) { 1075 if (isa<Constant>(Incoming)) { 1076 Phi->addIncoming(Incoming, ClonedBB); 1077 continue; 1078 } 1079 Value *ClonedVal = VMap[Incoming]; 1080 if (ClonedVal) 1081 Phi->addIncoming(ClonedVal, ClonedBB); 1082 else 1083 Phi->addIncoming(Incoming, ClonedBB); 1084 } 1085 } 1086 } 1087 } 1088 1089 /// Sets the successor of PrevBB to be NewBB instead of OldBB. Note that all 1090 /// other successors are kept as well. 1091 void updatePredecessor(BasicBlock *PrevBB, BasicBlock *OldBB, 1092 BasicBlock *NewBB, DomTreeUpdater *DTU) { 1093 // When a path is reused, there is a chance that predecessors were already 1094 // updated before. Check if the predecessor needs to be updated first. 1095 if (!isPredecessor(OldBB, PrevBB)) 1096 return; 1097 1098 Instruction *PrevTerm = PrevBB->getTerminator(); 1099 for (unsigned Idx = 0; Idx < PrevTerm->getNumSuccessors(); Idx++) { 1100 if (PrevTerm->getSuccessor(Idx) == OldBB) { 1101 OldBB->removePredecessor(PrevBB, /* KeepOneInputPHIs = */ true); 1102 PrevTerm->setSuccessor(Idx, NewBB); 1103 } 1104 } 1105 DTU->applyUpdates({{DominatorTree::Delete, PrevBB, OldBB}, 1106 {DominatorTree::Insert, PrevBB, NewBB}}); 1107 } 1108 1109 /// Add new value mappings to the DefMap to keep track of all new definitions 1110 /// for a particular instruction. These will be used while updating SSA form. 1111 void updateDefMap(DefMap &NewDefs, ValueToValueMapTy &VMap) { 1112 SmallVector<std::pair<Instruction *, Instruction *>> NewDefsVector; 1113 NewDefsVector.reserve(VMap.size()); 1114 1115 for (auto Entry : VMap) { 1116 Instruction *Inst = 1117 dyn_cast<Instruction>(const_cast<Value *>(Entry.first)); 1118 if (!Inst || !Entry.second || isa<BranchInst>(Inst) || 1119 isa<SwitchInst>(Inst)) { 1120 continue; 1121 } 1122 1123 Instruction *Cloned = dyn_cast<Instruction>(Entry.second); 1124 if (!Cloned) 1125 continue; 1126 1127 NewDefsVector.push_back({Inst, Cloned}); 1128 } 1129 1130 // Sort the defs to get deterministic insertion order into NewDefs. 1131 sort(NewDefsVector, [](const auto &LHS, const auto &RHS) { 1132 if (LHS.first == RHS.first) 1133 return LHS.second->comesBefore(RHS.second); 1134 return LHS.first->comesBefore(RHS.first); 1135 }); 1136 1137 for (const auto &KV : NewDefsVector) 1138 NewDefs[KV.first].push_back(KV.second); 1139 } 1140 1141 /// Update the last branch of a particular cloned path to point to the correct 1142 /// case successor. 1143 /// 1144 /// Note that this is an optional step and would have been done in later 1145 /// optimizations, but it makes the CFG significantly easier to work with. 1146 void updateLastSuccessor(ThreadingPath &TPath, 1147 DuplicateBlockMap &DuplicateMap, 1148 DomTreeUpdater *DTU) { 1149 APInt NextState = TPath.getExitValue(); 1150 BasicBlock *BB = TPath.getPath().back(); 1151 BasicBlock *LastBlock = getClonedBB(BB, NextState, DuplicateMap); 1152 1153 // Note multiple paths can end at the same block so check that it is not 1154 // updated yet 1155 if (!isa<SwitchInst>(LastBlock->getTerminator())) 1156 return; 1157 SwitchInst *Switch = cast<SwitchInst>(LastBlock->getTerminator()); 1158 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState); 1159 1160 std::vector<DominatorTree::UpdateType> DTUpdates; 1161 SmallPtrSet<BasicBlock *, 4> SuccSet; 1162 for (BasicBlock *Succ : successors(LastBlock)) { 1163 if (Succ != NextCase && SuccSet.insert(Succ).second) 1164 DTUpdates.push_back({DominatorTree::Delete, LastBlock, Succ}); 1165 } 1166 1167 Switch->eraseFromParent(); 1168 BranchInst::Create(NextCase, LastBlock); 1169 1170 DTU->applyUpdates(DTUpdates); 1171 } 1172 1173 /// After cloning blocks, some of the phi nodes have extra incoming values 1174 /// that are no longer used. This function removes them. 1175 void cleanPhiNodes(BasicBlock *BB) { 1176 // If BB is no longer reachable, remove any remaining phi nodes 1177 if (pred_empty(BB)) { 1178 std::vector<PHINode *> PhiToRemove; 1179 for (auto II = BB->begin(); PHINode *Phi = dyn_cast<PHINode>(II); ++II) { 1180 PhiToRemove.push_back(Phi); 1181 } 1182 for (PHINode *PN : PhiToRemove) { 1183 PN->replaceAllUsesWith(PoisonValue::get(PN->getType())); 1184 PN->eraseFromParent(); 1185 } 1186 return; 1187 } 1188 1189 // Remove any incoming values that come from an invalid predecessor 1190 for (auto II = BB->begin(); PHINode *Phi = dyn_cast<PHINode>(II); ++II) { 1191 std::vector<BasicBlock *> BlocksToRemove; 1192 for (BasicBlock *IncomingBB : Phi->blocks()) { 1193 if (!isPredecessor(BB, IncomingBB)) 1194 BlocksToRemove.push_back(IncomingBB); 1195 } 1196 for (BasicBlock *BB : BlocksToRemove) 1197 Phi->removeIncomingValue(BB); 1198 } 1199 } 1200 1201 /// Checks if BB was already cloned for a particular next state value. If it 1202 /// was then it returns this cloned block, and otherwise null. 1203 BasicBlock *getClonedBB(BasicBlock *BB, const APInt &NextState, 1204 DuplicateBlockMap &DuplicateMap) { 1205 CloneList ClonedBBs = DuplicateMap[BB]; 1206 1207 // Find an entry in the CloneList with this NextState. If it exists then 1208 // return the corresponding BB 1209 auto It = llvm::find_if(ClonedBBs, [NextState](const ClonedBlock &C) { 1210 return C.State == NextState; 1211 }); 1212 return It != ClonedBBs.end() ? (*It).BB : nullptr; 1213 } 1214 1215 /// Helper to get the successor corresponding to a particular case value for 1216 /// a switch statement. 1217 BasicBlock *getNextCaseSuccessor(SwitchInst *Switch, const APInt &NextState) { 1218 BasicBlock *NextCase = nullptr; 1219 for (auto Case : Switch->cases()) { 1220 if (Case.getCaseValue()->getValue() == NextState) { 1221 NextCase = Case.getCaseSuccessor(); 1222 break; 1223 } 1224 } 1225 if (!NextCase) 1226 NextCase = Switch->getDefaultDest(); 1227 return NextCase; 1228 } 1229 1230 /// Returns true if IncomingBB is a predecessor of BB. 1231 bool isPredecessor(BasicBlock *BB, BasicBlock *IncomingBB) { 1232 return llvm::is_contained(predecessors(BB), IncomingBB); 1233 } 1234 1235 AllSwitchPaths *SwitchPaths; 1236 DominatorTree *DT; 1237 AssumptionCache *AC; 1238 TargetTransformInfo *TTI; 1239 OptimizationRemarkEmitter *ORE; 1240 SmallPtrSet<const Value *, 32> EphValues; 1241 std::vector<ThreadingPath> TPaths; 1242 }; 1243 1244 bool DFAJumpThreading::run(Function &F) { 1245 LLVM_DEBUG(dbgs() << "\nDFA Jump threading: " << F.getName() << "\n"); 1246 1247 if (F.hasOptSize()) { 1248 LLVM_DEBUG(dbgs() << "Skipping due to the 'minsize' attribute\n"); 1249 return false; 1250 } 1251 1252 if (ClViewCfgBefore) 1253 F.viewCFG(); 1254 1255 SmallVector<AllSwitchPaths, 2> ThreadableLoops; 1256 bool MadeChanges = false; 1257 1258 for (BasicBlock &BB : F) { 1259 auto *SI = dyn_cast<SwitchInst>(BB.getTerminator()); 1260 if (!SI) 1261 continue; 1262 1263 LLVM_DEBUG(dbgs() << "\nCheck if SwitchInst in BB " << BB.getName() 1264 << " is a candidate\n"); 1265 MainSwitch Switch(SI, ORE); 1266 1267 if (!Switch.getInstr()) 1268 continue; 1269 1270 LLVM_DEBUG(dbgs() << "\nSwitchInst in BB " << BB.getName() << " is a " 1271 << "candidate for jump threading\n"); 1272 LLVM_DEBUG(SI->dump()); 1273 1274 unfoldSelectInstrs(DT, Switch.getSelectInsts()); 1275 if (!Switch.getSelectInsts().empty()) 1276 MadeChanges = true; 1277 1278 AllSwitchPaths SwitchPaths(&Switch, ORE); 1279 SwitchPaths.run(); 1280 1281 if (SwitchPaths.getNumThreadingPaths() > 0) { 1282 ThreadableLoops.push_back(SwitchPaths); 1283 1284 // For the time being limit this optimization to occurring once in a 1285 // function since it can change the CFG significantly. This is not a 1286 // strict requirement but it can cause buggy behavior if there is an 1287 // overlap of blocks in different opportunities. There is a lot of room to 1288 // experiment with catching more opportunities here. 1289 break; 1290 } 1291 } 1292 1293 SmallPtrSet<const Value *, 32> EphValues; 1294 if (ThreadableLoops.size() > 0) 1295 CodeMetrics::collectEphemeralValues(&F, AC, EphValues); 1296 1297 for (AllSwitchPaths SwitchPaths : ThreadableLoops) { 1298 TransformDFA Transform(&SwitchPaths, DT, AC, TTI, ORE, EphValues); 1299 Transform.run(); 1300 MadeChanges = true; 1301 } 1302 1303 #ifdef EXPENSIVE_CHECKS 1304 assert(DT->verify(DominatorTree::VerificationLevel::Full)); 1305 verifyFunction(F, &dbgs()); 1306 #endif 1307 1308 return MadeChanges; 1309 } 1310 1311 } // end anonymous namespace 1312 1313 /// Integrate with the new Pass Manager 1314 PreservedAnalyses DFAJumpThreadingPass::run(Function &F, 1315 FunctionAnalysisManager &AM) { 1316 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F); 1317 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F); 1318 TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F); 1319 OptimizationRemarkEmitter ORE(&F); 1320 1321 if (!DFAJumpThreading(&AC, &DT, &TTI, &ORE).run(F)) 1322 return PreservedAnalyses::all(); 1323 1324 PreservedAnalyses PA; 1325 PA.preserve<DominatorTreeAnalysis>(); 1326 return PA; 1327 } 1328