/* Basic block reordering routines for the GNU compiler.
- Copyright (C) 2000-2018 Free Software Foundation, Inc.
+ Copyright (C) 2000-2020 Free Software Foundation, Inc.
This file is part of GCC.
*/
#include "config.h"
-#define INCLUDE_ALGORITHM /* stable_sort */
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "emit-rtl.h"
#include "output.h"
#include "expr.h"
-#include "params.h"
#include "tree-pass.h"
#include "cfgrtl.h"
#include "cfganal.h"
#include "cfgcleanup.h"
#include "bb-reorder.h"
#include "except.h"
+#include "alloc-pool.h"
#include "fibonacci_heap.h"
#include "stringpool.h"
#include "attribs.h"
+#include "common/common-target.h"
/* The number of rounds. In most cases there will only be 4 rounds, but
when partitioning hot and cold basic blocks into separate sections of
/* If the best destination has multiple successors or predecessors,
don't allow it to be added when optimizing for size. This makes
sure predecessors with smaller index are handled before the best
- destinarion. It breaks long trace and reduces long jumps.
+ destination. It breaks long trace and reduces long jumps.
Take if-then-else as an example.
A
e_index = e->src->index;
/* We are looking for predecessor, so probabilities are not that
- informative. We do not want to connect A to B becuse A has
- only one sucessor (probablity is 100%) while there is edge
+ informative. We do not want to connect A to B because A has
+ only one successor (probability is 100%) while there is edge
A' to B where probability is 90% but which is much more frequent. */
if (e->count () > cur_best_edge->count ())
/* The edge has higher probability than the temporary best edge. */
else if (e->count () < cur_best_edge->count ())
/* The edge has lower probability than the temporary best edge. */
is_better_edge = false;
- if (e->probability > cur_best_edge->probability)
+ else if (e->probability > cur_best_edge->probability)
/* The edge has higher probability than the temporary best edge. */
is_better_edge = true;
else if (e->probability < cur_best_edge->probability)
static bool
copy_bb_p (const_basic_block bb, int code_may_grow)
{
- int size = 0;
- int max_size = uncond_jump_length;
+ unsigned int size = 0;
+ unsigned int max_size = uncond_jump_length;
rtx_insn *insn;
if (EDGE_COUNT (bb->preds) < 2)
return false;
if (code_may_grow && optimize_bb_for_speed_p (bb))
- max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);
+ max_size *= param_max_grow_copy_bb_insns;
FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
- size += get_attr_min_length (insn);
+ {
+ size += get_attr_min_length (insn);
+ if (size > max_size)
+ break;
+ }
}
if (size <= max_size)
if (dump_file)
{
fprintf (dump_file,
- "Block %d can't be copied because its size = %d.\n",
+ "Block %d can't be copied because its size = %u.\n",
bb->index, size);
}
int
get_uncond_jump_length (void)
{
- int length;
+ unsigned int length;
start_sequence ();
rtx_code_label *label = emit_label (gen_label_rtx ());
length = get_attr_min_length (jump);
end_sequence ();
+ gcc_assert (length < INT_MAX);
return length;
}
+/* Create a forwarder block to OLD_BB starting with NEW_LABEL and in the
+ other partition wrt OLD_BB. */
+
+static basic_block
+create_eh_forwarder_block (rtx_code_label *new_label, basic_block old_bb)
+{
+ /* Split OLD_BB, so that EH pads have always only incoming EH edges,
+ bb_has_eh_pred bbs are treated specially by DF infrastructure. */
+ old_bb = split_block_after_labels (old_bb)->dest;
+
+ /* Put the new label and a jump in the new basic block. */
+ rtx_insn *label = emit_label (new_label);
+ rtx_code_label *old_label = block_label (old_bb);
+ rtx_insn *jump = emit_jump_insn (targetm.gen_jump (old_label));
+ JUMP_LABEL (jump) = old_label;
+
+ /* Create the new basic block and put it in last position. */
+ basic_block last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
+ basic_block new_bb = create_basic_block (label, jump, last_bb);
+ new_bb->aux = last_bb->aux;
+ new_bb->count = old_bb->count;
+ last_bb->aux = new_bb;
+
+ emit_barrier_after_bb (new_bb);
+
+ make_single_succ_edge (new_bb, old_bb, 0);
+
+ /* Make sure the new basic block is in the other partition. */
+ unsigned new_partition = BB_PARTITION (old_bb);
+ new_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
+ BB_SET_PARTITION (new_bb, new_partition);
+
+ return new_bb;
+}
+
+/* The common landing pad in block OLD_BB has edges from both partitions.
+ Add a new landing pad that will just jump to the old one and split the
+ edges so that no EH edge crosses partitions. */
+
+static void
+sjlj_fix_up_crossing_landing_pad (basic_block old_bb)
+{
+ const unsigned lp_len = cfun->eh->lp_array->length ();
+ edge_iterator ei;
+ edge e;
+
+ /* Generate the new common landing-pad label. */
+ rtx_code_label *new_label = gen_label_rtx ();
+ LABEL_PRESERVE_P (new_label) = 1;
+
+ /* Create the forwarder block. */
+ basic_block new_bb = create_eh_forwarder_block (new_label, old_bb);
+
+ /* Create the map from old to new lp index and initialize it. */
+ unsigned *index_map = (unsigned *) alloca (lp_len * sizeof (unsigned));
+ memset (index_map, 0, lp_len * sizeof (unsigned));
+
+ /* Fix up the edges. */
+ for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
+ if (e->src != new_bb && BB_PARTITION (e->src) == BB_PARTITION (new_bb))
+ {
+ rtx_insn *insn = BB_END (e->src);
+ rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
+
+ gcc_assert (note != NULL);
+ const unsigned old_index = INTVAL (XEXP (note, 0));
+
+ /* Generate the new landing-pad structure. */
+ if (index_map[old_index] == 0)
+ {
+ eh_landing_pad old_lp = (*cfun->eh->lp_array)[old_index];
+ eh_landing_pad new_lp = gen_eh_landing_pad (old_lp->region);
+ new_lp->post_landing_pad = old_lp->post_landing_pad;
+ new_lp->landing_pad = new_label;
+ index_map[old_index] = new_lp->index;
+ }
+ XEXP (note, 0) = GEN_INT (index_map[old_index]);
+
+ /* Adjust the edge to the new destination. */
+ redirect_edge_succ (e, new_bb);
+ }
+ else
+ ei_next (&ei);
+}
+
/* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
- Duplicate the landing pad and split the edges so that no EH edge
- crosses partitions. */
+ Add a new landing pad that will just jump to the old one and split the
+ edges so that no EH edge crosses partitions. */
static void
-fix_up_crossing_landing_pad (eh_landing_pad old_lp, basic_block old_bb)
+dw2_fix_up_crossing_landing_pad (eh_landing_pad old_lp, basic_block old_bb)
{
eh_landing_pad new_lp;
- basic_block new_bb, last_bb, post_bb;
- rtx_insn *jump;
- unsigned new_partition;
edge_iterator ei;
edge e;
new_lp->landing_pad = gen_label_rtx ();
LABEL_PRESERVE_P (new_lp->landing_pad) = 1;
- /* Put appropriate instructions in new bb. */
- rtx_code_label *new_label = emit_label (new_lp->landing_pad);
-
- expand_dw2_landing_pad_for_region (old_lp->region);
-
- post_bb = BLOCK_FOR_INSN (old_lp->landing_pad);
- post_bb = single_succ (post_bb);
- rtx_code_label *post_label = block_label (post_bb);
- jump = emit_jump_insn (targetm.gen_jump (post_label));
- JUMP_LABEL (jump) = post_label;
-
- /* Create new basic block to be dest for lp. */
- last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
- new_bb = create_basic_block (new_label, jump, last_bb);
- new_bb->aux = last_bb->aux;
- new_bb->count = post_bb->count;
- last_bb->aux = new_bb;
-
- emit_barrier_after_bb (new_bb);
-
- make_single_succ_edge (new_bb, post_bb, 0);
-
- /* Make sure new bb is in the other partition. */
- new_partition = BB_PARTITION (old_bb);
- new_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
- BB_SET_PARTITION (new_bb, new_partition);
+ /* Create the forwarder block. */
+ basic_block new_bb = create_eh_forwarder_block (new_lp->landing_pad, old_bb);
/* Fix up the edges. */
for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
- if (BB_PARTITION (e->src) == new_partition)
+ if (e->src != new_bb && BB_PARTITION (e->src) == BB_PARTITION (new_bb))
{
rtx_insn *insn = BB_END (e->src);
rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
hot_bbs_to_check.safe_push (reach_bb);
}
}
+ hot_bbs_to_check.release ();
return cold_bb_count;
}
if (probably_never_executed_bb_p (cfun, bb))
{
+ cold_bb = true;
+
/* Handle profile insanities created by upstream optimizations
by also checking the incoming edge weights. If there is a non-cold
incoming edge, conservatively prevent this block from being split
into the cold section. */
- cold_bb = true;
- FOR_EACH_EDGE (e, ei, bb->preds)
- if (!probably_never_executed_edge_p (cfun, e))
- {
- cold_bb = false;
- break;
- }
+ if (!bb->count.precise_p ())
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (!probably_never_executed_edge_p (cfun, e))
+ {
+ cold_bb = false;
+ break;
+ }
}
if (cold_bb)
{
/* The format of .gcc_except_table does not allow landing pads to
be in a different partition as the throw. Fix this by either
- moving or duplicating the landing pads. */
+ moving the landing pads or inserting forwarder landing pads. */
if (cfun->eh->lp_array)
{
+ const bool sjlj
+ = (targetm_common.except_unwind_info (&global_options) == UI_SJLJ);
unsigned i;
eh_landing_pad lp;
which ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
BB_SET_PARTITION (bb, which);
}
+ else if (sjlj)
+ sjlj_fix_up_crossing_landing_pad (bb);
else
- fix_up_crossing_landing_pad (lp, bb);
+ dw2_fix_up_crossing_landing_pad (lp, bb);
+
+ /* There is a single, common landing pad in SJLJ mode. */
+ if (sjlj)
+ break;
}
}
/* Mark every edge that crosses between sections. */
-
FOR_EACH_BB_FN (bb, cfun)
FOR_EACH_EDGE (e, ei, bb->succs)
{
FREE (bbd);
}
-/* Return true if edge E1 is more desirable as a fallthrough edge than
- edge E2 is. */
+/* Order edges by execution frequency, higher first. */
-static bool
-edge_order (edge e1, edge e2)
+static int
+edge_order (const void *ve1, const void *ve2)
{
- return e1->count () > e2->count ();
+ edge e1 = *(const edge *) ve1;
+ edge e2 = *(const edge *) ve2;
+ profile_count c1 = e1->count ();
+ profile_count c2 = e2->count ();
+ /* Since profile_count::operator< does not establish a strict weak order
+ in presence of uninitialized counts, use 'max': this makes them appear
+ as if having execution frequency less than any initialized count. */
+ profile_count m = c1.max (c2);
+ return (m == c2) - (m == c1);
}
/* Reorder basic blocks using the "simple" algorithm. This tries to
all edges are equally desirable. */
if (optimize_function_for_speed_p (cfun))
- std::stable_sort (edges, edges + n, edge_order);
+ gcc_stablesort (edges, n, sizeof *edges, edge_order);
/* Now decide which of those edges to make fallthrough edges. We set
BB_VISITED if a block already has a fallthrough successor assigned
bb->aux = bb->next_bb;
cfg_layout_finalize ();
+ FOR_EACH_BB_FN (bb, fun)
+ df_recompute_luids (bb);
return 0;
}
/* Never copy a block larger than this. */
int max_size
- = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
+ = uncond_jump_length * param_max_goto_duplication_insns;
bool changed = false;
{
/* The optimization to partition hot/cold basic blocks into separate
sections of the .o file does not work well with linkonce or with
- user defined section attributes. Don't call it if either case
- arises. */
+ user defined section attributes or with naked attribute. Don't call
+ it if either case arises. */
return (flag_reorder_blocks_and_partition
&& optimize
/* See pass_reorder_blocks::gate. We should not partition if
&& optimize_function_for_speed_p (fun)
&& !DECL_COMDAT_GROUP (current_function_decl)
&& !lookup_attribute ("section", DECL_ATTRIBUTES (fun->decl))
+ && !lookup_attribute ("naked", DECL_ATTRIBUTES (fun->decl))
/* Workaround a bug in GDB where read_partial_die doesn't cope
with DIEs with DW_AT_ranges, see PR81115. */
&& !(in_lto_p && MAIN_NAME_P (DECL_NAME (fun->decl))));