Mercurial > hg > truffle

annotate graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java @ 2729:108adba3345e

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