Mercurial > hg > truffle

annotate graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ControlFlowOptimizer.java @ 14806:a8723f1ff542

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LIR renamed setter and getter functions.
author Josef Eisl <josef.eisl@jku.at>
date Mon, 17 Mar 2014 19:18:35 +0100
parents 6ce74db1c9fb
children f4e31f06b019
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1 /*
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
2 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
4 *
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
7 * published by the Free Software Foundation.
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
8 *
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
13 * accompanied this code).
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
14 *
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
18 *
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
21 * questions.
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
22 */
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
23 package com.oracle.graal.lir;
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
24
13268
68b964b6dc8e introduced BlockEndOp interface and require that every LIR block is terminated by such an operation
Doug Simon <doug.simon@oracle.com>
parents: 7530
diff changeset
25 import static com.oracle.graal.lir.LIR.*;
68b964b6dc8e introduced BlockEndOp interface and require that every LIR block is terminated by such an operation
Doug Simon <doug.simon@oracle.com>
parents: 7530
diff changeset
26
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
27 import java.util.*;
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
28
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
29 import com.oracle.graal.debug.*;
6529
2e96dc4eb8e2 renamed package: com.oracle.graal.lir.cfg -> com.oracle.graal.nodes.cfg
Doug Simon <doug.simon@oracle.com>
parents: 6411
diff changeset
30 import com.oracle.graal.nodes.cfg.*;
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
31
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
32 /**
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
33 * This class performs basic optimizations on the control flow graph after LIR generation.
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
34 */
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
35 public final class ControlFlowOptimizer {
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
36
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
37 /**
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
38 * Performs control flow optimizations on the given LIR graph.
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
39 */
14787
6ce74db1c9fb Use List<T> instead of Iterable<T> in AbstractBlock to (temporary) allow editing.
Josef Eisl <josef.eisl@jku.at>
parents: 14786
diff changeset
40 public static <T extends AbstractBlock<T>> void optimize(LIR lir, List<T> codeEmittingOrder) {
6ce74db1c9fb Use List<T> instead of Iterable<T> in AbstractBlock to (temporary) allow editing.
Josef Eisl <josef.eisl@jku.at>
parents: 14786
diff changeset
41 ControlFlowOptimizer.deleteEmptyBlocks(lir, codeEmittingOrder);
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
42 }
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
43
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
44 private ControlFlowOptimizer() {
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
45 }
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
46
14016
555867401850 Make Debug.metric objects static
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13843
diff changeset
47 private static final DebugMetric BLOCKS_DELETED = Debug.metric("BlocksDeleted");
555867401850 Make Debug.metric objects static
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13843
diff changeset
48
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
49 /**
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
50 * Checks whether a block can be deleted. Only blocks with exactly one successor and an
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
51 * unconditional branch to this successor are eligable.
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
52 *
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
53 * @param block the block checked for deletion
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
54 * @return whether the block can be deleted
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
55 */
14786
a6595f1b55b0 Make LIR use AbstractBlock. (errors)
Josef Eisl <josef.eisl@jku.at>
parents: 14016
diff changeset
56 private static boolean canDeleteBlock(LIR lir, AbstractBlock<?> block) {
a6595f1b55b0 Make LIR use AbstractBlock. (errors)
Josef Eisl <josef.eisl@jku.at>
parents: 14016
diff changeset
57 if (block.getSuccessorCount() != 1 || block.getPredecessorCount() == 0 || block.getSuccessors().iterator().next() == block) {
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
58 return false;
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
59 }
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
60
14806
a8723f1ff542 LIR renamed setter and getter functions.
Josef Eisl <josef.eisl@jku.at>
parents: 14787
diff changeset
61 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
62
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
63 assert instructions.size() >= 2 : "block must have label and branch";
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
64 assert instructions.get(0) instanceof StandardOp.LabelOp : "first instruction must always be a label";
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
65 assert instructions.get(instructions.size() - 1) instanceof StandardOp.JumpOp : "last instruction must always be a branch";
14806
a8723f1ff542 LIR renamed setter and getter functions.
Josef Eisl <josef.eisl@jku.at>
parents: 14787
diff changeset
66 assert ((StandardOp.JumpOp) instructions.get(instructions.size() - 1)).destination().label() == ((StandardOp.LabelOp) lir.getLIRforBlock(block.getSuccessors().iterator().next()).get(0)).getLabel() : "branch target must be the successor";
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
67
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
68 // Block must have exactly one successor.
13497
55987bbeec42 Bugfix: do not eliminate exception handler entry blocks
Christian Wimmer <christian.wimmer@oracle.com>
parents: 13268
diff changeset
69 return instructions.size() == 2 && !instructions.get(instructions.size() - 1).hasState() && !block.isExceptionEntry();
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
70 }
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
71
14786
a6595f1b55b0 Make LIR use AbstractBlock. (errors)
Josef Eisl <josef.eisl@jku.at>
parents: 14016
diff changeset
72 private static void alignBlock(LIR lir, AbstractBlock<?> block) {
13843
f5f81bc9c9f0 Align successor when deleting aligned empty block.
Roland Schatz <roland.schatz@oracle.com>
parents: 13497
diff changeset
73 if (!block.isAligned()) {
f5f81bc9c9f0 Align successor when deleting aligned empty block.
Roland Schatz <roland.schatz@oracle.com>
parents: 13497
diff changeset
74 block.setAlign(true);
14806
a8723f1ff542 LIR renamed setter and getter functions.
Josef Eisl <josef.eisl@jku.at>
parents: 14787
diff changeset
75 List<LIRInstruction> instructions = lir.getLIRforBlock(block);
13843
f5f81bc9c9f0 Align successor when deleting aligned empty block.
Roland Schatz <roland.schatz@oracle.com>
parents: 13497
diff changeset
76 assert instructions.get(0) instanceof StandardOp.LabelOp : "first instruction must always be a label";
f5f81bc9c9f0 Align successor when deleting aligned empty block.
Roland Schatz <roland.schatz@oracle.com>
parents: 13497
diff changeset
77 StandardOp.LabelOp label = (StandardOp.LabelOp) instructions.get(0);
f5f81bc9c9f0 Align successor when deleting aligned empty block.
Roland Schatz <roland.schatz@oracle.com>
parents: 13497
diff changeset
78 instructions.set(0, new StandardOp.LabelOp(label.getLabel(), true));
f5f81bc9c9f0 Align successor when deleting aligned empty block.
Roland Schatz <roland.schatz@oracle.com>
parents: 13497
diff changeset
79 }
f5f81bc9c9f0 Align successor when deleting aligned empty block.
Roland Schatz <roland.schatz@oracle.com>
parents: 13497
diff changeset
80 }
f5f81bc9c9f0 Align successor when deleting aligned empty block.
Roland Schatz <roland.schatz@oracle.com>
parents: 13497
diff changeset
81
14787
6ce74db1c9fb Use List<T> instead of Iterable<T> in AbstractBlock to (temporary) allow editing.
Josef Eisl <josef.eisl@jku.at>
parents: 14786
diff changeset
82 private static <T extends AbstractBlock<T>> void deleteEmptyBlocks(LIR lir, List<T> blocks) {
13268
68b964b6dc8e introduced BlockEndOp interface and require that every LIR block is terminated by such an operation
Doug Simon <doug.simon@oracle.com>
parents: 7530
diff changeset
83 assert verifyBlocks(lir, blocks);
14787
6ce74db1c9fb Use List<T> instead of Iterable<T> in AbstractBlock to (temporary) allow editing.
Josef Eisl <josef.eisl@jku.at>
parents: 14786
diff changeset
84 Iterator<T> iterator = blocks.iterator();
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
85 while (iterator.hasNext()) {
14787
6ce74db1c9fb Use List<T> instead of Iterable<T> in AbstractBlock to (temporary) allow editing.
Josef Eisl <josef.eisl@jku.at>
parents: 14786
diff changeset
86 T block = iterator.next();
13268
68b964b6dc8e introduced BlockEndOp interface and require that every LIR block is terminated by such an operation
Doug Simon <doug.simon@oracle.com>
parents: 7530
diff changeset
87 if (canDeleteBlock(lir, block)) {
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
88 // adjust successor and predecessor lists
14787
6ce74db1c9fb Use List<T> instead of Iterable<T> in AbstractBlock to (temporary) allow editing.
Josef Eisl <josef.eisl@jku.at>
parents: 14786
diff changeset
89 T other = block.getSuccessors().iterator().next();
6ce74db1c9fb Use List<T> instead of Iterable<T> in AbstractBlock to (temporary) allow editing.
Josef Eisl <josef.eisl@jku.at>
parents: 14786
diff changeset
90 for (AbstractBlock<T> pred : block.getPredecessors()) {
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
91 Collections.replaceAll(pred.getSuccessors(), block, other);
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
92 }
7499
ca3e5df0e6cf Small clean up of access to predecessor/successor of blocks.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7498
diff changeset
93 for (int i = 0; i < other.getPredecessorCount(); i++) {
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
94 if (other.getPredecessors().get(i) == block) {
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
95 other.getPredecessors().remove(i);
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
96 other.getPredecessors().addAll(i, block.getPredecessors());
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
97 }
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
98 }
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
99 block.getSuccessors().clear();
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
100 block.getPredecessors().clear();
13843
f5f81bc9c9f0 Align successor when deleting aligned empty block.
Roland Schatz <roland.schatz@oracle.com>
parents: 13497
diff changeset
101
f5f81bc9c9f0 Align successor when deleting aligned empty block.
Roland Schatz <roland.schatz@oracle.com>
parents: 13497
diff changeset
102 if (block.isAligned()) {
f5f81bc9c9f0 Align successor when deleting aligned empty block.
Roland Schatz <roland.schatz@oracle.com>
parents: 13497
diff changeset
103 alignBlock(lir, other);
f5f81bc9c9f0 Align successor when deleting aligned empty block.
Roland Schatz <roland.schatz@oracle.com>
parents: 13497
diff changeset
104 }
f5f81bc9c9f0 Align successor when deleting aligned empty block.
Roland Schatz <roland.schatz@oracle.com>
parents: 13497
diff changeset
105
14016
555867401850 Make Debug.metric objects static
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 13843
diff changeset
106 BLOCKS_DELETED.increment();
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
107 iterator.remove();
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
108 }
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
109 }
13268
68b964b6dc8e introduced BlockEndOp interface and require that every LIR block is terminated by such an operation
Doug Simon <doug.simon@oracle.com>
parents: 7530
diff changeset
110 assert verifyBlocks(lir, blocks);
6321
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
111 }
9418ff4c9e7c Clean up ControlFlowOptimizer.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
112 }