lower_copyb.c 8.25 KB
Newer Older
Michael Beck's avatar
Michael Beck committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Michael Beck's avatar
Michael Beck committed
4
5
6
7
 */

/**
 * @file
8
9
 * @brief   Lower small CopyB nodes into a series of Load/Store nodes
 * @author  Michael Beck, Matthias Braun, Manuel Mohr
Michael Beck's avatar
Michael Beck committed
10
 */
Michael Beck's avatar
Michael Beck committed
11
#include "adt/list.h"
Michael Beck's avatar
Michael Beck committed
12
13
14
#include "ircons.h"
#include "lowering.h"
#include "irprog_t.h"
15
#include "irgwalk.h"
Michael Beck's avatar
Michael Beck committed
16
17
#include "irnode_t.h"
#include "type_t.h"
18
19
#include "irgmod.h"
#include "error.h"
20
#include "be.h"
21
#include "util.h"
22

Michael Beck's avatar
Michael Beck committed
23
24
25
26
27
28
typedef struct entry entry_t;
struct entry {
	struct list_head list;
	ir_node *copyb;
};

29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 * Every CopyB is assigned a size category as follows:
 *  - 'small'  iff                  size <= max_small_size,
 *  - 'medium' iff max_small_size < size <  min_large_size,
 *  - 'large'  iff                  size >= min_large_size.
 *
 * The idea is that each backend can apply different optimizations in each
 * of the three categories.
 *
 * For small CopyBs, the x86 backend could, e.g., emit a single SSE
 * instruction to copy 16 bytes.  Other backends might just go with a series
 * of Load/Stores.  Therefore, x86 would like to keep the small CopyB nodes
 * around whereas other backends would not.
 * For medium-sized CopyBs, the x86 backend might generate a rep-prefixed mov
 * instruction.  Hence, it also wants to keep the CopyBs in these cases.  Other
 * backends might handle this differently.
 * For large CopyBs, a call to memcpy is worth the call overhead, so large
 * CopyBs should always be lowered to memcpy calls.
 *
 * The lowerer performs the following actions if the CopyB is
 * - 'small':  Replace it with a series of Loads/Stores
 * - 'medium': Nothing.
 * - 'large':  Replace it with a call to memcpy.
 *
 * max_small_size and min_large_size allow for a flexible configuration.
 * For example, one backend could specify max_small_size == 0 and
 * min_large_size == 8192 to keep all CopyB nodes smaller than 8192 and get
 * memcpy Calls for all others.  Here, the set of small CopyBs is empty.
 * Another backend could specify max_small_size == 63 and min_large_size == 64
 * to lower all small CopyBs to Loads/Stores and all big CopyBs to memcpy.
 * Hence, the set of medium-sized CopyBs is empty and this backend never
 * sees a CopyB node at all.
 * If memcpy is not available, min_large_size can be set to UINT_MAX to prevent
 * the creation of calls to memcpy.  Note that CopyBs whose size is UINT_MAX
 * will still be lowered to memcpy calls because we check if the size is greater
 * *or equal* to min_large_size.  However, this should never occur in practice.
 */

static unsigned max_small_size; /**< The maximum size of a CopyB node
                                     so that it is regarded as 'small'. */
static unsigned min_large_size; /**< The minimum size of a CopyB node
                                     so that it is regarded as 'large'. */
71
static unsigned native_mode_bytes; /**< The size of the native mode in bytes. */
72
73
static int allow_misalignments; /**< Whether backend can handle misaligned
                                     loads and stores. */
74

Michael Beck's avatar
Michael Beck committed
75
typedef struct walk_env {
76
77
78
	struct obstack   obst;           /**< the obstack where data is allocated
	                                      on. */
	struct list_head list;           /**< the list of copyb nodes. */
Michael Beck's avatar
Michael Beck committed
79
} walk_env_t;
80

81
static ir_mode *get_ir_mode(unsigned mode_bytes)
82
{
83
	switch (mode_bytes) {
84
	case 1:  return mode_Bu;
85
86
87
88
89
90
	case 2:  return mode_Hu;
	case 4:  return mode_Iu;
	case 8:  return mode_Lu;
	case 16: return mode_LLu;
	default:
		panic("unexpected mode size requested in copyb lowering");
Michael Beck's avatar
Michael Beck committed
91
92
93
94
	}
}

/**
95
 * Turn a small CopyB node into a series of Load/Store nodes.
Michael Beck's avatar
Michael Beck committed
96
 */
97
static void lower_small_copyb_node(ir_node *irn)
98
{
99
	ir_graph *irg        = get_irn_irg(irn);
100
101
102
103
104
105
106
107
108
	ir_node  *block      = get_nodes_block(irn);
	ir_type  *tp         = get_CopyB_type(irn);
	ir_node  *addr_src   = get_CopyB_src(irn);
	ir_node  *addr_dst   = get_CopyB_dst(irn);
	ir_node  *mem        = get_CopyB_mem(irn);
	ir_mode  *addr_mode  = get_irn_mode(addr_src);
	unsigned  mode_bytes = allow_misalignments ? native_mode_bytes : tp->align;
	unsigned  size       = get_type_size_bytes(tp);
	unsigned  offset     = 0;
109
	ir_mode  *mode;
110

Michael Beck's avatar
Michael Beck committed
111
	while (offset < size) {
112
		mode = get_ir_mode(mode_bytes);
Michael Beck's avatar
Michael Beck committed
113
		for (; offset + mode_bytes <= size; offset += mode_bytes) {
114
115
116
117
118
119
120
121
122
			/* construct offset */
			ir_node *addr_const;
			ir_node *add;
			ir_node *load;
			ir_node *load_res;
			ir_node *load_mem;
			ir_node *store;
			ir_node *store_mem;

123
			addr_const = new_r_Const_long(irg, mode_Iu, offset);
124
			add        = new_r_Add(block, addr_src, addr_const, addr_mode);
125

126
			load     = new_r_Load(block, mem, add, mode, cons_none);
127
128
			load_res = new_r_Proj(load, mode, pn_Load_res);
			load_mem = new_r_Proj(load, mode_M, pn_Load_M);
129

130
			addr_const = new_r_Const_long(irg, mode_Iu, offset);
131
			add        = new_r_Add(block, addr_dst, addr_const, addr_mode);
132

133
			store     = new_r_Store(block, load_mem, add, load_res, cons_none);
134
			store_mem = new_r_Proj(store, mode_M, pn_Store_M);
135
136
137
138
139

			mem = store_mem;
		}

		mode_bytes /= 2;
Michael Beck's avatar
Michael Beck committed
140
	}
141

142
	exchange(irn, mem);
143
144
}

Andreas Zwinkau's avatar
Andreas Zwinkau committed
145
static ir_type *get_memcpy_methodtype(void)
146
{
Manuel Mohr's avatar
Manuel Mohr committed
147
148
	ir_type *tp          = new_type_method(3, 1);
	ir_mode *size_t_mode = get_ir_mode(native_mode_bytes);
149
150
151

	set_method_param_type(tp, 0, get_type_for_mode(mode_P));
	set_method_param_type(tp, 1, get_type_for_mode(mode_P));
152
	set_method_param_type(tp, 2, get_type_for_mode(size_t_mode));
153
154
155
156
157
158
159
160
161
	set_method_res_type  (tp, 0, get_type_for_mode(mode_P));

	return tp;
}

static ir_node *get_memcpy_symconst(ir_graph *irg)
{
	ident     *id  = new_id_from_str("memcpy");
	ir_type   *mt  = get_memcpy_methodtype();
162
	ir_entity *ent = create_compilerlib_entity(id, mt);
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
	symconst_symbol sym;

	sym.entity_p = ent;
	return new_r_SymConst(irg, mode_P_code, sym, symconst_addr_ent);
}

/**
 * Turn a large CopyB node into a memcpy call.
 */
static void lower_large_copyb_node(ir_node *irn)
{
	ir_graph *irg      = get_irn_irg(irn);
	ir_node  *block    = get_nodes_block(irn);
	dbg_info *dbgi     = get_irn_dbg_info(irn);
	ir_node  *mem      = get_CopyB_mem(irn);
	ir_node  *addr_src = get_CopyB_src(irn);
	ir_node  *addr_dst = get_CopyB_dst(irn);
	ir_type  *copyb_tp = get_CopyB_type(irn);
	unsigned  size     = get_type_size_bytes(copyb_tp);

183
184
185
	ir_node  *symconst    = get_memcpy_symconst(irg);
	ir_type  *call_tp     = get_memcpy_methodtype();
	ir_mode  *mode_size_t = get_ir_mode(native_mode_bytes);
186
187
188
189
190
191
	ir_node  *in[3];
	ir_node  *call;
	ir_node  *call_mem;

	in[0]    = addr_dst;
	in[1]    = addr_src;
192
	in[2]    = new_r_Const_long(irg, mode_size_t, size);
193
194
195
	call     = new_rd_Call(dbgi, block, mem, symconst, 3, in, call_tp);
	call_mem = new_r_Proj(call, mode_M, pn_Call_M);

196
	exchange(irn, call_mem);
197
198
}

199
static void lower_copyb_node(ir_node *irn)
200
201
202
203
204
{
	ir_type *tp   = get_CopyB_type(irn);
	unsigned size = get_type_size_bytes(tp);

	if (size <= max_small_size)
205
		lower_small_copyb_node(irn);
206
207
208
209
210
211
	else if (size >= min_large_size)
		lower_large_copyb_node(irn);
	else
		assert(!"CopyB of invalid size handed to lower_copyb_node");
}

Michael Beck's avatar
Michael Beck committed
212
/**
213
 * Post-Walker: find CopyB nodes.
Michael Beck's avatar
Michael Beck committed
214
 */
215
216
static void find_copyb_nodes(ir_node *irn, void *ctx)
{
217
	walk_env_t *env = (walk_env_t*)ctx;
Michael Beck's avatar
Michael Beck committed
218
219
220
	ir_type    *tp;
	unsigned   size;
	entry_t    *entry;
221
	bool        medium_sized;
Michael Beck's avatar
Michael Beck committed
222
223
224
225
226
227
228
229

	if (! is_CopyB(irn))
		return;

	tp = get_CopyB_type(irn);
	if (get_type_state(tp) != layout_fixed)
		return;

230
231
232
233
	size         = get_type_size_bytes(tp);
	medium_sized = max_small_size < size && size < min_large_size;
	if (medium_sized)
		return; /* Nothing to do for medium-sized CopyBs. */
Michael Beck's avatar
Michael Beck committed
234

235
	/* Okay, either small or large CopyB, so link it in and lower it later. */
236
	entry = OALLOC(&env->obst, entry_t);
Michael Beck's avatar
Michael Beck committed
237
238
239
240
241
242
	entry->copyb = irn;
	INIT_LIST_HEAD(&entry->list);
	set_irn_link(irn, entry);
	list_add_tail(&entry->list, &env->list);
}

243
244
void lower_CopyB(ir_graph *irg, unsigned max_small_sz, unsigned min_large_sz,
                 int allow_misaligns)
245
{
246
247
248
	const backend_params *bparams = be_get_backend_param();
	walk_env_t            env;

249
	assert(max_small_sz < min_large_sz && "CopyB size ranges must not overlap");
250

251
252
253
254
	max_small_size      = max_small_sz;
	min_large_size      = min_large_sz;
	native_mode_bytes   = bparams->machine_size / 8;
	allow_misalignments = allow_misaligns;
255

Michael Beck's avatar
Michael Beck committed
256
257
258
259
260
	obstack_init(&env.obst);
	INIT_LIST_HEAD(&env.list);
	irg_walk_graph(irg, NULL, find_copyb_nodes, &env);

	list_for_each_entry(entry_t, entry, &env.list, list) {
261
		lower_copyb_node(entry->copyb);
Michael Beck's avatar
Michael Beck committed
262
	}
263

Michael Beck's avatar
Michael Beck committed
264
	obstack_free(&env.obst, NULL);
Michael Beck's avatar
Michael Beck committed
265
}