nsz Git - libfirm/blob - ir/opt/convopt.c

   1 /*
   2  * Copyright (C) 1995-2011 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  *
  25  * Try to minimize the number of conv nodes by changing modes of operations.
  26  * The typical example is the following structure:
  27  *    (some node mode_Hs)
  28  *            |                                       (some node_Hs)
  29  *         Conv Is                                          |
  30  *            |                                          Add Hs
  31  *          Add Is            gets transformed to           |
  32  *            |
  33  *         Conv Hs
  34  *
  35  * TODO: * try to optimize cmp modes
  36  *       * decide when it is useful to move the convs through phis
  37  */
  38 #include "config.h"
  39
  40 #include "iroptimize.h"
  41
  42 #include <assert.h>
  43 #include <stdbool.h>
  44 #include "debug.h"
  45 #include "ircons.h"
  46 #include "irgmod.h"
  47 #include "irgopt.h"
  48 #include "irnode_t.h"
  49 #include "iropt_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, ir_mode *dest_mode)
  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_Sub:
  73                 return true;
  74         case iro_Shl: {
  75                 int modulo_shift = get_mode_modulo_shift(dest_mode);
  76                 int old_shift    = get_mode_modulo_shift(get_irn_mode(node));
  77                 /* bail out if modulo shift changes */
  78                 if (modulo_shift != old_shift)
  79                         return false;
  80                 return true;
  81         }
  82
  83         default:
  84                 return false;
  85         }
  86 }
  87
  88 static ir_tarval* conv_const_tv(const ir_node* cnst, ir_mode* dest_mode)
  89 {
  90         return tarval_convert_to(get_Const_tarval(cnst), dest_mode);
  91 }
  92
  93 static int is_downconv(ir_mode *src_mode, ir_mode *dest_mode)
  94 {
  95         return
  96                 mode_is_int(src_mode) &&
  97                 mode_is_int(dest_mode) &&
  98                 get_mode_size_bits(dest_mode) <= get_mode_size_bits(src_mode);
  99 }
 100
 101 static int get_conv_costs(const ir_node *node, ir_mode *dest_mode)
 102 {
 103         ir_mode *mode = get_irn_mode(node);
 104         int arity;
 105         int i;
 106         int costs;
 107
 108         if (mode == dest_mode)
 109                 return 0;
 110
 111         if (is_Const(node)) {
 112                 /* TODO tarval module is incomplete and can't convert floats to ints */
 113                 return conv_const_tv(node, dest_mode) == tarval_bad ? 1 : 0;
 114         }
 115
 116         if (is_Conv(node) &&
 117                         is_downconv(mode, dest_mode) &&
 118                         get_irn_mode(get_Conv_op(node)) == dest_mode) {
 119                 return -1;
 120         }
 121
 122         if (get_irn_n_edges(node) > 1) {
 123                 DB((dbg, LEVEL_3, "multi outs at %+F\n", node));
 124                 return 1;
 125         }
 126
 127         if (ir_zero_when_converted(node, dest_mode)) {
 128                 return -1;
 129         }
 130
 131 #if 0 // TODO
 132         /* Take the minimum of the conversion costs for Phi predecessors as only one
 133          * branch is actually executed at a time */
 134         if (is_Phi(node)) {
 135                 int i;
 136                 int arity = get_Phi_n_preds(node);
 137                 int costs;
 138
 139                 costs = get_conv_costs(get_Phi_pred(node, 0), dest_mode);
 140                 for (i = 1; i < arity; ++i) {
 141                         ir_node *pred = get_Phi_pred(node, i);
 142                         int c = get_conv_costs(pred, dest_mode);
 143                         if (c < costs) costs = c;
 144                 }
 145
 146                 return costs;
 147         }
 148 #endif
 149
 150         if (!is_downconv(mode, dest_mode)) {
 151                 return 1;
 152         }
 153
 154         if (is_Conv(node)) {
 155                 ir_node *pred      = get_Conv_op(node);
 156                 ir_mode *pred_mode = get_irn_mode(pred);
 157
 158                 if (!values_in_mode(dest_mode, pred_mode)) {
 159                         return 1;
 160                 }
 161                 return get_conv_costs(get_Conv_op(node), dest_mode) - 1;
 162         }
 163
 164         if (!is_optimizable_node(node, dest_mode)) {
 165                 return 1;
 166         }
 167
 168         costs = 0;
 169         // The shift count does not participate in the conv optimisation
 170         arity = is_Shl(node) ? 1 : get_irn_arity(node);
 171         for (i = 0; i < arity; ++i) {
 172                 ir_node *pred = get_irn_n(node, i);
 173                 costs += imin(get_conv_costs(pred, dest_mode), 1);
 174         }
 175
 176         return costs;
 177 }
 178
 179 static ir_node *place_conv(ir_node *node, ir_mode *dest_mode)
 180 {
 181         ir_node *block = get_nodes_block(node);
 182         ir_node *conv = new_r_Conv(block, node, dest_mode);
 183         return conv;
 184 }
 185
 186 static ir_node *conv_transform(ir_node *node, ir_mode *dest_mode)
 187 {
 188         ir_mode  *mode = get_irn_mode(node);
 189         ir_graph *irg  = get_irn_irg(node);
 190         int       arity;
 191         int       conv_arity;
 192         int       i;
 193         ir_node  *new_node;
 194         ir_node **ins;
 195
 196         if (mode == dest_mode)
 197                 return node;
 198
 199         if (is_Const(node)) {
 200                 /* TODO tarval module is incomplete and can't convert floats to ints */
 201                 ir_tarval *tv = conv_const_tv(node, dest_mode);
 202                 if (tv == tarval_bad) {
 203                         return place_conv(node, dest_mode);
 204                 } else {
 205                         return new_r_Const(irg, tv);
 206                 }
 207         }
 208
 209         if (is_Conv(node) &&
 210                         is_downconv(mode, dest_mode) &&
 211                         get_irn_mode(get_Conv_op(node)) == dest_mode) {
 212                 return get_Conv_op(node);
 213         }
 214
 215         if (get_irn_n_edges(node) > 1) {
 216                 return place_conv(node, dest_mode);
 217         }
 218
 219         if (!is_downconv(mode, dest_mode)) {
 220                 return place_conv(node, dest_mode);
 221         }
 222
 223         if (is_Conv(node)) {
 224                 ir_node *pred      = get_Conv_op(node);
 225                 ir_mode *pred_mode = get_irn_mode(pred);
 226
 227                 if (!values_in_mode(dest_mode, pred_mode)) {
 228                         return place_conv(node, dest_mode);
 229                 }
 230                 return conv_transform(get_Conv_op(node), dest_mode);
 231         }
 232
 233         if (!is_optimizable_node(node, dest_mode)) {
 234                 return place_conv(node, dest_mode);
 235         }
 236
 237         // We want to create a new node with the right mode
 238         arity = get_irn_arity(node);
 239         ins = ALLOCAN(ir_node *, arity);
 240
 241         // The shift count does not participate in the conv optimisation
 242         conv_arity = is_Shl(node) ? 1 : arity;
 243         for (i = 0; i < conv_arity; i++) {
 244                 ir_node *pred = get_irn_n(node, i);
 245                 ir_node *transformed;
 246                 if (get_conv_costs(pred, dest_mode) > 0) {
 247                         transformed = place_conv(pred, dest_mode);
 248                 } else {
 249                         transformed = conv_transform(pred, dest_mode);
 250                 }
 251                 ins[i] = transformed;
 252         }
 253
 254         for (i = conv_arity; i < arity; i++) {
 255                 ins[i] = get_irn_n(node, i);
 256         }
 257
 258         new_node = new_ir_node(get_irn_dbg_info(node),
 259                                 irg,
 260                                 get_nodes_block(node),
 261                                 get_irn_op(node),
 262                                 dest_mode,
 263                                 arity,
 264                                 ins);
 265         copy_node_attr(irg, node, new_node);
 266
 267         return new_node;
 268 }
 269
 270 static void conv_opt_walker(ir_node *node, void *data)
 271 {
 272         ir_node *transformed;
 273         ir_node *pred;
 274         ir_mode *pred_mode;
 275         ir_mode *mode;
 276         int costs;
 277         bool *changed = (bool*)data;
 278
 279         if (!is_Conv(node))
 280                 return;
 281
 282         pred      = get_Conv_op(node);
 283         mode      = get_irn_mode(node);
 284         pred_mode = get_irn_mode(pred);
 285
 286         if (mode_is_reference(mode) || mode_is_reference(pred_mode))
 287                 return;
 288
 289         if (!is_Phi(pred) && !is_downconv(pred_mode, mode))
 290                 return;
 291
 292         /* - 1 for the initial conv */
 293         costs = get_conv_costs(pred, mode) - 1;
 294         DB((dbg, LEVEL_2, "Costs for %+F -> %+F: %d\n", node, pred, costs));
 295         if (costs > 0)
 296                 return;
 297
 298         transformed = conv_transform(pred, mode);
 299         if (node != transformed) {
 300                 exchange(node, transformed);
 301                 *changed = true;
 302         }
 303 }
 304
 305 void conv_opt(ir_graph *irg)
 306 {
 307         bool global_changed = false;
 308         bool changed;
 309         FIRM_DBG_REGISTER(dbg, "firm.opt.conv");
 310
 311         assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES);
 312
 313         DB((dbg, LEVEL_1, "===> Performing conversion optimization on %+F\n", irg));
 314
 315         do {
 316                 changed = false;
 317                 irg_walk_graph(irg, NULL, conv_opt_walker, &changed);
 318                 local_optimize_graph(irg);
 319                 global_changed |= changed;
 320         } while (changed);
 321
 322         confirm_irg_properties(irg,
 323                 global_changed ? IR_GRAPH_PROPERTIES_NONE : IR_GRAPH_PROPERTIES_ALL);
 324 }
 325
 326 /* Creates an ir_graph pass for conv_opt. */
 327 ir_graph_pass_t *conv_opt_pass(const char *name)
 328 {
 329         ir_graph_pass_t *path = def_graph_pass(name ? name : "conv_opt", conv_opt);
 330
 331         /* safe to run parallel on all irgs */
 332         ir_graph_pass_set_parallel(path, 1);
 333
 334         return path;
 335 }