Mercurial > hg > truffle

comparison graal/Compiler/src/com/sun/c1x/graph/IR.java @ 2507:9ec15d6914ca

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Pull over of compiler from maxine repository.
author Thomas Wuerthinger <thomas@wuerthinger.net>
date Wed, 27 Apr 2011 11:43:22 +0200
parents
children
comparison
equal deleted inserted replaced
2506:4a3bf8a5bf41 2507:9ec15d6914ca
1 /*
2 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package com.sun.c1x.graph;
24
25 import java.util.*;
26
27 import com.sun.c1x.*;
28 import com.sun.c1x.debug.*;
29 import com.sun.c1x.ir.*;
30 import com.sun.c1x.observer.*;
31 import com.sun.c1x.opt.*;
32 import com.sun.c1x.value.*;
33
34 /**
35 * This class implements the overall container for the HIR (high-level IR) graph
36 * and directs its construction, optimization, and finalization.
37 *
38 * @author Thomas Wuerthinger
39 * @author Ben L. Titzer
40 */
41 public class IR {
42
43 /**
44 * The compilation associated with this IR.
45 */
46 public final C1XCompilation compilation;
47
48 /**
49 * The start block of this IR.
50 */
51 public BlockBegin startBlock;
52
53 /**
54 * The entry block for an OSR compile.
55 */
56 public BlockBegin osrEntryBlock;
57
58 /**
59 * The top IRScope.
60 */
61 public IRScope topScope;
62
63 /**
64 * The linear-scan ordered list of blocks.
65 */
66 private List<BlockBegin> orderedBlocks;
67
68 /**
69 * Creates a new IR instance for the specified compilation.
70 * @param compilation the compilation
71 */
72 public IR(C1XCompilation compilation) {
73 this.compilation = compilation;
74 }
75
76 /**
77 * Builds the graph, optimizes it, and computes the linear scan block order.
78 */
79 public void build() {
80 if (C1XOptions.PrintTimers) {
81 C1XTimers.HIR_CREATE.start();
82 }
83
84 buildGraph();
85
86 if (C1XOptions.PrintTimers) {
87 C1XTimers.HIR_CREATE.stop();
88 C1XTimers.HIR_OPTIMIZE.start();
89 }
90
91 optimize1();
92 computeLinearScanOrder();
93 optimize2();
94
95 if (C1XOptions.PrintTimers) {
96 C1XTimers.HIR_OPTIMIZE.stop();
97 }
98 }
99
100 private void buildGraph() {
101 topScope = new IRScope(null, null, compilation.method, compilation.osrBCI);
102
103 // Graph builder must set the startBlock and the osrEntryBlock
104 new GraphBuilder(compilation, this).build(topScope);
105 assert startBlock != null;
106 verifyAndPrint("After graph building");
107
108 if (C1XOptions.PrintCompilation) {
109 TTY.print(String.format("%3d blocks | ", this.numberOfBlocks()));
110 }
111 }
112
113 private void optimize1() {
114 if (!compilation.isTypesafe()) {
115 new UnsafeCastEliminator(this);
116 verifyAndPrint("After unsafe cast elimination");
117 }
118
119 // do basic optimizations
120 if (C1XOptions.PhiSimplify) {
121 new PhiSimplifier(this);
122 verifyAndPrint("After phi simplification");
123 }
124 if (C1XOptions.OptNullCheckElimination) {
125 new NullCheckEliminator(this);
126 verifyAndPrint("After null check elimination");
127 }
128 if (C1XOptions.OptDeadCodeElimination1) {
129 new LivenessMarker(this).removeDeadCode();
130 verifyAndPrint("After dead code elimination 1");
131 }
132 if (C1XOptions.OptCEElimination) {
133 new CEEliminator(this);
134 verifyAndPrint("After CEE elimination");
135 }
136 if (C1XOptions.OptBlockMerging) {
137 new BlockMerger(this);
138 verifyAndPrint("After block merging");
139 }
140
141 if (compilation.compiler.extensions != null) {
142 for (C1XCompilerExtension ext : compilation.compiler.extensions) {
143 ext.run(this);
144 }
145 }
146 }
147
148 private void computeLinearScanOrder() {
149 if (C1XOptions.GenLIR) {
150 makeLinearScanOrder();
151 verifyAndPrint("After linear scan order");
152 }
153 }
154
155 private void makeLinearScanOrder() {
156 if (orderedBlocks == null) {
157 CriticalEdgeFinder finder = new CriticalEdgeFinder(this);
158 startBlock.iteratePreOrder(finder);
159 finder.splitCriticalEdges();
160 ComputeLinearScanOrder computeLinearScanOrder = new ComputeLinearScanOrder(compilation.stats.blockCount, startBlock);
161 orderedBlocks = computeLinearScanOrder.linearScanOrder();
162 compilation.stats.loopCount = computeLinearScanOrder.numLoops();
163 computeLinearScanOrder.printBlocks();
164 }
165 }
166
167 private void optimize2() {
168 // do more advanced, dominator-based optimizations
169 if (C1XOptions.OptGlobalValueNumbering) {
170 makeLinearScanOrder();
171 new GlobalValueNumberer(this);
172 verifyAndPrint("After global value numbering");
173 }
174 if (C1XOptions.OptDeadCodeElimination2) {
175 new LivenessMarker(this).removeDeadCode();
176 verifyAndPrint("After dead code elimination 2");
177 }
178
179 }
180
181 /**
182 * Gets the linear scan ordering of blocks as a list.
183 * @return the blocks in linear scan order
184 */
185 public List<BlockBegin> linearScanOrder() {
186 return orderedBlocks;
187 }
188
189 private void print(boolean cfgOnly) {
190 if (!TTY.isSuppressed()) {
191 TTY.println("IR for " + compilation.method);
192 final InstructionPrinter ip = new InstructionPrinter(TTY.out());
193 final BlockPrinter bp = new BlockPrinter(this, ip, cfgOnly, false);
194 startBlock.iteratePreOrder(bp);
195 }
196 }
197
198 /**
199 * Verifies the IR and prints it out if the relevant options are set.
200 * @param phase the name of the phase for printing
201 */
202 public void verifyAndPrint(String phase) {
203 printToTTY(phase);
204
205 if (compilation.compiler.isObserved()) {
206 compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, phase, startBlock, true, false));
207 }
208 }
209
210 private void printToTTY(String phase) {
211 if (C1XOptions.PrintHIR && !TTY.isSuppressed()) {
212 TTY.println(phase);
213 print(false);
214 }
215 }
216
217 /**
218 * Creates and inserts a new block between this block and the specified successor,
219 * altering the successor and predecessor lists of involved blocks appropriately.
220 * @param source the source of the edge
221 * @param target the successor before which to insert a block
222 * @return the new block inserted
223 */
224 public BlockBegin splitEdge(BlockBegin source, BlockBegin target) {
225 int bci;
226 if (target.predecessors().size() == 1) {
227 bci = target.bci();
228 } else {
229 bci = source.end().bci();
230 }
231
232 // create new successor and mark it for special block order treatment
233 BlockBegin newSucc = new BlockBegin(bci, nextBlockNumber());
234
235 newSucc.setCriticalEdgeSplit(true);
236
237 // This goto is not a safepoint.
238 Goto e = new Goto(target, null, false);
239 newSucc.setNext(e, bci);
240 newSucc.setEnd(e);
241 // setup states
242 FrameState s = source.end().stateAfter();
243 newSucc.setStateBefore(s);
244 e.setStateAfter(s);
245 assert newSucc.stateBefore().localsSize() == s.localsSize();
246 assert newSucc.stateBefore().stackSize() == s.stackSize();
247 assert newSucc.stateBefore().locksSize() == s.locksSize();
248 // link predecessor to new block
249 source.end().substituteSuccessor(target, newSucc);
250
251 // The ordering needs to be the same, so remove the link that the
252 // set_end call above added and substitute the new_sux for this
253 // block.
254 target.removePredecessor(newSucc);
255
256 // the successor could be the target of a switch so it might have
257 // multiple copies of this predecessor, so substitute the new_sux
258 // for the first and delete the rest.
259 List<BlockBegin> list = target.predecessors();
260 int x = list.indexOf(source);
261 assert x >= 0;
262 list.set(x, newSucc);
263 newSucc.addPredecessor(source);
264 Iterator<BlockBegin> iterator = list.iterator();
265 while (iterator.hasNext()) {
266 if (iterator.next() == source) {
267 iterator.remove();
268 newSucc.addPredecessor(source);
269 }
270 }
271 return newSucc;
272 }
273
274 public void replaceBlock(BlockBegin oldBlock, BlockBegin newBlock) {
275 assert !oldBlock.isExceptionEntry() : "cannot replace exception handler blocks (yet)";
276 for (BlockBegin succ : oldBlock.end().successors()) {
277 succ.removePredecessor(oldBlock);
278 }
279 for (BlockBegin pred : oldBlock.predecessors()) {
280 // substitute the new successor for this block in each predecessor
281 pred.end().substituteSuccessor(oldBlock, newBlock);
282 // and add each predecessor to the successor
283 newBlock.addPredecessor(pred);
284 }
285 // this block is now disconnected; remove all its incoming and outgoing edges
286 oldBlock.predecessors().clear();
287 oldBlock.end().successors().clear();
288 }
289
290 /**
291 * Disconnects the specified block from all other blocks.
292 * @param block the block to remove from the graph
293 */
294 public void disconnectFromGraph(BlockBegin block) {
295 for (BlockBegin p : block.predecessors()) {
296 p.end().successors().remove(block);
297 }
298 for (BlockBegin s : block.end().successors()) {
299 s.predecessors().remove(block);
300 }
301 }
302
303 public int nextBlockNumber() {
304 return compilation.stats.blockCount++;
305 }
306
307 public int numberOfBlocks() {
308 return compilation.stats.blockCount;
309 }
310
311 public int numLoops() {
312 return compilation.stats.loopCount;
313 }
314 }