32f996d8680922ae52eb8d9072947f993a628514
2 * @(#)inlinejsr.c 1.22 02/09/27
4 * Copyright 1995-2001 by Sun Microsystems, Inc.,
5 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
8 * This software is the confidential and proprietary information
9 * of Sun Microsystems, Inc. ("Confidential Information"). You
10 * shall not disclose such Confidential Information and shall use
11 * it only in accordance with the terms of the license agreement
12 * you entered into with Sun.
13 * Use is subject to license terms.
16 /*=========================================================================
18 * SUBSYSTEM: JSR inlining
20 * OVERVIEW: Routines for inlining of JSR and RET bytecodes.
22 * AUTHOR: Frank Yellin, Sun Microsystems, Inc.
23 * Edited by Tasneem Sayeed, Sun Microsystems
24 *=======================================================================*/
26 /*=========================================================================
28 *=======================================================================*/
30 #include "check_code.h"
32 /*=========================================================================
33 * Globals and extern declarations
34 *=======================================================================*/
36 /* Maximum byte code size is 64K. */
37 #define MAX_CODE_SIZE 65535
39 typedef struct SubrContext
{
40 int id
; /* id, for debugging */
41 int depth
; /* depth of subroutine */
42 struct SubrContext
*parent
; /* subroutine of caller */
43 struct CodeRef
*caller
; /* jsr that got us there */
44 struct CodeRef
*nextInstruction
; /* first instruction following inlining */
47 struct SubrContext
*next
; /* linked list of all subr contexts */
51 /* global context, keep track of info when a method is rewritten */
52 typedef struct JsrContext
{
53 context_type
*vcontext
; /* The verifier's context */
54 struct CodeRef
*codeRef
; /* big array of codeRef's */
55 struct CodeRef
*codeRefEnd
; /* pointer to next codeRef to fill in */
56 int scontext_id
; /* ID assigned to last SubrContext */
57 struct SubrContext
*allSubrContexts
; /* pointer to linked list */
58 struct CodeRef
**mapping
; /* maps inumbers CodeRef's */
61 /* A single instruction in the resulting stream */
62 typedef struct CodeRef
{
63 long inumber
; /* instruction number in original code */
64 SubrContext
*subroutine
; /* subroutine call that this is part of */
65 enum { CRF_NORMAL
, /* normal instruction */
66 CRF_SKIP
, /* skip this instruction */
67 CRF_JSR_SIMPLE_GOTO
, /* jsr to subroutine that doesn't return */
68 CRF_JSR_TARGETED_GOTO
, /* jsr to subroutine that does return */
69 CRF_RET_SIMPLE_GOTO
/* ret that's not at the end of subroutine */
71 /* My offset in the new code */
73 struct CodeRef
*next
; /* next codeRef with same "inumber" */
77 static bool_t
matchSubroutine(JsrContext
*, instruction_data_type
*,
79 static bool_t
subroutineGoto(JsrContext
*, SubrContext
*, SubrContext
*);
83 rewriteOneSubroutine(JsrContext
*context
, SubrContext
*subroutine
);
85 static void fixupCode(JsrContext
*);
86 static void fixupExceptionHandlers(JsrContext
*);
87 static void fixupLineNumberTable(JsrContext
*);
88 static void fixupVariableTable(JsrContext
*);
92 updateTarget(JsrContext
*,
94 SubrContext
* subroutine
,
95 void* target
, int offset
, int size
);
99 rewriteCode(context_type
*vcontext
, struct methodblock
*mb
)
101 JsrContext context_buf
;
102 JsrContext
*context
= &context_buf
;
105 printf("Starting %s.%s%s\n", cbName(mb
->fb
.clazz
), mb
->fb
.name
, mb
->fb
.signature
);
107 /* Initialize the context */
108 memset(context
, 0, sizeof(context
));
109 context
->vcontext
= vcontext
; /* The verifier context */
110 /* Allow up to MAX_CODE_SIZE instructions. */
111 context
->codeRef
= (CodeRef
*)malloc(MAX_CODE_SIZE
* sizeof(CodeRef
));
112 context
->codeRefEnd
= context
->codeRef
;
113 /* Id (for debugging) of last subroutine structure created */
114 context
->scontext_id
= 0;
115 /* Keep a list of all subroutines, so that we can easily free() them */
116 context
->allSubrContexts
= NULL
;
117 /* Make it easy to go from inumber to all CodeRef's that have that inumber*/
118 context
->mapping
= (CodeRef
**)calloc(vcontext
->instruction_count
,
121 /* Fill in context->codeRef with this routine. In line all subroutine
122 * calls, and delete all unreachable code */
123 rewriteOneSubroutine(context
, NULL
);
125 /* Modify mb->code and mb->code_length for the new code */
128 /* Update the exception table */
129 if (mb
->exception_table_length
!= 0) {
130 fixupExceptionHandlers(context
);
133 /* Update the line number table */
134 if (mb
->line_number_table_length
!= 0) {
135 fixupLineNumberTable(context
);
138 /* Update the local variable table */
139 if (mb
->localvar_table_length
!= 0) {
140 fixupVariableTable(context
);
144 free(context
->codeRef
);
145 free(context
->mapping
);
147 /* Free all the subroutine contexts that we created */
148 while (context
->allSubrContexts
!= NULL
) {
149 SubrContext
*this = context
->allSubrContexts
;
150 SubrContext
*next
= this->next
;
152 context
->allSubrContexts
= next
;
157 rewriteOneSubroutine(JsrContext
*context
, SubrContext
*subroutine
)
159 context_type
*vcontext
= context
->vcontext
;
160 int depth
= subroutine
? subroutine
->depth
: 0;
161 instruction_data_type
*idata
= vcontext
->instruction_data
;
162 int instruction_count
= vcontext
->instruction_count
;
163 CodeRef
**mapping
= context
->mapping
;
165 instruction_data_type
*this_idata
;
168 CodeRef
*retOpcode
= NULL
;
171 for ( inumber
= 0, this_idata
= idata
;
172 inumber
< instruction_count
;
173 inumber
++, this_idata
++) {
174 if ( (this_idata
->or_flags
& FLAG_REACHED
)
175 && (this_idata
->register_info
.mask_count
== depth
)
177 || matchSubroutine(context
, this_idata
, subroutine
))) {
179 /* We have an instruction that is part of this subroutine */
181 CodeRef
*codeRef
= context
->codeRefEnd
++;
183 printf("\t%d:\t%d (%d)\t%s (%d)\n",
184 (codeRef
- context
->codeRef
), /* new instruction index */
185 inumber
, (subroutine
? subroutine
->id
: 0),
186 (this_idata
->opcode
== 256
187 ? "invokeinit" : opnames
[this_idata
->opcode
]),
190 codeRef
->inumber
= inumber
;
191 codeRef
->subroutine
= subroutine
;
192 codeRef
->flags
= CRF_NORMAL
;
193 codeRef
->next
= mapping
[inumber
]; /* Add to inumber mapping */
194 mapping
[inumber
] = codeRef
;
198 if (count
== 1 && depth
> 0) {
199 /* This is the first instruction included as part of the
200 * subroutine call. If it's the target of the jsr that got
201 * us here, then we can just "ignore" the jsr.
202 * Otherwise, we have to convert the 'jsr' into a 'goto'
204 CodeRef
*caller
= subroutine
->caller
;
205 if (inumber
!= idata
[caller
->inumber
].operand
.i
) {
206 caller
->flags
= CRF_JSR_TARGETED_GOTO
;
210 switch(this_idata
->opcode
) {
211 case opc_jsr
: case opc_jsr_w
:
212 if (this_idata
->operand2
.i
== UNKNOWN_RET_INSTRUCTION
) {
213 /* We're calling a subroutine that doesn't return.
214 * The verifier has already made sure that the
215 * subroutine doesn't have a deeper depth.
216 * We turn the JSR into a goto */
217 codeRef
->flags
= CRF_JSR_SIMPLE_GOTO
;
219 SubrContext
*newSubr
= malloc(sizeof(SubrContext
));
221 /* In rare cases, we'll have to change this in the
223 codeRef
->flags
= CRF_SKIP
;
225 /* Create a new subroutine, and inline it */
226 newSubr
->id
= ++context
->scontext_id
;
227 newSubr
->caller
= codeRef
;
228 newSubr
->target
= this_idata
->operand
.i
;
229 newSubr
->depth
= depth
+ 1;
230 newSubr
->nextInstruction
= NULL
; /* unknown for now */
231 newSubr
->parent
= subroutine
;
232 /* Add this to the list of all subroutine contexts */
233 newSubr
->next
= context
->allSubrContexts
;
234 context
->allSubrContexts
= newSubr
;
235 /* Generate the code for this subroutine */
236 rewriteOneSubroutine(context
, newSubr
);
241 if (retOpcode
!= NULL
) {
242 /* There should only be one per subroutine */
243 panic("Multiple return opcodes??");
244 } else if (depth
== 0) {
245 /* We're not in a subroutine */
246 panic("Ret at depth = 0");
249 /* Flags are set at the end of the loop, below */
253 /* We discard any astore's that move a return address
254 * from the stack to a register.
256 if (GET_ITEM_TYPE(this_idata
->stack_info
.stack
->item
)
257 == ITEM_ReturnAddress
) {
258 codeRef
->flags
= CRF_SKIP
;
269 subroutine
->nextInstruction
= context
->codeRefEnd
;
270 if (retOpcode
!= NULL
) {
271 /* If the last instruction wasn't a 'ret', then we need to
272 * convert the 'ret' into a 'goto'.
274 if (context
->codeRefEnd
== retOpcode
+ 1) {
275 retOpcode
->flags
= CRF_SKIP
;
277 retOpcode
->flags
= CRF_RET_SIMPLE_GOTO
;
285 fixupCode(JsrContext
*context
)
287 context_type
*vcontext
= context
->vcontext
;
288 instruction_data_type
*idata
= vcontext
->instruction_data
;
289 struct methodblock
*mb
= vcontext
->mb
;
290 unsigned char *oldCode
= mb
->code
;
291 CodeRef
*codeRefEnd
= context
->codeRefEnd
;
293 unsigned char *newCode
;
298 /* Assign offsets to each instruction. */
300 printf("Assigning offsets\n");
302 for (pc
= 0, codeRef
= context
->codeRef
; codeRef
< codeRefEnd
; codeRef
++) {
303 instruction_data_type
*this_idata
= &idata
[codeRef
->inumber
];
304 opcode_type opcode
= this_idata
->opcode
;
306 codeRef
->offset
= pc
;
309 printf("\t%d:\t%d\tpc=%d\t%s (%d) %s\n",
310 (codeRef
- context
->codeRef
),
311 (this_idata
- vcontext
->instruction_data
),
313 (this_idata
->opcode
== 256
314 ? "invokeinit" : opnames
[this_idata
->opcode
]),
316 ((codeRef
->flags
== CRF_SKIP
) ? " XX" : "")
320 /* Now increment the pc, depending on the instruction */
321 if (codeRef
->flags
== CRF_SKIP
) {
323 } else if (opcode
== opc_tableswitch
|| opcode
== opc_lookupswitch
) {
324 /* This mysterious calculation works.
325 * The first term increments pc and then rounds it up to a
326 * multiple of 4. The second term is the size of the word-aligned
329 pc
= ((pc
+ 1 + 3) & ~3) + ((this_idata
->length
- 1) & ~3);
330 } else if (opcode
== opc_ret
) {
331 /* We must be turning it into an opc_goto */
334 pc
+= this_idata
->length
;
338 /* Create a new code object */
339 newCode
= (unsigned char *)malloc(pc
);
343 printf("Creating code of length %d\n", pc
);
346 for (codeRef
= context
->codeRef
; codeRef
< codeRefEnd
; codeRef
++) {
347 if (codeRef
->flags
!= CRF_SKIP
) {
348 instruction_data_type
*this_idata
= &idata
[codeRef
->inumber
];
349 opcode_type opcode
= this_idata
->opcode
;
350 int pc
= codeRef
->offset
;
351 unsigned char *source
= &oldCode
[this_idata
->offset
];
352 unsigned char *target
= &newCode
[pc
];
355 printf("\t%d:\t%d\tpc=%d\t%s (%d) \n",
356 (codeRef
- context
->codeRef
),
357 (this_idata
- vcontext
->instruction_data
),
359 (this_idata
->opcode
== 256
360 ? "invokeinit" : opnames
[this_idata
->opcode
]),
366 case opc_ifeq
: case opc_ifne
: case opc_iflt
:
367 case opc_ifge
: case opc_ifgt
: case opc_ifle
:
368 case opc_ifnull
: case opc_ifnonnull
:
369 case opc_if_icmpeq
: case opc_if_icmpne
: case opc_if_icmplt
:
370 case opc_if_icmpge
: case opc_if_icmpgt
: case opc_if_icmple
:
371 case opc_if_acmpeq
: case opc_if_acmpne
:
372 case opc_goto
: case opc_goto_w
:
373 target
[0] = source
[0];
374 updateTarget(context
, this_idata
->operand
.i
,
376 target
+ 1, pc
, this_idata
->length
- 1);
379 case opc_jsr
: case opc_jsr_w
:
380 target
[0] = opc_goto
;
381 if (codeRef
->flags
== CRF_JSR_SIMPLE_GOTO
) {
382 updateTarget(context
, this_idata
->operand
.i
,
384 target
+ 1, pc
, this_idata
->length
- 1);
385 } else if (codeRef
->flags
== CRF_JSR_TARGETED_GOTO
) {
386 updateTarget(context
, this_idata
->operand
.i
,
387 codeRef
[1].subroutine
,
388 target
+ 1, pc
, this_idata
->length
- 1);
390 panic("Shouldn't have anything referring to jsr");
395 if (codeRef
->flags
& CRF_RET_SIMPLE_GOTO
) {
397 codeRef
->subroutine
->nextInstruction
->offset
;
398 target
[0] = opc_goto
;
399 target
[1] = (gotoTarget
- pc
) >> 8;
400 target
[2] = (gotoTarget
- pc
);
402 panic("Shouldn't have anything referring to ret");
407 memcpy(target
, source
, this_idata
->length
);
411 case opc_tableswitch
:
412 case opc_lookupswitch
: {
413 int *successors
= this_idata
->operand
.ip
;
414 int keys
= successors
[0] - 1; /* don't include default */
415 SubrContext
*subroutine
= codeRef
->subroutine
;
418 long *targetPtr
, *sourcePtr
;
419 target
[0] = source
[0];
420 target
[1] = target
[2] = target
[3] = 0; /* clear alignment */
422 targetPtr
= (long *)UCALIGN(target
+ 1);
423 sourcePtr
= (long *)UCALIGN(source
+ 1);
425 /* Update the default target */
426 updateTarget(context
, successors
[1], subroutine
,
428 if (opcode
== opc_tableswitch
) {
429 targetPtr
[1] = sourcePtr
[1]; /* low */
430 targetPtr
[2] = sourcePtr
[2]; /* high */
431 for (i
= 0; i
< keys
; i
++) {
432 updateTarget(context
, successors
[2 + i
], subroutine
,
433 &targetPtr
[3 + i
], pc
, 4);
436 targetPtr
[1] = sourcePtr
[1]; /* pairs */
437 for (i
= 0; i
< keys
; i
++) {
438 targetPtr
[2 + (i
<< 1)] = sourcePtr
[2 + (i
<< 1)];
439 updateTarget(context
, successors
[2 + i
], subroutine
,
440 &targetPtr
[3 + (i
<< 1)], pc
, 4);
450 mb
->code_length
= newCodeLength
;
453 static void fixupExceptionHandlers(JsrContext
*context
) {
454 const int catchFrameSize
= sizeof(struct CatchFrame
);
455 context_type
*vcontext
= context
->vcontext
;
456 struct methodblock
*mb
= vcontext
->mb
;
458 short *code_data
= vcontext
->code_data
; /* maps offset to inumber */
460 CodeRef
*codeRefEnd
= context
->codeRefEnd
;
462 /* Structure to hold new catch frames */
463 struct CatchFrame
*catchFrames
= malloc(catchFrameSize
* MAX_CODE_SIZE
);
464 struct CatchFrame
*currentCatchFrame
= catchFrames
;
466 CodeRef
*hRef
, *instRef
;
469 /* Look at each exception handler */
470 for (i
= 0; i
< mb
->exception_table_length
; i
++) {
471 struct CatchFrame
*this_handler
= &mb
->exception_table
[i
];
472 int start_inumber
= code_data
[this_handler
->start_pc
];
473 int end_inumber
= code_data
[this_handler
->end_pc
];
474 int handler_inumber
= code_data
[this_handler
->handler_pc
];
476 /* First instruction that maps to the specified handler */
477 for (hRef
= context
->mapping
[handler_inumber
]
478 ; hRef
!= NULL
; hRef
= hRef
->next
) {
479 /* Find all instructions that go to this handler. */
480 bool_t wasMatch
= FALSE
;
481 for (instRef
= context
->codeRef
; instRef
< codeRefEnd
; instRef
++) {
482 if (instRef
->flags
!= CRF_SKIP
) {
483 bool_t thisMatch
= instRef
->inumber
>= start_inumber
484 && instRef
->inumber
< end_inumber
485 && subroutineGoto(context
,
488 if (thisMatch
&& !wasMatch
) {
489 /* Start a new catch frame */
490 memcpy(currentCatchFrame
, this_handler
, catchFrameSize
);
491 currentCatchFrame
->handler_pc
= hRef
->offset
;
492 currentCatchFrame
->start_pc
= instRef
->offset
;
494 } else if (wasMatch
&& !thisMatch
) {
495 currentCatchFrame
->end_pc
= instRef
->offset
;
502 /* We end the code still in the catch frame */
503 currentCatchFrame
->end_pc
= mb
->code_length
;
508 /* free(mb->exception_table); */
509 mb
->exception_table_length
= currentCatchFrame
- catchFrames
;
510 mb
->exception_table
= realloc(catchFrames
,
511 (char *)currentCatchFrame
- (char *)catchFrames
);
515 static void fixupLineNumberTable(JsrContext
*context
) {
516 context_type
*vcontext
= context
->vcontext
;
517 struct methodblock
*mb
= vcontext
->mb
;
518 int tableLength
= mb
->line_number_table_length
;
520 instruction_data_type
*idata
= vcontext
->instruction_data
;
521 instruction_data_type
*last_idata
= &idata
[vcontext
->instruction_count
- 1];
522 int oldCodeLength
= last_idata
->offset
+ last_idata
->length
;
523 struct lineno
*lineTable
= malloc(sizeof(struct lineno
) * MAX_CODE_SIZE
);
524 struct lineno
*currentLineTableEntry
= lineTable
;
525 unsigned long *mapTable
= calloc(sizeof(short *), oldCodeLength
);
526 CodeRef
*codeRefEnd
= context
->codeRefEnd
;
528 int i
, currentLineNumber
;
531 unsigned long startPC
, endPC
, line
, pc
;
533 for (i
= 0; i
< tableLength
- 1; i
++) {
534 startPC
= mb
->line_number_table
[i
].pc
;
535 endPC
= mb
->line_number_table
[i
+ 1].pc
;
536 line
= mb
->line_number_table
[i
].line_number
;
537 for (pc
= startPC
; pc
< endPC
; pc
++) {
541 startPC
= mb
->line_number_table
[tableLength
- 1].pc
;
542 endPC
= oldCodeLength
;
543 line
= mb
->line_number_table
[tableLength
- 1].line_number
;
544 for (pc
= startPC
; pc
< endPC
; pc
++) {
549 currentLineNumber
= -1;
550 for (codeRef
= context
->codeRef
; codeRef
< codeRefEnd
; codeRef
++) {
551 if (codeRef
->flags
!= CRF_SKIP
) {
552 instruction_data_type
*this_idata
= &idata
[codeRef
->inumber
];
553 int thisLineNumber
= mapTable
[this_idata
->offset
];
554 if (thisLineNumber
!= currentLineNumber
) {
555 currentLineTableEntry
->line_number
= thisLineNumber
;
556 currentLineTableEntry
->pc
= codeRef
->offset
;
557 currentLineTableEntry
++;
558 currentLineNumber
= thisLineNumber
;
564 mb
->line_number_table
= realloc(lineTable
,
565 (char *)currentLineTableEntry
-
567 mb
->line_number_table_length
= currentLineTableEntry
- lineTable
;
571 static void fixupVariableTable(JsrContext
*context
) {
572 context_type
*vcontext
= context
->vcontext
;
573 struct methodblock
*mb
= context
->vcontext
->mb
;
574 instruction_data_type
*idata
= vcontext
->instruction_data
;
575 CodeRef
*codeRefEnd
= context
->codeRefEnd
;
579 struct localvar
*localVars
=
580 malloc(sizeof(struct localvar
) * MAX_CODE_SIZE
);
581 struct localvar
*currentLocalVar
= localVars
;
583 for (i
= 0; i
< mb
->localvar_table_length
; i
++) {
584 struct localvar
*oldEntry
= &mb
->localvar_table
[i
];
585 int startPC
= oldEntry
->pc0
;
586 int endPC
= startPC
+ oldEntry
->length
; /* inclusive! */
588 bool_t was_matching
= FALSE
;
590 for (codeRef
= context
->codeRef
; codeRef
< codeRefEnd
; codeRef
++) {
591 if (codeRef
->flags
!= CRF_SKIP
) {
592 instruction_data_type
*this_idata
= &idata
[codeRef
->inumber
];
593 bool_t is_matching
= this_idata
->offset
>= startPC
594 && this_idata
->offset
<= endPC
;
595 if (!was_matching
&& is_matching
) {
596 memcpy(currentLocalVar
, oldEntry
, sizeof(struct localvar
));
597 currentLocalVar
->pc0
= codeRef
->offset
;
599 } else if (was_matching
&& !is_matching
) {
600 currentLocalVar
->length
=
601 codeRef
[-1].offset
- currentLocalVar
->pc0
;
603 was_matching
= FALSE
;
608 currentLocalVar
->length
=
609 codeRefEnd
[-1].offset
- currentLocalVar
->pc0
;
614 /* free(mb->localvar_table); */
615 mb
->localvar_table_length
= currentLocalVar
- localVars
;
616 mb
->localvar_table
= realloc(localVars
,
617 (char *)currentLocalVar
- (char *)localVars
);
622 updateTarget(JsrContext
*context
, int inumber
,
623 SubrContext
* subroutine
, void* target
, int offset
, int size
)
626 for (codeRef
= context
->mapping
[inumber
];
628 codeRef
= codeRef
->next
) {
629 if (subroutineGoto(context
, subroutine
, codeRef
->subroutine
)) {
630 int value
= codeRef
->offset
- offset
;
631 unsigned char *t
= target
;
635 } else if (size
== 4) {
641 panic("Bad value passed for size");
646 panic("Cannot find value for updateTarget");
652 subroutineGoto(JsrContext
*context
, SubrContext
*from
, SubrContext
*to
)
654 if (to
== NULL
|| to
== from
) {
656 } else if (from
== NULL
|| to
->depth
>= from
->depth
) {
659 do { from
= from
->parent
; } while (from
->depth
> to
->depth
);
666 matchSubroutine(JsrContext
*context
,
667 instruction_data_type
*this_idata
,
668 SubrContext
*subroutine
)
670 int depth
= subroutine
->depth
;
673 for (i
= depth
- 1; i
>= 0; --i
) {
674 if (this_idata
->register_info
.masks
[i
].entry
!= subroutine
->target
) {
677 subroutine
= subroutine
->parent
;