1 /*
2 * Copyright (c) 2015, 2017, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.phases.common;
24
25 import java.util.ArrayDeque;
26 import java.util.Deque;
27 import java.util.List;
28
29 import org.graalvm.compiler.core.common.cfg.BlockMap;
30 import org.graalvm.compiler.core.common.type.ArithmeticOpTable;
31 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp;
32 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.And;
33 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Or;
34 import org.graalvm.compiler.core.common.type.IntegerStamp;
35 import org.graalvm.compiler.core.common.type.ObjectStamp;
36 import org.graalvm.compiler.core.common.type.Stamp;
37 import org.graalvm.compiler.core.common.type.StampFactory;
38 import org.graalvm.compiler.debug.CounterKey;
39 import org.graalvm.compiler.debug.DebugCloseable;
40 import org.graalvm.compiler.debug.DebugContext;
41 import org.graalvm.compiler.graph.Node;
42 import org.graalvm.compiler.graph.NodeMap;
43 import org.graalvm.compiler.graph.NodeStack;
44 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
45 import org.graalvm.compiler.nodeinfo.InputType;
46 import org.graalvm.compiler.nodes.AbstractBeginNode;
47 import org.graalvm.compiler.nodes.AbstractMergeNode;
48 import org.graalvm.compiler.nodes.BinaryOpLogicNode;
49 import org.graalvm.compiler.nodes.ConditionAnchorNode;
50 import org.graalvm.compiler.nodes.DeoptimizeNode;
51 import org.graalvm.compiler.nodes.DeoptimizingGuard;
52 import org.graalvm.compiler.nodes.EndNode;
53 import org.graalvm.compiler.nodes.FixedGuardNode;
54 import org.graalvm.compiler.nodes.FixedNode;
55 import org.graalvm.compiler.nodes.FixedWithNextNode;
56 import org.graalvm.compiler.nodes.GuardNode;
57 import org.graalvm.compiler.nodes.IfNode;
58 import org.graalvm.compiler.nodes.LogicNode;
59 import org.graalvm.compiler.nodes.LoopExitNode;
60 import org.graalvm.compiler.nodes.MergeNode;
61 import org.graalvm.compiler.nodes.ParameterNode;
62 import org.graalvm.compiler.nodes.PiNode;
63 import org.graalvm.compiler.nodes.ProxyNode;
64 import org.graalvm.compiler.nodes.ShortCircuitOrNode;
65 import org.graalvm.compiler.nodes.StructuredGraph;
66 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
67 import org.graalvm.compiler.nodes.UnaryOpLogicNode;
68 import org.graalvm.compiler.nodes.ValueNode;
69 import org.graalvm.compiler.nodes.ValuePhiNode;
70 import org.graalvm.compiler.nodes.calc.AndNode;
71 import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode;
72 import org.graalvm.compiler.nodes.calc.BinaryNode;
73 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
74 import org.graalvm.compiler.nodes.calc.UnaryNode;
75 import org.graalvm.compiler.nodes.cfg.Block;
76 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
77 import org.graalvm.compiler.nodes.extended.GuardingNode;
78 import org.graalvm.compiler.nodes.extended.IntegerSwitchNode;
79 import org.graalvm.compiler.nodes.extended.LoadHubNode;
80 import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
81 import org.graalvm.compiler.nodes.java.TypeSwitchNode;
82 import org.graalvm.compiler.nodes.spi.NodeWithState;
83 import org.graalvm.compiler.nodes.spi.StampInverter;
84 import org.graalvm.compiler.nodes.util.GraphUtil;
85 import org.graalvm.compiler.phases.BasePhase;
86 import org.graalvm.compiler.phases.schedule.SchedulePhase;
87 import org.graalvm.compiler.phases.schedule.SchedulePhase.SchedulingStrategy;
88 import org.graalvm.compiler.phases.tiers.PhaseContext;
89 import org.graalvm.util.EconomicMap;
90 import org.graalvm.util.Equivalence;
91 import org.graalvm.util.MapCursor;
92 import org.graalvm.util.Pair;
93
94 import jdk.vm.ci.meta.JavaConstant;
95 import jdk.vm.ci.meta.TriState;
96
97 public class ConditionalEliminationPhase extends BasePhase<PhaseContext> {
98
99 private static final CounterKey counterStampsRegistered = DebugContext.counter("StampsRegistered");
100 private static final CounterKey counterStampsFound = DebugContext.counter("StampsFound");
101 private static final CounterKey counterIfsKilled = DebugContext.counter("CE_KilledIfs");
102 private static final CounterKey counterPhiStampsImproved = DebugContext.counter("CE_ImprovedPhis");
103 private final boolean fullSchedule;
104 private final boolean moveGuards;
105
106 public ConditionalEliminationPhase(boolean fullSchedule) {
107 this(fullSchedule, true);
108 }
109
110 public ConditionalEliminationPhase(boolean fullSchedule, boolean moveGuards) {
111 this.fullSchedule = fullSchedule;
112 this.moveGuards = moveGuards;
113 }
114
115 @Override
116 @SuppressWarnings("try")
117 protected void run(StructuredGraph graph, PhaseContext context) {
118 try (DebugContext.Scope s = graph.getDebug().scope("DominatorConditionalElimination")) {
119 BlockMap<List<Node>> blockToNodes = null;
120 NodeMap<Block> nodeToBlock = null;
121 ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true);
122 if (fullSchedule) {
123 if (moveGuards) {
124 cfg.visitDominatorTree(new MoveGuardsUpwards(), graph.hasValueProxies());
125 }
126 SchedulePhase.run(graph, SchedulingStrategy.EARLIEST, cfg);
127 ScheduleResult r = graph.getLastSchedule();
128 blockToNodes = r.getBlockToNodesMap();
129 nodeToBlock = r.getNodeToBlockMap();
130 } else {
131 nodeToBlock = cfg.getNodeToBlock();
132 blockToNodes = getBlockToNodes(cfg);
133 }
134 ControlFlowGraph.RecursiveVisitor<?> visitor = createVisitor(graph, cfg, blockToNodes, nodeToBlock, context);
135 cfg.visitDominatorTree(visitor, graph.hasValueProxies());
136 }
137 }
138
139 protected BlockMap<List<Node>> getBlockToNodes(@SuppressWarnings("unused") ControlFlowGraph cfg) {
140 return null;
141 }
142
143 protected ControlFlowGraph.RecursiveVisitor<?> createVisitor(StructuredGraph graph, @SuppressWarnings("unused") ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodes,
144 @SuppressWarnings("unused") NodeMap<Block> nodeToBlock, PhaseContext context) {
145 return new Instance(graph, blockToNodes, context);
146 }
147
148 public static class MoveGuardsUpwards implements ControlFlowGraph.RecursiveVisitor<Block> {
149
150 Block anchorBlock;
151
152 @Override
153 @SuppressWarnings("try")
154 public Block enter(Block b) {
155 Block oldAnchorBlock = anchorBlock;
156 if (b.getDominator() == null || b.getDominator().getPostdominator() != b) {
157 // New anchor.
158 anchorBlock = b;
159 }
160
161 AbstractBeginNode beginNode = b.getBeginNode();
162 if (beginNode instanceof AbstractMergeNode && anchorBlock != b) {
163 AbstractMergeNode mergeNode = (AbstractMergeNode) beginNode;
164 for (GuardNode guard : mergeNode.guards().snapshot()) {
165 try (DebugCloseable closeable = guard.withNodeSourcePosition()) {
166 GuardNode newlyCreatedGuard = new GuardNode(guard.getCondition(), anchorBlock.getBeginNode(), guard.getReason(), guard.getAction(), guard.isNegated(), guard.getSpeculation());
167 GuardNode newGuard = mergeNode.graph().unique(newlyCreatedGuard);
168 guard.replaceAndDelete(newGuard);
169 }
170 }
171 }
172
173 FixedNode endNode = b.getEndNode();
174 if (endNode instanceof IfNode) {
175 IfNode node = (IfNode) endNode;
176
177 // Check if we can move guards upwards.
178 AbstractBeginNode trueSuccessor = node.trueSuccessor();
179 EconomicMap<LogicNode, GuardNode> trueGuards = EconomicMap.create(Equivalence.IDENTITY);
180 for (GuardNode guard : trueSuccessor.guards()) {
181 LogicNode condition = guard.getCondition();
182 if (condition.hasMoreThanOneUsage()) {
183 trueGuards.put(condition, guard);
184 }
185 }
186
187 if (!trueGuards.isEmpty()) {
188 for (GuardNode guard : node.falseSuccessor().guards().snapshot()) {
189 GuardNode otherGuard = trueGuards.get(guard.getCondition());
190 if (otherGuard != null && guard.isNegated() == otherGuard.isNegated()) {
191 JavaConstant speculation = otherGuard.getSpeculation();
192 if (speculation == null) {
193 speculation = guard.getSpeculation();
194 } else if (guard.getSpeculation() != null && guard.getSpeculation() != speculation) {
195 // Cannot optimize due to different speculations.
196 continue;
197 }
198 try (DebugCloseable closeable = guard.withNodeSourcePosition()) {
199 GuardNode newlyCreatedGuard = new GuardNode(guard.getCondition(), anchorBlock.getBeginNode(), guard.getReason(), guard.getAction(), guard.isNegated(), speculation);
200 GuardNode newGuard = node.graph().unique(newlyCreatedGuard);
201 if (otherGuard.isAlive()) {
202 otherGuard.replaceAndDelete(newGuard);
203 }
204 guard.replaceAndDelete(newGuard);
205 }
206 }
207 }
208 }
209 }
210 return oldAnchorBlock;
211 }
212
213 @Override
214 public void exit(Block b, Block value) {
215 anchorBlock = value;
216 }
217
218 }
219
220 private static final class PhiInfoElement {
221
222 private EconomicMap<EndNode, InfoElement> infoElements;
223
224 public void set(EndNode end, InfoElement infoElement) {
225 if (infoElements == null) {
226 infoElements = EconomicMap.create(Equivalence.IDENTITY);
227 }
228 infoElements.put(end, infoElement);
229 }
230
231 public InfoElement get(EndNode end) {
232 if (infoElements == null) {
233 return null;
234 }
235 return infoElements.get(end);
236 }
237 }
238
239 public static class Instance implements ControlFlowGraph.RecursiveVisitor<Integer> {
240 protected final NodeMap<InfoElement> map;
241 protected final BlockMap<List<Node>> blockToNodes;
242 protected final CanonicalizerTool tool;
243 protected final NodeStack undoOperations;
244 protected final StructuredGraph graph;
245 protected final DebugContext debug;
246 protected final EconomicMap<MergeNode, EconomicMap<ValuePhiNode, PhiInfoElement>> mergeMaps;
247
248 /**
249 * Tests which may be eliminated because post dominating tests to prove a broader condition.
250 */
251 private Deque<PendingTest> pendingTests;
252
253 public Instance(StructuredGraph graph, BlockMap<List<Node>> blockToNodes, PhaseContext context) {
254 this.graph = graph;
255 this.debug = graph.getDebug();
256 this.blockToNodes = blockToNodes;
257 this.undoOperations = new NodeStack();
258 this.map = graph.createNodeMap();
259 pendingTests = new ArrayDeque<>();
260 tool = GraphUtil.getDefaultSimplifier(context.getMetaAccess(), context.getConstantReflection(), context.getConstantFieldProvider(), false, graph.getAssumptions(), graph.getOptions(),
261 context.getLowerer());
262 mergeMaps = EconomicMap.create();
263 }
264
265 protected void processConditionAnchor(ConditionAnchorNode node) {
266 tryProveCondition(node.condition(), (guard, result, guardedValueStamp, newInput) -> {
267 if (result != node.isNegated()) {
268 node.replaceAtUsages(guard.asNode());
269 GraphUtil.unlinkFixedNode(node);
270 GraphUtil.killWithUnusedFloatingInputs(node);
271 } else {
272 ValueAnchorNode valueAnchor = node.graph().add(new ValueAnchorNode(null));
273 node.replaceAtUsages(valueAnchor);
274 node.graph().replaceFixedWithFixed(node, valueAnchor);
275 }
276 return true;
277 });
278 }
279
280 protected void processGuard(GuardNode node) {
281 if (!tryProveGuardCondition(node, node.getCondition(), (guard, result, guardedValueStamp, newInput) -> {
282 if (result != node.isNegated()) {
283 node.replaceAndDelete(guard.asNode());
284 } else {
285 DeoptimizeNode deopt = node.graph().add(new DeoptimizeNode(node.getAction(), node.getReason(), node.getSpeculation()));
286 AbstractBeginNode beginNode = (AbstractBeginNode) node.getAnchor();
287 FixedNode next = beginNode.next();
288 beginNode.setNext(deopt);
289 GraphUtil.killCFG(next);
290 }
291 return true;
292 })) {
293 registerNewCondition(node.getCondition(), node.isNegated(), node);
294 }
295 }
296
297 protected void processFixedGuard(FixedGuardNode node) {
298 if (!tryProveGuardCondition(node, node.condition(), (guard, result, guardedValueStamp, newInput) -> {
299 if (result != node.isNegated()) {
300 node.replaceAtUsages(guard.asNode());
301 GraphUtil.unlinkFixedNode(node);
302 GraphUtil.killWithUnusedFloatingInputs(node);
303 } else {
304 DeoptimizeNode deopt = node.graph().add(new DeoptimizeNode(node.getAction(), node.getReason(), node.getSpeculation()));
305 deopt.setStateBefore(node.stateBefore());
306 node.replaceAtPredecessor(deopt);
307 GraphUtil.killCFG(node);
308 }
309 debug.log("Kill fixed guard guard");
310 return true;
311 })) {
312 registerNewCondition(node.condition(), node.isNegated(), node);
313 }
314 }
315
316 protected void processIf(IfNode node) {
317 tryProveCondition(node.condition(), (guard, result, guardedValueStamp, newInput) -> {
318 AbstractBeginNode survivingSuccessor = node.getSuccessor(result);
319 survivingSuccessor.replaceAtUsages(InputType.Guard, guard.asNode());
320 survivingSuccessor.replaceAtPredecessor(null);
321 node.replaceAtPredecessor(survivingSuccessor);
322 GraphUtil.killCFG(node);
323 counterIfsKilled.increment(debug);
324 return true;
325 });
326 }
327
328 @Override
329 public Integer enter(Block block) {
330 int mark = undoOperations.size();
331 debug.log("[Pre Processing block %s]", block);
332 // For now conservatively collect guards only within the same block.
333 pendingTests.clear();
334 processNodes(block);
335 return mark;
336 }
337
338 protected void processNodes(Block block) {
339 if (blockToNodes != null) {
340 for (Node n : blockToNodes.get(block)) {
341 if (n.isAlive()) {
342 processNode(n);
343 }
344 }
345 } else {
346 processBlock(block);
347 }
348 }
349
350 private void processBlock(Block block) {
351 FixedNode n = block.getBeginNode();
352 FixedNode endNode = block.getEndNode();
353 debug.log("[Processing block %s]", block);
354 while (n != endNode) {
355 if (n.isDeleted() || endNode.isDeleted()) {
356 // This branch was deleted!
357 return;
358 }
359 FixedNode next = ((FixedWithNextNode) n).next();
360 processNode(n);
361 n = next;
362 }
363 if (endNode.isAlive()) {
364 processNode(endNode);
365 }
366 }
367
368 @SuppressWarnings("try")
369 protected void processNode(Node node) {
370 try (DebugCloseable closeable = node.withNodeSourcePosition()) {
371 if (node instanceof NodeWithState && !(node instanceof GuardingNode)) {
372 pendingTests.clear();
373 }
374
375 if (node instanceof MergeNode) {
376 introducePisForPhis((MergeNode) node);
377 }
378
379 if (node instanceof AbstractBeginNode) {
380 if (node instanceof LoopExitNode && graph.hasValueProxies()) {
381 // Condition must not be used down this path.
382 return;
383 }
384 processAbstractBegin((AbstractBeginNode) node);
385 } else if (node instanceof FixedGuardNode) {
386 processFixedGuard((FixedGuardNode) node);
387 } else if (node instanceof GuardNode) {
388 processGuard((GuardNode) node);
389 } else if (node instanceof ConditionAnchorNode) {
390 processConditionAnchor((ConditionAnchorNode) node);
391 } else if (node instanceof IfNode) {
392 processIf((IfNode) node);
393 } else if (node instanceof EndNode) {
394 processEnd((EndNode) node);
395 }
396 }
397 }
398
399 protected void introducePisForPhis(MergeNode merge) {
400 EconomicMap<ValuePhiNode, PhiInfoElement> mergeMap = this.mergeMaps.get(merge);
401 if (mergeMap != null) {
402 MapCursor<ValuePhiNode, PhiInfoElement> entries = mergeMap.getEntries();
403 while (entries.advance()) {
404 ValuePhiNode phi = entries.getKey();
405 assert phi.isAlive() || phi.isDeleted();
406 /*
407 * Phi might have been killed already via a conditional elimination in another
408 * branch.
409 */
410 if (phi.isDeleted()) {
411 continue;
412 }
413 PhiInfoElement phiInfoElements = entries.getValue();
414 Stamp bestPossibleStamp = null;
415 for (int i = 0; i < phi.valueCount(); ++i) {
416 ValueNode valueAt = phi.valueAt(i);
417 Stamp curBestStamp = valueAt.stamp();
418 InfoElement infoElement = phiInfoElements.get(merge.forwardEndAt(i));
419 if (infoElement != null) {
420 curBestStamp = curBestStamp.join(infoElement.getStamp());
421 }
422
423 if (bestPossibleStamp == null) {
424 bestPossibleStamp = curBestStamp;
425 } else {
426 bestPossibleStamp = bestPossibleStamp.meet(curBestStamp);
427 }
428 }
429
430 Stamp oldStamp = phi.stamp();
431 if (oldStamp.tryImproveWith(bestPossibleStamp) != null) {
432
433 // Need to be careful to not run into stamp update cycles with the iterative
434 // canonicalization.
435 boolean allow = false;
436 if (bestPossibleStamp instanceof ObjectStamp) {
437 // Always allow object stamps.
438 allow = true;
439 } else if (bestPossibleStamp instanceof IntegerStamp) {
440 IntegerStamp integerStamp = (IntegerStamp) bestPossibleStamp;
441 IntegerStamp oldIntegerStamp = (IntegerStamp) oldStamp;
442 if (integerStamp.isPositive() != oldIntegerStamp.isPositive()) {
443 allow = true;
444 } else if (integerStamp.isNegative() != oldIntegerStamp.isNegative()) {
445 allow = true;
446 } else if (integerStamp.isStrictlyPositive() != oldIntegerStamp.isStrictlyPositive()) {
447 allow = true;
448 } else if (integerStamp.isStrictlyNegative() != oldIntegerStamp.isStrictlyNegative()) {
449 allow = true;
450 } else if (integerStamp.asConstant() != null) {
451 allow = true;
452 } else if (oldStamp.isUnrestricted()) {
453 allow = true;
454 }
455 } else {
456 allow = (bestPossibleStamp.asConstant() != null);
457 }
458
459 if (allow) {
460 ValuePhiNode newPhi = graph.addWithoutUnique(new ValuePhiNode(bestPossibleStamp, merge));
461 for (int i = 0; i < phi.valueCount(); ++i) {
462 ValueNode valueAt = phi.valueAt(i);
463 if (bestPossibleStamp.meet(valueAt.stamp()).equals(bestPossibleStamp)) {
464 // Pi not required here.
465 } else {
466 InfoElement infoElement = phiInfoElements.get(merge.forwardEndAt(i));
467 assert infoElement != null;
468 Stamp curBestStamp = infoElement.getStamp();
469 ValueNode input = infoElement.getProxifiedInput();
470 if (input == null) {
471 input = valueAt;
472 }
473 ValueNode valueNode = graph.maybeAddOrUnique(PiNode.create(input, curBestStamp, (ValueNode) infoElement.guard));
474 valueAt = valueNode;
475 }
476 newPhi.addInput(valueAt);
477 }
478 counterPhiStampsImproved.increment(debug);
479 phi.replaceAtUsagesAndDelete(newPhi);
480 }
481 }
482 }
483 }
484 }
485
486 protected void processEnd(EndNode end) {
487 AbstractMergeNode abstractMerge = end.merge();
488 if (abstractMerge instanceof MergeNode) {
489 MergeNode merge = (MergeNode) abstractMerge;
490
491 EconomicMap<ValuePhiNode, PhiInfoElement> mergeMap = this.mergeMaps.get(merge);
492 for (ValuePhiNode phi : merge.valuePhis()) {
493 ValueNode valueAt = phi.valueAt(end);
494 InfoElement infoElement = this.getInfoElements(valueAt);
495 while (infoElement != null) {
496 Stamp newStamp = infoElement.getStamp();
497 if (phi.stamp().tryImproveWith(newStamp) != null) {
498 if (mergeMap == null) {
499 mergeMap = EconomicMap.create();
500 mergeMaps.put(merge, mergeMap);
501 }
502
503 PhiInfoElement phiInfoElement = mergeMap.get(phi);
504 if (phiInfoElement == null) {
505 phiInfoElement = new PhiInfoElement();
506 mergeMap.put(phi, phiInfoElement);
507 }
508
509 phiInfoElement.set(end, infoElement);
510 break;
511 }
512 infoElement = nextElement(infoElement);
513 }
514 }
515 }
516 }
517
518 protected void registerNewCondition(LogicNode condition, boolean negated, GuardingNode guard) {
519 if (condition instanceof UnaryOpLogicNode) {
520 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) condition;
521 ValueNode value = unaryLogicNode.getValue();
522 if (maybeMultipleUsages(value)) {
523 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(negated);
524 registerNewStamp(value, newStamp, guard);
525 }
526 } else if (condition instanceof BinaryOpLogicNode) {
527 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) condition;
528 ValueNode x = binaryOpLogicNode.getX();
529 ValueNode y = binaryOpLogicNode.getY();
530 if (!x.isConstant() && maybeMultipleUsages(x)) {
531 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(negated, getSafeStamp(x), getOtherSafeStamp(y));
532 registerNewStamp(x, newStampX, guard);
533 }
534
535 if (!y.isConstant() && maybeMultipleUsages(y)) {
536 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(negated, getOtherSafeStamp(x), getSafeStamp(y));
537 registerNewStamp(y, newStampY, guard);
538 }
539
540 if (condition instanceof IntegerEqualsNode && guard instanceof DeoptimizingGuard && !negated) {
541 if (y.isConstant() && x instanceof AndNode) {
542 AndNode and = (AndNode) x;
543 ValueNode andX = and.getX();
544 if (and.getY() == y && maybeMultipleUsages(andX)) {
545 /*
546 * This 'and' proves something about some of the bits in and.getX().
547 * It's equivalent to or'ing in the mask value since those values are
548 * known to be set.
549 */
550 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp()).getOr();
551 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(andX), getOtherSafeStamp(y));
552 registerNewStamp(andX, newStampX, guard);
553 }
554 }
555 }
556 }
557 if (guard instanceof DeoptimizingGuard) {
558 pendingTests.push(new PendingTest(condition, (DeoptimizingGuard) guard));
559 }
560 registerCondition(condition, negated, guard);
561 }
562
563 Pair<InfoElement, Stamp> recursiveFoldStamp(Node node) {
564 if (node instanceof UnaryNode) {
565 UnaryNode unary = (UnaryNode) node;
566 ValueNode value = unary.getValue();
567 InfoElement infoElement = getInfoElements(value);
568 while (infoElement != null) {
569 Stamp result = unary.foldStamp(infoElement.getStamp());
570 if (result != null) {
571 return Pair.create(infoElement, result);
572 }
573 infoElement = nextElement(infoElement);
574 }
575 } else if (node instanceof BinaryNode) {
576 BinaryNode binary = (BinaryNode) node;
577 ValueNode y = binary.getY();
578 ValueNode x = binary.getX();
579 if (y.isConstant()) {
580 InfoElement infoElement = getInfoElements(x);
581 while (infoElement != null) {
582 Stamp result = binary.foldStamp(infoElement.stamp, y.stamp());
583 if (result != null) {
584 return Pair.create(infoElement, result);
585 }
586 infoElement = nextElement(infoElement);
587 }
588 }
589 }
590 return null;
591 }
592
593 /**
594 * Get the stamp that may be used for the value for which we are registering the condition.
595 * We may directly use the stamp here without restriction, because any later lookup of the
596 * registered info elements is in the same chain of pi nodes.
597 */
598 private static Stamp getSafeStamp(ValueNode x) {
599 return x.stamp();
600 }
601
602 /**
603 * We can only use the stamp of a second value involved in the condition if we are sure that
604 * we are not implicitly creating a dependency on a pi node that is responsible for that
605 * stamp. For now, we are conservatively only using the stamps of constants. Under certain
606 * circumstances, we may also be able to use the stamp of the value after skipping pi nodes
607 * (e.g., the stamp of a parameter after inlining, or the stamp of a fixed node that can
608 * never be replaced with a pi node via canonicalization).
609 */
610 private static Stamp getOtherSafeStamp(ValueNode x) {
611 if (x.isConstant()) {
612 return x.stamp();
613 }
614 return x.stamp().unrestricted();
615 }
616
617 /**
618 * Recursively try to fold stamps within this expression using information from
619 * {@link #getInfoElements(ValueNode)}. It's only safe to use constants and one
620 * {@link InfoElement} otherwise more than one guard would be required.
621 *
622 * @param node
623 * @return the pair of the @{link InfoElement} used and the stamp produced for the whole
624 * expression
625 */
626 Pair<InfoElement, Stamp> recursiveFoldStampFromInfo(Node node) {
627 return recursiveFoldStamp(node);
628 }
629
630 protected boolean foldPendingTest(DeoptimizingGuard thisGuard, ValueNode original, Stamp newStamp, GuardRewirer rewireGuardFunction) {
631 for (PendingTest pending : pendingTests) {
632 TriState result = TriState.UNKNOWN;
633 if (pending.condition instanceof UnaryOpLogicNode) {
634 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) pending.condition;
635 if (unaryLogicNode.getValue() == original) {
636 result = unaryLogicNode.tryFold(newStamp);
637 }
638 } else if (pending.condition instanceof BinaryOpLogicNode) {
639 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) pending.condition;
640 ValueNode x = binaryOpLogicNode.getX();
641 ValueNode y = binaryOpLogicNode.getY();
642 if (x == original) {
643 result = binaryOpLogicNode.tryFold(newStamp, getOtherSafeStamp(y));
644 } else if (y == original) {
645 result = binaryOpLogicNode.tryFold(getOtherSafeStamp(x), newStamp);
646 } else if (binaryOpLogicNode instanceof IntegerEqualsNode && y.isConstant() && x instanceof AndNode) {
647 AndNode and = (AndNode) x;
648 if (and.getY() == y && and.getX() == original) {
649 BinaryOp<And> andOp = ArithmeticOpTable.forStamp(newStamp).getAnd();
650 result = binaryOpLogicNode.tryFold(andOp.foldStamp(newStamp, getOtherSafeStamp(y)), getOtherSafeStamp(y));
651 }
652 }
653 }
654 if (result.isKnown()) {
655 /*
656 * The test case be folded using the information available but the test can only
657 * be moved up if we're sure there's no schedule dependence. For now limit it to
658 * the original node and constants.
659 */
660 InputFilter v = new InputFilter(original);
661 thisGuard.getCondition().applyInputs(v);
662 if (v.ok && foldGuard(thisGuard, pending.guard, newStamp, rewireGuardFunction)) {
663 return true;
664 }
665 }
666 }
667 return false;
668 }
669
670 protected boolean foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) {
671 if (otherGuard.getAction() == thisGuard.getAction() && otherGuard.getSpeculation() == thisGuard.getSpeculation()) {
672 LogicNode condition = (LogicNode) thisGuard.getCondition().copyWithInputs();
673 GuardRewirer rewirer = (guard, result, innerGuardedValueStamp, newInput) -> {
674 if (rewireGuardFunction.rewire(guard, result, innerGuardedValueStamp, newInput)) {
675 otherGuard.setCondition(condition, thisGuard.isNegated());
676 return true;
677 }
678 condition.safeDelete();
679 return false;
680 };
681 // Move the later test up
682 return rewireGuards(otherGuard, !thisGuard.isNegated(), null, guardedValueStamp, rewirer);
683 }
684 return false;
685 }
686
687 protected void registerCondition(LogicNode condition, boolean negated, GuardingNode guard) {
688 if (condition.getUsageCount() > 1) {
689 registerNewStamp(condition, negated ? StampFactory.contradiction() : StampFactory.tautology(), guard);
690 }
691 }
692
693 protected InfoElement getInfoElements(ValueNode proxiedValue) {
694 ValueNode value = GraphUtil.skipPi(proxiedValue);
695 if (value == null) {
696 return null;
697 }
698 return map.getAndGrow(value);
699 }
700
701 protected boolean rewireGuards(GuardingNode guard, boolean result, ValueNode proxifiedInput, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) {
702 counterStampsFound.increment(debug);
703 return rewireGuardFunction.rewire(guard, result, guardedValueStamp, proxifiedInput);
704 }
705
706 protected boolean tryProveCondition(LogicNode node, GuardRewirer rewireGuardFunction) {
707 return tryProveGuardCondition(null, node, rewireGuardFunction);
708 }
709
710 private InfoElement nextElement(InfoElement current) {
711 InfoElement parent = current.getParent();
712 if (parent != null) {
713 return parent;
714 } else {
715 ValueNode proxifiedInput = current.getProxifiedInput();
716 if (proxifiedInput instanceof PiNode) {
717 PiNode piNode = (PiNode) proxifiedInput;
718 return getInfoElements(piNode.getOriginalNode());
719 }
720 }
721 return null;
722 }
723
724 protected boolean tryProveGuardCondition(DeoptimizingGuard thisGuard, LogicNode node, GuardRewirer rewireGuardFunction) {
725 InfoElement infoElement = getInfoElements(node);
726 while (infoElement != null) {
727 Stamp stamp = infoElement.getStamp();
728 JavaConstant constant = (JavaConstant) stamp.asConstant();
729 if (constant != null) {
730 // No proxified input and stamp required.
731 return rewireGuards(infoElement.getGuard(), constant.asBoolean(), null, null, rewireGuardFunction);
732 }
733 infoElement = nextElement(infoElement);
734 }
735
736 if (node instanceof UnaryOpLogicNode) {
737 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) node;
738 ValueNode value = unaryLogicNode.getValue();
739 infoElement = getInfoElements(value);
740 while (infoElement != null) {
741 Stamp stamp = infoElement.getStamp();
742 TriState result = unaryLogicNode.tryFold(stamp);
743 if (result.isKnown()) {
744 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
745 }
746 infoElement = nextElement(infoElement);
747 }
748 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(value);
749 if (foldResult != null) {
750 TriState result = unaryLogicNode.tryFold(foldResult.getRight());
751 if (result.isKnown()) {
752 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction);
753 }
754 }
755 if (thisGuard != null) {
756 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(thisGuard.isNegated());
757 if (newStamp != null && foldPendingTest(thisGuard, value, newStamp, rewireGuardFunction)) {
758 return true;
759 }
760
761 }
762 } else if (node instanceof BinaryOpLogicNode) {
763 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) node;
764 infoElement = getInfoElements(binaryOpLogicNode);
765 while (infoElement != null) {
766 if (infoElement.getStamp().equals(StampFactory.contradiction())) {
767 return rewireGuards(infoElement.getGuard(), false, infoElement.getProxifiedInput(), null, rewireGuardFunction);
768 } else if (infoElement.getStamp().equals(StampFactory.tautology())) {
769 return rewireGuards(infoElement.getGuard(), true, infoElement.getProxifiedInput(), null, rewireGuardFunction);
770 }
771 infoElement = nextElement(infoElement);
772 }
773
774 ValueNode x = binaryOpLogicNode.getX();
775 ValueNode y = binaryOpLogicNode.getY();
776 infoElement = getInfoElements(x);
777 while (infoElement != null) {
778 TriState result = binaryOpLogicNode.tryFold(infoElement.getStamp(), y.stamp());
779 if (result.isKnown()) {
780 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
781 }
782 infoElement = nextElement(infoElement);
783 }
784
785 if (y.isConstant()) {
786 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(x);
787 if (foldResult != null) {
788 TriState result = binaryOpLogicNode.tryFold(foldResult.getRight(), y.stamp());
789 if (result.isKnown()) {
790 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction);
791 }
792 }
793 } else {
794 infoElement = getInfoElements(y);
795 while (infoElement != null) {
796 TriState result = binaryOpLogicNode.tryFold(x.stamp(), infoElement.getStamp());
797 if (result.isKnown()) {
798 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
799 }
800 infoElement = nextElement(infoElement);
801 }
802 }
803
804 /*
805 * For complex expressions involving constants, see if it's possible to fold the
806 * tests by using stamps one level up in the expression. For instance, (x + n < y)
807 * might fold if something is known about x and all other values are constants. The
808 * reason for the constant restriction is that if more than 1 real value is involved
809 * the code might need to adopt multiple guards to have proper dependences.
810 */
811 if (x instanceof BinaryArithmeticNode<?> && y.isConstant()) {
812 BinaryArithmeticNode<?> binary = (BinaryArithmeticNode<?>) x;
813 if (binary.getY().isConstant()) {
814 infoElement = getInfoElements(binary.getX());
815 while (infoElement != null) {
816 Stamp newStampX = binary.foldStamp(infoElement.getStamp(), binary.getY().stamp());
817 TriState result = binaryOpLogicNode.tryFold(newStampX, y.stamp());
818 if (result.isKnown()) {
819 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), newStampX, rewireGuardFunction);
820 }
821 infoElement = nextElement(infoElement);
822 }
823 }
824 }
825
826 if (thisGuard != null && binaryOpLogicNode instanceof IntegerEqualsNode && !thisGuard.isNegated()) {
827 if (y.isConstant() && x instanceof AndNode) {
828 AndNode and = (AndNode) x;
829 if (and.getY() == y) {
830 /*
831 * This 'and' proves something about some of the bits in and.getX().
832 * It's equivalent to or'ing in the mask value since those values are
833 * known to be set.
834 */
835 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp()).getOr();
836 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(and.getX()), getOtherSafeStamp(y));
837 if (foldPendingTest(thisGuard, and.getX(), newStampX, rewireGuardFunction)) {
838 return true;
839 }
840 }
841 }
842 }
843
844 if (thisGuard != null) {
845 if (!x.isConstant()) {
846 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(thisGuard.isNegated(), getSafeStamp(x), getOtherSafeStamp(y));
847 if (newStampX != null && foldPendingTest(thisGuard, x, newStampX, rewireGuardFunction)) {
848 return true;
849 }
850 }
851 if (!y.isConstant()) {
852 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(thisGuard.isNegated(), getOtherSafeStamp(x), getSafeStamp(y));
853 if (newStampY != null && foldPendingTest(thisGuard, y, newStampY, rewireGuardFunction)) {
854 return true;
855 }
856 }
857 }
858 } else if (node instanceof ShortCircuitOrNode) {
859 final ShortCircuitOrNode shortCircuitOrNode = (ShortCircuitOrNode) node;
860 return tryProveCondition(shortCircuitOrNode.getX(), (guard, result, guardedValueStamp, newInput) -> {
861 if (result == !shortCircuitOrNode.isXNegated()) {
862 return rewireGuards(guard, true, newInput, guardedValueStamp, rewireGuardFunction);
863 } else {
864 return tryProveCondition(shortCircuitOrNode.getY(), (innerGuard, innerResult, innerGuardedValueStamp, innerNewInput) -> {
865 ValueNode proxifiedInput = newInput;
866 if (proxifiedInput == null) {
867 proxifiedInput = innerNewInput;
868 } else if (innerNewInput != null) {
869 if (innerNewInput != newInput) {
870 // Cannot canonicalize due to different proxied inputs.
871 return false;
872 }
873 }
874 // Can only canonicalize if the guards are equal.
875 if (innerGuard == guard) {
876 return rewireGuards(guard, innerResult ^ shortCircuitOrNode.isYNegated(), proxifiedInput, guardedValueStamp, rewireGuardFunction);
877 }
878 return false;
879 });
880 }
881 });
882 }
883
884 return false;
885 }
886
887 protected void registerNewStamp(ValueNode maybeProxiedValue, Stamp newStamp, GuardingNode guard) {
888 assert maybeProxiedValue != null;
889 assert guard != null;
890 if (newStamp != null) {
891 ValueNode value = maybeProxiedValue;
892 Stamp stamp = newStamp;
893 ValueNode proxiedValue = null;
894 if (value instanceof PiNode) {
895 proxiedValue = value;
896 }
897 do {
898 counterStampsRegistered.increment(debug);
899 debug.log("\t Saving stamp for node %s stamp %s guarded by %s", value, stamp, guard);
900 assert value instanceof LogicNode || stamp.isCompatible(value.stamp()) : stamp + " vs. " + value.stamp() + " (" + value + ")";
901 map.setAndGrow(value, new InfoElement(stamp, guard, proxiedValue, map.getAndGrow(value)));
902 undoOperations.push(value);
903 if (value instanceof StampInverter) {
904 StampInverter stampInverter = (StampInverter) value;
905 value = stampInverter.getValue();
906 stamp = stampInverter.invertStamp(stamp);
907 } else {
908 value = null;
909 stamp = null;
910 }
911 } while (value != null && stamp != null);
912 }
913 }
914
915 protected void processAbstractBegin(AbstractBeginNode beginNode) {
916 Node predecessor = beginNode.predecessor();
917 if (predecessor instanceof IfNode) {
918 IfNode ifNode = (IfNode) predecessor;
919 boolean negated = (ifNode.falseSuccessor() == beginNode);
920 LogicNode condition = ifNode.condition();
921 registerNewCondition(condition, negated, beginNode);
922 } else if (predecessor instanceof TypeSwitchNode) {
923 TypeSwitchNode typeSwitch = (TypeSwitchNode) predecessor;
924 processTypeSwitch(beginNode, typeSwitch);
925 } else if (predecessor instanceof IntegerSwitchNode) {
926 IntegerSwitchNode integerSwitchNode = (IntegerSwitchNode) predecessor;
927 processIntegerSwitch(beginNode, integerSwitchNode);
928 }
929 }
930
931 private static boolean maybeMultipleUsages(ValueNode value) {
932 if (value.hasMoreThanOneUsage()) {
933 return true;
934 } else {
935 return value instanceof ProxyNode;
936 }
937 }
938
939 protected void processIntegerSwitch(AbstractBeginNode beginNode, IntegerSwitchNode integerSwitchNode) {
940 ValueNode value = integerSwitchNode.value();
941 if (maybeMultipleUsages(value)) {
942 Stamp stamp = integerSwitchNode.getValueStampForSuccessor(beginNode);
943 if (stamp != null) {
944 registerNewStamp(value, stamp, beginNode);
945 }
946 }
947 }
948
949 protected void processTypeSwitch(AbstractBeginNode beginNode, TypeSwitchNode typeSwitch) {
950 ValueNode hub = typeSwitch.value();
951 if (hub instanceof LoadHubNode) {
952 LoadHubNode loadHub = (LoadHubNode) hub;
953 ValueNode value = loadHub.getValue();
954 if (maybeMultipleUsages(value)) {
955 Stamp stamp = typeSwitch.getValueStampForSuccessor(beginNode);
956 if (stamp != null) {
957 registerNewStamp(value, stamp, beginNode);
958 }
959 }
960 }
961 }
962
963 @Override
964 public void exit(Block b, Integer state) {
965 int mark = state;
966 while (undoOperations.size() > mark) {
967 Node node = undoOperations.pop();
968 if (node.isAlive()) {
969 map.set(node, map.get(node).getParent());
970 }
971 }
972 }
973 }
974
975 @FunctionalInterface
976 protected interface InfoElementProvider {
977 Iterable<InfoElement> getInfoElements(ValueNode value);
978 }
979
980 /**
981 * Checks for safe nodes when moving pending tests up.
982 */
983 static class InputFilter extends Node.EdgeVisitor {
984 boolean ok;
985 private ValueNode value;
986
987 InputFilter(ValueNode value) {
988 this.value = value;
989 this.ok = true;
990 }
991
992 @Override
993 public Node apply(Node node, Node curNode) {
994 if (!ok) {
995 // Abort the recursion
996 return curNode;
997 }
998 if (!(curNode instanceof ValueNode)) {
999 ok = false;
1000 return curNode;
1001 }
1002 ValueNode curValue = (ValueNode) curNode;
1003 if (curValue.isConstant() || curValue == value || curValue instanceof ParameterNode) {
1004 return curNode;
1005 }
1006 if (curValue instanceof BinaryNode || curValue instanceof UnaryNode) {
1007 curValue.applyInputs(this);
1008 } else {
1009 ok = false;
1010 }
1011 return curNode;
1012 }
1013 }
1014
1015 @FunctionalInterface
1016 protected interface GuardRewirer {
1017 /**
1018 * Called if the condition could be proven to have a constant value ({@code result}) under
1019 * {@code guard}.
1020 *
1021 * @param guard the guard whose result is proven
1022 * @param result the known result of the guard
1023 * @param newInput new input to pi nodes depending on the new guard
1024 * @return whether the transformation could be applied
1025 */
1026 boolean rewire(GuardingNode guard, boolean result, Stamp guardedValueStamp, ValueNode newInput);
1027 }
1028
1029 protected static class PendingTest {
1030 private final LogicNode condition;
1031 private final DeoptimizingGuard guard;
1032
1033 public PendingTest(LogicNode condition, DeoptimizingGuard guard) {
1034 this.condition = condition;
1035 this.guard = guard;
1036 }
1037 }
1038
1039 protected static final class InfoElement {
1040 private final Stamp stamp;
1041 private final GuardingNode guard;
1042 private final ValueNode proxifiedInput;
1043 private final InfoElement parent;
1044
1045 public InfoElement(Stamp stamp, GuardingNode guard, ValueNode proxifiedInput, InfoElement parent) {
1046 this.stamp = stamp;
1047 this.guard = guard;
1048 this.proxifiedInput = proxifiedInput;
1049 this.parent = parent;
1050 }
1051
1052 public InfoElement getParent() {
1053 return parent;
1054 }
1055
1056 public Stamp getStamp() {
1057 return stamp;
1058 }
1059
1060 public GuardingNode getGuard() {
1061 return guard;
1062 }
1063
1064 public ValueNode getProxifiedInput() {
1065 return proxifiedInput;
1066 }
1067
1068 @Override
1069 public String toString() {
1070 return stamp + " -> " + guard;
1071 }
1072 }
1073
1074 @Override
1075 public float codeSizeIncrease() {
1076 return 1.5f;
1077 }
1078 }