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

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