001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package EDU.purdue.cs.bloat.inline;
022:
023: import java.util.*;
024:
025: import EDU.purdue.cs.bloat.editor.*;
026: import EDU.purdue.cs.bloat.util.*;
027:
028: /**
029: * Performs call site specialization for virtual method invocations. At each
030: * virtual method invocation, the call graph is consulted to determine which
031: * methods the call site could resolve to. The virtual call site is converted
032: * into a "switch" on the method receiver. Each "case" corresponds to a possible
033: * type that the receiver may take on. Inside the "case" branch, the receiver is
034: * cast to the expected type. Finally, a static version of the virtual method is
035: * called. In the "default" case, the virtual method is invoked.
036: */
037: public class Specialize implements Opcode {
038: public static boolean DEBUG = false;
039:
040: public static boolean DB_STATIC = false;
041:
042: public static boolean PRINTCODE = false;
043:
044: public static boolean STATS = false;
045:
046: public static boolean NOSTATIC = false;
047:
048: public static boolean USE_PREEXISTS = true;
049:
050: private final Map staticMethods = new HashMap();
051:
052: private final Set specialized = new HashSet(); // calls that have
053: // specialized
054:
055: private InlineStats stats;
056:
057: /**
058: * Maximum number of specializations per call site
059: */
060: public static int MAX_MORPH = 5;
061:
062: /**
063: * Do we specialize monomorphic call sites? By default, <tt>false</tt>.
064: */
065: public static boolean MONO = false;
066:
067: private InlineContext context;
068:
069: private static void db(final String s) {
070: if (Specialize.DEBUG) {
071: System.out.println(s);
072: }
073: }
074:
075: /**
076: * Constructor.
077: */
078: public Specialize(final InlineContext context) {
079: this .context = context;
080:
081: stats = context.getInlineStats();
082: }
083:
084: /**
085: * Examines the virtual method call sites in a method and specializes them
086: * based on the resolves-to information found in the call graph.
087: *
088: * @return <tt>true</tt>, if the method was modified (that is, it
089: * requires committing)
090: */
091: public boolean specialize(final MethodEditor method) {
092: if (method.isNative()) {
093: // Can't do anything with native methods
094: return (false);
095: }
096:
097: // Do we ignore this method
098: if (context.ignoreMethod(method.memberRef())) {
099: return (false);
100: }
101:
102: Specialize.db("\nSpecializing "
103: + method.declaringClass().name() + "." + method.name()
104: + method.type());
105:
106: // Okay, what are we doing here? The first task is to find
107: // virtual call sites. That's easy. Finding the code that pushes
108: // the call's arguments is not so easy. We use the following
109: // method. At each instruction we use a InstructionStack to keep
110: // track of what the stack looks like. That is, we want to know
111: // which instructions push which stack elements. Thus, at a call
112: // site we can easily determine which instruction(s) (yes, there
113: // might be more than one) push the receiver object on the stack.
114: // We insert a dup and a store into a local variable after these
115: // instructions. Back at the call site we load from the local
116: // variable and specialize away. This method only adds a couple
117: // of instructions and can handle all sort of bizzare control
118: // flow.
119:
120: final CallGraph cg = context.getCallGraph();
121: boolean changed = false;
122: final InstructionStack stack = new InstructionStack(method);
123:
124: // Go through the code looking for call sites. Along the way keep
125: // track of the stack.
126: final List code = method.code();
127:
128: for (int i = 0; i < code.size(); i++) {
129: final Object o = code.get(i);
130: if (o instanceof Instruction) {
131: final Instruction inst = (Instruction) o;
132:
133: if ((inst.opcodeClass() == Opcode.opcx_invokevirtual)
134: || (inst.opcodeClass() == Opcode.opcx_invokeinterface)) {
135: // Found a virtual method call
136: Specialize.db(" Call: " + inst);
137:
138: final MemberRef callee = (MemberRef) inst.operand();
139:
140: // Do we ignore the callee?
141: if (context.ignoreMethod(callee)) {
142: Specialize
143: .db(" Explicitly ignoring this method");
144: stack.handle(inst);
145: continue;
146: }
147:
148: MethodEditor me = null;
149: try {
150: me = context.editMethod(callee);
151:
152: } catch (final NoSuchMethodException ex0) {
153: System.err.println("** Cannot find method "
154: + callee);
155: ex0.printStackTrace(System.err);
156: System.exit(1);
157: }
158:
159: if (me.isFinal() && !me.isNative()) {
160: // Ah, we have a final method. Just convert it to a
161: // static method.
162: Specialize.db(" Converting final method "
163: + callee + " to static");
164:
165: final int index = code.indexOf(inst);
166: final Instruction newInst = new Instruction(
167: Opcode.opcx_invokespecial, me
168: .memberRef());
169: code.add(index, newInst);
170: code.remove(inst);
171: stack.handle(newInst);
172:
173: // Make note of call
174: continue;
175: }
176:
177: // Calculate the number of stack slots needed to hold the
178: // callee's arguments.
179: final int nArgs = callee.nameAndType().type()
180: .paramTypes().length;
181:
182: // Determine the instructions that push the receiver on the
183: // stack. Make note of these.
184: final Set pushes = stack.atDepth(nArgs);
185: if (Specialize.DEBUG) {
186: Specialize
187: .db(" Receiver on stack after: "
188: + (stack
189: .preexistsAtDepth(nArgs) != null ? " (preexists)"
190: : ""));
191: final Iterator pushies = pushes.iterator();
192: while (pushies.hasNext()) {
193: final Instruction push = (Instruction) pushies
194: .next();
195: Specialize.db(" " + code.indexOf(push)
196: + ") " + push);
197: }
198: }
199:
200: Set set = null; // Method call could resolve to
201: if (Specialize.USE_PREEXISTS) {
202: // If the receiver is not preexistent, then we can't
203: // safely inline the method. Don't bother converting it
204: // into a static method.
205: final Set preexists = stack
206: .preexistsAtDepth(nArgs);
207: if (preexists == null) {
208: stack.handle(inst);
209: if (Specialize.STATS) {
210: stats.noteNoPreexist();
211: }
212: Specialize
213: .db(" Receiver does not preexist");
214: continue;
215: }
216:
217: // If the preexists is non-empty, then it contains the
218: // type(s) that we know the receiver can take on. Remove
219: // all others from the set of possible receiver types.
220: // Wicked awesome!
221: if (!preexists.isEmpty()) {
222: set = cg.resolvesTo(callee, preexists);
223: ;
224:
225: if (Specialize.DEBUG) {
226: final StringBuffer sb = new StringBuffer(
227: " retaining: ");
228: final Iterator iter = preexists
229: .iterator();
230: while (iter.hasNext()) {
231: final Type type = (Type) iter
232: .next();
233: sb.append(Type.truncatedName(type));
234: if (iter.hasNext()) {
235: sb.append(", ");
236: }
237: }
238: Specialize.db(sb.toString());
239: }
240: }
241: }
242:
243: if (set == null) {
244: set = cg.resolvesTo(callee);
245: }
246:
247: if ((set == null) || set.isEmpty()
248: || specialized.contains(inst)) {
249: // What does it mean if a call has no call sites? Well,
250: // it means that no class that implements the method is
251: // created. So, either we have a null pointer exception
252: // waiting to happen or the class is instantiated in
253: // someplace that we don't analyze (e.g. native
254: // methods).
255: Specialize
256: .db(" "
257: + (specialized.contains(inst) ? "Call already handled"
258: : "Resolves to no methods")
259: + ". Ignoring.");
260:
261: // Don't forget to update the stack
262: stack.handle(inst);
263: continue;
264: }
265:
266: specialized.add(inst);
267:
268: if (Specialize.STATS) {
269: // Make note of the number of methods a call site
270: // resolves
271: // to
272: stats.noteMorphicity(set.size());
273: }
274:
275: if (set.size() > Specialize.MAX_MORPH) {
276: // If we only care about monomorphic calls sites, then
277: // go
278: // home.
279: stack.handle(inst);
280: continue;
281: }
282:
283: // Don't update the stack if the call is specialized. This
284: // will all get taken care of later.
285:
286: // Okay, it's showtime. Originally, I specialized all of
287: // the call sites after I had visited the entire method.
288: // However, this was incorrect because specialized code may
289: // push the receiver on the stack. Bummer.
290:
291: // We're making changes
292: changed = true;
293:
294: // Add a dup and store right after the instructions that
295: // pushes the receiver.
296: final LocalVariable var = method.newLocal(callee
297: .declaringClass());
298:
299: Specialize.db(" New local: " + var + " "
300: + var.type() + " (from method "
301: + method.name() + method.type() + ", max "
302: + method.maxLocals() + ")");
303:
304: final Iterator iter = pushes.iterator();
305: Assert.isTrue(iter.hasNext(),
306: "No instruction pushes receiver for "
307: + inst);
308: Instruction newInst = null;
309:
310: boolean mono = (set.size() == 1);
311:
312: while (!mono && iter.hasNext()) {
313: // Since we've already examined the code that pushes the
314: // receiver, we don't need to worry about keeping track
315: // of
316: // the stack height. Besides, this code doesn't effect
317: // the stack. I hope.
318:
319: // There is no need to dup the receiver object if the
320: // call
321: // is monomorphic. This avoids extra dups being
322: // executed.
323:
324: final Instruction push = (Instruction) iter
325: .next();
326: final int index = code.indexOf(push);
327: Assert.isTrue(index != -1, push
328: + " not found in code");
329: newInst = new Instruction(Opcode.opcx_dup);
330: code.add(index + 1, newInst);
331:
332: final Instruction store = new Instruction(
333: Opcode.opcx_astore, var);
334: code.add(index + 2, store);
335: }
336:
337: // We've added instructions before the call. This will
338: // mess up our code index, i. Update accordingly.
339: i = code.indexOf(inst) - 1;
340:
341: // Now specialize the call site. Examine each method the
342: // call could resolve to in an order such that overriding
343: // methods come before overriden methods. We don't need to
344: // keep track of the stack because these instructions will
345: // be iterated over in a minute. I hope.
346:
347: Specialize.db(" Specializing call site...");
348:
349: Label nextLabel = null;
350: final Label endLabel = method.newLabel();
351: endLabel.setStartsBlock(true);
352: endLabel.setComment("End Specialization");
353:
354: int index = code.indexOf(inst);
355: Assert.isTrue(index != -1, "Call " + inst
356: + " not found in code");
357:
358: index--; // Trust me
359:
360: Assert.isTrue(set != null, "Call to " + callee
361: + " should resolve to something");
362: final Object[] sortedSites = set.toArray();
363:
364: if (sortedSites.length == 1) {
365: // If the call site only resolve to one method, then we
366: // don't need to do all of the specialization stuff.
367: // Just
368: // call the static-ized method.
369: Specialize.db(" Monomorphic call site");
370: final MemberRef resolvesTo = (MemberRef) sortedSites[0];
371: MethodEditor resolvesToMethod = null;
372: try {
373: resolvesToMethod = this .context
374: .editMethod(resolvesTo);
375:
376: } catch (final NoSuchMethodException ex) {
377: System.err.println("** No such method "
378: + resolvesTo);
379: System.exit(1);
380: }
381:
382: if (resolvesToMethod.isNative()) {
383: // Can't specialize native methods. Oh well.
384: // Remember
385: // that it is possible for an overriding method to
386: // be
387: // native.
388: newInst = new Instruction(
389: Opcode.opcx_invokespecial,
390: resolvesTo);
391: code.add(++index, newInst);
392:
393: } else {
394: // Make a static version of the virtual method being
395: // invoked. Call it.
396: if (Specialize.NOSTATIC) {
397: // For testing the specialization stuff, call
398: // the
399: // virtual method instead of the static method.
400: newInst = new Instruction(inst
401: .opcodeClass(), inst.operand());
402: specialized.add(newInst);
403:
404: } else {
405: newInst = new Instruction(
406: Opcode.opcx_invokespecial,
407: resolvesToMethod.memberRef());
408: }
409:
410: code.add(++index, newInst);
411: }
412:
413: // Remove the call to the virtual method
414: code.remove(inst);
415: continue;
416: }
417:
418: // If we get to here we have a polymorphic call site
419:
420: for (int s = 0; (s < sortedSites.length)
421: && (s <= Specialize.MAX_MORPH); s++) {
422: final MemberRef resolvesTo = (MemberRef) sortedSites[s];
423:
424: // Do we ignore this method?
425: if (context.ignoreMethod(resolvesTo)) {
426: continue;
427: }
428:
429: Specialize.db(" Resolves to " + resolvesTo
430: + ")");
431:
432: final Type rType = resolvesTo.declaringClass();
433:
434: // This may be the target of a branch
435: if (nextLabel != null) {
436: nextLabel.setComment("Type " + rType);
437: code.add(++index, nextLabel);
438: }
439:
440: // Push the receiver object
441: newInst = new Instruction(Opcode.opcx_aload,
442: var);
443: code.add(++index, newInst);
444:
445: // Check to see if it is this type
446: newInst = new Instruction(
447: Opcode.opcx_instanceof , rType);
448: code.add(++index, newInst);
449:
450: // If its not, try something else
451: nextLabel = method.newLabel();
452: nextLabel.setStartsBlock(true);
453: newInst = new Instruction(Opcode.opcx_ifeq,
454: nextLabel);
455: code.add(++index, newInst);
456:
457: // We have to add a label here because all branches must
458: // be followed by a label. If we don't BLOAT will barf
459: // during CFG construction. And that's messy.
460: final Label grumble = method.newLabel();
461: grumble.setStartsBlock(true);
462: code.add(++index, grumble);
463:
464: // Otherwise, call the static-ified method. We can't
465: // cast
466: // the receiver to the expected type. Oh well, we
467: // weren't
468: // planning on verifying anyway.
469: MethodEditor resolvesToMethod = null;
470: try {
471: resolvesToMethod = this .context
472: .editMethod(resolvesTo);
473:
474: } catch (final NoSuchMethodException ex) {
475: System.err.println("** No such method "
476: + resolvesTo);
477: System.exit(1);
478: }
479:
480: if (resolvesToMethod.isNative()) {
481: // Can't specialize native methods. Oh well.
482: // Remember
483: // that it is possible for an overriding method to
484: // be
485: // native.
486: newInst = new Instruction(
487: Opcode.opcx_invokespecial,
488: resolvesTo);
489: code.add(++index, newInst);
490:
491: } else {
492: // Make a static version of the virtual method being
493: // invoked. Call it.
494: if (Specialize.NOSTATIC) {
495: // For testing the specialization stuff, call
496: // the
497: // virtual method instead of the static method.
498: newInst = new Instruction(inst
499: .opcodeClass(), inst.operand());
500: specialized.add(newInst);
501:
502: } else {
503: newInst = new Instruction(
504: Opcode.opcx_invokespecial,
505: resolvesToMethod.memberRef());
506: }
507:
508: code.add(++index, newInst);
509: }
510:
511: // Jump to the end
512: newInst = new Instruction(Opcode.opcx_goto,
513: endLabel);
514: code.add(++index, newInst);
515: }
516:
517: // Default code still invokes virtual method
518: if (nextLabel != null) {
519: nextLabel.setComment("Default invocation");
520: code.add(++index, nextLabel);
521: }
522:
523: // Call virtual method. Should be next in line.
524: index++;
525:
526: // Jump to end.
527: newInst = new Instruction(Opcode.opcx_goto,
528: endLabel);
529: code.add(++index, newInst);
530:
531: // We're all done
532: code.add(++index, endLabel);
533:
534: if (Specialize.DEBUG) {
535: // Print code up to and including end label
536: System.out.println(" Code after specializing "
537: + callee.name() + callee.type());
538: for (int j = 0; (j <= (index + 2))
539: && (j < code.size()); j++) {
540: final Object q = code.get(j);
541: if (q instanceof Label) {
542: final Label label = (Label) q;
543: System.out
544: .println(" "
545: + j
546: + ") "
547: + label
548: + (label.startsBlock() ? " (starts block)"
549: : ""));
550:
551: } else {
552: System.out.println(" " + j + ") "
553: + q);
554: }
555: }
556: }
557:
558: // Don't print the stack at the call instruction
559: continue;
560:
561: } else if (inst.opcodeClass() == Opcode.opcx_invokespecial) {
562: // To make our lives easier, convert some invokespecial to
563: // invoke static. Basically, if the callee is non-native
564: // and is a method of the caller's class or one of its
565: // superclasses, we can convert it.
566: final MemberRef callee = (MemberRef) inst.operand();
567:
568: MethodEditor me = null;
569: try {
570: me = context.editMethod(callee);
571: if (me.isNative() || me.isSynchronized()
572: || me.isConstructor()) {
573: // Forget about these guys
574: stack.handle(inst);
575:
576: } else {
577: final Type calleeType = callee
578: .declaringClass();
579: final Type callerType = method
580: .declaringClass().type();
581: final ClassHierarchy hier = context
582: .getHierarchy();
583:
584: if (calleeType.equals(callerType)
585: || hier.subclassOf(callerType,
586: calleeType)) {
587: Specialize.db(" Making special "
588: + inst + " static");
589:
590: final int index = code.indexOf(inst);
591: final Instruction newInst = new Instruction(
592: Opcode.opcx_invokespecial, me
593: .memberRef());
594: code.add(index, newInst);
595: code.remove(inst);
596: stack.handle(newInst);
597:
598: } else {
599: // Don't forget about the stack
600: stack.handle(inst);
601: }
602: }
603:
604: } catch (final NoSuchMethodException ex2) {
605: System.err.println("** Couldn't find method "
606: + callee);
607: ex2.printStackTrace(System.err);
608: System.exit(1);
609: }
610:
611: } else {
612: // Just update stack
613: stack.handle(inst);
614: }
615:
616: if (Specialize.DEBUG) {
617: Specialize.db(" " + code.indexOf(inst) + ") "
618: + inst);
619: for (int q = 0; q < stack.height(); q++) {
620: final Iterator iter = stack.atDepth(q)
621: .iterator();
622: if (iter.hasNext()) {
623: System.out.print(" ");
624: }
625: while (iter.hasNext()) {
626: System.out.print(code.indexOf(iter.next()));
627: if (iter.hasNext()) {
628: System.out.print(", ");
629: }
630: }
631:
632: if (stack.preexistsAtDepth(q) != null) {
633: System.out.print(" (preexists)");
634:
635: } else {
636: System.out.print(" (does not preexist)");
637: }
638: System.out.println("");
639: }
640: }
641:
642: } else if (o instanceof Label) {
643: // We've reached a label.
644: final Label label = (Label) o;
645: stack.handle(label);
646:
647: Specialize.db(" " + o);
648:
649: if (Specialize.DEBUG) {
650: for (int q = 0; q < stack.height(); q++) {
651: final Iterator iter = stack.atDepth(q)
652: .iterator();
653: if (iter.hasNext()) {
654: System.out.print(" ");
655: }
656: while (iter.hasNext()) {
657: System.out.print(code.indexOf(iter.next()));
658: if (iter.hasNext()) {
659: System.out.print(", ");
660: }
661: }
662: System.out.println("");
663: }
664: }
665:
666: } else {
667: Assert.isTrue(false, "What is " + o
668: + " doing in the instruction stream?");
669: }
670: }
671:
672: if (Specialize.DEBUG || Specialize.PRINTCODE) {
673: // Print out the code
674: System.out.println("Specialized code for "
675: + method.declaringClass().name() + "."
676: + method.name() + method.type());
677:
678: final Iterator iter2 = code.iterator();
679: while (iter2.hasNext()) {
680: final Object o = iter2.next();
681:
682: if (o instanceof Label) {
683: System.out.println("");
684: }
685:
686: System.out.println(" " + o);
687: }
688: }
689:
690: if (changed) {
691: method.setDirty(true);
692: }
693:
694: return (changed);
695: }
696:
697: }
|