/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/FlowSensitive/Arena.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- Arena.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/Analysis/FlowSensitive/Arena.h" |
10 | | #include "clang/Analysis/FlowSensitive/Formula.h" |
11 | | #include "clang/Analysis/FlowSensitive/Value.h" |
12 | | #include "llvm/Support/Error.h" |
13 | | #include <string> |
14 | | |
15 | | namespace clang::dataflow { |
16 | | |
17 | | static std::pair<const Formula *, const Formula *> |
18 | 10.9k | canonicalFormulaPair(const Formula &LHS, const Formula &RHS) { |
19 | 10.9k | auto Res = std::make_pair(&LHS, &RHS); |
20 | 10.9k | if (&RHS < &LHS) // FIXME: use a deterministic order instead |
21 | 7.76k | std::swap(Res.first, Res.second); |
22 | 10.9k | return Res; |
23 | 10.9k | } |
24 | | |
25 | 22.8k | const Formula &Arena::makeAtomRef(Atom A) { |
26 | 22.8k | auto [It, Inserted] = AtomRefs.try_emplace(A); |
27 | 22.8k | if (Inserted) |
28 | 7.65k | It->second = |
29 | 7.65k | &Formula::create(Alloc, Formula::AtomRef, {}, static_cast<unsigned>(A)); |
30 | 22.8k | return *It->second; |
31 | 22.8k | } |
32 | | |
33 | 2.91k | const Formula &Arena::makeAnd(const Formula &LHS, const Formula &RHS) { |
34 | 2.91k | if (&LHS == &RHS) |
35 | 2 | return LHS; |
36 | | |
37 | 2.91k | auto [It, Inserted] = |
38 | 2.91k | Ands.try_emplace(canonicalFormulaPair(LHS, RHS), nullptr); |
39 | 2.91k | if (Inserted) |
40 | 2.13k | It->second = &Formula::create(Alloc, Formula::And, {&LHS, &RHS}); |
41 | 2.91k | return *It->second; |
42 | 2.91k | } |
43 | | |
44 | 1.38k | const Formula &Arena::makeOr(const Formula &LHS, const Formula &RHS) { |
45 | 1.38k | if (&LHS == &RHS) |
46 | 2 | return LHS; |
47 | | |
48 | 1.38k | auto [It, Inserted] = |
49 | 1.38k | Ors.try_emplace(canonicalFormulaPair(LHS, RHS), nullptr); |
50 | 1.38k | if (Inserted) |
51 | 1.15k | It->second = &Formula::create(Alloc, Formula::Or, {&LHS, &RHS}); |
52 | 1.38k | return *It->second; |
53 | 1.38k | } |
54 | | |
55 | 4.19k | const Formula &Arena::makeNot(const Formula &Val) { |
56 | 4.19k | auto [It, Inserted] = Nots.try_emplace(&Val, nullptr); |
57 | 4.19k | if (Inserted) |
58 | 1.87k | It->second = &Formula::create(Alloc, Formula::Not, {&Val}); |
59 | 4.19k | return *It->second; |
60 | 4.19k | } |
61 | | |
62 | 428 | const Formula &Arena::makeImplies(const Formula &LHS, const Formula &RHS) { |
63 | 428 | if (&LHS == &RHS) |
64 | 1 | return makeLiteral(true); |
65 | | |
66 | 427 | auto [It, Inserted] = |
67 | 427 | Implies.try_emplace(std::make_pair(&LHS, &RHS), nullptr); |
68 | 427 | if (Inserted) |
69 | 369 | It->second = &Formula::create(Alloc, Formula::Implies, {&LHS, &RHS}); |
70 | 427 | return *It->second; |
71 | 428 | } |
72 | | |
73 | 6.63k | const Formula &Arena::makeEquals(const Formula &LHS, const Formula &RHS) { |
74 | 6.63k | if (&LHS == &RHS) |
75 | 7 | return makeLiteral(true); |
76 | | |
77 | 6.62k | auto [It, Inserted] = |
78 | 6.62k | Equals.try_emplace(canonicalFormulaPair(LHS, RHS), nullptr); |
79 | 6.62k | if (Inserted) |
80 | 2.76k | It->second = &Formula::create(Alloc, Formula::Equal, {&LHS, &RHS}); |
81 | 6.62k | return *It->second; |
82 | 6.63k | } |
83 | | |
84 | 882 | IntegerValue &Arena::makeIntLiteral(llvm::APInt Value) { |
85 | 882 | auto [It, Inserted] = IntegerLiterals.try_emplace(Value, nullptr); |
86 | | |
87 | 882 | if (Inserted) |
88 | 333 | It->second = &create<IntegerValue>(); |
89 | 882 | return *It->second; |
90 | 882 | } |
91 | | |
92 | 3.97k | BoolValue &Arena::makeBoolValue(const Formula &F) { |
93 | 3.97k | auto [It, Inserted] = FormulaValues.try_emplace(&F); |
94 | 3.97k | if (Inserted) |
95 | 2.74k | It->second = (F.kind() == Formula::AtomRef) |
96 | 2.74k | ? (BoolValue *)&create<AtomicBoolValue>(F)2.03k |
97 | 2.74k | : &create<FormulaBoolValue>(F)708 ; |
98 | 3.97k | return *It->second; |
99 | 3.97k | } |
100 | | |
101 | | namespace { |
102 | 109 | const Formula *parse(Arena &A, llvm::StringRef &In) { |
103 | 170 | auto EatSpaces = [&] { In = In.ltrim(' '); }; |
104 | 109 | EatSpaces(); |
105 | | |
106 | 109 | if (In.consume_front("!")) { |
107 | 20 | if (auto *Arg = parse(A, In)) |
108 | 20 | return &A.makeNot(*Arg); |
109 | 0 | return nullptr; |
110 | 20 | } |
111 | | |
112 | 89 | if (In.consume_front("(")) { |
113 | 31 | auto *Arg1 = parse(A, In); |
114 | 31 | if (!Arg1) |
115 | 0 | return nullptr; |
116 | | |
117 | 31 | EatSpaces(); |
118 | 31 | decltype(&Arena::makeOr) Op; |
119 | 31 | if (In.consume_front("|")) |
120 | 7 | Op = &Arena::makeOr; |
121 | 24 | else if (In.consume_front("&")) |
122 | 9 | Op = &Arena::makeAnd; |
123 | 15 | else if (In.consume_front("=>")) |
124 | 5 | Op = &Arena::makeImplies; |
125 | 10 | else if (In.consume_front("=")) |
126 | 10 | Op = &Arena::makeEquals; |
127 | 0 | else |
128 | 0 | return nullptr; |
129 | | |
130 | 31 | auto *Arg2 = parse(A, In); |
131 | 31 | if (!Arg2) |
132 | 1 | return nullptr; |
133 | | |
134 | 30 | EatSpaces(); |
135 | 30 | if (!In.consume_front(")")) |
136 | 0 | return nullptr; |
137 | | |
138 | 30 | return &(A.*Op)(*Arg1, *Arg2); |
139 | 30 | } |
140 | | |
141 | | // For now, only support unnamed variables V0, V1 etc. |
142 | | // FIXME: parse e.g. "X" by allocating an atom and storing a name somewhere. |
143 | 58 | if (In.consume_front("V")) { |
144 | 54 | std::underlying_type_t<Atom> At; |
145 | 54 | if (In.consumeInteger(10, At)) |
146 | 0 | return nullptr; |
147 | 54 | return &A.makeAtomRef(static_cast<Atom>(At)); |
148 | 54 | } |
149 | | |
150 | 4 | if (In.consume_front("true")) |
151 | 1 | return &A.makeLiteral(true); |
152 | 3 | if (In.consume_front("false")) |
153 | 2 | return &A.makeLiteral(false); |
154 | | |
155 | 1 | return nullptr; |
156 | 3 | } |
157 | | |
158 | | class FormulaParseError : public llvm::ErrorInfo<FormulaParseError> { |
159 | | std::string Formula; |
160 | | unsigned Offset; |
161 | | |
162 | | public: |
163 | | static char ID; |
164 | | FormulaParseError(llvm::StringRef Formula, unsigned Offset) |
165 | 2 | : Formula(Formula), Offset(Offset) {} |
166 | | |
167 | 2 | void log(raw_ostream &OS) const override { |
168 | 2 | OS << "bad formula at offset " << Offset << "\n"; |
169 | 2 | OS << Formula << "\n"; |
170 | 2 | OS.indent(Offset) << "^"; |
171 | 2 | } |
172 | | |
173 | 0 | std::error_code convertToErrorCode() const override { |
174 | 0 | return std::make_error_code(std::errc::invalid_argument); |
175 | 0 | } |
176 | | }; |
177 | | |
178 | | char FormulaParseError::ID = 0; |
179 | | |
180 | | } // namespace |
181 | | |
182 | 27 | llvm::Expected<const Formula &> Arena::parseFormula(llvm::StringRef In) { |
183 | 27 | llvm::StringRef Rest = In; |
184 | 27 | auto *Result = parse(*this, Rest); |
185 | 27 | if (!Result) // parse() hit something unparseable |
186 | 1 | return llvm::make_error<FormulaParseError>(In, In.size() - Rest.size()); |
187 | 26 | Rest = Rest.ltrim(); |
188 | 26 | if (!Rest.empty()) // parse didn't consume all the input |
189 | 1 | return llvm::make_error<FormulaParseError>(In, In.size() - Rest.size()); |
190 | 25 | return *Result; |
191 | 26 | } |
192 | | |
193 | | } // namespace clang::dataflow |