2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
21 * Author: Daniel Grund
23 * Copyright: (c) Universitaet Karlsruhe
24 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
41 #include "irprintf_t.h"
43 #include "irgraph_t.h"
45 #include "iredges_t.h"
49 #include "beraextern.h"
54 #include "besched_t.h"
59 #include "bessadestrsimple.h"
63 typedef struct _ssa_destr_env_t {
65 const arch_register_class_t *cls;
66 const arch_env_t *aenv;
70 #define pset_foreach(pset, irn) for(irn=pset_first(pset); irn; irn=pset_next(pset))
71 #define set_foreach(set, e) for(e=set_first(set); e; e=set_next(set))
73 static phi_classes_t *pc = NULL;
75 /******************************************************************************
77 \ \ / / | | |__ \ \ \ / /
78 \ \ / /_ _| |___ ) | \ \ / /_ _ _ __ ___
79 \ \/ / _` | / __| / / \ \/ / _` | '__/ __|
80 \ / (_| | \__ \ / /_ \ / (_| | | \__ \
81 \/ \__,_|_|___/ |____| \/ \__,_|_| |___/
82 *****************************************************************************/
85 * The link field of an irn points to the var_info struct
86 * representing the corresponding variable.
88 #define set_var_info(irn, vi) set_irn_link(irn, vi)
90 #define HASH_VAR_NR(var_nr) var_nr
92 static int compare_var_infos(const void *e1, const void *e2, size_t size) {
93 const be_var_info_t *v1 = e1;
94 const be_var_info_t *v2 = e2;
96 if (v1->var_nr == SET_REMOVED || v2->var_nr == SET_REMOVED)
99 return v1->var_nr != v2->var_nr;
102 be_var_info_t *be_var_find(set *vars, int var_nr) {
106 return set_find(vars, &vi, sizeof(vi), HASH_VAR_NR(var_nr));
109 be_var_info_t *be_var_find_or_insert(set *vars, int var_nr) {
110 be_var_info_t vi, *found;
111 memset(&vi, 0, sizeof(vi));
114 found = set_insert(vars, &vi, sizeof(vi), HASH_VAR_NR(var_nr));
117 found->values = pset_new_ptr(1);
123 * Adds a value to a variable. Sets all pointers accordingly.
125 be_var_info_t *be_var_add_value(set *vars, int var_nr, ir_node *irn) {
126 be_var_info_t *vi = be_var_find_or_insert(vars, var_nr);
128 /* var 2 value mapping */
129 pset_insert_ptr(vi->values, irn);
131 /* value 2 var mapping */
132 set_var_info(irn, vi);
137 pset *be_get_var_values(set *vars, int var_nr) {
138 be_var_info_t *vi = be_var_find(vars, var_nr);
139 assert(vi && "Variable does not exist");
143 static INLINE ir_node *get_first_phi(ir_node **s) {
146 for (i = ARR_LEN(s) - 1; i >= 0; --i) {
151 assert(0 && "There must be a phi in this");
157 * Define variables (numbers) for all SSA-values.
158 * All values in a phi class get assigned the same variable name.
159 * The link field maps values to the var-name
161 static void values_to_vars(ir_node *irn, void *env) {
162 ssa_destr_env_t *sde = env;
163 int nr, i, build_vals = 0;
166 if (arch_get_irn_reg_class(sde->aenv, irn, -1) == NULL)
169 vals = get_phi_class(pc, irn);
172 nr = get_irn_node_nr(get_first_phi(vals));
174 /* not a phi class member, value == var */
175 nr = get_irn_node_nr(irn);
176 vals = NEW_ARR_F(ir_node *, 1);
181 /* values <--> var mapping */
182 for (i = ARR_LEN(vals) - 1; i >= 0; --i) {
183 be_var_add_value(sde->vars, nr, vals[i]);
190 /******************************************************************************
192 / ____/ ____| /\ | __ \ | |
193 | (___| (___ / \ ______| | | | ___ ___| |_ _ __
194 \___ \\___ \ / /\ \______| | | |/ _ \/ __| __| '__|
195 ____) |___) / ____ \ | |__| | __/\__ \ |_| |
196 |_____/_____/_/ \_\ |_____/ \___||___/\__|_|
198 *****************************************************************************/
200 #define mark_as_done(irn, pos) set_irn_link(irn, INT_TO_PTR(pos+1))
201 #define has_been_done(irn, pos) (PTR_TO_INT(get_irn_link(irn)) > pos)
204 * Insert a copy for the argument of @p start_phi found at position @p pos.
205 * Also searches a phi-loop of arbitrary length to detect and resolve
206 * the class of phi-swap-problems. To search for a loop recursion is used.
208 * 1) Simplest case (phi with a non-phi arg):
209 * A single copy is inserted.
211 * 2) Phi chain (phi (with phi-arg)* with non-phi arg):
212 * Several copies are placed, each after returning from recursion.
215 * On detection a loop breaker is inserted, which is a copy of the start_phi.
216 * This copy then pretends beeing the argumnent of the last phi.
217 * Now case 2) can be used.
219 * The values of @p start_phi and @p pos never change during recursion.
221 * @p start_phi Phi node to process
222 * @p pos Argument position to insert copy/copies for
223 * @p curr_phi Phi node currently processed during recursion. Equals start_phi on initial call
225 * @return NULL If no copy is necessary
226 * NULL If the phi has already been processed at this pos
227 * Link field is used to keep track of processed positions
228 * In all other cases the ir_node *copy which was placed is returned.
230 static ir_node *insert_copies(ssa_destr_env_t *sde, const arch_register_class_t *cls, ir_node *start_phi, int pos, ir_node *curr_phi) {
231 ir_node *arg = get_irn_n(curr_phi, pos);
232 ir_node *arg_blk = get_nodes_block(arg);
233 ir_node *pred_blk = get_Block_cfgpred_block(get_nodes_block(curr_phi), pos);
234 ir_node *curr_cpy, *last_cpy;
236 assert(is_Phi(start_phi) && is_Phi(curr_phi));
238 if (has_been_done(start_phi, pos))
241 /* In case this is a 'normal' phi we insert at the
242 * end of the pred block before cf nodes */
243 last_cpy = sched_skip(pred_blk, 0, sched_skip_cf_predicator, (void *)sde->aenv);
244 last_cpy = sched_next(last_cpy);
246 /* If we detect a loop stop recursion. */
247 if (arg == start_phi) {
248 ir_node *loop_breaker;
249 if (start_phi == curr_phi) {
250 /* Phi directly uses itself. No copy necessary */
254 /* At least 2 phis are involved */
255 /* Insert a loop breaking copy (an additional variable T) */
256 loop_breaker = be_new_Copy(cls, sde->irg, pred_blk, start_phi);
257 sched_add_before(last_cpy, loop_breaker);
262 /* If arg is a phi in the same block we have to continue search */
263 if (is_Phi(arg) && arg_blk == get_nodes_block(start_phi))
264 last_cpy = insert_copies(sde, cls, start_phi, pos, arg);
266 /* Insert copy of argument (may be the loop-breaker) */
267 curr_cpy = be_new_Copy(cls, sde->irg, pred_blk, arg);
268 set_irn_n(curr_phi, pos, curr_cpy);
269 mark_as_done(curr_phi, pos);
270 sched_add_before(last_cpy, curr_cpy);
276 * Perform simple SSA-destruction with copies.
277 * The order of processing _must_ be
278 * for all positions {
283 * else the magic to keep track of processed phi-positions will fail in
284 * function 'insert_copies'
286 static void ssa_destr_simple_walker(ir_node *blk, void *env) {
287 ssa_destr_env_t *sde = env;
290 const arch_register_class_t *cls;
292 /* for all argument positions of the phis */
293 for (pos=0, max=get_irn_arity(blk); pos<max; ++pos) {
295 /* for all phi nodes (which are scheduled first) */
296 sched_foreach(blk, phi) {
300 if (arch_irn_is(sde->aenv, phi, ignore))
303 cls = arch_get_irn_reg_class(sde->aenv, phi, -1);
304 insert_copies(sde, cls, phi, pos, phi);
310 set *be_ssa_destr_simple(ir_graph *irg, const arch_env_t *aenv) {
315 sde.vars = new_set(compare_var_infos, 16);
318 irg_block_walk_graph(irg, ssa_destr_simple_walker, NULL, &sde);
320 /* Mapping of SSA-Values <--> Variables */
321 pc = phi_class_new_from_irg(irg, 0);
323 irg_walk_graph(irg, values_to_vars, NULL, &sde);
328 void free_ssa_destr_simple(set *vars)
332 set_foreach(vars, vi)
333 del_pset(vi->values);