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.opt.regalloc;
014
015 import java.util.ArrayList;
016 import java.util.HashMap;
017 import java.util.HashSet;
018 import org.jikesrvm.compilers.opt.ir.Instruction;
019 import org.jikesrvm.compilers.opt.ir.Register;
020
021 /**
022 * This class holds information on scratch register usage, needed to
023 * adjust GC Maps.
024 */
025 public final class ScratchMap {
026
027 private static final boolean DEBUG = false;
028
029 /**
030 * For each register, the set of intervals describing the register.
031 */
032 private final HashMap<Register, ArrayList<Interval>> map = new HashMap<Register, ArrayList<Interval>>();
033
034 /**
035 * For each register, a pending (incomplete) interval under
036 * construction.
037 */
038 private final HashMap<Register, Interval> pending = new HashMap<Register, Interval>();
039
040 /**
041 * For each GC Point s, a set of symbolic registers that are cached in
042 * dirty scratch registers before s.
043 */
044 private final HashMap<Instruction, HashSet<Register>> dirtyMap =
045 new HashMap<Instruction, HashSet<Register>>();
046
047 /**
048 * Begin a new interval of scratch-ness for a symbolic register.
049 *
050 * @param r the symbolic register being moved into scratch
051 * @param scratch the physical register being used as a scratch
052 * @param begin the instruction before which the physical register is
053 * vacated.
054 */
055 void beginSymbolicInterval(Register r, Register scratch, Instruction begin) {
056 if (DEBUG) {
057 System.out.println("beginSymbolicInterval " + r + " " + scratch + " " + begin.scratch);
058 }
059
060 SymbolicInterval i = new SymbolicInterval(r, scratch);
061 i.begin = begin;
062 ArrayList<Interval> v = findOrCreateIntervalSet(r);
063 v.add(i);
064 pending.put(r, i);
065 }
066
067 /**
068 * End an interval of scratch-ness for a symbolic register.
069 *
070 * @param r the symbolic register being moved into scratch
071 * @param end the instruction before which the scratch interval ends
072 */
073 public void endSymbolicInterval(Register r, Instruction end) {
074 if (DEBUG) {
075 System.out.println("endSymbolicInterval " + r + " " + end.scratch);
076 }
077
078 SymbolicInterval i = (SymbolicInterval) pending.get(r);
079 i.end = end;
080 pending.remove(i);
081 }
082
083 /**
084 * Begin a new interval of scratch-ness for a physical register.
085 *
086 * @param r the physical register being used as a scratch
087 * @param begin the instruction before which the physical register is
088 * vacated.
089 */
090 void beginScratchInterval(Register r, Instruction begin) {
091 if (DEBUG) {
092 System.out.println("beginScratchInterval " + r + " " + begin.scratch);
093 }
094 PhysicalInterval p = new PhysicalInterval(r);
095 p.begin = begin;
096 ArrayList<Interval> v = findOrCreateIntervalSet(r);
097 v.add(p);
098 pending.put(r, p);
099 }
100
101 /**
102 * End an interval of scratch-ness for a physical register.
103 *
104 * @param r the physical register being used as a scratch
105 * @param end the instruction before which the physical register is
106 * vacated.
107 */
108 public void endScratchInterval(Register r, Instruction end) {
109 if (DEBUG) {
110 System.out.println("endScratchInterval " + r + " " + end.scratch);
111 }
112 PhysicalInterval p = (PhysicalInterval) pending.get(r);
113 p.end = end;
114 pending.remove(r);
115 }
116
117 /**
118 * Find or create the set of intervals corresponding to a register r.
119 */
120 private ArrayList<Interval> findOrCreateIntervalSet(Register r) {
121 ArrayList<Interval> v = map.get(r);
122 if (v == null) {
123 v = new ArrayList<Interval>();
124 map.put(r, v);
125 }
126 return v;
127 }
128
129 /**
130 * Is the given physical register being used as a scratch register
131 * in the given instruction?
132 * @param r a physical register
133 * @param n the instruction's number
134 * @return {@code true} if the register is used as a scratch register
135 * in the instruction, {@code false} otherwise
136 */
137 boolean isScratch(Register r, int n) {
138 ArrayList<Interval> v = map.get(r);
139 if (v == null) return false;
140 for (final Interval interval : v) {
141 if (interval.contains(n)) return true;
142 }
143 return false;
144 }
145
146 /**
147 * If a symbolic register resides in a scratch register at an
148 * instruction numbered n, then return the scratch register. Else,
149 * return null.
150 */
151 Register getScratch(Register r, int n) {
152 ArrayList<Interval> v = map.get(r);
153 if (v == null) return null;
154 for (Interval i : v) {
155 if (i.contains(n)) return i.scratch;
156 }
157 return null;
158 }
159
160 /**
161 * Is this map empty?
162 */
163 public boolean isEmpty() {
164 return map.isEmpty();
165 }
166
167 /**
168 * Note that at GC point s, the real value of register symb is cached in
169 * a dirty scratch register.
170 */
171 public void markDirty(Instruction s, Register symb) {
172 HashSet<Register> set = dirtyMap.get(s);
173 if (set == null) {
174 set = new HashSet<Register>(3);
175 dirtyMap.put(s, set);
176 }
177 set.add(symb);
178 }
179
180 /**
181 * At GC point s, is the value of register r cached in a dirty scratch
182 * register?
183 */
184 public boolean isDirty(Instruction s, Register r) {
185 HashSet<Register> set = dirtyMap.get(s);
186 if (set == null) {
187 return false;
188 } else {
189 return set.contains(r);
190 }
191 }
192
193 /**
194 * Return a String representation.
195 */
196 @Override
197 public String toString() {
198 String result = "";
199 for (ArrayList<Interval> v : map.values()) {
200 for (Interval i : v) {
201 result += i + "\n";
202 }
203 }
204 return result;
205 }
206
207 /**
208 * Super class of physical and symbolic intervals
209 */
210 private abstract static class Interval {
211 /**
212 * The instruction before which the scratch range begins.
213 */
214 Instruction begin;
215 /**
216 * The instruction before which the scratch range ends.
217 */
218 Instruction end;
219 /**
220 * The physical scratch register or register evicted.
221 */
222 final Register scratch;
223
224 /**
225 * Initialize scratch register
226 */
227 Interval(Register scratch) {
228 this.scratch = scratch;
229 }
230
231 /**
232 * Does this interval contain the instruction numbered n?
233 */
234 final boolean contains(int n) {
235 return (begin.scratch <= n && end.scratch > n);
236 }
237 }
238
239 /**
240 * An object that represents an interval where a symbolic register
241 * resides in a scratch register.<p>
242 *
243 * Note that this interval must not span a basic block.
244 */
245 static final class SymbolicInterval extends Interval {
246 /**
247 * The symbolic register
248 */
249 final Register symbolic;
250
251 SymbolicInterval(Register symbolic, Register scratch) {
252 super(scratch);
253 this.symbolic = symbolic;
254 }
255
256 /**
257 * Return a string representation, assuming the 'scratch' field of
258 * Instruction identifies an instruction.
259 */
260 @Override
261 public String toString() {
262 return "SI: " + symbolic + " " + scratch + " [" + begin.scratch + "," + end.scratch + "]";
263 }
264 }
265
266 /**
267 * An object that represents an interval where a physical register's
268 * contents are evicted so that the physical register can be used as a
269 * scratch.<p>
270 *
271 * Note that this interval must not span a basic block.
272 */
273 static final class PhysicalInterval extends Interval {
274 PhysicalInterval(Register scratch) {
275 super(scratch);
276 }
277
278 /**
279 * Return a string representation, assuming the 'scratch' field of
280 * Instruction identifies an instruction.
281 */
282 @Override
283 public String toString() {
284 return "PI: " + scratch + " [" + begin.scratch + "," + end.scratch + "]";
285 }
286 }
287 }