[Bug rtl-optimization/33224] failing rtl iv analysis (maybe due to df)
--- Comment #1 from dorit at gcc dot gnu dot org 2007-08-29 09:04 --- > In the testcase below, after the inner-loop gets completely unrolled, the > enclosing i-loop does not get unrolled because of failure to analyze the loop > iv, possibly due to a bug in df: ... > Compiler options used: > /Develop/mainline-dn1/bin/gcc -O3 -maltivec -funroll-loops > vect-outer-fir2-kernel.c -S --param max-completely-peeled-insns=5000 --param > max-completely-peel-times=40 -fdump-tree-all -da -ftree-vectorize > (without -ftree-vectorize the i-loop does get unrolled). (it could be ofcourse a result of something the vectorizer does. like, maybe the vectorizer is not updating the dominance information correctly or something. but I'd think most such information would be recomputed and verified between vectorization and rtl unrolling? anyhow, verify_dominance seem to pass). -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33224
[Bug rtl-optimization/33224] failing rtl iv analysis (maybe due to df)
-- dorit at gcc dot gnu dot org changed: What|Removed |Added AssignedTo|unassigned at gcc dot gnu |dorit at gcc dot gnu dot org |dot org | Status|UNCONFIRMED |ASSIGNED Ever Confirmed|0 |1 Last reconfirmed|-00-00 00:00:00 |2007-08-29 09:13:05 date|| http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33224
[Bug rtl-optimization/33224] failing rtl iv analysis (maybe due to df)
--- Comment #2 from spark at gcc dot gnu dot org 2007-08-29 15:23 --- I suspect this might be due to not updating the rd information after unrolling. Can you check if analyze_insns_in_loop() (which calls df_analyze()) is being called just before the problematic unrolling ? -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33224
[Bug rtl-optimization/33224] failing rtl iv analysis (maybe due to df)
--- Comment #3 from dorit at gcc dot gnu dot org 2007-08-30 08:12 --- (In reply to comment #2) > I suspect this might be due to not updating the rd information after > unrolling. > Can you check if > analyze_insns_in_loop() (which calls df_analyze()) is being called just before > the problematic unrolling ? it looks like it's called just before the unroller actually transforms somthing, but not before the (failing) analysis. But when I add a call to it in decide_peel_completely the analysis still fails. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33224
[Bug rtl-optimization/33224] failing rtl iv analysis (maybe due to df)
--- Comment #4 from zadeck at naturalbridge dot com 2007-08-30 14:43 --- Subject: Re: failing rtl iv analysis (maybe due to df) dorit at gcc dot gnu dot org wrote: > --- Comment #3 from dorit at gcc dot gnu dot org 2007-08-30 08:12 --- > (In reply to comment #2) > >> I suspect this might be due to not updating the rd information after >> unrolling. >> Can you check if >> analyze_insns_in_loop() (which calls df_analyze()) is being called just >> before >> the problematic unrolling ? >> > > it looks like it's called just before the unroller actually transforms > somthing, but not before the (failing) analysis. But when I add a call to it > in > decide_peel_completely the analysis still fails. > > > dorit, i am having trouble exactly reproducing this example because you did not give the svn revision and so all of the numbers are a little bit different. However, I am going to submit a patch which improves the dump information a lot for these passes and we should talk about it after we can get on the same page. However, from looking at your posting, there are some issues that you may want to look at before we talk: The reaching defs problem makes a scan for all of the defs in the blocks in the region. Once all of the defs are found, they are sorted where the primary key is the regno. The id's (DF_REF_ID) are then assigned based on this sorting. The reaching defs problem actually depends on all of the defs for a regno to be contigious. The DF_REF_IDs are not stable between calls to df_set_blocks and any def outside of the region has an undefined DF_REF_ID. In your posting you have: > Below is the output of df_ref_debug for adef in each iteration of the loop in > latch_dominating_def: > d40 reg 187 bb 3 insn 255 flag 0x0 type 0x0 loc 0xf7da4608(0xf7d9a4e0) chain > { } > d93 reg 187 bb 2 insn 40 flag 0x0 type 0x0 loc 0xf7d89cc8(0xf7d9a4e0) chain { > } The number after the first "d" is the DF_REF_ID. Note that they are not contiguous. Given the sorting that occurred, they must be contiguous. I assume from this that someone is holding on to old id's. This is not correct. If you are going to play the game with df_set_blocks, you are allowed to hold onto a def, but not the DF_REF_ID, you cannot look at the DF_REF_ID for a def that is not in the blocks set by df_set_blocks. Kenny Index: df-core.c === --- df-core.c (revision 127917) +++ df-core.c (working copy) @@ -1761,6 +1761,7 @@ df_print_regset (FILE *file, bitmap r) /* Dump dataflow info. */ + void df_dump (FILE *file) { @@ -1778,6 +1779,33 @@ df_dump (FILE *file) } +/* Dump dataflow info for df->blocks_to_analyze. */ + +void +df_dump_region (FILE *file) +{ + if (df->blocks_to_analyze) +{ + bitmap_iterator bi; + unsigned int bb_index; + + fprintf (file, "\n\nstarting region dump\n"); + df_dump_start (file); + + EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi) + { + basic_block bb = BASIC_BLOCK (bb_index); + + df_print_bb_index (bb, file); + df_dump_top (bb, file); + df_dump_bottom (bb, file); + } + fprintf (file, "\n"); +} + else df_dump (file); +} + + /* Dump the introductory information for each problem defined. */ void Index: df.h === --- df.h(revision 127917) +++ df.h(working copy) @@ -836,6 +836,7 @@ extern bool df_reg_used (rtx, rtx); extern void df_worklist_dataflow (struct dataflow *,bitmap, int *, int); extern void df_print_regset (FILE *file, bitmap r); extern void df_dump (FILE *); +extern void df_dump_region (FILE *); extern void df_dump_start (FILE *); extern void df_dump_top (basic_block, FILE *); extern void df_dump_bottom (basic_block, FILE *); Index: loop-invariant.c === --- loop-invariant.c(revision 127917) +++ loop-invariant.c(working copy) @@ -644,6 +644,7 @@ find_defs (struct loop *loop, basic_bloc if (dump_file) { + df_dump_region (dump_file); fprintf (dump_file, "*starting processing of loop **\n"); print_rtl_with_bb (dump_file, get_insns ()); fprintf (dump_file, "*ending processing of loop **\n"); Index: loop-iv.c === --- loop-iv.c (revision 127917) +++ loop-iv.c (working copy) @@ -280,7 +280,7 @@ iv_analysis_loop_init (struct loop *loop df_set_blocks (blocks); df_analyze (); if (dump_file) -df_dump (dump_file); +df_dump_region (dump_file); check_iv_ref_table_size (); BITMAP_FREE (blocks); -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33224
[Bug rtl-optimization/33224] failing rtl iv analysis (maybe due to df)
--- Comment #5 from dorit at gcc dot gnu dot org 2007-08-30 16:29 --- > dorit, > i am having trouble exactly reproducing this example because you did not > give the svn revision and so all of the numbers are a little bit > different. it's revision 127623 > However, I am going to submit a patch which improves the dump > information a lot for these passes and we should talk about it after we > can get on the same page. I applied your patch, and I'll send you the dump shorlty. > However, from looking at your posting, there are some issues that you > may want to look at before we talk: > The reaching defs problem makes a scan for all of the defs in the blocks > in the region. Once all of the defs are found, they are sorted where > the primary key is the regno. > The id's (DF_REF_ID) are then assigned based on this sorting. The > reaching defs problem actually depends on all of the defs for a regno to > be contigious. > The DF_REF_IDs are not stable between calls to df_set_blocks and any def > outside of the region has an undefined DF_REF_ID. > In your posting you have: > > Below is the output of df_ref_debug for adef in each iteration of the loop > > in > > latch_dominating_def: > > d40 reg 187 bb 3 insn 255 flag 0x0 type 0x0 loc 0xf7da4608(0xf7d9a4e0) > > chain { } > > d93 reg 187 bb 2 insn 40 flag 0x0 type 0x0 loc 0xf7d89cc8(0xf7d9a4e0) chain > > { } > The number after the first "d" is the DF_REF_ID. Note that they are not > contiguous. > Given the sorting that occurred, they must be contiguous. I assume from this > that > someone is holding on to old id's. This is not correct. > If you are going to play the game with df_set_blocks, you are allowed to hold > onto a > def, but not the DF_REF_ID, you cannot look at the DF_REF_ID for a def > that is not in the blocks set by df_set_blocks. are you saying it's safer not to call df_set_blocks in iv_analysis_loop_init? (iv-analysis still fails when I do that, but maybe that in turn requires other changes?) -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33224
[Bug rtl-optimization/33224] failing rtl iv analysis (maybe due to df)
--- Comment #7 from rakdver at kam dot mff dot cuni dot cz 2007-08-30 18:09 --- Subject: Re: failing rtl iv analysis (maybe due to df) > The only thing that you are allowed to do with the DF_REF_ID is to get > it from a df_def > AFTER YOU ARE SURE THAT THE DEF IS IN THE REGION OK, this might be the problem; the code takes the defs from the reg->def lists, and checks whether the defs are set in the reaching def bitmaps. Naturally, it assumes that when the region is set by df_set_blocks, the reaching def bitmaps will only contain the defs that belong to the region (which used to be true before your changes). Anyway, it would be nice to have some documentation for df (there is only a short notice in http://gcc.gnu.org/onlinedocs/gccint/Liveness-information.html#Liveness-information, which appears wrong given the importance of this api), in particular pointing out such non-obvious traps would be great. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33224
[Bug rtl-optimization/33224] failing rtl iv analysis (maybe due to df)
--- Comment #8 from zadeck at naturalbridge dot com 2007-08-30 18:51 --- Subject: Re: failing rtl iv analysis (maybe due to df) rakdver at kam dot mff dot cuni dot cz wrote: > --- Comment #7 from rakdver at kam dot mff dot cuni dot cz 2007-08-30 > 18:09 --- > Subject: Re: failing rtl iv analysis (maybe due to df) > > >> The only thing that you are allowed to do with the DF_REF_ID is to get >> it from a df_def >> AFTER YOU ARE SURE THAT THE DEF IS IN THE REGION >> > > OK, this might be the problem; the code takes the defs from the reg->def > lists, and checks whether the defs are set in the reaching def bitmaps. > Naturally, it assumes that when the region is set by df_set_blocks, the > reaching def bitmaps will only contain the defs that belong to the > region (which used to be true before your changes). > > And it is still true now. The set of bits in the bitmaps are EXACTLY the set of defs inside the region. The thing that has changed is that the location (slot) in the bitmap is only defined after the calls to df_set_blocks and df_analyze, i.e. the slots in the bitvectors are moved around by these calls. In your example, you asked about 2 defs. One of those defs is in the region and one of them is outside the region. It is not that the bits are zero for a def outside of the region, there is no slot in the bitvectors that corresponds to that def in the bitvectors. You are not allowed to look in the bitmap for the def outside of the region as ask any questions at all if they involve the DF_REF_ID. For the def that is in the region, you can ask but you cannot use the DF_REF_ID that it had before the call to set_blocks. That old one is trash. What has changed, and this was a very old change, from the time that danny still worked at ibm, was that the DF_REF_ID's are not stable and the slots change after setting the blocks in the region. One of the first df patches that was committed by us was to reorganize the bits so that all of the refs for a single reg were contiguous. This gave a factor of 7 speedup over the old code because it allowed for the use of new bitmap operations that worked over dense range indexes. I assume that this code has not really worked since then. > Anyway, it would be nice to have some documentation for df (there > is only a short notice in > http://gcc.gnu.org/onlinedocs/gccint/Liveness-information.html#Liveness-information, > which appears wrong given the importance of this api), in particular > pointing out such non-obvious traps would be great. > > > This is only an issue if you use df_set_blocks and the only passes that use it are these zdenek's loop passes. If I had my way (and infinite free time) I would get rid of df_set_blocks anyway. The information that it provides is generally wrong since it ignores information that enters a block from the outside, but if you are very careful to only ask a very limited range of questions, as Zdenek did, it can give you what you want relatively inexpensively. Furthermore, it has been a real pain to keep it correct as the rest of df has evolved. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33224
[Bug rtl-optimization/33224] failing rtl iv analysis (maybe due to df)
--- Comment #9 from zadeck at naturalbridge dot com 2007-08-30 18:57 --- Subject: Re: failing rtl iv analysis (maybe due to df) zadeck at naturalbridge dot com wrote: > --- Comment #8 from zadeck at naturalbridge dot com 2007-08-30 18:51 > --- > Subject: Re: failing rtl iv analysis (maybe due > to df) > > rakdver at kam dot mff dot cuni dot cz wrote: > >> --- Comment #7 from rakdver at kam dot mff dot cuni dot cz 2007-08-30 >> 18:09 --- >> Subject: Re: failing rtl iv analysis (maybe due to df) >> >> >> >>> The only thing that you are allowed to do with the DF_REF_ID is to get >>> it from a df_def >>> AFTER YOU ARE SURE THAT THE DEF IS IN THE REGION >>> >>> >> OK, this might be the problem; the code takes the defs from the reg->def >> lists, and checks whether the defs are set in the reaching def bitmaps. >> Naturally, it assumes that when the region is set by df_set_blocks, the >> reaching def bitmaps will only contain the defs that belong to the >> region (which used to be true before your changes). >> >> >> > And it is still true now. The set of bits in the bitmaps are EXACTLY > the set of defs inside the region. The thing that has changed is that > the location (slot) in the bitmap is only defined after the calls to > df_set_blocks and df_analyze, i.e. the slots in the bitvectors are moved > around by these calls. > > In your example, you asked about 2 defs. One of those defs is in the > region and one of them is outside the region. It is not that the bits > are zero for a def outside of the region, there is no slot in the > bitvectors that corresponds to that def in the bitvectors. You are not > allowed to look in the bitmap for the def outside of the region as ask > any questions at all if they involve the DF_REF_ID. For the def that is > in the region, you can ask but you cannot use the DF_REF_ID that it had > before the call to set_blocks. That old one is trash. > > What has changed, and this was a very old change, from the time that > danny still worked at ibm, was that the DF_REF_ID's are not stable and > the slots change after setting the blocks in the region. One of the > first df patches that was committed by us was to reorganize the bits so > that all of the refs for a single reg were contiguous. This gave a > factor of 7 speedup over the old code because it allowed for the use of > new bitmap operations that worked over dense range indexes. I assume > that this code has not really worked since then. > > >> Anyway, it would be nice to have some documentation for df (there >> is only a short notice in >> http://gcc.gnu.org/onlinedocs/gccint/Liveness-information.html#Liveness-information, >> which appears wrong given the importance of this api), in particular >> pointing out such non-obvious traps would be great. >> >> >> >> > This is only an issue if you use df_set_blocks and the only passes that > use it are these zdenek's loop passes. If I had my way (and infinite > free time) I would get rid of df_set_blocks anyway. The information > that it provides is generally wrong since it ignores information that > enters a block from the outside, but if you are very careful to only ask > a very limited range of questions, as Zdenek did, it can give you what > you want relatively inexpensively. > > Furthermore, it has been a real pain to keep it correct as the rest of > df has evolved. > > > > sorry zdenek, i misread who this was from, i would not have referred to you in the third person if i had read it correctly. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33224
[Bug rtl-optimization/33224] failing rtl iv analysis (maybe due to df)
--- Comment #10 from rakdver at gcc dot gnu dot org 2007-08-30 20:05 --- I know how to fix the problem, now. -- rakdver at gcc dot gnu dot org changed: What|Removed |Added AssignedTo|seongbae dot park at gmail |rakdver at gcc dot gnu dot |dot com |org http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33224
[Bug rtl-optimization/33224] failing rtl iv analysis (maybe due to df)
--- Comment #11 from zadeck at naturalbridge dot com 2007-08-30 21:46 --- Subject: Re: failing rtl iv analysis (maybe due to df) rakdver at gcc dot gnu dot org wrote: > --- Comment #10 from rakdver at gcc dot gnu dot org 2007-08-30 20:05 > --- > I know how to fix the problem, now. > > > thanks kenny -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33224
[Bug rtl-optimization/33224] failing rtl iv analysis (maybe due to df)
--- Comment #12 from rakdver at gcc dot gnu dot org 2007-08-31 15:34 --- Subject: Bug 33224 Author: rakdver Date: Fri Aug 31 15:34:45 2007 New Revision: 127996 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=127996 Log: PR rtl-optimization/33224 * loop-iv.c (latch_dominating_def): Check that the definition belongs to the analysed region. Modified: trunk/gcc/ChangeLog trunk/gcc/loop-iv.c -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33224