DeadStoreElimination.cpp Source File (original) (raw)

84#include

85#include

86#include

87#include

88#include

89#include

91using namespace llvm;

94#define DEBUG_TYPE "dse"

96 STATISTIC(NumRemainingStores, "Number of stores remaining after DSE");

97 STATISTIC(NumRedundantStores, "Number of redundant stores deleted");

98 STATISTIC(NumFastStores, "Number of stores deleted");

99 STATISTIC(NumFastOther, "Number of other instrs removed");

100 STATISTIC(NumCompletePartials, "Number of stores dead by later partials");

101 STATISTIC(NumModifiedStores, "Number of stores modified");

102 STATISTIC(NumCFGChecks, "Number of stores modified");

103 STATISTIC(NumCFGTries, "Number of stores modified");

104 STATISTIC(NumCFGSuccess, "Number of stores modified");

106 "Number of times a valid candidate is returned from getDomMemoryDef");

108 "Number iterations check for reads in getDomMemoryDef");

109

111 "Controls which MemoryDefs are eliminated.");

112

116 cl::desc("Enable partial-overwrite tracking in DSE"));

117

121 cl::desc("Enable partial store merging in DSE"));

122

125 cl::desc("The number of memory instructions to scan for "

126 "dead store elimination (default = 150)"));

129 cl::desc("The maximum number of steps while walking upwards to find "

130 "MemoryDefs that may be killed (default = 90)"));

131

134 cl::desc("The maximum number candidates that only partially overwrite the "

135 "killing MemoryDef to consider"

136 " (default = 5)"));

137

140 cl::desc("The number of MemoryDefs we consider as candidates to eliminated "

141 "other stores per basic block (default = 5000)"));

142

146 "The cost of a step in the same basic block as the killing MemoryDef"

147 "(default = 1)"));

148

152 cl::desc("The cost of a step in a different basic "

153 "block than the killing MemoryDef"

154 "(default = 5)"));

155

158 cl::desc("The maximum number of blocks to check when trying to prove that "

159 "all paths to an exit go through a killing block (default = 50)"));

160

161

162

163

164

165

166

169 cl::desc("Allow DSE to optimize memory accesses."));

170

171

173 "enable-dse-initializes-attr-improvement", cl::init(true), cl::Hidden,

174 cl::desc("Enable the initializes attr improvement in DSE"));

175

176

177

178

181

182

183

185

187 return false;

188

190 switch (II->getIntrinsicID()) {

191 default: return false;

192 case Intrinsic::memset:

193 case Intrinsic::memcpy:

194 case Intrinsic::memcpy_element_unordered_atomic:

195 case Intrinsic::memset_element_unordered_atomic:

196

197

198 return true;

199 }

200 }

201

202

203

204 return false;

205}

206

207

208

214

222

225 return std::nullopt;

226}

227

228namespace {

229

230enum OverwriteResult {

231 OW_Begin,

232 OW_Complete,

233 OW_End,

234 OW_PartialEarlierWithFullLater,

235 OW_MaybePartial,

236 OW_None,

237 OW_Unknown

238};

239

240}

241

242

243

244

250 if (KillingII == nullptr || DeadII == nullptr)

251 return OW_Unknown;

252 if (KillingII->getIntrinsicID() != DeadII->getIntrinsicID())

253 return OW_Unknown;

254

255 switch (KillingII->getIntrinsicID()) {

256 case Intrinsic::masked_store:

257 case Intrinsic::vp_store: {

258 const DataLayout &DL = KillingII->getDataLayout();

259 auto *KillingTy = KillingII->getArgOperand(0)->getType();

260 auto *DeadTy = DeadII->getArgOperand(0)->getType();

261 if (DL.getTypeSizeInBits(KillingTy) != DL.getTypeSizeInBits(DeadTy))

262 return OW_Unknown;

263

266 return OW_Unknown;

267

268 Value *KillingPtr = KillingII->getArgOperand(1);

269 Value *DeadPtr = DeadII->getArgOperand(1);

270 if (KillingPtr != DeadPtr && .isMustAlias(KillingPtr, DeadPtr))

271 return OW_Unknown;

272 if (KillingII->getIntrinsicID() == Intrinsic::masked_store) {

273

274

275 if (KillingII->getArgOperand(2) != DeadII->getArgOperand(2))

276 return OW_Unknown;

277 } else if (KillingII->getIntrinsicID() == Intrinsic::vp_store) {

278

279

280 if (KillingII->getArgOperand(2) != DeadII->getArgOperand(2))

281 return OW_Unknown;

282

283 if (KillingII->getArgOperand(3) != DeadII->getArgOperand(3))

284 return OW_Unknown;

285 }

286 return OW_Complete;

287 }

288 default:

289 return OW_Unknown;

290 }

291}

292

293

294

295

296

297

298

299

300

301

302

305 int64_t KillingOff, int64_t DeadOff,

310

311

312

313

314

316 KillingOff < int64_t(DeadOff + DeadSize) &&

317 int64_t(KillingOff + KillingSize) >= DeadOff) {

318

319

320 auto &IM = IOL[DeadI];

321 LLVM_DEBUG(dbgs() << "DSE: Partial overwrite: DeadLoc [" << DeadOff << ", "

322 << int64_t(DeadOff + DeadSize) << ") KillingLoc ["

323 << KillingOff << ", " << int64_t(KillingOff + KillingSize)

324 << ")\n");

325

326

327

328

329

330 int64_t KillingIntStart = KillingOff;

331 int64_t KillingIntEnd = KillingOff + KillingSize;

332

333

334

335 auto ILI = IM.lower_bound(KillingIntStart);

336 if (ILI != IM.end() && ILI->second <= KillingIntEnd) {

337

338

339

340 KillingIntStart = std::min(KillingIntStart, ILI->second);

341 KillingIntEnd = std::max(KillingIntEnd, ILI->first);

342 ILI = IM.erase(ILI);

343

344

345

346

347

348

349

350 while (ILI != IM.end() && ILI->second <= KillingIntEnd) {

351 assert(ILI->second > KillingIntStart && "Unexpected interval");

352 KillingIntEnd = std::max(KillingIntEnd, ILI->first);

353 ILI = IM.erase(ILI);

354 }

355 }

356

357 IM[KillingIntEnd] = KillingIntStart;

358

359 ILI = IM.begin();

360 if (ILI->second <= DeadOff && ILI->first >= int64_t(DeadOff + DeadSize)) {

361 LLVM_DEBUG(dbgs() << "DSE: Full overwrite from partials: DeadLoc ["

362 << DeadOff << ", " << int64_t(DeadOff + DeadSize)

363 << ") Composite KillingLoc [" << ILI->second << ", "

364 << ILI->first << ")\n");

365 ++NumCompletePartials;

366 return OW_Complete;

367 }

368 }

369

370

371

373 int64_t(DeadOff + DeadSize) > KillingOff &&

374 uint64_t(KillingOff - DeadOff) + KillingSize <= DeadSize) {

375 LLVM_DEBUG(dbgs() << "DSE: Partial overwrite a dead load [" << DeadOff

376 << ", " << int64_t(DeadOff + DeadSize)

377 << ") by a killing store [" << KillingOff << ", "

378 << int64_t(KillingOff + KillingSize) << ")\n");

379

380 return OW_PartialEarlierWithFullLater;

381 }

382

383

384

385

386

387

388

389

390

391

393 (KillingOff > DeadOff && KillingOff < int64_t(DeadOff + DeadSize) &&

394 int64_t(KillingOff + KillingSize) >= int64_t(DeadOff + DeadSize)))

395 return OW_End;

396

397

398

399

400

401

402

403

404

405

407 (KillingOff <= DeadOff && int64_t(KillingOff + KillingSize) > DeadOff)) {

408 assert(int64_t(KillingOff + KillingSize) < int64_t(DeadOff + DeadSize) &&

409 "Expect to be handled as OW_Complete");

410 return OW_Begin;

411 }

412

413 return OW_Unknown;

414}

415

416

417

418

419

420static bool

424

425

426

427

428

429 using BlockAddressPair = std::pair<BasicBlock *, PHITransAddr>;

431

432

434

436 ++FirstBBI;

443 else

445

446 auto *MemLocPtr = const_cast<Value *>(MemLoc.Ptr);

447

448

450 std::make_pair(SecondBB, PHITransAddr(MemLocPtr, DL, nullptr)));

451 bool isFirstBlock = true;

452

453

454 while (!WorkList.empty()) {

455 BlockAddressPair Current = WorkList.pop_back_val();

459

460

462

464 if (isFirstBlock) {

465

466 assert(B == SecondBB && "first block is not the store block");

467 EI = SecondBBI;

468 isFirstBlock = false;

469 } else {

470

471

472 EI = B->end();

473 }

474 for (; BI != EI; ++BI) {

476 if (I->mayWriteToMemory() && I != SecondI)

478 return false;

479 }

480 if (B != FirstBB) {

482 "Should not hit the entry block because SI must be dominated by LI");

487 return false;

489 return false;

490 }

492 auto Inserted = Visited.insert(std::make_pair(Pred, TranslatedPtr));

493 if (!Inserted.second) {

494

495

496 if (TranslatedPtr != Inserted.first->second)

497 return false;

498

499 continue;

500 }

501 WorkList.push_back(std::make_pair(Pred, PredAddr));

502 }

503 }

504 }

505 return true;

506}

507

510 uint64_t NewSizeInBits, bool IsOverwriteEnd) {

512 uint64_t DeadSliceSizeInBits = OldSizeInBits - NewSizeInBits;

513 uint64_t DeadSliceOffsetInBits =

514 OldOffsetInBits + (IsOverwriteEnd ? NewSizeInBits : 0);

515 auto SetDeadFragExpr = [](auto *Assign,

517

518

519 uint64_t RelativeOffset = DeadFragment.OffsetInBits -

520 Assign->getExpression()

521 ->getFragmentInfo()

523 .OffsetInBits;

525 Assign->getExpression(), RelativeOffset, DeadFragment.SizeInBits)) {

526 Assign->setExpression(*NewExpr);

527 return;

528 }

529

530

532 DIExpression::get(Assign->getContext(), {}), DeadFragment.OffsetInBits,

533 DeadFragment.SizeInBits);

534 Assign->setExpression(Expr);

535 Assign->setKillLocation();

536 };

537

538

539

542 auto GetDeadLink = [&Ctx, &LinkToNothing]() {

543 if (!LinkToNothing)

545 return LinkToNothing;

546 };

547

548

549

551 std::optionalDIExpression::FragmentInfo NewFragment;

553 DeadSliceSizeInBits, Assign,

554 NewFragment) ||

555 !NewFragment) {

556

557

558 Assign->setKillAddress();

559 Assign->setAssignId(GetDeadLink());

560 continue;

561 }

562

563 if (NewFragment->SizeInBits == 0)

564 continue;

565

566

567 auto *NewAssign = static_cast<decltype(Assign)>(Assign->clone());

568 NewAssign->insertAfter(Assign->getIterator());

569 NewAssign->setAssignId(GetDeadLink());

570 if (NewFragment)

571 SetDeadFragExpr(NewAssign, *NewFragment);

572 NewAssign->setKillAddress();

573 }

574}

575

576

577

578

581

583

584

586 for (auto &Attr : OldAttrs) {

587 if (Attr.hasKindAsEnum()) {

588 switch (Attr.getKindAsEnum()) {

589 default:

590 break;

591 case Attribute::Alignment:

592

593 if (isAligned(Attr.getAlignment().valueOrOne(), PtrOffset))

594 continue;

595 break;

596 case Attribute::Dereferenceable:

597 case Attribute::DereferenceableOrNull:

598

599

600 break;

601 case Attribute::NonNull:

602 case Attribute::NoUndef:

603 continue;

604 }

605 }

607 }

608

609

610 Intrinsic->removeParamAttrs(ArgNo, AttrsToRemove);

611}

612

614 uint64_t &DeadSize, int64_t KillingStart,

615 uint64_t KillingSize, bool IsOverwriteEnd) {

617 Align PrefAlign = DeadIntrinsic->getDestAlign().valueOrOne();

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633 int64_t ToRemoveStart = 0;

635

636

637 if (IsOverwriteEnd) {

638

639

642 ToRemoveStart = KillingStart + Off;

643 if (DeadSize <= uint64_t(ToRemoveStart - DeadStart))

644 return false;

645 ToRemoveSize = DeadSize - uint64_t(ToRemoveStart - DeadStart);

646 } else {

647 ToRemoveStart = DeadStart;

648 assert(KillingSize >= uint64_t(DeadStart - KillingStart) &&

649 "Not overlapping accesses?");

650 ToRemoveSize = KillingSize - uint64_t(DeadStart - KillingStart);

651

652

654 if (Off != 0) {

655 if (ToRemoveSize <= (PrefAlign.value() - Off))

656 return false;

657 ToRemoveSize -= PrefAlign.value() - Off;

658 }

660 "Should preserve selected alignment");

661 }

662

663 assert(ToRemoveSize > 0 && "Shouldn't reach here if nothing to remove");

664 assert(DeadSize > ToRemoveSize && "Can't remove more than original size");

665

666 uint64_t NewSize = DeadSize - ToRemoveSize;

667 if (DeadIntrinsic->isAtomic()) {

668

669

670 const uint32_t ElementSize = DeadIntrinsic->getElementSizeInBytes();

671 if (0 != NewSize % ElementSize)

672 return false;

673 }

674

676 << (IsOverwriteEnd ? "END" : "BEGIN") << ": " << *DeadI

677 << "\n KILLER [" << ToRemoveStart << ", "

678 << int64_t(ToRemoveStart + ToRemoveSize) << ")\n");

679

680 DeadIntrinsic->setLength(NewSize);

681 DeadIntrinsic->setDestAlignment(PrefAlign);

682

683 Value *OrigDest = DeadIntrinsic->getRawDest();

684 if (!IsOverwriteEnd) {

685 Value *Indices[1] = {

686 ConstantInt::get(DeadIntrinsic->getLength()->getType(), ToRemoveSize)};

688 Type::getInt8Ty(DeadIntrinsic->getContext()), OrigDest, Indices, "",

690 NewDestGEP->setDebugLoc(DeadIntrinsic->getDebugLoc());

691 DeadIntrinsic->setDest(NewDestGEP);

693 }

694

695

696 shortenAssignment(DeadI, OrigDest, DeadStart * 8, DeadSize * 8, NewSize * 8,

697 IsOverwriteEnd);

698

699

700 if (!IsOverwriteEnd)

701 DeadStart += ToRemoveSize;

702 DeadSize = NewSize;

703

704 return true;

705}

706

708 int64_t &DeadStart, uint64_t &DeadSize) {

710 return false;

711

712 OverlapIntervalsTy::iterator OII = --IntervalMap.end();

713 int64_t KillingStart = OII->second;

714 uint64_t KillingSize = OII->first - KillingStart;

715

716 assert(OII->first - KillingStart >= 0 && "Size expected to be positive");

717

718 if (KillingStart > DeadStart &&

719

720

721 (uint64_t)(KillingStart - DeadStart) < DeadSize &&

722

723

724 KillingSize >= DeadSize - (uint64_t)(KillingStart - DeadStart)) {

725 if (tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,

726 true)) {

728 return true;

729 }

730 }

731 return false;

732}

733

736 int64_t &DeadStart, uint64_t &DeadSize) {

738 return false;

739

741 int64_t KillingStart = OII->second;

742 uint64_t KillingSize = OII->first - KillingStart;

743

744 assert(OII->first - KillingStart >= 0 && "Size expected to be positive");

745

746 if (KillingStart <= DeadStart &&

747

748

749 KillingSize > (uint64_t)(DeadStart - KillingStart)) {

750

751

752 assert(KillingSize - (uint64_t)(DeadStart - KillingStart) < DeadSize &&

753 "Should have been handled as OW_Complete");

754 if (tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,

755 false)) {

757 return true;

758 }

759 }

760 return false;

761}

762

765 int64_t KillingOffset, int64_t DeadOffset,

768

774

775

776

777

778

779

780

781

782

783

785 APInt KillingValue =

787 unsigned KillingBits = KillingValue.getBitWidth();

789 KillingValue = KillingValue.zext(DeadValue.getBitWidth());

790

791

792 unsigned BitOffsetDiff = (KillingOffset - DeadOffset) * 8;

793 unsigned LShiftAmount =

794 DL.isBigEndian() ? DeadValue.getBitWidth() - BitOffsetDiff - KillingBits

795 : BitOffsetDiff;

797 LShiftAmount + KillingBits);

798

799

800 APInt Merged = (DeadValue & ~Mask) | (KillingValue << LShiftAmount);

801 LLVM_DEBUG(dbgs() << "DSE: Merge Stores:\n Dead: " << *DeadI

802 << "\n Killing: " << *KillingI

803 << "\n Merged Value: " << Merged << '\n');

805 }

806 return nullptr;

807}

808

809

812 switch (II->getIntrinsicID()) {

813 case Intrinsic::lifetime_start:

814 case Intrinsic::lifetime_end:

815 case Intrinsic::invariant_end:

816 case Intrinsic::launder_invariant_group:

817 case Intrinsic::assume:

818 return true;

819 case Intrinsic::dbg_declare:

820 case Intrinsic::dbg_label:

821 case Intrinsic::dbg_value:

822 llvm_unreachable("Intrinsic should not be modeled in MemorySSA");

823 default:

824 return false;

825 }

826 }

827 return false;

828}

829

830

833

834

836 if (CB->onlyAccessesInaccessibleMemory())

837 return true;

838

839

840

841 if (DI->mayThrow() && !DefVisibleToCaller)

842 return true;

843

844

845

846

847

848

850 return true;

851

852

854 return true;

855

856 return false;

857}

858

859namespace {

860

861

862

863struct MemoryLocationWrapper {

864 MemoryLocationWrapper(MemoryLocation MemLoc, MemoryDef *MemDef,

865 bool DefByInitializesAttr)

866 : MemLoc(MemLoc), MemDef(MemDef),

867 DefByInitializesAttr(DefByInitializesAttr) {

868 assert(MemLoc.Ptr && "MemLoc should be not null");

870 DefInst = MemDef->getMemoryInst();

871 }

872

873 MemoryLocation MemLoc;

874 const Value *UnderlyingObject;

875 MemoryDef *MemDef;

877 bool DefByInitializesAttr = false;

878};

879

880

881

882struct MemoryDefWrapper {

883 MemoryDefWrapper(MemoryDef *MemDef,

884 ArrayRef<std::pair<MemoryLocation, bool>> MemLocations) {

886 for (auto &[MemLoc, DefByInitializesAttr] : MemLocations)

887 DefinedLocations.push_back(

888 MemoryLocationWrapper(MemLoc, MemDef, DefByInitializesAttr));

889 }

892};

893

894struct ArgumentInitInfo {

895 unsigned Idx;

896 bool IsDeadOrInvisibleOnUnwind;

897 ConstantRangeList Inits;

898};

899}

900

905

906

907

908

909

912 bool CallHasNoUnwindAttr) {

913 if (Args.empty())

914 return {};

915

916

917

918 for (const auto &Arg : Args) {

919 if (!CallHasNoUnwindAttr && !Arg.IsDeadOrInvisibleOnUnwind)

920 return {};

921 if (Arg.Inits.empty())

922 return {};

923 }

924

926 for (auto &Arg : Args.drop_front())

927 IntersectedIntervals = IntersectedIntervals.intersectWith(Arg.Inits);

928

929 return IntersectedIntervals;

930}

931

932namespace {

933

934struct DSEState {

937 EarliestEscapeAnalysis EA;

938

939

940

941

942

943

944

945

946 BatchAAResults BatchAA;

947

949 DominatorTree &DT;

950 PostDominatorTree &PDT;

951 const TargetLibraryInfo &TLI;

952 const DataLayout &DL;

953 const LoopInfo &LI;

954

955

956

957 bool ContainsIrreducibleLoops;

958

959

961

962 SmallPtrSet<MemoryAccess *, 4> SkipStores;

963

964 DenseMap<const Value *, bool> CapturedBeforeReturn;

965

966

967 DenseMap<const Value *, bool> InvisibleToCallerAfterRet;

968

969 SmallPtrSet<BasicBlock *, 16> ThrowingBlocks;

970

971

972 DenseMap<BasicBlock *, unsigned> PostOrderNumbers;

973

974

975

976 MapVector<BasicBlock *, InstOverlapIntervalsTy> IOLs;

977

978

979

980 bool AnyUnreachableExit;

981

982

983

984

985 bool ShouldIterateEndOfFunctionDSE;

986

987

989

990

991 DSEState(const DSEState &) = delete;

992 DSEState &operator=(const DSEState &) = delete;

993

995 PostDominatorTree &PDT, const TargetLibraryInfo &TLI,

996 const LoopInfo &LI)

997 : F(F), AA(AA), EA(DT, &LI), BatchAA(AA, &EA), MSSA(MSSA), DT(DT),

998 PDT(PDT), TLI(TLI), DL(F.getDataLayout()), LI(LI) {

999

1000

1001 unsigned PO = 0;

1002 for (BasicBlock *BB : post_order(&F)) {

1003 PostOrderNumbers[BB] = PO++;

1004 for (Instruction &I : *BB) {

1005 MemoryAccess *MA = MSSA.getMemoryAccess(&I);

1006 if (I.mayThrow() && !MA)

1007 ThrowingBlocks.insert(I.getParent());

1008

1011 (getLocForWrite(&I) || isMemTerminatorInst(&I) ||

1013 MemDefs.push_back(MD);

1014 }

1015 }

1016

1017

1018

1019 for (Argument &AI : F.args())

1020 if (AI.hasPassPointeeByValueCopyAttr() || AI.hasDeadOnReturnAttr())

1021 InvisibleToCallerAfterRet.insert({&AI, true});

1022

1023

1025

1026 AnyUnreachableExit = any_of(PDT.roots(), [](const BasicBlock *E) {

1027 return isa(E->getTerminator());

1028 });

1029 }

1030

1031 static void pushMemUses(MemoryAccess *Acc,

1032 SmallVectorImpl<MemoryAccess *> &WorkList,

1033 SmallPtrSetImpl<MemoryAccess *> &Visited) {

1034 for (Use &U : Acc->uses()) {

1036 if (Visited.insert(MA).second)

1038 }

1039 };

1040

1041 LocationSize strengthenLocationSize(const Instruction *I,

1042 LocationSize Size) const {

1044 LibFunc F;

1045 if (TLI.getLibFunc(*CB, F) && TLI.has(F) &&

1046 (F == LibFunc_memset_chk || F == LibFunc_memcpy_chk)) {

1047

1048

1049

1050

1051

1052

1053

1054

1057 }

1058 }

1059 return Size;

1060 }

1061

1062

1063

1064

1065

1066

1067

1068

1069

1070 OverwriteResult isOverwrite(const Instruction *KillingI,

1071 const Instruction *DeadI,

1072 const MemoryLocation &KillingLoc,

1073 const MemoryLocation &DeadLoc,

1074 int64_t &KillingOff, int64_t &DeadOff) {

1075

1076

1077

1078 if (!isGuaranteedLoopIndependent(DeadI, KillingI, DeadLoc))

1079 return OW_Unknown;

1080

1081 LocationSize KillingLocSize =

1082 strengthenLocationSize(KillingI, KillingLoc.Size);

1087

1088

1089

1090 if (DeadUndObj == KillingUndObj && KillingLocSize.isPrecise() &&

1092 std::optional KillingUndObjSize =

1094 if (KillingUndObjSize && *KillingUndObjSize == KillingLocSize.getValue())

1095 return OW_Complete;

1096 }

1097

1098

1099

1101

1102

1105 if (KillingMemI && DeadMemI) {

1106 const Value *KillingV = KillingMemI->getLength();

1107 const Value *DeadV = DeadMemI->getLength();

1108 if (KillingV == DeadV && BatchAA.isMustAlias(DeadLoc, KillingLoc))

1109 return OW_Complete;

1110 }

1111

1112

1113

1115 }

1116

1117 const TypeSize KillingSize = KillingLocSize.getValue();

1118 const TypeSize DeadSize = DeadLoc.Size.getValue();

1119

1120

1121 const bool AnyScalable =

1123

1124 if (AnyScalable)

1125 return OW_Unknown;

1126

1127 AliasResult AAR = BatchAA.alias(KillingLoc, DeadLoc);

1128

1129

1130

1132

1133 if (KillingSize >= DeadSize)

1134 return OW_Complete;

1135 }

1136

1137

1140 if (Off >= 0 && (uint64_t)Off + DeadSize <= KillingSize)

1141 return OW_Complete;

1142 }

1143

1144

1145

1146 if (DeadUndObj != KillingUndObj) {

1147

1148

1149

1150

1151

1153 return OW_None;

1154 return OW_Unknown;

1155 }

1156

1157

1158

1159

1160 DeadOff = 0;

1161 KillingOff = 0;

1162 const Value *DeadBasePtr =

1164 const Value *KillingBasePtr =

1166

1167

1168

1169 if (DeadBasePtr != KillingBasePtr)

1170 return OW_Unknown;

1171

1172

1173

1174

1175

1176

1177

1178

1179

1180

1181

1182

1183

1184

1185

1186

1187 if (DeadOff >= KillingOff) {

1188

1189

1190 if (uint64_t(DeadOff - KillingOff) + DeadSize <= KillingSize)

1191 return OW_Complete;

1192

1193

1194 else if ((uint64_t)(DeadOff - KillingOff) < KillingSize)

1195 return OW_MaybePartial;

1196 }

1197

1198

1199 else if ((uint64_t)(KillingOff - DeadOff) < DeadSize) {

1200 return OW_MaybePartial;

1201 }

1202

1203

1204 return OW_None;

1205 }

1206

1207 bool isInvisibleToCallerAfterRet(const Value *V) {

1209 return true;

1210

1211 auto I = InvisibleToCallerAfterRet.insert({V, false});

1212 if (I.second && isInvisibleToCallerOnUnwind(V) && isNoAliasCall(V))

1214 V, true, CaptureComponents::Provenance));

1215 return I.first->second;

1216 }

1217

1218 bool isInvisibleToCallerOnUnwind(const Value *V) {

1219 bool RequiresNoCaptureBeforeUnwind;

1221 return false;

1222 if (!RequiresNoCaptureBeforeUnwind)

1223 return true;

1224

1225 auto I = CapturedBeforeReturn.insert({V, true});

1226 if (I.second)

1227

1228

1229

1230

1232 V, false, CaptureComponents::Provenance));

1233 return .first->second;

1234 }

1235

1236 std::optional getLocForWrite(Instruction *I) const {

1237 if (->mayWriteToMemory())

1238 return std::nullopt;

1239

1242

1244 }

1245

1246

1247

1249 getLocForInst(Instruction *I, bool ConsiderInitializesAttr) {

1251 if (isMemTerminatorInst(I)) {

1252 if (auto Loc = getLocForTerminator(I))

1253 Locations.push_back(std::make_pair(Loc->first, false));

1255 }

1256

1257 if (auto Loc = getLocForWrite(I))

1258 Locations.push_back(std::make_pair(*Loc, false));

1259

1260 if (ConsiderInitializesAttr) {

1261 for (auto &MemLoc : getInitializesArgMemLoc(I)) {

1262 Locations.push_back(std::make_pair(MemLoc, true));

1263 }

1264 }

1266 }

1267

1268

1269

1270 bool isRemovable(Instruction *I) {

1271 assert(getLocForWrite(I) && "Must have analyzable write");

1272

1273

1275 return SI->isUnordered();

1276

1278

1280 return ->isVolatile();

1281

1282

1283

1284 if (CB->isLifetimeStartOrEnd())

1285 return false;

1286

1287 return CB->use_empty() && CB->willReturn() && CB->doesNotThrow() &&

1288 !CB->isTerminator();

1289 }

1290

1291 return false;

1292 }

1293

1294

1295

1296 bool isCompleteOverwrite(const MemoryLocation &DefLoc, Instruction *DefInst,

1297 Instruction *UseInst) {

1298

1299

1300

1302 return false;

1303

1305 if (CB->onlyAccessesInaccessibleMemory())

1306 return false;

1307

1308 int64_t InstWriteOffset, DepWriteOffset;

1309 if (auto CC = getLocForWrite(UseInst))

1310 return isOverwrite(UseInst, DefInst, *CC, DefLoc, InstWriteOffset,

1311 DepWriteOffset) == OW_Complete;

1312 return false;

1313 }

1314

1315

1316 bool isWriteAtEndOfFunction(MemoryDef *Def, const MemoryLocation &DefLoc) {

1317 LLVM_DEBUG(dbgs() << " Check if def " << *Def << " ("

1318 << *Def->getMemoryInst()

1319 << ") is at the end the function \n");

1321 SmallPtrSet<MemoryAccess *, 8> Visited;

1322

1323 pushMemUses(Def, WorkList, Visited);

1324 for (unsigned I = 0; I < WorkList.size(); I++) {

1326 LLVM_DEBUG(dbgs() << " ... hit exploration limit.\n");

1327 return false;

1328 }

1329

1330 MemoryAccess *UseAccess = WorkList[I];

1332

1333

1334

1335 if (!isGuaranteedLoopInvariant(DefLoc.Ptr))

1336 return false;

1337

1338 pushMemUses(cast(UseAccess), WorkList, Visited);

1339 continue;

1340 }

1341

1342

1344 if (isReadClobber(DefLoc, UseInst)) {

1345 LLVM_DEBUG(dbgs() << " ... hit read clobber " << *UseInst << ".\n");

1346 return false;

1347 }

1348

1350 pushMemUses(UseDef, WorkList, Visited);

1351 }

1352 return true;

1353 }

1354

1355

1356

1357

1358 std::optional<std::pair<MemoryLocation, bool>>

1359 getLocForTerminator(Instruction *I) const {

1361 if (CB->getIntrinsicID() == Intrinsic::lifetime_end)

1362 return {

1366 }

1367

1368 return std::nullopt;

1369 }

1370

1371

1372

1373 bool isMemTerminatorInst(Instruction *I) const {

1375 return CB && (CB->getIntrinsicID() == Intrinsic::lifetime_end ||

1377 }

1378

1379

1380

1381 bool isMemTerminator(const MemoryLocation &Loc, Instruction *AccessI,

1382 Instruction *MaybeTerm) {

1383 std::optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =

1384 getLocForTerminator(MaybeTerm);

1385

1386 if (!MaybeTermLoc)

1387 return false;

1388

1389

1390

1393 return false;

1394

1395 auto TermLoc = MaybeTermLoc->first;

1396 if (MaybeTermLoc->second) {

1398 return BatchAA.isMustAlias(TermLoc.Ptr, LocUO);

1399 }

1400 int64_t InstWriteOffset = 0;

1401 int64_t DepWriteOffset = 0;

1402 return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, InstWriteOffset,

1403 DepWriteOffset) == OW_Complete;

1404 }

1405

1406

1407 bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {

1409 return false;

1410

1411

1412

1414 return isStrongerThan(SI->getOrdering(), AtomicOrdering::Monotonic);

1415

1417 return false;

1418

1420 if (CB->onlyAccessesInaccessibleMemory())

1421 return false;

1422

1423 return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc));

1424 }

1425

1426

1427

1428

1429

1430

1431 bool isGuaranteedLoopIndependent(const Instruction *Current,

1432 const Instruction *KillingDef,

1433 const MemoryLocation &CurrentLoc) {

1434

1435

1436

1437

1439 return true;

1440 const Loop *CurrentLI = LI.getLoopFor(Current->getParent());

1441 if (!ContainsIrreducibleLoops && CurrentLI &&

1442 CurrentLI == LI.getLoopFor(KillingDef->getParent()))

1443 return true;

1444

1445 return isGuaranteedLoopInvariant(CurrentLoc.Ptr);

1446 }

1447

1448

1449

1450

1451 bool isGuaranteedLoopInvariant(const Value *Ptr) {

1454 if (GEP->hasAllConstantIndices())

1456

1458 return I->getParent()->isEntryBlock() ||

1459 (!ContainsIrreducibleLoops && !LI.getLoopFor(I->getParent()));

1460 }

1461 return true;

1462 }

1463

1464

1465

1466

1467

1468

1469

1470 std::optional<MemoryAccess *>

1471 getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *StartAccess,

1472 const MemoryLocation &KillingLoc, const Value *KillingUndObj,

1473 unsigned &ScanLimit, unsigned &WalkerStepLimit,

1474 bool IsMemTerm, unsigned &PartialLimit,

1475 bool IsInitializesAttrMemLoc) {

1476 if (ScanLimit == 0 || WalkerStepLimit == 0) {

1478 return std::nullopt;

1479 }

1480

1481 MemoryAccess *Current = StartAccess;

1483 LLVM_DEBUG(dbgs() << " trying to get dominating access\n");

1484

1485

1486

1487

1488

1489

1493

1494

1495 std::optional CurrentLoc;

1496 for (;; Current = cast(Current)->getDefiningAccess()) {

1498 dbgs() << " visiting " << *Current;

1501 << ")";

1502 dbgs() << "\n";

1503 });

1504

1505

1506 if (MSSA.isLiveOnEntryDef(Current)) {

1507 LLVM_DEBUG(dbgs() << " ... found LiveOnEntryDef\n");

1509

1511 return std::nullopt;

1512 }

1513

1514

1515

1516 unsigned StepCost = KillingDef->getBlock() == Current->getBlock()

1519 if (WalkerStepLimit <= StepCost) {

1520 LLVM_DEBUG(dbgs() << " ... hit walker step limit\n");

1521 return std::nullopt;

1522 }

1523 WalkerStepLimit -= StepCost;

1524

1525

1526

1529 return Current;

1530 }

1531

1532

1533

1536

1537 if (canSkipDef(CurrentDef, !isInvisibleToCallerOnUnwind(KillingUndObj))) {

1538 CanOptimize = false;

1539 continue;

1540 }

1541

1542

1543

1544 if (mayThrowBetween(KillingI, CurrentI, KillingUndObj)) {

1546 return std::nullopt;

1547 }

1548

1549

1550

1551 if (isDSEBarrier(KillingUndObj, CurrentI)) {

1553 return std::nullopt;

1554 }

1555

1556

1557

1558

1559

1560 if ( isa<IntrinsicInst> (CurrentI) && isReadClobber(KillingLoc, CurrentI))

1561 return std::nullopt;

1562

1563

1564 if (any_of(Current->uses(), [this, &KillingLoc, StartAccess](Use &U) {

1565 if (auto *UseOrDef = dyn_cast(U.getUser()))

1566 return !MSSA.dominates(StartAccess, UseOrDef) &&

1567 isReadClobber(KillingLoc, UseOrDef->getMemoryInst());

1568 return false;

1569 })) {

1570 LLVM_DEBUG(dbgs() << " ... found a read clobber\n");

1571 return std::nullopt;

1572 }

1573

1574

1575

1576 CurrentLoc = getLocForWrite(CurrentI);

1577 if (!CurrentLoc || !isRemovable(CurrentI)) {

1578 CanOptimize = false;

1579 continue;

1580 }

1581

1582

1583

1584

1585 if (!isGuaranteedLoopIndependent(CurrentI, KillingI, *CurrentLoc)) {

1586 LLVM_DEBUG(dbgs() << " ... not guaranteed loop independent\n");

1587 CanOptimize = false;

1588 continue;

1589 }

1590

1591 if (IsMemTerm) {

1592

1593

1594

1595 if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {

1596 CanOptimize = false;

1597 continue;

1598 }

1599 } else {

1600 int64_t KillingOffset = 0;

1601 int64_t DeadOffset = 0;

1602 auto OR = isOverwrite(KillingI, CurrentI, KillingLoc, *CurrentLoc,

1603 KillingOffset, DeadOffset);

1604 if (CanOptimize) {

1605

1606

1607

1609 (OR == OW_Complete || OR == OW_MaybePartial))

1611

1612

1613

1614 if (OR != OW_None)

1615 CanOptimize = false;

1616 }

1617

1618

1619

1620 if (OR == OW_Unknown || OR == OW_None)

1621 continue;

1622 else if (OR == OW_MaybePartial) {

1623

1624

1625

1626

1627 if (PartialLimit <= 1) {

1628 WalkerStepLimit -= 1;

1629 LLVM_DEBUG(dbgs() << " ... reached partial limit ... continue with next access\n");

1630 continue;

1631 }

1632 PartialLimit -= 1;

1633 }

1634 }

1635 break;

1636 };

1637

1638

1639

1640

1641

1642 SmallPtrSet<Instruction *, 16> KillingDefs;

1644 MemoryAccess *MaybeDeadAccess = Current;

1645 MemoryLocation MaybeDeadLoc = *CurrentLoc;

1647 LLVM_DEBUG(dbgs() << " Checking for reads of " << *MaybeDeadAccess << " ("

1648 << *MaybeDeadI << ")\n");

1649

1651 SmallPtrSet<MemoryAccess *, 32> Visited;

1652 pushMemUses(MaybeDeadAccess, WorkList, Visited);

1653

1654

1655 for (unsigned I = 0; I < WorkList.size(); I++) {

1656 MemoryAccess *UseAccess = WorkList[I];

1657

1659

1660 if (ScanLimit < (WorkList.size() - I)) {

1662 return std::nullopt;

1663 }

1664 --ScanLimit;

1665 NumDomMemDefChecks++;

1666

1668 if (any_of(KillingDefs, [this, UseAccess](Instruction *KI) {

1669 return DT.properlyDominates(KI->getParent(),

1671 })) {

1672 LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing block\n");

1673 continue;

1674 }

1676 pushMemUses(UseAccess, WorkList, Visited);

1677 continue;

1678 }

1679

1682

1683 if (any_of(KillingDefs, [this, UseInst](Instruction *KI) {

1684 return DT.dominates(KI, UseInst);

1685 })) {

1686 LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing def\n");

1687 continue;

1688 }

1689

1690

1691

1692 if (isMemTerminator(MaybeDeadLoc, MaybeDeadI, UseInst)) {

1695 << " ... skipping, memterminator invalidates following accesses\n");

1696 continue;

1697 }

1698

1700 LLVM_DEBUG(dbgs() << " ... adding uses of intrinsic\n");

1701 pushMemUses(UseAccess, WorkList, Visited);

1702 continue;

1703 }

1704

1705 if (UseInst->mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj)) {

1706 LLVM_DEBUG(dbgs() << " ... found throwing instruction\n");

1707 return std::nullopt;

1708 }

1709

1710

1711

1712

1713

1714 bool IsKillingDefFromInitAttr = false;

1715 if (IsInitializesAttrMemLoc) {

1716 if (KillingI == UseInst &&

1718 IsKillingDefFromInitAttr = true;

1719 }

1720

1721 if (isReadClobber(MaybeDeadLoc, UseInst) && !IsKillingDefFromInitAttr) {

1723 return std::nullopt;

1724 }

1725

1726

1727

1728

1729 if (MaybeDeadAccess == UseAccess &&

1730 !isGuaranteedLoopInvariant(MaybeDeadLoc.Ptr)) {

1731 LLVM_DEBUG(dbgs() << " ... found not loop invariant self access\n");

1732 return std::nullopt;

1733 }

1734

1735

1736

1737

1738 if (KillingDef == UseAccess || MaybeDeadAccess == UseAccess) {

1739 LLVM_DEBUG(dbgs() << " ... skipping killing def/dom access\n");

1740 continue;

1741 }

1742

1743

1744

1745

1746

1747

1748

1749

1750

1751

1752

1754 if (isCompleteOverwrite(MaybeDeadLoc, MaybeDeadI, UseInst)) {

1756 if (PostOrderNumbers.find(MaybeKillingBlock)->second <

1757 PostOrderNumbers.find(MaybeDeadAccess->getBlock())->second) {

1758 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {

1760 << " ... found killing def " << *UseInst << "\n");

1761 KillingDefs.insert(UseInst);

1762 }

1763 } else {

1765 << " ... found preceeding def " << *UseInst << "\n");

1766 return std::nullopt;

1767 }

1768 } else

1769 pushMemUses(UseDef, WorkList, Visited);

1770 }

1771 }

1772

1773

1774

1775

1776 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {

1777 SmallPtrSet<BasicBlock *, 16> KillingBlocks;

1778 for (Instruction *KD : KillingDefs)

1779 KillingBlocks.insert(KD->getParent());

1781 "Expected at least a single killing block");

1782

1783

1786 if (!CommonPred)

1787 break;

1788 CommonPred = PDT.findNearestCommonDominator(CommonPred, BB);

1789 }

1790

1791

1792

1793

1794 if (!PDT.dominates(CommonPred, MaybeDeadAccess->getBlock())) {

1795 if (!AnyUnreachableExit)

1796 return std::nullopt;

1797

1798

1799

1800 CommonPred = nullptr;

1801 }

1802

1803

1804 if (KillingBlocks.count(CommonPred))

1805 return {MaybeDeadAccess};

1806

1807 SetVector<BasicBlock *> WorkList;

1808

1809

1810 if (CommonPred)

1811 WorkList.insert(CommonPred);

1812 else

1813 for (BasicBlock *R : PDT.roots()) {

1816 }

1817

1818 NumCFGTries++;

1819

1820

1821 for (unsigned I = 0; I < WorkList.size(); I++) {

1822 NumCFGChecks++;

1824 if (KillingBlocks.count(Current))

1825 continue;

1826 if (Current == MaybeDeadAccess->getBlock())

1827 return std::nullopt;

1828

1829

1830

1831 if (!DT.isReachableFromEntry(Current))

1832 continue;

1833

1835

1837 return std::nullopt;

1838 }

1839 NumCFGSuccess++;

1840 }

1841

1842

1843

1844 return {MaybeDeadAccess};

1845 }

1846

1847

1848

1849 void

1851 SmallPtrSetImpl<MemoryAccess *> *Deleted = nullptr) {

1852 MemorySSAUpdater Updater(&MSSA);

1855 --NumFastOther;

1856

1857 while (!NowDeadInsts.empty()) {

1859 ++NumFastOther;

1860

1861

1864

1865

1866 MemoryAccess *MA = MSSA.getMemoryAccess(DeadInst);

1868 if (MA) {

1869 if (IsMemDef) {

1871 SkipStores.insert(MD);

1875 if (SI->getValueOperand()->getType()->isPointerTy()) {

1877 if (CapturedBeforeReturn.erase(UO))

1878 ShouldIterateEndOfFunctionDSE = true;

1879 InvisibleToCallerAfterRet.erase(UO);

1880 }

1881 }

1882 }

1883

1884 Updater.removeMemoryAccess(MA);

1885 }

1886

1887 auto I = IOLs.find(DeadInst->getParent());

1888 if (I != IOLs.end())

1889 I->second.erase(DeadInst);

1890

1891 for (Use &O : DeadInst->operands())

1896 }

1897

1898 EA.removeInstruction(DeadInst);

1899

1900

1901

1902

1903

1906 else

1907 ToRemove.push_back(DeadInst);

1908 }

1909 }

1910

1911

1912

1913

1914

1915 bool mayThrowBetween(Instruction *KillingI, Instruction *DeadI,

1916 const Value *KillingUndObj) {

1917

1918

1919

1920 if (KillingUndObj && isInvisibleToCallerOnUnwind(KillingUndObj))

1921 return false;

1922

1924 return ThrowingBlocks.count(KillingI->getParent());

1925 return !ThrowingBlocks.empty();

1926 }

1927

1928

1929

1930

1931

1932

1933 bool isDSEBarrier(const Value *KillingUndObj, Instruction *DeadI) {

1934

1935

1936 if (DeadI->mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj))

1937 return true;

1938

1939

1940

1951 llvm_unreachable("other instructions should be skipped in MemorySSA");

1952 }

1953 return false;

1954 }

1955

1956

1957

1958 bool eliminateDeadWritesAtEndOfFunction() {

1959 bool MadeChange = false;

1962 << "Trying to eliminate MemoryDefs at the end of the function\n");

1963 do {

1964 ShouldIterateEndOfFunctionDSE = false;

1966 if (SkipStores.contains(Def))

1967 continue;

1968

1970 auto DefLoc = getLocForWrite(DefI);

1971 if (!DefLoc || !isRemovable(DefI)) {

1972 LLVM_DEBUG(dbgs() << " ... could not get location for write or "

1973 "instruction not removable.\n");

1974 continue;

1975 }

1976

1977

1978

1979

1980

1981

1983 if (!isInvisibleToCallerAfterRet(UO))

1984 continue;

1985

1986 if (isWriteAtEndOfFunction(Def, *DefLoc)) {

1987

1988 LLVM_DEBUG(dbgs() << " ... MemoryDef is not accessed until the end "

1989 "of the function\n");

1991 ++NumFastStores;

1992 MadeChange = true;

1993 }

1994 }

1995 } while (ShouldIterateEndOfFunctionDSE);

1996 return MadeChange;

1997 }

1998

1999

2000

2001 bool tryFoldIntoCalloc(MemoryDef *Def, const Value *DefUO) {

2004 if (!MemSet)

2005

2006 return false;

2008 if (!StoredConstant || !StoredConstant->isNullValue())

2009 return false;

2010

2011 if (!isRemovable(DefI))

2012

2013 return false;

2014

2015 if (F.hasFnAttribute(Attribute::SanitizeMemory) ||

2016 F.hasFnAttribute(Attribute::SanitizeAddress) ||

2017 F.hasFnAttribute(Attribute::SanitizeHWAddress) ||

2018 F.getName() == "calloc")

2019 return false;

2022 return false;

2023 auto *InnerCallee = Malloc->getCalledFunction();

2024 if (!InnerCallee)

2025 return false;

2026 LibFunc Func = NotLibFunc;

2027 StringRef ZeroedVariantName;

2028 if (!TLI.getLibFunc(*InnerCallee, Func) || !TLI.has(Func) ||

2029 Func != LibFunc_malloc) {

2030 Attribute Attr = Malloc->getFnAttr("alloc-variant-zeroed");

2032 return false;

2034 if (ZeroedVariantName.empty())

2035 return false;

2036 }

2037

2038

2040 if (!MallocDef)

2041 return false;

2042

2043 auto shouldCreateCalloc = [](CallInst *Malloc, CallInst *Memset) {

2044

2045

2046 auto *MallocBB = Malloc->getParent(),

2047 *MemsetBB = Memset->getParent();

2048 if (MallocBB == MemsetBB)

2049 return true;

2050 auto *Ptr = Memset->getArgOperand(0);

2051 auto *TI = MallocBB->getTerminator();

2055 TrueBB, FalseBB)))

2056 return false;

2057 if (MemsetBB != FalseBB)

2058 return false;

2059 return true;

2060 };

2061

2063 return false;

2064 if (!shouldCreateCalloc(Malloc, MemSet) || !DT.dominates(Malloc, MemSet) ||

2066 return false;

2068 assert(Func == LibFunc_malloc || !ZeroedVariantName.empty());

2069 Value *Calloc = nullptr;

2070 if (!ZeroedVariantName.empty()) {

2071 LLVMContext &Ctx = Malloc->getContext();

2072 AttributeList Attrs = InnerCallee->getAttributes();

2074 Attrs.getFnAttr(Attribute::AllocKind).getAllocKind() |

2075 AllocFnKind::Zeroed;

2078 Attrs.addFnAttribute(Ctx, Attribute::getWithAllocKind(Ctx, AllocKind))

2079 .removeFnAttribute(Ctx, "alloc-variant-zeroed");

2080 FunctionCallee ZeroedVariant = Malloc->getModule()->getOrInsertFunction(

2081 ZeroedVariantName, InnerCallee->getFunctionType(), Attrs);

2084 Calloc = IRB.CreateCall(ZeroedVariant, Args, ZeroedVariantName);

2085 } else {

2086 Type *SizeTTy = Malloc->getArgOperand(0)->getType();

2087 Calloc =

2088 emitCalloc(ConstantInt::get(SizeTTy, 1), Malloc->getArgOperand(0),

2089 IRB, TLI, Malloc->getType()->getPointerAddressSpace());

2090 }

2091 if (!Calloc)

2092 return false;

2093

2094 MemorySSAUpdater Updater(&MSSA);

2095 auto *NewAccess =

2096 Updater.createMemoryAccessAfter(cast(Calloc), nullptr,

2097 MallocDef);

2099 Updater.insertDef(NewAccessMD, true);

2100 Malloc->replaceAllUsesWith(Calloc);

2102 return true;

2103 }

2104

2105

2106

2107 bool dominatingConditionImpliesValue(MemoryDef *Def) {

2109 BasicBlock *StoreBB = StoreI->getParent();

2110 Value *StorePtr = StoreI->getPointerOperand();

2111 Value *StoreVal = StoreI->getValueOperand();

2112

2114 if (!IDom)

2115 return false;

2116

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

2119 return false;

2120

2121

2122

2123

2124 if (BI->getSuccessor(0) == BI->getSuccessor(1))

2125 return false;

2126

2128 CmpPredicate Pred;

2129 if ( match (BI->getCondition(),

2135 return false;

2136

2137

2138

2139 if (Pred == ICmpInst::ICMP_EQ &&

2140 !DT.dominates(BasicBlockEdge(BI->getParent(), BI->getSuccessor(0)),

2141 StoreBB))

2142 return false;

2143

2144 if (Pred == ICmpInst::ICMP_NE &&

2145 !DT.dominates(BasicBlockEdge(BI->getParent(), BI->getSuccessor(1)),

2146 StoreBB))

2147 return false;

2148

2149 MemoryAccess *LoadAcc = MSSA.getMemoryAccess(ICmpL);

2150 MemoryAccess *ClobAcc =

2151 MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def, BatchAA);

2152

2153 return MSSA.dominates(ClobAcc, LoadAcc);

2154 }

2155

2156

2157

2158 bool storeIsNoop(MemoryDef *Def, const Value *DefUO) {

2162 Constant *StoredConstant = nullptr;

2163 if (Store)

2165 else if (MemSet)

2167 else

2168 return false;

2169

2170 if (!isRemovable(DefI))

2171 return false;

2172

2173 if (StoredConstant) {

2176

2177

2178 if (InitC && InitC == StoredConstant)

2179 return MSSA.isLiveOnEntryDef(

2180 MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def, BatchAA));

2181 }

2182

2183 if (!Store)

2184 return false;

2185

2186 if (dominatingConditionImpliesValue(Def))

2187 return true;

2188

2190 if (LoadI->getPointerOperand() == Store->getOperand(1)) {

2191

2192 auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess();

2193

2194 if (LoadAccess == Def->getDefiningAccess())

2195 return true;

2196

2197

2198

2199

2200 SetVector<MemoryAccess *> ToCheck;

2201 MemoryAccess *Current =

2202 MSSA.getWalker()->getClobberingMemoryAccess(Def, BatchAA);

2203

2204

2205

2206 ToCheck.insert(Def);

2207 ToCheck.insert(Current);

2208

2209 for (unsigned I = 1; I < ToCheck.size(); ++I) {

2210 Current = ToCheck[I];

2212

2213 for (auto &Use : PhiAccess->incoming_values())

2215 continue;

2216 }

2217

2218

2219

2221 "Only MemoryDefs should reach here.");

2222

2223

2224

2225

2226 if (LoadAccess != Current)

2227 return false;

2228 }

2229 return true;

2230 }

2231 }

2232

2233 return false;

2234 }

2235

2238 for (auto OI : IOL) {

2240 MemoryLocation Loc = *getLocForWrite(DeadI);

2241 assert(isRemovable(DeadI) && "Expect only removable instruction");

2242

2244 int64_t DeadStart = 0;

2249 if (IntervalMap.empty())

2250 continue;

2252 }

2254 }

2255

2256

2257

2258 bool eliminateRedundantStoresOfExistingValues() {

2259 bool MadeChange = false;

2260 LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs that write the "

2261 "already existing value\n");

2262 for (auto *Def : MemDefs) {

2263 if (SkipStores.contains(Def) || MSSA.isLiveOnEntryDef(Def))

2264 continue;

2265

2267 auto MaybeDefLoc = getLocForWrite(DefInst);

2268 if (!MaybeDefLoc || !isRemovable(DefInst))

2269 continue;

2270

2271 MemoryDef *UpperDef;

2272

2273

2274

2275 if (Def->isOptimized())

2277 else

2279 if (!UpperDef || MSSA.isLiveOnEntryDef(UpperDef))

2280 continue;

2281

2283 auto IsRedundantStore = [&]() {

2284

2286 true))

2287 return true;

2290

2291 auto UpperLoc = getLocForWrite(UpperInst);

2292 if (!UpperLoc)

2293 return false;

2294 int64_t InstWriteOffset = 0;

2295 int64_t DepWriteOffset = 0;

2296 auto OR = isOverwrite(UpperInst, DefInst, *UpperLoc, *MaybeDefLoc,

2297 InstWriteOffset, DepWriteOffset);

2299 return StoredByte && StoredByte == MemSetI->getOperand(1) &&

2300 OR == OW_Complete;

2301 }

2302 }

2303 return false;

2304 };

2305

2306 if (!IsRedundantStore() || isReadClobber(*MaybeDefLoc, DefInst))

2307 continue;

2308 LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n DEAD: " << *DefInst

2309 << '\n');

2311 NumRedundantStores++;

2312 MadeChange = true;

2313 }

2314 return MadeChange;

2315 }

2316

2317

2318

2319

2320

2321

2322

2323

2324

2326

2327

2328

2329

2330 std::pair<bool, bool>

2331 eliminateDeadDefs(const MemoryLocationWrapper &KillingLocWrapper);

2332

2333

2334

2335 bool eliminateDeadDefs(const MemoryDefWrapper &KillingDefWrapper);

2336};

2337}

2338

2339

2347

2349DSEState::getInitializesArgMemLoc(const Instruction *I) {

2351 if (!CB)

2352 return {};

2353

2354

2355 SmallMapVector<Value *, SmallVector<ArgumentInitInfo, 2>, 2> Arguments;

2356 for (unsigned Idx = 0, Count = CB->arg_size(); Idx < Count; ++Idx) {

2359 continue;

2360

2361 ConstantRangeList Inits;

2363

2364

2367

2368

2369

2370

2373 Inits = ConstantRangeList();

2374

2375

2376

2377

2378

2379

2380

2381 bool IsDeadOrInvisibleOnUnwind =

2382 CB->paramHasAttr(Idx, Attribute::DeadOnUnwind) ||

2383 (isa(CB) && isInvisibleToCallerOnUnwind(CurArg));

2384 ArgumentInitInfo InitInfo{Idx, IsDeadOrInvisibleOnUnwind, Inits};

2385 bool FoundAliasing = false;

2386 for (auto &[Arg, AliasList] : Arguments) {

2390 continue;

2392 FoundAliasing = true;

2393 AliasList.push_back(InitInfo);

2394 } else {

2395

2396

2397

2398 FoundAliasing = true;

2399 AliasList.push_back(ArgumentInitInfo{Idx, IsDeadOrInvisibleOnUnwind,

2400 ConstantRangeList()});

2401 }

2402 }

2403 if (!FoundAliasing)

2405 }

2406

2408 for (const auto &[_, Args] : Arguments) {

2409 auto IntersectedRanges =

2411 if (IntersectedRanges.empty())

2412 continue;

2413

2414 for (const auto &Arg : Args) {

2415 for (const auto &Range : IntersectedRanges) {

2418

2419 if (Start == 0)

2423 }

2424 }

2425 }

2427}

2428

2429std::pair<bool, bool>

2430DSEState::eliminateDeadDefs(const MemoryLocationWrapper &KillingLocWrapper) {

2432 bool DeletedKillingLoc = false;

2436

2437

2438 SmallSetVector<MemoryAccess *, 8> ToCheck;

2439

2440

2441

2442 SmallPtrSet<MemoryAccess *, 8> Deleted;

2443 [[maybe_unused]] unsigned OrigNumSkipStores = SkipStores.size();

2445

2446

2447

2448 for (unsigned I = 0; I < ToCheck.size(); I++) {

2449 MemoryAccess *Current = ToCheck[I];

2450 if (Deleted.contains(Current))

2451 continue;

2452 std::optional<MemoryAccess *> MaybeDeadAccess = getDomMemoryDef(

2453 KillingLocWrapper.MemDef, Current, KillingLocWrapper.MemLoc,

2454 KillingLocWrapper.UnderlyingObject, ScanLimit, WalkerStepLimit,

2455 isMemTerminatorInst(KillingLocWrapper.DefInst), PartialLimit,

2456 KillingLocWrapper.DefByInitializesAttr);

2457

2458 if (!MaybeDeadAccess) {

2460 continue;

2461 }

2462 MemoryAccess *DeadAccess = *MaybeDeadAccess;

2463 LLVM_DEBUG(dbgs() << " Checking if we can kill " << *DeadAccess);

2465 LLVM_DEBUG(dbgs() << "\n ... adding incoming values to worklist\n");

2470

2471

2472

2473

2474 if (PostOrderNumbers[IncomingBlock] > PostOrderNumbers[PhiBlock])

2475 ToCheck.insert(IncomingAccess);

2476 }

2477 continue;

2478 }

2479

2480

2481

2482

2483

2484

2485

2486 MemoryDefWrapper DeadDefWrapper(

2488 getLocForInst(cast(DeadAccess)->getMemoryInst(),

2489 false));

2490 assert(DeadDefWrapper.DefinedLocations.size() == 1);

2491 MemoryLocationWrapper &DeadLocWrapper =

2492 DeadDefWrapper.DefinedLocations.front();

2493 LLVM_DEBUG(dbgs() << " (" << *DeadLocWrapper.DefInst << ")\n");

2495 NumGetDomMemoryDefPassed++;

2496

2498 continue;

2499 if (isMemTerminatorInst(KillingLocWrapper.DefInst)) {

2500 if (KillingLocWrapper.UnderlyingObject != DeadLocWrapper.UnderlyingObject)

2501 continue;

2502 LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: "

2503 << *DeadLocWrapper.DefInst << "\n KILLER: "

2504 << *KillingLocWrapper.DefInst << '\n');

2506 ++NumFastStores;

2508 } else {

2509

2510 int64_t KillingOffset = 0;

2511 int64_t DeadOffset = 0;

2512 OverwriteResult OR =

2513 isOverwrite(KillingLocWrapper.DefInst, DeadLocWrapper.DefInst,

2514 KillingLocWrapper.MemLoc, DeadLocWrapper.MemLoc,

2515 KillingOffset, DeadOffset);

2516 if (OR == OW_MaybePartial) {

2517 auto &IOL = IOLs[DeadLocWrapper.DefInst->getParent()];

2519 KillingOffset, DeadOffset,

2520 DeadLocWrapper.DefInst, IOL);

2521 }

2525

2526

2527

2528 if (DeadSI && KillingSI && DT.dominates(DeadSI, KillingSI)) {

2530 KillingSI, DeadSI, KillingOffset, DeadOffset, DL, BatchAA,

2531 &DT)) {

2532

2533

2534 DeadSI->setOperand(0, Merged);

2535 ++NumModifiedStores;

2537 DeletedKillingLoc = true;

2538

2539

2540

2542 auto I = IOLs.find(DeadSI->getParent());

2543 if (I != IOLs.end())

2544 I->second.erase(DeadSI);

2545 break;

2546 }

2547 }

2548 }

2549 if (OR == OW_Complete) {

2550 LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: "

2551 << *DeadLocWrapper.DefInst << "\n KILLER: "

2552 << *KillingLocWrapper.DefInst << '\n');

2554 ++NumFastStores;

2556 }

2557 }

2558 }

2559

2560 assert(SkipStores.size() - OrigNumSkipStores == Deleted.size() &&

2561 "SkipStores and Deleted out of sync?");

2562

2563 return {Changed, DeletedKillingLoc};

2564}

2565

2566bool DSEState::eliminateDeadDefs(const MemoryDefWrapper &KillingDefWrapper) {

2567 if (KillingDefWrapper.DefinedLocations.empty()) {

2568 LLVM_DEBUG(dbgs() << "Failed to find analyzable write location for "

2569 << *KillingDefWrapper.DefInst << "\n");

2570 return false;

2571 }

2572

2573 bool MadeChange = false;

2574 for (auto &KillingLocWrapper : KillingDefWrapper.DefinedLocations) {

2575 LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by "

2576 << *KillingLocWrapper.MemDef << " ("

2577 << *KillingLocWrapper.DefInst << ")\n");

2578 auto [Changed, DeletedKillingLoc] = eliminateDeadDefs(KillingLocWrapper);

2580

2581

2582 if (!DeletedKillingLoc && storeIsNoop(KillingLocWrapper.MemDef,

2583 KillingLocWrapper.UnderlyingObject)) {

2584 LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n DEAD: "

2585 << *KillingLocWrapper.DefInst << '\n');

2587 NumRedundantStores++;

2588 MadeChange = true;

2589 continue;

2590 }

2591

2592 if (!DeletedKillingLoc &&

2593 tryFoldIntoCalloc(KillingLocWrapper.MemDef,

2594 KillingLocWrapper.UnderlyingObject)) {

2595 LLVM_DEBUG(dbgs() << "DSE: Remove memset after forming calloc:\n"

2596 << " DEAD: " << *KillingLocWrapper.DefInst << '\n');

2598 MadeChange = true;

2599 continue;

2600 }

2601 }

2602 return MadeChange;

2603}

2604

2609 bool MadeChange = false;

2610 DSEState State(F, AA, MSSA, DT, PDT, TLI, LI);

2611

2612 for (unsigned I = 0; I < State.MemDefs.size(); I++) {

2613 MemoryDef *KillingDef = State.MemDefs[I];

2614 if (State.SkipStores.count(KillingDef))

2615 continue;

2616

2617 MemoryDefWrapper KillingDefWrapper(

2618 KillingDef, State.getLocForInst(KillingDef->getMemoryInst(),

2620 MadeChange |= State.eliminateDeadDefs(KillingDefWrapper);

2621 }

2622

2624 for (auto &KV : State.IOLs)

2625 MadeChange |= State.removePartiallyOverlappedStores(KV.second);

2626

2627 MadeChange |= State.eliminateRedundantStoresOfExistingValues();

2628 MadeChange |= State.eliminateDeadWritesAtEndOfFunction();

2629

2630 while (!State.ToRemove.empty()) {

2631 Instruction *DeadInst = State.ToRemove.pop_back_val();

2633 }

2634

2635 return MadeChange;

2636}

2637

2638

2639

2640

2648

2650

2651#ifdef LLVM_ENABLE_STATS

2655#endif

2656

2659

2664 return PA;

2665}

2666

2667namespace {

2668

2669

2671public:

2672 static char ID;

2673

2676 }

2677

2679 if (skipFunction(F))

2680 return false;

2681

2682 AliasAnalysis &AA = getAnalysis().getAAResults();

2683 DominatorTree &DT = getAnalysis().getDomTree();

2685 getAnalysis().getTLI(F);

2686 MemorySSA &MSSA = getAnalysis().getMSSA();

2688 getAnalysis().getPostDomTree();

2689 LoopInfo &LI = getAnalysis().getLoopInfo();

2690

2692

2693#ifdef LLVM_ENABLE_STATS

2697#endif

2698

2700 }

2701

2702 void getAnalysisUsage(AnalysisUsage &AU) const override {

2705 AU.addRequired();

2707 AU.addRequired();

2708 AU.addPreserved();

2709 AU.addRequired();

2711 AU.addPreserved();

2715 AU.addRequired();

2716 }

2717};

2718

2719}

2720

2721char DSELegacyPass::ID = 0;

2722

2724 false)

2736

2738 return new DSELegacyPass();

2739}

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

AMDGPU Lower Kernel Arguments

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Expand Atomic instructions

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

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

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

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

MapVector< Instruction *, OverlapIntervalsTy > InstOverlapIntervalsTy

Definition DeadStoreElimination.cpp:180

static bool canSkipDef(MemoryDef *D, bool DefVisibleToCaller)

Definition DeadStoreElimination.cpp:831

static cl::opt< bool > EnableInitializesImprovement("enable-dse-initializes-attr-improvement", cl::init(true), cl::Hidden, cl::desc("Enable the initializes attr improvement in DSE"))

static void shortenAssignment(Instruction *Inst, Value *OriginalDest, uint64_t OldOffsetInBits, uint64_t OldSizeInBits, uint64_t NewSizeInBits, bool IsOverwriteEnd)

Definition DeadStoreElimination.cpp:508

static bool isShortenableAtTheEnd(Instruction *I)

Returns true if the end of this instruction can be safely shortened in length.

Definition DeadStoreElimination.cpp:184

static bool isNoopIntrinsic(Instruction *I)

Definition DeadStoreElimination.cpp:810

static ConstantRangeList getIntersectedInitRangeList(ArrayRef< ArgumentInitInfo > Args, bool CallHasNoUnwindAttr)

Definition DeadStoreElimination.cpp:911

static cl::opt< bool > EnablePartialStoreMerging("enable-dse-partial-store-merging", cl::init(true), cl::Hidden, cl::desc("Enable partial store merging in DSE"))

static bool tryToShortenBegin(Instruction *DeadI, OverlapIntervalsTy &IntervalMap, int64_t &DeadStart, uint64_t &DeadSize)

Definition DeadStoreElimination.cpp:734

std::map< int64_t, int64_t > OverlapIntervalsTy

Definition DeadStoreElimination.cpp:179

static bool isShortenableAtTheBeginning(Instruction *I)

Returns true if the beginning of this instruction can be safely shortened in length.

Definition DeadStoreElimination.cpp:209

static cl::opt< unsigned > MemorySSADefsPerBlockLimit("dse-memoryssa-defs-per-block-limit", cl::init(5000), cl::Hidden, cl::desc("The number of MemoryDefs we consider as candidates to eliminated " "other stores per basic block (default = 5000)"))

static Constant * tryToMergePartialOverlappingStores(StoreInst *KillingI, StoreInst *DeadI, int64_t KillingOffset, int64_t DeadOffset, const DataLayout &DL, BatchAAResults &AA, DominatorTree *DT)

Definition DeadStoreElimination.cpp:764

static bool memoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI, BatchAAResults &AA, const DataLayout &DL, DominatorTree *DT)

Returns true if the memory which is accessed by the second instruction is not modified between the fi...

Definition DeadStoreElimination.cpp:421

static OverwriteResult isMaskedStoreOverwrite(const Instruction *KillingI, const Instruction *DeadI, BatchAAResults &AA)

Check if two instruction are masked stores that completely overwrite one another.

Definition DeadStoreElimination.cpp:245

static cl::opt< unsigned > MemorySSAOtherBBStepCost("dse-memoryssa-otherbb-cost", cl::init(5), cl::Hidden, cl::desc("The cost of a step in a different basic " "block than the killing MemoryDef" "(default = 5)"))

static bool tryToShorten(Instruction *DeadI, int64_t &DeadStart, uint64_t &DeadSize, int64_t KillingStart, uint64_t KillingSize, bool IsOverwriteEnd)

Definition DeadStoreElimination.cpp:613

static cl::opt< unsigned > MemorySSAScanLimit("dse-memoryssa-scanlimit", cl::init(150), cl::Hidden, cl::desc("The number of memory instructions to scan for " "dead store elimination (default = 150)"))

static bool isFuncLocalAndNotCaptured(Value *Arg, const CallBase *CB, EarliestEscapeAnalysis &EA)

Definition DeadStoreElimination.cpp:2340

static cl::opt< unsigned > MemorySSASameBBStepCost("dse-memoryssa-samebb-cost", cl::init(1), cl::Hidden, cl::desc("The cost of a step in the same basic block as the killing MemoryDef" "(default = 1)"))

static cl::opt< bool > EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking", cl::init(true), cl::Hidden, cl::desc("Enable partial-overwrite tracking in DSE"))

static OverwriteResult isPartialOverwrite(const MemoryLocation &KillingLoc, const MemoryLocation &DeadLoc, int64_t KillingOff, int64_t DeadOff, Instruction *DeadI, InstOverlapIntervalsTy &IOL)

Return 'OW_Complete' if a store to the 'KillingLoc' location completely overwrites a store to the 'De...

Definition DeadStoreElimination.cpp:303

static cl::opt< unsigned > MemorySSAPartialStoreLimit("dse-memoryssa-partial-store-limit", cl::init(5), cl::Hidden, cl::desc("The maximum number candidates that only partially overwrite the " "killing MemoryDef to consider" " (default = 5)"))

static std::optional< TypeSize > getPointerSize(const Value *V, const DataLayout &DL, const TargetLibraryInfo &TLI, const Function *F)

Definition DeadStoreElimination.cpp:215

static bool tryToShortenEnd(Instruction *DeadI, OverlapIntervalsTy &IntervalMap, int64_t &DeadStart, uint64_t &DeadSize)

Definition DeadStoreElimination.cpp:707

static void adjustArgAttributes(AnyMemIntrinsic *Intrinsic, unsigned ArgNo, uint64_t PtrOffset)

Update the attributes given that a memory access is updated (the dereferenced pointer could be moved ...

Definition DeadStoreElimination.cpp:579

static cl::opt< unsigned > MemorySSAUpwardsStepLimit("dse-memoryssa-walklimit", cl::init(90), cl::Hidden, cl::desc("The maximum number of steps while walking upwards to find " "MemoryDefs that may be killed (default = 90)"))

static cl::opt< bool > OptimizeMemorySSA("dse-optimize-memoryssa", cl::init(true), cl::Hidden, cl::desc("Allow DSE to optimize memory accesses."))

static bool hasInitializesAttr(Instruction *I)

Definition DeadStoreElimination.cpp:901

static cl::opt< unsigned > MemorySSAPathCheckLimit("dse-memoryssa-path-check-limit", cl::init(50), cl::Hidden, cl::desc("The maximum number of blocks to check when trying to prove that " "all paths to an exit go through a killing block (default = 50)"))

static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT, PostDominatorTree &PDT, const TargetLibraryInfo &TLI, const LoopInfo &LI)

Definition DeadStoreElimination.cpp:2605

This file provides an implementation of debug counters.

#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)

This file defines the DenseMap class.

early cse Early CSE w MemorySSA

static bool runOnFunction(Function &F, bool PostInlining)

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

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

This header defines various interfaces for pass management in LLVM.

static void deleteDeadInstruction(Instruction *I)

This file implements a map that provides insertion order iteration.

This file provides utility analysis objects describing memory locations.

This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...

Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...

ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))

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 builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.

This file implements a set that has insertion order iteration characteristics.

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.

Class for arbitrary precision integers.

LLVM_ABI APInt zext(unsigned width) const

Zero extend to a new width.

static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit)

Get a value with a block of bits set.

unsigned getBitWidth() const

Return the number of bits in the APInt.

int64_t getSExtValue() const

Get sign extended value.

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

constexpr int32_t getOffset() const

constexpr bool hasOffset() const

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

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

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

LLVM_ABI void setPreservesCFG()

This function should be called by the pass, iff they do not:

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

An immutable pass that tracks lazily created AssumptionCache objects.

This class stores enough information to efficiently remove some attributes from an existing AttrBuild...

AttributeMask & addAttribute(Attribute::AttrKind Val)

Add an attribute to the mask.

This class holds the attributes for a particular argument, parameter, function, or return value.

LLVM_ABI ArrayRef< ConstantRange > getValueAsConstantRangeList() const

Return the attribute's value as a ConstantRange array.

LLVM_ABI StringRef getValueAsString() const

Return the attribute's value as a string.

bool isValid() const

Return true if the attribute is any kind of attribute.

LLVM Basic Block Representation.

const Function * getParent() const

Return the enclosing method, or null if none.

InstListType::iterator iterator

Instruction iterators...

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

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)

Represents analyses that only rely on functions' control flow.

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

LLVM_ABI bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const

Determine whether the argument or parameter has the given attribute.

Attribute getParamAttr(unsigned ArgNo, Attribute::AttrKind Kind) const

Get the attribute of a given kind from a given arg.

bool isByValArgument(unsigned ArgNo) const

Determine whether this argument is passed by value.

LLVM_ABI bool onlyAccessesInaccessibleMemOrArgMem() const

Determine if the function may only access memory that is either inaccessible from the IR or pointed t...

bool doesNotThrow() const

Determine if the call cannot unwind.

Value * getArgOperand(unsigned i) const

LLVM_ABI Value * getArgOperandWithAttribute(Attribute::AttrKind Kind) const

If one of the arguments has the specified attribute, returns its operand value.

unsigned arg_size() const

This class represents a list of constant ranges.

bool empty() const

Return true if this list contains no members.

LLVM_ABI ConstantRangeList intersectWith(const ConstantRangeList &CRL) const

Return the range list that results from the intersection of this ConstantRangeList with another Const...

const APInt & getLower() const

Return the lower value for this range.

const APInt & getUpper() const

Return the upper value for this range.

This is an important base class in LLVM.

LLVM_ABI bool isNullValue() const

Return true if this is the value that would be returned by getNullValue.

static DIAssignID * getDistinct(LLVMContext &Context)

DbgVariableFragmentInfo FragmentInfo

static LLVM_ABI std::optional< DIExpression * > createFragmentExpression(const DIExpression *Expr, unsigned OffsetInBits, unsigned SizeInBits)

Create a DIExpression to describe one part of an aggregate variable that is fragmented across multipl...

PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)

Definition DeadStoreElimination.cpp:2641

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

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

static bool shouldExecute(CounterInfo &Counter)

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

DomTreeNodeBase * getIDom() const

Analysis pass which computes a DominatorTree.

Legacy analysis pass which computes a DominatorTree.

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

LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

Context-sensitive CaptureAnalysis provider, which computes and caches the earliest common dominator c...

CaptureComponents getCapturesBefore(const Value *Object, const Instruction *I, bool OrAt) override

Return how Object may be captured before instruction I, considering only provenance captures.

FunctionPass class - This class is used to implement most global optimizations.

const BasicBlock & getEntryBlock() const

static GetElementPtrInst * CreateInBounds(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Create an "inbounds" getelementptr.

Legacy wrapper pass to provide the GlobalsAAResult object.

bool isEquality() const

Return true if this predicate is either EQ or NE.

LLVM_ABI bool mayThrow(bool IncludePhaseOneUnwind=false) const LLVM_READONLY

Return true if this instruction may throw an exception.

LLVM_ABI bool mayWriteToMemory() const LLVM_READONLY

Return true if this instruction may modify memory.

LLVM_ABI bool isAtomic() const LLVM_READONLY

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

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes 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,...

LLVM_ABI bool mayReadFromMemory() const LLVM_READONLY

Return true if this instruction may read memory.

LLVM_ABI AAMDNodes getAAMetadata() const

Returns the AA metadata for this instruction.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

LLVM_ABI const DataLayout & getDataLayout() const

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

const_iterator begin() const

bool empty() const

empty - Return true when no intervals are mapped.

const_iterator end() const

A wrapper class for inspecting calls to intrinsic functions.

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

static LocationSize precise(uint64_t Value)

TypeSize getValue() const

Analysis pass that exposes the LoopInfo for a function.

The legacy pass manager's analysis pass to compute loop information.

static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)

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

iterator find(const KeyT &Key)

Value * getLength() const

BasicBlock * getBlock() const

Represents a read-write access to memory, whether it is a must-alias, or a may-alias.

void setOptimized(MemoryAccess *MA)

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

Representation for a specific memory location.

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 getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())

Return a location that may access any location before or after Ptr, while remaining within the underl...

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

const Value * Ptr

The address of the start of the location.

static LLVM_ABI MemoryLocation getForDest(const MemIntrinsic *MI)

Return a location representing the destination of a memory set or transfer.

static LLVM_ABI std::optional< MemoryLocation > getOrNone(const Instruction *Inst)

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

Return a location representing a particular argument of a call.

An analysis that produces MemorySSA for a function.

Legacy analysis pass which computes MemorySSA.

Encapsulates MemorySSA, including all data associated with memory accesses.

MemoryAccess * getDefiningAccess() const

Get the access that produces the memory state used by this Use.

Instruction * getMemoryInst() const

Get the instruction that this MemoryUse represents.

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

LLVM_ABI bool isPotentiallyPHITranslatable() const

isPotentiallyPHITranslatable - If this needs PHI translation, return true if we have some hope of doi...

bool needsPHITranslationFromBlock(BasicBlock *BB) const

needsPHITranslationFromBlock - Return true if moving from the specified BasicBlock to its predecessor...

static LLVM_ABI PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

static LLVM_ABI PoisonValue * get(Type *T)

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

Analysis pass which computes a PostDominatorTree.

PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...

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 & preserveSet()

Mark an analysis set as preserved.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

size_type size() const

Determine the number of elements in the SetVector.

void insert_range(Range &&R)

bool insert(const value_type &X)

Insert a new element into the SetVector.

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.

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.

Value * getValueOperand()

constexpr bool empty() const

empty - Check if the string is empty.

Analysis pass providing the TargetLibraryInfo.

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

static constexpr TypeSize getFixed(ScalarTy ExactSize)

bool isPointerTy() const

True if this is an instance of PointerType.

static LLVM_ABI IntegerType * getInt8Ty(LLVMContext &C)

bool isVoidTy() const

Return true if this is 'void'.

LLVM Value Representation.

Type * getType() const

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

LLVM_ABI const Value * stripPointerCasts() const

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

LLVM_ABI LLVMContext & getContext() const

All values hold a context through their type.

iterator_range< use_iterator > uses()

constexpr bool isScalable() const

Returns whether the quantity is scaled by a runtime quantity (vscale).

const ParentTy * getParent() const

self_iterator getIterator()

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

Abstract Attribute helper functions.

constexpr char Args[]

Key for Kernel::Metadata::mArgs.

constexpr char Attrs[]

Key for Kernel::Metadata::mAttrs.

unsigned ID

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

@ BasicBlock

Various leaf nodes.

This namespace contains an enum with a value for every intrinsic/builtin function known by LLVM.

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

bind_ty< Instruction > m_Instruction(Instruction *&I)

Match an instruction, capturing it if we match.

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

CmpClass_match< LHS, RHS, ICmpInst, true > m_c_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)

Matches an ICmp with a predicate over LHS and RHS in either order.

match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)

Combine two pattern matchers matching L && R.

SpecificCmpClass_match< LHS, RHS, ICmpInst > m_SpecificICmp(CmpPredicate MatchPred, const LHS &L, const RHS &R)

OneOps_match< OpTy, Instruction::Load > m_Load(const OpTy &Op)

Matches LoadInst.

brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)

is_zero m_Zero()

Match any null constant or a vector with all elements equal to 0.

SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)

Return a range of dbg_assign records for which Inst performs the assignment they encode.

LLVM_ABI bool calculateFragmentIntersect(const DataLayout &DL, const Value *Dest, uint64_t SliceOffsetInBits, uint64_t SliceSizeInBits, const DbgVariableRecord *DVRAssign, std::optional< DIExpression::FragmentInfo > &Result)

Calculate the fragment of the variable in DAI covered from (Dest + SliceOffsetInBits) to to (Dest + S...

initializer< Ty > init(const Ty &Val)

NodeAddr< DefNode * > Def

NodeAddr< FuncNode * > Func

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

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

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

LLVM_ABI void initializeDSELegacyPassPass(PassRegistry &)

FunctionAddr VTableAddr Value

LLVM_ABI Constant * getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty)

If this is a call to an allocation function that initializes memory to a fixed value,...

decltype(auto) dyn_cast(const From &Val)

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

bool isStrongerThanMonotonic(AtomicOrdering AO)

bool isAligned(Align Lhs, uint64_t SizeInBytes)

Checks that SizeInBytes is a multiple of the alignment.

LLVM_ABI void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)

Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...

Value * GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, const DataLayout &DL, bool AllowNonInbounds=true)

Analyze the specified pointer to see if it can be expressed as a base pointer plus a constant offset.

iterator_range< po_iterator< T > > post_order(const T &G)

LLVM_ABI bool isNoAliasCall(const Value *V)

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

DomTreeNodeBase< BasicBlock > DomTreeNode

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.

LLVM_ABI bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})

Compute the size of the object pointed by Ptr.

auto reverse(ContainerTy &&C)

bool isModSet(const ModRefInfo MRI)

LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)

Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...

LLVM_ABI raw_ostream & dbgs()

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

FunctionAddr VTableAddr Count

LLVM_ABI bool AreStatisticsEnabled()

Check if statistics are enabled.

LLVM_ABI bool isNotVisibleOnUnwind(const Value *Object, bool &RequiresNoCaptureBeforeUnwind)

Return true if Object memory is not visible after an unwind, in the sense that program semantics cann...

LLVM_ABI Value * emitCalloc(Value *Num, Value *Size, IRBuilderBase &B, const TargetLibraryInfo &TLI, unsigned AddrSpace)

Emit a call to the calloc function.

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

uint64_t offsetToAlignment(uint64_t Value, Align Alignment)

Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...

IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >

LLVM_ABI bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)

Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.

LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, unsigned MaxUsesToExplore=0)

PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...

ArrayRef(const T &OneElt) -> ArrayRef< T >

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

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

LLVM_ABI bool isIdentifiedFunctionLocal(const Value *V)

Return true if V is umabigously identified at the function-level.

decltype(auto) cast(const From &Val)

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

LLVM_ABI FunctionPass * createDeadStoreEliminationPass()

Definition DeadStoreElimination.cpp:2737

LLVM_ABI Value * isBytewiseValue(Value *V, const DataLayout &DL)

If the specified value can be set by repeating the same byte in memory, return the i8 value that it i...

auto predecessors(const MachineBasicBlock *BB)

bool capturesAnything(CaptureComponents CC)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)

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

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

AAResults AliasAnalysis

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

bool capturesNothing(CaptureComponents CC)

LLVM_ABI bool isIdentifiedObject(const Value *V)

Return true if this pointer refers to a distinct and identifiable object.

bool isStrongerThan(AtomicOrdering AO, AtomicOrdering Other)

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

bool isRefSet(const ModRefInfo MRI)

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

constexpr uint64_t value() const

This is a hole in the type system and should not be abused.

Various options to control the behavior of getObjectSize.

bool NullIsUnknownSize

If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.