================
@@ -208,6 +208,27 @@ bool DataflowAnalysisContext::equivalentFormulas(const
Formula &Val1,
return isUnsatisfiable(std::move(Constraints));
}
+llvm::DenseSet<Atom> DataflowAnalysisContext::getTransitiveClosure(
+ const llvm::DenseSet<Atom> &Tokens) const {
+ llvm::DenseSet<Atom> VisitedTokens;
+ // Use a worklist algorithm, with `Remaining` holding the worklist.
+ std::vector<Atom> Remaining(Tokens.begin(), Tokens.end());
+
+ // For each token in `Remaining`, add its dependencies to the worklist.
+ while (!Remaining.empty()) {
+ auto Token = Remaining.back();
+ Remaining.pop_back();
+ if (!VisitedTokens.insert(Token).second)
+ continue;
+ if (auto DepsIt = FlowConditionDeps.find(Token);
+ DepsIt != FlowConditionDeps.end())
+ for (Atom A : DepsIt->second)
+ Remaining.push_back(A);
----------------
usx95 wrote:
Sorry for not expanding earlier. While explaining, I realized my initial
suggestion did have an extra lookup for unvisited nodes. My bad.
There were trade offs here though.
For **already visited tokens**, current approach did extra `push_back` and
`pop_back`. Cost of one `Lookup` remains the same whether it happens before the
push or after the pop.
For **unvisited tokens**, the suggested approach _does_ add an extra `lookup`
on top of the already lookup on 221.
>Since we can never establish an invariant on Remaining that it contains only
>unvisited tokens
I think we can.
My suggestion would be to remove lookup on 221 and move it to before the push
which avoids adding redundant items to the worklist altogether. This also makes
the original check after popping unnecessary.
```cpp
llvm::DenseSet<Atom> VisitedTokens(Tokens.begin(), Tokens.end());
std::vector<Atom> Remaining(Tokens.begin(), Tokens.end());
while (!Remaining.empty()) {
Atom CurrentToken = Remaining.back();
Remaining.pop_back();
if (auto DepsIt = FlowConditionDeps.find(Token);
DepsIt != FlowConditionDeps.end())
for (Atom A : DepsIt->second)
if (VisitedTokens.insert(A).second)
Remaining.push_back(A);
}
```
In this case, you might want to rename `VisitedTokens` to something else
(`Result`, `TokensSeen` as we have not yet visited it in principle).
https://github.com/llvm/llvm-project/pull/152487
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
