#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 "diagnostic.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "tree-pass.h"
#include "timevar.h"
#include "cfgloop.h"
#include "tree-inline.h"
#include "flags.h"
#include "tree-inline.h"
struct loops *
tree_loop_optimizer_init (FILE *dump, bool canonicalize_ssa)
{
struct loops *loops = loop_optimizer_init (dump);
if (!loops)
return NULL;
if (!canonicalize_ssa)
return loops;
kill_redundant_phi_nodes ();
rewrite_into_ssa (false);
bitmap_clear (vars_to_rename);
rewrite_into_loop_closed_ssa ();
#ifdef ENABLE_CHECKING
verify_loop_closed_ssa ();
#endif
return loops;
}
static void
tree_ssa_loop_opt (void)
{
struct loops *loops;
loops = tree_loop_optimizer_init (dump_file, true);
if (loops)
{
#if 0
test_unrolling_and_peeling (loops);
#endif
#if 0
test_loop_versioning (loops);
#endif
tree_ssa_lim (loops);
if (flag_unswitch_loops)
tree_ssa_unswitch_loops (loops);
tree_ssa_iv_optimize (loops);
loop_optimizer_finalize (loops,
(dump_flags & TDF_DETAILS ? dump_file : NULL));
cleanup_tree_cfg ();
}
}
static bool
gate_loop (void)
{
return flag_tree_loop != 0;
}
struct tree_opt_pass pass_loop =
{
"loop",
gate_loop,
tree_ssa_loop_opt,
NULL,
NULL,
0,
TV_TREE_LOOP,
PROP_cfg,
0,
0,
TODO_ggc_collect,
TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect
};
static bool
should_duplicate_loop_header_p (basic_block header, struct loop *loop,
int *limit)
{
block_stmt_iterator bsi;
tree last;
if (header->aux)
return false;
if (!header->succ)
abort ();
if (!header->succ->succ_next)
return false;
if (header->succ->succ_next->succ_next)
return false;
if (flow_bb_inside_loop_p (loop, header->succ->dest)
&& flow_bb_inside_loop_p (loop, header->succ->succ_next->dest))
return false;
if (header != loop->header
&& header->pred->pred_next)
return false;
last = last_stmt (header);
if (TREE_CODE (last) != COND_EXPR)
return false;
for (bsi = bsi_start (header); !bsi_end_p (bsi); bsi_next (&bsi))
{
last = bsi_stmt (bsi);
if (TREE_CODE (last) == LABEL_EXPR)
continue;
if (get_call_expr_in (last))
return false;
*limit -= estimate_num_insns (last);
if (*limit < 0)
return false;
}
return true;
}
static void
mark_defs_for_rewrite (basic_block bb)
{
tree stmt, var;
block_stmt_iterator bsi;
stmt_ann_t ann;
def_optype defs;
vdef_optype vdefs;
vuse_optype vuses;
unsigned i;
for (stmt = phi_nodes (bb); stmt; stmt = TREE_CHAIN (stmt))
{
var = SSA_NAME_VAR (PHI_RESULT (stmt));
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
var = var_ann (var)->type_mem_tag;
if (var)
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
}
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt = bsi_stmt (bsi);
get_stmt_operands (stmt);
ann = stmt_ann (stmt);
defs = DEF_OPS (ann);
for (i = 0; i < NUM_DEFS (defs); i++)
{
var = SSA_NAME_VAR (DEF_OP (defs, i));
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
var = var_ann (var)->type_mem_tag;
if (var)
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
}
vdefs = VDEF_OPS (ann);
for (i = 0; i < NUM_VDEFS (vdefs); i++)
{
var = SSA_NAME_VAR (VDEF_RESULT (vdefs, i));
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
}
vuses = VUSE_OPS (ann);
for (i = 0; i < NUM_VUSES (vuses); i++)
{
var = SSA_NAME_VAR (VUSE_OP (vuses, i));
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
}
}
}
static void
duplicate_blocks (varray_type bbs_to_duplicate)
{
unsigned i;
edge preheader_edge, e, e1;
basic_block header, new_header;
tree phi;
size_t old_num_referenced_vars = num_referenced_vars;
for (i = 0; i < VARRAY_ACTIVE_SIZE (bbs_to_duplicate); i++)
{
preheader_edge = VARRAY_GENERIC_PTR_NOGC (bbs_to_duplicate, i);
header = preheader_edge->dest;
mark_defs_for_rewrite (header);
}
rewrite_vars_out_of_ssa (vars_to_rename);
for (i = old_num_referenced_vars; i < num_referenced_vars; i++)
{
bitmap_set_bit (vars_to_rename, i);
var_ann (referenced_var (i))->out_of_ssa_tag = 0;
}
for (i = 0; i < VARRAY_ACTIVE_SIZE (bbs_to_duplicate); i++)
{
preheader_edge = VARRAY_GENERIC_PTR_NOGC (bbs_to_duplicate, i);
header = preheader_edge->dest;
while (!header->aux)
{
preheader_edge = header->succ;
header = preheader_edge->dest;
}
header->aux = NULL;
new_header = duplicate_block (header, preheader_edge);
for (e = header->succ; e; e = e->succ_next)
{
for (e1 = new_header->succ; e1->dest != e->dest; e1 = e1->succ_next)
continue;
for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
{
tree def = phi_element_for_edge (phi, e)->def;
add_phi_arg (&phi, def, e1);
}
}
}
}
static bool
do_while_loop_p (struct loop *loop)
{
tree stmt = last_stmt (loop->latch);
if (stmt
&& TREE_CODE (stmt) != LABEL_EXPR)
return false;
stmt = last_and_only_stmt (loop->header);
if (stmt
&& TREE_CODE (stmt) == COND_EXPR)
return false;
return true;
}
static void
copy_loop_headers (void)
{
struct loops *loops;
unsigned i;
struct loop *loop;
basic_block header;
edge preheader_edge;
varray_type bbs_to_duplicate = NULL;
loops = tree_loop_optimizer_init (dump_file, false);
if (!loops)
return;
free_dominance_info (CDI_DOMINATORS);
loops->state &= ~LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
#ifdef ENABLE_CHECKING
verify_loop_structure (loops);
#endif
for (i = 1; i < loops->num; i++)
{
int limit = 20;
loop = loops->parray[i];
preheader_edge = loop_preheader_edge (loop);
header = preheader_edge->dest;
if (do_while_loop_p (loop))
continue;
while (should_duplicate_loop_header_p (header, loop, &limit))
{
if (!bbs_to_duplicate)
VARRAY_GENERIC_PTR_NOGC_INIT (bbs_to_duplicate, 10,
"bbs_to_duplicate");
VARRAY_PUSH_GENERIC_PTR_NOGC (bbs_to_duplicate, preheader_edge);
header->aux = &header->aux;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
"Scheduled basic block %d for duplication.\n",
header->index);
if (flow_bb_inside_loop_p (loop, header->succ->dest))
preheader_edge = header->succ;
else
preheader_edge = header->succ->succ_next;
header = preheader_edge->dest;
}
}
loop_optimizer_finalize (loops, NULL);
if (bbs_to_duplicate)
{
duplicate_blocks (bbs_to_duplicate);
VARRAY_FREE (bbs_to_duplicate);
}
cleanup_tree_cfg ();
}
static bool
gate_ch (void)
{
return flag_tree_ch != 0;
}
struct tree_opt_pass pass_ch =
{
"ch",
gate_ch,
copy_loop_headers,
NULL,
NULL,
0,
TV_TREE_CH,
PROP_cfg | PROP_ssa,
0,
0,
0,
(TODO_rename_vars
| TODO_dump_func
| TODO_verify_ssa)
};