Re: [RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [0/3] v2
On Thu, Dec 10, 2015 at 12:23 AM, Jeff Law 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
[RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [0/3] v2
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? Jeff
[RFA] [PATCH] [PR tree-optimization/68619] Avoid direct cfg cleanups in tree-ssa-dom.c [0/3]
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. This change essentially has DOM working in the same was as SCCVN. The change is broken into 3 parts. 1. Refactor the code from tree-ssa-sccvn.c into domwalk.c Essentially it's 4 new member functions that a dominator walker can optionally use to improve it's behaviour when the pass might make certain edges unexecutable. I need someone to review these changes. If you've got a better name for the member functions, certainly pass them along. I'm not particularly happy with maybe_clear_unreachable_dom. It feels like an internal implementation detail has leaked out, but I'm not really sure how to fix it, so any suggestions there are certainly welcome 2. Use the new member functions in tree-ssa-dom.c. It's pretty simple stuff. 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. The patchset as a whole has been bootstrapped and regression tested on x86_64-linux-gnu. Jeff
