On Fri, 19 Oct 2012, Jan Hubicka wrote: > > On Fri, 19 Oct 2012, Jan Hubicka wrote: > > > > > Hi, > > > this patch fixes off-by-one error in the testcase attached. The problem > > > is that > > > dominance based test used by record_estimate to check whether the given > > > statement > > > must be executed at last iteration of the loop is wrong ignoring the side > > > effect > > > of other statements that may terminate the program. > > > It also does not work for mulitple exits as excercised by cunroll-2.c > > > testcase. > > > > > > This patch makes simple approach of computing set of all statements that > > > must > > > by executed last iteration first time record_estimate is executed this > > > way. > > > The set is computed conservatively walking header BB and its signle > > > successors > > > (possibly diving into nested loop) stopping on first BB with multiple > > > exits. > > > > > > Better result can be computed by > > > 1) estimating what loops are known to be finite > > > 2) inserting fake edges for all infinite loop and all statements with > > > side effect > > > that may terminate the execution > > > 3) using the post dominance info. > > > > would using post-dom info even work? That only says that _if_ the > > dominated stmt executed then it came through the dominator. It > > doesn't deal with functions that may not return. > > With fake edges inserted it will. We do have code for that used in profiling > that > also needs this stronger definition of CFG.
Huh, but then we will need to split blocks. I don't think that's viable. > > > > What about the conservative variant of simply > > > > else > > delta = double_int_one; > > I think it would be bad idea: it makes us to completely unroll one interation > too many that bloats code for no benefit. No optimization cancels the path in > CFG because of undefined effect and thus the code will be output (unless > someone > smarter, like VRP, cleans up later, but it is more an exception than rule.) > > > > ? I don't like all the code you add, nor the use of ->aux. > > Neither I really do, but what are the alternatives? See above ;) > My first implementation simply checked that stmt is in the loop header and > walked up to the beggining of basic blocks looking for side effects. Then I > become worried about possibility of gigantic basic blocks with many array > stores within the loop, so I decided to record the reachable statements > instead > of repeating the walk. > Loop count estimation is recursive (i.e. it dives into inner loops), thus I > ended up with using AUX. I can for sure put this separately or add extra > reference argument passed over the whole call stack, but there are quite many > functions that can leads to record_estimate. (I have nothing against that > alternative however if AUX looks ugly) I am worried about passes trying to use AUX. We should at least document that it is for internal use only. > > > > > i_bound += delta; > > > > Another alternative would be to not use i_bound for the > > strong upper bound but only the estimate (thus conservatively > > use i_bound + 1 for the upper bound if !is_exit). > > We can not derrive realistic estimate based on this: the loop may exit much > earlier. > We can only lower the estimate if it is already there and greater than this > bound. > This can probably happen with profile feedback and I can implement it later, > I do not think it is terribly important though. > > Honza > > -- Richard Biener <rguent...@suse.de> SUSE / SUSE Labs SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 GF: Jeff Hawn, Jennifer Guild, Felix Imend
