+
+void
+debug_bb (basic_block bb)
+{
+ dump_bb (bb, stderr, 0);
+}
+
+basic_block
+debug_bb_n (int n)
+{
+ basic_block bb = BASIC_BLOCK (n);
+ dump_bb (bb, stderr, 0);
+ return bb;
+}
+
+/* Dumps cfg related information about basic block BB to FILE. */
+
+static void
+dump_cfg_bb_info (FILE *file, basic_block bb)
+{
+ unsigned i;
+ edge_iterator ei;
+ bool first = true;
+ static const char * const bb_bitnames[] =
+ {
+ "new", "reachable", "irreducible_loop", "superblock",
+ "nosched", "hot", "cold", "dup", "xlabel", "rtl",
+ "fwdr", "nothrd"
+ };
+ const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
+ edge e;
+
+ fprintf (file, "Basic block %d", bb->index);
+ for (i = 0; i < n_bitnames; i++)
+ if (bb->flags & (1 << i))
+ {
+ if (first)
+ fputs (" (", file);
+ else
+ fputs (", ", file);
+ first = false;
+ fputs (bb_bitnames[i], file);
+ }
+ if (!first)
+ putc (')', file);
+ putc ('\n', file);
+
+ fputs ("Predecessors: ", file);
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ dump_edge_info (file, e, 0);
+
+ fprintf (file, "\nSuccessors: ");
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ dump_edge_info (file, e, 1);
+ fputs ("\n\n", file);
+}
+
+/* Dumps a brief description of cfg to FILE. */
+
+void
+brief_dump_cfg (FILE *file)
+{
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
+ {
+ dump_cfg_bb_info (file, bb);
+ }
+}
+
+/* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
+ leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
+ redirected to destination of TAKEN_EDGE.
+
+ This function may leave the profile inconsistent in the case TAKEN_EDGE
+ frequency or count is believed to be lower than FREQUENCY or COUNT
+ respectively. */
+void
+update_bb_profile_for_threading (basic_block bb, int edge_frequency,
+ gcov_type count, edge taken_edge)
+{
+ edge c;
+ int prob;
+ edge_iterator ei;
+
+ bb->count -= count;
+ if (bb->count < 0)
+ {
+ if (dump_file)
+ fprintf (dump_file, "bb %i count became negative after threading",
+ bb->index);
+ bb->count = 0;
+ }
+
+ /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
+ Watch for overflows. */
+ if (bb->frequency)
+ prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
+ else
+ prob = 0;
+ if (prob > taken_edge->probability)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Jump threading proved probability of edge "
+ "%i->%i too small (it is %i, should be %i).\n",
+ taken_edge->src->index, taken_edge->dest->index,
+ taken_edge->probability, prob);
+ prob = taken_edge->probability;
+ }
+
+ /* Now rescale the probabilities. */
+ taken_edge->probability -= prob;
+ prob = REG_BR_PROB_BASE - prob;
+ bb->frequency -= edge_frequency;
+ if (bb->frequency < 0)
+ bb->frequency = 0;
+ if (prob <= 0)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
+ "frequency of block should end up being 0, it is %i\n",
+ bb->index, bb->frequency);
+ EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
+ ei = ei_start (bb->succs);
+ ei_next (&ei);
+ for (; (c = ei_safe_edge (ei)); ei_next (&ei))
+ c->probability = 0;
+ }
+ else if (prob != REG_BR_PROB_BASE)
+ {
+ int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
+
+ FOR_EACH_EDGE (c, ei, bb->succs)
+ {
+ /* Protect from overflow due to additional scaling. */
+ if (c->probability > prob)
+ c->probability = REG_BR_PROB_BASE;
+ else
+ {
+ c->probability = RDIV (c->probability * scale, 65536);
+ if (c->probability > REG_BR_PROB_BASE)
+ c->probability = REG_BR_PROB_BASE;
+ }
+ }
+ }
+
+ gcc_assert (bb == taken_edge->src);
+ taken_edge->count -= count;
+ if (taken_edge->count < 0)
+ {
+ if (dump_file)
+ fprintf (dump_file, "edge %i->%i count became negative after threading",
+ taken_edge->src->index, taken_edge->dest->index);
+ taken_edge->count = 0;
+ }
+}
+
+/* Multiply all frequencies of basic blocks in array BBS of length NBBS
+ by NUM/DEN, in int arithmetic. May lose some accuracy. */
+void
+scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
+{
+ int i;
+ edge e;
+ if (num < 0)
+ num = 0;
+
+ /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
+ 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
+ and still safely fit in int during calculations. */
+ if (den > 1000)
+ {
+ if (num > 1000000)
+ return;
+
+ num = RDIV (1000 * num, den);
+ den = 1000;
+ }
+ if (num > 100 * den)
+ return;
+
+ for (i = 0; i < nbbs; i++)
+ {
+ edge_iterator ei;
+ bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
+ /* Make sure the frequencies do not grow over BB_FREQ_MAX. */
+ if (bbs[i]->frequency > BB_FREQ_MAX)
+ bbs[i]->frequency = BB_FREQ_MAX;
+ bbs[i]->count = RDIV (bbs[i]->count * num, den);
+ FOR_EACH_EDGE (e, ei, bbs[i]->succs)
+ e->count = RDIV (e->count * num, den);
+ }
+}
+
+/* numbers smaller than this value are safe to multiply without getting
+ 64bit overflow. */
+#define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
+
+/* Multiply all frequencies of basic blocks in array BBS of length NBBS
+ by NUM/DEN, in gcov_type arithmetic. More accurate than previous
+ function but considerably slower. */
+void
+scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num,
+ gcov_type den)
+{
+ int i;
+ edge e;
+ gcov_type fraction = RDIV (num * 65536, den);
+
+ gcc_assert (fraction >= 0);
+
+ if (num < MAX_SAFE_MULTIPLIER)
+ for (i = 0; i < nbbs; i++)
+ {
+ edge_iterator ei;
+ bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
+ if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
+ bbs[i]->count = RDIV (bbs[i]->count * num, den);
+ else
+ bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
+ FOR_EACH_EDGE (e, ei, bbs[i]->succs)
+ if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
+ e->count = RDIV (e->count * num, den);
+ else
+ e->count = RDIV (e->count * fraction, 65536);
+ }
+ else
+ for (i = 0; i < nbbs; i++)
+ {
+ edge_iterator ei;
+ if (sizeof (gcov_type) > sizeof (int))
+ bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
+ else
+ bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
+ bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
+ FOR_EACH_EDGE (e, ei, bbs[i]->succs)
+ e->count = RDIV (e->count * fraction, 65536);
+ }
+}
+
+/* Data structures used to maintain mapping between basic blocks and
+ copies. */
+static htab_t bb_original;
+static htab_t bb_copy;
+
+/* And between loops and copies. */
+static htab_t loop_copy;
+static alloc_pool original_copy_bb_pool;
+
+struct htab_bb_copy_original_entry
+{
+ /* Block we are attaching info to. */
+ int index1;
+ /* Index of original or copy (depending on the hashtable) */
+ int index2;
+};
+
+static hashval_t
+bb_copy_original_hash (const void *p)
+{
+ const struct htab_bb_copy_original_entry *data
+ = ((const struct htab_bb_copy_original_entry *)p);
+
+ return data->index1;
+}
+static int
+bb_copy_original_eq (const void *p, const void *q)
+{
+ const struct htab_bb_copy_original_entry *data
+ = ((const struct htab_bb_copy_original_entry *)p);
+ const struct htab_bb_copy_original_entry *data2
+ = ((const struct htab_bb_copy_original_entry *)q);
+
+ return data->index1 == data2->index1;
+}
+
+/* Initialize the data structures to maintain mapping between blocks
+ and its copies. */
+void
+initialize_original_copy_tables (void)
+{
+ gcc_assert (!original_copy_bb_pool);
+ original_copy_bb_pool
+ = create_alloc_pool ("original_copy",
+ sizeof (struct htab_bb_copy_original_entry), 10);
+ bb_original = htab_create (10, bb_copy_original_hash,
+ bb_copy_original_eq, NULL);
+ bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
+ loop_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
+}
+
+/* Free the data structures to maintain mapping between blocks and
+ its copies. */
+void
+free_original_copy_tables (void)
+{
+ gcc_assert (original_copy_bb_pool);
+ htab_delete (bb_copy);
+ htab_delete (bb_original);
+ htab_delete (loop_copy);
+ free_alloc_pool (original_copy_bb_pool);
+ bb_copy = NULL;
+ bb_original = NULL;
+ loop_copy = NULL;
+ original_copy_bb_pool = NULL;
+}
+
+/* Removes the value associated with OBJ from table TAB. */
+
+static void
+copy_original_table_clear (htab_t tab, unsigned obj)
+{
+ void **slot;
+ struct htab_bb_copy_original_entry key, *elt;
+
+ if (!original_copy_bb_pool)
+ return;
+
+ key.index1 = obj;
+ slot = htab_find_slot (tab, &key, NO_INSERT);
+ if (!slot)
+ return;
+
+ elt = (struct htab_bb_copy_original_entry *) *slot;
+ htab_clear_slot (tab, slot);
+ pool_free (original_copy_bb_pool, elt);
+}
+
+/* Sets the value associated with OBJ in table TAB to VAL.
+ Do nothing when data structures are not initialized. */
+
+static void
+copy_original_table_set (htab_t tab, unsigned obj, unsigned val)
+{
+ struct htab_bb_copy_original_entry **slot;
+ struct htab_bb_copy_original_entry key;
+
+ if (!original_copy_bb_pool)
+ return;
+
+ key.index1 = obj;
+ slot = (struct htab_bb_copy_original_entry **)
+ htab_find_slot (tab, &key, INSERT);
+ if (!*slot)
+ {
+ *slot = (struct htab_bb_copy_original_entry *)
+ pool_alloc (original_copy_bb_pool);
+ (*slot)->index1 = obj;
+ }
+ (*slot)->index2 = val;
+}
+
+/* Set original for basic block. Do nothing when data structures are not
+ initialized so passes not needing this don't need to care. */
+void
+set_bb_original (basic_block bb, basic_block original)
+{
+ copy_original_table_set (bb_original, bb->index, original->index);
+}
+
+/* Get the original basic block. */
+basic_block
+get_bb_original (basic_block bb)
+{
+ struct htab_bb_copy_original_entry *entry;
+ struct htab_bb_copy_original_entry key;
+
+ gcc_assert (original_copy_bb_pool);
+
+ key.index1 = bb->index;
+ entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
+ if (entry)
+ return BASIC_BLOCK (entry->index2);
+ else
+ return NULL;
+}
+
+/* Set copy for basic block. Do nothing when data structures are not
+ initialized so passes not needing this don't need to care. */
+void
+set_bb_copy (basic_block bb, basic_block copy)
+{
+ copy_original_table_set (bb_copy, bb->index, copy->index);
+}
+
+/* Get the copy of basic block. */
+basic_block
+get_bb_copy (basic_block bb)
+{
+ struct htab_bb_copy_original_entry *entry;
+ struct htab_bb_copy_original_entry key;
+
+ gcc_assert (original_copy_bb_pool);
+
+ key.index1 = bb->index;
+ entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
+ if (entry)
+ return BASIC_BLOCK (entry->index2);
+ else
+ return NULL;
+}
+
+/* Set copy for LOOP to COPY. Do nothing when data structures are not
+ initialized so passes not needing this don't need to care. */
+
+void
+set_loop_copy (struct loop *loop, struct loop *copy)
+{
+ if (!copy)
+ copy_original_table_clear (loop_copy, loop->num);
+ else
+ copy_original_table_set (loop_copy, loop->num, copy->num);
+}
+
+/* Get the copy of LOOP. */
+
+struct loop *
+get_loop_copy (struct loop *loop)
+{
+ struct htab_bb_copy_original_entry *entry;
+ struct htab_bb_copy_original_entry key;
+
+ gcc_assert (original_copy_bb_pool);
+
+ key.index1 = loop->num;
+ entry = (struct htab_bb_copy_original_entry *) htab_find (loop_copy, &key);
+ if (entry)
+ return get_loop (entry->index2);
+ else
+ return NULL;
+}