外文文獻翻譯--java虛擬機指令系統(tǒng)的編碼

1、<p><b>　　中文6000字</b></p><p>　　Encoding the Java Virtual Machine’s Instruction Set</p><p>　　1 Introduction</p><p>　　The development of programs that parse and analyz

2、e 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 bytecode and for (re-) developing standa

3、rd control- and data-flow analyses which calculate, e.g., the control-flow graph or the data-dependency graph.</p><p>　　To reduce these efforts, we have developed a specification language (OPAL SPL) for enco

4、ding the instructions of stack-based intermediate languages. The idea is that—once the instruction set is completely specified using OPAL SPL—generating both bytecode parsers and standard analyses is much easier than the

5、ir manual development. To support this goal, OPAL SPL supports the specification of both the format of bytecode instructions and the effect on the stack and registers these instructions have wh</p><p>　　Thou

6、gh the language was designed with Java Bytecode specifically in mind and is used to encode the complete instruction set of the Java Virtual Machine (JVM) , we have striven for a Java-independent specification language. I

7、n particular, OPAL SPL focuses on specifying the instruction set rather than the complete class file format, not only because the former’s structure is much more regular than the latter’s,but also because a specification

8、 of the instruction set promises to be most beneficial. </p><p>　　The next section describes the specification language. In Section3we reason about the language’s design by discussing the specification of se

9、lected JVM instructions. In 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.</p>&l

10、t;p>　　2 Specifying Bytecode Instructions</p><p>　　The language for specifying bytecode instructions (OPAL SPL) was primarily designed to enable a concise specification of the JVM’s instruction set. OPAL S

11、PL supports the specification of both an instruction’s 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 fr

12、om and pushed onto the stack as well as which local variables are read or written. Given a specification of the complete instr</p><p>　　However, OPAL SPL is not particularly tied to Java as it abstracts from

13、 the particularities of the JVM Specification. For example, the JVM’s type system is part of an OPAL SPL specification rather than an integral part of the OPAL SPL language itself.</p><p>　　Next, we first gi

14、ve an overview of the language before we discuss its semantics.</p><p>　　2.1 Syntax</p><p>　　The OPAL Specification Language (OPAL SPL) is an XML-based language. Its grammar is depicted in Fig.2

15、using 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

16、“@” (@type, @var, etc.). We refer to the content of an XML-element using symbols that start with“/” (/VALUEEXPRESSION, /EXPECTEDVALUE, etc.). “<>” is used to specify nesting of el</p><p>　　2.2 Semantic

17、s</p><p>　　Format Specification</p><p>　　Each specification written in OPAL SPL consists of four major parts (line 1 in Fig.2). The first part(types, lines 2–3) specifies the type system that is

18、 used by the underlying virtual machine. The second part (exceptions, line 4) declares the exceptions that may be thrown when instructions are executed. The third part (functions, line 5) declares the functions that are

19、used in instruction specifications. The fourth part is the specification of the instructions themselves (lines 6–12), each of w</p><p>　　The specification of an instruction consists of up to four parts： the

20、instruction’s format (lines 7–8), a description of the effect the instruction has on the stack when executed (lines 9–10), a descriptions of the registers it affects upon execution (lines 11–12), and information about th

21、e exceptions that may be thrown during execution (end of line 6). An instruction’s format is specified by sequences which describe how an instruction is stored. Theu1, u2andu4elements (line 8) of each format se</p>

22、<p>　　Unique Prefix Rule</p><p>　　One constraint placed upon specifications written in OPAL SPL is that a format sequence can be identified unambiguously by only parsing a prefix of the instruction; n

23、o 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

24、unique prefix rule is checked automatically (cf. Sec.4); furthermore, this rule facilitates generating fast parser</p><p>　　Type System</p><p>　　OPAL SPL does not have a hard-coded type hierarch

25、y. Instead, each specification written in SPL contains a description of the type system used by the bytecode language being described. The only restriction is that all types have to be arranged in a single, strict hierar

26、chy.</p><p>　　The Java Virtual Machine Specification [9]’s type hierarchy is shown in Fig.3(1). It captures all runtime types known to the Java virtual machine, as well as those types that are used only at l

27、ink- or compile-time, e.g., branchoffset, fieldref and methodref. The hierarchy is a result of the peculiarities of the JVM’s instruction set. The byteorbooleantype, e.g., is required to model the baloadandbastore instru

28、ctions, which operate on arrays of byteorbooleanalike.</p><p>　　OPAL SPL’s type system implicitly defines a second type hierarchy ((2) in Fig. 3). The declared hierarchy of types (1) is mirrored by a hierarc

29、hy of kinds (2); for every (lower-case) type there automatically exists an (upper-case) kind. This convention ensures their consistency and keeps the specification itself brief. The values of kindINT LIKEareint, short, e

30、tc., just as the values of type int like are 1, 2, etc. Kinds enable parameterizing logical instructions likeareturnwith types,thus makin</p><p>　　Information Flow</p><p>　　In OPAL SPL, the flow

31、 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 exampl

32、e, variables defined 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

33、 all format sequences, i.e., it is comm</p><p>　　3 Design Discussion</p><p>　　The design of the OPAL specification language (OPAL SPL) is influenced by the peculiarities of the JVM’s instruction

34、 set [9, Chapter 6]. In the following, we discuss those instructions that had a major influence on the design.</p><p>　　3.1 Modeling the Stack Bottom(athrow)</p><p>　　All JVM instructions—with t

35、he exception ofathrow—specify 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 layo

36、ut after its execution is completely determined (Fig.5, line 6); the single element on the stack is the thrown exception. This necessitates explicit modeling of the stack’s contents beyond the operands that are pushed an

37、d popped by a particular instruct</p><p>　　3.2 Pure Register Instructions(iinc)</p><p>　　The flow of information for instructions that do not affect the stack—e.g., the JVM’siinc instruction—is

38、depicted in Fig. 7and adheres to the general scheme of information flow (cf. Fig. 4). After parsing the instruction according to the format sequence(Fig. 6, lines3–5), the two variables lvIndex an dincrement are initiali

39、zed.</p><p>　　3.3 Interpretation of Arithmetic Instructions （iinc, add, sub,etc.）</p><p>　　The specification ofiinc (Fig. 6) also illustrates OPAL SPL’s ability to model computed values, e.g., a

40、dd(value, increment). This information can subsequently be used, e.g., by static analyses to determine data dependencies or to perform abstract interpretations.</p><p>　　3.4 Constant Pool Handling (ldc)</

41、p><p>　　The Java class file format achieves its compactness in part through the use of a constant pool. Hereby, immediate operands of an instruction are replaced by an index into the (global) pool. For example,

42、 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 value’s type, one uses the reflective type offunction that the enclosi

43、ng toolkitx has to provide (line14).</p><p>　　3.5 Multiple Format Sequences, Single Logical Instruction</p><p>　　An instruction such asldc, which may refer to an integer value in the constant po

44、ol, is conceptually similar to instructions such asiconst 0orsipush;allofthem push a constant value onto the operand stack. The primary difference between the format sequences of ldc(Fig. 8, lines 3–5)andiconst 0(lines 6

45、–7)isthat the former’s operand resides in the constant pool. In contrast, sipushencodes its operand explicitly in the bytecode stream as an immediate value (line9).</p><p>　　To facilitate standard control- a

46、nd 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 (

47、Fig. 8), e.g., subsumes all JVM instructions that just push a constant value onto the stack. In this case the pushed value is either a computed value (line5), an implicit value (line7), or an immediate operand (line9).&l

48、t;/p><p>　　3.6 Variable Operand Counts (invokevirtual, invokespecial,etc.)</p><p>　　Some instructions pop a variable number of operands, e.g., the four invoke instructions invokevirtual, invokespec

49、ial, 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 provid

50、es the list element (Fig.9, line 8). Using the list element’scountattribute, it is possible to specify a function that determines the number of operands actually poppe</p><p>　　Using functions (methodrefargc

51、ount, methodrefargtype, ...) offloads the intricate handling of the constant pool to externally supplied code (cf. Sec.3.4)—the enclosing toolkit; the OPAL specification language itself remains independent of how the fra

52、mework or toolkit under development stores such information.</p><p>　　3.7 Exceptions</p><p>　　The specification of invokevirtual (Fig. 9) also makes explicit which exceptions the instruction may

53、 throw (line 16). This information is required by control-flow analyses and thus needs to be present in specifications. To identify the instructions which may handle the exception the function (caughtby)needs to be defin

54、ed by the toolkit. This functions computes, given both the instruction’s address and the type of the exception, the addresses of all instructions in the same method that handle the</p><p>　　3.8 Variable-leng

55、th Instructions (tableswitch, lookupswitch)</p><p>　　The support for variable-length instructions (tableswitch, lookupswitch) is similar to the support for instructions with a variable stack size (cf. Sec. 3

56、.6). In this case, anelementselement can be used to specify how many times (Fig.10, line 7) which kind of values (lines8–9) need to be read. Hereby, the elementsconstruct can accommodate multiple sequence elements (lines

57、7–10).</p><p>　　The variable number of cases is, however, just one reason why table switch and lookupswitch are classified as variable-length instructions; the JVM Specification mandates that up to three pad

58、ding bytes are inserted, to align the following format elements on a four-byte boundary (line4).</p><p>　　3.9 Single Instruction, Multiple Operand Stacks (dup2)</p><p>　　The JVM specification de

59、fines several instructions that operate on the stack independent of their operands’ types or—if we change the perspective—that behave differently depending on the type of the operands present on the stack prior to their

60、execution. For example, thedup2instruction (Fig. 11) duplicates the contents of two one-word stack slots.</p><p>　　Instructions such asdup2anddup2x1distinguish their operands by their computational type (cat

61、egory 1 or 2) rather than by their actual type (int, reference,etc.). This makes it possible to compactly encode instructions such asdup2and motivates the corresponding level in the type hierarchy (cf. Sec.2.2). Addition

62、ally, this requires that OPAL SPL supports multiple stack layouts.</p><p>　　In OPAL SPL, the stack is modeled as a list of operands, not as a list of slots as discussed in the JVM specification. While the ef

63、fect of an instruction such asdup2 is more easily expressed in terms of stack slots, the vast majority of instructions naturally refers to operands. In particular, the decision to base the stack model on operands rather

64、than slots avoids explicit modeling of the higher and lower halves of category-2-values, e.g., the high and low word of a 64 bitlong operand. </p><p>　　3.10 (Conditional) Control Transfer Instructions (if, g

65、oto, jsr, ret)</p><p>　　To perform control-flow analyses it is necessary to identify those instructions that may transfer control, either by directly manipulating the program counter or terminating the curre

66、nt method. This information is specified using theinstruction element’s optional transferscontrol attribute (Fig.12, line 1). It specifies if control is transfered conditionally or always. The target instruction to which

67、 control is transferredisidentifiedbythevaluesoftype branchoffset orabsoluteaddress.For these two</p><p>　　3.11 Multibyte Opcodes and Modifiers (wideinstructions, newarray)</p><p>　　The JVM inst

68、ruction set consists mostly of instructions whose opcode is a single byte, although a few instructions have longer opcode sequences. In most cases this is due to the widemodifier, a single byte prefix to the instruction.

69、 In case of the newarray instruction, however, a suffix is used to determine its precise effect. As can be seen in Fig.13, the parser needs to examine two bytes to determine the correct format sequence.</p><p&

70、gt;　　3.12 Implicit Types and Type Constructors</p><p>　　The specification ofnewarray(Fig.13) also illustrates the specification of implied types and type constructors. As the JVM instruction set is a typed a

71、ssembly language, many instructions exist in a variety of formats, e.g., asiadd, ladd, fadd, anddadd.Theimplicit type construct is designed to eliminate this kind of redundancy in the specification, resulting in a single

72、, logical instruction：add. Similarily, newarraymakes use of type bindings (lines5, 8).</p><p>　　But, to precisely model the effect ofnewarrayon the operand stack, an additional function that constructs a typ

73、e is needed. Given a type and an integer, the function arrayconstructs a new type; here, a one-dimensional array of the base type (line14).</p><p>　　3.13 Extension Mechanism</p><p>　　OPAL SPL ha

74、s been designed with extensibility in mind. The extension point for additional information is the instruction element’sappinfochild, whose content can consist of arbitrary elements with a namespace other than OPAL SPL’s

75、own.</p><p>　　To illustrate the mechanism, suppose that we want to create a Prolog representation for Java Bytecode, in which information about operators is explicit, i.e., in which theifgt instruction is a

76、n if instruction which compares two values using the greater than operator, as illustrated by Fig.14.</p><p>　　4 Validating Specifications</p><p>　　To validate an OPAL SPL specification, we have

77、 defined an XML Schema which ensures syntactic correctness of the specification and performs basic identity checking. It checks, for example, that each declared type and each instruction’s mnemonic is unique. Additionall

78、y, we have developed a program which analyzes a specification and detects the following errors: (a) a format sequence does not have a unique prefix path, (b) multiple format sequences of a single instruction do not agree

79、 in the variab</p><p>　　5 Evaluation</p><p>　　We have used the specification of the JVM’s instruction set [9] for the implementation of a highly flexible bytecode toolkit. The toolkit supports f

80、our representations of Java bytecode: a native representation, which is a one-to-one representation of the Java Bytecode; a higher-level representation, which abstracts away some details of Java bytecode—in particular fr

81、om the constant pool; an XML representation which uses the higher-level representation; a Prolog-based representation of Java Byteco</p><p>　　6 Related Work</p><p>　　Applying XML technologies to

82、 Java bytecode is not a new idea [5]. The XML serialization of class files, e.g., allows for their declarative transformation using XSLT. The XMLVM [11] project aims to support not only the JVM instruction set [9], but a

83、lso the CLR instruction set [8]. This requires that at least the CLR’s operand stack is transformed [12], as the JVM requires. The description of the effect that individual CLR instructions have on the operand stack is,

84、however, not specified in an eas</p><p>　　7 Conclusion and Future Work</p><p>　　In future work, we will investigate the use of OPAL SPL for the encoding of other bytecode languages, such as the

85、Common Intermediate Language. This would make it possible to develop (control- and dataflow-) analyses with respect to the OPAL SPL and to use the same analysis to analyze bytecode of different languages.</p><

86、p>　　From:Encoding the Java Virtual Machine’s Instruction Set</p><p>　　Java虛擬機指令系統(tǒng)的編碼</p><p><b>　　1引言</b></p><p>　　解釋和分析Java字節(jié)碼程序的發(fā)展有已經(jīng)長的歷史了，新的方案仍在研究。然而，開發(fā)這類工具，大量的時間都會

87、花在開發(fā)解析器的字節(jié)碼和 （重新）制定的標(biāo)準(zhǔn)控制分析和數(shù)據(jù)流分析，他們是用于計算的，如控制流圖或數(shù)據(jù)依賴圖。</p><p>　　為了減少這些工作，我們已經(jīng)制定了規(guī)范語言（OPAL SPL）來對基于堆棧的中間語言指令進行編碼。一旦使用OPAL SPL語言產(chǎn)生完全指定的指令集 ，我們的思路是兩個字節(jié)碼的解析器和標(biāo)準(zhǔn)分析比他們的手工制定更容易。為了支持這一目標(biāo)，OPAL SPL支持規(guī)范的 字節(jié)碼指令和堆棧上的效果格式

88、并且當(dāng)有指令執(zhí)行時，注冊它們。另一種使用的OPAL SPL的特殊情況是用于輸入到一個通用分析程序或通用的分析所。</p><p>　　雖然語言是通過Java字節(jié)碼內(nèi)在的設(shè)計與并且用于Java虛擬機（JVM）的完整指令集進行編碼，我們努力的制作獨立的Java規(guī)范語言。特別是，OPAL SPL側(cè)重于指定指令集，而不是完整的類文件格式，這不僅是因為前者的結(jié)構(gòu)比后者更為正規(guī)，但也因為指令集的規(guī)范可能成為最有利的。鑒于OP

89、AL SPL的第一重點是基本生成解析器，我們明確了設(shè)計的語言，使得我們有可能對相關(guān)的指令進行分組。這就使得規(guī)范更為簡潔，并允許以幾乎相同方式的類似指令分析。例如， JVM的ILOAD 5指令，即加載存儲在寄存器#5的整數(shù)值，是一種通用ILOAD指令的操作數(shù)是5的特殊情況。我們以這樣一種方式設(shè)計OPAL SPL，即規(guī)范沒有規(guī)定一個框架如何代表或處理信息;例如 OPALSPL是表示不可知。</p><p>　　下一節(jié)

90、所要描述的的規(guī)范語言。在第3節(jié)，我們通過討論選定的JVM指令的規(guī)范解釋關(guān)于語言的設(shè)計。 在第4節(jié)，我們對規(guī)格驗證進行了討論。第5節(jié)，我們提出該方法的評價。論文的最后，我們以相關(guān)工作的討論和一個結(jié)論結(jié)尾。</p><p><b>　　2指定字節(jié)碼指令</b></p><p>　　指定的字節(jié)碼指令（OPAL SPL）的語言最初的設(shè)計主要是啟用簡潔規(guī)范的JVM的指令集。當(dāng)執(zhí)

91、行的指令時，OPAL SPL 支持規(guī)定的指令格式和它在棧上與局部變量（寄存器）上產(chǎn)生的效果。這樣可以 指定哪些類型的值都彈出和壓入堆棧，以及其中的局部變量讀取或?qū)懭搿Ｍ暾囊?guī)范的給出指令集通過標(biāo)準(zhǔn)控制然后對數(shù)據(jù)流所需的信息進行分析就可以做到了。</p><p>　　然而，OPAL SPL并不特別依賴于Java，因為它從JVM規(guī)范特性分離出來。例如，JVM的類型系統(tǒng)是 OPAL SPL規(guī)范的一部分，而不是OPAL

92、SPL語言本身的一個組成部分 。 </p><p>　　接下來，在我們討論它的語義前，我們先給出語言的綜述。</p><p><b>　　2.1　語法</b></p><p>　　OPAL規(guī)范語言（OPAL SPL）是一種基于XML的語言。其語法在圖2中是使用EBNF類似的格式進行描繪。非終結(jié)符都用大寫字母（INSTRUCTIONS, TYPE

93、S等），XML元素的名稱用小字母（types, stack等）表達和XML的屬性的名稱 以“@” （@type, @var等）開始。我們參考的一個XML元素的內(nèi)容以“/”開始（/VALUEEXPRESSION, /EXPECTEDVALUE， 等）。 “<>”用于指定元素的嵌套。 “（），+，*，{}，|？”具有通常的 語義。例如，exceptions< （exception @type）+ >指定了 XML元素

94、exceptions具有一個或多個exception子元素,它們總是有type的屬性。</p><p><b>　　2.2語義</b></p><p><b>　　格式規(guī)范</b></p><p>　　用OPAL SPL寫的每一種規(guī)格都有四個主要部分（圖 2中第1行）。第一部分（types，2-3行）指定該類型的系統(tǒng) ，用

95、來做虛擬機基礎(chǔ)。第二部分（exception，4行）表示指令執(zhí)行時，可能會出現(xiàn)被拋出的意外。第三部分（functions， 5行）表示，在指令規(guī)范中使用的函數(shù)。第四部分是指令規(guī)范的本身（6-12行），其中每個都通過函數(shù)來獲取信息而不是簡單地與該指令存儲 。例如，invoke指令不存儲信號并指出類的調(diào)用的方法。相反，在所謂的常量池引用的一個條目就被存儲起來。只有這種常量池項有關(guān)于類函數(shù)的所有信息 。例如為了獲得類函數(shù)被調(diào)用的方法的返回類型

96、，一個抽象的函數(shù)TYPE methodref return type（methodref）表明將參考該條目作為輸入并返回該方法的返回類型。使用抽象函數(shù)表明，我們通過封閉字節(jié)碼工具包，從此類信息的具體表現(xiàn)分離出來。</p><p>　　指令的規(guī)范包括最多四個部分組成：指令的格式（第7-8行） ，指令產(chǎn)生的效果在堆棧上執(zhí)行的描述（第9-10行 ），寄存器執(zhí)行時產(chǎn)生影響的描述（第11-12行 ），以及關(guān)于可能在執(zhí)行過程

97、中出現(xiàn)拋出的異常信息（第6行的末尾） 。一個指令的格式是由它描述的序列來指定指令如何被存儲的。每種格式的U1，U2和U4元素（第8行）序中指定的當(dāng)前值分別是1 ， 2和4字節(jié)的無符號整數(shù)值。同樣， I1，I2和I4元素（第8行）被用來指定當(dāng)前值是（1，2或4字節(jié)）符號整數(shù)值。這些值可以綁定到使用var屬性的變量，它們使用type屬性也可以有第二個語義。例如， <i2 type="short" var="

98、;value"/>是兩字節(jié)的有符號整數(shù)的值被綁定到該變量，并且輸入符號的短整型值與指令集的類型系統(tǒng)相關(guān)。此外，它可以指定期望的值（第8行） 。這使得格式序列的選擇用于讀入該指令。例如， <sequence><u1 var=”opcode”>171</u1>...規(guī)定，如果第一個字節(jié)的值是171，這個順序匹配。序列的列表元素被用來指定一個數(shù)目可變的值需要讀取。元素的實際數(shù)字由計數(shù)屬性來確

99、定。該屬性的值是由之前賦值</p><p><b>　　獨特的前綴規(guī)則</b></p><p>　　一個用OPAL SPL規(guī)范寫入的約束是一個格式序列可以明確地用解析指令的前綴來標(biāo)識; 沒有超前是必要的。換句話說，如果每個格式的序列被認(rèn)為是一個 產(chǎn)品并且U1，U2，等被認(rèn)為是一個終端，然后OPAL SPL需要 格式序列來構(gòu)成一個LR（0）語法。這種獨特的前綴規(guī)則自動檢