[patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns

[Richard Guenther]

On Wed, Jun 29, 2011 at 3:00 PM, Kai Tietz <ktietz@redhat.com> wrote:
> ----- Original Message -----
> From: "Kai Tietz" <ktietz@redhat.com>
> To: "Richard Guenther" <richard.guenther@gmail.com>
> Cc: gcc-patches@gcc.gnu.org
> Sent: Wednesday, June 29, 2011 1:33:30 PM
> Subject: Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns
>
> ----- Original Message -----
> From: "Richard Guenther" <richard.guenther@gmail.com>
> To: "Kai Tietz" <ktietz@redhat.com>
> Cc: gcc-patches@gcc.gnu.org
> Sent: Wednesday, June 29, 2011 12:14:10 PM
> Subject: Re: [patch tree-optimization]: Do bitwise operator optimizations for X op !X patterns
>
> On Tue, Jun 28, 2011 at 5:05 PM, Kai Tietz <ktietz@redhat.com> wrote:
>> Hello,
>>
>> this patch implements the X op !X patterns within tree-ssa-forwprop.c without using here const-fold routines.  Additionally it does some trivial folding for X op X.  Implementation
>> also looks through [(type)] X op [(type)] !X, if type of X is integral and precision is suitable
>> for operation.
>>
>> ChangeLog gcc/
>>
>> 2011-06-28  Kai Tietz  <ktietz@redhat.com>
>>
>>        * tree-ssa-forwprop.c (operand_precision_onep): New
>>        function.
>>        (find_possible_not_expr_argument): Likewise.
>>        (simplify_bitwise_binary_1): Likewise.
>>        (simplify_bitwise_binary): Use simplify_bitwise_binary_1
>>        for detecting various X op !X optimizations.
>>
>> ChangeLog gcc/testsuite
>>
>> 2011-06-28  Kai Tietz  <ktietz@redhat.com>
>>
>>        * gcc.dg/binop-notand1a.c: New test.
>>        * gcc.dg/binop-notand2a.c: New test.
>>        * gcc.dg/binop-notand3a.c: New test.
>>        * gcc.dg/binop-notand4a.c: New test.
>>        * gcc.dg/binop-notand5a.c: New test.
>>        * gcc.dg/binop-notand6a.c: New test.
>>        * gcc.dg/binop-notor1.c: New test.
>>        * gcc.dg/binop-notor2.c: New test.
>>        * gcc.dg/binop-notxor1.c: New test.
>>        * gcc.dg/binop-notxor2.c: New test.
>>
>> Bootstrapped and regression tested for all languages plus Ada and Obj-C for x86_64-pc-linux-gnu. Ok for apply?
>
> I can't follow the code in find_possible_not_expr_argument or its uses
> at all.  Please try to produce patches that look more obvious in what
> they are doing - don't try to solve every testcase you can come up with
> in a single patch.  Especially don't write functions like
> find_possible_not_expr_argument which seems to have evolved a lot
> after you wrote the overall function comment.
>
> Thanks,
> Richard.
>
>> Regards,
>> Kai
>>
>
> Well, I added some comments to these functions and renamed the find_possible_not_expr_argument function to detect_not_expr_operand, which hits its use better.
> The cause for this function is, that there are more then one variant of expressing a logical-not and all of them are used.
> This routine simply tries to detect different variants used for not. Eg ~X == !X and (X ^ 1) == !X for integral type of X with precision one. For X with integral type, (X == 0) == !X.
>
> The folding for the three different bitwise-operations is pretty easy and it makes sense to implement them at once.  I see here no good point to separate them into different patches.  To separate them might even lead to questions about abstracting some code-pieces out of the main function.
> I didn't added testcases for all variants I am aware now. Just those, which are now handled.
>
> So hope you can read and understand logic of patch better by updated patch.
>
> Regards,
> Kai
>
> I found that in version I've sent there is an unclosed comment.  So here is updated patch, which additionally simplify some code to ease reading.

Ok, I'm going to comment on a few things in the patch.

+/* Checks if expression has type of one-bit precision, or is result of
+   a known boolean expression.  */
+static bool
+operand_precision_onep (tree expr)
+{
+  enum tree_code code;
+  gimple def_stmt;
+
+  do
+    {
+      code = TREE_CODE (expr);
+      if (!INTEGRAL_TYPE_P (TREE_TYPE (expr)))
+	return false;
+      if (TYPE_PRECISION (TREE_TYPE (expr)) == 1)
+	return true;
+      if (code != SSA_NAME)
+	break;
+      def_stmt = SSA_NAME_DEF_STMT (expr);
+      if (!def_stmt || !is_gimple_assign (def_stmt))
+	break;
+      code = gimple_assign_rhs_code (def_stmt);
+      if (!CONVERT_EXPR_CODE_P (code))
+	break;
+      expr = gimple_assign_rhs1 (def_stmt);
+    }
+  while (CONVERT_EXPR_CODE_P (code));
+
+  if (code == TRUTH_NOT_EXPR || TREE_CODE_CLASS (code) == tcc_comparison)
+    return true;
+  return false;
+}

Please don't do arbitrary deep lookups like this.  Instead this
function should be

bool
truth_valued_ssa_name_p (tree name)
{
  tree type = TREE_TYPE (name);
  gimple def_stmt;

  if (!INTEGRAL_TYPE_P (type))
    return false;
  if (TREE_CODE (type) == BOOLEAN_TYPE
      || TYPE_PRECISION (type) == 1)
    return true;

  def_stmt = SSA_NAME_DEF_STMT (name);
  if (is_gimple_assign (def_stmt))
    return truth_value_p (gimple_assign_rhs_code (def_stmt));
  return false;
}

+static tree
+detect_not_expr_operand (tree name, tree *nexpr)

same, don't do arbitrary deep lookups.  Do simple matches by
enumerating them.  The code is not followable or easily verifiable
for correctness.  Look at how all the code in fold-const.c is written - it's
very easy to follow what is matched and what is produced.  This is not
at all the case for your code.

Richard.

> Regards,
> Kai
>