/* If-conversion for vectorizer.
|
/* If-conversion for vectorizer.
|
Copyright (C) 2004, 2005, 2007 Free Software Foundation, Inc.
|
Copyright (C) 2004, 2005, 2007 Free Software Foundation, Inc.
|
Contributed by Devang Patel <dpatel@apple.com>
|
Contributed by Devang Patel <dpatel@apple.com>
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it under
|
GCC is free software; you can redistribute it and/or modify it under
|
the terms of the GNU General Public License as published by the Free
|
the terms of the GNU General Public License as published by the Free
|
Software Foundation; either version 3, or (at your option) any later
|
Software Foundation; either version 3, or (at your option) any later
|
version.
|
version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
/* This pass implements tree level if-conversion transformation of loops.
|
/* This pass implements tree level if-conversion transformation of loops.
|
Initial goal is to help vectorizer vectorize loops with conditions.
|
Initial goal is to help vectorizer vectorize loops with conditions.
|
|
|
A short description of if-conversion:
|
A short description of if-conversion:
|
|
|
o Decide if a loop is if-convertible or not.
|
o Decide if a loop is if-convertible or not.
|
o Walk all loop basic blocks in breadth first order (BFS order).
|
o Walk all loop basic blocks in breadth first order (BFS order).
|
o Remove conditional statements (at the end of basic block)
|
o Remove conditional statements (at the end of basic block)
|
and propagate condition into destination basic blocks'
|
and propagate condition into destination basic blocks'
|
predicate list.
|
predicate list.
|
o Replace modify expression with conditional modify expression
|
o Replace modify expression with conditional modify expression
|
using current basic block's condition.
|
using current basic block's condition.
|
o Merge all basic blocks
|
o Merge all basic blocks
|
o Replace phi nodes with conditional modify expr
|
o Replace phi nodes with conditional modify expr
|
o Merge all basic blocks into header
|
o Merge all basic blocks into header
|
|
|
Sample transformation:
|
Sample transformation:
|
|
|
INPUT
|
INPUT
|
-----
|
-----
|
|
|
# i_23 = PHI <0(0), i_18(10)>;
|
# i_23 = PHI <0(0), i_18(10)>;
|
<L0>:;
|
<L0>:;
|
j_15 = A[i_23];
|
j_15 = A[i_23];
|
if (j_15 > 41) goto <L1>; else goto <L17>;
|
if (j_15 > 41) goto <L1>; else goto <L17>;
|
|
|
<L17>:;
|
<L17>:;
|
goto <bb 3> (<L3>);
|
goto <bb 3> (<L3>);
|
|
|
<L1>:;
|
<L1>:;
|
|
|
# iftmp.2_4 = PHI <0(8), 42(2)>;
|
# iftmp.2_4 = PHI <0(8), 42(2)>;
|
<L3>:;
|
<L3>:;
|
A[i_23] = iftmp.2_4;
|
A[i_23] = iftmp.2_4;
|
i_18 = i_23 + 1;
|
i_18 = i_23 + 1;
|
if (i_18 <= 15) goto <L19>; else goto <L18>;
|
if (i_18 <= 15) goto <L19>; else goto <L18>;
|
|
|
<L19>:;
|
<L19>:;
|
goto <bb 1> (<L0>);
|
goto <bb 1> (<L0>);
|
|
|
<L18>:;
|
<L18>:;
|
|
|
OUTPUT
|
OUTPUT
|
------
|
------
|
|
|
# i_23 = PHI <0(0), i_18(10)>;
|
# i_23 = PHI <0(0), i_18(10)>;
|
<L0>:;
|
<L0>:;
|
j_15 = A[i_23];
|
j_15 = A[i_23];
|
|
|
<L3>:;
|
<L3>:;
|
iftmp.2_4 = j_15 > 41 ? 42 : 0;
|
iftmp.2_4 = j_15 > 41 ? 42 : 0;
|
A[i_23] = iftmp.2_4;
|
A[i_23] = iftmp.2_4;
|
i_18 = i_23 + 1;
|
i_18 = i_23 + 1;
|
if (i_18 <= 15) goto <L19>; else goto <L18>;
|
if (i_18 <= 15) goto <L19>; else goto <L18>;
|
|
|
<L19>:;
|
<L19>:;
|
goto <bb 1> (<L0>);
|
goto <bb 1> (<L0>);
|
|
|
<L18>:;
|
<L18>:;
|
*/
|
*/
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "c-common.h"
|
#include "c-common.h"
|
#include "flags.h"
|
#include "flags.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "varray.h"
|
#include "varray.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "tree-dump.h"
|
#include "tree-dump.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
#include "tree-chrec.h"
|
#include "tree-chrec.h"
|
#include "tree-data-ref.h"
|
#include "tree-data-ref.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "target.h"
|
#include "target.h"
|
|
|
/* local function prototypes */
|
/* local function prototypes */
|
static unsigned int main_tree_if_conversion (void);
|
static unsigned int main_tree_if_conversion (void);
|
static tree tree_if_convert_stmt (struct loop *loop, tree, tree,
|
static tree tree_if_convert_stmt (struct loop *loop, tree, tree,
|
block_stmt_iterator *);
|
block_stmt_iterator *);
|
static void tree_if_convert_cond_expr (struct loop *, tree, tree,
|
static void tree_if_convert_cond_expr (struct loop *, tree, tree,
|
block_stmt_iterator *);
|
block_stmt_iterator *);
|
static bool if_convertible_phi_p (struct loop *, basic_block, tree);
|
static bool if_convertible_phi_p (struct loop *, basic_block, tree);
|
static bool if_convertible_modify_expr_p (struct loop *, basic_block, tree);
|
static bool if_convertible_modify_expr_p (struct loop *, basic_block, tree);
|
static bool if_convertible_stmt_p (struct loop *, basic_block, tree);
|
static bool if_convertible_stmt_p (struct loop *, basic_block, tree);
|
static bool if_convertible_bb_p (struct loop *, basic_block, basic_block);
|
static bool if_convertible_bb_p (struct loop *, basic_block, basic_block);
|
static bool if_convertible_loop_p (struct loop *, bool);
|
static bool if_convertible_loop_p (struct loop *, bool);
|
static void add_to_predicate_list (basic_block, tree);
|
static void add_to_predicate_list (basic_block, tree);
|
static tree add_to_dst_predicate_list (struct loop * loop, edge,
|
static tree add_to_dst_predicate_list (struct loop * loop, edge,
|
tree, tree,
|
tree, tree,
|
block_stmt_iterator *);
|
block_stmt_iterator *);
|
static void clean_predicate_lists (struct loop *loop);
|
static void clean_predicate_lists (struct loop *loop);
|
static basic_block find_phi_replacement_condition (struct loop *loop,
|
static basic_block find_phi_replacement_condition (struct loop *loop,
|
basic_block, tree *,
|
basic_block, tree *,
|
block_stmt_iterator *);
|
block_stmt_iterator *);
|
static void replace_phi_with_cond_modify_expr (tree, tree, basic_block,
|
static void replace_phi_with_cond_modify_expr (tree, tree, basic_block,
|
block_stmt_iterator *);
|
block_stmt_iterator *);
|
static void process_phi_nodes (struct loop *);
|
static void process_phi_nodes (struct loop *);
|
static void combine_blocks (struct loop *);
|
static void combine_blocks (struct loop *);
|
static tree ifc_temp_var (tree, tree);
|
static tree ifc_temp_var (tree, tree);
|
static bool pred_blocks_visited_p (basic_block, bitmap *);
|
static bool pred_blocks_visited_p (basic_block, bitmap *);
|
static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop);
|
static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop);
|
static bool bb_with_exit_edge_p (struct loop *, basic_block);
|
static bool bb_with_exit_edge_p (struct loop *, basic_block);
|
|
|
/* List of basic blocks in if-conversion-suitable order. */
|
/* List of basic blocks in if-conversion-suitable order. */
|
static basic_block *ifc_bbs;
|
static basic_block *ifc_bbs;
|
|
|
/* Main entry point.
|
/* Main entry point.
|
Apply if-conversion to the LOOP. Return true if successful otherwise return
|
Apply if-conversion to the LOOP. Return true if successful otherwise return
|
false. If false is returned then loop remains unchanged.
|
false. If false is returned then loop remains unchanged.
|
FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used
|
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
|
for vectorizer or not. If it is used for vectorizer, additional checks are
|
used. (Vectorization checks are not yet implemented). */
|
used. (Vectorization checks are not yet implemented). */
|
|
|
static bool
|
static bool
|
tree_if_conversion (struct loop *loop, bool for_vectorizer)
|
tree_if_conversion (struct loop *loop, bool for_vectorizer)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
block_stmt_iterator itr;
|
block_stmt_iterator itr;
|
unsigned int i;
|
unsigned int i;
|
|
|
ifc_bbs = NULL;
|
ifc_bbs = NULL;
|
|
|
/* if-conversion is not appropriate for all loops. First, check if loop is
|
/* if-conversion is not appropriate for all loops. First, check if loop is
|
if-convertible or not. */
|
if-convertible or not. */
|
if (!if_convertible_loop_p (loop, for_vectorizer))
|
if (!if_convertible_loop_p (loop, for_vectorizer))
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file,"-------------------------\n");
|
fprintf (dump_file,"-------------------------\n");
|
if (ifc_bbs)
|
if (ifc_bbs)
|
{
|
{
|
free (ifc_bbs);
|
free (ifc_bbs);
|
ifc_bbs = NULL;
|
ifc_bbs = NULL;
|
}
|
}
|
free_dominance_info (CDI_POST_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
return false;
|
return false;
|
}
|
}
|
|
|
/* Do actual work now. */
|
/* Do actual work now. */
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
{
|
{
|
tree cond;
|
tree cond;
|
|
|
bb = ifc_bbs [i];
|
bb = ifc_bbs [i];
|
|
|
/* Update condition using predicate list. */
|
/* Update condition using predicate list. */
|
cond = bb->aux;
|
cond = bb->aux;
|
|
|
/* Process all statements in this basic block.
|
/* Process all statements in this basic block.
|
Remove conditional expression, if any, and annotate
|
Remove conditional expression, if any, and annotate
|
destination basic block(s) appropriately. */
|
destination basic block(s) appropriately. */
|
for (itr = bsi_start (bb); !bsi_end_p (itr); /* empty */)
|
for (itr = bsi_start (bb); !bsi_end_p (itr); /* empty */)
|
{
|
{
|
tree t = bsi_stmt (itr);
|
tree t = bsi_stmt (itr);
|
cond = tree_if_convert_stmt (loop, t, cond, &itr);
|
cond = tree_if_convert_stmt (loop, t, cond, &itr);
|
if (!bsi_end_p (itr))
|
if (!bsi_end_p (itr))
|
bsi_next (&itr);
|
bsi_next (&itr);
|
}
|
}
|
|
|
/* If current bb has only one successor, then consider it as an
|
/* If current bb has only one successor, then consider it as an
|
unconditional goto. */
|
unconditional goto. */
|
if (single_succ_p (bb))
|
if (single_succ_p (bb))
|
{
|
{
|
basic_block bb_n = single_succ (bb);
|
basic_block bb_n = single_succ (bb);
|
if (cond != NULL_TREE)
|
if (cond != NULL_TREE)
|
add_to_predicate_list (bb_n, cond);
|
add_to_predicate_list (bb_n, cond);
|
}
|
}
|
}
|
}
|
|
|
/* Now, all statements are if-converted and basic blocks are
|
/* Now, all statements are if-converted and basic blocks are
|
annotated appropriately. Combine all basic block into one huge
|
annotated appropriately. Combine all basic block into one huge
|
basic block. */
|
basic block. */
|
combine_blocks (loop);
|
combine_blocks (loop);
|
|
|
/* clean up */
|
/* clean up */
|
clean_predicate_lists (loop);
|
clean_predicate_lists (loop);
|
free (ifc_bbs);
|
free (ifc_bbs);
|
ifc_bbs = NULL;
|
ifc_bbs = NULL;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* if-convert stmt T which is part of LOOP.
|
/* if-convert stmt T which is part of LOOP.
|
If T is a MODIFY_EXPR than it is converted into conditional modify
|
If T is a MODIFY_EXPR than it is converted into conditional modify
|
expression using COND. For conditional expressions, add condition in the
|
expression using COND. For conditional expressions, add condition in the
|
destination basic block's predicate list and remove conditional
|
destination basic block's predicate list and remove conditional
|
expression itself. BSI is the iterator used to traverse statements of
|
expression itself. BSI is the iterator used to traverse statements of
|
loop. It is used here when it is required to delete current statement. */
|
loop. It is used here when it is required to delete current statement. */
|
|
|
static tree
|
static tree
|
tree_if_convert_stmt (struct loop * loop, tree t, tree cond,
|
tree_if_convert_stmt (struct loop * loop, tree t, tree cond,
|
block_stmt_iterator *bsi)
|
block_stmt_iterator *bsi)
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "------if-convert stmt\n");
|
fprintf (dump_file, "------if-convert stmt\n");
|
print_generic_stmt (dump_file, t, TDF_SLIM);
|
print_generic_stmt (dump_file, t, TDF_SLIM);
|
print_generic_stmt (dump_file, cond, TDF_SLIM);
|
print_generic_stmt (dump_file, cond, TDF_SLIM);
|
}
|
}
|
|
|
switch (TREE_CODE (t))
|
switch (TREE_CODE (t))
|
{
|
{
|
/* Labels are harmless here. */
|
/* Labels are harmless here. */
|
case LABEL_EXPR:
|
case LABEL_EXPR:
|
break;
|
break;
|
|
|
case MODIFY_EXPR:
|
case MODIFY_EXPR:
|
/* This modify_expr is killing previous value of LHS. Appropriate value will
|
/* This modify_expr is killing previous value of LHS. Appropriate value will
|
be selected by PHI node based on condition. It is possible that before
|
be selected by PHI node based on condition. It is possible that before
|
this transformation, PHI nodes was selecting default value and now it will
|
this transformation, PHI nodes was selecting default value and now it will
|
use this new value. This is OK because it does not change validity the
|
use this new value. This is OK because it does not change validity the
|
program. */
|
program. */
|
break;
|
break;
|
|
|
case COND_EXPR:
|
case COND_EXPR:
|
/* Update destination blocks' predicate list and remove this
|
/* Update destination blocks' predicate list and remove this
|
condition expression. */
|
condition expression. */
|
tree_if_convert_cond_expr (loop, t, cond, bsi);
|
tree_if_convert_cond_expr (loop, t, cond, bsi);
|
cond = NULL_TREE;
|
cond = NULL_TREE;
|
break;
|
break;
|
|
|
default:
|
default:
|
gcc_unreachable ();
|
gcc_unreachable ();
|
}
|
}
|
return cond;
|
return cond;
|
}
|
}
|
|
|
/* STMT is COND_EXPR. Update two destination's predicate list.
|
/* STMT is COND_EXPR. Update two destination's predicate list.
|
Remove COND_EXPR, if it is not the loop exit condition. Otherwise
|
Remove COND_EXPR, if it is not the loop exit condition. Otherwise
|
update loop exit condition appropriately. BSI is the iterator
|
update loop exit condition appropriately. BSI is the iterator
|
used to traverse statement list. STMT is part of loop LOOP. */
|
used to traverse statement list. STMT is part of loop LOOP. */
|
|
|
static void
|
static void
|
tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond,
|
tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond,
|
block_stmt_iterator *bsi)
|
block_stmt_iterator *bsi)
|
{
|
{
|
tree c, c2;
|
tree c, c2;
|
edge true_edge, false_edge;
|
edge true_edge, false_edge;
|
|
|
gcc_assert (TREE_CODE (stmt) == COND_EXPR);
|
gcc_assert (TREE_CODE (stmt) == COND_EXPR);
|
|
|
c = COND_EXPR_COND (stmt);
|
c = COND_EXPR_COND (stmt);
|
|
|
extract_true_false_edges_from_block (bb_for_stmt (stmt),
|
extract_true_false_edges_from_block (bb_for_stmt (stmt),
|
&true_edge, &false_edge);
|
&true_edge, &false_edge);
|
|
|
/* Add new condition into destination's predicate list. */
|
/* Add new condition into destination's predicate list. */
|
|
|
/* If 'c' is true then TRUE_EDGE is taken. */
|
/* If 'c' is true then TRUE_EDGE is taken. */
|
add_to_dst_predicate_list (loop, true_edge, cond,
|
add_to_dst_predicate_list (loop, true_edge, cond,
|
unshare_expr (c), bsi);
|
unshare_expr (c), bsi);
|
|
|
/* If 'c' is false then FALSE_EDGE is taken. */
|
/* If 'c' is false then FALSE_EDGE is taken. */
|
c2 = invert_truthvalue (unshare_expr (c));
|
c2 = invert_truthvalue (unshare_expr (c));
|
add_to_dst_predicate_list (loop, false_edge, cond, c2, bsi);
|
add_to_dst_predicate_list (loop, false_edge, cond, c2, bsi);
|
|
|
/* Now this conditional statement is redundant. Remove it.
|
/* Now this conditional statement is redundant. Remove it.
|
But, do not remove exit condition! Update exit condition
|
But, do not remove exit condition! Update exit condition
|
using new condition. */
|
using new condition. */
|
if (!bb_with_exit_edge_p (loop, bb_for_stmt (stmt)))
|
if (!bb_with_exit_edge_p (loop, bb_for_stmt (stmt)))
|
{
|
{
|
bsi_remove (bsi, true);
|
bsi_remove (bsi, true);
|
cond = NULL_TREE;
|
cond = NULL_TREE;
|
}
|
}
|
return;
|
return;
|
}
|
}
|
|
|
/* Return true, iff PHI is if-convertible. PHI is part of loop LOOP
|
/* Return true, iff PHI is if-convertible. PHI is part of loop LOOP
|
and it belongs to basic block BB.
|
and it belongs to basic block BB.
|
PHI is not if-convertible
|
PHI is not if-convertible
|
- if it has more than 2 arguments.
|
- if it has more than 2 arguments.
|
- Virtual PHI is immediately used in another PHI node. */
|
- Virtual PHI is immediately used in another PHI node. */
|
|
|
static bool
|
static bool
|
if_convertible_phi_p (struct loop *loop, basic_block bb, tree phi)
|
if_convertible_phi_p (struct loop *loop, basic_block bb, tree phi)
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "-------------------------\n");
|
fprintf (dump_file, "-------------------------\n");
|
print_generic_stmt (dump_file, phi, TDF_SLIM);
|
print_generic_stmt (dump_file, phi, TDF_SLIM);
|
}
|
}
|
|
|
if (bb != loop->header && PHI_NUM_ARGS (phi) != 2)
|
if (bb != loop->header && PHI_NUM_ARGS (phi) != 2)
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "More than two phi node args.\n");
|
fprintf (dump_file, "More than two phi node args.\n");
|
return false;
|
return false;
|
}
|
}
|
|
|
if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
|
if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
|
{
|
{
|
imm_use_iterator imm_iter;
|
imm_use_iterator imm_iter;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, PHI_RESULT (phi))
|
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, PHI_RESULT (phi))
|
{
|
{
|
if (TREE_CODE (USE_STMT (use_p)) == PHI_NODE)
|
if (TREE_CODE (USE_STMT (use_p)) == PHI_NODE)
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "Difficult to handle this virtual phi.\n");
|
fprintf (dump_file, "Difficult to handle this virtual phi.\n");
|
return false;
|
return false;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Return true, if M_EXPR is if-convertible.
|
/* Return true, if M_EXPR is if-convertible.
|
MODIFY_EXPR is not if-convertible if,
|
MODIFY_EXPR is not if-convertible if,
|
- It is not movable.
|
- It is not movable.
|
- It could trap.
|
- It could trap.
|
- LHS is not var decl.
|
- LHS is not var decl.
|
MODIFY_EXPR is part of block BB, which is inside loop LOOP.
|
MODIFY_EXPR is part of block BB, which is inside loop LOOP.
|
*/
|
*/
|
|
|
static bool
|
static bool
|
if_convertible_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr)
|
if_convertible_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr)
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "-------------------------\n");
|
fprintf (dump_file, "-------------------------\n");
|
print_generic_stmt (dump_file, m_expr, TDF_SLIM);
|
print_generic_stmt (dump_file, m_expr, TDF_SLIM);
|
}
|
}
|
|
|
/* Be conservative and do not handle immovable expressions. */
|
/* Be conservative and do not handle immovable expressions. */
|
if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE)
|
if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE)
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "stmt is movable. Don't take risk\n");
|
fprintf (dump_file, "stmt is movable. Don't take risk\n");
|
return false;
|
return false;
|
}
|
}
|
|
|
/* See if it needs speculative loading or not. */
|
/* See if it needs speculative loading or not. */
|
if (bb != loop->header
|
if (bb != loop->header
|
&& tree_could_trap_p (TREE_OPERAND (m_expr, 1)))
|
&& tree_could_trap_p (TREE_OPERAND (m_expr, 1)))
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "tree could trap...\n");
|
fprintf (dump_file, "tree could trap...\n");
|
return false;
|
return false;
|
}
|
}
|
|
|
if (TREE_CODE (TREE_OPERAND (m_expr, 1)) == CALL_EXPR)
|
if (TREE_CODE (TREE_OPERAND (m_expr, 1)) == CALL_EXPR)
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "CALL_EXPR \n");
|
fprintf (dump_file, "CALL_EXPR \n");
|
return false;
|
return false;
|
}
|
}
|
|
|
if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME
|
if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME
|
&& bb != loop->header
|
&& bb != loop->header
|
&& !bb_with_exit_edge_p (loop, bb))
|
&& !bb_with_exit_edge_p (loop, bb))
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "LHS is not var\n");
|
fprintf (dump_file, "LHS is not var\n");
|
print_generic_stmt (dump_file, m_expr, TDF_SLIM);
|
print_generic_stmt (dump_file, m_expr, TDF_SLIM);
|
}
|
}
|
return false;
|
return false;
|
}
|
}
|
|
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Return true, iff STMT is if-convertible.
|
/* Return true, iff STMT is if-convertible.
|
Statement is if-convertible if,
|
Statement is if-convertible if,
|
- It is if-convertible MODIFY_EXPR
|
- It is if-convertible MODIFY_EXPR
|
- IT is LABEL_EXPR or COND_EXPR.
|
- IT is LABEL_EXPR or COND_EXPR.
|
STMT is inside block BB, which is inside loop LOOP. */
|
STMT is inside block BB, which is inside loop LOOP. */
|
|
|
static bool
|
static bool
|
if_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt)
|
if_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt)
|
{
|
{
|
switch (TREE_CODE (stmt))
|
switch (TREE_CODE (stmt))
|
{
|
{
|
case LABEL_EXPR:
|
case LABEL_EXPR:
|
break;
|
break;
|
|
|
case MODIFY_EXPR:
|
case MODIFY_EXPR:
|
|
|
if (!if_convertible_modify_expr_p (loop, bb, stmt))
|
if (!if_convertible_modify_expr_p (loop, bb, stmt))
|
return false;
|
return false;
|
break;
|
break;
|
|
|
case COND_EXPR:
|
case COND_EXPR:
|
break;
|
break;
|
|
|
default:
|
default:
|
/* Don't know what to do with 'em so don't do anything. */
|
/* Don't know what to do with 'em so don't do anything. */
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "don't know what to do\n");
|
fprintf (dump_file, "don't know what to do\n");
|
print_generic_stmt (dump_file, stmt, TDF_SLIM);
|
print_generic_stmt (dump_file, stmt, TDF_SLIM);
|
}
|
}
|
return false;
|
return false;
|
break;
|
break;
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Return true, iff BB is if-convertible.
|
/* Return true, iff BB is if-convertible.
|
Note: This routine does _not_ check basic block statements and phis.
|
Note: This routine does _not_ check basic block statements and phis.
|
Basic block is not if-convertible if,
|
Basic block is not if-convertible if,
|
- Basic block is non-empty and it is after exit block (in BFS order).
|
- 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 is after exit block but before latch.
|
- Basic block edge(s) is not normal.
|
- Basic block edge(s) is not normal.
|
EXIT_BB_SEEN is true if basic block with exit edge is already seen.
|
EXIT_BB_SEEN is true if basic block with exit edge is already seen.
|
BB is inside loop LOOP. */
|
BB is inside loop LOOP. */
|
|
|
static bool
|
static bool
|
if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
|
if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "----------[%d]-------------\n", bb->index);
|
fprintf (dump_file, "----------[%d]-------------\n", bb->index);
|
|
|
if (exit_bb)
|
if (exit_bb)
|
{
|
{
|
if (bb != loop->latch)
|
if (bb != loop->latch)
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "basic block after exit bb but before latch\n");
|
fprintf (dump_file, "basic block after exit bb but before latch\n");
|
return false;
|
return false;
|
}
|
}
|
else if (!empty_block_p (bb))
|
else if (!empty_block_p (bb))
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "non empty basic block after exit bb\n");
|
fprintf (dump_file, "non empty basic block after exit bb\n");
|
return false;
|
return false;
|
}
|
}
|
else if (bb == loop->latch
|
else if (bb == loop->latch
|
&& bb != exit_bb
|
&& bb != exit_bb
|
&& !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
|
&& !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "latch is not dominated by exit_block\n");
|
fprintf (dump_file, "latch is not dominated by exit_block\n");
|
return false;
|
return false;
|
}
|
}
|
}
|
}
|
|
|
/* Be less adventurous and handle only normal edges. */
|
/* Be less adventurous and handle only normal edges. */
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
if (e->flags &
|
if (e->flags &
|
(EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
|
(EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file,"Difficult to handle edges\n");
|
fprintf (dump_file,"Difficult to handle edges\n");
|
return false;
|
return false;
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Return true, iff LOOP is if-convertible.
|
/* Return true, iff LOOP is if-convertible.
|
LOOP is if-convertible if,
|
LOOP is if-convertible if,
|
- It is innermost.
|
- It is innermost.
|
- It has two or more basic blocks.
|
- It has two or more basic blocks.
|
- It has only one exit.
|
- It has only one exit.
|
- Loop header is not the exit edge.
|
- Loop header is not the exit edge.
|
- If its basic blocks and phi nodes are if convertible. See above for
|
- If its basic blocks and phi nodes are if convertible. See above for
|
more info.
|
more info.
|
FOR_VECTORIZER enables vectorizer specific checks. For example, support
|
FOR_VECTORIZER enables vectorizer specific checks. For example, support
|
for vector conditions, data dependency checks etc.. (Not implemented yet). */
|
for vector conditions, data dependency checks etc.. (Not implemented yet). */
|
|
|
static bool
|
static bool
|
if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
|
if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
|
{
|
{
|
tree phi;
|
tree phi;
|
basic_block bb;
|
basic_block bb;
|
block_stmt_iterator itr;
|
block_stmt_iterator itr;
|
unsigned int i;
|
unsigned int i;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
basic_block exit_bb = NULL;
|
basic_block exit_bb = NULL;
|
|
|
/* Handle only inner most loop. */
|
/* Handle only inner most loop. */
|
if (!loop || loop->inner)
|
if (!loop || loop->inner)
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "not inner most loop\n");
|
fprintf (dump_file, "not inner most loop\n");
|
return false;
|
return false;
|
}
|
}
|
|
|
/* If only one block, no need for if-conversion. */
|
/* If only one block, no need for if-conversion. */
|
if (loop->num_nodes <= 2)
|
if (loop->num_nodes <= 2)
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "less than 2 basic blocks\n");
|
fprintf (dump_file, "less than 2 basic blocks\n");
|
return false;
|
return false;
|
}
|
}
|
|
|
/* More than one loop exit is too much to handle. */
|
/* More than one loop exit is too much to handle. */
|
if (!loop->single_exit)
|
if (!loop->single_exit)
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file, "multiple exits\n");
|
fprintf (dump_file, "multiple exits\n");
|
return false;
|
return false;
|
}
|
}
|
|
|
/* ??? Check target's vector conditional operation support for vectorizer. */
|
/* ??? Check target's vector conditional operation support for vectorizer. */
|
|
|
/* If one of the loop header's edge is exit edge then do not apply
|
/* If one of the loop header's edge is exit edge then do not apply
|
if-conversion. */
|
if-conversion. */
|
FOR_EACH_EDGE (e, ei, loop->header->succs)
|
FOR_EACH_EDGE (e, ei, loop->header->succs)
|
{
|
{
|
if (loop_exit_edge_p (loop, e))
|
if (loop_exit_edge_p (loop, e))
|
return false;
|
return false;
|
}
|
}
|
|
|
calculate_dominance_info (CDI_DOMINATORS);
|
calculate_dominance_info (CDI_DOMINATORS);
|
calculate_dominance_info (CDI_POST_DOMINATORS);
|
calculate_dominance_info (CDI_POST_DOMINATORS);
|
|
|
/* Allow statements that can be handled during if-conversion. */
|
/* Allow statements that can be handled during if-conversion. */
|
ifc_bbs = get_loop_body_in_if_conv_order (loop);
|
ifc_bbs = get_loop_body_in_if_conv_order (loop);
|
if (!ifc_bbs)
|
if (!ifc_bbs)
|
{
|
{
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
fprintf (dump_file,"Irreducible loop\n");
|
fprintf (dump_file,"Irreducible loop\n");
|
free_dominance_info (CDI_POST_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
return false;
|
return false;
|
}
|
}
|
|
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
{
|
{
|
bb = ifc_bbs[i];
|
bb = ifc_bbs[i];
|
|
|
if (!if_convertible_bb_p (loop, bb, exit_bb))
|
if (!if_convertible_bb_p (loop, bb, exit_bb))
|
return false;
|
return false;
|
|
|
/* Check statements. */
|
/* Check statements. */
|
for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr))
|
for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr))
|
if (!if_convertible_stmt_p (loop, bb, bsi_stmt (itr)))
|
if (!if_convertible_stmt_p (loop, bb, bsi_stmt (itr)))
|
return false;
|
return false;
|
/* ??? Check data dependency for vectorizer. */
|
/* ??? Check data dependency for vectorizer. */
|
|
|
/* What about phi nodes ? */
|
/* What about phi nodes ? */
|
phi = phi_nodes (bb);
|
phi = phi_nodes (bb);
|
|
|
/* Clear aux field of incoming edges to a bb with a phi node. */
|
/* Clear aux field of incoming edges to a bb with a phi node. */
|
if (phi)
|
if (phi)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
e->aux = NULL;
|
e->aux = NULL;
|
|
|
/* Check statements. */
|
/* Check statements. */
|
for (; phi; phi = PHI_CHAIN (phi))
|
for (; phi; phi = PHI_CHAIN (phi))
|
if (!if_convertible_phi_p (loop, bb, phi))
|
if (!if_convertible_phi_p (loop, bb, phi))
|
return false;
|
return false;
|
|
|
if (bb_with_exit_edge_p (loop, bb))
|
if (bb_with_exit_edge_p (loop, bb))
|
exit_bb = bb;
|
exit_bb = bb;
|
}
|
}
|
|
|
/* OK. Did not find any potential issues so go ahead in if-convert
|
/* OK. Did not find any potential issues so go ahead in if-convert
|
this loop. Now there is no looking back. */
|
this loop. Now there is no looking back. */
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file,"Applying if-conversion\n");
|
fprintf (dump_file,"Applying if-conversion\n");
|
|
|
free_dominance_info (CDI_POST_DOMINATORS);
|
free_dominance_info (CDI_POST_DOMINATORS);
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Add condition COND into predicate list of basic block BB. */
|
/* Add condition COND into predicate list of basic block BB. */
|
|
|
static void
|
static void
|
add_to_predicate_list (basic_block bb, tree new_cond)
|
add_to_predicate_list (basic_block bb, tree new_cond)
|
{
|
{
|
tree cond = bb->aux;
|
tree cond = bb->aux;
|
|
|
if (cond)
|
if (cond)
|
cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
|
cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
|
unshare_expr (cond), new_cond);
|
unshare_expr (cond), new_cond);
|
else
|
else
|
cond = new_cond;
|
cond = new_cond;
|
|
|
bb->aux = cond;
|
bb->aux = cond;
|
}
|
}
|
|
|
/* Add condition COND into BB's predicate list. PREV_COND is
|
/* Add condition COND into BB's predicate list. PREV_COND is
|
existing condition. */
|
existing condition. */
|
|
|
static tree
|
static tree
|
add_to_dst_predicate_list (struct loop * loop, edge e,
|
add_to_dst_predicate_list (struct loop * loop, edge e,
|
tree prev_cond, tree cond,
|
tree prev_cond, tree cond,
|
block_stmt_iterator *bsi)
|
block_stmt_iterator *bsi)
|
{
|
{
|
tree new_cond = NULL_TREE;
|
tree new_cond = NULL_TREE;
|
|
|
if (!flow_bb_inside_loop_p (loop, e->dest))
|
if (!flow_bb_inside_loop_p (loop, e->dest))
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
if (prev_cond == boolean_true_node || !prev_cond)
|
if (prev_cond == boolean_true_node || !prev_cond)
|
new_cond = unshare_expr (cond);
|
new_cond = unshare_expr (cond);
|
else
|
else
|
{
|
{
|
tree tmp;
|
tree tmp;
|
tree tmp_stmt = NULL_TREE;
|
tree tmp_stmt = NULL_TREE;
|
tree tmp_stmts1 = NULL_TREE;
|
tree tmp_stmts1 = NULL_TREE;
|
tree tmp_stmts2 = NULL_TREE;
|
tree tmp_stmts2 = NULL_TREE;
|
prev_cond = force_gimple_operand (unshare_expr (prev_cond),
|
prev_cond = force_gimple_operand (unshare_expr (prev_cond),
|
&tmp_stmts1, true, NULL);
|
&tmp_stmts1, true, NULL);
|
if (tmp_stmts1)
|
if (tmp_stmts1)
|
bsi_insert_before (bsi, tmp_stmts1, BSI_SAME_STMT);
|
bsi_insert_before (bsi, tmp_stmts1, BSI_SAME_STMT);
|
|
|
cond = force_gimple_operand (unshare_expr (cond),
|
cond = force_gimple_operand (unshare_expr (cond),
|
&tmp_stmts2, true, NULL);
|
&tmp_stmts2, true, NULL);
|
if (tmp_stmts2)
|
if (tmp_stmts2)
|
bsi_insert_before (bsi, tmp_stmts2, BSI_SAME_STMT);
|
bsi_insert_before (bsi, tmp_stmts2, BSI_SAME_STMT);
|
|
|
/* Add the condition to aux field of the edge. In case edge
|
/* Add the condition to aux field of the edge. In case edge
|
destination is a PHI node, this condition will be ANDed with
|
destination is a PHI node, this condition will be ANDed with
|
block predicate to construct complete condition. */
|
block predicate to construct complete condition. */
|
e->aux = cond;
|
e->aux = cond;
|
|
|
/* new_cond == prev_cond AND cond */
|
/* new_cond == prev_cond AND cond */
|
tmp = build2 (TRUTH_AND_EXPR, boolean_type_node,
|
tmp = build2 (TRUTH_AND_EXPR, boolean_type_node,
|
unshare_expr (prev_cond), cond);
|
unshare_expr (prev_cond), cond);
|
tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
|
tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
|
bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT);
|
bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT);
|
new_cond = TREE_OPERAND (tmp_stmt, 0);
|
new_cond = TREE_OPERAND (tmp_stmt, 0);
|
}
|
}
|
add_to_predicate_list (e->dest, new_cond);
|
add_to_predicate_list (e->dest, new_cond);
|
return new_cond;
|
return new_cond;
|
}
|
}
|
|
|
/* During if-conversion aux field from basic block structure is used to hold
|
/* 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.
|
predicate list. Clean each basic block's predicate list for the given LOOP.
|
Also clean aux field of succesor edges, used to hold true and false
|
Also clean aux field of succesor edges, used to hold true and false
|
condition from conditional expression. */
|
condition from conditional expression. */
|
|
|
static void
|
static void
|
clean_predicate_lists (struct loop *loop)
|
clean_predicate_lists (struct loop *loop)
|
{
|
{
|
basic_block *bb;
|
basic_block *bb;
|
unsigned int i;
|
unsigned int i;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
bb = get_loop_body (loop);
|
bb = get_loop_body (loop);
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
{
|
{
|
bb[i]->aux = NULL;
|
bb[i]->aux = NULL;
|
FOR_EACH_EDGE (e, ei, bb[i]->succs)
|
FOR_EACH_EDGE (e, ei, bb[i]->succs)
|
e->aux = NULL;
|
e->aux = NULL;
|
}
|
}
|
free (bb);
|
free (bb);
|
}
|
}
|
|
|
/* Basic block BB has two predecessors. Using predecessor's aux field, set
|
/* Basic block BB has two predecessors. Using predecessor's aux field, set
|
appropriate condition COND for the PHI node replacement. Return true block
|
appropriate condition COND for the PHI node replacement. Return true block
|
whose phi arguments are selected when cond is true. */
|
whose phi arguments are selected when cond is true. */
|
|
|
static basic_block
|
static basic_block
|
find_phi_replacement_condition (struct loop *loop,
|
find_phi_replacement_condition (struct loop *loop,
|
basic_block bb, tree *cond,
|
basic_block bb, tree *cond,
|
block_stmt_iterator *bsi)
|
block_stmt_iterator *bsi)
|
{
|
{
|
edge first_edge, second_edge;
|
edge first_edge, second_edge;
|
tree tmp_cond, new_stmts;
|
tree tmp_cond, new_stmts;
|
|
|
gcc_assert (EDGE_COUNT (bb->preds) == 2);
|
gcc_assert (EDGE_COUNT (bb->preds) == 2);
|
first_edge = EDGE_PRED (bb, 0);
|
first_edge = EDGE_PRED (bb, 0);
|
second_edge = EDGE_PRED (bb, 1);
|
second_edge = EDGE_PRED (bb, 1);
|
|
|
/* Use condition based on following criteria:
|
/* Use condition based on following criteria:
|
1)
|
1)
|
S1: x = !c ? a : b;
|
S1: x = !c ? a : b;
|
|
|
S2: x = c ? b : a;
|
S2: x = c ? b : a;
|
|
|
S2 is preferred over S1. Make 'b' first_bb and use its condition.
|
S2 is preferred over S1. Make 'b' first_bb and use its condition.
|
|
|
2) Do not make loop header first_bb.
|
2) Do not make loop header first_bb.
|
|
|
3)
|
3)
|
S1: x = !(c == d)? a : b;
|
S1: x = !(c == d)? a : b;
|
|
|
S21: t1 = c == d;
|
S21: t1 = c == d;
|
S22: x = t1 ? b : a;
|
S22: x = t1 ? b : a;
|
|
|
S3: x = (c == d) ? b : a;
|
S3: x = (c == d) ? b : a;
|
|
|
S3 is preferred over S1 and S2*, Make 'b' first_bb and use
|
S3 is preferred over S1 and S2*, Make 'b' first_bb and use
|
its condition.
|
its condition.
|
|
|
4) If pred B is dominated by pred A then use pred B's condition.
|
4) If pred B is dominated by pred A then use pred B's condition.
|
See PR23115. */
|
See PR23115. */
|
|
|
/* Select condition that is not TRUTH_NOT_EXPR. */
|
/* Select condition that is not TRUTH_NOT_EXPR. */
|
tmp_cond = (first_edge->src)->aux;
|
tmp_cond = (first_edge->src)->aux;
|
if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
|
if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
|
{
|
{
|
edge tmp_edge;
|
edge tmp_edge;
|
|
|
tmp_edge = first_edge;
|
tmp_edge = first_edge;
|
first_edge = second_edge;
|
first_edge = second_edge;
|
second_edge = tmp_edge;
|
second_edge = tmp_edge;
|
}
|
}
|
|
|
/* Check if FIRST_BB is loop header or not and make sure that
|
/* Check if FIRST_BB is loop header or not and make sure that
|
FIRST_BB does not dominate SECOND_BB. */
|
FIRST_BB does not dominate SECOND_BB. */
|
if (first_edge->src == loop->header
|
if (first_edge->src == loop->header
|
|| dominated_by_p (CDI_DOMINATORS,
|
|| dominated_by_p (CDI_DOMINATORS,
|
second_edge->src, first_edge->src))
|
second_edge->src, first_edge->src))
|
{
|
{
|
*cond = (second_edge->src)->aux;
|
*cond = (second_edge->src)->aux;
|
|
|
/* If there is a condition on an incoming edge,
|
/* If there is a condition on an incoming edge,
|
AND it with the incoming bb predicate. */
|
AND it with the incoming bb predicate. */
|
if (second_edge->aux)
|
if (second_edge->aux)
|
*cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
|
*cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
|
*cond, second_edge->aux);
|
*cond, second_edge->aux);
|
|
|
if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
|
if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
|
/* We can be smart here and choose inverted
|
/* We can be smart here and choose inverted
|
condition without switching bbs. */
|
condition without switching bbs. */
|
*cond = invert_truthvalue (*cond);
|
*cond = invert_truthvalue (*cond);
|
else
|
else
|
/* Select non loop header bb. */
|
/* Select non loop header bb. */
|
first_edge = second_edge;
|
first_edge = second_edge;
|
}
|
}
|
else
|
else
|
{
|
{
|
/* FIRST_BB is not loop header */
|
/* FIRST_BB is not loop header */
|
*cond = (first_edge->src)->aux;
|
*cond = (first_edge->src)->aux;
|
|
|
/* If there is a condition on an incoming edge,
|
/* If there is a condition on an incoming edge,
|
AND it with the incoming bb predicate. */
|
AND it with the incoming bb predicate. */
|
if (first_edge->aux)
|
if (first_edge->aux)
|
*cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
|
*cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
|
*cond, first_edge->aux);
|
*cond, first_edge->aux);
|
}
|
}
|
|
|
/* Create temp. for the condition. Vectorizer prefers to have gimple
|
/* Create temp. for the condition. Vectorizer prefers to have gimple
|
value as condition. Various targets use different means to communicate
|
value as condition. Various targets use different means to communicate
|
condition in vector compare operation. Using gimple value allows
|
condition in vector compare operation. Using gimple value allows
|
compiler to emit vector compare and select RTL without exposing
|
compiler to emit vector compare and select RTL without exposing
|
compare's result. */
|
compare's result. */
|
*cond = force_gimple_operand (unshare_expr (*cond), &new_stmts,
|
*cond = force_gimple_operand (unshare_expr (*cond), &new_stmts,
|
false, NULL_TREE);
|
false, NULL_TREE);
|
if (new_stmts)
|
if (new_stmts)
|
bsi_insert_before (bsi, new_stmts, BSI_SAME_STMT);
|
bsi_insert_before (bsi, new_stmts, BSI_SAME_STMT);
|
if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
|
if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
|
{
|
{
|
tree new_stmt;
|
tree new_stmt;
|
|
|
new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
|
new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
|
bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
|
bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
|
*cond = TREE_OPERAND (new_stmt, 0);
|
*cond = TREE_OPERAND (new_stmt, 0);
|
}
|
}
|
|
|
gcc_assert (*cond);
|
gcc_assert (*cond);
|
|
|
return first_edge->src;
|
return first_edge->src;
|
}
|
}
|
|
|
|
|
/* Replace PHI node with conditional modify expr using COND.
|
/* Replace PHI node with conditional modify expr using COND.
|
This routine does not handle PHI nodes with more than two arguments.
|
This routine does not handle PHI nodes with more than two arguments.
|
For example,
|
For example,
|
S1: A = PHI <x1(1), x2(5)
|
S1: A = PHI <x1(1), x2(5)
|
is converted into,
|
is converted into,
|
S2: A = cond ? x1 : x2;
|
S2: A = cond ? x1 : x2;
|
S2 is inserted at the top of basic block's statement list.
|
S2 is inserted at the top of basic block's statement list.
|
When COND is true, phi arg from TRUE_BB is selected.
|
When COND is true, phi arg from TRUE_BB is selected.
|
*/
|
*/
|
|
|
static void
|
static void
|
replace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb,
|
replace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb,
|
block_stmt_iterator *bsi)
|
block_stmt_iterator *bsi)
|
{
|
{
|
tree new_stmt;
|
tree new_stmt;
|
basic_block bb;
|
basic_block bb;
|
tree rhs;
|
tree rhs;
|
tree arg_0, arg_1;
|
tree arg_0, arg_1;
|
|
|
gcc_assert (TREE_CODE (phi) == PHI_NODE);
|
gcc_assert (TREE_CODE (phi) == PHI_NODE);
|
|
|
/* If this is not filtered earlier, then now it is too late. */
|
/* If this is not filtered earlier, then now it is too late. */
|
gcc_assert (PHI_NUM_ARGS (phi) == 2);
|
gcc_assert (PHI_NUM_ARGS (phi) == 2);
|
|
|
/* Find basic block and initialize iterator. */
|
/* Find basic block and initialize iterator. */
|
bb = bb_for_stmt (phi);
|
bb = bb_for_stmt (phi);
|
|
|
/* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
|
/* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
|
if (EDGE_PRED (bb, 1)->src == true_bb)
|
if (EDGE_PRED (bb, 1)->src == true_bb)
|
{
|
{
|
arg_0 = PHI_ARG_DEF (phi, 1);
|
arg_0 = PHI_ARG_DEF (phi, 1);
|
arg_1 = PHI_ARG_DEF (phi, 0);
|
arg_1 = PHI_ARG_DEF (phi, 0);
|
}
|
}
|
else
|
else
|
{
|
{
|
arg_0 = PHI_ARG_DEF (phi, 0);
|
arg_0 = PHI_ARG_DEF (phi, 0);
|
arg_1 = PHI_ARG_DEF (phi, 1);
|
arg_1 = PHI_ARG_DEF (phi, 1);
|
}
|
}
|
|
|
/* Build new RHS using selected condition and arguments. */
|
/* Build new RHS using selected condition and arguments. */
|
rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
|
rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
|
unshare_expr (cond), unshare_expr (arg_0),
|
unshare_expr (cond), unshare_expr (arg_0),
|
unshare_expr (arg_1));
|
unshare_expr (arg_1));
|
|
|
/* Create new MODIFY expression using RHS. */
|
/* Create new MODIFY expression using RHS. */
|
new_stmt = build2 (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
|
new_stmt = build2 (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
|
unshare_expr (PHI_RESULT (phi)), rhs);
|
unshare_expr (PHI_RESULT (phi)), rhs);
|
|
|
/* Make new statement definition of the original phi result. */
|
/* Make new statement definition of the original phi result. */
|
SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
|
SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
|
|
|
/* Insert using iterator. */
|
/* Insert using iterator. */
|
bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
|
bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
|
update_stmt (new_stmt);
|
update_stmt (new_stmt);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
fprintf (dump_file, "new phi replacement stmt\n");
|
fprintf (dump_file, "new phi replacement stmt\n");
|
print_generic_stmt (dump_file, new_stmt, TDF_SLIM);
|
print_generic_stmt (dump_file, new_stmt, TDF_SLIM);
|
}
|
}
|
}
|
}
|
|
|
/* Process phi nodes for the given LOOP. Replace phi nodes with cond
|
/* Process phi nodes for the given LOOP. Replace phi nodes with cond
|
modify expr. */
|
modify expr. */
|
|
|
static void
|
static void
|
process_phi_nodes (struct loop *loop)
|
process_phi_nodes (struct loop *loop)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
unsigned int orig_loop_num_nodes = loop->num_nodes;
|
unsigned int orig_loop_num_nodes = loop->num_nodes;
|
unsigned int i;
|
unsigned int i;
|
|
|
/* Replace phi nodes with cond. modify expr. */
|
/* Replace phi nodes with cond. modify expr. */
|
for (i = 1; i < orig_loop_num_nodes; i++)
|
for (i = 1; i < orig_loop_num_nodes; i++)
|
{
|
{
|
tree phi, cond;
|
tree phi, cond;
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
basic_block true_bb = NULL;
|
basic_block true_bb = NULL;
|
bb = ifc_bbs[i];
|
bb = ifc_bbs[i];
|
|
|
if (bb == loop->header)
|
if (bb == loop->header)
|
continue;
|
continue;
|
|
|
phi = phi_nodes (bb);
|
phi = phi_nodes (bb);
|
bsi = bsi_after_labels (bb);
|
bsi = bsi_after_labels (bb);
|
|
|
/* BB has two predecessors. Using predecessor's aux field, set
|
/* BB has two predecessors. Using predecessor's aux field, set
|
appropriate condition for the PHI node replacement. */
|
appropriate condition for the PHI node replacement. */
|
if (phi)
|
if (phi)
|
true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi);
|
true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi);
|
|
|
while (phi)
|
while (phi)
|
{
|
{
|
tree next = PHI_CHAIN (phi);
|
tree next = PHI_CHAIN (phi);
|
replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi);
|
replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi);
|
release_phi_node (phi);
|
release_phi_node (phi);
|
phi = next;
|
phi = next;
|
}
|
}
|
bb->phi_nodes = NULL;
|
bb->phi_nodes = NULL;
|
}
|
}
|
return;
|
return;
|
}
|
}
|
|
|
/* Combine all basic block from the given LOOP into one or two super
|
/* Combine all basic block from the given LOOP into one or two super
|
basic block. Replace PHI nodes with conditional modify expression. */
|
basic block. Replace PHI nodes with conditional modify expression. */
|
|
|
static void
|
static void
|
combine_blocks (struct loop *loop)
|
combine_blocks (struct loop *loop)
|
{
|
{
|
basic_block bb, exit_bb, merge_target_bb;
|
basic_block bb, exit_bb, merge_target_bb;
|
unsigned int orig_loop_num_nodes = loop->num_nodes;
|
unsigned int orig_loop_num_nodes = loop->num_nodes;
|
unsigned int i;
|
unsigned int i;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
/* Process phi nodes to prepare blocks for merge. */
|
/* Process phi nodes to prepare blocks for merge. */
|
process_phi_nodes (loop);
|
process_phi_nodes (loop);
|
|
|
/* Merge basic blocks. First remove all the edges in the loop, except
|
/* Merge basic blocks. First remove all the edges in the loop, except
|
for those from the exit block. */
|
for those from the exit block. */
|
exit_bb = NULL;
|
exit_bb = NULL;
|
for (i = 0; i < orig_loop_num_nodes; i++)
|
for (i = 0; i < orig_loop_num_nodes; i++)
|
{
|
{
|
bb = ifc_bbs[i];
|
bb = ifc_bbs[i];
|
if (bb_with_exit_edge_p (loop, bb))
|
if (bb_with_exit_edge_p (loop, bb))
|
{
|
{
|
exit_bb = bb;
|
exit_bb = bb;
|
break;
|
break;
|
}
|
}
|
}
|
}
|
gcc_assert (exit_bb != loop->latch);
|
gcc_assert (exit_bb != loop->latch);
|
|
|
for (i = 1; i < orig_loop_num_nodes; i++)
|
for (i = 1; i < orig_loop_num_nodes; i++)
|
{
|
{
|
bb = ifc_bbs[i];
|
bb = ifc_bbs[i];
|
|
|
for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
|
for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
|
{
|
{
|
if (e->src == exit_bb)
|
if (e->src == exit_bb)
|
ei_next (&ei);
|
ei_next (&ei);
|
else
|
else
|
remove_edge (e);
|
remove_edge (e);
|
}
|
}
|
}
|
}
|
|
|
if (exit_bb != NULL)
|
if (exit_bb != NULL)
|
{
|
{
|
if (exit_bb != loop->header)
|
if (exit_bb != loop->header)
|
{
|
{
|
/* Connect this node with loop header. */
|
/* Connect this node with loop header. */
|
make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
|
make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
|
set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
|
set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
|
}
|
}
|
|
|
/* Redirect non-exit edges to loop->latch. */
|
/* Redirect non-exit edges to loop->latch. */
|
FOR_EACH_EDGE (e, ei, exit_bb->succs)
|
FOR_EACH_EDGE (e, ei, exit_bb->succs)
|
{
|
{
|
if (!loop_exit_edge_p (loop, e))
|
if (!loop_exit_edge_p (loop, e))
|
redirect_edge_and_branch (e, loop->latch);
|
redirect_edge_and_branch (e, loop->latch);
|
}
|
}
|
set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
|
set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
|
}
|
}
|
else
|
else
|
{
|
{
|
/* If the loop does not have exit then reconnect header and latch. */
|
/* If the loop does not have exit then reconnect header and latch. */
|
make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
|
make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
|
set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
|
set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
|
}
|
}
|
|
|
merge_target_bb = loop->header;
|
merge_target_bb = loop->header;
|
for (i = 1; i < orig_loop_num_nodes; i++)
|
for (i = 1; i < orig_loop_num_nodes; i++)
|
{
|
{
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
tree_stmt_iterator last;
|
tree_stmt_iterator last;
|
|
|
bb = ifc_bbs[i];
|
bb = ifc_bbs[i];
|
|
|
if (bb == exit_bb || bb == loop->latch)
|
if (bb == exit_bb || bb == loop->latch)
|
continue;
|
continue;
|
|
|
/* Remove labels and make stmts member of loop->header. */
|
/* Remove labels and make stmts member of loop->header. */
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
|
{
|
{
|
if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
|
if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
|
bsi_remove (&bsi, true);
|
bsi_remove (&bsi, true);
|
else
|
else
|
{
|
{
|
set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
|
set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
|
bsi_next (&bsi);
|
bsi_next (&bsi);
|
}
|
}
|
}
|
}
|
|
|
/* Update stmt list. */
|
/* Update stmt list. */
|
last = tsi_last (merge_target_bb->stmt_list);
|
last = tsi_last (merge_target_bb->stmt_list);
|
tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT);
|
tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT);
|
bb->stmt_list = NULL;
|
bb->stmt_list = NULL;
|
|
|
/* Update dominator info. */
|
/* Update dominator info. */
|
if (dom_computed[CDI_DOMINATORS])
|
if (dom_computed[CDI_DOMINATORS])
|
delete_from_dominance_info (CDI_DOMINATORS, bb);
|
delete_from_dominance_info (CDI_DOMINATORS, bb);
|
if (dom_computed[CDI_POST_DOMINATORS])
|
if (dom_computed[CDI_POST_DOMINATORS])
|
delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
|
delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
|
|
|
/* Remove basic block. */
|
/* Remove basic block. */
|
remove_bb_from_loops (bb);
|
remove_bb_from_loops (bb);
|
expunge_block (bb);
|
expunge_block (bb);
|
}
|
}
|
|
|
/* Now if possible, merge loop header and block with exit edge.
|
/* Now if possible, merge loop header and block with exit edge.
|
This reduces number of basic blocks to 2. Auto vectorizer addresses
|
This reduces number of basic blocks to 2. Auto vectorizer addresses
|
loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */
|
loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */
|
if (exit_bb
|
if (exit_bb
|
&& exit_bb != loop->header
|
&& exit_bb != loop->header
|
&& can_merge_blocks_p (loop->header, exit_bb))
|
&& can_merge_blocks_p (loop->header, exit_bb))
|
{
|
{
|
remove_bb_from_loops (exit_bb);
|
remove_bb_from_loops (exit_bb);
|
merge_blocks (loop->header, exit_bb);
|
merge_blocks (loop->header, exit_bb);
|
}
|
}
|
}
|
}
|
|
|
/* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP
|
/* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP
|
to the new variable. */
|
to the new variable. */
|
|
|
static tree
|
static tree
|
ifc_temp_var (tree type, tree exp)
|
ifc_temp_var (tree type, tree exp)
|
{
|
{
|
const char *name = "_ifc_";
|
const char *name = "_ifc_";
|
tree var, stmt, new_name;
|
tree var, stmt, new_name;
|
|
|
if (is_gimple_reg (exp))
|
if (is_gimple_reg (exp))
|
return exp;
|
return exp;
|
|
|
/* Create new temporary variable. */
|
/* Create new temporary variable. */
|
var = create_tmp_var (type, name);
|
var = create_tmp_var (type, name);
|
add_referenced_var (var);
|
add_referenced_var (var);
|
|
|
/* Build new statement to assign EXP to new variable. */
|
/* Build new statement to assign EXP to new variable. */
|
stmt = build2 (MODIFY_EXPR, type, var, exp);
|
stmt = build2 (MODIFY_EXPR, type, var, exp);
|
|
|
/* Get SSA name for the new variable and set make new statement
|
/* Get SSA name for the new variable and set make new statement
|
its definition statement. */
|
its definition statement. */
|
new_name = make_ssa_name (var, stmt);
|
new_name = make_ssa_name (var, stmt);
|
TREE_OPERAND (stmt, 0) = new_name;
|
TREE_OPERAND (stmt, 0) = new_name;
|
SSA_NAME_DEF_STMT (new_name) = stmt;
|
SSA_NAME_DEF_STMT (new_name) = stmt;
|
|
|
return stmt;
|
return stmt;
|
}
|
}
|
|
|
|
|
/* Return TRUE iff, all pred blocks of BB are visited.
|
/* Return TRUE iff, all pred blocks of BB are visited.
|
Bitmap VISITED keeps history of visited blocks. */
|
Bitmap VISITED keeps history of visited blocks. */
|
|
|
static bool
|
static bool
|
pred_blocks_visited_p (basic_block bb, bitmap *visited)
|
pred_blocks_visited_p (basic_block bb, bitmap *visited)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
if (!bitmap_bit_p (*visited, e->src->index))
|
if (!bitmap_bit_p (*visited, e->src->index))
|
return false;
|
return false;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Get body of a LOOP in suitable order for if-conversion.
|
/* Get body of a LOOP in suitable order for if-conversion.
|
It is caller's responsibility to deallocate basic block
|
It is caller's responsibility to deallocate basic block
|
list. If-conversion suitable order is, BFS order with one
|
list. If-conversion suitable order is, BFS order with one
|
additional constraint. Select block in BFS block, if all
|
additional constraint. Select block in BFS block, if all
|
pred are already selected. */
|
pred are already selected. */
|
|
|
static basic_block *
|
static basic_block *
|
get_loop_body_in_if_conv_order (const struct loop *loop)
|
get_loop_body_in_if_conv_order (const struct loop *loop)
|
{
|
{
|
basic_block *blocks, *blocks_in_bfs_order;
|
basic_block *blocks, *blocks_in_bfs_order;
|
basic_block bb;
|
basic_block bb;
|
bitmap visited;
|
bitmap visited;
|
unsigned int index = 0;
|
unsigned int index = 0;
|
unsigned int visited_count = 0;
|
unsigned int visited_count = 0;
|
|
|
gcc_assert (loop->num_nodes);
|
gcc_assert (loop->num_nodes);
|
gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
|
|
blocks = XCNEWVEC (basic_block, loop->num_nodes);
|
blocks = XCNEWVEC (basic_block, loop->num_nodes);
|
visited = BITMAP_ALLOC (NULL);
|
visited = BITMAP_ALLOC (NULL);
|
|
|
blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
|
blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
|
|
|
index = 0;
|
index = 0;
|
while (index < loop->num_nodes)
|
while (index < loop->num_nodes)
|
{
|
{
|
bb = blocks_in_bfs_order [index];
|
bb = blocks_in_bfs_order [index];
|
|
|
if (bb->flags & BB_IRREDUCIBLE_LOOP)
|
if (bb->flags & BB_IRREDUCIBLE_LOOP)
|
{
|
{
|
free (blocks_in_bfs_order);
|
free (blocks_in_bfs_order);
|
BITMAP_FREE (visited);
|
BITMAP_FREE (visited);
|
free (blocks);
|
free (blocks);
|
return NULL;
|
return NULL;
|
}
|
}
|
if (!bitmap_bit_p (visited, bb->index))
|
if (!bitmap_bit_p (visited, bb->index))
|
{
|
{
|
if (pred_blocks_visited_p (bb, &visited)
|
if (pred_blocks_visited_p (bb, &visited)
|
|| bb == loop->header)
|
|| bb == loop->header)
|
{
|
{
|
/* This block is now visited. */
|
/* This block is now visited. */
|
bitmap_set_bit (visited, bb->index);
|
bitmap_set_bit (visited, bb->index);
|
blocks[visited_count++] = bb;
|
blocks[visited_count++] = bb;
|
}
|
}
|
}
|
}
|
index++;
|
index++;
|
if (index == loop->num_nodes
|
if (index == loop->num_nodes
|
&& visited_count != loop->num_nodes)
|
&& visited_count != loop->num_nodes)
|
{
|
{
|
/* Not done yet. */
|
/* Not done yet. */
|
index = 0;
|
index = 0;
|
}
|
}
|
}
|
}
|
free (blocks_in_bfs_order);
|
free (blocks_in_bfs_order);
|
BITMAP_FREE (visited);
|
BITMAP_FREE (visited);
|
return blocks;
|
return blocks;
|
}
|
}
|
|
|
/* Return true if one of the basic block BB edge is exit of LOOP. */
|
/* Return true if one of the basic block BB edge is exit of LOOP. */
|
|
|
static bool
|
static bool
|
bb_with_exit_edge_p (struct loop *loop, basic_block bb)
|
bb_with_exit_edge_p (struct loop *loop, basic_block bb)
|
{
|
{
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
bool exit_edge_found = false;
|
bool exit_edge_found = false;
|
|
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
if (loop_exit_edge_p (loop, e))
|
if (loop_exit_edge_p (loop, e))
|
{
|
{
|
exit_edge_found = true;
|
exit_edge_found = true;
|
break;
|
break;
|
}
|
}
|
|
|
return exit_edge_found;
|
return exit_edge_found;
|
}
|
}
|
|
|
/* Tree if-conversion pass management. */
|
/* Tree if-conversion pass management. */
|
|
|
static unsigned int
|
static unsigned int
|
main_tree_if_conversion (void)
|
main_tree_if_conversion (void)
|
{
|
{
|
unsigned i, loop_num;
|
unsigned i, loop_num;
|
struct loop *loop;
|
struct loop *loop;
|
|
|
if (!current_loops)
|
if (!current_loops)
|
return 0;
|
return 0;
|
|
|
loop_num = current_loops->num;
|
loop_num = current_loops->num;
|
for (i = 0; i < loop_num; i++)
|
for (i = 0; i < loop_num; i++)
|
{
|
{
|
loop = current_loops->parray[i];
|
loop = current_loops->parray[i];
|
if (!loop)
|
if (!loop)
|
continue;
|
continue;
|
|
|
tree_if_conversion (loop, true);
|
tree_if_conversion (loop, true);
|
}
|
}
|
return 0;
|
return 0;
|
}
|
}
|
|
|
static bool
|
static bool
|
gate_tree_if_conversion (void)
|
gate_tree_if_conversion (void)
|
{
|
{
|
return flag_tree_vectorize != 0;
|
return flag_tree_vectorize != 0;
|
}
|
}
|
|
|
struct tree_opt_pass pass_if_conversion =
|
struct tree_opt_pass pass_if_conversion =
|
{
|
{
|
"ifcvt", /* name */
|
"ifcvt", /* name */
|
gate_tree_if_conversion, /* gate */
|
gate_tree_if_conversion, /* gate */
|
main_tree_if_conversion, /* execute */
|
main_tree_if_conversion, /* execute */
|
NULL, /* sub */
|
NULL, /* sub */
|
NULL, /* next */
|
NULL, /* next */
|
0, /* static_pass_number */
|
0, /* static_pass_number */
|
0, /* tv_id */
|
0, /* tv_id */
|
PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
|
PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
|
0, /* properties_provided */
|
0, /* properties_provided */
|
0, /* properties_destroyed */
|
0, /* properties_destroyed */
|
0, /* todo_flags_start */
|
0, /* todo_flags_start */
|
TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow,
|
TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow,
|
/* todo_flags_finish */
|
/* todo_flags_finish */
|
0 /* letter */
|
0 /* letter */
|
};
|
};
|
|
|
