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.compilers.opt.inlining;
014
015 import java.util.Iterator;
016 import org.jikesrvm.classloader.RVMClass;
017 import org.jikesrvm.classloader.RVMMethod;
018 import org.jikesrvm.util.HashMapRVM;
019 import org.jikesrvm.util.HashSetRVM;
020
021 /**
022 * This class holds the dependencies that define invalidation
023 * requirements for the opt compiled methods.
024 *
025 * <p> Currently we only support 2 kinds of dependencies:
026 * The set of compiled method id's that depend on a RVMMethod
027 * not being overridden.
028 * The set of compiled method id's that depend on a RVMClass
029 * having no subclasses
030 *
031 * <p> Note we track by compiled method ids instead of pointers to
032 * compiled methods because we don't have weak pointers.
033 * We don't want the invalidaton database to keep code alive!
034 * This would be an ideal use of weak references if we had them.
035 *
036 * <p> TODO: In the future, we should think about implementing a general
037 * dependency mechanism.
038 * See Chambers, Dean, Grove in ICSE-17 (1995) for one possible design
039 * and pointers to related work.
040 */
041 public final class InvalidationDatabase {
042
043 /**
044 * A mapping from RVMMethod to MethodSet: holds the set of methods which
045 * depend on a particular method being "final"
046 */
047 private final HashMapRVM<RVMMethod, MethodSet> nonOverriddenHash =
048 new HashMapRVM<RVMMethod, MethodSet>();
049
050 /**
051 * A mapping from RVMClass to MethodSet: holds the set of methods which
052 * depend on a particular class being "final"
053 */
054 private final HashMapRVM<RVMClass, MethodSet> noSubclassHash =
055 new HashMapRVM<RVMClass, MethodSet>();
056
057 /////////////////////
058 // (1) Dependency on a particular RVMMethod not being overridden.
059 /////////////////////
060
061 /**
062 * Returns an iteration of CMID's (compiled method ids) that are dependent
063 * on the argument RVMMethod not being overridden. If there are no dependent
064 * methods, {@code null} will be returned.<p>
065 *
066 * NOTE: {@code null} is used instead of {@code EmptyIterator.getInstance}
067 * as part of delicate dance to avoid recursive classloading.
068 *
069 * @param m a method that can be overridden
070 * @return an iterator of CMIDs or {@code null}
071 */
072 public Iterator<Integer> invalidatedByOverriddenMethod(RVMMethod m) {
073 MethodSet s = nonOverriddenHash.get(m);
074 return (s == null) ? null : s.iterator();
075 }
076
077 /**
078 * Record that if a particular RVMMethod method is ever overridden, then
079 * the CompiledMethod encoded by the cmid must be invalidated.
080 */
081 public void addNotOverriddenDependency(RVMMethod source, int dependent_cmid) {
082 MethodSet s = findOrCreateMethodSet(nonOverriddenHash, source);
083 s.add(dependent_cmid);
084 }
085
086 /**
087 * Delete a NotOverriddenDependency.
088 * No effect if the dependency doesn't exist..
089 */
090 public void removeNotOverriddenDependency(RVMMethod source, int dependent_cmid) {
091 MethodSet s = nonOverriddenHash.get(source);
092 if (s != null) {
093 s.remove(dependent_cmid);
094 }
095 }
096
097 /**
098 * Delete all NotOverridden dependencies on the argument RVMMethod
099 */
100 public void removeNotOverriddenDependency(RVMMethod source) {
101 nonOverriddenHash.remove(source);
102 }
103
104 /////////////////////
105 // (2) Dependency on a particular RVMClass not having any subclasses.
106 /////////////////////
107
108 /**
109 * Returns an iteration of CMID's (compiled method ids) that are dependent
110 * on the argument RVMMethod not having any subclasses. If there are no
111 * dependent methods, {@code null} will be returned.<p>
112 *
113 * NOTE: {@code null} is used instead of {@code EmptyIterator.getInstance}
114 * as part of delicate dance to avoid recursive classloading.
115 *
116 * @param m a method that can be overridden
117 * @return an iterator of CMIDs or {@code null}
118 */
119 public Iterator<Integer> invalidatedBySubclass(RVMClass m) {
120 MethodSet s = noSubclassHash.get(m);
121 return (s == null) ? null : s.iterator();
122 }
123
124 /**
125 * Record that if a particular RVMClass ever has a subclass, then
126 * the CompiledMethod encoded by the cmid must be invalidated.
127 */
128 public void addNoSubclassDependency(RVMClass source, int dependent_cmid) {
129 MethodSet s = findOrCreateMethodSet(noSubclassHash, source);
130 s.add(dependent_cmid);
131 }
132
133 /**
134 * Delete a NoSubclassDependency. No effect if the dependency doesn't exist..
135 */
136 public void removeNoSubclassDependency(RVMClass source, int dependent_cmid) {
137 MethodSet s = noSubclassHash.get(source);
138 if (s != null) {
139 s.remove(dependent_cmid);
140 }
141 }
142
143 /**
144 * Delete all NoSubclass dependencies on the argument RVMClass
145 */
146 public void removeNoSubclassDependency(RVMClass source) {
147 noSubclassHash.remove(source);
148 }
149
150 /**
151 * Look up the MethodSet corresponding to a given key in the database.
152 * If none found, create one.
153 */
154 private <T> MethodSet findOrCreateMethodSet(HashMapRVM<T, MethodSet> hash, T key) {
155 MethodSet result = hash.get(key);
156 if (result == null) {
157 result = new MethodSet(key);
158 hash.put(key, result);
159 }
160 return result;
161 }
162
163 /**
164 * The following defines a set of methods that share a common "key"
165 */
166 static final class MethodSet {
167 final Object key;
168 /**
169 * a set of cmids (Integers)
170 */
171 final HashSetRVM<Integer> methods = new HashSetRVM<Integer>();
172
173 MethodSet(Object key) {
174 this.key = key;
175 }
176
177 void add(int cmid) {
178 methods.add(cmid);
179 }
180
181 void remove(int cmid) {
182 methods.remove(cmid);
183 }
184
185 public Iterator<Integer> iterator() {
186 return methods.iterator();
187 }
188 }
189 }