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