1
2
3
4 package joeq.Compiler.Analysis.IPA;
5
6 import java.io.IOException;
7 import java.util.Iterator;
8 import java.util.Map;
9 import java.util.StringTokenizer;
10 import joeq.Class.jq_Class;
11 import joeq.Class.jq_ClassFileConstants;
12 import joeq.Class.jq_FakeInstanceMethod;
13 import joeq.Class.jq_InstanceMethod;
14 import joeq.Class.jq_LineNumberBC;
15 import joeq.Class.jq_Method;
16 import joeq.Class.jq_Type;
17 import joeq.Compiler.BytecodeAnalysis.BytecodeVisitor;
18 import joeq.Compiler.BytecodeAnalysis.Bytecodes;
19 import joeq.Compiler.Quad.CodeCache;
20 import joeq.Compiler.Quad.ControlFlowGraph;
21 import joeq.Compiler.Quad.Operator;
22 import joeq.Compiler.Quad.Quad;
23 import joeq.Compiler.Quad.QuadIterator;
24 import joeq.Compiler.Quad.Operator.Invoke;
25 import joeq.UTF.Utf8;
26 import jwutil.io.ByteSequence;
27 import jwutil.io.Textualizable;
28 import jwutil.io.Textualizer;
29 import jwutil.util.Assert;
30 import jwutil.util.Convert;
31
32 /***
33 * This class provides a general mechanism to describe a location in the code,
34 * independent of IR type. It combines a method and a location within that
35 * method. This is useful for interprocedural analysis, among other things.
36 *
37 * @author John Whaley <jwhaley@alum.mit.edu>
38 * @version $Id: ProgramLocation.java 2458 2006-05-02 22:01:25Z mcmartin $
39 */
40 public abstract class ProgramLocation implements Textualizable {
41 public static final boolean GIVE_SIGNATURES = !System.getProperty("pa.signaturesinlocs", "no").equals("no");
42 /*** The method of this location. **/
43 protected final jq_Method m;
44
45 protected ProgramLocation(jq_Method m) {
46 this.m = m;
47 }
48
49 public jq_Class getContainingClass() {
50 return m.getDeclaringClass();
51 }
52
53 public jq_Method getMethod() {
54 return m;
55 }
56
57 public Utf8 getSourceFile() {
58 return getContainingClass().getSourceFile();
59 }
60
61 public int getLineNumber() {
62 return m.getLineNumber(getBytecodeIndex());
63 }
64
65 /*** Print a location as it would appear in an exception stacktrace. */
66 public String toStringLong() {
67 return getContainingClass()+"."+getMethod().getName()+'('+getSourceFile()+':'+getLineNumber()+')';
68 }
69
70 public abstract int getID();
71 public abstract int getBytecodeIndex();
72 public abstract jq_Type getResultType();
73
74 public abstract void write(Textualizer t) throws IOException;
75 public void writeEdges(Textualizer t) throws IOException {}
76 public void addEdge(String edgeName, Textualizable t) {}
77
78 public abstract boolean isCall();
79 public abstract jq_Method getTargetMethod();
80 public abstract jq_Method resolveTargetMethod();
81 public abstract jq_Type[] getParamTypes();
82 public abstract jq_Type getReturnType();
83 public abstract boolean isSingleTarget();
84 public abstract boolean isInterfaceCall();
85 public abstract byte getInvocationType();
86
87 public String getEmacsName() {
88 Utf8 source = getSourceFile();
89 if (source != null) {
90 int lineno = getLineNumber();
91 return source+":"+lineno;
92 } else {
93 String className = getContainingClass().getJDKName();
94 String method = m.getNameAndDesc().toString();
95 int id = getID();
96 return className+":"+method+":"+id;
97 }
98 }
99
100 public static class QuadProgramLocation extends ProgramLocation {
101 private final Quad q;
102 public QuadProgramLocation(jq_Method m, Quad q) {
103 super(m);
104 this.q = q;
105 }
106
107 public Quad getQuad() {
108 return q;
109 }
110
111 public int getID() {
112 return q.getID();
113 }
114
115 public int getBytecodeIndex() {
116 Map map = CodeCache.getBCMap((jq_Method) super.m);
117 if (map == null) return -1;
118 Integer i = (Integer) map.get(q);
119 if (i == null) return -1;
120 return i.intValue();
121 }
122
123 public jq_Type getResultType() {
124 return q.getDefinedRegisters().getRegisterOperand(0).getType();
125 }
126
127 public boolean isCall() {
128 return q.getOperator() instanceof Invoke;
129 }
130
131 public jq_Method getTargetMethod() {
132 Assert._assert(isCall());
133 return Invoke.getMethod(q).getMethod();
134 }
135
136 public jq_Method resolveTargetMethod() {
137 Assert._assert(isCall());
138 Invoke.getMethod(q).resolve();
139 return Invoke.getMethod(q).getMethod();
140 }
141
142 public jq_Type[] getParamTypes() {
143 Assert._assert(isCall());
144 jq_Type[] t = Invoke.getMethod(q).getMethod().getParamTypes();
145 if (t.length != Invoke.getParamList(q).length()) {
146 t = new jq_Type[Invoke.getParamList(q).length()];
147 for (int i=0; i<t.length; ++i) {
148 t[i] = Invoke.getParamList(q).get(i).getType();
149 }
150 }
151 return t;
152 }
153
154 public jq_Type getReturnType() {
155 Assert._assert(isCall());
156 return Invoke.getMethod(q).getMethod().getReturnType();
157 }
158
159 public boolean isSingleTarget() {
160 if (isInterfaceCall()) return false;
161 if (!((Invoke) q.getOperator()).isVirtual()) return true;
162 Object trg = Invoke.getMethod(q).getMethod();
163 Assert._assert(trg instanceof jq_InstanceMethod, "Unexpected " + trg + " of type " + trg.getClass());
164 jq_InstanceMethod target = (jq_InstanceMethod) trg;
165 target.getDeclaringClass().load();
166 if (target.getDeclaringClass().isFinal()) return true;
167 target.getDeclaringClass().prepare();
168 if (!target.isLoaded()) {
169 target = target.resolve1();
170 if (!target.isLoaded()) {
171
172 return false;
173 }
174 Invoke.getMethod(q).setMethod(target);
175 }
176 if (target.isFinal()) return true;
177 if (!target.isVirtual()) return true;
178 return false;
179 }
180
181 public boolean isInterfaceCall() {
182 return q.getOperator() instanceof Invoke.InvokeInterface;
183 }
184
185 public int hashCode() {
186 return (q==null)?-1:q.hashCode();
187 }
188 public boolean equals(QuadProgramLocation that) {
189 return this.q == that.q;
190 }
191 public boolean equals(Object o) {
192 if (o instanceof QuadProgramLocation)
193 return equals((QuadProgramLocation)o);
194 return false;
195 }
196
197 public String toString() {
198 StringBuffer sb = new StringBuffer();
199 sb.append(super.m.getDeclaringClass().getName());
200 sb.append('.');
201 sb.append(super.m.getName());
202 sb.append("() quad ");
203 sb.append((q==null)?-1:q.getID());
204 if (q.getOperator() instanceof Invoke) {
205 sb.append(" => ");
206 if (GIVE_SIGNATURES) {
207 sb.append(Invoke.getMethod(q).getMethod().getNameAndDesc());
208 } else {
209 sb.append(Invoke.getMethod(q).getMethod().getName());
210 sb.append("()");
211 }
212 if (isSingleTarget())
213 sb.append("*");
214 }
215
216
217
218
219 return sb.toString();
220 }
221
222 public byte getInvocationType() {
223 if (q.getOperator() instanceof Invoke.InvokeVirtual) {
224 return BytecodeVisitor.INVOKE_VIRTUAL;
225 } else if (q.getOperator() instanceof Invoke.InvokeStatic) {
226 jq_Method target = Invoke.getMethod(q).getMethod();
227 if (target instanceof jq_InstanceMethod)
228 return BytecodeVisitor.INVOKE_SPECIAL;
229 else
230 return BytecodeVisitor.INVOKE_STATIC;
231 } else {
232 Assert._assert(q.getOperator() instanceof Invoke.InvokeInterface);
233 return BytecodeVisitor.INVOKE_INTERFACE;
234 }
235 }
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260 public void write(Textualizer t) throws IOException {
261 t.writeString("quad "+q.getID()+" ");
262 t.writeObject(m);
263 }
264 }
265
266 public static class BCProgramLocation extends ProgramLocation {
267 final int bcIndex;
268
269 public BCProgramLocation(jq_Method m, int bcIndex) {
270 super(m);
271 this.bcIndex = bcIndex;
272 }
273
274 public int getID() {
275 return bcIndex;
276 }
277
278 public int getBytecodeIndex() {
279 return bcIndex;
280 }
281
282 public byte getBytecode() {
283 byte[] bc = ((jq_Method) super.m).getBytecode();
284 return bc[bcIndex];
285 }
286
287 public jq_Type getResultType() {
288 ByteSequence bs = new ByteSequence(m.getBytecode(), bcIndex, 8);
289 try {
290 Bytecodes.Instruction i = Bytecodes.Instruction.readInstruction(getContainingClass().getCP(), bs);
291 if (!(i instanceof Bytecodes.TypedInstruction)) return null;
292 return ((Bytecodes.TypedInstruction)i).getType();
293 } catch (IOException x) {
294 Assert.UNREACHABLE();
295 return null;
296 }
297 }
298
299 public boolean isCall() {
300 switch (getBytecode()) {
301 case (byte) jq_ClassFileConstants.jbc_INVOKEVIRTUAL:
302 case (byte) jq_ClassFileConstants.jbc_INVOKESPECIAL:
303 case (byte) jq_ClassFileConstants.jbc_INVOKEINTERFACE:
304 case (byte) jq_ClassFileConstants.jbc_INVOKESTATIC:
305 case (byte) jq_ClassFileConstants.jbc_MULTIANEWARRAY:
306 return true;
307 default:
308 return false;
309 }
310 }
311
312 public jq_Method getTargetMethod() {
313 jq_Class clazz = ((jq_Method) super.m).getDeclaringClass();
314 byte[] bc = ((jq_Method) super.m).getBytecode();
315 char cpi = Convert.twoBytesToChar(bc, bcIndex+1);
316 switch (bc[bcIndex]) {
317 case (byte) jq_ClassFileConstants.jbc_INVOKEVIRTUAL:
318 case (byte) jq_ClassFileConstants.jbc_INVOKESPECIAL:
319 case (byte) jq_ClassFileConstants.jbc_INVOKEINTERFACE:
320 return clazz.getCPasInstanceMethod(cpi);
321 case (byte) jq_ClassFileConstants.jbc_INVOKESTATIC:
322 return clazz.getCPasStaticMethod(cpi);
323 case (byte) jq_ClassFileConstants.jbc_MULTIANEWARRAY:
324 return joeq.Runtime.Arrays._multinewarray;
325 default:
326 return null;
327 }
328 }
329
330
331 public jq_Method resolveTargetMethod() {
332 jq_Method m = getTargetMethod();
333 m = (jq_Method) m.resolve();
334 return m;
335 }
336
337 public jq_Type[] getParamTypes() {
338 return getTargetMethod().getParamTypes();
339 }
340
341 public jq_Type getReturnType() {
342 return getTargetMethod().getReturnType();
343 }
344
345 public boolean isSingleTarget() {
346 switch (getBytecode()) {
347 case (byte) jq_ClassFileConstants.jbc_INVOKESPECIAL:
348 case (byte) jq_ClassFileConstants.jbc_INVOKESTATIC:
349 case (byte) jq_ClassFileConstants.jbc_MULTIANEWARRAY:
350 return true;
351 case (byte) jq_ClassFileConstants.jbc_INVOKEVIRTUAL:
352 case (byte) jq_ClassFileConstants.jbc_INVOKEINTERFACE:
353 default:
354 return false;
355 }
356 }
357
358 public boolean isInterfaceCall() {
359 return getBytecode() == jq_ClassFileConstants.jbc_INVOKEINTERFACE;
360 }
361
362 public int hashCode() {
363 return super.m.hashCode() ^ bcIndex;
364 }
365 public boolean equals(BCProgramLocation that) {
366 return this.bcIndex == that.bcIndex && super.m == that.m;
367 }
368 public boolean equals(Object o) {
369 if (o instanceof BCProgramLocation)
370 return equals((BCProgramLocation) o);
371 return false;
372 }
373 public String toString() {
374 StringBuffer sb = new StringBuffer(super.m.getDeclaringClass().getName());
375 sb.append('.');
376 if (GIVE_SIGNATURES) {
377 sb.append(super.m.getNameAndDesc());
378 } else {
379 sb.append(super.m.getName()).append("()");
380 }
381 sb.append(" @ ").append(bcIndex);
382 return sb.toString();
383 }
384
385 public byte getInvocationType() {
386 switch (getBytecode()) {
387 case (byte) jq_ClassFileConstants.jbc_INVOKEVIRTUAL:
388 return BytecodeVisitor.INVOKE_VIRTUAL;
389 case (byte) jq_ClassFileConstants.jbc_INVOKESPECIAL:
390 return BytecodeVisitor.INVOKE_SPECIAL;
391 case (byte) jq_ClassFileConstants.jbc_INVOKEINTERFACE:
392 return BytecodeVisitor.INVOKE_INTERFACE;
393 case (byte) jq_ClassFileConstants.jbc_INVOKESTATIC:
394 case (byte) jq_ClassFileConstants.jbc_MULTIANEWARRAY:
395 return BytecodeVisitor.INVOKE_STATIC;
396 default:
397 return -1;
398 }
399 }
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496 public void write(Textualizer t) throws IOException {
497 t.writeString("bc "+bcIndex+" ");
498 t.writeObject(m);
499 }
500
501 }
502
503 public static class FakeProgramLocation extends ProgramLocation {
504 String label;
505
506 public FakeProgramLocation(jq_Method m, String label) {
507 super(m);
508 this.label = label;
509 }
510
511 public void write(Textualizer t) throws IOException {
512 t.writeString("fake "+label.replace(' ', '_') + " ");
513 t.writeObject(m);
514 }
515
516 public String toString() {
517 String s = super.m.getDeclaringClass().getName()+"."+super.m.getName()+"() '"+label+"'";
518 return s;
519 }
520
521 public int getID() { return -1; }
522 public int getBytecodeIndex() { return -1; }
523 public jq_Type getResultType() { return null; }
524 public boolean isCall() { return false; }
525 public jq_Method getTargetMethod() { return null; }
526 public jq_Method resolveTargetMethod() { return null; }
527 public jq_Type[] getParamTypes() { return null; }
528 public jq_Type getReturnType() { return null; }
529 public boolean isSingleTarget() { return false; }
530 public boolean isInterfaceCall() { return false; }
531 public byte getInvocationType() { return -1; }
532 }
533
534 public static class PlaceholderParameterProgramLocation extends ProgramLocation {
535 String locationLabel;
536
537 public PlaceholderParameterProgramLocation(jq_Method m, String locationLabel) {
538 super(m);
539 this.locationLabel = locationLabel;
540 }
541
542 public PlaceholderParameterProgramLocation(PlaceholderParameterProgramLocation that, String postfix) {
543 this(that.getMethod(), that.getLocationLabel() + postfix);
544 }
545
546 public String getLocationLabel() {
547 return locationLabel;
548 }
549
550 public void write(Textualizer t) throws IOException {
551 t.writeString("placeholder "+locationLabel.replace(' ', '_') + " ");
552 t.writeObject(m);
553 }
554
555 public String toString() {
556 String s = locationLabel + " of " + super.m.getDeclaringClass().getName()+"."+super.m.getName()+"()";
557 return s;
558 }
559
560 public int getID() { return -1; }
561 public int getBytecodeIndex() { return -1; }
562 public jq_Type getResultType() { return null; }
563 public boolean isCall() { return false; }
564 public jq_Method getTargetMethod() { return null; }
565 public jq_Method resolveTargetMethod() { return null; }
566 public jq_Type[] getParamTypes() { return null; }
567 public jq_Type getReturnType() { return null; }
568 public boolean isSingleTarget() { return false; }
569 public boolean isInterfaceCall() { return false; }
570 public byte getInvocationType() { return -1; }
571 public String getEmacsName() {
572 Utf8 source = getSourceFile();
573 if (source == null) {
574 return m + ":"+m.getLineNumber(0) + locationLabel;
575 }else{
576 return source+":"+m.getLineNumber(0) + locationLabel;
577 }
578 }
579 }
580
581 public static ProgramLocation read(StringTokenizer st) {
582 String s = st.nextToken();
583 if (s.equals("null"))
584 return null;
585 if (s.equals("fake")) {
586 String label = st.nextToken().replace('_', ' ');
587 jq_Method m = (jq_Method)jq_FakeInstanceMethod.read(st);
588 if (m == null) return null;
589 return new FakeProgramLocation(m, label);
590 }
591 int id = Integer.parseInt(st.nextToken());
592 jq_Method m = (jq_Method) jq_Method.read(st);
593 if (m == null) return null;
594 if (s.equals("bc")) {
595 return new BCProgramLocation(m, id);
596 }
597 if (s.equals("quad")) {
598 if (m.getBytecode() == null) return null;
599 ControlFlowGraph cfg = CodeCache.getCode(m);
600 for (QuadIterator i = new QuadIterator(cfg); i.hasNext(); ) {
601 Quad q = i.nextQuad();
602 if (q.getID() == id) return new QuadProgramLocation(m, q);
603 }
604 }
605 return null;
606 }
607
608 public static ProgramLocation getLoadLocation(jq_Class klass, int lineNum) {
609 if (true)
610 return getBCProgramLocation(klass, lineNum, Bytecodes.LoadInstruction.class, 0);
611 else {
612 ProgramLocation pl;
613 pl = getQuadProgramLocation(klass, lineNum, Operator.ALoad.ALOAD_A.class, 0);
614 if (pl != null) return pl;
615 pl = getQuadProgramLocation(klass, lineNum, Operator.ALoad.ALOAD_P.class, 0);
616 if (pl != null) return pl;
617 pl = getQuadProgramLocation(klass, lineNum, Operator.Getfield.GETFIELD_A.class, 0);
618 if (pl != null) return pl;
619 return getQuadProgramLocation(klass, lineNum, Operator.Getfield.GETFIELD_P.class, 0);
620 }
621 }
622
623 public static ProgramLocation getAllocLocation(jq_Class klass, int lineNum) {
624 if (true)
625 return getBCProgramLocation(klass, lineNum, Bytecodes.AllocationInstruction.class, 0);
626 else {
627 ProgramLocation pl;
628 pl = getQuadProgramLocation(klass, lineNum, Operator.New.class, 0);
629 if (pl != null) return pl;
630 return getQuadProgramLocation(klass, lineNum, Operator.NewArray.class, 0);
631 }
632 }
633
634 public static ProgramLocation getConstLocation(jq_Class klass, int lineNum) {
635 if (true) {
636 ProgramLocation pl = getBCProgramLocation(klass, lineNum, Bytecodes.LDC.class, 0);
637 if (pl != null) return pl;
638 return getBCProgramLocation(klass, lineNum, Bytecodes.LDC2_W.class, 0);
639 } else {
640 return getQuadProgramLocation(klass, lineNum, Operator.Move.class, 0);
641 }
642 }
643
644 public static ProgramLocation getInvokeLocation(jq_Class klass, int lineNum) {
645 if (true)
646 return getBCProgramLocation(klass, lineNum, Bytecodes.InvokeInstruction.class, 0);
647 else {
648 return getQuadProgramLocation(klass, lineNum, Operator.Invoke.class, 0);
649 }
650 }
651
652 public static ProgramLocation getBCProgramLocation(jq_Class klass, int lineNum, Class instructionType, int k) {
653 klass.load();
654 jq_Method m = klass.getMethodContainingLine((char) lineNum);
655 if (m == null) return null;
656 jq_LineNumberBC[] ln = m.getLineNumberTable();
657 if (ln == null) return null;
658 int i = 0;
659 for ( ; i<ln.length; ++i) {
660 if (ln[i].getLineNum() == lineNum) break;
661 }
662 if (i == ln.length) return null;
663 int loIndex = ln[i].getStartPC();
664 int hiIndex = m.getBytecode().length;
665 if (i < ln.length-1) hiIndex = ln[i+1].getStartPC();
666 ByteSequence bs = new ByteSequence(m.getBytecode(), loIndex, hiIndex-loIndex);
667 try {
668 while (bs.available() > 0) {
669 int off = bs.getIndex();
670 Bytecodes.Instruction in = Bytecodes.Instruction.readInstruction(klass.getCP(), bs);
671 if (instructionType.isInstance(in)) {
672 if (k == 0)
673 return new BCProgramLocation(m, off);
674 --k;
675 }
676 }
677 } catch (IOException x) {
678 Assert.UNREACHABLE();
679 }
680 return null;
681 }
682
683 public static ProgramLocation getQuadProgramLocation(jq_Class klass, int lineNum, Class instructionType, int k) {
684 klass.load();
685 jq_Method m = klass.getMethodContainingLine((char) lineNum);
686 if (m == null) return null;
687 jq_LineNumberBC[] ln = m.getLineNumberTable();
688 if (ln == null) return null;
689 int i = 0;
690 for ( ; i<ln.length; ++i) {
691 if (ln[i].getLineNum() == lineNum) break;
692 }
693 if (i == ln.length) return null;
694 int loIndex = ln[i].getStartPC();
695 int hiIndex = m.getBytecode().length;
696 if (i < ln.length-1) hiIndex = ln[i+1].getStartPC();
697 Map bc_map = CodeCache.getBCMap(m);
698 for (Iterator j = bc_map.entrySet().iterator(); j.hasNext(); ) {
699 Map.Entry e = (Map.Entry) j.next();
700 Quad q = (Quad) e.getKey();
701 if (!instructionType.isInstance(q.getOperator()))
702 continue;
703 int index = ((Integer) e.getValue()).intValue();
704 if (index >= loIndex && index < hiIndex)
705 return new QuadProgramLocation(m, q);
706 }
707 return null;
708 }
709 }