source: trunk/abcl/src/org/armedbear/lisp/jvm-instructions.lisp

Last change on this file was 15616, checked in by Mark Evenson, 16 months ago

Fix ASTORE, ILOAD, ISTORE, ILOAD, and LSTORE for wide access

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 40.6 KB
Line 
1;;; jvm-instructions.lisp
2;;;
3;;; Copyright (C) 2003-2006 Peter Graves
4;;; Copyright (C) 2010 Erik Huelsmann
5;;; $Id: jvm-instructions.lisp 15616 2022-12-08 16:08:59Z mevenson $
6;;;
7;;; This program is free software; you can redistribute it and/or
8;;; modify it under the terms of the GNU General Public License
9;;; as published by the Free Software Foundation; either version 2
10;;; of the License, or (at your option) any later version.
11;;;
12;;; This program is distributed in the hope that it will be useful,
13;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
14;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15;;; GNU General Public License for more details.
16;;;
17;;; You should have received a copy of the GNU General Public License
18;;; along with this program; if not, write to the Free Software
19;;; Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
20;;;
21;;; As a special exception, the copyright holders of this library give you
22;;; permission to link this library with independent modules to produce an
23;;; executable, regardless of the license terms of these independent
24;;; modules, and to copy and distribute the resulting executable under
25;;; terms of your choice, provided that you also meet, for each linked
26;;; independent module, the terms and conditions of the license of that
27;;; module.  An independent module is a module which is not derived from
28;;; or based on this library.  If you modify this library, you may extend
29;;; this exception to your version of the library, but you are not
30;;; obligated to do so.  If you do not wish to do so, delete this
31;;; exception statement from your version.
32
33(in-package #:jvm)
34
35(require "COMPILER-ERROR")
36
37
38(declaim (inline u2 s1 s2))
39
40(defknown u2 (fixnum) cons)
41(defun u2 (n)
42  (declare (optimize speed))
43  (declare (type (unsigned-byte 16) n))
44  (when (not (<= 0 n 65535))
45    (error "u2 argument ~A out of 65k range." n))
46  (list (logand (ash n -8) #xff)
47        (logand n #xff)))
48
49(defknown s1 (fixnum) fixnum)
50(defun s1 (n)
51  (declare (optimize speed))
52  (declare (type (signed-byte 8) n))
53  (when (not (<= -128 n 127))
54    (error "s1 argument ~A out of 8-bit signed range." n))
55  (if (< n 0)
56      (1+ (logxor (- n) #xFF))
57      n))
58
59
60(defknown s2 (fixnum) cons)
61(defun s2 (n)
62  (declare (optimize speed))
63  (declare (type (signed-byte 16) n))
64  (when (not (<= -32768 n 32767))
65    (error "s2 argument ~A out of 16-bit signed range." n))
66  (u2 (if (< n 0) (1+ (logxor (- n) #xFFFF))
67          n)))
68
69;;    OPCODES
70
71(defconst *opcode-table* (make-array 256))
72
73(defconst *opcodes* (make-hash-table :test 'equalp))
74
75;; instruction arguments are encoded as part of the instruction,
76;; we're not talking stack values here.
77
78;; b = signed byte (8-bit)
79;; B = unsigned byte (8-bit)
80;; w = signed word (16-bit)
81;; W = unsigned word (16-bit)
82;; i = signed int (32-bit)
83;; I = unsigend int (32-bit)
84
85;; o = signed offset (relative code pointer) (16-bit)
86;; p = pool index (unsigned 8-bit)
87;; P = pool index (unsigned 16-bit)
88;; l = local variable (8-bit)
89;; L = local variable (16-bit)
90
91;; z = zero padding (1 to 3 bytes) to guarantee 4-byte alignment
92;;      of the following arguments
93;; q = lookupswitch variable length instruction arguments
94;; Q = tableswitch variable length instruction arguments
95
96;; t = 8-bit java builtin type designator (in {4,5,6,7,8,9,10,11})
97
98
99(defstruct jvm-opcode name number size stack-effect register-used
100           (args-spec ""))
101
102(defun %define-opcode (name number size stack-effect register
103                       &optional args-spec)
104  (declare (type fixnum number size))
105  (let* ((name (string name))
106         (opcode (make-jvm-opcode :name name
107                                  :number number
108                                  :size size
109                                  :stack-effect stack-effect
110                                  :register-used register
111                                  :args-spec args-spec)))
112     (setf (svref *opcode-table* number) opcode)
113     (setf (gethash name *opcodes*) opcode)
114     (setf (gethash number *opcodes*) opcode)))
115
116(defmacro define-opcode (name number size stack-effect register
117                         &optional args-spec)
118  `(%define-opcode ',name ,number ,size ,stack-effect ,register
119                   ,@(when args-spec
120                           (list args-spec))))
121
122;; name number size stack-effect register-used
123(define-opcode nop 0 1 0 nil)
124(define-opcode aconst_null 1 1 1 nil)
125(define-opcode iconst_m1 2 1 1 nil)
126(define-opcode iconst_0 3 1 1 nil)
127(define-opcode iconst_1 4 1 1 nil)
128(define-opcode iconst_2 5 1 1 nil)
129(define-opcode iconst_3 6 1 1 nil)
130(define-opcode iconst_4 7 1 1 nil)
131(define-opcode iconst_5 8 1 1 nil)
132(define-opcode lconst_0 9 1 2 nil)
133(define-opcode lconst_1 10 1 2 nil)
134(define-opcode fconst_0 11 1 1 nil)
135(define-opcode fconst_1 12 1 1 nil)
136(define-opcode fconst_2 13 1 1 nil)
137(define-opcode dconst_0 14 1 2 nil)
138(define-opcode dconst_1 15 1 2 nil)
139(define-opcode bipush 16 2 1 nil)
140(define-opcode sipush 17 3 1 nil)
141(define-opcode ldc 18 2 1 nil "p")
142(define-opcode ldc_w 19 3 1 nil "P")
143(define-opcode ldc2_w 20 3 2 nil "P")
144(define-opcode iload 21 2 1 t)
145(define-opcode lload 22 2 2 t)
146(define-opcode fload 23 2 nil t)
147(define-opcode dload 24 2 nil t)
148(define-opcode aload 25 2 1 t)
149(define-opcode iload_0 26 1 1 0)
150(define-opcode iload_1 27 1 1 1)
151(define-opcode iload_2 28 1 1 2)
152(define-opcode iload_3 29 1 1 3)
153(define-opcode lload_0 30 1 2 0)
154(define-opcode lload_1 31 1 2 1)
155(define-opcode lload_2 32 1 2 2)
156(define-opcode lload_3 33 1 2 3)
157(define-opcode fload_0 34 1 nil 0)
158(define-opcode fload_1 35 1 nil 1)
159(define-opcode fload_2 36 1 nil 2)
160(define-opcode fload_3 37 1 nil 3)
161(define-opcode dload_0 38 1 nil 0)
162(define-opcode dload_1 39 1 nil 1)
163(define-opcode dload_2 40 1 nil 2)
164(define-opcode dload_3 41 1 nil 3)
165(define-opcode aload_0 42 1 1 0)
166(define-opcode aload_1 43 1 1 1)
167(define-opcode aload_2 44 1 1 2)
168(define-opcode aload_3 45 1 1 3)
169(define-opcode iaload 46 1 -1 nil)
170(define-opcode laload 47 1 0 nil)
171(define-opcode faload 48 1 -1 nil)
172(define-opcode daload 49 1 0 nil)
173(define-opcode aaload 50 1 -1 nil)
174(define-opcode baload 51 1 nil nil)
175(define-opcode caload 52 1 nil nil)
176(define-opcode saload 53 1 nil nil)
177(define-opcode istore 54 2 -1 t)
178(define-opcode lstore 55 2 -2 t)
179(define-opcode fstore 56 2 nil t)
180(define-opcode dstore 57 2 nil t)
181(define-opcode astore 58 2 -1 t)
182(define-opcode istore_0 59 1 -1 0)
183(define-opcode istore_1 60 1 -1 1)
184(define-opcode istore_2 61 1 -1 2)
185(define-opcode istore_3 62 1 -1 3)
186(define-opcode lstore_0 63 1 -2 0)
187(define-opcode lstore_1 64 1 -2 1)
188(define-opcode lstore_2 65 1 -2 2)
189(define-opcode lstore_3 66 1 -2 3)
190(define-opcode fstore_0 67 1 nil 0)
191(define-opcode fstore_1 68 1 nil 1)
192(define-opcode fstore_2 69 1 nil 2)
193(define-opcode fstore_3 70 1 nil 3)
194(define-opcode dstore_0 71 1 nil 0)
195(define-opcode dstore_1 72 1 nil 1)
196(define-opcode dstore_2 73 1 nil 2)
197(define-opcode dstore_3 74 1 nil 3)
198(define-opcode astore_0 75 1 -1 0)
199(define-opcode astore_1 76 1 -1 1)
200(define-opcode astore_2 77 1 -1 2)
201(define-opcode astore_3 78 1 -1 3)
202(define-opcode iastore 79 1 -3 nil)
203(define-opcode lastore 80 1 -4 nil)
204(define-opcode fastore 81 1 -3 nil)
205(define-opcode dastore 82 1 -4 nil)
206(define-opcode aastore 83 1 -3 nil)
207(define-opcode bastore 84 1 nil nil)
208(define-opcode castore 85 1 nil nil)
209(define-opcode sastore 86 1 nil nil)
210(define-opcode pop 87 1 -1 nil)
211(define-opcode pop2 88 1 -2 nil)
212(define-opcode dup 89 1 1 nil)
213(define-opcode dup_x1 90 1 1 nil)
214(define-opcode dup_x2 91 1 1 nil)
215(define-opcode dup2 92 1 2 nil)
216(define-opcode dup2_x1 93 1 2 nil)
217(define-opcode dup2_x2 94 1 2 nil)
218(define-opcode swap 95 1 0 nil)
219(define-opcode iadd 96 1 -1 nil)
220(define-opcode ladd 97 1 -2 nil)
221(define-opcode fadd 98 1 -1 nil)
222(define-opcode dadd 99 1 -2 nil)
223(define-opcode isub 100 1 -1 nil)
224(define-opcode lsub 101 1 -2 nil)
225(define-opcode fsub 102 1 -1 nil)
226(define-opcode dsub 103 1 -2 nil)
227(define-opcode imul 104 1 -1 nil)
228(define-opcode lmul 105 1 -2 nil)
229(define-opcode fmul 106 1 -1 nil)
230(define-opcode dmul 107 1 -2 nil)
231(define-opcode idiv 108 1 nil nil)
232(define-opcode ldiv 109 1 nil nil)
233(define-opcode fdiv 110 1 nil nil)
234(define-opcode ddiv 111 1 nil nil)
235(define-opcode irem 112 1 nil nil)
236(define-opcode lrem 113 1 nil nil)
237(define-opcode frem 114 1 nil nil)
238(define-opcode drem 115 1 nil nil)
239(define-opcode ineg 116 1 0 nil)
240(define-opcode lneg 117 1 0 nil)
241(define-opcode fneg 118 1 0 nil)
242(define-opcode dneg 119 1 0 nil)
243(define-opcode ishl 120 1 -1 nil)
244(define-opcode lshl 121 1 -1 nil)
245(define-opcode ishr 122 1 -1 nil)
246(define-opcode lshr 123 1 -1 nil)
247(define-opcode iushr 124 1 nil nil)
248(define-opcode lushr 125 1 nil nil)
249(define-opcode iand 126 1 -1 nil)
250(define-opcode land 127 1 -2 nil)
251(define-opcode ior 128 1 -1 nil)
252(define-opcode lor 129 1 -2 nil)
253(define-opcode ixor 130 1 -1 nil)
254(define-opcode lxor 131 1 -2 nil)
255(define-opcode iinc 132 3 0 t)
256(define-opcode i2l 133 1 1 nil)
257(define-opcode i2f 134 1 0 nil)
258(define-opcode i2d 135 1 1 nil)
259(define-opcode l2i 136 1 -1 nil)
260(define-opcode l2f 137 1 -1 nil)
261(define-opcode l2d 138 1 0 nil)
262(define-opcode f2i 139 1 nil nil)
263(define-opcode f2l 140 1 nil nil)
264(define-opcode f2d 141 1 1 nil)
265(define-opcode d2i 142 1 nil nil)
266(define-opcode d2l 143 1 nil nil)
267(define-opcode d2f 144 1 -1 nil)
268(define-opcode i2b 145 1 nil nil)
269(define-opcode i2c 146 1 nil nil)
270(define-opcode i2s 147 1 nil nil)
271(define-opcode lcmp 148 1 -3 nil)
272(define-opcode fcmpl 149 1 -1 nil)
273(define-opcode fcmpg 150 1 -1 nil)
274(define-opcode dcmpl 151 1 -3 nil)
275(define-opcode dcmpg 152 1 -3 nil)
276(define-opcode ifeq 153 3 -1 nil)
277(define-opcode ifne 154 3 -1 nil)
278(define-opcode iflt 155 3 -1 nil)
279(define-opcode ifge 156 3 -1 nil)
280(define-opcode ifgt 157 3 -1 nil)
281(define-opcode ifle 158 3 -1 nil)
282(define-opcode if_icmpeq 159 3 -2 nil)
283(define-opcode if_icmpne 160 3 -2 nil)
284(define-opcode if_icmplt 161 3 -2 nil)
285(define-opcode if_icmpge 162 3 -2 nil)
286(define-opcode if_icmpgt 163 3 -2 nil)
287(define-opcode if_icmple 164 3 -2 nil)
288(define-opcode if_acmpeq 165 3 -2 nil)
289(define-opcode if_acmpne 166 3 -2 nil)
290(define-opcode goto 167 3 0 nil)
291;;(define-opcode jsr 168 3 1) Don't use these 2 opcodes: deprecated
292;;(define-opcode ret 169 2 0) their use results in JVM verifier errors
293(define-opcode tableswitch 170 0 nil nil)
294(define-opcode lookupswitch 171 0 nil nil)
295(define-opcode ireturn 172 1 nil nil)
296(define-opcode lreturn 173 1 nil nil)
297(define-opcode freturn 174 1 nil nil)
298(define-opcode dreturn 175 1 nil nil)
299(define-opcode ireturn 172 1 -1 nil)
300(define-opcode areturn 176 1 -1 nil)
301(define-opcode return 177 1 0 nil)
302(define-opcode getstatic 178 3 1 nil "P")
303(define-opcode putstatic 179 3 -1 nil "P")
304(define-opcode getfield 180 3 0 nil "P")
305(define-opcode putfield 181 3 -2 nil "P")
306(define-opcode invokevirtual 182 3 nil nil "P")
307(define-opcode invokespecial 183 3 nil nil "P")
308(define-opcode invokestatic 184 3 nil nil "P")
309(define-opcode invokeinterface 185 5 nil nil "P")
310(define-opcode unused 186 0 nil nil)
311(define-opcode new 187 3 1 nil "P")
312(define-opcode newarray 188 2 nil nil)
313(define-opcode anewarray 189 3 0 nil)
314(define-opcode arraylength 190 1 0 nil)
315(define-opcode athrow 191 1 0 nil)
316(define-opcode checkcast 192 3 0 nil "P")
317(define-opcode instanceof 193 3 0 nil "P")
318(define-opcode monitorenter 194 1 -1 nil)
319(define-opcode monitorexit 195 1 -1 nil)
320(define-opcode wide 196 0 nil nil)
321(define-opcode multianewarray 197 4 nil nil)
322(define-opcode ifnull 198 3 -1 nil)
323(define-opcode ifnonnull 199 3 nil nil)
324(define-opcode goto_w 200 5 nil nil)
325;; (define-opcode jsr_w 201 5 nil) Don't use: deprecated
326(define-opcode label 202 0 0 nil)  ;; virtual: does not exist in the JVM
327;; (define-opcode push-value 203 nil 1)
328;; (define-opcode store-value 204 nil -1)
329(define-opcode clear-values 205 0 0 t)  ;; virtual: does not exist in the JVM
330;;(define-opcode var-ref 206 0 0)
331
332(defparameter *last-opcode* 206)
333
334(declaim (ftype (function (t) t) opcode-name))
335(defun opcode-name (opcode-number)
336  (let ((opcode (gethash opcode-number *opcodes*)))
337    (and opcode (jvm-opcode-name opcode))))
338
339(declaim (ftype (function (t) (integer 0 255)) opcode-number))
340(defun opcode-number (opcode-name)
341  (declare (optimize speed))
342  (let ((opcode (gethash (string opcode-name) *opcodes*)))
343    (if opcode
344        (jvm-opcode-number opcode)
345        (error "Unknown opcode ~S." opcode-name))))
346
347(declaim (ftype (function (t) fixnum) opcode-size))
348(defun opcode-size (opcode-number)
349  (declare (optimize speed (safety 0)))
350  (declare (type (integer 0 255) opcode-number))
351  (jvm-opcode-size (svref *opcode-table* opcode-number)))
352
353(declaim (ftype (function (t) t) opcode-stack-effect))
354(defun opcode-stack-effect (opcode-number)
355  (declare (optimize speed))
356  (jvm-opcode-stack-effect (svref *opcode-table* opcode-number)))
357
358(defun opcode-args-spec (opcode-number)
359  (let ((opcode (gethash opcode-number *opcodes*)))
360    (and opcode (jvm-opcode-args-spec))))
361
362
363
364;;   INSTRUCTION
365
366(defstruct (instruction (:constructor %make-instruction (opcode args)))
367  (opcode 0 :type (integer 0 255))
368  args
369  stack
370  depth
371  wide)
372
373(defun make-instruction (opcode args)
374  (let ((inst (apply #'%make-instruction
375                     (list opcode
376                           (remove :wide-prefix args)))))
377    (when (memq :wide-prefix args)
378      (setf (instruction-wide inst) t))
379    inst))
380
381(defun print-instruction (instruction)
382  (sys::%format nil "~A ~A stack = ~S depth = ~S"
383          (opcode-name (instruction-opcode instruction))
384          (instruction-args instruction)
385          (instruction-stack instruction)
386          (instruction-depth instruction)))
387
388(declaim (ftype (function (t) t) instruction-label))
389(defun instruction-label (instruction)
390  (and instruction
391       (= (instruction-opcode (the instruction instruction)) 202)
392       (car (instruction-args instruction))))
393
394
395
396(defknown inst * t)
397(defun inst (instr &optional args)
398  (declare (optimize speed))
399  (let ((opcode (if (fixnump instr)
400                    instr
401                    (opcode-number instr))))
402    (unless (listp args)
403      (setf args (list args)))
404    (make-instruction opcode args)))
405
406
407;; Having %emit and %%emit output their code to *code*
408;; is currently an implementation detail exposed to all users.
409;; We need to have APIs to address this, but for now pass2 is
410;; our only user and we'll hard-code the use of *code*.
411(defvar *code* nil)
412
413(defknown %%emit * t)
414(defun %%emit (instr &rest args)
415  (declare (optimize speed))
416  (let ((instruction (make-instruction instr args)))
417    (push instruction *code*)
418    instruction))
419
420(defknown %emit * t)
421(defun %emit (instr &rest args)
422  (declare (optimize speed))
423  (let ((instruction (inst instr args)))
424    (push instruction *code*)
425    instruction))
426
427(defmacro emit (instr &rest args)
428  (when (and (consp instr)
429             (eq (car instr) 'QUOTE)
430             (symbolp (cadr instr)))
431    (setf instr (opcode-number (cadr instr))))
432  (if (fixnump instr)
433      `(%%emit ,instr ,@args)
434      `(%emit ,instr ,@args)))
435
436
437;;  Helper routines
438
439(defknown label (symbol) t)
440(defun label (symbol)
441  (declare (type symbol symbol))
442  (declare (optimize speed))
443  (emit 'label symbol)
444  (setf (symbol-value symbol) nil))
445
446(defknown aload (fixnum) t)
447(defun aload (index)
448  (case index
449    (0 (emit 'aload_0))
450    (1 (emit 'aload_1))
451    (2 (emit 'aload_2))
452    (3 (emit 'aload_3))
453    (t (emit 'aload index))))
454
455(defknown astore (fixnum) t)
456(defun astore (index)
457  (case index
458    (0 (emit 'astore_0))
459    (1 (emit 'astore_1))
460    (2 (emit 'astore_2))
461    (3 (emit 'astore_3))
462    (t (emit 'astore index))))
463
464(defknown iload (fixnum) t)
465(defun iload (index)
466  (case index
467    (0 (emit 'iload_0))
468    (1 (emit 'iload_1))
469    (2 (emit 'iload_2))
470    (3 (emit 'iload_3))
471    (t (emit 'iload index))))
472
473(defknown istore (fixnum) t)
474(defun istore (index)
475  (case index
476    (0 (emit 'istore_0))
477    (1 (emit 'istore_1))
478    (2 (emit 'istore_2))
479    (3 (emit 'istore_3))
480    (t (emit 'istore index))))
481
482(declaim (ftype (function (t) t) branch-p)
483         (inline branch-p))
484(defun branch-p (opcode)
485;;  (declare (optimize speed))
486;;  (declare (type '(integer 0 255) opcode))
487  (or (<= 153 opcode 167)
488      (<= 198 opcode 200))) ;; ifnull / ifnonnull / goto_w
489
490(declaim (ftype (function (t) t) unconditional-control-transfer-p)
491         (inline unconditional-control-transfer-p))
492(defun unconditional-control-transfer-p (opcode)
493  (or (= 167 opcode) ;; goto
494      (= 200 opcode) ;; goto_w
495      (<= 172 opcode 177) ;; ?return
496      (= 191 opcode) ;; athrow
497      ))
498
499(declaim (ftype (function (t) boolean) label-p)
500         (inline label-p))
501(defun label-p (instruction)
502  (and instruction
503       (= (the fixnum (instruction-opcode (the instruction instruction))) 202)))
504
505(defun constant-pool-index (instruction)
506  "If an instruction references an item in the constant pool, return
507   the index, otherwise return nil."
508  ;; 1 byte index
509  ;; 18 ldc
510  ;;
511  ;; 2 byte index
512  ;; 178 getstatic
513  ;; 179 putstatic
514  ;; 180 getfield
515  ;; 181 putfield
516  ;; 182 invokevirtual
517  ;; 183 invokespecial
518  ;; 184 invokestatic
519  ;; 185 invokeinterface
520  ;; 187 new
521  ;; 192 checkcast
522  ;; 193 instanceof
523  (when instruction
524    (case (instruction-opcode instruction)
525      (18 (first (instruction-args instruction)))
526      ((19 20 178 179 180 181 182 183 184 185 187 192 193)
527       (logior
528        (ash (first (instruction-args instruction)) 8)
529        (second (instruction-args instruction)))))))
530
531(defun format-instruction-args (instruction pool)
532  (let* ((*print-readably* nil)
533         (*print-escape* nil)
534         (pool-index (constant-pool-index instruction))
535         (entry (when pool-index
536                  (find-pool-entry pool pool-index))))
537    (when entry
538      (return-from
539       format-instruction-args
540        (with-output-to-string (s)
541          (print-pool-constant pool
542                               entry
543                               s
544                               :package "org/armedbear/lisp")))))
545  (when (instruction-args instruction)
546    (format nil "~S" (instruction-args instruction))))
547
548(defun print-code (code pool)
549  (declare (ignorable pool))
550  (dotimes (i (length code))
551    (let ((instruction (elt code i)))
552      (format t "~3D ~A ~19T~A ~@[IStack: ~A~] ~@[IDepth: ~A~]~%"
553                    i
554                    (opcode-name (instruction-opcode instruction))
555                    (or (format-instruction-args instruction pool) "")
556                    (instruction-stack instruction)
557                    (instruction-depth instruction)))))
558
559(defun print-code2 (code pool)
560  (declare (ignorable pool))
561  (dotimes (i (length code))
562    (let ((instruction (elt code i)))
563      (case (instruction-opcode instruction)
564        (202 ; LABEL
565         (format t "~A:~%" (car (instruction-args instruction))))
566        (t
567         (format t "~8D:   ~A ~S~%"
568                 i
569                 (opcode-name (instruction-opcode instruction))
570                 (instruction-args instruction)))))))
571
572(defun expand-virtual-instructions (code)
573  (let* ((len (length code))
574         (vector (make-array (ash len 1) :fill-pointer 0 :adjustable t)))
575    (dotimes (index len vector)
576      (declare (type (unsigned-byte 16) index))
577      (let ((instruction (svref code index)))
578        (case (instruction-opcode instruction)
579          (205 ; CLEAR-VALUES
580           (dolist (instruction
581                     (list
582                      (inst 'aload (car (instruction-args instruction)))
583                      (inst 'aconst_null)
584                      (inst 'putfield (list (pool-field +lisp-thread+ "_values"
585                                                        +lisp-object-array+)))))
586             (vector-push-extend instruction vector)))
587          (t
588           (vector-push-extend instruction vector)))))))
589
590
591;;   RESOLVERS
592
593(defun unsupported-opcode (instruction)
594  (error "Unsupported opcode ~D." (instruction-opcode instruction)))
595
596(declaim (type hash-table +resolvers+))
597(defconst +resolvers+ (make-hash-table))
598
599(defun initialize-resolvers ()
600  (let ((ht +resolvers+))
601    (dotimes (n (1+ *last-opcode*))
602      (setf (gethash n ht) #'unsupported-opcode))
603    ;; The following opcodes resolve to themselves.
604    (dolist (n '(0 ; nop
605                 1 ; aconst_null
606                 2 ; iconst_m1
607                 3 ; iconst_0
608                 4 ; iconst_1
609                 5 ; iconst_2
610                 6 ; iconst_3
611                 7 ; iconst_4
612                 8 ; iconst_5
613                 9 ; lconst_0
614                 10 ; lconst_1
615                 11 ; fconst_0
616                 12 ; fconst_1
617                 13 ; fconst_2
618                 14 ; dconst_0
619                 15 ; dconst_1
620                 26 ; iload_0
621                 27 ; iload_1
622                 28 ; iload_2
623                 29 ; iload_3
624                 42 ; aload_0
625                 43 ; aload_1
626                 44 ; aload_2
627                 45 ; aload_3
628                 46 ; iaload
629                 47 ; laload
630                 48 ; faload
631                 49 ; daload
632                 50 ; aaload
633                 54 ; istore
634                 59 ; istore_0
635                 60 ; istore_1
636                 61 ; istore_2
637                 62 ; istore_3
638                 75 ; astore_0
639                 76 ; astore_1
640                 77 ; astore_2
641                 78 ; astore_3
642                 79 ; iastore
643                 80 ; lastore
644                 81 ; fastore
645                 82 ; dastore
646                 83 ; aastore
647                 87 ; pop
648                 88 ; pop2
649                 89 ; dup
650                 90 ; dup_x1
651                 91 ; dup_x2
652                 92 ; dup2
653                 93 ; dup2_x1
654                 94 ; dup2_x2
655                 95 ; swap
656                 96 ; iadd
657                 97 ; ladd
658                 98 ; fadd
659                 99 ; dadd
660                 100 ; isub
661                 101 ; lsub
662                 102 ; fsub
663                 103 ; dsub
664                 104 ; imul
665                 105 ; lmul
666                 106 ; fmul
667                 107 ; dmul
668                 116 ; ineg
669                 117 ; lneg
670                 118 ; fneg
671                 119 ; dneg
672                 120 ; ishl
673                 121 ; lshl
674                 122 ; ishr
675                 123 ; lshr
676                 126 ; iand
677                 127 ; land
678                 128 ; ior
679                 129 ; lor
680                 130 ; ixor
681                 131 ; lxor
682                 133 ; i2l
683                 134 ; i2f
684                 135 ; i2d
685                 136 ; l2i
686                 137 ; l2f
687                 138 ; l2d
688                 141 ; f2d
689                 144 ; d2f
690                 148 ; lcmp
691                 149 ; fcmpd
692                 150 ; fcmpg
693                 151 ; dcmpd
694                 152 ; dcmpg
695                 153 ; ifeq
696                 154 ; ifne
697                 155 ; ifge
698                 156 ; ifgt
699                 157 ; ifgt
700                 158 ; ifle
701                 159 ; if_icmpeq
702                 160 ; if_icmpne
703                 161 ; if_icmplt
704                 162 ; if_icmpge
705                 163 ; if_icmpgt
706                 164 ; if_icmple
707                 165 ; if_acmpeq
708                 166 ; if_acmpne
709                 167 ; goto
710                 172 ; ireturn
711                 176 ; areturn
712                 177 ; return
713                 189 ; anewarray
714                 190 ; arraylength
715                 191 ; athrow
716                 194 ; monitorenter
717                 195 ; monitorexit
718                 198 ; ifnull
719                 202 ; label
720                 ))
721      (setf (gethash n ht) nil))))
722
723(initialize-resolvers)
724
725(defmacro define-resolver (opcodes args &body body)
726  (let ((name (gensym)))
727    `(progn
728       (defun ,name ,args ,@body)
729       (eval-when (:load-toplevel :execute)
730         ,(if (listp opcodes)
731              `(dolist (op ',opcodes)
732                 (setf (gethash op +resolvers+)
733                       (symbol-function ',name)))
734              `(setf (gethash ,opcodes +resolvers+)
735                     (symbol-function ',name)))))))
736
737(defun load/store-resolver (instruction inst-index inst-index2 error-text)
738 (let* ((args (instruction-args instruction))
739        (index (car args)))
740   (declare (type (unsigned-byte 16) index))
741   (cond ((<= 0 index 3)
742          ;; use the offset for aload<n>, iload<n>. 

743          (inst (+ index inst-index)))
744         ((<= 0 index 255)
745          (inst inst-index2 index))
746         ((<= 256 index 65535)
747          (inst inst-index2
748                `(,@(u2 index)
749                  :wide-prefix)))
750         (t
751          (error error-text)))))
752
753;; aload
754(define-resolver 25 (instruction)
755  (load/store-resolver instruction 42 25 "ALOAD unsupported case"))
756
757;; astore
758(define-resolver 58 (instruction)
759  (load/store-resolver instruction 75 58 "ASTORE unsupported case"))
760
761
762;; iload
763(define-resolver 21 (instruction)
764  (load/store-resolver instruction 26 21 "ILOAD unsupported case"))
765
766;; istore
767(define-resolver 54 (instruction)
768  (load/store-resolver instruction 59 54 "ISTORE unsupported case"))
769
770;; lload
771(define-resolver 22 (instruction)
772  (load/store-resolver instruction 30 22 "LLOAD unsupported case"))
773
774;; lstore
775(define-resolver 55 (instruction)
776  (load/store-resolver instruction 63 55 "LSTORE unsupported case"))
777
778;; bipush, sipush
779(define-resolver (16 17) (instruction)
780  (let* ((args (instruction-args instruction))
781         (n (first args)))
782    (declare (type fixnum n))
783    (cond ((<= 0 n 5)
784           (inst (+ n 3)))
785          ((<= -128 n 127)
786           (inst 16 (logand n #xff))) ; BIPUSH
787          (t ; SIPUSH
788           (inst 17 (s2 n))))))
789
790;; ldc
791(define-resolver 18 (instruction)
792  (let* ((args (instruction-args instruction)))
793    (unless (= (length args) 1)
794      (error "Wrong number of args for LDC."))
795    (if (> (car args) 255)
796        (inst 19 (u2 (car args))) ; LDC_W
797        (inst 18 args))))
798
799;; ldc_w
800(define-resolver 19 (instruction)
801  (let* ((args (instruction-args instruction)))
802    (unless (= (length args) 1)
803      (error "Wrong number of args for LDC_W."))
804    (inst 19 (u2 (car args)))))
805
806;; ldc2_w
807(define-resolver 20 (instruction)
808  (let* ((args (instruction-args instruction)))
809    (unless (= (length args) 1)
810      (error "Wrong number of args for LDC2_W."))
811    (inst 20 (u2 (car args)))))
812
813;; iinc
814(define-resolver 132 (instruction)
815  (let* ((args (instruction-args instruction))
816         (register (first args))
817         (n (second args)))
818    (when (not (<= -128 n 127))
819      (error "IINC argument ~A out of bounds." n))
820    (inst 132 (list register (s1 n)))))
821
822(define-resolver (178 179 180 181 182 183 184 185 192 193 187)
823    (instruction)
824  (let* ((arg (car (instruction-args instruction))))
825    (setf (instruction-args instruction)
826          (u2 arg))
827    instruction))
828
829(defknown resolve-instruction (t) t)
830(defun resolve-instruction (instruction)
831  (declare (optimize speed))
832  (let ((resolver (gethash1 (instruction-opcode instruction) +resolvers+)))
833    (if resolver
834        (funcall resolver instruction)
835        instruction)))
836
837(defun resolve-instructions (code)
838  (let* ((len (length code))
839         (vector (make-array len :fill-pointer 0 :adjustable t)))
840    (dotimes (index len vector)
841      (declare (type (unsigned-byte 16) index))
842      (let ((instruction (aref code index)))
843        (vector-push-extend (resolve-instruction instruction) vector)))))
844
845
846
847;; BYTE CODE ANALYSIS AND OPTIMIZATION
848
849(declaim (ftype (function (t t t) t) analyze-stack-path))
850(defun analyze-stack-path (code start-index depth)
851  (declare (optimize speed))
852  (declare (type fixnum start-index depth))
853  (do* ((i start-index (1+ i))
854        (limit (length code)))
855       ((>= i limit))
856    (declare (type fixnum i limit))
857    (let* ((instruction (aref code i))
858           (instruction-depth (instruction-depth instruction))
859           (instruction-stack (instruction-stack instruction)))
860      (declare (type fixnum instruction-stack))
861      (when instruction-depth
862        (unless (= (the fixnum instruction-depth)
863                   (the fixnum (+ depth instruction-stack)))
864          (internal-compiler-error "Stack inconsistency detected ~
865                                    in ~A at index ~D: ~
866                                    found ~S, expected ~S."
867                                   (if *current-compiland*
868                                       (compiland-name *current-compiland*)
869                                       "<unknown>")
870                                   i instruction-depth
871                                   (+ depth instruction-stack)))
872        (return-from analyze-stack-path))
873      (let ((opcode (instruction-opcode instruction)))
874        (setf depth (+ depth instruction-stack))
875        (setf (instruction-depth instruction) depth)
876        (unless (<= 0 depth)
877          (internal-compiler-error "Stack inconsistency detected ~
878                                    in ~A at index ~D: ~
879                                    negative depth ~S."
880                                   (if *current-compiland*
881                                       (compiland-name *current-compiland*)
882                                       "<unknown>")
883                                   i depth))
884        (when (branch-p opcode)
885          (let ((label (car (instruction-args instruction))))
886            (declare (type symbol label))
887            (analyze-stack-path code (symbol-value label) depth)))
888        (when (unconditional-control-transfer-p opcode)
889          ;; Current path ends.
890          (return-from analyze-stack-path))))))
891
892(declaim (ftype (function (t) t) analyze-stack))
893(defun analyze-stack (code exception-entry-points)
894  (declare (optimize speed))
895  ;;(print-code code *pool*)
896  (let* ((code-length (length code)))
897    (declare (type vector code))
898    (dotimes (i code-length)
899      (let* ((instruction (aref code i))
900             (opcode (instruction-opcode instruction)))
901        (when (eql opcode 202) ; LABEL
902          (let ((label (car (instruction-args instruction))))
903            (set label i)))
904        (unless (instruction-stack instruction)
905          (setf (instruction-stack instruction)
906                (opcode-stack-effect opcode))
907          (unless (instruction-stack instruction)
908            (sys::%format t "no stack information for instruction ~D~%"
909                          (instruction-opcode instruction))
910            (aver nil)))))
911    (analyze-stack-path code 0 0)
912    (dolist (entry-point exception-entry-points)
913      ;; Stack depth is always 1 when handler is called.
914      (analyze-stack-path code (symbol-value entry-point) 1))
915    (let ((max-stack 0))
916      (declare (type fixnum max-stack))
917      (dotimes (i code-length)
918        (let* ((instruction (aref code i))
919               (instruction-depth (instruction-depth instruction)))
920          (when instruction-depth
921            (setf max-stack (max max-stack (the fixnum instruction-depth))))))
922      max-stack)))
923
924(defun analyze-locals (code)
925  (let ((code-length (length code))
926        (max-local 0))
927    (dotimes (i code-length max-local)
928      (let* ((instruction (aref code i))
929             (opcode (instruction-opcode instruction)))
930        (setf max-local
931              (max max-local
932                   (or (let ((opcode-register
933                                (jvm-opcode-register-used opcode)))
934                         (if (eq t opcode-register)
935                             (car (instruction-args instruction))
936                             opcode-register))
937                       0)))))))
938
939(defun delete-unused-labels (code handler-labels)
940  (declare (optimize speed))
941  (let ((code (coerce code 'vector))
942        (changed nil)
943        (marker (gensym)))
944    ;; Mark the labels that are actually branched to.
945    (dotimes (i (length code))
946      (let ((instruction (aref code i)))
947        (when (branch-p (instruction-opcode instruction))
948          (let ((label (car (instruction-args instruction))))
949            (set label marker)))))
950    ;; Add labels used for exception handlers.
951    (dolist (label handler-labels)
952      (set label marker))
953    ;; Remove labels that are not used as branch targets.
954    (dotimes (i (length code))
955      (let ((instruction (aref code i)))
956        (when (= (instruction-opcode instruction) 202) ; LABEL
957          (let ((label (car (instruction-args instruction))))
958            (declare (type symbol label))
959            (unless (eq (symbol-value label) marker)
960              (setf (aref code i) nil)
961              (setf changed t))))))
962    (values (if changed (delete nil code) code)
963            changed)))
964
965(defun delete-unreachable-code (code)
966  ;; Look for unreachable code after GOTO.
967  (declare (optimize speed))
968  (let* ((code (coerce code 'vector))
969         (changed nil)
970         (after-goto/areturn nil))
971    (dotimes (i (length code))
972      (declare (type (unsigned-byte 16) i))
973      (let* ((instruction (aref code i))
974             (opcode (instruction-opcode instruction)))
975        (cond (after-goto/areturn
976               (if (= opcode 202) ; LABEL
977                   (setf after-goto/areturn nil)
978                   ;; Unreachable.
979                   (progn
980                     (setf (aref code i) nil)
981                     (setf changed t))))
982              ((unconditional-control-transfer-p opcode)
983               (setf after-goto/areturn t)))))
984    (values (if changed (delete nil code) code)
985            changed)))
986
987
988(declaim (ftype (function (t) label-target-instructions) hash-labels))
989(defun label-target-instructions (code)
990  (let ((ht (make-hash-table :test 'eq))
991        (code (coerce code 'vector))
992        (pending-labels '()))
993    (dotimes (i (length code))
994      (let ((instruction (aref code i)))
995        (cond ((label-p instruction)
996               (push (instruction-label instruction) pending-labels))
997              (t
998               ;; Not a label.
999               (when pending-labels
1000                 (dolist (label pending-labels)
1001                   (setf (gethash label ht) instruction))
1002                 (setf pending-labels nil))))))
1003    ht))
1004
1005(defun optimize-jumps (code)
1006  (declare (optimize speed))
1007  (let* ((code (coerce code 'vector))
1008         (ht (label-target-instructions code))
1009         (changed nil))
1010    (dotimes (i (length code))
1011      (let* ((instruction (aref code i))
1012             (opcode (and instruction (instruction-opcode instruction))))
1013        (when (and opcode (branch-p opcode))
1014          (let* ((target-label (car (instruction-args instruction)))
1015                 (next-instruction (gethash1 target-label ht)))
1016            (when next-instruction
1017              (case (instruction-opcode next-instruction)
1018                ((167 200)                  ;; GOTO
1019                 (setf (instruction-args instruction)
1020                       (instruction-args next-instruction)
1021                       changed t))
1022                (176 ; ARETURN
1023                 (when (unconditional-control-transfer-p opcode)
1024                   (setf (instruction-opcode instruction) 176
1025                         (instruction-args instruction) nil
1026                         changed t)))))))))
1027    (values code changed)))
1028
1029
1030(defun optimize-instruction-sequences (code)
1031  (let* ((code (coerce code 'vector))
1032         (changed nil))
1033    (dotimes (i (1- (length code)))
1034      (let* ((this-instruction (aref code i))
1035             (this-opcode (and this-instruction
1036                               (instruction-opcode this-instruction)))
1037             (labels-skipped-p nil)
1038             (next-instruction (do ((j (1+ i) (1+ j)))
1039                                   ((or (>= j (length code))
1040                                        (/= 202 ; LABEL
1041                                            (instruction-opcode (aref code j))))
1042                                    (when (< j (length code))
1043                                      (aref code j)))
1044                                 (setf labels-skipped-p t)))
1045             (next-opcode (and next-instruction
1046                               (instruction-opcode next-instruction))))
1047        (case this-opcode
1048          (205 ; CLEAR-VALUES
1049           (when (eql next-opcode 205)       ; CLEAR-VALUES
1050             (setf (aref code i) nil)
1051             (setf changed t)))
1052          (178 ; GETSTATIC
1053           (when (and (eql next-opcode 87)   ; POP
1054                      (not labels-skipped-p))
1055             (setf (aref code i) nil)
1056             (setf (aref code (1+ i)) nil)
1057             (setf changed t)))
1058          (176 ; ARETURN
1059           (when (eql next-opcode 176)       ; ARETURN
1060             (setf (aref code i) nil)
1061             (setf changed t)))
1062          ((200 167)                         ; GOTO GOTO_W
1063           (when (and (or (eql next-opcode 202)  ; LABEL
1064                          (eql next-opcode 200)  ; GOTO_W
1065                          (eql next-opcode 167)) ; GOTO
1066                      (eq (car (instruction-args this-instruction))
1067                          (car (instruction-args next-instruction))))
1068             (setf (aref code i) nil)
1069             (setf changed t))))))
1070    (values (if changed (delete nil code) code)
1071            changed)))
1072
1073(defvar *enable-optimization* t)
1074
1075(defknown optimize-code (t t) t)
1076(defun optimize-code (code handler-labels pool)
1077  (unless *enable-optimization*
1078    (format t "optimizations are disabled~%"))
1079  (when *enable-optimization*
1080    (when *compiler-debug*
1081      (format t "----- before optimization -----~%")
1082      (print-code code pool))
1083    (loop
1084       (let ((changed-p nil))
1085         (multiple-value-setq
1086             (code changed-p)
1087           (delete-unused-labels code handler-labels))
1088         (if changed-p
1089             (setf code (optimize-instruction-sequences code))
1090             (multiple-value-setq
1091                 (code changed-p)
1092               (optimize-instruction-sequences code)))
1093         (if changed-p
1094             (setf code (optimize-jumps code))
1095             (multiple-value-setq
1096                 (code changed-p)
1097               (optimize-jumps code)))
1098         (if changed-p
1099             (setf code (delete-unreachable-code code))
1100             (multiple-value-setq
1101                 (code changed-p)
1102               (delete-unreachable-code code)))
1103         (unless changed-p
1104           (return))))
1105    (unless (vectorp code)
1106      (setf code (coerce code 'vector)))
1107    (when *compiler-debug*
1108      (sys::%format t "----- after optimization -----~%")
1109      (print-code code pool)))
1110  code)
1111
1112
1113
1114
1115(defun code-bytes (code)
1116  (let ((length 0)
1117        labels ;; alist
1118        )
1119    (declare (type (unsigned-byte 16) length))
1120    ;; Pass 1: calculate label offsets and overall length.
1121    (dotimes (i (length code))
1122      (declare (type (unsigned-byte 16) i))
1123      (let* ((instruction (aref code i))
1124             (opcode (instruction-opcode instruction)))
1125        (if (= opcode 202) ; LABEL
1126            (let ((label (car (instruction-args instruction))))
1127              (set label length)
1128              (setf labels
1129                    (acons label length labels)))
1130            (progn 
1131              (incf length (opcode-size opcode))
1132              ;; hacky fixup: right way forward would be to have
1133              ;; opcode size to be a function of its arguments?
1134              (when (instruction-wide instruction)
1135                (incf length 2))))))
1136    (when *compiler-debug* 
1137      (sys::%format *compiler-debug* "~&DEBUG: length for list of size ~a calculated as ~a~%"
1138                    (length code) length))
1139    ;; Pass 2: replace labels with calculated offsets.
1140    (let ((index 0))
1141      (declare (type (unsigned-byte 16) index))
1142      (dotimes (i (length code))
1143        (declare (type (unsigned-byte 16) i))
1144        (let ((instruction (aref code i)))
1145          (when (branch-p (instruction-opcode instruction))
1146            (let* ((label (car (instruction-args instruction)))
1147                   (offset (- (the (unsigned-byte 16)
1148                                (symbol-value (the symbol label)))
1149                              index)))
1150              (assert (<= -32768 offset 32767))
1151              (setf (instruction-args instruction) (s2 offset))))
1152          (unless (= (instruction-opcode instruction) 202) ; LABEL
1153            (incf index (opcode-size (instruction-opcode instruction)))
1154            (when (instruction-wide instruction)
1155              (incf index 2))))))                         
1156    ;; Expand instructions into bytes, skipping LABEL pseudo-instructions.
1157    (let ((bytes (make-array length))
1158          (index 0))
1159      (declare (type (unsigned-byte 16) index))
1160      (dotimes (i (length code))
1161        (declare (type (unsigned-byte 16) i))
1162        (let ((instruction (aref code i)))
1163          (unless (= (instruction-opcode instruction) 202) ; LABEL
1164            ;; possibly emit the wide prefix to instrument the opcode
1165            (when (instruction-wide instruction)
1166              (progn
1167                (setf (svref bytes index)
1168                      196)
1169                (incf index)))
1170            (setf (svref bytes index) (instruction-opcode instruction))
1171            (incf index)
1172            (dolist (byte (instruction-args instruction))
1173              (setf (svref bytes index) byte)
1174              (incf index)))))
1175      (values bytes labels))))
1176
1177(defun finalize-code (code handler-labels optimize pool)
1178  (setf code (coerce (nreverse code) 'vector))
1179  (when optimize
1180    (setf code (optimize-code code handler-labels pool)))
1181  (resolve-instructions (expand-virtual-instructions code)))
1182
1183(provide '#:jvm-instructions)
Note: See TracBrowser for help on using the repository browser.