Mercurial > hg > graal-jvmci-8
comparison graal/GraalCompiler/src/com/sun/c1x/graph/IR.java @ 2866:7f14e6b48a9c
added dead code elimination
added ValueAnchor (temp workaround)
more inlining logic (now uses DCE)
IdealGraphPrinter: print even if Scheduler fails
added inlining and DCE tracing options to C1XOptions
author | Lukas Stadler <lukas.stadler@jku.at> |
---|---|
date | Tue, 07 Jun 2011 16:27:08 +0200 |
parents | 7596ae867a7b |
children | 5c545fef2c81 |
comparison
equal
deleted
inserted
replaced
2845:e55543ff91fd | 2866:7f14e6b48a9c |
---|---|
81 if (C1XOptions.PrintTimers) { | 81 if (C1XOptions.PrintTimers) { |
82 C1XTimers.HIR_CREATE.stop(); | 82 C1XTimers.HIR_CREATE.stop(); |
83 C1XTimers.HIR_OPTIMIZE.start(); | 83 C1XTimers.HIR_OPTIMIZE.start(); |
84 } | 84 } |
85 | 85 |
86 new PhiSimplifier(this); | |
87 | |
88 // Graph newGraph = new Graph(); | |
89 // HashMap<Node, Node> replacement = new HashMap<Node, Node>(); | |
90 // replacement.put(compilation.graph.start(), newGraph.start()); | |
91 // replacement.put(compilation.graph.end(), newGraph.end()); | |
92 // newGraph.addDuplicate(compilation.graph.getNodes(), replacement); | |
93 // compilation.graph = newGraph; | |
94 | |
95 Graph graph = compilation.graph; | 86 Graph graph = compilation.graph; |
96 | 87 |
97 // Split critical edges. | 88 // Split critical edges. |
98 List<Node> nodes = graph.getNodes(); | 89 List<Node> nodes = graph.getNodes(); |
99 for (int i = 0; i < nodes.size(); ++i) { | 90 for (int i = 0; i < nodes.size(); ++i) { |
100 Node n = nodes.get(i); | 91 Node n = nodes.get(i); |
101 if (Schedule.trueSuccessorCount(n) > 1) { | 92 if (Schedule.trueSuccessorCount(n) > 1) { |
102 for (int j = 0; j < n.successors().size(); ++j) { | 93 for (int j = 0; j < n.successors().size(); ++j) { |
103 Node succ = n.successors().get(j); | 94 Node succ = n.successors().get(j); |
104 if (Schedule.truePredecessorCount(succ) > 1) { | 95 if (Schedule.truePredecessorCount(succ) > 1) { |
105 Anchor a = new Anchor(null, graph); | 96 Anchor a = new Anchor(graph); |
106 a.successors().setAndClear(1, n, j); | 97 a.successors().setAndClear(1, n, j); |
107 n.successors().set(j, a); | 98 n.successors().set(j, a); |
108 } | 99 } |
109 } | 100 } |
110 } | 101 } |
162 } | 153 } |
163 } | 154 } |
164 | 155 |
165 private void buildGraph() { | 156 private void buildGraph() { |
166 // Graph builder must set the startBlock and the osrEntryBlock | 157 // Graph builder must set the startBlock and the osrEntryBlock |
167 new GraphBuilder(compilation, compilation.method, compilation.graph).build(); | 158 new GraphBuilder(compilation, compilation.method, compilation.graph).build(false); |
168 | 159 |
169 verifyAndPrint("After graph building"); | 160 verifyAndPrint("After graph building"); |
170 | 161 |
171 List<Invoke> trivialInline = new ArrayList<Invoke>(); | 162 DeadCodeElimination dce = new DeadCodeElimination(); |
172 List<Invoke> deoptInline = new ArrayList<Invoke>(); | 163 dce.apply(compilation.graph); |
173 List<RiMethod> deoptMethods = new ArrayList<RiMethod>(); | 164 if (dce.deletedNodeCount > 0) { |
174 for (Node node : compilation.graph.getNodes()) { | 165 verifyAndPrint("After dead code elimination"); |
175 if (node instanceof Invoke) { | 166 } |
176 Invoke invoke = (Invoke) node; | 167 |
177 RiMethod target = invoke.target; | 168 if (C1XOptions.Inline) { |
178 if (target.isResolved() && !Modifier.isNative(target.accessFlags())) { | 169 inlineMethods(); |
179 if (target.canBeStaticallyBound()) { | |
180 trivialInline.add(invoke); | |
181 } else { | |
182 RiMethod concrete = invoke.target.holder().uniqueConcreteMethod(invoke.target); | |
183 if (concrete != null) { | |
184 deoptInline.add(invoke); | |
185 deoptMethods.add(concrete); | |
186 } | |
187 } | |
188 } | |
189 } | |
190 } | |
191 | |
192 int allowedInlinings = 50; | |
193 for (Invoke invoke : trivialInline) { | |
194 if (inlineMethod(invoke, invoke.target)) { | |
195 if (--allowedInlinings <= 0) { | |
196 break; | |
197 } | |
198 } | |
199 } | |
200 | |
201 for (int i = 0; i < deoptInline.size(); i++) { | |
202 Invoke invoke = deoptInline.get(i); | |
203 RiMethod method = deoptMethods.get(i); | |
204 if (inlineMethod(invoke, method)) { | |
205 if (C1XOptions.TraceInlining) { | |
206 System.out.println("registering concrete method assumption..."); | |
207 } | |
208 compilation.assumptions.recordConcreteMethod(invoke.target, method); | |
209 if (--allowedInlinings <= 0) { | |
210 break; | |
211 } | |
212 } | |
213 } | 170 } |
214 | 171 |
215 if (C1XOptions.PrintCompilation) { | 172 if (C1XOptions.PrintCompilation) { |
216 TTY.print(String.format("%3d blocks | ", compilation.stats.blockCount)); | 173 TTY.print(String.format("%3d blocks | ", compilation.stats.blockCount)); |
217 } | 174 } |
218 } | 175 } |
219 | 176 |
177 private void inlineMethods() { | |
178 int inliningSize = compilation.method.code().length; | |
179 boolean inlined; | |
180 int iterations = C1XOptions.MaximumRecursiveInlineLevel; | |
181 do { | |
182 inlined = false; | |
183 | |
184 List<Invoke> trivialInline = new ArrayList<Invoke>(); | |
185 List<Invoke> deoptInline = new ArrayList<Invoke>(); | |
186 List<RiMethod> deoptMethods = new ArrayList<RiMethod>(); | |
187 for (Node node : compilation.graph.getNodes()) { | |
188 if (node instanceof Invoke) { | |
189 Invoke invoke = (Invoke) node; | |
190 RiMethod target = invoke.target; | |
191 if (target.isResolved() && !Modifier.isNative(target.accessFlags())) { | |
192 if (target.canBeStaticallyBound()) { | |
193 trivialInline.add(invoke); | |
194 } else { | |
195 RiMethod concrete = invoke.target.holder().uniqueConcreteMethod(invoke.target); | |
196 if (concrete != null && concrete.isResolved() && !Modifier.isNative(concrete.accessFlags())) { | |
197 deoptInline.add(invoke); | |
198 deoptMethods.add(concrete); | |
199 } | |
200 } | |
201 } | |
202 } | |
203 } | |
204 | |
205 for (Invoke invoke : trivialInline) { | |
206 if (inlineMethod(invoke, invoke.target)) { | |
207 inlined = true; | |
208 inliningSize += invoke.target.code().length; | |
209 if (inliningSize > C1XOptions.MaximumInstructionCount) { | |
210 break; | |
211 } | |
212 } | |
213 } | |
214 | |
215 for (int i = 0; i < deoptInline.size(); i++) { | |
216 Invoke invoke = deoptInline.get(i); | |
217 RiMethod method = deoptMethods.get(i); | |
218 if (inlineMethod(invoke, method)) { | |
219 if (C1XOptions.TraceInlining) { | |
220 System.out.println("registering concrete method assumption..."); | |
221 } | |
222 compilation.assumptions.recordConcreteMethod(invoke.target, method); | |
223 inlined = true; | |
224 inliningSize += method.code().length; | |
225 if (inliningSize > C1XOptions.MaximumInstructionCount) { | |
226 break; | |
227 } | |
228 } | |
229 } | |
230 | |
231 if (inlined) { | |
232 DeadCodeElimination dce = new DeadCodeElimination(); | |
233 dce.apply(compilation.graph); | |
234 if (dce.deletedNodeCount > 0) { | |
235 verifyAndPrint("After dead code elimination"); | |
236 } | |
237 verifyAndPrint("After inlining iteration"); | |
238 } | |
239 | |
240 if (inliningSize > C1XOptions.MaximumInstructionCount) { | |
241 break; | |
242 } | |
243 } while(inlined && (--iterations > 0)); | |
244 } | |
245 | |
220 private boolean inlineMethod(Invoke invoke, RiMethod method) { | 246 private boolean inlineMethod(Invoke invoke, RiMethod method) { |
221 String name = invoke.id() + ": " + CiUtil.format("%H.%n(%p):%r", method, false) + " (" + method.code().length + " bytes)"; | 247 String name = invoke.id() + ": " + CiUtil.format("%H.%n(%p):%r", method, false) + " (" + method.code().length + " bytes)"; |
222 | 248 FrameState stateAfter = invoke.stateAfter(); |
223 if (method.code().length > 50) { | 249 |
250 if (method.code().length > C1XOptions.MaximumInlineSize) { | |
224 if (C1XOptions.TraceInlining) { | 251 if (C1XOptions.TraceInlining) { |
225 System.out.println("not inlining " + name + " because of code size"); | 252 System.out.println("not inlining " + name + " because of code size"); |
226 } | 253 } |
227 return false; | 254 return false; |
228 } | 255 } |
229 | 256 |
257 if (invoke.predecessors().size() == 0) { | |
258 if (C1XOptions.TraceInlining) { | |
259 System.out.println("not inlining " + name + " because the invoke is dead code"); | |
260 } | |
261 return false; | |
262 } | |
263 | |
230 Instruction exceptionEdge = invoke.exceptionEdge(); | 264 Instruction exceptionEdge = invoke.exceptionEdge(); |
231 if (exceptionEdge != null) { | 265 // if (exceptionEdge != null) { |
232 if (C1XOptions.TraceInlining) { | 266 // if (C1XOptions.TraceInlining) { |
233 System.out.println("not inlining " + name + " because of exceptionEdge"); | 267 // System.out.println("not inlining " + name + " because of exceptionEdge"); |
234 } | 268 // } |
235 return false; | 269 // return false; |
236 } | 270 // } |
237 if (!method.holder().isInitialized()) { | 271 if (!method.holder().isInitialized()) { |
238 if (C1XOptions.TraceInlining) { | 272 if (C1XOptions.TraceInlining) { |
239 System.out.println("not inlining " + name + " because of non-initialized class"); | 273 System.out.println("not inlining " + name + " because of non-initialized class"); |
240 } | 274 } |
241 return false; | 275 return false; |
242 } | 276 } |
243 | 277 |
244 if (C1XOptions.TraceInlining) { | 278 if (C1XOptions.TraceInlining) { |
245 System.out.println("building graph: " + name); | 279 System.out.printf("Building graph for %s, locals: %d, stack: %d\n", name, method.maxLocals(), method.maxStackSize()); |
246 } | 280 } |
281 | |
247 CompilerGraph graph = new CompilerGraph(); | 282 CompilerGraph graph = new CompilerGraph(); |
248 new GraphBuilder(compilation, method, graph).build(); | 283 new GraphBuilder(compilation, method, graph).build(true); |
249 | 284 |
250 boolean withReceiver = !Modifier.isStatic(method.accessFlags()); | 285 boolean withReceiver = !Modifier.isStatic(method.accessFlags()); |
251 | 286 |
252 int argumentCount = method.signature().argumentCount(false); | 287 int argumentCount = method.signature().argumentCount(false); |
253 Value[] parameters = new Value[argumentCount + (withReceiver ? 1 : 0)]; | 288 Value[] parameters = new Value[argumentCount + (withReceiver ? 1 : 0)]; |
264 HashMap<Node, Node> replacements = new HashMap<Node, Node>(); | 299 HashMap<Node, Node> replacements = new HashMap<Node, Node>(); |
265 ArrayList<Node> nodes = new ArrayList<Node>(); | 300 ArrayList<Node> nodes = new ArrayList<Node>(); |
266 ArrayList<Node> frameStates = new ArrayList<Node>(); | 301 ArrayList<Node> frameStates = new ArrayList<Node>(); |
267 Return returnNode = null; | 302 Return returnNode = null; |
268 Unwind unwindNode = null; | 303 Unwind unwindNode = null; |
269 StartNode startNode = null; | 304 StartNode startNode = graph.start(); |
270 boolean invokes = false; | |
271 for (Node node : graph.getNodes()) { | 305 for (Node node : graph.getNodes()) { |
272 if (node != null) { | 306 if (node != null) { |
273 if (node instanceof StartNode) { | 307 if (node instanceof StartNode) { |
274 startNode = (StartNode) node; | 308 assert startNode == node; |
275 } else if (node instanceof Local) { | 309 } else if (node instanceof Local) { |
276 replacements.put(node, parameters[((Local) node).index()]); | 310 replacements.put(node, parameters[((Local) node).index()]); |
277 } else { | 311 } else { |
278 nodes.add(node); | 312 nodes.add(node); |
279 if (node instanceof Return) { | 313 if (node instanceof Return) { |
284 frameStates.add(node); | 318 frameStates.add(node); |
285 } | 319 } |
286 } | 320 } |
287 } | 321 } |
288 } | 322 } |
289 if (unwindNode != null) { | |
290 if (C1XOptions.TraceInlining) { | |
291 System.out.println("not inlining " + name + " because of unwind node"); | |
292 } | |
293 return false; | |
294 } | |
295 if (invokes) { | |
296 if (C1XOptions.TraceInlining) { | |
297 System.out.println("not inlining " + name + " because of invokes"); | |
298 } | |
299 return false; | |
300 } | |
301 | 323 |
302 if (C1XOptions.TraceInlining) { | 324 if (C1XOptions.TraceInlining) { |
325 printGraph("Subgraph " + CiUtil.format("%H.%n(%p):%r", method, false), graph); | |
303 System.out.println("inlining " + name + ": " + frameStates.size() + " frame states, " + nodes.size() + " nodes"); | 326 System.out.println("inlining " + name + ": " + frameStates.size() + " frame states, " + nodes.size() + " nodes"); |
304 } | 327 } |
305 | 328 |
329 assert invoke.predecessors().size() == 1 : "size: " + invoke.predecessors().size(); | |
306 Instruction pred; | 330 Instruction pred; |
307 if (withReceiver) { | 331 if (withReceiver) { |
308 pred = new NullCheck(parameters[0], compilation.graph); | 332 pred = new NullCheck(parameters[0], compilation.graph); |
309 } else { | 333 } else { |
310 pred = new Merge(compilation.graph); | 334 pred = new Merge(compilation.graph); |
311 } | 335 } |
312 assert invoke.predecessors().size() == 1; | |
313 invoke.predecessors().get(0).successors().replace(invoke, pred); | 336 invoke.predecessors().get(0).successors().replace(invoke, pred); |
314 replacements.put(startNode, pred); | 337 replacements.put(startNode, pred); |
315 | 338 |
316 Map<Node, Node> duplicates = compilation.graph.addDuplicate(nodes, replacements); | 339 Map<Node, Node> duplicates = compilation.graph.addDuplicate(nodes, replacements); |
317 | 340 |
329 | 352 |
330 assert returnDuplicate.predecessors().size() == 1; | 353 assert returnDuplicate.predecessors().size() == 1; |
331 Node returnPred = returnDuplicate.predecessors().get(0); | 354 Node returnPred = returnDuplicate.predecessors().get(0); |
332 int index = returnDuplicate.predecessorsIndex().get(0); | 355 int index = returnDuplicate.predecessorsIndex().get(0); |
333 returnPred.successors().setAndClear(index, invoke, 0); | 356 returnPred.successors().setAndClear(index, invoke, 0); |
334 | |
335 returnDuplicate.delete(); | 357 returnDuplicate.delete(); |
336 } | 358 } |
337 FrameState stateAfter = invoke.stateAfter(); | 359 |
360 // if (invoke.next() instanceof Merge) { | |
361 // ((Merge) invoke.next()).removePhiPredecessor(invoke); | |
362 // } | |
363 // invoke.successors().clearAll(); | |
364 invoke.inputs().clearAll(); | |
365 invoke.setExceptionEdge(null); | |
366 // invoke.delete(); | |
367 | |
368 | |
369 if (exceptionEdge != null) { | |
370 if (unwindNode != null) { | |
371 assert unwindNode.predecessors().size() == 1; | |
372 assert exceptionEdge.successors().size() == 1; | |
373 ExceptionObject obj = (ExceptionObject) exceptionEdge; | |
374 | |
375 List<Node> usages = new ArrayList<Node>(obj.usages()); | |
376 for (Node usage : usages) { | |
377 if (replacements.containsKey(unwindNode.exception())) { | |
378 usage.inputs().replace(obj, replacements.get(unwindNode.exception())); | |
379 } else { | |
380 usage.inputs().replace(obj, duplicates.get(unwindNode.exception())); | |
381 } | |
382 } | |
383 Node unwindDuplicate = duplicates.get(unwindNode); | |
384 unwindDuplicate.inputs().clearAll(); | |
385 | |
386 assert unwindDuplicate.predecessors().size() == 1; | |
387 Node unwindPred = unwindDuplicate.predecessors().get(0); | |
388 int index = unwindDuplicate.predecessorsIndex().get(0); | |
389 unwindPred.successors().setAndClear(index, obj, 0); | |
390 | |
391 obj.inputs().clearAll(); | |
392 obj.delete(); | |
393 unwindDuplicate.delete(); | |
394 | |
395 } | |
396 } | |
397 | |
398 // adjust all frame states that were copied | |
338 if (frameStates.size() > 0) { | 399 if (frameStates.size() > 0) { |
339 FrameState outerFrameState = stateAfter.duplicateModified(invoke.bci, invoke.kind); | 400 FrameState outerFrameState = stateAfter.duplicateModified(invoke.bci, invoke.kind); |
340 for (Node frameState : frameStates) { | 401 for (Node frameState : frameStates) { |
341 ((FrameState) duplicates.get(frameState)).setOuterFrameState(outerFrameState); | 402 ((FrameState) duplicates.get(frameState)).setOuterFrameState(outerFrameState); |
342 } | 403 } |
343 } | 404 } |
344 | 405 |
345 invoke.successors().clearAll(); | 406 if (C1XOptions.TraceInlining) { |
346 invoke.inputs().clearAll(); | 407 verifyAndPrint("After inlining " + CiUtil.format("%H.%n(%p):%r", method, false)); |
347 invoke.delete(); | 408 } |
348 | |
349 stateAfter.delete(); | |
350 | |
351 deleteUnused(exceptionEdge); | |
352 | |
353 verifyAndPrint("After inlining " + CiUtil.format("%H.%n(%p):%r", method, false)); | |
354 return true; | 409 return true; |
355 } | |
356 | |
357 private void deleteUnused(Node node) { | |
358 if (node != null && node.predecessors().size() == 0) { | |
359 if (node instanceof ExceptionObject) { | |
360 Node successor = node.successors().get(0); | |
361 node.successors().clearAll(); | |
362 if (successor instanceof ExceptionDispatch) { | |
363 ExceptionDispatch dispatch = (ExceptionDispatch) successor; | |
364 Node succ1 = dispatch.catchSuccessor(); | |
365 Node succ2 = dispatch.otherSuccessor(); | |
366 if (succ1 instanceof Merge) { | |
367 ((Merge) succ1).removePhiPredecessor(dispatch); | |
368 } | |
369 if (succ2 instanceof Merge) { | |
370 ((Merge) succ2).removePhiPredecessor(dispatch); | |
371 } | |
372 dispatch.successors().clearAll(); | |
373 deleteUnused(succ1); | |
374 deleteUnused(succ2); | |
375 dispatch.delete(); | |
376 } else { | |
377 assert successor instanceof Merge; | |
378 System.out.println("succ: " + successor.successors().get(0)); | |
379 Node next = successor.successors().get(0); | |
380 successor.successors().clearAll(); | |
381 deleteUnused(next); | |
382 successor.delete(); | |
383 } | |
384 node.delete(); | |
385 } else if (node instanceof Unwind) { | |
386 node.delete(); | |
387 } | |
388 } | |
389 } | 410 } |
390 | 411 |
391 /** | 412 /** |
392 * Gets the linear scan ordering of blocks as a list. | 413 * Gets the linear scan ordering of blocks as a list. |
393 * @return the blocks in linear scan order | 414 * @return the blocks in linear scan order |
415 print(false); | 436 print(false); |
416 } | 437 } |
417 | 438 |
418 if (compilation.compiler.isObserved()) { | 439 if (compilation.compiler.isObserved()) { |
419 compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, phase, compilation.graph, true, false)); | 440 compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, phase, compilation.graph, true, false)); |
441 } | |
442 } | |
443 | |
444 public void printGraph(String phase, Graph graph) { | |
445 if (C1XOptions.PrintHIR && !TTY.isSuppressed()) { | |
446 TTY.println(phase); | |
447 print(false); | |
448 } | |
449 | |
450 if (compilation.compiler.isObserved()) { | |
451 compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, phase, graph, true, false)); | |
420 } | 452 } |
421 } | 453 } |
422 | 454 |
423 public int numLoops() { | 455 public int numLoops() { |
424 return compilation.stats.loopCount; | 456 return compilation.stats.loopCount; |