Mercurial > hg > truffle

annotate graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java @ 18955:bef8b6316627

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Do not add proxy nodes of loop exits to the schedule.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Mon, 26 Jan 2015 23:30:09 +0100
parents c943ba97b2a7
children 53fcb13db742
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
10894
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
80 public static enum MemoryScheduling {
14908
8db6e76cb658 Formatter: Keep one enum constant per line
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 14906
diff changeset
81 NONE,
8db6e76cb658 Formatter: Keep one enum constant per line
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 14906
diff changeset
82 OPTIMAL
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
83 }
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
84
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
85 private class KillSet implements Iterable<LocationIdentity> {
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
86 private List<LocationIdentity> list;
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
87
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
88 public KillSet() {
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
89 list = null;
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
90 }
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
91
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
92 public KillSet(KillSet other) {
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
93 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
94 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
95 }
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
96 }
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
97
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
98 private void initSet() {
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
99 if (list == null) {
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
100 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
101 }
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
102 }
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
103
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
104 public void add(LocationIdentity locationIdentity) {
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
105 if (list == null || !list.contains(locationIdentity)) {
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
106 initSet();
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
107 list.add(locationIdentity);
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
108 }
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
109 }
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
110
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
111 public void addAll(KillSet other) {
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
112 if (other.list == null) {
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
113 return;
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
114 }
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
115 initSet();
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
116 for (LocationIdentity locationIdentity : other) {
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
117 if (!list.contains(locationIdentity)) {
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
118 list.add(locationIdentity);
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
119 }
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
120 }
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
121 }
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
122
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
123 public Iterator<LocationIdentity> iterator() {
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
124 if (list == null) {
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
125 return Collections.emptyIterator();
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
126 }
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
127 return list.iterator();
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
128 }
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
129
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
130 public boolean isKilled(LocationIdentity locationIdentity) {
15599
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
131 if (list == null) {
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
132 return false;
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
133 }
f0254bab4c6b SchedulePhase: improve KillSet implementation by using a lazy initialized ArrayList
Bernhard Urban <bernhard.urban@jku.at>
parents: 15534
diff changeset
134 return list.contains(locationIdentity);
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
135 }
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
136 }
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 private class NewMemoryScheduleClosure extends BlockIteratorClosure<KillSet> {
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
139 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
140 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
141
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
142 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
143 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
144 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
145 }
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
146
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
147 public NewMemoryScheduleClosure() {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
148 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
149 }
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
150
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
151 @Override
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
152 protected KillSet getInitialState() {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
153 return cloneState(blockToKillSet.get(getCFG().getStartBlock()));
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
154 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
155
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
156 @Override
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
157 protected KillSet processBlock(Block block, KillSet currentState) {
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
158 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
159 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
160 return currentState;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
161 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
162
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
163 @Override
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
164 protected KillSet merge(Block merge, List<KillSet> states) {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
165 assert merge.getBeginNode() instanceof MergeNode;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
166
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
167 KillSet initKillSet = new KillSet();
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
168 for (KillSet state : states) {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
169 initKillSet.addAll(state);
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
170 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
171
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
172 return initKillSet;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
173 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
174
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
175 @Override
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
176 protected KillSet cloneState(KillSet state) {
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
177 return new KillSet(state);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
178 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
179
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
180 @Override
15107
1bf700e19e84 Make Loop generic.
Josef Eisl <josef.eisl@jku.at>
parents: 15008
diff changeset
181 protected List<KillSet> processLoop(Loop<Block> loop, KillSet state) {
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
182 LoopInfo<KillSet> 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
183
15534
4bd6ad45ee0a Encapsulate members of Loop.
Josef Eisl <josef.eisl@jku.at>
parents: 15423
diff changeset
184 assert loop.getHeader().getBeginNode() instanceof LoopBeginNode;
4bd6ad45ee0a Encapsulate members of Loop.
Josef Eisl <josef.eisl@jku.at>
parents: 15423
diff changeset
185 KillSet headerState = merge(loop.getHeader(), info.endStates);
11863
7763a42d1658 NewMemoryAwareScheduling: handle MemoryPhis properly
Bernhard Urban <bernhard.urban@jku.at>
parents: 11787
diff changeset
186
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
187 // 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
188 info = ReentrantBlockIterator.processLoop(this, loop, cloneState(headerState));
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 return info.exitStates;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
191 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
192 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
193
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
194 /**
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
195 * 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
196 *
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
197 * assumptions: {@link MemoryCheckpoint MemoryCheckPoints} are {@link FixedNode FixedNodes}.
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
198 *
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
199 * @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
200 * @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
201 * until we reach excludeNode.
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
202 * @return all killed locations
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
203 */
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
204 private KillSet computeKillSet(Block block, Node excludeNode) {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
205 // 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
206 if (excludeNode == null) {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
207 KillSet cachedSet = blockToKillSet.get(block);
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
208 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
209 return cachedSet;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
210 }
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
211 }
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
212
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
213 // 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
214 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
215
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
216 KillSet set = new KillSet();
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
217 KillSet excludedLocations = new KillSet();
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
218 if (block.getBeginNode() instanceof MergeNode) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
219 MergeNode mergeNode = (MergeNode) block.getBeginNode();
13152
640516a8ca6b Separate class for MemoryProxy and MemoryPhi.
Roland Schatz <roland.schatz@oracle.com>
parents: 13092
diff changeset
220 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
221 if (foundExcludeNode) {
640516a8ca6b Separate class for MemoryProxy and MemoryPhi.
Roland Schatz <roland.schatz@oracle.com>
parents: 13092
diff changeset
222 set.add(phi.getLocationIdentity());
640516a8ca6b Separate class for MemoryProxy and MemoryPhi.
Roland Schatz <roland.schatz@oracle.com>
parents: 13092
diff changeset
223 } else {
640516a8ca6b Separate class for MemoryProxy and MemoryPhi.
Roland Schatz <roland.schatz@oracle.com>
parents: 13092
diff changeset
224 excludedLocations.add(phi.getLocationIdentity());
640516a8ca6b Separate class for MemoryProxy and MemoryPhi.
Roland Schatz <roland.schatz@oracle.com>
parents: 13092
diff changeset
225 foundExcludeNode = phi == excludeNode;
11863
7763a42d1658 NewMemoryAwareScheduling: handle MemoryPhis properly
Bernhard Urban <bernhard.urban@jku.at>
parents: 11787
diff changeset
226 }
7763a42d1658 NewMemoryAwareScheduling: handle MemoryPhis properly
Bernhard Urban <bernhard.urban@jku.at>
parents: 11787
diff changeset
227 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
228 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
229
15145
df2ef5204f2b Remove AbstractBeginNode, move the framestate from AbstractBeginNode to BeginStateSplitNode.
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 15107
diff changeset
230 BeginNode 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
231 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
232
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
233 KillSet accm = foundExcludeNode ? set : excludedLocations;
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
234 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
235 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
236 foundExcludeNode = true;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
237 }
15782
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
238 if (node != startNode) {
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
239 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
240 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
241 accm.add(identity);
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
242 } 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
243 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
244 accm.add(identity);
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
245 }
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
246 }
6a6cb7f2db90 fix wrong handling of memory anti-dependencies in scheduler
Erik Eckstein <erik.eckstein@oracle.com>
parents: 15599
diff changeset
247 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
248 }
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
249
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
250 if (foundExcludeNode) {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
251 accm = set;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
252 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
253 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
254
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
255 // 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
256 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
257 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
258
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
259 return set;
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
260 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
261
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
262 private KillSet computeKillSet(Block block) {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
263 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
264 }
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
265
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
266 private ControlFlowGraph cfg;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
267 private NodeMap<Block> earliestCache;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
268
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
269 /**
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
270 * Map from blocks to the nodes in each block.
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
271 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
272 private BlockMap<List<ValueNode>> blockToNodesMap;
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
273 private BlockMap<KillSet> blockToKillSet;
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
274 private final SchedulingStrategy selectedStrategy;
10894
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
275 private final MemoryScheduling memsched;
8325
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
276
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
277 public SchedulePhase() {
9864
063a712fe8d8 converted remaining options in GraalOptions to new system (GRAAL-27)
Doug Simon <doug.simon@oracle.com>
parents: 9810
diff changeset
278 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
279 }
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
280
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
281 public SchedulePhase(SchedulingStrategy strategy) {
17365
4ab45518048b removed MemoryAwareScheduling option (since non-memory aware scheduling currently generates invalid code)
Doug Simon <doug.simon@oracle.com>
parents: 17064
diff changeset
282 this.memsched = MemoryScheduling.OPTIMAL;
8330
022ae20329fb Rename field.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8325
diff changeset
283 this.selectedStrategy = strategy;
8325
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
284 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
285
10925
32a48a01e411 SchedulePhase: remove debugging boolean
Bernhard Urban <bernhard.urban@jku.at>
parents: 10924
diff changeset
286 public SchedulePhase(SchedulingStrategy strategy, MemoryScheduling memsched) {
10894
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
287 this.selectedStrategy = strategy;
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
288 this.memsched = memsched;
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
289 }
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
290
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
291 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
292 protected void run(StructuredGraph graph) {
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 13599
diff changeset
293 assert GraphOrder.assertNonCyclicGraph(graph);
9413
4f8b7dc2766d SchedulePhase: compute post-dominators in CFG-graph
Bernhard Urban <bernhard.urban@jku.at>
parents: 8957
diff changeset
294 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
295 earliestCache = graph.createNodeMap();
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
296 blockToNodesMap = new BlockMap<>(cfg);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
297
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
298 if (memsched == MemoryScheduling.OPTIMAL && selectedStrategy != SchedulingStrategy.EARLIEST) {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
299 blockToKillSet = new BlockMap<>(cfg);
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
300 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
301
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
302 assignBlockToNodes(graph, selectedStrategy);
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
303 printSchedule("after assign nodes to blocks");
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
304
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
305 sortNodesWithinBlocks(graph, selectedStrategy);
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
306 printSchedule("after sorting nodes within blocks");
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
307 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
308
13153
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
309 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
310 MemoryNode current = memory;
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
311 while (current instanceof MemoryProxy) {
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
312 current = ((MemoryProxy) current).getOriginalMemoryNode();
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
313 }
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
314 Block b = cfg.getNodeToBlock().get(current.asNode());
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
315 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
316 return b;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
317 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
318
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
319 private void printSchedule(String desc) {
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
320 if (Debug.isLogEnabled()) {
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
321 printScheduleHelper(desc);
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
322 }
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
323 }
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
324
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
325 private void printScheduleHelper(String desc) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
326 Formatter buf = new Formatter();
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
327 buf.format("=== %s / %s / %s (%s) ===%n", getCFG().getStartBlock().getBeginNode().graph(), selectedStrategy, memsched, desc);
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
328 for (Block b : getCFG().getBlocks()) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
329 buf.format("==== b: %s (loopDepth: %s). ", b, b.getLoopDepth());
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
330 buf.format("dom: %s. ", b.getDominator());
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
331 buf.format("post-dom: %s. ", b.getPostdominator());
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
332 buf.format("preds: %s. ", b.getPredecessors());
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
333 buf.format("succs: %s ====%n", b.getSuccessors());
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
334 BlockMap<KillSet> killSets = blockToKillSet;
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
335 if (killSets != null) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
336 buf.format("X block kills: %n");
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
337 if (killSets.get(b) != null) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
338 for (LocationIdentity locId : killSets.get(b)) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
339 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
340 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
341 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
342 }
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
343
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
344 if (blockToNodesMap.get(b) != null) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
345 for (Node n : nodesFor(b)) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
346 printNode(n);
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
347 }
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
348 } else {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
349 for (Node n : b.getNodes()) {
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
350 printNode(n);
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
351 }
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
352 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
353 }
18813
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
354 buf.format("%n");
498a56d8bb9b Remove IterableNodeType from FloatingReadNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18583
diff changeset
355 Debug.log("%s", buf);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
356 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
357
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
358 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
359 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
360 buf.format("%s", n);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
361 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
362 buf.format(" // kills %s", ((MemoryCheckpoint.Single) n).getLocationIdentity());
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
363 } 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
364 buf.format(" // kills ");
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
365 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
366 buf.format("%s, ", locid);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
367 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
368 } else if (n instanceof FloatingReadNode) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
369 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
370 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
371 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
372 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
373 } else if (n instanceof GuardNode) {
15008
01fdabd19cd5 new AnchoringNode interface
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14908
diff changeset
374 buf.format(", anchor: %s", ((GuardNode) n).getAnchor());
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
375 }
14873
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
376 Debug.log("%s", buf);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
377 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
378
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
379 public ControlFlowGraph getCFG() {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
380 return cfg;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
381 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
382
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
383 /**
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
384 * 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
385 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
386 public BlockMap<List<ValueNode>> getBlockToNodesMap() {
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
387 return blockToNodesMap;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
388 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
389
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
390 /**
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
391 * Gets the nodes in a given block.
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
392 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
393 public List<ValueNode> nodesFor(Block block) {
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
394 return blockToNodesMap.get(block);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
395 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
396
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
397 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
398 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
399 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
400 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
401 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
402 }
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
403 blockToNodesMap.put(block, nodes);
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
404 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
405 nodes.add(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
406 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
407 }
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 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
410 if (n instanceof ValueNode) {
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
411 assignBlockToNode((ValueNode) n, strategy);
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
412 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
413 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
414 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
415
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
416 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
417 * 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
418 * 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
419 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
420 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
421 assert !node.isDeleted();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
422
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
423 if (cfg.getNodeToBlock().containsKey(node)) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
424 return;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
425 }
10892
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 10891
diff changeset
426 // 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
427 // ControlFlowGraph.identifyBlocks
10892
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 10891
diff changeset
428 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
429 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
430 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
431
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
432 Block earliestBlock = earliestBlock(node);
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
433 Block block = null;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
434 Block latest = null;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
435 switch (strategy) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
436 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
437 block = earliestBlock;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
438 break;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
439 case LATEST:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
440 case LATEST_OUT_OF_LOOPS:
18231
70df63b02309 Use LocationIdentity.isImmutable instead of testing against FINAL_LOCATION
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 17365
diff changeset
441 boolean scheduleRead = memsched == MemoryScheduling.OPTIMAL && 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
442 if (scheduleRead) {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
443 FloatingReadNode read = (FloatingReadNode) node;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
444 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
445 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
446 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
447 read.getLocationIdentity());
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
448 } else {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
449 block = latestBlock(node, strategy);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
450 }
12772
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
451 if (block == null) {
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
452 // handle nodes without usages
12772
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
453 block = earliestBlock;
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
454 } 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
455 // 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
456 latest = block;
12772
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
457 block = scheduleOutOfLoops(node, block, earliestBlock);
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
458 }
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
459
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
460 if (assertionEnabled()) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
461 if (scheduleRead) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
462 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
463 MemoryNode lastLocationAccess = read.getLastLocationAccess();
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
464 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
465 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
466 "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
467 read.getLocationIdentity(), block, upperBound, earliestBlock, latest);
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
468 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
469 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
470 break;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
471 default:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
472 throw new GraalInternalError("unknown scheduling strategy");
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
473 }
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
474 if (!dominates(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
475 throw new SchedulingError("%s: Graph cannot be scheduled : inconsistent for %s, %d usages, (%s needs to dominate %s)", node.graph(), node, node.usages().count(), earliestBlock, block);
3d97040060d4 SchedulePhase: bail out with SchedulingError if scheduled block is not dominated by earliest
Bernhard Urban <bernhard.urban@jku.at>
parents: 11864
diff changeset
476 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
477 cfg.getNodeToBlock().set(node, block);
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
478 blockToNodesMap.get(block).add(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
479 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
480
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
481 @SuppressWarnings("all")
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
482 private static boolean assertionEnabled() {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
483 boolean enabled = false;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
484 assert enabled = true;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
485 return enabled;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
486 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
487
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
488 /**
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
489 * 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
490 * 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
491 * dependencies using kill sets.
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
492 *
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
493 * In terms of domination relation, it looks like this:
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
494 *
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
495 * <pre>
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
496 * 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
497 * &and;
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
498 * E earliest block
14906
f3a5036cc13c javadoc fixes
Bernhard Urban <bernhard.urban@jku.at>
parents: 14873
diff changeset
499 * &and;
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
500 * 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
501 * &and;
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
502 * 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
503 * </pre>
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
504 *
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
505 * 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
506 *
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
507 */
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
508 private Block optimalBlock(FloatingReadNode n, SchedulingStrategy strategy) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
509 assert memsched == MemoryScheduling.OPTIMAL;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
510
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
511 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
512 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
513
13153
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
514 Block upperBoundBlock = blockForMemoryNode(n.getLastLocationAccess());
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
515 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
516 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
517
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
518 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
519 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
520
14873
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
521 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
522 if (earliestBlock == latestBlock) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
523 // 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
524 return latestBlock;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
525 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
526
13599
29b1b216d20a SchedulePhase: use {Queue,Deque}/LinkedList instead of Stack
Bernhard Urban <bernhard.urban@jku.at>
parents: 13370
diff changeset
527 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
528 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
529
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
530 // follow path, start at earliest schedule
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
531 while (path.size() > 0) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
532 Block currentBlock = path.pop();
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
533 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
534 if (dominatedBlock != null && !currentBlock.getSuccessors().contains(dominatedBlock)) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
535 // the dominated block is not a successor -> we have a split
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
536 assert dominatedBlock.getBeginNode() instanceof MergeNode;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
537
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
538 HashSet<Block> region = computeRegion(currentBlock, dominatedBlock);
14873
00eb80d735ed removed Debug.printf and added multi-arg versions of Debug.dump
Doug Simon <doug.simon@oracle.com>
parents: 14763
diff changeset
539 Debug.log("> merge. %s: region for %s -> %s: %s", n, currentBlock, dominatedBlock, region);
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
540
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
541 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
542 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
543 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
544 // 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
545 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
546 } else {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
547 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
548 }
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
549 Map<FixedNode, KillSet> states;
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
550 states = ReentrantBlockIterator.apply(closure, currentBlock, new KillSet(), region);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
551
12774
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
552 KillSet mergeState = states.get(dominatedBlock.getBeginNode());
1729072a893a NewMemoryAwareScheduling: hide data structure behind wrapper class
Bernhard Urban <bernhard.urban@jku.at>
parents: 12773
diff changeset
553 if (mergeState.isKilled(locid)) {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
554 // location got killed somewhere in the branches,
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
555 // 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
556 return currentBlock;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
557 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
558 } else {
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
559 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
560 assert earliestBlock == upperBoundBlock;
13153
ae0001b445c0 Common base interface for nodes in the memory graph.
Roland Schatz <roland.schatz@oracle.com>
parents: 13152
diff changeset
561 KillSet ks = computeKillSet(upperBoundBlock, ValueNodeUtil.asNode(n.getLastLocationAccess()));
13092
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
562 if (ks.isKilled(locid)) {
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
563 return upperBoundBlock;
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
564 }
b334ca53f077 NewMemoryAwareScheduling: don't consider lastAccessLocation of a read as a kill
Bernhard Urban <bernhard.urban@jku.at>
parents: 12774
diff changeset
565 } else if (dominatedBlock == null || computeKillSet(currentBlock).isKilled(locid)) {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
566 return currentBlock;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
567 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
568 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
569 }
13370
3e67710a6d08 SchedulePhase: remove old memory aware scheudling
Bernhard Urban <bernhard.urban@jku.at>
parents: 13369
diff changeset
570 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
571 }
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
572
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
573 /**
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
574 * 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
575 *
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
576 * @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
577 */
13599
29b1b216d20a SchedulePhase: use {Queue,Deque}/LinkedList instead of Stack
Bernhard Urban <bernhard.urban@jku.at>
parents: 13370
diff changeset
578 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
579 Deque<Block> path = new LinkedList<>();
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
580 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
581 while (currentBlock != null && dominates(earliestBlock, currentBlock)) {
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
582 path.push(currentBlock);
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
583 currentBlock = currentBlock.getDominator();
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
584 }
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
585 assert path.peek() == earliestBlock;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
586 return path;
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
587 }
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
588
12773
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 * compute a set that contains all blocks in a region spanned by dominatorBlock and
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
591 * dominatedBlock (exclusive the dominatedBlock).
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
592 */
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
593 private static HashSet<Block> computeRegion(Block dominatorBlock, Block dominatedBlock) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
594 HashSet<Block> region = new HashSet<>();
13599
29b1b216d20a SchedulePhase: use {Queue,Deque}/LinkedList instead of Stack
Bernhard Urban <bernhard.urban@jku.at>
parents: 13370
diff changeset
595 Queue<Block> workList = new LinkedList<>();
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
596
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
597 region.add(dominatorBlock);
13599
29b1b216d20a SchedulePhase: use {Queue,Deque}/LinkedList instead of Stack
Bernhard Urban <bernhard.urban@jku.at>
parents: 13370
diff changeset
598 workList.addAll(dominatorBlock.getSuccessors());
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
599 while (workList.size() > 0) {
13599
29b1b216d20a SchedulePhase: use {Queue,Deque}/LinkedList instead of Stack
Bernhard Urban <bernhard.urban@jku.at>
parents: 13370
diff changeset
600 Block current = workList.poll();
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
601 if (current != dominatedBlock) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
602 region.add(current);
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
603 for (Block b : current.getSuccessors()) {
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
604 if (!region.contains(b) && !workList.contains(b)) {
13599
29b1b216d20a SchedulePhase: use {Queue,Deque}/LinkedList instead of Stack
Bernhard Urban <bernhard.urban@jku.at>
parents: 13370
diff changeset
605 workList.offer(b);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
606 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
607 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
608 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
609 }
12773
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
610 assert !region.contains(dominatedBlock) && region.containsAll(dominatedBlock.getPredecessors());
b6e04d6fe3a7 NewMemoryAwareScheduling: rewrite to set based approach
Bernhard Urban <bernhard.urban@jku.at>
parents: 12772
diff changeset
611 return region;
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
612 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
613
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
614 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
615 * 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
616 * 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
617 *
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
618 * @param strategy
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
619 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
620 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
621 CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(null);
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
622 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
623 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
624 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
625 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
626 cdbc.apply(cfg.getNodeToBlock().get(succ));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
627 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
628 ensureScheduledUsages(node, strategy);
17064
3c54a098455f removed Node.recordsUsages()
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
629 for (Node usage : node.usages()) {
3c54a098455f removed Node.recordsUsages()
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
630 blocksForUsage(node, usage, cdbc, strategy);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
631 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
632
13298
5a3491b0c2f0 convert assertion in SchedulePhase to raise SchedulingError instead of AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 13153
diff changeset
633 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
634 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
635 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
636 }
5a3491b0c2f0 convert assertion in SchedulePhase to raise SchedulingError instead of AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 13153
diff changeset
637 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
638 return cdbc.block;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
639 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
640
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
641 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
642 * 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
643 * {@link #apply(Block)} method.
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
644 */
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
645 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
646
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
647 public Block block;
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
648
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
649 public CommonDominatorBlockClosure(Block block) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
650 this.block = block;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
651 }
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
652
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
653 @Override
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
654 public void apply(Block newBlock) {
16503
b3800429f543 Move commonDominator to AbstractControlFlowGraph.
Josef Eisl <josef.eisl@jku.at>
parents: 16443
diff changeset
655 this.block = commonDominatorTyped(this.block, newBlock);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
656 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
657 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
658
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
659 /**
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
660 * 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
661 */
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
662 private Block earliestBlock(Node node) {
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
663 Block earliest = cfg.getNodeToBlock().get(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
664 if (earliest != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
665 return earliest;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
666 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
667 earliest = earliestCache.get(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
668 if (earliest != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
669 return earliest;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
670 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
671 /*
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
672 * 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
673 * 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
674 * 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
675 * 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
676 */
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
677
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
678 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
679 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
680 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
681 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
682 assert input instanceof ValueNode;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
683 Block inputEarliest;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
684 if (input instanceof InvokeWithExceptionNode) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
685 inputEarliest = cfg.getNodeToBlock().get(((InvokeWithExceptionNode) input).next());
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
686 } else {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
687 inputEarliest = earliestBlock(input);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
688 }
15173
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
689 if (earliest == null) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
690 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
691 } 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
692 // 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
693 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
694 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
695 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
696 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
697 // 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
698 break;
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
699 } 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
700 // 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
701 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
702 break;
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
703 }
fc7f2bbd4edd Improve schedule phase to avoid allocation of a BitSet per scheduled node.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15157
diff changeset
704 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
705 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
706 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
707 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
708 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
709 if (earliest == null) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
710 earliest = cfg.getStartBlock();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
711 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
712 earliestCache.set(node, earliest);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
713 return earliest;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
714 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
715
12772
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
716 /**
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
717 * 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
718 * 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
719 * not valid.
14763
a6c1c3eb20c4 transition to JDK8
Doug Simon <doug.simon@oracle.com>
parents: 14734
diff changeset
720 *
12772
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
721 * @param n Node to schedule
6a7b6dcb7f67 NewMemoryAwareScheduling: fix out of loop for FloatingReadNodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 12722
diff changeset
722 * @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
723 * @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
724 * @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
725 */
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
726 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
727 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
728 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
729 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
730 Block cur = latestBlock;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
731 Block result = latestBlock;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
732 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
733 Block dom = cur.getDominator();
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
734 if (dom.getLoopDepth() < result.getLoopDepth()) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
735 result = dom;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
736 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
737 cur = dom;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
738 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
739 return result;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
740 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
741
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
742 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
743 * 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
744 * 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
745 *
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
746 * @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
747 * @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
748 * @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
749 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
750 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
751 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
752 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
753 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
754
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
755 if (usage instanceof PhiNode) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
756 // 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
757 // the PhiNode input.
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
758 // 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
759 // usage.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
760 PhiNode phi = (PhiNode) usage;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
761 MergeNode merge = phi.merge();
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
762 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
763 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
764 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
765 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
766 for (int i = 0; i < phi.valueCount(); ++i) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
767 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
768 if (mergeBlock.getPredecessorCount() <= i) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
769 TTY.println(merge.toString());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
770 TTY.println(phi.toString());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
771 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
772 TTY.println(mergeBlock.getPredecessors().toString());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
773 TTY.println(phi.inputs().toString());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
774 TTY.println("value count: " + phi.valueCount());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
775 }
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4525
diff changeset
776 closure.apply(mergeBlock.getPredecessors().get(i));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
777 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
778 }
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
779 } else if (usage instanceof VirtualState) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
780 // 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
781 // called for PhiNodes.
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
782 for (Node unscheduledUsage : usage.usages()) {
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
783 if (unscheduledUsage instanceof VirtualState) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
784 // 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
785 // FrameState was the actual usage, by recursing.
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
786 blocksForUsage(node, unscheduledUsage, closure, strategy);
15145
df2ef5204f2b Remove AbstractBeginNode, move the framestate from AbstractBeginNode to BeginStateSplitNode.
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 15107
diff changeset
787 } else if (unscheduledUsage instanceof BeginNode) {
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
788 // 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
789 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
790 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
791 }
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
792 if (unscheduledUsage instanceof StartNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
793 closure.apply(cfg.getNodeToBlock().get(unscheduledUsage));
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
794 } else {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
795 // 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
796 // the common dominator of all EndNodes.
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
797 for (Node pred : unscheduledUsage.cfgPredecessors()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
798 closure.apply(cfg.getNodeToBlock().get(pred));
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13729
diff changeset
799 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
800 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
801 } else {
13293
5215f94f94ec GRAAL-632: Clarify difference between states managed by StateSplit and DeoptimizingNode
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 13153
diff changeset
802 // 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
803 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
804 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
805 }
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
806 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
807 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
808 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
809 // 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
810 assignBlockToNode((ValueNode) unscheduledUsage, strategy);
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
811 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
812 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
813 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
814 } else {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
815 // 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
816 assignBlockToNode((ValueNode) usage, strategy);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
817 closure.apply(cfg.getNodeToBlock().get(usage));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
818 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
819 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
820
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
821 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
822 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
823 assignBlockToNode((ValueNode) usage, strategy);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
824 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
825 // now true usages are ready
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
826 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
827
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
828 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
829 NodeBitMap visited = graph.createNodeBitMap();
10921
b73121a215f7 NewMemoryAwareScheduling: create nodebitmap once per graph (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10920
diff changeset
830 NodeBitMap beforeLastLocation = graph.createNodeBitMap();
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
831 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
832 sortNodesWithinBlock(b, visited, beforeLastLocation, strategy);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
833 assert noDuplicatedNodesInBlock(b) : "duplicated nodes in " + b;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
834 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
835 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
836
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
837 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
838 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
839 Set<ValueNode> hashset = Node.newSet(list);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
840 return list.size() == hashset.size();
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
841 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
842
10921
b73121a215f7 NewMemoryAwareScheduling: create nodebitmap once per graph (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10920
diff changeset
843 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
844 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
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 }
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
847 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
848 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
849 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
850
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
851 List<ValueNode> sortedInstructions;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
852 switch (strategy) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
853 case EARLIEST:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
854 sortedInstructions = sortNodesWithinBlockEarliest(b, visited);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
855 break;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
856 case LATEST:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
857 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
858 sortedInstructions = sortNodesWithinBlockLatest(b, visited, beforeLastLocation);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
859 break;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
860 default:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
861 throw new GraalInternalError("unknown scheduling strategy");
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
862 }
10922
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
863 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
864 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
865 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
866 blockToNodesMap.put(b, sortedInstructions);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
867 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
868
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
869 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
870 List<ValueNode> result = new ArrayList<>();
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
871 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
872 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
873 result.add(n);
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 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
876 return result;
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
877 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
878
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
879 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
880 List<ValueNode> result = new ArrayList<>();
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
881 for (ValueNode n : list) {
11501
a116fb4875a6 SchedulePhase: remove special handling of localnodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 11460
diff changeset
882 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
883 result.add(n);
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 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
886 return result;
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
887 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
888
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
889 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
890 Iterator<ValueNode> fixedIterator = fixed.iterator();
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
891 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
892
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 while (sortedIterator.hasNext()) {
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
894 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
895 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
896 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
897 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
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 }
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 }
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
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 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
903 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
904 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
905 }
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
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
908 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
909 }
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
910
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
911 private static class SortState {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
912 private Block block;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
913 private NodeBitMap visited;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
914 private NodeBitMap beforeLastLocation;
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
915 private List<ValueNode> sortedInstructions;
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
916 private List<FloatingReadNode> reads;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
917
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
918 SortState(Block block, NodeBitMap visited, NodeBitMap beforeLastLocation, List<ValueNode> sortedInstructions) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
919 this.block = block;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
920 this.visited = visited;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
921 this.beforeLastLocation = beforeLastLocation;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
922 this.sortedInstructions = sortedInstructions;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
923 this.reads = null;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
924 }
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 public Block currentBlock() {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
927 return block;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
928 }
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 void markVisited(Node n) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
931 visited.mark(n);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
932 }
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 boolean isVisited(Node n) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
935 return visited.isMarked(n);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
936 }
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 void markBeforeLastLocation(FloatingReadNode n) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
939 beforeLastLocation.mark(n);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
940 }
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 void clearBeforeLastLocation(FloatingReadNode frn) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
943 beforeLastLocation.clear(frn);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
944 }
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 boolean isBeforeLastLocation(FloatingReadNode n) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
947 return beforeLastLocation.isMarked(n);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
948 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
949
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
950 void addRead(FloatingReadNode n) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
951 if (reads == null) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
952 reads = new ArrayList<>();
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 reads.add(n);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
955 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
956
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
957 int readsSize() {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
958 if (reads == null) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
959 return 0;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
960 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
961 return reads.size();
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
962 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
963
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
964 void removeRead(ValueNode i) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
965 assert reads != null;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
966 reads.remove(i);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
967 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
968
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
969 List<FloatingReadNode> readsSnapshot() {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
970 assert reads != null;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
971 return new ArrayList<>(reads);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
972 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
973
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
974 List<ValueNode> getSortedInstructions() {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
975 return sortedInstructions;
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
976 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
977
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
978 boolean containsInstruction(ValueNode i) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
979 return sortedInstructions.contains(i);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
980 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
981
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
982 void addInstruction(ValueNode i) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
983 sortedInstructions.add(i);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
984 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
985 }
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
986
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
987 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
988 * 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
989 * 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
990 * processed.
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
991 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
992 private List<ValueNode> sortNodesWithinBlockLatest(Block b, NodeBitMap visited, NodeBitMap beforeLastLocation) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
993 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
994 List<ValueNode> instructions = blockToNodesMap.get(b);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
995
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
996 if (memsched == MemoryScheduling.OPTIMAL) {
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
997 for (ValueNode i : instructions) {
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
998 if (i instanceof FloatingReadNode) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
999 FloatingReadNode frn = (FloatingReadNode) i;
18231
70df63b02309 Use LocationIdentity.isImmutable instead of testing against FINAL_LOCATION
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 17365
diff changeset
1000 if (!frn.location().getLocationIdentity().isImmutable()) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1001 state.addRead(frn);
12722
b87c2f34e0e0 Maintain lastLocationAccess in WriteNode.
Roland Schatz <roland.schatz@oracle.com>
parents: 12721
diff changeset
1002 if (nodesFor(b).contains(frn.getLastLocationAccess())) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1003 assert !state.isBeforeLastLocation(frn);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1004 state.markBeforeLastLocation(frn);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1005 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1006 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1007 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1008 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1009 }
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1010
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1011 for (ValueNode i : instructions) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1012 addToLatestSorting(i, state);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1013 }
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1014 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
1015
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
1016 // 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
1017 // it).
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1018 List<ValueNode> sortedInstructions = state.getSortedInstructions();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1019 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
1020 if (lastSorted != b.getEndNode()) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
1021 int idx = sortedInstructions.indexOf(b.getEndNode());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1022 boolean canNotMove = false;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1023 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
1024 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
1025 canNotMove = true;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1026 break;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1027 }
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 if (canNotMove) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
1030 if (b.getEndNode() instanceof ControlSplitNode) {
15193
96bb07a5d667 Spit up and move GraalInternalError.
Josef Eisl <josef.eisl@jku.at>
parents: 15192
diff changeset
1031 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
1032 b.getEndNode());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1033 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1034
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
1035 // b.setLastNode(lastSorted);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1036 } else {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
1037 sortedInstructions.remove(b.getEndNode());
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
1038 sortedInstructions.add(b.getEndNode());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1039 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1040 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1041 return sortedInstructions;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1042 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1043
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1044 private void processKillLocation(Node node, LocationIdentity identity, SortState state) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1045 for (FloatingReadNode frn : state.readsSnapshot()) {
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1046 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
1047 assert !readLocation.isImmutable();
12722
b87c2f34e0e0 Maintain lastLocationAccess in WriteNode.
Roland Schatz <roland.schatz@oracle.com>
parents: 12721
diff changeset
1048 if (frn.getLastLocationAccess() == node) {
18583
12bd2b344b08 replace usages of == with .equals()
Doug Simon <doug.simon@oracle.com>
parents: 18383
diff changeset
1049 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
1050 state.clearBeforeLastLocation(frn);
18583
12bd2b344b08 replace usages of == with .equals()
Doug Simon <doug.simon@oracle.com>
parents: 18383
diff changeset
1051 } 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
1052 state.removeRead(frn);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1053 addToLatestSorting(frn, state);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1054 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1055 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1056 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1057
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1058 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
1059 if (state != null) {
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
1060 // UnscheduledNodes should never be marked as visited.
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1061 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
1062 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
1063 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1064
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1065 for (Node input : state.inputs()) {
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
1066 if (input instanceof VirtualState) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1067 addUnscheduledToLatestSorting((VirtualState) input, sortState);
13327
c258331fdde6 removed support for external nodes (GRAAL-508)
Doug Simon <doug.simon@oracle.com>
parents: 13299
diff changeset
1068 } else {
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1069 addToLatestSorting((ValueNode) input, sortState);
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1070 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1071 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1072 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1073 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1074
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1075 private void addToLatestSorting(ValueNode i, SortState state) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1076 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
1077 return;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1078 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1079
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
1080 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
1081 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
1082 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
1083 }
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
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1085 for (Node input : i.inputs()) {
10891
8c0ab217ed00 Scheduling: remove dead code in addToLatestSorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10890
diff changeset
1086 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
1087 if (input != stateAfter) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1088 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
1089 }
13327
c258331fdde6 removed support for external nodes (GRAAL-508)
Doug Simon <doug.simon@oracle.com>
parents: 13299
diff changeset
1090 } else {
15284
9b122a4d2e94 correctly schedule loop proxies
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15259
diff changeset
1091 if (!(i instanceof ProxyNode && input instanceof LoopExitNode)) {
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1092 addToLatestSorting((ValueNode) input, state);
15284
9b122a4d2e94 correctly schedule loop proxies
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15259
diff changeset
1093 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1094 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1095 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1096
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1097 if (memsched == MemoryScheduling.OPTIMAL && state.readsSize() != 0) {
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1098 if (i instanceof MemoryCheckpoint.Single) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1099 LocationIdentity identity = ((MemoryCheckpoint.Single) i).getLocationIdentity();
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 } else if (i instanceof MemoryCheckpoint.Multi) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1102 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) i).getLocationIdentities()) {
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1103 processKillLocation(i, identity, state);
10896
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 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1106 assert MemoryCheckpoint.TypeAssertion.correctType(i);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1107 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1108
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1109 addToLatestSorting((ValueNode) i.predecessor(), state);
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1110 state.markVisited(i);
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1111 addUnscheduledToLatestSorting(stateAfter, state);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1112
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1113 // 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
1114 if (!state.containsInstruction(i)) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1115 state.addInstruction(i);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1116 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1117
15423
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1118 if (state.readsSize() != 0 && i instanceof FloatingReadNode) {
81eee524bbec SchedulePhase: refactoring
Bernhard Urban <bernhard.urban@jku.at>
parents: 15422
diff changeset
1119 state.removeRead(i);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1120 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1121 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1122
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1123 /**
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1124 * 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
1125 * 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
1126 * nodes.
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1127 */
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1128 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
1129 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
1130 addToEarliestSorting(b, b.getEndNode(), sortedInstructions, visited);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1131 Collections.reverse(sortedInstructions);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1132 return sortedInstructions;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1133 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1134
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1135 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
1136 ValueNode instruction = i;
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1137 while (true) {
11501
a116fb4875a6 SchedulePhase: remove special handling of localnodes
Bernhard Urban <bernhard.urban@jku.at>
parents: 11460
diff changeset
1138 if (instruction == null || visited.isMarked(instruction) || cfg.getNodeToBlock().get(instruction) != b || instruction instanceof PhiNode) {
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1139 return;
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1140 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1141
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1142 visited.mark(instruction);
17064
3c54a098455f removed Node.recordsUsages()
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
1143 for (Node usage : instruction.usages()) {
3c54a098455f removed Node.recordsUsages()
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
1144 if (usage instanceof VirtualState) {
3c54a098455f removed Node.recordsUsages()
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
1145 // 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
1146 } else {
3c54a098455f removed Node.recordsUsages()
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
1147 if (instruction instanceof LoopExitNode && usage instanceof ProxyNode) {
3c54a098455f removed Node.recordsUsages()
Doug Simon <doug.simon@oracle.com>
parents: 16841
diff changeset
1148 // value proxies should be scheduled before the loopexit, not after
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1149 } else {
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1150 addToEarliestSorting(b, (ValueNode) usage, sortedInstructions, visited);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1151 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1152 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1153 }
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1154
15145
df2ef5204f2b Remove AbstractBeginNode, move the framestate from AbstractBeginNode to BeginStateSplitNode.
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 15107
diff changeset
1155 if (instruction instanceof BeginNode) {
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1156 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
1157 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
1158 addToEarliestSorting(b, inBlock, sortedInstructions, visited);
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1159 }
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1160 }
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1161 sortedInstructions.add(instruction);
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1162 break;
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1163 } else {
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1164 sortedInstructions.add(instruction);
18941
c943ba97b2a7 Remove class ScheduledNode from the node class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18813
diff changeset
1165 instruction = (ValueNode) instruction.predecessor();
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1166 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1167 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1168 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1169 }