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 guarentee that the targets will be iterated in monotonically decrasing
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 exisits
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 public void visitTargets(Visitor func) {
092 func.visit(target, weight);
093 }
094
095 public UnResolvedWeightedCallTargets augmentCount(MethodReference t, double v) {
096 if (target.equals(t)) {
097 weight += v;
098 return this;
099 } else {
100 UnResolvedMultiTarget ms = new UnResolvedMultiTarget();
101 ms.augmentCount(target, weight);
102 ms.augmentCount(t, v);
103 return ms;
104 }
105 }
106
107 public void decay(double rate) {
108 weight /= rate;
109 }
110
111 public double totalWeight() { return weight; }
112
113 public UnResolvedWeightedCallTargets filter(MethodReference goal) {
114 return (goal.equals(target)) ? this : null;
115 }
116 }
117
118 /**
119 * An implementation for storing a call site distribution that has multiple targets.
120 */
121 private static final class UnResolvedMultiTarget extends UnResolvedWeightedCallTargets {
122 MethodReference[] methods = new MethodReference[5];
123 float[] weights = new float[5];
124
125 public synchronized void visitTargets(Visitor func) {
126 // Typically expect elements to be "almost" sorted due to previous sorting operations.
127 // When this is true, expected time for insertion sort is O(n).
128 for (int i = 1; i < methods.length; i++) {
129 MethodReference m = methods[i];
130 if (m != null) {
131 float w = weights[i];
132 int j = i;
133 while (j > 0 && weights[j - 1] < w) {
134 methods[j] = methods[j - 1];
135 weights[j] = weights[j - 1];
136 j--;
137 }
138 methods[j] = m;
139 weights[j] = w;
140 }
141 }
142
143 for (int i = 0; i < methods.length; i++) {
144 if (methods[i] != null) {
145 func.visit(methods[i], weights[i]);
146 }
147 }
148 }
149
150 public synchronized UnResolvedWeightedCallTargets augmentCount(MethodReference t, double v) {
151 int empty = -1;
152 for (int i = 0; i < methods.length; i++) {
153 if (methods[i] != null) {
154 if (methods[i].equals(t)) {
155 weights[i] += v;
156 return this;
157 }
158 } else {
159 if (empty == -1) { empty = i; }
160 }
161 }
162
163 // New target must be added
164 if (empty == -1) {
165 // must grow arrays
166 empty = methods.length;
167 MethodReference[] newM = new MethodReference[methods.length * 2];
168 System.arraycopy(methods, 0, newM, 0, methods.length);
169 methods = newM;
170 float[] newW = new float[weights.length * 2];
171 System.arraycopy(weights, 0, newW, 0, weights.length);
172 weights = newW;
173 }
174
175 methods[empty] = t;
176 weights[empty] = (float) v;
177 return this;
178 }
179
180 public synchronized void decay(double rate) {
181 for (int i = 0; i < weights.length; i++) {
182 weights[i] /= rate;
183 }
184 }
185
186 public synchronized double totalWeight() {
187 double sum = 0;
188 for (float weight : weights) {
189 sum += weight;
190 }
191 return sum;
192 }
193
194 public synchronized UnResolvedWeightedCallTargets filter(MethodReference goal) {
195 for (int i = 0; i < methods.length; i++) {
196 if (goal.equals(methods[i])) {
197 return UnResolvedWeightedCallTargets.create(methods[i], weights[i]);
198 }
199 }
200 return null;
201 }
202 }
203 }