================
@@ -202,53 +203,74 @@ class AnalysisImpl
return getLoans(getState(P), OID);
}
- llvm::SmallVector<OriginID>
- buildOriginFlowChain(ProgramPoint StartPoint, const OriginID StartOID,
- const LoanID TargetLoan) const {
+ llvm::SmallVector<OriginID> buildOriginFlowChain(ProgramPoint StartPoint,
+ const OriginID StartOID,
+ const LoanID TargetLoan,
+ const CFG *Cfg) const {
assert(getLoans(StartOID, StartPoint).contains(TargetLoan) &&
"TargetLoan must be present in the StartOID at the StartPoint");
- OriginID CurrOID = StartOID;
- llvm::SmallVector<OriginID> OriginFlowChain;
- llvm::ArrayRef<const Fact *> Facts =
FactMgr.getBlockContaining(StartPoint);
- const auto *StartIt = llvm::find(Facts, StartPoint);
- assert(StartIt != Facts.end());
-
- for (const Fact *F :
- llvm::reverse(llvm::make_range(Facts.begin(), StartIt))) {
- if (const auto *IF = F->getAs<IssueFact>())
- if (IF->getLoanID() == TargetLoan) {
- assert(IF->getOriginID() == CurrOID);
- return OriginFlowChain;
- }
+ // Locate the CFG block containing the StartPoint
+ const CFGBlock *EndBlock = nullptr;
+ size_t BlockID = FactMgr.getBlockID(StartPoint);
+ for (const CFGBlock *Block : *Cfg)
+ if (Block->getBlockID() == BlockID) {
+ EndBlock = Block;
+ break;
+ }
- const auto *OFF = F->getAs<OriginFlowFact>();
- if (!OFF)
- continue;
- if (OFF->getDestOriginID() != CurrOID)
- continue;
+ // Set up DFS traversal state
+ // SearchState tracks which block we're in and which origin we're tracing
+ // Each DFSNode maintains its own OriginFlowChain.
+ using SearchState = std::pair<const CFGBlock *, OriginID>;
+ struct DFSNode {
+ SearchState CurrState;
+ llvm::SmallVector<OriginID> OriginFlowChain;
+ };
+
+ llvm::SmallVector<DFSNode> PendingStates;
+ llvm::SmallSet<SearchState, 16> VistedStates;
+ PendingStates.push_back({{EndBlock, StartOID}, {}});
+
+ // DFS loop to trace loan backwards through CFG
+ while (!PendingStates.empty()) {
+ DFSNode CurrNode = PendingStates.pop_back_val();
+ auto [CurrBlock, CurrOID] = CurrNode.CurrState;
+
+ // Trace origins within the current block
+ const auto [BuildResult, Complete] =
+ buildOriginFlowChain(CurrBlock, CurrOID, TargetLoan);
+ if (!BuildResult.empty()) {
+ CurrNode.OriginFlowChain.append(BuildResult);
+ CurrOID = BuildResult.back();
+ }
- const OriginID SrcOriginID = OFF->getSrcOriginID();
- if (!getLoans(SrcOriginID, OFF).contains(TargetLoan))
- continue;
- OriginFlowChain.push_back(SrcOriginID);
- CurrOID = SrcOriginID;
+ // If we found the IssueFact, we're done
+ if (Complete)
+ return CurrNode.OriginFlowChain;
+
+ // Only explore predecessor blocks where the target loan is present in
the
+ // current origin.
+ for (const CFGBlock *PredBlock : CurrBlock->preds()) {
+ SearchState NextState = {PredBlock, CurrOID};
+ if (getLoans(getOutState(PredBlock), CurrOID).contains(TargetLoan) &&
+ VistedStates.insert(NextState).second)
+ PendingStates.push_back({NextState, CurrNode.OriginFlowChain});
+ }
}
- // FIXME: Ideally, this return is unreachable and should be an assert
- // because we expect to always finish at an IssueFact. But since current
- // traversal is limited to a single CFG block, multi-block OriginFlowChain
- // construction might miss the IssueFact. We should add llvm_unreachable
- // here once multi-block support is implemented.
- return {};
+ llvm_unreachable(
+ "buildOriginFlowChain did not reach IssueFact for TargetLoan");
----------------
NeKon69 wrote:
nit: I think we can make this more descriptive
```cpp
llvm_unreachable(
"Could not reconstruct origin flow. Search finished without reaching
IssueFact");
```
Or something similar.
https://github.com/llvm/llvm-project/pull/204592
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
