harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From gshiman...@apache.org
Subject svn commit: r528575 [5/6] - in /harmony/enhanced/drlvm/trunk: src/test/regression/H3225/ vm/vmcore/include/ vm/vmcore/src/verifier/
Date Fri, 13 Apr 2007 18:26:28 GMT
Modified: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_real.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_real.h?view=diff&rev=528575&r1=528574&r2=528575
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_real.h (original)
+++ harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_real.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_REAL_H_
@@ -45,55 +45,97 @@
  */
 //===========================================================
 /**
- * Define debug mode for verifier.
+ * Defines a debug mode for verifier.
  */
 #ifdef NDEBUG
-#define _VERIFY_DEBUG 0
+#define _VF_DEBUG 0
 #else // NDEBUG
-#define _VERIFY_DEBUG 1
+#define _VF_DEBUG 1
 #endif // NDEBUG
 
 /**
- * Debugging and trace message defines.
- * @note Debug messages is available only in debug mode, 
- *       trace messages is available in any mode.
- * @note Verifier trace looks like: 'verifier' + component of verifier
- */
-#if _VERIFY_DEBUG
-#define VERIFY_DEBUG(info) ECHO("vf_debug: " << info)
-#else // _VERIFY_DEBUG
-#define VERIFY_DEBUG(info)
-#endif // _VERIFY_DEBUG
-#define VERIFY_TRACE(comp, mess) TRACE2("verifier." comp, mess)
-#define VERIFY_REPORT(context, error_message )      \
-    {                                               \
-        stringstream stream;                        \
-        stream << error_message;                    \
-        vf_set_error_message( stream, (context) );  \
-    }
-#define VERIFY_REPORT_CLASS(context, method, error_message )        \
-    VERIFY_REPORT(context,                                          \
-        "(class: " << class_get_name( (context)->m_class )          \
-        << ", method: " << method_get_name( method )                \
-        << method_get_descriptor( method )                          \
-        << ") " << error_message )
-#define VERIFY_REPORT_METHOD(context, error_message )               \
-    VERIFY_REPORT_CLASS(context, (context)->m_method, error_message )
+ * Both debug and trace channels are available only at debug mode.
+ * A debug channel is visible for a user while a trace channel should be
+ * enabled via <code>-Xtrace:verifier</code> command line option.
+ */
+#if _VF_DEBUG
+#define VF_DEBUG( info ) ECHO( "vf_debug: " << info )
+#define VF_DUMP( category, expr ) { \
+    static LogSite logSite = { UNKNOWN, NULL }; \
+    if( logSite.state && is_trace_enabled( "vfdump." category, &logSite ) ) { \
+        expr; \
+    } \
+}
+#define VF_STOP assert(0)
+#else
+#define VF_DEBUG(info)
+#define VF_DUMP(category, expr)
+#define VF_STOP DIE("Aborted at " __FILE__ "(" << __LINE__ << ")")
+#endif // _VF_DEBUG
+
+#define VF_TRACE(comp, message) TRACE2("verifier." comp, message)
+/**
+ * Verifer dump domains. They can be specified in a command line in
+ * a following form <code>-Xtrace:vfdump.&lt;domain&gt;</code>.
+ */
+/** Type constraints for a class. */
+#define DUMP_CONSTRAINT "constraint"
+/** An instruction array. */
+#define DUMP_INSTR "instr"
+/** A control flow graph. */
+#define DUMP_GRAPH "graph"
+/** A graph with cleaned dead nodes and inlined subroutines. */
+#define DUMP_MOD "mod_graph"
+/** A graph in a dot format. */
+#define DUMP_DOT "dot"
+/** A modified graph in a dot format. */
+#define DUMP_DOT_MOD "mod_dot"
+/** Node map vectors. */
+#define DUMP_NODE_MAP "map.node"
+/** Instruction map vectors. */
+#define DUMP_INSTR_MAP "map.instr"
+/** Merged map vectors. */
+#define DUMP_MERGE_MAP "map.merge"
+/** A path to subroutine <code>ret</code> instruction. */
+#define DUMP_NODESTACK "node.stack"
+
+
+/** Store a verification error in a verification context. */
+#define VF_SET_CTX( ctx, error_message ) \
+{ \
+    stringstream stream; \
+    stream << error_message; \
+    vf_set_error_message( stream, ( ctx ) ); \
+}
+
+/** Dump a current class and method. */
+#define VF_REPORT_CTX( ctx ) "(class: " << class_get_name( (ctx)->m_class ) \
+    << ", method: " << method_get_name( (ctx)->m_method ) \
+    << method_get_descriptor( (ctx)->m_method ) << ") "
+
+/** Report a verification error. */
+#define VF_REPORT( ctx, error_message ) \
+    VF_SET_CTX( ctx, VF_REPORT_CTX( ctx ) << error_message )
+
+/** Abort a verifier abnormally. */
+#define VF_DIE( error_message ) \
+    VF_DEBUG( "Verifer aborted: " << error_message ); \
+    VF_STOP;
 
 /**
  * Define source code line and source file name parameters and arguments.
  */
-#if _VERIFY_DEBUG
-#define VERIFY_SOURCE_PARAMS                UNREF int line_, UNREF const char *file_
-#define VERIFY_SOURCE_ARGS0                 __LINE__, __FILE__
-#define VERIFY_SOURCE_ARGS1                 line_, file_
-#define VERIFY_REPORT_SOURCE                file_ << "(" << line_ << "): "
-#else  // _VERIFY_DEBUG
-#define VERIFY_SOURCE_PARAMS                int
-#define VERIFY_SOURCE_ARGS0                 0
-#define VERIFY_SOURCE_ARGS1                 0
-#define VERIFY_REPORT_SOURCE                ""
-#endif // _VERIFY_DEBUG
+#if _VF_DEBUG
+#define VF_SOURCE_PARAMS                UNREF int line_, UNREF const char *file_
+#define VF_SOURCE_ARGS0                 __LINE__, __FILE__
+#define VF_SOURCE_ARGS1                 line_, file_
+#define VF_REPORT_SOURCE                file_ << "(" << line_ << "): "
+#else // _VF_DEBUG
+#define VF_SOURCE_PARAMS                int
+#define VF_SOURCE_ARGS0                 0
+#define VF_SOURCE_ARGS1                 0
+#define VF_REPORT_SOURCE                ""
+#endif // _VF_DEBUG
 
 //===========================================================
 // Verifier contant pool checks
@@ -103,64 +145,64 @@
  * Constant pool checks.
  */
 // for handler id = 0 is legal value
-#define CHECK_HANDLER_CONST_POOL_ID( id, len, context )                                 \
-    if( (id) >= (len) ) {                                                               \
-        VERIFY_REPORT_METHOD( context, "Illegal constant pool index in handler" );      \
-        return VER_ErrorHandler;                                                        \
+#define CHECK_HANDLER_CONST_POOL_ID( id, len, ctx ) \
+    if( (id) >= (len) ) { \
+        VF_REPORT( ctx, "Illegal constant pool index in handler" ); \
+        return VER_ErrorHandler; \
     }
 // for handler id = 0 is legal value
-#define CHECK_HANDLER_CONST_POOL_CLASS( context, id )                                   \
-    if( (id) && class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_Class ) {     \
-        VERIFY_REPORT_METHOD( context, "Illegal type in constant pool for handler, "    \
-            << id << ": CONSTANT_Class is expected" );                                  \
-        return VER_ErrorHandler;                                                        \
+#define CHECK_HANDLER_CONST_POOL_CLASS( ctx, id ) \
+    if( (id) && class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_Class ) { \
+        VF_REPORT( ctx, "Illegal type in constant pool for handler, " \
+            << id << ": CONSTANT_Class is expected" ); \
+        return VER_ErrorHandler; \
     }
-#define CHECK_CONST_POOL_ID( id, len, context )                                         \
-    if( !(id) || (id) >= (len) ) {                                                      \
-        VERIFY_REPORT_METHOD( context, "Illegal constant pool index" );                 \
-        return VER_ErrorConstantPool;                                                   \
+#define CHECK_CONST_POOL_ID( id, len, ctx ) \
+    if( !(id) || (id) >= (len) ) { \
+        VF_REPORT( ctx, "Illegal constant pool index" ); \
+        return VER_ErrorConstantPool; \
     }
-#define CHECK_CONST_POOL_CLASS( context, id )                                           \
-    if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_Class ) {             \
-        VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, "                \
-            << id << ": CONSTANT_Class is expected" );                                  \
-        return VER_ErrorConstantPool;                                                   \
+#define CHECK_CONST_POOL_CLASS( ctx, id ) \
+    if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_Class ) { \
+        VF_REPORT( ctx, "Illegal type in constant pool, " \
+            << id << ": CONSTANT_Class is expected" ); \
+        return VER_ErrorConstantPool; \
     }
-#define CHECK_CONST_POOL_METHOD( context, id )                                          \
-    if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_Methodref ) {         \
-        VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, "                \
-            << id << ": CONSTANT_Methodref is expected" );                              \
-        return VER_ErrorConstantPool;                                                   \
+#define CHECK_CONST_POOL_METHOD( ctx, id ) \
+    if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_Methodref ) { \
+        VF_REPORT( ctx, "Illegal type in constant pool, " \
+            << id << ": CONSTANT_Methodref is expected" ); \
+        return VER_ErrorConstantPool; \
     }
-#define CHECK_CONST_POOL_INTERFACE( context, id )                                           \
-    if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_InterfaceMethodref ) {    \
-        VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, "                    \
-            << id << ": CONSTANT_InterfaceMethodref is expected" );                         \
-        return VER_ErrorConstantPool;                                                       \
+#define CHECK_CONST_POOL_INTERFACE( ctx, id ) \
+    if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_InterfaceMethodref ) { \
+        VF_REPORT( ctx, "Illegal type in constant pool, " \
+            << id << ": CONSTANT_InterfaceMethodref is expected" ); \
+        return VER_ErrorConstantPool; \
     }
-#define CHECK_CONST_POOL_FIELD( context, id )                                           \
-    if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_Fieldref ) {          \
-        VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, "                \
-            << id << ": CONSTANT_Fieldref is expected" );                               \
-        return VER_ErrorConstantPool;                                                   \
+#define CHECK_CONST_POOL_FIELD( ctx, id ) \
+    if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_Fieldref ) { \
+        VF_REPORT( ctx, "Illegal type in constant pool, " \
+            << id << ": CONSTANT_Fieldref is expected" ); \
+        return VER_ErrorConstantPool; \
     }
-#define CHECK_CONST_POOL_TYPE( context, id )                                            \
-    if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_NameAndType ) {       \
-        VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, "                \
-            << id << ": CONSTANT_NameAndType is expected" );                            \
-        return VER_ErrorConstantPool;                                                   \
+#define CHECK_CONST_POOL_TYPE( ctx, id ) \
+    if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_NameAndType ) { \
+        VF_REPORT( ctx, "Illegal type in constant pool, " \
+            << id << ": CONSTANT_NameAndType is expected" ); \
+        return VER_ErrorConstantPool; \
     }
-#define CHECK_CONST_POOL_STRING( context, id )                                          \
-    if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_String ) {            \
-        VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, "                \
-            << id << ": CONSTANT_String is expected" );                                 \
-        return VER_ErrorConstantPool;                                                   \
+#define CHECK_CONST_POOL_STRING( ctx, id ) \
+    if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_String ) { \
+        VF_REPORT( ctx, "Illegal type in constant pool, " \
+            << id << ": CONSTANT_String is expected" ); \
+        return VER_ErrorConstantPool; \
     }
-#define CHECK_CONST_POOL_UTF8( context, id )                                            \
-    if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_Utf8) {               \
-        VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, "                \
-            << id << ": CONSTANT_Utf8 is expected" );                                   \
-        return VER_ErrorConstantPool;                                                   \
+#define CHECK_CONST_POOL_UTF8( ctx, id ) \
+    if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_Utf8) { \
+        VF_REPORT( ctx, "Illegal type in constant pool, " \
+            << id << ": CONSTANT_Utf8 is expected" ); \
+        return VER_ErrorConstantPool; \
     }
 
 //===========================================================
@@ -168,9 +210,15 @@
 //===========================================================
 
 /**
+ * Verifier error codes.
+ */
+typedef Verifier_Result vf_Result;
+
+/**
  * Constraint check types enum.
  */
-typedef enum {
+typedef enum
+{
     VF_CHECK_NONE = 0,
     VF_CHECK_PARAM,
     VF_CHECK_ASSIGN,
@@ -186,12 +234,13 @@
     VF_CHECK_INVOKESPECIAL,
     VF_CHECK_UNINITIALIZED_THIS,
     VF_CHECK_NUM
-} vf_CheckConstraint_t;
+} vf_CheckConstraint;
 
 /** 
  * Stack map entry types enum.
  */
-typedef enum {
+typedef enum
+{
     // original types
     SM_TOP = 0,
     SM_INT,
@@ -199,35 +248,35 @@
     SM_NULL,
     SM_REF,
     SM_UNINITIALIZED,
-    SM_UNINITIALIZED_THIS,
     SM_LONG_LO,
     SM_DOUBLE_LO,
     SM_LONG_HI,
     SM_DOUBLE_HI,
     SM_RETURN_ADDR,
     // additional types
+    SM_ANY,                     // matches any value
     SM_COPY_0,
     SM_COPY_1,
     SM_COPY_2,
     SM_COPY_3,
     SM_UP_ARRAY,
-    SM_RETURN,
-    SM_TERMINATE,
     SM_WORD,
     SM_WORD2_LO,
     SM_WORD2_HI,
     SM_NUMBER
-} vf_MapType_t;
+} vf_MapType;
 
 /**
  * Each instruction has a descriptive bitmap.
  */
-typedef enum {
-    VF_TYPE_INSTR_NONE        = 0,
-    VF_TYPE_INSTR_RETURN      = 1,
-    VF_TYPE_INSTR_THROW       = 2,
-    VF_TYPE_INSTR_SUBROUTINE  = 3
-} vf_CodeType;
+typedef enum
+{
+    VF_INSTR_NONE = 0,
+    VF_INSTR_RETURN = 1,
+    VF_INSTR_THROW = 2,
+    VF_INSTR_JSR = 3,
+    VF_INSTR_RET = 4
+} vf_InstrType;
 
 //===========================================================
 // Verifier predefined structures
@@ -235,37 +284,147 @@
 
 /**
  * @ingroup Handles
- * The handle of the verifier context.
+ * A handle of a verifier context.
+ */
+typedef const struct vf_Context *vf_ContextHandle;
+/**
+ * @ingroup Handles
+ * A handle of a subroutine information.
+ */
+typedef const struct vf_SubContext *vf_SubContextHandle;
+/**
+ * @ingroup Handles
+ * A graph handle.
+ */
+typedef const class vf_Graph *vf_GraphHandle;
+/**
+ * @ingroup Handles
+ * A handle of a graph node.
+ */
+typedef const struct vf_Node *vf_NodeHandle;
+/**
+ * @ingroup Handles
+ * A map vector handle.
+ */
+typedef const struct vf_MapVector *vf_MapVectorHandle;
+/**
+ * @ingroup Handles
+ * A handle of an instruction.
+ */
+typedef const struct vf_Instr *vf_InstrHandle;
+
+//===========================================================
+// Code instruction structures.
+//===========================================================
+
+/**
+ * Valid types structure.
+ */
+struct vf_ValidType
+{
+    unsigned number;            ///< number of types
+    const char *string[1];      ///< type array
+};
+
+/** 
+ * Stack map entry structure.
+ */
+struct vf_MapEntry
+{
+    vf_ValidType *m_vtype;      ///< valid type for reference
+    union
+    {
+        unsigned m_new;         ///< program count of opcode new for uninitialized
+        unsigned m_pc;          ///< program count of return address for subroutine
+    };
+    union
+    {
+        unsigned short m_local; ///< number of local variable
+        unsigned short m_index; ///< constant pool index for access check
+    };
+    unsigned short m_type:5;    ///< stack map type @see vf_MapType
+    unsigned short m_ctype:4;   ///< constraint type @see vf_CheckConstraint
+    unsigned short m_is_local:1;        ///< local variable modify flag
+    ///< true - modify local, false - modify stack
+};
+
+/**
+ * A bytecode instruction.
+ */
+struct vf_Instr
+{
+    unsigned char *m_addr;      ///< a start of a bytecode instruction
+    unsigned *m_off;            ///< an array of instruction branches
+    vf_MapEntry *m_invector;    ///< a stack map IN instruction vector
+    vf_MapEntry *m_outvector;   ///< a stack map OUT instruction vector
+    unsigned m_offcount;        ///< a number of instruction branches
+    union
+    {
+        vf_NodeHandle m_node;   ///< contains a node handle if the corresponding
+        ///< basic block starts at the instruction, <code>NULL</code> otherwise
+        bool m_is_bb_start;     ///< if this is a begin of a basic block
+    };
+    unsigned short m_minstack;  ///< a minimal stack for instruction
+    unsigned short m_inlen;     ///< an IN stack vector length
+    unsigned short m_outlen;    ///< an OUT stack vector length
+    short m_stack;              ///< a stack change
+    vf_InstrType m_type;        ///< an instruction type @see vf_InstrType
+};
+
+/**
+ * A byte of a bytecode.
+ */
+struct vf_BCode
+{
+    vf_InstrHandle m_instr;     ///< a pointer to vf_Context.m_instr
+    bool m_is_bb_start:1;       ///< <code>true</code> if the block starts here
+};
+
+/** 
+ * Constant pool parse structure.
  */
-typedef const struct vf_Context* vf_ContextHandle;
+union vf_Parse
+{
+    struct
+    {
+        vf_MapEntry *m_invector;        ///< method IN stack vector
+        vf_MapEntry *m_outvector;       ///< method OUT stack vector
+        const char *m_name;     ///< invoked method name
+        unsigned short m_inlen; ///< IN vector length
+        unsigned short m_outlen;        ///< OUT vector length
+    } method;
+    struct
+    {
+        vf_MapEntry *f_vector;  ///< field type map vector
+        unsigned short f_vlen;  ///< field type map vector len
+    } field;
+};
 
-/// Verifier context structure.
-typedef struct vf_Context vf_Context_t;
-/// Verifier structure for a byte of a bytecode.
-typedef struct vf_BCode vf_BCode_t;
-/// Verifier valid types structure.
-typedef struct vf_ValidType vf_ValidType_t;
-/// Verifier stack map entry structure.
-typedef struct vf_MapEntry vf_MapEntry_t;
-/// Verifier code instruction structure.
-typedef struct vf_Code vf_Code_t;
-/// Verifier constant pool parse structure.
-typedef union vf_Parse vf_Parse_t;
-/// Verifier graph structure declaration.
-class vf_Graph;
-/// Verifier type constraint structure.
-typedef struct vf_TypeConstraint vf_TypeConstraint_t;
-/// Verifier hash table structure.
-typedef struct vf_Hash vf_Hash_t;
-/// Verifier hash table entry structure.
-typedef struct vf_HashEntry vf_HashEntry_t;
-/// Verifier pool structure.
-typedef struct vf_VerifyPool vf_VerifyPool_t;
-/// Verifier pool internal structure.
-typedef struct vf_VerifyPoolInternal vf_VerifyPoolInternal_t;
-/// Verifier structure of class loader constraint data.
-typedef struct vf_ClassLoaderData vf_ClassLoaderData_t;
+//===========================================================
+// Pool structures.
+//===========================================================
+
+/**
+ * Internal structure of memory pool.
+ */
+struct vf_PoolInternal
+{
+    void *m_memory;             ///< pool entry memory
+    char *m_free;               ///< free space in pool entry
+    vf_PoolInternal *m_next;    ///< next pool entry
+    size_t m_freesize;          ///< size of free space in pool entry
+};
 
+/**
+ * Head structure of memory pool.
+ */
+struct vf_Pool
+{
+    vf_PoolInternal *m_pool;    ///< pool entry
+    size_t m_memory;            ///< allocated memory size
+    size_t m_used;              ///< used memory size
+    size_t m_maxuse;            ///< max used memory size
+};
 
 //===========================================================
 // Verifier memory management functions diclarations
@@ -274,219 +433,127 @@
 /**
  * Memory pool entry size.
  */
-#define VERIFY_POOL_ENTRY_SIZE  0x2000
+#define VF_POOL_ENTRY_SIZE  0x2000
 
 /**
  * Macros hide source line and source file name function arguments.
  */
-#define vf_error()                                                  \
-    vf_error_func(VERIFY_SOURCE_ARGS0)
-#define vf_calloc(number, size_element)                             \
-    vf_calloc_func((number), (size_element), VERIFY_SOURCE_ARGS0)
-#define vf_malloc(size)                                             \
-    vf_malloc_func((size), VERIFY_SOURCE_ARGS0)
-#define vf_free(pointer)                                            \
-    vf_free_func((pointer), VERIFY_SOURCE_ARGS0)
-#define vf_realloc(pointer, resize)                                 \
-    vf_realloc_func((pointer), (resize), VERIFY_SOURCE_ARGS0)
-#define vf_create_pool()                                            \
-    vf_create_pool_func(VERIFY_SOURCE_ARGS0)
-#define vf_alloc_pool_memory(pool, size)                            \
-    vf_alloc_pool_memory_func((pool), (size), VERIFY_SOURCE_ARGS0)
-#define vf_clean_pool_memory(pool)                                  \
-    vf_clean_pool_memory_func((pool), VERIFY_SOURCE_ARGS0)
-#define vf_delete_pool(pool)                                        \
-    vf_delete_pool_func((pool), VERIFY_SOURCE_ARGS0)
-
-/**
- * Function performs abend exit from VM.
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
- * @see VERIFY_SOURCE_PARAMS
- * @see vf_error
- */
-void
-vf_error_func( VERIFY_SOURCE_PARAMS );
+#define vf_calloc(number, size_element) \
+    vf_calloc_func((number), (size_element), VF_SOURCE_ARGS0)
+#define vf_malloc(size) \
+    vf_malloc_func((size), VF_SOURCE_ARGS0)
+#define vf_free(pointer) \
+    vf_free_func((pointer), VF_SOURCE_ARGS0)
+#define vf_realloc(pointer, resize) \
+    vf_realloc_func((pointer), (resize), VF_SOURCE_ARGS0)
+#define vf_create_pool() \
+    vf_create_pool_func(VF_SOURCE_ARGS0)
+#define vf_palloc(pool, size) \
+    vf_palloc_func((pool), (size), VF_SOURCE_ARGS0)
+#define vf_clean_pool(pool) \
+    vf_clean_pool_func((pool), VF_SOURCE_ARGS0)
+#define vf_delete_pool(pool) \
+    vf_delete_pool_func((pool), VF_SOURCE_ARGS0)
 
 /**
  * Function allocates an array in memory with elements initialized to zero. 
  * @param number        - number of elements
  * @param element_size  - size of element
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
  * @return Pointer to allocated memory block.
- * @see VERIFY_SOURCE_PARAMS
+ * @see VF_SOURCE_PARAMS
  * @see vf_calloc
  * @note Assertion is raised if <i>number</i> or <i>element_size</i>
  *       are equal to zero or if out of memory error is arisen.
  * @note Trace is available with argument <b>verifier:memory</b>.
  */
-void *
-vf_calloc_func( unsigned number, size_t element_size, VERIFY_SOURCE_PARAMS );
+void *vf_calloc_func( unsigned number, size_t element_size,
+                      VF_SOURCE_PARAMS );
 
 /**
  * Function allocates memory blocks.
  * @param size - size of memory block
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
  * @return Pointer to allocated memory block.
- * @see VERIFY_SOURCE_PARAMS
+ * @see VF_SOURCE_PARAMS
  * @see vf_malloc
  * @note Assertion is raised if <i>size</i> is equal to zero
  *       or if out of memory error is arisen.
  * @note Trace is available with argument <b>verifier:memory</b>.
  */
-void *
-vf_malloc_func( size_t size, VERIFY_SOURCE_PARAMS );
+void *vf_malloc_func( size_t size, VF_SOURCE_PARAMS );
 
 /**
  * Function releases allocated memory blocks.
  * @param pointer - pointer to allocated block
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
- * @see VERIFY_SOURCE_PARAMS
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @see VF_SOURCE_PARAMS
  * @see vf_free
  * @note Assertion is raised if <i>pointer</i> is equal to null.
  * @note Trace is available with argument <b>verifier:memory</b>.
  */
-void
-vf_free_func( void *pointer, VERIFY_SOURCE_PARAMS );
+void vf_free_func( void *pointer, VF_SOURCE_PARAMS );
 
 /**
  * Function reallocates memory blocks.
  * @param pointer   - pointer to allocated block
  * @param resize    - new size of memory block
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
  * @return Pointer to reallocated memory block.
- * @see VERIFY_SOURCE_PARAMS
+ * @see VF_SOURCE_PARAMS
  * @see vf_realloc
  * @note Assertion is raised if <i>resize</i> is equal to zero
  *       or if out of memory error is arisen.
  * @note If <i>pointer</i> is equal to null function works like vf_malloc_func.
  * @note Trace is available with argument <b>verifier:memory</b>.
  */
-void *
-vf_realloc_func( void *pointer, size_t resize, VERIFY_SOURCE_PARAMS );
+void *vf_realloc_func( void *pointer, size_t resize, VF_SOURCE_PARAMS );
 
 /**
  * Function creates memory pool structure.
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
  * @return Pointer to created memory pool.
- * @see VERIFY_SOURCE_PARAMS
+ * @see VF_SOURCE_PARAMS
  * @see vf_create_pool
- * @see vf_VerifyPool_t
+ * @see vf_Pool
  * @note Trace is available with argument <b>verifier:memory:pool</b>.
  */
-vf_VerifyPool_t *
-vf_create_pool_func( VERIFY_SOURCE_PARAMS );
+vf_Pool *vf_create_pool_func( VF_SOURCE_PARAMS );
 
 /**
  * Function allocates memory blocks in current pool.
  * @param pool - pointer to memory pool structure
  * @param size - memory block size
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
  * @return Pointer to allocated memory block.
- * @see VERIFY_SOURCE_PARAMS
- * @see vf_alloc_pool_memory
- * @see vf_VerifyPool_t
+ * @see VF_SOURCE_PARAMS
+ * @see vf_palloc
+ * @see vf_Pool
  * @note Trace is available with argument <b>verifier:memory:pool</b>.
  */
-void *
-vf_alloc_pool_memory_func( vf_VerifyPool_t *pool, size_t size, VERIFY_SOURCE_PARAMS );
+void *vf_palloc_func( vf_Pool *pool, size_t size, VF_SOURCE_PARAMS );
 
 /**
  * Function cleans given pool.
  * @param pool - memory pool structure
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
- * @see VERIFY_SOURCE_PARAMS
- * @see vf_clean_pool_memory
- * @see vf_VerifyPool_t
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @see VF_SOURCE_PARAMS
+ * @see vf_clean_pool
+ * @see vf_Pool
  * @note Trace is available with argument <b>verifier:memory:pool</b>.
  */
-void
-vf_clean_pool_memory_func( vf_VerifyPool_t *pool, VERIFY_SOURCE_PARAMS );
+void vf_clean_pool_func( vf_Pool *pool, VF_SOURCE_PARAMS );
 
 /**
  * Function releases memory from given pool.
  * @param pool - memory pool structure
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
- * @see VERIFY_SOURCE_PARAMS
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @see VF_SOURCE_PARAMS
  * @see vf_delete_pool
- * @see vf_VerifyPool_t
+ * @see vf_Pool
  * @note Trace is available with argument <b>verifier:memory:pool</b>.
  */
-void
-vf_delete_pool_func( vf_VerifyPool_t *pool, VERIFY_SOURCE_PARAMS );
-
-//===========================================================
-// Code instruction structures.
-//===========================================================
-
-/**
- * A byte of a bytecode.
- */
-struct vf_BCode {
-    unsigned m_instr;       ///< a number + 1 of code instruction at
-                            ///< vf_Context.m_code
-    unsigned m_mark : 1;    ///< control flow branch flag
-};
-
-/**
- * Valid types structure.
- */
-struct vf_ValidType {
-    unsigned number;          ///< number of types
-    const char *string[1];    ///< type array
-};
-
-/** 
- * Stack map entry structure.
- */
-struct vf_MapEntry {
-    vf_ValidType_t *m_vtype;        ///< valid type for reference
-    union {
-        unsigned m_new;             ///< program count of opcode new for uninitialized
-        unsigned m_pc;              ///< program count of return address for subroutine
-    };
-    union {
-        unsigned short m_local;     ///< number of local variable
-        unsigned short m_index;     ///< constant pool index for access check
-    };
-    unsigned short m_type : 5;      ///< stack map type @see vf_MapType_t
-    unsigned short m_ctype : 4;     ///< constraint type @see vf_CheckConstraint_t
-    unsigned short m_is_local : 1;  ///< local variable modify flag
-                                    ///< true - modify local, false - modify stack
-};
-
-/**
- * Complete struct of bytecode instructions.
- */
-struct vf_Code {
-    unsigned char *m_addr;          ///< address of bytecode instruction
-    unsigned *m_off;                ///< array of instruction branches
-    vf_MapEntry_t *m_invector;      ///< stack map IN instruction vector
-    vf_MapEntry_t *m_outvector;     ///< stack map OUT instruction vector
-    unsigned m_offcount;            ///< number of instruction branches
-    unsigned short m_minstack;      ///< minimal stack for instruction
-    unsigned short m_inlen;         ///< stack map IN instruction vector length
-    unsigned short m_outlen;        ///< stack map OUT instruction vector length
-    short m_stack;                  ///< stack change for instruction
-    vf_CodeType m_type;             ///< instruction flag @see vf_CodeType_t
-    bool m_basic_block_start : 1;   ///< begin of a basic block
-};
-
-/** 
- * Constant pool parse structure.
- */
-union vf_Parse {
-    struct {
-        vf_MapEntry_t *m_invector;   ///< method IN stack vector
-        vf_MapEntry_t *m_outvector;  ///< method OUT stack vector
-        const char *m_name;          ///< invoked method name
-        int m_inlen;                 ///< IN vector length
-        int m_outlen;                ///< OUT vector length
-    } method;
-    struct {
-        vf_MapEntry_t *f_vector;     ///< field type map vector
-        int f_vlen;                  ///< field type map vector len
-    } field;
-};
+void vf_delete_pool_func( vf_Pool *pool, VF_SOURCE_PARAMS );
 
 //===========================================================
 // Verifier hash table structures.
@@ -495,10 +562,11 @@
 /**
  * Structure of hash entry.
  */
-struct vf_HashEntry {
+struct vf_HashEntry
+{
     const char *key;            ///< hash entry key
     void *data;                 ///< pointer to hash entry data
-    vf_HashEntry_t *next;       ///< next hash entry
+    vf_HashEntry *next;         ///< next hash entry
 };
 
 /**
@@ -511,83 +579,83 @@
      * Hash table constructor.
      * @note Function allocates memory for hash pool and hash table.
      */
-    vf_Hash();
+    vf_Hash ();
 
     /**
      * Hash table constructor.
      * @param pool - external memory pool
      * @note Function allocates memory for hash pool and hash table.
      */
-    vf_Hash( vf_VerifyPool_t *pool);
+    vf_Hash ( vf_Pool *pool );
 
     /**
      * Hash table destructor.
      * @note Function release memory for hash pool and hash table.
      */
-    ~vf_Hash();
+           ~vf_Hash ();
 
     /**
      * Function looks up hash entry which is identical to given hash key.
      * @param key - given hash key
      * @return Hash entry which is identical to given hash key.
-     * @see vf_HashEntry_t
+     * @see vf_HashEntry
      */
-    vf_HashEntry_t * Lookup( const char *key );
+    vf_HashEntry *Lookup( const char *key );
 
     /**
      * Function looks up hash entry which is identical to given hash key.
      * @param key - given hash key
      * @param len - hash key length
      * @return Hash entry which is identical to given hash key.
-     * @see vf_HashEntry_t
+     * @see vf_HashEntry
      */
-    vf_HashEntry_t * Lookup( const char *key, unsigned len );
+    vf_HashEntry *Lookup( const char *key, size_t len );
 
     /**
      * Function creates hash entry which is identical to given hash key.
      * @param key - given hash key
      * @return Hash entry which are identical to given hash key.
-     * @see vf_HashEntry_t
+     * @see vf_HashEntry
      * @note Created hash key and hash entry is allocated into hash memory pool.
      */
-    vf_HashEntry_t * NewHashEntry( const char *key );
+    vf_HashEntry *NewHashEntry( const char *key );
 
     /**
      * Function creates hash entry which is identical to given hash key.
      * @param key - given hash key
      * @param len - hash key length
      * @return Hash entry which are identical to given hash key.
-     * @see vf_HashEntry_t
+     * @see vf_HashEntry
      * @note Created hash key and hash entry is allocated into hash memory pool.
      */
-    vf_HashEntry_t * NewHashEntry( const char *key, size_t len );
+    vf_HashEntry *NewHashEntry( const char *key, size_t len );
 
-private:
-    vf_VerifyPool_t *m_pool;    ///< hash memory pool
-    vf_HashEntry_t **m_hash;    ///< hash table
+  private:
+    vf_Pool *m_pool;            ///< hash memory pool
+    vf_HashEntry **m_hash;      ///< hash table
     const unsigned HASH_SIZE;   ///< hash table size
     bool m_free;                ///< need to free pool
 
     /**
-     * Function checks key identity.
+     * Checks key identity.
      * @param hash_entry - checked hash entry
      * @param key        - checked key
      * @return If keys are identical function returns <code>true</code>,
      *         else returns <code>false</code>.
-     * @see vf_HashEntry_t
+     * @see vf_HashEntry
      */
-    bool CheckKey( vf_HashEntry_t *hash_entry, const char *key );
+    bool CheckKey( vf_HashEntry *hash_entry, const char *key );
 
     /**
-     * Function checks key identity.
+     * Checks key identity.
      * @param hash_entry - checked hash entry
      * @param key        - checked key
      * @param len        - checked key length
      * @return If keys are identical function returns <code>true</code>,
      *         else returns <code>false</code>.
-     * @see vf_HashEntry_t
+     * @see vf_HashEntry
      */
-    bool CheckKey( vf_HashEntry_t *hash_entry, const char *key, size_t len );
+    bool CheckKey( vf_HashEntry *hash_entry, const char *key, size_t len );
 
     /**
      * Hash function.
@@ -603,22 +671,23 @@
      * @return Hash index relevant to key.
      */
     unsigned HashFunc( const char *key, size_t len );
-}; // struct vf_Hash
+};                              // struct vf_Hash
 
 //===========================================================
 // Verifier type constraint structures.
 //===========================================================
 
 /**
- * Verifier type constraint structure.
+ * A list of constraints.
  */
-struct vf_TypeConstraint {
-    const char *source;         ///< constraint source class name
-    const char *target;         ///< constraint target class name
-    method_handler method;      ///< constraint for method
-    vf_TypeConstraint_t *next;  ///< next constraint
-    unsigned short index;       ///< constant pool index
-    unsigned short check_type;  ///< constraint check type @see vf_CheckConstraint_t
+struct vf_TypeConstraint
+{
+    const char *m_source;       ///< constraint source class name
+    const char *m_target;       ///< constraint target class name
+    method_handler m_method;    ///< constraint for method
+    vf_TypeConstraint *m_next;  ///< next constraint
+    unsigned short m_index;     ///< constant pool index
+    unsigned short m_check_type;        ///< constraint check type @see vf_CheckConstraint
 };
 
 /**
@@ -644,20 +713,20 @@
      * @param type - given class name
      * @param len  - class name length
      * @return Created valid type structure.
-     * @see vf_ValidType_t
+     * @see vf_ValidType
      */
-    vf_ValidType_t * NewType( const char *type, size_t len );
+    vf_ValidType *NewType( const char *type, size_t len );
 
     /**
      * Function creates valid type which is identical to an element of a given array type.
      * @param array - array valid type
      * @return Created valid type of a given array element.
-     * @see vf_ValidType_t
+     * @see vf_ValidType
      */
-    vf_ValidType_t * NewArrayElemType( vf_ValidType_t *array );
+    vf_ValidType *NewArrayElemType( vf_ValidType *array );
 
     /**
-     * Function checks types and create constraints if it's necessarily.
+     * Checks types and create constraints if it's necessarily.
      * @param required      - required type
      * @param available     - available type
      * @param index         - constant pool index
@@ -665,13 +734,12 @@
      * @return If available type satisfy to required type
      *         function will return <code>false</code> (is it error?),
      *         else will return <code>true</code> (is it error?).
-     * @see vf_ValidType_t
-     * @see vf_CheckConstraint_t
+     * @see vf_ValidType
+     * @see vf_CheckConstraint
      */
-    bool CheckTypes( vf_ValidType_t *required,
-                     vf_ValidType_t *available,
-                     unsigned short index,
-                     vf_CheckConstraint_t check_type);
+    bool CheckTypes( vf_ValidType *required,
+                     vf_ValidType *available,
+                     unsigned short index, vf_CheckConstraint check_type );
 
     /**
      * Function merges two valid types.
@@ -679,12 +747,12 @@
      * @param second - second merged type
      * @return Function returns created valid type corresponding with merge result.
      * @return Function returns <code>NULL</code> if vector wasn't merged.
-     * @see vf_ValidType_t
+     * @see vf_ValidType
      */
-    vf_ValidType_t * MergeTypes( vf_ValidType_t *first, vf_ValidType_t *second );
+    vf_ValidType *MergeTypes( vf_ValidType *first, vf_ValidType *second );
 
     /**
-     * Function dumps constraint collection in stream.
+     * Dumps constraint collection in stream.
      * @param out - pointer to output stream
      * @note If <i>out</i> is equal to null, output stream is <i>cerr</i>.
      */
@@ -693,44 +761,44 @@
     /**
      * Function returns the methods constraints array.
      * @return Array of the methods constraints.
-     * @see vf_TypeConstraint_t
+     * @see vf_TypeConstraint
      */
-    vf_TypeConstraint_t * GetClassConstraint();
+    vf_TypeConstraint *GetClassConstraint();
 
     /**
-     * Function sets current context method.
+     * Sets current context method.
      * @param method - current context method
      */
     void SetMethod( method_handler method );
 
     /**
-     * Function sets restriction from target class to source class.
+     * Sets restriction from target class to source class.
      * @param target        - target class name
      * @param source        - source class name
      * @param index         - constant pool index
      * @param check_type    - constraint check type
-     * @see vf_CheckConstraint_t
+     * @see vf_CheckConstraint
      */
     void SetRestriction( const char *target,
-                         const char *source, 
+                         const char *source,
                          unsigned short index,
-                         vf_CheckConstraint_t check_type );
+                         vf_CheckConstraint check_type );
 
-private:
-    vf_VerifyPool_t *m_pool;                ///< collection memory pool
-    vf_Hash_t *m_Hash;                      ///< hash table
-    method_handler m_method;                ///< current context method
-    vf_TypeConstraint_t *m_restriction;     ///< array of the class constraints
-}; // vf_TypePool
+  private:
+    vf_Pool *m_pool;            ///< collection memory pool
+    vf_Hash *m_Hash;            ///< hash table
+    method_handler m_method;    ///< current context method
+    vf_TypeConstraint *m_restriction;   ///< array of the class constraints
+};                              // vf_TypePool
 
 //===========================================================
 // Verifier type constraint structures.
 //===========================================================
 
-void vf_clean_pool_memory_func( vf_VerifyPool_t *pool, VERIFY_SOURCE_PARAMS );
+void vf_clean_pool_func( vf_Pool *pool, VF_SOURCE_PARAMS );
 
 /**
- * Structure of verifier context
+ * Verification context.
  */
 struct vf_Context
 {
@@ -738,116 +806,126 @@
     /**
      * Verifier context constructor
      */
-    vf_Context() : m_class(NULL), m_type(NULL), m_error(NULL),
-        m_method(NULL), m_graph(NULL), m_pool(NULL), m_code(NULL), 
-        m_codeNum(0), m_nodeNum(0), m_edgeNum(0)
+    vf_Context ():m_class( NULL ), m_type( NULL ), m_error( NULL ),
+        m_method( NULL ), m_graph( NULL ), m_pool( NULL ), m_instr( NULL ),
+        m_last_instr( NULL ), m_retnum( 0 ), m_verify_all( false )
     {
-        vf_ContextDump zero1 = {0};
-        vf_ContextVType zero2 = {0};
-
-        m_dump = zero1;
+        vf_ContextVType zero2 = { 0 };
         m_vtype = zero2;
     }
 
+    void SetMethod( method_handler method )
+    {
+        m_method = method;
+
+        // get method parameters
+        m_len = method_get_code_length( method );
+        m_bytes = method_get_bytecode( method );
+        m_handlers = method_get_exc_handler_number( method );
+
+        // get method limitations
+        m_maxlocal = method_get_max_local( method );
+        m_maxstack = method_get_max_stack( method );
+
+        // cache in the context if the method is a constructor
+        m_is_constructor =
+            memcmp( method_get_name( method ), "<init>", 7 ) == 0;
+    }
+
     /**
      * Verifier context destructor
      */
-    ~vf_Context() {}
+    ~vf_Context ()
+    {
+        if( m_pool ) {
+            vf_delete_pool( m_pool );
+        }
+        if( m_type ) {
+            delete m_type;
+        }
+    }
 
     /**
-     * Function clears context.
+     * Clears context.
      */
     void ClearContext()
     {
         m_method = NULL;
         m_is_constructor = false;
         m_graph = NULL;
-        m_code = NULL;
-        m_bc   = NULL;
-        m_codeNum = 0;
-        m_nodeNum = 0;
-        m_edgeNum = 0;
-        vf_clean_pool_memory( m_pool );
-    } // vf_ClearContext
+        m_instr = NULL;
+        m_bc = NULL;
+        m_last_instr = NULL;
+        m_retnum = 0;
+        vf_clean_pool( m_pool );
+    }                           // vf_ClearContext
 
 public:
-    vf_TypePool *m_type;                ///< context type constraint collection
-    char *m_error;                      ///< context error message
-    vf_Graph *m_graph;                  ///< context control flow graph
-    vf_VerifyPool_t *m_pool;            ///< context memory pool
-    vf_Code_t *m_code;                  ///< context code instruction of method
-    vf_BCode_t* m_bc;                   ///< bytecode to code mapping
-    class_handler m_class;              ///< context class
-    method_handler m_method;            ///< context method
-    unsigned m_codeNum;                 ///< code instruction number
-    unsigned m_nodeNum;                 ///< graph node number
-    unsigned m_edgeNum;                 ///< graph edge number
-    bool m_is_constructor;              ///< <code>true</code> if the
-                                        ///< method is a constructor
-
-    /**
-     * Structure contains useful valid types
-     */
-    struct vf_ContextVType {
-        vf_ValidType_t *m_class;        ///< context a given class valid type
-        vf_ValidType_t *m_throwable;    ///< context java/lang/Throwable valid type
-        vf_ValidType_t *m_object;       ///< context java/lang/Object valid type
-        vf_ValidType_t *m_array;        ///< context [Ljava/lang/Object; valid type
-        vf_ValidType_t *m_clone;        ///< context java/lang/Cloneable valid type
-        vf_ValidType_t *m_serialize;    ///< context java/io/Serializable valid type
-    } m_vtype;
+    vf_TypePool *m_type;        ///< context type constraint collection
+    char *m_error;              ///< context error message
+    vf_Graph *m_graph;          ///< control flow graph
+    vf_Pool *m_pool;            ///< memory pool
+    vf_InstrHandle m_instr;     ///< method instructions
+    vf_InstrHandle m_last_instr;        ///< the pointer follows
+    ///< the last instruction at <code>m_instr</code>
+    vf_BCode *m_bc;             ///< bytecode to instruction mapping
+    unsigned m_retnum;          ///< a number of <code>ret</code>s
+
+    /**
+     * Cached method info.
+     */
+    class_handler m_class;      ///< a context class
+    method_handler m_method;    ///< a context method
+    unsigned m_len;             ///< bytecode length
+    unsigned char *m_bytes;     ///< bytecode location
+    unsigned short m_handlers;  ///< a number of exception handlers
+    unsigned short m_maxstack;  ///< max stack length
+    unsigned short m_maxlocal;  ///< max local number
+    bool m_is_constructor;      ///< <code>true</code> if the
+    ///< method is a constructor
+
+    vf_SubContext *m_sub_ctx;   ///< aggregate subroutine info
+    vf_MapVector *m_map;        ///< a stack map for control flow analysis,
+    ///< vectors themselves are allocated from the graph pool
+    vf_MapEntry *m_method_invector;     ///< method parameters
+    unsigned short m_method_inlen;      ///< a length of <code>m_method_invector</code>
+    vf_MapEntry *m_method_outvector;    ///< method return value
+    unsigned short m_method_outlen;     ///< a length of <code>m_method_outvector</code>
+
+    vf_MapEntry *m_buf;         ///< used to store intermediate stack states
+    ///< during data flow analysis
+
+    bool m_verify_all;          ///< if <code>true</code> need to verify more checks
 
     /**
-     * Structure contains debug dump flags
+     * Contains useful valid types.
      */
-    struct vf_ContextDump {
-        unsigned m_verify : 1;          ///< verify all flag
-        unsigned m_with_subroutine : 1; ///< verified method has subroutine
-        unsigned m_constraint : 1;      ///< dump type constraints for class
-        unsigned m_code : 1;            ///< print code array in stream
-        unsigned m_graph : 1;           ///< print original control flow graph
-        unsigned m_mod_graph : 1;       ///< print modified control flow graph
-        unsigned m_dot_graph : 1;       ///< dump original control flow graph in file in DOT format
-        unsigned m_dot_mod_graph : 1;   ///< dump modified control flow graph in file in DOT format
-        unsigned m_node_vector : 1;     ///< print data flow node vectors
-        unsigned m_code_vector : 1;     ///< print data flow node code instruction vectors
-        unsigned m_merge_vector : 1;    ///< print result of merge data flow vectors
-    } m_dump;
+    struct vf_ContextVType
+    {
+        vf_ValidType *m_class;  ///< a given class
+        vf_ValidType *m_throwable;      ///< java/lang/Throwable
+        vf_ValidType *m_object; ///< java/lang/Object
+        vf_ValidType *m_array;  ///< [Ljava/lang/Object;
+        vf_ValidType *m_clone;  ///< java/lang/Cloneable
+        vf_ValidType *m_serialize;      ///< java/io/Serializable
+    } m_vtype;
 
-}; // struct vf_Context
+};                              // struct vf_Context
 
 //===========================================================
 // Other structures.
 //===========================================================
 
 /**
- * Head structure of memory pool.
- */
-struct vf_VerifyPool {
-    vf_VerifyPoolInternal_t *m_pool;    ///< pool entry
-    size_t m_memory;                    ///< allocated memory size
-    size_t m_used;                      ///< used memory size
-    size_t m_maxuse;                    ///< max used memory size
-};
-
-/**
- * Internal structure of memory pool.
- */
-struct vf_VerifyPoolInternal {
-    void *m_memory;                     ///< pool entry memory
-    char *m_free;                       ///< free space in pool entry
-    vf_VerifyPoolInternal_t *m_next;    ///< next pool entry
-    size_t m_freesize;                  ///< size of free space in pool entry
-};
-
-/**
  * Structure of class loader constraint data.
  */
-struct vf_ClassLoaderData {
-    vf_VerifyPool_t *pool;  ///< constraint memory pool
-    vf_Hash_t *string;      ///< string pool hash table
+struct vf_ClassLoaderData
+{
+    vf_Pool *pool;              ///< constraint memory pool
+    vf_Hash *string;            ///< string pool hash table
 };
 
+
 //===========================================================
 // Verifier debug data
 //===========================================================
@@ -855,9 +933,9 @@
 /**
  * Array of opcode names. Available in debug mode.
  */
-#if _VERIFY_DEBUG
+#if _VF_DEBUG
 extern const char *vf_opcode_names[];
-#endif // _VERIFY_DEBUG
+#endif // _VF_DEBUG
 
 //===========================================================
 // Verifier functions.
@@ -865,13 +943,12 @@
 
 /**
  * Function creates bytecode control flow graph.
- * @param context - verifier context
+ * @param ctx - verifier context
  * @return Result of graph creation.
- * @see vf_Context_t
- * @see Verifier_Result
+ * @see vf_Context
+ * @see vf_Result
  */
-Verifier_Result
-vf_create_graph( vf_Context_t *context );
+vf_Result vf_create_graph( vf_Context *ctx );
 
 /**
  * Checks control flow and data flow of graph.
@@ -880,55 +957,50 @@
  *
  * @return a result of graph checks
  */
-Verifier_Result
-vf_check_graph( vf_Context_t *context );
+vf_Result vf_check_graph( vf_Context *ctx );
 
 /**
- * Function provides data flow checks of verifier graph structure.
- * @param context - verifier context
+ * Provides data flow checks of verifier graph structure.
+ * @param ctx - verifier context
  * @return Check result.
- * @see vf_Context_t
- * @see Verifier_Result
+ * @see vf_Context
+ * @see vf_Result
  */
-Verifier_Result
-vf_check_graph_data_flow( vf_Context_t *context );
+vf_Result vf_check_graph_data_flow( vf_Context *ctx );
 
 /**
- * Function parses method, class or field descriptors.
- * @param descr  - descriptor of method, class or field
- * @param inlen  - returned number of <i>IN</i> descriptor parameters 
- * @param outlen - returned number of <i>OUT</i> descriptor parameters (for method)
- * @note Assertion is raised if <i>descr</i> or <i>inlen</i> are equal to null.
+ * Parses method, class or field descriptors.
+ * @param descr  descriptor of method, class or field
+ * @param inlen  returned number of <i>IN</i> descriptor parameters 
+ * @param outlen returned number of <i>OUT</i> descriptor parameters (for method)
+ * @note Assertion is raised if <i>descr</i> or <i>inlen</i> are equal to <code>NULL</code>.
  * @note Parameter <i>outlen</i> may be equal to null (for class or field descriptor).
  */
-void
-vf_parse_description( const char *descr, int *inlen, int *outlen);
+void vf_parse_description( const char *descr, unsigned short *inlen,
+                           unsigned short *outlen );
 
 /**
- * Function parses descriptor and sets input and output data flow vectors.
- * @param descr     - descriptor of method, class or field
- * @param inlen     - number of entries for <i>IN</i> data flow vector
- * @param add       - additional number of entries to <i>IN</i> data flow vector
- * @param outlen    - number of entries for <i>OUT</i> data flow vector (for method)
- * @param invector  - pointer to <i>IN</i> data flow vector
- * @param outvector - pointer to <i>OUT</i> data flow vector
- * @param context   - verifier context
+ * Parses a descriptor and sets input and output data flow vectors.
+ * @param descr     a descriptor of method, class or field
+ * @param inlen     a number of entries for <i>IN</i> data flow vector
+ * @param add       an additional number of entries to <i>IN</i> data flow vector
+ * @param outlen    a number of entries for <i>OUT</i> data flow vector (for method)
+ * @param invector  a pointer to <i>IN</i> data flow vector
+ * @param outvector a pointer to <i>OUT</i> data flow vector
+ * @param ctx   a verifier context
  * @note Assertion is raised if <i>descr</i> is equal to null.
  * @note Parameter <i>invector</i> may be equal to null 
  *       if sum of parameters <i>inlen + add</i> is equal to zero.
  * @note Parameter <i>outvector</i> may be equal to null 
  *       if parameter <i>outlen</i> is equal to zero.
- * @see vf_MapEntry_t
- * @see vf_Context_t
  */
 void
 vf_set_description_vector( const char *descr,
-                           int inlen,
-                           int add,
-                           int outlen,
-                           vf_MapEntry_t **invector,
-                           vf_MapEntry_t **outvector,
-                           vf_Context_t *context);
+                           unsigned short inlen,
+                           unsigned short add,
+                           unsigned short outlen,
+                           vf_MapEntry **invector,
+                           vf_MapEntry **outvector, vf_ContextHandle ctx );
 
 /**
  * Gets a class name from a constant pool.
@@ -938,51 +1010,46 @@
  *
  * @return a pointer to UTF8 constant pool entry
  */
-static inline const char*
-vf_get_cp_class_name( class_handler klass,
-                      unsigned short index )
+static inline const char *
+vf_get_cp_class_name( class_handler klass, unsigned short index )
 {
     unsigned short class_name_index =
-        class_get_cp_class_name_index(klass, index);
-    const char* name = class_get_cp_utf8_bytes(klass, class_name_index);
+        class_get_cp_class_name_index( klass, index );
+    const char *name = class_get_cp_utf8_bytes( klass, class_name_index );
     return name;
-} // vf_get_cp_class_name
+}                               // vf_get_cp_class_name
 
 /**
- * Function creates valid type by given class name.
- * @param class_name - class name
- * @param context    - verifier context
- * @return Valid type structure corresponding to given class name.
- * @see vf_ValidType_t
- * @see vf_Context_t
+ * Creates a valid type from a given class name.
+ * @param class_name a class name
+ * @param ctx    a verifier context
+ * @return a valid type structure corresponding to the given class name
  */
-vf_ValidType_t *
-vf_create_class_valid_type( const char *class_name, vf_Context_t *context );
+vf_ValidType *vf_create_class_valid_type( const char *class_name,
+                                          vf_ContextHandle ctx );
 
 /**
- * Function provides constraint checks for current class.
- * @param context - verifier context
+ * Provides constraint checks for current class.
+ * @param ctx - verifier context
  * @return Check result.
  * @note Provides only checks with loaded classes.
  * @note All unchecked constraints are saved to class loader verify data.
- * @see vf_Context_t
- * @see Verifier_Result
+ * @see vf_Context
+ * @see vf_Result
  */
-Verifier_Result
-vf_check_class_constraints( vf_Context_t *context );
+vf_Result vf_check_class_constraints( vf_Context *ctx );
 
 /**
  * Function compares two valid types.
  * @param type1 - first checked type
  * @param type2 - second checked type
  * @return If types are equal returns <code>true</code>, else returns <code>false</code>.
- * @see vf_ValidType_t
+ * @see vf_ValidType
  */
-bool
-vf_is_types_equal( vf_ValidType_t *type1, vf_ValidType_t *type2 );
+bool vf_is_types_equal( vf_ValidType *type1, vf_ValidType *type2 );
 
 /**
- * Function checks access to protected field/method.
+ * Checks access to protected field/method.
  * If function cannot check constraint because of any class isn't loaded,
  * function return unloaded error to store restriction to the class
  * for future constraint check.
@@ -990,45 +1057,42 @@
  * @param instance_name - name of instance class
  * @param index         - constant pool index
  * @param check_type    - access check type
- * @param ctex          - verifier context
+ * @param ctx          - verifier context
  * @return Check result.
  * @note Provides only checks with loaded classes.
- * @see vf_CheckConstraint_t
- * @see vf_Context_t
- * @see Verifier_Result
- */
-Verifier_Result
-vf_check_access_constraint( const char *super_name,             // name of super class
-                            const char *instance_name,          // name of instance class
-                            unsigned short index,               // constant pool index
-                            vf_CheckConstraint_t check_type,    // access check type
-                            vf_Context_t *ctex);                // verifier context
+ * @see vf_CheckConstraint
+ * @see vf_Context
+ * @see vf_Result
+ */
+vf_Result vf_check_access_constraint( const char *super_name,   // name of super class
+                                      const char *instance_name,        // name of instance class
+                                      unsigned short index,     // constant pool index
+                                      vf_CheckConstraint check_type,    // access check type
+                                      vf_Context *ctx );        // verification context
 
 /**
- * Sets error message of verifier.
+ * Sets error message of a verifier.
  *
  * @param[in] stream stringstream object with a message
- * @param[in] ctex   a verifier context
+ * @param[in] ctx   a verifier context
  */
 static inline void
-vf_set_error_message( stringstream &stream,
-                      vf_Context_t *ctex)
+vf_set_error_message( stringstream & stream, vf_Context *ctx )
 {
-    if( ctex->m_error ) {
+    if( ctx->m_error ) {
         // free old message
-        vf_free( ctex->m_error );
+        vf_free( ctx->m_error );
     }
     // create message
     size_t len = stream.str().length();
     if( len ) {
-        ctex->m_error = (char*)vf_malloc( len + 1 );
-        memcpy( ctex->m_error, stream.str().c_str(), len );
-        ctex->m_error[len] = '\0';
+        ctx->m_error = (char*)vf_malloc( len + 1 );
+        memcpy( ctx->m_error, stream.str().c_str(), len );
+        ctx->m_error[len] = '\0';
     } else {
-        ctex->m_error = NULL;
+        ctx->m_error = NULL;
     }
-    return;
-} // vf_set_error_message
+}                               // vf_set_error_message
 
 /**
  * Checks a version of a class file.
@@ -1038,26 +1102,26 @@
  * @return <code>true</code> if a class version is less than 1.4
  */
 static inline bool
-vf_is_class_version_14( vf_Context_t *context )
+vf_is_class_version_14( vf_ContextHandle ctx )
 {
-    return (class_get_version(context->m_class) < 49) ? true : false;
-} // vf_is_class_version_14
+    return ( class_get_version( ctx->m_class ) < 49 ) ? true : false;
+}                               // vf_is_class_version_14
 
 /**
  * Returns branch target for a given branch number.
  *
- * @param[in] code        a reference to instruction
+ * @param[in] instr        a reference to instruction
  * @param[in] branch_num  a branch number
  *
  * @return an absolute bytecode position to which the executuion
  * branches
  */
 static inline int
-vf_get_code_branch( vf_Code_t* code, unsigned branch_num )
+vf_get_instr_branch( vf_InstrHandle instr, unsigned branch_num )
 {
-    assert(branch_num < code->m_offcount);
-    return code->m_off[branch_num];
-} // vf_get_instruction_branch
+    assert( branch_num < instr->m_offcount );
+    return instr->m_off[branch_num];
+}                               // vf_get_instruction_branch
 
 /**
  * Allocates memory for a new stack map vector.
@@ -1066,16 +1130,13 @@
  * @param[in]  len    vector length
  * @param[in]  pool   memory pool
  */
-static inline void 
-vf_new_vector( vf_MapEntry_t** vector,
-               unsigned len,
-               vf_VerifyPool_t *pool)
+static inline void
+vf_new_vector( vf_MapEntry **vector, unsigned len, vf_Pool *pool )
 {
     // create new vector
-    (*vector) = (vf_MapEntry_t*) vf_alloc_pool_memory(pool, 
-        len * sizeof(vf_MapEntry_t));
-    return;
-} // vf_new_vector
+    ( *vector ) =    (vf_MapEntry*)vf_palloc( pool,
+                                              len * sizeof( vf_MapEntry ) );
+}                               // vf_new_vector
 
 /**
  * Sets a reference data type for a given stack map vector entry.
@@ -1085,24 +1146,53 @@
  * @param[in]      type   reference type
  */
 static inline void
-vf_set_vector_stack_entry_ref( vf_MapEntry_t* vector,
-                               unsigned num,
-                               vf_ValidType_t* type)
+vf_set_vector_stack_entry_ref( vf_MapEntry *vector,
+                               unsigned num, vf_ValidType *type )
 {
     // set a stack map vector entry by ref
     vector[num].m_type = SM_REF;
     vector[num].m_vtype = type;
-} // vf_set_vector_stack_entry_ref
+}                               // vf_set_vector_stack_entry_ref
+
+/**
+ * Calculates an index of instruction.
+ * @param[in] pc  a bytecode index at instruction start
+ * @param[in] ctx a verification context
+ * @return    an instruction index
+ */
+static inline unsigned
+vf_bc_to_instr_index( unsigned short pc, vf_ContextHandle ctx )
+{
+    vf_InstrHandle instr = ctx->m_bc[pc].m_instr;
+    assert( instr );
+    return instr - ctx->m_instr;
+}
+
+/**
+ * For a given instruction gets a start pointer of the next instruction or the
+ * pointer which follows the last bytecode of the method for the last instruction.
+ * @param[in] instr an instruction handle
+ * @param[in] ctx   a verification context
+ * @return a pointer which follows a given instruction
+ */
+static inline const unsigned char *
+vf_get_instr_end( vf_InstrHandle instr, vf_ContextHandle ctx )
+{
+    if( instr + 1 == ctx->m_last_instr ) {
+        return ctx->m_bytes + ctx->m_len;
+    }
+    return ( instr + 1 )->m_addr;
+}
 
 /**
  * Calls destructor of graph, if any.
  *
  * @param[in] context a context of verifier
  */
-void vf_free_graph( vf_Context_t* context );
+void vf_free_graph( vf_Context *context );
 
 /**
- * Inline subroutines in the call graph.
+ * Mark subroutine code.
  *
  * <p>Here is the algorithm sketch: we define subroutine boundaries with
  * simplified data flow analysis and duplicate subroutine nodes
@@ -1110,11 +1200,19 @@
  * <a href="http://wiki.apache.org/harmony/Subroutine_Verification">wiki
  * page</a>.</p>
  *
- * @param[in] context a verifier context
+ * @param ctx a verifier context
+ * @return VER_OK if no graph structure inconsistencies were detected during marking,
+ * an error code otherwise
+ */
+vf_Result vf_mark_subroutines( vf_Context *ctx );
+
+/**
+ * Inline subroutines in the call graph.
+ *
+ * @param ctx a verifier context
  * @return VER_OK if subroutines were inlined successfully,
  * an error code otherwise
  */
-Verifier_Result
-vf_inline_subroutines(vf_ContextHandle context);
+vf_Result vf_inline_subroutines( vf_Context *ctx );
 
 #endif // _VERIFIER_REAL_H_

Modified: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.cpp?view=diff&rev=528575&r1=528574&r2=528575
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.cpp (original)
+++ harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.cpp Fri Apr 13 11:26:27 2007
@@ -16,24 +16,578 @@
  */
 #include "ver_subroutine.h"
 
-static vf_Result
-MarkTopcode(vf_ContextHandle context, vf_NodeHandle nh) {
+#ifdef _VF_DEBUG
+/**
+ * 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)
+{
+    unsigned index = 0;
+    for (vf_SubHandle s = ctx->m_sub_ctx->m_sub; s; s = s->m_next) {
+        if (s == sub) {         // subroutine found
+            return index;
+        }
+        index++;
+    }
+    VF_DIE("vf_get_sub_num: Cannot find a subroutine " << sub <<
+        " in a list");
+    return 0;
+}
+
+void vf_Graph::DumpSub(vf_SubHandle sub)
+{
+    if (sub) {
+        VF_DEBUG("Subroutine:");
+        if (sub->m_entry) {
+            VF_DEBUG("    Entry node: " << GetNodeNum(sub->m_entry));
+        } else {
+            VF_DEBUG("    Entry node undefined");
+        }
+        if (sub->m_ret) {
+            VF_DEBUG("    Return node: " << GetNodeNum(sub->m_ret));
+        } else {
+            VF_DEBUG("    Return node undefined");
+        }
+    }
+}                               // vf_Graph::DumpSub
+
+static void DumpNodeStack(vf_Context *ctx)
+{
+    vf_NodeStackHandle p_element = ctx->m_sub_ctx->m_path_start;
+    bool fork_found = false;
+    unsigned count = 0;
+
+    VF_DEBUG("Dumping path: ");
+    for (; p_element; p_element = p_element->m_next, count++) {
+        if (p_element == ctx->m_sub_ctx->m_path_fork) {
+            fork_found = true;
+            VF_DEBUG("Fork");
+        }
+        VF_DEBUG("  Node #" << ctx->m_graph->GetNodeNum(p_element->m_node));
+    }
+    assert(fork_found || !ctx->m_sub_ctx->m_path_fork);
+    VF_DEBUG("Totally " << count << " nodes");
+}                               // DumpNodeStack
+#endif //  _VF_DEBUG
+
+
+/**
+ * Allocates memory for subroutine context.
+ * @param ctx a verification context
+ */
+static void AllocateSubContext(vf_Context *ctx)
+{
+    vf_Pool *pool = ctx->m_pool;
+
+    vf_SubContext *sub_ctx = (vf_SubContext *) vf_palloc(pool,
+        sizeof(vf_SubContext));
+    ctx->m_sub_ctx = sub_ctx;
+    sub_ctx->m_pool = pool;
+}                               // AllocateSubContext
+
+
+/**
+ * Adds a new subroutine into subroutine array.
+ * @param[in] ret_node a node containing a corresponding <code>ret</code>
+ * @param[in] sub_ctx  a subroutine verification context
+ * @return a sub handle
+ */
+static vf_Sub *AddNewSub(vf_NodeHandle ret_node, vf_SubContext * sub_ctx)
+{
+    vf_Sub *sub = (vf_Sub *) vf_palloc(sub_ctx->m_pool, sizeof(vf_Sub));
+    sub->m_next = sub_ctx->m_sub;
+    sub_ctx->m_sub = sub;
+    sub->m_ret = ret_node;
+    return sub;
+}                               // AddNewSub
+
+/**
+ * Adds a node to the subroutine.
+ * @param[in] sub a subroutine
+ * @param[in] node a node which is a part of this subroutine
+ */
+static void AddSubNode(vf_Sub *sub, vf_Node *node)
+{
+    assert(!node->m_sub);       // node is added once
+    node->m_sub = sub;
+    sub->m_nodenum++;
+    // a number of out edges for reachable node won't
+    // change while removing a dead code
+    sub->m_out_edgenum += node->m_outnum;
+}                               // AddNewSub
+
+static inline vf_Result ResolveSubroutineEntryPoint(vf_Node *node,
+    vf_Context *ctx)
+{
+    //initialize vector
+    vf_MapVector *map = ctx->m_map;
+
+    // the path element node to iterate from
+    vf_NodeStackHandle p_element = ctx->m_sub_ctx->m_path_fork;
+    if (!p_element) {
+        p_element = ctx->m_sub_ctx->m_path_start;
+        map->m_number = ctx->m_maxlocal;
+        unsigned index;
+        for (index = 0; index < map->m_number; index++) {
+            map->m_local[index].m_type = SM_ANY;
+        }
+
+        map->m_depth = p_element->m_node->m_inmap.m_depth;
+        for (index = 0; index + 1 < map->m_depth; index++) {
+            map->m_stack[index].m_type = SM_ANY;
+        }
+        map->m_stack[index].m_type = SM_RETURN_ADDR;
+        map->m_stack[index].m_pc =
+            p_element->m_node->m_start->m_addr - ctx->m_bytes;
+    }
+
+    VF_DUMP(DUMP_NODESTACK, DumpNodeStack(ctx));
+    for (; p_element; p_element = p_element->m_next) {
+        vf_Result result =
+            vf_set_node_out_vector(p_element->m_node, map, ctx);
+        if (result != VER_OK) {
+            return result;
+        }
+    }
+
+    // since a copy flag is set for SM_RETURN_ADDR entries,
+    // <code>ctx->m_buf</code> contains the last processed entry, i.&nbsp;e.
+    // an entry for <code>ret</code>
+    assert(ctx->m_buf->m_pc);
+    assert(SM_RETURN_ADDR == ctx->m_buf->m_type);
+    assert(node->m_outmap.m_depth == ctx->m_map->m_depth);
+    ((vf_Sub *) node->m_sub)->m_entry =
+        ctx->m_graph->GetNodeFromBytecodeIndex(ctx->m_buf->m_pc);
     return VER_OK;
-} // MarkTopcode
+}                               // ResolveSubroutineEntryPoint
+
+static vf_Result MarkNode(vf_NodeStack &stack, vf_Context *ctx);
 
-static vf_Result
-InlineMarkedSubNodes(vf_ContextHandle context) {
+/**
+ * Fills <code>m_sub</code> field of the node using <code>m_sub</code> field of
+ * the next node using the following rules:
+ * <ul>
+ * <li>If the mark of the next node is empty, it doesn't count.</li>
+ * <li>If the mark of this node is empty, it is set to the following node
+ * mark.</li>
+ * <li>Otherwise node marks should be equal, or an error should be reported.</li>
+ * </ul>
+ */
+static inline vf_Result
+MergeSubMarks(vf_Node *node, vf_NodeHandle next_node, vf_Context *ctx)
+{
+    if (next_node->m_sub) {
+        VF_TRACE("sub.mark", "sub[" << ctx->m_graph->GetNodeNum(node)
+            << "] := sub[" << ctx->m_graph->GetNodeNum(next_node->
+                m_sub->m_ret)
+            << "] (" << vf_get_sub_num(next_node->m_sub, ctx) << ")");
+        if (node->m_sub == NULL) {
+            AddSubNode((vf_Sub *) next_node->m_sub, node);
+        } else if (node->m_sub != next_node->m_sub) {
+            VF_REPORT(ctx,
+                "A subroutine splits execution into "
+                "several ret instructions");
+            return VER_ErrorJsrMultipleRet;
+        }
+    }
     return VER_OK;
-} // InlineMarkedSubNodes
+}                               // MergeSubMarks
 
-vf_Result
-vf_inline_subroutines(vf_ContextHandle context) {
 
-    vf_Result r = MarkTopcode(context, context->m_graph->GetFirstNode());
+/**
+ * Marks an edge end node.
+ */
+static inline vf_Result
+FollowEdge(vf_Node *node, vf_NodeStack &stack, vf_Context *ctx)
+{
+    vf_Result r = MarkNode(stack, ctx);
     if (VER_OK != r) {
         return r;
     }
 
-    r = InlineMarkedSubNodes(context);
+    return MergeSubMarks(node, stack.m_node, ctx);
+}                               // FollowEdge
+
+/**
+ * Marks a <code>jsr</code> edge end node. If the subroutine returns, marks a node, which
+ * follows the edge start node.
+ */
+static inline vf_Result
+FollowJsrEdge(vf_Node *node, vf_NodeStack &stack, vf_Context *ctx)
+{
+    bool set_start = !ctx->m_sub_ctx->m_path_start;
+    if (set_start) {
+        ctx->m_sub_ctx->m_path_start = &stack;
+    }
+    vf_Result r = MarkNode(stack, ctx);
+    if (VER_OK != r) {
+        return r;
+    }
+
+    if (stack.m_node->m_sub) {
+        // if this jsr returns we need to process a node which
+        // follows after edge start node
+        if (stack.m_node->m_sub->m_entry != stack.m_node) {
+            VF_REPORT(ctx, "Subroutines merge their execution");
+            return VER_ErrorDataFlow;
+        }
+
+        ctx->m_sub_ctx->m_path_fork = &stack;
+
+        // select and check the following node
+        stack.Set(node + 1, stack.m_node->m_sub->m_ret->m_outmap.m_depth);
+        if (VF_NODE_END_ENTRY == stack.m_node->m_type) {
+            VF_REPORT(ctx, "Falling off the end of the code");
+            return VER_ErrorBranch;
+        }
+        assert(VF_NODE_CODE_RANGE == stack.m_node->m_type);
+
+        r = MarkNode(stack, ctx);
+        ctx->m_sub_ctx->m_path_fork = NULL;
+        if (VER_OK != r) {
+            return r;
+        }
+    }
+
+    if (set_start) {
+        ctx->m_sub_ctx->m_path_start = NULL;
+    }
+    return MergeSubMarks(node, stack.m_node, ctx);
+}                               // FollowJsrEdge
+
+/**
+ * Marks a given node and follows <i>out</i> edges.
+ * @param[in] stack a reference to the stack element for the given node
+ * @param[in] ctx   a verification context
+ * @return VER_OK if marking was successful, an error code otherwise
+ */
+static vf_Result MarkNode(vf_NodeStack &stack, vf_Context *ctx)
+{
+    vf_Graph *graph = ctx->m_graph;
+    vf_Result r;
+
+    vf_Result result =
+        vf_check_node_stack_depth(stack.m_node, stack.m_depth, ctx);
+    if (result != VER_Continue) {
+        return result;
+    }
+    VF_TRACE("sub.mark",
+        "Processing node " << graph->GetNodeNum(stack.m_node));
+
+    if (VF_NODE_CODE_RANGE == stack.m_node->m_type) {
+        vf_InstrType last_instr_type = stack.m_node->m_end->m_type;
+
+        if (VF_INSTR_RET == last_instr_type) {
+            if (!ctx->m_sub_ctx->m_path_start) {
+                VF_REPORT(ctx, "Reached ret not using jsr branches");
+                return VER_ErrorJsrOther;
+            }
+            vf_Sub *sub = AddNewSub(stack.m_node, ctx->m_sub_ctx);
+            AddSubNode(sub, stack.m_node);
+            r = ResolveSubroutineEntryPoint(stack.m_node, ctx);
+            if (VER_OK != r) {
+                return r;
+            }
+        }
+    }
+
+    vf_NodeStack next_stack;
+    stack.m_next = &next_stack;
+    for (vf_EdgeHandle outedge = stack.m_node->m_outedge;
+        outedge; outedge = outedge->m_outnext) {
+        next_stack.Set(outedge->m_end, stack.m_depth);
+        if (!vf_is_jsr_branch(outedge, ctx)) {
+            r = FollowEdge(stack.m_node, next_stack, ctx);
+        } else {
+            assert(VF_NODE_CODE_RANGE == outedge->m_end->m_type);
+            assert(!outedge->m_outnext);
+            r = FollowJsrEdge(stack.m_node, next_stack, ctx);
+        }
+        if (VER_OK != r) {
+            return r;
+        }
+    }
+
+    return VER_OK;
+}                               // MarkNode
+
+
+vf_Result vf_mark_subroutines(vf_Context *ctx)
+{
+    vf_Graph *graph = ctx->m_graph;
+    AllocateSubContext(ctx);
+
+    vf_NodeStack bottom =
+        { (vf_Node *) ctx->m_graph->GetStartNode(), 0, NULL };
+    vf_Result r = MarkNode(bottom, ctx);
     return r;
-} // InlineSubroutines
+}                               // vf_mark_subroutines
+
+static vf_Result AddDupCount(vf_Sub *sub, unsigned &count, vf_Context *ctx)
+{
+    VF_TRACE("dupcount", "Calculating a duplication count for a subroutine #"
+        << vf_get_sub_num(sub, ctx));
+    if (ALL_BITS_SET == sub->m_dupcount) {
+        VF_REPORT(ctx, "Found a recursive subroutine call sequence");
+        return VER_ErrorJsrRecursive;
+    }
+
+    if (!sub->m_dupcount) {
+        sub->m_dupcount = ALL_BITS_SET;
+
+        unsigned sum = 0;
+        for (vf_EdgeHandle inedge = sub->m_entry->m_inedge;
+            inedge; inedge = inedge->m_innext) {
+            vf_NodeHandle node = inedge->m_start;
+
+            if (vf_is_jsr_branch(inedge, ctx)) {
+                assert(!inedge->m_outnext);
+                if (node->m_sub == NULL) {
+                    sum++;
+                } else if (node->m_sub != sub) {
+                    AddDupCount((vf_Sub *) node->m_sub, sum, ctx);
+                }               // else this call served as unconditional internal branch
+            } else if (node->m_sub != sub) {
+                VF_REPORT(ctx,
+                    "A subroutine splits execution into "
+                    "several ret instructions");
+                return VER_ErrorJsrMultipleRet;
+            }
+        }
+        sub->m_dupcount = sum;
+    }
+
+    VF_TRACE("dupcount", "A duplication count for a subroutine #"
+        << vf_get_sub_num(sub, ctx) << " is " << sub->m_dupcount);
+    count += sub->m_dupcount;
+    return VER_OK;
+}                               // AddSubDupCount
+
+static void InlineSubNodes(vf_ContextHandle ctx)
+{
+    vf_Graph *graph = ctx->m_graph;
+    vf_Sub *sub;
+
+    for (sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+        sub->m_nodes =
+            (vf_NodeHandle *) vf_palloc(ctx->m_sub_ctx->m_pool,
+            sub->m_nodenum * sizeof(vf_NodeHandle));
+    }
+
+    // populate subroutine node get the next node after the start node
+    vf_Node *node = (vf_Node *) graph->GetStartNode() + 1;
+    for (; VF_NODE_END_ENTRY != node->m_type; node++) {
+        if (node->m_sub) {
+            vf_Sub *sub = (vf_Sub *) node->m_sub;
+            node->m_nodecount = sub->m_index;
+            sub->m_nodes[sub->m_index++] = node;
+        }
+    }
+
+    for (sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+        // clear sub indices
+        assert(sub->m_nodenum == sub->m_index);
+        sub->m_index = 0;
+        // duplicate subroutine nodes
+        assert(sub->m_dupcount);
+        if (sub->m_dupcount == 1) {
+            continue;
+        }
+        vf_NodeHandle *p_node = sub->m_nodes;
+        vf_Node *new_node = sub->m_copies =
+            graph->AddNodes((sub->m_dupcount - 1) * sub->m_nodenum);
+        for (unsigned node_index = 0; node_index < sub->m_nodenum;
+            node_index++, p_node++) {
+            for (unsigned index = 1; index < sub->m_dupcount;
+                index++, new_node++) {
+                *new_node = **p_node;
+                // edges are outdated, delete them
+                new_node->m_inedge = new_node->m_outedge = NULL;
+                new_node->m_outnum = 0;
+                VF_TRACE("sub.inline",
+                    "Copied node " << graph->GetNodeNum(*p_node)
+                    << " to " << graph->GetNodeNum(new_node));
+            }
+        }
+    }
+    assert(0 == ctx->m_graph->HasMoreNodeSpace());
+
+}                               // InlineSubNodes
+
+/**
+ * Redirects subroutine calls to separate subroutine copies.
+ */
+static void InlineInEdges(vf_ContextHandle ctx)
+{
+    vf_Graph *graph = ctx->m_graph;
+
+    for (vf_SubHandle sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+        ((vf_Sub *) sub)->m_following_nodes =
+            (vf_Node **) vf_palloc(ctx->m_sub_ctx->m_pool,
+            sub->m_dupcount * sizeof(vf_Node *));
+        vf_NodeHandle sub_entry_copy =
+            sub->m_copies + sub->m_entry->m_nodecount * (sub->m_dupcount -
+            1) - 1;
+        vf_EdgeHandle *p_next_edge =
+            (vf_EdgeHandle *) & sub->m_entry->m_inedge;
+        vf_Edge *inedge = (vf_Edge *) sub->m_entry->m_inedge;
+        while (inedge) {
+            if (vf_is_jsr_branch(inedge, ctx)) {
+                if (sub->m_index) {
+                    assert(sub->m_copies);
+                    assert(sub->m_dupcount);
+                    // remove the edge from the list
+                    *p_next_edge = inedge->m_innext;
+                    // redirect jsr edge to correspondent subroutine copy
+                    inedge->m_end = sub_entry_copy + sub->m_index;
+                }
+                // store return point
+                vf_Node *next_node = (vf_Node *) inedge->m_start + 1;
+                assert(VF_NODE_CODE_RANGE == next_node->m_type);
+                sub->m_following_nodes[((vf_Sub *) sub)->m_index++] =
+                    next_node;
+            }
+            p_next_edge = &inedge->m_innext;
+            inedge = (vf_Edge *) inedge->m_innext;
+        }
+        assert(sub->m_index);   // there was at least one branch
+    }
+}                               // InlineInEdges
+
+/**
+ * Subroutine calls are redirected to correspondent subroutine copies,
+ * other edges are just duplicated.
+ */
+static void InlineOutEdges(vf_ContextHandle ctx)
+{
+    vf_Graph *graph = ctx->m_graph;
+
+    for (vf_SubHandle sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+        if (!sub->m_copies) {
+            continue;
+        }
+        vf_Node *copy = sub->m_copies;
+        for (unsigned node_index = 0; node_index < sub->m_nodenum;
+            node_index++, copy += sub->m_dupcount - 1) {
+            vf_NodeHandle node = sub->m_nodes[node_index];
+
+            for (vf_EdgeHandle outedge = node->m_outedge; outedge;
+                outedge = outedge->m_outnext) {
+                vf_NodeHandle end_node = outedge->m_end;
+                vf_SubHandle end_sub = end_node->m_sub;
+
+                vf_Node *c = copy;
+                if (NULL == end_sub) {
+                    for (unsigned index = 1; index < sub->m_dupcount; index++) {
+                        graph->NewEdge(c++, (vf_Node *) end_node);
+                    }
+                } else if (node->m_sub == end_sub) {
+                    vf_Node *e = sub->m_copies +
+                        end_node->m_nodecount * (sub->m_dupcount - 1);
+                    for (unsigned index = 1; index < sub->m_dupcount; index++) {
+                        graph->NewEdge(c++, e++);
+                    }
+                } else {
+                    assert(vf_is_jsr_branch(outedge, ctx));
+                    assert(!outedge->m_outnext);
+                    // an end node
+                    vf_Node *e = end_sub->m_copies +
+                        end_sub->m_entry->m_nodecount *
+                        (end_sub->m_dupcount - 1) - 1;
+                    // a node next to the start node
+                    vf_Node *n = c + (sub->m_dupcount - 1);
+                    for (unsigned index = 1;
+                        index < node->m_sub->m_dupcount; index++) {
+                        // direct jsr edge to correspondent subroutine copy
+                        graph->NewEdge(c++, e + end_sub->m_index);
+                        // store return point
+                        assert(VF_NODE_CODE_RANGE == n->m_type);
+                        end_sub->m_following_nodes[((vf_Sub *) end_sub)->
+                            m_index++] = n++;
+                    }
+                }
+            }
+        }
+    }
+}                               // InlineOutEdges
+
+/**
+ * Adds a back branch from <code>ret</code> nodes to a node
+ * which follows the correspondent <code>jsr</code> call node.
+ */
+static void InlineRetEdges(vf_ContextHandle ctx)
+{
+    vf_Graph *graph = ctx->m_graph;
+    for (vf_SubHandle sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+
+        vf_Node *ret_node = (vf_Node *) sub->m_ret;
+        vf_Node **next_node = sub->m_following_nodes;
+        graph->NewEdge(ret_node, *(next_node++));
+
+        vf_Node *ret_node_copy =
+            sub->m_copies + ret_node->m_nodecount * (sub->m_dupcount - 1);
+        for (unsigned index = 1; index < sub->m_dupcount; index++) {
+            // direct ret entry to the return point
+            graph->NewEdge(ret_node_copy++, *(next_node++));
+        }
+    }
+    assert(0 == ctx->m_graph->HasMoreEdgeSpace());
+}                               // InlineRetEdges
+
+/**
+ * Checks that every subroutine copy gets its call and
+ * all edges are created.
+ */
+static void CheckDupCounts(vf_ContextHandle ctx)
+{
+#if _VF_DEBUG
+    for (vf_SubHandle sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+        assert(sub->m_dupcount == sub->m_index);
+    }
+#endif // _VF_DEBUG
+}
+
+/**
+ * Calculates a number of additional nodes and edges and adds them
+ * to the graph.
+ */
+vf_Result vf_inline_subroutines(vf_Context *ctx)
+{
+    if (NULL == ctx->m_sub_ctx->m_sub) {
+        // subroutines are not reachable
+        return VER_OK;
+    }
+
+    unsigned count;
+    unsigned nodes = 0, edges = 0;
+    for (vf_Sub *sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+        vf_Result r = AddDupCount(sub, count, ctx);
+        if (VER_OK != r) {
+            return r;
+        }
+        // one copy already present in the graph
+        nodes += (sub->m_dupcount - 1) * sub->m_nodenum;
+        edges += (sub->m_dupcount - 1) * sub->m_out_edgenum;
+        // there is an additional edge from every ret
+        edges += sub->m_dupcount;
+    }
+    ctx->m_graph->CreateEdges(edges);
+
+    if (nodes) {
+        ctx->m_graph->CreateNodes(nodes);
+        InlineSubNodes(ctx);
+    }
+    InlineInEdges(ctx);
+
+    if (nodes) {
+        InlineOutEdges(ctx);
+    }
+
+    CheckDupCounts(ctx);
+    InlineRetEdges(ctx);
+    return VER_OK;
+}                               // vf_inline_subroutines

Modified: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.h?view=diff&rev=528575&r1=528574&r2=528575
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.h (original)
+++ harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.h Fri Apr 13 11:26:27 2007
@@ -16,8 +16,119 @@
  */
 #include "ver_graph.h"
 
+/**
+ * @ingroup Handles
+ * A handle of subroutine verification context.
+ */
+typedef const struct vf_SubContext *vf_SubContextHandle;
+/**
+ * @ingroup Handles
+ * A handle of subroutine verification context.
+ */
+typedef const struct vf_NodeStack *vf_NodeStackHandle;
+
+/**
+ * Subroutine info.
+ */
+struct vf_Sub
+{
+    /**
+     * A reference to the next subroutine.
+     */
+    vf_Sub *m_next;
+    /**
+     * A node which starts with subroutine entry point.
+     */
+    vf_NodeHandle m_entry;
+    /**
+     * A node which ends with ret instruction.
+     */
+    vf_NodeHandle m_ret;
+    /**
+     * A number of different <code>jsr</code> sequences to access
+     * this subroutine.
+     */
+    unsigned m_dupcount;
+    /**
+     * A number of nodes for this subroutine.
+     */
+    unsigned m_nodenum;
+    /**
+     * Subroutine nodes.
+     */
+    vf_NodeHandle *m_nodes;
+    /**
+     * Subroutine node copies. For each of <code>m_nodenum</code> nodes
+     * from <code>m_nodes</code> the (m_dupcount - 1) node copies follow
+     * one by one starting from this pointer.
+     * <code>NULL</code> when m_dupcount == 1.
+     */
+    vf_Node *m_copies;
+    /**
+     * For each of m_dupcount subroutine copies contain a return node for
+     * this copy.
+     */
+    vf_Node **m_following_nodes;
+    /**
+     * A number of edges between subroutine nodes.
+     */
+    unsigned m_out_edgenum;
+    /**
+     * A current duplication index.
+     */
+    unsigned m_index;
+};
+
+/**
+ * A stack of subsequent nodes representing a path traversing the graph, in
+ * particular a path to a <code>ret</code> node.
+ */
+struct vf_NodeStack
+{
+    /**
+     * A current node.
+     */
+    vf_Node *m_node;
+    /**
+     * An <i>out</i> stack depth of the node.
+     */
+    unsigned m_depth;
+    /**
+     * When a next stack element is created, points to the next stack element.
+     */
+    vf_NodeStackHandle m_next;
+
+    void Set(vf_NodeHandle node, unsigned depth)
+    {
+        m_node = (vf_Node *) node;
+        m_depth = depth;
+        m_next = NULL;
+    }
+};
+
 
 /**
- * Verifier error codes.
+ * Aggregated subroutine data.
  */
-typedef Verifier_Result vf_Result;
+struct vf_SubContext
+{
+    /**
+     * Dedicated memory pool.
+     */
+    vf_Pool *m_pool;
+    /**
+     * A head of a list of subroutine descriptors.
+     */
+    vf_Sub *m_sub;
+    /**
+     * A start of a path to the current <code>ret</code>.
+     */
+    vf_NodeStackHandle m_path_start;
+    /**
+     * After the <code>ret</code> is resolved a <code>ctx->m_map</code> contains a
+     * correct input map for a node which follows <code>jsr</code> call. This is
+     * a pointer to the corresponding node stack. If this pointer is
+     * <code>NULL</code> we start from <code>m_path_start</code> stack entry.
+     */
+    vf_NodeStackHandle m_path_fork;
+};



Mime
View raw message