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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief       Methods to compute when a value will be used again.
   9  * @author      Sebastian Hack, Matthias Braun
  10  * @date        27.06.2005
  11  */
  12 #include "config.h"
  13
  14 #include <limits.h>
  15 #include <stdlib.h>
  16
  17 #include "config.h"
  18 #include "obst.h"
  19 #include "pmap.h"
  20 #include "debug.h"
  21
  22 #include "irgwalk.h"
  23 #include "irnode_t.h"
  24 #include "ircons_t.h"
  25 #include "irgraph_t.h"
  26 #include "iredges_t.h"
  27 #include "irdom_t.h"
  28 #include "util.h"
  29
  30 #include "be_t.h"
  31 #include "beutil.h"
  32 #include "belive_t.h"
  33 #include "benode.h"
  34 #include "besched.h"
  35 #include "beirgmod.h"
  36 #include "bearch.h"
  37 #include "beuses.h"
  38
  39 #define UNKNOWN_OUTERMOST_LOOP  ((unsigned)-1)
  40
  41 typedef struct be_use_t {
  42         const ir_node *block;
  43         const ir_node *node;
  44         unsigned outermost_loop;
  45         unsigned next_use;
  46         ir_visited_t visited;
  47 } be_use_t;
  48
  49 /**
  50  * The "uses" environment.
  51  */
  52 struct be_uses_t {
  53         set *uses;                          /**< cache: contains all computed uses so far. */
  54         ir_graph *irg;                      /**< the graph for this environment. */
  55         const be_lv_t *lv;                  /**< the liveness for the graph. */
  56         ir_visited_t visited_counter;       /**< current search counter. */
  57         DEBUG_ONLY(firm_dbg_module_t *dbg;  /**< debug module for debug messages. */)
  58 };
  59
  60 /**
  61  * Set-compare two uses.
  62  */
  63 static int cmp_use(const void *a, const void *b, size_t n)
  64 {
  65         const be_use_t *p = (const be_use_t*)a;
  66         const be_use_t *q = (const be_use_t*)b;
  67         (void) n;
  68
  69         return !(p->block == q->block && p->node == q->node);
  70 }
  71
  72 static be_next_use_t get_next_use(be_uses_t *env, ir_node *from,
  73                                                                   const ir_node *def, int skip_from_uses);
  74
  75 /**
  76  * Return the use for the given definition in the given block if exists,
  77  * else create it.
  78  *
  79  * @param env    the uses environment
  80  * @param block  the block we search the use in
  81  * @param def    the definition of the value we are searching
  82  */
  83 static const be_use_t *get_or_set_use_block(be_uses_t *env,
  84                                             const ir_node *block,
  85                                             const ir_node *def)
  86 {
  87         unsigned hash = hash_combine(hash_irn(block), hash_irn(def));
  88         be_use_t temp;
  89         be_use_t* result;
  90
  91         temp.block = block;
  92         temp.node = def;
  93         result = set_find(be_use_t, env->uses, &temp, sizeof(temp), hash);
  94
  95         if (result == NULL) {
  96                 // insert templ first as we might end in a loop in the get_next_use
  97                 // call otherwise
  98                 temp.next_use = USES_INFINITY;
  99                 temp.outermost_loop = UNKNOWN_OUTERMOST_LOOP;
 100                 temp.visited = 0;
 101                 result = set_insert(be_use_t, env->uses, &temp, sizeof(temp), hash);
 102         }
 103
 104         if (result->outermost_loop == UNKNOWN_OUTERMOST_LOOP && result->visited < env->visited_counter) {
 105                 be_next_use_t next_use;
 106
 107                 result->visited = env->visited_counter;
 108                 next_use = get_next_use(env, sched_first(block), def, 0);
 109                 if (next_use.outermost_loop != UNKNOWN_OUTERMOST_LOOP) {
 110                         result->next_use = next_use.time;
 111                         result->outermost_loop = next_use.outermost_loop;
 112                         DBG((env->dbg, LEVEL_5, "Setting nextuse of %+F in block %+F to %u (outermostloop %d)\n",
 113                                 def, block, result->next_use, result->outermost_loop));
 114                 }
 115         }
 116
 117         return result;
 118 }
 119
 120 /**
 121  * Check if a value of the given definition is used in the given block
 122  * as a Phi argument.
 123  *
 124  * @param block  the block to check
 125  * @param def    the definition of the value
 126  *
 127  * @return non-zero if the value is used in the given block as a Phi argument
 128  * in one of its successor blocks.
 129  */
 130 static int be_is_phi_argument(const ir_node *block, const ir_node *def)
 131 {
 132         if (get_irn_n_edges_kind(block, EDGE_KIND_BLOCK) < 1)
 133                 return 0;
 134
 135         ir_node *const succ_block = get_first_block_succ(block);
 136
 137         if (get_Block_n_cfgpreds(succ_block) <= 1) {
 138                 /* no Phis in the successor */
 139                 return 0;
 140         }
 141
 142         /* find the index of block in its successor */
 143         int const i = get_Block_cfgpred_pos(succ_block, block);
 144         assert(i >= 0);
 145
 146         /* iterate over the Phi nodes in the successor and check if def is
 147          * one of its arguments */
 148         sched_foreach(succ_block, node) {
 149                 ir_node *arg;
 150
 151                 if (!is_Phi(node)) {
 152                         /* found first non-Phi node, we can stop the search here */
 153                         break;
 154                 }
 155
 156                 arg = get_irn_n(node, i);
 157                 if (arg == def)
 158                         return 1;
 159         }
 160
 161         return 0;
 162 }
 163
 164 /**
 165  * Retrieve the scheduled index (the "step") of this node in its
 166  * block.
 167  *
 168  * @param node  the node
 169  */
 170 static inline unsigned get_step(const ir_node *node)
 171 {
 172         return (unsigned)PTR_TO_INT(get_irn_link(node));
 173 }
 174
 175 /**
 176  * Set the scheduled index (the "step") of this node in its
 177  * block.
 178  *
 179  * @param node  the node
 180  * @param step  the scheduled index of the node
 181  */
 182 static inline void set_step(ir_node *node, unsigned step)
 183 {
 184         set_irn_link(node, INT_TO_PTR(step));
 185 }
 186
 187 /**
 188  * Find the next use of a value defined by def, starting at node from.
 189  *
 190  * @param env             the uses environment
 191  * @param from            the node at which we should start the search
 192  * @param def             the definition of the value
 193  * @param skip_from_uses  if non-zero, ignore from uses
 194  */
 195 static be_next_use_t get_next_use(be_uses_t *env, ir_node *from,
 196                                                                   const ir_node *def, int skip_from_uses)
 197 {
 198         unsigned  step;
 199         ir_node  *block = get_nodes_block(from);
 200         ir_node  *next_use_node;
 201         ir_node  *node;
 202         unsigned  timestep;
 203         unsigned  next_use_step;
 204
 205         assert(skip_from_uses == 0 || skip_from_uses == 1);
 206         if (skip_from_uses) {
 207                 from = sched_next(from);
 208         }
 209
 210         next_use_node = NULL;
 211         next_use_step = INT_MAX;
 212         timestep      = get_step(from);
 213         foreach_out_edge(def, edge) {
 214                 unsigned node_step;
 215                 node = get_edge_src_irn(edge);
 216
 217                 if (is_Anchor(node))
 218                         continue;
 219                 if (get_nodes_block(node) != block)
 220                         continue;
 221                 if (is_Phi(node))
 222                         continue;
 223
 224                 node_step = get_step(node);
 225                 if (node_step < timestep)
 226                         continue;
 227                 if (node_step < next_use_step) {
 228                         next_use_node = node;
 229                         next_use_step = node_step;
 230                 }
 231         }
 232
 233         if (next_use_node != NULL) {
 234                 be_next_use_t result;
 235                 result.time           = next_use_step - timestep + skip_from_uses;
 236                 result.outermost_loop = get_loop_depth(get_irn_loop(block));
 237                 result.before         = next_use_node;
 238                 return result;
 239         }
 240
 241         node = sched_last(block);
 242         step = get_step(node) + 1 + timestep + skip_from_uses;
 243
 244         if (be_is_phi_argument(block, def)) {
 245                 // TODO we really should continue searching the uses of the phi,
 246                 // as a phi isn't a real use that implies a reload (because we could
 247                 // easily spill the whole phi)
 248
 249                 be_next_use_t result;
 250                 result.time           = step;
 251                 result.outermost_loop = get_loop_depth(get_irn_loop(block));
 252                 result.before         = block;
 253                 return result;
 254         }
 255
 256         {
 257         unsigned  next_use   = USES_INFINITY;
 258         unsigned  outermost_loop;
 259         be_next_use_t result;
 260         ir_loop  *loop          = get_irn_loop(block);
 261         unsigned  loopdepth     = get_loop_depth(loop);
 262         int       found_visited = 0;
 263         int       found_use     = 0;
 264
 265         result.before  = NULL;
 266         outermost_loop = loopdepth;
 267         foreach_block_succ(block, edge) {
 268                 const be_use_t *use;
 269                 const ir_node *succ_block = get_edge_src_irn(edge);
 270                 ir_loop *succ_loop;
 271                 unsigned use_dist;
 272
 273                 DBG((env->dbg, LEVEL_5, "Checking succ of block %+F: %+F (for use of %+F)\n", block, succ_block, def));
 274                 if (!be_is_live_in(env->lv, succ_block, def)) {
 275                         //next_use = USES_INFINITY;
 276                         DBG((env->dbg, LEVEL_5, "   not live in\n"));
 277                         continue;
 278                 }
 279
 280                 use = get_or_set_use_block(env, succ_block, def);
 281                 DBG((env->dbg, LEVEL_5, "Found %u (loopdepth %u) (we're in block %+F)\n", use->next_use,
 282                                         use->outermost_loop, block));
 283                 if (USES_IS_INFINITE(use->next_use)) {
 284                         if (use->outermost_loop == UNKNOWN_OUTERMOST_LOOP) {
 285                                 found_visited = 1;
 286                         }
 287                         continue;
 288                 }
 289
 290                 found_use = 1;
 291                 use_dist = use->next_use;
 292
 293                 succ_loop = get_irn_loop(succ_block);
 294                 if (get_loop_depth(succ_loop) < loopdepth) {
 295                         unsigned factor = (loopdepth - get_loop_depth(succ_loop)) * 5000;
 296                         DBG((env->dbg, LEVEL_5, "Increase usestep because of loop out edge %d -> %d (%u)\n", factor));
 297                         // TODO we should use the number of nodes in the loop or so...
 298                         use_dist += factor;
 299                 }
 300
 301                 if (use_dist < next_use) {
 302                         next_use       = use_dist;
 303                         outermost_loop = use->outermost_loop;
 304                         result.before  = use->node;
 305                 }
 306         }
 307
 308         if (loopdepth < outermost_loop)
 309                 outermost_loop = loopdepth;
 310
 311         result.time           = next_use + step;
 312         result.outermost_loop = outermost_loop;
 313
 314         if (!found_use && found_visited) {
 315                 // the current result is correct for the current search, but isn't
 316                 // generally correct, so mark it
 317                 result.outermost_loop = UNKNOWN_OUTERMOST_LOOP;
 318         }
 319         DBG((env->dbg, LEVEL_5, "Result: %d (outerloop: %u)\n", result.time, result.outermost_loop));
 320         return result;
 321         }
 322 }
 323
 324 be_next_use_t be_get_next_use(be_uses_t *env, ir_node *from,
 325                          const ir_node *def, int skip_from_uses)
 326 {
 327         ++env->visited_counter;
 328         return get_next_use(env, from, def, skip_from_uses);
 329 }
 330
 331 /**
 332  * Pre-block walker, set the step number for every scheduled node
 333  * in increasing order.
 334  *
 335  * After this, two scheduled nodes can be easily compared for the
 336  * "scheduled earlier in block" property.
 337  */
 338 static void set_sched_step_walker(ir_node *block, void *data)
 339 {
 340         unsigned step = 0;
 341         (void) data;
 342
 343         sched_foreach(block, node) {
 344                 set_step(node, step);
 345                 if (is_Phi(node))
 346                         continue;
 347                 ++step;
 348         }
 349 }
 350
 351 be_uses_t *be_begin_uses(ir_graph *irg, const be_lv_t *lv)
 352 {
 353         be_uses_t *env = XMALLOC(be_uses_t);
 354
 355         assure_edges(irg);
 356
 357         //set_using_irn_link(irg);
 358
 359         /* precalculate sched steps */
 360         irg_block_walk_graph(irg, set_sched_step_walker, NULL, NULL);
 361
 362         env->uses = new_set(cmp_use, 512);
 363         env->irg = irg;
 364         env->lv = lv;
 365         env->visited_counter = 0;
 366         FIRM_DBG_REGISTER(env->dbg, "firm.be.uses");
 367
 368         return env;
 369 }
 370
 371 void be_end_uses(be_uses_t *env)
 372 {
 373         //clear_using_irn_link(env->irg);
 374         del_set(env->uses);
 375         free(env);
 376 }