--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.virtual/src/org/graalvm/compiler/virtual/phases/ea/PEReadEliminationClosure.java Thu Feb 16 15:46:09 2017 -0800
@@ -0,0 +1,433 @@
+/*
+ * Copyright (c) 2011, 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package org.graalvm.compiler.virtual.phases.ea;
+
+import static org.graalvm.compiler.core.common.GraalOptions.ReadEliminationMaxLoopVisits;
+import static org.graalvm.compiler.nodes.NamedLocationIdentity.ARRAY_LENGTH_LOCATION;
+
+import java.util.ArrayList;
+import java.util.EnumMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.graalvm.compiler.core.common.LocationIdentity;
+import org.graalvm.compiler.core.common.cfg.Loop;
+import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
+import org.graalvm.compiler.debug.Debug;
+import org.graalvm.compiler.graph.Node;
+import org.graalvm.compiler.nodes.FieldLocationIdentity;
+import org.graalvm.compiler.nodes.FixedNode;
+import org.graalvm.compiler.nodes.FixedWithNextNode;
+import org.graalvm.compiler.nodes.LoopBeginNode;
+import org.graalvm.compiler.nodes.LoopExitNode;
+import org.graalvm.compiler.nodes.NamedLocationIdentity;
+import org.graalvm.compiler.nodes.PhiNode;
+import org.graalvm.compiler.nodes.ProxyNode;
+import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
+import org.graalvm.compiler.nodes.ValueNode;
+import org.graalvm.compiler.nodes.ValueProxyNode;
+import org.graalvm.compiler.nodes.cfg.Block;
+import org.graalvm.compiler.nodes.extended.UnboxNode;
+import org.graalvm.compiler.nodes.extended.UnsafeLoadNode;
+import org.graalvm.compiler.nodes.extended.UnsafeStoreNode;
+import org.graalvm.compiler.nodes.java.ArrayLengthNode;
+import org.graalvm.compiler.nodes.java.LoadFieldNode;
+import org.graalvm.compiler.nodes.java.LoadIndexedNode;
+import org.graalvm.compiler.nodes.java.StoreFieldNode;
+import org.graalvm.compiler.nodes.java.StoreIndexedNode;
+import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;
+import org.graalvm.compiler.nodes.spi.LoweringProvider;
+import org.graalvm.compiler.nodes.type.StampTool;
+import org.graalvm.compiler.nodes.util.GraphUtil;
+import org.graalvm.compiler.nodes.virtual.VirtualArrayNode;
+import org.graalvm.compiler.virtual.phases.ea.PEReadEliminationBlockState.ReadCacheEntry;
+
+import jdk.vm.ci.meta.ConstantReflectionProvider;
+import jdk.vm.ci.meta.JavaConstant;
+import jdk.vm.ci.meta.JavaKind;
+import jdk.vm.ci.meta.MetaAccessProvider;
+import jdk.vm.ci.meta.ResolvedJavaType;
+
+public class PEReadEliminationClosure extends PartialEscapeClosure<PEReadEliminationBlockState> {
+
+ private static final EnumMap<JavaKind, LocationIdentity> UNBOX_LOCATIONS;
+
+ static {
+ UNBOX_LOCATIONS = new EnumMap<>(JavaKind.class);
+ for (JavaKind kind : JavaKind.values()) {
+ UNBOX_LOCATIONS.put(kind, NamedLocationIdentity.immutable("PEA unbox " + kind.getJavaName()));
+ }
+ }
+
+ public PEReadEliminationClosure(ScheduleResult schedule, MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider,
+ LoweringProvider loweringProvider) {
+ super(schedule, metaAccess, constantReflection, constantFieldProvider, loweringProvider);
+ }
+
+ @Override
+ protected PEReadEliminationBlockState getInitialState() {
+ return new PEReadEliminationBlockState();
+ }
+
+ @Override
+ protected boolean processNode(Node node, PEReadEliminationBlockState state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
+ if (super.processNode(node, state, effects, lastFixedNode)) {
+ return true;
+ }
+
+ if (node instanceof LoadFieldNode) {
+ return processLoadField((LoadFieldNode) node, state, effects);
+ } else if (node instanceof StoreFieldNode) {
+ return processStoreField((StoreFieldNode) node, state, effects);
+ } else if (node instanceof LoadIndexedNode) {
+ return processLoadIndexed((LoadIndexedNode) node, state, effects);
+ } else if (node instanceof StoreIndexedNode) {
+ return processStoreIndexed((StoreIndexedNode) node, state, effects);
+ } else if (node instanceof ArrayLengthNode) {
+ return processArrayLength((ArrayLengthNode) node, state, effects);
+ } else if (node instanceof UnboxNode) {
+ return processUnbox((UnboxNode) node, state, effects);
+ } else if (node instanceof UnsafeLoadNode) {
+ return processUnsafeLoad((UnsafeLoadNode) node, state, effects);
+ } else if (node instanceof UnsafeStoreNode) {
+ return processUnsafeStore((UnsafeStoreNode) node, state, effects);
+ } else if (node instanceof MemoryCheckpoint.Single) {
+ COUNTER_MEMORYCHECKPOINT.increment();
+ LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
+ processIdentity(state, identity);
+ } else if (node instanceof MemoryCheckpoint.Multi) {
+ COUNTER_MEMORYCHECKPOINT.increment();
+ for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
+ processIdentity(state, identity);
+ }
+ }
+
+ return false;
+ }
+
+ private boolean processStore(FixedNode store, ValueNode object, LocationIdentity identity, int index, ValueNode value, PEReadEliminationBlockState state, GraphEffectList effects) {
+ ValueNode unproxiedObject = GraphUtil.unproxify(object);
+ ValueNode cachedValue = state.getReadCache(object, identity, index, this);
+
+ ValueNode finalValue = getScalarAlias(value);
+ boolean result = false;
+ if (GraphUtil.unproxify(finalValue) == GraphUtil.unproxify(cachedValue)) {
+ effects.deleteNode(store);
+ result = true;
+ }
+ state.killReadCache(identity, index);
+ state.addReadCache(unproxiedObject, identity, index, finalValue, this);
+ return result;
+ }
+
+ private boolean processLoad(FixedNode load, ValueNode object, LocationIdentity identity, int index, PEReadEliminationBlockState state, GraphEffectList effects) {
+ ValueNode unproxiedObject = GraphUtil.unproxify(object);
+ ValueNode cachedValue = state.getReadCache(unproxiedObject, identity, index, this);
+ if (cachedValue != null) {
+ effects.replaceAtUsages(load, cachedValue);
+ addScalarAlias(load, cachedValue);
+ return true;
+ } else {
+ state.addReadCache(unproxiedObject, identity, index, load, this);
+ return false;
+ }
+ }
+
+ private boolean processUnsafeLoad(UnsafeLoadNode load, PEReadEliminationBlockState state, GraphEffectList effects) {
+ if (load.offset().isConstant()) {
+ ResolvedJavaType type = StampTool.typeOrNull(load.object());
+ if (type != null && type.isArray()) {
+ long offset = load.offset().asJavaConstant().asLong();
+ int index = VirtualArrayNode.entryIndexForOffset(offset, load.accessKind(), type.getComponentType(), Integer.MAX_VALUE);
+ ValueNode object = GraphUtil.unproxify(load.object());
+ LocationIdentity location = NamedLocationIdentity.getArrayLocation(type.getComponentType().getJavaKind());
+ ValueNode cachedValue = state.getReadCache(object, location, index, this);
+ if (cachedValue != null && load.stamp().isCompatible(cachedValue.stamp())) {
+ effects.replaceAtUsages(load, cachedValue);
+ addScalarAlias(load, cachedValue);
+ return true;
+ } else {
+ state.addReadCache(object, location, index, load, this);
+ }
+ }
+ }
+ return false;
+ }
+
+ private boolean processUnsafeStore(UnsafeStoreNode store, PEReadEliminationBlockState state, GraphEffectList effects) {
+ ResolvedJavaType type = StampTool.typeOrNull(store.object());
+ if (type != null && type.isArray()) {
+ LocationIdentity location = NamedLocationIdentity.getArrayLocation(type.getComponentType().getJavaKind());
+ if (store.offset().isConstant()) {
+ long offset = store.offset().asJavaConstant().asLong();
+ int index = VirtualArrayNode.entryIndexForOffset(offset, store.accessKind(), type.getComponentType(), Integer.MAX_VALUE);
+ return processStore(store, store.object(), location, index, store.value(), state, effects);
+ } else {
+ processIdentity(state, location);
+ }
+ } else {
+ state.killReadCache();
+ }
+ return false;
+ }
+
+ private boolean processArrayLength(ArrayLengthNode length, PEReadEliminationBlockState state, GraphEffectList effects) {
+ return processLoad(length, length.array(), ARRAY_LENGTH_LOCATION, -1, state, effects);
+ }
+
+ private boolean processStoreField(StoreFieldNode store, PEReadEliminationBlockState state, GraphEffectList effects) {
+ if (store.isVolatile()) {
+ state.killReadCache();
+ return false;
+ }
+ return processStore(store, store.object(), new FieldLocationIdentity(store.field()), -1, store.value(), state, effects);
+ }
+
+ private boolean processLoadField(LoadFieldNode load, PEReadEliminationBlockState state, GraphEffectList effects) {
+ if (load.isVolatile()) {
+ state.killReadCache();
+ return false;
+ }
+ return processLoad(load, load.object(), new FieldLocationIdentity(load.field()), -1, state, effects);
+ }
+
+ private boolean processStoreIndexed(StoreIndexedNode store, PEReadEliminationBlockState state, GraphEffectList effects) {
+ LocationIdentity arrayLocation = NamedLocationIdentity.getArrayLocation(store.elementKind());
+ if (store.index().isConstant()) {
+ int index = ((JavaConstant) store.index().asConstant()).asInt();
+ return processStore(store, store.array(), arrayLocation, index, store.value(), state, effects);
+ } else {
+ state.killReadCache(arrayLocation, -1);
+ }
+ return false;
+ }
+
+ private boolean processLoadIndexed(LoadIndexedNode load, PEReadEliminationBlockState state, GraphEffectList effects) {
+ if (load.index().isConstant()) {
+ int index = ((JavaConstant) load.index().asConstant()).asInt();
+ LocationIdentity arrayLocation = NamedLocationIdentity.getArrayLocation(load.elementKind());
+ return processLoad(load, load.array(), arrayLocation, index, state, effects);
+ }
+ return false;
+ }
+
+ private boolean processUnbox(UnboxNode unbox, PEReadEliminationBlockState state, GraphEffectList effects) {
+ return processLoad(unbox, unbox.getValue(), UNBOX_LOCATIONS.get(unbox.getBoxingKind()), -1, state, effects);
+ }
+
+ private static void processIdentity(PEReadEliminationBlockState state, LocationIdentity identity) {
+ if (identity.isAny()) {
+ state.killReadCache();
+ } else {
+ state.killReadCache(identity, -1);
+ }
+ }
+
+ @Override
+ protected void processInitialLoopState(Loop<Block> loop, PEReadEliminationBlockState initialState) {
+ super.processInitialLoopState(loop, initialState);
+
+ for (PhiNode phi : ((LoopBeginNode) loop.getHeader().getBeginNode()).phis()) {
+ ValueNode firstValue = phi.valueAt(0);
+ if (firstValue != null) {
+ firstValue = GraphUtil.unproxify(firstValue);
+ for (Map.Entry<ReadCacheEntry, ValueNode> entry : new ArrayList<>(initialState.getReadCache().entrySet())) {
+ if (entry.getKey().object == firstValue) {
+ initialState.addReadCache(phi, entry.getKey().identity, entry.getKey().index, entry.getValue(), this);
+ }
+ }
+ }
+ }
+ }
+
+ @Override
+ protected void processLoopExit(LoopExitNode exitNode, PEReadEliminationBlockState initialState, PEReadEliminationBlockState exitState, GraphEffectList effects) {
+ super.processLoopExit(exitNode, initialState, exitState, effects);
+
+ if (exitNode.graph().hasValueProxies()) {
+ for (Map.Entry<ReadCacheEntry, ValueNode> entry : exitState.getReadCache().entrySet()) {
+ if (initialState.getReadCache().get(entry.getKey()) != entry.getValue()) {
+ ValueNode value = exitState.getReadCache(entry.getKey().object, entry.getKey().identity, entry.getKey().index, this);
+ assert value != null : "Got null from read cache, entry's value:" + entry.getValue();
+ if (!(value instanceof ProxyNode) || ((ProxyNode) value).proxyPoint() != exitNode) {
+ ProxyNode proxy = new ValueProxyNode(value, exitNode);
+ effects.addFloatingNode(proxy, "readCacheProxy");
+ entry.setValue(proxy);
+ }
+ }
+ }
+ }
+ }
+
+ @Override
+ protected PEReadEliminationBlockState cloneState(PEReadEliminationBlockState other) {
+ return new PEReadEliminationBlockState(other);
+ }
+
+ @Override
+ protected MergeProcessor createMergeProcessor(Block merge) {
+ return new ReadEliminationMergeProcessor(merge);
+ }
+
+ private class ReadEliminationMergeProcessor extends MergeProcessor {
+
+ ReadEliminationMergeProcessor(Block mergeBlock) {
+ super(mergeBlock);
+ }
+
+ @Override
+ protected void merge(List<PEReadEliminationBlockState> states) {
+ super.merge(states);
+
+ mergeReadCache(states);
+ }
+
+ private void mergeReadCache(List<PEReadEliminationBlockState> states) {
+ for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
+ ReadCacheEntry key = entry.getKey();
+ ValueNode value = entry.getValue();
+ boolean phi = false;
+ for (int i = 1; i < states.size(); i++) {
+ ValueNode otherValue = states.get(i).readCache.get(key);
+ // e.g. unsafe loads / stores with different access kinds have different stamps
+ // although location, object and offset are the same, in this case we cannot
+ // create a phi nor can we set a common value
+ if (otherValue == null || !value.stamp().isCompatible(otherValue.stamp())) {
+ value = null;
+ phi = false;
+ break;
+ }
+ if (!phi && otherValue != value) {
+ phi = true;
+ }
+ }
+ if (phi) {
+ PhiNode phiNode = getPhi(entry, value.stamp().unrestricted());
+ mergeEffects.addFloatingNode(phiNode, "mergeReadCache");
+ for (int i = 0; i < states.size(); i++) {
+ ValueNode v = states.get(i).getReadCache(key.object, key.identity, key.index, PEReadEliminationClosure.this);
+ assert phiNode.stamp().isCompatible(v.stamp()) : "Cannot create read elimination phi for inputs with incompatible stamps.";
+ setPhiInput(phiNode, i, v);
+ }
+ newState.readCache.put(key, phiNode);
+ } else if (value != null) {
+ newState.readCache.put(key, value);
+ }
+ }
+ for (PhiNode phi : getPhis()) {
+ if (phi.getStackKind() == JavaKind.Object) {
+ for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
+ if (entry.getKey().object == getPhiValueAt(phi, 0)) {
+ mergeReadCachePhi(phi, entry.getKey().identity, entry.getKey().index, states);
+ }
+ }
+ }
+ }
+ }
+
+ private void mergeReadCachePhi(PhiNode phi, LocationIdentity identity, int index, List<PEReadEliminationBlockState> states) {
+ ValueNode[] values = new ValueNode[states.size()];
+ values[0] = states.get(0).getReadCache(getPhiValueAt(phi, 0), identity, index, PEReadEliminationClosure.this);
+ if (values[0] != null) {
+ for (int i = 1; i < states.size(); i++) {
+ ValueNode value = states.get(i).getReadCache(getPhiValueAt(phi, i), identity, index, PEReadEliminationClosure.this);
+ // e.g. unsafe loads / stores with same identity and different access kinds see
+ // mergeReadCache(states)
+ if (value == null || !values[i - 1].stamp().isCompatible(value.stamp())) {
+ return;
+ }
+ values[i] = value;
+ }
+
+ PhiNode phiNode = getPhi(new ReadCacheEntry(identity, phi, index), values[0].stamp().unrestricted());
+ mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi");
+ for (int i = 0; i < values.length; i++) {
+ setPhiInput(phiNode, i, values[i]);
+ }
+ newState.readCache.put(new ReadCacheEntry(identity, phi, index), phiNode);
+ }
+ }
+ }
+
+ @Override
+ protected void processKilledLoopLocations(Loop<Block> loop, PEReadEliminationBlockState initialState, PEReadEliminationBlockState mergedStates) {
+ assert initialState != null;
+ assert mergedStates != null;
+ if (initialState.readCache.size() > 0) {
+ LoopKillCache loopKilledLocations = loopLocationKillCache.get(loop);
+ // we have fully processed this loop the first time, remember to cache it the next time
+ // it is visited
+ if (loopKilledLocations == null) {
+ loopKilledLocations = new LoopKillCache(1/* 1.visit */);
+ loopLocationKillCache.put(loop, loopKilledLocations);
+ } else {
+ if (loopKilledLocations.visits() > ReadEliminationMaxLoopVisits.getValue()) {
+ // we have processed the loop too many times, kill all locations so the inner
+ // loop will never be processed more than once again on visit
+ loopKilledLocations.setKillsAll();
+ } else {
+ // we have fully processed this loop >1 times, update the killed locations
+ Set<LocationIdentity> forwardEndLiveLocations = new HashSet<>();
+ for (ReadCacheEntry entry : initialState.readCache.keySet()) {
+ forwardEndLiveLocations.add(entry.identity);
+ }
+ for (ReadCacheEntry entry : mergedStates.readCache.keySet()) {
+ forwardEndLiveLocations.remove(entry.identity);
+ }
+ // every location that is alive before the loop but not after is killed by the
+ // loop
+ for (LocationIdentity location : forwardEndLiveLocations) {
+ loopKilledLocations.rememberLoopKilledLocation(location);
+ }
+ if (Debug.isLogEnabled() && loopKilledLocations != null) {
+ Debug.log("[Early Read Elimination] Setting loop killed locations of loop at node %s with %s",
+ loop.getHeader().getBeginNode(), forwardEndLiveLocations);
+ }
+ }
+ // remember the loop visit
+ loopKilledLocations.visited();
+ }
+ }
+ }
+
+ @Override
+ protected PEReadEliminationBlockState stripKilledLoopLocations(Loop<Block> loop, PEReadEliminationBlockState originalInitialState) {
+ PEReadEliminationBlockState initialState = super.stripKilledLoopLocations(loop, originalInitialState);
+ LoopKillCache loopKilledLocations = loopLocationKillCache.get(loop);
+ if (loopKilledLocations != null && loopKilledLocations.loopKillsLocations()) {
+ Set<ReadCacheEntry> forwardEndLiveLocations = initialState.readCache.keySet();
+ Iterator<ReadCacheEntry> it = forwardEndLiveLocations.iterator();
+ while (it.hasNext()) {
+ ReadCacheEntry entry = it.next();
+ if (loopKilledLocations.containsLocation(entry.identity)) {
+ it.remove();
+ }
+ }
+ }
+ return initialState;
+ }
+
+}