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