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;
014
015 import static org.jikesrvm.compilers.opt.driver.OptConstants.YES;
016 import static org.jikesrvm.compilers.opt.ir.Operators.ARRAYLENGTH_opcode;
017 import static org.jikesrvm.compilers.opt.ir.Operators.BOUNDS_CHECK_opcode;
018 import static org.jikesrvm.compilers.opt.ir.Operators.GET_CAUGHT_EXCEPTION;
019 import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_MOVE;
020 import static org.jikesrvm.compilers.opt.ir.Operators.INT_MOVE;
021 import static org.jikesrvm.compilers.opt.ir.Operators.NEWARRAY;
022 import static org.jikesrvm.compilers.opt.ir.Operators.NEWARRAY_UNRESOLVED;
023 import static org.jikesrvm.compilers.opt.ir.Operators.NOP;
024 import static org.jikesrvm.compilers.opt.ir.Operators.PHI;
025 import static org.jikesrvm.compilers.opt.ir.Operators.SET_CAUGHT_EXCEPTION;
026 import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_BEGIN;
027 import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_END;
028
029 import java.lang.reflect.Constructor;
030 import java.util.ArrayList;
031 import java.util.Enumeration;
032
033 import org.jikesrvm.VM;
034 import org.jikesrvm.compilers.opt.controlflow.BranchOptimizations;
035 import org.jikesrvm.compilers.opt.controlflow.BranchSimplifier;
036 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
037 import org.jikesrvm.compilers.opt.ir.BasicBlock;
038 import org.jikesrvm.compilers.opt.ir.Binary;
039 import org.jikesrvm.compilers.opt.ir.BoundsCheck;
040 import org.jikesrvm.compilers.opt.ir.GuardedUnary;
041 import org.jikesrvm.compilers.opt.ir.IR;
042 import org.jikesrvm.compilers.opt.ir.Instruction;
043 import org.jikesrvm.compilers.opt.ir.Move;
044 import org.jikesrvm.compilers.opt.ir.NewArray;
045 import org.jikesrvm.compilers.opt.ir.Operator;
046 import org.jikesrvm.compilers.opt.ir.Phi;
047 import org.jikesrvm.compilers.opt.ir.Register;
048 import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
049 import org.jikesrvm.compilers.opt.ir.operand.Operand;
050 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
051 import org.jikesrvm.compilers.opt.ir.operand.TrueGuardOperand;
052
053 /**
054 * Simple flow-insensitive optimizations.
055 *
056 * <p> Except for the "CompilerPhase" methods, all fields and methods in
057 * this class are declared static.
058 */
059 public final class Simple extends CompilerPhase {
060
061 private final BranchOptimizations branchOpts = new BranchOptimizations(-1, false, false, false);
062
063 /**
064 * At what optimization level should this phase be run?
065 */
066 private final int level;
067 /**
068 * Perform type propagation?
069 */
070 private final boolean typeProp;
071 /**
072 * Attempt to eliminate bounds and cast checks?
073 */
074 private final boolean foldChecks;
075 /**
076 * Fold conditional branches with constant operands?
077 */
078 private final boolean foldBranches;
079 /**
080 * Sort registers used by commutative operators
081 */
082 private final boolean sortRegisters;
083
084 @Override
085 public boolean shouldPerform(OptOptions options) {
086 return options.getOptLevel() >= level;
087 }
088
089 @Override
090 public String getName() {
091 return "Simple Opts";
092 }
093
094 @Override
095 public boolean printingEnabled(OptOptions options, boolean before) {
096 return false;
097 }
098
099 /**
100 * The constructor is used to specify what pieces of Simple will
101 * be enabled for this instance. Some pieces are always enabled.
102 * Customizing can be useful because some of the optimizations are not
103 * valid/useful on LIR or even on "late stage" HIR.
104 *
105 * @param level at what optimization level should the phase be enabled?
106 * @param typeProp should type propagation be peformed?
107 * @param foldChecks should we attempt to eliminate boundscheck?
108 * @param foldBranches should we attempt to constant fold conditional
109 * @param sortRegisters should we sort use operands?
110 * branches?
111 */
112 public Simple(int level, boolean typeProp, boolean foldChecks, boolean foldBranches, boolean sortRegisters) {
113 super(new Object[]{level, typeProp, foldChecks, foldBranches, sortRegisters});
114 this.level = level;
115 this.typeProp = typeProp;
116 this.foldChecks = foldChecks;
117 this.foldBranches = foldBranches;
118 this.sortRegisters = sortRegisters;
119 }
120
121 /**
122 * Constructor for this compiler phase
123 */
124 private static final Constructor<CompilerPhase> constructor =
125 getCompilerPhaseConstructor(Simple.class,
126 new Class[]{Integer.TYPE, Boolean.TYPE, Boolean.TYPE, Boolean.TYPE, Boolean.TYPE});
127
128 /**
129 * Get a constructor object for this compiler phase
130 * @return compiler phase constructor
131 */
132 @Override
133 public Constructor<CompilerPhase> getClassConstructor() {
134 return constructor;
135 }
136
137 /**
138 * Main driver for the simple optimizations
139 *
140 * @param ir the IR to optimize
141 */
142 @Override
143 public void perform(IR ir) {
144 // Compute defList, useList, useCount fields for each register.
145 DefUse.computeDU(ir);
146 // Recompute isSSA flags
147 DefUse.recomputeSSA(ir);
148 // Simple copy propagation.
149 // This pass incrementally updates the register list.
150 copyPropagation(ir);
151 // Simple type propagation.
152 // This pass uses the register list, but doesn't modify it.
153 if (typeProp) {
154 typePropagation(ir);
155 }
156 // Perform simple bounds-check and arraylength elimination.
157 // This pass incrementally updates the register list
158 if (foldChecks) {
159 arrayPropagation(ir);
160 }
161 // Simple dead code elimination.
162 // This pass incrementally updates the register list
163 eliminateDeadInstructions(ir);
164 // constant folding
165 // This pass usually doesn't modify the DU, but
166 // if it does it will recompute it.
167 foldConstants(ir);
168 // Simple local expression folding respecting DU
169 if (ir.options.LOCAL_EXPRESSION_FOLDING && ExpressionFolding.performLocal(ir)) {
170 // constant folding again
171 foldConstants(ir);
172 }
173 // Try to remove conditional branches with constant operands
174 // If it actually constant folds a branch,
175 // this pass will recompute the DU
176 if (foldBranches) {
177 simplifyConstantBranches(ir);
178 }
179 // Should we sort commutative use operands
180 if (sortRegisters) {
181 sortCommutativeRegisterUses(ir);
182 }
183 }
184
185 /**
186 * Sort commutative use operands so that those defined most are on the lhs
187 *
188 * @param ir the IR to work on
189 */
190 private static void sortCommutativeRegisterUses(IR ir) {
191 // Pass over instructions
192 for (Enumeration<Instruction> e = ir.forwardInstrEnumerator(); e.hasMoreElements();) {
193 Instruction s = e.nextElement();
194 // Sort most frequently defined operands onto lhs
195 if (Binary.conforms(s) && s.operator.isCommutative() &&
196 Binary.getVal1(s).isRegister() && Binary.getVal2(s).isRegister()) {
197 RegisterOperand rop1 = Binary.getVal1(s).asRegister();
198 RegisterOperand rop2 = Binary.getVal2(s).asRegister();
199 // Simple SSA based test
200 if (rop1.register.isSSA()) {
201 if(rop2.register.isSSA()) {
202 // ordering is arbitrary, ignore
203 } else {
204 // swap
205 Binary.setVal1(s, rop2);
206 Binary.setVal2(s, rop1);
207 }
208 } else if (rop2.register.isSSA()) {
209 // already have prefered ordering
210 } else {
211 // neither registers are SSA so place registers used more on the RHS
212 // (we don't have easy access to a count of the number of definitions)
213 if (rop1.register.useCount > rop2.register.useCount) {
214 // swap
215 Binary.setVal1(s, rop2);
216 Binary.setVal2(s, rop1);
217 }
218 }
219 }
220 }
221 }
222
223 /**
224 * Perform flow-insensitive copy and constant propagation using
225 * register list information.
226 *
227 * <ul>
228 * <li> Note: register list MUST be initialized BEFORE calling this routine.
229 * <li> Note: this function incrementally maintains the register list.
230 * </ul>
231 *
232 * @param ir the IR in question
233 */
234 public static void copyPropagation(IR ir) {
235 // Use register list to enumerate register objects
236 Register elemNext;
237 boolean reiterate = true;
238 while (reiterate) { // /MT/ better think about proper ordering.
239 reiterate = false;
240 for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = elemNext) {
241 elemNext = reg.getNext(); // we may remove reg, so get elemNext up front
242 if (reg.useList == null || // Copy propagation not possible if reg
243 // has no uses
244 reg.defList == null || // Copy propagation not possible if reg
245 // has no defs
246 !reg.isSSA()) { // Flow-insensitive copy prop only possible
247 // for SSA registers.
248 continue;
249 }
250 // isSSA => reg has exactly one definition, reg.defList.
251 RegisterOperand lhs = reg.defList;
252 Instruction defInstr = lhs.instruction;
253 Operand rhs;
254 // Copy/constant propagation only possible when defInstr is a move
255 if (defInstr.isMove()) {
256 rhs = Move.getVal(defInstr);
257 } else if (defInstr.operator() == PHI) {
258 Operand phiVal = equivalentValforPHI(defInstr);
259 if (phiVal == null) continue;
260 rhs = phiVal;
261 } else {
262 continue;
263 }
264
265 if (rhs.isRegister()) {
266 Register rrhs = rhs.asRegister().getRegister();
267 // If rhs is a non-SSA register, then we can't propagate it
268 // because we can't be sure that the same definition reaches
269 // all uses.
270 if (!rrhs.isSSA()) continue;
271
272 // If rhs is a physical register, then we can't safely propagate
273 // it to uses of lhs because we don't understand the implicit
274 // uses/defs of physical registers well enough to do so safely.
275 if (rrhs.isPhysical()) continue;
276 }
277
278 reiterate = ir.options.getOptLevel() > 1;
279 // Now substitute rhs for all uses of lhs, updating the
280 // register list as we go.
281 if (rhs.isRegister()) {
282 RegisterOperand nextUse;
283 RegisterOperand rhsRegOp = rhs.asRegister();
284 for (RegisterOperand use = reg.useList; use != null; use = nextUse) {
285 nextUse = use.getNext(); // get early before reg's useList is updated.
286 if (VM.VerifyAssertions) VM._assert(rhsRegOp.getRegister().getType() == use.getRegister().getType());
287 DefUse.transferUse(use, rhsRegOp);
288 }
289 } else if (rhs.isConstant()) {
290 // NOTE: no need to incrementally update use's register list since we are going
291 // to blow it all away as soon as this loop is done.
292 for (RegisterOperand use = reg.useList; use != null; use = use.getNext()) {
293 int index = use.getIndexInInstruction();
294 use.instruction.putOperand(index, rhs.copy());
295 }
296 } else {
297 throw new OptimizingCompilerException("Simple.copyPropagation: unexpected operand type");
298 }
299 // defInstr is now dead. Remove it.
300 defInstr.remove();
301 if (rhs.isRegister()) {
302 DefUse.removeUse(rhs.asRegister());
303 }
304 ir.regpool.removeRegister(lhs.getRegister());
305 }
306 }
307 }
308
309 /**
310 * Try to find an operand that is equivalent to the result of a
311 * given phi instruction.
312 *
313 * @param phi the instruction to be simplified
314 * @return one of the phi's operands that is equivalent to the phi's result,
315 * or null if the phi can not be simplified.
316 */
317 static Operand equivalentValforPHI(Instruction phi) {
318 if (!Phi.conforms(phi)) return null;
319 // search for the first input that is different from the result
320 Operand result = Phi.getResult(phi), equiv = result;
321 int i = 0, n = Phi.getNumberOfValues(phi);
322 while (i < n) {
323 equiv = Phi.getValue(phi, i++);
324 if (!equiv.similar(result)) break;
325 }
326 // no luck if result and equiv aren't the only distinct inputs
327 while (i < n) {
328 Operand opi = Phi.getValue(phi, i++);
329 if (!opi.similar(equiv) && !opi.similar(result)) return null;
330 }
331 return equiv;
332 }
333
334 /**
335 * Perform flow-insensitive type propagation using register list
336 * information. Note: register list MUST be initialized BEFORE
337 * calling this routine.
338 *
339 * <p> Kept separate from copyPropagation loop to enable clients
340 * more flexibility.
341 *
342 * @param ir the IR in question
343 */
344 static void typePropagation(IR ir) {
345 // Use register list to enumerate register objects (FAST)
346 Register elemNext;
347 for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = elemNext) {
348 elemNext = reg.getNext();
349 // Type propagation not possible if reg has no uses
350 if (reg.useList == null) {
351 continue;
352 }
353 // Type propagation not possible if reg has no defs
354 if (reg.defList == null) {
355 continue;
356 }
357 // Do not attempt type propagation if reg has multiple defs
358 if (!reg.isSSA()) {
359 continue;
360 }
361 // Now reg has exactly one definition
362 RegisterOperand lhs = reg.defList;
363 Instruction instr = lhs.instruction;
364 Operator op = instr.operator();
365 // Type propagation not possible if lhs is not in a move instr
366 if (!op.isMove()) {
367 continue;
368 }
369 Operand rhsOp = Move.getVal(instr);
370 // Do not attempt type propagation if RHS is not a register
371 if (!(rhsOp instanceof RegisterOperand)) {
372 continue;
373 }
374 RegisterOperand rhs = (RegisterOperand) rhsOp;
375 // Propagate the type in the def
376 lhs.copyType(rhs);
377
378 // Now propagate lhs into all uses; substitute rhs.type for lhs.type
379 for (RegisterOperand use = reg.useList; use != null; use = use.getNext()) {
380 // if rhs.type is a supertype of use.type, don't do it
381 // because use.type has more detailed information
382 if (ClassLoaderProxy.includesType(rhs.getType(), use.getType()) == YES) {
383 continue;
384 }
385 // If Magic has been employed to convert an int to a reference,
386 // don't undo the effects!
387 if (rhs.getType().isPrimitiveType() && !use.getType().isPrimitiveType()) {
388 continue;
389 }
390 use.copyType(rhs);
391 }
392 }
393 }
394
395 /**
396 * Perform flow-insensitive propagation to eliminate bounds checks
397 * and arraylength for arrays with static lengths. Only useful on the HIR
398 * (because BOUNDS_CHECK is expanded in LIR into multiple instrs)
399 *
400 * <p> Note: this function incrementally maintains the register list.
401 *
402 * @param ir the IR in question
403 */
404 static void arrayPropagation(IR ir) {
405 // Use register list to enumerate register objects (FAST)
406 Register elemNext;
407 for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = elemNext) {
408 elemNext = reg.getNext();
409 if (reg.useList == null) {
410 continue;
411 }
412 if (reg.defList == null) {
413 continue;
414 }
415 if (!reg.isSSA()) {
416 continue;
417 }
418 // Now reg has exactly one definition
419 RegisterOperand lhs = reg.defList;
420 Instruction instr = lhs.instruction;
421 Operator op = instr.operator();
422 if (!(op == NEWARRAY || op == NEWARRAY_UNRESOLVED)) {
423 continue;
424 }
425 Operand sizeOp = NewArray.getSize(instr);
426 // check for an array whose length is a compile-time constant
427 // or an SSA register
428 boolean boundsCheckOK = false;
429 boolean arraylengthOK = false;
430 int size = -1;
431 if (sizeOp instanceof IntConstantOperand) {
432 size = ((IntConstantOperand) sizeOp).value;
433 boundsCheckOK = true;
434 arraylengthOK = true;
435 } else if (sizeOp instanceof RegisterOperand) {
436 if (sizeOp.asRegister().getRegister().isSSA()) {
437 arraylengthOK = true;
438 }
439 }
440 // Now propagate
441 for (RegisterOperand use = reg.useList; use != null; use = use.getNext()) {
442 Instruction i = use.instruction;
443 // bounds-check elimination
444 if (boundsCheckOK && i.getOpcode() == BOUNDS_CHECK_opcode) {
445 Operand indexOp = BoundsCheck.getIndex(i);
446 if (indexOp instanceof IntConstantOperand) {
447 if (((IntConstantOperand) indexOp).value <= size) {
448 Instruction s =
449 Move.create(GUARD_MOVE, BoundsCheck.getGuardResult(i).copyD2D(), new TrueGuardOperand());
450 s.position = i.position;
451 s.bcIndex = i.bcIndex;
452 i.insertAfter(s);
453 DefUse.updateDUForNewInstruction(s);
454 DefUse.removeInstructionAndUpdateDU(i);
455 }
456 }
457 } else if (arraylengthOK && i.getOpcode() == ARRAYLENGTH_opcode) {
458 Operand newSizeOp = sizeOp.copy();
459 RegisterOperand result = (RegisterOperand) GuardedUnary.getResult(i).copy();
460 Instruction s = Move.create(INT_MOVE, result, newSizeOp);
461 s.position = i.position;
462 s.bcIndex = i.bcIndex;
463 i.insertAfter(s);
464 DefUse.updateDUForNewInstruction(s);
465 DefUse.removeInstructionAndUpdateDU(i);
466 }
467 }
468 }
469 }
470
471 /**
472 * Simple conservative dead code elimination.
473 * An instruction is eliminated if:
474 * <ul>
475 * <li> 1. it is not a PEI, store or call
476 * <li> 2. it DEFs only registers
477 * <li> 3. all registers it DEFS are dead
478 * </ul>
479 *
480 * <p> Note: this function incrementally maintains the register list.
481 *
482 * @param ir the IR to optimize
483 */
484 static void eliminateDeadInstructions(IR ir) {
485 eliminateDeadInstructions(ir, false);
486 }
487
488 /**
489 * Simple conservative dead code elimination.
490 * An instruction is eliminated if:
491 * <ul>
492 * <li> 1. it is not a PEI, store or non-pure call
493 * <li> 2. it DEFs only registers
494 * <li> 3. all registers it DEFS are dead
495 * </ul>
496 *
497 * <p> Note: this function incrementally maintains the register list.
498 *
499 * @param ir IR to optimize
500 * @param preserveImplicitSSA if this is true, do not eliminate dead
501 * instructions that have implicit operands for heap array SSA form
502 */
503 public static void eliminateDeadInstructions(IR ir, boolean preserveImplicitSSA) {
504 // (USE BACKWARDS PASS FOR INCREASED EFFECTIVENESS)
505 ArrayList<Instruction> setCaughtExceptionInstructions = null;
506 int getCaughtExceptionInstructions = 0;
507 for (Instruction instr = ir.lastInstructionInCodeOrder(),
508 prevInstr = null; instr != null; instr = prevInstr) {
509 prevInstr = instr.prevInstructionInCodeOrder(); // cache because
510 // remove nulls next/prev fields
511 // if instr is a PEI, store, branch, or call, then it's not dead ...
512 if (instr.isPEI() || instr.isImplicitStore() || instr.isBranch() || instr.isNonPureCall()) {
513 continue;
514 }
515 if (preserveImplicitSSA && (instr.isImplicitLoad() || instr.isAllocation() || instr.operator() == PHI)) {
516 continue;
517 }
518
519 if (instr.operator() == SET_CAUGHT_EXCEPTION) {
520 if (setCaughtExceptionInstructions == null) {
521 setCaughtExceptionInstructions = new ArrayList<Instruction>();
522 }
523 setCaughtExceptionInstructions.add(instr);
524 }
525
526 // remove NOPs
527 if (instr.operator() == NOP) {
528 DefUse.removeInstructionAndUpdateDU(instr);
529 }
530
531 // remove UNINT_BEGIN/UNINT_END with nothing in between them
532 if (instr.operator() == UNINT_BEGIN) {
533 Instruction s = instr.nextInstructionInCodeOrder();
534 if (s.operator() == UNINT_END) {
535 DefUse.removeInstructionAndUpdateDU(s);
536 DefUse.removeInstructionAndUpdateDU(instr);
537 }
538 }
539
540 // remove trivial assignments
541 if (Move.conforms(instr)) {
542 Register lhs = Move.getResult(instr).asRegister().getRegister();
543 if (Move.getVal(instr).isRegister()) {
544 Register rhs = Move.getVal(instr).asRegister().getRegister();
545 if (lhs == rhs) {
546 DefUse.removeInstructionAndUpdateDU(instr);
547 continue;
548 }
549 }
550 }
551 if (instr.operator() == GET_CAUGHT_EXCEPTION) {
552 getCaughtExceptionInstructions++;
553 }
554
555 // check that all defs are to dead registers and that
556 // there is at least 1 def.
557 boolean isDead = true;
558 boolean foundRegisterDef = false;
559 for (Enumeration<Operand> defs = instr.getDefs(); defs.hasMoreElements();) {
560 Operand def = defs.nextElement();
561 if (!def.isRegister()) {
562 isDead = false;
563 break;
564 }
565 foundRegisterDef = true;
566 RegisterOperand r = def.asRegister();
567 if (r.getRegister().useList != null) {
568 isDead = false;
569 break;
570 }
571 if (r.getRegister().isPhysical()) {
572 isDead = false;
573 break;
574 }
575 }
576 if (!isDead) {
577 continue;
578 }
579 if (!foundRegisterDef) {
580 continue;
581 }
582 if (instr.operator() == GET_CAUGHT_EXCEPTION) {
583 getCaughtExceptionInstructions--;
584 }
585 // There are 1 or more register defs, but all of them are dead.
586 // Remove instr.
587 DefUse.removeInstructionAndUpdateDU(instr);
588 }
589 if (false && // temporarily disabled - see RVM-410
590 (getCaughtExceptionInstructions == 0) &&
591 (setCaughtExceptionInstructions != null)) {
592 for (Instruction instr : setCaughtExceptionInstructions) {
593 DefUse.removeInstructionAndUpdateDU(instr);
594 }
595 }
596 }
597
598 /**
599 * Perform constant folding.
600 *
601 * @param ir the IR to optimize
602 */
603 void foldConstants(IR ir) {
604 boolean recomputeRegList = false;
605 for (Instruction s = ir.firstInstructionInCodeOrder(); s != null; s = s.nextInstructionInCodeOrder()) {
606 Simplifier.DefUseEffect code = Simplifier.simplify(ir.IRStage == IR.HIR, ir.regpool, ir.options, s);
607 // If something was reduced (as opposed to folded) then its uses may
608 // be different. This happens so infrequently that it's cheaper to
609 // handle it by recomputing the DU from
610 // scratch rather than trying to do the incremental bookkeeping.
611 recomputeRegList |=
612 (code == Simplifier.DefUseEffect.MOVE_REDUCED ||
613 code == Simplifier.DefUseEffect.TRAP_REDUCED ||
614 code == Simplifier.DefUseEffect.REDUCED);
615 }
616 if (recomputeRegList) {
617 DefUse.computeDU(ir);
618 DefUse.recomputeSSA(ir);
619 }
620 }
621
622 /**
623 * Simplify branches whose operands are constants.
624 *
625 * <p> NOTE: This pass ensures that the register list is still valid after it
626 * is done.
627 *
628 * @param ir the IR to optimize
629 */
630 void simplifyConstantBranches(IR ir) {
631 boolean didSomething = false;
632 for (Enumeration<BasicBlock> e = ir.forwardBlockEnumerator(); e.hasMoreElements();) {
633 BasicBlock bb = e.nextElement();
634 didSomething |= BranchSimplifier.simplify(bb, ir);
635 }
636 if (didSomething) {
637 // killed at least one branch, cleanup the CFG removing dead code.
638 // Then recompute register list and isSSA info
639 branchOpts.perform(ir, true);
640 DefUse.computeDU(ir);
641 DefUse.recomputeSSA(ir);
642 }
643 }
644 }