1 //===-- Arena.cpp ---------------------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
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"
15 namespace clang::dataflow
{
17 static std::pair
<const Formula
*, const Formula
*>
18 canonicalFormulaPair(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
);
25 template <class Key
, class ComputeFunc
>
26 static const Formula
&cached(llvm::DenseMap
<Key
, const Formula
*> &Cache
, Key K
,
27 ComputeFunc
&&Compute
) {
28 auto [It
, Inserted
] = Cache
.try_emplace(std::forward
<Key
>(K
));
30 It
->second
= Compute();
34 const Formula
&Arena::makeAtomRef(Atom A
) {
35 return cached(AtomRefs
, A
, [&] {
36 return &Formula::create(Alloc
, Formula::AtomRef
, {},
37 static_cast<unsigned>(A
));
41 const Formula
&Arena::makeAnd(const Formula
&LHS
, const Formula
&RHS
) {
42 return cached(Ands
, canonicalFormulaPair(LHS
, RHS
), [&] {
45 if (LHS
.kind() == Formula::Literal
)
46 return LHS
.literal() ? &RHS
: &LHS
;
47 if (RHS
.kind() == Formula::Literal
)
48 return RHS
.literal() ? &LHS
: &RHS
;
50 return &Formula::create(Alloc
, Formula::And
, {&LHS
, &RHS
});
54 const Formula
&Arena::makeOr(const Formula
&LHS
, const Formula
&RHS
) {
55 return cached(Ors
, canonicalFormulaPair(LHS
, RHS
), [&] {
58 if (LHS
.kind() == Formula::Literal
)
59 return LHS
.literal() ? &LHS
: &RHS
;
60 if (RHS
.kind() == Formula::Literal
)
61 return RHS
.literal() ? &RHS
: &LHS
;
63 return &Formula::create(Alloc
, Formula::Or
, {&LHS
, &RHS
});
67 const 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());
74 return &Formula::create(Alloc
, Formula::Not
, {&Val
});
78 const Formula
&Arena::makeImplies(const Formula
&LHS
, const Formula
&RHS
) {
79 return cached(Implies
, std::make_pair(&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
);
87 return &Formula::create(Alloc
, Formula::Implies
, {&LHS
, &RHS
});
91 const Formula
&Arena::makeEquals(const Formula
&LHS
, const Formula
&RHS
) {
92 return cached(Equals
, canonicalFormulaPair(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
);
100 return &Formula::create(Alloc
, Formula::Equal
, {&LHS
, &RHS
});
104 IntegerValue
&Arena::makeIntLiteral(llvm::APInt Value
) {
105 auto [It
, Inserted
] = IntegerLiterals
.try_emplace(Value
, nullptr);
108 It
->second
= &create
<IntegerValue
>();
112 BoolValue
&Arena::makeBoolValue(const Formula
&F
) {
113 auto [It
, Inserted
] = FormulaValues
.try_emplace(&F
);
115 It
->second
= (F
.kind() == Formula::AtomRef
)
116 ? (BoolValue
*)&create
<AtomicBoolValue
>(F
)
117 : &create
<FormulaBoolValue
>(F
);
122 const Formula
*parse(Arena
&A
, llvm::StringRef
&In
) {
123 auto EatSpaces
= [&] { In
= In
.ltrim(' '); };
126 if (In
.consume_front("!")) {
127 if (auto *Arg
= parse(A
, In
))
128 return &A
.makeNot(*Arg
);
132 if (In
.consume_front("(")) {
133 auto *Arg1
= parse(A
, In
);
138 decltype(&Arena::makeOr
) Op
;
139 if (In
.consume_front("|"))
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
;
150 auto *Arg2
= parse(A
, In
);
155 if (!In
.consume_front(")"))
158 return &(A
.*Op
)(*Arg1
, *Arg2
);
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
))
167 return &A
.makeAtomRef(static_cast<Atom
>(At
));
170 if (In
.consume_front("true"))
171 return &A
.makeLiteral(true);
172 if (In
.consume_front("false"))
173 return &A
.makeLiteral(false);
178 class FormulaParseError
: public llvm::ErrorInfo
<FormulaParseError
> {
184 FormulaParseError(llvm::StringRef Formula
, unsigned Offset
)
185 : Formula(Formula
), Offset(Offset
) {}
187 void log(raw_ostream
&OS
) const override
{
188 OS
<< "bad formula at offset " << Offset
<< "\n";
189 OS
<< Formula
<< "\n";
190 OS
.indent(Offset
) << "^";
193 std::error_code
convertToErrorCode() const override
{
194 return std::make_error_code(std::errc::invalid_argument
);
198 char FormulaParseError::ID
= 0;
202 llvm::Expected
<const Formula
&> Arena::parseFormula(llvm::StringRef In
) {
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());
208 if (!Rest
.empty()) // parse didn't consume all the input
209 return llvm::make_error
<FormulaParseError
>(In
, In
.size() - Rest
.size());
213 } // namespace clang::dataflow