clang/lib/Analysis/FlowSensitive/Arena.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-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