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/ScalableStaticAnalysisFramework/Core/WholeProgramAnalysis/AnalysisDriver.h"
10#include "clang/ScalableStaticAnalysisFramework/Core/Support/ErrorBuilder.h"
11#include "clang/ScalableStaticAnalysisFramework/Core/WholeProgramAnalysis/AnalysisRegistry.h"
12#include "clang/ScalableStaticAnalysisFramework/Core/WholeProgramAnalysis/DerivedAnalysis.h"
13#include "clang/ScalableStaticAnalysisFramework/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->dependencyNames()) {
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 SummaryName SN = Summary.summaryName();
106 auto DataIt = LU->Data.find(x: SN);
107 if (DataIt == LU->Data.end()) {
108 return ErrorBuilder::create(EC: std::errc::invalid_argument,
109 Fmt: "no data for analysis '{0}' in LUSummary",
110 ArgVals: Summary.analysisName())
111 .build();
112 }
113
114 if (auto Err = Summary.initialize()) {
115 return Err;
116 }
117
118 for (auto &[Id, EntitySummary] : DataIt->second) {
119 if (auto Err = Summary.add(Id, Summary: *EntitySummary)) {
120 return Err;
121 }
122 }
123
124 if (auto Err = Summary.finalize()) {
125 return Err;
126 }
127
128 return llvm::Error::success();
129}
130
131llvm::Error AnalysisDriver::executeDerivedAnalysis(DerivedAnalysisBase &Derived,
132 WPASuite &Suite) const {
133 std::map<AnalysisName, const AnalysisResult *> DepMap;
134
135 for (const auto &DepName : Derived.dependencyNames()) {
136 auto It = Suite.Data.find(x: DepName);
137 if (It == Suite.Data.end()) {
138 ErrorBuilder::fatal(Fmt: "missing dependency '{0}' for analysis '{1}': "
139 "dependency graph is not topologically sorted",
140 ArgVals: DepName, ArgVals: Derived.analysisName());
141 }
142 DepMap[DepName] = It->second.get();
143 }
144
145 if (auto Err = Derived.initialize(DepResults: DepMap)) {
146 return Err;
147 }
148
149 while (true) {
150 auto StepOrErr = Derived.step();
151 if (!StepOrErr) {
152 return StepOrErr.takeError();
153 }
154 if (!*StepOrErr) {
155 break;
156 }
157 }
158
159 if (auto Err = Derived.finalize()) {
160 return Err;
161 }
162
163 return llvm::Error::success();
164}
165
166llvm::Expected<WPASuite> AnalysisDriver::execute(
167 EntityIdTable IdTable,
168 llvm::ArrayRef<std::unique_ptr<AnalysisBase>> Sorted) const {
169 WPASuite Suite;
170 Suite.IdTable = std::move(IdTable);
171
172 for (auto &Analysis : Sorted) {
173 switch (Analysis->TheKind) {
174 case AnalysisBase::Kind::Summary: {
175 SummaryAnalysisBase &SA = static_cast<SummaryAnalysisBase &>(*Analysis);
176 if (auto Err = executeSummaryAnalysis(Summary&: SA, Suite)) {
177 return std::move(Err);
178 }
179 break;
180 }
181 case AnalysisBase::Kind::Derived: {
182 DerivedAnalysisBase &DA = static_cast<DerivedAnalysisBase &>(*Analysis);
183 if (auto Err = executeDerivedAnalysis(Derived&: DA, Suite)) {
184 return std::move(Err);
185 }
186 break;
187 }
188 }
189 AnalysisName Name = Analysis->analysisName();
190 Suite.Data.emplace(args: std::move(Name), args: std::move(*Analysis).result());
191 }
192
193 return std::move(Suite);
194}
195
196llvm::Expected<WPASuite> AnalysisDriver::run() && {
197 auto ExpectedSorted = toposort(Roots: AnalysisRegistry::names());
198 if (!ExpectedSorted) {
199 return ExpectedSorted.takeError();
200 }
201 return execute(IdTable: std::move(LU->IdTable), Sorted: *ExpectedSorted);
202}
203
204llvm::Expected<WPASuite>
205AnalysisDriver::run(llvm::ArrayRef<AnalysisName> Names) const {
206 auto ExpectedSorted = toposort(Roots: Names);
207 if (!ExpectedSorted) {
208 return ExpectedSorted.takeError();
209 }
210
211 return execute(IdTable: LU->IdTable, Sorted: *ExpectedSorted);
212}
213