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;
014
015 import static org.jikesrvm.compilers.opt.ir.Operators.PHI;
016
017 import java.util.Enumeration;
018
019 import org.jikesrvm.VM;
020 import org.jikesrvm.classloader.TypeReference;
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.Register;
025 import org.jikesrvm.compilers.opt.ir.operand.Operand;
026 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
027 import org.vmmagic.pragma.NoInline;
028
029 /**
030 * This class computes du-lists and associated information.
031 *
032 * <P> Note: DU operands are stored on the USE lists, but not the DEF
033 * lists.
034 */
035 public final class DefUse {
036 static final boolean DEBUG = false;
037 static final boolean TRACE_DU_ACTIONS = false;
038 static final boolean SUPRESS_DU_FOR_PHYSICALS = true;
039
040 /**
041 * Clear defList, useList for an IR.
042 *
043 * @param ir the IR in question
044 */
045 public static void clearDU(IR ir) {
046 for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = reg.getNext()) {
047 reg.defList = null;
048 reg.useList = null;
049 reg.scratch = -1;
050 reg.clearSeenUse();
051 }
052 for (Enumeration<Register> e = ir.regpool.getPhysicalRegisterSet().enumerateAll(); e.hasMoreElements();) {
053 Register reg = e.nextElement();
054 reg.defList = null;
055 reg.useList = null;
056 reg.scratch = -1;
057 reg.clearSeenUse();
058 }
059
060 if (TRACE_DU_ACTIONS || DEBUG) {
061 VM.sysWrite("Cleared DU\n");
062 }
063 }
064
065 /**
066 * Compute the register list and def-use lists for a method.
067 *
068 * @param ir the IR in question
069 */
070 @NoInline
071 public static void computeDU(IR ir) {
072 // Clear old register list (if any)
073 clearDU(ir);
074 // Create register defList and useList
075 for (Instruction instr = ir.firstInstructionInCodeOrder(); instr != null; instr =
076 instr.nextInstructionInCodeOrder()) {
077
078 Enumeration<Operand> defs = instr.getPureDefs();
079 Enumeration<Operand> uses = instr.getUses();
080
081 while (defs.hasMoreElements()) {
082 Operand op = defs.nextElement();
083 if (op instanceof RegisterOperand) {
084 RegisterOperand rop = (RegisterOperand) op;
085 recordDef(rop);
086 }
087 } // for ( defs = ... )
088
089 while (uses.hasMoreElements()) {
090 Operand op = uses.nextElement();
091 if (op instanceof RegisterOperand) {
092 RegisterOperand rop = (RegisterOperand) op;
093 recordUse(rop);
094 }
095 } // for ( uses = ... )
096 } // for ( instr = ... )
097 // Remove any symbloic registers with no uses/defs from
098 // the register pool. We'll waste analysis time keeping them around.
099 Register next;
100 for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = next) {
101 next = reg.getNext();
102 if (reg.defList == null && reg.useList == null) {
103 if (DEBUG) {
104 VM.sysWrite("Removing " + reg + " from the register pool\n");
105 }
106 ir.regpool.removeRegister(reg);
107 }
108 }
109 }
110
111 /**
112 * Record a use of a register
113 * @param regOp the operand that uses the register
114 */
115 public static void recordUse(RegisterOperand regOp) {
116 Register reg = regOp.getRegister();
117 regOp.append(reg.useList);
118 reg.useList = regOp;
119 reg.useCount++;
120 }
121
122 /**
123 * Record a def/use of a register
124 * TODO: For now we just pretend this is a use!!!!
125 *
126 * @param regOp the operand that uses the register
127 */
128 public static void recordDefUse(RegisterOperand regOp) {
129 Register reg = regOp.getRegister();
130 if (SUPRESS_DU_FOR_PHYSICALS && reg.isPhysical()) return;
131 regOp.append(reg.useList);
132 reg.useList = regOp;
133 }
134
135 /**
136 * Record a def of a register
137 * @param regOp the operand that uses the register
138 */
139 public static void recordDef(RegisterOperand regOp) {
140 Register reg = regOp.getRegister();
141 if (SUPRESS_DU_FOR_PHYSICALS && reg.isPhysical()) return;
142 regOp.append(reg.defList);
143 reg.defList = regOp;
144 }
145
146 /**
147 * Record that a use of a register no longer applies
148 * @param regOp the operand that uses the register
149 */
150 public static void removeUse(RegisterOperand regOp) {
151 Register reg = regOp.getRegister();
152 if (SUPRESS_DU_FOR_PHYSICALS && reg.isPhysical()) return;
153 if (regOp == reg.useList) {
154 reg.useList = reg.useList.getNext();
155 } else {
156 RegisterOperand prev = reg.useList;
157 RegisterOperand curr = prev.getNext();
158 while (curr != regOp) {
159 prev = curr;
160 curr = curr.getNext();
161 }
162 prev.setNext(curr.getNext());
163 }
164 reg.useCount--;
165 if (DEBUG) {
166 VM.sysWrite("removed a use " + regOp.instruction + "\n");
167 printUses(reg);
168 }
169 }
170
171 /**
172 * Record that a def of a register no longer applies
173 * @param regOp the operand that uses the register
174 */
175 public static void removeDef(RegisterOperand regOp) {
176 Register reg = regOp.getRegister();
177 if (SUPRESS_DU_FOR_PHYSICALS && reg.isPhysical()) return;
178 if (regOp == reg.defList) {
179 reg.defList = reg.defList.getNext();
180 } else {
181 RegisterOperand prev = reg.defList;
182 RegisterOperand curr = prev.getNext();
183 while (curr != regOp) {
184 prev = curr;
185 curr = curr.getNext();
186 }
187 prev.setNext(curr.getNext());
188 }
189 if (DEBUG) {
190 VM.sysWrite("removed a def " + regOp.instruction + "\n");
191 printDefs(reg);
192 }
193 }
194
195 /**
196 * This code changes the use in <code>origRegOp</code> to use
197 * the use in <code>newRegOp</code>.
198 *
199 * <p> If the type of <code>origRegOp</code> is not a reference, but the
200 * type of <code>newRegOp</code> is a reference, we need to update
201 * <code>origRegOp</code> to be a reference.
202 * Otherwise, the GC map code will be incorrect. -- Mike Hind
203 * @param origRegOp the register operand to change
204 * @param newRegOp the register operand to use for the change
205 */
206 public static void transferUse(RegisterOperand origRegOp, RegisterOperand newRegOp) {
207 if (VM.VerifyAssertions) {
208 VM._assert(origRegOp.getRegister().getType() == newRegOp.getRegister().getType());
209 }
210 Instruction inst = origRegOp.instruction;
211 if (DEBUG) {
212 VM.sysWrite("Transfering a use of " + origRegOp + " in " + inst + " to " + newRegOp + "\n");
213 }
214 removeUse(origRegOp);
215 // check to see if the regOp type is NOT a ref, but the newRegOp type
216 // is a reference. This can occur because of magic calls.
217 if (!origRegOp.getType().isReferenceType() && newRegOp.getType().isReferenceType()) {
218 // clone the newRegOp object and use it to replace the regOp object
219 RegisterOperand copiedRegOp = (RegisterOperand) newRegOp.copy();
220 inst.replaceOperand(origRegOp, copiedRegOp);
221 recordUse(copiedRegOp);
222 } else {
223 // just copy the register
224 origRegOp.setRegister(newRegOp.getRegister());
225 if (newRegOp.getType() != TypeReference.ObjectReference &&
226 !newRegOp.getType().isUnboxedType() && !origRegOp.isPreciseType()) {
227 // copy type information from new to orig unless its an unboxed type
228 // (we don't want to copy type information for unboxed types as it is
229 // likely the result of inlining new) or the type of the original is
230 // precise
231 origRegOp.copyType(newRegOp);
232 }
233 recordUse(origRegOp);
234 }
235 if (DEBUG) {
236 printUses(origRegOp.getRegister());
237 printUses(newRegOp.getRegister());
238 }
239 }
240
241 /**
242 * Remove an instruction and update register lists.
243 */
244 public static void removeInstructionAndUpdateDU(Instruction s) {
245 for (Enumeration<Operand> e = s.getPureDefs(); e.hasMoreElements();) {
246 Operand op = e.nextElement();
247 if (op instanceof RegisterOperand) {
248 removeDef((RegisterOperand) op);
249 }
250 }
251 for (Enumeration<Operand> e = s.getUses(); e.hasMoreElements();) {
252 Operand op = e.nextElement();
253 if (op instanceof RegisterOperand) {
254 removeUse((RegisterOperand) op);
255 }
256 }
257 s.remove();
258 }
259
260 /**
261 * Update register lists to account for the effect of a new
262 * instruction s
263 */
264 public static void updateDUForNewInstruction(Instruction s) {
265 for (Enumeration<Operand> e = s.getPureDefs(); e.hasMoreElements();) {
266 Operand op = e.nextElement();
267 if (op instanceof RegisterOperand) {
268 recordDef((RegisterOperand) op);
269 }
270 }
271 for (Enumeration<Operand> e = s.getUses(); e.hasMoreElements();) {
272 Operand op = e.nextElement();
273 if (op instanceof RegisterOperand) {
274 recordUse((RegisterOperand) op);
275 }
276 }
277 }
278
279 /**
280 * Replace an instruction and update register lists.
281 */
282 public static void replaceInstructionAndUpdateDU(Instruction oldI, Instruction newI) {
283 oldI.insertBefore(newI);
284 removeInstructionAndUpdateDU(oldI);
285 updateDUForNewInstruction(newI);
286 }
287
288 /**
289 * Enumerate all operands that use a given register.
290 */
291 public static Enumeration<RegisterOperand> uses(Register reg) {
292 return new RegOpListWalker(reg.useList);
293 }
294
295 /**
296 * Enumerate all operands that def a given register.
297 */
298 public static Enumeration<RegisterOperand> defs(Register reg) {
299 return new RegOpListWalker(reg.defList);
300 }
301
302 /**
303 * Does a given register have exactly one use?
304 */
305 static boolean exactlyOneUse(Register reg) {
306 return (reg.useList != null) && (reg.useList.getNext() == null);
307 }
308
309 /**
310 * Print all the instructions that def a register.
311 * @param reg
312 */
313 static void printDefs(Register reg) {
314 VM.sysWrite("Definitions of " + reg + '\n');
315 for (Enumeration<RegisterOperand> e = defs(reg); e.hasMoreElements();) {
316 VM.sysWrite("\t" + e.nextElement().instruction + "\n");
317 }
318 }
319
320 /**
321 * Print all the instructions that usea register.
322 * @param reg
323 */
324 static void printUses(Register reg) {
325 VM.sysWrite("Uses of " + reg + '\n');
326 for (Enumeration<RegisterOperand> e = uses(reg); e.hasMoreElements();) {
327 VM.sysWrite("\t" + e.nextElement().instruction + "\n");
328 }
329 }
330
331 /**
332 * Recompute <code> isSSA </code> for all registers by traversing register
333 * list.
334 * NOTE: the DU MUST be computed BEFORE calling this function
335 *
336 * @param ir the IR in question
337 */
338 public static void recomputeSSA(IR ir) {
339 // Use register /ist to enumerate register objects (FAST)
340 for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = reg.getNext()) {
341 // Set isSSA = true iff reg has exactly one static definition.
342 reg.putSSA((reg.defList != null && reg.defList.getNext() == null));
343 }
344 }
345
346 /**
347 * Merge register reg2 into register reg1.
348 * Remove reg2 from the DU information
349 */
350 public static void mergeRegisters(IR ir, Register reg1, Register reg2) {
351 RegisterOperand lastOperand;
352 if (reg1 == reg2) {
353 return;
354 }
355 if (DEBUG) {
356 VM.sysWrite("Merging " + reg2 + " into " + reg1 + "\n");
357 printDefs(reg2);
358 printUses(reg2);
359 printDefs(reg1);
360 printUses(reg1);
361 }
362 // first loop through defs of reg2 (currently, there will only be one def)
363 lastOperand = null;
364 for (RegisterOperand def = reg2.defList; def != null; lastOperand = def, def = def.getNext()) {
365 // Change def to refer to reg1 instead
366 def.setRegister(reg1);
367 // Track lastOperand
368 lastOperand = def;
369 }
370 if (lastOperand != null) {
371 // Set reg1.defList = concat(reg2.defList, reg1.deflist)
372 lastOperand.setNext(reg1.defList);
373 reg1.defList = reg2.defList;
374 }
375 // now loop through uses
376 lastOperand = null;
377 for (RegisterOperand use = reg2.useList; use != null; use = use.getNext()) {
378 // Change use to refer to reg1 instead
379 use.setRegister(reg1);
380 // Track lastOperand
381 lastOperand = use;
382 }
383 if (lastOperand != null) {
384 // Set reg1.useList = concat(reg2.useList, reg1.uselist)
385 lastOperand.setNext(reg1.useList);
386 reg1.useList = reg2.useList;
387 }
388 // Remove reg2 from RegisterPool
389 ir.regpool.removeRegister(reg2);
390 if (DEBUG) {
391 VM.sysWrite("Merge complete\n");
392 printDefs(reg1);
393 printUses(reg1);
394 }
395 }
396
397 /**
398 * Recompute spansBasicBlock flags for all registers.
399 *
400 * @param ir the IR in question
401 */
402 public static void recomputeSpansBasicBlock(IR ir) {
403 // clear fields
404 for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = reg.getNext()) {
405 reg.scratch = -1;
406 reg.clearSpansBasicBlock();
407 }
408 // iterate over the basic blocks
409 for (BasicBlock bb = ir.firstBasicBlockInCodeOrder(); bb != null; bb = bb.nextBasicBlockInCodeOrder()) {
410 int bbNum = bb.getNumber();
411 // enumerate the instructions in the basic block
412 for (Enumeration<Instruction> e = bb.forwardRealInstrEnumerator(); e.hasMoreElements();) {
413 Instruction inst = e.nextElement();
414 // check each Operand in the instruction
415 for (Enumeration<Operand> ops = inst.getOperands(); ops.hasMoreElements();) {
416 Operand op = ops.nextElement();
417 if (op instanceof RegisterOperand) {
418 Register reg = ((RegisterOperand) op).getRegister();
419 if (reg.isPhysical()) {
420 continue;
421 }
422 if (reg.spansBasicBlock()) {
423 continue;
424 }
425 if (seenInDifferentBlock(reg, bbNum)) {
426 reg.setSpansBasicBlock();
427 continue;
428 }
429 if (inst.operator() == PHI) {
430 reg.setSpansBasicBlock();
431 continue;
432 }
433 logAppearance(reg, bbNum);
434 }
435 }
436 }
437 }
438 }
439
440 /**
441 * Mark that we have seen a register in a particular
442 * basic block, and whether we saw a use
443 *
444 * @param reg the register
445 * @param bbNum the number of the basic block
446 */
447 private static void logAppearance(Register reg, int bbNum) {
448 reg.scratch = bbNum;
449 }
450
451 /**
452 * Have we seen this register in a different basic block?
453 *
454 * @param reg the register
455 * @param bbNum the number of the basic block
456 */
457 private static boolean seenInDifferentBlock(Register reg, int bbNum) {
458 int bb = reg.scratch;
459 return (bb != -1) && (bb != bbNum);
460 }
461
462 /**
463 * Utility class to encapsulate walking a use/def list.
464 */
465 private static final class RegOpListWalker implements Enumeration<RegisterOperand> {
466
467 private RegisterOperand current;
468
469 RegOpListWalker(RegisterOperand start) {
470 current = start;
471 }
472
473 @Override
474 public boolean hasMoreElements() {
475 return current != null;
476 }
477
478 @Override
479 public RegisterOperand nextElement() {
480 if (current == null) raiseNoSuchElementException();
481 RegisterOperand tmp = current;
482 current = current.getNext();
483 return tmp;
484 }
485
486 @NoInline
487 private static void raiseNoSuchElementException() {
488 throw new java.util.NoSuchElementException("RegOpListWalker");
489 }
490 }
491 }