+ max_hdr[bbn] = bbn;
+ rescan = 1;
+ }
+ else
+ /* This block already was processed in find_rgns. */
+ max_hdr[bbn] = -1;
+ }
+
+ /* The idea is to topologically walk through CFG in top-down order.
+ During the traversal, if all the predecessors of a node are
+ marked to be in the same region (they all have the same max_hdr),
+ then current node is also marked to be a part of that region.
+ Otherwise the node starts its own region.
+ CFG should be traversed until no further changes are made. On each
+ iteration the set of the region heads is extended (the set of those
+ blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
+ set of all basic blocks, thus the algorithm is guaranteed to
+ terminate. */
+
+ while (rescan && iter < max_iter)
+ {
+ rescan = 0;
+
+ for (i = nblocks - 1; i >= 0; i--)
+ {
+ edge e;
+ edge_iterator ei;
+ int bbn = order[i];
+
+ if (max_hdr[bbn] != -1 && !TEST_BIT (header, bbn))
+ {
+ int hdr = -1;
+
+ FOR_EACH_EDGE (e, ei, BASIC_BLOCK (bbn)->preds)
+ {
+ int predn = e->src->index;
+
+ if (predn != ENTRY_BLOCK
+ /* If pred wasn't processed in find_rgns. */
+ && max_hdr[predn] != -1
+ /* And pred and bb reside in the same loop.
+ (Or out of any loop). */
+ && loop_hdr[bbn] == loop_hdr[predn])
+ {
+ if (hdr == -1)
+ /* Then bb extends the containing region of pred. */
+ hdr = max_hdr[predn];
+ else if (hdr != max_hdr[predn])
+ /* Too bad, there are at least two predecessors
+ that reside in different regions. Thus, BB should
+ begin its own region. */
+ {
+ hdr = bbn;
+ break;
+ }
+ }
+ else
+ /* BB starts its own region. */
+ {
+ hdr = bbn;
+ break;
+ }
+ }
+
+ if (hdr == bbn)
+ {
+ /* If BB start its own region,
+ update set of headers with BB. */
+ SET_BIT (header, bbn);
+ rescan = 1;
+ }
+ else
+ gcc_assert (hdr != -1);
+
+ max_hdr[bbn] = hdr;
+ }
+ }
+
+ iter++;
+ }
+
+ /* Statistics were gathered on the SPEC2000 package of tests with
+ mainline weekly snapshot gcc-4.1-20051015 on ia64.
+
+ Statistics for SPECint:
+ 1 iteration : 1751 cases (38.7%)
+ 2 iterations: 2770 cases (61.3%)
+ Blocks wrapped in regions by find_rgns without extension: 18295 blocks
+ Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
+ (We don't count single block regions here).
+
+ Statistics for SPECfp:
+ 1 iteration : 621 cases (35.9%)
+ 2 iterations: 1110 cases (64.1%)
+ Blocks wrapped in regions by find_rgns without extension: 6476 blocks
+ Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
+ (We don't count single block regions here).
+
+ By default we do at most 2 iterations.
+ This can be overridden with max-sched-extend-regions-iters parameter:
+ 0 - disable region extension,
+ N > 0 - do at most N iterations. */
+
+ if (sched_verbose && iter != 0)
+ fprintf (sched_dump, ";; Region extension iterations: %d%s\n", iter,
+ rescan ? "... failed" : "");
+
+ if (!rescan && iter != 0)
+ {
+ int *s1 = NULL, s1_sz = 0;
+
+ /* Save the old statistics for later printout. */
+ if (sched_verbose >= 6)
+ s1_sz = gather_region_statistics (&s1);
+
+ /* We have succeeded. Now assemble the regions. */
+ for (i = nblocks - 1; i >= 0; i--)
+ {
+ int bbn = order[i];
+
+ if (max_hdr[bbn] == bbn)
+ /* BBN is a region head. */
+ {
+ edge e;
+ edge_iterator ei;
+ int num_bbs = 0, j, num_insns = 0, large;
+
+ large = too_large (bbn, &num_bbs, &num_insns);
+
+ degree[bbn] = -1;
+ rgn_bb_table[idx] = bbn;
+ RGN_BLOCKS (nr_regions) = idx++;
+ RGN_DONT_CALC_DEPS (nr_regions) = 0;
+ RGN_HAS_REAL_EBB (nr_regions) = 0;
+ CONTAINING_RGN (bbn) = nr_regions;
+ BLOCK_TO_BB (bbn) = 0;
+
+ FOR_EACH_EDGE (e, ei, BASIC_BLOCK (bbn)->succs)
+ if (e->dest != EXIT_BLOCK_PTR)
+ degree[e->dest->index]--;
+
+ if (!large)
+ /* Here we check whether the region is too_large. */
+ for (j = i - 1; j >= 0; j--)
+ {
+ int succn = order[j];
+ if (max_hdr[succn] == bbn)
+ {
+ if ((large = too_large (succn, &num_bbs, &num_insns)))
+ break;
+ }
+ }
+
+ if (large)
+ /* If the region is too_large, then wrap every block of
+ the region into single block region.
+ Here we wrap region head only. Other blocks are
+ processed in the below cycle. */
+ {
+ RGN_NR_BLOCKS (nr_regions) = 1;
+ nr_regions++;
+ }
+
+ num_bbs = 1;
+
+ for (j = i - 1; j >= 0; j--)
+ {
+ int succn = order[j];
+
+ if (max_hdr[succn] == bbn)
+ /* This cycle iterates over all basic blocks, that
+ are supposed to be in the region with head BBN,
+ and wraps them into that region (or in single
+ block region). */
+ {
+ gcc_assert (degree[succn] == 0);
+
+ degree[succn] = -1;
+ rgn_bb_table[idx] = succn;
+ BLOCK_TO_BB (succn) = large ? 0 : num_bbs++;
+ CONTAINING_RGN (succn) = nr_regions;
+
+ if (large)
+ /* Wrap SUCCN into single block region. */
+ {
+ RGN_BLOCKS (nr_regions) = idx;
+ RGN_NR_BLOCKS (nr_regions) = 1;
+ RGN_DONT_CALC_DEPS (nr_regions) = 0;
+ RGN_HAS_REAL_EBB (nr_regions) = 0;
+ nr_regions++;
+ }
+
+ idx++;
+
+ FOR_EACH_EDGE (e, ei, BASIC_BLOCK (succn)->succs)
+ if (e->dest != EXIT_BLOCK_PTR)
+ degree[e->dest->index]--;
+ }
+ }
+
+ if (!large)
+ {
+ RGN_NR_BLOCKS (nr_regions) = num_bbs;
+ nr_regions++;
+ }
+ }
+ }
+
+ if (sched_verbose >= 6)
+ {
+ int *s2, s2_sz;
+
+ /* Get the new statistics and print the comparison with the
+ one before calling this function. */
+ s2_sz = gather_region_statistics (&s2);
+ print_region_statistics (s1, s1_sz, s2, s2_sz);
+ free (s1);
+ free (s2);
+ }
+ }
+
+ free (order);
+ free (max_hdr);
+
+ *idxp = idx;
+}
+
+/* Functions for regions scheduling information. */
+
+/* Compute dominators, probability, and potential-split-edges of bb.
+ Assume that these values were already computed for bb's predecessors. */
+
+static void
+compute_dom_prob_ps (int bb)
+{
+ edge_iterator in_ei;
+ edge in_edge;
+
+ /* We shouldn't have any real ebbs yet. */
+ gcc_assert (ebb_head [bb] == bb + current_blocks);
+
+ if (IS_RGN_ENTRY (bb))
+ {
+ SET_BIT (dom[bb], 0);
+ prob[bb] = REG_BR_PROB_BASE;
+ return;
+ }
+
+ prob[bb] = 0;
+
+ /* Initialize dom[bb] to '111..1'. */
+ sbitmap_ones (dom[bb]);
+
+ FOR_EACH_EDGE (in_edge, in_ei, BASIC_BLOCK (BB_TO_BLOCK (bb))->preds)
+ {
+ int pred_bb;
+ edge out_edge;
+ edge_iterator out_ei;
+
+ if (in_edge->src == ENTRY_BLOCK_PTR)
+ continue;
+
+ pred_bb = BLOCK_TO_BB (in_edge->src->index);
+ sbitmap_a_and_b (dom[bb], dom[bb], dom[pred_bb]);
+ sbitmap_a_or_b (ancestor_edges[bb],
+ ancestor_edges[bb], ancestor_edges[pred_bb]);
+
+ SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (in_edge));
+
+ sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[pred_bb]);
+
+ FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs)
+ SET_BIT (pot_split[bb], EDGE_TO_BIT (out_edge));
+
+ prob[bb] += ((prob[pred_bb] * in_edge->probability) / REG_BR_PROB_BASE);
+ }
+
+ SET_BIT (dom[bb], bb);
+ sbitmap_difference (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
+
+ if (sched_verbose >= 2)
+ fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
+ (100 * prob[bb]) / REG_BR_PROB_BASE);
+}
+
+/* Functions for target info. */
+
+/* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
+ Note that bb_trg dominates bb_src. */
+
+static void
+split_edges (int bb_src, int bb_trg, edgelst *bl)
+{
+ sbitmap src = sbitmap_alloc (pot_split[bb_src]->n_bits);
+ sbitmap_copy (src, pot_split[bb_src]);
+
+ sbitmap_difference (src, src, pot_split[bb_trg]);
+ extract_edgelst (src, bl);
+ sbitmap_free (src);
+}
+
+/* Find the valid candidate-source-blocks for the target block TRG, compute
+ their probability, and check if they are speculative or not.
+ For speculative sources, compute their update-blocks and split-blocks. */
+
+static void
+compute_trg_info (int trg)
+{
+ candidate *sp;
+ edgelst el = { NULL, 0 };
+ int i, j, k, update_idx;
+ basic_block block;
+ sbitmap visited;
+ edge_iterator ei;
+ edge e;
+
+ candidate_table = XNEWVEC (candidate, current_nr_blocks);
+
+ bblst_last = 0;
+ /* bblst_table holds split blocks and update blocks for each block after
+ the current one in the region. split blocks and update blocks are
+ the TO blocks of region edges, so there can be at most rgn_nr_edges
+ of them. */
+ bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
+ bblst_table = XNEWVEC (basic_block, bblst_size);
+
+ edgelst_last = 0;
+ edgelst_table = XNEWVEC (edge, rgn_nr_edges);
+
+ /* Define some of the fields for the target bb as well. */
+ sp = candidate_table + trg;
+ sp->is_valid = 1;
+ sp->is_speculative = 0;
+ sp->src_prob = REG_BR_PROB_BASE;
+
+ visited = sbitmap_alloc (last_basic_block);
+
+ for (i = trg + 1; i < current_nr_blocks; i++)
+ {
+ sp = candidate_table + i;
+
+ sp->is_valid = IS_DOMINATED (i, trg);
+ if (sp->is_valid)
+ {
+ int tf = prob[trg], cf = prob[i];
+
+ /* In CFGs with low probability edges TF can possibly be zero. */
+ sp->src_prob = (tf ? ((cf * REG_BR_PROB_BASE) / tf) : 0);
+ sp->is_valid = (sp->src_prob >= min_spec_prob);
OSDN Git Service
