ircons.c 32 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 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.
 */

Matthias Braun's avatar
Matthias Braun committed
20
21
22
23
24
/**
 * @file
 * @brief   Various irnode constructors. Automatic construction of SSA
 *          representation.
 * @author  Martin Trapp, Christian Schaefer, Goetz Lindenmaier, Boris Boesler
25
 *          Michael Beck, Matthias Braun
Matthias Braun's avatar
Matthias Braun committed
26
 * @version $Id$
Götz Lindenmaier's avatar
Götz Lindenmaier committed
27
 */
Matthias Braun's avatar
Matthias Braun committed
28
#include "config.h"
Michael Beck's avatar
Michael Beck committed
29

30
31
32
33
34
#include "irprog_t.h"
#include "irgraph_t.h"
#include "irnode_t.h"
#include "irmode_t.h"
#include "ircons_t.h"
35
#include "irverify.h"
36
37
38
#include "irop_t.h"
#include "iropt_t.h"
#include "irgmod.h"
39
#include "irhooks.h"
40
#include "array_t.h"
41
42
43
44
#include "irbackedge_t.h"
#include "irflag_t.h"
#include "iredges_t.h"
#include "irflag_t.h"
45
#include "error.h"
46

47
#include "gen_ir_cons.c.inl"
48

Michael Beck's avatar
Michael Beck committed
49
50
/**
 * Language dependent variable initialization callback.
51
 */
52
static uninitialized_local_variable_func_t *default_initialize_local_variable = NULL;
53

54
ir_node *new_rd_Start(dbg_info *db, ir_graph *irg)
55
{
56
57
	ir_node  *block = get_irg_start_block(irg);
	ir_node  *res   = new_ir_node(db, irg, block, op_Start, mode_T, 0, NULL);
Christian Schäfer's avatar
Christian Schäfer committed
58

59
60
	res = optimize_node(res);
	irn_verify_irg(res, irg);
61
	return res;
62
}
Christian Schäfer's avatar
Christian Schäfer committed
63

64
ir_node *new_rd_End(dbg_info *db, ir_graph *irg)
65
{
66
67
	ir_node  *block = get_irg_end_block(irg);
	ir_node  *res   = new_ir_node(db, irg, block, op_End, mode_X, -1, NULL);
Christian Schäfer's avatar
Christian Schäfer committed
68

69
70
	res = optimize_node(res);
	irn_verify_irg(res, irg);
71
	return res;
72
}
Christian Schäfer's avatar
Christian Schäfer committed
73

Michael Beck's avatar
Michael Beck committed
74
75
76
77
/**
 * Creates a Phi node with all predecessors.  Calling this constructor
 * is only allowed if the corresponding block is mature.
 */
78
79
ir_node *new_rd_Phi(dbg_info *db, ir_node *block, int arity, ir_node **in,
                    ir_mode *mode)
80
{
81
	ir_graph *irg = get_irn_irg(block);
82
	ir_node  *res = new_ir_node(db, irg, block, op_Phi, mode, arity, in);
83
	res->attr.phi.u.backedge = new_backedge_arr(irg->obst, arity);
84

85
86
	res = optimize_node(res);
	irn_verify_irg(res, irg);
87
88
89

	/* Memory Phis in endless loops must be kept alive.
	   As we can't distinguish these easily we keep all of them alive. */
Michael Beck's avatar
Michael Beck committed
90
	if (is_Phi(res) && mode == mode_M)
91
92
		add_End_keepalive(get_irg_end(irg), res);
	return res;
93
}
Christian Schäfer's avatar
Christian Schäfer committed
94

95
96
ir_node *new_rd_Const_type(dbg_info *db, ir_graph *irg, tarval *con,
                           ir_type *tp)
97
{
98
99
100
	ir_node  *block = get_irg_start_block(irg);
	ir_mode  *mode  = get_tarval_mode(con);
	ir_node  *res   = new_ir_node(db, irg, block, op_Const, mode, 0, NULL);
101
	res->attr.con.tarval = con;
102
103
104
	set_Const_type(res, tp);  /* Call method because of complex assertion. */
	res = optimize_node (res);
	assert(get_Const_type(res) == tp);
105
	irn_verify_irg(res, irg);
106
107

	return res;
108
}
Christian Schäfer's avatar
Christian Schäfer committed
109

110
ir_node *new_rd_Const(dbg_info *db, ir_graph *irg, tarval *con)
111
{
112
	return new_rd_Const_type(db, irg, con, firm_unknown_type);
113
}
114

115
116
ir_node *new_rd_Const_long(dbg_info *db, ir_graph *irg, ir_mode *mode,
                           long value)
117
{
118
	return new_rd_Const(db, irg, new_tarval_from_long(value, mode));
119
}
120

121
ir_node *new_rd_defaultProj(dbg_info *db, ir_node *arg, long max_proj)
122
{
123
	ir_node *res;
124

125
	assert(is_Cond(arg));
126
	arg->attr.cond.default_proj = max_proj;
127
	res = new_rd_Proj(db, arg, mode_X, max_proj);
128
	return res;
129
}
Christian Schäfer's avatar
Christian Schäfer committed
130

131
132
133
ir_node *new_rd_SymConst_type(dbg_info *db, ir_graph *irg, ir_mode *mode,
                              symconst_symbol value, symconst_kind symkind,
                              ir_type *tp)
134
{
135
136
	ir_node *block = get_irg_start_block(irg);
	ir_node *res   = new_ir_node(db, irg, block, op_SymConst, mode, 0, NULL);
Christian Schäfer's avatar
Christian Schäfer committed
137

138
139
140
	res->attr.symc.kind = symkind;
	res->attr.symc.sym  = value;
	res->attr.symc.tp   = tp;
Beyhan's avatar
Beyhan committed
141

142
	res = optimize_node(res);
143
	irn_verify_irg(res, irg);
144
	return res;
145
}
Christian Schäfer's avatar
Christian Schäfer committed
146

147
ir_node *new_rd_Sync(dbg_info *db, ir_node *block, int arity, ir_node *in[])
148
{
149
	ir_graph *irg = get_irn_irg(block);
150
151
	ir_node  *res = new_ir_node(db, irg, block, op_Sync, mode_M, -1, NULL);
	int       i;
152

153
154
155
156
157
	for (i = 0; i < arity; ++i)
		add_Sync_pred(res, in[i]);

	res = optimize_node(res);
	irn_verify_irg(res, irg);
158
	return res;
159
}
Christian Schäfer's avatar
Christian Schäfer committed
160

161
162
163
164
ir_node *new_rd_ASM(dbg_info *db, ir_node *block, int arity, ir_node *in[],
                    ir_asm_constraint *inputs, int n_outs,
	                ir_asm_constraint *outputs, int n_clobber,
	                ident *clobber[], ident *text)
165
{
166
	ir_graph *irg = get_irn_irg(block);
167
	ir_node  *res = new_ir_node(db, irg, block, op_ASM, mode_T, arity, in);
168

169
	res->attr.assem.pin_state = op_pin_state_pinned;
170
171
172
173
174
175
	res->attr.assem.input_constraints
		= NEW_ARR_D(ir_asm_constraint, irg->obst, arity);
	res->attr.assem.output_constraints
		= NEW_ARR_D(ir_asm_constraint, irg->obst, n_outs);
	res->attr.assem.clobbers = NEW_ARR_D(ident *, irg->obst, n_clobber);
	res->attr.assem.text     = text;
176

177
178
179
	memcpy(res->attr.assem.input_constraints,  inputs,  sizeof(inputs[0]) * arity);
	memcpy(res->attr.assem.output_constraints, outputs, sizeof(outputs[0]) * n_outs);
	memcpy(res->attr.assem.clobbers, clobber, sizeof(clobber[0]) * n_clobber);
180

181
	res = optimize_node(res);
182
	irn_verify_irg(res, irg);
183
	return res;
184
}
185

186
187
188
ir_node *new_rd_simpleSel(dbg_info *db, ir_node *block, ir_node *store,
                          ir_node *objptr, ir_entity *ent)
{
189
190
	return new_rd_Sel(db, block, store, objptr, 0, NULL, ent);
}
Michael Beck's avatar
BugFix:    
Michael Beck committed
191

192
193
194
ir_node *new_rd_SymConst(dbg_info *db, ir_graph *irg, ir_mode *mode,
                         symconst_symbol value, symconst_kind symkind)
{
195
	return new_rd_SymConst_type(db, irg, mode, value, symkind, firm_unknown_type);
196
}
Michael Beck's avatar
BugFix:    
Michael Beck committed
197

198
199
ir_node *new_rd_SymConst_addr_ent(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_entity *symbol, ir_type *tp)
{
200
201
	symconst_symbol sym;
	sym.entity_p = symbol;
202
	return new_rd_SymConst_type(db, irg, mode, sym, symconst_addr_ent, tp);
203
}
Michael Beck's avatar
BugFix:    
Michael Beck committed
204

205
206
ir_node *new_rd_SymConst_ofs_ent(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_entity *symbol, ir_type *tp)
{
207
208
	symconst_symbol sym;
	sym.entity_p = symbol;
209
	return new_rd_SymConst_type(db, irg, mode, sym, symconst_ofs_ent, tp);
210
}
211

212
213
ir_node *new_rd_SymConst_type_tag(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_type *symbol, ir_type *tp)
{
214
215
	symconst_symbol sym;
	sym.type_p = symbol;
216
	return new_rd_SymConst_type(db, irg, mode, sym, symconst_type_tag, tp);
217
}
Michael Beck's avatar
BugFix:    
Michael Beck committed
218

219
220
ir_node *new_rd_SymConst_size(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_type *symbol, ir_type *tp)
{
221
222
	symconst_symbol sym;
	sym.type_p = symbol;
223
	return new_rd_SymConst_type(db, irg, mode, sym, symconst_type_size, tp);
224
}
225

226
227
ir_node *new_rd_SymConst_align(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_type *symbol, ir_type *tp)
{
228
229
	symconst_symbol sym;
	sym.type_p = symbol;
230
	return new_rd_SymConst_type(db, irg, mode, sym, symconst_type_align, tp);
231
}
Michael Beck's avatar
Michael Beck committed
232

233
ir_node *new_r_Start(ir_graph *irg)
234
{
235
	return new_rd_Start(NULL, irg);
236
}
237
ir_node *new_r_End(ir_graph *irg)
238
{
239
	return new_rd_End(NULL, irg);
240
}
241
242
ir_node *new_r_Const(ir_graph *irg, tarval *con)
{
243
	return new_rd_Const(NULL, irg, con);
244
}
245
246
ir_node *new_r_Const_long(ir_graph *irg, ir_mode *mode, long value)
{
247
	return new_rd_Const_long(NULL, irg, mode, value);
248
}
249
250
ir_node *new_r_Const_type(ir_graph *irg, tarval *con, ir_type *tp)
{
251
	return new_rd_Const_type(NULL, irg, con, tp);
252
}
253
254
255
ir_node *new_r_SymConst(ir_graph *irg, ir_mode *mode, symconst_symbol value,
                        symconst_kind symkind)
{
256
	return new_rd_SymConst(NULL, irg, mode, value, symkind);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
257
}
258
259
260
ir_node *new_r_simpleSel(ir_node *block, ir_node *store, ir_node *objptr,
                         ir_entity *ent)
{
261
	return new_rd_Sel(NULL, block, store, objptr, 0, NULL, ent);
262
}
263
264
ir_node *new_r_Phi(ir_node *block, int arity, ir_node **in, ir_mode *mode)
{
265
	return new_rd_Phi(NULL, block, arity, in, mode);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
266
}
267
268
ir_node *new_r_Sync(ir_node *block, int arity, ir_node *in[])
{
269
	return new_rd_Sync(NULL, block, arity, in);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
270
}
271
ir_node *new_r_defaultProj(ir_node *arg, long max_proj)
272
{
273
	return new_rd_defaultProj(NULL, arg, max_proj);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
274
}
275
276
ir_node *new_r_Bad(ir_graph *irg)
{
277
	return get_irg_bad(irg);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
278
}
279
280
ir_node *new_r_NoMem(ir_graph *irg)
{
281
	return get_irg_no_mem(irg);
282
}
283
ir_node *new_r_ASM(ir_node *block,
Michael Beck's avatar
Michael Beck committed
284
                   int arity, ir_node *in[], ir_asm_constraint *inputs,
Michael Beck's avatar
Michael Beck committed
285
                   int n_outs, ir_asm_constraint *outputs,
286
                   int n_clobber, ident *clobber[], ident *text)
287
{
288
	return new_rd_ASM(NULL, block, arity, in, inputs, n_outs, outputs, n_clobber, clobber, text);
Michael Beck's avatar
Michael Beck committed
289
}
Michael Beck's avatar
Michael Beck committed
290

Boris Boesler's avatar
Boris Boesler committed
291
/** ********************/
Christian Schäfer's avatar
Christian Schäfer committed
292
293
294
/** public interfaces  */
/** construction tools */

295
ir_node *new_d_Start(dbg_info *db)
296
{
297
298
	ir_node *res;

299
	assert(get_irg_phase_state(current_ir_graph) == phase_building);
300
301
302
303
	res = new_ir_node(db, current_ir_graph, current_ir_graph->current_block,
	                  op_Start, mode_T, 0, NULL);

	res = optimize_node(res);
304
	irn_verify_irg(res, current_ir_graph);
305
	return res;
306
}
307

308
ir_node *new_d_End(dbg_info *db)
309
{
310
	ir_node *res;
311
	assert(get_irg_phase_state(current_ir_graph) == phase_building);
312
313
314
	res = new_ir_node(db, current_ir_graph,  current_ir_graph->current_block,
	                  op_End, mode_X, -1, NULL);
	res = optimize_node(res);
315
	irn_verify_irg(res, current_ir_graph);
316
317

	return res;
318
}
319

Boris Boesler's avatar
Boris Boesler committed
320
/* ***********************************************************************/
Götz Lindenmaier's avatar
Götz Lindenmaier committed
321
322
323
324
/* Methods necessary for automatic Phi node creation                     */
/*
  ir_node *phi_merge            (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
  ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
Michael Beck's avatar
Michael Beck committed
325
326
  ir_node *new_rd_Phi0          (ir_graph *irg, ir_node *block, ir_mode *mode)
  ir_node *new_rd_Phi_in        (ir_graph *irg, ir_node *block, ir_mode *mode, ir_node **in, int ins)
Götz Lindenmaier's avatar
Götz Lindenmaier committed
327
328
329

  Call Graph:   ( A ---> B == A "calls" B)

330
       get_value         mature_immBlock
Götz Lindenmaier's avatar
Götz Lindenmaier committed
331
332
333
334
335
336
337
338
339
          |                   |
          |                   |
          |                   |
          |          ---> phi_merge
          |         /       /   \
          |        /       /     \
         \|/      /      |/_      \
       get_r_value_internal        |
                |                  |
340
341
342
                |                  |
               \|/                \|/
           new_rd_Phi0          new_rd_Phi_in
Götz Lindenmaier's avatar
Götz Lindenmaier committed
343

Boris Boesler's avatar
Boris Boesler committed
344
* *************************************************************************** */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
345

Michael Beck's avatar
Michael Beck committed
346
/** Creates a Phi node with 0 predecessors. */
347
static inline ir_node *new_rd_Phi0(ir_node *block, ir_mode *mode)
348
{
349
350
351
	ir_graph *irg = get_irn_irg(block);
	ir_node  *res = new_ir_node(NULL, irg, block, op_Phi, mode, 0, NULL);
	irn_verify_irg(res, irg);
352
	return res;
353
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
354

Michael Beck's avatar
Michael Beck committed
355
356
357
358
359
360
/**
 * Internal constructor of a Phi node by a phi_merge operation.
 *
 * @param block  the block in which the Phi will be constructed
 * @param mode   the mod eof the Phi node
 * @param in     the input array of the phi node
361
 * @param n_in   number of elements in the input array
Michael Beck's avatar
Michael Beck committed
362
363
364
 * @param phi0   in non-NULL: the Phi0 node in the same block that represents
 *               the value for which the new Phi is constructed
 */
365
366
static ir_node *new_rd_Phi_in(ir_node *block, ir_mode *mode,
                              int n_in, ir_node **in, ir_node *phi0)
367
{
368
369
	int i;
	ir_node *res, *known;
370
	ir_graph *irg = get_irn_irg(block);
371
372
373

	/* Allocate a new node on the obstack.  The allocation copies the in
	   array. */
374
375
	res = new_ir_node(NULL, irg, block, op_Phi, mode, n_in, in);
	res->attr.phi.u.backedge = new_backedge_arr(irg->obst, n_in);
376
377
378
379

	/* This loop checks whether the Phi has more than one predecessor.
	   If so, it is a real Phi node and we break the loop.  Else the
	   Phi node merges the same definition on several paths and therefore
380
381
	   is not needed.
	   Note: We MUST consider Bad nodes, else we might get data flow cycles in dead loops! */
382
	known = res;
383
	for (i = n_in - 1; i >= 0; --i) {
384
385
386
387
388
389
		assert(in[i]);

		in[i] = skip_Id(in[i]);  /* increases the number of freed Phis. */

		/* Optimize self referencing Phis:  We can't detect them yet properly, as
		they still refer to the Phi0 they will replace.  So replace right now. */
Michael Beck's avatar
Michael Beck committed
390
391
		if (phi0 && in[i] == phi0)
			in[i] = res;
392

393
		if (in[i] == res || in[i] == known)
Michael Beck's avatar
Michael Beck committed
394
			continue;
395

Michael Beck's avatar
Michael Beck committed
396
		if (known == res)
397
398
399
400
401
			known = in[i];
		else
			break;
	}

Michael Beck's avatar
Michael Beck committed
402
403
	/* i < 0: there is at most one predecessor, we don't need a phi node. */
	if (i < 0) {
404
405
		if (res != known) {
			edges_node_deleted(res, current_ir_graph);
Michael Beck's avatar
Michael Beck committed
406
			obstack_free(current_ir_graph->obst, res);
407
408
409
410
411
412
413
414
415
416
417
			if (is_Phi(known)) {
				/* If pred is a phi node we want to optimize it: If loops are matured in a bad
				   order, an enclosing Phi know may get superfluous. */
				res = optimize_in_place_2(known);
				if (res != known)
					exchange(known, res);
			}
			else
				res = known;
		} else {
			/* A undefined value, e.g., in unreachable code. */
418
			res = new_r_Bad(irg);
419
420
		}
	} else {
Michael Beck's avatar
Michael Beck committed
421
		res = optimize_node(res);  /* This is necessary to add the node to the hash table for cse. */
422
		irn_verify_irg(res, irg);
423
424
		/* Memory Phis in endless loops must be kept alive.
		   As we can't distinguish these easily we keep all of them alive. */
Michael Beck's avatar
Michael Beck committed
425
		if (is_Phi(res) && mode == mode_M)
426
427
428
429
			add_End_keepalive(get_irg_end(irg), res);
	}

	return res;
430
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
431

432
static ir_node *get_r_value_internal(ir_node *block, int pos, ir_mode *mode);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
433

Sebastian Felis's avatar
Sebastian Felis committed
434
/**
Michael Beck's avatar
Michael Beck committed
435
436
437
438
439
 * Computes the predecessors for the real phi node, and then
 * allocates and returns this node.  The routine called to allocate the
 * node might optimize it away and return a real value.
 * This function must be called with an in-array of proper size.
 */
440
441
static ir_node *phi_merge(ir_node *block, int pos, ir_mode *mode,
                          int n_ins, ir_node **ins)
442
{
443
	ir_graph *irg = get_irn_irg(block);
444
	ir_node *prevBlock, *res, *phi0, *phi0_all;
445
446
447
448
449
450
	int i;

	/* If this block has no value at pos create a Phi0 and remember it
	   in graph_arr to break recursions.
	   Else we may not set graph_arr as there a later value is remembered. */
	phi0 = NULL;
Michael Beck's avatar
Michael Beck committed
451
452
453
	if (block->attr.block.graph_arr[pos] == NULL) {

		if (block == get_irg_start_block(irg)) {
454
455
456
457
458
459
460
461
462
463
464
			/* Collapsing to Bad tarvals is no good idea.
			   So we call a user-supplied routine here that deals with this
			   case as appropriate for the given language. Sorrily the only
			   help we can give here is the position.

			   Even if all variables are defined before use, it can happen that
			   we get to the start block, if a Cond has been replaced by a tuple
			   (bad, jmp).  In this case we call the function needlessly,
			   eventually generating an non existent error.
			   However, this SHOULD NOT HAPPEN, as bad control flow nodes are
			   intercepted before recurring.
465
			 */
Michael Beck's avatar
Michael Beck committed
466
			if (default_initialize_local_variable != NULL) {
467
				ir_node *rem = get_r_cur_block(irg);
468

469
				set_r_cur_block(irg, block);
Michael Beck's avatar
Michael Beck committed
470
				block->attr.block.graph_arr[pos] = default_initialize_local_variable(irg, mode, pos - 1);
471
				set_r_cur_block(irg, rem);
472
			} else {
473
				block->attr.block.graph_arr[pos] = new_r_Unknown(irg, mode);
474
			}
475
476
			return block->attr.block.graph_arr[pos];
		} else {
477
			phi0 = new_rd_Phi0(block, mode);
478
479
480
481
482
483
484
			block->attr.block.graph_arr[pos] = phi0;
		}
	}

	/* This loop goes to all predecessor blocks of the block the Phi node
	   is in and there finds the operands of the Phi node by calling
	   get_r_value_internal.  */
485
	for (i = 1; i <= n_ins; ++i) {
486
487
488
		ir_node *cf_pred = block->in[i];
		ir_node *prevCfOp = skip_Proj(cf_pred);
		assert(prevCfOp);
489
490
491
		if (is_Bad(prevCfOp)) {
			/* In case a Cond has been optimized we would get right to the start block
			with an invalid definition. */
492
			ins[i-1] = new_r_Bad(irg);
493
494
			continue;
		}
495
496
		prevBlock = prevCfOp->in[0]; /* go past control flow op to prev block */
		assert(prevBlock);
497
		if (!is_Bad(prevBlock)) {
498
			ins[i-1] = get_r_value_internal(prevBlock, pos, mode);
499
		} else {
500
			ins[i-1] = new_r_Bad(irg);
501
502
503
504
505
506
		}
	}

	/* We want to pass the Phi0 node to the constructor: this finds additional
	   optimization possibilities.
	   The Phi0 node either is allocated in this function, or it comes from
Michael Beck's avatar
Michael Beck committed
507
508
509
	   a former call to get_r_value_internal(). In this case we may not yet
	   exchange phi0, as this is done in mature_immBlock(). */
	if (phi0 == NULL) {
510
		phi0_all = block->attr.block.graph_arr[pos];
511
512
513
		if (! is_Phi0(phi0_all)            ||
		    get_irn_arity(phi0_all) != 0   ||
		    get_nodes_block(phi0_all) != block)
514
515
516
517
518
			phi0_all = NULL;
	} else {
		phi0_all = phi0;
	}

519
	/* After collecting all predecessors into the array ins a new Phi node
520
521
522
	   with these predecessors is created.  This constructor contains an
	   optimization: If all predecessors of the Phi node are identical it
	   returns the only operand instead of a new Phi node.  */
523
	res = new_rd_Phi_in(block, mode, n_ins, ins, phi0_all);
524
525
526

	/* In case we allocated a Phi0 node at the beginning of this procedure,
	   we need to exchange this Phi0 with the real Phi. */
Michael Beck's avatar
Michael Beck committed
527
	if (phi0 != NULL) {
528
529
530
531
532
		exchange(phi0, res);
		block->attr.block.graph_arr[pos] = res;
	}

	return res;
533
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
534

Michael Beck's avatar
Michael Beck committed
535
/**
536
537
 * This function returns the last definition of a value.  In case
 * this value was last defined in a previous block, Phi nodes are
Michael Beck's avatar
Michael Beck committed
538
539
 * inserted.  If the part of the firm graph containing the definition
 * is not yet constructed, a dummy Phi node is returned.
540
541
542
543
 *
 * @param block   the current block
 * @param pos     the value number of the value searched
 * @param mode    the mode of this value (needed for Phi construction)
Michael Beck's avatar
Michael Beck committed
544
 */
545
static ir_node *get_r_value_internal(ir_node *block, int pos, ir_mode *mode)
546
{
547
548
549
550
551
	ir_node *res;
	/* There are 4 cases to treat.

	   1. The block is not mature and we visit it the first time.  We can not
	      create a proper Phi node, therefore a Phi0, i.e., a Phi without
Michael Beck's avatar
Michael Beck committed
552
553
	      predecessors is returned.  This node is added to the linked list (block
	      attribute "phis") of the containing block to be completed when this block is
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
	      matured. (Completion will add a new Phi and turn the Phi0 into an Id
	      node.)

	   2. The value is already known in this block, graph_arr[pos] is set and we
	      visit the block the first time.  We can return the value without
	      creating any new nodes.

	   3. The block is mature and we visit it the first time.  A Phi node needs
	      to be created (phi_merge).  If the Phi is not needed, as all it's
	      operands are the same value reaching the block through different
	      paths, it's optimized away and the value itself is returned.

	   4. The block is mature, and we visit it the second time.  Now two
	      subcases are possible:
	      * The value was computed completely the last time we were here. This
	        is the case if there is no loop.  We can return the proper value.
	      * The recursion that visited this node and set the flag did not
	        return yet.  We are computing a value in a loop and need to
	        break the recursion.  This case only happens if we visited
	    the same block with phi_merge before, which inserted a Phi0.
	    So we return the Phi0.
	*/

	/* case 4 -- already visited. */
578
	if (irn_visited(block)) {
579
580
581
582
583
584
585
		/* As phi_merge allocates a Phi0 this value is always defined. Here
		is the critical difference of the two algorithms. */
		assert(block->attr.block.graph_arr[pos]);
		return block->attr.block.graph_arr[pos];
	}

	/* visited the first time */
586
	mark_irn_visited(block);
587
588
589
590
591

	/* Get the local valid value */
	res = block->attr.block.graph_arr[pos];

	/* case 2 -- If the value is actually computed, return it. */
Michael Beck's avatar
Michael Beck committed
592
593
	if (res != NULL)
		return res;
594

Michael Beck's avatar
Michael Beck committed
595
	if (block->attr.block.is_matured) { /* case 3 */
596
597

		/* The Phi has the same amount of ins as the corresponding block. */
598
599
600
		int n_in = get_irn_arity(block);
		ir_node **in;
		NEW_ARR_A(ir_node *, in, n_in);
601
602

		/* Phi merge collects the predecessors and then creates a node. */
603
		res = phi_merge(block, pos, mode, n_in, in);
604
605
606
607
608
609
610
611
	} else {  /* case 1 */
		/* The block is not mature, we don't know how many in's are needed.  A Phi
		   with zero predecessors is created.  Such a Phi node is called Phi0
		   node.  The Phi0 is then added to the list of Phi0 nodes in this block
		   to be matured by mature_immBlock later.
		   The Phi0 has to remember the pos of it's internal value.  If the real
		   Phi is computed, pos is used to update the array with the local
		   values. */
612
		res = new_rd_Phi0(block, mode);
613
614
615
		res->attr.phi.u.pos    = pos;
		res->attr.phi.next     = block->attr.block.phis;
		block->attr.block.phis = res;
616
617
	}

Michael Beck's avatar
Michael Beck committed
618
	assert(is_ir_node(res) && "phi_merge() failed to construct a definition");
619
620
621
622
623

	/* The local valid value is available now. */
	block->attr.block.graph_arr[pos] = res;

	return res;
624
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
625

Boris Boesler's avatar
Boris Boesler committed
626
/* ************************************************************************** */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
627

Michael Beck's avatar
Michael Beck committed
628
629
630
631
/*
 * Finalize a Block node, when all control flows are known.
 * Acceptable parameters are only Block nodes.
 */
632
void mature_immBlock(ir_node *block)
633
{
634
635
636
637
	int ins;
	ir_node *n, **nin;
	ir_node *next;

638
	assert(is_Block(block));
639
	if (!get_Block_matured(block)) {
Michael Beck's avatar
Michael Beck committed
640
641
642
		ir_graph *irg = current_ir_graph;

		ins = ARR_LEN(block->in) - 1;
643
		/* Fix block parameters */
Michael Beck's avatar
Michael Beck committed
644
		block->attr.block.backedge = new_backedge_arr(irg->obst, ins);
645
646

		/* An array for building the Phi nodes. */
647
		NEW_ARR_A(ir_node *, nin, ins);
648
649
650

		/* Traverse a chain of Phi nodes attached to this block and mature
		these, too. **/
651
		for (n = block->attr.block.phis; n; n = next) {
Michael Beck's avatar
Michael Beck committed
652
			inc_irg_visited(irg);
653
			next = n->attr.phi.next;
654
			exchange(n, phi_merge(block, n->attr.phi.u.pos, n->mode, ins, nin));
655
656
		}

Michael Beck's avatar
Michael Beck committed
657
		block->attr.block.is_matured = 1;
658

Michael Beck's avatar
Michael Beck committed
659
		/* Now, as the block is a finished Firm node, we can optimize it.
660
661
		   Since other nodes have been allocated since the block was created
		   we can not free the node on the obstack.  Therefore we have to call
Michael Beck's avatar
Michael Beck committed
662
		   optimize_in_place().
663
664
		   Unfortunately the optimization does not change a lot, as all allocated
		   nodes refer to the unoptimized node.
Michael Beck's avatar
Michael Beck committed
665
		   We can call optimize_in_place_2(), as global cse has no effect on blocks. */
666
		block = optimize_in_place_2(block);
667
		irn_verify_irg(block, irg);
668
	}
669
}
Christian Schäfer's avatar
Christian Schäfer committed
670

671
ir_node *new_d_Phi(dbg_info *db, int arity, ir_node **in, ir_mode *mode)
672
{
673
	assert(get_irg_phase_state(current_ir_graph) == phase_building);
674
675
	return new_rd_Phi(db, current_ir_graph->current_block, arity, in, mode);
}
Christian Schäfer's avatar
Christian Schäfer committed
676

677
ir_node *new_d_Const(dbg_info *db, tarval *con)
678
{
679
	assert(get_irg_phase_state(current_ir_graph) == phase_building);
680
681
	return new_rd_Const(db, current_ir_graph, con);
}
Christian Schäfer's avatar
Christian Schäfer committed
682

683
ir_node *new_d_Const_long(dbg_info *db, ir_mode *mode, long value)
684
{
685
	assert(get_irg_phase_state(current_ir_graph) == phase_building);
686
687
	return new_rd_Const_long(db, current_ir_graph, mode, value);
}
688

689
ir_node *new_d_Const_type(dbg_info *db, tarval *con, ir_type *tp)
690
{
691
	assert(get_irg_phase_state(current_ir_graph) == phase_building);
692
693
	return new_rd_Const_type(db, current_ir_graph, con, tp);
}
694

695
ir_node *new_d_defaultProj(dbg_info *db, ir_node *arg, long max_proj)
696
{
697
	ir_node *res;
698
	assert(is_Cond(arg));
699
	assert(get_irg_phase_state(current_ir_graph) == phase_building);
700
	arg->attr.cond.default_proj = max_proj;
701
	res = new_d_Proj(db, arg, mode_X, max_proj);
702
	return res;
703
}
704

705
706
ir_node *new_d_simpleSel(dbg_info *db, ir_node *store, ir_node *objptr,
                         ir_entity *ent)
Christian Schäfer's avatar
Christian Schäfer committed
707
{
708
	assert(get_irg_phase_state(current_ir_graph) == phase_building);
709
	return new_rd_Sel(db, current_ir_graph->current_block,
710
	                  store, objptr, 0, NULL, ent);
711
}
Christian Schäfer's avatar
Christian Schäfer committed
712

713
714
ir_node *new_d_SymConst_type(dbg_info *db, ir_mode *mode, symconst_symbol value,
                             symconst_kind kind, ir_type *tp)
715
{
716
	assert(get_irg_phase_state(current_ir_graph) == phase_building);
717
718
	return new_rd_SymConst_type(db, current_ir_graph, mode, value, kind, tp);
}
Beyhan's avatar
Beyhan committed
719

720
721
ir_node *new_d_SymConst(dbg_info *db, ir_mode *mode, symconst_symbol value,
                        symconst_kind kind)
722
{
723
	assert(get_irg_phase_state(current_ir_graph) == phase_building);
724
725
726
	return new_rd_SymConst_type(db, current_ir_graph, mode, value, kind,
	                            firm_unknown_type);
}
Christian Schäfer's avatar
Christian Schäfer committed
727

728
ir_node *new_d_Sync(dbg_info *db, int arity, ir_node *in[])
729
{
730
	assert(get_irg_phase_state(current_ir_graph) == phase_building);
731
	return new_rd_Sync(db, current_ir_graph->current_block, arity, in);
732
}
Christian Schäfer's avatar
Christian Schäfer committed
733

734
735
ir_node *new_d_ASM(dbg_info *db, int arity, ir_node *in[],
                   ir_asm_constraint *inputs,
736
                   int n_outs, ir_asm_constraint *outputs, int n_clobber,
737
                   ident *clobber[], ident *text)
738
{
739
	assert(get_irg_phase_state(current_ir_graph) == phase_building);
740
741
742
	return new_rd_ASM(db, current_ir_graph->current_block, arity, in, inputs,
	                  n_outs, outputs, n_clobber, clobber, text);
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
743

744
ir_node *new_rd_immBlock(dbg_info *dbgi, ir_graph *irg)
745
{
746
747
	ir_node *res;

748
	assert(get_irg_phase_state(irg) == phase_building);
749
	/* creates a new dynamic in-array as length of in is -1 */
750
	res = new_ir_node(dbgi, irg, NULL, op_Block, mode_BB, -1, NULL);
Michael Beck's avatar
Michael Beck committed
751
752
753

	res->attr.block.is_matured  = 0;
	res->attr.block.is_dead     = 0;
754
	res->attr.block.irg.irg     = irg;
755
756
757
758
759
	res->attr.block.backedge    = NULL;
	res->attr.block.in_cg       = NULL;
	res->attr.block.cg_backedge = NULL;
	res->attr.block.extblk      = NULL;
	res->attr.block.region      = NULL;
760
	res->attr.block.entity      = NULL;
Michael Beck's avatar
Michael Beck committed
761

762
763
764
	set_Block_block_visited(res, 0);

	/* Create and initialize array for Phi-node construction. */
765
766
	res->attr.block.graph_arr = NEW_ARR_D(ir_node *, irg->obst, irg->n_loc);
	memset(res->attr.block.graph_arr, 0, sizeof(ir_node*) * irg->n_loc);
767
768

	/* Immature block may not be optimized! */
769
	irn_verify_irg(res, irg);
770
771

	return res;
772
773
774
775
776
777
778
779
780
781
782
}

ir_node *new_r_immBlock(ir_graph *irg)
{
	return new_rd_immBlock(NULL, irg);
}

ir_node *new_d_immBlock(dbg_info *dbgi)
{
	return new_rd_immBlock(dbgi, current_ir_graph);
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
783

784
ir_node *new_immBlock(void)
785
{
786
787
	return new_rd_immBlock(NULL, current_ir_graph);
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
788

789
void add_immBlock_pred(ir_node *block, ir_node *jmp)
790
{
Michael Beck's avatar
Michael Beck committed
791
792
	int n = ARR_LEN(block->in) - 1;

Andreas Zwinkau's avatar
Andreas Zwinkau committed
793
	assert(is_Block(block) && "Error: Must be a Block");
Michael Beck's avatar
Michael Beck committed
794
	assert(!block->attr.block.is_matured && "Error: Block already matured!\n");
795
	assert(is_ir_node(jmp));
Michael Beck's avatar
Michael Beck committed
796
797
798
799

	ARR_APP1(ir_node *, block->in, jmp);
	/* Call the hook */
	hook_set_irn_n(block, n, jmp, NULL);
800
}
Christian Schäfer's avatar
Christian Schäfer committed
801

802
void set_cur_block(ir_node *target)