------- Comment #18 from hubicka at gcc dot gnu dot org 2008-02-06 16:44 ------- Created an attachment (id=15107) --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=15107&action=view) Path to predict_paths_leading_to
Hi, I've revived the continue heuristic patch. By itself it does not help becuase of bug in predict_paths_leading_to. The code looks as follows: if (test1) goto continue_block; if (test2) goto continue_block; if (test3) goto continue_block; if (test4) goto continue_block; goto real_loop_body; continue_block: goto loop_header; We call predict_paths_leading_to on the continue_block and expect that the continue_block will not be very likely. What the function does is to find dominator of continue_block that is the if(test1) block and predict edge from the first block. This is however not quite enough as all the other paths remain likely. It seems to me that we need to walk the whole set of BBs postdominated by the BB and mark all edges forming edge cut defined by this set. I am testing the attached patch. It makes the function linear (so we are overall quadratic) for very deep postdominator tree. If this turns out to be problem, I think we can just cut the computation after some specified amount of BBs is walked. Zdenek, does this seem sane? With this change and continue prediction patch I get sort of sane prediction for longest_match function. Profile is still quite unrealistic, but I am testing if it makes noticeable difference. Honza -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33761