[PATCH] vrp: fold ffs to ctz

Richard Guenther richard.guenther@gmail.com
Mon Jun 4 09:31:00 GMT 2012


On Sat, Jun 2, 2012 at 1:36 PM, Paolo Bonzini <paolo.bonzini@gmail.com> wrote:
> The ffs function can be converted to ctz if the operand is known not
> to be zero, as is the case for example in
>
>    while (x != 0) {
>       bit = ffs(x) - 1;
>       ...
>       x &= ~(1 << bit);
>    }
>
> CSE can already do this on x86, but the attached patch implements this
> folding in VRP in a target-independent way.
>
> Bootstrapped/regtested x86_64-pc-linux-gnu, ok?

+        val = compare_range_with_value (NE_EXPR, vr, integer_zero_node, &sop);
+        if (!val || !integer_onep (val))
+          return false;

please add a value_range_nonzero_p helper alongside value_range_nonnegative_p.

+        fndecl = builtin_decl_implicit (target_builtin_code);
+        lhs = gimple_call_lhs (stmt);
+        gcc_assert (TREE_TYPE (TREE_TYPE (fndecl)) == TREE_TYPE (lhs));

eh, if you care to check this please fail instead of ICEing ...

Do we always have CTZ if we have FFS?  Can't there be a target that
implements FFS as opcode but not CTZ, so you'd slow down things?
Thus, should the transform be conditonal on target support for CTZ
or no target support for FFS?
Please add a comment to the code as to what transform you are doing
here.

+        /* Convert argument type.  */
+        argtype = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
+        tem = create_tmp_reg (argtype, NULL);
+        newop = gimple_build_assign_with_ops (NOP_EXPR, tem, op0, NULL_TREE);
+        tem = make_ssa_name (tem, newop);
+        gimple_assign_set_lhs (newop, tem);
+        gsi_insert_before (gsi, newop, GSI_SAME_STMT);

why is that necessary?  Can you at least wrap it inside a

  if (!useless_type_conversion_p (argtype, TREE_TYPE (op0)))

?

+        /* Modify call in place.  */
+        tem = create_tmp_reg (TREE_TYPE (lhs), NULL);
+        tem = make_ssa_name (tem, stmt);
+        gimple_call_set_lhs (stmt, tem);

you should be able to re-use SSA_NAME_VAR of the existing lhs
avoiding the create_tmp_reg.

+        /* Sum one to the result.  */
+        newop = gimple_build_assign_with_ops (PLUS_EXPR, lhs, tem,
+                                              fold_convert (TREE_TYPE (lhs),
+                                                            integer_one_node));

build_one_cst (TREE_TYPE (lhs)), or build_int_cst (TREE_TYPE (lhs), 1).

Otherwise looks ok to me.

Thanks,
Richard.


>
> Paolo



More information about the Gcc-patches mailing list