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 @Override
153 public void transform() {
154 // first set up temporary scalars for the array elements
155 // initialize them before the def.
156 RegisterOperand[] scalars = new RegisterOperand[size];
157 TypeReference elementType = vmArray.getElementType().getTypeRef();
158 RegisterOperand def = reg.defList;
159 Instruction defI = def.instruction;
160 Operand defaultValue = IRTools.getDefaultOperand(elementType);
161 for (int i = 0; i < size; i++) {
162 scalars[i] = IRTools.moveIntoRegister(elementType, IRTools.getMoveOp(elementType), ir.regpool, defI, defaultValue.copy());
163 }
164 transform2(this.reg, defI, scalars);
165 }
166 private void transform2(Register reg, Instruction defI, RegisterOperand[] scalars) {
167 final boolean DEBUG = false;
168
169 // now remove the def
170 if (DEBUG) {
171 System.out.println("Removing " + defI);
172 }
173 DefUse.removeInstructionAndUpdateDU(defI);
174 // now handle the uses
175 for (RegisterOperand use = reg.useList; use != null; use = use.getNext()) {
176 scalarReplace(use, scalars, null);
177 }
178 }
179
180 /**
181 * Replace a given use of an array with its scalar equivalent.
182 *
183 * @param use the use to replace
184 * @param scalars an array of scalar register operands to replace
185 * the array with
186 */
187 private void scalarReplace(RegisterOperand use, RegisterOperand[] scalars, Set<Register> visited) {
188 Instruction inst = use.instruction;
189 RVMType type = vmArray.getElementType();
190 switch (inst.getOpcode()) {
191 case INT_ALOAD_opcode:
192 case LONG_ALOAD_opcode:
193 case FLOAT_ALOAD_opcode:
194 case DOUBLE_ALOAD_opcode:
195 case BYTE_ALOAD_opcode:
196 case UBYTE_ALOAD_opcode:
197 case USHORT_ALOAD_opcode:
198 case SHORT_ALOAD_opcode:
199 case REF_ALOAD_opcode: {
200 // Create use of scalar or eliminate unreachable instruction because
201 // of a trap
202 if (ALoad.getIndex(inst).isIntConstant()) {
203 Operator moveOp = IRTools.getMoveOp(type.getTypeRef());
204 int index = ALoad.getIndex(inst).asIntConstant().value;
205 if (index >= 0 && index < size) {
206 Instruction i2 = Move.create(moveOp, ALoad.getClearResult(inst), scalars[index].copyRO());
207 DefUse.replaceInstructionAndUpdateDU(inst, i2);
208 } else {
209 DefUse.removeInstructionAndUpdateDU(inst);
210 }
211 } else {
212 if (VM.BuildForIA32) {
213 if (size == 0) {
214 DefUse.removeInstructionAndUpdateDU(inst);
215 } else if (size == 1) {
216 int index = 0;
217 Operator moveOp = IRTools.getMoveOp(type.getTypeRef());
218 Instruction i2 = Move.create(moveOp, ALoad.getClearResult(inst), scalars[index].copyRO());
219 DefUse.replaceInstructionAndUpdateDU(inst, i2);
220 } else {
221 Operator moveOp = IRTools.getCondMoveOp(type.getTypeRef());
222 Instruction i2 = CondMove.create(moveOp, ALoad.getClearResult(inst),
223 ALoad.getIndex(inst), IC(0), ConditionOperand.EQUAL(),
224 scalars[0].copyRO(), scalars[1].copyRO());
225 DefUse.replaceInstructionAndUpdateDU(inst, i2);
226 }
227 } else {
228 if (size == 1) {
229 int index = 0;
230 Operator moveOp = IRTools.getMoveOp(type.getTypeRef());
231 Instruction i2 = Move.create(moveOp, ALoad.getClearResult(inst), scalars[index].copyRO());
232 DefUse.replaceInstructionAndUpdateDU(inst, i2);
233 } else {
234 DefUse.removeInstructionAndUpdateDU(inst);
235 }
236 }
237 }
238 }
239 break;
240 case INT_ASTORE_opcode:
241 case LONG_ASTORE_opcode:
242 case FLOAT_ASTORE_opcode:
243 case DOUBLE_ASTORE_opcode:
244 case BYTE_ASTORE_opcode:
245 case SHORT_ASTORE_opcode:
246 case REF_ASTORE_opcode: {
247 // Create move to scalar or eliminate unreachable instruction because
248 // of a trap
249 if (AStore.getIndex(inst).isIntConstant()) {
250 int index = AStore.getIndex(inst).asIntConstant().value;
251 if (index >= 0 && index < size) {
252 Operator moveOp = IRTools.getMoveOp(type.getTypeRef());
253 Instruction i2 = Move.create(moveOp, scalars[index].copyRO(), AStore.getClearValue(inst));
254 DefUse.replaceInstructionAndUpdateDU(inst, i2);
255 } else {
256 DefUse.removeInstructionAndUpdateDU(inst);
257 }
258 } else {
259 if (VM.BuildForIA32) {
260 if (size == 0) {
261 DefUse.removeInstructionAndUpdateDU(inst);
262 } else if (size == 1) {
263 int index = 0;
264 Operator moveOp = IRTools.getMoveOp(type.getTypeRef());
265 Instruction i2 = Move.create(moveOp, scalars[index].copyRO(), AStore.getClearValue(inst));
266 DefUse.replaceInstructionAndUpdateDU(inst, i2);
267 } else {
268 Operator moveOp = IRTools.getCondMoveOp(type.getTypeRef());
269 Operand value = AStore.getClearValue(inst);
270 Instruction i2 = CondMove.create(moveOp, scalars[0].copyRO(),
271 AStore.getIndex(inst), IC(0), ConditionOperand.EQUAL(),
272 value, scalars[0].copyRO());
273 DefUse.replaceInstructionAndUpdateDU(inst, i2);
274 Instruction i3 = CondMove.create(moveOp, scalars[1].copyRO(),
275 AStore.getIndex(inst), IC(0), ConditionOperand.NOT_EQUAL(),
276 value, scalars[1].copyRO());
277 i2.insertAfter(i3);
278 DefUse.updateDUForNewInstruction(i3);
279 }
280 } else {
281 if (size == 1) {
282 int index = 0;
283 Operator moveOp = IRTools.getMoveOp(type.getTypeRef());
284 Instruction i2 = Move.create(moveOp, scalars[index].copyRO(), AStore.getClearValue(inst));
285 DefUse.replaceInstructionAndUpdateDU(inst, i2);
286 } else {
287 DefUse.removeInstructionAndUpdateDU(inst);
288 }
289 }
290 }
291 }
292 break;
293 case NULL_CHECK_opcode: {
294 // Null check on result of new array must succeed
295 Instruction i2 = Move.create(GUARD_MOVE, NullCheck.getClearGuardResult(inst), new TrueGuardOperand());
296 DefUse.replaceInstructionAndUpdateDU(inst, i2);
297 }
298 break;
299 case BOUNDS_CHECK_opcode: {
300 // Remove or create trap as appropriate
301 Instruction i2 = TrapIf.create(TRAP_IF, BoundsCheck.getClearGuardResult(inst),
302 IC(size), BoundsCheck.getClearIndex(inst), ConditionOperand.LOWER_EQUAL(),
303 TrapCodeOperand.ArrayBounds());
304 DefUse.replaceInstructionAndUpdateDU(inst, i2);
305 }
306 break;
307 case CHECKCAST_opcode:
308 case CHECKCAST_NOTNULL_opcode:
309 case CHECKCAST_UNRESOLVED_opcode: {
310 // We cannot handle removing the checkcast if the result of the
311 // checkcast test is unknown
312 TypeReference lhsType = TypeCheck.getType(inst).getTypeRef();
313 if (ClassLoaderProxy.includesType(lhsType, vmArray.getTypeRef()) == OptConstants.YES) {
314 if (visited == null) {
315 visited = new HashSet<Register>();
316 }
317 Register copy = TypeCheck.getResult(inst).getRegister();
318 if(!visited.contains(copy)) {
319 visited.add(copy);
320 transform2(copy, inst, scalars);
321 // NB will remove inst
322 } else {
323 DefUse.removeInstructionAndUpdateDU(inst);
324 }
325 } else {
326 Instruction i2 = Trap.create(TRAP, null, TrapCodeOperand.CheckCast());
327 DefUse.replaceInstructionAndUpdateDU(inst, i2);
328 }
329 }
330 break;
331 case INSTANCEOF_opcode:
332 case INSTANCEOF_NOTNULL_opcode:
333 case INSTANCEOF_UNRESOLVED_opcode: {
334 // We cannot handle removing the instanceof if the result of the
335 // instanceof test is unknown
336 TypeReference lhsType = InstanceOf.getType(inst).getTypeRef();
337 Instruction i2;
338 if (ClassLoaderProxy.includesType(lhsType, vmArray.getTypeRef()) == OptConstants.YES) {
339 i2 = Move.create(INT_MOVE, InstanceOf.getClearResult(inst), IC(1));
340 } else {
341 i2 = Move.create(INT_MOVE, InstanceOf.getClearResult(inst), IC(0));
342 }
343 DefUse.replaceInstructionAndUpdateDU(inst, i2);
344 }
345 break;
346 case GET_OBJ_TIB_opcode: {
347 Instruction i2 = Move.create(REF_MOVE, GuardedUnary.getClearResult(inst), new TIBConstantOperand(vmArray));
348 DefUse.replaceInstructionAndUpdateDU(inst, i2);
349 }
350 break;
351 case REF_MOVE_opcode: {
352 if (visited == null) {
353 visited = new HashSet<Register>();
354 }
355 Register copy = Move.getResult(inst).getRegister();
356 if(!visited.contains(copy)) {
357 visited.add(copy);
358 transform2(copy, inst, scalars);
359 // NB will remove inst
360 } else {
361 DefUse.removeInstructionAndUpdateDU(inst);
362 }
363 }
364 break;
365 default:
366 throw new OptimizingCompilerException("Unexpected instruction: " + inst);
367 }
368 }
369
370 /**
371 * Some cases we don't handle yet. TODO: handle them.
372 *
373 * @param ir the governing IR
374 * @param reg the register in question
375 * @param size the size of the array to scalar replace.
376 */
377 private static boolean containsUnsupportedUse(IR ir, Register reg, int size, RVMArray vmArray, Set<Register> visited) {
378 // If an array is accessed by a non-constant integer, what's the maximum size of support array?
379 final int MAX_SIZE_FOR_VARIABLE_LOAD_STORE = VM.BuildForIA32 ? 2 : 1;
380 for (RegisterOperand use = reg.useList; use != null; use = use.getNext()) {
381 switch (use.instruction.getOpcode()) {
382 case REF_IFCMP_opcode:
383 // Comparison between the array reference we want to replace and
384 // another. TODO: this case is either always true or always false,
385 // we should optimize
386 case NEWOBJMULTIARRAY_opcode:
387 // dimensions array must be passed as an array argument to
388 // newobjmultiarray, common case of 2 arguments is handled without a
389 // dimensions array
390 case OBJARRAY_STORE_CHECK_opcode:
391 case OBJARRAY_STORE_CHECK_NOTNULL_opcode:
392 // TODO: create a store check that doesn't need an array argument
393 return true;
394 case CHECKCAST_opcode:
395 case CHECKCAST_NOTNULL_opcode:
396 case CHECKCAST_UNRESOLVED_opcode: {
397 // We cannot handle removing the checkcast if the result of the
398 // checkcast test is unknown
399 TypeReference lhsType = TypeCheck.getType(use.instruction).getTypeRef();
400 byte ans = ClassLoaderProxy.includesType(lhsType, vmArray.getTypeRef());
401 if (ans == OptConstants.MAYBE) {
402 return true;
403 } else if (ans == OptConstants.YES) {
404 // handle as a move
405 if (visited == null) {
406 visited = new HashSet<Register>();
407 }
408 Register copy = TypeCheck.getResult(use.instruction).getRegister();
409 if(!visited.contains(copy)) {
410 visited.add(copy);
411 if(containsUnsupportedUse(ir, copy, size, vmArray, visited)) {
412 return true;
413 }
414 }
415 }
416 }
417 break;
418 case INSTANCEOF_opcode:
419 case INSTANCEOF_NOTNULL_opcode:
420 case INSTANCEOF_UNRESOLVED_opcode: {
421 // We cannot handle removing the instanceof if the result of the
422 // instanceof test is unknown
423 TypeReference lhsType = InstanceOf.getType(use.instruction).getTypeRef();
424 if (ClassLoaderProxy.includesType(lhsType, vmArray.getTypeRef()) == OptConstants.MAYBE) {
425 return true;
426 }
427 }
428 break;
429 case INT_ASTORE_opcode:
430 case LONG_ASTORE_opcode:
431 case FLOAT_ASTORE_opcode:
432 case DOUBLE_ASTORE_opcode:
433 case BYTE_ASTORE_opcode:
434 case SHORT_ASTORE_opcode:
435 case REF_ASTORE_opcode:
436 // Don't handle registers as indexes
437 // TODO: support for registers if the size of the array is small (e.g. 1)
438 if (!AStore.getIndex(use.instruction).isIntConstant() && size > MAX_SIZE_FOR_VARIABLE_LOAD_STORE) {
439 return true;
440 }
441 break;
442 case INT_ALOAD_opcode:
443 case LONG_ALOAD_opcode:
444 case FLOAT_ALOAD_opcode:
445 case DOUBLE_ALOAD_opcode:
446 case BYTE_ALOAD_opcode:
447 case UBYTE_ALOAD_opcode:
448 case USHORT_ALOAD_opcode:
449 case SHORT_ALOAD_opcode:
450 case REF_ALOAD_opcode:
451 // Don't handle registers as indexes
452 // TODO: support for registers if the size of the array is small (e.g. 1)
453 if (!ALoad.getIndex(use.instruction).isIntConstant() && size > MAX_SIZE_FOR_VARIABLE_LOAD_STORE) {
454 return true;
455 }
456 break;
457 case REF_MOVE_opcode:
458 if (visited == null) {
459 visited = new HashSet<Register>();
460 }
461 Register copy = Move.getResult(use.instruction).getRegister();
462 if(!visited.contains(copy)) {
463 visited.add(copy);
464 if(containsUnsupportedUse(ir, copy, size, vmArray, visited)) {
465 return true;
466 }
467 }
468 break;
469 }
470 }
471 return false;
472 }
473 }