IRA conflict graph, multiple alternatives and commutative operands

[Jie Zhang <jie at codesourcery dot com>]

I'm looking at PR 42258. I have a question on IRA conflict graph and 
multiple alternatives.

Below is an RTL insn just before register allocation pass:

(insn 7 6 12 2 pr42258.c:2 (set (reg:SI 136)
        (mult:SI (reg:SI 137)
            (reg/v:SI 135 [ x ]))) 33 {*thumb_mulsi3})

IRA generates the following conflict graph for r135, r136 and r137:

;; a0(r136,l0) conflicts: a2(r137,l0) a1(r135,l0)
;;     total conflict hard regs:
;;     conflict hard regs:
;; a1(r135,l0) conflicts: a0(r136,l0) a2(r137,l0)
;;     total conflict hard regs:
;;     conflict hard regs:
;; a2(r137,l0) conflicts: a0(r136,l0) a1(r135,l0)
;;     total conflict hard regs:
;;     conflict hard regs:

  regions=1, blocks=3, points=5
    allocnos=3, copies=0, conflicts=0, ranges=3

Apparently this conflict graph is not an optimized one for any of the 
three alternatives in the following instruction pattern:

(define_insn "*thumb_mulsi3"
  [(set (match_operand:SI          0 "register_operand" "=&l,&l,&l")
        (mult:SI (match_operand:SI 1 "register_operand" "%l,*h,0")
                 (match_operand:SI 2 "register_operand" "l,l,l")))]
  ...)

This conflict graph seems like a merge of conflict graphs of the three 
alternatives. Ideally for the first and second alternatives, we should have

;; a0(r136,l0) conflicts: a2(r137,l0) a1(r135,l0)
;; a1(r135,l0) conflicts: a0(r136,l0)
;; a2(r137,l0) conflicts: a0(r136,l0)

For the third alternative, we'd better have

;; a0(r136,l0) conflicts: a1(r135,l0)
;; a1(r135,l0) conflicts: a0(r136,l0)
  cp0:a0(r136)<->a2(r137)@1000:constraint

And register allocator would use one of these more specific conflict 
graphs for coloring. If we take the commutative operands into count, we 
have to add the following conflict graph for choosing.

;; a0(r136,l0) conflicts: a2(r137,l0)
;; a2(r137,l0) conflicts: a0(r136,l0)
  cp0:a0(r136)<->a1(r135)@1000:constraint

(Actually, this conflict graph will result in an optimal result for the 
test case in PR 42258.)

Now the problem is when and how to choose the alternative for register 
allocator to calculate the conflict graph?

Yes, I have read the thread:

http://gcc.gnu.org/ml/gcc/2009-02/msg00215.html

This question seems not easy. So is there any practical method to make 
register allocator pick up the third alternative and do commutation 
before or during register allocation?

Thanks,
--
Jie Zhang
CodeSourcery
(650) 331-3385 x735