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 */ 013package org.jikesrvm.adaptive.util; 014 015import 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 */ 022public 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 * @param target the target method 040 * @return the object representing the method's targets 041 */ 042 public final UnResolvedWeightedCallTargets incrementCount(MethodReference target) { 043 return augmentCount(target, 1); 044 } 045 046 /** 047 * Augment the weight associated with the argument method by the argument amount. 048 * NOTE: This method may change the representation of the target 049 * method. The caller must be sure to update their backing store of 050 * UnResolvedWeightedCallTargets accordingly to avoid losing the update. 051 * 052 * @param target the target method 053 * @param amount the amount to add 054 * @return the object representing the method's targets 055 */ 056 public abstract UnResolvedWeightedCallTargets augmentCount(MethodReference target, double amount); 057 058 /** 059 * Decay the weights of all call targets by the specified amount 060 * @param rate the value to decay by 061 */ 062 public abstract void decay(double rate); 063 064 /** 065 * @return total weight of all call targets 066 */ 067 public abstract double totalWeight(); 068 069 /** 070 * @param goal MethodReference that is the only statically possible target 071 * @return the filtered call targets or {@code null} if no such target exists 072 */ 073 public abstract UnResolvedWeightedCallTargets filter(MethodReference goal); 074 075 public static UnResolvedWeightedCallTargets create(MethodReference target, double weight) { 076 return new UnResolvedSingleTarget(target, weight); 077 } 078 079 /** 080 * Used by visitTargets 081 */ 082 public interface Visitor { 083 void visit(MethodReference target, double weight); 084 } 085 086 /** 087 * An implementation for storing a call site distribution that has a single target. 088 */ 089 private static final class UnResolvedSingleTarget extends UnResolvedWeightedCallTargets { 090 private final MethodReference target; 091 private float weight; 092 093 UnResolvedSingleTarget(MethodReference t, double w) { 094 target = t; 095 weight = (float) w; 096 } 097 098 @Override 099 public void visitTargets(Visitor func) { 100 func.visit(target, weight); 101 } 102 103 @Override 104 public UnResolvedWeightedCallTargets augmentCount(MethodReference t, double v) { 105 if (target.equals(t)) { 106 weight += v; 107 return this; 108 } else { 109 UnResolvedMultiTarget ms = new UnResolvedMultiTarget(); 110 ms.augmentCount(target, weight); 111 ms.augmentCount(t, v); 112 return ms; 113 } 114 } 115 116 @Override 117 public void decay(double rate) { 118 weight /= rate; 119 } 120 121 @Override 122 public double totalWeight() { 123 return weight; 124 } 125 126 @Override 127 public UnResolvedWeightedCallTargets filter(MethodReference goal) { 128 return (goal.equals(target)) ? this : null; 129 } 130 } 131 132 /** 133 * An implementation for storing a call site distribution that has multiple targets. 134 */ 135 private static final class UnResolvedMultiTarget extends UnResolvedWeightedCallTargets { 136 MethodReference[] methods = new MethodReference[5]; 137 float[] weights = new float[5]; 138 139 @Override 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 MethodReference 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 @Override 166 public synchronized UnResolvedWeightedCallTargets augmentCount(MethodReference t, double v) { 167 int empty = -1; 168 for (int i = 0; i < methods.length; i++) { 169 if (methods[i] != null) { 170 if (methods[i].equals(t)) { 171 weights[i] += v; 172 return this; 173 } 174 } else { 175 if (empty == -1) { 176 empty = i; 177 } 178 } 179 } 180 181 // New target must be added 182 if (empty == -1) { 183 // must grow arrays 184 empty = methods.length; 185 MethodReference[] newM = new MethodReference[methods.length * 2]; 186 System.arraycopy(methods, 0, newM, 0, methods.length); 187 methods = newM; 188 float[] newW = new float[weights.length * 2]; 189 System.arraycopy(weights, 0, newW, 0, weights.length); 190 weights = newW; 191 } 192 193 methods[empty] = t; 194 weights[empty] = (float) v; 195 return this; 196 } 197 198 @Override 199 public synchronized void decay(double rate) { 200 for (int i = 0; i < weights.length; i++) { 201 weights[i] /= rate; 202 } 203 } 204 205 @Override 206 public synchronized double totalWeight() { 207 double sum = 0; 208 for (float weight : weights) { 209 sum += weight; 210 } 211 return sum; 212 } 213 214 @Override 215 public synchronized UnResolvedWeightedCallTargets filter(MethodReference goal) { 216 for (int i = 0; i < methods.length; i++) { 217 if (goal.equals(methods[i])) { 218 return UnResolvedWeightedCallTargets.create(methods[i], weights[i]); 219 } 220 } 221 return null; 222 } 223 } 224}