From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20464 invoked by alias); 30 Mar 2016 10:00:33 -0000 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 Received: (qmail 20436 invoked by uid 89); 30 Mar 2016 10:00:32 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.7 required=5.0 tests=AWL,BAYES_00,KAM_ASCII_DIVIDERS,KAM_LAZY_DOMAIN_SECURITY,RP_MATCHES_RCVD autolearn=no version=3.3.2 spammy=sk:tree_in, realistic, pay X-HELO: nikam.ms.mff.cuni.cz Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Wed, 30 Mar 2016 10:00:22 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id C788B545C83; Wed, 30 Mar 2016 12:00:18 +0200 (CEST) Date: Wed, 30 Mar 2016 11:02:00 -0000 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, rguenther@suse.de Subject: Do not give realistic estimates for loop with array accesses Message-ID: <20160330100018.GA54780@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) X-SW-Source: 2016-03/txt/msg01579.txt.bz2 Hi, while looking into sudoku solving benchark, I noticed that we incorrectly estimate loop to iterate 10 times just because the array it traverses is of dimension 10. This of course is just upper bound and not realistic bound. Realistically those loops iterates once most of time. It turns out this bug was introduced by me in https://gcc.gnu.org/ml/gcc-patches/2013-01/msg00444.html While I do not recall doing that patch, it seems like a thinko about reliable (name of the variable) and realistic (name of the parameter it is passed to). Fixing this caused one testsuite fallout in predictive commoning testcase because loop unswitching previously disabled itself having an estimated number of iterations 1 (I am not sure if that is not supposed to be 0, with 1 iteration unswithcing may pay back, little bit, I suppose it wants to test number of stmt executions of the condtional to be at least 2 which depends on whether the conditional is before or after the loop exits). This made me notice that some loop passes that want to give up on low trip count uses combination of estimated number of iterations and max number of iterations while other don't which is fixed here. The code combining both realistic and max counts is same as i.e. in unroller and other passes already. I also wonder if predictive comming is a win for loops with very low trip count, but that is for separate patch, too, anyway. Bootstrapped/regtested x86_64-linux, OK? Honza * tree-ssa-loop-niter.c (idx_infer_loop_bounds): We can't get realistic estimates here. * tree-ssa-loop-unswitch.c (tree_unswitch_single_loop): Use also max_loop_iterations_int. * tree-ssa-loop-ivopts.c (avg_loop_niter): Likewise. * tree-vect-loop.c (vect_analyze_loop_2): Likewise. Index: tree-ssa-loop-niter.c =================================================================== --- tree-ssa-loop-niter.c (revision 234516) +++ tree-ssa-loop-niter.c (working copy) @@ -3115,7 +3115,6 @@ idx_infer_loop_bounds (tree base, tree * tree low, high, type, next; bool sign, upper = true, at_end = false; struct loop *loop = data->loop; - bool reliable = true; if (TREE_CODE (base) != ARRAY_REF) return true; @@ -3187,14 +3186,14 @@ idx_infer_loop_bounds (tree base, tree * && tree_int_cst_compare (next, high) <= 0) return true; - /* If access is not executed on every iteration, we must ensure that overlow may - not make the access valid later. */ + /* If access is not executed on every iteration, we must ensure that overlow + may not make the access valid later. */ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt)) && scev_probably_wraps_p (initial_condition_in_loop_num (ev, loop->num), step, data->stmt, loop, true)) - reliable = false; + upper = false; - record_nonwrapping_iv (loop, init, step, data->stmt, low, high, reliable, upper); + record_nonwrapping_iv (loop, init, step, data->stmt, low, high, false, upper); return true; } Index: tree-ssa-loop-unswitch.c =================================================================== --- tree-ssa-loop-unswitch.c (revision 234516) +++ tree-ssa-loop-unswitch.c (working copy) @@ -223,6 +223,8 @@ tree_unswitch_single_loop (struct loop * /* If the loop is not expected to iterate, there is no need for unswitching. */ iterations = estimated_loop_iterations_int (loop); + if (iterations < 0) + iterations = max_loop_iterations_int (loop); if (iterations >= 0 && iterations <= 1) { if (dump_file && (dump_flags & TDF_DETAILS)) Index: tree-ssa-loop-ivopts.c =================================================================== --- tree-ssa-loop-ivopts.c (revision 234516) +++ tree-ssa-loop-ivopts.c (working copy) @@ -121,7 +121,11 @@ avg_loop_niter (struct loop *loop) { HOST_WIDE_INT niter = estimated_stmt_executions_int (loop); if (niter == -1) - return AVG_LOOP_NITER (loop); + { + niter = max_stmt_executions_int (loop); + if (niter == -1 || niter > AVG_LOOP_NITER (loop)) + return AVG_LOOP_NITER (loop); + } return niter; } Index: tree-vect-loop.c =================================================================== --- tree-vect-loop.c (revision 234516) +++ tree-vect-loop.c (working copy) @@ -2063,6 +2063,9 @@ start_over: estimated_niter = estimated_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo)); + if (estimated_niter != -1) + estimated_niter + = max_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo)); if (estimated_niter != -1 && ((unsigned HOST_WIDE_INT) estimated_niter <= MAX (th, (unsigned)min_profitable_estimate)))