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 java.util.ArrayList;
26 import java.util.List;
27
28 import org.graalvm.compiler.core.common.cfg.BlockMap;
29 import org.graalvm.compiler.core.common.cfg.Loop;
30 import org.graalvm.compiler.core.common.type.Stamp;
31 import org.graalvm.compiler.debug.DebugContext;
32 import org.graalvm.compiler.debug.GraalError;
33 import org.graalvm.compiler.debug.Indent;
34 import org.graalvm.compiler.graph.Node;
35 import org.graalvm.compiler.graph.NodeBitMap;
36 import org.graalvm.compiler.graph.NodeMap;
37 import org.graalvm.compiler.graph.iterators.NodeIterable;
38 import org.graalvm.compiler.nodes.AbstractMergeNode;
39 import org.graalvm.compiler.nodes.FixedWithNextNode;
40 import org.graalvm.compiler.nodes.IfNode;
41 import org.graalvm.compiler.nodes.LogicConstantNode;
42 import org.graalvm.compiler.nodes.LogicNode;
43 import org.graalvm.compiler.nodes.LoopBeginNode;
44 import org.graalvm.compiler.nodes.LoopExitNode;
45 import org.graalvm.compiler.nodes.PhiNode;
46 import org.graalvm.compiler.nodes.ProxyNode;
47 import org.graalvm.compiler.nodes.StructuredGraph;
48 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
49 import org.graalvm.compiler.nodes.ValueNode;
50 import org.graalvm.compiler.nodes.ValuePhiNode;
51 import org.graalvm.compiler.nodes.cfg.Block;
52 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
53 import org.graalvm.compiler.nodes.extended.BoxNode;
54 import org.graalvm.compiler.nodes.util.GraphUtil;
55 import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode;
56 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
57 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
58 import org.graalvm.compiler.options.OptionValues;
59 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator;
60 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
61 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.LoopInfo;
62 import org.graalvm.util.EconomicMap;
63 import org.graalvm.util.EconomicSet;
64 import org.graalvm.util.Equivalence;
65 import org.graalvm.word.LocationIdentity;
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 /**
73 * If a node has an alias, this means that it was replaced with another node during analysis.
74 * Nodes can be replaced by normal ("scalar") nodes, e.g., a LoadIndexedNode with a
75 * ConstantNode, or by virtual nodes, e.g., a NewInstanceNode with a VirtualInstanceNode. A node
76 * was replaced with a virtual value iff the alias is a subclass of VirtualObjectNode.
77 *
78 * This alias map exists only once and is not part of the block state, so that during iterative
79 * loop processing the alias of a node may be changed to another value.
80 */
81 protected final NodeMap<ValueNode> aliases;
82
83 /**
84 * This set allows for a quick check whether a node has inputs that were replaced with "scalar"
85 * values.
86 */
87 private final NodeBitMap hasScalarReplacedInputs;
88
89 /*
90 * TODO: if it was possible to introduce your own subclasses of Block and Loop, these maps would
91 * not be necessary. We could merge the GraphEffectsList logic into them.
92 */
93
94 /**
95 * The effects accumulated during analysis of nodes. They may be cleared and re-filled during
96 * iterative loop processing.
97 */
98 protected final BlockMap<GraphEffectList> blockEffects;
99
100 /**
101 * Effects that can only be applied after the effects from within the loop have been applied and
102 * that must be applied before any effect from after the loop is applied. E.g., updating phis.
103 */
104 protected final EconomicMap<Loop<Block>, GraphEffectList> loopMergeEffects = EconomicMap.create(Equivalence.IDENTITY);
105
106 /**
107 * The entry state of loops is needed when loop proxies are processed.
108 */
109 private final EconomicMap<LoopBeginNode, BlockT> loopEntryStates = EconomicMap.create(Equivalence.IDENTITY);
110
111 // Intended to be used by read-eliminating phases based on the effects phase.
112 protected final EconomicMap<Loop<Block>, LoopKillCache> loopLocationKillCache = EconomicMap.create(Equivalence.IDENTITY);
113
114 protected boolean changed;
115 protected final DebugContext debug;
116
117 public EffectsClosure(ScheduleResult schedule, ControlFlowGraph cfg) {
118 this.schedule = schedule;
119 this.cfg = cfg;
120 this.aliases = cfg.graph.createNodeMap();
121 this.hasScalarReplacedInputs = cfg.graph.createNodeBitMap();
122 this.blockEffects = new BlockMap<>(cfg);
123 this.debug = cfg.graph.getDebug();
124 for (Block block : cfg.getBlocks()) {
125 blockEffects.put(block, new GraphEffectList(debug));
126 }
127 }
128
129 @Override
130 public boolean hasChanged() {
131 return changed;
132 }
133
134 @Override
135 public boolean needsApplyEffects() {
136 return true;
137 }
138
139 @Override
140 public void applyEffects() {
141 final StructuredGraph graph = cfg.graph;
142 final ArrayList<Node> obsoleteNodes = new ArrayList<>(0);
143 final ArrayList<GraphEffectList> effectList = new ArrayList<>();
144 /*
145 * Effects are applied during a ordered iteration over the blocks to apply them in the
146 * correct order, e.g., apply the effect that adds a node to the graph before the node is
147 * used.
148 */
149 BlockIteratorClosure<Void> closure = new BlockIteratorClosure<Void>() {
150
151 @Override
152 protected Void getInitialState() {
153 return null;
154 }
155
156 private void apply(GraphEffectList effects) {
157 if (effects != null && !effects.isEmpty()) {
158 effectList.add(effects);
159 }
160 }
161
162 @Override
163 protected Void processBlock(Block block, Void currentState) {
164 apply(blockEffects.get(block));
165 return currentState;
166 }
167
168 @Override
169 protected Void merge(Block merge, List<Void> states) {
170 return null;
171 }
172
173 @Override
174 protected Void cloneState(Void oldState) {
175 return oldState;
176 }
177
178 @Override
179 protected List<Void> processLoop(Loop<Block> loop, Void initialState) {
180 LoopInfo<Void> info = ReentrantBlockIterator.processLoop(this, loop, initialState);
181 apply(loopMergeEffects.get(loop));
182 return info.exitStates;
183 }
184 };
185 ReentrantBlockIterator.apply(closure, cfg.getStartBlock());
186 for (GraphEffectList effects : effectList) {
187 effects.apply(graph, obsoleteNodes, false);
188 }
189 /*
190 * Effects that modify the cfg (e.g., removing a branch for an if that got a constant
191 * condition) need to be performed after all other effects, because they change phi value
192 * indexes.
193 */
194 for (GraphEffectList effects : effectList) {
195 effects.apply(graph, obsoleteNodes, true);
196 }
197 debug.dump(DebugContext.DETAILED_LEVEL, graph, "After applying effects");
198 assert VirtualUtil.assertNonReachable(graph, obsoleteNodes);
199 for (Node node : obsoleteNodes) {
200 if (node.isAlive() && node.hasNoUsages()) {
201 if (node instanceof FixedWithNextNode) {
202 assert ((FixedWithNextNode) node).next() == null;
203 }
204 node.replaceAtUsages(null);
205 GraphUtil.killWithUnusedFloatingInputs(node);
206 }
207 }
208 }
209
210 @Override
211 protected BlockT processBlock(Block block, BlockT state) {
212 if (!state.isDead()) {
213 GraphEffectList effects = blockEffects.get(block);
214
215 /*
216 * If we enter an if branch that is known to be unreachable, we mark it as dead and
217 * cease to do any more analysis on it. At merges, these dead branches will be ignored.
218 */
219 if (block.getBeginNode().predecessor() instanceof IfNode) {
220 IfNode ifNode = (IfNode) block.getBeginNode().predecessor();
221 LogicNode condition = ifNode.condition();
222 Node alias = getScalarAlias(condition);
223 if (alias instanceof LogicConstantNode) {
224 LogicConstantNode constant = (LogicConstantNode) alias;
225 boolean isTrueSuccessor = block.getBeginNode() == ifNode.trueSuccessor();
226
227 if (constant.getValue() != isTrueSuccessor) {
228 state.markAsDead();
229 effects.killIfBranch(ifNode, constant.getValue());
230 return state;
231 }
232 }
233 }
234
235 OptionValues options = block.getBeginNode().getOptions();
236 VirtualUtil.trace(options, debug, "\nBlock: %s, preds: %s, succ: %s (", block, block.getPredecessors(), block.getSuccessors());
237
238 // a lastFixedNode is needed in case we want to insert fixed nodes
239 FixedWithNextNode lastFixedNode = null;
240 Iterable<? extends Node> nodes = schedule != null ? schedule.getBlockToNodesMap().get(block) : block.getNodes();
241 for (Node node : nodes) {
242 // reset the aliases (may be non-null due to iterative loop processing)
243 aliases.set(node, null);
244 if (node instanceof LoopExitNode) {
245 LoopExitNode loopExit = (LoopExitNode) node;
246 for (ProxyNode proxy : loopExit.proxies()) {
247 aliases.set(proxy, null);
248 changed |= processNode(proxy, state, effects, lastFixedNode) && isSignificantNode(node);
249 }
250 processLoopExit(loopExit, loopEntryStates.get(loopExit.loopBegin()), state, blockEffects.get(block));
251 }
252 changed |= processNode(node, state, effects, lastFixedNode) && isSignificantNode(node);
253 if (node instanceof FixedWithNextNode) {
254 lastFixedNode = (FixedWithNextNode) node;
255 }
256 if (state.isDead()) {
257 break;
258 }
259 }
260 VirtualUtil.trace(options, debug, ")\n end state: %s\n", state);
261 }
262 return state;
263 }
264
265 /**
266 * Changes to {@link CommitAllocationNode}s, {@link AllocatedObjectNode}s and {@link BoxNode}s
267 * are not considered to be "important". If only changes to those nodes are discovered during
268 * analysis, the effects need not be applied.
269 */
270 private static boolean isSignificantNode(Node node) {
271 return !(node instanceof CommitAllocationNode || node instanceof AllocatedObjectNode || node instanceof BoxNode);
272 }
273
274 /**
275 * Collects the effects of virtualizing the given node.
276 *
277 * @return {@code true} if the effects include removing the node, {@code false} otherwise.
278 */
279 protected abstract boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode);
280
281 @Override
282 protected BlockT merge(Block merge, List<BlockT> states) {
283 assert blockEffects.get(merge).isEmpty();
284 MergeProcessor processor = createMergeProcessor(merge);
285 doMergeWithoutDead(processor, states);
286 blockEffects.get(merge).addAll(processor.mergeEffects);
287 blockEffects.get(merge).addAll(processor.afterMergeEffects);
288 return processor.newState;
289 }
290
291 @Override
292 @SuppressWarnings("try")
293 protected final List<BlockT> processLoop(Loop<Block> loop, BlockT initialState) {
294 if (initialState.isDead()) {
295 ArrayList<BlockT> states = new ArrayList<>();
296 for (int i = 0; i < loop.getExits().size(); i++) {
297 states.add(initialState);
298 }
299 return states;
300 }
301 /*
302 * Special case nested loops: To avoid an exponential runtime for nested loops we try to
303 * only process them as little times as possible.
304 *
305 * In the first iteration of an outer most loop we go into the inner most loop(s). We run
306 * the first iteration of the inner most loop and then, if necessary, a second iteration.
307 *
308 * We return from the recursion and finish the first iteration of the outermost loop. If we
309 * have to do a second iteration in the outer most loop we go again into the inner most
310 * loop(s) but this time we already know all states that are killed by the loop so inside
311 * the loop we will only have those changes that propagate from the first iteration of the
312 * outer most loop into the current loop. We strip the initial loop state for the inner most
313 * loops and do the first iteration with the (possible) changes from outer loops. If there
314 * are no changes we only have to do 1 iteration and are done.
315 *
316 */
317 BlockT initialStateRemovedKilledLocations = stripKilledLoopLocations(loop, cloneState(initialState));
318 BlockT loopEntryState = initialStateRemovedKilledLocations;
319 BlockT lastMergedState = cloneState(initialStateRemovedKilledLocations);
320 processInitialLoopState(loop, lastMergedState);
321 MergeProcessor mergeProcessor = createMergeProcessor(loop.getHeader());
322 /*
323 * Iterative loop processing: we take the predecessor state as the loop's starting state,
324 * processing the loop contents, merge the states of all loop ends, and check whether the
325 * resulting state is equal to the starting state. If it is, the loop processing has
326 * finished, if not, another iteration is needed.
327 *
328 * This processing converges because the merge processing always makes the starting state
329 * more generic, e.g., adding phis instead of non-phi values.
330 */
331 for (int iteration = 0; iteration < 10; iteration++) {
332 try (Indent i = debug.logAndIndent("================== Process Loop Effects Closure: block:%s begin node:%s", loop.getHeader(), loop.getHeader().getBeginNode())) {
333 LoopInfo<BlockT> info = ReentrantBlockIterator.processLoop(this, loop, cloneState(lastMergedState));
334
335 List<BlockT> states = new ArrayList<>();
336 states.add(initialStateRemovedKilledLocations);
337 states.addAll(info.endStates);
338 doMergeWithoutDead(mergeProcessor, states);
339
340 debug.log("MergeProcessor New State: %s", mergeProcessor.newState);
341 debug.log("===== vs.");
342 debug.log("Last Merged State: %s", lastMergedState);
343
344 if (mergeProcessor.newState.equivalentTo(lastMergedState)) {
345 blockEffects.get(loop.getHeader()).insertAll(mergeProcessor.mergeEffects, 0);
346 loopMergeEffects.put(loop, mergeProcessor.afterMergeEffects);
347
348 assert info.exitStates.size() == loop.getExits().size();
349 loopEntryStates.put((LoopBeginNode) loop.getHeader().getBeginNode(), loopEntryState);
350 assert assertExitStatesNonEmpty(loop, info);
351
352 processKilledLoopLocations(loop, initialStateRemovedKilledLocations, mergeProcessor.newState);
353 return info.exitStates;
354 } else {
355 lastMergedState = mergeProcessor.newState;
356 for (Block block : loop.getBlocks()) {
357 blockEffects.get(block).clear();
358 }
359 }
360 }
361 }
362 throw new GraalError("too many iterations at %s", loop);
363 }
364
365 @SuppressWarnings("unused")
366 protected BlockT stripKilledLoopLocations(Loop<Block> loop, BlockT initialState) {
367 return initialState;
368 }
369
370 @SuppressWarnings("unused")
371 protected void processKilledLoopLocations(Loop<Block> loop, BlockT initialState, BlockT mergedStates) {
372 // nothing to do
373 }
374
375 @SuppressWarnings("unused")
376 protected void processInitialLoopState(Loop<Block> loop, BlockT initialState) {
377 // nothing to do
378 }
379
380 private void doMergeWithoutDead(MergeProcessor mergeProcessor, List<BlockT> states) {
381 int alive = 0;
382 for (BlockT state : states) {
383 if (!state.isDead()) {
384 alive++;
385 }
386 }
387 if (alive == 0) {
388 mergeProcessor.setNewState(states.get(0));
389 } else if (alive == states.size()) {
390 int[] stateIndexes = new int[states.size()];
391 for (int i = 0; i < stateIndexes.length; i++) {
392 stateIndexes[i] = i;
393 }
394 mergeProcessor.setStateIndexes(stateIndexes);
395 mergeProcessor.setNewState(getInitialState());
396 mergeProcessor.merge(states);
397 } else {
398 ArrayList<BlockT> aliveStates = new ArrayList<>(alive);
399 int[] stateIndexes = new int[alive];
400 for (int i = 0; i < states.size(); i++) {
401 if (!states.get(i).isDead()) {
402 stateIndexes[aliveStates.size()] = i;
403 aliveStates.add(states.get(i));
404 }
405 }
406 mergeProcessor.setStateIndexes(stateIndexes);
407 mergeProcessor.setNewState(getInitialState());
408 mergeProcessor.merge(aliveStates);
409 }
410 }
411
412 private boolean assertExitStatesNonEmpty(Loop<Block> loop, LoopInfo<BlockT> info) {
413 for (int i = 0; i < loop.getExits().size(); i++) {
414 assert info.exitStates.get(i) != null : "no loop exit state at " + loop.getExits().get(i) + " / " + loop.getHeader();
415 }
416 return true;
417 }
418
419 protected abstract void processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects);
420
421 protected abstract MergeProcessor createMergeProcessor(Block merge);
422
423 /**
424 * The main workhorse for merging states, both for loops and for normal merges.
425 */
426 protected abstract class MergeProcessor {
427
428 private final Block mergeBlock;
429 private final AbstractMergeNode merge;
430
431 protected final GraphEffectList mergeEffects;
432 protected final GraphEffectList afterMergeEffects;
433
434 /**
435 * The indexes are used to map from an index in the list of active (non-dead) predecessors
436 * to an index in the list of all predecessors (the latter may be larger).
437 */
438 private int[] stateIndexes;
439 protected BlockT newState;
440
441 public MergeProcessor(Block mergeBlock) {
442 this.mergeBlock = mergeBlock;
443 this.merge = (AbstractMergeNode) mergeBlock.getBeginNode();
444 this.mergeEffects = new GraphEffectList(debug);
445 this.afterMergeEffects = new GraphEffectList(debug);
446 }
447
448 /**
449 * @param states the states that should be merged.
450 */
451 protected abstract void merge(List<BlockT> states);
452
453 private void setNewState(BlockT state) {
454 newState = state;
455 mergeEffects.clear();
456 afterMergeEffects.clear();
457 }
458
459 private void setStateIndexes(int[] stateIndexes) {
460 this.stateIndexes = stateIndexes;
461 }
462
463 protected final Block getPredecessor(int index) {
464 return mergeBlock.getPredecessors()[stateIndexes[index]];
465 }
466
467 protected final NodeIterable<PhiNode> getPhis() {
468 return merge.phis();
469 }
470
471 protected final ValueNode getPhiValueAt(PhiNode phi, int index) {
472 return phi.valueAt(stateIndexes[index]);
473 }
474
475 protected final ValuePhiNode createValuePhi(Stamp stamp) {
476 return new ValuePhiNode(stamp, merge, new ValueNode[mergeBlock.getPredecessorCount()]);
477 }
478
479 protected final void setPhiInput(PhiNode phi, int index, ValueNode value) {
480 afterMergeEffects.initializePhiInput(phi, stateIndexes[index], value);
481 }
482
483 protected final StructuredGraph graph() {
484 return merge.graph();
485 }
486
487 @Override
488 public String toString() {
489 return "MergeProcessor@" + merge;
490 }
491 }
492
493 public void addScalarAlias(ValueNode node, ValueNode alias) {
494 assert !(alias instanceof VirtualObjectNode);
495 aliases.set(node, alias);
496 for (Node usage : node.usages()) {
497 if (!hasScalarReplacedInputs.isNew(usage)) {
498 hasScalarReplacedInputs.mark(usage);
499 }
500 }
501 }
502
503 protected final boolean hasScalarReplacedInputs(Node node) {
504 return hasScalarReplacedInputs.isMarked(node);
505 }
506
507 public ValueNode getScalarAlias(ValueNode node) {
508 assert !(node instanceof VirtualObjectNode);
509 if (node == null || !node.isAlive() || aliases.isNew(node)) {
510 return node;
511 }
512 ValueNode result = aliases.get(node);
513 return (result == null || result instanceof VirtualObjectNode) ? node : result;
514 }
515
516 protected static final class LoopKillCache {
517 private int visits;
518 private LocationIdentity firstLocation;
519 private EconomicSet<LocationIdentity> killedLocations;
520 private boolean killsAll;
521
522 protected LoopKillCache(int visits) {
523 this.visits = visits;
524 }
525
526 protected void visited() {
527 visits++;
528 }
529
530 protected int visits() {
531 return visits;
532 }
533
534 protected void setKillsAll() {
535 killsAll = true;
536 firstLocation = null;
537 killedLocations = null;
538 }
539
540 protected boolean containsLocation(LocationIdentity locationIdentity) {
541 if (killsAll) {
542 return true;
543 }
544 if (firstLocation == null) {
545 return false;
546 }
547 if (!firstLocation.equals(locationIdentity)) {
548 return killedLocations != null ? killedLocations.contains(locationIdentity) : false;
549 }
550 return true;
551 }
552
553 protected void rememberLoopKilledLocation(LocationIdentity locationIdentity) {
554 if (killsAll) {
555 return;
556 }
557 if (firstLocation == null || firstLocation.equals(locationIdentity)) {
558 firstLocation = locationIdentity;
559 } else {
560 if (killedLocations == null) {
561 killedLocations = EconomicSet.create(Equivalence.IDENTITY);
562 }
563 killedLocations.add(locationIdentity);
564 }
565 }
566
567 protected boolean loopKillsLocations() {
568 if (killsAll) {
569 return true;
570 }
571 return firstLocation != null;
572 }
573 }
574
575 }