SymHeap Class Reference

extension of SymHeapCore dealing with abstract objects (list segments etc.) More...

#include <symheap.hh>

Inheritance diagram for SymHeap:

Collaboration diagram for SymHeap:

Public Member Functions
	SymHeap (TStorRef, Trace::Node *)
	create an empty symbolic heap
virtual	~SymHeap ()
	destruction of the symbolic heap invalidates all IDs of its entities
	SymHeap (const SymHeap &)
	relatively cheap operation as long as SH_COPY_ON_WRITE is enabled
SymHeap &	operator= (const SymHeap &)
	relatively cheap operation as long as SH_COPY_ON_WRITE is enabled
virtual void	swap (SymHeapCore &)
	exchange the contents with the other heap (works in constant time)
EObjKind	objKind (TObjId) const
	kind of object (region, SLS, DLS, ...)
const BindingOff &	segBinding (TObjId seg) const
	tuple of binding offsets (next, prev, ...)
void	objSetAbstract (TObjId seg, EObjKind kind, const BindingOff &off)
	set properties of an abstract object, set abstract if not already
void	objSetConcrete (TObjId)
	set the given abstract object to be a concrete object (drops props)
TMinLen	segMinLength (TObjId seg) const
	read the minimal segment length of the given abstract object
void	segSetMinLength (TObjId seg, TMinLen len)
	assign the minimal segment length of the given abstract object
virtual void	objInvalidate (TObjId)
	invalidate the given object
virtual TObjId	objClone (TObjId)
	clone the given object, including the outgoing has-value edges
TStorRef	stor () const
	each symbolic heap is associated with a CodeStorage model of code
Trace::Node *	traceNode () const
	each symbolic heap is associated with a trace graph node
void	traceUpdate (Trace::Node *)
	update the current trace graph node that the heap is associated with
unsigned	lastId () const
	the last assigned ID of a heap entity (not necessarily still valid)
void	usedBy (FldList &dst, TValId val, bool liveOnly=false) const
	collect all objects having the given value inside
unsigned	usedByCount (TValId val) const
	return how many objects have the value inside
void	pointedBy (FldList &dst, TObjId) const
	return all objects that point at/inside the given object
unsigned	pointedByCount (TObjId) const
	return how many objects point at/inside the given object
void	writeUniformBlock (TObjId obj, const UniformBlock &ub, TValSet *killedPtrs=0)
	write an uninitialized or nullified block of memory
void	copyBlockOfRawMemory (TValId dst, TValId src, TSizeOf size, TValSet *killedPtrs=0)
	copy 'size' bytes of raw memory from 'src' to 'dst'
void	addNeq (TValId v1, TValId v2)
	define an explicit Neq predicate
void	delNeq (TValId v1, TValId v2)
	remove an explicit Neq predicate if defined
bool	chkNeq (TValId v1, TValId v2) const
	true if there is an explicit Neq relation over the given values
void	gatherRelatedValues (TValList &dst, TValId val) const
	collect values connect with the given value via an extra predicate
void	copyRelevantPreds (SymHeapCore &dst, const TValMap &valMap) const
	transfer as many as possible extra heap predicates from this to dst
bool	matchPreds (const SymHeapCore &ref, const TValMap &valMap, bool nonZeroOnly=false) const
	true if all Neq predicates can be mapped to Neq predicates in ref
TValId	valByOffset (TValId, TOffset offset)
	translate the given address by the given offset
TValId	valByRange (TValId at, IR::Range range)
	create (or recycle) a VT_RANGE value at the given allocated address
TValId	valShift (TValId valToShift, TValId shiftBy)
	translate the given value by the given offset
EValueTarget	valTarget (TValId) const
	classify the object the given value points to
EValueOrigin	valOrigin (TValId) const
	classify where the given value originates from
ETargetSpecifier	targetSpec (TValId addr) const
	return the target specifier of the given address
TObjId	objByAddr (TValId addr) const
	return the object that the given address points to
EStorageClass	objStorClass (TObjId) const
	classify the storage class of the given object
TSizeRange	objSize (TObjId) const
	return size (in bytes) of the given object
TValId	addrOfTarget (TObjId, ETargetSpecifier, TOffset off=0)
	target address at the given object with target specifier and offset
TValId	valRoot (TValId) const
	return the address of the root which the given value is binded to
TOffset	valOffset (TValId) const
	return the relative placement from the root
IR::Range	valOffsetRange (TValId) const
	return the offset range associated with the given VT_RANGE value
void	valRestrictRange (TValId, IR::Range win)
	narrow down the offset range of the given VT_RANGE value
TValId	diffPointers (TValId v1, TValId v2)
	difference between two pointers (makes sense only for shared roots)
TSizeRange	valSizeOfString (TValId) const
	return count of bytes (including NULL) we can safely read as string
TObjId	regionByVar (CVar, bool createIfNeeded)
	return the region corresponding to the given program variable
virtual void	valReplace (TValId val, TValId replaceBy)
	replace all occurrences of val by replaceBy
void	gatherObjects (TObjList &dst, bool(*)(EStorageClass)=0) const
	return the list of objects satisfying the given filtering predicate
void	gatherLiveFields (FldList &dst, TObjId) const
	list of live fields (including ptrs) inside the given object
void	gatherUniformBlocks (TUniBlockMap &dst, TObjId) const
	list of uninitialized and nullified uniform blocks of the given obj
bool	findCoveringUniBlocks (TUniBlockMap *pCovered, TObjId root, UniformBlock block) const
	experimental optimization of joinUniBlocksCore()
CVar	cVarByObject (TObjId) const
	return program variable that the given object maps to
TFldId	valGetComposite (TValId val) const
	composite object given by val (applicable only on VT_COMPOSITE vals)
TObjId	stackAlloc (const TSizeRange &size, const CallInst &from)
	allocate a chunk of stack of known size from the select call stack
bool	isAnonStackObj (TObjId, CallInst *pFrom=0)
	return true if the given object was allocated by stackAlloc()
void	clearAnonStackObjects (TObjList &dst, const CallInst &of)
	clear the list of anonymous stack objects of the given call instance
TObjId	heapAlloc (const TSizeRange &size)
	allocate a chunk of heap of known size
bool	isValid (TObjId) const
	return true if the given object can be still accessed safely
void	objSetEstimatedType (TObjId obj, TObjType clt)
	update the estimated type-info of the given object
TObjType	objEstimatedType (TObjId obj) const
	return the estimated type-info of the given object
TValId	valCreate (EValueTarget code, EValueOrigin origin)
	create a generic value, otherwise use addrOfTarget()
TValId	valWrapCustom (CustomValue data)
	wrap a custom value, such as integer literal, or code pointer
const CustomValue &	valUnwrapCustom (TValId) const
	unwrap a custom value, such as integer literal, or code pointer
TProtoLevel	objProtoLevel (TObjId) const
	prototype level of the given object (0 means not a prototype)
void	objSetProtoLevel (TObjId obj, TProtoLevel level)
	set prototype level of the given boject (0 means not a prototype)

Protected Member Functions
TFldId	ptrLookup (TObjId obj, TOffset off)
	return a data pointer inside the given object at the given offset
TFldId	fldLookup (TObjId obj, TOffset off, TObjType clt)
	return a field of the specified type at the specified offset in obj
void	fldEnter (TFldId)
	increment the external reference count of the given object
void	fldLeave (TFldId)
	decrement the external reference count (may trigger its destruction)
TValId	valueOf (TFldId fld)
TValId	placedAt (TFldId fld)
TObjId	objByField (TFldId fld) const
TOffset	fieldOffset (TFldId fld) const
TObjType	fieldType (TFldId fld) const
void	setValOfField (TFldId fld, TValId val, TValSet *killedPtrs=0)

Protected Attributes
TStorRef	stor_

Private Attributes
Private *	d

Detailed Description

extension of SymHeapCore dealing with abstract objects (list segments etc.)

Definition at line 827 of file symheap.hh.

Constructor & Destructor Documentation

SymHeap	(	TStorRef	,
		Trace::Node *
	)

create an empty symbolic heap

virtual ~SymHeap ( )

virtual

destruction of the symbolic heap invalidates all IDs of its entities

SymHeap

(

const SymHeap &

)

relatively cheap operation as long as SH_COPY_ON_WRITE is enabled

Member Function Documentation

void addNeq ( TValId  v1, TValId  v2  )

inherited

define an explicit Neq predicate

TValId addrOfTarget ( TObjId  , ETargetSpecifier  , TOffset  off = 0  )

inherited

target address at the given object with target specifier and offset

Referenced by segHeadAt().

bool chkNeq ( TValId  v1, TValId  v2  ) const

inherited

true if there is an explicit Neq relation over the given values

void clearAnonStackObjects ( TObjList &  dst, const CallInst &  of  )

inherited

clear the list of anonymous stack objects of the given call instance

void copyBlockOfRawMemory ( TValId  dst, TValId  src, TSizeOf  size, TValSet *  killedPtrs = 0  )

inherited

copy 'size' bytes of raw memory from 'src' to 'dst'

void copyRelevantPreds ( SymHeapCore &  dst, const TValMap &  valMap  ) const

inherited

transfer as many as possible extra heap predicates from this to dst

CVar cVarByObject ( TObjId  ) const

inherited

return program variable that the given object maps to

Referenced by gatherProgramVarsCore(), and traverseProgramVarsGeneric().

void delNeq ( TValId  v1, TValId  v2  )

inherited

remove an explicit Neq predicate if defined

TValId diffPointers ( TValId  v1, TValId  v2  )

inherited

difference between two pointers (makes sense only for shared roots)

TOffset fieldOffset ( TFldId  fld ) const

protectedinherited

Referenced by FldHandle::offset().

TObjType fieldType ( TFldId  fld ) const

protectedinherited

Referenced by FldHandle::type().

bool findCoveringUniBlocks ( TUniBlockMap *  pCovered, TObjId  root, UniformBlock  block  ) const

inherited

experimental optimization of joinUniBlocksCore()

void fldEnter ( TFldId  )

protectedinherited

increment the external reference count of the given object

Referenced by FldHandle::FldHandle(), FldHandle::operator=(), and PtrHandle::PtrHandle().

void fldLeave ( TFldId  )

protectedinherited

decrement the external reference count (may trigger its destruction)

Referenced by FldHandle::operator=(), and FldHandle::~FldHandle().

TFldId fldLookup ( TObjId  obj, TOffset  off, TObjType  clt  )

protectedinherited

return a field of the specified type at the specified offset in obj

void gatherLiveFields ( FldList &  dst, TObjId    ) const

inherited

list of live fields (including ptrs) inside the given object

Referenced by traverseLiveFieldsGeneric().

void gatherObjects ( TObjList &  dst, bool(*)(EStorageClass)  = 0  ) const

inherited

return the list of objects satisfying the given filtering predicate

Referenced by gatherProgramVarsCore(), and traverseProgramVarsGeneric().

void gatherRelatedValues ( TValList &  dst, TValId  val  ) const

inherited

collect values connect with the given value via an extra predicate

void gatherUniformBlocks ( TUniBlockMap &  dst, TObjId    ) const

inherited

list of uninitialized and nullified uniform blocks of the given obj

TObjId heapAlloc ( const TSizeRange &  size )

inherited

allocate a chunk of heap of known size

bool isAnonStackObj ( TObjId  , CallInst *  pFrom = 0  )

inherited

return true if the given object was allocated by stackAlloc()

bool isValid ( TObjId  ) const

inherited

return true if the given object can be still accessed safely

Referenced by isPossibleToDeref(), nextObj(), and objMinLength().

unsigned lastId ( ) const

inherited

the last assigned ID of a heap entity (not necessarily still valid)

bool matchPreds ( const SymHeapCore &  ref, const TValMap &  valMap, bool  nonZeroOnly = false  ) const

inherited

true if all Neq predicates can be mapped to Neq predicates in ref

TObjId objByAddr ( TValId  addr ) const

inherited

return the object that the given address points to

Referenced by LeakMonitor::collectJunkFrom(), isPossibleToDeref(), and nextObj().

TObjId objByField ( TFldId  fld ) const

protectedinherited

Referenced by FldHandle::obj().

virtual TObjId objClone ( TObjId  )

virtual

clone the given object, including the outgoing has-value edges

Reimplemented from SymHeapCore.

TObjType objEstimatedType ( TObjId  obj ) const

inherited

return the estimated type-info of the given object

virtual void objInvalidate ( TObjId  )

virtual

invalidate the given object

Reimplemented from SymHeapCore.

EObjKind objKind

(

TObjId

)

const

kind of object (region, SLS, DLS, ...)

Referenced by buildIgnoreList(), headOffset(), isAbstractObject(), nextPtrFromSeg(), nextValFromSeg(), objMinLength(), prevPtrFromSeg(), and segHeadAt().

TProtoLevel objProtoLevel ( TObjId  ) const

inherited

prototype level of the given object (0 means not a prototype)

void objSetAbstract	(	TObjId	seg,
		EObjKind	kind,
		const BindingOff &	off
	)

set properties of an abstract object, set abstract if not already

void objSetConcrete

(

TObjId

)

set the given abstract object to be a concrete object (drops props)

void objSetEstimatedType ( TObjId  obj, TObjType  clt  )

inherited

update the estimated type-info of the given object

void objSetProtoLevel ( TObjId  obj, TProtoLevel  level  )

inherited

set prototype level of the given boject (0 means not a prototype)

TSizeRange objSize ( TObjId  ) const

inherited

return size (in bytes) of the given object

Referenced by traverseProgramVarsGeneric().

EStorageClass objStorClass ( TObjId  ) const

inherited

classify the storage class of the given object

SymHeap& operator=

(

const SymHeap &

)

relatively cheap operation as long as SH_COPY_ON_WRITE is enabled

TValId placedAt ( TFldId  fld )

protectedinherited

Referenced by FldHandle::placedAt().

void pointedBy ( FldList &  dst, TObjId    ) const

inherited

return all objects that point at/inside the given object

unsigned pointedByCount ( TObjId  ) const

inherited

return how many objects point at/inside the given object

TFldId ptrLookup ( TObjId  obj, TOffset  off  )

protectedinherited

return a data pointer inside the given object at the given offset

TObjId regionByVar ( CVar  , bool  createIfNeeded  )

inherited

return the region corresponding to the given program variable

Referenced by isVarAlive(), and traverseProgramVarsGeneric().

const BindingOff& segBinding

(

TObjId

seg

)

const

tuple of binding offsets (next, prev, ...)

Referenced by buildIgnoreList(), headOffset(), nextPtrFromSeg(), prevPtrFromSeg(), and segHeadAt().

TMinLen segMinLength

(

TObjId

seg

)

const

read the minimal segment length of the given abstract object

Referenced by objMinLength(), and segIncreaseMinLength().

void segSetMinLength	(	TObjId	seg,
		TMinLen	len
	)

assign the minimal segment length of the given abstract object

Referenced by segIncreaseMinLength().

void setValOfField ( TFldId  fld, TValId  val, TValSet *  killedPtrs = 0  )

protectedinherited

Referenced by FldHandle::setValue().

TObjId stackAlloc ( const TSizeRange &  size, const CallInst &  from  )

inherited

allocate a chunk of stack of known size from the select call stack

TStorRef stor ( ) const

inlineinherited

each symbolic heap is associated with a CodeStorage model of code

Definition at line 375 of file symheap.hh.

References SymHeapCore::stor_.

virtual void swap ( SymHeapCore &  )

virtual

exchange the contents with the other heap (works in constant time)

Reimplemented from SymHeapCore.

Referenced by SymState::swapExisting().

ETargetSpecifier targetSpec ( TValId  addr ) const

inherited

return the target specifier of the given address

Trace::Node* traceNode ( ) const

inherited

each symbolic heap is associated with a trace graph node

void traceUpdate ( Trace::Node *  )

inherited

update the current trace graph node that the heap is associated with

void usedBy ( FldList &  dst, TValId  val, bool  liveOnly = false  ) const

inherited

collect all objects having the given value inside

Parameters

dst	reference to a container to store the result to
val	ID of the value to look for
liveOnly	if true, exclude objects that are no longer alive

Note

The operation may return from 0 to n objects.

unsigned usedByCount ( TValId  val ) const

inherited

return how many objects have the value inside

TValId valByOffset ( TValId  , TOffset  offset  )

inherited

translate the given address by the given offset

TValId valByRange ( TValId  at, IR::Range  range  )

inherited

create (or recycle) a VT_RANGE value at the given allocated address

TValId valCreate ( EValueTarget  code, EValueOrigin  origin  )

inherited

create a generic value, otherwise use addrOfTarget()

Referenced by traverseProgramVarsGeneric().

TFldId valGetComposite ( TValId  val ) const

inherited

composite object given by val (applicable only on VT_COMPOSITE vals)

Todo:

should we operate on FldHandle instead?

TOffset valOffset ( TValId  ) const

inherited

return the relative placement from the root

Referenced by areValProtosEqual().

IR::Range valOffsetRange ( TValId  ) const

inherited

return the offset range associated with the given VT_RANGE value

EValueOrigin valOrigin ( TValId  ) const

inherited

classify where the given value originates from

Referenced by areValProtosEqual().

virtual void valReplace ( TValId  val, TValId  replaceBy  )

virtualinherited

replace all occurrences of val by replaceBy

void valRestrictRange ( TValId  , IR::Range  win  )

inherited

narrow down the offset range of the given VT_RANGE value

TValId valRoot ( TValId  ) const

inherited

return the address of the root which the given value is binded to

TValId valShift ( TValId  valToShift, TValId  shiftBy  )

inherited

translate the given value by the given offset

TSizeRange valSizeOfString ( TValId  ) const

inherited

return count of bytes (including NULL) we can safely read as string

EValueTarget valTarget ( TValId  ) const

inherited

classify the object the given value points to

Referenced by areValProtosEqual(), and isPossibleToDeref().

TValId valueOf ( TFldId  fld )

protectedinherited

Referenced by FldHandle::value().

const CustomValue& valUnwrapCustom ( TValId  ) const

inherited

unwrap a custom value, such as integer literal, or code pointer

TValId valWrapCustom ( CustomValue  data )

inherited

wrap a custom value, such as integer literal, or code pointer

void writeUniformBlock ( TObjId  obj, const UniformBlock &  ub, TValSet *  killedPtrs = 0  )

inherited

write an uninitialized or nullified block of memory

Referenced by traverseProgramVarsGeneric().

Field Documentation

Private* d

private

Definition at line 871 of file symheap.hh.

TStorRef stor_

protectedinherited

Definition at line 599 of file symheap.hh.

Referenced by SymHeapCore::stor().

---

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

• symheap.hh