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.adaptive.database.callgraph;
014
015 import org.jikesrvm.classloader.RVMMethod;
016 import org.jikesrvm.runtime.RuntimeEntrypoints;
017
018 /**
019 * A collection of weighted call targets.
020 * Depending on the size of the callee set, we use different subclasses
021 * that optimize the time/space tradeoffs.
022 */
023 public abstract class WeightedCallTargets {
024
025 /**
026 * Iterate over all of the targets, evaluating the argument function on each edge.<p>
027 * NOTE: We guarantee that the targets will be iterated in monotonically decreasing
028 * edge weight. This simplifies the coding of the inlining clients that consume
029 * this information.
030 * @param func the function to evaluate on each target
031 */
032 public abstract void visitTargets(Visitor func);
033
034 /**
035 * Augment the weight associated with the argument method by 1.<p>
036 * NOTE: This method may change the representation of the target
037 * method. The caller must be sure to update their backing store of
038 * WeightedCallTargets accordingly to avoid losing the update.
039 */
040 public final WeightedCallTargets incrementCount(RVMMethod target) {
041 return augmentCount(target, 1);
042 }
043
044 /**
045 * Augment the weight associated with the argument method by the argument amount.
046 * NOTE: This method may change the representation of the target
047 * method. The caller must be sure to update their backing store of
048 * WeightedCallTargets accordingly to avoid losing the update.
049 */
050 public abstract WeightedCallTargets augmentCount(RVMMethod target, double amount);
051
052 /**
053 * Decay the weights of all call targets by the specified amount
054 * @param rate the value to decay by
055 */
056 public abstract void decay(double rate);
057
058 /**
059 * totalWeight of all call targets
060 */
061 public abstract double totalWeight();
062
063 /**
064 * @param goal RVMMethod that is the statically possible target
065 * @param isPrecise whether or not goal is a precise target, or should be
066 * interpreted as being the root of a virtual method family, any of which
067 * are statically possible.
068 * @return the filtered call targets or {@code null} if no such target exists
069 */
070 public abstract WeightedCallTargets filter(RVMMethod goal, boolean isPrecise);
071
072 public static WeightedCallTargets create(RVMMethod target, double weight) {
073 return new SingleTarget(target, weight);
074 }
075
076 /**
077 * Used by visitTargets
078 */
079 public interface Visitor {
080 void visit(RVMMethod target, double weight);
081 }
082
083 /**
084 * An implementation for storing a call site distribution that has a single target.
085 */
086 private static final class SingleTarget extends WeightedCallTargets {
087 private final RVMMethod target;
088 private float weight;
089
090 SingleTarget(RVMMethod t, double w) {
091 target = t;
092 weight = (float) w;
093 }
094
095 @Override
096 public void visitTargets(Visitor func) {
097 func.visit(target, weight);
098 }
099
100 @Override
101 public WeightedCallTargets augmentCount(RVMMethod t, double v) {
102 if (target.equals(t)) {
103 weight += v;
104 return this;
105 } else {
106 MultiTarget ms = new MultiTarget();
107 ms.augmentCount(target, weight);
108 ms.augmentCount(t, v);
109 return ms;
110 }
111 }
112
113 @Override
114 public void decay(double rate) {
115 weight /= rate;
116 }
117
118 @Override
119 public double totalWeight() { return weight; }
120
121 @Override
122 public WeightedCallTargets filter(RVMMethod goal, boolean isPrecise) {
123 if (isPrecise) {
124 return (goal.equals(target)) ? this : null;
125 } else {
126 if (goal.equals(target)) {
127 return this;
128 }
129 if (RuntimeEntrypoints.isAssignableWith(goal.getDeclaringClass(), target.getDeclaringClass())) {
130 return this;
131 } else {
132 return null;
133 }
134 }
135 }
136 }
137
138 /**
139 * An implementation for storing a call site distribution that has multiple targets.
140 */
141 private static final class MultiTarget extends WeightedCallTargets {
142 RVMMethod[] methods = new RVMMethod[5];
143 float[] weights = new float[5];
144
145 @Override
146 public synchronized void visitTargets(Visitor func) {
147 // Typically expect elements to be "almost" sorted due to previous sorting operations.
148 // When this is true, expected time for insertion sort is O(n).
149 for (int i = 1; i < methods.length; i++) {
150 RVMMethod m = methods[i];
151 if (m != null) {
152 float w = weights[i];
153 int j = i;
154 while (j > 0 && weights[j - 1] < w) {
155 methods[j] = methods[j - 1];
156 weights[j] = weights[j - 1];
157 j--;
158 }
159 methods[j] = m;
160 weights[j] = w;
161 }
162 }
163
164 for (int i = 0; i < methods.length; i++) {
165 if (methods[i] != null) {
166 func.visit(methods[i], weights[i]);
167 }
168 }
169 }
170
171 @Override
172 public synchronized WeightedCallTargets augmentCount(RVMMethod t, double v) {
173 int empty = -1;
174 for (int i = 0; i < methods.length; i++) {
175 if (methods[i] != null) {
176 if (methods[i].equals(t)) {
177 weights[i] += v;
178 return this;
179 }
180 } else {
181 if (empty == -1) { empty = i; }
182 }
183 }
184
185 // New target must be added
186 if (empty == -1) {
187 // must grow arrays
188 empty = methods.length;
189 RVMMethod[] newM = new RVMMethod[methods.length * 2];
190 System.arraycopy(methods, 0, newM, 0, methods.length);
191 methods = newM;
192 float[] newW = new float[weights.length * 2];
193 System.arraycopy(weights, 0, newW, 0, weights.length);
194 weights = newW;
195 }
196
197 methods[empty] = t;
198 weights[empty] = (float) v;
199 return this;
200 }
201
202 @Override
203 public synchronized void decay(double rate) {
204 for (int i = 0; i < weights.length; i++) {
205 weights[i] /= rate;
206 }
207 }
208
209 @Override
210 public synchronized double totalWeight() {
211 double sum = 0;
212 for (float weight : weights) {
213 sum += weight;
214 }
215 return sum;
216 }
217
218 @Override
219 public synchronized WeightedCallTargets filter(RVMMethod goal, boolean isPrecise) {
220 if (isPrecise) {
221 for (int i = 0; i < methods.length; i++) {
222 if (goal.equals(methods[i])) {
223 return WeightedCallTargets.create(methods[i], weights[i]);
224 }
225 }
226 return null;
227 } else {
228 int matchCount = 0;
229 int mismatchCount = 0;
230 for (RVMMethod method : methods) {
231 if (method != null) {
232 if (RuntimeEntrypoints.isAssignableWith(goal.getDeclaringClass(), method.getDeclaringClass())) {
233 matchCount++;
234 } else {
235 mismatchCount++;
236 }
237 }
238 }
239 if (mismatchCount == 0) {
240 return this;
241 }
242 if (matchCount == 0) {
243 return null;
244 }
245
246 MultiTarget filtered = new MultiTarget();
247 for (int i=0; i<methods.length; i++) {
248 RVMMethod method = methods[i];
249 if (method != null && RuntimeEntrypoints.isAssignableWith(goal.getDeclaringClass(), method.getDeclaringClass())) {
250 filtered.augmentCount(method, weights[i]);
251 }
252 }
253 return filtered;
254 }
255 }
256 }
257 }