You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by ml...@apache.org on 2007/10/12 12:32:52 UTC
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...
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