diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h @@ -93,10 +93,29 @@ return L1 == L2; } - void transferTypeErased(const Stmt *Stmt, TypeErasedLattice &E, + /// Deprecated. Use the `transfer` function overload applied on `CFGElement`. + /// + /// Transfer function for statements in the code being analysed. + virtual void transfer(const Stmt *Stmt, Lattice &L, Environment &Env) {} + + /// Transfer function for elements in the control flow graph built from the + /// code being analysed. + virtual void transfer(const CFGElement *Element, Lattice &L, + Environment &Env) {} + + // FIXME: Use CRTP pattern and remove virtual transfer functions after users + // have been updated to implement transfer. + // (e.g. static_cast(this)->transfer(Element, L, Env)) + void transferTypeErased(const CFGElement *Element, TypeErasedLattice &E, Environment &Env) final { Lattice &L = llvm::any_cast(E.Value); - static_cast(this)->transfer(Stmt, L, Env); + transfer(Element, L, Env); + + // FIXME: Remove after users have been updated to implement the `transfer` + // overload applied on `CFGElement`. + if (auto Stmt = Element->getAs()) { + transfer(Stmt->getStmt(), L, Env); + } } private: @@ -112,37 +131,41 @@ Environment Env; }; +// FIXME: Rename to `runDataflowAnalysis` after usages of the overload that +// applies to `CFGStmt` have been replaced. +// /// 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 -/// `PostVisitStmt` on each statement with the final analysis results at that +/// `PostVisitCFG` on each CFG element with the final analysis results at that /// program point. template llvm::Expected>>> -runDataflowAnalysis( +runDataflowAnalysisOnCFG( const ControlFlowContext &CFCtx, AnalysisT &Analysis, const Environment &InitEnv, - std::function &)> - PostVisitStmt = nullptr) { - std::function - PostVisitStmtClosure = nullptr; - if (PostVisitStmt != nullptr) { - PostVisitStmtClosure = [&PostVisitStmt]( - const CFGStmt &Stmt, - const TypeErasedDataflowAnalysisState &State) { + std::function &)> + PostVisitCFG = nullptr) { + std::function + PostVisitCFGClosure = nullptr; + if (PostVisitCFG) { + PostVisitCFGClosure = [&PostVisitCFG]( + const CFGElement &Element, + const TypeErasedDataflowAnalysisState &State) { auto *Lattice = llvm::any_cast(&State.Lattice.Value); - PostVisitStmt(Stmt, DataflowAnalysisState{ - *Lattice, State.Env}); + PostVisitCFG(Element, DataflowAnalysisState{ + *Lattice, State.Env}); }; } auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis( - CFCtx, Analysis, InitEnv, PostVisitStmtClosure); + CFCtx, Analysis, InitEnv, PostVisitCFGClosure); if (!TypeErasedBlockStates) return TypeErasedBlockStates.takeError(); @@ -163,6 +186,41 @@ return BlockStates; } +/// Deprecated. Use `runDataflowAnalysisOnCFG` instead. +/// +/// 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 +/// `PostVisitStmt` on each statement with the final analysis results at that +/// program point. +template +llvm::Expected>>> +runDataflowAnalysis( + const ControlFlowContext &CFCtx, AnalysisT &Analysis, + const Environment &InitEnv, + std::function &)> + PostVisitStmt = nullptr) { + std::function &)> + PostVisitCFG = nullptr; + if (PostVisitStmt) { + PostVisitCFG = + [&PostVisitStmt]( + const CFGElement &Element, + const DataflowAnalysisState &State) { + if (auto Stmt = Element.getAs()) { + PostVisitStmt(*Stmt, State); + } + }; + } + return runDataflowAnalysisOnCFG(CFCtx, Analysis, InitEnv, PostVisitCFG); +} + /// Abstract base class for dataflow "models": reusable analysis components that /// model a particular aspect of program semantics in the `Environment`. For /// example, a model may capture a type and its related functions. diff --git a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h --- a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h @@ -79,9 +79,9 @@ virtual bool isEqualTypeErased(const TypeErasedLattice &, const TypeErasedLattice &) = 0; - /// Applies the analysis transfer function for a given statement and - /// type-erased lattice element. - virtual void transferTypeErased(const Stmt *, TypeErasedLattice &, + /// Applies the analysis transfer function for a given control flow graph + /// element and type-erased lattice element. + virtual void transferTypeErased(const CFGElement *, TypeErasedLattice &, Environment &) = 0; /// If the built-in transfer functions (which model the heap and stack in the @@ -104,10 +104,10 @@ : Lattice(std::move(Lattice)), Env(std::move(Env)) {} }; -/// Transfers the state of a basic block by evaluating each of its statements in +/// Transfers the state of a basic block by evaluating each of its elements in /// the context of `Analysis` and the states of its predecessors that are -/// available in `BlockStates`. `HandleTransferredStmt` (if provided) will be -/// applied to each statement in the block, after it is evaluated. +/// available in `BlockStates`. `PostVisitCFG` (if provided) will be applied to +/// each element in the block, after it is evaluated. /// /// Requirements: /// @@ -119,23 +119,23 @@ llvm::ArrayRef> BlockStates, const CFGBlock &Block, const Environment &InitEnv, TypeErasedDataflowAnalysis &Analysis, - std::function - HandleTransferredStmt = nullptr); + PostVisitCFG = nullptr); /// 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 -/// `PostVisitStmt` on each statement with the final analysis results at that +/// `PostVisitCFG` on each CFG element with the final analysis results at that /// program point. llvm::Expected>> runTypeErasedDataflowAnalysis( const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv, - std::function - PostVisitStmt = nullptr); + PostVisitCFG = nullptr); } // namespace dataflow } // namespace clang diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -154,19 +154,37 @@ TransferOptions TransferOpts; }; +/// Holds data structures required for running dataflow analysis. +struct AnalysisContext { + AnalysisContext( + const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, + const Environment &InitEnv, + llvm::ArrayRef> + BlockStates) + : CFCtx(CFCtx), Analysis(Analysis), InitEnv(InitEnv), + BlockStates(BlockStates) {} + + /// Contains the CFG being analyzed. + const ControlFlowContext &CFCtx; + /// The analysis to be run. + TypeErasedDataflowAnalysis &Analysis; + /// Initial state to start the analysis. + const Environment &InitEnv; + /// Stores the state of a CFG block if it has been evaluated by the analysis. + /// The indices correspond to the block IDs. + llvm::ArrayRef> BlockStates; +}; + /// 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 `BlockStates` that are set to +/// already been transferred. States in `AC.BlockStates` that are set to /// `llvm::None` represent basic blocks that are not evaluated yet. -static TypeErasedDataflowAnalysisState computeBlockInputState( - const ControlFlowContext &CFCtx, - llvm::ArrayRef> BlockStates, - const CFGBlock &Block, const Environment &InitEnv, - TypeErasedDataflowAnalysis &Analysis) { +static TypeErasedDataflowAnalysisState +computeBlockInputState(const CFGBlock &Block, AnalysisContext &AC) { llvm::DenseSet Preds; Preds.insert(Block.pred_begin(), Block.pred_end()); if (Block.getTerminator().isTemporaryDtorsBranch()) { @@ -193,13 +211,16 @@ // // See `NoreturnDestructorTest` for concrete examples. if (Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) { - auto StmtBlock = CFCtx.getStmtToBlock().find(Block.getTerminatorStmt()); - assert(StmtBlock != CFCtx.getStmtToBlock().end()); + auto &StmtToBlock = AC.CFCtx.getStmtToBlock(); + auto StmtBlock = StmtToBlock.find(Block.getTerminatorStmt()); + assert(StmtBlock != StmtToBlock.end()); Preds.erase(StmtBlock->getSecond()); } } llvm::Optional MaybeState; + + auto &Analysis = AC.Analysis; auto BuiltinTransferOpts = Analysis.builtinTransferOptions(); for (const CFGBlock *Pred : Preds) { @@ -210,14 +231,14 @@ // Skip if `Pred` was not evaluated yet. This could happen if `Pred` has a // loop back edge to `Block`. const llvm::Optional &MaybePredState = - BlockStates[Pred->getBlockID()]; + AC.BlockStates[Pred->getBlockID()]; if (!MaybePredState) continue; TypeErasedDataflowAnalysisState PredState = MaybePredState.value(); if (BuiltinTransferOpts) { if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) { - const StmtToEnvMapImpl StmtToEnv(CFCtx, BlockStates); + const StmtToEnvMapImpl StmtToEnv(AC.CFCtx, AC.BlockStates); TerminatorVisitor(StmtToEnv, PredState.Env, blockIndexInPredecessor(*Pred, Block), *BuiltinTransferOpts) @@ -236,107 +257,125 @@ // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()` // to enable building analyses like computation of dominators that // initialize the state of each basic block differently. - MaybeState.emplace(Analysis.typeErasedInitialElement(), InitEnv); + MaybeState.emplace(Analysis.typeErasedInitialElement(), AC.InitEnv); } return *MaybeState; } -/// Transfers `State` by evaluating `CfgStmt` in the context of `Analysis`. -/// `HandleTransferredStmt` (if provided) will be applied to `CfgStmt`, after it -/// is evaluated. -static void transferCFGStmt( - const ControlFlowContext &CFCtx, - llvm::ArrayRef> BlockStates, - const CFGStmt &CfgStmt, TypeErasedDataflowAnalysis &Analysis, - TypeErasedDataflowAnalysisState &State, - std::function - HandleTransferredStmt) { - const Stmt *S = CfgStmt.getStmt(); +/// Built-in transfer function for `CFGStmt`. +void builtinTransferStatement(const CFGStmt &Elt, + TypeErasedDataflowAnalysisState &InputState, + AnalysisContext &AC) { + const Stmt *S = Elt.getStmt(); assert(S != nullptr); - - auto BuiltinTransferOpts = Analysis.builtinTransferOptions(); - if (BuiltinTransferOpts) - transfer(StmtToEnvMapImpl(CFCtx, BlockStates), *S, State.Env, - *BuiltinTransferOpts); - Analysis.transferTypeErased(S, State.Lattice, State.Env); - - if (HandleTransferredStmt != nullptr) - HandleTransferredStmt(CfgStmt, State); + transfer(StmtToEnvMapImpl(AC.CFCtx, AC.BlockStates), *S, InputState.Env, + *AC.Analysis.builtinTransferOptions()); } -/// Transfers `State` by evaluating `CfgInit`. -static void transferCFGInitializer(const CFGInitializer &CfgInit, - TypeErasedDataflowAnalysisState &State) { - const auto &ThisLoc = *cast( - State.Env.getThisPointeeStorageLocation()); +/// Built-in transfer function for `CFGInitializer`. +void builtinTransferInitializer(const CFGInitializer &Elt, + TypeErasedDataflowAnalysisState &InputState) { + const CXXCtorInitializer *Init = Elt.getInitializer(); + assert(Init != nullptr); - const CXXCtorInitializer *Initializer = CfgInit.getInitializer(); - assert(Initializer != nullptr); + auto &Env = InputState.Env; + const auto &ThisLoc = + *cast(Env.getThisPointeeStorageLocation()); - const FieldDecl *Member = Initializer->getMember(); + const FieldDecl *Member = Init->getMember(); if (Member == nullptr) // Not a field initializer. return; - auto *InitStmt = Initializer->getInit(); + auto *InitStmt = Init->getInit(); assert(InitStmt != nullptr); - auto *InitStmtLoc = - State.Env.getStorageLocation(*InitStmt, SkipPast::Reference); + auto *InitStmtLoc = Env.getStorageLocation(*InitStmt, SkipPast::Reference); if (InitStmtLoc == nullptr) return; - auto *InitStmtVal = State.Env.getValue(*InitStmtLoc); + auto *InitStmtVal = Env.getValue(*InitStmtLoc); if (InitStmtVal == nullptr) return; if (Member->getType()->isReferenceType()) { auto &MemberLoc = ThisLoc.getChild(*Member); - State.Env.setValue(MemberLoc, - State.Env.takeOwnership( - std::make_unique(*InitStmtLoc))); + Env.setValue(MemberLoc, Env.takeOwnership(std::make_unique( + *InitStmtLoc))); } else { auto &MemberLoc = ThisLoc.getChild(*Member); - State.Env.setValue(MemberLoc, *InitStmtVal); + Env.setValue(MemberLoc, *InitStmtVal); + } +} + +void builtinTransfer(const CFGElement &Elt, + TypeErasedDataflowAnalysisState &State, + AnalysisContext &AC) { + switch (Elt.getKind()) { + case CFGElement::Statement: { + builtinTransferStatement(Elt.castAs(), State, AC); + break; + } + case CFGElement::Initializer: { + builtinTransferInitializer(Elt.castAs(), State); + break; + } + default: + // FIXME: Evaluate other kinds of `CFGElement`. + break; } } +/// 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. +TypeErasedDataflowAnalysisState +transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC, + std::function + PostVisitCFG = nullptr) { + auto State = computeBlockInputState(Block, AC); + for (const auto &Element : Block) { + // Built-in analysis + if (AC.Analysis.builtinTransferOptions()) { + builtinTransfer(Element, State, AC); + } + + // User-provided analysis + AC.Analysis.transferTypeErased(&Element, State.Lattice, State.Env); + + // Post processing + if (PostVisitCFG) { + PostVisitCFG(Element, State); + } + } + return State; +} + TypeErasedDataflowAnalysisState transferBlock( const ControlFlowContext &CFCtx, llvm::ArrayRef> BlockStates, const CFGBlock &Block, const Environment &InitEnv, TypeErasedDataflowAnalysis &Analysis, - std::function - HandleTransferredStmt) { - TypeErasedDataflowAnalysisState State = - computeBlockInputState(CFCtx, BlockStates, Block, InitEnv, Analysis); - for (const CFGElement &Element : Block) { - switch (Element.getKind()) { - case CFGElement::Statement: - transferCFGStmt(CFCtx, BlockStates, *Element.getAs(), Analysis, - State, HandleTransferredStmt); - break; - case CFGElement::Initializer: - if (Analysis.builtinTransferOptions()) - transferCFGInitializer(*Element.getAs(), State); - break; - default: - // FIXME: Evaluate other kinds of `CFGElement`. - break; - } - } - return State; + PostVisitCFG) { + AnalysisContext AC(CFCtx, Analysis, InitEnv, BlockStates); + return transferCFGBlock(Block, AC, PostVisitCFG); } llvm::Expected>> runTypeErasedDataflowAnalysis( const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv, - std::function - PostVisitStmt) { + PostVisitCFG) { PostOrderCFGView POV(&CFCtx.getCFG()); ForwardDataflowWorklist Worklist(CFCtx.getCFG(), &POV); @@ -349,6 +388,8 @@ InitEnv}; Worklist.enqueueSuccessors(&Entry); + AnalysisContext AC(CFCtx, Analysis, InitEnv, BlockStates); + // Bugs in lattices and transfer functions can prevent the analysis from // converging. To limit the damage (infinite loops) that these bugs can cause, // limit the number of iterations. @@ -373,7 +414,7 @@ const llvm::Optional &OldBlockState = BlockStates[Block->getBlockID()]; TypeErasedDataflowAnalysisState NewBlockState = - transferBlock(CFCtx, BlockStates, *Block, InitEnv, Analysis); + transferCFGBlock(*Block, AC); if (OldBlockState && Analysis.isEqualTypeErased(OldBlockState.value().Lattice, @@ -395,14 +436,12 @@ // FIXME: Consider evaluating unreachable basic blocks (those that have a // state set to `llvm::None` at this point) to also analyze dead code. - if (PostVisitStmt) { + if (PostVisitCFG) { for (const CFGBlock *Block : CFCtx.getCFG()) { // Skip blocks that were not evaluated. if (!BlockStates[Block->getBlockID()]) continue; - - transferBlock(CFCtx, BlockStates, *Block, InitEnv, Analysis, - PostVisitStmt); + transferCFGBlock(*Block, AC, PostVisitCFG); } } diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h --- a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h +++ b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h @@ -71,14 +71,25 @@ std::vector> &BlockStates; }; +// FIXME: Rename to `checkDataflow` after usages of the overload that applies to +// `CFGStmt` have been replaced. +// +/// Runs dataflow analysis (specified from `MakeAnalysis`) and the +/// `PostVisitCFG` function (if provided) on the body of the function that +/// matches `TargetFuncMatcher` in code snippet `Code`. `VerifyResults` checks +/// that the results from the analysis are correct. +/// +/// Requirements: +/// +/// `AnalysisT` contains a type `Lattice`. template -llvm::Error checkDataflow( +llvm::Error checkDataflowOnCFG( llvm::StringRef Code, ast_matchers::internal::Matcher TargetFuncMatcher, std::function MakeAnalysis, - std::function - PostVisitStmt, + PostVisitCFG, std::function VerifyResults, ArrayRef Args, const tooling::FileContentMappings &VirtualMappedFiles = {}) { llvm::Annotations AnnotatedCode(Code); @@ -112,13 +123,14 @@ Environment Env(DACtx, *F); auto Analysis = MakeAnalysis(Context, Env); - std::function - PostVisitStmtClosure = nullptr; - if (PostVisitStmt != nullptr) { - PostVisitStmtClosure = [&PostVisitStmt, &Context]( - const CFGStmt &Stmt, - const TypeErasedDataflowAnalysisState &State) { - PostVisitStmt(Context, Stmt, State); + std::function + PostVisitCFGClosure = nullptr; + if (PostVisitCFG) { + PostVisitCFGClosure = [&PostVisitCFG, &Context]( + const CFGElement &Element, + const TypeErasedDataflowAnalysisState &State) { + PostVisitCFG(Context, Element, State); }; } @@ -130,7 +142,7 @@ llvm::Expected>> MaybeBlockStates = runTypeErasedDataflowAnalysis(*CFCtx, Analysis, Env, - PostVisitStmtClosure); + PostVisitCFGClosure); if (!MaybeBlockStates) return MaybeBlockStates.takeError(); auto &BlockStates = *MaybeBlockStates; @@ -141,6 +153,32 @@ return llvm::Error::success(); } +template +llvm::Error checkDataflow( + llvm::StringRef Code, + ast_matchers::internal::Matcher TargetFuncMatcher, + std::function MakeAnalysis, + std::function + PostVisitStmt, + std::function VerifyResults, ArrayRef Args, + const tooling::FileContentMappings &VirtualMappedFiles = {}) { + std::function + PostVisitCFG = nullptr; + if (PostVisitStmt) { + PostVisitCFG = + [&PostVisitStmt](ASTContext &Context, const CFGElement &Element, + const TypeErasedDataflowAnalysisState &State) { + if (auto Stmt = Element.getAs()) { + PostVisitStmt(Context, *Stmt, State); + } + }; + } + return checkDataflowOnCFG(Code, TargetFuncMatcher, MakeAnalysis, PostVisitCFG, + VerifyResults, Args, VirtualMappedFiles); +} + // Runs dataflow on the body of the function that matches `TargetFuncMatcher` in // code snippet `Code`. Requires: `AnalysisT` contains a type `Lattice`. template @@ -157,9 +195,9 @@ const tooling::FileContentMappings &VirtualMappedFiles = {}) { using StateT = DataflowAnalysisState; - return checkDataflow( + return checkDataflowOnCFG( Code, std::move(TargetFuncMatcher), std::move(MakeAnalysis), - /*PostVisitStmt=*/nullptr, + /*PostVisitCFG=*/nullptr, [&VerifyResults](AnalysisData AnalysisData) { if (AnalysisData.BlockStates.empty()) { VerifyResults({}, AnalysisData.ASTCtx); @@ -180,9 +218,13 @@ AnalysisData.CFCtx, AnalysisData.BlockStates, *Block, AnalysisData.Env, AnalysisData.Analysis, [&Results, - &Annotations](const clang::CFGStmt &Stmt, + &Annotations](const clang::CFGElement &Element, const TypeErasedDataflowAnalysisState &State) { - auto It = Annotations.find(Stmt.getStmt()); + // FIXME: Extend testing annotations to non statement constructs + auto Stmt = Element.getAs(); + if (!Stmt) + return; + auto It = Annotations.find(Stmt->getStmt()); if (It == Annotations.end()) return; auto *Lattice = llvm::any_cast(