1 /*
2 * Copyright (c) 2011, 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.virtual.phases.ea;
24
25 import static org.graalvm.compiler.core.common.GraalOptions.ReadEliminationMaxLoopVisits;
26 import static org.graalvm.compiler.core.common.LocationIdentity.any;
27
28 import java.util.HashMap;
29 import java.util.HashSet;
30 import java.util.Iterator;
31 import java.util.List;
32 import java.util.Map;
33 import java.util.Set;
34
35 import org.graalvm.compiler.core.common.CollectionsFactory;
36 import org.graalvm.compiler.core.common.LocationIdentity;
37 import org.graalvm.compiler.core.common.cfg.Loop;
38 import org.graalvm.compiler.core.common.type.Stamp;
39 import org.graalvm.compiler.debug.Debug;
40 import org.graalvm.compiler.graph.Node;
41 import org.graalvm.compiler.nodes.FieldLocationIdentity;
42 import org.graalvm.compiler.nodes.FixedNode;
43 import org.graalvm.compiler.nodes.FixedWithNextNode;
44 import org.graalvm.compiler.nodes.LoopExitNode;
45 import org.graalvm.compiler.nodes.PhiNode;
46 import org.graalvm.compiler.nodes.ProxyNode;
47 import org.graalvm.compiler.nodes.ValueNode;
48 import org.graalvm.compiler.nodes.ValuePhiNode;
49 import org.graalvm.compiler.nodes.ValueProxyNode;
50 import org.graalvm.compiler.nodes.cfg.Block;
51 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
52 import org.graalvm.compiler.nodes.extended.GuardedNode;
53 import org.graalvm.compiler.nodes.extended.UnsafeAccessNode;
54 import org.graalvm.compiler.nodes.extended.UnsafeLoadNode;
55 import org.graalvm.compiler.nodes.extended.UnsafeStoreNode;
56 import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
57 import org.graalvm.compiler.nodes.java.AccessFieldNode;
58 import org.graalvm.compiler.nodes.java.LoadFieldNode;
59 import org.graalvm.compiler.nodes.java.StoreFieldNode;
60 import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;
61 import org.graalvm.compiler.nodes.memory.ReadNode;
62 import org.graalvm.compiler.nodes.memory.WriteNode;
63 import org.graalvm.compiler.nodes.util.GraphUtil;
64 import org.graalvm.compiler.virtual.phases.ea.ReadEliminationBlockState.CacheEntry;
65 import org.graalvm.compiler.virtual.phases.ea.ReadEliminationBlockState.LoadCacheEntry;
66 import org.graalvm.compiler.virtual.phases.ea.ReadEliminationBlockState.UnsafeLoadCacheEntry;
67
68 import jdk.vm.ci.meta.JavaKind;
69
70 public class ReadEliminationClosure extends EffectsClosure<ReadEliminationBlockState> {
71
72 public ReadEliminationClosure(ControlFlowGraph cfg) {
73 super(null, cfg);
74 }
75
76 @Override
77 protected ReadEliminationBlockState getInitialState() {
78 return new ReadEliminationBlockState();
79 }
80
81 @Override
82 protected boolean processNode(Node node, ReadEliminationBlockState state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
83 boolean deleted = false;
84 if (node instanceof AccessFieldNode) {
85 AccessFieldNode access = (AccessFieldNode) node;
86 if (access.isVolatile()) {
87 processIdentity(state, any());
88 } else {
89 ValueNode object = GraphUtil.unproxify(access.object());
90 LoadCacheEntry identifier = new LoadCacheEntry(object, new FieldLocationIdentity(access.field()));
91 ValueNode cachedValue = state.getCacheEntry(identifier);
92 if (node instanceof LoadFieldNode) {
93 if (cachedValue != null && access.stamp().isCompatible(cachedValue.stamp())) {
94 effects.replaceAtUsages(access, cachedValue);
95 addScalarAlias(access, cachedValue);
96 deleted = true;
97 } else {
98 state.addCacheEntry(identifier, access);
99 }
100 } else {
101 assert node instanceof StoreFieldNode;
102 StoreFieldNode store = (StoreFieldNode) node;
103 ValueNode value = getScalarAlias(store.value());
104 if (GraphUtil.unproxify(value) == GraphUtil.unproxify(cachedValue)) {
105 effects.deleteNode(store);
106 deleted = true;
107 }
108 state.killReadCache(identifier.identity);
109 state.addCacheEntry(identifier, value);
110 }
111 }
112 } else if (node instanceof ReadNode) {
113 ReadNode read = (ReadNode) node;
114 if (read.getLocationIdentity().isSingle()) {
115 ValueNode object = GraphUtil.unproxify(read.getAddress());
116 LoadCacheEntry identifier = new LoadCacheEntry(object, read.getLocationIdentity());
117 ValueNode cachedValue = state.getCacheEntry(identifier);
118 if (cachedValue != null && read.stamp().isCompatible(cachedValue.stamp())) {
119 // Anchor guard if it is not fixed and different from cachedValue's guard such
120 // that it gets preserved.
121 if (read.getGuard() != null && !(read.getGuard() instanceof FixedNode)) {
122 if (!(cachedValue instanceof GuardedNode) || ((GuardedNode) cachedValue).getGuard() != read.getGuard()) {
123 effects.addFixedNodeBefore(new ValueAnchorNode((ValueNode) read.getGuard()), read);
124 }
125 }
126 effects.replaceAtUsages(read, cachedValue);
127 addScalarAlias(read, cachedValue);
128 deleted = true;
129 } else {
130 state.addCacheEntry(identifier, read);
131 }
132 }
133 } else if (node instanceof WriteNode) {
134 WriteNode write = (WriteNode) node;
135 if (write.getLocationIdentity().isSingle()) {
136 ValueNode object = GraphUtil.unproxify(write.getAddress());
137 LoadCacheEntry identifier = new LoadCacheEntry(object, write.getLocationIdentity());
138 ValueNode cachedValue = state.getCacheEntry(identifier);
139
140 ValueNode value = getScalarAlias(write.value());
141 if (GraphUtil.unproxify(value) == GraphUtil.unproxify(cachedValue)) {
142 effects.deleteNode(write);
143 deleted = true;
144 }
145 processIdentity(state, write.getLocationIdentity());
146 state.addCacheEntry(identifier, value);
147 } else {
148 processIdentity(state, write.getLocationIdentity());
149 }
150 } else if (node instanceof UnsafeAccessNode) {
151 if (node instanceof UnsafeLoadNode) {
152 UnsafeLoadNode load = (UnsafeLoadNode) node;
153 if (load.getLocationIdentity().isSingle()) {
154 ValueNode object = GraphUtil.unproxify(load.object());
155 UnsafeLoadCacheEntry identifier = new UnsafeLoadCacheEntry(object, load.offset(), load.getLocationIdentity());
156 ValueNode cachedValue = state.getCacheEntry(identifier);
157 if (cachedValue != null && load.stamp().isCompatible(cachedValue.stamp())) {
158 effects.replaceAtUsages(load, cachedValue);
159 addScalarAlias(load, cachedValue);
160 deleted = true;
161 } else {
162 state.addCacheEntry(identifier, load);
163 }
164 }
165 } else {
166 assert node instanceof UnsafeStoreNode;
167 UnsafeStoreNode write = (UnsafeStoreNode) node;
168 if (write.getLocationIdentity().isSingle()) {
169 ValueNode object = GraphUtil.unproxify(write.object());
170 UnsafeLoadCacheEntry identifier = new UnsafeLoadCacheEntry(object, write.offset(), write.getLocationIdentity());
171 ValueNode cachedValue = state.getCacheEntry(identifier);
172
173 ValueNode value = getScalarAlias(write.value());
174 if (GraphUtil.unproxify(value) == GraphUtil.unproxify(cachedValue)) {
175 effects.deleteNode(write);
176 deleted = true;
177 }
178 processIdentity(state, write.getLocationIdentity());
179 state.addCacheEntry(identifier, value);
180 } else {
181 processIdentity(state, write.getLocationIdentity());
182 }
183 }
184 } else if (node instanceof MemoryCheckpoint.Single) {
185 LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
186 processIdentity(state, identity);
187 } else if (node instanceof MemoryCheckpoint.Multi) {
188 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
189 processIdentity(state, identity);
190 }
191 }
192 return deleted;
193 }
194
195 private static void processIdentity(ReadEliminationBlockState state, LocationIdentity identity) {
196 if (identity.isAny()) {
197 state.killReadCache();
198 return;
199 }
200 state.killReadCache(identity);
201 }
202
203 @Override
204 protected void processLoopExit(LoopExitNode exitNode, ReadEliminationBlockState initialState, ReadEliminationBlockState exitState, GraphEffectList effects) {
205 if (exitNode.graph().hasValueProxies()) {
206 for (Map.Entry<CacheEntry<?>, ValueNode> entry : exitState.getReadCache().entrySet()) {
207 if (initialState.getReadCache().get(entry.getKey()) != entry.getValue()) {
208 ProxyNode proxy = new ValueProxyNode(exitState.getCacheEntry(entry.getKey()), exitNode);
209 effects.addFloatingNode(proxy, "readCacheProxy");
210 entry.setValue(proxy);
211 }
212 }
213 }
214 }
215
216 @Override
217 protected ReadEliminationBlockState cloneState(ReadEliminationBlockState other) {
218 return new ReadEliminationBlockState(other);
219 }
220
221 @Override
222 protected MergeProcessor createMergeProcessor(Block merge) {
223 return new ReadEliminationMergeProcessor(merge);
224 }
225
226 private class ReadEliminationMergeProcessor extends EffectsClosure<ReadEliminationBlockState>.MergeProcessor {
227
228 private final HashMap<Object, ValuePhiNode> materializedPhis = CollectionsFactory.newMap();
229
230 ReadEliminationMergeProcessor(Block mergeBlock) {
231 super(mergeBlock);
232 }
233
234 protected <T> PhiNode getCachedPhi(T virtual, Stamp stamp) {
235 ValuePhiNode result = materializedPhis.get(virtual);
236 if (result == null) {
237 result = createValuePhi(stamp);
238 materializedPhis.put(virtual, result);
239 }
240 return result;
241 }
242
243 @Override
244 protected void merge(List<ReadEliminationBlockState> states) {
245 super.merge(states);
246
247 mergeReadCache(states);
248 }
249
250 private void mergeReadCache(List<ReadEliminationBlockState> states) {
251 for (Map.Entry<CacheEntry<?>, ValueNode> entry : states.get(0).readCache.entrySet()) {
252 CacheEntry<?> key = entry.getKey();
253 ValueNode value = entry.getValue();
254 boolean phi = false;
255 for (int i = 1; i < states.size(); i++) {
256 ValueNode otherValue = states.get(i).readCache.get(key);
257 // e.g. unsafe loads / stores with different access kinds have different stamps
258 // although location, object and offset are the same, in this case we cannot
259 // create a phi nor can we set a common value
260 if (otherValue == null || !value.stamp().isCompatible(otherValue.stamp())) {
261 value = null;
262 phi = false;
263 break;
264 }
265 if (!phi && otherValue != value) {
266 phi = true;
267 }
268 }
269 if (phi) {
270 PhiNode phiNode = getCachedPhi(entry, value.stamp().unrestricted());
271 mergeEffects.addFloatingNode(phiNode, "mergeReadCache");
272 for (int i = 0; i < states.size(); i++) {
273 ValueNode v = states.get(i).getCacheEntry(key);
274 assert phiNode.stamp().isCompatible(v.stamp()) : "Cannot create read elimination phi for inputs with incompatible stamps.";
275 setPhiInput(phiNode, i, v);
276 }
277 newState.addCacheEntry(key, phiNode);
278 } else if (value != null) {
279 // case that there is the same value on all branches
280 newState.addCacheEntry(key, value);
281 }
282 }
283 for (PhiNode phi : getPhis()) {
284 if (phi.getStackKind() == JavaKind.Object) {
285 for (Map.Entry<CacheEntry<?>, ValueNode> entry : states.get(0).readCache.entrySet()) {
286 if (entry.getKey().object == getPhiValueAt(phi, 0)) {
287 mergeReadCachePhi(phi, entry.getKey(), states);
288 }
289 }
290
291 }
292 }
293 }
294
295 private void mergeReadCachePhi(PhiNode phi, CacheEntry<?> identifier, List<ReadEliminationBlockState> states) {
296 ValueNode[] values = new ValueNode[states.size()];
297 values[0] = states.get(0).getCacheEntry(identifier.duplicateWithObject(getPhiValueAt(phi, 0)));
298 if (values[0] != null) {
299 for (int i = 1; i < states.size(); i++) {
300 ValueNode value = states.get(i).getCacheEntry(identifier.duplicateWithObject(getPhiValueAt(phi, i)));
301 // e.g. unsafe loads / stores with same identity and different access kinds see
302 // mergeReadCache(states)
303 if (value == null || !values[i - 1].stamp().isCompatible(value.stamp())) {
304 return;
305 }
306 values[i] = value;
307 }
308
309 CacheEntry<?> newIdentifier = identifier.duplicateWithObject(phi);
310 PhiNode phiNode = getCachedPhi(newIdentifier, values[0].stamp().unrestricted());
311 mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi");
312 for (int i = 0; i < values.length; i++) {
313 setPhiInput(phiNode, i, values[i]);
314 }
315 newState.addCacheEntry(newIdentifier, phiNode);
316 }
317 }
318 }
319
320 @Override
321 protected void processKilledLoopLocations(Loop<Block> loop, ReadEliminationBlockState initialState, ReadEliminationBlockState mergedStates) {
322 assert initialState != null;
323 assert mergedStates != null;
324 if (initialState.readCache.size() > 0) {
325 LoopKillCache loopKilledLocations = loopLocationKillCache.get(loop);
326 // we have fully processed this loop the first time, remember to cache it the next time
327 // it is visited
328 if (loopKilledLocations == null) {
329 loopKilledLocations = new LoopKillCache(1/* 1.visit */);
330 loopLocationKillCache.put(loop, loopKilledLocations);
331 } else {
332 if (loopKilledLocations.visits() > ReadEliminationMaxLoopVisits.getValue()) {
333 // we have processed the loop too many times, kill all locations so the inner
334 // loop will never be processed more than once again on visit
335 loopKilledLocations.setKillsAll();
336 } else {
337 // we have fully processed this loop >1 times, update the killed locations
338 Set<LocationIdentity> forwardEndLiveLocations = new HashSet<>();
339 for (CacheEntry<?> entry : initialState.readCache.keySet()) {
340 forwardEndLiveLocations.add(entry.getIdentity());
341 }
342 for (CacheEntry<?> entry : mergedStates.readCache.keySet()) {
343 forwardEndLiveLocations.remove(entry.getIdentity());
344 }
345 // every location that is alive before the loop but not after is killed by the
346 // loop
347 for (LocationIdentity location : forwardEndLiveLocations) {
348 loopKilledLocations.rememberLoopKilledLocation(location);
349 }
350 if (Debug.isLogEnabled() && loopKilledLocations != null) {
351 Debug.log("[Early Read Elimination] Setting loop killed locations of loop at node %s with %s",
352 loop.getHeader().getBeginNode(), forwardEndLiveLocations);
353 }
354 }
355 // remember the loop visit
356 loopKilledLocations.visited();
357 }
358 }
359 }
360
361 @Override
362 protected ReadEliminationBlockState stripKilledLoopLocations(Loop<Block> loop, ReadEliminationBlockState originalInitialState) {
363 ReadEliminationBlockState initialState = super.stripKilledLoopLocations(loop, originalInitialState);
364 LoopKillCache loopKilledLocations = loopLocationKillCache.get(loop);
365 if (loopKilledLocations != null && loopKilledLocations.loopKillsLocations()) {
366 Set<CacheEntry<?>> forwardEndLiveLocations = initialState.readCache.keySet();
367 Iterator<CacheEntry<?>> it = forwardEndLiveLocations.iterator();
368 while (it.hasNext()) {
369 CacheEntry<?> entry = it.next();
370 if (loopKilledLocations.containsLocation(entry.getIdentity())) {
371 it.remove();
372 }
373 }
374 }
375 return initialState;
376 }
377 }