nsz Git - libfirm/blob - ir/ana/irlivechk.c

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file    livechk.c
  22  * @date    21.04.2007
  23  * @author  Sebastian Hack
  24  * @version $Id$
  25  * @summary
  26  *
  27  * Liveness checks as developed by Benoit Boissinot, Fabrice Rastello and myself.
  28  *
  29  * The speciality here is, that nothing has to be recomputed if new nodes are created
  30  * or old ones deleted.
  31  *
  32  * This algo has one core routine check_live_end_internal() which performs the liveness check.
  33  * It only relies on the precomputation done in the constructor, which in turn needs:
  34  * - out edges
  35  * - the dominance tree
  36  * - data obtained from a depth-first-search
  37  *
  38  * The precomputation remains valid as long as the CFG is not altered.
  39  */
  40
  41 #include <stdio.h>
  42
  43 #include "irgraph_t.h"
  44 #include "irphase_t.h"
  45 #include "iredges_t.h"
  46 #include "irprintf.h"
  47 #include "irdump.h"
  48
  49 #include "dfs_t.h"
  50 #include "bitset.h"
  51 #include "util.h"
  52
  53 #include "irlivechk.h"
  54
  55 #define ENABLE_STATS
  56
  57 #ifdef ENABLE_STATS
  58 #define STAT_INC(memb)  ++lv->stat->memb
  59 #else
  60 #define STAT_INC(memb)
  61 #endif
  62
  63 typedef struct _bl_info_t {
  64         ir_node *block;            /**< The block. */
  65
  66         int id;                    /**< a tight number for the block.
  67                                                                  we're just reusing the pre num from
  68                                                                  the DFS. */
  69
  70         bitset_t *red_reachable;   /**< Holds all id's if blocks reachable
  71                                                                  in the CFG modulo back edges. */
  72
  73         bitset_t *be_tgt_reach;    /**< target blocks of back edges whose
  74                                                                  sources are reachable from this block
  75                                                                  in the reduced graph. */
  76
  77         bitset_t *be_tgt_dom;      /**< target blocks of back edges which
  78                                                                  are dominated by this block. */
  79 } bl_info_t;
  80
  81 #define get_block_info(lv, bl) ((bl_info_t *) phase_get_irn_data(&(lv)->ph, bl))
  82
  83 struct _lv_chk_t {
  84         ir_phase ph;
  85         dfs_t *dfs;
  86         DEBUG_ONLY(firm_dbg_module_t *dbg;)
  87         int n_blocks;
  88         bitset_t *back_edge_src;
  89         bitset_t *back_edge_tgt;
  90         bl_info_t **map;
  91         lv_chk_stat_t *stat;        /**< statistics information. */
  92         lv_chk_stat_t stat_data;
  93 };
  94
  95 static void *init_block_data(ir_phase *ph, ir_node *irn, void *old)
  96 {
  97         lv_chk_t *lv      = container_of(ph, lv_chk_t, ph);
  98         bl_info_t *bi     = phase_alloc(ph, sizeof(bi[0]));
  99
 100         bi->id            = dfs_get_pre_num(lv->dfs, irn);
 101         bi->block         = irn;
 102         bi->red_reachable = bitset_obstack_alloc(phase_obst(ph), lv->n_blocks);
 103         bi->be_tgt_reach  = bitset_obstack_alloc(phase_obst(ph), lv->n_blocks);
 104         bi->be_tgt_dom    = bitset_obstack_alloc(phase_obst(ph), lv->n_blocks);
 105         return bi;
 106 }
 107
 108 /**
 109  * Filter function to select all nodes for which liveness is computed.
 110  * @param irn A node.
 111  * @return    1 if the node shall be considered in liveness, 0 if not.
 112  */
 113 static INLINE int is_liveness_node(const ir_node *irn)
 114 {
 115         switch(get_irn_opcode(irn)) {
 116         case iro_Block:
 117         case iro_Bad:
 118         case iro_End:
 119                 return 0;
 120         default:;
 121         }
 122
 123         return 1;
 124 }
 125
 126 /**
 127  * Compute the transitive closure on the reduced graph.
 128  * The reduced graph is the original graph without back edges.
 129  * Since that is a DAG, a reverse post order of the graph gives a toposort
 130  * which is ideally suited to compute the transitive closure.
 131  * Note also, that the DFS tree of the reduced graph is the same than the one
 132  * of the original graph. This saves us computing a new reverse post order.
 133  * We also can re-use the DFS tree of the original graph.
 134  */
 135 static void red_trans_closure(lv_chk_t *lv)
 136 {
 137         int i, n;
 138
 139         for (i = 0, n = dfs_get_n_nodes(lv->dfs); i < n; ++i) {
 140                 ir_node *bl   = dfs_get_post_num_node(lv->dfs, i);
 141                 bl_info_t *bi = get_block_info(lv, bl);
 142
 143                 const ir_edge_t *edge;
 144
 145                 foreach_block_succ (bl, edge) {
 146                         ir_node *succ = get_edge_src_irn(edge);
 147                         bl_info_t *si = get_block_info(lv, succ);
 148                         dfs_edge_kind_t kind = dfs_get_edge_kind(lv->dfs, bl, succ);
 149
 150                         /*
 151                          * if the successor is no back edge, include all reachable
 152                          * blocks from there into the reachable set of the current node
 153                          */
 154                         if (kind != DFS_EDGE_BACK) {
 155                                 assert(dfs_get_post_num(lv->dfs, bl)
 156                                                 > dfs_get_post_num(lv->dfs, succ));
 157                                 bitset_or(bi->red_reachable, si->red_reachable);
 158                                 bitset_set(bi->red_reachable, si->id);
 159                         }
 160
 161                         /* mark the block as a back edge src and succ as back edge tgt. */
 162                         else {
 163                                 bitset_set(lv->back_edge_src, bi->id);
 164                                 bitset_set(lv->back_edge_tgt, si->id);
 165                         }
 166                 }
 167
 168         }
 169
 170 }
 171
 172 /**
 173  * Compute the two back edge sets for each block.
 174  * <code>be_tgt_reach</code> contains all target blocks of a back edges reachable from a node.
 175  * <code>be_tgt_dom</code> contains all target blocks of back edges strictly dominated
 176  * by a node.
 177  */
 178 static void compute_back_edge_sets(lv_chk_t *lv, ir_node *bl)
 179 {
 180         bl_info_t *bi = phase_get_or_set_irn_data(&(lv)->ph, bl);
 181         bitset_t *tmp = bitset_alloca(lv->n_blocks);
 182
 183         bitset_pos_t elm;
 184         ir_node *n;
 185
 186         dominates_for_each (bl, n) {
 187                 bl_info_t *ni = phase_get_or_set_irn_data(&(lv)->ph, n);
 188
 189                 /* compute information for dominance sub tree */
 190                 compute_back_edge_sets(lv, n);
 191
 192                 /*
 193                  * of course all blocks dominated by blocks in the
 194                  * subtree are also dominated by bl.
 195                  */
 196                 bitset_or(bi->be_tgt_dom, ni->be_tgt_dom);
 197
 198                 /*
 199                  * add the immeditate dominee to the back edge tgt dominance
 200                  * bitset if it is the target node of a back edge.
 201                  */
 202                 if (bitset_is_set(lv->back_edge_tgt, ni->id))
 203                         bitset_set(bi->be_tgt_dom, ni->id);
 204         }
 205
 206         /*
 207          * iterate over all back edge src nodes which are reachable from
 208          * this nodes and put the targets of the back edges in the be_tgt_reach
 209          * bitset of the node.
 210          */
 211         bitset_copy(tmp, bi->red_reachable);
 212         bitset_set(tmp, bi->id);
 213         bitset_and(tmp, lv->back_edge_src);
 214         bitset_foreach (tmp, elm) {
 215                 ir_node *src = lv->map[elm]->block;
 216                 const ir_edge_t *edge;
 217
 218                 foreach_block_succ (src, edge) {
 219                         ir_node *succ        = get_edge_src_irn(edge);
 220                         dfs_edge_kind_t kind = dfs_get_edge_kind(lv->dfs, src, succ);
 221
 222                         if (kind == DFS_EDGE_BACK) {
 223                                 bl_info_t *si = get_block_info(lv, succ);
 224                                 bitset_set(bi->be_tgt_reach, si->id);
 225                         }
 226                 }
 227         }
 228 }
 229
 230 lv_chk_t *lv_chk_new(ir_graph *irg)
 231 {
 232         lv_chk_t *res = xmalloc(sizeof(res[0]));
 233         struct obstack *obst;
 234         int i;
 235
 236         phase_init(&res->ph, "liveness check", irg, PHASE_DEFAULT_GROWTH, init_block_data, NULL);
 237         obst = phase_obst(&res->ph);
 238
 239         FIRM_DBG_REGISTER(res->dbg, "ir.ana.lvchk");
 240
 241         res->dfs           = dfs_new(&absgraph_irg_cfg_succ, irg);
 242         res->n_blocks      = dfs_get_n_nodes(res->dfs);
 243         res->back_edge_src = bitset_obstack_alloc(obst, res->n_blocks);
 244         res->back_edge_tgt = bitset_obstack_alloc(obst, res->n_blocks);
 245         res->map           = obstack_alloc(obst, res->n_blocks * sizeof(res->map[0]));
 246
 247 #ifdef ENABLE_STATS
 248         memset(&res->stat_data, 0, sizeof(res->stat_data));
 249         res->stat = &res->stat_data;
 250 #endif
 251 #if 0
 252         {
 253                 char name[256];
 254                 FILE *f;
 255                 ir_snprintf(name, sizeof(name), "dfs_%F.dot", irg);
 256                 if ((f = fopen(name, "wt")) != NULL) {
 257                         dfs_dump(res->dfs, f);
 258                         fclose(f);
 259                 }
 260                 dump_ir_block_graph(irg, "-lvchk");
 261         }
 262 #endif
 263
 264         /* fill the map which maps pre_num to block infos */
 265         for (i = res->n_blocks - 1; i >= 0; --i) {
 266                 ir_node *irn = dfs_get_pre_num_node(res->dfs, i);
 267                 res->map[i]  = phase_get_or_set_irn_data(&res->ph, irn);
 268         }
 269
 270         /* first of all, compute the transitive closure of the CFG *without* back edges */
 271         red_trans_closure(res);
 272
 273         /* now fill the two remaining bitsets concerning back edges */
 274         compute_back_edge_sets(res, get_irg_start_block(irg));
 275
 276         DEBUG_ONLY_NICE {
 277                 DBG((res->dbg, LEVEL_1, "liveness chk in %+F\n", irg));
 278                 for (i = res->n_blocks - 1; i >= 0; --i) {
 279                         ir_node *irn  = dfs_get_pre_num_node(res->dfs, i);
 280                         bl_info_t *bi = get_block_info(res, irn);
 281                         DBG((res->dbg, LEVEL_1, "lv_chk for %d -> %+F\n", i, irn));
 282                         DBG((res->dbg, LEVEL_1, "\tred reach: %B\n", bi->red_reachable));
 283                         DBG((res->dbg, LEVEL_1, "\ttgt reach: %B\n", bi->be_tgt_reach));
 284                         DBG((res->dbg, LEVEL_1, "\ttgt dom:   %B\n", bi->be_tgt_dom));
 285                 }
 286         }
 287
 288         DBG((res->dbg, LEVEL_1, "back edge src: %B\n", res->back_edge_src));
 289         DBG((res->dbg, LEVEL_1, "back edge tgt: %B\n", res->back_edge_tgt));
 290
 291         return res;
 292 }
 293
 294 void lv_chk_free(lv_chk_t *lv)
 295 {
 296         obstack_free(phase_obst(&lv->ph), NULL);
 297         dfs_free(lv->dfs);
 298         xfree(lv);
 299 }
 300
 301 const lv_chk_stat_t *lv_chk_get_stat(const lv_chk_t *lv)
 302 {
 303 #ifdef ENABLE_STATS
 304         return lv->stat;
 305 #else
 306         return NULL;
 307 #endif
 308 }
 309
 310 /**
 311  * Check if a node is live at the end of a block.
 312  * This function is for internal use as its code is shared between
 313  * the in/end routines below. It is almost the "live_end" routine
 314  * but passing in the bitset for recording the blocks where the variable
 315  * is used saves some effort in the "live_in" routine. See below for
 316  * details.
 317  *
 318  * @param lv    The liveness check environment.
 319  * @param what  The node to check for.
 320  * @param bl    The block under investigation.
 321  * @param uses  A bitset where this routine records all ids of blocks
 322  *              where this variable is used. Note that the bitset
 323  *              is only guaranteed to be filled if the node was not
 324  *              live at the end of the block.
 325  * @return      1, if @p what is live at the end at @p bl.
 326  */
 327 unsigned lv_chk_bl_xxx(const lv_chk_t *lv, const ir_node *bl, const ir_node *what)
 328 {
 329         ir_node *what_bl;
 330
 331         assert(is_Block(bl) && "can only check for liveness in a block");
 332
 333         if (!is_liveness_node(what))
 334                 return 0;
 335
 336         what_bl = get_nodes_block(what);
 337         if (!block_dominates(what_bl, bl)) {
 338                 STAT_INC(n_no_dominance);
 339                 return 0;
 340         }
 341
 342         /*
 343          * If the block in question is the same as the definition block,
 344          * the algorithm is simple. Just check for uses not inside this block.
 345          */
 346         if (what_bl == bl) {
 347                 int res = 0;
 348                 const ir_edge_t *edge;
 349
 350                 STAT_INC(n_def_block);
 351                 DBG((lv->dbg, LEVEL_2, "lv check same block %+F in %+F\n", what, bl));
 352                 foreach_out_edge (what, edge) {
 353                         ir_node *use    = get_edge_src_irn(edge);
 354                         ir_node *use_bl;
 355
 356                         if (!is_liveness_node(use))
 357                                 continue;
 358
 359                         use_bl = get_nodes_block(use);
 360                         if (is_Phi(use)) {
 361                                 int pos = get_edge_src_pos(edge);
 362                                 use_bl  = get_Block_cfgpred_block(use_bl, pos);
 363
 364                                 if (use_bl == bl) {
 365                                         DBG((lv->dbg, LEVEL_2, "\tphi %+F in succ %+F,%d -> live end\n", use, use_bl, pos));
 366                                         res |= lv_chk_state_end;
 367                                 }
 368                         }
 369
 370                         if (use_bl != what_bl)
 371                                 return lv_chk_state_end | lv_chk_state_out;
 372                 }
 373
 374                 return res;
 375         }
 376
 377         /* this is the complicated case */
 378         else {
 379                 bitset_t *visited   = bitset_alloca(lv->n_blocks);
 380                 bitset_t *to_visit  = bitset_alloca(lv->n_blocks);
 381                 bitset_t *next      = bitset_alloca(lv->n_blocks);
 382                 bitset_t *uses      = bitset_alloca(lv->n_blocks);
 383                 bl_info_t *def      = get_block_info(lv, what_bl);
 384                 bl_info_t *bli      = get_block_info(lv, bl);
 385                 int res = 0;
 386
 387                 const ir_edge_t *edge;
 388
 389                 foreach_out_edge (what, edge) {
 390                         ir_node *user   = get_edge_src_irn(edge);
 391                         ir_node *use_bl;
 392                         bl_info_t *bi;
 393
 394                         if (!is_liveness_node(user))
 395                                 continue;
 396
 397                         use_bl = get_nodes_block(user);
 398                         if (is_Phi(user)) {
 399                                 int pos          = get_edge_src_pos(edge);
 400
 401                                 use_bl = get_Block_cfgpred_block(use_bl, pos);
 402                                 bi     = get_block_info(lv, use_bl);
 403
 404                                 if (use_bl == bl)
 405                                         res |= lv_chk_state_end | lv_chk_state_in;
 406
 407                                 bitset_set(uses, bi->id);
 408                         }
 409
 410                         else {
 411                                 bi = get_block_info(lv, use_bl);
 412                                 bitset_set(uses, bi->id);
 413                                 if (use_bl == bl)
 414                                         res |= lv_chk_state_in;
 415                         }
 416
 417                 }
 418                 DBG((lv->dbg, LEVEL_2, "\tuses: %B\n", uses));
 419
 420                 bitset_clear(uses, def->id);
 421                 bitset_set(to_visit, bli->id);
 422                 do {
 423                         int id        = bitset_next_set(to_visit, 0);
 424                         bl_info_t *bi = lv->map[id];
 425
 426                         DBG((lv->dbg, LEVEL_2, "\tto visit: %B\n", to_visit));
 427                         DBG((lv->dbg, LEVEL_2, "\tvisited:  %B\n", visited));
 428
 429                         /*
 430                          * if one of the blocks is reachable, the node must be live there.
 431                          * Note that this is not sufficient, since the nodes reachable
 432                          * via back edges are not contained in the red_reachable set.
 433                          */
 434                         if (bitset_intersect(bi->red_reachable, uses))
 435                                 return lv_chk_state_end | lv_chk_state_out | lv_chk_state_in;
 436
 437                         /*
 438                          * if not, we have to check the back edges in question, if
 439                          * they lead to places which are reachable.
 440                          */
 441                         else {
 442                                 bitset_set(visited, id);
 443                                 bitset_or(visited, bi->red_reachable);
 444
 445                                 bitset_copy(next, bi->be_tgt_reach);
 446                                 bitset_and(next, def->be_tgt_dom);
 447                                 DBG((lv->dbg, LEVEL_2, "\tnext: %B\n----\n", next));
 448
 449                                 if (bitset_intersect(uses, next))
 450                                         return lv_chk_state_end | lv_chk_state_out | lv_chk_state_in;
 451
 452                                 bitset_or(to_visit, next);
 453                                 bitset_andnot(to_visit, visited);
 454
 455                         }
 456                 } while (!bitset_is_empty(to_visit));
 457
 458                 return res;
 459         }
 460
 461         return 0;
 462 }