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 */
013package org.jikesrvm.compilers.common.assembler;
014
015import 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 */
043public 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  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   * @param asm the assembler to use to resolve the reference
069   */
070  public abstract void resolve(AbstractAssembler asm);
071
072  /**
073   * Adds a new reference to a priority queue.
074   * @param q a forward reference acting as a priority queue
075   * @param r a new reference to enqueue
076   * @return the updated queue
077   */
078  public static ForwardReference enqueue(ForwardReference q, ForwardReference r) {
079    if (q == null) return r;
080    if (r.targetBytecodeIndex < q.targetBytecodeIndex) {
081      r.next = q;
082      return r;
083    } else if (r.targetBytecodeIndex == q.targetBytecodeIndex) {
084      r.other = q.other;
085      q.other = r;
086      return q;
087    }
088    ForwardReference s = q;
089    while (s.next != null && r.targetBytecodeIndex > s.next.targetBytecodeIndex) {
090      s = s.next;
091    }
092    s.next = enqueue(s.next, r);
093    return q;
094
095  }
096
097  /**
098   * Resolve any forward references on the priority queue for the given
099   * bytecode index.
100   *
101   * @param asm assembler to use for resolution
102   * @param q priority queue
103   * @param bi bytecode index
104   * @return queue of unresolved references
105   */
106  public static ForwardReference resolveMatching(AbstractAssembler asm, ForwardReference q, int bi) {
107    if (q == null) return null;
108    if (VM.VerifyAssertions) VM._assert(bi <= q.targetBytecodeIndex);
109    if (bi != q.targetBytecodeIndex) return q;
110    ForwardReference r = q.next;
111    while (q != null) {
112      q.resolve(asm);
113      q = q.other;
114    }
115    return r;
116  }
117
118  public static final class UnconditionalBranch extends ForwardReference {
119
120    public UnconditionalBranch(int source, int btarget) {
121      super(source, btarget);
122    }
123
124    @Override
125    public void resolve(AbstractAssembler asm) {
126      asm.patchUnconditionalBranch(sourceMachinecodeIndex);
127    }
128  }
129
130  public static final class ConditionalBranch extends ForwardReference {
131
132    public ConditionalBranch(int source, int btarget) {
133      super(source, btarget);
134    }
135
136    @Override
137    public void resolve(AbstractAssembler asm) {
138      asm.patchConditionalBranch(sourceMachinecodeIndex);
139    }
140  }
141
142  // Cannot be made final; subclassed for PPC
143  public static class ShortBranch extends ForwardReference {
144
145    public ShortBranch(int source) {
146      super(source);
147    }
148
149    public ShortBranch(int source, int btarget) {
150      super(source, btarget);
151    }
152
153    @Override
154    public void resolve(AbstractAssembler asm) {
155      asm.patchShortBranch(sourceMachinecodeIndex);
156    }
157  }
158
159  public static final class SwitchCase extends ForwardReference {
160
161    public SwitchCase(int source, int btarget) {
162      super(source, btarget);
163    }
164
165    @Override
166    public void resolve(AbstractAssembler asm) {
167      asm.patchSwitchCase(sourceMachinecodeIndex);
168    }
169  }
170
171  public static final class LoadReturnAddress extends ForwardReference {
172
173    public LoadReturnAddress(int source) {
174      super(source);
175    }
176
177    public LoadReturnAddress(int source, int btarget) {
178      super(source, btarget);
179    }
180
181    @Override
182    public void resolve(AbstractAssembler asm) {
183      asm.patchLoadReturnAddress(sourceMachinecodeIndex);
184    }
185  }
186}