Mercurial > hg > truffle
view graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java @ 7326:6939a5af19d5
Be sure to remove framestate of merge when removing empty diamond shape
author | Gilles Duboscq <duboscq@ssw.jku.at> |
---|---|
date | Thu, 10 Jan 2013 12:03:14 +0100 |
parents | a64cf8797166 |
children | f04a5e46cdd2 |
line wrap: on
line source
/* * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package com.oracle.graal.nodes; import java.util.*; import com.oracle.graal.api.meta.*; import com.oracle.graal.graph.*; import com.oracle.graal.graph.iterators.*; import com.oracle.graal.nodes.PhiNode.PhiType; import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.type.*; import com.oracle.graal.nodes.util.*; /** * The {@code IfNode} represents a branch that can go one of two directions depending on the outcome of a * comparison. */ public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable, Negatable { private final long leafGraphId; @Successor private BeginNode trueSuccessor; @Successor private BeginNode falseSuccessor; @Input private BooleanNode condition; private double takenProbability; public BooleanNode condition() { return condition; } public void setCondition(BooleanNode x) { updateUsages(condition, x); condition = x; } public IfNode(BooleanNode condition, FixedNode trueSuccessor, FixedNode falseSuccessor, double takenProbability, long leafGraphId) { this(condition, BeginNode.begin(trueSuccessor), BeginNode.begin(falseSuccessor), takenProbability, leafGraphId); } public IfNode(BooleanNode condition, BeginNode trueSuccessor, BeginNode falseSuccessor, double takenProbability, long leafGraphId) { super(StampFactory.forVoid()); this.condition = condition; this.falseSuccessor = falseSuccessor; this.takenProbability = takenProbability; this.leafGraphId = leafGraphId; this.trueSuccessor = trueSuccessor; } public long leafGraphId() { return leafGraphId; } /** * Gets the true successor. * * @return the true successor */ public BeginNode trueSuccessor() { return trueSuccessor; } /** * Gets the false successor. * * @return the false successor */ public BeginNode falseSuccessor() { return falseSuccessor; } public void setTrueSuccessor(BeginNode node) { updatePredecessor(trueSuccessor, node); trueSuccessor = node; } public void setFalseSuccessor(BeginNode node) { updatePredecessor(falseSuccessor, node); falseSuccessor = node; } /** * Gets the node corresponding to the specified outcome of the branch. * * @param istrue {@code true} if the true successor is requested, {@code false} otherwise * @return the corresponding successor */ public BeginNode successor(boolean istrue) { return istrue ? trueSuccessor : falseSuccessor; } @Override public Negatable negate() { BeginNode trueSucc = trueSuccessor(); BeginNode falseSucc = falseSuccessor(); setTrueSuccessor(null); setFalseSuccessor(null); setTrueSuccessor(falseSucc); setFalseSuccessor(trueSucc); takenProbability = 1 - takenProbability; return this; } @Override public double probability(BeginNode successor) { return successor == trueSuccessor ? takenProbability : 1 - takenProbability; } @Override public void generate(LIRGeneratorTool gen) { gen.emitIf(this); } @Override public boolean verify() { assertTrue(condition() != null, "missing condition"); assertTrue(trueSuccessor() != null, "missing trueSuccessor"); assertTrue(falseSuccessor() != null, "missing falseSuccessor"); return super.verify(); } @Override public void simplify(SimplifierTool tool) { if (condition() instanceof ConstantNode) { ConstantNode c = (ConstantNode) condition(); if (c.asConstant().asBoolean()) { tool.deleteBranch(falseSuccessor()); tool.addToWorkList(trueSuccessor()); ((StructuredGraph) graph()).removeSplit(this, trueSuccessor()); } else { tool.deleteBranch(trueSuccessor()); tool.addToWorkList(falseSuccessor()); ((StructuredGraph) graph()).removeSplit(this, falseSuccessor()); } } else if (trueSuccessor().guards().isEmpty() && falseSuccessor().guards().isEmpty()) { if (removeOrMaterializeIf(tool)) { return; } else if (removeIntermediateMaterialization(tool)) { return; } } } /** * Tries to remove an empty if construct or replace an if construct with a materialization. * * @return true if a transformation was made, false otherwise */ private boolean removeOrMaterializeIf(SimplifierTool tool) { if (trueSuccessor().next() instanceof EndNode && falseSuccessor().next() instanceof EndNode) { EndNode trueEnd = (EndNode) trueSuccessor().next(); EndNode falseEnd = (EndNode) falseSuccessor().next(); MergeNode merge = trueEnd.merge(); if (merge == falseEnd.merge() && merge.forwardEndCount() == 2 && trueSuccessor().anchored().isEmpty() && falseSuccessor().anchored().isEmpty()) { Iterator<PhiNode> phis = merge.phis().iterator(); if (!phis.hasNext()) { // empty if construct with no phis: remove it removeEmptyIf(tool); return false; } else { PhiNode singlePhi = phis.next(); if (!phis.hasNext()) { // one phi at the merge of an otherwise empty if construct: try to convert into a MaterializeNode boolean inverted = trueEnd == merge.forwardEndAt(1); ValueNode trueValue = singlePhi.valueAt(inverted ? 1 : 0); ValueNode falseValue = singlePhi.valueAt(inverted ? 0 : 1); if (trueValue.kind() != falseValue.kind()) { return false; } if (trueValue.kind() != Kind.Int && trueValue.kind() != Kind.Long) { return false; } if (trueValue.isConstant() && falseValue.isConstant()) { MaterializeNode materialize = MaterializeNode.create(condition(), trueValue, falseValue); ((StructuredGraph) graph()).replaceFloating(singlePhi, materialize); removeEmptyIf(tool); return true; } } } } } return false; } /** * Tries to connect code that initializes a variable directly with the successors of an if construct * that switches on the variable. For example, the pseudo code below: * * <pre> * contains(list, e, yes, no) { * if (list == null || e == null) { * condition = false; * } else { * condition = false; * for (i in list) { * if (i.equals(e)) { * condition = true; * break; * } * } * } * if (condition) { * return yes; * } else { * return no; * } * } * </pre> * will be transformed into: * <pre> * contains(list, e, yes, no) { * if (list == null || e == null) { * return no; * } else { * condition = false; * for (i in list) { * if (i.equals(e)) { * return yes; * } * } * return no; * } * } * </pre> * * @return true if a transformation was made, false otherwise */ private boolean removeIntermediateMaterialization(SimplifierTool tool) { if (!(condition() instanceof CompareNode)) { return false; } CompareNode compare = (CompareNode) condition(); if (compare.usages().count() != 1) { return false; } if (!(predecessor() instanceof MergeNode)) { return false; } MergeNode merge = (MergeNode) predecessor(); if (!merge.anchored().isEmpty()) { return false; } // Only consider merges with a single usage that is both a phi and an operand of the comparison NodeIterable<Node> mergeUsages = merge.usages(); if (mergeUsages.count() != 1) { return false; } Node singleUsage = mergeUsages.first(); if (!(singleUsage instanceof PhiNode) || (singleUsage != compare.x() && singleUsage != compare.y())) { return false; } // Ensure phi is used by at most the comparison and the merge's frame state (if any) PhiNode phi = (PhiNode) singleUsage; NodeIterable<Node> phiUsages = phi.usages(); if (phiUsages.count() > 2) { return false; } for (Node usage : phiUsages) { if (usage != compare && usage != merge.stateAfter()) { return false; } } List<EndNode> mergePredecessors = merge.cfgPredecessors().snapshot(); if (phi.valueCount() != merge.forwardEndCount()) { // Handles a loop begin merge return false; } Constant[] xs = constantValues(compare.x(), merge); Constant[] ys = constantValues(compare.y(), merge); if (xs == null || ys == null) { return false; } List<EndNode> falseEnds = new ArrayList<>(mergePredecessors.size()); List<EndNode> trueEnds = new ArrayList<>(mergePredecessors.size()); Map<EndNode, ValueNode> phiValues = new HashMap<>(mergePredecessors.size()); BeginNode oldFalseSuccessor = falseSuccessor(); BeginNode oldTrueSuccessor = trueSuccessor(); setFalseSuccessor(null); setTrueSuccessor(null); Iterator<EndNode> ends = mergePredecessors.iterator(); for (int i = 0; i < xs.length; i++) { EndNode end = ends.next(); phiValues.put(end, phi.valueAt(end)); if (compare.condition().foldCondition(xs[i], ys[i], tool.runtime(), compare.unorderedIsTrue())) { trueEnds.add(end); } else { falseEnds.add(end); } } assert !ends.hasNext(); connectEnds(falseEnds, phiValues, oldFalseSuccessor, merge, tool); connectEnds(trueEnds, phiValues, oldTrueSuccessor, merge, tool); GraphUtil.killCFG(merge); assert !merge.isAlive() : merge; assert !phi.isAlive() : phi; assert !compare.isAlive() : compare; assert !this.isAlive() : this; return true; } /** * Connects a set of ends to a given successor, inserting a merge node if * there is more than one end. If {@code ends} is empty, then {@code successor} * is {@linkplain GraphUtil#killCFG(FixedNode) killed} otherwise it is added to {@code tool}'s * {@linkplain SimplifierTool#addToWorkList(com.oracle.graal.graph.Node) work list}. * * @param oldMerge the merge being removed * @param phiValues the values of the phi at the merge, keyed by the merge ends */ private void connectEnds(List<EndNode> ends, Map<EndNode, ValueNode> phiValues, BeginNode successor, MergeNode oldMerge, SimplifierTool tool) { if (ends.isEmpty()) { GraphUtil.killCFG(successor); } else { if (ends.size() == 1) { EndNode end = ends.get(0); ((FixedWithNextNode) end.predecessor()).setNext(successor); oldMerge.removeEnd(end); GraphUtil.killCFG(end); } else { // Need a new phi in case the frame state is used by more than the merge being removed MergeNode newMerge = graph().add(new MergeNode()); PhiNode oldPhi = (PhiNode) oldMerge.usages().first(); PhiNode newPhi = graph().add(new PhiNode(oldPhi.stamp(), newMerge)); double probability = 0.0; for (EndNode end : ends) { newPhi.addInput(phiValues.get(end)); newMerge.addForwardEnd(end); probability += end.probability(); } newMerge.setProbability(probability); FrameState stateAfter = oldMerge.stateAfter(); if (stateAfter != null) { stateAfter = stateAfter.duplicate(); stateAfter.replaceFirstInput(oldPhi, newPhi); newMerge.setStateAfter(stateAfter); } newMerge.setNext(successor); } tool.addToWorkList(successor); } } /** * Gets an array of constants derived from a node that is either a {@link ConstantNode} * or a {@link PhiNode} whose input values are all constants. The length of the returned * array is equal to the number of ends terminating in a given merge node. * * @return null if {@code node} is neither a {@link ConstantNode} nor a {@link PhiNode} whose input values are all constants */ private static Constant[] constantValues(ValueNode node, MergeNode merge) { if (node.isConstant()) { Constant[] result = new Constant[merge.forwardEndCount()]; Arrays.fill(result, node.asConstant()); return result; } if (node instanceof PhiNode) { PhiNode phi = (PhiNode) node; if (phi.merge() == merge && phi.type() == PhiType.Value && phi.valueCount() == merge.forwardEndCount()) { Constant[] result = new Constant[merge.forwardEndCount()]; int i = 0; for (ValueNode n : phi.values()) { if (!n.isConstant()) { return null; } result[i++] = n.asConstant(); } return result; } } return null; } private void removeEmptyIf(SimplifierTool tool) { BeginNode originalTrueSuccessor = trueSuccessor(); BeginNode originalFalseSuccessor = falseSuccessor(); assert originalTrueSuccessor.next() instanceof EndNode && originalFalseSuccessor.next() instanceof EndNode; EndNode trueEnd = (EndNode) originalTrueSuccessor.next(); EndNode falseEnd = (EndNode) originalFalseSuccessor.next(); assert trueEnd.merge() == falseEnd.merge(); FixedWithNextNode pred = (FixedWithNextNode) predecessor(); MergeNode merge = trueEnd.merge(); merge.prepareDelete(pred); assert merge.usages().isEmpty(); originalTrueSuccessor.prepareDelete(); originalFalseSuccessor.prepareDelete(); FixedNode next = merge.next(); FrameState state = merge.stateAfter(); merge.setNext(null); setTrueSuccessor(null); setFalseSuccessor(null); pred.setNext(next); safeDelete(); originalTrueSuccessor.safeDelete(); originalFalseSuccessor.safeDelete(); merge.safeDelete(); trueEnd.safeDelete(); falseEnd.safeDelete(); if (state != null) { tool.removeIfUnused(state); } tool.addToWorkList(next); } }