Dataflow Directional Tag Classes. More...

Namespaces
namespace	internal

Classes
class	AdornedCFG
	Holds CFG with additional information derived from it that is needed to perform dataflow analysis. More...

class	AnalysisASTVisitor
	Specialization of `RecursiveASTVisitor` that visits those nodes that are relevant to the dataflow analysis; generally, these are the ones that also appear in the CFG. More...

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

class	ASTMatchSwitchBuilder
	Collects cases of a "match switch": a collection of matchers paired with callbacks, which together define a switch that can be applied to a node whose type derives from `BaseT`. More...

class	AtomicBoolValue
	Models an atomic boolean. More...

struct	backward_analysis_tag

class	BoolValue
	Models a boolean. More...

class	CachedConstAccessorsLattice
	A mixin for a lattice that additionally maintains a cache of stable method call return values to model const accessors methods. More...

struct	CFGEltCallbacks
	A pair of callbacks to be called with the state before and after visiting a CFG element. More...

struct	CFGEltCallbacksTypeErased
	A pair of callbacks to be called with the state before and after visiting a CFG element. More...

class	CFGMatchSwitchBuilder
	Collects cases of a "match switch": a collection of matchers paired with callbacks, which together define a switch that can be applied to an AST node contained in a CFG element. More...

class	ChromiumCheckModel
	Models the behavior of Chromium's CHECK, DCHECK, etc. More...

class	CNFFormula
	A boolean formula in 3-CNF (conjunctive normal form with at most 3 literals per clause). More...

struct	ContextSensitiveOptions

class	DataflowAnalysis
	Base class template for dataflow analyses built on a single lattice type. More...

class	DataflowAnalysisContext
	Owns objects that encompass the state of a program and stores context that is used during dataflow analysis. More...

struct	DataflowAnalysisOptions

struct	DataflowAnalysisState

class	DataflowModel
	Abstract base class for dataflow "models": reusable analysis components that model a particular aspect of program semantics in the `Environment`. More...

struct	DiagnosisCallbacks
	A pair of callbacks for performing diagnosis on a CFG element, called with the state before and after visiting that CFG element. More...

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

class	Formula

class	FormulaBoolValue
	Models a compound boolean formula. More...

struct	forward_analysis_tag

class	IntegerValue
	Models an integer. More...

class	Logger
	A logger is notified as the analysis progresses. More...

class	MapLattice
	A lattice that maps keys to individual lattice elements. More...

class	NoopAnalysis

class	NoopLattice
	Trivial lattice for dataflow analysis with exactly one element. More...

class	PointerValue
	Models a symbolic pointer. Specifically, any value of type `T*`. More...

class	RecordInitListHelper
	Helper class for initialization of a record with an `InitListExpr`. More...

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

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

class	ReferencedDeclsVisitor

class	ScalarStorageLocation
	A storage location that is not subdivided further for the purposes of abstract interpretation. More...

struct	SimplifyConstraintsInfo
	Information on the way a set of constraints was simplified. More...

class	Solver
	An interface for a SAT solver that can be used by dataflow analyses. More...

class	StmtToEnvMap
	Maps statements to the environments of basic blocks that contain them. More...

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

class	TopBoolValue
	A TopBoolValue represents a boolean that is explicitly unconstrained. More...

struct	TransferState
	A common form of state shared between the cases of a transfer function. More...

struct	TransferStateForDiagnostics
	A read-only version of TransferState. More...

class	TypeErasedDataflowAnalysis
	Type-erased base class for dataflow analyses built on a single lattice type. More...

struct	TypeErasedDataflowAnalysisState
	Type-erased model of the program at a given program point. More...

struct	TypeErasedLattice
	Type-erased lattice element container. More...

class	UncheckedOptionalAccessDiagnoser

class	UncheckedOptionalAccessModel
	Dataflow analysis that models whether optionals hold values or not. More...

struct	UncheckedOptionalAccessModelOptions

class	Value
	Base class for all values computed by abstract interpretation. More...

class	WatchedLiteralsSolver
	A SAT solver that is an implementation of Algorithm D from Knuth's The Art of Computer Programming Volume 4: Satisfiability, Fascicle 6. More...

struct	WidenResult
	The result of a `widen` operation. More...

Typedefs
using	FieldSet = llvm::SmallSetVector< const FieldDecl *, 4 >
	A set of `FieldDecl *`.

template<typename State , typename Result = void>
using	CFGMatchSwitch = std::function< Result(const CFGElement &, ASTContext &, State &)>

using	Variable = uint32_t
	Boolean variables are represented as positive integers.

using	Literal = uint32_t
	Literals are represented as positive integers.

using	ClauseID = uint32_t
	Clause identifiers are represented as positive integers.

template<typename AnalysisT >
using	CFGEltCallback = std::function< void(const CFGElement &, const DataflowAnalysisState< typename AnalysisT::Lattice > &)>
	A callback to be called with the state before or after visiting a CFG element.

template<typename AnalysisT , typename Diagnostic >
using	DiagnosisCallback = llvm::function_ref< llvm::SmallVector< Diagnostic >(const CFGElement &, ASTContext &, const TransferStateForDiagnostics< typename AnalysisT::Lattice > &)>
	A callback for performing diagnosis on a CFG element, called with the state before or after visiting that CFG element.

using	LatticeJoinEffect = LatticeEffect

template<typename ElementLattice >
using	VarMapLattice = MapLattice< const clang::VarDecl *, ElementLattice >
	Convenience alias that captures the common use of map lattices to model in-scope variables.

template<typename T >
using	MatchSwitchMatcher = ast_matchers::internal::Matcher< T >

template<typename T , typename State , typename Result = void>
using	MatchSwitchAction = std::function< Result(const T *, const ast_matchers::MatchFinder::MatchResult &, State &)>

template<typename BaseT , typename State , typename Result = void>
using	ASTMatchSwitch = std::function< Result(const BaseT &, ASTContext &, State &)>

using	UncheckedOptionalAccessLattice = CachedConstAccessorsLattice< NoopLattice >

using	CFGEltCallbackTypeErased = std::function< void(const CFGElement &, const TypeErasedDataflowAnalysisState &)>
	A callback to be called with the state before or after visiting a CFG element.

Enumerations
enum class	ComparisonResult { Same , Different , Unknown }
	Indicates the result of a tentative comparison. More...

enum class	LatticeEffect { Unchanged , Changed }
	Effect indicating whether a lattice operation resulted in a new value. More...

enum class	Atom : unsigned
	Identifies an atomic boolean variable such as "V1". More...

Functions
const Expr &	ignoreCFGOmittedNodes (const Expr &E)
	Skip past nodes that the CFG does not emit.

const Stmt &	ignoreCFGOmittedNodes (const Stmt &S)

FieldSet	getObjectFields (QualType Type)
	Returns the set of all fields in the type.

bool	containsSameFields (const FieldSet &Fields, const RecordStorageLocation::FieldToLoc &FieldLocs)
	Returns whether `Fields` and `FieldLocs` contain the same fields.

ReferencedDecls	getReferencedDecls (const FunctionDecl &FD)
	Returns declarations that are declared in or referenced from `FD`.

ReferencedDecls	getReferencedDecls (const Stmt &S)
	Returns declarations that are declared in or referenced from `S`.

constexpr Literal	posLit (Variable V)
	Returns the positive literal `V`.

constexpr Literal	negLit (Variable V)
	Returns the negative literal `!V`.

constexpr bool	isPosLit (Literal L)
	Returns whether `L` is a positive literal.

constexpr bool	isNegLit (Literal L)
	Returns whether `L` is a negative literal.

constexpr Literal	notLit (Literal L)
	Returns the negated literal `!L`.

constexpr Variable	var (Literal L)
	Returns the variable of `L`.

CNFFormula	buildCNF (const llvm::ArrayRef< const Formula * > &Formulas, llvm::DenseMap< Variable, Atom > &Atomics)
	Converts the conjunction of `Vals` into a formula in conjunctive normal form where each clause has at least one and at most three literals.

template<typename AnalysisT >
llvm::Expected< std::vector< std::optional< DataflowAnalysisState< typename AnalysisT::Lattice > > > >	runDataflowAnalysis (const AdornedCFG &ACFG, AnalysisT &Analysis, const Environment &InitEnv, CFGEltCallbacks< AnalysisT > PostAnalysisCallbacks={}, std::int32_t MaxBlockVisits=kDefaultMaxBlockVisits)
	Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states that model the respective basic blocks.

template<typename AnalysisT >
auto	createAnalysis (ASTContext &ASTCtx, Environment &Env) -> decltype(AnalysisT(ASTCtx, Env))

template<typename AnalysisT , typename Diagnostic >
llvm::Expected< llvm::SmallVector< Diagnostic > >	diagnoseFunction (const FunctionDecl &FuncDecl, ASTContext &ASTCtx, DiagnosisCallbacks< AnalysisT, Diagnostic > Diagnoser, std::int64_t MaxSATIterations=kDefaultMaxSATIterations, std::int32_t MaxBlockVisits=kDefaultMaxBlockVisits)
	Runs a dataflow analysis over the given function and then runs `Diagnoser` over the results.

template<typename AnalysisT , typename Diagnostic >
llvm::Expected< llvm::SmallVector< Diagnostic > >	diagnoseFunction (const FunctionDecl &FuncDecl, ASTContext &ASTCtx, DiagnosisCallback< AnalysisT, Diagnostic > Diagnoser, std::int64_t MaxSATIterations=kDefaultMaxSATIterations, std::int32_t MaxBlockVisits=kDefaultMaxBlockVisits)
	Overload that takes only one diagnosis callback, which is run on the state after visiting the `CFGElement`.

RecordStorageLocation *	getImplicitObjectLocation (const CXXMemberCallExpr &MCE, const Environment &Env)
	Returns the storage location for the implicit object of a `CXXMemberCallExpr`, or null if none is defined in the environment.

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

llvm::StringRef	debugString (Value::Kind Kind)
	Returns a string representation of a value kind.

llvm::StringRef	debugString (Solver::Result::Status Status)
	Returns a string representation of the result status of a SAT check.

llvm::raw_ostream &	operator<< (llvm::raw_ostream &OS, Atom A)

llvm::raw_ostream &	operator<< (llvm::raw_ostream &OS, const Formula &F)

template<typename Key , typename ElementLattice >
std::ostream &	operator<< (std::ostream &Os, const clang::dataflow::MapLattice< Key, ElementLattice > &M)

template<typename ElementLattice >
std::ostream &	operator<< (std::ostream &Os, const clang::dataflow::VarMapLattice< ElementLattice > &M)

std::ostream &	operator<< (std::ostream &OS, const NoopLattice &)

void	copyRecord (RecordStorageLocation &Src, RecordStorageLocation &Dst, Environment &Env)
	Copies a record (struct, class, or union) from `Src` to `Dst`.

bool	recordsEqual (const RecordStorageLocation &Loc1, const Environment &Env1, const RecordStorageLocation &Loc2, const Environment &Env2)
	Returns whether the records `Loc1` and `Loc2` are equal.

bool	recordsEqual (const RecordStorageLocation &Loc1, const RecordStorageLocation &Loc2, const Environment &Env)

void	simplifyConstraints (llvm::SetVector< const Formula * > &Constraints, Arena &arena, SimplifyConstraintsInfo *Info=nullptr)
	Simplifies a set of constraints (implicitly connected by "and") in a way that does not change satisfiability of the constraints.

llvm::raw_ostream &	operator<< (llvm::raw_ostream &, const Solver::Result &)

llvm::raw_ostream &	operator<< (llvm::raw_ostream &, Solver::Result::Assignment)

void	transfer (const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env, Environment::ValueModel &Model)
	Evaluates `S` and updates `Env` accordingly.

llvm::Expected< std::vector< std::optional< TypeErasedDataflowAnalysisState > > >	runTypeErasedDataflowAnalysis (const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv, const CFGEltCallbacksTypeErased &PostAnalysisCallbacks, std::int32_t MaxBlockVisits)
	Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states that model the respective basic blocks.

bool	areEquivalentValues (const Value &Val1, const Value &Val2)
	An equivalence relation for values.

raw_ostream &	operator<< (raw_ostream &OS, const Value &Val)

static llvm::DenseMap< const Stmt , const CFGBlock >	buildStmtToBasicBlockMap (const CFG &Cfg)
	Returns a map from statements to basic blocks that contain them.

static llvm::BitVector	findReachableBlocks (const CFG &Cfg)

static llvm::DenseSet< const CFGBlock * >	buildContainsExprConsumedInDifferentBlock (const CFG &Cfg, const internal::StmtToBlockMap &StmtToBlock)

static std::pair< const Formula , const Formula >	canonicalFormulaPair (const Formula &LHS, const Formula &RHS)

template<class Key , class ComputeFunc >
static const Formula &	cached (llvm::DenseMap< Key, const Formula * > &Cache, Key K, ComputeFunc &&Compute)

static void	getFieldsFromClassHierarchy (QualType Type, FieldSet &Fields)

template<class InitListT >
static std::vector< const FieldDecl * >	getFieldsForInitListExpr (const InitListT *InitList)
	Returns the fields of a `RecordDecl` that are initialized by an `InitListExpr` or `CXXParenListInitExpr`, in the order in which they appear in `InitListExpr::inits()` / `CXXParenListInitExpr::getInitExprs()`.

static void	insertIfGlobal (const Decl &D, llvm::DenseSet< const VarDecl * > &Globals)

static void	insertIfLocal (const Decl &D, llvm::DenseSet< const VarDecl * > &Locals)

static void	insertIfFunction (const Decl &D, llvm::DenseSet< const FunctionDecl * > &Funcs)

static MemberExpr *	getMemberForAccessor (const CXXMemberCallExpr &C)

template<typename T >
static llvm::DenseSet< llvm::StringRef >	getKeys (const llvm::StringMap< T > &Map)

static void	printAtomList (const llvm::SmallVector< Atom > &Atoms, llvm::raw_ostream &OS)

static std::unique_ptr< Logger >	makeLoggerFromCommandLine ()

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.

template<typename MapT >
static MapT	joinExprMaps (const MapT &Map1, const MapT &Map2)

static bool	equateUnknownValues (Value::Kind K)

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

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

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

template<typename Key >
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::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)

template<typename Key >
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 llvm::StringLiteral	sigil (Formula::Kind K)

static bool	isCheckLikeMethod (llvm::SmallDenseSet< const CXXMethodDecl * > &CheckDecls, const CXXMethodDecl &D)
	Determines whether `D` is one of the methods used to implement Chromium's `CHECK` macros.

template<class... NameTypes>
static bool	isFullyQualifiedNamespaceEqualTo (const NamespaceDecl &NS, llvm::StringRef Name, NameTypes... Names)

static bool	hasOptionalClassName (const CXXRecordDecl &RD)

static const CXXRecordDecl *	getOptionalBaseClass (const CXXRecordDecl *RD)

static bool	isSupportedOptionalType (QualType Ty)

static void	copyField (const ValueDecl &Field, StorageLocation SrcFieldLoc, StorageLocation DstFieldLoc, RecordStorageLocation &Dst, Environment &Env)

static void	copySyntheticField (QualType FieldType, StorageLocation &SrcFieldLoc, StorageLocation &DstFieldLoc, Environment &Env)

static const Formula &	substitute (const Formula &F, const llvm::DenseMap< Atom, const Formula * > &Substitutions, Arena &arena)

static llvm::DenseSet< Atom >	projectToLeaders (const llvm::DenseSet< Atom > &Atoms, llvm::EquivalenceClasses< Atom > &EquivalentAtoms)

static llvm::SmallVector< Atom >	atomsInEquivalenceClass (const llvm::EquivalenceClasses< Atom > &EquivalentAtoms, llvm::EquivalenceClasses< Atom >::iterator LeaderIt)

static BoolValue &	evaluateBooleanEquality (const Expr &LHS, const Expr &RHS, Environment &Env)

static BoolValue &	unpackValue (BoolValue &V, Environment &Env)

static Value *	maybeUnpackLValueExpr (const Expr &E, Environment &Env)

static void	propagateValue (const Expr &From, const Expr &To, Environment &Env)

static void	propagateStorageLocation (const Expr &From, const Expr &To, Environment &Env)

static void	propagateValueOrStorageLocation (const Expr &From, const Expr &To, Environment &Env)

static int	blockIndexInPredecessor (const CFGBlock &Pred, const CFGBlock &Block)
	Returns the index of `Block` in the successors of `Pred`.

static bool	isBackedgeNode (const CFGBlock &B)

static const Expr *	getTerminatorCondition (const Stmt *TerminatorStmt)

static TypeErasedDataflowAnalysisState	computeBlockInputState (const CFGBlock &Block, AnalysisContext &AC)
	Computes the input state for a given basic block by joining the output states of its predecessors.

static void	builtinTransferStatement (unsigned CurBlockID, const CFGStmt &Elt, TypeErasedDataflowAnalysisState &InputState, AnalysisContext &AC)
	Built-in transfer function for `CFGStmt`.

static void	builtinTransferInitializer (const CFGInitializer &Elt, TypeErasedDataflowAnalysisState &InputState)
	Built-in transfer function for `CFGInitializer`.

static void	builtinTransfer (unsigned CurBlockID, const CFGElement &Elt, TypeErasedDataflowAnalysisState &State, AnalysisContext &AC)

static TypeErasedDataflowAnalysisState	transferCFGBlock (const CFGBlock &Block, AnalysisContext &AC, const CFGEltCallbacksTypeErased &PostAnalysisCallbacks={})
	Transfers `State` by evaluating each element in the `Block` based on the `AC.Analysis` specified.

static bool	areEquivalentIndirectionValues (const Value &Val1, const Value &Val2)

Variables
constexpr Variable	NullVar = 0
	A null boolean variable is used as a placeholder in various data structures and algorithms.

constexpr Literal	NullLit = 0
	A null literal is used as a placeholder in various data structures and algorithms.

constexpr ClauseID	NullClause = 0
	A null clause identifier is used as a placeholder in various data structures and algorithms.

constexpr std::int64_t	kDefaultMaxSATIterations = 1'000'000'000
	Default for the maximum number of SAT solver iterations during analysis.

constexpr std::int32_t	kDefaultMaxBlockVisits = 20'000
	Default for the maximum number of block visits during analysis.

static constexpr int	MaxCompositeValueDepth = 3

static constexpr int	MaxCompositeValueSize = 1000

Detailed Description

Dataflow Directional Tag Classes.

These are used for tag dispatching within the dataflow solver/transfer functions to determine what direction a dataflow analysis flows.

Typedef Documentation

◆ ASTMatchSwitch

template<typename BaseT , typename State , typename Result = void>

using clang::dataflow::ASTMatchSwitch = typedef std::function<Result(const BaseT &, ASTContext &, State &)>

Definition at line 72 of file MatchSwitch.h.

◆ CFGEltCallback

template<typename AnalysisT >

using clang::dataflow::CFGEltCallback = typedef std::function<void( const CFGElement &, const DataflowAnalysisState<typename AnalysisT::Lattice> &)>

A callback to be called with the state before or after visiting a CFG element.

Definition at line 184 of file DataflowAnalysis.h.

◆ CFGEltCallbackTypeErased

using clang::dataflow::CFGEltCallbackTypeErased = typedef std::function<void( const CFGElement &, const TypeErasedDataflowAnalysisState &)>

A callback to be called with the state before or after visiting a CFG element.

Definition at line 137 of file TypeErasedDataflowAnalysis.h.

◆ CFGMatchSwitch

template<typename State , typename Result = void>

using clang::dataflow::CFGMatchSwitch = typedef std::function<Result(const CFGElement &, ASTContext &, State &)>

Definition at line 33 of file CFGMatchSwitch.h.

◆ ClauseID

using clang::dataflow::ClauseID = typedef uint32_t

Clause identifiers are represented as positive integers.

Definition at line 42 of file CNFFormula.h.

◆ DiagnosisCallback

template<typename AnalysisT , typename Diagnostic >

using clang::dataflow::DiagnosisCallback = typedef llvm::function_ref<llvm::SmallVector<Diagnostic>( const CFGElement &, ASTContext &, const TransferStateForDiagnostics<typename AnalysisT::Lattice> &)>

A callback for performing diagnosis on a CFG element, called with the state before or after visiting that CFG element.

Returns a list of diagnostics to emit (if any).

Definition at line 200 of file DataflowAnalysis.h.

◆ FieldSet

using clang::dataflow::FieldSet = typedef llvm::SmallSetVector<const FieldDecl *, 4>

A set of FieldDecl *.

Use SmallSetVector to guarantee deterministic iteration order.

Definition at line 43 of file ASTOps.h.

◆ LatticeJoinEffect

using clang::dataflow::LatticeJoinEffect = typedef LatticeEffect

Definition at line 26 of file DataflowLattice.h.

◆ Literal

using clang::dataflow::Literal = typedef uint32_t

Literals are represented as positive integers.

Specifically, for a boolean variable V that is represented as the positive integer I, the positive literal V is represented as the integer 2*I and the negative literal !V is represented as the integer 2*I+1.

Definition at line 35 of file CNFFormula.h.

◆ MatchSwitchAction

template<typename T , typename State , typename Result = void>

using clang::dataflow::MatchSwitchAction = typedef std::function<Result( const T *, const ast_matchers::MatchFinder::MatchResult &, State &)>

Definition at line 68 of file MatchSwitch.h.

◆ MatchSwitchMatcher

template<typename T >

using clang::dataflow::MatchSwitchMatcher = typedef ast_matchers::internal::Matcher<T>

Definition at line 65 of file MatchSwitch.h.

◆ UncheckedOptionalAccessLattice

using clang::dataflow::UncheckedOptionalAccessLattice = typedef CachedConstAccessorsLattice<NoopLattice>

Definition at line 51 of file UncheckedOptionalAccessModel.h.

◆ Variable

using clang::dataflow::Variable = typedef uint32_t

Boolean variables are represented as positive integers.

Definition at line 25 of file CNFFormula.h.

◆ VarMapLattice

template<typename ElementLattice >

using clang::dataflow::VarMapLattice = typedef MapLattice<const clang::VarDecl *, ElementLattice>

Convenience alias that captures the common use of map lattices to model in-scope variables.

Definition at line 112 of file MapLattice.h.

Enumeration Type Documentation

◆ Atom

enum class clang::dataflow::Atom : unsigned

strong

Identifies an atomic boolean variable such as "V1".

This often represents an assertion that is interesting to the analysis but cannot immediately be proven true or false. For example:

V1 may mean "the program reaches this point",
V2 may mean "the parameter was null"

We can use these variables in formulas to describe relationships we know to be true: "if the parameter was null, the program reaches this point". We also express hypotheses as formulas, and use a SAT solver to check whether they are consistent with the known facts.

Definition at line 34 of file Formula.h.

◆ ComparisonResult

enum class clang::dataflow::ComparisonResult

strong

Indicates the result of a tentative comparison.

Enumerator
Same
Different
Unknown

Definition at line 44 of file DataflowEnvironment.h.

◆ LatticeEffect

enum class clang::dataflow::LatticeEffect

strong

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

Enumerator
Unchanged
Changed

Definition at line 21 of file DataflowLattice.h.

Function Documentation

◆ areEquivalentIndirectionValues()

static bool clang::dataflow::areEquivalentIndirectionValues	(	const Value &	Val1,
		const Value &	Val2
	)

static

Definition at line 20 of file Value.cpp.

Referenced by areEquivalentValues().

◆ areEquivalentValues()

bool clang::dataflow::areEquivalentValues	(	const Value &	Val1,
		const Value &	Val2
	)

An equivalence relation for values.

It obeys reflexivity, symmetry and transitivity. It does not include comparison of Properties.

Computes equivalence for these subclasses:

PointerValue – pointee locations are equal. Does not compute deep equality of Value at said location.
TopBoolValue – both are TopBoolValues.

Otherwise, falls back to pointer equality.

Definition at line 29 of file Value.cpp.

References areEquivalentIndirectionValues(), clang::dataflow::Value::getKind(), and clang::dataflow::Value::properties().

Referenced by compareKeyToValueMaps(), clang::dataflow::Environment::joinValues(), and widenKeyToValueMap().

◆ atomsInEquivalenceClass()

static llvm::SmallVector< Atom > clang::dataflow::atomsInEquivalenceClass	(	const llvm::EquivalenceClasses< Atom > &	EquivalentAtoms,
		llvm::EquivalenceClasses< Atom >::iterator	LeaderIt
	)

static

Definition at line 66 of file SimplifyConstraints.cpp.

References clang::Result.

Referenced by simplifyConstraints().

◆ blockIndexInPredecessor()

static int clang::dataflow::blockIndexInPredecessor	(	const CFGBlock &	Pred,
		const CFGBlock &	Block
	)

static

Returns the index of Block in the successors of Pred.

Definition at line 59 of file TypeErasedDataflowAnalysis.cpp.

References Block, blockIndexInPredecessor(), clang::CFGBlock::succ_begin(), and clang::CFGBlock::succs().

Referenced by blockIndexInPredecessor(), and computeBlockInputState().

◆ buildCNF()

CNFFormula clang::dataflow::buildCNF	(	const llvm::ArrayRef< const Formula * > &	Formulas,
		llvm::DenseMap< Variable, Atom > &	Atomics
	)

Converts the conjunction of Vals into a formula in conjunctive normal form where each clause has at least one and at most three literals.

Atomics is populated with a mapping from Variables to the corresponding Atoms for atomic booleans in the input formulas.

Definition at line 116 of file CNFFormula.cpp.

◆ buildContainsExprConsumedInDifferentBlock()

static llvm::DenseSet< const CFGBlock * > clang::dataflow::buildContainsExprConsumedInDifferentBlock	(	const CFG &	Cfg,
		const internal::StmtToBlockMap &	StmtToBlock
	)

static

Definition at line 99 of file AdornedCFG.cpp.

References Block, buildContainsExprConsumedInDifferentBlock(), and clang::dataflow::internal::StmtToBlockMap::lookup().

Referenced by clang::dataflow::AdornedCFG::build(), and buildContainsExprConsumedInDifferentBlock().

◆ buildStmtToBasicBlockMap()

static llvm::DenseMap< const Stmt *, const CFGBlock * > clang::dataflow::buildStmtToBasicBlockMap ( const CFG & Cfg )

static

Returns a map from statements to basic blocks that contain them.

Definition at line 30 of file AdornedCFG.cpp.

References clang::Block.

Referenced by clang::dataflow::internal::StmtToBlockMap::StmtToBlockMap().

◆ builtinTransfer()

static void clang::dataflow::builtinTransfer	(	unsigned	CurBlockID,
		const CFGElement &	Elt,
		TypeErasedDataflowAnalysisState &	State,
		AnalysisContext &	AC
	)

static

Definition at line 395 of file TypeErasedDataflowAnalysis.cpp.

References builtinTransfer(), builtinTransferInitializer(), builtinTransferStatement(), clang::CFGElement::castAs(), clang::CFGElement::getKind(), and clang::CFGLifetimeEnds::getVarDecl().

Referenced by builtinTransfer().

◆ builtinTransferInitializer()

static void clang::dataflow::builtinTransferInitializer	(	const CFGInitializer &	Elt,
		TypeErasedDataflowAnalysisState &	InputState
	)

static

Built-in transfer function for CFGInitializer.

Definition at line 340 of file TypeErasedDataflowAnalysis.cpp.

References builtinTransferInitializer(), clang::IndirectFieldDecl::chain(), clang::dataflow::TypeErasedDataflowAnalysisState::Env, Env, clang::dataflow::RecordStorageLocation::getChild(), clang::CFGInitializer::getInitializer(), clang::Member, and clang::dataflow::RecordStorageLocation::setChild().

Referenced by builtinTransfer(), and builtinTransferInitializer().

◆ builtinTransferStatement()

static void clang::dataflow::builtinTransferStatement	(	unsigned	CurBlockID,
		const CFGStmt &	Elt,
		TypeErasedDataflowAnalysisState &	InputState,
		AnalysisContext &	AC
	)

static

Built-in transfer function for CFGStmt.

Definition at line 329 of file TypeErasedDataflowAnalysis.cpp.

References builtinTransferStatement(), clang::dataflow::TypeErasedDataflowAnalysisState::Env, clang::CFGStmt::getStmt(), and transfer().

Referenced by builtinTransfer(), and builtinTransferStatement().

◆ cached()

template<class Key , class ComputeFunc >

static const Formula & clang::dataflow::cached	(	llvm::DenseMap< Key, const Formula * > &	Cache,
		Key	K,
		ComputeFunc &&	Compute
	)

static

Definition at line 26 of file Arena.cpp.

References clang::Compute.

Referenced by clang::dataflow::Arena::makeAnd(), clang::dataflow::Arena::makeAtomRef(), clang::dataflow::Arena::makeEquals(), clang::dataflow::Arena::makeImplies(), clang::dataflow::Arena::makeNot(), and clang::dataflow::Arena::makeOr().

◆ canonicalFormulaPair()

static std::pair< const Formula , const Formula > clang::dataflow::canonicalFormulaPair	(	const Formula &	LHS,
		const Formula &	RHS
	)

static

Definition at line 18 of file Arena.cpp.

Referenced by clang::dataflow::Arena::makeAnd(), clang::dataflow::Arena::makeEquals(), and clang::dataflow::Arena::makeOr().

◆ compareDistinctValues()

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

static

Definition at line 97 of file DataflowEnvironment.cpp.

References clang::dataflow::Environment::ValueModel::compare(), Different, equateUnknownValues(), clang::dataflow::Value::getKind(), Same, and Unknown.

Referenced by compareKeyToValueMaps().

◆ compareKeyToValueMaps()

template<typename Key >

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

static

Definition at line 208 of file DataflowEnvironment.cpp.

References areEquivalentValues(), and compareDistinctValues().

Referenced by clang::dataflow::Environment::equivalentTo().

◆ computeBlockInputState()

static TypeErasedDataflowAnalysisState clang::dataflow::computeBlockInputState	(	const CFGBlock &	Block,
		AnalysisContext &	AC
	)

static

Computes the input state for a given basic block by joining the output states of its predecessors.

Requirements:

All predecessors of Block except those with loop back edges must have already been transferred. States in AC.BlockStates that are set to std::nullopt represent basic blocks that are not evaluated yet.

Definition at line 234 of file TypeErasedDataflowAnalysis.cpp.

References Block, blockIndexInPredecessor(), computeBlockInputState(), clang::Copy, clang::dataflow::BoolValue::formula(), and getTerminatorCondition().

Referenced by computeBlockInputState().

◆ containsSameFields()

bool clang::dataflow::containsSameFields	(	const FieldSet &	Fields,
		const RecordStorageLocation::FieldToLoc &	FieldLocs
	)

Returns whether Fields and FieldLocs contain the same fields.

Definition at line 81 of file ASTOps.cpp.

References Loc.

Referenced by clang::dataflow::DataflowAnalysisContext::createRecordStorageLocation().

◆ copyField()

static void clang::dataflow::copyField	(	const ValueDecl &	Field,
		StorageLocation *	SrcFieldLoc,
		StorageLocation *	DstFieldLoc,
		RecordStorageLocation &	Dst,
		Environment &	Env
	)

static

Definition at line 19 of file RecordOps.cpp.

References clang::dataflow::Environment::clearValue(), copyRecord(), Env, clang::dataflow::Environment::getValue(), clang::dataflow::RecordStorageLocation::setChild(), and clang::dataflow::Environment::setValue().

Referenced by copyRecord().

◆ copyRecord()

void clang::dataflow::copyRecord	(	RecordStorageLocation &	Src,
		RecordStorageLocation &	Dst,
		Environment &	Env
	)

Copies a record (struct, class, or union) from Src to Dst.

This performs a deep copy, i.e. it copies every field (including synthetic fields) and recurses on fields of record type.

If there is a RecordValue associated with Dst in the environment, this function creates a new RecordValue and associates it with Dst; clients need to be aware of this and must not assume that the RecordValue associated with Dst remains the same after the call.

Requirements:

Either:

Src and Dest must have the same canonical unqualified type, or
The type of Src must be derived from Dest, or
The type of Dest must be derived from Src (in this case, any fields that are only present in Dest are not overwritten).

Definition at line 51 of file RecordOps.cpp.

References clang::dataflow::RecordStorageLocation::children(), copyField(), copySyntheticField(), Env, clang::Type::getAsCXXRecordDecl(), clang::QualType::getCanonicalType(), clang::dataflow::RecordStorageLocation::getChild(), clang::dataflow::RecordStorageLocation::getSyntheticField(), clang::dataflow::StorageLocation::getType(), clang::QualType::getUnqualifiedType(), and clang::dataflow::RecordStorageLocation::synthetic_fields().

Referenced by copyField(), and copySyntheticField().

◆ copySyntheticField()

static void clang::dataflow::copySyntheticField	(	QualType	FieldType,
		StorageLocation &	SrcFieldLoc,
		StorageLocation &	DstFieldLoc,
		Environment &	Env
	)

static

Definition at line 38 of file RecordOps.cpp.

References clang::dataflow::Environment::clearValue(), copyRecord(), Env, clang::dataflow::Environment::getValue(), clang::Type::isRecordType(), and clang::dataflow::Environment::setValue().

Referenced by copyRecord().

◆ createAnalysis()

template<typename AnalysisT >

auto clang::dataflow::createAnalysis	(	ASTContext &	ASTCtx,
		Environment &	Env
	)		-> decltype(AnalysisT(ASTCtx, Env))

Definition at line 295 of file DataflowAnalysis.h.

References Env.

◆ debugString() [1/2]

llvm::StringRef clang::dataflow::debugString ( Solver::Result::Status Status )

Returns a string representation of the result status of a SAT check.

Definition at line 52 of file DebugSupport.cpp.

References clang::dataflow::Solver::Result::Satisfiable, clang::dataflow::Solver::Result::TimedOut, and clang::dataflow::Solver::Result::Unsatisfiable.

◆ debugString() [2/2]

llvm::StringRef clang::dataflow::debugString ( Value::Kind Kind )

Returns a string representation of a value kind.

Definition at line 25 of file DebugSupport.cpp.

References clang::dataflow::Value::AtomicBool, clang::dataflow::Value::FormulaBool, clang::dataflow::Value::Integer, Kind, clang::dataflow::Value::Pointer, and clang::dataflow::Value::TopBool.

Referenced by operator<<().

◆ diagnoseFunction() [1/2]

template<typename AnalysisT , typename Diagnostic >

llvm::Expected< llvm::SmallVector< Diagnostic > > clang::dataflow::diagnoseFunction	(	const FunctionDecl &	FuncDecl,
		ASTContext &	ASTCtx,
		DiagnosisCallback< AnalysisT, Diagnostic >	Diagnoser,
		std::int64_t	MaxSATIterations = `kDefaultMaxSATIterations`,
		std::int32_t	MaxBlockVisits = `kDefaultMaxBlockVisits`
	)

Overload that takes only one diagnosis callback, which is run on the state after visiting the CFGElement.

This is provided for backwards compatibility; new callers should call the overload taking DiagnosisCallbacks instead.

Definition at line 383 of file DataflowAnalysis.h.

References diagnoseFunction().

◆ diagnoseFunction() [2/2]

template<typename AnalysisT , typename Diagnostic >

llvm::Expected< llvm::SmallVector< Diagnostic > > clang::dataflow::diagnoseFunction	(	const FunctionDecl &	FuncDecl,
		ASTContext &	ASTCtx,
		DiagnosisCallbacks< AnalysisT, Diagnostic >	Diagnoser,
		std::int64_t	MaxSATIterations = `kDefaultMaxSATIterations`,
		std::int32_t	MaxBlockVisits = `kDefaultMaxBlockVisits`
	)

Runs a dataflow analysis over the given function and then runs Diagnoser over the results.

Returns a list of diagnostics for FuncDecl or an error. Currently, errors can occur (at least) because the analysis requires too many iterations over the CFG or the SAT solver times out.

The default value of MaxSATIterations was chosen based on the following observations:

Non-pathological calls to the solver typically require only a few hundred iterations.
This limit is still low enough to keep runtimes acceptable (on typical machines) in cases where we hit the limit.

MaxBlockVisits caps the number of block visits during analysis. See runDataflowAnalysis for a full description and explanation of the default value.

Definition at line 322 of file DataflowAnalysis.h.

References clang::dataflow::DiagnosisCallbacks< AnalysisT, Diagnostic >::After, clang::dataflow::CFGEltCallbacksTypeErased::After, Analysis, clang::dataflow::DiagnosisCallbacks< AnalysisT, Diagnostic >::Before, clang::dataflow::CFGEltCallbacksTypeErased::Before, clang::dataflow::AdornedCFG::build(), Env, clang::dataflow::Solver::reachedLimit(), and runTypeErasedDataflowAnalysis().

Referenced by diagnoseFunction().

◆ equateUnknownValues()

static bool clang::dataflow::equateUnknownValues ( Value::Kind K )

static

Definition at line 87 of file DataflowEnvironment.cpp.

References clang::dataflow::Value::Integer, and clang::dataflow::Value::Pointer.

Referenced by compareDistinctValues(), and widenDistinctValues().

◆ evaluateBooleanEquality()

static BoolValue & clang::dataflow::evaluateBooleanEquality	(	const Expr &	LHS,
		const Expr &	RHS,
		Environment &	Env
	)

static

Definition at line 58 of file Transfer.cpp.

References Env, clang::dataflow::Environment::getBoolLiteralValue(), clang::dataflow::Environment::getValue(), clang::dataflow::Environment::makeAtomicBoolValue(), and clang::dataflow::Environment::makeIff().

◆ findReachableBlocks()

static llvm::BitVector clang::dataflow::findReachableBlocks ( const CFG & Cfg )

static

Definition at line 76 of file AdornedCFG.cpp.

References Block, findReachableBlocks(), clang::CFG::getEntry(), and clang::CFG::getNumBlockIDs().

Referenced by clang::dataflow::AdornedCFG::build(), and findReachableBlocks().

◆ getBaseObjectLocation()

RecordStorageLocation * clang::dataflow::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 environment.

Dereferences the pointer if the member expression was written using ->.

Definition at line 1245 of file DataflowEnvironment.cpp.

References Env, clang::dataflow::Environment::get(), clang::MemberExpr::getBase(), and clang::MemberExpr::isArrow().

◆ getFieldsForInitListExpr()

template<class InitListT >

static std::vector< const FieldDecl * > clang::dataflow::getFieldsForInitListExpr ( const InitListT * InitList )

static

Returns the fields of a RecordDecl that are initialized by an InitListExpr or CXXParenListInitExpr, in the order in which they appear in InitListExpr::inits() / CXXParenListInitExpr::getInitExprs().

InitList->getType() must be a record type.

Definition at line 97 of file ASTOps.cpp.

References clang::RecordDecl::fields().

Referenced by clang::dataflow::ReferencedDeclsVisitor::VisitCXXParenListInitExpr(), and clang::dataflow::ReferencedDeclsVisitor::VisitInitListExpr().

◆ getFieldsFromClassHierarchy()

static void clang::dataflow::getFieldsFromClassHierarchy	(	QualType	Type,
		FieldSet &	Fields
	)

static

Definition at line 62 of file ASTOps.cpp.

References clang::RecordDecl::fields(), clang::Type::getAsCXXRecordDecl(), clang::Type::getAsRecordDecl(), getFieldsFromClassHierarchy(), clang::Type::isDependentType(), clang::Type::isIncompleteType(), and clang::Type::isRecordType().

Referenced by getFieldsFromClassHierarchy(), and getObjectFields().

◆ getImplicitObjectLocation()

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

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

Dereferences the pointer if the member call expression was written using ->.

Definition at line 1231 of file DataflowEnvironment.cpp.

References Env, clang::dataflow::Environment::get(), clang::CXXMemberCallExpr::getImplicitObjectArgument(), clang::dataflow::Environment::getStorageLocation(), clang::Expr::getType(), and clang::Type::isPointerType().

◆ getKeys()

template<typename T >

static llvm::DenseSet< llvm::StringRef > clang::dataflow::getKeys ( const llvm::StringMap< T > & Map )

static

Definition at line 88 of file DataflowAnalysisContext.cpp.

References getKeys().

Referenced by clang::dataflow::DataflowAnalysisContext::createRecordStorageLocation(), and getKeys().

◆ getMemberForAccessor()

static MemberExpr * clang::dataflow::getMemberForAccessor ( const CXXMemberCallExpr & C )

static

Definition at line 187 of file ASTOps.cpp.

References clang::C.

Referenced by clang::dataflow::ReferencedDeclsVisitor::VisitCXXMemberCallExpr().

◆ getObjectFields()

FieldSet clang::dataflow::getObjectFields ( QualType Type )

Returns the set of all fields in the type.

Gets the set of all fields in the type.

Definition at line 75 of file ASTOps.cpp.

References getFieldsFromClassHierarchy().

Referenced by clang::dataflow::DataflowAnalysisContext::getModeledFields().

◆ getOptionalBaseClass()

static const CXXRecordDecl * clang::dataflow::getOptionalBaseClass ( const CXXRecordDecl * RD )

static

Definition at line 91 of file UncheckedOptionalAccessModel.cpp.

References clang::CXXRecordDecl::bases(), getOptionalBaseClass(), clang::CXXRecordDecl::hasDefinition(), and hasOptionalClassName().

Referenced by getOptionalBaseClass(), isSupportedOptionalType(), and clang::dataflow::UncheckedOptionalAccessModel::UncheckedOptionalAccessModel().

◆ getReferencedDecls() [1/2]

ReferencedDecls clang::dataflow::getReferencedDecls ( const FunctionDecl & FD )

Returns declarations that are declared in or referenced from FD.

Definition at line 279 of file ASTOps.cpp.

References clang::FunctionDecl::getBody(), clang::isLambdaCallOperator(), clang::Result, clang::dataflow::ReferencedDeclsVisitor::traverseConstructorInits(), and clang::DynamicRecursiveASTVisitor::TraverseStmt().

Referenced by clang::dataflow::Environment::initialize().

◆ getReferencedDecls() [2/2]

ReferencedDecls clang::dataflow::getReferencedDecls ( const Stmt & S )

Returns declarations that are declared in or referenced from S.

Definition at line 311 of file ASTOps.cpp.

References clang::Result, and clang::DynamicRecursiveASTVisitor::TraverseStmt().

◆ getTerminatorCondition()

static const Expr * clang::dataflow::getTerminatorCondition ( const Stmt * TerminatorStmt )

static

Definition at line 220 of file TypeErasedDataflowAnalysis.cpp.

◆ hasOptionalClassName()

static bool clang::dataflow::hasOptionalClassName ( const CXXRecordDecl & RD )

static

Definition at line 63 of file UncheckedOptionalAccessModel.cpp.

References clang::Decl::getDeclContext(), clang::NamedDecl::getDeclName(), clang::NamedDecl::getName(), isFullyQualifiedNamespaceEqualTo(), and clang::DeclarationName::isIdentifier().

Referenced by getOptionalBaseClass().

◆ ignoreCFGOmittedNodes() [1/2]

const Expr & clang::dataflow::ignoreCFGOmittedNodes ( const Expr & E )

Skip past nodes that the CFG does not emit.

These nodes are invisible to flow-sensitive analysis, and should be ignored as they will effectively not exist.

ParenExpr - The CFG takes the operator precedence into account, but otherwise omits the node afterwards.
ExprWithCleanups - The CFG will generate the appropriate calls to destructors and then omit the node.

Definition at line 35 of file ASTOps.cpp.

References E, and clang::Last.

Referenced by clang::dataflow::DataflowAnalysisContext::getStableStorageLocation(), clang::dataflow::Environment::getStorageLocation(), clang::dataflow::Environment::getValue(), ignoreCFGOmittedNodes(), clang::dataflow::internal::StmtToBlockMap::lookup(), clang::dataflow::Environment::setStorageLocation(), and clang::dataflow::Environment::setValue().

◆ ignoreCFGOmittedNodes() [2/2]

const Stmt & clang::dataflow::ignoreCFGOmittedNodes ( const Stmt & S )

Definition at line 54 of file ASTOps.cpp.

References E, and ignoreCFGOmittedNodes().

◆ insertIfFunction()

static void clang::dataflow::insertIfFunction	(	const Decl &	D,
		llvm::DenseSet< const FunctionDecl * > &	Funcs
	)

static

Definition at line 181 of file ASTOps.cpp.

References D.

Referenced by clang::dataflow::ReferencedDeclsVisitor::VisitDecl(), clang::dataflow::ReferencedDeclsVisitor::VisitDeclRefExpr(), and clang::dataflow::ReferencedDeclsVisitor::VisitMemberExpr().

◆ insertIfGlobal()

static void clang::dataflow::insertIfGlobal	(	const Decl &	D,
		llvm::DenseSet< const VarDecl * > &	Globals
	)

static

Definition at line 167 of file ASTOps.cpp.

References D, and V.

Referenced by clang::dataflow::ReferencedDeclsVisitor::VisitDecl(), clang::dataflow::ReferencedDeclsVisitor::VisitDeclRefExpr(), and clang::dataflow::ReferencedDeclsVisitor::VisitMemberExpr().

◆ insertIfLocal()

static void clang::dataflow::insertIfLocal	(	const Decl &	D,
		llvm::DenseSet< const VarDecl * > &	Locals
	)

static

Definition at line 174 of file ASTOps.cpp.

References D, and V.

Referenced by clang::dataflow::ReferencedDeclsVisitor::VisitDecl(), and clang::dataflow::ReferencedDeclsVisitor::VisitDeclRefExpr().

◆ intersectDeclToLoc()

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

static

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

Definition at line 50 of file DataflowEnvironment.cpp.

References clang::Result.

Referenced by clang::dataflow::Environment::join().

◆ isBackedgeNode()

static bool clang::dataflow::isBackedgeNode ( const CFGBlock & B )

static

Definition at line 74 of file TypeErasedDataflowAnalysis.cpp.

References clang::CFGBlock::getLoopTarget(), and isBackedgeNode().

Referenced by isBackedgeNode(), and runTypeErasedDataflowAnalysis().

◆ isCheckLikeMethod()

static bool clang::dataflow::isCheckLikeMethod	(	llvm::SmallDenseSet< const CXXMethodDecl * > &	CheckDecls,
		const CXXMethodDecl &	D
	)

static

Determines whether D is one of the methods used to implement Chromium's CHECK macros.

Populates CheckDecls, if empty.

Definition at line 20 of file ChromiumCheckModel.cpp.

References D, clang::Decl::getDeclContext(), clang::NamedDecl::getDeclName(), clang::NamedDecl::getName(), clang::DeclarationName::isIdentifier(), and clang::CXXRecordDecl::methods().

Referenced by clang::dataflow::ChromiumCheckModel::transfer().

◆ isFullyQualifiedNamespaceEqualTo()

template<class... NameTypes>

static bool clang::dataflow::isFullyQualifiedNamespaceEqualTo	(	const NamespaceDecl &	NS,
		llvm::StringRef	Name,
		NameTypes...	Names
	)

static

Definition at line 45 of file UncheckedOptionalAccessModel.cpp.

References clang::NamedDecl::getDeclName(), clang::NamedDecl::getName(), clang::DeclContext::getParent(), isFullyQualifiedNamespaceEqualTo(), clang::DeclarationName::isIdentifier(), and clang::DeclContext::isTranslationUnit().

Referenced by hasOptionalClassName(), and isFullyQualifiedNamespaceEqualTo().

◆ isNegLit()

constexpr bool clang::dataflow::isNegLit ( Literal L )

inlineconstexpr

Returns whether L is a negative literal.

Definition at line 58 of file CNFFormula.h.

◆ isPosLit()

constexpr bool clang::dataflow::isPosLit ( Literal L )

inlineconstexpr

Returns whether L is a positive literal.

Definition at line 55 of file CNFFormula.h.

◆ isSupportedOptionalType()

static bool clang::dataflow::isSupportedOptionalType ( QualType Ty )

static

Definition at line 108 of file UncheckedOptionalAccessModel.cpp.

References clang::Type::getAsCXXRecordDecl(), getOptionalBaseClass(), and clang::Optional.

◆ joinDistinctValues()

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

static

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

Joining generally produces a single value that (soundly) approximates the two inputs, although the actual meaning depends on Model.

Definition at line 122 of file DataflowEnvironment.cpp.

References clang::dataflow::Environment::arena(), clang::dataflow::Environment::assume(), clang::dataflow::Environment::createValue(), clang::dataflow::Environment::getFlowConditionToken(), clang::dataflow::Environment::ValueModel::join(), and clang::dataflow::Arena::makeAtomRef().

Referenced by clang::dataflow::Environment::joinValues().

◆ joinExprMaps()

template<typename MapT >

static MapT clang::dataflow::joinExprMaps	(	const MapT &	Map1,
		const MapT &	Map2
	)

static

Definition at line 68 of file DataflowEnvironment.cpp.

References clang::Result.

Referenced by clang::dataflow::Environment::join().

◆ joinLocToVal()

static llvm::MapVector< const StorageLocation , Value > clang::dataflow::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

Definition at line 236 of file DataflowEnvironment.cpp.

References clang::dataflow::Environment::joinValues(), Loc, and clang::Result.

Referenced by clang::dataflow::Environment::join().

◆ makeLoggerFromCommandLine()

static std::unique_ptr< Logger > clang::dataflow::makeLoggerFromCommandLine ( )

static

Definition at line 313 of file DataflowAnalysisContext.cpp.

References DataflowLog(), clang::File, and makeLoggerFromCommandLine().

Referenced by makeLoggerFromCommandLine().

◆ maybeUnpackLValueExpr()

static Value * clang::dataflow::maybeUnpackLValueExpr	(	const Expr &	E,
		Environment &	Env
	)

static

Definition at line 92 of file Transfer.cpp.

References E, Env, clang::dataflow::Environment::getStorageLocation(), clang::dataflow::Environment::getValue(), Loc, clang::dataflow::Environment::setValue(), and unpackValue().

◆ negLit()

constexpr Literal clang::dataflow::negLit ( Variable V )

inlineconstexpr

Returns the negative literal !V.

Definition at line 52 of file CNFFormula.h.

References V.

Referenced by buildCNF().

◆ notLit()

constexpr Literal clang::dataflow::notLit ( Literal L )

inlineconstexpr

Returns the negated literal !L.

Definition at line 61 of file CNFFormula.h.

◆ operator<<() [1/8]

llvm::raw_ostream & clang::dataflow::operator<<	(	llvm::raw_ostream &	OS,
		const Solver::Result &	R
	)

Definition at line 64 of file DebugSupport.cpp.

References debugString(), clang::dataflow::Solver::Result::getSolution(), and clang::dataflow::Solver::Result::getStatus().

◆ operator<<() [2/8]

llvm::raw_ostream & clang::dataflow::operator<<	(	llvm::raw_ostream &	OS,
		Solver::Result::Assignment	Assignment
	)

Definition at line 41 of file DebugSupport.cpp.

References clang::dataflow::Solver::Result::AssignedFalse, and clang::dataflow::Solver::Result::AssignedTrue.

◆ operator<<() [3/8]

llvm::raw_ostream & clang::dataflow::operator<<	(	llvm::raw_ostream &	OS,
		Atom	A
	)

inline

Definition at line 125 of file Formula.h.

◆ operator<<() [4/8]

llvm::raw_ostream & clang::dataflow::operator<<	(	llvm::raw_ostream &	OS,
		const Formula &	F
	)

inline

Definition at line 128 of file Formula.h.

References clang::dataflow::Formula::print().

◆ operator<<() [5/8]

raw_ostream & clang::dataflow::operator<<	(	raw_ostream &	OS,
		const Value &	Val
	)

Definition at line 43 of file Value.cpp.

References clang::dataflow::Value::AtomicBool, clang::dataflow::Value::FormulaBool, clang::dataflow::Value::getKind(), clang::dataflow::Value::Integer, clang::dataflow::Value::Pointer, and clang::dataflow::Value::TopBool.

◆ operator<<() [6/8]

template<typename Key , typename ElementLattice >

std::ostream & clang::dataflow::operator<<	(	std::ostream &	Os,
		const clang::dataflow::MapLattice< Key, ElementLattice > &	M
	)

Definition at line 115 of file MapLattice.h.

References E.

◆ operator<<() [7/8]

template<typename ElementLattice >

std::ostream & clang::dataflow::operator<<	(	std::ostream &	Os,
		const clang::dataflow::VarMapLattice< ElementLattice > &	M
	)

Definition at line 128 of file MapLattice.h.

References E.

◆ operator<<() [8/8]

std::ostream & clang::dataflow::operator<<	(	std::ostream &	OS,
		const NoopLattice &
	)

inline

Definition at line 36 of file NoopLattice.h.

◆ posLit()

constexpr Literal clang::dataflow::posLit ( Variable V )

inlineconstexpr

Returns the positive literal V.

Definition at line 49 of file CNFFormula.h.

References V.

Referenced by buildCNF().

◆ printAtomList()

static void clang::dataflow::printAtomList	(	const llvm::SmallVector< Atom > &	Atoms,
		llvm::raw_ostream &	OS
	)

static

Definition at line 243 of file DataflowAnalysisContext.cpp.

References printAtomList().

Referenced by clang::dataflow::DataflowAnalysisContext::dumpFlowCondition(), and printAtomList().

◆ projectToLeaders()

static llvm::DenseSet< Atom > clang::dataflow::projectToLeaders	(	const llvm::DenseSet< Atom > &	Atoms,
		llvm::EquivalenceClasses< Atom > &	EquivalentAtoms
	)

static

Definition at line 53 of file SimplifyConstraints.cpp.

References clang::Result.

Referenced by simplifyConstraints().

◆ propagateStorageLocation()

static void clang::dataflow::propagateStorageLocation	(	const Expr &	From,
		const Expr &	To,
		Environment &	Env
	)

static

Definition at line 116 of file Transfer.cpp.

References Env, clang::dataflow::Environment::getStorageLocation(), Loc, and clang::dataflow::Environment::setStorageLocation().

Referenced by propagateValueOrStorageLocation().

◆ propagateValue()

static void clang::dataflow::propagateValue	(	const Expr &	From,
		const Expr &	To,
		Environment &	Env
	)

static

Definition at line 109 of file Transfer.cpp.

References Env, clang::Expr::getType(), clang::dataflow::Environment::getValue(), clang::Type::isRecordType(), and clang::dataflow::Environment::setValue().

Referenced by propagateValueOrStorageLocation().

◆ propagateValueOrStorageLocation()

static void clang::dataflow::propagateValueOrStorageLocation	(	const Expr &	From,
		const Expr &	To,
		Environment &	Env
	)

static

Definition at line 125 of file Transfer.cpp.

References Env, clang::Expr::isGLValue(), propagateStorageLocation(), and propagateValue().

◆ recordsEqual() [1/2]

bool clang::dataflow::recordsEqual	(	const RecordStorageLocation &	Loc1,
		const Environment &	Env1,
		const RecordStorageLocation &	Loc2,
		const Environment &	Env2
	)

Returns whether the records Loc1 and Loc2 are equal.

Values for Loc1 are retrieved from Env1, and values for Loc2 are retrieved from Env2. A convenience overload retrieves values for Loc1 and Loc2 from the same environment.

This performs a deep comparison, i.e. it compares every field (including synthetic fields) and recurses on fields of record type. Fields of reference type compare equal if they refer to the same storage location.

Note on how to interpret the result:

If this returns true, the records are guaranteed to be equal at runtime.
If this returns false, the records may still be equal at runtime; our analysis merely cannot guarantee that they will be equal.

Requirements:

Src and Dst must have the same canonical unqualified type.

Definition at line 88 of file RecordOps.cpp.

References clang::dataflow::RecordStorageLocation::children(), clang::QualType::getCanonicalType(), clang::dataflow::RecordStorageLocation::getChild(), clang::dataflow::RecordStorageLocation::getSyntheticField(), clang::dataflow::StorageLocation::getType(), clang::QualType::getUnqualifiedType(), clang::dataflow::Environment::getValue(), recordsEqual(), and clang::dataflow::RecordStorageLocation::synthetic_fields().

Referenced by recordsEqual().

◆ recordsEqual() [2/2]

bool clang::dataflow::recordsEqual	(	const RecordStorageLocation &	Loc1,
		const RecordStorageLocation &	Loc2,
		const Environment &	Env
	)

inline

Definition at line 63 of file RecordOps.h.

References Env, and recordsEqual().

◆ runDataflowAnalysis()

template<typename AnalysisT >

llvm::Expected< std::vector< std::optional< DataflowAnalysisState< typename AnalysisT::Lattice > > > > clang::dataflow::runDataflowAnalysis	(	const AdornedCFG &	ACFG,
		AnalysisT &	Analysis,
		const Environment &	InitEnv,
		CFGEltCallbacks< AnalysisT >	PostAnalysisCallbacks = `{}`,
		std::int32_t	MaxBlockVisits = `kDefaultMaxBlockVisits`
	)

Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states that model the respective basic blocks.

The returned vector, if any, will have the same size as the number of CFG blocks, with indices corresponding to basic block IDs. Returns an error if the dataflow analysis cannot be performed successfully. Otherwise, calls PostAnalysisCallbacks on each CFG element with the final analysis results before and after that program point.

MaxBlockVisits caps the number of block visits during analysis. See runTypeErasedDataflowAnalysis for a full description. The default value is essentially arbitrary – large enough to accommodate what seems like any reasonable CFG, but still small enough to limit the cost of hitting the limit.

Definition at line 234 of file DataflowAnalysis.h.

◆ runTypeErasedDataflowAnalysis()

llvm::Expected< std::vector< std::optional< TypeErasedDataflowAnalysisState > > > clang::dataflow::runTypeErasedDataflowAnalysis	(	const AdornedCFG &	ACFG,
		TypeErasedDataflowAnalysis &	Analysis,
		const Environment &	InitEnv,
		const CFGEltCallbacksTypeErased &	PostAnalysisCallbacks,
		std::int32_t	MaxBlockVisits
	)

Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states that model the respective basic blocks.

Indices of the returned vector correspond to basic block IDs. Returns an error if the dataflow analysis cannot be performed successfully. Otherwise, calls PostAnalysisCallbacks on each CFG element with the final analysis results before and after that program point.

MaxBlockVisits caps the number of block visits during analysis. It doesn't distinguish between repeat visits to the same block and visits to distinct blocks. This parameter is a backstop to prevent infinite loops, in the case of bugs in the lattice and/or transfer functions that prevent the analysis from converging.

Definition at line 489 of file TypeErasedDataflowAnalysis.cpp.

References ACFG, clang::dataflow::CFGEltCallbacksTypeErased::After, Analysis, clang::dataflow::CFGEltCallbacksTypeErased::Before, Block, BlockStates, clang::DataflowWorklistBase< Comp, QueueSize >::dequeue(), clang::dataflow::Environment::dump(), clang::ForwardDataflowWorklist::enqueueSuccessors(), clang::dataflow::TypeErasedDataflowAnalysisState::Env, clang::dataflow::Environment::fork(), clang::CFGBlock::getBlockID(), clang::CFG::getEntry(), InitEnv, isBackedgeNode(), clang::dataflow::TypeErasedDataflowAnalysisState::Lattice, runTypeErasedDataflowAnalysis(), clang::CFG::size(), transferCFGBlock(), and clang::dataflow::Environment::widen().

Referenced by diagnoseFunction(), and runTypeErasedDataflowAnalysis().

◆ sigil()

static llvm::StringLiteral clang::dataflow::sigil ( Formula::Kind K )

static

Definition at line 39 of file Formula.cpp.

References clang::dataflow::Formula::And, clang::dataflow::Formula::AtomRef, clang::dataflow::Formula::Equal, clang::dataflow::Formula::Implies, clang::dataflow::Formula::Literal, clang::dataflow::Formula::Not, and clang::dataflow::Formula::Or.

Referenced by clang::dataflow::Formula::print().

◆ simplifyConstraints()

void clang::dataflow::simplifyConstraints	(	llvm::SetVector< const Formula * > &	Constraints,
		Arena &	arena,
		SimplifyConstraintsInfo *	Info = `nullptr`
	)

Simplifies a set of constraints (implicitly connected by "and") in a way that does not change satisfiability of the constraints.

This does not mean that the set of solutions is the same before and after simplification. Info, if non-null, will be populated with information about the simplifications that were made to the formula (e.g. to display to the user).

Definition at line 75 of file SimplifyConstraints.cpp.

References clang::dataflow::Formula::And, clang::dataflow::Formula::AtomRef, atomsInEquivalenceClass(), clang::dataflow::Formula::Equal, clang::dataflow::SimplifyConstraintsInfo::EquivalentAtoms, clang::dataflow::SimplifyConstraintsInfo::FalseAtoms, clang::dataflow::Formula::isLiteral(), clang::dataflow::Formula::kind(), clang::dataflow::Arena::makeAtomRef(), clang::dataflow::Arena::makeLiteral(), clang::dataflow::Formula::Not, clang::dataflow::Formula::operands(), projectToLeaders(), substitute(), and clang::dataflow::SimplifyConstraintsInfo::TrueAtoms.

Referenced by clang::dataflow::DataflowAnalysisContext::dumpFlowCondition().

◆ substitute()

static const Formula & clang::dataflow::substitute	(	const Formula &	F,
		const llvm::DenseMap< Atom, const Formula * > &	Substitutions,
		Arena &	arena
	)

static

◆ transfer()

void clang::dataflow::transfer	(	const StmtToEnvMap &	StmtToEnv,
		const Stmt &	S,
		Environment &	Env,
		Environment::ValueModel &	Model
	)

Evaluates S and updates Env accordingly.

Requirements:

S must not be ParenExpr or ExprWithCleanups.

Definition at line 890 of file Transfer.cpp.

References Env.

Referenced by builtinTransferStatement(), and clang::dataflow::DataflowAnalysis< Derived, LatticeT >::transferTypeErased().

◆ transferCFGBlock()

static TypeErasedDataflowAnalysisState clang::dataflow::transferCFGBlock	(	const CFGBlock &	Block,
		AnalysisContext &	AC,
		const CFGEltCallbacksTypeErased &	PostAnalysisCallbacks = `{}`
	)

static

Transfers State by evaluating each element in the Block based on the AC.Analysis specified.

Built-in transfer functions (if the option for ApplyBuiltinTransfer is set by the analysis) will be applied to the element before evaluation by the user-specified analysis. PostVisitCFG (if provided) will be applied to the element after evaluation by the user-specified analysis.

Definition at line 429 of file TypeErasedDataflowAnalysis.cpp.

References transferCFGBlock().

Referenced by runTypeErasedDataflowAnalysis(), and transferCFGBlock().

◆ unpackValue()

static BoolValue & clang::dataflow::unpackValue	(	BoolValue &	V,
		Environment &	Env
	)

static

Definition at line 81 of file Transfer.cpp.

References clang::dataflow::DataflowAnalysisContext::arena(), Env, clang::dataflow::Environment::getDataflowAnalysisContext(), clang::dataflow::Arena::makeBoolValue(), and V.

Referenced by maybeUnpackLValueExpr().

◆ var()

constexpr Variable clang::dataflow::var ( Literal L )

inlineconstexpr

Returns the variable of L.

Definition at line 64 of file CNFFormula.h.

◆ widenDistinctValues()

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

static

Definition at line 162 of file DataflowEnvironment.cpp.

References clang::dataflow::Environment::arena(), Changed, equateUnknownValues(), clang::dataflow::Environment::getBoolLiteralValue(), clang::dataflow::Value::getKind(), clang::dataflow::Arena::makeNot(), clang::dataflow::Environment::makeTopBoolValue(), clang::dataflow::Environment::proves(), clang::Result, Unchanged, and clang::dataflow::Environment::ValueModel::widen().

Referenced by widenKeyToValueMap().

◆ widenKeyToValueMap()

template<typename Key >

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

static

Definition at line 266 of file DataflowEnvironment.cpp.

References areEquivalentValues(), Changed, and widenDistinctValues().

Referenced by clang::dataflow::Environment::widen().

Variable Documentation

◆ kDefaultMaxBlockVisits

constexpr std::int32_t clang::dataflow::kDefaultMaxBlockVisits = 20'000

inlineconstexpr

Default for the maximum number of block visits during analysis.

Definition at line 216 of file DataflowAnalysis.h.

◆ kDefaultMaxSATIterations

constexpr std::int64_t clang::dataflow::kDefaultMaxSATIterations = 1'000'000'000

inlineconstexpr

Default for the maximum number of SAT solver iterations during analysis.

Definition at line 213 of file DataflowAnalysis.h.

◆ MaxCompositeValueDepth

constexpr int clang::dataflow::MaxCompositeValueDepth = 3

staticconstexpr

Definition at line 46 of file DataflowEnvironment.cpp.

◆ MaxCompositeValueSize

constexpr int clang::dataflow::MaxCompositeValueSize = 1000

staticconstexpr

Definition at line 47 of file DataflowEnvironment.cpp.

Referenced by clang::dataflow::Environment::createValue(), and clang::dataflow::Environment::initializeFieldsWithValues().

◆ NullClause

constexpr ClauseID clang::dataflow::NullClause = 0

constexpr

A null clause identifier is used as a placeholder in various data structures and algorithms.

Definition at line 46 of file CNFFormula.h.

◆ NullLit

constexpr Literal clang::dataflow::NullLit = 0

constexpr

A null literal is used as a placeholder in various data structures and algorithms.

Definition at line 39 of file CNFFormula.h.

Referenced by clang::dataflow::CNFFormula::addClause().

◆ NullVar

constexpr Variable clang::dataflow::NullVar = 0

constexpr

A null boolean variable is used as a placeholder in various data structures and algorithms.

Definition at line 29 of file CNFFormula.h.

Namespaces

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

◆ ASTMatchSwitch

◆ CFGEltCallback

◆ CFGEltCallbackTypeErased

◆ CFGMatchSwitch

◆ ClauseID

◆ DiagnosisCallback

◆ FieldSet

◆ LatticeJoinEffect

◆ Literal

◆ MatchSwitchAction

◆ MatchSwitchMatcher

◆ UncheckedOptionalAccessLattice

◆ Variable

◆ VarMapLattice

Enumeration Type Documentation

◆ Atom

◆ ComparisonResult

◆ LatticeEffect

Function Documentation

◆ areEquivalentIndirectionValues()

◆ areEquivalentValues()

◆ atomsInEquivalenceClass()

◆ blockIndexInPredecessor()

◆ buildCNF()

◆ buildContainsExprConsumedInDifferentBlock()

◆ buildStmtToBasicBlockMap()

◆ builtinTransfer()

◆ builtinTransferInitializer()

◆ builtinTransferStatement()

◆ cached()

◆ canonicalFormulaPair()

◆ compareDistinctValues()

◆ compareKeyToValueMaps()

◆ computeBlockInputState()

◆ containsSameFields()

◆ copyField()

◆ copyRecord()

◆ copySyntheticField()

◆ createAnalysis()

◆ debugString() [1/2]

◆ debugString() [2/2]

◆ diagnoseFunction() [1/2]

◆ diagnoseFunction() [2/2]

◆ equateUnknownValues()

◆ evaluateBooleanEquality()

◆ findReachableBlocks()

◆ getBaseObjectLocation()

◆ getFieldsForInitListExpr()

◆ getFieldsFromClassHierarchy()

◆ getImplicitObjectLocation()

◆ getKeys()

◆ getMemberForAccessor()

◆ getObjectFields()

◆ getOptionalBaseClass()

◆ getReferencedDecls() [1/2]

◆ getReferencedDecls() [2/2]

◆ getTerminatorCondition()

◆ hasOptionalClassName()

◆ ignoreCFGOmittedNodes() [1/2]

◆ ignoreCFGOmittedNodes() [2/2]

◆ insertIfFunction()

◆ insertIfGlobal()

◆ insertIfLocal()

◆ intersectDeclToLoc()

◆ isBackedgeNode()

◆ isCheckLikeMethod()

◆ isFullyQualifiedNamespaceEqualTo()

◆ isNegLit()

◆ isPosLit()

◆ isSupportedOptionalType()

◆ joinDistinctValues()

◆ joinExprMaps()