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.Enumeration;
017 import java.util.HashMap;
018 import java.util.HashSet;
019 import org.jikesrvm.ArchitectureSpecificOpt.PhysicalRegisterSet;
020 import org.jikesrvm.VM;
021 import org.jikesrvm.compilers.opt.ir.BasicBlock;
022 import org.jikesrvm.compilers.opt.ir.IR;
023 import org.jikesrvm.compilers.opt.ir.Instruction;
024 import static org.jikesrvm.compilers.opt.ir.Operators.CALL_SAVE_VOLATILE;
025 import static org.jikesrvm.compilers.opt.ir.Operators.YIELDPOINT_OSR;
026 import org.jikesrvm.compilers.opt.ir.Register;
027 import org.jikesrvm.compilers.opt.util.BitSet;
028
029 /**
030 * An instance of this class provides a mapping from symbolic register to
031 * a set of restricted registers.
032 * <p>
033 * Each architecture will subclass this in a class
034 * RegisterRestrictions.
035 */
036 public abstract class GenericRegisterRestrictions {
037 // for each symbolic register, the set of physical registers that are
038 // illegal for assignment
039 private final HashMap<Register, RestrictedRegisterSet> hash = new HashMap<Register, RestrictedRegisterSet>();
040
041 // a set of symbolic registers that must not be spilled.
042 private final HashSet<Register> noSpill = new HashSet<Register>();
043
044 protected final PhysicalRegisterSet phys;
045
046 /**
047 * Default Constructor
048 */
049 protected GenericRegisterRestrictions(PhysicalRegisterSet phys) {
050 this.phys = phys;
051 }
052
053 /**
054 * Record that the register allocator must not spill a symbolic
055 * register.
056 */
057 protected final void noteMustNotSpill(Register r) {
058 noSpill.add(r);
059 }
060
061 /**
062 * Is spilling a register forbidden?
063 */
064 public final boolean mustNotSpill(Register r) {
065 return noSpill.contains(r);
066 }
067
068 /**
069 * Record all the register restrictions dictated by an IR.
070 *
071 * PRECONDITION: the instructions in each basic block are numbered in
072 * increasing order before calling this. The number for each
073 * instruction is stored in its <code>scratch</code> field.
074 */
075 public final void init(IR ir) {
076 // process each basic block
077 for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
078 BasicBlock b = e.nextElement();
079 processBlock(b);
080 }
081 }
082
083 /**
084 * Record all the register restrictions dictated by live ranges on a
085 * particular basic block.<p>
086 *
087 * PRECONDITION: the instructions in each basic block are numbered in
088 * increasing order before calling this. The number for each
089 * instruction is stored in its <code>scratch</code> field.
090 */
091 private void processBlock(BasicBlock bb) {
092 ArrayList<LiveIntervalElement> symbolic = new ArrayList<LiveIntervalElement>(20);
093 ArrayList<LiveIntervalElement> physical = new ArrayList<LiveIntervalElement>(20);
094
095 // 1. walk through the live intervals and identify which correspond to
096 // physical and symbolic registers
097 for (Enumeration<LiveIntervalElement> e = bb.enumerateLiveIntervals(); e.hasMoreElements();) {
098 LiveIntervalElement li = e.nextElement();
099 Register r = li.getRegister();
100 if (r.isPhysical()) {
101 if (r.isVolatile() || r.isNonVolatile()) {
102 physical.add(li);
103 }
104 } else {
105 symbolic.add(li);
106 }
107 }
108
109 // 2. walk through the live intervals for physical registers. For
110 // each such interval, record the conflicts where the live range
111 // overlaps a live range for a symbolic register.
112 for (LiveIntervalElement phys : physical) {
113 for (LiveIntervalElement symb : symbolic) {
114 if (overlaps(phys, symb)) {
115 addRestriction(symb.getRegister(), phys.getRegister());
116 }
117 }
118 }
119
120 // 3. Volatile registers used by CALL instructions do not appear in
121 // the liveness information. Handle CALL instructions as a special
122 // case.
123 for (Enumeration<Instruction> ie = bb.forwardInstrEnumerator(); ie.hasMoreElements();) {
124 Instruction s = ie.nextElement();
125 if (s.operator.isCall() && s.operator != CALL_SAVE_VOLATILE) {
126 for (LiveIntervalElement symb : symbolic) {
127 if (contains(symb, s.scratch)) {
128 forbidAllVolatiles(symb.getRegister());
129 }
130 }
131 }
132
133 // Before OSR points, we need to save all FPRs,
134 // On OptExecStateExtractor, all GPRs have to be recovered,
135 // but not FPRS.
136 //
137 if (s.operator == YIELDPOINT_OSR) {
138 for (LiveIntervalElement symb : symbolic) {
139 if (symb.getRegister().isFloatingPoint()) {
140 if (contains(symb, s.scratch)) {
141 forbidAllVolatiles(symb.getRegister());
142 }
143 }
144 }
145 }
146 }
147
148 // 3. architecture-specific restrictions
149 addArchRestrictions(bb, symbolic);
150 }
151
152 /**
153 * Add architecture-specific register restrictions for a basic block.
154 * Override as needed.
155 *
156 * @param bb the basic block
157 * @param symbolics the live intervals for symbolic registers on this
158 * block
159 */
160 public void addArchRestrictions(BasicBlock bb, ArrayList<LiveIntervalElement> symbolics) {}
161
162 /**
163 * Does a live range R contain an instruction with number n?<p>
164 *
165 * PRECONDITION: the instructions in each basic block are numbered in
166 * increasing order before calling this. The number for each
167 * instruction is stored in its <code>scratch</code> field.
168 */
169 protected final boolean contains(LiveIntervalElement R, int n) {
170 int begin = -1;
171 int end = Integer.MAX_VALUE;
172 if (R.getBegin() != null) {
173 begin = R.getBegin().scratch;
174 }
175 if (R.getEnd() != null) {
176 end = R.getEnd().scratch;
177 }
178
179 return ((begin <= n) && (n <= end));
180 }
181
182 /**
183 * Do two live ranges overlap?<p>
184 *
185 * PRECONDITION: the instructions in each basic block are numbered in
186 * increasing order before calling this. The number for each
187 * instruction is stored in its <code>scratch</code> field.
188 */
189 private boolean overlaps(LiveIntervalElement li1, LiveIntervalElement li2) {
190 // Under the following conditions: the live ranges do NOT overlap:
191 // 1. begin2 >= end1 > -1
192 // 2. begin1 >= end2 > -1
193 // Under all other cases, the ranges overlap
194
195 int begin1 = -1;
196 int end1 = -1;
197 int begin2 = -1;
198 int end2 = -1;
199
200 if (li1.getBegin() != null) {
201 begin1 = li1.getBegin().scratch;
202 }
203 if (li2.getEnd() != null) {
204 end2 = li2.getEnd().scratch;
205 }
206 if (end2 <= begin1 && end2 > -1) return false;
207
208 if (li1.getEnd() != null) {
209 end1 = li1.getEnd().scratch;
210 }
211 if (li2.getBegin() != null) {
212 begin2 = li2.getBegin().scratch;
213 }
214 return end1 > begin2 || end1 <= -1;
215
216 }
217
218 /**
219 * Record that it is illegal to assign a symbolic register symb to any
220 * volatile physical registers
221 */
222 final void forbidAllVolatiles(Register symb) {
223 RestrictedRegisterSet r = hash.get(symb);
224 if (r == null) {
225 r = new RestrictedRegisterSet(phys);
226 hash.put(symb, r);
227 }
228 r.setNoVolatiles();
229 }
230
231 /**
232 * Record that it is illegal to assign a symbolic register symb to any
233 * of a set of physical registers
234 */
235 protected final void addRestrictions(Register symb, BitSet set) {
236 RestrictedRegisterSet r = hash.get(symb);
237 if (r == null) {
238 r = new RestrictedRegisterSet(phys);
239 hash.put(symb, r);
240 }
241 r.addAll(set);
242 }
243
244 /**
245 * Record that it is illegal to assign a symbolic register symb to a
246 * physical register p
247 */
248 protected final void addRestriction(Register symb, Register p) {
249 RestrictedRegisterSet r = hash.get(symb);
250 if (r == null) {
251 r = new RestrictedRegisterSet(phys);
252 hash.put(symb, r);
253 }
254 r.add(p);
255 }
256
257 /**
258 * Return the set of restricted physical register for a given symbolic
259 * register. Return {@code null} if no restrictions.
260 */
261 final RestrictedRegisterSet getRestrictions(Register symb) {
262 return hash.get(symb);
263 }
264
265 /**
266 * Is it forbidden to assign symbolic register symb to any volatile
267 * register?
268 * @return {@code true}: yes, all volatiles are forbidden.
269 * {@code false} :maybe, maybe not
270 */
271 public final boolean allVolatilesForbidden(Register symb) {
272 if (VM.VerifyAssertions) {
273 VM._assert(symb != null);
274 }
275 RestrictedRegisterSet s = getRestrictions(symb);
276 if (s == null) return false;
277 return s.getNoVolatiles();
278 }
279
280 /**
281 * Is it forbidden to assign symbolic register symb to physical register
282 * phys?
283 */
284 public final boolean isForbidden(Register symb, Register phys) {
285 if (VM.VerifyAssertions) {
286 VM._assert(symb != null);
287 VM._assert(phys != null);
288 }
289 RestrictedRegisterSet s = getRestrictions(symb);
290 if (s == null) return false;
291 return s.contains(phys);
292 }
293
294 /**
295 * Is it forbidden to assign symbolic register symb to physical register r
296 * in instruction s?
297 */
298 public abstract boolean isForbidden(Register symb, Register r, Instruction s);
299
300 /**
301 * An instance of this class represents restrictions on physical register
302 * assignment.
303 */
304 private static final class RestrictedRegisterSet {
305 /**
306 * The set of registers to which assignment is forbidden.
307 */
308 private final BitSet bitset;
309
310 /**
311 * additionally, are all volatile registers forbidden?
312 */
313 private boolean noVolatiles = false;
314
315 boolean getNoVolatiles() { return noVolatiles; }
316
317 void setNoVolatiles() { noVolatiles = true; }
318
319 /**
320 * Default constructor
321 */
322 RestrictedRegisterSet(PhysicalRegisterSet phys) {
323 bitset = new BitSet(phys);
324 }
325
326 /**
327 * Add a particular physical register to the set.
328 */
329 void add(Register r) {
330 bitset.add(r);
331 }
332
333 /**
334 * Add a set of physical registers to this set.
335 */
336 void addAll(BitSet set) {
337 bitset.addAll(set);
338 }
339
340 /**
341 * Does this set contain a particular register?
342 */
343 boolean contains(Register r) {
344 if (r.isVolatile() && noVolatiles) {
345 return true;
346 } else {
347 return bitset.contains(r);
348 }
349 }
350 }
351 }