This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] for ivopts problem in PR 19038
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 19 Jan 2005 23:01:22 +0100
- Subject: [patch] for ivopts problem in PR 19038
Hello,
one of the problems in this PR is that ivopts sometimes put iv
increments to the loop latch block even in the case it was empty
previously, thus adding one basic block to the loop body.
The case where it might occur look like this (i unused outside of
the loop):
for (i = 0; i++ != n; )
something;
which translates to
do
{
i_1 = phi (0, i_2);
something;
i_2 = i_1 + 1;
} while (i_1 != n)
Ivopts decide to change it to
while (1)
{
i_1 = phi (0, i_2);
something;
if (i_1 == n)
break;
i_2 = i_1 + 1;
}
It is not obvious which of them is better; the second form needs one
less register, but one more jump per iteration. Also loops with two
blocks are not handled as well as single-block loops by some
optimizations.
The patch below makes ivopts avoid creating ivs whose increment would be
in an empty latch block. One pleasant side effect is that since ivopts
have less candidates to consider with it, the compile time is improved
a bit (7m18s on compilation of preprocessed gcc sources without the
patch, 7m14s with it).
The results of spec2000 on ppc64 are below (base without patch, peak
with, both just with -O2).
The patch was bootstrapped & regtested on ppc.
Zdenek
164.gzip 1400 192 731* 1400 190 736*
175.vpr 1400 304 461* 1400 306 458*
176.gcc X X
181.mcf 1800 543 331* 1800 547 329*
186.crafty 1000 86.1 1161* 1000 85.7 1167*
197.parser 1800 353 510* 1800 343 525*
252.eon 1300 120 1082* 1300 120 1083*
253.perlbmk 1800 245 735* 1800 246 733*
254.gap 1100 157 700* 1100 155 711*
255.vortex 1900 224 849* 1900 224 846*
256.bzip2 1500 252 595* 1500 252 594*
300.twolf X X
Est. SPECint_base2000 671
Est. SPECint2000 674
168.wupwise 1600 199 806* 1600 196 818*
171.swim 3100 1201 258* 3100 1217 255*
172.mgrid 1800 349 516* 1800 351 513*
173.applu 2100 349 602* 2100 351 598*
177.mesa 1400 141 993* 1400 143 978*
178.galgel 2900 377 769* 2900 373 778*
179.art 2600 399 652* 2600 401 648*
183.equake 1300 135 966* 1300 135 964*
187.facerec 1900 236 806* 1900 245 775*
188.ammp 2200 620 355* 2200 625 352*
189.lucas 2000 225 887* 2000 228 877*
191.fma3d 2100 263 800* 2100 260 807*
200.sixtrack 1100 249 442* 1100 250 440*
301.apsi 2600 496 524* 2600 501 518*
Est. SPECfp_base2000 627
Est. SPECfp2000 623
PR tree-optimization/19038
* tree-ssa-loop-ivopts.c (allow_ip_end_pos_p): New function.
(add_candidate): Add ivs with increment in latch only if
allow_ip_end_pos_p is true.
(determine_iv_cost): Use empty_block_p.
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.41
diff -c -3 -p -r2.41 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 18 Jan 2005 11:36:27 -0000 2.41
--- tree-ssa-loop-ivopts.c 19 Jan 2005 10:25:51 -0000
*************** add_candidate_1 (struct ivopts_data *dat
*** 1779,1784 ****
--- 1779,1805 ----
return cand;
}
+ /* Returns true if incrementing the induction variable at the end of the LOOP
+ is allowed.
+
+ The purpose is to avoid splitting latch edge with a biv increment, thus
+ creating a jump, possibly confusing other optimization passes and leaving
+ less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS
+ is not available (so we do not have a better alternative), or if the latch
+ edge is already nonempty. */
+
+ static bool
+ allow_ip_end_pos_p (struct loop *loop)
+ {
+ if (!ip_normal_pos (loop))
+ return true;
+
+ if (!empty_block_p (ip_end_pos (loop)))
+ return true;
+
+ return false;
+ }
+
/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
position to POS. If USE is not NULL, the candidate is set as related to
it. The candidate computation is scheduled on all available positions. */
*************** add_candidate (struct ivopts_data *data,
*** 1789,1795 ****
{
if (ip_normal_pos (data->current_loop))
add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
! if (ip_end_pos (data->current_loop))
add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
}
--- 1810,1817 ----
{
if (ip_normal_pos (data->current_loop))
add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE);
! if (ip_end_pos (data->current_loop)
! && allow_ip_end_pos_p (data->current_loop))
add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE);
}
*************** static void
*** 3518,3525 ****
determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
{
unsigned cost_base, cost_step;
! tree base, last;
! basic_block bb;
if (!cand->iv)
{
--- 3540,3546 ----
determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
{
unsigned cost_base, cost_step;
! tree base;
if (!cand->iv)
{
*************** determine_iv_cost (struct ivopts_data *d
*** 3543,3557 ****
/* Prefer not to insert statements into latch unless there are some
already (so that we do not create unnecessary jumps). */
! if (cand->pos == IP_END)
! {
! bb = ip_end_pos (data->current_loop);
! last = last_stmt (bb);
!
! if (!last
! || TREE_CODE (last) == LABEL_EXPR)
! cand->cost++;
! }
}
/* Determines costs of computation of the candidates. */
--- 3564,3572 ----
/* Prefer not to insert statements into latch unless there are some
already (so that we do not create unnecessary jumps). */
! if (cand->pos == IP_END
! && empty_block_p (ip_end_pos (data->current_loop)))
! cand->cost++;
}
/* Determines costs of computation of the candidates. */