/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

Source (jump to first uncovered line)
//===-- DataflowAnalysisContext.cpp -----------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
//  This file defines a DataflowAnalysisContext class that owns objects that
//  encompass the state of a program and stores context that is used during
//  dataflow analysis.
//
//===----------------------------------------------------------------------===//

#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
#include "clang/AST/ExprCXX.h"
#include "clang/Analysis/FlowSensitive/Value.h"
#include <cassert>
#include <memory>
#include <utility>

namespace clang {
namespace dataflow {

StorageLocation &
DataflowAnalysisContext::getStableStorageLocation(QualType Type) {
  if (!Type.isNull() &&
      (3.10kType->isStructureOrClassType()3.10k || Type->isUnionType()1.55k)) {
    // FIXME: Explore options to avoid eager initialization of fields as some of
    // them might not be needed for a particular analysis.
    llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
    for (const FieldDecl *Field : getObjectFields(Type))
      FieldLocs.insert({Field, &getStableStorageLocation(Field->getType())});
    return takeOwnership(
        std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs)));
  }
  return takeOwnership(std::make_unique<ScalarStorageLocation>(Type));
}

StorageLocation &
DataflowAnalysisContext::getStableStorageLocation(const VarDecl &D) {
  if (auto *Loc = getStorageLocation(D))
    return *Loc;
  auto &Loc = getStableStorageLocation(D.getType());
  setStorageLocation(D, Loc);
  return Loc;
}

StorageLocation &
DataflowAnalysisContext::getStableStorageLocation(const Expr &E) {
  if (auto *Loc = getStorageLocation(E))
    return *Loc;
  auto &Loc = getStableStorageLocation(E.getType());
  setStorageLocation(E, Loc);
  return Loc;
}

PointerValue &
DataflowAnalysisContext::getOrCreateNullPointerValue(QualType PointeeType) {
  auto CanonicalPointeeType =
      PointeeType.isNull() ? PointeeType2 : PointeeType.getCanonicalType()18;
  auto Res = NullPointerVals.try_emplace(CanonicalPointeeType, nullptr);
  if (Res.second) {
    auto &PointeeLoc = getStableStorageLocation(CanonicalPointeeType);
    Res.first->second =
        &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
  }
  return *Res.first->second;
}

static std::pair<BoolValue *, BoolValue *>
makeCanonicalBoolValuePair(BoolValue &LHS, BoolValue &RHS) {
  auto Res = std::make_pair(&LHS, &RHS);
  if (&RHS < &LHS)
    std::swap(Res.first, Res.second);
  return Res;
}

BoolValue &DataflowAnalysisContext::getOrCreateConjunction(BoolValue &LHS,
                                                           BoolValue &RHS) {
  if (&LHS == &RHS)
    return LHS;

  auto Res = ConjunctionVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS),
                                         nullptr);
  if (Res.second)
    Res.first->second =
        &takeOwnership(std::make_unique<ConjunctionValue>(LHS, RHS));
  return *Res.first->second;
}

BoolValue &DataflowAnalysisContext::getOrCreateDisjunction(BoolValue &LHS,
                                                           BoolValue &RHS) {
  if (&LHS == &RHS)
    return LHS;

  auto Res = DisjunctionVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS),
                                         nullptr);
  if (Res.second)
    Res.first->second =
        &takeOwnership(std::make_unique<DisjunctionValue>(LHS, RHS));
  return *Res.first->second;
}

BoolValue &DataflowAnalysisContext::getOrCreateNegation(BoolValue &Val) {
  auto Res = NegationVals.try_emplace(&Val, nullptr);
  if (Res.second)
    Res.first->second = &takeOwnership(std::make_unique<NegationValue>(Val));
  return *Res.first->second;
}

BoolValue &DataflowAnalysisContext::getOrCreateImplication(BoolValue &LHS,
                                                           BoolValue &RHS) {
  return &LHS == &RHS ? getBoolLiteralValue(true)1
                      : getOrCreateDisjunction(getOrCreateNegation(LHS), RHS)10.0k;
}

BoolValue &DataflowAnalysisContext::getOrCreateIff(BoolValue &LHS,
                                                   BoolValue &RHS) {
  return &LHS == &RHS
             ? getBoolLiteralValue(true)8
             : getOrCreateConjunction(getOrCreateImplication(LHS, RHS),
                                      getOrCreateImplication(RHS, LHS));
}

AtomicBoolValue &DataflowAnalysisContext::makeFlowConditionToken() {
  return createAtomicBoolValue();
}

void DataflowAnalysisContext::addFlowConditionConstraint(
    AtomicBoolValue &Token, BoolValue &Constraint) {
  auto Res = FlowConditionConstraints.try_emplace(&Token, &Constraint);
  if (!Res.second) {
    Res.first->second = &getOrCreateConjunction(*Res.first->second, Constraint);
  }
}

AtomicBoolValue &
DataflowAnalysisContext::forkFlowCondition(AtomicBoolValue &Token) {
  auto &ForkToken = makeFlowConditionToken();
  FlowConditionDeps[&ForkToken].insert(&Token);
  addFlowConditionConstraint(ForkToken, Token);
  return ForkToken;
}

AtomicBoolValue &
DataflowAnalysisContext::joinFlowConditions(AtomicBoolValue &FirstToken,
                                            AtomicBoolValue &SecondToken) {
  auto &Token = makeFlowConditionToken();
  FlowConditionDeps[&Token].insert(&FirstToken);
  FlowConditionDeps[&Token].insert(&SecondToken);
  addFlowConditionConstraint(Token,
                             getOrCreateDisjunction(FirstToken, SecondToken));
  return Token;
}

Solver::Result
DataflowAnalysisContext::querySolver(llvm::DenseSet<BoolValue *> Constraints) {
  Constraints.insert(&getBoolLiteralValue(true));
  Constraints.insert(&getOrCreateNegation(getBoolLiteralValue(false)));
  return S->solve(std::move(Constraints));
}

bool DataflowAnalysisContext::flowConditionImplies(AtomicBoolValue &Token,
                                                   BoolValue &Val) {
  // Returns true if and only if truth assignment of the flow condition implies
  // that `Val` is also true. We prove whether or not this property holds by
  // reducing the problem to satisfiability checking. In other words, we attempt
  // to show that assuming `Val` is false makes the constraints induced by the
  // flow condition unsatisfiable.
  llvm::DenseSet<BoolValue *> Constraints = {&Token, &getOrCreateNegation(Val)};
  llvm::DenseSet<AtomicBoolValue *> VisitedTokens;
  addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens);
  return isUnsatisfiable(std::move(Constraints));
}

bool DataflowAnalysisContext::flowConditionIsTautology(AtomicBoolValue &Token) {
  // Returns true if and only if we cannot prove that the flow condition can
  // ever be false.
  llvm::DenseSet<BoolValue *> Constraints = {&getOrCreateNegation(Token)};
  llvm::DenseSet<AtomicBoolValue *> VisitedTokens;
  addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens);
  return isUnsatisfiable(std::move(Constraints));
}

bool DataflowAnalysisContext::equivalentBoolValues(BoolValue &Val1,
                                                   BoolValue &Val2) {
  llvm::DenseSet<BoolValue *> Constraints = {
      &getOrCreateNegation(getOrCreateIff(Val1, Val2))};
  return isUnsatisfiable(Constraints);
}

void DataflowAnalysisContext::addTransitiveFlowConditionConstraints(
    AtomicBoolValue &Token, llvm::DenseSet<BoolValue *> &Constraints,
    llvm::DenseSet<AtomicBoolValue *> &VisitedTokens) {
  auto Res = VisitedTokens.insert(&Token);
  if (!Res.second)
    return;

  auto ConstraintsIT = FlowConditionConstraints.find(&Token);
  if (ConstraintsIT == FlowConditionConstraints.end()) {
    Constraints.insert(&Token);
  } else {
    // Bind flow condition token via `iff` to its set of constraints:
    // FC <=> (C1 ^ C2 ^ ...), where Ci are constraints
    Constraints.insert(&getOrCreateIff(Token, *ConstraintsIT->second));
  }

  auto DepsIT = FlowConditionDeps.find(&Token);
  if (DepsIT != FlowConditionDeps.end()) {
    for (AtomicBoolValue *DepToken : DepsIT->second) {
      addTransitiveFlowConditionConstraints(*DepToken, Constraints,
                                            VisitedTokens);
    }
  }
}

BoolValue &DataflowAnalysisContext::substituteBoolValue(
    BoolValue &Val,
    llvm::DenseMap<BoolValue *, BoolValue *> &SubstitutionsCache) {
  auto IT = SubstitutionsCache.find(&Val);
  if (IT != SubstitutionsCache.end()) {
    // Return memoized result of substituting this boolean value.
    return *IT->second;
  }

  // Handle substitution on the boolean value (and its subvalues), saving the
  // result into `SubstitutionsCache`.
  BoolValue *Result;
  switch (Val.getKind()) {
  case Value::Kind::AtomicBool: {
    Result = &Val;
    break;
  }
  case Value::Kind::Negation: {
    auto &Negation = *cast<NegationValue>(&Val);
    auto &Sub = substituteBoolValue(Negation.getSubVal(), SubstitutionsCache);
    Result = &getOrCreateNegation(Sub);
    break;
  }
  case Value::Kind::Disjunction: {
    auto &Disjunct = *cast<DisjunctionValue>(&Val);
    auto &LeftSub =
        substituteBoolValue(Disjunct.getLeftSubValue(), SubstitutionsCache);
    auto &RightSub =
        substituteBoolValue(Disjunct.getRightSubValue(), SubstitutionsCache);
    Result = &getOrCreateDisjunction(LeftSub, RightSub);
    break;
  }
  case Value::Kind::Conjunction: {
    auto &Conjunct = *cast<ConjunctionValue>(&Val);
    auto &LeftSub =
        substituteBoolValue(Conjunct.getLeftSubValue(), SubstitutionsCache);
    auto &RightSub =
        substituteBoolValue(Conjunct.getRightSubValue(), SubstitutionsCache);
    Result = &getOrCreateConjunction(LeftSub, RightSub);
    break;
  }
  default:
    llvm_unreachable("Unhandled Value Kind");
  }
  SubstitutionsCache[&Val] = Result;
  return *Result;
}

BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowCondition(
    AtomicBoolValue &Token,
    llvm::DenseMap<AtomicBoolValue *, BoolValue *> Substitutions) {
  assert(
      Substitutions.find(&getBoolLiteralValue(true)) == Substitutions.end() &&
      Substitutions.find(&getBoolLiteralValue(false)) == Substitutions.end() &&
      "Do not substitute true/false boolean literals");
  llvm::DenseMap<BoolValue *, BoolValue *> SubstitutionsCache(
      Substitutions.begin(), Substitutions.end());
  return buildAndSubstituteFlowConditionWithCache(Token, SubstitutionsCache);
}

BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowConditionWithCache(
    AtomicBoolValue &Token,
    llvm::DenseMap<BoolValue *, BoolValue *> &SubstitutionsCache) {
  auto ConstraintsIT = FlowConditionConstraints.find(&Token);
  if (ConstraintsIT == FlowConditionConstraints.end()) {
    return getBoolLiteralValue(true);
  }
  auto DepsIT = FlowConditionDeps.find(&Token);
  if (DepsIT != FlowConditionDeps.end()) {
    for (AtomicBoolValue *DepToken : DepsIT->second) {
      auto &NewDep = buildAndSubstituteFlowConditionWithCache(
          *DepToken, SubstitutionsCache);
      SubstitutionsCache[DepToken] = &NewDep;
    }
  }
  return substituteBoolValue(*ConstraintsIT->second, SubstitutionsCache);
}

} // namespace dataflow
} // namespace clang

using namespace clang;

const Expr &clang::dataflow::ignoreCFGOmittedNodes(const Expr &E) {
  const Expr *Current = &E;
  if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) {
    Current = EWC->getSubExpr();
    assert(Current != nullptr);
  }
  Current = Current->IgnoreParens();
  assert(Current != nullptr);
  return *Current;
}

const Stmt &clang::dataflow::ignoreCFGOmittedNodes(const Stmt &S) {
  if (auto *E = dyn_cast<Expr>(&S))
    return ignoreCFGOmittedNodes(*E);
  return S;
}

// FIXME: Does not precisely handle non-virtual diamond inheritance. A single
// field decl will be modeled for all instances of the inherited field.
static void
getFieldsFromClassHierarchy(QualType Type,
                            llvm::DenseSet<const FieldDecl *> &Fields) {
  if (Type->isIncompleteType() || Type->isDependentType() ||
      !Type->isRecordType())
    return;

  for (const FieldDecl *Field : Type->getAsRecordDecl()->fields())
    Fields.insert(Field);
  if (auto *CXXRecord = Type->getAsCXXRecordDecl())
    for (const CXXBaseSpecifier &Base : CXXRecord->bases())
      getFieldsFromClassHierarchy(Base.getType(), Fields);
}

/// Gets the set of all fields in the type.
llvm::DenseSet<const FieldDecl *>
clang::dataflow::getObjectFields(QualType Type) {
  llvm::DenseSet<const FieldDecl *> Fields;
  getFieldsFromClassHierarchy(Type, Fields);
  return Fields;
}

Coverage Report

Created: 2022-07-16 07:03

Line	Count	Source (jump to first uncovered line)
1		//===-- DataflowAnalysisContext.cpp ------------------------------ C++ --===//
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		// This file defines a DataflowAnalysisContext class that owns objects that
10		// encompass the state of a program and stores context that is used during
11		// dataflow analysis.
12		//
13		//===----------------------------------------------------------------------===//
14
15		#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
16		#include "clang/AST/ExprCXX.h"
17		#include "clang/Analysis/FlowSensitive/Value.h"
18		#include <cassert>
19		#include <memory>
20		#include <utility>
21
22		namespace clang {
23		namespace dataflow {
24
25		StorageLocation &
26	3.10k	DataflowAnalysisContext::getStableStorageLocation(QualType Type) {
27	3.10k	if (!Type.isNull() &&
28	3.10k	(3.10k Type->isStructureOrClassType()3.10k \|\| Type->isUnionType()1.55k )) {
29		// FIXME: Explore options to avoid eager initialization of fields as some of
30		// them might not be needed for a particular analysis.
31	1.55k	llvm::DenseMap<const ValueDecl , StorageLocation > FieldLocs;
32	1.55k	for (const FieldDecl *Field : getObjectFields(Type))
33	193	FieldLocs.insert({Field, &getStableStorageLocation(Field->getType())});
34	1.55k	return takeOwnership(
35	1.55k	std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs)));
36	1.55k	}
37	1.55k	return takeOwnership(std::make_unique<ScalarStorageLocation>(Type));
38	3.10k	}
39
40		StorageLocation &
41	1.00k	DataflowAnalysisContext::getStableStorageLocation(const VarDecl &D) {
42	1.00k	if (auto *Loc = getStorageLocation(D))
43	366	return *Loc;
44	642	auto &Loc = getStableStorageLocation(D.getType());
45	642	setStorageLocation(D, Loc);
46	642	return Loc;
47	1.00k	}
48
49		StorageLocation &
50	3.53k	DataflowAnalysisContext::getStableStorageLocation(const Expr &E) {
51	3.53k	if (auto *Loc = getStorageLocation(E))
52	1.83k	return *Loc;
53	1.69k	auto &Loc = getStableStorageLocation(E.getType());
54	1.69k	setStorageLocation(E, Loc);
55	1.69k	return Loc;
56	3.53k	}
57
58		PointerValue &
59	20	DataflowAnalysisContext::getOrCreateNullPointerValue(QualType PointeeType) {
60	20	auto CanonicalPointeeType =
61	20	PointeeType.isNull() ? PointeeType2 : PointeeType.getCanonicalType()18 ;
62	20	auto Res = NullPointerVals.try_emplace(CanonicalPointeeType, nullptr);
63	20	if (Res.second) {
64	9	auto &PointeeLoc = getStableStorageLocation(CanonicalPointeeType);
65	9	Res.first->second =
66	9	&takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
67	9	}
68	20	return *Res.first->second;
69	20	}
70
71		static std::pair<BoolValue , BoolValue >
72	16.8k	makeCanonicalBoolValuePair(BoolValue &LHS, BoolValue &RHS) {
73	16.8k	auto Res = std::make_pair(&LHS, &RHS);
74	16.8k	if (&RHS < &LHS)
75	10.0k	std::swap(Res.first, Res.second);
76	16.8k	return Res;
77	16.8k	}
78
79		BoolValue &DataflowAnalysisContext::getOrCreateConjunction(BoolValue &LHS,
80	6.26k	BoolValue &RHS) {
81	6.26k	if (&LHS == &RHS)
82	2	return LHS;
83
84	6.26k	auto Res = ConjunctionVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS),
85	6.26k	nullptr);
86	6.26k	if (Res.second)
87	2.84k	Res.first->second =
88	2.84k	&takeOwnership(std::make_unique<ConjunctionValue>(LHS, RHS));
89	6.26k	return *Res.first->second;
90	6.26k	}
91
92		BoolValue &DataflowAnalysisContext::getOrCreateDisjunction(BoolValue &LHS,
93	10.5k	BoolValue &RHS) {
94	10.5k	if (&LHS == &RHS)
95	3	return LHS;
96
97	10.5k	auto Res = DisjunctionVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS),
98	10.5k	nullptr);
99	10.5k	if (Res.second)
100	4.68k	Res.first->second =
101	4.68k	&takeOwnership(std::make_unique<DisjunctionValue>(LHS, RHS));
102	10.5k	return *Res.first->second;
103	10.5k	}
104
105	12.1k	BoolValue &DataflowAnalysisContext::getOrCreateNegation(BoolValue &Val) {
106	12.1k	auto Res = NegationVals.try_emplace(&Val, nullptr);
107	12.1k	if (Res.second)
108	3.69k	Res.first->second = &takeOwnership(std::make_unique<NegationValue>(Val));
109	12.1k	return *Res.first->second;
110	12.1k	}
111
112		BoolValue &DataflowAnalysisContext::getOrCreateImplication(BoolValue &LHS,
113	10.0k	BoolValue &RHS) {
114	10.0k	return &LHS == &RHS ? getBoolLiteralValue(true)1
115	10.0k	: getOrCreateDisjunction(getOrCreateNegation(LHS), RHS)10.0k ;
116	10.0k	}
117
118		BoolValue &DataflowAnalysisContext::getOrCreateIff(BoolValue &LHS,
119	4.99k	BoolValue &RHS) {
120	4.99k	return &LHS == &RHS
121	4.99k	? getBoolLiteralValue(true)8
122	4.99k	: getOrCreateConjunction(getOrCreateImplication(LHS, RHS),
123	4.98k	getOrCreateImplication(RHS, LHS));
124	4.99k	}
125
126	8.27k	AtomicBoolValue &DataflowAnalysisContext::makeFlowConditionToken() {
127	8.27k	return createAtomicBoolValue();
128	8.27k	}
129
130		void DataflowAnalysisContext::addFlowConditionConstraint(
131	8.46k	AtomicBoolValue &Token, BoolValue &Constraint) {
132	8.46k	auto Res = FlowConditionConstraints.try_emplace(&Token, &Constraint);
133	8.46k	if (!Res.second) {
134	1.05k	Res.first->second = &getOrCreateConjunction(*Res.first->second, Constraint);
135	1.05k	}
136	8.46k	}
137
138		AtomicBoolValue &
139	6.91k	DataflowAnalysisContext::forkFlowCondition(AtomicBoolValue &Token) {
140	6.91k	auto &ForkToken = makeFlowConditionToken();
141	6.91k	FlowConditionDeps[&ForkToken].insert(&Token);
142	6.91k	addFlowConditionConstraint(ForkToken, Token);
143	6.91k	return ForkToken;
144	6.91k	}
145
146		AtomicBoolValue &
147		DataflowAnalysisContext::joinFlowConditions(AtomicBoolValue &FirstToken,
148	474	AtomicBoolValue &SecondToken) {
149	474	auto &Token = makeFlowConditionToken();
150	474	FlowConditionDeps[&Token].insert(&FirstToken);
151	474	FlowConditionDeps[&Token].insert(&SecondToken);
152	474	addFlowConditionConstraint(Token,
153	474	getOrCreateDisjunction(FirstToken, SecondToken));
154	474	return Token;
155	474	}
156
157		Solver::Result
158	688	DataflowAnalysisContext::querySolver(llvm::DenseSet<BoolValue *> Constraints) {
159	688	Constraints.insert(&getBoolLiteralValue(true));
160	688	Constraints.insert(&getOrCreateNegation(getBoolLiteralValue(false)));
161	688	return S->solve(std::move(Constraints));
162	688	}
163
164		bool DataflowAnalysisContext::flowConditionImplies(AtomicBoolValue &Token,
165	648	BoolValue &Val) {
166		// Returns true if and only if truth assignment of the flow condition implies
167		// that `Val` is also true. We prove whether or not this property holds by
168		// reducing the problem to satisfiability checking. In other words, we attempt
169		// to show that assuming `Val` is false makes the constraints induced by the
170		// flow condition unsatisfiable.
171	648	llvm::DenseSet<BoolValue *> Constraints = {&Token, &getOrCreateNegation(Val)};
172	648	llvm::DenseSet<AtomicBoolValue *> VisitedTokens;
173	648	addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens);
174	648	return isUnsatisfiable(std::move(Constraints));
175	648	}
176
177	5	bool DataflowAnalysisContext::flowConditionIsTautology(AtomicBoolValue &Token) {
178		// Returns true if and only if we cannot prove that the flow condition can
179		// ever be false.
180	5	llvm::DenseSet<BoolValue *> Constraints = {&getOrCreateNegation(Token)};
181	5	llvm::DenseSet<AtomicBoolValue *> VisitedTokens;
182	5	addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens);
183	5	return isUnsatisfiable(std::move(Constraints));
184	5	}
185
186		bool DataflowAnalysisContext::equivalentBoolValues(BoolValue &Val1,
187	35	BoolValue &Val2) {
188	35	llvm::DenseSet<BoolValue *> Constraints = {
189	35	&getOrCreateNegation(getOrCreateIff(Val1, Val2))};
190	35	return isUnsatisfiable(Constraints);
191	35	}
192
193		void DataflowAnalysisContext::addTransitiveFlowConditionConstraints(
194		AtomicBoolValue &Token, llvm::DenseSet<BoolValue *> &Constraints,
195	5.67k	llvm::DenseSet<AtomicBoolValue *> &VisitedTokens) {
196	5.67k	auto Res = VisitedTokens.insert(&Token);
197	5.67k	if (!Res.second)
198	207	return;
199
200	5.47k	auto ConstraintsIT = FlowConditionConstraints.find(&Token);
201	5.47k	if (ConstraintsIT == FlowConditionConstraints.end()) {
202	640	Constraints.insert(&Token);
203	4.83k	} else {
204		// Bind flow condition token via `iff` to its set of constraints:
205		// FC <=> (C1 ^ C2 ^ ...), where Ci are constraints
206	4.83k	Constraints.insert(&getOrCreateIff(Token, *ConstraintsIT->second));
207	4.83k	}
208
209	5.47k	auto DepsIT = FlowConditionDeps.find(&Token);
210	5.47k	if (DepsIT != FlowConditionDeps.end()) {
211	5.02k	for (AtomicBoolValue *DepToken : DepsIT->second) {
212	5.02k	addTransitiveFlowConditionConstraints(*DepToken, Constraints,
213	5.02k	VisitedTokens);
214	5.02k	}
215	4.81k	}
216	5.47k	}
217
218		BoolValue &DataflowAnalysisContext::substituteBoolValue(
219		BoolValue &Val,
220	90	llvm::DenseMap<BoolValue , BoolValue > &SubstitutionsCache) {
221	90	auto IT = SubstitutionsCache.find(&Val);
222	90	if (IT != SubstitutionsCache.end()) {
223		// Return memoized result of substituting this boolean value.
224	37	return *IT->second;
225	37	}
226
227		// Handle substitution on the boolean value (and its subvalues), saving the
228		// result into `SubstitutionsCache`.
229	53	BoolValue *Result;
230	53	switch (Val.getKind()) {
231	25	case Value::Kind::AtomicBool: {
232	25	Result = &Val;
233	25	break;
234	0	}
235	2	case Value::Kind::Negation: {
236	2	auto &Negation = *cast<NegationValue>(&Val);
237	2	auto &Sub = substituteBoolValue(Negation.getSubVal(), SubstitutionsCache);
238	2	Result = &getOrCreateNegation(Sub);
239	2	break;
240	0	}
241	8	case Value::Kind::Disjunction: {
242	8	auto &Disjunct = *cast<DisjunctionValue>(&Val);
243	8	auto &LeftSub =
244	8	substituteBoolValue(Disjunct.getLeftSubValue(), SubstitutionsCache);
245	8	auto &RightSub =
246	8	substituteBoolValue(Disjunct.getRightSubValue(), SubstitutionsCache);
247	8	Result = &getOrCreateDisjunction(LeftSub, RightSub);
248	8	break;
249	0	}
250	18	case Value::Kind::Conjunction: {
251	18	auto &Conjunct = *cast<ConjunctionValue>(&Val);
252	18	auto &LeftSub =
253	18	substituteBoolValue(Conjunct.getLeftSubValue(), SubstitutionsCache);
254	18	auto &RightSub =
255	18	substituteBoolValue(Conjunct.getRightSubValue(), SubstitutionsCache);
256	18	Result = &getOrCreateConjunction(LeftSub, RightSub);
257	18	break;
258	0	}
259	0	default:
260	0	llvm_unreachable("Unhandled Value Kind");
261	53	}
262	53	SubstitutionsCache[&Val] = Result;
263	53	return *Result;
264	53	}
265
266		BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowCondition(
267		AtomicBoolValue &Token,
268	19	llvm::DenseMap<AtomicBoolValue , BoolValue > Substitutions) {
269	19	assert(
270	19	Substitutions.find(&getBoolLiteralValue(true)) == Substitutions.end() &&
271	19	Substitutions.find(&getBoolLiteralValue(false)) == Substitutions.end() &&
272	19	"Do not substitute true/false boolean literals");
273	0	llvm::DenseMap<BoolValue , BoolValue > SubstitutionsCache(
274	19	Substitutions.begin(), Substitutions.end());
275	19	return buildAndSubstituteFlowConditionWithCache(Token, SubstitutionsCache);
276	19	}
277
278		BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowConditionWithCache(
279		AtomicBoolValue &Token,
280	36	llvm::DenseMap<BoolValue , BoolValue > &SubstitutionsCache) {
281	36	auto ConstraintsIT = FlowConditionConstraints.find(&Token);
282	36	if (ConstraintsIT == FlowConditionConstraints.end()) {
283	0	return getBoolLiteralValue(true);
284	0	}
285	36	auto DepsIT = FlowConditionDeps.find(&Token);
286	36	if (DepsIT != FlowConditionDeps.end()) {
287	17	for (AtomicBoolValue *DepToken : DepsIT->second) {
288	17	auto &NewDep = buildAndSubstituteFlowConditionWithCache(
289	17	*DepToken, SubstitutionsCache);
290	17	SubstitutionsCache[DepToken] = &NewDep;
291	17	}
292	11	}
293	36	return substituteBoolValue(*ConstraintsIT->second, SubstitutionsCache);
294	36	}
295
296		} // namespace dataflow
297		} // namespace clang
298
299		using namespace clang;
300
301	19.2k	const Expr &clang::dataflow::ignoreCFGOmittedNodes(const Expr &E) {
302	19.2k	const Expr *Current = &E;
303	19.2k	if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) {
304	326	Current = EWC->getSubExpr();
305	326	assert(Current != nullptr);
306	326	}
307	0	Current = Current->IgnoreParens();
308	19.2k	assert(Current != nullptr);
309	0	return *Current;
310	19.2k	}
311
312	196	const Stmt &clang::dataflow::ignoreCFGOmittedNodes(const Stmt &S) {
313	196	if (auto *E = dyn_cast<Expr>(&S))
314	196	return ignoreCFGOmittedNodes(*E);
315	0	return S;
316	196	}
317
318		// FIXME: Does not precisely handle non-virtual diamond inheritance. A single
319		// field decl will be modeled for all instances of the inherited field.
320		static void
321		getFieldsFromClassHierarchy(QualType Type,
322	6.91k	llvm::DenseSet<const FieldDecl *> &Fields) {
323	6.91k	if (Type->isIncompleteType() \|\| Type->isDependentType() \|\|
324	6.91k	!Type->isRecordType())
325	0	return;
326
327	6.91k	for (const FieldDecl *Field : Type->getAsRecordDecl()->fields())
328	541	Fields.insert(Field);
329	6.91k	if (auto *CXXRecord = Type->getAsCXXRecordDecl())
330	6.91k	for (const CXXBaseSpecifier &Base : CXXRecord->bases())
331	2.17k	getFieldsFromClassHierarchy(Base.getType(), Fields);
332	6.91k	}
333
334		/// Gets the set of all fields in the type.
335		llvm::DenseSet<const FieldDecl *>
336	4.73k	clang::dataflow::getObjectFields(QualType Type) {
337	4.73k	llvm::DenseSet<const FieldDecl *> Fields;
338	4.73k	getFieldsFromClassHierarchy(Type, Fields);
339	4.73k	return Fields;
340	4.73k	}