================ @@ -0,0 +1,207 @@ +//===- AnalysisDriver.cpp -------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisDriver.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/AnalysisRegistry.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/DerivedAnalysis.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Analysis/SummaryAnalysis.h" +#include "clang/ScalableStaticAnalysisFramework/Core/Support/ErrorBuilder.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/ErrorHandling.h" +#include <map> +#include <vector> + +using namespace clang; +using namespace ssaf; + +AnalysisDriver::AnalysisDriver(std::unique_ptr<LUSummary> LU) + : LU(std::move(LU)) {} + +llvm::Expected<std::vector<std::unique_ptr<AnalysisBase>>> +AnalysisDriver::sort(llvm::ArrayRef<AnalysisName> Roots) { + struct Visitor { + enum class State { Unvisited, Visiting, Visited }; + + std::map<AnalysisName, State> Marks; + std::vector<AnalysisName> Path; + std::vector<std::unique_ptr<AnalysisBase>> Result; + + std::string formatCycle(const AnalysisName &CycleEntry) const { + auto CycleBegin = llvm::find(Path, CycleEntry); + std::string Cycle; + llvm::raw_string_ostream OS(Cycle); + llvm::interleave(llvm::make_range(CycleBegin, Path.end()), OS, " -> "); + OS << " -> " << CycleEntry; + return Cycle; + } + + llvm::Error visit(const AnalysisName &Name) { + auto It = Marks.find(Name); + switch (It != Marks.end() ? It->second : State::Unvisited) { + case State::Visited: + return llvm::Error::success(); + + case State::Visiting: + return ErrorBuilder::create(std::errc::invalid_argument, + "cycle detected: {0}", formatCycle(Name)) + .build(); + + case State::Unvisited: { + Marks[Name] = State::Visiting; + Path.push_back(Name); + + auto V = AnalysisRegistry::instantiate(Name.str()); + if (!V) { + Path.pop_back(); + return V.takeError(); + } + + auto Analysis = std::move(*V); + for (const auto &Dep : Analysis->dependencyNames()) { + if (auto Err = visit(Dep)) { + Path.pop_back(); + return Err; + } + } + + Marks[Name] = State::Visited; + Path.pop_back(); + Result.push_back(std::move(Analysis)); + return llvm::Error::success(); + } + } + llvm_unreachable("unhandled State"); + } + }; + + Visitor V; + for (const auto &Root : Roots) { + if (auto Err = V.visit(Root)) { + return std::move(Err); + } + } + return std::move(V.Result); +} + +llvm::Error AnalysisDriver::executeSummaryAnalysis( + std::unique_ptr<SummaryAnalysisBase> Summary, WPASuite &Suite) { + SummaryName SN = Summary->summaryName(); + auto DataIt = LU->Data.find(SN); + if (DataIt == LU->Data.end()) { + return ErrorBuilder::create(std::errc::invalid_argument, + "no data for analysis '{0}' in LUSummary", + Summary->analysisName()) + .build(); + } + + if (auto Err = Summary->initialize()) { + return Err; + } + + for (auto &[Id, EntitySummary] : DataIt->second) { + if (auto Err = Summary->add(Id, *EntitySummary)) { + return Err; + } + } + + if (auto Err = Summary->finalize()) { + return Err; + } + + AnalysisName Name = Summary->analysisName(); + Suite.Data.emplace(Name, std::move(*Summary).result()); + + return llvm::Error::success(); +} + +llvm::Error AnalysisDriver::executeDerivedAnalysis( + std::unique_ptr<DerivedAnalysisBase> Derived, WPASuite &Suite) { + std::map<AnalysisName, const AnalysisResult *> DepMap; + + for (const auto &DepName : Derived->dependencyNames()) { + auto It = Suite.Data.find(DepName); + if (It == Suite.Data.end()) { + ErrorBuilder::fatal("missing dependency '{0}' for analysis '{1}': " + "dependency graph is not topologically sorted", + DepName, Derived->analysisName()); + } + DepMap[DepName] = It->second.get(); + } + + if (auto Err = Derived->initialize(DepMap)) { + return Err; + } + + while (true) { ---------------- aviralg wrote:
Note that we insist on iteration for the `DerivedAnalysis::step` method. We could also opt for a one-shot execution of a `DerivedAnalysis::run` method where the analysis author can decide to do the iteration internally. So why force iteration? It's because any real static analysis is doing some iteration. There is either fix point iteration, iteration on all the constraints, or iteration on all the objects. This design bakes in the iteration so the analysis author only writes the code for a single step, and, explicitly expresses the iteration condition for return. The rare single-pass analysis will just return false after a fixed amount of work. https://github.com/llvm/llvm-project/pull/186813 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
