Mercurial > hg > truffle

comparison graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java @ 9993:053b837d0d7d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Readded the pass that fixes DeoptimizeNode probabilities.
author Christian Haeubl <haeubl@ssw.jku.at>
date Tue, 11 Jun 2013 13:10:25 +0200
parents 1b33ef6544b4
children 5260095a574b
comparison
equal deleted inserted replaced
9992:b2aea23ee2b1 9993:053b837d0d7d
22 */ 22 */
23 package com.oracle.graal.phases.graph; 23 package com.oracle.graal.phases.graph;
24 24
25 import java.util.*; 25 import java.util.*;
26 26
27 import com.oracle.graal.debug.internal.*;
27 import com.oracle.graal.graph.*; 28 import com.oracle.graal.graph.*;
28 import com.oracle.graal.nodes.*; 29 import com.oracle.graal.nodes.*;
29 import com.oracle.graal.nodes.util.*; 30 import com.oracle.graal.nodes.util.*;
30 31
31 /** 32 /**
61 this.loopInfos = new HashSet<>(); 62 this.loopInfos = new HashSet<>();
62 this.mergeLoops = new IdentityHashMap<>(); 63 this.mergeLoops = new IdentityHashMap<>();
63 } 64 }
64 65
65 public NodesToDoubles apply() { 66 public NodesToDoubles apply() {
67 adjustControlSplitProbabilities();
66 new PropagateProbability(graph.start()).apply(); 68 new PropagateProbability(graph.start()).apply();
67 computeLoopFactors(); 69 computeLoopFactors();
68 new PropagateLoopFrequency(graph.start()).apply(); 70 new PropagateLoopFrequency(graph.start()).apply();
71 assert verifyProbabilities();
69 return nodeProbabilities; 72 return nodeProbabilities;
73 }
74
75 /**
76 * Assume that paths with a DeoptimizeNode at their end are taken infrequently.
77 */
78 private void adjustControlSplitProbabilities() {
79 HashSet<ControlSplitNode> result = new HashSet<>();
80 NodeBitMap visitedNodes = new NodeBitMap(graph);
81 for (DeoptimizeNode n : graph.getNodes(DeoptimizeNode.class)) {
82 if (n.action().doesInvalidateCompilation()) {
83 findParentControlSplitNodes(result, n, visitedNodes);
84 }
85 }
86
87 for (ControlSplitNode n : result) {
88 if (!allSuxVisited(n, visitedNodes)) {
89 modifyProbabilities(n, visitedNodes);
90 }
91 }
92 }
93
94 private static void findParentControlSplitNodes(HashSet<ControlSplitNode> result, DeoptimizeNode n, NodeBitMap visitedNodes) {
95 ArrayDeque<FixedNode> nodes = new ArrayDeque<>();
96 nodes.push(n);
97
98 Node currentNode;
99 do {
100 currentNode = nodes.pop();
101 visitedNodes.mark(currentNode);
102
103 for (Node pred : currentNode.cfgPredecessors()) {
104 FixedNode fixedPred = (FixedNode) pred;
105 if (visitedNodes.isMarked(fixedPred) && allPredsVisited(fixedPred, visitedNodes)) {
106 DebugScope.dump(n.graph(), "ComputeProbabilityClosure");
107 GraalInternalError.shouldNotReachHere(String.format("Endless loop because %s was already visited", fixedPred));
108 } else if (allSuxVisited(fixedPred, visitedNodes)) {
109 nodes.push(fixedPred);
110 } else {
111 assert fixedPred instanceof ControlSplitNode : "only control splits can have more than one sux";
112 result.add((ControlSplitNode) fixedPred);
113 }
114 }
115 } while (!nodes.isEmpty());
116 }
117
118 private static void modifyProbabilities(ControlSplitNode controlSplit, NodeBitMap visitedNodes) {
119 assert !allSuxVisited(controlSplit, visitedNodes);
120 for (Node sux : controlSplit.successors()) {
121 if (visitedNodes.isMarked(sux)) {
122 controlSplit.setProbability((AbstractBeginNode) sux, 0);
123 }
124 }
125 }
126
127 private static boolean allSuxVisited(FixedNode node, NodeBitMap visitedNodes) {
128 return allVisited(node.successors(), visitedNodes);
129 }
130
131 private static boolean allPredsVisited(FixedNode node, NodeBitMap visitedNodes) {
132 return allVisited(node.cfgPredecessors(), visitedNodes);
133 }
134
135 private static boolean allVisited(Iterable<? extends Node> nodes, NodeBitMap visitedNodes) {
136 for (Node sux : nodes) {
137 if (!visitedNodes.contains(sux)) {
138 return false;
139 }
140 }
141 return true;
142 }
143
144 private boolean verifyProbabilities() {
145 if (doesNotAlwaysDeopt(graph)) {
146 for (DeoptimizeNode n : graph.getNodes(DeoptimizeNode.class)) {
147 if (n.action().doesInvalidateCompilation() && nodeProbabilities.get(n) > 0.01) {
148 throw new AssertionError(String.format("%s with reason %s and probability %f in graph %s", n, n.reason(), nodeProbabilities.get(n), graph));
149 }
150 }
151 }
152 return true;
153 }
154
155 private static boolean doesNotAlwaysDeopt(StructuredGraph graph) {
156 return graph.getNodes(ReturnNode.class).iterator().hasNext();
70 } 157 }
71 158
72 private void computeLoopFactors() { 159 private void computeLoopFactors() {
73 for (LoopInfo info : loopInfos) { 160 for (LoopInfo info : loopInfos) {
74 double frequency = info.loopFrequency(nodeProbabilities); 161 double frequency = info.loopFrequency(nodeProbabilities);