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.util;
014
015 import org.jikesrvm.classloader.MethodReference;
016
017 /**
018 * A collection of weighted call targets. In some case we can't resolve a
019 * class too early in the process. So we recorded it as unresolved and
020 * resolve the method when the method is being compiled.
021 */
022 public abstract class UnResolvedWeightedCallTargets {
023
024 /**
025 * Iterate over all of the targets, evaluating the argument function on each edge.
026 * NOTE: We guarantee that the targets will be iterated in monotonically decreasing
027 * edge weight. This simplifies the coding of the inlining clients that consume
028 * this information.
029 * @param func the function to evaluate on each target
030 */
031 public abstract void visitTargets(Visitor func);
032
033 /**
034 * Augment the weight associated with the argument method by 1.
035 * NOTE: This method may change the representation of the target
036 * method. The caller must be sure to update their backing store of
037 * UnResolvedWeightedCallTargets accordingly to avoid losing the update.
038 */
039 public final UnResolvedWeightedCallTargets incrementCount(MethodReference target) {
040 return augmentCount(target, 1);
041 }
042
043 /**
044 * Augment the weight associated with the argument method by the argument amount.
045 * NOTE: This method may change the representation of the target
046 * method. The caller must be sure to update their backing store of
047 * UnResolvedWeightedCallTargets accordingly to avoid losing the update.
048 */
049 public abstract UnResolvedWeightedCallTargets augmentCount(MethodReference target, double amount);
050
051 /**
052 * Decay the weights of all call targets by the specified amount
053 * @param rate the value to decay by
054 */
055 public abstract void decay(double rate);
056
057 /**
058 * totalWeight of all call targets
059 */
060 public abstract double totalWeight();
061
062 /**
063 * @param goal MethodReference that is the only statically possible target
064 * @return the filtered call targets or null if no such target exists
065 */
066 public abstract UnResolvedWeightedCallTargets filter(MethodReference goal);
067
068 public static UnResolvedWeightedCallTargets create(MethodReference target, double weight) {
069 return new UnResolvedSingleTarget(target, weight);
070 }
071
072 /**
073 * Used by visitTargets
074 */
075 public interface Visitor {
076 void visit(MethodReference target, double weight);
077 }
078
079 /**
080 * An implementation for storing a call site distribution that has a single target.
081 */
082 private static final class UnResolvedSingleTarget extends UnResolvedWeightedCallTargets {
083 private final MethodReference target;
084 private float weight;
085
086 UnResolvedSingleTarget(MethodReference t, double w) {
087 target = t;
088 weight = (float) w;
089 }
090
091 @Override
092 public void visitTargets(Visitor func) {
093 func.visit(target, weight);
094 }
095
096 @Override
097 public UnResolvedWeightedCallTargets augmentCount(MethodReference t, double v) {
098 if (target.equals(t)) {
099 weight += v;
100 return this;
101 } else {
102 UnResolvedMultiTarget ms = new UnResolvedMultiTarget();
103 ms.augmentCount(target, weight);
104 ms.augmentCount(t, v);
105 return ms;
106 }
107 }
108
109 @Override
110 public void decay(double rate) {
111 weight /= rate;
112 }
113
114 @Override
115 public double totalWeight() { return weight; }
116
117 @Override
118 public UnResolvedWeightedCallTargets filter(MethodReference goal) {
119 return (goal.equals(target)) ? this : null;
120 }
121 }
122
123 /**
124 * An implementation for storing a call site distribution that has multiple targets.
125 */
126 private static final class UnResolvedMultiTarget extends UnResolvedWeightedCallTargets {
127 MethodReference[] methods = new MethodReference[5];
128 float[] weights = new float[5];
129
130 @Override
131 public synchronized void visitTargets(Visitor func) {
132 // Typically expect elements to be "almost" sorted due to previous sorting operations.
133 // When this is true, expected time for insertion sort is O(n).
134 for (int i = 1; i < methods.length; i++) {
135 MethodReference m = methods[i];
136 if (m != null) {
137 float w = weights[i];
138 int j = i;
139 while (j > 0 && weights[j - 1] < w) {
140 methods[j] = methods[j - 1];
141 weights[j] = weights[j - 1];
142 j--;
143 }
144 methods[j] = m;
145 weights[j] = w;
146 }
147 }
148
149 for (int i = 0; i < methods.length; i++) {
150 if (methods[i] != null) {
151 func.visit(methods[i], weights[i]);
152 }
153 }
154 }
155
156 @Override
157 public synchronized UnResolvedWeightedCallTargets augmentCount(MethodReference t, double v) {
158 int empty = -1;
159 for (int i = 0; i < methods.length; i++) {
160 if (methods[i] != null) {
161 if (methods[i].equals(t)) {
162 weights[i] += v;
163 return this;
164 }
165 } else {
166 if (empty == -1) { empty = i; }
167 }
168 }
169
170 // New target must be added
171 if (empty == -1) {
172 // must grow arrays
173 empty = methods.length;
174 MethodReference[] newM = new MethodReference[methods.length * 2];
175 System.arraycopy(methods, 0, newM, 0, methods.length);
176 methods = newM;
177 float[] newW = new float[weights.length * 2];
178 System.arraycopy(weights, 0, newW, 0, weights.length);
179 weights = newW;
180 }
181
182 methods[empty] = t;
183 weights[empty] = (float) v;
184 return this;
185 }
186
187 @Override
188 public synchronized void decay(double rate) {
189 for (int i = 0; i < weights.length; i++) {
190 weights[i] /= rate;
191 }
192 }
193
194 @Override
195 public synchronized double totalWeight() {
196 double sum = 0;
197 for (float weight : weights) {
198 sum += weight;
199 }
200 return sum;
201 }
202
203 @Override
204 public synchronized UnResolvedWeightedCallTargets filter(MethodReference goal) {
205 for (int i = 0; i < methods.length; i++) {
206 if (goal.equals(methods[i])) {
207 return UnResolvedWeightedCallTargets.create(methods[i], weights[i]);
208 }
209 }
210 return null;
211 }
212 }
213 }