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.baseline;
014
015import static org.jikesrvm.classloader.BytecodeConstants.JBC_if_acmpeq;
016import static org.jikesrvm.classloader.BytecodeConstants.JBC_if_acmpne;
017import static org.jikesrvm.classloader.BytecodeConstants.JBC_if_icmpeq;
018import static org.jikesrvm.classloader.BytecodeConstants.JBC_if_icmpge;
019import static org.jikesrvm.classloader.BytecodeConstants.JBC_if_icmpgt;
020import static org.jikesrvm.classloader.BytecodeConstants.JBC_if_icmple;
021import static org.jikesrvm.classloader.BytecodeConstants.JBC_if_icmplt;
022import static org.jikesrvm.classloader.BytecodeConstants.JBC_if_icmpne;
023import static org.jikesrvm.classloader.BytecodeConstants.JBC_ifeq;
024import static org.jikesrvm.classloader.BytecodeConstants.JBC_ifge;
025import static org.jikesrvm.classloader.BytecodeConstants.JBC_ifgt;
026import static org.jikesrvm.classloader.BytecodeConstants.JBC_ifle;
027import static org.jikesrvm.classloader.BytecodeConstants.JBC_iflt;
028import static org.jikesrvm.classloader.BytecodeConstants.JBC_ifne;
029import static org.jikesrvm.classloader.BytecodeConstants.JBC_ifnonnull;
030import static org.jikesrvm.classloader.BytecodeConstants.JBC_ifnull;
031import static org.jikesrvm.classloader.BytecodeConstants.JBC_lookupswitch;
032import static org.jikesrvm.classloader.BytecodeConstants.JBC_tableswitch;
033
034import org.jikesrvm.VM;
035import org.jikesrvm.classloader.BytecodeStream;
036import org.jikesrvm.classloader.NormalMethod;
037
038
039/**
040 * Profile data for all conditional branches (including switches)
041 * of a single RVMMethod.
042 *
043 * @see EdgeCounts
044 */
045public final class BranchProfiles {
046  /** Method containing counters */
047  private final NormalMethod method;
048  /** Number of counters */
049  private final int numCounters;
050  /** Branch profile for each profiled bytecode */
051  private final BranchProfile[] data;
052
053  /**
054   * Find the BranchProfile for a given bytecode index in the BranchProfile array
055   * @param bcIndex the bytecode index of the branch instruction
056   * @return the desired BranchProfile, or null if it cannot be found.
057   */
058  public BranchProfile getEntry(int bcIndex) {
059    int low = 0;
060    int high = data.length - 1;
061    while (true) {
062      int mid = (low + high) >> 1;
063      int bci = data[mid].getBytecodeIndex();
064      if (bci == bcIndex) {
065        return data[mid];
066      }
067      if (low >= high) {
068        // search failed
069        if (VM.VerifyAssertions) {
070          VM._assert(VM.NOT_REACHED);
071        }
072        return null;
073      }
074      if (bci > bcIndex) {
075        high = mid - 1;
076      } else {
077        low = mid + 1;
078      }
079    }
080  }
081
082  public void print(java.io.PrintStream ps) {
083    ps.println("M " + numCounters + " " + method.getMemberRef());
084    for (BranchProfile profile : data) {
085      ps.println("\t" + profile);
086    }
087  }
088
089  BranchProfiles(NormalMethod m, int[] cs) {
090    method = m;
091    numCounters = cs.length;
092
093    // Originally we only allocate half of the number of edges for branch
094    // profiles, like data = new BranchProfile[cs.length/2]
095    // The conditional branch, tableswitch and lookupswitch all have at
096    // least two edges, supposingly. Then we found that the lookupswitch
097    // bytecode could have only one edge, so the number of branch profiles
098    // is not necessarily less than half of the number of edges.
099    BranchProfile[] data = new BranchProfile[cs.length];
100    BytecodeStream bcodes = m.getBytecodes();
101    int dataIdx = 0;
102    int countIdx = 0;
103
104    // We didn't record the bytecode index in the profile data to record space.
105    // Therefore we must now recover that information.
106    // We exploit the fact that the baseline compiler generates code in
107    // a linear pass over the bytecodes to make this possible.
108    while (bcodes.hasMoreBytecodes()) {
109      int bcIndex = bcodes.index();
110      int code = bcodes.nextInstruction();
111
112      switch (code) {
113        case JBC_ifeq:
114        case JBC_ifne:
115        case JBC_iflt:
116        case JBC_ifge:
117        case JBC_ifgt:
118        case JBC_ifle:
119        case JBC_if_icmpeq:
120        case JBC_if_icmpne:
121        case JBC_if_icmplt:
122        case JBC_if_icmpge:
123        case JBC_if_icmpgt:
124        case JBC_if_icmple:
125        case JBC_if_acmpeq:
126        case JBC_if_acmpne:
127        case JBC_ifnull:
128        case JBC_ifnonnull: {
129          if (countIdx >= cs.length) {
130            VM.sysWriteln("Warning: control flow instance encountered outside scope of available edge count array");
131            break;
132          }
133          int yea = cs[countIdx + EdgeCounts.TAKEN];
134          int nea = cs[countIdx + EdgeCounts.NOT_TAKEN];
135          int offset = bcodes.getBranchOffset();
136          boolean backwards = offset < 0;
137          countIdx += 2;
138          data[dataIdx++] = new ConditionalBranchProfile(bcIndex, yea, nea, backwards);
139          break;
140        }
141
142        case JBC_tableswitch: {
143          if (countIdx >= cs.length) {
144            VM.sysWriteln("Warning: control flow instance encountered outside scope of available edge count array");
145            break;
146          }
147          bcodes.alignSwitch();
148          bcodes.getDefaultSwitchOffset();
149          int low = bcodes.getLowSwitchValue();
150          int high = bcodes.getHighSwitchValue();
151          int n = high - low + 1;
152          data[dataIdx++] = new SwitchBranchProfile(bcIndex, cs, countIdx, n + 1);
153          countIdx += n + 1;
154          bcodes.skipTableSwitchOffsets(n);
155          break;
156        }
157
158        case JBC_lookupswitch: {
159          if (countIdx >= cs.length) {
160            VM.sysWriteln("Warning: control flow instance encountered outside scope of available edge count array");
161            break;
162          }
163          bcodes.alignSwitch();
164          bcodes.getDefaultSwitchOffset();
165          int numPairs = bcodes.getSwitchLength();
166          data[dataIdx++] = new SwitchBranchProfile(bcIndex, cs, countIdx, numPairs + 1);
167          countIdx += numPairs + 1;
168          bcodes.skipLookupSwitchPairs(numPairs);
169          break;
170        }
171
172        default:
173          bcodes.skipInstruction();
174          break;
175      }
176    }
177
178    // Make sure we are in sync
179    if (VM.VerifyAssertions) VM._assert(countIdx == cs.length);
180
181    if (dataIdx != data.length) {
182      // We had a switch statment; shrink the array.
183      BranchProfile[] newData = new BranchProfile[dataIdx];
184      for (int i = 0; i < dataIdx; i++) {
185        newData[i] = data[i];
186      }
187      data = newData;
188    }
189    this.data = data;
190  }
191}