+/*
+DEF_VEC_P(basic_block);
+DEF_VEC_ALLOC_P(basic_block,heap);
+*/
+
+/* Add all the blocks dominated by ENTRY to the array BBS_P. Stop
+ adding blocks when the dominator traversal reaches EXIT. This
+ function silently assumes that ENTRY strictly dominates EXIT. */
+
+static void
+gather_blocks_in_sese_region (basic_block entry, basic_block exit,
+ VEC(basic_block,heap) **bbs_p)
+{
+ basic_block son;
+
+ for (son = first_dom_son (CDI_DOMINATORS, entry);
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ {
+ VEC_safe_push (basic_block, heap, *bbs_p, son);
+ if (son != exit)
+ gather_blocks_in_sese_region (son, exit, bbs_p);
+ }
+}
+
+
+struct move_stmt_d
+{
+ tree block;
+ tree from_context;
+ tree to_context;
+ bitmap vars_to_remove;
+ htab_t new_label_map;
+ bool remap_decls_p;
+};
+
+/* Helper for move_block_to_fn. Set TREE_BLOCK in every expression
+ contained in *TP and change the DECL_CONTEXT of every local
+ variable referenced in *TP. */
+
+static tree
+move_stmt_r (tree *tp, int *walk_subtrees, void *data)
+{
+ struct move_stmt_d *p = (struct move_stmt_d *) data;
+ tree t = *tp;
+
+ if (p->block
+ && (EXPR_P (t) || GIMPLE_STMT_P (t)))
+ TREE_BLOCK (t) = p->block;
+
+ if (OMP_DIRECTIVE_P (t)
+ && TREE_CODE (t) != OMP_RETURN
+ && TREE_CODE (t) != OMP_CONTINUE)
+ {
+ /* Do not remap variables inside OMP directives. Variables
+ referenced in clauses and directive header belong to the
+ parent function and should not be moved into the child
+ function. */
+ bool save_remap_decls_p = p->remap_decls_p;
+ p->remap_decls_p = false;
+ *walk_subtrees = 0;
+
+ walk_tree (&OMP_BODY (t), move_stmt_r, p, NULL);
+
+ p->remap_decls_p = save_remap_decls_p;
+ }
+ else if (DECL_P (t) && DECL_CONTEXT (t) == p->from_context)
+ {
+ if (TREE_CODE (t) == LABEL_DECL)
+ {
+ if (p->new_label_map)
+ {
+ struct tree_map in, *out;
+ in.from = t;
+ out = htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
+ if (out)
+ *tp = t = out->to;
+ }
+
+ DECL_CONTEXT (t) = p->to_context;
+ }
+ else if (p->remap_decls_p)
+ {
+ DECL_CONTEXT (t) = p->to_context;
+
+ if (TREE_CODE (t) == VAR_DECL)
+ {
+ struct function *f = DECL_STRUCT_FUNCTION (p->to_context);
+ f->unexpanded_var_list
+ = tree_cons (0, t, f->unexpanded_var_list);
+
+ /* Mark T to be removed from the original function,
+ otherwise it will be given a DECL_RTL when the
+ original function is expanded. */
+ bitmap_set_bit (p->vars_to_remove, DECL_UID (t));
+ }
+ }
+ }
+ else if (TYPE_P (t))
+ *walk_subtrees = 0;
+
+ return NULL_TREE;
+}
+
+
+/* Move basic block BB from function CFUN to function DEST_FN. The
+ block is moved out of the original linked list and placed after
+ block AFTER in the new list. Also, the block is removed from the
+ original array of blocks and placed in DEST_FN's array of blocks.
+ If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
+ updated to reflect the moved edges.
+
+ On exit, local variables that need to be removed from
+ CFUN->UNEXPANDED_VAR_LIST will have been added to VARS_TO_REMOVE. */
+
+static void
+move_block_to_fn (struct function *dest_cfun, basic_block bb,
+ basic_block after, bool update_edge_count_p,
+ bitmap vars_to_remove, htab_t new_label_map, int eh_offset)
+{
+ struct control_flow_graph *cfg;
+ edge_iterator ei;
+ edge e;
+ block_stmt_iterator si;
+ struct move_stmt_d d;
+ unsigned old_len, new_len;
+
+ /* Link BB to the new linked list. */
+ move_block_after (bb, after);
+
+ /* Update the edge count in the corresponding flowgraphs. */
+ if (update_edge_count_p)
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ cfun->cfg->x_n_edges--;
+ dest_cfun->cfg->x_n_edges++;
+ }
+
+ /* Remove BB from the original basic block array. */
+ VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
+ cfun->cfg->x_n_basic_blocks--;
+
+ /* Grow DEST_CFUN's basic block array if needed. */
+ cfg = dest_cfun->cfg;
+ cfg->x_n_basic_blocks++;
+ if (bb->index > cfg->x_last_basic_block)
+ cfg->x_last_basic_block = bb->index;
+
+ old_len = VEC_length (basic_block, cfg->x_basic_block_info);
+ if ((unsigned) cfg->x_last_basic_block >= old_len)
+ {
+ new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
+ VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
+ new_len);
+ }
+
+ VEC_replace (basic_block, cfg->x_basic_block_info,
+ cfg->x_last_basic_block, bb);
+
+ /* The statements in BB need to be associated with a new TREE_BLOCK.
+ Labels need to be associated with a new label-to-block map. */
+ memset (&d, 0, sizeof (d));
+ d.vars_to_remove = vars_to_remove;
+
+ for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+ {
+ tree stmt = bsi_stmt (si);
+ int region;
+
+ d.from_context = cfun->decl;
+ d.to_context = dest_cfun->decl;
+ d.remap_decls_p = true;
+ d.new_label_map = new_label_map;
+ if (TREE_BLOCK (stmt))
+ d.block = DECL_INITIAL (dest_cfun->decl);
+
+ walk_tree (&stmt, move_stmt_r, &d, NULL);
+
+ if (TREE_CODE (stmt) == LABEL_EXPR)
+ {
+ tree label = LABEL_EXPR_LABEL (stmt);
+ int uid = LABEL_DECL_UID (label);
+
+ gcc_assert (uid > -1);
+
+ old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
+ if (old_len <= (unsigned) uid)
+ {
+ new_len = 3 * uid / 2;
+ VEC_safe_grow_cleared (basic_block, gc,
+ cfg->x_label_to_block_map, new_len);
+ }
+
+ VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
+ VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
+
+ gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
+
+ if (uid >= dest_cfun->last_label_uid)
+ dest_cfun->last_label_uid = uid + 1;
+ }
+ else if (TREE_CODE (stmt) == RESX_EXPR && eh_offset != 0)
+ TREE_OPERAND (stmt, 0) =
+ build_int_cst (NULL_TREE,
+ TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0))
+ + eh_offset);
+
+ region = lookup_stmt_eh_region (stmt);
+ if (region >= 0)
+ {
+ add_stmt_to_eh_region_fn (dest_cfun, stmt, region + eh_offset);
+ remove_stmt_from_eh_region (stmt);
+ gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
+ gimple_remove_stmt_histograms (cfun, stmt);
+ }
+ }
+}
+
+/* Examine the statements in BB (which is in SRC_CFUN); find and return
+ the outermost EH region. Use REGION as the incoming base EH region. */
+
+static int
+find_outermost_region_in_block (struct function *src_cfun,
+ basic_block bb, int region)
+{
+ block_stmt_iterator si;
+
+ for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+ {
+ tree stmt = bsi_stmt (si);
+ int stmt_region;
+
+ if (TREE_CODE (stmt) == RESX_EXPR)
+ stmt_region = TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0));
+ else
+ stmt_region = lookup_stmt_eh_region_fn (src_cfun, stmt);
+ if (stmt_region > 0)
+ {
+ if (region < 0)
+ region = stmt_region;
+ else if (stmt_region != region)
+ {
+ region = eh_region_outermost (src_cfun, stmt_region, region);
+ gcc_assert (region != -1);
+ }
+ }
+ }
+
+ return region;
+}
+
+static tree
+new_label_mapper (tree decl, void *data)
+{
+ htab_t hash = (htab_t) data;
+ struct tree_map *m;
+ void **slot;
+
+ gcc_assert (TREE_CODE (decl) == LABEL_DECL);
+
+ m = xmalloc (sizeof (struct tree_map));
+ m->hash = DECL_UID (decl);
+ m->from = decl;
+ m->to = create_artificial_label ();
+ LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
+
+ slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
+ gcc_assert (*slot == NULL);
+
+ *slot = m;
+
+ return m->to;
+}
+
+/* Move a single-entry, single-exit region delimited by ENTRY_BB and
+ EXIT_BB to function DEST_CFUN. The whole region is replaced by a
+ single basic block in the original CFG and the new basic block is
+ returned. DEST_CFUN must not have a CFG yet.
+
+ Note that the region need not be a pure SESE region. Blocks inside
+ the region may contain calls to abort/exit. The only restriction
+ is that ENTRY_BB should be the only entry point and it must
+ dominate EXIT_BB.
+
+ All local variables referenced in the region are assumed to be in
+ the corresponding BLOCK_VARS and unexpanded variable lists
+ associated with DEST_CFUN. */
+
+basic_block
+move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
+ basic_block exit_bb)
+{
+ VEC(basic_block,heap) *bbs;
+ basic_block after, bb, *entry_pred, *exit_succ;
+ struct function *saved_cfun;
+ int *entry_flag, *exit_flag, eh_offset;
+ unsigned i, num_entry_edges, num_exit_edges;
+ edge e;
+ edge_iterator ei;
+ bitmap vars_to_remove;
+ htab_t new_label_map;
+
+ saved_cfun = cfun;
+
+ /* Collect all the blocks in the region. Manually add ENTRY_BB
+ because it won't be added by dfs_enumerate_from. */
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
+ region. */
+ gcc_assert (entry_bb != exit_bb
+ && (!exit_bb
+ || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
+
+ bbs = NULL;
+ VEC_safe_push (basic_block, heap, bbs, entry_bb);
+ gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
+
+ /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG. We need to remember
+ the predecessor edges to ENTRY_BB and the successor edges to
+ EXIT_BB so that we can re-attach them to the new basic block that
+ will replace the region. */
+ num_entry_edges = EDGE_COUNT (entry_bb->preds);
+ entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
+ entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
+ i = 0;
+ for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
+ {
+ entry_flag[i] = e->flags;
+ entry_pred[i++] = e->src;
+ remove_edge (e);
+ }
+
+ if (exit_bb)
+ {
+ num_exit_edges = EDGE_COUNT (exit_bb->succs);
+ exit_succ = (basic_block *) xcalloc (num_exit_edges,
+ sizeof (basic_block));
+ exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
+ i = 0;
+ for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
+ {
+ exit_flag[i] = e->flags;
+ exit_succ[i++] = e->dest;
+ remove_edge (e);
+ }
+ }
+ else
+ {
+ num_exit_edges = 0;
+ exit_succ = NULL;
+ exit_flag = NULL;
+ }
+
+ /* Switch context to the child function to initialize DEST_FN's CFG. */
+ gcc_assert (dest_cfun->cfg == NULL);
+ cfun = dest_cfun;
+
+ init_empty_tree_cfg ();
+
+ /* Initialize EH information for the new function. */
+ eh_offset = 0;
+ new_label_map = NULL;
+ if (saved_cfun->eh)
+ {
+ int region = -1;
+
+ for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ region = find_outermost_region_in_block (saved_cfun, bb, region);
+
+ init_eh_for_function ();
+ if (region != -1)
+ {
+ new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
+ eh_offset = duplicate_eh_regions (saved_cfun, new_label_mapper,
+ new_label_map, region, 0);
+ }
+ }
+
+ cfun = saved_cfun;
+
+ /* Move blocks from BBS into DEST_CFUN. */
+ gcc_assert (VEC_length (basic_block, bbs) >= 2);
+ after = dest_cfun->cfg->x_entry_block_ptr;
+ vars_to_remove = BITMAP_ALLOC (NULL);
+ for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ {
+ /* No need to update edge counts on the last block. It has
+ already been updated earlier when we detached the region from
+ the original CFG. */
+ move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, vars_to_remove,
+ new_label_map, eh_offset);
+ after = bb;
+ }
+
+ if (new_label_map)
+ htab_delete (new_label_map);
+
+ /* Remove the variables marked in VARS_TO_REMOVE from
+ CFUN->UNEXPANDED_VAR_LIST. Otherwise, they will be given a
+ DECL_RTL in the context of CFUN. */
+ if (!bitmap_empty_p (vars_to_remove))
+ {
+ tree *p;
+
+ for (p = &cfun->unexpanded_var_list; *p; )
+ {
+ tree var = TREE_VALUE (*p);
+ if (bitmap_bit_p (vars_to_remove, DECL_UID (var)))
+ {
+ *p = TREE_CHAIN (*p);
+ continue;
+ }
+
+ p = &TREE_CHAIN (*p);
+ }
+ }
+
+ BITMAP_FREE (vars_to_remove);
+
+ /* Rewire the entry and exit blocks. The successor to the entry
+ block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
+ the child function. Similarly, the predecessor of DEST_FN's
+ EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR. We
+ need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
+ various CFG manipulation function get to the right CFG.
+
+ FIXME, this is silly. The CFG ought to become a parameter to
+ these helpers. */
+ cfun = dest_cfun;
+ make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
+ if (exit_bb)
+ make_edge (exit_bb, EXIT_BLOCK_PTR, 0);
+ cfun = saved_cfun;
+
+ /* Back in the original function, the SESE region has disappeared,
+ create a new basic block in its place. */
+ bb = create_empty_bb (entry_pred[0]);
+ for (i = 0; i < num_entry_edges; i++)
+ make_edge (entry_pred[i], bb, entry_flag[i]);
+
+ for (i = 0; i < num_exit_edges; i++)
+ make_edge (bb, exit_succ[i], exit_flag[i]);
+
+ if (exit_bb)
+ {
+ free (exit_flag);
+ free (exit_succ);
+ }
+ free (entry_flag);
+ free (entry_pred);
+ free_dominance_info (CDI_DOMINATORS);
+ free_dominance_info (CDI_POST_DOMINATORS);
+ VEC_free (basic_block, heap, bbs);
+
+ return bb;
+}
+