Mercurial > hg > graal-compiler
annotate graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2509:16b9a8b5ad39
Renamings Runtime=>GraalRuntime and Compiler=>GraalCompiler
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 27 Apr 2011 11:50:44 +0200 |
parents | graal/Compiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java@9ec15d6914ca |
children | a384fac3fd34 |
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 /** |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
34 * @author Thomas Wuerthinger |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
35 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
36 */ |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
37 public final class ComputeLinearScanOrder { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
38 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
39 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
|
40 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
|
41 private int numLoops; // total number of loops |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
42 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
|
43 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
44 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
|
45 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
46 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
|
47 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
|
48 final CiBitMap dominatorBlocks; // temporary BitMap used for computation of dominator |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
49 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
|
50 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
|
51 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
|
52 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
|
53 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
54 // accessors for visitedBlocks and activeBlocks |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
55 void initVisited() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
56 activeBlocks.clearAll(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
57 visitedBlocks.clearAll(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
58 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
59 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
60 boolean isVisited(BlockBegin b) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
61 return visitedBlocks.get(b.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
62 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
63 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
64 boolean isActive(BlockBegin b) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
65 return activeBlocks.get(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 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
68 void setVisited(BlockBegin b) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
69 assert !isVisited(b) : "already set"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
70 visitedBlocks.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 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
73 void setActive(BlockBegin b) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
74 assert !isActive(b) : "already set"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
75 activeBlocks.set(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 void clearActive(BlockBegin b) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
79 assert isActive(b) : "not already"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
80 activeBlocks.clear(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 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
83 // accessors for forwardBranches |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
84 void incForwardBranches(BlockBegin b) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
85 forwardBranches[b.blockID]++; |
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 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
88 int decForwardBranches(BlockBegin b) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
89 return --forwardBranches[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 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
92 // accessors for loopMap |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
93 boolean isBlockInLoop(int loopIdx, BlockBegin b) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
94 return loopMap.at(loopIdx, b.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
95 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
96 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
97 void setBlockInLoop(int loopIdx, BlockBegin b) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
98 loopMap.setBit(loopIdx, b.blockID); |
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 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
101 void clearBlockInLoop(int loopIdx, int blockId) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
102 loopMap.clearBit(loopIdx, blockId); |
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 // accessors for final result |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
106 public List<BlockBegin> linearScanOrder() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
107 return linearScanOrder; |
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 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
110 public int numLoops() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
111 return numLoops; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
112 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
113 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
114 public ComputeLinearScanOrder(int maxBlockId, BlockBegin startBlock) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
115 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
116 this.maxBlockId = maxBlockId; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
117 visitedBlocks = new CiBitMap(maxBlockId); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
118 activeBlocks = new CiBitMap(maxBlockId); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
119 dominatorBlocks = new CiBitMap(maxBlockId); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
120 forwardBranches = new int[maxBlockId]; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
121 loopEndBlocks = new ArrayList<BlockBegin>(8); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
122 workList = new ArrayList<BlockBegin>(8); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
123 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
124 splitCriticalEdges(); |
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 countEdges(startBlock, null); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
127 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
128 if (numLoops > 0) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
129 markLoops(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
130 clearNonNaturalLoops(startBlock); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
131 assignLoopDepth(startBlock); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
132 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
133 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
134 computeOrder(startBlock); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
135 computeDominators(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
136 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
137 printBlocks(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
138 assert verify(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
139 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
140 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
141 void splitCriticalEdges() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
142 // TODO: move critical edge splitting from IR to here |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
143 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
144 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
145 /** |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
146 * 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
|
147 * |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
148 * 1. Count of total number of blocks. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
149 * 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
|
150 * 3. Number loop header blocks. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
151 * 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
|
152 */ |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
153 void countEdges(BlockBegin cur, BlockBegin parent) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
154 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
155 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
|
156 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
157 assert cur.dominator() == null : "dominator already initialized"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
158 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
159 if (isActive(cur)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
160 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
161 TTY.println("backward branch"); |
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 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
|
164 assert parent != null : "must have parent"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
165 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
166 cur.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
167 cur.setBlockFlag(BlockBegin.BlockFlag.BackwardBranchTarget); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
168 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
169 parent.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
170 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
171 // When a loop header is also the start of an exception handler, then the backward branch is |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
172 // an exception edge. Because such edges are usually critical edges which cannot be split, the |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
173 // loop must be excluded here from processing. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
174 if (cur.checkBlockFlag(BlockBegin.BlockFlag.ExceptionEntry)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
175 // Make sure that dominators are correct in this weird situation |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
176 iterativeDominators = true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
177 return; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
178 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
179 // assert parent.numberOfSux() == 1 && parent.suxAt(0) == cur : "loop end blocks must have one successor (critical edges are split)"; |
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 loopEndBlocks.add(parent); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
182 return; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
183 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
184 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
185 // increment number of incoming forward branches |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
186 incForwardBranches(cur); |
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 if (isVisited(cur)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
189 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
190 TTY.println("block already visited"); |
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 return; |
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 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
195 numBlocks++; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
196 setVisited(cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
197 setActive(cur); |
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 // recursive call for all successors |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
200 int i; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
201 for (i = cur.numberOfSux() - 1; i >= 0; i--) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
202 countEdges(cur.suxAt(i), cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
203 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
204 for (i = cur.numberOfExceptionHandlers() - 1; i >= 0; i--) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
205 countEdges(cur.exceptionHandlerAt(i), cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
206 } |
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 clearActive(cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
209 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
210 // Each loop has a unique number. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
211 // When multiple loops are nested, assignLoopDepth assumes that the |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
212 // innermost loop has the lowest number. This is guaranteed by setting |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
213 // the loop number after the recursive calls for the successors above |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
214 // have returned. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
215 if (cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
216 assert cur.loopIndex() == -1 : "cannot set loop-index twice"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
217 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
218 TTY.println("Block B%d is loop header of loop %d", cur.blockID, numLoops); |
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 cur.setLoopIndex(numLoops); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
222 numLoops++; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
223 } |
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 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
226 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
|
227 } |
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 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
230 void markLoops() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
231 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
232 TTY.println("----- marking loops"); |
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 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
235 loopMap = new BitMap2D(numLoops, maxBlockId); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
236 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
237 for (int i = loopEndBlocks.size() - 1; i >= 0; i--) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
238 BlockBegin loopEnd = loopEndBlocks.get(i); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
239 BlockBegin loopStart = loopEnd.suxAt(0); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
240 int loopIdx = loopStart.loopIndex(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
241 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
242 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
243 TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID, loopEnd.blockID, loopIdx); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
244 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
245 assert loopEnd.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd) : "loop end flag must be set"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
246 // assert loopEnd.numberOfSux() == 1 : "incorrect number of successors"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
247 assert loopStart.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "loop header flag must be set"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
248 assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
249 assert workList.isEmpty() : "work list must be empty before processing"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
250 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
251 // add the end-block of the loop to the working list |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
252 workList.add(loopEnd); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
253 setBlockInLoop(loopIdx, loopEnd); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
254 do { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
255 BlockBegin cur = workList.remove(workList.size() - 1); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
256 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
257 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
258 TTY.println(" processing B%d", cur.blockID); |
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 assert isBlockInLoop(loopIdx, cur) : "bit in loop map must be set when block is in work list"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
261 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
262 // recursive processing of all predecessors ends when start block of loop is reached |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
263 if (cur != loopStart && !cur.checkBlockFlag(BlockBegin.BlockFlag.OsrEntry)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
264 for (int j = cur.numberOfPreds() - 1; j >= 0; j--) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
265 BlockBegin pred = cur.predAt(j); |
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 if (!isBlockInLoop(loopIdx, pred)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
268 // this predecessor has not been processed yet, so add it to work list |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
269 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
270 TTY.println(" pushing B%d", pred.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
271 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
272 workList.add(pred); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
273 setBlockInLoop(loopIdx, pred); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
274 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
275 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
276 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
277 } while (!workList.isEmpty()); |
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 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
280 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
281 // check for non-natural loops (loops where the loop header does not dominate |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
282 // all other loop blocks = loops with multiple entries). |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
283 // such loops are ignored |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
284 void clearNonNaturalLoops(BlockBegin startBlock) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
285 for (int i = numLoops - 1; i >= 0; i--) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
286 if (isBlockInLoop(i, startBlock)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
287 // loop i contains the entry block of the method. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
288 // this is not a natural loop, so ignore it |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
289 if (C1XOptions.TraceLinearScanLevel >= 2) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
290 TTY.println("Loop %d is non-natural, so it is ignored", i); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
291 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
292 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
293 for (int blockId = maxBlockId - 1; blockId >= 0; blockId--) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
294 clearBlockInLoop(i, blockId); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
295 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
296 iterativeDominators = true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
297 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
298 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
299 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
300 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
301 void assignLoopDepth(BlockBegin startBlock) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
302 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
303 TTY.println("----- computing loop-depth and weight"); |
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 initVisited(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
306 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
307 assert workList.isEmpty() : "work list must be empty before processing"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
308 workList.add(startBlock); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
309 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
310 do { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
311 BlockBegin cur = workList.remove(workList.size() - 1); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
312 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
313 if (!isVisited(cur)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
314 setVisited(cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
315 if (C1XOptions.TraceLinearScanLevel >= 4) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
316 TTY.println("Computing loop depth for block B%d", cur.blockID); |
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 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
319 // compute loop-depth and loop-index for the block |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
320 assert cur.loopDepth() == 0 : "cannot set loop-depth twice"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
321 int i; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
322 int loopDepth = 0; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
323 int minLoopIdx = -1; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
324 for (i = numLoops - 1; i >= 0; i--) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
325 if (isBlockInLoop(i, cur)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
326 loopDepth++; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
327 minLoopIdx = i; |
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 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
330 cur.setLoopDepth(loopDepth); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
331 cur.setLoopIndex(minLoopIdx); |
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 // append all unvisited successors to work list |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
334 for (i = cur.numberOfSux() - 1; i >= 0; i--) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
335 workList.add(cur.suxAt(i)); |
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 for (i = cur.numberOfExceptionHandlers() - 1; i >= 0; i--) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
338 workList.add(cur.exceptionHandlerAt(i)); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
339 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
340 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
341 } while (!workList.isEmpty()); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
342 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
343 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
344 BlockBegin commonDominator(BlockBegin a, BlockBegin b) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
345 assert a != null && b != null : "must have input blocks"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
346 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
347 dominatorBlocks.clearAll(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
348 while (a != null) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
349 dominatorBlocks.set(a.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
350 assert a.dominator() != null || a == linearScanOrder.get(0) : "dominator must be initialized"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
351 a = a.dominator(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
352 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
353 while (b != null && !dominatorBlocks.get(b.blockID)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
354 assert b.dominator() != null || b == linearScanOrder.get(0) : "dominator must be initialized"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
355 b = b.dominator(); |
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 assert b != null : "could not find dominator"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
359 return b; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
360 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
361 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
362 void computeDominator(BlockBegin cur, BlockBegin parent) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
363 if (cur.dominator() == null) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
364 if (C1XOptions.TraceLinearScanLevel >= 4) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
365 TTY.println("DOM: initializing dominator of B%d to B%d", cur.blockID, parent.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
366 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
367 if (cur.isExceptionEntry()) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
368 assert parent.dominator() != null; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
369 cur.setDominator(parent.dominator()); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
370 } else { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
371 cur.setDominator(parent); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
372 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
373 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
374 } else if (!(cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) && parent.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd))) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
375 if (C1XOptions.TraceLinearScanLevel >= 4) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
376 TTY.println("DOM: computing dominator of B%d: common dominator of B%d and B%d is B%d", cur.blockID, parent.blockID, cur.dominator().blockID, commonDominator(cur.dominator(), parent).blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
377 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
378 assert cur.numberOfPreds() > 1 : ""; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
379 cur.setDominator(commonDominator(cur.dominator(), parent)); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
380 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
381 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
382 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
383 int computeWeight(BlockBegin cur) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
384 BlockBegin singleSux = null; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
385 if (cur.numberOfSux() == 1) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
386 singleSux = cur.suxAt(0); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
387 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
388 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
389 // limit loop-depth to 15 bit (only for security reason, it will never be so big) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
390 int weight = (cur.loopDepth() & 0x7FFF) << 16; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
391 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
392 int curBit = 15; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
393 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
394 // this is necessary for the (very rare) case that two successive blocks have |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
395 // the same loop depth, but a different loop index (can happen for endless loops |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
396 // with exception handlers) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
397 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
398 weight |= (1 << curBit); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
399 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
400 curBit--; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
401 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
402 // loop end blocks (blocks that end with a backward branch) are added |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
403 // after all other blocks of the loop. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
404 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
405 weight |= (1 << curBit); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
406 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
407 curBit--; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
408 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
409 // critical edge split blocks are preferred because then they have a greater |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
410 // probability to be completely empty |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
411 if (cur.isCriticalEdgeSplit()) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
412 weight |= (1 << curBit); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
413 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
414 curBit--; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
415 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
416 // 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
|
417 // are added as late as possible |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
418 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
|
419 weight |= (1 << curBit); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
420 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
421 curBit--; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
422 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
|
423 weight |= (1 << curBit); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
424 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
425 curBit--; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
426 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
427 // exceptions handlers are added as late as possible |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
428 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.ExceptionEntry)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
429 weight |= (1 << curBit); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
430 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
431 curBit--; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
432 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
433 // guarantee that weight is > 0 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
434 weight |= 1; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
435 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
436 assert curBit >= 0 : "too many flags"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
437 assert weight > 0 : "weight cannot become negative"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
438 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
439 return weight; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
440 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
441 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
442 boolean readyForProcessing(BlockBegin cur) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
443 // Discount the edge just traveled. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
444 // 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
|
445 if (decForwardBranches(cur) != 0) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
446 return false; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
447 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
448 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
449 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
|
450 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
|
451 return true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
452 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
453 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
454 void sortIntoWorkList(BlockBegin cur) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
455 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
|
456 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
457 int curWeight = computeWeight(cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
458 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
459 // 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
|
460 cur.setLinearScanNumber(curWeight); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
461 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
462 if (C1XOptions.StressLinearScan) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
463 workList.add(0, cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
464 return; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
465 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
466 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
467 workList.add(null); // provide space for new element |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
468 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
469 int insertIdx = workList.size() - 1; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
470 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
|
471 workList.set(insertIdx, workList.get(insertIdx - 1)); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
472 insertIdx--; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
473 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
474 workList.set(insertIdx, cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
475 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
476 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
477 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
|
478 for (int i = 0; i < workList.size(); i++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
479 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
|
480 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
481 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
482 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
483 for (int i = 0; i < workList.size(); i++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
484 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
|
485 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
|
486 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
487 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
488 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
489 void appendBlock(BlockBegin cur) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
490 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
491 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
|
492 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
493 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
|
494 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
495 // 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
|
496 // 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
|
497 // be equal. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
498 cur.setLinearScanNumber(linearScanOrder.size()); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
499 linearScanOrder.add(cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
500 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
501 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
502 void computeOrder(BlockBegin startBlock) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
503 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
504 TTY.println("----- computing final block order"); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
505 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
506 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
507 // 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
|
508 linearScanOrder = new ArrayList<BlockBegin>(numBlocks); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
509 appendBlock(startBlock); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
510 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
511 assert startBlock.end() instanceof Base : "start block must end with Base-instruction"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
512 BlockBegin stdEntry = ((Base) startBlock.end()).standardEntry(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
513 BlockBegin osrEntry = ((Base) startBlock.end()).osrEntry(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
514 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
515 BlockBegin suxOfOsrEntry = null; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
516 if (osrEntry != null) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
517 // special handling for osr entry: |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
518 // ignore the edge between the osr entry and its successor for processing |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
519 // the osr entry block is added manually below |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
520 assert osrEntry.numberOfSux() == 1 : "osr entry must have exactly one successor"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
521 assert osrEntry.suxAt(0).numberOfPreds() >= 2 : "sucessor of osr entry must have two predecessors (otherwise it is not present in normal control flow)"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
522 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
523 suxOfOsrEntry = osrEntry.suxAt(0); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
524 decForwardBranches(suxOfOsrEntry); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
525 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
526 computeDominator(osrEntry, startBlock); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
527 iterativeDominators = true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
528 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
529 computeDominator(stdEntry, startBlock); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
530 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
531 // start processing with standard entry block |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
532 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
|
533 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
534 if (readyForProcessing(stdEntry)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
535 sortIntoWorkList(stdEntry); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
536 } else { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
537 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
|
538 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
539 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
540 do { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
541 BlockBegin cur = workList.remove(workList.size() - 1); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
542 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
543 if (cur == suxOfOsrEntry) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
544 // the osr entry block is ignored in normal processing : it is never added to the |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
545 // work list. Instead : it is added as late as possible manually here. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
546 appendBlock(osrEntry); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
547 computeDominator(cur, osrEntry); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
548 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
549 appendBlock(cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
550 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
551 int i; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
552 int numSux = cur.numberOfSux(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
553 // changed loop order to get "intuitive" order of if- and else-blocks |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
554 for (i = 0; i < numSux; i++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
555 BlockBegin sux = cur.suxAt(i); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
556 computeDominator(sux, cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
557 if (readyForProcessing(sux)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
558 sortIntoWorkList(sux); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
559 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
560 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
561 numSux = cur.numberOfExceptionHandlers(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
562 for (i = 0; i < numSux; i++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
563 BlockBegin sux = cur.exceptionHandlerAt(i); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
564 computeDominator(sux, cur); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
565 if (readyForProcessing(sux)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
566 sortIntoWorkList(sux); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
567 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
568 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
569 } while (workList.size() > 0); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
570 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
571 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
572 boolean computeDominatorsIter() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
573 boolean changed = false; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
574 int numBlocks = linearScanOrder.size(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
575 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
576 assert linearScanOrder.get(0).dominator() == null : "must not have dominator"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
577 assert linearScanOrder.get(0).numberOfPreds() == 0 : "must not have predecessors"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
578 for (int i = 1; i < numBlocks; i++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
579 BlockBegin block = linearScanOrder.get(i); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
580 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
581 assert block.numberOfPreds() > 0; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
582 BlockBegin dominator = block.predAt(0); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
583 if (block.isExceptionEntry()) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
584 dominator = dominator.dominator(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
585 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
586 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
587 int numPreds = block.numberOfPreds(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
588 for (int j = 1; j < numPreds; j++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
589 BlockBegin curPred = block.predAt(j); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
590 if (block.isExceptionEntry()) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
591 curPred = curPred.dominator(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
592 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
593 dominator = commonDominator(dominator, curPred); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
594 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
595 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
596 if (dominator != block.dominator()) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
597 if (C1XOptions.TraceLinearScanLevel >= 4) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
598 TTY.println("DOM: updating dominator of B%d from B%d to B%d", block.blockID, block.dominator().blockID, dominator.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
599 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
600 block.setDominator(dominator); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
601 changed = true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
602 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
603 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
604 return changed; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
605 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
606 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
607 void computeDominators() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
608 if (C1XOptions.TraceLinearScanLevel >= 3) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
609 TTY.println("----- computing dominators (iterative computation reqired: %b)", iterativeDominators); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
610 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
611 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
612 // iterative computation of dominators is only required for methods with non-natural loops |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
613 // and OSR-methods. For all other methods : the dominators computed when generating the |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
614 // linear scan block order are correct. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
615 if (iterativeDominators) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
616 do { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
617 if (C1XOptions.TraceLinearScanLevel >= 1) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
618 TTY.println("DOM: next iteration of fix-point calculation"); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
619 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
620 } while (computeDominatorsIter()); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
621 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
622 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
623 // check that dominators are correct |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
624 assert !computeDominatorsIter() : "fix point not reached"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
625 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
626 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
627 public void printBlocks() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
628 if (C1XOptions.TraceLinearScanLevel >= 2) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
629 TTY.println("----- loop information:"); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
630 for (BlockBegin cur : linearScanOrder) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
631 TTY.print(String.format("%4d: B%02d: ", cur.linearScanNumber(), cur.blockID)); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
632 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
633 TTY.print(String.format("%d = %b ", loopIdx, isBlockInLoop(loopIdx, cur))); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
634 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
635 TTY.println(String.format(" . loopIndex: %2d, loopDepth: %2d", cur.loopIndex(), cur.loopDepth())); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
636 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
637 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
638 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
639 if (C1XOptions.TraceLinearScanLevel >= 1) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
640 TTY.println("----- linear-scan block order:"); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
641 for (BlockBegin cur : linearScanOrder) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
642 TTY.print(String.format("%4d: B%02d loop: %2d depth: %2d", cur.linearScanNumber(), cur.blockID, cur.loopIndex(), cur.loopDepth())); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
643 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
644 TTY.print(cur.isExceptionEntry() ? " ex" : " "); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
645 TTY.print(cur.isCriticalEdgeSplit() ? " ce" : " "); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
646 TTY.print(cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) ? " lh" : " "); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
647 TTY.print(cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd) ? " le" : " "); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
648 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
649 if (cur.dominator() != null) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
650 TTY.print(" dom: B%d ", cur.dominator().blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
651 } else { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
652 TTY.print(" dom: null "); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
653 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
654 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
655 if (cur.numberOfPreds() > 0) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
656 TTY.print(" preds: "); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
657 for (int j = 0; j < cur.numberOfPreds(); j++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
658 BlockBegin pred = cur.predAt(j); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
659 TTY.print("B%d ", pred.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
660 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
661 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
662 if (cur.numberOfSux() > 0) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
663 TTY.print(" sux: "); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
664 for (int j = 0; j < cur.numberOfSux(); j++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
665 BlockBegin sux = cur.suxAt(j); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
666 TTY.print("B%d ", sux.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
667 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
668 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
669 if (cur.numberOfExceptionHandlers() > 0) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
670 TTY.print(" ex: "); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
671 for (int j = 0; j < cur.numberOfExceptionHandlers(); j++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
672 BlockBegin ex = cur.exceptionHandlerAt(j); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
673 TTY.print("B%d ", ex.blockID); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
674 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
675 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
676 TTY.println(); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
677 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
678 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
679 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
680 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
681 boolean verify() { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
682 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
|
683 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
684 if (C1XOptions.StressLinearScan) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
685 // blocks are scrambled when StressLinearScan is used |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
686 return true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
687 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
688 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
689 // 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
|
690 // 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
|
691 // (only backward branches of loops are ignored) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
692 int i; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
693 for (i = 0; i < linearScanOrder.size(); i++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
694 BlockBegin cur = linearScanOrder.get(i); |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
695 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
696 assert cur.linearScanNumber() == i : "incorrect linearScanNumber"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
697 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
|
698 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
699 for (BlockBegin sux : cur.end().successors()) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
700 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
|
701 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
702 assert cur.linearScanNumber() < sux.linearScanNumber() : "invalid order"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
703 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
704 if (cur.loopDepth() == sux.loopDepth()) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
705 assert cur.loopIndex() == sux.loopIndex() || sux.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
706 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
707 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
708 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
709 for (BlockBegin pred : cur.predecessors()) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
710 assert pred.linearScanNumber() >= 0 && pred.linearScanNumber() == linearScanOrder.indexOf(pred) : "incorrect linearScanNumber"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
711 if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
712 assert cur.linearScanNumber() > pred.linearScanNumber() : "invalid order"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
713 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
714 if (cur.loopDepth() == pred.loopDepth()) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
715 assert cur.loopIndex() == pred.loopIndex() || cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
716 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
717 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
718 assert cur.dominator().linearScanNumber() <= pred.linearScanNumber() : "dominator must be before predecessors"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
719 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
720 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
721 // check dominator |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
722 if (i == 0) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
723 assert cur.dominator() == null : "first block has no dominator"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
724 } else { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
725 assert cur.dominator() != null : "all but first block must have dominator"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
726 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
727 assert cur.numberOfPreds() != 1 || cur.dominator() == cur.predAt(0) || cur.isExceptionEntry() : "Single predecessor must also be dominator"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
728 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
729 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
730 // check that all loops are continuous |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
731 for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
732 int blockIdx = 0; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
733 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "the first block must not be present in any loop"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
734 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
735 // skip blocks before the loop |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
736 while (blockIdx < numBlocks && !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
737 blockIdx++; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
738 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
739 // skip blocks of loop |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
740 while (blockIdx < numBlocks && isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
741 blockIdx++; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
742 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
743 // after the first non-loop block : there must not be another loop-block |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
744 while (blockIdx < numBlocks) { |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
745 assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "loop not continuous in linear-scan order"; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
746 blockIdx++; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
747 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
748 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
749 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
750 return true; |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
751 } |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
752 } |