From patchwork Tue Oct 30 14:51:22 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 195510 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 946622C0085 for ; Wed, 31 Oct 2012 01:52:14 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1352213534; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Date: From:To:Subject:Message-ID:MIME-Version:Content-Type: Content-Disposition:User-Agent:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=/uzc2hTrmAYMC5mP8RrdVpShE7E=; b=igLf9haXb/cuRCJ nefpY31QBtgPIzXoowyyO/+PiAxu0wR0Q+JfYLQ1TIylKkkqZwBx99dRlOlr5FMf yoK1wMm+5+JZ7BQoQRvpOtXi7MZT2pi34IRdDiiAOQiiAq5EI3J/0hzlgymGfgAR kltuPCD75jZKGp2lXaO8PcClvx6o= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Date:From:To:Subject:Message-ID:MIME-Version:Content-Type:Content-Disposition:User-Agent:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=VXKyu1tCZgLKl8osBqLvU0/i5ZSyVhJRCYSFDHdcqedWnImdKNYGY2MIRkMEMy dh+XH9KL4ADLqZq8jDZ/BjI1VgPQJifH0XWWkXmqTwX42xASk1YG3mEsedXEbTK0 ph/OOMobKjp7j5jHbVR/OUSr4x/9jbnCdA+q10pOdRKu4=; Received: (qmail 5412 invoked by alias); 30 Oct 2012 14:51:40 -0000 Received: (qmail 5129 invoked by uid 22791); 30 Oct 2012 14:51:35 -0000 X-SWARE-Spam-Status: No, hits=-4.1 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_W, RCVD_IN_HOSTKARMA_WL, RP_MATCHES_RCVD, TW_TM X-Spam-Check-By: sourceware.org Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 30 Oct 2012 14:51:23 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 3946A5439C5; Tue, 30 Oct 2012 15:51:22 +0100 (CET) Date: Tue, 30 Oct 2012 15:51:22 +0100 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, rguenther@suse.de Subject: Non-dominating loop bounds in tree-ssa-loop-niter 1/4 Message-ID: <20121030145122.GB2803@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Hi, this is first patch of change of tree-ssa-loop-niter to consider bounds that are not in block dominating latch. This patch makes them to be recorded and they are not used. I plan to followup with: 1) patch to add simple shortest path walk at the end of estimate_numbers_of_iterations_loop determining bound of i.e. int a[10]; int b[10]; for (i=0;ilatch, exit->src)) + if (every_iteration + && !dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src)) return false; niter->assumptions = boolean_false_node; @@ -2568,6 +2572,11 @@ record_estimate (struct loop *loop, tree loop->bounds = elt; } + /* If statement is executed on every path to the loop latch, we can directly + infer the upper bound on the # of iterations of the loop. */ + if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt))) + return; + /* Update the number of iteration estimates according to the bound. If at_stmt is an exit then the loop latch is executed at most BOUND times, otherwise it can be executed BOUND + 1 times. We will lower the estimate @@ -2651,7 +2660,6 @@ struct ilb_data { struct loop *loop; gimple stmt; - bool reliable; }; static bool @@ -2660,7 +2668,7 @@ idx_infer_loop_bounds (tree base, tree * struct ilb_data *data = (struct ilb_data *) dta; tree ev, init, step; tree low, high, type, next; - bool sign, upper = data->reliable, at_end = false; + bool sign, upper = true, at_end = false; struct loop *loop = data->loop; if (TREE_CODE (base) != ARRAY_REF) @@ -2737,14 +2745,12 @@ idx_infer_loop_bounds (tree base, tree * STMT is guaranteed to be executed in every iteration of LOOP.*/ static void -infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref, - bool reliable) +infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref) { struct ilb_data data; data.loop = loop; data.stmt = stmt; - data.reliable = reliable; for_each_index (&ref, idx_infer_loop_bounds, &data); } @@ -2753,7 +2759,7 @@ infer_loop_bounds_from_ref (struct loop executed in every iteration of LOOP. */ static void -infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable) +infer_loop_bounds_from_array (struct loop *loop, gimple stmt) { if (is_gimple_assign (stmt)) { @@ -2763,10 +2769,10 @@ infer_loop_bounds_from_array (struct loo /* For each memory access, analyze its access function and record a bound on the loop iteration domain. */ if (REFERENCE_CLASS_P (op0)) - infer_loop_bounds_from_ref (loop, stmt, op0, reliable); + infer_loop_bounds_from_ref (loop, stmt, op0); if (REFERENCE_CLASS_P (op1)) - infer_loop_bounds_from_ref (loop, stmt, op1, reliable); + infer_loop_bounds_from_ref (loop, stmt, op1); } else if (is_gimple_call (stmt)) { @@ -2775,13 +2781,13 @@ infer_loop_bounds_from_array (struct loo lhs = gimple_call_lhs (stmt); if (lhs && REFERENCE_CLASS_P (lhs)) - infer_loop_bounds_from_ref (loop, stmt, lhs, reliable); + infer_loop_bounds_from_ref (loop, stmt, lhs); for (i = 0; i < n; i++) { arg = gimple_call_arg (stmt, i); if (REFERENCE_CLASS_P (arg)) - infer_loop_bounds_from_ref (loop, stmt, arg, reliable); + infer_loop_bounds_from_ref (loop, stmt, arg); } } } @@ -2910,14 +2916,15 @@ infer_loop_bounds_from_undefined (struct /* If BB is not executed in each iteration of the loop, we cannot use the operations in it to infer reliable upper bound on the - # of iterations of the loop. However, we can use it as a guess. */ + # of iterations of the loop. However, we can use it as a guess. + Reliable guesses come only from array bounds. */ reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb); for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) { gimple stmt = gsi_stmt (bsi); - infer_loop_bounds_from_array (loop, stmt, reliable); + infer_loop_bounds_from_array (loop, stmt); if (reliable) { @@ -3078,7 +3085,7 @@ estimate_numbers_of_iterations_loop (str likely_exit = single_likely_exit (loop); FOR_EACH_VEC_ELT (edge, exits, i, ex) { - if (!number_of_iterations_exit (loop, ex, &niter_desc, false)) + if (!number_of_iterations_exit (loop, ex, &niter_desc, false, false)) continue; niter = niter_desc.niter;