1//===- AnalysisDriver.cpp -------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/AnalysisDriver.h"
10#include "clang/ScalableStaticAnalysis/Core/Support/ErrorBuilder.h"
11#include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/AnalysisRegistry.h"
12#include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/DerivedAnalysis.h"
13#include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/SummaryAnalysis.h"
14#include "llvm/ADT/STLExtras.h"
15#include "llvm/Support/Error.h"
16#include "llvm/Support/ErrorHandling.h"
17#include <map>
18#include <vector>
19
20using namespace clang;
21using namespace ssaf;
22
23AnalysisDriver::AnalysisDriver(std::unique_ptr<LUSummary> LU)
24 : LU(std::move(LU)) {}
25
26llvm::Expected<std::vector<std::unique_ptr<AnalysisBase>>>
27AnalysisDriver::toposort(llvm::ArrayRef<AnalysisName> Roots) {
28 struct Visitor {
29 enum class State { Unvisited, Visiting, Visited };
30
31 std::map<AnalysisName, State> Marks;
32 std::vector<AnalysisName> Path;
33 std::vector<std::unique_ptr<AnalysisBase>> Result;
34
35 explicit Visitor(size_t N) {
36 Path.reserve(n: N);
37 Result.reserve(n: N);
38 }
39
40 std::string formatCycle(const AnalysisName &CycleEntry) const {
41 auto CycleBegin = llvm::find(Range: Path, Val: CycleEntry);
42 std::string Cycle;
43 llvm::raw_string_ostream OS(Cycle);
44 llvm::interleave(c: llvm::make_range(x: CycleBegin, y: Path.end()), os&: OS, separator: " -> ");
45 OS << " -> " << CycleEntry;
46 return Cycle;
47 }
48
49 llvm::Error visit(const AnalysisName &Name) {
50 auto [It, _] = Marks.emplace(args: Name, args: State::Unvisited);
51
52 switch (It->second) {
53 case State::Visited:
54 return llvm::Error::success();
55
56 case State::Visiting:
57 return ErrorBuilder::create(EC: std::errc::invalid_argument,
58 Fmt: "cycle detected: {0}", ArgVals: formatCycle(CycleEntry: Name))
59 .build();
60
61 case State::Unvisited: {
62 It->second = State::Visiting;
63 Path.push_back(x: Name);
64
65 llvm::Expected<std::unique_ptr<AnalysisBase>> V =
66 AnalysisRegistry::instantiate(Name);
67 if (!V) {
68 return V.takeError();
69 }
70
71 // Unwrap for convenience to avoid the noise of dereferencing an
72 // Expected on every subsequent access.
73 std::unique_ptr<AnalysisBase> Analysis = std::move(*V);
74
75 for (const auto &Dep : Analysis->getDependencyNames()) {
76 if (auto Err = visit(Name: Dep)) {
77 return Err;
78 }
79 }
80
81 // std::map iterators are not invalidated by insertions, so It remains
82 // valid after recursive visit() calls that insert new entries.
83 It->second = State::Visited;
84 Path.pop_back();
85 Result.push_back(x: std::move(Analysis));
86
87 return llvm::Error::success();
88 }
89 }
90 llvm_unreachable("unhandled State");
91 }
92 };
93
94 Visitor V(Roots.size());
95 for (const auto &Root : Roots) {
96 if (auto Err = V.visit(Name: Root)) {
97 return std::move(Err);
98 }
99 }
100 return std::move(V.Result);
101}
102
103llvm::Error AnalysisDriver::executeSummaryAnalysis(SummaryAnalysisBase &Summary,
104 WPASuite &Suite) const {
105 if (auto Err = Summary.initialize())
106 return Err;
107
108 auto DataIt = LU->Data.find(x: Summary.getSummaryName());
109 if (DataIt != LU->Data.end()) {
110 for (auto &[Id, EntitySummary] : DataIt->second)
111 if (auto Err = Summary.add(Id, Summary: *EntitySummary))
112 return Err;
113 }
114 return Summary.finalize();
115}
116
117llvm::Error AnalysisDriver::executeDerivedAnalysis(DerivedAnalysisBase &Derived,
118 WPASuite &Suite) const {
119 std::map<AnalysisName, const AnalysisResult *> DepMap;
120
121 for (const auto &DepName : Derived.getDependencyNames()) {
122 auto It = Suite.Data.find(x: DepName);
123 if (It == Suite.Data.end()) {
124 ErrorBuilder::fatal(Fmt: "missing dependency '{0}' for analysis '{1}': "
125 "dependency graph is not topologically sorted",
126 ArgVals: DepName, ArgVals: Derived.getAnalysisName());
127 }
128 DepMap[DepName] = It->second.get();
129 }
130
131 if (auto Err = Derived.initialize(DepResults: DepMap)) {
132 return Err;
133 }
134
135 while (true) {
136 auto StepOrErr = Derived.step();
137 if (!StepOrErr) {
138 return StepOrErr.takeError();
139 }
140 if (!*StepOrErr) {
141 break;
142 }
143 }
144
145 if (auto Err = Derived.finalize()) {
146 return Err;
147 }
148
149 return llvm::Error::success();
150}
151
152llvm::Expected<WPASuite> AnalysisDriver::execute(
153 EntityIdTable IdTable,
154 llvm::ArrayRef<std::unique_ptr<AnalysisBase>> Sorted) const {
155 WPASuite Suite;
156 Suite.IdTable = std::move(IdTable);
157
158 for (auto &Analysis : Sorted) {
159 switch (Analysis->TheKind) {
160 case AnalysisBase::Kind::Summary: {
161 SummaryAnalysisBase &SA = static_cast<SummaryAnalysisBase &>(*Analysis);
162 if (auto Err = executeSummaryAnalysis(Summary&: SA, Suite)) {
163 return std::move(Err);
164 }
165 break;
166 }
167 case AnalysisBase::Kind::Derived: {
168 DerivedAnalysisBase &DA = static_cast<DerivedAnalysisBase &>(*Analysis);
169 if (auto Err = executeDerivedAnalysis(Derived&: DA, Suite)) {
170 return std::move(Err);
171 }
172 break;
173 }
174 }
175 AnalysisName Name = Analysis->getAnalysisName();
176 Suite.Data.emplace(args: std::move(Name), args: std::move(*Analysis).takeResult());
177 }
178
179 return std::move(Suite);
180}
181
182llvm::Expected<WPASuite> AnalysisDriver::run() && {
183 auto ExpectedSorted = toposort(Roots: AnalysisRegistry::names());
184 if (!ExpectedSorted) {
185 return ExpectedSorted.takeError();
186 }
187 return execute(IdTable: std::move(LU->IdTable), Sorted: *ExpectedSorted);
188}
189
190llvm::Expected<WPASuite>
191AnalysisDriver::run(llvm::ArrayRef<AnalysisName> Names) const {
192 auto ExpectedSorted = toposort(Roots: Names);
193 if (!ExpectedSorted) {
194 return ExpectedSorted.takeError();
195 }
196
197 return execute(IdTable: LU->IdTable, Sorted: *ExpectedSorted);
198}
199