nsz Git - libfirm/blob - ir/opt/proc_cloning.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/opt/proc_cloning.c
   4  * Purpose:     procedure cloning
   5  * Author:      Beyhan Veliev
   6  * Created:
   7  * CVS-ID:      $Id$
   8  * Copyright:   (c) 1998-2005 Universität Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11
  12 /**
  13  * @file proc_cloning.c
  14  *
  15  */
  16 #ifdef HAVE_CONFIG_H
  17 #include "config.h"
  18 #endif
  19
  20 #include <stdarg.h>
  21 #include <string.h>
  22
  23 #include "tv.h"
  24 #include "set.h"
  25 #include "entity.h"
  26 #include "irprog_t.h"
  27 #include "hashptr.h"
  28 #include "irgwalk.h"
  29 #include "proc_cloning.h"
  30 #include "analyze_irg_args.h"
  31 #include "irprintf.h"
  32
  33 /* A macro to iterate sets.*/
  34 #define ITERATE_SET(set_entrys, entry) for(entry = set_first(set_entrys); entry; entry = set_next(set_entrys))
  35
  36 /**
  37  * This struct contains the information triple for a Call, which we need to
  38  * decide if this function must be cloned.
  39  */
  40 typedef struct _entry {
  41   struct triple {
  42     entity        *ent;   /**< The entity of our Call. */
  43     int           pos;    /**< Position of a constant argument of our Call. */
  44     tarval        *tv;    /**< The tarval of this constant argument. */
  45   } t;                    /**< The heuristic triple. */
  46
  47   float         weight;   /**< The estimated weight of this triple. */
  48   struct _entry *next;    /**< used for linking and sorting */
  49 } entry_t;
  50
  51 /**
  52  * Compare two triples.
  53  *
  54  * @return 0 if they are identically
  55  */
  56 static int entry_cmp(const void *elt, const void *key, size_t size)
  57 {
  58   const entry_t *c1 = elt;
  59   const entry_t *c2 = key;
  60
  61   return (c1->t.ent != c2->t.ent) || (c1->t.pos != c2->t.pos) || (c1->t.tv != c2->t.tv);
  62 }
  63
  64 /**
  65  * Hash a element of typ entry_t
  66  *
  67  * @param name    A string (the name of the method)
  68  * @param length  The length of this string
  69  * @param pos     A integer value.
  70  */
  71 static int hash_entry(const entry_t *entry)
  72 {
  73   return HASH_PTR(entry->t.ent) ^ HASH_PTR(entry->t.tv) ^ (entry->t.pos * 9);
  74 }
  75
  76 /**
  77  * Collect all calls in a ir_graph
  78  * to a set.
  79  *
  80  * @param call   A ir_node to be checked.
  81  * @param env    The set where we will collect the calls.
  82  */
  83 static void collect_irg_calls(ir_node *call, void *env)
  84 {
  85   ir_node *call_ptr;
  86   entity *call_ent;
  87   set *entrys;
  88   entry_t key, *entry;
  89   ir_node *call_param;
  90   int i;
  91
  92
  93   /* We collect just "Call" nodes*/
  94   if (get_irn_op(call) != op_Call)
  95     return;
  96
  97   call_ptr = get_Call_ptr(call);
  98
  99   /* Call pointer must be a symconst*/
 100   if (op_SymConst != get_irn_op(call_ptr))
 101     return;
 102   /* Call pointer must be the address of an entity.*/
 103   if (get_SymConst_kind(call_ptr) != symconst_addr_ent)
 104     return;
 105
 106   entrys = env;
 107   call_ent = get_SymConst_entity(call_ptr);
 108
 109   /* In this for loop we collect the calls, that have
 110      an constant parameter. */
 111   for (i = get_Call_n_params(call) - 1; i >= 0; i--) {
 112     call_param = get_Call_param(call, i);
 113     if (is_Const(call_param)) {
 114       /* we have found a Call to collect and we save the informations,
 115          which we need.*/
 116       key.t.ent  = call_ent;
 117       key.t.pos  = i;
 118       key.t.tv   = get_Const_tarval(call_param);
 119       key.weight = 0.0f;
 120
 121       /* We insert our information in the set, where we collect the calls.*/
 122       entry     = set_insert(entrys, &key, sizeof(key), hash_entry(&key));
 123
 124       /* we found one more */
 125       entry->weight += 1.0f;
 126     }
 127   }
 128 }
 129
 130 /*
 131  * Do the procedure cloning. Evaluate a heuristic weight for every
 132  * call(..., Const, ...). If the weight is bigger than threshold,
 133  * clone the entity and fix the calls.
 134  */
 135 void proc_cloning(float threshold)
 136 {
 137   set *set_entrys;
 138   entry_t *entry, *p, *heavy_uses = NULL;
 139   ir_graph *irg;
 140   int i;
 141
 142   set_entrys  = new_set(entry_cmp, 8);
 143   entry       = NULL;
 144
 145   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 146     irg = get_irp_irg(i);
 147     irg_walk_graph(irg, collect_irg_calls, NULL, set_entrys);
 148   }
 149
 150   /* We iterate the set and arrange the element of the set in a plist'
 151      The elements are arranged dependent of their value descending.*/
 152   ITERATE_SET(set_entrys, entry) {
 153     entry->weight *= get_method_param_weight(entry->t.ent, entry->t.pos);
 154
 155     /*
 156      * Do not put entry with a weight < threshold in the list
 157      */
 158     if (entry->weight < threshold)
 159       continue;
 160
 161     /* put entry in the heavy uses list */
 162     entry->next = NULL;
 163     if (! heavy_uses)
 164       heavy_uses = entry;
 165     else {
 166       if (entry->weight >= heavy_uses->weight) {
 167         entry->next = heavy_uses;
 168         heavy_uses  = entry;
 169       }
 170       else {
 171         for (p = heavy_uses; p->next; p = p->next) {
 172           if (entry->weight >= p->next->weight) {
 173                   entry->next = p->next;
 174             p->next     = entry;
 175                   break;
 176           }
 177         }
 178         if (! p->next)
 179           p->next = entry;
 180       }
 181     }
 182   }
 183
 184   /* Print some informations about the list. */
 185   for (entry = heavy_uses; entry; entry = entry->next) {
 186     printf("\nweight: is %f\n", entry->weight);
 187     ir_printf("Call for Method %E\n", entry->t.ent);
 188     printf("Position %i\n", entry->t.pos);
 189     ir_printf("Value %T\n", entry->t.tv);
 190   }
 191 }