CSE & compare/branch template problem

CSE & compare/branch template problem

[Michael Eager]

Hi --

I'm working on creating the cstore and cbranch templates
for the Xilinx MicroBlaze processor.  I've run into some
problems and an unexpected interaction with CSE processing.
Possibly, the insns I'm generating for comparisons are not
what the CSE optimization expects.

MicroBlaze has a bit unusual compare and branch architecture.
There are no condition flags; comparison results are stored in
a result register.

There's one branch instruction, which compares a register
with zero and branches based on condition (eq, ne, lt, gt, etc.).

There are a number of different instructions which can be used
for comparisons.  Regular instructions like sub or xor can be
used in some cases.  There are also cmp/cmpu instructions which
do a modified subtraction of signed and unsigned integers.
There are other comparison instructions for eq/ne which give
a 0 or one result.  The FP comparisons are all coupled with
a condition:  fcmp.eq, fcmp.lt, etc.

To generate the correct comparison instruction, I need to
know both the operands and the test condition.

It doesn't look like the (compare:CC ...) template can be
used.  Compare takes two operands and there is no place to
save the condition.

For comparisons, I'm generating insns like:

   (set (reg:CC rD) (eq:CC (reg:SI rA) (reg:SI rB))

followed by a branch:

   (if_then_else
      (eq:CC (reg:CC rD) (const_int 0))
      (label_ref xx)
      (pc)))

This looks OK and it appears to work reasonably well.  At
least without optimization.  CSE appears to be misinterpreting
the comparison insn and the code gets trashed.

This is taken from strchr.c in Newlib.  The preprocessed code
snippet is

    unsigned char c = i;

    if (!c)
       {
         while (((long)s & (sizeof (long) - 1)))
           {
             if (!*s)
               return (char *) s;
             s++;
           }
         . . .

Before CSE, this is the insn sequence:

(insn 90 89 91 2 .../strchr.c:66
   (set (reg/v:SI 137 [ c+-3 ])
        (zero_extend:SI (subreg:QI (reg/v:SI 244 [ i ]) 3))) 33

(insn 92 91 93 2 .../strchr.c:73
   (set (reg:SI 245)
        (const_int 0 [0x0])) 41

(insn 93 92 94 2 .../strchr.c:73
   (set (reg:CC 246)
        (eq:CC
            (reg/v:SI 137 [ c+-3 ])
            (reg:SI 245))) 71

(jump_insn 94 93 95 2 .../strchr.c:73
   (set (pc)
        (if_then_else
             (eq:CC
                 (reg:CC 246)
                 (const_int 0 [0x0]))
             (label_ref 112)
             (pc)))

This is the first if expression.   Note that reg 137 [c] is set to the
masked value of the search character i.  Reg 245 is set to zero, which
is used in the compare instruction in insn 93.

The while expression is

(insn 97 96 98 3 .../strchr.c:93
   (set (reg:SI 247)
        (and:SI
	    (reg/v/f:SI 140 [ s ])
             (const_int 3 [0x3]))) 25

(insn 98 97 99 3 .../strchr.c:93
   (set (reg:SI 248)
        (const_int 0 [0x0])) 41

(insn 99 98 100 3 .../strchr.c:93
   (set (reg:CC 249)
        (eq:CC
            (reg:SI 247)
            (reg:SI 248))) 71

(jump_insn 100 99 101 3 .../strchr.c:93
   (set (pc)
        (if_then_else
             (eq:CC
                 (reg:CC 249)
                 (const_int 0 [0x0]))
             (label_ref 225)
             (pc))) 75

Reg 247 is set to the masked value of s, the string pointer.
Reg 248 is set to zero and is used in the compare in insn 99.

All of this looks OK to me.

There is an intermediate step where reg 248 is replaced by
reg 245, since both are set to zero.

Somehow, CSE is deciding that reg 137 is equal to zero and
translates insn 99 to

(insn 99 98 100 3 .../strchr.c:93
   (set (reg:CC 249)
        (eq:CC
            (reg:SI 247)
            (reg/v:SI 137 [ c+-3 ]))) 71

There is a REG_EQUAL note on this insn saying that it is equal
to const zero.  At this point, the code is hosed.

I've been stepping through CSE to figure out why it
decides that reg 137 is equal to zero, but haven't
found this yet.

(Yes, I do recognize that a comparison with zero can be
simplified into just the branch insn.  That's on my to do list.)

Questions:

   Is this a reasonable way to represent the comparisons?

   Are there other targets which save comparison results
   in registers and require the condition?

   Any suggestions on better ways to model the MicroBlaze
   comparison operations?

   Are there some restriction on using eq/ne/lt/... the
   way I am?

   Any suggestions on how to fix the problem in CSE?

-- 
Michael Eager	 eager@eagercon.com
1960 Park Blvd., Palo Alto, CA 94306  650-325-8077

Re: CSE & compare/branch template problem

[Joern Rennecke]

Quoting Michael Eager <eager@eagercon.com>:

> Hi --
>
> I'm working on creating the cstore and cbranch templates
> for the Xilinx MicroBlaze processor.

In theory cstore / cbranch should be the future, but the last time I tried
to use them, they didn't quite work right yet, particularily if you have
an incomplete comparison set.  Because of delays with the Copyright
assignment, fixing the middle-end was not an efficient option, so I went
for the old hack with separate compare and condjump / cstore patterns.

> Somehow, CSE is deciding that reg 137 is equal to zero and
> translates insn 99 to
>
> (insn 99 98 100 3 .../strchr.c:93
>   (set (reg:CC 249)
>        (eq:CC
>            (reg:SI 247)
>            (reg/v:SI 137 [ c+-3 ]))) 71

That is correct; after the jump_insn 94 is not taken, you can conclude
that reg 137 is zero.
>
> There is a REG_EQUAL note on this insn saying that it is equal
> to const zero.

I would say that is a problem; find out why the note gets there.


>   Are there other targets which save comparison results
>   in registers and require the condition?

Yes.  One example is SH64.

>   Any suggestions on better ways to model the MicroBlaze
>   comparison operations?
>
>   Are there some restriction on using eq/ne/lt/... the
>   way I am?
>
>   Any suggestions on how to fix the problem in CSE?

There are some problems if comparisons can't be reversed.
I think it's a bug in the generic code, but for any given port, it's
easier - and gives better code - to make sure that all conditions can
be reversed, rather than fix the generic code.
I ran into this with the MXP port.

Re: CSE & compare/branch template problem

[Michael Eager]

Joern Rennecke wrote:
> Quoting Michael Eager <eager@eagercon.com>:
> 
>> Hi --
>>
>> I'm working on creating the cstore and cbranch templates
>> for the Xilinx MicroBlaze processor.
> 
> In theory cstore / cbranch should be the future, but the last time I tried
> to use them, they didn't quite work right yet, particularily if you have
> an incomplete comparison set.  Because of delays with the Copyright
> assignment, fixing the middle-end was not an efficient option, so I went
> for the old hack with separate compare and condjump / cstore patterns.

Thanks.  That's good to know.

> 
>> Somehow, CSE is deciding that reg 137 is equal to zero and
>> translates insn 99 to
>>
>> (insn 99 98 100 3 .../strchr.c:93
>>   (set (reg:CC 249)
>>        (eq:CC
>>            (reg:SI 247)
>>            (reg/v:SI 137 [ c+-3 ]))) 71
> 
> That is correct; after the jump_insn 94 is not taken, you can conclude
> that reg 137 is zero.

Urk.  After stepping through the code and seeing that the hw reg
allocated to reg 137 was non-zero, I looked at the insns and
(incorrectly) decided that CSE had been wrong.  I think I
managed to confuse myself since reg 246 is 1 if reg 137 is 0.

This means that the instruction generated for the compare or
the branch is incorrect.  That's easier than chasing after a
non-existent CSE bug.

Thanks for pointing this out.


>>   Are there other targets which save comparison results
>>   in registers and require the condition?
> 
> Yes.  One example is SH64.
> 
>>   Any suggestions on better ways to model the MicroBlaze
>>   comparison operations?
>>
>>   Are there some restriction on using eq/ne/lt/... the
>>   way I am?
>>
>>   Any suggestions on how to fix the problem in CSE?
> 
> There are some problems if comparisons can't be reversed.
> I think it's a bug in the generic code, but for any given port, it's
> easier - and gives better code - to make sure that all conditions can
> be reversed, rather than fix the generic code.
> I ran into this with the MXP port.

Thanks!

-- 
Michael Eager	 eager@eagercon.com
1960 Park Blvd., Palo Alto, CA 94306  650-325-8077

Re: CSE & compare/branch template problem

[Paolo Bonzini]

On 12/19/2009 01:07 AM, Joern Rennecke wrote:
> Quoting Michael Eager <eager@eagercon.com>:
>
>> Hi --
>>
>> I'm working on creating the cstore and cbranch templates
>> for the Xilinx MicroBlaze processor.
>
> In theory cstore / cbranch should be the future, but the last time I tried
> to use them, they didn't quite work right yet, particularily if you have
> an incomplete comparison set. Because of delays with the Copyright
> assignment, fixing the middle-end was not an efficient option, so I went
> for the old hack with separate compare and condjump / cstore patterns.

Well, 4.5 has only cbranch/cstore. :-)

 >   (set (reg:CC rD) (eq:CC (reg:SI rA) (reg:SI rB))
 >
 > followed by a branch:
 >
 >   (if_then_else
 >      (eq:CC (reg:CC rD) (const_int 0))
 >      (label_ref xx)
 >      (pc)))

If there is only one instruction for comparison, the first insn should 
be (set (reg:CC rD) (compare:CC (reg:SI rA) (reg:SI rB))).  If there are 
many, having eq:CC in the first insn is fine but then the second should 
be (ne:CC (reg:CC rD) (const_int 0))

Now you have (eq:CC (eq:CC (reg:SI rA) (reg:SI rB)) (const_int 0)), 
which is exactly the opposite of what you mean, because (eq <condition> 
0) means "check if the condition is false" and hence "reverse the 
condition".  So CSE sees a reversed condition, thinks the loop must 
execute while the variable _is_ zero, and propagates zero inside the loop.

Note that the cmpMM+bXX+sXX -> cbranchMM4/cstoreMM4 conversion usually 
can be done in a completely mechanical fashion.  It is usually a matter 
of defining the right predicates for the operator operand of 
cbranch/cstore (operand zero and one, respectively), especially if (as 
most ports did) the MicroBlaze port's cmpMM patterns only saved their 
operands.

Paolo

Re: CSE & compare/branch template problem

[Richard Henderson]

On 12/18/2009 03:18 PM, Michael Eager wrote:
> MicroBlaze has a bit unusual compare and branch architecture.
> There are no condition flags; comparison results are stored in
> a result register.

This like Alpha or MIPS then.

> There's one branch instruction, which compares a register
> with zero and branches based on condition (eq, ne, lt, gt, etc.).

Yep,

> There are a number of different instructions which can be used
> for comparisons. Regular instructions like sub or xor can be
> used in some cases. There are also cmp/cmpu instructions which
> do a modified subtraction of signed and unsigned integers.

Yep,

> For comparisons, I'm generating insns like:
>
> (set (reg:CC rD) (eq:CC (reg:SI rA) (reg:SI rB))
>
> followed by a branch:
>
> (if_then_else
> (eq:CC (reg:CC rD) (const_int 0))
> (label_ref xx)
> (pc)))

There's no need to use CCmode; SImode will work just fine.

Your cmp instruction is a bit weird, in that only bit 0 is
set for the comparison, and the rest of the register still
contains the result of the subtraction.  You may well want
to model this with

(define_insn_and_split "*cmp"
   [(set (match_operand:SI 0 "register_operand" "=r")
         (lt:SI (match_operand:SI 1 "register_operand" "r")
                (match_operand:SI 2 "register_operand" "r")))]
   ""
   "cmp %0,%1,%2\;andi $0,$0,1"
   ""
   [(set (match_dup 0)
         (unspec:SI [(match_dup 1) (match_dup 2)] UNSPEC_CMP))
    (set (match_dup 0) (and:SI (match_dup 0) (const_int 1)))]
   "")

If your cmp instruction cleared bits 31:1, then this would be
exactly the MIPS SLT instruction.

I think all your problems will just Go Away if you stop using
CCmode, and model your branch instructions like MIPS does.


r~

Re: CSE & compare/branch template problem

[Paolo Bonzini]

On 12/21/2009 08:10 PM, Richard Henderson wrote:
> (define_insn_and_split "*cmp"
>    [(set (match_operand:SI 0 "register_operand" "=r")
>          (lt:SI (match_operand:SI 1 "register_operand" "r")
>                 (match_operand:SI 2 "register_operand" "r")))]
>    ""
>    "cmp %0,%1,%2\;andi $0,$0,1"
>    ""
>    [(set (match_dup 0)
>          (unspec:SI [(match_dup 1) (match_dup 2)] UNSPEC_CMP))
>     (set (match_dup 0) (and:SI (match_dup 0) (const_int 1)))]
>    "")

It's actually the MSB that is affected, and the entire register is set 
to zero if a == b.  Basically cmp/cmpu prepare rD so that a signed 
compare-with-zero-and-branch will do the requested conditional branch.

So, branches are easy, but cstores are tricky.  Something like this 
should work; indeed you do not need any CC mode:

;; cbranch expander, possibly use cmp/cmpu to make operand 0 into a
;; signed comparison with zero
(define_expand "cbranchsi4"
     [(set (pc)
           (if_then_else
             (match_operator 0 "ordered_comparison_operator"
              [(match_operand:SI 1 "register_operand" "")
               (match_operand:SI 2 "register_operand_or_0" "")])
             (label_ref (match_operand 3 ""))
             (pc)))]
     "enum rtx_code signed =
        signed_condition (GET_CODE (operands[0]));
      if (operands[2] != const0_rtx || signed != GET_CODE (operands[0]))
        {
          rtx reg = gen_reg_rtx (SImode);
          if (signed != GET_CODE (operands[0]))
            emit_insn (gen_cmpusi (reg, operands[1], operands[2]));
          else
            emit_insn (gen_cmpsi (reg, operands[1], operands[2]));

          operands[1] = reg;
          operands[2] = const0_rtx;
          operands[0] = gen_rtx_fmt_ee (signed, SImode, reg, const0_rtx);
        }")

;; branch instructions do a signed comparison with 0 (needs
;; a predicate signed_comparison_operator), you could also
;; write a pattern for indirect conditional branches
(define_insn "*branch"
     [(set (pc)
           (if_then_else
             (match_operator 0 "signed_comparison_operator"
              [(match_operand:SI 1 "register_operand" "")
               (const_int 0)])
             (label_ref (match_operand 2 ""))
             (pc)))]
     ""
     "b%0i %1,%2"
     "")

;; unspecs for cmp/cmpu
(define_insn "cmpsi"
     [(set (match_operand:SI 0 "register_operand" "=r")
           (unspec
             [(match_operand:SI 1 "register_operand" "r")
              (match_operand:SI 2 "register_operand" "r")] UNSPEC_CMP))]
     ""
     "cmp %0,%1,%2"
     "")

(define_insn "cmpusi"
     [(set (match_operand:SI 0 "register_operand" "=r")
           (unspec
             [(match_operand:SI 1 "register_operand" "r")
              (match_operand:SI 2 "register_operand" "r")] UNSPEC_CMPU))]
     ""
     "cmp %0,%1,%2"
     "")

;; these are used for cstore tricks when the old contents of rD are
;; significant
(define_insn "*cmpsi4"
     [(set (match_operand:SI 0 "register_operand" "+r")
           (unspec
             [(match_dup 0)
              (match_operand:SI 1 "register_operand" "r")
              (match_operand:SI 2 "register_operand" "r")] UNSPEC_CMP))]
     ""
     "cmp %0,%1,%2"
     "")

(define_insn "*cmpusi4"
     [(set (match_operand:SI 0 "register_operand" "+r")
           (unspec
             [(match_dup 0)
              (match_operand:SI 1 "register_operand" "r")
              (match_operand:SI 2 "register_operand" "r")] UNSPEC_CMPU))]
     ""
     "cmp %0,%1,%2"
     "")

;; some cstore patterns: cstoresi4 should canonicalize lt/ltu to gt/gtu,
;; as should CANONICALIZE_COMPARISON.
;;
;; common code takes care of ge/geu/le/leu as long as the rtx_costs say
;; it's profitable.  Same for a != b for nonzero b.
;;
;;   ...
;;   if (GET_CODE (operands[1]) == LT || GET_CODE (operands[1]) == LTU)
;;     {
;;       operands[1] =
;;         gen_rtx_fmt_ee (swap_condition (GET_CODE (operands[1])),
;;                         SImode, operands[3], operands[2]);
;;       operands[2] = XEXP (operands[1], 0);
;;       operands[3] = XEXP (operands[1], 1);
;;     }
;;   else if (GET_CODE (operands[1]) == NE && operands[3] != const0_rtx)
;;     FAIL;
;;

;; preset rD to 1 to implement a == b
(define_insn_and_split "eqsi3"
     [(set (match_operand:SI 0 "register_operand" "=&r")
             (eq:SI (match_operand:SI 1 "register_operand" "r")
                    (match_operand:SI 2 "register_operand" "r")))]
     ""
     ""
     ""
     [(set (match_dup 0) (const_int 1))
      (set (match_dup 0) (unspec:SI [(match_dup 0)
                                     (match_dup 1) (match_dup 2)]
                                    UNSPEC_CMP))
      (set (match_dup 0) (and:SI (match_dup 0) (const_int 1))]
     "")

;; use a GTU 0 to implement a != 0.  but cmpu does not accept immediates
(define_insn_and_split "nesi3"
     [(set (match_operand:SI 0 "register_operand" "=&r")
             (ne:SI (match_operand:SI 1 "register_operand" "r")
                    (const_int 0)))]
     ""
     ""
     ""
     [(set (match_dup 0) (const_int 0))
      (set (match_dup 0) (unspec:SI [(match_dup 1) (match_dup 0)]
                                    UNSPEC_CMPU))
      (set (match_dup 0) (lshiftrt:SI (match_dup 0) (const_int 31))]
     "")

;; these are easy at least :-)
(define_insn_and_split "gtsi3"
     [(set (match_operand:SI 0 "register_operand" "=r")
             (gt:SI (match_operand:SI 1 "register_operand" "r")
                    (match_operand:SI 2 "register_operand" "r")))]
     ""
     ""
     ""
     [(set (match_dup 0) (unspec:SI [(const_int 0)
                                     (match_dup 1) (match_dup 2)]
                                    UNSPEC_CMP))
      (set (match_dup 0) (lshiftrt:SI (match_dup 0) (const_int 31))]
     "")

(define_insn_and_split "gtusi3"
     [(set (match_operand:SI 0 "register_operand" "=r")
             (gtu:SI (match_operand:SI 1 "register_operand" "r")
                     (match_operand:SI 2 "register_operand" "r")))]
     ""
     ""
     ""
     [(set (match_dup 0) (unspec:SI [(const_int 0)
                                     (match_dup 1) (match_dup 2)]
                                    UNSPEC_CMPU))
      (set (match_dup 0) (lshiftrt:SI (match_dup 0) (const_int 31))]
     "")

;; some sample combiner patterns

(define_insn_and_split "*negnesi3"
     [(set (match_operand:SI 0 "register_operand" "=&r")
            (neg:SI
             (ne:SI (match_operand:SI 1 "register_operand" "r")
                    (const_int 0))))]
     ""
     ""
     ""
     [(set (match_dup 0) (const_int 0))
      (set (match_dup 0) (unspec:SI [(match_dup 1) (match_dup 0)]
                                    UNSPEC_CMPU))
      (set (match_dup 0) (ashiftrt:SI (match_dup 0) (const_int 31))]
     "")

(define_insn_and_split "*neggtsi3"
     [(set (match_operand:SI 0 "register_operand" "=r")
            (neg:SI
             (gt:SI (match_operand:SI 1 "register_operand" "r")
                    (match_operand:SI 2 "register_operand" "r"))))]
     ""
     ""
     ""
     [(set (match_dup 0) (unspec:SI [(const_int 0)
                                     (match_dup 1) (match_dup 2)]
                                    UNSPEC_CMP))
      (set (match_dup 0) (ashiftrt:SI (match_dup 0) (const_int 31))]
     "")

(define_insn_and_split "*neggtusi3"
     [(set (match_operand:SI 0 "register_operand" "=r")
            (neg:SI
             (gtu:SI (match_operand:SI 1 "register_operand" "r")
                     (match_operand:SI 2 "register_operand" "r"))))]
     ""
     ""
     ""
     [(set (match_dup 0) (unspec:SI [(const_int 0)
                                     (match_dup 1) (match_dup 2)]
                                    UNSPEC_CMPU))
      (set (match_dup 0) (ashiftrt:SI (match_dup 0) (const_int 31))]
     "")

Paolo

Re: CSE & compare/branch template problem

[Michael Eager]

Paolo Bonzini wrote:
> On 12/21/2009 08:10 PM, Richard Henderson wrote:
>> (define_insn_and_split "*cmp"
>>    [(set (match_operand:SI 0 "register_operand" "=r")
>>          (lt:SI (match_operand:SI 1 "register_operand" "r")
>>                 (match_operand:SI 2 "register_operand" "r")))]
>>    ""
>>    "cmp %0,%1,%2\;andi $0,$0,1"
>>    ""
>>    [(set (match_dup 0)
>>          (unspec:SI [(match_dup 1) (match_dup 2)] UNSPEC_CMP))
>>     (set (match_dup 0) (and:SI (match_dup 0) (const_int 1)))]
>>    "")
> 
> It's actually the MSB that is affected, and the entire register is set 
> to zero if a == b.  Basically cmp/cmpu prepare rD so that a signed 
> compare-with-zero-and-branch will do the requested conditional branch.
> 
> So, branches are easy, but cstores are tricky.  Something like this 
> should work; indeed you do not need any CC mode:

Thanks.  I'll take a look at this.

There are some other quirks with the MicroBlaze architecture.
The cmp/cmpu instructions only take a register.  Other instructions
which can be used for equality or signed comparisons (xor or sub)
can take an immediate operand.  I'll see how they can be added.

-- 
Michael Eager	 eager@eagercon.com
1960 Park Blvd., Palo Alto, CA 94306  650-325-8077

Re: CSE & compare/branch template problem

[Paolo Bonzini]

> There are some other quirks with the MicroBlaze architecture.
> The cmp/cmpu instructions only take a register.  Other instructions
> which can be used for equality or signed comparisons (xor or sub)
> can take an immediate operand.  I'll see how they can be added.

You can probably convince combine to merge the compare and branch
insns into a single pattern, that is immediately split to a
xor+branch-if-equal.

Paolo