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.debug.Debug;
35 import org.graalvm.compiler.graph.Node;
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.UnboxNode;
49 import org.graalvm.compiler.nodes.extended.RawLoadNode;
50 import org.graalvm.compiler.nodes.extended.RawStoreNode;
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;
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());
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();
121 LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
122 processIdentity(state, identity);
123 } else if (node instanceof MemoryCheckpoint.Multi) {
124 COUNTER_MEMORYCHECKPOINT.increment();
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);
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 OptionValues options = loop.getHeader().getBeginNode().getOptions();
430 if (loopKilledLocations.visits() > ReadEliminationMaxLoopVisits.getValue(options)) {
431 // we have processed the loop too many times, kill all locations so the inner
432 // loop will never be processed more than once again on visit
433 loopKilledLocations.setKillsAll();
434 } else {
435 // we have fully processed this loop >1 times, update the killed locations
436 EconomicSet<LocationIdentity> forwardEndLiveLocations = EconomicSet.create(Equivalence.DEFAULT);
437 for (ReadCacheEntry entry : initialState.readCache.getKeys()) {
438 forwardEndLiveLocations.add(entry.identity);
439 }
440 for (ReadCacheEntry entry : mergedStates.readCache.getKeys()) {
441 forwardEndLiveLocations.remove(entry.identity);
442 }
443 // every location that is alive before the loop but not after is killed by the
444 // loop
445 for (LocationIdentity location : forwardEndLiveLocations) {
446 loopKilledLocations.rememberLoopKilledLocation(location);
447 }
448 if (Debug.isLogEnabled() && loopKilledLocations != null) {
449 Debug.log("[Early Read Elimination] Setting loop killed locations of loop at node %s with %s",
450 loop.getHeader().getBeginNode(), forwardEndLiveLocations);
451 }
452 }
453 // remember the loop visit
454 loopKilledLocations.visited();
455 }
456 }
457 }
458
459 @Override
460 protected PEReadEliminationBlockState stripKilledLoopLocations(Loop<Block> loop, PEReadEliminationBlockState originalInitialState) {
461 PEReadEliminationBlockState initialState = super.stripKilledLoopLocations(loop, originalInitialState);
462 LoopKillCache loopKilledLocations = loopLocationKillCache.get(loop);
463 if (loopKilledLocations != null && loopKilledLocations.loopKillsLocations()) {
464 Iterator<ReadCacheEntry> it = initialState.readCache.getKeys().iterator();
465 while (it.hasNext()) {
466 ReadCacheEntry entry = it.next();
467 if (loopKilledLocations.containsLocation(entry.identity)) {
468 it.remove();
469 }
470 }
|
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;
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);
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 }
|