nsz Git - libfirm/blob - ir/lower/lower_copyb.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   Lower small CopyB nodes into a series of Load/Store nodes
  23  * @author  Michael Beck, Matthias Braun, Manuel Mohr
  24  * @version $Id$
  25  */
  26 #include "config.h"
  27
  28 #include "adt/list.h"
  29 #include "ircons.h"
  30 #include "lowering.h"
  31 #include "irprog_t.h"
  32 #include "irgwalk.h"
  33 #include "irnode_t.h"
  34 #include "type_t.h"
  35 #include "irtools.h"
  36 #include "irgmod.h"
  37 #include "error.h"
  38 #include "be.h"
  39
  40 typedef struct entry entry_t;
  41 struct entry {
  42         struct list_head list;
  43         ir_node *copyb;
  44 };
  45
  46 /**
  47  * Every CopyB is assigned a size category as follows:
  48  *  - 'small'  iff                  size <= max_small_size,
  49  *  - 'medium' iff max_small_size < size <  min_large_size,
  50  *  - 'large'  iff                  size >= min_large_size.
  51  *
  52  * The idea is that each backend can apply different optimizations in each
  53  * of the three categories.
  54  *
  55  * For small CopyBs, the x86 backend could, e.g., emit a single SSE
  56  * instruction to copy 16 bytes.  Other backends might just go with a series
  57  * of Load/Stores.  Therefore, x86 would like to keep the small CopyB nodes
  58  * around whereas other backends would not.
  59  * For medium-sized CopyBs, the x86 backend might generate a rep-prefixed mov
  60  * instruction.  Hence, it also wants to keep the CopyBs in these cases.  Other
  61  * backends might handle this differently.
  62  * For large CopyBs, a call to memcpy is worth the call overhead, so large
  63  * CopyBs should always be lowered to memcpy calls.
  64  *
  65  * The lowerer performs the following actions if the CopyB is
  66  * - 'small':  Replace it with a series of Loads/Stores
  67  * - 'medium': Nothing.
  68  * - 'large':  Replace it with a call to memcpy.
  69  *
  70  * max_small_size and min_large_size allow for a flexible configuration.
  71  * For example, one backend could specify max_small_size == 0 and
  72  * min_large_size == 8192 to keep all CopyB nodes smaller than 8192 and get
  73  * memcpy Calls for all others.  Here, the set of small CopyBs is empty.
  74  * Another backend could specify max_small_size == 63 and min_large_size == 64
  75  * to lower all small CopyBs to Loads/Stores and all big CopyBs to memcpy.
  76  * Hence, the set of medium-sized CopyBs is empty and this backend never
  77  * sees a CopyB node at all.
  78  * If memcpy is not available, min_large_size can be set to UINT_MAX to prevent
  79  * the creation of calls to memcpy.  Note that CopyBs whose size is UINT_MAX
  80  * will still be lowered to memcpy calls because we check if the size is greater
  81  * *or equal* to min_large_size.  However, this should never occur in practice.
  82  */
  83
  84 static unsigned max_small_size; /**< The maximum size of a CopyB node
  85                                      so that it is regarded as 'small'. */
  86 static unsigned min_large_size; /**< The minimum size of a CopyB node
  87                                      so that it is regarded as 'large'. */
  88 static unsigned native_mode_bytes; /**< The size of the native mode in bytes. */
  89
  90 typedef struct walk_env {
  91         struct obstack   obst;           /**< the obstack where data is allocated
  92                                               on. */
  93         struct list_head list;           /**< the list of copyb nodes. */
  94 } walk_env_t;
  95
  96 static ir_mode *get_ir_mode(unsigned mode_bytes)
  97 {
  98         switch (mode_bytes) {
  99         case 1:  return mode_Bu;
 100         case 2:  return mode_Hu;
 101         case 4:  return mode_Iu;
 102         case 8:  return mode_Lu;
 103         case 16: return mode_LLu;
 104         default:
 105                 panic("unexpected mode size requested in copyb lowering");
 106         }
 107 }
 108
 109 /**
 110  * Turn a small CopyB node into a series of Load/Store nodes.
 111  */
 112 static void lower_small_copyb_node(ir_node *irn)
 113 {
 114         ir_graph *irg        = get_irn_irg(irn);
 115         unsigned  mode_bytes = native_mode_bytes;
 116         unsigned  size;
 117         unsigned  offset;
 118         ir_mode  *mode;
 119         ir_mode  *addr_mode;
 120         ir_node  *mem;
 121         ir_node  *addr_src;
 122         ir_node  *addr_dst;
 123         ir_node  *block;
 124         ir_type  *tp;
 125
 126         addr_src  = get_CopyB_src(irn);
 127         addr_dst  = get_CopyB_dst(irn);
 128         mem       = get_CopyB_mem(irn);
 129         addr_mode = get_irn_mode(addr_src);
 130         block     = get_nodes_block(irn);
 131
 132         tp   = get_CopyB_type(irn);
 133         size = get_type_size_bytes(tp);
 134
 135         offset     = 0;
 136         while (offset < size) {
 137                 mode = get_ir_mode(mode_bytes);
 138                 for (; offset + mode_bytes <= size; offset += mode_bytes) {
 139                         /* construct offset */
 140                         ir_node *addr_const;
 141                         ir_node *add;
 142                         ir_node *load;
 143                         ir_node *load_res;
 144                         ir_node *load_mem;
 145                         ir_node *store;
 146                         ir_node *store_mem;
 147
 148                         addr_const = new_r_Const_long(irg, mode_Iu, offset);
 149                         add        = new_r_Add(block, addr_src, addr_const, addr_mode);
 150
 151                         load     = new_r_Load(block, mem, add, mode, cons_none);
 152                         load_res = new_r_Proj(load, mode, pn_Load_res);
 153                         load_mem = new_r_Proj(load, mode_M, pn_Load_M);
 154
 155                         addr_const = new_r_Const_long(irg, mode_Iu, offset);
 156                         add        = new_r_Add(block, addr_dst, addr_const, addr_mode);
 157
 158                         store     = new_r_Store(block, load_mem, add, load_res, cons_none);
 159                         store_mem = new_r_Proj(store, mode_M, pn_Store_M);
 160
 161                         mem = store_mem;
 162                 }
 163
 164                 mode_bytes /= 2;
 165         }
 166
 167         turn_into_tuple(irn, pn_CopyB_max+1);
 168         set_Tuple_pred(irn, pn_CopyB_M,         mem);
 169         set_Tuple_pred(irn, pn_CopyB_X_regular, new_r_Bad(irg, mode_X));
 170         set_Tuple_pred(irn, pn_CopyB_X_except,  new_r_Bad(irg, mode_X));
 171 }
 172
 173 static ir_type *get_memcpy_methodtype()
 174 {
 175         ir_type              *tp           = new_type_method(3, 1);
 176         ir_mode              *size_t_mode  = get_ir_mode(native_mode_bytes);
 177
 178         set_method_param_type(tp, 0, get_type_for_mode(mode_P));
 179         set_method_param_type(tp, 1, get_type_for_mode(mode_P));
 180         set_method_param_type(tp, 2, get_type_for_mode(size_t_mode));
 181         set_method_res_type  (tp, 0, get_type_for_mode(mode_P));
 182
 183         return tp;
 184 }
 185
 186 static ir_node *get_memcpy_symconst(ir_graph *irg)
 187 {
 188         ident     *id  = new_id_from_str("memcpy");
 189         ir_type   *mt  = get_memcpy_methodtype();
 190         ir_entity *ent = new_entity(get_glob_type(), id, mt);
 191         symconst_symbol sym;
 192
 193         set_entity_ld_ident(ent, get_entity_ident(ent));
 194         sym.entity_p = ent;
 195
 196         return new_r_SymConst(irg, mode_P_code, sym, symconst_addr_ent);
 197 }
 198
 199 /**
 200  * Turn a large CopyB node into a memcpy call.
 201  */
 202 static void lower_large_copyb_node(ir_node *irn)
 203 {
 204         ir_graph *irg      = get_irn_irg(irn);
 205         ir_node  *block    = get_nodes_block(irn);
 206         dbg_info *dbgi     = get_irn_dbg_info(irn);
 207         ir_node  *mem      = get_CopyB_mem(irn);
 208         ir_node  *addr_src = get_CopyB_src(irn);
 209         ir_node  *addr_dst = get_CopyB_dst(irn);
 210         ir_type  *copyb_tp = get_CopyB_type(irn);
 211         unsigned  size     = get_type_size_bytes(copyb_tp);
 212
 213         ir_node  *symconst    = get_memcpy_symconst(irg);
 214         ir_type  *call_tp     = get_memcpy_methodtype();
 215         ir_mode  *mode_size_t = get_ir_mode(native_mode_bytes);
 216         ir_node  *in[3];
 217         ir_node  *call;
 218         ir_node  *call_mem;
 219
 220         in[0]    = addr_dst;
 221         in[1]    = addr_src;
 222         in[2]    = new_r_Const_long(irg, mode_size_t, size);
 223         call     = new_rd_Call(dbgi, block, mem, symconst, 3, in, call_tp);
 224         call_mem = new_r_Proj(call, mode_M, pn_Call_M);
 225
 226         turn_into_tuple(irn, 1);
 227         set_irn_n(irn, pn_CopyB_M, call_mem);
 228 }
 229
 230 static void lower_copyb_node(ir_node *irn)
 231 {
 232         ir_type *tp   = get_CopyB_type(irn);
 233         unsigned size = get_type_size_bytes(tp);
 234
 235         if (size <= max_small_size)
 236                 lower_small_copyb_node(irn);
 237         else if (size >= min_large_size)
 238                 lower_large_copyb_node(irn);
 239         else
 240                 assert(!"CopyB of invalid size handed to lower_copyb_node");
 241 }
 242
 243 /**
 244  * Post-Walker: find CopyB nodes.
 245  */
 246 static void find_copyb_nodes(ir_node *irn, void *ctx)
 247 {
 248         walk_env_t *env = (walk_env_t*)ctx;
 249         ir_type    *tp;
 250         unsigned   size;
 251         entry_t    *entry;
 252         bool        medium_sized;
 253
 254         if (is_Proj(irn)) {
 255                 ir_node *pred = get_Proj_pred(irn);
 256
 257                 if (is_CopyB(pred) && get_Proj_proj(irn) != pn_CopyB_M) {
 258                         /* found an exception Proj: remove it from the list again */
 259                         entry = (entry_t*)get_irn_link(pred);
 260                         list_del(&entry->list);
 261                 }
 262                 return;
 263         }
 264
 265         if (! is_CopyB(irn))
 266                 return;
 267
 268         tp = get_CopyB_type(irn);
 269         if (get_type_state(tp) != layout_fixed)
 270                 return;
 271
 272         size         = get_type_size_bytes(tp);
 273         medium_sized = max_small_size < size && size < min_large_size;
 274         if (medium_sized)
 275                 return; /* Nothing to do for medium-sized CopyBs. */
 276
 277         /* Okay, either small or large CopyB, so link it in and lower it later. */
 278         entry = OALLOC(&env->obst, entry_t);
 279         entry->copyb = irn;
 280         INIT_LIST_HEAD(&entry->list);
 281         set_irn_link(irn, entry);
 282         list_add_tail(&entry->list, &env->list);
 283 }
 284
 285 void lower_CopyB(ir_graph *irg, unsigned max_small_sz, unsigned min_large_sz)
 286 {
 287         const backend_params *bparams = be_get_backend_param();
 288         walk_env_t            env;
 289         entry_t              *entry;
 290
 291         assert(max_small_sz < min_large_sz && "CopyB size ranges must not overlap");
 292
 293         max_small_size    = max_small_sz;
 294         min_large_size    = min_large_sz;
 295         native_mode_bytes = bparams->machine_size / 8;
 296
 297         obstack_init(&env.obst);
 298         INIT_LIST_HEAD(&env.list);
 299         irg_walk_graph(irg, NULL, find_copyb_nodes, &env);
 300
 301         list_for_each_entry(entry_t, entry, &env.list, list) {
 302                 lower_copyb_node(entry->copyb);
 303         }
 304
 305         obstack_free(&env.obst, NULL);
 306 }