On August 11, 2016 8:41:53 PM GMT+02:00, Jeff Law <l...@redhat.com> wrote: >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.
Hmm, isn't walking backwards from uses doing a lot of redundant stmt walking compared to walking stmts once in forward direction? To me it sounds like a 'local' patterns matching like optimization rather than a global one with proper data flow or a lattice? Richard. > >Jeff
