nsz Git - libfirm/blob - ir/opt/convopt.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   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 #include "config.h"
  40
  41 #include "iroptimize.h"
  42
  43 #include <assert.h>
  44 #include <stdbool.h>
  45 #include "debug.h"
  46 #include "ircons.h"
  47 #include "irgmod.h"
  48 #include "irgopt.h"
  49 #include "irnode_t.h"
  50 #include "iredges_t.h"
  51 #include "irgwalk.h"
  52 #include "irprintf.h"
  53 #include "irpass_t.h"
  54 #include "tv.h"
  55 #include "vrp.h"
  56
  57 DEBUG_ONLY(static firm_dbg_module_t *dbg);
  58
  59 static inline int imin(int a, int b) { return a < b ? a : b; }
  60
  61 static bool is_optimizable_node(const ir_node *node)
  62 {
  63         switch (get_irn_opcode(node)) {
  64         case iro_Add:
  65         case iro_And:
  66         case iro_Eor:
  67         case iro_Minus:
  68         case iro_Mul:
  69         case iro_Not:
  70         case iro_Or:
  71         case iro_Phi:
  72         case iro_Shl:
  73         case iro_Sub:
  74                 return true;
  75         default:
  76                 return false;
  77         }
  78 }
  79
  80 static tarval* conv_const_tv(const ir_node* cnst, ir_mode* dest_mode)
  81 {
  82         return tarval_convert_to(get_Const_tarval(cnst), dest_mode);
  83 }
  84
  85 static int is_downconv(ir_mode *src_mode, ir_mode *dest_mode)
  86 {
  87         return
  88                 mode_is_int(src_mode) &&
  89                 mode_is_int(dest_mode) &&
  90                 get_mode_size_bits(dest_mode) <= get_mode_size_bits(src_mode);
  91 }
  92
  93 static int get_conv_costs(const ir_node *node, ir_mode *dest_mode)
  94 {
  95         ir_mode *mode = get_irn_mode(node);
  96         size_t arity;
  97         size_t i;
  98         int costs;
  99
 100         if (mode == dest_mode)
 101                 return 0;
 102
 103         if (is_Const(node)) {
 104                 /* TODO tarval module is incomplete and can't convert floats to ints */
 105                 return conv_const_tv(node, dest_mode) == tarval_bad ? 1 : 0;
 106         }
 107
 108         if (is_Conv(node) &&
 109                         is_downconv(mode, dest_mode) &&
 110                         get_irn_mode(get_Conv_op(node)) == dest_mode) {
 111                 return -1;
 112         }
 113
 114         if (get_irn_n_edges(node) > 1) {
 115                 DB((dbg, LEVEL_3, "multi outs at %+F\n", node));
 116                 return 1;
 117         }
 118
 119 #if 0 // TODO
 120         /* Take the minimum of the conversion costs for Phi predecessors as only one
 121          * branch is actually executed at a time */
 122         if (is_Phi(node)) {
 123                 size_t i;
 124                 size_t arity = get_Phi_n_preds(node);
 125                 int costs;
 126
 127                 costs = get_conv_costs(get_Phi_pred(node, 0), dest_mode);
 128                 for (i = 1; i < arity; ++i) {
 129                         ir_node *pred = get_Phi_pred(node, i);
 130                         int c = get_conv_costs(pred, dest_mode);
 131                         if (c < costs) costs = c;
 132                 }
 133
 134                 return costs;
 135         }
 136 #endif
 137
 138         if (!is_downconv(mode, dest_mode)) {
 139                 return 1;
 140         }
 141
 142         if (is_Conv(node)) {
 143                 ir_node *pred      = get_Conv_op(node);
 144                 ir_mode *pred_mode = get_irn_mode(pred);
 145
 146                 if (!values_in_mode(dest_mode, pred_mode)) {
 147                         return 1;
 148                 }
 149                 return get_conv_costs(get_Conv_op(node), dest_mode) - 1;
 150         }
 151
 152         if (!is_optimizable_node(node)) {
 153                 return 1;
 154         }
 155
 156         costs = 0;
 157         // The shift count does not participate in the conv optimisation
 158         arity = is_Shl(node) ? 1 : get_irn_arity(node);
 159         for (i = 0; i < arity; ++i) {
 160                 ir_node *pred = get_irn_n(node, i);
 161                 costs += imin(get_conv_costs(pred, dest_mode), 1);
 162         }
 163
 164         return costs;
 165 }
 166
 167 static ir_node *place_conv(ir_node *node, ir_mode *dest_mode)
 168 {
 169         ir_node *block = get_nodes_block(node);
 170         ir_node *conv = new_r_Conv(block, node, dest_mode);
 171         return conv;
 172 }
 173
 174 static ir_node *conv_transform(ir_node *node, ir_mode *dest_mode)
 175 {
 176         ir_mode  *mode = get_irn_mode(node);
 177         size_t    arity;
 178         size_t    i;
 179         ir_node  *new_node;
 180         ir_graph *irg = get_irn_irg(node);
 181
 182         if (mode == dest_mode)
 183                 return node;
 184
 185         if (is_Const(node)) {
 186                 /* TODO tarval module is incomplete and can't convert floats to ints */
 187                 tarval *tv = conv_const_tv(node, dest_mode);
 188                 if (tv == tarval_bad) {
 189                         return place_conv(node, dest_mode);
 190                 } else {
 191                         return new_Const(tv);
 192                 }
 193         }
 194
 195         if (is_Conv(node) &&
 196                         is_downconv(mode, dest_mode) &&
 197                         get_irn_mode(get_Conv_op(node)) == dest_mode) {
 198                 return get_Conv_op(node);
 199         }
 200
 201         if (get_irn_n_edges(node) > 1) {
 202                 return place_conv(node, dest_mode);
 203         }
 204
 205         if (!is_downconv(mode, dest_mode)) {
 206                 return place_conv(node, dest_mode);
 207         }
 208
 209         if (is_Conv(node)) {
 210                 ir_node *pred      = get_Conv_op(node);
 211                 ir_mode *pred_mode = get_irn_mode(pred);
 212
 213                 if (!values_in_mode(dest_mode, pred_mode)) {
 214                         return place_conv(node, dest_mode);
 215                 }
 216                 return conv_transform(get_Conv_op(node), dest_mode);
 217         }
 218
 219         if (!is_optimizable_node(node)) {
 220                 return place_conv(node, dest_mode);
 221         }
 222
 223         // Create a new node with the right mode
 224         new_node = new_ir_node(get_irn_dbg_info(node),
 225                                 irg,
 226                                 get_nodes_block(node),
 227                                 get_irn_op(node),
 228                                 dest_mode,
 229                                 get_irn_arity(node),
 230                                 get_irn_in(node) + 1);
 231         copy_node_attr(irg, node, new_node);
 232
 233         // The shift count does not participate in the conv optimisation
 234         arity = is_Shl(new_node) ? 1 : get_irn_arity(new_node);
 235         for (i = 0; i < arity; i++) {
 236                 ir_node *pred = get_irn_n(new_node, i);
 237                 ir_node *transformed;
 238                 if (get_conv_costs(pred, dest_mode) > 0) {
 239                         transformed = place_conv(pred, dest_mode);
 240                 } else {
 241                         transformed = conv_transform(pred, dest_mode);
 242                 }
 243                 set_irn_n(new_node, i, transformed);
 244         }
 245
 246         return new_node;
 247 }
 248
 249 /* TODO, backends (at least ia32) can't handle it at the moment,
 250    and it's probably not more efficient on most archs */
 251 #if 0
 252 static void try_optimize_cmp(ir_node *node)
 253 {
 254         ir_node *left  = get_Cmp_left(node);
 255         ir_node *right = get_Cmp_right(node);
 256         ir_node *conv  = NULL;
 257
 258         if (is_downconv
 259 }
 260 #endif
 261
 262 static void conv_opt_walker(ir_node *node, void *data)
 263 {
 264         ir_node *transformed;
 265         ir_node *pred;
 266         ir_mode *pred_mode;
 267         ir_mode *mode;
 268         int costs;
 269         bool *changed = data;
 270
 271 #if 0
 272         if (is_Cmp(node)) {
 273                 try_optimize_cmp(node);
 274                 return;
 275         }
 276 #endif
 277
 278         if (!is_Conv(node))
 279                 return;
 280
 281         pred      = get_Conv_op(node);
 282         mode      = get_irn_mode(node);
 283         pred_mode = get_irn_mode(pred);
 284
 285         if (mode_is_reference(mode) || mode_is_reference(pred_mode))
 286                 return;
 287
 288         if (!is_Phi(pred) && !is_downconv(pred_mode, mode))
 289                 return;
 290
 291         /* - 1 for the initial conv */
 292         costs = get_conv_costs(pred, mode) - 1;
 293         DB((dbg, LEVEL_2, "Costs for %+F -> %+F: %d\n", node, pred, costs));
 294         if (costs > 0)
 295                 return;
 296
 297         transformed = conv_transform(pred, mode);
 298         if (node != transformed) {
 299                 vrp_attr *vrp;
 300
 301                 exchange(node, transformed);
 302                 vrp = vrp_get_info(transformed);
 303                 if (vrp && vrp->valid) {
 304                         vrp->range_type = VRP_VARYING;
 305                         vrp->bits_set = tarval_convert_to(vrp->bits_set, mode);
 306                         vrp->bits_not_set = tarval_convert_to(vrp->bits_not_set, mode);
 307                 }
 308
 309                 *changed = true;
 310         }
 311 }
 312
 313 int conv_opt(ir_graph *irg)
 314 {
 315         bool changed;
 316         bool invalidate = false;
 317         FIRM_DBG_REGISTER(dbg, "firm.opt.conv");
 318
 319         DB((dbg, LEVEL_1, "===> Performing conversion optimization on %+F\n", irg));
 320
 321         edges_assure(irg);
 322         do {
 323                 changed = false;
 324                 irg_walk_graph(irg, NULL, conv_opt_walker, &changed);
 325                 local_optimize_graph(irg);
 326                 invalidate |= changed;
 327         } while (changed);
 328
 329         if (invalidate) {
 330                 set_irg_outs_inconsistent(irg);
 331         }
 332         return invalidate;
 333 }
 334
 335 /* Creates an ir_graph pass for conv_opt. */
 336 ir_graph_pass_t *conv_opt_pass(const char *name)
 337 {
 338         ir_graph_pass_t *path = def_graph_pass_ret(name ? name : "conv_opt", conv_opt);
 339
 340         /* safe to run parallel on all irgs */
 341         ir_graph_pass_set_parallel(path, 1);
 342
 343         return path;
 344 }