InstCombineLoadStoreAlloca.cpp Source File (original) (raw)

27using namespace llvm;

28using namespace PatternMatch;

30#define DEBUG_TYPE "instcombine"

32 STATISTIC(NumDeadStore, "Number of dead stores eliminated");

33 STATISTIC(NumGlobalCopies, "Number of allocas copied from constant global");

36 "instcombine-max-copied-from-constant-users", cl::init(300),

37 cl::desc("Maximum users to visit in copy from constant transform"),

47static bool

59 while (!Worklist.empty()) {

60 ValueAndIsOffset Elem = Worklist.pop_back_val();

61 if (!Visited.insert(Elem).second)

62 continue;

64 return false;

66 const auto [Value, IsOffset] = Elem;

68 auto *I = cast(U.getUser());

70 if (auto *LI = dyn_cast(I)) {

72 if (!LI->isSimple()) return false;

73 continue;

74 }

76 if (isa<PHINode, SelectInst>(I)) {

81 continue;

82 }

83 if (isa<BitCastInst, AddrSpaceCastInst>(I)) {

86 continue;

87 }

88 if (auto *GEP = dyn_cast(I)) {

91 Worklist.emplace_back(I, IsOffset || GEP ->hasAllZeroIndices());

92 continue;

93 }

95 if (auto *Call = dyn_cast(I)) {

98 if (Call->isCallee(&U))

99 continue;

100

101 unsigned DataOpNo = Call->getDataOperandNo(&U);

102 bool IsArgOperand = Call->isArgOperand(&U);

103

104

105 if (IsArgOperand && Call->isInAllocaArgument(DataOpNo))

106 return false;

107

108

109

110

111 bool NoCapture = Call->doesNotCapture(DataOpNo);

112 if ((Call->onlyReadsMemory() && (Call->use_empty() || NoCapture)) ||

113 (Call->onlyReadsMemory(DataOpNo) && NoCapture))

114 continue;

115 }

116

117

118 if (I->isLifetimeStartOrEnd()) {

119 assert(I->use_empty() && "Lifetime markers have no result to use!");

121 continue;

122 }

123

124

125

127 if ()

128 return false;

129

130

131 if (MI->isVolatile())

132 return false;

133

134

135

136 if (U.getOperandNo() == 1)

137 continue;

138

139

140 if (TheCopy) return false;

141

142

143

144 if (IsOffset) return false;

145

146

147 if (U.getOperandNo() != 0) return false;

148

149

151 return false;

152

153

154 TheCopy = MI;

155 }

156 }

157 return true;

158}

159

160

161

162

163

170 return TheCopy;

171 return nullptr;

172}

173

174

178 return false;

180 if (!AllocaSize)

181 return false;

183 APInt(64, AllocaSize), DL);

184}

185

188

190

192 return nullptr;

193

194

196 }

197

198

200 if (C->getValue().getActiveBits() <= 64) {

204 New->setAlignment(AI.getAlign());

206

209 }

210 }

211

214

215

216

217

222 }

223

224 return nullptr;

225}

226

227namespace {

228

229

230

231

232

233

234

235

236

237

238class PointerReplacer {

239public:

241 : IC(IC), Root(Root), FromAS(SrcAS) {}

242

243 bool collectUsers();

244 void replacePointer(Value *V);

245

246private:

251 return I == &Root || Worklist.contains(I);

252 }

253

254 bool isEqualOrValidAddrSpaceCast(const Instruction *I,

255 unsigned FromAS) const {

256 const auto *ASC = dyn_cast(I);

257 if (!ASC)

258 return false;

259 unsigned ToAS = ASC->getDestAddressSpace();

260 return (FromAS == ToAS) || IC.isValidAddrSpaceCast(FromAS, ToAS);

261 }

262

268 unsigned FromAS;

269};

270}

271

272bool PointerReplacer::collectUsers() {

273 if (!collectUsersRecursive(Root))

274 return false;

275

276

277

278

280}

281

282bool PointerReplacer::collectUsersRecursive(Instruction &I) {

283 for (auto *U : I.users()) {

284 auto *Inst = cast(&*U);

285 if (auto *Load = dyn_cast(Inst)) {

286 if (Load->isVolatile())

287 return false;

288 Worklist.insert(Load);

289 } else if (auto *PHI = dyn_cast(Inst)) {

290

291 if (any_of(PHI->incoming_values(),

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

293 return false;

294

295

296

297

298 if (any_of(PHI->incoming_values(), [this](Value *V) {

299 return !isAvailable(cast(V));

300 })) {

301 ValuesToRevisit.insert(Inst);

302 continue;

303 }

304

305 Worklist.insert(PHI);

306 if (!collectUsersRecursive(*PHI))

307 return false;

308 } else if (auto *SI = dyn_cast(Inst)) {

309 if (!isa(SI->getTrueValue()) ||

310 !isa(SI->getFalseValue()))

311 return false;

312

313 if ( isAvailable (cast(SI->getTrueValue())) ||

314 isAvailable (cast(SI->getFalseValue()))) {

315 ValuesToRevisit.insert(Inst);

316 continue;

317 }

318 Worklist.insert(SI);

319 if (!collectUsersRecursive(*SI))

320 return false;

321 } else if (isa(Inst)) {

322 Worklist.insert(Inst);

323 if (!collectUsersRecursive(*Inst))

324 return false;

325 } else if (auto *MI = dyn_cast(Inst)) {

326 if (MI->isVolatile())

327 return false;

328 Worklist.insert(Inst);

329 } else if (isEqualOrValidAddrSpaceCast(Inst, FromAS)) {

330 Worklist.insert(Inst);

331 if (!collectUsersRecursive(*Inst))

332 return false;

333 } else if (Inst->isLifetimeStartOrEnd()) {

334 continue;

335 } else {

336

337

338 LLVM_DEBUG(dbgs() << "Cannot handle pointer user: " << *U << '\n');

339 return false;

340 }

341 }

342

343 return true;

344}

345

346Value *PointerReplacer::getReplacement(Value *V) { return WorkMap.lookup(V); }

347

348void PointerReplacer::replace(Instruction *I) {

349 if (getReplacement(I))

350 return;

351

352 if (auto *LT = dyn_cast(I)) {

353 auto *V = getReplacement(LT->getPointerOperand());

354 assert(V && "Operand not replaced");

355 auto *NewI = new LoadInst(LT->getType(), V, "", LT->isVolatile(),

356 LT->getAlign(), LT->getOrdering(),

357 LT->getSyncScopeID());

358 NewI->takeName(LT);

360

361 IC.InsertNewInstWith(NewI, LT->getIterator());

362 IC.replaceInstUsesWith(*LT, NewI);

363 WorkMap[LT] = NewI;

364 } else if (auto *PHI = dyn_cast(I)) {

365 Type *NewTy = getReplacement(PHI->getIncomingValue(0))->getType();

367 PHI->getName(), PHI->getIterator());

368 for (unsigned int I = 0; I < PHI->getNumIncomingValues(); ++I)

369 NewPHI->addIncoming(getReplacement(PHI->getIncomingValue(I)),

370 PHI->getIncomingBlock(I));

371 WorkMap[PHI] = NewPHI;

372 } else if (auto *GEP = dyn_cast(I)) {

373 auto *V = getReplacement(GEP->getPointerOperand());

374 assert(V && "Operand not replaced");

376 auto *NewI =

378 IC.InsertNewInstWith(NewI, GEP->getIterator());

379 NewI->takeName(GEP);

380 NewI->setNoWrapFlags(GEP->getNoWrapFlags());

381 WorkMap[GEP] = NewI;

382 } else if (auto *SI = dyn_cast(I)) {

383 Value *TrueValue = SI->getTrueValue();

384 Value *FalseValue = SI->getFalseValue();

385 if (Value *Replacement = getReplacement(TrueValue))

386 TrueValue = Replacement;

387 if (Value *Replacement = getReplacement(FalseValue))

388 FalseValue = Replacement;

390 SI->getName(), nullptr, SI);

391 IC.InsertNewInstWith(NewSI, SI->getIterator());

392 NewSI->takeName(SI);

393 WorkMap[SI] = NewSI;

394 } else if (auto *MemCpy = dyn_cast(I)) {

395 auto *DestV = MemCpy->getRawDest();

396 auto *SrcV = MemCpy->getRawSource();

397

398 if (auto *DestReplace = getReplacement(DestV))

399 DestV = DestReplace;

400 if (auto *SrcReplace = getReplacement(SrcV))

401 SrcV = SrcReplace;

402

403 IC.Builder.SetInsertPoint(MemCpy);

404 auto *NewI = IC.Builder.CreateMemTransferInst(

405 MemCpy->getIntrinsicID(), DestV, MemCpy->getDestAlign(), SrcV,

406 MemCpy->getSourceAlign(), MemCpy->getLength(), MemCpy->isVolatile());

407 AAMDNodes AAMD = MemCpy->getAAMetadata();

408 if (AAMD)

409 NewI->setAAMetadata(AAMD);

410

411 IC.eraseInstFromFunction(*MemCpy);

412 WorkMap[MemCpy] = NewI;

413 } else if (auto *ASC = dyn_cast(I)) {

414 auto *V = getReplacement(ASC->getPointerOperand());

415 assert(V && "Operand not replaced");

416 assert(isEqualOrValidAddrSpaceCast(

417 ASC, V->getType()->getPointerAddressSpace()) &&

418 "Invalid address space cast!");

419

420 if (V->getType()->getPointerAddressSpace() !=

421 ASC->getType()->getPointerAddressSpace()) {

423 NewI->takeName(ASC);

424 IC.InsertNewInstWith(NewI, ASC->getIterator());

425 WorkMap[ASC] = NewI;

426 } else {

427 WorkMap[ASC] = V;

428 }

429

430 } else {

432 }

433}

434

435void PointerReplacer::replacePointer(Value *V) {

436#ifndef NDEBUG

437 auto *PT = cast(Root.getType());

438 auto *NT = cast(V->getType());

439 assert(PT != NT && "Invalid usage");

440#endif

441 WorkMap[&Root] = V;

442

445}

446

449 return I;

450

452

453

454

456

457

458

462

463

466 if (FirstInst != &AI) {

467

468

469

470 AllocaInst *EntryAI = dyn_cast(FirstInst);

475 return &AI;

476 }

477

478

479

480

484 }

485 }

486 }

487

488

489

490

491

492

493

496 Value *TheSrc = Copy->getSource();

499 TheSrc, AllocaAlign, DL, &AI, &AC, &DT);

500 if (AllocaAlign <= SourceAlign &&

502 !isa(TheSrc)) {

503

504

505 LLVM_DEBUG(dbgs() << "Found alloca equal to global: " << AI << '\n');

511

514 ++NumGlobalCopies;

515 return NewI;

516 }

517

518 PointerReplacer PtrReplacer(*this, AI, SrcAddrSpace);

519 if (PtrReplacer.collectUsers()) {

522

523 PtrReplacer.replacePointer(TheSrc);

524 ++NumGlobalCopies;

525 }

526 }

527 }

528

529

530

532}

533

534

537}

538

539

540

541

542

543

544

545

546

547

549 const Twine &Suffix) {

551 "can't fold an atomic load to requested type");

552

558 return NewLoad;

559}

560

561

562

563

567 "can't fold an atomic store of requested type");

568

569 Value *Ptr = SI.getPointerOperand();

571 SI.getAllMetadata(MD);

572

575 NewStore->setAtomic(SI.getOrdering(), SI.getSyncScopeID());

576 for (const auto &MDPair : MD) {

577 unsigned ID = MDPair.first;

578 MDNode *N = MDPair.second;

579

580

581

582

583

584

585

586

587 switch (ID) {

588 case LLVMContext::MD_dbg:

589 case LLVMContext::MD_DIAssignID:

590 case LLVMContext::MD_tbaa:

591 case LLVMContext::MD_prof:

592 case LLVMContext::MD_fpmath:

593 case LLVMContext::MD_tbaa_struct:

594 case LLVMContext::MD_alias_scope:

595 case LLVMContext::MD_noalias:

596 case LLVMContext::MD_nontemporal:

597 case LLVMContext::MD_mem_parallel_loop_access:

598 case LLVMContext::MD_access_group:

599

601 break;

602 case LLVMContext::MD_invariant_load:

603 case LLVMContext::MD_nonnull:

604 case LLVMContext::MD_noundef:

605 case LLVMContext::MD_range:

606 case LLVMContext::MD_align:

607 case LLVMContext::MD_dereferenceable:

608 case LLVMContext::MD_dereferenceable_or_null:

609

610 break;

611 }

612 }

613

614 return NewStore;

615}

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

636

637

638 if (!Load.isUnordered())

639 return nullptr;

640

641 if (Load.use_empty())

642 return nullptr;

643

644

645 if (Load.getPointerOperand()->isSwiftError())

646 return nullptr;

647

648

649

650

651 if (Load.hasOneUse()) {

652

653

654 Type *LoadTy = Load.getType();

655 if (auto *BC = dyn_cast(Load.user_back())) {

656 assert(!LoadTy->isX86_AMXTy() && "Load from x86_amx* should not happen!");

657 if (BC->getType()->isX86_AMXTy())

658 return nullptr;

659 }

660

661 if (auto *CastUser = dyn_cast(Load.user_back())) {

662 Type *DestTy = CastUser->getDestTy();

669 return &Load;

670 }

671 }

672 }

673

674

675

676 return nullptr;

677}

678

680

681

683 return nullptr;

684

686 if (->isAggregateType())

687 return nullptr;

688

690

691 if (auto *ST = dyn_cast(T)) {

692

693 auto NumElements = ST->getNumElements();

694 if (NumElements == 1) {

696 ".unpack");

700 }

701

702

703

705 auto *SL = DL.getStructLayout(ST);

706

707

708 if (SL->getSizeInBits().isScalable())

709 return nullptr;

710

711 if (SL->hasPadding())

712 return nullptr;

713

717 auto *Zero = ConstantInt::get(IdxType, 0);

718

720 for (unsigned i = 0; i < NumElements; i++) {

721 Value *Indices[2] = {

722 Zero,

723 ConstantInt::get(IdxType, i),

724 };

726 Name + ".elt");

728 ST->getElementType(i), Ptr,

730

733 }

734

735 V->setName(Name);

737 }

738

739 if (auto *AT = dyn_cast(T)) {

740 auto *ET = AT->getElementType();

741 auto NumElements = AT->getNumElements();

742 if (NumElements == 1) {

747 }

748

749

750

751

752

754 return nullptr;

755

757 TypeSize EltSize = DL.getTypeAllocSize(ET);

759

762 auto *Zero = ConstantInt::get(IdxType, 0);

763

766 for (uint64_t i = 0; i < NumElements; i++) {

767 Value *Indices[2] = {

768 Zero,

769 ConstantInt::get(IdxType, i),

770 };

772 Name + ".elt");

775 EltAlign, Name + ".unpack");

779 }

780

781 V->setName(Name);

783 }

784

785 return nullptr;

786}

787

788

789

790

791

792

793

798

799 do {

801 P = P->stripPointerCasts();

802

803 if (!Visited.insert(P).second)

804 continue;

805

806 if (SelectInst *SI = dyn_cast(P)) {

807 Worklist.push_back(SI->getTrueValue());

808 Worklist.push_back(SI->getFalseValue());

809 continue;

810 }

811

812 if (PHINode *PN = dyn_cast(P)) {

813 append_range(Worklist, PN->incoming_values());

814 continue;

815 }

816

817 if (GlobalAlias *GA = dyn_cast(P)) {

818 if (GA->isInterposable())

819 return false;

820 Worklist.push_back(GA->getAliasee());

821 continue;

822 }

823

824

825

826 if (AllocaInst *AI = dyn_cast(P)) {

827 if (!AI->getAllocatedType()->isSized())

828 return false;

829

830 ConstantInt *CS = dyn_cast(AI->getArraySize());

831 if (!CS)

832 return false;

833

834 TypeSize TS = DL.getTypeAllocSize(AI->getAllocatedType());

836 return false;

837

838

840 .ugt(MaxSize))

841 return false;

842 continue;

843 }

844

846 if (!GV->hasDefinitiveInitializer() || !GV->isConstant())

847 return false;

848

849 uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType());

850 if (InitSize > MaxSize)

851 return false;

852 continue;

853 }

854

855 return false;

856 } while (!Worklist.empty());

857

858 return true;

859}

860

861

862

863

864

865

866

867

868

869

870

871

872

873

874

875

878 unsigned &Idx) {

880 return false;

881

882

883

885 unsigned I = 1;

888 if (const ConstantInt *CI = dyn_cast(V))

889 if (CI->isZero())

890 continue;

891

892 break;

893 }

894

895 return I;

896 };

897

898

899

900 Idx = FirstNZIdx(GEPI);

902 return false;

904 return false;

905

908

909

911 return false;

912

914 if (!AllocTy || !AllocTy->isSized())

915 return false;

917 uint64_t TyAllocSize = DL.getTypeAllocSize(AllocTy).getFixedValue();

918

919

920

921

922

923 auto IsAllNonNegative = [&]() {

924 for (unsigned i = Idx+1, e = GEPI->getNumOperands(); i != e; ++i) {

927 continue;

928 return false;

929 }

930

931 return true;

932 };

933

934

935

936

937

938

940 return false;

941

942

943

945 IsAllNonNegative();

946}

947

948

949

950

954 unsigned Idx;

958 ConstantInt::get(GEPI->getOperand(Idx)->getType(), 0));

960 return NewGEPI;

961 }

962 }

963

964 return nullptr;

965}

966

969 return false;

970

971 auto *Ptr = SI.getPointerOperand();

973 Ptr = GEPI->getOperand(0);

974 return (isa(Ptr) &&

976}

977

980 const Value *GEPI0 = GEPI->getOperand(0);

981 if (isa(GEPI0) &&

983 return true;

984 }

985 if (isa(Op) ||

986 (isa(Op) &&

988 return true;

989 return false;

990}

991

996

997

999 return Res;

1000

1001

1004

1006 return Res;

1007

1008

1009

1010

1011 bool IsLoadCSE = false;

1014 if (IsLoadCSE)

1016

1019 LI.getName() + ".cast"));

1020 }

1021

1022

1023

1025

1026

1027

1028

1032 }

1033

1034 if (Op->hasOneUse()) {

1035

1036

1037

1038

1039

1040

1041

1042

1043

1044

1045 if (SelectInst *SI = dyn_cast(Op)) {

1046

1049 Alignment, DL, SI) &&

1051 Alignment, DL, SI)) {

1054 SI->getOperand(1)->getName() + ".val");

1057 SI->getOperand(2)->getName() + ".val");

1061 V2->setAlignment(Alignment);

1063

1064

1068 }

1069

1070

1071 if (isa(SI->getOperand(1)) &&

1075

1076

1077 if (isa(SI->getOperand(2)) &&

1081 }

1082 }

1083 return nullptr;

1084}

1085

1086

1087

1088

1089

1090

1091

1092

1093

1094

1095

1096

1097

1098

1099

1101 Value *U = nullptr;

1102 while (auto *IV = dyn_cast(V)) {

1103 auto *E = dyn_cast(IV->getInsertedValueOperand());

1104 if (!E)

1105 return nullptr;

1106 auto *W = E->getVectorOperand();

1107 if (!U)

1108 U = W;

1109 else if (U != W)

1110 return nullptr;

1111 auto *CI = dyn_cast(E->getIndexOperand());

1112 if (!CI || IV->getNumIndices() != 1 || CI->getZExtValue() != *IV->idx_begin())

1113 return nullptr;

1114 V = IV->getAggregateOperand();

1115 }

1117 return nullptr;

1118

1119 auto *UT = cast(U->getType());

1120 auto *VT = V->getType();

1121

1123 if (DL.getTypeStoreSizeInBits(UT) != DL.getTypeStoreSizeInBits(VT)) {

1124 return nullptr;

1125 }

1126 if (auto *AT = dyn_cast(VT)) {

1127 if (AT->getNumElements() != cast(UT)->getNumElements())

1128 return nullptr;

1129 } else {

1130 auto *ST = cast(VT);

1131 if (ST->getNumElements() != cast(UT)->getNumElements())

1132 return nullptr;

1133 for (const auto *EltT : ST->elements()) {

1134 if (EltT != UT->getElementType())

1135 return nullptr;

1136 }

1137 }

1138 return U;

1139}

1140

1141

1142

1143

1144

1145

1146

1147

1148

1149

1150

1151

1152

1153

1154

1155

1156

1157

1158

1159

1160

1162

1163

1164 if (!SI.isUnordered())

1165 return false;

1166

1167

1168 if (SI.getPointerOperand()->isSwiftError())

1169 return false;

1170

1171 Value *V = SI.getValueOperand();

1172

1173

1174 if (auto *BC = dyn_cast(V)) {

1175 assert(!BC->getType()->isX86_AMXTy() &&

1176 "store to x86_amx* should not happen!");

1177 V = BC->getOperand(0);

1178

1179

1180 if (V->getType()->isX86_AMXTy())

1181 return false;

1184 return true;

1185 }

1186 }

1187

1191 return true;

1192 }

1193

1194

1195

1196 return false;

1197}

1198

1200

1201

1202 if (!SI.isSimple())

1203 return false;

1204

1205 Value *V = SI.getValueOperand();

1206 Type *T = V->getType();

1207

1208 if (->isAggregateType())

1209 return false;

1210

1211 if (auto *ST = dyn_cast(T)) {

1212

1213 unsigned Count = ST->getNumElements();

1214 if (Count == 1) {

1217 return true;

1218 }

1219

1220

1221

1223 auto *SL = DL.getStructLayout(ST);

1224

1225

1226 if (SL->getSizeInBits().isScalable())

1227 return false;

1228

1229 if (SL->hasPadding())

1230 return false;

1231

1232 const auto Align = SI.getAlign();

1233

1235 EltName += ".elt";

1236 auto *Addr = SI.getPointerOperand();

1238 AddrName += ".repack";

1239

1241 auto *Zero = ConstantInt::get(IdxType, 0);

1242 for (unsigned i = 0; i < Count; i++) {

1243 Value *Indices[2] = {

1244 Zero,

1245 ConstantInt::get(IdxType, i),

1246 };

1247 auto *Ptr =

1253 }

1254

1255 return true;

1256 }

1257

1258 if (auto *AT = dyn_cast(T)) {

1259

1260 auto NumElements = AT->getNumElements();

1261 if (NumElements == 1) {

1264 return true;

1265 }

1266

1267

1268

1269

1270

1272 return false;

1273

1275 TypeSize EltSize = DL.getTypeAllocSize(AT->getElementType());

1276 const auto Align = SI.getAlign();

1277

1279 EltName += ".elt";

1280 auto *Addr = SI.getPointerOperand();

1282 AddrName += ".repack";

1283

1285 auto *Zero = ConstantInt::get(IdxType, 0);

1286

1288 for (uint64_t i = 0; i < NumElements; i++) {

1289 Value *Indices[2] = {

1290 Zero,

1291 ConstantInt::get(IdxType, i),

1292 };

1293 auto *Ptr =

1300 }

1301

1302 return true;

1303 }

1304

1305 return false;

1306}

1307

1308

1309

1310

1311

1312

1313

1314

1315

1317

1318 if (A == B) return true;

1319

1320

1321

1322

1323

1324

1325 if (isa(A) ||

1326 isa(A) ||

1327 isa(A) ||

1328 isa(A))

1329 if (Instruction *BI = dyn_cast(B))

1330 if (cast(A)->isIdenticalToWhenDefined(BI))

1331 return true;

1332

1333

1334 return false;

1335}

1336

1338 Value *Val = SI.getOperand(0);

1339 Value *Ptr = SI.getOperand(1);

1340

1341

1344

1345

1348

1349

1352

1353

1354

1355 if (!SI.isUnordered()) return nullptr;

1356

1357

1358

1359 if (Ptr->hasOneUse()) {

1360 if (isa(Ptr))

1363 if (isa(GEP->getOperand(0))) {

1364 if (GEP->getOperand(0)->hasOneUse())

1366 }

1367 }

1368 }

1369

1370

1371

1372

1375

1376

1377

1378

1380 for (unsigned ScanInsts = 6; BBI != SI.getParent()->begin() && ScanInsts;

1381 --ScanInsts) {

1382 --BBI;

1383

1384

1385 if (BBI->isDebugOrPseudoInst()) {

1386 ScanInsts++;

1387 continue;

1388 }

1389

1390 if (StoreInst *PrevSI = dyn_cast(BBI)) {

1391

1392 if (PrevSI->isUnordered() &&

1394 PrevSI->getValueOperand()->getType() ==

1395 SI.getValueOperand()->getType()) {

1396 ++NumDeadStore;

1397

1398

1399

1402 return nullptr;

1403 }

1404 break;

1405 }

1406

1407

1408

1409

1410 if (LoadInst *LI = dyn_cast(BBI)) {

1412 assert(SI.isUnordered() && "can't eliminate ordering operation");

1414 }

1415

1416

1417

1418 break;

1419 }

1420

1421

1422 if (BBI->mayWriteToMemory() || BBI->mayReadFromMemory() || BBI->mayThrow())

1423 break;

1424 }

1425

1426

1427

1429 if (!isa(Val))

1431 return nullptr;

1432 }

1433

1434

1435 if (isa(Ptr)) {

1436

1438 return &SI;

1439

1440

1441

1445 return nullptr;

1446 }

1447

1448

1449

1450

1451 if (isa(Val))

1453

1454 return nullptr;

1455}

1456

1457

1458

1459

1460

1461

1463 if (!SI.isUnordered())

1464 return false;

1465

1466

1467 BasicBlock *StoreBB = SI.getParent();

1470 return false;

1471

1472

1474 if (*PredIter == StoreBB)

1475 ++PredIter;

1477

1478

1479

1480 if (StoreBB == DestBB || OtherBB == DestBB)

1481 return false;

1482

1483

1485 BranchInst *OtherBr = dyn_cast(BBI);

1486 if (!OtherBr || BBI == OtherBB->begin())

1487 return false;

1488

1489 auto OtherStoreIsMergeable = [&](StoreInst *OtherStore) -> bool {

1490 if (!OtherStore ||

1491 OtherStore->getPointerOperand() != SI.getPointerOperand())

1492 return false;

1493

1494 auto *SIVTy = SI.getValueOperand()->getType();

1495 auto *OSVTy = OtherStore->getValueOperand()->getType();

1497 SI.hasSameSpecialState(OtherStore);

1498 };

1499

1500

1501

1502 StoreInst *OtherStore = nullptr;

1504 --BBI;

1505

1506 while (BBI->isDebugOrPseudoInst()) {

1507 if (BBI==OtherBB->begin())

1508 return false;

1509 --BBI;

1510 }

1511

1512

1513 OtherStore = dyn_cast(BBI);

1514 if (!OtherStoreIsMergeable(OtherStore))

1515 return false;

1516 } else {

1517

1518

1521 return false;

1522

1523

1524

1525

1526 for (;; --BBI) {

1527

1528 OtherStore = dyn_cast(BBI);

1529 if (OtherStoreIsMergeable(OtherStore))

1530 break;

1531

1532

1533

1534 if (BBI->mayReadFromMemory() || BBI->mayThrow() ||

1535 BBI->mayWriteToMemory() || BBI == OtherBB->begin())

1536 return false;

1537 }

1538

1539

1540

1542

1543 if (I->mayReadFromMemory() || I->mayThrow() || I->mayWriteToMemory())

1544 return false;

1545 }

1546 }

1547

1548

1550

1553 if (MergedVal != SI.getValueOperand()) {

1555 PHINode::Create(SI.getValueOperand()->getType(), 2, "storemerge");

1556 PN->addIncoming(SI.getValueOperand(), SI.getParent());

1559 OtherBB);

1562 }

1563

1564

1567 new StoreInst(MergedVal, SI.getOperand(1), SI.isVolatile(), SI.getAlign(),

1568 SI.getOrdering(), SI.getSyncScopeID());

1572

1573

1574 AAMDNodes AATags = SI.getAAMetadata();

1575 if (AATags)

1577

1578

1581 return true;

1582}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

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

This file provides internal interfaces used to implement the InstCombine.

static StoreInst * combineStoreToNewValue(InstCombinerImpl &IC, StoreInst &SI, Value *V)

Combine a store to a new type.

static Instruction * combineLoadToOperationType(InstCombinerImpl &IC, LoadInst &Load)

Combine loads to match the type of their uses' value after looking through intervening bitcasts.

static Instruction * replaceGEPIdxWithZero(InstCombinerImpl &IC, Value *Ptr, Instruction &MemI)

static Instruction * simplifyAllocaArraySize(InstCombinerImpl &IC, AllocaInst &AI, DominatorTree &DT)

static bool canSimplifyNullStoreOrGEP(StoreInst &SI)

static bool equivalentAddressValues(Value *A, Value *B)

equivalentAddressValues - Test if A and B will obviously have the same value.

static bool canReplaceGEPIdxWithZero(InstCombinerImpl &IC, GetElementPtrInst *GEPI, Instruction *MemI, unsigned &Idx)

static bool canSimplifyNullLoadOrGEP(LoadInst &LI, Value *Op)

static bool isSupportedAtomicType(Type *Ty)

static bool isDereferenceableForAllocaSize(const Value *V, const AllocaInst *AI, const DataLayout &DL)

Returns true if V is dereferenceable for size of alloca.

static Instruction * unpackLoadToAggregate(InstCombinerImpl &IC, LoadInst &LI)

static cl::opt< unsigned > MaxCopiedFromConstantUsers("instcombine-max-copied-from-constant-users", cl::init(300), cl::desc("Maximum users to visit in copy from constant transform"), cl::Hidden)

static bool combineStoreToValueType(InstCombinerImpl &IC, StoreInst &SI)

Combine stores to match the type of value being stored.

static bool unpackStoreToAggregate(InstCombinerImpl &IC, StoreInst &SI)

static Value * likeBitCastFromVector(InstCombinerImpl &IC, Value *V)

Look for extractelement/insertvalue sequence that acts like a bitcast.

static bool isOnlyCopiedFromConstantMemory(AAResults *AA, AllocaInst *V, MemTransferInst *&TheCopy, SmallVectorImpl< Instruction * > &ToDelete)

isOnlyCopiedFromConstantMemory - Recursively walk the uses of a (derived) pointer to an alloca.

static bool isObjectSizeLessThanOrEq(Value *V, uint64_t MaxSize, const DataLayout &DL)

This file provides the interface for the instcombine pass implementation.

This file implements a map that provides insertion order iteration.

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

This file defines generic set operations that may be used on set's of different types,...

This file defines the SmallString class.

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

#define STATISTIC(VARNAME, DESC)

static const uint32_t IV[8]

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

Returns a bitmask that should be unconditionally applied to the ModRef info of a memory location.

Class for arbitrary precision integers.

APInt zext(unsigned width) const

Zero extend to a new width.

This class represents a conversion between pointers from one address space to another.

an instruction to allocate memory on the stack

Align getAlign() const

Return the alignment of the memory that is being allocated by the instruction.

PointerType * getType() const

Overload to return most specific pointer type.

Type * getAllocatedType() const

Return the type that is being allocated by the instruction.

bool isUsedWithInAlloca() const

Return true if this alloca is used as an inalloca argument to a call.

unsigned getAddressSpace() const

Return the address space for the allocation.

bool isArrayAllocation() const

Return true if there is an allocation size parameter to the allocation instruction that is not 1.

void setAlignment(Align Align)

const Value * getArraySize() const

Get the number of elements allocated.

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

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

const_iterator getFirstInsertionPt() const

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

bool hasNPredecessors(unsigned N) const

Return true if this block has exactly N predecessors.

const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const

Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...

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

Conditional or Unconditional Branch instruction.

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

static bool isBitOrNoopPointerCastable(Type *SrcTy, Type *DestTy, const DataLayout &DL)

Check whether a bitcast, inttoptr, or ptrtoint cast between these types is valid and a no-op.

This is the shared class of boolean and integer constants.

const APInt & getValue() const

Return the constant as an APInt value reference.

static Constant * getNullValue(Type *Ty)

Constructor to create a '0' constant of arbitrary type.

static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)

When two instructions are combined into a single instruction we also need to combine the original loc...

This class represents an Operation in the Expression.

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

IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const

Returns the type of a GEP index in AddressSpace.

TypeSize getTypeAllocSize(Type *Ty) const

Returns the offset in bytes between successive objects of the specified type, including alignment pad...

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

an instruction for type-safe pointer arithmetic to access elements of arrays and structs

bool isInBounds() const

Determine whether the GEP has the inbounds flag.

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

static Type * getIndexedType(Type *Ty, ArrayRef< Value * > IdxList)

Returns the result type of a getelementptr with the given source element type and indexes.

Type * getSourceElementType() const

AllocaInst * CreateAlloca(Type *Ty, unsigned AddrSpace, Value *ArraySize=nullptr, const Twine &Name="")

Value * CreateInsertValue(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &Name="")

LoadInst * CreateAlignedLoad(Type *Ty, Value *Ptr, MaybeAlign Align, const char *Name)

Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")

Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")

ConstantInt * getInt32(uint32_t C)

Get a constant 32-bit value.

Value * CreateBitOrPointerCast(Value *V, Type *DestTy, const Twine &Name="")

LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)

Provided to resolve 'CreateLoad(Ty, Ptr, "...")' correctly, instead of converting the string to 'bool...

Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")

void SetInsertPoint(BasicBlock *TheBB)

This specifies that created instructions should be appended to the end of the specified block.

StoreInst * CreateAlignedStore(Value *Val, Value *Ptr, MaybeAlign Align, bool isVolatile=false)

void handleUnreachableFrom(Instruction *I, SmallVectorImpl< BasicBlock * > &Worklist)

Instruction * visitLoadInst(LoadInst &LI)

void handlePotentiallyDeadBlocks(SmallVectorImpl< BasicBlock * > &Worklist)

Instruction * eraseInstFromFunction(Instruction &I) override

Combiner aware instruction erasure.

Instruction * visitStoreInst(StoreInst &SI)

bool mergeStoreIntoSuccessor(StoreInst &SI)

Try to transform: if () { *P = v1; } else { *P = v2 } or: *P = v1; if () { *P = v2; } into a phi node...

void CreateNonTerminatorUnreachable(Instruction *InsertAt)

Create and insert the idiom we use to indicate a block is unreachable without having to rewrite the C...

bool removeInstructionsBeforeUnreachable(Instruction &I)

LoadInst * combineLoadToNewType(LoadInst &LI, Type *NewTy, const Twine &Suffix="")

Helper to combine a load to a new type.

Instruction * visitAllocSite(Instruction &FI)

Instruction * visitAllocaInst(AllocaInst &AI)

const DataLayout & getDataLayout() const

Instruction * InsertNewInstBefore(Instruction *New, BasicBlock::iterator Old)

Inserts an instruction New before instruction Old.

Instruction * replaceInstUsesWith(Instruction &I, Value *V)

A combiner-aware RAUW-like routine.

uint64_t MaxArraySizeForCombine

Maximum size of array considered when transforming.

InstructionWorklist & Worklist

A worklist of the instructions that need to be simplified.

Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)

Replace operand of instruction and add old operand to the worklist.

void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const

void push(Instruction *I)

Push the instruction onto the worklist stack.

Instruction * clone() const

Create a copy of 'this' instruction that is identical in all ways except the following:

void mergeDIAssignID(ArrayRef< const Instruction * > SourceInstructions)

Merge the DIAssignID metadata from this instruction and those attached to instructions in SourceInstr...

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

void setAAMetadata(const AAMDNodes &N)

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

bool isAtomic() const LLVM_READONLY

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

const Function * getFunction() const

Return the function this instruction belongs to.

BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

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

void setMetadata(unsigned KindID, MDNode *Node)

Set the metadata of the specified kind to the specified node.

AAMDNodes getAAMetadata() const

Returns the AA metadata for this instruction.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())

Copy metadata from SrcInst to this instruction.

void moveBefore(Instruction *MovePos)

Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...

An instruction for reading from memory.

unsigned getPointerAddressSpace() const

Returns the address space of the pointer operand.

void setAlignment(Align Align)

Value * getPointerOperand()

bool isVolatile() const

Return true if this is a load from a volatile memory location.

void setAtomic(AtomicOrdering Ordering, SyncScope::ID SSID=SyncScope::System)

Sets the ordering constraint and the synchronization scope ID of this load instruction.

AtomicOrdering getOrdering() const

Returns the ordering constraint of this load instruction.

SyncScope::ID getSyncScopeID() const

Returns the synchronization scope ID of this load instruction.

Align getAlign() const

Return the alignment of the access that is being performed.

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

This class wraps the llvm.memcpy/memmove intrinsics.

void addIncoming(Value *V, BasicBlock *BB)

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

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

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

PointerIntPair - This class implements a pair of a pointer and small integer.

static PoisonValue * get(Type *T)

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

This class represents the LLVM 'select' instruction.

static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, Instruction *MDFrom=nullptr)

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.

A SetVector that performs no allocations if smaller than a certain size.

SmallString - A SmallString is just a SmallVector with methods and accessors that make it work better...

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

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

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

An instruction for storing to memory.

Value * getValueOperand()

void setAtomic(AtomicOrdering Ordering, SyncScope::ID SSID=SyncScope::System)

Sets the ordering constraint and the synchronization scope ID of this store instruction.

StringRef - Represent a constant reference to a string, i.e.

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

static constexpr TypeSize getZero()

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

unsigned getPointerAddressSpace() const

Get the address space of this pointer or pointer vector type.

bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const

Return true if it makes sense to take the size of this type.

bool isScalableTy(SmallPtrSetImpl< const Type * > &Visited) const

Return true if this is a type whose size is a known multiple of vscale.

bool isFloatingPointTy() const

Return true if this is one of the floating-point types.

bool isPtrOrPtrVectorTy() const

Return true if this is a pointer type or a vector of pointer types.

bool isX86_AMXTy() const

Return true if this is X86 AMX.

bool isIntOrPtrTy() const

Return true if this is an integer type or a pointer type.

static IntegerType * getInt32Ty(LLVMContext &C)

static IntegerType * getInt64Ty(LLVMContext &C)

bool isIntegerTy() const

True if this is an instance of IntegerType.

void setOperand(unsigned i, Value *Val)

Value * getOperand(unsigned i) const

unsigned getNumOperands() const

LLVM Value Representation.

Type * getType() const

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

void replaceAllUsesWith(Value *V)

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

iterator_range< use_iterator > uses()

StringRef getName() const

Return a constant reference to the value's name.

constexpr ScalarTy getFixedValue() const

constexpr bool isScalable() const

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

constexpr ScalarTy getKnownMinValue() const

Returns the minimum value this quantity can represent.

const ParentTy * getParent() const

self_iterator getIterator()

#define llvm_unreachable(msg)

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

@ C

The default llvm calling convention, compatible with C.

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

auto m_Undef()

Match an arbitrary undef constant.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

bool isDereferenceableAndAlignedPointer(const Value *V, Type *Ty, Align Alignment, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)

Returns true if V is always a dereferenceable pointer with alignment greater or equal than requested.

void copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source)

Copy the metadata from the source instruction to the destination (the replacement for the source inst...

bool set_is_subset(const S1Ty &S1, const S2Ty &S2)

set_is_subset(A, B) - Return true iff A in B

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

Wrapper function to append range R to container C.

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

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

bool any_of(R &&range, UnaryPredicate P)

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

Align getOrEnforceKnownAlignment(Value *V, MaybeAlign PrefAlign, const DataLayout &DL, const Instruction *CxtI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)

Try to ensure that the alignment of V is at least PrefAlign bytes.

bool isModSet(const ModRefInfo MRI)

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

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

bool isSafeToLoadUnconditionally(Value *V, Align Alignment, const APInt &Size, const DataLayout &DL, Instruction *ScanFrom, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)

Return true if we know that executing a load from this value cannot trap.

raw_ostream & dbgs()

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

bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT)

Point debug users of From to To or salvage them.

Value * simplifyLoadInst(LoadInst *LI, Value *PtrOp, const SimplifyQuery &Q)

Given a load instruction and its pointer operand, fold the result or return null.

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

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

void replace(R &&Range, const T &OldValue, const T &NewValue)

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

auto pred_begin(const MachineBasicBlock *BB)

Align commonAlignment(Align A, uint64_t Offset)

Returns the alignment that satisfies both alignments.

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

AAMDNodes merge(const AAMDNodes &Other) const

Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...

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

bool isNonNegative() const

Returns true if this value is known to be non-negative.

SimplifyQuery getWithInstruction(const Instruction *I) const