This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Early jump threading
On August 11, 2016 8:41:53 PM GMT+02:00, Jeff Law <law@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