Re: Basic block reordering algorithm
On Wednesday 13 April 2005 00:18, Pat Haugen wrote: When we have a test block gating whether a loop should be entered, the new block frequency check causes the code to pick the non-loop path as the next block to add to the trace since the loop header block has a higher frequency, and hence the loop gets moved out of line. Have you tried with the patch to re-enable the loop header copying predictor: http://gcc.gnu.org/ml/gcc-patches/2005-03/msg02577.html? It sounds like you might want to try that first... Gr. Steven
Re: Basic block reordering algorithm
Steven Bosscher [EMAIL PROTECTED] wrote on 04/13/2005 09:39:55 AM: On Wednesday 13 April 2005 00:18, Pat Haugen wrote: When we have a test block gating whether a loop should be entered, the new block frequency check causes the code to pick the non-loop path as the next block to add to the trace since the loop header block has a higher frequency, and hence the loop gets moved out of line. Have you tried with the patch to re-enable the loop header copying predictor: http://gcc.gnu.org/ml/gcc-patches/2005-03/msg02577.html? It sounds like you might want to try that first... That does indeed fix the case when there is no profile data present. But if we have real profile data which presents a 50/50 probability on the gating block then we're back to the same situation of moving the loop out of line (although I guess one can always come up with scenarios to cause heuristics to look bad, which many times may not be worth worrying about).
Re: Basic block reordering algorithm
On Wednesday 13 April 2005 20:46, Pat Haugen wrote: Steven Bosscher [EMAIL PROTECTED] wrote on 04/13/2005 09:39:55 AM: On Wednesday 13 April 2005 00:18, Pat Haugen wrote: When we have a test block gating whether a loop should be entered, the new block frequency check causes the code to pick the non-loop path as the next block to add to the trace since the loop header block has a higher frequency, and hence the loop gets moved out of line. Have you tried with the patch to re-enable the loop header copying predictor: http://gcc.gnu.org/ml/gcc-patches/2005-03/msg02577.html? It sounds like you might want to try that first... That does indeed fix the case when there is no profile data present. But if we have real profile data which presents a 50/50 probability on the gating block then we're back to the same situation of moving the loop out of line (although I guess one can always come up with scenarios to cause heuristics to look bad, which many times may not be worth worrying about). Well, if there is a 50/50 probability, does it matter if the loop is moved out of line? There is a 50/50 chance that you will not enter the loop, so moving it inline hurts the other, equally likely path. The problem with your original proposal is that computing post-dominance information really is expensive. Depending on how often this 50/50 case happens, in a real profile, it may or may not be worth the cost do as you suggested. My guess is that it doesn't happen very often and it isn't worth it. Maybe it is, you'd have to try. With some luck we will have the infrastructure in place RSN to preserve loop information over passes (at the very least as a loop region). When that stuff is available, we could teach bb-reorder to use that information to solve your problem properly (and fix the find_traces_1_round hack you noted). Gr. Steven
Re: Basic block reordering algorithm
On Wednesday 13 April 2005 22:52, Pat Haugen wrote: Back to the original problem with the algorithm using edge frequency vs. block frequency. Would you agree that the correct thing to do is fix the code so that it uses block frequency, especially since the patch of Zdenek's you referenced takes care of the original problem I saw when doing so? My understanding of what you propose is that you want to use the dest block frequency as the tie-breaker in the case that both edges have the same probability. Right? I think this would be reasonable. Not my decision to make, though ;-) Gr. Steven P.S. I wonder why the code for the best edge in tracer.c:better_p is not the same as the code in bb-reorder -- or why we have two trace finding algorithms in one compiler... Honza??
