Mercurial > hg > truffle

annotate graal/GraalCompiler/src/com/sun/c1x/doc/LoopPeeling.txt @ 2630:c93adece95d2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Small clean up.
author Thomas Wuerthinger <thomas@wuerthinger.net>
date Tue, 10 May 2011 16:47:49 +0200
parents 16b9a8b5ad39
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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