1 /*
2 * Copyright (c) 2015, 2018, 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.nodes.StaticDeoptimizingNode.mergeActions;
28
29 import java.util.ArrayDeque;
30 import java.util.Deque;
31 import java.util.List;
32
33 import jdk.internal.vm.compiler.collections.EconomicMap;
34 import jdk.internal.vm.compiler.collections.Equivalence;
35 import jdk.internal.vm.compiler.collections.MapCursor;
36 import jdk.internal.vm.compiler.collections.Pair;
37 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
38 import org.graalvm.compiler.core.common.cfg.BlockMap;
39 import org.graalvm.compiler.core.common.type.ArithmeticOpTable;
40 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp;
41 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.And;
42 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Or;
43 import org.graalvm.compiler.core.common.type.IntegerStamp;
44 import org.graalvm.compiler.core.common.type.ObjectStamp;
45 import org.graalvm.compiler.core.common.type.Stamp;
46 import org.graalvm.compiler.core.common.type.StampFactory;
47 import org.graalvm.compiler.debug.CounterKey;
48 import org.graalvm.compiler.debug.DebugCloseable;
49 import org.graalvm.compiler.debug.DebugContext;
50 import org.graalvm.compiler.graph.Node;
51 import org.graalvm.compiler.graph.NodeMap;
52 import org.graalvm.compiler.graph.NodeStack;
53 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
54 import org.graalvm.compiler.nodeinfo.InputType;
55 import org.graalvm.compiler.nodes.AbstractBeginNode;
56 import org.graalvm.compiler.nodes.AbstractMergeNode;
57 import org.graalvm.compiler.nodes.BinaryOpLogicNode;
58 import org.graalvm.compiler.nodes.ConditionAnchorNode;
59 import org.graalvm.compiler.nodes.DeoptimizeNode;
60 import org.graalvm.compiler.nodes.DeoptimizingGuard;
61 import org.graalvm.compiler.nodes.EndNode;
62 import org.graalvm.compiler.nodes.FixedGuardNode;
63 import org.graalvm.compiler.nodes.FixedNode;
64 import org.graalvm.compiler.nodes.FixedWithNextNode;
65 import org.graalvm.compiler.nodes.GuardNode;
66 import org.graalvm.compiler.nodes.IfNode;
67 import org.graalvm.compiler.nodes.LogicConstantNode;
68 import org.graalvm.compiler.nodes.LogicNode;
69 import org.graalvm.compiler.nodes.LoopExitNode;
70 import org.graalvm.compiler.nodes.MergeNode;
71 import org.graalvm.compiler.nodes.NodeView;
72 import org.graalvm.compiler.nodes.ParameterNode;
73 import org.graalvm.compiler.nodes.PiNode;
74 import org.graalvm.compiler.nodes.ProxyNode;
75 import org.graalvm.compiler.nodes.ShortCircuitOrNode;
76 import org.graalvm.compiler.nodes.StructuredGraph;
77 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
78 import org.graalvm.compiler.nodes.UnaryOpLogicNode;
79 import org.graalvm.compiler.nodes.ValueNode;
80 import org.graalvm.compiler.nodes.ValuePhiNode;
81 import org.graalvm.compiler.nodes.calc.AndNode;
82 import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode;
83 import org.graalvm.compiler.nodes.calc.BinaryNode;
84 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
85 import org.graalvm.compiler.nodes.calc.UnaryNode;
86 import org.graalvm.compiler.nodes.cfg.Block;
87 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
88 import org.graalvm.compiler.nodes.extended.GuardingNode;
89 import org.graalvm.compiler.nodes.extended.IntegerSwitchNode;
90 import org.graalvm.compiler.nodes.extended.LoadHubNode;
91 import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
92 import org.graalvm.compiler.nodes.java.InstanceOfNode;
93 import org.graalvm.compiler.nodes.java.TypeSwitchNode;
94 import org.graalvm.compiler.nodes.spi.CoreProviders;
95 import org.graalvm.compiler.nodes.spi.NodeWithState;
96 import org.graalvm.compiler.nodes.spi.StampInverter;
97 import org.graalvm.compiler.nodes.util.GraphUtil;
98 import org.graalvm.compiler.phases.BasePhase;
99 import org.graalvm.compiler.phases.schedule.SchedulePhase;
100 import org.graalvm.compiler.phases.schedule.SchedulePhase.SchedulingStrategy;
101
102 import jdk.vm.ci.meta.DeoptimizationAction;
103 import jdk.vm.ci.meta.JavaConstant;
104 import jdk.vm.ci.meta.SpeculationLog.Speculation;
105 import jdk.vm.ci.meta.TriState;
106
107 public class ConditionalEliminationPhase extends BasePhase<CoreProviders> {
108
109 private static final CounterKey counterStampsRegistered = DebugContext.counter("StampsRegistered");
110 private static final CounterKey counterStampsFound = DebugContext.counter("StampsFound");
111 private static final CounterKey counterIfsKilled = DebugContext.counter("CE_KilledIfs");
112 private static final CounterKey counterPhiStampsImproved = DebugContext.counter("CE_ImprovedPhis");
113 private final boolean fullSchedule;
114 private final boolean moveGuards;
115
116 public ConditionalEliminationPhase(boolean fullSchedule) {
117 this(fullSchedule, true);
118 }
119
120 public ConditionalEliminationPhase(boolean fullSchedule, boolean moveGuards) {
121 this.fullSchedule = fullSchedule;
122 this.moveGuards = moveGuards;
123 }
124
125 @Override
126 @SuppressWarnings("try")
127 protected void run(StructuredGraph graph, CoreProviders context) {
128 try (DebugContext.Scope s = graph.getDebug().scope("DominatorConditionalElimination")) {
129 BlockMap<List<Node>> blockToNodes = null;
130 NodeMap<Block> nodeToBlock = null;
131 ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true);
132 if (fullSchedule) {
133 if (moveGuards) {
134 cfg.visitDominatorTree(new MoveGuardsUpwards(), graph.hasValueProxies());
135 }
136 try (DebugContext.Scope scheduleScope = graph.getDebug().scope(SchedulePhase.class)) {
137 SchedulePhase.run(graph, SchedulingStrategy.EARLIEST_WITH_GUARD_ORDER, cfg);
138 } catch (Throwable t) {
139 throw graph.getDebug().handle(t);
140 }
141 ScheduleResult r = graph.getLastSchedule();
142 blockToNodes = r.getBlockToNodesMap();
143 nodeToBlock = r.getNodeToBlockMap();
144 } else {
145 nodeToBlock = cfg.getNodeToBlock();
146 blockToNodes = getBlockToNodes(cfg);
147 }
148 ControlFlowGraph.RecursiveVisitor<?> visitor = createVisitor(graph, cfg, blockToNodes, nodeToBlock, context);
149 cfg.visitDominatorTree(visitor, graph.hasValueProxies());
150 }
151 }
152
153 protected BlockMap<List<Node>> getBlockToNodes(@SuppressWarnings("unused") ControlFlowGraph cfg) {
154 return null;
155 }
156
157 protected ControlFlowGraph.RecursiveVisitor<?> createVisitor(StructuredGraph graph, @SuppressWarnings("unused") ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodes,
158 NodeMap<Block> nodeToBlock, CoreProviders context) {
159 return new Instance(graph, blockToNodes, nodeToBlock, context);
160 }
161
162 public static class MoveGuardsUpwards implements ControlFlowGraph.RecursiveVisitor<Block> {
163
164 Block anchorBlock;
165
166 @Override
167 @SuppressWarnings("try")
168 public Block enter(Block b) {
169 Block oldAnchorBlock = anchorBlock;
170 if (b.getDominator() == null || b.getDominator().getPostdominator() != b) {
171 // New anchor.
172 anchorBlock = b;
173 }
174
175 AbstractBeginNode beginNode = b.getBeginNode();
176 if (beginNode instanceof AbstractMergeNode && anchorBlock != b) {
177 AbstractMergeNode mergeNode = (AbstractMergeNode) beginNode;
178 mergeNode.replaceAtUsages(InputType.Anchor, anchorBlock.getBeginNode());
179 mergeNode.replaceAtUsages(InputType.Guard, anchorBlock.getBeginNode());
180 assert mergeNode.anchored().isEmpty();
181 }
182
183 FixedNode endNode = b.getEndNode();
184 if (endNode instanceof IfNode) {
185 IfNode node = (IfNode) endNode;
186
187 // Check if we can move guards upwards.
188 AbstractBeginNode trueSuccessor = node.trueSuccessor();
189 EconomicMap<LogicNode, GuardNode> trueGuards = EconomicMap.create(Equivalence.IDENTITY);
190 for (GuardNode guard : trueSuccessor.guards()) {
191 LogicNode condition = guard.getCondition();
192 if (condition.hasMoreThanOneUsage()) {
193 trueGuards.put(condition, guard);
194 }
195 }
196
197 if (!trueGuards.isEmpty()) {
198 for (GuardNode guard : node.falseSuccessor().guards().snapshot()) {
199 GuardNode otherGuard = trueGuards.get(guard.getCondition());
200 if (otherGuard != null && guard.isNegated() == otherGuard.isNegated()) {
201 Speculation speculation = otherGuard.getSpeculation();
202 if (speculation == null) {
203 speculation = guard.getSpeculation();
204 } else if (guard.getSpeculation() != null && guard.getSpeculation() != speculation) {
205 // Cannot optimize due to different speculations.
206 continue;
207 }
208 try (DebugCloseable closeable = guard.withNodeSourcePosition()) {
209 GuardNode newlyCreatedGuard = new GuardNode(guard.getCondition(), anchorBlock.getBeginNode(), guard.getReason(), guard.getAction(), guard.isNegated(), speculation,
210 guard.getNoDeoptSuccessorPosition());
211 GuardNode newGuard = node.graph().unique(newlyCreatedGuard);
212 if (otherGuard.isAlive()) {
213 otherGuard.replaceAndDelete(newGuard);
214 }
215 guard.replaceAndDelete(newGuard);
216 }
217 }
218 }
219 }
220 }
221 return oldAnchorBlock;
222 }
223
224 @Override
225 public void exit(Block b, Block value) {
226 anchorBlock = value;
227 }
228
229 }
230
231 private static final class PhiInfoElement {
232
233 private EconomicMap<EndNode, InfoElement> infoElements;
234
235 public void set(EndNode end, InfoElement infoElement) {
236 if (infoElements == null) {
237 infoElements = EconomicMap.create(Equivalence.IDENTITY);
238 }
239 infoElements.put(end, infoElement);
240 }
241
242 public InfoElement get(EndNode end) {
243 if (infoElements == null) {
244 return null;
245 }
246 return infoElements.get(end);
247 }
248 }
249
250 public static final class Marks {
251 final int infoElementOperations;
252 final int conditions;
253
254 public Marks(int infoElementOperations, int conditions) {
255 this.infoElementOperations = infoElementOperations;
256 this.conditions = conditions;
257 }
258 }
259
260 protected static final class GuardedCondition {
261 private final GuardingNode guard;
262 private final LogicNode condition;
263 private final boolean negated;
264
265 public GuardedCondition(GuardingNode guard, LogicNode condition, boolean negated) {
266 this.guard = guard;
267 this.condition = condition;
268 this.negated = negated;
269 }
270
271 public GuardingNode getGuard() {
272 return guard;
273 }
274
275 public LogicNode getCondition() {
276 return condition;
277 }
278
279 public boolean isNegated() {
280 return negated;
281 }
282 }
283
284 public static class Instance implements ControlFlowGraph.RecursiveVisitor<Marks> {
285 protected final NodeMap<InfoElement> map;
286 protected final BlockMap<List<Node>> blockToNodes;
287 protected final NodeMap<Block> nodeToBlock;
288 protected final CanonicalizerTool tool;
289 protected final NodeStack undoOperations;
290 protected final StructuredGraph graph;
291 protected final DebugContext debug;
292 protected final EconomicMap<MergeNode, EconomicMap<ValuePhiNode, PhiInfoElement>> mergeMaps;
293
294 protected final ArrayDeque<GuardedCondition> conditions;
295
296 /**
297 * Tests which may be eliminated because post dominating tests to prove a broader condition.
298 */
299 private Deque<DeoptimizingGuard> pendingTests;
300
301 public Instance(StructuredGraph graph, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, CoreProviders context) {
302 this.graph = graph;
303 this.debug = graph.getDebug();
304 this.blockToNodes = blockToNodes;
305 this.nodeToBlock = nodeToBlock;
306 this.undoOperations = new NodeStack();
307 this.map = graph.createNodeMap();
308 this.pendingTests = new ArrayDeque<>();
309 this.conditions = new ArrayDeque<>();
310 tool = GraphUtil.getDefaultSimplifier(context.getMetaAccess(), context.getConstantReflection(), context.getConstantFieldProvider(), false, graph.getAssumptions(), graph.getOptions(),
311 context.getLowerer());
312 mergeMaps = EconomicMap.create();
313 }
314
315 protected void processConditionAnchor(ConditionAnchorNode node) {
316 tryProveCondition(node.condition(), (guard, result, guardedValueStamp, newInput) -> {
317 if (result != node.isNegated()) {
318 node.replaceAtUsages(guard.asNode());
319 GraphUtil.unlinkFixedNode(node);
320 GraphUtil.killWithUnusedFloatingInputs(node);
321 } else {
322 ValueAnchorNode valueAnchor = node.graph().add(new ValueAnchorNode(null));
323 node.replaceAtUsages(valueAnchor);
324 node.graph().replaceFixedWithFixed(node, valueAnchor);
325 }
326 return true;
327 });
328 }
329
330 protected void processGuard(GuardNode node) {
331 if (!tryProveGuardCondition(node, node.getCondition(), (guard, result, guardedValueStamp, newInput) -> {
332 if (result != node.isNegated()) {
333 node.replaceAndDelete(guard.asNode());
334 if (guard instanceof DeoptimizingGuard && !((DeoptimizingGuard) guard).isNegated()) {
335 rebuildPiNodes((DeoptimizingGuard) guard);
336 }
337 } else {
338 AbstractBeginNode beginNode = (AbstractBeginNode) node.getAnchor();
339
340 if (beginNode.next() instanceof DeoptimizeNode) {
341 // This branch is already dead.
342 } else {
343 /*
344 * Don't kill this branch immediately because `killCFG` can have complex
345 * implications in the presence of loops: it might replace or delete nodes
346 * in other branches or even above the kill point. Instead of killing
347 * immediately, just leave the graph in a state that is easy to simplify by
348 * a subsequent canonicalizer phase.
349 */
350 FixedGuardNode deopt = new FixedGuardNode(LogicConstantNode.forBoolean(result, node.graph()), node.getReason(), node.getAction(), node.getSpeculation(), node.isNegated(),
351 node.getNodeSourcePosition());
352 graph.addAfterFixed(beginNode, node.graph().add(deopt));
353 }
354 }
355 return true;
356 })) {
357 registerNewCondition(node.getCondition(), node.isNegated(), node);
358 }
359 }
360
361 protected void processFixedGuard(FixedGuardNode node) {
362 if (!tryProveGuardCondition(node, node.condition(), (guard, result, guardedValueStamp, newInput) -> {
363 if (result != node.isNegated()) {
364 node.replaceAtUsages(guard.asNode());
365 GraphUtil.unlinkFixedNode(node);
366 GraphUtil.killWithUnusedFloatingInputs(node);
367 if (guard instanceof DeoptimizingGuard && !((DeoptimizingGuard) guard).isNegated()) {
368 rebuildPiNodes((DeoptimizingGuard) guard);
369 }
370 } else {
371 node.setCondition(LogicConstantNode.forBoolean(result, node.graph()), node.isNegated());
372 // Don't kill this branch immediately, see `processGuard`.
373 }
374
375 debug.log("Kill fixed guard %s", node);
376 return true;
377 })) {
378 registerNewCondition(node.condition(), node.isNegated(), node);
379 }
380 }
381
382 private void rebuildPiNodes(DeoptimizingGuard guard) {
383 LogicNode newCondition = guard.getCondition();
384 if (newCondition instanceof InstanceOfNode) {
385 InstanceOfNode inst = (InstanceOfNode) newCondition;
386 ValueNode originalValue = GraphUtil.skipPi(inst.getValue());
387 PiNode pi = null;
388 // Ensure that any Pi that's weaker than what the instanceof proves is
389 // replaced by one derived from the instanceof itself.
390 for (PiNode existing : guard.asNode().usages().filter(PiNode.class).snapshot()) {
391 if (!existing.isAlive()) {
392 continue;
393 }
394 if (originalValue != GraphUtil.skipPi(existing.object())) {
395 // Somehow these are unrelated values so leave it alone
396 continue;
397 }
398 // If the pi has a weaker stamp or the same stamp but a different input
399 // then replace it.
400 boolean strongerStamp = !existing.piStamp().join(inst.getCheckedStamp()).equals(inst.getCheckedStamp());
401 boolean differentCheckedStamp = !existing.piStamp().equals(inst.getCheckedStamp());
402 boolean differentObject = existing.object() != inst.getValue();
403 if (!strongerStamp && (differentCheckedStamp || differentObject)) {
404 if (pi == null) {
405 pi = graph.unique(new PiNode(inst.getValue(), inst.getCheckedStamp(), (ValueNode) guard));
406 }
407 if (!pi.stamp(NodeView.DEFAULT).join(existing.stamp(NodeView.DEFAULT)).equals(pi.stamp(NodeView.DEFAULT))) {
408 /*
409 * With a code sequence like null check, type check, null check of type
410 * checked value, CE will use the first null check to prove the second
411 * null check so the graph ends up a Pi guarded by the first null check
412 * but consuming the output Pi from the type check check. In this case
413 * we should still canonicalize the checked stamp for consistency.
414 */
415 if (differentCheckedStamp) {
416 PiNode alternatePi = graph.unique(new PiNode(existing.object(), inst.getCheckedStamp(), (ValueNode) guard));
417 /*
418 * If the resulting stamp is as good or better then do the
419 * replacement. However when interface types are involved it's
420 * possible that improving the checked stamp merges types which
421 * appear unrelated so there's we must skip the replacement.
422 */
423 if (alternatePi.stamp(NodeView.DEFAULT).join(existing.stamp(NodeView.DEFAULT)).equals(alternatePi.stamp(NodeView.DEFAULT))) {
424 existing.replaceAndDelete(alternatePi);
425 }
426 }
427 continue;
428 }
429 existing.replaceAndDelete(pi);
430 }
431 }
432 }
433 }
434
435 protected void processIf(IfNode node) {
436 tryProveCondition(node.condition(), (guard, result, guardedValueStamp, newInput) -> {
437 node.setCondition(LogicConstantNode.forBoolean(result, node.graph()));
438 AbstractBeginNode survivingSuccessor = node.getSuccessor(result);
439 survivingSuccessor.replaceAtUsages(InputType.Guard, guard.asNode());
440 // Don't kill the other branch immediately, see `processGuard`.
441 counterIfsKilled.increment(debug);
442 return true;
443 });
444 }
445
446 @Override
447 public Marks enter(Block block) {
448 int infoElementsMark = undoOperations.size();
449 int conditionsMark = conditions.size();
450 debug.log("[Pre Processing block %s]", block);
451 // For now conservatively collect guards only within the same block.
452 pendingTests.clear();
453 processNodes(block);
454 return new Marks(infoElementsMark, conditionsMark);
455 }
456
457 protected void processNodes(Block block) {
458 if (blockToNodes != null) {
459 for (Node n : blockToNodes.get(block)) {
460 if (n.isAlive()) {
461 processNode(n);
462 }
463 }
464 } else {
465 processBlock(block);
466 }
467 }
468
469 private void processBlock(Block block) {
470 FixedNode n = block.getBeginNode();
471 FixedNode endNode = block.getEndNode();
472 debug.log("[Processing block %s]", block);
473 while (n != endNode) {
474 if (n.isDeleted() || endNode.isDeleted()) {
475 // This branch was deleted!
476 return;
477 }
478 FixedNode next = ((FixedWithNextNode) n).next();
479 processNode(n);
480 n = next;
481 }
482 if (endNode.isAlive()) {
483 processNode(endNode);
484 }
485 }
486
487 @SuppressWarnings("try")
488 protected void processNode(Node node) {
489 try (DebugCloseable closeable = node.withNodeSourcePosition()) {
490 if (node instanceof NodeWithState && !(node instanceof GuardingNode)) {
491 pendingTests.clear();
492 }
493
494 if (node instanceof MergeNode) {
495 introducePisForPhis((MergeNode) node);
496 }
497
498 if (node instanceof AbstractBeginNode) {
499 if (node instanceof LoopExitNode && graph.hasValueProxies()) {
500 // Condition must not be used down this path.
501 return;
502 }
503 processAbstractBegin((AbstractBeginNode) node);
504 } else if (node instanceof FixedGuardNode) {
505 processFixedGuard((FixedGuardNode) node);
506 } else if (node instanceof GuardNode) {
507 processGuard((GuardNode) node);
508 } else if (node instanceof ConditionAnchorNode) {
509 processConditionAnchor((ConditionAnchorNode) node);
510 } else if (node instanceof IfNode) {
511 processIf((IfNode) node);
512 } else if (node instanceof EndNode) {
513 processEnd((EndNode) node);
514 }
515 }
516 }
517
518 protected void introducePisForPhis(MergeNode merge) {
519 EconomicMap<ValuePhiNode, PhiInfoElement> mergeMap = this.mergeMaps.get(merge);
520 if (mergeMap != null) {
521 MapCursor<ValuePhiNode, PhiInfoElement> entries = mergeMap.getEntries();
522 while (entries.advance()) {
523 ValuePhiNode phi = entries.getKey();
524 assert phi.isAlive() || phi.isDeleted();
525 /*
526 * Phi might have been killed already via a conditional elimination in another
527 * branch.
528 */
529 if (phi.isDeleted()) {
530 continue;
531 }
532 PhiInfoElement phiInfoElements = entries.getValue();
533 Stamp bestPossibleStamp = null;
534 for (int i = 0; i < phi.valueCount(); ++i) {
535 ValueNode valueAt = phi.valueAt(i);
536 Stamp curBestStamp = valueAt.stamp(NodeView.DEFAULT);
537 InfoElement infoElement = phiInfoElements.get(merge.forwardEndAt(i));
538 if (infoElement != null) {
539 curBestStamp = curBestStamp.join(infoElement.getStamp());
540 }
541
542 if (bestPossibleStamp == null) {
543 bestPossibleStamp = curBestStamp;
544 } else {
545 bestPossibleStamp = bestPossibleStamp.meet(curBestStamp);
546 }
547 }
548
549 Stamp oldStamp = phi.stamp(NodeView.DEFAULT);
550 if (oldStamp.tryImproveWith(bestPossibleStamp) != null) {
551
552 // Need to be careful to not run into stamp update cycles with the iterative
553 // canonicalization.
554 boolean allow = false;
555 if (bestPossibleStamp instanceof ObjectStamp) {
556 // Always allow object stamps.
557 allow = true;
558 } else if (bestPossibleStamp instanceof IntegerStamp) {
559 IntegerStamp integerStamp = (IntegerStamp) bestPossibleStamp;
560 IntegerStamp oldIntegerStamp = (IntegerStamp) oldStamp;
561 if (integerStamp.isPositive() != oldIntegerStamp.isPositive()) {
562 allow = true;
563 } else if (integerStamp.isNegative() != oldIntegerStamp.isNegative()) {
564 allow = true;
565 } else if (integerStamp.isStrictlyPositive() != oldIntegerStamp.isStrictlyPositive()) {
566 allow = true;
567 } else if (integerStamp.isStrictlyNegative() != oldIntegerStamp.isStrictlyNegative()) {
568 allow = true;
569 } else if (integerStamp.asConstant() != null) {
570 allow = true;
571 } else if (oldStamp.isUnrestricted()) {
572 allow = true;
573 }
574 } else {
575 // Fortify: Suppress Null Dereference false positive
576 assert bestPossibleStamp != null;
577 allow = (bestPossibleStamp.asConstant() != null);
578 }
579
580 if (allow) {
581 ValuePhiNode newPhi = graph.addWithoutUnique(new ValuePhiNode(bestPossibleStamp, merge));
582 for (int i = 0; i < phi.valueCount(); ++i) {
583 ValueNode valueAt = phi.valueAt(i);
584 if (bestPossibleStamp.meet(valueAt.stamp(NodeView.DEFAULT)).equals(bestPossibleStamp)) {
585 // Pi not required here.
586 } else {
587 InfoElement infoElement = phiInfoElements.get(merge.forwardEndAt(i));
588 assert infoElement != null;
589 Stamp curBestStamp = infoElement.getStamp();
590 ValueNode input = infoElement.getProxifiedInput();
591 if (input == null) {
592 input = valueAt;
593 }
594 valueAt = graph.maybeAddOrUnique(PiNode.create(input, curBestStamp, (ValueNode) infoElement.guard));
595 }
596 newPhi.addInput(valueAt);
597 }
598 counterPhiStampsImproved.increment(debug);
599 phi.replaceAtUsagesAndDelete(newPhi);
600 }
601 }
602 }
603 }
604 }
605
606 protected void processEnd(EndNode end) {
607 AbstractMergeNode abstractMerge = end.merge();
608 if (abstractMerge instanceof MergeNode) {
609 MergeNode merge = (MergeNode) abstractMerge;
610
611 EconomicMap<ValuePhiNode, PhiInfoElement> mergeMap = this.mergeMaps.get(merge);
612 for (ValuePhiNode phi : merge.valuePhis()) {
613 ValueNode valueAt = phi.valueAt(end);
614 InfoElement infoElement = this.getInfoElements(valueAt);
615 while (infoElement != null) {
616 Stamp newStamp = infoElement.getStamp();
617 if (phi.stamp(NodeView.DEFAULT).tryImproveWith(newStamp) != null) {
618 if (mergeMap == null) {
619 mergeMap = EconomicMap.create();
620 mergeMaps.put(merge, mergeMap);
621 }
622
623 PhiInfoElement phiInfoElement = mergeMap.get(phi);
624 if (phiInfoElement == null) {
625 phiInfoElement = new PhiInfoElement();
626 mergeMap.put(phi, phiInfoElement);
627 }
628
629 phiInfoElement.set(end, infoElement);
630 break;
631 }
632 infoElement = nextElement(infoElement);
633 }
634 }
635 }
636 }
637
638 protected void registerNewCondition(LogicNode condition, boolean negated, GuardingNode guard) {
639 if (condition instanceof UnaryOpLogicNode) {
640 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) condition;
641 ValueNode value = unaryLogicNode.getValue();
642 if (maybeMultipleUsages(value)) {
643 // getSucceedingStampForValue doesn't take the (potentially a Pi Node) input
644 // stamp into account, so it can be safely propagated.
645 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(negated);
646 registerNewStamp(value, newStamp, guard, true);
647 }
648 } else if (condition instanceof BinaryOpLogicNode) {
649 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) condition;
650 ValueNode x = binaryOpLogicNode.getX();
651 ValueNode y = binaryOpLogicNode.getY();
652 if (!x.isConstant() && maybeMultipleUsages(x)) {
653 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(negated, getSafeStamp(x), getOtherSafeStamp(y));
654 registerNewStamp(x, newStampX, guard);
655 }
656
657 if (!y.isConstant() && maybeMultipleUsages(y)) {
658 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(negated, getOtherSafeStamp(x), getSafeStamp(y));
659 registerNewStamp(y, newStampY, guard);
660 }
661
662 if (condition instanceof IntegerEqualsNode && guard instanceof DeoptimizingGuard && !negated) {
663 if (y.isConstant() && x instanceof AndNode) {
664 AndNode and = (AndNode) x;
665 ValueNode andX = and.getX();
666 if (and.getY() == y && maybeMultipleUsages(andX)) {
667 /*
668 * This 'and' proves something about some of the bits in and.getX().
669 * It's equivalent to or'ing in the mask value since those values are
670 * known to be set.
671 */
672 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp(NodeView.DEFAULT)).getOr();
673 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(andX), getOtherSafeStamp(y));
674 registerNewStamp(andX, newStampX, guard);
675 }
676 }
677 }
678 }
679 if (guard instanceof DeoptimizingGuard) {
680 assert ((DeoptimizingGuard) guard).getCondition() == condition;
681 pendingTests.push((DeoptimizingGuard) guard);
682 }
683 registerCondition(condition, negated, guard);
684 }
685
686 Pair<InfoElement, Stamp> recursiveFoldStamp(Node node) {
687 if (node instanceof UnaryNode) {
688 UnaryNode unary = (UnaryNode) node;
689 ValueNode value = unary.getValue();
690 InfoElement infoElement = getInfoElements(value);
691 while (infoElement != null) {
692 Stamp result = unary.foldStamp(infoElement.getStamp());
693 if (result != null) {
694 return Pair.create(infoElement, result);
695 }
696 infoElement = nextElement(infoElement);
697 }
698 } else if (node instanceof BinaryNode) {
699 BinaryNode binary = (BinaryNode) node;
700 ValueNode y = binary.getY();
701 ValueNode x = binary.getX();
702 if (y.isConstant()) {
703 InfoElement infoElement = getInfoElements(x);
704 while (infoElement != null) {
705 Stamp result = binary.foldStamp(infoElement.stamp, y.stamp(NodeView.DEFAULT));
706 if (result != null) {
707 return Pair.create(infoElement, result);
708 }
709 infoElement = nextElement(infoElement);
710 }
711 }
712 }
713 return null;
714 }
715
716 /**
717 * Get the stamp that may be used for the value for which we are registering the condition.
718 * We may directly use the stamp here without restriction, because any later lookup of the
719 * registered info elements is in the same chain of pi nodes.
720 */
721 private static Stamp getSafeStamp(ValueNode x) {
722 return x.stamp(NodeView.DEFAULT);
723 }
724
725 /**
726 * We can only use the stamp of a second value involved in the condition if we are sure that
727 * we are not implicitly creating a dependency on a pi node that is responsible for that
728 * stamp. For now, we are conservatively only using the stamps of constants. Under certain
729 * circumstances, we may also be able to use the stamp of the value after skipping pi nodes
730 * (e.g., the stamp of a parameter after inlining, or the stamp of a fixed node that can
731 * never be replaced with a pi node via canonicalization).
732 */
733 private static Stamp getOtherSafeStamp(ValueNode x) {
734 if (x.isConstant() || x.graph().isAfterFixedReadPhase()) {
735 return x.stamp(NodeView.DEFAULT);
736 }
737 return x.stamp(NodeView.DEFAULT).unrestricted();
738 }
739
740 /**
741 * Recursively try to fold stamps within this expression using information from
742 * {@link #getInfoElements(ValueNode)}. It's only safe to use constants and one
743 * {@link InfoElement} otherwise more than one guard would be required.
744 *
745 * @param node
746 * @return the pair of the @{link InfoElement} used and the stamp produced for the whole
747 * expression
748 */
749 Pair<InfoElement, Stamp> recursiveFoldStampFromInfo(Node node) {
750 return recursiveFoldStamp(node);
751 }
752
753 /**
754 * Look for a preceding guard whose condition is implied by {@code thisGuard}. If we find
755 * one, try to move this guard just above that preceding guard so that we can fold it:
756 *
757 * <pre>
758 * guard(C1); // preceding guard
759 * ...
760 * guard(C2); // thisGuard
761 * </pre>
762 *
763 * If C2 => C1, transform to:
764 *
765 * <pre>
766 * guard(C2);
767 * ...
768 * </pre>
769 */
770 protected boolean foldPendingTest(DeoptimizingGuard thisGuard, ValueNode original, Stamp newStamp, GuardRewirer rewireGuardFunction) {
771 for (DeoptimizingGuard pendingGuard : pendingTests) {
772 LogicNode pendingCondition = pendingGuard.getCondition();
773 TriState result = TriState.UNKNOWN;
774 if (pendingCondition instanceof UnaryOpLogicNode) {
775 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) pendingCondition;
776 if (unaryLogicNode.getValue() == original) {
777 result = unaryLogicNode.tryFold(newStamp);
778 }
779 } else if (pendingCondition instanceof BinaryOpLogicNode) {
780 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) pendingCondition;
781 ValueNode x = binaryOpLogicNode.getX();
782 ValueNode y = binaryOpLogicNode.getY();
783 if (x == original) {
784 result = binaryOpLogicNode.tryFold(newStamp, getOtherSafeStamp(y));
785 } else if (y == original) {
786 result = binaryOpLogicNode.tryFold(getOtherSafeStamp(x), newStamp);
787 } else if (binaryOpLogicNode instanceof IntegerEqualsNode && y.isConstant() && x instanceof AndNode) {
788 AndNode and = (AndNode) x;
789 if (and.getY() == y && and.getX() == original) {
790 BinaryOp<And> andOp = ArithmeticOpTable.forStamp(newStamp).getAnd();
791 result = binaryOpLogicNode.tryFold(andOp.foldStamp(newStamp, getOtherSafeStamp(y)), getOtherSafeStamp(y));
792 }
793 }
794 }
795 if (result.isKnown()) {
796 /*
797 * The test case be folded using the information available but the test can only
798 * be moved up if we're sure there's no schedule dependence.
799 */
800 if (canScheduleAbove(thisGuard.getCondition(), pendingGuard.asNode(), original) && foldGuard(thisGuard, pendingGuard, result.toBoolean(), newStamp, rewireGuardFunction)) {
801 return true;
802 }
803 }
804 }
805 return false;
806 }
807
808 private boolean canScheduleAbove(Node n, Node target, ValueNode knownToBeAbove) {
809 Block targetBlock = nodeToBlock.get(target);
810 Block testBlock = nodeToBlock.get(n);
811 if (targetBlock != null && testBlock != null) {
812 if (targetBlock == testBlock) {
813 for (Node fixed : blockToNodes.get(targetBlock)) {
814 if (fixed == n) {
815 return true;
816 } else if (fixed == target) {
817 break;
818 }
819 }
820 } else if (AbstractControlFlowGraph.dominates(testBlock, targetBlock)) {
821 return true;
822 }
823 }
824 InputFilter v = new InputFilter(knownToBeAbove);
825 n.applyInputs(v);
826 return v.ok;
827 }
828
829 protected boolean foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, boolean outcome, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) {
830 DeoptimizationAction action = mergeActions(otherGuard.getAction(), thisGuard.getAction());
831 if (action != null && otherGuard.getSpeculation() == thisGuard.getSpeculation()) {
832 LogicNode condition = (LogicNode) thisGuard.getCondition().copyWithInputs();
833 /*
834 * We have ...; guard(C1); guard(C2);...
835 *
836 * Where the first guard is `otherGuard` and the second one `thisGuard`.
837 *
838 * Depending on `outcome`, we have C2 => C1 or C2 => !C1.
839 *
840 * - If C2 => C1, `mustDeopt` below is false and we transform to ...; guard(C2); ...
841 *
842 * - If C2 => !C1, `mustDeopt` is true and we transform to ..; guard(C1); deopt;
843 */
844 // for the second case, the action of the deopt is copied from there:
845 thisGuard.setAction(action);
846 GuardRewirer rewirer = (guard, result, innerGuardedValueStamp, newInput) -> {
847 // `result` is `outcome`, `guard` is `otherGuard`
848 boolean mustDeopt = result == otherGuard.isNegated();
849 if (rewireGuardFunction.rewire(guard, mustDeopt == thisGuard.isNegated(), innerGuardedValueStamp, newInput)) {
850 if (!mustDeopt) {
851 otherGuard.setCondition(condition, thisGuard.isNegated());
852 otherGuard.setAction(action);
853 otherGuard.setReason(thisGuard.getReason());
854 }
855 return true;
856 }
857 condition.safeDelete();
858 return false;
859 };
860 // Move the later test up
861 return rewireGuards(otherGuard, outcome, null, guardedValueStamp, rewirer);
862 }
863 return false;
864 }
865
866 protected void registerCondition(LogicNode condition, boolean negated, GuardingNode guard) {
867 if (condition.hasMoreThanOneUsage()) {
868 registerNewStamp(condition, negated ? StampFactory.contradiction() : StampFactory.tautology(), guard);
869 }
870 conditions.push(new GuardedCondition(guard, condition, negated));
871 }
872
873 protected InfoElement getInfoElements(ValueNode proxiedValue) {
874 if (proxiedValue == null) {
875 return null;
876 }
877 InfoElement infoElement = map.getAndGrow(proxiedValue);
878 if (infoElement == null) {
879 infoElement = map.getAndGrow(GraphUtil.skipPi(proxiedValue));
880 }
881 return infoElement;
882 }
883
884 protected boolean rewireGuards(GuardingNode guard, boolean result, ValueNode proxifiedInput, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) {
885 counterStampsFound.increment(debug);
886 return rewireGuardFunction.rewire(guard, result, guardedValueStamp, proxifiedInput);
887 }
888
889 protected boolean tryProveCondition(LogicNode node, GuardRewirer rewireGuardFunction) {
890 return tryProveGuardCondition(null, node, rewireGuardFunction);
891 }
892
893 private InfoElement nextElement(InfoElement current) {
894 InfoElement parent = current.getParent();
895 if (parent != null) {
896 return parent;
897 } else {
898 ValueNode proxifiedInput = current.getProxifiedInput();
899 if (proxifiedInput instanceof PiNode) {
900 PiNode piNode = (PiNode) proxifiedInput;
901 return getInfoElements(piNode.getOriginalNode());
902 }
903 }
904 return null;
905 }
906
907 protected boolean tryProveGuardCondition(DeoptimizingGuard thisGuard, LogicNode node, GuardRewirer rewireGuardFunction) {
908 InfoElement infoElement = getInfoElements(node);
909 while (infoElement != null) {
910 Stamp stamp = infoElement.getStamp();
911 JavaConstant constant = (JavaConstant) stamp.asConstant();
912 if (constant != null) {
913 // No proxified input and stamp required.
914 return rewireGuards(infoElement.getGuard(), constant.asBoolean(), null, null, rewireGuardFunction);
915 }
916 infoElement = nextElement(infoElement);
917 }
918
919 for (GuardedCondition guardedCondition : this.conditions) {
920 TriState result = guardedCondition.getCondition().implies(guardedCondition.isNegated(), node);
921 if (result.isKnown()) {
922 return rewireGuards(guardedCondition.guard, result.toBoolean(), null, null, rewireGuardFunction);
923 }
924 }
925
926 if (node instanceof UnaryOpLogicNode) {
927 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) node;
928 ValueNode value = unaryLogicNode.getValue();
929 infoElement = getInfoElements(value);
930 while (infoElement != null) {
931 Stamp stamp = infoElement.getStamp();
932 TriState result = unaryLogicNode.tryFold(stamp);
933 if (result.isKnown()) {
934 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
935 }
936 infoElement = nextElement(infoElement);
937 }
938 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(value);
939 if (foldResult != null) {
940 TriState result = unaryLogicNode.tryFold(foldResult.getRight());
941 if (result.isKnown()) {
942 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction);
943 }
944 }
945 if (thisGuard != null) {
946 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(thisGuard.isNegated());
947 if (newStamp != null && foldPendingTest(thisGuard, value, newStamp, rewireGuardFunction)) {
948 return true;
949 }
950
951 }
952 } else if (node instanceof BinaryOpLogicNode) {
953 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) node;
954 ValueNode x = binaryOpLogicNode.getX();
955 ValueNode y = binaryOpLogicNode.getY();
956 infoElement = getInfoElements(x);
957 while (infoElement != null) {
958 TriState result = binaryOpLogicNode.tryFold(infoElement.getStamp(), y.stamp(NodeView.DEFAULT));
959 if (result.isKnown()) {
960 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
961 }
962 infoElement = nextElement(infoElement);
963 }
964
965 if (y.isConstant()) {
966 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(x);
967 if (foldResult != null) {
968 TriState result = binaryOpLogicNode.tryFold(foldResult.getRight(), y.stamp(NodeView.DEFAULT));
969 if (result.isKnown()) {
970 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction);
971 }
972 }
973 } else {
974 infoElement = getInfoElements(y);
975 while (infoElement != null) {
976 TriState result = binaryOpLogicNode.tryFold(x.stamp(NodeView.DEFAULT), infoElement.getStamp());
977 if (result.isKnown()) {
978 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
979 }
980 infoElement = nextElement(infoElement);
981 }
982 }
983
984 /*
985 * For complex expressions involving constants, see if it's possible to fold the
986 * tests by using stamps one level up in the expression. For instance, (x + n < y)
987 * might fold if something is known about x and all other values are constants. The
988 * reason for the constant restriction is that if more than 1 real value is involved
989 * the code might need to adopt multiple guards to have proper dependences.
990 */
991 if (x instanceof BinaryArithmeticNode<?> && y.isConstant()) {
992 BinaryArithmeticNode<?> binary = (BinaryArithmeticNode<?>) x;
993 if (binary.getY().isConstant()) {
994 infoElement = getInfoElements(binary.getX());
995 while (infoElement != null) {
996 Stamp newStampX = binary.foldStamp(infoElement.getStamp(), binary.getY().stamp(NodeView.DEFAULT));
997 TriState result = binaryOpLogicNode.tryFold(newStampX, y.stamp(NodeView.DEFAULT));
998 if (result.isKnown()) {
999 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), newStampX, rewireGuardFunction);
1000 }
1001 infoElement = nextElement(infoElement);
1002 }
1003 }
1004 }
1005
1006 if (thisGuard != null && binaryOpLogicNode instanceof IntegerEqualsNode && !thisGuard.isNegated()) {
1007 if (y.isConstant() && x instanceof AndNode) {
1008 AndNode and = (AndNode) x;
1009 if (and.getY() == y) {
1010 /*
1011 * This 'and' proves something about some of the bits in and.getX().
1012 * It's equivalent to or'ing in the mask value since those values are
1013 * known to be set.
1014 */
1015 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp(NodeView.DEFAULT)).getOr();
1016 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(and.getX()), getOtherSafeStamp(y));
1017 if (foldPendingTest(thisGuard, and.getX(), newStampX, rewireGuardFunction)) {
1018 return true;
1019 }
1020 }
1021 }
1022 }
1023
1024 if (thisGuard != null) {
1025 if (!x.isConstant()) {
1026 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(thisGuard.isNegated(), getSafeStamp(x), getOtherSafeStamp(y));
1027 if (newStampX != null && foldPendingTest(thisGuard, x, newStampX, rewireGuardFunction)) {
1028 return true;
1029 }
1030 }
1031 if (!y.isConstant()) {
1032 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(thisGuard.isNegated(), getOtherSafeStamp(x), getSafeStamp(y));
1033 if (newStampY != null && foldPendingTest(thisGuard, y, newStampY, rewireGuardFunction)) {
1034 return true;
1035 }
1036 }
1037 }
1038 } else if (node instanceof ShortCircuitOrNode) {
1039 final ShortCircuitOrNode shortCircuitOrNode = (ShortCircuitOrNode) node;
1040 return tryProveCondition(shortCircuitOrNode.getX(), (guard, result, guardedValueStamp, newInput) -> {
1041 if (result == !shortCircuitOrNode.isXNegated()) {
1042 return rewireGuards(guard, true, newInput, guardedValueStamp, rewireGuardFunction);
1043 } else {
1044 return tryProveCondition(shortCircuitOrNode.getY(), (innerGuard, innerResult, innerGuardedValueStamp, innerNewInput) -> {
1045 ValueNode proxifiedInput = newInput;
1046 if (proxifiedInput == null) {
1047 proxifiedInput = innerNewInput;
1048 } else if (innerNewInput != null) {
1049 if (innerNewInput != newInput) {
1050 // Cannot canonicalize due to different proxied inputs.
1051 return false;
1052 }
1053 }
1054 // Can only canonicalize if the guards are equal.
1055 if (innerGuard == guard) {
1056 return rewireGuards(guard, innerResult ^ shortCircuitOrNode.isYNegated(), proxifiedInput, guardedValueStamp, rewireGuardFunction);
1057 }
1058 return false;
1059 });
1060 }
1061 });
1062 }
1063
1064 return false;
1065 }
1066
1067 protected void registerNewStamp(ValueNode maybeProxiedValue, Stamp newStamp, GuardingNode guard) {
1068 registerNewStamp(maybeProxiedValue, newStamp, guard, false);
1069 }
1070
1071 protected void registerNewStamp(ValueNode maybeProxiedValue, Stamp newStamp, GuardingNode guard, boolean propagateThroughPis) {
1072 assert maybeProxiedValue != null;
1073 assert guard != null;
1074
1075 if (newStamp == null || newStamp.isUnrestricted()) {
1076 return;
1077 }
1078
1079 ValueNode value = maybeProxiedValue;
1080 Stamp stamp = newStamp;
1081
1082 while (stamp != null && value != null) {
1083 ValueNode proxiedValue = null;
1084 if (value instanceof PiNode) {
1085 proxiedValue = value;
1086 }
1087 counterStampsRegistered.increment(debug);
1088 debug.log("\t Saving stamp for node %s stamp %s guarded by %s", value, stamp, guard);
1089 assert value instanceof LogicNode || stamp.isCompatible(value.stamp(NodeView.DEFAULT)) : stamp + " vs. " + value.stamp(NodeView.DEFAULT) + " (" + value + ")";
1090 map.setAndGrow(value, new InfoElement(stamp, guard, proxiedValue, map.getAndGrow(value)));
1091 undoOperations.push(value);
1092 if (propagateThroughPis && value instanceof PiNode) {
1093 PiNode piNode = (PiNode) value;
1094 value = piNode.getOriginalNode();
1095 } else if (value instanceof StampInverter) {
1096 StampInverter stampInverter = (StampInverter) value;
1097 value = stampInverter.getValue();
1098 stamp = stampInverter.invertStamp(stamp);
1099 } else {
1100 break;
1101 }
1102 }
1103 }
1104
1105 protected void processAbstractBegin(AbstractBeginNode beginNode) {
1106 Node predecessor = beginNode.predecessor();
1107 if (predecessor instanceof IfNode) {
1108 IfNode ifNode = (IfNode) predecessor;
1109 boolean negated = (ifNode.falseSuccessor() == beginNode);
1110 LogicNode condition = ifNode.condition();
1111 registerNewCondition(condition, negated, beginNode);
1112 } else if (predecessor instanceof TypeSwitchNode) {
1113 TypeSwitchNode typeSwitch = (TypeSwitchNode) predecessor;
1114 processTypeSwitch(beginNode, typeSwitch);
1115 } else if (predecessor instanceof IntegerSwitchNode) {
1116 IntegerSwitchNode integerSwitchNode = (IntegerSwitchNode) predecessor;
1117 processIntegerSwitch(beginNode, integerSwitchNode);
1118 }
1119 }
1120
1121 private static boolean maybeMultipleUsages(ValueNode value) {
1122 if (value.hasMoreThanOneUsage()) {
1123 return true;
1124 } else {
1125 return value instanceof ProxyNode ||
1126 value instanceof PiNode ||
1127 value instanceof StampInverter;
1128 }
1129 }
1130
1131 protected void processIntegerSwitch(AbstractBeginNode beginNode, IntegerSwitchNode integerSwitchNode) {
1132 ValueNode value = integerSwitchNode.value();
1133 if (maybeMultipleUsages(value)) {
1134 Stamp stamp = integerSwitchNode.getValueStampForSuccessor(beginNode);
1135 if (stamp != null) {
1136 registerNewStamp(value, stamp, beginNode);
1137 }
1138 }
1139 }
1140
1141 protected void processTypeSwitch(AbstractBeginNode beginNode, TypeSwitchNode typeSwitch) {
1142 ValueNode hub = typeSwitch.value();
1143 if (hub instanceof LoadHubNode) {
1144 LoadHubNode loadHub = (LoadHubNode) hub;
1145 ValueNode value = loadHub.getValue();
1146 if (maybeMultipleUsages(value)) {
1147 Stamp stamp = typeSwitch.getValueStampForSuccessor(beginNode);
1148 if (stamp != null) {
1149 registerNewStamp(value, stamp, beginNode);
1150 }
1151 }
1152 }
1153 }
1154
1155 @Override
1156 public void exit(Block b, Marks marks) {
1157 int infoElementsMark = marks.infoElementOperations;
1158 while (undoOperations.size() > infoElementsMark) {
1159 Node node = undoOperations.pop();
1160 if (node.isAlive()) {
1161 map.set(node, map.get(node).getParent());
1162 }
1163 }
1164
1165 int conditionsMark = marks.conditions;
1166 while (conditions.size() > conditionsMark) {
1167 conditions.pop();
1168 }
1169 }
1170 }
1171
1172 @FunctionalInterface
1173 protected interface InfoElementProvider {
1174 Iterable<InfoElement> getInfoElements(ValueNode value);
1175 }
1176
1177 /**
1178 * Checks for safe nodes when moving pending tests up.
1179 */
1180 static class InputFilter extends Node.EdgeVisitor {
1181 boolean ok;
1182 private ValueNode value;
1183
1184 InputFilter(ValueNode value) {
1185 this.value = value;
1186 this.ok = true;
1187 }
1188
1189 @Override
1190 public Node apply(Node node, Node curNode) {
1191 if (!ok) {
1192 // Abort the recursion
1193 return curNode;
1194 }
1195 if (!(curNode instanceof ValueNode)) {
1196 ok = false;
1197 return curNode;
1198 }
1199 ValueNode curValue = (ValueNode) curNode;
1200 if (curValue.isConstant() || curValue == value || curValue instanceof ParameterNode) {
1201 return curNode;
1202 }
1203 if (curValue instanceof BinaryNode || curValue instanceof UnaryNode) {
1204 curValue.applyInputs(this);
1205 } else {
1206 ok = false;
1207 }
1208 return curNode;
1209 }
1210 }
1211
1212 @FunctionalInterface
1213 protected interface GuardRewirer {
1214 /**
1215 * Called if the condition could be proven to have a constant value ({@code result}) under
1216 * {@code guard}.
1217 *
1218 * @param guard the guard whose result is proven
1219 * @param result the known result of the guard
1220 * @param newInput new input to pi nodes depending on the new guard
1221 * @return whether the transformation could be applied
1222 */
1223 boolean rewire(GuardingNode guard, boolean result, Stamp guardedValueStamp, ValueNode newInput);
1224 }
1225
1226 protected static final class InfoElement {
1227 private final Stamp stamp;
1228 private final GuardingNode guard;
1229 private final ValueNode proxifiedInput;
1230 private final InfoElement parent;
1231
1232 public InfoElement(Stamp stamp, GuardingNode guard, ValueNode proxifiedInput, InfoElement parent) {
1233 this.stamp = stamp;
1234 this.guard = guard;
1235 this.proxifiedInput = proxifiedInput;
1236 this.parent = parent;
1237 }
1238
1239 public InfoElement getParent() {
1240 return parent;
1241 }
1242
1243 public Stamp getStamp() {
1244 return stamp;
1245 }
1246
1247 public GuardingNode getGuard() {
1248 return guard;
1249 }
1250
1251 public ValueNode getProxifiedInput() {
1252 return proxifiedInput;
1253 }
1254
1255 @Override
1256 public String toString() {
1257 return stamp + " -> " + guard;
1258 }
1259 }
1260
1261 @Override
1262 public float codeSizeIncrease() {
1263 return 1.5f;
1264 }
1265 }