1 /*
2 * Copyright (c) 2015, 2016, 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.ArrayList;
27 import java.util.Collections;
28 import java.util.Deque;
29 import java.util.Iterator;
30 import java.util.List;
31 import java.util.function.Function;
32
33 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
34 import org.graalvm.compiler.core.common.cfg.BlockMap;
35 import org.graalvm.compiler.core.common.type.ArithmeticOpTable;
36 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp;
37 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.And;
38 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Or;
39 import org.graalvm.compiler.core.common.type.IntegerStamp;
40 import org.graalvm.compiler.core.common.type.ObjectStamp;
41 import org.graalvm.compiler.core.common.type.Stamp;
42 import org.graalvm.compiler.core.common.type.StampFactory;
43 import org.graalvm.compiler.core.common.type.TypeReference;
44 import org.graalvm.compiler.debug.Debug;
45 import org.graalvm.compiler.debug.DebugCounter;
46 import org.graalvm.compiler.graph.Node;
47 import org.graalvm.compiler.graph.NodeMap;
48 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
49 import org.graalvm.compiler.nodeinfo.InputType;
50 import org.graalvm.compiler.nodes.AbstractBeginNode;
51 import org.graalvm.compiler.nodes.BeginNode;
52 import org.graalvm.compiler.nodes.BinaryOpLogicNode;
53 import org.graalvm.compiler.nodes.ConditionAnchorNode;
54 import org.graalvm.compiler.nodes.ConstantNode;
55 import org.graalvm.compiler.nodes.DeoptimizeNode;
56 import org.graalvm.compiler.nodes.DeoptimizingGuard;
57 import org.graalvm.compiler.nodes.FixedGuardNode;
58 import org.graalvm.compiler.nodes.FixedNode;
59 import org.graalvm.compiler.nodes.GuardNode;
60 import org.graalvm.compiler.nodes.GuardProxyNode;
61 import org.graalvm.compiler.nodes.IfNode;
62 import org.graalvm.compiler.nodes.LogicNode;
63 import org.graalvm.compiler.nodes.LoopExitNode;
64 import org.graalvm.compiler.nodes.ParameterNode;
65 import org.graalvm.compiler.nodes.ShortCircuitOrNode;
66 import org.graalvm.compiler.nodes.StructuredGraph;
67 import org.graalvm.compiler.nodes.UnaryOpLogicNode;
68 import org.graalvm.compiler.nodes.ValueNode;
69 import org.graalvm.compiler.nodes.calc.AndNode;
70 import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode;
71 import org.graalvm.compiler.nodes.calc.BinaryNode;
72 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
73 import org.graalvm.compiler.nodes.calc.ObjectEqualsNode;
74 import org.graalvm.compiler.nodes.calc.PointerEqualsNode;
75 import org.graalvm.compiler.nodes.calc.UnaryNode;
76 import org.graalvm.compiler.nodes.cfg.Block;
77 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
78 import org.graalvm.compiler.nodes.extended.GuardingNode;
79 import org.graalvm.compiler.nodes.extended.IntegerSwitchNode;
80 import org.graalvm.compiler.nodes.extended.LoadHubNode;
81 import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
82 import org.graalvm.compiler.nodes.java.LoadFieldNode;
83 import org.graalvm.compiler.nodes.java.TypeSwitchNode;
84 import org.graalvm.compiler.nodes.spi.NodeWithState;
85 import org.graalvm.compiler.nodes.util.GraphUtil;
86 import org.graalvm.compiler.phases.BasePhase;
87 import org.graalvm.compiler.phases.common.LoweringPhase.Frame;
88 import org.graalvm.compiler.phases.schedule.SchedulePhase;
89 import org.graalvm.compiler.phases.tiers.PhaseContext;
90
91 import jdk.vm.ci.meta.JavaConstant;
92 import jdk.vm.ci.meta.TriState;
93
94 public class DominatorConditionalEliminationPhase extends BasePhase<PhaseContext> {
95
96 private static final DebugCounter counterStampsRegistered = Debug.counter("StampsRegistered");
97 private static final DebugCounter counterStampsFound = Debug.counter("StampsFound");
98 private static final DebugCounter counterIfsKilled = Debug.counter("CE_KilledIfs");
99 private static final DebugCounter counterLFFolded = Debug.counter("ConstantLFFolded");
100 private final boolean fullSchedule;
101
102 public DominatorConditionalEliminationPhase(boolean fullSchedule) {
103 this.fullSchedule = fullSchedule;
104 }
105
106 @Override
107 @SuppressWarnings("try")
108 protected void run(StructuredGraph graph, PhaseContext context) {
109 try (Debug.Scope s = Debug.scope("DominatorConditionalElimination")) {
110 Function<Block, Iterable<? extends Node>> blockToNodes;
111 Function<Node, Block> nodeToBlock;
112 Block startBlock;
113
114 if (fullSchedule) {
115 SchedulePhase schedule = new SchedulePhase(SchedulePhase.SchedulingStrategy.EARLIEST);
116 schedule.apply(graph);
117 ControlFlowGraph cfg = graph.getLastSchedule().getCFG();
118 cfg.computePostdominators();
119 blockToNodes = b -> graph.getLastSchedule().getBlockToNodesMap().get(b);
120 nodeToBlock = n -> graph.getLastSchedule().getNodeToBlockMap().get(n);
121 startBlock = cfg.getStartBlock();
122 } else {
123 ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true);
124 BlockMap<List<FixedNode>> nodes = new BlockMap<>(cfg);
125 for (Block b : cfg.getBlocks()) {
126 ArrayList<FixedNode> curNodes = new ArrayList<>();
127 for (FixedNode node : b.getNodes()) {
128 if (node instanceof AbstractBeginNode || node instanceof FixedGuardNode || node instanceof ConditionAnchorNode || node instanceof IfNode) {
129 curNodes.add(node);
130 }
131 }
132 nodes.put(b, curNodes);
133 }
134 blockToNodes = b -> nodes.get(b);
135 nodeToBlock = n -> cfg.blockFor(n);
136 startBlock = cfg.getStartBlock();
137 }
138 new Instance(graph, blockToNodes, nodeToBlock, context).processBlock(startBlock);
139 }
140 }
141
142 public static class Instance {
143 protected NodeMap<Info> map;
144 protected Deque<LoopExitNode> loopExits;
145 protected final Function<Block, Iterable<? extends Node>> blockToNodes;
146 protected final Function<Node, Block> nodeToBlock;
147 protected final CanonicalizerTool tool;
148 /**
149 * Tests which may be eliminated because post dominating tests to prove a broader condition.
150 */
151 private Deque<PendingTest> pendingTests;
152
153 public Instance(StructuredGraph graph, Function<Block, Iterable<? extends Node>> blockToNodes,
154 Function<Node, Block> nodeToBlock, PhaseContext context) {
155 map = graph.createNodeMap();
156 loopExits = new ArrayDeque<>();
157 this.blockToNodes = blockToNodes;
158 this.nodeToBlock = nodeToBlock;
159 pendingTests = new ArrayDeque<>();
160 tool = GraphUtil.getDefaultSimplifier(context.getMetaAccess(), context.getConstantReflection(), context.getConstantFieldProvider(), false, graph.getAssumptions(), context.getLowerer());
161 }
162
163 public void processBlock(Block startBlock) {
164 LoweringPhase.processBlock(new InstanceFrame(startBlock, null));
165 }
166
167 public class InstanceFrame extends LoweringPhase.Frame<InstanceFrame> {
168 protected List<Runnable> undoOperations = new ArrayList<>();
169
170 public InstanceFrame(Block block, InstanceFrame parent) {
171 super(block, parent);
172 }
173
174 @Override
175 public Frame<?> enter(Block b) {
176 return new InstanceFrame(b, this);
177 }
178
179 @Override
180 public void postprocess() {
181 Debug.log("[Post Processing block %s]", block);
182 undoOperations.forEach(x -> x.run());
183 }
184
185 protected void processConditionAnchor(ConditionAnchorNode node) {
186 tryProveCondition(node.condition(), (guard, result) -> {
187 if (result != node.isNegated()) {
188 node.replaceAtUsages(guard);
189 GraphUtil.unlinkFixedNode(node);
190 GraphUtil.killWithUnusedFloatingInputs(node);
191 } else {
192 ValueAnchorNode valueAnchor = node.graph().add(new ValueAnchorNode(null));
193 node.replaceAtUsages(valueAnchor);
194 node.graph().replaceFixedWithFixed(node, valueAnchor);
195 }
196 return true;
197 });
198 }
199
200 protected void processGuard(GuardNode node) {
201 if (!tryProveGuardCondition(node, node.getCondition(), (guard, result) -> {
202 if (result != node.isNegated()) {
203 node.replaceAndDelete(guard);
204 } else {
205 DeoptimizeNode deopt = node.graph().add(new DeoptimizeNode(node.getAction(), node.getReason(), node.getSpeculation()));
206 AbstractBeginNode beginNode = (AbstractBeginNode) node.getAnchor();
207 FixedNode next = beginNode.next();
208 beginNode.setNext(deopt);
209 GraphUtil.killCFG(next);
210 }
211 return true;
212 })) {
213 registerNewCondition(node.getCondition(), node.isNegated(), node);
214 }
215 }
216
217 protected void processFixedGuard(FixedGuardNode node) {
218 if (!tryProveGuardCondition(node, node.condition(), (guard, result) -> {
219 if (result != node.isNegated()) {
220 node.replaceAtUsages(guard);
221 GraphUtil.unlinkFixedNode(node);
222 GraphUtil.killWithUnusedFloatingInputs(node);
223 } else {
224 DeoptimizeNode deopt = node.graph().add(new DeoptimizeNode(node.getAction(), node.getReason(), node.getSpeculation()));
225 deopt.setStateBefore(node.stateBefore());
226 node.replaceAtPredecessor(deopt);
227 GraphUtil.killCFG(node);
228 }
229 Debug.log("Kill fixed guard guard");
230 return true;
231 })) {
232 registerNewCondition(node.condition(), node.isNegated(), node);
233 }
234 }
235
236 protected void processIf(IfNode node) {
237 tryProveCondition(node.condition(), (guard, result) -> {
238 AbstractBeginNode survivingSuccessor = node.getSuccessor(result);
239 survivingSuccessor.replaceAtUsages(InputType.Guard, guard);
240 survivingSuccessor.replaceAtPredecessor(null);
241 node.replaceAtPredecessor(survivingSuccessor);
242 GraphUtil.killCFG(node);
243 if (survivingSuccessor instanceof BeginNode) {
244 undoOperations.add(() -> {
245 if (survivingSuccessor.isAlive()) {
246 ((BeginNode) survivingSuccessor).trySimplify();
247 }
248 });
249 }
250 Debug.log("Kill if");
251 counterIfsKilled.increment();
252 return true;
253 });
254 }
255
256 @Override
257 public void preprocess() {
258 Debug.log("[Pre Processing block %s]", block);
259 AbstractBeginNode beginNode = block.getBeginNode();
260 if (beginNode instanceof LoopExitNode && beginNode.isAlive()) {
261 LoopExitNode loopExitNode = (LoopExitNode) beginNode;
262 Instance.this.loopExits.push(loopExitNode);
263 undoOperations.add(() -> loopExits.pop());
264 } else if (block.getDominator() != null && (block.getDominator().getLoopDepth() > block.getLoopDepth() ||
265 (block.getDominator().getLoopDepth() == block.getLoopDepth() && block.getDominator().getLoop() != block.getLoop()))) {
266 // We are exiting the loop, but there is not a single loop exit block along our
267 // dominator tree (e.g., we are a merge of two loop exits).
268 final NodeMap<Info> oldMap = map;
269 final Deque<LoopExitNode> oldLoopExits = loopExits;
270 map = map.graph().createNodeMap();
271 loopExits = new ArrayDeque<>();
272 undoOperations.add(() -> {
273 map = oldMap;
274 loopExits = oldLoopExits;
275 });
276 }
277
278 // For now conservatively collect guards only within the same block.
279 pendingTests.clear();
280 for (Node n : blockToNodes.apply(block)) {
281 if (n.isAlive()) {
282 processNode(n);
283 }
284 }
285 }
286
287 protected void processNode(Node node) {
288 if (node instanceof NodeWithState && !(node instanceof GuardingNode)) {
289 pendingTests.clear();
290 }
291 if (node instanceof AbstractBeginNode) {
292 processAbstractBegin((AbstractBeginNode) node);
293 } else if (node instanceof FixedGuardNode) {
294 processFixedGuard((FixedGuardNode) node);
295 } else if (node instanceof GuardNode) {
296 processGuard((GuardNode) node);
297 } else if (node instanceof ConditionAnchorNode) {
298 processConditionAnchor((ConditionAnchorNode) node);
299 } else if (node instanceof IfNode) {
300 processIf((IfNode) node);
301 } else {
302 return;
303 }
304 }
305
306 protected void registerNewCondition(LogicNode condition, boolean negated, ValueNode guard) {
307 if (!negated && condition instanceof PointerEqualsNode) {
308 PointerEqualsNode pe = (PointerEqualsNode) condition;
309 ValueNode x = pe.getX();
310 ValueNode y = pe.getY();
311 if (y.isConstant()) {
312 JavaConstant constant = y.asJavaConstant();
313 Stamp succeeding = pe.getSucceedingStampForX(negated);
314 if (succeeding == null && pe instanceof ObjectEqualsNode && guard instanceof FixedGuardNode) {
315 succeeding = y.stamp();
316 }
317 if (succeeding != null) {
318 if (y.stamp() instanceof ObjectStamp) {
319 GuardedConstantStamp cos = new GuardedConstantStamp(constant, (ObjectStamp) succeeding);
320 registerNewStamp(x, cos, guard);
321 return;
322 }
323 }
324 }
325 }
326 if (condition instanceof UnaryOpLogicNode) {
327 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) condition;
328 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(negated);
329 registerNewStamp(unaryLogicNode.getValue(), newStamp, guard);
330 } else if (condition instanceof BinaryOpLogicNode) {
331 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) condition;
332 ValueNode x = binaryOpLogicNode.getX();
333 if (!x.isConstant()) {
334 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(negated);
335 registerNewStamp(x, newStampX, guard);
336 }
337
338 ValueNode y = binaryOpLogicNode.getY();
339 if (!y.isConstant()) {
340 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(negated);
341 registerNewStamp(y, newStampY, guard);
342 }
343 if (condition instanceof IntegerEqualsNode && guard instanceof DeoptimizingGuard && !negated) {
344 if (y.isConstant() && x instanceof AndNode) {
345 AndNode and = (AndNode) x;
346 if (and.getY() == y) {
347 /*
348 * This 'and' proves something about some of the bits in and.getX().
349 * It's equivalent to or'ing in the mask value since those values
350 * are known to be set.
351 */
352 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp()).getOr();
353 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(and.getX().stamp(), y.stamp());
354 registerNewStamp(and.getX(), newStampX, guard);
355 }
356 }
357 }
358 }
359 if (guard instanceof DeoptimizingGuard) {
360 pendingTests.push(new PendingTest(condition, (DeoptimizingGuard) guard));
361 }
362 registerCondition(condition, negated, guard);
363 }
364
365 @SuppressWarnings("try")
366 protected Pair<InfoElement, Stamp> foldFromConstLoadField(LoadFieldNode loadFieldNode, InfoElementProvider info) {
367 ValueNode object = loadFieldNode.object();
368 if (!loadFieldNode.field().isStatic()) {
369 // look if we got stamp info for the object and return the constant stamp
370 Pair<InfoElement, Stamp> pair = getConstantObjectStamp(info, object);
371 if (pair == null) {
372 pair = recursiveFoldStamp(object, info);
373 }
374 if (pair != null) {
375 Stamp s = pair.second;
376 if (s instanceof GuardedConstantStamp) {
377 ConstantNode c = tryFoldFromLoadField(loadFieldNode, pair.second);
378 if (c != null) {
379 counterLFFolded.increment();
380 if (c.stamp() instanceof ObjectStamp) {
381 GuardedConstantStamp cos = new GuardedConstantStamp(c.asJavaConstant(), (ObjectStamp) c.stamp());
382 return new Pair<>(pair.first, cos);
383 }
384 return new Pair<>(pair.first, c.stamp());
385 }
386 }
387 }
388 }
389 return null;
390 }
391
392 private ConstantNode tryFoldFromLoadField(LoadFieldNode lf, Stamp x) {
393 GuardedConstantStamp cos = (GuardedConstantStamp) x;
394 return lf.asConstant(tool, cos.objectConstant);
395 }
396
397 private Pair<InfoElement, Stamp> getConstantObjectStamp(InfoElementProvider infos, ValueNode n) {
398 for (InfoElement infoElement : infos.getInfoElements(n)) {
399 Stamp s = infoElement.getStamp();
400 if (s instanceof GuardedConstantStamp) {
401 return new Pair<>(infoElement, s);
402 }
403 }
404 return null;
405 }
406
407 Pair<InfoElement, Stamp> recursiveFoldStamp(Node node, InfoElementProvider info) {
408 if (node instanceof LoadFieldNode) {
409 Pair<InfoElement, Stamp> pair = foldFromConstLoadField((LoadFieldNode) node, info);
410 if (pair != null) {
411 return pair;
412 }
413 }
414 if (node instanceof UnaryNode) {
415 UnaryNode unary = (UnaryNode) node;
416 ValueNode value = unary.getValue();
417 for (InfoElement infoElement : info.getInfoElements(value)) {
418 Stamp result = unary.foldStamp(infoElement.getStamp());
419 if (result != null) {
420 return new Pair<>(infoElement, result);
421 }
422 }
423 Pair<InfoElement, Stamp> foldResult = recursiveFoldStamp(value, info);
424 if (foldResult != null) {
425 Stamp result = unary.foldStamp(foldResult.second);
426 if (result != null) {
427 return new Pair<>(foldResult.first, result);
428 }
429 }
430 } else if (node instanceof BinaryNode) {
431 BinaryNode binary = (BinaryNode) node;
432 ValueNode y = binary.getY();
433 ValueNode x = binary.getX();
434 if (y.isConstant()) {
435 for (InfoElement infoElement : info.getInfoElements(x)) {
436 Stamp result = binary.foldStamp(infoElement.stamp, y.stamp());
437 if (result != null) {
438 return new Pair<>(infoElement, result);
439 }
440 }
441 Pair<InfoElement, Stamp> foldResult = recursiveFoldStamp(x, info);
442 if (foldResult != null) {
443 Stamp result = binary.foldStamp(foldResult.second, y.stamp());
444 if (result != null) {
445 return new Pair<>(foldResult.first, result);
446 }
447 }
448 } else if (x instanceof LoadFieldNode || y instanceof LoadFieldNode) {
449 boolean useX = x instanceof LoadFieldNode;
450 Pair<InfoElement, Stamp> foldResult = recursiveFoldStamp(useX ? x : y, info);
451 if (foldResult != null) {
452 Stamp result = binary.foldStamp(useX ? foldResult.second : x.stamp(), useX ? y.stamp() : foldResult.second);
453 if (result != null) {
454 return new Pair<>(foldResult.first, result);
455 }
456 }
457 }
458 }
459 return null;
460 }
461
462 /**
463 * Recursively try to fold stamps within this expression using information from
464 * {@link #getInfoElements(ValueNode)}. It's only safe to use constants and one
465 * {@link InfoElement} otherwise more than one guard would be required.
466 *
467 * @param node
468 * @return the pair of the @{link InfoElement} used and the stamp produced for the whole
469 * expression
470 */
471 Pair<InfoElement, Stamp> recursiveFoldStampFromInfo(Node node) {
472 return recursiveFoldStamp(node, (value) -> getInfoElements(value));
473 }
474
475 /**
476 * Recursively try to fold stamps within this expression using {@code newStamp} if the
477 * node {@code original} is encountered in the expression. It's only safe to use
478 * constants and the passed in stamp otherwise more than one guard would be required.
479 *
480 * @param node
481 * @param original
482 * @param newStamp
483 * @return the improved stamp or null is nothing could be done
484 */
485 @SuppressWarnings("unchecked")
486 Stamp recursiveFoldStamp(Node node, ValueNode original, Stamp newStamp) {
487 Debug.log("Recursively fold stamp for node %s original %s stamp %s", node, original, newStamp);
488 InfoElement element = new InfoElement(newStamp, original);
489 Pair<InfoElement, Stamp> result = recursiveFoldStamp(node, (value) -> value == original ? Collections.singleton(element) : Collections.EMPTY_LIST);
490 if (result != null) {
491 return result.second;
492 }
493 return null;
494 }
495
496 protected boolean foldPendingTest(DeoptimizingGuard thisGuard, ValueNode original, Stamp newStamp, GuardRewirer rewireGuardFunction) {
497 for (PendingTest pending : pendingTests) {
498 TriState result = TriState.UNKNOWN;
499 if (pending.condition instanceof UnaryOpLogicNode) {
500 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) pending.condition;
501 if (unaryLogicNode.getValue() == original) {
502 result = unaryLogicNode.tryFold(newStamp);
503 }
504 if (!result.isKnown()) {
505 Stamp foldResult = recursiveFoldStamp(unaryLogicNode.getValue(), original, newStamp);
506 if (foldResult != null) {
507 result = unaryLogicNode.tryFold(foldResult);
508 }
509 }
510 } else if (pending.condition instanceof BinaryOpLogicNode) {
511 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) pending.condition;
512 ValueNode x = binaryOpLogicNode.getX();
513 ValueNode y = binaryOpLogicNode.getY();
514 if (binaryOpLogicNode.getX() == original) {
515 result = binaryOpLogicNode.tryFold(newStamp, binaryOpLogicNode.getY().stamp());
516 } else if (binaryOpLogicNode instanceof IntegerEqualsNode && y.isConstant() && x instanceof AndNode) {
517 AndNode and = (AndNode) x;
518 if (and.getY() == y && and.getX() == original) {
519 BinaryOp<And> andOp = ArithmeticOpTable.forStamp(newStamp).getAnd();
520 result = binaryOpLogicNode.tryFold(andOp.foldStamp(newStamp, y.stamp()), y.stamp());
521 }
522 }
523 if (!result.isKnown() && y.isConstant()) {
524 Stamp foldResult = recursiveFoldStamp(x, original, newStamp);
525 if (foldResult != null) {
526 result = binaryOpLogicNode.tryFold(foldResult, y.stamp());
527 }
528 }
529 }
530 if (result.isKnown()) {
531 /*
532 * The test case be folded using the information available but the test can
533 * only be moved up if we're sure there's no schedule dependence. For now
534 * limit it to the original node and constants.
535 */
536 InputFilter v = new InputFilter(original);
537 thisGuard.getCondition().applyInputs(v);
538 if (v.ok && foldGuard(thisGuard, pending.guard, rewireGuardFunction)) {
539 return true;
540 }
541 }
542 }
543 return false;
544 }
545
546 protected boolean foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, GuardRewirer rewireGuardFunction) {
547 if (otherGuard.getAction() == thisGuard.getAction() && otherGuard.getReason() == thisGuard.getReason() && otherGuard.getSpeculation() == thisGuard.getSpeculation()) {
548 LogicNode condition = (LogicNode) thisGuard.getCondition().copyWithInputs();
549 GuardRewirer rewirer = (guard, result) -> {
550 if (rewireGuardFunction.rewire(guard, result)) {
551 otherGuard.setCondition(condition, thisGuard.isNegated());
552 return true;
553 }
554 condition.safeDelete();
555 return false;
556 };
557 // Move the later test up
558 return rewireGuards(otherGuard.asNode(), !thisGuard.isNegated(), rewirer);
559 }
560 return false;
561 }
562
563 protected void registerCondition(LogicNode condition, boolean negated, ValueNode guard) {
564 registerNewStamp(condition, negated ? StampFactory.contradiction() : StampFactory.tautology(), guard);
565 }
566
567 protected Iterable<InfoElement> getInfoElements(ValueNode proxiedValue) {
568 ValueNode value = GraphUtil.unproxify(proxiedValue);
569 if (value == null) {
570 return Collections.emptyList();
571 }
572 Info info = map.get(value);
573 if (info == null) {
574 return Collections.emptyList();
575 } else {
576 return info.getElements();
577 }
578 }
579
580 protected boolean rewireGuards(ValueNode guard, boolean result, GuardRewirer rewireGuardFunction) {
581 assert guard instanceof GuardingNode;
582 counterStampsFound.increment();
583 ValueNode proxiedGuard = proxyGuard(guard);
584 return rewireGuardFunction.rewire(proxiedGuard, result);
585 }
586
587 protected ValueNode proxyGuard(ValueNode guard) {
588 ValueNode proxiedGuard = guard;
589 if (!Instance.this.loopExits.isEmpty()) {
590 while (proxiedGuard instanceof GuardProxyNode) {
591 proxiedGuard = ((GuardProxyNode) proxiedGuard).value();
592 }
593 Block guardBlock = nodeToBlock.apply(proxiedGuard);
594 assert guardBlock != null;
595 for (Iterator<LoopExitNode> iter = loopExits.descendingIterator(); iter.hasNext();) {
596 LoopExitNode loopExitNode = iter.next();
597 Block loopExitBlock = nodeToBlock.apply(loopExitNode);
598 if (guardBlock != loopExitBlock && AbstractControlFlowGraph.dominates(guardBlock, loopExitBlock)) {
599 Block loopBeginBlock = nodeToBlock.apply(loopExitNode.loopBegin());
600 if (!AbstractControlFlowGraph.dominates(guardBlock, loopBeginBlock) || guardBlock == loopBeginBlock) {
601 proxiedGuard = proxiedGuard.graph().unique(new GuardProxyNode((GuardingNode) proxiedGuard, loopExitNode));
602 }
603 }
604 }
605 }
606 return proxiedGuard;
607 }
608
609 protected boolean tryProveCondition(LogicNode node, GuardRewirer rewireGuardFunction) {
610 return tryProveGuardCondition(null, node, rewireGuardFunction);
611 }
612
613 protected boolean tryProveGuardCondition(DeoptimizingGuard thisGuard, LogicNode node, GuardRewirer rewireGuardFunction) {
614 for (InfoElement infoElement : getInfoElements(node)) {
615 Stamp stamp = infoElement.getStamp();
616 JavaConstant constant = (JavaConstant) stamp.asConstant();
617 if (constant != null) {
618 return rewireGuards(infoElement.getGuard(), constant.asBoolean(), rewireGuardFunction);
619 }
620 }
621 if (node instanceof UnaryOpLogicNode) {
622 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) node;
623 ValueNode value = unaryLogicNode.getValue();
624 for (InfoElement infoElement : getInfoElements(value)) {
625 Stamp stamp = infoElement.getStamp();
626 TriState result = unaryLogicNode.tryFold(stamp);
627 if (result.isKnown()) {
628 return rewireGuards(infoElement.getGuard(), result.toBoolean(), rewireGuardFunction);
629 }
630 }
631 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(value);
632 if (foldResult != null) {
633 TriState result = unaryLogicNode.tryFold(foldResult.second);
634 if (result.isKnown()) {
635 return rewireGuards(foldResult.first.getGuard(), result.toBoolean(), rewireGuardFunction);
636 }
637 }
638 if (thisGuard != null) {
639 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(thisGuard.isNegated());
640 if (newStamp != null && foldPendingTest(thisGuard, value, newStamp, rewireGuardFunction)) {
641 return true;
642 }
643
644 }
645 } else if (node instanceof BinaryOpLogicNode) {
646 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) node;
647 for (InfoElement infoElement : getInfoElements(binaryOpLogicNode)) {
648 if (infoElement.getStamp().equals(StampFactory.contradiction())) {
649 return rewireGuards(infoElement.getGuard(), false, rewireGuardFunction);
650 } else if (infoElement.getStamp().equals(StampFactory.tautology())) {
651 return rewireGuards(infoElement.getGuard(), true, rewireGuardFunction);
652 }
653 }
654
655 ValueNode x = binaryOpLogicNode.getX();
656 ValueNode y = binaryOpLogicNode.getY();
657 for (InfoElement infoElement : getInfoElements(x)) {
658 TriState result = binaryOpLogicNode.tryFold(infoElement.getStamp(), y.stamp());
659 if (result.isKnown()) {
660 return rewireGuards(infoElement.getGuard(), result.toBoolean(), rewireGuardFunction);
661 }
662 }
663
664 if (y.isConstant()) {
665 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(x);
666 if (foldResult != null) {
667 TriState result = binaryOpLogicNode.tryFold(foldResult.second, y.stamp());
668 if (result.isKnown()) {
669 return rewireGuards(foldResult.first.getGuard(), result.toBoolean(), rewireGuardFunction);
670 }
671 }
672 } else {
673 for (InfoElement infoElement : getInfoElements(y)) {
674 TriState result = binaryOpLogicNode.tryFold(x.stamp(), infoElement.getStamp());
675 if (result.isKnown()) {
676 return rewireGuards(infoElement.getGuard(), result.toBoolean(), rewireGuardFunction);
677 }
678 }
679 }
680
681 /*
682 * For complex expressions involving constants, see if it's possible to fold the
683 * tests by using stamps one level up in the expression. For instance, (x + n <
684 * y) might fold if something is known about x and all other values are
685 * constants. The reason for the constant restriction is that if more than 1
686 * real value is involved the code might need to adopt multiple guards to have
687 * proper dependences.
688 */
689 if (x instanceof BinaryArithmeticNode<?> && y.isConstant()) {
690 BinaryArithmeticNode<?> binary = (BinaryArithmeticNode<?>) x;
691 if (binary.getY().isConstant()) {
692 for (InfoElement infoElement : getInfoElements(binary.getX())) {
693 Stamp newStampX = binary.foldStamp(infoElement.getStamp(), binary.getY().stamp());
694 TriState result = binaryOpLogicNode.tryFold(newStampX, y.stamp());
695 if (result.isKnown()) {
696 return rewireGuards(infoElement.getGuard(), result.toBoolean(), rewireGuardFunction);
697 }
698 }
699 }
700 }
701 if (thisGuard != null && binaryOpLogicNode instanceof IntegerEqualsNode && !thisGuard.isNegated()) {
702 if (y.isConstant() && x instanceof AndNode) {
703 AndNode and = (AndNode) x;
704 if (and.getY() == y) {
705 /*
706 * This 'and' proves something about some of the bits in and.getX().
707 * It's equivalent to or'ing in the mask value since those values
708 * are known to be set.
709 */
710 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp()).getOr();
711 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(and.getX().stamp(), y.stamp());
712 if (foldPendingTest(thisGuard, and.getX(), newStampX, rewireGuardFunction)) {
713 return true;
714 }
715 }
716 }
717 }
718 if (thisGuard != null) {
719 if (!x.isConstant()) {
720 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(thisGuard.isNegated());
721 if (newStampX != null && foldPendingTest(thisGuard, x, newStampX, rewireGuardFunction)) {
722 return true;
723 }
724 }
725 if (!y.isConstant()) {
726 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(thisGuard.isNegated());
727 if (newStampY != null && foldPendingTest(thisGuard, y, newStampY, rewireGuardFunction)) {
728 return true;
729 }
730 }
731 }
732 } else if (node instanceof ShortCircuitOrNode) {
733 final ShortCircuitOrNode shortCircuitOrNode = (ShortCircuitOrNode) node;
734 if (Instance.this.loopExits.isEmpty()) {
735 return tryProveCondition(shortCircuitOrNode.getX(), (guard, result) -> {
736 if (result == !shortCircuitOrNode.isXNegated()) {
737 return rewireGuards(guard, true, rewireGuardFunction);
738 } else {
739 return tryProveCondition(shortCircuitOrNode.getY(), (innerGuard, innerResult) -> {
740 if (innerGuard == guard) {
741 return rewireGuards(guard, innerResult ^ shortCircuitOrNode.isYNegated(), rewireGuardFunction);
742 }
743 return false;
744 });
745 }
746 });
747 }
748 }
749
750 return false;
751 }
752
753 protected void registerNewStamp(ValueNode proxiedValue, Stamp newStamp, ValueNode guard) {
754 assert proxiedValue != null;
755 assert guard != null;
756 if (newStamp != null) {
757 ValueNode value = GraphUtil.unproxify(proxiedValue);
758 Info info = map.get(value);
759 if (info == null) {
760 info = new Info();
761 map.set(value, info);
762 }
763 counterStampsRegistered.increment();
764 final Info finalInfo = info;
765 Debug.log("\t Saving stamp for node %s stamp %s guarded by %s", value, newStamp, guard == null ? "null" : guard);
766 finalInfo.pushElement(new InfoElement(newStamp, guard));
767 undoOperations.add(() -> finalInfo.popElement());
768 }
769 }
770
771 protected void processAbstractBegin(AbstractBeginNode beginNode) {
772 Node predecessor = beginNode.predecessor();
773 if (predecessor instanceof IfNode) {
774 IfNode ifNode = (IfNode) predecessor;
775 boolean negated = (ifNode.falseSuccessor() == beginNode);
776 LogicNode condition = ifNode.condition();
777 registerNewCondition(condition, negated, beginNode);
778 } else if (predecessor instanceof TypeSwitchNode) {
779 TypeSwitchNode typeSwitch = (TypeSwitchNode) predecessor;
780 processTypeSwitch(beginNode, predecessor, typeSwitch);
781 } else if (predecessor instanceof IntegerSwitchNode) {
782 IntegerSwitchNode integerSwitchNode = (IntegerSwitchNode) predecessor;
783 processIntegerSwitch(beginNode, predecessor, integerSwitchNode);
784 }
785 }
786
787 protected void processIntegerSwitch(AbstractBeginNode beginNode, Node predecessor, IntegerSwitchNode integerSwitchNode) {
788 Stamp stamp = null;
789 for (int i = 0; i < integerSwitchNode.keyCount(); i++) {
790 if (integerSwitchNode.keySuccessor(i) == predecessor) {
791 if (stamp == null) {
792 stamp = StampFactory.forConstant(integerSwitchNode.keyAt(i));
793 } else {
794 stamp = stamp.meet(StampFactory.forConstant(integerSwitchNode.keyAt(i)));
795 }
796 }
797 }
798
799 if (stamp != null) {
800 registerNewStamp(integerSwitchNode.value(), stamp, beginNode);
801 }
802 }
803
804 protected void processTypeSwitch(AbstractBeginNode beginNode, Node predecessor, TypeSwitchNode typeSwitch) {
805 ValueNode hub = typeSwitch.value();
806 if (hub instanceof LoadHubNode) {
807 LoadHubNode loadHub = (LoadHubNode) hub;
808 Stamp stamp = null;
809 for (int i = 0; i < typeSwitch.keyCount(); i++) {
810 if (typeSwitch.keySuccessor(i) == predecessor) {
811 if (stamp == null) {
812 stamp = StampFactory.objectNonNull(TypeReference.createExactTrusted(typeSwitch.typeAt(i)));
813 } else {
814 stamp = stamp.meet(StampFactory.objectNonNull(TypeReference.createExactTrusted(typeSwitch.typeAt(i))));
815 }
816 }
817 }
818 if (stamp != null) {
819 registerNewStamp(loadHub.getValue(), stamp, beginNode);
820 }
821 }
822 }
823 }
824 }
825
826 protected static class Pair<F, S> {
827 public final F first;
828 public final S second;
829
830 Pair(F first, S second) {
831 this.first = first;
832 this.second = second;
833 }
834
835 @Override
836 public int hashCode() {
837 return first.hashCode() * 31 ^ second.hashCode();
838 }
839
840 @Override
841 public boolean equals(Object obj) {
842 if (obj instanceof Pair<?, ?>) {
843 Pair<?, ?> other = (Pair<?, ?>) obj;
844 return this.first.equals(other.first) && this.second.equals(other.second);
845 }
846 return false;
847 }
848 }
849
850 @FunctionalInterface
851 protected interface InfoElementProvider {
852 Iterable<InfoElement> getInfoElements(ValueNode value);
853 }
854
855 /**
856 * Checks for safe nodes when moving pending tests up.
857 */
858 static class InputFilter extends Node.EdgeVisitor {
859 boolean ok;
860 private ValueNode value;
861
862 InputFilter(ValueNode value) {
863 this.value = value;
864 this.ok = true;
865 }
866
867 @Override
868 public Node apply(Node node, Node curNode) {
869 if (!(curNode instanceof ValueNode)) {
870 ok = false;
871 return curNode;
872 }
873 ValueNode curValue = (ValueNode) curNode;
874 if (curValue.isConstant() || curValue == value || curValue instanceof ParameterNode) {
875 return curNode;
876 }
877 if (curValue instanceof BinaryNode || curValue instanceof UnaryNode) {
878 curValue.applyInputs(this);
879 } else {
880 ok = false;
881 }
882 return curNode;
883 }
884 }
885
886 @FunctionalInterface
887 protected interface GuardRewirer {
888 /**
889 * Called if the condition could be proven to have a constant value ({@code result}) under
890 * {@code guard}.
891 *
892 * Return whether a transformation could be applied.
893 */
894 boolean rewire(ValueNode guard, boolean result);
895 }
896
897 protected static class PendingTest {
898 private final LogicNode condition;
899 private final DeoptimizingGuard guard;
900
901 public PendingTest(LogicNode condition, DeoptimizingGuard guard) {
902 this.condition = condition;
903 this.guard = guard;
904 }
905 }
906
907 protected static final class InfoElement {
908 private final Stamp stamp;
909 private final ValueNode guard;
910
911 public InfoElement(Stamp stamp, ValueNode guard) {
912 this.stamp = stamp;
913 this.guard = guard;
914 }
915
916 public Stamp getStamp() {
917 return stamp;
918 }
919
920 public ValueNode getGuard() {
921 return guard;
922 }
923
924 @Override
925 public String toString() {
926 return stamp + " -> " + guard;
927 }
928 }
929
930 protected static final class Info {
931 private final ArrayList<InfoElement> infos;
932
933 public Info() {
934 infos = new ArrayList<>();
935 }
936
937 public Iterable<InfoElement> getElements() {
938 return infos;
939 }
940
941 public void pushElement(InfoElement element) {
942 Debug.log(Debug.VERBOSE_LOG_LEVEL, "Pushing an info element:%s", element);
943 infos.add(element);
944 }
945
946 public void popElement() {
947 infos.remove(infos.size() - 1);
948 }
949 }
950
951 private static class GuardedConstantStamp extends ObjectStamp {
952 private final JavaConstant objectConstant;
953
954 GuardedConstantStamp(JavaConstant objectConstant, ObjectStamp succeedingStamp) {
955 super(succeedingStamp.type(), succeedingStamp.isExactType(), succeedingStamp.nonNull(), succeedingStamp.alwaysNull());
956 this.objectConstant = objectConstant;
957 }
958
959 }
960
961 @Override
962 public float codeSizeIncrease() {
963 return 1.5f;
964 }
965 }