24 |
24 |
25 package org.graalvm.compiler.loop; |
25 package org.graalvm.compiler.loop; |
26 |
26 |
27 import static org.graalvm.compiler.core.common.GraalOptions.LoopMaxUnswitch; |
27 import static org.graalvm.compiler.core.common.GraalOptions.LoopMaxUnswitch; |
28 import static org.graalvm.compiler.core.common.GraalOptions.MaximumDesiredSize; |
28 import static org.graalvm.compiler.core.common.GraalOptions.MaximumDesiredSize; |
29 import static org.graalvm.compiler.core.common.GraalOptions.MinimumPeelProbability; |
29 import static org.graalvm.compiler.core.common.GraalOptions.MinimumPeelFrequency; |
30 |
30 |
31 import java.util.List; |
31 import java.util.List; |
32 |
32 |
33 import org.graalvm.compiler.core.common.util.UnsignedLong; |
33 import org.graalvm.compiler.core.common.util.UnsignedLong; |
34 import org.graalvm.compiler.debug.CounterKey; |
34 import org.graalvm.compiler.debug.CounterKey; |
36 import org.graalvm.compiler.debug.GraalError; |
36 import org.graalvm.compiler.debug.GraalError; |
37 import org.graalvm.compiler.graph.Node; |
37 import org.graalvm.compiler.graph.Node; |
38 import org.graalvm.compiler.graph.NodeBitMap; |
38 import org.graalvm.compiler.graph.NodeBitMap; |
39 import org.graalvm.compiler.nodes.AbstractBeginNode; |
39 import org.graalvm.compiler.nodes.AbstractBeginNode; |
40 import org.graalvm.compiler.nodes.ControlSplitNode; |
40 import org.graalvm.compiler.nodes.ControlSplitNode; |
41 import org.graalvm.compiler.nodes.DeoptimizeNode; |
|
42 import org.graalvm.compiler.nodes.FixedNode; |
|
43 import org.graalvm.compiler.nodes.FixedWithNextNode; |
|
44 import org.graalvm.compiler.nodes.InvokeNode; |
41 import org.graalvm.compiler.nodes.InvokeNode; |
45 import org.graalvm.compiler.nodes.LoopBeginNode; |
42 import org.graalvm.compiler.nodes.LoopBeginNode; |
46 import org.graalvm.compiler.nodes.MergeNode; |
43 import org.graalvm.compiler.nodes.MergeNode; |
47 import org.graalvm.compiler.nodes.StructuredGraph; |
44 import org.graalvm.compiler.nodes.StructuredGraph; |
48 import org.graalvm.compiler.nodes.VirtualState; |
45 import org.graalvm.compiler.nodes.VirtualState; |
49 import org.graalvm.compiler.nodes.VirtualState.VirtualClosure; |
46 import org.graalvm.compiler.nodes.VirtualState.VirtualClosure; |
50 import org.graalvm.compiler.nodes.calc.CompareNode; |
47 import org.graalvm.compiler.nodes.calc.CompareNode; |
51 import org.graalvm.compiler.nodes.cfg.Block; |
48 import org.graalvm.compiler.nodes.cfg.Block; |
52 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph; |
49 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph; |
53 import org.graalvm.compiler.nodes.debug.ControlFlowAnchorNode; |
50 import org.graalvm.compiler.nodes.debug.ControlFlowAnchorNode; |
54 import org.graalvm.compiler.nodes.java.TypeSwitchNode; |
|
55 import org.graalvm.compiler.options.Option; |
51 import org.graalvm.compiler.options.Option; |
56 import org.graalvm.compiler.options.OptionKey; |
52 import org.graalvm.compiler.options.OptionKey; |
57 import org.graalvm.compiler.options.OptionType; |
53 import org.graalvm.compiler.options.OptionType; |
58 import org.graalvm.compiler.options.OptionValues; |
54 import org.graalvm.compiler.options.OptionValues; |
59 |
55 |
77 |
73 |
78 @Override |
74 @Override |
79 public boolean shouldPeel(LoopEx loop, ControlFlowGraph cfg, MetaAccessProvider metaAccess) { |
75 public boolean shouldPeel(LoopEx loop, ControlFlowGraph cfg, MetaAccessProvider metaAccess) { |
80 LoopBeginNode loopBegin = loop.loopBegin(); |
76 LoopBeginNode loopBegin = loop.loopBegin(); |
81 double entryProbability = cfg.blockFor(loopBegin.forwardEnd()).getRelativeFrequency(); |
77 double entryProbability = cfg.blockFor(loopBegin.forwardEnd()).getRelativeFrequency(); |
82 OptionValues options = cfg.graph.getOptions(); |
78 StructuredGraph graph = cfg.graph; |
83 if (entryProbability > MinimumPeelProbability.getValue(options) && loop.size() + loopBegin.graph().getNodeCount() < MaximumDesiredSize.getValue(options)) { |
79 OptionValues options = graph.getOptions(); |
84 // check whether we're allowed to peel this loop |
80 |
85 return loop.canDuplicateLoop(); |
81 if (entryProbability < MinimumPeelFrequency.getValue(options)) { |
86 } else { |
82 return false; |
87 return false; |
83 } |
88 } |
84 |
|
85 if (loop.parent() != null) { |
|
86 if (loop.size() > loop.parent().size() >> 1) { |
|
87 // This loops make up more than half of the parent loop in terms of number of nodes. |
|
88 // There is a risk that this loop unproportionally increases parent loop body size. |
|
89 return false; |
|
90 } |
|
91 } |
|
92 |
|
93 if (loop.loop().getChildren().size() > 0) { |
|
94 // This loop has child loops. Loop peeling could explode graph size. |
|
95 return false; |
|
96 } |
|
97 |
|
98 if (loop.size() + graph.getNodeCount() > MaximumDesiredSize.getValue(options)) { |
|
99 // We are out of budget for peeling. |
|
100 return false; |
|
101 } |
|
102 |
|
103 return true; |
89 } |
104 } |
90 |
105 |
91 @Override |
106 @Override |
92 public boolean shouldFullUnroll(LoopEx loop) { |
107 public boolean shouldFullUnroll(LoopEx loop) { |
93 if (!loop.isCounted() || !loop.counted().isConstantMaxTripCount() || !loop.counted().counterNeverOverflows()) { |
108 if (!loop.isCounted() || !loop.counted().isConstantMaxTripCount() || !loop.counted().counterNeverOverflows()) { |
187 double loopFrequency = loopBegin.loopFrequency(); |
202 double loopFrequency = loopBegin.loopFrequency(); |
188 if (loopFrequency <= 1.0) { |
203 if (loopFrequency <= 1.0) { |
189 return false; |
204 return false; |
190 } |
205 } |
191 OptionValues options = loop.entryPoint().getOptions(); |
206 OptionValues options = loop.entryPoint().getOptions(); |
192 return loopBegin.unswitches() <= LoopMaxUnswitch.getValue(options); |
207 return loopBegin.unswitches() < LoopMaxUnswitch.getValue(options); |
193 } |
208 } |
194 |
209 |
195 private static final class CountingClosure implements VirtualClosure { |
210 private static final class CountingClosure implements VirtualClosure { |
196 int count; |
211 int count; |
197 |
212 |
236 |
251 |
237 loop.loopBegin().stateAfter().applyToVirtual(stateNodesCount); |
252 loop.loopBegin().stateAfter().applyToVirtual(stateNodesCount); |
238 int loopTotal = loop.size() - loop.loopBegin().phis().count() - stateNodesCount.count - 1; |
253 int loopTotal = loop.size() - loop.loopBegin().phis().count() - stateNodesCount.count - 1; |
239 int actualDiff = (loopTotal - inBranchTotal); |
254 int actualDiff = (loopTotal - inBranchTotal); |
240 ControlSplitNode firstSplit = controlSplits.get(0); |
255 ControlSplitNode firstSplit = controlSplits.get(0); |
241 if (firstSplit instanceof TypeSwitchNode) { |
256 |
242 int copies = firstSplit.successors().count() - 1; |
257 int copies = firstSplit.successors().count() - 1; |
243 for (Node succ : firstSplit.successors()) { |
258 actualDiff = actualDiff * copies; |
244 FixedNode current = (FixedNode) succ; |
|
245 while (current instanceof FixedWithNextNode) { |
|
246 current = ((FixedWithNextNode) current).next(); |
|
247 } |
|
248 if (current instanceof DeoptimizeNode) { |
|
249 copies--; |
|
250 } |
|
251 } |
|
252 actualDiff = actualDiff * copies; |
|
253 } |
|
254 |
259 |
255 debug.log("shouldUnswitch(%s, %s) : delta=%d (%.2f%% inside of branches), max=%d, f=%.2f, phis=%d -> %b", loop, controlSplits, actualDiff, (double) (inBranchTotal) / loopTotal * 100, maxDiff, |
260 debug.log("shouldUnswitch(%s, %s) : delta=%d (%.2f%% inside of branches), max=%d, f=%.2f, phis=%d -> %b", loop, controlSplits, actualDiff, (double) (inBranchTotal) / loopTotal * 100, maxDiff, |
256 loopFrequency, phis, actualDiff <= maxDiff); |
261 loopFrequency, phis, actualDiff <= maxDiff); |
257 if (actualDiff <= maxDiff) { |
262 if (actualDiff <= maxDiff) { |
258 // check whether we're allowed to unswitch this loop |
263 // check whether we're allowed to unswitch this loop |