1 /*
2 * Copyright (c) 2011, 2017, 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.word.LocationIdentity.any;
27
28 import java.util.Iterator;
29 import java.util.List;
30
31 import org.graalvm.compiler.core.common.cfg.Loop;
32 import org.graalvm.compiler.core.common.type.Stamp;
33 import org.graalvm.compiler.graph.Node;
34 import org.graalvm.compiler.nodes.FieldLocationIdentity;
35 import org.graalvm.compiler.nodes.FixedWithNextNode;
36 import org.graalvm.compiler.nodes.LoopExitNode;
37 import org.graalvm.compiler.nodes.PhiNode;
38 import org.graalvm.compiler.nodes.ProxyNode;
39 import org.graalvm.compiler.nodes.ValueNode;
40 import org.graalvm.compiler.nodes.ValuePhiNode;
41 import org.graalvm.compiler.nodes.ValueProxyNode;
42 import org.graalvm.compiler.nodes.cfg.Block;
43 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
44 import org.graalvm.compiler.nodes.extended.GuardedNode;
45 import org.graalvm.compiler.nodes.extended.GuardingNode;
46 import org.graalvm.compiler.nodes.extended.RawLoadNode;
47 import org.graalvm.compiler.nodes.extended.RawStoreNode;
48 import org.graalvm.compiler.nodes.extended.UnsafeAccessNode;
49 import org.graalvm.compiler.nodes.java.AccessFieldNode;
50 import org.graalvm.compiler.nodes.java.LoadFieldNode;
51 import org.graalvm.compiler.nodes.java.StoreFieldNode;
52 import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;
53 import org.graalvm.compiler.nodes.memory.ReadNode;
54 import org.graalvm.compiler.nodes.memory.WriteNode;
55 import org.graalvm.compiler.nodes.util.GraphUtil;
56 import org.graalvm.compiler.options.OptionValues;
57 import org.graalvm.compiler.virtual.phases.ea.ReadEliminationBlockState.CacheEntry;
58 import org.graalvm.compiler.virtual.phases.ea.ReadEliminationBlockState.LoadCacheEntry;
59 import org.graalvm.compiler.virtual.phases.ea.ReadEliminationBlockState.UnsafeLoadCacheEntry;
60 import org.graalvm.util.EconomicMap;
61 import org.graalvm.util.EconomicSet;
62 import org.graalvm.util.Equivalence;
63 import org.graalvm.util.MapCursor;
64 import org.graalvm.word.LocationIdentity;
65
66 import jdk.vm.ci.meta.JavaKind;
67
68 /**
69 * This closure initially handled a set of nodes that is disjunct from
70 * {@link PEReadEliminationClosure}, but over time both have evolved so that there's a significant
71 * overlap.
72 */
73 public final class ReadEliminationClosure extends EffectsClosure<ReadEliminationBlockState> {
74 private final boolean considerGuards;
75
76 public ReadEliminationClosure(ControlFlowGraph cfg, boolean considerGuards) {
77 super(null, cfg);
78 this.considerGuards = considerGuards;
79 }
80
81 @Override
82 protected ReadEliminationBlockState getInitialState() {
83 return new ReadEliminationBlockState();
84 }
85
86 @Override
87 protected boolean processNode(Node node, ReadEliminationBlockState state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
88 boolean deleted = false;
89 if (node instanceof AccessFieldNode) {
90 AccessFieldNode access = (AccessFieldNode) node;
91 if (access.isVolatile()) {
92 processIdentity(state, any());
93 } else {
94 ValueNode object = GraphUtil.unproxify(access.object());
95 LoadCacheEntry identifier = new LoadCacheEntry(object, new FieldLocationIdentity(access.field()));
96 ValueNode cachedValue = state.getCacheEntry(identifier);
97 if (node instanceof LoadFieldNode) {
98 if (cachedValue != null && access.stamp().isCompatible(cachedValue.stamp())) {
99 effects.replaceAtUsages(access, cachedValue, access);
100 addScalarAlias(access, cachedValue);
101 deleted = true;
102 } else {
103 state.addCacheEntry(identifier, access);
104 }
105 } else {
106 assert node instanceof StoreFieldNode;
107 StoreFieldNode store = (StoreFieldNode) node;
108 ValueNode value = getScalarAlias(store.value());
109 if (GraphUtil.unproxify(value) == GraphUtil.unproxify(cachedValue)) {
110 effects.deleteNode(store);
111 deleted = true;
112 }
113 state.killReadCache(identifier.identity);
114 state.addCacheEntry(identifier, value);
115 }
116 }
117 } else if (node instanceof ReadNode) {
118 ReadNode read = (ReadNode) node;
119 if (read.getLocationIdentity().isSingle()) {
120 ValueNode object = GraphUtil.unproxify(read.getAddress());
121 LoadCacheEntry identifier = new LoadCacheEntry(object, read.getLocationIdentity());
122 ValueNode cachedValue = state.getCacheEntry(identifier);
123 if (cachedValue != null && areValuesReplaceable(read, cachedValue, considerGuards)) {
124 effects.replaceAtUsages(read, cachedValue, read);
125 addScalarAlias(read, cachedValue);
126 deleted = true;
127 } else {
128 state.addCacheEntry(identifier, read);
129 }
130 }
131 } else if (node instanceof WriteNode) {
132 WriteNode write = (WriteNode) node;
133 if (write.getLocationIdentity().isSingle()) {
134 ValueNode object = GraphUtil.unproxify(write.getAddress());
135 LoadCacheEntry identifier = new LoadCacheEntry(object, write.getLocationIdentity());
136 ValueNode cachedValue = state.getCacheEntry(identifier);
137
138 ValueNode value = getScalarAlias(write.value());
139 if (GraphUtil.unproxify(value) == GraphUtil.unproxify(cachedValue)) {
140 effects.deleteNode(write);
141 deleted = true;
142 }
143 processIdentity(state, write.getLocationIdentity());
144 state.addCacheEntry(identifier, value);
145 } else {
146 processIdentity(state, write.getLocationIdentity());
147 }
148 } else if (node instanceof UnsafeAccessNode) {
149 if (node instanceof RawLoadNode) {
150 RawLoadNode load = (RawLoadNode) node;
151 if (load.getLocationIdentity().isSingle()) {
152 ValueNode object = GraphUtil.unproxify(load.object());
153 UnsafeLoadCacheEntry identifier = new UnsafeLoadCacheEntry(object, load.offset(), load.getLocationIdentity());
154 ValueNode cachedValue = state.getCacheEntry(identifier);
155 if (cachedValue != null && areValuesReplaceable(load, cachedValue, considerGuards)) {
156 effects.replaceAtUsages(load, cachedValue, load);
157 addScalarAlias(load, cachedValue);
158 deleted = true;
159 } else {
160 state.addCacheEntry(identifier, load);
161 }
162 }
163 } else {
164 assert node instanceof RawStoreNode;
165 RawStoreNode write = (RawStoreNode) node;
166 if (write.getLocationIdentity().isSingle()) {
167 ValueNode object = GraphUtil.unproxify(write.object());
168 UnsafeLoadCacheEntry identifier = new UnsafeLoadCacheEntry(object, write.offset(), write.getLocationIdentity());
169 ValueNode cachedValue = state.getCacheEntry(identifier);
170
171 ValueNode value = getScalarAlias(write.value());
172 if (GraphUtil.unproxify(value) == GraphUtil.unproxify(cachedValue)) {
173 effects.deleteNode(write);
174 deleted = true;
175 }
176 processIdentity(state, write.getLocationIdentity());
177 state.addCacheEntry(identifier, value);
178 } else {
179 processIdentity(state, write.getLocationIdentity());
180 }
181 }
182 } else if (node instanceof MemoryCheckpoint.Single) {
183 LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
184 processIdentity(state, identity);
185 } else if (node instanceof MemoryCheckpoint.Multi) {
186 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
187 processIdentity(state, identity);
188 }
189 }
190 return deleted;
191 }
192
193 private static boolean areValuesReplaceable(ValueNode originalValue, ValueNode replacementValue, boolean considerGuards) {
194 return originalValue.stamp().isCompatible(replacementValue.stamp()) &&
195 (!considerGuards || (getGuard(originalValue) == null || getGuard(originalValue) == getGuard(replacementValue)));
196 }
197
198 private static GuardingNode getGuard(ValueNode node) {
199 if (node instanceof GuardedNode) {
200 GuardedNode guardedNode = (GuardedNode) node;
201 return guardedNode.getGuard();
202 }
203 return null;
204 }
205
206 private static void processIdentity(ReadEliminationBlockState state, LocationIdentity identity) {
207 if (identity.isAny()) {
208 state.killReadCache();
209 return;
210 }
211 state.killReadCache(identity);
212 }
213
214 @Override
215 protected void processLoopExit(LoopExitNode exitNode, ReadEliminationBlockState initialState, ReadEliminationBlockState exitState, GraphEffectList effects) {
216 if (exitNode.graph().hasValueProxies()) {
217 MapCursor<CacheEntry<?>, ValueNode> entry = exitState.getReadCache().getEntries();
218 while (entry.advance()) {
219 if (initialState.getReadCache().get(entry.getKey()) != entry.getValue()) {
220 ProxyNode proxy = new ValueProxyNode(exitState.getCacheEntry(entry.getKey()), exitNode);
221 effects.addFloatingNode(proxy, "readCacheProxy");
222 exitState.getReadCache().put(entry.getKey(), proxy);
223 }
224 }
225 }
226 }
227
228 @Override
229 protected ReadEliminationBlockState cloneState(ReadEliminationBlockState other) {
230 return new ReadEliminationBlockState(other);
231 }
232
233 @Override
234 protected MergeProcessor createMergeProcessor(Block merge) {
235 return new ReadEliminationMergeProcessor(merge);
236 }
237
238 private class ReadEliminationMergeProcessor extends EffectsClosure<ReadEliminationBlockState>.MergeProcessor {
239
240 private final EconomicMap<Object, ValuePhiNode> materializedPhis = EconomicMap.create(Equivalence.DEFAULT);
241
242 ReadEliminationMergeProcessor(Block mergeBlock) {
243 super(mergeBlock);
244 }
245
246 protected ValuePhiNode getCachedPhi(CacheEntry<?> virtual, Stamp stamp) {
247 ValuePhiNode result = materializedPhis.get(virtual);
248 if (result == null) {
249 result = createValuePhi(stamp);
250 materializedPhis.put(virtual, result);
251 }
252 return result;
253 }
254
255 @Override
256 protected void merge(List<ReadEliminationBlockState> states) {
257 MapCursor<CacheEntry<?>, ValueNode> cursor = states.get(0).readCache.getEntries();
258 while (cursor.advance()) {
259 CacheEntry<?> key = cursor.getKey();
260 ValueNode value = cursor.getValue();
261 boolean phi = false;
262 for (int i = 1; i < states.size(); i++) {
263 ValueNode otherValue = states.get(i).readCache.get(key);
264 // E.g. unsafe loads / stores with different access kinds have different stamps
265 // although location, object and offset are the same. In this case we cannot
266 // create a phi nor can we set a common value.
267 if (otherValue == null || !value.stamp().isCompatible(otherValue.stamp())) {
268 value = null;
269 phi = false;
270 break;
271 }
272 if (!phi && otherValue != value) {
273 phi = true;
274 }
275 }
276 if (phi) {
277 PhiNode phiNode = getCachedPhi(key, value.stamp().unrestricted());
278 mergeEffects.addFloatingNode(phiNode, "mergeReadCache");
279 for (int i = 0; i < states.size(); i++) {
280 ValueNode v = states.get(i).getCacheEntry(key);
281 assert phiNode.stamp().isCompatible(v.stamp()) : "Cannot create read elimination phi for inputs with incompatible stamps.";
282 setPhiInput(phiNode, i, v);
283 }
284 newState.addCacheEntry(key, phiNode);
285 } else if (value != null) {
286 // case that there is the same value on all branches
287 newState.addCacheEntry(key, value);
288 }
289 }
290 /*
291 * For object phis, see if there are known reads on all predecessors, for which we could
292 * create new phis.
293 */
294 for (PhiNode phi : getPhis()) {
295 if (phi.getStackKind() == JavaKind.Object) {
296 for (CacheEntry<?> entry : states.get(0).readCache.getKeys()) {
297 if (entry.object == getPhiValueAt(phi, 0)) {
298 mergeReadCachePhi(phi, entry, states);
299 }
300 }
301 }
302 }
303 }
304
305 private void mergeReadCachePhi(PhiNode phi, CacheEntry<?> identifier, List<ReadEliminationBlockState> states) {
306 ValueNode[] values = new ValueNode[states.size()];
307 values[0] = states.get(0).getCacheEntry(identifier.duplicateWithObject(getPhiValueAt(phi, 0)));
308 if (values[0] != null) {
309 for (int i = 1; i < states.size(); i++) {
310 ValueNode value = states.get(i).getCacheEntry(identifier.duplicateWithObject(getPhiValueAt(phi, i)));
311 // e.g. unsafe loads / stores with same identity and different access kinds see
312 // mergeReadCache(states)
313 if (value == null || !values[i - 1].stamp().isCompatible(value.stamp())) {
314 return;
315 }
316 values[i] = value;
317 }
318
319 CacheEntry<?> newIdentifier = identifier.duplicateWithObject(phi);
320 PhiNode phiNode = getCachedPhi(newIdentifier, values[0].stamp().unrestricted());
321 mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi");
322 for (int i = 0; i < values.length; i++) {
323 setPhiInput(phiNode, i, values[i]);
324 }
325 newState.addCacheEntry(newIdentifier, phiNode);
326 }
327 }
328 }
329
330 @Override
331 protected void processKilledLoopLocations(Loop<Block> loop, ReadEliminationBlockState initialState, ReadEliminationBlockState mergedStates) {
332 assert initialState != null;
333 assert mergedStates != null;
334 if (initialState.readCache.size() > 0) {
335 LoopKillCache loopKilledLocations = loopLocationKillCache.get(loop);
336 // we have fully processed this loop the first time, remember to cache it the next time
337 // it is visited
338 if (loopKilledLocations == null) {
339 loopKilledLocations = new LoopKillCache(1/* 1.visit */);
340 loopLocationKillCache.put(loop, loopKilledLocations);
341 } else {
342 OptionValues options = loop.getHeader().getBeginNode().getOptions();
343 if (loopKilledLocations.visits() > ReadEliminationMaxLoopVisits.getValue(options)) {
344 // we have processed the loop too many times, kill all locations so the inner
345 // loop will never be processed more than once again on visit
346 loopKilledLocations.setKillsAll();
347 } else {
348 // we have fully processed this loop >1 times, update the killed locations
349 EconomicSet<LocationIdentity> forwardEndLiveLocations = EconomicSet.create(Equivalence.DEFAULT);
350 for (CacheEntry<?> entry : initialState.readCache.getKeys()) {
351 forwardEndLiveLocations.add(entry.getIdentity());
352 }
353 for (CacheEntry<?> entry : mergedStates.readCache.getKeys()) {
354 forwardEndLiveLocations.remove(entry.getIdentity());
355 }
356 // every location that is alive before the loop but not after is killed by the
357 // loop
358 for (LocationIdentity location : forwardEndLiveLocations) {
359 loopKilledLocations.rememberLoopKilledLocation(location);
360 }
361 if (debug.isLogEnabled() && loopKilledLocations != null) {
362 debug.log("[Early Read Elimination] Setting loop killed locations of loop at node %s with %s",
363 loop.getHeader().getBeginNode(), forwardEndLiveLocations);
364 }
365 }
366 // remember the loop visit
367 loopKilledLocations.visited();
368 }
369 }
370 }
371
372 @Override
373 protected ReadEliminationBlockState stripKilledLoopLocations(Loop<Block> loop, ReadEliminationBlockState originalInitialState) {
374 ReadEliminationBlockState initialState = super.stripKilledLoopLocations(loop, originalInitialState);
375 LoopKillCache loopKilledLocations = loopLocationKillCache.get(loop);
376 if (loopKilledLocations != null && loopKilledLocations.loopKillsLocations()) {
377 Iterator<CacheEntry<?>> it = initialState.readCache.getKeys().iterator();
378 while (it.hasNext()) {
379 CacheEntry<?> entry = it.next();
380 if (loopKilledLocations.containsLocation(entry.getIdentity())) {
381 it.remove();
382 }
383 }
384 }
385 return initialState;
386 }
387 }