SCCPSolver.cpp Source File (original) (raw)

28#include

29#include

30#include

32using namespace llvm;

34#define DEBUG_TYPE "sccp"

44}

46namespace llvm {

51}

55}

59 if (!Const)

60 return false;

65 CallBase *CB = dyn_cast(V);

71 if (F)

74 LLVM_DEBUG(dbgs() << " Can\'t treat the result of call " << *CB

75 << " as a constant\n");

76 return false;

77 }

79 LLVM_DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n');

82 V->replaceAllUsesWith(Const);

83 return true;

84}

90 bool Changed = false;

91 auto GetRange = [&Solver, &InsertedValues](Value *Op) {

92 if (auto *Const = dyn_cast(Op))

93 return Const->toConstantRange();

95 unsigned Bitwidth = Op->getType()->getScalarSizeInBits();

96 return ConstantRange::getFull(Bitwidth);

97 }

99 Op->getType(), false);

100 };

101

102 if (isa(Inst)) {

104 return false;

105

106 auto RangeA = GetRange(Inst.getOperand(0));

107 auto RangeB = GetRange(Inst.getOperand(1));

112 if (NUWRange.contains(RangeA)) {

114 Changed = true;

115 }

116 }

121 if (NSWRange.contains(RangeA)) {

123 Changed = true;

124 }

125 }

126 } else if (isa(Inst) && !Inst.hasNonNeg()) {

130 Changed = true;

131 }

132 } else if (TruncInst *TI = dyn_cast(&Inst)) {

133 if (TI->hasNoSignedWrap() && TI->hasNoUnsignedWrap())

134 return false;

135

137 uint64_t DestWidth = TI->getDestTy()->getScalarSizeInBits();

138 if (!TI->hasNoUnsignedWrap()) {

140 TI->setHasNoUnsignedWrap(true);

141 Changed = true;

142 }

143 }

144 if (!TI->hasNoSignedWrap()) {

146 TI->setHasNoSignedWrap(true);

147 Changed = true;

148 }

149 }

150 } else if (auto *GEP = dyn_cast(&Inst)) {

151 if (GEP->hasNoUnsignedWrap() || GEP ->hasNoUnsignedSignedWrap())

152 return false;

153

155 [&](Value *V) { return GetRange(V).isAllNonNegative(); })) {

156 GEP->setNoWrapFlags(GEP->getNoWrapFlags() |

158 Changed = true;

159 }

160 }

161

162 return Changed;

163}

164

165

169

170 auto isNonNegative = [&Solver](Value *V) {

171

172

173 if (auto *C = dyn_cast(V)) {

174 auto *CInt = dyn_cast(C);

175 return CInt && !CInt->isNegative();

176 }

178 return IV.isConstantRange(false) &&

179 IV.getConstantRange().isAllNonNegative();

180 };

181

184 case Instruction::SIToFP:

185 case Instruction::SExt: {

186

188 if (InsertedValues.count(Op0) || !isNonNegative(Op0))

189 return false;

191 ? Instruction::ZExt

192 : Instruction::UIToFP,

195 break;

196 }

197 case Instruction::AShr: {

198

200 if (InsertedValues.count(Op0) || !isNonNegative(Op0))

201 return false;

202 NewInst = BinaryOperator::CreateLShr(Op0, Inst.getOperand(1), "", Inst.getIterator());

204 break;

205 }

206 case Instruction::SDiv:

207 case Instruction::SRem: {

208

210 if (InsertedValues.count(Op0) || InsertedValues.count(Op1) ||

211 !isNonNegative(Op0) || !isNonNegative(Op1))

212 return false;

213 auto NewOpcode = Inst.getOpcode() == Instruction::SDiv ? Instruction::UDiv

214 : Instruction::URem;

216 if (Inst.getOpcode() == Instruction::SDiv)

218 break;

219 }

220 default:

221 return false;

222 }

223

224

225 assert(NewInst && "Expected replacement instruction");

227 InsertedValues.insert(NewInst);

232 return true;

233}

234

239 bool MadeChanges = false;

241 if (Inst.getType()->isVoidTy())

242 continue;

245 Inst.eraseFromParent();

246

247 MadeChanges = true;

248 ++InstRemovedStat;

250 MadeChanges = true;

251 ++InstReplacedStat;

253 MadeChanges = true;

254 }

255 }

256 return MadeChanges;

257}

258

260 BasicBlock *&NewUnreachableBB) const {

262 bool HasNonFeasibleEdges = false;

265 FeasibleSuccessors.insert(Succ);

266 else

267 HasNonFeasibleEdges = true;

268 }

269

270

271 if (!HasNonFeasibleEdges)

272 return false;

273

274

276 assert((isa(TI) || isa(TI) ||

277 isa(TI)) &&

278 "Terminator must be a br, switch or indirectbr");

279

280 if (FeasibleSuccessors.size() == 0) {

281

285 Succ->removePredecessor(BB);

286 if (SeenSuccs.insert(Succ).second)

288 }

292 } else if (FeasibleSuccessors.size() == 1) {

293

294 BasicBlock *OnlyFeasibleSuccessor = *FeasibleSuccessors.begin();

296 bool HaveSeenOnlyFeasibleSuccessor = false;

298 if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {

299

300

301 HaveSeenOnlyFeasibleSuccessor = true;

302 continue;

303 }

304

305 Succ->removePredecessor(BB);

307 }

308

313 } else if (FeasibleSuccessors.size() > 1) {

316

317

318

319 BasicBlock *DefaultDest = SI->getDefaultDest();

320 if (!FeasibleSuccessors.contains(DefaultDest)) {

321 if (!NewUnreachableBB) {

322 NewUnreachableBB =

324 DefaultDest->getParent(), DefaultDest);

326 }

327

329 SI->setDefaultDest(NewUnreachableBB);

332 }

333

334 for (auto CI = SI->case_begin(); CI != SI->case_end();) {

335 if (FeasibleSuccessors.contains(CI->getCaseSuccessor())) {

336 ++CI;

337 continue;

338 }

339

340 BasicBlock *Succ = CI->getCaseSuccessor();

343 SI.removeCase(CI);

344

345 }

346

348 } else {

349 llvm_unreachable("Must have at least one feasible successor");

350 }

351 return true;

352}

353

356

358

360 return;

361

362

363 Attribute OldAttr = F->getAttributeAtIndex(AttrIndex, Attribute::Range);

367 F->addAttributeAtIndex(

368 AttrIndex, Attribute::get(F->getContext(), Attribute::Range, CR));

369 return;

370 }

371

374 ->hasAttributeAtIndex(AttrIndex, Attribute::NonNull)) {

375 F->addAttributeAtIndex(AttrIndex,

377 }

378}

379

383}

384

388 continue;

390 if (.getType()->isStructTy())

393 }

394}

395

396

397

403 ValueState;

404

405

406

408

409

410

411

412

414

415

416

417

419

420

421

423 TrackedMultipleRetVals;

424

425

426

428

429

430

432

433

435

436

437

438

440

441

442

443

444

445

446

447

450

451

453

454

455

456 using Edge = std::pair<BasicBlock *, BasicBlock *>;

458

460

462

464

465private:

467 return dyn_cast_or_null(getConstant(IV, Ty));

468 }

469

470

472

473

474

476

477

478

479

481 bool MayIncludeUndef = false);

482

484 assert(!V->getType()->isStructTy() && "structs should use mergeInValue");

485 return markConstant(ValueState[V], V, C);

486 }

487

489

492 }

493

494

495

496

497

500

501

502

503

505

506

507

511 false, false});

512

515 false, false}) {

516 assert(!V->getType()->isStructTy() &&

517 "non-structs should use markConstant");

518 return mergeInValue(ValueState[V], V, MergeWithV, Opts);

519 }

520

521

522

523

525 assert(!V->getType()->isStructTy() && "Should use getStructValueState");

526

529

530 if (.second)

531 return LV;

532

533 if (auto *C = dyn_cast(V))

535

536

537 return LV;

538 }

539

540

541

542

544 assert(V->getType()->isStructTy() && "Should use getValueState");

545 assert(i < cast(V->getType())->getNumElements() &&

546 "Invalid element #");

547

548 auto I = StructValueState.insert(

551

552 if (.second)

553 return LV;

554

555 if (auto *C = dyn_cast(V)) {

556 Constant *Elt = C->getAggregateElement(i);

557

558 if (!Elt)

560 else

561 LV.markConstant(Elt);

562 }

563

564

565 return LV;

566 }

567

568

569

570 void invalidate(CallBase *Call) {

573

574 while (!ToInvalidate.empty()) {

576

578 continue;

579

580 if (!BBExecutable.count(Inst->getParent()))

581 continue;

582

583 Value *V = nullptr;

584

585

586 if (auto *RetInst = dyn_cast(Inst)) {

587 Function *F = RetInst->getParent()->getParent();

588 if (auto It = TrackedRetVals.find(F); It != TrackedRetVals.end()) {

590 V = F;

591 } else if (MRVFunctionsTracked.count(F)) {

592 auto *STy = cast(F->getReturnType());

593 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I)

595 V = F;

596 }

597 } else if (auto *STy = dyn_cast(Inst->getType())) {

598 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {

599 if (auto It = StructValueState.find({Inst, I});

600 It != StructValueState.end()) {

602 V = Inst;

603 }

604 }

605 } else if (auto It = ValueState.find(Inst); It != ValueState.end()) {

607 V = Inst;

608 }

609

610 if (V) {

611 LLVM_DEBUG(dbgs() << "Invalidated lattice for " << *V << "\n");

612

613 for (User *U : V->users())

614 if (auto *UI = dyn_cast(U))

616

617 auto It = AdditionalUsers.find(V);

618 if (It != AdditionalUsers.end())

619 for (User *U : It->second)

620 if (auto *UI = dyn_cast(U))

622 }

623 }

624 }

625

626

627

629

630

631

633

634

635

636

638 if (BBExecutable.count(I->getParent()))

640 }

641

642

643 void addAdditionalUser(Value *V, User *U) { AdditionalUsers[V].insert(U); }

644

645

646 void markUsersAsChanged(Value *I) {

647

648

649

650

651 if (isa(I)) {

652 for (User *U : I->users()) {

653 if (auto *CB = dyn_cast(U))

654 handleCallResult(*CB);

655 }

656 } else {

657 for (User *U : I->users())

658 if (auto *UI = dyn_cast(U))

659 operandChangedState(UI);

660 }

661

662 auto Iter = AdditionalUsers.find(I);

663 if (Iter != AdditionalUsers.end()) {

664

665

667 for (User *U : Iter->second)

668 if (auto *UI = dyn_cast(U))

671 operandChangedState(UI);

672 }

673 }

674 void handleCallOverdefined(CallBase &CB);

675 void handleCallResult(CallBase &CB);

676 void handleCallArguments(CallBase &CB);

679

680private:

682

683

684

685

686 void visitPHINode(PHINode &I);

687

688

689

692

698 void visitCmpInst(CmpInst &I);

701

703 markOverdefined(&CPI);

704 visitTerminator(CPI);

705 }

706

707

708

712 void visitAllocaInst(AllocaInst &AI);

713

715 visitCallBase(II);

716 visitTerminator(II);

717 }

718

719 void visitCallBrInst(CallBrInst &CBI) {

720 visitCallBase(CBI);

721 visitTerminator(CBI);

722 }

723

724 void visitCallBase(CallBase &CB);

725 void visitResumeInst(ResumeInst &I) {

726 }

727 void visitUnreachableInst(UnreachableInst &I) {

728 }

729 void visitFenceInst(FenceInst &I) {

730 }

731

733

734public:

736 FnPredicateInfo.insert({&F, std::make_unique(F, DT, AC)});

737 }

738

740

742

744 auto It = FnPredicateInfo.find(I->getParent()->getParent());

745 if (It == FnPredicateInfo.end())

746 return nullptr;

747 return It->second->getPredicateInfoFor(I);

748 }

749

753 : DL(DL), GetTLI(GetTLI), Ctx(Ctx) {}

754

756

760 }

761 }

762

764

765 if (auto *STy = dyn_cast(F->getReturnType())) {

766 MRVFunctionsTracked.insert(F);

767 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)

768 TrackedMultipleRetVals.insert(

770 } else if (->getReturnType()->isVoidTy())

772 }

773

775 MustPreserveReturnsInFunctions.insert(F);

776 }

777

779 return MustPreserveReturnsInFunctions.count(F);

780 }

781

783 TrackingIncomingArguments.insert(F);

784 }

785

787 return TrackingIncomingArguments.count(F);

788 }

789

791 return TrackingIncomingArguments;

792 }

793

795

797

799

801 return BBExecutable.count(BB);

802 }

803

805

807 std::vector StructValues;

808 auto *STy = dyn_cast(V->getType());

809 assert(STy && "getStructLatticeValueFor() can be called only on structs");

810 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {

811 auto I = StructValueState.find(std::make_pair(V, i));

812 assert(I != StructValueState.end() && "Value not in valuemap!");

813 StructValues.push_back(I->second);

814 }

815 return StructValues;

816 }

817

819

820

821

823

824 Function *F = Call->getCalledFunction();

825 (void)F;

826 assert(->getReturnType()->isVoidTy() &&

827 (TrackedRetVals.count(F) || MRVFunctionsTracked.count(F)) &&

828 "All non void specializations should be tracked");

829 invalidate(Call);

830 handleCallResult(*Call);

831 }

832

834 assert(!V->getType()->isStructTy() &&

835 "Should use getStructLatticeValueFor");

837 ValueState.find(V);

839 "V not found in ValueState nor Paramstate map!");

840 return I->second;

841 }

842

844 return TrackedRetVals;

845 }

846

848 return TrackedGlobals;

849 }

850

852 return MRVFunctionsTracked;

853 }

854

856 if (auto *STy = dyn_cast(V->getType()))

857 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)

858 markOverdefined(getStructValueState(V, i), V);

859 else

860 markOverdefined(ValueState[V], V);

861 }

862

864 if (A->getType()->isIntOrIntVectorTy()) {

865 if (std::optional Range = A->getRange())

867 }

868 if (A->hasNonNullAttr())

870

872 }

873

875 if (A->getType()->isStructTy())

876 return (void)markOverdefined(A);

878 }

879

881

883

885

888

890 for (auto &BB : *F)

891 BBExecutable.erase(&BB);

892 }

893

895 bool ResolvedUndefs = true;

896 while (ResolvedUndefs) {

898 ResolvedUndefs = false;

901 }

902 }

903

905 bool ResolvedUndefs = true;

906 while (ResolvedUndefs) {

908 ResolvedUndefs = false;

911 }

912 }

913

915 bool ResolvedUndefs = true;

916 while (ResolvedUndefs) {

918 ResolvedUndefs = false;

920 if (auto *I = dyn_cast(V))

922 }

924 }

925};

926

927}

928

930 if (!BBExecutable.insert(BB).second)

931 return false;

933 BBWorkList.push_back(BB);

934 return true;

935}

936

938 if (IV.isOverdefined()) {

939 if (OverdefinedInstWorkList.empty() || OverdefinedInstWorkList.back() != V)

940 OverdefinedInstWorkList.push_back(V);

941 return;

942 }

943 if (InstWorkList.empty() || InstWorkList.back() != V)

944 InstWorkList.push_back(V);

945}

946

948 LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n');

949 pushToWorkList(IV, V);

950}

951

953 Constant *C, bool MayIncludeUndef) {

954 if (.markConstant(C, MayIncludeUndef))

955 return false;

956 LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');

957 pushToWorkList(IV, V);

958 return true;

959}

960

963 if (.markNotConstant(C))

964 return false;

965 LLVM_DEBUG(dbgs() << "markNotConstant: " << *C << ": " << *V << '\n');

966 pushToWorkList(IV, V);

967 return true;

968}

969

972 if (.markConstantRange(CR))

973 return false;

974 LLVM_DEBUG(dbgs() << "markConstantRange: " << CR << ": " << *V << '\n');

975 pushToWorkList(IV, V);

976 return true;

977}

978

980 if (.markOverdefined())

981 return false;

982

984 if (auto *F = dyn_cast(V)) dbgs()

985 << "Function '" << F->getName() << "'\n";

986 else dbgs() << *V << '\n');

987

988 pushToWorkList(IV, V);

989 return true;

990}

991

993 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {

994 const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i));

995 assert(It != TrackedMultipleRetVals.end());

998 return false;

999 }

1000 return true;

1001}

1002

1004 Type *Ty) const {

1007 assert(C->getType() == Ty && "Type mismatch");

1008 return C;

1009 }

1010

1015 }

1016 return nullptr;

1017}

1018

1021 if (V->getType()->isStructTy()) {

1024 return nullptr;

1025 std::vector<Constant *> ConstVals;

1026 auto *ST = cast(V->getType());

1027 for (unsigned I = 0, E = ST->getNumElements(); I != E; ++I) {

1032 }

1034 } else {

1037 return nullptr;

1040 }

1041 assert(Const && "Constant is nullptr here!");

1042 return Const;

1043}

1044

1047 assert(!Args.empty() && "Specialization without arguments");

1048 assert(F->arg_size() == Args[0].Formal->getParent()->arg_size() &&

1049 "Functions should have the same number of arguments");

1050

1051 auto Iter = Args.begin();

1054 for (auto End = F->arg_end(); NewArg != End; ++NewArg, ++OldArg) {

1055

1058

1059

1060

1061 if (Iter != Args.end() && Iter->Formal == &*OldArg) {

1062 if (auto *STy = dyn_cast(NewArg->getType())) {

1063 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {

1065 NewValue.markConstant(Iter->Actual->getAggregateElement(I));

1066 }

1067 } else {

1068 ValueState[&*NewArg].markConstant(Iter->Actual);

1069 }

1070 ++Iter;

1071 } else {

1072 if (auto *STy = dyn_cast(NewArg->getType())) {

1073 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {

1075 NewValue = StructValueState[{&*OldArg, I}];

1076 }

1077 } else {

1079 NewValue = ValueState[&*OldArg];

1080 }

1081 }

1082 }

1083}

1084

1085void SCCPInstVisitor::visitInstruction(Instruction &I) {

1086

1087

1088 LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n');

1089 markOverdefined(&I);

1090}

1091

1095 if (IV.mergeIn(MergeWithV, Opts)) {

1096 pushToWorkList(IV, V);

1097 LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : "

1098 << IV << "\n");

1099 return true;

1100 }

1101 return false;

1102}

1103

1104bool SCCPInstVisitor::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {

1105 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)

1106 return false;

1107

1109

1110

1111

1113 << " -> " << Dest->getName() << '\n');

1114

1116 visitPHINode(PN);

1117 }

1118 return true;

1119}

1120

1121

1122

1123void SCCPInstVisitor::getFeasibleSuccessors(Instruction &TI,

1126 if (auto *BI = dyn_cast(&TI)) {

1127 if (BI->isUnconditional()) {

1128 Succs[0] = true;

1129 return;

1130 }

1131

1134 if (!CI) {

1135

1136

1138 Succs[0] = Succs[1] = true;

1139 return;

1140 }

1141

1142

1143 Succs[CI->isZero()] = true;

1144 return;

1145 }

1146

1147

1148

1151 return;

1152 }

1153

1154 if (auto *SI = dyn_cast(&TI)) {

1155 if (->getNumCases()) {

1156 Succs[0] = true;

1157 return;

1158 }

1162 Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true;

1163 return;

1164 }

1165

1166

1167

1170 unsigned ReachableCaseCount = 0;

1171 for (const auto &Case : SI->cases()) {

1172 const APInt &CaseValue = Case.getCaseValue()->getValue();

1174 Succs[Case.getSuccessorIndex()] = true;

1175 ++ReachableCaseCount;

1176 }

1177 }

1178

1179 Succs[SI->case_default()->getSuccessorIndex()] =

1181 return;

1182 }

1183

1184

1187 return;

1188 }

1189

1190

1191

1192 if (auto *IBR = dyn_cast(&TI)) {

1193

1196 getConstant(IBRValue, IBR->getAddress()->getType()));

1197 if ( Addr ) {

1198

1201 return;

1202 }

1203

1205 assert(Addr->getFunction() == T->getParent() &&

1206 "Block address of a different function ?");

1207 for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {

1208

1209 if (IBR->getDestination(i) == T) {

1210 Succs[i] = true;

1211 return;

1212 }

1213 }

1214

1215

1216

1217 return;

1218 }

1219

1220 LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');

1221 llvm_unreachable("SCCP: Don't know how to handle this terminator!");

1222}

1223

1224

1225

1227

1228

1229

1230 return KnownFeasibleEdges.count(Edge(From, To));

1231}

1232

1233

1234

1235

1236

1237

1238

1239

1240

1241

1242

1243

1244

1245

1246

1247

1248

1249

1250void SCCPInstVisitor::visitPHINode(PHINode &PN) {

1251

1252

1254 return (void)markOverdefined(&PN);

1255

1256 if (getValueState(&PN).isOverdefined())

1257 return;

1258

1259

1260

1262 return (void)markOverdefined(&PN);

1263

1264 unsigned NumActiveIncoming = 0;

1265

1266

1267

1268

1269

1270

1274 continue;

1275

1278 NumActiveIncoming++;

1280 break;

1281 }

1282

1283

1284

1285

1286

1287

1288 mergeInValue(&PN, PhiState,

1290 NumActiveIncoming + 1));

1294}

1295

1296void SCCPInstVisitor::visitReturnInst(ReturnInst &I) {

1297 if (I.getNumOperands() == 0)

1298 return;

1299

1300 Function *F = I.getParent()->getParent();

1301 Value *ResultOp = I.getOperand(0);

1302

1303

1304 if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {

1305 auto TFRVI = TrackedRetVals.find(F);

1306 if (TFRVI != TrackedRetVals.end()) {

1307 mergeInValue(TFRVI->second, F, getValueState(ResultOp));

1308 return;

1309 }

1310 }

1311

1312

1313 if (!TrackedMultipleRetVals.empty()) {

1314 if (auto *STy = dyn_cast(ResultOp->getType()))

1315 if (MRVFunctionsTracked.count(F))

1316 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)

1317 mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F,

1318 getStructValueState(ResultOp, i));

1319 }

1320}

1321

1322void SCCPInstVisitor::visitTerminator(Instruction &TI) {

1324 getFeasibleSuccessors(TI, SuccFeasible);

1325

1327

1328

1329 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)

1330 if (SuccFeasible[i])

1332}

1333

1334void SCCPInstVisitor::visitCastInst(CastInst &I) {

1335

1336

1337 if (ValueState[&I].isOverdefined())

1338 return;

1339

1342 return;

1343

1345

1348 return (void)markConstant(&I, C);

1349 }

1350

1351

1352 if (I.getDestTy()->isIntOrIntVectorTy() &&

1353 I.getSrcTy()->isIntOrIntVectorTy() &&

1354 I.getOpcode() != Instruction::BitCast) {

1355 auto &LV = getValueState(&I);

1358

1359 Type *DestTy = I.getDestTy();

1363 } else

1364 markOverdefined(&I);

1365}

1366

1367void SCCPInstVisitor::handleExtractOfWithOverflow(ExtractValueInst &EVI,

1369 unsigned Idx) {

1373 addAdditionalUser(LHS, &EVI);

1374 addAdditionalUser(RHS, &EVI);

1375 if (L.isUnknownOrUndef() || R.isUnknownOrUndef())

1376 return;

1377

1379 ConstantRange LR = L.asConstantRange(Ty, false);

1380 ConstantRange RR = R.asConstantRange(Ty, false);

1381 if (Idx == 0) {

1384 } else {

1385 assert(Idx == 1 && "Index can only be 0 or 1");

1390 markOverdefined(&EVI);

1391 }

1392}

1393

1394void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) {

1395

1396

1398 return (void)markOverdefined(&EVI);

1399

1400

1401

1402 if (ValueState[&EVI].isOverdefined())

1403 return (void)markOverdefined(&EVI);

1404

1405

1407 return (void)markOverdefined(&EVI);

1408

1412 if (auto *WO = dyn_cast(AggVal))

1413 return handleExtractOfWithOverflow(EVI, WO, i);

1415 mergeInValue(getValueState(&EVI), &EVI, EltVal);

1416 } else {

1417

1418 return (void)markOverdefined(&EVI);

1419 }

1420}

1421

1422void SCCPInstVisitor::visitInsertValueInst(InsertValueInst &IVI) {

1423 auto *STy = dyn_cast(IVI.getType());

1424 if (!STy)

1425 return (void)markOverdefined(&IVI);

1426

1427

1428

1429 if (ValueState[&IVI].isOverdefined())

1430 return (void)markOverdefined(&IVI);

1431

1432

1433

1435 return (void)markOverdefined(&IVI);

1436

1439

1440

1441 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {

1442

1443 if (i != Idx) {

1445 mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);

1446 continue;

1447 }

1448

1451

1452 markOverdefined(getStructValueState(&IVI, i), &IVI);

1453 else {

1455 mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);

1456 }

1457 }

1458}

1459

1460void SCCPInstVisitor::visitSelectInst(SelectInst &I) {

1461

1462

1463 if (I.getType()->isStructTy())

1464 return (void)markOverdefined(&I);

1465

1466

1467

1468 if (ValueState[&I].isOverdefined())

1469 return (void)markOverdefined(&I);

1470

1473 return;

1474

1476 getConstantInt(CondValue, I.getCondition()->getType())) {

1477 Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();

1478 mergeInValue(&I, getValueState(OpVal));

1479 return;

1480 }

1481

1482

1483

1484

1487

1488 bool Changed = ValueState[&I].mergeIn(TVal);

1489 Changed |= ValueState[&I].mergeIn(FVal);

1490 if (Changed)

1491 pushToWorkListMsg(ValueState[&I], &I);

1492}

1493

1494

1495void SCCPInstVisitor::visitUnaryOperator(Instruction &I) {

1497

1499

1500

1501 if (IV.isOverdefined())

1502 return (void)markOverdefined(&I);

1503

1504

1506 return;

1507

1511 return (void)markConstant(IV, &I, C);

1512

1513 markOverdefined(&I);

1514}

1515

1516void SCCPInstVisitor::visitFreezeInst(FreezeInst &I) {

1517

1518

1519 if (I.getType()->isStructTy())

1520 return (void)markOverdefined(&I);

1521

1524

1525

1526 if (IV.isOverdefined())

1527 return (void)markOverdefined(&I);

1528

1529

1531 return;

1532

1535 return (void)markConstant(IV, &I, getConstant(V0State, I.getType()));

1536

1537 markOverdefined(&I);

1538}

1539

1540

1541void SCCPInstVisitor::visitBinaryOperator(Instruction &I) {

1544

1546 if (IV.isOverdefined())

1547 return;

1548

1549

1551 return;

1552

1554 return (void)markOverdefined(&I);

1555

1556

1557

1560 ? getConstant(V1State, I.getOperand(0)->getType())

1561 : I.getOperand(0);

1563 ? getConstant(V2State, I.getOperand(1)->getType())

1564 : I.getOperand(1);

1566 auto *C = dyn_cast_or_null(R);

1567 if (C) {

1568

1569

1570

1571

1572

1575 return (void)mergeInValue(&I, NewV);

1576 }

1577 }

1578

1579

1580 if (.getType()->isIntOrIntVectorTy())

1581 return markOverdefined(&I);

1582

1583

1585 V1State.asConstantRange(I.getType(), false);

1587 V2State.asConstantRange(I.getType(), false);

1588

1589 auto *BO = cast(&I);

1590 ConstantRange R = ConstantRange::getEmpty(I.getType()->getScalarSizeInBits());

1591 if (auto *OBO = dyn_cast(BO))

1592 R = A.overflowingBinaryOp(BO->getOpcode(), B, OBO->getNoWrapKind());

1593 else

1594 R = A.binaryOp(BO->getOpcode(), B);

1596

1597

1598

1599

1600}

1601

1602

1603void SCCPInstVisitor::visitCmpInst(CmpInst &I) {

1604

1605

1606 if (ValueState[&I].isOverdefined())

1607 return (void)markOverdefined(&I);

1608

1609 Value *Op1 = I.getOperand(0);

1610 Value *Op2 = I.getOperand(1);

1611

1612

1613

1614 auto V1State = getValueState(Op1);

1615 auto V2State = getValueState(Op2);

1616

1618 if (C) {

1621 mergeInValue(&I, CV);

1622 return;

1623 }

1624

1625

1628 return;

1629

1630 markOverdefined(&I);

1631}

1632

1633

1634

1636 if (ValueState[&I].isOverdefined())

1637 return (void)markOverdefined(&I);

1638

1641 return;

1642

1643

1645 if (I.hasNoUnsignedWrap() ||

1646 (I.isInBounds() &&

1648 return (void)markNotNull(ValueState[&I], &I);

1649 return (void)markOverdefined(&I);

1650 }

1651

1653 Operands.reserve(I.getNumOperands());

1654

1655 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {

1658 return;

1659

1662 continue;

1663 }

1664

1665 return (void)markOverdefined(&I);

1666 }

1667

1669 markConstant(&I, C);

1670 else

1671 markOverdefined(&I);

1672}

1673

1674void SCCPInstVisitor::visitAllocaInst(AllocaInst &I) {

1676 return (void)markNotNull(ValueState[&I], &I);

1677

1678 markOverdefined(&I);

1679}

1680

1681void SCCPInstVisitor::visitStoreInst(StoreInst &SI) {

1682

1683 if (SI.getOperand(0)->getType()->isStructTy())

1684 return;

1685

1686 if (TrackedGlobals.empty() || !isa(SI.getOperand(1)))

1687 return;

1688

1689 GlobalVariable *GV = cast(SI.getOperand(1));

1690 auto I = TrackedGlobals.find(GV);

1691 if (I == TrackedGlobals.end())

1692 return;

1693

1694

1695 mergeInValue(I->second, GV, getValueState(SI.getOperand(0)),

1697 if (I->second.isOverdefined())

1698 TrackedGlobals.erase(I);

1699}

1700

1702 if (const auto *CB = dyn_cast(I)) {

1703 if (CB->getType()->isIntOrIntVectorTy())

1704 if (std::optional Range = CB->getRange())

1706 if (CB->getType()->isPointerTy() && CB->isReturnNonNull())

1709 }

1710

1711 if (I->getType()->isIntOrIntVectorTy())

1712 if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range))

1715 if (I->hasMetadata(LLVMContext::MD_nonnull))

1718

1720}

1721

1722

1723

1724void SCCPInstVisitor::visitLoadInst(LoadInst &I) {

1725

1726

1727 if (I.getType()->isStructTy() || I.isVolatile())

1728 return (void)markOverdefined(&I);

1729

1730

1731

1732 if (ValueState[&I].isOverdefined())

1733 return (void)markOverdefined(&I);

1734

1737 return;

1738

1740

1743

1744

1745 if (isa(Ptr)) {

1747 return (void)markOverdefined(IV, &I);

1748 else

1749 return;

1750 }

1751

1752

1753 if (auto *GV = dyn_cast(Ptr)) {

1754 if (!TrackedGlobals.empty()) {

1755

1756 auto It = TrackedGlobals.find(GV);

1757 if (It != TrackedGlobals.end()) {

1759 return;

1760 }

1761 }

1762 }

1763

1764

1766 return (void)markConstant(IV, &I, C);

1767 }

1768

1769

1771}

1772

1773void SCCPInstVisitor::visitCallBase(CallBase &CB) {

1774 handleCallResult(CB);

1775 handleCallArguments(CB);

1776}

1777

1778void SCCPInstVisitor::handleCallOverdefined(CallBase &CB) {

1780

1781

1783 return;

1784

1785

1787 return (void)markOverdefined(&CB);

1788

1789

1790

1793 for (const Use &A : CB.args()) {

1794 if (A.get()->getType()->isStructTy())

1795 return markOverdefined(&CB);

1796 if (A.get()->getType()->isMetadataTy())

1797 continue;

1799

1801 return;

1803 return (void)markOverdefined(&CB);

1806 }

1807

1809 return (void)markOverdefined(&CB);

1810

1811

1812

1814 return (void)markConstant(&CB, C);

1815 }

1816

1817

1819}

1820

1821void SCCPInstVisitor::handleCallArguments(CallBase &CB) {

1823

1824

1825

1826 if (TrackingIncomingArguments.count(F)) {

1828

1829

1832 ++AI, ++CAI) {

1833

1834

1835 if (AI->hasByValAttr() && ->onlyReadsMemory()) {

1836 markOverdefined(&*AI);

1837 continue;

1838 }

1839

1840 if (auto *STy = dyn_cast(AI->getType())) {

1841 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {

1843 mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg,

1845 }

1846 } else

1847 mergeInValue(&*AI,

1850 }

1851 }

1852}

1853

1854void SCCPInstVisitor::handleCallResult(CallBase &CB) {

1856

1857 if (auto *II = dyn_cast(&CB)) {

1858 if (II->getIntrinsicID() == Intrinsic::ssa_copy) {

1859 if (ValueState[&CB].isOverdefined())

1860 return;

1861

1865 assert(PI && "Missing predicate info for ssa.copy");

1866

1867 const std::optional &Constraint =

1868 PI->getConstraint();

1869 if (!Constraint) {

1870 mergeInValue(ValueState[&CB], &CB, CopyOfVal);

1871 return;

1872 }

1873

1875 Value *OtherOp = Constraint->OtherOp;

1876

1877

1878 if (getValueState(OtherOp).isUnknown()) {

1879 addAdditionalUser(OtherOp, &CB);

1880 return;

1881 }

1882

1886 auto ImposedCR =

1887 ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));

1888

1889

1893

1894

1895

1897 true);

1898

1899 if (CopyOfCR.isEmptySet())

1900 CopyOfCR = ConstantRange::getFull(CopyOfCR.getBitWidth());

1901 auto NewCR = ImposedCR.intersectWith(CopyOfCR);

1902

1903

1904

1905 if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())

1906 NewCR = CopyOfCR;

1907

1908

1909

1910

1911

1912

1913 addAdditionalUser(OtherOp, &CB);

1914 mergeInValue(

1915 IV, &CB,

1917 return;

1920

1921

1922 addAdditionalUser(OtherOp, &CB);

1923 mergeInValue(IV, &CB, CondVal);

1924 return;

1926

1927 addAdditionalUser(OtherOp, &CB);

1928 mergeInValue(IV, &CB,

1930 return;

1931 }

1932

1933 return (void)mergeInValue(IV, &CB, CopyOfVal);

1934 }

1935

1936 if (II->getIntrinsicID() == Intrinsic::vscale) {

1940 }

1941

1943

1944

1945

1950 return;

1953 }

1954

1958 }

1959 }

1960

1961

1962

1963

1964 if ( || F->isDeclaration())

1965 return handleCallOverdefined(CB);

1966

1967

1968 if (auto *STy = dyn_cast(F->getReturnType())) {

1969 if (!MRVFunctionsTracked.count(F))

1970 return handleCallOverdefined(CB);

1971

1972

1973

1974 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)

1975 mergeInValue(getStructValueState(&CB, i), &CB,

1976 TrackedMultipleRetVals[std::make_pair(F, i)],

1978 } else {

1979 auto TFRVI = TrackedRetVals.find(F);

1980 if (TFRVI == TrackedRetVals.end())

1981 return handleCallOverdefined(CB);

1982

1983

1985 }

1986}

1987

1989

1990 while (!BBWorkList.empty() || !InstWorkList.empty() ||

1991 !OverdefinedInstWorkList.empty()) {

1992

1993

1994 while (!OverdefinedInstWorkList.empty()) {

1995 Value *I = OverdefinedInstWorkList.pop_back_val();

1997

1998 LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n');

1999

2000

2001

2002

2003

2004

2005

2006

2007 markUsersAsChanged(I);

2008 }

2009

2010

2011 while (!InstWorkList.empty()) {

2012 Value *I = InstWorkList.pop_back_val();

2014

2015 LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');

2016

2017

2018

2019

2020

2021

2022

2023

2024 if (I->getType()->isStructTy() || !getValueState(I).isOverdefined())

2025 markUsersAsChanged(I);

2026 }

2027

2028

2029 while (!BBWorkList.empty()) {

2030 BasicBlock *BB = BBWorkList.pop_back_val();

2031

2032 LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');

2033

2034

2035

2037 }

2038 }

2039}

2040

2042

2043 if (I.getType()->isVoidTy())

2044 return false;

2045

2046 if (auto *STy = dyn_cast(I.getType())) {

2047

2048

2049

2050 if (auto *CB = dyn_cast(&I))

2052 if (MRVFunctionsTracked.count(F))

2053 return false;

2054

2055

2056

2057 if (isa(I) || isa(I))

2058 return false;

2059

2060

2061 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {

2064 markOverdefined(LV, &I);

2065 return true;

2066 }

2067 }

2068 return false;

2069 }

2070

2073 return false;

2074

2075

2076

2077

2078

2079

2080 if (auto *CB = dyn_cast(&I))

2082 if (TrackedRetVals.count(F))

2083 return false;

2084

2085 if (isa(I)) {

2086

2087

2088

2089 return false;

2090 }

2091

2092 markOverdefined(&I);

2093 return true;

2094}

2095

2096

2097

2098

2099

2100

2101

2102

2103

2104

2105

2106

2107

2108

2110 bool MadeChange = false;

2112 if (!BBExecutable.count(&BB))

2113 continue;

2114

2117 }

2118

2120 << "\nResolved undefs in " << F.getName() << '\n');

2121

2122 return MadeChange;

2123}

2124

2125

2126

2127

2128

2134

2136

2139 Visitor->addPredicateInfo(F, DT, AC);

2140}

2141

2143 return Visitor->markBlockExecutable(BB);

2144}

2145

2147 return Visitor->getPredicateInfoFor(I);

2148}

2149

2151 Visitor->trackValueOfGlobalVariable(GV);

2152}

2153

2155 Visitor->addTrackedFunction(F);

2156}

2157

2159 Visitor->addToMustPreserveReturnsInFunctions(F);

2160}

2161

2163 return Visitor->mustPreserveReturn(F);

2164}

2165

2167 Visitor->addArgumentTrackedFunction(F);

2168}

2169

2171 return Visitor->isArgumentTrackedFunction(F);

2172}

2173

2176 return Visitor->getArgumentTrackedFunctions();

2177}

2178

2180

2182 return Visitor->resolvedUndefsIn(F);

2183}

2184

2186 Visitor->solveWhileResolvedUndefsIn(M);

2187}

2188

2189void

2191 Visitor->solveWhileResolvedUndefsIn(WorkList);

2192}

2193

2195 Visitor->solveWhileResolvedUndefs();

2196}

2197

2199 return Visitor->isBlockExecutable(BB);

2200}

2201

2203 return Visitor->isEdgeFeasible(From, To);

2204}

2205

2206std::vector

2208 return Visitor->getStructLatticeValueFor(V);

2209}

2210

2212 return Visitor->removeLatticeValueFor(V);

2213}

2214

2216 Visitor->resetLatticeValueFor(Call);

2217}

2218

2220 return Visitor->getLatticeValueFor(V);

2221}

2222

2225 return Visitor->getTrackedRetVals();

2226}

2227

2230 return Visitor->getTrackedGlobals();

2231}

2232

2234 return Visitor->getMRVFunctionsTracked();

2235}

2236

2238

2240 Visitor->trackValueOfArgument(V);

2241}

2242

2244 return Visitor->isStructLatticeConstant(F, STy);

2245}

2246

2248 Type *Ty) const {

2249 return Visitor->getConstant(LV, Ty);

2250}

2251

2253 return Visitor->getConstantOrNull(V);

2254}

2255

2258 Visitor->setLatticeValueForSpecializationArguments(F, Args);

2259}

2260

2262 Visitor->markFunctionUnreachable(F);

2263}

2264

2266

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

BlockVerifier::State From

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

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

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

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

mir Rename Register Operands

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

uint64_t IntrinsicInst * II

static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts()

Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.

static const unsigned MaxNumRangeExtensions

static ValueLatticeElement getValueFromMetadata(const Instruction *I)

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

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

static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)

Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.

static const uint32_t IV[8]

Class for arbitrary precision integers.

an instruction to allocate memory on the stack

This class represents an incoming formal argument to a Function.

A cache of @llvm.assume calls within a function.

const ConstantRange & getRange() const

Returns the value of the range attribute.

static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)

Return a uniquified Attribute object.

bool isValid() const

Return true if the attribute is any kind of attribute.

LLVM Basic Block Representation.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

const Function * getParent() const

Return the enclosing method, or null if none.

LLVMContext & getContext() const

Get the context in which this basic block lives.

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

void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)

Update PHI nodes in this BasicBlock before removal of predecessor Pred.

unsigned getNoWrapKind() const

Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.

Instruction::BinaryOps getBinaryOp() const

Returns the binary operation underlying the intrinsic.

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.

The address of a basic block.

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

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

std::optional< OperandBundleUse > getOperandBundle(StringRef Name) const

Return an operand bundle by name, if present.

Function * getCalledFunction() const

Returns the function called, or null if this is an indirect function invocation or the function signa...

User::op_iterator arg_begin()

Return the iterator pointing to the beginning of the argument list.

bool isMustTailCall() const

Tests if this call site must be tail call optimized.

iterator_range< User::op_iterator > args()

Iteration adapter for range-for loops.

CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...

This class represents a function call, abstracting a target machine's calling convention.

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

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.

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

This is the shared class of boolean and integer constants.

bool isZero() const

This is just a convenience method to make client code smaller for a common code.

static ConstantInt * getFalse(LLVMContext &Context)

static ConstantPointerNull * get(PointerType *T)

Static factory methods - Return objects of the specified value.

This class represents a range of values.

unsigned getActiveBits() const

Compute the maximal number of active bits needed to represent every value in this range.

const APInt * getSingleElement() const

If this set contains a single element, return it, otherwise return null.

ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const

Return a new range representing the possible values resulting from an application of the specified ca...

static ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)

Compute range of intrinsic result for the given operand ranges.

bool isSizeLargerThan(uint64_t MaxSize) const

Compare set size of this range with Value.

static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)

Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.

bool isSingleElement() const

Return true if this set contains exactly one member.

bool isAllNonNegative() const

Return true if all values in this range are non-negative.

static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)

Produce the smallest range such that all values that may satisfy the given predicate with any value c...

bool contains(const APInt &Val) const

Return true if the specified value is in the set.

ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const

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

static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)

Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...

unsigned getMinSignedBits() const

Compute the maximal number of bits needed to represent every value in this signed range.

ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const

Return a new range representing the possible values resulting from an application of the specified bi...

static Constant * get(StructType *T, ArrayRef< Constant * > V)

This is an important base class in LLVM.

static Constant * getNullValue(Type *Ty)

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

bool isNullValue() const

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

This class represents an Operation in the Expression.

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

iterator find(const_arg_type_t< KeyT > Val)

bool erase(const KeyT &Val)

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

Implements a dense probed hash-table based set.

static constexpr UpdateKind Delete

static constexpr UpdateKind Insert

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

An instruction for ordering other memory operations.

This class represents a freeze function that returns random concrete value if an operand is either a ...

static GEPNoWrapFlags noUnsignedWrap()

void applyUpdatesPermissive(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

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

Type * getValueType() const

const Constant * getInitializer() const

getInitializer - Return the initializer for this global variable.

This instruction inserts a struct field of array element value into an aggregate value.

Value * getInsertedValueOperand()

Value * getAggregateOperand()

unsigned getNumIndices() const

idx_iterator idx_begin() const

Base class for instruction visitors.

void visit(Iterator Start, Iterator End)

void setHasNoUnsignedWrap(bool b=true)

Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.

bool hasNoUnsignedWrap() const LLVM_READONLY

Determine whether the no unsigned wrap flag is set.

unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

bool hasNoSignedWrap() const LLVM_READONLY

Determine whether the no signed wrap flag is set.

void setHasNoSignedWrap(bool b=true)

Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

bool isExact() const LLVM_READONLY

Determine whether the exact flag is set.

BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

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

void setNonNeg(bool b=true)

Set or clear the nneg flag on this instruction, which must be a zext instruction.

bool hasNonNeg() const LLVM_READONLY

Determine whether the the nneg flag is set.

unsigned getOpcode() const

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

void setIsExact(bool b=true)

Set or clear the exact flag on this instruction, which must be an operator which supports this flag.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

bool isSpecialTerminator() const

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

@ OB_clang_arc_attachedcall

An instruction for reading from memory.

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

size_type count(const KeyT &Key) const

iterator find(const KeyT &Key)

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

A Module instance is used to store all the information related to an LLVM module.

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.

Resume the propagation of an exception.

Return a value (possibly void), from a function.

Helper class for SCCPSolver.

const PredicateBase * getPredicateInfoFor(Instruction *I)

std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const

bool resolvedUndef(Instruction &I)

void markFunctionUnreachable(Function *F)

bool markBlockExecutable(BasicBlock *BB)

bool resolvedUndefsIn(Function &F)

While solving the dataflow for a function, we don't compute a result for operations with an undef ope...

Constant * getConstant(const ValueLatticeElement &LV, Type *Ty) const

SCCPInstVisitor(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)

const ValueLatticeElement & getLatticeValueFor(Value *V) const

void removeLatticeValueFor(Value *V)

const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()

void trackValueOfArgument(Argument *A)

void visitCallInst(CallInst &I)

void markOverdefined(Value *V)

bool isArgumentTrackedFunction(Function *F)

void addTrackedFunction(Function *F)

void solveWhileResolvedUndefs()

void solveWhileResolvedUndefsIn(Module &M)

void trackValueOfGlobalVariable(GlobalVariable *GV)

Constant * getConstantOrNull(Value *V) const

const SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions() const

const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()

void resetLatticeValueFor(CallBase *Call)

Invalidate the Lattice Value of Call and its users after specializing the call.

const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()

ValueLatticeElement getArgAttributeVL(Argument *A)

void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC)

void addToMustPreserveReturnsInFunctions(Function *F)

void addArgumentTrackedFunction(Function *F)

bool isStructLatticeConstant(Function *F, StructType *STy)

void solveWhileResolvedUndefsIn(SmallVectorImpl< Function * > &WorkList)

bool isBlockExecutable(BasicBlock *BB) const

bool mustPreserveReturn(Function *F)

void setLatticeValueForSpecializationArguments(Function *F, const SmallVectorImpl< ArgInfo > &Args)

bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const

SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...

void visitCall(CallInst &I)

const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()

getTrackedGlobals - Get and return the set of inferred initializers for global variables.

void resetLatticeValueFor(CallBase *Call)

Invalidate the Lattice Value of Call and its users after specializing the call.

void trackValueOfGlobalVariable(GlobalVariable *GV)

trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...

bool tryToReplaceWithConstant(Value *V)

void inferArgAttributes() const

bool isStructLatticeConstant(Function *F, StructType *STy)

void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC)

void solve()

Solve - Solve for constants and executable blocks.

void visit(Instruction *I)

void trackValueOfArgument(Argument *V)

trackValueOfArgument - Mark the specified argument overdefined unless it have range attribute.

void addTrackedFunction(Function *F)

addTrackedFunction - If the SCCP solver is supposed to track calls into and out of the specified func...

void solveWhileResolvedUndefsIn(Module &M)

const PredicateBase * getPredicateInfoFor(Instruction *I)

const SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions() const

bool resolvedUndefsIn(Function &F)

resolvedUndefsIn - While solving the dataflow for a function, we assume that branches on undef values...

void addArgumentTrackedFunction(Function *F)

void solveWhileResolvedUndefs()

void removeLatticeValueFor(Value *V)

std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const

const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()

getMRVFunctionsTracked - Get the set of functions which return multiple values tracked by the pass.

Constant * getConstantOrNull(Value *V) const

Return either a Constant or nullptr for a given Value.

bool simplifyInstsInBlock(BasicBlock &BB, SmallPtrSetImpl< Value * > &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)

Constant * getConstant(const ValueLatticeElement &LV, Type *Ty) const

Helper to return a Constant if LV is either a constant or a constant range with a single element.

const ValueLatticeElement & getLatticeValueFor(Value *V) const

void addToMustPreserveReturnsInFunctions(Function *F)

Add function to the list of functions whose return cannot be modified.

bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, BasicBlock *&NewUnreachableBB) const

bool isBlockExecutable(BasicBlock *BB) const

void inferReturnAttributes() const

bool markBlockExecutable(BasicBlock *BB)

markBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...

void setLatticeValueForSpecializationArguments(Function *F, const SmallVectorImpl< ArgInfo > &Args)

Set the Lattice Value for the arguments of a specialization F.

static bool isConstant(const ValueLatticeElement &LV)

const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals() const

getTrackedRetVals - Get the inferred return value map.

bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const

bool mustPreserveReturn(Function *F)

Returns true if the return of the given function cannot be modified.

static bool isOverdefined(const ValueLatticeElement &LV)

void markFunctionUnreachable(Function *F)

Mark all of the blocks in function F non-executable.

bool isArgumentTrackedFunction(Function *F)

Returns true if the given function is in the solver's set of argument-tracked functions.

SCCPSolver(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)

void markOverdefined(Value *V)

markOverdefined - Mark the specified value overdefined.

This class represents the LLVM 'select' instruction.

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.

bool contains(ConstPtrType Ptr) const

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

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

void assign(size_type NumElts, ValueParamT Elt)

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.

Class to represent struct types.

unsigned getNumElements() const

Random access to the elements.

A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...

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

This class represents a truncation of integer types.

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.

bool isSingleValueType() const

Return true if the type is a valid type for a register in codegen.

unsigned getScalarSizeInBits() const LLVM_READONLY

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

bool isStructTy() const

True if this is an instance of StructType.

bool isVoidTy() const

Return true if this is 'void'.

static UndefValue * get(Type *T)

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

This function has undefined behavior.

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

Value * getOperand(unsigned i) const

This class represents lattice values for constants.

static ValueLatticeElement getRange(ConstantRange CR, bool MayIncludeUndef=false)

bool isOverdefined() const

Constant * getCompare(CmpInst::Predicate Pred, Type *Ty, const ValueLatticeElement &Other, const DataLayout &DL) const

true, false or undef constants, or nullptr if the comparison cannot be evaluated.

bool isConstantRangeIncludingUndef() const

static ValueLatticeElement getNot(Constant *C)

ConstantRange asConstantRange(unsigned BW, bool UndefAllowed=false) const

bool isNotConstant() const

void setNumRangeExtensions(unsigned N)

const ConstantRange & getConstantRange(bool UndefAllowed=true) const

Returns the constant range for this value.

bool isConstantRange(bool UndefAllowed=true) const

Returns true if this value is a constant range.

unsigned getNumRangeExtensions() const

Constant * getNotConstant() const

ValueLatticeElement intersect(const ValueLatticeElement &Other) const

Combine two sets of facts about the same value into a single set of facts.

bool isUnknownOrUndef() const

Constant * getConstant() const

bool mergeIn(const ValueLatticeElement &RHS, MergeOptions Opts=MergeOptions())

Updates this object to approximate both this object and RHS.

bool markConstant(Constant *V, bool MayIncludeUndef=false)

static ValueLatticeElement getOverdefined()

LLVM Value Representation.

Type * getType() const

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

std::string getNameOrAsOperand() const

void replaceAllUsesWith(Value *V)

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

StringRef getName() const

Return a constant reference to the value's name.

void takeName(Value *V)

Transfer the name from V to this value.

Represents an op.with.overflow intrinsic.

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

size_type count(const_arg_type_t< ValueT > V) const

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

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.

This is an optimization pass for GlobalISel generic memory operations.

bool all_of(R &&range, UnaryPredicate P)

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

static bool replaceSignedInst(SCCPSolver &Solver, SmallPtrSetImpl< Value * > &InsertedValues, Instruction &Inst)

Try to replace signed instructions with their unsigned equivalent.

bool canConstantFoldCallTo(const CallBase *Call, const Function *F)

canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.

auto successors(const MachineBasicBlock *BB)

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

Constant * ConstantFoldCall(const CallBase *Call, Function *F, ArrayRef< Constant * > Operands, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)

ConstantFoldCall - Attempt to constant fold a call to the specified function with the specified argum...

ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)

Parse out a conservative ConstantRange from !range metadata.

bool any_of(R &&range, UnaryPredicate P)

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

Constant * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)

Attempt to constant fold a unary operation with the specified operand.

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

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

raw_ostream & dbgs()

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

bool wouldInstructionBeTriviallyDead(const Instruction *I, const TargetLibraryInfo *TLI=nullptr)

Return true if the result produced by the instruction would have no side effects if it was not used.

ConstantRange getVScaleRange(const Function *F, unsigned BitWidth)

Determine the possible constant range of vscale with the given bit width, based on the vscale_range f...

Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)

ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.

Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)

Attempt to constant fold a cast with the specified operand.

Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)

Given operands for a BinaryOperator, fold the result or return null.

DWARFExpression::Operation Op

bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)

Return true if this function can prove that V does not have undef bits and is never poison.

constexpr unsigned BitWidth

OutputIt move(R &&Range, OutputIt Out)

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

Constant * ConstantFoldLoadFromConstPtr(Constant *C, Type *Ty, APInt Offset, const DataLayout &DL)

Return the value that a load from C with offset Offset would produce if it is constant and determinab...

static bool refineInstruction(SCCPSolver &Solver, const SmallPtrSetImpl< Value * > &InsertedValues, Instruction &Inst)

Try to use Inst's value range from Solver to infer the NUW flag.

static void inferAttribute(Function *F, unsigned AttrIndex, const ValueLatticeElement &Val)

Implement std::hash so that hash_code can be used in STL containers.

Struct to control some aspects related to merging constant ranges.

MergeOptions & setMaxWidenSteps(unsigned Steps=1)

MergeOptions & setCheckWiden(bool V=true)