1 /*
   2  * Copyright (c) 2011, 2017, 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.word.LocationIdentity.any;
  27 
  28 import java.util.Iterator;
  29 import java.util.List;
  30 
  31 import jdk.vm.ci.meta.ResolvedJavaType;
  32 import org.graalvm.compiler.core.common.cfg.Loop;
  33 import org.graalvm.compiler.core.common.type.Stamp;
  34 import org.graalvm.compiler.graph.Node;
  35 import org.graalvm.compiler.nodes.FieldLocationIdentity;
  36 import org.graalvm.compiler.nodes.FixedWithNextNode;
  37 import org.graalvm.compiler.nodes.LoopExitNode;
  38 import org.graalvm.compiler.nodes.PhiNode;
  39 import org.graalvm.compiler.nodes.ProxyNode;
  40 import org.graalvm.compiler.nodes.ValueNode;
  41 import org.graalvm.compiler.nodes.ValuePhiNode;
  42 import org.graalvm.compiler.nodes.ValueProxyNode;
  43 import org.graalvm.compiler.nodes.cfg.Block;
  44 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
  45 import org.graalvm.compiler.nodes.extended.GuardedNode;
  46 import org.graalvm.compiler.nodes.extended.GuardingNode;
  47 import org.graalvm.compiler.nodes.extended.RawLoadNode;
  48 import org.graalvm.compiler.nodes.extended.RawStoreNode;
  49 import org.graalvm.compiler.nodes.extended.UnsafeAccessNode;
  50 import org.graalvm.compiler.nodes.java.AccessFieldNode;
  51 import org.graalvm.compiler.nodes.java.LoadFieldNode;
  52 import org.graalvm.compiler.nodes.java.StoreFieldNode;
  53 import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;
  54 import org.graalvm.compiler.nodes.memory.ReadNode;
  55 import org.graalvm.compiler.nodes.memory.WriteNode;
  56 import org.graalvm.compiler.nodes.type.StampTool;
  57 import org.graalvm.compiler.nodes.util.GraphUtil;
  58 import org.graalvm.compiler.options.OptionValues;
  59 import org.graalvm.compiler.virtual.phases.ea.ReadEliminationBlockState.CacheEntry;
  60 import org.graalvm.compiler.virtual.phases.ea.ReadEliminationBlockState.LoadCacheEntry;
  61 import org.graalvm.compiler.virtual.phases.ea.ReadEliminationBlockState.UnsafeLoadCacheEntry;
  62 import org.graalvm.util.EconomicMap;
  63 import org.graalvm.util.EconomicSet;
  64 import org.graalvm.util.Equivalence;
  65 import org.graalvm.util.MapCursor;
  66 import org.graalvm.word.LocationIdentity;
  67 
  68 import jdk.vm.ci.meta.JavaKind;
  69 
  70 /**
  71  * This closure initially handled a set of nodes that is disjunct from
  72  * {@link PEReadEliminationClosure}, but over time both have evolved so that there's a significant
  73  * overlap.
  74  */
  75 public final class ReadEliminationClosure extends EffectsClosure<ReadEliminationBlockState> {
  76     private final boolean considerGuards;
  77 
  78     public ReadEliminationClosure(ControlFlowGraph cfg, boolean considerGuards) {
  79         super(null, cfg);
  80         this.considerGuards = considerGuards;
  81     }
  82 
  83     @Override
  84     protected ReadEliminationBlockState getInitialState() {
  85         return new ReadEliminationBlockState();
  86     }
  87 
  88     @Override
  89     protected boolean processNode(Node node, ReadEliminationBlockState state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
  90         boolean deleted = false;
  91         if (node instanceof AccessFieldNode) {
  92             AccessFieldNode access = (AccessFieldNode) node;
  93             if (access.isVolatile()) {
  94                 processIdentity(state, any());
  95             } else {
  96                 ValueNode object = GraphUtil.unproxify(access.object());
  97                 LoadCacheEntry identifier = new LoadCacheEntry(object, new FieldLocationIdentity(access.field()));
  98                 ValueNode cachedValue = state.getCacheEntry(identifier);
  99                 if (node instanceof LoadFieldNode) {
 100                     if (cachedValue != null && access.stamp().isCompatible(cachedValue.stamp())) {
 101                         effects.replaceAtUsages(access, cachedValue, access);
 102                         addScalarAlias(access, cachedValue);
 103                         deleted = true;
 104                     } else {
 105                         state.addCacheEntry(identifier, access);
 106                     }
 107                 } else {
 108                     assert node instanceof StoreFieldNode;
 109                     StoreFieldNode store = (StoreFieldNode) node;
 110                     ValueNode value = getScalarAlias(store.value());
 111                     if (GraphUtil.unproxify(value) == GraphUtil.unproxify(cachedValue)) {
 112                         effects.deleteNode(store);
 113                         deleted = true;
 114                     }
 115                     state.killReadCache(identifier.identity);
 116                     state.addCacheEntry(identifier, value);
 117                 }
 118             }
 119         } else if (node instanceof ReadNode) {
 120             ReadNode read = (ReadNode) node;
 121             if (read.getLocationIdentity().isSingle()) {
 122                 ValueNode object = GraphUtil.unproxify(read.getAddress());
 123                 LoadCacheEntry identifier = new LoadCacheEntry(object, read.getLocationIdentity());
 124                 ValueNode cachedValue = state.getCacheEntry(identifier);
 125                 if (cachedValue != null && areValuesReplaceable(read, cachedValue, considerGuards)) {
 126                     effects.replaceAtUsages(read, cachedValue, read);
 127                     addScalarAlias(read, cachedValue);
 128                     deleted = true;
 129                 } else {
 130                     state.addCacheEntry(identifier, read);
 131                 }
 132             }
 133         } else if (node instanceof WriteNode) {
 134             WriteNode write = (WriteNode) node;
 135             if (write.getLocationIdentity().isSingle()) {
 136                 ValueNode object = GraphUtil.unproxify(write.getAddress());
 137                 LoadCacheEntry identifier = new LoadCacheEntry(object, write.getLocationIdentity());
 138                 ValueNode cachedValue = state.getCacheEntry(identifier);
 139 
 140                 ValueNode value = getScalarAlias(write.value());
 141                 if (GraphUtil.unproxify(value) == GraphUtil.unproxify(cachedValue)) {
 142                     effects.deleteNode(write);
 143                     deleted = true;
 144                 }
 145                 processIdentity(state, write.getLocationIdentity());
 146                 state.addCacheEntry(identifier, value);
 147             } else {
 148                 processIdentity(state, write.getLocationIdentity());
 149             }
 150         } else if (node instanceof UnsafeAccessNode) {
 151             ResolvedJavaType type = StampTool.typeOrNull(((UnsafeAccessNode) node).object());
 152             if (type != null && !type.isArray()) {
 153                 if (node instanceof RawLoadNode) {
 154                     RawLoadNode load = (RawLoadNode) node;
 155                     if (load.getLocationIdentity().isSingle()) {
 156                         ValueNode object = GraphUtil.unproxify(load.object());
 157                         UnsafeLoadCacheEntry identifier = new UnsafeLoadCacheEntry(object, load.offset(), load.getLocationIdentity());
 158                         ValueNode cachedValue = state.getCacheEntry(identifier);
 159                         if (cachedValue != null && areValuesReplaceable(load, cachedValue, considerGuards)) {
 160                             effects.replaceAtUsages(load, cachedValue, load);
 161                             addScalarAlias(load, cachedValue);
 162                             deleted = true;
 163                         } else {
 164                             state.addCacheEntry(identifier, load);
 165                         }
 166                     }
 167                 } else {
 168                     assert node instanceof RawStoreNode;
 169                     RawStoreNode write = (RawStoreNode) node;
 170                     if (write.getLocationIdentity().isSingle()) {
 171                         ValueNode object = GraphUtil.unproxify(write.object());
 172                         UnsafeLoadCacheEntry identifier = new UnsafeLoadCacheEntry(object, write.offset(), write.getLocationIdentity());
 173                         ValueNode cachedValue = state.getCacheEntry(identifier);
 174 
 175                         ValueNode value = getScalarAlias(write.value());
 176                         if (GraphUtil.unproxify(value) == GraphUtil.unproxify(cachedValue)) {
 177                             effects.deleteNode(write);
 178                             deleted = true;
 179                         }
 180                         processIdentity(state, write.getLocationIdentity());
 181                         state.addCacheEntry(identifier, value);
 182                     } else {
 183                         processIdentity(state, write.getLocationIdentity());
 184                     }
 185                 }
 186             }
 187         } else if (node instanceof MemoryCheckpoint.Single) {
 188             LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
 189             processIdentity(state, identity);
 190         } else if (node instanceof MemoryCheckpoint.Multi) {
 191             for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
 192                 processIdentity(state, identity);
 193             }
 194         }
 195         return deleted;
 196     }
 197 
 198     private static boolean areValuesReplaceable(ValueNode originalValue, ValueNode replacementValue, boolean considerGuards) {
 199         return originalValue.stamp().isCompatible(replacementValue.stamp()) &&
 200                         (!considerGuards || (getGuard(originalValue) == null || getGuard(originalValue) == getGuard(replacementValue)));
 201     }
 202 
 203     private static GuardingNode getGuard(ValueNode node) {
 204         if (node instanceof GuardedNode) {
 205             GuardedNode guardedNode = (GuardedNode) node;
 206             return guardedNode.getGuard();
 207         }
 208         return null;
 209     }
 210 
 211     private static void processIdentity(ReadEliminationBlockState state, LocationIdentity identity) {
 212         if (identity.isAny()) {
 213             state.killReadCache();
 214             return;
 215         }
 216         state.killReadCache(identity);
 217     }
 218 
 219     @Override
 220     protected void processLoopExit(LoopExitNode exitNode, ReadEliminationBlockState initialState, ReadEliminationBlockState exitState, GraphEffectList effects) {
 221         if (exitNode.graph().hasValueProxies()) {
 222             MapCursor<CacheEntry<?>, ValueNode> entry = exitState.getReadCache().getEntries();
 223             while (entry.advance()) {
 224                 if (initialState.getReadCache().get(entry.getKey()) != entry.getValue()) {
 225                     ProxyNode proxy = new ValueProxyNode(exitState.getCacheEntry(entry.getKey()), exitNode);
 226                     effects.addFloatingNode(proxy, "readCacheProxy");
 227                     exitState.getReadCache().put(entry.getKey(), proxy);
 228                 }
 229             }
 230         }
 231     }
 232 
 233     @Override
 234     protected ReadEliminationBlockState cloneState(ReadEliminationBlockState other) {
 235         return new ReadEliminationBlockState(other);
 236     }
 237 
 238     @Override
 239     protected MergeProcessor createMergeProcessor(Block merge) {
 240         return new ReadEliminationMergeProcessor(merge);
 241     }
 242 
 243     private class ReadEliminationMergeProcessor extends EffectsClosure<ReadEliminationBlockState>.MergeProcessor {
 244 
 245         private final EconomicMap<Object, ValuePhiNode> materializedPhis = EconomicMap.create(Equivalence.DEFAULT);
 246 
 247         ReadEliminationMergeProcessor(Block mergeBlock) {
 248             super(mergeBlock);
 249         }
 250 
 251         protected ValuePhiNode getCachedPhi(CacheEntry<?> virtual, Stamp stamp) {
 252             ValuePhiNode result = materializedPhis.get(virtual);
 253             if (result == null) {
 254                 result = createValuePhi(stamp);
 255                 materializedPhis.put(virtual, result);
 256             }
 257             return result;
 258         }
 259 
 260         @Override
 261         protected void merge(List<ReadEliminationBlockState> states) {
 262             MapCursor<CacheEntry<?>, ValueNode> cursor = states.get(0).readCache.getEntries();
 263             while (cursor.advance()) {
 264                 CacheEntry<?> key = cursor.getKey();
 265                 ValueNode value = cursor.getValue();
 266                 boolean phi = false;
 267                 for (int i = 1; i < states.size(); i++) {
 268                     ValueNode otherValue = states.get(i).readCache.get(key);
 269                     // E.g. unsafe loads / stores with different access kinds have different stamps
 270                     // although location, object and offset are the same. In this case we cannot
 271                     // create a phi nor can we set a common value.
 272                     if (otherValue == null || !value.stamp().isCompatible(otherValue.stamp())) {
 273                         value = null;
 274                         phi = false;
 275                         break;
 276                     }
 277                     if (!phi && otherValue != value) {
 278                         phi = true;
 279                     }
 280                 }
 281                 if (phi) {
 282                     PhiNode phiNode = getCachedPhi(key, value.stamp().unrestricted());
 283                     mergeEffects.addFloatingNode(phiNode, "mergeReadCache");
 284                     for (int i = 0; i < states.size(); i++) {
 285                         ValueNode v = states.get(i).getCacheEntry(key);
 286                         assert phiNode.stamp().isCompatible(v.stamp()) : "Cannot create read elimination phi for inputs with incompatible stamps.";
 287                         setPhiInput(phiNode, i, v);
 288                     }
 289                     newState.addCacheEntry(key, phiNode);
 290                 } else if (value != null) {
 291                     // case that there is the same value on all branches
 292                     newState.addCacheEntry(key, value);
 293                 }
 294             }
 295             /*
 296              * For object phis, see if there are known reads on all predecessors, for which we could
 297              * create new phis.
 298              */
 299             for (PhiNode phi : getPhis()) {
 300                 if (phi.getStackKind() == JavaKind.Object) {
 301                     for (CacheEntry<?> entry : states.get(0).readCache.getKeys()) {
 302                         if (entry.object == getPhiValueAt(phi, 0)) {
 303                             mergeReadCachePhi(phi, entry, states);
 304                         }
 305                     }
 306                 }
 307             }
 308         }
 309 
 310         private void mergeReadCachePhi(PhiNode phi, CacheEntry<?> identifier, List<ReadEliminationBlockState> states) {
 311             ValueNode[] values = new ValueNode[states.size()];
 312             values[0] = states.get(0).getCacheEntry(identifier.duplicateWithObject(getPhiValueAt(phi, 0)));
 313             if (values[0] != null) {
 314                 for (int i = 1; i < states.size(); i++) {
 315                     ValueNode value = states.get(i).getCacheEntry(identifier.duplicateWithObject(getPhiValueAt(phi, i)));
 316                     // e.g. unsafe loads / stores with same identity and different access kinds see
 317                     // mergeReadCache(states)
 318                     if (value == null || !values[i - 1].stamp().isCompatible(value.stamp())) {
 319                         return;
 320                     }
 321                     values[i] = value;
 322                 }
 323 
 324                 CacheEntry<?> newIdentifier = identifier.duplicateWithObject(phi);
 325                 PhiNode phiNode = getCachedPhi(newIdentifier, values[0].stamp().unrestricted());
 326                 mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi");
 327                 for (int i = 0; i < values.length; i++) {
 328                     setPhiInput(phiNode, i, values[i]);
 329                 }
 330                 newState.addCacheEntry(newIdentifier, phiNode);
 331             }
 332         }
 333     }
 334 
 335     @Override
 336     protected void processKilledLoopLocations(Loop<Block> loop, ReadEliminationBlockState initialState, ReadEliminationBlockState mergedStates) {
 337         assert initialState != null;
 338         assert mergedStates != null;
 339         if (initialState.readCache.size() > 0) {
 340             LoopKillCache loopKilledLocations = loopLocationKillCache.get(loop);
 341             // we have fully processed this loop the first time, remember to cache it the next time
 342             // it is visited
 343             if (loopKilledLocations == null) {
 344                 loopKilledLocations = new LoopKillCache(1/* 1.visit */);
 345                 loopLocationKillCache.put(loop, loopKilledLocations);
 346             } else {
 347                 OptionValues options = loop.getHeader().getBeginNode().getOptions();
 348                 if (loopKilledLocations.visits() > ReadEliminationMaxLoopVisits.getValue(options)) {
 349                     // we have processed the loop too many times, kill all locations so the inner
 350                     // loop will never be processed more than once again on visit
 351                     loopKilledLocations.setKillsAll();
 352                 } else {
 353                     // we have fully processed this loop >1 times, update the killed locations
 354                     EconomicSet<LocationIdentity> forwardEndLiveLocations = EconomicSet.create(Equivalence.DEFAULT);
 355                     for (CacheEntry<?> entry : initialState.readCache.getKeys()) {
 356                         forwardEndLiveLocations.add(entry.getIdentity());
 357                     }
 358                     for (CacheEntry<?> entry : mergedStates.readCache.getKeys()) {
 359                         forwardEndLiveLocations.remove(entry.getIdentity());
 360                     }
 361                     // every location that is alive before the loop but not after is killed by the
 362                     // loop
 363                     for (LocationIdentity location : forwardEndLiveLocations) {
 364                         loopKilledLocations.rememberLoopKilledLocation(location);
 365                     }
 366                     if (debug.isLogEnabled() && loopKilledLocations != null) {
 367                         debug.log("[Early Read Elimination] Setting loop killed locations of loop at node %s with %s",
 368                                         loop.getHeader().getBeginNode(), forwardEndLiveLocations);
 369                     }
 370                 }
 371                 // remember the loop visit
 372                 loopKilledLocations.visited();
 373             }
 374         }
 375     }
 376 
 377     @Override
 378     protected ReadEliminationBlockState stripKilledLoopLocations(Loop<Block> loop, ReadEliminationBlockState originalInitialState) {
 379         ReadEliminationBlockState initialState = super.stripKilledLoopLocations(loop, originalInitialState);
 380         LoopKillCache loopKilledLocations = loopLocationKillCache.get(loop);
 381         if (loopKilledLocations != null && loopKilledLocations.loopKillsLocations()) {
 382             Iterator<CacheEntry<?>> it = initialState.readCache.getKeys().iterator();
 383             while (it.hasNext()) {
 384                 CacheEntry<?> entry = it.next();
 385                 if (loopKilledLocations.containsLocation(entry.getIdentity())) {
 386                     it.remove();
 387                 }
 388             }
 389         }
 390         return initialState;
 391     }
 392 }