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 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> 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 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 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 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 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 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 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 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 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 { 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; 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 198 char FormulaParseError::ID = 0; 199 200 } // namespace 201 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