On Thu, Dec 10, 2015 at 12:23 AM, Jeff Law <l...@redhat.com> wrote: > Richi and I have been discussing revamping slightly how DOM handles > conditionals which it detects are always true or always false. > > During gcc6 stage1 I added code to allow DOM to clean them up > immediately, primarily to avoid the waste of having the threader handle > those cases. It was also believed that by cleaning things up during the > DOM walk we could realize some secondary benefits (certain PHIs become > more likely to collapse down to a const/copy which can then be propagated). > > That code causes an interesting problem as shown by 68619. Essentially > the CFG has 3 loops, one is a natural loop, the other two are irreducible. > > DOM finds conditionals which it can optimize to true/false. It removes > the unreachable edges and everything seems perfect. Except that removal > of those edges causes the irreducible loops become reducible. This is a > good thing, except.... > > Now we have two new natural loops, which triggers a checking failure > because we haven't set up loop structures for the newly exposed natural > loops. > > Richi's suggestion (before this problem was reported) was to have DOM > leave the CFG alone, but otherwise optimize as-if the edges had been > removed. Final removal of the edges would be left to cfg_cleanup. He > also pointed me at SCCVN which does something similar. > > Further iteration with Richi has led us to extending the dom walker > interface to directly support propagation of unexecutable properties for > clients that want that improvement. > > To use the new capability, the client passes a new parameter to the walker > constructor and in its before_dom_children callback the client returns > either the taken edge when a COND, SWITCH or GOTO collapse to a single > compile-time destination or NULL otherwise. > > The walker will take that information and determine which edges are no > longer executable. If that in turn causes blocks to become unreachable the > walker can then mark further edges as non-executable. > > The walker clears EDGE_EXECUTABLE on any edges that are deemed not > executable. The client can use this to further refine analysis and > optimizations. > > The walker will no longer call the before/after_dom_children callbacks for > unreachable blocks. > > The change is broken into 4 parts for ease of review. They must be > committed together due to the API change in the walker. They have been > bootstrapped and regression tested as a unit on x86_64-linux-gnu. > > > 1. Refactor the code from tree-ssa-sccvn.c into domwalk.c. Essentially the > constructor is no longer trivial as it may need to initialize > EDGE_EXECUTABLE. The return type of the before_dom_children callback > changes from void to an edge. Two additional private member functions are > added to check a block for reachability and to propagate unexecutable > properties. Included are the changes to sccvn to use the new capabilities. > > 2. Use the new capabilities in tree-ssa-dom.c. > > 3. New tests. One is the actual 68619 testcase. Two ICEs for minor > bugs found during development/testing, one case where we optimize better > now than before, one for a missed optimization during development. > > 4. Mechanical changes to the other dom walkers. The return type of the > before_dom_children callback changes from void to edge. For the callbacks > changed in this patch, we always return NULL. > > > How does this look now?
The series looks good to me. Thanks, Richard. > > Jeff
