nsz Git - libfirm/blob - ir/be/beuses.c

   1 /**
   2  * @file   beuse.c
   3  * @date   27.06.2005
   4  * @author Sebastian Hack, Matthias Braun
   5  *
   6  * Methods to compute when a value will be used again.
   7  *
   8  * Copyright (C) 2005 Universitaet Karlsruhe
   9  * Released under the GPL
  10  */
  11 #ifdef HAVE_CONFIG_H
  12 #include "config.h"
  13 #endif
  14
  15 #include <limits.h>
  16 #include <stdlib.h>
  17
  18 #include "config.h"
  19 #include "obst.h"
  20 #include "pmap.h"
  21 #include "debug.h"
  22
  23 #include "irgwalk.h"
  24 #include "irnode_t.h"
  25 #include "ircons_t.h"
  26 #include "irgraph_t.h"
  27 #include "iredges_t.h"
  28 #include "irdom_t.h"
  29
  30 #include "be_t.h"
  31 #include "beutil.h"
  32 #include "belive_t.h"
  33 #include "benode_t.h"
  34 #include "besched_t.h"
  35 #include "beirgmod.h"
  36 #include "bearch.h"
  37 #include "beuses_t.h"
  38 #include "benodesets.h"
  39
  40 #define SCAN_INTERBLOCK_USES
  41
  42 typedef struct _be_use_t {
  43         const ir_node *block;
  44         const ir_node *node;
  45         unsigned next_use;
  46 } be_use_t;
  47
  48 struct _be_uses_t {
  49         set *uses;
  50         ir_graph *irg;
  51         const exec_freq_t *execfreqs;
  52         const be_lv_t *lv;
  53         DEBUG_ONLY(firm_dbg_module_t *dbg;)
  54 };
  55
  56 static int cmp_use(const void *a, const void *b, size_t n)
  57 {
  58         const be_use_t *p = a;
  59         const be_use_t *q = b;
  60         return !(p->block == q->block && p->node == q->node);
  61 }
  62
  63 static const be_use_t *get_or_set_use_block(be_uses_t *uses,
  64                                             const ir_node *block,
  65                                             const ir_node *def)
  66 {
  67         unsigned hash = HASH_COMBINE(nodeset_hash(block), nodeset_hash(def));
  68         be_use_t temp;
  69         be_use_t* result;
  70
  71         temp.block = block;
  72         temp.node = def;
  73         result = set_find(uses->uses, &temp, sizeof(temp), hash);
  74
  75         if(result == NULL) {
  76                 // insert templ first as we might end in a loop in the get_next_use
  77                 // call otherwise
  78                 temp.next_use = USES_INFINITY;
  79                 result = set_insert(uses->uses, &temp, sizeof(temp), hash);
  80
  81                 result->next_use = be_get_next_use(uses, sched_first(block), 0, def, 0);
  82         }
  83
  84         return result;
  85 }
  86
  87 unsigned be_get_next_use(be_uses_t *uses, const ir_node *from,
  88                          unsigned from_step, const ir_node *def,
  89                          int skip_from_uses)
  90 {
  91         unsigned step = from_step;
  92         ir_node *block = get_nodes_block(from);
  93         const ir_node *node;
  94         const ir_edge_t *edge;
  95
  96         if(skip_from_uses) {
  97                 step++;
  98                 node = sched_next(node);
  99         }
 100
 101         sched_foreach_from(from, node) {
 102                 int i, arity;
 103
 104                 arity = get_irn_arity(node);
 105                 for (i = 0; i < arity; ++i) {
 106                         const ir_node *operand = get_irn_n(node, i);
 107
 108                         if (operand == def) {
 109                                 DBG((uses->dbg, LEVEL_3, "found use of %+F at %+F\n", operand, node));
 110                                 return step;
 111                         }
 112                 }
 113
 114                 step++;
 115         }
 116
 117         if(be_is_live_end(uses->lv, block, def))
 118                 return step;
 119
 120 #ifdef SCAN_INTERBLOCK_USES
 121         {
 122         double best_execfreq = -1;
 123         unsigned next_use = USES_INFINITY;
 124
 125         foreach_block_succ(block, edge) {
 126                 const be_use_t *use;
 127                 const ir_node *succ_block = get_edge_src_irn(edge);
 128                 double execfreq = get_block_execfreq(uses->execfreqs, succ_block);
 129
 130                 //execfreq_sum += execfreq;
 131
 132                 if(execfreq > best_execfreq) {
 133                         best_execfreq = execfreq;
 134
 135                         if(!be_is_live_in(uses->lv, succ_block, def)) {
 136                                 next_use = USES_INFINITY;
 137                                 continue;
 138                         }
 139
 140                         use = get_or_set_use_block(uses, succ_block, def);
 141                         //if(USES_IS_INFINITE(use->next_use))
 142                         //      continue;
 143
 144                         next_use = use->next_use;
 145                 }
 146
 147                 //next_use += use->next_use / execfreq;
 148         }
 149
 150         /*if(next_use == 0)
 151                 return USES_INFINITY;*/
 152
 153         //next_use /= execfreq_sum;
 154
 155         return ((unsigned) next_use) + step;
 156         }
 157 #else
 158         return USES_INFINITY;
 159 #endif
 160 }
 161
 162 be_uses_t *be_begin_uses(ir_graph *irg, const exec_freq_t *execfreqs, const be_lv_t *lv)
 163 {
 164         be_uses_t *uses = xmalloc(sizeof(uses[0]));
 165
 166         edges_assure(irg);
 167
 168         uses->uses = new_set(cmp_use, 512);
 169         uses->irg = irg;
 170         uses->execfreqs = execfreqs;
 171         uses->lv = lv;
 172         FIRM_DBG_REGISTER(uses->dbg, "firm.be.uses");
 173
 174         return uses;
 175 }
 176
 177 void be_end_uses(be_uses_t *uses)
 178 {
 179         del_set(uses->uses);
 180         free(uses);
 181 }