Mercurial > hg > truffle

annotate graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ExpandLogicPhase.java @ 21543:93c50cefb9e8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
moved GraalInternalError to com.oracle.jvmci.common and renamed it to JVMCIError (JBS:GRAAL-53)
author Doug Simon <doug.simon@oracle.com>
date Mon, 25 May 2015 23:30:34 +0200
parents 1cde96b96673
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
9443
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
1 /*
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
2 * Copyright (c) 2013, 2013, Oracle and/or its affiliates. All rights reserved.
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
4 *
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
7 * published by the Free Software Foundation.
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
8 *
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
13 * accompanied this code).
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
14 *
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
18 *
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
21 * questions.
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
22 */
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
23 package com.oracle.graal.phases.common;
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
24
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
25 import com.oracle.graal.graph.*;
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
26 import com.oracle.graal.nodes.*;
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
27 import com.oracle.graal.nodes.calc.*;
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
28 import com.oracle.graal.phases.*;
21543
93c50cefb9e8 moved GraalInternalError to com.oracle.jvmci.common and renamed it to JVMCIError (JBS:GRAAL-53)
Doug Simon <doug.simon@oracle.com>
parents: 19507
diff changeset
29 import com.oracle.jvmci.common.*;
9443
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
30
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
31 public class ExpandLogicPhase extends Phase {
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
32
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
33 @Override
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
34 protected void run(StructuredGraph graph) {
19403
61d3cb8e1280 Add generic parameter to NodeClass. Change Graph#getNodes(Class) to Graph#getNodes(NodeClass).
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18996
diff changeset
35 for (ShortCircuitOrNode logic : graph.getNodes(ShortCircuitOrNode.TYPE)) {
9443
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
36 processBinary(logic);
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
37 }
19403
61d3cb8e1280 Add generic parameter to NodeClass. Change Graph#getNodes(Class) to Graph#getNodes(NodeClass).
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18996
diff changeset
38 assert graph.getNodes(ShortCircuitOrNode.TYPE).isEmpty();
9443
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
39 }
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
40
11580
5ce62ee0fed7 Remove ShortCircuitAndNode
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 10789
diff changeset
41 private static void processBinary(ShortCircuitOrNode binary) {
9443
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
42 while (binary.usages().isNotEmpty()) {
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
43 Node usage = binary.usages().first();
11580
5ce62ee0fed7 Remove ShortCircuitAndNode
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 10789
diff changeset
44 if (usage instanceof ShortCircuitOrNode) {
5ce62ee0fed7 Remove ShortCircuitAndNode
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 10789
diff changeset
45 processBinary((ShortCircuitOrNode) usage);
9443
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
46 } else if (usage instanceof IfNode) {
11581
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
47 processIf(binary.getX(), binary.isXNegated(), binary.getY(), binary.isYNegated(), (IfNode) usage, binary.getShortCircuitProbability());
9443
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
48 } else if (usage instanceof ConditionalNode) {
11581
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
49 processConditional(binary.getX(), binary.isXNegated(), binary.getY(), binary.isYNegated(), (ConditionalNode) usage);
9443
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
50 } else {
21543
93c50cefb9e8 moved GraalInternalError to com.oracle.jvmci.common and renamed it to JVMCIError (JBS:GRAAL-53)
Doug Simon <doug.simon@oracle.com>
parents: 19507
diff changeset
51 throw JVMCIError.shouldNotReachHere();
9443
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
52 }
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
53 }
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
54 binary.safeDelete();
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
55 }
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
56
11581
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
57 private static void processIf(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, IfNode ifNode, double shortCircuitProbability) {
18993
480bd3b1adcd Rename BeginNode => AbstractBeginNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18845
diff changeset
58 AbstractBeginNode trueTarget = ifNode.trueSuccessor();
480bd3b1adcd Rename BeginNode => AbstractBeginNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18845
diff changeset
59 AbstractBeginNode falseTarget = ifNode.falseSuccessor();
10786
745322b36359 added a field to LogicBinaryNode capturing the probability that the evaluation of the logic node is short-circuited (i.e. only the left input is evaluated)
Doug Simon <doug.simon@oracle.com>
parents: 9569
diff changeset
60 double firstIfProbability = shortCircuitProbability;
11581
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
61 /*
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
62 * P(Y | not(X)) = P(Y inter not(X)) / P(not(X)) = (P(X union Y) - P(X)) / (1 - P(X))
19507
1cde96b96673 Fixed code format issues.
Roland Schatz <roland.schatz@oracle.com>
parents: 19403
diff changeset
63 *
11581
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
64 * P(X) = shortCircuitProbability
19507
1cde96b96673 Fixed code format issues.
Roland Schatz <roland.schatz@oracle.com>
parents: 19403
diff changeset
65 *
11581
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
66 * P(X union Y) = ifNode.probability(trueTarget)
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
67 */
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
68 double secondIfProbability = (ifNode.probability(trueTarget) - shortCircuitProbability) / (1 - shortCircuitProbability);
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
69 secondIfProbability = Math.min(1.0, Math.max(0.0, secondIfProbability));
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
70 if (Double.isNaN(secondIfProbability)) {
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
71 secondIfProbability = 0.5;
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
72 }
9443
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
73 ifNode.clearSuccessors();
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
74 Graph graph = ifNode.graph();
18996
46c2e70d54ad Make AbstractMergeNode abstract and introduce concrete subclass MergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
75 AbstractMergeNode trueTargetMerge = graph.add(new MergeNode());
11581
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
76 trueTargetMerge.setNext(trueTarget);
18845
f57d86eb036f removed Node factory methods
Doug Simon <doug.simon@oracle.com>
parents: 16895
diff changeset
77 EndNode firstTrueEnd = graph.add(new EndNode());
f57d86eb036f removed Node factory methods
Doug Simon <doug.simon@oracle.com>
parents: 16895
diff changeset
78 EndNode secondTrueEnd = graph.add(new EndNode());
11581
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
79 trueTargetMerge.addForwardEnd(firstTrueEnd);
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
80 trueTargetMerge.addForwardEnd(secondTrueEnd);
18994
8b4ef818169c Make AbstractBeginNode an abstract class and create concrete subclass BeginNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
81 AbstractBeginNode firstTrueTarget = BeginNode.begin(firstTrueEnd);
8b4ef818169c Make AbstractBeginNode an abstract class and create concrete subclass BeginNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
82 AbstractBeginNode secondTrueTarget = BeginNode.begin(secondTrueEnd);
8b4ef818169c Make AbstractBeginNode an abstract class and create concrete subclass BeginNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
83 AbstractBeginNode secondIf = BeginNode.begin(graph.add(new IfNode(y, yNegated ? falseTarget : secondTrueTarget, yNegated ? secondTrueTarget : falseTarget, secondIfProbability)));
18845
f57d86eb036f removed Node factory methods
Doug Simon <doug.simon@oracle.com>
parents: 16895
diff changeset
84 IfNode firstIf = graph.add(new IfNode(x, xNegated ? secondIf : firstTrueTarget, xNegated ? firstTrueTarget : secondIf, firstIfProbability));
9443
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
85 ifNode.replaceAtPredecessor(firstIf);
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
86 ifNode.safeDelete();
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
87 }
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
88
11581
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
89 private static void processConditional(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, ConditionalNode conditional) {
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
90 ValueNode trueTarget = conditional.trueValue();
454dc34d041c Simplify ExpandLogicPhase after ShortCircuitAndNode removal
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11580
diff changeset
91 ValueNode falseTarget = conditional.falseValue();
9443
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
92 Graph graph = conditional.graph();
18845
f57d86eb036f removed Node factory methods
Doug Simon <doug.simon@oracle.com>
parents: 16895
diff changeset
93 ConditionalNode secondConditional = graph.unique(new ConditionalNode(y, yNegated ? falseTarget : trueTarget, yNegated ? trueTarget : falseTarget));
f57d86eb036f removed Node factory methods
Doug Simon <doug.simon@oracle.com>
parents: 16895
diff changeset
94 ConditionalNode firstConditional = graph.unique(new ConditionalNode(x, xNegated ? secondConditional : trueTarget, xNegated ? trueTarget : secondConditional));
9443
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
95 conditional.replaceAndDelete(firstConditional);
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
96 }
490d283dbe90 Add Logic conjunction and disjunction and expand them before lir generation
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff changeset
97 }