You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by gs...@apache.org on 2007/04/13 20:26:28 UTC
svn commit: r528575 [4/6] - in /harmony/enhanced/drlvm/trunk:
src/test/regression/H3225/ vm/vmcore/include/ vm/vmcore/src/verifier/
Modified: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_graph.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_graph.h?view=diff&rev=528575&r1=528574&r2=528575
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_graph.h (original)
+++ harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_graph.h Fri Apr 13 11:26:27 2007
@@ -17,7 +17,7 @@
/**
* @author Pavel Rebriy, Alexei Fedotov
* @version $Revision: 1.1.2.3.4.4 $
- */
+ */
#ifndef _VERIFIER_GRAPH_H_
@@ -30,70 +30,77 @@
#include "ver_real.h"
/**
- * Initial node mark in verifier graph.
+ * Each node has a descriptive bitmap.
*/
-#define VERIFY_START_MARK 1
+enum vf_NodeType
+{
+ VF_NODE_CODE_RANGE = 0,
+ VF_NODE_START_ENTRY = 1,
+ VF_NODE_END_ENTRY = 2,
+ VF_NODE_HANDLER = 3
+};
+const unsigned ALL_BITS_SET = ~0U;
/**
- * Each node has a descriptive bitmap.
+ * @ingroup Handles
+ * A handle of a stack map vector.
*/
-enum vf_NodeType {
- VF_TYPE_NODE_CODE_RANGE = 0,
- VF_TYPE_NODE_START_ENTRY = 1,
- VF_TYPE_NODE_END_ENTRY = 2,
- VF_TYPE_NODE_HANDLER = 3
-};
-
+typedef const struct vf_MapVector *vf_MapVectorHandle;
/**
* @ingroup Handles
- * The stack map handle vector handle.
+ * A handle of a graph edge.
*/
-typedef const struct vf_MapVector* vf_MapVectorHandle;
+typedef const struct vf_Edge *vf_EdgeHandle;
/**
* @ingroup Handles
- * The handle of the graph node.
+ * A handle of a container.
*/
-typedef const struct vf_Node* vf_NodeHandle;
+typedef const struct vf_Container *vf_ContainerHandle;
/**
* @ingroup Handles
- * The handle of the graph edge.
+ * A subroutine handle.
*/
-typedef const struct vf_Edge* vf_EdgeHandle;
-/// Declaration of enum with a descriptive bitmap.
-typedef enum vf_NodeType vf_NodeType_t;
+typedef const struct vf_Sub *vf_SubHandle;
/**
* Structure of stack map vector.
*/
-struct vf_MapVector {
- vf_MapEntry_t *m_stack; ///< stack map vector
- vf_MapEntry_t *m_local; ///< locals map vector
- unsigned short m_number; ///< number of locals
- unsigned short m_depth; ///< stack depth
- unsigned short m_maxstack; ///< max stack length
- unsigned short m_maxlocal; ///< max local number
+struct vf_MapVector
+{
+ vf_MapEntry *m_stack; ///< stack map vector
+ vf_MapEntry *m_local; ///< locals map vector
+ unsigned short m_number; ///< number of locals
+ unsigned short m_depth; ///< stack depth
};
/**
+ * Node marks are greater or equal to this, zero mark means
+ * unmarked node.
+ */
+const unsigned VF_START_MARK = 1;
+
+/**
* Graph node structure.
*/
struct vf_Node
{
- vf_MapVector m_inMapVector; ///< stack map IN node vector
- vf_MapVector m_outMapVector; ///< stack map OUT node vector
- unsigned m_start; ///< index of the first instruction at vf_Context.m_code
- unsigned m_end; ///< index of the last instruction at vf_Context.m_code
- unsigned m_inedge; ///< the first incoming edge
- unsigned m_outedge; ///< the first outcoming edge
- unsigned m_innum; ///< number of incoming edges
- unsigned m_outnum; ///< number of outcoming edges
- unsigned m_nodecount; ///< node count in enumeration
- int m_stack; ///< stack depth
- int m_mark; ///< node mark
- vf_NodeType_t m_type; ///< node type
- bool m_initialized : 1; ///< reference in a local variable
- ///< should be initialized
+ vf_MapVector m_inmap; ///< stack map IN node vector
+ vf_MapVector m_outmap; ///< stack map OUT node vector
+ vf_InstrHandle m_start; ///< the first instruction
+ vf_InstrHandle m_end; ///< the last instruction
+ vf_EdgeHandle m_inedge; ///< the first incoming edge
+ vf_EdgeHandle m_outedge; ///< the first outcoming edge
+ unsigned m_outnum; ///< a number of outcoming edges
+ unsigned m_nodecount; ///< node count in enumeration
+ ///< 0 for unreachable and start nodes
+ int m_stack; ///< stack depth modifier
+ int m_mark; ///< node mark
+ vf_SubHandle m_sub; ///< if this is a subroutine node, this refers
+ ///< to the corresponding subroutine descriptor
+ vf_NodeType m_type; ///< node type
+ bool m_initialized:1; ///< reference in a local variable
+ ///< should be initialized
};
/**
@@ -101,452 +108,548 @@
*/
struct vf_Edge
{
- unsigned m_start; ///< start edge node
- unsigned m_end; ///< end edge node
- unsigned m_innext; ///< next incoming edge
- unsigned m_outnext; ///< next outcoming edge
+ vf_NodeHandle m_start; ///< start edge node
+ vf_NodeHandle m_end; ///< end edge node
+ vf_EdgeHandle m_innext; ///< next incoming edge
+ vf_EdgeHandle m_outnext; ///< next outcoming edge
};
/**
- * Graph node container structure.
+ * A generic container.
+ */
+struct vf_Container
+{
+ vf_ContainerHandle m_next; ///< next container
+ unsigned m_max; ///< max number of nodes in container
+ unsigned m_used; ///< number of nodes in container
+};
+
+/**
+ * Locates a container for an object by its number.
+ * @param[in] container a container to start a search from
+ * @param[in] n an object number
+ * @param[out] n an object index in a returned container
+ * @return a container
+ */
+static inline vf_ContainerHandle vf_get_container(vf_ContainerHandle
+ container, unsigned &n)
+{
+ while (n >= container->m_max) {
+ n -= container->m_max;
+ container = container->m_next;
+ assert(container);
+ assert(container->m_max);
+ }
+ return container;
+}
+
+/**
+ * Adds a new container to the container list.
+ * @param[in, out] head the first list element
+ * @param[in] new_container a new container to be placed at the end of the list
+ */
+static inline void vf_add_container(vf_ContainerHandle head,
+ vf_ContainerHandle new_container)
+{
+ while (head->m_next) {
+ head = head->m_next;
+ }
+ ((vf_Container *) head)->m_next = new_container;
+}
+
+
+/**
+ * Checks amount of used space for given containers.
+ */
+static inline unsigned vf_used_space(vf_ContainerHandle container)
+{
+ unsigned used = 0;
+
+ for (; container; container = container->m_next) {
+ used += container->m_used;
+ }
+ return used;
+} // vf_used_space
+
+/**
+ * Checks amount of pre-allocated space for given containers.
+ */
+static inline unsigned vf_total_space(vf_ContainerHandle container)
+{
+ unsigned total_space = 0;
+
+ for (; container; container = container->m_next) {
+ total_space += container->m_max;
+ }
+ return total_space;
+} // vf_total_space
+
+
+
+/**
+ * A linked list of containers containing arrays of nodes.
*/
struct vf_NodeContainer
{
- vf_NodeContainer* m_next; ///< next container
- unsigned m_max; ///< max number of nodes in container
- unsigned m_used; ///< number of nodes in container
- vf_Node m_node[1]; ///< array of contained nodes
+ vf_Container container; ///< a container
+ vf_Node m_node[1]; ///< an array of nodes
};
/**
- * Graph edge container structure.
+ * A linked list of containers containing arrays of edges.
*/
struct vf_EdgeContainer
{
- vf_EdgeContainer* m_next; ///< next container
- unsigned m_max; ///< max number of edges in container
- unsigned m_used; ///< number of edges in container
- vf_Edge m_edge[1]; ///< array of contained edges
+ vf_Container container; ///< a container
+ vf_Edge m_edge[1]; ///< an array of edges
};
/**
- * Verifier control flow graph structure.
+ * An iterator over nodes.
*/
-class vf_Graph
+class vf_Iterator
{
-public:
- /**
- * Control flow graph constructor.
- * @param node - number of graph nodes
- * @param edge - number of graph edges
- * @param pool - external memory pool
- * @note Function allocates memory for graph structure, nodes and edges.
- */
- vf_Graph( unsigned node, unsigned edge, vf_VerifyPool_t *pool )
- : m_nodes(NULL), m_edges(NULL), m_pool(pool), m_enum(NULL),
- m_nodenum(0), m_edgenum(1), m_enummax(0), m_enumcount(0),
- m_free(false)
- {
- CreateNodes( node );
- CreateEdges( edge );
- return;
- } // vf_Graph
+ vf_ContainerHandle m_container; ///< a container
+ unsigned m_index; ///< an index in this container
/**
- * Control flow graph destructor.
- * @note Function release memory for graph structure, nodes and edges.
+ * Go to the next container.
*/
- ~vf_Graph()
+ void SkipContainer()
{
- if( m_free ) {
- vf_delete_pool( m_pool );
- }
- return;
- } // ~vf_Graph
+ m_container = m_container->m_next;
+ m_index = 0;
+ }
/**
- * Function create graph nodes.
- * @param count - number of graph nodes
- * @note Function allocates memory for graph nodes.
+ * Advances iterator to the next object.
*/
- void CreateNodes( unsigned count );
-
+ void Advance()
+ {
+ m_index++;
+ if (m_index < m_container->m_max) {
+ return;
+ }
+ SkipContainer();
+ }
+public:
/**
- * Gets a graph node.
- *
- * @param[in] node_num a node number, should be in range
- * @return a handle of the node
+ * Empty constructor.
*/
- vf_NodeHandle GetNode( unsigned node_num );
+ vf_Iterator ()
+ {
+ }
/**
- * Gets the first node.
- *
- * @return a handle of the node
+ * Creates an iterator for given containers.
+ * @param[in] container the first container
*/
- vf_NodeHandle GetFirstNode()
+ vf_Iterator (vf_ContainerHandle container)
{
- return GetNode( 0 );
- } // GetFirstNode
+ Reset(container);
+ }
/**
- * Creates a new node of a specific type.
- * Node array must have enough free space for a new element.
- *
- * @param[in] m_type node type
- * @param[in] stack a stack modifier (signed value)
- * @return a handle of the created node
+ * Resets an iterator for given containers.
+ * @param[in] container the first container
*/
- vf_NodeHandle NewNode( vf_NodeType_t m_type, int stack );
+ void Reset(vf_ContainerHandle container)
+ {
+ m_container = container;
+ m_index = 0;
+ }
/**
- * Creates a new node for a bytecode range.
- * Node array must have enough free space for a new element.
- *
- * @param[in] start an instruction start index
- * @param[in] end an instruction end index
- * @param[in] stack a stack modifier (signed value)
- * @return a handle of the created node
+ * Gets a current node.
*/
- vf_NodeHandle NewNode( unsigned start,
- unsigned end,
- int stack)
+ vf_NodeHandle GetNextNode()
{
- // get node
- vf_Node* node = (vf_Node*) NewNode( VF_TYPE_NODE_CODE_RANGE, stack );
- node->m_start = start;
- node->m_end = end;
+ vf_NodeHandle node =
+ ((vf_NodeContainer *) m_container)->m_node + m_index;
+ Advance();
return node;
- } // NewNode( start, end, len )
+ }
/**
- * Gets graph edge.
- * Parameter <i>edge_num</i> must be in range.
- *
- * @param[in] edge_num - edge number
- *
- * @return The pointer to edge structure.
+ * @return <code>true</code> if the iterator can be advanced further.
*/
- vf_EdgeHandle GetEdge( unsigned edge_num );
+ bool HasMoreElements() const
+ {
+ return m_container;
+ }
+}; // vf_Iterator
+
+/**
+ * Verifier control flow graph structure.
+ */
+class vf_Graph
+{
+ vf_NodeContainer *m_nodes; ///< array of nodes
+ vf_EdgeContainer *m_edges; ///< array of edges
+ vf_Pool *m_pool; ///< graph memory pool
+ vf_NodeHandle *m_enum; ///< graph node enumeration
+ unsigned m_nodenum; ///< number of nodes
+ unsigned m_edgenum; ///< number of edges
+ unsigned m_enumcount; ///< number of enumerated elements
+ vf_NodeHandle m_endnode; ///< control flow end
+ vf_ContextHandle m_ctx; ///< a verification context
+ vf_Iterator iterator; ///< an embedded graph iterator
+ bool m_free; ///< need to free pool
/**
- * Creates a new edge for graph nodes.
- *
- * @param start_node - start edge node
- * @param end_node - end edge node
- * @note Edge is set as out edge for start_node and as in edge for end_node.
+ * Prints a graph node in <code>stderr</code>.
+ * @param node a graph node
*/
- void NewEdge( unsigned start_node,
- unsigned end_node);
+ void DumpNode(vf_NodeHandle node);
/**
- * Gets the first code instruction of a node.
- * @param node_num the node number
- * @return a number of the first code instruction of graph node
- * @note Assertion is raised if <i>node_num</i> is not a
- * code range node.
+ * Prints graph node instructions in <code>stderr</code>.
+ * @param node_num a graph node
+ * @note Empty in release mode.
*/
- unsigned GetNodeFirstInstr( unsigned node_num )
- {
- vf_NodeHandle node = GetNode( node_num );
- assert( VF_TYPE_NODE_CODE_RANGE == node->m_type );
- return node->m_start;
- } // GetNodeFirstInstr
+ void DumpNodeInternal(vf_NodeHandle node);
+#ifdef _VF_DEBUG
/**
- * Gets the last code instruction of a node.
- * @param node_num the node number
- * @return a number of the last code instruction of graph node
- * @note Assertion is raised if <i>node_num</i> is not a
- * code range node.
+ * Prints subroutine information in <code>stderr</code>.
+ * @param sub a subroutine handle
*/
- unsigned GetNodeLastInstr( unsigned node_num )
- {
- vf_NodeHandle node = GetNode( node_num );
- assert( VF_TYPE_NODE_CODE_RANGE == node->m_type );
- return node->m_end;
- } // GetNodeLastInstr
+ void DumpSub(vf_SubHandle sub);
/**
- * Gets a bytecode length of a graph node instructions.
- * @param context a verifier context handle
- * @param node a node handle
- * @return a number of the last code instruction of graph node
- * @note Assertion is raised if <i>node_num</i> is not a
- * code range node.
+ * Checks if node maps are allocated.
+ * @param[in] vector to check
*/
- unsigned GetNodeBytecodeLen( vf_ContextHandle context,
- vf_NodeHandle node)
+ bool AreMapsAllocated(vf_MapVectorHandle vector) const
{
- assert( VF_TYPE_NODE_CODE_RANGE == node->m_type );
- unsigned char* code_end = (node->m_end + 1 == context->m_codeNum)
- ? method_get_bytecode( context->m_method )
- + method_get_code_length( context->m_method )
- : context->m_code[node->m_end + 1].m_addr;
-
- unsigned len = (unsigned)(code_end -
- context->m_code[node->m_start].m_addr);
- return len;
- } // GetNodeBytecodeLen
+ return (!m_ctx->m_maxlocal || vector->m_local)
+ && (!m_ctx->m_maxstack || vector->m_stack);
+ }
+#endif // _VF_DEBUG
/**
- * Gets a stack modifier of a graph node.
- * @param node_num a node number
- * @return a stack modifier of graph node
+ * Dumps a graph header in a file in a DOT format.
+ * @param graph_name a graph name
+ * @param fout a file stream
+ * @note Empty in release mode.
*/
- int GetNodeStackModifier( unsigned node_num )
- {
- return GetNode( node_num )->m_stack;
- } // GetNodeStackModifier
+ void DumpDotHeader(const char *graph_name, ofstream &fout);
/**
- * Sets graph node stack modifier.
- * @param node_num a graph node number
- * @param stack a stack modifier (signed value)
+ * Dumps a graph node in a file in DOT format.
+ * @param node a graph node
+ * @param fout a file stream
+ * @note Empty in release mode.
*/
- void SetNodeStackModifier( unsigned node_num, int stack )
- {
- vf_Node* node = (vf_Node*) GetNode( node_num );
- node->m_stack = stack;
- } // SetNodeStackModifier
+ void DumpDotNode(vf_NodeHandle node, ofstream &fout);
/**
- * Counts graph nodes.
- * @return a number of graph nodes
+ * Dumps graph node instructions in a file stream in DOT format.
+ * @param node a graph node
+ * @param next_node a separator between nodes in stream
+ * @param next_instr a separator between instructions in stream
+ * @param fout an output file stream
+ * @note Empty in release mode.
*/
- unsigned GetNodeCount()
- {
- return m_nodenum;
- } // GetNodeCount
+ void DumpDotNodeInternal(vf_NodeHandle node,
+ char *next_node, char *next_instr, ofstream &fout);
/**
- * Counts graph edges excluding
- * the reserved edge.
- * @return a number of graph edges
+ * Dumps graph end in file in DOT format.
+ * @param fout - output file stream
+ * @note Empty in release mode.
*/
- unsigned GetEdgeCount()
- {
- return m_edgenum - 1;
- } // GetEdgeCount
+ void DumpDotEnd(ofstream &fout);
+public:
/**
- * Marks a graph node with a given number.
- * @param node_num a graph node number
- * @param mark a mark
- */
- void SetNodeMark( unsigned node_num, int mark )
- {
- vf_Node* node = (vf_Node*) GetNode( node_num );
- node->m_mark = mark;
- } // SetNodeMark
+ * Constructs a control flow graph and allocates memory for
+ * graph structure, nodes and edges.
+ * @param nodenum a number of graph nodes
+ * @param edgenum a number of graph edges
+ * @param ctx a verification context
+ */
+ vf_Graph(unsigned nodenum, unsigned edgenum,
+ vf_ContextHandle ctx):m_nodes(NULL), m_edges(NULL),
+ m_pool(ctx->m_pool), m_enum(NULL), m_nodenum(0), m_edgenum(0),
+ m_enumcount(0), m_ctx(ctx), m_free(false)
+ {
+ CreateNodes(nodenum);
+ CreateEdges(edgenum);
+ } // vf_Graph
/**
- * Gets a graph node mark.
- * @param node_num a node number
- * @return a graph node mark
+ * Control flow graph destructor.
+ * @note Function release memory for graph structure, nodes and edges.
*/
- int GetNodeMark( unsigned node_num )
- {
- return GetNode( node_num )->m_mark;
- } // GetNodeMark
+ ~vf_Graph() {
+ if (m_free) {
+ vf_delete_pool(m_pool);
+ }
+ } // ~vf_Graph
/**
- * Checks if a node is marked.
- * @param node_num a graph node number
- * @return <code>true</code> if node is marked, <code>false</code> otherwise
+ * Allocates memory for graph nodes.
+ * @param count a number of nodes
*/
- bool IsNodeMarked( unsigned node_num )
+ void CreateNodes(unsigned count)
{
- return 0 != GetNode( node_num )->m_mark;
- } // IsNodeMarked
+ assert(count > 0);
+ vf_NodeContainer *nodes =
+ (vf_NodeContainer *) AllocMemory(sizeof(vf_NodeContainer)
+ + (count - 1) * sizeof(vf_Node));
+
+ nodes->container.m_max = count;
+ if (m_nodes == NULL) {
+ m_nodes = nodes;
+ } else {
+ vf_add_container(&m_nodes->container, &nodes->container);
+ }
+ }
/**
- * Function removes node mark.
+ * Allocates a container for graph edges.
+ * @param count a number of edges
*/
- void CleanNodesMark()
+ void CreateEdges(unsigned count)
{
- // clean node's mark
- assert( m_nodes );
- vf_NodeContainer* nodes = m_nodes;
- while( nodes != NULL ) {
- for( unsigned index = 0; index < nodes->m_used; index++ ) {
- nodes->m_node[index].m_mark = 0;
- }
- nodes = nodes->m_next;
+ assert(count > 0);
+ vf_EdgeContainer *edges =
+ (vf_EdgeContainer *) AllocMemory(sizeof(vf_EdgeContainer)
+ + (count - 1) * sizeof(vf_Edge));
+ edges->container.m_max = count;
+ if (m_edges == NULL) {
+ m_edges = edges;
+ } else {
+ vf_add_container(&m_edges->container, &edges->container);
}
- return;
- } // CleanNodesMark
+ }
/**
- * Sets local variable reference initialization flag for a anode.
- * @param node_num a graph node number
- * @param flag a node flag
+ * Gets a graph node.
+ * @param[in] node_num a node number, should be in range
+ * @return a handle of the node
*/
- void SetNodeInitFlag( unsigned node_num, bool flag )
+ vf_NodeHandle GetNode(unsigned node_num) const
{
- vf_Node* node = (vf_Node*) GetNode( node_num );
- node->m_initialized = flag;
- } // SetNodeInitFlag
+ // get node
+ assert(m_nodes);
+ assert(node_num < m_nodenum);
+
+ vf_NodeContainer *nodes =
+ (vf_NodeContainer *) vf_get_container(&m_nodes->container,
+ node_num);
+ return nodes->m_node + node_num;
+ } // GetNode
+
/**
- * Gets an initialization flag for local variable reference for a given node.
- * @param node_num a graph node number
- * @return <code>true</code> if the local variable reference has
- * to be initialized, <code>false</code> otherwise.
+ * Gets a graph node from a program counter.
+ *
+ * @param[in] pc a bytecode index at a node start
+ * @return a handle of a node
*/
- bool GetNodeInitFlag( unsigned node_num )
+ vf_NodeHandle GetNodeFromBytecodeIndex(unsigned pc) const
{
- return GetNode( node_num )->m_initialized;
- } // GetNodeInitFlag
+ vf_InstrHandle instr = m_ctx->m_bc[pc].m_instr;
+ assert(instr);
+ assert(m_ctx->m_bc[pc].m_instr->m_addr - m_ctx->m_bytes == pc);
+ vf_NodeHandle node = instr->m_node;
+ assert(GetNodeNum(node) > m_ctx->m_handlers);
+ return node;
+ }
/**
- * Function creates <i>IN</i> data flow vector of a node.
- * @param node_num a graph node number
- * @param example a handle of copied data flow vector
- * @param need_copy a copy flag
- * @note If copy flag <code>true</code>, incoming vector is copied to <i>IN</i>,
- * else if copy flag <code>false</code>, <i>IN</i> vector is created
- * with parameters of current vector.
+ * Gets the start node.
+ * @return the handle of the start node
*/
- void SetNodeInVector( unsigned node_num,
- vf_MapVectorHandle example,
- bool need_copy)
+ vf_NodeHandle GetStartNode()
{
- SetVector( GetNodeInVector( node_num ), example, need_copy );
- } // SetNodeInVector
+ return m_nodes->m_node;
+ } // GetStartNode
/**
- * Creates <i>OUT</i> data flow vector of a node.
- * @param node_num a graph node number
- * @param example a handle of copied data flow vector
- * @param need_copy a copy flag
- * @note If copy flag <code>true</code>, incoming vector is copied to <i>OUT</i>,
- * else if copy flag <code>false</code>, <i>OUT</i> vector is created
- * with parameters of current vector.
+ * Adds the end node.
+ * @return the handle of the end node
*/
- void SetNodeOutVector( unsigned node_num,
- vf_MapVectorHandle example,
- bool need_copy )
+ vf_NodeHandle AddEndNode()
{
- SetVector( GetNodeOutVector( node_num ), example, need_copy );
- } // SetNodeOutVector
+ m_endnode = NewNode(VF_NODE_END_ENTRY);
+ return m_endnode;
+ } // GetEndNode
/**
- * Gets <i>IN</i> data flow vector for the node.
- * @param node_num graph node number
- * @return a reference to <i>IN</i> data flow stack map vector
- * @note Assertion is raised if <i>node_num</i> is out of range.
- * @see vf_MapVector_t
+ * Gets the end node.
+ * @return the handle of the end node
*/
- vf_MapVectorHandle GetNodeInVector( unsigned node_num )
+ vf_NodeHandle GetEndNode()
{
- return &( GetNode( node_num )->m_inMapVector );
- } // GetNodeInVector
+ return m_endnode;
+ } // GetEndNode
/**
- * Gets <i>OUT</i> data flow vector for the node.
- * @param node_num graph node number
- * @return a reference to <i>OUT</i> data flow stack map vector
- * @see vf_MapVector_t
+ * Creates a new node of a specific type.
+ * A node array must have enough free space for a new element.
+ * @param[in] type node type
+ * @return a handle of the created node
*/
- vf_MapVectorHandle GetNodeOutVector( unsigned node_num )
+ vf_NodeHandle NewNode(vf_NodeType type)
{
- return &( GetNode( node_num )->m_outMapVector );
- } // GetNodeOutVector
+ // get node
+ assert(m_nodes);
+ unsigned count = m_nodenum;
+ vf_NodeContainer *nodes =
+ (vf_NodeContainer *) vf_get_container(&m_nodes->container, count);
+
+ // increment nodes count
+ m_nodenum++;
+ nodes->container.m_used++;
+ assert(nodes->container.m_used <= nodes->container.m_max);
+
+ // set node
+ vf_Node *node = nodes->m_node + count;
+ node->m_type = type;
+ return node;
+ } // NewNode
+
/**
- * Function creates graph edges.
- * @param number - number of edges
+ * Creates a new node for a bytecode range.
+ * A node array must have enough free space for a new element.
+ * @param[in] start the first instruction
+ * @param[in] end the last instruction
+ * @return a handle of the created node
*/
- void CreateEdges( unsigned number );
+ vf_NodeHandle NewNode(vf_InstrHandle start, vf_InstrHandle end)
+ {
+ // get node
+ vf_Node *node = (vf_Node *) NewNode(VF_NODE_CODE_RANGE);
+ node->m_start = start;
+ node->m_end = end;
+ return node;
+ } // NewNode(start, end)
/**
- * Function receives next <i>IN</i> edge of graph node.
- * @param edge_num - number of graph edge
- * @return Number of next <i>IN</i> edge of node.
- * @note Assertion is raised if <i>edge_num</i> is out of range.
+ * A quick interface for adding nodes to the container. Reserves a
+ * given number of nodes by increasing <code>m_used</code> count
+ * of the current container.
+ * A node array must have enough free space for a new element.
+ * @param[in] count a handle of an existing node
+ * @return a reference to the first reserved node
*/
- unsigned GetEdgeNextInEdge( unsigned edge_num )
+ vf_Node *AddNodes(unsigned count)
{
- return GetEdge( edge_num )->m_innext;
- } // GetEdgeNextInEdge
+ // get node
+ assert(m_nodes);
+
+ // find a container
+ unsigned c = m_nodenum;
+ vf_NodeContainer *nodes =
+ (vf_NodeContainer *) vf_get_container(&m_nodes->container, c);
+
+ // increment nodes count
+ m_nodenum += count;
+ nodes->container.m_used += count;
+ assert(nodes->container.m_used <= nodes->container.m_max);
+
+ // return a reference
+ return nodes->m_node + c;
+ } // AddNodes
/**
- * Function receives next <i>OUT</i> edge of graph node.
- * @param edge_num - number of graph edge
- * @return Number of next <i>OUT</i> edge of node.
- * @note Assertion is raised if <i>edge_num</i> is out of range.
+ * Creates a new edge between graph nodes.
+ *
+ * @param start_node an edge start
+ * @param end_node an edge end
+ * @return a handle of a created edge
*/
- unsigned GetEdgeNextOutEdge( unsigned edge_num )
+ vf_EdgeHandle NewEdge(vf_Node *start_node, vf_Node *end_node)
{
- return GetEdge( edge_num )->m_outnext;
- } // GetEdgeNextOutEdge
+ // get edge
+ assert(m_edges);
+
+ VF_TRACE("graph",
+ "Creating a new edge from " << GetNodeNum(start_node)
+ << " to " << GetNodeNum(end_node));
+ unsigned count = m_edgenum;
+ vf_EdgeContainer *edges =
+ (vf_EdgeContainer *) vf_get_container(&m_edges->container, count);
+
+ // get a new edge and edge's nodes
+ vf_Edge *edge = edges->m_edge + count;
+
+ // set a new edge
+ edge->m_start = start_node;
+ edge->m_end = end_node;
+ edge->m_outnext = start_node->m_outedge;
+ start_node->m_outedge = edge;
+ start_node->m_outnum++;
+ edge->m_innext = end_node->m_inedge;
+ end_node->m_inedge = edge;
+
+ // increment edge count
+ m_edgenum++;
+ edges->container.m_used++;
+ assert(edges->container.m_used <= edges->container.m_max);
+ return edge;
+ } // NewEdge
/**
- * Function receives start graph node of edge.
- * @param edge_num - number of graph edge
- * @return Number start graph node of edge.
- * @note Assertion is raised if <i>edge_num</i> is out of range.
+ * Resets an internal graph node iterator.
*/
- unsigned GetEdgeStartNode( unsigned edge_num )
+ void ResetNodeIterator()
{
- return GetEdge( edge_num )->m_start;
- } // GetEdgeStartNode
+ iterator.Reset(&m_nodes->container);
+ }
/**
- * Function receives end graph node of edge.
- * @param edge_num - number of graph edge
- * @return Number end graph node of edge.
- * @note Assertion is raised if <i>edge_num</i> is out of range.
+ * Gets a next node.
*/
- unsigned GetEdgeEndNode( unsigned edge_num )
+ vf_NodeHandle GetNextNode()
{
- return GetEdge( edge_num )->m_end;
- } // GetEdgeStartNode
+ return iterator.GetNextNode();
+ }
/**
- * Function receives number of <i>IN</i> edges of graph node.
- * @param node_num - number of graph node
- * @return Number of <i>IN</i> edges of graph node.
- * @note Assertion is raised if <i>node_num</i> is out of range.
+ * Checks if there are still elements to iterate.
*/
- unsigned GetNodeInEdgeNumber( unsigned node_num )
+ bool HasMoreElements() const
{
- return GetNode( node_num )->m_innum;
- } // GetNodeInEdgeNumber
+ return iterator.HasMoreElements();
+ }
/**
- * Function receives number of <i>OUT</i> edges of graph node.
- * @param node_num - number of graph node
- * @return Number of <i>OUT</i> edges of graph node.
- * @note Assertion is raised if <i>node_num</i> is out of range.
+ * Counts graph nodes.
+ * @return a number of graph nodes
*/
- unsigned GetNodeOutEdgeNumber( unsigned node_num )
+ unsigned GetNodeCount()
{
- return GetNode( node_num )->m_outnum;
- } // GetNodeOutEdgeNumber
+ return m_nodenum;
+ } // GetNodeCount
/**
- * Function receives first <i>IN</i> edge of graph node.
- * @param node_num - number of graph node
- * @return First <i>IN</i> edges of node.
- * @note Assertion is raised if <i>node_num</i> is out of range.
+ * Counts graph edges excluding
+ * the reserved edge.
+ * @return a number of graph edges
*/
- unsigned GetNodeFirstInEdge( unsigned node_num )
+ unsigned GetEdgeCount() const
{
- return GetNode( node_num )->m_inedge;
- } // GetNodeFirstInEdge
+ return m_edgenum;
+ } // GetEdgeCount
/**
- * Function receives first <i>OUT</i> edge of graph node.
- * @param node_num - number of graph node
- * @return First <i>OUT</i> edges of node.
- * @note Assertion is raised if <i>node_num</i> is out of range.
+ * Removes marks for all nodes.
*/
- unsigned GetNodeFirstOutEdge( unsigned node_num )
+ void CleanNodeMarks()
{
- return GetNode( node_num )->m_outedge;
- } // GetNodeFirstOutEdge
+ assert(m_nodes);
+ ResetNodeIterator();
+
+ // clean node marks
+ while (HasMoreElements()) {
+ ((vf_Node *) GetNextNode())->m_mark = 0;
+ }
+ } // CleanNodeMarks
/**
* Allocates memory from the graph memory pool.
@@ -554,205 +657,275 @@
* @return a pointer to allocated memory,
* or <code>NULL</code> if memory allocation failed.
*/
- void* AllocMemory( unsigned size ) {
- assert( size );
- return vf_alloc_pool_memory( m_pool, size );
- } // AllocMemory
+ void *AllocMemory(unsigned size)
+ {
+ assert(size);
+ return vf_palloc(m_pool, size);
+ } // AllocMemory
/**
- * Function cleans graph node enumeration, creates new graph
- * enumeration structure and sets first enumeration element.
- * @param node_num - first enumeration node
- * @note Assertion is raised if <i>node_num</i> is out of range.
+ * Allocates a graph node enumeration sequence and
+ * sets first enumeration element.
+ * @param node a first enumeration node
*/
- void SetStartCountNode( unsigned node_num );
+ void SetStartCountNode(vf_Node *node)
+ {
+ // check node number is in range
+ assert(m_nodes);
+ assert(node);
+
+ // allocate memory
+ m_enum = (vf_NodeHandle *) vf_palloc(m_pool, sizeof(vf_NodeHandle)
+ * m_nodenum);
+
+ // clean node enumeration
+ ResetNodeIterator();
+ while (HasMoreElements()) {
+ ((vf_Node *) GetNextNode())->m_nodecount = ALL_BITS_SET;
+ }
+
+ // set node enumeration number
+ node->m_nodecount = 0;
+
+ // set enumeration first element;
+ m_enum[0] = node;
+ m_enumcount = 1;
+ }
/**
- * Function receives number of enumerated nodes.
+ * Receives number of enumerated nodes.
* @return Function returns number of enumerated nodes.
*/
- unsigned GetEnumCount()
+ unsigned GetReachableNodeCount()
{
return m_enumcount;
- } // SetStartCountNode
+ } // SetStartCountNode
/**
- * Function sets next enumeration element in graph enumeration structure.
- * @param node_num - next enumeration node
- * @note Assertion is raised if <i>node_num</i> is out of range.
+ * Sets a next enumeration element in a graph enumeration
+ * and stores the index in the node.
+ * @param node a node handle
*/
- void SetNextCountNode( unsigned node_num )
+ void AddReachableNode(vf_Node *node)
{
// check enumeration count is in range
- assert( m_enumcount < m_nodenum );
+ assert(m_enumcount < m_nodenum);
// set enumeration element for node
- m_enum[m_enumcount] = node_num;
+ m_enum[m_enumcount] = node;
// set node enumeration number and increase number of enumerated nodes
- vf_Node* node = (vf_Node*) GetNode( node_num );
node->m_nodecount = m_enumcount++;
- return;
- } // SetNextCountNode
+ } // SetNextCountNode
/**
- * Function receives first enumerated graph node.
- * @return First enumerated graph node in graph enumeration structure.
+ * Suits for counting reachable nodes.
+ * @param node a node handle
*/
- unsigned GetStartCountNode()
+ void IncrementReachableCount()
{
- return m_enum[0];
- } // GetStartCountNode
-
+ m_enumcount++;
+ } // IncreaseReachableCount
+
/**
- * Function receives graph node relevant to enumeration element.
- * @param count - given enumeration element
- * @return Graph node relevant to enumeration element.
- * @note Assertion is raised if <i>count</i> is out of range.
+ * Gets a graph node by enumeration index.
+ * @param count given enumeration index
+ * @return a graph node handle
*/
- unsigned GetCountElementNode( unsigned count )
+ vf_NodeHandle GetReachableNode(unsigned count)
{
- // check element is in range.
- assert( count < m_nodenum );
return m_enum[count];
- } // GetCountElementNode
+ } // GetCountElementNode
/**
- * Function receives graph node enumeration count.
- * @param node_num - given node
- * @return Graph node enumeration count.
- * @note Assertion is raised if <i>node_num</i> is out of range.
+ * Copies a data flow vector from a given source.
+ * @param source a handle of a source vector
+ * @param dest a pointer to a vector to set
*/
- unsigned GetNodeCountElement( unsigned node_num )
+ void CopyVector(vf_MapVectorHandle source, vf_MapVector *dest)
{
- return GetNode( node_num )->m_nodecount;
- } // GetNodeCountElement
+ assert(AreMapsAllocated(source));
+ assert(AreMapsAllocated(dest));
- /**
- * Function prints graph structure in <code>stderr</code>.
- * @param context - current verifier context
- * @note Function is valid in debug mode.
- * @see vf_Context_t
- */
- void DumpGraph( vf_Context_t *context );
+ dest->m_number = source->m_number;
+ dest->m_depth = source->m_depth;
+
+ unsigned index;
+ for (index = 0; index < source->m_number; index++) {
+ dest->m_local[index] = source->m_local[index];
+ }
+ for (index = 0; index < source->m_depth; index++) {
+ dest->m_stack[index] = source->m_stack[index];
+ }
+ }
/**
- * Function dumps verifier graph in file in DOT format.
- * @param context - current verifier context
- * @note Function is valid in debug mode.
- * @note File name is created from class and method names with .dot extension.
- * @see vf_Context_t
+ * Copies a data flow vector from a given source,
+ * nullifies the rest of the destination.
+ * @param source a handle of a source vector
+ * @param dest a pointer to a vector to set
*/
- void DumpDotGraph( vf_Context_t *context );
+ void CopyFullVector(vf_MapVectorHandle source, vf_MapVector *dest)
+ {
+ assert(AreMapsAllocated(source));
+ assert(AreMapsAllocated(dest));
-private:
- vf_NodeContainer* m_nodes; ///< array of nodes
- vf_EdgeContainer* m_edges; ///< array of edges
- vf_VerifyPool_t *m_pool; ///< graph memory pool
- unsigned *m_enum; ///< graph node enumeration structure
- unsigned m_nodenum; ///< number of nodes
- unsigned m_edgenum; ///< number of edges
- unsigned m_enummax; ///< max number of enumerated elements
- unsigned m_enumcount; ///< number of enumerated elements
- bool m_free; ///< need to free pool
+ unsigned index;
+ vf_MapEntry zero = { 0 };
- /**
- * Creates a data flow vector from a given example.
- * @param vector_handle a vector to set
- * @param example a handle of an example vector
- * @param need_copy a copy flag
- * @note If copy flag <code>true</code>, incoming vector is copied to,
- * otherwise <i>IN</i> vector is created
- * with parameters of current vector.
- */
- void SetVector( vf_MapVectorHandle vector_handle,
- vf_MapVectorHandle example,
- bool need_copy);
+ dest->m_number = source->m_number;
+ dest->m_depth = source->m_depth;
+
+ // copy locals
+ for (index = 0; index < source->m_number; index++) {
+ dest->m_local[index] = source->m_local[index];
+ }
+ for (; index < m_ctx->m_maxlocal; index++) {
+ dest->m_local[index] = zero;
+ }
+ // copy stack
+ for (index = 0; index < source->m_depth; index++) {
+ dest->m_stack[index] = source->m_stack[index];
+ }
+ for (; index < m_ctx->m_maxstack; index++) {
+ dest->m_stack[index] = zero;
+ }
+ }
/**
- * Function prints graph node in <code>stderr</code>.
- * @param node_num - number of graph node
- * @param context - current verifier context
- * @note Function is valid in debug mode.
- * @note Assertion is raised if <i>node_num</i> is out of range.
- * @see vf_Context_t
+ * Allocates a vector with maximum storage capacity.
+ * @param[out] vector map to allocate
*/
- void DumpNode( unsigned node_num, vf_Context_t *context );
+ void AllocVector(vf_MapVector *vector)
+ {
+ // create and set local vector
+ if (m_ctx->m_maxlocal && !vector->m_local) {
+ vector->m_local =
+ (vf_MapEntry *) vf_palloc(m_pool,
+ m_ctx->m_maxlocal * sizeof(vf_MapEntry));
+ }
+ // create and set stack vector
+ if (m_ctx->m_maxstack && !vector->m_stack) {
+ vector->m_stack =
+ (vf_MapEntry *) vf_palloc(m_pool,
+ m_ctx->m_maxstack * sizeof(vf_MapEntry));
+ }
+ }
/**
- * Function prints graph node instruction in stream.
- * @param node_num - number of graph node
- * @param context - current verifier context
- * @note Function is valid in debug mode.
- * @note Assertion is raised if <i>node_num</i> is out of range.
- * @see vf_Context_t
+ * Prints a graph structure in <code>stderr</code>.
+ * @note Empty in release mode.
*/
- void DumpNodeInternal( unsigned node_num,
- vf_Context_t *context);
-
+ void DumpGraph();
/**
- * Function dumps graph header in file in DOT format.
- * @param graph_name - graph name
- * @param fout - file stream
- * @note Function is valid in debug mode.
- * @note Graph name is created from class and method names.
+ * Dumps a graph in a file in DOT format.
+ * @note Empty in release mode.
+ * @note File name is created from class and method names with .dot extension.
*/
- void DumpDotHeader( char *graph_name, ofstream &fout );
+ void DumpDotGraph();
+#if _VF_DEBUG
/**
- * Function dumps graph node in file in DOT format.
- * @param node_num - number of graph node
- * @param fout - file stream
- * @param context - current verifier context
- * @note Function is valid in debug mode.
- * @note Assertion is raised if <i>node_num</i> is out of range.
- * @see vf_Context_t
+ * Gets a graph node number for debugging purposes.
+ *
+ * @param[in] node a node handle
+ * @return a subsequent node number
*/
- void DumpDotNode( unsigned node_num, ofstream &fout, vf_Context_t *context );
+ unsigned GetNodeNum(vf_NodeHandle node) const
+ {
+ assert(node);
+ unsigned node_num = 0;
+ vf_NodeContainer *nodes = m_nodes;
+ while (nodes) {
+ unsigned index = node - nodes->m_node;
+ if (index < nodes->container.m_max) {
+ node_num += index;
+ assert(node_num < m_nodenum);
+ return node_num;
+ }
+ node_num += nodes->container.m_max;
+ nodes = (vf_NodeContainer *) nodes->container.m_next;
+ }
+ VF_DIE("vf_Graph::GetNodeNum: cannot find a node " << node);
+ return 0;
+ }
/**
- * Function dumps graph node instruction in file stream in DOT format.
- * @param node_num - number of graph node
- * @param next_node - separator between nodes in stream
- * @param next_instr - separator between instructions in stream
- * @param fout - output file stream
- * @param context - current verifier context
- * @note Function is valid in debug mode.
- * @note Assertion is raised if <i>node_num</i> is out of range.
- * @see vf_Context_t
+ * Checks amount of pre-allocated space for nodes in the graph.
*/
- void DumpDotNodeInternal( unsigned node_num,
- char *next_node,
- char *next_instr,
- ofstream &fout,
- vf_Context_t *context);
+ unsigned HasMoreNodeSpace() const
+ {
+ unsigned used = vf_used_space(&m_nodes->container);
+ assert(used == m_nodenum);
+ return vf_total_space(&m_nodes->container) - used;
+ } // HasMoreNodeSpace
/**
- * Function dumps graph end in file in DOT format.
- * @param fout - output file stream
- * @note Function is valid in debug mode.
+ * Checks amount of pre-allocated space for edges in the graph.
*/
- void DumpDotEnd( ofstream &fout );
+ unsigned HasMoreEdgeSpace() const
+ {
+ unsigned used = vf_used_space(&m_edges->container);
+ assert(used == m_edgenum);
+ return vf_total_space(&m_edges->container) - used;
+ } // HasMoreEdgeSpace
+
+#endif // _VF_DEBUG
-}; // vf_Graph
+}; // vf_Graph
/**
- * Checks if a code range node ends with a specific
- * instruction type.
- *
- * @param[in] context a verifier context
- * @param[in] node_index the node identifier
- *
- * @return a type of the last instruction of code range node
+ * Checks if a given edge is a subroutine call branch.
+ * @param[in] edge an edge handle
+ * @param[in] ctx a verification context
+ * @return <code>true</code> if this branch is a jsr call branch
*/
-static inline vf_CodeType
-vf_get_last_instruction_type( vf_ContextHandle context,
- unsigned node_index)
+static inline bool vf_is_jsr_branch(vf_EdgeHandle edge, vf_ContextHandle ctx)
{
- vf_NodeHandle node = context->m_graph->GetNode( node_index );
- assert( VF_TYPE_NODE_CODE_RANGE == node->m_type );
- return context->m_code[node->m_end].m_type;
+ vf_NodeHandle node = edge->m_start;
+ return (VF_NODE_CODE_RANGE == node->m_type)
+ && (VF_INSTR_JSR == node->m_end->m_type)
+ && (VF_NODE_CODE_RANGE == edge->m_end->m_type);
}
+
+/**
+ * Gets a subroutine number for a node. The function is slow and should be used for
+ * debugging purposes only.
+ * @param[in] sub a given subroutine handle
+ * @param[in] ctx a verification context
+ * @return a sequential subroutine number in a list
+ */
+unsigned vf_get_sub_num(vf_SubHandle sub, vf_ContextHandle ctx);
+
+/**
+ * Checks that a stack depth is the same as during last visit, calculates
+ * a stack modifier, counts a number of visited nodes, for each instruction checks
+ * that stack doesn't overflow.
+ * @param[in, out] node a pointer to a node structure, <code>m_mark</code> is
+ * modified during the call
+ * @param[in, out] depth starts as node depth before the first node instruction and ends
+ * as a node depth after the last node instruction
+ * @param[in] ctx a verifier context
+ * @return <code>VER_Continue</code> if this node wasn't visited before, and analysis of
+ * subsequent nodes is needed, <code>VER_OK</code> if the stack depth is consistent, an
+ * error code otherwise
+ */
+vf_Result vf_check_node_stack_depth(vf_Node *node, // a graph node
+ unsigned &depth, // stack depth
+ vf_Context *ctx); // verification context
+
+/**
+ * Creates and sets graph node OUT vector.
+ * @param[in] node a graph node handle
+ * @param[in, out] invector an IN vector, then OUT vector
+ * @param[in] ctx a verifier context
+ * @return <code>VER_OK</code> if OUT vector wasn't changed,
+ * <code>VER_Continue</code>
+ * if the vector was changed successfully, an error code otherwise
+ */
+vf_Result
+vf_set_node_out_vector(vf_NodeHandle node,
+ vf_MapVector *invector, vf_Context *ctx);
#endif // _VERIFIER_GRAPH_H_