nsz Git - libfirm/blob - ir/lower/lower_copyb.c

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