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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/irconsconfirm.c
   4  * Purpose:     Construction of Confirm nodes
   5  * Author:      Michael Beck
   6  * Modified by:
   7  * Created:     6.2005
   8  * CVS-ID:      $Id$
   9  * Copyright:   (C) 2002-2005 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 /**
  14  * @file irconsconfirm.c
  15  *
  16  * Construction of Confirm nodes
  17  *
  18  * @author Michael Beck
  19  */
  20
  21 #ifdef HAVE_CONFIG_H
  22 # include "config.h"
  23 #endif
  24
  25 #include "irgraph_t.h"
  26 #include "irnode_t.h"
  27 #include "ircons_t.h"
  28 #include "irgmod.h"
  29 #include "iropt_dbg.h"
  30 #include "iredges_t.h"
  31 #include "irgwalk.h"
  32 #include "irprintf.h"
  33
  34 /**
  35  * Walker environment.
  36  */
  37 typedef struct _env_t {
  38   unsigned num_confirms;  /**< number of inserted Confirm nodes */
  39   unsigned num_consts;    /**< number of constants placed */
  40   unsigned num_eq;        /**< number of equalities placed */
  41 } env_t;
  42
  43 /**
  44  * Return the effective use block of a node and it's predecessor on
  45  * position pos.
  46  *
  47  * @param node  the node
  48  * @param pos   the position of the used input
  49  *
  50  * This handles correctly Phi nodes.
  51  */
  52 static ir_node *get_effective_use_block(ir_node *node, int pos)
  53 {
  54   /* the effective use of a Phi is in its predecessor block */
  55   if (is_Phi(node))
  56     return get_nodes_block(get_irn_n(node, pos));
  57   else
  58     return get_nodes_block(node);
  59 }
  60
  61 /**
  62  * Handle a CASE-branch.
  63  *
  64  * @param block   the block which is entered by the branch
  65  * @param irn     the node expressing the switch value
  66  * @param nr      the branch label
  67  * @param env     statistical environment
  68  *
  69  * Branch labels are a simple case. We can replace the value
  70  * by a Const with the branch label.
  71  */
  72 static void handle_case(ir_node *block, ir_node *irn, long nr, env_t *env)
  73 {
  74   const ir_edge_t *edge, *next;
  75   ir_node *c = NULL;
  76
  77   if (is_Bad(irn))
  78     return;
  79
  80   for (edge = get_irn_out_edge_first(irn); edge; edge = next) {
  81     ir_node *succ = get_edge_src_irn(edge);
  82     int     pos   = get_edge_src_pos(edge);
  83     ir_node *blk  = get_effective_use_block(succ, pos);
  84
  85     next = get_irn_out_edge_next(irn, edge);
  86
  87     if (block_dominates(block, blk)) {
  88       /*
  89        * Ok, we found a user of irn that is placed
  90        * in a block dominated by the branch block.
  91        * We can replace the input with the Constant
  92        * branch label.
  93        */
  94
  95       if (! c) {
  96         ir_mode *mode = get_irn_mode(irn);
  97         ir_type *tp   = get_irn_type(irn);
  98         tarval *tv    = new_tarval_from_long(nr, mode);
  99         c = new_r_Const_type(current_ir_graph, block, mode, tv, tp);
 100       }
 101
 102       set_irn_n(succ, pos, c);
 103       DBG_OPT_CONFIRM_C(irn, c);
 104 //      ir_printf("1 Replacing input %d of node %n with %n\n", pos, succ, c);
 105
 106       env->num_consts += 1;
 107     }
 108   }
 109 }  /* handle_case */
 110
 111 /**
 112  * Handle an IF-branch.
 113  *
 114  * @param block   the block which is entered by the branch
 115  * @param cmp     the Cmp node expressing the branch condition
 116  * @param pnc     the Compare relation for taking this branch
 117  * @param env     statistical environment
 118  */
 119 static void handle_if(ir_node *block, ir_node *cmp, pn_Cmp pnc, env_t *env)
 120 {
 121   ir_node *left  = get_Cmp_left(cmp);
 122   ir_node *right = get_Cmp_right(cmp);
 123   ir_op *op;
 124   const ir_edge_t *edge, *next;
 125
 126   /* Beware of Bads */
 127   if (is_Bad(left) ||is_Bad(right))
 128     return;
 129
 130   op = get_irn_op(left);
 131
 132   /* Do not create Confirm nodes for Cmp(Const, Const) constructs.
 133      These are removed anyway */
 134   if (op == op_Const && is_Const(right))
 135     return;
 136
 137   /* try to place the constant on the right side for a Confirm */
 138   if (op == op_Const || op == op_SymConst) {
 139     ir_node *t = left;
 140
 141     left  = right;
 142     right = t;
 143
 144     pnc = get_inversed_pnc(pnc);
 145   }
 146
 147   /*
 148    * First case: both values are identical.
 149    * replace the left one by the right (potentially const) one.
 150    */
 151   if (pnc == pn_Cmp_Eq) {
 152     for (edge = get_irn_out_edge_first(left); edge; edge = next) {
 153       ir_node *succ = get_edge_src_irn(edge);
 154       int     pos   = get_edge_src_pos(edge);
 155       ir_node *blk  = get_effective_use_block(succ, pos);
 156
 157       next = get_irn_out_edge_next(left, edge);
 158       if (block_dominates(block, blk)) {
 159         /*
 160          * Ok, we found a usage of left in a block
 161          * dominated by the branch block.
 162          * We can replace the input with right.
 163          */
 164         set_irn_n(succ, pos, right);
 165         DBG_OPT_CONFIRM(left, right);
 166
 167 //        ir_printf("2 Replacing input %d of node %n with %n\n", pos, succ, right);
 168
 169         env->num_eq += 1;
 170       }
 171     }
 172   }
 173   else { /* not pn_Cmp_Eq cases */
 174     ir_node *c = NULL;
 175
 176     for (edge = get_irn_out_edge_first(left); edge; edge = next) {
 177       ir_node *succ = get_edge_src_irn(edge);
 178       int     pos   = get_edge_src_pos(edge);
 179       ir_node *blk  = get_effective_use_block(succ, pos);
 180
 181       next = get_irn_out_edge_next(left, edge);
 182       if (block_dominates(block, blk)) {
 183         /*
 184          * Ok, we found a usage of left in a block
 185          * dominated by the branch block.
 186          * We can replace the input with a Confirm(left, pnc, right).
 187          */
 188         if (! c)
 189           c = new_r_Confirm(current_ir_graph, block, left, right, pnc);
 190
 191         pos = get_edge_src_pos(edge);
 192         set_irn_n(succ, pos, c);
 193 //        ir_printf("3 Replacing input %d of node %n with %n\n", pos, succ, c);
 194
 195         env->num_confirms += 1;
 196       }
 197     }
 198   }
 199 }  /* handle_if */
 200
 201 /**
 202  * Pre-walker: Called for every block to insert Confirm nodes
 203  */
 204 static void insert_Confirm(ir_node *block, void *env)
 205 {
 206   ir_node *cond, *proj, *selector;
 207   ir_mode *mode;
 208
 209   /*
 210    * we can only handle blocks with only ONE control flow
 211    * predecessor yet.
 212    */
 213   if (get_Block_n_cfgpreds(block) != 1)
 214     return;
 215
 216   proj = get_Block_cfgpred(block, 0);
 217   if (get_irn_op(proj) != op_Proj)
 218     return;
 219
 220   cond = get_Proj_pred(proj);
 221   if (get_irn_op(cond) != op_Cond)
 222     return;
 223
 224   selector = get_Cond_selector(cond);
 225   mode = get_irn_mode(selector);
 226
 227   if (mode == mode_b) {
 228     ir_node *cmp;
 229     pn_Cmp pnc;
 230
 231     /* this should be an IF, check this */
 232     if (get_irn_op(selector) != op_Proj)
 233       return;
 234
 235     cmp = get_Proj_pred(selector);
 236     if (get_irn_op(cmp) != op_Cmp)
 237       return;
 238
 239     pnc = get_Proj_proj(selector);
 240
 241     if (get_Proj_proj(proj) != pn_Cond_true) {
 242       /* it's the false branch */
 243       pnc = get_negated_pnc(pnc, mode);
 244     }
 245 //    ir_printf("At %n using %n Confirm %=\n", block, cmp, pnc);
 246
 247     handle_if(block, cmp, pnc, env);
 248   }
 249   else if (mode_is_int(mode)) {
 250     long proj_nr = get_Proj_proj(proj);
 251
 252     /* this is a CASE, but we cannot handle the default case */
 253     if (proj_nr == get_Cond_defaultProj(cond))
 254       return;
 255
 256     handle_case(block, get_Cond_selector(cond), proj_nr, env);
 257   }
 258 }  /* insert_Confirm */
 259
 260 /*
 261  * Construct Confirm nodes
 262  */
 263 void construct_confirms(ir_graph *irg)
 264 {
 265   env_t env;
 266   int edges_active = edges_activated(irg);
 267
 268   /* we need dominance info */
 269   assure_doms(irg);
 270
 271   assert(get_irg_pinned(irg) == op_pin_state_pinned &&
 272     "Nodes must be placed to insert Confirms");
 273
 274   if (! edges_active) {
 275     /* We need edges */
 276     edges_activate(irg);
 277   }
 278
 279   env.num_confirms = 0;
 280   env.num_consts   = 0;
 281   env.num_eq       = 0;
 282
 283   /* now, visit all blocks and add Confirms where possible */
 284   irg_block_walk_graph(irg, insert_Confirm, NULL, &env);
 285
 286   if (env.num_confirms | env.num_consts | env.num_eq) {
 287     /* we have add nodes or changed DF edges */
 288     set_irg_outs_inconsistent(irg);
 289
 290     /* the new nodes are not in the loop info */
 291     set_irg_loopinfo_inconsistent(irg);
 292   }
 293
 294 #if 0
 295   printf("# Confirms inserted : %u\n", env.num_confirms);
 296   printf("# Const replacements: %u\n", env.num_consts);
 297   printf("# node equalities   : %u\n", env.num_eq);
 298 #endif
 299
 300   /* deactivate edges if they where off */
 301   if (! edges_active)
 302     edges_deactivate(irg);
 303 }  /* construct_confirms */
 304
 305 /**
 306  * Post-walker: Remove Confirm nodes
 307  */
 308 static void rem_Confirm(ir_node *n, void *env) {
 309   if (get_irn_op(n) == op_Confirm) {
 310     ir_node *value = get_Confirm_value(n);
 311     if (value != n)
 312       exchange(n, value);
 313     else {
 314       /*
 315        * Strange: a Confirm is it's own bound. This can happen
 316        * in dead blocks when Phi nodes are already removed.
 317        */
 318       exchange(n, new_Bad());
 319     }
 320   }
 321 }  /* rem_Confirm */
 322
 323 /*
 324  * Remove all Confirm nodes from a graph.
 325  */
 326 void remove_confirms(ir_graph *irg) {
 327   irg_walk_graph(irg, NULL, rem_Confirm, NULL);
 328 }  /* remove_confirms */