DEADSOFTWARE

32f996d8680922ae52eb8d9072947f993a628514
[mp3cc.git] / MPC.3.5.LINUX / preverifier / inlinejsr.c
1 /*
2 * @(#)inlinejsr.c 1.22 02/09/27
3 *
4 * Copyright 1995-2001 by Sun Microsystems, Inc.,
5 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
6 * All rights reserved.
7 *
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.
14 */
16 /*=========================================================================
17 * SYSTEM: Verifier
18 * SUBSYSTEM: JSR inlining
19 * FILE: inlinejsr.c
20 * OVERVIEW: Routines for inlining of JSR and RET bytecodes.
21 *
22 * AUTHOR: Frank Yellin, Sun Microsystems, Inc.
23 * Edited by Tasneem Sayeed, Sun Microsystems
24 *=======================================================================*/
26 /*=========================================================================
27 * Include files
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 */
45 int target;
47 struct SubrContext *next; /* linked list of all subr contexts */
48 } SubrContext;
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 */
59 } JsrContext;
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 */
70 } flags;
71 /* My offset in the new code */
72 int offset;
73 struct CodeRef *next; /* next codeRef with same "inumber" */
74 } CodeRef;
77 static bool_t matchSubroutine(JsrContext *, instruction_data_type*,
78 SubrContext *);
79 static bool_t subroutineGoto(JsrContext *, SubrContext *, SubrContext *);
82 static void
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*);
91 static void
92 updateTarget(JsrContext *,
93 int inumber,
94 SubrContext* subroutine,
95 void* target, int offset, int size);
98 void
99 rewriteCode(context_type *vcontext, struct methodblock *mb)
101 JsrContext context_buf;
102 JsrContext *context = &context_buf;
104 #if MYDEBUG
105 printf("Starting %s.%s%s\n", cbName(mb->fb.clazz), mb->fb.name, mb->fb.signature);
106 #endif
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,
119 sizeof(CodeRef **));
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 */
126 fixupCode(context);
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);
143 /* Clean up */
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;
151 free(this);
152 context->allSubrContexts = next;
156 static void
157 rewriteOneSubroutine(JsrContext *context, SubrContext *subroutine)
158 {
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;
166 int inumber;
167 int count = 0;
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)
176 && ((depth == 0)
177 || matchSubroutine(context, this_idata, subroutine))) {
179 /* We have an instruction that is part of this subroutine */
181 CodeRef *codeRef = context->codeRefEnd++;
182 #if MYDEBUG
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]),
188 this_idata->offset);
189 #endif
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;
196 count++;
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'
203 */
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;
218 } else {
219 SubrContext *newSubr = malloc(sizeof(SubrContext));
221 /* In rare cases, we'll have to change this in the
222 * subroutine code */
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);
238 break;
240 case opc_ret:
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");
248 retOpcode = codeRef;
249 /* Flags are set at the end of the loop, below */
250 break;
252 case opc_astore:
253 /* We discard any astore's that move a return address
254 * from the stack to a register.
255 */
256 if (GET_ITEM_TYPE(this_idata->stack_info.stack->item)
257 == ITEM_ReturnAddress) {
258 codeRef->flags = CRF_SKIP;
259 }
260 break;
262 default:
263 /* Nothing to do */
264 break;
268 if (depth > 0) {
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'.
273 */
274 if (context->codeRefEnd == retOpcode + 1) {
275 retOpcode->flags = CRF_SKIP;
276 } else {
277 retOpcode->flags = CRF_RET_SIMPLE_GOTO;
284 static void
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;
294 CodeRef *codeRef;
295 int pc;
296 long newCodeLength;
298 /* Assign offsets to each instruction. */
299 #if MYDEBUG
300 printf("Assigning offsets\n");
301 #endif
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;
308 #if MYDEBUG
309 printf("\t%d:\t%d\tpc=%d\t%s (%d) %s\n",
310 (codeRef - context->codeRef),
311 (this_idata - vcontext->instruction_data),
312 pc,
313 (this_idata->opcode == 256
314 ? "invokeinit" : opnames[this_idata->opcode]),
315 this_idata->offset,
316 ((codeRef->flags == CRF_SKIP) ? " XX" : "")
317 );
318 #endif
320 /* Now increment the pc, depending on the instruction */
321 if (codeRef->flags == CRF_SKIP) {
322 /* do nothing */
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
327 * values.
328 */
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 */
332 pc += 3;
333 } else {
334 pc += this_idata->length;
338 /* Create a new code object */
339 newCode = (unsigned char *)malloc(pc);
340 newCodeLength = pc;
342 #if MYDEBUG
343 printf("Creating code of length %d\n", pc);
344 #endif
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];
354 #if MYDEBUG
355 printf("\t%d:\t%d\tpc=%d\t%s (%d) \n",
356 (codeRef - context->codeRef),
357 (this_idata - vcontext->instruction_data),
358 pc,
359 (this_idata->opcode == 256
360 ? "invokeinit" : opnames[this_idata->opcode]),
361 this_idata->offset
362 );
363 #endif
365 switch(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,
375 codeRef->subroutine,
376 target + 1, pc, this_idata->length - 1);
377 break;
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,
383 codeRef->subroutine,
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);
389 } else {
390 panic("Shouldn't have anything referring to jsr");
392 break;
394 case opc_ret:
395 if (codeRef->flags & CRF_RET_SIMPLE_GOTO) {
396 int gotoTarget =
397 codeRef->subroutine->nextInstruction->offset;
398 target[0] = opc_goto;
399 target[1] = (gotoTarget - pc) >> 8;
400 target[2] = (gotoTarget - pc);
401 } else {
402 panic("Shouldn't have anything referring to ret");
404 break;
406 default:
407 memcpy(target, source, this_idata->length);
408 break;
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;
416 int i;
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,
427 targetPtr, pc, 4);
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);
435 } else {
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);
443 break;
449 mb->code = newCode;
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;
467 unsigned long i;
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,
486 instRef->subroutine,
487 hRef->subroutine);
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;
493 wasMatch = TRUE;
494 } else if (wasMatch && !thisMatch) {
495 currentCatchFrame->end_pc = instRef->offset;
496 currentCatchFrame++;
497 wasMatch = FALSE;
501 if (wasMatch) {
502 /* We end the code still in the catch frame */
503 currentCatchFrame->end_pc = mb->code_length;
504 currentCatchFrame++;
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;
527 CodeRef *codeRef;
528 int i, currentLineNumber;
530 {
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++) {
538 mapTable[pc] = line;
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++) {
545 mapTable[pc] = line;
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;
563 free(mapTable);
564 mb->line_number_table = realloc(lineTable,
565 (char *)currentLineTableEntry -
566 (char *)lineTable);
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;
576 CodeRef *codeRef;
577 unsigned long i;
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;
598 was_matching = TRUE;
599 } else if (was_matching && !is_matching) {
600 currentLocalVar->length =
601 codeRef[-1].offset - currentLocalVar->pc0;
602 currentLocalVar++;
603 was_matching = FALSE;
607 if (was_matching) {
608 currentLocalVar->length =
609 codeRefEnd[-1].offset - currentLocalVar->pc0;
610 currentLocalVar++;
614 /* free(mb->localvar_table); */
615 mb->localvar_table_length = currentLocalVar - localVars;
616 mb->localvar_table = realloc(localVars,
617 (char *)currentLocalVar - (char *)localVars);
621 static void
622 updateTarget(JsrContext *context, int inumber,
623 SubrContext* subroutine, void* target, int offset, int size)
625 CodeRef *codeRef;
626 for (codeRef = context->mapping[inumber];
627 codeRef != NULL;
628 codeRef = codeRef->next) {
629 if (subroutineGoto(context, subroutine, codeRef->subroutine)) {
630 int value = codeRef->offset - offset;
631 unsigned char *t = target;
632 if (size == 2) {
633 t[0] = value >> 8;
634 t[1] = value;
635 } else if (size == 4) {
636 t[0] = value >> 24;
637 t[1] = value >> 16;
638 t[2] = value >> 8;
639 t[3] = value;
640 } else {
641 panic("Bad value passed for size");
643 return;
646 panic("Cannot find value for updateTarget");
651 static bool_t
652 subroutineGoto(JsrContext *context, SubrContext *from, SubrContext *to)
653 {
654 if (to == NULL || to == from) {
655 return TRUE;
656 } else if (from == NULL || to->depth >= from->depth) {
657 return FALSE;
658 } else {
659 do { from = from->parent; } while (from->depth > to->depth);
660 return from == to;
665 static bool_t
666 matchSubroutine(JsrContext *context,
667 instruction_data_type *this_idata,
668 SubrContext *subroutine)
670 int depth = subroutine->depth;
671 int i;
673 for (i = depth - 1; i >= 0; --i) {
674 if (this_idata->register_info.masks[i].entry != subroutine->target) {
675 return FALSE;
677 subroutine = subroutine->parent;
679 return TRUE;