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.lir2mir;
014
015import static org.jikesrvm.compilers.opt.ir.Operators.ARRAYLENGTH_opcode;
016import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_2LONG_opcode;
017import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_REM_opcode;
018import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_2LONG_opcode;
019import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_REM_opcode;
020import static org.jikesrvm.compilers.opt.ir.Operators.GET_ARRAY_ELEMENT_TIB_FROM_TIB_opcode;
021import static org.jikesrvm.compilers.opt.ir.Operators.GET_CLASS_TIB_opcode;
022import static org.jikesrvm.compilers.opt.ir.Operators.GET_DOES_IMPLEMENT_FROM_TIB_opcode;
023import static org.jikesrvm.compilers.opt.ir.Operators.GET_OBJ_TIB_opcode;
024import static org.jikesrvm.compilers.opt.ir.Operators.GET_SUPERCLASS_IDS_FROM_TIB_opcode;
025import static org.jikesrvm.compilers.opt.ir.Operators.GET_TYPE_FROM_TIB_opcode;
026import static org.jikesrvm.compilers.opt.ir.Operators.INT_LOAD;
027import static org.jikesrvm.compilers.opt.ir.Operators.LONG_2DOUBLE_opcode;
028import static org.jikesrvm.compilers.opt.ir.Operators.LONG_2FLOAT_opcode;
029import static org.jikesrvm.compilers.opt.ir.Operators.LONG_DIV_opcode;
030import static org.jikesrvm.compilers.opt.ir.Operators.LONG_REM_opcode;
031import static org.jikesrvm.compilers.opt.ir.Operators.REF_LOAD;
032import static org.jikesrvm.compilers.opt.ir.Operators.SYSCALL;
033import static org.jikesrvm.compilers.opt.ir.Operators.SYSCALL_opcode;
034import static org.jikesrvm.objectmodel.TIBLayoutConstants.TIB_ARRAY_ELEMENT_TIB_INDEX;
035import static org.jikesrvm.objectmodel.TIBLayoutConstants.TIB_DOES_IMPLEMENT_INDEX;
036import static org.jikesrvm.objectmodel.TIBLayoutConstants.TIB_SUPERCLASS_IDS_INDEX;
037import static org.jikesrvm.objectmodel.TIBLayoutConstants.TIB_TYPE_INDEX;
038import static org.jikesrvm.runtime.UnboxedSizeConstants.LOG_BYTES_IN_ADDRESS;
039
040import org.jikesrvm.VM;
041import org.jikesrvm.classloader.RVMType;
042import org.jikesrvm.compilers.opt.DefUse;
043import org.jikesrvm.compilers.opt.NullCheckCombining;
044import org.jikesrvm.compilers.opt.OptOptions;
045import org.jikesrvm.compilers.opt.OptimizingCompilerException;
046import org.jikesrvm.compilers.opt.driver.CompilerPhase;
047import org.jikesrvm.compilers.opt.driver.OptimizationPlanAtomicElement;
048import org.jikesrvm.compilers.opt.driver.OptimizationPlanCompositeElement;
049import org.jikesrvm.compilers.opt.driver.OptimizationPlanElement;
050import org.jikesrvm.compilers.opt.driver.OptimizingCompiler;
051import org.jikesrvm.compilers.opt.hir2lir.ConvertToLowLevelIR;
052import org.jikesrvm.compilers.opt.ir.BasicBlock;
053import org.jikesrvm.compilers.opt.ir.Binary;
054import org.jikesrvm.compilers.opt.ir.Call;
055import org.jikesrvm.compilers.opt.ir.GuardedBinary;
056import org.jikesrvm.compilers.opt.ir.GuardedUnary;
057import org.jikesrvm.compilers.opt.ir.IR;
058import org.jikesrvm.compilers.opt.ir.IRTools;
059import org.jikesrvm.compilers.opt.ir.Instruction;
060import org.jikesrvm.compilers.opt.ir.Load;
061import org.jikesrvm.compilers.opt.ir.MIRInfo;
062import org.jikesrvm.compilers.opt.ir.Operators;
063import org.jikesrvm.compilers.opt.ir.Unary;
064import org.jikesrvm.compilers.opt.ir.operand.AddressConstantOperand;
065import org.jikesrvm.compilers.opt.ir.operand.LocationOperand;
066import org.jikesrvm.compilers.opt.ir.operand.MethodOperand;
067import org.jikesrvm.compilers.opt.ir.operand.Operand;
068import org.jikesrvm.compilers.opt.ir.operand.TypeOperand;
069import org.jikesrvm.compilers.opt.liveness.LiveAnalysis;
070import org.jikesrvm.objectmodel.JavaHeader;
071import org.jikesrvm.objectmodel.ObjectModel;
072import org.jikesrvm.runtime.Entrypoints;
073import org.vmmagic.unboxed.Offset;
074
075/**
076 * Convert an IR object from LIR to MIR via BURS
077 */
078public final class ConvertLIRtoMIR extends OptimizationPlanCompositeElement {
079
080  /**
081   * Create this phase element as a composite of other elements
082   */
083  public ConvertLIRtoMIR() {
084    super("Instruction Selection", new OptimizationPlanElement[]{
085        // Stage 1: Reduce the LIR operator set to a core set of operators.
086        new OptimizationPlanAtomicElement(new ReduceOperators()),
087
088        // Stage 2: Convert ALU operators
089        new OptimizationPlanAtomicElement(
090          VM.BuildForIA32 ? new org.jikesrvm.compilers.opt.lir2mir.ia32.ConvertALUOperators() :
091                            new org.jikesrvm.compilers.opt.lir2mir.ppc.ConvertALUOperators()),
092
093        // Stage 3: Normalize usage of constants to simplify Stage 3.
094        new OptimizationPlanAtomicElement(new NormalizeConstantsPhase()),
095
096        // Stage 4a: Compute liveness information for DepGraph
097        new OptimizationPlanAtomicElement(new DoLiveness()),
098
099        // Stage 4b: Block by block build DepGraph and do
100        //           BURS based instruction selection.
101        new OptimizationPlanAtomicElement(new DoBURS()),
102
103        // Stage 5: Handle complex operators
104        //          (those that expand to multiple basic blocks of MIR).
105        new OptimizationPlanAtomicElement(new ComplexOperators()),
106
107        // Stage 6: Use validation operands to do null check combining,
108        //          and then finish the removal off all validation
109        //          operands (they are not present in the MIR).
110        new OptimizationPlanAtomicElement(new NullCheckCombining() {
111          @Override
112          public void perform(IR ir) {
113            super.perform(ir);
114            // ir now contains well formed MIR.
115            ir.IRStage = IR.MIR;
116            ir.MIRInfo = new MIRInfo(ir);
117          }
118        }),
119        new OptimizationPlanAtomicElement(new InsertIMMQ_MOVForX64())});
120  }
121
122  /**
123   * Stage 1: Reduce the LIR operator set to a core set of operators.
124   */
125  private static final class ReduceOperators extends CompilerPhase {
126
127    @Override
128    public String getName() {
129      return "Reduce Operators";
130    }
131
132    @Override
133    public CompilerPhase newExecution(IR ir) {
134      return this;
135    }
136
137    private void expandSysCall(Instruction s, IR ir) {
138      if (VM.BuildForIA32) {
139        org.jikesrvm.compilers.opt.regalloc.ia32.CallingConvention.expandSysCall(s, ir);
140      } else {
141        if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
142        org.jikesrvm.compilers.opt.regalloc.ppc.CallingConvention.expandSysCall(s, ir);
143      }
144    }
145
146    @Override
147    public void perform(IR ir) {
148      for (Instruction s = ir.firstInstructionInCodeOrder(); s != null; s = s.nextInstructionInCodeOrder()) {
149        switch (s.getOpcode()) {
150          case ARRAYLENGTH_opcode: {
151            // array_ref[ObjectModel.getArrayLengthOffset()] contains the length
152            Load.mutate(s,
153                        INT_LOAD,
154                        GuardedUnary.getClearResult(s),
155                        GuardedUnary.getClearVal(s),
156                        IRTools.AC(ObjectModel.getArrayLengthOffset()),
157                        new LocationOperand(),
158                        GuardedUnary.getClearGuard(s));
159          }
160          break;
161
162          case GET_OBJ_TIB_opcode:
163            // TODO: valid location operand.
164            Operand address = GuardedUnary.getClearVal(s);
165            Load.mutate(s,
166                        Operators.REF_LOAD,
167                        GuardedUnary.getClearResult(s),
168                        address,
169                        new AddressConstantOperand(JavaHeader.getTibOffset()),
170                        null,
171                        GuardedUnary.getClearGuard(s));
172            break;
173
174          case GET_CLASS_TIB_opcode: {
175            RVMType type = ((TypeOperand) Unary.getVal(s)).getVMType();
176            Offset offset = type.getTibOffset();
177            Load.mutate(s,
178                        REF_LOAD,
179                        Unary.getClearResult(s),
180                        ir.regpool.makeJTOCOp(),
181                        IRTools.AC(offset),
182                        new LocationOperand(offset));
183          }
184          break;
185
186          case GET_TYPE_FROM_TIB_opcode: {
187            // TODO: Valid location operand?
188            Load.mutate(s,
189                        REF_LOAD,
190                        Unary.getClearResult(s),
191                        Unary.getClearVal(s),
192                        IRTools.AC(Offset.fromIntZeroExtend(TIB_TYPE_INDEX << LOG_BYTES_IN_ADDRESS)),
193                        null);
194          }
195          break;
196
197          case GET_SUPERCLASS_IDS_FROM_TIB_opcode: {
198            // TODO: Valid location operand?
199            Load.mutate(s,
200                        REF_LOAD,
201                        Unary.getClearResult(s),
202                        Unary.getClearVal(s),
203                        IRTools.AC(Offset.fromIntZeroExtend(TIB_SUPERCLASS_IDS_INDEX << LOG_BYTES_IN_ADDRESS)),
204                        null);
205          }
206          break;
207
208          case GET_DOES_IMPLEMENT_FROM_TIB_opcode: {
209            // TODO: Valid location operand?
210            Load.mutate(s,
211                        REF_LOAD,
212                        Unary.getClearResult(s),
213                        Unary.getClearVal(s),
214                        IRTools.AC(Offset.fromIntZeroExtend(TIB_DOES_IMPLEMENT_INDEX << LOG_BYTES_IN_ADDRESS)),
215                        null);
216          }
217          break;
218
219          case GET_ARRAY_ELEMENT_TIB_FROM_TIB_opcode: {
220            // TODO: Valid location operand?
221            Load.mutate(s,
222                        REF_LOAD,
223                        Unary.getClearResult(s),
224                        Unary.getClearVal(s),
225                        IRTools.AC(Offset.fromIntZeroExtend(TIB_ARRAY_ELEMENT_TIB_INDEX << LOG_BYTES_IN_ADDRESS)),
226                        null);
227          }
228          break;
229
230          case LONG_DIV_opcode: {
231            if (VM.BuildForPowerPC && VM.BuildFor64Addr) break; // don't reduce operator -- leave for BURS
232            Call.mutate2(s,
233                         SYSCALL,
234                         GuardedBinary.getClearResult(s),
235                         null,
236                         MethodOperand.STATIC(Entrypoints.sysLongDivideIPField),
237                         GuardedBinary.getClearVal1(s),
238                         GuardedBinary.getClearVal2(s));
239            ConvertToLowLevelIR.expandSysCallTarget(s, ir);
240            expandSysCall(s, ir);
241          }
242          break;
243
244          case LONG_REM_opcode: {
245            if (VM.BuildForPowerPC && VM.BuildFor64Addr) break; // don't reduce operator -- leave for BURS
246            Call.mutate2(s,
247                         SYSCALL,
248                         GuardedBinary.getClearResult(s),
249                         null,
250                         MethodOperand.STATIC(Entrypoints.sysLongRemainderIPField),
251                         GuardedBinary.getClearVal1(s),
252                         GuardedBinary.getClearVal2(s));
253            ConvertToLowLevelIR.expandSysCallTarget(s, ir);
254            expandSysCall(s, ir);
255          }
256          break;
257
258          case FLOAT_REM_opcode:
259          case DOUBLE_REM_opcode: {
260            if (VM.BuildForPowerPC) {
261              Call.mutate2(s,
262                           SYSCALL,
263                           Binary.getClearResult(s),
264                           null,
265                           MethodOperand.STATIC(Entrypoints.sysDoubleRemainderIPField),
266                           Binary.getClearVal1(s),
267                           Binary.getClearVal2(s));
268              ConvertToLowLevelIR.expandSysCallTarget(s, ir);
269              expandSysCall(s, ir);
270            }
271          }
272          break;
273
274          case LONG_2FLOAT_opcode: {
275            if (VM.BuildForPowerPC) {
276              Call.mutate1(s,
277                           SYSCALL,
278                           Unary.getClearResult(s),
279                           null,
280                           MethodOperand.STATIC(Entrypoints.sysLongToFloatIPField),
281                           Unary.getClearVal(s));
282              ConvertToLowLevelIR.expandSysCallTarget(s, ir);
283              expandSysCall(s, ir);
284            }
285          }
286          break;
287
288          case LONG_2DOUBLE_opcode: {
289            if (VM.BuildForPowerPC) {
290              Call.mutate1(s,
291                           SYSCALL,
292                           Unary.getClearResult(s),
293                           null,
294                           MethodOperand.STATIC(Entrypoints.sysLongToDoubleIPField),
295                           Unary.getClearVal(s));
296              ConvertToLowLevelIR.expandSysCallTarget(s, ir);
297              expandSysCall(s, ir);
298            }
299          }
300          break;
301
302          case FLOAT_2LONG_opcode: {
303            if (VM.BuildForPowerPC && VM.BuildFor64Addr || VM.BuildForSSE2Full) break; // don't reduce operator -- leave for BURS
304            Call.mutate1(s,
305                         SYSCALL,
306                         Unary.getClearResult(s),
307                         null,
308                         MethodOperand.STATIC(Entrypoints.sysFloatToLongIPField),
309                         Unary.getClearVal(s));
310            ConvertToLowLevelIR.expandSysCallTarget(s, ir);
311            expandSysCall(s, ir);
312          }
313          break;
314
315          case DOUBLE_2LONG_opcode: {
316            if (VM.BuildForPowerPC && VM.BuildFor64Addr || VM.BuildForSSE2Full) break; // don't reduce operator -- leave for BURS
317            Call.mutate1(s,
318                         SYSCALL,
319                         Unary.getClearResult(s),
320                         null,
321                         MethodOperand.STATIC(Entrypoints.sysDoubleToLongIPField),
322                         Unary.getClearVal(s));
323            ConvertToLowLevelIR.expandSysCallTarget(s, ir);
324            expandSysCall(s, ir);
325          }
326          break;
327          case SYSCALL_opcode:
328            expandSysCall(s, ir);
329            break;
330          default:
331            break;
332        }
333      }
334    }
335  }
336
337  /**
338   * Stage 2: Normalize usage of int constants to make less work in Stage 3.
339   */
340  private static final class NormalizeConstantsPhase extends CompilerPhase {
341
342    @Override
343    public String getName() {
344      return "Normalize Constants";
345    }
346
347    @Override
348    public CompilerPhase newExecution(IR ir) {
349      return this;
350    }
351
352    @Override
353    public void perform(IR ir) {
354      if (VM.BuildForIA32) {
355        org.jikesrvm.compilers.opt.lir2mir.ia32.NormalizeConstants.perform(ir);
356      } else {
357        if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
358        org.jikesrvm.compilers.opt.lir2mir.ppc.NormalizeConstants.perform(ir);
359      }
360    }
361  }
362
363  private static final class DoLiveness extends CompilerPhase {
364
365    @Override
366    public String getName() {
367      return "Live Handlers";
368    }
369
370    @Override
371    public CompilerPhase newExecution(IR ir) {
372      return this;
373    }
374
375    @Override
376    public void perform(IR ir) {
377      if (ir.options.L2M_HANDLER_LIVENESS) {
378        new LiveAnalysis(false, false, true).perform(ir);
379      } else {
380        ir.setHandlerLivenessComputed(false);
381      }
382    }
383  }
384
385  /**
386   * Stage 3: Block by block build DepGraph and do BURS based
387   * instruction selection.
388   */
389  private static final class DoBURS extends CompilerPhase {
390
391    @Override
392    public String getName() {
393      return "DepGraph & BURS";
394    }
395
396    @Override
397    public CompilerPhase newExecution(IR ir) {
398      return this;
399    }
400
401    @Override
402    public void reportAdditionalStats() {
403      VM.sysWrite("  ");
404      VM.sysWrite(container.counter1 / container.counter2 * 100, 2);
405      VM.sysWrite("% Infrequent BBs");
406    }
407
408    // IR is inconsistent state between DoBURS and ComplexOperators.
409    // It isn't verifiable again until after ComplexOperators completes.
410    @Override
411    public void verify(IR ir) { }
412
413    @Override
414    public void perform(IR ir) {
415      OptOptions options = ir.options;
416      DefUse.recomputeSpansBasicBlock(ir);
417      MinimalBURS mburs = new MinimalBURS(ir);
418      NormalBURS burs = new NormalBURS(ir);
419      for (BasicBlock bb = ir.firstBasicBlockInCodeOrder(); bb != null; bb = bb.nextBasicBlockInCodeOrder()) {
420        if (bb.isEmpty()) continue;
421        container.counter2++;
422        if (bb.getInfrequent()) {
423          container.counter1++;
424          if (options.FREQ_FOCUS_EFFORT) {
425            // Basic block is infrequent -- use quick and dirty instruction selection
426            mburs.prepareForBlock(bb);
427            mburs.invoke(bb);
428            mburs.finalizeBlock(bb);
429            continue;
430          }
431        }
432        // Use Normal instruction selection.
433        burs.prepareForBlock(bb);
434        // I. Build Dependence graph for the basic block
435        NormalBURS_DepGraph dgraph = new NormalBURS_DepGraph(ir, bb.firstRealInstruction(), bb.lastRealInstruction(), bb);
436        if (options.PRINT_DG_BURS) {
437          // print dependence graph.
438          OptimizingCompiler.header("DepGraph", ir.method);
439          dgraph.printDepGraph();
440          OptimizingCompiler.bottom("DepGraph", ir.method);
441        }
442        // II. Invoke BURS and rewrite block from LIR to MIR
443        try {
444          burs.invoke(dgraph);
445        } catch (OptimizingCompilerException e) {
446          System.err.println("Exception occurred in ConvertLIRtoMIR");
447          e.printStackTrace();
448          ir.printInstructions();
449          throw e;
450        }
451        burs.finalizeBlock(bb);
452      }
453    }
454  }
455
456  /**
457   * Stage 4: Handle complex operators
458   * (those that expand to multiple basic blocks).
459   */
460  private static final class ComplexOperators extends CompilerPhase {
461
462    @Override
463    public String getName() {
464      return "Complex Operators";
465    }
466
467    @Override
468    public CompilerPhase newExecution(IR ir) {
469      return this;
470    }
471
472    @Override
473    public void perform(IR ir) {
474      if (VM.BuildForIA32) {
475        org.jikesrvm.compilers.opt.lir2mir.ia32.ComplexLIR2MIRExpansion.convert(ir);
476      } else {
477        if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
478        org.jikesrvm.compilers.opt.lir2mir.ppc.ComplexLIR2MIRExpansion.convert(ir);
479      }
480    }
481  }
482
483  private static final class InsertIMMQ_MOVForX64 extends CompilerPhase {
484    @Override
485    public String getName() {
486      return "Insert IMMQ_MOV instructions for 64-bit immediate values";
487    }
488
489    @Override
490    public boolean shouldPerform(OptOptions options) {
491      return VM.BuildForIA32 && VM.BuildFor64Addr;
492    }
493
494    @Override
495    public CompilerPhase newExecution(IR ir) {
496      return this;
497    }
498
499    @Override
500    public void perform(IR ir) {
501      if (VM.BuildForIA32) {
502        org.jikesrvm.compilers.opt.lir2mir.ia32.ComplexLIR2MIRExpansion.process64BitImmediateValues(ir);
503      }
504    }
505  }
506}