nsz Git - libfirm/blob - ir/opt/convopt.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
  22  * @brief   conv node optimisation
  23  * @author  Matthias Braun, Christoph Mallon
  24  * @version $Id$
  25  *
  26  * Try to minimize the number of conv nodes by changing modes of operations.
  27  * The typical example is the following structure:
  28  *    (some node mode_Hs)
  29  *            |                                       (some node_Hs)
  30  *         Conv Is                                          |
  31  *            |                                          Add Hs
  32  *          Add Is            gets transformed to           |
  33  *            |
  34  *         Conv Hs
  35  *
  36  * TODO: * try to optimize cmp modes
  37  *       * decide when it is useful to move the convs through phis
  38  */
  39 #ifdef HAVE_CONFIG_H
  40 #include "config.h"
  41 #endif
  42
  43 #include "iroptimize.h"
  44
  45 #include <assert.h>
  46 #include "debug.h"
  47 #include "ircons.h"
  48 #include "irgmod.h"
  49 #include "irgopt.h"
  50 #include "irnode_t.h"
  51 #include "iredges_t.h"
  52 #include "irgwalk.h"
  53 #include "irprintf.h"
  54
  55 DEBUG_ONLY(static firm_dbg_module_t *dbg);
  56
  57 static
  58 int is_optimizable_node(const ir_node *node)
  59 {
  60         return
  61                 is_And(node) ||
  62                 is_Or(node)  ||
  63                 is_Eor(node) ||
  64                 is_Add(node) ||
  65                 is_Sub(node) ||
  66                 is_Mul(node) ||
  67                 is_Phi(node);
  68 }
  69
  70 static tarval* conv_const_tv(const ir_node* cnst, ir_mode* dest_mode)
  71 {
  72         return tarval_convert_to(get_Const_tarval(cnst), dest_mode);
  73 }
  74
  75 static
  76 int get_conv_costs(const ir_node *node, ir_mode *dest_mode)
  77 {
  78         ir_mode *mode = get_irn_mode(node);
  79         size_t arity;
  80         size_t i;
  81         int costs;
  82
  83         if (mode == dest_mode)
  84                 return 0;
  85
  86         if (is_Const(node)) {
  87                 /* TODO tarval module is incomplete and can't convert floats to ints */
  88                 return conv_const_tv(node, dest_mode) == tarval_bad ? 1 : 0;
  89         }
  90
  91         if (get_irn_n_edges(node) > 1) {
  92                 DB((dbg, LEVEL_3, "multi outs at %+F\n", node));
  93                 return 1;
  94         }
  95
  96         if (is_Conv(node)) {
  97                 return get_conv_costs(get_Conv_op(node), dest_mode) - 1;
  98         }
  99
 100         if (!is_optimizable_node(node)) {
 101                 return 1;
 102         }
 103
 104         costs = 0;
 105         arity = get_irn_arity(node);
 106         for (i = 0; i < arity; ++i) {
 107                 ir_node *pred = get_irn_n(node, i);
 108                 costs += get_conv_costs(pred, dest_mode);
 109         }
 110
 111         return costs;
 112 }
 113
 114 static ir_node *place_conv(ir_node *node, ir_mode *dest_mode)
 115 {
 116         ir_node *block = get_nodes_block(node);
 117         ir_node *conv = new_r_Conv(current_ir_graph, block, node, dest_mode);
 118         return conv;
 119 }
 120
 121 static
 122 ir_node *conv_transform(ir_node *node, ir_mode *dest_mode)
 123 {
 124         size_t arity;
 125         size_t i;
 126
 127         if (get_irn_mode(node) == dest_mode)
 128                 return node;
 129
 130         if (is_Const(node)) {
 131                 /* TODO tarval module is incomplete and can't convert floats to ints */
 132                 tarval *tv = conv_const_tv(node, dest_mode);
 133                 if (tv == tarval_bad) {
 134                         return place_conv(node, dest_mode);
 135                 } else {
 136                         return new_Const(dest_mode, tv);
 137                 }
 138         }
 139
 140         if (get_irn_n_edges(node) > 1) {
 141                 return place_conv(node, dest_mode);
 142         }
 143
 144         if (is_Conv(node)) {
 145                 return conv_transform(get_Conv_op(node), dest_mode);
 146         }
 147
 148         if (!is_optimizable_node(node)) {
 149                 return place_conv(node, dest_mode);
 150         }
 151
 152         arity = get_irn_arity(node);
 153         for (i = 0; i < arity; i++) {
 154                 ir_node *pred = get_irn_n(node, i);
 155                 ir_node *transformed = conv_transform(pred, dest_mode);
 156                 set_irn_n(node, i, transformed);
 157         }
 158         set_irn_mode(node, dest_mode);
 159         return node;
 160 }
 161
 162 static
 163 int is_downconv(ir_mode *src_mode, ir_mode *dest_mode)
 164 {
 165         return
 166                 mode_is_int(src_mode) &&
 167                 mode_is_int(dest_mode) &&
 168                 get_mode_size_bits(dest_mode) < get_mode_size_bits(src_mode);
 169 }
 170
 171 /* TODO, backends (at least ia23) can't handle it at the moment,
 172    and it's probably not more efficient on most archs */
 173 #if 0
 174 static
 175 void try_optimize_cmp(ir_node *node)
 176 {
 177         ir_node *left  = get_Cmp_left(node);
 178         ir_node *right = get_Cmp_right(node);
 179         ir_node *conv  = NULL;
 180
 181         if(is_downconv
 182 }
 183 #endif
 184
 185 static char changed;
 186
 187 static
 188 void conv_opt_walker(ir_node *node, void *data)
 189 {
 190         ir_node *transformed;
 191         ir_node *pred;
 192         ir_mode *pred_mode;
 193         ir_mode *mode;
 194         int costs;
 195         (void) data;
 196
 197 #if 0
 198         if(is_Cmp(node)) {
 199                 try_optimize_cmp(node);
 200                 return;
 201         }
 202 #endif
 203
 204         if (!is_Conv(node))
 205                 return;
 206
 207         pred      = get_Conv_op(node);
 208         mode      = get_irn_mode(node);
 209         pred_mode = get_irn_mode(pred);
 210
 211         if (!is_Phi(pred) && !is_downconv(pred_mode, mode))
 212                 return;
 213
 214         /* - 1 for the initial conv */
 215         costs = get_conv_costs(pred, mode) - 1;
 216         DB((dbg, LEVEL_2, "Costs for %+F -> %+F: %d\n", node, pred, costs));
 217         if (costs >= 0) return;
 218
 219         transformed = conv_transform(pred, mode);
 220         exchange(node, transformed);
 221         changed = 1;
 222 }
 223
 224 void conv_opt(ir_graph *irg)
 225 {
 226         char invalidate = 0;
 227         FIRM_DBG_REGISTER(dbg, "firm.opt.conv");
 228
 229         DB((dbg, LEVEL_1, "===> Performing conversion optimization on %+F\n", irg));
 230
 231         edges_assure(irg);
 232         do {
 233                 changed = 0;
 234                 irg_walk_graph(irg, NULL, conv_opt_walker, NULL);
 235                 local_optimize_graph(irg);
 236                 invalidate |= changed;
 237         } while (changed);
 238
 239         if (invalidate) {
 240                 set_irg_outs_inconsistent(irg);
 241         }
 242 }