RFA: check_dbra_loop

[Mark Mitchell <mark at codesourcery dot com>]

Recently, I posted a patch to fix an invalid loop reversal.  Testing
revealed that this patch caused a new failure on SPARC.  Namely,
990604-1.c is now miscompiled with -Os.  The loop in question is:

    i = 0
    do {
      b = i;
      i++;
    } while (i < 10);

I don't think my patch is directly to blame; there seems to be an
underlying problem.  Here is the loop we have with -Os:

  (note 18 16 37 NOTE_INSN_LOOP_BEG 0)

  (code_label 37 18 46 7 "" "" [1 uses])

  (note 46 37 23 [bb 1] NOTE_INSN_BASIC_BLOCK 0)

  (insn 23 46 26 (set (reg/f:SI 111)
	  (reg/f:SI 108)) 51 {*movsi_insn} (nil)
      (expr_list:REG_EQUAL (high:SI (symbol_ref:SI ("b")))
	  (nil)))

  (insn 26 23 29 (set (mem/f:SI (lo_sum:SI (reg/f:SI 111)
		  (symbol_ref:SI ("b"))) 1)
	  (reg/v:SI 106)) 51 {*movsi_insn} (nil)
      (nil))

  (insn 29 26 30 (set (reg/v:SI 106)
	  (plus:SI (reg/v:SI 106)
	      (const_int 1 [0x1]))) 177 {*addsi3} (nil)
      (nil))

  (note 30 29 33 NOTE_INSN_LOOP_CONT 0)

  (insn 33 30 34 (set (reg:CC 100 %icc)
	  (compare:CC (reg/v:SI 106)
	      (const_int 9 [0x9]))) 0 {*cmpsi_insn} (nil)
      (nil))

  (jump_insn 34 33 38 (set (pc)
	  (if_then_else (le (reg:CC 100 %icc)
		  (const_int 0 [0x0]))
	      (label_ref 37)
	      (pc))) 37 {*normal_branch} (nil)
      (nil))

  (note 38 34 40 NOTE_INSN_LOOP_END 0)

The problem seems to be with this logic in check_dbra_loop:

  /* If the loop has a single store, and the destination address is
     invariant, then we can't reverse the loop, because this address
     might then have the wrong value at loop exit.
     This would work if the source was invariant also, however, in that
     case, the insn should have been moved out of the loop.  */

  reversible_mem_store
    = (! loop_info->unknown_address_altered
       && ! loop_info->unknown_constant_address_altered
       && ! loop_invariant_p (loop,
			      XEXP (XEXP (loop_info->store_mems, 0),
				    0)));

We're here because of the store to b, which is global.  We're
wondering whether we can still reverse the loop, given this write to a
global variable.  The answer, of course, is that we can't -- if we
reverse the loop, we end up writing the wrong value into b.

However, we set reversible_mem_store to 1 here because we're not smart
enough to figure out that:

  (lo_sum:SI (reg/f:SI 111)
             (symbol_ref:SI ("b"))) 1)

is loop-invariant.  (We *do* figure this out with -O2, because we move
the set of (reg/f:SI 111) out of the loop; that's why this problem
only shows up with -Os.)

Now, it seems wrong on principle to me to try to ever base an
optimization on loop_invariant_p *not* holding, since that function is
conservative.  We never know for sure that something is *not* loop
invariant; we only know that we cannot prove that it *is* loop
invariant.

(Furthermore, reversing a loop (in the naive way) seems bogus when
there is *any* write to global memory because a program can tell the
difference.  For example, consider a threaded program, where another
thread is looking at the global continuously.  It should see the
numbers count upwards, not downwards.  We could still legally reverse
the loop by moving the write to the global outside the loop, after the
rest of the loop is complete; the threaded program can't depend on
actually seeing all the increments, so we can replace a series of
increments with one single write.)

So, I think this reversible_mem_store stuff is bogus, and that we are
not currently smart enough to reverse any loop that writes to memory.

Thoughts?

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com