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
24
25 package org.graalvm.compiler.phases.common;
26
27 import static org.graalvm.compiler.graph.Graph.NodeEvent.NODE_ADDED;
28 import static org.graalvm.compiler.graph.Graph.NodeEvent.ZERO_USAGES;
29 import static jdk.internal.vm.compiler.word.LocationIdentity.any;
30
31 import java.util.EnumSet;
32 import java.util.Iterator;
33 import java.util.List;
34
35 import jdk.internal.vm.compiler.collections.EconomicMap;
36 import jdk.internal.vm.compiler.collections.EconomicSet;
37 import jdk.internal.vm.compiler.collections.Equivalence;
38 import jdk.internal.vm.compiler.collections.UnmodifiableMapCursor;
39 import org.graalvm.compiler.core.common.cfg.Loop;
40 import org.graalvm.compiler.debug.DebugCloseable;
41 import org.graalvm.compiler.graph.Graph.NodeEventScope;
42 import org.graalvm.compiler.graph.Node;
43 import org.graalvm.compiler.nodes.AbstractBeginNode;
44 import org.graalvm.compiler.nodes.AbstractMergeNode;
45 import org.graalvm.compiler.nodes.FixedNode;
46 import org.graalvm.compiler.nodes.InvokeWithExceptionNode;
47 import org.graalvm.compiler.nodes.LoopBeginNode;
48 import org.graalvm.compiler.nodes.LoopEndNode;
49 import org.graalvm.compiler.nodes.LoopExitNode;
50 import org.graalvm.compiler.nodes.PhiNode;
51 import org.graalvm.compiler.nodes.ReturnNode;
52 import org.graalvm.compiler.nodes.StartNode;
53 import org.graalvm.compiler.nodes.StructuredGraph;
54 import org.graalvm.compiler.nodes.ValueNodeUtil;
55 import org.graalvm.compiler.nodes.calc.FloatingNode;
56 import org.graalvm.compiler.nodes.cfg.Block;
57 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
58 import org.graalvm.compiler.nodes.cfg.HIRLoop;
59 import org.graalvm.compiler.nodes.memory.FloatableAccessNode;
60 import org.graalvm.compiler.nodes.memory.FloatingAccessNode;
61 import org.graalvm.compiler.nodes.memory.FloatingReadNode;
62 import org.graalvm.compiler.nodes.memory.MemoryAccess;
63 import org.graalvm.compiler.nodes.memory.MemoryAnchorNode;
64 import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;
65 import org.graalvm.compiler.nodes.memory.MemoryMap;
66 import org.graalvm.compiler.nodes.memory.MemoryMapNode;
67 import org.graalvm.compiler.nodes.memory.MemoryNode;
68 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
69 import org.graalvm.compiler.nodes.memory.ReadNode;
70 import org.graalvm.compiler.nodes.util.GraphUtil;
71 import org.graalvm.compiler.phases.Phase;
72 import org.graalvm.compiler.phases.common.util.EconomicSetNodeEventListener;
73 import org.graalvm.compiler.phases.graph.ReentrantNodeIterator;
74 import org.graalvm.compiler.phases.graph.ReentrantNodeIterator.LoopInfo;
75 import org.graalvm.compiler.phases.graph.ReentrantNodeIterator.NodeIteratorClosure;
76 import jdk.internal.vm.compiler.word.LocationIdentity;
77
78 public class FloatingReadPhase extends Phase {
79
80 private boolean createFloatingReads;
81 private boolean createMemoryMapNodes;
82
83 public static class MemoryMapImpl implements MemoryMap {
84
85 private final EconomicMap<LocationIdentity, MemoryNode> lastMemorySnapshot;
86
87 public MemoryMapImpl(MemoryMapImpl memoryMap) {
88 lastMemorySnapshot = EconomicMap.create(Equivalence.DEFAULT, memoryMap.lastMemorySnapshot);
89 }
90
91 public MemoryMapImpl(StartNode start) {
92 this();
93 lastMemorySnapshot.put(any(), start);
94 }
95
96 public MemoryMapImpl() {
97 lastMemorySnapshot = EconomicMap.create(Equivalence.DEFAULT);
98 }
99
100 @Override
101 public MemoryNode getLastLocationAccess(LocationIdentity locationIdentity) {
102 MemoryNode lastLocationAccess;
103 if (locationIdentity.isImmutable()) {
104 return null;
105 } else {
106 lastLocationAccess = lastMemorySnapshot.get(locationIdentity);
107 if (lastLocationAccess == null) {
108 lastLocationAccess = lastMemorySnapshot.get(any());
109 assert lastLocationAccess != null;
110 }
111 return lastLocationAccess;
112 }
113 }
114
115 @Override
116 public Iterable<LocationIdentity> getLocations() {
117 return lastMemorySnapshot.getKeys();
118 }
119
120 public EconomicMap<LocationIdentity, MemoryNode> getMap() {
121 return lastMemorySnapshot;
122 }
123 }
124
125 public FloatingReadPhase() {
126 this(true, false);
127 }
128
129 /**
130 * @param createFloatingReads specifies whether {@link FloatableAccessNode}s like
131 * {@link ReadNode} should be converted into floating nodes (e.g.,
132 * {@link FloatingReadNode}s) where possible
133 * @param createMemoryMapNodes a {@link MemoryMapNode} will be created for each return if this
134 * is true
135 */
136 public FloatingReadPhase(boolean createFloatingReads, boolean createMemoryMapNodes) {
137 this.createFloatingReads = createFloatingReads;
138 this.createMemoryMapNodes = createMemoryMapNodes;
139 }
140
141 @Override
142 public float codeSizeIncrease() {
143 return 1.25f;
144 }
145
146 /**
147 * Removes nodes from a given set that (transitively) have a usage outside the set.
148 */
149 private static EconomicSet<Node> removeExternallyUsedNodes(EconomicSet<Node> set) {
150 boolean change;
151 do {
152 change = false;
153 for (Iterator<Node> iter = set.iterator(); iter.hasNext();) {
154 Node node = iter.next();
155 for (Node usage : node.usages()) {
156 if (!set.contains(usage)) {
157 change = true;
158 iter.remove();
159 break;
160 }
161 }
162 }
163 } while (change);
164 return set;
165 }
166
167 protected void processNode(FixedNode node, EconomicSet<LocationIdentity> currentState) {
168 if (node instanceof MemoryCheckpoint.Single) {
169 processIdentity(currentState, ((MemoryCheckpoint.Single) node).getLocationIdentity());
170 } else if (node instanceof MemoryCheckpoint.Multi) {
171 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
172 processIdentity(currentState, identity);
173 }
174 }
175 }
176
177 private static void processIdentity(EconomicSet<LocationIdentity> currentState, LocationIdentity identity) {
178 if (identity.isMutable()) {
179 currentState.add(identity);
180 }
181 }
182
183 protected void processBlock(Block b, EconomicSet<LocationIdentity> currentState) {
184 for (FixedNode n : b.getNodes()) {
185 processNode(n, currentState);
186 }
187 }
188
189 private EconomicSet<LocationIdentity> processLoop(HIRLoop loop, EconomicMap<LoopBeginNode, EconomicSet<LocationIdentity>> modifiedInLoops) {
190 LoopBeginNode loopBegin = (LoopBeginNode) loop.getHeader().getBeginNode();
191 EconomicSet<LocationIdentity> result = modifiedInLoops.get(loopBegin);
192 if (result != null) {
193 return result;
194 }
195
196 result = EconomicSet.create(Equivalence.DEFAULT);
197 for (Loop<Block> inner : loop.getChildren()) {
198 result.addAll(processLoop((HIRLoop) inner, modifiedInLoops));
199 }
200
201 for (Block b : loop.getBlocks()) {
202 if (b.getLoop() == loop) {
203 processBlock(b, result);
204 }
205 }
206
207 modifiedInLoops.put(loopBegin, result);
208 return result;
209 }
210
211 @Override
212 @SuppressWarnings("try")
213 protected void run(StructuredGraph graph) {
214 EconomicMap<LoopBeginNode, EconomicSet<LocationIdentity>> modifiedInLoops = null;
215 if (graph.hasLoops()) {
216 modifiedInLoops = EconomicMap.create(Equivalence.IDENTITY);
217 ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false);
218 for (Loop<?> l : cfg.getLoops()) {
219 HIRLoop loop = (HIRLoop) l;
220 processLoop(loop, modifiedInLoops);
221 }
222 }
223
224 EconomicSetNodeEventListener listener = new EconomicSetNodeEventListener(EnumSet.of(NODE_ADDED, ZERO_USAGES));
225 try (NodeEventScope nes = graph.trackNodeEvents(listener)) {
226 ReentrantNodeIterator.apply(new FloatingReadClosure(modifiedInLoops, createFloatingReads, createMemoryMapNodes), graph.start(), new MemoryMapImpl(graph.start()));
227 }
228
229 for (Node n : removeExternallyUsedNodes(listener.getNodes())) {
230 if (n.isAlive() && n instanceof FloatingNode) {
231 n.replaceAtUsages(null);
232 GraphUtil.killWithUnusedFloatingInputs(n);
233 }
234 }
235 if (createFloatingReads) {
236 assert !graph.isAfterFloatingReadPhase();
237 graph.setAfterFloatingReadPhase(true);
238 }
239 }
240
241 public static MemoryMapImpl mergeMemoryMaps(AbstractMergeNode merge, List<? extends MemoryMap> states) {
242 MemoryMapImpl newState = new MemoryMapImpl();
243
244 EconomicSet<LocationIdentity> keys = EconomicSet.create(Equivalence.DEFAULT);
245 for (MemoryMap other : states) {
246 keys.addAll(other.getLocations());
247 }
248 assert checkNoImmutableLocations(keys);
249
250 for (LocationIdentity key : keys) {
251 int mergedStatesCount = 0;
252 boolean isPhi = false;
253 MemoryNode merged = null;
254 for (MemoryMap state : states) {
255 MemoryNode last = state.getLastLocationAccess(key);
256 if (isPhi) {
257 ((MemoryPhiNode) merged).addInput(ValueNodeUtil.asNode(last));
258 } else {
259 if (merged == last) {
260 // nothing to do
261 } else if (merged == null) {
262 merged = last;
263 } else {
264 MemoryPhiNode phi = merge.graph().addWithoutUnique(new MemoryPhiNode(merge, key));
265 for (int j = 0; j < mergedStatesCount; j++) {
266 phi.addInput(ValueNodeUtil.asNode(merged));
267 }
268 phi.addInput(ValueNodeUtil.asNode(last));
269 merged = phi;
270 isPhi = true;
271 }
272 }
273 mergedStatesCount++;
274 }
275 newState.lastMemorySnapshot.put(key, merged);
276 }
277 return newState;
278
279 }
280
281 private static boolean checkNoImmutableLocations(EconomicSet<LocationIdentity> keys) {
282 keys.forEach(t -> {
283 assert t.isMutable();
284 });
285 return true;
286 }
287
288 public static class FloatingReadClosure extends NodeIteratorClosure<MemoryMapImpl> {
289
290 private final EconomicMap<LoopBeginNode, EconomicSet<LocationIdentity>> modifiedInLoops;
291 private boolean createFloatingReads;
292 private boolean createMemoryMapNodes;
293
294 public FloatingReadClosure(EconomicMap<LoopBeginNode, EconomicSet<LocationIdentity>> modifiedInLoops, boolean createFloatingReads, boolean createMemoryMapNodes) {
295 this.modifiedInLoops = modifiedInLoops;
296 this.createFloatingReads = createFloatingReads;
297 this.createMemoryMapNodes = createMemoryMapNodes;
298 }
299
300 @Override
301 protected MemoryMapImpl processNode(FixedNode node, MemoryMapImpl state) {
302 if (node instanceof MemoryAnchorNode) {
303 processAnchor((MemoryAnchorNode) node, state);
304 return state;
305 }
306
307 if (node instanceof MemoryAccess) {
308 processAccess((MemoryAccess) node, state);
309 }
310
311 if (createFloatingReads && node instanceof FloatableAccessNode) {
312 processFloatable((FloatableAccessNode) node, state);
313 } else if (node instanceof MemoryCheckpoint.Single) {
314 processCheckpoint((MemoryCheckpoint.Single) node, state);
315 } else if (node instanceof MemoryCheckpoint.Multi) {
316 processCheckpoint((MemoryCheckpoint.Multi) node, state);
317 }
318 assert MemoryCheckpoint.TypeAssertion.correctType(node) : node;
319
320 if (createMemoryMapNodes && node instanceof ReturnNode) {
321 ((ReturnNode) node).setMemoryMap(node.graph().unique(new MemoryMapNode(state.lastMemorySnapshot)));
322 }
323 return state;
324 }
325
326 /**
327 * Improve the memory graph by re-wiring all usages of a {@link MemoryAnchorNode} to the
328 * real last access location.
329 */
330 private static void processAnchor(MemoryAnchorNode anchor, MemoryMapImpl state) {
331 for (Node node : anchor.usages().snapshot()) {
332 if (node instanceof MemoryAccess) {
333 MemoryAccess access = (MemoryAccess) node;
334 if (access.getLastLocationAccess() == anchor) {
335 MemoryNode lastLocationAccess = state.getLastLocationAccess(access.getLocationIdentity());
336 assert lastLocationAccess != null;
337 access.setLastLocationAccess(lastLocationAccess);
338 }
339 }
340 }
341
342 if (anchor.hasNoUsages()) {
343 anchor.graph().removeFixed(anchor);
344 }
345 }
346
347 private static void processAccess(MemoryAccess access, MemoryMapImpl state) {
348 LocationIdentity locationIdentity = access.getLocationIdentity();
349 if (!locationIdentity.equals(LocationIdentity.any())) {
350 MemoryNode lastLocationAccess = state.getLastLocationAccess(locationIdentity);
351 access.setLastLocationAccess(lastLocationAccess);
352 }
353 }
354
355 private static void processCheckpoint(MemoryCheckpoint.Single checkpoint, MemoryMapImpl state) {
356 processIdentity(checkpoint.getLocationIdentity(), checkpoint, state);
357 }
358
359 private static void processCheckpoint(MemoryCheckpoint.Multi checkpoint, MemoryMapImpl state) {
360 for (LocationIdentity identity : checkpoint.getLocationIdentities()) {
361 processIdentity(identity, checkpoint, state);
362 }
363 }
364
365 private static void processIdentity(LocationIdentity identity, MemoryCheckpoint checkpoint, MemoryMapImpl state) {
366 if (identity.isAny()) {
367 state.lastMemorySnapshot.clear();
368 }
369 if (identity.isMutable()) {
370 state.lastMemorySnapshot.put(identity, checkpoint);
371 }
372 }
373
374 @SuppressWarnings("try")
375 private static void processFloatable(FloatableAccessNode accessNode, MemoryMapImpl state) {
376 StructuredGraph graph = accessNode.graph();
377 LocationIdentity locationIdentity = accessNode.getLocationIdentity();
378 if (accessNode.canFloat()) {
379 assert accessNode.getNullCheck() == false;
380 MemoryNode lastLocationAccess = state.getLastLocationAccess(locationIdentity);
381 try (DebugCloseable position = accessNode.withNodeSourcePosition()) {
382 FloatingAccessNode floatingNode = accessNode.asFloatingNode(lastLocationAccess);
383 graph.replaceFixedWithFloating(accessNode, floatingNode);
384 }
385 }
386 }
387
388 @Override
389 protected MemoryMapImpl merge(AbstractMergeNode merge, List<MemoryMapImpl> states) {
390 return mergeMemoryMaps(merge, states);
391 }
392
393 @Override
394 protected MemoryMapImpl afterSplit(AbstractBeginNode node, MemoryMapImpl oldState) {
395 MemoryMapImpl result = new MemoryMapImpl(oldState);
396 if (node.predecessor() instanceof InvokeWithExceptionNode) {
397 /*
398 * InvokeWithException cannot be the lastLocationAccess for a FloatingReadNode.
399 * Since it is both the invoke and a control flow split, the scheduler cannot
400 * schedule anything immediately after the invoke. It can only schedule in the
401 * normal or exceptional successor - and we have to tell the scheduler here which
402 * side it needs to choose by putting in the location identity on both successors.
403 */
404 InvokeWithExceptionNode invoke = (InvokeWithExceptionNode) node.predecessor();
405 result.lastMemorySnapshot.put(invoke.getLocationIdentity(), (MemoryCheckpoint) node);
406 }
407 return result;
408 }
409
410 @Override
411 protected EconomicMap<LoopExitNode, MemoryMapImpl> processLoop(LoopBeginNode loop, MemoryMapImpl initialState) {
412 EconomicSet<LocationIdentity> modifiedLocations = modifiedInLoops.get(loop);
413 EconomicMap<LocationIdentity, MemoryPhiNode> phis = EconomicMap.create(Equivalence.DEFAULT);
414 if (modifiedLocations.contains(LocationIdentity.any())) {
415 // create phis for all locations if ANY is modified in the loop
416 modifiedLocations = EconomicSet.create(Equivalence.DEFAULT, modifiedLocations);
417 modifiedLocations.addAll(initialState.lastMemorySnapshot.getKeys());
418 }
419
420 for (LocationIdentity location : modifiedLocations) {
421 createMemoryPhi(loop, initialState, phis, location);
422 }
423 initialState.lastMemorySnapshot.putAll(phis);
424
425 LoopInfo<MemoryMapImpl> loopInfo = ReentrantNodeIterator.processLoop(this, loop, initialState);
426
427 UnmodifiableMapCursor<LoopEndNode, MemoryMapImpl> endStateCursor = loopInfo.endStates.getEntries();
428 while (endStateCursor.advance()) {
429 int endIndex = loop.phiPredecessorIndex(endStateCursor.getKey());
430 UnmodifiableMapCursor<LocationIdentity, MemoryPhiNode> phiCursor = phis.getEntries();
431 while (phiCursor.advance()) {
432 LocationIdentity key = phiCursor.getKey();
433 PhiNode phi = phiCursor.getValue();
434 phi.initializeValueAt(endIndex, ValueNodeUtil.asNode(endStateCursor.getValue().getLastLocationAccess(key)));
435 }
436 }
437 return loopInfo.exitStates;
438 }
439
440 private static void createMemoryPhi(LoopBeginNode loop, MemoryMapImpl initialState, EconomicMap<LocationIdentity, MemoryPhiNode> phis, LocationIdentity location) {
441 MemoryPhiNode phi = loop.graph().addWithoutUnique(new MemoryPhiNode(loop, location));
442 phi.addInput(ValueNodeUtil.asNode(initialState.getLastLocationAccess(location)));
443 phis.put(location, phi);
444 }
445 }
446 }