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;
014
015import java.util.Enumeration;
016
017import org.jikesrvm.classloader.RVMMethod;
018import org.jikesrvm.compilers.opt.driver.CompilerPhase;
019import org.jikesrvm.compilers.opt.ir.Athrow;
020import org.jikesrvm.compilers.opt.ir.BasicBlock;
021import org.jikesrvm.compilers.opt.ir.Call;
022import org.jikesrvm.compilers.opt.ir.IR;
023import org.jikesrvm.compilers.opt.ir.IfCmp;
024import org.jikesrvm.compilers.opt.ir.Instruction;
025import org.jikesrvm.compilers.opt.ir.Trap;
026import org.jikesrvm.compilers.opt.ir.operand.BranchProfileOperand;
027import 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 */
033public 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}