Re: IRA conflict graph, multiple alternatives and commutative operands

[Vladimir Makarov]

Jie Zhang wrote:
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?
I do not know such practical method.  IRA should create correct RA 
whatever alternative reload chooses for insns.  Otherwise reload might 
generate a wrong code.  As for code telling IRA (and reload) what 
alternatives only to consider, it is doable to implement but the 
question again is how to choose what alternatives to consider.

In you particular example.  It might seem that 1st alternative is always 
worse than third one if the first operand dies.  But even such check is 
not easy to implement.  Also that might be not true for some global 
register allocation results.