http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55860
--- Comment #3 from Jeffrey A. Law <law at redhat dot com> --- The other issue here is the loop header which looks like: bb4: # iii_16 = PHI <iii_12(8), 0(3)> # jkl_17 = PHI <jkl_4(8), 0(3)> L1: if (m_8(D) > iii_16) goto <bb 5>; else goto <bb 6>; [... ] bb7 # iii_12 = PHI <0(6), iii_10(5)> # jkl_4 = PHI <jkl_11(6), jkl_17(5)> L2: if (jkl_4 < n_7(D)) goto <bb 8>; else goto <bb 9>; The path 4->5->7->8->4 is the path we want to optimize. The problem is we can't record anything useful about the value of jkl_17 in bb4 and propagate that to bb4's children. We don't have a useful path to follow backwards because of the multiple predecessors of bb4. What would be more promising would be Bodik's approach of walking backwards from the test expression to discover the redundancy. That would require reimplementing the jump threading code as a separate pass from DOM, which would probably be a good thing. In this particular case it'd work something like this At the end of bb7 we have this expression and we want to see if it's already been computed and available on a useful path. jkl_4 < n_7 We look up jlk_4's definition statement (PHI in bb7) and substitute values from both paths. The path from 6->7 gets followed and nothing useful will be found. The path from block 5-7 is the interesting one and results in jkl_17 < n_7 We then look up jlk_17's definition statement (PHI in bb4) and substitute values from path paths. The path from bb8 is obviously not useful, but the path from bb3 is useful resulting in 0 < n_7 We then would find 0 < n_7 with the value as true when bb4 is reached from bb3. This tells us that the path 3->4->5->7 has a redundant condition and if we can isolate the path it can be optimized. But this is definitely future work. I'm looking at some limited code to walk up the control dependence tree to pick up more expressions for the tables. At first glance it seems to factor out nicely. It won't help this case, but may help others.
