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 *>
canonicalFormulaPair(const Formula & LHS,const Formula & RHS)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);
22   return Res;
23 }
24 
25 template <class Key, class ComputeFunc>
cached(llvm::DenseMap<Key,const Formula * > & Cache,Key K,ComputeFunc && Compute)26 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));
29   if (Inserted)
30     It->second = Compute();
31   return *It->second;
32 }
33 
makeAtomRef(Atom A)34 const Formula &Arena::makeAtomRef(Atom A) {
35   return cached(AtomRefs, A, [&] {
36     return &Formula::create(Alloc, Formula::AtomRef, {},
37                             static_cast<unsigned>(A));
38   });
39 }
40 
makeAnd(const Formula & LHS,const Formula & RHS)41 const 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 
makeOr(const Formula & LHS,const Formula & RHS)54 const 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 
makeNot(const Formula & Val)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());
73 
74     return &Formula::create(Alloc, Formula::Not, {&Val});
75   });
76 }
77 
makeImplies(const Formula & LHS,const Formula & RHS)78 const 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 
makeEquals(const Formula & LHS,const Formula & RHS)91 const 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 
makeIntLiteral(llvm::APInt Value)104 IntegerValue &Arena::makeIntLiteral(llvm::APInt Value) {
105   auto [It, Inserted] = IntegerLiterals.try_emplace(Value, nullptr);
106 
107   if (Inserted)
108     It->second = &create<IntegerValue>();
109   return *It->second;
110 }
111 
makeBoolValue(const Formula & F)112 BoolValue &Arena::makeBoolValue(const Formula &F) {
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 
121 namespace {
parse(Arena & A,llvm::StringRef & In)122 const 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 
178 class FormulaParseError : public llvm::ErrorInfo<FormulaParseError> {
179   std::string Formula;
180   unsigned Offset;
181 
182 public:
183   static char ID;
FormulaParseError(llvm::StringRef Formula,unsigned Offset)184   FormulaParseError(llvm::StringRef Formula, unsigned Offset)
185       : Formula(Formula), Offset(Offset) {}
186 
log(raw_ostream & OS) const187   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 
convertToErrorCode() const193   std::error_code convertToErrorCode() const override {
194     return std::make_error_code(std::errc::invalid_argument);
195   }
196 };
197 
198 char FormulaParseError::ID = 0;
199 
200 } // namespace
201 
parseFormula(llvm::StringRef In)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());
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
214