1 /*
2 * Copyright (c) 2011, 2012, 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 java.util.ArrayList;
26 import java.util.HashSet;
27 import java.util.List;
28 import java.util.Map;
29 import java.util.Set;
30
31 import org.graalvm.compiler.core.common.CollectionsFactory;
32 import org.graalvm.compiler.core.common.LocationIdentity;
33 import org.graalvm.compiler.core.common.cfg.BlockMap;
34 import org.graalvm.compiler.core.common.cfg.Loop;
35 import org.graalvm.compiler.core.common.type.Stamp;
36 import org.graalvm.compiler.debug.Debug;
37 import org.graalvm.compiler.debug.GraalError;
38 import org.graalvm.compiler.debug.Indent;
39 import org.graalvm.compiler.graph.Node;
40 import org.graalvm.compiler.graph.NodeBitMap;
41 import org.graalvm.compiler.graph.NodeMap;
42 import org.graalvm.compiler.graph.iterators.NodeIterable;
43 import org.graalvm.compiler.nodes.AbstractMergeNode;
44 import org.graalvm.compiler.nodes.FixedWithNextNode;
45 import org.graalvm.compiler.nodes.IfNode;
46 import org.graalvm.compiler.nodes.LogicConstantNode;
47 import org.graalvm.compiler.nodes.LogicNode;
48 import org.graalvm.compiler.nodes.LoopBeginNode;
49 import org.graalvm.compiler.nodes.LoopExitNode;
50 import org.graalvm.compiler.nodes.PhiNode;
51 import org.graalvm.compiler.nodes.ProxyNode;
52 import org.graalvm.compiler.nodes.StructuredGraph;
53 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
54 import org.graalvm.compiler.nodes.ValueNode;
55 import org.graalvm.compiler.nodes.ValuePhiNode;
56 import org.graalvm.compiler.nodes.cfg.Block;
57 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
58 import org.graalvm.compiler.nodes.extended.BoxNode;
59 import org.graalvm.compiler.nodes.util.GraphUtil;
60 import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode;
61 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
62 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
63 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator;
64 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
65 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.LoopInfo;
66
67 public abstract class EffectsClosure<BlockT extends EffectsBlockState<BlockT>> extends EffectsPhase.Closure<BlockT> {
68
69 protected final ControlFlowGraph cfg;
70 protected final ScheduleResult schedule;
71
72 protected final NodeMap<ValueNode> aliases;
73 protected final BlockMap<GraphEffectList> blockEffects;
74 private final Map<Loop<Block>, GraphEffectList> loopMergeEffects = CollectionsFactory.newIdentityMap();
75 // Intended to be used by read-eliminating phases based on the effects phase.
76 protected final Map<Loop<Block>, LoopKillCache> loopLocationKillCache = CollectionsFactory.newIdentityMap();
77 private final Map<LoopBeginNode, BlockT> loopEntryStates = Node.newIdentityMap();
78 private final NodeBitMap hasScalarReplacedInputs;
79
80 protected boolean changed;
81
82 public EffectsClosure(ScheduleResult schedule, ControlFlowGraph cfg) {
83 this.schedule = schedule;
84 this.cfg = cfg;
85 this.aliases = cfg.graph.createNodeMap();
86 this.hasScalarReplacedInputs = cfg.graph.createNodeBitMap();
87 this.blockEffects = new BlockMap<>(cfg);
88 for (Block block : cfg.getBlocks()) {
89 blockEffects.put(block, new GraphEffectList());
90 }
91 }
92
93 @Override
94 public boolean hasChanged() {
95 return changed;
96 }
97
98 @Override
99 public void applyEffects() {
100 final StructuredGraph graph = cfg.graph;
101 final ArrayList<Node> obsoleteNodes = new ArrayList<>(0);
102 final ArrayList<GraphEffectList> effectList = new ArrayList<>();
103 BlockIteratorClosure<Void> closure = new BlockIteratorClosure<Void>() {
104
105 @Override
106 protected Void getInitialState() {
107 return null;
108 }
109
110 private void apply(GraphEffectList effects) {
111 if (effects != null && !effects.isEmpty()) {
112 effectList.add(effects);
113 }
114 }
115
116 @Override
117 protected Void processBlock(Block block, Void currentState) {
118 apply(blockEffects.get(block));
119 return currentState;
120 }
121
122 @Override
123 protected Void merge(Block merge, List<Void> states) {
124 return null;
125 }
126
127 @Override
128 protected Void cloneState(Void oldState) {
129 return oldState;
130 }
131
132 @Override
133 protected List<Void> processLoop(Loop<Block> loop, Void initialState) {
134 LoopInfo<Void> info = ReentrantBlockIterator.processLoop(this, loop, initialState);
135 apply(loopMergeEffects.get(loop));
136 return info.exitStates;
137 }
138 };
139 ReentrantBlockIterator.apply(closure, cfg.getStartBlock());
140 for (GraphEffectList effects : effectList) {
141 Debug.log(" ==== effects");
142 effects.apply(graph, obsoleteNodes, false);
143 }
144 for (GraphEffectList effects : effectList) {
145 Debug.log(" ==== cfg kill effects");
146 effects.apply(graph, obsoleteNodes, true);
147 }
148 Debug.dump(Debug.VERBOSE_LOG_LEVEL, graph, "After applying effects");
149 assert VirtualUtil.assertNonReachable(graph, obsoleteNodes);
150 for (Node node : obsoleteNodes) {
151 if (node.isAlive()) {
152 node.replaceAtUsages(null);
153 GraphUtil.killWithUnusedFloatingInputs(node);
154 }
155 }
156 }
157
158 @Override
159 protected BlockT processBlock(Block block, BlockT state) {
160 if (!state.isDead()) {
161 GraphEffectList effects = blockEffects.get(block);
162
163 if (block.getBeginNode().predecessor() instanceof IfNode) {
164 IfNode ifNode = (IfNode) block.getBeginNode().predecessor();
165 LogicNode condition = ifNode.condition();
166 Node alias = getScalarAlias(condition);
167 if (alias instanceof LogicConstantNode) {
168 LogicConstantNode constant = (LogicConstantNode) alias;
169 boolean deadBranch = constant.getValue() != (block.getBeginNode() == ifNode.trueSuccessor());
170
171 if (deadBranch) {
172 state.markAsDead();
173 effects.killIfBranch(ifNode, constant.getValue());
174 return state;
175 }
176 }
177 }
178
179 VirtualUtil.trace("\nBlock: %s, preds: %s, succ: %s (", block, block.getPredecessors(), block.getSuccessors());
180
181 FixedWithNextNode lastFixedNode = block.getBeginNode().predecessor() instanceof FixedWithNextNode ? (FixedWithNextNode) block.getBeginNode().predecessor() : null;
182 Iterable<? extends Node> nodes = schedule != null ? schedule.getBlockToNodesMap().get(block) : block.getNodes();
183 for (Node node : nodes) {
184 aliases.set(node, null);
185 if (node instanceof LoopExitNode) {
186 LoopExitNode loopExit = (LoopExitNode) node;
187 for (ProxyNode proxy : loopExit.proxies()) {
188 aliases.set(proxy, null);
189 changed |= processNode(proxy, state, effects, lastFixedNode) && isSignificantNode(node);
190 }
191 processLoopExit(loopExit, loopEntryStates.get(loopExit.loopBegin()), state, blockEffects.get(block));
192 }
193 changed |= processNode(node, state, effects, lastFixedNode) && isSignificantNode(node);
194 if (node instanceof FixedWithNextNode) {
195 lastFixedNode = (FixedWithNextNode) node;
196 }
197 if (state.isDead()) {
198 break;
199 }
200 }
201 VirtualUtil.trace(")\n end state: %s\n", state);
202 }
203 return state;
204 }
205
206 private static boolean isSignificantNode(Node node) {
207 return !(node instanceof CommitAllocationNode || node instanceof AllocatedObjectNode || node instanceof BoxNode);
208 }
209
210 /**
211 * Collects the effects of virtualizing the given node.
212 *
213 * @return {@code true} if the effects include removing the node, {@code false} otherwise.
214 */
215 protected abstract boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode);
216
217 @Override
218 protected BlockT merge(Block merge, List<BlockT> states) {
219 assert blockEffects.get(merge).isEmpty();
220 MergeProcessor processor = createMergeProcessor(merge);
221 doMergeWithoutDead(processor, states);
222 processor.commitEnds(states);
223 blockEffects.get(merge).addAll(processor.mergeEffects);
224 blockEffects.get(merge).addAll(processor.afterMergeEffects);
225 return processor.newState;
226 }
227
228 @Override
229 @SuppressWarnings("try")
230 protected final List<BlockT> processLoop(Loop<Block> loop, BlockT initialState) {
231 if (initialState.isDead()) {
232 ArrayList<BlockT> states = new ArrayList<>();
233 for (int i = 0; i < loop.getExits().size(); i++) {
234 states.add(initialState);
235 }
236 return states;
237 }
238 /*
239 * Special case nested loops: To avoid an exponential runtime for nested loops we try to
240 * only process them as little times as possible.
241 *
242 * In the first iteration of an outer most loop we go into the inner most loop(s). We run
243 * the first iteration of the inner most loop and then, if necessary, a second iteration.
244 *
245 * We return from the recursion and finish the first iteration of the outermost loop. If we
246 * have to do a second iteration in the outer most loop we go again into the inner most
247 * loop(s) but this time we already know all states that are killed by the loop so inside
248 * the loop we will only have those changes that propagate from the first iteration of the
249 * outer most loop into the current loop. We strip the initial loop state for the inner most
250 * loops and do the first iteration with the (possible) changes from outer loops. If there
251 * are no changes we only have to do 1 iteration and are done.
252 *
253 */
254 BlockT initialStateRemovedKilledLocations = stripKilledLoopLocations(loop, cloneState(initialState));
255 BlockT loopEntryState = initialStateRemovedKilledLocations;
256 BlockT lastMergedState = cloneState(initialStateRemovedKilledLocations);
257 processInitialLoopState(loop, lastMergedState);
258 MergeProcessor mergeProcessor = createMergeProcessor(loop.getHeader());
259 for (int iteration = 0; iteration < 10; iteration++) {
260 try (Indent i = Debug.logAndIndent("================== Process Loop Effects Closure: block:%s begin node:%s", loop.getHeader(), loop.getHeader().getBeginNode())) {
261 LoopInfo<BlockT> info = ReentrantBlockIterator.processLoop(this, loop, cloneState(lastMergedState));
262
263 List<BlockT> states = new ArrayList<>();
264 states.add(initialStateRemovedKilledLocations);
265 states.addAll(info.endStates);
266 doMergeWithoutDead(mergeProcessor, states);
267
268 Debug.log("MergeProcessor New State: %s", mergeProcessor.newState);
269 Debug.log("===== vs.");
270 Debug.log("Last Merged State: %s", lastMergedState);
271
272 if (mergeProcessor.newState.equivalentTo(lastMergedState)) {
273 mergeProcessor.commitEnds(states);
274
275 blockEffects.get(loop.getHeader()).insertAll(mergeProcessor.mergeEffects, 0);
276 loopMergeEffects.put(loop, mergeProcessor.afterMergeEffects);
277
278 assert info.exitStates.size() == loop.getExits().size();
279 loopEntryStates.put((LoopBeginNode) loop.getHeader().getBeginNode(), loopEntryState);
280 assert assertExitStatesNonEmpty(loop, info);
281
282 processKilledLoopLocations(loop, initialStateRemovedKilledLocations, mergeProcessor.newState);
283 return info.exitStates;
284 } else {
285 lastMergedState = mergeProcessor.newState;
286 for (Block block : loop.getBlocks()) {
287 blockEffects.get(block).clear();
288 }
289 }
290 }
291 }
292 throw new GraalError("too many iterations at %s", loop);
293 }
294
295 @SuppressWarnings("unused")
296 protected BlockT stripKilledLoopLocations(Loop<Block> loop, BlockT initialState) {
297 return initialState;
298 }
299
300 @SuppressWarnings("unused")
301 protected void processKilledLoopLocations(Loop<Block> loop, BlockT initialState, BlockT mergedStates) {
302 // nothing to do
303 }
304
305 @SuppressWarnings("unused")
306 protected void processInitialLoopState(Loop<Block> loop, BlockT initialState) {
307 // nothing to do
308 }
309
310 private void doMergeWithoutDead(MergeProcessor mergeProcessor, List<BlockT> states) {
311 int alive = 0;
312 for (BlockT state : states) {
313 if (!state.isDead()) {
314 alive++;
315 }
316 }
317 if (alive == 0) {
318 mergeProcessor.setNewState(states.get(0));
319 } else if (alive == states.size()) {
320 int[] stateIndexes = new int[states.size()];
321 for (int i = 0; i < stateIndexes.length; i++) {
322 stateIndexes[i] = i;
323 }
324 mergeProcessor.setStateIndexes(stateIndexes);
325 mergeProcessor.merge(states);
326 } else {
327 ArrayList<BlockT> aliveStates = new ArrayList<>(alive);
328 int[] stateIndexes = new int[alive];
329 for (int i = 0; i < states.size(); i++) {
330 if (!states.get(i).isDead()) {
331 stateIndexes[aliveStates.size()] = i;
332 aliveStates.add(states.get(i));
333 }
334 }
335 mergeProcessor.setStateIndexes(stateIndexes);
336 mergeProcessor.merge(aliveStates);
337 }
338 }
339
340 private boolean assertExitStatesNonEmpty(Loop<Block> loop, LoopInfo<BlockT> info) {
341 for (int i = 0; i < loop.getExits().size(); i++) {
342 assert info.exitStates.get(i) != null : "no loop exit state at " + loop.getExits().get(i) + " / " + loop.getHeader();
343 }
344 return true;
345 }
346
347 protected abstract void processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects);
348
349 protected abstract MergeProcessor createMergeProcessor(Block merge);
350
351 protected class MergeProcessor {
352
353 private final Block mergeBlock;
354 private final AbstractMergeNode merge;
355
356 protected final GraphEffectList mergeEffects;
357 protected final GraphEffectList afterMergeEffects;
358
359 private int[] stateIndexes;
360 protected BlockT newState;
361
362 public MergeProcessor(Block mergeBlock) {
363 this.mergeBlock = mergeBlock;
364 this.merge = (AbstractMergeNode) mergeBlock.getBeginNode();
365 this.mergeEffects = new GraphEffectList();
366 this.afterMergeEffects = new GraphEffectList();
367 }
368
369 /**
370 * @param states the states that should be merged.
371 */
372 protected void merge(List<BlockT> states) {
373 setNewState(getInitialState());
374 }
375
376 private void setNewState(BlockT state) {
377 newState = state;
378 mergeEffects.clear();
379 afterMergeEffects.clear();
380 }
381
382 private void setStateIndexes(int[] stateIndexes) {
383 this.stateIndexes = stateIndexes;
384 }
385
386 @SuppressWarnings("unused")
387 protected void commitEnds(List<BlockT> states) {
388 }
389
390 protected final Block getPredecessor(int index) {
391 return mergeBlock.getPredecessors()[stateIndexes[index]];
392 }
393
394 protected final NodeIterable<PhiNode> getPhis() {
395 return merge.phis();
396 }
397
398 protected final ValueNode getPhiValueAt(PhiNode phi, int index) {
399 return phi.valueAt(stateIndexes[index]);
400 }
401
402 protected final ValuePhiNode createValuePhi(Stamp stamp) {
403 return new ValuePhiNode(stamp, merge, new ValueNode[mergeBlock.getPredecessorCount()]);
404 }
405
406 protected final void setPhiInput(PhiNode phi, int index, ValueNode value) {
407 afterMergeEffects.initializePhiInput(phi, stateIndexes[index], value);
408 }
409
410 protected final int getStateIndex(int i) {
411 return stateIndexes[i];
412 }
413
414 protected final StructuredGraph graph() {
415 return merge.graph();
416 }
417
418 @Override
419 public String toString() {
420 return "MergeProcessor@" + merge;
421 }
422 }
423
424 public void addScalarAlias(ValueNode node, ValueNode alias) {
425 assert !(alias instanceof VirtualObjectNode);
426 aliases.set(node, alias);
427 for (Node usage : node.usages()) {
428 if (!hasScalarReplacedInputs.isNew(usage)) {
429 hasScalarReplacedInputs.mark(usage);
430 }
431 }
432 }
433
434 protected final boolean hasScalarReplacedInputs(Node node) {
435 return hasScalarReplacedInputs.isMarked(node);
436 }
437
438 public ValueNode getScalarAlias(ValueNode node) {
439 assert !(node instanceof VirtualObjectNode);
440 if (node == null || !node.isAlive() || aliases.isNew(node)) {
441 return node;
442 }
443 ValueNode result = aliases.get(node);
444 return (result == null || result instanceof VirtualObjectNode) ? node : result;
445 }
446
447 protected static class LoopKillCache {
448 private int visits;
449 private LocationIdentity firstLocation;
450 private Set<LocationIdentity> killedLocations;
451 private boolean killsAll;
452
453 protected LoopKillCache(int visits) {
454 this.visits = visits;
455 }
456
457 protected void visited() {
458 visits++;
459 }
460
461 protected int visits() {
462 return visits;
463 }
464
465 protected void setKillsAll() {
466 killsAll = true;
467 firstLocation = null;
468 killedLocations = null;
469 }
470
471 protected boolean containsLocation(LocationIdentity locationIdentity) {
472 if (killsAll) {
473 return true;
474 }
475 if (firstLocation == null) {
476 return false;
477 }
478 if (!firstLocation.equals(locationIdentity)) {
479 return killedLocations != null ? killedLocations.contains(locationIdentity) : false;
480 }
481 return true;
482 }
483
484 protected void rememberLoopKilledLocation(LocationIdentity locationIdentity) {
485 if (killsAll) {
486 return;
487 }
488 if (firstLocation == null || firstLocation.equals(locationIdentity)) {
489 firstLocation = locationIdentity;
490 } else {
491 if (killedLocations == null) {
492 killedLocations = new HashSet<>();
493 }
494 killedLocations.add(locationIdentity);
495 }
496 }
497
498 protected boolean loopKillsLocations() {
499 if (killsAll) {
500 return true;
501 }
502 return firstLocation != null;
503 }
504 }
505
506 }