Mercurial > hg > truffle

annotate graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java @ 2995:00e0c0928e7c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge.
author Thomas Wuerthinger <thomas@wuerthinger.net>
date Thu, 16 Jun 2011 13:45:16 +0200
parents 7ed943d4d730 c6b89544fef5
children 4025f436a2e4
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
1 /*
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
2 * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
4 *
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
7 * published by the Free Software Foundation.
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
8 *
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
13 * accompanied this code).
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
14 *
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
18 *
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
21 * questions.
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
22 */
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
23 package com.oracle.max.graal.compiler.schedule;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
24
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
25 import java.util.*;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
26
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
27 import com.oracle.max.graal.compiler.debug.*;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
28 import com.oracle.max.graal.compiler.ir.*;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
29 import com.oracle.max.graal.compiler.phases.*;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
30 import com.oracle.max.graal.compiler.value.*;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
31 import com.oracle.max.graal.graph.*;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
32 import com.sun.cri.ci.*;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
33
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
34
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
35 public class IdentifyBlocksPhase extends Phase {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
36 private final List<Block> blocks = new ArrayList<Block>();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
37 private NodeMap<Block> nodeToBlock;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
38 private Graph graph;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
39 private boolean scheduleAllNodes;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
40
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
41 public IdentifyBlocksPhase(boolean scheduleAllNodes) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
42 super(scheduleAllNodes ? "FullSchedule" : "PartSchedule");
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
43 this.scheduleAllNodes = scheduleAllNodes;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
44 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
45
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
46
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
47 @Override
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
48 protected void run(Graph graph) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
49 this.graph = graph;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
50 nodeToBlock = graph.createNodeMap();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
51 identifyBlocks();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
52 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
53
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
54 public List<Block> getBlocks() {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
55 return Collections.unmodifiableList(blocks);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
56 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
57
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
58 public NodeMap<Block> getNodeToBlock() {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
59 return nodeToBlock;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
60 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
61
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
62 private Block createBlock() {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
63 Block b = new Block(blocks.size());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
64 blocks.add(b);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
65 return b;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
66 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
67
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
68 private Block assignBlock(Node n) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
69 Block curBlock = nodeToBlock.get(n);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
70 if (curBlock == null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
71 curBlock = createBlock();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
72 return assignBlock(n, curBlock);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
73 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
74 return curBlock;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
75 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
76
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
77
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
78 private Block assignBlock(Node n, Block b) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
79 assert nodeToBlock.get(n) == null;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
80 nodeToBlock.set(n, b);
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
81 for (Node input : n.inputs()) {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
82 if (input instanceof FrameState) {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
83 assert nodeToBlock.get(n) == null;
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
84 nodeToBlock.set(n, b);
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
85 }
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
86 }
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
87
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
88 if (b.firstNode() == null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
89 b.setFirstNode(n);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
90 b.setLastNode(n);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
91 } else {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
92 if (b.lastNode() != null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
93 b.getInstructions().add(b.lastNode());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
94 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
95 b.setLastNode(n);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
96 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
97 b.setLastNode(n);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
98 return b;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
99 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
100
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
101 private Block assignBlockNew(Node n, Block b) {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
102 if (b == null) {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
103 b = createBlock();
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
104 }
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
105
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
106 assert nodeToBlock.get(n) == null;
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
107 nodeToBlock.set(n, b);
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
108 if (b.lastNode() == null) {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
109 b.setFirstNode(n);
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
110 b.setLastNode(n);
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
111 } else {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
112 if (b.firstNode() != b.lastNode()) {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
113 b.getInstructions().add(0, b.firstNode());
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
114 }
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
115 b.setFirstNode(n);
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
116 }
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
117
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
118 return b;
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
119 }
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
120
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
121 public static boolean isFixed(Node n) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
122 return n != null && ((n instanceof FixedNode) || n == n.graph().start());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
123 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
124
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
125 public static boolean isBlockEnd(Node n) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
126 return trueSuccessorCount(n) > 1 || n instanceof Anchor || n instanceof Return || n instanceof Unwind;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
127 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
128
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
129 private void identifyBlocks() {
2968
9133554259c5 Clean up.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2967
diff changeset
130
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
131 // Identify blocks.
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
132 for (Node n : graph.getNodes()) {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
133 if (n != null) {
2976
57c2e3409be7 Fixed merge issues.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2975
diff changeset
134 if (n instanceof EndNode || n instanceof Return || n instanceof Unwind || n instanceof LoopEnd || n instanceof Deoptimize) {
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
135 Block block = null;
2994
7ed943d4d730 Fix checkstyle issues.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2989
diff changeset
136 Node currentNode = n;
7ed943d4d730 Fix checkstyle issues.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2989
diff changeset
137 while (nodeToBlock.get(currentNode) == null) {
7ed943d4d730 Fix checkstyle issues.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2989
diff changeset
138 if (block != null && IdentifyBlocksPhase.trueSuccessorCount(currentNode) > 1) {
2968
9133554259c5 Clean up.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2967
diff changeset
139 // We are at a split node => start a new block.
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
140 block = null;
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
141 }
2994
7ed943d4d730 Fix checkstyle issues.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2989
diff changeset
142 block = assignBlockNew(currentNode, block);
7ed943d4d730 Fix checkstyle issues.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2989
diff changeset
143 if (currentNode.predecessors().size() == 0) {
2968
9133554259c5 Clean up.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2967
diff changeset
144 // Either dead code or at a merge node => stop iteration.
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
145 break;
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
146 }
2994
7ed943d4d730 Fix checkstyle issues.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2989
diff changeset
147 assert currentNode.predecessors().size() == 1 : "preds: " + currentNode;
7ed943d4d730 Fix checkstyle issues.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2989
diff changeset
148 currentNode = currentNode.predecessors().get(0);
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
149 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
150 }
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
151 }
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
152 }
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
153
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
154 // Connect blocks.
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
155 for (Block block : blocks) {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
156 Node n = block.firstNode();
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
157 if (n instanceof Merge) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
158 for (Node usage : n.usages()) {
2981
42681ed31c4d Some LoopCounter work
Gilles Duboscq <gilles.duboscq@oracle.com>
parents: 2946
diff changeset
159 if (usage instanceof Phi || usage instanceof LoopCounter) {
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
160 nodeToBlock.set(usage, block);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
161 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
162 }
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
163 Merge m = (Merge) n;
2984
Gilles Duboscq <gilles.duboscq@oracle.com>
parents: 2976 2983
diff changeset
164 for (int i = 0; i < m.endCount(); ++i) {
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
165 EndNode end = m.endAt(i);
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
166 Block predBlock = nodeToBlock.get(end);
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
167 predBlock.addSuccessor(block);
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
168 }
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
169 } else {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
170 for (Node pred : n.predecessors()) {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
171 if (isFixed(pred)) {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
172 Block predBlock = nodeToBlock.get(pred);
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
173 predBlock.addSuccessor(block);
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
174 }
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
175 }
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
176 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
177 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
178
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
179 for (Node n : graph.getNodes()) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
180 if (n instanceof FrameState) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
181 FrameState f = (FrameState) n;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
182 if (f.predecessors().size() == 1) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
183 Block predBlock = nodeToBlock.get(f.predecessors().get(0));
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
184 assert predBlock != null;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
185 nodeToBlock.set(f, predBlock);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
186 predBlock.getInstructions().add(f);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
187 } else {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
188 assert f.predecessors().size() == 0;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
189 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
190 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
191 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
192
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
193 computeDominators();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
194
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
195
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
196 if (scheduleAllNodes) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
197
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
198 // Add successors of loop end nodes. Makes the graph cyclic.
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
199 for (Block block : blocks) {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
200 Node n = block.firstNode();
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
201 if (n instanceof LoopBegin) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
202 LoopBegin loopBegin = (LoopBegin) n;
2988
2bf5ac3f6fc3 Clean up dead code elimination. Bring simple merge deletion back in.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2976
diff changeset
203 assert loopBegin.loopEnd() != null;
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
204 nodeToBlock.get(loopBegin.loopEnd()).addSuccessor(block);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
205 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
206 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
207
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
208 assignLatestPossibleBlockToNodes();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
209 sortNodesWithinBlocks();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
210 } else {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
211 computeJavaBlocks();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
212 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
213 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
214
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
215 private void computeJavaBlocks() {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
216
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
217 for (Block b : blocks) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
218 computeJavaBlock(b);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
219 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
220 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
221
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
222 private Block computeJavaBlock(Block b) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
223 if (b.javaBlock() == null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
224 if (b.getPredecessors().size() == 0) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
225 b.setJavaBlock(b);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
226 } else if (b.getPredecessors().size() == 1) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
227 Block pred = b.getPredecessors().get(0);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
228 if (pred.getSuccessors().size() > 1) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
229 b.setJavaBlock(b);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
230 } else {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
231 b.setJavaBlock(computeJavaBlock(pred));
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
232 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
233 } else {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
234 Block dominatorBlock = b.getPredecessors().get(0);
2951
0c0e407faa39 another fix to debug info (on-stack parameters), DCE removes unnecessary merges and LoopBegins whose LoopEnd went away
Lukas Stadler <lukas.stadler@jku.at>
parents: 2946
diff changeset
235 for (int i = 1; i < b.getPredecessors().size(); ++i) {
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
236 dominatorBlock = getCommonDominator(dominatorBlock, b.getPredecessors().get(i));
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
237 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
238 CiBitMap blockMap = new CiBitMap(blocks.size());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
239 markPredecessors(b, dominatorBlock, blockMap);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
240
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
241 Block result = dominatorBlock;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
242 L1: for (Block curBlock : blocks) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
243 if (curBlock != b && blockMap.get(curBlock.blockID())) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
244 for (Block succ : curBlock.getSuccessors()) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
245 if (!blockMap.get(succ.blockID())) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
246 result = b;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
247 break L1;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
248 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
249 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
250 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
251 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
252 b.setJavaBlock(result);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
253 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
254 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
255 return b.javaBlock();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
256 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
257
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
258 private void markPredecessors(Block b, Block stopBlock, CiBitMap blockMap) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
259 if (blockMap.get(b.blockID())) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
260 return;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
261 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
262 blockMap.set(b.blockID());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
263 if (b != stopBlock) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
264 for (Block pred : b.getPredecessors()) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
265 markPredecessors(pred, stopBlock, blockMap);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
266 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
267 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
268 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
269
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
270 private void assignLatestPossibleBlockToNodes() {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
271 for (Node n : graph.getNodes()) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
272 assignLatestPossibleBlockToNode(n);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
273 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
274 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
275
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
276 private Block assignLatestPossibleBlockToNode(Node n) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
277 if (n == null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
278 return null;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
279 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
280
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
281 Block prevBlock = nodeToBlock.get(n);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
282 if (prevBlock != null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
283 return prevBlock;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
284 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
285
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
286 Block block = null;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
287 for (Node succ : n.successors()) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
288 block = getCommonDominator(block, assignLatestPossibleBlockToNode(succ));
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
289 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
290 for (Node usage : n.usages()) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
291 if (usage instanceof Phi) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
292 Phi phi = (Phi) usage;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
293 Merge merge = phi.merge();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
294 Block mergeBlock = nodeToBlock.get(merge);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
295 assert mergeBlock != null : "no block for merge " + merge.id();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
296 for (int i = 0; i < phi.valueCount(); ++i) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
297 if (phi.valueAt(i) == n) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
298 if (mergeBlock.getPredecessors().size() == 0) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
299 TTY.println(merge.toString());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
300 TTY.println(phi.toString());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
301 TTY.println(merge.predecessors().toString());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
302 TTY.println("value count: " + phi.valueCount());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
303 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
304 block = getCommonDominator(block, mergeBlock.getPredecessors().get(i));
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
305 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
306 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
307 } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
308 Merge merge = ((FrameState) usage).block();
2984
Gilles Duboscq <gilles.duboscq@oracle.com>
parents: 2976 2983
diff changeset
309 for (int i = 0; i < merge.endCount(); ++i) {
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
310 EndNode pred = merge.endAt(i);
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
311 block = getCommonDominator(block, nodeToBlock.get(pred));
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
312 }
2981
42681ed31c4d Some LoopCounter work
Gilles Duboscq <gilles.duboscq@oracle.com>
parents: 2946
diff changeset
313 } else if (usage instanceof LoopCounter) {
42681ed31c4d Some LoopCounter work
Gilles Duboscq <gilles.duboscq@oracle.com>
parents: 2946
diff changeset
314 LoopCounter counter = (LoopCounter) usage;
2992
c6b89544fef5 Fix scheduling around loopcounters
Gilles Duboscq <gilles.duboscq@oracle.com>
parents: 2989
diff changeset
315 if (n == counter.init() || n == counter.stride()) {
2981
42681ed31c4d Some LoopCounter work
Gilles Duboscq <gilles.duboscq@oracle.com>
parents: 2946
diff changeset
316 LoopBegin loopBegin = counter.loopBegin();
42681ed31c4d Some LoopCounter work
Gilles Duboscq <gilles.duboscq@oracle.com>
parents: 2946
diff changeset
317 Block mergeBlock = nodeToBlock.get(loopBegin);
2983
11dfbb40ca69 LoopCounter, WIP
Gilles Duboscq <gilles.duboscq@oracle.com>
parents: 2982
diff changeset
318 block = getCommonDominator(block, mergeBlock.dominator());
2981
42681ed31c4d Some LoopCounter work
Gilles Duboscq <gilles.duboscq@oracle.com>
parents: 2946
diff changeset
319 }
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
320 } else {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
321 block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage));
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
322 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
323 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
324
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
325 nodeToBlock.set(n, block);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
326 if (block != null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
327 block.getInstructions().add(n);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
328 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
329 return block;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
330 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
331
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
332 private Block getCommonDominator(Block a, Block b) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
333 if (a == null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
334 return b;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
335 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
336 if (b == null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
337 return a;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
338 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
339 return commonDominator(a, b);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
340 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
341
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
342 private void sortNodesWithinBlocks() {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
343 NodeBitMap map = graph.createNodeBitMap();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
344 for (Block b : blocks) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
345 sortNodesWithinBlocks(b, map);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
346 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
347 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
348
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
349 private void sortNodesWithinBlocks(Block b, NodeBitMap map) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
350 List<Node> instructions = b.getInstructions();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
351 List<Node> sortedInstructions = new ArrayList<Node>();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
352 assert !map.isMarked(b.firstNode()) && nodeToBlock.get(b.firstNode()) == b;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
353
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
354 boolean scheduleFirst = true;
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
355 assert !instructions.contains(b.lastNode());
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
356 assert !instructions.contains(b.firstNode());
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
357
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
358 if (b.firstNode() == b.lastNode()) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
359 Node node = b.firstNode();
2985
ce38e01aa596 LoopEnd should be scheduled at the end of a block
Gilles Duboscq <gilles.duboscq@oracle.com>
parents: 2984
diff changeset
360 if (!(node instanceof Merge) || node instanceof LoopEnd) {
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
361 scheduleFirst = false;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
362 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
363 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
364 if (scheduleFirst) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
365 addToSorting(b, b.firstNode(), sortedInstructions, map);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
366 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
367 for (Node i : instructions) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
368 addToSorting(b, i, sortedInstructions, map);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
369 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
370 addToSorting(b, b.lastNode(), sortedInstructions, map);
2984
Gilles Duboscq <gilles.duboscq@oracle.com>
parents: 2976 2983
diff changeset
371 assert sortedInstructions.get(sortedInstructions.size() - 1) == b.lastNode() : "lastNode=" + b.lastNode() + ", firstNode=" + b.firstNode() + ", sorted(sz-1)=" + sortedInstructions.get(sortedInstructions.size() - 1);
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
372 b.setInstructions(sortedInstructions);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
373 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
374
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
375 private void addToSorting(Block b, Node i, List<Node> sortedInstructions, NodeBitMap map) {
2981
42681ed31c4d Some LoopCounter work
Gilles Duboscq <gilles.duboscq@oracle.com>
parents: 2946
diff changeset
376 if (i == null || map.isMarked(i) || nodeToBlock.get(i) != b || i instanceof Phi || i instanceof Local || i instanceof LoopCounter) {
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
377 return;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
378 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
379
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
380 FrameState state = null;
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
381 for (Node input : i.inputs()) {
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
382 // if (input instanceof FrameState) {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
383 // state = (FrameState) input;
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
384 // } else {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
385 addToSorting(b, input, sortedInstructions, map);
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
386 // }
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
387 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
388
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
389 for (Node pred : i.predecessors()) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
390 addToSorting(b, pred, sortedInstructions, map);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
391 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
392
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
393 map.mark(i);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
394
2967
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
395 if (state != null) {
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
396 addToSorting(b, state, sortedInstructions, map);
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
397 }
60a58915c94d Removed next pointer from EndNode to Merge. New scheduler.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2946
diff changeset
398
2945
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
399 for (Node succ : i.successors()) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
400 if (succ instanceof FrameState) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
401 addToSorting(b, succ, sortedInstructions, map);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
402 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
403 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
404
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
405 // Now predecessors and inputs are scheduled => we can add this node.
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
406 if (!(i instanceof FrameState)) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
407 sortedInstructions.add(i);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
408 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
409 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
410
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
411 private void computeDominators() {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
412 Block dominatorRoot = nodeToBlock.get(graph.start());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
413 assert dominatorRoot.getPredecessors().size() == 0;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
414 CiBitMap visited = new CiBitMap(blocks.size());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
415 visited.set(dominatorRoot.blockID());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
416 LinkedList<Block> workList = new LinkedList<Block>();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
417 workList.add(dominatorRoot);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
418
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
419 while (!workList.isEmpty()) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
420 Block b = workList.remove();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
421
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
422 List<Block> predecessors = b.getPredecessors();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
423 if (predecessors.size() == 1) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
424 b.setDominator(predecessors.get(0));
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
425 } else if (predecessors.size() > 0) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
426 boolean delay = false;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
427 for (Block pred : predecessors) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
428 if (pred != dominatorRoot && pred.dominator() == null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
429 delay = true;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
430 break;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
431 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
432 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
433
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
434 if (delay) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
435 workList.add(b);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
436 continue;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
437 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
438
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
439 Block dominator = null;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
440 for (Block pred : predecessors) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
441 if (dominator == null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
442 dominator = pred;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
443 } else {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
444 dominator = commonDominator(dominator, pred);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
445 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
446 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
447 b.setDominator(dominator);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
448 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
449
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
450 for (Block succ : b.getSuccessors()) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
451 if (!visited.get(succ.blockID())) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
452 visited.set(succ.blockID());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
453 workList.add(succ);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
454 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
455 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
456 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
457 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
458
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
459 public Block commonDominator(Block a, Block b) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
460 CiBitMap bitMap = new CiBitMap(blocks.size());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
461 Block cur = a;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
462 while (cur != null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
463 bitMap.set(cur.blockID());
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
464 cur = cur.dominator();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
465 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
466
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
467 cur = b;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
468 while (cur != null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
469 if (bitMap.get(cur.blockID())) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
470 return cur;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
471 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
472 cur = cur.dominator();
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
473 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
474
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
475 throw new IllegalStateException("no common dominator between " + a + " and " + b);
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
476 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
477
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
478 public static int trueSuccessorCount(Node n) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
479 if (n == null) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
480 return 0;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
481 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
482 int i = 0;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
483 for (Node s : n.successors()) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
484 if (isFixed(s)) {
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
485 i++;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
486 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
487 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
488 return i;
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
489 }
41318fcb6b56 Added two algorithms for identifying Java-level blocks.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff changeset
490 }