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(VM.NOT_REACHED); }
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
086 switch (code) {
087 case JBC_ifeq:
088 case JBC_ifne:
089 case JBC_iflt:
090 case JBC_ifge:
091 case JBC_ifgt:
092 case JBC_ifle:
093 case JBC_if_icmpeq:
094 case JBC_if_icmpne:
095 case JBC_if_icmplt:
096 case JBC_if_icmpge:
097 case JBC_if_icmpgt:
098 case JBC_if_icmple:
099 case JBC_if_acmpeq:
100 case JBC_if_acmpne:
101 case JBC_ifnull:
102 case JBC_ifnonnull: {
103 if (countIdx >= cs.length) {
104 VM.sysWriteln("Warning: control flow instance encountered outside scope of available edge count array");
105 break;
106 }
107 int yea = cs[countIdx + EdgeCounts.TAKEN];
108 int nea = cs[countIdx + EdgeCounts.NOT_TAKEN];
109 int offset = bcodes.getBranchOffset();
110 boolean backwards = offset < 0;
111 countIdx += 2;
112 data[dataIdx++] = new ConditionalBranchProfile(bcIndex, yea, nea, backwards);
113 break;
114 }
115
116 case JBC_tableswitch: {
117 if (countIdx >= cs.length) {
118 VM.sysWriteln("Warning: control flow instance encountered outside scope of available edge count array");
119 break;
120 }
121 bcodes.alignSwitch();
122 bcodes.getDefaultSwitchOffset();
123 int low = bcodes.getLowSwitchValue();
124 int high = bcodes.getHighSwitchValue();
125 int n = high - low + 1;
126 data[dataIdx++] = new SwitchBranchProfile(bcIndex, cs, countIdx, n + 1);
127 countIdx += n + 1;
128 bcodes.skipTableSwitchOffsets(n);
129 break;
130 }
131
132 case JBC_lookupswitch: {
133 if (countIdx >= cs.length) {
134 VM.sysWriteln("Warning: control flow instance encountered outside scope of available edge count array");
135 break;
136 }
137 bcodes.alignSwitch();
138 bcodes.getDefaultSwitchOffset();
139 int numPairs = bcodes.getSwitchLength();
140 data[dataIdx++] = new SwitchBranchProfile(bcIndex, cs, countIdx, numPairs + 1);
141 countIdx += numPairs + 1;
142 bcodes.skipLookupSwitchPairs(numPairs);
143 break;
144 }
145
146 default:
147 bcodes.skipInstruction();
148 break;
149 }
150 }
151
152 // Make sure we are in sync
153 if (VM.VerifyAssertions) VM._assert(countIdx == cs.length);
154
155 if (dataIdx != data.length) {
156 // We had a switch statment; shrink the array.
157 BranchProfile[] newData = new BranchProfile[dataIdx];
158 for (int i = 0; i < dataIdx; i++) {
159 newData[i] = data[i];
160 }
161 data = newData;
162 }
163 this.data = data;
164 }
165 }