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.
027 * NOTE: We guarentee that the targets will be iterated in monotonically decrasing
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.
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 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 public void visitTargets(Visitor func) {
096 func.visit(target, weight);
097 }
098
099 public WeightedCallTargets augmentCount(RVMMethod t, double v) {
100 if (target.equals(t)) {
101 weight += v;
102 return this;
103 } else {
104 MultiTarget ms = new MultiTarget();
105 ms.augmentCount(target, weight);
106 ms.augmentCount(t, v);
107 return ms;
108 }
109 }
110
111 public void decay(double rate) {
112 weight /= rate;
113 }
114
115 public double totalWeight() { return weight; }
116
117 public WeightedCallTargets filter(RVMMethod goal, boolean isPrecise) {
118 if (isPrecise) {
119 return (goal.equals(target)) ? this : null;
120 } else {
121 if (goal.equals(target)) {
122 return this;
123 }
124 if (RuntimeEntrypoints.isAssignableWith(goal.getDeclaringClass(), target.getDeclaringClass())) {
125 return this;
126 } else {
127 return null;
128 }
129 }
130 }
131 }
132
133 /**
134 * An implementation for storing a call site distribution that has multiple targets.
135 */
136 private static final class MultiTarget extends WeightedCallTargets {
137 RVMMethod[] methods = new RVMMethod[5];
138 float[] weights = new float[5];
139
140 public synchronized void visitTargets(Visitor func) {
141 // Typically expect elements to be "almost" sorted due to previous sorting operations.
142 // When this is true, expected time for insertion sort is O(n).
143 for (int i = 1; i < methods.length; i++) {
144 RVMMethod m = methods[i];
145 if (m != null) {
146 float w = weights[i];
147 int j = i;
148 while (j > 0 && weights[j - 1] < w) {
149 methods[j] = methods[j - 1];
150 weights[j] = weights[j - 1];
151 j--;
152 }
153 methods[j] = m;
154 weights[j] = w;
155 }
156 }
157
158 for (int i = 0; i < methods.length; i++) {
159 if (methods[i] != null) {
160 func.visit(methods[i], weights[i]);
161 }
162 }
163 }
164
165 public synchronized WeightedCallTargets augmentCount(RVMMethod t, double v) {
166 int empty = -1;
167 for (int i = 0; i < methods.length; i++) {
168 if (methods[i] != null) {
169 if (methods[i].equals(t)) {
170 weights[i] += v;
171 return this;
172 }
173 } else {
174 if (empty == -1) { empty = i; }
175 }
176 }
177
178 // New target must be added
179 if (empty == -1) {
180 // must grow arrays
181 empty = methods.length;
182 RVMMethod[] newM = new RVMMethod[methods.length * 2];
183 System.arraycopy(methods, 0, newM, 0, methods.length);
184 methods = newM;
185 float[] newW = new float[weights.length * 2];
186 System.arraycopy(weights, 0, newW, 0, weights.length);
187 weights = newW;
188 }
189
190 methods[empty] = t;
191 weights[empty] = (float) v;
192 return this;
193 }
194
195 public synchronized void decay(double rate) {
196 for (int i = 0; i < weights.length; i++) {
197 weights[i] /= rate;
198 }
199 }
200
201 public synchronized double totalWeight() {
202 double sum = 0;
203 for (float weight : weights) {
204 sum += weight;
205 }
206 return sum;
207 }
208
209 public synchronized WeightedCallTargets filter(RVMMethod goal, boolean isPrecise) {
210 if (isPrecise) {
211 for (int i = 0; i < methods.length; i++) {
212 if (goal.equals(methods[i])) {
213 return WeightedCallTargets.create(methods[i], weights[i]);
214 }
215 }
216 return null;
217 } else {
218 int matchCount = 0;
219 int mismatchCount = 0;
220 for (RVMMethod method : methods) {
221 if (method != null) {
222 if (RuntimeEntrypoints.isAssignableWith(goal.getDeclaringClass(), method.getDeclaringClass())) {
223 matchCount++;
224 } else {
225 mismatchCount++;
226 }
227 }
228 }
229 if (mismatchCount == 0) {
230 return this;
231 }
232 if (matchCount == 0) {
233 return null;
234 }
235
236 MultiTarget filtered = new MultiTarget();
237 for (int i=0; i<methods.length; i++) {
238 RVMMethod method = methods[i];
239 if (method != null && RuntimeEntrypoints.isAssignableWith(goal.getDeclaringClass(), method.getDeclaringClass())) {
240 filtered.augmentCount(method, weights[i]);
241 }
242 }
243 return filtered;
244 }
245 }
246 }
247 }