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.ia32;
014
015 import java.util.ArrayList;
016 import java.util.Enumeration;
017 import org.jikesrvm.VM;
018 import org.jikesrvm.ArchitectureSpecificOpt.PhysicalRegisterSet;
019 import org.jikesrvm.compilers.opt.ir.MIR_BinaryAcc;
020 import org.jikesrvm.compilers.opt.ir.MIR_CacheOp;
021 import org.jikesrvm.compilers.opt.ir.MIR_Compare;
022 import org.jikesrvm.compilers.opt.ir.MIR_CondMove;
023 import org.jikesrvm.compilers.opt.ir.MIR_DoubleShift;
024 import org.jikesrvm.compilers.opt.ir.MIR_LowTableSwitch;
025 import org.jikesrvm.compilers.opt.ir.MIR_Move;
026 import org.jikesrvm.compilers.opt.ir.MIR_Set;
027 import org.jikesrvm.compilers.opt.ir.MIR_Test;
028 import org.jikesrvm.compilers.opt.ir.MIR_Unary;
029 import org.jikesrvm.compilers.opt.ir.MIR_UnaryNoRes;
030 import org.jikesrvm.compilers.opt.ir.BasicBlock;
031 import org.jikesrvm.compilers.opt.ir.Instruction;
032 import org.jikesrvm.compilers.opt.ir.InstructionEnumeration;
033 import org.jikesrvm.compilers.opt.ir.OperandEnumeration;
034 import org.jikesrvm.compilers.opt.ir.Operators;
035 import org.jikesrvm.compilers.opt.ir.Register;
036 import org.jikesrvm.compilers.opt.ir.operand.MemoryOperand;
037 import org.jikesrvm.compilers.opt.ir.operand.Operand;
038 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
039 import org.jikesrvm.compilers.opt.ir.operand.ia32.BURSManagedFPROperand;
040 import org.jikesrvm.compilers.opt.regalloc.GenericRegisterRestrictions;
041 import org.jikesrvm.compilers.opt.regalloc.LiveIntervalElement;
042
043 /**
044 * An instance of this class encapsulates restrictions on register
045 * assignment.
046 */
047 public class RegisterRestrictions extends GenericRegisterRestrictions
048 implements Operators, PhysicalRegisterConstants {
049
050 /**
051 * Allow scratch registers in PEIs?
052 */
053 public static final boolean SCRATCH_IN_PEI = true;
054
055 /**
056 * Default Constructor
057 */
058 protected RegisterRestrictions(PhysicalRegisterSet phys) {
059 super(phys);
060 }
061
062 /**
063 * Add architecture-specific register restrictions for a basic block.
064 * Override as needed.
065 *
066 * @param bb the basic block
067 * @param symbolics the live intervals for symbolic registers on this
068 * block
069 */
070 public void addArchRestrictions(BasicBlock bb, ArrayList<LiveIntervalElement> symbolics) {
071 // If there are any registers used in catch blocks, we want to ensure
072 // that these registers are not used or evicted from scratch registers
073 // at a relevant PEI, so that the assumptions of register homes in the
074 // catch block remain valid. For now, we do this by forcing any
075 // register used in such a PEI as not spilled. TODO: relax this
076 // restriction for better code.
077 for (InstructionEnumeration ie = bb.forwardInstrEnumerator(); ie.hasMoreElements();) {
078 Instruction s = ie.next();
079 if (s.isPEI() && s.operator != IR_PROLOGUE) {
080 if (bb.hasApplicableExceptionalOut(s) || !SCRATCH_IN_PEI) {
081 for (Enumeration<Operand> e = s.getOperands(); e.hasMoreElements();) {
082 Operand op = e.nextElement();
083 if (op != null && op.isRegister()) {
084 noteMustNotSpill(op.asRegister().getRegister());
085 handle8BitRestrictions(s);
086 }
087 }
088 }
089 }
090
091 // handle special cases
092 switch (s.getOpcode()) {
093 case MIR_LOWTABLESWITCH_opcode: {
094 RegisterOperand op = MIR_LowTableSwitch.getMethodStart(s);
095 noteMustNotSpill(op.getRegister());
096 op = MIR_LowTableSwitch.getIndex(s);
097 noteMustNotSpill(op.getRegister());
098 }
099 break;
100 case IA32_MOVZX__B_opcode:
101 case IA32_MOVSX__B_opcode: {
102 if (MIR_Unary.getVal(s).isRegister()) {
103 RegisterOperand val = MIR_Unary.getVal(s).asRegister();
104 restrictTo8Bits(val.getRegister());
105 }
106 }
107 break;
108 case IA32_SET__B_opcode: {
109 if (MIR_Set.getResult(s).isRegister()) {
110 RegisterOperand op = MIR_Set.getResult(s).asRegister();
111 restrictTo8Bits(op.getRegister());
112 }
113 }
114 break;
115
116 default:
117 handle8BitRestrictions(s);
118 break;
119 }
120 }
121 for (InstructionEnumeration ie = bb.forwardInstrEnumerator(); ie.hasMoreElements();) {
122 Instruction s = ie.next();
123 if (s.operator == IA32_FNINIT) {
124 // No floating point register survives across an FNINIT
125 for (LiveIntervalElement symb : symbolics) {
126 if (symb.getRegister().isFloatingPoint()) {
127 if (contains(symb, s.scratch)) {
128 addRestrictions(symb.getRegister(), phys.getFPRs());
129 }
130 }
131 }
132 } else if (s.operator == IA32_FCLEAR) {
133 // Only some FPRs survive across an FCLEAR
134 for (LiveIntervalElement symb : symbolics) {
135 if (symb.getRegister().isFloatingPoint()) {
136 if (contains(symb, s.scratch)) {
137 int nSave = MIR_UnaryNoRes.getVal(s).asIntConstant().value;
138 for (int i = nSave; i < NUM_FPRS; i++) {
139 addRestriction(symb.getRegister(), phys.getFPR(i));
140 }
141 }
142 }
143 }
144 }
145 }
146 }
147
148 /**
149 * Does instruction s contain an 8-bit memory operand?
150 */
151 final boolean has8BitMemoryOperand(Instruction s) {
152 for (OperandEnumeration me = s.getMemoryOperands(); me.hasMoreElements();) {
153 MemoryOperand mop = (MemoryOperand) me.next();
154 if (mop.size == 1) {
155 return true;
156 }
157 }
158 return false;
159 }
160
161 /**
162 * Ensure that if an operand has an 8 bit memory operand that
163 * all of its register operands are in 8 bit registers.
164 * @param s the instruction to restrict
165 */
166 final void handle8BitRestrictions(Instruction s) {
167 for (OperandEnumeration me = s.getMemoryOperands(); me.hasMoreElements();) {
168 MemoryOperand mop = (MemoryOperand) me.next();
169 if (mop.size == 1) {
170 for (OperandEnumeration e2 = s.getRootOperands(); e2.hasMoreElements();) {
171 Operand rootOp = e2.next();
172 if (rootOp.isRegister()) {
173 restrictTo8Bits(rootOp.asRegister().getRegister());
174 }
175 }
176 }
177 }
178 }
179
180 /**
181 * Ensure that a particular register is only assigned to AL, BL, CL, or
182 * DL, since these are the only 8-bit registers we normally address.
183 */
184 final void restrictTo8Bits(Register r) {
185 Register ESP = phys.getESP();
186 Register EBP = phys.getEBP();
187 Register ESI = phys.getESI();
188 Register EDI = phys.getEDI();
189 addRestriction(r, ESP);
190 addRestriction(r, EBP);
191 addRestriction(r, ESI);
192 addRestriction(r, EDI);
193 }
194
195 /**
196 * Given symbolic register r that appears in instruction s, does the
197 * architecture demand that r be assigned to a physical register in s?
198 */
199 public static boolean mustBeInRegister(Register r, Instruction s) {
200 switch (s.getOpcode()) {
201 case IA32_PREFETCHNTA_opcode: {
202 RegisterOperand op = MIR_CacheOp.getAddress(s).asRegister();
203 if (op.register == r) return true;
204 }
205 break;
206
207 case IA32_SQRTSS_opcode:
208 case IA32_SQRTSD_opcode:
209 case IA32_CVTSD2SI_opcode:
210 case IA32_CVTSD2SS_opcode:
211 case IA32_CVTSI2SD_opcode:
212 case IA32_CVTSS2SD_opcode:
213 case IA32_CVTSS2SI_opcode:
214 case IA32_CVTTSD2SI_opcode:
215 case IA32_CVTTSS2SI_opcode:
216 case IA32_CVTSI2SS_opcode: {
217 RegisterOperand op = MIR_Unary.getResult(s).asRegister();
218 if (op.getRegister() == r) return true;
219 }
220 break;
221
222 // Instructions that require 16byte alignment (not guaranteed by our
223 // spills) must be forced to always use registers
224 case IA32_ANDPS_opcode:
225 case IA32_ANDNPS_opcode:
226 case IA32_ORPS_opcode:
227 case IA32_XORPS_opcode:
228 case IA32_ANDPD_opcode:
229 case IA32_ANDNPD_opcode:
230 case IA32_ORPD_opcode:
231 case IA32_XORPD_opcode:
232 return true;
233
234 case IA32_ADDSS_opcode:
235 case IA32_CMPEQSS_opcode:
236 case IA32_CMPLTSS_opcode:
237 case IA32_CMPLESS_opcode:
238 case IA32_CMPUNORDSS_opcode:
239 case IA32_CMPNESS_opcode:
240 case IA32_CMPNLTSS_opcode:
241 case IA32_CMPNLESS_opcode:
242 case IA32_CMPORDSS_opcode:
243 case IA32_DIVSS_opcode:
244 case IA32_MULSS_opcode:
245 case IA32_SUBSS_opcode:
246 case IA32_ADDSD_opcode:
247 case IA32_CMPEQSD_opcode:
248 case IA32_CMPLTSD_opcode:
249 case IA32_CMPLESD_opcode:
250 case IA32_CMPUNORDSD_opcode:
251 case IA32_CMPNESD_opcode:
252 case IA32_CMPNLTSD_opcode:
253 case IA32_CMPNLESD_opcode:
254 case IA32_CMPORDSD_opcode:
255 case IA32_DIVSD_opcode:
256 case IA32_MULSD_opcode:
257 case IA32_SUBSD_opcode: {
258 RegisterOperand op = MIR_BinaryAcc.getResult(s).asRegister();
259 if (op.getRegister() == r) return true;
260 }
261 break;
262
263 case IA32_UCOMISD_opcode:
264 case IA32_UCOMISS_opcode: {
265 RegisterOperand op = MIR_Compare.getVal1(s).asRegister();
266 if (op.getRegister() == r) return true;
267 }
268 break;
269
270 case IA32_SHRD_opcode:
271 case IA32_SHLD_opcode: {
272 RegisterOperand op = MIR_DoubleShift.getSource(s);
273 if (op.getRegister() == r) return true;
274 }
275 break;
276 case IA32_FCOMI_opcode:
277 case IA32_FCOMIP_opcode: {
278 Operand op = MIR_Compare.getVal2(s);
279 if (!(op instanceof BURSManagedFPROperand)) {
280 if (op.asRegister().getRegister() == r) return true;
281 }
282 }
283 break;
284 case IA32_IMUL2_opcode: {
285 RegisterOperand op = MIR_BinaryAcc.getResult(s).asRegister();
286 if (op.getRegister() == r) return true;
287 }
288 break;
289 case MIR_LOWTABLESWITCH_opcode: {
290 RegisterOperand op = MIR_LowTableSwitch.getIndex(s);
291 if (op.getRegister() == r) return true;
292 }
293 break;
294 case IA32_CMOV_opcode:
295 case IA32_FCMOV_opcode: {
296 RegisterOperand op = MIR_CondMove.getResult(s).asRegister();
297 if (op.getRegister() == r) return true;
298 }
299 break;
300 case IA32_MOVD_opcode: {
301 RegisterOperand res = MIR_Move.getResult(s).asRegister();
302 if (!res.isFloat() && !res.isDouble()) {
303 // result is integer so source must be MM/XMM register and
304 // result must remain a register
305 if (VM.VerifyAssertions) {
306 Operand val = MIR_Move.getValue(s);
307 VM._assert(val.isRegister() && (val.isFloat() || val.isDouble()));
308 }
309 return true;
310 }
311 Operand val = MIR_Move.getValue(s);
312 if (!val.isFloat() && !val.isDouble()) {
313 // source is integer so destination must be MM/XMM register and
314 // source must remain a register
315 if (VM.VerifyAssertions) {
316 VM._assert(res.isRegister() && (res.isFloat() || res.isDouble()));
317 }
318 return true;
319 }
320 }
321 break;
322 case IA32_MOVZX__B_opcode:
323 case IA32_MOVSX__B_opcode: {
324 RegisterOperand op = MIR_Unary.getResult(s).asRegister();
325 if (op.getRegister() == r) return true;
326 }
327 break;
328 case IA32_MOVZX__W_opcode:
329 case IA32_MOVSX__W_opcode: {
330 RegisterOperand op = MIR_Unary.getResult(s).asRegister();
331 if (op.getRegister() == r) return true;
332 }
333 break;
334 case IA32_SET__B_opcode: {
335 if (MIR_Set.getResult(s).isRegister()) {
336 RegisterOperand op = MIR_Set.getResult(s).asRegister();
337 if (op.asRegister().getRegister() == r) return true;
338 }
339 }
340 break;
341 case IA32_TEST_opcode: {
342 // at least 1 of the two operands must be in a register
343 if (!MIR_Test.getVal2(s).isConstant()) {
344 if (MIR_Test.getVal1(s).isRegister()) {
345 if (MIR_Test.getVal1(s).asRegister().getRegister() == r) return true;
346 } else if (MIR_Test.getVal2(s).isRegister()) {
347 if (MIR_Test.getVal2(s).asRegister().getRegister() == r) return true;
348 }
349 }
350 }
351 break;
352 case IA32_BT_opcode: {
353 // val2 of bit test must be either a constant or register
354 if (!MIR_Test.getVal2(s).isConstant()) {
355 if (MIR_Test.getVal2(s).isRegister()) {
356 if (MIR_Test.getVal2(s).asRegister().getRegister() == r) return true;
357 }
358 }
359 }
360 break;
361
362 default:
363 break;
364 }
365 return false;
366 }
367
368 /**
369 * Can physical register r hold an 8-bit value?
370 */
371 private boolean okFor8(Register r) {
372 Register ESP = phys.getESP();
373 Register EBP = phys.getEBP();
374 Register ESI = phys.getESI();
375 Register EDI = phys.getEDI();
376 return (r != ESP && r != EBP && r != ESI && r != EDI);
377 }
378
379 /**
380 * Is it forbidden to assign symbolic register symb to physical register r
381 * in instruction s?
382 */
383 public boolean isForbidden(Register symb, Register r, Instruction s) {
384
385 // Look at 8-bit restrictions.
386 switch (s.operator.opcode) {
387 case IA32_MOVZX__B_opcode:
388 case IA32_MOVSX__B_opcode: {
389 if (MIR_Unary.getVal(s).isRegister()) {
390 RegisterOperand val = MIR_Unary.getVal(s).asRegister();
391 if (val.getRegister() == symb) {
392 return !okFor8(r);
393 }
394 }
395 }
396 break;
397 case IA32_SET__B_opcode: {
398 if (MIR_Set.getResult(s).isRegister()) {
399 RegisterOperand op = MIR_Set.getResult(s).asRegister();
400 if (op.asRegister().getRegister() == symb) {
401 return !okFor8(r);
402 }
403 }
404 }
405 break;
406 }
407
408 if (has8BitMemoryOperand(s)) {
409 return !okFor8(r);
410 }
411
412 // Otherwise, it's OK.
413 return false;
414 }
415 }