Patchwork [gimplifier] : Boolify more strict conditional expressions and transform simple form to binary

login
register
mail settings
Submitter Kai Tietz
Date May 11, 2011, 9 a.m.
Message ID <BANLkTinuQk-K4GKv6hpwJ2o=ZxYxO-68sA@mail.gmail.com>
Download mbox | patch
Permalink /patch/95204/
State New
Headers show

Comments

Kai Tietz - May 11, 2011, 9 a.m.
Hi,

By investigating the conditional expression handling I found some
causes, why TRUTH operations AND, ANDIF, OR, XOR, and ORIF are
appearing withing conditional folding during gimplification.
The reason for this can be that the truth expression is simply used as
result of an assignment or return statement, which then leads to the
issue that expression has lhs type.  By this reason it is still
necessary to have in TRUTH operations type-cast after boolifying it
for later operation, if type isn't of kind boolean.  Therefore it is
necessary for conditional to check if their arms might be TRUTH
results and therefore doing boolification of the arms, too.

2011-05-11  Kai Tietz

	* gimplify.c (gimple_boolify): Handle COND_EXPR
	and make sure that even if type is BOOLEAN for
	TRUTH-opcodes the operands getting boolified.
	(gimple_has_cond_boolean_arms): Helper function to
	detect if condition is a TRUTH operation in arms.
	(gimple_is_truth_op): Checks if operand is of BOOLEAN
	kind.
	(gimplify_expr): Boolify operand condition for
	COND_EXPR and try to see if condition might be an TRUTH operation.
	Boolify truth opcodes AND, ANDIF, OR, ORIF, and XOR. Additional
	take care that we keep expression's type.

Tested on x86_64-w64-mingw32 and x86_64-pc-linux-gnu. Ok for apply?

Regards,
Kai
Richard Guenther - May 11, 2011, 9:08 a.m.
On Wed, May 11, 2011 at 11:00 AM, Kai Tietz <ktietz70@googlemail.com> wrote:
> Hi,
>
> By investigating the conditional expression handling I found some
> causes, why TRUTH operations AND, ANDIF, OR, XOR, and ORIF are
> appearing withing conditional folding during gimplification.
> The reason for this can be that the truth expression is simply used as
> result of an assignment or return statement, which then leads to the
> issue that expression has lhs type.  By this reason it is still
> necessary to have in TRUTH operations type-cast after boolifying it
> for later operation, if type isn't of kind boolean.  Therefore it is
> necessary for conditional to check if their arms might be TRUTH
> results and therefore doing boolification of the arms, too.

You are not making much sense - gimple_boolify already boolifies
both arms.  It assumes that if the expr is bool already the arms are
as well - I'm not sure that always holds, so defering that check as
your patch did probably makes sense.

Richard.

> 2011-05-11  Kai Tietz
>
>        * gimplify.c (gimple_boolify): Handle COND_EXPR
>        and make sure that even if type is BOOLEAN for
>        TRUTH-opcodes the operands getting boolified.
>        (gimple_has_cond_boolean_arms): Helper function to
>        detect if condition is a TRUTH operation in arms.
>        (gimple_is_truth_op): Checks if operand is of BOOLEAN
>        kind.
>        (gimplify_expr): Boolify operand condition for
>        COND_EXPR and try to see if condition might be an TRUTH operation.
>        Boolify truth opcodes AND, ANDIF, OR, ORIF, and XOR. Additional
>        take care that we keep expression's type.
>
> Tested on x86_64-w64-mingw32 and x86_64-pc-linux-gnu. Ok for apply?
>
> Regards,
> Kai
>
Kai Tietz - May 11, 2011, 9:14 a.m.
2011/5/11 Richard Guenther <richard.guenther@gmail.com>:
> On Wed, May 11, 2011 at 11:00 AM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> Hi,
>>
>> By investigating the conditional expression handling I found some
>> causes, why TRUTH operations AND, ANDIF, OR, XOR, and ORIF are
>> appearing withing conditional folding during gimplification.
>> The reason for this can be that the truth expression is simply used as
>> result of an assignment or return statement, which then leads to the
>> issue that expression has lhs type.  By this reason it is still
>> necessary to have in TRUTH operations type-cast after boolifying it
>> for later operation, if type isn't of kind boolean.  Therefore it is
>> necessary for conditional to check if their arms might be TRUTH
>> results and therefore doing boolification of the arms, too.
>
> You are not making much sense - gimple_boolify already boolifies
> both arms.  It assumes that if the expr is bool already the arms are
> as well - I'm not sure that always holds, so defering that check as
> your patch did probably makes sense.

It makes absolutely sense. Simply try the following example:

int
foo (int a, int b, int c)
{
  int e = (a && b);
  return e ? (c && !a) : (c && a && b);
}

You will see that by this you have TRUTH AND operations with none
boolean type, due the fact that for a conditional only the cond part
was converted. This patch checks that inner arms getting boolified, if
result of condition on both arms is a TRUTH result.

Regards,
Kai
Kai Tietz - May 11, 2011, 9:35 a.m.
For more detail what happens and why this conditional handling is necessary:

The sample code is:

int
foo (int a, int b)
{
  return (a ? b != 3 : 0);
}

leads for variant without condition boolifying of arms to:

;; Function foo (foo)

foo (int a, int b)
{
  int D.1991;
  int D.1990;
  int D.1989;

<bb 2>:
  D.1990_2 = a_1(D) != 0;
  D.1991_4 = b_3(D) != 3;
  D.1989_5 = D.1991_4 & D.1990_2;
  return D.1989_5;

}

with this code we see


;; Function foo (foo)

foo (int a, int b)
{
  _Bool D.1992;
  _Bool D.1991;
  _Bool D.1990;
  int D.1989;

<bb 2>:
  D.1990_2 = a_1(D) != 0;
  D.1991_4 = b_3(D) != 3;
  D.1992_5 = D.1991_4 & D.1990_2;
  D.1989_6 = (int) D.1992_5;
  return D.1989_6;

}

So you see that by this, the SSA variable having _Bool type, as to be
wished, and not being handled as int.

Regards,
Kai

Patch

Index: gcc/gcc/gimplify.c
===================================================================
--- gcc.orig/gcc/gimplify.c	2011-05-10 18:31:40.000000000 +0200
+++ gcc/gcc/gimplify.c	2011-05-11 10:20:30.413964700 +0200
@@ -102,6 +102,7 @@  typedef struct gimple_temp_hash_elt
 
 /* Forward declaration.  */
 static enum gimplify_status gimplify_compound_expr (tree *, gimple_seq *, bool);
+static bool gimple_has_cond_boolean_arms (tree);
 
 /* Mark X addressable.  Unlike the langhook we expect X to be in gimple
    form and we don't do any syntax checking.  */
@@ -2824,11 +2825,26 @@  gimple_boolify (tree expr)
 	}
     }
 
-  if (TREE_CODE (type) == BOOLEAN_TYPE)
-    return expr;
-
   switch (TREE_CODE (expr))
     {
+    case COND_EXPR:
+      /* If we have a conditional expression, which shall be
+         boolean, take care we boolify also their left and right arm.  */
+      if (TREE_OPERAND (expr, 2) != NULL_TREE && !VOID_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 2))))
+        TREE_OPERAND (expr, 2) = gimple_boolify (TREE_OPERAND (expr, 2));
+      if (TREE_OPERAND (expr, 1) != NULL_TREE && !VOID_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 1))))
+        TREE_OPERAND (expr, 1) = gimple_boolify (TREE_OPERAND (expr, 1));
+      TREE_OPERAND (expr, 0) = gimple_boolify (TREE_OPERAND (expr, 0));
+      if (TREE_CODE (type) == BOOLEAN_TYPE)
+	return expr;
+      if (!VOID_TYPE_P (TREE_TYPE (expr)))
+        {
+	  /* These expressions always produce boolean results.  */
+	  TREE_TYPE (expr) = boolean_type_node;
+	}
+      else
+        return fold_convert_loc (loc, boolean_type_node, expr);
+
     case TRUTH_AND_EXPR:
     case TRUTH_OR_EXPR:
     case TRUTH_XOR_EXPR:
@@ -2851,6 +2867,8 @@  gimple_boolify (tree expr)
     default:
       /* Other expressions that get here must have boolean values, but
 	 might need to be converted to the appropriate mode.  */
+      if (TREE_CODE (type) == BOOLEAN_TYPE)
+	return expr;
       return fold_convert_loc (loc, boolean_type_node, expr);
     }
 }
@@ -2909,6 +2927,66 @@  generic_expr_could_trap_p (tree expr)
   return false;
 }
 
+/* This function checks if OP is of TRUTH kind expression. It special-case
+   COND_EXPR, as here we need to look on results, too. See function
+   gimple_has_cond_boolean_arms () for more details.
+   If OP is of possible kind TRUTH expression, TRUE is returned,
+   otherwise FALSE is returned.
+   This functions assumes that all TRUTH operations, COND_EXPR with
+   boolean arms, INTEGER_CST with value of one or zero, and any
+   comparision has boolean result. */
+
+static bool
+gimple_is_truth_op (tree op)
+{
+  if (VOID_TYPE_P (TREE_TYPE (op)))
+    return false;
+  if (TREE_CODE (TREE_TYPE (op)) == BOOLEAN_TYPE)
+    return true;
+  switch (TREE_CODE (op))
+    {
+    case TRUTH_AND_EXPR:
+    case TRUTH_OR_EXPR:
+    case TRUTH_XOR_EXPR:
+    case TRUTH_ANDIF_EXPR:
+    case TRUTH_ORIF_EXPR:
+    case TRUTH_NOT_EXPR:
+      return true;
+    case COND_EXPR:
+       return gimple_has_cond_boolean_arms (op);
+    case INTEGER_CST:
+       if (integer_zerop (op) || integer_onep (op))
+         return true;
+       return false;
+    default:
+       if (TREE_CODE_CLASS (TREE_CODE (op)) == tcc_comparison)
+         return true;
+       break;
+    }
+  return false;
+}
+
+/* This function checks if all arms of the condition expression EXPR
+   are of kind TRUTH. If so, it returns TRUE, otherwise FALSE. */
+
+static bool
+gimple_has_cond_boolean_arms (tree expr)
+{
+  tree type = TREE_TYPE (expr);
+  tree arm1 = TREE_OPERAND (expr, 0);
+  tree arm2 = TREE_OPERAND (expr, 1);
+
+  if (VOID_TYPE_P (type))
+    return false;
+  if (!arm1 && !arm2)
+    return false;
+  if (arm1 && !gimple_is_truth_op (arm1))
+    return false;
+  if (arm2 && !gimple_is_truth_op (arm2))
+    return false;
+  return true;
+}
+
 /*  Convert the conditional expression pointed to by EXPR_P '(p) ? a : b;'
     into
 
@@ -6714,7 +6792,25 @@  gimplify_expr (tree *expr_p, gimple_seq
 	  break;
 
 	case COND_EXPR:
-	  ret = gimplify_cond_expr (expr_p, pre_p, fallback);
+	  {
+	    tree type = TREE_TYPE (*expr_p);
+	    tree nexpr = NULL_TREE;
+	    if (TREE_CODE (type) == BOOLEAN_TYPE
+	        || !gimple_has_cond_boolean_arms (*expr_p))
+	      type = NULL;
+	    if (type)
+	      nexpr = gimple_boolify (*expr_p);
+
+	    TREE_OPERAND (*expr_p, 0) = gimple_boolify (TREE_OPERAND (*expr_p, 0));
+	  
+	    ret = gimplify_cond_expr (expr_p, pre_p, fallback);
+
+	    if (nexpr)
+	      {
+		*expr_p = fold_convert (type, *expr_p);
+		ret = GS_OK;
+	      }
+	  }
 
 	  /* C99 code may assign to an array in a structure value of a
 	     conditional expression, and this has undefined behavior
@@ -6762,6 +6858,18 @@  gimplify_expr (tree *expr_p, gimple_seq
 
 	case TRUTH_ANDIF_EXPR:
 	case TRUTH_ORIF_EXPR:
+	  /* This shouldn't happen, but due fold-const (and here especially
+	     fold_truth_not_expr) happily uses operand type and doesn't
+	     automatically uses boolean_type as result, this happens.  */
+	  if (TREE_CODE (TREE_TYPE (*expr_p)) != BOOLEAN_TYPE)
+	    {
+	      tree type = TREE_TYPE (*expr_p);
+
+	      *expr_p = fold_convert (type, gimple_boolify (*expr_p));
+	      ret = GS_OK;
+	      break;
+	    }
+	  *expr_p = gimple_boolify (*expr_p);
 	  /* Pass the source location of the outer expression.  */
 	  ret = gimplify_boolean_expr (expr_p, saved_location);
 	  break;
@@ -7203,6 +7311,17 @@  gimplify_expr (tree *expr_p, gimple_seq
 	case TRUTH_AND_EXPR:
 	case TRUTH_OR_EXPR:
 	case TRUTH_XOR_EXPR:
+	  /* This shouldn't happen, but due fold-const (and here especially
+	     fold_truth_not_expr) happily uses operand type and doesn't
+	     automatically uses boolean_type as result, this happens.  */
+	  if (TREE_CODE (TREE_TYPE (*expr_p)) != BOOLEAN_TYPE)
+	    {
+	      tree type = TREE_TYPE (*expr_p);
+	      *expr_p = fold_convert (type, gimple_boolify (*expr_p));
+	      ret = GS_OK;
+	      break;
+	    }
+	  *expr_p = gimple_boolify (*expr_p);
 	  /* Classified as tcc_expression.  */
 	  goto expr_2;