Coverage Report

Created: 2023-09-30 09:22

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/FlowSensitive/Arena.cpp
Line
Count
Source (jump to first uncovered line)
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
10.9k
canonicalFormulaPair(const Formula &LHS, const Formula &RHS) {
19
10.9k
  auto Res = std::make_pair(&LHS, &RHS);
20
10.9k
  if (&RHS < &LHS) // FIXME: use a deterministic order instead
21
7.76k
    std::swap(Res.first, Res.second);
22
10.9k
  return Res;
23
10.9k
}
24
25
22.8k
const Formula &Arena::makeAtomRef(Atom A) {
26
22.8k
  auto [It, Inserted] = AtomRefs.try_emplace(A);
27
22.8k
  if (Inserted)
28
7.65k
    It->second =
29
7.65k
        &Formula::create(Alloc, Formula::AtomRef, {}, static_cast<unsigned>(A));
30
22.8k
  return *It->second;
31
22.8k
}
32
33
2.91k
const Formula &Arena::makeAnd(const Formula &LHS, const Formula &RHS) {
34
2.91k
  if (&LHS == &RHS)
35
2
    return LHS;
36
37
2.91k
  auto [It, Inserted] =
38
2.91k
      Ands.try_emplace(canonicalFormulaPair(LHS, RHS), nullptr);
39
2.91k
  if (Inserted)
40
2.13k
    It->second = &Formula::create(Alloc, Formula::And, {&LHS, &RHS});
41
2.91k
  return *It->second;
42
2.91k
}
43
44
1.38k
const Formula &Arena::makeOr(const Formula &LHS, const Formula &RHS) {
45
1.38k
  if (&LHS == &RHS)
46
2
    return LHS;
47
48
1.38k
  auto [It, Inserted] =
49
1.38k
      Ors.try_emplace(canonicalFormulaPair(LHS, RHS), nullptr);
50
1.38k
  if (Inserted)
51
1.15k
    It->second = &Formula::create(Alloc, Formula::Or, {&LHS, &RHS});
52
1.38k
  return *It->second;
53
1.38k
}
54
55
4.19k
const Formula &Arena::makeNot(const Formula &Val) {
56
4.19k
  auto [It, Inserted] = Nots.try_emplace(&Val, nullptr);
57
4.19k
  if (Inserted)
58
1.87k
    It->second = &Formula::create(Alloc, Formula::Not, {&Val});
59
4.19k
  return *It->second;
60
4.19k
}
61
62
428
const Formula &Arena::makeImplies(const Formula &LHS, const Formula &RHS) {
63
428
  if (&LHS == &RHS)
64
1
    return makeLiteral(true);
65
66
427
  auto [It, Inserted] =
67
427
      Implies.try_emplace(std::make_pair(&LHS, &RHS), nullptr);
68
427
  if (Inserted)
69
369
    It->second = &Formula::create(Alloc, Formula::Implies, {&LHS, &RHS});
70
427
  return *It->second;
71
428
}
72
73
6.63k
const Formula &Arena::makeEquals(const Formula &LHS, const Formula &RHS) {
74
6.63k
  if (&LHS == &RHS)
75
7
    return makeLiteral(true);
76
77
6.62k
  auto [It, Inserted] =
78
6.62k
      Equals.try_emplace(canonicalFormulaPair(LHS, RHS), nullptr);
79
6.62k
  if (Inserted)
80
2.76k
    It->second = &Formula::create(Alloc, Formula::Equal, {&LHS, &RHS});
81
6.62k
  return *It->second;
82
6.63k
}
83
84
882
IntegerValue &Arena::makeIntLiteral(llvm::APInt Value) {
85
882
  auto [It, Inserted] = IntegerLiterals.try_emplace(Value, nullptr);
86
87
882
  if (Inserted)
88
333
    It->second = &create<IntegerValue>();
89
882
  return *It->second;
90
882
}
91
92
3.97k
BoolValue &Arena::makeBoolValue(const Formula &F) {
93
3.97k
  auto [It, Inserted] = FormulaValues.try_emplace(&F);
94
3.97k
  if (Inserted)
95
2.74k
    It->second = (F.kind() == Formula::AtomRef)
96
2.74k
                     ? 
(BoolValue *)&create<AtomicBoolValue>(F)2.03k
97
2.74k
                     : 
&create<FormulaBoolValue>(F)708
;
98
3.97k
  return *It->second;
99
3.97k
}
100
101
namespace {
102
109
const Formula *parse(Arena &A, llvm::StringRef &In) {
103
170
  auto EatSpaces = [&] { In = In.ltrim(' '); };
104
109
  EatSpaces();
105
106
109
  if (In.consume_front("!")) {
107
20
    if (auto *Arg = parse(A, In))
108
20
      return &A.makeNot(*Arg);
109
0
    return nullptr;
110
20
  }
111
112
89
  if (In.consume_front("(")) {
113
31
    auto *Arg1 = parse(A, In);
114
31
    if (!Arg1)
115
0
      return nullptr;
116
117
31
    EatSpaces();
118
31
    decltype(&Arena::makeOr) Op;
119
31
    if (In.consume_front("|"))
120
7
      Op = &Arena::makeOr;
121
24
    else if (In.consume_front("&"))
122
9
      Op = &Arena::makeAnd;
123
15
    else if (In.consume_front("=>"))
124
5
      Op = &Arena::makeImplies;
125
10
    else if (In.consume_front("="))
126
10
      Op = &Arena::makeEquals;
127
0
    else
128
0
      return nullptr;
129
130
31
    auto *Arg2 = parse(A, In);
131
31
    if (!Arg2)
132
1
      return nullptr;
133
134
30
    EatSpaces();
135
30
    if (!In.consume_front(")"))
136
0
      return nullptr;
137
138
30
    return &(A.*Op)(*Arg1, *Arg2);
139
30
  }
140
141
  // For now, only support unnamed variables V0, V1 etc.
142
  // FIXME: parse e.g. "X" by allocating an atom and storing a name somewhere.
143
58
  if (In.consume_front("V")) {
144
54
    std::underlying_type_t<Atom> At;
145
54
    if (In.consumeInteger(10, At))
146
0
      return nullptr;
147
54
    return &A.makeAtomRef(static_cast<Atom>(At));
148
54
  }
149
150
4
  if (In.consume_front("true"))
151
1
    return &A.makeLiteral(true);
152
3
  if (In.consume_front("false"))
153
2
    return &A.makeLiteral(false);
154
155
1
  return nullptr;
156
3
}
157
158
class FormulaParseError : public llvm::ErrorInfo<FormulaParseError> {
159
  std::string Formula;
160
  unsigned Offset;
161
162
public:
163
  static char ID;
164
  FormulaParseError(llvm::StringRef Formula, unsigned Offset)
165
2
      : Formula(Formula), Offset(Offset) {}
166
167
2
  void log(raw_ostream &OS) const override {
168
2
    OS << "bad formula at offset " << Offset << "\n";
169
2
    OS << Formula << "\n";
170
2
    OS.indent(Offset) << "^";
171
2
  }
172
173
0
  std::error_code convertToErrorCode() const override {
174
0
    return std::make_error_code(std::errc::invalid_argument);
175
0
  }
176
};
177
178
char FormulaParseError::ID = 0;
179
180
} // namespace
181
182
27
llvm::Expected<const Formula &> Arena::parseFormula(llvm::StringRef In) {
183
27
  llvm::StringRef Rest = In;
184
27
  auto *Result = parse(*this, Rest);
185
27
  if (!Result) // parse() hit something unparseable
186
1
    return llvm::make_error<FormulaParseError>(In, In.size() - Rest.size());
187
26
  Rest = Rest.ltrim();
188
26
  if (!Rest.empty()) // parse didn't consume all the input
189
1
    return llvm::make_error<FormulaParseError>(In, In.size() - Rest.size());
190
25
  return *Result;
191
26
}
192
193
} // namespace clang::dataflow