harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mloe...@apache.org
Subject svn commit: r584118 [5/6] - in /harmony/enhanced/drlvm/trunk: build/make/components/vm/ vm/vmcore/include/ vm/vmcore/src/class_support/ vm/vmcore/src/verifier-3363/ vm/vmcore/src/verifier-3363/base/ vm/vmcore/src/verifier-3363/java5/ vm/vmcore/src/veri...
Date Fri, 12 Oct 2007 10:32:52 GMT
Added: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/context_5.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/context_5.cpp?rev=584118&view=auto
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/context_5.cpp (added)
+++ harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/context_5.cpp Fri Oct 12 03:32:50 2007
@@ -0,0 +1,680 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+/** 
+ * @author Mikhail Loenko, Vladimir Molotkov
+ */  
+
+#include "context_5.h"
+namespace CPVerifier_5 {
+
+    /*
+    This method makes the first pass through the instruction set.
+    On that pass we check that all instruction have valid opcode, that no
+    jumps, no exception handlers lead to the middle of instruction nor 
+    out of the method. it checks that control does not flow out of the method.
+
+    It also finds all instructions that have multiple predecessors 
+    (like goto tagrtes), this information will be used on the second Pass
+
+    Method starts with the instruction <code>instr</code> for each it was invoked and go down 
+    filling the mask array with the flags. On this pass it distignushes
+    4 types of instructions:
+    0 - non-passed instruction or dead code
+    1 - passed instruction
+    2 - middle of passed instruction
+    3 - passed multiway instruction (having many predecessors)
+
+    If the method comes to a return, ret, athrow, or an already passed instruction, it terminates
+    If it comes to a switch, an if, or a jsr then it push all branches onto the stack
+    If it comes to a goto then it continues from the jump target
+    */
+
+    vf_Result vf_Context_5::parse(Address instr) {
+        // instruction is out of the method or in the middle of another instruction
+        if( instr > m_code_length || props.isOperand(instr) ) {
+            return error(VF_ErrorCodeEnd, "jump to the middle of instruction or out of the method");
+        }
+
+        while( instr < m_code_length ) {
+            if( props.isParsePassed(instr) ) {
+                // more than one branch leads to this instruction
+                if( !dead_code_parsing ) {
+                    props.setMultiway(instr);
+                }
+                return VF_OK;
+            }
+
+            OpCode opcode = (OpCode)m_bytecode[instr];
+            processed_instruction = instr;
+
+            // does code correspond to any valid instruction?
+            if( !instr_is_valid_bytecode(opcode) ) {
+                return error(VF_ErrorInstruction, "invalid opcode");
+            }
+
+            // keep all nessesary information about instruction
+            ParseInfo &pi = instr_get_parse_info(opcode);
+
+            // get MINIMAL length of the instruction with operands
+            unsigned instr_len = instr_get_minlen(pi);
+
+            // code does not correspond to any valid instruction or method length is less than required
+            if( instr + instr_len > m_code_length ) {
+                return error(VF_ErrorInstruction, "method length is less than required");
+            }
+
+            if( instr_is_compound(opcode, pi) ) {
+                // get ACTUAL length for variable length insgtructions
+                instr_len = instr_get_len_compound(instr, opcode);
+
+                // method length is less than required
+                if( instr + instr_len > m_code_length ) {
+                    return error(VF_ErrorInstruction, "compound instruction: method length is less than required");
+                }
+            }
+
+            // mark this instruction as processed
+            assert( !props.isParsePassed(instr) );
+            props.setParsePassed(instr);
+
+            // check that no other instruction jumps to the middle of the current instruction
+            for( Address i = instr + 1; i < instr + instr_len; i++ ) {
+                if( !props.setOperand(i) ) {
+                    return error(VF_ErrorUnknown, "jump to the middle of instruction");
+                }
+            }
+
+
+
+            if( instr_is_regular(pi) ) {
+                //regular instruction - go to the next instruction
+                instr += instr_len;
+            } else if( instr_is_jump(pi) ) {
+                // goto, goto_w, if*
+
+                Address target = instr_get_jump_target(pi, m_bytecode, instr);
+
+                // jump out of method or to the middle of an instruction
+                if( target >= m_code_length || props.isOperand(target) ) {
+                    return error(VF_ErrorBranch, "jump out of method or to the middle of an instruction");
+                }
+
+                if( instr_direct(pi, opcode, m_bytecode, instr) ) {
+                    //TODO: though the spec does not require to check the dead code for correctness
+                    //RI seems to check it and some Harmony negative tests have broken dead code
+
+                    dead_code_stack.push(instr+instr_len);
+
+                    instr = target; // it is not an if* - go to jump target
+                } else {
+                    // process conditional jump target or jsr
+                    stack.push(target);
+
+                    // go to the next instruction
+                    instr += instr_len;
+                }
+            } else if( instr_direct(pi, opcode, m_bytecode, instr) ) {
+                dead_code_stack.push(instr+instr_len);
+
+                // it is not a jump ==> it is return or throw or ret
+                return VF_OK;
+            } else {
+                assert( instr_is_switch(pi) );
+
+                Address next_target_adr = (instr & (~3) ) + 4;
+
+                //default target
+                Address target = instr + read_int32(m_bytecode + next_target_adr);
+                stack.push(target);
+
+                // in tableswitch instruction target offsets are stored with shift = 4,
+                // in lookupswitch with shift = 8
+                int shift = (opcode == OP_TABLESWITCH) ? 4 : 8;
+
+                for (next_target_adr += 12;
+                    next_target_adr < instr + instr_len;
+                    next_target_adr += shift)
+                {
+                    target = instr + read_int32(m_bytecode + next_target_adr);
+                    // jump out of method or to the middle of an instruction
+                    if( target >= m_code_length || props.isOperand(target) ) {
+                        return error(VF_ErrorBranch, "jump out of method or to the middle of an instruction");
+                    }
+                    // process conditional jump target
+                    stack.push(target);
+                }
+
+                return VF_OK;
+            }
+        }
+
+        //it might be a dead code -- code followed by JSR which never returns
+        //if it's a dead code - it's OK, if it's not - we will catch it on the second pass
+        return VF_OK;
+    }
+
+
+    vf_Result vf_Context_5::StartLinearDataflow(Address instr) {
+
+        vf_Result tcr;
+        int workmap_is_a_copy_of_stackmap;
+
+        if( props.isDataflowPassed(instr) ) {
+            //passed since it was added to the stack
+            assert(instr);
+            return VF_OK;
+        }
+
+        if (instr) {
+            workmap_is_a_copy_of_stackmap = true;
+            fill_workmap(instr);
+        } else {
+            //for the first instruction it does not matter if it is multiway or not
+            workmap_is_a_copy_of_stackmap = false;
+            // may return error in case of method's wrong signature
+            if((tcr = create_method_initial_workmap()) != VF_OK ) {
+                return tcr;
+            }
+        }
+
+        //list of handlers unknown
+        next_start_pc = 0;
+
+        return DataflowLoop(instr, workmap_is_a_copy_of_stackmap);
+    }
+
+    vf_Result vf_Context_5::SubroutineDone(Address subr) {
+        SubroutineData *subrdata = ((PropsHead*)props.getInstrProps(subr)->next)->getSubrData(m_max_stack + m_stack_start);
+        subrdata->subrDataflowed = 1;
+
+        if( !subrdata->retCount ) {
+            //no ret from subroutine -- dead code follows
+            return VF_OK;
+        }
+
+        Address jsr = subrdata->caller;
+
+        OpCode opcode = (OpCode)m_bytecode[jsr];
+        ParseInfo &pi = instr_get_parse_info(opcode);
+
+        processed_instruction = jsr;
+        if (jsr || props.isMultiway(jsr)) {
+            //note that in SubroutineDone unlike StartLinearDataflow we get workmap from stackmap
+            //in case of the first instruction of the method
+            fill_workmap(jsr);
+        } else {
+            vf_Result tcr = create_method_initial_workmap();
+            assert(tcr == VF_OK); // method's signature was already verified in StartLinearDataflow
+        }
+
+        //list of handlers unknown
+        next_start_pc = 0;
+
+        restore_workmap_after_jsr(subr);
+
+        //make a shift to the instr following jsr
+        Address instr = jsr + (opcode == OP_JSR_W ? 5 : 3);
+        assert(opcode == OP_JSR || opcode == OP_JSR_W);
+
+
+        return DataflowLoop(instr, 0);
+    }
+
+
+
+    // iterate thru the instructions starting with 'instr'
+    vf_Result vf_Context_5::DataflowLoop (Address instr, int workmap_is_a_copy_of_stackmap) {
+
+        vf_Result tcr;
+
+        while( instr < m_code_length ) {
+            if( !workmap_is_a_copy_of_stackmap && props.isMultiway(instr) ) {
+                //if instruction has a stackmap and workmap was not just obtained from that stackmap
+                // add constraint: workmap is assignable to stackmap(instr)
+                if( (tcr=new_generic_vector_constraint(instr)) != VF_OK ) {
+                    return tcr;
+                }
+
+                if( props.isDataflowPassed(instr) ) {
+                    return VF_OK;
+                }
+
+                fill_workmap(instr);
+            }
+            workmap_is_a_copy_of_stackmap = false;
+
+            OpCode opcode = (OpCode)m_bytecode[instr];
+            processed_instruction = instr;
+            // keep all nessesary information about instruction
+            ParseInfo &pi = instr_get_parse_info(opcode);
+
+            //check IN types, create OUT types, check exception
+            if( (tcr=dataflow_instruction(instr)) != VF_OK ) {
+                return tcr;
+            }
+
+            props.setDataflowPassed(instr);
+
+            unsigned instr_len = instr_get_minlen(pi);
+            if( instr_is_compound(opcode, pi) ) {
+                // get ACTUAL length for variable length insgtructions
+                instr_len = instr_get_len_compound(instr, opcode);
+            }
+
+            if( instr_is_jump(pi) ) {
+                Address target = instr_get_jump_target(pi, m_bytecode, instr);
+
+                if( props.isMultiway(target) || instr_is_jsr(opcode) ) {
+                    //TODO: need to test commented out optimization
+                    //&& (!instr_direct(pi, opcode, m_bytecode, instr) || props.isDataflowPassed(target))
+                    if( (tcr=new_generic_vector_constraint(target)) != VF_OK ) {
+                        return tcr;
+                    }
+                }
+
+                if( instr_direct(pi, opcode, m_bytecode, instr) ) {
+                    //goto, goto_w
+                    if( !props.isDataflowPassed(target) ) {
+                        if( target < instr ) next_start_pc = 0;
+
+                        //if we like to flush StackMapTable attribute from this method
+                        if( stackmapattr_calculation && !props.isMultiway(target) ) {
+                            //store workmap to flush it further
+                            assert(!props.getInstrProps(target));
+                            storeWorkmapCopy(target);
+                        }
+
+                        instr = target;
+                        continue;
+                    } else {
+                        return VF_OK;
+                    }
+                }
+
+
+                //TODO: makes sense to move the block into dataflow_instruction??
+                if( instr_is_jsr(opcode) ) {
+                    PropsHead *target_pro = (PropsHead*)props.getInstrProps(target);
+
+                    if( !props.isDataflowPassed(target) ) {
+                        for( unsigned i = 0; i < m_stack_start; i++ ) {
+                            StackmapElement &el = target_pro->stackmap.elements[i];
+                            el.clearJsrModified();
+                        }
+
+                        //create vector for storing ret types coming out of subroutine
+                        PropsHead *retpro = newRetData();
+                        retpro->instr = 0xFFFF;
+                        assert(!target_pro->next || target_pro->next->instr != 0xFFFF );
+                        retpro->next = target_pro->next;
+                        target_pro->next = retpro;
+
+                        SubroutineData *subrdata = retpro->getSubrData(m_stack_start+m_max_stack);
+
+                        if( !props.getInstrProps(instr) && instr) {
+                            //if jsr instruction does not have workmap copy or stackmap, associated with it - create it
+                            assert(workmap->depth);
+                            workmap->depth--; // undo PUSH(SM_RETADDR)
+                            storeWorkmapCopy(instr);
+                        }
+
+                        //need to return to that JSR instr later, when finish subroutine processing
+                        subrdata->caller = instr;
+
+                        //need to postpone some finalizing stuff
+                        stack.xPush(target, MARK_SUBROUTINE_DONE);
+
+                        //process subroutine
+                        stack.xPush(target);
+
+                        return VF_OK;
+                    } else {
+                        SubroutineData *subrdata = ((PropsHead*)target_pro->next)->getSubrData(m_stack_start+m_max_stack);
+
+                        if( !subrdata->subrDataflowed ) {
+                            //recursive call?
+                            return error(VF_ErrorDataFlow, "recursive subroutine");
+                        }
+
+                        restore_workmap_after_jsr(target);
+
+                        if( !subrdata->retCount ) {
+                            //no ret from subroutine -- dead code follows
+                            return VF_OK;
+                        } 
+
+                        instr += instr_len;
+                        continue;
+                    }
+                }
+
+                if( !props.isMultiway(target) ) {
+                    //if* with no stackmap at branch
+                    storeWorkmapCopy(target);
+                    assert( !props.isDataflowPassed(target) );
+                }
+
+                if( !props.isDataflowPassed(target) ) {
+                    stack.xPush(target);
+                }
+
+                instr += instr_len;
+            } else if( instr_direct(pi, opcode, m_bytecode, instr) ) {
+                // it is not a jump ==> it is ret, return or throw
+                return VF_OK;
+            } else if( instr_is_switch(pi) ) {
+
+                Address next_target_adr = (instr & (~3) ) + 4;
+
+                //default target
+                Address target = instr + read_int32(m_bytecode + next_target_adr);
+                processSwitchTarget(target);
+
+                // in tableswitch instruction target offsets are stored with shift = 4,
+                // in lookupswitch with shift = 8
+                int shift = (opcode == OP_TABLESWITCH) ? 4 : 8;
+
+                // process conditional jump target
+                for (next_target_adr += 12;
+                    next_target_adr < instr + instr_len;
+                    next_target_adr += shift)
+                {
+                    target = instr + read_int32(m_bytecode + next_target_adr);
+                    processSwitchTarget(target);
+                }
+
+                return VF_OK;
+            } else {
+                assert( instr_is_regular(pi) );
+                instr += instr_len;
+            }
+
+        }
+
+        // control went out of method bounds
+        return error(VF_ErrorCodeEnd, "control went out of method bounds");
+    }
+
+    vf_Result vf_Context_5::verify_method(method_handler method) {
+        vf_Result tcr;
+
+        //nothing to verify
+        if( !method_get_code_length( method ) ) {
+            return VF_OK;
+        }
+
+        //load memory storage, read variable like max_stack, etc
+        init(method);
+
+        //////////////////////////// FIRST PASS /////////////////////////
+        pass = 1;
+        stack.push(0);
+
+        unsigned short idx;
+        unsigned short start_pc;
+        unsigned short end_pc;
+        unsigned short handler_pc;
+        unsigned short handler_cp_index;
+
+        for( idx = 0; idx < m_handlecount; idx++ ) {
+            method_get_exc_handler_info( m_method, idx, &start_pc, &end_pc,
+                &handler_pc, &handler_cp_index );
+
+            if( start_pc >= end_pc || end_pc > m_code_length ) {
+                return error(VF_ErrorHandler, "start_pc >= end_pc OR end_pc > code_length");
+            }
+            stack.push(handler_pc);
+        }
+
+        //we have different slightly rules for processing dead and live code
+        //e.g. it's not a problem if dead code runs out of the method
+        //but we still have to verify it for corrupted instructions to follow RI
+        dead_code_parsing = 0;
+        do {
+            while( !stack.is_empty() ) {
+                vf_Result tcr = parse(stack.pop());
+                if( tcr != VF_OK ) {
+                    return tcr;
+                }
+            }
+
+            dead_code_parsing = 1;
+
+            while( !dead_code_stack.is_empty() ) {
+                vf_Result tcr = parse(dead_code_stack.pop());
+                if( tcr != VF_OK ) {
+                    return tcr;
+                }
+            }
+        } while (!stack.is_empty());
+
+
+
+        for( idx = 0; idx < m_handlecount; idx++ ) {
+
+            method_get_exc_handler_info( m_method, idx, &start_pc, &end_pc,
+                &handler_pc, &handler_cp_index );
+
+            if( end_pc < m_code_length && props.isOperand(end_pc) || props.isOperand(start_pc) ) {
+                return error(VF_ErrorCodeEnd, "start_pc or end_pc are at the middle of an instruction");
+            }
+
+            SmConstant handler_type;
+            if( handler_cp_index ) {
+                if( !tpool.cpool_get_class(handler_cp_index, &handler_type) ||
+                    !tpool.mustbe_assignable(handler_type, tpool.sm_get_const_throwable()) )
+                {
+                    return error(VF_ErrorHandler, "incorrect constantpool entry");
+                }
+            } else {
+                handler_type = tpool.sm_get_const_throwable();
+            }
+
+            props.setMultiway(handler_pc);
+            createHandlerStackmap(handler_pc, handler_type);
+        }
+
+        //////////////////////////// SECOND PASS /////////////////////////
+        pass = 2;
+
+        stack.xPush(0);
+        while( !stack.is_empty() ) {
+            Address next;
+            short mark;
+
+            stack.xPop(&next, &mark);
+
+            if( !mark ) {
+                tcr = StartLinearDataflow(next);
+            } else {
+                assert(mark == MARK_SUBROUTINE_DONE);
+                tcr = SubroutineDone(next);
+            }
+
+            if( tcr != VF_OK ) {
+                return tcr;
+            }
+        }
+
+        return VF_OK;
+    }
+
+
+
+
+    vf_Result vf_Context_5::new_ret_vector_constraint(Address jsr_target) {
+        PropsHead *inpro = (PropsHead*)props.getInstrProps(jsr_target);
+        PropsHead *outpro = (PropsHead*)inpro->next;
+        assert(outpro->instr == 0xFFFF);
+
+        SubroutineData *subrdata = outpro->getSubrData(m_stack_start + m_max_stack);
+        subrdata->retCount++;
+
+        //if it is a first ret from the given subroutine (majority of the cases)
+        if( subrdata->retCount == 1 ) {
+            //remove newly appeared ret addresses: it might happen
+            //if non-top subroutine made a ret
+            StackmapHead* original = inpro->getStackmap();
+            unsigned i;
+
+            for( i = 0; i < m_stack_start + workmap->depth; i++ ) {
+                if( i < m_stack_start && !workmap->elements[i].isJsrModified() ) {
+                    //nothing new here
+                    continue;
+                }
+
+                SmConstant val = workmap->elements[i].getAnyPossibleValue();
+                if( val.isRetAddr() ) {
+                    //check if it's a newly appeared ret addfress
+
+                    // '-1' is twice below to exclude top of the stack. 
+                    // top of the stack contains ret address for the current subroutine
+                    // it also cleaned up if it's still there
+
+                    if( i < m_stack_start + original->depth - 1 && 
+                        original->elements[i].getAnyIncomingValue() == val ) 
+                    {
+                        //most likely: this ret address was there before
+                        continue;
+                    }
+
+                    //iterate thru original types and look for this ret address
+                    int found_in_original = 0;
+                    for( unsigned j = 0; j < m_stack_start + original->depth - 1; j++ ) {
+                        if( original->elements[j].getAnyIncomingValue() == val ) {
+                            found_in_original = 1;
+                            break;
+                        }
+                    }
+                    if( !found_in_original ) {
+                        //original types did not have this ret address
+                        workmap->elements[i] = _WorkmapElement(SM_BOGUS);
+                    }
+                }
+            }
+
+            //TODO make sure incoming was created as JSR transformation
+            tc_memcpy(outpro->getWorkmap(), workmap, sizeof(WorkmapHead) + sizeof(WorkmapElement) * (m_stack_start + workmap->depth));
+            return VF_OK;
+        }
+
+        return error(VF_ErrorStackDepth, "Multiple returns to single jsr");
+    }
+
+
+    void vf_Context_5::restore_workmap_after_jsr(Address jsr_target) {
+        PropsHead *inpro = (PropsHead*)props.getInstrProps(jsr_target);
+        PropsHead *outpro = (PropsHead*)inpro->next;
+        SubroutineData *subrdata = outpro->getSubrData(m_stack_start + m_max_stack);
+
+        if( subrdata->retCount ) {
+            assert( subrdata->retCount == 1 );
+            WorkmapHead* outcoming = outpro->getWorkmap();
+            workmap->depth = outcoming->depth;
+
+            unsigned i;
+            for( i = 0; i < m_stack_start; i++ ) {
+                if( outcoming->elements[i].isJsrModified() ) {
+                    workmap->elements[i] = outcoming->elements[i];
+                }
+            }
+            for( ; i < m_stack_start + workmap->depth; i++ ) {
+                workmap->elements[i] = outcoming->elements[i];
+            }    
+        }
+    }
+
+    vf_Result vf_Context_5::new_scalar_constraint(WorkmapElement *from, StackmapElement *to) {
+        assert(from->getAnyPossibleValue() != SM_NONE);
+
+        if( from->isJsrModified() ) {
+            //JSR overhead
+            to->setJsrModified();
+        }
+
+        if( !from->isVariable() ) {
+            SmConstant inc_val = from->getConst();
+            return add_incoming_value( inc_val, to );
+        } else {
+            GenericCnstr* gen = from->getVariable()->firstGenericCnstr();
+            while( gen ) {
+                if( gen->variable == to ) return VF_OK;
+                gen = gen->next();
+            }
+
+            IncomingType *inc = from->getVariable()->firstIncoming();
+            from->getVariable()->newGenericConstraint(&mem, to);
+
+            while( inc ) {
+                vf_Result vcr = add_incoming_value( inc->value, to );
+                if( vcr != VF_OK ) {
+                    return vcr;
+                }
+                inc = inc->next();
+            }
+            return VF_OK;
+        }
+    }
+
+    vf_Result vf_Context_5::add_incoming_value(SmConstant new_value, StackmapElement *destination) {
+        //check if the node already has such incoming value
+        IncomingType *inc = destination->firstIncoming();
+        while( inc ) {
+            if( new_value == inc->value  || inc->value == SM_BOGUS ) {
+                return VF_OK;
+            }
+            inc = inc->next();
+        }
+
+        if( new_value.isNonMergeable() && destination->firstIncoming() ) {
+            //uninit value merged to any different value is bogus
+            //ret address merged to any different value is bogus
+            //assert - incoming value exists is different - we've already checked that new_value is missing in the list of incoming values
+            new_value = SM_BOGUS;
+        }
+
+        //add incoming value if it does not have
+        Constraint* next = destination->firstOthers();
+        //TODO: optimize memory footprint for new_value == SM_BOGUS
+        destination->newIncomingType(&mem, new_value);
+
+        //check if it contradicts to expected types and further propagate
+        while( next ) {
+            switch (next->type) {
+            case CT_EXPECTED_TYPE:
+                if( !tpool.mustbe_assignable(new_value, next->value) ) return error(VF_ErrorUnknown, "unexpected type on stack or local variable");
+                break;
+            case CT_GENERIC: {
+                vf_Result vcr = add_incoming_value(new_value, next->variable);
+                if( vcr != VF_OK ) return vcr;
+                break;
+                             }
+            case CT_ARRAY2REF: {
+                vf_Result vcr = add_incoming_value( tpool.get_ref_from_array(new_value), next->variable);
+                if( vcr != VF_OK ) return vcr;
+                break;
+                               }
+            default:
+                assert(0);
+                return error(VF_ErrorInternal, "unreachable statement in add_incoming_value");
+            }
+            next = next->next();
+        }
+        return VF_OK;
+    }
+
+} // namespace CPVerifier

Propchange: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/context_5.cpp
------------------------------------------------------------------------------
    svn:executable = *

Added: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/context_5.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/context_5.h?rev=584118&view=auto
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/context_5.h (added)
+++ harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/context_5.h Fri Oct 12 03:32:50 2007
@@ -0,0 +1,327 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+/** 
+ * @author Mikhail Loenko, Vladimir Molotkov
+ */  
+
+#ifndef __CONTEXT5_H__
+#define __CONTEXT5_H__
+
+#include <assert.h>
+#include <string.h>
+#include "../base/context_x.h"
+#include "stackmap_5.h"
+#include "instr_props_5.h"
+
+using namespace CPVerifier;
+
+
+namespace CPVerifier_5 {
+
+    //
+    // Context - main class of Type Checker
+    //
+
+    class vf_Context_5 : public vf_Context_x<vf_Context_5, WorkmapElement, _WorkmapElement, StackmapElement> {
+    public:
+        vf_Context_5(SharedClasswideData &classwide) :
+          vf_Context_x<vf_Context_5, WorkmapElement, _WorkmapElement, StackmapElement>(classwide) {}
+
+          vf_Result verify_method(method_handler method);
+    protected:
+        // various flags for all the method's bytecode instructions
+        InstrProps props;
+
+        // stack to push instructions like branch targets, etc to go thru the method. the stack is method-wide.
+        MarkableStack stack;
+
+        FastStack dead_code_stack;
+        bool      dead_code_parsing;
+
+        //we would like to flush StackMapTable attribute from this method
+        bool      stackmapattr_calculation;
+
+        static const short MARK_SUBROUTINE_DONE = -1;
+
+        //init method-wide data
+        void init(method_handler _m_method, bool _stackmapattr_calculation = 0) {
+            vf_Context_x<vf_Context_5, WorkmapElement, _WorkmapElement, StackmapElement>::init(_m_method);
+            stack.init();
+            dead_code_stack.init();
+
+            props.init(mem, m_code_length);
+
+            //we would like to flush StackMapTable attribute from this method
+            stackmapattr_calculation = _stackmapattr_calculation;
+        }
+
+        // load derived types previously stored for the given instruction
+        void fill_workmap(Address instr) {
+            PropsHead *head = (PropsHead*)props.getInstrProps(instr);
+            if( head->is_workmap() ) {
+                tc_memcpy(workmap, head->getWorkmap(), sizeof(WorkmapHead) + sizeof(WorkmapElement) * (m_stack_start + head->workmap.depth));
+            } else {
+                StackmapHead *stackmap = head->getStackmap();
+
+                workmap->depth = stackmap->depth;
+
+                for( unsigned i = 0; i < m_stack_start + stackmap->depth; i++) {
+                    workmap->elements[i] = _WorkmapElement(&stackmap->elements[i]);
+                    assert( workmap->elements[i].getAnyPossibleValue() != SM_NONE );
+                }
+            }
+            no_locals_info = 1;
+        }
+
+        //store a copy of the current workmap for another instruction (such as a branch target)
+        void storeWorkmapCopy(Address target) {
+            int sz = m_stack_start + workmap->depth;
+            PropsHead* copy = newWorkmapProps(sz);
+            tc_memcpy(copy->getWorkmap(), workmap, sizeof(WorkmapHead) + sizeof(WorkmapElement) * sz);
+
+            props.setInstrProps(target, copy);
+        }
+
+        //create a stackmap vector of the given size sz (max_locals <= sz <= max_locals+max_stack)
+        PropsHead* newStackmap(int sz) {
+            return (PropsHead*)mem.calloc(sizeof(PropsHead) + sizeof(StackmapElement) * sz);
+        }
+
+        //create a vector that will be used for JSR procesing. 
+        //It contains ether stackmap or workmap vector, SubrouitineData, and flags vector indicating 
+        //changed locals
+        PropsHead *newRetData() {
+            assert( sizeof(StackmapElement) >= sizeof(WorkmapElement) );
+
+            int sz = sizeof(PropsHead) + sizeof(StackmapElement) * (m_max_stack + m_stack_start) + //stackmap
+                ((sizeof(SubroutineData)+ m_stack_start) & (~3)) + 4; // fixed data and changed locals vector
+
+            PropsHead * ret = (PropsHead *) mem.calloc(sz);
+            ret->set_as_workmap();
+            return ret;
+        }
+
+        //creates a temporary variable for converting 
+        StackmapElement *new_variable() {
+            return (StackmapElement*) mem.calloc(sizeof(StackmapElement));
+        }
+
+        /////////////////////////////////////////////////////////////////////////////////////////////////////
+
+        //First verification pass thru the method. checks that no jump outside the method or to the middle of instruction
+        //checks that opcodes are valid
+        vf_Result parse(Address instr);
+
+        //Second pass: dataflow of a piece of the method starting from the beginning or a branch target and finishing
+        //on return, athrow or hitting previously passed instruction. 
+        //This function initializes workmap and calls DataflowLoop
+        vf_Result StartLinearDataflow(Address start);
+
+        //Second pass: Finilize subroutie processing -- once we are here, then all the RETs from achievable for
+        //the given subroutine are passed, so we can resume passing for JSRs to the given address
+        //This function initializes workmap properly and calls DataflowLoop
+        vf_Result SubroutineDone(Address start);
+
+        //Second pass: dataflow of a piece of the method starting from the beginning or a branch target and finishing
+        //on return, athrow or hitting previously passed instruction
+        vf_Result DataflowLoop(Address start, int workmap_is_a_copy_of_stackmap);
+
+        //constraint propagation
+        vf_Result propagate(StackmapElement *changed, SmConstant new_value);
+
+        //update current derived types according to what was changed in subroutine
+        void restore_workmap_after_jsr(Address jsr_target);
+
+        //create vector constraints for each target of a switch
+        vf_Result processSwitchTarget(Address target) {
+            vf_Result tcr;
+            if( props.isMultiway(target) ) {
+                if( (tcr=new_generic_vector_constraint(target)) != VF_OK ) {
+                    return tcr;
+                }
+
+                if( !props.isDataflowPassed(target) ) {
+                    stack.xPush(target);
+                }
+            } else {
+                assert( !props.isDataflowPassed(target) );
+                storeWorkmapCopy(target);
+
+                stack.xPush(target);
+            }
+            return VF_OK;
+        }
+
+
+        ///////////////////////////////////  "VIRTUAL" METHODS /////////////////////////////////////////////
+    public:
+        //create constraint vector in case of a branch 
+        //simple conatraints are created for pairs of both locals and stack (current must be assignable to target)
+        vf_Result new_generic_vector_constraint(Address target_instr) {
+            return new_generic_vector_constraint_impl(getStackmap(target_instr, workmap->depth));
+        }
+
+        //when we hit RET instruction we update the data for the given subroutine with current derived types
+        vf_Result new_ret_vector_constraint(Address target_instr);
+
+        // push catch-block to the stack of branches to pass
+        void push_handler(Address handler_pc) {
+            if( !props.isDataflowPassed(handler_pc) ) {
+                stack.xPush(handler_pc);
+            }
+        }
+
+        //create simple single constraint: "'from' is assingable to 'to'"
+        vf_Result new_scalar_constraint(WorkmapElement *from, StackmapElement *to);
+
+        //add one more possible value (type) that can come to the given point (local or stack)
+        vf_Result add_incoming_value(SmConstant new_value, StackmapElement *destination);
+
+        //create stackmap for exception handler start
+        void createHandlerStackmap(Address handler_pc, SmConstant type) {
+            StackmapHead *map = getStackmap(handler_pc, 1);
+            //handler stackmaps are created before any dataflow analysis is done
+            assert(map->depth == 0 || map->depth == 1);
+            map->depth = 1;
+
+            vf_Result tcr = add_incoming_value(type, &map->elements[m_stack_start]);
+
+            // it is initialization stage
+            assert(tcr == VF_OK);
+        }
+
+
+        //create a workmap vector for the given size sz (max_locals <= sz <= max_locals+max_stack)
+        PropsHead *newWorkmapProps(int sz) {
+            PropsHead * ret = (PropsHead*)mem.malloc(sizeof(PropsHead) + sizeof(WorkmapElement) * sz);
+            ret->set_as_workmap();
+            return ret;
+        }
+
+        //returns stackmap for the 'instr' instruction
+        //if it does not exists yet -- create it. When created use 'depth' as stack depth
+        StackmapHead *getStackmap(Address instr, int depth) {
+            PropsHead *pro = (PropsHead*) props.getInstrProps(instr);
+            if( !pro ) {
+                pro = newStackmap(m_stack_start + depth);
+                props.setInstrProps(instr, pro);
+                pro->getStackmap()->depth = depth;
+            }
+            return pro->getStackmap();
+        }
+
+        //returns stackmap for the 'instr' instruction. it must exist
+        StackmapHead *getStackmap(Address instr) {
+            PropsHead *pro = (PropsHead*)props.getInstrProps(instr);
+            assert(pro);
+            return pro->getStackmap();
+        }
+
+        /////////////// expect some type //////////////
+
+        //expect exactly this type
+        int workmap_expect_strict( WorkmapElement &el, SmConstant type ) {
+            assert(type != SM_BOGUS);
+
+            if( !el.isVariable() ) {
+                return type == el.getConst();
+            }
+
+            IncomingType *in = el.getVariable()->firstIncoming();
+            while( in ) {
+                if( type != in->value ) {
+                    return false;
+                }
+                in = in->next();
+            }
+
+            ExpectedType *exp = el.getVariable()->firstExpected();
+            while( exp ) {
+                if( type == exp->value ) {
+                    return true;
+                }
+                exp = exp->next();
+            }
+
+            el.getVariable()->newExpectedType(&mem, type);
+
+            return true;
+        }
+
+        int workmap_expect( WorkmapElement &el, SmConstant type ) {
+            if( !el.isVariable() ) {
+                return tpool.mustbe_assignable(el.getConst(), type);
+            } else {
+                ExpectedType* exp = el.getVariable()->firstExpected();
+                while( exp ) {
+                    if( type == exp->value ) {
+                        return true;
+                    }
+                    exp = exp->next();
+                }
+
+                IncomingType *in = el.getVariable()->firstIncoming();
+                //check that all existing incoming type are assignable to the new expected type
+                while( in ) {
+                    if( !tpool.mustbe_assignable(in->value, type) ) {
+                        return false;
+                    }
+                    in = in->next();
+                }
+                //add the new expected type
+                el.getVariable()->newExpectedType(&mem, type);
+            }
+            return true;
+        }
+
+        //create special type of conatraint: "'from' is an array and it's element is assignable to 'to'"
+        vf_Result new_scalar_array2ref_constraint(WorkmapElement *from, WorkmapElement *to) {
+            if( !from->isVariable() ) {
+                //although new_scalar_conatraint() whould process from constants correctly 
+                // we just do not need new variable if it is really a constant
+                *to = _WorkmapElement( tpool.get_ref_from_array(from->getConst()) );
+                return VF_OK;
+            }
+            assert( from->isVariable() );
+
+            ArrayCnstr* arr = from->getVariable()->firstArrayCnstr();
+            //at most one array conversion constraint per variable is possible
+            if( arr ) {
+                *to = _WorkmapElement(arr->variable);
+                return VF_OK;
+            }
+
+            *to = _WorkmapElement( new_variable() );
+
+            IncomingType *inc = from->getVariable()->firstIncoming();
+            from->getVariable()->newArrayConversionConstraint(&mem, to->getVariable());
+
+            while( inc ) {
+                SmConstant inc_val = tpool.get_ref_from_array(inc->value);
+                vf_Result vcr = add_incoming_value( inc_val, to->getVariable() );
+                if( vcr != VF_OK ) {
+                    return vcr;
+                }
+                inc = inc->next();
+            }
+            return VF_OK;
+        }
+    };
+
+} // namespace CPVerifier
+
+#endif

Propchange: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/context_5.h
------------------------------------------------------------------------------
    svn:executable = *

Added: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/instr_props_5.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/instr_props_5.h?rev=584118&view=auto
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/instr_props_5.h (added)
+++ harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/instr_props_5.h Fri Oct 12 03:32:50 2007
@@ -0,0 +1,129 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+/** 
+ * @author Mikhail Loenko, Vladimir Molotkov
+ */  
+
+#ifndef __INSTR_PROPS5_H_
+#define __INSTR_PROPS5_H_
+
+#include <assert.h>
+#include "../base/stackmap.h"
+
+using namespace CPVerifier;
+
+namespace CPVerifier_5 {
+
+    //store flags and properties (stackmaps, workmaps, etc) for each instruction
+    class InstrProps : public InstrPropsBase {
+    private:
+        //array of bit flags
+        uint8* packed_flags;
+
+        //returns flags for the instruction 'instr'. other bits are not necessary 0s
+        int get_dirty_mask(Address instr) {
+            int b = packed_flags[instr/4];
+            b = b >> ((instr % 4) * 2);
+            return b;
+        }
+
+        //bit OR flags for the instruction 'instr' with 'mask'
+        void fill_mask(Address instr, int mask) {
+            assert((mask & ~3) == 0);
+            mask = mask << ((instr % 4) * 2);
+
+            packed_flags[instr/4] |= mask;
+        }
+
+        //clears bits the are set in the 'mask' (& ~mask) for the instruction 'instr'
+        void clear_mask(Address instr, int mask) {
+            assert((mask & ~3) == 0);
+            mask = mask << (instr % 4) * 2;
+
+            packed_flags[instr/4] &= ~mask;
+        }
+
+    public:
+        //initializes the class. this function is invoked once per method - removes old data in initializes storages.
+        void init(Memory &mem, int code_len) {
+            InstrPropsBase::init(mem, code_len);
+            packed_flags = (uint8*)mem.calloc( ((code_len/4) & ~3) + 4);
+        }
+
+        //pass1: 00 - new (or dead code), 01 - parsed, 10 - middle of instruction, 11 - 'special' parsed (special == has stackmap)
+        //returns 1 if mask is 01 (parsed) or 11 ('special' parsed  special == has stackmap)
+        int isParsePassed(Address instr) {
+            return get_dirty_mask(instr) & 1;
+        }
+
+        //pass1: 00 - new (or dead code), 01 - parsed, 10 - middle of instruction, 11 - 'special' parsed (special == has stackmap)
+        //returns 1 if mask is 10 (middle of instruction)
+        int isOperand(Address instr) {
+            return (get_dirty_mask(instr) & 3) == 2;
+        }
+
+        //pass1: 00 - new (or dead code), 01 - parsed, 10 - middle of instruction, 11 - 'special' parsed (special == has stackmap)
+        //setls low mask bit to 1
+        void setParsePassed(Address instr) {
+            fill_mask(instr, 1);
+        }
+
+        //pass1: 00 - new (or dead code), 01 - parsed, 10 - middle of instruction, 11 - 'special' parsed (special == has stackmap)
+        //sets mask to 10
+        int setOperand(Address instr) {
+            int idx = instr/4;
+            int shift = ((instr % 4) * 2);
+
+            int mask01 = 1 << shift;
+            int mask10 = 2 << shift;
+
+            //is an instruction
+            if( packed_flags[idx] & mask01 ) return 0;
+
+            //mark as a middle
+            packed_flags[idx] |= mask10;
+            return 1;
+        }
+
+        //pass1: 00 - new (or dead code), 01 - parsed, 10 - middle of instruction, 11 - 'special' parsed (special == has stackmap)
+        //set mask to 11
+        void setMultiway(Address instr) {
+            fill_mask(instr, 3);
+        }
+
+        //pass2: 01 - new, 11 - special, 00 - passed (or unused), 10 - special passed (or unused)
+        //for all instructions (except unuzed) returns 1 if it's 'passed' or 'special passed'
+        //return 0 otherwise
+        int isDataflowPassed(Address instr) {
+            return !(get_dirty_mask(instr) & 1);
+        }
+
+        //return 1 for special and special passed instructions (instructions that are achievable by multiple passes)
+        int isMultiway(Address instr) { //II_MULTIWAY
+            return get_dirty_mask(instr) & 2;
+        }
+
+        //mark instruction as passed
+        void setDataflowPassed(Address instr) {
+            clear_mask(instr, 1);
+        }
+
+    };
+} // namespace CPVerifier
+
+
+#endif

Propchange: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/instr_props_5.h
------------------------------------------------------------------------------
    svn:executable = *

Copied: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/stackmap_5.h (from r584094, harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/stackmap.h)
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/stackmap_5.h?p2=harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/stackmap_5.h&p1=harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/stackmap.h&r1=584094&r2=584118&rev=584118&view=diff
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/stackmap.h (original)
+++ harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier-3363/java5/stackmap_5.h Fri Oct 12 03:32:50 2007
@@ -17,520 +17,356 @@
 /** 
  * @author Mikhail Loenko, Vladimir Molotkov
  */  
-
-#ifndef __STACKMAP_H__
-#define __STACKMAP_H__
-
-#include <stdlib.h>
-#include <string.h>
-#include <assert.h>
-#include "ver_utils.h"
-
-#ifdef WIN32
-#define intptr int64
-#else
-#define intptr long
-#endif
-
-namespace CPVerifier {
-
-    //predefined verification types
-    enum SmConstPredefined {
-        SM_TOP                          = 0,
-        SM_ONEWORDED                    = 1,
-        SM_REF_OR_UNINIT_OR_RETADR      = 3,
-        SM_REF_OR_UNINIT                = 5,
-        SM_THISUNINIT                   = 7,
-        SM_ANYARRAY                     = 9,
-        SM_NULL                         = 11,
-        SM_HIGH_WORD                    = 13,
-        SM_INTEGER                      = 15,
-        SM_FLOAT                        = 17,
-        SM_BOGUS                        = 19,
-        SM_LONG                         = 21,
-        SM_DOUBLE                       = 23,
-    };
-
-    //verification types with comparision operators
-    struct _SmConstant {
-        unsigned c;
-
-        int operator ==(_SmConstant other) {
-            return c == other.c;
-        }
-
-        int operator ==(unsigned other) {
-            return c == other;
-        }
-
-        int operator !=(_SmConstant other) {
-            return c != other.c;
-        }
-
-        int operator !=(unsigned other) {
-            return c != other;
-        }
-
-
-    };
-
-    //verification types with convinient functions
-    struct SmConstant : _SmConstant {
-        //all constants except SM_TOP must be odd
-
-        //default constructor
-        SmConstant() {}
-
-        //creating from unsigned
-        SmConstant(unsigned int other) {
-            c = other;
-        }
-
-        //copy constructor
-        SmConstant(const _SmConstant other) {
-            c = other.c;
-        }
-
-        ///////////////////////////////////////
-
-        //is it a RETADDR verification type? (that's pushed by JSR instructions)
-        int isRetAddr() {
-            return c & TYPE_RETADDR;
-        }
-
-        //is it a reference? (like Object)
-        int isReference() {
-            return c & TYPE_REFERENCE;
-        }
-
-        //is it a new object? (e.g. just created by 'new' instruction)
-        int isNewObject() {
-            return c & TYPE_NEWOBJECT;
-        }
-
-        //is it a primitive verification type? (e.g. int, long)
-        int isPrimitive() {
-            return !(c & (TYPE_NEWOBJECT | TYPE_REFERENCE | TYPE_RETADDR));
-        }
-
-        //is it a two-word type?
-        int isLongOrDouble() {
-            return c == SM_LONG || c == SM_DOUBLE;
-        }
-
-        //does merge with any other type results in SM_BOGUS?
-        int isNonMergeable() {
-            return (c & (TYPE_NEWOBJECT|TYPE_RETADDR)) || c == SM_THISUNINIT;
-        }
-
-        ///////////////////////////////////////
-
-        //for a reference: return class id in the table (see tpool)
-        int getReferenceIdx() {
-            assert(isReference());
-            return (c & ~TYPE_REFERENCE) >> 1;
-        }
-
-        //for 'new' type: return address of the 'new' instruction created this SmConstant
-        Address getNewInstr() {
-            assert(isNewObject());
-            return (c & ~TYPE_NEWOBJECT) >> 1;
-        }
-
-        //for RetAddress: return address of the subroutine start (i.e. target of JSR instruction)
-        //Note: this is different from what is recorded in RetAddress type when actual execution happens
-        Address getRetInstr() {
-            assert(isRetAddr());
-            return (c & ~TYPE_RETADDR) >> 1;
-        }
-
-        ///////////////////////////////////////
-
-        //create "new object" verification type corresponding to 'instr'
-        static SmConstant getNewObject(Address instr) {
-            return ((instr<<1) | (TYPE_NEWOBJECT | 1));
-        }
-
-        //create "ret address" verification type corresponding to subroutine startig at 'instr'
-        //Note: this is different from what is recorded in RetAddress type when actual execution happens
-        static SmConstant getRetAddr(Address instr) {
-            return ((instr<<1) | (TYPE_RETADDR | 1));
-        }
-
-        //create "object" verification type
-        static SmConstant getReference(unsigned idx) {
-            return ((idx<<1) | (TYPE_REFERENCE | 1));
-        }
-
-        ////////////////////////////////////////
-
-        static const unsigned TYPE_RETADDR   = 0x2000000;
-        static const unsigned TYPE_REFERENCE = 0x4000000;
-        static const unsigned TYPE_NEWOBJECT = 0x8000000;
-
-    };
-
-    //possible relations between verificaton types
-    enum ConstraintType {
-        CT_GENERIC,         // sub-defined type A is assignable to sub-defined type B
-        CT_ARRAY2REF,       // A is a known-type array. element of A is assignable to sub-defined type B
-        CT_EXPECTED_TYPE,   // sub-defined type A is assignable to known-type B
-        CT_INCOMING_VALUE   // known-type A is assignable to sub-defined type B
-    };
-
-    struct StackmapHead;
-    struct WorkmapHead;
-    struct StackmapElement;
-
-    //structure for maintaining subroutine-specific data
-    //until subroutine is passed with the second (dataflow) pass we record to the wait list all JSR instructions
-    //calling this subroutine. Once the subroutine is over we continue 2nd pass for each wait-listed instruction
-    //see vf_Context_t::SubroutineDone
-    struct SubroutineData {
-        Address caller;         //first JSR instruction that called this subroutine
-        short retCount;         //number of ret instructions for this subroutine
-        byte  subrDataflowed;   // =1 if dataflow pass for the subroutine is over
-    };
-
-    //list constant verification type (i.e. known-type) that are assignable to some sub-definite type (i.e. StackMapElement)
-    //see StackmapElement
-    struct IncomingType {
-        //next in the list
-        IncomingType *nxt;
-
-        //value of the verification type recorded as int
-        //TODO: don't remember why it's 'int' rather than 'SmConstant'
-        int value;
-
-        //simple next in the list
-        IncomingType *next() {
-            return nxt;
-        }
-    };
-
-    //list of constraints for some sub-definite verification type (i.e. StackMapElement)
-    //see StackmapElement
-
-    struct Constraint {
-        //next in the list
-        Constraint *nxt;
-
-        //either
-        union {
-            StackmapElement *variable; // sub-definite verificarion type
-            int value;                 // or constant (known) verification type rcorded as int
-        };
-
-        //consatrint type
-        ConstraintType type;
-
-        //next constrait of type 't'
-        static Constraint *next(Constraint *cur, ConstraintType t) {
-            while( cur && cur->type != t ) {
-                cur = (Constraint*)cur->next();
-            }
-            return cur;
-        }
-
-        //simple next in the list
-        Constraint *next() {
-            return nxt;
-        }
-    };
-
-    //constraint of the CT_EXPECTED_TYPE type: sub-defined type A is assignable to known-type B
-    struct ExpectedType : Constraint {
-        ExpectedType *next() {
-            return (ExpectedType *) Constraint::next(Constraint::next(), CT_EXPECTED_TYPE);
-        }
-    };
-
-    //constraint of the CT_GENERIC type: sub-defined type A is assignable to sub-defined type B
-    struct GenericCnstr : Constraint {
-        GenericCnstr *next() {
-            return (GenericCnstr *) Constraint::next(Constraint::next(), CT_GENERIC);
-        }
-    };
-
-    //constraint of the CT_ARRAY2REF type: A is a known-type array. element of A is assignable to sub-defined type B
-    struct ArrayCnstr : Constraint {
-        //there can be only one CT_ARRAY2REF per StackMap Element
-        ArrayCnstr *next() {
-            assert(0);
-            return 0;
-        }
-    };
-
-
-    //StackMapElement structure represens sub-definite verification type: we don't know what type is it, but
-    //we know about instructions that expect ExpectedTypes here and we know that IncomingValues can be here
-    //we also know that this type must be assignable to other sub-defenite types as indicated by CT_GENERIC
-    //constrains and there can be special limitations represented by CT_ARRAY2REF constraints
-    struct StackmapElement { //TODO: should be rewritten to save footprint
-        //list of IncomingType constraint
-        IncomingType *incoming;
-
-        //list of all the conatraints of other types
-        Constraint *others;
-
-        //return value from any IncomingType constraint
-        //when we need to compae to some unmergable type we don;t need to interate thru the list
-        //also used to assert that an IncomingValue constraint exists
-        SmConstant getAnyIncomingValue() {
-            assert(firstIncoming());
-            return firstIncoming()->value;
-        }
-
-        //return first IncomingType constraint
-        IncomingType *firstIncoming() {
-            //TODO: I have to store somewhere the "modified" bit. Sorry.
-            return (IncomingType*)( (intptr)incoming & ~3 );
-        }
-
-        //return first conatrint of any type except IncomingType
-        Constraint *firstOthers() {
-            return others;
-        }
-
-        //return first CT_EXPECTED_TYPE constraint
-        ExpectedType *firstExpected() {
-            return (ExpectedType*)Constraint::next(others, CT_EXPECTED_TYPE);
-        }
-
-        //return first CT_GENERIC constraint
-        GenericCnstr *firstGenericCnstr() {
-            return (GenericCnstr*)Constraint::next(others, CT_GENERIC);
-        }
-
-        //return first (and the only) CT_ARRAY2REF constraint
-        ArrayCnstr *firstArrayCnstr() {
-            return (ArrayCnstr*)Constraint::next(others, CT_ARRAY2REF);
-        }
-
-        //clean-up
-        void init() {
-            incoming = 0;
-            others = 0;
-        }
-
-        //add incoming type with the 'value' value
-        void newIncomingType(Memory *mem, SmConstant value) {
-            IncomingType *in = (IncomingType *)mem->malloc(sizeof(IncomingType));
-
-            intptr mask = (intptr)incoming & 3;
-            incoming = (IncomingType *) ((intptr)incoming & ~3);
-
-            in->nxt = value == SM_BOGUS ? 0 : incoming;
-            //in->type = CT_INCOMING_VALUE;
-            in->value = value.c;
-
-            incoming = in;
-
-            incoming = (IncomingType *) ((intptr)incoming | mask);
-        }
-
-        //add expected type with the 'value' value
-        void newExpectedType(Memory *mem, SmConstant value) {
-            Constraint *o = (Constraint *)mem->malloc(sizeof(Constraint));
-
-            o->nxt = others;
-            o->type = CT_EXPECTED_TYPE;
-            o->value = value.c;
-
-            others = o;
-        }
-
-        //add generic constraint ('this' is assignable to 'to')
-        void newGenericConstraint(Memory *mem, StackmapElement *to) {
-            Constraint *o = (Constraint *)mem->malloc(sizeof(Constraint));
-
-            o->nxt = others;
-            o->type = CT_GENERIC;
-            o->variable = to;
-
-            others = o;
-        }
-
-        //add generic constraint ('this' is an array, which element is assignable to 'to')
-        void newArrayConversionConstraint(Memory *mem, StackmapElement *to) {
-            assert(!firstArrayCnstr());
-            Constraint *o = (Constraint *)mem->malloc(sizeof(Constraint));
-
-            //at most one array conversion constraint per variable is possible
-            o->nxt = others;
-            o->type = CT_ARRAY2REF;
-            o->variable = to;
-
-            others = o;
-        }
-
-        // return 'modified' flag for the stackmap. the flag is stored in the first bit of the 'incoming' pointer
-        // "modified" is about subroutines: you have to track which locals were changed
-        int isJsrModified() {
-            return (int)(intptr)incoming & 1;
-        }
-
-        //set 'modified' flag for the stackmap. the flag is stored in the first bit of the 'incoming' pointer
-        // "modified" is about subroutines: you have to track which locals were changed
-        void setJsrModified() {
-            incoming = (IncomingType *) ((intptr)incoming | 1);
-        }
-
-        //clear 'modified' flag for the stackmap. the flag is stored in the first bit of the 'incoming' pointer
-        // "modified" is about subroutines: you have to track which locals were changed
-        void clearJsrModified() {
-            incoming = (IncomingType *) ((intptr)incoming & ~1);
-        }
-    };
-
-    //WorkMapElement structure represent an element of the workmap vector -- vector of the derived types
-    //a type might be either constant (or known) (e.g. if some previous instruction has put something on stack or locals)
-    //or sub-definite (e.g. if we've recently passed a branch target and don't know which types were on stack or locals)
-    struct WorkmapElement {
-        //value. two low bits a used to store flags
-        union {
-            _SmConstant const_val;      //either a constant (known-type)
-            StackmapElement *var_ptr;   //or a variable (sub-definite type)
-        };
-
-        //is it a sub-definite (not constant) type?
-        int isVariable() {
-            assert(const_val != SM_TOP);
-            return !((intptr)var_ptr & 1);
-        }
-
-        //get value for the constant (known) verification type
-        SmConstant getConst() {
-            return const_val;
-        }
-
-        //get variable representing sub-definite verification type
-        StackmapElement *getVariable() {
-            return (StackmapElement *) ((intptr)var_ptr & ~3);
-        }
-
-        //when we need to compae to some unmergable type we don;t need to interate thru the list
-        //also used to assert that an IncomingValue constraint exists
-        SmConstant getAnyPossibleValue() {
-            SmConstant ret = isVariable() ? getVariable()->getAnyIncomingValue() : const_val;
-            assert(ret != SM_TOP);
-            return ret;
-        }
-
-        // return 'modified' flag for the workmap element. the flag is stored in the second bit of the union
-        //"modified" is about subroutines: you have to track which locals were changed
-        //it's easier to think of all the constants as "modified"
-        int isJsrModified() {
-            return (int)(intptr)var_ptr & 3;
-        }
-
-        // set 'modified' flag for the workmap element. the flag is stored in the second bit of the union
-        void setJsrModified() {
-            if( isVariable() ) {
-                var_ptr = (StackmapElement*)((intptr)var_ptr | 2);
-            }
-        }
-    };
-
-    //WorkmapElement type with some constructors
-    struct _WorkmapElement : WorkmapElement{
-        _WorkmapElement(WorkmapElement other) {
-            const_val = other.const_val;
-        }
-
-        _WorkmapElement(StackmapElement *s) {
-            var_ptr = s;
-            if( s->isJsrModified() ) {
-                setJsrModified();
-            }
-        }
-
-        _WorkmapElement(SmConstant c) {
-            const_val = c;
-        }
-    };
-
-#pragma warning( push )
-#pragma warning( disable : 4200 )
-
-    //vector of StackMap elements. the size is known at the moment of allocation
-    struct StackmapHead {
-        unsigned short depth;
-        StackmapElement elements[0];
-    };
-
-    //vector of WorkMap elements. the size is known at the moment of allocation
-    struct WorkmapHead {
-        unsigned short depth;
-        WorkmapElement elements[0];
-    };
-
-#pragma warning( pop )
-
-    //Store various data for the given instruction. Possible data are: StackMap vector, WorkMap vector,
-    //Subroutine-specific data
-    //for a single instruction it might be either
-    // 1) no data
-    // 2) workmap only
-    // 3) stackmap only
-    // 4) stackmap and subroutine data. in this case two PropsHead structures are created the first one for the StackMap,
-    //    it's 'next' points to the second PropsHead containing Subroutine info. In this case second PropsHead keeps 0xFFFF
-    //    instead of 'instr'
-    // the list is used to organize storing Props as a HashTable
-    struct PropsHead {
-        // Address of the instruction for which this properties are stored
-        // or 0xFFFF if this is a subroutine data for previous PropsHead
-        // TODO: if instr_flags are not optimized, introduce a 'subroutine data' flag and get rid of 0xFFFF instructions
-        Address instr;
-
-        //next property in the list
-        PropsHead* next;
-
-        // really one bit is used: FF_ISWORKMAP. TODO: merge with (Stack|Work)map->flags
-        unsigned short instr_flags; 
-
-        //possible flag value
-        static const short FF_ISWORKMAP = 1;
-
-        //actual properties
-        union {
-            WorkmapHead workmap;
-            StackmapHead stackmap;
-        };
-
-        //get workmap stored here
-        WorkmapHead *getWorkmap() {
-            assert(is_workmap());
-            return &workmap;
-        }
-
-        //get stackmap stored here
-        StackmapHead *getStackmap() {
-            assert(!is_workmap());
-            return &stackmap;
-        }
-
-        //get subroutine data stored here
-        SubroutineData *getSubrData(int el_cnt) {
-            assert(instr == 0xFFFF);
-            return (SubroutineData *) &stackmap.elements[el_cnt];
-        }
-
-        //is it a workmap?
-        int is_workmap() {
-            return instr_flags & FF_ISWORKMAP;
-        }
-
-        //set 'is workmap' flag
-        void set_as_workmap() {
-            instr_flags |= FF_ISWORKMAP;
-        }
-
-        //clear flag
-        void clearInstrFlag(short flag) {
-            instr_flags &= ~flag;
-        }
-    };
-} // namespace CPVerifier
-
-#endif
+
+#ifndef __STACKMAP5_H__
+#define __STACKMAP5_H__
+
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include "../base/stackmap_x.h"
+
+#ifdef WIN32
+#define intptr int64
+#else
+#define intptr long
+#endif
+
+using namespace CPVerifier;
+
+namespace CPVerifier_5 {
+
+    struct StackmapElement;
+    struct WorkmapElement;
+
+    //possible relations between verificaton types
+    enum ConstraintType {
+        CT_GENERIC = 0,         // sub-defined type A is assignable to sub-defined type B
+        CT_ARRAY2REF = 1,       // A is a known-type array. element of A is assignable to sub-defined type B
+        CT_EXPECTED_TYPE = 2,   // sub-defined type A is assignable to known-type B
+        CT_INCOMING_VALUE = 3   // known-type A is assignable to sub-defined type B
+    };
+
+    //structure for maintaining subroutine-specific data
+    //until subroutine is passed with the second (dataflow) pass we record to the wait list all JSR instructions
+    //calling this subroutine. Once the subroutine is over we continue 2nd pass for each wait-listed instruction
+    //see vf_Context_Base::SubroutineDone
+    struct SubroutineData {
+        Address caller;         //first JSR instruction that called this subroutine
+        short retCount;         //number of ret instructions for this subroutine
+        uint8  subrDataflowed;   // =1 if dataflow pass for the subroutine is over
+    };
+
+    //list constant verification type (i.e. known-type) that are assignable to some sub-definite type (i.e. StackMapElement)
+    //see StackmapElement
+    struct IncomingType {
+        //next in the list
+        IncomingType *nxt;
+
+        //value of the verification type recorded as int
+        //TODO: don't remember why it's 'int' rather than 'SmConstant'
+        int value;
+
+        //simple next in the list
+        IncomingType *next() {
+            return nxt;
+        }
+    };
+
+    //list of constraints for some sub-definite verification type (i.e. StackMapElement)
+    //see StackmapElement
+
+    struct Constraint {
+        //next in the list
+        Constraint *nxt;
+
+        //either
+        union {
+            StackmapElement *variable; // sub-definite verificarion type
+            int value;                 // or constant (known) verification type rcorded as int
+        };
+
+        //consatrint type
+        ConstraintType type;
+
+        //next constrait of type 't'
+        static Constraint *next(Constraint *cur, int t) {
+            while( cur && cur->type != t ) {
+                cur = (Constraint*)cur->next();
+            }
+            return cur;
+        }
+
+        //simple next in the list
+        Constraint *next() {
+            return nxt;
+        }
+    };
+
+    //constraint of the CT_EXPECTED_TYPE type: sub-defined type A is assignable to known-type B
+    struct ExpectedType : Constraint {
+        ExpectedType *next() {
+            return (ExpectedType *) Constraint::next(Constraint::next(), CT_EXPECTED_TYPE);
+        }
+    };
+
+    //constraint of the CT_GENERIC type: sub-defined type A is assignable to sub-defined type B
+    struct GenericCnstr : Constraint {
+        GenericCnstr *next() {
+            return (GenericCnstr *) Constraint::next(Constraint::next(), CT_GENERIC);
+        }
+    };
+
+    //constraint of the CT_ARRAY2REF type: A is a known-type array. element of A is assignable to sub-defined type B
+    struct ArrayCnstr : Constraint {
+        //there can be only one CT_ARRAY2REF per StackMap Element
+        ArrayCnstr *next() {
+            assert(0);
+            return 0;
+        }
+    };
+
+
+    //StackMapElement structure represens sub-definite verification type: we don't know what type is it, but
+    //we know about instructions that expect ExpectedTypes here and we know that IncomingValues can be here
+    //we also know that this type must be assignable to other sub-defenite types as indicated by CT_GENERIC
+    //constrains and there can be special limitations represented by CT_ARRAY2REF constraints
+    struct StackmapElement { //TODO: should be rewritten to save footprint
+        //list of IncomingType constraint
+        IncomingType *incoming;
+
+        //list of all the conatraints of other types
+        Constraint *others;
+
+        //return value from any IncomingType constraint
+        //when we need to compae to some unmergable type we don;t need to interate thru the list
+        //also used to assert that an IncomingValue constraint exists
+        SmConstant getAnyIncomingValue() {
+            assert(firstIncoming());
+            return firstIncoming()->value;
+        }
+
+        //return first IncomingType constraint
+        IncomingType *firstIncoming() {
+            //TODO: I have to store somewhere the "modified" bit. Sorry.
+            return (IncomingType*)( (intptr)incoming & ~3 );
+        }
+
+        //return first conatrint of any type except IncomingType
+        Constraint *firstOthers() {
+            return others;
+        }
+
+        //return first CT_EXPECTED_TYPE constraint
+        ExpectedType *firstExpected() {
+            return (ExpectedType*)Constraint::next(others, CT_EXPECTED_TYPE);
+        }
+
+        //return first CT_GENERIC constraint
+        GenericCnstr *firstGenericCnstr() {
+            return (GenericCnstr*)Constraint::next(others, CT_GENERIC);
+        }
+
+        //return first (and the only) CT_ARRAY2REF constraint
+        ArrayCnstr *firstArrayCnstr() {
+            return (ArrayCnstr*)Constraint::next(others, CT_ARRAY2REF);
+        }
+
+        //clean-up
+        void init() {
+            incoming = 0;
+            others = 0;
+        }
+
+        //add incoming type with the 'value' value
+        void newIncomingType(Memory *mem, SmConstant value) {
+            IncomingType *in = (IncomingType *)mem->malloc(sizeof(IncomingType));
+
+            intptr mask = (intptr)incoming & 3;
+            incoming = (IncomingType *) ((intptr)incoming & ~3);
+
+            in->nxt = value == SM_BOGUS ? 0 : incoming;
+            //in->type = CT_INCOMING_VALUE;
+            in->value = value.c;
+
+            incoming = in;
+
+            incoming = (IncomingType *) ((intptr)incoming | mask);
+        }
+
+        //add expected type with the 'value' value
+        void newExpectedType(Memory *mem, SmConstant value) {
+            newConstraint(mem, CT_EXPECTED_TYPE)->value = value.c;
+        }
+
+        Constraint *newConstraint(Memory *mem, int type) {
+            Constraint *o = (Constraint *)mem->malloc(sizeof(Constraint));
+
+            o->nxt = others;
+            o->type = (ConstraintType)type;
+
+            others = o;
+            return o;
+        }
+
+        //add generic constraint ('this' is assignable to 'to')
+        void newGenericConstraint(Memory *mem, StackmapElement *to) {
+            newConstraint(mem, CT_GENERIC)->variable = to;
+        }
+
+        //add generic constraint ('this' is an array, which element is assignable to 'to')
+        void newArrayConversionConstraint(Memory *mem, StackmapElement *to) {
+            assert(!firstArrayCnstr());
+            newConstraint(mem, CT_ARRAY2REF)->variable = to;
+        }
+
+        // return 'modified' flag for the stackmap. the flag is stored in the first bit of the 'incoming' pointer
+        // "modified" is about subroutines: you have to track which locals were changed
+        int isJsrModified() {
+            return (int)(intptr)incoming & 1;
+        }
+
+        //set 'modified' flag for the stackmap. the flag is stored in the first bit of the 'incoming' pointer
+        // "modified" is about subroutines: you have to track which locals were changed
+        void setJsrModified() {
+            incoming = (IncomingType *) ((intptr)incoming | 1);
+        }
+
+        //clear 'modified' flag for the stackmap. the flag is stored in the first bit of the 'incoming' pointer
+        // "modified" is about subroutines: you have to track which locals were changed
+        void clearJsrModified() {
+            incoming = (IncomingType *) ((intptr)incoming & ~1);
+        }
+    };
+
+    //WorkMapElement structure represent an element of the workmap vector -- vector of the derived types
+    //a type might be either constant (or known) (e.g. if some previous instruction has put something on stack or locals)
+    //or sub-definite (e.g. if we've recently passed a branch target and don't know which types were on stack or locals)
+    struct WorkmapElement {
+        //value. two low bits a used to store flags
+        union {
+            _SmConstant const_val;      //either a constant (known-type)
+            StackmapElement *var_ptr;   //or a variable (sub-definite type)
+        };
+
+        //is it a sub-definite (not constant) type?
+        int isVariable() {
+            assert(const_val != SM_NONE);
+            return !((intptr)var_ptr & 1);
+        }
+
+        //get value for the constant (known) verification type
+        SmConstant getConst() {
+            return const_val;
+        }
+
+        //get variable representing sub-definite verification type
+        StackmapElement *getVariable() {
+            return (StackmapElement *) ((intptr)var_ptr & ~3);
+        }
+
+        //when we need to compae to some unmergable type we don;t need to interate thru the list
+        //also used to assert that an IncomingValue constraint exists
+        SmConstant getAnyPossibleValue() {
+            SmConstant ret = isVariable() ? getVariable()->getAnyIncomingValue() : const_val;
+            assert(ret != SM_NONE);
+            return ret;
+        }
+
+        // return 'modified' flag for the workmap element. the flag is stored in the second bit of the union
+        //"modified" is about subroutines: you have to track which locals were changed
+        //it's easier to think of all the constants as "modified"
+        int isJsrModified() {
+            return (int)(intptr)var_ptr & 3;
+        }
+
+        // set 'modified' flag for the workmap element. the flag is stored in the second bit of the union
+        void setJsrModified() {
+            if( isVariable() ) {
+                var_ptr = (StackmapElement*)((intptr)var_ptr | 2);
+            }
+        }
+    };
+
+    //WorkmapElement type with some constructors
+    struct _WorkmapElement : WorkmapElement {
+        _WorkmapElement(WorkmapElement other) {
+            const_val = other.const_val;
+        }
+
+        _WorkmapElement(StackmapElement *s) {
+            var_ptr = s;
+            if( s->isJsrModified() ) {
+                setJsrModified();
+            }
+        }
+
+        _WorkmapElement(SmConstant c) {
+            const_val = c;
+        }
+    };
+
+    //Store various data for the given instruction. Possible data are: StackMap vector, WorkMap vector,
+    //Subroutine-specific data
+    //for a single instruction it might be either
+    // 1) no data
+    // 2) workmap only
+    // 3) stackmap only
+    // 4) stackmap and subroutine data. in this case two PropsHead structures are created the first one for the StackMap,
+    //    it's 'next' points to the second PropsHead containing Subroutine info. In this case second PropsHead keeps 0xFFFF
+    //    instead of 'instr'
+    // the list is used to organize storing Props as a HashTable
+    struct PropsHead : public PropsHeadBase {
+        typedef MapHead<WorkmapElement> WorkmapHead;
+        typedef MapHead<StackmapElement> StackmapHead;
+
+        // really one bit is used: FF_ISWORKMAP. TODO: merge with (Stack|Work)map->flags
+        unsigned short instr_flags; 
+
+        //possible flag value
+        static const short FF_ISWORKMAP = 1;
+
+        //actual properties
+        union {
+            WorkmapHead workmap;
+            StackmapHead stackmap;
+        };
+
+        //get workmap stored here
+        WorkmapHead *getWorkmap() {
+            assert(is_workmap());
+            return &workmap;
+        }
+
+        //get stackmap stored here
+        StackmapHead *getStackmap() {
+            assert(!is_workmap());
+            return &stackmap;
+        }
+
+        //get subroutine data stored here
+        SubroutineData *getSubrData(int el_cnt) {
+            assert(instr == 0xFFFF);
+            return (SubroutineData *) &stackmap.elements[el_cnt];
+        }
+
+        //is it a workmap?
+        int is_workmap() {
+            return instr_flags & FF_ISWORKMAP;
+        }
+
+        //set 'is workmap' flag
+        void set_as_workmap() {
+            instr_flags |= FF_ISWORKMAP;
+        }
+
+        //clear flag
+        void clearInstrFlag(short flag) {
+            instr_flags &= ~flag;
+        }
+    };
+
+
+} // namespace CPVerifier_5
+
+#endif



Mime
View raw message