001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the "License");
007 * you may not use this file except in compliance with the License.
008 * You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018 /*
019 * $Id: MethodGenerator.java 1225436 2011-12-29 05:09:31Z mrglavas $
020 */
021
022 package org.apache.xalan.xsltc.compiler.util;
023
024 import java.util.ArrayList;
025 import java.util.Collections;
026 import java.util.HashMap;
027 import java.util.Hashtable;
028 import java.util.Iterator;
029 import java.util.Map;
030 import java.util.Stack;
031
032 import org.apache.bcel.Constants;
033 import org.apache.bcel.classfile.Field;
034 import org.apache.bcel.classfile.Method;
035 import org.apache.bcel.generic.ALOAD;
036 import org.apache.bcel.generic.ASTORE;
037 import org.apache.bcel.generic.BranchHandle;
038 import org.apache.bcel.generic.BranchInstruction;
039 import org.apache.bcel.generic.ConstantPoolGen;
040 import org.apache.bcel.generic.DLOAD;
041 import org.apache.bcel.generic.DSTORE;
042 import org.apache.bcel.generic.FLOAD;
043 import org.apache.bcel.generic.FSTORE;
044 import org.apache.bcel.generic.GETFIELD;
045 import org.apache.bcel.generic.GOTO;
046 import org.apache.bcel.generic.ICONST;
047 import org.apache.bcel.generic.IfInstruction;
048 import org.apache.bcel.generic.ILOAD;
049 import org.apache.bcel.generic.IndexedInstruction;
050 import org.apache.bcel.generic.INVOKEINTERFACE;
051 import org.apache.bcel.generic.INVOKESPECIAL;
052 import org.apache.bcel.generic.INVOKESTATIC;
053 import org.apache.bcel.generic.INVOKEVIRTUAL;
054 import org.apache.bcel.generic.ISTORE;
055 import org.apache.bcel.generic.Instruction;
056 import org.apache.bcel.generic.InstructionConstants;
057 import org.apache.bcel.generic.InstructionHandle;
058 import org.apache.bcel.generic.InstructionList;
059 import org.apache.bcel.generic.InstructionTargeter;
060 import org.apache.bcel.generic.LocalVariableGen;
061 import org.apache.bcel.generic.LocalVariableInstruction;
062 import org.apache.bcel.generic.LLOAD;
063 import org.apache.bcel.generic.LSTORE;
064 import org.apache.bcel.generic.MethodGen;
065 import org.apache.bcel.generic.NEW;
066 import org.apache.bcel.generic.PUTFIELD;
067 import org.apache.bcel.generic.RET;
068 import org.apache.bcel.generic.Select;
069 import org.apache.bcel.generic.TargetLostException;
070 import org.apache.bcel.generic.Type;
071
072 import org.apache.xalan.xsltc.compiler.Pattern;
073 import org.apache.xalan.xsltc.compiler.XSLTC;
074
075 /**
076 * @author Jacek Ambroziak
077 * @author Santiago Pericas-Geertsen
078 */
079 public class MethodGenerator extends MethodGen
080 implements org.apache.xalan.xsltc.compiler.Constants {
081 protected static final int INVALID_INDEX = -1;
082
083 private static final String START_ELEMENT_SIG
084 = "(" + STRING_SIG + ")V";
085 private static final String END_ELEMENT_SIG
086 = START_ELEMENT_SIG;
087
088 private InstructionList _mapTypeSub;
089
090 private static final int DOM_INDEX = 1;
091 private static final int ITERATOR_INDEX = 2;
092 private static final int HANDLER_INDEX = 3;
093
094 private static final int MAX_METHOD_SIZE = 65535;
095 private static final int MAX_BRANCH_TARGET_OFFSET = 32767;
096 private static final int MIN_BRANCH_TARGET_OFFSET = -32768;
097
098 private static final int TARGET_METHOD_SIZE = 60000;
099 private static final int MINIMUM_OUTLINEABLE_CHUNK_SIZE = 1000;
100
101 private Instruction _iloadCurrent;
102 private Instruction _istoreCurrent;
103 private final Instruction _astoreHandler;
104 private final Instruction _aloadHandler;
105 private final Instruction _astoreIterator;
106 private final Instruction _aloadIterator;
107 private final Instruction _aloadDom;
108 private final Instruction _astoreDom;
109
110 private final Instruction _startElement;
111 private final Instruction _endElement;
112 private final Instruction _startDocument;
113 private final Instruction _endDocument;
114 private final Instruction _attribute;
115 private final Instruction _uniqueAttribute;
116 private final Instruction _namespace;
117
118 private final Instruction _setStartNode;
119 private final Instruction _reset;
120 private final Instruction _nextNode;
121
122 private SlotAllocator _slotAllocator;
123 private boolean _allocatorInit = false;
124 private LocalVariableRegistry _localVariableRegistry;
125
126 /**
127 * A mapping between patterns and instruction lists used by
128 * test sequences to avoid compiling the same pattern multiple
129 * times. Note that patterns whose kernels are "*", "node()"
130 * and "@*" can between shared by test sequences.
131 */
132 private Hashtable _preCompiled = new Hashtable();
133
134 public MethodGenerator(int access_flags, Type return_type,
135 Type[] arg_types, String[] arg_names,
136 String method_name, String class_name,
137 InstructionList il, ConstantPoolGen cpg) {
138 super(access_flags, return_type, arg_types, arg_names, method_name,
139 class_name, il, cpg);
140
141 _astoreHandler = new ASTORE(HANDLER_INDEX);
142 _aloadHandler = new ALOAD(HANDLER_INDEX);
143 _astoreIterator = new ASTORE(ITERATOR_INDEX);
144 _aloadIterator = new ALOAD(ITERATOR_INDEX);
145 _aloadDom = new ALOAD(DOM_INDEX);
146 _astoreDom = new ASTORE(DOM_INDEX);
147
148 final int startElement =
149 cpg.addInterfaceMethodref(TRANSLET_OUTPUT_INTERFACE,
150 "startElement",
151 START_ELEMENT_SIG);
152 _startElement = new INVOKEINTERFACE(startElement, 2);
153
154 final int endElement =
155 cpg.addInterfaceMethodref(TRANSLET_OUTPUT_INTERFACE,
156 "endElement",
157 END_ELEMENT_SIG);
158 _endElement = new INVOKEINTERFACE(endElement, 2);
159
160 final int attribute =
161 cpg.addInterfaceMethodref(TRANSLET_OUTPUT_INTERFACE,
162 "addAttribute",
163 "("
164 + STRING_SIG
165 + STRING_SIG
166 + ")V");
167 _attribute = new INVOKEINTERFACE(attribute, 3);
168
169 final int uniqueAttribute =
170 cpg.addInterfaceMethodref(TRANSLET_OUTPUT_INTERFACE,
171 "addUniqueAttribute",
172 "("
173 + STRING_SIG
174 + STRING_SIG
175 + "I)V");
176 _uniqueAttribute = new INVOKEINTERFACE(uniqueAttribute, 4);
177
178 final int namespace =
179 cpg.addInterfaceMethodref(TRANSLET_OUTPUT_INTERFACE,
180 "namespaceAfterStartElement",
181 "("
182 + STRING_SIG
183 + STRING_SIG
184 + ")V");
185 _namespace = new INVOKEINTERFACE(namespace, 3);
186
187 int index = cpg.addInterfaceMethodref(TRANSLET_OUTPUT_INTERFACE,
188 "startDocument",
189 "()V");
190 _startDocument = new INVOKEINTERFACE(index, 1);
191
192 index = cpg.addInterfaceMethodref(TRANSLET_OUTPUT_INTERFACE,
193 "endDocument",
194 "()V");
195 _endDocument = new INVOKEINTERFACE(index, 1);
196
197
198 index = cpg.addInterfaceMethodref(NODE_ITERATOR,
199 SET_START_NODE,
200 SET_START_NODE_SIG);
201 _setStartNode = new INVOKEINTERFACE(index, 2);
202
203 index = cpg.addInterfaceMethodref(NODE_ITERATOR,
204 "reset", "()"+NODE_ITERATOR_SIG);
205 _reset = new INVOKEINTERFACE(index, 1);
206
207 index = cpg.addInterfaceMethodref(NODE_ITERATOR, NEXT, NEXT_SIG);
208 _nextNode = new INVOKEINTERFACE(index, 1);
209
210 _slotAllocator = new SlotAllocator();
211 _slotAllocator.initialize(getLocalVariableRegistry().getLocals(false));
212 _allocatorInit = true;
213 }
214
215 /**
216 * Allocates a local variable. If the slot allocator has already been
217 * initialized, then call addLocalVariable2() so that the new variable
218 * is known to the allocator. Failing to do this may cause the allocator
219 * to return a slot that is already in use.
220 */
221 public LocalVariableGen addLocalVariable(String name, Type type,
222 InstructionHandle start,
223 InstructionHandle end)
224 {
225 LocalVariableGen lvg;
226
227 if (_allocatorInit) {
228 lvg = addLocalVariable2(name, type, start);
229 } else {
230 lvg = super.addLocalVariable(name, type, start, end);
231 getLocalVariableRegistry().registerLocalVariable(lvg);
232 }
233
234 return lvg;
235 }
236
237 public LocalVariableGen addLocalVariable2(String name, Type type,
238 InstructionHandle start)
239 {
240 LocalVariableGen lvg = super.addLocalVariable(name, type,
241 _slotAllocator.allocateSlot(type),
242 start, null);
243 getLocalVariableRegistry().registerLocalVariable(lvg);
244 return lvg;
245 }
246
247 private LocalVariableRegistry getLocalVariableRegistry() {
248 if (_localVariableRegistry == null) {
249 _localVariableRegistry = new LocalVariableRegistry();
250 }
251
252 return _localVariableRegistry;
253 }
254
255 /**
256 * Keeps track of all local variables used in the method.
257 * <p>The
258 * {@link MethodGen#addLocalVariable(String,Type,InstructionHandle,InstructionHandle)}</code>
259 * and
260 * {@link MethodGen#addLocalVariable(String,Type,int,InstructionHandle,InstructionHandle)}</code>
261 * methods of {@link MethodGen} will only keep track of
262 * {@link LocalVariableGen} object until it'ss removed by a call to
263 * {@link MethodGen#removeLocalVariable(LocalVariableGen)}.</p>
264 * <p>In order to support efficient copying of local variables to outlined
265 * methods by
266 * {@link #outline(InstructionHandle,InstructionHandle,String,ClassGenerator)},
267 * this class keeps track of all local variables defined by the method.</p>
268 */
269 protected class LocalVariableRegistry {
270 /**
271 * <p>A <code>java.lang.ArrayList</code> of all
272 * {@link LocalVariableGen}s created for this method, indexed by the
273 * slot number of the local variable. The JVM stack frame of local
274 * variables is divided into "slots". A single slot can be used to
275 * store more than one variable in a method, without regard to type, so
276 * long as the byte code keeps the ranges of the two disjoint.</p>
277 * <p>If only one registration of use of a particular slot occurs, the
278 * corresponding entry of <code>_variables</code> contains the
279 * <code>LocalVariableGen</code>; if more than one occurs, the
280 * corresponding entry contains all such <code>LocalVariableGen</code>s
281 * registered for the same slot; and if none occurs, the entry will be
282 * <code>null</code>.
283 */
284 protected ArrayList _variables = new ArrayList();
285
286 /**
287 * Maps a name to a {@link LocalVariableGen}
288 */
289 protected HashMap _nameToLVGMap = new HashMap();
290
291 /**
292 * Registers a {@link org.apache.bcel.generic.LocalVariableGen}
293 * for this method.
294 * <p><b>Preconditions:</b>
295 * <ul>
296 * <li>The range of instructions for <code>lvg</code> does not
297 * overlap with the range of instructions for any
298 * <code>LocalVariableGen</code> with the same slot index previously
299 * registered for this method. <b><em>(Unchecked.)</em></b></li>
300 * </ul></p>
301 * @param lvg The variable to be registered
302 */
303 protected void registerLocalVariable(LocalVariableGen lvg) {
304 int slot = lvg.getIndex();
305
306 int registrySize = _variables.size();
307
308 // If the LocalVariableGen uses a slot index beyond any previously
309 // encountered, expand the _variables, padding with intervening null
310 // entries as required.
311 if (slot >= registrySize) {
312 for (int i = registrySize; i < slot; i++) {
313 _variables.add(null);
314 }
315 _variables.add(lvg);
316 } else {
317 // If the LocalVariableGen reuses a slot, make sure the entry
318 // in _variables contains an ArrayList and add the newly
319 // registered LocalVariableGen to the list. If the entry in
320 // _variables just contains null padding, store the
321 // LocalVariableGen directly.
322 Object localsInSlot = _variables.get(slot);
323 if (localsInSlot != null) {
324 if (localsInSlot instanceof LocalVariableGen) {
325 ArrayList listOfLocalsInSlot = new ArrayList();
326 listOfLocalsInSlot.add(localsInSlot);
327 listOfLocalsInSlot.add(lvg);
328 _variables.set(slot, listOfLocalsInSlot);
329 } else {
330 ((ArrayList) localsInSlot).add(lvg);
331 }
332 } else {
333 _variables.set(slot, lvg);
334 }
335 }
336
337 registerByName(lvg);
338 }
339
340 /**
341 * <p>Find which {@link LocalVariableGen}, if any, is registered for a
342 * particular JVM local stack frame slot at a particular position in the
343 * byte code for the method.</p>
344 * <p><b>Preconditions:</b>
345 * <ul>
346 * <li>The {@link InstructionList#setPositions()} has been called for
347 * the {@link InstructionList} associated with this
348 * {@link MethodGenerator}.</li>
349 * </ul></p>
350 * @param slot the JVM local stack frame slot number
351 * @param offset the position in the byte code
352 * @return the <code>LocalVariableGen</code> for the local variable
353 * stored in the relevant slot at the relevant offset; <code>null</code>
354 * if there is none.
355 */
356 protected LocalVariableGen lookupRegisteredLocalVariable(int slot,
357 int offset) {
358 Object localsInSlot = (_variables != null) ? _variables.get(slot)
359 : null;
360
361 // If this slot index was never used, _variables.get will return
362 // null; if it was used once, it will return the LocalVariableGen;
363 // more than once it will return an ArrayList of all the
364 // LocalVariableGens for variables stored in that slot. For each
365 // LocalVariableGen, check whether its range includes the
366 // specified offset, and return the first such encountered.
367 if (localsInSlot != null) {
368 if (localsInSlot instanceof LocalVariableGen) {
369 LocalVariableGen lvg = (LocalVariableGen)localsInSlot;
370 if (offsetInLocalVariableGenRange(lvg, offset)) {
371 return lvg;
372 }
373 } else {
374 ArrayList listOfLocalsInSlot = (ArrayList) localsInSlot;
375 int size = listOfLocalsInSlot.size();
376
377 for (int i = 0; i < size; i++) {
378 LocalVariableGen lvg =
379 (LocalVariableGen)listOfLocalsInSlot.get(i);
380 if (offsetInLocalVariableGenRange(lvg, offset)) {
381 return lvg;
382 }
383 }
384 }
385 }
386
387 // No local variable stored in the specified slot at the specified
388 return null;
389 }
390
391 /**
392 * <p>Set up a mapping of the name of the specified
393 * {@link LocalVariableGen} object to the <code>LocalVariableGen</code>
394 * itself.</p>
395 * <p>This is a bit of a hack. XSLTC is relying on the fact that the
396 * name that is being looked up won't be duplicated, which isn't
397 * guaranteed. It replaces code which used to call
398 * {@link MethodGen#getLocalVariables()} and looped through the
399 * <code>LocalVariableGen</code> objects it contained to find the one
400 * with the specified name. However, <code>getLocalVariables()</code>
401 * has the side effect of setting the start and end for any
402 * <code>LocalVariableGen</code> which did not already have them
403 * set, which causes problems for outlining..</p>
404 * <p>See also {@link #lookUpByName(String)} and
405 * {@link #removeByNameTracking(LocalVariableGen)}</P
406 * @param lvg a <code>LocalVariableGen</code>
407 */
408 protected void registerByName(LocalVariableGen lvg) {
409 Object duplicateNameEntry = _nameToLVGMap.get(lvg.getName());
410
411 if (duplicateNameEntry == null) {
412 _nameToLVGMap.put(lvg.getName(), lvg);
413 } else {
414 ArrayList sameNameList;
415
416 if (duplicateNameEntry instanceof ArrayList) {
417 sameNameList = (ArrayList) duplicateNameEntry;
418 sameNameList.add(lvg);
419 } else {
420 sameNameList = new ArrayList();
421 sameNameList.add(duplicateNameEntry);
422 sameNameList.add(lvg);
423 }
424
425 _nameToLVGMap.put(lvg.getName(), sameNameList);
426 }
427 }
428
429 /**
430 * Remove the mapping from the name of the specified
431 * {@link LocalVariableGen} to itself.
432 * See also {@link #registerByName(LocalVariableGen)} and
433 * {@link #lookUpByName(String)}
434 * @param lvg a <code>LocalVariableGen</code>
435 */
436 protected void removeByNameTracking(LocalVariableGen lvg) {
437 Object duplicateNameEntry = _nameToLVGMap.get(lvg.getName());
438
439 if (duplicateNameEntry instanceof ArrayList) {
440 ArrayList sameNameList = (ArrayList) duplicateNameEntry;
441 for (int i = 0; i < sameNameList.size(); i++) {
442 if (sameNameList.get(i) == lvg) {
443 sameNameList.remove(i);
444 break;
445 }
446 }
447 } else {
448 _nameToLVGMap.remove(lvg);
449 }
450 }
451
452 /**
453 * <p>Given the name of a variable, finds a {@link LocalVariableGen}
454 * corresponding to it.</p>
455 * <p>See also {@link #registerByName(LocalVariableGen)} and
456 * {@link #removeByNameTracking(LocalVariableGen)}</p>
457 * @param name
458 * @return
459 */
460 protected LocalVariableGen lookUpByName(String name) {
461 LocalVariableGen lvg = null;
462 Object duplicateNameEntry = _nameToLVGMap.get(name);
463
464 if (duplicateNameEntry instanceof ArrayList) {
465 ArrayList sameNameList = (ArrayList) duplicateNameEntry;
466
467 for (int i = 0; i < sameNameList.size(); i++) {
468 lvg = (LocalVariableGen)sameNameList.get(i);
469 if (lvg.getName() == name) {
470 break;
471 }
472 }
473 } else {
474 lvg = (LocalVariableGen) duplicateNameEntry;
475 }
476
477 return lvg;
478 }
479
480 /**
481 * <p>Gets all {@link LocalVariableGen} objects for this method.</p>
482 * <p>When the <code>includeRemoved</code> argument has the value
483 * <code>false</code>, this method replaces uses of
484 * {@link MethodGen#getLocalVariables()} which has
485 * a side-effect of setting the start and end range for any
486 * <code>LocalVariableGen</code> if either was <code>null</code>. That
487 * side-effect causes problems for outlining of code in XSLTC.
488 * @param includeRemoved Specifies whether all local variables ever
489 * declared should be returned (<code>true</code>) or only those not
490 * removed (<code>false</code>)
491 * @return an array of <code>LocalVariableGen</code> containing all the
492 * local variables
493 */
494 protected LocalVariableGen[] getLocals(boolean includeRemoved) {
495 LocalVariableGen[] locals = null;
496 ArrayList allVarsEverDeclared = new ArrayList();
497
498 if (includeRemoved) {
499 int slotCount = allVarsEverDeclared.size();
500
501 for (int i = 0; i < slotCount; i++) {
502 Object slotEntries = _variables.get(i);
503 if (slotEntries != null) {
504 if (slotEntries instanceof ArrayList) {
505 ArrayList slotList = (ArrayList) slotEntries;
506
507 for (int j = 0; j < slotList.size(); j++) {
508 allVarsEverDeclared.add(slotList.get(i));
509 }
510 } else {
511 allVarsEverDeclared.add(slotEntries);
512 }
513 }
514 }
515 } else {
516 Iterator nameVarsPairsIter = _nameToLVGMap.entrySet().iterator();
517
518 while (nameVarsPairsIter.hasNext()) {
519 Map.Entry nameVarsPair =
520 (Map.Entry) nameVarsPairsIter.next();
521 Object vars = nameVarsPair.getValue();
522 if (vars != null) {
523 if (vars instanceof ArrayList) {
524 ArrayList varsList = (ArrayList) vars;
525 for (int i = 0; i < varsList.size(); i++) {
526 allVarsEverDeclared.add(varsList.get(i));
527 }
528 } else {
529 allVarsEverDeclared.add(vars);
530 }
531 }
532 }
533 }
534
535 locals = new LocalVariableGen[allVarsEverDeclared.size()];
536 allVarsEverDeclared.toArray(locals);
537
538 return locals;
539 }
540 }
541
542 /**
543 * Determines whether a particular variable is in use at a particular offset
544 * in the byte code for this method.
545 * <p><b>Preconditions:</b>
546 * <ul>
547 * <li>The {@link InstructionList#setPositions()} has been called for the
548 * {@link InstructionList} associated with this {@link MethodGenerator}.
549 * </li></ul></p>
550 * @param lvg the {@link LocalVariableGen} for the variable
551 * @param offset the position in the byte code
552 * @return <code>true</code> if and only if the specified variable is in
553 * use at the particular byte code offset.
554 */
555 boolean offsetInLocalVariableGenRange(LocalVariableGen lvg, int offset) {
556 InstructionHandle lvgStart = lvg.getStart();
557 InstructionHandle lvgEnd = lvg.getEnd();
558
559 // If no start handle is recorded for the LocalVariableGen, it is
560 // assumed to be in use from the beginning of the method.
561 if (lvgStart == null) {
562 lvgStart = getInstructionList().getStart();
563 }
564
565 // If no end handle is recorded for the LocalVariableGen, it is assumed
566 // to be in use to the end of the method.
567 if (lvgEnd == null) {
568 lvgEnd = getInstructionList().getEnd();
569 }
570
571 // Does the range of the instruction include the specified offset?
572 // Note that the InstructionHandle.getPosition method returns the
573 // offset of the beginning of an instruction. A LocalVariableGen's
574 // range includes the end instruction itself, so that instruction's
575 // length must be taken into consideration in computing whether the
576 // varible is in range at a particular offset.
577 return ((lvgStart.getPosition() <= offset)
578 && (lvgEnd.getPosition()
579 + lvgEnd.getInstruction().getLength() >= offset));
580 }
581
582 public void removeLocalVariable(LocalVariableGen lvg) {
583 _slotAllocator.releaseSlot(lvg);
584 getLocalVariableRegistry().removeByNameTracking(lvg);
585 super.removeLocalVariable(lvg);
586 }
587
588 public Instruction loadDOM() {
589 return _aloadDom;
590 }
591
592 public Instruction storeDOM() {
593 return _astoreDom;
594 }
595
596 public Instruction storeHandler() {
597 return _astoreHandler;
598 }
599
600 public Instruction loadHandler() {
601 return _aloadHandler;
602 }
603
604 public Instruction storeIterator() {
605 return _astoreIterator;
606 }
607
608 public Instruction loadIterator() {
609 return _aloadIterator;
610 }
611
612 public final Instruction setStartNode() {
613 return _setStartNode;
614 }
615
616 public final Instruction reset() {
617 return _reset;
618 }
619
620 public final Instruction nextNode() {
621 return _nextNode;
622 }
623
624 public final Instruction startElement() {
625 return _startElement;
626 }
627
628 public final Instruction endElement() {
629 return _endElement;
630 }
631
632 public final Instruction startDocument() {
633 return _startDocument;
634 }
635
636 public final Instruction endDocument() {
637 return _endDocument;
638 }
639
640 public final Instruction attribute() {
641 return _attribute;
642 }
643
644 public final Instruction uniqueAttribute() {
645 return _uniqueAttribute;
646 }
647
648 public final Instruction namespace() {
649 return _namespace;
650 }
651
652 public Instruction loadCurrentNode() {
653 if (_iloadCurrent == null) {
654 int idx = getLocalIndex("current");
655 if (idx > 0)
656 _iloadCurrent = new ILOAD(idx);
657 else
658 _iloadCurrent = new ICONST(0);
659 }
660 return _iloadCurrent;
661 }
662
663 public Instruction storeCurrentNode() {
664 return _istoreCurrent != null
665 ? _istoreCurrent
666 : (_istoreCurrent = new ISTORE(getLocalIndex("current")));
667 }
668
669 /** by default context node is the same as current node. MK437 */
670 public Instruction loadContextNode() {
671 return loadCurrentNode();
672 }
673
674 public Instruction storeContextNode() {
675 return storeCurrentNode();
676 }
677
678 public int getLocalIndex(String name) {
679 return getLocalVariable(name).getIndex();
680 }
681
682 public LocalVariableGen getLocalVariable(String name) {
683 return getLocalVariableRegistry().lookUpByName(name);
684 }
685
686 public void setMaxLocals() {
687
688 // Get the current number of local variable slots
689 int maxLocals = super.getMaxLocals();
690
691 // Get numer of actual variables
692 final LocalVariableGen[] localVars = super.getLocalVariables();
693 if (localVars != null) {
694 if (localVars.length > maxLocals)
695 maxLocals = localVars.length;
696 }
697
698 // We want at least 5 local variable slots (for parameters)
699 if (maxLocals < 5) maxLocals = 5;
700
701 super.setMaxLocals(maxLocals);
702 }
703
704 /**
705 * Add a pre-compiled pattern to this mode.
706 */
707 public void addInstructionList(Pattern pattern, InstructionList ilist) {
708 _preCompiled.put(pattern, ilist);
709 }
710
711 /**
712 * Get the instruction list for a pre-compiled pattern. Used by
713 * test sequences to avoid compiling patterns more than once.
714 */
715 public InstructionList getInstructionList(Pattern pattern) {
716 return (InstructionList) _preCompiled.get(pattern);
717 }
718
719 /**
720 * Used to keep track of an outlineable chunk of instructions in the
721 * current method. See {@link OutlineableChunkStart} and
722 * {@link OutlineableChunkEnd} for more information.
723 */
724 private static class Chunk implements Comparable {
725 /**
726 * {@link InstructionHandle} of the first instruction in the outlineable
727 * chunk.
728 */
729 private InstructionHandle m_start;
730
731 /**
732 * {@link org.apache.bcel.generic.InstructionHandle} of the first
733 * instruction in the outlineable chunk.
734 */
735 private InstructionHandle m_end;
736
737 /**
738 * Number of bytes in the instructions contained in this outlineable
739 * chunk.
740 */
741 private int m_size;
742
743 /**
744 * <p>Constructor for an outlineable {@link MethodGenerator.Chunk}.</p>
745 * <p><b>Preconditions:</b>
746 * <ul>
747 * <li>The {@link InstructionList#setPositions()} has been called for
748 * the {@link InstructionList} associated with this
749 * {@link MethodGenerator}.</li>
750 * </ul></p>
751 * @param start The {@link InstructionHandle} of the first
752 * instruction in the outlineable chunk.
753 * @param end The {@link InstructionHandle} of the last
754 * instruction in the outlineable chunk.
755 */
756 Chunk(InstructionHandle start, InstructionHandle end) {
757 m_start = start;
758 m_end = end;
759 m_size = end.getPosition() - start.getPosition();
760 }
761
762 /**
763 * Determines whether this outlineable {@link MethodGenerator.Chunk} is
764 * followed immediately by the argument
765 * <code>MethodGenerator.Chunk</code>, with no other intervening
766 * instructions, including {@link OutlineableChunkStart} or
767 * {@link OutlineableChunkEnd} instructions.
768 * @param neighbour an outlineable {@link MethodGenerator.Chunk}
769 * @return <code>true</code> if and only if the argument chunk
770 * immediately follows <code>this</code> chunk
771 */
772 boolean isAdjacentTo(Chunk neighbour) {
773 return getChunkEnd().getNext() == neighbour.getChunkStart();
774 }
775
776 /**
777 * Getter method for the start of this {@linke MethodGenerator.Chunk}
778 * @return the {@link org.apache.bcel.generic.InstructionHandle} of the
779 * start of this chunk
780 */
781 InstructionHandle getChunkStart() {
782 return m_start;
783 }
784
785 /**
786 * Getter method for the end of this {@link MethodGenerator.Chunk}
787 * @return the {@link InstructionHandle} of the start of this chunk
788 */
789 InstructionHandle getChunkEnd() {
790 return m_end;
791 }
792
793 /**
794 * The size of this {@link MethodGenerator.Chunk}
795 * @return the number of bytes in the byte code represented by this
796 * chunk.
797 */
798 int getChunkSize() {
799 return m_size;
800 }
801
802 /**
803 * Implements the <code>java.util.Comparable.compareTo(Object)</code>
804 * method.
805 * @return
806 * <ul>
807 * <li>A positive <code>int</code> if the length of <code>this</code>
808 * chunk in bytes is greater than that of <code>comparand</code></li>
809 * <li>A negative <code>int</code> if the length of <code>this</code>
810 * chunk in bytes is less than that of <code>comparand</code></li>
811 * <li>Zero, otherwise.</li>
812 * </ul>
813 */
814 public int compareTo(Object comparand) {
815 return getChunkSize() - ((Chunk)comparand).getChunkSize();
816 }
817 }
818
819 /**
820 * Find the outlineable chunks in this method that would be the best choices
821 * to outline, based on size and position in the method.
822 * @param classGen The {@link ClassGen} with which the generated methods
823 * will be associated
824 * @param totalMethodSize the size of the bytecode in the original method
825 * @return a <code>java.util.ArrayList</code> containing the
826 * {@link MethodGenerator.Chunk}s that may be outlined from this method
827 */
828 private ArrayList getCandidateChunks(ClassGenerator classGen,
829 int totalMethodSize) {
830 Iterator instructions = getInstructionList().iterator();
831 ArrayList candidateChunks = new ArrayList();
832 ArrayList currLevelChunks = new ArrayList();
833 Stack subChunkStack = new Stack();
834 boolean openChunkAtCurrLevel = false;
835 boolean firstInstruction = true;
836
837 InstructionHandle currentHandle;
838
839 if (m_openChunks != 0) {
840 String msg =
841 (new ErrorMsg(ErrorMsg.OUTLINE_ERR_UNBALANCED_MARKERS))
842 .toString();
843 throw new InternalError(msg);
844 }
845
846 // Scan instructions in the method, keeping track of the nesting level
847 // of outlineable chunks.
848 //
849 // currLevelChunks
850 // keeps track of the child chunks of a chunk. For each chunk,
851 // there will be a pair of entries: the InstructionHandles for the
852 // start and for the end of the chunk
853 // subChunkStack
854 // a stack containing the partially accumulated currLevelChunks for
855 // each chunk that's still open at the current position in the
856 // InstructionList.
857 // candidateChunks
858 // the list of chunks which have been accepted as candidates chunks
859 // for outlining
860 do {
861 // Get the next instruction. The loop will perform one extra
862 // iteration after it reaches the end of the InstructionList, with
863 // currentHandle set to null.
864 currentHandle = instructions.hasNext()
865 ? (InstructionHandle) instructions.next()
866 : null;
867 Instruction inst =
868 (currentHandle != null) ? currentHandle.getInstruction()
869 : null;
870
871 // At the first iteration, create a chunk representing all the
872 // code in the method. This is done just to simplify the logic -
873 // this chunk can never be outlined because it will be too big.
874 if (firstInstruction) {
875 openChunkAtCurrLevel = true;
876 currLevelChunks.add(currentHandle);
877 firstInstruction = false;
878 }
879
880 // Found a new chunk
881 if (inst instanceof OutlineableChunkStart) {
882 // If last MarkerInstruction encountered was an
883 // OutlineableChunkStart, this represents the first chunk
884 // nested within that previous chunk - push the list of chunks
885 // from the outer level onto the stack
886 if (openChunkAtCurrLevel) {
887 subChunkStack.push(currLevelChunks);
888 currLevelChunks = new ArrayList();
889 }
890
891 openChunkAtCurrLevel = true;
892 currLevelChunks.add(currentHandle);
893 // Close off an open chunk
894 } else if (currentHandle == null
895 || inst instanceof OutlineableChunkEnd) {
896 ArrayList nestedSubChunks = null;
897
898 // If the last MarkerInstruction encountered was an
899 // OutlineableChunkEnd, it means that the current instruction
900 // marks the end of a chunk that contained child chunks.
901 // Those children might need to be examined below in case they
902 // are better candidates for outlining than the current chunk.
903 if (!openChunkAtCurrLevel) {
904 nestedSubChunks = currLevelChunks;
905 currLevelChunks = (ArrayList)subChunkStack.pop();
906 }
907
908 // Get the handle for the start of this chunk (the last entry
909 // in currLevelChunks)
910 InstructionHandle chunkStart =
911 (InstructionHandle) currLevelChunks.get(
912 currLevelChunks.size()-1);
913
914 int chunkEndPosition =
915 (currentHandle != null) ? currentHandle.getPosition()
916 : totalMethodSize;
917 int chunkSize = chunkEndPosition - chunkStart.getPosition();
918
919 // Two ranges of chunk size to consider:
920 //
921 // 1. [0,TARGET_METHOD_SIZE]
922 // Keep this chunk in consideration as a candidate,
923 // and ignore its subchunks, if any - there's nothing to be
924 // gained by outlining both the current chunk and its
925 // children!
926 //
927 // 2. (TARGET_METHOD_SIZE,+infinity)
928 // Ignore this chunk - it's too big. Add its subchunks
929 // as candidates, after merging adjacent chunks to produce
930 // chunks that are as large as possible
931 if (chunkSize <= TARGET_METHOD_SIZE) {
932 currLevelChunks.add(currentHandle);
933 } else {
934 if (!openChunkAtCurrLevel) {
935 int childChunkCount = nestedSubChunks.size() / 2;
936 if (childChunkCount > 0) {
937 Chunk[] childChunks = new Chunk[childChunkCount];
938
939 // Gather all the child chunks of the current chunk
940 for (int i = 0; i < childChunkCount; i++) {
941 InstructionHandle start =
942 (InstructionHandle) nestedSubChunks
943 .get(i*2);
944 InstructionHandle end =
945 (InstructionHandle) nestedSubChunks
946 .get(i*2+1);
947
948 childChunks[i] = new Chunk(start, end);
949 }
950
951 // Merge adjacent siblings
952 ArrayList mergedChildChunks =
953 mergeAdjacentChunks(childChunks);
954
955 // Add chunks that mean minimum size requirements
956 // to the list of candidate chunks for outlining
957 for (int i = 0; i < mergedChildChunks.size(); i++) {
958 Chunk mergedChunk =
959 (Chunk)mergedChildChunks.get(i);
960 int mergedSize = mergedChunk.getChunkSize();
961
962 if (mergedSize >= MINIMUM_OUTLINEABLE_CHUNK_SIZE
963 && mergedSize <= TARGET_METHOD_SIZE) {
964 candidateChunks.add(mergedChunk);
965 }
966 }
967 }
968 }
969
970 // Drop the chunk which was too big
971 currLevelChunks.remove(currLevelChunks.size() - 1);
972 }
973
974 // currLevelChunks contains pairs of InstructionHandles. If
975 // its size is an odd number, the loop has encountered the
976 // start of a chunk at this level, but not its end.
977 openChunkAtCurrLevel = ((currLevelChunks.size() & 0x1) == 1);
978 }
979
980 } while (currentHandle != null);
981
982 return candidateChunks;
983 }
984
985 /**
986 * Merge adjacent sibling chunks to produce larger candidate chunks for
987 * outlining
988 * @param chunks array of sibling {@link MethodGenerator.Chunk}s that are
989 * under consideration for outlining. Chunks must be in
990 * the order encountered in the {@link InstructionList}
991 * @return a <code>java.util.ArrayList</code> of
992 * <code>MethodGenerator.Chunk</code>s maximally merged
993 */
994 private ArrayList mergeAdjacentChunks(Chunk[] chunks) {
995 int[] adjacencyRunStart = new int[chunks.length];
996 int[] adjacencyRunLength = new int[chunks.length];
997 boolean[] chunkWasMerged = new boolean[chunks.length];
998
999 int maximumRunOfChunks = 0;
1000 int startOfCurrentRun;
1001 int numAdjacentRuns = 0;
1002
1003 ArrayList mergedChunks = new ArrayList();
1004
1005 startOfCurrentRun = 0;
1006
1007 // Loop through chunks, and record in adjacencyRunStart where each
1008 // run of adjacent chunks begins and how many are in that run. For
1009 // example, given chunks A B C D E F, if A is adjacent to B, but not
1010 // to C, and C, D, E and F are all adjacent,
1011 // adjacencyRunStart[0] == 0; adjacencyRunLength[0] == 2
1012 // adjacencyRunStart[1] == 2; adjacencyRunLength[1] == 4
1013 for (int i = 1; i < chunks.length; i++) {
1014 if (!chunks[i-1].isAdjacentTo(chunks[i])) {
1015 int lengthOfRun = i - startOfCurrentRun;
1016
1017 // Track the longest run of chunks found
1018 if (maximumRunOfChunks < lengthOfRun) {
1019 maximumRunOfChunks = lengthOfRun;
1020 }
1021
1022 if (lengthOfRun > 1 ) {
1023 adjacencyRunLength[numAdjacentRuns] = lengthOfRun;
1024 adjacencyRunStart[numAdjacentRuns] = startOfCurrentRun;
1025 numAdjacentRuns++;
1026 }
1027
1028 startOfCurrentRun = i;
1029 }
1030 }
1031
1032 if (chunks.length - startOfCurrentRun > 1) {
1033 int lengthOfRun = chunks.length - startOfCurrentRun;
1034
1035 // Track the longest run of chunks found
1036 if (maximumRunOfChunks < lengthOfRun) {
1037 maximumRunOfChunks = lengthOfRun;
1038 }
1039
1040 adjacencyRunLength[numAdjacentRuns] =
1041 chunks.length - startOfCurrentRun;
1042 adjacencyRunStart[numAdjacentRuns] = startOfCurrentRun;
1043 numAdjacentRuns++;
1044 }
1045
1046 // Try merging adjacent chunks to come up with better sized chunks for
1047 // outlining. This algorithm is not optimal, but it should be
1048 // reasonably fast. Consider an example like this, where four chunks
1049 // of the sizes specified in brackets are adjacent. The best way of
1050 // combining these chunks would be to merge the first pair and merge
1051 // the last three to form two chunks, but the algorithm will merge the
1052 // three in the middle instead, leaving three chunks in all.
1053 // [25000] [25000] [20000] [1000] [20000]
1054
1055 // Start by trying to merge the maximum number of adjacent chunks, and
1056 // work down from there.
1057 for (int numToMerge = maximumRunOfChunks; numToMerge>1; numToMerge--) {
1058 // Look at each run of adjacent chunks
1059 for (int run = 0; run < numAdjacentRuns; run++) {
1060 int runStart = adjacencyRunStart[run];
1061 int runEnd = runStart + adjacencyRunLength[run] - 1;
1062
1063 boolean foundChunksToMerge = false;
1064
1065 // Within the current run of adjacent chunks, look at all
1066 // "subruns" of length numToMerge, until we run out or find
1067 // a subrun that can be merged.
1068 for (int mergeStart = runStart;
1069 mergeStart+numToMerge-1 <= runEnd && !foundChunksToMerge;
1070 mergeStart++) {
1071 int mergeEnd = mergeStart + numToMerge - 1;
1072 int mergeSize = 0;
1073
1074 // Find out how big the subrun is
1075 for (int j = mergeStart; j <= mergeEnd; j++) {
1076 mergeSize = mergeSize + chunks[j].getChunkSize();
1077 }
1078
1079 // If the current subrun is small enough to outline,
1080 // merge it, and split the remaining chunks in the run
1081 if (mergeSize <= TARGET_METHOD_SIZE) {
1082 foundChunksToMerge = true;
1083
1084 for (int j = mergeStart; j <= mergeEnd; j++) {
1085 chunkWasMerged[j] = true;
1086 }
1087
1088 mergedChunks.add(
1089 new Chunk(chunks[mergeStart].getChunkStart(),
1090 chunks[mergeEnd].getChunkEnd()));
1091
1092 // Adjust the length of the current run of adjacent
1093 // chunks to end at the newly merged chunk...
1094 adjacencyRunLength[run] =
1095 adjacencyRunStart[run] - mergeStart;
1096
1097 int trailingRunLength = runEnd - mergeEnd;
1098
1099 // and any chunks that follow the newly merged chunk
1100 // in the current run of adjacent chunks form another
1101 // new run of adjacent chunks
1102 if (trailingRunLength >= 2) {
1103 adjacencyRunStart[numAdjacentRuns] = mergeEnd + 1;
1104 adjacencyRunLength[numAdjacentRuns] =
1105 trailingRunLength;
1106 numAdjacentRuns++;
1107 }
1108 }
1109 }
1110 }
1111 }
1112
1113 // Make a final pass for any chunk that wasn't merged with a sibling
1114 // and include it in the list of chunks after merging.
1115 for (int i = 0; i < chunks.length; i++) {
1116 if (!chunkWasMerged[i]) {
1117 mergedChunks.add(chunks[i]);
1118 }
1119 }
1120
1121 return mergedChunks;
1122 }
1123
1124 /**
1125 * Breaks up the IL for this {@link MethodGenerator} into separate
1126 * outlined methods so that no method exceeds the 64KB limit on the length
1127 * of the byte code associated with a method.
1128 * @param classGen The {@link ClassGen} with which the generated methods
1129 * will be associated
1130 * @param originalMethodSize The number of bytes of bytecode represented by
1131 * the {@link InstructionList} of this method
1132 * @return an array of the outlined <code>Method</code>s and the original
1133 * method itself
1134 */
1135 public Method[] outlineChunks(ClassGenerator classGen,
1136 int originalMethodSize) {
1137 ArrayList methodsOutlined = new ArrayList();
1138 int currentMethodSize = originalMethodSize;
1139
1140 int outlinedCount = 0;
1141 boolean moreMethodsOutlined;
1142 String originalMethodName = getName();
1143
1144 // Special handling for initialization methods. No other methods can
1145 // include the less than and greater than characters in their names,
1146 // so we munge the names here.
1147 if (originalMethodName.equals("<init>")) {
1148 originalMethodName = "$lt$init$gt$";
1149 } else if (originalMethodName.equals("<clinit>")) {
1150 originalMethodName = "$lt$clinit$gt$";
1151 }
1152
1153 // Loop until the original method comes in under the JVM limit or
1154 // the loop was unable to outline any more methods
1155 do {
1156 // Get all the best candidates for outlining, and sort them in
1157 // ascending order of size
1158 ArrayList candidateChunks = getCandidateChunks(classGen,
1159 currentMethodSize);
1160 Collections.sort(candidateChunks);
1161
1162 moreMethodsOutlined = false;
1163
1164 // Loop over the candidates for outlining, from the largest to the
1165 // smallest and outline them one at a time, until the loop has
1166 // outlined all or the original method comes in under the JVM
1167 // limit on the size of a method.
1168 for (int i = candidateChunks.size()-1;
1169 i >= 0 && currentMethodSize > TARGET_METHOD_SIZE;
1170 i--) {
1171 Chunk chunkToOutline = (Chunk)candidateChunks.get(i);
1172
1173 methodsOutlined.add(outline(chunkToOutline.getChunkStart(),
1174 chunkToOutline.getChunkEnd(),
1175 originalMethodName + "$outline$"
1176 + outlinedCount,
1177 classGen));
1178 outlinedCount++;
1179 moreMethodsOutlined = true;
1180
1181 InstructionList il = getInstructionList();
1182 InstructionHandle lastInst = il.getEnd();
1183 il.setPositions();
1184
1185 // Check the size of the method now
1186 currentMethodSize =
1187 lastInst.getPosition()
1188 + lastInst.getInstruction().getLength();
1189 }
1190 } while (moreMethodsOutlined && currentMethodSize > TARGET_METHOD_SIZE);
1191
1192 // Outlining failed to reduce the size of the current method
1193 // sufficiently. Throw an internal error.
1194 if (currentMethodSize > MAX_METHOD_SIZE) {
1195 String msg = (new ErrorMsg(ErrorMsg.OUTLINE_ERR_METHOD_TOO_BIG))
1196 .toString();
1197 throw new InternalError(msg);
1198 }
1199
1200 Method[] methodsArr = new Method[methodsOutlined.size() + 1];
1201 methodsOutlined.toArray(methodsArr);
1202
1203 methodsArr[methodsOutlined.size()] = getThisMethod();
1204
1205 return methodsArr;
1206 }
1207
1208 /**
1209 * Given an outlineable chunk of code in the current {@link MethodGenerator}
1210 * move ("outline") the chunk to a new method, and replace the chunk in the
1211 * old method with a reference to that new method. No
1212 * {@link OutlineableChunkStart} or {@link OutlineableChunkEnd} instructions
1213 * are copied.
1214 * @param first The {@link InstructionHandle} of the first instruction in
1215 * the chunk to outline
1216 * @param last The <code>InstructionHandle</code> of the last instruction in
1217 * the chunk to outline
1218 * @param outlinedMethodName The name of the new method
1219 * @param classGen The {@link ClassGenerator} of which the original
1220 * and new methods will be members
1221 * @return The new {@link Method} containing the outlined code.
1222 */
1223 private Method outline(InstructionHandle first, InstructionHandle last,
1224 String outlinedMethodName, ClassGenerator classGen) {
1225 // We're not equipped to deal with exception handlers yet. Bail out!
1226 if (getExceptionHandlers().length != 0) {
1227 String msg = (new ErrorMsg(ErrorMsg.OUTLINE_ERR_TRY_CATCH))
1228 .toString();
1229 throw new InternalError(msg);
1230 }
1231
1232 int outlineChunkStartOffset = first.getPosition();
1233 int outlineChunkEndOffset = last.getPosition()
1234 + last.getInstruction().getLength();
1235
1236 ConstantPoolGen cpg = getConstantPool();
1237
1238 // Create new outlined method with signature:
1239 //
1240 // private final outlinedMethodName(CopyLocals copyLocals);
1241 //
1242 // CopyLocals is an object that is used to copy-in/copy-out local
1243 // variables that are used by the outlined method. Only locals whose
1244 // value is potentially set or referenced outside the range of the
1245 // chunk that is being outlined will be represented in CopyLocals. The
1246 // type of the variable for copying local variables is actually
1247 // generated to be unique - it is not named CopyLocals.
1248 //
1249 // The outlined method never needs to be referenced outside of this
1250 // class, and will never be overridden, so we mark it private final.
1251 final InstructionList newIL = new InstructionList();
1252
1253 final XSLTC xsltc = classGen.getParser().getXSLTC();
1254 final String argTypeName = xsltc.getHelperClassName();
1255 final Type[] argTypes =
1256 new Type[] {(new ObjectType(argTypeName)).toJCType()};
1257 final String argName = "copyLocals";
1258 final String[] argNames = new String[] {argName};
1259
1260 int methodAttributes = ACC_PRIVATE | ACC_FINAL;
1261 final boolean isStaticMethod = (getAccessFlags() & ACC_STATIC) != 0;
1262
1263 if (isStaticMethod) {
1264 methodAttributes = methodAttributes | ACC_STATIC;
1265 }
1266
1267 final MethodGenerator outlinedMethodGen =
1268 new MethodGenerator(methodAttributes,
1269 org.apache.bcel.generic.Type.VOID,
1270 argTypes, argNames, outlinedMethodName,
1271 getClassName(), newIL, cpg);
1272
1273 // Create class for copying local variables to the outlined method.
1274 // The fields the class will need to contain will be determined as the
1275 // code in the outlineable chunk is examined.
1276 ClassGenerator copyAreaCG
1277 = new ClassGenerator(argTypeName, OBJECT_CLASS, argTypeName+".java",
1278 ACC_FINAL | ACC_PUBLIC | ACC_SUPER, null,
1279 classGen.getStylesheet()) {
1280 public boolean isExternal() {
1281 return true;
1282 }
1283 };
1284 ConstantPoolGen copyAreaCPG = copyAreaCG.getConstantPool();
1285 copyAreaCG.addEmptyConstructor(ACC_PUBLIC);
1286
1287 // Number of fields in the copy class
1288 int copyAreaFieldCount = 0;
1289
1290 // The handle for the instruction after the last one to be outlined.
1291 // Note that this should never end up being null. An outlineable chunk
1292 // won't contain a RETURN instruction or other branch out of the chunk,
1293 // and the JVM specification prohibits code in a method from just
1294 // "falling off the end" so this should always point to a valid handle.
1295 InstructionHandle limit = last.getNext();
1296
1297 // InstructionLists for copying values into and out of an instance of
1298 // CopyLocals:
1299 // oldMethCoypInIL - from locals in old method into an instance
1300 // of the CopyLocals class (oldMethCopyInIL)
1301 // oldMethCopyOutIL - from CopyLocals back into locals in the old
1302 // method
1303 // newMethCopyInIL - from CopyLocals into locals in the new
1304 // method
1305 // newMethCopyOutIL - from locals in new method into the instance
1306 // of the CopyLocals class
1307 InstructionList oldMethCopyInIL = new InstructionList();
1308 InstructionList oldMethCopyOutIL = new InstructionList();
1309 InstructionList newMethCopyInIL = new InstructionList();
1310 InstructionList newMethCopyOutIL = new InstructionList();
1311
1312 // Allocate instance of class in which we'll copy in or copy out locals
1313 // and make two copies: last copy is used to invoke constructor;
1314 // other two are used for references to fields in the CopyLocals object
1315 InstructionHandle outlinedMethodCallSetup =
1316 oldMethCopyInIL.append(new NEW(cpg.addClass(argTypeName)));
1317 oldMethCopyInIL.append(InstructionConstants.DUP);
1318 oldMethCopyInIL.append(InstructionConstants.DUP);
1319 oldMethCopyInIL.append(
1320 new INVOKESPECIAL(cpg.addMethodref(argTypeName, "<init>", "()V")));
1321
1322 // Generate code to invoke the new outlined method, and place the code
1323 // on oldMethCopyOutIL
1324 InstructionHandle outlinedMethodRef;
1325
1326 if (isStaticMethod) {
1327 outlinedMethodRef =
1328 oldMethCopyOutIL.append(
1329 new INVOKESTATIC(cpg.addMethodref(
1330 classGen.getClassName(),
1331 outlinedMethodName,
1332 outlinedMethodGen.getSignature())));
1333 } else {
1334 oldMethCopyOutIL.append(InstructionConstants.THIS);
1335 oldMethCopyOutIL.append(InstructionConstants.SWAP);
1336 outlinedMethodRef =
1337 oldMethCopyOutIL.append(
1338 new INVOKEVIRTUAL(cpg.addMethodref(
1339 classGen.getClassName(),
1340 outlinedMethodName,
1341 outlinedMethodGen.getSignature())));
1342 }
1343
1344 // Used to keep track of the first in a sequence of
1345 // OutlineableChunkStart instructions
1346 boolean chunkStartTargetMappingsPending = false;
1347 InstructionHandle pendingTargetMappingHandle = null;
1348
1349 // Used to keep track of the last instruction that was copied
1350 InstructionHandle lastCopyHandle = null;
1351
1352 // Keeps track of the mapping from instruction handles in the old
1353 // method to instruction handles in the outlined method. Only need
1354 // to track instructions that are targeted by something else in the
1355 // generated BCEL
1356 HashMap targetMap = new HashMap();
1357
1358 // Keeps track of the mapping from local variables in the old method
1359 // to local variables in the outlined method.
1360 HashMap localVarMap = new HashMap();
1361
1362 HashMap revisedLocalVarStart = new HashMap();
1363 HashMap revisedLocalVarEnd = new HashMap();
1364
1365 // Pass 1: Make copies of all instructions, append them to the new list
1366 // and associate old instruction references with the new ones, i.e.,
1367 // a 1:1 mapping. The special marker instructions are not copied.
1368 // Also, identify local variables whose values need to be copied into or
1369 // out of the new outlined method, and builds up targetMap and
1370 // localVarMap as described above. The code identifies those local
1371 // variables first so that they can have fixed slots in the stack
1372 // frame for the outlined method assigned them ahead of all those
1373 // variables that don't need to exist for the entirety of the outlined
1374 // method invocation.
1375 for (InstructionHandle ih = first; ih != limit; ih = ih.getNext()) {
1376 Instruction inst = ih.getInstruction();
1377
1378 // MarkerInstructions are not copied, so if something else targets
1379 // one, the targetMap will point to the nearest copied sibling
1380 // InstructionHandle: for an OutlineableChunkEnd, the nearest
1381 // preceding sibling; for an OutlineableChunkStart, the nearest
1382 // following sibling.
1383 if (inst instanceof MarkerInstruction) {
1384 if (ih.hasTargeters()) {
1385 if (inst instanceof OutlineableChunkEnd) {
1386 targetMap.put(ih, lastCopyHandle);
1387 } else {
1388 if (!chunkStartTargetMappingsPending) {
1389 chunkStartTargetMappingsPending = true;
1390 pendingTargetMappingHandle = ih;
1391 }
1392 }
1393 }
1394 } else {
1395 // Copy the instruction and append it to the outlined method's
1396 // InstructionList.
1397 Instruction c = inst.copy(); // Use clone for shallow copy
1398
1399 if (c instanceof BranchInstruction) {
1400 lastCopyHandle = newIL.append((BranchInstruction)c);
1401 } else {
1402 lastCopyHandle = newIL.append(c);
1403 }
1404
1405 if (c instanceof LocalVariableInstruction
1406 || c instanceof RET) {
1407 // For any instruction that touches a local variable,
1408 // check whether the local variable's value needs to be
1409 // copied into or out of the outlined method. If so,
1410 // generate the code to perform the necessary copying, and
1411 // use localVarMap to map the variable in the original
1412 // method to the variable in the new method.
1413 IndexedInstruction lvi = (IndexedInstruction)c;
1414 int oldLocalVarIndex = lvi.getIndex();
1415 LocalVariableGen oldLVG =
1416 getLocalVariableRegistry()
1417 .lookupRegisteredLocalVariable(oldLocalVarIndex,
1418 ih.getPosition());
1419 LocalVariableGen newLVG =
1420 (LocalVariableGen)localVarMap.get(oldLVG);
1421
1422 // Has the code already mapped this local variable to a
1423 // local in the new method?
1424 if (localVarMap.get(oldLVG) == null) {
1425 // Determine whether the local variable needs to be
1426 // copied into or out of the outlined by checking
1427 // whether the range of instructions in which the
1428 // variable is accessible is outside the range of
1429 // instructions in the outlineable chunk.
1430 // Special case a chunk start offset of zero: a local
1431 // variable live at that position must be a method
1432 // parameter, so the code doesn't need to check whether
1433 // the variable is live before that point; being live
1434 // at offset zero is sufficient to know that the value
1435 // must be copied in to the outlined method.
1436 boolean copyInLocalValue =
1437 offsetInLocalVariableGenRange(oldLVG,
1438 (outlineChunkStartOffset != 0)
1439 ? outlineChunkStartOffset-1
1440 : 0);
1441 boolean copyOutLocalValue =
1442 offsetInLocalVariableGenRange(oldLVG,
1443 outlineChunkEndOffset+1);
1444
1445 // For any variable that needs to be copied into or out
1446 // of the outlined method, create a field in the
1447 // CopyLocals class, and generate the necessary code for
1448 // copying the value.
1449 if (copyInLocalValue || copyOutLocalValue) {
1450 String varName = oldLVG.getName();
1451 Type varType = oldLVG.getType();
1452 newLVG = outlinedMethodGen.addLocalVariable(varName,
1453 varType,
1454 null,
1455 null);
1456 int newLocalVarIndex = newLVG.getIndex();
1457 String varSignature = varType.getSignature();
1458
1459 // Record the mapping from the old local to the new
1460 localVarMap.put(oldLVG, newLVG);
1461
1462 copyAreaFieldCount++;
1463 String copyAreaFieldName =
1464 "field" + copyAreaFieldCount;
1465 copyAreaCG.addField(
1466 new Field(ACC_PUBLIC,
1467 copyAreaCPG.addUtf8(copyAreaFieldName),
1468 copyAreaCPG.addUtf8(varSignature),
1469 null, copyAreaCPG.getConstantPool()));
1470
1471 int fieldRef = cpg.addFieldref(argTypeName,
1472 copyAreaFieldName,
1473 varSignature);
1474
1475 if (copyInLocalValue) {
1476 // Generate code for the old method to store the
1477 // value of the local into the correct field in
1478 // CopyLocals prior to invocation of the
1479 // outlined method.
1480 oldMethCopyInIL.append(
1481 InstructionConstants.DUP);
1482 InstructionHandle copyInLoad =
1483 oldMethCopyInIL.append(
1484 loadLocal(oldLocalVarIndex, varType));
1485 oldMethCopyInIL.append(new PUTFIELD(fieldRef));
1486
1487 // If the end of the live range of the old
1488 // variable was in the middle of the outlined
1489 // chunk. Make the load of its value the new
1490 // end of its range.
1491 if (!copyOutLocalValue) {
1492 revisedLocalVarEnd.put(oldLVG, copyInLoad);
1493 }
1494
1495 // Generate code for start of the outlined
1496 // method to copy the value from a field in
1497 // CopyLocals to the new local in the outlined
1498 // method
1499 newMethCopyInIL.append(
1500 InstructionConstants.ALOAD_1);
1501 newMethCopyInIL.append(new GETFIELD(fieldRef));
1502 newMethCopyInIL.append(
1503 storeLocal(newLocalVarIndex, varType));
1504 }
1505
1506 if (copyOutLocalValue) {
1507 // Generate code for the end of the outlined
1508 // method to copy the value from the new local
1509 // variable into a field in CopyLocals
1510 // method
1511 newMethCopyOutIL.append(
1512 InstructionConstants.ALOAD_1);
1513 newMethCopyOutIL.append(
1514 loadLocal(newLocalVarIndex, varType));
1515 newMethCopyOutIL.append(new PUTFIELD(fieldRef));
1516
1517 // Generate code to copy the value from a field
1518 // in CopyLocals into a local in the original
1519 // method following invocation of the outlined
1520 // method.
1521 oldMethCopyOutIL.append(
1522 InstructionConstants.DUP);
1523 oldMethCopyOutIL.append(new GETFIELD(fieldRef));
1524 InstructionHandle copyOutStore =
1525 oldMethCopyOutIL.append(
1526 storeLocal(oldLocalVarIndex, varType));
1527
1528 // If the start of the live range of the old
1529 // variable was in the middle of the outlined
1530 // chunk. Make this store into it the new start
1531 // of its range.
1532 if (!copyInLocalValue) {
1533 revisedLocalVarStart.put(oldLVG,
1534 copyOutStore);
1535 }
1536 }
1537 }
1538 }
1539 }
1540
1541 if (ih.hasTargeters()) {
1542 targetMap.put(ih, lastCopyHandle);
1543 }
1544
1545 // If this is the first instruction copied following a sequence
1546 // of OutlineableChunkStart instructions, indicate that the
1547 // sequence of old instruction all map to this newly created
1548 // instruction
1549 if (chunkStartTargetMappingsPending) {
1550 do {
1551 targetMap.put(pendingTargetMappingHandle,
1552 lastCopyHandle);
1553 pendingTargetMappingHandle =
1554 pendingTargetMappingHandle.getNext();
1555 } while(pendingTargetMappingHandle != ih);
1556
1557 chunkStartTargetMappingsPending = false;
1558 }
1559 }
1560 }
1561
1562 // Pass 2: Walk old and new instruction lists, updating branch targets
1563 // and local variable references in the new list
1564 InstructionHandle ih = first;
1565 InstructionHandle ch = newIL.getStart();
1566
1567 while (ch != null) {
1568 // i == old instruction; c == copied instruction
1569 Instruction i = ih.getInstruction();
1570 Instruction c = ch.getInstruction();
1571
1572 if (i instanceof BranchInstruction) {
1573 BranchInstruction bc = (BranchInstruction)c;
1574 BranchInstruction bi = (BranchInstruction)i;
1575 InstructionHandle itarget = bi.getTarget(); // old target
1576
1577 // New target must be in targetMap
1578 InstructionHandle newTarget =
1579 (InstructionHandle)targetMap.get(itarget);
1580
1581 bc.setTarget(newTarget);
1582
1583 // Handle LOOKUPSWITCH or TABLESWITCH which may have many
1584 // target instructions
1585 if (bi instanceof Select) {
1586 InstructionHandle[] itargets = ((Select)bi).getTargets();
1587 InstructionHandle[] ctargets = ((Select)bc).getTargets();
1588
1589 // Update all targets
1590 for (int j=0; j < itargets.length; j++) {
1591 ctargets[j] =
1592 (InstructionHandle)targetMap.get(itargets[j]);
1593 }
1594 }
1595 } else if (i instanceof LocalVariableInstruction
1596 || i instanceof RET) {
1597 // For any instruction that touches a local variable,
1598 // map the location of the variable in the original
1599 // method to its location in the new method.
1600 IndexedInstruction lvi = (IndexedInstruction)c;
1601 int oldLocalVarIndex = lvi.getIndex();
1602 LocalVariableGen oldLVG =
1603 getLocalVariableRegistry()
1604 .lookupRegisteredLocalVariable(oldLocalVarIndex,
1605 ih.getPosition());
1606 LocalVariableGen newLVG =
1607 (LocalVariableGen)localVarMap.get(oldLVG);
1608 int newLocalVarIndex;
1609
1610 if (newLVG == null) {
1611 // Create new variable based on old variable - use same
1612 // name and type, but we will let the variable be active
1613 // for the entire outlined method.
1614 // LocalVariableGen oldLocal = oldLocals[oldLocalVarIndex];
1615 String varName = oldLVG.getName();
1616 Type varType = oldLVG.getType();
1617 newLVG = outlinedMethodGen.addLocalVariable(varName,
1618 varType,
1619 null,
1620 null);
1621 newLocalVarIndex = newLVG.getIndex();
1622 localVarMap.put(oldLVG, newLVG);
1623
1624 // The old variable's live range was wholly contained in
1625 // the outlined chunk. There should no longer be stores
1626 // of values into it or loads of its value, so we can just
1627 // mark its live range as the reference to the outlined
1628 // method.
1629 revisedLocalVarStart.put(oldLVG, outlinedMethodRef);
1630 revisedLocalVarEnd.put(oldLVG, outlinedMethodRef);
1631 } else {
1632 newLocalVarIndex = newLVG.getIndex();
1633 }
1634 lvi.setIndex(newLocalVarIndex);
1635 }
1636
1637 // If the old instruction marks the end of the range of a local
1638 // variable, make sure that any slots on the stack reserved for
1639 // local variables are made available for reuse by calling
1640 // MethodGenerator.removeLocalVariable
1641 if (ih.hasTargeters()) {
1642 InstructionTargeter[] targeters = ih.getTargeters();
1643
1644 for (int idx = 0; idx < targeters.length; idx++) {
1645 InstructionTargeter targeter = targeters[idx];
1646
1647 if (targeter instanceof LocalVariableGen
1648 && ((LocalVariableGen)targeter).getEnd()==ih) {
1649 Object newLVG = localVarMap.get(targeter);
1650 if (newLVG != null) {
1651 outlinedMethodGen.removeLocalVariable(
1652 (LocalVariableGen)newLVG);
1653 }
1654 }
1655 }
1656 }
1657
1658 // If the current instruction in the original list was a marker,
1659 // it wasn't copied, so don't advance through the list of copied
1660 // instructions yet.
1661 if (!(i instanceof MarkerInstruction)) {
1662 ch = ch.getNext();
1663 }
1664 ih = ih.getNext();
1665
1666 }
1667
1668 // POP the reference to the CopyLocals object from the stack
1669 oldMethCopyOutIL.append(InstructionConstants.POP);
1670
1671 // Now that the generation of the outlined code is complete, update
1672 // the old local variables with new start and end ranges, as required.
1673 Iterator revisedLocalVarStartPairIter = revisedLocalVarStart.entrySet()
1674 .iterator();
1675 while (revisedLocalVarStartPairIter.hasNext()) {
1676 Map.Entry lvgRangeStartPair =
1677 (Map.Entry)revisedLocalVarStartPairIter.next();
1678 LocalVariableGen lvg = (LocalVariableGen)lvgRangeStartPair.getKey();
1679 InstructionHandle startInst =
1680 (InstructionHandle)lvgRangeStartPair.getValue();
1681
1682 lvg.setStart(startInst);
1683
1684 }
1685
1686 Iterator revisedLocalVarEndPairIter = revisedLocalVarEnd.entrySet()
1687 .iterator();
1688 while (revisedLocalVarEndPairIter.hasNext()) {
1689 Map.Entry lvgRangeEndPair =
1690 (Map.Entry)revisedLocalVarEndPairIter.next();
1691 LocalVariableGen lvg = (LocalVariableGen)lvgRangeEndPair.getKey();
1692 InstructionHandle endInst =
1693 (InstructionHandle)lvgRangeEndPair.getValue();
1694
1695 lvg.setEnd(endInst);
1696 }
1697
1698 xsltc.dumpClass(copyAreaCG.getJavaClass());
1699
1700 // Assemble the instruction lists so that the old method invokes the
1701 // new outlined method
1702 InstructionList oldMethodIL = getInstructionList();
1703
1704 oldMethodIL.insert(first, oldMethCopyInIL);
1705 oldMethodIL.insert(first, oldMethCopyOutIL);
1706
1707 // Insert the copying code into the outlined method
1708 newIL.insert(newMethCopyInIL);
1709 newIL.append(newMethCopyOutIL);
1710 newIL.append(InstructionConstants.RETURN);
1711
1712 // Discard instructions in outlineable chunk from old method
1713 try {
1714 oldMethodIL.delete(first, last);
1715 } catch (TargetLostException e) {
1716 InstructionHandle[] targets = e.getTargets();
1717 // If there were still references to old instructions lingering,
1718 // clean those up. The only instructions targetting the deleted
1719 // instructions should have been part of the chunk that was just
1720 // deleted, except that instructions might branch to the start of
1721 // the outlined chunk; similarly, all the live ranges of local
1722 // variables should have been adjusted, except for unreferenced
1723 // variables.
1724 for (int i = 0; i < targets.length; i++) {
1725 InstructionHandle lostTarget = targets[i];
1726 InstructionTargeter[] targeters = lostTarget.getTargeters();
1727 for (int j = 0; j < targeters.length; j++) {
1728 if (targeters[j] instanceof LocalVariableGen) {
1729 LocalVariableGen lvgTargeter =
1730 (LocalVariableGen) targeters[j];
1731 // In the case of any lingering variable references,
1732 // just make the live range point to the outlined
1733 // function reference. Such variables should be unused
1734 // anyway.
1735 if (lvgTargeter.getStart() == lostTarget) {
1736 lvgTargeter.setStart(outlinedMethodRef);
1737 }
1738 if (lvgTargeter.getEnd() == lostTarget) {
1739 lvgTargeter.setEnd(outlinedMethodRef);
1740 }
1741 } else {
1742 targeters[j].updateTarget(lostTarget,
1743 outlinedMethodCallSetup);
1744 }
1745 }
1746 }
1747 }
1748
1749 // Make a copy for the new method of all exceptions that might be thrown
1750 String[] exceptions = getExceptions();
1751 for (int i = 0; i < exceptions.length; i++) {
1752 outlinedMethodGen.addException(exceptions[i]);
1753 }
1754
1755 return outlinedMethodGen.getThisMethod();
1756 }
1757
1758 /**
1759 * Helper method to generate an instance of a subclass of
1760 * {@link LoadInstruction} based on the specified {@link Type} that will
1761 * load the specified local variable
1762 * @param index the JVM stack frame index of the variable that is to be
1763 * loaded
1764 * @param type the {@link Type} of the variable
1765 * @return the generated {@link LoadInstruction}
1766 */
1767 private static Instruction loadLocal(int index, Type type) {
1768 if (type == Type.BOOLEAN) {
1769 return new ILOAD(index);
1770 } else if (type == Type.INT) {
1771 return new ILOAD(index);
1772 } else if (type == Type.SHORT) {
1773 return new ILOAD(index);
1774 } else if (type == Type.LONG) {
1775 return new LLOAD(index);
1776 } else if (type == Type.BYTE) {
1777 return new ILOAD(index);
1778 } else if (type == Type.CHAR) {
1779 return new ILOAD(index);
1780 } else if (type == Type.FLOAT) {
1781 return new FLOAD(index);
1782 } else if (type == Type.DOUBLE) {
1783 return new DLOAD(index);
1784 } else {
1785 return new ALOAD(index);
1786 }
1787 }
1788
1789 /**
1790 * Helper method to generate an instance of a subclass of
1791 * {@link StoreInstruction} based on the specified {@link Type} that will
1792 * store a value in the specified local variable
1793 * @param index the JVM stack frame index of the variable that is to be
1794 * stored
1795 * @param type the {@link Type} of the variable
1796 * @return the generated {@link StoredInstruction}
1797 */
1798 private static Instruction storeLocal(int index, Type type) {
1799 if (type == Type.BOOLEAN) {
1800 return new ISTORE(index);
1801 } else if (type == Type.INT) {
1802 return new ISTORE(index);
1803 } else if (type == Type.SHORT) {
1804 return new ISTORE(index);
1805 } else if (type == Type.LONG) {
1806 return new LSTORE(index);
1807 } else if (type == Type.BYTE) {
1808 return new ISTORE(index);
1809 } else if (type == Type.CHAR) {
1810 return new ISTORE(index);
1811 } else if (type == Type.FLOAT) {
1812 return new FSTORE(index);
1813 } else if (type == Type.DOUBLE) {
1814 return new DSTORE(index);
1815 } else {
1816 return new ASTORE(index);
1817 }
1818 }
1819
1820 /**
1821 * Track the number of outlineable chunks seen.
1822 */
1823 private int m_totalChunks = 0;
1824
1825 /**
1826 * Track the number of outlineable chunks started but not yet ended. Used
1827 * to detect imbalances in byte code generation.
1828 */
1829 private int m_openChunks = 0;
1830
1831 /**
1832 * Mark the end of the method's
1833 * {@link InstructionList} as the start of an outlineable chunk of code.
1834 * The outlineable chunk begins after the {@link InstructionHandle} that is
1835 * at the end of the method's {@link InstructionList}, or at the start of
1836 * the method if the <code>InstructionList</code> is empty.
1837 * See {@link OutlineableChunkStart} for more information.
1838 */
1839 public void markChunkStart() {
1840 // m_chunkTree.markChunkStart();
1841 getInstructionList()
1842 .append(OutlineableChunkStart.OUTLINEABLECHUNKSTART);
1843 m_totalChunks++;
1844 m_openChunks++;
1845 }
1846
1847 /**
1848 * Mark the end of an outlineable chunk of code. See
1849 * {@link OutlineableChunkStart} for more information.
1850 */
1851 public void markChunkEnd() {
1852 // m_chunkTree.markChunkEnd();
1853 getInstructionList()
1854 .append(OutlineableChunkEnd.OUTLINEABLECHUNKEND);
1855 m_openChunks--;
1856 if (m_openChunks < 0) {
1857 String msg = (new ErrorMsg(ErrorMsg.OUTLINE_ERR_UNBALANCED_MARKERS))
1858 .toString();
1859 throw new InternalError(msg);
1860 }
1861 }
1862
1863 /**
1864 * <p>Get all {@link Method}s generated by this {@link MethodGenerator}.
1865 * The {@link MethodGen#getMethod()} only returns a single
1866 * <code>Method</code> object. This method takes into account the Java
1867 * Virtual Machine Specification limit of 64KB on the size of a method, and
1868 * may return more than one <code>Method</code>.</p>
1869 * <p>If the code associated with the <code>MethodGenerator</code> would
1870 * exceed the 64KB limit, this method will attempt to split the code in
1871 * the {@link InstructionList} associated with this
1872 * <code>MethodGenerator</code> into several methods.</p>
1873 * @param classGen the {@link ClassGenerator} of which these methods are
1874 * members
1875 * @return an array of all the <code>Method</code>s generated
1876 */
1877 Method[] getGeneratedMethods(ClassGenerator classGen) {
1878 Method[] generatedMethods;
1879 InstructionList il = getInstructionList();
1880 InstructionHandle last = il.getEnd();
1881
1882 il.setPositions();
1883
1884 int instructionListSize =
1885 last.getPosition() + last.getInstruction().getLength();
1886
1887 // Need to look for any branch target offsets that exceed the range
1888 // [-32768,32767]
1889 if (instructionListSize > MAX_BRANCH_TARGET_OFFSET) {
1890 boolean ilChanged = widenConditionalBranchTargetOffsets();
1891
1892 // If any branch instructions needed widening, recompute the size
1893 // of the byte code for the method
1894 if (ilChanged) {
1895 il.setPositions();
1896 last = il.getEnd();
1897 instructionListSize =
1898 last.getPosition() + last.getInstruction().getLength();
1899 }
1900 }
1901
1902 if (instructionListSize > MAX_METHOD_SIZE) {
1903 generatedMethods = outlineChunks(classGen, instructionListSize);
1904 } else {
1905 generatedMethods = new Method[] {getThisMethod()};
1906 }
1907 return generatedMethods;
1908 }
1909
1910 protected Method getThisMethod() {
1911 stripAttributes(true);
1912 setMaxLocals();
1913 setMaxStack();
1914 removeNOPs();
1915
1916 return getMethod();
1917 }
1918 /**
1919 * <p>Rewrites branches to avoid the JVM limits of relative branch
1920 * offsets. There is no need to invoke this method if the bytecode for the
1921 * {@link MethodGenerator} does not exceed 32KB.</p>
1922 * <p>The Java Virtual Machine Specification permits the code portion of a
1923 * method to be up to 64KB in length. However, some control transfer
1924 * instructions specify relative offsets as a signed 16-bit quantity,
1925 * limiting the range to a subset of the instructions that might be in a
1926 * method.</p>
1927 * <p>The <code>TABLESWITCH</code> and <code>LOOKUPSWITCH</code>
1928 * instructions always use 32-bit signed relative offsets, so they are
1929 * immune to this problem.</p>
1930 * <p>The <code>GOTO</code> and <code>JSR</code>
1931 * instructions come in two forms, one of which uses 16-bit relative
1932 * offsets, and the other of which uses 32-bit relative offsets. The BCEL
1933 * library decides whether to use the wide form of <code>GOTO</code> or
1934 * <code>JSR</code>instructions based on the relative offset of the target
1935 * of the instruction without any intervention by the user of the
1936 * library.</p>
1937 * <p>This leaves the various conditional branch instructions,
1938 * <code>IFEQ</code>, <code>IFNULL</code>, <code>IF_ICMPEQ</code>,
1939 * <em>et al.</em>, all of which use 16-bit signed relative offsets, with no
1940 * 32-bit wide form available.</p>
1941 * <p>This method scans the {@link InstructionList} associated with this
1942 * {@link MethodGenerator} and finds all conditional branch instructions
1943 * that might exceed the 16-bit limitation for relative branch offsets.
1944 * The logic of each such instruction is inverted, and made to target the
1945 * instruction which follows it. An unconditional branch to the original
1946 * target of the instruction is then inserted between the conditional
1947 * branch and the instruction which previously followed it. The
1948 * unconditional branch is permitted to have a 16-bit or a 32-bit relative
1949 * offset, as described above. For example,
1950 * <code>
1951 * 1234: NOP
1952 * ...
1953 * 55278: IFEQ -54044
1954 * 55280: NOP
1955 * </code>
1956 * is rewritten as
1957 * <code>
1958 * 1234: NOP
1959 * ...
1960 * 55278: IFNE 7
1961 * 55280: GOTO_W -54046
1962 * 55285: NOP
1963 * </code></p>
1964 * <p><b>Preconditions:</b>
1965 * <ul><li>The {@link InstructionList#setPositions()} has been called for
1966 * the <code>InstructionList</code> associated with this
1967 * <code>MethodGenerator</code>.
1968 * </li></ul></p>
1969 * <p><b>Postconditions:</b>
1970 * <ul><li>Any further changes to the <code>InstructionList</code> for this
1971 * <code>MethodGenerator</code> will invalidate the changes made by this
1972 * method.</li></ul>
1973 * </p>
1974 * @return <code>true</code> if the <code>InstructionList</code> was
1975 * modified; <code>false</code> otherwise
1976 * @see The Java Virtual Machine Specification, Second Edition
1977 */
1978 boolean widenConditionalBranchTargetOffsets() {
1979 boolean ilChanged = false;
1980 int maxOffsetChange = 0;
1981 InstructionList il = getInstructionList();
1982
1983 // Loop through all the instructions, finding those that would be
1984 // affected by inserting new instructions in the InstructionList, and
1985 // calculating the maximum amount by which the relative offset between
1986 // two instructions could possibly change.
1987 // In part this loop duplicates code in
1988 // org.apache.bcel.generic.InstructionList.setPosition(), which does
1989 // this to determine whether to use 16-bit or 32-bit offsets for GOTO
1990 // and JSR instructions. Ideally, that method would do the same for
1991 // conditional branch instructions, but it doesn't, so we duplicate the
1992 // processing here.
1993 for (InstructionHandle ih = il.getStart();
1994 ih != null;
1995 ih = ih.getNext()) {
1996 Instruction inst = ih.getInstruction();
1997
1998 switch (inst.getOpcode()) {
1999 // Instructions that may have 16-bit or 32-bit branch targets.
2000 // The size of the branch offset might increase by two bytes.
2001 case Constants.GOTO:
2002 case Constants.JSR:
2003 maxOffsetChange = maxOffsetChange + 2;
2004 break;
2005 // Instructions that contain padding for alignment purposes
2006 // Up to three bytes of padding might be needed. For greater
2007 // accuracy, we should be able to discount any padding already
2008 // added to these instructions by InstructionList.setPosition(),
2009 // their APIs do not expose that information.
2010 case Constants.TABLESWITCH:
2011 case Constants.LOOKUPSWITCH:
2012 maxOffsetChange = maxOffsetChange + 3;
2013 break;
2014 // Instructions that might be rewritten by this method as a
2015 // conditional branch followed by an unconditional branch.
2016 // The unconditional branch would require five bytes.
2017 case Constants.IF_ACMPEQ:
2018 case Constants.IF_ACMPNE:
2019 case Constants.IF_ICMPEQ:
2020 case Constants.IF_ICMPGE:
2021 case Constants.IF_ICMPGT:
2022 case Constants.IF_ICMPLE:
2023 case Constants.IF_ICMPLT:
2024 case Constants.IF_ICMPNE:
2025 case Constants.IFEQ:
2026 case Constants.IFGE:
2027 case Constants.IFGT:
2028 case Constants.IFLE:
2029 case Constants.IFLT:
2030 case Constants.IFNE:
2031 case Constants.IFNONNULL:
2032 case Constants.IFNULL:
2033 maxOffsetChange = maxOffsetChange + 5;
2034 break;
2035 }
2036 }
2037
2038 // Now that the maximum number of bytes by which the method might grow
2039 // has been determined, look for conditional branches to see which
2040 // might possibly exceed the 16-bit relative offset.
2041 for (InstructionHandle ih = il.getStart();
2042 ih != null;
2043 ih = ih.getNext()) {
2044 Instruction inst = ih.getInstruction();
2045
2046 if (inst instanceof IfInstruction) {
2047 IfInstruction oldIfInst = (IfInstruction)inst;
2048 BranchHandle oldIfHandle = (BranchHandle)ih;
2049 InstructionHandle target = oldIfInst.getTarget();
2050 int relativeTargetOffset = target.getPosition()
2051 - oldIfHandle.getPosition();
2052
2053 // Consider the worst case scenario in which the conditional
2054 // branch and its target are separated by all the instructions
2055 // in the method that might increase in size. If that results
2056 // in a relative offset that cannot be represented as a 32-bit
2057 // signed quantity, rewrite the instruction as described above.
2058 if ((relativeTargetOffset - maxOffsetChange
2059 < MIN_BRANCH_TARGET_OFFSET)
2060 || (relativeTargetOffset + maxOffsetChange
2061 > MAX_BRANCH_TARGET_OFFSET)) {
2062 // Invert the logic of the IF instruction, and append
2063 // that to the InstructionList following the original IF
2064 // instruction
2065 InstructionHandle nextHandle = oldIfHandle.getNext();
2066 IfInstruction invertedIfInst = oldIfInst.negate();
2067 BranchHandle invertedIfHandle = il.append(oldIfHandle,
2068 invertedIfInst);
2069
2070 // Append an unconditional branch to the target of the
2071 // original IF instruction after the new IF instruction
2072 BranchHandle gotoHandle = il.append(invertedIfHandle,
2073 new GOTO(target));
2074
2075 // If the original IF was the last instruction in
2076 // InstructionList, add a new no-op to act as the target
2077 // of the new IF
2078 if (nextHandle == null) {
2079 nextHandle = il.append(gotoHandle, NOP);
2080 }
2081
2082 // Make the new IF instruction branch around the GOTO
2083 invertedIfHandle.updateTarget(target, nextHandle);
2084
2085 // If anything still "points" to the old IF instruction,
2086 // make adjustments to refer to either the new IF or GOTO
2087 // instruction
2088 if (oldIfHandle.hasTargeters()) {
2089 InstructionTargeter[] targeters =
2090 oldIfHandle.getTargeters();
2091
2092 for (int i = 0; i < targeters.length; i++) {
2093 InstructionTargeter targeter = targeters[i];
2094 // Ideally, one should simply be able to use
2095 // InstructionTargeter.updateTarget to change
2096 // references to the old IF instruction to the new
2097 // IF instruction. However, if a LocalVariableGen
2098 // indicated the old IF marked the end of the range
2099 // in which the IF variable is in use, the live
2100 // range of the variable must extend to include the
2101 // newly created GOTO instruction. The need for
2102 // this sort of specific knowledge of an
2103 // implementor of the InstructionTargeter interface
2104 // makes the code more fragile. Future implementors
2105 // of the interface might have similar requirements
2106 // which wouldn't be accommodated seemlessly.
2107 if (targeter instanceof LocalVariableGen) {
2108 LocalVariableGen lvg =
2109 (LocalVariableGen) targeter;
2110 if (lvg.getStart() == oldIfHandle) {
2111 lvg.setStart(invertedIfHandle);
2112 } else if (lvg.getEnd() == oldIfHandle) {
2113 lvg.setEnd(gotoHandle);
2114 }
2115 } else {
2116 targeter.updateTarget(oldIfHandle,
2117 invertedIfHandle);
2118 }
2119 }
2120 }
2121
2122 try {
2123 il.delete(oldIfHandle);
2124 } catch (TargetLostException tle) {
2125 // This can never happen - we updated the list of
2126 // instructions that target the deleted instruction
2127 // prior to deleting it.
2128 String msg =
2129 new ErrorMsg(ErrorMsg.OUTLINE_ERR_DELETED_TARGET,
2130 tle.getMessage()).toString();
2131 throw new InternalError(msg);
2132 }
2133
2134 // Adjust the pointer in the InstructionList to point after
2135 // the newly inserted IF instruction
2136 ih = gotoHandle;
2137
2138 // Indicate that this method rewrote at least one IF
2139 ilChanged = true;
2140 }
2141 }
2142 }
2143
2144 // Did this method rewrite any IF instructions?
2145 return ilChanged;
2146 }
2147 }