Mercurial > hg > truffle
annotate graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java @ 7257:b1ebd583be14
Remove @Successor private final NodeSuccessorList<BeginNode> blockSuccessors from ControlSplitNode
Use normal successor fields in IfNode and InvokeWithException
MergeableState.afterSplit(FixedNode) is now MergeableState.afterSplit(BeginNode)
author | Gilles Duboscq <duboscq@ssw.jku.at> |
---|---|
date | Tue, 18 Dec 2012 11:27:12 +0100 |
parents | 2e96dc4eb8e2 |
children | 3964f3d4eb18 |
rev | line source |
---|---|
5675
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
1 /* |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
2 * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
4 * |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
5 * This code is free software; you can redistribute it and/or modify it |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
6 * under the terms of the GNU General Public License version 2 only, as |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
7 * published by the Free Software Foundation. |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
8 * |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
9 * This code is distributed in the hope that it will be useful, but WITHOUT |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
12 * version 2 for more details (a copy is included in the LICENSE file that |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
13 * accompanied this code). |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
14 * |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
15 * You should have received a copy of the GNU General Public License version |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
16 * 2 along with this work; if not, write to the Free Software Foundation, |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
18 * |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
21 * questions. |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
22 */ |
6523
c8763a2deb0c
rename packages in graal.loop to match project name
Doug Simon <doug.simon@oracle.com>
parents:
6522
diff
changeset
|
23 package com.oracle.graal.loop; |
5675
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
24 |
5732
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
25 import com.oracle.graal.debug.*; |
5675
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
26 import com.oracle.graal.nodes.*; |
6529
2e96dc4eb8e2
renamed package: com.oracle.graal.lir.cfg -> com.oracle.graal.nodes.cfg
Doug Simon <doug.simon@oracle.com>
parents:
6525
diff
changeset
|
27 import com.oracle.graal.nodes.cfg.*; |
6525
2c913b643422
rename packages in graal.phases to match project name
Doug Simon <doug.simon@oracle.com>
parents:
6523
diff
changeset
|
28 import com.oracle.graal.phases.*; |
5675
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
29 |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
30 |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
31 public abstract class LoopPolicies { |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
32 private LoopPolicies() { |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
33 // does not need to be instantiated |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
34 } |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
35 |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
36 // TODO (gd) change when inversion is available |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
37 public static boolean shouldPeel(LoopEx loop) { |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
38 LoopBeginNode loopBegin = loop.loopBegin(); |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
39 double entryProbability = loopBegin.forwardEnd().probability(); |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
40 return entryProbability > GraalOptions.MinimumPeelProbability && loop.size() + loopBegin.graph().getNodeCount() < GraalOptions.MaximumDesiredSize; |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
41 } |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
42 |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
43 public static boolean shouldFullUnroll(LoopEx loop) { |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
44 if (!loop.isCounted() || !loop.counted().isConstantMaxTripCount()) { |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
45 return false; |
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
46 } |
5887
e8628cb6296b
fix to FullUnroll changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
5884
diff
changeset
|
47 CountedLoopInfo counted = loop.counted(); |
e8628cb6296b
fix to FullUnroll changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
5884
diff
changeset
|
48 long exactTrips = counted.constantMaxTripCount(); |
e8628cb6296b
fix to FullUnroll changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
5884
diff
changeset
|
49 int maxNodes = (counted.isExactTripCount() && counted.isConstantExactTripCount()) ? GraalOptions.ExactFullUnrollMaxNodes : GraalOptions.FullUnrollMaxNodes; |
5884
347fad1ea1d0
increase full unrolling budget for fixed-size loops
Lukas Stadler <lukas.stadler@jku.at>
parents:
5732
diff
changeset
|
50 maxNodes = Math.min(maxNodes, GraalOptions.MaximumDesiredSize - loop.loopBegin().graph().getNodeCount()); |
5688
9bb0ba9e8ba6
Adjust loop unroll policy a bit
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5675
diff
changeset
|
51 int size = Math.max(1, loop.size() - 1 - loop.loopBegin().phis().count()); |
9bb0ba9e8ba6
Adjust loop unroll policy a bit
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5675
diff
changeset
|
52 return size * exactTrips <= maxNodes; |
5675
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
53 } |
5696
f592c22421e7
Look for LoopUnswitch opportunities (LoopUnswitch currently disabled)
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5688
diff
changeset
|
54 |
6309
6f8b6fc03c96
Add a maximum number of unswitching per loop
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5887
diff
changeset
|
55 public static boolean shouldTryUnswitch(LoopEx loop) { |
6f8b6fc03c96
Add a maximum number of unswitching per loop
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5887
diff
changeset
|
56 return loop.loopBegin().unswitches() <= GraalOptions.LoopMaxUnswitch; |
5696
f592c22421e7
Look for LoopUnswitch opportunities (LoopUnswitch currently disabled)
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5688
diff
changeset
|
57 } |
5732
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
58 |
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
59 public static boolean shouldUnswitch(LoopEx loop, IfNode ifNode) { |
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
60 Block postDomBlock = loop.loopsData().controlFlowGraph().blockFor(ifNode).getPostdominator(); |
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
61 BeginNode postDom = postDomBlock != null ? postDomBlock.getBeginNode() : null; |
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
62 int inTrueBranch = loop.nodesInLoopFrom(ifNode.trueSuccessor(), postDom).cardinality(); |
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
63 int inFalseBranch = loop.nodesInLoopFrom(ifNode.falseSuccessor(), postDom).cardinality(); |
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
64 int loopTotal = loop.size(); |
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
65 int netDiff = loopTotal - (inTrueBranch + inFalseBranch); |
7257
b1ebd583be14
Remove @Successor private final NodeSuccessorList<BeginNode> blockSuccessors from ControlSplitNode
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
6529
diff
changeset
|
66 double uncertainty = (0.5 - Math.abs(ifNode.probability(ifNode.trueSuccessor()) - 0.5)) * 2; |
5732
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
67 int maxDiff = GraalOptions.LoopUnswitchMaxIncrease + (int) (GraalOptions.LoopUnswitchUncertaintyBoost * loop.loopBegin().loopFrequency() * uncertainty); |
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
68 Debug.log("shouldUnswitch(%s, %s) : delta=%d, max=%d, %.2f%% inside of if", loop, ifNode, netDiff, maxDiff, (double) (inTrueBranch + inFalseBranch) / loopTotal * 100); |
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
69 return netDiff <= maxDiff; |
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
70 } |
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
71 |
e1d5c642d022
Started to draft a loop unswitching policy
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
5696
diff
changeset
|
72 |
5675
776366f3a41a
A bit of work on counted loops
Gilles Duboscq <duboscq@ssw.jku.at>
parents:
diff
changeset
|
73 } |