Mercurial > hg > graal-jvmci-8
annotate graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2723:173067211acb
Removed two more BlockBegin flags.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Thu, 19 May 2011 16:44:05 +0200 |
parents | 23d0bcfa3c84 |
children | 03b80fb10ae9 |
rev | line source |
---|---|
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
1 /* |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
2 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
4 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
5 * This code is free software; you can redistribute it and/or modify it |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
6 * under the terms of the GNU General Public License version 2 only, as |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
7 * published by the Free Software Foundation. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
8 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
9 * This code is distributed in the hope that it will be useful, but WITHOUT |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
12 * version 2 for more details (a copy is included in the LICENSE file that |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
13 * accompanied this code). |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
14 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
15 * You should have received a copy of the GNU General Public License version |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
16 * 2 along with this work; if not, write to the Free Software Foundation, |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
18 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
21 * questions. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
22 */ |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
23 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
24 package com.sun.c1x.ir; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
25 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
26 import java.util.*; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
27 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
28 import com.sun.c1x.*; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
29 import com.sun.c1x.debug.*; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
30 import com.sun.c1x.util.*; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
31 import com.sun.cri.ci.*; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
32 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
33 public final class ComputeLinearScanOrder { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
34 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
35 private final int maxBlockId; // the highest blockId of a block |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
36 private int numBlocks; // total number of blocks (smaller than maxBlockId) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
37 private int numLoops; // total number of loops |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
38 private boolean iterativeDominators; // method requires iterative computation of dominators |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
39 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
40 List<BlockBegin> linearScanOrder; // the resulting list of blocks in correct order |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
41 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
42 final CiBitMap visitedBlocks; // used for recursive processing of blocks |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
43 final CiBitMap activeBlocks; // used for recursive processing of blocks |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
44 final int[] forwardBranches; // number of incoming forward branches for each block |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
45 final List<BlockBegin> loopEndBlocks; // list of all loop end blocks collected during countEdges |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
46 BitMap2D loopMap; // two-dimensional bit set: a bit is set if a block is contained in a loop |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
47 final List<BlockBegin> workList; // temporary list (used in markLoops and computeOrder) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
48 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
49 // accessors for visitedBlocks and activeBlocks |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
50 private void initVisited() { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
51 activeBlocks.clearAll(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
52 visitedBlocks.clearAll(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
53 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
54 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
55 private boolean isVisited(BlockBegin b) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
56 return visitedBlocks.get(b.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
57 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
58 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
59 private boolean isActive(BlockBegin b) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
60 return activeBlocks.get(b.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
61 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
62 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
63 private void setVisited(BlockBegin b) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
64 assert !isVisited(b) : "already set"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
65 visitedBlocks.set(b.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
66 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
67 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
68 private void setActive(BlockBegin b) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
69 assert !isActive(b) : "already set"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
70 activeBlocks.set(b.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
71 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
72 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
73 private void clearActive(BlockBegin b) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
74 assert isActive(b) : "not already"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
75 activeBlocks.clear(b.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
76 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
77 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
78 // accessors for forwardBranches |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
79 private void incForwardBranches(BlockBegin b) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
80 forwardBranches[b.blockID]++; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
81 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
82 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
83 private int decForwardBranches(BlockBegin b) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
84 return --forwardBranches[b.blockID]; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
85 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
86 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
87 // accessors for loopMap |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
88 private boolean isBlockInLoop(int loopIdx, BlockBegin b) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
89 return loopMap.at(loopIdx, b.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
90 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
91 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
92 private void setBlockInLoop(int loopIdx, BlockBegin b) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
93 loopMap.setBit(loopIdx, b.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
94 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
95 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
96 private void clearBlockInLoop(int loopIdx, int blockId) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
97 loopMap.clearBit(loopIdx, blockId); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
98 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
99 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
100 // accessors for final result |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
101 public List<BlockBegin> linearScanOrder() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
102 return linearScanOrder; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
103 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
104 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
105 public int numLoops() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
106 return numLoops; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
107 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
108 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
109 public ComputeLinearScanOrder(int maxBlockId, BlockBegin startBlock) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
110 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
111 this.maxBlockId = maxBlockId; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
112 visitedBlocks = new CiBitMap(maxBlockId); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
113 activeBlocks = new CiBitMap(maxBlockId); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
114 forwardBranches = new int[maxBlockId]; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
115 loopEndBlocks = new ArrayList<BlockBegin>(8); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
116 workList = new ArrayList<BlockBegin>(8); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
117 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
118 countEdges(startBlock, null); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
119 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
120 computeOrder(startBlock); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
121 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
122 printBlocks(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
123 assert verify(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
124 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
125 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
126 /** |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
127 * Traverses the CFG to analyze block and edge info. The analysis performed is: |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
128 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
129 * 1. Count of total number of blocks. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
130 * 2. Count of all incoming edges and backward incoming edges. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
131 * 3. Number loop header blocks. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
132 * 4. Create a list with all loop end blocks. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
133 */ |
2707
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
134 private void countEdges(final BlockBegin cur, BlockBegin parent) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
135 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
136 TTY.println("Counting edges for block B%d%s", cur.blockID, parent == null ? "" : " coming from B" + parent.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
137 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
138 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
139 if (isActive(cur)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
140 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
141 TTY.println("backward branch"); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
142 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
143 assert isVisited(cur) : "block must be visited when block is active"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
144 assert parent != null : "must have parent"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
145 |
2723
173067211acb
Removed two more BlockBegin flags.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2722
diff
changeset
|
146 //cur.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader); |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
147 |
2723
173067211acb
Removed two more BlockBegin flags.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2722
diff
changeset
|
148 //parent.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd); |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
149 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
150 loopEndBlocks.add(parent); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
151 return; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
152 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
153 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
154 // increment number of incoming forward branches |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
155 incForwardBranches(cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
156 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
157 if (isVisited(cur)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
158 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
159 TTY.println("block already visited"); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
160 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
161 return; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
162 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
163 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
164 numBlocks++; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
165 setVisited(cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
166 setActive(cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
167 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
168 // recursive call for all successors |
2707
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
169 cur.allSuccessorsDo(true, new BlockClosure() { |
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
170 public void apply(BlockBegin block) { |
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
171 countEdges(block, cur); |
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
172 } |
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
173 }); |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
174 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
175 clearActive(cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
176 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
177 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
178 TTY.println("Finished counting edges for block B%d", cur.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
179 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
180 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
181 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
182 private int computeWeight(BlockBegin cur) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
183 BlockBegin singleSux = null; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
184 if (cur.numberOfSux() == 1) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
185 singleSux = cur.suxAt(0); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
186 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
187 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
188 // limit loop-depth to 15 bit (only for security reason, it will never be so big) |
2718
c1ce2a53d6c3
Attempt to remove dependency between backend and BlockBegin.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2717
diff
changeset
|
189 int loopDepth = 0; // TODO(tw): Assign loop depth |
c1ce2a53d6c3
Attempt to remove dependency between backend and BlockBegin.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2717
diff
changeset
|
190 int weight = (loopDepth & 0x7FFF) << 16; |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
191 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
192 int curBit = 15; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
193 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
194 // exceptions should not be thrown in normal control flow, so these blocks |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
195 // are added as late as possible |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
196 if (!(cur.end() instanceof Throw) && (singleSux == null || !(singleSux.end() instanceof Throw))) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
197 weight |= (1 << curBit); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
198 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
199 curBit--; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
200 if (!(cur.end() instanceof Return) && (singleSux == null || !(singleSux.end() instanceof Return))) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
201 weight |= (1 << curBit); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
202 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
203 curBit--; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
204 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
205 // guarantee that weight is > 0 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
206 weight |= 1; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
207 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
208 assert curBit >= 0 : "too many flags"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
209 assert weight > 0 : "weight cannot become negative"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
210 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
211 return weight; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
212 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
213 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
214 private boolean readyForProcessing(BlockBegin cur) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
215 // Discount the edge just traveled. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
216 // When the number drops to zero, all forward branches were processed |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
217 if (decForwardBranches(cur) != 0) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
218 return false; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
219 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
220 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
221 assert !linearScanOrder.contains(cur) : "block already processed (block can be ready only once)"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
222 assert !workList.contains(cur) : "block already in work-list (block can be ready only once)"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
223 return true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
224 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
225 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
226 private void sortIntoWorkList(BlockBegin cur) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
227 assert !workList.contains(cur) : "block already in work list"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
228 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
229 int curWeight = computeWeight(cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
230 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
231 // the linearScanNumber is used to cache the weight of a block |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
232 cur.setLinearScanNumber(curWeight); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
233 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
234 if (C1XOptions.StressLinearScan) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
235 workList.add(0, cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
236 return; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
237 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
238 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
239 workList.add(null); // provide space for new element |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
240 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
241 int insertIdx = workList.size() - 1; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
242 while (insertIdx > 0 && workList.get(insertIdx - 1).linearScanNumber() > curWeight) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
243 workList.set(insertIdx, workList.get(insertIdx - 1)); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
244 insertIdx--; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
245 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
246 workList.set(insertIdx, cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
247 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
248 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
249 TTY.println("Sorted B%d into worklist. new worklist:", cur.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
250 for (int i = 0; i < workList.size(); i++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
251 TTY.println(String.format("%8d B%02d weight:%6x", i, workList.get(i).blockID, workList.get(i).linearScanNumber())); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
252 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
253 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
254 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
255 for (int i = 0; i < workList.size(); i++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
256 assert workList.get(i).linearScanNumber() > 0 : "weight not set"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
257 assert i == 0 || workList.get(i - 1).linearScanNumber() <= workList.get(i).linearScanNumber() : "incorrect order in worklist"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
258 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
259 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
260 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
261 private void appendBlock(BlockBegin cur) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
262 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
263 TTY.println("appending block B%d (weight 0x%06x) to linear-scan order", cur.blockID, cur.linearScanNumber()); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
264 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
265 assert !linearScanOrder.contains(cur) : "cannot add the same block twice"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
266 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
267 // currently, the linear scan order and code emit order are equal. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
268 // therefore the linearScanNumber and the weight of a block must also |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
269 // be equal. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
270 cur.setLinearScanNumber(linearScanOrder.size()); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
271 linearScanOrder.add(cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
272 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
273 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
274 private void computeOrder(BlockBegin startBlock) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
275 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
276 TTY.println("----- computing final block order"); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
277 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
278 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
279 // the start block is always the first block in the linear scan order |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
280 linearScanOrder = new ArrayList<BlockBegin>(numBlocks); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
281 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
282 // start processing with standard entry block |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
283 assert workList.isEmpty() : "list must be empty before processing"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
284 |
2657
4a6518c4d17d
Removed need for base instruction. Cleanup.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2653
diff
changeset
|
285 if (readyForProcessing(startBlock)) { |
4a6518c4d17d
Removed need for base instruction. Cleanup.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2653
diff
changeset
|
286 sortIntoWorkList(startBlock); |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
287 } else { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
288 throw new CiBailout("the stdEntry must be ready for processing (otherwise, the method has no start block)"); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
289 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
290 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
291 do { |
2707
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
292 final BlockBegin cur = workList.remove(workList.size() - 1); |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
293 appendBlock(cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
294 |
2707
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
295 cur.allSuccessorsDo(false, new BlockClosure() { |
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
296 public void apply(BlockBegin block) { |
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
297 if (readyForProcessing(block)) { |
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
298 sortIntoWorkList(block); |
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
299 } |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
300 } |
2707
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
301 }); |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
302 } while (workList.size() > 0); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
303 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
304 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
305 public void printBlocks() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
306 if (C1XOptions.TraceLinearScanLevel >= 1) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
307 TTY.println("----- linear-scan block order:"); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
308 for (BlockBegin cur : linearScanOrder) { |
2718
c1ce2a53d6c3
Attempt to remove dependency between backend and BlockBegin.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2717
diff
changeset
|
309 TTY.print(String.format("%4d: B%02d loop: %2d depth: %2d", cur.linearScanNumber(), cur.blockID, -1, -1)); |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
310 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
311 if (cur.numberOfPreds() > 0) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
312 TTY.print(" preds: "); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
313 for (int j = 0; j < cur.numberOfPreds(); j++) { |
2707
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
314 BlockBegin pred = cur.predAt(j).block(); |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
315 TTY.print("B%d ", pred.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
316 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
317 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
318 if (cur.numberOfSux() > 0) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
319 TTY.print(" sux: "); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
320 for (int j = 0; j < cur.numberOfSux(); j++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
321 BlockBegin sux = cur.suxAt(j); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
322 TTY.print("B%d ", sux.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
323 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
324 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
325 TTY.println(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
326 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
327 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
328 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
329 |
2653
7c8ad40c1f88
No need for stateAfter on volatile field loads.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2652
diff
changeset
|
330 private boolean verify() { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
331 assert linearScanOrder.size() == numBlocks : "wrong number of blocks in list"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
332 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
333 if (C1XOptions.StressLinearScan) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
334 // blocks are scrambled when StressLinearScan is used |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
335 return true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
336 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
337 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
338 // check that all successors of a block have a higher linear-scan-number |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
339 // and that all predecessors of a block have a lower linear-scan-number |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
340 // (only backward branches of loops are ignored) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
341 int i; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
342 for (i = 0; i < linearScanOrder.size(); i++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
343 BlockBegin cur = linearScanOrder.get(i); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
344 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
345 assert cur.linearScanNumber() == i : "incorrect linearScanNumber"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
346 assert cur.linearScanNumber() >= 0 && cur.linearScanNumber() == linearScanOrder.indexOf(cur) : "incorrect linearScanNumber"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
347 |
2581
4a36a0bd6d18
added GraalGraph to classpath, Node as superclass of Value
Lukas Stadler <lukas.stadler@jku.at>
parents:
2516
diff
changeset
|
348 for (BlockBegin sux : cur.end().blockSuccessors()) { |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
349 assert sux.linearScanNumber() >= 0 && sux.linearScanNumber() == linearScanOrder.indexOf(sux) : "incorrect linearScanNumber"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
350 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
351 |
2707
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
352 for (Instruction pred : cur.blockPredecessors()) { |
7ed72769d51a
exception handling related changes:
Lukas Stadler <lukas.stadler@jku.at>
parents:
2674
diff
changeset
|
353 BlockBegin begin = pred.block(); |
2674
6ab73784566a
* BlockBegin.predecessors changed to List<BlockEnd>
Lukas Stadler <lukas.stadler@jku.at>
parents:
2657
diff
changeset
|
354 assert begin.linearScanNumber() >= 0 && begin.linearScanNumber() == linearScanOrder.indexOf(begin) : "incorrect linearScanNumber"; |
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
355 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
356 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
357 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
358 return true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
359 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
360 } |