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