DFAJumpThreading.cpp Source File (original) (raw)

79#include

81#ifdef EXPENSIVE_CHECKS

83#endif

85using namespace llvm;

87#define DEBUG_TYPE "dfa-jump-threading"

89 STATISTIC(NumTransforms, "Number of transformations done");

90 STATISTIC(NumCloned, "Number of blocks cloned");

91 STATISTIC(NumPaths, "Number of individual paths threaded");

93namespace llvm {

96 cl::desc("View the CFG before DFA Jump Threading"),

100 "dfa-early-exit-heuristic",

101 cl::desc("Exit early if an unpredictable value come from the same loop"),

103

105 "dfa-max-path-length",

106 cl::desc("Max number of blocks searched to find a threading path"),

108

110 "dfa-max-num-visited-paths",

112 "Max number of blocks visited while enumerating paths around a switch"),

114

117 cl::desc("Max number of paths enumerated around a switch"),

119

122 cl::desc("Maximum cost accepted for the transformation"),

124

126 "dfa-max-cloned-rate",

128 "Maximum cloned instructions rate accepted for the transformation"),

130

133 cl::desc("Maximum unduplicated blocks with outer uses "

134 "accepted for the transformation"),

136

138

139}

140

141namespace {

142class SelectInstToUnfold {

145

146public:

148

149 SelectInst *getInst() { return SI; }

150 PHINode *getUse() { return SIUse; }

151

152 explicit operator bool() const { return SI && SIUse; }

153};

154

155class DFAJumpThreading {

156public:

157 DFAJumpThreading(AssumptionCache *AC, DomTreeUpdater *DTU, LoopInfo *LI,

158 TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE)

159 : AC(AC), DTU(DTU), LI(LI), TTI(TTI), ORE(ORE) {}

160

161 bool run(Function &F);

162 bool LoopInfoBroken;

163

164private:

165 void

168

169 while ( Stack .empty()) {

170 SelectInstToUnfold SIToUnfold = Stack.pop_back_val();

171

172 std::vector NewSIsToUnfold;

173 std::vector<BasicBlock *> NewBBs;

174 unfold(DTU, LI, SIToUnfold, &NewSIsToUnfold, &NewBBs);

175

176

178 }

179 }

180

181 static void unfold(DomTreeUpdater *DTU, LoopInfo *LI,

182 SelectInstToUnfold SIToUnfold,

183 std::vector *NewSIsToUnfold,

184 std::vector<BasicBlock *> *NewBBs);

185

186 AssumptionCache *AC;

187 DomTreeUpdater *DTU;

188 LoopInfo *LI;

189 TargetTransformInfo *TTI;

190 OptimizationRemarkEmitter *ORE;

191};

192}

193

194

195

196

197

198

199

200

202 SelectInstToUnfold SIToUnfold,

203 std::vector *NewSIsToUnfold,

204 std::vector<BasicBlock *> *NewBBs) {

205 SelectInst *SI = SIToUnfold.getInst();

206 PHINode *SIUse = SIToUnfold.getUse();

208

210 BranchInst *StartBlockTerm =

212 assert(StartBlockTerm);

213

216

218 SI->getContext(), Twine(SI->getName(), ".si.unfold.false"),

219 EndBlock->getParent(), EndBlock);

220 NewBBs->push_back(NewBlock);

222 DTU->applyUpdates({{DominatorTree::Insert, NewBlock, EndBlock}});

223

224

225

226

227

228

229 Value *SIOp1 = SI->getTrueValue();

230 Value *SIOp2 = SI->getFalseValue();

231

233 Twine(SIOp2->getName(), ".si.unfold.phi"),

236

237

238 for (PHINode &Phi : EndBlock->phis()) {

239 if (SIUse == &Phi)

240 continue;

241 Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), NewBlock);

242 }

243

244

245 if (EndBlock == SIUse->getParent()) {

248 } else {

250 Twine(SI->getName(), ".si.unfold.phi"),

252 for (BasicBlock *Pred : predecessors(EndBlock)) {

253 if (Pred != StartBlock && Pred != NewBlock)

255 }

256

260 SIUse = EndPhi;

261 }

262

264 NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, SIUse));

266 NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, NewPhi));

267

268

270 auto *BI =

273 BI->setMetadata(LLVMContext::MD_prof,

274 SI->getMetadata(LLVMContext::MD_prof));

275 DTU->applyUpdates({{DominatorTree::Insert, StartBlock, NewBlock}});

276 } else {

279 SI->getContext(), Twine(SI->getName(), ".si.unfold.true"),

280 EndBlock->getParent(), EndBlock);

282 SI->getContext(), Twine(SI->getName(), ".si.unfold.false"),

283 EndBlock->getParent(), EndBlock);

284

285 NewBBs->push_back(NewBlockT);

286 NewBBs->push_back(NewBlockF);

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

307

308 auto *BI =

311 BI->setMetadata(LLVMContext::MD_prof,

312 SI->getMetadata(LLVMContext::MD_prof));

313 DTU->applyUpdates({{DominatorTree::Insert, NewBlockT, NewBlockF},

314 {DominatorTree::Insert, NewBlockT, EndBlock},

315 {DominatorTree::Insert, NewBlockF, EndBlock}});

316

319

321 SIUse->getType(), 1, Twine(TrueVal->getName(), ".si.unfold.phi"),

324 SIUse->getType(), 1, Twine(FalseVal->getName(), ".si.unfold.phi"),

326 NewPhiT->addIncoming(TrueVal, StartBlock);

327 NewPhiF->addIncoming(FalseVal, NewBlockT);

328

330 NewSIsToUnfold->push_back(SelectInstToUnfold(TrueSI, NewPhiT));

332 NewSIsToUnfold->push_back(SelectInstToUnfold(FalseSi, NewPhiF));

333

337

338

339 for (PHINode &Phi : EndBlock->phis()) {

340 if (SIUse == &Phi)

341 continue;

342 Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), NewBlockT);

343 Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), NewBlockF);

344 Phi.removeIncomingValue(StartBlock);

345 }

346

347

348

349 unsigned SuccNum = StartBlockTerm->getSuccessor(1) == EndBlock ? 1 : 0;

350 StartBlockTerm->setSuccessor(SuccNum, NewBlockT);

351 DTU->applyUpdates({{DominatorTree::Delete, StartBlock, EndBlock},

352 {DominatorTree::Insert, StartBlock, NewBlockT}});

353 }

354

355

356 if (Loop *L = LI->getLoopFor(StartBlock)) {

357 for (BasicBlock *NewBB : *NewBBs)

358 L->addBasicBlockToLoop(NewBB, *LI);

359 }

360

361

362 assert(SI->use_empty() && "Select must be dead now");

363 SI->eraseFromParent();

364}

365

366namespace {

367struct ClonedBlock {

369 APInt State;

370};

371}

372

373typedef std::deque<BasicBlock *> PathType;

377

378

379

380

382

383

384

386

390 OS << "< " << llvm::join(BBNames, ", ") << " >";

391 return OS;

392}

393

394namespace {

395

396

397

398

399struct ThreadingPath {

400

401 APInt getExitValue() const { return ExitVal; }

402 void setExitValue(const ConstantInt *V) {

403 ExitVal = V->getValue();

404 IsExitValSet = true;

405 }

406 void setExitValue(const APInt &V) {

407 ExitVal = V;

408 IsExitValSet = true;

409 }

410 bool isExitValueSet() const { return IsExitValSet; }

411

412

413 const BasicBlock *getDeterminatorBB() const { return DBB; }

414 void setDeterminator(const BasicBlock *BB) { DBB = BB; }

415

416

417 const PathType &getPath() const { return Path; }

418 void setPath(const PathType &NewPath) { Path = NewPath; }

419 void push_back(BasicBlock *BB) { Path.push_back(BB); }

420 void push_front(BasicBlock *BB) { Path.push_front(BB); }

421 void appendExcludingFirst(const PathType &OtherPath) {

423 }

424

425 void print(raw_ostream &OS) const {

426 OS << Path << " [ " << ExitVal << ", " << DBB->getNameOrAsOperand() << " ]";

427 }

428

429private:

431 APInt ExitVal;

433 bool IsExitValSet = false;

434};

435

436#ifndef NDEBUG

437inline raw_ostream &operator<<(raw_ostream &OS, const ThreadingPath &TPath) {

438 TPath.print(OS);

439 return OS;

440}

441#endif

442

443struct MainSwitch {

444 MainSwitch(SwitchInst *SI, LoopInfo *LI, OptimizationRemarkEmitter *ORE)

445 : LI(LI) {

447 Instr = SI;

448 } else {

449 ORE->emit([&]() {

450 return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable", SI)

451 << "Switch instruction is not predictable.";

452 });

453 }

454 }

455

456 virtual ~MainSwitch() = default;

457

458 SwitchInst *getInstr() const { return Instr; }

460 return SelectInsts;

461 }

462

463private:

464

465

466

467

469 std::deque<std::pair<Value *, BasicBlock *>> Q;

470 SmallPtrSet<Value *, 16> SeenValues;

471 SelectInsts.clear();

472

473 Value *SICond = SI->getCondition();

474 LLVM_DEBUG(dbgs() << "\tSICond: " << *SICond << "\n");

476 return false;

477

478

480 if (!L)

481 return false;

482

483 addToQueue(SICond, nullptr, Q, SeenValues);

484

485 while (!Q.empty()) {

486 Value *Current = Q.front().first;

487 BasicBlock *CurrentIncomingBB = Q.front().second;

488 Q.pop_front();

489

491 for (BasicBlock *IncomingBB : Phi->blocks()) {

492 Value *Incoming = Phi->getIncomingValueForBlock(IncomingBB);

493 addToQueue(Incoming, IncomingBB, Q, SeenValues);

494 }

497 if (!isValidSelectInst(SelI))

498 return false;

499 addToQueue(SelI->getTrueValue(), CurrentIncomingBB, Q, SeenValues);

500 addToQueue(SelI->getFalseValue(), CurrentIncomingBB, Q, SeenValues);

503 SelectInsts.push_back(SelectInstToUnfold(SelI, SelIUse));

505 LLVM_DEBUG(dbgs() << "\tconst: " << *Current << "\n");

506 continue;

507 } else {

508 LLVM_DEBUG(dbgs() << "\tother: " << *Current << "\n");

509

510

511

512

513

514

515

516

517

519 L->contains(LI->getLoopFor(CurrentIncomingBB))) {

521 << "\tExiting early due to unpredictability heuristic.\n");

522 return false;

523 }

524

525 continue;

526 }

527 }

528

529 return true;

530 }

531

532 void addToQueue(Value *Val, BasicBlock *BB,

533 std::deque<std::pair<Value *, BasicBlock *>> &Q,

534 SmallPtrSet<Value *, 16> &SeenValues) {

535 if (SeenValues.insert(Val).second)

536 Q.push_back({Val, BB});

537 }

538

539 bool isValidSelectInst(SelectInst *SI) {

540 if (->hasOneUse())

541 return false;

542

544

546 return false;

547

549

550

551

554 return false;

555

556

557

558

561 return false;

562

563

564

565 for (SelectInstToUnfold SIToUnfold : SelectInsts) {

566 SelectInst *PrevSI = SIToUnfold.getInst();

569 return false;

570 }

571

572 return true;

573 }

574

575 LoopInfo *LI;

576 SwitchInst *Instr = nullptr;

578};

579

580struct AllSwitchPaths {

581 AllSwitchPaths(const MainSwitch *MSwitch, OptimizationRemarkEmitter *ORE,

582 LoopInfo *LI, Loop *L)

583 : Switch(MSwitch->getInstr()), SwitchBlock(Switch->getParent()), ORE(ORE),

584 LI(LI), SwitchOuterLoop(L) {}

585

586 std::vector &getThreadingPaths() { return TPaths; }

587 unsigned getNumThreadingPaths() { return TPaths.size(); }

588 SwitchInst *getSwitchInst() { return Switch; }

589 BasicBlock *getSwitchBlock() { return SwitchBlock; }

590

591 void run() {

592 findTPaths();

593 unifyTPaths();

594 }

595

596private:

597

598

599 typedef DenseMap<const BasicBlock *, const PHINode *> StateDefMap;

600 std::vector getPathsFromStateDefMap(StateDefMap &StateDef,

601 PHINode *Phi,

603 unsigned PathsLimit) {

604 std::vector Res;

605 auto *PhiBB = Phi->getParent();

607

609 for (auto *IncomingBB : Phi->blocks()) {

610 if (Res.size() >= PathsLimit)

611 break;

612 if (!UniqueBlocks.insert(IncomingBB).second)

613 continue;

614 if (!SwitchOuterLoop->contains(IncomingBB))

615 continue;

616

617 Value *IncomingValue = Phi->getIncomingValueForBlock(IncomingBB);

618

620

621 if (PhiBB == SwitchBlock &&

623 continue;

624 ThreadingPath NewPath;

625 NewPath.setDeterminator(PhiBB);

626 NewPath.setExitValue(C);

627

628 if (IncomingBB != SwitchBlock) {

629

631 continue;

632 NewPath.push_back(IncomingBB);

633 }

634 NewPath.push_back(PhiBB);

635 Res.push_back(NewPath);

636 continue;

637 }

638

639 if (VB.contains(IncomingBB) || IncomingBB == SwitchBlock)

640 continue;

641

643 if (!IncomingPhi)

644 continue;

645 auto *IncomingPhiDefBB = IncomingPhi->getParent();

646 if (!StateDef.contains(IncomingPhiDefBB))

647 continue;

648

649

650 if (IncomingPhiDefBB == IncomingBB) {

651 assert(PathsLimit > Res.size());

652 std::vector PredPaths = getPathsFromStateDefMap(

653 StateDef, IncomingPhi, VB, PathsLimit - Res.size());

654 for (ThreadingPath &Path : PredPaths) {

655 Path.push_back(PhiBB);

656 Res.push_back(std::move(Path));

657 }

658 continue;

659 }

660

661

662 if (VB.contains(IncomingPhiDefBB))

663 continue;

664

666 assert(PathsLimit > Res.size());

667 auto InterPathLimit = PathsLimit - Res.size();

668 IntermediatePaths = paths(IncomingPhiDefBB, IncomingBB, VB,

669 1, InterPathLimit);

670 if (IntermediatePaths.empty())

671 continue;

672

673 assert(InterPathLimit >= IntermediatePaths.size());

674 auto PredPathLimit = InterPathLimit / IntermediatePaths.size();

675 std::vector PredPaths =

676 getPathsFromStateDefMap(StateDef, IncomingPhi, VB, PredPathLimit);

677 for (const ThreadingPath &Path : PredPaths) {

678 for (const PathType &IPath : IntermediatePaths) {

679 ThreadingPath NewPath(Path);

680 NewPath.appendExcludingFirst(IPath);

681 NewPath.push_back(PhiBB);

682 Res.push_back(NewPath);

683 }

684 }

685 }

687 return Res;

688 }

689

691 unsigned PathDepth, unsigned PathsLimit) {

693

694

696 ORE->emit([&]() {

697 return OptimizationRemarkAnalysis(DEBUG_TYPE, "MaxPathLengthReached",

698 Switch)

699 << "Exploration stopped after visiting MaxPathLength="

701 });

702 return Res;

703 }

704

707 return Res;

708

709

710

711 if (!SwitchOuterLoop->contains(BB))

712 return Res;

713

714

715

716 SmallPtrSet<BasicBlock *, 4> Successors;

717 for (BasicBlock *Succ : successors(BB)) {

718 if (Res.size() >= PathsLimit)

719 break;

720 if (!Successors.insert(Succ).second)

721 continue;

722

723

724 if (Succ == ToBB) {

725 Res.push_back({BB, ToBB});

726 continue;

727 }

728

729

731 continue;

732

734

735 if (Succ == CurrLoop->getHeader())

736 continue;

737

738

739 if (LI->getLoopFor(Succ) != CurrLoop)

740 continue;

741 assert(PathsLimit > Res.size());

743 paths(Succ, ToBB, Visited, PathDepth + 1, PathsLimit - Res.size());

744 for (PathType &Path : SuccPaths) {

745 Path.push_front(BB);

746 Res.push_back(Path);

747 }

748 }

749

750

751

752 Visited.erase(BB);

753 return Res;

754 }

755

756

757

758 StateDefMap getStateDefMap() const {

759 StateDefMap Res;

761 assert(FirstDef && "The first definition must be a phi.");

762

764 Stack.push_back(FirstDef);

765 SmallPtrSet<Value *, 16> SeenValues;

766

767 while ( Stack .empty()) {

768 PHINode *CurPhi = Stack.pop_back_val();

769

770 Res[CurPhi->getParent()] = CurPhi;

771 SeenValues.insert(CurPhi);

772

773 for (BasicBlock *IncomingBB : CurPhi->blocks()) {

774 PHINode *IncomingPhi =

776 if (!IncomingPhi)

777 continue;

778 bool IsOutsideLoops = !SwitchOuterLoop->contains(IncomingBB);

779 if (SeenValues.contains(IncomingPhi) || IsOutsideLoops)

780 continue;

781

782 Stack.push_back(IncomingPhi);

783 }

784 }

785

786 return Res;

787 }

788

789

790 void findTPaths() {

791 StateDefMap StateDef = getStateDefMap();

792 if (StateDef.empty()) {

793 ORE->emit([&]() {

794 return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable",

795 Switch)

796 << "Switch instruction is not predictable.";

797 });

798 return;

799 }

800

802 auto *SwitchPhiDefBB = SwitchPhi->getParent();

804

805 std::vector PathsToPhiDef =

806 getPathsFromStateDefMap(StateDef, SwitchPhi, VB, MaxNumPaths);

807 if (SwitchPhiDefBB == SwitchBlock || PathsToPhiDef.empty()) {

808 TPaths = std::move(PathsToPhiDef);

809 return;

810 }

811

812 assert(MaxNumPaths >= PathsToPhiDef.size() && !PathsToPhiDef.empty());

813 auto PathsLimit = MaxNumPaths / PathsToPhiDef.size();

814

816 paths(SwitchPhiDefBB, SwitchBlock, VB, 1, PathsLimit);

817 if (PathsToSwitchBB.empty())

818 return;

819

820 std::vector TempList;

821 for (const ThreadingPath &Path : PathsToPhiDef) {

822 SmallPtrSet<BasicBlock *, 32> PathSet(Path.getPath().begin(),

823 Path.getPath().end());

824 for (const PathType &PathToSw : PathsToSwitchBB) {

826 [&](const BasicBlock *BB) { return PathSet.contains(BB); }))

827 continue;

828 ThreadingPath PathCopy(Path);

829 PathCopy.appendExcludingFirst(PathToSw);

830 TempList.push_back(PathCopy);

831 }

832 }

833 TPaths = std::move(TempList);

834 }

835

836

837

838 BasicBlock *getNextCaseSuccessor(const APInt &NextState) {

839

840 if (CaseValToDest.empty()) {

841 for (auto Case : Switch->cases()) {

842 APInt CaseVal = Case.getCaseValue()->getValue();

843 CaseValToDest[CaseVal] = Case.getCaseSuccessor();

844 }

845 }

846

847 auto SuccIt = CaseValToDest.find(NextState);

848 return SuccIt == CaseValToDest.end() ? Switch->getDefaultDest()

849 : SuccIt->second;

850 }

851

852

853

854 void unifyTPaths() {

855 SmallDenseMap<BasicBlock *, APInt> DestToState;

856 for (ThreadingPath &Path : TPaths) {

857 APInt NextState = Path.getExitValue();

858 BasicBlock *Dest = getNextCaseSuccessor(NextState);

860 if (Inserted)

861 continue;

862 if (NextState != StateIt->second) {

863 LLVM_DEBUG(dbgs() << "Next state in " << Path << " is equivalent to "

864 << StateIt->second << "\n");

865 Path.setExitValue(StateIt->second);

866 }

867 }

868 }

869

870 unsigned NumVisited = 0;

871 SwitchInst *Switch;

873 OptimizationRemarkEmitter *ORE;

874 std::vector TPaths;

875 DenseMap<APInt, BasicBlock *> CaseValToDest;

876 LoopInfo *LI;

877 Loop *SwitchOuterLoop;

878};

879

880struct TransformDFA {

881 TransformDFA(AllSwitchPaths *SwitchPaths, DomTreeUpdater *DTU,

882 AssumptionCache *AC, TargetTransformInfo *TTI,

883 OptimizationRemarkEmitter *ORE,

884 SmallPtrSet<const Value *, 32> EphValues)

885 : SwitchPaths(SwitchPaths), DTU(DTU), AC(AC), TTI(TTI), ORE(ORE),

886 EphValues(EphValues) {}

887

888 bool run() {

889 if (isLegalAndProfitableToTransform()) {

890 createAllExitPaths();

891 NumTransforms++;

892 return true;

893 }

894 return false;

895 }

896

897private:

898

899

900

901

902 bool isLegalAndProfitableToTransform() {

904 uint64_t NumClonedInst = 0;

905 SwitchInst *Switch = SwitchPaths->getSwitchInst();

906

907

908 if (Switch->getNumSuccessors() <= 1)

909 return false;

910

911

912

914 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {

915 PathType PathBBs = TPath.getPath();

916 APInt NextState = TPath.getExitValue();

917 const BasicBlock *Determinator = TPath.getDeterminatorBB();

918

919

920 BasicBlock *BB = SwitchPaths->getSwitchBlock();

921 BasicBlock *VisitedBB = getClonedBB(BB, NextState, DuplicateMap);

922 if (!VisitedBB) {

923 Metrics.analyzeBasicBlock(BB, *TTI, EphValues);

925 DuplicateMap[BB].push_back({BB, NextState});

926 }

927

928

929

930 if (PathBBs.front() == Determinator)

931 continue;

932

933

934

935 auto DetIt = llvm::find(PathBBs, Determinator);

936 for (auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {

937 BB = *BBIt;

938 VisitedBB = getClonedBB(BB, NextState, DuplicateMap);

939 if (VisitedBB)

940 continue;

941 Metrics.analyzeBasicBlock(BB, *TTI, EphValues);

943 DuplicateMap[BB].push_back({BB, NextState});

944 }

945

946 if (Metrics.notDuplicatable) {

947 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "

948 << "non-duplicatable instructions.\n");

949 ORE->emit([&]() {

950 return OptimizationRemarkMissed(DEBUG_TYPE, "NonDuplicatableInst",

951 Switch)

952 << "Contains non-duplicatable instructions.";

953 });

954 return false;

955 }

956

957

958 if (Metrics.Convergence != ConvergenceKind::None) {

959 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "

960 << "convergent instructions.\n");

961 ORE->emit([&]() {

962 return OptimizationRemarkMissed(DEBUG_TYPE, "ConvergentInst", Switch)

963 << "Contains convergent instructions.";

964 });

965 return false;

966 }

967

968 if ( Metrics .NumInsts.isValid()) {

969 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "

970 << "instructions with invalid cost.\n");

971 ORE->emit([&]() {

972 return OptimizationRemarkMissed(DEBUG_TYPE, "ConvergentInst", Switch)

973 << "Contains instructions with invalid cost.";

974 });

975 return false;

976 }

977 }

978

979

980

981

982 uint64_t NumOrigInst = 0;

983 uint64_t NumOuterUseBlock = 0;

984 for (auto *BB : DuplicateMap.keys()) {

986

987

989 if (!DuplicateMap.count(Succ) && Succ->getSinglePredecessor())

990 NumOuterUseBlock++;

991 }

992

993 if (double(NumClonedInst) / double(NumOrigInst) > MaxClonedRate) {

994 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, too much "

995 "instructions wll be cloned\n");

996 ORE->emit([&]() {

997 return OptimizationRemarkMissed(DEBUG_TYPE, "NotProfitable", Switch)

998 << "Too much instructions will be cloned.";

999 });

1000 return false;

1001 }

1002

1003

1004

1005

1006

1008 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, too much "

1009 "blocks with outer uses\n");

1010 ORE->emit([&]() {

1011 return OptimizationRemarkMissed(DEBUG_TYPE, "NotProfitable", Switch)

1012 << "Too much blocks with outer uses.";

1013 });

1014 return false;

1015 }

1016

1018

1019 unsigned JumpTableSize = 0;

1021 nullptr);

1022 if (JumpTableSize == 0) {

1023

1024

1025

1026 unsigned CondBranches =

1027 APInt(32, Switch->getNumSuccessors()).ceilLogBase2();

1028 assert(CondBranches > 0 &&

1029 "The threaded switch must have multiple branches");

1030 DuplicationCost = Metrics.NumInsts / CondBranches;

1031 } else {

1032

1033

1034

1035

1036

1037

1038 DuplicationCost = Metrics.NumInsts / JumpTableSize;

1039 }

1040

1041 LLVM_DEBUG(dbgs() << "\nDFA Jump Threading: Cost to jump thread block "

1042 << SwitchPaths->getSwitchBlock()->getName()

1043 << " is: " << DuplicationCost << "\n\n");

1044

1046 LLVM_DEBUG(dbgs() << "Not jump threading, duplication cost exceeds the "

1047 << "cost threshold.\n");

1048 ORE->emit([&]() {

1049 return OptimizationRemarkMissed(DEBUG_TYPE, "NotProfitable", Switch)

1050 << "Duplication cost exceeds the cost threshold (cost="

1051 << ore::NV("Cost", DuplicationCost)

1053 });

1054 return false;

1055 }

1056

1057 ORE->emit([&]() {

1058 return OptimizationRemark(DEBUG_TYPE, "JumpThreaded", Switch)

1059 << "Switch statement jump-threaded.";

1060 });

1061

1062 return true;

1063 }

1064

1065

1066 void createAllExitPaths() {

1067

1068 BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock();

1069 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {

1071

1072

1073 TPath.push_front(SwitchBlock);

1074 }

1075

1076

1079

1080 SmallPtrSet<BasicBlock *, 16> BlocksToClean;

1082

1083 for (const ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {

1084 createExitPath(NewDefs, TPath, DuplicateMap, BlocksToClean, DTU);

1085 NumPaths++;

1086 }

1087

1088

1089

1090 for (const ThreadingPath &TPath : SwitchPaths->getThreadingPaths())

1091 updateLastSuccessor(TPath, DuplicateMap, DTU);

1092

1093

1094 updateSSA(NewDefs);

1095

1096

1097 for (BasicBlock *BB : BlocksToClean)

1098 cleanPhiNodes(BB);

1099 }

1100

1101

1102

1103

1104

1105

1106

1107 void createExitPath(DefMap &NewDefs, const ThreadingPath &Path,

1109 SmallPtrSet<BasicBlock *, 16> &BlocksToClean,

1110 DomTreeUpdater *DTU) {

1111 APInt NextState = Path.getExitValue();

1112 const BasicBlock *Determinator = Path.getDeterminatorBB();

1114

1115

1116 if (PathBBs.front() == Determinator)

1117 PathBBs.pop_front();

1118

1119 auto DetIt = llvm::find(PathBBs, Determinator);

1120

1121

1122 BasicBlock *PrevBB = PathBBs.size() == 1 ? *DetIt : *std::prev(DetIt);

1123 for (auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {

1125 BlocksToClean.insert(BB);

1126

1127

1128

1129 BasicBlock *NextBB = getClonedBB(BB, NextState, DuplicateMap);

1130 if (NextBB) {

1131 updatePredecessor(PrevBB, BB, NextBB, DTU);

1132 PrevBB = NextBB;

1133 continue;

1134 }

1135

1136

1137 BasicBlock *NewBB = cloneBlockAndUpdatePredecessor(

1138 BB, PrevBB, NextState, DuplicateMap, NewDefs, DTU);

1139 DuplicateMap[BB].push_back({NewBB, NextState});

1140 BlocksToClean.insert(NewBB);

1141 PrevBB = NewBB;

1142 }

1143 }

1144

1145

1146

1147

1148

1149

1150

1151 void updateSSA(DefMap &NewDefs) {

1152 SSAUpdaterBulk SSAUpdate;

1153 SmallVector<Use *, 16> UsesToRename;

1154

1155 for (const auto &KV : NewDefs) {

1158 std::vector<Instruction *> Cloned = KV.second;

1159

1160

1161

1162 for (Use &U : I->uses()) {

1165 if (UserPN->getIncomingBlock(U) == BB)

1166 continue;

1167 } else if (User->getParent() == BB) {

1168 continue;

1169 }

1170

1172 }

1173

1174

1175

1176 if (UsesToRename.empty())

1177 continue;

1178 LLVM_DEBUG(dbgs() << "DFA-JT: Renaming non-local uses of: " << *I

1179 << "\n");

1180

1181

1182

1183

1184 unsigned VarNum = SSAUpdate.AddVariable(I->getName(), I->getType());

1186 for (Instruction *New : Cloned)

1188

1189 while (!UsesToRename.empty())

1191

1193 }

1194

1195

1197 }

1198

1199

1200

1201

1202

1203 static BasicBlock *getNextCaseSuccessor(SwitchInst *Switch,

1204 const APInt &NextState) {

1206 for (auto Case : Switch->cases()) {

1207 if (Case.getCaseValue()->getValue() == NextState) {

1208 NextCase = Case.getCaseSuccessor();

1209 break;

1210 }

1211 }

1212 if (!NextCase)

1213 NextCase = Switch->getDefaultDest();

1214 return NextCase;

1215 }

1216

1217

1218

1219

1220

1221 BasicBlock *cloneBlockAndUpdatePredecessor(BasicBlock *BB, BasicBlock *PrevBB,

1222 const APInt &NextState,

1225 DomTreeUpdater *DTU) {

1228 BB, VMap, ".jt" + std::to_string(NextState.getLimitedValue()),

1231 NumCloned++;

1232

1233 for (Instruction &I : *NewBB) {

1234

1235

1236

1238 continue;

1243 }

1244

1245 updateSuccessorPhis(BB, NewBB, NextState, VMap, DuplicateMap);

1246 updatePredecessor(PrevBB, BB, NewBB, DTU);

1247 updateDefMap(NewDefs, VMap);

1248

1249

1250 SmallPtrSet<BasicBlock *, 4> SuccSet;

1251 for (auto *SuccBB : successors(NewBB)) {

1252 if (SuccSet.insert(SuccBB).second)

1253 DTU->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}});

1254 }

1255 SuccSet.clear();

1256 return NewBB;

1257 }

1258

1259

1260

1261

1262

1263 void updateSuccessorPhis(BasicBlock *BB, BasicBlock *ClonedBB,

1266 std::vector<BasicBlock *> BlocksToUpdate;

1267

1268

1269

1270 if (BB == SwitchPaths->getSwitchBlock()) {

1271 SwitchInst *Switch = SwitchPaths->getSwitchInst();

1272 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);

1273 BlocksToUpdate.push_back(NextCase);

1274 BasicBlock *ClonedSucc = getClonedBB(NextCase, NextState, DuplicateMap);

1275 if (ClonedSucc)

1276 BlocksToUpdate.push_back(ClonedSucc);

1277 }

1278

1279 else {

1280 for (BasicBlock *Succ : successors(BB)) {

1281 BlocksToUpdate.push_back(Succ);

1282

1283

1284

1285

1286 BasicBlock *ClonedSucc = getClonedBB(Succ, NextState, DuplicateMap);

1287 if (ClonedSucc)

1288 BlocksToUpdate.push_back(ClonedSucc);

1289 }

1290 }

1291

1292

1293

1294

1295 for (BasicBlock *Succ : BlocksToUpdate) {

1296 for (PHINode &Phi : Succ->phis()) {

1297 Value *Incoming = Phi.getIncomingValueForBlock(BB);

1298 if (Incoming) {

1300 Phi.addIncoming(Incoming, ClonedBB);

1301 continue;

1302 }

1303 Value *ClonedVal = VMap[Incoming];

1304 if (ClonedVal)

1305 Phi.addIncoming(ClonedVal, ClonedBB);

1306 else

1307 Phi.addIncoming(Incoming, ClonedBB);

1308 }

1309 }

1310 }

1311 }

1312

1313

1314

1315 void updatePredecessor(BasicBlock *PrevBB, BasicBlock *OldBB,

1316 BasicBlock *NewBB, DomTreeUpdater *DTU) {

1317

1318

1319 if (!isPredecessor(OldBB, PrevBB))

1320 return;

1321

1323 for (unsigned Idx = 0; Idx < PrevTerm->getNumSuccessors(); Idx++) {

1325 OldBB->removePredecessor(PrevBB, true);

1327 }

1328 }

1329 DTU->applyUpdates({{DominatorTree::Delete, PrevBB, OldBB},

1330 {DominatorTree::Insert, PrevBB, NewBB}});

1331 }

1332

1333

1334

1338

1339 for (auto Entry : VMap) {

1344 continue;

1345 }

1346

1348 if (!Cloned)

1349 continue;

1350

1351 NewDefsVector.push_back({Inst, Cloned});

1352 }

1353

1354

1355 sort(NewDefsVector, [](const auto &LHS, const auto &RHS) {

1356 if (LHS.first == RHS.first)

1357 return LHS.second->comesBefore(RHS.second);

1358 return LHS.first->comesBefore(RHS.first);

1359 });

1360

1361 for (const auto &KV : NewDefsVector)

1362 NewDefs[KV.first].push_back(KV.second);

1363 }

1364

1365

1366

1367

1368

1369

1370 void updateLastSuccessor(const ThreadingPath &TPath,

1372 DomTreeUpdater *DTU) {

1373 APInt NextState = TPath.getExitValue();

1374 BasicBlock *BB = TPath.getPath().back();

1375 BasicBlock *LastBlock = getClonedBB(BB, NextState, DuplicateMap);

1376

1377

1378

1380 return;

1382 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);

1383

1384 std::vectorDominatorTree::UpdateType DTUpdates;

1385 SmallPtrSet<BasicBlock *, 4> SuccSet;

1386 for (BasicBlock *Succ : successors(LastBlock)) {

1387 if (Succ != NextCase && SuccSet.insert(Succ).second)

1388 DTUpdates.push_back({DominatorTree::Delete, LastBlock, Succ});

1389 }

1390

1391 Switch->eraseFromParent();

1393

1395 }

1396

1397

1398

1399 void cleanPhiNodes(BasicBlock *BB) {

1400

1404 PN.eraseFromParent();

1405 }

1406 return;

1407 }

1408

1409

1410 for (PHINode &Phi : BB->phis())

1411 Phi.removeIncomingValueIf([&](unsigned Index) {

1412 BasicBlock *IncomingBB = Phi.getIncomingBlock(Index);

1413 return !isPredecessor(BB, IncomingBB);

1414 });

1415 }

1416

1417

1418

1419 BasicBlock *getClonedBB(BasicBlock *BB, const APInt &NextState,

1421 CloneList ClonedBBs = DuplicateMap[BB];

1422

1423

1424

1425 auto It = llvm::find_if(ClonedBBs, [NextState](const ClonedBlock &C) {

1426 return C.State == NextState;

1427 });

1428 return It != ClonedBBs.end() ? (*It).BB : nullptr;

1429 }

1430

1431

1432 bool isPredecessor(BasicBlock *BB, BasicBlock *IncomingBB) {

1434 }

1435

1436 AllSwitchPaths *SwitchPaths;

1437 DomTreeUpdater *DTU;

1438 AssumptionCache *AC;

1439 TargetTransformInfo *TTI;

1440 OptimizationRemarkEmitter *ORE;

1441 SmallPtrSet<const Value *, 32> EphValues;

1442 std::vector TPaths;

1443};

1444}

1445

1446bool DFAJumpThreading::run(Function &F) {

1447 LLVM_DEBUG(dbgs() << "\nDFA Jump threading: " << F.getName() << "\n");

1448

1449 if (F.hasOptSize()) {

1450 LLVM_DEBUG(dbgs() << "Skipping due to the 'minsize' attribute\n");

1451 return false;

1452 }

1453

1455 F.viewCFG();

1456

1458 bool MadeChanges = false;

1459 LoopInfoBroken = false;

1460

1461 for (BasicBlock &BB : F) {

1463 if (!SI)

1464 continue;

1465

1467 << " is a candidate\n");

1468 MainSwitch Switch(SI, LI, ORE);

1469

1470 if ( Switch .getInstr()) {

1472 << "candidate for jump threading\n");

1473 continue;

1474 }

1475

1477 << "candidate for jump threading\n");

1479

1480 unfoldSelectInstrs(Switch.getSelectInsts());

1481 if ( Switch .getSelectInsts().empty())

1482 MadeChanges = true;

1483

1484 AllSwitchPaths SwitchPaths(&Switch, ORE, LI,

1486 SwitchPaths.run();

1487

1488 if (SwitchPaths.getNumThreadingPaths() > 0) {

1489 ThreadableLoops.push_back(SwitchPaths);

1490

1491

1492

1493

1494

1495

1496

1497 break;

1498 }

1499 }

1500

1501#ifdef NDEBUG

1503#endif

1504

1505 SmallPtrSet<const Value *, 32> EphValues;

1506 if (ThreadableLoops.size() > 0)

1508

1509 for (AllSwitchPaths SwitchPaths : ThreadableLoops) {

1510 TransformDFA Transform(&SwitchPaths, DTU, AC, TTI, ORE, EphValues);

1511 if (Transform.run())

1512 MadeChanges = LoopInfoBroken = true;

1513 }

1514

1516

1517#ifdef EXPENSIVE_CHECKS

1519#endif

1520

1523 "Failed to maintain validity of domtree!");

1524

1525 return MadeChanges;

1526}

1527

1528

1536

1537 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);

1538 DFAJumpThreading ThreadImpl(&AC, &DTU, &LI, &TTI, &ORE);

1539 if (!ThreadImpl.run(F))

1541

1544 if (!ThreadImpl.LoopInfoBroken)

1546 return PA;

1547}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file implements a class to represent arbitrary precision integral constant values and operations...

static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)

static const Function * getParent(const Value *V)

This file contains the declarations for the subclasses of Constant, which represent the different fla...

SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks

Definition DFAJumpThreading.cpp:375

std::deque< BasicBlock * > PathType

Definition DFAJumpThreading.cpp:373

std::vector< PathType > PathsType

Definition DFAJumpThreading.cpp:374

MapVector< Instruction *, std::vector< Instruction * > > DefMap

Definition DFAJumpThreading.cpp:385

std::vector< ClonedBlock > CloneList

Definition DFAJumpThreading.cpp:376

DenseMap< BasicBlock *, CloneList > DuplicateBlockMap

Definition DFAJumpThreading.cpp:381

This file defines the DenseMap class.

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

static bool isCandidate(const MachineInstr *MI, Register &DefedReg, Register FrameReg)

uint64_t IntrinsicInst * II

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

This pass exposes codegen information to IR-level passes.

uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const

If this value is smaller than the specified limit, return it, otherwise return the limit value.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

A function analysis which provides an AssumptionCache.

A cache of @llvm.assume calls within a function.

LLVM_ABI void registerAssumption(AssumeInst *CI)

Add an @llvm.assume intrinsic to this function's cache.

LLVM Basic Block Representation.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

LLVM_ABI const_iterator getFirstInsertionPt() const

Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...

const Function * getParent() const

Return the enclosing method, or null if none.

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

LLVM_ABI void moveAfter(BasicBlock *MovePos)

Unlink this basic block from its current function and insert it right after MovePos in the function M...

LLVM_ABI const BasicBlock * getUniqueSuccessor() const

Return the successor of this block if it has a unique successor.

LLVM_ABI filter_iterator< BasicBlock::const_iterator, std::function< bool(constInstruction &)> >::difference_type sizeWithoutDebug() const

Return the size of the basic block ignoring debug instructions.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)

Update PHI nodes in this BasicBlock before removal of predecessor Pred.

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

void setSuccessor(unsigned idx, BasicBlock *NewSucc)

std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

Analysis pass which computes a DominatorTree.

bool verify(VerificationLevel VL=VerificationLevel::Full) const

verify - checks if the tree is correct.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

DomTreeT & getDomTree()

Flush DomTree updates and return DomTree.

void applyUpdates(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

void flush()

Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.

LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

Return the specified successor. This instruction must be a terminator.

LLVM_ABI void setSuccessor(unsigned Idx, BasicBlock *BB)

Update the specified successor to point at the provided block.

Analysis pass that exposes the LoopInfo for a function.

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this loop.

const LoopT * getOutermostLoop() const

Get the outermost loop in which this loop is contained.

void verify(const DominatorTreeBase< BlockT, false > &DomTree) const

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

This class implements a map that also provides access to all stored values in a deterministic order.

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

iterator_range< const_block_iterator > blocks() const

LLVM_ABI Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)

Remove an incoming value.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

static LLVM_ABI PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

LLVM_ABI unsigned AddVariable(StringRef Name, Type *Ty)

Add a new variable to the SSA rewriter.

LLVM_ABI void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V)

Indicate that a rewritten value is available in the specified block with the specified value.

LLVM_ABI void RewriteAllUses(DominatorTree *DT, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)

Perform all the necessary updates, including new PHI-nodes insertion and the requested uses update.

LLVM_ABI void AddUse(unsigned Var, Use *U)

Record a use of the symbolic value.

This class represents the LLVM 'select' instruction.

const Value * getFalseValue() const

const Value * getTrueValue() const

bool erase(PtrType Ptr)

Remove pointer from the set.

void insert_range(Range &&R)

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

bool contains(ConstPtrType Ptr) const

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

void reserve(size_type N)

void push_back(const T &Elt)

BasicBlock * getDefaultDest() const

iterator_range< CaseIt > cases()

Iteration adapter for range-for loops.

Analysis pass providing the TargetTransformInfo.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

LLVM_ABI unsigned getEstimatedNumberOfCaseClusters(const SwitchInst &SI, unsigned &JTSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) const

LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)

Replace uses of one Value with another.

Value * getOperand(unsigned i) const

Type * getType() const

All values are typed, get the type of this value.

LLVM_ABI std::string getNameOrAsOperand() const

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

const ParentTy * getParent() const

This class implements an extremely fast bulk output stream that can only output to a stream.

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

initializer< Ty > init(const Ty &Val)

@ Switch

The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

@ User

could "use" a pointer

DiagnosticInfoOptimizationBase::Argument NV

NodeAddr< PhiNode * > Phi

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

auto drop_begin(T &&RangeOrContainer, size_t N=1)

Return a range covering RangeOrContainer with the first N elements excluded.

FunctionAddr VTableAddr Value

auto find(R &&Range, const T &Val)

Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.

static cl::opt< unsigned > MaxNumPaths("dfa-max-num-paths", cl::desc("Max number of paths enumerated around a switch"), cl::Hidden, cl::init(200))

LLVM_ABI BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, bool MapAtoms=true)

Return a copy of the specified basic block, but without embedding the block into a particular functio...

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)

Check a function for errors, useful for use when debugging a pass.

auto successors(const MachineBasicBlock *BB)

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

auto pred_size(const MachineBasicBlock *BB)

static cl::opt< bool > ClViewCfgBefore("dfa-jump-view-cfg-before", cl::desc("View the CFG before DFA Jump Threading"), cl::Hidden, cl::init(false))

auto map_range(ContainerTy &&C, FuncTy F)

static cl::opt< double > MaxClonedRate("dfa-max-cloned-rate", cl::desc("Maximum cloned instructions rate accepted for the transformation"), cl::Hidden, cl::init(7.5))

bool any_of(R &&range, UnaryPredicate P)

Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.

void sort(IteratorTy Start, IteratorTy End)

@ RF_IgnoreMissingLocals

If this flag is set, the remapper ignores missing function-local entries (Argument,...

@ RF_NoModuleLevelChanges

If this flag is set, the remapper knows that only local values within a function (such as an instruct...

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

static cl::opt< unsigned > MaxNumVisitiedPaths("dfa-max-num-visited-paths", cl::desc("Max number of blocks visited while enumerating paths around a switch"), cl::Hidden, cl::init(2500))

std::string join(IteratorT Begin, IteratorT End, StringRef Separator)

Joins the strings in the range [Begin, End), adding Separator between the elements.

static cl::opt< bool > EarlyExitHeuristic("dfa-early-exit-heuristic", cl::desc("Exit early if an unpredictable value come from the same loop"), cl::Hidden, cl::init(true))

void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)

Convert the instruction operands from referencing the current values into those specified by VM.

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

LLVM_ABI bool VerifyDomInfo

Enables verification of dominator trees.

static cl::opt< unsigned > MaxOuterUseBlocks("dfa-max-out-use-blocks", cl::desc("Maximum unduplicated blocks with outer uses " "accepted for the transformation"), cl::Hidden, cl::init(40))

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

auto find_if(R &&Range, UnaryPredicate P)

Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.

static cl::opt< unsigned > MaxPathLength("dfa-max-path-length", cl::desc("Max number of blocks searched to find a threading path"), cl::Hidden, cl::init(20))

auto predecessors(const MachineBasicBlock *BB)

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))

bool pred_empty(const BasicBlock *BB)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

static cl::opt< unsigned > CostThreshold("dfa-cost-threshold", cl::desc("Maximum cost accepted for the transformation"), cl::Hidden, cl::init(50))

static LLVM_ABI void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)

Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Integrate with the new Pass Manager.

Definition DFAJumpThreading.cpp:1529