scalar_replace.c 20.3 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

Michael Beck's avatar
Michael Beck committed
20
21
22
23
24
/**
 * @file
 * @brief   Scalar replacement of compounds.
 * @author  Beyhan Veliev, Michael Beck
 * @version $Id$
Michael Beck's avatar
Michael Beck committed
25
 */
Michael Beck's avatar
Michael Beck committed
26
27
#include "config.h"

Michael Beck's avatar
Michael Beck committed
28
29
#include <string.h>

30
#include "iroptimize.h"
31
#include "scalar_replace.h"
32
#include "opt_init.h"
Michael Beck's avatar
Michael Beck committed
33
34
35
36
37
38
39
40
41
42
43
#include "irflag_t.h"
#include "irouts.h"
#include "set.h"
#include "pset.h"
#include "array.h"
#include "tv.h"
#include "ircons_t.h"
#include "hashptr.h"
#include "irgwalk.h"
#include "irgmod.h"
#include "irnode_t.h"
44
#include "irpass.h"
45
#include "irtools.h"
46
#include "xmalloc.h"
47
48
#include "debug.h"
#include "error.h"
Michael Beck's avatar
Michael Beck committed
49

50
51
#define SET_VNUM(node, vnum) set_irn_link(node, INT_TO_PTR(vnum))
#define GET_VNUM(node)       (unsigned)PTR_TO_INT(get_irn_link(node))
Michael Beck's avatar
Michael Beck committed
52

53
/**
Michael Beck's avatar
Michael Beck committed
54
 * A path element entry: it is either an entity
Michael Beck's avatar
Michael Beck committed
55
 * or a tarval, because we evaluate only constant array
56
57
58
 * accesses like a.b.c[8].d
 */
typedef union {
Michael Beck's avatar
Michael Beck committed
59
	ir_entity *ent;
Matthias Braun's avatar
Matthias Braun committed
60
	ir_tarval *tv;
61
} path_elem_t;
Michael Beck's avatar
Michael Beck committed
62

63
64
/**
 * An access path, used to assign value numbers
65
 * to variables that will be scalar replaced.
66
 */
67
typedef struct path_t {
Michael Beck's avatar
Michael Beck committed
68
	unsigned    vnum;      /**< The value number. */
69
	size_t      path_len;  /**< The length of the access path. */
Michael Beck's avatar
Michael Beck committed
70
	path_elem_t path[1];   /**< The path. */
71
72
} path_t;

73
/** The size of a path in bytes. */
Michael Beck's avatar
Michael Beck committed
74
75
#define PATH_SIZE(p)  (sizeof(*(p)) + sizeof((p)->path[0]) * ((p)->path_len - 1))

76
typedef struct scalars_t {
Michael Beck's avatar
Michael Beck committed
77
	ir_entity *ent;              /**< A entity for scalar replacement. */
78
79
} scalars_t;

80
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
81
82

/**
Michael Beck's avatar
Michael Beck committed
83
84
85
 * Compare two pathes.
 *
 * @return 0 if they are identically
86
 */
87
88
static int path_cmp(const void *elt, const void *key, size_t size)
{
89
90
	const path_t *p1 = (const path_t*)elt;
	const path_t *p2 = (const path_t*)key;
Michael Beck's avatar
Michael Beck committed
91
	(void) size;
92

Michael Beck's avatar
Michael Beck committed
93
94
	/* we can use memcmp here, because identical tarvals should have identical addresses */
	return memcmp(p1->path, p2->path, p1->path_len * sizeof(p1->path[0]));
95
96
97
}

/**
Michael Beck's avatar
Michael Beck committed
98
99
100
 * Compare two elements of the scalars_t set.
 *
 * @return 0 if they are identically
101
 */
102
103
static int ent_cmp(const void *elt, const void *key, size_t size)
{
104
105
	const scalars_t *c1 = (const scalars_t*)elt;
	const scalars_t *c2 = (const scalars_t*)key;
Michael Beck's avatar
Michael Beck committed
106
	(void) size;
107

Michael Beck's avatar
Michael Beck committed
108
	return c1->ent != c2->ent;
109
110
111
}

/**
Michael Beck's avatar
Michael Beck committed
112
 * Calculate a hash value for a path.
113
 */
114
115
static unsigned path_hash(const path_t *path)
{
Michael Beck's avatar
Michael Beck committed
116
117
	unsigned hash = 0;
	unsigned i;
118

Michael Beck's avatar
Michael Beck committed
119
120
	for (i = 0; i < path->path_len; ++i)
		hash ^= (unsigned)PTR_TO_INT(path->path[i].ent);
121

Michael Beck's avatar
Michael Beck committed
122
	return hash >> 4;
123
124
125
}

/**
Michael Beck's avatar
Michael Beck committed
126
 * Returns non-zero, if all indeces of a Sel node are constants.
127
 *
Michael Beck's avatar
Michael Beck committed
128
 * @param sel  the Sel node that will be checked
129
 */
130
131
static int is_const_sel(ir_node *sel)
{
Michael Beck's avatar
Michael Beck committed
132
	int i, n = get_Sel_n_indexs(sel);
133

Michael Beck's avatar
Michael Beck committed
134
135
	for (i = 0; i < n; ++i) {
		ir_node *idx = get_Sel_index(sel, i);
136

137
		if (!is_Const(idx))
Michael Beck's avatar
Michael Beck committed
138
139
140
			return 0;
	}
	return 1;
141
142
}

143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/**
 * Check the mode of a Load/Store with the mode of the entity
 * that is accessed.
 * If the mode of the entity and the Load/Store mode do not match, we
 * have the bad reinterpret case:
 *
 * int i;
 * char b = *(char *)&i;
 *
 * We do NOT count this as one value and return address_taken
 * in that case.
 * However, we support an often used case. If the mode is two-complement
 * we allow casts between signed/unsigned.
 *
 * @param mode     the mode of the Load/Store
 * @param ent_mode the mode of the accessed entity
 */
160
161
static int check_load_store_mode(ir_mode *mode, ir_mode *ent_mode)
{
Michael Beck's avatar
Michael Beck committed
162
163
164
165
166
167
168
169
170
	if (ent_mode != mode) {
		if (ent_mode == NULL ||
		    get_mode_size_bits(ent_mode) != get_mode_size_bits(mode) ||
		    get_mode_sort(ent_mode) != get_mode_sort(mode) ||
		    get_mode_arithmetic(ent_mode) != irma_twos_complement ||
		    get_mode_arithmetic(mode) != irma_twos_complement)
			return 0;
	}
	return 1;
171
172
}

Michael Beck's avatar
Michael Beck committed
173
/*
Michael Beck's avatar
Michael Beck committed
174
 * Returns non-zero, if the address of an entity
175
 * represented by a Sel node (or its successor Sels) is taken.
176
 */
Michael Beck's avatar
Michael Beck committed
177
int is_address_taken(ir_node *sel)
178
{
179
180
181
	int       i, input_nr, k;
	ir_mode   *emode, *mode;
	ir_node   *value;
Michael Beck's avatar
Michael Beck committed
182
183
184
185
186
187
188
189
190
191
	ir_entity *ent;

	if (! is_const_sel(sel))
		return 1;

	for (i = get_irn_n_outs(sel) - 1; i >= 0; --i) {
		ir_node *succ = get_irn_out(sel, i);

		switch (get_irn_opcode(succ)) {
		case iro_Load:
192
193
194
			/* do not remove volatile variables */
			if (get_Load_volatility(succ) == volatility_is_volatile)
				return 1;
Michael Beck's avatar
Michael Beck committed
195
196
197
198
199
200
201
202
203
204
205
206
207
			/* check if this load is not a hidden conversion */
			mode = get_Load_mode(succ);
			ent = get_Sel_entity(sel);
			emode = get_type_mode(get_entity_type(ent));
			if (! check_load_store_mode(mode, emode))
				return 1;
			break;

		case iro_Store:
			/* check that Sel is not the Store's value */
			value = get_Store_value(succ);
			if (value == sel)
				return 1;
208
209
210
			/* do not remove volatile variables */
			if (get_Store_volatility(succ) == volatility_is_volatile)
				return 1;
Michael Beck's avatar
Michael Beck committed
211
212
213
214
215
216
217
218
219
			/* check if this Store is not a hidden conversion */
			mode = get_irn_mode(value);
			ent = get_Sel_entity(sel);
			emode = get_type_mode(get_entity_type(ent));
			if (! check_load_store_mode(mode, emode))
				return 1;
			break;

		case iro_Sel: {
Michael Beck's avatar
Michael Beck committed
220
221
			int       res;
			ir_entity *entity = get_Sel_entity(succ);
222
223
224
225
			/* we can't handle unions correctly yet -> address taken */
			if (is_Union_type(get_entity_owner(entity)))
				return 1;

Michael Beck's avatar
Michael Beck committed
226
			/* Check the Sel successor of Sel */
Michael Beck's avatar
Michael Beck committed
227
			res = is_address_taken(succ);
Michael Beck's avatar
Michael Beck committed
228
229
230
231
232
233
234
235
236
237
238
239
240
241
			if (res)
				return 1;
			break;
		}

		case iro_Call:
			/* The address of an entity is given as a parameter.
			 * As long as we do not have analyses that can tell what
			 * is done with parameters, think is taken.
			 * One special case: If the Call type tells that it's a
			 * value parameter, the address is NOT taken.
			 */
			return 1;

242
243
244
245
246
247
248
		case iro_Id: {
			int res = is_address_taken(succ);
			if (res)
				return 1;
			break;
		}

249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
		case iro_Tuple:
			/* Non-optimized Tuple, happens in inlining */
			for (input_nr = get_Tuple_n_preds(succ) - 1; input_nr >= 0; --input_nr) {
				ir_node *pred = get_Tuple_pred(succ, input_nr);

				if (pred == sel) {
					/* we found one input */
					for (k = get_irn_n_outs(succ) - 1; k >= 0; --k) {
						ir_node *proj = get_irn_out(succ, k);

						if (is_Proj(proj) && get_Proj_proj(proj) == input_nr) {
							int res = is_address_taken(proj);
							if (res)
								return 1;
						}
					}
				}
			}
			break;

Michael Beck's avatar
Michael Beck committed
269
270
271
272
273
274
		default:
			/* another op, the address is taken */
			return 1;
		}
	}
	return 0;
275
276
277
}

/**
Michael Beck's avatar
Michael Beck committed
278
 * Link all leave Sels with the entity.
279
280
281
282
 *
 * @param ent  the entity that will be scalar replaced
 * @param sel  a Sel node that selects some fields of this entity
 */
283
284
static int link_all_leave_sels(ir_entity *ent, ir_node *sel)
{
285
	int i, is_leave = 1;
Michael Beck's avatar
Michael Beck committed
286

287
	for (i = get_irn_n_outs(sel) - 1; i >= 0; --i) {
Michael Beck's avatar
Michael Beck committed
288
289
290
		ir_node *succ = get_irn_out(sel, i);

		if (is_Sel(succ)) {
291
292
			/* the current leave has further Sel's, no leave */
			is_leave = 0;
Michael Beck's avatar
Michael Beck committed
293
			link_all_leave_sels(ent, succ);
294
295
		} else if (is_Id(succ)) {
			is_leave &= link_all_leave_sels(ent, succ);
Michael Beck's avatar
Michael Beck committed
296
297
298
		}
	}

299
300
301
	if (is_leave) {
		/* beware of Id's */
		sel = skip_Id(sel);
Michael Beck's avatar
Michael Beck committed
302
303

		/* we know we are at a leave, because this function is only
304
305
		 * called if the address is NOT taken, so sel's successor(s)
		 * must be Loads or Stores
Michael Beck's avatar
Michael Beck committed
306
307
308
309
		 */
		set_irn_link(sel, get_entity_link(ent));
		set_entity_link(ent, sel);
	}
310
	return is_leave;
311
312
}

Michael Beck's avatar
Michael Beck committed
313
/* we need a special address that serves as an address taken marker */
314
315
316
317
static char _x;
static void *ADDRESS_TAKEN = &_x;

/**
Michael Beck's avatar
Michael Beck committed
318
 * Find possible scalar replacements.
319
320
321
322
323
 *
 * @param irg  an IR graph
 *
 * This function finds variables on the (members of the) frame type
 * that can be scalar replaced, because their address is never taken.
324
 * If such a variable is found, its entity link will hold a list of all
Michael Beck's avatar
Michael Beck committed
325
326
327
328
329
 * Sel nodes, that selects the atomic fields of this entity.
 * Otherwise, the link will be ADDRESS_TAKEN or NULL.
 *
 * @return  non-zero if at least one entity could be replaced
 *          potentially
330
 */
331
332
static int find_possible_replacements(ir_graph *irg)
{
333
334
	ir_node *irg_frame;
	ir_type *frame_tp;
335
	int     i, j, k, static_link_arg;
336
	int     res = 0;
Michael Beck's avatar
Michael Beck committed
337
338
339
340

	/*
	 * First, clear the link field of all interesting entities.
	 */
341
342
343
344
	frame_tp = get_irg_frame_type(irg);
	for (i = get_class_n_members(frame_tp) - 1; i >= 0; --i) {
		ir_entity *ent = get_class_member(frame_tp, i);
		set_entity_link(ent, NULL);
Michael Beck's avatar
Michael Beck committed
345
346
	}

347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
	/* check for inner functions:
	 * FIXME: need a way to get the argument position for the static link */
	static_link_arg = 0;
	for (i = get_class_n_members(frame_tp) - 1; i >= 0; --i) {
		ir_entity *ent = get_class_member(frame_tp, i);
		if (is_method_entity(ent)) {
			ir_graph *inner_irg = get_entity_irg(ent);
			ir_node  *args;

			assure_irg_outs(inner_irg);
			args = get_irg_args(inner_irg);
			for (j = get_irn_n_outs(args) - 1; j >= 0; --j) {
				ir_node *arg = get_irn_out(args, j);

				if (get_Proj_proj(arg) == static_link_arg) {
					for (k = get_irn_n_outs(arg) - 1; k >= 0; --k) {
						ir_node *succ = get_irn_out(arg, k);

						if (is_Sel(succ)) {
							ir_entity *ent = get_Sel_entity(succ);

							if (get_entity_owner(ent) == frame_tp) {
								/* found an access to the outer frame */
								set_entity_link(ent, ADDRESS_TAKEN);
							}
						}
					}
				}
			}
		}
	}

Michael Beck's avatar
Michael Beck committed
379
380
381
382
383
	/*
	 * Check the ir_graph for Sel nodes. If the entity of Sel
	 * isn't a scalar replacement set the link of this entity
	 * equal ADDRESS_TAKEN.
	 */
384
385
	irg_frame = get_irg_frame(irg);
	for (i = get_irn_n_outs(irg_frame) - 1; i >= 0; --i) {
Michael Beck's avatar
Michael Beck committed
386
387
388
389
390
391
		ir_node *succ = get_irn_out(irg_frame, i);

		if (is_Sel(succ)) {
			ir_entity *ent = get_Sel_entity(succ);
			ir_type *ent_type;

392
393
394
395
396
			/* we are only interested in entities on the frame, NOT
			   on the value type */
			if (get_entity_owner(ent) != frame_tp)
				continue;

Michael Beck's avatar
Michael Beck committed
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
			if (get_entity_link(ent) == ADDRESS_TAKEN)
				continue;

			/*
			 * Beware: in rare cases even entities on the frame might be
			 * volatile. This might happen if the entity serves as a store
			 * to a value that must survive a exception. Do not optimize
			 * such entities away.
			 */
			if (get_entity_volatility(ent) == volatility_is_volatile) {
				set_entity_link(ent, ADDRESS_TAKEN);
				continue;
			}

			ent_type = get_entity_type(ent);

			/* we can handle arrays, structs and atomic types yet */
			if (is_Array_type(ent_type) || is_Struct_type(ent_type) || is_atomic_type(ent_type)) {
				if (is_address_taken(succ)) {
416
417
					 /* killing one */
					if (get_entity_link(ent))
Michael Beck's avatar
Michael Beck committed
418
419
420
421
422
423
424
425
426
427
428
429
430
						--res;
					set_entity_link(ent, ADDRESS_TAKEN);
				} else {
					/* possible found one */
					if (get_entity_link(ent) == NULL)
						++res;
					link_all_leave_sels(ent, succ);
				}
			}
		}
	}

	return res;
431
432
433
}

/**
434
 * Return a path from the Sel node "sel" to its root.
Michael Beck's avatar
Michael Beck committed
435
436
437
 *
 * @param sel  the Sel node
 * @param len  the length of the path so far
438
 */
439
static path_t *find_path(ir_node *sel, size_t len)
440
{
441
442
	size_t pos;
	int i, n;
Michael Beck's avatar
Michael Beck committed
443
444
	path_t *res;
	ir_node *pred = get_Sel_ptr(sel);
Michael Beck's avatar
Michael Beck committed
445

Michael Beck's avatar
Michael Beck committed
446
447
448
	/* the current Sel node will add some path elements */
	n    = get_Sel_n_indexs(sel);
	len += n + 1;
449

Michael Beck's avatar
Michael Beck committed
450
451
	if (! is_Sel(pred)) {
		/* we found the root */
452
		res = XMALLOCF(path_t, path, len);
Michael Beck's avatar
Michael Beck committed
453
454
455
		res->path_len = len;
	} else
		res = find_path(pred, len);
456

Michael Beck's avatar
Michael Beck committed
457
	assert(len <= res->path_len);
Michael Beck's avatar
Michael Beck committed
458
	pos = res->path_len - len;
459

Michael Beck's avatar
Michael Beck committed
460
461
462
	res->path[pos++].ent = get_Sel_entity(sel);
	for (i = 0; i < n; ++i) {
		ir_node *index = get_Sel_index(sel, i);
463

Michael Beck's avatar
Michael Beck committed
464
465
466
		res->path[pos++].tv = get_Const_tarval(index);
	}
	return res;
467
468
469
470
}


/**
Michael Beck's avatar
Michael Beck committed
471
472
 * Allocate value numbers for the leaves
 * in our found entities.
473
 *
Michael Beck's avatar
Michael Beck committed
474
 * @param sels  a set that will contain all Sels that have a value number
475
476
477
478
479
480
481
 * @param ent   the entity that will be scalar replaced
 * @param vnum  the first value number we can assign
 * @param modes a flexible array, containing all the modes of
 *              the value numbers.
 *
 * @return the next free value number
 */
482
static unsigned allocate_value_numbers(pset *sels, ir_entity *ent, unsigned vnum, ir_mode ***modes)
483
{
Michael Beck's avatar
Michael Beck committed
484
485
486
	ir_node *sel, *next;
	path_t *key, *path;
	set *pathes = new_set(path_cmp, 8);
487

488
	DB((dbg, SET_LEVEL_3, "  Visiting Sel nodes of entity %+F\n", ent));
Michael Beck's avatar
Michael Beck committed
489
	/* visit all Sel nodes in the chain of the entity */
490
491
492
	for (sel = (ir_node*)get_entity_link(ent); sel != NULL;
	     sel = next) {
		next = (ir_node*)get_irn_link(sel);
493

Michael Beck's avatar
Michael Beck committed
494
495
		/* we must mark this sel for later */
		pset_insert_ptr(sels, sel);
Michael Beck's avatar
Michael Beck committed
496

Michael Beck's avatar
Michael Beck committed
497
		key  = find_path(sel, 0);
498
		path = (path_t*)set_find(pathes, key, PATH_SIZE(key), path_hash(key));
499

500
		if (path) {
Michael Beck's avatar
Michael Beck committed
501
			SET_VNUM(sel, path->vnum);
502
503
			DB((dbg, SET_LEVEL_3, "  %+F represents value %u\n", sel, path->vnum));
		} else {
Michael Beck's avatar
Michael Beck committed
504
			key->vnum = vnum++;
505

Michael Beck's avatar
Michael Beck committed
506
			set_insert(pathes, key, PATH_SIZE(key), path_hash(key));
507

Michael Beck's avatar
Michael Beck committed
508
			SET_VNUM(sel, key->vnum);
509
510
			DB((dbg, SET_LEVEL_3, "  %+F represents value %u\n", sel, key->vnum));

511
			ARR_EXTO(ir_mode *, *modes, (key->vnum + 15) & ~15);
512

Michael Beck's avatar
Michael Beck committed
513
			(*modes)[key->vnum] = get_type_mode(get_entity_type(get_Sel_entity(sel)));
514

Michael Beck's avatar
Michael Beck committed
515
			assert((*modes)[key->vnum] && "Value is not atomic");
Michael Beck's avatar
Michael Beck committed
516
517

#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
518
			/* Debug output */
519
			{
Michael Beck's avatar
Michael Beck committed
520
				unsigned i;
521
				DB((dbg, SET_LEVEL_2, "  %s", get_entity_name(key->path[0].ent)));
Michael Beck's avatar
Michael Beck committed
522
523
				for (i = 1; i < key->path_len; ++i) {
					if (is_entity(key->path[i].ent))
524
						DB((dbg, SET_LEVEL_2, ".%s", get_entity_name(key->path[i].ent)));
Michael Beck's avatar
Michael Beck committed
525
					else
526
						DB((dbg, SET_LEVEL_2, "[%ld]", get_tarval_long(key->path[i].tv)));
Michael Beck's avatar
Michael Beck committed
527
				}
528
				DB((dbg, SET_LEVEL_2, " = %u (%s)\n", PTR_TO_INT(get_irn_link(sel)), get_mode_name((*modes)[key->vnum])));
Michael Beck's avatar
Michael Beck committed
529
			}
Michael Beck's avatar
Michael Beck committed
530
#endif /* DEBUG_libfirm */
Michael Beck's avatar
Michael Beck committed
531
532
533
		}
		free(key);
	}
534

Michael Beck's avatar
Michael Beck committed
535
536
537
	del_set(pathes);
	set_entity_link(ent, NULL);
	return vnum;
538
539
}

Michael Beck's avatar
Michael Beck committed
540
541
542
/**
 * A list entry for the fixing lists
 */
543
typedef struct list_entry_t {
Michael Beck's avatar
Michael Beck committed
544
545
	ir_node  *node;   /**< the node that must be fixed */
	unsigned vnum;    /**< the value number of this node */
Michael Beck's avatar
Michael Beck committed
546
} list_entry_t;
547
548
549
550

/**
 * environment for memory walker
 */
551
typedef struct env_t {
Michael Beck's avatar
Michael Beck committed
552
553
554
	int          nvals;       /**< number of values */
	ir_mode      **modes;     /**< the modes of the values */
	pset         *sels;       /**< A set of all Sel nodes that have a value number */
555
556
557
} env_t;

/**
558
 * topological post-walker.
559
 */
560
561
static void topologic_walker(ir_node *node, void *ctx)
{
562
	env_t    *env = (env_t*)ctx;
563
564
565
566
	ir_graph *irg = get_irn_irg(node);
	ir_node  *adr, *block, *mem, *val;
	ir_mode  *mode;
	unsigned vnum;
Michael Beck's avatar
Michael Beck committed
567

568
	if (is_Load(node)) {
Michael Beck's avatar
Michael Beck committed
569
570
571
		/* a load, check if we can resolve it */
		adr = get_Load_ptr(node);

572
573
574
		DB((dbg, SET_LEVEL_3, "  checking %+F for replacement ", node));
		if (! is_Sel(adr)) {
			DB((dbg, SET_LEVEL_3, "no Sel input (%+F)\n", adr));
Michael Beck's avatar
Michael Beck committed
575
			return;
576
		}
Michael Beck's avatar
Michael Beck committed
577

578
579
		if (! pset_find_ptr(env->sels, adr)) {
			DB((dbg, SET_LEVEL_3, "Sel %+F has no VNUM\n", adr));
Michael Beck's avatar
Michael Beck committed
580
			return;
581
		}
Michael Beck's avatar
Michael Beck committed
582
583
584
585
586

		/* ok, we have a Load that will be replaced */
		vnum = GET_VNUM(adr);
		assert(vnum < (unsigned)env->nvals);

587
		DB((dbg, SET_LEVEL_3, "replacing by value %u\n", vnum));
Michael Beck's avatar
Michael Beck committed
588

589
590
591
		block = get_nodes_block(node);
		set_cur_block(block);

Michael Beck's avatar
Michael Beck committed
592
		/* check, if we can replace this Load */
593
		val = get_value(vnum, env->modes[vnum]);
Michael Beck's avatar
Michael Beck committed
594

595
596
597
598
599
600
601
602
603
		/* Beware: A Load can contain a hidden conversion in Firm.
		This happens for instance in the following code:

		 int i;
		 unsigned j = *(unsigned *)&i;

		Handle this here. */
		mode = get_Load_mode(node);
		if (mode != get_irn_mode(val))
604
			val = new_rd_Conv(get_irn_dbg_info(node), block, val, mode);
605
606
607
608
609

		mem = get_Load_mem(node);
		turn_into_tuple(node, pn_Load_max);
		set_Tuple_pred(node, pn_Load_M,         mem);
		set_Tuple_pred(node, pn_Load_res,       val);
610
611
		set_Tuple_pred(node, pn_Load_X_regular, new_r_Jmp(block));
		set_Tuple_pred(node, pn_Load_X_except,  new_r_Bad(irg));
612
	} else if (is_Store(node)) {
613
614
		DB((dbg, SET_LEVEL_3, "  checking %+F for replacement ", node));

Michael Beck's avatar
Michael Beck committed
615
616
617
		/* a Store always can be replaced */
		adr = get_Store_ptr(node);

618
619
		if (! is_Sel(adr)) {
			DB((dbg, SET_LEVEL_3, "no Sel input (%+F)\n", adr));
Michael Beck's avatar
Michael Beck committed
620
			return;
621
		}
Michael Beck's avatar
Michael Beck committed
622

623
624
		if (! pset_find_ptr(env->sels, adr)) {
			DB((dbg, SET_LEVEL_3, "Sel %+F has no VNUM\n", adr));
Michael Beck's avatar
Michael Beck committed
625
			return;
626
		}
Michael Beck's avatar
Michael Beck committed
627
628
629
630

		vnum = GET_VNUM(adr);
		assert(vnum < (unsigned)env->nvals);

631
		DB((dbg, SET_LEVEL_3, "replacing by value %u\n", vnum));
Michael Beck's avatar
Michael Beck committed
632

633
634
635
		block = get_nodes_block(node);
		set_cur_block(block);

Michael Beck's avatar
Michael Beck committed
636
637
638
		/* Beware: A Store can contain a hidden conversion in Firm. */
		val = get_Store_value(node);
		if (get_irn_mode(val) != env->modes[vnum])
639
			val = new_rd_Conv(get_irn_dbg_info(node), block, val, env->modes[vnum]);
Michael Beck's avatar
Michael Beck committed
640

641
		set_value(vnum, val);
Michael Beck's avatar
Michael Beck committed
642

643
		mem = get_Store_mem(node);
Michael Beck's avatar
Michael Beck committed
644
645
		turn_into_tuple(node, pn_Store_max);
		set_Tuple_pred(node, pn_Store_M,         mem);
646
647
		set_Tuple_pred(node, pn_Store_X_regular, new_r_Jmp(block));
		set_Tuple_pred(node, pn_Store_X_except,  new_r_Bad(irg));
Michael Beck's avatar
Michael Beck committed
648
	}
649
650
651
}

/**
652
 * Make scalar replacement.
653
 *
Michael Beck's avatar
Michael Beck committed
654
655
 * @param sels    A set containing all Sel nodes that have a value number
 * @param nvals   The number of scalars.
Michael Beck's avatar
Michael Beck committed
656
657
 * @param modes   A flexible array, containing all the modes of
 *                the value numbers.
658
 */
659
660
static void do_scalar_replacements(ir_graph *irg, pset *sels, int nvals,
                                   ir_mode **modes)
661
{
Michael Beck's avatar
Michael Beck committed
662
663
	env_t env;

664
	ssa_cons_start(irg, nvals);
665

666
667
668
	env.nvals = nvals;
	env.modes = modes;
	env.sels  = sels;
Michael Beck's avatar
Michael Beck committed
669
670
671
672
673

	/*
	 * second step: walk over the graph blockwise in topological order
	 * and fill the array as much as possible.
	 */
674
675
	DB((dbg, SET_LEVEL_3, "Substituting Loads and Stores in %+F\n", irg));
	irg_walk_blkwise_graph(irg, NULL, topologic_walker, &env);
Michael Beck's avatar
Michael Beck committed
676

677
	ssa_cons_finish(irg);
678
679
680
681
682
}

/*
 * Find possible scalar replacements
 *
Michael Beck's avatar
Michael Beck committed
683
 * @param irg  The current ir graph.
Michael Beck's avatar
Michael Beck committed
684
 */
685
686
int scalar_replacement_opt(ir_graph *irg)
{
Michael Beck's avatar
Michael Beck committed
687
688
689
690
691
692
693
	unsigned  nvals;
	int       i;
	scalars_t key, *value;
	ir_node   *irg_frame;
	ir_mode   **modes;
	set       *set_ent;
	pset      *sels;
694
	ir_type   *ent_type, *frame_tp;
695
	int       res = 0;
Michael Beck's avatar
Michael Beck committed
696
697
698
699

	/* Call algorithm that computes the out edges */
	assure_irg_outs(irg);

700
	/* we use the link field to store the VNUM */
701
	ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
702
	irp_reserve_resources(irp, IR_RESOURCE_ENTITY_LINK);
703

Michael Beck's avatar
Michael Beck committed
704
705
	/* Find possible scalar replacements */
	if (find_possible_replacements(irg)) {
706
		DB((dbg, SET_LEVEL_1, "Scalar Replacement: %+F\n", irg));
Michael Beck's avatar
Michael Beck committed
707
708
709

		/* Insert in set the scalar replacements. */
		irg_frame = get_irg_frame(irg);
710
711
712
713
714
		nvals     = 0;
		modes     = NEW_ARR_F(ir_mode *, 16);
		set_ent   = new_set(ent_cmp, 8);
		sels      = pset_new_ptr(8);
		frame_tp  = get_irg_frame_type(irg);
Michael Beck's avatar
Michael Beck committed
715

716
		for (i = get_irn_n_outs(irg_frame) - 1; i >= 0; --i) {
Michael Beck's avatar
Michael Beck committed
717
718
719
720
721
			ir_node *succ = get_irn_out(irg_frame, i);

			if (is_Sel(succ)) {
				ir_entity *ent = get_Sel_entity(succ);

722
723
724
725
726
				/* we are only interested in entities on the frame, NOT
				   on the value type */
				if (get_entity_owner(ent) != frame_tp)
					continue;

Michael Beck's avatar
Michael Beck committed
727
728
729
730
731
732
733
734
				if (get_entity_link(ent) == NULL || get_entity_link(ent) == ADDRESS_TAKEN)
					continue;

				ent_type = get_entity_type(ent);

				key.ent       = ent;
				set_insert(set_ent, &key, sizeof(key), HASH_PTR(key.ent));

735
736
737
738
739
740
741
742
743
#ifdef DEBUG_libfirm
				if (is_Array_type(ent_type)) {
					DB((dbg, SET_LEVEL_1, "  found array %s\n", get_entity_name(ent)));
				} else if (is_Struct_type(ent_type)) {
					DB((dbg, SET_LEVEL_1, "  found struct %s\n", get_entity_name(ent)));
				} else if (is_atomic_type(ent_type))
					DB((dbg, SET_LEVEL_1, "  found atomic value %s\n", get_entity_name(ent)));
				else {
					panic("Neither an array nor a struct or atomic value found in scalar replace");
Michael Beck's avatar
Michael Beck committed
744
				}
745
#endif /* DEBUG_libfirm */
Michael Beck's avatar
Michael Beck committed
746
747
748
749
750

				nvals = allocate_value_numbers(sels, ent, nvals, &modes);
			}
		}

751
		DB((dbg, SET_LEVEL_1, "  %u values will be needed\n", nvals));
Michael Beck's avatar
Michael Beck committed
752
753

		/* If scalars were found. */
754
		if (nvals > 0) {
755
			do_scalar_replacements(irg, sels, nvals, modes);
Michael Beck's avatar
Michael Beck committed
756

757
			foreach_set(set_ent, scalars_t*, value) {
758
				free_entity(value->ent);
Michael Beck's avatar
Michael Beck committed
759
760
761
762
763
764
765
766
767
			}

			/*
			 * We changed the graph, but did NOT introduce new blocks
			 * neither changed control flow, cf-backedges should be still
			 * consistent.
			 */
			set_irg_outs_inconsistent(irg);
			set_irg_loopinfo_inconsistent(irg);
768

Michael Beck's avatar
Michael Beck committed
769
			res = 1;
Michael Beck's avatar
Michael Beck committed
770
		}
771
772
773
		del_pset(sels);
		del_set(set_ent);
		DEL_ARR_F(modes);
Michael Beck's avatar
Michael Beck committed
774
775
	}

776
777
778
	ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
	irp_free_resources(irp, IR_RESOURCE_ENTITY_LINK);

779
	return res;
Michael Beck's avatar
Michael Beck committed
780
}
781

782
783
ir_graph_pass_t *scalar_replacement_opt_pass(const char *name)
{
784
785
	return def_graph_pass_ret(name ? name : "scalar_rep",
	                          scalar_replacement_opt);
786
787
}

788
789
void firm_init_scalar_replace(void)
{
790
791
	FIRM_DBG_REGISTER(dbg, "firm.opt.scalar_replace");
}