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 java.util.Enumeration;
016
017 import org.jikesrvm.classloader.RVMMethod;
018 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
019 import org.jikesrvm.compilers.opt.ir.Athrow;
020 import org.jikesrvm.compilers.opt.ir.BasicBlock;
021 import org.jikesrvm.compilers.opt.ir.Call;
022 import org.jikesrvm.compilers.opt.ir.IR;
023 import org.jikesrvm.compilers.opt.ir.IfCmp;
024 import org.jikesrvm.compilers.opt.ir.Instruction;
025 import org.jikesrvm.compilers.opt.ir.Trap;
026 import org.jikesrvm.compilers.opt.ir.operand.BranchProfileOperand;
027 import org.jikesrvm.compilers.opt.ir.operand.MethodOperand;
028
029 /**
030 * This pass adjusts branch probabilities derived from static estimates
031 * to account for blocks that are statically guessed to be infrequent.
032 */
033 public class AdjustBranchProbabilities extends CompilerPhase {
034
035 @Override
036 public final String getName() {
037 return "Adjust Branch Probabilities";
038 }
039
040 @Override
041 public final CompilerPhase newExecution(IR ir) {
042 return this;
043 }
044
045 /**
046 * Simplistic adjustment of branch probabilities.
047 * The main target of this pass is to detect idioms like
048 * <pre>
049 * if (P) { infrequent block }
050 * if (P) { } else { infrequent block }
051 * </pre>
052 * that are introduced by ExpandRuntimeServices.
053 * <p>
054 * Key idea: If a block is infrequent then make sure that
055 * any conditional branch that targets/avoids the block
056 * does not have 0.5 as its branch probability.
057 *
058 * @param ir the governing IR
059 */
060 @Override
061 public final void perform(IR ir) {
062 for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
063 BasicBlock target = e.nextElement();
064 if (findInfrequentInstruction(target)) {
065 blockLoop:
066 for (Enumeration<BasicBlock> sources = target.getIn(); sources.hasMoreElements();) {
067 BasicBlock source = sources.nextElement();
068 // Found an edge to an infrequent block.
069 // Look to see if there is a conditional branch that we need to adjust
070 Instruction condBranch = null;
071 for (Enumeration<Instruction> ie = source.enumerateBranchInstructions(); ie.hasMoreElements();) {
072 Instruction s = ie.nextElement();
073 if (IfCmp.conforms(s) && IfCmp.getBranchProfile(s).takenProbability == 0.5f) {
074 if (condBranch == null) {
075 condBranch = s;
076 } else {
077 continue blockLoop; // branching is too complicated.
078 }
079 }
080 }
081 if (condBranch != null) {
082 BasicBlock notTaken = source.getNotTakenNextBlock();
083 if (notTaken == target) {
084 // The not taken branch is the unlikely one, make the branch be taken always.
085 IfCmp.setBranchProfile(condBranch, BranchProfileOperand.always());
086 } else {
087 // The taken branch is the unlikely one,
088 IfCmp.setBranchProfile(condBranch, BranchProfileOperand.never());
089 }
090 }
091 }
092 }
093 }
094 }
095
096 private boolean findInfrequentInstruction(BasicBlock bb) {
097 for (Enumeration<Instruction> e2 = bb.forwardRealInstrEnumerator(); e2.hasMoreElements();) {
098 Instruction s = e2.nextElement();
099 if (Call.conforms(s)) {
100 MethodOperand op = Call.getMethod(s);
101 if (op != null) {
102 RVMMethod target = op.getTarget();
103 if (target != null && target.hasNoInlinePragma()) {
104 return true;
105 }
106 }
107 } else if (Athrow.conforms(s) || Trap.conforms(s)) {
108 return true;
109 }
110 }
111 return false;
112 }
113 }