001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.common.assembler;
014
015 import org.jikesrvm.VM;
016
017 /**
018 *
019 * A forward reference has a machine-code-index source and optionally
020 * a bytecode-index target. The idea is to fix up the instruction at
021 * the source when the machine-code-index of the target is known.
022 * There need not be an explicit target, if the reference is used (by
023 * the compiler) within the machine-code for one bytecode.
024 *
025 * There are three kinds of forward reference:
026 * 1) unconditional branches
027 * 2) conditional branches
028 * 3) switch cases
029 * Each subclass must be able to resolve itself.
030 *
031 * This class also includes the machinery for maintaining a priority
032 * queue of forward references, priorities being target bytecode
033 * addresses. The head of this priority queue is maintained by a
034 * Assembler object.
035 *
036 * The priority queue is implemented as a one-way linked list of forward
037 * references with strictly increasing targets. The link for this list
038 * is "next". A separate linked list ("other" is the link) contains all
039 * forward references with the same target.
040 */
041 public abstract class ForwardReference {
042
043 final int sourceMachinecodeIndex;
044 final int targetBytecodeIndex; // optional
045
046 /* Support for priority queue of forward references */
047 /** Has next larger targetBytecodeIndex */
048 ForwardReference next;
049 /** Has the same targetBytecodeIndex */
050 ForwardReference other;
051
052 protected ForwardReference(int source, int btarget) {
053 sourceMachinecodeIndex = source;
054 targetBytecodeIndex = btarget;
055 }
056
057 /**
058 * No target; for use within cases of the main compiler loop
059 */
060 protected ForwardReference(int source) {
061 sourceMachinecodeIndex = source;
062 targetBytecodeIndex = 0;
063 }
064
065 /**
066 * Rewrite source to reference current machine code (in asm's machineCodes)
067 */
068 public abstract void resolve(AbstractAssembler asm);
069
070 /**
071 * Add a new reference r to a priority queue q
072 * @return the updated queue
073 */
074 public static ForwardReference enqueue(ForwardReference q, ForwardReference r) {
075 if (q == null) return r;
076 if (r.targetBytecodeIndex < q.targetBytecodeIndex) {
077 r.next = q;
078 return r;
079 } else if (r.targetBytecodeIndex == q.targetBytecodeIndex) {
080 r.other = q.other;
081 q.other = r;
082 return q;
083 }
084 ForwardReference s = q;
085 while (s.next != null && r.targetBytecodeIndex > s.next.targetBytecodeIndex) {
086 s = s.next;
087 }
088 s.next = enqueue(s.next, r);
089 return q;
090
091 }
092
093 /**
094 * Resolve any forward references on priority queue q to bytecode index bi
095 * @return queue of unresolved references
096 */
097 public static ForwardReference resolveMatching(AbstractAssembler asm, ForwardReference q, int bi) {
098 if (q == null) return null;
099 if (VM.VerifyAssertions) VM._assert(bi <= q.targetBytecodeIndex);
100 if (bi != q.targetBytecodeIndex) return q;
101 ForwardReference r = q.next;
102 while (q != null) {
103 q.resolve(asm);
104 q = q.other;
105 }
106 return r;
107 }
108
109 public static final class UnconditionalBranch extends ForwardReference {
110
111 public UnconditionalBranch(int source, int btarget) {
112 super(source, btarget);
113 }
114
115 public void resolve(AbstractAssembler asm) {
116 asm.patchUnconditionalBranch(sourceMachinecodeIndex);
117 }
118 }
119
120 public static final class ConditionalBranch extends ForwardReference {
121
122 public ConditionalBranch(int source, int btarget) {
123 super(source, btarget);
124 }
125
126 public void resolve(AbstractAssembler asm) {
127 asm.patchConditionalBranch(sourceMachinecodeIndex);
128 }
129 }
130
131 // Cannot be made final; subclassed for PPC
132 public static class ShortBranch extends ForwardReference {
133
134 public ShortBranch(int source) {
135 super(source);
136 }
137
138 public ShortBranch(int source, int btarget) {
139 super(source, btarget);
140 }
141
142 public void resolve(AbstractAssembler asm) {
143 asm.patchShortBranch(sourceMachinecodeIndex);
144 }
145 }
146
147 public static final class SwitchCase extends ForwardReference {
148
149 public SwitchCase(int source, int btarget) {
150 super(source, btarget);
151 }
152
153 public void resolve(AbstractAssembler asm) {
154 asm.patchSwitchCase(sourceMachinecodeIndex);
155 }
156 }
157
158 public static final class LoadReturnAddress extends ForwardReference {
159
160 public LoadReturnAddress(int source) {
161 super(source);
162 }
163
164 public LoadReturnAddress(int source, int btarget) {
165 super(source, btarget);
166 }
167
168 public void resolve(AbstractAssembler asm) {
169 asm.patchLoadReturnAddress(sourceMachinecodeIndex);
170 }
171 }
172 }