MemoryDependenceAnalysis.cpp Source File (original) (raw)

50#include

51#include

52#include

53#include

55using namespace llvm;

57#define DEBUG_TYPE "memdep"

59 STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses");

60 STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses");

61 STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");

64 "Number of fully cached non-local ptr responses");

66 "Number of cached, but dirty, non-local ptr responses");

67 STATISTIC(NumUncacheNonLocalPtr, "Number of uncached non-local ptr responses");

69 "Number of block queries that were completely cached");

75 cl::desc("The number of instructions to scan in a block in memory "

76 "dependency analysis (default = 100)"));

80 cl::desc("The number of blocks to scan during memory "

81 "dependency analysis (default = 200)"));

85 cl::desc("The max number of entries allowed in a cache (default = 10000)"));

93template

94static void

98 ReverseMap.find(Inst);

99 assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");

100 bool Found = InstIt->second.erase(Val);

101 assert(Found && "Invalid reverse map!");

102 (void)Found;

103 if (InstIt->second.empty())

104 ReverseMap.erase(InstIt);

105}

106

107

108

109

110

111

115 if (LI->isUnordered()) {

118 }

122 }

125 }

126

128 if (SI->isUnordered()) {

131 }

135 }

138 }

139

143 }

144

147

150 }

151 }

152

154 switch (II->getIntrinsicID()) {

155 case Intrinsic::lifetime_start:

156 case Intrinsic::lifetime_end:

158

159

161 case Intrinsic::invariant_start:

163

164

166 case Intrinsic::invariant_end:

168

169

171 case Intrinsic::masked_load:

174 case Intrinsic::masked_store:

177 default:

178 break;

179 }

180 }

181

182

188}

189

190

191MemDepResult MemoryDependenceResults::getCallDependencyFrom(

195

196

197 while (ScanIt != BB->begin()) {

199

200

201

202 --Limit;

203 if (!Limit)

205

206

207 MemoryLocation Loc;

209 if (Loc.Ptr) {

210

213 continue;

214 }

215

217

219

220

221 if (isReadOnlyCall && isModSet (MR) &&

224

225

226

227 continue;

228 } else

230 }

231

232

233

236 }

237

238

239

243}

244

250 if (QueryInst != nullptr) {

253

254 if (InvariantGroupDependency.isDef())

255 return InvariantGroupDependency;

256 }

257 }

259 MemLoc, isLoad, ScanIt, BB, QueryInst, Limit, BatchAA);

260 if (SimpleDep.isDef())

261 return SimpleDep;

262

263

264

265 if (InvariantGroupDependency.isNonLocal())

266 return InvariantGroupDependency;

267

269 "InvariantGroupDependency should be only unknown at this point");

270 return SimpleDep;

271}

272

280

284

285 if (!LI->hasMetadata(LLVMContext::MD_invariant_group))

287

288

289

291

292

293

294

295

298

299 Instruction *ClosestDependency = nullptr;

300

301

303 assert(Other && "Must call it with not null instruction");

304 if (Best == nullptr || DT.dominates(Best, Other))

306 return Best;

307 };

308

309 for (const Use &Us : LoadOperand->uses()) {

311 if (!U || U == LI || !DT.dominates(U, LI))

312 continue;

313

314

315

316

320 U->hasMetadata(LLVMContext::MD_invariant_group))

321 ClosestDependency = GetClosestDependency(ClosestDependency, U);

322 }

323

324 if (!ClosestDependency)

326 if (ClosestDependency->getParent() == BB)

328

329

330

331

332 NonLocalDefsCache.try_emplace(

335 ReverseNonLocalDefsCache[ClosestDependency].insert(LI);

337}

338

339

340

341

342

343

347 unsigned ScanLimit) {

349 return false;

351 return false;

353 return false;

354 if (std::min(MemLocAlign, SI->getAlign()).value() <

356 return false;

357

359 if (!LI || LI->getParent() != SI->getParent())

360 return false;

362 return false;

363 unsigned NumVisitedInsts = 0;

365 if (++NumVisitedInsts > ScanLimit ||

367 return false;

368

369 return true;

370}

371

377 Align MemLocAlign =

379

381 if (!Limit)

382 Limit = &DefaultLimit;

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416 if (isLoad && QueryInst)

418 if (LI->hasMetadata(LLVMContext::MD_invariant_load))

420 MemLocAlign = LI->getAlign();

421 }

422

423

424

425

427 if (I->isVolatile())

428 return true;

433 return I->mayReadOrWriteMemory();

434 };

435

436

437 while (ScanIt != BB->begin()) {

439

440

441

442 --*Limit;

443 if (!*Limit)

445

447

448

450 switch (ID) {

451 case Intrinsic::lifetime_start: {

455 continue;

456 }

457 case Intrinsic::masked_load:

458 case Intrinsic::masked_store: {

463 continue;

466 if (ID == Intrinsic::masked_load)

467 continue;

469 }

470 }

471 }

472

473

474

475

476

477

479

480

481

482 if (LI->isVolatile()) {

483 if (!QueryInst)

484

487

489

490 }

491

492

493

494

495

497 if (!QueryInst ||

502 }

503

505

506

508

510 continue;

511

513

516

517

518

520 ClobberOffsets[LI] = R.getOffset();

522 }

523

524

525

526 continue;

527 }

528

529

531 continue;

532

533

535 }

536

538

539

540

541 if (->isUnordered() && SI->isAtomic()) {

542 if (!QueryInst ||

545

546

547

548

549

550

551

552

553

554 }

555

556

557

558

559 if (SI->isVolatile())

560 if (!QueryInst || QueryInst->isVolatile())

562

563

564

565

567 continue;

568

569

570

571

573

574

576

578 continue;

582 continue;

584 continue;

586 }

587

588

589

590

591

592

593

596 if (AccessPtr == Inst || BatchAA.isMustAlias(Inst, AccessPtr))

598 }

599

600

601

604

606 continue;

607

608

609

610

611

612

615 continue;

616

617

620

621 continue;

625

626

628 continue;

629 [[fallthrough]];

630 default:

631

633 }

634 }

635

636

637

641}

642

644 ClobberOffsets.clear();

646

647

648 MemDepResult &LocalCache = LocalDeps[QueryInst];

649

650

651

652 if (!LocalCache.isDirty())

653 return LocalCache;

654

655

656

658 ScanPos = Inst;

659

661 }

662

664

665

667

668

671 else

673 } else {

676 if (MemLoc.Ptr) {

677

680 isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;

681

682 LocalCache =

684 QueryParent, QueryInst, nullptr);

686 bool isReadOnly = AA.onlyReadsMemory(QueryCall);

687 LocalCache = getCallDependencyFrom(QueryCall, isReadOnly,

689 } else

690

692 }

693

694

696 ReverseLocalDeps[I].insert(QueryInst);

697

698 return LocalCache;

699}

700

701#ifndef NDEBUG

702

703

705 int Count = -1) {

707 Count = Cache.size();

708 assert(std::is_sorted(Cache.begin(), Cache.begin() + Count) &&

709 "Cache isn't sorted!");

710}

711#endif

712

716 "getNonLocalCallDependency should only be used on calls with "

717 "non-local deps!");

718 PerInstNLInfo &CacheP = NonLocalDepsMap[QueryCall];

720

721

722

723

725

726 if (!Cache.empty()) {

727

728

729 if (!CacheP.second) {

730 ++NumCacheNonLocal;

731 return Cache;

732 }

733

734

735

736 for (auto &Entry : Cache)

737 if (Entry.getResult().isDirty())

738 DirtyBlocks.push_back(Entry.getBB());

739

740

742

743 ++NumCacheDirtyNonLocal;

744 } else {

745

747 append_range(DirtyBlocks, PredCache.get(QueryBB));

748 ++NumUncacheNonLocal;

749 }

750

751

752 bool isReadonlyCall = AA.onlyReadsMemory(QueryCall);

753

755

756 unsigned NumSortedEntries = Cache.size();

758

759

760 while (!DirtyBlocks.empty()) {

762

763

764 if (!Visited.insert(DirtyBB).second)

765 continue;

766

767

768

770 NonLocalDepInfo::iterator Entry =

771 std::upper_bound(Cache.begin(), Cache.begin() + NumSortedEntries,

773 if (Entry != Cache.begin() && std::prev(Entry)->getBB() == DirtyBB)

774 --Entry;

775

777 if (Entry != Cache.begin() + NumSortedEntries &&

778 Entry->getBB() == DirtyBB) {

779

780

781 if (!Entry->getResult().isDirty())

782 continue;

783

784

785 ExistingResult = &*Entry;

786 }

787

788

789

791 if (ExistingResult) {

794

796 QueryCall);

797 }

798 }

799

800

802

803 if (ScanPos != DirtyBB->begin()) {

804 Dep = getCallDependencyFrom(QueryCall, isReadonlyCall, ScanPos, DirtyBB);

806

807

809 } else {

811 }

812

813

814

815 if (ExistingResult)

817 else

819

820

821

823

824

826 ReverseNonLocalDeps[Inst].insert(QueryCall);

827 } else {

828

829

830

831 append_range(DirtyBlocks, PredCache.get(DirtyBB));

832 }

833 }

834

835 return Cache;

836}

837

844

845 assert(Loc.Ptr->getType()->isPointerTy() &&

846 "Can't get pointer deps of a non-pointer!");

847 Result.clear();

848 {

849

850 auto NonLocalDefIt = NonLocalDefsCache.find(QueryInst);

851 if (NonLocalDefIt != NonLocalDefsCache.end()) {

852 Result.push_back(NonLocalDefIt->second);

853 ReverseNonLocalDefsCache[NonLocalDefIt->second.getResult().getInst()]

854 .erase(QueryInst);

855 NonLocalDefsCache.erase(NonLocalDefIt);

856 return;

857 }

858 }

859

860

861

862

863

864

865

866

869 return !LI->isUnordered();

871 return ->isUnordered();

872 }

873 return false;

874 };

877 const_cast<Value *>(Loc.Ptr)));

878 return;

879 }

882

883

884

885

886

888 if (getNonLocalPointerDepFromBB(QueryInst, Address, Loc, isLoad, FromBB,

889 Result, Visited, true))

890 return;

891 Result.clear();

893 const_cast<Value *>(Loc.Ptr)));

894}

895

896

897

898

899

900

901MemDepResult MemoryDependenceResults::getNonLocalInfoForBlock(

903 BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries,

905

907

909 isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);

910

911

912

913 NonLocalDepInfo::iterator Entry = std::upper_bound(

914 Cache->begin(), Cache->begin() + NumSortedEntries, NonLocalDepEntry(BB));

915 if (Entry != Cache->begin() && (Entry - 1)->getBB() == BB)

916 --Entry;

917

919 if (Entry != Cache->begin() + NumSortedEntries && Entry->getBB() == BB)

920 ExistingResult = &*Entry;

921

922

923

924

927 ExistingResult = nullptr;

928

929

930

931 if (ExistingResult && !ExistingResult->getResult().isDirty()) {

932 ++NumCacheNonLocalPtr;

933 return ExistingResult->getResult();

934 }

935

936

937

938

940 if (ExistingResult && ExistingResult->getResult().getInst()) {

942 "Instruction invalidated?");

943 ++NumCacheDirtyNonLocalPtr;

945

946

947 ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);

949 } else {

950 ++NumUncacheNonLocalPtr;

951 }

952

953

955 QueryInst, nullptr, BatchAA);

956

957

959 return Dep;

960

961

962

963 if (ExistingResult)

965 else

966 Cache->push_back(NonLocalDepEntry(BB, Dep));

967

968

969

970

972 return Dep;

973

974

975

977 assert(Inst && "Didn't depend on anything?");

978 ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);

979 ReverseNonLocalPtrDeps[Inst].insert(CacheKey);

980 return Dep;

981}

982

983

984

985

986

987static void

989 unsigned NumSortedEntries) {

990

991

992 if (Cache.size() < 2)

993 return;

994

995 unsigned s = Cache.size() - NumSortedEntries;

996

997

998 if (s == 0)

999 return;

1000

1001

1002 if (NumSortedEntries == 0) {

1004 return;

1005 }

1006

1007

1008

1009

1010 if (s < Log2_32(Cache.size())) {

1011 while (s > 0) {

1013 Cache.pop_back();

1014 MemoryDependenceResults::NonLocalDepInfo::iterator Entry =

1015 std::upper_bound(Cache.begin(), Cache.end() - s + 1, Val);

1016 Cache.insert(Entry, Val);

1017 s--;

1018 }

1019 } else {

1021 }

1022}

1023

1024

1025

1026

1027

1028

1029

1030

1031

1032

1033

1034

1035

1036

1037bool MemoryDependenceResults::getNonLocalPointerDepFromBB(

1042 bool IsIncomplete) {

1043

1044 ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);

1045

1046

1047

1048

1049

1050 NonLocalPointerInfo InitialNLPI;

1051 InitialNLPI.Size = Loc.Size;

1052 InitialNLPI.AATags = Loc.AATags;

1053

1056 isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);

1057

1058

1059

1060 std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =

1061 NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));

1062 NonLocalPointerInfo *CacheInfo = &Pair.first->second;

1063

1064

1065

1066

1068 if (CacheInfo->Size != Loc.Size) {

1069

1070

1071 CacheInfo->Pair = BBSkipFirstBlockPair();

1072 CacheInfo->Size = Loc.Size;

1073 for (auto &Entry : CacheInfo->NonLocalDeps)

1074 if (Instruction *Inst = Entry.getResult().getInst())

1076 CacheInfo->NonLocalDeps.clear();

1077

1078

1079

1080 IsIncomplete = true;

1081 }

1082

1083

1084

1085

1086 if (CacheInfo->AATags != Loc.AATags) {

1087 if (CacheInfo->AATags) {

1088 CacheInfo->Pair = BBSkipFirstBlockPair();

1089 CacheInfo->AATags = AAMDNodes();

1090 for (auto &Entry : CacheInfo->NonLocalDeps)

1091 if (Instruction *Inst = Entry.getResult().getInst())

1093 CacheInfo->NonLocalDeps.clear();

1094

1095

1096

1097 IsIncomplete = true;

1098 }

1100 return getNonLocalPointerDepFromBB(

1102 Visited, SkipFirstBlock, IsIncomplete);

1103 }

1104 }

1105

1107

1108

1109

1110

1111

1113 CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {

1114

1115

1116

1117

1118

1119 if (!Visited.empty()) {

1120 for (auto &Entry : *Cache) {

1123 if (VI == Visited.end() || VI->second == Pointer.getAddr())

1124 continue;

1125

1126

1127

1128

1129 return false;

1130 }

1131 }

1132

1134 for (auto &Entry : *Cache) {

1135 Visited.insert(std::make_pair(Entry.getBB(), Addr));

1136 if (Entry.getResult().isNonLocal()) {

1137 continue;

1138 }

1139

1140 if (DT.isReachableFromEntry(Entry.getBB())) {

1142 NonLocalDepResult(Entry.getBB(), Entry.getResult(), Addr));

1143 }

1144 }

1145 ++NumCacheCompleteNonLocalPtr;

1146 return true;

1147 }

1148

1149

1151 return false;

1152

1153

1154

1155

1156

1157

1158

1159

1161 if (!IsIncomplete && Cache->empty())

1162 CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);

1163 else

1164 CacheInfo->Pair = BBSkipFirstBlockPair();

1165 }

1166

1169

1170

1172

1173

1174

1175

1176

1177

1178 unsigned NumSortedEntries = Cache->size();

1180 bool GotWorklistLimit = false;

1182

1183 BatchAAResults BatchAA(AA, &EEA);

1184 while (!Worklist.empty()) {

1186

1187

1188

1190

1191

1192

1193 if (Cache && NumSortedEntries != Cache->size()) {

1195 }

1196

1197

1198

1199

1200 CacheInfo->Pair = BBSkipFirstBlockPair();

1201 return false;

1202 }

1203

1204

1205 if (!SkipFirstBlock) {

1206

1207

1208 assert(Visited.count(BB) && "Should check 'visited' before adding to WL");

1209

1210

1211

1213 MemDepResult Dep = getNonLocalInfoForBlock(

1214 QueryInst, Loc, isLoad, BB, Cache, NumSortedEntries, BatchAA);

1215

1216

1218 if (DT.isReachableFromEntry(BB)) {

1219 Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr()));

1220 continue;

1221 }

1222 }

1223 }

1224

1225

1226

1227

1228

1229 if ( Pointer .needsPHITranslationFromBlock(BB)) {

1230 SkipFirstBlock = false;

1231 SmallVector<BasicBlock *, 16> NewBlocks;

1232 for (BasicBlock *Pred : PredCache.get(BB)) {

1233

1234 std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> InsertRes =

1235 Visited.insert(std::make_pair(Pred, Pointer.getAddr()));

1236 if (InsertRes.second) {

1237

1239 continue;

1240 }

1241

1242

1243

1244

1245 if (InsertRes.first->second != Pointer.getAddr()) {

1246

1247

1248 for (auto *NewBlock : NewBlocks)

1249 Visited.erase(NewBlock);

1250 goto PredTranslationFailure;

1251 }

1252 }

1253 if (NewBlocks.size() > WorklistEntries) {

1254

1255

1256 for (auto *NewBlock : NewBlocks)

1257 Visited.erase(NewBlock);

1258 GotWorklistLimit = true;

1259 goto PredTranslationFailure;

1260 }

1261 WorklistEntries -= NewBlocks.size();

1262 Worklist.append(NewBlocks.begin(), NewBlocks.end());

1263 continue;

1264 }

1265

1266

1267

1268 if ( Pointer .isPotentiallyPHITranslatable())

1269 goto PredTranslationFailure;

1270

1271

1272

1273

1274

1275

1276 if (Cache && NumSortedEntries != Cache->size()) {

1278 NumSortedEntries = Cache->size();

1279 }

1280 Cache = nullptr;

1281

1282 PredList.clear();

1283 for (BasicBlock *Pred : PredCache.get(BB)) {

1284 PredList.push_back(std::make_pair(Pred, Pointer));

1285

1286

1287

1288 PHITransAddr &PredPointer = PredList.back().second;

1289 Value *PredPtrVal =

1290 PredPointer.translateValue(BB, Pred, &DT, false);

1291

1292

1293

1294

1295

1296

1297 std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> InsertRes =

1298 Visited.insert(std::make_pair(Pred, PredPtrVal));

1299

1300 if (!InsertRes.second) {

1301

1303

1304

1305

1306 if (InsertRes.first->second == PredPtrVal)

1307 continue;

1308

1309

1310

1311

1312

1313

1314

1315 for (const auto &Pred : PredList)

1316 Visited.erase(Pred.first);

1317

1318 goto PredTranslationFailure;

1319 }

1320 }

1321

1322

1323

1324

1325

1326

1327 for (auto &I : PredList) {

1329 PHITransAddr &PredPointer = I.second;

1331

1332 bool CanTranslate = true;

1333

1334

1335

1336

1337 if (!PredPtrVal)

1338 CanTranslate = false;

1339

1340

1341

1342

1343

1344

1345

1346

1347

1348 if (!CanTranslate ||

1349 !getNonLocalPointerDepFromBB(QueryInst, PredPointer,

1351 Pred, Result, Visited)) {

1352

1354 Result.push_back(Entry);

1355

1356

1357

1358

1359

1360

1361 NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];

1362 NLPI.Pair = BBSkipFirstBlockPair();

1363 continue;

1364 }

1365 }

1366

1367

1368 CacheInfo = &NonLocalPointerDeps[CacheKey];

1369 Cache = &CacheInfo->NonLocalDeps;

1370 NumSortedEntries = Cache->size();

1371

1372

1373

1374

1375

1376 CacheInfo->Pair = BBSkipFirstBlockPair();

1377 SkipFirstBlock = false;

1378 continue;

1379

1380 PredTranslationFailure:

1381

1382

1383

1384

1385 if (!Cache) {

1386

1387 CacheInfo = &NonLocalPointerDeps[CacheKey];

1388 Cache = &CacheInfo->NonLocalDeps;

1389 NumSortedEntries = Cache->size();

1390 }

1391

1392

1393

1394

1395

1396 CacheInfo->Pair = BBSkipFirstBlockPair();

1397

1398

1399

1400

1401

1402

1403 if (SkipFirstBlock)

1404 return false;

1405

1406

1407

1410 if (I.getBB() != BB)

1411 continue;

1412

1413 assert((GotWorklistLimit || I.getResult().isNonLocal() ||

1414 !DT.isReachableFromEntry(BB)) &&

1415 "Should only be here with transparent block");

1416

1418

1419

1420 break;

1421 }

1422 }

1423 (void)GotWorklistLimit;

1424

1427 }

1428

1429

1432 return true;

1433}

1434

1435

1436void MemoryDependenceResults::removeCachedNonLocalPointerDependencies(

1437 ValueIsLoadPair P) {

1438

1439

1440 if (!NonLocalDefsCache.empty()) {

1441 auto it = NonLocalDefsCache.find(P.getPointer());

1442 if (it != NonLocalDefsCache.end()) {

1444 it->second.getResult().getInst(), P.getPointer());

1445 NonLocalDefsCache.erase(it);

1446 }

1447

1449 auto toRemoveIt = ReverseNonLocalDefsCache.find(I);

1450 if (toRemoveIt != ReverseNonLocalDefsCache.end()) {

1451 for (const auto *entry : toRemoveIt->second)

1452 NonLocalDefsCache.erase(entry);

1453 ReverseNonLocalDefsCache.erase(toRemoveIt);

1454 }

1455 }

1456 }

1457

1459 if (It == NonLocalPointerDeps.end())

1460 return;

1461

1462

1463

1465

1466 for (const NonLocalDepEntry &DE : PInfo) {

1468 if (!Target)

1469 continue;

1471

1472

1474 }

1475

1476

1477 NonLocalPointerDeps.erase(It);

1478}

1479

1481

1483 return;

1484

1485 removeCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false));

1486

1487 removeCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));

1488}

1489

1491 PredCache.clear();

1492}

1493

1495 EEA.removeInstruction(RemInst);

1496

1497

1498

1500 if (NLDI != NonLocalDepsMap.end()) {

1502 for (auto &Entry : BlockMap)

1503 if (Instruction *Inst = Entry.getResult().getInst())

1505 NonLocalDepsMap.erase(NLDI);

1506 }

1507

1508

1510 if (LocalDepEntry != LocalDeps.end()) {

1511

1512 if (Instruction *Inst = LocalDepEntry->second.getInst())

1514

1515

1516 LocalDeps.erase(LocalDepEntry);

1517 }

1518

1519

1520

1521

1522

1523

1525 removeCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));

1526 removeCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));

1527 } else {

1528

1529

1530 auto toRemoveIt = NonLocalDefsCache.find(RemInst);

1531 if (toRemoveIt != NonLocalDefsCache.end()) {

1533 "only load instructions should be added directly");

1534 const Instruction *DepV = toRemoveIt->second.getResult().getInst();

1535 ReverseNonLocalDefsCache.find(DepV)->second.erase(RemInst);

1536 NonLocalDefsCache.erase(toRemoveIt);

1537 }

1538 }

1539

1540

1542

1543

1544

1545

1546

1547

1548

1551 NewDirtyVal = MemDepResult::getDirty(&*++RemInst->getIterator());

1552

1553 ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);

1554 if (ReverseDepIt != ReverseLocalDeps.end()) {

1555

1557 "Nothing can locally depend on a terminator");

1558

1559 for (Instruction *InstDependingOnRemInst : ReverseDepIt->second) {

1560 assert(InstDependingOnRemInst != RemInst &&

1561 "Already removed our local dep info");

1562

1563 LocalDeps[InstDependingOnRemInst] = NewDirtyVal;

1564

1565

1567 "There is no way something else can have "

1568 "a local dep on this if it is a terminator!");

1570 std::make_pair(NewDirtyVal.getInst(), InstDependingOnRemInst));

1571 }

1572

1573 ReverseLocalDeps.erase(ReverseDepIt);

1574

1575

1576

1577 while (!ReverseDepsToAdd.empty()) {

1578 ReverseLocalDeps[ReverseDepsToAdd.back().first].insert(

1579 ReverseDepsToAdd.back().second);

1580 ReverseDepsToAdd.pop_back();

1581 }

1582 }

1583

1584 ReverseDepIt = ReverseNonLocalDeps.find(RemInst);

1585 if (ReverseDepIt != ReverseNonLocalDeps.end()) {

1586 for (Instruction *I : ReverseDepIt->second) {

1587 assert(I != RemInst && "Already removed NonLocalDep info for RemInst");

1588

1589 PerInstNLInfo &INLD = NonLocalDepsMap[I];

1590

1591 INLD.second = true;

1592

1593 for (auto &Entry : INLD.first) {

1594 if (Entry.getResult().getInst() != RemInst)

1595 continue;

1596

1597

1598 Entry.setResult(NewDirtyVal);

1599

1601 ReverseDepsToAdd.push_back(std::make_pair(NextI, I));

1602 }

1603 }

1604

1605 ReverseNonLocalDeps.erase(ReverseDepIt);

1606

1607

1608 while (!ReverseDepsToAdd.empty()) {

1609 ReverseNonLocalDeps[ReverseDepsToAdd.back().first].insert(

1610 ReverseDepsToAdd.back().second);

1611 ReverseDepsToAdd.pop_back();

1612 }

1613 }

1614

1615

1616

1617 ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =

1618 ReverseNonLocalPtrDeps.find(RemInst);

1619 if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {

1621 ReversePtrDepsToAdd;

1622

1623 for (ValueIsLoadPair P : ReversePtrDepIt->second) {

1624 assert(P.getPointer() != RemInst &&

1625 "Already removed NonLocalPointerDeps info for RemInst");

1626

1627 auto &NLPD = NonLocalPointerDeps[P];

1628

1630

1631

1632 NLPD.Pair = BBSkipFirstBlockPair();

1633

1634

1635 for (auto &Entry : NLPDI) {

1636 if (Entry.getResult().getInst() != RemInst)

1637 continue;

1638

1639

1640 Entry.setResult(NewDirtyVal);

1641

1643 ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));

1644 }

1645

1646

1647

1649 }

1650

1651 ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);

1652

1653 while (!ReversePtrDepsToAdd.empty()) {

1654 ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first].insert(

1655 ReversePtrDepsToAdd.back().second);

1656 ReversePtrDepsToAdd.pop_back();

1657 }

1658 }

1659

1660 assert(!NonLocalDepsMap.count(RemInst) && "RemInst got reinserted?");

1662}

1663

1664

1665

1666

1667

1668void MemoryDependenceResults::verifyRemoved(Instruction *D) const {

1669#ifndef NDEBUG

1670 for (const auto &DepKV : LocalDeps) {

1671 assert(DepKV.first != D && "Inst occurs in data structures");

1672 assert(DepKV.second.getInst() != D && "Inst occurs in data structures");

1673 }

1674

1675 for (const auto &DepKV : NonLocalPointerDeps) {

1676 assert(DepKV.first.getPointer() != D && "Inst occurs in NLPD map key");

1677 for (const auto &Entry : DepKV.second.NonLocalDeps)

1678 assert(Entry.getResult().getInst() != D && "Inst occurs as NLPD value");

1679 }

1680

1681 for (const auto &DepKV : NonLocalDepsMap) {

1682 assert(DepKV.first != D && "Inst occurs in data structures");

1683 const PerInstNLInfo &INLD = DepKV.second;

1684 for (const auto &Entry : INLD.first)

1686 "Inst occurs in data structures");

1687 }

1688

1689 for (const auto &DepKV : ReverseLocalDeps) {

1690 assert(DepKV.first != D && "Inst occurs in data structures");

1691 for (Instruction *Inst : DepKV.second)

1692 assert(Inst != D && "Inst occurs in data structures");

1693 }

1694

1695 for (const auto &DepKV : ReverseNonLocalDeps) {

1696 assert(DepKV.first != D && "Inst occurs in data structures");

1697 for (Instruction *Inst : DepKV.second)

1698 assert(Inst != D && "Inst occurs in data structures");

1699 }

1700

1701 for (const auto &DepKV : ReverseNonLocalPtrDeps) {

1702 assert(DepKV.first != D && "Inst occurs in rev NLPD map");

1703

1704 for (ValueIsLoadPair P : DepKV.second)

1705 assert(P != ValueIsLoadPair(D, false) && P != ValueIsLoadPair(D, true) &&

1706 "Inst occurs in ReverseNonLocalPtrDeps map");

1707 }

1708#endif

1709}

1710

1711AnalysisKey MemoryDependenceAnalysis::Key;

1712

1715

1724

1726

1728 "Memory Dependence Analysis", false, true)

1735

1737

1739

1741 MemDep.reset();

1742}

1743

1751

1753 FunctionAnalysisManager::Invalidator &Inv) {

1754

1757

1758 return true;

1759

1760

1761 if (Inv.invalidate<AAManager>(F, PA) ||

1764 return true;

1765

1766

1767 return false;

1768}

1769

1771 return DefaultBlockScanLimit;

1772}

1773

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

static bool isLoad(int Opcode)

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Atomic ordering constants.

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

This file defines the DenseMap class.

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

This defines the Use class.

static const unsigned int NumResultsLimit

Definition MemoryDependenceAnalysis.cpp:88

static cl::opt< unsigned > CacheGlobalLimit("memdep-cache-global-limit", cl::Hidden, cl::init(10000), cl::desc("The max number of entries allowed in a cache (default = 10000)"))

static ModRefInfo GetLocation(const Instruction *Inst, MemoryLocation &Loc, const TargetLibraryInfo &TLI)

If the given instruction references a specific memory location, fill in Loc with the details,...

Definition MemoryDependenceAnalysis.cpp:112

static cl::opt< unsigned > BlockNumberLimit("memdep-block-number-limit", cl::Hidden, cl::init(200), cl::desc("The number of blocks to scan during memory " "dependency analysis (default = 200)"))

static void RemoveFromReverseMap(DenseMap< Instruction *, SmallPtrSet< KeyTy, 4 > > &ReverseMap, Instruction *Inst, KeyTy Val)

This is a helper function that removes Val from 'Inst's set in ReverseMap.

Definition MemoryDependenceAnalysis.cpp:95

static void SortNonLocalDepInfoCache(MemoryDependenceResults::NonLocalDepInfo &Cache, unsigned NumSortedEntries)

Sort the NonLocalDepInfo cache, given a certain number of elements in the array that are already prop...

Definition MemoryDependenceAnalysis.cpp:988

static void AssertSorted(MemoryDependenceResults::NonLocalDepInfo &Cache, int Count=-1)

This method is used when -debug is specified to verify that cache arrays are properly kept sorted.

Definition MemoryDependenceAnalysis.cpp:704

static bool canSkipClobberingStore(const StoreInst *SI, const MemoryLocation &MemLoc, Align MemLocAlign, BatchAAResults &BatchAA, unsigned ScanLimit)

Definition MemoryDependenceAnalysis.cpp:344

static cl::opt< unsigned > BlockScanLimit("memdep-block-scan-limit", cl::Hidden, cl::init(100), cl::desc("The number of instructions to scan in a block in memory " "dependency analysis (default = 100)"))

This file provides utility analysis objects describing memory locations.

static bool isOrdered(const Instruction *I)

static bool isInvariantLoad(const Instruction *I, const Value *Ptr, const bool IsKernelFn)

uint64_t IntrinsicInst * II

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

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)

A manager for alias analyses.

A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.

The possible results of an alias query.

@ NoAlias

The two locations do not alias at all.

@ PartialAlias

The two locations alias, but only due to a partial overlap.

@ MustAlias

The two locations precisely alias each other.

This templated class represents "all analyses that operate over " (e....

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

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

Represent the analysis usage information of a pass.

AnalysisUsage & addRequired()

void setPreservesAll()

Set by analyses that do not transform their input at all.

AnalysisUsage & addRequiredTransitive()

A function analysis which provides an AssumptionCache.

An immutable pass that tracks lazily created AssumptionCache objects.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

const Function * getParent() const

Return the enclosing method, or null if none.

LLVM_ABI const DataLayout & getDataLayout() const

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

InstListType::iterator iterator

Instruction iterators...

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

AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)

bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)

ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)

ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, bool IgnoreLocals=false)

Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...

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

iterator find(const_arg_type_t< KeyT > Val)

bool erase(const KeyT &Val)

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator

size_type count(const_arg_type_t< KeyT > Val) const

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

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

Analysis pass which computes a DominatorTree.

Legacy analysis pass which computes a DominatorTree.

An instruction for ordering other memory operations.

const BasicBlock & getEntryBlock() const

LLVM_ABI bool mayWriteToMemory() const LLVM_READONLY

Return true if this instruction may modify memory.

bool hasMetadata() const

Return true if this instruction has any metadata attached to it.

LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY

This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...

bool isTerminator() const

LLVM_ABI bool mayReadFromMemory() const LLVM_READONLY

Return true if this instruction may read memory.

LLVM_ABI bool isVolatile() const LLVM_READONLY

Return true if this instruction has a volatile memory access.

A wrapper class for inspecting calls to intrinsic functions.

An instruction for reading from memory.

Value * getPointerOperand()

TypeSize getValue() const

A memory dependence query can return one of three different answers.

bool isNonLocal() const

Tests if this MemDepResult represents a query that is transparent to the start of the block,...

static MemDepResult getNonLocal()

bool isNonFuncLocal() const

Tests if this MemDepResult represents a query that is transparent to the start of the function.

static MemDepResult getClobber(Instruction *Inst)

bool isDef() const

Tests if this MemDepResult represents a query that is an instruction definition dependency.

static MemDepResult getUnknown()

bool isLocal() const

Tests if this MemDepResult represents a valid local query (Clobber/Def).

bool isUnknown() const

Tests if this MemDepResult represents a query which cannot and/or will not be computed.

static MemDepResult getNonFuncLocal()

static MemDepResult getDef(Instruction *Inst)

get methods: These are static ctor methods for creating various MemDepResult kinds.

Instruction * getInst() const

If this is a normal dependency, returns the instruction that is depended on.

An analysis that produces MemoryDependenceResults for a function.

MemoryDependenceResults run(Function &F, FunctionAnalysisManager &AM)

Definition MemoryDependenceAnalysis.cpp:1717

MemoryDependenceAnalysis()

Definition MemoryDependenceAnalysis.cpp:1713

Provides a lazy, caching interface for making common memory aliasing information queries,...

MemDepResult getSimplePointerDependencyFrom(const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst, unsigned *Limit, BatchAAResults &BatchAA)

Definition MemoryDependenceAnalysis.cpp:372

std::vector< NonLocalDepEntry > NonLocalDepInfo

void invalidateCachedPredecessors()

Clears the PredIteratorCache info.

Definition MemoryDependenceAnalysis.cpp:1490

void invalidateCachedPointerInfo(Value *Ptr)

Invalidates cached information about the specified pointer, because it may be too conservative in mem...

Definition MemoryDependenceAnalysis.cpp:1480

MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst=nullptr, unsigned *Limit=nullptr)

Returns the instruction on which a memory location depends.

Definition MemoryDependenceAnalysis.cpp:273

void removeInstruction(Instruction *InstToRemove)

Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...

Definition MemoryDependenceAnalysis.cpp:1494

MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB)

This analysis looks for other loads and stores with invariant.group metadata and the same pointer ope...

Definition MemoryDependenceAnalysis.cpp:282

unsigned getDefaultBlockScanLimit() const

Some methods limit the number of instructions they will examine.

Definition MemoryDependenceAnalysis.cpp:1770

MemDepResult getDependency(Instruction *QueryInst)

Returns the instruction on which a memory operation depends.

Definition MemoryDependenceAnalysis.cpp:643

const NonLocalDepInfo & getNonLocalCallDependency(CallBase *QueryCall)

Perform a full dependency query for the specified call, returning the set of blocks that the value is...

Definition MemoryDependenceAnalysis.cpp:714

void getNonLocalPointerDependency(Instruction *QueryInst, SmallVectorImpl< NonLocalDepResult > &Result)

Perform a full dependency query for an access to the QueryInst's specified memory location,...

Definition MemoryDependenceAnalysis.cpp:838

bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)

Handle invalidation in the new PM.

Definition MemoryDependenceAnalysis.cpp:1752

A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance.

bool runOnFunction(Function &) override

Pass Implementation stuff. This doesn't do any analysis eagerly.

Definition MemoryDependenceAnalysis.cpp:1774

~MemoryDependenceWrapperPass() override

void getAnalysisUsage(AnalysisUsage &AU) const override

Does not modify anything. It uses Value Numbering and Alias Analysis.

Definition MemoryDependenceAnalysis.cpp:1744

void releaseMemory() override

Clean up memory in between runs.

Definition MemoryDependenceAnalysis.cpp:1740

MemoryDependenceWrapperPass()

Definition MemoryDependenceAnalysis.cpp:1736

Representation for a specific memory location.

MemoryLocation getWithoutAATags() const

static LLVM_ABI MemoryLocation get(const LoadInst *LI)

Return a location with information about the memory reference by the given instruction.

LocationSize Size

The maximum size of the location, in address-units, or UnknownSize if the size is not known.

static MemoryLocation getAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())

Return a location that may access any location after Ptr, while remaining within the underlying objec...

MemoryLocation getWithNewPtr(const Value *NewPtr) const

AAMDNodes AATags

The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...

const Value * Ptr

The address of the start of the location.

static LLVM_ABI MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)

Return a location representing a particular argument of a call.

This is an entry in the NonLocalDepInfo cache.

void setResult(const MemDepResult &R)

const MemDepResult & getResult() const

This is a result from a NonLocal dependence query.

PHITransAddr - An address value which tracks and handles phi translation.

LLVM_ABI Value * translateValue(BasicBlock *CurBB, BasicBlock *PredBB, const DominatorTree *DT, bool MustDominate)

translateValue - PHI translate the current address up the CFG from CurBB to Pred, updating our state ...

AnalysisType & getAnalysis() const

getAnalysis() - This function is used by subclasses to get to the analysis information ...

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

PreservedAnalysisChecker getChecker() const

Build a checker for this PreservedAnalyses and the specified analysis type.

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.

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

iterator erase(const_iterator CI)

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

void push_back(const T &Elt)

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

An instruction for storing to memory.

Analysis pass providing the TargetLibraryInfo.

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

bool isPointerTy() const

True if this is an instance of PointerType.

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

This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...

LLVM Value Representation.

Type * getType() const

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

LLVM_ABI Align getPointerAlignment(const DataLayout &DL) const

Returns an alignment of the pointer value.

LLVM_ABI const Value * stripPointerCasts() const

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

iterator_range< use_iterator > uses()

constexpr ScalarTy getKnownMinValue() const

Returns the minimum value this quantity can represent.

const ParentTy * getParent() const

self_iterator getIterator()

Abstract Attribute helper functions.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

@ BasicBlock

Various leaf nodes.

initializer< Ty > init(const Ty &Val)

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

decltype(auto) dyn_cast(const From &Val)

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

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

Wrapper function to append range R to container C.

bool isStrongerThanUnordered(AtomicOrdering AO)

LLVM_ABI bool isNoAliasCall(const Value *V)

Return true if this pointer is returned by a noalias function.

const Value * getPointerOperand(const Value *V)

A helper function that returns the pointer operand of a load, store or GEP instruction.

auto dyn_cast_or_null(const Y &Val)

unsigned Log2_32(uint32_t Value)

Return the floor log base 2 of the specified value, -1 if the value is zero.

auto reverse(ContainerTy &&C)

bool isModSet(const ModRefInfo MRI)

void sort(IteratorTy Start, IteratorTy End)

FunctionAddr VTableAddr Count

bool isModOrRefSet(const ModRefInfo MRI)

class LLVM_GSL_OWNER SmallVector

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

bool isa(const From &Val)

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

AtomicOrdering

Atomic ordering for LLVM's memory model.

ModRefInfo

Flags indicating whether a memory access modifies or references memory.

@ Ref

The access may reference the value stored in memory.

@ ModRef

The access may reference and may modify the value stored in memory.

@ Mod

The access may modify the value stored in memory.

@ NoModRef

The access neither references nor modifies the value stored in memory.

LLVM_ABI Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)

If this if a call to a free function, return the freed operand.

decltype(auto) cast(const From &Val)

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)

This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....

bool isNoModRef(const ModRefInfo MRI)

bool isStrongerThan(AtomicOrdering AO, AtomicOrdering Other)

Returns true if ao is stronger than other as defined by the AtomicOrdering lattice,...

This struct is a compact representation of a valid (non-zero power of two) alignment.

A special type used by analysis passes to provide an address that identifies that particular analysis...