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