RE: A problem about loop store motion

["Jiangning Liu" <jiangning dot liu at arm dot com>]

> -----Original Message-----
> From: gcc-owner@gcc.gnu.org [mailto:gcc-owner@gcc.gnu.org] On Behalf Of
> Jiangning Liu
> Sent: Friday, February 17, 2012 5:53 PM
> To: gcc@gcc.gnu.org
> Subject: A problem about loop store motion
> 
> Hi,
> 
> For this small test case,
> 
> int *l, *r;
> int test_func(void)
> {
> 	int i;
> 	int direction;
> 	static int pos;
> 
> 	pos = 0;
> 	direction = 1;
> 
> 	for ( i = 0; i <= 400; i++ )
> 	{
> 		if ( direction == 0 )
> 			pos = l[pos];
> 		else
> 			pos = r[pos];
> 
> 		if ( pos == -1 )
> 		{
> 			pos = 0;
> 			direction = !direction;
> 		}
> 	}
> 	return i;
> }
> 
> In middle end, I don't see pos is sunk out of loop by loop store motion.
> Any
> idea?
> 
> The dump after lim is like below, and I expect a SSA symbole xxx_lsm
> could
> be created with this pass.
> 
> ;; Function test_func (test_func, funcdef_no=0, decl_uid=4057,
> cgraph_uid=0)
> 
> 
> Symbols to be put in SSA form
> { .MEM }
> Incremental SSA update started at block: 0
> Number of blocks in CFG: 12
> Number of blocks to update: 11 ( 92%)
> 
> 
> test_func ()
> {
>   int pretmp.14;
>   unsigned int pretmp.13;
>   int prephitmp.12;
>   int pretmp.11;
>   unsigned int pretmp.10;
>   int pretmp.9;
>   int D.4088;
>   static int pos;
>   int direction;
>   int i;
>   _Bool D.4082;
>   int pos.5;
>   int * D.4078;
>   int * r.4;
>   int pos.3;
>   int * D.4074;
>   unsigned int D.4073;
>   unsigned int pos.2;
>   int pos.1;
>   int * l.0;
> 
> <bb 2>:
>   pos = 0;
>   l.0_6 = l;
>   r.4_12 = r;
> 
> <bb 3>:
>   # i_32 = PHI <i_21(11), 0(2)>
>   # direction_37 = PHI <direction_2(11), 1(2)>
>   # prephitmp.12_35 = PHI <pretmp.11_1(11), 0(2)>
>   if (direction_37 == 0)
>     goto <bb 4>;
>   else
>     goto <bb 5>;
> 
> <bb 4>:
>   pos.1_7 = prephitmp.12_35;
>   pos.2_8 = (unsigned int) pos.1_7;
>   D.4073_9 = pos.2_8 * 4;
>   D.4074_10 = l.0_6 + D.4073_9;
>   pos.3_11 = *D.4074_10;
>   pos = pos.3_11;
>   goto <bb 6>;
> 
> <bb 5>:
>   pos.1_13 = prephitmp.12_35;
>   pos.2_14 = (unsigned int) pos.1_13;
>   D.4073_15 = pos.2_14 * 4;
>   D.4078_16 = r.4_12 + D.4073_15;
>   pos.5_17 = *D.4078_16;
>   pos = pos.5_17;
> 
> <bb 6>:
>   # prephitmp.12_31 = PHI <pos.3_11(4), pos.5_17(5)>
>   pos.1_18 = prephitmp.12_31;
>   if (pos.1_18 == -1)
>     goto <bb 7>;
>   else
>     goto <bb 10>;
> 
> <bb 10>:
>   goto <bb 8>;
> 
> <bb 7>:
>   pos = 0;
>   D.4088_36 = direction_37 ^ 1;
>   direction_20 = D.4088_36 & 1;
> 
> <bb 8>:
>   # direction_2 = PHI <direction_37(10), direction_20(7)>
>   i_21 = i_32 + 1;
>   if (i_21 != 401)
>     goto <bb 11>;
>   else
>     goto <bb 9>;
> 
> <bb 11>:
>   pretmp.11_1 = pos;

Hi,

pos in RHS seems to be transformed to MEM[&pos] by the code in
tree-ssa-sccvn.c like below,

	case VAR_DECL:
	  if (DECL_HARD_REGISTER (ref))
	    {
	      temp.op0 = ref;
	      break;
	    }
	  /* Fallthru.  */
	case PARM_DECL:
	case CONST_DECL:
	case RESULT_DECL:
	  /* Canonicalize decls to MEM[&decl] which is what we end up with
	     when valueizing MEM[ptr] with ptr = &decl.  */
	  temp.opcode = MEM_REF;
	  temp.op0 = build_int_cst (build_pointer_type (TREE_TYPE (ref)),
0);
	  temp.off = 0;
	  VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
	  temp.opcode = ADDR_EXPR;
	  temp.op0 = build_fold_addr_expr (ref);
	  temp.type = TREE_TYPE (temp.op0);
	  temp.off = -1;
	  break;

But the LHS doesn't have this kind of transformation on gimple,

So the code below in gather_mem_refs_stmt of tree-ssa-loop-im.c can't find
MEM[&pos] is just pos,

  hash = iterative_hash_expr (*mem, 0);
  slot = htab_find_slot_with_hash (memory_accesses.refs, *mem, hash,
INSERT);

Finally pos is set to be dependent on pretmp.11_1 at code below in
ref_indep_loop_p_1, and then loop store motion fails to find pos.

  EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
    {
      aref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
      if (!refs_independent_p (ref, aref))
	{
	  ret = false;
	  record_indep_loop (loop, aref, false);
	  break;
	}
    }

Should we fix this problem by enhancing iterative_hash_expr, or we should
use MEM[&pos] to describe pos at all?

Any hints? I need to understand why we have to use MEM[&pos] to describe
pos? This looks strange to me.

BTW, this bug caused significant regression for an important benchmark.

Thanks,
-Jiangning

>   goto <bb 3>;
> 
> <bb 9>:
>   return 401;
> 
> }
> 
> Thanks,
> -Jiangning
> 
> 
>