JumpThreading.cpp Source File (original) (raw)

72#include

73#include

74#include

75#include

76#include

78using namespace llvm;

81#define DEBUG_TYPE "jump-threading"

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

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

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

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

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

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

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

100 "jump-threading-phi-threshold",

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

103

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

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

108

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

147

150 if (!CondBr)

151 return;

152

153 uint64_t TrueWeight, FalseWeight;

155 return;

156

157 if (TrueWeight + FalseWeight == 0)

158

159

160

161 return;

162

163

164

165 auto GetPredOutEdge =

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

168 auto *PredBB = IncomingBB;

169 auto *SuccBB = PhiBB;

171 while (true) {

174 return {PredBB, SuccBB};

175 Visited.insert(PredBB);

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

177 if (!SinglePredBB)

178 return {nullptr, nullptr};

179

180

181

182 if (Visited.count(SinglePredBB))

183 return {nullptr, nullptr};

184

185 SuccBB = PredBB;

186 PredBB = SinglePredBB;

187 }

188 };

189

193

195 continue;

196

199 TrueWeight, TrueWeight + FalseWeight)

201 FalseWeight, TrueWeight + FalseWeight));

202

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

204 if (!PredOutEdge.first)

205 return;

206

207 BasicBlock *PredBB = PredOutEdge.first;

209 if (!PredBr)

210 return;

211

212 uint64_t PredTrueWeight, PredFalseWeight;

213

214

215

216

218 continue;

219

220

221

223 continue;

224

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

229 } else {

232 }

234 }

235}

236

240

241 if (TTI.hasBranchDivergence(&F))

247

249 runImpl(F, &AM, &TLI, &TTI, &LVI, &AA,

250 std::make_unique(

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

252 nullptr, nullptr);

253

256

257

259

260#if defined(EXPENSIVE_CHECKS)

262 DominatorTree::VerificationLevel::Full) &&

263 "DT broken after JumpThreading");

266 PostDominatorTree::VerificationLevel::Full)) &&

267 "PDT broken after JumpThreading");

268#else

270 DominatorTree::VerificationLevel::Fast) &&

271 "DT broken after JumpThreading");

274 PostDominatorTree::VerificationLevel::Fast)) &&

275 "PDT broken after JumpThreading");

276#endif

277

278 return getPreservedAnalysis();

279}

280

285 std::unique_ptr DTU_,

289 F = &F_;

290 FAM = FAM_;

291 TLI = TLI_;

292 TTI = TTI_;

293 LVI = LVI_;

294 AA = AA_;

295 DTU = std::move(DTU_);

296 BFI = BFI_;

297 BPI = BPI_;

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

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

301

302

303

306 else if (F->hasMinSize())

307 BBDupThreshold = 3;

308 else

309 BBDupThreshold = DefaultBBDupThreshold;

310

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

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

314

315 Unreachable.clear();

316 for (auto &BB : *F)

318 Unreachable.insert(&BB);

319

322

323 bool EverChanged = false;

325 do {

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);

346 LVI->eraseBlock(&BB);

348 Changed = ChangedSinceLastAnalysisUpdate = true;

349 continue;

350 }

351

352

353

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

366 LVI->eraseBlock(&BB);

367 Changed = ChangedSinceLastAnalysisUpdate = true;

368 }

369 }

370 }

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

396

397

398

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

402

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

405

406

407

409 break;

410

411

413 break;

415 }

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

417 Cond->eraseFromParent();

419 }

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;

439 FirstNonPHI = &I;

440 break;

441 }

443 return ~0U;

444 }

445

446

448

449

450

451

452 unsigned Bonus = 0;

454

455

456

458 Bonus = 6;

459

460

462 Bonus = 8;

463 }

464

465

466

467 Threshold += Bonus;

468

469

470

471 unsigned Size = 0;

473

474

475 if (Size > Threshold)

477

478

479

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

481 return ~0U;

482

483

484

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

487 return ~0U;

488

491 continue;

492

493

495

496

497

498

499

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

530

531

532

533

534

535

537 if (!Val)

538 return nullptr;

539

540

542 return U;

543

546

548}

549

550

551

552

553

554

555

561

562

563

564

565

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

567 return false;

568

569

572 Result.emplace_back(KC, Pred);

573

574 return !Result.empty();

575 }

576

577

578

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

581

582

583

586

587

588 Constant *PredCst = LVI->getConstantOnEdge(V, P, BB, CxtI);

589

590

591

592

597 PredCst = LVI->getPredicateOnEdge(Pred, Val, Cst, P, BB, CxtI);

599 Result.emplace_back(KC, P);

600 }

601

602 return !Result.empty();

603 }

604

605

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

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

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

611 } else {

612 Constant *CI = LVI->getConstantOnEdge(InVal,

613 PN->getIncomingBlock(i),

614 BB, CxtI);

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

617 }

618 }

619

620 return !Result.empty();

621 }

622

623

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

628 RecursionSet, CxtI);

629 if (Vals.empty())

630 return false;

631

632

633 for (auto &Val : Vals)

635 CI->getType(), DL))

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

637

638 return !Result.empty();

639 }

640

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

644 RecursionSet, CxtI);

645

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

648 });

649

650 return !Result.empty();

651 }

652

653

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

657 return false;

658

659

660 Value *Op0, *Op1;

664

666 RecursionSet, CxtI);

668 RecursionSet, CxtI);

669

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

671 return false;

672

676 else

678

680

681

682

683 for (const auto &LHSVal : LHSVals)

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

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

686 LHSKnownBBs.insert(LHSVal.second);

687 }

688 for (const auto &RHSVal : RHSVals)

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

690

691

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

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

694 }

695

696 return !Result.empty();

697 }

698

699

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

705 if (Result.empty())

706 return false;

707

708

709 for (auto &R : Result)

711

712 return true;

713 }

714

715

718 return false;

723

724

725 for (const auto &LHSVal : LHSVals) {

729

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

732 }

733 }

734

735 return !Result.empty();

736 }

737

738

741 return false;

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

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

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

746

748 if (!PN)

750

751

752

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

755

756

759 Value *LHS, *RHS;

760 if (PN == CmpLHS) {

763 } else {

766 }

768 if (!Res) {

770 continue;

771

772

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

775 continue;

776

777 Res = LVI->getPredicateOnEdge(Pred, LHS, cast(RHS), PredBB,

778 BB, CxtI ? CxtI : Cmp);

779 }

780

782 Result.emplace_back(KC, PredBB);

783 }

784

785 return !Result.empty();

786 }

787

788

789

792

796

797

798 Constant *Res = LVI->getPredicateOnEdge(Pred, CmpLHS, CmpConst, P, BB,

799 CxtI ? CxtI : Cmp);

801 Result.emplace_back(KC, P);

802 }

803

804 return !Result.empty();

805 }

806

807

808

809

810 {

812

820

821

822

825

827

828

831

837 else

838 continue;

839

840 Result.emplace_back(ResC, P);

841 }

842

843 return !Result.empty();

844 }

845 }

846 }

847

848

849

853

854 for (const auto &LHSVal : LHSVals) {

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

860 }

861

862 return !Result.empty();

863 }

864 }

865

867

868

872 if ((TrueVal || FalseVal) &&

875 for (auto &C : Conds) {

877

878

879 bool KnownCond;

881

882 KnownCond = CI->isOne();

883 } else {

885

886

887

888 KnownCond = (TrueVal != nullptr);

889 }

890

891

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

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

894 }

895

896 return !Result.empty();

897 }

898 }

899

900

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

902 Constant *CI = LVI->getConstant(V, CxtI);

905 Result.emplace_back(KC, Pred);

906 }

907

908 return !Result.empty();

909}

910

911

912

913

914

915

918 unsigned MinSucc = 0;

920

921 unsigned MinNumPreds = pred_size(TestBB);

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

924 unsigned NumPreds = pred_size(TestBB);

925 if (NumPreds < MinNumPreds) {

926 MinSucc = i;

927 MinNumPreds = NumPreds;

928 }

929 }

930

931 return MinSucc;

932}

933

943

944

945

947

948

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

951 return false;

952

953

954

955

956

958 return true;

959

961 return true;

962

963

965 return true;

966

967

969

970

971

972 Value *Condition;

975

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

977 Condition = BI->getCondition();

979 Condition = SI->getCondition();

981

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

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

985 } else {

986 return false;

987 }

988

989

990 bool ConstantFolded = false;

991

992

993

995 Value *SimpleVal =

997 if (SimpleVal) {

998 I->replaceAllUsesWith(SimpleVal);

1000 I->eraseFromParent();

1001 Condition = SimpleVal;

1002 ConstantFolded = true;

1003 }

1004 }

1005

1006

1007

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

1012 std::vectorDominatorTree::UpdateType Updates;

1013

1014

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

1018 if (i == BestSucc) continue;

1022 }

1023

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

1028 ++NumFolds;

1030 DTU->applyUpdatesPermissive(Updates);

1031 if (FI)

1032 FI->eraseFromParent();

1033 return true;

1034 }

1035

1036

1037

1038

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

1042 << '\n');

1043 ++NumFolds;

1045 if (auto *BPI = getBPI())

1046 BPI->eraseBlock(BB);

1047 return true;

1048 }

1049

1051

1052

1053 if (!CondInst) {

1054

1056 return true;

1057 return ConstantFolded;

1058 }

1059

1060

1061 Value *CondWithoutFreeze = CondInst;

1063 CondWithoutFreeze = FI->getOperand(0);

1064

1066

1067

1068

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

1073 false);

1074 if (Res) {

1075

1076

1077

1078

1079

1080

1081

1083 return true;

1084 }

1085

1086

1087

1089 return true;

1090 }

1091 }

1092

1095 return true;

1096

1097

1098

1099

1100

1101 Value *SimplifyValue = CondWithoutFreeze;

1102

1105 SimplifyValue = CondCmp->getOperand(0);

1106

1107

1108

1111 return true;

1112

1113

1117

1118

1119

1120

1122 return true;

1123

1124

1125

1129

1130

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

1134

1135

1136

1138 return true;

1139

1140 return false;

1141}

1142

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

1146 return false;

1147

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

1149

1150

1151

1152

1153

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

1156 Cond = FICond->getOperand(0);

1157 else

1158 FICond = nullptr;

1159

1162 unsigned Iter = 0;

1163

1165

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

1169 return false;

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

1171 return false;

1172

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

1174 std::optional Implication =

1176

1177

1178

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

1181 FICond->getOperand(0))

1182 Implication = CondIsTrue;

1183 }

1184

1185 if (Implication) {

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

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

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

1191 ++NumFolds;

1192 BI->eraseFromParent();

1193 if (FICond)

1194 FICond->eraseFromParent();

1195

1197 if (auto *BPI = getBPI())

1198 BPI->eraseBlock(BB);

1199 return true;

1200 }

1201 CurrentBB = CurrentPred;

1203 }

1204

1205 return false;

1206}

1207

1208

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

1212 return true;

1213 return false;

1214}

1215

1216

1217

1218

1219

1221

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

1223

1224

1225

1228 return false;

1229

1230

1231

1232

1234 return false;

1235

1237

1238

1239

1241 return false;

1242

1243

1244

1246 bool IsLoadCSE;

1248

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

1252

1253

1254

1255 if (IsLoadCSE) {

1258 LVI->forgetValue(NLoadI);

1259 };

1260

1261

1262

1263 if (AvailableVal == LoadI)

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

1269 }

1272 return true;

1273 }

1274

1275

1276

1277

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

1279 return false;

1280

1281

1282

1284

1286

1288

1289 AvailablePredsTy AvailablePreds;

1290 BasicBlock *OneUnavailablePred = nullptr;

1292

1293

1294

1296

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

1298 continue;

1299

1300 BBIt = PredBB->end();

1301 unsigned NumScanedInst = 0;

1302 Value *PredAvailable = nullptr;

1303

1304

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

1307

1308

1313 AATags);

1316 &BatchAA, &IsLoadCSE, &NumScanedInst);

1317

1318

1319

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

1324 if (SinglePredBB) {

1325 BBIt = SinglePredBB->end();

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

1329 &NumScanedInst);

1330 }

1331 }

1332

1333 if (!PredAvailable) {

1334 OneUnavailablePred = PredBB;

1335 continue;

1336 }

1337

1338 if (IsLoadCSE)

1340

1341

1342

1343 AvailablePreds.emplace_back(PredBB, PredAvailable);

1344 }

1345

1346

1347

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

1349

1350

1351

1352

1353

1354

1355 BasicBlock *UnavailablePred = nullptr;

1356

1357

1358

1359

1360

1361

1362

1363

1364

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

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

1369 return false;

1370

1371

1372

1373

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

1376 UnavailablePred = OneUnavailablePred;

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

1378

1379

1383

1384

1386

1388 return false;

1389

1390 if (!AvailablePredSet.count(P))

1392 }

1393

1394

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

1396 }

1397

1398

1399

1400

1401 if (UnavailablePred) {

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

1410 if (AATags)

1412

1413 AvailablePreds.emplace_back(UnavailablePred, NewVal);

1414 }

1415

1416

1417

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

1419

1420

1425

1426

1427

1429 AvailablePredsTy::iterator I =

1431

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

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

1434

1435

1436

1437

1438

1439 Value *&PredV = I->second;

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

1443

1444

1445

1446

1447 DebugLoc DL = P->getTerminator()->getNumSuccessors() == 1

1451 }

1452

1454 }

1455

1456 for (LoadInst *PredLoadI : CSELoads) {

1458 LVI->forgetValue(PredLoadI);

1459 }

1460

1463

1464 return true;

1465}

1466

1467

1468

1469

1474 assert(!PredToDestList.empty());

1475

1476

1477

1478

1479

1481

1482

1483

1484

1485

1486 DestPopularity[nullptr] = 0;

1488 DestPopularity[SuccBB] = 0;

1489

1490 for (const auto &PredToDest : PredToDestList)

1491 if (PredToDest.second)

1492 DestPopularity[PredToDest.second]++;

1493

1494

1496

1497

1498 return MostPopular->first;

1499}

1500

1501

1502

1510

1514 if (!Visited.insert(V).second)

1515 return nullptr;

1517

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

1520

1522 return Cst;

1523 }

1524

1525

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

1528 return LVI->getConstantOnEdge(V, PredPredBB, PredBB, nullptr);

1529 }

1530

1531

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

1535 return nullptr;

1536 }

1537

1538

1539

1540

1541

1542

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

1546 BB, PredPredBB, CondCmp->getOperand(0), DL, Visited);

1548 BB, PredPredBB, CondCmp->getOperand(1), DL, Visited);

1549 if (Op0 && Op1) {

1551 Op1, DL);

1552 }

1553 }

1554 return nullptr;

1555 }

1556

1557 return nullptr;

1558}

1559

1563

1564

1565 if (LoopHeaders.count(BB))

1566 return false;

1567

1570 CxtI)) {

1571

1572

1574 }

1575

1577 "computeValueKnownInPredecessors returned true with no values");

1578

1580 for (const auto &PredValue : PredValues) {

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

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

1584 });

1585

1586

1587

1588

1589

1592

1595 Constant *OnlyVal = nullptr;

1597

1598 for (const auto &PredValue : PredValues) {

1599 BasicBlock *Pred = PredValue.second;

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

1601 continue;

1602

1603 Constant *Val = PredValue.first;

1604

1607 DestBB = nullptr;

1614 } else {

1616 && "Unexpected terminator");

1619 }

1620

1621

1622 if (PredToDestList.empty()) {

1623 OnlyDest = DestBB;

1624 OnlyVal = Val;

1625 } else {

1626 if (OnlyDest != DestBB)

1627 OnlyDest = MultipleDestSentinel;

1628

1629

1630 if (Val != OnlyVal)

1631 OnlyVal = MultipleVal;

1632 }

1633

1634

1635

1637 continue;

1638

1640 }

1641

1642

1643 if (PredToDestList.empty())

1644 return false;

1645

1646

1647

1648

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

1651 bool SeenFirstBranchToOnlyDest = false;

1652 std::vector DominatorTree::UpdateType Updates;

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

1656 SeenFirstBranchToOnlyDest = true;

1657 } else {

1658 SuccBB->removePredecessor(BB, true);

1660 }

1661 }

1662

1663

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

1667 ++NumFolds;

1668 Term->eraseFromParent();

1669 DTU->applyUpdatesPermissive(Updates);

1670 if (auto *BPI = getBPI())

1671 BPI->eraseBlock(BB);

1672

1673

1674

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

1677 CondInst->eraseFromParent();

1678

1679

1680

1681

1682

1683

1684

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

1687 }

1688 return true;

1689 }

1690 }

1691

1692

1693

1694

1695

1696 BasicBlock *MostPopularDest = OnlyDest;

1697

1698 if (MostPopularDest == MultipleDestSentinel) {

1699

1700

1701

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

1704 return LoopHeaders.contains(PredToDest.second);

1705 });

1706

1707 if (PredToDestList.empty())

1708 return false;

1709

1711 }

1712

1713

1714

1716 for (const auto &PredToDest : PredToDestList)

1717 if (PredToDest.second == MostPopularDest) {

1718 BasicBlock *Pred = PredToDest.first;

1719

1720

1721

1722

1724 if (Succ == BB)

1726 }

1727

1728

1729

1730 if (!MostPopularDest)

1733

1734

1735 return tryThreadEdge(BB, PredsToFactor, MostPopularDest);

1736}

1737

1738

1739

1740

1743

1744

1745

1748

1749

1750

1751

1752

1753

1754

1755

1759 if (PredBr->isUnconditional()) {

1760 PredBBs[0] = PredBB;

1761

1763 return true;

1764 }

1765 }

1766

1767 return false;

1768}

1769

1770

1771

1772

1775

1776

1777

1780 return false;

1781

1782

1783

1785 return false;

1786

1787

1789 return false;

1790

1791

1792

1793

1794

1795

1796

1797

1798

1799

1800

1801

1802

1803

1804

1805

1806

1807

1808

1810 bool isLHS = true;

1816 return false;

1817 isLHS = false;

1818 }

1819

1821 "computeValueKnownInPredecessors returned true with no values");

1822

1823

1824

1825 unsigned NumTrue = 0, NumFalse = 0;

1826 for (const auto &XorOpValue : XorOpValues) {

1828

1829 continue;

1831 ++NumFalse;

1832 else

1833 ++NumTrue;

1834 }

1835

1836

1838 if (NumTrue > NumFalse)

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

1842

1843

1844

1846 for (const auto &XorOpValue : XorOpValues) {

1847 if (XorOpValue.first != SplitVal && isa<UndefValue> (XorOpValue.first))

1848 continue;

1849

1850 BlocksToFoldInto.push_back(XorOpValue.second);

1851 }

1852

1853

1854

1855 if (BlocksToFoldInto.size() ==

1857 if (!SplitVal) {

1858

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

1862

1865 } else {

1866

1868 }

1869

1870 return true;

1871 }

1872

1873

1874

1877 }))

1878 return false;

1879

1880

1882}

1883

1884

1885

1886

1892

1893

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

1895

1896

1900 IV = I->second;

1901 }

1902

1903 PN.addIncoming(IV, NewPred);

1904 }

1905}

1906

1907

1910 if (!SinglePred)

1911 return false;

1912

1916 return false;

1917

1918

1919

1920 if (Unreachable.count(SinglePred))

1921 return false;

1922

1923

1924

1925

1928 return false;

1929

1930

1931 if (LoopHeaders.erase(SinglePred))

1932 LoopHeaders.insert(BB);

1933

1934 LVI->eraseBlock(SinglePred);

1936

1937

1938

1939

1940

1941

1942

1943

1944

1945

1946

1947

1948

1949

1950

1951

1952

1953

1954

1955

1956

1957

1958

1959

1960

1961

1962

1963

1965 LVI->eraseBlock(BB);

1966 return true;

1967}

1968

1969

1970

1973

1974

1975

1976

1980

1982

1983

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

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

1988 continue;

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

1990 continue;

1991

1993 }

1994

1995

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

1999 });

2000

2001

2002 if (UsesToRename.empty() && DbgVariableRecords.empty())

2003 continue;

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

2005

2006

2007

2008

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

2012

2013 while (!UsesToRename.empty())

2015 if (!DbgVariableRecords.empty()) {

2017 DbgVariableRecords.clear();

2018 }

2019

2021 }

2022}

2023

2027 return;

2028 for (auto It = Begin; It != End; ++It)

2030}

2031

2032

2033

2034

2035

2041

2042

2043

2044

2045

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

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

2050 if (!OpInst)

2051 continue;

2052

2053 auto I = ValueMapping.find(OpInst);

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

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

2056 }

2057

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

2059 DVR->replaceVariableLocationOp(OldOp, MappedOp);

2060 };

2061

2063

2064

2065

2066

2070 ValueMapping[PN] = NewPN;

2073 }

2074

2075

2076

2077

2083

2087 RetargetDbgVariableRecordIfPossible(&DVR);

2088 };

2089

2090

2091

2092

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

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

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

2097 ValueMapping[&*BI] = New;

2099

2100 CloneAndRemapDbgInfo(New, &*BI);

2101 if (const DebugLoc &DL = New->getDebugLoc())

2103

2104

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

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

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

2110 }

2111 }

2112

2113

2114

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

2116

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

2121 RetargetDbgVariableRecordIfPossible(&DVR);

2122 }

2123}

2124

2125

2128

2129

2130

2131

2132

2133

2134

2135

2136

2137

2138

2139

2140

2141

2142

2143

2144

2146 if (!CondBr)

2147 return false;

2148

2149

2151 if (!PredBB)

2152 return false;

2153

2154

2155

2156

2159 return false;

2160

2161

2162

2164 return false;

2165

2166

2167

2168

2169

2170

2171

2172

2173

2174

2176 return false;

2177

2178

2179 if (LoopHeaders.count(PredBB))

2180 return false;

2181

2182

2184 return false;

2185

2186

2187

2188

2189 unsigned ZeroCount = 0;

2190 unsigned OneCount = 0;

2195

2197 continue;

2200 if (CI->isZero()) {

2201 ZeroCount++;

2202 ZeroPred = P;

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

2204 OneCount++;

2205 OnePred = P;

2206 }

2207 }

2208 }

2209

2210

2212 if (ZeroCount == 1) {

2213 PredPredBB = ZeroPred;

2214 } else if (OneCount == 1) {

2215 PredPredBB = OnePred;

2216 } else {

2217 return false;

2218 }

2219

2221

2222

2223 if (SuccBB == BB) {

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

2226 return false;

2227 }

2228

2229

2230

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

2233 bool BBIsHeader = LoopHeaders.count(BB);

2234 bool SuccIsHeader = LoopHeaders.count(SuccBB);

2235 dbgs() << " Not threading across "

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

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

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

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

2241 });

2242 return false;

2243 }

2244

2245

2249 TTI, PredBB, PredBB->getTerminator(), BBDupThreshold);

2250

2251

2252

2253

2254 if (BBCost > BBDupThreshold || PredBBCost > BBDupThreshold ||

2255 BBCost + PredBBCost > BBDupThreshold) {

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

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

2259 return false;

2260 }

2261

2262

2264 return true;

2265}

2266

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

2273

2274

2275 bool HasProfile = doesBlockHaveProfileData(BB);

2276 auto *BFI = getOrCreateBFI(HasProfile);

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

2278

2281

2286

2287

2288 if (BFI) {

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

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

2291 BPI->getEdgeProbability(PredPredBB, PredBB);

2292 BFI->setBlockFreq(NewBB, NewBBFreq);

2293 }

2294

2295

2296

2297

2300 PredPredBB);

2301

2302

2303 if (BPI)

2304 BPI->copyEdgeProbabilities(PredBB, NewBB);

2305

2306

2307

2308

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

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

2314 }

2315

2317 ValueMapping);

2319 ValueMapping);

2320

2321 DTU->applyUpdatesPermissive(

2326

2327

2329

2330 updateSSA(PredBB, NewBB, ValueMapping);

2331

2332

2333

2336

2339 threadEdge(BB, PredsToFactor, SuccBB);

2340}

2341

2342

2346

2347 if (SuccBB == BB) {

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

2350 return false;

2351 }

2352

2353

2354

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

2357 bool BBIsHeader = LoopHeaders.count(BB);

2358 bool SuccIsHeader = LoopHeaders.count(SuccBB);

2359 dbgs() << " Not threading across "

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

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

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

2363 });

2364 return false;

2365 }

2366

2369 if (JumpThreadCost > BBDupThreshold) {

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

2372 return false;

2373 }

2374

2376 return true;

2377}

2378

2379

2380

2381

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

2386

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

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

2389

2390

2391 bool HasProfile = doesBlockHaveProfileData(BB);

2392 auto *BFI = getOrCreateBFI(HasProfile);

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

2394

2395

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

2398 PredBB = PredBBs[0];

2399 else {

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

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

2403 }

2404

2405

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

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

2409

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

2411

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

2416

2417

2418 if (BFI) {

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

2420 auto NewBBFreq =

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

2422 BFI->setBlockFreq(NewBB, NewBBFreq);

2423 }

2424

2425

2428 PredBB);

2429

2430

2431

2434

2435

2436

2438

2439

2440

2441

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

2447 }

2448

2449

2453

2455 updateSSA(BB, NewBB, ValueMapping);

2456

2457

2458

2459

2461

2462

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

2464

2465

2466 ++NumThreads;

2467}

2468

2469

2470

2471

2474 const char *Suffix) {

2476

2477

2478

2480 auto *BFI = getBFI();

2481 if (BFI) {

2482 auto *BPI = getOrCreateBPI(true);

2483 for (auto *Pred : Preds)

2484 FreqMap.insert(std::make_pair(

2486 }

2487

2488

2489

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

2493 } else {

2495 }

2496

2497 std::vectorDominatorTree::UpdateType Updates;

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

2499 for (auto *NewBB : NewBBs) {

2500 BlockFrequency NewBBFreq(0);

2505 if (BFI)

2506 NewBBFreq += FreqMap.lookup(Pred);

2507 }

2508 if (BFI)

2509 BFI->setBlockFreq(NewBB, NewBBFreq);

2510 }

2511

2512 DTU->applyUpdatesPermissive(Updates);

2513 return NewBBs[0];

2514}

2515

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

2519 return false;

2520

2522}

2523

2524

2525

2526

2527void JumpThreadingPass::updateBlockFreqAndEdgeWeight(BasicBlock *PredBB,

2533 bool HasProfile) {

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

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

2536

2537 if (!BFI) {

2538 assert(!HasProfile &&

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

2540 return;

2541 }

2542

2543

2544

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

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

2547 auto BBNewFreq = BBOrigFreq - NewBBFreq;

2548 BFI->setBlockFreq(BB, BBNewFreq);

2549

2550

2551

2552 SmallVector<uint64_t, 4> BBSuccFreq;

2554 auto BB2SuccBBFreq =

2555 BBOrigFreq * BPI->getEdgeProbability(BB, I.getSuccessorIndex());

2556 auto SuccFreq = (*I == SuccBB) ? BB2SuccBBFreq - NewBBFreq : BB2SuccBBFreq;

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

2558 }

2559

2561

2563 if (MaxBBSuccFreq == 0)

2564 BBSuccProbs.assign(BBSuccFreq.size(),

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

2566 else {

2567 for (uint64_t Freq : BBSuccFreq)

2570

2572 BBSuccProbs.end());

2573 }

2574

2575

2576 BPI->setEdgeProbability(BB, BBSuccProbs);

2577

2578

2579

2580

2581

2582

2583

2584

2585

2586

2587

2588

2589

2590

2591

2592

2593

2594

2595

2596

2597

2598

2599

2600

2601

2602

2603

2604

2605

2606

2607

2608

2609

2610

2611

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

2613 SmallVector<uint32_t, 4> Weights;

2614 for (auto Prob : BBSuccProbs)

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

2616

2619 }

2620}

2621

2622

2623

2624

2625

2626

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

2630

2631

2632

2633

2634 if (LoopHeaders.count(BB)) {

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

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

2638 return false;

2639 }

2640

2643 if (DuplicationCost > BBDupThreshold) {

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

2646 return false;

2647 }

2648

2649

2650 std::vectorDominatorTree::UpdateType Updates;

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

2653 PredBB = PredBBs[0];

2654 else {

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

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

2658 }

2660

2661

2662

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

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

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

2667

2668

2669

2671

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

2674 PredBB = SplitEdge(OldPredBB, BB);

2679 }

2680

2681

2682

2684

2685

2686 auto RItBeforeInsertPt = std::next(OldPredBranch->getReverseIterator());

2687

2691

2692

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

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

2696

2697

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

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

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

2703 }

2704

2705

2707 if (const DebugLoc &DL = New->getDebugLoc())

2709

2710

2711

2712

2714 New,

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

2716 ValueMapping[&*BI] = IV;

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

2718 New->eraseFromParent();

2719 New = nullptr;

2720

2721

2723 }

2724 } else {

2725 ValueMapping[&*BI] = New;

2726 }

2727 if (New) {

2728

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

2730

2731 New->cloneDebugInfoFrom(&*BI);

2732

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

2736 }

2737 }

2738

2739

2740

2743 ValueMapping);

2745 ValueMapping);

2746

2747

2748 remapSourceAtoms(ValueMapping, std::prev(RItBeforeInsertPt)->getIterator(),

2750

2751 updateSSA(BB, PredBB, ValueMapping);

2752

2753

2754

2756

2757

2759 if (auto *BPI = getBPI())

2760 BPI->copyEdgeProbabilities(BB, PredBB);

2761 DTU->applyUpdatesPermissive(Updates);

2762

2763 ++NumDupes;

2764 return true;

2765}

2766

2767

2768

2769

2770

2771

2774 unsigned Idx) {

2775

2776

2777

2778

2779

2780

2781

2782

2783

2787

2790

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

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

2796

2799

2801 (TrueWeight + FalseWeight) != 0) {

2804 TrueWeight, TrueWeight + FalseWeight));

2806 FalseWeight, TrueWeight + FalseWeight));

2807

2808 if (auto *BPI = getBPI())

2809 BPI->setEdgeProbability(Pred, BP);

2810 }

2811

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

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

2814 TrueWeight = 1;

2815 FalseWeight = 1;

2816 }

2818 TrueWeight, TrueWeight + FalseWeight);

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

2820 BFI->setBlockFreq(NewBB, NewBBFreq);

2821 }

2822

2823

2824 SI->eraseFromParent();

2827

2828

2831 if (Phi != SIUse)

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

2833}

2834

2837

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

2839 return false;

2840

2844

2845

2846

2847

2849 continue;

2850

2853 continue;

2854

2856 return true;

2857 }

2858 return false;

2859}

2860

2861

2862

2863

2864

2865

2866

2867

2868

2869

2870

2871

2872

2877

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

2880 return false;

2881

2885

2886

2887

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

2889 continue;

2890

2893 continue;

2894

2895

2896

2897

2899 LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(1),

2900 CondRHS, Pred, BB, CondCmp);

2902 LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(2),

2903 CondRHS, Pred, BB, CondCmp);

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

2906 return true;

2907 }

2908 }

2909 return false;

2910}

2911

2912

2913

2914

2915

2916

2917

2918

2919

2920

2921

2922

2923

2924

2925

2926

2927

2928

2929

2930

2931

2933

2934

2936 return false;

2937

2938

2939

2940 if (LoopHeaders.count(BB))

2941 return false;

2942

2945

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

2948 continue;

2949

2952

2953

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

2955 return false;

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

2959 };

2960

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

2964

2965

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

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

2970 SI = SelectI;

2971 break;

2972 }

2974

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

2976 SI = SelectI;

2977 break;

2978 }

2979 }

2980 }

2981

2982 if ()

2983 continue;

2984

2989 }

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

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

2999 SI->replaceAllUsesWith(NewPN);

3000 SI->eraseFromParent();

3001

3002 std::vectorDominatorTree::UpdateType Updates;

3007

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

3011 }

3012 DTU->applyUpdatesPermissive(Updates);

3013 return true;

3014 }

3015 return false;

3016}

3017

3018

3019

3020

3021

3022

3023

3024

3025

3026

3027

3028

3029

3030

3031

3032

3033

3034

3035

3036

3039

3040

3043 if (PI == PE)

3044 return false;

3045 Pred1 = *PI++;

3046 if (PI == PE)

3047 return false;

3048 Pred2 = *PI++;

3049 if (PI != PE)

3050 return false;

3051 if (Pred1 == Pred2)

3052 return false;

3053

3054

3055

3058 return false;

3059

3061 for (auto &I : *BB)

3063 return true;

3064

3065 return false;

3066}

3067

3068

3069

3070

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

3079

3081 bool TrueDestIsSafe = false;

3082 bool FalseDestIsSafe = false;

3083

3084

3086 if (Impl && *Impl)

3087 TrueDestIsSafe = true;

3088 else {

3089

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

3091 if (Impl && *Impl)

3092 FalseDestIsSafe = true;

3093 }

3094

3095 if (!TrueDestIsSafe && !FalseDestIsSafe)

3096 return false;

3097

3098 BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;

3099 BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;

3100

3103 unsigned Cost =

3105 if (Cost > BBDupThreshold)

3106 return false;

3107

3108

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

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

3112

3113

3114

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

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

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

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

3120

3121

3122

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

3127

3130

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

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

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

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

3138 Inst->replaceAllUsesWith(NewPN);

3139 }

3140 Inst->dropDbgRecords();

3141 Inst->eraseFromParent();

3142 }

3143 return true;

3144}

3145

3146PreservedAnalyses JumpThreadingPass::getPreservedAnalysis() const {

3150

3151

3152

3153 return PA;

3154}

3155

3156template

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

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

3159

3160

3161

3162

3163 if (!ChangedSinceLastAnalysisUpdate) {

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

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

3166

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

3168 }

3169 ChangedSinceLastAnalysisUpdate = false;

3170

3171 auto PA = getPreservedAnalysis();

3172

3173

3174 PA.preserve();

3175 PA.preserve();

3176

3177 FAM->invalidate(*F, PA);

3178

3179 DTU->flush();

3180

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

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

3183 DTU->getPostDomTree().verify(

3184 PostDominatorTree::VerificationLevel::Fast)));

3185

3186 auto *Result = &FAM->getResult(*F);

3187

3188 TTI = &FAM->getResult(*F);

3189 TLI = &FAM->getResult(*F);

3190 AA = &FAM->getResult(*F);

3191

3193}

3194

3196 if (!BPI) {

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

3198 BPI = FAM->getCachedResult(*F);

3199 }

3200 return BPI;

3201}

3202

3204 if (!BFI) {

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

3206 BFI = FAM->getCachedResult(*F);

3207 }

3208 return BFI;

3209}

3210

3211

3212

3213

3215 auto *Res = getBPI();

3216 if (Res)

3217 return Res;

3218

3219 if (Force)

3220 BPI = runExternalAnalysis();

3221

3222 return BPI;

3223}

3224

3226 auto *Res = getBFI();

3227 if (Res)

3228 return Res;

3229

3230 if (Force)

3231 BFI = runExternalAnalysis();

3232

3233 return BFI;

3234}

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

ReachingDefInfo InstSet & ToRemove

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static const Function * getParent(const Value *V)

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

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

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

Definition JumpThreading.cpp:916

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)

Definition JumpThreading.cpp:392

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

Definition JumpThreading.cpp:426

static void remapSourceAtoms(ValueToValueMapTy &VM, BasicBlock::iterator Begin, BasicBlock::iterator End)

Definition JumpThreading.cpp:2024

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

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

Definition JumpThreading.cpp:1887

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

findMostPopularDest - The specified list contains multiple possible threadable destinations.

Definition JumpThreading.cpp:1471

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

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

Definition JumpThreading.cpp:536

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.

Definition JumpThreading.cpp:1209

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

Definition JumpThreading.cpp:148

static bool hasAddressTakenAndUsed(BasicBlock *BB)

Definition JumpThreading.cpp:934

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.

FunctionAnalysisManager FAM

This file contains the declarations for profiling metadata utility functions.

const SmallVectorImpl< MachineOperand > & Cond

This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...

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.

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.

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.

LLVM_ABI 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

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 bool hasNPredecessors(unsigned N) const

Return true if this block has exactly N predecessors.

LLVM_ABI const BasicBlock * getSinglePredecessor() const

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

const Instruction & front() const

LLVM_ABI const DataLayout & getDataLayout() const

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

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

LLVM_ABI LLVMContext & getContext() const

Get the context in which this basic block lives.

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

LLVM_ABI 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 LLVM_ABI BlockAddress * get(Function *F, BasicBlock *BB)

Return a BlockAddress for the specified function and basic block.

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

LLVM_ABI BlockFrequency getBlockFreq(const BasicBlock *BB) const

getblockFreq - Return block frequency.

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 providing branch probability information.

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

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

static LLVM_ABI 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 LLVM_ABI 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 LLVM_ABI 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 LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)

bool isZero() const

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

static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)

const APInt & getValue() const

Return the constant as an APInt value reference.

This class represents a range of values.

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

LLVM_ABI ConstantRange inverse() const

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

LLVM_ABI bool contains(const APInt &Val) const

Return true if the specified value is in the set.

This is an important base class in LLVM.

LLVM_ABI void removeDeadConstantUsers() const

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

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

Per-instruction record of debug-info.

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

LLVM_ABI const BasicBlock * getParent() const

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

static DebugLoc getTemporary()

static DebugLoc getDropped()

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.

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

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

Indirect Branch Instruction.

LLVM_ABI void removeFromParent()

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

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

LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

LLVM_ABI void setAAMetadata(const AAMDNodes &N)

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

LLVM_ABI bool isAtomic() const LLVM_READONLY

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

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

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

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

LLVM_ABI void setSuccessor(unsigned Idx, BasicBlock *BB)

Update the specified successor to point at the provided block.

LLVM_ABI const DataLayout & getDataLayout() const

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

bool isSpecialTerminator() const

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

LLVM_ABI bool simplifyPartiallyRedundantLoad(LoadInst *LI)

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

Definition JumpThreading.cpp:1220

LLVM_ABI bool processBranchOnXOR(BinaryOperator *BO)

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

Definition JumpThreading.cpp:1773

LLVM_ABI bool processGuards(BasicBlock *BB)

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

Definition JumpThreading.cpp:3037

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

Update the SSA form.

Definition JumpThreading.cpp:1971

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

LLVM_ABI void findLoopHeaders(Function &F)

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

Definition JumpThreading.cpp:525

LLVM_ABI bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB)

Merge basic block BB into its sole predecessor if possible.

Definition JumpThreading.cpp:1908

LLVM_ABI JumpThreadingPass(int T=-1)

Definition JumpThreading.cpp:109

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

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

Definition JumpThreading.cpp:2036

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition JumpThreading.cpp:237

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

Definition JumpThreading.cpp:1503

LLVM_ABI bool processBranchOnPHI(PHINode *PN)

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

Definition JumpThreading.cpp:1741

LLVM_ABI bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond)

Attempt to thread through two successive basic blocks.

Definition JumpThreading.cpp:2126

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

Definition JumpThreading.cpp:556

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

Definition JumpThreading.cpp:2772

DomTreeUpdater * getDomTreeUpdater() const

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

Definition JumpThreading.cpp:281

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

Definition JumpThreading.cpp:1560

LLVM_ABI bool processBlock(BasicBlock *BB)

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

Definition JumpThreading.cpp:946

LLVM_ABI bool processImpliedCondition(BasicBlock *BB)

Definition JumpThreading.cpp:1143

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

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

Definition JumpThreading.cpp:2627

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

Definition JumpThreading.cpp:2267

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

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

Definition JumpThreading.cpp:2343

LLVM_ABI bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB)

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

Definition JumpThreading.cpp:2873

LLVM_ABI bool tryToUnfoldSelectInCurrBB(BasicBlock *BB)

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

Definition JumpThreading.cpp:2932

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

Definition JumpThreading.cpp:2382

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

Definition JumpThreading.cpp:3071

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.

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

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.

bool erase(PtrType Ptr)

Remove pointer from the set.

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.

@ TCK_SizeAndLatency

The weighted sum of size and latency.

@ TCC_Free

Expected to fold away in lowering.

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 LLVM_ABI 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)

ValueMapIteratorImpl< MapT, const Value *, false > iterator

DMAtomT AtomMap

Map {(InlinedAt, old atom number) -> new atom number}.

LLVM Value Representation.

Type * getType() const

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

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

LLVM_ABI void replaceAllUsesWith(Value *V)

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

LLVM_ABI const Value * stripPointerCasts() const

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

iterator_range< use_iterator > uses()

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

LLVM_ABI void takeName(Value *V)

Transfer the name from V to this value.

const ParentTy * getParent() const

reverse_self_iterator getReverseIterator()

self_iterator getIterator()

NodeTy * getNextNode()

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

@ C

The default llvm calling convention, compatible with C.

LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)

Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.

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)

A private "module" namespace for types and utilities used by JumpThreading.

SmallVector< std::pair< Constant *, BasicBlock * >, 8 > PredValueInfoTy

SmallVectorImpl< std::pair< Constant *, BasicBlock * > > PredValueInfo

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

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

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

static cl::opt< unsigned long > StopAt("sbvec-stop-at", cl::init(StopAtDisabled), cl::Hidden, cl::desc("Vectorize if the invocation count is < than this. 0 " "disables vectorization."))

LLVM_ABI void findDbgValues(Value *V, SmallVectorImpl< DbgVariableRecord * > &DbgVariableRecords)

Finds the dbg.values describing a value.

detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)

auto pred_end(const MachineBasicBlock *BB)

LLVM_ABI unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)

decltype(auto) dyn_cast(const From &Val)

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

auto successors(const MachineBasicBlock *BB)

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

ConstantFoldInstruction - Try to constant fold the specified instruction.

constexpr from_range_t from_range

LLVM_ABI MDNode * getBranchWeightMDNode(const Instruction &I)

Get the branch weights metadata node.

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

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

LLVM_ABI 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)

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

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

Delete the specified block, which must have no predecessors.

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

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

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

LLVM_ABI bool hasBranchWeightOrigin(const Instruction &I)

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

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

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

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

LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)

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

auto dyn_cast_or_null(const Y &Val)

bool any_of(R &&range, UnaryPredicate P)

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

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

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

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

LLVM_ABI bool HasLoopOrEntryConvergenceToken(const BasicBlock *BB)

Check if the given basic block contains any loop or entry convergent intrinsic instructions.

auto reverse(ContainerTy &&C)

LLVM_ABI bool hasValidBranchWeightMD(const Instruction &I)

Checks if an instructions has valid Branch Weight Metadata.

LLVM_ABI raw_ostream & dbgs()

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

auto make_first_range(ContainerTy &&c)

Given a container of pairs, return a range over the first elements.

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

Attempt to constant fold a cast with the specified operand.

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

Duplicate the specified list of noalias decl scopes.

class LLVM_GSL_OWNER SmallVector

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

LLVM_ABI cl::opt< unsigned > DefMaxInstsToScan

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

bool isa(const From &Val)

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

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

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

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

RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)

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

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

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

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

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

RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)

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

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

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

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

DWARFExpression::Operation Op

auto max_element(R &&Range)

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

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

auto make_second_range(ContainerTy &&c)

Given a container of pairs, return a range over the second elements.

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)

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

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

Extract branch weights from MD_prof metadata.

auto pred_begin(const MachineBasicBlock *BB)

decltype(auto) cast(const From &Val)

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

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)

SuccIterator< Instruction, BasicBlock > succ_iterator

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

Returns true if Element is found in Range.

bool pred_empty(const BasicBlock *BB)

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

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

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

void array_pod_sort(IteratorTy Start, IteratorTy End)

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

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

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

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

AAResults AliasAnalysis

Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.

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

Filter the DbgRecord range to DbgVariableRecord types only and downcast.

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

LLVM_ABI void RemapSourceAtom(Instruction *I, ValueToValueMapTy &VM)

Remap source location atom.

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

LLVM_ABI void mapAtomInstance(const DebugLoc &DL, ValueToValueMapTy &VMap)

Mark a cloned instruction as a new instance so that its source loc can be updated when remapped.

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