Re: A problem about loop store motion

[Richard Guenther <richard dot guenther at gmail dot com>]

On Mon, Feb 20, 2012 at 9:46 AM, Jiangning Liu <jiangning.liu@arm.com> wrote:
>
>
>> -----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?

The MEM form is more "canonical", so the loop SM machinery to detect
equality should be adjusted accordingly.  Alternatively you can teach
PRE insertion to strip off the MEM if possible (though fold_stmt_inplace should
arelady do this if possible).

Richard.

> 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
>>
>>
>>
>
>
>
>