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

41namespace dataflow {

48};

57};

66public:

70 public:

93 }

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

162 : DACtx(&DACtx),

163 FlowConditionToken(DACtx.arena().makeFlowConditionToken()) {}

164

165

166

168 InitialTargetStmt = &S;

169 }

170

171

172

173

174

175

176

177

181 InitialTargetFunc = &FD;

182 }

183

184

186

189

190

191

192

193

194

196

197

198

199

200

201

202

203

204

206

207

208

209

210

211

212

213

214

215

216

217

220

221

222

225

226

227

228

229

230

231

232

233

234

235

238

239

240

241

245 };

246

247

248

249

250

251

252

253

257

258

259

260

261

262

263

264

265

266

267

272

273

274

275

276

277

278

279

282

283

284

285

286

287

288

289

290

291

293

294

295

296

298

299

300

301

303

304

305

306

307

308

310

311

312

314

315

317

318

319

320

321

322

323

324

326

327

328

329

330

331

332

334

335

336

337

338

339

340 template

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

344 }

345 template

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

349 }

350

351

352

353

355 return ThisPointeeLoc;

356 }

357

358

359

361 ThisPointeeLoc = &Loc;

362 }

363

364

365

366

367

368

369

370

371

372

373

374

375

378

379

380

381

382

383

384

385

386

387

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

391 return ReturnVal;

392 }

393

394

395

396

397

398

399

400

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

404 return ReturnLoc;

405 }

406

407

408

409

410

411

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

415 ReturnVal = Val;

416 }

417

418

419

420

421

422

423

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

427 ReturnLoc = Loc;

428 }

429

430

431

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

451

452

453

454

455

457 return createObjectInternal(nullptr, Ty, InitExpr);

458 }

459

460

461

462

463

464

466 return createObjectInternal(&D, D.getType(), D.getInit());

467 }

468

469

470

471

472

473

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

476 }

477

478

479

480

481

482

483

484

488 }

489

490

491

492

493

494

496

497

499

500

501

502

503

504

505

507

508

509

510

511

512

513

515

516

517

518

519

520

521

523

524

525

527

528

529

530

531

532

533 template

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

537 }

538 template

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

541 return cast_or_null(getValue(D));

542 }

543 template

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

545 return cast_or_null(getValue(E));

546 }

547

548

549

550

551

552

553

554

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

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

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

559 }

560

561

562

565 }

566

567

568

571 }

572

573

576 }

577

578

581 }

582

583

584

585

586

590 }

591

592

593

594

595

599 }

600

601

602

605 }

606

607

608

609

610

614 }

615

616

617

618

619

623 }

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

640

641

643

644

645

646

647

648

649

650

651

652

654

655

656

657

659

660

661

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

664 }

665

666

667

669

670

671

672

673

675

676

678

680

681 LLVM_DUMP_METHOD void dump() const;

682 LLVM_DUMP_METHOD void dump(raw_ostream &OS) const;

683

684private:

685 using PrValueToResultObject =

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

687

688

690

691

692

693

694

695

696

697

698

699

700

701

703 llvm::DenseSet &Visited,

704 int Depth, int &CreatedValuesCount);

705

706

707

708

709

711 llvm::DenseSet &Visited,

712 int Depth, int &CreatedValuesCount);

713

714

715

716

717

718

719

721 llvm::DenseSet &Visited, int Depth,

722 int &CreatedValuesCount);

723

724

725

727 const Expr *InitExpr);

728

729

730

731

732 void pushCallInternal(const FunctionDecl *FuncDecl,

734

735

736

737 void initFieldsGlobalsAndFuncs(const ReferencedDecls &Referenced);

738

739 static PrValueToResultObject

744

745 static PrValueToResultObject

749

750

752

753

754

755

756

757

758

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

760

761

762

763 const FunctionDecl *InitialTargetFunc = nullptr;

764

765

766

767

768 Stmt *InitialTargetStmt = nullptr;

769

770

771

772

773

774

775

776

777 std::shared_ptr ResultObjectMap;

778

779

780

781

782

783 Value *ReturnVal = nullptr;

784

785

787

788

789

791

792

793

795

796

797

798

799

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

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

802

803

804

805

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

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

808

809 Atom FlowConditionToken;

810};

811

812

813

814

815

817 const Environment &Env);

818

819

820

821

823 const Environment &Env);

824

825}

826}

827

828#endif

llvm::DenseSet< const void * > Visited

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.

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.

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

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.

void initializeFieldsWithValues(RecordStorageLocation &Loc)

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.

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

RecordStorageLocation * getThisPointeeStorageLocation() const

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

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

Returns a boolean value represents LHS <=> RHS.

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.

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

void setReturnValue(Value *Val)

Sets the return value of the function currently being analyzed.

Environment(Environment &&Other)=default

BoolValue & makeTopBoolValue() const

Returns a unique instance of boolean Top.

StorageLocation & createObject(const VarDecl &D)

Creates an object for the variable declaration D.

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.

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.

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.

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

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

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.

DataflowAnalysisContext & getDataflowAnalysisContext() const

Returns the DataflowAnalysisContext used by the environment.

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

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.

IntegerValue & getIntLiteralValue(llvm::APInt Value) const

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

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

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

Environment(DataflowAnalysisContext &DACtx, const FunctionDecl &FD)

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

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

Creates an object for the variable declaration D.

BoolValue & makeNot(BoolValue &Val) const

Returns a boolean value that represents the negation of Val.

size_t callStackSize() const

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

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

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

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

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

void setReturnStorageLocation(StorageLocation *Loc)

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

StorageLocation * getReturnStorageLocation() const

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

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

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

Returns a boolean value represents LHS => RHS.

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.

Atom

Identifies an atomic boolean variable such as "V1".

ComparisonResult

Indicates the result of a tentative comparison.

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.

LatticeEffect Effect

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

Value * V

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