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.Debug;
39 import org.graalvm.compiler.debug.DebugCloseable;
40 import org.graalvm.compiler.debug.DebugCounter;
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.UnaryOpLogicNode;
67 import org.graalvm.compiler.nodes.ValueNode;
68 import org.graalvm.compiler.nodes.ValuePhiNode;
69 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
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 DebugCounter counterStampsRegistered = Debug.counter("StampsRegistered");
100 private static final DebugCounter counterStampsFound = Debug.counter("StampsFound");
101 private static final DebugCounter counterIfsKilled = Debug.counter("CE_KilledIfs");
102 private static final DebugCounter counterPhiStampsImproved = Debug.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 (Debug.Scope s = Debug.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 EconomicMap<MergeNode, EconomicMap<ValuePhiNode, PhiInfoElement>> mergeMaps;
246
247 /**
248 * Tests which may be eliminated because post dominating tests to prove a broader condition.
249 */
250 private Deque<PendingTest> pendingTests;
251
252 public Instance(StructuredGraph graph, BlockMap<List<Node>> blockToNodes, PhaseContext context) {
253 this.graph = graph;
254 this.blockToNodes = blockToNodes;
255 this.undoOperations = new NodeStack();
256 this.map = graph.createNodeMap();
257 pendingTests = new ArrayDeque<>();
258 tool = GraphUtil.getDefaultSimplifier(context.getMetaAccess(), context.getConstantReflection(), context.getConstantFieldProvider(), false, graph.getAssumptions(), graph.getOptions(),
259 context.getLowerer());
260 mergeMaps = EconomicMap.create();
261 }
262
263 protected void processConditionAnchor(ConditionAnchorNode node) {
264 tryProveCondition(node.condition(), (guard, result, guardedValueStamp, newInput) -> {
265 if (result != node.isNegated()) {
266 node.replaceAtUsages(guard.asNode());
267 GraphUtil.unlinkFixedNode(node);
268 GraphUtil.killWithUnusedFloatingInputs(node);
269 } else {
270 ValueAnchorNode valueAnchor = node.graph().add(new ValueAnchorNode(null));
271 node.replaceAtUsages(valueAnchor);
272 node.graph().replaceFixedWithFixed(node, valueAnchor);
273 }
274 return true;
275 });
276 }
277
278 protected void processGuard(GuardNode node) {
279 if (!tryProveGuardCondition(node, node.getCondition(), (guard, result, guardedValueStamp, newInput) -> {
280 if (result != node.isNegated()) {
281 node.replaceAndDelete(guard.asNode());
282 } else {
283 DeoptimizeNode deopt = node.graph().add(new DeoptimizeNode(node.getAction(), node.getReason(), node.getSpeculation()));
284 AbstractBeginNode beginNode = (AbstractBeginNode) node.getAnchor();
285 FixedNode next = beginNode.next();
286 beginNode.setNext(deopt);
287 GraphUtil.killCFG(next);
288 }
289 return true;
290 })) {
291 registerNewCondition(node.getCondition(), node.isNegated(), node);
292 }
293 }
294
295 protected void processFixedGuard(FixedGuardNode node) {
296 if (!tryProveGuardCondition(node, node.condition(), (guard, result, guardedValueStamp, newInput) -> {
297 if (result != node.isNegated()) {
298 node.replaceAtUsages(guard.asNode());
299 GraphUtil.unlinkFixedNode(node);
300 GraphUtil.killWithUnusedFloatingInputs(node);
301 } else {
302 DeoptimizeNode deopt = node.graph().add(new DeoptimizeNode(node.getAction(), node.getReason(), node.getSpeculation()));
303 deopt.setStateBefore(node.stateBefore());
304 node.replaceAtPredecessor(deopt);
305 GraphUtil.killCFG(node);
306 }
307 Debug.log("Kill fixed guard guard");
308 return true;
309 })) {
310 registerNewCondition(node.condition(), node.isNegated(), node);
311 }
312 }
313
314 protected void processIf(IfNode node) {
315 tryProveCondition(node.condition(), (guard, result, guardedValueStamp, newInput) -> {
316 AbstractBeginNode survivingSuccessor = node.getSuccessor(result);
317 survivingSuccessor.replaceAtUsages(InputType.Guard, guard.asNode());
318 survivingSuccessor.replaceAtPredecessor(null);
319 node.replaceAtPredecessor(survivingSuccessor);
320 GraphUtil.killCFG(node);
321 counterIfsKilled.increment();
322 return true;
323 });
324 }
325
326 @Override
327 public Integer enter(Block block) {
328 int mark = undoOperations.size();
329 Debug.log("[Pre Processing block %s]", block);
330 // For now conservatively collect guards only within the same block.
331 pendingTests.clear();
332 processNodes(block);
333 return mark;
334 }
335
336 protected void processNodes(Block block) {
337 if (blockToNodes != null) {
338 for (Node n : blockToNodes.get(block)) {
339 if (n.isAlive()) {
340 processNode(n);
341 }
342 }
343 } else {
344 processBlock(block);
345 }
346 }
347
348 private void processBlock(Block block) {
349 FixedNode n = block.getBeginNode();
350 FixedNode endNode = block.getEndNode();
351 Debug.log("[Processing block %s]", block);
352 while (n != endNode) {
353 if (n.isDeleted() || endNode.isDeleted()) {
354 // This branch was deleted!
355 return;
356 }
357 FixedNode next = ((FixedWithNextNode) n).next();
358 processNode(n);
359 n = next;
360 }
361 if (endNode.isAlive()) {
362 processNode(endNode);
363 }
364 }
365
366 @SuppressWarnings("try")
367 protected void processNode(Node node) {
368 try (DebugCloseable closeable = node.withNodeSourcePosition()) {
369 if (node instanceof NodeWithState && !(node instanceof GuardingNode)) {
370 pendingTests.clear();
371 }
372
373 if (node instanceof MergeNode) {
374 introducePisForPhis((MergeNode) node);
375 }
376
377 if (node instanceof AbstractBeginNode) {
378 if (node instanceof LoopExitNode && graph.hasValueProxies()) {
379 // Condition must not be used down this path.
380 return;
381 }
382 processAbstractBegin((AbstractBeginNode) node);
383 } else if (node instanceof FixedGuardNode) {
384 processFixedGuard((FixedGuardNode) node);
385 } else if (node instanceof GuardNode) {
386 processGuard((GuardNode) node);
387 } else if (node instanceof ConditionAnchorNode) {
388 processConditionAnchor((ConditionAnchorNode) node);
389 } else if (node instanceof IfNode) {
390 processIf((IfNode) node);
391 } else if (node instanceof EndNode) {
392 processEnd((EndNode) node);
393 }
394 }
395 }
396
397 protected void introducePisForPhis(MergeNode merge) {
398 EconomicMap<ValuePhiNode, PhiInfoElement> mergeMap = this.mergeMaps.get(merge);
399 if (mergeMap != null) {
400 MapCursor<ValuePhiNode, PhiInfoElement> entries = mergeMap.getEntries();
401 while (entries.advance()) {
402 ValuePhiNode phi = entries.getKey();
403 assert phi.isAlive() || phi.isDeleted();
404 /*
405 * Phi might have been killed already via a conditional elimination in another
406 * branch.
407 */
408 if (phi.isDeleted()) {
409 continue;
410 }
411 PhiInfoElement phiInfoElements = entries.getValue();
412 Stamp bestPossibleStamp = null;
413 for (int i = 0; i < phi.valueCount(); ++i) {
414 ValueNode valueAt = phi.valueAt(i);
415 Stamp curBestStamp = valueAt.stamp();
416 InfoElement infoElement = phiInfoElements.get(merge.forwardEndAt(i));
417 if (infoElement != null) {
418 curBestStamp = curBestStamp.join(infoElement.getStamp());
419 }
420
421 if (bestPossibleStamp == null) {
422 bestPossibleStamp = curBestStamp;
423 } else {
424 bestPossibleStamp = bestPossibleStamp.meet(curBestStamp);
425 }
426 }
427
428 Stamp oldStamp = phi.stamp();
429 if (oldStamp.tryImproveWith(bestPossibleStamp) != null) {
430
431 // Need to be careful to not run into stamp update cycles with the iterative
432 // canonicalization.
433 boolean allow = false;
434 if (bestPossibleStamp instanceof ObjectStamp) {
435 // Always allow object stamps.
436 allow = true;
437 } else if (bestPossibleStamp instanceof IntegerStamp) {
438 IntegerStamp integerStamp = (IntegerStamp) bestPossibleStamp;
439 IntegerStamp oldIntegerStamp = (IntegerStamp) oldStamp;
440 if (integerStamp.isPositive() != oldIntegerStamp.isPositive()) {
441 allow = true;
442 } else if (integerStamp.isNegative() != oldIntegerStamp.isNegative()) {
443 allow = true;
444 } else if (integerStamp.isStrictlyPositive() != oldIntegerStamp.isStrictlyPositive()) {
445 allow = true;
446 } else if (integerStamp.isStrictlyNegative() != oldIntegerStamp.isStrictlyNegative()) {
447 allow = true;
448 } else if (integerStamp.asConstant() != null) {
449 allow = true;
450 } else if (oldStamp.isUnrestricted()) {
451 allow = true;
452 }
453 } else {
454 allow = (bestPossibleStamp.asConstant() != null);
455 }
456
457 if (allow) {
458 ValuePhiNode newPhi = graph.addWithoutUnique(new ValuePhiNode(bestPossibleStamp, merge));
459 for (int i = 0; i < phi.valueCount(); ++i) {
460 ValueNode valueAt = phi.valueAt(i);
461 if (bestPossibleStamp.meet(valueAt.stamp()).equals(bestPossibleStamp)) {
462 // Pi not required here.
463 } else {
464 InfoElement infoElement = phiInfoElements.get(merge.forwardEndAt(i));
465 assert infoElement != null;
466 Stamp curBestStamp = infoElement.getStamp();
467 ValueNode input = infoElement.getProxifiedInput();
468 if (input == null) {
469 input = valueAt;
470 }
471 ValueNode valueNode = graph.maybeAddOrUnique(PiNode.create(input, curBestStamp, (ValueNode) infoElement.guard));
472 valueAt = valueNode;
473 }
474 newPhi.addInput(valueAt);
475 }
476 counterPhiStampsImproved.increment();
477 phi.replaceAtUsagesAndDelete(newPhi);
478 }
479 }
480 }
481 }
482 }
483
484 protected void processEnd(EndNode end) {
485 AbstractMergeNode abstractMerge = end.merge();
486 if (abstractMerge instanceof MergeNode) {
487 MergeNode merge = (MergeNode) abstractMerge;
488
489 EconomicMap<ValuePhiNode, PhiInfoElement> mergeMap = this.mergeMaps.get(merge);
490 for (ValuePhiNode phi : merge.valuePhis()) {
491 ValueNode valueAt = phi.valueAt(end);
492 InfoElement infoElement = this.getInfoElements(valueAt);
493 while (infoElement != null) {
494 Stamp newStamp = infoElement.getStamp();
495 if (phi.stamp().tryImproveWith(newStamp) != null) {
496 if (mergeMap == null) {
497 mergeMap = EconomicMap.create();
498 mergeMaps.put(merge, mergeMap);
499 }
500
501 PhiInfoElement phiInfoElement = mergeMap.get(phi);
502 if (phiInfoElement == null) {
503 phiInfoElement = new PhiInfoElement();
504 mergeMap.put(phi, phiInfoElement);
505 }
506
507 phiInfoElement.set(end, infoElement);
508 break;
509 }
510 infoElement = nextElement(infoElement);
511 }
512 }
513 }
514 }
515
516 protected void registerNewCondition(LogicNode condition, boolean negated, GuardingNode guard) {
517 if (condition instanceof UnaryOpLogicNode) {
518 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) condition;
519 ValueNode value = unaryLogicNode.getValue();
520 if (maybeMultipleUsages(value)) {
521 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(negated);
522 registerNewStamp(value, newStamp, guard);
523 }
524 } else if (condition instanceof BinaryOpLogicNode) {
525 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) condition;
526 ValueNode x = binaryOpLogicNode.getX();
527 ValueNode y = binaryOpLogicNode.getY();
528 if (!x.isConstant() && maybeMultipleUsages(x)) {
529 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(negated, getSafeStamp(x), getOtherSafeStamp(y));
530 registerNewStamp(x, newStampX, guard);
531 }
532
533 if (!y.isConstant() && maybeMultipleUsages(y)) {
534 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(negated, getOtherSafeStamp(x), getSafeStamp(y));
535 registerNewStamp(y, newStampY, guard);
536 }
537
538 if (condition instanceof IntegerEqualsNode && guard instanceof DeoptimizingGuard && !negated) {
539 if (y.isConstant() && x instanceof AndNode) {
540 AndNode and = (AndNode) x;
541 ValueNode andX = and.getX();
542 if (and.getY() == y && maybeMultipleUsages(andX)) {
543 /*
544 * This 'and' proves something about some of the bits in and.getX().
545 * It's equivalent to or'ing in the mask value since those values are
546 * known to be set.
547 */
548 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp()).getOr();
549 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(andX), getOtherSafeStamp(y));
550 registerNewStamp(andX, newStampX, guard);
551 }
552 }
553 }
554 }
555 if (guard instanceof DeoptimizingGuard) {
556 pendingTests.push(new PendingTest(condition, (DeoptimizingGuard) guard));
557 }
558 registerCondition(condition, negated, guard);
559 }
560
561 Pair<InfoElement, Stamp> recursiveFoldStamp(Node node) {
562 if (node instanceof UnaryNode) {
563 UnaryNode unary = (UnaryNode) node;
564 ValueNode value = unary.getValue();
565 InfoElement infoElement = getInfoElements(value);
566 while (infoElement != null) {
567 Stamp result = unary.foldStamp(infoElement.getStamp());
568 if (result != null) {
569 return Pair.create(infoElement, result);
570 }
571 infoElement = nextElement(infoElement);
572 }
573 } else if (node instanceof BinaryNode) {
574 BinaryNode binary = (BinaryNode) node;
575 ValueNode y = binary.getY();
576 ValueNode x = binary.getX();
577 if (y.isConstant()) {
578 InfoElement infoElement = getInfoElements(x);
579 while (infoElement != null) {
580 Stamp result = binary.foldStamp(infoElement.stamp, y.stamp());
581 if (result != null) {
582 return Pair.create(infoElement, result);
583 }
584 infoElement = nextElement(infoElement);
585 }
586 }
587 }
588 return null;
589 }
590
591 /**
592 * Get the stamp that may be used for the value for which we are registering the condition.
593 * We may directly use the stamp here without restriction, because any later lookup of the
594 * registered info elements is in the same chain of pi nodes.
595 */
596 private static Stamp getSafeStamp(ValueNode x) {
597 return x.stamp();
598 }
599
600 /**
601 * We can only use the stamp of a second value involved in the condition if we are sure that
602 * we are not implicitly creating a dependency on a pi node that is responsible for that
603 * stamp. For now, we are conservatively only using the stamps of constants. Under certain
604 * circumstances, we may also be able to use the stamp of the value after skipping pi nodes
605 * (e.g., the stamp of a parameter after inlining, or the stamp of a fixed node that can
606 * never be replaced with a pi node via canonicalization).
607 */
608 private static Stamp getOtherSafeStamp(ValueNode x) {
609 if (x.isConstant()) {
610 return x.stamp();
611 }
612 return x.stamp().unrestricted();
613 }
614
615 /**
616 * Recursively try to fold stamps within this expression using information from
617 * {@link #getInfoElements(ValueNode)}. It's only safe to use constants and one
618 * {@link InfoElement} otherwise more than one guard would be required.
619 *
620 * @param node
621 * @return the pair of the @{link InfoElement} used and the stamp produced for the whole
622 * expression
623 */
624 Pair<InfoElement, Stamp> recursiveFoldStampFromInfo(Node node) {
625 return recursiveFoldStamp(node);
626 }
627
628 protected boolean foldPendingTest(DeoptimizingGuard thisGuard, ValueNode original, Stamp newStamp, GuardRewirer rewireGuardFunction) {
629 for (PendingTest pending : pendingTests) {
630 TriState result = TriState.UNKNOWN;
631 if (pending.condition instanceof UnaryOpLogicNode) {
632 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) pending.condition;
633 if (unaryLogicNode.getValue() == original) {
634 result = unaryLogicNode.tryFold(newStamp);
635 }
636 } else if (pending.condition instanceof BinaryOpLogicNode) {
637 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) pending.condition;
638 ValueNode x = binaryOpLogicNode.getX();
639 ValueNode y = binaryOpLogicNode.getY();
640 if (x == original) {
641 result = binaryOpLogicNode.tryFold(newStamp, getOtherSafeStamp(y));
642 } else if (y == original) {
643 result = binaryOpLogicNode.tryFold(getOtherSafeStamp(x), newStamp);
644 } else if (binaryOpLogicNode instanceof IntegerEqualsNode && y.isConstant() && x instanceof AndNode) {
645 AndNode and = (AndNode) x;
646 if (and.getY() == y && and.getX() == original) {
647 BinaryOp<And> andOp = ArithmeticOpTable.forStamp(newStamp).getAnd();
648 result = binaryOpLogicNode.tryFold(andOp.foldStamp(newStamp, getOtherSafeStamp(y)), getOtherSafeStamp(y));
649 }
650 }
651 }
652 if (result.isKnown()) {
653 /*
654 * The test case be folded using the information available but the test can only
655 * be moved up if we're sure there's no schedule dependence. For now limit it to
656 * the original node and constants.
657 */
658 InputFilter v = new InputFilter(original);
659 thisGuard.getCondition().applyInputs(v);
660 if (v.ok && foldGuard(thisGuard, pending.guard, newStamp, rewireGuardFunction)) {
661 return true;
662 }
663 }
664 }
665 return false;
666 }
667
668 protected boolean foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) {
669 if (otherGuard.getAction() == thisGuard.getAction() && otherGuard.getSpeculation() == thisGuard.getSpeculation()) {
670 LogicNode condition = (LogicNode) thisGuard.getCondition().copyWithInputs();
671 GuardRewirer rewirer = (guard, result, innerGuardedValueStamp, newInput) -> {
672 if (rewireGuardFunction.rewire(guard, result, innerGuardedValueStamp, newInput)) {
673 otherGuard.setCondition(condition, thisGuard.isNegated());
674 return true;
675 }
676 condition.safeDelete();
677 return false;
678 };
679 // Move the later test up
680 return rewireGuards(otherGuard, !thisGuard.isNegated(), null, guardedValueStamp, rewirer);
681 }
682 return false;
683 }
684
685 protected void registerCondition(LogicNode condition, boolean negated, GuardingNode guard) {
686 if (condition.getUsageCount() > 1) {
687 registerNewStamp(condition, negated ? StampFactory.contradiction() : StampFactory.tautology(), guard);
688 }
689 }
690
691 protected InfoElement getInfoElements(ValueNode proxiedValue) {
692 ValueNode value = GraphUtil.skipPi(proxiedValue);
693 if (value == null) {
694 return null;
695 }
696 return map.getAndGrow(value);
697 }
698
699 protected boolean rewireGuards(GuardingNode guard, boolean result, ValueNode proxifiedInput, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) {
700 counterStampsFound.increment();
701 return rewireGuardFunction.rewire(guard, result, guardedValueStamp, proxifiedInput);
702 }
703
704 protected boolean tryProveCondition(LogicNode node, GuardRewirer rewireGuardFunction) {
705 return tryProveGuardCondition(null, node, rewireGuardFunction);
706 }
707
708 private InfoElement nextElement(InfoElement current) {
709 InfoElement parent = current.getParent();
710 if (parent != null) {
711 return parent;
712 } else {
713 ValueNode proxifiedInput = current.getProxifiedInput();
714 if (proxifiedInput instanceof PiNode) {
715 PiNode piNode = (PiNode) proxifiedInput;
716 return getInfoElements(piNode.getOriginalNode());
717 }
718 }
719 return null;
720 }
721
722 protected boolean tryProveGuardCondition(DeoptimizingGuard thisGuard, LogicNode node, GuardRewirer rewireGuardFunction) {
723 InfoElement infoElement = getInfoElements(node);
724 while (infoElement != null) {
725 Stamp stamp = infoElement.getStamp();
726 JavaConstant constant = (JavaConstant) stamp.asConstant();
727 if (constant != null) {
728 // No proxified input and stamp required.
729 return rewireGuards(infoElement.getGuard(), constant.asBoolean(), null, null, rewireGuardFunction);
730 }
731 infoElement = nextElement(infoElement);
732 }
733
734 if (node instanceof UnaryOpLogicNode) {
735 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) node;
736 ValueNode value = unaryLogicNode.getValue();
737 infoElement = getInfoElements(value);
738 while (infoElement != null) {
739 Stamp stamp = infoElement.getStamp();
740 TriState result = unaryLogicNode.tryFold(stamp);
741 if (result.isKnown()) {
742 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
743 }
744 infoElement = nextElement(infoElement);
745 }
746 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(value);
747 if (foldResult != null) {
748 TriState result = unaryLogicNode.tryFold(foldResult.getRight());
749 if (result.isKnown()) {
750 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction);
751 }
752 }
753 if (thisGuard != null) {
754 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(thisGuard.isNegated());
755 if (newStamp != null && foldPendingTest(thisGuard, value, newStamp, rewireGuardFunction)) {
756 return true;
757 }
758
759 }
760 } else if (node instanceof BinaryOpLogicNode) {
761 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) node;
762 infoElement = getInfoElements(binaryOpLogicNode);
763 while (infoElement != null) {
764 if (infoElement.getStamp().equals(StampFactory.contradiction())) {
765 return rewireGuards(infoElement.getGuard(), false, infoElement.getProxifiedInput(), null, rewireGuardFunction);
766 } else if (infoElement.getStamp().equals(StampFactory.tautology())) {
767 return rewireGuards(infoElement.getGuard(), true, infoElement.getProxifiedInput(), null, rewireGuardFunction);
768 }
769 infoElement = nextElement(infoElement);
770 }
771
772 ValueNode x = binaryOpLogicNode.getX();
773 ValueNode y = binaryOpLogicNode.getY();
774 infoElement = getInfoElements(x);
775 while (infoElement != null) {
776 TriState result = binaryOpLogicNode.tryFold(infoElement.getStamp(), y.stamp());
777 if (result.isKnown()) {
778 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
779 }
780 infoElement = nextElement(infoElement);
781 }
782
783 if (y.isConstant()) {
784 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(x);
785 if (foldResult != null) {
786 TriState result = binaryOpLogicNode.tryFold(foldResult.getRight(), y.stamp());
787 if (result.isKnown()) {
788 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction);
789 }
790 }
791 } else {
792 infoElement = getInfoElements(y);
793 while (infoElement != null) {
794 TriState result = binaryOpLogicNode.tryFold(x.stamp(), infoElement.getStamp());
795 if (result.isKnown()) {
796 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
797 }
798 infoElement = nextElement(infoElement);
799 }
800 }
801
802 /*
803 * For complex expressions involving constants, see if it's possible to fold the
804 * tests by using stamps one level up in the expression. For instance, (x + n < y)
805 * might fold if something is known about x and all other values are constants. The
806 * reason for the constant restriction is that if more than 1 real value is involved
807 * the code might need to adopt multiple guards to have proper dependences.
808 */
809 if (x instanceof BinaryArithmeticNode<?> && y.isConstant()) {
810 BinaryArithmeticNode<?> binary = (BinaryArithmeticNode<?>) x;
811 if (binary.getY().isConstant()) {
812 infoElement = getInfoElements(binary.getX());
813 while (infoElement != null) {
814 Stamp newStampX = binary.foldStamp(infoElement.getStamp(), binary.getY().stamp());
815 TriState result = binaryOpLogicNode.tryFold(newStampX, y.stamp());
816 if (result.isKnown()) {
817 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), newStampX, rewireGuardFunction);
818 }
819 infoElement = nextElement(infoElement);
820 }
821 }
822 }
823
824 if (thisGuard != null && binaryOpLogicNode instanceof IntegerEqualsNode && !thisGuard.isNegated()) {
825 if (y.isConstant() && x instanceof AndNode) {
826 AndNode and = (AndNode) x;
827 if (and.getY() == y) {
828 /*
829 * This 'and' proves something about some of the bits in and.getX().
830 * It's equivalent to or'ing in the mask value since those values are
831 * known to be set.
832 */
833 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp()).getOr();
834 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(and.getX()), getOtherSafeStamp(y));
835 if (foldPendingTest(thisGuard, and.getX(), newStampX, rewireGuardFunction)) {
836 return true;
837 }
838 }
839 }
840 }
841
842 if (thisGuard != null) {
843 if (!x.isConstant()) {
844 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(thisGuard.isNegated(), getSafeStamp(x), getOtherSafeStamp(y));
845 if (newStampX != null && foldPendingTest(thisGuard, x, newStampX, rewireGuardFunction)) {
846 return true;
847 }
848 }
849 if (!y.isConstant()) {
850 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(thisGuard.isNegated(), getOtherSafeStamp(x), getSafeStamp(y));
851 if (newStampY != null && foldPendingTest(thisGuard, y, newStampY, rewireGuardFunction)) {
852 return true;
853 }
854 }
855 }
856 } else if (node instanceof ShortCircuitOrNode) {
857 final ShortCircuitOrNode shortCircuitOrNode = (ShortCircuitOrNode) node;
858 return tryProveCondition(shortCircuitOrNode.getX(), (guard, result, guardedValueStamp, newInput) -> {
859 if (result == !shortCircuitOrNode.isXNegated()) {
860 return rewireGuards(guard, true, newInput, guardedValueStamp, rewireGuardFunction);
861 } else {
862 return tryProveCondition(shortCircuitOrNode.getY(), (innerGuard, innerResult, innerGuardedValueStamp, innerNewInput) -> {
863 ValueNode proxifiedInput = newInput;
864 if (proxifiedInput == null) {
865 proxifiedInput = innerNewInput;
866 } else if (innerNewInput != null) {
867 if (innerNewInput != newInput) {
868 // Cannot canonicalize due to different proxied inputs.
869 return false;
870 }
871 }
872 // Can only canonicalize if the guards are equal.
873 if (innerGuard == guard) {
874 return rewireGuards(guard, innerResult ^ shortCircuitOrNode.isYNegated(), proxifiedInput, guardedValueStamp, rewireGuardFunction);
875 }
876 return false;
877 });
878 }
879 });
880 }
881
882 return false;
883 }
884
885 protected void registerNewStamp(ValueNode maybeProxiedValue, Stamp newStamp, GuardingNode guard) {
886 assert maybeProxiedValue != null;
887 assert guard != null;
888 if (newStamp != null) {
889 ValueNode value = maybeProxiedValue;
890 Stamp stamp = newStamp;
891 ValueNode proxiedValue = null;
892 if (value instanceof PiNode) {
893 proxiedValue = value;
894 }
895 do {
896 counterStampsRegistered.increment();
897 Debug.log("\t Saving stamp for node %s stamp %s guarded by %s", value, stamp, guard);
898 assert value instanceof LogicNode || stamp.isCompatible(value.stamp()) : stamp + " vs. " + value.stamp() + " (" + value + ")";
899 map.setAndGrow(value, new InfoElement(stamp, guard, proxiedValue, map.getAndGrow(value)));
900 undoOperations.push(value);
901 if (value instanceof StampInverter) {
902 StampInverter stampInverter = (StampInverter) value;
903 value = stampInverter.getValue();
904 stamp = stampInverter.invertStamp(stamp);
905 } else {
906 value = null;
907 stamp = null;
908 }
909 } while (value != null && stamp != null);
910 }
911 }
912
913 protected void processAbstractBegin(AbstractBeginNode beginNode) {
914 Node predecessor = beginNode.predecessor();
915 if (predecessor instanceof IfNode) {
916 IfNode ifNode = (IfNode) predecessor;
917 boolean negated = (ifNode.falseSuccessor() == beginNode);
918 LogicNode condition = ifNode.condition();
919 registerNewCondition(condition, negated, beginNode);
920 } else if (predecessor instanceof TypeSwitchNode) {
921 TypeSwitchNode typeSwitch = (TypeSwitchNode) predecessor;
922 processTypeSwitch(beginNode, typeSwitch);
923 } else if (predecessor instanceof IntegerSwitchNode) {
924 IntegerSwitchNode integerSwitchNode = (IntegerSwitchNode) predecessor;
925 processIntegerSwitch(beginNode, integerSwitchNode);
926 }
927 }
928
929 private static boolean maybeMultipleUsages(ValueNode value) {
930 if (value.hasMoreThanOneUsage()) {
931 return true;
932 } else {
933 return value instanceof ProxyNode;
934 }
935 }
936
937 protected void processIntegerSwitch(AbstractBeginNode beginNode, IntegerSwitchNode integerSwitchNode) {
938 ValueNode value = integerSwitchNode.value();
939 if (maybeMultipleUsages(value)) {
940 Stamp stamp = integerSwitchNode.getValueStampForSuccessor(beginNode);
941 if (stamp != null) {
942 registerNewStamp(value, stamp, beginNode);
943 }
944 }
945 }
946
947 protected void processTypeSwitch(AbstractBeginNode beginNode, TypeSwitchNode typeSwitch) {
948 ValueNode hub = typeSwitch.value();
949 if (hub instanceof LoadHubNode) {
950 LoadHubNode loadHub = (LoadHubNode) hub;
951 ValueNode value = loadHub.getValue();
952 if (maybeMultipleUsages(value)) {
953 Stamp stamp = typeSwitch.getValueStampForSuccessor(beginNode);
954 if (stamp != null) {
955 registerNewStamp(value, stamp, beginNode);
956 }
957 }
958 }
959 }
960
961 @Override
962 public void exit(Block b, Integer state) {
963 int mark = state;
964 while (undoOperations.size() > mark) {
965 Node node = undoOperations.pop();
966 if (node.isAlive()) {
967 map.set(node, map.get(node).getParent());
968 }
969 }
970 }
971 }
972
973 @FunctionalInterface
974 protected interface InfoElementProvider {
975 Iterable<InfoElement> getInfoElements(ValueNode value);
976 }
977
978 /**
979 * Checks for safe nodes when moving pending tests up.
980 */
981 static class InputFilter extends Node.EdgeVisitor {
982 boolean ok;
983 private ValueNode value;
984
985 InputFilter(ValueNode value) {
986 this.value = value;
987 this.ok = true;
988 }
989
990 @Override
991 public Node apply(Node node, Node curNode) {
992 if (!ok) {
993 // Abort the recursion
994 return curNode;
995 }
996 if (!(curNode instanceof ValueNode)) {
997 ok = false;
998 return curNode;
999 }
1000 ValueNode curValue = (ValueNode) curNode;
1001 if (curValue.isConstant() || curValue == value || curValue instanceof ParameterNode) {
1002 return curNode;
1003 }
1004 if (curValue instanceof BinaryNode || curValue instanceof UnaryNode) {
1005 curValue.applyInputs(this);
1006 } else {
1007 ok = false;
1008 }
1009 return curNode;
1010 }
1011 }
1012
1013 @FunctionalInterface
1014 protected interface GuardRewirer {
1015 /**
1016 * Called if the condition could be proven to have a constant value ({@code result}) under
1017 * {@code guard}.
1018 *
1019 * @param guard the guard whose result is proven
1020 * @param result the known result of the guard
1021 * @param newInput new input to pi nodes depending on the new guard
1022 * @return whether the transformation could be applied
1023 */
1024 boolean rewire(GuardingNode guard, boolean result, Stamp guardedValueStamp, ValueNode newInput);
1025 }
1026
1027 protected static class PendingTest {
1028 private final LogicNode condition;
1029 private final DeoptimizingGuard guard;
1030
1031 public PendingTest(LogicNode condition, DeoptimizingGuard guard) {
1032 this.condition = condition;
1033 this.guard = guard;
1034 }
1035 }
1036
1037 protected static final class InfoElement {
1038 private final Stamp stamp;
1039 private final GuardingNode guard;
1040 private final ValueNode proxifiedInput;
1041 private final InfoElement parent;
1042
1043 public InfoElement(Stamp stamp, GuardingNode guard, ValueNode proxifiedInput, InfoElement parent) {
1044 this.stamp = stamp;
1045 this.guard = guard;
1046 this.proxifiedInput = proxifiedInput;
1047 this.parent = parent;
1048 }
1049
1050 public InfoElement getParent() {
1051 return parent;
1052 }
1053
1054 public Stamp getStamp() {
1055 return stamp;
1056 }
1057
1058 public GuardingNode getGuard() {
1059 return guard;
1060 }
1061
1062 public ValueNode getProxifiedInput() {
1063 return proxifiedInput;
1064 }
1065
1066 @Override
1067 public String toString() {
1068 return stamp + " -> " + guard;
1069 }
1070 }
1071
1072 @Override
1073 public float codeSizeIncrease() {
1074 return 1.5f;
1075 }
1076 }