DataflowAnalysis.h Source File (original) (raw)

14#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H

15#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H

17#include

18#include

19#include <type_traits>

20#include

21#include

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

32#include "llvm/ADT/STLFunctionalExtras.h"

33#include "llvm/ADT/SmallVector.h"

34#include "llvm/Support/Errc.h"

35#include "llvm/Support/Error.h"

38namespace dataflow {

79template <typename Derived, typename LatticeT>

81public:

94 return {static_cast<Derived *>(this)->initialElement()};

95 }

100 Lattice L1 = llvm::any_cast<const Lattice &>(E1.Value);

101 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);

102 L1.join(L2);

103 return {std::move(L1)};

104 }

105

108 Lattice &C = llvm::any_cast<Lattice &>(Current.Value);

109 const Lattice &P = llvm::any_cast<const Lattice &>(Previous.Value);

110 return widenInternal(Rank0{}, C, P);

111 }

112

115 const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);

116 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);

117 return L1 == L2;

118 }

119

122 Lattice &L = llvm::any_cast<Lattice &>(E.Value);

123 static_cast<Derived *>(this)->transfer(Element, L, Env);

124 }

125

128 transferBranchInternal(Rank0{}, *static_cast<Derived *>(this), Branch, Stmt,

130 }

131

132private:

133

134

135 struct Rank1 {};

136 struct Rank0 : Rank1 {};

137

138

139 template

140 static auto widenInternal(Rank0, T &Current, const T &Prev)

141 -> decltype(Current.widen(Prev)) {

142 return Current.widen(Prev);

143 }

144

145

146

147

152 }

153

154

155 template

156 static auto transferBranchInternal(Rank0, Analysis &A, bool Branch,

157 const Stmt *Stmt, TypeErasedLattice &L,

158 Environment &Env)

159 -> std::void_t<decltype(A.transferBranch(

160 Branch, Stmt, std::declval<LatticeT &>(), Env))> {

161 A.transferBranch(Branch, Stmt, llvm::any_cast<Lattice &>(L.Value), Env);

162 }

163

164

165 template

166 static void transferBranchInternal(Rank1, Analysis &A, bool, const Stmt *,

167 TypeErasedLattice &, Environment &) {}

168

169 ASTContext &Context;

170};

171

172

174

176

177

179};

180

181

182

183template

187

188

189

190

194};

195

196

197

198

199template <typename AnalysisT, typename Diagnostic>

203

204

205

206

210};

211

212

214

215

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231template

233 std::optional<DataflowAnalysisState>>>

238 CFGEltCallbacksTypeErased TypeErasedCallbacks;

239 if (PostAnalysisCallbacks.Before) {

240 TypeErasedCallbacks.Before =

241 [&PostAnalysisCallbacks](const CFGElement &Element,

242 const TypeErasedDataflowAnalysisState &State) {

243 auto *Lattice =

244 llvm::any_cast(&State.Lattice.Value);

245

246

247 PostAnalysisCallbacks.Before(

248 Element, DataflowAnalysisState{

249 *Lattice, State.Env.fork()});

250 };

251 }

252 if (PostAnalysisCallbacks.After) {

253 TypeErasedCallbacks.After =

254 [&PostAnalysisCallbacks](const CFGElement &Element,

255 const TypeErasedDataflowAnalysisState &State) {

256 auto *Lattice =

257 llvm::any_cast(&State.Lattice.Value);

258

259

260 PostAnalysisCallbacks.After(

261 Element, DataflowAnalysisState{

262 *Lattice, State.Env.fork()});

263 };

264 }

265

267 ACFG, Analysis, InitEnv, TypeErasedCallbacks, MaxBlockVisits);

268 if (!TypeErasedBlockStates)

269 return TypeErasedBlockStates.takeError();

270

271 std::vector<std::optional<DataflowAnalysisState>>

273 BlockStates.reserve(TypeErasedBlockStates->size());

274

275 llvm::transform(

276 std::move(*TypeErasedBlockStates), std::back_inserter(BlockStates),

277 [](auto &OptState) {

278 return llvm::transformOptional(

279 std::move(OptState), [](TypeErasedDataflowAnalysisState &&State) {

280 return DataflowAnalysisState{

281 llvm::any_cast(

282 std::move(State.Lattice.Value)),

283 std::move(State.Env)};

284 });

285 });

287}

288

289

290

291

292

293

294template

296 -> decltype(AnalysisT(ASTCtx, Env)) {

297 return AnalysisT(ASTCtx, Env);

298}

299template

301 -> decltype(AnalysisT(ASTCtx)) {

302 return AnalysisT(ASTCtx);

303}

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320template <typename AnalysisT, typename Diagnostic>

327 if (!Context)

328 return Context.takeError();

329

330 auto Solver = std::make_unique(MaxSATIterations);

333 AnalysisT Analysis = createAnalysis(ASTCtx, Env);

336 if (Diagnoser.Before) {

337 PostAnalysisCallbacks.Before =

338 [&ASTCtx, &Diagnoser,

341 auto EltDiagnostics = Diagnoser.Before(

342 Elt, ASTCtx,

344 llvm::any_cast<const typename AnalysisT::Lattice &>(

345 State.Lattice.Value),

346 State.Env));

347 llvm::move(EltDiagnostics, std::back_inserter(Diagnostics));

348 };

349 }

350 if (Diagnoser.After) {

351 PostAnalysisCallbacks.After =

352 [&ASTCtx, &Diagnoser,

355 auto EltDiagnostics = Diagnoser.After(

356 Elt, ASTCtx,

358 llvm::any_cast<const typename AnalysisT::Lattice &>(

359 State.Lattice.Value),

360 State.Env));

361 llvm::move(EltDiagnostics, std::back_inserter(Diagnostics));

362 };

363 }

364 if (llvm::Error Err =

366 PostAnalysisCallbacks, MaxBlockVisits)

367 .takeError())

368 return std::move(Err);

369

371 return llvm::createStringError(llvm::errc::interrupted,

372 "SAT solver timed out");

373

374 return Diagnostics;

375}

376

377

378

379

380

381template <typename AnalysisT, typename Diagnostic>

388 return diagnoseFunction(FuncDecl, ASTCtx, Callbacks, MaxSATIterations,

389 MaxBlockVisits);

390}

391

392

393

394

396public:

397

399};

400

401}

402}

403

404#endif

Defines the clang::ASTContext interface.

llvm::ArrayRef< std::optional< TypeErasedDataflowAnalysisState > > BlockStates

Stores the state of a CFG block if it has been evaluated by the analysis.

const Environment & InitEnv

Initial state to start the analysis.

TypeErasedDataflowAnalysis & Analysis

The analysis to be run.

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

Represents a top-level expression in a basic block.

Represents a function declaration or definition.

Stmt - This represents one statement.

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

static llvm::Expected< AdornedCFG > build(const FunctionDecl &Func)

Builds an AdornedCFG from a FunctionDecl.

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

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

LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current, const TypeErasedLattice &Previous) final

Chooses a lattice element that approximates the current element at a program point,...

ASTContext & getASTContext() final

Returns the ASTContext that is used by the analysis.

DataflowAnalysis(ASTContext &Context, DataflowAnalysisOptions Options)

bool isEqualTypeErased(const TypeErasedLattice &E1, const TypeErasedLattice &E2) final

Returns true if and only if the two given type-erased lattice elements are equal.

DataflowAnalysis(ASTContext &Context)

TypeErasedLattice joinTypeErased(const TypeErasedLattice &E1, const TypeErasedLattice &E2) final

Joins two type-erased lattice elements by computing their least upper bound.

void transferBranchTypeErased(bool Branch, const Stmt *Stmt, TypeErasedLattice &E, Environment &Env) final

Applies the analysis transfer function for a given edge from a CFG block of a conditional statement.

TypeErasedLattice typeErasedInitialElement() final

Returns a type-erased lattice element that models the initial state of a basic block.

LatticeT Lattice

Bounded join-semilattice that is used in the analysis.

void transferTypeErased(const CFGElement &Element, TypeErasedLattice &E, Environment &Env) final

Applies the analysis transfer function for a given control flow graph element and type-erased lattice...

Abstract base class for dataflow "models": reusable analysis components that model a particular aspec...

virtual bool transfer(const CFGElement &Element, Environment &Env)=0

Return value indicates whether the model processed the Element.

Supplements Environment with non-standard comparison and join operations.

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

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

virtual bool reachedLimit() const =0

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

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

Evaluates S and updates Env accordingly.

llvm::function_ref< llvm::SmallVector< Diagnostic >(const CFGElement &, ASTContext &, const TransferStateForDiagnostics< typename AnalysisT::Lattice > &)> DiagnosisCallback

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

constexpr std::int32_t kDefaultMaxBlockVisits

Default for the maximum number of block visits during analysis.

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

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.

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

std::function< void(const CFGElement &, const DataflowAnalysisState< typename AnalysisT::Lattice > &)> CFGEltCallback

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

LatticeEffect LatticeJoinEffect

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

LatticeEffect

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

constexpr std::int64_t kDefaultMaxSATIterations

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

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

const FunctionProtoType * T

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

CFGEltCallbackTypeErased Before

CFGEltCallbackTypeErased After

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

CFGEltCallback< AnalysisT > After

CFGEltCallback< AnalysisT > Before

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

DiagnosisCallback< AnalysisT, Diagnostic > Before

DiagnosisCallback< AnalysisT, Diagnostic > After

A read-only version of TransferState.

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

Type-erased lattice element container.