Mercurial > hg > truffle

annotate graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java @ 19048:b300d1f6e817

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
schedule inputs of proxy nodes at the loop exit
author Lukas Stadler <lukas.stadler@oracle.com>
date Fri, 30 Jan 2015 20:52:39 +0100
parents 84bf57a0ddcb
children db390d92bb16
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1 /*
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
2 * Copyright (c) 2011, 2013, Oracle and/or its affiliates. All rights reserved.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
4 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
7 * published by the Free Software Foundation.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
8 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
13 * accompanied this code).
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
14 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
18 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
21 * questions.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
22 */
6525
2c913b643422 rename packages in graal.phases to match project name
Doug Simon <doug.simon@oracle.com>
parents: 6522
diff changeset
23 package com.oracle.graal.phases.schedule;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
24
9793
b4f12c603be5 added support for the runtime to specify for each foreign call whether it is re-executable and what memory locations it kills
Doug Simon <doug.simon@oracle.com>
parents: 9792
diff changeset
25 import static com.oracle.graal.api.meta.LocationIdentity.*;
15259
d90e5c22ba55 Move GraalOptions to graal.compiler.common.
Josef Eisl <josef.eisl@jku.at>
parents: 15193
diff changeset
26 import static com.oracle.graal.compiler.common.GraalOptions.*;
16503
b3800429f543 Move commonDominator to AbstractControlFlowGraph.
Josef Eisl <josef.eisl@jku.at>
parents: 16443
diff changeset
27 import static com.oracle.graal.compiler.common.cfg.AbstractControlFlowGraph.*;
9793
b4f12c603be5 added support for the runtime to specify for each foreign call whether it is re-executable and what memory locations it kills
Doug Simon <doug.simon@oracle.com>
parents: 9792
diff changeset
28
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
29 import java.util.*;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
30
9792
06dc2d2324d6 pulled LocationIdentity into a top level class and moved it to the api.meta project
Doug Simon <doug.simon@oracle.com>
parents: 9725
diff changeset
31 import com.oracle.graal.api.meta.*;
15193
96bb07a5d667 Spit up and move GraalInternalError.
Josef Eisl <josef.eisl@jku.at>
parents: 15192
diff changeset
32 import com.oracle.graal.compiler.common.*;
15192
644dfe49c0f4 Move packages com.oracle.graal.cfg to com.oracle.graal.compiler.common.cfg.
Josef Eisl <josef.eisl@jku.at>
parents: 15173
diff changeset
33 import com.oracle.graal.compiler.common.cfg.*;
6500
8fd4201ce98c moved TTY and LogStream to com.oracle.graal.debug
Doug Simon <doug.simon@oracle.com>
parents: 6411
diff changeset
34 import com.oracle.graal.debug.*;
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
35 import com.oracle.graal.graph.*;
16841
cbd42807a31f moved NodeInfo and friends into separate com.oracle.graal.nodeinfo project so that annotation processor can be applied to the base Node class
Doug Simon <doug.simon@oracle.com>
parents: 16505
diff changeset
36 import com.oracle.graal.nodeinfo.*;
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
37 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: 6526
diff changeset
38 import com.oracle.graal.nodes.cfg.*;
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
39 import com.oracle.graal.nodes.extended.*;
11787
4fc75b6ca3dd Introduce NodeWithState for nodes that hold some VirtualState. Use this interface in the required special cases (Scheduling and PEA)
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11501
diff changeset
40 import com.oracle.graal.nodes.spi.*;
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
41 import com.oracle.graal.nodes.virtual.*;
6525
2c913b643422 rename packages in graal.phases to match project name
Doug Simon <doug.simon@oracle.com>
parents: 6522
diff changeset
42 import com.oracle.graal.phases.*;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
43 import com.oracle.graal.phases.graph.*;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
44 import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
45 import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo;
13369
c3ecad078114 utils: introduce ArraySet. use it instead of HashSet at some places
Bernhard Urban <bernhard.urban@jku.at>
parents: 13327
diff changeset
46 import com.oracle.graal.phases.util.*;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
47
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
48 public final class SchedulePhase extends Phase {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
49
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
50 /**
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
51 * Error thrown when a graph cannot be scheduled.
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
52 */
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
53 public static class SchedulingError extends Error {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
54
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
55 private static final long serialVersionUID = 1621001069476473145L;
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
56
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
57 public SchedulingError() {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
58 super();
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
59 }
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
60
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
61 /**
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
62 * This constructor creates a {@link SchedulingError} with a message assembled via
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
63 * {@link String#format(String, Object...)}.
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
64 *
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
65 * @param format a {@linkplain Formatter format} string
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
66 * @param args parameters to {@link String#format(String, Object...)}
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
67 */
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
68 public SchedulingError(String format, Object... args) {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
69 super(String.format(format, args));
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
70 }
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
71
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
72 }
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
73
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
74 public static enum SchedulingStrategy {
14908
8db6e76cb658 Formatter: Keep one enum constant per line
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 14906
diff changeset
75 EARLIEST,
8db6e76cb658 Formatter: Keep one enum constant per line
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 14906
diff changeset
76 LATEST,
8db6e76cb658 Formatter: Keep one enum constant per line
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 14906
diff changeset
77 LATEST_OUT_OF_LOOPS
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
78 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
79
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
80 static int created;
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
81
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
82 private class LocationSet {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
83 private LocationIdentity firstLocation;
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
84 private List<LocationIdentity> list;
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
85
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
86 public LocationSet() {
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
87 list = null;
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
88 }
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
89
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
90 public LocationSet(LocationSet other) {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
91 this.firstLocation = other.firstLocation;
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
92 if (other.list != null && other.list.size() > 0) {
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
93 list = new ArrayList<>(other.list);
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
94 }
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
95 }
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
96
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
97 private void initList() {
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
98 if (list == null) {
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
99 list = new ArrayList<>(4);
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
100 }
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
101 }
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
102
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
103 public void add(LocationIdentity location) {
19002
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
104 if (LocationIdentity.ANY_LOCATION.equals(location)) {
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
105 firstLocation = location;
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
106 list = null;
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
107 } else {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
108 if (firstLocation == null) {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
109 firstLocation = location;
19002
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
110 } else if (LocationIdentity.ANY_LOCATION.equals(firstLocation)) {
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
111 return;
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
112 } else if (location.equals(firstLocation)) {
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
113 return;
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
114 } else {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
115 initList();
19002
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
116 for (int i = 0; i < list.size(); ++i) {
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
117 LocationIdentity value = list.get(i);
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
118 if (location.equals(value)) {
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
119 return;
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
120 }
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
121 }
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
122 list.add(location);
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
123 }
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
124 }
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
125 }
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
126
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
127 public void addAll(LocationSet other) {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
128 if (other.firstLocation != null) {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
129 add(other.firstLocation);
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
130 }
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
131 List<LocationIdentity> otherList = other.list;
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
132 if (otherList != null) {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
133 for (LocationIdentity l : otherList) {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
134 add(l);
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
135 }
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
136 }
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
137 }
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
138
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
139 public boolean contains(LocationIdentity locationIdentity) {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
140 assert locationIdentity != null;
19002
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
141 assert !locationIdentity.equals(LocationIdentity.ANY_LOCATION);
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
142 assert !locationIdentity.equals(LocationIdentity.FINAL_LOCATION);
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
143 if (LocationIdentity.ANY_LOCATION.equals(firstLocation)) {
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
144 return true;
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
145 }
19002
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
146 if (locationIdentity.equals(firstLocation)) {
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
147 return true;
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
148 }
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
149 if (list != null) {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
150 for (int i = 0; i < list.size(); ++i) {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
151 LocationIdentity value = list.get(i);
19002
3be6793b4549 Fix LocationSet - use equals for comparing LocationIdentity objects.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
152 if (locationIdentity.equals(value)) {
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
153 return true;
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
154 }
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
155 }
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
156 }
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
157 return false;
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
158 }
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
159
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
160 public List<LocationIdentity> getCopyAsList() {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
161 ArrayList<LocationIdentity> result = new ArrayList<>();
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
162 if (firstLocation != null) {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
163 result.add(firstLocation);
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
164 }
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
165 if (list != null) {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
166 result.addAll(list);
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
167 }
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
168 return result;
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
169 }
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
170 }
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
171
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
172 private class NewMemoryScheduleClosure extends BlockIteratorClosure<LocationSet> {
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
173 private Node excludeNode;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
174 private Block upperBoundBlock;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
175
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
176 public NewMemoryScheduleClosure(Node excludeNode, Block upperBoundBlock) {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
177 this.excludeNode = excludeNode;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
178 this.upperBoundBlock = upperBoundBlock;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
179 }
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
180
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
181 public NewMemoryScheduleClosure() {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
182 this(null, null);
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
183 }
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
184
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
185 @Override
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
186 protected LocationSet getInitialState() {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
187 return cloneState(blockToKillSet.get(getCFG().getStartBlock()));
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
188 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
189
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
190 @Override
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
191 protected LocationSet processBlock(Block block, LocationSet currentState) {
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
192 assert block != null;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
193 currentState.addAll(computeKillSet(block, block == upperBoundBlock ? excludeNode : null));
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
194 return currentState;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
195 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
196
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
197 @Override
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
198 protected LocationSet merge(Block merge, List<LocationSet> states) {
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
199 assert merge.getBeginNode() instanceof AbstractMergeNode;
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
200
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
201 LocationSet initKillSet = new LocationSet();
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
202 for (LocationSet state : states) {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
203 initKillSet.addAll(state);
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
204 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
205
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
206 return initKillSet;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
207 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
208
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
209 @Override
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
210 protected LocationSet cloneState(LocationSet state) {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
211 return new LocationSet(state);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
212 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
213
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
214 @Override
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
215 protected List<LocationSet> processLoop(Loop<Block> loop, LocationSet state) {
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
216 LoopInfo<LocationSet> info = ReentrantBlockIterator.processLoop(this, loop, cloneState(state));
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
217
15534
4bd6ad45ee0a Encapsulate members of Loop.
Josef Eisl <josef.eisl@jku.at>
parents: 15423
diff changeset
218 assert loop.getHeader().getBeginNode() instanceof LoopBeginNode;
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
219 LocationSet headerState = merge(loop.getHeader(), info.endStates);
11863
7763a42d1658 NewMemoryAwareScheduling: handle MemoryPhis properly
Bernhard Urban <bernhard.urban@jku.at>
parents: 11787
diff changeset
220
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
221 // second iteration, for propagating information to loop exits
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
222 info = ReentrantBlockIterator.processLoop(this, loop, cloneState(headerState));
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
223
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
224 return info.exitStates;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
225 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
226 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
227
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
228 /**
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
229 * gather all kill locations by iterating trough the nodes assigned to a block.
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
230 *
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
231 * assumptions: {@link MemoryCheckpoint MemoryCheckPoints} are {@link FixedNode FixedNodes}.
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
232 *
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
233 * @param block block to analyze
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
234 * @param excludeNode if null, compute normal set of kill locations. if != null, don't add kills
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
235 * until we reach excludeNode.
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
236 * @return all killed locations
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
237 */
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
238 private LocationSet computeKillSet(Block block, Node excludeNode) {
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
239 // cache is only valid if we don't potentially exclude kills from the set
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
240 if (excludeNode == null) {
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
241 LocationSet cachedSet = blockToKillSet.get(block);
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
242 if (cachedSet != null) {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
243 return cachedSet;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
244 }
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
245 }
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
246
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
247 // add locations to excludedLocations until we reach the excluded node
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
248 boolean foundExcludeNode = excludeNode == null;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
249
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
250 LocationSet set = new LocationSet();
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
251 LocationSet excludedLocations = new LocationSet();
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
252 if (block.getBeginNode() instanceof AbstractMergeNode) {
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
253 AbstractMergeNode mergeNode = (AbstractMergeNode) block.getBeginNode();
13152
640516a8ca6b Separate class for MemoryProxy and MemoryPhi.
Roland Schatz <roland.schatz@oracle.com>
parents: 13092
diff changeset
254 for (MemoryPhiNode phi : mergeNode.usages().filter(MemoryPhiNode.class)) {
640516a8ca6b Separate class for MemoryProxy and MemoryPhi.
Roland Schatz <roland.schatz@oracle.com>
parents: 13092
diff changeset
255 if (foundExcludeNode) {
640516a8ca6b Separate class for MemoryProxy and MemoryPhi.
Roland Schatz <roland.schatz@oracle.com>
parents: 13092
diff changeset
256 set.add(phi.getLocationIdentity());
640516a8ca6b Separate class for MemoryProxy and MemoryPhi.
Roland Schatz <roland.schatz@oracle.com>
parents: 13092
diff changeset
257 } else {
640516a8ca6b Separate class for MemoryProxy and MemoryPhi.
Roland Schatz <roland.schatz@oracle.com>
parents: 13092
diff changeset
258 excludedLocations.add(phi.getLocationIdentity());
640516a8ca6b Separate class for MemoryProxy and MemoryPhi.
Roland Schatz <roland.schatz@oracle.com>
parents: 13092
diff changeset
259 foundExcludeNode = phi == excludeNode;
11863
7763a42d1658 NewMemoryAwareScheduling: handle MemoryPhis properly
Bernhard Urban <bernhard.urban@jku.at>
parents: 11787
diff changeset
260 }
7763a42d1658 NewMemoryAwareScheduling: handle MemoryPhis properly
Bernhard Urban <bernhard.urban@jku.at>
parents: 11787
diff changeset
261 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
262 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
263
18993
480bd3b1adcd Rename BeginNode => AbstractBeginNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18992
diff changeset
264 AbstractBeginNode startNode = cfg.getStartBlock().getBeginNode();
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
265 assert startNode instanceof StartNode;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
266
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
267 LocationSet accm = foundExcludeNode ? set : excludedLocations;
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
268 for (Node node : block.getNodes()) {
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
269 if (!foundExcludeNode && node == excludeNode) {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
270 foundExcludeNode = true;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
271 }
15782
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
272 if (node != startNode) {
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
273 if (node instanceof MemoryCheckpoint.Single) {
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
274 LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
275 accm.add(identity);
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
276 } else if (node instanceof MemoryCheckpoint.Multi) {
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
277 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
278 accm.add(identity);
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
279 }
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
280 }
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
281 assert MemoryCheckpoint.TypeAssertion.correctType(node);
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
282 }
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
283
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
284 if (foundExcludeNode) {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
285 accm = set;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
286 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
287 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
288
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
289 // merge it for the cache entry
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
290 excludedLocations.addAll(set);
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
291 blockToKillSet.put(block, excludedLocations);
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
292
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
293 return set;
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
294 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
295
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
296 private LocationSet computeKillSet(Block block) {
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
297 return computeKillSet(block, null);
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
298 }
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
299
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
300 private ControlFlowGraph cfg;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
301 private NodeMap<Block> earliestCache;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
302
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
303 /**
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
304 * Map from blocks to the nodes in each block.
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
305 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
306 private BlockMap<List<ValueNode>> blockToNodesMap;
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
307 private BlockMap<LocationSet> blockToKillSet;
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
308 private final SchedulingStrategy selectedStrategy;
8325
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
309
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
310 public SchedulePhase() {
9864
063a712fe8d8 converted remaining options in GraalOptions to new system (GRAAL-27)
Doug Simon <doug.simon@oracle.com>
parents: 9810
diff changeset
311 this(OptScheduleOutOfLoops.getValue() ? SchedulingStrategy.LATEST_OUT_OF_LOOPS : SchedulingStrategy.LATEST);
8325
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
312 }
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
313
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
314 public SchedulePhase(SchedulingStrategy strategy) {
8330
022ae20329fb Rename field.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8325
diff changeset
315 this.selectedStrategy = strategy;
8325
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
316 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
317
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
318 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
319 protected void run(StructuredGraph graph) {
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 13599
diff changeset
320 assert GraphOrder.assertNonCyclicGraph(graph);
9413
4f8b7dc2766d SchedulePhase: compute post-dominators in CFG-graph
Bernhard Urban <bernhard.urban@jku.at>
parents: 8957
diff changeset
321 cfg = ControlFlowGraph.compute(graph, true, true, true, true);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
322 earliestCache = graph.createNodeMap();
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
323 blockToNodesMap = new BlockMap<>(cfg);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
324
18965
53fcb13db742 Always use read aware memory scheduling.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18955
diff changeset
325 if (selectedStrategy != SchedulingStrategy.EARLIEST) {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
326 blockToKillSet = new BlockMap<>(cfg);
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
327 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
328
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
329 assignBlockToNodes(graph, selectedStrategy);
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
330 printSchedule("after assign nodes to blocks");
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
331
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
332 sortNodesWithinBlocks(graph, selectedStrategy);
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
333 printSchedule("after sorting nodes within blocks");
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
334 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
335
13153
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
336 private Block blockForMemoryNode(MemoryNode memory) {
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
337 MemoryNode current = memory;
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
338 while (current instanceof MemoryProxy) {
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
339 current = ((MemoryProxy) current).getOriginalMemoryNode();
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
340 }
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
341 Block b = cfg.getNodeToBlock().get(current.asNode());
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
342 assert b != null : "all lastAccess locations should have a block assignment from CFG";
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
343 return b;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
344 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
345
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
346 private void printSchedule(String desc) {
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
347 if (Debug.isLogEnabled()) {
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
348 printScheduleHelper(desc);
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
349 }
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
350 }
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
351
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
352 private void printScheduleHelper(String desc) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
353 Formatter buf = new Formatter();
18965
53fcb13db742 Always use read aware memory scheduling.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18955
diff changeset
354 buf.format("=== %s / %s / %s ===%n", getCFG().getStartBlock().getBeginNode().graph(), selectedStrategy, desc);
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
355 for (Block b : getCFG().getBlocks()) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
356 buf.format("==== b: %s (loopDepth: %s). ", b, b.getLoopDepth());
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
357 buf.format("dom: %s. ", b.getDominator());
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
358 buf.format("post-dom: %s. ", b.getPostdominator());
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
359 buf.format("preds: %s. ", b.getPredecessors());
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
360 buf.format("succs: %s ====%n", b.getSuccessors());
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
361 BlockMap<LocationSet> killSets = blockToKillSet;
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
362 if (killSets != null) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
363 buf.format("X block kills: %n");
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
364 if (killSets.get(b) != null) {
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
365 for (LocationIdentity locId : killSets.get(b).getCopyAsList()) {
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
366 buf.format("X %s killed by %s%n", locId, "dunno anymore");
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
367 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
368 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
369 }
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
370
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
371 if (blockToNodesMap.get(b) != null) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
372 for (Node n : nodesFor(b)) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
373 printNode(n);
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
374 }
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
375 } else {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
376 for (Node n : b.getNodes()) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
377 printNode(n);
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
378 }
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
379 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
380 }
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
381 buf.format("%n");
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
382 Debug.log("%s", buf);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
383 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
384
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
385 private static void printNode(Node n) {
14873
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
386 Formatter buf = new Formatter();
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
387 buf.format("%s", n);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
388 if (n instanceof MemoryCheckpoint.Single) {
14873
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
389 buf.format(" // kills %s", ((MemoryCheckpoint.Single) n).getLocationIdentity());
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
390 } else if (n instanceof MemoryCheckpoint.Multi) {
14873
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
391 buf.format(" // kills ");
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
392 for (LocationIdentity locid : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
14873
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
393 buf.format("%s, ", locid);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
394 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
395 } else if (n instanceof FloatingReadNode) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
396 FloatingReadNode frn = (FloatingReadNode) n;
14873
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
397 buf.format(" // from %s", frn.location().getLocationIdentity());
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
398 buf.format(", lastAccess: %s", frn.getLastLocationAccess());
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
399 buf.format(", object: %s", frn.object());
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
400 } else if (n instanceof GuardNode) {
15008
01fdabd19cd5 new AnchoringNode interface
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14908
diff changeset
401 buf.format(", anchor: %s", ((GuardNode) n).getAnchor());
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
402 }
14873
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
403 Debug.log("%s", buf);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
404 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
405
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
406 public ControlFlowGraph getCFG() {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
407 return cfg;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
408 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
409
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
410 /**
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
411 * Gets the map from each block to the nodes in the block.
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
412 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
413 public BlockMap<List<ValueNode>> getBlockToNodesMap() {
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
414 return blockToNodesMap;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
415 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
416
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
417 /**
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
418 * Gets the nodes in a given block.
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
419 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
420 public List<ValueNode> nodesFor(Block block) {
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
421 return blockToNodesMap.get(block);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
422 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
423
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
424 private void assignBlockToNodes(StructuredGraph graph, SchedulingStrategy strategy) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
425 for (Block block : cfg.getBlocks()) {
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
426 List<ValueNode> nodes = new ArrayList<>();
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
427 if (blockToNodesMap.get(block) != null) {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
428 throw new SchedulingError();
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
429 }
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
430 blockToNodesMap.put(block, nodes);
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
431 for (FixedNode node : block.getNodes()) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
432 nodes.add(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
433 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
434 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
435
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
436 for (Node n : graph.getNodes()) {
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
437 if (n instanceof ValueNode) {
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
438 assignBlockToNode((ValueNode) n, strategy);
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
439 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
440 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
441 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
442
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
443 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
444 * Assigns a block to the given node. This method expects that PhiNodes and FixedNodes are
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
445 * already assigned to a block.
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
446 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
447 private void assignBlockToNode(ValueNode node, SchedulingStrategy strategy) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
448 assert !node.isDeleted();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
449
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
450 if (cfg.getNodeToBlock().containsKey(node)) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
451 return;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
452 }
10892
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 10891
diff changeset
453 // PhiNodes, ProxyNodes and FixedNodes should already have been placed in blocks by
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
454 // ControlFlowGraph.identifyBlocks
10892
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 10891
diff changeset
455 if (node instanceof PhiNode || node instanceof ProxyNode || node instanceof FixedNode) {
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
456 throw new SchedulingError("%s should already have been placed in a block", node);
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
457 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
458
11865
3d97040060d4 SchedulePhase: bail out with SchedulingError if scheduled block is not dominated by earliest
Bernhard Urban <bernhard.urban@jku.at>
parents: 11864
diff changeset
459 Block earliestBlock = earliestBlock(node);
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
460 Block block = null;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
461 Block latest = null;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
462 switch (strategy) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
463 case EARLIEST:
11865
3d97040060d4 SchedulePhase: bail out with SchedulingError if scheduled block is not dominated by earliest
Bernhard Urban <bernhard.urban@jku.at>
parents: 11864
diff changeset
464 block = earliestBlock;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
465 break;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
466 case LATEST:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
467 case LATEST_OUT_OF_LOOPS:
18965
53fcb13db742 Always use read aware memory scheduling.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18955
diff changeset
468 boolean scheduleRead = node instanceof FloatingReadNode && !((FloatingReadNode) node).location().getLocationIdentity().isImmutable();
12772
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
469 if (scheduleRead) {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
470 FloatingReadNode read = (FloatingReadNode) node;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
471 block = optimalBlock(read, strategy);
14873
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
472 Debug.log("schedule for %s: %s", read, block);
16013
dd5c15b85f78 Move dominates() and isDominatedBy() from Block to AbstractBlock and make them static methods.
Josef Eisl <josef.eisl@jku.at>
parents: 15782
diff changeset
473 assert dominates(earliestBlock, block) : String.format("%s (%s) cannot be scheduled before earliest schedule (%s). location: %s", read, block, earliestBlock,
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
474 read.getLocationIdentity());
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
475 } else {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
476 block = latestBlock(node, strategy);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
477 }
12772
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
478 if (block == null) {
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
479 // handle nodes without usages
12772
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
480 block = earliestBlock;
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
481 } else if (strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS && !(node instanceof VirtualObjectNode)) {
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
482 // schedule at the latest position possible in the outermost loop possible
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
483 latest = block;
12772
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
484 block = scheduleOutOfLoops(node, block, earliestBlock);
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
485 }
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
486
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
487 if (assertionEnabled()) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
488 if (scheduleRead) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
489 FloatingReadNode read = (FloatingReadNode) node;
13153
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
490 MemoryNode lastLocationAccess = read.getLastLocationAccess();
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
491 Block upperBound = blockForMemoryNode(lastLocationAccess);
16013
dd5c15b85f78 Move dominates() and isDominatedBy() from Block to AbstractBlock and make them static methods.
Josef Eisl <josef.eisl@jku.at>
parents: 15782
diff changeset
492 assert dominates(upperBound, block) : String.format(
13153
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
493 "out of loop movement voilated memory semantics for %s (location %s). moved to %s but upper bound is %s (earliest: %s, latest: %s)", read,
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
494 read.getLocationIdentity(), block, upperBound, earliestBlock, latest);
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
495 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
496 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
497 break;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
498 default:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
499 throw new GraalInternalError("unknown scheduling strategy");
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
500 }
16013
dd5c15b85f78 Move dominates() and isDominatedBy() from Block to AbstractBlock and make them static methods.
Josef Eisl <josef.eisl@jku.at>
parents: 15782
diff changeset
501 if (!dominates(earliestBlock, block)) {
18969
14496953435e Use Node#getUsageCount wherever possible.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18965
diff changeset
502 throw new SchedulingError("%s: Graph cannot be scheduled : inconsistent for %s, %d usages, (%s needs to dominate %s)", node.graph(), node, node.getUsageCount(), earliestBlock, block);
11865
3d97040060d4 SchedulePhase: bail out with SchedulingError if scheduled block is not dominated by earliest
Bernhard Urban <bernhard.urban@jku.at>
parents: 11864
diff changeset
503 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
504 cfg.getNodeToBlock().set(node, block);
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
505 blockToNodesMap.get(block).add(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
506 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
507
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
508 @SuppressWarnings("all")
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
509 private static boolean assertionEnabled() {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
510 boolean enabled = false;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
511 assert enabled = true;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
512 return enabled;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
513 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
514
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
515 /**
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
516 * this method tries to find the "optimal" schedule for a read, by pushing it down towards its
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
517 * latest schedule starting by the earliest schedule. By doing this, it takes care of memory
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
518 * dependencies using kill sets.
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
519 *
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
520 * In terms of domination relation, it looks like this:
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
521 *
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
522 * <pre>
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
523 * U upperbound block, defined by last access location of the floating read
14906
f3a5036cc13c javadoc fixes
Bernhard Urban <bernhard.urban@jku.at>
parents: 14873
diff changeset
524 * &and;
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
525 * E earliest block
14906
f3a5036cc13c javadoc fixes
Bernhard Urban <bernhard.urban@jku.at>
parents: 14873
diff changeset
526 * &and;
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
527 * O optimal block, first block that contains a kill of the read's location
14906
f3a5036cc13c javadoc fixes
Bernhard Urban <bernhard.urban@jku.at>
parents: 14873
diff changeset
528 * &and;
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
529 * L latest block
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
530 * </pre>
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
531 *
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
532 * i.e. <code>upperbound `dom` earliest `dom` optimal `dom` latest</code>.
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
533 *
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
534 */
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
535 private Block optimalBlock(FloatingReadNode n, SchedulingStrategy strategy) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
536 LocationIdentity locid = n.location().getLocationIdentity();
18231
70df63b02309 Use LocationIdentity.isImmutable instead of testing against FINAL_LOCATION
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 17365
diff changeset
537 assert !locid.isImmutable();
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
538
13153
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
539 Block upperBoundBlock = blockForMemoryNode(n.getLastLocationAccess());
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
540 Block earliestBlock = earliestBlock(n);
16013
dd5c15b85f78 Move dominates() and isDominatedBy() from Block to AbstractBlock and make them static methods.
Josef Eisl <josef.eisl@jku.at>
parents: 15782
diff changeset
541 assert dominates(upperBoundBlock, earliestBlock) : "upper bound (" + upperBoundBlock + ") should dominate earliest (" + earliestBlock + ")";
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
542
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
543 Block latestBlock = latestBlock(n, strategy);
16013
dd5c15b85f78 Move dominates() and isDominatedBy() from Block to AbstractBlock and make them static methods.
Josef Eisl <josef.eisl@jku.at>
parents: 15782
diff changeset
544 assert latestBlock != null && dominates(earliestBlock, latestBlock) : "earliest (" + earliestBlock + ") should dominate latest block (" + latestBlock + ")";
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
545
14873
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
546 Debug.log("processing %s (accessing %s): latest %s, earliest %s, upper bound %s (%s)", n, locid, latestBlock, earliestBlock, upperBoundBlock, n.getLastLocationAccess());
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
547 if (earliestBlock == latestBlock) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
548 // read is fixed to this block, nothing to schedule
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
549 return latestBlock;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
550 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
551
13599
29b1b216d20a SchedulePhase: use {Queue,Deque}/LinkedList instead of Stack
Bernhard Urban <bernhard.urban@jku.at>
parents: 13370
diff changeset
552 Deque<Block> path = computePathInDominatorTree(earliestBlock, latestBlock);
14873
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
553 Debug.log("|path| is %d: %s", path.size(), path);
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
554
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
555 // follow path, start at earliest schedule
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
556 while (path.size() > 0) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
557 Block currentBlock = path.pop();
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
558 Block dominatedBlock = path.size() == 0 ? null : path.peek();
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
559 if (dominatedBlock != null && !currentBlock.getSuccessors().contains(dominatedBlock)) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
560 // the dominated block is not a successor -> we have a split
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
561 assert dominatedBlock.getBeginNode() instanceof AbstractMergeNode;
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
562
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
563 NewMemoryScheduleClosure closure = null;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
564 if (currentBlock == upperBoundBlock) {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
565 assert earliestBlock == upperBoundBlock;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
566 // don't treat lastLocationAccess node as a kill for this read.
13153
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
567 closure = new NewMemoryScheduleClosure(ValueNodeUtil.asNode(n.getLastLocationAccess()), upperBoundBlock);
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
568 } else {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
569 closure = new NewMemoryScheduleClosure();
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
570 }
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
571 Map<FixedNode, LocationSet> states;
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
572 states = ReentrantBlockIterator.apply(closure, currentBlock, new LocationSet(), block -> block == dominatedBlock);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
573
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
574 LocationSet mergeState = states.get(dominatedBlock.getBeginNode());
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
575 if (mergeState.contains(locid)) {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
576 // location got killed somewhere in the branches,
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
577 // thus we've to move the read above it
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
578 return currentBlock;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
579 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
580 } else {
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
581 if (currentBlock == upperBoundBlock) {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
582 assert earliestBlock == upperBoundBlock;
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
583 LocationSet ks = computeKillSet(upperBoundBlock, ValueNodeUtil.asNode(n.getLastLocationAccess()));
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
584 if (ks.contains(locid)) {
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
585 return upperBoundBlock;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
586 }
18992
b1c03c2bfa40 Rename KillSet to LocationSet, make it more efficient, and fix a bug related to ANY_LOCATION.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18974
diff changeset
587 } else if (dominatedBlock == null || computeKillSet(currentBlock).contains(locid)) {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
588 return currentBlock;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
589 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
590 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
591 }
13370
3e67710a6d08 SchedulePhase: remove old memory aware scheudling
Bernhard Urban <bernhard.urban@jku.at>
parents: 13369
diff changeset
592 throw new SchedulingError("should have found a block for " + n);
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
593 }
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
594
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
595 /**
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
596 * compute path in dominator tree from earliest schedule to latest schedule.
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
597 *
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
598 * @return the order of the stack is such as the first element is the earliest schedule.
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
599 */
13599
29b1b216d20a SchedulePhase: use {Queue,Deque}/LinkedList instead of Stack
Bernhard Urban <bernhard.urban@jku.at>
parents: 13370
diff changeset
600 private static Deque<Block> computePathInDominatorTree(Block earliestBlock, Block latestBlock) {
29b1b216d20a SchedulePhase: use {Queue,Deque}/LinkedList instead of Stack
Bernhard Urban <bernhard.urban@jku.at>
parents: 13370
diff changeset
601 Deque<Block> path = new LinkedList<>();
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
602 Block currentBlock = latestBlock;
16013
dd5c15b85f78 Move dominates() and isDominatedBy() from Block to AbstractBlock and make them static methods.
Josef Eisl <josef.eisl@jku.at>
parents: 15782
diff changeset
603 while (currentBlock != null && dominates(earliestBlock, currentBlock)) {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
604 path.push(currentBlock);
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
605 currentBlock = currentBlock.getDominator();
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
606 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
607 assert path.peek() == earliestBlock;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
608 return path;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
609 }
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
610
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
611 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
612 * Calculates the last block that the given node could be scheduled in, i.e., the common
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
613 * dominator of all usages. To do so all usages are also assigned to blocks.
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
614 *
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
615 * @param strategy
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
616 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
617 private Block latestBlock(ValueNode node, SchedulingStrategy strategy) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
618 CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(null);
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
619 for (Node succ : node.successors().nonNull()) {
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
620 if (cfg.getNodeToBlock().get(succ) == null) {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
621 throw new SchedulingError();
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
622 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
623 cdbc.apply(cfg.getNodeToBlock().get(succ));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
624 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
625 ensureScheduledUsages(node, strategy);
17064
3c54a098455f removed Node.recordsUsages()
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
626 for (Node usage : node.usages()) {
3c54a098455f removed Node.recordsUsages()
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
627 blocksForUsage(node, usage, cdbc, strategy);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
628 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
629
13298
5a3491b0c2f0 convert assertion in SchedulePhase to raise SchedulingError instead of AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 13153
diff changeset
630 if (assertionEnabled()) {
16013
dd5c15b85f78 Move dominates() and isDominatedBy() from Block to AbstractBlock and make them static methods.
Josef Eisl <josef.eisl@jku.at>
parents: 15782
diff changeset
631 if (cdbc.block != null && !dominates(earliestBlock(node), cdbc.block)) {
13298
5a3491b0c2f0 convert assertion in SchedulePhase to raise SchedulingError instead of AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 13153
diff changeset
632 throw new SchedulingError("failed to find correct latest schedule for %s. cdbc: %s, earliest: %s", node, cdbc.block, earliestBlock(node));
5a3491b0c2f0 convert assertion in SchedulePhase to raise SchedulingError instead of AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 13153
diff changeset
633 }
5a3491b0c2f0 convert assertion in SchedulePhase to raise SchedulingError instead of AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 13153
diff changeset
634 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
635 return cdbc.block;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
636 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
637
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
638 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
639 * A closure that will calculate the common dominator of all blocks passed to its
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
640 * {@link #apply(Block)} method.
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
641 */
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
642 private static class CommonDominatorBlockClosure implements BlockClosure {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
643
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
644 public Block block;
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
645
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
646 public CommonDominatorBlockClosure(Block block) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
647 this.block = block;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
648 }
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
649
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
650 @Override
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
651 public void apply(Block newBlock) {
16503
b3800429f543 Move commonDominator to AbstractControlFlowGraph.
Josef Eisl <josef.eisl@jku.at>
parents: 16443
diff changeset
652 this.block = commonDominatorTyped(this.block, newBlock);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
653 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
654 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
655
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
656 /**
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
657 * Determines the earliest block in which the given node can be scheduled.
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
658 */
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
659 private Block earliestBlock(Node node) {
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
660 Block earliest = cfg.getNodeToBlock().get(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
661 if (earliest != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
662 return earliest;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
663 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
664 earliest = earliestCache.get(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
665 if (earliest != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
666 return earliest;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
667 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
668 /*
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
669 * All inputs must be in a dominating block, otherwise the graph cannot be scheduled. This
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
670 * implies that the inputs' blocks have a total ordering via their dominance relation. So in
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
671 * order to find the earliest block placement for this node we need to find the input block
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
672 * that is dominated by all other input blocks.
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
673 */
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
674
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
675 if (node.predecessor() != null) {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
676 throw new SchedulingError();
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
677 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
678 for (Node input : node.inputs().nonNull()) {
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
679 assert input instanceof ValueNode;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
680 Block inputEarliest;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
681 if (input instanceof InvokeWithExceptionNode) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
682 inputEarliest = cfg.getNodeToBlock().get(((InvokeWithExceptionNode) input).next());
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
683 } else {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
684 inputEarliest = earliestBlock(input);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
685 }
15173
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
686 if (earliest == null) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
687 earliest = inputEarliest;
15173
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
688 } else if (earliest != inputEarliest) {
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
689 // Find out whether earliest or inputEarliest is earlier.
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
690 Block a = earliest.getDominator();
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
691 Block b = inputEarliest;
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
692 while (true) {
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
693 if (a == inputEarliest || b == null) {
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
694 // Nothing to change, the previous earliest block is still earliest.
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
695 break;
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
696 } else if (b == earliest || a == null) {
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
697 // New earliest is the earliest.
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
698 earliest = inputEarliest;
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
699 break;
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
700 }
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
701 a = a.getDominator();
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
702 b = b.getDominator();
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
703 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
704 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
705 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
706 if (earliest == null) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
707 earliest = cfg.getStartBlock();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
708 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
709 earliestCache.set(node, earliest);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
710 return earliest;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
711 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
712
12772
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
713 /**
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
714 * Schedules a node out of loop based on its earliest schedule. Note that this movement is only
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
715 * valid if it's done for <b>every</b> other node in the schedule, otherwise this movement is
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
716 * not valid.
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
717 *
12772
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
718 * @param n Node to schedule
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
719 * @param latestBlock latest possible schedule for {@code n}
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
720 * @param earliest earliest possible schedule for {@code n}
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
721 * @return block schedule for {@code n} which is not inside a loop (if possible)
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
722 */
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
723 private static Block scheduleOutOfLoops(Node n, Block latestBlock, Block earliest) {
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
724 if (latestBlock == null) {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
725 throw new SchedulingError("no latest : %s", n);
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
726 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
727 Block cur = latestBlock;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
728 Block result = latestBlock;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
729 while (cur.getLoop() != null && cur != earliest && cur.getDominator() != null) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
730 Block dom = cur.getDominator();
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
731 if (dom.getLoopDepth() < result.getLoopDepth()) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
732 result = dom;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
733 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
734 cur = dom;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
735 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
736 return result;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
737 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
738
5583
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
739 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
740 * Passes all blocks that a specific usage of a node is in to a given closure. This is more
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
741 * complex than just taking the usage's block because of of PhiNodes and FrameStates.
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
742 *
5583
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
743 * @param node the node that needs to be scheduled
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
744 * @param usage the usage whose blocks need to be considered
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
745 * @param closure the closure that will be called for each block
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
746 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
747 private void blocksForUsage(ValueNode node, Node usage, BlockClosure closure, SchedulingStrategy strategy) {
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
748 if (node instanceof PhiNode) {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
749 throw new SchedulingError(node.toString());
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
750 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
751
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
752 if (usage instanceof PhiNode) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
753 // An input to a PhiNode is used at the end of the predecessor block that corresponds to
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
754 // the PhiNode input.
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
755 // One PhiNode can use an input multiple times, the closure will be called for each
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
756 // usage.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
757 PhiNode phi = (PhiNode) usage;
18995
a2cb19764970 Rename MergeNode to AbstractMergeNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18993
diff changeset
758 AbstractMergeNode merge = phi.merge();
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
759 Block mergeBlock = cfg.getNodeToBlock().get(merge);
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
760 if (mergeBlock == null) {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
761 throw new SchedulingError("no block for merge %s", merge.toString(Verbosity.Id));
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
762 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
763 for (int i = 0; i < phi.valueCount(); ++i) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
764 if (phi.valueAt(i) == node) {
7499
ca3e5df0e6cf Small clean up of access to predecessor/successor of blocks.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 6670
diff changeset
765 if (mergeBlock.getPredecessorCount() <= i) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
766 TTY.println(merge.toString());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
767 TTY.println(phi.toString());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
768 TTY.println(merge.cfgPredecessors().toString());
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4525
diff changeset
769 TTY.println(mergeBlock.getPredecessors().toString());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
770 TTY.println(phi.inputs().toString());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
771 TTY.println("value count: " + phi.valueCount());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
772 }
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4525
diff changeset
773 closure.apply(mergeBlock.getPredecessors().get(i));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
774 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
775 }
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
776 } else if (usage instanceof VirtualState) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
777 // The following logic does not work if node is a PhiNode, but this method is never
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
778 // called for PhiNodes.
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
779 for (Node unscheduledUsage : usage.usages()) {
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
780 if (unscheduledUsage instanceof VirtualState) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
781 // If a FrameState is an outer FrameState this method behaves as if the inner
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
782 // FrameState was the actual usage, by recursing.
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
783 blocksForUsage(node, unscheduledUsage, closure, strategy);
18993
480bd3b1adcd Rename BeginNode => AbstractBeginNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18992
diff changeset
784 } else if (unscheduledUsage instanceof AbstractBeginNode) {
11460
ac2bddbe3b51 SchedulePhase: schedule inputs of framestates which are attached to AbstractBeginNodes to the dominator (not just for MergeNodes)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10925
diff changeset
785 // Only FrameStates can be connected to BeginNodes.
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
786 if (!(usage instanceof FrameState)) {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
787 throw new SchedulingError(usage.toString());
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
788 }
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
789 if (unscheduledUsage instanceof StartNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
790 closure.apply(cfg.getNodeToBlock().get(unscheduledUsage));
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
791 } else {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
792 // If a FrameState belongs to a BeginNode then it's inputs will be placed at
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
793 // the common dominator of all EndNodes.
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
794 for (Node pred : unscheduledUsage.cfgPredecessors()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
795 closure.apply(cfg.getNodeToBlock().get(pred));
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
796 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
797 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
798 } else {
13293
5215f94f94ec GRAAL-632: Clarify difference between states managed by StateSplit and DeoptimizingNode
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 13153
diff changeset
799 // For the time being, FrameStates can only be connected to NodeWithState.
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
800 if (!(usage instanceof FrameState)) {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
801 throw new SchedulingError(usage.toString());
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
802 }
11787
4fc75b6ca3dd Introduce NodeWithState for nodes that hold some VirtualState. Use this interface in the required special cases (Scheduling and PEA)
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 11501
diff changeset
803 if (!(unscheduledUsage instanceof NodeWithState)) {
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
804 throw new SchedulingError(unscheduledUsage.toString());
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
805 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
806 // Otherwise: Put the input into the same block as the usage.
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
807 assignBlockToNode((ValueNode) unscheduledUsage, strategy);
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
808 closure.apply(cfg.getNodeToBlock().get(unscheduledUsage));
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
809 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
810 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
811 } else {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
812 // All other types of usages: Put the input into the same block as the usage.
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
813 assignBlockToNode((ValueNode) usage, strategy);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
814 closure.apply(cfg.getNodeToBlock().get(usage));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
815 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
816 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
817
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
818 private void ensureScheduledUsages(Node node, SchedulingStrategy strategy) {
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
819 for (Node usage : node.usages().filter(ValueNode.class)) {
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
820 assignBlockToNode((ValueNode) usage, strategy);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
821 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
822 // now true usages are ready
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
823 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
824
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
825 private void sortNodesWithinBlocks(StructuredGraph graph, SchedulingStrategy strategy) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
826 NodeBitMap visited = graph.createNodeBitMap();
10921
b73121a215f7 NewMemoryAwareScheduling: create nodebitmap once per graph (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10920
diff changeset
827 NodeBitMap beforeLastLocation = graph.createNodeBitMap();
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
828 for (Block b : cfg.getBlocks()) {
10921
b73121a215f7 NewMemoryAwareScheduling: create nodebitmap once per graph (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10920
diff changeset
829 sortNodesWithinBlock(b, visited, beforeLastLocation, strategy);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
830 assert noDuplicatedNodesInBlock(b) : "duplicated nodes in " + b;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
831 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
832 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
833
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
834 private boolean noDuplicatedNodesInBlock(Block b) {
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
835 List<ValueNode> list = blockToNodesMap.get(b);
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
836 Set<ValueNode> hashset = Node.newSet(list);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
837 return list.size() == hashset.size();
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
838 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
839
10921
b73121a215f7 NewMemoryAwareScheduling: create nodebitmap once per graph (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10920
diff changeset
840 private void sortNodesWithinBlock(Block b, NodeBitMap visited, NodeBitMap beforeLastLocation, SchedulingStrategy strategy) {
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
841 if (visited.isMarked(b.getBeginNode()) || cfg.blockFor(b.getBeginNode()) != b) {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
842 throw new SchedulingError();
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
843 }
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
844 if (visited.isMarked(b.getEndNode()) || cfg.blockFor(b.getEndNode()) != b) {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
845 throw new SchedulingError();
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
846 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
847
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
848 List<ValueNode> sortedInstructions;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
849 switch (strategy) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
850 case EARLIEST:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
851 sortedInstructions = sortNodesWithinBlockEarliest(b, visited);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
852 break;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
853 case LATEST:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
854 case LATEST_OUT_OF_LOOPS:
10921
b73121a215f7 NewMemoryAwareScheduling: create nodebitmap once per graph (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10920
diff changeset
855 sortedInstructions = sortNodesWithinBlockLatest(b, visited, beforeLastLocation);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
856 break;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
857 default:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
858 throw new GraalInternalError("unknown scheduling strategy");
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
859 }
10922
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
860 assert filterSchedulableNodes(blockToNodesMap.get(b)).size() == removeProxies(sortedInstructions).size() : "sorted block does not contain the same amount of nodes: " +
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
861 filterSchedulableNodes(blockToNodesMap.get(b)) + " vs. " + removeProxies(sortedInstructions);
10890
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
862 assert sameOrderForFixedNodes(blockToNodesMap.get(b), sortedInstructions) : "fixed nodes in sorted block are not in the same order";
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
863 blockToNodesMap.put(b, sortedInstructions);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
864 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
865
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
866 private static List<ValueNode> removeProxies(List<ValueNode> list) {
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
867 List<ValueNode> result = new ArrayList<>();
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
868 for (ValueNode n : list) {
10922
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
869 if (!(n instanceof ProxyNode)) {
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
870 result.add(n);
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
871 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
872 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
873 return result;
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
874 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
875
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
876 private static List<ValueNode> filterSchedulableNodes(List<ValueNode> list) {
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
877 List<ValueNode> result = new ArrayList<>();
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
878 for (ValueNode n : list) {
11501
a116fb4875a6 SchedulePhase: remove special handling of localnodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 11460
diff changeset
879 if (!(n instanceof PhiNode)) {
10922
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
880 result.add(n);
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
881 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
882 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
883 return result;
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
884 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
885
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
886 private static boolean sameOrderForFixedNodes(List<ValueNode> fixed, List<ValueNode> sorted) {
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
887 Iterator<ValueNode> fixedIterator = fixed.iterator();
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
888 Iterator<ValueNode> sortedIterator = sorted.iterator();
10890
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
889
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
890 while (sortedIterator.hasNext()) {
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
891 ValueNode sortedCurrent = sortedIterator.next();
10890
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
892 if (sortedCurrent instanceof FixedNode) {
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
893 if (!(fixedIterator.hasNext() && fixedIterator.next() == sortedCurrent)) {
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
894 return false;
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
895 }
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
896 }
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
897 }
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
898
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
899 while (fixedIterator.hasNext()) {
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
900 if (fixedIterator.next() instanceof FixedNode) {
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
901 return false;
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
902 }
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
903 }
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
904
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
905 return true;
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
906 }
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
907
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
908 private static class SortState {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
909 private Block block;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
910 private NodeBitMap visited;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
911 private NodeBitMap beforeLastLocation;
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
912 private List<ValueNode> sortedInstructions;
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
913 private List<FloatingReadNode> reads;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
914
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
915 SortState(Block block, NodeBitMap visited, NodeBitMap beforeLastLocation, List<ValueNode> sortedInstructions) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
916 this.block = block;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
917 this.visited = visited;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
918 this.beforeLastLocation = beforeLastLocation;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
919 this.sortedInstructions = sortedInstructions;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
920 this.reads = null;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
921 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
922
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
923 public Block currentBlock() {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
924 return block;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
925 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
926
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
927 void markVisited(Node n) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
928 visited.mark(n);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
929 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
930
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
931 boolean isVisited(Node n) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
932 return visited.isMarked(n);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
933 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
934
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
935 void markBeforeLastLocation(FloatingReadNode n) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
936 beforeLastLocation.mark(n);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
937 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
938
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
939 void clearBeforeLastLocation(FloatingReadNode frn) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
940 beforeLastLocation.clear(frn);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
941 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
942
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
943 boolean isBeforeLastLocation(FloatingReadNode n) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
944 return beforeLastLocation.isMarked(n);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
945 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
946
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
947 void addRead(FloatingReadNode n) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
948 if (reads == null) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
949 reads = new ArrayList<>();
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
950 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
951 reads.add(n);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
952 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
953
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
954 int readsSize() {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
955 if (reads == null) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
956 return 0;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
957 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
958 return reads.size();
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
959 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
960
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
961 void removeRead(ValueNode i) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
962 assert reads != null;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
963 reads.remove(i);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
964 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
965
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
966 List<FloatingReadNode> readsSnapshot() {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
967 assert reads != null;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
968 return new ArrayList<>(reads);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
969 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
970
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
971 List<ValueNode> getSortedInstructions() {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
972 return sortedInstructions;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
973 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
974
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
975 boolean containsInstruction(ValueNode i) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
976 return sortedInstructions.contains(i);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
977 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
978
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
979 void addInstruction(ValueNode i) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
980 sortedInstructions.add(i);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
981 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
982 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
983
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
984 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
985 * Sorts the nodes within a block by adding the nodes to a list in a post-order iteration over
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
986 * all inputs. This means that a node is added to the list after all its inputs have been
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
987 * processed.
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
988 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
989 private List<ValueNode> sortNodesWithinBlockLatest(Block b, NodeBitMap visited, NodeBitMap beforeLastLocation) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
990 SortState state = new SortState(b, visited, beforeLastLocation, new ArrayList<>(blockToNodesMap.get(b).size() + 2));
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
991 List<ValueNode> instructions = blockToNodesMap.get(b);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
992
18965
53fcb13db742 Always use read aware memory scheduling.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18955
diff changeset
993 for (ValueNode i : instructions) {
53fcb13db742 Always use read aware memory scheduling.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18955
diff changeset
994 if (i instanceof FloatingReadNode) {
53fcb13db742 Always use read aware memory scheduling.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18955
diff changeset
995 FloatingReadNode frn = (FloatingReadNode) i;
53fcb13db742 Always use read aware memory scheduling.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18955
diff changeset
996 if (!frn.location().getLocationIdentity().isImmutable()) {
53fcb13db742 Always use read aware memory scheduling.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18955
diff changeset
997 state.addRead(frn);
53fcb13db742 Always use read aware memory scheduling.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18955
diff changeset
998 if (nodesFor(b).contains(frn.getLastLocationAccess())) {
53fcb13db742 Always use read aware memory scheduling.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18955
diff changeset
999 assert !state.isBeforeLastLocation(frn);
53fcb13db742 Always use read aware memory scheduling.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18955
diff changeset
1000 state.markBeforeLastLocation(frn);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1001 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1002 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1003 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1004 }
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1005
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1006 for (ValueNode i : instructions) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1007 addToLatestSorting(i, state);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1008 }
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1009 assert state.readsSize() == 0 : "not all reads are scheduled";
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1010
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
1011 // Make sure that last node gets really last (i.e. when a frame state successor hangs off
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
1012 // it).
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1013 List<ValueNode> sortedInstructions = state.getSortedInstructions();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1014 Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
1015 if (lastSorted != b.getEndNode()) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
1016 int idx = sortedInstructions.indexOf(b.getEndNode());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1017 boolean canNotMove = false;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1018 for (int i = idx + 1; i < sortedInstructions.size(); i++) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
1019 if (sortedInstructions.get(i).inputs().contains(b.getEndNode())) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1020 canNotMove = true;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1021 break;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1022 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1023 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1024 if (canNotMove) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
1025 if (b.getEndNode() instanceof ControlSplitNode) {
15193
96bb07a5d667 Spit up and move GraalInternalError.
Josef Eisl <josef.eisl@jku.at>
parents: 15192
diff changeset
1026 throw new GraalGraphInternalError("Schedule is not possible : needs to move a node after the last node of the block which can not be move").addContext(lastSorted).addContext(
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
1027 b.getEndNode());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1028 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1029
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
1030 // b.setLastNode(lastSorted);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1031 } else {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
1032 sortedInstructions.remove(b.getEndNode());
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
1033 sortedInstructions.add(b.getEndNode());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1034 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1035 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1036 return sortedInstructions;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1037 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1038
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1039 private void processKillLocation(Node node, LocationIdentity identity, SortState state) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1040 for (FloatingReadNode frn : state.readsSnapshot()) {
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1041 LocationIdentity readLocation = frn.location().getLocationIdentity();
18231
70df63b02309 Use LocationIdentity.isImmutable instead of testing against FINAL_LOCATION
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 17365
diff changeset
1042 assert !readLocation.isImmutable();
12722
b87c2f34e0e0 Maintain lastLocationAccess in WriteNode.
Roland Schatz <roland.schatz@oracle.com>
parents: 12721
diff changeset
1043 if (frn.getLastLocationAccess() == node) {
18583
12bd2b344b08 replace usages of == with .equals()
Doug Simon <doug.simon@oracle.com>
parents: 18383
diff changeset
1044 assert identity.equals(ANY_LOCATION) || readLocation.equals(identity) || node instanceof MemoryCheckpoint.Multi : "location doesn't match: " + readLocation + ", " + identity;
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1045 state.clearBeforeLastLocation(frn);
18583
12bd2b344b08 replace usages of == with .equals()
Doug Simon <doug.simon@oracle.com>
parents: 18383
diff changeset
1046 } else if (!state.isBeforeLastLocation(frn) && (readLocation.equals(identity) || (node != getCFG().graph.start() && ANY_LOCATION.equals(identity)))) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1047 state.removeRead(frn);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1048 addToLatestSorting(frn, state);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1049 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1050 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1051 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1052
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1053 private void addUnscheduledToLatestSorting(VirtualState state, SortState sortState) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1054 if (state != null) {
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
1055 // UnscheduledNodes should never be marked as visited.
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1056 if (sortState.isVisited(state)) {
8950
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
1057 throw new SchedulingError();
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
1058 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1059
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1060 for (Node input : state.inputs()) {
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
1061 if (input instanceof VirtualState) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1062 addUnscheduledToLatestSorting((VirtualState) input, sortState);
13327
c258331fdde6 removed support for external nodes (GRAAL-508)
Doug Simon <doug.simon@oracle.com>
parents: 13299
diff changeset
1063 } else {
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1064 addToLatestSorting((ValueNode) input, sortState);
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1065 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1066 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1067 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1068 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1069
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1070 private void addToLatestSorting(ValueNode i, SortState state) {
19048
b300d1f6e817 schedule inputs of proxy nodes at the loop exit
Lukas Stadler <lukas.stadler@oracle.com>
parents: 19007
diff changeset
1071 if (i == null || state.isVisited(i) || cfg.getNodeToBlock().get(i) != state.currentBlock() || i instanceof PhiNode) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1072 return;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1073 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1074
14734
6ae9af961b7c Introduce separate interfaces for deoptimizing nodes that deopt to a state before, during or after their execution.
Roland Schatz <roland.schatz@oracle.com>
parents: 14534
diff changeset
1075 FrameState stateAfter = null;
6ae9af961b7c Introduce separate interfaces for deoptimizing nodes that deopt to a state before, during or after their execution.
Roland Schatz <roland.schatz@oracle.com>
parents: 14534
diff changeset
1076 if (i instanceof StateSplit) {
6ae9af961b7c Introduce separate interfaces for deoptimizing nodes that deopt to a state before, during or after their execution.
Roland Schatz <roland.schatz@oracle.com>
parents: 14534
diff changeset
1077 stateAfter = ((StateSplit) i).stateAfter();
6ae9af961b7c Introduce separate interfaces for deoptimizing nodes that deopt to a state before, during or after their execution.
Roland Schatz <roland.schatz@oracle.com>
parents: 14534
diff changeset
1078 }
6ae9af961b7c Introduce separate interfaces for deoptimizing nodes that deopt to a state before, during or after their execution.
Roland Schatz <roland.schatz@oracle.com>
parents: 14534
diff changeset
1079
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1080 for (Node input : i.inputs()) {
10891
8c0ab217ed00 Scheduling: remove dead code in addToLatestSorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10890
diff changeset
1081 if (input instanceof FrameState) {
14734
6ae9af961b7c Introduce separate interfaces for deoptimizing nodes that deopt to a state before, during or after their execution.
Roland Schatz <roland.schatz@oracle.com>
parents: 14534
diff changeset
1082 if (input != stateAfter) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1083 addUnscheduledToLatestSorting((FrameState) input, state);
14734
6ae9af961b7c Introduce separate interfaces for deoptimizing nodes that deopt to a state before, during or after their execution.
Roland Schatz <roland.schatz@oracle.com>
parents: 14534
diff changeset
1084 }
13327
c258331fdde6 removed support for external nodes (GRAAL-508)
Doug Simon <doug.simon@oracle.com>
parents: 13299
diff changeset
1085 } else {
19007
84bf57a0ddcb Remove ValueProxy nodes from schedule lists.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19002
diff changeset
1086 addToLatestSorting((ValueNode) input, state);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1087 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1088 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1089
19048
b300d1f6e817 schedule inputs of proxy nodes at the loop exit
Lukas Stadler <lukas.stadler@oracle.com>
parents: 19007
diff changeset
1090 if (i instanceof ProxyNode) {
b300d1f6e817 schedule inputs of proxy nodes at the loop exit
Lukas Stadler <lukas.stadler@oracle.com>
parents: 19007
diff changeset
1091 return;
b300d1f6e817 schedule inputs of proxy nodes at the loop exit
Lukas Stadler <lukas.stadler@oracle.com>
parents: 19007
diff changeset
1092 }
b300d1f6e817 schedule inputs of proxy nodes at the loop exit
Lukas Stadler <lukas.stadler@oracle.com>
parents: 19007
diff changeset
1093
18965
53fcb13db742 Always use read aware memory scheduling.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18955
diff changeset
1094 if (state.readsSize() != 0) {
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1095 if (i instanceof MemoryCheckpoint.Single) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1096 LocationIdentity identity = ((MemoryCheckpoint.Single) i).getLocationIdentity();
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1097 processKillLocation(i, identity, state);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1098 } else if (i instanceof MemoryCheckpoint.Multi) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1099 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) i).getLocationIdentities()) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1100 processKillLocation(i, identity, state);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1101 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1102 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1103 assert MemoryCheckpoint.TypeAssertion.correctType(i);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1104 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1105
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1106 addToLatestSorting((ValueNode) i.predecessor(), state);
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1107 state.markVisited(i);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1108 addUnscheduledToLatestSorting(stateAfter, state);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1109
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1110 // Now predecessors and inputs are scheduled => we can add this node.
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1111 if (!state.containsInstruction(i)) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1112 state.addInstruction(i);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1113 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1114
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1115 if (state.readsSize() != 0 && i instanceof FloatingReadNode) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1116 state.removeRead(i);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1117 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1118 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1119
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1120 /**
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1121 * Sorts the nodes within a block by adding the nodes to a list in a post-order iteration over
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1122 * all usages. The resulting list is reversed to create an earliest-possible scheduling of
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1123 * nodes.
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1124 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1125 private List<ValueNode> sortNodesWithinBlockEarliest(Block b, NodeBitMap visited) {
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1126 List<ValueNode> sortedInstructions = new ArrayList<>(blockToNodesMap.get(b).size() + 2);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1127 addToEarliestSorting(b, b.getEndNode(), sortedInstructions, visited);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1128 Collections.reverse(sortedInstructions);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1129 return sortedInstructions;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1130 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1131
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1132 private void addToEarliestSorting(Block b, ValueNode i, List<ValueNode> sortedInstructions, NodeBitMap visited) {
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1133 ValueNode instruction = i;
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1134 while (true) {
19007
84bf57a0ddcb Remove ValueProxy nodes from schedule lists.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19002
diff changeset
1135 if (instruction == null || visited.isMarked(instruction) || cfg.getNodeToBlock().get(instruction) != b || instruction instanceof PhiNode || instruction instanceof ProxyNode) {
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1136 return;
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1137 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1138
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1139 visited.mark(instruction);
17064
3c54a098455f removed Node.recordsUsages()
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
1140 for (Node usage : instruction.usages()) {
3c54a098455f removed Node.recordsUsages()
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
1141 if (usage instanceof VirtualState) {
3c54a098455f removed Node.recordsUsages()
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
1142 // only fixed nodes can have VirtualState -> no need to schedule them
3c54a098455f removed Node.recordsUsages()
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
1143 } else {
19007
84bf57a0ddcb Remove ValueProxy nodes from schedule lists.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19002
diff changeset
1144 addToEarliestSorting(b, (ValueNode) usage, sortedInstructions, visited);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1145 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1146 }
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1147
18993
480bd3b1adcd Rename BeginNode => AbstractBeginNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18992
diff changeset
1148 if (instruction instanceof AbstractBeginNode) {
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1149 for (ValueNode inBlock : blockToNodesMap.get(b)) {
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1150 if (!visited.isMarked(inBlock)) {
18955
bef8b6316627 Do not add proxy nodes of loop exits to the schedule.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18941
diff changeset
1151 addToEarliestSorting(b, inBlock, sortedInstructions, visited);
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1152 }
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1153 }
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1154 sortedInstructions.add(instruction);
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1155 break;
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1156 } else {
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1157 sortedInstructions.add(instruction);
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1158 instruction = (ValueNode) instruction.predecessor();
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1159 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1160 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1161 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1162 }