This is the mail archive of the
mailing list for the GCC project.
Re: [4.5] Autoinc support in tree-ssa-loop-ivopts.c
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: Bernd Schmidt <bernds_cb1 at t-online dot de>
- Cc: Zdenek Dvorak <rakdver at kam dot mff dot cuni dot cz>, GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Wed, 13 May 2009 14:30:31 -0400
- Subject: Re: [4.5] Autoinc support in tree-ssa-loop-ivopts.c
- References: <4999939F.email@example.com> <20090217163948.GA30309@kam.mff.cuni.cz> <4A0AEC7E.firstname.lastname@example.org>
On Wed, May 13, 2009 at 11:51 AM, Bernd Schmidt <email@example.com> wrote:
> Zdenek Dvorak wrote:
>> thanks for looking into the issue.
>>> ? ? ? ?(iv_ca_recount_cost): Give a bonus to a candidate/use pair where
>>> ? ? ? ?candidate is used exactly once in the loop in a way that allows
>>> ? ? ? ?autoincrement addressing.
>> This is a too costly way to implement this idea. ?iv_ca_recount_cost is
>> called a lot, and the patch adds a quadratic loop (#of candidates * #of
>> uses) to it, that furthermore invokes a rather costly computation.
>> At the very least you should move the computation to the
>> point where USE becomes the single use of CAND. ?Also, it should be
>> possible to do most of the work of autoinc_possible_at in
>> get_computation_cost_at (see the patch proposed for PR 31849 in
>> bugzilla for inspiration), and to avoid the code duplication.
>> Another thing: is this really the right condition to detect? ?I would
>> expect autoinc modes to be useful even in cases where more than one
>> memory reference and possibly also the exit test are based on the
>> autoincremented induction variable.
> Here's a new patch which has been extensively changed.
> One possible condition to test for would be whether the uses closest to the
> position of the biv increment (either before or after) allow autoincrement.
> ?That seems to me rather expensive since we'd have to walk the basic blocks
> a few times to determine an order for the uses,
> so I've chosen something
> slightly weaker: either all uses before the increment, or all uses after the
> increment must allow autoincrement. This condition gives us a strict
> superset of opportunites compared to the one used by the previous patch.
Just FYI, you only have to walk them once.
Do what PRE does, and give all the statements UIDs in DFS order.
Then you can compare uses by their block's DFS number and then by the
statement DFS number, and determine which is closer to the DFS number
for the increment.
This only takes a single walk.