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<DeoptimizingGuard> 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 assert ((DeoptimizingGuard) guard).getCondition() == condition;
559 pendingTests.push((DeoptimizingGuard) guard);
560 }
561 registerCondition(condition, negated, guard);
562 }
563
564 Pair<InfoElement, Stamp> recursiveFoldStamp(Node node) {
565 if (node instanceof UnaryNode) {
566 UnaryNode unary = (UnaryNode) node;
567 ValueNode value = unary.getValue();
568 InfoElement infoElement = getInfoElements(value);
569 while (infoElement != null) {
570 Stamp result = unary.foldStamp(infoElement.getStamp());
571 if (result != null) {
572 return Pair.create(infoElement, result);
573 }
574 infoElement = nextElement(infoElement);
575 }
576 } else if (node instanceof BinaryNode) {
577 BinaryNode binary = (BinaryNode) node;
578 ValueNode y = binary.getY();
579 ValueNode x = binary.getX();
580 if (y.isConstant()) {
581 InfoElement infoElement = getInfoElements(x);
582 while (infoElement != null) {
583 Stamp result = binary.foldStamp(infoElement.stamp, y.stamp());
584 if (result != null) {
585 return Pair.create(infoElement, result);
586 }
587 infoElement = nextElement(infoElement);
588 }
589 }
590 }
591 return null;
592 }
593
594 /**
595 * Get the stamp that may be used for the value for which we are registering the condition.
596 * We may directly use the stamp here without restriction, because any later lookup of the
597 * registered info elements is in the same chain of pi nodes.
598 */
599 private static Stamp getSafeStamp(ValueNode x) {
600 return x.stamp();
601 }
602
603 /**
604 * We can only use the stamp of a second value involved in the condition if we are sure that
605 * we are not implicitly creating a dependency on a pi node that is responsible for that
606 * stamp. For now, we are conservatively only using the stamps of constants. Under certain
607 * circumstances, we may also be able to use the stamp of the value after skipping pi nodes
608 * (e.g., the stamp of a parameter after inlining, or the stamp of a fixed node that can
609 * never be replaced with a pi node via canonicalization).
610 */
611 private static Stamp getOtherSafeStamp(ValueNode x) {
612 if (x.isConstant()) {
613 return x.stamp();
614 }
615 return x.stamp().unrestricted();
616 }
617
618 /**
619 * Recursively try to fold stamps within this expression using information from
620 * {@link #getInfoElements(ValueNode)}. It's only safe to use constants and one
621 * {@link InfoElement} otherwise more than one guard would be required.
622 *
623 * @param node
624 * @return the pair of the @{link InfoElement} used and the stamp produced for the whole
625 * expression
626 */
627 Pair<InfoElement, Stamp> recursiveFoldStampFromInfo(Node node) {
628 return recursiveFoldStamp(node);
629 }
630
631 protected boolean foldPendingTest(DeoptimizingGuard thisGuard, ValueNode original, Stamp newStamp, GuardRewirer rewireGuardFunction) {
632 for (DeoptimizingGuard pendingGuard : pendingTests) {
633 LogicNode pendingCondition = pendingGuard.getCondition();
634 TriState result = TriState.UNKNOWN;
635 if (pendingCondition instanceof UnaryOpLogicNode) {
636 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) pendingCondition;
637 if (unaryLogicNode.getValue() == original) {
638 result = unaryLogicNode.tryFold(newStamp);
639 }
640 } else if (pendingCondition instanceof BinaryOpLogicNode) {
641 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) pendingCondition;
642 ValueNode x = binaryOpLogicNode.getX();
643 ValueNode y = binaryOpLogicNode.getY();
644 if (x == original) {
645 result = binaryOpLogicNode.tryFold(newStamp, getOtherSafeStamp(y));
646 } else if (y == original) {
647 result = binaryOpLogicNode.tryFold(getOtherSafeStamp(x), newStamp);
648 } else if (binaryOpLogicNode instanceof IntegerEqualsNode && y.isConstant() && x instanceof AndNode) {
649 AndNode and = (AndNode) x;
650 if (and.getY() == y && and.getX() == original) {
651 BinaryOp<And> andOp = ArithmeticOpTable.forStamp(newStamp).getAnd();
652 result = binaryOpLogicNode.tryFold(andOp.foldStamp(newStamp, getOtherSafeStamp(y)), getOtherSafeStamp(y));
653 }
654 }
655 }
656 if (result.isKnown()) {
657 /*
658 * The test case be folded using the information available but the test can only
659 * be moved up if we're sure there's no schedule dependence. For now limit it to
660 * the original node and constants.
661 */
662 InputFilter v = new InputFilter(original);
663 thisGuard.getCondition().applyInputs(v);
664 if (v.ok && foldGuard(thisGuard, pendingGuard, newStamp, rewireGuardFunction)) {
665 return true;
666 }
667 }
668 }
669 return false;
670 }
671
672 protected boolean foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) {
673 if (otherGuard.getAction() == thisGuard.getAction() && otherGuard.getSpeculation() == thisGuard.getSpeculation()) {
674 LogicNode condition = (LogicNode) thisGuard.getCondition().copyWithInputs();
675 GuardRewirer rewirer = (guard, result, innerGuardedValueStamp, newInput) -> {
676 if (rewireGuardFunction.rewire(guard, result, innerGuardedValueStamp, newInput)) {
677 otherGuard.setCondition(condition, thisGuard.isNegated());
678 return true;
679 }
680 condition.safeDelete();
681 return false;
682 };
683 // Move the later test up
684 return rewireGuards(otherGuard, !thisGuard.isNegated(), null, guardedValueStamp, rewirer);
685 }
686 return false;
687 }
688
689 protected void registerCondition(LogicNode condition, boolean negated, GuardingNode guard) {
690 if (condition.getUsageCount() > 1) {
691 registerNewStamp(condition, negated ? StampFactory.contradiction() : StampFactory.tautology(), guard);
692 }
693 }
694
695 protected InfoElement getInfoElements(ValueNode proxiedValue) {
696 ValueNode value = GraphUtil.skipPi(proxiedValue);
697 if (value == null) {
698 return null;
699 }
700 return map.getAndGrow(value);
701 }
702
703 protected boolean rewireGuards(GuardingNode guard, boolean result, ValueNode proxifiedInput, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) {
704 counterStampsFound.increment(debug);
705 return rewireGuardFunction.rewire(guard, result, guardedValueStamp, proxifiedInput);
706 }
707
708 protected boolean tryProveCondition(LogicNode node, GuardRewirer rewireGuardFunction) {
709 return tryProveGuardCondition(null, node, rewireGuardFunction);
710 }
711
712 private InfoElement nextElement(InfoElement current) {
713 InfoElement parent = current.getParent();
714 if (parent != null) {
715 return parent;
716 } else {
717 ValueNode proxifiedInput = current.getProxifiedInput();
718 if (proxifiedInput instanceof PiNode) {
719 PiNode piNode = (PiNode) proxifiedInput;
720 return getInfoElements(piNode.getOriginalNode());
721 }
722 }
723 return null;
724 }
725
726 protected boolean tryProveGuardCondition(DeoptimizingGuard thisGuard, LogicNode node, GuardRewirer rewireGuardFunction) {
727 InfoElement infoElement = getInfoElements(node);
728 while (infoElement != null) {
729 Stamp stamp = infoElement.getStamp();
730 JavaConstant constant = (JavaConstant) stamp.asConstant();
731 if (constant != null) {
732 // No proxified input and stamp required.
733 return rewireGuards(infoElement.getGuard(), constant.asBoolean(), null, null, rewireGuardFunction);
734 }
735 infoElement = nextElement(infoElement);
736 }
737
738 if (node instanceof UnaryOpLogicNode) {
739 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) node;
740 ValueNode value = unaryLogicNode.getValue();
741 infoElement = getInfoElements(value);
742 while (infoElement != null) {
743 Stamp stamp = infoElement.getStamp();
744 TriState result = unaryLogicNode.tryFold(stamp);
745 if (result.isKnown()) {
746 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
747 }
748 infoElement = nextElement(infoElement);
749 }
750 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(value);
751 if (foldResult != null) {
752 TriState result = unaryLogicNode.tryFold(foldResult.getRight());
753 if (result.isKnown()) {
754 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction);
755 }
756 }
757 if (thisGuard != null) {
758 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(thisGuard.isNegated());
759 if (newStamp != null && foldPendingTest(thisGuard, value, newStamp, rewireGuardFunction)) {
760 return true;
761 }
762
763 }
764 } else if (node instanceof BinaryOpLogicNode) {
765 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) node;
766 infoElement = getInfoElements(binaryOpLogicNode);
767 while (infoElement != null) {
768 if (infoElement.getStamp().equals(StampFactory.contradiction())) {
769 return rewireGuards(infoElement.getGuard(), false, infoElement.getProxifiedInput(), null, rewireGuardFunction);
770 } else if (infoElement.getStamp().equals(StampFactory.tautology())) {
771 return rewireGuards(infoElement.getGuard(), true, infoElement.getProxifiedInput(), null, rewireGuardFunction);
772 }
773 infoElement = nextElement(infoElement);
774 }
775
776 ValueNode x = binaryOpLogicNode.getX();
777 ValueNode y = binaryOpLogicNode.getY();
778 infoElement = getInfoElements(x);
779 while (infoElement != null) {
780 TriState result = binaryOpLogicNode.tryFold(infoElement.getStamp(), y.stamp());
781 if (result.isKnown()) {
782 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
783 }
784 infoElement = nextElement(infoElement);
785 }
786
787 if (y.isConstant()) {
788 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(x);
789 if (foldResult != null) {
790 TriState result = binaryOpLogicNode.tryFold(foldResult.getRight(), y.stamp());
791 if (result.isKnown()) {
792 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction);
793 }
794 }
795 } else {
796 infoElement = getInfoElements(y);
797 while (infoElement != null) {
798 TriState result = binaryOpLogicNode.tryFold(x.stamp(), infoElement.getStamp());
799 if (result.isKnown()) {
800 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
801 }
802 infoElement = nextElement(infoElement);
803 }
804 }
805
806 /*
807 * For complex expressions involving constants, see if it's possible to fold the
808 * tests by using stamps one level up in the expression. For instance, (x + n < y)
809 * might fold if something is known about x and all other values are constants. The
810 * reason for the constant restriction is that if more than 1 real value is involved
811 * the code might need to adopt multiple guards to have proper dependences.
812 */
813 if (x instanceof BinaryArithmeticNode<?> && y.isConstant()) {
814 BinaryArithmeticNode<?> binary = (BinaryArithmeticNode<?>) x;
815 if (binary.getY().isConstant()) {
816 infoElement = getInfoElements(binary.getX());
817 while (infoElement != null) {
818 Stamp newStampX = binary.foldStamp(infoElement.getStamp(), binary.getY().stamp());
819 TriState result = binaryOpLogicNode.tryFold(newStampX, y.stamp());
820 if (result.isKnown()) {
821 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), newStampX, rewireGuardFunction);
822 }
823 infoElement = nextElement(infoElement);
824 }
825 }
826 }
827
828 if (thisGuard != null && binaryOpLogicNode instanceof IntegerEqualsNode && !thisGuard.isNegated()) {
829 if (y.isConstant() && x instanceof AndNode) {
830 AndNode and = (AndNode) x;
831 if (and.getY() == y) {
832 /*
833 * This 'and' proves something about some of the bits in and.getX().
834 * It's equivalent to or'ing in the mask value since those values are
835 * known to be set.
836 */
837 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp()).getOr();
838 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(and.getX()), getOtherSafeStamp(y));
839 if (foldPendingTest(thisGuard, and.getX(), newStampX, rewireGuardFunction)) {
840 return true;
841 }
842 }
843 }
844 }
845
846 if (thisGuard != null) {
847 if (!x.isConstant()) {
848 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(thisGuard.isNegated(), getSafeStamp(x), getOtherSafeStamp(y));
849 if (newStampX != null && foldPendingTest(thisGuard, x, newStampX, rewireGuardFunction)) {
850 return true;
851 }
852 }
853 if (!y.isConstant()) {
854 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(thisGuard.isNegated(), getOtherSafeStamp(x), getSafeStamp(y));
855 if (newStampY != null && foldPendingTest(thisGuard, y, newStampY, rewireGuardFunction)) {
856 return true;
857 }
858 }
859 }
860 } else if (node instanceof ShortCircuitOrNode) {
861 final ShortCircuitOrNode shortCircuitOrNode = (ShortCircuitOrNode) node;
862 return tryProveCondition(shortCircuitOrNode.getX(), (guard, result, guardedValueStamp, newInput) -> {
863 if (result == !shortCircuitOrNode.isXNegated()) {
864 return rewireGuards(guard, true, newInput, guardedValueStamp, rewireGuardFunction);
865 } else {
866 return tryProveCondition(shortCircuitOrNode.getY(), (innerGuard, innerResult, innerGuardedValueStamp, innerNewInput) -> {
867 ValueNode proxifiedInput = newInput;
868 if (proxifiedInput == null) {
869 proxifiedInput = innerNewInput;
870 } else if (innerNewInput != null) {
871 if (innerNewInput != newInput) {
872 // Cannot canonicalize due to different proxied inputs.
873 return false;
874 }
875 }
876 // Can only canonicalize if the guards are equal.
877 if (innerGuard == guard) {
878 return rewireGuards(guard, innerResult ^ shortCircuitOrNode.isYNegated(), proxifiedInput, guardedValueStamp, rewireGuardFunction);
879 }
880 return false;
881 });
882 }
883 });
884 }
885
886 return false;
887 }
888
889 protected void registerNewStamp(ValueNode maybeProxiedValue, Stamp newStamp, GuardingNode guard) {
890 assert maybeProxiedValue != null;
891 assert guard != null;
892 if (newStamp != null) {
893 ValueNode value = maybeProxiedValue;
894 Stamp stamp = newStamp;
895 ValueNode proxiedValue = null;
896 if (value instanceof PiNode) {
897 proxiedValue = value;
898 }
899 do {
900 counterStampsRegistered.increment(debug);
901 debug.log("\t Saving stamp for node %s stamp %s guarded by %s", value, stamp, guard);
902 assert value instanceof LogicNode || stamp.isCompatible(value.stamp()) : stamp + " vs. " + value.stamp() + " (" + value + ")";
903 map.setAndGrow(value, new InfoElement(stamp, guard, proxiedValue, map.getAndGrow(value)));
904 undoOperations.push(value);
905 if (value instanceof StampInverter) {
906 StampInverter stampInverter = (StampInverter) value;
907 value = stampInverter.getValue();
908 stamp = stampInverter.invertStamp(stamp);
909 } else {
910 value = null;
911 stamp = null;
912 }
913 } while (value != null && stamp != null);
914 }
915 }
916
917 protected void processAbstractBegin(AbstractBeginNode beginNode) {
918 Node predecessor = beginNode.predecessor();
919 if (predecessor instanceof IfNode) {
920 IfNode ifNode = (IfNode) predecessor;
921 boolean negated = (ifNode.falseSuccessor() == beginNode);
922 LogicNode condition = ifNode.condition();
923 registerNewCondition(condition, negated, beginNode);
924 } else if (predecessor instanceof TypeSwitchNode) {
925 TypeSwitchNode typeSwitch = (TypeSwitchNode) predecessor;
926 processTypeSwitch(beginNode, typeSwitch);
927 } else if (predecessor instanceof IntegerSwitchNode) {
928 IntegerSwitchNode integerSwitchNode = (IntegerSwitchNode) predecessor;
929 processIntegerSwitch(beginNode, integerSwitchNode);
930 }
931 }
932
933 private static boolean maybeMultipleUsages(ValueNode value) {
934 if (value.hasMoreThanOneUsage()) {
935 return true;
936 } else {
937 return value instanceof ProxyNode;
938 }
939 }
940
941 protected void processIntegerSwitch(AbstractBeginNode beginNode, IntegerSwitchNode integerSwitchNode) {
942 ValueNode value = integerSwitchNode.value();
943 if (maybeMultipleUsages(value)) {
944 Stamp stamp = integerSwitchNode.getValueStampForSuccessor(beginNode);
945 if (stamp != null) {
946 registerNewStamp(value, stamp, beginNode);
947 }
948 }
949 }
950
951 protected void processTypeSwitch(AbstractBeginNode beginNode, TypeSwitchNode typeSwitch) {
952 ValueNode hub = typeSwitch.value();
953 if (hub instanceof LoadHubNode) {
954 LoadHubNode loadHub = (LoadHubNode) hub;
955 ValueNode value = loadHub.getValue();
956 if (maybeMultipleUsages(value)) {
957 Stamp stamp = typeSwitch.getValueStampForSuccessor(beginNode);
958 if (stamp != null) {
959 registerNewStamp(value, stamp, beginNode);
960 }
961 }
962 }
963 }
964
965 @Override
966 public void exit(Block b, Integer state) {
967 int mark = state;
968 while (undoOperations.size() > mark) {
969 Node node = undoOperations.pop();
970 if (node.isAlive()) {
971 map.set(node, map.get(node).getParent());
972 }
973 }
974 }
975 }
976
977 @FunctionalInterface
978 protected interface InfoElementProvider {
979 Iterable<InfoElement> getInfoElements(ValueNode value);
980 }
981
982 /**
983 * Checks for safe nodes when moving pending tests up.
984 */
985 static class InputFilter extends Node.EdgeVisitor {
986 boolean ok;
987 private ValueNode value;
988
989 InputFilter(ValueNode value) {
990 this.value = value;
991 this.ok = true;
992 }
993
994 @Override
995 public Node apply(Node node, Node curNode) {
996 if (!ok) {
997 // Abort the recursion
998 return curNode;
999 }
1000 if (!(curNode instanceof ValueNode)) {
1001 ok = false;
1002 return curNode;
1003 }
1004 ValueNode curValue = (ValueNode) curNode;
1005 if (curValue.isConstant() || curValue == value || curValue instanceof ParameterNode) {
1006 return curNode;
1007 }
1008 if (curValue instanceof BinaryNode || curValue instanceof UnaryNode) {
1009 curValue.applyInputs(this);
1010 } else {
1011 ok = false;
1012 }
1013 return curNode;
1014 }
1015 }
1016
1017 @FunctionalInterface
1018 protected interface GuardRewirer {
1019 /**
1020 * Called if the condition could be proven to have a constant value ({@code result}) under
1021 * {@code guard}.
1022 *
1023 * @param guard the guard whose result is proven
1024 * @param result the known result of the guard
1025 * @param newInput new input to pi nodes depending on the new guard
1026 * @return whether the transformation could be applied
1027 */
1028 boolean rewire(GuardingNode guard, boolean result, Stamp guardedValueStamp, ValueNode newInput);
1029 }
1030
1031 protected static final class InfoElement {
1032 private final Stamp stamp;
1033 private final GuardingNode guard;
1034 private final ValueNode proxifiedInput;
1035 private final InfoElement parent;
1036
1037 public InfoElement(Stamp stamp, GuardingNode guard, ValueNode proxifiedInput, InfoElement parent) {
1038 this.stamp = stamp;
1039 this.guard = guard;
1040 this.proxifiedInput = proxifiedInput;
1041 this.parent = parent;
1042 }
1043
1044 public InfoElement getParent() {
1045 return parent;
1046 }
1047
1048 public Stamp getStamp() {
1049 return stamp;
1050 }
1051
1052 public GuardingNode getGuard() {
1053 return guard;
1054 }
1055
1056 public ValueNode getProxifiedInput() {
1057 return proxifiedInput;
1058 }
1059
1060 @Override
1061 public String toString() {
1062 return stamp + " -> " + guard;
1063 }
1064 }
1065
1066 @Override
1067 public float codeSizeIncrease() {
1068 return 1.5f;
1069 }
1070 }