Re: A problem with the loop structure

["Vladimir Yanovsky" <volodyan at gmail dot com>]

Hi,

Thanks a lot for your help and suggestions! Below I attach some more
observations. I would be grateful for any more ideas on what can be
wrong here.

Thanks a lot,
Vladimir
---------------------------------------------------------------------------

The problem happens because the num_nodes of the outer loop of the
versioned loop is more than what is reported by the DFS traversal.

i)
The loops are:
1) Before versioning:
;; Loop 7:  //Outer loop
;;  header 256, latch 24
;;  depth 4, level 2, outer 6
;;  nodes: 256 24 23 21
;;
;; Loop 8:  //To be versioned
;;  header 24, latch 24
;;  depth 5, level 1, outer 7
;;  nodes: 24


(gdb) p loop->num_nodes
$221 = 2
(gdb) p loop->num
$222 = 8


2) After versioning (loop 7 printed suppressing the assert(dfs_result
== num_nodes):
;; Loop 7:
;;  header 256, latch 266
;;  depth 4, level 2, outer 6
;;  nodes: 256 266 24 265 259 263 262 23 21
;;
;; Loop 8:
;;  header 24, latch 259
;;  depth 5, level 1, outer 7
;;  nodes: 24 259
;; Loop 54:
;;  header 260, latch 261
;;  depth 5, level 1, outer 7
;;  nodes: 260 261

ii)
In loop_version there are two calls to loop_split_edge_with
1.  loop_split_edge_with (loop_preheader_edge (loop), NULL);
2.  loop_split_edge_with (loop_preheader_edge (nloop), NULL);
nloop is the versioned loop, loop is the original.

loop_split_edge_with has the following:
 new_bb = split_edge (e);
 add_bb_to_loop (new_bb, loop_c);

1) When we get to the fist call, nloop->outer->num_nodes = 8 while dfs
returns 6.
After the first call
nloop->outer->num_nodes = 9 and dfs returns 7, seems that
add_bb_to_loop performed OK in this case.

Here is the dump of new_bb in the first call:

loop_split_edge_with (edge e, rtx insns) ->  add_bb_to_loop (new_bb, loop_c);
Correct result:
(gdb) p debug_bb_n(new_bb->index)
;; basic block 263, loop depth 0, count 0
;; prev block 262, next block 24
;; pred:       262
;; succ:       24 [100.0%]  (fallthru)
;; Registers live at start:  1 [$sp] 127 [$127] 128 [$vfp] 129 [$vap]
587 607 626 628 629 635 672 733 735 792 846 897 1432 1437 1438 1440
1450 1453 1456 1560 1561 1676
(code_label 5826 5824 5825 263 418 "" [1 uses])
(note 5825 5826 710 263 [bb 263] NOTE_INSN_BASIC_BLOCK)
;; Registers live at end:  1 [$sp] 127 [$127] 128 [$vfp] 129 [$vap]
587 607 626 628 629 635 672 733 735 792 846 897 1432 1437 1438 1440
1450 1453 1456 1560 1561 1676

2. Now, the second call to
loop_split_edge_with (edge e, rtx insns) ->  add_bb_to_loop (new_bb, loop_c)
results in nloop->outer->num_nodes = 10 while dfs still returns 7.
Printing new_bb we see it has both pred and succ fallthru.

(gdb) p debug_bb_n(new_bb->index)
;; basic block 264, loop depth 0, count 0
;; prev block 262, next block 263
;; pred:       262 [100.0%]  (fallthru)
;; succ:       260 [100.0%]  (fallthru)
;; Registers live at start:  1 [$sp] 127 [$127] 128 [$vfp] 129 [$vap]
587 607 626 628 629 635 672 733 735 792 846 897 1432 1437 1438 1440
1450 1453 1456 1560 1561 1676
(note 5827 5824 5826 264 [bb 264] NOTE_INSN_BASIC_BLOCK)
;; Registers live at end:  1 [$sp] 127 [$127] 128 [$vfp] 129 [$vap]
587 607 626 628 629 635 672 733 735 792 846 897 1432 1437 1438 1440
1450 1453 1456 1560 1561 1676
$215 = (struct basic_block_def *) 0x2aaaaebc0500


On 4/29/07, Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz> wrote:
> Hello,
>
> > (based on gcc 4.1.1).
>
> now that is a problem; things have changed a lot since then, so I am not
> sure how much I will be able to help.
>
> > 1. The problem was unveiled by compiling a testcase with dump turned
> > on. The compilation failed while calling function get_loop_body from
> > flow_loop_dump on the following assert :
> >
> >  else if (loop->latch != loop->header)
> >    {
> >      tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
> >                               tovisit + 1, loop->num_nodes - 1,
> >                               loop->header) + 1;
> >
> >
> >  gcc_assert (tv == loop->num_nodes);
> >
> > The compilation exits successfully if compiled without enabling the dump.
>
> this means that there is some problem in some loop transformation,
> forgetting to record membership of some blocks to their loops or something
> like that.
>
> > 2. SMS pass contained a single call to loop_version on the loop to be
> > SMSed. This happened before any SMS related stuff was done. Trying to
> > call verify_loop_structure(loops) just after the call to loop_version
> > failed on the same assert in get_loop_body as in (1). The loop on
> > which we fail is neither the versioned loop nor the new loop.
>
> Probably it is their superloop?
>
> > Below
> > there are dumps to verify_loop_structure called from different places
> > in loop_version:
>
> These dumps are not very useful, loop structures do not have to be
> consistent in the middle of the transformation.
>
> > 3.  At the very beginning of the SMS pass we build the loop structure
> > using build_loops_structure defined in modulo-sched.c. Just after the
> >
> > call I tried to print in gdb the loop on which we failed in
> > get_loop_body. This failed as well
> >
> > (gdb)  p print_loop(dumpfile, 0xbabe20, 0)
>
> Do not use print_loop, that only works on gimple.  Use flow_loops_dump
> to find which blocks belong to which loops, and possibly debug_bb_n
> if you need to see the contents of the blocks.
>
> Zdenek