+static tree gimple_divmod_fixed_value (gimple, tree, int, gcov_type, gcov_type);
+static tree gimple_mod_pow2 (gimple, int, gcov_type, gcov_type);
+static tree gimple_mod_subtract (gimple, int, int, int, gcov_type, gcov_type,
+ gcov_type);
+static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *);
+static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *);
+static bool gimple_mod_subtract_transform (gimple_stmt_iterator *);
+static bool gimple_stringops_transform (gimple_stmt_iterator *);
+static bool gimple_ic_transform (gimple);
+
+/* Allocate histogram value. */
+
+static histogram_value
+gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,
+ enum hist_type type, gimple stmt, tree value)
+{
+ histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist));
+ hist->hvalue.value = value;
+ hist->hvalue.stmt = stmt;
+ hist->type = type;
+ return hist;
+}
+
+/* Hash value for histogram. */
+
+static hashval_t
+histogram_hash (const void *x)
+{
+ return htab_hash_pointer (((const_histogram_value)x)->hvalue.stmt);
+}
+
+/* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */
+
+static int
+histogram_eq (const void *x, const void *y)
+{
+ return ((const_histogram_value) x)->hvalue.stmt == (const_gimple) y;
+}
+
+/* Set histogram for STMT. */
+
+static void
+set_histogram_value (struct function *fun, gimple stmt, histogram_value hist)
+{
+ void **loc;
+ if (!hist && !VALUE_HISTOGRAMS (fun))
+ return;
+ if (!VALUE_HISTOGRAMS (fun))
+ VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash,
+ histogram_eq, NULL);
+ loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt,
+ htab_hash_pointer (stmt),
+ hist ? INSERT : NO_INSERT);
+ if (!hist)
+ {
+ if (loc)
+ htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);
+ return;
+ }
+ *loc = hist;
+}
+
+/* Get histogram list for STMT. */
+
+histogram_value
+gimple_histogram_value (struct function *fun, gimple stmt)
+{
+ if (!VALUE_HISTOGRAMS (fun))
+ return NULL;
+ return (histogram_value) htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,
+ htab_hash_pointer (stmt));
+}
+
+/* Add histogram for STMT. */
+
+void
+gimple_add_histogram_value (struct function *fun, gimple stmt,
+ histogram_value hist)
+{
+ hist->hvalue.next = gimple_histogram_value (fun, stmt);
+ set_histogram_value (fun, stmt, hist);
+}
+
+
+/* Remove histogram HIST from STMT's histogram list. */
+
+void
+gimple_remove_histogram_value (struct function *fun, gimple stmt,
+ histogram_value hist)
+{
+ histogram_value hist2 = gimple_histogram_value (fun, stmt);
+ if (hist == hist2)
+ {
+ set_histogram_value (fun, stmt, hist->hvalue.next);
+ }
+ else
+ {
+ while (hist2->hvalue.next != hist)
+ hist2 = hist2->hvalue.next;
+ hist2->hvalue.next = hist->hvalue.next;
+ }
+ free (hist->hvalue.counters);
+#ifdef ENABLE_CHECKING
+ memset (hist, 0xab, sizeof (*hist));
+#endif
+ free (hist);
+}
+
+
+/* Lookup histogram of type TYPE in the STMT. */
+
+histogram_value
+gimple_histogram_value_of_type (struct function *fun, gimple stmt,
+ enum hist_type type)
+{
+ histogram_value hist;
+ for (hist = gimple_histogram_value (fun, stmt); hist;
+ hist = hist->hvalue.next)
+ if (hist->type == type)
+ return hist;
+ return NULL;
+}
+
+/* Dump information about HIST to DUMP_FILE. */
+
+static void
+dump_histogram_value (FILE *dump_file, histogram_value hist)
+{
+ switch (hist->type)
+ {
+ case HIST_TYPE_INTERVAL:
+ fprintf (dump_file, "Interval counter range %d -- %d",
+ hist->hdata.intvl.int_start,
+ (hist->hdata.intvl.int_start
+ + hist->hdata.intvl.steps - 1));
+ if (hist->hvalue.counters)
+ {
+ unsigned int i;
+ fprintf(dump_file, " [");
+ for (i = 0; i < hist->hdata.intvl.steps; i++)
+ fprintf (dump_file, " %d:"HOST_WIDEST_INT_PRINT_DEC,
+ hist->hdata.intvl.int_start + i,
+ (HOST_WIDEST_INT) hist->hvalue.counters[i]);
+ fprintf (dump_file, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) hist->hvalue.counters[i]);
+ }
+ fprintf (dump_file, ".\n");
+ break;
+
+ case HIST_TYPE_POW2:
+ fprintf (dump_file, "Pow2 counter ");
+ if (hist->hvalue.counters)
+ {
+ fprintf (dump_file, "pow2:"HOST_WIDEST_INT_PRINT_DEC
+ " nonpow2:"HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) hist->hvalue.counters[0],
+ (HOST_WIDEST_INT) hist->hvalue.counters[1]);
+ }
+ fprintf (dump_file, ".\n");
+ break;
+
+ case HIST_TYPE_SINGLE_VALUE:
+ fprintf (dump_file, "Single value ");
+ if (hist->hvalue.counters)
+ {
+ fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
+ " match:"HOST_WIDEST_INT_PRINT_DEC
+ " wrong:"HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) hist->hvalue.counters[0],
+ (HOST_WIDEST_INT) hist->hvalue.counters[1],
+ (HOST_WIDEST_INT) hist->hvalue.counters[2]);
+ }
+ fprintf (dump_file, ".\n");
+ break;
+
+ case HIST_TYPE_AVERAGE:
+ fprintf (dump_file, "Average value ");
+ if (hist->hvalue.counters)
+ {
+ fprintf (dump_file, "sum:"HOST_WIDEST_INT_PRINT_DEC
+ " times:"HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) hist->hvalue.counters[0],
+ (HOST_WIDEST_INT) hist->hvalue.counters[1]);
+ }
+ fprintf (dump_file, ".\n");
+ break;
+
+ case HIST_TYPE_IOR:
+ fprintf (dump_file, "IOR value ");
+ if (hist->hvalue.counters)
+ {
+ fprintf (dump_file, "ior:"HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) hist->hvalue.counters[0]);
+ }
+ fprintf (dump_file, ".\n");
+ break;
+
+ case HIST_TYPE_CONST_DELTA:
+ fprintf (dump_file, "Constant delta ");
+ if (hist->hvalue.counters)
+ {
+ fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
+ " match:"HOST_WIDEST_INT_PRINT_DEC
+ " wrong:"HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) hist->hvalue.counters[0],
+ (HOST_WIDEST_INT) hist->hvalue.counters[1],
+ (HOST_WIDEST_INT) hist->hvalue.counters[2]);
+ }
+ fprintf (dump_file, ".\n");
+ break;
+ case HIST_TYPE_INDIR_CALL:
+ fprintf (dump_file, "Indirect call ");
+ if (hist->hvalue.counters)
+ {
+ fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
+ " match:"HOST_WIDEST_INT_PRINT_DEC
+ " all:"HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) hist->hvalue.counters[0],
+ (HOST_WIDEST_INT) hist->hvalue.counters[1],
+ (HOST_WIDEST_INT) hist->hvalue.counters[2]);
+ }
+ fprintf (dump_file, ".\n");
+ break;
+ }
+}
+
+/* Dump all histograms attached to STMT to DUMP_FILE. */
+
+void
+dump_histograms_for_stmt (struct function *fun, FILE *dump_file, gimple stmt)
+{
+ histogram_value hist;
+ for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
+ dump_histogram_value (dump_file, hist);
+}
+
+/* Remove all histograms associated with STMT. */
+
+void
+gimple_remove_stmt_histograms (struct function *fun, gimple stmt)
+{
+ histogram_value val;
+ while ((val = gimple_histogram_value (fun, stmt)) != NULL)
+ gimple_remove_histogram_value (fun, stmt, val);
+}
+
+/* Duplicate all histograms associates with OSTMT to STMT. */
+
+void
+gimple_duplicate_stmt_histograms (struct function *fun, gimple stmt,
+ struct function *ofun, gimple ostmt)
+{
+ histogram_value val;
+ for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next)
+ {
+ histogram_value new_val = gimple_alloc_histogram_value (fun, val->type, NULL, NULL);
+ memcpy (new_val, val, sizeof (*val));
+ new_val->hvalue.stmt = stmt;
+ new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
+ memcpy (new_val->hvalue.counters, val->hvalue.counters, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
+ gimple_add_histogram_value (fun, stmt, new_val);
+ }
+}
+
+
+/* Move all histograms associated with OSTMT to STMT. */
+
+void
+gimple_move_stmt_histograms (struct function *fun, gimple stmt, gimple ostmt)
+{
+ histogram_value val = gimple_histogram_value (fun, ostmt);
+ if (val)
+ {
+ /* The following three statements can't be reordered,
+ because histogram hashtab relies on stmt field value
+ for finding the exact slot. */
+ set_histogram_value (fun, ostmt, NULL);
+ for (; val != NULL; val = val->hvalue.next)
+ val->hvalue.stmt = stmt;
+ set_histogram_value (fun, stmt, val);
+ }
+}
+
+static bool error_found = false;
+
+/* Helper function for verify_histograms. For each histogram reachable via htab
+ walk verify that it was reached via statement walk. */
+
+static int
+visit_hist (void **slot, void *data)
+{
+ struct pointer_set_t *visited = (struct pointer_set_t *) data;
+ histogram_value hist = *(histogram_value *) slot;
+ if (!pointer_set_contains (visited, hist))
+ {
+ error ("Dead histogram");
+ dump_histogram_value (stderr, hist);
+ debug_gimple_stmt (hist->hvalue.stmt);
+ error_found = true;
+ }
+ return 1;
+}
+
+
+/* Verify sanity of the histograms. */
+
+void
+verify_histograms (void)
+{
+ basic_block bb;
+ gimple_stmt_iterator gsi;
+ histogram_value hist;
+ struct pointer_set_t *visited_hists;
+
+ error_found = false;
+ visited_hists = pointer_set_create ();
+ FOR_EACH_BB (bb)
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple stmt = gsi_stmt (gsi);
+
+ for (hist = gimple_histogram_value (cfun, stmt); hist;
+ hist = hist->hvalue.next)
+ {
+ if (hist->hvalue.stmt != stmt)
+ {
+ error ("Histogram value statement does not correspond to "
+ "the statement it is associated with");
+ debug_gimple_stmt (stmt);
+ dump_histogram_value (stderr, hist);
+ error_found = true;
+ }
+ pointer_set_insert (visited_hists, hist);
+ }
+ }
+ if (VALUE_HISTOGRAMS (cfun))
+ htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, visited_hists);
+ pointer_set_destroy (visited_hists);
+ if (error_found)
+ internal_error ("verify_histograms failed");
+}
+
+/* Helper function for verify_histograms. For each histogram reachable via htab
+ walk verify that it was reached via statement walk. */
+
+static int
+free_hist (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+ histogram_value hist = *(histogram_value *) slot;
+ free (hist->hvalue.counters);
+#ifdef ENABLE_CHECKING
+ memset (hist, 0xab, sizeof (*hist));
+#endif
+ free (hist);
+ return 1;
+}
+
+void
+free_histograms (void)
+{
+ if (VALUE_HISTOGRAMS (cfun))
+ {
+ htab_traverse (VALUE_HISTOGRAMS (cfun), free_hist, NULL);
+ htab_delete (VALUE_HISTOGRAMS (cfun));
+ VALUE_HISTOGRAMS (cfun) = NULL;
+ }
+}
+
+
+/* The overall number of invocations of the counter should match
+ execution count of basic block. Report it as error rather than
+ internal error as it might mean that user has misused the profile
+ somehow. */