On 08/11/2016 08:27 AM, Jan Hubicka wrote:
On tramp3d all VRP passes threads together 730 branches, all DOM passes 393, so
FSM threading (with 1957 branches) is the most effective one. Perhaps eventually
early VRP can also do bit of work.
That's roughly consistent with what I've seen. I have some thoughts on
what DOM's threading pass is catching that we're missing in the
backward/FSM threader, but I haven't had time to see how big those
effects really are.
I am not 100% sure from where "backward" is comming from. I guess is means that
analysis goes backward from conditionals to definitions: it looks for
conditional driven by a PHI statement that has a constant value on some paths
and duplicates for those. This seems cheap and rather effective way of getting
good part of the threading oppurtunities (most expensive part is probably
identifying and walking paths that will not be threaded at the end).
Correct, forward/backward is based on the direction of analysis. ie, do
we start at the conditional and work backwards through the USE-DEF chain
or do we build a equivalence table as we walk forward through the entire
function and use the equivalence tables to simplify the conditional.
BTW I wonder if the same analysis can't be done for other instructions where
constant
operands are very profitable, like division or multiplication.
Yes. There's all kinds of problems that can be solved using a backwards
walk to identify useful properties on paths, then path duplication to
isolate the use point and modify it.
So you could (for example) walk backwards from an indirect call and
identify paths through the CFG where we know the target. We then can
use path duplication to isolate that path from the rest and call the
target function directly.
Jeff
