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, JavaKind accessKind, boolean overflowAccess, ValueNode value,
 134                     PEReadEliminationBlockState state, GraphEffectList effects) {
 135         ValueNode unproxiedObject = GraphUtil.unproxify(object);
 136         ValueNode cachedValue = state.getReadCache(object, identity, index, accessKind, this);
 137 
 138         ValueNode finalValue = getScalarAlias(value);
 139         boolean result = false;
 140         if (GraphUtil.unproxify(finalValue) == GraphUtil.unproxify(cachedValue)) {
 141             effects.deleteNode(store);
 142             result = true;
 143         }
 144         state.killReadCache(identity, index);
 145         state.addReadCache(unproxiedObject, identity, index, accessKind, overflowAccess, finalValue, this);
 146         return result;
 147     }
 148 
 149     private boolean processLoad(FixedNode load, ValueNode object, LocationIdentity identity, int index, JavaKind kind, PEReadEliminationBlockState state, GraphEffectList effects) {
 150         ValueNode unproxiedObject = GraphUtil.unproxify(object);
 151         ValueNode cachedValue = state.getReadCache(unproxiedObject, identity, index, kind, this);
 152         if (cachedValue != null) {











 153             // perform the read elimination
 154             effects.replaceAtUsages(load, cachedValue, load);
 155             addScalarAlias(load, cachedValue);
 156             return true;

 157         } else {
 158             state.addReadCache(unproxiedObject, identity, index, kind, false, load, this);
 159             return false;
 160         }
 161     }
 162 
 163     private static boolean isOverflowAccess(JavaKind accessKind, JavaKind declaredKind) {
 164         if (accessKind == declaredKind) {
 165             return false;
 166         }
 167         if (accessKind == JavaKind.Object) {
 168             switch (declaredKind) {
 169                 case Object:
 170                 case Double:
 171                 case Long:
 172                     return false;
 173                 default:
 174                     return true;
 175             }
 176         }
 177         assert accessKind.isPrimitive() : "Illegal access kind";
 178         return declaredKind.isPrimitive() ? accessKind.getBitCount() > declaredKind.getBitCount() : true;
 179     }
 180 
 181     private boolean processUnsafeLoad(RawLoadNode load, PEReadEliminationBlockState state, GraphEffectList effects) {
 182         if (load.offset().isConstant()) {
 183             ResolvedJavaType type = StampTool.typeOrNull(load.object());
 184             if (type != null && type.isArray()) {
 185                 JavaKind accessKind = load.accessKind();
 186                 JavaKind componentKind = type.getComponentType().getJavaKind();
 187                 long offset = load.offset().asJavaConstant().asLong();
 188                 int index = VirtualArrayNode.entryIndexForOffset(offset, accessKind, type.getComponentType(), Integer.MAX_VALUE);
 189                 ValueNode object = GraphUtil.unproxify(load.object());
 190                 LocationIdentity location = NamedLocationIdentity.getArrayLocation(componentKind);
 191                 ValueNode cachedValue = state.getReadCache(object, location, index, accessKind, this);
 192                 assert cachedValue == null || load.stamp().isCompatible(cachedValue.stamp()) : "The RawLoadNode's stamp is not compatible with the cached value.";
 193                 if (cachedValue != null) {
 194                     effects.replaceAtUsages(load, cachedValue, load);
 195                     addScalarAlias(load, cachedValue);
 196                     return true;
 197                 } else {
 198                     state.addReadCache(object, location, index, accessKind, isOverflowAccess(accessKind, componentKind), load, this);
 199                 }
 200             }
 201         }
 202         return false;
 203     }
 204 
 205     private boolean processUnsafeStore(RawStoreNode store, PEReadEliminationBlockState state, GraphEffectList effects) {
 206         ResolvedJavaType type = StampTool.typeOrNull(store.object());
 207         if (type != null && type.isArray()) {
 208             JavaKind accessKind = store.accessKind();
 209             JavaKind componentKind = type.getComponentType().getJavaKind();
 210             LocationIdentity location = NamedLocationIdentity.getArrayLocation(componentKind);
 211             if (store.offset().isConstant()) {
 212                 long offset = store.offset().asJavaConstant().asLong();
 213                 boolean overflowAccess = isOverflowAccess(accessKind, componentKind);
 214                 int index = overflowAccess ? -1 : VirtualArrayNode.entryIndexForOffset(offset, accessKind, type.getComponentType(), Integer.MAX_VALUE);
 215                 return processStore(store, store.object(), location, index, accessKind, overflowAccess, store.value(), state, effects);
 216             } else {
 217                 processIdentity(state, location);
 218             }
 219         } else {
 220             state.killReadCache();
 221         }
 222         return false;
 223     }
 224 
 225     private boolean processArrayLength(ArrayLengthNode length, PEReadEliminationBlockState state, GraphEffectList effects) {
 226         return processLoad(length, length.array(), ARRAY_LENGTH_LOCATION, -1, JavaKind.Int, state, effects);
 227     }
 228 
 229     private boolean processStoreField(StoreFieldNode store, PEReadEliminationBlockState state, GraphEffectList effects) {
 230         if (store.isVolatile()) {
 231             state.killReadCache();
 232             return false;
 233         }
 234         JavaKind kind = store.field().getJavaKind();
 235         return processStore(store, store.object(), new FieldLocationIdentity(store.field()), -1, kind, false, store.value(), state, effects);
 236     }
 237 
 238     private boolean processLoadField(LoadFieldNode load, PEReadEliminationBlockState state, GraphEffectList effects) {
 239         if (load.isVolatile()) {
 240             state.killReadCache();
 241             return false;
 242         }
 243         return processLoad(load, load.object(), new FieldLocationIdentity(load.field()), -1, load.field().getJavaKind(), state, effects);
 244     }
 245 
 246     private static JavaKind getElementKindFromStamp(ValueNode array) {
 247         ResolvedJavaType type = StampTool.typeOrNull(array);
 248         if (type != null && type.isArray()) {
 249             return type.getComponentType().getJavaKind();
 250         } else {
 251             // It is likely an OSRLocal without valid stamp
 252             return JavaKind.Illegal;
 253         }
 254     }
 255 
 256     private boolean processStoreIndexed(StoreIndexedNode store, PEReadEliminationBlockState state, GraphEffectList effects) {
 257         int index = store.index().isConstant() ? ((JavaConstant) store.index().asConstant()).asInt() : -1;
 258         // BASTORE (with elementKind being Byte) can be used to store values in boolean arrays.
 259         JavaKind elementKind = store.elementKind();
 260         if (elementKind == JavaKind.Byte) {
 261             elementKind = getElementKindFromStamp(store.array());
 262             if (elementKind == JavaKind.Illegal) {
 263                 // Could not determine the actual access kind from stamp. Hence kill both.
 264                 state.killReadCache(NamedLocationIdentity.getArrayLocation(JavaKind.Boolean), index);
 265                 state.killReadCache(NamedLocationIdentity.getArrayLocation(JavaKind.Byte), index);
 266                 return false;
 267             }
 268         }
 269         LocationIdentity arrayLocation = NamedLocationIdentity.getArrayLocation(elementKind);
 270         if (index != -1) {
 271             return processStore(store, store.array(), arrayLocation, index, elementKind, false, store.value(), state, effects);
 272         } else {
 273             state.killReadCache(arrayLocation, -1);
 274         }
 275         return false;
 276     }
 277 
 278     private boolean processLoadIndexed(LoadIndexedNode load, PEReadEliminationBlockState state, GraphEffectList effects) {
 279         if (load.index().isConstant()) {
 280             int index = ((JavaConstant) load.index().asConstant()).asInt();
 281             // BALOAD (with elementKind being Byte) can be used to retrieve values from boolean
 282             // arrays.
 283             JavaKind elementKind = load.elementKind();
 284             if (elementKind == JavaKind.Byte) {
 285                 elementKind = getElementKindFromStamp(load.array());
 286                 if (elementKind == JavaKind.Illegal) {
 287                     return false;
 288                 }
 289             }
 290             LocationIdentity arrayLocation = NamedLocationIdentity.getArrayLocation(elementKind);
 291             return processLoad(load, load.array(), arrayLocation, index, elementKind, state, effects);
 292         }
 293         return false;
 294     }
 295 
 296     private boolean processUnbox(UnboxNode unbox, PEReadEliminationBlockState state, GraphEffectList effects) {
 297         return processLoad(unbox, unbox.getValue(), UNBOX_LOCATIONS.get(unbox.getBoxingKind()), -1, unbox.getBoxingKind(), state, effects);
 298     }
 299 
 300     private static void processIdentity(PEReadEliminationBlockState state, LocationIdentity identity) {
 301         if (identity.isAny()) {
 302             state.killReadCache();
 303         } else {
 304             state.killReadCache(identity, -1);
 305         }
 306     }
 307 
 308     @SuppressWarnings("unchecked")
 309     @Override
 310     protected void processInitialLoopState(Loop<Block> loop, PEReadEliminationBlockState initialState) {
 311         super.processInitialLoopState(loop, initialState);
 312 
 313         if (!initialState.getReadCache().isEmpty()) {
 314             EconomicMap<ValueNode, Pair<ValueNode, Object>> firstValueSet = null;
 315             for (PhiNode phi : ((LoopBeginNode) loop.getHeader().getBeginNode()).phis()) {
 316                 ValueNode firstValue = phi.valueAt(0);
 317                 if (firstValue != null && phi.getStackKind().isObject()) {
 318                     ValueNode unproxified = GraphUtil.unproxify(firstValue);
 319                     if (firstValueSet == null) {
 320                         firstValueSet = EconomicMap.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE);
 321                     }
 322                     Pair<ValueNode, Object> pair = Pair.create(unproxified, firstValueSet.get(unproxified));
 323                     firstValueSet.put(unproxified, pair);
 324                 }
 325             }
 326 
 327             if (firstValueSet != null) {
 328                 ReadCacheEntry[] entries = new ReadCacheEntry[initialState.getReadCache().size()];
 329                 int z = 0;
 330                 for (ReadCacheEntry entry : initialState.getReadCache().getKeys()) {
 331                     entries[z++] = entry;
 332                 }
 333 
 334                 for (ReadCacheEntry entry : entries) {
 335                     ValueNode object = entry.object;
 336                     if (object != null) {
 337                         Pair<ValueNode, Object> pair = firstValueSet.get(object);
 338                         while (pair != null) {
 339                             initialState.addReadCache(pair.getLeft(), entry.identity, entry.index, entry.kind, entry.overflowAccess, initialState.getReadCache().get(entry), this);
 340                             pair = (Pair<ValueNode, Object>) pair.getRight();
 341                         }
 342                     }
 343                 }
 344             }
 345         }
 346     }
 347 
 348     @Override
 349     protected void processLoopExit(LoopExitNode exitNode, PEReadEliminationBlockState initialState, PEReadEliminationBlockState exitState, GraphEffectList effects) {
 350         super.processLoopExit(exitNode, initialState, exitState, effects);
 351 
 352         if (exitNode.graph().hasValueProxies()) {
 353             MapCursor<ReadCacheEntry, ValueNode> entry = exitState.getReadCache().getEntries();
 354             while (entry.advance()) {
 355                 if (initialState.getReadCache().get(entry.getKey()) != entry.getValue()) {
 356                     ValueNode value = exitState.getReadCache(entry.getKey().object, entry.getKey().identity, entry.getKey().index, entry.getKey().kind, this);
 357                     assert value != null : "Got null from read cache, entry's value:" + entry.getValue();
 358                     if (!(value instanceof ProxyNode) || ((ProxyNode) value).proxyPoint() != exitNode) {
 359                         ProxyNode proxy = new ValueProxyNode(value, exitNode);
 360                         effects.addFloatingNode(proxy, "readCacheProxy");
 361                         exitState.getReadCache().put(entry.getKey(), proxy);
 362                     }
 363                 }
 364             }
 365         }
 366     }
 367 
 368     @Override
 369     protected PEReadEliminationBlockState cloneState(PEReadEliminationBlockState other) {
 370         return new PEReadEliminationBlockState(other);
 371     }
 372 
 373     @Override
 374     protected MergeProcessor createMergeProcessor(Block merge) {
 375         return new ReadEliminationMergeProcessor(merge);
 376     }
 377 
 378     private class ReadEliminationMergeProcessor extends MergeProcessor {
 379 
 380         ReadEliminationMergeProcessor(Block mergeBlock) {
 381             super(mergeBlock);
 382         }
 383 
 384         @Override
 385         protected void merge(List<PEReadEliminationBlockState> states) {
 386             super.merge(states);
 387 
 388             mergeReadCache(states);
 389         }
 390 
 391         private void mergeReadCache(List<PEReadEliminationBlockState> states) {
 392             MapCursor<ReadCacheEntry, ValueNode> cursor = states.get(0).readCache.getEntries();
 393             while (cursor.advance()) {
 394                 ReadCacheEntry key = cursor.getKey();
 395                 ValueNode value = cursor.getValue();
 396                 boolean phi = false;
 397                 for (int i = 1; i < states.size(); i++) {
 398                     ValueNode otherValue = states.get(i).readCache.get(key);
 399                     // e.g. unsafe loads / stores with different access kinds have different stamps
 400                     // although location, object and offset are the same, in this case we cannot
 401                     // create a phi nor can we set a common value
 402                     if (otherValue == null || !value.stamp().isCompatible(otherValue.stamp())) {
 403                         value = null;
 404                         phi = false;
 405                         break;
 406                     }
 407                     if (!phi && otherValue != value) {
 408                         phi = true;
 409                     }
 410                 }
 411                 if (phi) {
 412                     PhiNode phiNode = getPhi(key, value.stamp().unrestricted());
 413                     mergeEffects.addFloatingNode(phiNode, "mergeReadCache");
 414                     for (int i = 0; i < states.size(); i++) {
 415                         ValueNode v = states.get(i).getReadCache(key.object, key.identity, key.index, key.kind, PEReadEliminationClosure.this);
 416                         assert phiNode.stamp().isCompatible(v.stamp()) : "Cannot create read elimination phi for inputs with incompatible stamps.";
 417                         setPhiInput(phiNode, i, v);
 418                     }
 419                     newState.readCache.put(key, phiNode);
 420                 } else if (value != null) {
 421                     newState.readCache.put(key, value);
 422                 }
 423             }
 424             /*
 425              * For object phis, see if there are known reads on all predecessors, for which we could
 426              * create new phis.
 427              */
 428             for (PhiNode phi : getPhis()) {
 429                 if (phi.getStackKind() == JavaKind.Object) {
 430                     for (ReadCacheEntry entry : states.get(0).readCache.getKeys()) {
 431                         if (entry.object == getPhiValueAt(phi, 0)) {
 432                             mergeReadCachePhi(phi, entry.identity, entry.index, entry.kind, entry.overflowAccess, states);
 433                         }
 434                     }
 435                 }
 436             }
 437         }
 438 
 439         private void mergeReadCachePhi(PhiNode phi, LocationIdentity identity, int index, JavaKind kind, boolean overflowAccess, List<PEReadEliminationBlockState> states) {
 440             ValueNode[] values = new ValueNode[states.size()];
 441             values[0] = states.get(0).getReadCache(getPhiValueAt(phi, 0), identity, index, kind, PEReadEliminationClosure.this);
 442             if (values[0] != null) {
 443                 for (int i = 1; i < states.size(); i++) {
 444                     ValueNode value = states.get(i).getReadCache(getPhiValueAt(phi, i), identity, index, kind, PEReadEliminationClosure.this);
 445                     // e.g. unsafe loads / stores with same identity and different access kinds see
 446                     // mergeReadCache(states)
 447                     if (value == null || !values[i - 1].stamp().isCompatible(value.stamp())) {
 448                         return;
 449                     }
 450                     values[i] = value;
 451                 }
 452 
 453                 PhiNode phiNode = getPhi(new ReadCacheEntry(identity, phi, index, kind, overflowAccess), values[0].stamp().unrestricted());
 454                 mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi");
 455                 for (int i = 0; i < values.length; i++) {
 456                     setPhiInput(phiNode, i, values[i]);
 457                 }
 458                 newState.readCache.put(new ReadCacheEntry(identity, phi, index, kind, overflowAccess), phiNode);
 459             }
 460         }
 461     }
 462 
 463     @Override
 464     protected void processKilledLoopLocations(Loop<Block> loop, PEReadEliminationBlockState initialState, PEReadEliminationBlockState mergedStates) {
 465         assert initialState != null;
 466         assert mergedStates != null;
 467         if (initialState.readCache.size() > 0) {
 468             LoopKillCache loopKilledLocations = loopLocationKillCache.get(loop);
 469             // we have fully processed this loop the first time, remember to cache it the next time
 470             // it is visited
 471             if (loopKilledLocations == null) {
 472                 loopKilledLocations = new LoopKillCache(1/* 1.visit */);
 473                 loopLocationKillCache.put(loop, loopKilledLocations);
 474             } else {
 475                 AbstractBeginNode beginNode = loop.getHeader().getBeginNode();
 476                 OptionValues options = beginNode.getOptions();
 477                 if (loopKilledLocations.visits() > ReadEliminationMaxLoopVisits.getValue(options)) {
 478                     // we have processed the loop too many times, kill all locations so the inner
 479                     // loop will never be processed more than once again on visit
 480                     loopKilledLocations.setKillsAll();
 481                 } else {
 482                     // we have fully processed this loop >1 times, update the killed locations
 483                     EconomicSet<LocationIdentity> forwardEndLiveLocations = EconomicSet.create(Equivalence.DEFAULT);
 484                     for (ReadCacheEntry entry : initialState.readCache.getKeys()) {
 485                         forwardEndLiveLocations.add(entry.identity);
 486                     }
 487                     for (ReadCacheEntry entry : mergedStates.readCache.getKeys()) {
 488                         forwardEndLiveLocations.remove(entry.identity);
 489                     }
 490                     // every location that is alive before the loop but not after is killed by the
 491                     // loop
 492                     for (LocationIdentity location : forwardEndLiveLocations) {
 493                         loopKilledLocations.rememberLoopKilledLocation(location);
 494                     }
 495                     if (debug.isLogEnabled() && loopKilledLocations != null) {
 496                         debug.log("[Early Read Elimination] Setting loop killed locations of loop at node %s with %s",
 497                                         beginNode, forwardEndLiveLocations);
 498                     }
 499                 }
 500                 // remember the loop visit
 501                 loopKilledLocations.visited();
 502             }
 503         }
 504     }
 505 
 506     @Override
 507     protected PEReadEliminationBlockState stripKilledLoopLocations(Loop<Block> loop, PEReadEliminationBlockState originalInitialState) {
 508         PEReadEliminationBlockState initialState = super.stripKilledLoopLocations(loop, originalInitialState);
 509         LoopKillCache loopKilledLocations = loopLocationKillCache.get(loop);
 510         if (loopKilledLocations != null && loopKilledLocations.loopKillsLocations()) {
 511             Iterator<ReadCacheEntry> it = initialState.readCache.getKeys().iterator();
 512             while (it.hasNext()) {
 513                 ReadCacheEntry entry = it.next();
 514                 if (loopKilledLocations.containsLocation(entry.identity)) {
 515                     it.remove();
 516                 }
 517             }
 518         }
 519         return initialState;
 520     }
 521 
 522 }
--- EOF ---