Backward insn combination?

[Jeffrey A Law]

  > Can anyone familiar with the insn combination pass elucidate why it
  > scans insns in a forward direction.  My naiive understanding would
  > suggest that it could do a better job by scanning in a reverse
  > direction so I'm assuming that I've missed something fundamental.
The scan direction is not particularly important.  What is important is
the backwards dependency information found in the LOG_LINKS fields of
each insn.

  > For example, say I had the following pseudo RTL (typical of what is
  > generated when performing complex arithmetic):
  > 
  > insn 1:  (set (reg 1) (mem (post_inc (reg 0))))
  > insn 2:  (set (reg 2) (mem (post_inc (reg 0))))
  > insn 3:  (set (reg 3) (abs (reg r1)))
  > insn 4:  (set (reg 4) (abs (reg r2)))
  > 
  > which I would like converted to:
  > 
  > insn 3:  (set (reg 3) (abs (mem (post_inc (reg 0)))))
  > insn 4:  (set (reg 4) (abs (mem (post_inc (reg 0)))))
  > 
  > Now, the current combiner would try combing insn3 with insn1, but
  > would find that it would have to move the def of (reg 0) in insn1 past
  > the use of (reg 0) in insn2, so it would give up.  It doesn't realise
  > that this wouldn't be a problem since it is possible to combine insn 2
  > with insn 4, which it does without any problem.
  > 
  > If the combiner scanned the insns in backward direction, would this
  > not solve the problem?  I suppose another pass of the combiner would
  > also fix this particular example?
And with a trivial amount of work once would be able to write cases which
fail when scanning backward, but not forward.  Half a dozen one way, 6 the
other I suspect.

What you may need is multiple iterations of the combiner at higher optimization
levels.  Though I have no idea how safe that would be and how many new
combinations later passes would find. Probably worth some experiments.

Another approach would be to keep full dependency information.  Then when you
perform a combination like insn 2 -> insn 4 above, you go back to the previous
use/def of r0 (insn 1) and restart the combination process.



jeff