You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "errors.h"
#include "ggc.h"
#include "tree.h"
#include "rtl.h"
#include "tree-dump.h"
#include "langhooks.h"
-static void tree_ssa_phiopt (void);
-static bool conditional_replacement (basic_block, basic_block, basic_block,
+static unsigned int tree_ssa_phiopt (void);
+static bool conditional_replacement (basic_block, basic_block,
edge, edge, tree, tree, tree);
-static bool value_replacement (basic_block, basic_block, basic_block,
+static bool value_replacement (basic_block, basic_block,
edge, edge, tree, tree, tree);
-static bool minmax_replacement (basic_block, basic_block, basic_block,
+static bool minmax_replacement (basic_block, basic_block,
edge, edge, tree, tree, tree);
-static bool abs_replacement (basic_block, basic_block, basic_block,
+static bool abs_replacement (basic_block, basic_block,
edge, edge, tree, tree, tree);
-static void replace_phi_edge_with_variable (basic_block, basic_block, edge,
- tree, tree);
+static void replace_phi_edge_with_variable (basic_block, edge, tree, tree);
static basic_block *blocks_in_phiopt_order (void);
-/* This pass eliminates PHI nodes which can be trivially implemented as
- an assignment from a conditional expression. i.e. if we have something
- like:
+/* This pass tries to replaces an if-then-else block with an
+ assignment. We have four kinds of transformations. Some of these
+ transformations are also performed by the ifcvt RTL optimizer.
+
+ Conditional Replacement
+ -----------------------
+
+ This transformation, implemented in conditional_replacement,
+ replaces
bb0:
if (cond) goto bb2; else goto bb1;
bb1:
bb2:
- x = PHI (0 (bb1), 1 (bb0)
+ x = PHI <0 (bb1), 1 (bb0), ...>;
- We can rewrite that as:
+ with
bb0:
- bb1:
+ x' = cond;
+ goto bb2;
bb2:
- x = cond;
+ x = PHI <x' (bb0), ...>;
+
+ We remove bb1 as it becomes unreachable. This occurs often due to
+ gimplification of conditionals.
- bb1 will become unreachable and bb0 and bb2 will almost always
- be merged into a single block. This occurs often due to gimplification
- of conditionals.
+ Value Replacement
+ -----------------
- Also done is the following optimization:
+ This transformation, implemented in value_replacement, replaces
bb0:
- if (a != b) goto bb2; else goto bb1;
+ if (a != b) goto bb2; else goto bb1;
bb1:
bb2:
- x = PHI (a (bb1), b (bb0))
+ x = PHI <a (bb1), b (bb0), ...>;
- We can rewrite that as:
+ with
bb0:
- bb1:
bb2:
- x = b;
+ x = PHI <b (bb0), ...>;
+
+ This opportunity can sometimes occur as a result of other
+ optimizations.
- This can sometimes occur as a result of other optimizations. A
- similar transformation is done by the ifcvt RTL optimizer.
+ ABS Replacement
+ ---------------
- This pass also eliminates PHI nodes which are really absolute
- values. i.e. if we have something like:
+ This transformation, implemented in abs_replacement, replaces
bb0:
- if (a >= 0) goto bb2; else goto bb1;
+ if (a >= 0) goto bb2; else goto bb1;
bb1:
- x = -a;
+ x = -a;
bb2:
- x = PHI (x (bb1), a (bb0));
+ x = PHI <x (bb1), a (bb0), ...>;
- We can rewrite that as:
+ with
bb0:
- bb1:
+ x' = ABS_EXPR< a >;
bb2:
- x = ABS_EXPR< a >;
+ x = PHI <x' (bb0), ...>;
- Similarly,
+ MIN/MAX Replacement
+ -------------------
+
+ This transformation, minmax_replacement replaces
bb0:
- if (a <= b) goto bb2; else goto bb1;
+ if (a <= b) goto bb2; else goto bb1;
bb1:
- goto bb2;
bb2:
- x = PHI (b (bb1), a (bb0));
+ x = PHI <b (bb1), a (bb0), ...>;
- Becomes
+ with
- x = MIN_EXPR (a, b)
-
- And the same transformation for MAX_EXPR.
+ bb0:
+ x' = MIN_EXPR (a, b)
+ bb2:
+ x = PHI <x' (bb0), ...>;
- bb1 will become unreachable and bb0 and bb2 will almost always be merged
- into a single block. Similar transformations are done by the ifcvt
- RTL optimizer. */
+ A similar transformation is done for MAX_EXPR. */
-static void
+static unsigned int
tree_ssa_phiopt (void)
{
basic_block bb;
basic_block *bb_order;
unsigned n, i;
+ bool cfgchanged = false;
/* Search every basic block for COND_EXPR we may be able to optimize.
outer ones, and also that we do not try to visit a removed
block. */
bb_order = blocks_in_phiopt_order ();
- n = n_basic_blocks;
+ n = n_basic_blocks - NUM_FIXED_BLOCKS;
- for (i = 0; i < n; i++)
+ for (i = 0; i < n; i++)
{
tree cond_expr;
tree phi;
e1 = EDGE_SUCC (bb1, 0);
/* Make sure that bb1 is just a fall through. */
- if (!single_succ_p (bb1) > 1
+ if (!single_succ_p (bb1)
|| (e1->flags & EDGE_FALLTHRU) == 0)
continue;
- /* Also make that bb1 only have one pred and it is bb. */
+ /* Also make sure that bb1 only have one predecessor and that it
+ is bb. */
if (!single_pred_p (bb1)
|| single_pred (bb1) != bb)
continue;
arg0 = PHI_ARG_DEF_TREE (phi, e1->dest_idx);
arg1 = PHI_ARG_DEF_TREE (phi, e2->dest_idx);
- /* We know something is wrong if we cannot find the edges in the PHI
+ /* Something is wrong if we cannot find the arguments in the PHI
node. */
gcc_assert (arg0 != NULL && arg1 != NULL);
/* Do the replacement of conditional if it can be done. */
- if (conditional_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1))
- ;
- else if (value_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1))
- ;
- else if (abs_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1))
- ;
- else
- minmax_replacement (bb, bb1, bb2, e1, e2, phi, arg0, arg1);
+ if (conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
+ cfgchanged = true;
+ else if (value_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
+ cfgchanged = true;
+ else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
+ cfgchanged = true;
+ else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
+ cfgchanged = true;
}
free (bb_order);
+
+ /* If the CFG has changed, we should cleanup the CFG. */
+ return cfgchanged ? TODO_cleanup_cfg : 0;
}
/* Returns the list of basic blocks in the function in an order that guarantees
blocks_in_phiopt_order (void)
{
basic_block x, y;
- basic_block *order = xmalloc (sizeof (basic_block) * n_basic_blocks);
- unsigned n = n_basic_blocks, np, i;
- sbitmap visited = sbitmap_alloc (last_basic_block + 2);
+ basic_block *order = XNEWVEC (basic_block, n_basic_blocks);
+ unsigned n = n_basic_blocks - NUM_FIXED_BLOCKS;
+ unsigned np, i;
+ sbitmap visited = sbitmap_alloc (last_basic_block);
-#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index + 2))
-#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index + 2))
+#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
+#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
sbitmap_zero (visited);
return true;
}
-/* Replace PHI node element whoes edge is E in block BB with variable NEW.
+/* Replace PHI node element whose edge is E in block BB with variable NEW.
Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
is known to have two edges, one of which must reach BB). */
static void
-replace_phi_edge_with_variable (basic_block cond_block, basic_block bb,
+replace_phi_edge_with_variable (basic_block cond_block,
edge e, tree phi, tree new)
{
+ basic_block bb = bb_for_stmt (phi);
basic_block block_to_remove;
block_stmt_iterator bsi;
{
EDGE_SUCC (cond_block, 0)->flags |= EDGE_FALLTHRU;
EDGE_SUCC (cond_block, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+ EDGE_SUCC (cond_block, 0)->probability = REG_BR_PROB_BASE;
+ EDGE_SUCC (cond_block, 0)->count += EDGE_SUCC (cond_block, 1)->count;
block_to_remove = EDGE_SUCC (cond_block, 1)->dest;
}
EDGE_SUCC (cond_block, 1)->flags |= EDGE_FALLTHRU;
EDGE_SUCC (cond_block, 1)->flags
&= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+ EDGE_SUCC (cond_block, 1)->probability = REG_BR_PROB_BASE;
+ EDGE_SUCC (cond_block, 1)->count += EDGE_SUCC (cond_block, 0)->count;
block_to_remove = EDGE_SUCC (cond_block, 0)->dest;
}
/* Eliminate the COND_EXPR at the end of COND_BLOCK. */
bsi = bsi_last (cond_block);
- bsi_remove (&bsi);
+ bsi_remove (&bsi, true);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
static bool
conditional_replacement (basic_block cond_bb, basic_block middle_bb,
- basic_block phi_bb, edge e0, edge e1, tree phi,
+ edge e0, edge e1, tree phi,
tree arg0, tree arg1)
{
tree result;
if (TREE_CODE (cond) != SSA_NAME
&& !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
{
- new_var = make_rename_temp (TREE_TYPE (cond), NULL);
+ tree tmp;
+
+ if (!COMPARISON_CLASS_P (cond))
+ return false;
+
+ tmp = create_tmp_var (TREE_TYPE (cond), NULL);
+ add_referenced_var (tmp);
+ new_var = make_ssa_name (tmp, NULL);
old_result = cond;
cond = new_var;
}
if (old_result)
{
tree new1;
- if (!COMPARISON_CLASS_P (old_result))
- return false;
new1 = build2 (TREE_CODE (old_result), TREE_TYPE (old_result),
TREE_OPERAND (old_result, 0),
TREE_OPERAND (old_result, 1));
- new1 = build2 (MODIFY_EXPR, TREE_TYPE (old_result), new_var, new1);
+ new1 = build2_gimple (GIMPLE_MODIFY_STMT, new_var, new1);
+ SSA_NAME_DEF_STMT (new_var) = new1;
+
bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
}
|| (e1 == true_edge && integer_onep (arg1))
|| (e1 == false_edge && integer_zerop (arg1)))
{
- new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
+ new = build2_gimple (GIMPLE_MODIFY_STMT, new_var1, cond);
}
else
{
tree cond1 = invert_truthvalue (cond);
cond = cond1;
+
/* If what we get back is a conditional expression, there is no
way that it can be gimple. */
if (TREE_CODE (cond) == COND_EXPR)
return false;
}
+ /* If COND is not something we can expect to be reducible to a GIMPLE
+ condition, return early. */
+ if (is_gimple_cast (cond))
+ cond1 = TREE_OPERAND (cond, 0);
+ if (TREE_CODE (cond1) == TRUTH_NOT_EXPR
+ && !is_gimple_val (TREE_OPERAND (cond1, 0)))
+ {
+ release_ssa_name (new_var1);
+ return false;
+ }
+
/* If what we get back is not gimple try to create it as gimple by
using a temporary variable. */
if (is_gimple_cast (cond)
&& !is_gimple_val (TREE_OPERAND (cond, 0)))
{
- tree temp = TREE_OPERAND (cond, 0);
- tree new_var_1 = make_rename_temp (TREE_TYPE (temp), NULL);
- new = build2 (MODIFY_EXPR, TREE_TYPE (new_var_1), new_var_1, temp);
- bsi_insert_after (&bsi, new, BSI_NEW_STMT);
- cond = fold_convert (TREE_TYPE (result), new_var_1);
- }
+ tree op0, tmp, cond_tmp;
- if (TREE_CODE (cond) == TRUTH_NOT_EXPR
- && !is_gimple_val (TREE_OPERAND (cond, 0)))
- {
- release_ssa_name (new_var1);
- return false;
+ /* Only "real" casts are OK here, not everything that is
+ acceptable to is_gimple_cast. Make sure we don't do
+ anything stupid here. */
+ gcc_assert (TREE_CODE (cond) == NOP_EXPR
+ || TREE_CODE (cond) == CONVERT_EXPR);
+
+ op0 = TREE_OPERAND (cond, 0);
+ tmp = create_tmp_var (TREE_TYPE (op0), NULL);
+ add_referenced_var (tmp);
+ cond_tmp = make_ssa_name (tmp, NULL);
+ new = build2_gimple (GIMPLE_MODIFY_STMT, cond_tmp, op0);
+ SSA_NAME_DEF_STMT (cond_tmp) = new;
+
+ bsi_insert_after (&bsi, new, BSI_NEW_STMT);
+ cond = fold_convert (TREE_TYPE (result), cond_tmp);
}
- new = build2 (MODIFY_EXPR, TREE_TYPE (new_var1), new_var1, cond);
+ new = build2_gimple (GIMPLE_MODIFY_STMT, new_var1, cond);
}
bsi_insert_after (&bsi, new, BSI_NEW_STMT);
SSA_NAME_DEF_STMT (new_var1) = new;
- replace_phi_edge_with_variable (cond_bb, phi_bb, e1, phi, new_var1);
+ replace_phi_edge_with_variable (cond_bb, e1, phi, new_var1);
/* Note that we optimized this PHI. */
return true;
static bool
value_replacement (basic_block cond_bb, basic_block middle_bb,
- basic_block phi_bb, edge e0, edge e1, tree phi,
+ edge e0, edge e1, tree phi,
tree arg0, tree arg1)
{
tree cond;
else
arg = arg1;
- replace_phi_edge_with_variable (cond_bb, phi_bb, e1, phi, arg);
+ replace_phi_edge_with_variable (cond_bb, e1, phi, arg);
/* Note that we optimized this PHI. */
return true;
static bool
minmax_replacement (basic_block cond_bb, basic_block middle_bb,
- basic_block phi_bb, edge e0, edge e1, tree phi,
+ edge e0, edge e1, tree phi,
tree arg0, tree arg1)
{
tree result, type;
tree lhs, rhs, op0, op1, bound;
if (!assign
- || TREE_CODE (assign) != MODIFY_EXPR)
+ || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
return false;
- lhs = TREE_OPERAND (assign, 0);
- rhs = TREE_OPERAND (assign, 1);
+ lhs = GIMPLE_STMT_OPERAND (assign, 0);
+ rhs = GIMPLE_STMT_OPERAND (assign, 1);
ass_code = TREE_CODE (rhs);
if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
return false;
return false;
/* We need BOUND <= LARGER. */
- if (!integer_nonzerop (fold (build2 (LE_EXPR, boolean_type_node,
- bound, larger))))
+ if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
+ bound, larger)))
return false;
}
else if (operand_equal_for_phi_arg_p (arg_false, smaller))
return false;
/* We need BOUND >= SMALLER. */
- if (!integer_nonzerop (fold (build2 (GE_EXPR, boolean_type_node,
- bound, smaller))))
+ if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
+ bound, smaller)))
return false;
}
else
return false;
/* We need BOUND >= LARGER. */
- if (!integer_nonzerop (fold (build2 (GE_EXPR, boolean_type_node,
- bound, larger))))
+ if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node,
+ bound, larger)))
return false;
}
else if (operand_equal_for_phi_arg_p (arg_true, smaller))
return false;
/* We need BOUND <= SMALLER. */
- if (!integer_nonzerop (fold (build2 (LE_EXPR, boolean_type_node,
- bound, smaller))))
+ if (!integer_nonzerop (fold_build2 (LE_EXPR, boolean_type_node,
+ bound, smaller)))
return false;
}
else
/* Emit the statement to compute min/max. */
result = duplicate_ssa_name (PHI_RESULT (phi), NULL);
- new = build2 (MODIFY_EXPR, type, result,
- build2 (minmax, type, arg0, arg1));
+ new = build2_gimple (GIMPLE_MODIFY_STMT, result,
+ build2 (minmax, type, arg0, arg1));
SSA_NAME_DEF_STMT (result) = new;
bsi = bsi_last (cond_bb);
bsi_insert_before (&bsi, new, BSI_NEW_STMT);
- replace_phi_edge_with_variable (cond_bb, phi_bb, e1, phi, result);
+ replace_phi_edge_with_variable (cond_bb, e1, phi, result);
return true;
}
static bool
abs_replacement (basic_block cond_bb, basic_block middle_bb,
- basic_block phi_bb, edge e0 ATTRIBUTE_UNUSED, edge e1,
+ edge e0 ATTRIBUTE_UNUSED, edge e1,
tree phi, tree arg0, tree arg1)
{
tree result;
/* If we got here, then we have found the only executable statement
in OTHER_BLOCK. If it is anything other than arg = -arg1 or
arg1 = -arg0, then we can not optimize. */
- if (TREE_CODE (assign) != MODIFY_EXPR)
+ if (TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
return false;
- lhs = TREE_OPERAND (assign, 0);
- rhs = TREE_OPERAND (assign, 1);
+ lhs = GIMPLE_STMT_OPERAND (assign, 0);
+ rhs = GIMPLE_STMT_OPERAND (assign, 1);
if (TREE_CODE (rhs) != NEGATE_EXPR)
return false;
result = duplicate_ssa_name (result, NULL);
if (negate)
- lhs = make_rename_temp (TREE_TYPE (result), NULL);
+ {
+ tree tmp = create_tmp_var (TREE_TYPE (result), NULL);
+ add_referenced_var (tmp);
+ lhs = make_ssa_name (tmp, NULL);
+ }
else
lhs = result;
/* Build the modify expression with abs expression. */
- new = build2 (MODIFY_EXPR, TREE_TYPE (lhs),
- lhs, build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
+ new = build2_gimple (GIMPLE_MODIFY_STMT,
+ lhs, build1 (ABS_EXPR, TREE_TYPE (lhs), rhs));
+ SSA_NAME_DEF_STMT (lhs) = new;
bsi = bsi_last (cond_bb);
bsi_insert_before (&bsi, new, BSI_NEW_STMT);
/* Get the right BSI. We want to insert after the recently
added ABS_EXPR statement (which we know is the first statement
in the block. */
- new = build2 (MODIFY_EXPR, TREE_TYPE (result),
- result, build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs));
+ new = build2_gimple (GIMPLE_MODIFY_STMT,
+ result, build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs));
+ SSA_NAME_DEF_STMT (result) = new;
bsi_insert_after (&bsi, new, BSI_NEW_STMT);
}
- SSA_NAME_DEF_STMT (result) = new;
- replace_phi_edge_with_variable (cond_bb, phi_bb, e1, phi, result);
+ replace_phi_edge_with_variable (cond_bb, e1, phi, result);
/* Note that we optimized this PHI. */
return true;
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_cleanup_cfg
- | TODO_dump_func
+ TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
- | TODO_update_ssa
| TODO_verify_flow
| TODO_verify_stmts, /* todo_flags_finish */
0 /* letter */
OSDN Git Service
