clang 20.0.0git
Arena.cpp
Go to the documentation of this file.
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
12#include "llvm/Support/Error.h"
13#include <string>
14
15namespace clang::dataflow {
16
17static std::pair<const Formula *, const Formula *>
18canonicalFormulaPair(const Formula &LHS, const Formula &RHS) {
19 auto Res = std::make_pair(&LHS, &RHS);
20 if (&RHS < &LHS) // FIXME: use a deterministic order instead
21 std::swap(Res.first, Res.second);
22 return Res;
23}
24
25template <class Key, class ComputeFunc>
26const Formula &cached(llvm::DenseMap<Key, const Formula *> &Cache, Key K,
27 ComputeFunc &&Compute) {
28 auto [It, Inserted] = Cache.try_emplace(std::forward<Key>(K));
29 if (Inserted)
30 It->second = Compute();
31 return *It->second;
32}
33
35 return cached(AtomRefs, A, [&] {
36 return &Formula::create(Alloc, Formula::AtomRef, {},
37 static_cast<unsigned>(A));
38 });
39}
40
41const Formula &Arena::makeAnd(const Formula &LHS, const Formula &RHS) {
42 return cached(Ands, canonicalFormulaPair(LHS, RHS), [&] {
43 if (&LHS == &RHS)
44 return &LHS;
45 if (LHS.kind() == Formula::Literal)
46 return LHS.literal() ? &RHS : &LHS;
47 if (RHS.kind() == Formula::Literal)
48 return RHS.literal() ? &LHS : &RHS;
49
50 return &Formula::create(Alloc, Formula::And, {&LHS, &RHS});
51 });
52}
53
54const Formula &Arena::makeOr(const Formula &LHS, const Formula &RHS) {
55 return cached(Ors, canonicalFormulaPair(LHS, RHS), [&] {
56 if (&LHS == &RHS)
57 return &LHS;
58 if (LHS.kind() == Formula::Literal)
59 return LHS.literal() ? &LHS : &RHS;
60 if (RHS.kind() == Formula::Literal)
61 return RHS.literal() ? &RHS : &LHS;
62
63 return &Formula::create(Alloc, Formula::Or, {&LHS, &RHS});
64 });
65}
66
67const Formula &Arena::makeNot(const Formula &Val) {
68 return cached(Nots, &Val, [&] {
69 if (Val.kind() == Formula::Not)
70 return Val.operands()[0];
71 if (Val.kind() == Formula::Literal)
72 return &makeLiteral(!Val.literal());
73
74 return &Formula::create(Alloc, Formula::Not, {&Val});
75 });
76}
77
78const Formula &Arena::makeImplies(const Formula &LHS, const Formula &RHS) {
79 return cached(Implies, std::make_pair(&LHS, &RHS), [&] {
80 if (&LHS == &RHS)
81 return &makeLiteral(true);
82 if (LHS.kind() == Formula::Literal)
83 return LHS.literal() ? &RHS : &makeLiteral(true);
84 if (RHS.kind() == Formula::Literal)
85 return RHS.literal() ? &RHS : &makeNot(LHS);
86
87 return &Formula::create(Alloc, Formula::Implies, {&LHS, &RHS});
88 });
89}
90
91const Formula &Arena::makeEquals(const Formula &LHS, const Formula &RHS) {
92 return cached(Equals, canonicalFormulaPair(LHS, RHS), [&] {
93 if (&LHS == &RHS)
94 return &makeLiteral(true);
95 if (LHS.kind() == Formula::Literal)
96 return LHS.literal() ? &RHS : &makeNot(RHS);
97 if (RHS.kind() == Formula::Literal)
98 return RHS.literal() ? &LHS : &makeNot(LHS);
99
100 return &Formula::create(Alloc, Formula::Equal, {&LHS, &RHS});
101 });
102}
103
105 auto [It, Inserted] = IntegerLiterals.try_emplace(Value, nullptr);
106
107 if (Inserted)
108 It->second = &create<IntegerValue>();
109 return *It->second;
110}
111
113 auto [It, Inserted] = FormulaValues.try_emplace(&F);
114 if (Inserted)
115 It->second = (F.kind() == Formula::AtomRef)
116 ? (BoolValue *)&create<AtomicBoolValue>(F)
117 : &create<FormulaBoolValue>(F);
118 return *It->second;
119}
120
121namespace {
122const Formula *parse(Arena &A, llvm::StringRef &In) {
123 auto EatSpaces = [&] { In = In.ltrim(' '); };
124 EatSpaces();
125
126 if (In.consume_front("!")) {
127 if (auto *Arg = parse(A, In))
128 return &A.makeNot(*Arg);
129 return nullptr;
130 }
131
132 if (In.consume_front("(")) {
133 auto *Arg1 = parse(A, In);
134 if (!Arg1)
135 return nullptr;
136
137 EatSpaces();
138 decltype(&Arena::makeOr) Op;
139 if (In.consume_front("|"))
140 Op = &Arena::makeOr;
141 else if (In.consume_front("&"))
142 Op = &Arena::makeAnd;
143 else if (In.consume_front("=>"))
144 Op = &Arena::makeImplies;
145 else if (In.consume_front("="))
146 Op = &Arena::makeEquals;
147 else
148 return nullptr;
149
150 auto *Arg2 = parse(A, In);
151 if (!Arg2)
152 return nullptr;
153
154 EatSpaces();
155 if (!In.consume_front(")"))
156 return nullptr;
157
158 return &(A.*Op)(*Arg1, *Arg2);
159 }
160
161 // For now, only support unnamed variables V0, V1 etc.
162 // FIXME: parse e.g. "X" by allocating an atom and storing a name somewhere.
163 if (In.consume_front("V")) {
164 std::underlying_type_t<Atom> At;
165 if (In.consumeInteger(10, At))
166 return nullptr;
167 return &A.makeAtomRef(static_cast<Atom>(At));
168 }
169
170 if (In.consume_front("true"))
171 return &A.makeLiteral(true);
172 if (In.consume_front("false"))
173 return &A.makeLiteral(false);
174
175 return nullptr;
176}
177
178class FormulaParseError : public llvm::ErrorInfo<FormulaParseError> {
179 std::string Formula;
180 unsigned Offset;
181
182public:
183 static char ID;
184 FormulaParseError(llvm::StringRef Formula, unsigned Offset)
185 : Formula(Formula), Offset(Offset) {}
186
187 void log(raw_ostream &OS) const override {
188 OS << "bad formula at offset " << Offset << "\n";
189 OS << Formula << "\n";
190 OS.indent(Offset) << "^";
191 }
192
193 std::error_code convertToErrorCode() const override {
194 return std::make_error_code(std::errc::invalid_argument);
195 }
196};
197
198char FormulaParseError::ID = 0;
199
200} // namespace
201
203 llvm::StringRef Rest = In;
204 auto *Result = parse(*this, Rest);
205 if (!Result) // parse() hit something unparseable
206 return llvm::make_error<FormulaParseError>(In, In.size() - Rest.size());
207 Rest = Rest.ltrim();
208 if (!Rest.empty()) // parse didn't consume all the input
209 return llvm::make_error<FormulaParseError>(In, In.size() - Rest.size());
210 return *Result;
211}
212
213} // namespace clang::dataflow
TypePropertyCache< Private > Cache
Definition: Type.cpp:4483
The Arena owns the objects that model data within an analysis.
Definition: Arena.h:21
const Formula & makeEquals(const Formula &LHS, const Formula &RHS)
Returns a formula for LHS <=> RHS.
Definition: Arena.cpp:91
const Formula & makeAtomRef(Atom A)
Returns a formula for the variable A.
Definition: Arena.cpp:34
IntegerValue & makeIntLiteral(llvm::APInt Value)
Returns a symbolic integer value that models an integer literal equal to Value.
Definition: Arena.cpp:104
const Formula & makeNot(const Formula &Val)
Returns a formula for the negation of Val.
Definition: Arena.cpp:67
const Formula & makeOr(const Formula &LHS, const Formula &RHS)
Returns a formula for the disjunction of LHS and RHS.
Definition: Arena.cpp:54
BoolValue & makeBoolValue(const Formula &)
Creates a BoolValue wrapping a particular formula.
Definition: Arena.cpp:112
const Formula & makeAnd(const Formula &LHS, const Formula &RHS)
Returns a formula for the conjunction of LHS and RHS.
Definition: Arena.cpp:41
const Formula & makeImplies(const Formula &LHS, const Formula &RHS)
Returns a formula for LHS => RHS.
Definition: Arena.cpp:78
const Formula & makeLiteral(bool Value)
Returns a formula for a literal true/false.
Definition: Arena.h:111
llvm::Expected< const Formula & > parseFormula(llvm::StringRef)
Definition: Arena.cpp:202
Models a boolean.
Definition: Value.h:94
ArrayRef< const Formula * > operands() const
Definition: Formula.h:82
@ Equal
True if LHS is false or RHS is true.
Definition: Formula.h:64
@ Implies
True if either LHS or RHS is true.
Definition: Formula.h:63
@ AtomRef
A reference to an atomic boolean variable.
Definition: Formula.h:54
@ Literal
Constant true or false.
Definition: Formula.h:56
@ Or
True if LHS and RHS are both true.
Definition: Formula.h:62
@ And
True if its only operand is false.
Definition: Formula.h:61
static const Formula & create(llvm::BumpPtrAllocator &Alloc, Kind K, ArrayRef< const Formula * > Operands, unsigned Value=0)
Definition: Formula.cpp:20
bool literal() const
Definition: Formula.h:73
Kind kind() const
Definition: Formula.h:66
Models an integer.
Definition: Value.h:160
Base class for all values computed by abstract interpretation.
Definition: Value.h:33
Dataflow Directional Tag Classes.
Definition: AdornedCFG.h:29
const Formula & cached(llvm::DenseMap< Key, const Formula * > &Cache, Key K, ComputeFunc &&Compute)
Definition: Arena.cpp:26
Atom
Identifies an atomic boolean variable such as "V1".
Definition: Formula.h:34
static std::pair< const Formula *, const Formula * > canonicalFormulaPair(const Formula &LHS, const Formula &RHS)
Definition: Arena.cpp:18
if(T->getSizeExpr()) TRY_TO(TraverseStmt(const_cast< Expr * >(T -> getSizeExpr())))
@ Result
The result type of a method or function.
#define log(__x)
Definition: tgmath.h:460