DataflowEnvironment.h Source File (original) (raw)

15#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H

16#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H

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

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

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

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

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

34#include

35#include

36#include <type_traits>

37#include

38#include

66public:

70 public:

100

101

102

103

104

105

106

107

108

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

145

146

147 switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) {

149 return std::nullopt;

154 }

155 llvm_unreachable("all cases in switch covered");

156 }

157 };

158

159

160

161

162

163

164

166 : DACtx(&DACtx), FlowConditionToken(FlowConditionToken) {}

167

168

169

172

173

174

176 InitialTargetStmt = &S;

177 }

178

179

180

181

182

183

184

185

189 InitialTargetFunc = &FD;

190 }

191

192

194

197

198

199

200

201

202

204

205

206

207

208

209

210

211

212

214

215

216

217

218

219

220

221

222

223

224

225

228

229

230

233

234

235

236

237

238

239

240

241

242

243

246

247

248

249

254

255

256

257

258

259

260

261

265

266

267

268

269

270

271

272

273

274

275

280

281

282

283

284

285

286

287

290

291

292

293

294

295

296

297

298

299

301

302

303

304

306

307

308

309

311

312

313

314

315

316

318

319

320

322

323

325

326

327

328

329

330

331

332

334

335

336

337

338

339

340

342

343

344

345

346

347

348 template

349 std::enable_if_t<std::is_base_of_v<StorageLocation, T>, T *>

353 template

354 std::enable_if_t<std::is_base_of_v<StorageLocation, T>, T *>

358

359

360

361

363 return ThisPointeeLoc;

364 }

365

366

367

369 ThisPointeeLoc = &Loc;

370 }

371

372

373

374

375

376

377

378

379

380

381

382

383

386

387

388

389

390

391

392

393

394

395

398 getCurrentFunc ()->getReturnType()->isReferenceType());

399 return ReturnVal;

400 }

401

402

403

404

405

406

407

408

411 getCurrentFunc()->getReturnType()->isReferenceType());

412 return ReturnLoc;

413 }

414

415

416

417

418

419

422 getCurrentFunc ()->getReturnType()->isReferenceType());

423 ReturnVal = Val;

424 }

425

426

427

428

429

430

431

434 getCurrentFunc()->getReturnType()->isReferenceType());

435 ReturnLoc = Loc;

436 }

437

438

439

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

459

460

461

462

463

465 return createObjectInternal(nullptr, Ty, InitExpr);

466 }

467

468

469

470

471

472

476

477

478

479

480

481

483 return createObjectInternal(&D, D.getType(), InitExpr);

484 }

485

486

487

488

489

490

491

492

497

498

499

500

501

502

504

505

507

508

509

510

511

512

513

515

516

517

518

519

520

521

523

524

525

526

527

528

529

531

532

533

535

536

537

538

539

540

541 template

542 std::enable_if_t<std::is_base_of_v<Value, T>, T *>

544 return cast_or_null(getValue(Loc));

545 }

546 template

547 std::enable_if_t<std::is_base_of_v<Value, T>, T *>

549 return cast_or_null(getValue(D));

550 }

551 template

552 std::enable_if_t<std::is_base_of_v<Value, T>, T *> get(const Expr &E) const {

553 return cast_or_null(getValue(E));

554 }

555

556

557

558

559

560

561

562

563 template <typename T, typename... Args>

564 std::enable_if_t<std::is_base_of<Value, T>::value, T &>

566 return arena().create<T>(std::forward(args)...);

567 }

568

569

570

574

575

576

580

581

585

586

590

591

592

593

594

599

600

601

602

603

608

609

610

614

615

616

617

618

623

624

625

626

627

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

648

649

651

652

653

654

655

656

657

658

659

660

662

663

664

665

667

668

669

671 return CallStack.empty() ? InitialTargetFunc : CallStack.back();

672 }

673

674

675

677

678

679

680

681

683

684

686

688

689 LLVM_DUMP_METHOD void dump() const;

690 LLVM_DUMP_METHOD void dump(raw_ostream &OS) const;

691

692private:

693 using PrValueToResultObject =

694 llvm::DenseMap<const Expr *, RecordStorageLocation *>;

695

696

698

699

700

701

702

703

704

705

706

707

708

709

711 llvm::DenseSet &Visited,

712 int Depth, int &CreatedValuesCount);

713

714

715

716

717

719 llvm::DenseSet &Visited,

720 int Depth, int &CreatedValuesCount);

721

722

723

724

725

726

727

729 llvm::DenseSet &Visited, int Depth,

730 int &CreatedValuesCount);

731

732

733

735 const Expr *InitExpr);

736

737

738

739

740 void pushCallInternal(const FunctionDecl *FuncDecl,

742

743

744

745 void initFieldsGlobalsAndFuncs(const ReferencedDecls &Referenced);

746

747 static PrValueToResultObject

752

753 static PrValueToResultObject

757

758

760

761

762

763

764

765

766

767 std::vector<const FunctionDecl *> CallStack;

768

769

770

771 const FunctionDecl *InitialTargetFunc = nullptr;

772

773

774

775

776 Stmt *InitialTargetStmt = nullptr;

777

778

779

780

781

782

783

784

785 std::shared_ptr ResultObjectMap;

786

787

788

789

790

791 Value *ReturnVal = nullptr;

792

793

795

796

797

799

800

801

803

804

805

806

807

808 llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;

809 llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;

810

811

812

813

814 llvm::MapVector<const Expr *, Value *> ExprToVal;

815 llvm::MapVector<const StorageLocation *, Value *> LocToVal;

816

817 Atom FlowConditionToken;

818};

819

820

821

822

823

825 const Environment &Env);

826

827

828

829

831 const Environment &Env);

832

833}

834}

835

836#endif

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

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

This represents one expression.

Represents a function declaration or definition.

bool doesThisDeclarationHaveABody() const

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

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.

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 Expr * getInit() const

The Arena owns the objects that model data within an analysis.

IntegerValue & makeIntLiteral(llvm::APInt Value)

Returns a symbolic integer value that models an integer literal equal to Value.

TopBoolValue & makeTopValue()

Creates a fresh Top boolean value.

BoolValue & makeBoolValue(const Formula &)

Creates a BoolValue wrapping a particular formula.

AtomicBoolValue & makeAtomValue()

Creates a fresh atom and wraps in in an AtomicBoolValue.

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

const Formula & formula() const

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

Supplements Environment with non-standard comparison and join operations.

Definition DataflowEnvironment.h:69

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

Definition DataflowEnvironment.h:141

virtual ~ValueModel()=default

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.

Definition DataflowEnvironment.h:109

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.

Definition DataflowEnvironment.h:87

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

Definition DataflowEnvironment.h:65

bool allows(const Formula &) const

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

void initializeFieldsWithValues(RecordStorageLocation &Loc)

Definition DataflowEnvironment.h:494

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.

BoolValue & makeAnd(BoolValue &LHS, BoolValue &RHS) const

Returns a boolean value that represents the conjunction of LHS and RHS.

Definition DataflowEnvironment.h:595

std::enable_if_t< std::is_base_of_v< Value, T >, T * > get(const StorageLocation &Loc) const

Returns the result of casting getValue(...) to a subclass of Value (using cast_or_null).

Definition DataflowEnvironment.h:543

RecordStorageLocation * getThisPointeeStorageLocation() const

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

Definition DataflowEnvironment.h:362

BoolValue & makeIff(BoolValue &LHS, BoolValue &RHS) const

Returns a boolean value represents LHS <=> RHS.

Definition DataflowEnvironment.h:628

Arena & arena() const

Definition DataflowEnvironment.h:687

Environment pushCall(const CallExpr *Call) const

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

void clearValue(const StorageLocation &Loc)

Clears any association between Loc and a value in the environment.

Definition DataflowEnvironment.h:506

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

Environment(DataflowAnalysisContext &DACtx, Stmt &S)

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

Definition DataflowEnvironment.h:175

void setReturnValue(Value *Val)

Sets the return value of the function currently being analyzed.

Definition DataflowEnvironment.h:420

Environment(Environment &&Other)=default

BoolValue & makeTopBoolValue() const

Returns a unique instance of boolean Top.

Definition DataflowEnvironment.h:587

StorageLocation & createObject(const VarDecl &D)

Creates an object for the variable declaration D.

Definition DataflowEnvironment.h:473

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.

Value * getReturnValue() const

Returns the return value of the function currently being analyzed.

Definition DataflowEnvironment.h:396

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.

Environment(DataflowAnalysisContext &DACtx)

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

Definition DataflowEnvironment.h:170

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.

Definition DataflowEnvironment.h:582

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

Definition DataflowEnvironment.h:548

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

Environment & operator=(const Environment &Other)=delete

const FunctionDecl * getCurrentFunc() const

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

Definition DataflowEnvironment.h:670

BoolValue & getBoolLiteralValue(bool Value) const

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

Definition DataflowEnvironment.h:577

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

Creates an object (i.e.

Definition DataflowEnvironment.h:464

void assume(const Formula &)

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

DataflowAnalysisContext & getDataflowAnalysisContext() const

Returns the DataflowAnalysisContext used by the environment.

Definition DataflowEnvironment.h:685

Environment(DataflowAnalysisContext &DACtx, Atom FlowConditionToken)

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

Definition DataflowEnvironment.h:165

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.

std::enable_if_t< std::is_base_of_v< StorageLocation, T >, T * > get(const Expr &E) const

Definition DataflowEnvironment.h:355

ExprJoinBehavior

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

Definition DataflowEnvironment.h:250

@ DiscardExprState

Definition DataflowEnvironment.h:251

@ KeepExprState

Definition DataflowEnvironment.h:252

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.

IntegerValue & getIntLiteralValue(llvm::APInt Value) const

Returns a symbolic integer value that models an integer literal equal to Value

Definition DataflowEnvironment.h:571

Environment & operator=(Environment &&Other)=default

void setThisPointeeStorageLocation(RecordStorageLocation &Loc)

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

Definition DataflowEnvironment.h:368

Atom getFlowConditionToken() const

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

Definition DataflowEnvironment.h:647

Environment(DataflowAnalysisContext &DACtx, const FunctionDecl &FD)

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

Definition DataflowEnvironment.h:186

StorageLocation & createObject(const ValueDecl &D, const Expr *InitExpr)

Creates an object for the variable declaration D.

Definition DataflowEnvironment.h:482

BoolValue & makeNot(BoolValue &Val) const

Returns a boolean value that represents the negation of Val.

Definition DataflowEnvironment.h:611

size_t callStackSize() const

Returns the size of the call stack, not counting the initial analysis target.

Definition DataflowEnvironment.h:676

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

Definition DataflowEnvironment.h:350

void initialize()

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

BoolValue & makeOr(BoolValue &LHS, BoolValue &RHS) const

Returns a boolean value that represents the disjunction of LHS and RHS.

Definition DataflowEnvironment.h:604

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

Creates a T (some subclass of Value), forwarding args to the constructor, and returns a reference to ...

Definition DataflowEnvironment.h:565

void setReturnStorageLocation(StorageLocation *Loc)

Sets the storage location for the reference returned by the function currently being analyzed.

Definition DataflowEnvironment.h:432

StorageLocation * getReturnStorageLocation() const

Returns the storage location for the reference returned by the function currently being analyzed.

Definition DataflowEnvironment.h:409

std::enable_if_t< std::is_base_of_v< Value, T >, T * > get(const Expr &E) const

Definition DataflowEnvironment.h:552

BoolValue & makeImplication(BoolValue &LHS, BoolValue &RHS) const

Returns a boolean value represents LHS => RHS.

Definition DataflowEnvironment.h:619

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.

Dataflow Directional Tag Classes.

Atom

Identifies an atomic boolean variable such as "V1".

ComparisonResult

Indicates the result of a tentative comparison.

Definition DataflowEnvironment.h:44

@ Different

Definition DataflowEnvironment.h:46

@ Unknown

Definition DataflowEnvironment.h:47

@ Same

Definition DataflowEnvironment.h:45

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

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

LatticeEffect

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

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

const FunctionProtoType * T

@ Other

Other implicit parameter.

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

The result of a widen operation.

Definition DataflowEnvironment.h:51

LatticeEffect Effect

Whether V represents a "change" (that is, a different value) with respect to the previous value in th...

Definition DataflowEnvironment.h:56

Value * V

Non-null pointer to a potentially widened version of the input value.

Definition DataflowEnvironment.h:53