[patch] [RFC] Gimplifying rhs cond_exprs

[Dorit Nuzman <DORIT at il dot ibm dot com>]

Hi,

We'd like to get some feedback on what people think about the following
patch, that enables gimplification of rhs cond_expr in force_gimple_operand
(i.e rhs cond_exprs are allowed *only* in the code gimplified by
force_gimple_operand).

This issue was raised before:
http://gcc.gnu.org/ml/gcc/2006-09/msg00515.html
http://gcc.gnu.org/ml/gcc-patches/2006-12/msg00447.html
http://gcc.gnu.org/ml/gcc-patches/2006-12/msg00695.html
http://gcc.gnu.org/ml/gcc-patches/2007-06/msg00136.html

As mentioned in the links above, one thing this patch allows is expressing
the loop-count for loops like the following (for which we don't know if it
executes 0 or n times) as a cond_expr, which makes the loop countable, and
therefore vectorizable:

      int a[1000];
      void foo (int n)
      {
        int i = 0;

        do
          {
            a[i] = 0;
            i++;
          }
          while (i < n);
      }

The patch was written by Zdenek. I checked it on top of of autovect-branch,
where we create rhs cond_exprs in the vectorizer (to express loop counts
that are "zero-or-n"), and it passed bootstrap with and without
vectorization enabled on powerpc64-linux and i386-linux.

thanks,

Zdenek and Dorit


Index: tree-gimple.c
===================================================================
*** tree-gimple.c        (revision 126877)
--- tree-gimple.c        (working copy)
*************** is_gimple_formal_tmp_rhs (tree t)
*** 62,67 ****
--- 62,68 ----
      case TRUTH_AND_EXPR:
      case TRUTH_OR_EXPR:
      case TRUTH_XOR_EXPR:
+     case COND_EXPR:
      case ADDR_EXPR:
      case CALL_EXPR:
      case CONSTRUCTOR:
Index: gimplify.c
===================================================================
*** gimplify.c           (revision 126877)
--- gimplify.c           (working copy)
*************** struct gimplify_ctx
*** 95,100 ****
--- 95,101 ----
    int conditions;
    bool save_stack;
    bool into_ssa;
+   bool allow_rhs_cond_expr;
  };

  static struct gimplify_ctx *gimplify_ctxp;
*************** gimple_boolify (tree expr)
*** 2494,2499 ****
--- 2497,2559 ----
      }
  }

+ /* Given a conditional expression *EXPR_P without side effects, gimplify
+    its operands.  New statements are inserted to PRE_P.  */
+
+ static enum gimplify_status
+ gimplify_pure_cond_expr (tree *expr_p, tree *pre_p)
+ {
+   tree expr = *expr_p, cond;
+   enum gimplify_status ret, tret;
+   enum tree_code code;
+
+   cond = gimple_boolify (COND_EXPR_COND (expr));
+
+   /* We need to handle && and || specially, as their gimplification
+      creates pure cond_expr, thus leading to an infinite cycle otherwise.
*/
+   code = TREE_CODE (cond);
+   if (code == TRUTH_ANDIF_EXPR)
+     TREE_SET_CODE (cond, TRUTH_AND_EXPR);
+   else if (code == TRUTH_ORIF_EXPR)
+     TREE_SET_CODE (cond, TRUTH_OR_EXPR);
+   ret = gimplify_expr (&cond, pre_p, NULL,
+                               is_gimple_condexpr, fb_rvalue);
+   COND_EXPR_COND (*expr_p) = cond;
+
+   tret = gimplify_expr (&COND_EXPR_THEN (expr), pre_p, NULL,
+                                    is_gimple_val, fb_rvalue);
+   ret = MIN (ret, tret);
+   tret = gimplify_expr (&COND_EXPR_ELSE (expr), pre_p, NULL,
+                                    is_gimple_val, fb_rvalue);
+
+   return MIN (ret, tret);
+ }
+
+ /* Returns true if EXPR is an expression whose evaluation does not have
+    any side effects.  */
+
+ static bool
+ expression_without_side_effects_p (tree expr)
+ {
+   unsigned i, n;
+
+   if (!expr || is_gimple_val (expr))
+     return true;
+
+   if (tree_could_trap_p (expr))
+     return false;
+
+   if (!EXPR_P (expr))
+     return false;
+
+   n = TREE_OPERAND_LENGTH (expr);
+   for (i = 0; i < n; i++)
+     if (!expression_without_side_effects_p (TREE_OPERAND (expr, i)))
+       return false;
+
+   return true;
+ }
+
  /*  Convert the conditional expression pointed to by EXPR_P '(p) ? a :
b;'
      into

*************** gimplify_cond_expr (tree *expr_p, tree *
*** 2527,2532 ****
--- 2587,2597 ----

        if ((fallback & fb_lvalue) == 0)
             {
+              if (gimplify_ctxp->allow_rhs_cond_expr
+                  && !TREE_SIDE_EFFECTS (*expr_p)
+                  && expression_without_side_effects_p (*expr_p))
+                return gimplify_pure_cond_expr (expr_p, pre_p);
+
               result = tmp2 = tmp = create_tmp_var (TREE_TYPE (expr),
"iftmp");
               ret = GS_ALL_DONE;
             }
*************** force_gimple_operand (tree expr, tree *s
*** 6635,6640 ****
--- 6700,6706 ----

    push_gimplify_context ();
    gimplify_ctxp->into_ssa = gimple_in_ssa_p (cfun);
+   gimplify_ctxp->allow_rhs_cond_expr = true;

    if (var)
      expr = build_gimple_modify_stmt (var, expr);