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_t.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         int outermost_loop;
  46         unsigned next_use;
  47         unsigned visited;
  48 } be_use_t;
  49
  50 struct _be_uses_t {
  51         set *uses;
  52         ir_graph *irg;
  53         const be_lv_t *lv;
  54         unsigned visited_counter;
  55         DEBUG_ONLY(firm_dbg_module_t *dbg;)
  56 };
  57
  58 static int cmp_use(const void *a, const void *b, size_t n)
  59 {
  60         const be_use_t *p = a;
  61         const be_use_t *q = b;
  62         return !(p->block == q->block && p->node == q->node);
  63 }
  64
  65 static be_next_use_t get_next_use(be_uses_t *env, ir_node *from,
  66                                                                   unsigned from_step, const ir_node *def,
  67                                                                   int skip_from_uses);
  68
  69 static const be_use_t *get_or_set_use_block(be_uses_t *env,
  70                                             const ir_node *block,
  71                                             const ir_node *def)
  72 {
  73         unsigned hash = HASH_COMBINE(nodeset_hash(block), nodeset_hash(def));
  74         be_use_t temp;
  75         be_use_t* result;
  76
  77         temp.block = block;
  78         temp.node = def;
  79         result = set_find(env->uses, &temp, sizeof(temp), hash);
  80
  81         if(result == NULL) {
  82                 // insert templ first as we might end in a loop in the get_next_use
  83                 // call otherwise
  84                 temp.next_use = USES_INFINITY;
  85                 temp.outermost_loop = -1;
  86                 temp.visited = 0;
  87                 result = set_insert(env->uses, &temp, sizeof(temp), hash);
  88         }
  89
  90         if(result->outermost_loop < 0 && result->visited < env->visited_counter) {
  91                 be_next_use_t next_use;
  92
  93                 result->visited = env->visited_counter;
  94                 next_use = get_next_use(env, sched_first(block), 0, def, 0);
  95                 if(next_use.outermost_loop >= 0) {
  96                         result->next_use = next_use.time;
  97                         result->outermost_loop = next_use.outermost_loop;
  98                         DBG((env->dbg, LEVEL_5, "Setting nextuse of %+F in block %+F to %u (outermostloop %d)\n", def, block, result->next_use, result->outermost_loop));
  99                 }
 100         }
 101
 102         return result;
 103 }
 104
 105 static int be_is_phi_argument(const be_lv_t *lv, const ir_node *block, const ir_node *def)
 106 {
 107         ir_node *node;
 108         ir_node *succ_block = NULL;
 109         const ir_edge_t *edge;
 110         int arity, i;
 111
 112 #if 0
 113         if(get_irn_n_edges_kind(block, EDGE_KIND_BLOCK) > 1)
 114                 return 0;
 115 #endif
 116
 117         foreach_block_succ(block, edge) {
 118                 succ_block = get_edge_src_irn(edge);
 119                 break;
 120         }
 121
 122         arity = get_Block_n_cfgpreds(succ_block);
 123         if(arity <= 1)
 124                 return 0;
 125
 126         for(i = 0; i < arity; ++i) {
 127                 if(get_Block_cfgpred_block(succ_block, i) == block)
 128                         break;
 129         }
 130         assert(i < arity);
 131
 132         sched_foreach(succ_block, node) {
 133                 ir_node *arg;
 134
 135                 if(!is_Phi(node))
 136                         break;
 137
 138                 arg = get_irn_n(node, i);
 139                 if(arg == def)
 140                         return 1;
 141         }
 142
 143         return 0;
 144 }
 145
 146 static be_next_use_t get_next_use(be_uses_t *env, ir_node *from,
 147                                                                   unsigned from_step, const ir_node *def,
 148                                                                   int skip_from_uses)
 149 {
 150         unsigned step = from_step;
 151         ir_node *block = get_nodes_block(from);
 152         ir_node *node;
 153         const ir_edge_t *edge;
 154
 155         if(skip_from_uses) {
 156                 step++;
 157                 from = sched_next(from);
 158         }
 159
 160         sched_foreach_from(from, node) {
 161                 int i, arity;
 162
 163                 if(is_Phi(node)) {
 164                         step++;
 165                         continue;
 166                 }
 167
 168                 arity = get_irn_arity(node);
 169                 for (i = 0; i < arity; ++i) {
 170                         const ir_node *operand = get_irn_n(node, i);
 171
 172                         if (operand == def) {
 173                                 be_next_use_t result;
 174
 175                                 DBG((env->dbg, LEVEL_3, "found use of %+F at %+F\n", operand, node));
 176
 177                                 /**
 178                                  * Spills/Reloads are a special case, they're not really a
 179                                  * usage of a value, continue searching
 180                                  */
 181                                 if (be_is_Spill(node) || be_is_Reload(node)) {
 182                                         return be_get_next_use(env, node, step, node, 1);
 183                                 }
 184
 185                                 result.time = step;
 186                                 result.outermost_loop = get_loop_depth(get_irn_loop(block));
 187                                 return result;
 188                         }
 189                 }
 190
 191                 step++;
 192         }
 193
 194         if(be_is_phi_argument(env->lv, block, def)) {
 195                 // TODO we really should continue searching the uses of the phi,
 196                 // as a phi isn't a real use that implies a reload (because we could
 197                 // easily spill the whole phi)
 198
 199                 be_next_use_t result;
 200                 result.time = step;
 201                 result.outermost_loop = get_loop_depth(get_irn_loop(block));
 202                 return result;
 203         }
 204
 205 #ifdef SCAN_INTERBLOCK_USES
 206         {
 207         unsigned next_use = USES_INFINITY;
 208         int outermost_loop;
 209         be_next_use_t result;
 210         ir_loop *loop = get_irn_loop(block);
 211         int loopdepth = get_loop_depth(loop);
 212         int found_visited = 0;
 213         int found_use = 0;
 214         ir_graph *irg = get_irn_irg(block);
 215         ir_node *startblock = get_irg_start_block(irg);
 216
 217         outermost_loop = loopdepth;
 218         foreach_block_succ(block, edge) {
 219                 const be_use_t *use;
 220                 const ir_node *succ_block = get_edge_src_irn(edge);
 221                 ir_loop *succ_loop;
 222                 int use_dist;
 223
 224                 if(succ_block == startblock)
 225                         continue;
 226
 227                 DBG((env->dbg, LEVEL_5, "Checking succ of block %+F: %+F (for use of %+F)\n", block, succ_block, def));
 228                 if(!be_is_live_in(env->lv, succ_block, def)) {
 229                         //next_use = USES_INFINITY;
 230                         DBG((env->dbg, LEVEL_5, "   not live in\n"));
 231                         continue;
 232                 }
 233
 234                 use = get_or_set_use_block(env, succ_block, def);
 235                 DBG((env->dbg, LEVEL_5, "Found %u (loopdepth %d) (we're in block %+F)\n", use->next_use,
 236                                         use->outermost_loop, block));
 237                 if(USES_IS_INFINITE(use->next_use)) {
 238                         if(use->outermost_loop < 0) {
 239                                 found_visited = 1;
 240                         }
 241                         continue;
 242                 }
 243
 244                 found_use = 1;
 245                 use_dist = use->next_use;
 246
 247                 succ_loop = get_irn_loop(succ_block);
 248                 if(get_loop_depth(succ_loop) < loopdepth) {
 249                         int factor = (loopdepth - get_loop_depth(succ_loop)) * 5000;
 250                         DBG((env->dbg, LEVEL_5, "Increase usestep because of loop out edge %d -> %d (%u)\n", factor));
 251                         // TODO we should use the number of nodes in the loop or so...
 252                         use_dist += factor;
 253                 }
 254
 255                 if(use_dist < next_use) {
 256                         next_use = use_dist;
 257                         outermost_loop = use->outermost_loop;
 258                 }
 259         }
 260
 261         if(loopdepth < outermost_loop)
 262                 outermost_loop = loopdepth;
 263
 264         result.time = next_use + step;
 265         result.outermost_loop = outermost_loop;
 266
 267         if(!found_use && found_visited) {
 268                 // the current result is correct for the current search, but isn't
 269                 // generally correct, so mark it
 270                 result.outermost_loop = -1;
 271         }
 272         DBG((env->dbg, LEVEL_5, "Result: %d (outerloop: %d)\n", result.time, result.outermost_loop));
 273         return result;
 274         }
 275 #else
 276         return USES_INFINITY;
 277 #endif
 278 }
 279
 280 be_next_use_t be_get_next_use(be_uses_t *env, ir_node *from,
 281                          unsigned from_step, const ir_node *def,
 282                          int skip_from_uses)
 283 {
 284         env->visited_counter++;
 285         return get_next_use(env, from, from_step, def, skip_from_uses);
 286 }
 287
 288 be_uses_t *be_begin_uses(ir_graph *irg, const be_lv_t *lv)
 289 {
 290         be_uses_t *env = xmalloc(sizeof(env[0]));
 291
 292         edges_assure(irg);
 293
 294         env->uses = new_set(cmp_use, 512);
 295         env->irg = irg;
 296         env->lv = lv;
 297         env->visited_counter = 0;
 298         FIRM_DBG_REGISTER(env->dbg, "firm.be.uses");
 299
 300         return env;
 301 }
 302
 303 void be_end_uses(be_uses_t *env)
 304 {
 305         del_set(env->uses);
 306         free(env);
 307 }