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