DataflowEnvironment.cpp Source File (original) (raw)

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

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

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

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

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

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

31#include

32#include

33#include

35#define DEBUG_TYPE "dataflow"

38namespace dataflow {

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

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

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

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

51 for (auto &Entry : DeclToLoc1) {

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

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

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

55 }

57}

64template

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

68 for (const auto &Entry : Map2) {

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

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

73 }

76}

85 switch (K) {

88 return true;

89 default:

90 return false;

91 }

92}

100

101

102

103

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

106 return true;

108 return false;

111 }

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

113}

114

115

116

117

118

124

125

127

128

129

130

131

132

133

134

135

136

137

138

139

142 auto &A = JoinedEnv.arena();

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

146 A.makeEquals(JoinedVal, Expr1)),

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

149 return &A.makeBoolValue(JoinedVal);

150 }

151

153 if (JoinedVal)

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

155

156 return JoinedVal;

157}

158

163

165

166

167

170

172

173

175

176

177

178

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

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

181 if (TruePrev && TrueCur)

183 if (!TruePrev && !TrueCur &&

187

189 }

190

191

192

193

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

196

200}

201

202

203

204template

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

210 for (auto &Entry : Map1) {

211 Key K = Entry.first;

212 assert(K != nullptr);

213

214 Value *Val = Entry.second;

215 assert(Val != nullptr);

216

217 auto It = Map2.find(K);

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

219 continue;

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

221

224 Model))

225 return false;

226 }

227

228 return true;

229}

230

231

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

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

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

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

238 for (auto &Entry : LocToVal) {

240 assert(Loc != nullptr);

241

242 Value *Val = Entry.second;

243 assert(Val != nullptr);

244

245 auto It = LocToVal2.find(Loc);

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

247 continue;

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

249

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

252 Result.insert({Loc, JoinedVal});

253 }

254 }

255

257}

258

259

260

261template

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

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

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

268 for (auto &Entry : CurMap) {

269 Key K = Entry.first;

270 assert(K != nullptr);

271

272 Value *Val = Entry.second;

273 assert(Val != nullptr);

274

275 auto PrevIt = PrevMap.find(K);

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

277 continue;

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

279

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

282 continue;

283 }

284

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

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

290 }

291

292 return WidenedMap;

293}

294

295namespace {

296

297

298

299

300class ResultObjectVisitor : public AnalysisASTVisitor {

301public:

302

303

304

305

306 explicit ResultObjectVisitor(

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

308 RecordStorageLocation *LocForRecordReturnVal,

309 DataflowAnalysisContext &DACtx)

310 : ResultObjectMap(ResultObjectMap),

311 LocForRecordReturnVal(LocForRecordReturnVal), DACtx(DACtx) {}

312

313

314

315

316

317 void traverseConstructorInits(const CXXConstructorDecl *Ctor,

318 RecordStorageLocation *ThisPointeeLoc) {

319 assert(ThisPointeeLoc != nullptr);

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

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

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

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

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

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

327 PropagateResultObject(InitExpr, ThisPointeeLoc);

328 }

329

330

331

332 TraverseStmt(InitExpr);

333

334

335

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

337 TraverseStmt(DefaultInit->getExpr());

338 }

339 }

340

341 bool VisitVarDecl(VarDecl *VD) override {

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

343 PropagateResultObject(

344 VD->getInit(),

346 return true;

347 }

348

349 bool VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE) override {

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

351 PropagateResultObject(

352 MTE->getSubExpr(),

354 return true;

355 }

356

357 bool VisitReturnStmt(ReturnStmt *Return) override {

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

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

361 PropagateResultObject(RetValue, LocForRecordReturnVal);

362 return true;

363 }

364

365 bool VisitExpr(Expr *E) override {

366

367

368

369

370

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

372 !ResultObjectMap.contains(E))

373 PropagateResultObject(

375 return true;

376 }

377

378 void

379 PropagateResultObjectToRecordInitList(const RecordInitListHelper &InitList,

380 RecordStorageLocation *Loc) {

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

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

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

384

385

386

387

388 PropagateResultObject(Init, Loc);

389 }

390

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

392

393

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

395 PropagateResultObject(

397 }

398 }

399

400

401

402

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

404 if (!E->isPRValue() || !E->getType()->isRecordType()) {

405 assert(false);

406

407

408 return;

409 }

410

411 ResultObjectMap[E] = Loc;

412

413

414

415

419

420

421

423 return;

424 }

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

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

427

428 return;

429 }

430

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

432 if (!InitList->isSemanticForm())

433 return;

434 if (InitList->isTransparent()) {

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

436 return;

437 }

438

439 PropagateResultObjectToRecordInitList(RecordInitListHelper(InitList),

440 Loc);

441 return;

442 }

443

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

445 PropagateResultObjectToRecordInitList(RecordInitListHelper(ParenInitList),

446 Loc);

447 return;

448 }

449

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

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

452 return;

453 }

454

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

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

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

458 return;

459 }

460

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

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

463 return;

464 }

465

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

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

468 return;

469 }

470

471

472

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

474 LLVM_DEBUG({

476 E->dump();

477 });

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

480 PropagateResultObject(cast(S), Loc);

481 }

482

483private:

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

485 RecordStorageLocation *LocForRecordReturnVal;

486 DataflowAnalysisContext &DACtx;

487};

488

489}

490

492 if (InitialTargetStmt == nullptr)

493 return;

494

495 if (InitialTargetFunc == nullptr) {

497 ResultObjectMap =

498 std::make_shared(buildResultObjectMap(

500 nullptr));

501 return;

502 }

503

505

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

507 assert(ParamDecl != nullptr);

509 }

510

511 if (InitialTargetFunc->getReturnType()->isRecordType())

514

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

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

517 assert(Parent != nullptr);

518

519 if (Parent->isLambda()) {

520 for (const auto &Capture : Parent->captures()) {

521 if (Capture.capturesVariable()) {

523 assert(VarDecl != nullptr);

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

526 if (auto *Ancestor = InitialTargetFunc->getNonClosureAncestor()) {

529 SurroundingMethodDecl->getFunctionObjectParameterType();

532 } else if (auto *FieldBeingInitialized =

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

534

540 } else {

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

542 }

543 }

544 }

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

546 QualType ThisPointeeType = MethodDecl->getFunctionObjectParameterType();

547 auto &ThisLoc =

550

551

552

555 }

556 }

557

558

559

560 ResultObjectMap =

561 std::make_shared(buildResultObjectMap(

563 LocForRecordReturnVal));

564}

565

566

567

568

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

570

571

572 DACtx->addModeledFields(Referenced.Fields);

573

576 continue;

577

578

579

580

581

582

584 }

585

588 continue;

591 }

592}

593

596 Copy.FlowConditionToken = DACtx->forkFlowCondition(FlowConditionToken);

598}

599

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

603}

604

607

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

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

611 Env.ThisPointeeLoc =

613

614

615 }

616 }

617

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

620

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

623

624 return Env;

625}

626

629

632

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

635

636 return Env;

637}

638

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

641

642

643

646

647 CallStack.push_back(FuncDecl);

648

650

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

652

653

654

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

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

657 const VarDecl *Param = *ParamIt;

659 }

660

661 ResultObjectMap = std::make_shared(

663 LocForRecordReturnVal));

664}

665

667

668

669

670

671

672

673

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

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

676

677 if (Call->isGLValue()) {

678 if (CalleeEnv.ReturnLoc != nullptr)

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

681 if (CalleeEnv.ReturnVal != nullptr)

683 }

684}

685

688

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

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

691}

692

695 assert(DACtx == Other.DACtx);

696

697 if (ReturnVal != Other.ReturnVal)

698 return false;

699

700 if (ReturnLoc != Other.ReturnLoc)

701 return false;

702

703 if (LocForRecordReturnVal != Other.LocForRecordReturnVal)

704 return false;

705

706 if (ThisPointeeLoc != Other.ThisPointeeLoc)

707 return false;

708

709 if (DeclToLoc != Other.DeclToLoc)

710 return false;

711

712 if (ExprToLoc != Other.ExprToLoc)

713 return false;

714

716 return false;

717

719 return false;

720

721 return true;

722}

723

726 assert(DACtx == PrevEnv.DACtx);

727 assert(ReturnVal == PrevEnv.ReturnVal);

728 assert(ReturnLoc == PrevEnv.ReturnLoc);

729 assert(LocForRecordReturnVal == PrevEnv.LocForRecordReturnVal);

730 assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);

731 assert(CallStack == PrevEnv.CallStack);

732 assert(ResultObjectMap == PrevEnv.ResultObjectMap);

733 assert(InitialTargetFunc == PrevEnv.InitialTargetFunc);

734 assert(InitialTargetStmt == PrevEnv.InitialTargetStmt);

735

737

738

739

740

741

742

743

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

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

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

747

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

749 Model, Effect);

750

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

752 Model, Effect);

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

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

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

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

758

759 return Effect;

760}

761

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

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

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

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

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

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

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

772

774

775 JoinedEnv.CallStack = EnvA.CallStack;

776 JoinedEnv.ResultObjectMap = EnvA.ResultObjectMap;

777 JoinedEnv.LocForRecordReturnVal = EnvA.LocForRecordReturnVal;

778 JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc;

779 JoinedEnv.InitialTargetFunc = EnvA.InitialTargetFunc;

780 JoinedEnv.InitialTargetStmt = EnvA.InitialTargetStmt;

781

784 JoinedEnv.ReturnVal = nullptr;

785 } else {

786 JoinedEnv.ReturnVal =

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

788 EnvB, JoinedEnv, Model);

789 }

790

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

792 JoinedEnv.ReturnLoc = EnvA.ReturnLoc;

793 else

794 JoinedEnv.ReturnLoc = nullptr;

795

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

797

798

799

801 EnvA.FlowConditionToken, EnvB.FlowConditionToken);

802

803 JoinedEnv.LocToVal =

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

805

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

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

809 }

810

811 return JoinedEnv;

812}

813

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

819

820

821

822

823 return nullptr;

824

826

827 return Val1;

828

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

830}

831

833 return DACtx->createStorageLocation(Type);

834}

835

837

838

839

840 return DACtx->getStableStorageLocation(D);

841}

842

844

845

846

847 return DACtx->getStableStorageLocation(E);

848}

849

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

852

853

854

855

858 DeclToLoc[&D] = &Loc;

859}

860

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

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

864 return nullptr;

865

867

868 return Loc;

869}

870

872

874

875

876

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

881 ExprToLoc[&CanonE] = &Loc;

882}

883

885

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

890}

891

895 assert(RecordPRValue.isPRValue());

896

897 assert(ResultObjectMap != nullptr);

899 assert(Loc != nullptr);

900

901

902 if (Loc == nullptr)

904 DACtx->getStableStorageLocation(RecordPRValue));

905 return *Loc;

906}

907

909 return DACtx->getOrCreateNullPointerValue(PointeeType);

910}

911

914 llvm::DenseSet Visited;

915 int CreatedValuesCount = 0;

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

919 << '\n';

920 }

921}

922

924

926 LocToVal[&Loc] = &Val;

927}

928

931

933

935 ExprToVal[&CanonE] = &Val;

936}

937

939

941 return LocToVal.lookup(&Loc);

942}

943

946 if (Loc == nullptr)

947 return nullptr;

949}

950

952

954

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

958 }

959

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

962 return nullptr;

963 return getValue(*It->second);

964}

965

967 llvm::DenseSet Visited;

968 int CreatedValuesCount = 0;

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

970 CreatedValuesCount);

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

973 << '\n';

974 }

975 return Val;

976}

977

978Value *Environment::createValueUnlessSelfReferential(

979 QualType Type, llvm::DenseSet &Visited, int Depth,

980 int &CreatedValuesCount) {

981 assert( Type .isNull());

984

985

988 return nullptr;

989

991 CreatedValuesCount++;

993 }

994

996

997

998

999 CreatedValuesCount++;

1001 }

1002

1003 if (Type->isPointerType()) {

1004 CreatedValuesCount++;

1005 QualType PointeeType = Type->getPointeeType();

1006 StorageLocation &PointeeLoc =

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

1008

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

1010 }

1011

1012 return nullptr;

1013}

1014

1016Environment::createLocAndMaybeValue(QualType Ty,

1017 llvm::DenseSet &Visited,

1018 int Depth, int &CreatedValuesCount) {

1019 if (!Visited.insert(Ty.getCanonicalType()).second)

1021 auto EraseVisited = llvm::make_scope_exit(

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

1023

1024 Ty = Ty.getNonReferenceType();

1025

1026 if (Ty->isRecordType()) {

1029 return Loc;

1030 }

1031

1033

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

1035 CreatedValuesCount))

1037

1038 return Loc;

1039}

1040

1042 QualType Type,

1043 llvm::DenseSet &Visited,

1044 int Depth,

1045 int &CreatedValuesCount) {

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

1047 if (FieldType->isRecordType()) {

1050 Visited, Depth + 1, CreatedValuesCount);

1051 } else {

1052 if (getValue(FieldLoc) != nullptr)

1053 return;

1054 if (!Visited.insert(FieldType.getCanonicalType()).second)

1055 return;

1056 if (Value *Val = createValueUnlessSelfReferential(

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

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

1060 }

1061 };

1062

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

1064 assert(Field != nullptr);

1065 QualType FieldType = Field->getType();

1066

1067 if (FieldType->isReferenceType()) {

1068 Loc.setChild(*Field,

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

1070 CreatedValuesCount));

1071 } else {

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

1073 assert(FieldLoc != nullptr);

1074 initField(FieldType, *FieldLoc);

1075 }

1076 }

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

1078

1079

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

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

1082 }

1083}

1084

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

1086 QualType Ty,

1087 const Expr *InitExpr) {

1088 if (Ty->isReferenceType()) {

1089

1090

1091

1092 if (InitExpr) {

1094 return *InitExprLoc;

1095 }

1096

1097

1098

1099

1100

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

1102 }

1103

1104 StorageLocation &Loc =

1106

1107 if (Ty->isRecordType()) {

1108 auto &RecordLoc = cast(Loc);

1109 if (!InitExpr)

1110 initializeFieldsWithValues(RecordLoc);

1111 } else {

1112 Value *Val = nullptr;

1113 if (InitExpr)

1114

1115

1116

1117

1118

1119

1120

1121

1122

1123

1124

1125

1126

1127 Val = getValue(*InitExpr);

1128 if (!Val)

1129 Val = createValue(Ty);

1130 if (Val)

1131 setValue(Loc, *Val);

1132 }

1133

1134 return Loc;

1135}

1136

1138 DACtx->addFlowConditionConstraint(FlowConditionToken, F);

1139}

1140

1142 return DACtx->flowConditionImplies(FlowConditionToken, F);

1143}

1144

1146 return DACtx->flowConditionAllows(FlowConditionToken, F);

1147}

1148

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

1151 if (LocForRecordReturnVal != nullptr)

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

1153 if (ThisPointeeLoc != nullptr)

1154 LocToName[ThisPointeeLoc] = "this";

1155

1156 OS << "DeclToLoc:\n";

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

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

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

1160 }

1161 OS << "ExprToLoc:\n";

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

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

1164

1165 OS << "ExprToVal:\n";

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

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

1168

1169 OS << "LocToVal:\n";

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

1171 OS << " [" << L;

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

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

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

1175 }

1176

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

1179 OS << "ReturnLoc: " << ReturnLoc;

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

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

1182 OS << "\n";

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

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

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

1187 if (ReturnVal == nullptr)

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

1189 else

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

1191 }

1192

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

1195 }

1196 }

1197

1198 OS << "\n";

1199 DACtx->dumpFlowCondition(FlowConditionToken, OS);

1200}

1201

1203

1204Environment::PrValueToResultObject Environment::buildResultObjectMap(

1209

1210 PrValueToResultObject Map = buildResultObjectMap(

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

1212

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

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

1215 Visitor.traverseConstructorInits(Ctor, ThisPointeeLoc);

1216

1217 return Map;

1218}

1219

1220Environment::PrValueToResultObject Environment::buildResultObjectMap(

1221 DataflowAnalysisContext *DACtx, Stmt *S,

1222 RecordStorageLocation *ThisPointeeLoc,

1223 RecordStorageLocation *LocForRecordReturnVal) {

1224 PrValueToResultObject Map;

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

1226 Visitor.TraverseStmt(S);

1227 return Map;

1228}

1229

1233 if (ImplicitObject == nullptr)

1234 return nullptr;

1238 return nullptr;

1239 }

1240 return cast_or_null(

1242}

1243

1247 if (Base == nullptr)

1248 return nullptr;

1252 return nullptr;

1253 }

1255}

1256

1257}

1258}

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 IsVolatile, bool IsActive, bool IsUnionField, bool InUnion, const Descriptor *D, unsigned FieldOffset)

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

SmallVector< AnnotatedLine *, 1 > Children

If this token starts a block, this contains all the unwrapped lines in it.

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

C Language Family Type Representation.

Represents a member of a struct/union/class.

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

CanQualType getCanonicalTagType(const TagDecl *TD) const

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

DeclContext * getParent()

getParent - Returns the containing DeclContext.

ASTContext & getASTContext() const LLVM_READONLY

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

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.

Represents a struct/union/class.

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 isSpecificBuiltinType(unsigned K) const

Test for a particular builtin type.

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

Supplements Environment with non-standard comparison and join operations.

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.

Definition DataflowEnvironment.cpp:1145

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

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

Definition DataflowEnvironment.cpp:724

PointerValue & getOrCreateNullPointerValue(QualType PointeeType)

Returns a pointer value that represents a null pointer.

Definition DataflowEnvironment.cpp:908

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.

Definition DataflowEnvironment.cpp:605

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

Definition DataflowEnvironment.cpp:861

LLVM_DUMP_METHOD void dump() const

Definition DataflowEnvironment.cpp:1202

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

Definition DataflowEnvironment.cpp:912

StorageLocation & createStorageLocation(QualType Type)

Creates a storage location appropriate for Type.

Definition DataflowEnvironment.cpp:832

Environment fork() const

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

Definition DataflowEnvironment.cpp:594

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

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

Definition DataflowEnvironment.cpp:666

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:

Definition DataflowEnvironment.cpp:693

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.

Definition DataflowEnvironment.cpp:1141

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

Definition DataflowEnvironment.cpp:938

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.

Definition DataflowEnvironment.cpp:1137

Environment(DataflowAnalysisContext &DACtx, Atom FlowConditionToken)

Creates an environment that uses DACtx to store objects that encompass the state of a program.

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.

Definition DataflowEnvironment.cpp:814

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

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

Definition DataflowEnvironment.cpp:850

void removeDecl(const ValueDecl &D)

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

Definition DataflowEnvironment.cpp:871

RecordStorageLocation & getResultObjectLocation(const Expr &RecordPRValue) const

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

Definition DataflowEnvironment.cpp:893

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

Definition DataflowEnvironment.cpp:762

Value * createValue(QualType Type)

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

Definition DataflowEnvironment.cpp:966

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

Assigns Val as the value of Loc in the environment.

Definition DataflowEnvironment.cpp:923

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.

Definition DataflowEnvironment.cpp:600

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

Definition DataflowEnvironment.cpp:491

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)

Definition DataflowEnvironment.cpp:205

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.

Definition DataflowEnvironment.cpp:47

static bool equateUnknownValues(Value::Kind K)

Definition DataflowEnvironment.cpp:84

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)

Definition DataflowEnvironment.cpp:263

static constexpr int MaxCompositeValueDepth

Definition DataflowEnvironment.cpp:43

static constexpr int MaxCompositeValueSize

Definition DataflowEnvironment.cpp:44

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

Definition DataflowEnvironment.cpp:1230

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

Definition DataflowEnvironment.cpp:159

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)

Definition DataflowEnvironment.cpp:233

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

Definition DataflowEnvironment.cpp:65

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

Definition DataflowEnvironment.cpp:94

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

Definition DataflowEnvironment.cpp:1244

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.

Definition DataflowEnvironment.cpp:119

LatticeEffect

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

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

CanQual< Type > CanQualType

Represents a canonical, potentially-qualified type.

bool isa(CodeGen::Address addr)

nullptr

This class represents a compute construct, representing a 'Kind' of ‘parallel’, 'serial',...

@ Result

The result type of a method or function.

const FunctionProtoType * T

@ Type

The name was classified as a type.

U cast(CodeGen::Address addr)

@ Other

Other implicit parameter.

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

llvm::SetVector< const VarDecl * > Globals

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

FieldSet Fields

Non-static member variables.

llvm::SetVector< const FunctionDecl * > Functions

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

The result of a widen operation.