#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
#include "toplev.h"
#include "flags.h"
#include "function.h"
#include "expr.h"
#include "ggc.h"
#include "langhooks.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "timevar.h"
#include "tree-dump.h"
#include "tree-pass.h"
#include "toplev.h"
#include "except.h"
#include "cfgloop.h"
#include "cfglayout.h"
#include "hashtab.h"
#include "tree-ssa-propagate.h"
#include "tree-scalar-evolution.h"
static bool
remove_fallthru_edge (VEC(edge,gc) *ev)
{
edge_iterator ei;
edge e;
FOR_EACH_EDGE (e, ei, ev)
if ((e->flags & EDGE_FALLTHRU) != 0)
{
remove_edge (e);
return true;
}
return false;
}
static bool
cleanup_control_expr_graph (basic_block bb, block_stmt_iterator bsi)
{
edge taken_edge;
bool retval = false;
tree expr = bsi_stmt (bsi), val;
if (!single_succ_p (bb))
{
edge e;
edge_iterator ei;
bool warned;
fold_defer_overflow_warnings ();
switch (TREE_CODE (expr))
{
case COND_EXPR:
val = fold (COND_EXPR_COND (expr));
break;
case SWITCH_EXPR:
val = fold (SWITCH_COND (expr));
if (TREE_CODE (val) != INTEGER_CST)
{
fold_undefer_and_ignore_overflow_warnings ();
return false;
}
break;
default:
gcc_unreachable ();
}
taken_edge = find_taken_edge (bb, val);
if (!taken_edge)
{
fold_undefer_and_ignore_overflow_warnings ();
return false;
}
warned = false;
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
if (e != taken_edge)
{
if (!warned)
{
fold_undefer_overflow_warnings
(true, expr, WARN_STRICT_OVERFLOW_CONDITIONAL);
warned = true;
}
taken_edge->probability += e->probability;
taken_edge->count += e->count;
remove_edge (e);
retval = true;
}
else
ei_next (&ei);
}
if (!warned)
fold_undefer_and_ignore_overflow_warnings ();
if (taken_edge->probability > REG_BR_PROB_BASE)
taken_edge->probability = REG_BR_PROB_BASE;
}
else
taken_edge = single_succ_edge (bb);
bsi_remove (&bsi, true);
taken_edge->flags = EDGE_FALLTHRU;
free_dominance_info (CDI_DOMINATORS);
return retval;
}
VEC(tree,gc) *modified_noreturn_calls;
static bool
cleanup_control_flow (void)
{
basic_block bb;
block_stmt_iterator bsi;
bool retval = false;
tree stmt;
while (VEC_length (tree, modified_noreturn_calls))
{
stmt = VEC_pop (tree, modified_noreturn_calls);
bb = bb_for_stmt (stmt);
if (bb != NULL && last_stmt (bb) != stmt && noreturn_call_p (stmt))
split_block (bb, stmt);
}
FOR_EACH_BB (bb)
{
bsi = bsi_last (bb);
retval |= tree_purge_dead_eh_edges (bb);
if (bsi_end_p (bsi))
continue;
stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) == COND_EXPR
|| TREE_CODE (stmt) == SWITCH_EXPR)
retval |= cleanup_control_expr_graph (bb, bsi);
else if (TREE_CODE (stmt) == GOTO_EXPR
&& TREE_CODE (GOTO_DESTINATION (stmt)) == ADDR_EXPR
&& (TREE_CODE (TREE_OPERAND (GOTO_DESTINATION (stmt), 0))
== LABEL_DECL))
{
edge e;
tree label;
edge_iterator ei;
basic_block target_block;
bool removed_edge = false;
label = TREE_OPERAND (GOTO_DESTINATION (stmt), 0);
target_block = label_to_block (label);
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
if (e->dest != target_block)
{
removed_edge = true;
remove_edge (e);
}
else
{
e->flags &= ~EDGE_ABNORMAL;
e->flags |= EDGE_FALLTHRU;
ei_next (&ei);
}
}
if (removed_edge)
free_dominance_info (CDI_DOMINATORS);
bsi_remove (&bsi, true);
retval = true;
}
else if (noreturn_call_p (stmt) && remove_fallthru_edge (bb->succs))
{
free_dominance_info (CDI_DOMINATORS);
retval = true;
}
}
return retval;
}
static bool
tree_forwarder_block_p (basic_block bb, bool phi_wanted)
{
block_stmt_iterator bsi;
edge_iterator ei;
edge e, succ;
basic_block dest;
if (single_succ_p (bb) != 1
|| (phi_nodes (bb) != NULL_TREE) != phi_wanted
|| single_succ (bb) == EXIT_BLOCK_PTR
|| single_succ (bb) == bb
|| (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
return false;
#if ENABLE_CHECKING
gcc_assert (bb != ENTRY_BLOCK_PTR);
#endif
for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
{
tree stmt = bsi_stmt (bsi);
switch (TREE_CODE (stmt))
{
case LABEL_EXPR:
if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
return false;
break;
default:
return false;
}
}
if (find_edge (ENTRY_BLOCK_PTR, bb))
return false;
if (current_loops)
{
basic_block dest;
if (bb->loop_father->header == bb)
return false;
dest = EDGE_SUCC (bb, 0)->dest;
if (dest->loop_father->header == dest)
return false;
}
succ = single_succ_edge (bb);
dest = succ->dest;
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (e->flags & EDGE_EH)
{
if (!single_pred_p (dest))
return false;
}
}
return true;
}
static inline bool
has_abnormal_incoming_edge_p (basic_block bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->preds)
if (e->flags & EDGE_ABNORMAL)
return true;
return false;
}
static bool
phi_alternatives_equal (basic_block dest, edge e1, edge e2)
{
int n1 = e1->dest_idx;
int n2 = e2->dest_idx;
tree phi;
for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
{
tree val1 = PHI_ARG_DEF (phi, n1);
tree val2 = PHI_ARG_DEF (phi, n2);
gcc_assert (val1 != NULL_TREE);
gcc_assert (val2 != NULL_TREE);
if (!operand_equal_for_phi_arg_p (val1, val2))
return false;
}
return true;
}
static bool
remove_forwarder_block (basic_block bb, basic_block **worklist)
{
edge succ = single_succ_edge (bb), e, s;
basic_block dest = succ->dest;
tree label;
tree phi;
edge_iterator ei;
block_stmt_iterator bsi, bsi_to;
bool seen_abnormal_edge = false;
if (dest == bb)
return false;
label = first_stmt (dest);
if (label
&& TREE_CODE (label) == LABEL_EXPR
&& DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
return false;
if (has_abnormal_incoming_edge_p (bb))
{
seen_abnormal_edge = true;
if (has_abnormal_incoming_edge_p (dest)
|| phi_nodes (dest) != NULL_TREE)
return false;
}
if (phi_nodes (dest))
{
FOR_EACH_EDGE (e, ei, bb->preds)
{
s = find_edge (e->src, dest);
if (!s)
continue;
if (!phi_alternatives_equal (dest, succ, s))
return false;
}
}
for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
{
if (e->flags & EDGE_ABNORMAL)
{
s = redirect_edge_succ_nodup (e, dest);
}
else
s = redirect_edge_and_branch (e, dest);
if (s == e)
{
for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
add_phi_arg (phi, PHI_ARG_DEF (phi, succ->dest_idx), s);
}
else
{
if (tree_forwarder_block_p (s->src, false))
*(*worklist)++ = s->src;
}
}
if (seen_abnormal_edge)
{
bsi_to = bsi_start (dest);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
{
label = bsi_stmt (bsi);
gcc_assert (TREE_CODE (label) == LABEL_EXPR);
bsi_remove (&bsi, false);
bsi_insert_before (&bsi_to, label, BSI_CONTINUE_LINKING);
}
}
if (dom_info_available_p (CDI_DOMINATORS))
{
basic_block dom, dombb, domdest;
dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
if (domdest == bb)
{
dom = dombb;
}
else
dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
set_immediate_dominator (CDI_DOMINATORS, dest, dom);
}
delete_basic_block (bb);
return true;
}
static bool
cleanup_forwarder_blocks (void)
{
basic_block bb;
bool changed = false;
basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
basic_block *current = worklist;
FOR_EACH_BB (bb)
{
if (tree_forwarder_block_p (bb, false))
*current++ = bb;
}
while (current != worklist)
{
bb = *--current;
changed |= remove_forwarder_block (bb, ¤t);
}
free (worklist);
return changed;
}
static bool
cleanup_tree_cfg_1 (void)
{
bool retval;
retval = cleanup_control_flow ();
retval |= delete_unreachable_blocks ();
if (optimize > 0)
{
start_recording_case_labels ();
retval |= cleanup_forwarder_blocks ();
end_recording_case_labels ();
}
retval |= merge_seq_blocks ();
return retval;
}
bool
cleanup_tree_cfg (void)
{
bool retval, changed;
timevar_push (TV_TREE_CLEANUP_CFG);
changed = false;
do
{
retval = cleanup_tree_cfg_1 ();
changed |= retval;
}
while (retval);
compact_blocks ();
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
timevar_pop (TV_TREE_CLEANUP_CFG);
return changed;
}
void
cleanup_tree_cfg_loop (void)
{
bool changed = cleanup_tree_cfg ();
if (changed)
{
bitmap changed_bbs = BITMAP_ALLOC (NULL);
fix_loop_structure (current_loops, changed_bbs);
calculate_dominance_info (CDI_DOMINATORS);
rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
BITMAP_FREE (changed_bbs);
#ifdef ENABLE_CHECKING
verify_loop_structure (current_loops);
#endif
scev_reset ();
}
}
static void
remove_forwarder_block_with_phi (basic_block bb)
{
edge succ = single_succ_edge (bb);
basic_block dest = succ->dest;
tree label;
basic_block dombb, domdest, dom;
if (dest == bb)
return;
label = first_stmt (dest);
if (label
&& TREE_CODE (label) == LABEL_EXPR
&& DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
return;
while (EDGE_COUNT (bb->preds) > 0)
{
edge e = EDGE_PRED (bb, 0), s;
tree phi;
s = find_edge (e->src, dest);
if (s)
{
if (phi_alternatives_equal (dest, s, succ))
{
e = redirect_edge_and_branch (e, dest);
PENDING_STMT (e) = NULL_TREE;
continue;
}
e = single_succ_edge (split_edge (e));
}
s = redirect_edge_and_branch (e, dest);
gcc_assert (s == e);
for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
{
tree def = PHI_ARG_DEF (phi, succ->dest_idx);
if (TREE_CODE (def) == SSA_NAME)
{
tree var;
for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var))
{
tree old_arg = TREE_PURPOSE (var);
tree new_arg = TREE_VALUE (var);
if (def == old_arg)
{
def = new_arg;
break;
}
}
}
add_phi_arg (phi, def, s);
}
PENDING_STMT (e) = NULL;
}
dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
if (domdest == bb)
{
dom = dombb;
}
else
dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
set_immediate_dominator (CDI_DOMINATORS, dest, dom);
delete_basic_block (bb);
}
static unsigned int
merge_phi_nodes (void)
{
basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
basic_block *current = worklist;
basic_block bb;
calculate_dominance_info (CDI_DOMINATORS);
FOR_EACH_BB (bb)
{
basic_block dest;
if (!tree_forwarder_block_p (bb, true))
continue;
dest = single_succ (bb);
if (!phi_nodes (dest)
|| has_abnormal_incoming_edge_p (bb))
continue;
if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
{
*current++ = bb;
}
else
{
tree phi;
unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree result = PHI_RESULT (phi);
use_operand_p imm_use;
tree use_stmt;
if (has_zero_uses (result))
continue;
if (!single_imm_use (result, &imm_use, &use_stmt)
|| TREE_CODE (use_stmt) != PHI_NODE
|| bb_for_stmt (use_stmt) != dest
|| PHI_ARG_DEF (use_stmt, dest_idx) != result)
break;
}
if (!phi)
*current++ = bb;
}
}
while (current != worklist)
{
bb = *--current;
remove_forwarder_block_with_phi (bb);
}
free (worklist);
return 0;
}
static bool
gate_merge_phi (void)
{
return 1;
}
struct tree_opt_pass pass_merge_phi = {
"mergephi",
gate_merge_phi,
merge_phi_nodes,
NULL,
NULL,
0,
TV_TREE_MERGE_PHI,
PROP_cfg | PROP_ssa,
0,
0,
0,
TODO_dump_func | TODO_ggc_collect
| TODO_verify_ssa,
0
};