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