decrement & branch isns

[Nathan Sidwell <nathan at codesourcery dot com>]

Hi,
The next bit of this port (on the 3.4 branch) I've got stuck on is
recognizing decrement & branch instruction possibilities.  The actual
instruction I have to play with looks like this bit of rtl,

  [(set (pc)
	(if_then_else (ne:SI (match_operand:SI 0 "register_operand" "+r,m")
			     (const_int 0))
	  	      (label_ref (match_operand 1 "" "")) (pc)))
   (set (match_dup 0) (plus:SI (match_dup 0) (const_int -1)))]

I.e it does the test on the old value of the loop variable, and always
decrements it in parallel. Hence on exit, the loop variable will be -1.
This differs from the m68k decrement_and_branch_until_zero pattern, which
tests the new value of the loop variable.

I've had some success with using a doloop_end expander, but that
only allows single exit loops. If I compile the following test case
  unsigned Baz (unsigned j, int *ptr)
  {
    unsigned ix;

    for (ix = j; ix--;)
      if (!ptr[ix])
        return ix;
    return -1u;
  }
and then make the multiple-exit and contains calls tests in doloop.c
conditional on HAVE_doloop_begin (which I presume will always be defined
on that kind of hardware with really hardware iteration variables), then
this too is optimized, but doesn't recogize that the loop control variable
and ix are decremented in lock step.  What is generated is,

        mov       reg5,reg4  # reg4 contains ix
.L8:
        load      reg6,reg2  # reg2 contains (biased) ptr
        add       reg2,reg2,4 # decrement ptr
        branchz   reg6,.L10
        sub       reg4,reg4,1  # here is the unneeded decrement of ix
        branchdec reg5,.L8  # and here is the branch and dec of reg5

I also had problems with the loop unroller generating incorrect
code. I had some success with the attached patch, which as you can
see adjusts the delta based on whether the end-loop test biases the
loop variable's value.  However, this wasn't successful in all cases
but I've not investigated those further (the remaining failure
looks like bad liveness analysis).

nathan

--
Nathan Sidwell    ::   http://www.codesourcery.com   ::     CodeSourcery LLC
nathan@codesourcery.com    ::     http://www.planetfall.pwp.blueyonder.co.uk

Index: loop-unroll.c
===================================================================
RCS file: /home/icera/Repository/gnu/gcc/loop-unroll.c,v
retrieving revision 1.1.1.1
diff -c -3 -p -r1.1.1.1 loop-unroll.c
*** loop-unroll.c	29 Apr 2004 11:47:30 -0000	1.1.1.1
--- loop-unroll.c	9 Jun 2004 11:50:17 -0000
*************** Software Foundation, 59 Temple Place - S
*** 30,35 ****
--- 30,36 ----
  #include "params.h"
  #include "output.h"
  #include "expr.h"
+ #include "loop.h"
  /* We need to use the macro exact_log2. */
  #include "toplev.h"
  
*************** unroll_loop_runtime_iterations (struct l
*** 871,876 ****
--- 872,879 ----
      { 
        rtx count, count2, count_unroll_mod;
        int count_unroll;
+       int incr = 1;
+       rtx cond;
  
        /* start_sequence (); */
                    
*************** unroll_loop_runtime_iterations (struct l
*** 885,892 ****
  				  count, count_unroll_mod,
  				  0, 0, OPTAB_LIB_WIDEN);
  
        count2 = expand_simple_binop (GET_MODE (desc->var), PLUS,
! 				     count, GEN_INT (2),
  				     0, 0, OPTAB_LIB_WIDEN);
       
        emit_move_insn (desc->var, count2);
--- 888,900 ----
  				  count, count_unroll_mod,
  				  0, 0, OPTAB_LIB_WIDEN);
  
+       cond = doloop_condition_get (PATTERN (BB_END (desc->out_edge->src)));
+       cond = XEXP (cond, 0);
+       if (GET_CODE (cond) == PLUS)
+ 	incr -= INTVAL (XEXP (cond, 1));
+ 
        count2 = expand_simple_binop (GET_MODE (desc->var), PLUS,
! 				     count, GEN_INT (incr),
  				     0, 0, OPTAB_LIB_WIDEN);
       
        emit_move_insn (desc->var, count2);