From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 25373 invoked by alias); 15 Mar 2008 07:59:31 -0000 Received: (qmail 25363 invoked by uid 22791); 15 Mar 2008 07:59:30 -0000 X-Spam-Check-By: sourceware.org Received: from ercist.iscas.ac.cn (HELO ercist.iscas.ac.cn) (124.16.138.3) by sourceware.org (qpsmtpd/0.31) with SMTP; Sat, 15 Mar 2008 07:59:11 +0000 Received: (qmail 14655 invoked by uid 98); 15 Mar 2008 07:58:23 -0000 Received: from 124.16.138.62 by ercist.iscas.ac.cn (envelope-from , uid 89) with qmail-scanner-1.25 (spamassassin: 3.1.0. Clear:RC:1(124.16.138.62):SA:0(-2.5/8.0):. Processed in 2.586773 secs); 15 Mar 2008 07:58:23 -0000 X-Qmail-Scanner-Mail-From: zhouzhouyi@gmail.com via ercist.iscas.ac.cn X-Qmail-Scanner: 1.25 (Clear:RC:1(124.16.138.62):SA:0(-2.5/8.0):. Processed in 2.586773 secs) Received: from unknown (HELO zzy.H.qngy.gscas) (zhouzhouyi@ercist.iscas.ac.cn@124.16.138.62) by 0 with SMTP; 15 Mar 2008 07:58:20 -0000 Date: Sat, 15 Mar 2008 08:33:00 -0000 From: zhouyi zhou To: gcc-patches@gcc.gnu.org Subject: advanced value range propagation for tree-ssa Message-Id: <20080315155725.20cf482c.zhouzhouyi@gmail.com> In-Reply-To: <1205565704.14045.ezmlm@gcc.gnu.org> References: <1205565704.14045.ezmlm@gcc.gnu.org> X-Mailer: Sylpheed version 1.0.4 (GTK+ 1.2.10; i386-portbld-freebsd5.4) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2008-03/txt/msg00930.txt.bz2 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