Mercurial > hg > truffle
annotate graal/GraalCompiler/src/com/sun/c1x/doc/LoopPeeling.txt @ 2509:16b9a8b5ad39
Renamings Runtime=>GraalRuntime and Compiler=>GraalCompiler
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 27 Apr 2011 11:50:44 +0200 |
parents | graal/Compiler/src/com/sun/c1x/doc/LoopPeeling.txt@9ec15d6914ca |
children |
rev | line source |
---|---|
2507
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
1 Remaining Issues in the Loop Peeling optimization (September/18/09) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
2 =================================================================== |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
3 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
4 Known Problems: |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
5 Currently loop peeling is not working when the loop has exception |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
6 blocks. The algorithm has to be updated to handle these cases. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
7 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
8 Limitations: |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
9 The algorithm performs loop peeling only on innermost loops. However, |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
10 this is not a limitation. If one wants to peel the outermost loop(s), |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
11 after peeling the innermost loop, an additional pass is necessary |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
12 to update the blocks of the outermost loop, since after peeling |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
13 the innermost loop, newer blocks are added to the CFG. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
14 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
15 Current status as of 09/18/2009 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
16 After running using hir configuration, with optimization level 3, the |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
17 following test cases produce wrong results: |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
18 (4 fails) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
19 233: jtt/except/Catch_Loop01.java: (4) failed with unexpected com.sun.c1x.ci.CiBailout (expected -170) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
20 234: jtt/except/Catch_Loop02.java: (4) failed with unexpected com.sun.c1x.ci.CiBailout (expected -170) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
21 245: jtt/except/Catch_StackOverflowError_03.java: (0) failed with unexpected com.sun.c1x.ci.CiBailout (expected 0) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
22 272: jtt/hotpath/HP_array04.java: (80) failed with unexpected java.lang.AssertionError (expected 15645) |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
23 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
24 All of them are related the known problem aforementioned. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
25 All the tests have the innermost loops peeled, and produce right results. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
26 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
27 Future Work: |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
28 1- Add more loop tests to jtt. New tests should run the loop 0, 1, 2 or more iterations. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
29 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
30 2- Peel loops with exception blocks. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
31 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
32 3- Currently, all innermost loops are peeled. Should we add logic to filter out some loops from loop peeling? |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
33 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
34 4- Improve the way instructions are cloned. Now the algorithm visits the blocks in BFS order, which |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
35 might produce errors depending on the order the blocks are visited. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
36 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
37 5- After inserting new phi instructions at exit blocks, we need to iterate over the remaining CFG to update instructions |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
38 that may use the new phi. The way it's done now might me inefficient if the block has more than one exit node, since |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
39 we can iterate over the same block more than once. This needs to be improved. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
40 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
41 5- For performance reasons, improve the way loops are represented, for example, to use a bitmap to represent the loop blocks. |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
42 |
9ec15d6914ca
Pull over of compiler from maxine repository.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
diff
changeset
|
43 |