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 * <p>
025 * There are three kinds of forward reference:
026 * <ol>
027 * <li>unconditional branches
028 * <li>conditional branches
029 * <li>switch cases
030 * </ol>
031 * Each subclass must be able to resolve itself.
032 * <p>
033 * This class also includes the machinery for maintaining a priority
034 * queue of forward references, priorities being target bytecode
035 * addresses. The head of this priority queue is maintained by a
036 * Assembler object.
037 * <p>
038 * The priority queue is implemented as a one-way linked list of forward
039 * references with strictly increasing targets. The link for this list
040 * is "next". A separate linked list ("other" is the link) contains all
041 * forward references with the same target.
042 */
043 public abstract class ForwardReference {
044
045 final int sourceMachinecodeIndex;
046 final int targetBytecodeIndex; // optional
047
048 /* Support for priority queue of forward references */
049
050 /** Has next larger targetBytecodeIndex */
051 ForwardReference next;
052 /** Has the same targetBytecodeIndex */
053 ForwardReference other;
054
055 protected ForwardReference(int source, int btarget) {
056 sourceMachinecodeIndex = source;
057 targetBytecodeIndex = btarget;
058 }
059
060 /**
061 * No target; for use within cases of the main compiler loop
062 */
063 protected ForwardReference(int source) {
064 sourceMachinecodeIndex = source;
065 targetBytecodeIndex = 0;
066 }
067
068 /**
069 * Rewrite source to reference current machine code (in asm's machineCodes)
070 */
071 public abstract void resolve(AbstractAssembler asm);
072
073 /**
074 * Add a new reference r to a priority queue q
075 * @return the updated queue
076 */
077 public static ForwardReference enqueue(ForwardReference q, ForwardReference r) {
078 if (q == null) return r;
079 if (r.targetBytecodeIndex < q.targetBytecodeIndex) {
080 r.next = q;
081 return r;
082 } else if (r.targetBytecodeIndex == q.targetBytecodeIndex) {
083 r.other = q.other;
084 q.other = r;
085 return q;
086 }
087 ForwardReference s = q;
088 while (s.next != null && r.targetBytecodeIndex > s.next.targetBytecodeIndex) {
089 s = s.next;
090 }
091 s.next = enqueue(s.next, r);
092 return q;
093
094 }
095
096 /**
097 * Resolve any forward references on priority queue q to bytecode index bi
098 * @return queue of unresolved references
099 */
100 public static ForwardReference resolveMatching(AbstractAssembler asm, ForwardReference q, int bi) {
101 if (q == null) return null;
102 if (VM.VerifyAssertions) VM._assert(bi <= q.targetBytecodeIndex);
103 if (bi != q.targetBytecodeIndex) return q;
104 ForwardReference r = q.next;
105 while (q != null) {
106 q.resolve(asm);
107 q = q.other;
108 }
109 return r;
110 }
111
112 public static final class UnconditionalBranch extends ForwardReference {
113
114 public UnconditionalBranch(int source, int btarget) {
115 super(source, btarget);
116 }
117
118 @Override
119 public void resolve(AbstractAssembler asm) {
120 asm.patchUnconditionalBranch(sourceMachinecodeIndex);
121 }
122 }
123
124 public static final class ConditionalBranch extends ForwardReference {
125
126 public ConditionalBranch(int source, int btarget) {
127 super(source, btarget);
128 }
129
130 @Override
131 public void resolve(AbstractAssembler asm) {
132 asm.patchConditionalBranch(sourceMachinecodeIndex);
133 }
134 }
135
136 // Cannot be made final; subclassed for PPC
137 public static class ShortBranch extends ForwardReference {
138
139 public ShortBranch(int source) {
140 super(source);
141 }
142
143 public ShortBranch(int source, int btarget) {
144 super(source, btarget);
145 }
146
147 @Override
148 public void resolve(AbstractAssembler asm) {
149 asm.patchShortBranch(sourceMachinecodeIndex);
150 }
151 }
152
153 public static final class SwitchCase extends ForwardReference {
154
155 public SwitchCase(int source, int btarget) {
156 super(source, btarget);
157 }
158
159 @Override
160 public void resolve(AbstractAssembler asm) {
161 asm.patchSwitchCase(sourceMachinecodeIndex);
162 }
163 }
164
165 public static final class LoadReturnAddress extends ForwardReference {
166
167 public LoadReturnAddress(int source) {
168 super(source);
169 }
170
171 public LoadReturnAddress(int source, int btarget) {
172 super(source, btarget);
173 }
174
175 @Override
176 public void resolve(AbstractAssembler asm) {
177 asm.patchLoadReturnAddress(sourceMachinecodeIndex);
178 }
179 }
180 }