================
@@ -1118,109 +1119,189 @@ class LoanPropagationAnalysis
OriginLoanMapFactory.add(In.Origins, DestOID, MergedLoans));
}
- LoanSet getLoans(OriginID OID, ProgramPoint P) {
+ LoanSet getLoans(OriginID OID, ProgramPoint P) const {
return getLoans(getState(P), OID);
}
private:
- LoanSet getLoans(Lattice L, OriginID OID) {
+ LoanSet getLoans(Lattice L, OriginID OID) const {
if (auto *Loans = L.Origins.lookup(OID))
return *Loans;
return LoanSetFactory.getEmptySet();
}
};
// ========================================================================= //
-// Expired Loans Analysis
+// Live Origins Analysis
// ========================================================================= //
-/// The dataflow lattice for tracking the set of expired loans.
-struct ExpiredLattice {
- /// Map from an expired `LoanID` to the `ExpireFact` that made it expire.
- ExpiredLoanMap Expired;
+/// Information about why an origin is live at a program point.
+struct LivenessInfo {
+ /// The use that makes the origin live. If liveness is propagated from
+ /// multiple uses along different paths, this will point to the use appearing
+ /// before in the translation unit.
+ const UseFact *CausingUseFact;
+ /// The confidence in the liveness of the origin.
+ /// `Definite`: The origin is live on all control-flow paths from the current
+ /// point to the function's exit (i.e. the current point is dominated by a
set
+ /// of uses).
+ /// `Maybe`: indicates it is live on some but not all paths.
+ Confidence ConfidenceLevel;
+
+ LivenessInfo() : CausingUseFact(nullptr), ConfidenceLevel(Confidence::None)
{}
+ LivenessInfo(const UseFact *UF, Confidence C)
+ : CausingUseFact(UF), ConfidenceLevel(C) {}
+
+ bool operator==(const LivenessInfo &Other) const {
+ return CausingUseFact == Other.CausingUseFact &&
+ ConfidenceLevel == Other.ConfidenceLevel;
+ }
+ bool operator!=(const LivenessInfo &Other) const { return !(*this == Other);
}
+
+ void Profile(llvm::FoldingSetNodeID &IDBuilder) const {
+ IDBuilder.AddPointer(CausingUseFact);
+ IDBuilder.Add(ConfidenceLevel);
+ }
+};
+
+using LivenessMap = llvm::ImmutableMap<OriginID, LivenessInfo>;
+
+/// The dataflow lattice for origin liveness analysis.
+/// It tracks which origins are live, why they're live (which UseFact),
+/// and the confidence level of that liveness.
+struct LivenessLattice {
+ LivenessMap LiveOrigins;
+
+ LivenessLattice() : LiveOrigins(nullptr) {};
- ExpiredLattice() : Expired(nullptr) {};
- explicit ExpiredLattice(ExpiredLoanMap M) : Expired(M) {}
+ explicit LivenessLattice(LivenessMap L) : LiveOrigins(L) {}
- bool operator==(const ExpiredLattice &Other) const {
- return Expired == Other.Expired;
+ bool operator==(const LivenessLattice &Other) const {
+ return LiveOrigins == Other.LiveOrigins;
}
- bool operator!=(const ExpiredLattice &Other) const {
+
+ bool operator!=(const LivenessLattice &Other) const {
return !(*this == Other);
}
- void dump(llvm::raw_ostream &OS) const {
- OS << "ExpiredLattice State:\n";
- if (Expired.isEmpty())
+ void dump(llvm::raw_ostream &OS, const OriginManager &OM) const {
+ if (LiveOrigins.isEmpty())
OS << " <empty>\n";
- for (const auto &[ID, _] : Expired)
- OS << " Loan " << ID << " is expired\n";
+ for (const auto &Entry : LiveOrigins) {
+ OriginID OID = Entry.first;
+ const LivenessInfo &Info = Entry.second;
+ OS << " ";
+ OM.dump(OID, OS);
+ OS << " is ";
+ switch (Info.ConfidenceLevel) {
+ case Confidence::Definite:
+ OS << "definitely";
+ break;
+ case Confidence::Maybe:
+ OS << "maybe";
+ break;
+ case Confidence::None:
+ llvm_unreachable("liveness condidence should not be none.");
+ }
+ OS << " live at this point\n";
+ }
}
};
-/// The analysis that tracks which loans have expired.
-class ExpiredLoansAnalysis
- : public DataflowAnalysis<ExpiredLoansAnalysis, ExpiredLattice,
- Direction::Forward> {
-
- ExpiredLoanMap::Factory &Factory;
+/// The analysis that tracks which origins are live, with granular information
+/// about the causing use fact and confidence level. This is a backward
+/// analysis.
+class LiveOriginAnalysis
+ : public DataflowAnalysis<LiveOriginAnalysis, LivenessLattice,
+ Direction::Backward> {
+ FactManager &FactMgr;
+ LivenessMap::Factory &Factory;
public:
- ExpiredLoansAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
- LifetimeFactory &Factory)
- : DataflowAnalysis(C, AC, F), Factory(Factory.ExpiredLoanMapFactory) {}
-
- using Base::transfer;
+ LiveOriginAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F,
+ LivenessMap::Factory &SF)
+ : DataflowAnalysis(C, AC, F), FactMgr(F), Factory(SF) {}
+ using DataflowAnalysis<LiveOriginAnalysis, Lattice,
+ Direction::Backward>::transfer;
- StringRef getAnalysisName() const { return "ExpiredLoans"; }
+ StringRef getAnalysisName() const { return "LiveOrigins"; }
Lattice getInitialState() { return Lattice(Factory.getEmptyMap()); }
- /// Merges two lattices by taking the union of the two expired loans.
- Lattice join(Lattice L1, Lattice L2) {
- return Lattice(
- utils::join(L1.Expired, L2.Expired, Factory,
- // Take the last expiry fact to make this hermetic.
- [](const ExpireFact *F1, const ExpireFact *F2) {
- return F1->getExpiryLoc() > F2->getExpiryLoc() ? F1 : F2;
- }));
- }
-
- Lattice transfer(Lattice In, const ExpireFact &F) {
- return Lattice(Factory.add(In.Expired, F.getLoanID(), &F));
- }
-
- // Removes the loan from the set of expired loans.
- //
- // When a loan is re-issued (e.g., in a loop), it is no longer considered
- // expired. A loan can be in the expired set at the point of issue due to
- // the dataflow state from a previous loop iteration being propagated along
- // a backedge in the CFG.
- //
- // Note: This has a subtle false-negative though where a loan from previous
- // iteration is not overwritten by a reissue. This needs careful tracking
- // of loans "across iterations" which can be considered for future
- // enhancements.
- //
- // void foo(int safe) {
- // int* p = &safe;
- // int* q = &safe;
- // while (condition()) {
- // int x = 1;
- // p = &x; // A loan to 'x' is issued to 'p' in every iteration.
- // if (condition()) {
- // q = p;
- // }
- // (void)*p; // OK — 'p' points to 'x' from new iteration.
- // (void)*q; // UaF - 'q' still points to 'x' from previous iteration
- // // which is now destroyed.
- // }
- // }
- Lattice transfer(Lattice In, const IssueFact &F) {
- return Lattice(Factory.remove(In.Expired, F.getLoanID()));
+ /// Merges two lattices by combining liveness information.
+ /// When the same origin has different confidence levels, we take the lower
+ /// one.
+ Lattice join(Lattice L1, Lattice L2) const {
+ LivenessMap Merged = L1.LiveOrigins;
+ // Take the earliest UseFact to make this hermetic.
+ auto CombineUseFact = [](const UseFact *A,
+ const UseFact *B) -> const UseFact * {
+ return A->getUseExpr()->getExprLoc() < B->getUseExpr()->getExprLoc() ? A
+ : B;
+ };
+ auto CombineConfidence = [](Confidence C1, Confidence C2) -> Confidence {
+ // Only return Definite if both paths are Definite, otherwise Maybe.
+ if (C1 == Confidence::Definite && C2 == Confidence::Definite)
----------------
usx95 wrote:
Added an assertion. I would prefer not to reply on their enum values and be
explicit for clarity.
https://github.com/llvm/llvm-project/pull/159991
_______________________________________________
llvm-branch-commits mailing list
llvm-branch-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
