JumpThreading.cpp Source File (original) (raw)

71#include

72#include

73#include

74#include

75#include

77using namespace llvm;

78using namespace jumpthreading;

80#define DEBUG_TYPE "jump-threading"

82 STATISTIC(NumThreads, "Number of jumps threaded");

83 STATISTIC(NumFolds, "Number of terminators folded");

84 STATISTIC(NumDupes, "Number of branch blocks duplicated to eliminate phi");

88 cl::desc("Max block size to duplicate for jump threading"),

93 "jump-threading-implication-search-threshold",

94 cl::desc("The number of predecessors to search for a stronger "

95 "condition to use to thread over a weaker condition"),

99 "jump-threading-phi-threshold",

100 cl::desc("Max PHIs in BB to duplicate for jump threading"), cl::init(76),

102

104 "jump-threading-across-loop-headers",

105 cl::desc("Allow JumpThreading to thread across loop headers, for testing"),

107

110}

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

149 if (!CondBr)

150 return;

151

152 uint64_t TrueWeight, FalseWeight;

154 return;

155

156 if (TrueWeight + FalseWeight == 0)

157

158

159

160 return;

161

162

163

164 auto GetPredOutEdge =

166 BasicBlock *PhiBB) -> std::pair<BasicBlock *, BasicBlock *> {

167 auto *PredBB = IncomingBB;

168 auto *SuccBB = PhiBB;

170 while (true) {

171 BranchInst *PredBr = dyn_cast(PredBB->getTerminator());

173 return {PredBB, SuccBB};

174 Visited.insert(PredBB);

175 auto *SinglePredBB = PredBB->getSinglePredecessor();

176 if (!SinglePredBB)

177 return {nullptr, nullptr};

178

179

180

181 if (Visited.count(SinglePredBB))

182 return {nullptr, nullptr};

183

184 SuccBB = PredBB;

185 PredBB = SinglePredBB;

186 }

187 };

188

191 ConstantInt *CI = dyn_cast(PhiOpnd);

192

194 continue;

195

198 TrueWeight, TrueWeight + FalseWeight)

200 FalseWeight, TrueWeight + FalseWeight));

201

202 auto PredOutEdge = GetPredOutEdge(PN->getIncomingBlock(i), BB);

203 if (!PredOutEdge.first)

204 return;

205

206 BasicBlock *PredBB = PredOutEdge.first;

208 if (!PredBr)

209 return;

210

211 uint64_t PredTrueWeight, PredFalseWeight;

212

213

214

215

217 continue;

218

219

220

222 continue;

223

225 if (PredBr->getSuccessor(0) == PredOutEdge.second) {

228 } else {

231 }

233 }

234}

235

239

246

247 bool Changed =

249 std::make_unique(

250 &DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy),

251 std::nullopt, std::nullopt);

252

253 if (!Changed)

255

256

258

259#if defined(EXPENSIVE_CHECKS)

261 DominatorTree::VerificationLevel::Full) &&

262 "DT broken after JumpThreading");

266 "PDT broken after JumpThreading");

267#else

269 DominatorTree::VerificationLevel::Fast) &&

270 "DT broken after JumpThreading");

274 "PDT broken after JumpThreading");

275#endif

276

277 return getPreservedAnalysis();

278}

279

284 std::unique_ptr DTU_,

285 std::optional<BlockFrequencyInfo *> BFI_,

286 std::optional<BranchProbabilityInfo *> BPI_) {

288 F = &F_;

289 FAM = FAM_;

290 TLI = TLI_;

291 TTI = TTI_;

292 LVI = LVI_;

293 AA = AA_;

294 DTU = std::move(DTU_);

295 BFI = BFI_;

296 BPI = BPI_;

298 F->getParent(), Intrinsic::experimental_guard);

299 HasGuards = GuardDecl && !GuardDecl->use_empty();

300

301

302

306 BBDupThreshold = 3;

307 else

308 BBDupThreshold = DefaultBBDupThreshold;

309

310

311

313 assert(DTU && "DTU isn't passed into JumpThreading before using it.");

314 assert(DTU->hasDomTree() && "JumpThreading relies on DomTree to proceed.");

316 for (auto &BB : *F)

318 Unreachable.insert(&BB);

319

322

323 bool EverChanged = false;

324 bool Changed;

325 do {

326 Changed = false;

327 for (auto &BB : *F) {

328 if (Unreachable.count(&BB))

329 continue;

330 while (processBlock(&BB))

331 Changed = ChangedSinceLastAnalysisUpdate = true;

332

333

334

335

336 if (&BB == &F->getEntryBlock() || DTU->isBBPendingDeletion(&BB))

337 continue;

338

340

341

342 LLVM_DEBUG(dbgs() << " JT: Deleting dead block '" << BB.getName()

343 << "' with terminator: " << *BB.getTerminator()

344 << '\n');

345 LoopHeaders.erase(&BB);

348 Changed = ChangedSinceLastAnalysisUpdate = true;

349 continue;

350 }

351

352

353

354 auto *BI = dyn_cast(BB.getTerminator());

355 if (BI && BI->isUnconditional()) {

356 BasicBlock *Succ = BI->getSuccessor(0);

357 if (

358

359 BB.getFirstNonPHIOrDbg(true)->isTerminator() &&

360

361

362 !LoopHeaders.count(&BB) && !LoopHeaders.count(Succ) &&

364

365

367 Changed = ChangedSinceLastAnalysisUpdate = true;

368 }

369 }

370 }

371 EverChanged |= Changed;

372 } while (Changed);

373

374

375

376 if (EverChanged)

377 for (auto &BB : *F) {

379 }

380

381 LoopHeaders.clear();

382 return EverChanged;

383}

384

385

386

387

388

389

390

391

394 bool Changed = false;

396

397

398

399 if (Cond->getParent() == KnownAtEndOfBB)

402

404 DVR.replaceVariableLocationOp(Cond, ToVal, true);

405

406

407

409 break;

410

411

413 break;

414 Changed |= I.replaceUsesOfWith(Cond, ToVal);

415 }

416 if (Cond->use_empty() && Cond ->mayHaveSideEffects()) {

417 Cond->eraseFromParent();

418 Changed = true;

419 }

420 return Changed;

421}

422

423

424

425

429 unsigned Threshold) {

430 assert(StopAt->getParent() == BB && "Not an instruction from proper BB?");

431

432

433

434

435 unsigned PhiCount = 0;

438 if (!isa(&I)) {

439 FirstNonPHI = &I;

440 break;

441 }

443 return ~0U;

444 }

445

446

448

449

450

451

452 unsigned Bonus = 0;

454

455

456

457 if (isa(StopAt))

458 Bonus = 6;

459

460

461 if (isa(StopAt))

462 Bonus = 8;

463 }

464

465

466

467 Threshold += Bonus;

468

469

470

471 unsigned Size = 0;

472 for (; &*I != StopAt; ++I) {

473

474

475 if (Size > Threshold)

477

478

479

480 if (I->getType()->isTokenTy() && I->isUsedOutsideOfBlock(BB))

481 return ~0U;

482

483

484

485 if (const CallInst *CI = dyn_cast(I))

486 if (CI->cannotDuplicate() || CI->isConvergent())

487 return ~0U;

488

491 continue;

492

493

495

496

497

498

499

500 if (const CallInst *CI = dyn_cast(I)) {

501 if (!isa(CI))

503 else if (!CI->getType()->isVectorTy())

505 }

506 }

507

508 return Size > Bonus ? Size - Bonus : 0;

509}

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

528

529 for (const auto &Edge : Edges)

530 LoopHeaders.insert(Edge.second);

531}

532

533

534

535

536

537

539 if (!Val)

540 return nullptr;

541

542

543 if (UndefValue *U = dyn_cast(Val))

544 return U;

545

548

549 return dyn_cast(Val);

550}

551

552

553

554

555

556

557

563

564

565

566

567

568 if (!RecursionSet.insert(V).second)

569 return false;

570

571

574 Result.emplace_back(KC, Pred);

575

576 return !Result.empty();

577 }

578

579

580

582 if ( || I->getParent() != BB) {

583

584

585

587 using namespace PatternMatch;

588

589

591

592

593

594

601 Result.emplace_back(KC, P);

602 }

603

604 return !Result.empty();

605 }

606

607

608 if (PHINode *PN = dyn_cast(I)) {

609 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {

610 Value *InVal = PN->getIncomingValue(i);

612 Result.emplace_back(KC, PN->getIncomingBlock(i));

613 } else {

615 PN->getIncomingBlock(i),

616 BB, CxtI);

618 Result.emplace_back(KC, PN->getIncomingBlock(i));

619 }

620 }

621

622 return !Result.empty();

623 }

624

625

626 if (CastInst *CI = dyn_cast(I)) {

627 Value *Source = CI->getOperand(0);

630 RecursionSet, CxtI);

631 if (Vals.empty())

632 return false;

633

634

635 for (auto &Val : Vals)

637 CI->getType(), DL))

638 Result.emplace_back(Folded, Val.second);

639

640 return !Result.empty();

641 }

642

643 if (FreezeInst *FI = dyn_cast(I)) {

644 Value *Source = FI->getOperand(0);

646 RecursionSet, CxtI);

647

648 erase_if(Result, [](auto &Pair) {

650 });

651

652 return !Result.empty();

653 }

654

655

656 if (I->getType()->getPrimitiveSizeInBits() == 1) {

657 using namespace PatternMatch;

659 return false;

660

661

662 Value *Op0, *Op1;

666

668 RecursionSet, CxtI);

670 RecursionSet, CxtI);

671

672 if (LHSVals.empty() && RHSVals.empty())

673 return false;

674

678 else

680

682

683

684

685 for (const auto &LHSVal : LHSVals)

686 if (LHSVal.first == InterestingVal || isa(LHSVal.first)) {

687 Result.emplace_back(InterestingVal, LHSVal.second);

688 LHSKnownBBs.insert(LHSVal.second);

689 }

690 for (const auto &RHSVal : RHSVals)

691 if (RHSVal.first == InterestingVal || isa(RHSVal.first)) {

692

693

694 if (!LHSKnownBBs.count(RHSVal.second))

695 Result.emplace_back(InterestingVal, RHSVal.second);

696 }

697

698 return !Result.empty();

699 }

700

701

702 if (I->getOpcode() == Instruction::Xor &&

703 isa(I->getOperand(1)) &&

704 cast(I->getOperand(1))->isOne()) {

707 if (Result.empty())

708 return false;

709

710

711 for (auto &R : Result)

713

714 return true;

715 }

716

717

718 } else if (BinaryOperator *BO = dyn_cast(I)) {

720 return false;

721 if (ConstantInt *CI = dyn_cast(BO->getOperand(1))) {

725

726

727 for (const auto &LHSVal : LHSVals) {

731

733 Result.emplace_back(KC, LHSVal.second);

734 }

735 }

736

737 return !Result.empty();

738 }

739

740

741 if (CmpInst *Cmp = dyn_cast(I)) {

743 return false;

744 Type *CmpType = Cmp->getType();

745 Value *CmpLHS = Cmp->getOperand(0);

746 Value *CmpRHS = Cmp->getOperand(1);

748

749 PHINode *PN = dyn_cast(CmpLHS);

750 if (!PN)

751 PN = dyn_cast(CmpRHS);

752

753

754

755 if (PN && PN->getParent() == BB && !LoopHeaders.contains(BB)) {

757

758

762 if (PN == CmpLHS) {

765 } else {

768 }

770 if (!Res) {

771 if (!isa(RHS))

772 continue;

773

774

775 auto LHSInst = dyn_cast(LHS);

776 if (LHSInst && LHSInst->getParent() == BB)

777 continue;

778

780 BB, CxtI ? CxtI : Cmp);

781 }

782

784 Result.emplace_back(KC, PredBB);

785 }

786

787 return !Result.empty();

788 }

789

790

791

792 if (isa(CmpRHS) && !CmpType->isVectorTy()) {

793 Constant *CmpConst = cast(CmpRHS);

794

795 if (!isa(CmpLHS) ||

796 cast(CmpLHS)->getParent() != BB) {

798

799

801 CxtI ? CxtI : Cmp);

803 Result.emplace_back(KC, P);

804 }

805

806 return !Result.empty();

807 }

808

809

810

811

812 {

813 using namespace PatternMatch;

814

817 if (isa(CmpConst) &&

819 if (!isa(AddLHS) ||

820 cast(AddLHS)->getParent() != BB) {

822

823

824

826 AddLHS, P, BB, CxtI ? CxtI : cast(CmpLHS));

827

829

830

832 Pred, cast(CmpConst)->getValue());

833

839 else

840 continue;

841

842 Result.emplace_back(ResC, P);

843 }

844

845 return !Result.empty();

846 }

847 }

848 }

849

850

851

855

856 for (const auto &LHSVal : LHSVals) {

861 Result.emplace_back(KC, LHSVal.second);

862 }

863

864 return !Result.empty();

865 }

866 }

867

868 if (SelectInst *SI = dyn_cast(I)) {

869

870

874 if ((TrueVal || FalseVal) &&

877 for (auto &C : Conds) {

879

880

881 bool KnownCond;

883

884 KnownCond = CI->isOne();

885 } else {

886 assert(isa(Cond) && "Unexpected condition value");

887

888

889

890 KnownCond = (TrueVal != nullptr);

891 }

892

893

894 if (Constant *Val = KnownCond ? TrueVal : FalseVal)

895 Result.emplace_back(Val, C.second);

896 }

897

898 return !Result.empty();

899 }

900 }

901

902

903 assert(CxtI->getParent() == BB && "CxtI should be in BB");

907 Result.emplace_back(KC, Pred);

908 }

909

910 return !Result.empty();

911}

912

913

914

915

916

917

920 unsigned MinSucc = 0;

922

923 unsigned MinNumPreds = pred_size(TestBB);

924 for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) {

926 unsigned NumPreds = pred_size(TestBB);

927 if (NumPreds < MinNumPreds) {

928 MinSucc = i;

929 MinNumPreds = NumPreds;

930 }

931 }

932

933 return MinSucc;

934}

935

938

939

940

944}

945

946

947

949

950

951 if (DTU->isBBPendingDeletion(BB) ||

953 return false;

954

955

956

957

958

960 return true;

961

963 return true;

964

965

967 return true;

968

969

971

972

973

974 Value *Condition;

976 if (BranchInst *BI = dyn_cast(Terminator)) {

977

978 if (BI->isUnconditional()) return false;

979 Condition = BI->getCondition();

980 } else if (SwitchInst *SI = dyn_cast(Terminator)) {

981 Condition = SI->getCondition();

982 } else if (IndirectBrInst *IB = dyn_cast(Terminator)) {

983

984 if (IB->getNumSuccessors() == 0) return false;

985 Condition = IB->getAddress()->stripPointerCasts();

987 } else {

988 return false;

989 }

990

991

992 bool ConstantFolded = false;

993

994

995

996 if (Instruction *I = dyn_cast(Condition)) {

997 Value *SimpleVal =

999 if (SimpleVal) {

1000 I->replaceAllUsesWith(SimpleVal);

1002 I->eraseFromParent();

1003 Condition = SimpleVal;

1004 ConstantFolded = true;

1005 }

1006 }

1007

1008

1009

1010 auto *FI = dyn_cast(Condition);

1011 if (isa(Condition) ||

1012 (FI && isa(FI->getOperand(0)) && FI->hasOneUse())) {

1014 std::vectorDominatorTree::UpdateType Updates;

1015

1016

1019 for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {

1020 if (i == BestSucc) continue;

1024 }

1025

1027 << "' folding undef terminator: " << *BBTerm << '\n');

1030 ++NumFolds;

1032 DTU->applyUpdatesPermissive(Updates);

1033 if (FI)

1034 FI->eraseFromParent();

1035 return true;

1036 }

1037

1038

1039

1040

1043 << "' folding terminator: " << *BB->getTerminator()

1044 << '\n');

1045 ++NumFolds;

1047 if (auto *BPI = getBPI())

1048 BPI->eraseBlock(BB);

1049 return true;

1050 }

1051

1052 Instruction *CondInst = dyn_cast(Condition);

1053

1054

1055 if (!CondInst) {

1056

1058 return true;

1059 return ConstantFolded;

1060 }

1061

1062

1063 Value *CondWithoutFreeze = CondInst;

1064 if (auto *FI = dyn_cast(CondInst))

1065 CondWithoutFreeze = FI->getOperand(0);

1066

1067 if (CmpInst *CondCmp = dyn_cast(CondWithoutFreeze)) {

1068

1069

1070

1071 if (Constant *CondConst = dyn_cast(CondCmp->getOperand(1))) {

1073 LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),

1075 false);

1076 if (Res) {

1077

1078

1079

1080

1081

1082

1083

1085 return true;

1086 }

1087

1088

1089

1091 return true;

1092 }

1093 }

1094

1097 return true;

1098

1099

1100

1101

1102

1103 Value *SimplifyValue = CondWithoutFreeze;

1104

1105 if (CmpInst *CondCmp = dyn_cast(SimplifyValue))

1106 if (isa(CondCmp->getOperand(1)))

1107 SimplifyValue = CondCmp->getOperand(0);

1108

1109

1110

1111 if (LoadInst *LoadI = dyn_cast(SimplifyValue))

1113 return true;

1114

1115

1116 if (PHINode *PN = dyn_cast(CondInst))

1117 if (PN->getParent() == BB && isa(BB->getTerminator()))

1119

1120

1121

1122

1124 return true;

1125

1126

1127

1128 PHINode *PN = dyn_cast(CondWithoutFreeze);

1131

1132

1133 if (CondInst->getOpcode() == Instruction::Xor &&

1136

1137

1138

1140 return true;

1141

1142 return false;

1143}

1144

1146 auto *BI = dyn_cast(BB->getTerminator());

1147 if (!BI || !BI->isConditional())

1148 return false;

1149

1150 Value *Cond = BI->getCondition();

1151

1152

1153

1154

1155

1156 auto *FICond = dyn_cast(Cond);

1157 if (FICond && FICond->hasOneUse())

1158 Cond = FICond->getOperand(0);

1159 else

1160 FICond = nullptr;

1161

1164 unsigned Iter = 0;

1165

1167

1169 auto *PBI = dyn_cast(CurrentPred->getTerminator());

1170 if (!PBI || !PBI->isConditional())

1171 return false;

1172 if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)

1173 return false;

1174

1175 bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;

1176 std::optional Implication =

1178

1179

1180

1181 if (!Implication && FICond && isa(PBI->getCondition())) {

1182 if (cast(PBI->getCondition())->getOperand(0) ==

1183 FICond->getOperand(0))

1184 Implication = CondIsTrue;

1185 }

1186

1187 if (Implication) {

1188 BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);

1189 BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);

1192 UncondBI->setDebugLoc(BI->getDebugLoc());

1193 ++NumFolds;

1194 BI->eraseFromParent();

1195 if (FICond)

1196 FICond->eraseFromParent();

1197

1199 if (auto *BPI = getBPI())

1200 BPI->eraseBlock(BB);

1201 return true;

1202 }

1203 CurrentBB = CurrentPred;

1205 }

1206

1207 return false;

1208}

1209

1210

1212 if (Instruction *OpInst = dyn_cast(Op))

1213 if (OpInst->getParent() == BB)

1214 return true;

1215 return false;

1216}

1217

1218

1219

1220

1221

1223

1224 if (!LoadI->isUnordered()) return false;

1225

1226

1227

1230 return false;

1231

1232

1233

1234

1236 return false;

1237

1239

1240

1241

1242 if (isOpDefinedInBlock(LoadedPtr, LoadBB) && !isa(LoadedPtr))

1243 return false;

1244

1245

1246

1248 bool IsLoadCSE;

1250

1253 LoadI, LoadBB, BBIt, DefMaxInstsToScan, &BatchAA, &IsLoadCSE)) {

1254

1255

1256

1257 if (IsLoadCSE) {

1258 LoadInst *NLoadI = cast(AvailableVal);

1261 };

1262

1263

1264

1265 if (AvailableVal == LoadI)

1267 if (AvailableVal->getType() != LoadI->getType()) {

1270 cast(AvailableVal)->setDebugLoc(LoadI->getDebugLoc());

1271 }

1274 return true;

1275 }

1276

1277

1278

1279

1280 if (BBIt != LoadBB->begin())

1281 return false;

1282

1283

1284

1286

1288

1290

1291 AvailablePredsTy AvailablePreds;

1292 BasicBlock *OneUnavailablePred = nullptr;

1294

1295

1296

1298

1299 if (!PredsScanned.insert(PredBB).second)

1300 continue;

1301

1302 BBIt = PredBB->end();

1303 unsigned NumScanedInst = 0;

1304 Value *PredAvailable = nullptr;

1305

1306

1308 "Attempting to CSE volatile or atomic loads");

1309

1310

1315 AATags);

1318 &BatchAA, &IsLoadCSE, &NumScanedInst);

1319

1320

1321

1323 while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->begin() &&

1326 if (SinglePredBB) {

1327 BBIt = SinglePredBB->end();

1329 Loc, AccessTy, LoadI->isAtomic(), SinglePredBB, BBIt,

1331 &NumScanedInst);

1332 }

1333 }

1334

1335 if (!PredAvailable) {

1336 OneUnavailablePred = PredBB;

1337 continue;

1338 }

1339

1340 if (IsLoadCSE)

1341 CSELoads.push_back(cast(PredAvailable));

1342

1343

1344

1345 AvailablePreds.emplace_back(PredBB, PredAvailable);

1346 }

1347

1348

1349

1350 if (AvailablePreds.empty()) return false;

1351

1352

1353

1354

1355

1356

1357 BasicBlock *UnavailablePred = nullptr;

1358

1359

1360

1361

1362

1363

1364

1365

1366

1367 if (PredsScanned.size() != AvailablePreds.size() &&

1369 for (auto I = LoadBB->begin(); &*I != LoadI; ++I)

1371 return false;

1372

1373

1374

1375

1376 if (PredsScanned.size() == AvailablePreds.size()+1 &&

1378 UnavailablePred = OneUnavailablePred;

1379 } else if (PredsScanned.size() != AvailablePreds.size()) {

1380

1381

1384

1385 for (const auto &AvailablePred : AvailablePreds)

1386 AvailablePredSet.insert(AvailablePred.first);

1387

1388

1390

1391 if (isa(P->getTerminator()))

1392 return false;

1393

1394 if (!AvailablePredSet.count(P))

1396 }

1397

1398

1399 UnavailablePred = splitBlockPreds(LoadBB, PredsToSplit, "thread-pre-split");

1400 }

1401

1402

1403

1404

1405 if (UnavailablePred) {

1407 "Can't handle critical edge here!");

1414 if (AATags)

1416

1417 AvailablePreds.emplace_back(UnavailablePred, NewVal);

1418 }

1419

1420

1421

1422 array_pod_sort(AvailablePreds.begin(), AvailablePreds.end());

1423

1424

1429

1430

1431

1433 AvailablePredsTy::iterator I =

1435

1436 assert(I != AvailablePreds.end() && I->first == P &&

1437 "Didn't find entry for predecessor!");

1438

1439

1440

1441

1442

1443 Value *&PredV = I->second;

1446 PredV, LoadI->getType(), "", P->getTerminator()->getIterator());

1447

1449 }

1450

1451 for (LoadInst *PredLoadI : CSELoads) {

1454 }

1455

1458

1459 return true;

1460}

1461

1462

1463

1464

1469 assert(!PredToDestList.empty());

1470

1471

1472

1473

1474

1476

1477

1478

1479

1480

1481 DestPopularity[nullptr] = 0;

1483 DestPopularity[SuccBB] = 0;

1484

1485 for (const auto &PredToDest : PredToDestList)

1486 if (PredToDest.second)

1487 DestPopularity[PredToDest.second]++;

1488

1489

1491

1492

1493 return MostPopular->first;

1494}

1495

1496

1497

1503 assert(PredBB && "Expected a single predecessor");

1504

1505 if (Constant *Cst = dyn_cast(V)) {

1506 return Cst;

1507 }

1508

1509

1511 if ( || (I->getParent() != BB && I->getParent() != PredBB)) {

1513 }

1514

1515

1516 if (PHINode *PHI = dyn_cast(V)) {

1517 if (PHI->getParent() == PredBB)

1518 return dyn_cast(PHI->getIncomingValueForBlock(PredPredBB));

1519 return nullptr;

1520 }

1521

1522

1523 if (CmpInst *CondCmp = dyn_cast(V)) {

1524 if (CondCmp->getParent() == BB) {

1529 if (Op0 && Op1) {

1531 Op1, DL);

1532 }

1533 }

1534 return nullptr;

1535 }

1536

1537 return nullptr;

1538}

1539

1543

1544

1545 if (LoopHeaders.count(BB))

1546 return false;

1547

1550 CxtI)) {

1551

1552

1554 }

1555

1557 "computeValueKnownInPredecessors returned true with no values");

1558

1560 for (const auto &PredValue : PredValues) {

1562 << "': FOUND condition = " << *PredValue.first

1563 << " for pred '" << PredValue.second->getName() << "'.\n";

1564 });

1565

1566

1567

1568

1569

1572

1575 Constant *OnlyVal = nullptr;

1577

1578 for (const auto &PredValue : PredValues) {

1579 BasicBlock *Pred = PredValue.second;

1580 if (!SeenPreds.insert(Pred).second)

1581 continue;

1582

1583 Constant *Val = PredValue.first;

1584

1586 if (isa(Val))

1587 DestBB = nullptr;

1589 assert(isa(Val) && "Expecting a constant integer");

1590 DestBB = BI->getSuccessor(cast(Val)->isZero());

1592 assert(isa(Val) && "Expecting a constant integer");

1593 DestBB = SI->findCaseValue(cast(Val))->getCaseSuccessor();

1594 } else {

1596 && "Unexpected terminator");

1597 assert(isa(Val) && "Expecting a constant blockaddress");

1598 DestBB = cast(Val)->getBasicBlock();

1599 }

1600

1601

1602 if (PredToDestList.empty()) {

1603 OnlyDest = DestBB;

1604 OnlyVal = Val;

1605 } else {

1606 if (OnlyDest != DestBB)

1607 OnlyDest = MultipleDestSentinel;

1608

1609

1610 if (Val != OnlyVal)

1611 OnlyVal = MultipleVal;

1612 }

1613

1614

1615

1617 continue;

1618

1620 }

1621

1622

1623 if (PredToDestList.empty())

1624 return false;

1625

1626

1627

1628

1629 if (OnlyDest && OnlyDest != MultipleDestSentinel) {

1631 bool SeenFirstBranchToOnlyDest = false;

1632 std::vector DominatorTree::UpdateType Updates;

1635 if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {

1636 SeenFirstBranchToOnlyDest = true;

1637 } else {

1638 SuccBB->removePredecessor(BB, true);

1640 }

1641 }

1642

1643

1646 NewBI->setDebugLoc(Term->getDebugLoc());

1647 ++NumFolds;

1648 Term->eraseFromParent();

1649 DTU->applyUpdatesPermissive(Updates);

1650 if (auto *BPI = getBPI())

1651 BPI->eraseBlock(BB);

1652

1653

1654

1655 if (auto *CondInst = dyn_cast(Cond)) {

1656 if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())

1657 CondInst->eraseFromParent();

1658

1659

1660

1661

1662

1663

1664

1665 else if (OnlyVal && OnlyVal != MultipleVal)

1667 }

1668 return true;

1669 }

1670 }

1671

1672

1673

1674

1675

1676 BasicBlock *MostPopularDest = OnlyDest;

1677

1678 if (MostPopularDest == MultipleDestSentinel) {

1679

1680

1681

1683 [&](const std::pair<BasicBlock *, BasicBlock *> &PredToDest) {

1684 return LoopHeaders.contains(PredToDest.second);

1685 });

1686

1687 if (PredToDestList.empty())

1688 return false;

1689

1691 }

1692

1693

1694

1696 for (const auto &PredToDest : PredToDestList)

1697 if (PredToDest.second == MostPopularDest) {

1698 BasicBlock *Pred = PredToDest.first;

1699

1700

1701

1702

1704 if (Succ == BB)

1706 }

1707

1708

1709

1710 if (!MostPopularDest)

1713

1714

1715 return tryThreadEdge(BB, PredsToFactor, MostPopularDest);

1716}

1717

1718

1719

1720

1723

1724

1725

1728

1729

1730

1731

1732

1733

1734

1735

1739 if (PredBr->isUnconditional()) {

1740 PredBBs[0] = PredBB;

1741

1743 return true;

1744 }

1745 }

1746

1747 return false;

1748}

1749

1750

1751

1752

1755

1756

1757

1758 if (isa(BO->getOperand(0)) ||

1759 isa(BO->getOperand(1)))

1760 return false;

1761

1762

1763

1764 if (!isa(BB->front()))

1765 return false;

1766

1767

1769 return false;

1770

1771

1772

1773

1774

1775

1776

1777

1778

1779

1780

1781

1782

1783

1784

1785

1786

1787

1788

1790 bool isLHS = true;

1796 return false;

1797 isLHS = false;

1798 }

1799

1801 "computeValueKnownInPredecessors returned true with no values");

1802

1803

1804

1805 unsigned NumTrue = 0, NumFalse = 0;

1806 for (const auto &XorOpValue : XorOpValues) {

1807 if (isa(XorOpValue.first))

1808

1809 continue;

1810 if (cast(XorOpValue.first)->isZero())

1811 ++NumFalse;

1812 else

1813 ++NumTrue;

1814 }

1815

1816

1818 if (NumTrue > NumFalse)

1820 else if (NumTrue != 0 || NumFalse != 0)

1822

1823

1824

1826 for (const auto &XorOpValue : XorOpValues) {

1827 if (XorOpValue.first != SplitVal && !isa(XorOpValue.first))

1828 continue;

1829

1830 BlocksToFoldInto.push_back(XorOpValue.second);

1831 }

1832

1833

1834

1835 if (BlocksToFoldInto.size() ==

1836 cast(BB->front()).getNumIncomingValues()) {

1837 if (!SplitVal) {

1838

1841 } else if (SplitVal->isZero() && BO != BO->getOperand(isLHS)) {

1842

1845 } else {

1846

1848 }

1849

1850 return true;

1851 }

1852

1853

1854

1856 return isa(Pred->getTerminator());

1857 }))

1858 return false;

1859

1860

1862}

1863

1864

1865

1866

1872

1873

1874 Value *IV = PN.getIncomingValueForBlock(OldPred);

1875

1876

1877 if (Instruction *Inst = dyn_cast(IV)) {

1880 IV = I->second;

1881 }

1882

1883 PN.addIncoming(IV, NewPred);

1884 }

1885}

1886

1887

1890 if (!SinglePred)

1891 return false;

1892

1896 return false;

1897

1898

1899 if (LoopHeaders.erase(SinglePred))

1900 LoopHeaders.insert(BB);

1901

1904

1905

1906

1907

1908

1909

1910

1911

1912

1913

1914

1915

1916

1917

1918

1919

1920

1921

1922

1923

1924

1925

1926

1927

1928

1929

1930

1931

1934 return true;

1935}

1936

1937

1938

1941

1942

1943

1944

1949

1951

1952

1953 for (Use &U : I.uses()) {

1955 if (PHINode *UserPN = dyn_cast(User)) {

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

1957 continue;

1958 } else if (User->getParent() == BB)

1959 continue;

1960

1962 }

1963

1964

1967 return DbgVal->getParent() == BB;

1968 });

1970 return DbgVarRec->getParent() == BB;

1971 });

1972

1973

1974 if (UsesToRename.empty() && DbgValues.empty() && DbgVariableRecords.empty())

1975 continue;

1976 LLVM_DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");

1977

1978

1979

1980

1981 SSAUpdate.Initialize(I.getType(), I.getName());

1984

1985 while (!UsesToRename.empty())

1987 if (!DbgValues.empty() || !DbgVariableRecords.empty()) {

1990 DbgValues.clear();

1991 DbgVariableRecords.clear();

1992 }

1993

1995 }

1996}

1997

1998

1999

2000

2001

2007

2008

2009

2010

2011

2012 auto RetargetDbgValueIfPossible = [&](Instruction *NewInst) -> bool {

2013 auto DbgInstruction = dyn_cast(NewInst);

2014 if (!DbgInstruction)

2015 return false;

2016

2018 for (auto DbgOperand : DbgInstruction->location_ops()) {

2019 auto DbgOperandInstruction = dyn_cast(DbgOperand);

2020 if (!DbgOperandInstruction)

2021 continue;

2022

2023 auto I = ValueMapping.find(DbgOperandInstruction);

2024 if (I != ValueMapping.end()) {

2025 OperandsToRemap.insert(

2026 std::pair<Value *, Value *>(DbgOperand, I->second));

2027 }

2028 }

2029

2030 for (auto &[OldOp, MappedOp] : OperandsToRemap)

2031 DbgInstruction->replaceVariableLocationOp(OldOp, MappedOp);

2032 return true;

2033 };

2034

2035

2036

2037 auto RetargetDbgVariableRecordIfPossible = [&](DbgVariableRecord *DVR) {

2039 for (auto *Op : DVR->location_ops()) {

2040 Instruction *OpInst = dyn_cast(Op);

2041 if (!OpInst)

2042 continue;

2043

2044 auto I = ValueMapping.find(OpInst);

2045 if (I != ValueMapping.end())

2046 OperandsToRemap.insert({OpInst, I->second});

2047 }

2048

2049 for (auto &[OldOp, MappedOp] : OperandsToRemap)

2050 DVR->replaceVariableLocationOp(OldOp, MappedOp);

2051 };

2052

2054

2055

2056

2057

2058 for (; PHINode *PN = dyn_cast(BI); ++BI) {

2061 ValueMapping[PN] = NewPN;

2062 }

2063

2064

2065

2066

2072

2076 RetargetDbgVariableRecordIfPossible(&DVR);

2077 };

2078

2079

2080

2081

2082 for (; BI != BE; ++BI) {

2084 New->setName(BI->getName());

2085 New->insertInto(NewBB, NewBB->end());

2086 ValueMapping[&*BI] = New;

2088

2089 CloneAndRemapDbgInfo(New, &*BI);

2090

2091 if (RetargetDbgValueIfPossible(New))

2092 continue;

2093

2094

2095 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)

2096 if (Instruction *Inst = dyn_cast(New->getOperand(i))) {

2098 if (I != ValueMapping.end())

2099 New->setOperand(i, I->second);

2100 }

2101 }

2102

2103

2104

2105 if (BE != RangeBB->end() && BE->hasDbgRecords()) {

2106

2109 auto DVRRange = EndMarker->cloneDebugInfoFrom(Marker, std::nullopt);

2111 RetargetDbgVariableRecordIfPossible(&DVR);

2112 }

2113}

2114

2115

2118

2119

2120

2121

2122

2123

2124

2125

2126

2127

2128

2129

2130

2131

2132

2133

2134

2136 if (!CondBr)

2137 return false;

2138

2139

2141 if (!PredBB)

2142 return false;

2143

2144

2145

2146

2149 return false;

2150

2151

2152

2154 return false;

2155

2156

2157

2158

2159

2160

2161

2162

2163

2164

2166 return false;

2167

2168

2169 if (LoopHeaders.count(PredBB))

2170 return false;

2171

2172

2174 return false;

2175

2176

2177

2178

2179 unsigned ZeroCount = 0;

2180 unsigned OneCount = 0;

2185

2186 if (isa(P->getTerminator()))

2187 continue;

2188 if (ConstantInt *CI = dyn_cast_or_null(

2190 if (CI->isZero()) {

2191 ZeroCount++;

2192 ZeroPred = P;

2193 } else if (CI->isOne()) {

2194 OneCount++;

2195 OnePred = P;

2196 }

2197 }

2198 }

2199

2200

2202 if (ZeroCount == 1) {

2203 PredPredBB = ZeroPred;

2204 } else if (OneCount == 1) {

2205 PredPredBB = OnePred;

2206 } else {

2207 return false;

2208 }

2209

2211

2212

2213 if (SuccBB == BB) {

2215 << "' - would thread to self!\n");

2216 return false;

2217 }

2218

2219

2220

2221 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {

2223 bool BBIsHeader = LoopHeaders.count(BB);

2224 bool SuccIsHeader = LoopHeaders.count(SuccBB);

2225 dbgs() << " Not threading across "

2226 << (BBIsHeader ? "loop header BB '" : "block BB '")

2227 << BB->getName() << "' to dest "

2228 << (SuccIsHeader ? "loop header BB '" : "block BB '")

2230 << "' - it might create an irreducible loop!\n";

2231 });

2232 return false;

2233 }

2234

2235

2240

2241

2242

2243

2244 if (BBCost > BBDupThreshold || PredBBCost > BBDupThreshold ||

2245 BBCost + PredBBCost > BBDupThreshold) {

2247 << "' - Cost is too high: " << PredBBCost

2248 << " for PredBB, " << BBCost << "for BB\n");

2249 return false;

2250 }

2251

2252

2254 return true;

2255}

2256

2262 << BB->getName() << "'\n");

2263

2264

2265 bool HasProfile = doesBlockHaveProfileData(BB);

2266 auto *BFI = getOrCreateBFI(HasProfile);

2267 auto *BPI = getOrCreateBPI(BFI != nullptr);

2268

2271

2276

2277

2278 if (BFI) {

2279 assert(BPI && "It's expected BPI to exist along with BFI");

2280 auto NewBBFreq = BFI->getBlockFreq(PredPredBB) *

2281 BPI->getEdgeProbability(PredPredBB, PredBB);

2282 BFI->setBlockFreq(NewBB, NewBBFreq);

2283 }

2284

2285

2286

2287

2290 PredPredBB);

2291

2292

2293 if (BPI)

2294 BPI->copyEdgeProbabilities(PredBB, NewBB);

2295

2296

2297

2298

2300 for (unsigned i = 0, e = PredPredTerm->getNumSuccessors(); i != e; ++i)

2301 if (PredPredTerm->getSuccessor(i) == PredBB) {

2304 }

2305

2307 ValueMapping);

2309 ValueMapping);

2310

2311 DTU->applyUpdatesPermissive(

2316

2317 updateSSA(PredBB, NewBB, ValueMapping);

2318

2319

2320

2323

2326 threadEdge(BB, PredsToFactor, SuccBB);

2327}

2328

2329

2333

2334 if (SuccBB == BB) {

2336 << "' - would thread to self!\n");

2337 return false;

2338 }

2339

2340

2341

2342 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {

2344 bool BBIsHeader = LoopHeaders.count(BB);

2345 bool SuccIsHeader = LoopHeaders.count(SuccBB);

2346 dbgs() << " Not threading across "

2347 << (BBIsHeader ? "loop header BB '" : "block BB '") << BB->getName()

2348 << "' to dest " << (SuccIsHeader ? "loop header BB '" : "block BB '")

2349 << SuccBB->getName() << "' - it might create an irreducible loop!\n";

2350 });

2351 return false;

2352 }

2353

2356 if (JumpThreadCost > BBDupThreshold) {

2358 << "' - Cost is too high: " << JumpThreadCost << "\n");

2359 return false;

2360 }

2361

2363 return true;

2364}

2365

2366

2367

2368

2372 assert(SuccBB != BB && "Don't create an infinite loop");

2373

2374 assert(!LoopHeaders.count(BB) && !LoopHeaders.count(SuccBB) &&

2375 "Don't thread across loop headers");

2376

2377

2378 bool HasProfile = doesBlockHaveProfileData(BB);

2379 auto *BFI = getOrCreateBFI(HasProfile);

2380 auto *BPI = getOrCreateBPI(BFI != nullptr);

2381

2382

2384 if (PredBBs.size() == 1)

2385 PredBB = PredBBs[0];

2386 else {

2388 << " common predecessors.\n");

2389 PredBB = splitBlockPreds(BB, PredBBs, ".thr_comm");

2390 }

2391

2392

2394 << "' to '" << SuccBB->getName()

2395 << ", across block:\n " << *BB << "\n");

2396

2397 LVI->threadEdge(PredBB, BB, SuccBB);

2398

2400 BB->getName()+".thread",

2403

2404

2405 if (BFI) {

2406 assert(BPI && "It's expected BPI to exist along with BFI");

2407 auto NewBBFreq =

2408 BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);

2409 BFI->setBlockFreq(NewBB, NewBBFreq);

2410 }

2411

2412

2415 PredBB);

2416

2417

2418

2421

2422

2423

2425

2426

2427

2428

2430 for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)

2434 }

2435

2436

2440

2441 updateSSA(BB, NewBB, ValueMapping);

2442

2443

2444

2445

2447

2448

2449 updateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB, BFI, BPI, HasProfile);

2450

2451

2452 ++NumThreads;

2453}

2454

2455

2456

2457

2460 const char *Suffix) {

2462

2463

2464

2466 auto *BFI = getBFI();

2467 if (BFI) {

2468 auto *BPI = getOrCreateBPI(true);

2469 for (auto *Pred : Preds)

2470 FreqMap.insert(std::make_pair(

2471 Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));

2472 }

2473

2474

2475

2477 std::string NewName = std::string(Suffix) + ".split-lp";

2479 } else {

2481 }

2482

2483 std::vectorDominatorTree::UpdateType Updates;

2484 Updates.reserve((2 * Preds.size()) + NewBBs.size());

2485 for (auto *NewBB : NewBBs) {

2491 if (BFI)

2492 NewBBFreq += FreqMap.lookup(Pred);

2493 }

2494 if (BFI)

2495 BFI->setBlockFreq(NewBB, NewBBFreq);

2496 }

2497

2498 DTU->applyUpdatesPermissive(Updates);

2499 return NewBBs[0];

2500}

2501

2502bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {

2505 return false;

2506

2508}

2509

2510

2511

2512

2513void JumpThreadingPass::updateBlockFreqAndEdgeWeight(BasicBlock *PredBB,

2519 bool HasProfile) {

2520 assert(((BFI && BPI) || (!BFI && !BFI)) &&

2521 "Both BFI & BPI should either be set or unset");

2522

2523 if (!BFI) {

2524 assert(!HasProfile &&

2525 "It's expected to have BFI/BPI when profile info exists");

2526 return;

2527 }

2528

2529

2530

2531 auto BBOrigFreq = BFI->getBlockFreq(BB);

2532 auto NewBBFreq = BFI->getBlockFreq(NewBB);

2533 auto BB2SuccBBFreq = BBOrigFreq * BPI->getEdgeProbability(BB, SuccBB);

2534 auto BBNewFreq = BBOrigFreq - NewBBFreq;

2535 BFI->setBlockFreq(BB, BBNewFreq);

2536

2537

2538

2541 auto SuccFreq = (Succ == SuccBB)

2542 ? BB2SuccBBFreq - NewBBFreq

2544 BBSuccFreq.push_back(SuccFreq.getFrequency());

2545 }

2546

2548

2550 if (MaxBBSuccFreq == 0)

2551 BBSuccProbs.assign(BBSuccFreq.size(),

2552 {1, static_cast(BBSuccFreq.size())});

2553 else {

2554 for (uint64_t Freq : BBSuccFreq)

2557

2559 BBSuccProbs.end());

2560 }

2561

2562

2564

2565

2566

2567

2568

2569

2570

2571

2572

2573

2574

2575

2576

2577

2578

2579

2580

2581

2582

2583

2584

2585

2586

2587

2588

2589

2590

2591

2592

2593

2594

2595

2596

2597

2598

2599 if (BBSuccProbs.size() >= 2 && HasProfile) {

2601 for (auto Prob : BBSuccProbs)

2602 Weights.push_back(Prob.getNumerator());

2603

2606 }

2607}

2608

2609

2610

2611

2612

2613

2616 assert(!PredBBs.empty() && "Can't handle an empty set");

2617

2618

2619

2620

2621 if (LoopHeaders.count(BB)) {

2623 << "' into predecessor block '" << PredBBs[0]->getName()

2624 << "' - it might create an irreducible loop!\n");

2625 return false;

2626 }

2627

2630 if (DuplicationCost > BBDupThreshold) {

2632 << "' - Cost is too high: " << DuplicationCost << "\n");

2633 return false;

2634 }

2635

2636

2637 std::vectorDominatorTree::UpdateType Updates;

2639 if (PredBBs.size() == 1)

2640 PredBB = PredBBs[0];

2641 else {

2643 << " common predecessors.\n");

2644 PredBB = splitBlockPreds(BB, PredBBs, ".thr_comm");

2645 }

2647

2648

2649

2651 << "' into end of '" << PredBB->getName()

2652 << "' to eliminate branch on phi. Cost: "

2653 << DuplicationCost << " block is:" << *BB << "\n");

2654

2655

2656

2658

2659 if (!OldPredBranch || !OldPredBranch->isUnconditional()) {

2661 PredBB = SplitEdge(OldPredBB, BB);

2665 OldPredBranch = cast(PredBB->getTerminator());

2666 }

2667

2668

2669

2671

2673 for (; PHINode *PN = dyn_cast(BI); ++BI)

2675

2676

2677 for (; BI != BB->end(); ++BI) {

2679 New->insertInto(PredBB, OldPredBranch->getIterator());

2680

2681

2682 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)

2683 if (Instruction *Inst = dyn_cast(New->getOperand(i))) {

2685 if (I != ValueMapping.end())

2686 New->setOperand(i, I->second);

2687 }

2688

2689

2691

2692

2693

2694

2696 New,

2697 {BB->getDataLayout(), TLI, nullptr, nullptr, New})) {

2698 ValueMapping[&*BI] = IV;

2699 if (!New->mayHaveSideEffects()) {

2700 New->eraseFromParent();

2701 New = nullptr;

2702

2703

2705 }

2706 } else {

2707 ValueMapping[&*BI] = New;

2708 }

2709 if (New) {

2710

2711 New->setName(BI->getName());

2712

2713 New->cloneDebugInfoFrom(&*BI);

2714

2715 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)

2716 if (BasicBlock *SuccBB = dyn_cast(New->getOperand(i)))

2718 }

2719 }

2720

2721

2722

2725 ValueMapping);

2727 ValueMapping);

2728

2729 updateSSA(BB, PredBB, ValueMapping);

2730

2731

2732

2734

2735

2737 if (auto *BPI = getBPI())

2739 DTU->applyUpdatesPermissive(Updates);

2740

2741 ++NumDupes;

2742 return true;

2743}

2744

2745

2746

2747

2748

2749

2752 unsigned Idx) {

2753

2754

2755

2756

2757

2758

2759

2760

2761

2765

2768

2770 BI->applyMergedLocation(PredTerm->getDebugLoc(), SI->getDebugLoc());

2771 BI->copyMetadata(*SI, {LLVMContext::MD_prof});

2773 SIUse->addIncoming(SI->getTrueValue(), NewBB);

2774

2777

2779 (TrueWeight + FalseWeight) != 0) {

2782 TrueWeight, TrueWeight + FalseWeight));

2784 FalseWeight, TrueWeight + FalseWeight));

2785

2786 if (auto *BPI = getBPI())

2788 }

2789

2790 if (auto *BFI = getBFI()) {

2791 if ((TrueWeight + FalseWeight) == 0) {

2792 TrueWeight = 1;

2793 FalseWeight = 1;

2794 }

2796 TrueWeight, TrueWeight + FalseWeight);

2797 auto NewBBFreq = BFI->getBlockFreq(Pred) * PredToNewBBProb;

2798 BFI->setBlockFreq(NewBB, NewBBFreq);

2799 }

2800

2801

2802 SI->eraseFromParent();

2805

2806

2808 PHINode *Phi = dyn_cast(BI); ++BI)

2809 if (Phi != SIUse)

2810 Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);

2811}

2812

2814 PHINode *CondPHI = dyn_cast(SI->getCondition());

2815

2816 if (!CondPHI || CondPHI->getParent() != BB)

2817 return false;

2818

2822

2823

2824

2825

2827 continue;

2828

2831 continue;

2832

2834 return true;

2835 }

2836 return false;

2837}

2838

2839

2840

2841

2842

2843

2844

2845

2846

2847

2848

2849

2850

2855

2856 if (!CondBr || !CondBr->isConditional() || !CondLHS ||

2858 return false;

2859

2863

2864

2865

2866 if (!SI || SI->getParent() != Pred || !SI->hasOneUse())

2867 continue;

2868

2871 continue;

2872

2873

2874

2875

2878 CondRHS, Pred, BB, CondCmp);

2881 CondRHS, Pred, BB, CondCmp);

2882 if ((LHSRes || RHSRes) && LHSRes != RHSRes) {

2884 return true;

2885 }

2886 }

2887 return false;

2888}

2889

2890

2891

2892

2893

2894

2895

2896

2897

2898

2899

2900

2901

2902

2903

2904

2905

2906

2907

2908

2909

2911

2912

2914 return false;

2915

2916

2917

2918 if (LoopHeaders.count(BB))

2919 return false;

2920

2922 PHINode *PN = dyn_cast(BI); ++BI) {

2923

2925 [](Value *V) { return !isa(V); }))

2926 continue;

2927

2928 auto isUnfoldCandidate = [BB](SelectInst *SI, Value *V) {

2929 using namespace PatternMatch;

2930

2931

2932 if (SI->getParent() != BB)

2933 return false;

2934 Value *Cond = SI->getCondition();

2936 return Cond && Cond == V && Cond->getType()->isIntegerTy(1) && !IsAndOr;

2937 };

2938

2940 for (Use &U : PN->uses()) {

2941 if (ICmpInst *Cmp = dyn_cast(U.getUser())) {

2942

2943

2944 if (Cmp->getParent() == BB && Cmp->hasOneUse() &&

2945 isa(Cmp->getOperand(1 - U.getOperandNo())))

2946 if (SelectInst *SelectI = dyn_cast(Cmp->user_back()))

2947 if (isUnfoldCandidate(SelectI, Cmp->use_begin()->get())) {

2948 SI = SelectI;

2949 break;

2950 }

2951 } else if (SelectInst *SelectI = dyn_cast(U.getUser())) {

2952

2953 if (isUnfoldCandidate(SelectI, U.get())) {

2954 SI = SelectI;

2955 break;

2956 }

2957 }

2958 }

2959

2960 if (!SI)

2961 continue;

2962

2963 Value *Cond = SI->getCondition();

2969 BasicBlock *SplitBB = SI->getParent();

2970 BasicBlock *NewBB = Term->getParent();

2972 NewPN->addIncoming(SI->getTrueValue(), Term->getParent());

2973 NewPN->addIncoming(SI->getFalseValue(), BB);

2975 SI->replaceAllUsesWith(NewPN);

2976 SI->eraseFromParent();

2977

2978 std::vectorDominatorTree::UpdateType Updates;

2983

2984 for (auto *Succ : successors(SplitBB)) {

2987 }

2988 DTU->applyUpdatesPermissive(Updates);

2989 return true;

2990 }

2991 return false;

2992}

2993

2994

2995

2996

2997

2998

2999

3000

3001

3002

3003

3004

3005

3006

3007

3008

3009

3010

3011

3012

3014 using namespace PatternMatch;

3015

3016

3019 if (PI == PE)

3020 return false;

3021 Pred1 = *PI++;

3022 if (PI == PE)

3023 return false;

3024 Pred2 = *PI++;

3025 if (PI != PE)

3026 return false;

3027 if (Pred1 == Pred2)

3028 return false;

3029

3030

3031

3034 return false;

3035

3036 if (auto *BI = dyn_cast(Parent->getTerminator()))

3037 for (auto &I : *BB)

3039 return true;

3040

3041 return false;

3042}

3043

3044

3045

3046

3050 assert(BI->isConditional() && "Unconditional branch has 2 successors?");

3055

3057 bool TrueDestIsSafe = false;

3058 bool FalseDestIsSafe = false;

3059

3060

3062 if (Impl && *Impl)

3063 TrueDestIsSafe = true;

3064 else {

3065

3066 Impl = isImpliedCondition(BranchCond, GuardCond, DL, false);

3067 if (Impl && *Impl)

3068 FalseDestIsSafe = true;

3069 }

3070

3071 if (!TrueDestIsSafe && !FalseDestIsSafe)

3072 return false;

3073

3074 BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;

3075 BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;

3076

3079 unsigned Cost =

3081 if (Cost > BBDupThreshold)

3082 return false;

3083

3084

3086 BB, PredGuardedBlock, AfterGuard, GuardedMapping, *DTU);

3087 assert(GuardedBlock && "Could not create the guarded block?");

3088

3089

3090

3092 BB, PredUnguardedBlock, Guard, UnguardedMapping, *DTU);

3093 assert(UnguardedBlock && "Could not create the unguarded block?");

3094 LLVM_DEBUG(dbgs() << "Moved guard " << *Guard << " to block "

3095 << GuardedBlock->getName() << "\n");

3096

3097

3098

3100 for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)

3101 if (!isa(&*BI))

3103

3106

3108 if (!Inst->use_empty()) {

3110 NewPN->addIncoming(UnguardedMapping[Inst], UnguardedBlock);

3111 NewPN->addIncoming(GuardedMapping[Inst], GuardedBlock);

3112 NewPN->setDebugLoc(Inst->getDebugLoc());

3114 Inst->replaceAllUsesWith(NewPN);

3115 }

3116 Inst->dropDbgRecords();

3117 Inst->eraseFromParent();

3118 }

3119 return true;

3120}

3121

3122PreservedAnalyses JumpThreadingPass::getPreservedAnalysis() const {

3126

3127

3128

3129 return PA;

3130}

3131

3132template

3133typename AnalysisT::Result *JumpThreadingPass::runExternalAnalysis() {

3134 assert(FAM && "Can't run external analysis without FunctionAnalysisManager");

3135

3136

3137

3138

3139 if (!ChangedSinceLastAnalysisUpdate) {

3140 assert(!DTU->hasPendingUpdates() &&

3141 "Lost update of 'ChangedSinceLastAnalysisUpdate'?");

3142

3143 return &FAM->getResult(*F);

3144 }

3145 ChangedSinceLastAnalysisUpdate = false;

3146

3147 auto PA = getPreservedAnalysis();

3148

3149

3152

3154

3155 DTU->flush();

3156

3157 assert(DTU->getDomTree().verify(DominatorTree::VerificationLevel::Fast));

3158 assert((!DTU->hasPostDomTree() ||

3159 DTU->getPostDomTree().verify(

3161

3163

3167

3169}

3170

3172 if (!BPI) {

3173 assert(FAM && "Can't create BPI without FunctionAnalysisManager");

3175 }

3176 return *BPI;

3177}

3178

3180 if (!BFI) {

3181 assert(FAM && "Can't create BFI without FunctionAnalysisManager");

3183 }

3184 return *BFI;

3185}

3186

3187

3188

3189

3191 auto *Res = getBPI();

3192 if (Res)

3193 return Res;

3194

3195 if (Force)

3196 BPI = runExternalAnalysis();

3197

3198 return *BPI;

3199}

3200

3202 auto *Res = getBFI();

3203 if (Res)

3204 return Res;

3205

3206 if (Force)

3207 BFI = runExternalAnalysis();

3208

3209 return *BFI;

3210}

ReachingDefAnalysis InstSet & ToRemove

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static const Function * getParent(const Value *V)

BlockVerifier::State From

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

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

This file defines the DenseMap class.

This is the interface for a simple mod/ref and alias analysis over globals.

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

Module.h This file contains the declarations for the Module class.

This header defines various interfaces for pass management in LLVM.

This defines the Use class.

static unsigned getBestDestForJumpOnUndef(BasicBlock *BB)

GetBestDestForBranchOnUndef - If we determine that the specified block ends in an undefined jump,...

static cl::opt< unsigned > PhiDuplicateThreshold("jump-threading-phi-threshold", cl::desc("Max PHIs in BB to duplicate for jump threading"), cl::init(76), cl::Hidden)

static bool replaceFoldableUses(Instruction *Cond, Value *ToVal, BasicBlock *KnownAtEndOfBB)

static cl::opt< unsigned > BBDuplicateThreshold("jump-threading-threshold", cl::desc("Max block size to duplicate for jump threading"), cl::init(6), cl::Hidden)

static cl::opt< bool > ThreadAcrossLoopHeaders("jump-threading-across-loop-headers", cl::desc("Allow JumpThreading to thread across loop headers, for testing"), cl::init(false), cl::Hidden)

static unsigned getJumpThreadDuplicationCost(const TargetTransformInfo *TTI, BasicBlock *BB, Instruction *StopAt, unsigned Threshold)

Return the cost of duplicating a piece of this block from first non-phi and before StopAt instruction...

static void addPHINodeEntriesForMappedBlock(BasicBlock *PHIBB, BasicBlock *OldPred, BasicBlock *NewPred, ValueToValueMapTy &ValueMap)

addPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new predecessor to the PHIBB block.

static BasicBlock * findMostPopularDest(BasicBlock *BB, const SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * > > &PredToDestList)

findMostPopularDest - The specified list contains multiple possible threadable destinations.

static Constant * getKnownConstant(Value *Val, ConstantPreference Preference)

getKnownConstant - Helper method to determine if we can thread over a terminator with the given value...

static cl::opt< unsigned > ImplicationSearchThreshold("jump-threading-implication-search-threshold", cl::desc("The number of predecessors to search for a stronger " "condition to use to thread over a weaker condition"), cl::init(3), cl::Hidden)

static bool isOpDefinedInBlock(Value *Op, BasicBlock *BB)

Return true if Op is an instruction defined in the given block.

static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB)

static bool hasAddressTakenAndUsed(BasicBlock *BB)

See the comments on JumpThreadingPass.

static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)

This file implements a map that provides insertion order iteration.

This file provides utility analysis objects describing memory locations.

This file contains the declarations for profiling metadata utility functions.

const SmallVectorImpl< MachineOperand > & Cond

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

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.

static const uint32_t IV[8]

A manager for alias analyses.

A container for analyses that lazily runs them and caches their results.

void invalidate(IRUnitT &IR, const PreservedAnalyses &PA)

Invalidate cached analyses for an IR unit.

PassT::Result * getCachedResult(IRUnitT &IR) const

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

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

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

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

iterator_range< const_phi_iterator > phis() const

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

const_iterator getFirstInsertionPt() const

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

DbgMarker * createMarker(Instruction *I)

Attach a DbgMarker to the given instruction.

bool hasAddressTaken() const

Returns true if there are any uses of this basic block other than direct branches,...

InstListType::const_iterator const_iterator

const Instruction & front() const

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

Creates a new BasicBlock.

void moveAfter(BasicBlock *MovePos)

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

bool hasNPredecessors(unsigned N) const

Return true if this block has exactly N predecessors.

const BasicBlock * getSinglePredecessor() const

Return the predecessor of this block if it has a single predecessor block.

const Function * getParent() const

Return the enclosing method, or null if none.

const DataLayout & getDataLayout() const

Get the data layout of the module this basic block belongs to.

DbgMarker * getMarker(InstListType::iterator It)

Return the DbgMarker for the position given by It, so that DbgRecords can be inserted there.

InstListType::iterator iterator

Instruction iterators...

LLVMContext & getContext() const

Get the context in which this basic block lives.

bool isLandingPad() const

Return true if this basic block is a landing pad.

bool isEHPad() const

Return true if this basic block is an exception handling block.

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...

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

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

This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...

void disableDominatorTree()

Disable the use of the dominator tree during alias analysis queries.

The address of a basic block.

static BlockAddress * get(Function *F, BasicBlock *BB)

Return a BlockAddress for the specified function and basic block.

Analysis pass which computes BlockFrequencyInfo.

BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...

Conditional or Unconditional Branch instruction.

bool isConditional() const

unsigned getNumSuccessors() const

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

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

Value * getCondition() const

Analysis pass which computes BranchProbabilityInfo.

Analysis providing branch probability information.

void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)

Set the raw probabilities for all edges from the given block.

BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const

Get an edge's probability, relative to other out-edges of the Src.

void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst)

Copy outgoing edge probabilities from Src to Dst.

static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)

uint32_t getNumerator() const

BranchProbability getCompl() const

static void normalizeProbabilities(ProbabilityIter Begin, ProbabilityIter End)

Value * getArgOperand(unsigned i) const

This class represents a function call, abstracting a target machine's calling convention.

This is the base class for all instructions that perform data casts.

static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)

Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.

This class is the base class for the comparison instructions.

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

Predicate getPredicate() const

Return the predicate for this instruction.

An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...

static Constant * getNot(Constant *C)

This is the shared class of boolean and integer constants.

bool isOne() const

This is just a convenience method to make client code smaller for a common case.

static ConstantInt * getTrue(LLVMContext &Context)

bool isZero() const

This is just a convenience method to make client code smaller for a common code.

static ConstantInt * getFalse(LLVMContext &Context)

const APInt & getValue() const

Return the constant as an APInt value reference.

This class represents a range of values.

ConstantRange add(const ConstantRange &Other) const

Return a new range representing the possible values resulting from an addition of a value in this ran...

static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)

Produce the exact range such that all values in the returned range satisfy the given predicate with a...

ConstantRange inverse() const

Return a new range that is the logical not of the current set.

bool contains(const APInt &Val) const

Return true if the specified value is in the set.

This is an important base class in LLVM.

void removeDeadConstantUsers() const

If there are any dead constant users dangling off of this constant, remove them.

This class represents an Operation in the Expression.

A parsed version of the target data layout string in and methods for querying it.

Per-instruction record of debug-info.

iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(DbgMarker *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere, bool InsertAtHead=false)

Clone all DbgMarkers from From into this marker.

const BasicBlock * getParent() const

This represents the llvm.dbg.value instruction.

Record of a variable value-assignment, aka a non instruction representation of the dbg....

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

Analysis pass which computes a DominatorTree.

static constexpr UpdateKind Delete

static constexpr UpdateKind Insert

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

bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

This class represents a freeze function that returns random concrete value if an operand is either a ...

const BasicBlock & getEntryBlock() const

bool hasFnAttribute(Attribute::AttrKind Kind) const

Return true if the function has the attribute.

void flush()

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

Module * getParent()

Get the module that this global value is contained inside of...

This instruction compares its operands according to the predicate given to the constructor.

Indirect Branch Instruction.

void removeFromParent()

This method unlinks 'this' from the containing basic block, but does not delete it.

iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)

Clone any debug-info attached to From onto this instruction.

unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

void insertBefore(Instruction *InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified instruction.

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

void setAAMetadata(const AAMDNodes &N)

Sets the AA metadata on this instruction from the AAMDNodes structure.

bool isAtomic() const LLVM_READONLY

Return true if this instruction has an AtomicOrdering of unordered or higher.

InstListType::iterator eraseFromParent()

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

BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

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

AAMDNodes getAAMetadata() const

Returns the AA metadata for this instruction.

unsigned getOpcode() const

Returns a member of one of the enums like Instruction::Add.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

void setSuccessor(unsigned Idx, BasicBlock *BB)

Update the specified successor to point at the provided block.

const DataLayout & getDataLayout() const

Get the data layout of the module this instruction belongs to.

bool isSpecialTerminator() const

InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)

Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...

A wrapper class for inspecting calls to intrinsic functions.

bool simplifyPartiallyRedundantLoad(LoadInst *LI)

simplifyPartiallyRedundantLoad - If LoadI is an obviously partially redundant load instruction,...

bool processBranchOnXOR(BinaryOperator *BO)

processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the...

bool processGuards(BasicBlock *BB)

Try to propagate a guard from the current BB into one of its predecessors in case if another branch o...

void updateSSA(BasicBlock *BB, BasicBlock *NewBB, ValueToValueMapTy &ValueMapping)

Update the SSA form.

bool computeValueKnownInPredecessors(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)

void findLoopHeaders(Function &F)

findLoopHeaders - We do not want jump threading to turn proper loop structures into irreducible loops...

bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB)

Merge basic block BB into its sole predecessor if possible.

JumpThreadingPass(int T=-1)

void cloneInstructions(ValueToValueMapTy &ValueMapping, BasicBlock::iterator BI, BasicBlock::iterator BE, BasicBlock *NewBB, BasicBlock *PredBB)

Clone instructions in range [BI, BE) to NewBB.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

bool runImpl(Function &F, FunctionAnalysisManager *FAM, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, LazyValueInfo *LVI, AAResults *AA, std::unique_ptr< DomTreeUpdater > DTU, std::optional< BlockFrequencyInfo * > BFI, std::optional< BranchProbabilityInfo * > BPI)

Constant * evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, Value *cond, const DataLayout &DL)

bool processBranchOnPHI(PHINode *PN)

processBranchOnPHI - We have an otherwise unthreadable conditional branch on a PHI node (or freeze PH...

bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond)

Attempt to thread through two successive basic blocks.

bool computeValueKnownInPredecessorsImpl(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, SmallPtrSet< Value *, 4 > &RecursionSet, Instruction *CxtI=nullptr)

computeValueKnownInPredecessors - Given a basic block BB and a value V, see if we can infer that the ...

void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, PHINode *SIUse, unsigned Idx)

DomTreeUpdater * getDomTreeUpdater() const

bool processThreadableEdges(Value *Cond, BasicBlock *BB, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)

bool processBlock(BasicBlock *BB)

processBlock - If there are any predecessors whose control can be threaded through to a successor,...

bool processImpliedCondition(BasicBlock *BB)

bool duplicateCondBranchOnPHIIntoPred(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs)

duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch to BB which contains an i1...

void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, BasicBlock *BB, BasicBlock *SuccBB)

bool tryThreadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)

tryThreadEdge - Thread an edge if it's safe and profitable to do so.

bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB)

tryToUnfoldSelect - Look for blocks of the form bb1: a = select br bb2

bool tryToUnfoldSelectInCurrBB(BasicBlock *BB)

tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the same BB in the form bb: p = ...

void threadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)

threadEdge - We have decided that it is safe and profitable to factor the blocks in PredBBs to one pr...

bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI)

Try to propagate the guard from BB which is the lower block of a diamond to one of its branches,...

This is an important class for using LLVM in a threaded context.

Analysis to compute lazy value information.

This pass computes, caches, and vends lazy value constraint information.

void eraseBlock(BasicBlock *BB)

Inform the analysis cache that we have erased a block.

void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc)

Inform the analysis cache that we have threaded an edge from PredBB to OldSucc to be from PredBB to N...

Constant * getPredicateOnEdge(CmpInst::Predicate Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)

Determine whether the specified value comparison with a constant is known to be true or false on the ...

Constant * getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)

Determine whether the specified value is known to be a constant on the specified edge.

ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)

Return the ConstantRage constraint that is known to hold for the specified value on the specified edg...

Constant * getConstant(Value *V, Instruction *CxtI)

Determine whether the specified value is known to be a constant at the specified instruction.

void forgetValue(Value *V)

Remove information related to this value from the cache.

Constant * getPredicateAt(CmpInst::Predicate Pred, Value *V, Constant *C, Instruction *CxtI, bool UseBlockValue)

Determine whether the specified value comparison with a constant is known to be true or false at the ...

An instruction for reading from memory.

AtomicOrdering getOrdering() const

Returns the ordering constraint of this load instruction.

SyncScope::ID getSyncScopeID() const

Returns the synchronization scope ID of this load instruction.

Align getAlign() const

Return the alignment of the access that is being performed.

static LocationSize precise(uint64_t Value)

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

Representation for a specific memory location.

void addIncoming(Value *V, BasicBlock *BB)

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

void setIncomingValue(unsigned i, Value *V)

Value * getIncomingValueForBlock(const BasicBlock *BB) const

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

Value * getIncomingValue(unsigned i) const

Return incoming value number x.

unsigned getNumIncomingValues() const

Return the number of incoming edges.

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 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.

void preserve()

Mark an analysis as preserved.

Helper class for SSA formation on a set of values defined in multiple blocks.

void RewriteUse(Use &U)

Rewrite a use of the symbolic value.

void Initialize(Type *Ty, StringRef Name)

Reset this object to get ready for a new set of SSA updates with type 'Ty'.

void UpdateDebugValues(Instruction *I)

Rewrite debug value intrinsics to conform to a new SSA form.

void AddAvailableValue(BasicBlock *BB, Value *V)

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

This class represents the LLVM 'select' instruction.

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

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

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

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

SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...

std::pair< const_iterator, bool > insert(const T &V)

insert - Insert an element into the set if it isn't already there.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void assign(size_type NumElts, ValueParamT Elt)

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Analysis pass providing the TargetTransformInfo.

Analysis pass providing the TargetLibraryInfo.

Provides information about what library functions are available for the current target.

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

bool hasBranchDivergence(const Function *F=nullptr) const

Return true if branch divergence exists.

@ TCK_SizeAndLatency

The weighted sum of size and latency.

@ TCC_Free

Expected to fold away in lowering.

InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const

Estimate the cost of a given IR user when lowered.

The instances of the Type class are immutable: once they are created, they are never changed.

bool isVectorTy() const

True if this is an instance of VectorType.

bool isIntegerTy() const

True if this is an instance of IntegerType.

'undef' values are things that do not have specified contents.

static UndefValue * get(Type *T)

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

A Use represents the edge between a Value definition and its users.

void setOperand(unsigned i, Value *Val)

Value * getOperand(unsigned i) const

iterator find(const KeyT &Val)

LLVM Value Representation.

Type * getType() const

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

const Value * DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) const

Translate PHI node to its predecessor from the given basic block.

bool hasOneUse() const

Return true if there is exactly one use of this value.

void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

const Value * stripPointerCasts() const

Strip off pointer casts, all-zero GEPs and address space casts.

StringRef getName() const

Return a constant reference to the value's name.

void takeName(Value *V)

Transfer the name from V to this value.

const ParentTy * getParent() const

self_iterator getIterator()

NodeTy * getNextNode()

Get the next node, or nullptr for the list tail.

@ C

The default llvm calling convention, compatible with C.

Function * getDeclarationIfExists(Module *M, ID id, ArrayRef< Type * > Tys, FunctionType *FT=nullptr)

This version supports overloaded intrinsics.

BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)

class_match< Constant > m_Constant()

Match an arbitrary Constant and ignore it.

bool match(Val *V, const Pattern &P)

class_match< ConstantInt > m_ConstantInt()

Match an arbitrary ConstantInt and ignore it.

auto m_LogicalOr()

Matches L || R where L and R are arbitrary values.

class_match< CmpInst > m_Cmp()

Matches any compare instruction and ignore it.

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

auto m_LogicalAnd()

Matches L && R where L and R are arbitrary values.

match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)

Combine two pattern matchers matching L || R.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

bool RemoveRedundantDbgInstrs(BasicBlock *BB)

Try to remove redundant dbg.value instructions from given basic block.

bool all_of(R &&range, UnaryPredicate P)

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

bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)

If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...

auto pred_end(const MachineBasicBlock *BB)

unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)

auto successors(const MachineBasicBlock *BB)

MDNode * getBranchWeightMDNode(const Instruction &I)

Get the branch weights metadata node.

Value * findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan, BatchAAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst)

Scan backwards to see if we have the value of the given pointer available locally within a small numb...

void remapDebugVariable(ValueToValueMapTy &Mapping, Instruction *Inst)

Remap the operands of the debug records attached to Inst, and the operands of Inst itself if it's a d...

Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)

Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.

auto pred_size(const MachineBasicBlock *BB)

bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)

Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...

void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)

Delete the specified block, which must have no predecessors.

Value * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, BatchAAResults *AA=nullptr, bool *IsLoadCSE=nullptr, unsigned *NumScanedInst=nullptr)

Scan backwards to see if we have the value of the given load available locally within a small number ...

bool hasBranchWeightOrigin(const Instruction &I)

Check if Branch Weight Metadata has an "expected" field from an llvm.expect* intrinsic.

BasicBlock * DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt, ValueToValueMapTy &ValueMapping, DomTreeUpdater &DTU)

Split edge between BB and PredBB and duplicate all non-Phi instructions from BB between its beginning...

void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)

Finds the llvm.dbg.value intrinsics describing a value.

Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)

See if we can compute a simplified version of this instruction.

bool any_of(R &&range, UnaryPredicate P)

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

bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)

Return true if the result produced by the instruction is not used, and the instruction will return.

bool isGuard(const User *U)

Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....

bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)

BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...

auto reverse(ContainerTy &&C)

void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected)

Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...

bool hasValidBranchWeightMD(const Instruction &I)

Checks if an instructions has valid Branch Weight Metadata.

raw_ostream & dbgs()

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

bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true)

Return true if the instruction does not have any effects besides calculating the result and does not ...

Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)

Attempt to constant fold a cast with the specified operand.

void cloneNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, DenseMap< MDNode *, MDNode * > &ClonedScopes, StringRef Ext, LLVMContext &Context)

Duplicate the specified list of noalias decl scopes.

cl::opt< unsigned > DefMaxInstsToScan

The default number of maximum instructions to scan in the block, used by FindAvailableLoadedValue().

void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)

This method transforms the landing pad, OrigBB, by introducing two new basic blocks into the function...

Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)

Attempt to constant fold a binary operation with the specified operands.

void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)

Combine the metadata of two instructions so that K can replace J.

BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)

This method introduces at least one new basic block into the function and moves some of the predecess...

void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)

BB is a block with one predecessor and its predecessor is known to have one successor (BB!...

auto lower_bound(R &&Range, T &&Value)

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

void adaptNoAliasScopes(llvm::Instruction *I, const DenseMap< MDNode *, MDNode * > &ClonedScopes, LLVMContext &Context)

Adapt the metadata for the specified instruction according to the provided mapping.

auto max_element(R &&Range)

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

Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)

ConstantFoldInstruction - Try to constant fold the specified instruction.

bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)

Return true if this function can prove that V does not have undef bits and is never poison.

bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)

Return true if this function can prove that the instruction I will always transfer execution to one o...

bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)

Extract branch weights from MD_prof metadata.

auto pred_begin(const MachineBasicBlock *BB)

void erase_if(Container &C, UnaryPredicate P)

Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...

auto predecessors(const MachineBasicBlock *BB)

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

Returns true if Element is found in Range.

bool pred_empty(const BasicBlock *BB)

Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)

Split the containing block at the specified instruction - everything before SplitBefore stays in the ...

Value * simplifyCmpInst(CmpPredicate Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)

Given operands for a CmpInst, fold the result or return null.

void array_pod_sort(IteratorTy Start, IteratorTy End)

array_pod_sort - This sorts an array with the specified start and end extent.

void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)

Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...

BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")

Split the edge connecting the specified blocks, and return the newly created basic block between From...

static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)

Filter the DbgRecord range to DbgVariableRecord types only and downcast.

void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock * > > &Result)

Analyze the specified function to find all of the loop backedges in the function and return them.

std::optional< bool > isImpliedCondition(const Value *LHS, const Value *RHS, const DataLayout &DL, bool LHSIsTrue=true, unsigned Depth=0)

Return true if RHS is known to be implied true by LHS.

A collection of metadata nodes that might be associated with a memory access used by the alias-analys...

Function object to check whether the second component of a container supported by std::get (like std:...