DataflowEnvironment.cpp Source File (original) (raw)

26#include "llvm/ADT/DenseMap.h"

27#include "llvm/ADT/DenseSet.h"

28#include "llvm/ADT/MapVector.h"

29#include "llvm/ADT/PointerUnion.h"

30#include "llvm/ADT/STLExtras.h"

31#include "llvm/ADT/ScopeExit.h"

32#include "llvm/Support/ErrorHandling.h"

33#include

34#include

35#include

36#include

38#define DEBUG_TYPE "dataflow"

41namespace dataflow {

50static llvm::DenseMap<const ValueDecl *, StorageLocation *> intersectDeclToLoc(

51 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc1,

52 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc2) {

53 llvm::DenseMap<const ValueDecl *, StorageLocation *> Result;

54 for (auto &Entry : DeclToLoc1) {

55 auto It = DeclToLoc2.find(Entry.first);

56 if (It != DeclToLoc2.end() && Entry.second == It->second)

57 Result.insert({Entry.first, Entry.second});

58 }

60}

67template

68static MapT joinExprMaps(const MapT &Map1, const MapT &Map2) {

71 for (const auto &Entry : Map2) {

72 [[maybe_unused]] auto [It, Inserted] = Result.insert(Entry);

75 assert(It->second == Entry.second);

76 }

79}

88 switch (K) {

91 return true;

92 default:

93 return false;

94 }

95}

101

102

103

104

105

106

107 switch (Model.compare(Type, Val1, Env1, Val2, Env2)) {

109 return true;

111 return false;

114 }

115 llvm_unreachable("All cases covered in switch");

116}

117

118

119

120

121

127

128

129 if (isa(&Val1) && isa(&Val2)) {

130

131

132

133

134

135

136

137

138

139

140

141

142

143 auto &Expr1 = cast(Val1).formula();

144 auto &Expr2 = cast(Val2).formula();

145 auto &A = JoinedEnv.arena();

146 auto &JoinedVal = A.makeAtomRef(A.makeAtom());

149 A.makeEquals(JoinedVal, Expr1)),

151 A.makeEquals(JoinedVal, Expr2))));

152 return &A.makeBoolValue(JoinedVal);

153 }

154

156 if (JoinedVal)

157 Model.join(Type, Val1, Env1, Val2, Env2, *JoinedVal, JoinedEnv);

158

159 return JoinedVal;

160}

161

166

167 if (isa(Prev) && isa(Current)) {

168

169

170

171 auto &PrevBool = cast(Prev);

172 auto &CurBool = cast(Current);

173

174 if (isa(Prev))

175

176

178

179

180

181

182 bool TruePrev = PrevEnv.proves(PrevBool.formula());

183 bool TrueCur = CurrentEnv.proves(CurBool.formula());

184 if (TruePrev && TrueCur)

186 if (!TruePrev && !TrueCur &&

190

192 }

193

194

195

196

197 if (auto Result = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv))

199

203}

204

205

206

207template

209 const llvm::MapVector<Key, Value *> &Map2,

213 for (auto &Entry : Map1) {

214 Key K = Entry.first;

215 assert(K != nullptr);

216

217 Value *Val = Entry.second;

218 assert(Val != nullptr);

219

220 auto It = Map2.find(K);

221 if (It == Map2.end())

222 continue;

223 assert(It->second != nullptr);

224

227 Model))

228 return false;

229 }

230

231 return true;

232}

233

234

235static llvm::MapVector<const StorageLocation *, Value *>

236 joinLocToVal(const llvm::MapVector<const StorageLocation *, Value *> &LocToVal,

237 const llvm::MapVector<const StorageLocation *, Value *> &LocToVal2,

240 llvm::MapVector<const StorageLocation *, Value *> Result;

241 for (auto &Entry : LocToVal) {

243 assert(Loc != nullptr);

244

245 Value *Val = Entry.second;

246 assert(Val != nullptr);

247

248 auto It = LocToVal2.find(Loc);

249 if (It == LocToVal2.end())

250 continue;

251 assert(It->second != nullptr);

252

254 Loc->getType(), Val, Env1, It->second, Env2, JoinedEnv, Model)) {

256 }

257 }

258

260}

261

262

263

264template

265static llvm::MapVector<Key, Value *>

267 const llvm::MapVector<Key, Value *> &PrevMap,

270 llvm::MapVector<Key, Value *> WidenedMap;

271 for (auto &Entry : CurMap) {

272 Key K = Entry.first;

273 assert(K != nullptr);

274

275 Value *Val = Entry.second;

276 assert(Val != nullptr);

277

278 auto PrevIt = PrevMap.find(K);

279 if (PrevIt == PrevMap.end())

280 continue;

281 assert(PrevIt->second != nullptr);

282

284 WidenedMap.insert({K, Val});

285 continue;

286 }

287

289 K->getType(), *PrevIt->second, PrevEnv, *Val, CurEnv, Model);

290 WidenedMap.insert({K, WidenedVal});

293 }

294

295 return WidenedMap;

296}

297

298namespace {

299

300

301

302

303class ResultObjectVisitor : public AnalysisASTVisitor {

304public:

305

306

307

308

309 explicit ResultObjectVisitor(

310 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap,

311 RecordStorageLocation *LocForRecordReturnVal,

312 DataflowAnalysisContext &DACtx)

313 : ResultObjectMap(ResultObjectMap),

314 LocForRecordReturnVal(LocForRecordReturnVal), DACtx(DACtx) {}

315

316

317

318

319

320 void traverseConstructorInits(const CXXConstructorDecl *Ctor,

321 RecordStorageLocation *ThisPointeeLoc) {

322 assert(ThisPointeeLoc != nullptr);

323 for (const CXXCtorInitializer *Init : Ctor->inits()) {

324 Expr *InitExpr = Init->getInit();

325 if (FieldDecl *Field = Init->getMember();

326 Field != nullptr && Field->getType()->isRecordType()) {

327 PropagateResultObject(InitExpr, cast(

328 ThisPointeeLoc->getChild(*Field)));

329 } else if (Init->getBaseClass()) {

330 PropagateResultObject(InitExpr, ThisPointeeLoc);

331 }

332

333

334

335 TraverseStmt(InitExpr);

336

337

338

339 if (auto *DefaultInit = dyn_cast(InitExpr))

340 TraverseStmt(DefaultInit->getExpr());

341 }

342 }

343

344 bool VisitVarDecl(VarDecl *VD) override {

345 if (VD->getType()->isRecordType() && VD->hasInit())

346 PropagateResultObject(

347 VD->getInit(),

348 &cast(DACtx.getStableStorageLocation(*VD)));

349 return true;

350 }

351

352 bool VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE) override {

353 if (MTE->getType()->isRecordType())

354 PropagateResultObject(

355 MTE->getSubExpr(),

356 &cast(DACtx.getStableStorageLocation(*MTE)));

357 return true;

358 }

359

360 bool VisitReturnStmt(ReturnStmt *Return) override {

361 Expr *RetValue = Return->getRetValue();

362 if (RetValue != nullptr && RetValue->getType()->isRecordType() &&

364 PropagateResultObject(RetValue, LocForRecordReturnVal);

365 return true;

366 }

367

368 bool VisitExpr(Expr *E) override {

369

370

371

372

373

374 if (E->isPRValue() && E->getType()->isRecordType() &&

375 !ResultObjectMap.contains(E))

376 PropagateResultObject(

377 E, &cast(DACtx.getStableStorageLocation(*E)));

378 return true;

379 }

380

381 void

382 PropagateResultObjectToRecordInitList(const RecordInitListHelper &InitList,

383 RecordStorageLocation *Loc) {

384 for (auto [Base, Init] : InitList.base_inits()) {

385 assert(Base->getType().getCanonicalType() ==

386 Init->getType().getCanonicalType());

387

388

389

390

391 PropagateResultObject(Init, Loc);

392 }

393

394 for (auto [Field, Init] : InitList.field_inits()) {

395

396

397 if (Field->getType()->isRecordType())

398 PropagateResultObject(

399 Init, cast(Loc->getChild(*Field)));

400 }

401 }

402

403

404

405

406 void PropagateResultObject(Expr *E, RecordStorageLocation *Loc) {

407 if (->isPRValue() || ->getType()->isRecordType()) {

408 assert(false);

409

410

411 return;

412 }

413

414 ResultObjectMap[E] = Loc;

415

416

417

418

419 if (isa(E) || isa(E) || isa(E) ||

420 isa(E) || isa(E) ||

421 isa(E) || isa(E) ||

422

423

424

425 isa(E)) {

426 return;

427 }

428 if (auto *Op = dyn_cast(E);

429 Op && Op->getOpcode() == BO_Cmp) {

430

431 return;

432 }

433

434 if (auto *InitList = dyn_cast(E)) {

435 if (!InitList->isSemanticForm())

436 return;

437 if (InitList->isTransparent()) {

438 PropagateResultObject(InitList->getInit(0), Loc);

439 return;

440 }

441

442 PropagateResultObjectToRecordInitList(RecordInitListHelper(InitList),

444 return;

445 }

446

447 if (auto *ParenInitList = dyn_cast(E)) {

448 PropagateResultObjectToRecordInitList(RecordInitListHelper(ParenInitList),

450 return;

451 }

452

453 if (auto *Op = dyn_cast(E); Op && Op->isCommaOp()) {

454 PropagateResultObject(Op->getRHS(), Loc);

455 return;

456 }

457

458 if (auto *Cond = dyn_cast(E)) {

459 PropagateResultObject(Cond->getTrueExpr(), Loc);

460 PropagateResultObject(Cond->getFalseExpr(), Loc);

461 return;

462 }

463

464 if (auto *SE = dyn_cast(E)) {

465 PropagateResultObject(cast(SE->getSubStmt()->body_back()), Loc);

466 return;

467 }

468

469 if (auto *DIE = dyn_cast(E)) {

470 PropagateResultObject(DIE->getExpr(), Loc);

471 return;

472 }

473

474

475

476 SmallVector<Stmt *, 1> Children(E->child_begin(), E->child_end());

477 LLVM_DEBUG({

478 if (Children.size() != 1)

479 E->dump();

480 });

481 assert(Children.size() == 1);

482 for (Stmt *S : Children)

483 PropagateResultObject(cast(S), Loc);

484 }

485

486private:

487 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap;

488 RecordStorageLocation *LocForRecordReturnVal;

489 DataflowAnalysisContext &DACtx;

490};

491

492}

493

495 if (InitialTargetStmt == nullptr)

496 return;

497

498 if (InitialTargetFunc == nullptr) {

500 ResultObjectMap =

501 std::make_shared(buildResultObjectMap(

503 nullptr));

504 return;

505 }

506

508

509 for (const auto *ParamDecl : InitialTargetFunc->parameters()) {

510 assert(ParamDecl != nullptr);

512 }

513

515 LocForRecordReturnVal = &cast(

517

518 if (const auto *MethodDecl = dyn_cast(InitialTargetFunc)) {

519 auto *Parent = MethodDecl->getParent();

520 assert(Parent != nullptr);

521

522 if (Parent->isLambda()) {

524 if (Capture.capturesVariable()) {

526 assert(VarDecl != nullptr);

528 } else if (Capture.capturesThis()) {

530 const auto *SurroundingMethodDecl = cast(Ancestor);

532 SurroundingMethodDecl->getFunctionObjectParameterType();

534 cast(createObject(ThisPointeeType)));

535 } else if (auto *FieldBeingInitialized =

536 dyn_cast(Parent->getLambdaContextDecl())) {

537

540 FieldBeingInitialized->getParent()->getTypeForDecl(), 0))));

541 } else {

542 assert(false && "Unexpected this-capturing lambda context.");

543 }

544 }

545 }

546 } else if (MethodDecl->isImplicitObjectMemberFunction()) {

547 QualType ThisPointeeType = MethodDecl->getFunctionObjectParameterType();

548 auto &ThisLoc =

551

552

553

554 if (!isa(MethodDecl))

556 }

557 }

558

559

560

561 ResultObjectMap =

562 std::make_shared(buildResultObjectMap(

564 LocForRecordReturnVal));

565}

566

567

568

569

570void Environment::initFieldsGlobalsAndFuncs(const ReferencedDecls &Referenced) {

571

572

573 DACtx->addModeledFields(Referenced.Fields);

574

577 continue;

578

579

580

581

582

583

585 }

586

589 continue;

592 }

593}

594

599}

600

603 return CallStack.size() < MaxDepth && !llvm::is_contained(CallStack, Callee);

604}

605

608

609 if (const auto *MethodCall = dyn_cast(Call)) {

610 if (const Expr *Arg = MethodCall->getImplicitObjectArgument()) {

611 if (!isa(Arg))

612 Env.ThisPointeeLoc =

614

615

616 }

617 }

618

619 if (Call->getType()->isRecordType() && Call->isPRValue())

620 Env.LocForRecordReturnVal = &Env.getResultObjectLocation(*Call);

621

622 Env.pushCallInternal(Call->getDirectCallee(),

624

625 return Env;

626}

627

630

631 Env.ThisPointeeLoc = &Env.getResultObjectLocation(*Call);

632 Env.LocForRecordReturnVal = &Env.getResultObjectLocation(*Call);

633

634 Env.pushCallInternal(Call->getConstructor(),

636

637 return Env;

638}

639

640void Environment::pushCallInternal(const FunctionDecl *FuncDecl,

642

643

644

647

648 CallStack.push_back(FuncDecl);

649

651

652 const auto *ParamIt = FuncDecl->param_begin();

653

654

655

656 for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {

657 assert(ParamIt != FuncDecl->param_end());

658 const VarDecl *Param = *ParamIt;

660 }

661

662 ResultObjectMap = std::make_shared(

664 LocForRecordReturnVal));

665}

666

668

669

670

671

672

673

674

675 this->LocToVal = std::move(CalleeEnv.LocToVal);

676 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);

677

678 if (Call->isGLValue()) {

679 if (CalleeEnv.ReturnLoc != nullptr)

681 } else if ( Call ->getType()->isVoidType()) {

682 if (CalleeEnv.ReturnVal != nullptr)

684 }

685}

686

689

690 this->LocToVal = std::move(CalleeEnv.LocToVal);

691 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);

692}

693

696 assert(DACtx == Other.DACtx);

697

698 if (ReturnVal != Other.ReturnVal)

699 return false;

700

701 if (ReturnLoc != Other.ReturnLoc)

702 return false;

703

704 if (LocForRecordReturnVal != Other.LocForRecordReturnVal)

705 return false;

706

707 if (ThisPointeeLoc != Other.ThisPointeeLoc)

708 return false;

709

710 if (DeclToLoc != Other.DeclToLoc)

711 return false;

712

713 if (ExprToLoc != Other.ExprToLoc)

714 return false;

715

717 return false;

718

720 return false;

721

722 return true;

723}

724

727 assert(DACtx == PrevEnv.DACtx);

728 assert(ReturnVal == PrevEnv.ReturnVal);

729 assert(ReturnLoc == PrevEnv.ReturnLoc);

730 assert(LocForRecordReturnVal == PrevEnv.LocForRecordReturnVal);

731 assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);

732 assert(CallStack == PrevEnv.CallStack);

733 assert(ResultObjectMap == PrevEnv.ResultObjectMap);

734 assert(InitialTargetFunc == PrevEnv.InitialTargetFunc);

735 assert(InitialTargetStmt == PrevEnv.InitialTargetStmt);

736

738

739

740

741

742

743

744

745 assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());

746 assert(ExprToVal.size() <= PrevEnv.ExprToVal.size());

747 assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());

748

749 ExprToVal = widenKeyToValueMap(ExprToVal, PrevEnv.ExprToVal, *this, PrevEnv,

750 Model, Effect);

751

752 LocToVal = widenKeyToValueMap(LocToVal, PrevEnv.LocToVal, *this, PrevEnv,

753 Model, Effect);

754 if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||

755 ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||

756 ExprToVal.size() != PrevEnv.ExprToVal.size() ||

757 LocToVal.size() != PrevEnv.LocToVal.size())

759

760 return Effect;

761}

762

766 assert(EnvA.DACtx == EnvB.DACtx);

767 assert(EnvA.LocForRecordReturnVal == EnvB.LocForRecordReturnVal);

768 assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc);

769 assert(EnvA.CallStack == EnvB.CallStack);

770 assert(EnvA.ResultObjectMap == EnvB.ResultObjectMap);

771 assert(EnvA.InitialTargetFunc == EnvB.InitialTargetFunc);

772 assert(EnvA.InitialTargetStmt == EnvB.InitialTargetStmt);

773

775

776 JoinedEnv.CallStack = EnvA.CallStack;

777 JoinedEnv.ResultObjectMap = EnvA.ResultObjectMap;

778 JoinedEnv.LocForRecordReturnVal = EnvA.LocForRecordReturnVal;

779 JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc;

780 JoinedEnv.InitialTargetFunc = EnvA.InitialTargetFunc;

781 JoinedEnv.InitialTargetStmt = EnvA.InitialTargetStmt;

782

785 JoinedEnv.ReturnVal = nullptr;

786 } else {

787 JoinedEnv.ReturnVal =

788 joinValues(Func->getReturnType(), EnvA.ReturnVal, EnvA, EnvB.ReturnVal,

789 EnvB, JoinedEnv, Model);

790 }

791

792 if (EnvA.ReturnLoc == EnvB.ReturnLoc)

793 JoinedEnv.ReturnLoc = EnvA.ReturnLoc;

794 else

795 JoinedEnv.ReturnLoc = nullptr;

796

797 JoinedEnv.DeclToLoc = intersectDeclToLoc(EnvA.DeclToLoc, EnvB.DeclToLoc);

798

799

800

802 EnvA.FlowConditionToken, EnvB.FlowConditionToken);

803

804 JoinedEnv.LocToVal =

805 joinLocToVal(EnvA.LocToVal, EnvB.LocToVal, EnvA, EnvB, JoinedEnv, Model);

806

808 JoinedEnv.ExprToVal = joinExprMaps(EnvA.ExprToVal, EnvB.ExprToVal);

809 JoinedEnv.ExprToLoc = joinExprMaps(EnvA.ExprToLoc, EnvB.ExprToLoc);

810 }

811

812 return JoinedEnv;

813}

814

819 if (Val1 == nullptr || Val2 == nullptr)

820

821

822

823

824 return nullptr;

825

827

828 return Val1;

829

830 return joinDistinctValues(Ty, *Val1, Env1, *Val2, Env2, JoinedEnv, Model);

831}

832

835}

836

838

839

840

842}

843

845

846

847

849}

850

852 assert(!DeclToLoc.contains(&D));

853

854

855

856

857 assert(D.getType()->isReferenceType() || isa(D) ||

859 DeclToLoc[&D] = &Loc;

860}

861

863 auto It = DeclToLoc.find(&D);

864 if (It == DeclToLoc.end())

865 return nullptr;

866

868

869 return Loc;

870}

871

873

875

876

877

878 assert(E.isGLValue() ||

879 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));

881 assert(!ExprToLoc.contains(&CanonE));

882 ExprToLoc[&CanonE] = &Loc;

883}

884

886

887 assert(E.isGLValue() ||

888 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));

890 return It == ExprToLoc.end() ? nullptr : &*It->second;

891}

892

896 assert(RecordPRValue.isPRValue());

897

898 assert(ResultObjectMap != nullptr);

900 assert(Loc != nullptr);

901

902

903 if (Loc == nullptr)

904 return cast(

906 return *Loc;

907}

908

911}

912

915 llvm::DenseSet Visited;

916 int CreatedValuesCount = 0;

919 llvm::errs() << "Attempting to initialize a huge value of type: " << Type

920 << '\n';

921 }

922}

923

925

926 assert(!isa(Loc));

927 LocToVal[&Loc] = &Val;

928}

929

932

934

936 ExprToVal[&CanonE] = &Val;

937}

938

940

941 assert(!isa(Loc));

942 return LocToVal.lookup(&Loc);

943}

944

947 if (Loc == nullptr)

948 return nullptr;

950}

951

953

954 assert(.getType()->isRecordType());

955

956 if (E.isPRValue()) {

958 return It == ExprToVal.end() ? nullptr : It->second;

959 }

960

962 if (It == ExprToLoc.end())

963 return nullptr;

964 return getValue(*It->second);

965}

966

968 llvm::DenseSet Visited;

969 int CreatedValuesCount = 0;

970 Value *Val = createValueUnlessSelfReferential(Type, Visited, 0,

971 CreatedValuesCount);

973 llvm::errs() << "Attempting to initialize a huge value of type: " << Type

974 << '\n';

975 }

976 return Val;

977}

978

979Value *Environment::createValueUnlessSelfReferential(

981 int &CreatedValuesCount) {

982 assert( Type .isNull());

985

986

989 return nullptr;

990

992 CreatedValuesCount++;

994 }

995

997

998

999

1000 CreatedValuesCount++;

1002 }

1003

1004 if (Type->isPointerType()) {

1005 CreatedValuesCount++;

1006 QualType PointeeType = Type->getPointeeType();

1007 StorageLocation &PointeeLoc =

1008 createLocAndMaybeValue(PointeeType, Visited, Depth, CreatedValuesCount);

1009

1010 return &arena().create(PointeeLoc);

1011 }

1012

1013 return nullptr;

1014}

1015

1016StorageLocation &

1017Environment::createLocAndMaybeValue(QualType Ty,

1018 llvm::DenseSet &Visited,

1019 int Depth, int &CreatedValuesCount) {

1020 if ( Visited .insert(Ty.getCanonicalType()).second)

1022 auto EraseVisited = llvm::make_scope_exit(

1023 [&Visited, Ty] { Visited.erase(Ty.getCanonicalType()); });

1024

1025 Ty = Ty.getNonReferenceType();

1026

1027 if (Ty->isRecordType()) {

1030 return Loc;

1031 }

1032

1034

1035 if (Value *Val = createValueUnlessSelfReferential(Ty, Visited, Depth,

1036 CreatedValuesCount))

1038

1039 return Loc;

1040}

1041

1043 QualType Type,

1044 llvm::DenseSet &Visited,

1045 int Depth,

1046 int &CreatedValuesCount) {

1047 auto initField = [&](QualType FieldType, StorageLocation &FieldLoc) {

1048 if (FieldType->isRecordType()) {

1049 auto &FieldRecordLoc = cast(FieldLoc);

1051 Visited, Depth + 1, CreatedValuesCount);

1052 } else {

1053 if (getValue(FieldLoc) != nullptr)

1054 return;

1055 if ( Visited .insert(FieldType.getCanonicalType()).second)

1056 return;

1057 if (Value *Val = createValueUnlessSelfReferential(

1058 FieldType, Visited, Depth + 1, CreatedValuesCount))

1060 Visited.erase(FieldType.getCanonicalType());

1061 }

1062 };

1063

1064 for (const FieldDecl *Field : DACtx->getModeledFields(Type)) {

1065 assert(Field != nullptr);

1066 QualType FieldType = Field->getType();

1067

1068 if (FieldType->isReferenceType()) {

1069 Loc.setChild(*Field,

1070 &createLocAndMaybeValue(FieldType, Visited, Depth + 1,

1071 CreatedValuesCount));

1072 } else {

1073 StorageLocation *FieldLoc = Loc.getChild(*Field);

1074 assert(FieldLoc != nullptr);

1075 initField(FieldType, *FieldLoc);

1076 }

1077 }

1078 for (const auto &[FieldName, FieldType] : DACtx->getSyntheticFields(Type)) {

1079

1080

1081 assert(!FieldType->isReferenceType());

1082 initField(FieldType, Loc.getSyntheticField(FieldName));

1083 }

1084}

1085

1086StorageLocation &Environment::createObjectInternal(const ValueDecl *D,

1087 QualType Ty,

1088 const Expr *InitExpr) {

1089 if (Ty->isReferenceType()) {

1090

1091

1092

1093 if (InitExpr) {

1095 return *InitExprLoc;

1096 }

1097

1098

1099

1100

1101

1102 return createObjectInternal(D, Ty.getNonReferenceType(), nullptr);

1103 }

1104

1105 StorageLocation &Loc =

1107

1108 if (Ty->isRecordType()) {

1109 auto &RecordLoc = cast(Loc);

1110 if (!InitExpr)

1112 } else {

1113 Value *Val = nullptr;

1114 if (InitExpr)

1115

1116

1117

1118

1119

1120

1121

1122

1123

1124

1125

1126

1127

1129 if (!Val)

1131 if (Val)

1133 }

1134

1135 return Loc;

1136}

1137

1140}

1141

1144}

1145

1148}

1149

1151 llvm::DenseMap<const StorageLocation *, std::string> LocToName;

1152 if (LocForRecordReturnVal != nullptr)

1153 LocToName[LocForRecordReturnVal] = "(returned record)";

1154 if (ThisPointeeLoc != nullptr)

1155 LocToName[ThisPointeeLoc] = "this";

1156

1157 OS << "DeclToLoc:\n";

1158 for (auto [D, L] : DeclToLoc) {

1159 auto Iter = LocToName.insert({L, D->getNameAsString()}).first;

1160 OS << " [" << Iter->second << ", " << L << "]\n";

1161 }

1162 OS << "ExprToLoc:\n";

1163 for (auto [E, L] : ExprToLoc)

1164 OS << " [" << E << ", " << L << "]\n";

1165

1166 OS << "ExprToVal:\n";

1167 for (auto [E, V] : ExprToVal)

1168 OS << " [" << E << ", " << V << ": " << *V << "]\n";

1169

1170 OS << "LocToVal:\n";

1171 for (auto [L, V] : LocToVal) {

1172 OS << " [" << L;

1173 if (auto Iter = LocToName.find(L); Iter != LocToName.end())

1174 OS << " (" << Iter->second << ")";

1175 OS << ", " << V << ": " << *V << "]\n";

1176 }

1177

1179 if (Func->getReturnType()->isReferenceType()) {

1180 OS << "ReturnLoc: " << ReturnLoc;

1181 if (auto Iter = LocToName.find(ReturnLoc); Iter != LocToName.end())

1182 OS << " (" << Iter->second << ")";

1183 OS << "\n";

1184 } else if (Func->getReturnType()->isRecordType() ||

1185 isa(Func)) {

1186 OS << "LocForRecordReturnVal: " << LocForRecordReturnVal << "\n";

1187 } else if ( Func ->getReturnType()->isVoidType()) {

1188 if (ReturnVal == nullptr)

1189 OS << "ReturnVal: nullptr\n";

1190 else

1191 OS << "ReturnVal: " << *ReturnVal << "\n";

1192 }

1193

1194 if (isa(Func)) {

1195 OS << "ThisPointeeLoc: " << ThisPointeeLoc << "\n";

1196 }

1197 }

1198

1199 OS << "\n";

1201}

1202

1204

1205Environment::PrValueToResultObject Environment::buildResultObjectMap(

1210

1211 PrValueToResultObject Map = buildResultObjectMap(

1212 DACtx, FuncDecl->getBody(), ThisPointeeLoc, LocForRecordReturnVal);

1213

1214 ResultObjectVisitor Visitor(Map, LocForRecordReturnVal, *DACtx);

1215 if (const auto *Ctor = dyn_cast(FuncDecl))

1216 Visitor.traverseConstructorInits(Ctor, ThisPointeeLoc);

1217

1218 return Map;

1219}

1220

1221Environment::PrValueToResultObject Environment::buildResultObjectMap(

1222 DataflowAnalysisContext *DACtx, Stmt *S,

1223 RecordStorageLocation *ThisPointeeLoc,

1224 RecordStorageLocation *LocForRecordReturnVal) {

1225 PrValueToResultObject Map;

1226 ResultObjectVisitor Visitor(Map, LocForRecordReturnVal, *DACtx);

1227 Visitor.TraverseStmt(S);

1228 return Map;

1229}

1230

1234 if (ImplicitObject == nullptr)

1235 return nullptr;

1238 return &cast(Val->getPointeeLoc());

1239 return nullptr;

1240 }

1241 return cast_or_null(

1243}

1244

1248 if (Base == nullptr)

1249 return nullptr;

1252 return &cast(Val->getPointeeLoc());

1253 return nullptr;

1254 }

1256}

1257

1258}

1259}

Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....

static void initField(Block *B, std::byte *Ptr, bool IsConst, bool IsMutable, bool IsActive, bool IsUnionField, bool InUnion, const Descriptor *D, unsigned FieldOffset)

Defines the clang::Expr interface and subclasses for C++ expressions.

llvm::DenseSet< const void * > Visited

static bool RetValue(InterpState &S, CodePtr &Pt)

llvm::MachO::RecordLoc RecordLoc

C Language Family Type Representation.

Represents a call to a C++ constructor.

Represents a call to a member function that may be written either with member call syntax (e....

Expr * getImplicitObjectArgument() const

Retrieve the implicit object argument for the member call.

CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).

Decl * getNonClosureAncestor()

Find the nearest non-closure ancestor of this context, i.e.

This represents one expression.

Represents a function declaration or definition.

Stmt * getBody(const FunctionDecl *&Definition) const

Retrieve the body (definition) of the function.

param_iterator param_end()

QualType getReturnType() const

ArrayRef< ParmVarDecl * > parameters() const

param_iterator param_begin()

bool doesThisDeclarationHaveABody() const

Returns whether this specific declaration of the function has a body.

FunctionDecl * getDefinition()

Get the definition for this declaration.

MemberExpr - [C99 6.5.2.3] Structure and Union Members.

A (possibly-)qualified type.

Stmt - This represents one statement.

The base class of the type hierarchy.

bool isBooleanType() const

bool isPointerType() const

bool isIntegerType() const

isIntegerType() does not include complex integers (a GCC extension).

bool isReferenceType() const

bool isRecordType() const

Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...

Represents a variable declaration or definition.

const Formula & makeAtomRef(Atom A)

Returns a formula for the variable A.

const Formula & makeNot(const Formula &Val)

Returns a formula for the negation of Val.

std::enable_if_t< std::is_base_of< StorageLocation, T >::value, T & > create(Args &&...args)

Creates a T (some subclass of StorageLocation), forwarding args to the constructor,...

Owns objects that encompass the state of a program and stores context that is used during dataflow an...

Atom joinFlowConditions(Atom FirstToken, Atom SecondToken)

Creates a new flow condition that represents the disjunction of the flow conditions identified by Fir...

void addFlowConditionConstraint(Atom Token, const Formula &Constraint)

Adds Constraint to the flow condition identified by Token.

Atom forkFlowCondition(Atom Token)

Creates a new flow condition with the same constraints as the flow condition identified by Token and ...

StorageLocation & getStableStorageLocation(const ValueDecl &D)

Returns a stable storage location for D.

bool flowConditionImplies(Atom Token, const Formula &F)

Returns true if the constraints of the flow condition identified by Token imply that F is true.

bool flowConditionAllows(Atom Token, const Formula &F)

Returns true if the constraints of the flow condition identified by Token still allow F to be true.

PointerValue & getOrCreateNullPointerValue(QualType PointeeType)

Returns a pointer value that represents a null pointer.

llvm::StringMap< QualType > getSyntheticFields(QualType Type)

Returns the names and types of the synthetic fields for the given record type.

StorageLocation & createStorageLocation(QualType Type)

Returns a new storage location appropriate for Type.

FieldSet getModeledFields(QualType Type)

Returns the fields of Type, limited to the set of fields modeled by this context.

LLVM_DUMP_METHOD void dumpFlowCondition(Atom Token, llvm::raw_ostream &OS=llvm::dbgs())

Supplements Environment with non-standard comparison and join operations.

virtual std::optional< WidenResult > widen(QualType Type, Value &Prev, const Environment &PrevEnv, Value &Current, Environment &CurrentEnv)

This function may widen the current value – replace it with an approximation that can reach a fixed p...

virtual void join(QualType Type, const Value &Val1, const Environment &Env1, const Value &Val2, const Environment &Env2, Value &JoinedVal, Environment &JoinedEnv)

Modifies JoinedVal to approximate both Val1 and Val2.

virtual ComparisonResult compare(QualType Type, const Value &Val1, const Environment &Env1, const Value &Val2, const Environment &Env2)

Returns: Same: Val1 is equivalent to Val2, according to the model.

Holds the state of the program (store and heap) at a given program point.

bool allows(const Formula &) const

Returns true if the formula may be true when this point is reached.

LatticeEffect widen(const Environment &PrevEnv, Environment::ValueModel &Model)

Widens the environment point-wise, using PrevEnv as needed to inform the approximation.

PointerValue & getOrCreateNullPointerValue(QualType PointeeType)

Returns a pointer value that represents a null pointer.

RecordStorageLocation * getThisPointeeStorageLocation() const

Returns the storage location assigned to the this pointee in the environment or null if the this poin...

Environment pushCall(const CallExpr *Call) const

Creates and returns an environment to use for an inline analysis of the callee.

StorageLocation * getStorageLocation(const ValueDecl &D) const

Returns the storage location assigned to D in the environment, or null if D isn't assigned a storage ...

LLVM_DUMP_METHOD void dump() const

BoolValue & makeTopBoolValue() const

Returns a unique instance of boolean Top.

void initializeFieldsWithValues(RecordStorageLocation &Loc, QualType Type)

Initializes the fields (including synthetic fields) of Loc with values, unless values of the field ty...

StorageLocation & createStorageLocation(QualType Type)

Creates a storage location appropriate for Type.

Environment fork() const

Returns a new environment that is a copy of this one.

void popCall(const CallExpr *Call, const Environment &CalleeEnv)

Moves gathered information back into this from a CalleeEnv created via pushCall.

bool equivalentTo(const Environment &Other, Environment::ValueModel &Model) const

Returns true if and only if the environment is equivalent to Other, i.e the two environments:

BoolValue & makeAtomicBoolValue() const

Returns an atomic boolean value.

bool proves(const Formula &) const

Returns true if the formula is always true when this point is reached.

Value * getValue(const StorageLocation &Loc) const

Returns the value assigned to Loc in the environment or null if Loc isn't assigned a value in the env...

const FunctionDecl * getCurrentFunc() const

Returns the function currently being analyzed, or null if the code being analyzed isn't part of a fun...

BoolValue & getBoolLiteralValue(bool Value) const

Returns a symbolic boolean value that models a boolean literal equal to Value

StorageLocation & createObject(QualType Ty, const Expr *InitExpr=nullptr)

Creates an object (i.e.

void assume(const Formula &)

Record a fact that must be true if this point in the program is reached.

static Value * joinValues(QualType Ty, Value *Val1, const Environment &Env1, Value *Val2, const Environment &Env2, Environment &JoinedEnv, Environment::ValueModel &Model)

Returns a value that approximates both Val1 and Val2, or null if no such value can be produced.

void setStorageLocation(const ValueDecl &D, StorageLocation &Loc)

Assigns Loc as the storage location of D in the environment.

void removeDecl(const ValueDecl &D)

Removes the location assigned to D in the environment (if any).

RecordStorageLocation & getResultObjectLocation(const Expr &RecordPRValue) const

Returns the location of the result object for a record-type prvalue.

ExprJoinBehavior

How to treat expression state (ExprToLoc and ExprToVal) in a join.

static Environment join(const Environment &EnvA, const Environment &EnvB, Environment::ValueModel &Model, ExprJoinBehavior ExprBehavior)

Joins two environments by taking the intersection of storage locations and values that are stored in ...

Value * createValue(QualType Type)

Creates a value appropriate for Type, if Type is supported, otherwise returns null.

void setValue(const StorageLocation &Loc, Value &Val)

Assigns Val as the value of Loc in the environment.

void setThisPointeeStorageLocation(RecordStorageLocation &Loc)

Sets the storage location assigned to the this pointee in the environment.

Atom getFlowConditionToken() const

Returns a boolean variable that identifies the flow condition (FC).

bool canDescend(unsigned MaxDepth, const FunctionDecl *Callee) const

Returns whether this Environment can be extended to analyze the given Callee (i.e.

std::enable_if_t< std::is_base_of_v< StorageLocation, T >, T * > get(const ValueDecl &D) const

Returns the result of casting getStorageLocation(...) to a subclass of StorageLocation (using cast_or...

void initialize()

Assigns storage locations and values to all parameters, captures, global variables,...

Models a symbolic pointer. Specifically, any value of type T*.

A storage location for a record (struct, class, or union).

Base class for elements of the local variable store and of the heap.

Base class for all values computed by abstract interpretation.

static bool compareKeyToValueMaps(const llvm::MapVector< Key, Value * > &Map1, const llvm::MapVector< Key, Value * > &Map2, const Environment &Env1, const Environment &Env2, Environment::ValueModel &Model)

static llvm::DenseMap< const ValueDecl *, StorageLocation * > intersectDeclToLoc(const llvm::DenseMap< const ValueDecl *, StorageLocation * > &DeclToLoc1, const llvm::DenseMap< const ValueDecl *, StorageLocation * > &DeclToLoc2)

Returns a map consisting of key-value entries that are present in both maps.

static bool equateUnknownValues(Value::Kind K)

bool areEquivalentValues(const Value &Val1, const Value &Val2)

An equivalence relation for values.

static llvm::MapVector< Key, Value * > widenKeyToValueMap(const llvm::MapVector< Key, Value * > &CurMap, const llvm::MapVector< Key, Value * > &PrevMap, Environment &CurEnv, const Environment &PrevEnv, Environment::ValueModel &Model, LatticeEffect &Effect)

static constexpr int MaxCompositeValueDepth

static constexpr int MaxCompositeValueSize

ReferencedDecls getReferencedDecls(const FunctionDecl &FD)

Returns declarations that are declared in or referenced from FD.

RecordStorageLocation * getImplicitObjectLocation(const CXXMemberCallExpr &MCE, const Environment &Env)

Returns the storage location for the implicit object of a CXXMemberCallExpr, or null if none is defin...

static WidenResult widenDistinctValues(QualType Type, Value &Prev, const Environment &PrevEnv, Value &Current, Environment &CurrentEnv, Environment::ValueModel &Model)

const Expr & ignoreCFGOmittedNodes(const Expr &E)

Skip past nodes that the CFG does not emit.

static llvm::MapVector< const StorageLocation *, Value * > joinLocToVal(const llvm::MapVector< const StorageLocation *, Value * > &LocToVal, const llvm::MapVector< const StorageLocation *, Value * > &LocToVal2, const Environment &Env1, const Environment &Env2, Environment &JoinedEnv, Environment::ValueModel &Model)

static MapT joinExprMaps(const MapT &Map1, const MapT &Map2)

static bool compareDistinctValues(QualType Type, Value &Val1, const Environment &Env1, Value &Val2, const Environment &Env2, Environment::ValueModel &Model)

RecordStorageLocation * getBaseObjectLocation(const MemberExpr &ME, const Environment &Env)

Returns the storage location for the base object of a MemberExpr, or null if none is defined in the e...

static Value * joinDistinctValues(QualType Type, Value &Val1, const Environment &Env1, Value &Val2, const Environment &Env2, Environment &JoinedEnv, Environment::ValueModel &Model)

Attempts to join distinct values Val1 and Val2 in Env1 and Env2, respectively, of the same type Type.

LatticeEffect

Effect indicating whether a lattice operation resulted in a new value.

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

@ Result

The result type of a method or function.

@ Other

Other implicit parameter.

A collection of several types of declarations, all referenced from the same function.

llvm::DenseSet< const VarDecl * > Globals

All variables with static storage duration, notably including static member variables and static vari...

llvm::DenseSet< const FunctionDecl * > Functions

Free functions and member functions which are referenced (but not necessarily called).

FieldSet Fields

Non-static member variables.

The result of a widen operation.