Re: [PATCH 28/28] New -fcompare-elim pass.

[Paolo Bonzini <bonzini at gnu dot org>]

On 01/12/2011 08:44 PM, Richard Henderson wrote:
> On 01/12/2011 12:31 AM, Paolo Bonzini wrote:
> > > +      /* Note that df does not create use chains that cross basic blocks.
> >
> > I don't think this is correct, as this is the very thing that is
> > responsible for the chains problem's potential quadratic behavior.
> > Have you seen it in practice (the chain that doesn't cross basic
> > blocks, not the quadratic behavior)?
>
> No, I thought I'd correctly read the code to determine that.

Chains are based on the output of reaching definitions, they do not care 
about whether the defs are in the same basic block or not.

> > > +  if (DF_REF_CHAIN (use) == NULL)
> > > +    return false;
> > > +
> > > +  def = DF_REF_CHAIN (use)->ref;
> >
> > Here you should probably bail out if the use has multiple reaching
> > definitions (i.e. DF_REF_CHAIN (use)->next != NULL). It probably
> > won't happen given how cbranch/cstore splitters work, but you never
> > know.
>
> Good idea, though this has nothing to do with cbranch/cstore.  This
> is finding the DEF for the register use inside the compare.

Oops, right.

> > > +     Note that this doesn't follow the USE-DEF chain from X, but
> > > +     since we already have to search for the previous clobber of
> > > +     the flags register, this wouldn't really be a problem.  */
> > > +
> > > +  /* Make sure that the flags are not clobbered in between the two
> > > +     instructions.  Unfortunately, we don't get DEF-DEF chains, so
> > > +     do this the old fashioned way.  */
> >
> > Again, this is probably handled better without the use-def chains.
> > (Chains are in the DF framework, but are rarely the best
> > solution---especially if you're not limiting them to a region, e.g. a
> > loop).
>
> Err, I'm not using use-def chains for this.  I'm using reg_set_between_p.
> I'm a bit confused about your statement here.

You're right, what I meant was "since you are anyway resorting to the 
old fashioned way, you can probably handle everything better without the 
use-def chains".

> I'm a bit confused about the stance in regards to chains.  Should I
> attempt to avoid them entirely, so that I never add the problem?

It's an expensive problem when applied to the entire function, so it is 
better to avoid it.  I'm not saying this cannot be delayed to 4.7 if the 
pass goes in now (it's almost a target-specific pass now, so it probably 
could).

> I guess I can implement try_eliminate_compare by:
>
>    * In find_comparisons_in_bb, remember the previous insn that
>      clobbers CC_REG.  Record that in struct comparison.prev_clobber.
>
>    * In try_eliminate_compare, if prev_clobber is not set, then we
>      don't know where CC_REG was previously set, so we cannot eliminate.
>
>    * The SET in prev_clobber must be the comparison.in_a register.
>      If it isn't, then we cannot eliminate.
>
>    * Use reg_set_between_p to verify that comparison.in_a is not
>      modified between prev_clobber and comparison.insn.

Exactly.

> It's that last step that seems a bit... odd, but not wrong exactly.
> But is it odd enough to warrant using chains?

I'd say no because you're doing the same right now.  USE-DEF chains get 
you to a clobber, and then reg_set_between_p confirms whether that 
clobber is the prev_clobber.

If you really want to remove the reg_set_between_p, you can of course 
record the SET of prev_clobber, and reset prev_clobber if an insn sets 
that register.  But I think it's more clumsy and not enough more 
efficient than what you outlined.

Paolo