Mercurial > hg > truffle

annotate graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java @ 7353:b5280041f59e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Experiment with soft alignment for branch targets.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Sun, 13 Jan 2013 19:32:16 +0100
parents 9f69799a1768
children 4c6e577d0c01
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
7348
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
48 private Comparator<Block> blockComparator = new Comparator<Block>() {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
49 @Override
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
50 public int compare(Block o1, Block o2) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
51 // Loop blocks before any loop exit block.
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
52 int diff = o2.getLoopDepth() - o1.getLoopDepth();
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
53 if (diff != 0) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
54 return diff;
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
55 }
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
56
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
57 // Blocks with high probability before blocks with low probability.
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
58 if (o1.getBeginNode().probability() > o2.getBeginNode().probability()) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
59 return -1;
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
60 } else {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
61 return 1;
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
62 }
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
63 }};
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
64
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
65 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
66 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
67 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
68 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
69 }
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
70 visitedBlocks = new BitSet(maxBlockId);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
71 activeBlocks = new BitSet(maxBlockId);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
72 forwardBranches = new int[maxBlockId];
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
73 workList = new ArrayList<>(8);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
74 this.reorderLoops = reorderLoops;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
75
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
76 countEdges(startBlock, null);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
77 computeOrder(startBlock);
7331
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
78
7348
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
79 List<Block> order = new ArrayList<>();
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
80 PriorityQueue<Block> worklist = new PriorityQueue<>(10, blockComparator);
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
81 BitSet orderedBlocks = new BitSet(maxBlockId);
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
82 orderedBlocks.set(startBlock.getId());
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
83 worklist.add(startBlock);
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
84 computeCodeEmittingOrder(order, worklist, orderedBlocks);
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
85 assert codeEmittingOrder.size() == order.size();
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
86 codeEmittingOrder = order;
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
87 }
7331
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
88
7348
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
89 private void computeCodeEmittingOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet orderedBlocks) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
90 while (!worklist.isEmpty()) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
91 Block nextImportantPath = worklist.poll();
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
92 addImportantPath(nextImportantPath, order, worklist, orderedBlocks);
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
93 }
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
94 }
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
95
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
96 private void addImportantPath(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet orderedBlocks) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
97 if (!skipLoopHeader(block)) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
98 if (block.isLoopHeader()) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
99 block.align = true;
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
100 }
7353
b5280041f59e Experiment with soft alignment for branch targets.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7348
diff changeset
101 addBlock(block, order);
7348
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
102 }
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
103 if (block.isLoopEnd() && skipLoopHeader(block.getLoop().header)) {
7353
b5280041f59e Experiment with soft alignment for branch targets.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7348
diff changeset
104 addBlock(block.getLoop().header, order);
7348
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
105 for (Block succ : block.getLoop().header.getSuccessors()) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
106 if (succ.getLoopDepth() == block.getLoopDepth()) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
107 succ.align = true;
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
108 }
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
109 }
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
110 }
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
111 Block bestSucc = null;
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
112 double bestSuccProb = 0;
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
113
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
114 for (Block succ : block.getSuccessors()) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
115 if (!orderedBlocks.get(succ.getId()) && succ.getLoopDepth() >= block.getLoopDepth()) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
116 double curProb = succ.getBeginNode().probability();
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
117 if (curProb >= bestSuccProb) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
118 bestSuccProb = curProb;
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
119 bestSucc = succ;
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
120 }
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
121 assert curProb >= 0 : curProb;
7331
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
122 }
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
123 }
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
124
7348
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
125 for (Block succ : block.getSuccessors()) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
126 if (!orderedBlocks.get(succ.getId())) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
127 if (succ != bestSucc) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
128 orderedBlocks.set(succ.getId());
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
129 worklist.add(succ);
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
130 }
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
131 }
7331
88b3b9b9a47b Experimentation with new probability based code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7317
diff changeset
132 }
7348
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
133
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
134 if (bestSucc != null) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
135 orderedBlocks.set(bestSucc.getId());
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
136 addImportantPath(bestSucc, order, worklist, orderedBlocks);
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
137 }
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
138 }
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
139
7353
b5280041f59e Experiment with soft alignment for branch targets.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7348
diff changeset
140 private static void addBlock(Block block, List<Block> order) {
b5280041f59e Experiment with soft alignment for branch targets.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7348
diff changeset
141 if (order.size() > 0 && block.getPredecessors().size() == 1 && block.getPredecessors().get(0) != order.get(order.size() - 1)) {
b5280041f59e Experiment with soft alignment for branch targets.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7348
diff changeset
142 block.softAlign = false;
b5280041f59e Experiment with soft alignment for branch targets.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7348
diff changeset
143 }
b5280041f59e Experiment with soft alignment for branch targets.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7348
diff changeset
144 order.add(block);
b5280041f59e Experiment with soft alignment for branch targets.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7348
diff changeset
145 }
b5280041f59e Experiment with soft alignment for branch targets.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7348
diff changeset
146
7348
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
147 private boolean skipLoopHeader(Block bestSucc) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
148 return (reorderLoops && bestSucc.isLoopHeader() && !bestSucc.isLoopEnd() && bestSucc.getLoop().loopBegin().loopEnds().count() == 1);
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
149 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
150
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 * 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
153 * @return list of sorted blocks
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
154 */
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
155 public List<Block> linearScanOrder() {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
156 return linearScanOrder;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
157 }
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 /**
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
160 * 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
161 * @return list of sorted blocks2222
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
162 */
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
163 public List<Block> codeEmittingOrder() {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
164 return codeEmittingOrder;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
165 }
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 private boolean isVisited(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
168 return visitedBlocks.get(b.getId());
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
169 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
170
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
171 private boolean isActive(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
172 return activeBlocks.get(b.getId());
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
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
175 private void setVisited(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
176 assert !isVisited(b);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
177 visitedBlocks.set(b.getId());
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
178 }
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 private void setActive(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
181 assert !isActive(b);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
182 activeBlocks.set(b.getId());
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
183 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
184
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
185 private void clearActive(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
186 assert isActive(b);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
187 activeBlocks.clear(b.getId());
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
188 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
189
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
190 private void incForwardBranches(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
191 forwardBranches[b.getId()]++;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
192 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
193
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
194 private int decForwardBranches(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
195 return --forwardBranches[b.getId()];
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
196 }
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 /**
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
199 * 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
200 *
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
201 * 1. Count of total number of blocks.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
202 * 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
203 * 3. Number loop header blocks.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
204 * 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
205 */
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
206 private void countEdges(Block cur, Block parent) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
207 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
208
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
209 if (isActive(cur)) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
210 return;
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 // increment number of incoming forward branches
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
214 incForwardBranches(cur);
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 if (isVisited(cur)) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
217 return;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
218 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
219
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
220 blockCount++;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
221 setVisited(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
222 setActive(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
223
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
224 // recursive call for all successors
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
225 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
226 countEdges(cur.suxAt(i), cur);
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
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
229 clearActive(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
230
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
231 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
232 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
233
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
234 private static int computeWeight(Block cur) {
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 // 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
237 int weight = (cur.getLoopDepth() & 0x7FFF) << 16;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
238
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
239 int curBit = 15;
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 // 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
242 // after all other blocks of the loop.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
243 if (!cur.isLoopEnd()) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
244 weight |= 1 << curBit;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
245 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
246 curBit--;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
247
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
248 // exceptions handlers are added as late as possible
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
249 if (!cur.isExceptionEntry()) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
250 weight |= 1 << curBit;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
251 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
252 curBit--;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
253
7317
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
254 if (cur.getBeginNode().probability() > 0.5) {
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
255 weight |= 1 << curBit;
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
256 }
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
257 curBit--;
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
258
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
259 if (cur.getBeginNode().probability() > 0.05) {
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
260 weight |= 1 << curBit;
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
261 }
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
262 curBit--;
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
263
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
264 // guarantee that weight is > 0
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
265 weight |= 1;
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 assert curBit >= 0 : "too many flags";
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
268 assert weight > 0 : "weight cannot become negative";
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
269
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
270 return weight;
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 private boolean readyForProcessing(Block cur) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
274 // Discount the edge just traveled.
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
275 // 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
276 if (decForwardBranches(cur) != 0) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
277 return false;
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 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
281 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
282 return true;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
283 }
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 private void sortIntoWorkList(Block cur) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
286 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
287
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
288 int curWeight = computeWeight(cur);
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 // 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
291 cur.linearScanNumber = curWeight;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
292
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
293 workList.add(null); // provide space for new element
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
294
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
295 int insertIdx = workList.size() - 1;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
296 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
297 workList.set(insertIdx, workList.get(insertIdx - 1));
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
298 insertIdx--;
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
299 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
300 workList.set(insertIdx, cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
301
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
302 if (Debug.isLogEnabled()) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
303 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
304 for (int i = 0; i < workList.size(); i++) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
305 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
306 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
307 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
308
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
309 for (int i = 0; i < workList.size(); i++) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
310 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
311 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
312 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
313 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
314
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
315 private void appendBlock(Block cur) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
316 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
317 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
318
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
319 cur.linearScanNumber = linearScanOrder.size();
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
320 linearScanOrder.add(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
321
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
322 if (cur.isLoopEnd() && cur.isLoopHeader()) {
7348
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
323 //cur.align = true;
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
324 codeEmittingOrder.add(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
325 } else {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
326 if (!cur.isLoopHeader() || ((LoopBeginNode) cur.getBeginNode()).loopEnds().count() > 1 || !reorderLoops) {
7348
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
327 if (cur.isLoopHeader()) {
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
328 // cur.align = true;
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
329 }
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
330 codeEmittingOrder.add(cur);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
331
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
332 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
333 Block loopHeader = loopHeaders.get(cur.getLoop().index);
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
334 if (loopHeader != null) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
335 codeEmittingOrder.add(loopHeader);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
336
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
337 for (int i = 0; i < loopHeader.numberOfSux(); i++) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
338 Block succ = loopHeader.suxAt(i);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
339 if (succ.getLoopDepth() == loopHeader.getLoopDepth()) {
7348
9f69799a1768 New experiment with block code emission order.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7331
diff changeset
340 // succ.align = true;
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
341 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
342 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
343 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
344 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
345 } 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
346 loopHeaders.set(cur.getLoop().index, cur);
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
347 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
348 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
349 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
350
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
351 private void checkAndSortIntoWorkList(Block b) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
352 if (readyForProcessing(b)) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
353 sortIntoWorkList(b);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
354 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
355 }
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
356
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
357 private void computeOrder(Block startBlock) {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
358 // 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
359 linearScanOrder = new ArrayList<>(blockCount);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
360
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
361 codeEmittingOrder = new ArrayList<>(blockCount);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
362
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
363 // start processing with standard entry block
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
364 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
365
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
366 sortIntoWorkList(startBlock);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
367
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
368 do {
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
369 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
370 processBlock(cur);
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
371 } while (workList.size() > 0);
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
372 }
7317
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
373
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
374 private void processBlock(Block cur) {
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
375 appendBlock(cur);
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
376
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
377 Node endNode = cur.getEndNode();
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
378 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
379 assert cur.numberOfSux() == 2;
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
380 checkAndSortIntoWorkList(cur.suxAt(1));
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
381 checkAndSortIntoWorkList(cur.suxAt(0));
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
382 } else {
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
383 for (Block sux : cur.getSuccessors()) {
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
384 checkAndSortIntoWorkList(sux);
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
385 }
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
386 }
40be0ff5a3ce Include probability when calculating block weight.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7316
diff changeset
387 }
6317
3ee3eb48e683 Clean up ComputeLinearScanOrder. Rename to ComputeBlockOrder.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
388 }