* advanced value range propagation for tree-ssa [not found] <1205565704.14045.ezmlm@gcc.gnu.org> @ 2008-03-15 8:33 ` zhouyi zhou 2008-03-15 22:36 ` Jeff Law 2008-03-16 5:32 ` Daniel Berlin 0 siblings, 2 replies; 6+ messages in thread From: zhouyi zhou @ 2008-03-15 8:33 UTC (permalink / raw) To: gcc-patches High, Currently gcc can optimize following program by threading a block: int fn(int s, int w) { int i; i = 2; if (s) i = 1; if (s) printf("%d\n", i); return 0; } While it cannot handle programs of following kind: int fn(int s, int w) { int i; i = 2; if (s) i = 1; if (w) goto out1; if (s) printf("%d\n", i); out1: return 0; } The advanced value range propagation: http://wiki.freebsd.org/ZhouyiZHOU?action=AttachFile&do=get&target=avrp.patch nicely handles the above case 2 (if s) / \ 8 3 \ | \__ 4---- / 5(if s) / \ 6 10 The advanced value range propagation 1) identify the candidate basic block pairs by recurively matching the dom son and dom parent (in our case block 5 and block 2 are selected) 2) identiy the threadable edge pairs: here edge pair 8-4 and 5-6, 3-4 and 5-10 are selected 3) thread the edges (duplicate the basic blocks between) 2 / \ 8 3 | \ 4'- 4''- | | 5' 5'' / | 6 10 The patch is being compiled and bootstraped on i686-linux m-32. and passed most of regression test by make -k check (the not passed tests are caused the wrong configuration of my machine like libgmp and libmpfr) The patch is rudimentary and very dirty written currently, I will clean it in the future Your review and reply are greatly appreciated. Zhouyi and libmpfr ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: advanced value range propagation for tree-ssa 2008-03-15 8:33 ` advanced value range propagation for tree-ssa zhouyi zhou @ 2008-03-15 22:36 ` Jeff Law 2008-03-16 5:32 ` Daniel Berlin 1 sibling, 0 replies; 6+ messages in thread From: Jeff Law @ 2008-03-15 22:36 UTC (permalink / raw) To: zhouyi zhou; +Cc: gcc-patches zhouyi zhou wrote: > High, > Currently gcc can optimize following program by threading a block: > int > fn(int s, int w) { > int i; > > i = 2; > > if (s) > i = 1; > > if (s) > printf("%d\n", i); > > return 0; > } > > While it cannot handle programs of following kind: > int > fn(int s, int w) { > int i; > > i = 2; > > if (s) > i = 1; > > if (w) > goto out1; > > if (s) > printf("%d\n", i); > > out1: > return 0; > } > > The advanced value range propagation: > http://wiki.freebsd.org/ZhouyiZHOU?action=AttachFile&do=get&target=avrp.patch > > nicely handles the above case > > 2 (if s) > / \ > 8 3 > \ | > \__ 4---- > / > 5(if s) > / \ > 6 10 > > The advanced value range propagation > 1) identify the candidate basic block pairs by > recurively matching the dom son and dom parent (in our case block 5 and block 2 are > selected) > 2) identiy the threadable edge pairs: > here edge pair 8-4 and 5-6, 3-4 and 5-10 are selected > 3) thread the edges (duplicate the basic blocks between) > 2 > / \ > 8 3 > | \ > 4'- 4''- > | | > 5' 5'' > / | > 6 10 > > The patch is being compiled and bootstraped on i686-linux m-32. > and passed most of regression test by make -k check (the not passed tests > are caused the wrong configuration of my machine like libgmp and libmpfr) > > The patch is rudimentary and very dirty written currently, I will clean it in the future Kenny outlined an algorithm which should handle these cases rather easily at the GCC summit a few years back. You might ask him for the slides from his opening presentation as they included the outline of the algorithm. I did an implementation to compare it against the current edge threading code and while it didn't stack up too well, there were a few cases where Kenny's algorithm would find something optimizable, but the current threader would not. Your example is one of those cases. Implementation was fairly easy -- it might be easier to work from Kenny's algorithm than cleaning up your own. Jeff > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: advanced value range propagation for tree-ssa 2008-03-15 8:33 ` advanced value range propagation for tree-ssa zhouyi zhou 2008-03-15 22:36 ` Jeff Law @ 2008-03-16 5:32 ` Daniel Berlin 2008-03-16 9:56 ` Zhouyi Zhou ` (2 more replies) 1 sibling, 3 replies; 6+ messages in thread From: Daniel Berlin @ 2008-03-16 5:32 UTC (permalink / raw) To: zhouyi zhou; +Cc: gcc-patches On Sat, Mar 15, 2008 at 3:57 AM, zhouyi zhou <zhouzhouyi@gmail.com> wrote: > High, > Currently gcc can optimize following program by threading a block: > int > fn(int s, int w) { > int i; > > i = 2; > > if (s) > i = 1; > > if (s) > printf("%d\n", i); > > return 0; > } > > While it cannot handle programs of following kind: > int > fn(int s, int w) { > int i; > > i = 2; > > if (s) > i = 1; > > if (w) > goto out1; > > if (s) > printf("%d\n", i); > > out1: > return 0; > } > > The advanced value range propagation: > http://wiki.freebsd.org/ZhouyiZHOU?action=AttachFile&do=get&target=avrp.patch > > nicely handles the above case > > 2 (if s) > / \ > 8 3 > \ | > \__ 4---- > / > 5(if s) > / \ > 6 10 > > The advanced value range propagation > 1) identify the candidate basic block pairs by > recurively matching the dom son and dom parent (in our case block 5 and block 2 are > selected) > 2) identiy the threadable edge pairs: > here edge pair 8-4 and 5-6, 3-4 and 5-10 are selected > 3) thread the edges (duplicate the basic blocks between) > 2 > / \ > 8 3 > | \ > 4'- 4''- > | | > 5' 5'' > / | > 6 10 > > The patch is being compiled and bootstraped on i686-linux m-32. > and passed most of regression test by make -k check (the not passed tests > are caused the wrong configuration of my machine like libgmp and libmpfr) > > The patch is rudimentary and very dirty written currently, I will clean it in the future > > Your review and reply are greatly appreciated. > Zhouyi > and libmpfr You didn't svn add tree-avrp.c, so it doesn't appear in the patch :) > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: advanced value range propagation for tree-ssa 2008-03-16 5:32 ` Daniel Berlin @ 2008-03-16 9:56 ` Zhouyi Zhou 2008-03-16 10:37 ` Zhouyi Zhou 2008-03-18 12:04 ` zhouyi zhou 2 siblings, 0 replies; 6+ messages in thread From: Zhouyi Zhou @ 2008-03-16 9:56 UTC (permalink / raw) To: gcc-patches; +Cc: Daniel Berlin and thank you Daniel, I do forgot it, the patch is updated as: http://wiki.freebsd.org/ZhouyiZHOU?action=AttachFile&do=get&target=avrp20080316.patch ----- Original Message ----- From: "Daniel Berlin" <dberlin@dberlin.org> To: "zhouyi zhou" <zhouzhouyi@gmail.com> Cc: <gcc-patches@gcc.gnu.org> Sent: Sunday, March 16, 2008 11:41 AM Subject: Re: advanced value range propagation for tree-ssa > You didn't svn add tree-avrp.c, so it doesn't appear in the patch :) ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: advanced value range propagation for tree-ssa 2008-03-16 5:32 ` Daniel Berlin 2008-03-16 9:56 ` Zhouyi Zhou @ 2008-03-16 10:37 ` Zhouyi Zhou 2008-03-18 12:04 ` zhouyi zhou 2 siblings, 0 replies; 6+ messages in thread From: Zhouyi Zhou @ 2008-03-16 10:37 UTC (permalink / raw) To: law; +Cc: gcc-patches Nice! but who is kenny and I can't google him or the slides out :-) (there are so many kenny hehe) On 3/16/08, Jeff Law <law@redhat.com> wrote: Kenny outlined an algorithm which should handle these cases rather ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: advanced value range propagation for tree-ssa 2008-03-16 5:32 ` Daniel Berlin 2008-03-16 9:56 ` Zhouyi Zhou 2008-03-16 10:37 ` Zhouyi Zhou @ 2008-03-18 12:04 ` zhouyi zhou 2 siblings, 0 replies; 6+ messages in thread From: zhouyi zhou @ 2008-03-18 12:04 UTC (permalink / raw) To: Daniel Berlin; +Cc: gcc-patches There is some logic error in the patch, I will provide the corrected one later, sorry for the trouble :-) On Sat, 15 Mar 2008 23:41:11 -0400 "Daniel Berlin" <dberlin@dberlin.org> wrote: > > http://wiki.freebsd.org/ZhouyiZHOU?action=AttachFile&do=get&target=avrp.patch > > You didn't svn add tree-avrp.c, so it doesn't appear in the patch :) > > > ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2008-03-18 10:11 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <1205565704.14045.ezmlm@gcc.gnu.org> 2008-03-15 8:33 ` advanced value range propagation for tree-ssa zhouyi zhou 2008-03-15 22:36 ` Jeff Law 2008-03-16 5:32 ` Daniel Berlin 2008-03-16 9:56 ` Zhouyi Zhou 2008-03-16 10:37 ` Zhouyi Zhou 2008-03-18 12:04 ` zhouyi zhou
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).