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
