From: Tom de Vries <vries@codesourcery.com>
To: Zdenek Dvorak <rakdver@kam.mff.cuni.cz>
Cc: gcc-patches@gcc.gnu.org
Subject: [PATCH PR45098, 7/10] Nowrap limits iterations
Date: Wed, 18 May 2011 17:52:00 -0000 [thread overview]
Message-ID: <4DD3FD79.2020804@codesourcery.com> (raw)
In-Reply-To: <4DD221CF.4040002@codesourcery.com>
[-- Attachment #1: Type: text/plain, Size: 1113 bytes --]
On 05/17/2011 09:20 AM, Tom de Vries wrote:
> On 05/17/2011 09:10 AM, Tom de Vries wrote:
>> Hi Zdenek,
>>
>> I have a patch set for for PR45098.
>>
>> 01_object-size-target.patch
>> 02_pr45098-rtx-cost-set.patch
>> 03_pr45098-computation-cost.patch
>> 04_pr45098-iv-init-cost.patch
>> 05_pr45098-bound-cost.patch
>> 06_pr45098-bound-cost.test.patch
>> 07_pr45098-nowrap-limits-iterations.patch
>> 08_pr45098-nowrap-limits-iterations.test.patch
>> 09_pr45098-shift-add-cost.patch
>> 10_pr45098-shift-add-cost.test.patch
>>
>> I will sent out the patches individually.
>>
>
> OK for trunk?
>
> Thanks,
> - Tom
Resubmitting with comment.
This patch attemps to estimate the number of iterations of the loop based on
nonwrapping arithmetic in the loop body.
2011-05-05 Tom de Vries <tom@codesourcery.com>
PR target/45098
* tree-ssa-loop-ivopts.c (struct ivopts_data): Add fields
max_iterations_p and max_iterations.
(is_nonwrap_use, max_loop_iterations, set_max_iterations): New function.
(may_eliminate_iv): Use max_iterations_p and max_iterations.
(tree_ssa_iv_optimize_loop): Use set_max_iterations.
[-- Attachment #2: 07_pr45098-nowrap-limits-iterations.patch --]
[-- Type: text/x-patch, Size: 4472 bytes --]
Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c (revision 173355)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -291,6 +291,12 @@ struct ivopts_data
/* Whether the loop body includes any function calls. */
bool body_includes_call;
+
+ /* Whether max_iterations is valid. */
+ bool max_iterations_p;
+
+ /* Maximum number of iterations of current_loop. */
+ double_int max_iterations;
};
/* An assignment of iv candidates to uses. */
@@ -4319,6 +4325,108 @@ iv_elimination_compare (struct ivopts_da
return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
}
+/* Determine if USE contains non-wrapping arithmetic. */
+
+static bool
+is_nonwrap_use (struct ivopts_data *data, struct iv_use *use)
+{
+ gimple stmt = use->stmt;
+ tree var, ptr, ptr_type;
+
+ if (!is_gimple_assign (stmt))
+ return false;
+
+ switch (gimple_assign_rhs_code (stmt))
+ {
+ case POINTER_PLUS_EXPR:
+ ptr = gimple_assign_rhs1 (stmt);
+ ptr_type = TREE_TYPE (ptr);
+ var = gimple_assign_rhs2 (stmt);
+ if (!expr_invariant_in_loop_p (data->current_loop, ptr))
+ return false;
+ break;
+ case ARRAY_REF:
+ ptr = TREE_OPERAND ((gimple_assign_rhs1 (stmt)), 0);
+ ptr_type = build_pointer_type (TREE_TYPE (gimple_assign_rhs1 (stmt)));
+ var = TREE_OPERAND ((gimple_assign_rhs1 (stmt)), 1);
+ break;
+ default:
+ return false;
+ }
+
+ if (!nowrap_type_p (ptr_type))
+ return false;
+
+ if (TYPE_PRECISION (ptr_type) != TYPE_PRECISION (TREE_TYPE (var)))
+ return false;
+
+ return true;
+}
+
+/* Attempt to infer maximum number of loop iterations of DATA->current_loop
+ from uses in loop containing non-wrapping arithmetic. If successful,
+ return true, and return maximum iterations in MAX_NITER. */
+
+static bool
+max_loop_iterations (struct ivopts_data *data, double_int *max_niter)
+{
+ struct iv_use *use;
+ struct iv *iv;
+ bool found = false;
+ double_int period;
+ gimple stmt;
+ unsigned i;
+
+ for (i = 0; i < n_iv_uses (data); i++)
+ {
+ use = iv_use (data, i);
+
+ stmt = use->stmt;
+ if (!just_once_each_iteration_p (data->current_loop, gimple_bb (stmt)))
+ continue;
+
+ if (!is_nonwrap_use (data, use))
+ continue;
+
+ iv = use->iv;
+ if (iv->step == NULL_TREE || TREE_CODE (iv->step) != INTEGER_CST)
+ continue;
+ period = tree_to_double_int (iv_period (iv));
+
+ if (found)
+ *max_niter = double_int_umin (*max_niter, period);
+ else
+ {
+ found = true;
+ *max_niter = period;
+ }
+ }
+
+ return found;
+}
+
+/* Initializes DATA->max_iterations and DATA->max_iterations_p. */
+
+static void
+set_max_iterations (struct ivopts_data *data)
+{
+ double_int max_niter, max_niter2;
+ bool estimate1, estimate2;
+
+ data->max_iterations_p = false;
+ estimate1 = estimated_loop_iterations (data->current_loop, true, &max_niter);
+ estimate2 = max_loop_iterations (data, &max_niter2);
+ if (!(estimate1 || estimate2))
+ return;
+ if (estimate1 && estimate2)
+ data->max_iterations = double_int_umin (max_niter, max_niter2);
+ else if (estimate1)
+ data->max_iterations = max_niter;
+ else
+ data->max_iterations = max_niter2;
+ data->max_iterations_p = true;
+}
+
/* Check whether it is possible to express the condition in USE by comparison
of candidate CAND. If so, store the value compared with to BOUND. */
@@ -4391,10 +4499,10 @@ may_eliminate_iv (struct ivopts_data *da
/* See if we can take advantage of infered loop bound information. */
if (loop_only_exit_p (loop, exit))
{
- if (!estimated_loop_iterations (loop, true, &max_niter))
+ if (!data->max_iterations_p)
return false;
/* The loop bound is already adjusted by adding 1. */
- if (double_int_ucmp (max_niter, period_value) > 0)
+ if (double_int_ucmp (data->max_iterations, period_value) > 0)
return false;
}
else
@@ -6390,6 +6498,8 @@ tree_ssa_iv_optimize_loop (struct ivopts
/* Finds candidates for the induction variables (item 2). */
find_iv_candidates (data);
+ set_max_iterations (data);
+
/* Calculates the costs (item 3, part 1). */
determine_iv_costs (data);
determine_use_iv_costs (data);
next prev parent reply other threads:[~2011-05-18 17:11 UTC|newest]
Thread overview: 46+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-05-17 7:23 [PATCH, PR45098] Tom de Vries
2011-05-17 7:25 ` [PATCH, PR45098, 1/10] Tom de Vries
2011-05-19 11:17 ` [PATCH PR45098, 1/10] Proc object-size fix Tom de Vries
2011-05-17 8:12 ` [PATCH, PR45098, 2/10] Tom de Vries
2011-05-18 9:39 ` Zdenek Dvorak
2011-05-17 8:30 ` [PATCH, PR45098, 3/10] Tom de Vries
2011-05-18 10:10 ` Zdenek Dvorak
2011-05-18 13:00 ` Tom de Vries
[not found] ` <20110518152457.GA13360@kam.mff.cuni.cz>
2011-05-18 19:30 ` Tom de Vries
2011-05-17 8:32 ` [PATCH, PR45098, 4/10] Tom de Vries
2011-05-18 17:46 ` [PATCH PR45098, 4/10] Iv init cost Tom de Vries
2011-05-18 22:59 ` Zdenek Dvorak
2011-05-25 14:20 ` Richard Sandiford
2011-05-26 12:24 ` Tom de Vries
2011-05-31 15:22 ` Richard Sandiford
2011-05-17 8:37 ` [PATCH, PR45098, 5/10] Tom de Vries
2011-05-18 17:48 ` [PATCH PR45098, 5/10] Bound cost Tom de Vries
2011-05-19 4:45 ` Zdenek Dvorak
2011-05-17 8:42 ` [PATCH, PR45098, 6/10] Tom de Vries
2011-05-18 17:48 ` [PATCH PR45098, 6/10] Bound cost - test cases Tom de Vries
2011-05-17 8:58 ` [PATCH, PR45098, 7/10] Tom de Vries
2011-05-18 17:52 ` Tom de Vries [this message]
2011-05-19 4:45 ` [PATCH PR45098, 7/10] Nowrap limits iterations Zdenek Dvorak
2011-05-20 12:22 ` Tom de Vries
2011-05-21 18:54 ` Zdenek Dvorak
2011-05-21 22:53 ` Tom de Vries
2011-05-28 17:58 ` Tom de Vries
2011-05-30 15:12 ` Zdenek Dvorak
2011-05-31 9:07 ` Tom de Vries
2011-05-31 9:11 ` Zdenek Dvorak
2011-06-11 10:13 ` Tom de Vries
2011-06-12 1:17 ` Zdenek Dvorak
2011-05-23 14:50 ` H.J. Lu
2011-05-17 9:03 ` [PATCH, PR45098, 8/10] Tom de Vries
2011-05-18 18:23 ` [PATCH PR45098, 8/10] Nowrap limits iterations - test cases Tom de Vries
2011-05-18 18:27 ` [PATCH PR45098, 9/10] Cheap shift-add Tom de Vries
2011-05-19 5:33 ` Zdenek Dvorak
2011-05-20 11:32 ` Tom de Vries
2011-05-20 20:09 ` Zdenek Dvorak
2011-05-21 15:05 ` Eric Botcazou
2011-05-22 19:33 ` Tom de Vries
2011-05-22 20:22 ` Richard Guenther
2011-05-22 21:11 ` Eric Botcazou
2011-05-17 10:03 ` [PATCH, PR45098, 9/10] Tom de Vries
2011-05-17 10:30 ` [PATCH, PR45098, 10/10] Tom de Vries
2011-05-18 18:30 ` [PATCH PR45098, 10/10] Cheap shift-add - test case Tom de Vries
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4DD3FD79.2020804@codesourcery.com \
--to=vries@codesourcery.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=rakdver@kam.mff.cuni.cz \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).