Static Value-Flow Analysis
Loading...
Searching...
No Matches
SVF::SemiSparseAbstractInterpretation Class Reference

#include <SparseAbstractInterpretation.h>

Inheritance diagram for SVF::SemiSparseAbstractInterpretation:
SVF::AbstractInterpretation SVF::FullSparseAbstractInterpretation

Public Member Functions

 SemiSparseAbstractInterpretation ()
 ~SemiSparseAbstractInterpretation () override=default
Public Member Functions inherited from SVF::AbstractInterpretation
virtual void runOnModule ()
virtual ~AbstractInterpretation ()
 Destructor.
void analyse ()
 Program entry.
void analyzeFromAllProgEntries ()
 Analyze all entry points (functions without callers).
FIFOWorkList< const FunObjVar * > collectProgEntryFuns ()
 Get all entry point functions (functions without callers).
void addDetector (std::unique_ptr< AEDetector > detector)
const SVFVar * getSVFVar (NodeID varId) const
 Retrieve SVFVar given its ID; asserts if no such variable exists.
AbstractState & getAbsState (const ICFGNode *node)
bool hasAbsState (const ICFGNode *node)
void getAbsState (const Set< const ValVar * > &vars, AbstractState &result, const ICFGNode *node)
void getAbsState (const Set< const ObjVar * > &vars, AbstractState &result, const ICFGNode *node)
void getAbsState (const Set< const SVFVar * > &vars, AbstractState &result, const ICFGNode *node)
IntervalValue getGepElementIndex (const GepStmt *gep)
IntervalValue getGepByteOffset (const GepStmt *gep)
AddressValue getGepObjAddrs (const ValVar *pointer, IntervalValue offset)
virtual AbstractValue loadValue (const ValVar *pointer, const ICFGNode *node)
 Read memory through the pointer's address targets.
virtual void storeValue (const ValVar *pointer, const AbstractValue &val, const ICFGNode *node)
const SVFType * getPointeeElement (const ObjVar *var, const ICFGNode *node)
AllocationSizeBounds getAllocaInstByteSize (const AddrStmt *addr)
Map< const ICFGNode *, AbstractState > & getTrace ()
AbstractState & operator[] (const ICFGNode *node)

Protected Member Functions

AbstractState getFullCycleHeadState (const ICFGCycleWTO *cycle) override
bool widenCycleState (const AbstractState &prev, const AbstractState &cur, const ICFGCycleWTO *cycle) override
bool narrowCycleState (const AbstractState &prev, const AbstractState &cur, const ICFGCycleWTO *cycle) override
const AbstractValue & getAbsValue (const ValVar *var, const ICFGNode *node) override
bool hasAbsValue (const ValVar *var, const ICFGNode *node) const override
 Side-effect-free existence check.
void updateAbsValue (const ValVar *var, const AbstractValue &val, const ICFGNode *node) override
void updateAbsState (const ICFGNode *node, const AbstractState &state) override
void joinStates (AbstractState &dst, const AbstractState &src) override
const ICFGNode * getICFGNode (const ValVar *var) const
virtual const AbstractValue & getAbsValue (const ObjVar *var, const ICFGNode *node)
virtual const AbstractValue & getAbsValue (const SVFVar *var, const ICFGNode *node)
virtual bool hasAbsValue (const ObjVar *var, const ICFGNode *node) const
virtual bool hasAbsValue (const SVFVar *var, const ICFGNode *node) const
virtual void updateAbsValue (const ObjVar *var, const AbstractValue &val, const ICFGNode *node)
virtual void updateAbsValue (const SVFVar *var, const AbstractValue &val, const ICFGNode *node)
Protected Member Functions inherited from SVF::AbstractInterpretation
 AbstractInterpretation ()
bool isStrongUpdate (const AddressValue &targets, const AbstractState &state) const
virtual bool mergeStatesFromPredecessors (const ICFGNode *node)
bool isBranchEdgeFeasible (const IntraCFGEdge *edge, AbstractState &as)
bool applyBranchRefinement (const IntraCFGEdge *edge, AbstractState &as)
bool shouldApplyNarrowing (const FunObjVar *fun)
 Check if narrowing should be applied: always for regular loops, mode-dependent for recursion.

Additional Inherited Members

Public Types inherited from SVF::AbstractInterpretation
enum  AESparsity { Dense , SemiSparse , Sparse }
enum  HandleRecur { TOP , WIDEN_ONLY , WIDEN_NARROW }
enum  AEFunEntryMode { MAIN , NO_MAIN }
Static Public Member Functions inherited from SVF::AbstractInterpretation
static AbstractInterpretation & getAEInstance ()
Protected Attributes inherited from SVF::AbstractInterpretation
SVFIR * svfir {nullptr}
 Data and helpers reachable from SparseAbstractInterpretation.
AEWTO * preAnalysis {nullptr}
Map< const ICFGNode *, AbstractState > abstractTrace
 per-node trace; owned here

Detailed Description

Abstract Interpretation for Options::AESparsity::SemiSparse.

ValVars live at their SVFG-style def-sites: reads pull from there, writes go there, state merges replace only the ObjVar map and skip the ValVar map, and the cycle helpers gather/scatter cycle ValVars around each widening iteration.

Definition at line 41 of file SparseAbstractInterpretation.h.

Constructor & Destructor Documentation

◆ SemiSparseAbstractInterpretation()

SVF::SemiSparseAbstractInterpretation::SemiSparseAbstractInterpretation ( )
inline

Definition at line 44 of file SparseAbstractInterpretation.h.

45 {
46 preAnalysis->initCycleValVars();
47 }

◆ ~SemiSparseAbstractInterpretation()

SVF::SemiSparseAbstractInterpretation::~SemiSparseAbstractInterpretation ( )
overridedefault

Member Function Documentation

◆ getAbsValue() [1/3]

const AbstractValue & AbstractInterpretation::getAbsValue ( const ObjVar * var,
const ICFGNode * node )
protectedvirtual

Reimplemented from SVF::AbstractInterpretation.

Definition at line 143 of file AbstractStateManager.cpp.

94{
95 AbstractState& as = getAbsState(node);
97 return as.load(addr);
98}
AbstractState & getAbsState(const ICFGNode *node)
virtual AbstractValue & load(u32_t addr)
static u32_t getVirtualMemAddress(u32_t idx)
The physical address starts with 0x7f...... + idx.
NodeID getId() const
Get ID.
Definition SVFValue.h:158
unsigned u32_t
Definition GeneralType.h:67

◆ getAbsValue() [2/3]

const AbstractValue & AbstractInterpretation::getAbsValue ( const SVFVar * var,
const ICFGNode * node )
protectedvirtual

Reimplemented from SVF::AbstractInterpretation.

Definition at line 144 of file AbstractStateManager.cpp.

101{
102 if (const ObjVar* objVar = SVFUtil::dyn_cast<ObjVar>(var))
103 return getAbsValue(objVar, node);
104 if (const ValVar* valVar = SVFUtil::dyn_cast<ValVar>(var))
105 return getAbsValue(valVar, node);
106 assert(false && "Unknown SVFVar kind");
107 abort();
108}
const AbstractValue & getAbsValue(const ValVar *var, const ICFGNode *node) override
LLVM_NODISCARD std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition Casting.h:405

◆ getAbsValue() [3/3]

const AbstractValue & SemiSparseAbstractInterpretation::getAbsValue ( const ValVar * var,
const ICFGNode * node )
overrideprotectedvirtual

Read a top-level variable's abstract value. Dense base does a direct trace lookup; sparse subclasses override with their own resolution chain (def-site walk, call-result fallback, etc.). All three overloads are virtual so full-sparse can route ObjVar reads through the SVFG.

Dense base: direct trace lookup, with a type-directed top value for genuinely missing entries (e.g. function parameters never written before first read). Sparse subclasses override with a def-site resolution chain.

The "in map" check is a raw map.count — NOT inVarToValTable / inVarToAddrsTable, which gate on isInterval / isAddr. SVF canonically represents uninit and null-pointer shapes as (interval=bottom ∧ addrs=∅); those predicates would falsely report such an entry as "not present", and the top fallback below would then clobber the very signal NullptrDerefDetector::isUninit keys off.

Reimplemented from SVF::AbstractInterpretation.

Definition at line 253 of file SparseAbstractInterpretation.cpp.

255{
256 // Read from the var's def-site (where updateAbsValue wrote it).
258}
virtual const AbstractValue & getAbsValue(const ValVar *var, const ICFGNode *node)
const ICFGNode * getICFGNode(const ValVar *var) const

◆ getFullCycleHeadState()

AbstractState SemiSparseAbstractInterpretation::getFullCycleHeadState ( const ICFGCycleWTO * cycle)
overrideprotectedvirtual

Build a full cycle-head AbstractState. Dense default: trace[cycle_head] as-is. Semi-sparse subclass: also pull cycle ValVars from def-sites.

Reimplemented from SVF::AbstractInterpretation.

Definition at line 125 of file SparseAbstractInterpretation.cpp.

127{
128 // Start from the dense snapshot (ObjVars + any ValVars that happen to
129 // be cached at cycle_head's trace entry).
130 AbstractState snap = AbstractInterpretation::getFullCycleHeadState(cycle);
131
132 const Set<const ValVar*>& valVars = preAnalysis->getCycleValVars(cycle);
133 if (valVars.empty())
134 return snap; // no cycle ValVars known: nothing to pull
135
136 // Drop stale ValVar entries and pull each cycle ValVar from its
137 // def-site. ValVars without a genuine stored value are skipped to
138 // avoid getAbsValue's top-fallback contaminating body def-sites on
139 // the subsequent widen/narrow scatter.
140 snap.clearValVars();
141 for (const ValVar* v : valVars)
142 {
143 const ICFGNode* defSite = v->getICFGNode();
144 if (!defSite || !hasAbsValue(v, defSite))
145 continue;
146 snap[v->getId()] = getAbsValue(v, defSite);
147 }
148 return snap;
149}
virtual AbstractState getFullCycleHeadState(const ICFGCycleWTO *cycle)
bool hasAbsValue(const ValVar *var, const ICFGNode *node) const override
Side-effect-free existence check.
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
Definition GeneralType.h:51

◆ getICFGNode()

const ICFGNode * SemiSparseAbstractInterpretation::getICFGNode ( const ValVar * var) const
protected

Definition at line 221 of file SparseAbstractInterpretation.cpp.

223{
224 // const ValVars are all defined in global node
225 if (!var->getICFGNode())
226 {
227 return svfir->getICFG()->getGlobalICFGNode();
228 }
229 // for return value of callsite, use the ret-site as def-site
230 else if (SVFUtil::isa<CallICFGNode>(var->getICFGNode()) &&
232 {
234 ->getRetICFGNode();
235 }
236 // for other ValVars, use their def-site as the node to query abstract
237 // value.
238 else
239 {
240 return var->getICFGNode();
241 }
242}
SVFIR * svfir
Data and helpers reachable from SparseAbstractInterpretation.
const ICFGNode * getICFGNode() const
LLVM_NODISCARD bool isa(const Y &Val)
Definition Casting.h:241

◆ hasAbsValue() [1/3]

bool AbstractInterpretation::hasAbsValue ( const ObjVar * var,
const ICFGNode * node ) const
protectedvirtual

Reimplemented from SVF::AbstractInterpretation.

Definition at line 148 of file AbstractStateManager.cpp.

123{
124 auto it = abstractTrace.find(node);
125 if (it == abstractTrace.end())
126 return false;
127 return it->second.getLocToVal().count(var->getId()) != 0;
128}
Map< const ICFGNode *, AbstractState > abstractTrace
per-node trace; owned here

◆ hasAbsValue() [2/3]

bool AbstractInterpretation::hasAbsValue ( const SVFVar * var,
const ICFGNode * node ) const
protectedvirtual

Reimplemented from SVF::AbstractInterpretation.

Definition at line 149 of file AbstractStateManager.cpp.

131{
132 if (const ObjVar* objVar = SVFUtil::dyn_cast<ObjVar>(var))
133 return hasAbsValue(objVar, node);
134 if (const ValVar* valVar = SVFUtil::dyn_cast<ValVar>(var))
135 return hasAbsValue(valVar, node);
136 return false;
137}

◆ hasAbsValue() [3/3]

bool SemiSparseAbstractInterpretation::hasAbsValue ( const ValVar * var,
const ICFGNode * node ) const
overrideprotectedvirtual

Side-effect-free existence check.

Dense base: direct existence check at node. Mirrors the simplified getAbsValue lookup — uses raw map.contains rather than inVar*Table predicates, which would falsely report neutral (interval=bottom ∧ addrs=∅) entries as "not present".

Reimplemented from SVF::AbstractInterpretation.

Definition at line 260 of file SparseAbstractInterpretation.cpp.

262{
264}
virtual bool hasAbsValue(const ValVar *var, const ICFGNode *node) const
Side-effect-free existence check.

◆ joinStates()

void SemiSparseAbstractInterpretation::joinStates ( AbstractState & dst,
const AbstractState & src )
overrideprotectedvirtual

Join src into dst with sparsity-aware semantics. Dense merges everything; semi-sparse skips ValVars.

Reimplemented from SVF::AbstractInterpretation.

Definition at line 201 of file SparseAbstractInterpretation.cpp.

203{
204 // ValVars live at def-sites in semi-sparse mode; they don't flow
205 // through state merges. Iterate src's ObjVar (_addrToAbsVal) entries
206 // directly and join into dst, leaving dst's ValVar map untouched.
207 // _freedAddrs (used by the null-deref detector) also rides along
208 // ICFG edges — there is no SVFG-level encoding of free events.
209 for (const auto& [id, val] : src.getLocToVal())
210 {
212 if (dst.getLocToVal().count(id))
213 dst.load(addr).join_with(val);
214 else
215 dst.store(addr, val);
216 }
217 for (NodeID a : src.getFreedAddrs())
218 dst.addToFreedAddrs(a);
219}
cJSON * a
Definition cJSON.cpp:2560
const AddrToAbsValMap & getLocToVal() const
get loc2val map
void store(u32_t addr, const AbstractValue &val)
const Set< NodeID > & getFreedAddrs() const
void addToFreedAddrs(NodeID addr)
void join_with(const AbstractValue &other)
u32_t NodeID
Definition GeneralType.h:76

◆ narrowCycleState()

bool SemiSparseAbstractInterpretation::narrowCycleState ( const AbstractState & prev,
const AbstractState & cur,
const ICFGCycleWTO * cycle )
overrideprotectedvirtual

Narrow prev with cur; write the narrowed state back. Returns true when narrowing is disabled or the narrowed state equals prev. Semi-sparse subclass scatters the narrowed ValVars on non-fixpoint.

Reimplemented from SVF::AbstractInterpretation.

Definition at line 169 of file SparseAbstractInterpretation.cpp.

171{
172 // Delegate to base. It returns true on the two non-scatter cases
173 // (narrowing disabled, or narrow fixpoint); we preserve the original
174 // "skip scatter at fixpoint" semantics by bailing early here.
175 bool fixpoint = AbstractInterpretation::narrowCycleState(prev, cur, cycle);
176 if (fixpoint)
177 return true;
178
179 // Non-fixpoint: base wrote the narrowed state to trace. Scatter the
180 // narrowed ValVars back to def-sites.
181 const ICFGNode* cycle_head = cycle->head()->getICFGNode();
182 const AbstractState& next = abstractTrace[cycle_head];
183 for (const auto& [id, val] : next.getVarToVal())
184 updateAbsValue(svfir->getSVFVar(id), val, cycle_head);
185 return false;
186}
item next
Definition cJSON.cpp:2224
newitem prev
Definition cJSON.cpp:2285
virtual bool narrowCycleState(const AbstractState &prev, const AbstractState &cur, const ICFGCycleWTO *cycle)
void updateAbsValue(const ValVar *var, const AbstractValue &val, const ICFGNode *node) override
const WTONode< GraphT > * head() const
Return the head of the cycle.
Definition WTO.h:411
const NodeT * getICFGNode() const
Return the graph node.
Definition WTO.h:343

◆ updateAbsState()

void SemiSparseAbstractInterpretation::updateAbsState ( const ICFGNode * node,
const AbstractState & state )
overrideprotectedvirtual

Replace the state at node. Sparse subclasses replace only the ObjVar map (ValVars live at def-sites).

Reimplemented from SVF::AbstractInterpretation.

Definition at line 193 of file SparseAbstractInterpretation.cpp.

195{
196 // Only replace ObjVar state. ValVars live at their def-sites and
197 // must not be overwritten when the predecessor's state is merged in.
198 abstractTrace[node].updateAddrStateOnly(state);
199}

◆ updateAbsValue() [1/3]

void AbstractInterpretation::updateAbsValue ( const ObjVar * var,
const AbstractValue & val,
const ICFGNode * node )
protectedvirtual

Reimplemented from SVF::AbstractInterpretation.

Definition at line 154 of file AbstractStateManager.cpp.

145{
146 AbstractState& as = getAbsState(node);
148 as.store(addr, val);
149}

◆ updateAbsValue() [2/3]

void AbstractInterpretation::updateAbsValue ( const SVFVar * var,
const AbstractValue & val,
const ICFGNode * node )
protectedvirtual

Reimplemented from SVF::AbstractInterpretation.

Definition at line 155 of file AbstractStateManager.cpp.

152{
153 if (const ObjVar* objVar = SVFUtil::dyn_cast<ObjVar>(var))
154 updateAbsValue(objVar, val, node);
155 else if (const ValVar* valVar = SVFUtil::dyn_cast<ValVar>(var))
156 updateAbsValue(valVar, val, node);
157 else
158 assert(false && "Unknown SVFVar kind");
159}

◆ updateAbsValue() [3/3]

void SemiSparseAbstractInterpretation::updateAbsValue ( const ValVar * var,
const AbstractValue & val,
const ICFGNode * node )
overrideprotectedvirtual

Write a variable's abstract value. Sparse subclasses re-route ValVar writes to the def-site.

Reimplemented from SVF::AbstractInterpretation.

Definition at line 244 of file SparseAbstractInterpretation.cpp.

247{
248 // Write to the var's def-site so getAbsValue stays consistent.
249 const ICFGNode* defNode = var->getICFGNode();
250 abstractTrace[defNode ? defNode : node][var->getId()] = val;
251}

◆ widenCycleState()

bool SemiSparseAbstractInterpretation::widenCycleState ( const AbstractState & prev,
const AbstractState & cur,
const ICFGCycleWTO * cycle )
overrideprotectedvirtual

Widen prev with cur; write the widened state to trace[cycle_head]. Returns true when next == prev (fixpoint). Semi-sparse subclass additionally scatters ValVars to their def-sites.

Reimplemented from SVF::AbstractInterpretation.

Definition at line 151 of file SparseAbstractInterpretation.cpp.

153{
154 // Base widens, writes trace[cycle_head], and returns fixpoint bool.
155 bool fixpoint = AbstractInterpretation::widenCycleState(prev, cur, cycle);
156
157 // Scatter the widened ValVars back to their def-sites so body nodes
158 // observe the widened values on the next iteration. Matches the
159 // pre-refactor semantics: scatter unconditionally, including at
160 // widening fixpoint (see the narrowing-starts-with-stale-body issue
161 // fixed by always writing widened state back).
162 const ICFGNode* cycle_head = cycle->head()->getICFGNode();
163 const AbstractState& next = abstractTrace[cycle_head];
164 for (const auto& [id, val] : next.getVarToVal())
165 updateAbsValue(svfir->getSVFVar(id), val, cycle_head);
166 return fixpoint;
167}
virtual bool widenCycleState(const AbstractState &prev, const AbstractState &cur, const ICFGCycleWTO *cycle)

The documentation for this class was generated from the following files: