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.