Fix comments in ifconvert.

[pf3gnuchains/gcc-fork.git] / gcc / tree-if-conv.c

diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index fbdaa0d..e7af4aa 100644 (file)
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -103,8 +103,12 @@ along with GCC; see the file COPYING3.  If not see
 /* List of basic blocks in if-conversion-suitable order.  */
 static basic_block *ifc_bbs;
 
 /* List of basic blocks in if-conversion-suitable order.  */
 static basic_block *ifc_bbs;
 

-/* Create a new temp variable of type TYPE.  Add GIMPLE_ASSIGN to assign EXP
-   to the new variable.  */
+/* Main entry point.  Apply if-conversion to the LOOP.  Return true if
+   successful otherwise return false.  If false is returned then loop
+   remains unchanged.  FOR_VECTORIZER is a boolean flag.  It indicates
+   whether if-conversion is used for vectorizer or not.  If it is used
+   for vectorizer, additional checks are used. (Vectorization checks
+   are not yet implemented).  */

 
 static gimple
 ifc_temp_var (tree type, tree exp)
 
 static gimple
 ifc_temp_var (tree type, tree exp)


@@ -127,44 +131,9 @@ ifc_temp_var (tree type, tree exp)
   SSA_NAME_DEF_STMT (new_name) = stmt;
   update_stmt (stmt);
 
   SSA_NAME_DEF_STMT (new_name) = stmt;
   update_stmt (stmt);
 

-  return stmt;
-}
-
-/* Add condition NEW_COND to the predicate list of basic block BB.  */
-
-static void
-add_to_predicate_list (basic_block bb, tree new_cond)
-{
-  tree cond = (tree) bb->aux;
-
-  if (cond)
-    cond = fold_build2_loc (EXPR_LOCATION (cond),
-                           TRUTH_OR_EXPR, boolean_type_node,
-                           unshare_expr (cond), new_cond);
-  else
-    cond = new_cond;
-
-  bb->aux = cond;
-}
-
-/* Add the condition COND to the previous condition PREV_COND, and add this
-   to the predicate list of the destination of edge E.  GSI is the
-   place where the gimplification of the resulting condition should
-   output code.  LOOP is the loop to be if-converted.  */
-
-static tree
-add_to_dst_predicate_list (struct loop *loop, edge e,
-                          tree prev_cond, tree cond,
-                          gimple_stmt_iterator *gsi)
-{
-  tree new_cond = NULL_TREE;
-
-  if (!flow_bb_inside_loop_p (loop, e->dest))
-    return NULL_TREE;
-
-  if (prev_cond == boolean_true_node || !prev_cond)
-    new_cond = unshare_expr (cond);
-  else
+  /* If-conversion is not appropriate for all loops.  First, check if
+     loop is if-convertible or not.  */
+  if (!if_convertible_loop_p (loop, for_vectorizer))

     {
       tree tmp;
       gimple tmp_stmt = NULL;
     {
       tree tmp;
       gimple tmp_stmt = NULL;


@@ -206,10 +175,11 @@ bb_with_exit_edge_p (struct loop *loop, basic_block bb)
   return false;
 }
 
   return false;
 }
 

-/* STMT is a GIMPLE_COND.  Update two destination's predicate list.
-   Remove COND_EXPR, if it is not the exit condition of LOOP.
-   Otherwise update the exit condition of LOOP appropriately.  GSI
-   points to the statement STMT.  */
+         /* Successor bb inherits predicate of its predecessor.  If there
+            is no predicate in predecessor bb, then consider successor bb
+            as always executed.  */
+         if (cond == NULL_TREE)
+           cond = boolean_true_node;

 
 static void
 tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
 
 static void
 tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,


@@ -221,8 +191,10 @@ tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
   tree c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node,
                            gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
 
   tree c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node,
                            gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
 

-  extract_true_false_edges_from_block (gimple_bb (stmt),
-                                      &true_edge, &false_edge);
+  /* Now, all statements are if-converted and basic blocks are
+     annotated appropriately.  Combine all basic block into one huge
+     basic block.  */
+  combine_blocks (loop);

 
   /* Add new condition into destination's predicate list.  */
 
 
   /* Add new condition into destination's predicate list.  */
 


@@ -244,12 +216,11 @@ tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
 }
 
 /* If-convert stmt T which is part of LOOP.
 }
 
 /* If-convert stmt T which is part of LOOP.

-
-   If T is a GIMPLE_ASSIGN then it is converted into a conditional
-   modify expression using COND.  For conditional expressions, add
-   a condition in the destination basic block's predicate list and
-   remove the conditional expression itself.  GSI points to the
-   statement T.  */
+   If T is a GIMPLE_ASSIGN then it is converted into conditional modify
+   expression using COND.  For conditional expressions, add condition in the
+   destination basic block's predicate list and remove conditional
+   expression itself.  BSI is the iterator used to traverse statements of
+   loop.  It is used here when it is required to delete current statement.  */

 
 static tree
 tree_if_convert_stmt (struct loop *loop, gimple t, tree cond,
 
 static tree
 tree_if_convert_stmt (struct loop *loop, gimple t, tree cond,


@@ -295,15 +266,54 @@ tree_if_convert_stmt (struct loop *loop, gimple t, tree cond,
     default:
       gcc_unreachable ();
     }
     default:
       gcc_unreachable ();
     }

-

   return cond;
 }
 
   return cond;
 }
 

-/* Return true when PHI is if-convertible.  PHI is part of loop LOOP
-   and it belongs to basic block BB.
+/* STMT is a GIMPLE_COND.  Update two destination's predicate list.
+   Remove COND_EXPR, if it is not the loop exit condition.  Otherwise
+   update loop exit condition appropriately.  GSI is the iterator
+   used to traverse statement list.  STMT is part of loop LOOP.  */
+
+static void
+tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
+                          gimple_stmt_iterator *gsi)
+{
+  tree c, c2;
+  edge true_edge, false_edge;
+  location_t loc = gimple_location (stmt);
+
+  gcc_assert (gimple_code (stmt) == GIMPLE_COND);
+
+  c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node,
+                  gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));

 
 

-   PHI is not if-convertible if:
-   - it has more than 2 arguments,
+  extract_true_false_edges_from_block (gimple_bb (stmt),
+                                      &true_edge, &false_edge);
+
+  /* Add new condition into destination's predicate list.  */
+
+  /* If C is true, then TRUE_EDGE is taken.  */
+  add_to_dst_predicate_list (loop, true_edge, cond, c, gsi);
+
+  /* If C is false, then FALSE_EDGE is taken.  */
+  c2 = invert_truthvalue_loc (loc, unshare_expr (c));
+  add_to_dst_predicate_list (loop, false_edge, cond, c2, gsi);
+
+  /* Now this conditional statement is redundant.  Remove it.
+     But, do not remove exit condition!  Update exit condition
+     using new condition.  */
+  if (!bb_with_exit_edge_p (loop, gimple_bb (stmt)))
+    {
+      gsi_remove (gsi, true);
+      cond = NULL_TREE;
+    }
+  return;
+}
+
+/* Return true, iff PHI is if-convertible.  PHI is part of loop LOOP
+   and it belongs to basic block BB.
+   PHI is not if-convertible
+   - if it has more than 2 arguments,

    - virtual PHI is immediately used in another PHI node,
    - virtual PHI on BB other than header.  */
 
    - virtual PHI is immediately used in another PHI node,
    - virtual PHI on BB other than header.  */
 


@@ -354,7 +364,6 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
    - it is not movable,
    - it could trap,
    - LHS is not var decl.
    - it is not movable,
    - it could trap,
    - LHS is not var decl.

-

    GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP.  */
 
 static bool
    GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP.  */
 
 static bool


@@ -405,13 +414,11 @@ if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
   return true;
 }
 
   return true;
 }
 

-/* Return true when STMT is if-convertible.
-
-   A statement is if-convertible if:
-   - it is an if-convertible GIMPLE_ASSGIN,
-   - it is a GIMPLE_LABEL or a GIMPLE_COND.
-
-   STMT is inside BB, which is inside loop LOOP.  */
+/* Return true, iff STMT is if-convertible.
+   Statement is if-convertible if,
+   - it is if-convertible GIMPLE_ASSGIN,
+   - it is GIMPLE_LABEL or GIMPLE_COND.
+   STMT is inside block BB, which is inside loop LOOP.  */

 
 static bool
 if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
 
 static bool
 if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)


@@ -440,16 +447,14 @@ if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
   return true;
 }
 
   return true;
 }
 

-/* Return true when BB is if-convertible.  This routine does not check
-   basic block's statements and phis.
-
-   A basic block is not if-convertible if:
-   - it is non-empty and it is after the exit block (in BFS order),
-   - it is after the exit block but before the latch,
-   - its edges are not normal.
-
-   EXIT_BB is the basic block containing the exit of the LOOP.  BB is
-   inside LOOP.  */
+/* Return true, iff BB is if-convertible.
+   Note: This routine does _not_ check basic block statements and phis.
+   Basic block is not if-convertible if:
+   - basic block is non-empty and it is after exit block (in BFS order),
+   - basic block is after exit block but before latch,
+   - basic block edge(s) is not normal.
+   EXIT_BB_SEEN is true if basic block with exit edge is already seen.
+   BB is inside loop LOOP.  */

 
 static bool
 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
 
 static bool
 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)


@@ -497,8 +502,17 @@ if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
   return true;
 }
 
   return true;
 }
 

-/* Return true when all predecessor blocks of BB are visited.  The
-   VISITED bitmap keeps track of the visited blocks.  */
+/* Return true, iff LOOP is if-convertible.
+   LOOP is if-convertible if:
+   - it is innermost,
+   - it has two or more basic blocks,
+   - it has only one exit,
+   - loop header is not the exit edge,
+   - if its basic blocks and phi nodes are if convertible.  See above for
+     more info.
+   FOR_VECTORIZER enables vectorizer specific checks, for example, support
+   for vector conditions, data dependency checks, etc.
+   (Not implemented yet).  */

 
 static bool
 pred_blocks_visited_p (basic_block bb, bitmap *visited)
 
 static bool
 pred_blocks_visited_p (basic_block bb, bitmap *visited)


@@ -668,11 +682,69 @@ if_convertible_loop_p (struct loop *loop)
   return true;
 }
 
   return true;
 }
 

-/* During if-conversion, the bb->aux field is used to hold a predicate
-   list.  This function cleans for all the basic blocks in the given
-   LOOP their predicate list.  It also cleans up the e->aux field of
-   all the successor edges: e->aux is used to hold the true and false
-   conditions for conditional expressions.  */
+/* Add condition COND into predicate list of basic block BB.  */
+
+static void
+add_to_predicate_list (basic_block bb, tree new_cond)
+{
+  tree cond = (tree) bb->aux;
+
+  if (cond)
+    cond = fold_build2_loc (EXPR_LOCATION (cond),
+                       TRUTH_OR_EXPR, boolean_type_node,
+                       unshare_expr (cond), new_cond);
+  else
+    cond = new_cond;
+
+  bb->aux = cond;
+}
+
+/* Add condition COND into BB's predicate list.  PREV_COND is
+   existing condition.  */
+
+static tree
+add_to_dst_predicate_list (struct loop * loop, edge e,
+                          tree prev_cond, tree cond,
+                          gimple_stmt_iterator *gsi)
+{
+  tree new_cond = NULL_TREE;
+
+  if (!flow_bb_inside_loop_p (loop, e->dest))
+    return NULL_TREE;
+
+  if (prev_cond == boolean_true_node || !prev_cond)
+    new_cond = unshare_expr (cond);
+  else
+    {
+      tree tmp;
+      gimple tmp_stmt = NULL;
+
+      prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond),
+                                           true, NULL, true, GSI_SAME_STMT);
+
+      cond = force_gimple_operand_gsi (gsi, unshare_expr (cond),
+                                      true, NULL, true, GSI_SAME_STMT);
+
+      /* Add the condition to aux field of the edge.  In case edge
+        destination is a PHI node, this condition will be ANDed with
+        block predicate to construct complete condition.  */
+      e->aux = cond;
+
+      /* new_cond == prev_cond AND cond */
+      tmp = build2 (TRUTH_AND_EXPR, boolean_type_node,
+                   unshare_expr (prev_cond), cond);
+      tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
+      gsi_insert_before (gsi, tmp_stmt, GSI_SAME_STMT);
+      new_cond = gimple_assign_lhs (tmp_stmt);
+    }
+  add_to_predicate_list (e->dest, new_cond);
+  return new_cond;
+}
+
+/* During if-conversion aux field from basic block structure is used to hold
+   predicate list.  Clean each basic block's predicate list for the given LOOP.
+   Also clean aux field of successor edges, used to hold true and false
+   condition from conditional expression.  */

 
 static void
 clean_predicate_lists (struct loop *loop)
 
 static void
 clean_predicate_lists (struct loop *loop)


@@ -692,11 +764,9 @@ clean_predicate_lists (struct loop *loop)
   free (bb);
 }
 
   free (bb);
 }
 

-/* Basic block BB has two predecessors.  Using predecessor's bb->aux
-   field, set appropriate condition COND for the PHI node replacement.
-   Return true block whose phi arguments are selected when cond is
-   true.  LOOP is the loop containing the if-converted region, GSI is
-   the place to insert the code for the if-conversion.  */
+/* Basic block BB has two predecessors. Using predecessor's aux field, set
+   appropriate condition COND for the PHI node replacement.  Return true block
+   whose phi arguments are selected when cond is true.  */

 
 static basic_block
 find_phi_replacement_condition (struct loop *loop,
 
 static basic_block
 find_phi_replacement_condition (struct loop *loop,


@@ -993,25 +1063,78 @@ combine_blocks (struct loop *loop)
       delete_basic_block (bb);
     }
 
       delete_basic_block (bb);
     }
 

-  /* If possible, merge loop header to the block with the exit edge.
-     This reduces the number of basic blocks to two, to please the
-     vectorizer that handles only loops with two nodes.
-
-     FIXME: Call cleanup_tree_cfg.  */
+  /* Now if possible, merge loop header and block with exit edge.
+     This reduces number of basic blocks to 2.  Auto vectorizer addresses
+     loops with two nodes only.  FIXME: Use cleanup_tree_cfg().  */

   if (exit_bb
       && exit_bb != loop->header
       && can_merge_blocks_p (loop->header, exit_bb))
     merge_blocks (loop->header, exit_bb);
 }
 
   if (exit_bb
       && exit_bb != loop->header
       && can_merge_blocks_p (loop->header, exit_bb))
     merge_blocks (loop->header, exit_bb);
 }
 

-/* Main entry point: return true when LOOP is if-converted, otherwise
-   the loop remains unchanged.  */
+/* Make a new temp variable of type TYPE.  Add GIMPLE_ASSIGN to assign EXP
+   to the new variable.  */
+
+static gimple
+ifc_temp_var (tree type, tree exp)
+{
+  const char *name = "_ifc_";
+  tree var, new_name;
+  gimple stmt;
+
+  /* Create new temporary variable.  */
+  var = create_tmp_var (type, name);
+  add_referenced_var (var);
+
+  /* Build new statement to assign EXP to new variable.  */
+  stmt = gimple_build_assign (var, exp);
+
+  /* Get SSA name for the new variable and set make new statement
+     its definition statement.  */
+  new_name = make_ssa_name (var, stmt);
+  gimple_assign_set_lhs (stmt, new_name);
+  SSA_NAME_DEF_STMT (new_name) = stmt;
+  update_stmt (stmt);
+
+  return stmt;
+}
+
+
+/* Return TRUE iff, all pred blocks of BB are visited.
+   Bitmap VISITED keeps history of visited blocks.  */

 
 static bool
 tree_if_conversion (struct loop *loop)
 {
 
 static bool
 tree_if_conversion (struct loop *loop)
 {

-  gimple_stmt_iterator itr;
-  unsigned int i;
+  edge e;
+  edge_iterator ei;
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    if (!bitmap_bit_p (*visited, e->src->index))
+      return false;
+
+  return true;
+}
+
+/* Get body of a LOOP in suitable order for if-conversion.  It is
+   caller's responsibility to deallocate basic block list.
+   If-conversion suitable order is, breadth first sort (BFS) order
+   with an additional constraint: select a block only if all its
+   predecessors are already selected.  */
+
+static basic_block *
+get_loop_body_in_if_conv_order (const struct loop *loop)
+{
+  basic_block *blocks, *blocks_in_bfs_order;
+  basic_block bb;
+  bitmap visited;
+  unsigned int index = 0;
+  unsigned int visited_count = 0;
+
+  gcc_assert (loop->num_nodes);
+  gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+
+  blocks = XCNEWVEC (basic_block, loop->num_nodes);
+  visited = BITMAP_ALLOC (NULL);

 
   ifc_bbs = NULL;
 
 
   ifc_bbs = NULL;
 


@@ -1026,19 +1149,8 @@ tree_if_conversion (struct loop *loop)
          free (ifc_bbs);
          ifc_bbs = NULL;
        }
          free (ifc_bbs);
          ifc_bbs = NULL;
        }

-      free_dominance_info (CDI_POST_DOMINATORS);
-      return false;
-    }
-
-  for (i = 0; i < loop->num_nodes; i++)
-    {
-      basic_block bb = ifc_bbs [i];
-      tree cond = (tree) bb->aux;

 
 

-      /* Process all the statements in this basic block.
-        Remove conditional expression, if any, and annotate
-        destination basic block(s) appropriately.  */
-      for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */)
+      if (!bitmap_bit_p (visited, bb->index))

        {
          gimple t = gsi_stmt (itr);
          cond = tree_if_convert_stmt (loop, t, cond, &itr);
        {
          gimple t = gsi_stmt (itr);
          cond = tree_if_convert_stmt (loop, t, cond, &itr);


@@ -1046,20 +1158,12 @@ tree_if_conversion (struct loop *loop)
            gsi_next (&itr);
        }
 
            gsi_next (&itr);
        }
 

-      /* If current bb has only one successor, then consider it as an
-        unconditional goto.  */
-      if (single_succ_p (bb))
-       {
-         basic_block bb_n = single_succ (bb);
-
-         /* The successor bb inherits the predicate of its
-            predecessor.  If there is no predicate in the predecessor
-            bb, then consider the successor bb as always executed.  */
-         if (cond == NULL_TREE)
-           cond = boolean_true_node;
+      index++;

 
 

-         add_to_predicate_list (bb_n, cond);
-       }
+      if (index == loop->num_nodes
+         && visited_count != loop->num_nodes)
+       /* Not done yet.  */
+       index = 0;

     }
 
   /* Now, all statements are if-converted and basic blocks are
     }
 
   /* Now, all statements are if-converted and basic blocks are