cse vs libcalls

[Jeffrey A Law]

Consider a target without hardware floating point and this sample code.

float f1, f2, f3, f4;

void foo()
{
  f3 = f1 + f2;

  if (f4) return;

  f4 = f1 + f2;
}

Since we don't have hardware floating point, the addition and comparison
operations will be done with libcalls.

Even so, it should be possible for GCC to identify the second addition as a
common subexpression and eliminate the second call to addsf3.  But that is
not happening.

This is clearly a case where CSE should have identified the redundant libcall
and removed it.

At the end of the first libcall sequence we have something like
this:

(insn 25 23 27 (set (reg:SF 37)
        (reg:SF 0 r0)) 256 {*arm_movsf_soft_insn} (nil)
    (insn_list:REG_RETVAL 19 (expr_list:REG_EQUAL (plus:SF (reg:SF 35)
                (reg:SF 36))
            (nil))))

(insn 27 25 30 (set (mem/f:SF (reg:SI 32) 1)
        (reg:SF 37)) 256 {*arm_movsf_soft_insn} (nil)
    (nil))

At the end of processing insn 25 one would expect that we would have an
equivalence class with the following entries:

(plus:SF (reg:SF 35) (reg:SF 36))
(reg:SF 37)

And at the end of insn 27 we should have added (mem/f:SF (reg:SI 32) 1)) to
the equivalence class.

But nooooo.  The only entry in the equivalence class is the (plus ...)
expression.  Neither the (reg:SF 37) nor the (mem:SF ...) are ever added
to the equivalence class.

Thus, when we process the second libcall, we aren't aware of the other 
(cheaper)
forms of the (plus ...) expression.  

In the loop to insert destinations into equivalence classes we have the
following check:

            /* If we didn't put a REG_EQUAL value or a source into the hash
               table, there is no point is recording DEST.  */
            || sets[i].src_elt == 0

Indeed when we process insn 25 sets[i].src_elt == 0 and we do not record the
destination in the equivalence class.  Yes, it's true CSE did not add a
REG_EQUAL note -- the REG_EQUAL note was created when the libcall was first
emitted.

When we started processing insn 25, the equivalence class is empty.  So the
initialization of sets[0].src_elt from a previously computed equivalence
class all set it to zero.  This is normal and expected.

Then we have this hunk of code:

  /* Now enter all non-volatile source expressions in the hash table
     if they are not already present.
     Record their equivalence classes in src_elt.
     This way we can insert the corresponding destinations into
     the same classes even if the actual sources are no longer in them
     (having been invalidated).  */

  if (src_eqv && src_eqv_elt == 0 && sets[0].rtl != 0 && ! src_eqv_volatile
      && ! rtx_equal_p (src_eqv, SET_DEST (sets[0].rtl)))
    {
      register struct table_elt *elt;
      register struct table_elt *classp = sets[0].src_elt;
      rtx dest = SET_DEST (sets[0].rtl);
      enum machine_mode eqvmode = GET_MODE (dest);

      if (GET_CODE (dest) == STRICT_LOW_PART)
        {
          eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
          classp = 0;
        }
      if (insert_regs (src_eqv, classp, 0))
        {
          rehash_using_reg (src_eqv);
          src_eqv_hash = HASH (src_eqv, eqvmode);
        }
      elt = insert (src_eqv, classp, src_eqv_hash, eqvmode);
      elt->in_memory = src_eqv_in_memory;
      elt->in_struct = src_eqv_in_struct;
      src_eqv_elt = elt;

      /* Check to see if src_eqv_elt is the same as a set source which
         does not yet have an elt, and if so set the elt of the set source
         to src_eqv_elt.  */
      for (i = 0; i < n_sets; i++)
        if (sets[i].rtl && sets[i].src_elt == 0
            && rtx_equal_p (SET_SRC (sets[i].rtl), src_eqv))
          sets[i].src_elt = src_eqv_elt;
    }

The call to "insert" will initialize the equivalence class to contain the
(plus ...) expression.

However, since the source of the set (regSF 0) is not the same as src_eqv
(plus (...)) we do not update sets[i].src_elt.   Which in turn leads to
not recording (reg:SF 37) to the equivalence table and so on...

It seems to me that if we only have a single set that src_eqv_elt must 
correspond to the one and only one set source in the insn, regardless of
whether or not sets[i].rtl is the same as src_eqv.

Indeed, changing that final test to look like:

      /* Check to see if src_eqv_elt is the same as a set source which
         does not yet have an elt, and if so set the elt of the set source
         to src_eqv_elt.  */
      for (i = 0; i < n_sets; i++)
        if (n_sets == 1
            || (sets[i].rtl && sets[i].src_elt == 0
                && rtx_equal_p (SET_SRC (sets[i].rtl), src_eqv)))
          sets[i].src_elt = src_eqv_elt;

Results in the equivalence class having all the proper entries and eventually
the removal of the redundant libcall because we know the value it computes
is sitting around in (reg:SF 37).


	* cse.c (cse_insn): If an insn has only a single set, SRC_EQV
	is nonzero and the single set does not have an elt, then assign
	it an elt.

Index: cse.c
===================================================================
RCS file: /cvs/cvsfiles/devo/gcc/cse.c,v
retrieving revision 1.183
diff -c -3 -p -r1.183 cse.c
*** cse.c	1999/11/01 00:21:25	1.183
--- cse.c	1999/11/01 02:10:47
*************** cse_insn (insn, libcall_insn)
*** 5741,5748 ****
  	 does not yet have an elt, and if so set the elt of the set source
  	 to src_eqv_elt.  */
        for (i = 0; i < n_sets; i++)
! 	if (sets[i].rtl && sets[i].src_elt == 0
! 	    && rtx_equal_p (SET_SRC (sets[i].rtl), src_eqv))
  	  sets[i].src_elt = src_eqv_elt;
      }
  
--- 5741,5749 ----
  	 does not yet have an elt, and if so set the elt of the set source
  	 to src_eqv_elt.  */
        for (i = 0; i < n_sets; i++)
! 	if (n_sets == 1
! 	    || (sets[i].rtl && sets[i].src_elt == 0
! 		&& rtx_equal_p (SET_SRC (sets[i].rtl), src_eqv)))
  	  sets[i].src_elt = src_eqv_elt;
      }