SimpleSValBuilder.cpp Source File (original) (raw)

19#include

21using namespace clang;

22using namespace ento;

24namespace {

25class SimpleSValBuilder : public SValBuilder {

66public:

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

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

70 ~SimpleSValBuilder() 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

151 else if (RHS == 1)

152 isIdempotent = true;

153 break;

154 case BO_Rem:

155

156 if (RHS == 0)

157

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

184 }

185 break;

186 }

187

188

189

190

191 if (isIdempotent)

193

194

195

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

198

199

200

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

236 SValBuilder &SVB = State->getStateManager().getSValBuilder();

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

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

243 }

244 return false;

245}

246

247

248

249

250

251

254 SValBuilder &SVB = State->getStateManager().getSValBuilder();

256

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

297 SValBuilder &SVB = State->getStateManager().getSValBuilder();

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

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

435 lhs = *simplifiedLhsAsNonLoc;

436 if (auto simplifiedRhsAsNonLoc = simplifiedRhs.getAs<NonLoc>())

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,

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

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:

480 }

481 }

482 case nonloc::LocAsIntegerKind: {

485 case nonloc::LocAsIntegerKind:

486

487

490 return evalBinOpLL(state, op, lhsL,

492 resultTy);

493 case nonloc::ConcreteIntKind: {

494

495

498

499

500

501

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: {

528

529

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

531 llvm::APSInt RHSValue = *KnownRHSValue;

533

534

535

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

548 if (!Result) {

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

550

551

552

553

554

555

556

557

558

560 }

562 }

563

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

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!");

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

795

796

797

798

799

800

802

803

804

805

806

807

808

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

858

859 case loc::ConcreteIntKind: {

861

862

863

865 if (op == BO_Cmp)

867

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

870

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

873 }

874

875

878

879 if (std::optional ResultInt =

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

883 }

884

885

886

887

888

889 assert((isa<loc::MemRegionVal, loc::GotoLabel>(rhs)));

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

908 }

909 case loc::MemRegionValKind: {

911

912

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

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

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

931 }

932 }

933

934

936 }

937

938

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

941

943 if (!RightMR)

944

945

946

948

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

954

955

956

957

958 if (LeftMS != RightMS &&

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

960 (isa(LeftMS) || isa(RightMS)))) {

961 switch (op) {

962 default:

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

982 ((!isa(LeftBase) && !isa(RightBase)) ||

983 (isa(LeftMS) || isa(RightMS))) ){

984 switch (op) {

985 default:

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

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

1008 if (!LeftIndex)

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

1011 LeftIndex = LeftIndexVal.getAs<NonLoc>();

1012 if (!LeftIndex)

1014

1015

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

1018 if (!RightIndex)

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

1021 RightIndex = RightIndexVal.getAs<NonLoc>();

1022 if (!RightIndex)

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

1044

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

1050

1051 switch (op) {

1052 default:

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

1078 }

1079 }

1080}

1081

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

1087 if (PTMSV->isNullMemberPointer())

1089

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

1091 SVal Result = lhs;

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<FieldDecl>()) {

1101 return getFieldLValue(FD);

1102 }

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

1116 return lhs;

1117

1118

1120 return lhs;

1121

1122

1123

1124

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

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

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

1130 assert(leftI.isUnsigned());

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

1132

1133

1134

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

1136

1137

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

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

1141 rightI *= Multiplicand;

1142

1143

1144 switch (op) {

1145 case BO_Add:

1146 rightI = leftI + rightI;

1147 break;

1148 case BO_Sub:

1149 rightI = leftI - rightI;

1150 break;

1151 default:

1152 llvm_unreachable("Invalid pointer arithmetic operation");

1153 }

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

1155 }

1156 }

1157

1158

1160 rhs = convertToArrayIndex(rhs).castAs<NonLoc>();

1162 const SubRegion *superR = nullptr;

1163

1164

1166

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

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

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

1170 getArrayIndexType());

1171 superR = cast(elemReg->getSuperRegion());

1172 elementType = elemReg->getElementType();

1173 }

1174 else if (isa(region)) {

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

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

1177 superR = cast(region);

1178

1179

1180

1181

1184 }

1185

1186

1187

1188

1190 elementType = getContext().CharTy;

1191

1192 if (std::optional indexV = index.getAs<NonLoc>()) {

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

1194 superR, getContext()));

1195 }

1196 }

1198}

1199

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

1203 return Res;

1204

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

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

1207

1208 return nullptr;

1209}

1210

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

1212 if (std::optionalloc::ConcreteInt X = V.getAs<loc::ConcreteInt>())

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

1214

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

1217

1218 return nullptr;

1219}

1220

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

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

1224}

1225

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

1228 V = simplifySVal(state, V);

1229

1231 return Res;

1232

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

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

1235

1236 return nullptr;

1237}

1238

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

1241 V = simplifySVal(state, V);

1242

1244 return Res;

1245

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

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

1248

1249 return nullptr;

1250}

1251

1253 SVal SimplifiedVal = simplifySValOnce(State, Val);

1254 while (SimplifiedVal != Val) {

1255 Val = SimplifiedVal;

1256 SimplifiedVal = simplifySValOnce(State, Val);

1257 }

1258 return SimplifiedVal;

1259}

1260

1262 return simplifyUntilFixpoint(State, V);

1263}

1264

1266

1267

1268

1269

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

1273

1274

1275

1276

1277

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

1279

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

1282 }

1283

1285 Cached[Sym] = V;

1286 return V;

1287 }

1288

1291 }

1292

1293

1294

1296 const llvm::APSInt *Const =

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

1298 if (Const)

1302 }

1303

1305 const SVal Ret = getConst(Sym);

1306 if (Ret.isUndef())

1307 return Visit(Sym);

1308 return Ret;

1309 }

1310

1311 public:

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

1314

1316

1317 if (const llvm::APSInt *I =

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

1322 }

1323

1325 auto I = Cached.find(S);

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

1327 return I->second;

1328

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

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

1331 return skip(S);

1332

1334

1335

1336

1337

1340

1341

1342

1346 }

1348 } else {

1350 }

1351

1352 return cache(

1353 S, SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType()));

1354 }

1355

1357 auto I = Cached.find(S);

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

1359 return I->second;

1360

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

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

1363 return skip(S);

1364

1366 return cache(

1367 S, SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType()));

1368 }

1369

1371 auto I = Cached.find(S);

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

1373 return I->second;

1374

1375

1376

1377

1378

1381 return skip(S);

1382

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

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

1385

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

1387 return skip(S);

1388

1389 return cache(

1390 S, SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType()));

1391 }

1392

1394 auto I = Cached.find(S);

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

1396 return I->second;

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

1398 SVal OpVal = getConstOrVisit(OpSym);

1399 if (isUnchanged(OpSym, OpVal))

1400 return skip(S);

1401

1402 return cache(S, SVB.evalCast(OpVal, S->getType(), OpSym->getType()));

1403 }

1404

1406 auto I = Cached.find(S);

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

1408 return I->second;

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

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

1411 return skip(S);

1412

1413 return cache(

1414 S, SVB.evalUnaryOp(State, S->getOpcode(), Op, S->getType()));

1415 }

1416

1418

1420

1422

1423

1424 return Visit(V.getSymbol());

1425 }

1426

1428 };

1429

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

1431 return SimplifiedV;

1432}

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

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

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

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

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

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

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

static bool isWithinConstantOverflowBounds(SymbolRef Sym, ProgramStateRef State)

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

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

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.

bool isComparisonOp() const

static Opcode negateComparisonOp(Opcode Opc)

static Opcode reverseComparisonOp(Opcode Opc)

bool isAdditiveOp() const

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.

Represents a field injected from an anonymous union/struct into the parent scope.

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.

Template implementation for all binary symbolic expressions.

ElementRegion is used to represent both array elements and casts.

QualType getElementType() const

LLVM_ATTRIBUTE_RETURNS_NONNULL const FieldDecl * getDecl() const override

FullSValVisitor - a convenient mixed visitor for all three: SVal, SymExpr and MemRegion subclasses.

static bool isLocType(QualType T)

RetTy VisitMemRegion(const MemRegion *R)

MemRegion - The root abstract class for all memory regions.

LLVM_ATTRIBUTE_RETURNS_NONNULL const MemSpaceRegion * getMemorySpace() const

RegionOffset getAsOffset() const

Compute the offset within the top level memory object.

LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getBaseRegion() const

MemSpaceRegion - A memory region that represents a "memory space"; for example, the set of global var...

SValBuilder & getSValBuilder()

Represent a region's offset within the top level base region.

bool hasSymbolicOffset() const

const MemRegion * getRegion() const

It might return null.

int64_t getOffset() const

virtual const llvm::APSInt * getKnownValue(ProgramStateRef state, SVal val)=0

Evaluates a given SVal.

BasicValueFactory & getBasicValueFactory()

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

Create a new value which represents a binary expression with a memory location and non-location opera...

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

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

nonloc::ConcreteInt makeIntVal(const IntegerLiteral *integer)

loc::MemRegionVal makeLoc(SymbolRef sym)

virtual const llvm::APSInt * getMinValue(ProgramStateRef state, SVal val)=0

Tries to get the minimal possible (integer) value of a given SVal.

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

virtual SVal simplifySVal(ProgramStateRef State, SVal Val)=0

Simplify symbolic expressions within a given SVal.

QualType getConditionType() const

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

virtual const llvm::APSInt * getMaxValue(ProgramStateRef state, SVal val)=0

Tries to get the maximal possible (integer) value of a given SVal.

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.

SubRegion - A region that subsets another larger region.

LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getSuperRegion() const

RetTy VisitSymExpr(SymbolRef S)

virtual QualType getType() const =0

Represents a cast expression.

A symbol representing data which can be stored in a memory location (region).

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

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

Represents a symbolic expression involving a unary operator.

Value representing integer constant.

Value representing pointer-to-member.

const PTMDataType getPTMData() const

Represents symbolic expression that isn't a location.

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

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.

const FunctionProtoType * T