1 /*
   2  * Copyright (c) 2013, 2013, 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 org.graalvm.compiler.debug.GraalError;
  26 import org.graalvm.compiler.graph.Graph;
  27 import org.graalvm.compiler.graph.Node;
  28 import org.graalvm.compiler.nodes.AbstractBeginNode;
  29 import org.graalvm.compiler.nodes.AbstractMergeNode;
  30 import org.graalvm.compiler.nodes.BeginNode;
  31 import org.graalvm.compiler.nodes.EndNode;
  32 import org.graalvm.compiler.nodes.IfNode;
  33 import org.graalvm.compiler.nodes.LogicNode;
  34 import org.graalvm.compiler.nodes.MergeNode;
  35 import org.graalvm.compiler.nodes.ShortCircuitOrNode;
  36 import org.graalvm.compiler.nodes.StructuredGraph;
  37 import org.graalvm.compiler.nodes.ValueNode;
  38 import org.graalvm.compiler.nodes.calc.ConditionalNode;
  39 import org.graalvm.compiler.phases.Phase;
  40 
  41 public class ExpandLogicPhase extends Phase {
  42 
  43     @Override
  44     protected void run(StructuredGraph graph) {
  45         for (ShortCircuitOrNode logic : graph.getNodes(ShortCircuitOrNode.TYPE)) {
  46             processBinary(logic);
  47         }
  48         assert graph.getNodes(ShortCircuitOrNode.TYPE).isEmpty();
  49     }
  50 
  51     private static void processBinary(ShortCircuitOrNode binary) {
  52         while (binary.usages().isNotEmpty()) {
  53             Node usage = binary.usages().first();
  54             if (usage instanceof ShortCircuitOrNode) {
  55                 processBinary((ShortCircuitOrNode) usage);
  56             } else if (usage instanceof IfNode) {
  57                 processIf(binary.getX(), binary.isXNegated(), binary.getY(), binary.isYNegated(), (IfNode) usage, binary.getShortCircuitProbability());
  58             } else if (usage instanceof ConditionalNode) {
  59                 processConditional(binary.getX(), binary.isXNegated(), binary.getY(), binary.isYNegated(), (ConditionalNode) usage);
  60             } else {
  61                 throw GraalError.shouldNotReachHere();
  62             }
  63         }
  64         binary.safeDelete();
  65     }
  66 
  67     private static void processIf(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, IfNode ifNode, double shortCircuitProbability) {
  68         AbstractBeginNode trueTarget = ifNode.trueSuccessor();
  69         AbstractBeginNode falseTarget = ifNode.falseSuccessor();
  70         double firstIfProbability = shortCircuitProbability;
  71         /*
  72          * P(Y | not(X)) = P(Y inter not(X)) / P(not(X)) = (P(X union Y) - P(X)) / (1 - P(X))
  73          *
  74          * P(X) = shortCircuitProbability
  75          *
  76          * P(X union Y) = ifNode.probability(trueTarget)
  77          */
  78         double secondIfProbability = (ifNode.probability(trueTarget) - shortCircuitProbability) / (1 - shortCircuitProbability);
  79         secondIfProbability = Math.min(1.0, Math.max(0.0, secondIfProbability));
  80         if (Double.isNaN(secondIfProbability)) {
  81             secondIfProbability = 0.5;
  82         }
  83         ifNode.clearSuccessors();
  84         Graph graph = ifNode.graph();
  85         AbstractMergeNode trueTargetMerge = graph.add(new MergeNode());
  86         trueTargetMerge.setNext(trueTarget);
  87         EndNode firstTrueEnd = graph.add(new EndNode());
  88         EndNode secondTrueEnd = graph.add(new EndNode());
  89         trueTargetMerge.addForwardEnd(firstTrueEnd);
  90         trueTargetMerge.addForwardEnd(secondTrueEnd);
  91         AbstractBeginNode firstTrueTarget = BeginNode.begin(firstTrueEnd);
  92         AbstractBeginNode secondTrueTarget = BeginNode.begin(secondTrueEnd);
  93         AbstractBeginNode secondIf = BeginNode.begin(graph.add(new IfNode(y, yNegated ? falseTarget : secondTrueTarget, yNegated ? secondTrueTarget : falseTarget, secondIfProbability)));
  94         IfNode firstIf = graph.add(new IfNode(x, xNegated ? secondIf : firstTrueTarget, xNegated ? firstTrueTarget : secondIf, firstIfProbability));
  95         ifNode.replaceAtPredecessor(firstIf);
  96         ifNode.safeDelete();
  97     }
  98 
  99     private static void processConditional(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, ConditionalNode conditional) {
 100         ValueNode trueTarget = conditional.trueValue();
 101         ValueNode falseTarget = conditional.falseValue();
 102         Graph graph = conditional.graph();
 103         ConditionalNode secondConditional = graph.unique(new ConditionalNode(y, yNegated ? falseTarget : trueTarget, yNegated ? trueTarget : falseTarget));
 104         ConditionalNode firstConditional = graph.unique(new ConditionalNode(x, xNegated ? secondConditional : trueTarget, xNegated ? trueTarget : secondConditional));
 105         conditional.replaceAndDelete(firstConditional);
 106     }
 107 
 108     @Override
 109     public boolean checkContract() {
 110         return false;
 111     }
 112 }