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.nodes.NamedLocationIdentity.ARRAY_LENGTH_LOCATION;
27
28 import java.util.ArrayList;
29 import java.util.EnumMap;
30 import java.util.HashSet;
31 import java.util.Iterator;
32 import java.util.List;
33 import java.util.Map;
34 import java.util.Set;
35
36 import org.graalvm.compiler.core.common.LocationIdentity;
37 import org.graalvm.compiler.core.common.cfg.Loop;
38 import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
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.LoopBeginNode;
45 import org.graalvm.compiler.nodes.LoopExitNode;
46 import org.graalvm.compiler.nodes.NamedLocationIdentity;
47 import org.graalvm.compiler.nodes.PhiNode;
48 import org.graalvm.compiler.nodes.ProxyNode;
49 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
50 import org.graalvm.compiler.nodes.ValueNode;
51 import org.graalvm.compiler.nodes.ValueProxyNode;
52 import org.graalvm.compiler.nodes.cfg.Block;
53 import org.graalvm.compiler.nodes.extended.UnboxNode;
54 import org.graalvm.compiler.nodes.extended.UnsafeLoadNode;
55 import org.graalvm.compiler.nodes.extended.UnsafeStoreNode;
56 import org.graalvm.compiler.nodes.java.ArrayLengthNode;
57 import org.graalvm.compiler.nodes.java.LoadFieldNode;
58 import org.graalvm.compiler.nodes.java.LoadIndexedNode;
59 import org.graalvm.compiler.nodes.java.StoreFieldNode;
60 import org.graalvm.compiler.nodes.java.StoreIndexedNode;
61 import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;
62 import org.graalvm.compiler.nodes.spi.LoweringProvider;
63 import org.graalvm.compiler.nodes.type.StampTool;
64 import org.graalvm.compiler.nodes.util.GraphUtil;
65 import org.graalvm.compiler.nodes.virtual.VirtualArrayNode;
66 import org.graalvm.compiler.virtual.phases.ea.PEReadEliminationBlockState.ReadCacheEntry;
67
68 import jdk.vm.ci.meta.ConstantReflectionProvider;
69 import jdk.vm.ci.meta.JavaConstant;
70 import jdk.vm.ci.meta.JavaKind;
71 import jdk.vm.ci.meta.MetaAccessProvider;
72 import jdk.vm.ci.meta.ResolvedJavaType;
73
74 public class PEReadEliminationClosure extends PartialEscapeClosure<PEReadEliminationBlockState> {
75
76 private static final EnumMap<JavaKind, LocationIdentity> UNBOX_LOCATIONS;
77
78 static {
79 UNBOX_LOCATIONS = new EnumMap<>(JavaKind.class);
80 for (JavaKind kind : JavaKind.values()) {
81 UNBOX_LOCATIONS.put(kind, NamedLocationIdentity.immutable("PEA unbox " + kind.getJavaName()));
82 }
83 }
84
85 public PEReadEliminationClosure(ScheduleResult schedule, MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider,
86 LoweringProvider loweringProvider) {
87 super(schedule, metaAccess, constantReflection, constantFieldProvider, loweringProvider);
88 }
89
90 @Override
91 protected PEReadEliminationBlockState getInitialState() {
92 return new PEReadEliminationBlockState();
93 }
94
95 @Override
96 protected boolean processNode(Node node, PEReadEliminationBlockState state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
97 if (super.processNode(node, state, effects, lastFixedNode)) {
98 return true;
99 }
100
101 if (node instanceof LoadFieldNode) {
102 return processLoadField((LoadFieldNode) node, state, effects);
103 } else if (node instanceof StoreFieldNode) {
104 return processStoreField((StoreFieldNode) node, state, effects);
105 } else if (node instanceof LoadIndexedNode) {
106 return processLoadIndexed((LoadIndexedNode) node, state, effects);
107 } else if (node instanceof StoreIndexedNode) {
108 return processStoreIndexed((StoreIndexedNode) node, state, effects);
109 } else if (node instanceof ArrayLengthNode) {
110 return processArrayLength((ArrayLengthNode) node, state, effects);
111 } else if (node instanceof UnboxNode) {
112 return processUnbox((UnboxNode) node, state, effects);
113 } else if (node instanceof UnsafeLoadNode) {
114 return processUnsafeLoad((UnsafeLoadNode) node, state, effects);
115 } else if (node instanceof UnsafeStoreNode) {
116 return processUnsafeStore((UnsafeStoreNode) node, state, effects);
117 } else if (node instanceof MemoryCheckpoint.Single) {
118 COUNTER_MEMORYCHECKPOINT.increment();
119 LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
120 processIdentity(state, identity);
121 } else if (node instanceof MemoryCheckpoint.Multi) {
122 COUNTER_MEMORYCHECKPOINT.increment();
123 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
124 processIdentity(state, identity);
125 }
126 }
127
128 return false;
129 }
130
131 private boolean processStore(FixedNode store, ValueNode object, LocationIdentity identity, int index, ValueNode value, PEReadEliminationBlockState state, GraphEffectList effects) {
132 ValueNode unproxiedObject = GraphUtil.unproxify(object);
133 ValueNode cachedValue = state.getReadCache(object, identity, index, this);
134
135 ValueNode finalValue = getScalarAlias(value);
136 boolean result = false;
137 if (GraphUtil.unproxify(finalValue) == GraphUtil.unproxify(cachedValue)) {
138 effects.deleteNode(store);
139 result = true;
140 }
141 state.killReadCache(identity, index);
142 state.addReadCache(unproxiedObject, identity, index, finalValue, this);
143 return result;
144 }
145
146 private boolean processLoad(FixedNode load, ValueNode object, LocationIdentity identity, int index, PEReadEliminationBlockState state, GraphEffectList effects) {
147 ValueNode unproxiedObject = GraphUtil.unproxify(object);
148 ValueNode cachedValue = state.getReadCache(unproxiedObject, identity, index, this);
149 if (cachedValue != null) {
150 effects.replaceAtUsages(load, cachedValue);
151 addScalarAlias(load, cachedValue);
152 return true;
153 } else {
154 state.addReadCache(unproxiedObject, identity, index, load, this);
155 return false;
156 }
157 }
158
159 private boolean processUnsafeLoad(UnsafeLoadNode load, PEReadEliminationBlockState state, GraphEffectList effects) {
160 if (load.offset().isConstant()) {
161 ResolvedJavaType type = StampTool.typeOrNull(load.object());
162 if (type != null && type.isArray()) {
163 long offset = load.offset().asJavaConstant().asLong();
164 int index = VirtualArrayNode.entryIndexForOffset(offset, load.accessKind(), type.getComponentType(), Integer.MAX_VALUE);
165 ValueNode object = GraphUtil.unproxify(load.object());
166 LocationIdentity location = NamedLocationIdentity.getArrayLocation(type.getComponentType().getJavaKind());
167 ValueNode cachedValue = state.getReadCache(object, location, index, this);
168 if (cachedValue != null && load.stamp().isCompatible(cachedValue.stamp())) {
169 effects.replaceAtUsages(load, cachedValue);
170 addScalarAlias(load, cachedValue);
171 return true;
172 } else {
173 state.addReadCache(object, location, index, load, this);
174 }
175 }
176 }
177 return false;
178 }
179
180 private boolean processUnsafeStore(UnsafeStoreNode store, PEReadEliminationBlockState state, GraphEffectList effects) {
181 ResolvedJavaType type = StampTool.typeOrNull(store.object());
182 if (type != null && type.isArray()) {
183 LocationIdentity location = NamedLocationIdentity.getArrayLocation(type.getComponentType().getJavaKind());
184 if (store.offset().isConstant()) {
185 long offset = store.offset().asJavaConstant().asLong();
186 int index = VirtualArrayNode.entryIndexForOffset(offset, store.accessKind(), type.getComponentType(), Integer.MAX_VALUE);
187 return processStore(store, store.object(), location, index, store.value(), state, effects);
188 } else {
189 processIdentity(state, location);
190 }
191 } else {
192 state.killReadCache();
193 }
194 return false;
195 }
196
197 private boolean processArrayLength(ArrayLengthNode length, PEReadEliminationBlockState state, GraphEffectList effects) {
198 return processLoad(length, length.array(), ARRAY_LENGTH_LOCATION, -1, state, effects);
199 }
200
201 private boolean processStoreField(StoreFieldNode store, PEReadEliminationBlockState state, GraphEffectList effects) {
202 if (store.isVolatile()) {
203 state.killReadCache();
204 return false;
205 }
206 return processStore(store, store.object(), new FieldLocationIdentity(store.field()), -1, store.value(), state, effects);
207 }
208
209 private boolean processLoadField(LoadFieldNode load, PEReadEliminationBlockState state, GraphEffectList effects) {
210 if (load.isVolatile()) {
211 state.killReadCache();
212 return false;
213 }
214 return processLoad(load, load.object(), new FieldLocationIdentity(load.field()), -1, state, effects);
215 }
216
217 private boolean processStoreIndexed(StoreIndexedNode store, PEReadEliminationBlockState state, GraphEffectList effects) {
218 LocationIdentity arrayLocation = NamedLocationIdentity.getArrayLocation(store.elementKind());
219 if (store.index().isConstant()) {
220 int index = ((JavaConstant) store.index().asConstant()).asInt();
221 return processStore(store, store.array(), arrayLocation, index, store.value(), state, effects);
222 } else {
223 state.killReadCache(arrayLocation, -1);
224 }
225 return false;
226 }
227
228 private boolean processLoadIndexed(LoadIndexedNode load, PEReadEliminationBlockState state, GraphEffectList effects) {
229 if (load.index().isConstant()) {
230 int index = ((JavaConstant) load.index().asConstant()).asInt();
231 LocationIdentity arrayLocation = NamedLocationIdentity.getArrayLocation(load.elementKind());
232 return processLoad(load, load.array(), arrayLocation, index, state, effects);
233 }
234 return false;
235 }
236
237 private boolean processUnbox(UnboxNode unbox, PEReadEliminationBlockState state, GraphEffectList effects) {
238 return processLoad(unbox, unbox.getValue(), UNBOX_LOCATIONS.get(unbox.getBoxingKind()), -1, state, effects);
239 }
240
241 private static void processIdentity(PEReadEliminationBlockState state, LocationIdentity identity) {
242 if (identity.isAny()) {
243 state.killReadCache();
244 } else {
245 state.killReadCache(identity, -1);
246 }
247 }
248
249 @Override
250 protected void processInitialLoopState(Loop<Block> loop, PEReadEliminationBlockState initialState) {
251 super.processInitialLoopState(loop, initialState);
252
253 for (PhiNode phi : ((LoopBeginNode) loop.getHeader().getBeginNode()).phis()) {
254 ValueNode firstValue = phi.valueAt(0);
255 if (firstValue != null) {
256 firstValue = GraphUtil.unproxify(firstValue);
257 for (Map.Entry<ReadCacheEntry, ValueNode> entry : new ArrayList<>(initialState.getReadCache().entrySet())) {
258 if (entry.getKey().object == firstValue) {
259 initialState.addReadCache(phi, entry.getKey().identity, entry.getKey().index, entry.getValue(), this);
260 }
261 }
262 }
263 }
264 }
265
266 @Override
267 protected void processLoopExit(LoopExitNode exitNode, PEReadEliminationBlockState initialState, PEReadEliminationBlockState exitState, GraphEffectList effects) {
268 super.processLoopExit(exitNode, initialState, exitState, effects);
269
270 if (exitNode.graph().hasValueProxies()) {
271 for (Map.Entry<ReadCacheEntry, ValueNode> entry : exitState.getReadCache().entrySet()) {
272 if (initialState.getReadCache().get(entry.getKey()) != entry.getValue()) {
273 ValueNode value = exitState.getReadCache(entry.getKey().object, entry.getKey().identity, entry.getKey().index, this);
274 assert value != null : "Got null from read cache, entry's value:" + entry.getValue();
275 if (!(value instanceof ProxyNode) || ((ProxyNode) value).proxyPoint() != exitNode) {
276 ProxyNode proxy = new ValueProxyNode(value, exitNode);
277 effects.addFloatingNode(proxy, "readCacheProxy");
278 entry.setValue(proxy);
279 }
280 }
281 }
282 }
283 }
284
285 @Override
286 protected PEReadEliminationBlockState cloneState(PEReadEliminationBlockState other) {
287 return new PEReadEliminationBlockState(other);
288 }
289
290 @Override
291 protected MergeProcessor createMergeProcessor(Block merge) {
292 return new ReadEliminationMergeProcessor(merge);
293 }
294
295 private class ReadEliminationMergeProcessor extends MergeProcessor {
296
297 ReadEliminationMergeProcessor(Block mergeBlock) {
298 super(mergeBlock);
299 }
300
301 @Override
302 protected void merge(List<PEReadEliminationBlockState> states) {
303 super.merge(states);
304
305 mergeReadCache(states);
306 }
307
308 private void mergeReadCache(List<PEReadEliminationBlockState> states) {
309 for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
310 ReadCacheEntry key = entry.getKey();
311 ValueNode value = entry.getValue();
312 boolean phi = false;
313 for (int i = 1; i < states.size(); i++) {
314 ValueNode otherValue = states.get(i).readCache.get(key);
315 // e.g. unsafe loads / stores with different access kinds have different stamps
316 // although location, object and offset are the same, in this case we cannot
317 // create a phi nor can we set a common value
318 if (otherValue == null || !value.stamp().isCompatible(otherValue.stamp())) {
319 value = null;
320 phi = false;
321 break;
322 }
323 if (!phi && otherValue != value) {
324 phi = true;
325 }
326 }
327 if (phi) {
328 PhiNode phiNode = getPhi(entry, value.stamp().unrestricted());
329 mergeEffects.addFloatingNode(phiNode, "mergeReadCache");
330 for (int i = 0; i < states.size(); i++) {
331 ValueNode v = states.get(i).getReadCache(key.object, key.identity, key.index, PEReadEliminationClosure.this);
332 assert phiNode.stamp().isCompatible(v.stamp()) : "Cannot create read elimination phi for inputs with incompatible stamps.";
333 setPhiInput(phiNode, i, v);
334 }
335 newState.readCache.put(key, phiNode);
336 } else if (value != null) {
337 newState.readCache.put(key, value);
338 }
339 }
340 for (PhiNode phi : getPhis()) {
341 if (phi.getStackKind() == JavaKind.Object) {
342 for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
343 if (entry.getKey().object == getPhiValueAt(phi, 0)) {
344 mergeReadCachePhi(phi, entry.getKey().identity, entry.getKey().index, states);
345 }
346 }
347 }
348 }
349 }
350
351 private void mergeReadCachePhi(PhiNode phi, LocationIdentity identity, int index, List<PEReadEliminationBlockState> states) {
352 ValueNode[] values = new ValueNode[states.size()];
353 values[0] = states.get(0).getReadCache(getPhiValueAt(phi, 0), identity, index, PEReadEliminationClosure.this);
354 if (values[0] != null) {
355 for (int i = 1; i < states.size(); i++) {
356 ValueNode value = states.get(i).getReadCache(getPhiValueAt(phi, i), identity, index, PEReadEliminationClosure.this);
357 // e.g. unsafe loads / stores with same identity and different access kinds see
358 // mergeReadCache(states)
359 if (value == null || !values[i - 1].stamp().isCompatible(value.stamp())) {
360 return;
361 }
362 values[i] = value;
363 }
364
365 PhiNode phiNode = getPhi(new ReadCacheEntry(identity, phi, index), values[0].stamp().unrestricted());
366 mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi");
367 for (int i = 0; i < values.length; i++) {
368 setPhiInput(phiNode, i, values[i]);
369 }
370 newState.readCache.put(new ReadCacheEntry(identity, phi, index), phiNode);
371 }
372 }
373 }
374
375 @Override
376 protected void processKilledLoopLocations(Loop<Block> loop, PEReadEliminationBlockState initialState, PEReadEliminationBlockState mergedStates) {
377 assert initialState != null;
378 assert mergedStates != null;
379 if (initialState.readCache.size() > 0) {
380 LoopKillCache loopKilledLocations = loopLocationKillCache.get(loop);
381 // we have fully processed this loop the first time, remember to cache it the next time
382 // it is visited
383 if (loopKilledLocations == null) {
384 loopKilledLocations = new LoopKillCache(1/* 1.visit */);
385 loopLocationKillCache.put(loop, loopKilledLocations);
386 } else {
387 if (loopKilledLocations.visits() > ReadEliminationMaxLoopVisits.getValue()) {
388 // we have processed the loop too many times, kill all locations so the inner
389 // loop will never be processed more than once again on visit
390 loopKilledLocations.setKillsAll();
391 } else {
392 // we have fully processed this loop >1 times, update the killed locations
393 Set<LocationIdentity> forwardEndLiveLocations = new HashSet<>();
394 for (ReadCacheEntry entry : initialState.readCache.keySet()) {
395 forwardEndLiveLocations.add(entry.identity);
396 }
397 for (ReadCacheEntry entry : mergedStates.readCache.keySet()) {
398 forwardEndLiveLocations.remove(entry.identity);
399 }
400 // every location that is alive before the loop but not after is killed by the
401 // loop
402 for (LocationIdentity location : forwardEndLiveLocations) {
403 loopKilledLocations.rememberLoopKilledLocation(location);
404 }
405 if (Debug.isLogEnabled() && loopKilledLocations != null) {
406 Debug.log("[Early Read Elimination] Setting loop killed locations of loop at node %s with %s",
407 loop.getHeader().getBeginNode(), forwardEndLiveLocations);
408 }
409 }
410 // remember the loop visit
411 loopKilledLocations.visited();
412 }
413 }
414 }
415
416 @Override
417 protected PEReadEliminationBlockState stripKilledLoopLocations(Loop<Block> loop, PEReadEliminationBlockState originalInitialState) {
418 PEReadEliminationBlockState initialState = super.stripKilledLoopLocations(loop, originalInitialState);
419 LoopKillCache loopKilledLocations = loopLocationKillCache.get(loop);
420 if (loopKilledLocations != null && loopKilledLocations.loopKillsLocations()) {
421 Set<ReadCacheEntry> forwardEndLiveLocations = initialState.readCache.keySet();
422 Iterator<ReadCacheEntry> it = forwardEndLiveLocations.iterator();
423 while (it.hasNext()) {
424 ReadCacheEntry entry = it.next();
425 if (loopKilledLocations.containsLocation(entry.identity)) {
426 it.remove();
427 }
428 }
429 }
430 return initialState;
431 }
432
433 }