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