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 * If a physical register is being used as a scratch register at
131 * instruction n, return true; else, return false;
132 */
133 boolean isScratch(Register r, int n) {
134 ArrayList<Interval> v = map.get(r);
135 if (v == null) return false;
136 for (final Interval interval : v) {
137 if (interval.contains(n)) return true;
138 }
139 return false;
140 }
141
142 /**
143 * If a symbolic register resides in a scratch register at an
144 * instruction numbered n, then return the scratch register. Else,
145 * return null.
146 */
147 Register getScratch(Register r, int n) {
148 ArrayList<Interval> v = map.get(r);
149 if (v == null) return null;
150 for (Interval i : v) {
151 if (i.contains(n)) return i.scratch;
152 }
153 return null;
154 }
155
156 /**
157 * Is this map empty?
158 */
159 public boolean isEmpty() {
160 return map.isEmpty();
161 }
162
163 /**
164 * Note that at GC point s, the real value of register symb is cached in
165 * a dirty scratch register.
166 */
167 public void markDirty(Instruction s, Register symb) {
168 HashSet<Register> set = dirtyMap.get(s);
169 if (set == null) {
170 set = new HashSet<Register>(3);
171 dirtyMap.put(s, set);
172 }
173 set.add(symb);
174 }
175
176 /**
177 * At GC point s, is the value of register r cached in a dirty scratch
178 * register?
179 */
180 public boolean isDirty(Instruction s, Register r) {
181 HashSet<Register> set = dirtyMap.get(s);
182 if (set == null) {
183 return false;
184 } else {
185 return set.contains(r);
186 }
187 }
188
189 /**
190 * Return a String representation.
191 */
192 public String toString() {
193 String result = "";
194 for (ArrayList<Interval> v : map.values()) {
195 for (Interval i : v) {
196 result += i + "\n";
197 }
198 }
199 return result;
200 }
201
202 /**
203 * Super class of physical and symbolic intervals
204 */
205 private abstract static class Interval {
206 /**
207 * The instruction before which the scratch range begins.
208 */
209 Instruction begin;
210 /**
211 * The instruction before which the scratch range ends.
212 */
213 Instruction end;
214 /**
215 * The physical scratch register or register evicted.
216 */
217 final Register scratch;
218
219 /**
220 * Initialize scratch register
221 */
222 Interval(Register scratch) {
223 this.scratch = scratch;
224 }
225
226 /**
227 * Does this interval contain the instruction numbered n?
228 */
229 final boolean contains(int n) {
230 return (begin.scratch <= n && end.scratch > n);
231 }
232 }
233
234 /**
235 * An object that represents an interval where a symbolic register
236 * resides in a scratch register.
237 * Note that this interval must not span a basic block.
238 */
239 static final class SymbolicInterval extends Interval {
240 /**
241 * The symbolic register
242 */
243 final Register symbolic;
244
245 SymbolicInterval(Register symbolic, Register scratch) {
246 super(scratch);
247 this.symbolic = symbolic;
248 }
249
250 /**
251 * Return a string representation, assuming the 'scratch' field of
252 * Instruction identifies an instruction.
253 */
254 public String toString() {
255 return "SI: " + symbolic + " " + scratch + " [" + begin.scratch + "," + end.scratch + "]";
256 }
257 }
258
259 /**
260 * An object that represents an interval where a physical register's
261 * contents are evicted so that the physical register can be used as a
262 * scratch. Note that this interval must not span a basic block.
263 */
264 static final class PhysicalInterval extends Interval {
265 PhysicalInterval(Register scratch) {
266 super(scratch);
267 }
268
269 /**
270 * Return a string representation, assuming the 'scratch' field of
271 * Instruction identifies an instruction.
272 */
273 public String toString() {
274 return "PI: " + scratch + " [" + begin.scratch + "," + end.scratch + "]";
275 }
276 }
277 }