Patchwork [rtl-optimization] : Fix post-reload compare elimination pre-pass

login
register
mail settings
Submitter Uros Bizjak
Date Feb. 9, 2012, 11:47 p.m.
Message ID <CAFULd4b2xTuHyQNxpdPjnxmg0OZfhmzWLAwrJskCNCZEULt8gg@mail.gmail.com>
Download mbox | patch
Permalink /patch/140453/
State New
Headers show

Comments

Uros Bizjak - Feb. 9, 2012, 11:47 p.m.
Hello!

I am trying to enable post-reload compare elimination pass on x86, and
I discovered a problem in the way redundant compares are eliminated.
The problem lies in the assumption that:

  (1) All comparison patterns are represented as

       [(set (reg:CC) (compare:CC (reg) (immediate)))]

which is not true for x86 or any target which exposes FLAGS_REG early
and defines SELECT_CC_MODE.

Following testcase:

--cut here--
int test (int a, int b)
{
 int lt = a + b < 0;
 int eq = a + b == 0;
 if (lt)
   return 1;
 return eq;
}
--cut here--

compiles to the following dump before entering post-reload compare
elimination pass:

(insn 8 4 9 2 (parallel [
           (set (reg:SI 4 si [orig:60 D.1710 ] [60])
               (plus:SI (reg/v:SI 5 di [orig:63 a ] [63])
                   (reg/v:SI 4 si [orig:64 b ] [64])))
           (clobber (reg:CC 17 flags))
       ]) cmp.c:3 253 {*addsi_1}
    (nil))

(insn 9 8 10 2 (set (reg:CCZ 17 flags)
       (compare:CCZ (reg:SI 4 si [orig:60 D.1710 ] [60])
           (const_int 0 [0]))) cmp.c:4 2 {*cmpsi_ccno_1}
    (nil))

(note 10 9 33 2 NOTE_INSN_DELETED)

(insn 33 10 34 2 (set (reg:QI 1 dx [65])
       (eq:QI (reg:CCZ 17 flags)
           (const_int 0 [0]))) cmp.c:4 595 {*setcc_qi}
    (nil))

(insn 34 33 30 2 (set (reg:SI 1 dx [65])
       (zero_extend:SI (reg:QI 1 dx [65]))) cmp.c:4 123
{*zero_extendqisi2_movzbl}
    (nil))

(insn 30 34 29 2 (set (reg/v:SI 0 ax [orig:59 eq ] [59])
       (const_int 1 [0x1])) cmp.c:6 64 {*movsi_internal}
    (expr_list:REG_EQUAL (const_int 1 [0x1])
       (nil)))

(insn 29 30 31 2 (set (reg:CCGOC 17 flags)
       (compare:CCGOC (reg:SI 4 si [orig:60 D.1710 ] [60])
           (const_int 0 [0]))) cmp.c:6 2 {*cmpsi_ccno_1}
    (nil))

(insn 31 29 25 2 (set (reg/v:SI 0 ax [orig:59 eq ] [59])
       (if_then_else:SI (ge (reg:CCGOC 17 flags)
               (const_int 0 [0]))
           (reg:SI 1 dx [65])
           (reg/v:SI 0 ax [orig:59 eq ] [59]))) cmp.c:6 903 {*movsicc_noc}
    (nil))

The redundant-compare elimination pre-pass blindly eliminates (insn
29) from the sequence. The elimination is done without updating the
compare mode in (insn 9)! The correct approach would be to also update
the compare mode of (insn 9) to the mode of
targetm.cc_modes_compatible target hook, which in the case abowe would
be (CCZmode, CCGOCmode) -> CCGOCmode.

Attached patch fixes this problem by checking for mode compatibility
of redundant compare with previous compare before elimination, and
sets the mode of previous compare to mode, compatible with both
compares.

2012-02-10  Uros Bizjak  <ubizjak@gmail.com>

	* compare-elim.c (find_comparisons_in_bb): Eliminate only compares
	having mode compatible with the mode of previous compare.  Substitute
	compare mode of previous compare with the mode, compatible
	with eliminated and previous compare.

Patch was bootstrapped and regression tested with additional x86
specific patch that enables post-reload compare eliminations on
x86_64-pc-linux-gnu {,-m32}. The complete patch is attached to this
message.

Is RTL optimisation part of the patch OK for mainline SVN and 4.6 ?

Uros.
Richard Henderson - Feb. 11, 2012, 12:26 a.m.
On 02/09/2012 03:47 PM, Uros Bizjak wrote:
> 2012-02-10  Uros Bizjak  <ubizjak@gmail.com>
> 
> 	* compare-elim.c (find_comparisons_in_bb): Eliminate only compares
> 	having mode compatible with the mode of previous compare.  Substitute
> 	compare mode of previous compare with the mode, compatible
> 	with eliminated and previous compare.

This patch is ok for 4.8.

For 4.6 and 4.7 I would prefer that we simply not eliminate the compare.  I.e.

+	  enum machine_mode src_mode = GET_MODE (src);
+
 	  /* Eliminate a compare that's redundant with the previous.  */
 	  if (last_cmp_valid
+             && src_mode == last_cmp->orig_mode
 	      && rtx_equal_p (last_cmp->in_a, XEXP (src, 0))
 	      && rtx_equal_p (last_cmp->in_b, XEXP (src, 1)))
 	    {
...
-	  last_cmp->orig_mode = GET_MODE (SET_DEST (single_set (insn)));
+	  last_cmp->orig_mode = src_mode;


For 4.6 and 4.7, there are only two extant users of this pass and neither
of them use anything besides CCmode before compare-elim.c does its own
manipulation of the modes later.


r~
Uros Bizjak - Feb. 11, 2012, 3:09 p.m.
On Sat, Feb 11, 2012 at 1:26 AM, Richard Henderson <rth@redhat.com> wrote:
> On 02/09/2012 03:47 PM, Uros Bizjak wrote:
>> 2012-02-10  Uros Bizjak  <ubizjak@gmail.com>
>>
>>       * compare-elim.c (find_comparisons_in_bb): Eliminate only compares
>>       having mode compatible with the mode of previous compare.  Substitute
>>       compare mode of previous compare with the mode, compatible
>>       with eliminated and previous compare.
>
> This patch is ok for 4.8.

Unfortunately, we need to update all uses of flag register with a new,
compatible mode, as well, similar to how compatible mode is handled in
CSE2 pass with cse_condition_code_reg in cse.c

The postreload compare elimination pass should be extended to handle
compare elimination for targets that expose FLAGS_REG early through
SELECT_CC_MODE, taking into account the fact that flags reg can live
past BB boundaries.

Uros.
Richard Henderson - Feb. 11, 2012, 10:01 p.m.
On 02/11/2012 07:09 AM, Uros Bizjak wrote:
> On Sat, Feb 11, 2012 at 1:26 AM, Richard Henderson <rth@redhat.com> wrote:
>> On 02/09/2012 03:47 PM, Uros Bizjak wrote:
>>> 2012-02-10  Uros Bizjak  <ubizjak@gmail.com>
>>>
>>>       * compare-elim.c (find_comparisons_in_bb): Eliminate only compares
>>>       having mode compatible with the mode of previous compare.  Substitute
>>>       compare mode of previous compare with the mode, compatible
>>>       with eliminated and previous compare.
>>
>> This patch is ok for 4.8.
> 
> Unfortunately, we need to update all uses of flag register with a new,
> compatible mode, as well, similar to how compatible mode is handled in
> CSE2 pass with cse_condition_code_reg in cse.c

We do?  What subsequent pass really cares?
What goes wrong leaving things as they are?


r~
Uros Bizjak - Feb. 12, 2012, 8:50 a.m.
On Sat, Feb 11, 2012 at 11:01 PM, Richard Henderson <rth@redhat.com> wrote:

>>>>       * compare-elim.c (find_comparisons_in_bb): Eliminate only compares
>>>>       having mode compatible with the mode of previous compare.  Substitute
>>>>       compare mode of previous compare with the mode, compatible
>>>>       with eliminated and previous compare.
>>>
>>> This patch is ok for 4.8.
>>
>> Unfortunately, we need to update all uses of flag register with a new,
>> compatible mode, as well, similar to how compatible mode is handled in
>> CSE2 pass with cse_condition_code_reg in cse.c
>
> We do?  What subsequent pass really cares?

Yes, please see an example in  [1] how CSE2 pass handles this.

I don't know if this is necessary, but when we merge arithmetic insn
with compare, we _do_ update the flags users, in the same way as CSE2
pass.

> What goes wrong leaving things as they are?

x86 tolerates wrong modes in flags users, so as far as x86 is
concerned, this is allowed. But I don't know if wrong, although
compatible modes, should be generated from a generic pass.

[1] http://gcc.gnu.org/ml/gcc-patches/2012-02/msg00547.htm

Uros.

Patch

Index: compare-elim.c
===================================================================
--- compare-elim.c	(revision 184067)
+++ compare-elim.c	(working copy)
@@ -297,11 +297,36 @@  find_comparisons_in_bb (struct dom_walk_data *data
       src = conforming_compare (insn);
       if (src)
 	{
+	  enum machine_mode src_mode = GET_MODE (src);
+
 	  /* Eliminate a compare that's redundant with the previous.  */
 	  if (last_cmp_valid
 	      && rtx_equal_p (last_cmp->in_a, XEXP (src, 0))
 	      && rtx_equal_p (last_cmp->in_b, XEXP (src, 1)))
 	    {
+	      rtx flags, x;
+	      enum machine_mode new_mode
+		= targetm.cc_modes_compatible (last_cmp->orig_mode, src_mode);
+
+	      /* New mode is incompatible with the previous compare mode.  */
+	      if (new_mode == VOIDmode)
+		continue;
+
+	      if (new_mode != last_cmp->orig_mode)
+		{
+		  flags = gen_rtx_REG (src_mode, targetm.flags_regnum);
+
+		  /* Generate new comparison for substitution.  */
+		  x = gen_rtx_COMPARE (new_mode, XEXP (src, 0), XEXP (src, 1));
+		  x = gen_rtx_SET (VOIDmode, flags, x);
+
+		  if (!validate_change (last_cmp->insn,
+					&PATTERN (last_cmp->insn), x, false))
+		    continue;
+
+		  last_cmp->orig_mode = new_mode;
+		}
+
 	      delete_insn (insn);
 	      continue;
 	    }
@@ -311,7 +336,7 @@  find_comparisons_in_bb (struct dom_walk_data *data
 	  last_cmp->prev_clobber = last_clobber;
 	  last_cmp->in_a = XEXP (src, 0);
 	  last_cmp->in_b = XEXP (src, 1);
-	  last_cmp->orig_mode = GET_MODE (SET_DEST (single_set (insn)));
+	  last_cmp->orig_mode = src_mode;
 	  VEC_safe_push (comparison_struct_p, heap, all_compares, last_cmp);
 
 	  /* It's unusual, but be prepared for comparison patterns that
Index: config/i386/i386.c
===================================================================
--- config/i386/i386.c	(revision 184067)
+++ config/i386/i386.c	(working copy)
@@ -17778,6 +17778,11 @@  ix86_cc_modes_compatible (enum machine_mode m1, en
       || (m1 == CCGOCmode && m2 == CCGCmode))
     return CCGCmode;
 
+  if (m1 == CCZmode && (m2 == CCGCmode || m2 == CCGOCmode))
+    return m2;
+  else if (m2 == CCZmode && (m1 == CCGCmode || m1 == CCGOCmode))
+    return m1;
+
   switch (m1)
     {
     default:
@@ -38685,6 +38690,9 @@  ix86_autovectorize_vector_sizes (void)
 #undef TARGET_EXPAND_TO_RTL_HOOK
 #define TARGET_EXPAND_TO_RTL_HOOK ix86_maybe_switch_abi
 
+#undef TARGET_FLAGS_REGNUM
+#define TARGET_FLAGS_REGNUM FLAGS_REG
+
 #undef TARGET_LEGITIMATE_ADDRESS_P
 #define TARGET_LEGITIMATE_ADDRESS_P ix86_legitimate_address_p