> 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. > > 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? 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_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
