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