On 2021/9/10 21:54, Xionghu Luo via Gcc-patches wrote:
On 2021/9/9 18:55, Richard Biener wrote:
diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
index 5d6845478e7..4b187c2cdaf 100644
--- a/gcc/tree-ssa-loop-im.c
+++ b/gcc/tree-ssa-loop-im.c
@@ -3074,15 +3074,13 @@ fill_always_executed_in_1 (class loop *loop,
sbitmap contains_call)
break;
if (bb->loop_father->header == bb)
- {
- if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
- break;
-
- /* In a loop that is always entered we may proceed anyway.
- But record that we entered it and stop once we leave it
- since it might not be finite. */
- inn_loop = bb->loop_father;
- }
+ /* Record that we enter into a subloop since it might not
+ be finite. */
+ /* ??? Entering into a not always executed subloop makes
+ fill_always_executed_in quadratic in loop depth since
+ we walk those loops N times. This is not a problem
+ in practice though, see PR102253 for a worst-case
testcase. */
+ inn_loop = bb->loop_father;
Yes your two patches extracted the get_loop_body_in_dom_order out and
removed
the inn_loop break logic when it doesn't dominate outer loop. Confirmed
the replacement
could improve for saving ~10% build time due to not full DOM walker and
marked the previously
ignored ALWAYS_EXECUTED bbs.
But if we don't break for inner loop again, why still keep the
*inn_loop* variable?
It seems unnecessary and confusing, could we just remove it and restore
the original
infinte loop check in bb->succs for better understanding?
What's more, the refine of this fix is incorrect for PR78185.
commit 483e400870601f650c80f867ec781cd5f83507d6
Author: Richard Biener <rguent...@suse.de>
Date: Thu Sep 2 10:47:35 2021 +0200
Refine fix for PR78185, improve LIM for code after inner loops
This refines the fix for PR78185 after understanding that the code
regarding to the comment 'In a loop that is always entered we may
proceed anyway. But record that we entered it and stop once we leave
it.' was supposed to protect us from leaving possibly infinite inner
loops. The simpler fix of moving the misplaced stopping code
can then be refined to continue processing when the exited inner
loop is finite, improving invariant motion for cases like in the
added testcase.
2021-09-02 Richard Biener <rguent...@suse.de>
* tree-ssa-loop-im.c (fill_always_executed_in_1): Refine
fix for PR78185 and continue processing when leaving
finite inner loops.
* gcc.dg/tree-ssa/ssa-lim-16.c: New testcase.
3<-------
| |
6<--- |
| \ | |
| \ | |
4 8 |
|--- |
| | |
5 7------
|
1
loop 2 is an infinite loop, it is only ALWAYS_EXECUTED for loop 2,
but r12-3313-g483e40087 sets it ALWAYS_EXECUTED for loop 1.
We need to restore it like this:
https://gcc.gnu.org/pipermail/gcc-patches/2021-September/579195.html
diff of pr78185.c.138t.lim2:
;;
;; Loop 1
;; header 3, latch 7
;; depth 1, outer 0
;; nodes: 3 7 4 6 8
;;
;; Loop 2
;; header 6, latch 8
;; depth 2, outer 1
;; nodes: 6 8
;; 2 succs { 3 }
;; 3 succs { 6 }
;; 6 succs { 4 8 }
;; 8 succs { 6 }
;; 4 succs { 7 5 }
;; 7 succs { 3 }
;; 5 succs { 1 }
Memory reference 1: var1
-BB 6 is always executed in loop 1
BB 3 is always executed in loop 1
+BB 6 is always executed in loop 2
Basic block 3 (loop 1 -- depth 1):
Basic block 6 (loop 2 -- depth 2):
diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
index d1e2104233b..82a0509e0c4 100644
--- a/gcc/tree-ssa-loop-im.c
+++ b/gcc/tree-ssa-loop-im.c
@@ -3200,7 +3200,6 @@ fill_always_executed_in_1 (class loop *loop,
sbitmap contains_call)
{
basic_block bb = NULL, last = NULL;
edge e;
- class loop *inn_loop = loop;
if (ALWAYS_EXECUTED_IN (loop->header) == NULL)
{
@@ -3213,17 +3212,6 @@ fill_always_executed_in_1 (class loop *loop,
sbitmap contains_call)
edge_iterator ei;
bb = worklist.pop ();
- if (!flow_bb_inside_loop_p (inn_loop, bb))
- {
- /* When we are leaving a possibly infinite inner loop
- we have to stop processing. */
- if (!finite_loop_p (inn_loop))
- break;
- /* If the loop was finite we can continue with processing
- the loop we exited to. */
- inn_loop = bb->loop_father;
- }
-
if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
last = bb;
@@ -3232,8 +3220,15 @@ fill_always_executed_in_1 (class loop *loop,
sbitmap contains_call)
/* If LOOP exits from this BB stop processing. */
FOR_EACH_EDGE (e, ei, bb->succs)
+ {
if (!flow_bb_inside_loop_p (loop, e->dest))
break;
+ /* Or we enter a possibly non-finite loop. */
+ if (flow_loop_nested_p (bb->loop_father,
+ e->dest->loop_father)
+ && ! finite_loop_p (e->dest->loop_father))
+ break;
+ }
if (e)
break;
@@ -3242,15 +3237,6 @@ fill_always_executed_in_1 (class loop *loop,
sbitmap contains_call)
if (bb->flags & BB_IRREDUCIBLE_LOOP)
break;
- if (bb->loop_father->header == bb)
- /* Record that we enter into a subloop since it might not
- be finite. */
- /* ??? Entering into a not always executed subloop makes
- fill_always_executed_in quadratic in loop depth since
- we walk those loops N times. This is not a problem
- in practice though, see PR102253 for a worst-case
testcase. */
- inn_loop = bb->loop_father;
-
/* Walk the body of LOOP sorted by dominance relation.
Additionally,
if a basic block S dominates the latch, then only blocks
dominated
by S are after it.
/* Walk the body of LOOP sorted by dominance relation.
Additionally,
if a basic block S dominates the latch, then only blocks
dominated
--
Thanks,
Xionghu
