214 lines · cpp
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-exception6//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 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 instead21 std::swap(Res.first, Res.second);22 return Res;23}24 25template <class Key, class ComputeFunc>26static 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 34const 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 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 104IntegerValue &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 112BoolValue &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 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 else148 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} // namespace201 202llvm::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 unparseable206 return llvm::make_error<FormulaParseError>(In, In.size() - Rest.size());207 Rest = Rest.ltrim();208 if (!Rest.empty()) // parse didn't consume all the input209 return llvm::make_error<FormulaParseError>(In, In.size() - Rest.size());210 return *Result;211}212 213} // namespace clang::dataflow214