Mercurial > hg > truffle

annotate graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java @ 10922:1d1675f18e85

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Scheduling: add assert about nodes in a block after sorting
author Bernhard Urban <bernhard.urban@jku.at>
date Thu, 01 Aug 2013 17:24:41 +0200
parents b73121a215f7
children f75695de1312
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.*;
10609
5f016460f95b scheduling: remove duplicated code
Bernhard Urban <bernhard.urban@jku.at>
parents: 10490
diff changeset
26 import static com.oracle.graal.nodes.cfg.ControlFlowGraph.*;
9864
063a712fe8d8 converted remaining options in GraalOptions to new system (GRAAL-27)
Doug Simon <doug.simon@oracle.com>
parents: 9810
diff changeset
27 import static com.oracle.graal.phases.GraalOptions.*;
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.*;
6500
8fd4201ce98c moved TTY and LogStream to com.oracle.graal.debug
Doug Simon <doug.simon@oracle.com>
parents: 6411
diff changeset
32 import com.oracle.graal.debug.*;
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
33 import com.oracle.graal.graph.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
34 import com.oracle.graal.graph.Node.Verbosity;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
35 import com.oracle.graal.nodes.*;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
36 import com.oracle.graal.nodes.calc.*;
6529
2e96dc4eb8e2 renamed package: com.oracle.graal.lir.cfg -> com.oracle.graal.nodes.cfg
Doug Simon <doug.simon@oracle.com>
parents: 6526
diff changeset
37 import com.oracle.graal.nodes.cfg.*;
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
38 import com.oracle.graal.nodes.extended.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
39 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
40 import com.oracle.graal.phases.*;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
41 import com.oracle.graal.phases.graph.*;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
42 import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
43 import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
44
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
45 public final class SchedulePhase extends Phase {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
46
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
47 /**
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
48 * 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
49 */
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 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
51
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 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
53
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 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
55 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
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
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 /**
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 * 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
60 * {@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
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 * @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
63 * @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
64 */
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 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
66 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
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
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 }
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
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
71 public static enum SchedulingStrategy {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
72 EARLIEST, LATEST, LATEST_OUT_OF_LOOPS
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
73 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
74
10894
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
75 public static enum MemoryScheduling {
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
76 NONE, CONSERVATIVE, OPTIMAL
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
77 }
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
78
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
79 /**
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
80 * This closure iterates over all nodes of a scheduled graph (it expects a
8207
ed880b9992b4 Add GuardLoweringPhase which transforms floating guards into fixed if+deopt
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 7897
diff changeset
81 * {@link SchedulingStrategy#EARLIEST} schedule) and keeps a list of "active" reads. Whenever it
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
82 * encounters a read, it adds it to the active reads. Whenever it encounters a memory
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
83 * checkpoint, it adds all reads that need to be committed before this checkpoint to the
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
84 * "phantom" usages and inputs, so that the read is scheduled before the checkpoint afterwards.
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
85 *
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
86 * At merges, the intersection of all sets of active reads is calculated. A read that was
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
87 * committed within one predecessor branch cannot be scheduled after the merge anyway.
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
88 *
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
89 * Similarly for loops, all reads that are killed somewhere within the loop are removed from the
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
90 * exits' active reads, since they cannot be scheduled after the exit anyway.
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
91 */
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
92 private class MemoryScheduleClosure extends BlockIteratorClosure<HashSet<FloatingReadNode>> {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
93
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
94 @Override
9809
a8a5d5832def first step towards extensibility of the escape analysis phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 9725
diff changeset
95 protected HashSet<FloatingReadNode> getInitialState() {
a8a5d5832def first step towards extensibility of the escape analysis phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 9725
diff changeset
96 return new HashSet<>();
a8a5d5832def first step towards extensibility of the escape analysis phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 9725
diff changeset
97 }
a8a5d5832def first step towards extensibility of the escape analysis phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 9725
diff changeset
98
a8a5d5832def first step towards extensibility of the escape analysis phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 9725
diff changeset
99 @Override
9624
87eafaddf9d9 let ReentrantBlockIterator.processBlock return the next state
Lukas Stadler <lukas.stadler@jku.at>
parents: 9526
diff changeset
100 protected HashSet<FloatingReadNode> processBlock(Block block, HashSet<FloatingReadNode> currentState) {
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
101 for (Node node : getBlockToNodesMap().get(block)) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
102 if (node instanceof FloatingReadNode) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
103 currentState.add((FloatingReadNode) node);
10090
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
104 } else if (node instanceof MemoryCheckpoint.Single) {
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
105 LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
106 processIdentity(currentState, (FixedNode) node, identity);
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
107 } else if (node instanceof MemoryCheckpoint.Multi) {
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
108 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
109 processIdentity(currentState, (FixedNode) node, identity);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
110 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
111 }
10090
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
112 assert MemoryCheckpoint.TypeAssertion.correctType(node);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
113 }
9624
87eafaddf9d9 let ReentrantBlockIterator.processBlock return the next state
Lukas Stadler <lukas.stadler@jku.at>
parents: 9526
diff changeset
114 return currentState;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
115 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
116
10090
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
117 private void processIdentity(HashSet<FloatingReadNode> currentState, FixedNode fixed, LocationIdentity identity) {
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
118 for (Iterator<FloatingReadNode> iter = currentState.iterator(); iter.hasNext();) {
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
119 FloatingReadNode read = iter.next();
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
120 if (identity == ANY_LOCATION || read.location().getLocationIdentity() == identity) {
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
121 addPhantomReference(read, fixed);
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
122 iter.remove();
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
123 }
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
124 }
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
125 }
ae6f0c381087 split MemoryCheckpoint interface into Single and Multi
Lukas Stadler <lukas.stadler@jku.at>
parents: 9864
diff changeset
126
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
127 public void addPhantomReference(FloatingReadNode read, FixedNode fixed) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
128 List<FixedNode> usageList = phantomUsages.get(read);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
129 if (usageList == null) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
130 phantomUsages.put(read, usageList = new ArrayList<>());
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
131 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
132 usageList.add(fixed);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
133 List<FloatingNode> inputList = phantomInputs.get(fixed);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
134 if (inputList == null) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
135 phantomInputs.put(fixed, inputList = new ArrayList<>());
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
136 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
137 inputList.add(read);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
138 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
139
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
140 @Override
8920
4aa5f76a0579 small change to ReentrantBlockIterator interface
Lukas Stadler <lukas.stadler@jku.at>
parents: 8542
diff changeset
141 protected HashSet<FloatingReadNode> merge(Block merge, List<HashSet<FloatingReadNode>> states) {
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
142 HashSet<FloatingReadNode> state = new HashSet<>(states.get(0));
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
143 for (int i = 1; i < states.size(); i++) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
144 state.retainAll(states.get(i));
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
145 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
146 return state;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
147 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
148
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
149 @Override
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
150 protected HashSet<FloatingReadNode> cloneState(HashSet<FloatingReadNode> oldState) {
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
151 return new HashSet<>(oldState);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
152 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
153
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
154 @Override
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
155 protected List<HashSet<FloatingReadNode>> processLoop(Loop loop, HashSet<FloatingReadNode> state) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
156 LoopInfo<HashSet<FloatingReadNode>> info = ReentrantBlockIterator.processLoop(this, loop, new HashSet<>(state));
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
157
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
158 List<HashSet<FloatingReadNode>> loopEndStates = info.endStates;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
159
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
160 // collect all reads that were killed in some branch within the loop
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
161 Set<FloatingReadNode> killedReads = new HashSet<>(state);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
162 Set<FloatingReadNode> survivingReads = new HashSet<>(loopEndStates.get(0));
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
163 for (int i = 1; i < loopEndStates.size(); i++) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
164 survivingReads.retainAll(loopEndStates.get(i));
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
165 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
166 killedReads.removeAll(survivingReads);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
167
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
168 // reads that were killed within the loop cannot be scheduled after the loop anyway
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
169 for (HashSet<FloatingReadNode> exitState : info.exitStates) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
170 exitState.removeAll(killedReads);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
171 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
172 return info.exitStates;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
173 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
174 }
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
175
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
176 private class NewMemoryScheduleClosure extends BlockIteratorClosure<Map<LocationIdentity, Node>> {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
177
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
178 @Override
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
179 protected Map<LocationIdentity, Node> getInitialState() {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
180 return cloneState(blockToKillMap.get(getCFG().getStartBlock()));
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
181 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
182
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
183 @Override
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
184 protected Map<LocationIdentity, Node> processBlock(Block block, Map<LocationIdentity, Node> currentState) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
185 Map<LocationIdentity, Node> initKillMap = getBlockToKillMap().get(block);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
186 initKillMap.putAll(currentState);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
187
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
188 for (Node node : block.getNodes()) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
189 if (node instanceof MemoryCheckpoint.Single) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
190 LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
191 initKillMap.put(identity, node);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
192 } else if (node instanceof MemoryCheckpoint.Multi) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
193 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
194 initKillMap.put(identity, node);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
195 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
196 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
197 assert MemoryCheckpoint.TypeAssertion.correctType(node);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
198 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
199
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
200 return cloneState(initKillMap);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
201 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
202
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
203 @Override
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
204 protected Map<LocationIdentity, Node> merge(Block merge, List<Map<LocationIdentity, Node>> states) {
10919
2cf0785957fb NewMemoryAwareScheduling: handle loop headers different than merges (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10896
diff changeset
205 return merge(merge, states, false);
2cf0785957fb NewMemoryAwareScheduling: handle loop headers different than merges (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10896
diff changeset
206 }
2cf0785957fb NewMemoryAwareScheduling: handle loop headers different than merges (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10896
diff changeset
207
2cf0785957fb NewMemoryAwareScheduling: handle loop headers different than merges (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10896
diff changeset
208 protected Map<LocationIdentity, Node> merge(Block merge, List<Map<LocationIdentity, Node>> states, boolean loopbegin) {
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
209 assert merge.getBeginNode() instanceof MergeNode;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
210 MergeNode mergeNode = (MergeNode) merge.getBeginNode();
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
211
10919
2cf0785957fb NewMemoryAwareScheduling: handle loop headers different than merges (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10896
diff changeset
212 Map<LocationIdentity, Node> initKillMap = new HashMap<>();
2cf0785957fb NewMemoryAwareScheduling: handle loop headers different than merges (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10896
diff changeset
213 if (loopbegin) {
2cf0785957fb NewMemoryAwareScheduling: handle loop headers different than merges (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10896
diff changeset
214 initKillMap.putAll(getBlockToKillMap().get(merge));
2cf0785957fb NewMemoryAwareScheduling: handle loop headers different than merges (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10896
diff changeset
215 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
216 for (Map<LocationIdentity, Node> state : states) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
217 for (LocationIdentity locid : state.keySet()) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
218 if (initKillMap.containsKey(locid)) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
219 if (!initKillMap.get(locid).equals(state.get(locid))) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
220 initKillMap.put(locid, mergeNode);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
221 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
222 } else {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
223 initKillMap.put(locid, state.get(locid));
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
224 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
225 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
226 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
227
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
228 getMergeToKillMap().set(mergeNode, cloneState(initKillMap));
10919
2cf0785957fb NewMemoryAwareScheduling: handle loop headers different than merges (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10896
diff changeset
229 if (!loopbegin) {
2cf0785957fb NewMemoryAwareScheduling: handle loop headers different than merges (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10896
diff changeset
230 initKillMap.putAll(getBlockToKillMap().get(merge));
2cf0785957fb NewMemoryAwareScheduling: handle loop headers different than merges (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10896
diff changeset
231 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
232 return initKillMap;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
233 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
234
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
235 @Override
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
236 protected Map<LocationIdentity, Node> cloneState(Map<LocationIdentity, Node> state) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
237 return new HashMap<>(state);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
238 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
239
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
240 @Override
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
241 protected List<Map<LocationIdentity, Node>> processLoop(Loop loop, Map<LocationIdentity, Node> state) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
242 LoopInfo<Map<LocationIdentity, Node>> info = ReentrantBlockIterator.processLoop(this, loop, new HashMap<>(state));
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
243
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
244 assert loop.header.getBeginNode() instanceof LoopBeginNode;
10919
2cf0785957fb NewMemoryAwareScheduling: handle loop headers different than merges (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10896
diff changeset
245 Map<LocationIdentity, Node> headerState = merge(loop.header, info.endStates, true);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
246 getBlockToKillMap().put(loop.header, headerState);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
247
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
248 for (Map<LocationIdentity, Node> exitState : info.exitStates) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
249 for (LocationIdentity key : headerState.keySet()) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
250 exitState.put(key, headerState.get(key));
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
251 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
252 }
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 return info.exitStates;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
255 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
256 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
257
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
258 private ControlFlowGraph cfg;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
259 private NodeMap<Block> earliestCache;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
260
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
261 /**
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
262 * Map from blocks to the nodes in each block.
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
263 */
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
264 private BlockMap<List<ScheduledNode>> blockToNodesMap;
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
265 private BlockMap<Map<LocationIdentity, Node>> blockToKillMap;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
266 private NodeMap<Map<LocationIdentity, Node>> mergeToKillMap;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
267 private final Map<FloatingNode, List<FixedNode>> phantomUsages = new IdentityHashMap<>();
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
268 private final Map<FixedNode, List<FloatingNode>> phantomInputs = new IdentityHashMap<>();
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
269 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
270 private final MemoryScheduling memsched;
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
271 private final boolean dumpSchedule;
8325
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
272
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
273 public SchedulePhase() {
9864
063a712fe8d8 converted remaining options in GraalOptions to new system (GRAAL-27)
Doug Simon <doug.simon@oracle.com>
parents: 9810
diff changeset
274 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
275 }
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(SchedulingStrategy strategy) {
10894
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
278 if (MemoryAwareScheduling.getValue() && NewMemoryAwareScheduling.getValue()) {
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
279 throw new SchedulingError("cannot enable both: MemoryAware- and NewMemoryAwareScheduling");
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
280 }
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
281 if (MemoryAwareScheduling.getValue()) {
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
282 this.memsched = MemoryScheduling.CONSERVATIVE;
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
283 } else if (NewMemoryAwareScheduling.getValue()) {
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
284 this.memsched = MemoryScheduling.OPTIMAL;
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
285 } else {
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
286 this.memsched = MemoryScheduling.NONE;
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
287 }
8330
022ae20329fb Rename field.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8325
diff changeset
288 this.selectedStrategy = strategy;
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
289 this.dumpSchedule = false;
8325
330b455f18be Make scheduling phase customizable.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8323
diff changeset
290 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
291
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
292 public SchedulePhase(SchedulingStrategy strategy, MemoryScheduling memsched, boolean dumpSchedule) {
10894
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
293 this.selectedStrategy = strategy;
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
294 this.memsched = memsched;
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
295 this.dumpSchedule = dumpSchedule;
10894
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
296 }
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
297
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
298 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
299 protected void run(StructuredGraph graph) {
9413
4f8b7dc2766d SchedulePhase: compute post-dominators in CFG-graph
Bernhard Urban <bernhard.urban@jku.at>
parents: 8957
diff changeset
300 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
301 earliestCache = graph.createNodeMap();
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
302 blockToNodesMap = new BlockMap<>(cfg);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
303
10894
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
304 if (memsched == MemoryScheduling.CONSERVATIVE && selectedStrategy != SchedulingStrategy.EARLIEST && graph.getNodes(FloatingReadNode.class).isNotEmpty()) {
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
305 assignBlockToNodes(graph, SchedulingStrategy.EARLIEST);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
306 sortNodesWithinBlocks(graph, SchedulingStrategy.EARLIEST);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
307
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
308 MemoryScheduleClosure closure = new MemoryScheduleClosure();
9809
a8a5d5832def first step towards extensibility of the escape analysis phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 9725
diff changeset
309 ReentrantBlockIterator.apply(closure, getCFG().getStartBlock());
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
310
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
311 cfg.clearNodeToBlock();
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
312 blockToNodesMap = new BlockMap<>(cfg);
10894
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
313
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
314 assignBlockToNodes(graph, selectedStrategy);
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
315 sortNodesWithinBlocks(graph, selectedStrategy);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
316 printSchedule("after sorting nodes within blocks");
10894
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
317 } else if (memsched == MemoryScheduling.OPTIMAL && selectedStrategy != SchedulingStrategy.EARLIEST && graph.getNodes(FloatingReadNode.class).isNotEmpty()) {
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
318 mergeToKillMap = graph.createNodeMap();
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
319
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
320 blockToKillMap = new BlockMap<>(cfg);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
321 for (Block b : cfg.getBlocks()) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
322 blockToKillMap.put(b, new HashMap<LocationIdentity, Node>());
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
323 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
324
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
325 // initialize killMaps with lastLocationAccess
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
326 for (FloatingReadNode n : graph.getNodes(FloatingReadNode.class)) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
327 if (n.location().getLocationIdentity() == FINAL_LOCATION) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
328 continue;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
329 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
330 Node first = n.lastLocationAccess();
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
331 assert first != null;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
332
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
333 Map<LocationIdentity, Node> killMap = blockToKillMap.get(forKillLocation(first));
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
334 killMap.put(n.location().getLocationIdentity(), first);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
335 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
336
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
337 // distribute and compute killMaps for all blocks
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
338 NewMemoryScheduleClosure closure = new NewMemoryScheduleClosure();
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
339 ReentrantBlockIterator.apply(closure, getCFG().getStartBlock());
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
340 printSchedule("after computing killMaps");
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 assignBlockToNodes(graph, selectedStrategy);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
343 printSchedule("after assign nodes to blocks");
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
344
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
345 sortNodesWithinBlocks(graph, selectedStrategy);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
346 printSchedule("after sorting nodes within blocks");
10894
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
347 } else {
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
348 assignBlockToNodes(graph, selectedStrategy);
af441d477a40 SchedulingPhase: add option for new memory aware scheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10892
diff changeset
349 sortNodesWithinBlocks(graph, selectedStrategy);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
350 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
351 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
352
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
353 private Block forKillLocation(Node n) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
354 Block b = cfg.getNodeToBlock().get(n);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
355 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
356 return b;
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
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
359 private void printSchedule(String desc) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
360 if (dumpSchedule) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
361 TTY.print("=== %s / %s / %s (%s) ===\n", getCFG().getStartBlock().getBeginNode().graph(), selectedStrategy, memsched, desc);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
362 for (Block b : getCFG().getBlocks()) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
363 TTY.print("==== b: %s. ", b);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
364 TTY.print("dom: %s. ", b.getDominator());
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
365 TTY.print("post-dom: %s. ", b.getPostdominator());
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
366 TTY.print("preds: %s. ", b.getPredecessors());
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
367 TTY.print("succs: %s ====\n", b.getSuccessors());
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
368 BlockMap<Map<LocationIdentity, Node>> killMaps = getBlockToKillMap();
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
369 if (killMaps != null) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
370 TTY.print("X block kills: \n");
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
371 for (LocationIdentity locId : killMaps.get(b).keySet()) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
372 TTY.print("X %s killed by %s\n", locId, killMaps.get(b).get(locId));
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
373 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
374 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
375
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
376 if (getBlockToNodesMap().get(b) != null) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
377 for (Node n : nodesFor(b)) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
378 printNode(n);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
379 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
380 } else {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
381 for (Node n : b.getNodes()) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
382 printNode(n);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
383 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
384 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
385 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
386 TTY.print("\n\n");
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
387 TTY.flush();
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
388 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
389 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
390
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
391 private static void printNode(Node n) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
392 TTY.print("%s", n);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
393 if (n instanceof MemoryCheckpoint.Single) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
394 TTY.print(" // kills %s", ((MemoryCheckpoint.Single) n).getLocationIdentity());
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
395 } else if (n instanceof MemoryCheckpoint.Multi) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
396 TTY.print(" // kills ");
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
397 for (LocationIdentity locid : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
398 TTY.print("%s, ", locid);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
399 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
400 } else if (n instanceof FloatingReadNode) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
401 FloatingReadNode frn = (FloatingReadNode) n;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
402 TTY.print(" // from %s", frn.location().getLocationIdentity());
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
403 TTY.print(", lastAccess: %s", frn.lastLocationAccess());
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
404 TTY.print(", 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
405 } else if (n instanceof GuardNode) {
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
406 TTY.print(", guard: %s", ((GuardNode) n).getGuard());
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
407 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
408 TTY.print("\n");
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
409 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
410
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
411 public ControlFlowGraph getCFG() {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
412 return cfg;
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
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
415 /**
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
416 * 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
417 */
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
418 public BlockMap<List<ScheduledNode>> getBlockToNodesMap() {
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
419 return blockToNodesMap;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
420 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
421
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
422 public BlockMap<Map<LocationIdentity, Node>> getBlockToKillMap() {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
423 return blockToKillMap;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
424 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
425
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
426 public NodeMap<Map<LocationIdentity, Node>> getMergeToKillMap() {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
427 return mergeToKillMap;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
428 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
429
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
430 /**
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
431 * Gets the nodes in a given block.
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
432 */
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
433 public List<ScheduledNode> nodesFor(Block block) {
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
434 return blockToNodesMap.get(block);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
435 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
436
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
437 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
438 for (Block block : cfg.getBlocks()) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
439 List<ScheduledNode> 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
440 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
441 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
442 }
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
443 blockToNodesMap.put(block, nodes);
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
444 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
445 nodes.add(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
446 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
447 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
448
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
449 for (Node n : graph.getNodes()) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
450 if (n instanceof ScheduledNode) {
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
451 assignBlockToNode((ScheduledNode) n, strategy);
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
452 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
453 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
454 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
455
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
456 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
457 * 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
458 * 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
459 */
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
460 private void assignBlockToNode(ScheduledNode node, SchedulingStrategy strategy) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
461 assert !node.isDeleted();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
462
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
463 Block prevBlock = cfg.getNodeToBlock().get(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
464 if (prevBlock != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
465 return;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
466 }
10892
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 10891
diff changeset
467 // 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
468 // ControlFlowGraph.identifyBlocks
10892
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 10891
diff changeset
469 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
470 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
471 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
472
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
473 Block block;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
474 switch (strategy) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
475 case EARLIEST:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
476 block = earliestBlock(node);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
477 break;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
478 case LATEST:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
479 case LATEST_OUT_OF_LOOPS:
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
480 if (memsched == MemoryScheduling.OPTIMAL && node instanceof FloatingReadNode && ((FloatingReadNode) node).location().getLocationIdentity() != FINAL_LOCATION) {
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
481 block = optimalBlock((FloatingReadNode) node, strategy);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
482 } else {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
483 block = latestBlock(node, strategy);
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
484 if (block == null) {
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
485 block = earliestBlock(node);
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
486 } else if (strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS && !(node instanceof VirtualObjectNode)) {
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
487 // schedule at the latest position possible in the outermost loop possible
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
488 Block earliestBlock = earliestBlock(node);
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
489 Block before = block;
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
490 block = scheduleOutOfLoops(node, block, earliestBlock);
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
491 if (!earliestBlock.dominates(block)) {
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
492 throw new SchedulingError("%s: Graph cannot be scheduled : inconsistent for %s, %d usages, (%s needs to dominate %s (before %s))", node.graph(), node,
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
493 node.usages().count(), earliestBlock, block, before);
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
494 }
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
495 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
496 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
497 break;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
498 default:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
499 throw new GraalInternalError("unknown scheduling strategy");
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
500 }
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
501 assert earliestBlock(node).dominates(block) : "node " + node + " in block " + block + " is not dominated by earliest " + earliestBlock(node);
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
502 cfg.getNodeToBlock().set(node, block);
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
503 blockToNodesMap.get(block).add(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
504 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
505
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
506 /**
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
507 * this method tries to find the latest position for a read, by taking the information gathered
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
508 * by {@link NewMemoryScheduleClosure} into account.
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
509 *
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
510 * The idea is to iterate the dominator tree starting with the latest schedule of the read.
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
511 *
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
512 * <pre>
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
513 * U upperbound block, defined by last access location of the floating read
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
514 * &#9650;
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
515 * E earliest block
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
516 * &#9650;
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
517 * O optimal block, first block that contains a kill of the read's location
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
518 * &#9650;
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
519 * 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
520 * </pre>
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
521 *
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
522 * i.e. <code>upperbound `dom` earliest `dom` optimal `dom` latest</code>. However, there're
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
523 * cases where <code>earliest `dom` optimal</code> is not true, because the position is
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
524 * (impliclitly) bounded by an anchor of the read's guard. In such cases, the earliest schedule
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
525 * is taken.
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
526 *
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
527 */
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
528 private Block optimalBlock(FloatingReadNode n, SchedulingStrategy strategy) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
529 assert memsched == MemoryScheduling.OPTIMAL;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
530
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
531 LocationIdentity locid = n.location().getLocationIdentity();
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
532 assert locid != FINAL_LOCATION;
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
533
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
534 Node upperBound = n.lastLocationAccess();
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
535 Block upperBoundBlock = forKillLocation(upperBound);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
536 Block earliestBlock = earliestBlock(n);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
537 assert upperBoundBlock.dominates(earliestBlock) : "upper bound (" + upperBoundBlock + ") should dominate earliest (" + earliestBlock + ")";
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
538
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
539 Block currentBlock = latestBlock(n, strategy);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
540 assert currentBlock != null && earliestBlock.dominates(currentBlock) : "earliest (" + earliestBlock + ") should dominate latest block (" + currentBlock + ")";
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
541 Block previousBlock = currentBlock;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
542
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
543 if (dumpSchedule) {
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
544 TTY.print("processing %s (accessing %s): latest %s, earliest %s, upper bound %s (%s)\n", n, locid, currentBlock, earliestBlock, upperBoundBlock, upperBound);
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
545 }
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
546
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
547 int iterations = 0;
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
548 // iterate the dominator tree
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
549 while (true) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
550 iterations++;
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
551 assert earliestBlock.dominates(previousBlock) : "iterations: " + iterations;
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
552 Node lastKill = blockToKillMap.get(currentBlock).get(locid);
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
553 boolean isAtEarliest = earliestBlock == previousBlock && previousBlock != currentBlock;
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
554
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
555 if (lastKill.equals(upperBound)) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
556 // assign node to the block which kills the location
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
557
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
558 boolean outOfLoop = false;
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
559
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
560 // schedule read out of the loop if possible, in terms of killMaps and earliest
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
561 // schedule
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
562 if (currentBlock != earliestBlock && previousBlock != earliestBlock) {
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
563 assert earliestBlock.dominates(currentBlock);
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
564 Block t = currentBlock;
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
565 while (t.getLoop() != null && t.getDominator() != null && earliestBlock.dominates(t)) {
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
566 Block dom = t.getDominator();
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
567 if (dom.getLoopDepth() < currentBlock.getLoopDepth() && blockToKillMap.get(dom).get(locid) == upperBound && earliestBlock.dominates(dom)) {
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
568 printIterations(iterations, "moved out of loop, from " + currentBlock + " to " + dom);
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
569 previousBlock = currentBlock = dom;
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
570 outOfLoop = true;
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
571 }
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
572 t = dom;
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
573 }
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
574 }
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
575
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
576 if (!outOfLoop && previousBlock.getBeginNode() instanceof MergeNode) {
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
577 // merges kill locations right at the beginning of a block. if a merge is the
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
578 // killing node, we assign it to the dominating node.
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
579
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
580 MergeNode merge = (MergeNode) previousBlock.getBeginNode();
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
581 Node killer = getMergeToKillMap().get(merge).get(locid);
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
582
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
583 if (killer != null && killer == merge) {
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
584 // check if we violate earliest schedule condition
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
585 if (isAtEarliest) {
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
586 printIterations(iterations, "earliest bound in merge: " + earliestBlock);
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
587 return earliestBlock;
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
588 }
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
589 printIterations(iterations, "kill by merge: " + currentBlock);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
590 return currentBlock;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
591 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
592 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
593
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
594 // current block matches last access, that means the previous (dominated) block
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
595 // kills the location, therefore schedule read to previous block.
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
596 printIterations(iterations, "regular kill: " + previousBlock);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
597 return previousBlock;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
598 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
599
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
600 if (isAtEarliest) {
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
601 printIterations(iterations, "earliest bound: " + earliestBlock);
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
602 return earliestBlock;
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
603 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
604
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
605 if (upperBoundBlock == currentBlock) {
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
606 printIterations(iterations, "upper bound: " + currentBlock + ", previous: " + previousBlock);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
607 return currentBlock;
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
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
610 previousBlock = currentBlock;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
611 currentBlock = currentBlock.getDominator();
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
612 assert currentBlock != null;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
613 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
614 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
615
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
616 private void printIterations(int iterations, String desc) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
617 if (dumpSchedule) {
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
618 TTY.print("iterations: %d, %s\n", iterations, desc);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
619 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
620 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
621
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
622 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
623 * 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
624 * dominator of all usages. To do so all usages are also assigned to blocks.
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
625 *
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
626 * @param strategy
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
627 */
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
628 private Block latestBlock(ScheduledNode node, SchedulingStrategy strategy) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
629 CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(null);
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
630 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
631 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
632 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
633 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
634 cdbc.apply(cfg.getNodeToBlock().get(succ));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
635 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
636 ensureScheduledUsages(node, strategy);
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
637 for (Node usage : node.usages()) {
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
638 blocksForUsage(node, usage, cdbc, strategy);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
639 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
640 List<FixedNode> usages = phantomUsages.get(node);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
641 if (usages != null) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
642 for (FixedNode usage : usages) {
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
643 if (cfg.getNodeToBlock().get(usage) == 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
644 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
645 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
646 cdbc.apply(cfg.getNodeToBlock().get(usage));
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
647 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
648 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
649
10920
9802c478a26c NewMemoryAwareScheduling: fix out of loop scheduling for floating reads (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10919
diff changeset
650 assert cdbc.block == null || earliestBlock(node).dominates(cdbc.block) : "failed to find correct latest schedule for " + node + ". cdbc: " + cdbc.block + ", earliest: " + earliestBlock(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
651 return cdbc.block;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
652 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
653
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
654 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
655 * 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
656 * {@link #apply(Block)} method.
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
657 */
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
658 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
659
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
660 public Block block;
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
661
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
662 public CommonDominatorBlockClosure(Block block) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
663 this.block = block;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
664 }
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
665
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
666 @Override
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
667 public void apply(Block newBlock) {
10609
5f016460f95b scheduling: remove duplicated code
Bernhard Urban <bernhard.urban@jku.at>
parents: 10490
diff changeset
668 this.block = commonDominator(this.block, newBlock);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
669 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
670 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
671
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
672 /**
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
673 * 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
674 */
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
675 private Block earliestBlock(Node node) {
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
676 Block earliest = cfg.getNodeToBlock().get(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
677 if (earliest != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
678 return earliest;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
679 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
680 earliest = earliestCache.get(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
681 if (earliest != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
682 return earliest;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
683 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
684 /*
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
685 * 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
686 * 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
687 * 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
688 * that is dominated by all other input blocks.
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
689 *
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
690 * While iterating over the inputs a set of dominator blocks of the current earliest
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
691 * placement is maintained. When the block of an input is not within this set, it becomes
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
692 * the current earliest placement and the list of dominator blocks is updated.
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
693 */
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
694 BitSet dominators = new BitSet(cfg.getBlocks().length);
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
695
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
696 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
697 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
698 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
699 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
700 assert input instanceof ValueNode;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
701 Block inputEarliest;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
702 if (input instanceof InvokeWithExceptionNode) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
703 inputEarliest = cfg.getNodeToBlock().get(((InvokeWithExceptionNode) input).next());
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
704 } else {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
705 inputEarliest = earliestBlock(input);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
706 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
707 if (!dominators.get(inputEarliest.getId())) {
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
708 earliest = inputEarliest;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
709 do {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
710 dominators.set(inputEarliest.getId());
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
711 inputEarliest = inputEarliest.getDominator();
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
712 } while (inputEarliest != null && !dominators.get(inputEarliest.getId()));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
713 }
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 if (earliest == null) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
716 earliest = cfg.getStartBlock();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
717 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
718 earliestCache.set(node, earliest);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
719 return earliest;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
720 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
721
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
722 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
723 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
724 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
725 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
726 Block cur = latestBlock;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
727 Block result = latestBlock;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
728 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
729 Block dom = cur.getDominator();
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
730 if (dom.getLoopDepth() < result.getLoopDepth()) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
731 result = dom;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
732 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
733 cur = dom;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
734 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
735 return result;
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
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
738 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
739 * 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
740 * complex than just taking the usage's block because of of PhiNodes and FrameStates.
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
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 * @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
743 * @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
744 * @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
745 */
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
746 private void blocksForUsage(ScheduledNode 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
747 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
748 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
749 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
750
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
751 if (usage instanceof PhiNode) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
752 // 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
753 // the PhiNode input.
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
754 // 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
755 // usage.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
756 PhiNode phi = (PhiNode) usage;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
757 MergeNode merge = phi.merge();
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
758 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
759 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
760 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
761 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
762 for (int i = 0; i < phi.valueCount(); ++i) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
763 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
764 if (mergeBlock.getPredecessorCount() <= i) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
765 TTY.println(merge.toString());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
766 TTY.println(phi.toString());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
767 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
768 TTY.println(mergeBlock.getPredecessors().toString());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
769 TTY.println(phi.inputs().toString());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
770 TTY.println("value count: " + phi.valueCount());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
771 }
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4525
diff changeset
772 closure.apply(mergeBlock.getPredecessors().get(i));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
773 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
774 }
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
775 } else if (usage instanceof VirtualState) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
776 // 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
777 // called for PhiNodes.
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
778 for (Node unscheduledUsage : usage.usages()) {
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
779 if (unscheduledUsage instanceof VirtualState) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
780 // 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
781 // FrameState was the actual usage, by recursing.
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
782 blocksForUsage(node, unscheduledUsage, closure, strategy);
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
783 } else if (unscheduledUsage instanceof MergeNode) {
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
784 // Only FrameStates can be connected to MergeNodes.
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
785 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
786 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
787 }
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
788 // If a FrameState belongs to a MergeNode then it's inputs will be placed at the
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
789 // common dominator of all EndNodes.
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
790 for (Node pred : unscheduledUsage.cfgPredecessors()) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
791 closure.apply(cfg.getNodeToBlock().get(pred));
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
792 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
793 } else {
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
794 // For the time being, only FrameStates can be connected to StateSplits.
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
795 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
796 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
797 }
8957
1af9b5d75139 Move framestate assignement to the hir
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 8950
diff changeset
798 if (!(unscheduledUsage instanceof StateSplit || unscheduledUsage instanceof DeoptimizingNode)) {
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
799 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
800 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
801 // Otherwise: Put the input into the same block as the usage.
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
802 assignBlockToNode((ScheduledNode) unscheduledUsage, strategy);
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
803 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
804 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
805 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
806 } else {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
807 // All other types of usages: Put the input into the same block as the usage.
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
808 assignBlockToNode((ScheduledNode) usage, strategy);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
809 closure.apply(cfg.getNodeToBlock().get(usage));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
810 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
811 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
812
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
813 private void ensureScheduledUsages(Node node, SchedulingStrategy strategy) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
814 for (Node usage : node.usages().filter(ScheduledNode.class)) {
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
815 assignBlockToNode((ScheduledNode) usage, strategy);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
816 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
817 // now true usages are ready
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
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
820 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
821 NodeBitMap visited = graph.createNodeBitMap();
10921
b73121a215f7 NewMemoryAwareScheduling: create nodebitmap once per graph (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10920
diff changeset
822 NodeBitMap beforeLastLocation = graph.createNodeBitMap();
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
823 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
824 sortNodesWithinBlock(b, visited, beforeLastLocation, strategy);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
825 assert noDuplicatedNodesInBlock(b) : "duplicated nodes in " + b;
3733
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 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
828
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
829 private boolean noDuplicatedNodesInBlock(Block b) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
830 List<ScheduledNode> list = blockToNodesMap.get(b);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
831 HashSet<ScheduledNode> hashset = new HashSet<>(list);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
832 return list.size() == hashset.size();
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
833 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
834
10921
b73121a215f7 NewMemoryAwareScheduling: create nodebitmap once per graph (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10920
diff changeset
835 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
836 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
837 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
838 }
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
839 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
840 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
841 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
842
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
843 List<ScheduledNode> sortedInstructions;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
844 switch (strategy) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
845 case EARLIEST:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
846 sortedInstructions = sortNodesWithinBlockEarliest(b, visited);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
847 break;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
848 case LATEST:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
849 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
850 sortedInstructions = sortNodesWithinBlockLatest(b, visited, beforeLastLocation);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
851 break;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
852 default:
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
853 throw new GraalInternalError("unknown scheduling strategy");
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
854 }
10922
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
855 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
856 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
857 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
858 blockToNodesMap.put(b, sortedInstructions);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
859 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
860
10922
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
861 private static List<ScheduledNode> removeProxies(List<ScheduledNode> list) {
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
862 List<ScheduledNode> result = new ArrayList<>();
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
863 for (ScheduledNode n : list) {
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
864 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
865 result.add(n);
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
866 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
867 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
868 return result;
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
869 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
870
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
871 private static List<ScheduledNode> filterSchedulableNodes(List<ScheduledNode> list) {
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
872 List<ScheduledNode> result = new ArrayList<>();
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
873 for (ScheduledNode n : list) {
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
874 if (!(n instanceof LocalNode) && !(n instanceof PhiNode)) {
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
875 result.add(n);
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
876 }
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 return result;
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
879 }
1d1675f18e85 Scheduling: add assert about nodes in a block after sorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10921
diff changeset
880
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
881 private static boolean sameOrderForFixedNodes(List<ScheduledNode> fixed, List<ScheduledNode> sorted) {
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
882 Iterator<ScheduledNode> fixedIterator = fixed.iterator();
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
883 Iterator<ScheduledNode> sortedIterator = sorted.iterator();
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
884
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
885 while (sortedIterator.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
886 ScheduledNode sortedCurrent = sortedIterator.next();
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
887 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
888 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
889 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
890 }
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
891 }
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
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
894 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
895 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
896 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
897 }
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
898 }
2cdd22e1ac5e SchedulingPhase: check if fixed nodes have the same order before and after sorting a block
Bernhard Urban <bernhard.urban@jku.at>
parents: 10609
diff changeset
899
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 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
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
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
903 /**
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
904 * 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
905 * 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
906 * processed.
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
907 */
10921
b73121a215f7 NewMemoryAwareScheduling: create nodebitmap once per graph (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10920
diff changeset
908 private List<ScheduledNode> sortNodesWithinBlockLatest(Block b, NodeBitMap visited, NodeBitMap beforeLastLocation) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
909 List<ScheduledNode> instructions = blockToNodesMap.get(b);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
910 List<ScheduledNode> sortedInstructions = new ArrayList<>(blockToNodesMap.get(b).size() + 2);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
911 List<FloatingReadNode> reads = new ArrayList<>();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
912
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
913 if (memsched == MemoryScheduling.OPTIMAL) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
914 /*
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
915 * TODO: add assert for invariant
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
916 * "floatingreads occur always after memory checkpoints in unsorted list"
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
917 */
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
918 for (ScheduledNode i : instructions) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
919 if (i instanceof FloatingReadNode) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
920 FloatingReadNode frn = (FloatingReadNode) i;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
921 if (frn.location().getLocationIdentity() != FINAL_LOCATION) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
922 reads.add(frn);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
923 if (nodesFor(b).contains(frn.lastLocationAccess())) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
924 assert !beforeLastLocation.isMarked(frn);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
925 beforeLastLocation.mark(frn);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
926 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
927 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
928 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
929 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
930 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
931 for (ScheduledNode i : instructions) {
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
932 addToLatestSorting(b, i, sortedInstructions, visited, reads, beforeLastLocation);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
933 }
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
934 assert reads.size() == 0 : "not all reads are scheduled";
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
935
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
936 // 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
937 // it).
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
938 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
939 if (lastSorted != b.getEndNode()) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
940 int idx = sortedInstructions.indexOf(b.getEndNode());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
941 boolean canNotMove = false;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
942 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
943 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
944 canNotMove = true;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
945 break;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
946 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
947 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
948 if (canNotMove) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
949 if (b.getEndNode() instanceof ControlSplitNode) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
950 throw new GraalInternalError("Schedule is not possible : needs to move a node after the last node of the block which can not be move").addContext(lastSorted).addContext(
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
951 b.getEndNode());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
952 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
953
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
954 // b.setLastNode(lastSorted);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
955 } else {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
956 sortedInstructions.remove(b.getEndNode());
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
957 sortedInstructions.add(b.getEndNode());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
958 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
959 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
960 return sortedInstructions;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
961 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
962
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
963 private void processKillLocation(Block b, Node node, LocationIdentity identity, List<ScheduledNode> sortedInstructions, NodeBitMap visited, List<FloatingReadNode> reads,
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
964 NodeBitMap beforeLastLocation) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
965 for (FloatingReadNode frn : new ArrayList<>(reads)) { // TODO: change to iterator?
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
966 LocationIdentity readLocation = frn.location().getLocationIdentity();
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
967 assert readLocation != FINAL_LOCATION;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
968 if (frn.lastLocationAccess() == node) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
969 assert identity == ANY_LOCATION || readLocation == identity : "location doesn't match: " + readLocation + ", " + identity;
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
970 beforeLastLocation.clear(frn);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
971 } else if (!beforeLastLocation.isMarked(frn) && (readLocation == identity || (!(node instanceof StartNode) && ANY_LOCATION == identity))) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
972 // TODO: replace instanceof check with object identity check
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
973 reads.remove(frn);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
974 addToLatestSorting(b, frn, sortedInstructions, visited, reads, beforeLastLocation);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
975 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
976 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
977 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
978
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
979 private void addUnscheduledToLatestSorting(Block b, VirtualState state, List<ScheduledNode> sortedInstructions, NodeBitMap visited, List<FloatingReadNode> reads, NodeBitMap beforeLastLocation) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
980 if (state != null) {
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
981 // UnscheduledNodes should never be marked as visited.
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
982 if (visited.isMarked(state)) {
43fb04e78250 modified (some) checks in SchedulePhase to raise a SchedulingError instead of an AssertionError
Doug Simon <doug.simon@oracle.com>
parents: 8920
diff changeset
983 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
984 }
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
985
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
986 for (Node input : state.inputs()) {
5598
a9b615da0cba removed delta-encoding of VirtualObjectState
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
987 if (input instanceof VirtualState) {
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
988 addUnscheduledToLatestSorting(b, (VirtualState) input, sortedInstructions, visited, reads, beforeLastLocation);
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
989 } else {
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
990 addToLatestSorting(b, (ScheduledNode) input, sortedInstructions, visited, reads, beforeLastLocation);
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
991 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
992 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
993 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
994 }
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
995
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
996 private void addToLatestSorting(Block b, ScheduledNode i, List<ScheduledNode> sortedInstructions, NodeBitMap visited, List<FloatingReadNode> reads, NodeBitMap beforeLastLocation) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
997 if (i == null || visited.isMarked(i) || cfg.getNodeToBlock().get(i) != b || i instanceof PhiNode || i instanceof LocalNode) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
998 return;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
999 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1000
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1001 FrameState state = null;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1002 for (Node input : i.inputs()) {
10891
8c0ab217ed00 Scheduling: remove dead code in addToLatestSorting
Bernhard Urban <bernhard.urban@jku.at>
parents: 10890
diff changeset
1003 if (input instanceof FrameState) {
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1004 assert state == null;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1005 state = (FrameState) input;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1006 } else {
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1007 addToLatestSorting(b, (ScheduledNode) input, sortedInstructions, visited, reads, beforeLastLocation);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1008 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1009 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1010 List<FloatingNode> inputs = phantomInputs.get(i);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1011 if (inputs != null) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1012 for (FloatingNode input : inputs) {
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1013 addToLatestSorting(b, input, sortedInstructions, visited, reads, beforeLastLocation);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1014 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1015 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1016
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1017 if (memsched == MemoryScheduling.OPTIMAL && reads.size() != 0) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1018 if (i instanceof MemoryCheckpoint.Single) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1019 LocationIdentity identity = ((MemoryCheckpoint.Single) i).getLocationIdentity();
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1020 processKillLocation(b, i, identity, sortedInstructions, visited, reads, beforeLastLocation);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1021 } else if (i instanceof MemoryCheckpoint.Multi) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1022 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) i).getLocationIdentities()) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1023 processKillLocation(b, i, identity, sortedInstructions, visited, reads, beforeLastLocation);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1024 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1025 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1026 assert MemoryCheckpoint.TypeAssertion.correctType(i);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1027 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1028
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1029 addToLatestSorting(b, (ScheduledNode) i.predecessor(), sortedInstructions, visited, reads, beforeLastLocation);
5591
d52edd1af4c4 SchedulePhase doesn't schedule FrameStates, added documentation, cleanups
Lukas Stadler <lukas.stadler@jku.at>
parents: 5583
diff changeset
1030 visited.mark(i);
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1031 addUnscheduledToLatestSorting(b, state, sortedInstructions, visited, reads, beforeLastLocation);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1032
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1033 // Now predecessors and inputs are scheduled => we can add this node.
10896
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1034 if (!sortedInstructions.contains(i)) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1035 sortedInstructions.add(i);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1036 }
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1037
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1038 if (i instanceof FloatingReadNode) {
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1039 reads.remove(i);
8106edbdeac9 add NewMemoryAwareScheduling (GRAAL-159)
Bernhard Urban <bernhard.urban@jku.at>
parents: 10894
diff changeset
1040 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1041 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1042
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1043 /**
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1044 * 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
1045 * 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
1046 * nodes.
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1047 */
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1048 private List<ScheduledNode> sortNodesWithinBlockEarliest(Block b, NodeBitMap visited) {
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1049 List<ScheduledNode> sortedInstructions = new ArrayList<>(blockToNodesMap.get(b).size() + 2);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1050 addToEarliestSorting(b, b.getEndNode(), sortedInstructions, visited);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1051 Collections.reverse(sortedInstructions);
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1052 return sortedInstructions;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1053 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1054
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1055 private void addToEarliestSorting(Block b, ScheduledNode i, List<ScheduledNode> sortedInstructions, NodeBitMap visited) {
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1056 ScheduledNode instruction = i;
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1057 while (true) {
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1058 if (instruction == null || visited.isMarked(instruction) || cfg.getNodeToBlock().get(instruction) != b || instruction instanceof PhiNode || instruction instanceof LocalNode) {
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1059 return;
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1060 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1061
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1062 visited.mark(instruction);
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1063 for (Node usage : instruction.usages()) {
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1064 if (usage instanceof VirtualState) {
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1065 // only fixed nodes can have VirtualState -> no need to schedule them
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1066 } else {
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1067 if (instruction instanceof LoopExitNode && usage instanceof ProxyNode) {
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1068 // 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
1069 } else {
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1070 addToEarliestSorting(b, (ScheduledNode) usage, sortedInstructions, visited);
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1071 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1072 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1073 }
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1074
9436
ae815a4c112a Rename BeginNode => AbstractBeginNode and make abstract. Introduce concrete subclass BeginNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 8957
diff changeset
1075 if (instruction instanceof AbstractBeginNode) {
8542
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1076 ArrayList<ProxyNode> proxies = (instruction instanceof LoopExitNode) ? new ArrayList<ProxyNode>() : null;
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1077 for (ScheduledNode inBlock : blockToNodesMap.get(b)) {
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1078 if (!visited.isMarked(inBlock)) {
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1079 if (inBlock instanceof ProxyNode) {
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1080 proxies.add((ProxyNode) inBlock);
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1081 } else {
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1082 addToEarliestSorting(b, inBlock, sortedInstructions, visited);
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1083 }
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1084 }
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1085 }
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1086 sortedInstructions.add(instruction);
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1087 if (proxies != null) {
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1088 sortedInstructions.addAll(proxies);
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1089 }
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1090 break;
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1091 } else {
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1092 sortedInstructions.add(instruction);
30a141944bcb tail recursion for SchedulePhase.addToEarliestSorting (fixes StackOverflowErrors)
Lukas Stadler <lukas.stadler@jku.at>
parents: 8394
diff changeset
1093 instruction = (ScheduledNode) instruction.predecessor();
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 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
1096 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1097 }