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