IKVM11  11
Java SE 11 Virtual Machine for .NET
Loading...
Searching...
No Matches
JsrInliner.cs
Go to the documentation of this file.
1/*
2 Copyright (C) 2002-2010 Jeroen Frijters
3
4 This software is provided 'as-is', without any express or implied
5 warranty. In no event will the authors be held liable for any damages
6 arising from the use of this software.
7
8 Permission is granted to anyone to use this software for any purpose,
9 including commercial applications, and to alter it and redistribute it
10 freely, subject to the following restrictions:
11
12 1. The origin of this software must not be misrepresented; you must not
13 claim that you wrote the original software. If you use this software
14 in a product, an acknowledgment in the product documentation would be
15 appreciated but is not required.
16 2. Altered source versions must be plainly marked as such, and must not be
17 misrepresented as being the original software.
18 3. This notice may not be removed or altered from any source distribution.
19
20 Jeroen Frijters
21 jeroen@frijters.net
22
23*/
24using System;
25using System.Collections.Generic;
26
27using IKVM.ByteCode;
28
29using InstructionFlags = IKVM.Runtime.ClassFile.Method.InstructionFlags;
30
31namespace IKVM.Runtime
32{
33
37 sealed class JsrInliner
38 {
39
40 internal static void InlineJsrs(RuntimeClassLoader classLoader, RuntimeJavaMethod mw, ClassFile classFile, ClassFile.Method m)
41 {
42 JsrInliner inliner;
43
44 do
45 {
46 var codeCopy = (ClassFile.Method.Instruction[])m.Instructions.Clone();
47 var flags = new InstructionFlags[codeCopy.Length];
48 var ma = new JsrMethodAnalyzer(mw, classFile, m, classLoader, flags);
49 inliner = new JsrInliner(codeCopy, flags, m, ma);
50 } while (inliner.InlineJsrs());
51 }
52
53 ClassFile.Method.Instruction[] codeCopy;
54 int codeLength;
55 InstructionFlags[] flags;
56 readonly ClassFile.Method m;
57 readonly JsrMethodAnalyzer ma;
58
66 JsrInliner(ClassFile.Method.Instruction[] codeCopy, InstructionFlags[] flags, ClassFile.Method m, JsrMethodAnalyzer ma)
67 {
68 this.codeCopy = codeCopy;
69 codeLength = codeCopy.Length;
70 this.flags = flags;
71 this.m = m;
72 this.ma = ma;
73 }
74
75 void Add(ClassFile.Method.Instruction instr)
76 {
77 if (codeLength == codeCopy.Length)
78 {
79 Array.Resize(ref codeCopy, codeLength * 2);
80 Array.Resize(ref flags, codeLength * 2);
81 }
82
83 codeCopy[codeLength++] = instr;
84 }
85
90 bool InlineJsrs()
91 {
92 var hasJsrs = false;
93 var subs = new List<SubroutineCall>();
94 int len = codeLength;
95
96 for (int i = 0; i < len; i++)
97 {
98 // note that we're also (needlessly) processing the subroutines here, but that shouldn't be a problem (just a minor waste of cpu)
99 // because the code is unreachable anyway
100 if ((flags[i] & InstructionFlags.Reachable) != 0 && m.Instructions[i].NormalizedOpCode == NormalizedByteCode.__jsr)
101 {
102 int subroutineId = m.Instructions[i].TargetIndex;
103 codeCopy[i].PatchOpCode(NormalizedByteCode.__goto, codeLength);
104 var sub = new SubroutineCall(this, subroutineId, i + 1);
105 hasJsrs |= sub.InlineSubroutine();
106 subs.Add(sub);
107 }
108 }
109
110 var exceptions = new List<ClassFile.Method.ExceptionTableEntry>(m.ExceptionTable);
111 foreach (var sub in subs)
112 sub.DoExceptions(m.ExceptionTable, exceptions);
113
114 m.ExceptionTable = exceptions.ToArray();
115 var instr = new ClassFile.Method.Instruction();
116 instr.SetTermNop(0xFFFF);
117 Add(instr);
118 Array.Resize(ref codeCopy, codeLength);
119
120 m.Instructions = codeCopy;
121 return hasJsrs;
122 }
123
124 sealed class SubroutineCall
125 {
126
127 readonly JsrInliner inliner;
128 readonly int subroutineIndex;
129 readonly int returnIndex;
130 readonly int[] branchMap;
131 readonly int baseIndex;
132 int endIndex;
133
140 internal SubroutineCall(JsrInliner inliner, int subroutineIndex, int returnIndex)
141 {
142 this.inliner = inliner;
143 this.subroutineIndex = subroutineIndex;
144 this.returnIndex = returnIndex;
145 baseIndex = inliner.codeLength;
146 branchMap = new int[inliner.m.Instructions.Length];
147 for (int i = 0; i < branchMap.Length; i++)
148 branchMap[i] = i;
149 }
150
151 void Emit(ClassFile.Method.Instruction instr)
152 {
153 inliner.Add(instr);
154 }
155
156 void EmitGoto(int targetIndex)
157 {
158 var instr = new ClassFile.Method.Instruction();
159 instr.PatchOpCode(NormalizedByteCode.__goto, targetIndex);
160 instr.SetPC(-1);
161 Emit(instr);
162 }
163
164 internal bool InlineSubroutine()
165 {
166 var hasJsrs = false;
167
168 // start with a pre-amble to load a dummy return address on the stack and to branch to the subroutine
169 {
170 // TODO consider exception handling around these instructions
171 var instr = new ClassFile.Method.Instruction();
172 instr.PatchOpCode(NormalizedByteCode.__aconst_null);
173 instr.SetPC(inliner.m.Instructions[subroutineIndex].PC);
174 Emit(instr);
175 EmitGoto(subroutineIndex);
176 }
177
178 var fallThru = false;
179 for (int instructionIndex = 0; instructionIndex < inliner.m.Instructions.Length; instructionIndex++)
180 {
181 if ((inliner.flags[instructionIndex] & InstructionFlags.Reachable) != 0 && inliner.ma.IsSubroutineActive(instructionIndex, subroutineIndex))
182 {
183 fallThru = false;
184 branchMap[instructionIndex] = inliner.codeLength;
185
186 switch (inliner.m.Instructions[instructionIndex].NormalizedOpCode)
187 {
188 case NormalizedByteCode.__tableswitch:
189 case NormalizedByteCode.__lookupswitch:
190 case NormalizedByteCode.__ireturn:
191 case NormalizedByteCode.__lreturn:
192 case NormalizedByteCode.__freturn:
193 case NormalizedByteCode.__dreturn:
194 case NormalizedByteCode.__areturn:
195 case NormalizedByteCode.__return:
196 case NormalizedByteCode.__athrow:
197 case NormalizedByteCode.__goto:
198 Emit(inliner.m.Instructions[instructionIndex]);
199 break;
200 case NormalizedByteCode.__jsr:
201 hasJsrs = true;
202 goto default;
203 case NormalizedByteCode.__ret:
204 {
205 int subid = inliner.ma.GetLocalTypeWrapper(instructionIndex, inliner.m.Instructions[instructionIndex].TargetIndex).SubroutineIndex;
206 if (subid == subroutineIndex)
207 EmitGoto(returnIndex);
208 else
209 Emit(inliner.m.Instructions[instructionIndex]);
210 break;
211 }
212 default:
213 fallThru = true;
214 Emit(inliner.m.Instructions[instructionIndex]);
215 break;
216 }
217 }
218 else if (fallThru)
219 {
220 EmitGoto(instructionIndex);
221 }
222 }
223
224 endIndex = inliner.codeLength;
225 DoFixups();
226 return hasJsrs;
227 }
228
229 void DoFixups()
230 {
231 for (int instructionIndex = baseIndex; instructionIndex < endIndex; instructionIndex++)
232 {
233 switch (inliner.codeCopy[instructionIndex].NormalizedOpCode)
234 {
235 case NormalizedByteCode.__lookupswitch:
236 case NormalizedByteCode.__tableswitch:
237 {
238 var targets = new int[inliner.codeCopy[instructionIndex].SwitchEntryCount];
239 for (int i = 0; i < targets.Length; i++)
240 targets[i] = branchMap[inliner.codeCopy[instructionIndex].GetSwitchTargetIndex(i)];
241
242 inliner.codeCopy[instructionIndex].SetSwitchTargets(targets);
243 inliner.codeCopy[instructionIndex].DefaultTarget = branchMap[inliner.codeCopy[instructionIndex].DefaultTarget];
244 }
245 break;
246 case NormalizedByteCode.__ifeq:
247 case NormalizedByteCode.__ifne:
248 case NormalizedByteCode.__iflt:
249 case NormalizedByteCode.__ifge:
250 case NormalizedByteCode.__ifgt:
251 case NormalizedByteCode.__ifle:
252 case NormalizedByteCode.__if_icmpeq:
253 case NormalizedByteCode.__if_icmpne:
254 case NormalizedByteCode.__if_icmplt:
255 case NormalizedByteCode.__if_icmpge:
256 case NormalizedByteCode.__if_icmpgt:
257 case NormalizedByteCode.__if_icmple:
258 case NormalizedByteCode.__if_acmpeq:
259 case NormalizedByteCode.__if_acmpne:
260 case NormalizedByteCode.__ifnull:
261 case NormalizedByteCode.__ifnonnull:
262 case NormalizedByteCode.__goto:
263 case NormalizedByteCode.__jsr:
264 inliner.codeCopy[instructionIndex].TargetIndex = branchMap[inliner.codeCopy[instructionIndex].TargetIndex];
265 break;
266 }
267 }
268 }
269
270 int MapExceptionStartEnd(int index)
271 {
272 while (branchMap[index] < baseIndex)
273 {
274 index++;
275 if (index == branchMap.Length)
276 return endIndex;
277 }
278
279 return branchMap[index];
280 }
281
282 internal void DoExceptions(ClassFile.Method.ExceptionTableEntry[] table, List<ClassFile.Method.ExceptionTableEntry> newExceptions)
283 {
284 foreach (var entry in table)
285 {
286 int start = MapExceptionStartEnd(entry.startIndex);
287 int end = MapExceptionStartEnd(entry.endIndex);
288 if (start != end)
289 {
290 var newEntry = new ClassFile.Method.ExceptionTableEntry(start, end, branchMap[entry.handlerIndex], entry.catchType, entry.ordinal);
291 newExceptions.Add(newEntry);
292 }
293 }
294 }
295
296 }
297
301 class SimpleType
302 {
303
304 sealed class ReturnAddressType : SimpleType
305 {
306
307 internal readonly int subroutineIndex;
308
309 internal ReturnAddressType(int subroutineIndex)
310 {
311 this.subroutineIndex = subroutineIndex;
312 }
313
314 }
315
316 internal static readonly SimpleType Invalid = null;
317 internal static readonly SimpleType Primitive = new SimpleType();
318 internal static readonly SimpleType WidePrimitive = new SimpleType();
319 internal static readonly SimpleType Object = new SimpleType();
320 internal static readonly SimpleType[] EmptyArray = [];
321
325 SimpleType()
326 {
327
328 }
329
330 internal bool IsPrimitive => this == SimpleType.Primitive || this == SimpleType.WidePrimitive;
331
332 internal bool IsWidePrimitive => this == SimpleType.WidePrimitive;
333
334 internal static SimpleType MakeRet(int subroutineIndex)
335 {
336 return new ReturnAddressType(subroutineIndex);
337 }
338
339 internal static bool IsRet(SimpleType w)
340 {
341 return w is ReturnAddressType;
342 }
343
344 internal int SubroutineIndex => ((ReturnAddressType)this).subroutineIndex;
345
346 }
347
348 sealed class JsrMethodAnalyzer
349 {
350
351 readonly ClassFile _classFile;
352 readonly InstructionState[] _state;
353 readonly List<int>[] _callsites;
354 readonly List<int>[] _returnsites;
355
368 internal JsrMethodAnalyzer(RuntimeJavaMethod mw, ClassFile classFile, ClassFile.Method method, RuntimeClassLoader classLoader, InstructionFlags[] flags)
369 {
370 if (method.VerifyError != null)
371 throw new VerifyError(method.VerifyError);
372
373 _classFile = classFile;
374 _state = new InstructionState[method.Instructions.Length];
375 _callsites = new List<int>[method.Instructions.Length];
376 _returnsites = new List<int>[method.Instructions.Length];
377
378 // because types have to have identity, the subroutine return address types are cached here
379 var returnAddressTypes = new Dictionary<int, SimpleType>();
380
381 try
382 {
383 // ensure that exception blocks and handlers start and end at instruction boundaries
384 for (int i = 0; i < method.ExceptionTable.Length; i++)
385 {
386 int start = method.ExceptionTable[i].startIndex;
387 int end = method.ExceptionTable[i].endIndex;
388 int handler = method.ExceptionTable[i].handlerIndex;
389 if (start >= end || start == -1 || end == -1 || handler <= 0)
390 throw new IndexOutOfRangeException();
391 }
392 }
393 catch (IndexOutOfRangeException)
394 {
395 throw new ClassFormatError(string.Format("Illegal exception table (class: {0}, method: {1}, signature: {2}", classFile.Name, method.Name, method.Signature));
396 }
397
398 // start by computing the initial state, the stack is empty and the locals contain the arguments
399 _state[0] = new InstructionState(method.MaxLocals, method.MaxStack);
400 SimpleType thisType;
401 int firstNonArgLocalIndex = 0;
402 if (method.IsStatic == false)
403 {
404 thisType = SimpleType.Object;
405 _state[0].SetLocalType(firstNonArgLocalIndex++, thisType, -1);
406 }
407 else
408 {
409 thisType = null;
410 }
411
412 var argTypeWrappers = mw.GetParameters();
413 for (int i = 0; i < argTypeWrappers.Length; i++)
414 {
415 var tw = argTypeWrappers[i];
416
417 SimpleType type;
418 if (tw.IsWidePrimitive)
419 {
420 type = SimpleType.WidePrimitive;
421 }
422 else if (tw.IsPrimitive)
423 {
424 type = SimpleType.Primitive;
425 }
426 else
427 {
428 type = SimpleType.Object;
429 }
430
431 _state[0].SetLocalType(firstNonArgLocalIndex++, type, -1);
432 if (type.IsWidePrimitive)
433 firstNonArgLocalIndex++;
434 }
435
436 var argumentsByLocalIndex = new SimpleType[firstNonArgLocalIndex];
437 for (int i = 0; i < argumentsByLocalIndex.Length; i++)
438 argumentsByLocalIndex[i] = _state[0].GetLocalTypeEx(i);
439
440 var s = _state[0].Copy();
441 var done = false;
442 var instructions = method.Instructions;
443
444 while (!done)
445 {
446 done = true;
447
448 for (int i = 0; i < instructions.Length; i++)
449 {
450 if (_state[i] != null && _state[i].changed)
451 {
452 try
453 {
454 done = false;
455 _state[i].changed = false;
456
457 // mark the exception handlers reachable from this instruction
458 for (int j = 0; j < method.ExceptionTable.Length; j++)
459 if (method.ExceptionTable[j].startIndex <= i && i < method.ExceptionTable[j].endIndex)
460 MergeExceptionHandler(method.ExceptionTable[j].handlerIndex, _state[i]);
461
462 _state[i].CopyTo(s);
463 var instr = instructions[i];
464
465 switch (instr.NormalizedOpCode)
466 {
467 case NormalizedByteCode.__aload:
468 {
469 var type = s.GetLocalType(instr.NormalizedArg1);
470 if (type == SimpleType.Invalid || type.IsPrimitive)
471 throw new VerifyError("Object reference expected");
472
473 s.PushType(type);
474 break;
475 }
476 case NormalizedByteCode.__astore:
477 s.SetLocalType(instr.NormalizedArg1, s.PopObjectType(), i);
478 break;
479 case NormalizedByteCode.__aconst_null:
480 s.PushObject();
481 break;
482 case NormalizedByteCode.__aaload:
483 s.PopPrimitive();
484 s.PopObjectType();
485 s.PushObject();
486 break;
487 case NormalizedByteCode.__aastore:
488 s.PopObjectType();
489 s.PopPrimitive();
490 s.PopObjectType();
491 break;
492 case NormalizedByteCode.__baload:
493 s.PopPrimitive();
494 s.PopObjectType();
495 s.PushPrimitive();
496 break;
497 case NormalizedByteCode.__bastore:
498 s.PopPrimitive();
499 s.PopPrimitive();
500 s.PopObjectType();
501 break;
502 case NormalizedByteCode.__caload:
503 s.PopPrimitive();
504 s.PopObjectType();
505 s.PushPrimitive();
506 break;
507 case NormalizedByteCode.__castore:
508 s.PopPrimitive();
509 s.PopPrimitive();
510 s.PopObjectType();
511 break;
512 case NormalizedByteCode.__saload:
513 s.PopPrimitive();
514 s.PopObjectType();
515 s.PushPrimitive();
516 break;
517 case NormalizedByteCode.__sastore:
518 s.PopPrimitive();
519 s.PopPrimitive();
520 s.PopObjectType();
521 break;
522 case NormalizedByteCode.__iaload:
523 s.PopPrimitive();
524 s.PopObjectType();
525 s.PushPrimitive();
526 break;
527 case NormalizedByteCode.__iastore:
528 s.PopPrimitive();
529 s.PopPrimitive();
530 s.PopObjectType();
531 break;
532 case NormalizedByteCode.__laload:
533 s.PopPrimitive();
534 s.PopObjectType();
535 s.PushWidePrimitive();
536 break;
537 case NormalizedByteCode.__lastore:
538 s.PopWidePrimitive();
539 s.PopPrimitive();
540 s.PopObjectType();
541 break;
542 case NormalizedByteCode.__daload:
543 s.PopPrimitive();
544 s.PopObjectType();
545 s.PushWidePrimitive();
546 break;
547 case NormalizedByteCode.__dastore:
548 s.PopWidePrimitive();
549 s.PopPrimitive();
550 s.PopObjectType();
551 break;
552 case NormalizedByteCode.__faload:
553 s.PopPrimitive();
554 s.PopObjectType();
555 s.PushPrimitive();
556 break;
557 case NormalizedByteCode.__fastore:
558 s.PopPrimitive();
559 s.PopPrimitive();
560 s.PopObjectType();
561 break;
562 case NormalizedByteCode.__arraylength:
563 s.PopObjectType();
564 s.PushPrimitive();
565 break;
566 case NormalizedByteCode.__iconst:
567 s.PushPrimitive();
568 break;
569 case NormalizedByteCode.__if_icmpeq:
570 case NormalizedByteCode.__if_icmpne:
571 case NormalizedByteCode.__if_icmplt:
572 case NormalizedByteCode.__if_icmpge:
573 case NormalizedByteCode.__if_icmpgt:
574 case NormalizedByteCode.__if_icmple:
575 s.PopPrimitive();
576 s.PopPrimitive();
577 break;
578 case NormalizedByteCode.__ifeq:
579 case NormalizedByteCode.__ifge:
580 case NormalizedByteCode.__ifgt:
581 case NormalizedByteCode.__ifle:
582 case NormalizedByteCode.__iflt:
583 case NormalizedByteCode.__ifne:
584 s.PopPrimitive();
585 break;
586 case NormalizedByteCode.__ifnonnull:
587 case NormalizedByteCode.__ifnull:
588 s.PopObjectType();
589 break;
590 case NormalizedByteCode.__if_acmpeq:
591 case NormalizedByteCode.__if_acmpne:
592 s.PopObjectType();
593 s.PopObjectType();
594 break;
595 case NormalizedByteCode.__getstatic:
596 s.PushType(GetFieldref(instr.Arg1).Signature);
597 break;
598 case NormalizedByteCode.__putstatic:
599 s.PopType(GetFieldref(instr.Arg1).Signature);
600 break;
601 case NormalizedByteCode.__getfield:
602 s.PopObjectType();
603 s.PushType(GetFieldref(instr.Arg1).Signature);
604 break;
605 case NormalizedByteCode.__putfield:
606 s.PopType(GetFieldref(instr.Arg1).Signature);
607 s.PopObjectType();
608 break;
609 case NormalizedByteCode.__ldc:
610 {
611 switch (GetConstantPoolConstantType(instr.Arg1))
612 {
613 case ClassFile.ConstantType.Double:
614 s.PushWidePrimitive();
615 break;
616 case ClassFile.ConstantType.Float:
617 s.PushPrimitive();
618 break;
619 case ClassFile.ConstantType.Integer:
620 s.PushPrimitive();
621 break;
622 case ClassFile.ConstantType.Long:
623 s.PushWidePrimitive();
624 break;
625 case ClassFile.ConstantType.String:
626 case ClassFile.ConstantType.Class:
627 s.PushObject();
628 break;
629 default:
630 // NOTE this is not a VerifyError, because it cannot happen (unless we have
631 // a bug in ClassFile.GetConstantPoolConstantType)
632 throw new InvalidOperationException();
633 }
634 break;
635 }
636 case NormalizedByteCode.__invokevirtual:
637 case NormalizedByteCode.__invokespecial:
638 case NormalizedByteCode.__invokeinterface:
639 case NormalizedByteCode.__invokestatic:
640 {
641 var cpi = GetMethodref(instr.Arg1);
642 s.MultiPopAnyType(cpi.GetArgTypes().Length);
643 if (instr.NormalizedOpCode != NormalizedByteCode.__invokestatic)
644 s.PopType();
645
646 var sig = cpi.Signature;
647 sig = sig.Substring(sig.IndexOf(')') + 1);
648 if (sig != "V")
649 s.PushType(sig);
650 break;
651 }
652 case NormalizedByteCode.__goto:
653 break;
654 case NormalizedByteCode.__istore:
655 s.PopPrimitive();
656 s.SetLocalPrimitive(instr.NormalizedArg1, i);
657 break;
658 case NormalizedByteCode.__iload:
659 s.PushPrimitive();
660 break;
661 case NormalizedByteCode.__ineg:
662 s.PopPrimitive();
663 s.PushPrimitive();
664 break;
665 case NormalizedByteCode.__iadd:
666 case NormalizedByteCode.__isub:
667 case NormalizedByteCode.__imul:
668 case NormalizedByteCode.__idiv:
669 case NormalizedByteCode.__irem:
670 case NormalizedByteCode.__iand:
671 case NormalizedByteCode.__ior:
672 case NormalizedByteCode.__ixor:
673 case NormalizedByteCode.__ishl:
674 case NormalizedByteCode.__ishr:
675 case NormalizedByteCode.__iushr:
676 s.PopPrimitive();
677 s.PopPrimitive();
678 s.PushPrimitive();
679 break;
680 case NormalizedByteCode.__lneg:
681 s.PopWidePrimitive();
682 s.PushWidePrimitive();
683 break;
684 case NormalizedByteCode.__ladd:
685 case NormalizedByteCode.__lsub:
686 case NormalizedByteCode.__lmul:
687 case NormalizedByteCode.__ldiv:
688 case NormalizedByteCode.__lrem:
689 case NormalizedByteCode.__land:
690 case NormalizedByteCode.__lor:
691 case NormalizedByteCode.__lxor:
692 s.PopWidePrimitive();
693 s.PopWidePrimitive();
694 s.PushWidePrimitive();
695 break;
696 case NormalizedByteCode.__lshl:
697 case NormalizedByteCode.__lshr:
698 case NormalizedByteCode.__lushr:
699 s.PopPrimitive();
700 s.PopWidePrimitive();
701 s.PushWidePrimitive();
702 break;
703 case NormalizedByteCode.__fneg:
704 s.PopPrimitive();
705 s.PushPrimitive();
706 break;
707 case NormalizedByteCode.__fadd:
708 case NormalizedByteCode.__fsub:
709 case NormalizedByteCode.__fmul:
710 case NormalizedByteCode.__fdiv:
711 case NormalizedByteCode.__frem:
712 s.PopPrimitive();
713 s.PopPrimitive();
714 s.PushPrimitive();
715 break;
716 case NormalizedByteCode.__dneg:
717 s.PopWidePrimitive();
718 s.PushWidePrimitive();
719 break;
720 case NormalizedByteCode.__dadd:
721 case NormalizedByteCode.__dsub:
722 case NormalizedByteCode.__dmul:
723 case NormalizedByteCode.__ddiv:
724 case NormalizedByteCode.__drem:
725 s.PopWidePrimitive();
726 s.PopWidePrimitive();
727 s.PushWidePrimitive();
728 break;
729 case NormalizedByteCode.__new:
730 s.PushObject();
731 break;
732 case NormalizedByteCode.__multianewarray:
733 {
734 if (instr.Arg2 < 1)
735 throw new VerifyError("Illegal dimension argument");
736
737 for (int j = 0; j < instr.Arg2; j++)
738 s.PopPrimitive();
739
740 s.PushObject();
741 break;
742 }
743 case NormalizedByteCode.__anewarray:
744 s.PopPrimitive();
745 s.PushObject();
746 break;
747 case NormalizedByteCode.__newarray:
748 s.PopPrimitive();
749 s.PushObject();
750 break;
751 case NormalizedByteCode.__swap:
752 {
753 var t1 = s.PopType();
754 var t2 = s.PopType();
755 s.PushType(t1);
756 s.PushType(t2);
757 break;
758 }
759 case NormalizedByteCode.__dup:
760 {
761 var t = s.PopType();
762 s.PushType(t);
763 s.PushType(t);
764 break;
765 }
766 case NormalizedByteCode.__dup2:
767 {
768 var t = s.PopAnyType();
769 if (t.IsWidePrimitive)
770 {
771 s.PushType(t);
772 s.PushType(t);
773 }
774 else
775 {
776 var t2 = s.PopType();
777 s.PushType(t2);
778 s.PushType(t);
779 s.PushType(t2);
780 s.PushType(t);
781 }
782 break;
783 }
784 case NormalizedByteCode.__dup_x1:
785 {
786 var value1 = s.PopType();
787 var value2 = s.PopType();
788 s.PushType(value1);
789 s.PushType(value2);
790 s.PushType(value1);
791 break;
792 }
793 case NormalizedByteCode.__dup2_x1:
794 {
795 var value1 = s.PopAnyType();
796 if (value1.IsWidePrimitive)
797 {
798 var value2 = s.PopType();
799 s.PushType(value1);
800 s.PushType(value2);
801 s.PushType(value1);
802 }
803 else
804 {
805 var value2 = s.PopType();
806 var value3 = s.PopType();
807 s.PushType(value2);
808 s.PushType(value1);
809 s.PushType(value3);
810 s.PushType(value2);
811 s.PushType(value1);
812 }
813 break;
814 }
815 case NormalizedByteCode.__dup_x2:
816 {
817 var value1 = s.PopType();
818 var value2 = s.PopAnyType();
819 if (value2.IsWidePrimitive)
820 {
821 s.PushType(value1);
822 s.PushType(value2);
823 s.PushType(value1);
824 }
825 else
826 {
827 var value3 = s.PopType();
828 s.PushType(value1);
829 s.PushType(value3);
830 s.PushType(value2);
831 s.PushType(value1);
832 }
833 break;
834 }
835 case NormalizedByteCode.__dup2_x2:
836 {
837 var value1 = s.PopAnyType();
838 if (value1.IsWidePrimitive)
839 {
840 var value2 = s.PopAnyType();
841 if (value2.IsWidePrimitive)
842 {
843 // Form 4
844 s.PushType(value1);
845 s.PushType(value2);
846 s.PushType(value1);
847 }
848 else
849 {
850 // Form 2
851 var value3 = s.PopType();
852 s.PushType(value1);
853 s.PushType(value3);
854 s.PushType(value2);
855 s.PushType(value1);
856 }
857 }
858 else
859 {
860 var value2 = s.PopType();
861 var value3 = s.PopAnyType();
862 if (value3.IsWidePrimitive)
863 {
864 // Form 3
865 s.PushType(value2);
866 s.PushType(value1);
867 s.PushType(value3);
868 s.PushType(value2);
869 s.PushType(value1);
870 }
871 else
872 {
873 // Form 4
874 var value4 = s.PopType();
875 s.PushType(value2);
876 s.PushType(value1);
877 s.PushType(value4);
878 s.PushType(value3);
879 s.PushType(value2);
880 s.PushType(value1);
881 }
882 }
883 break;
884 }
885 case NormalizedByteCode.__pop:
886 s.PopType();
887 break;
888 case NormalizedByteCode.__pop2:
889 {
890 var type = s.PopAnyType();
891 if (!type.IsWidePrimitive)
892 s.PopType();
893
894 break;
895 }
896 case NormalizedByteCode.__monitorenter:
897 case NormalizedByteCode.__monitorexit:
898 s.PopObjectType();
899 break;
900 case NormalizedByteCode.__return:
901 break;
902 case NormalizedByteCode.__areturn:
903 s.PopObjectType();
904 break;
905 case NormalizedByteCode.__ireturn:
906 s.PopPrimitive();
907 break;
908 case NormalizedByteCode.__lreturn:
909 s.PopWidePrimitive();
910 break;
911 case NormalizedByteCode.__freturn:
912 s.PopPrimitive();
913 break;
914 case NormalizedByteCode.__dreturn:
915 s.PopWidePrimitive();
916 break;
917 case NormalizedByteCode.__fload:
918 s.PushPrimitive();
919 break;
920 case NormalizedByteCode.__fstore:
921 s.PopPrimitive();
922 s.SetLocalPrimitive(instr.NormalizedArg1, i);
923 break;
924 case NormalizedByteCode.__dload:
925 s.PushWidePrimitive();
926 break;
927 case NormalizedByteCode.__dstore:
928 s.PopWidePrimitive();
929 s.SetLocalWidePrimitive(instr.NormalizedArg1, i);
930 break;
931 case NormalizedByteCode.__lload:
932 s.PushWidePrimitive();
933 break;
934 case NormalizedByteCode.__lstore:
935 s.PopWidePrimitive();
936 s.SetLocalWidePrimitive(instr.NormalizedArg1, i);
937 break;
938 case NormalizedByteCode.__lconst_0:
939 case NormalizedByteCode.__lconst_1:
940 s.PushWidePrimitive();
941 break;
942 case NormalizedByteCode.__fconst_0:
943 case NormalizedByteCode.__fconst_1:
944 case NormalizedByteCode.__fconst_2:
945 s.PushPrimitive();
946 break;
947 case NormalizedByteCode.__dconst_0:
948 case NormalizedByteCode.__dconst_1:
949 s.PushWidePrimitive();
950 break;
951 case NormalizedByteCode.__lcmp:
952 s.PopWidePrimitive();
953 s.PopWidePrimitive();
954 s.PushPrimitive();
955 break;
956 case NormalizedByteCode.__fcmpl:
957 case NormalizedByteCode.__fcmpg:
958 s.PopPrimitive();
959 s.PopPrimitive();
960 s.PushPrimitive();
961 break;
962 case NormalizedByteCode.__dcmpl:
963 case NormalizedByteCode.__dcmpg:
964 s.PopWidePrimitive();
965 s.PopWidePrimitive();
966 s.PushPrimitive();
967 break;
968 case NormalizedByteCode.__checkcast:
969 s.PopObjectType();
970 s.PushObject();
971 break;
972 case NormalizedByteCode.__instanceof:
973 s.PopObjectType();
974 s.PushPrimitive();
975 break;
976 case NormalizedByteCode.__iinc:
977 break;
978 case NormalizedByteCode.__athrow:
979 s.PopObjectType();
980 break;
981 case NormalizedByteCode.__tableswitch:
982 case NormalizedByteCode.__lookupswitch:
983 s.PopPrimitive();
984 break;
985 case NormalizedByteCode.__i2b:
986 s.PopPrimitive();
987 s.PushPrimitive();
988 break;
989 case NormalizedByteCode.__i2c:
990 s.PopPrimitive();
991 s.PushPrimitive();
992 break;
993 case NormalizedByteCode.__i2s:
994 s.PopPrimitive();
995 s.PushPrimitive();
996 break;
997 case NormalizedByteCode.__i2l:
998 s.PopPrimitive();
999 s.PushWidePrimitive();
1000 break;
1001 case NormalizedByteCode.__i2f:
1002 s.PopPrimitive();
1003 s.PushPrimitive();
1004 break;
1005 case NormalizedByteCode.__i2d:
1006 s.PopPrimitive();
1007 s.PushWidePrimitive();
1008 break;
1009 case NormalizedByteCode.__l2i:
1010 s.PopWidePrimitive();
1011 s.PushPrimitive();
1012 break;
1013 case NormalizedByteCode.__l2f:
1014 s.PopWidePrimitive();
1015 s.PushPrimitive();
1016 break;
1017 case NormalizedByteCode.__l2d:
1018 s.PopWidePrimitive();
1019 s.PushWidePrimitive();
1020 break;
1021 case NormalizedByteCode.__f2i:
1022 s.PopPrimitive();
1023 s.PushPrimitive();
1024 break;
1025 case NormalizedByteCode.__f2l:
1026 s.PopPrimitive();
1027 s.PushWidePrimitive();
1028 break;
1029 case NormalizedByteCode.__f2d:
1030 s.PopPrimitive();
1031 s.PushWidePrimitive();
1032 break;
1033 case NormalizedByteCode.__d2i:
1034 s.PopWidePrimitive();
1035 s.PushPrimitive();
1036 break;
1037 case NormalizedByteCode.__d2f:
1038 s.PopWidePrimitive();
1039 s.PushPrimitive();
1040 break;
1041 case NormalizedByteCode.__d2l:
1042 s.PopWidePrimitive();
1043 s.PushWidePrimitive();
1044 break;
1045 case NormalizedByteCode.__jsr:
1046 // TODO make sure we're not calling a subroutine we're already in
1047 break;
1048 case NormalizedByteCode.__ret:
1049 {
1050 // TODO if we're returning from a higher level subroutine, invalidate
1051 // all the intermediate return addresses
1052 var subroutineIndex = s.GetLocalRet(instr.Arg1);
1053 s.CheckSubroutineActive(subroutineIndex);
1054 break;
1055 }
1056 case NormalizedByteCode.__nop:
1057 if (i + 1 == instructions.Length)
1058 throw new VerifyError("Falling off the end of the code");
1059
1060 break;
1061 case NormalizedByteCode.__invokedynamic:
1062 // it is impossible to have a valid invokedynamic in a pre-7.0 class file
1063 throw new VerifyError("Illegal type in constant pool");
1064 default:
1065 throw new NotImplementedException(instr.NormalizedOpCode.ToString());
1066 }
1067
1068 if (s.GetStackHeight() > method.MaxStack)
1069 throw new VerifyError("Stack size too large");
1070
1071 for (int j = 0; j < method.ExceptionTable.Length; j++)
1072 if (method.ExceptionTable[j].endIndex == i + 1)
1073 MergeExceptionHandler(method.ExceptionTable[j].handlerIndex, s);
1074
1075 try
1076 {
1077 // another big switch to handle the opcode targets
1078 switch (instr.NormalizedOpCode)
1079 {
1080 case NormalizedByteCode.__tableswitch:
1081 case NormalizedByteCode.__lookupswitch:
1082 for (int j = 0; j < instr.SwitchEntryCount; j++)
1083 {
1084 _state[instr.GetSwitchTargetIndex(j)] += s;
1085 }
1086 _state[instr.DefaultTarget] += s;
1087 break;
1088 case NormalizedByteCode.__ifeq:
1089 case NormalizedByteCode.__ifne:
1090 case NormalizedByteCode.__iflt:
1091 case NormalizedByteCode.__ifge:
1092 case NormalizedByteCode.__ifgt:
1093 case NormalizedByteCode.__ifle:
1094 case NormalizedByteCode.__if_icmpeq:
1095 case NormalizedByteCode.__if_icmpne:
1096 case NormalizedByteCode.__if_icmplt:
1097 case NormalizedByteCode.__if_icmpge:
1098 case NormalizedByteCode.__if_icmpgt:
1099 case NormalizedByteCode.__if_icmple:
1100 case NormalizedByteCode.__if_acmpeq:
1101 case NormalizedByteCode.__if_acmpne:
1102 case NormalizedByteCode.__ifnull:
1103 case NormalizedByteCode.__ifnonnull:
1104 _state[i + 1] += s;
1105 _state[instr.TargetIndex] += s;
1106 break;
1107 case NormalizedByteCode.__goto:
1108 _state[instr.TargetIndex] += s;
1109 break;
1110 case NormalizedByteCode.__jsr:
1111 {
1112 int index = instr.TargetIndex;
1113 s.SetSubroutineId(index);
1114
1115 if (returnAddressTypes.TryGetValue(index, out var retAddressType) == false)
1116 {
1117 retAddressType = SimpleType.MakeRet(index);
1118 returnAddressTypes[index] = retAddressType;
1119 }
1120
1121 s.PushType(retAddressType);
1122 _state[index] += s;
1123
1124 var returns = GetReturnSites(i);
1125 if (returns != null)
1126 foreach (int returnIndex in returns)
1127 _state[i + 1] = InstructionState.MergeSubroutineReturn(_state[i + 1], s, _state[returnIndex], _state[returnIndex].GetLocalsModified(index));
1128
1129 AddCallSite(index, i);
1130 break;
1131 }
1132 case NormalizedByteCode.__ret:
1133 {
1134 // HACK if the ret is processed before all of the jsr instructions to this subroutine
1135 // we wouldn't be able to properly merge, so that is why we track the number of callsites
1136 // for each subroutine instruction (see Instruction.AddCallSite())
1137 var subroutineIndex = s.GetLocalRet(instr.Arg1);
1138 var cs = GetCallSites(subroutineIndex);
1139 var locals_modified = s.GetLocalsModified(subroutineIndex);
1140 for (int j = 0; j < cs.Length; j++)
1141 {
1142 AddReturnSite(cs[j], i);
1143 _state[cs[j] + 1] = InstructionState.MergeSubroutineReturn(_state[cs[j] + 1], _state[cs[j]], s, locals_modified);
1144 }
1145
1146 break;
1147 }
1148 case NormalizedByteCode.__ireturn:
1149 case NormalizedByteCode.__lreturn:
1150 case NormalizedByteCode.__freturn:
1151 case NormalizedByteCode.__dreturn:
1152 case NormalizedByteCode.__areturn:
1153 case NormalizedByteCode.__return:
1154 case NormalizedByteCode.__athrow:
1155 break;
1156 default:
1157 _state[i + 1] += s;
1158 break;
1159 }
1160 }
1161 catch (IndexOutOfRangeException)
1162 {
1163 // we're going to assume that this always means that we have an invalid branch target
1164 // NOTE because PcIndexMap returns -1 for illegal PCs (in the middle of an instruction) and
1165 // we always use that value as an index into the state array, any invalid PC will result
1166 // in an IndexOutOfRangeException
1167 throw new VerifyError("Illegal target of jump or branch");
1168 }
1169 }
1170 catch (VerifyError x)
1171 {
1172 var opcode = instructions[i].NormalizedOpCode.ToString();
1173 if (opcode.StartsWith("__"))
1174 opcode = opcode.Substring(2);
1175
1176 throw new VerifyError($"{x.Message} (class: {classFile.Name}, method: {method.Name}, signature: {method.Signature}, offset: {instructions[i].PC}, instruction: {opcode})", x);
1177 }
1178 }
1179 }
1180 }
1181
1182 // Now we do another pass to compute reachability
1183 done = false;
1184 flags[0] |= InstructionFlags.Reachable;
1185
1186 while (!done)
1187 {
1188 done = true;
1189 var didJsrOrRet = false;
1190 for (int i = 0; i < instructions.Length; i++)
1191 {
1192 if ((flags[i] & (InstructionFlags.Reachable | InstructionFlags.Processed)) == InstructionFlags.Reachable)
1193 {
1194 done = false;
1195 flags[i] |= InstructionFlags.Processed;
1196
1197 // mark the exception handlers reachable from this instruction
1198 for (int j = 0; j < method.ExceptionTable.Length; j++)
1199 if (method.ExceptionTable[j].startIndex <= i && i < method.ExceptionTable[j].endIndex)
1200 flags[method.ExceptionTable[j].handlerIndex] |= InstructionFlags.Reachable | InstructionFlags.BranchTarget;
1201
1202 // mark the successor instructions
1203 switch (instructions[i].NormalizedOpCode)
1204 {
1205 case NormalizedByteCode.__tableswitch:
1206 case NormalizedByteCode.__lookupswitch:
1207 {
1208 var hasbackbranch = false;
1209 for (int j = 0; j < instructions[i].SwitchEntryCount; j++)
1210 {
1211 hasbackbranch |= instructions[i].GetSwitchTargetIndex(j) < i;
1212 flags[instructions[i].GetSwitchTargetIndex(j)] |= InstructionFlags.Reachable | InstructionFlags.BranchTarget;
1213 }
1214
1215 hasbackbranch |= instructions[i].DefaultTarget < i;
1216 flags[instructions[i].DefaultTarget] |= InstructionFlags.Reachable | InstructionFlags.BranchTarget;
1217 break;
1218 }
1219 case NormalizedByteCode.__goto:
1220 flags[instructions[i].TargetIndex] |= InstructionFlags.Reachable | InstructionFlags.BranchTarget;
1221 break;
1222 case NormalizedByteCode.__ifeq:
1223 case NormalizedByteCode.__ifne:
1224 case NormalizedByteCode.__iflt:
1225 case NormalizedByteCode.__ifge:
1226 case NormalizedByteCode.__ifgt:
1227 case NormalizedByteCode.__ifle:
1228 case NormalizedByteCode.__if_icmpeq:
1229 case NormalizedByteCode.__if_icmpne:
1230 case NormalizedByteCode.__if_icmplt:
1231 case NormalizedByteCode.__if_icmpge:
1232 case NormalizedByteCode.__if_icmpgt:
1233 case NormalizedByteCode.__if_icmple:
1234 case NormalizedByteCode.__if_acmpeq:
1235 case NormalizedByteCode.__if_acmpne:
1236 case NormalizedByteCode.__ifnull:
1237 case NormalizedByteCode.__ifnonnull:
1238 flags[instructions[i].TargetIndex] |= InstructionFlags.Reachable | InstructionFlags.BranchTarget;
1239 flags[i + 1] |= InstructionFlags.Reachable;
1240 break;
1241 case NormalizedByteCode.__jsr:
1242 flags[instructions[i].TargetIndex] |= InstructionFlags.Reachable | InstructionFlags.BranchTarget;
1243 // Note that we don't mark the next instruction as reachable,
1244 // because that depends on the corresponding ret actually being
1245 // reachable. We handle this in the loop below.
1246 didJsrOrRet = true;
1247 break;
1248 case NormalizedByteCode.__ret:
1249 // Note that we can't handle ret here, because we might encounter the ret
1250 // before having seen all the corresponding jsr instructions, so we can't
1251 // update all the call sites.
1252 // We handle ret in the loop below.
1253 didJsrOrRet = true;
1254 break;
1255 case NormalizedByteCode.__ireturn:
1256 case NormalizedByteCode.__lreturn:
1257 case NormalizedByteCode.__freturn:
1258 case NormalizedByteCode.__dreturn:
1259 case NormalizedByteCode.__areturn:
1260 case NormalizedByteCode.__return:
1261 case NormalizedByteCode.__athrow:
1262 break;
1263 default:
1264 flags[i + 1] |= InstructionFlags.Reachable;
1265 break;
1266 }
1267 }
1268 }
1269
1270 if (didJsrOrRet)
1271 {
1272 for (int i = 0; i < instructions.Length; i++)
1273 {
1274 if (instructions[i].NormalizedOpCode == NormalizedByteCode.__ret && (flags[i] & InstructionFlags.Reachable) != 0)
1275 {
1276 var subroutineIndex = _state[i].GetLocalRet(instructions[i].Arg1);
1277 var cs = GetCallSites(subroutineIndex);
1278 for (int j = 0; j < cs.Length; j++)
1279 if ((flags[cs[j]] & InstructionFlags.Reachable) != 0)
1280 flags[cs[j] + 1] |= InstructionFlags.Reachable | InstructionFlags.BranchTarget;
1281 }
1282 }
1283 }
1284 }
1285 }
1286
1287 void MergeExceptionHandler(int handlerIndex, InstructionState curr)
1288 {
1289 // NOTE this used to be CopyLocalsAndSubroutines, but it doesn't (always) make
1290 // sense to copy the subroutine state
1291 // TODO figure out if there are circumstances under which it does make sense
1292 // to copy the active subroutine state
1293 // UPDATE subroutines must be copied as well, but I think I now have a better
1294 // understanding of subroutine merges, so the problems that triggered the previous
1295 // change here hopefully won't arise anymore
1296 var ex = curr.CopyLocalsAndSubroutines();
1297 ex.PushObject();
1298 _state[handlerIndex] += ex;
1299 }
1300
1301 ClassFile.ConstantPoolItemMI GetMethodref(int index)
1302 {
1303 try
1304 {
1305 var item = _classFile.GetMethodref(new MethodrefConstantHandle(checked((ushort)index)));
1306 if (item != null)
1307 return item;
1308 }
1309 catch (OverflowException)
1310 {
1311 // constant pool index isn't ushort
1312 }
1313 catch (InvalidCastException)
1314 {
1315
1316 }
1317 catch (IndexOutOfRangeException)
1318 {
1319
1320 }
1321
1322 throw new VerifyError("Illegal constant pool index");
1323 }
1324
1325 ClassFile.ConstantPoolItemFieldref GetFieldref(int index)
1326 {
1327 try
1328 {
1329 var item = _classFile.GetFieldref(new FieldrefConstantHandle(checked((ushort)index)));
1330 if (item != null)
1331 return item;
1332 }
1333 catch (OverflowException)
1334 {
1335 // constant pool index isn't ushort
1336 }
1337 catch (InvalidCastException)
1338 {
1339 // constant pool index isn't ushort
1340 }
1341 catch (IndexOutOfRangeException)
1342 {
1343
1344 }
1345
1346 throw new VerifyError("Illegal constant pool index");
1347 }
1348
1349 ClassFile.ConstantType GetConstantPoolConstantType(int index)
1350 {
1351 try
1352 {
1353 return _classFile.GetConstantPoolConstantType(new ConstantHandle(ConstantKind.Unknown, checked((ushort)index)));
1354 }
1355 catch (OverflowException)
1356 {
1357 // constant pool index isn't ushort
1358 }
1359 catch (InvalidCastException)
1360 {
1361 // constant pool index isn't ushort
1362 }
1363 catch (IndexOutOfRangeException)
1364 {
1365 // constant pool index out of range
1366 }
1367 catch (InvalidOperationException)
1368 {
1369 // specified constant pool entry doesn't contain a constant
1370 }
1371 catch (NullReferenceException)
1372 {
1373 // specified constant pool entry is empty (entry 0 or the filler following a wide entry)
1374 }
1375
1376 throw new VerifyError("Illegal constant pool index");
1377 }
1378
1379 void AddReturnSite(int callSiteIndex, int returnSiteIndex)
1380 {
1381 _returnsites[callSiteIndex] ??= new List<int>();
1382
1383 var l = _returnsites[callSiteIndex];
1384 if (l.IndexOf(returnSiteIndex) == -1)
1385 {
1386 _state[callSiteIndex].changed = true;
1387 l.Add(returnSiteIndex);
1388 }
1389 }
1390
1391 List<int> GetReturnSites(int callSiteIndex)
1392 {
1393 return _returnsites[callSiteIndex];
1394 }
1395
1396 void AddCallSite(int subroutineIndex, int callSiteIndex)
1397 {
1398 _callsites[subroutineIndex] ??= new List<int>();
1399
1400 var l = _callsites[subroutineIndex];
1401 if (l.IndexOf(callSiteIndex) == -1)
1402 {
1403 l.Add(callSiteIndex);
1404 _state[subroutineIndex].AddCallSite();
1405 }
1406 }
1407
1408 int[] GetCallSites(int subroutineIndex)
1409 {
1410 return _callsites[subroutineIndex].ToArray();
1411 }
1412
1413 internal SimpleType GetLocalTypeWrapper(int index, int local)
1414 {
1415 return _state[index].GetLocalTypeEx(local);
1416 }
1417
1418 internal bool IsSubroutineActive(int instructionIndex, int subroutineIndex)
1419 {
1420 return _state[instructionIndex].IsSubroutineActive(subroutineIndex);
1421 }
1422
1423 sealed class Subroutine
1424 {
1425
1426 readonly int subroutineIndex;
1427 readonly bool[] localsModified;
1428
1434 Subroutine(int subroutineIndex, bool[] localsModified)
1435 {
1436 this.subroutineIndex = subroutineIndex;
1437 this.localsModified = localsModified;
1438 }
1439
1445 internal Subroutine(int subroutineIndex, int maxLocals)
1446 {
1447 this.subroutineIndex = subroutineIndex;
1448 localsModified = new bool[maxLocals];
1449 }
1450
1451 internal int SubroutineIndex => subroutineIndex;
1452
1453 internal bool[] LocalsModified => localsModified;
1454
1455 internal void SetLocalModified(int local)
1456 {
1457 localsModified[local] = true;
1458 }
1459
1460 internal Subroutine Copy()
1461 {
1462 return new Subroutine(subroutineIndex, (bool[])localsModified.Clone());
1463 }
1464
1465 }
1466
1467 sealed class InstructionState
1468 {
1469
1470 enum ShareFlags : byte
1471 {
1472 None = 0,
1473 Stack = 1,
1474 Locals = 2,
1475 Subroutines = 4,
1476 All = Stack | Locals | Subroutines
1477 }
1478
1479 SimpleType[] stack;
1480 int stackSize;
1481 int stackEnd;
1482 SimpleType[] locals;
1483 List<Subroutine> subroutines;
1484 int callsites;
1485 internal bool changed = true;
1486 ShareFlags flags;
1487
1497 private InstructionState(SimpleType[] stack, int stackSize, int stackEnd, SimpleType[] locals, List<Subroutine> subroutines, int callsites)
1498 {
1499 this.flags = ShareFlags.All;
1500 this.stack = stack;
1501 this.stackSize = stackSize;
1502 this.stackEnd = stackEnd;
1503 this.locals = locals;
1504 this.subroutines = subroutines;
1505 this.callsites = callsites;
1506 }
1507
1513 internal InstructionState(int maxLocals, int maxStack)
1514 {
1515 this.flags = ShareFlags.None;
1516 this.stack = new SimpleType[maxStack];
1517 this.stackEnd = maxStack;
1518 this.locals = new SimpleType[maxLocals];
1519 }
1520
1521 internal InstructionState Copy()
1522 {
1523 return new InstructionState(stack, stackSize, stackEnd, locals, subroutines, callsites);
1524 }
1525
1526 internal void CopyTo(InstructionState target)
1527 {
1528 target.flags = ShareFlags.All;
1529 target.stack = stack;
1530 target.stackSize = stackSize;
1531 target.stackEnd = stackEnd;
1532 target.locals = locals;
1533 target.subroutines = subroutines;
1534 target.callsites = callsites;
1535 target.changed = true;
1536 }
1537
1538 internal InstructionState CopyLocalsAndSubroutines()
1539 {
1540 var copy = new InstructionState(new SimpleType[stack.Length], 0, stack.Length, locals, subroutines, callsites);
1541 copy.flags &= ~ShareFlags.Stack;
1542 return copy;
1543 }
1544
1545 private static List<Subroutine> CopySubroutines(List<Subroutine> l)
1546 {
1547 if (l == null)
1548 return null;
1549
1550 var n = new List<Subroutine>(l.Count);
1551 foreach (var s in l)
1552 n.Add(s.Copy());
1553
1554 return n;
1555 }
1556
1557 private void MergeSubroutineHelper(InstructionState s2)
1558 {
1559 if (subroutines == null || s2.subroutines == null)
1560 {
1561 if (subroutines != null)
1562 {
1563 subroutines = null;
1564 changed = true;
1565 }
1566 }
1567 else
1568 {
1569 SubroutinesCopyOnWrite();
1570
1571 var ss1 = subroutines;
1572 subroutines = new List<Subroutine>();
1573 foreach (var ss2 in s2.subroutines)
1574 {
1575 foreach (var ss in ss1)
1576 {
1577 if (ss.SubroutineIndex == ss2.SubroutineIndex)
1578 {
1579 subroutines.Add(ss);
1580 for (int i = 0; i < ss.LocalsModified.Length; i++)
1581 {
1582 if (ss2.LocalsModified[i] && !ss.LocalsModified[i])
1583 {
1584 ss.LocalsModified[i] = true;
1585 changed = true;
1586 }
1587 }
1588 }
1589 }
1590 }
1591
1592 if (ss1.Count != subroutines.Count)
1593 changed = true;
1594 }
1595
1596 if (s2.callsites > callsites)
1597 {
1598 //Console.WriteLine("s2.callsites = {0}, callsites = {1}", s2.callsites, callsites);
1599 callsites = s2.callsites;
1600 changed = true;
1601 }
1602 }
1603
1604 internal static InstructionState MergeSubroutineReturn(InstructionState jsrSuccessor, InstructionState jsr, InstructionState ret, bool[] locals_modified)
1605 {
1606 var next = ret.Copy();
1607 next.LocalsCopyOnWrite();
1608
1609 for (int i = 0; i < locals_modified.Length; i++)
1610 if (!locals_modified[i])
1611 next.locals[i] = jsr.locals[i];
1612
1613 next.flags |= ShareFlags.Subroutines;
1614 next.subroutines = jsr.subroutines;
1615 next.callsites = jsr.callsites;
1616 return jsrSuccessor + next;
1617 }
1618
1619 public static InstructionState operator +(InstructionState s1, InstructionState s2)
1620 {
1621 if (s1 == null)
1622 return s2.Copy();
1623
1624 if (s1.stackSize != s2.stackSize || s1.stackEnd != s2.stackEnd)
1625 throw new VerifyError($"Inconsistent stack height: {s1.stackSize + s1.stack.Length - s1.stackEnd} != {s2.stackSize + s2.stack.Length - s2.stackEnd}");
1626
1627 var s = s1.Copy();
1628 s.changed = s1.changed;
1629 for (int i = 0; i < s.stackSize; i++)
1630 {
1631 var type = s.stack[i];
1632 var type2 = s2.stack[i];
1633 if (type == type2)
1634 {
1635 // perfect match, nothing to do
1636 }
1637 else if (!type.IsPrimitive)
1638 {
1639 var baseType = InstructionState.FindCommonBaseType(type, type2);
1640 if (baseType == SimpleType.Invalid)
1641 {
1642 if (SimpleType.IsRet(type) && SimpleType.IsRet(type2))
1643 {
1644 // if we never return from a subroutine, it is legal to merge to subroutine flows
1645 // (this is from the Mauve test subr.pass.mergeok)
1646 }
1647 else
1648 {
1649 throw new VerifyError(string.Format("cannot merge {0} and {1}", type, type2));
1650 }
1651 }
1652 if (type != baseType)
1653 {
1654 s.StackCopyOnWrite();
1655 s.stack[i] = baseType;
1656 s.changed = true;
1657 }
1658 }
1659 else
1660 {
1661 throw new VerifyError(string.Format("cannot merge {0} and {1}", type, type2));
1662 }
1663 }
1664
1665 for (int i = 0; i < s.locals.Length; i++)
1666 {
1667 var type = s.locals[i];
1668 var type2 = s2.locals[i];
1669 var baseType = InstructionState.FindCommonBaseType(type, type2);
1670 if (type != baseType)
1671 {
1672 s.LocalsCopyOnWrite();
1673 s.locals[i] = baseType;
1674 s.changed = true;
1675 }
1676 }
1677
1678 s.MergeSubroutineHelper(s2);
1679 return s;
1680 }
1681
1682 internal void AddCallSite()
1683 {
1684 callsites++;
1685 changed = true;
1686 }
1687
1688 internal void SetSubroutineId(int subroutineIndex)
1689 {
1690 SubroutinesCopyOnWrite();
1691
1692 if (subroutines == null)
1693 {
1694 subroutines = new List<Subroutine>();
1695 }
1696 else
1697 {
1698 foreach (var s in subroutines)
1699 {
1700 if (s.SubroutineIndex == subroutineIndex)
1701 {
1702 // subroutines cannot recursivly call themselves
1703 throw new VerifyError("subroutines cannot recurse");
1704 }
1705 }
1706 }
1707
1708 subroutines.Add(new Subroutine(subroutineIndex, locals.Length));
1709 }
1710
1711 internal bool[] GetLocalsModified(int subroutineIndex)
1712 {
1713 if (subroutines != null)
1714 foreach (var s in subroutines)
1715 if (s.SubroutineIndex == subroutineIndex)
1716 return s.LocalsModified;
1717
1718 throw new VerifyError("return from wrong subroutine");
1719 }
1720
1721 internal bool IsSubroutineActive(int subroutineIndex)
1722 {
1723 if (subroutines != null)
1724 foreach (var s in subroutines)
1725 if (s.SubroutineIndex == subroutineIndex)
1726 return true;
1727
1728 return false;
1729 }
1730
1731 internal void CheckSubroutineActive(int subroutineIndex)
1732 {
1733 if (!IsSubroutineActive(subroutineIndex))
1734 throw new VerifyError("inactive subroutine");
1735 }
1736
1737 internal static SimpleType FindCommonBaseType(SimpleType type1, SimpleType type2)
1738 {
1739 if (type1 == type2)
1740 return type1;
1741
1742 if (type1 == SimpleType.Object)
1743 return type2;
1744
1745 if (type2 == SimpleType.Object)
1746 return type1;
1747
1748 if (type1 == SimpleType.Invalid || type2 == SimpleType.Invalid)
1749 return SimpleType.Invalid;
1750
1751 if (type1.IsPrimitive || type2.IsPrimitive)
1752 return SimpleType.Invalid;
1753
1754 if (SimpleType.IsRet(type1) || SimpleType.IsRet(type2))
1755 return SimpleType.Invalid;
1756
1757 return SimpleType.Object;
1758 }
1759
1760 void SetLocal1(int index, SimpleType type)
1761 {
1762 try
1763 {
1764 LocalsCopyOnWrite();
1765 SubroutinesCopyOnWrite();
1766
1767 if (index > 0 && locals[index - 1] != SimpleType.Invalid && locals[index - 1].IsWidePrimitive)
1768 {
1769 locals[index - 1] = SimpleType.Invalid;
1770 if (subroutines != null)
1771 foreach (var s in subroutines)
1772 s.SetLocalModified(index - 1);
1773 }
1774
1775 locals[index] = type;
1776 if (subroutines != null)
1777 foreach (var s in subroutines)
1778 s.SetLocalModified(index);
1779 }
1780 catch (IndexOutOfRangeException)
1781 {
1782 throw new VerifyError("Illegal local variable number");
1783 }
1784 }
1785
1786 void SetLocal2(int index, SimpleType type)
1787 {
1788 try
1789 {
1790 LocalsCopyOnWrite();
1791 SubroutinesCopyOnWrite();
1792
1793 if (index > 0 && locals[index - 1] != SimpleType.Invalid && locals[index - 1].IsWidePrimitive)
1794 {
1795 locals[index - 1] = SimpleType.Invalid;
1796 if (subroutines != null)
1797 foreach (var s in subroutines)
1798 s.SetLocalModified(index - 1);
1799 }
1800
1801 locals[index] = type;
1802 locals[index + 1] = SimpleType.Invalid;
1803
1804 if (subroutines != null)
1805 {
1806 foreach (var s in subroutines)
1807 {
1808 s.SetLocalModified(index);
1809 s.SetLocalModified(index + 1);
1810 }
1811 }
1812 }
1813 catch (IndexOutOfRangeException)
1814 {
1815 throw new VerifyError("Illegal local variable number");
1816 }
1817 }
1818
1819 internal void SetLocalPrimitive(int index, int instructionIndex)
1820 {
1821 SetLocal1(index, SimpleType.Primitive);
1822 }
1823
1824 internal void SetLocalWidePrimitive(int index, int instructionIndex)
1825 {
1826 SetLocal2(index, SimpleType.WidePrimitive);
1827 }
1828
1829 internal SimpleType GetLocalType(int index)
1830 {
1831 try
1832 {
1833 return locals[index];
1834 }
1835 catch (IndexOutOfRangeException)
1836 {
1837 throw new VerifyError("Illegal local variable number");
1838 }
1839 }
1840
1841 // this is used by the compiler (indirectly, through MethodAnalyzer.GetLocalTypeWrapper),
1842 // we've already verified the code so we know we won't run outside the array boundary,
1843 // and we don't need to record the fact that we're reading the local.
1844 internal SimpleType GetLocalTypeEx(int index)
1845 {
1846 return locals[index];
1847 }
1848
1849 internal int GetLocalRet(int index)
1850 {
1851 var type = GetLocalType(index);
1852 if (SimpleType.IsRet(type))
1853 return type.SubroutineIndex;
1854
1855 throw new VerifyError("incorrect local type, not ret");
1856 }
1857
1858 internal void SetLocalType(int index, SimpleType type, int instructionIndex)
1859 {
1860 if (type.IsWidePrimitive)
1861 SetLocalWidePrimitive(index, instructionIndex);
1862 else
1863 SetLocal1(index, type);
1864 }
1865
1866 internal void PushType(string signature)
1867 {
1868 switch (signature[0])
1869 {
1870 case 'J':
1871 case 'D':
1872 PushWidePrimitive();
1873 break;
1874 case '[':
1875 case 'L':
1876 PushObject();
1877 break;
1878 default:
1879 PushPrimitive();
1880 break;
1881 }
1882 }
1883
1884 internal void PushWidePrimitive()
1885 {
1886 PushType(SimpleType.WidePrimitive);
1887 }
1888
1889 internal void PushPrimitive()
1890 {
1891 PushType(SimpleType.Primitive);
1892 }
1893
1894 internal void PushObject()
1895 {
1896 PushType(SimpleType.Object);
1897 }
1898
1899 // object reference or a subroutine return address
1900 internal SimpleType PopObjectType()
1901 {
1902 var type = PopType();
1903 if (type.IsPrimitive)
1904 throw new VerifyError("Expected object reference on stack");
1905
1906 return type;
1907 }
1908
1909 internal void MultiPopAnyType(int count)
1910 {
1911 while (count-- != 0)
1912 PopAnyType();
1913 }
1914
1915 internal SimpleType PopAnyType()
1916 {
1917 if (stackSize == 0)
1918 throw new VerifyError("Unable to pop operand off an empty stack");
1919
1920 var type = stack[--stackSize];
1921 if (type.IsWidePrimitive)
1922 stackEnd++;
1923
1924 return type;
1925 }
1926
1927 // NOTE this can *not* be used to pop double or long
1928 internal SimpleType PopType()
1929 {
1930 var type = PopAnyType();
1931 if (type.IsWidePrimitive)
1932 throw new VerifyError("Attempt to split long or double on the stack");
1933
1934 return type;
1935 }
1936
1937 internal void PopPrimitive()
1938 {
1939 if (!PopType().IsPrimitive)
1940 throw new VerifyError("Primitive type expected on stack");
1941 }
1942
1943 internal void PopWidePrimitive()
1944 {
1945 var type = PopAnyType();
1946 if (type != SimpleType.WidePrimitive)
1947 throw new VerifyError("Wide primitive type expected on stack");
1948 }
1949
1950 internal void PopType(string signature)
1951 {
1952 switch (signature[0])
1953 {
1954 case 'J':
1955 case 'D':
1956 PopWidePrimitive();
1957 break;
1958 case '[':
1959 case 'L':
1960 PopObjectType();
1961 break;
1962 default:
1963 PopPrimitive();
1964 break;
1965 }
1966 }
1967
1968 internal int GetStackHeight()
1969 {
1970 return stackSize;
1971 }
1972
1973 internal void PushType(SimpleType type)
1974 {
1975 if (type.IsWidePrimitive)
1976 stackEnd--;
1977
1978 if (stackSize >= stackEnd)
1979 throw new VerifyError("Stack overflow");
1980
1981 StackCopyOnWrite();
1982 stack[stackSize++] = type;
1983 }
1984
1985 private void StackCopyOnWrite()
1986 {
1987 if ((flags & ShareFlags.Stack) != 0)
1988 {
1989 flags &= ~ShareFlags.Stack;
1990 stack = (SimpleType[])stack.Clone();
1991 }
1992 }
1993
1994 private void LocalsCopyOnWrite()
1995 {
1996 if ((flags & ShareFlags.Locals) != 0)
1997 {
1998 flags &= ~ShareFlags.Locals;
1999 locals = (SimpleType[])locals.Clone();
2000 }
2001 }
2002
2003 private void SubroutinesCopyOnWrite()
2004 {
2005 if ((flags & ShareFlags.Subroutines) != 0)
2006 {
2007 flags &= ~ShareFlags.Subroutines;
2008 subroutines = CopySubroutines(subroutines);
2009 }
2010 }
2011
2012 internal void DumpLocals()
2013 {
2014 Console.Write("// ");
2015 string sep = "";
2016 for (int i = 0; i < locals.Length; i++)
2017 {
2018 Console.Write(sep);
2019 Console.Write(locals[i]);
2020 sep = ", ";
2021 }
2022 Console.WriteLine();
2023 }
2024
2025 internal void DumpStack()
2026 {
2027 Console.Write("// ");
2028 string sep = "";
2029 for (int i = 0; i < stackSize; i++)
2030 {
2031 Console.Write(sep);
2032 Console.Write(stack[i]);
2033 sep = ", ";
2034 }
2035 Console.WriteLine();
2036 }
2037
2038 internal void DumpSubroutines()
2039 {
2040 Console.Write("// subs: ");
2041 string sep = "";
2042 if (subroutines != null)
2043 {
2044 for (int i = 0; i < subroutines.Count; i++)
2045 {
2046 Console.Write(sep);
2047 Console.Write(((Subroutine)subroutines[i]).SubroutineIndex);
2048 sep = ", ";
2049 }
2050 }
2051 Console.WriteLine();
2052 }
2053
2054 }
2055
2056 }
2057
2058 }
2059
2060}
InstructionFlags
IKVM.Runtime.ClassFile.Method.InstructionFlags InstructionFlags
Definition atomic.cs:37
IKVM.Runtime.JsrInliner
A customized and simplified version of MethodAnalyzer that exists purely to inline jsr instructions.
Definition JsrInliner.cs:38
IKVM.Runtime.RuntimeClassLoader
Runtime support for a class loader.
Definition RuntimeClassLoader.cs:61
IKVM.Runtime.InstructionState.LocalsCopyOnWrite
void LocalsCopyOnWrite()
Copies the locals for future modification.
Definition InstructionState.cs:863