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

53 }

54}

62 Stack.push_back(&PN);

64 while (!Stack.empty()) {

65 PHINode *Phi = Stack.pop_back_val();

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

68 if (!Visited.insert(PhiUse).second)

69 continue;

71 if (Visited.size() >= 16)

72 return false;

73 Stack.push_back(PhiUse);

74 } else

75 return false;

76 }

77 }

78 for (PHINode *Phi : Visited)

80 for (PHINode *Phi : Visited)

82 return true;

83}

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

134

137 return false;

139 return false;

140

142 if (!IntToPtr)

143 return false;

144

145

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

148 Value *Ptr = nullptr;

150 Ptr = LoadI->getPointerOperand();

152 Ptr = SI->getPointerOperand();

154 Ptr = GI->getPointerOperand();

155 }

156

157 if (Ptr && Ptr == IIP)

158 return true;

159 }

160 return false;

161 };

162

163 if (!HasPointerUse(IntToPtr))

164 return false;

165

166 if (DL.getPointerSizeInBits(IntToPtr->getAddressSpace()) !=

167 DL.getTypeSizeInBits(IntToPtr->getOperand(0)->getType()))

168 return false;

169

174

175

177 return false;

178

179

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

182 continue;

183 }

184

185

186 Value *ArgIntToPtr = nullptr;

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

191 ArgIntToPtr = U;

192 break;

193 }

194 }

195

196 if (ArgIntToPtr) {

198 continue;

199 }

200

201

202

205 continue;

206 }

207

208

210 if (!LoadI)

211 return false;

212

213 if (!LoadI->hasOneUse())

214 return false;

215

216

217

218

220 }

221

222

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

226 PHINode *MatchingPtrPHI = nullptr;

227 unsigned NumPhis = 0;

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

229

231 return false;

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

233 continue;

235 [&](const auto &BlockAndValue) {

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

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

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

239 }))

240 continue;

241 MatchingPtrPHI = &PtrPHI;

242 break;

243 }

244

245 if (MatchingPtrPHI) {

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

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

248

249

253 return true;

254 }

255

256

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

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

259 }))

260 return false;

261

262

263

264

265

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

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

268 return false;

270 if (!Inst)

271 return false;

272 if (Inst->isTerminator())

273 return true;

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

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

276 return true;

277 return false;

278 }))

279 return false;

280

283

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

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

289

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

291 NewPtrPHI->addIncoming(IncomingVal, IncomingBB);

292 continue;

293 }

294

295#ifndef NDEBUG

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

299 (LoadI && LoadI->hasOneUse())) &&

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

301#endif

302

303

304

305

306

307

308

309

311 if (!CI) {

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

316 InsertPos++;

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

322 } else {

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

325 }

326 }

328 }

329

330

331

335 return true;

336}

337

338

339

341

342

344 return nullptr;

345

346

347

348 bool OperandWithRoundTripCast = false;

350 if (auto *NewOp =

353 OperandWithRoundTripCast = true;

354 }

355 }

356 if (!OperandWithRoundTripCast)

357 return nullptr;

358 return &PN;

359}

360

361

362

366

367

368

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

372 return nullptr;

373 }

374

375

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

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

378 auto *&NewOperand = NewOperands[OpIdx];

379

380

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

384

386 NewOperand->addIncoming(

390 }

391

392

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

395

397 ++NumPHIsOfInsertValues;

398 return NewIVI;

399}

400

401

402

406

407

408

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

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

413 FirstEVI->getAggregateOperand()->getType())

414 return nullptr;

415 }

416

417

418

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

422

424 NewAggregateOperand->addIncoming(

428

429

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

432

434 ++NumPHIsOfExtractValues;

435 return NewEVI;

436}

437

438

439

446

449

450

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

454

455

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

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

458 return nullptr;

459

460

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

463 return nullptr;

464

465

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

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

468 }

469

470

471

472

473

474 if (!LHSVal && !RHSVal)

475 return nullptr;

476

477

478

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

482 if (!LHSVal) {

487 LHSVal = NewLHS;

488 }

489

490 if (!RHSVal) {

495 RHSVal = NewRHS;

496 }

497

498

499 if (NewLHS || NewRHS) {

504 if (NewLHS) {

507 }

508 if (NewRHS) {

510 NewRHS->addIncoming(NewInRHS, InBB);

511 }

512 }

513 }

514

517 LHSVal, RHSVal);

519 return NewCI;

520 }

521

525

527

530

532 return NewBinOp;

533}

534

537

539 FirstInst->op_end());

540

541

542 bool AllBasePointersAreAllocas = true;

543

544

545

546

547 bool NeededPhi = false;

548

549

551

552

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

558 return nullptr;

559

560 NW &= GEP->getNoWrapFlags();

561

562

563 if (AllBasePointersAreAllocas &&

565 GEP ->hasAllConstantIndices()))

566 AllBasePointersAreAllocas = false;

567

568

571 continue;

572

573

574

575

576

577

580 return nullptr;

581

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

584 return nullptr;

585

586

587

588

589

590 if (NeededPhi)

591 return nullptr;

592

593 FixedOperands[Op] = nullptr;

594 NeededPhi = true;

595 }

596 }

597

598

599

600

601

602

603

604 if (AllBasePointersAreAllocas)

605 return nullptr;

606

607

608

610

611 bool HasAnyPHIs = false;

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

613 if (FixedOperands[I])

614 continue;

619

621 OperandPhis[I] = NewPN;

622 FixedOperands[I] = NewPN;

623 HasAnyPHIs = true;

624 }

625

626

627 if (HasAnyPHIs) {

632

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

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

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

636 }

637 }

638

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

644 return NewGEP;

645}

646

647

648

649

650

651

652

653

656

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

658 if (BBI->mayWriteToMemory()) {

659

660

662 if (CB->onlyAccessesInaccessibleMemory())

663 continue;

664 return false;

665 }

666

667

668

670 bool IsAddressTaken = false;

674

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

676 }

677 IsAddressTaken = true;

678 break;

679 }

680

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

682 return false;

683 }

684

685

686

687

688

689

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

693 return false;

694

695 return true;

696}

697

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

733 return nullptr;

734

735

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

738 return nullptr;

739

741 return nullptr;

742

743

744

746 return nullptr;

747

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

749

750

751

752

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

754 return nullptr;

755 }

756

757

758

762

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

768

769

776 if (NewInVal != InVal)

777 InVal = nullptr;

779 }

780

781 if (InVal) {

782

783

785 delete NewPN;

786 } else {

788 }

789

790

791

792

793 if (IsVolatile)

796

798 return NewLI;

799}

800

801

802

803

805

806

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

808 if (TI->isEHPad())

809 return nullptr;

810

811

812

813

814 unsigned NumIncomingValues = Phi.getNumIncomingValues();

815 if (NumIncomingValues < 3)

816 return nullptr;

817

818

819 Type *NarrowType = nullptr;

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

822 NarrowType = Zext->getSrcTy();

823 break;

824 }

825 }

826 if (!NarrowType)

827 return nullptr;

828

829

830

832 unsigned NumZexts = 0;

833 unsigned NumConsts = 0;

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

836

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

838 return nullptr;

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

840 NumZexts++;

842

844 if (!Trunc)

845 return nullptr;

847 NumConsts++;

848 } else {

849

850 return nullptr;

851 }

852 }

853

854

855

856

857

858

859

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

861 return nullptr;

862

863

864

865

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

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

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

870

873

874

875

876

877

879 return CI;

880}

881

882

883

884

886

887

889 if (TI->isEHPad())

890 return nullptr;

891

893

902

903

904

905

906

907 Constant *ConstantOp = nullptr;

908 Type *CastSrcTy = nullptr;

909

912

913

914

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

917 return nullptr;

918 }

920

921

923 if (!ConstantOp)

925 } else {

926 return nullptr;

927 }

928

929

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

933 return nullptr;

934 if (CastSrcTy) {

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

936 return nullptr;

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

938 return nullptr;

939 }

940 }

941

942

943

947

950

951

956 if (NewInVal != InVal)

957 InVal = nullptr;

959 }

960

962 if (InVal) {

963

964

965 PhiVal = InVal;

966 delete NewPN;

967 } else {

969 PhiVal = NewPN;

970 }

971

972

977 return NewCI;

978 }

979

983

985 BinOp->andIRFlags(V);

986

988 return BinOp;

989 }

990

993 PhiVal, ConstantOp);

995 return NewCI;

996}

997

998

999

1000

1003

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

1005 return true;

1006

1007

1008 if (ValueEqualPHIs.size() >= 16)

1009 return false;

1010

1011

1012

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

1016 if (NonPhiInVal)

1017 return false;

1018 NonPhiInVal = OpPN;

1019 }

1020 } else if (Op != NonPhiInVal)

1021 return false;

1022 }

1023

1024 return true;

1025}

1026

1027

1028

1033 if (!ConstVA->isZero())

1034 return ConstVA;

1036}

1037

1038namespace {

1039struct PHIUsageRecord {

1040 unsigned PHIId;

1041 unsigned Shift;

1042 Instruction *Inst;

1043

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

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

1046

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

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

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

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

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

1054 }

1055};

1056

1057struct LoweredPHIRecord {

1058 PHINode *PN;

1059 unsigned Shift;

1060 unsigned Width;

1061

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

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

1064

1065

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

1067};

1068}

1069

1072 return LoweredPHIRecord(nullptr, 0);

1073 }

1075 return LoweredPHIRecord(nullptr, 1);

1076 }

1079 (Val.Width >> 3);

1080 }

1081 static bool isEqual(const LoweredPHIRecord &LHS,

1082 const LoweredPHIRecord &RHS) {

1083 return LHS.PN == RHS.PN && LHS.Shift == RHS.Shift && LHS.Width == RHS.Width;

1084 }

1085};

1086

1087

1088

1089

1090

1091

1092

1093

1094

1096

1097

1099

1100

1101

1102

1103

1106

1107 PHIsToSlice.push_back(&FirstPhi);

1108 PHIsInspected.insert(&FirstPhi);

1109

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

1111 PHINode *PN = PHIsToSlice[PHIId];

1112

1113

1114

1115

1116

1121 if ()

1122 continue;

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

1124 continue;

1125

1126

1127

1128

1129 return nullptr;

1130 }

1131

1132

1133

1134

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

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

1137 return nullptr;

1138

1141

1142

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

1146 continue;

1147 }

1148

1149

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

1152 continue;

1153 }

1154

1155

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

1159 return nullptr;

1160

1161

1164 return nullptr;

1165

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

1168 }

1169 }

1170

1171

1172 if (PHIUsers.empty())

1174

1175

1176

1178

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

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

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

1182

1183

1184

1186

1187

1188

1190

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

1192 unsigned PHIId = PHIUsers[UserI].PHIId;

1193 PHINode *PN = PHIsToSlice[PHIId];

1194 unsigned Offset = PHIUsers[UserI].Shift;

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

1196

1198

1199

1200

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

1202

1203

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

1209

1213 Value *&PredVal = PredValues[Pred];

1214

1215

1216 if (PredVal) {

1218 continue;

1219 }

1220

1221

1222 if (InVal == PN) {

1223 PredVal = EltPHI;

1225 continue;

1226 }

1227

1229

1230

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

1232 PredVal = Res;

1234 continue;

1235 }

1236 }

1237

1238

1239 Builder.SetInsertPoint(Pred->getTerminator());

1240 Value *Res = InVal;

1242 Res = Builder.CreateLShr(

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

1244 Res = Builder.CreateTrunc(Res, Ty, "extract.t");

1245 PredVal = Res;

1247

1248

1249

1250

1251

1253 if (PHIsInspected.count(OldInVal)) {

1254 unsigned RefPHIId =

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

1258 ++UserE;

1259 }

1260 }

1261 PredValues.clear();

1262

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

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

1266 }

1267

1268

1270 }

1271

1272

1273

1278}

1279

1282

1283

1284

1285

1286

1287

1288

1289

1290

1291

1292

1293

1294

1296 return nullptr;

1297

1299

1301 return nullptr;

1302

1303

1310 SuccForValue[C] = Succ;

1311 ++SuccCount[Succ];

1312 };

1314 if (BI->isUnconditional())

1315 return nullptr;

1316

1317 Cond = BI->getCondition();

1321 Cond = SI->getCondition();

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

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

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

1325 } else {

1326 return nullptr;

1327 }

1328

1330 return nullptr;

1331

1332

1333

1334 std::optional Invert;

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

1339

1340

1341

1342 auto It = SuccForValue.find(Input);

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

1346 };

1347

1348

1349 bool NeedsInvert;

1350 if (IsCorrectInput(Input))

1351 NeedsInvert = false;

1353 NeedsInvert = true;

1354 else

1355 return nullptr;

1356

1357

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

1359 return nullptr;

1360

1361 Invert = NeedsInvert;

1362 }

1363

1364 if (!*Invert)

1365 return Cond;

1366

1367

1368

1369

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

1374 }

1375

1376 return nullptr;

1377}

1378

1379

1380

1381

1382

1386 return nullptr;

1387

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

1394 Start = V1;

1396 return true;

1397 }

1398 return false;

1399 };

1400

1403 return nullptr;

1404

1406 Value *Iv2Start, *Iv2Step;

1409 return nullptr;

1410

1415 if (Iv2Start != Identity)

1416 return nullptr;

1417

1419 if (!BO) {

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

1423 }

1424

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

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

1428 return Res;

1429}

1430

1431

1432

1436

1438 return Result;

1439

1441 return Result;

1442

1443

1444

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

1448 Inst0->hasOneUser())

1450 return Result;

1451

1452

1453

1458

1459

1461 CheckedIVs.insert(IV0);

1462 if (IV0 != IV0Stripped &&

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

1465 IV0Stripped == IV->stripPointerCasts();

1466 })) {

1468 }

1469 }

1470

1472 return nullptr;

1473

1474

1477 return nullptr;

1478

1479

1480

1481

1482

1483

1484

1491 }

1492 }

1493

1494

1495

1496

1497

1498

1499

1500

1501

1502

1503

1504

1505

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

1509 auto *CmpInst = dyn_cast(U);

1510 if (!CmpInst) {

1511

1512

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

1514 DropPoisonFlags.push_back(cast(U));

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

1516 }

1517 }

1520 return false;

1521 }

1522 return true;

1523 });

1524

1525 if (AllUsesOfPhiEndsInCmp) {

1527 bool MadeChange = false;

1532 if (!NonZeroConst)

1534 if (NonZeroConst != VA) {

1536

1538 I->dropPoisonGeneratingFlags();

1539 MadeChange = true;

1540 }

1541 }

1542 }

1543 if (MadeChange)

1544 return &PN;

1545 }

1546 }

1547

1548

1549

1550

1551

1552

1553

1554

1555

1556 {

1557 unsigned InValNo = 0, NumIncomingVals = PN.getNumIncomingValues();

1558

1559 while (InValNo != NumIncomingVals &&

1561 ++InValNo;

1562

1563 Value *NonPhiInVal =

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

1565

1566

1567

1568 if (NonPhiInVal)

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

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

1571 if (OpVal != NonPhiInVal && isa<PHINode> (OpVal))

1572 break;

1573 }

1574

1575

1576

1577

1578 if (InValNo == NumIncomingVals) {

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

1581 return replaceInstUsesWith(PN, NonPhiInVal);

1582 }

1583 }

1584

1585

1586

1587

1588

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

1590 if (!Res.second) {

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

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

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

1595 if (BBA != BBB) {

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

1597 unsigned J = PN.getBasicBlockIndex(BBB);

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

1599 PN.setIncomingBlock(I, BBB);

1600 PN.setIncomingValue(I, VB);

1601 PN.setIncomingBlock(J, BBA);

1602 PN.setIncomingValue(J, VA);

1603

1604

1605

1606

1607 }

1608 }

1609 } else {

1610

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

1612 }

1613

1614

1616

1617 if (&IdenticalPN == &PN)

1618 continue;

1619

1620

1621

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

1623 continue;

1624

1625 ++NumPHICSEs;

1626 return replaceInstUsesWith(PN, &IdenticalPN);

1627 }

1628

1629

1630

1631

1632

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

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

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

1636 return Res;

1637

1638

1640 return replaceInstUsesWith(PN, V);

1641

1643 return replaceInstUsesWith(PN, Res);

1644

1645 return nullptr;

1646}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static const Function * getParent(const Value *V)

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

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.

Definition InstCombinePHI.cpp:1029

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

Definition InstCombinePHI.cpp:1383

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.

Definition InstCombinePHI.cpp:654

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

Definition InstCombinePHI.cpp:1280

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

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

Definition InstCombinePHI.cpp:1001

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.

MachineInstr unsigned OpIdx

uint64_t IntrinsicInst * II

const SmallVectorImpl< MachineOperand > & Cond

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]

The Input class is used to parse a yaml document into in-memory structs and vectors.

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.

LLVM_ABI const_iterator getFirstInsertionPt() const

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

const Function * getParent() const

Return the enclosing method, or null if none.

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 LLVM_ABI 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 LLVM_ABI CastInst * CreatePointerCast(Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)

Create a BitCast, AddrSpaceCast or a PtrToInt cast instruction.

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

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

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

Create a ZExt or BitCast cast instruction.

static LLVM_ABI 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 LLVM_ABI bool isEquality(Predicate pred)

Determine if this is an equals/not equals predicate.

static LLVM_ABI 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 LLVM_ABI Constant * getNot(Constant *C)

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

static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)

This is an important base class in LLVM.

static LLVM_ABI Constant * getNullValue(Type *Ty)

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

static DebugLoc getDropped()

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.

LLVM_ABI bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

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.

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

LLVM_ABI GEPNoWrapFlags getNoWrapFlags() const

Get the nowrap flags for the GEP instruction.

Common base class shared among various IRBuilders.

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

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

Definition InstCombinePHI.cpp:364

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

Definition InstCombinePHI.cpp:440

Instruction * eraseInstFromFunction(Instruction &I) override

Combiner aware instruction erasure.

Instruction * visitPHINode(PHINode &PN)

Definition InstCombinePHI.cpp:1433

Instruction * foldPHIArgOpIntoPHI(PHINode &PN)

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

Definition InstCombinePHI.cpp:885

Instruction * foldPHIArgZextsIntoPHI(PHINode &PN)

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

Definition InstCombinePHI.cpp:804

Instruction * foldPHIArgLoadIntoPHI(PHINode &PN)

Definition InstCombinePHI.cpp:698

bool foldIntegerTypedPHI(PHINode &PN)

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

Definition InstCombinePHI.cpp:135

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

Definition InstCombinePHI.cpp:59

Instruction * foldPHIArgIntToPtrToPHI(PHINode &PN)

Definition InstCombinePHI.cpp:340

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

Definition InstCombinePHI.cpp:1095

Instruction * foldPHIArgGEPIntoPHI(PHINode &PN)

Definition InstCombinePHI.cpp:535

void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN)

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

Definition InstCombinePHI.cpp:43

Instruction * foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN)

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

Definition InstCombinePHI.cpp:404

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

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

LLVM_ABI void andIRFlags(const Value *V)

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

LLVM_ABI 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 setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

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

Copy metadata from SrcInst to this instruction.

LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)

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

LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY

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

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

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.

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

LLVM_ABI bool hasNUsesOrMore(unsigned N) const

Return true if this value has N uses or more.

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.

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

@ User

could "use" a pointer

NodeAddr< PhiNode * > Phi

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.

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.

decltype(auto) dyn_cast(const From &Val)

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

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

Wrapper function to append range R to container C.

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

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

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

LLVM_ABI Constant * getLosslessUnsignedTrunc(Constant *C, Type *DestTy, const DataLayout &DL, PreservedCastFlags *Flags=nullptr)

LLVM_ABI raw_ostream & dbgs()

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

bool isa(const From &Val)

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

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

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

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

LLVM_ABI bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)

Given an instruction, is it legal to set operand OpIdx to a non-constant value?

DWARFExpression::Operation Op

decltype(auto) cast(const From &Val)

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

void array_pod_sort(IteratorTy Start, IteratorTy End)

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

constexpr detail::IsaCheckPredicate< Types... > IsaPred

Function object wrapper for the llvm::isa type check.

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

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

Definition InstCombinePHI.cpp:1081

static unsigned getHashValue(const LoweredPHIRecord &Val)

Definition InstCombinePHI.cpp:1077

static LoweredPHIRecord getEmptyKey()

Definition InstCombinePHI.cpp:1071

static LoweredPHIRecord getTombstoneKey()

Definition InstCombinePHI.cpp:1074

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