InstCombinePHI.cpp Source File (original) (raw)

23#include

25using namespace llvm;

28#define DEBUG_TYPE "instcombine"

32 cl::desc("Maximum number phis to handle in intptr/ptrint folding"));

35 "Number of phi-of-insertvalue turned into insertvalue-of-phis");

37 "Number of phi-of-extractvalue turned into extractvalue-of-phi");

38 STATISTIC(NumPHICSEs, "Number of PHI's that got CSE'd");

45 Inst->setDebugLoc(FirstInst->getDebugLoc());

48 assert(!isa(Inst));

51 auto *I = cast(V);

53 }

54}

62 Stack.push_back(&PN);

63 while (!Stack.empty()) {

64 PHINode *Phi = Stack.pop_back_val();

65 if (!Visited.insert(Phi).second)

66 continue;

68 if (Visited.size() == 16)

69 return false;

70 for (User *Use : Phi->users()) {

71 if (PHINode *PhiUse = dyn_cast(Use))

72 Stack.push_back(PhiUse);

73 else

74 return false;

75 }

76 }

77 for (PHINode *Phi : Visited)

79 for (PHINode *Phi : Visited)

81 return true;

82}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

136 return false;

138 return false;

139

140 auto *IntToPtr = dyn_cast(PN.user_back());

141 if (!IntToPtr)

142 return false;

143

144

145 auto HasPointerUse = [](Instruction *IIP) {

146 for (User *U : IIP->users()) {

148 if (LoadInst *LoadI = dyn_cast(U)) {

149 Ptr = LoadI->getPointerOperand();

150 } else if (StoreInst *SI = dyn_cast(U)) {

151 Ptr = SI->getPointerOperand();

152 } else if (GetElementPtrInst *GI = dyn_cast(U)) {

153 Ptr = GI->getPointerOperand();

154 }

155

156 if (Ptr && Ptr == IIP)

157 return true;

158 }

159 return false;

160 };

161

162 if (!HasPointerUse(IntToPtr))

163 return false;

164

167 return false;

168

173

174

175 if (!isa(Arg) && !isa(Arg))

176 return false;

177

178

179 if (auto *PI = dyn_cast(Arg)) {

180 AvailablePtrVals.emplace_back(PI->getOperand(0));

181 continue;

182 }

183

184

185 Value *ArgIntToPtr = nullptr;

187 if (isa(U) && U->getType() == IntToPtr->getType() &&

188 (DT.dominates(cast(U), BB) ||

189 cast(U)->getParent() == BB)) {

190 ArgIntToPtr = U;

191 break;

192 }

193 }

194

195 if (ArgIntToPtr) {

197 continue;

198 }

199

200

201

202 if (isa(Arg)) {

204 continue;

205 }

206

207

208 auto *LoadI = dyn_cast(Arg);

209 if (!LoadI)

210 return false;

211

212 if (!LoadI->hasOneUse())

213 return false;

214

215

216

217

219 }

220

221

224 "Not enough available ptr typed incoming values");

225 PHINode *MatchingPtrPHI = nullptr;

226 unsigned NumPhis = 0;

227 for (PHINode &PtrPHI : BB->phis()) {

228

230 return false;

231 if (&PtrPHI == &PN || PtrPHI.getType() != IntToPtr->getType())

232 continue;

234 [&](const auto &BlockAndValue) {

235 BasicBlock *BB = std::get<0>(BlockAndValue);

236 Value *V = std::get<1>(BlockAndValue);

237 return PtrPHI.getIncomingValueForBlock(BB) != V;

238 }))

239 continue;

240 MatchingPtrPHI = &PtrPHI;

241 break;

242 }

243

244 if (MatchingPtrPHI) {

245 assert(MatchingPtrPHI->getType() == IntToPtr->getType() &&

246 "Phi's Type does not match with IntToPtr");

247

248

252 return true;

253 }

254

255

256 if (all_of(AvailablePtrVals, [&](Value *V) {

257 return (V->getType() != IntToPtr->getType()) || isa(V);

258 }))

259 return false;

260

261

262

263

264

265 if (any_of(AvailablePtrVals, [&](Value *V) {

266 if (V->getType() == IntToPtr->getType())

267 return false;

268 auto *Inst = dyn_cast(V);

269 if (!Inst)

270 return false;

271 if (Inst->isTerminator())

272 return true;

273 auto *BB = Inst->getParent();

274 if (isa(Inst) && BB->getFirstInsertionPt() == BB->end())

275 return true;

276 return false;

277 }))

278 return false;

279

282

286 auto *IncomingBB = std::get<0>(Incoming);

287 auto *IncomingVal = std::get<1>(Incoming);

288

289 if (IncomingVal->getType() == IntToPtr->getType()) {

290 NewPtrPHI->addIncoming(IncomingVal, IncomingBB);

291 continue;

292 }

293

294#ifndef NDEBUG

295 LoadInst *LoadI = dyn_cast(IncomingVal);

296 assert((isa(IncomingVal) ||

297 IncomingVal->getType()->isPointerTy() ||

298 (LoadI && LoadI->hasOneUse())) &&

299 "Can not replace LoadInst with multiple uses");

300#endif

301

302

303

304

305

306

307

308

310 if (!CI) {

312 IncomingVal->getName() + ".ptr");

313 if (auto *IncomingI = dyn_cast(IncomingVal)) {

315 InsertPos++;

317 if (isa(IncomingI))

319 assert(InsertPos != BB->end() && "should have checked above");

321 } else {

322 auto *InsertBB = &IncomingBB->getParent()->getEntryBlock();

324 }

325 }

327 }

328

329

330

334 return true;

335}

336

337

338

340

341

342 if ( $all\_of$ (PN.users(), [](User *U) { return isa(U); }))

343 return nullptr;

344

345

346

347 bool OperandWithRoundTripCast = false;

349 if (auto *NewOp =

352 OperandWithRoundTripCast = true;

353 }

354 }

355 if (!OperandWithRoundTripCast)

356 return nullptr;

357 return &PN;

358}

359

360

361

364 auto *FirstIVI = cast(PN.getIncomingValue(0));

365

366

367

369 auto *I = dyn_cast(V);

370 if ( || ->hasOneUser() || I->getIndices() != FirstIVI->getIndices())

371 return nullptr;

372 }

373

374

375 std::array<PHINode *, 2> NewOperands;

376 for (int OpIdx : {0, 1}) {

377 auto *&NewOperand = NewOperands[OpIdx];

378

379

382 FirstIVI->getOperand(OpIdx)->getName() + ".pn");

383

385 NewOperand->addIncoming(

386 cast(std::get<1>(Incoming))->getOperand(OpIdx),

389 }

390

391

393 FirstIVI->getIndices(), PN.getName());

394

396 ++NumPHIsOfInsertValues;

397 return NewIVI;

398}

399

400

401

404 auto *FirstEVI = cast(PN.getIncomingValue(0));

405

406

407

409 auto *I = dyn_cast(V);

410 if ( || ->hasOneUser() || I->getIndices() != FirstEVI->getIndices() ||

411 I->getAggregateOperand()->getType() !=

412 FirstEVI->getAggregateOperand()->getType())

413 return nullptr;

414 }

415

416

417

420 FirstEVI->getAggregateOperand()->getName() + ".pn");

421

423 NewAggregateOperand->addIncoming(

424 cast(std::get<1>(Incoming))->getAggregateOperand(),

427

428

430 FirstEVI->getIndices(), PN.getName());

431

433 ++NumPHIsOfExtractValues;

434 return NewEVI;

435}

436

437

438

441 assert(isa(FirstInst) || isa(FirstInst));

442 unsigned Opc = FirstInst->getOpcode();

445

448

449

452 if ( || I->getOpcode() != Opc || ->hasOneUser() ||

453

454

455 I->getOperand(0)->getType() != LHSType ||

456 I->getOperand(1)->getType() != RHSType)

457 return nullptr;

458

459

460 if (CmpInst *CI = dyn_cast(I))

461 if (CI->getPredicate() != cast(FirstInst)->getPredicate())

462 return nullptr;

463

464

465 if (I->getOperand(0) != LHSVal) LHSVal = nullptr;

466 if (I->getOperand(1) != RHSVal) RHSVal = nullptr;

467 }

468

469

470

471

472

473 if (!LHSVal && !RHSVal)

474 return nullptr;

475

476

477

480 PHINode *NewLHS = nullptr, *NewRHS = nullptr;

481 if (!LHSVal) {

486 LHSVal = NewLHS;

487 }

488

489 if (!RHSVal) {

494 RHSVal = NewRHS;

495 }

496

497

498 if (NewLHS || NewRHS) {

502 Instruction *InInst = cast(InVal);

503 if (NewLHS) {

506 }

507 if (NewRHS) {

509 NewRHS->addIncoming(NewInRHS, InBB);

510 }

511 }

512 }

513

514 if (CmpInst *CIOp = dyn_cast(FirstInst)) {

516 LHSVal, RHSVal);

518 return NewCI;

519 }

520

521 BinaryOperator *BinOp = cast(FirstInst);

524

526

529

531 return NewBinOp;

532}

533

536

538 FirstInst->op_end());

539

540

541 bool AllBasePointersAreAllocas = true;

542

543

544

545

546 bool NeededPhi = false;

547

548

550

551

554 if ( GEP || GEP ->hasOneUser() ||

557 return nullptr;

558

559 NW &= GEP->getNoWrapFlags();

560

561

562 if (AllBasePointersAreAllocas &&

563 (!isa(GEP->getOperand(0)) ||

564 GEP ->hasAllConstantIndices()))

565 AllBasePointersAreAllocas = false;

566

567

570 continue;

571

572

573

574

575

576

577 if (isa(FirstInst->getOperand(Op)) ||

578 isa(GEP->getOperand(Op)))

579 return nullptr;

580

582 GEP->getOperand(Op)->getType())

583 return nullptr;

584

585

586

587

588

589 if (NeededPhi)

590 return nullptr;

591

592 FixedOperands[Op] = nullptr;

593 NeededPhi = true;

594 }

595 }

596

597

598

599

600

601

602

603 if (AllBasePointersAreAllocas)

604 return nullptr;

605

606

607

609

610 bool HasAnyPHIs = false;

611 for (unsigned I = 0, E = FixedOperands.size(); I != E; ++I) {

612 if (FixedOperands[I])

613 continue;

618

620 OperandPhis[I] = NewPN;

621 FixedOperands[I] = NewPN;

622 HasAnyPHIs = true;

623 }

624

625

626 if (HasAnyPHIs) {

631

632 for (unsigned Op = 0, E = OperandPhis.size(); Op != E; ++Op)

633 if (PHINode *OpPhi = OperandPhis[Op])

634 OpPhi->addIncoming(InGEP->getOperand(Op), InBB);

635 }

636 }

637

641 ArrayRef(FixedOperands).slice(1), NW);

643 return NewGEP;

644}

645

646

647

648

649

650

651

652

655

656 for (++BBI; BBI != E; ++BBI)

657 if (BBI->mayWriteToMemory()) {

658

659

660 if (auto *CB = dyn_cast(BBI))

661 if (CB->onlyAccessesInaccessibleMemory())

662 continue;

663 return false;

664 }

665

666

667

668 if (AllocaInst *AI = dyn_cast(L->getOperand(0))) {

669 bool IsAddressTaken = false;

670 for (User *U : AI->users()) {

671 if (isa(U)) continue;

672 if (StoreInst *SI = dyn_cast(U)) {

673

674 if (SI->getOperand(1) == AI) continue;

675 }

676 IsAddressTaken = true;

677 break;

678 }

679

680 if (!IsAddressTaken && AI->isStaticAlloca())

681 return false;

682 }

683

684

685

686

687

688

690 if (AllocaInst *AI = dyn_cast(GEP->getOperand(0)))

691 if (AI->isStaticAlloca() && GEP->hasAllConstantIndices())

692 return false;

693

694 return true;

695}

696

699

700

702 return nullptr;

703

704

705

707 return nullptr;

708

709

710

711 bool IsVolatile = FirstLI->isVolatile();

714

715

716

719 return nullptr;

720

721

722

723

724 if (IsVolatile &&

725 FirstLI->getParent()->getTerminator()->getNumSuccessors() != 1)

726 return nullptr;

727

731 LoadInst *LI = dyn_cast(InVal);

733 return nullptr;

734

735

736 if (LI->isVolatile() != IsVolatile ||

738 return nullptr;

739

740

742 return nullptr;

743

744

745

747 return nullptr;

748

749 LoadAlignment = std::min(LoadAlignment, LI->getAlign());

750

751

752

753

754 if (IsVolatile && LI->getParent()->getTerminator()->getNumSuccessors() != 1)

755 return nullptr;

756 }

757

758

759

763

767 new LoadInst(FirstLI->getType(), NewPN, "", IsVolatile, LoadAlignment);

769

770

774 LoadInst *LI = cast(V);

777 if (NewInVal != InVal)

778 InVal = nullptr;

780 }

781

782 if (InVal) {

783

784

786 delete NewPN;

787 } else {

789 }

790

791

792

793

794 if (IsVolatile)

796 cast(IncValue)->setVolatile(false);

797

799 return NewLI;

800}

801

802

803

804

806

807

808 if (Instruction *TI = Phi.getParent()->getTerminator())

809 if (TI->isEHPad())

810 return nullptr;

811

812

813

814

815 unsigned NumIncomingValues = Phi.getNumIncomingValues();

816 if (NumIncomingValues < 3)

817 return nullptr;

818

819

820 Type *NarrowType = nullptr;

821 for (Value *V : Phi.incoming_values()) {

822 if (auto *Zext = dyn_cast(V)) {

823 NarrowType = Zext->getSrcTy();

824 break;

825 }

826 }

827 if (!NarrowType)

828 return nullptr;

829

830

831

833 unsigned NumZexts = 0;

834 unsigned NumConsts = 0;

835 for (Value *V : Phi.incoming_values()) {

836 if (auto *Zext = dyn_cast(V)) {

837

838 if (Zext->getSrcTy() != NarrowType || !Zext->hasOneUser())

839 return nullptr;

840 NewIncoming.push_back(Zext->getOperand(0));

841 NumZexts++;

842 } else if (auto *C = dyn_cast(V)) {

843

845 if (!Trunc)

846 return nullptr;

848 NumConsts++;

849 } else {

850

851 return nullptr;

852 }

853 }

854

855

856

857

858

859

860

861 if (NumConsts == 0 || NumZexts < 2)

862 return nullptr;

863

864

865

866

868 Phi.getName() + ".shrunk");

869 for (unsigned I = 0; I != NumIncomingValues; ++I)

870 NewPhi->addIncoming(NewIncoming[I], Phi.getIncomingBlock(I));

871

874}

875

876

877

878

880

881

883 if (TI->isEHPad())

884 return nullptr;

885

887

888 if (isa(FirstInst))

890 if (isa(FirstInst))

892 if (isa(FirstInst))

894 if (isa(FirstInst))

896

897

898

899

900

901 Constant *ConstantOp = nullptr;

902 Type *CastSrcTy = nullptr;

903

904 if (isa(FirstInst)) {

906

907

908

910 if (!shouldChangeType(PN.getType(), CastSrcTy))

911 return nullptr;

912 }

913 } else if (isa(FirstInst) || isa(FirstInst)) {

914

915

916 ConstantOp = dyn_cast(FirstInst->getOperand(1));

917 if (!ConstantOp)

919 } else {

920 return nullptr;

921 }

922

923

926 if ( || ->hasOneUser() || ->isSameOperationAs(FirstInst))

927 return nullptr;

928 if (CastSrcTy) {

929 if (I->getOperand(0)->getType() != CastSrcTy)

930 return nullptr;

931 } else if (I->getOperand(1) != ConstantOp) {

932 return nullptr;

933 }

934 }

935

936

937

941

944

945

949 Value *NewInVal = cast(V)->getOperand(0);

950 if (NewInVal != InVal)

951 InVal = nullptr;

953 }

954

956 if (InVal) {

957

958

959 PhiVal = InVal;

960 delete NewPN;

961 } else {

963 PhiVal = NewPN;

964 }

965

966

967 if (CastInst *FirstCI = dyn_cast(FirstInst)) {

971 return NewCI;

972 }

973

974 if (BinaryOperator *BinOp = dyn_cast(FirstInst)) {

977

979 BinOp->andIRFlags(V);

980

982 return BinOp;

983 }

984

985 CmpInst *CIOp = cast(FirstInst);

987 PhiVal, ConstantOp);

989 return NewCI;

990}

991

992

993

994

997

998 if (!ValueEqualPHIs.insert(PN).second)

999 return true;

1000

1001

1002 if (ValueEqualPHIs.size() == 16)

1003 return false;

1004

1005

1006

1008 if (PHINode *OpPN = dyn_cast(Op)) {

1009 if ( PHIsEqualValue (OpPN, NonPhiInVal, ValueEqualPHIs)) {

1010 if (NonPhiInVal)

1011 return false;

1012 NonPhiInVal = OpPN;

1013 }

1014 } else if (Op != NonPhiInVal)

1015 return false;

1016 }

1017

1018 return true;

1019}

1020

1021

1022

1024 assert(isa(PN.getType()) && "Expect only integer type phi");

1026 if (auto *ConstVA = dyn_cast(V))

1027 if (!ConstVA->isZero())

1028 return ConstVA;

1029 return ConstantInt::get(cast(PN.getType()), 1);

1030}

1031

1032namespace {

1033struct PHIUsageRecord {

1034 unsigned PHIId;

1035 unsigned Shift;

1036 Instruction *Inst;

1037

1038 PHIUsageRecord(unsigned Pn, unsigned Sh, Instruction *User)

1039 : PHIId(Pn), Shift(Sh), Inst(User) {}

1040

1041 bool operator<(const PHIUsageRecord &RHS) const {

1042 if (PHIId < RHS.PHIId) return true;

1043 if (PHIId > RHS.PHIId) return false;

1044 if (Shift < RHS.Shift) return true;

1045 if (Shift > RHS.Shift) return false;

1048 }

1049};

1050

1051struct LoweredPHIRecord {

1052 PHINode *PN;

1053 unsigned Shift;

1054 unsigned Width;

1055

1056 LoweredPHIRecord(PHINode *Phi, unsigned Sh, Type *Ty)

1057 : PN(Phi), Shift(Sh), Width(Ty->getPrimitiveSizeInBits()) {}

1058

1059

1060 LoweredPHIRecord(PHINode *Phi, unsigned Sh) : PN(Phi), Shift(Sh), Width(0) {}

1061};

1062}

1063

1064namespace llvm {

1065 template<>

1068 return LoweredPHIRecord(nullptr, 0);

1069 }

1071 return LoweredPHIRecord(nullptr, 1);

1072 }

1075 (Val.Width>>3);

1076 }

1077 static bool isEqual(const LoweredPHIRecord &LHS,

1078 const LoweredPHIRecord &RHS) {

1079 return LHS.PN == RHS.PN && LHS.Shift == RHS.Shift &&

1080 LHS.Width == RHS.Width;

1081 }

1082 };

1083}

1084

1085

1086

1087

1088

1089

1090

1091

1092

1093

1095

1096

1098

1099

1100

1101

1102

1105

1106 PHIsToSlice.push_back(&FirstPhi);

1107 PHIsInspected.insert(&FirstPhi);

1108

1109 for (unsigned PHIId = 0; PHIId != PHIsToSlice.size(); ++PHIId) {

1110 PHINode *PN = PHIsToSlice[PHIId];

1111

1112

1113

1114

1115

1120 if ()

1121 continue;

1122 if (II->getParent() != BB)

1123 continue;

1124

1125

1126

1127

1128 return nullptr;

1129 }

1130

1131

1132

1133

1134 for (auto *Pred : PN->blocks())

1135 if (Pred->getFirstInsertionPt() == Pred->end())

1136 return nullptr;

1137

1139 Instruction *UserI = cast(U);

1140

1141

1142 if (PHINode *UserPN = dyn_cast(UserI)) {

1143 if (PHIsInspected.insert(UserPN).second)

1145 continue;

1146 }

1147

1148

1149 if (isa(UserI)) {

1150 PHIUsers.push_back(PHIUsageRecord(PHIId, 0, UserI));

1151 continue;

1152 }

1153

1154

1155 if (UserI->getOpcode() != Instruction::LShr ||

1157 !isa(UserI->getOperand(1)))

1158 return nullptr;

1159

1160

1162 if (cast(UserI->getOperand(1))->getValue().uge(SizeInBits))

1163 return nullptr;

1164

1165 unsigned Shift = cast(UserI->getOperand(1))->getZExtValue();

1166 PHIUsers.push_back(PHIUsageRecord(PHIId, Shift, UserI->user_back()));

1167 }

1168 }

1169

1170

1171 if (PHIUsers.empty())

1173

1174

1175

1177

1178 LLVM_DEBUG(dbgs() << "SLICING UP PHI: " << FirstPhi << '\n';

1179 for (unsigned I = 1; I != PHIsToSlice.size(); ++I) dbgs()

1180 << "AND USER PHI #" << I << ": " << *PHIsToSlice[I] << '\n');

1181

1182

1183

1185

1186

1187

1189

1190 for (unsigned UserI = 0, UserE = PHIUsers.size(); UserI != UserE; ++UserI) {

1191 unsigned PHIId = PHIUsers[UserI].PHIId;

1192 PHINode *PN = PHIsToSlice[PHIId];

1193 unsigned Offset = PHIUsers[UserI].Shift;

1194 Type *Ty = PHIUsers[UserI].Inst->getType();

1195

1197

1198

1199

1200 if ((EltPHI = ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)]) == nullptr) {

1201

1202

1207 "Truncate didn't shrink phi?");

1208

1212 Value *&PredVal = PredValues[Pred];

1213

1214

1215 if (PredVal) {

1217 continue;

1218 }

1219

1220

1221 if (InVal == PN) {

1222 PredVal = EltPHI;

1224 continue;

1225 }

1226

1227 if (PHINode *InPHI = dyn_cast(PN)) {

1228

1229

1230 if (Value *Res = ExtractedVals[LoweredPHIRecord(InPHI, Offset, Ty)]) {

1231 PredVal = Res;

1233 continue;

1234 }

1235 }

1236

1237

1239 Value *Res = InVal;

1242 Res, ConstantInt::get(InVal->getType(), Offset), "extract");

1244 PredVal = Res;

1246

1247

1248

1249

1250

1251 if (PHINode *OldInVal = dyn_cast(InVal))

1252 if (PHIsInspected.count(OldInVal)) {

1253 unsigned RefPHIId =

1254 find(PHIsToSlice, OldInVal) - PHIsToSlice.begin();

1256 PHIUsageRecord(RefPHIId, Offset, cast(Res)));

1257 ++UserE;

1258 }

1259 }

1260 PredValues.clear();

1261

1263 << *EltPHI << '\n');

1264 ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)] = EltPHI;

1265 }

1266

1267

1269 }

1270

1271

1272

1277}

1278

1281

1282

1283

1284

1285

1286

1287

1288

1289

1290

1291

1292

1293

1294 if ( $all\_of$ (PN.operands(), [](Value *V) { return isa(V); }))

1295 return nullptr;

1296

1298

1300 return nullptr;

1301

1302

1309 SuccForValue[C] = Succ;

1310 ++SuccCount[Succ];

1311 };

1312 if (auto *BI = dyn_cast(IDom->getTerminator())) {

1313 if (BI->isUnconditional())

1314 return nullptr;

1315

1316 Cond = BI->getCondition();

1319 } else if (auto *SI = dyn_cast(IDom->getTerminator())) {

1320 Cond = SI->getCondition();

1321 ++SuccCount[SI->getDefaultDest()];

1322 for (auto Case : SI->cases())

1323 AddSucc(Case.getCaseValue(), Case.getCaseSuccessor());

1324 } else {

1325 return nullptr;

1326 }

1327

1329 return nullptr;

1330

1331

1332

1333 std::optional Invert;

1335 auto *Input = cast(std::get<0>(Pair));

1336 BasicBlock *Pred = std::get<1>(Pair);

1337 auto IsCorrectInput = [&](ConstantInt *Input) {

1338

1339

1340

1341 auto It = SuccForValue.find(Input);

1342 return It != SuccForValue.end() && SuccCount[It->second] == 1 &&

1345 };

1346

1347

1348 bool NeedsInvert;

1349 if (IsCorrectInput(Input))

1350 NeedsInvert = false;

1352 NeedsInvert = true;

1353 else

1354 return nullptr;

1355

1356

1357 if (Invert && *Invert != NeedsInvert)

1358 return nullptr;

1359

1360 Invert = NeedsInvert;

1361 }

1362

1363 if (!*Invert)

1364 return Cond;

1365

1366

1367

1368

1370 if (InsertPt != BB->end()) {

1373 }

1374

1375 return nullptr;

1376}

1377

1378

1379

1380

1381

1385 return nullptr;

1386

1390 auto MatchOuterIV = [&](Value *V1, Value *V2) {

1393 Start = V1;

1394 IvNext = cast(V2);

1395 return true;

1396 }

1397 return false;

1398 };

1399

1402 return nullptr;

1403

1405 Value *Iv2Start, *Iv2Step;

1408 return nullptr;

1409

1410 auto *BO = dyn_cast(IvNext);

1414 if (Iv2Start != Identity)

1415 return nullptr;

1416

1418 if (!BO) {

1419 auto *GEP = cast(IvNext);

1420 return Builder.CreateGEP(GEP->getSourceElementType(), Start, Iv2, "",

1421 cast(IvNext)->getNoWrapFlags());

1422 }

1423

1424 assert(BO->isCommutative() && "Must be commutative");

1425 Value *Res = Builder.CreateBinOp(BO->getOpcode(), Iv2, Start);

1426 cast(Res)->copyIRFlags(BO);

1427 return Res;

1428}

1429

1430

1431

1435

1437 return Result;

1438

1440 return Result;

1441

1442

1443

1444 auto *Inst0 = dyn_cast(PN.getIncomingValue(0));

1445 auto *Inst1 = dyn_cast(PN.getIncomingValue(1));

1446 if (Inst0 && Inst1 && Inst0->getOpcode() == Inst1->getOpcode() &&

1447 Inst0->hasOneUser())

1449 return Result;

1450

1451

1452

1457

1458

1460 CheckedIVs.insert(IV0);

1461 if (IV0 != IV0Stripped &&

1463 return !CheckedIVs.insert(IV).second ||

1464 IV0Stripped == IV->stripPointerCasts();

1465 })) {

1467 }

1468 }

1469

1471 return nullptr;

1472

1473

1476 return nullptr;

1477

1478

1479

1480

1481

1482

1483

1486 (isa(PHIUser) || isa(PHIUser) ||

1487 isa(PHIUser)) &&

1490 }

1491 }

1492

1493

1494

1495

1496

1497

1498

1499

1500

1501

1502

1503

1504

1507 bool AllUsesOfPhiEndsInCmp = all_of(PN.users(), [&](User *U) {

1508 auto *CmpInst = dyn_cast(U);

1509 if (!CmpInst) {

1510

1511

1512 if (U->hasOneUse() && match(U, m_c_Or(m_Specific(&PN), m_Value()))) {

1513 DropPoisonFlags.push_back(cast(U));

1514 CmpInst = dyn_cast(U->user_back());

1515 }

1516 }

1519 return false;

1520 }

1521 return true;

1522 });

1523

1524 if (AllUsesOfPhiEndsInCmp) {

1526 bool MadeChange = false;

1531 if (!NonZeroConst)

1533 if (NonZeroConst != VA) {

1535

1537 I->dropPoisonGeneratingFlags();

1538 MadeChange = true;

1539 }

1540 }

1541 }

1542 if (MadeChange)

1543 return &PN;

1544 }

1545 }

1546

1547

1548

1549

1550

1551

1552

1553

1554

1555 {

1557

1558 while (InValNo != NumIncomingVals &&

1559 isa(PN.getIncomingValue(InValNo)))

1560 ++InValNo;

1561

1562 Value *NonPhiInVal =

1563 InValNo != NumIncomingVals ? PN.getIncomingValue(InValNo) : nullptr;

1564

1565

1566

1567 if (NonPhiInVal)

1568 for (++InValNo; InValNo != NumIncomingVals; ++InValNo) {

1569 Value *OpVal = PN.getIncomingValue(InValNo);

1570 if (OpVal != NonPhiInVal && !isa(OpVal))

1571 break;

1572 }

1573

1574

1575

1576

1577 if (InValNo == NumIncomingVals) {

1579 if (PHIsEqualValue(&PN, NonPhiInVal, ValueEqualPHIs))

1580 return replaceInstUsesWith(PN, NonPhiInVal);

1581 }

1582 }

1583

1584

1585

1586

1587

1588 auto Res = PredOrder.try_emplace(PN.getParent());

1589 if (!Res.second) {

1590 const auto &Preds = Res.first->second;

1591 for (unsigned I = 0, E = PN.getNumIncomingValues(); I != E; ++I) {

1592 BasicBlock *BBA = PN.getIncomingBlock(I);

1594 if (BBA != BBB) {

1595 Value *VA = PN.getIncomingValue(I);

1596 unsigned J = PN.getBasicBlockIndex(BBB);

1597 Value *VB = PN.getIncomingValue(J);

1598 PN.setIncomingBlock(I, BBB);

1599 PN.setIncomingValue(I, VB);

1600 PN.setIncomingBlock(J, BBA);

1601 PN.setIncomingValue(J, VA);

1602

1603

1604

1605

1606 }

1607 }

1608 } else {

1609

1610 append_range(Res.first->second, PN.blocks());

1611 }

1612

1613

1615

1616 if (&IdenticalPN == &PN)

1617 continue;

1618

1619

1620

1621 if (!PN.isIdenticalToWhenDefined(&IdenticalPN))

1622 continue;

1623

1624 ++NumPHICSEs;

1625 return replaceInstUsesWith(PN, &IdenticalPN);

1626 }

1627

1628

1629

1630

1631

1632 if (PN.getType()->isIntegerTy() &&

1633 .isLegalInteger(PN.getType()->getPrimitiveSizeInBits()))

1634 if (Instruction *Res = SliceUpIllegalIntegerPHI(PN))

1635 return Res;

1636

1637

1639 return replaceInstUsesWith(PN, V);

1640

1642 return replaceInstUsesWith(PN, Res);

1643

1644 return nullptr;

1645}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

This file provides internal interfaces used to implement the InstCombine.

static ConstantInt * getAnyNonZeroConstInt(PHINode &PN)

Return an existing non-zero constant if this phi node has one, otherwise return constant 1.

static Value * foldDependentIVs(PHINode &PN, IRBuilderBase &Builder)

static bool isSafeAndProfitableToSinkLoad(LoadInst *L)

Return true if we know that it is safe to sink the load out of the block that defines it.

static Value * simplifyUsingControlFlow(InstCombiner &Self, PHINode &PN, const DominatorTree &DT)

static bool PHIsEqualValue(PHINode *PN, Value *&NonPhiInVal, SmallPtrSetImpl< PHINode * > &ValueEqualPHIs)

Return true if this phi node is always equal to NonPhiInVal.

static cl::opt< unsigned > MaxNumPhis("instcombine-max-num-phis", cl::init(512), cl::desc("Maximum number phis to handle in intptr/ptrint folding"))

This file provides the interface for the instcombine pass implementation.

uint64_t IntrinsicInst * II

const SmallVectorImpl< MachineOperand > & Cond

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

This file defines the SmallPtrSet 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]

an instruction to allocate memory on the stack

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

LLVM Basic Block Representation.

const_iterator getFirstInsertionPt() const

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

const Function * getParent() const

Return the enclosing method, or null if none.

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

BinaryOps getOpcode() const

static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)

Construct a binary instruction, given the opcode and the two operands.

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

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

Create a BitCast, AddrSpaceCast or a PtrToInt cast instruction.

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

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

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

Create a ZExt or BitCast cast instruction.

static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)

Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...

This class is the base class for the comparison instructions.

static bool isEquality(Predicate pred)

Determine if this is an equals/not equals predicate.

static CmpInst * Create(OtherOps Op, Predicate Pred, Value *S1, Value *S2, const Twine &Name="", InsertPosition InsertBefore=nullptr)

Construct a compare instruction, given the opcode, the predicate and the two operands.

Predicate getPredicate() const

Return the predicate for this instruction.

OtherOps getOpcode() const

Get the opcode casted to the right type.

static Constant * getNot(Constant *C)

static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)

Return the identity constant for a binary opcode.

This is the shared class of boolean and integer constants.

static ConstantInt * getTrue(LLVMContext &Context)

static ConstantInt * getFalse(LLVMContext &Context)

This is an important base class in LLVM.

static Constant * getNullValue(Type *Ty)

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

This class represents an Operation in the Expression.

unsigned getPointerSizeInBits(unsigned AS=0) const

Layout pointer size, in bits FIXME: The defaults need to be removed once all of the backends/clients ...

TypeSize getTypeSizeInBits(Type *Ty) const

Size examples:

iterator find(const_arg_type_t< KeyT > Val)

DomTreeNodeBase * getIDom() const

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

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

bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

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

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

Represents flags for the getelementptr instruction/expression.

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

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

Type * getSourceElementType() const

GEPNoWrapFlags getNoWrapFlags() const

Get the nowrap flags for the GEP instruction.

Common base class shared among various IRBuilders.

Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)

Value * CreateGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="", GEPNoWrapFlags NW=GEPNoWrapFlags::none())

Value * CreateNot(Value *V, const Twine &Name="")

Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)

Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)

void SetInsertPoint(BasicBlock *TheBB)

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

static InsertValueInst * Create(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Instruction * foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN)

If we have something like phi [insertvalue(a,b,0), insertvalue(c,d,0)], turn this into a phi[a,...

Instruction * foldPHIArgBinOpIntoPHI(PHINode &PN)

If we have something like phi [add (a,b), add(a,c)] and if a/b/c and the adds all have a single user,...

Constant * getLosslessUnsignedTrunc(Constant *C, Type *TruncTy)

Instruction * eraseInstFromFunction(Instruction &I) override

Combiner aware instruction erasure.

Instruction * visitPHINode(PHINode &PN)

Instruction * foldPHIArgOpIntoPHI(PHINode &PN)

Try to rotate an operation below a PHI node, using PHI nodes for its operands.

Instruction * foldPHIArgZextsIntoPHI(PHINode &PN)

TODO: This function could handle other cast types, but then it might require special-casing a cast fr...

Instruction * foldPHIArgLoadIntoPHI(PHINode &PN)

bool foldIntegerTypedPHI(PHINode &PN)

If an integer typed PHI has only one use which is an IntToPtr operation, replace the PHI with an exis...

bool foldDeadPhiWeb(PHINode &PN)

If the phi is within a phi web, which is formed by the def-use chain of phis and all the phis in the ...

Instruction * foldPHIArgIntToPtrToPHI(PHINode &PN)

Instruction * SliceUpIllegalIntegerPHI(PHINode &PN)

This is an integer PHI and we know that it has an illegal type: see if it is only used by trunc or tr...

Instruction * foldPHIArgGEPIntoPHI(PHINode &PN)

void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN)

Helper function for FoldPHIArgXIntoPHI() to set debug location for the folded operation.

Instruction * foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN)

If we have something like phi [extractvalue(a,0), extractvalue(b,0)], turn this into a phi[a,...

The core instruction combiner logic.

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.

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

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

const SimplifyQuery & getSimplifyQuery() const

void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)

Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

void andIRFlags(const Value *V)

Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.

bool isAtomic() const LLVM_READONLY

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

Instruction * user_back()

Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...

unsigned getOpcode() const

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

void applyMergedLocation(DILocation *LocA, DILocation *LocB)

Merge 2 debug locations and apply it to the 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.

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

An instruction for reading from memory.

unsigned getPointerAddressSpace() const

Returns the address space of the pointer operand.

bool isVolatile() const

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

Align getAlign() const

Return the alignment of the access that is being performed.

void addIncoming(Value *V, BasicBlock *BB)

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

iterator_range< const_block_iterator > blocks() const

op_range incoming_values()

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

Value * getIncomingValue(unsigned i) const

Return incoming value number x.

unsigned getNumIncomingValues() const

Return the number of incoming edges.

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

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

static PoisonValue * get(Type *T)

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

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

size_type count(ConstPtrType Ptr) const

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

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

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

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

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.

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

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

bool isPointerTy() const

True if this is an instance of PointerType.

unsigned getScalarSizeInBits() const LLVM_READONLY

If this is a vector type, return the getPrimitiveSizeInBits value for the element type.

bool isIntegerTy() const

True if this is an instance of IntegerType.

TypeSize getPrimitiveSizeInBits() const LLVM_READONLY

Return the basic size of this type if it is a primitive type.

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

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.

bool hasOneUser() const

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

bool hasOneUse() const

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

iterator_range< user_iterator > users()

bool hasNUsesOrMore(unsigned N) const

Return true if this value has N uses or more.

const Value * stripPointerCasts() const

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

bool isSwiftError() const

Return true if this value is a swifterror value.

LLVMContext & getContext() const

All values hold a context through their type.

StringRef getName() const

Return a constant reference to the value's name.

const ParentTy * getParent() const

self_iterator getIterator()

@ C

The default llvm calling convention, compatible with C.

class_match< BinaryOperator > m_BinOp()

Match an arbitrary binary operation and ignore it.

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

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

auto m_GEP(const OperandTypes &...Ops)

Matches GetElementPtrInst.

AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)

Matches a BinaryOperator with LHS and RHS in either order.

is_zero m_Zero()

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

initializer< Ty > init(const Ty &Val)

NodeAddr< PhiNode * > Phi

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.

detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)

zip iterator for two or more iteratable types.

bool operator<(int64_t V1, const APSInt &V2)

auto find(R &&Range, const T &Val)

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

bool all_of(R &&range, UnaryPredicate P)

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

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

Wrapper function to append range R to container C.

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

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

bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)

Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...

bool any_of(R &&range, UnaryPredicate P)

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

raw_ostream & dbgs()

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

bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)

Return true if the given value is known to be non-zero when defined.

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

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

DWARFExpression::Operation Op

void array_pod_sort(IteratorTy Start, IteratorTy End)

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

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

static bool isEqual(const LoweredPHIRecord &LHS, const LoweredPHIRecord &RHS)

static unsigned getHashValue(const LoweredPHIRecord &Val)

static LoweredPHIRecord getEmptyKey()

static LoweredPHIRecord getTombstoneKey()

An information struct used to provide DenseMap with the various necessary components for a given valu...

Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...

SimplifyQuery getWithInstruction(const Instruction *I) const