Mercurial > hg > graal-jvmci-8

annotate graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java @ 7331:88b3b9b9a47b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Experimentation with new probability based code emission order.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Thu, 10 Jan 2013 16:04:25 +0100
parents 40be0ff5a3ce
children 9f69799a1768
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1 /*
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
2 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
4 *
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
7 * published by the Free Software Foundation.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
8 *
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
13 * accompanied this code).
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
14 *
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
18 *
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
21 * questions.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
22 */
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
23
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
24 package com.oracle.graal.alloc;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
25
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
26 import java.util.*;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
27
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
28 import com.oracle.graal.debug.*;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
29 import com.oracle.graal.graph.*;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
30 import com.oracle.graal.nodes.*;
6529
2e96dc4eb8e2 renamed package: com.oracle.graal.lir.cfg -> com.oracle.graal.nodes.cfg
Doug Simon <doug.simon@oracle.com>
parents: 6411
diff changeset
31 import com.oracle.graal.nodes.cfg.*;
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
32
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
33 /**
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
34 * Computes an ordering of the block that can be used by the linear scan register allocator
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
35 * and the machine code generator.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
36 */
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
37 public final class ComputeBlockOrder {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
38 private int blockCount;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
39 private List<Block> linearScanOrder;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
40 private List<Block> codeEmittingOrder;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
41 private final BitSet visitedBlocks; // used for recursive processing of blocks
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
42 private final BitSet activeBlocks; // used for recursive processing of blocks
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
43 private final int[] forwardBranches; // number of incoming forward branches for each block
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
44 private final List<Block> workList; // temporary list (used in markLoops and computeOrder)
6411
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6317
diff changeset
45 private final List<Block> loopHeaders;
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
46 private final boolean reorderLoops;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
47
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
48 public ComputeBlockOrder(int maxBlockId, int loopCount, Block startBlock, boolean reorderLoops) {
6411
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6317
diff changeset
49 loopHeaders = new ArrayList<>(loopCount);
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6317
diff changeset
50 while (loopHeaders.size() < loopCount) {
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6317
diff changeset
51 loopHeaders.add(null);
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6317
diff changeset
52 }
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
53 visitedBlocks = new BitSet(maxBlockId);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
54 activeBlocks = new BitSet(maxBlockId);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
55 forwardBranches = new int[maxBlockId];
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
56 workList = new ArrayList<>(8);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
57 this.reorderLoops = reorderLoops;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
58
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
59 countEdges(startBlock, null);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
60 computeOrder(startBlock);
7331
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
61
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
62
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
63 List<Block> newCodeEmittingOrder = new ArrayList<>();
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
64 List<Block> outOfLine = new ArrayList<>();
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
65 for (Block b : codeEmittingOrder) {
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
66 if (b.getBeginNode().probability() > 0.07) {
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
67 newCodeEmittingOrder.add(b);
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
68 } else {
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
69 outOfLine.add(b);
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
70 }
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
71 }
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
72
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
73 for (Block b : outOfLine) {
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
74 newCodeEmittingOrder.add(b);
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
75 }
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
76 codeEmittingOrder = newCodeEmittingOrder;
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
77 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
78
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
79 /**
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
80 * Returns the block order used for the linear scan register allocator.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
81 * @return list of sorted blocks
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
82 */
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
83 public List<Block> linearScanOrder() {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
84 return linearScanOrder;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
85 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
86
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
87 /**
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
88 * Returns the block order used for machine code generation.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
89 * @return list of sorted blocks2222
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
90 */
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
91 public List<Block> codeEmittingOrder() {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
92 return codeEmittingOrder;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
93 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
94
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
95 private boolean isVisited(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
96 return visitedBlocks.get(b.getId());
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
97 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
98
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
99 private boolean isActive(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
100 return activeBlocks.get(b.getId());
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
101 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
102
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
103 private void setVisited(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
104 assert !isVisited(b);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
105 visitedBlocks.set(b.getId());
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
106 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
107
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
108 private void setActive(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
109 assert !isActive(b);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
110 activeBlocks.set(b.getId());
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
111 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
112
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
113 private void clearActive(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
114 assert isActive(b);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
115 activeBlocks.clear(b.getId());
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
116 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
117
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
118 private void incForwardBranches(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
119 forwardBranches[b.getId()]++;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
120 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
121
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
122 private int decForwardBranches(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
123 return --forwardBranches[b.getId()];
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
124 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
125
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
126 /**
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
127 * Traverses the CFG to analyze block and edge info. The analysis performed is:
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
128 *
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
129 * 1. Count of total number of blocks.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
130 * 2. Count of all incoming edges and backward incoming edges.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
131 * 3. Number loop header blocks.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
132 * 4. Create a list with all loop end blocks.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
133 */
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
134 private void countEdges(Block cur, Block parent) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
135 Debug.log("Counting edges for block B%d%s", cur.getId(), parent == null ? "" : " coming from B" + parent.getId());
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
136
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
137 if (isActive(cur)) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
138 return;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
139 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
140
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
141 // increment number of incoming forward branches
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
142 incForwardBranches(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
143
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
144 if (isVisited(cur)) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
145 return;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
146 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
147
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
148 blockCount++;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
149 setVisited(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
150 setActive(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
151
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
152 // recursive call for all successors
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
153 for (int i = cur.numberOfSux() - 1; i >= 0; i--) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
154 countEdges(cur.suxAt(i), cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
155 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
156
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
157 clearActive(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
158
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
159 Debug.log("Finished counting edges for block B%d", cur.getId());
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
160 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
161
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
162 private static int computeWeight(Block cur) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
163
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
164 // limit loop-depth to 15 bit (only for security reason, it will never be so big)
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
165 int weight = (cur.getLoopDepth() & 0x7FFF) << 16;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
166
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
167 int curBit = 15;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
168
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
169 // loop end blocks (blocks that end with a backward branch) are added
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
170 // after all other blocks of the loop.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
171 if (!cur.isLoopEnd()) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
172 weight |= 1 << curBit;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
173 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
174 curBit--;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
175
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
176 // exceptions handlers are added as late as possible
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
177 if (!cur.isExceptionEntry()) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
178 weight |= 1 << curBit;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
179 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
180 curBit--;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
181
7317
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
182 if (cur.getBeginNode().probability() > 0.5) {
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
183 weight |= 1 << curBit;
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
184 }
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
185 curBit--;
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
186
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
187 if (cur.getBeginNode().probability() > 0.05) {
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
188 weight |= 1 << curBit;
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
189 }
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
190 curBit--;
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
191
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
192 // guarantee that weight is > 0
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
193 weight |= 1;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
194
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
195 assert curBit >= 0 : "too many flags";
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
196 assert weight > 0 : "weight cannot become negative";
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
197
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
198 return weight;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
199 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
200
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
201 private boolean readyForProcessing(Block cur) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
202 // Discount the edge just traveled.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
203 // When the number drops to zero, all forward branches were processed
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
204 if (decForwardBranches(cur) != 0) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
205 return false;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
206 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
207
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
208 assert !linearScanOrder.contains(cur) : "block already processed (block can be ready only once)";
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
209 assert !workList.contains(cur) : "block already in work-list (block can be ready only once)";
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
210 return true;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
211 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
212
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
213 private void sortIntoWorkList(Block cur) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
214 assert !workList.contains(cur) : "block already in work list";
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
215
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
216 int curWeight = computeWeight(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
217
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
218 // the linearScanNumber is used to cache the weight of a block
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
219 cur.linearScanNumber = curWeight;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
220
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
221 workList.add(null); // provide space for new element
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
222
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
223 int insertIdx = workList.size() - 1;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
224 while (insertIdx > 0 && workList.get(insertIdx - 1).linearScanNumber > curWeight) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
225 workList.set(insertIdx, workList.get(insertIdx - 1));
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
226 insertIdx--;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
227 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
228 workList.set(insertIdx, cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
229
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
230 if (Debug.isLogEnabled()) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
231 Debug.log("Sorted B%d into worklist. new worklist:", cur.getId());
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
232 for (int i = 0; i < workList.size(); i++) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
233 Debug.log(String.format("%8d B%02d weight:%6x", i, workList.get(i).getId(), workList.get(i).linearScanNumber));
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
234 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
235 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
236
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
237 for (int i = 0; i < workList.size(); i++) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
238 assert workList.get(i).linearScanNumber > 0 : "weight not set";
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
239 assert i == 0 || workList.get(i - 1).linearScanNumber <= workList.get(i).linearScanNumber : "incorrect order in worklist";
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
240 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
241 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
242
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
243 private void appendBlock(Block cur) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
244 Debug.log("appending block B%d (weight 0x%06x) to linear-scan order", cur.getId(), cur.linearScanNumber);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
245 assert !linearScanOrder.contains(cur) : "cannot add the same block twice";
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
246
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
247 cur.linearScanNumber = linearScanOrder.size();
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
248 linearScanOrder.add(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
249
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
250 if (cur.isLoopEnd() && cur.isLoopHeader()) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
251 codeEmittingOrder.add(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
252 } else {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
253 if (!cur.isLoopHeader() || ((LoopBeginNode) cur.getBeginNode()).loopEnds().count() > 1 || !reorderLoops) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
254 codeEmittingOrder.add(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
255
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
256 if (cur.isLoopEnd() && reorderLoops) {
6411
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6317
diff changeset
257 Block loopHeader = loopHeaders.get(cur.getLoop().index);
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
258 if (loopHeader != null) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
259 codeEmittingOrder.add(loopHeader);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
260
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
261 for (int i = 0; i < loopHeader.numberOfSux(); i++) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
262 Block succ = loopHeader.suxAt(i);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
263 if (succ.getLoopDepth() == loopHeader.getLoopDepth()) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
264 succ.align = true;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
265 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
266 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
267 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
268 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
269 } else {
6411
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 6317
diff changeset
270 loopHeaders.set(cur.getLoop().index, cur);
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
271 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
272 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
273 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
274
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
275 private void checkAndSortIntoWorkList(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
276 if (readyForProcessing(b)) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
277 sortIntoWorkList(b);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
278 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
279 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
280
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
281 private void computeOrder(Block startBlock) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
282 // the start block is always the first block in the linear scan order
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
283 linearScanOrder = new ArrayList<>(blockCount);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
284
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
285 codeEmittingOrder = new ArrayList<>(blockCount);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
286
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
287 // start processing with standard entry block
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
288 assert workList.isEmpty() : "list must be empty before processing";
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
289
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
290 sortIntoWorkList(startBlock);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
291
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
292 do {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
293 Block cur = workList.remove(workList.size() - 1);
7317
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
294 processBlock(cur);
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
295 } while (workList.size() > 0);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
296 }
7317
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
297
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
298 private void processBlock(Block cur) {
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
299 appendBlock(cur);
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
300
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
301 Node endNode = cur.getEndNode();
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
302 if (endNode instanceof IfNode && ((IfNode) endNode).probability() < 0.5) {
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
303 assert cur.numberOfSux() == 2;
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
304 checkAndSortIntoWorkList(cur.suxAt(1));
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
305 checkAndSortIntoWorkList(cur.suxAt(0));
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
306 } else {
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
307 for (Block sux : cur.getSuccessors()) {
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
308 checkAndSortIntoWorkList(sux);
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
309 }
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
310 }
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
311 }
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
312 }