SimpleSValBuilder.cpp Source File (original) (raw)

19#include

21using namespace clang;

22using namespace ento;

24namespace {

25class SimpleSValBuilder : public SValBuilder {

32 static const llvm::APSInt *getConstValue(ProgramStateRef state, SVal V);

58 SVal simplifyUntilFixpoint(ProgramStateRef State, SVal Val);

66public:

67 SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,

68 ProgramStateManager &stateMgr)

69 : SValBuilder(alloc, context, stateMgr) {}

70 ~SimpleSValBuilder() override {}

73 NonLoc lhs, NonLoc rhs, QualType resultTy) override;

75 Loc lhs, Loc rhs, QualType resultTy) override;

77 Loc lhs, NonLoc rhs, QualType resultTy) override;

87 const llvm::APSInt *getMinValue(ProgramStateRef state, SVal V) override;

92 const llvm::APSInt *getMaxValue(ProgramStateRef state, SVal V) override;

97 const llvm::APSInt &RHS, QualType resultTy);

98};

99}

100

104 return new SimpleSValBuilder(alloc, context, stateMgr);

105}

106

107

108

111 const unsigned ValueBits = Value.getSignificantBits();

112 if (ValueBits == ResultType.getBitWidth()) {

113

114

115

117 }

118

119

120

121 return ValueBits < ResultType.getBitWidth();

122}

123

124

125

126

127

128SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS,

130 const llvm::APSInt &RHS,

132 bool isIdempotent = false;

133

134

135 switch (op) {

136 default:

137

138 break;

139 case BO_Mul:

140

141 if (RHS == 0)

142 return makeIntVal(0, resultTy);

143 else if (RHS == 1)

144 isIdempotent = true;

145 break;

146 case BO_Div:

147

148 if (RHS == 0)

149

150 return UndefinedVal();

151 else if (RHS == 1)

152 isIdempotent = true;

153 break;

154 case BO_Rem:

155

156 if (RHS == 0)

157

158 return UndefinedVal();

159 else if (RHS == 1)

160 return makeIntVal(0, resultTy);

161 break;

162 case BO_Add:

163 case BO_Sub:

164 case BO_Shl:

165 case BO_Shr:

166 case BO_Xor:

167

168 if (RHS == 0)

169 isIdempotent = true;

170 break;

171 case BO_And:

172

173 if (RHS == 0)

174 return makeIntVal(0, resultTy);

175 else if (RHS.isAllOnes())

176 isIdempotent = true;

177 break;

178 case BO_Or:

179

180 if (RHS == 0)

181 isIdempotent = true;

182 else if (RHS.isAllOnes()) {

183 return nonloc::ConcreteInt(BasicVals.Convert(resultTy, RHS));

184 }

185 break;

186 }

187

188

189

190

191 if (isIdempotent)

192 return evalCast(nonloc::SymbolVal(LHS), resultTy, QualType{});

193

194

195

196 std::optional ConvertedRHS = BasicVals.getValue(RHS);

198

199

200

201 ASTContext &Ctx = getContext();

202 QualType SymbolType = LHS->getType();

203 uint64_t ValWidth = RHS.getBitWidth();

205

206 if (ValWidth < TypeWidth) {

207

208 ConvertedRHS = BasicVals.Convert(SymbolType, RHS);

209 } else if (ValWidth == TypeWidth) {

210

211

212

214 ConvertedRHS = BasicVals.Convert(SymbolType, RHS);

215 }

217

218

219

220 APSIntType resultIntTy = BasicVals.getAPSIntType(resultTy);

222 ConvertedRHS = BasicVals.getValue(-resultIntTy.convert(RHS));

223 op = (op == BO_Add) ? BO_Sub : BO_Add;

224 } else {

225 ConvertedRHS = BasicVals.Convert(resultTy, RHS);

226 }

227 } else

228 ConvertedRHS = BasicVals.Convert(resultTy, RHS);

229

230 return makeNonLoc(LHS, op, *ConvertedRHS, resultTy);

231}

232

233

241 if (auto DV = Result.getAs<DefinedSVal>()) {

242 return !State->assume(*DV, false);

243 }

244 return false;

245}

246

247

248

249

250

251

256

258 assert(T->isSignedIntegerOrEnumerationType() &&

259 "This only works with signed integers!");

261

265}

266

267

271 "This only works with signed integers!");

272

274 return (I <= Max) && (I >= -Max);

275}

276

279 if (const auto *SymInt = dyn_cast(Sym))

281 return std::make_pair(SymInt->getLHS(),

282 (SymInt->getOpcode() == BO_Add)

283 ? BV.getValue(SymInt->getRHS())

284 : BV.getValue(-SymInt->getRHS()));

285

286

287 return std::make_pair(Sym, BV.getValue(0, Sym->getType()));

288}

289

290

291

292

295 SymbolRef LSym, llvm::APSInt LInt,

296 SymbolRef RSym, llvm::APSInt RInt) {

300

302 assert(SymTy == RSym->getType() &&

303 "Symbols are not of the same type!");

305 "Integers are not of the same type as symbols!");

307 "Integers are not of the same type as symbols!");

308

313 ResultTy = SymTy;

314 else

315 llvm_unreachable("Operation not suitable for unchecked rearrangement!");

316

317 if (LSym == RSym)

318 return SVB

322

325 llvm::APSInt ResultInt;

327

328

329

330 if (LInt > RInt) {

331 ResultSym = SymMgr.acquire<SymSymExpr>(RSym, BO_Sub, LSym, SymTy);

333 ResultInt = LInt - RInt;

334 } else {

335 ResultSym = SymMgr.acquire<SymSymExpr>(LSym, BO_Sub, RSym, SymTy);

336 ResultOp = Op;

337 ResultInt = RInt - LInt;

338 }

339 } else {

341 ResultInt = (Op == BO_Add) ? (LInt + RInt) : (LInt - RInt);

342 ResultOp = BO_Add;

343

344 if (ResultInt < 0) {

345 ResultInt = -ResultInt;

346 ResultOp = BO_Sub;

347 } else if (ResultInt == 0) {

348

350 }

351 }

352 APSIntPtr PersistentResultInt = BV.getValue(ResultInt);

354 ResultSym, ResultOp, PersistentResultInt, ResultTy));

355}

356

357

358

359

362 return Sym->getType() == Ty &&

366}

367

373

374

376

377

378

379

380 if (!SVB.getAnalyzerOptions().ShouldAggressivelySimplifyBinaryOperation)

381 return std::nullopt;

382

384 if (!LSym)

385 return std::nullopt;

386

388 SingleTy = LSym->getType();

390 return std::nullopt;

391

393 SingleTy = ResultTy;

394 if (LSym->getType() != SingleTy)

395 return std::nullopt;

396 } else {

397

398 return std::nullopt;

399 }

400

401 assert(!SingleTy.isNull() && "We should have figured out the type by now!");

402

403

405 return std::nullopt;

406

408 if (!RSym || RSym->getType() != SingleTy)

409 return std::nullopt;

410

412 llvm::APSInt LInt, RInt;

417 return std::nullopt;

418

419

421}

422

423SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state,

425 NonLoc lhs, NonLoc rhs,

426 QualType resultTy) {

427 NonLoc InputLHS = lhs;

428 NonLoc InputRHS = rhs;

429

430

431

432 SVal simplifiedLhs = simplifySVal(state, lhs);

433 SVal simplifiedRhs = simplifySVal(state, rhs);

434 if (auto simplifiedLhsAsNonLoc = simplifiedLhs.getAs())

435 lhs = *simplifiedLhsAsNonLoc;

436 if (auto simplifiedRhsAsNonLoc = simplifiedRhs.getAs())

437 rhs = *simplifiedRhsAsNonLoc;

438

439

440 if (lhs == rhs)

441 switch (op) {

442 default:

443 break;

444 case BO_EQ:

445 case BO_LE:

446 case BO_GE:

447 return makeTruthVal(true, resultTy);

448 case BO_LT:

449 case BO_GT:

450 case BO_NE:

451 return makeTruthVal(false, resultTy);

452 case BO_Xor:

453 case BO_Sub:

455 return makeIntVal(0, resultTy);

456 return evalCast(makeIntVal(0, false), resultTy,

457 QualType{});

458 case BO_Or:

459 case BO_And:

460 return evalCast(lhs, resultTy, QualType{});

461 }

462

463 while (true) {

465 default:

466 return makeSymExprValNN(op, lhs, rhs, resultTy);

467 case nonloc::PointerToMemberKind: {

468 assert(rhs.getKind() == nonloc::PointerToMemberKind &&

469 "Both SVals should have pointer-to-member-type");

470 auto LPTM = lhs.castAs nonloc::PointerToMember(),

471 RPTM = rhs.castAs nonloc::PointerToMember();

472 auto LPTMD = LPTM.getPTMData(), RPTMD = RPTM.getPTMData();

473 switch (op) {

474 case BO_EQ:

475 return makeTruthVal(LPTMD == RPTMD, resultTy);

476 case BO_NE:

477 return makeTruthVal(LPTMD != RPTMD, resultTy);

478 default:

479 return UnknownVal();

480 }

481 }

482 case nonloc::LocAsIntegerKind: {

483 Loc lhsL = lhs.castAs nonloc::LocAsInteger().getLoc();

485 case nonloc::LocAsIntegerKind:

486

487

489 return UnknownVal();

490 return evalBinOpLL(state, op, lhsL,

491 rhs.castAs nonloc::LocAsInteger().getLoc(),

492 resultTy);

493 case nonloc::ConcreteIntKind: {

494

495

497 return UnknownVal();

498

499

500

501

502 llvm::APSInt i = rhs.castAs nonloc::ConcreteInt().getValue();

503

504

505

506

507

509 BasicVals.getAPSIntType(lSym->getType()).apply(i);

510 else

511 BasicVals.getAPSIntType(Context.VoidPtrTy).apply(i);

512 return evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy);

513 }

514 default:

515 switch (op) {

516 case BO_EQ:

517 return makeTruthVal(false, resultTy);

518 case BO_NE:

519 return makeTruthVal(true, resultTy);

520 default:

521

522 return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);

523 }

524 }

525 }

526 case nonloc::ConcreteIntKind: {

527 llvm::APSInt LHSValue = lhs.castAs nonloc::ConcreteInt().getValue();

528

529

530 if (const llvm::APSInt *KnownRHSValue = getConstValue(state, rhs)) {

531 llvm::APSInt RHSValue = *KnownRHSValue;

533

534

535

536 APSIntType CompareType = std::max(APSIntType(LHSValue),

537 APSIntType(RHSValue));

538 CompareType.apply(LHSValue);

539 CompareType.apply(RHSValue);

541 APSIntType IntType = BasicVals.getAPSIntType(resultTy);

542 IntType.apply(LHSValue);

543 IntType.apply(RHSValue);

544 }

545

546 std::optional Result =

547 BasicVals.evalAPSInt(op, LHSValue, RHSValue);

549 if (op == BO_Shl || op == BO_Shr) {

550

551

552

553

554

555

556

557

558

559 return UnknownVal();

560 }

561 return UndefinedVal();

562 }

563

564 return nonloc::ConcreteInt(*Result);

565 }

566

567

568

569

570

571 switch (op) {

572 case BO_LT:

573 case BO_GT:

574 case BO_LE:

575 case BO_GE:

577 [[fallthrough]];

578 case BO_EQ:

579 case BO_NE:

580 case BO_Add:

581 case BO_Mul:

582 case BO_And:

583 case BO_Xor:

584 case BO_Or:

585 std::swap(lhs, rhs);

586 continue;

587 case BO_Shr:

588

589 if (LHSValue.isAllOnes() && LHSValue.isSigned())

590 return evalCast(lhs, resultTy, QualType{});

591 [[fallthrough]];

592 case BO_Shl:

593

594 if (LHSValue == 0)

595 return evalCast(lhs, resultTy, QualType{});

596 return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);

597 case BO_Div:

598

599 case BO_Rem:

600

601 if (LHSValue == 0)

602 return makeZeroVal(resultTy);

603 [[fallthrough]];

604 default:

605 return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);

606 }

607 }

608 case nonloc::SymbolValKind: {

609

610 SymbolRef Sym = lhs.castAs nonloc::SymbolVal().getSymbol();

611

612

613 if (const SymIntExpr *symIntExpr = dyn_cast(Sym)) {

614

615

617

618

620 switch (opc) {

621 default:

622

623

624 break;

625 case BO_LAnd:

626 case BO_LOr:

627 llvm_unreachable("Logical operators handled by branching logic.");

628 case BO_Assign:

629 case BO_MulAssign:

630 case BO_DivAssign:

631 case BO_RemAssign:

632 case BO_AddAssign:

633 case BO_SubAssign:

634 case BO_ShlAssign:

635 case BO_ShrAssign:

636 case BO_AndAssign:

637 case BO_XorAssign:

638 case BO_OrAssign:

639 case BO_Comma:

640 llvm_unreachable("'=' and ',' operators handled by ExprEngine.");

641 case BO_PtrMemD:

642 case BO_PtrMemI:

643 llvm_unreachable("Pointer arithmetic not handled here.");

644 case BO_LT:

645 case BO_GT:

646 case BO_LE:

647 case BO_GE:

648 case BO_EQ:

649 case BO_NE:

651 resultTy == getConditionType());

652 assert(symIntExpr->getType()->isBooleanType() ||

653 getContext().hasSameUnqualifiedType(symIntExpr->getType(),

654 getConditionType()));

655

657 return makeNonLoc(symIntExpr->getLHS(), opc,

658 symIntExpr->getRHS(), resultTy);

659 }

660 }

661

662

663 if (const llvm::APSInt *RHSValue = getConstValue(state, rhs)) {

664

665

669

670

671

672

673

674

675

676 APSIntType IntType = BasicVals.getAPSIntType(resultTy);

677 const llvm::APSInt &first = IntType.convert(symIntExpr->getRHS());

678 const llvm::APSInt &second = IntType.convert(*RHSValue);

679

680

681

682

683

684

685

686

687 std::optional newRHS;

688 if (lop == op) {

689 newRHS = BasicVals.evalAPSInt(BO_Add, first, second);

690 } else if (first >= second) {

691 newRHS = BasicVals.evalAPSInt(BO_Sub, first, second);

692 op = lop;

693 } else {

694 newRHS = BasicVals.evalAPSInt(BO_Sub, second, first);

695 }

696

697 assert(newRHS && "Invalid operation despite common type!");

698 rhs = nonloc::ConcreteInt(*newRHS);

699 lhs = nonloc::SymbolVal(symIntExpr->getLHS());

700 continue;

701 }

702 }

703

704

705 return MakeSymIntVal(symIntExpr, op, *RHSValue, resultTy);

706 }

707 }

708

709

710 if (const llvm::APSInt *RHSValue = getConstValue(state, rhs))

711 return MakeSymIntVal(Sym, op, *RHSValue, resultTy);

712

713 if (std::optional V = tryRearrange(state, op, lhs, rhs, resultTy))

714 return *V;

715

716

717 return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);

718 }

719 }

720 }

721}

722

727 SimpleSValBuilder &SVB) {

728

731

732

733

734

737

741

742

743

746

747

748

749 if (op == BO_EQ)

750 return SVB.makeTruthVal(false, resultTy);

751 if (op == BO_NE)

752 return SVB.makeTruthVal(true, resultTy);

753

754

755

756

757

758 bool leftFirst = (op == BO_LT || op == BO_LE);

759 for (const auto *I : RD->fields()) {

760 if (I == LeftFD)

761 return SVB.makeTruthVal(leftFirst, resultTy);

762 if (I == RightFD)

763 return SVB.makeTruthVal(!leftFirst, resultTy);

764 }

765

766 llvm_unreachable("Fields not found in parent record's definition");

767}

768

769

770

771

772

773

774

775

777 Loc LhsLoc) {

778

779 ASTContext &Ctx = State->getStateManager().getContext();

780 uint64_t RhsBitwidth =

782 uint64_t LhsBitwidth =

784 if (RhsBitwidth && LhsBitwidth && (LhsLoc.getKind() == RhsLoc.getKind())) {

785 assert(RhsBitwidth == LhsBitwidth &&

786 "RhsLoc and LhsLoc bitwidth must be same!");

787 }

788}

789

790

791SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,

793 Loc lhs, Loc rhs,

794 QualType resultTy) {

795

796

797

798

799

800

802

803

804

805

806

807

808

810 return UnknownVal();

811

812

813 if (lhs == rhs) {

814 switch (op) {

815 default:

816 llvm_unreachable("Unimplemented operation for two identical values");

817 case BO_Sub:

818 return makeZeroVal(resultTy);

819 case BO_EQ:

820 case BO_LE:

821 case BO_GE:

822 return makeTruthVal(true, resultTy);

823 case BO_NE:

824 case BO_LT:

825 case BO_GT:

826 return makeTruthVal(false, resultTy);

827 }

828 }

829

831 default:

832 llvm_unreachable("Ordering not implemented for this Loc.");

833

834 case loc::GotoLabelKind:

835

837 switch (op) {

838 default:

839 break;

840 case BO_Sub:

841 return evalCast(lhs, resultTy, QualType{});

842 case BO_EQ:

843 case BO_LE:

844 case BO_LT:

845 return makeTruthVal(false, resultTy);

846 case BO_NE:

847 case BO_GT:

848 case BO_GE:

849 return makeTruthVal(true, resultTy);

850 }

851 }

852

853

854

855

856

857 return UnknownVal();

858

859 case loc::ConcreteIntKind: {

860 auto L = lhs.castAs loc::ConcreteInt();

861

862

863

865 if (op == BO_Cmp)

866 return UnknownVal();

867

869 return makeNonLoc(L.getValue(), op, rSym, resultTy);

870

872 return makeNonLoc(rSym, op, L.getValue(), resultTy);

873 }

874

875

876 if (std::optionalloc::ConcreteInt rInt = rhs.getAs loc::ConcreteInt()) {

878

879 if (std::optional ResultInt =

880 BasicVals.evalAPSInt(op, L.getValue(), rInt->getValue()))

881 return evalCast(nonloc::ConcreteInt(*ResultInt), resultTy, QualType{});

882 return UnknownVal();

883 }

884

885

886

887

888

891 switch (op) {

892 default:

893 break;

894 case BO_EQ:

895 case BO_GT:

896 case BO_GE:

897 return makeTruthVal(false, resultTy);

898 case BO_NE:

899 case BO_LT:

900 case BO_LE:

901 return makeTruthVal(true, resultTy);

902 }

903 }

904

905

906

907 return UnknownVal();

908 }

909 case loc::MemRegionValKind: {

910 if (std::optionalloc::ConcreteInt rInt = rhs.getAs loc::ConcreteInt()) {

911

912

915 return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy);

916 return UnknownVal();

917 }

918

919

920

921

922 if (rInt->isZeroConstant()) {

923 if (op == BO_Sub)

924 return evalCast(lhs, resultTy, QualType{});

925

927 QualType boolType = getContext().BoolTy;

928 NonLoc l = evalCast(lhs, boolType, QualType{}).castAs();

929 NonLoc r = makeTruthVal(false, boolType).castAs();

930 return evalBinOpNN(state, op, l, r, resultTy);

931 }

932 }

933

934

935 return UnknownVal();

936 }

937

938

939 const MemRegion *LeftMR = lhs.getAsRegion();

940 assert(LeftMR && "MemRegionValKind SVal doesn't have a region!");

941

942 const MemRegion *RightMR = rhs.getAsRegion();

943 if (!RightMR)

944

945

946

947 return UnknownVal();

948

949 const MemRegion *LeftBase = LeftMR->getBaseRegion();

950 const MemRegion *RightBase = RightMR->getBaseRegion();

951 const MemSpaceRegion *LeftMS = LeftBase->getMemorySpace(state);

952 const MemSpaceRegion *RightMS = RightBase->getMemorySpace(state);

953 const MemSpaceRegion *UnknownMS = MemMgr.getUnknownRegion();

954

955

956

957

958 if (LeftMS != RightMS &&

959 ((LeftMS != UnknownMS && RightMS != UnknownMS) ||

961 switch (op) {

962 default:

963 return UnknownVal();

964 case BO_EQ:

965 return makeTruthVal(false, resultTy);

966 case BO_NE:

967 return makeTruthVal(true, resultTy);

968 }

969 }

970

971

972

973

974

975

976

977

978

979

980

981 if (LeftBase != RightBase &&

984 switch (op) {

985 default:

986 return UnknownVal();

987 case BO_EQ:

988 return makeTruthVal(false, resultTy);

989 case BO_NE:

990 return makeTruthVal(true, resultTy);

991 }

992 }

993

994

995 const ElementRegion *RightER = dyn_cast(RightMR);

996 const ElementRegion *LeftER = dyn_cast(LeftMR);

997 if (RightER && LeftER) {

998

999

1000

1001

1004

1005

1006 SVal LeftIndexVal = LeftER->getIndex();

1007 std::optional LeftIndex = LeftIndexVal.getAs();

1008 if (!LeftIndex)

1009 return UnknownVal();

1010 LeftIndexVal = evalCast(*LeftIndex, ArrayIndexTy, QualType{});

1011 LeftIndex = LeftIndexVal.getAs();

1012 if (!LeftIndex)

1013 return UnknownVal();

1014

1015

1016 SVal RightIndexVal = RightER->getIndex();

1017 std::optional RightIndex = RightIndexVal.getAs();

1018 if (!RightIndex)

1019 return UnknownVal();

1020 RightIndexVal = evalCast(*RightIndex, ArrayIndexTy, QualType{});

1021 RightIndex = RightIndexVal.getAs();

1022 if (!RightIndex)

1023 return UnknownVal();

1024

1025

1026

1027 return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy);

1028 }

1029 }

1030

1031

1032 const FieldRegion *RightFR = dyn_cast(RightMR);

1033 const FieldRegion *LeftFR = dyn_cast(LeftMR);

1034 if (RightFR && LeftFR) {

1036 *this);

1038 return R;

1039 }

1040

1041

1042 RegionOffset LeftOffset = LeftMR->getAsOffset();

1043 RegionOffset RightOffset = RightMR->getAsOffset();

1044

1045 if (LeftOffset.getRegion() != nullptr &&

1050

1051 switch (op) {

1052 default:

1053 return UnknownVal();

1054 case BO_LT:

1055 return makeTruthVal(left < right, resultTy);

1056 case BO_GT:

1057 return makeTruthVal(left > right, resultTy);

1058 case BO_LE:

1059 return makeTruthVal(left <= right, resultTy);

1060 case BO_GE:

1061 return makeTruthVal(left >= right, resultTy);

1062 case BO_EQ:

1063 return makeTruthVal(left == right, resultTy);

1064 case BO_NE:

1065 return makeTruthVal(left != right, resultTy);

1066 }

1067 }

1068

1069

1070

1073 if (LHSSym && RHSSym)

1074 return makeNonLoc(LHSSym, op, RHSSym, resultTy);

1075

1076

1077 return UnknownVal();

1078 }

1079 }

1080}

1081

1082SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state,

1084 NonLoc rhs, QualType resultTy) {

1085 if (op >= BO_PtrMemD && op <= BO_PtrMemI) {

1086 if (auto PTMSV = rhs.getAs nonloc::PointerToMember()) {

1087 if (PTMSV->isNullMemberPointer())

1088 return UndefinedVal();

1089

1090 auto getFieldLValue = [&](const auto *FD) -> SVal {

1092

1093 for (const auto &I : *PTMSV)

1094 Result = StateMgr.getStoreManager().evalDerivedToBase(

1095 Result, I->getType(), I->isVirtual());

1096

1097 return state->getLValue(FD, Result);

1098 };

1099

1100 if (const auto *FD = PTMSV->getDeclAs()) {

1101 return getFieldLValue(FD);

1102 }

1103 if (const auto *FD = PTMSV->getDeclAs()) {

1104 return getFieldLValue(FD);

1105 }

1106 }

1107

1108 return rhs;

1109 }

1110

1112 "arguments to comparison ops must be of the same type");

1113

1114 SVal simplifiedRhs = simplifySVal(state, rhs);

1115 if (auto simplifiedRhsAsNonLoc = simplifiedRhs.getAs())

1116 rhs = *simplifiedRhsAsNonLoc;

1117

1118

1120 return lhs;

1121

1122

1124 return lhs;

1125

1126

1127

1128

1129 if (std::optionalnonloc::ConcreteInt rhsInt =

1130 rhs.getAs nonloc::ConcreteInt()) {

1131 if (std::optionalloc::ConcreteInt lhsInt =

1132 lhs.getAs loc::ConcreteInt()) {

1133 const llvm::APSInt &leftI = lhsInt->getValue();

1134 assert(leftI.isUnsigned());

1135 llvm::APSInt rightI(rhsInt->getValue(), true);

1136

1137

1138

1139 rightI = rightI.extOrTrunc(leftI.getBitWidth());

1140

1141

1142 llvm::APSInt Multiplicand(rightI.getBitWidth(), true);

1144 Multiplicand = getContext().getTypeSizeInChars(pointeeType).getQuantity();

1145 rightI *= Multiplicand;

1146

1147

1148 switch (op) {

1149 case BO_Add:

1150 rightI = leftI + rightI;

1151 break;

1152 case BO_Sub:

1153 rightI = leftI - rightI;

1154 break;

1155 default:

1156 llvm_unreachable("Invalid pointer arithmetic operation");

1157 }

1158 return loc::ConcreteInt(getBasicValueFactory().getValue(rightI));

1159 }

1160 }

1161

1162

1163 if (const MemRegion *region = lhs.getAsRegion()) {

1164 rhs = convertToArrayIndex(rhs).castAs();

1165 SVal index = UnknownVal();

1166 const SubRegion *superR = nullptr;

1167

1168

1169 QualType elementType;

1170

1171 if (const ElementRegion *elemReg = dyn_cast(region)) {

1172 assert(op == BO_Add || op == BO_Sub);

1173 index = evalBinOpNN(state, op, elemReg->getIndex(), rhs,

1174 getArrayIndexType());

1176 elementType = elemReg->getElementType();

1177 }

1179 assert(op == BO_Add || op == BO_Sub);

1180 index = (op == BO_Add) ? rhs : evalMinus(rhs);

1182

1183

1184

1185

1188 }

1189

1190

1191

1192

1194 elementType = getContext().CharTy;

1195

1196 if (std::optional indexV = index.getAs()) {

1197 return loc::MemRegionVal(MemMgr.getElementRegion(elementType, *indexV,

1198 superR, getContext()));

1199 }

1200 }

1201 return UnknownVal();

1202}

1203

1204const llvm::APSInt *SimpleSValBuilder::getConstValue(ProgramStateRef state,

1205 SVal V) {

1207 return Res;

1208

1209 if (SymbolRef Sym = V.getAsSymbol())

1210 return state->getConstraintManager().getSymVal(state, Sym);

1211

1212 return nullptr;

1213}

1214

1215const llvm::APSInt *SimpleSValBuilder::getConcreteValue(SVal V) {

1216 if (std::optionalloc::ConcreteInt X = V.getAsloc::ConcreteInt())

1217 return X->getValue().get();

1218

1219 if (std::optionalnonloc::ConcreteInt X = V.getAsnonloc::ConcreteInt())

1220 return X->getValue().get();

1221

1222 return nullptr;

1223}

1224

1225const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state,

1226 SVal V) {

1227 return getConstValue(state, simplifySVal(state, V));

1228}

1229

1230const llvm::APSInt *SimpleSValBuilder::getMinValue(ProgramStateRef state,

1231 SVal V) {

1232 V = simplifySVal(state, V);

1233

1235 return Res;

1236

1237 if (SymbolRef Sym = V.getAsSymbol())

1238 return state->getConstraintManager().getSymMinVal(state, Sym);

1239

1240 return nullptr;

1241}

1242

1243const llvm::APSInt *SimpleSValBuilder::getMaxValue(ProgramStateRef state,

1244 SVal V) {

1245 V = simplifySVal(state, V);

1246

1248 return Res;

1249

1250 if (SymbolRef Sym = V.getAsSymbol())

1251 return state->getConstraintManager().getSymMaxVal(state, Sym);

1252

1253 return nullptr;

1254}

1255

1256SVal SimpleSValBuilder::simplifyUntilFixpoint(ProgramStateRef State, SVal Val) {

1257 SVal SimplifiedVal = simplifySValOnce(State, Val);

1258 while (SimplifiedVal != Val) {

1259 Val = SimplifiedVal;

1260 SimplifiedVal = simplifySValOnce(State, Val);

1261 }

1262 return SimplifiedVal;

1263}

1264

1265SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {

1266 return simplifyUntilFixpoint(State, V);

1267}

1268

1269SVal SimpleSValBuilder::simplifySValOnce(ProgramStateRef State, SVal V) {

1270

1271

1272

1273

1274 class Simplifier : public FullSValVisitor<Simplifier, SVal> {

1276 SValBuilder &SVB;

1277

1278

1279

1280

1281

1282 llvm::DenseMap<SymbolRef, SVal> Cached;

1283

1284 static bool isUnchanged(SymbolRef Sym, SVal Val) {

1286 }

1287

1289 Cached[Sym] = V;

1290 return V;

1291 }

1292

1295 }

1296

1297

1298

1300 const llvm::APSInt *Const =

1301 State->getConstraintManager().getSymVal(State, Sym);

1302 if (Const)

1305 return UndefinedVal();

1306 }

1307

1308 SVal getConstOrVisit(SymbolRef Sym) {

1310 if (Ret.isUndef())

1311 return Visit(Sym);

1312 return Ret;

1313 }

1314

1315 public:

1317 : State(State), SVB(State->getStateManager().getSValBuilder()) {}

1318

1319 SVal VisitSymbolData(const SymbolData *S) {

1320

1321 if (const llvm::APSInt *I =

1322 State->getConstraintManager().getSymVal(State, S))

1326 }

1327

1328 SVal VisitSymIntExpr(const SymIntExpr *S) {

1329 auto I = Cached.find(S);

1330 if (I != Cached.end())

1331 return I->second;

1332

1333 SVal LHS = getConstOrVisit(S->getLHS());

1334 if (isUnchanged(S->getLHS(), LHS))

1335 return skip(S);

1336

1337 SVal RHS;

1338

1339

1340

1341

1344

1345

1346

1350 }

1352 } else {

1354 }

1355

1356 return cache(

1358 }

1359

1360 SVal VisitIntSymExpr(const IntSymExpr *S) {

1361 auto I = Cached.find(S);

1362 if (I != Cached.end())

1363 return I->second;

1364

1365 SVal RHS = getConstOrVisit(S->getRHS());

1366 if (isUnchanged(S->getRHS(), RHS))

1367 return skip(S);

1368

1370 return cache(

1372 }

1373

1374 SVal VisitSymSymExpr(const SymSymExpr *S) {

1375 auto I = Cached.find(S);

1376 if (I != Cached.end())

1377 return I->second;

1378

1379

1380

1381

1382

1385 return skip(S);

1386

1387 SVal LHS = getConstOrVisit(S->getLHS());

1388 SVal RHS = getConstOrVisit(S->getRHS());

1389

1390 if (isUnchanged(S->getLHS(), LHS) && isUnchanged(S->getRHS(), RHS))

1391 return skip(S);

1392

1393 return cache(

1395 }

1396

1397 SVal VisitSymbolCast(const SymbolCast *S) {

1398 auto I = Cached.find(S);

1399 if (I != Cached.end())

1400 return I->second;

1401 const SymExpr *OpSym = S->getOperand();

1402 SVal OpVal = getConstOrVisit(OpSym);

1403 if (isUnchanged(OpSym, OpVal))

1404 return skip(S);

1405

1407 }

1408

1409 SVal VisitUnarySymExpr(const UnarySymExpr *S) {

1410 auto I = Cached.find(S);

1411 if (I != Cached.end())

1412 return I->second;

1413 SVal Op = getConstOrVisit(S->getOperand());

1414 if (isUnchanged(S->getOperand(), Op))

1415 return skip(S);

1416

1417 return cache(

1419 }

1420

1421 SVal VisitSymExpr(SymbolRef S) { return nonloc::SymbolVal(S); }

1422

1423 SVal VisitMemRegion(const MemRegion *R) { return loc::MemRegionVal(R); }

1424

1425 SVal VisitSymbolVal(nonloc::SymbolVal V) {

1426

1427

1428 return Visit(V.getSymbol());

1429 }

1430

1431 SVal VisitSVal(SVal V) { return V; }

1432 };

1433

1434 SVal SimplifiedV = Simplifier(State).Visit(V);

1435 return SimplifiedV;

1436}

static std::optional< int64_t > getConcreteValue(NonLoc SV)

mlir::Value getConst(mlir::OpBuilder &bld, mlir::Location loc, mlir::Type typ, unsigned val)

static bool isInRelation(BinaryOperator::Opcode Rel, SymbolRef Sym, llvm::APSInt Bound, ProgramStateRef State)

Definition SimpleSValBuilder.cpp:234

static NonLoc doRearrangeUnchecked(ProgramStateRef State, BinaryOperator::Opcode Op, SymbolRef LSym, llvm::APSInt LInt, SymbolRef RSym, llvm::APSInt RInt)

Definition SimpleSValBuilder.cpp:293

static bool isNegationValuePreserving(const llvm::APSInt &Value, APSIntType ResultType)

Definition SimpleSValBuilder.cpp:109

static std::optional< NonLoc > tryRearrange(ProgramStateRef State, BinaryOperator::Opcode Op, NonLoc Lhs, NonLoc Rhs, QualType ResultTy)

Definition SimpleSValBuilder.cpp:368

static bool shouldRearrange(ProgramStateRef State, BinaryOperator::Opcode Op, SymbolRef Sym, llvm::APSInt Int, QualType Ty)

Definition SimpleSValBuilder.cpp:360

static SVal evalBinOpFieldRegionFieldRegion(const FieldRegion *LeftFR, const FieldRegion *RightFR, BinaryOperator::Opcode op, QualType resultTy, SimpleSValBuilder &SVB)

Definition SimpleSValBuilder.cpp:723

static bool isWithinConstantOverflowBounds(SymbolRef Sym, ProgramStateRef State)

Definition SimpleSValBuilder.cpp:252

static std::pair< SymbolRef, APSIntPtr > decomposeSymbol(SymbolRef Sym, BasicValueFactory &BV)

Definition SimpleSValBuilder.cpp:277

static void assertEqualBitWidths(ProgramStateRef State, Loc RhsLoc, Loc LhsLoc)

Definition SimpleSValBuilder.cpp:776

static std::optional< int64_t > getKnownValue(ProgramStateRef State, SVal V)

Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...

uint64_t getTypeSize(QualType T) const

Return the size of the specified (complete) type T, in bits.

static bool isComparisonOp(Opcode Opc)

bool isComparisonOp() const

static Opcode negateComparisonOp(Opcode Opc)

static Opcode reverseComparisonOp(Opcode Opc)

bool isAdditiveOp() const

static bool isAdditiveOp(Opcode Opc)

BinaryOperatorKind Opcode

Represents a member of a struct/union/class.

const RecordDecl * getParent() const

Returns the parent of this field declaration, which is the struct in which this field is defined.

A (possibly-)qualified type.

bool isNull() const

Return true if this QualType doesn't point to a type yet.

Represents a struct/union/class.

field_range fields() const

bool isBooleanType() const

bool isSignedIntegerOrEnumerationType() const

Determines whether this is an integer type that is signed or an enumeration types whose underlying ty...

QualType getPointeeType() const

If this is a pointer, ObjC object pointer, or block pointer, this returns the respective pointee.

bool isIntegralOrEnumerationType() const

Determine whether this type is an integral or enumeration type.

bool isAnyPointerType() const

A safe wrapper around APSInt objects allocated and owned by BasicValueFactory.

A record of the "type" of an APSInt, used for conversions.

uint32_t getBitWidth() const

llvm::APSInt getMaxValue() const LLVM_READONLY

Returns the maximum value for this type.

void apply(llvm::APSInt &Value) const

Convert a given APSInt, in place, to match this type.

llvm::APSInt convert(const llvm::APSInt &Value) const LLVM_READONLY

Convert and return a new APSInt with the given value, but this type's bit width and signedness.

llvm::APSInt getValue(uint64_t RawValue) const LLVM_READONLY

APSIntType getAPSIntType(QualType T) const

Returns the type of the APSInt used to store values of the given QualType.

QualType getType() const override

BinaryOperator::Opcode getOpcode() const

QualType getElementType() const

LLVM_ATTRIBUTE_RETURNS_NONNULL const FieldDecl * getDecl() const override

static bool isLocType(QualType T)

RegionOffset getAsOffset() const

Compute the offset within the top level memory object.

LLVM_ATTRIBUTE_RETURNS_NONNULL const MemSpaceRegion * getMemorySpace(ProgramStateRef State) const

Returns the most specific memory space for this memory region in the given ProgramStateRef.

LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getBaseRegion() const

SValBuilder & getSValBuilder()

bool hasSymbolicOffset() const

const MemRegion * getRegion() const

It might return null.

int64_t getOffset() const

BasicValueFactory & getBasicValueFactory()

ProgramStateManager & getStateManager()

nonloc::ConcreteInt makeIntVal(const IntegerLiteral *integer)

loc::MemRegionVal makeLoc(SymbolRef sym)

virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy)=0

Create a new value which represents a binary expression with two non- location operands.

DefinedSVal makeSymbolVal(SymbolRef Sym)

Make an SVal that represents the given symbol.

SVal evalCast(SVal V, QualType CastTy, QualType OriginalTy)

Cast a given SVal to another SVal using given QualType's.

const AnalyzerOptions & getAnalyzerOptions() const

QualType getConditionType() const

SVal evalUnaryOp(ProgramStateRef state, UnaryOperator::Opcode opc, SVal operand, QualType type)

SymbolManager & getSymbolManager()

SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, SVal lhs, SVal rhs, QualType type)

loc::ConcreteInt makeIntLocVal(const llvm::APSInt &integer)

SVal - This represents a symbolic expression, which can be either an L-value or an R-value.

bool isZeroConstant() const

SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const

If this SVal wraps a symbol return that SymbolRef.

std::optional< T > getAs() const

Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.

QualType getType(const ASTContext &) const

Try to get a reasonable type for the given value.

SymbolRef getAsLocSymbol(bool IncludeBaseRegions=false) const

If this SVal is a location and wraps a symbol, return that SymbolRef.

const MemRegion * getAsRegion() const

T castAs() const

Convert to the specified SVal type, asserting that this SVal is of the desired type.

LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getSuperRegion() const

virtual QualType getType() const =0

QualType getType() const override

LLVM_ATTRIBUTE_RETURNS_NONNULL const SymExpr * getOperand() const

const SymExprT * acquire(Args &&...args)

Create or retrieve a SymExpr of type SymExprT for the given arguments.

QualType getType() const override

UnaryOperator::Opcode getOpcode() const

const SymExpr * getOperand() const

Value representing integer constant.

Represents symbolic expression that isn't a location.

SValBuilder * createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, ProgramStateManager &stateMgr)

Definition SimpleSValBuilder.cpp:101

BinarySymExprImpl< APSIntPtr, const SymExpr *, SymExpr::Kind::IntSymExprKind > IntSymExpr

Represents a symbolic expression like 3 - 'x'.

IntrusiveRefCntPtr< const ProgramState > ProgramStateRef

const SymExpr * SymbolRef

BinarySymExprImpl< const SymExpr *, const SymExpr *, SymExpr::Kind::SymSymExprKind > SymSymExpr

Represents a symbolic expression like 'x' + 'y'.

BinarySymExprImpl< const SymExpr *, APSIntPtr, SymExpr::Kind::SymIntExprKind > SymIntExpr

Represents a symbolic expression like 'x' + 3.

bool Const(InterpState &S, CodePtr OpPC, const T &Arg)

bool Ret(InterpState &S, CodePtr &PC)

The JSON file list parser is used to communicate input to InstallAPI.

bool isa(CodeGen::Address addr)

@ Result

The result type of a method or function.

const FunctionProtoType * T

U cast(CodeGen::Address addr)