Combine error?

Combine error?

[Jason Eckhardt]

I'm seeing many of these on hppa1.1 with --enable-checking:
Internal compiler error in `combine_instructions', at combine.c:632
    RTL check: access of elt 5 of `note' with last elt 4

That code is:
          /* Try each sequence of three linked insns ending with this one.  */

          for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
-->         for (nextlinks = LOG_LINKS (XEXP (links, 0)); nextlinks;
                 nextlinks = XEXP (nextlinks, 1))


The subexpression "XEXP (links, 0)" in some cases is a note, so the rtl
checker flags a problem when we access LOG_LINKS of it.
What is the intent here? Should we simply check for a note and not
execute the for-loop if it is?

jason.

Re: Combine error?

[Richard Earnshaw]

> 
> I'm seeing many of these on hppa1.1 with --enable-checking:
> Internal compiler error in `combine_instructions', at combine.c:632
>     RTL check: access of elt 5 of `note' with last elt 4
> 
> That code is:
>           /* Try each sequence of three linked insns ending with this one.  */
> 
>           for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
> -->         for (nextlinks = LOG_LINKS (XEXP (links, 0)); nextlinks;
>                  nextlinks = XEXP (nextlinks, 1))
> 
> 
> The subexpression "XEXP (links, 0)" in some cases is a note, so the rtl
> checker flags a problem when we access LOG_LINKS of it.
> What is the intent here? Should we simply check for a note and not
> execute the for-loop if it is?
> 
> jason.

Nick Clifton posted a patch to do exactly that.  I objected because I 
thought that it was wrong for a log-link to point to a note (it happens 
because flow has converted the insn pointed to into a pre/post operand in 
another insn, but hasn't updated the link).  However, I thought Jeff had 
over-ruled on this one and said the patch was OK; but it doesn't seem to 
have got any further than that.

R.

Re: Combine error?

[Jeffrey A Law]

  In message < 200003201600.QAA11765@cam-mail2.cambridge.arm.com >you write:
  > Nick Clifton posted a patch to do exactly that.  I objected because I 
  > thought that it was wrong for a log-link to point to a note (it happens 
  > because flow has converted the insn pointed to into a pre/post operand in 
  > another insn, but hasn't updated the link).  However, I thought Jeff had 
  > over-ruled on this one and said the patch was OK; but it doesn't seem to 
  > have got any further than that.
I didn't remember a final resolution on whether or not we should try to
kill the dead LOG_LINKS or just handle them.

I would think the only way we could get dead LOG_LINK pointers would be
due to the optimization phase of flow (auto-inc, dead code elimination
and the like) or due to combine's actions.  So it may be possible to avoid
the dead links.  I really don't know.

jeff

Re: Combine error?

[Richard Earnshaw]

> 
>   In message < 200003201600.QAA11765@cam-mail2.cambridge.arm.com >you write:
>   > Nick Clifton posted a patch to do exactly that.  I objected because I 
>   > thought that it was wrong for a log-link to point to a note (it happens 
>   > because flow has converted the insn pointed to into a pre/post operand in 
>   > another insn, but hasn't updated the link).  However, I thought Jeff had 
>   > over-ruled on this one and said the patch was OK; but it doesn't seem to 
>   > have got any further than that.
> I didn't remember a final resolution on whether or not we should try to
> kill the dead LOG_LINKS or just handle them.

I don't think the discussion got any further than two opinions :-(

> I would think the only way we could get dead LOG_LINK pointers would be
> due to the optimization phase of flow (auto-inc, dead code elimination
> and the like) or due to combine's actions.  So it may be possible to avoid
> the dead links.  I really don't know.

AFAIK, the auto-inc optimizations are the only source of this problem.  
LOG_LINKS always point backwards within a single BB; and dead-code 
elimination will only remove code to the end of a BB (ie it won't remove 
some code from a BB without removing all code to the end of that block) 
[err, actually, won't it only remove whole blocks?].  Combine also can't 
create such anomalies because it only works on insns that have a single 
subsequent use.

So I believe the problem can only occur in the auto-inc code (which is why 
only some ports see this problem when checking is enabled).

R.

Re: Combine error?

[Jeffrey A Law]

  In message < 200003210700.HAA23579@cam-mail2.cambridge.arm.com >you write:
  > and dead-code 
  > elimination will only remove code to the end of a BB (ie it won't remove 
  > some code from a BB without removing all code to the end of that block) 
  > [err, actually, won't it only remove whole blocks?].
No, dead code elimination will remove any instruction which it can prove
is useless.  For example if we have consecutive stores to the same pseudo,
one must be dead and dead code elimination will delete the first store.

You might be confusing dead code elimination with removal of unreachable
code.  When we delete unreachable code we delete entire blocks (since the
entire block is unreachable).

  > Combine also can't 
  > create such anomalies because it only works on insns that have a single 
  > subsequent use.
I don't see how that avoids the problem.

In the simple case, when we do a 2->1 combination, one of the old insns is
dead.  I don't remember offhand if we combine earlier insns into later insns
or vice-versa.

If we combine earlier into later, then the earlier insn can be turned into
a NOTE_INSN_DELETED.  Presumably if that happens we delete the link from
the later insn to the earlier insn.

If we combine later into earlier, then the later insn can be turned into a
NOTE_INSN_DELETED, but we don't have any convenient way to find any LOG_LINKS
that pointed to the later insn.

The same basic problem applies to auto-inc.  If we turn the later insn into
a NOTE_INSN_DELETED, then we'd have to wander the insn chain to find LOG_LINKS
which point to the later insn.

jeff

Re: Combine error?

[Richard Earnshaw]

>   In message < 200003210700.HAA23579@cam-mail2.cambridge.arm.com >you write:
>   > and dead-code 
>   > elimination will only remove code to the end of a BB (ie it won't remove 
>   > some code from a BB without removing all code to the end of that block) 
>   > [err, actually, won't it only remove whole blocks?].
> No, dead code elimination will remove any instruction which it can prove
> is useless.  For example if we have consecutive stores to the same pseudo,
> one must be dead and dead code elimination will delete the first store.
> 

But in that case the link should point to the last such store; we would 
have a real bug if the log_link pointed to the store that had been 
eliminated.  And if the use were between the two stores, then by 
definition the first store wouldn't be dead (though the second might be).

> You might be confusing dead code elimination with removal of unreachable
> code.  When we delete unreachable code we delete entire blocks (since the
> entire block is unreachable).

Yes, I was.

> 
>   > Combine also can't 
>   > create such anomalies because it only works on insns that have a single 
>   > subsequent use.
> I don't see how that avoids the problem.
> 
> In the simple case, when we do a 2->1 combination, one of the old insns is
> dead.  I don't remember offhand if we combine earlier insns into later insns
> or vice-versa.
> 
> If we combine earlier into later, then the earlier insn can be turned into
> a NOTE_INSN_DELETED.  Presumably if that happens we delete the link from
> the later insn to the earlier insn.
> 
> If we combine later into earlier, then the later insn can be turned into a
> NOTE_INSN_DELETED, but we don't have any convenient way to find any LOG_LINKS
> that pointed to the later insn.

We always combine the earlier into the later; in fact, combine won't allow 
the merge if it can't effectively relocate the insns it is combining to be 
consecutive at the later position (it doesn't actually move them of 
course, it just checks that such a transformation would be legal).

If there is a problem with combine, I think it can only occur if the 
earlier insn is a parallel of more than one set; but I'm not sure that we 
even get links for that case (or if we do, that combine will every try to 
merge them).

The fact that combine always puts the result of a merge at the target does 
mean that we sometimes miss potential recombinations; for example

i1:  (set r1 plus (r2, r3))

i2:  (set r2 plus (r2, const 1))

i3:  (set r4 plus (r1, const 5))

We cannot at present combine i1 and i3 because i1 cannot be "moved" after 
i2 (since r2 is updated).  We could, but don't, merge i1 and i3 and place 
them before i2; but at present combine doesn't know how to do this.  Even 
if we did this, then provided we kept the shell of i3 as the result; any 
log_links pointing to it would still point to the setter insn.

> 
> The same basic problem applies to auto-inc.  If we turn the later insn into
> a NOTE_INSN_DELETED, then we'd have to wander the insn chain to find LOG_LINKS
> which point to the later insn.

I think the problem only occurs with post_inc/dec type adjustments.  In 
this case we have something like:

i1: (set r1 mem(r2))

i2: (xxx)

i3: (set r2 plus (r2, const 4))

i4: (xxx (r2)) LOG_LINK (i3)

In this case flow combines i1 and i3 and puts the result in the shell of 
i1, giving:

i1: (set r1 mem(post_inc(r2)))

i2: (xxx)

i3: (dead)

i2: (xxx (r2) LOG_LINK (i3)

Which of course, leads to a possible solution to our problem of updating 
i4:  If, as part of creating the auto_inc we first reorder the stream as

i1: (set r1 mem(r2))

i3: (set r2 plus (r2, const 4))

i2: (xxx)

i4: (xxx (r2)) LOG_LINK (i3)

and then combine, but put the result in i3, we get:

i1: (dead)

i3: (set r1 mem(post_inc(r2)))

i2: (xxx)

i2: (xxx (r2) LOG_LINK (i3)

and our log_link still points to the correct setter.

Re: Combine error?

[Jeffrey A Law]

  In message < 200003221223.MAA25613@cam-mail2.cambridge.arm.com >you write:
  > We always combine the earlier into the later; in fact, combine won't allow 
  > the merge if it can't effectively relocate the insns it is combining to be 
  > consecutive at the later position (it doesn't actually move them of 
  > course, it just checks that such a transformation would be legal).
OK.  I wasn't sure and didn't have time to check the sources :-)

  > The fact that combine always puts the result of a merge at the target does 
  > mean that we sometimes miss potential recombinations; for example
  > 
  > i1:  (set r1 plus (r2, r3))
  > 
  > i2:  (set r2 plus (r2, const 1))
  > 
  > i3:  (set r4 plus (r1, const 5))
  > 
  > We cannot at present combine i1 and i3 because i1 cannot be "moved" after 
  > i2 (since r2 is updated).  We could, but don't, merge i1 and i3 and place 
  > them before i2; but at present combine doesn't know how to do this.  Even 
  > if we did this, then provided we kept the shell of i3 as the result; any 
  > log_links pointing to it would still point to the setter insn.
Right. I think Michael Hayes has mentioned similar cases where we're
missing opportunities for insn combination.  The question is can we safely
and cleaning change combine to handle both?

Having combine work on SSA form might provide the functionality we need --
r2 in i2 would be renamed to a new register which removes the problamtic
dependency between i1 and i2.


  > I think the problem only occurs with post_inc/dec type adjustments.  In 
  > this case we have something like:
[ ... ]
Got it.

  > Which of course, leads to a possible solution to our problem of updating 
  > i4:  If, as part of creating the auto_inc we first reorder the stream as
  > 
  > i1: (set r1 mem(r2))
  > 
  > i3: (set r2 plus (r2, const 4))
  > 
  > i2: (xxx)
  > 
  > i4: (xxx (r2)) LOG_LINK (i3)
  > 
  > and then combine, but put the result in i3, we get:
  > 
  > i1: (dead)
  > 
  > i3: (set r1 mem(post_inc(r2)))
  > 
  > i2: (xxx)
  > 
  > i2: (xxx (r2) LOG_LINK (i3)
  > 
  > and our log_link still points to the correct setter.
Interesting.  However, don't you have to go find any LOG_LINK that points
to i1 and redirect it to i2?  Consider the next user of the value in r1.

jeff

Re: Combine error?

[Richard Earnshaw]

> Having combine work on SSA form might provide the functionality we need --
> r2 in i2 would be renamed to a new register which removes the problamtic
> dependency between i1 and i2.

Yes, that should handle this case, though at the possible expense of 
increasing register pressure.  I'm not sure if there are other cases that 
we are missing that might need other approaches; for example if memory 
references are involved (this is probably more of an issue on a CISC 
architecture than a RISC of course, since most RISCs are load-store).  
This is good news since it means that combine's algorithm won't need 
changing to take advantage of this optimization.

An interesting corollary of transforming to SSA form is that we won't see 
the log_links to a deleted insn either (I'm assuming SSA is generated 
before flow runs), since the insns killed by generating post-inc/dec will 
instead contain a copy from the incremented insn to the new target.

> 
>   > Which of course, leads to a possible solution to our problem of updating 
[...]

> Interesting.  However, don't you have to go find any LOG_LINK that points
> to i1 and redirect it to i2?  Consider the next user of the value in r1.

Argh! You are quite correct.  It is also the case that the LOG_LINK that 
we keep by this method is of little use to combine since it is now not an 
insn src setter (so combine can't substitute for it).

I'll see if I can think of an efficient way of tracking down a dead link 
from within flow when we create the anomaly.

R.