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.escape;
014
015 import java.util.HashSet;
016 import java.util.Set;
017 import org.jikesrvm.VM;
018 import org.jikesrvm.classloader.RVMArray;
019 import org.jikesrvm.classloader.RVMType;
020 import org.jikesrvm.classloader.TypeReference;
021 import org.jikesrvm.compilers.opt.ClassLoaderProxy;
022 import org.jikesrvm.compilers.opt.DefUse;
023 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
024 import org.jikesrvm.compilers.opt.ir.ALoad;
025 import org.jikesrvm.compilers.opt.ir.AStore;
026 import org.jikesrvm.compilers.opt.ir.BoundsCheck;
027 import org.jikesrvm.compilers.opt.ir.CondMove;
028 import org.jikesrvm.compilers.opt.ir.GuardedUnary;
029 import org.jikesrvm.compilers.opt.ir.InstanceOf;
030 import org.jikesrvm.compilers.opt.ir.Move;
031 import org.jikesrvm.compilers.opt.ir.NewArray;
032 import org.jikesrvm.compilers.opt.ir.NullCheck;
033 import org.jikesrvm.compilers.opt.ir.IR;
034 import org.jikesrvm.compilers.opt.ir.IRTools;
035 import org.jikesrvm.compilers.opt.ir.Instruction;
036 import org.jikesrvm.compilers.opt.ir.Operator;
037 import org.jikesrvm.compilers.opt.ir.Trap;
038 import org.jikesrvm.compilers.opt.ir.TrapIf;
039 import org.jikesrvm.compilers.opt.ir.TypeCheck;
040 import org.jikesrvm.compilers.opt.driver.OptConstants;
041 import static org.jikesrvm.compilers.opt.ir.IRTools.IC;
042 import static org.jikesrvm.compilers.opt.ir.Operators.BOUNDS_CHECK_opcode;
043 import static org.jikesrvm.compilers.opt.ir.Operators.BYTE_ALOAD_opcode;
044 import static org.jikesrvm.compilers.opt.ir.Operators.BYTE_ASTORE_opcode;
045 import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_NOTNULL_opcode;
046 import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_UNRESOLVED_opcode;
047 import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_opcode;
048 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_ALOAD_opcode;
049 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_ASTORE_opcode;
050 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_ALOAD_opcode;
051 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_ASTORE_opcode;
052 import static org.jikesrvm.compilers.opt.ir.Operators.GET_OBJ_TIB_opcode;
053 import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_MOVE;
054 import static org.jikesrvm.compilers.opt.ir.Operators.INSTANCEOF_NOTNULL_opcode;
055 import static org.jikesrvm.compilers.opt.ir.Operators.INSTANCEOF_UNRESOLVED_opcode;
056 import static org.jikesrvm.compilers.opt.ir.Operators.INSTANCEOF_opcode;
057 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ALOAD_opcode;
058 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ASTORE_opcode;
059 import static org.jikesrvm.compilers.opt.ir.Operators.INT_MOVE;
060 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_ALOAD_opcode;
061 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_ASTORE_opcode;
062 import static org.jikesrvm.compilers.opt.ir.Operators.NEWARRAY;
063 import static org.jikesrvm.compilers.opt.ir.Operators.NEWOBJMULTIARRAY_opcode;
064 import static org.jikesrvm.compilers.opt.ir.Operators.NULL_CHECK_opcode;
065 import static org.jikesrvm.compilers.opt.ir.Operators.OBJARRAY_STORE_CHECK_NOTNULL_opcode;
066 import static org.jikesrvm.compilers.opt.ir.Operators.OBJARRAY_STORE_CHECK_opcode;
067 import static org.jikesrvm.compilers.opt.ir.Operators.REF_ALOAD_opcode;
068 import static org.jikesrvm.compilers.opt.ir.Operators.REF_ASTORE_opcode;
069 import static org.jikesrvm.compilers.opt.ir.Operators.REF_IFCMP_opcode;
070 import static org.jikesrvm.compilers.opt.ir.Operators.REF_MOVE;
071 import static org.jikesrvm.compilers.opt.ir.Operators.REF_MOVE_opcode;
072 import static org.jikesrvm.compilers.opt.ir.Operators.SHORT_ALOAD_opcode;
073 import static org.jikesrvm.compilers.opt.ir.Operators.SHORT_ASTORE_opcode;
074 import static org.jikesrvm.compilers.opt.ir.Operators.TRAP;
075 import static org.jikesrvm.compilers.opt.ir.Operators.TRAP_IF;
076 import static org.jikesrvm.compilers.opt.ir.Operators.UBYTE_ALOAD_opcode;
077 import static org.jikesrvm.compilers.opt.ir.Operators.USHORT_ALOAD_opcode;
078 import org.jikesrvm.compilers.opt.ir.Register;
079 import org.jikesrvm.compilers.opt.ir.operand.ConditionOperand;
080 import org.jikesrvm.compilers.opt.ir.operand.Operand;
081 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
082 import org.jikesrvm.compilers.opt.ir.operand.TIBConstantOperand;
083 import org.jikesrvm.compilers.opt.ir.operand.TrapCodeOperand;
084 import org.jikesrvm.compilers.opt.ir.operand.TrueGuardOperand;
085
086 /**
087 * Class that performs scalar replacement of short arrays
088 */
089 final class ShortArrayReplacer implements AggregateReplacer {
090 /**
091 * number of elements in the array
092 */
093 private final int size;
094 /**
095 * type of the array
096 */
097 private final RVMArray vmArray;
098 /**
099 * the register holding the array reference
100 */
101 private final Register reg;
102 /**
103 * the governing IR
104 */
105 private final IR ir;
106
107 /**
108 * @param r the register holding the array reference
109 * @param a the type of the array to replace
110 * @param s the size of the array to replace
111 * @param i the IR
112 */
113 private ShortArrayReplacer(Register r, RVMArray a, int s, IR i) {
114 reg = r;
115 vmArray = a;
116 size = s;
117 ir = i;
118 }
119
120 /**
121 * Return an object representing this transformation for a given
122 * allocation site
123 *
124 * @param inst the allocation site
125 * @param ir
126 * @return the object, or null if illegal
127 */
128 public static ShortArrayReplacer getReplacer(Instruction inst, IR ir) {
129 if (inst.operator != NEWARRAY) {
130 return null;
131 }
132 Operand size = NewArray.getSize(inst);
133 if (!size.isIntConstant()) {
134 return null;
135 }
136 int s = size.asIntConstant().value;
137 if (s > ir.options.ESCAPE_MAX_ARRAY_SIZE) {
138 return null;
139 }
140 if (s < 0) {
141 return null;
142 }
143 Register r = NewArray.getResult(inst).getRegister();
144 RVMArray a = NewArray.getType(inst).getVMType().asArray();
145 // TODO :handle these cases
146 if (containsUnsupportedUse(ir, r, s, a, null)) {
147 return null;
148 }
149 return new ShortArrayReplacer(r, a, s, ir);
150 }
151
152 /**
153 * Perform the transformation.
154 */
155 public void transform() {
156 // first set up temporary scalars for the array elements
157 // initialize them before the def.
158 RegisterOperand[] scalars = new RegisterOperand[size];
159 TypeReference elementType = vmArray.getElementType().getTypeRef();
160 RegisterOperand def = reg.defList;
161 Instruction defI = def.instruction;
162 Operand defaultValue = IRTools.getDefaultOperand(elementType);
163 for (int i = 0; i < size; i++) {
164 scalars[i] = IRTools.moveIntoRegister(elementType, IRTools.getMoveOp(elementType), ir.regpool, defI, defaultValue.copy());
165 }
166 transform2(this.reg, defI, scalars);
167 }
168 private void transform2(Register reg, Instruction defI, RegisterOperand[] scalars) {
169 final boolean DEBUG = false;
170
171 // now remove the def
172 if (DEBUG) {
173 System.out.println("Removing " + defI);
174 }
175 DefUse.removeInstructionAndUpdateDU(defI);
176 // now handle the uses
177 for (RegisterOperand use = reg.useList; use != null; use = use.getNext()) {
178 scalarReplace(use, scalars, null);
179 }
180 }
181
182 /**
183 * Replace a given use of an array with its scalar equivalent.
184 *
185 * @param use the use to replace
186 * @param scalars an array of scalar register operands to replace
187 * the array with
188 */
189 private void scalarReplace(RegisterOperand use, RegisterOperand[] scalars, Set<Register> visited) {
190 Instruction inst = use.instruction;
191 RVMType type = vmArray.getElementType();
192 switch (inst.getOpcode()) {
193 case INT_ALOAD_opcode:
194 case LONG_ALOAD_opcode:
195 case FLOAT_ALOAD_opcode:
196 case DOUBLE_ALOAD_opcode:
197 case BYTE_ALOAD_opcode:
198 case UBYTE_ALOAD_opcode:
199 case USHORT_ALOAD_opcode:
200 case SHORT_ALOAD_opcode:
201 case REF_ALOAD_opcode: {
202 // Create use of scalar or eliminate unreachable instruction because
203 // of a trap
204 if (ALoad.getIndex(inst).isIntConstant()) {
205 Operator moveOp = IRTools.getMoveOp(type.getTypeRef());
206 int index = ALoad.getIndex(inst).asIntConstant().value;
207 if (index >= 0 && index < size) {
208 Instruction i2 = Move.create(moveOp, ALoad.getClearResult(inst), scalars[index].copyRO());
209 DefUse.replaceInstructionAndUpdateDU(inst, i2);
210 } else {
211 DefUse.removeInstructionAndUpdateDU(inst);
212 }
213 } else {
214 if (VM.BuildForIA32) {
215 if (size == 0) {
216 DefUse.removeInstructionAndUpdateDU(inst);
217 } else if (size == 1) {
218 int index = 0;
219 Operator moveOp = IRTools.getMoveOp(type.getTypeRef());
220 Instruction i2 = Move.create(moveOp, ALoad.getClearResult(inst), scalars[index].copyRO());
221 DefUse.replaceInstructionAndUpdateDU(inst, i2);
222 } else {
223 Operator moveOp = IRTools.getCondMoveOp(type.getTypeRef());
224 Instruction i2 = CondMove.create(moveOp, ALoad.getClearResult(inst),
225 ALoad.getIndex(inst), IC(0), ConditionOperand.EQUAL(),
226 scalars[0].copyRO(), scalars[1].copyRO());
227 DefUse.replaceInstructionAndUpdateDU(inst, i2);
228 }
229 } else {
230 if (size == 1) {
231 int index = 0;
232 Operator moveOp = IRTools.getMoveOp(type.getTypeRef());
233 Instruction i2 = Move.create(moveOp, ALoad.getClearResult(inst), scalars[index].copyRO());
234 DefUse.replaceInstructionAndUpdateDU(inst, i2);
235 } else {
236 DefUse.removeInstructionAndUpdateDU(inst);
237 }
238 }
239 }
240 }
241 break;
242 case INT_ASTORE_opcode:
243 case LONG_ASTORE_opcode:
244 case FLOAT_ASTORE_opcode:
245 case DOUBLE_ASTORE_opcode:
246 case BYTE_ASTORE_opcode:
247 case SHORT_ASTORE_opcode:
248 case REF_ASTORE_opcode: {
249 // Create move to scalar or eliminate unreachable instruction because
250 // of a trap
251 if (AStore.getIndex(inst).isIntConstant()) {
252 int index = AStore.getIndex(inst).asIntConstant().value;
253 if (index >= 0 && index < size) {
254 Operator moveOp = IRTools.getMoveOp(type.getTypeRef());
255 Instruction i2 = Move.create(moveOp, scalars[index].copyRO(), AStore.getClearValue(inst));
256 DefUse.replaceInstructionAndUpdateDU(inst, i2);
257 } else {
258 DefUse.removeInstructionAndUpdateDU(inst);
259 }
260 } else {
261 if (VM.BuildForIA32) {
262 if (size == 0) {
263 DefUse.removeInstructionAndUpdateDU(inst);
264 } else if (size == 1) {
265 int index = 0;
266 Operator moveOp = IRTools.getMoveOp(type.getTypeRef());
267 Instruction i2 = Move.create(moveOp, scalars[index].copyRO(), AStore.getClearValue(inst));
268 DefUse.replaceInstructionAndUpdateDU(inst, i2);
269 } else {
270 Operator moveOp = IRTools.getCondMoveOp(type.getTypeRef());
271 Operand value = AStore.getClearValue(inst);
272 Instruction i2 = CondMove.create(moveOp, scalars[0].copyRO(),
273 AStore.getIndex(inst), IC(0), ConditionOperand.EQUAL(),
274 value, scalars[0].copyRO());
275 DefUse.replaceInstructionAndUpdateDU(inst, i2);
276 Instruction i3 = CondMove.create(moveOp, scalars[1].copyRO(),
277 AStore.getIndex(inst), IC(0), ConditionOperand.NOT_EQUAL(),
278 value, scalars[1].copyRO());
279 i2.insertAfter(i3);
280 DefUse.updateDUForNewInstruction(i3);
281 }
282 } else {
283 if (size == 1) {
284 int index = 0;
285 Operator moveOp = IRTools.getMoveOp(type.getTypeRef());
286 Instruction i2 = Move.create(moveOp, scalars[index].copyRO(), AStore.getClearValue(inst));
287 DefUse.replaceInstructionAndUpdateDU(inst, i2);
288 } else {
289 DefUse.removeInstructionAndUpdateDU(inst);
290 }
291 }
292 }
293 }
294 break;
295 case NULL_CHECK_opcode: {
296 // Null check on result of new array must succeed
297 Instruction i2 = Move.create(GUARD_MOVE, NullCheck.getClearGuardResult(inst), new TrueGuardOperand());
298 DefUse.replaceInstructionAndUpdateDU(inst, i2);
299 }
300 break;
301 case BOUNDS_CHECK_opcode: {
302 // Remove or create trap as appropriate
303 Instruction i2 = TrapIf.create(TRAP_IF, BoundsCheck.getClearGuardResult(inst),
304 IC(size), BoundsCheck.getClearIndex(inst), ConditionOperand.LOWER_EQUAL(),
305 TrapCodeOperand.ArrayBounds());
306 DefUse.replaceInstructionAndUpdateDU(inst, i2);
307 }
308 break;
309 case CHECKCAST_opcode:
310 case CHECKCAST_NOTNULL_opcode:
311 case CHECKCAST_UNRESOLVED_opcode: {
312 // We cannot handle removing the checkcast if the result of the
313 // checkcast test is unknown
314 TypeReference lhsType = TypeCheck.getType(inst).getTypeRef();
315 if (ClassLoaderProxy.includesType(lhsType, vmArray.getTypeRef()) == OptConstants.YES) {
316 if (visited == null) {
317 visited = new HashSet<Register>();
318 }
319 Register copy = TypeCheck.getResult(inst).getRegister();
320 if(!visited.contains(copy)) {
321 visited.add(copy);
322 transform2(copy, inst, scalars);
323 // NB will remove inst
324 } else {
325 DefUse.removeInstructionAndUpdateDU(inst);
326 }
327 } else {
328 Instruction i2 = Trap.create(TRAP, null, TrapCodeOperand.CheckCast());
329 DefUse.replaceInstructionAndUpdateDU(inst, i2);
330 }
331 }
332 break;
333 case INSTANCEOF_opcode:
334 case INSTANCEOF_NOTNULL_opcode:
335 case INSTANCEOF_UNRESOLVED_opcode: {
336 // We cannot handle removing the instanceof if the result of the
337 // instanceof test is unknown
338 TypeReference lhsType = InstanceOf.getType(inst).getTypeRef();
339 Instruction i2;
340 if (ClassLoaderProxy.includesType(lhsType, vmArray.getTypeRef()) == OptConstants.YES) {
341 i2 = Move.create(INT_MOVE, InstanceOf.getClearResult(inst), IC(1));
342 } else {
343 i2 = Move.create(INT_MOVE, InstanceOf.getClearResult(inst), IC(0));
344 }
345 DefUse.replaceInstructionAndUpdateDU(inst, i2);
346 }
347 break;
348 case GET_OBJ_TIB_opcode: {
349 Instruction i2 = Move.create(REF_MOVE, GuardedUnary.getClearResult(inst), new TIBConstantOperand(vmArray));
350 DefUse.replaceInstructionAndUpdateDU(inst, i2);
351 }
352 break;
353 case REF_MOVE_opcode: {
354 if (visited == null) {
355 visited = new HashSet<Register>();
356 }
357 Register copy = Move.getResult(inst).getRegister();
358 if(!visited.contains(copy)) {
359 visited.add(copy);
360 transform2(copy, inst, scalars);
361 // NB will remove inst
362 } else {
363 DefUse.removeInstructionAndUpdateDU(inst);
364 }
365 }
366 break;
367 default:
368 throw new OptimizingCompilerException("Unexpected instruction: " + inst);
369 }
370 }
371
372 /**
373 * Some cases we don't handle yet. TODO: handle them.
374 *
375 * @param ir the governing IR
376 * @param reg the register in question
377 * @param size the size of the array to scalar replace.
378 */
379 private static boolean containsUnsupportedUse(IR ir, Register reg, int size, RVMArray vmArray, Set<Register> visited) {
380 // If an array is accessed by a non-constant integer, what's the maximum size of support array?
381 final int MAX_SIZE_FOR_VARIABLE_LOAD_STORE = VM.BuildForIA32 ? 2 : 1;
382 for (RegisterOperand use = reg.useList; use != null; use = use.getNext()) {
383 switch (use.instruction.getOpcode()) {
384 case REF_IFCMP_opcode:
385 // Comparison between the array reference we want to replace and
386 // another. TODO: this case is either always true or always false,
387 // we should optimize
388 case NEWOBJMULTIARRAY_opcode:
389 // dimensions array must be passed as an array argument to
390 // newobjmultiarray, common case of 2 arguments is handled without a
391 // dimensions array
392 case OBJARRAY_STORE_CHECK_opcode:
393 case OBJARRAY_STORE_CHECK_NOTNULL_opcode:
394 // TODO: create a store check that doesn't need an array argument
395 return true;
396 case CHECKCAST_opcode:
397 case CHECKCAST_NOTNULL_opcode:
398 case CHECKCAST_UNRESOLVED_opcode: {
399 // We cannot handle removing the checkcast if the result of the
400 // checkcast test is unknown
401 TypeReference lhsType = TypeCheck.getType(use.instruction).getTypeRef();
402 byte ans = ClassLoaderProxy.includesType(lhsType, vmArray.getTypeRef());
403 if (ans == OptConstants.MAYBE) {
404 return true;
405 } else if (ans == OptConstants.YES) {
406 // handle as a move
407 if (visited == null) {
408 visited = new HashSet<Register>();
409 }
410 Register copy = TypeCheck.getResult(use.instruction).getRegister();
411 if(!visited.contains(copy)) {
412 visited.add(copy);
413 if(containsUnsupportedUse(ir, copy, size, vmArray, visited)) {
414 return true;
415 }
416 }
417 }
418 }
419 break;
420 case INSTANCEOF_opcode:
421 case INSTANCEOF_NOTNULL_opcode:
422 case INSTANCEOF_UNRESOLVED_opcode: {
423 // We cannot handle removing the instanceof if the result of the
424 // instanceof test is unknown
425 TypeReference lhsType = InstanceOf.getType(use.instruction).getTypeRef();
426 if (ClassLoaderProxy.includesType(lhsType, vmArray.getTypeRef()) == OptConstants.MAYBE) {
427 return true;
428 }
429 }
430 break;
431 case INT_ASTORE_opcode:
432 case LONG_ASTORE_opcode:
433 case FLOAT_ASTORE_opcode:
434 case DOUBLE_ASTORE_opcode:
435 case BYTE_ASTORE_opcode:
436 case SHORT_ASTORE_opcode:
437 case REF_ASTORE_opcode:
438 // Don't handle registers as indexes
439 // TODO: support for registers if the size of the array is small (e.g. 1)
440 if (!AStore.getIndex(use.instruction).isIntConstant() && size > MAX_SIZE_FOR_VARIABLE_LOAD_STORE) {
441 return true;
442 }
443 break;
444 case INT_ALOAD_opcode:
445 case LONG_ALOAD_opcode:
446 case FLOAT_ALOAD_opcode:
447 case DOUBLE_ALOAD_opcode:
448 case BYTE_ALOAD_opcode:
449 case UBYTE_ALOAD_opcode:
450 case USHORT_ALOAD_opcode:
451 case SHORT_ALOAD_opcode:
452 case REF_ALOAD_opcode:
453 // Don't handle registers as indexes
454 // TODO: support for registers if the size of the array is small (e.g. 1)
455 if (!ALoad.getIndex(use.instruction).isIntConstant() && size > MAX_SIZE_FOR_VARIABLE_LOAD_STORE) {
456 return true;
457 }
458 break;
459 case REF_MOVE_opcode:
460 if (visited == null) {
461 visited = new HashSet<Register>();
462 }
463 Register copy = Move.getResult(use.instruction).getRegister();
464 if(!visited.contains(copy)) {
465 visited.add(copy);
466 if(containsUnsupportedUse(ir, copy, size, vmArray, visited)) {
467 return true;
468 }
469 }
470 break;
471 }
472 }
473 return false;
474 }
475 }