Mercurial > hg > truffle

changeset 9443:490d283dbe90

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add Logic conjunction and disjunction and expand them before lir generation
author Gilles Duboscq <duboscq@ssw.jku.at>
date Tue, 30 Apr 2013 19:53:04 +0200
parents 46e83862cc03
children fd60b73f1759
files graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LowTier.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/AbstractBeginNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/AbstractEndNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicBinaryNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicConjunctionNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicDisjunctionNode.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ExpandLogicPhase.java
diffstat 5 files changed, 310 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LowTier.java	Tue Apr 30 19:51:49 2013 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LowTier.java	Tue Apr 30 19:53:04 2013 +0200
@@ -34,6 +34,8 @@
 
         addPhase(new FrameStateAssignmentPhase());
 
+        addPhase(new ExpandLogicPhase());
+
         addPhase(new DeadCodeEliminationPhase());
     }
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicBinaryNode.java	Tue Apr 30 19:53:04 2013 +0200
@@ -0,0 +1,72 @@
+/*
+ * Copyright (c) 2013, 2013, 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 com.oracle.graal.graph.*;
+import com.oracle.graal.nodes.spi.*;
+
+public abstract class LogicBinaryNode extends LogicNode implements Negatable, Node.IterableNodeType {
+
+    @Input private LogicNode x;
+    @Input private LogicNode y;
+    private boolean xNegated;
+    private boolean yNegated;
+
+    public LogicBinaryNode(LogicNode x, LogicNode y) {
+        this(x, false, y, false);
+    }
+
+    public LogicBinaryNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated) {
+        this.x = x;
+        this.xNegated = xNegated;
+        this.y = y;
+        this.yNegated = yNegated;
+    }
+
+    public LogicNode getX() {
+        return x;
+    }
+
+    public LogicNode getY() {
+        return y;
+    }
+
+    public boolean isXNegated() {
+        return xNegated;
+    }
+
+    public boolean isYNegated() {
+        return yNegated;
+    }
+
+    @Override
+    public Negatable negate(LogicNode condition) {
+        if (condition == x) {
+            xNegated = !xNegated;
+        }
+        if (condition == y) {
+            yNegated = !yNegated;
+        }
+        return this;
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicConjunctionNode.java	Tue Apr 30 19:53:04 2013 +0200
@@ -0,0 +1,70 @@
+/*
+ * Copyright (c) 2013, 2013, 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 com.oracle.graal.nodes.spi.*;
+
+/**
+ * This node is true if {@link #getX() x} <b>and</b> {@link #getY() y} are true.
+ * 
+ */
+public class LogicConjunctionNode extends LogicBinaryNode implements Canonicalizable {
+
+    public LogicConjunctionNode(LogicNode x, LogicNode y) {
+        this(x, false, y, false);
+    }
+
+    public LogicConjunctionNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated) {
+        super(x, xNegated, y, yNegated);
+    }
+
+    @Override
+    public LogicNode canonical(CanonicalizerTool tool) {
+        LogicNode x = getX();
+        LogicNode y = getY();
+        if (x == y) {
+            return x;
+        }
+        if (x instanceof LogicConstantNode) {
+            if (((LogicConstantNode) x).getValue() ^ isXNegated()) {
+                if (isYNegated()) {
+                    negateUsages();
+                }
+                return y;
+            } else {
+                return LogicConstantNode.contradiction(graph());
+            }
+        }
+        if (y instanceof LogicConstantNode) {
+            if (((LogicConstantNode) y).getValue() ^ isYNegated()) {
+                if (isXNegated()) {
+                    negateUsages();
+                }
+                return x;
+            } else {
+                return LogicConstantNode.contradiction(graph());
+            }
+        }
+        return this;
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicDisjunctionNode.java	Tue Apr 30 19:53:04 2013 +0200
@@ -0,0 +1,71 @@
+/*
+ * Copyright (c) 2013, 2013, 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 com.oracle.graal.nodes.spi.*;
+
+/**
+ * This node is true if {@link #getX() x} <b>or</b> {@link #getY() y} are true.
+ * 
+ */
+public class LogicDisjunctionNode extends LogicBinaryNode implements Canonicalizable {
+
+    public LogicDisjunctionNode(LogicNode x, LogicNode y) {
+        this(x, false, y, false);
+    }
+
+    public LogicDisjunctionNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated) {
+        super(x, xNegated, y, yNegated);
+    }
+
+    @Override
+    public LogicNode canonical(CanonicalizerTool tool) {
+        LogicNode x = getX();
+        LogicNode y = getY();
+        if (x == y) {
+            return x;
+        }
+        if (x instanceof LogicConstantNode) {
+            if (((LogicConstantNode) x).getValue() ^ isXNegated()) {
+                return LogicConstantNode.tautology(graph());
+            } else {
+                if (isYNegated()) {
+                    negateUsages();
+                }
+                return y;
+            }
+        }
+        if (y instanceof LogicConstantNode) {
+            if (((LogicConstantNode) y).getValue() ^ isYNegated()) {
+                return LogicConstantNode.tautology(graph());
+            } else {
+                if (isXNegated()) {
+                    negateUsages();
+                }
+                return x;
+            }
+        }
+        return this;
+    }
+
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ExpandLogicPhase.java	Tue Apr 30 19:53:04 2013 +0200
@@ -0,0 +1,95 @@
+/*
+ * Copyright (c) 2013, 2013, 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.phases.common;
+
+import com.oracle.graal.graph.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.calc.*;
+import com.oracle.graal.phases.*;
+
+public class ExpandLogicPhase extends Phase {
+
+    @Override
+    protected void run(StructuredGraph graph) {
+        for (LogicBinaryNode logic : graph.getNodes(LogicBinaryNode.class)) {
+            processBinary(logic);
+        }
+    }
+
+    private static void processBinary(LogicBinaryNode binary) {
+        while (binary.usages().isNotEmpty()) {
+            Node usage = binary.usages().first();
+            if (usage instanceof LogicBinaryNode) {
+                processBinary((LogicBinaryNode) usage);
+            } else if (usage instanceof IfNode) {
+                if (binary instanceof LogicConjunctionNode) {
+                    processIf(binary.getX(), binary.isXNegated(), binary.getY(), binary.isYNegated(), (IfNode) usage, false);
+                } else if (binary instanceof LogicDisjunctionNode) {
+                    processIf(binary.getX(), !binary.isXNegated(), binary.getY(), !binary.isYNegated(), (IfNode) usage, true);
+                } else {
+                    throw GraalInternalError.shouldNotReachHere();
+                }
+            } else if (usage instanceof ConditionalNode) {
+                if (binary instanceof LogicConjunctionNode) {
+                    processConditional(binary.getX(), binary.isXNegated(), binary.getY(), binary.isYNegated(), (ConditionalNode) usage, false);
+                } else if (binary instanceof LogicDisjunctionNode) {
+                    processConditional(binary.getX(), !binary.isXNegated(), binary.getY(), !binary.isYNegated(), (ConditionalNode) usage, true);
+                } else {
+                    throw GraalInternalError.shouldNotReachHere();
+                }
+            } else {
+                throw GraalInternalError.shouldNotReachHere();
+            }
+        }
+        binary.safeDelete();
+    }
+
+    private static void processIf(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, IfNode ifNode, boolean negateTargets) {
+        AbstractBeginNode trueTarget = negateTargets ? ifNode.falseSuccessor() : ifNode.trueSuccessor();
+        AbstractBeginNode falseTarget = negateTargets ? ifNode.trueSuccessor() : ifNode.falseSuccessor();
+        double p = Math.sqrt(ifNode.probability(trueTarget));
+        ifNode.clearSuccessors();
+        Graph graph = ifNode.graph();
+        MergeNode falseTargetMerge = graph.add(new MergeNode());
+        falseTargetMerge.setNext(falseTarget);
+        EndNode firstFalseEnd = graph.add(new EndNode());
+        EndNode secondFalseEnd = graph.add(new EndNode());
+        falseTargetMerge.addForwardEnd(firstFalseEnd);
+        falseTargetMerge.addForwardEnd(secondFalseEnd);
+        AbstractBeginNode firstFalseTarget = AbstractBeginNode.begin(firstFalseEnd);
+        AbstractBeginNode secondFalseTarget = AbstractBeginNode.begin(secondFalseEnd);
+        AbstractBeginNode secondIf = AbstractBeginNode.begin(graph.add(new IfNode(y, yNegated ? firstFalseTarget : trueTarget, yNegated ? trueTarget : firstFalseTarget, yNegated ? 1 - p : p)));
+        IfNode firstIf = graph.add(new IfNode(x, xNegated ? secondFalseTarget : secondIf, xNegated ? secondIf : secondFalseTarget, xNegated ? 1 - p : p));
+        ifNode.replaceAtPredecessor(firstIf);
+        ifNode.safeDelete();
+    }
+
+    private static void processConditional(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, ConditionalNode conditional, boolean negateTargets) {
+        ValueNode trueTarget = negateTargets ? conditional.falseValue() : conditional.trueValue();
+        ValueNode falseTarget = negateTargets ? conditional.trueValue() : conditional.falseValue();
+        Graph graph = conditional.graph();
+        ConditionalNode secondConditional = graph.unique(new ConditionalNode(y, yNegated ? falseTarget : trueTarget, yNegated ? trueTarget : falseTarget));
+        ConditionalNode firstConditional = graph.unique(new ConditionalNode(x, xNegated ? falseTarget : secondConditional, xNegated ? secondConditional : falseTarget));
+        conditional.replaceAndDelete(firstConditional);
+    }
+}