Encoding the Java Virtual Machine’s Instruction Set毕业设计外文文献翻译.doc

1、外文资料原文Encoding the Java Virtual Machines Instruction Set 1 Introduction The development of programs that parse and analyze Java Bytecode 9 has a long history and new programs are still developed 2,3,4,7,13. When developing such tools, however, a lot of effort is spent to develop a parser for the byt

2、ecode and for (re-) developing standard control- and data-flow analyses which calculate, e.g., the control-flow graph or the data-dependency graph. To reduce these efforts, we have developed a specification language (OPAL SPL) for encoding the instructions of stack-based intermediate languages. The

3、idea is thatonce the instruction set is completely specified using OPAL SPLgenerating both bytecode parsers and standard analyses is much easier than their manual development. To support this goal, OPAL SPL supports the specification of both the format of bytecode instructions and the effect on the

4、stack and registers these instructions have when executed. An alternative use of an OPAL SPL specification is as input to a generic parser or to generic analyses as illustrated by Fig. 1 Though the language was designed with Java Bytecode specifically in mind and is used to encode the complete instr

5、uction set of the Java Virtual Machine (JVM) , we have striven for a Java-independent specification language. In particular, OPAL SPL focuses on specifying the instruction set rather than the complete class file format, not only because the formers structure is much more regular than the latters,but

6、 also because a specification of the instruction set promises to be most beneficial. Given the primary focus of OPAL SPLgenerating parsers and facilitating basic analyseswe explicitly designed the language such that it is possible to group related instructions. This makes specifications more concise

7、 and allows analyses to treat similar instructions in nearly the same way. For example, the JVMs iload 5 instruction, which loads the integer value stored in register #5, is a special case of the generic iload instruction where the instructions operand is 5. We also designed OPAL SPL in such a way t

8、hat specifications do not prescribe how a framework represents or processes information; i.e., OPAL SPL is representation agnostic. The next section describes the specification language. In Section3we reason about the languages design by discussing the specification of selected JVM instructions. In

9、Section4the validation of specifications is discussed. The evaluation of the approach is presented in Section5. The paper ends with a discussion of related work and a conclusion. 2 Specifying Bytecode Instructions The language for specifying bytecode instructions (OPAL SPL) was primarily designed to

10、 enable a concise specification of the JVMs instruction set. OPAL SPL supports the specification of both an instructions format and its effect on the stack and local variables (registers)when the instruction is executed. It is thus possible to specify which kind of values are popped from and pushed

11、onto the stack as well as which local variables are read or written. Given a specification of the complete instruction set the information required by standard control- and data-flow analyses is then available. However, OPAL SPL is not particularly tied to Java as it abstracts from the particulariti

12、es of the JVM Specification. For example, the JVMs type system is part of an OPAL SPL specification rather than an integral part of the OPAL SPL language itself. Next, we first give an overview of the language before we discuss its semantics. 2.1 Syntax The OPAL Specification Language (OPAL SPL) is

13、an XML-based language. Its grammar is depicted in Fig.2using an EBNF-like format. Non-terminals are written in capital letters (INSTRUCTIONS, TYPES, etc.), the names of XML-elements are written in small letters (types, stack, etc.) and the names of XML-attributes start with “” (type, var, etc.). We

14、refer to the content of an XML-element using symbols that start with“/” (/VALUEEXPRESSION, /EXPECTEDVALUE, etc.). “” is used to specify nesting of elements. “( ),?,+,*,|” have the usual semantics. For example,exceptionsspecifies that the XML-elementexceptionshas one or moreexceptionchild elements th

15、at always have the attributetype. 2.2 Semantics Format Specification Each specification written in OPAL SPL consists of four major parts (line 1 in Fig.2). The first part(types, lines 23) specifies the type system that is used by the underlying virtual machine. The second part (exceptions, line 4) d

16、eclares the exceptions that may be thrown when instructions are executed. The third part (functions, line 5) declares the functions that are used in instruction specifications. The fourth part is the specification of the instructions themselves (lines 612), each of which may resort to the declared f

17、unctions to access information not simply stored along with the instruction. For example,invoke instructions do not store the signature and declaring class of the called methods. Instead, a reference to an entry in the so-called constant pool is stored. Only this constant pool entry has all informat

18、ion about the method. To obtain, e.g., the return type of the called method, an abstract function TYPE method refreturn type(method ref) is declared that takes a reference to the entry as input and returns the methods return type. Using abstract function declarations, we abstractin the specification

19、 of the instructionsfrom the concrete representation of such information by the enclosing by tecode toolkit. The specification of an instruction consists of up to four parts： the instructions format (lines 78), a description of the effect the instruction has on the stack when executed (lines 910), a

20、 descriptions of the registers it affects upon execution (lines 1112), and information about the exceptions that may be thrown during execution (end of line 6). An instructions format is specified by sequences which describe how an instruction is stored. Theu1, u2andu4elements (line 8) of each forma

21、t sequence specify that the current value is an unsigned integer value with 1, 2 and 4 bytes, respectively. Similarly, thei1, i2 andi4 elements (line 8) are used to specify that the current value is a (1, 2 or 4 byte) signed integer value. The values can be bound to variables using thevarat tribute

22、and can be given a second semantics using thetype attribute. For example,is a twobyte signed integer value that is bound to the variable value and has type short with respect to the instruction sets type system. Additionally, it is possible to specify expected values (line 8). This enables the selec

23、tion of the format sequence to be used for reading in the instruction. E.g., 171. specifies that this sequence matches if the value of the first byte is 171. A sequences list element is used to specify that a variable number of values need to be read. The concrete number of elements is determined by

24、 the count attribute. The attributes value is an expression that can use values that were previously assigned to a variable. The sequence elements implicit and implicit type are used to bind implicit value and type information to variables that can later on be used in type or value expressions(line

25、7, 10 and 11). To make it possible to aggregate related bytecode instructions to one logical instruction, several format sequences can be defined. The effect on the stack is determined by the number and type of stack operands that are popped (line 9) and pushed (line 10). If multiple stack layouts a

26、re specified, the effect on the stack is determined by the firstbefore-executionstack layout that matches; i.e., to determine the effect on the stack a data-flow analysis is necessary. Unique Prefix Rule One constraint placed upon specifications written in OPAL SPL is that a format sequence can be i

27、dentified unambiguously by only parsing a prefix of the instruction; no lookahead is necessary. In other words, if each format sequence is considered a production and eachu1, u2, etc. is considered a terminal, then OPAL SPL requires the format sequences to constitute an LR(0) grammar This unique pre

28、fix rule is checked automatically (cf. Sec.4); furthermore, this rule facilitates generating fast parsers from the specification, e.g., using nestedswitchstatements. Type System OPAL SPL does not have a hard-coded type hierarchy. Instead, each specification written in SPL contains a description of t

29、he type system used by the bytecode language being described. The only restriction is that all types have to be arranged in a single, strict hierarchy. The Java Virtual Machine Specification 9s type hierarchy is shown in Fig.3(1). It captures all runtime types known to the Java virtual machine, as w

30、ell as those types that are used only at link- or compile-time, e.g., branchoffset, fieldref and methodref. The hierarchy is a result of the peculiarities of the JVMs instruction set. The byteorbooleantype, e.g., is required to model the baloadandbastore instructions, which operate on arrays of byte

31、orbooleanalike. OPAL SPLs type system implicitly defines a second type hierarchy (2) in Fig. 3). The declared hierarchy of types (1) is mirrored by a hierarchy of kinds (2); for every (lower-case) type there automatically exists an (upper-case) kind. This convention ensures their consistency and kee

32、ps the specification itself brief. The values of kindINT LIKEareint, short, etc., just as the values of type int like are 1, 2, etc. Kinds enable parameterizing logical instructions likeareturnwith types,thus making a concise specification of related instructions (e.g., freturn, ireturn, andareturn)

33、 possible (cf. Sec.3.12). Information Flow In OPAL SPL, the flow of information (values, types, register IDs) is modeled by means of named variables and expressions using the variables. In general, the flow of information is subject to the constraints illustrated by Fig.4. For example, variables def

34、ined within a specific format sequence can only be referred to by later elements within the same format sequence; a variable cannot be referred to across format sequences. If the same variable is bound by all format sequences, i.e., it is common to all format sequences, then the variable can be used

35、 to identify register IDs, the values pushed onto the stack, etc. Similarly, if an instruction defines multiple stack layouts, then a value can only flow from the i-th stack layout before execution to the i-th stack layout after execution and only information that is common to all stack layouts befo

36、re execution may be stored in a register. 3 Design Discussion The design of the OPAL specification language (OPAL SPL) is influenced by the peculiarities of the JVMs instruction set 9, Chapter 6. In the following, we discuss those instructions that had a major influence on the design. 3.1 Modeling t

37、he Stack Bottom(athrow) All JVM instructionswith the exception ofathrowspecify only the number and types of operands popped from and pushed onto the stack; they do not determine the layout of the complete stack. In case of the athrowinstruction, however, the stack layout after its execution is compl

38、etely determined (Fig.5, line 6); the single element on the stack is the thrown exception. This necessitates explicit modeling of the stacks contents beyond the operands that are pushed and popped by a particular instruction. The explicit modeling of the rest of the stack (line5) here by allows for

39、the (implicit) modeling of stacks of a fixed size (line6). 3.2 Pure Register Instructions(iinc) The flow of information for instructions that do not affect the stacke.g., the JVMsiinc instructionis depicted in Fig. 7and adheres to the general scheme of information flow (cf. Fig. 4). After parsing th

40、e instruction according to the format sequence(Fig. 6, lines35), the two variables lvIndex an dincrement are initialized. 3.3 Interpretation of Arithmetic Instructions （iinc, add, sub,etc.） The specification ofiinc (Fig. 6) also illustrates OPAL SPLs ability to model computed values, e.g., add(value

41、, increment). This information can subsequently be used, e.g., by static analyses to determine data dependencies or to perform abstract interpretations. 3.4 Constant Pool Handling (ldc) The Java class file format achieves its compactness in part through the use of a constant pool. Hereby, immediate

42、operands of an instruction are replaced by an index into the (global) pool. For example, in case of the load constant intructionldc, the operand needs to be programmatically retrieved from the constant pool (Fig.8, line 5). To obtain the values type, one uses the reflective type offunction that the

43、enclosing toolkitx has to provide (line14). 3.5 Multiple Format Sequences, Single Logical Instruction An instruction such asldc, which may refer to an integer value in the constant pool, is conceptually similar to instructions such asiconst 0orsipush;allofthem push a constant value onto the operand

44、stack. The primary difference between the format sequences of ldc(Fig. 8, lines 35)andiconst 0(lines 67)isthat the formers operand resides in the constant pool. In contrast, sipushencodes its operand explicitly in the bytecode stream as an immediate value (line9). To facilitate standard control- and

45、 data-flow analyses, OPAL SPL abstracts away from such details, so that similar instructions can be subsumed by more generic instructions using explicit or implicit type and value bindings. A generic push instruction (Fig. 8), e.g., subsumes all JVM instructions that just push a constant value onto

46、the stack. In this case the pushed value is either a computed value (line5), an implicit value (line7), or an immediate operand (line9). 3.6 Variable Operand Counts (invokevirtual, invokespecial,etc.) Some instructions pop a variable number of operands, e.g., the four invoke instructions invokevirtu

47、al, invokespecial, invokeinterface,andinvokestatic. In their case the number of popped operands directly depends on the number of arguments of the method. To support instructions that pop a variable number of operands, OPAL SPL provides the list element (Fig.9, line 8). Using the list elementscounta

48、ttribute, it is possible to specify a function that determines the number of operands actually popped from the stack. It is furthermore possible, by using theloop varattribute, to specify a variable iterating over these operands. The loop variable (i) can then be used inside the list element to specify the expected operands (line10). This enables specification of both the expected number and type of operands, i.e., of the method arguments (lines810). Using functions (methodrefargcount, methodrefargtype, .) offloads the intricate handling of the constant pool