fixed CRLF

[libfirm] / ir / ana / execfreq.c

diff --git a/ir/ana/execfreq.c b/ir/ana/execfreq.c
index f7ca3f3..a09b15c 100644 (file)
--- a/ir/ana/execfreq.c
+++ b/ir/ana/execfreq.c
@@ -9,7 +9,6 @@
  * Copyright:   (c) 2006 Universität Karlsruhe
  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  */
-
 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #endif
@@ -60,7 +59,7 @@ typedef struct _walkerdata_t {
   size_t  idx;
 } walkerdata_t;
 
-struct _exec_freq_t {
+struct ir_exec_freq {
        set *set;
        hook_entry_t hook;
        double max;
@@ -98,7 +97,7 @@ set_insert_freq(set * set, const ir_node * irn)
 }
 
 double
-get_block_execfreq(const exec_freq_t *ef, const ir_node * irn)
+get_block_execfreq(const ir_exec_freq *ef, const ir_node * irn)
 {
        if(!ef->infeasible) {
                set *freqs = ef->set;
@@ -115,13 +114,17 @@ get_block_execfreq(const exec_freq_t *ef, const ir_node * irn)
 }
 
 unsigned long
-get_block_execfreq_ulong(const exec_freq_t *ef, const ir_node *bb)
+get_block_execfreq_ulong(const ir_exec_freq *ef, const ir_node *bb)
 {
        double f       = get_block_execfreq(ef, bb);
-       return (int) (f > ef->min_non_zero ? ef->m * f + ef->b : 1.0);
+       int res        = (int) (f > ef->min_non_zero ? ef->m * f + ef->b : 1.0);
+
+       // printf("%20.6f %10d\n", f, res);
+       return res;
 }
 
-#define ZERO(x)   (fabs(x) < 0.0001)
+#define EPSILON                0.0001
+#define UNDEF(x)    !(x > EPSILON)
 
 static void
 block_walker(ir_node * bb, void * data)
@@ -190,14 +193,14 @@ get_cf_probability(ir_node *bb, int pos, double loop_weight)
 static void exec_freq_node_info(void *ctx, FILE *f, const ir_node *irn)
 {
        if(is_Block(irn)) {
-               exec_freq_t *ef = ctx;
+               ir_exec_freq *ef = ctx;
                fprintf(f, "execution frequency: %g/%lu\n", get_block_execfreq(ef, irn), get_block_execfreq_ulong(ef, irn));
        }
 }
 
-exec_freq_t *create_execfreq(ir_graph *irg)
+ir_exec_freq *create_execfreq(ir_graph *irg)
 {
-       exec_freq_t *execfreq = xmalloc(sizeof(execfreq[0]));
+       ir_exec_freq *execfreq = xmalloc(sizeof(execfreq[0]));
        memset(execfreq, 0, sizeof(execfreq[0]));
        execfreq->set = new_set(cmp_freq, 32);
 
@@ -209,13 +212,13 @@ exec_freq_t *create_execfreq(ir_graph *irg)
        return execfreq;
 }
 
-void set_execfreq(exec_freq_t *execfreq, const ir_node *block, double freq)
+void set_execfreq(ir_exec_freq *execfreq, const ir_node *block, double freq)
 {
        freq_t *f = set_insert_freq(execfreq->set, block);
        f->freq = freq;
 }
 
-exec_freq_t *
+ir_exec_freq *
 compute_execfreq(ir_graph * irg, double loop_weight)
 {
        size_t        size;
@@ -224,7 +227,7 @@ compute_execfreq(ir_graph * irg, double loop_weight)
        int           i;
        freq_t       *freq;
        walkerdata_t  wd;
-       exec_freq_t  *ef;
+       ir_exec_freq  *ef;
        set          *freqs;
 #ifdef USE_GSL
        gsl_vector   *x;
@@ -276,15 +279,16 @@ compute_execfreq(ir_graph * irg, double loop_weight)
                return ef;
        }
 
-       ef->max = MAX_INT_FREQ;
+       ef->max = 0.0;
+
        set_foreach(freqs, freq) {
                const ir_node *bb = freq->irn;
                size_t        idx = PTR_TO_INT(get_irn_link(bb));
 
 #ifdef USE_GSL
-               freq->freq = ZERO(gsl_vector_get(x, idx)) ? 0.0 : gsl_vector_get(x, idx);
+               freq->freq = UNDEF(gsl_vector_get(x, idx)) ? EPSILON : gsl_vector_get(x, idx);
 #else
-               freq->freq = ZERO(x[idx]) ? 0.0 : x[idx];
+               freq->freq = UNDEF(x[idx]) ? EPSILON : x[idx];
 #endif
 
                /* get the maximum exec freq */
@@ -297,13 +301,52 @@ compute_execfreq(ir_graph * irg, double loop_weight)
 
        /* compute m and b of the transformation used to convert the doubles into scaled ints */
        {
-               double l1 = 1.0;
-               double h1 = MAX_INT_FREQ;
+               double smallest_diff = 1.0;
+
                double l2 = ef->min_non_zero;
                double h2 = ef->max;
+               double l1 = 1.0;
+               double h1 = MAX_INT_FREQ;
+
+               double *fs = malloc(set_count(freqs) * sizeof(fs[0]));
+               int i, j, n = 0;
+
+               set_foreach(freqs, freq)
+                       fs[n++] = freq->freq;
+
+               /*
+                * find the smallest difference of the execution frequencies
+                * we try to ressolve it with 1 integer.
+                */
+               for(i = 0; i < n; ++i) {
+                       if(fs[i] <= 0.0)
+                               continue;
+
+                       for(j = i + 1; j < n; ++j) {
+                               double diff = fabs(fs[i] - fs[j]);
+
+                               if(!UNDEF(diff))
+                                       smallest_diff = MIN(diff, smallest_diff);
+                       }
+               }
+
+               /* according to that the slope of the translation function is 1.0 / smallest diff */
+               ef->m = 1.0 / smallest_diff;
+
+               /* the abscissa is then given by */
+               ef->b = l1 - ef->m * l2;
+
+               /*
+                * if the slope is so high that the largest integer would be larger than MAX_INT_FREQ
+                * set the largest int freq to that upper limit and recompute the translation function
+                */
+               if(ef->m * h2 + ef->b > MAX_INT_FREQ) {
+                       ef->m = (h1 - l1) / (h2 - l2);
+                       ef->b = l1 - ef->m * l2;
+               }
 
-               ef->m = (h1 - l1) / (h2 - l2);
-               ef->b = (l1 * h2  - l2 * h1) / (h2 - l2);
+               // printf("smallest_diff: %g, l1: %f, h1: %f, l2: %f, h2: %f, m: %f, b: %f\n", smallest_diff, l1, h1, l2, h2, ef->m, ef->b);
+               free(fs);
        }
 
 #ifdef USE_GSL
@@ -320,7 +363,7 @@ compute_execfreq(ir_graph * irg, double loop_weight)
 }
 
 void
-free_execfreq(exec_freq_t *ef)
+free_execfreq(ir_exec_freq *ef)
 {
        del_set(ef->set);
        unregister_hook(hook_node_info, &ef->hook);