4 * Copyright: (c) Universitaet Karlsruhe
5 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
7 * Performs SSA-Destruction.
18 #include "iredges_t.h"
25 #include "bechordal_t.h"
29 #include "besched_t.h"
31 static firm_dbg_module_t *dbg = NULL;
34 #define get_chordal_arch(ce) ((ce)->main_env->arch_env)
35 #define get_reg(irn) arch_get_irn_register(get_chordal_arch(chordal_env), irn)
36 #define set_reg(irn, reg) arch_set_irn_register(get_chordal_arch(chordal_env), irn, reg)
38 #define is_Perm(irn) (arch_irn_classify(arch_env, irn) == arch_irn_class_perm)
39 #define get_reg_cls(irn) (arch_get_irn_reg_class(arch_env, irn, -1))
40 #define is_curr_reg_class(irn) (get_reg_cls(p) == chordal_env->cls)
42 static void clear_link(ir_node *irn, void *data)
44 set_irn_link(irn, NULL);
48 * Build a list of phis of a block.
50 static void collect_phis(ir_node *irn, void *data)
52 be_chordal_env_t *env = data;
53 if(is_Phi(irn) && chordal_has_class(env, irn)) {
54 ir_node *bl = get_nodes_block(irn);
55 set_irn_link(irn, get_irn_link(bl));
56 set_irn_link(bl, irn);
61 * Build a ring of phis for each block in the link field.
62 * @param env The chordal env.
64 static INLINE void build_phi_rings(be_chordal_env_t *env)
66 irg_walk_graph(env->irg, clear_link, collect_phis, env);
70 * This struct represents a Proj for a Perm.
71 * It records the argument in the Perm and the corresponding Proj of the
75 ir_node *arg; /**< The phi argument to make the Proj for. */
76 int pos; /**< The proj number the Proj will get.
77 This also denotes the position of @p arg
78 in the in array of the Perm. */
79 ir_node *proj; /**< The proj created for @p arg. */
82 static int cmp_perm_proj(const void *a, const void *b, size_t n)
84 const perm_proj_t *p = a;
85 const perm_proj_t *q = b;
86 return !(p->arg == q->arg);
89 static void insert_all_perms_walker(ir_node *bl, void *data)
91 be_chordal_env_t *chordal_env = data;
92 pmap *perm_map = chordal_env->data;
93 ir_graph *irg = chordal_env->irg;
94 const be_node_factory_t *fact = chordal_env->main_env->node_factory;
96 /* Dummy targets for the projs */
97 ir_node *dummy = new_rd_Unknown(irg, mode_T);
101 /* If the link flag is NULL, this block has no phis. */
102 if(get_irn_link(bl)) {
105 /* Look at all predecessors of the phi block */
106 for(i = 0, n = get_irn_arity(bl); i < n; ++i) {
107 ir_node *phi, *perm, *insert_after, **in;
110 set *arg_set = new_set(cmp_perm_proj, chordal_env->cls->n_regs);
111 ir_node *pred_bl = get_Block_cfgpred_block(bl, i);
114 assert(!pmap_contains(perm_map, pred_bl) && "Already permed that block");
117 * Note that all phis in the list are in the same register class
120 for(phi = get_irn_link(bl); phi; phi = get_irn_link(phi)) {
122 ir_node *arg = get_irn_n(phi, i);
123 unsigned hash = HASH_PTR(arg);
126 pp = set_find(arg_set, &templ, sizeof(templ), hash);
129 * If a proj_perm_t entry has not been made in the argument set,
130 * create one. The only restriction is, that the phi argument
131 * mey not be live in at the current block, since this argument
132 * interferes with the phi and must thus not be member of a
133 * Perm. A copy will be inserted for this argument alter on.
135 if(!pp && !is_live_in(bl, arg)) {
136 templ.pos = n_projs++;
137 set_insert(arg_set, &templ, sizeof(templ), hash);
142 * set the in array of the Perm to the arguments of the phis
145 in = malloc(n_projs * sizeof(in[0]));
146 for(pp = set_first(arg_set); pp; pp = set_next(arg_set))
147 in[pp->pos] = pp->arg;
149 perm = new_Perm(fact, chordal_env->cls, irg, pred_bl, n_projs, in);
150 insert_after = sched_skip(sched_last(pred_bl), 0, sched_skip_cf_predicator,
151 chordal_env->main_env->arch_env);
152 sched_add_after(insert_after, perm);
153 exchange(dummy, perm);
156 * Make the Projs for the Perm.
157 * register allocation is copied form former phi arguments
158 * to the projs (new phi arguments)
160 for(pp = set_first(arg_set); pp; pp = set_next(arg_set)) {
161 pp->proj = new_r_Proj(irg, pred_bl, perm, get_irn_mode(pp->arg), pp->pos);
162 set_reg(pp->proj, get_reg(pp->arg));
163 DBG((dbg, LEVEL_2, "Copy register assignment %s from %+F to %+F\n",
164 get_reg(pp->arg)->name, pp->arg, pp->proj));
168 * Set the phi nodes to their new arguments: The Projs of the Perm
170 for(phi = get_irn_link(bl); phi; phi = get_irn_link(phi)) {
173 templ.arg = get_irn_n(phi, i);
174 pp = set_find(arg_set, &templ, sizeof(templ), HASH_PTR(templ.arg));
176 assert(pp && "A Perm Proj must be created for this Phi argument");
177 set_irn_n(phi, i, pp->proj);
183 /* register in perm map */
184 pmap_insert(perm_map, pred_bl, perm);
189 static void insert_all_perms(be_chordal_env_t *chordal_env) {
190 DBG((dbg, LEVEL_1, "Placing perms...\n"));
191 irg_block_walk_graph(chordal_env->irg, insert_all_perms_walker, NULL, chordal_env);
194 #define is_pinned(irn) (get_irn_link(irn))
195 #define get_pinning_block(irn) ((ir_node *)get_irn_link(irn))
196 #define pin_irn(irn, lock) (set_irn_link(irn, lock))
200 * Adjusts the register allocation for the phi-operands
201 * by inserting perm nodes, if necessary.
202 * @param phi The phi node to adjust operands for
204 static void adjust_phi_arguments(be_chordal_env_t *chordal_env, ir_node *phi) {
206 ir_node *arg, *phi_block, *arg_block;
207 const arch_register_t *phi_reg, *arg_reg;
208 const arch_register_class_t *cls;
210 assert(is_Phi(phi) && "Can only handle phi-destruction :)");
212 phi_block = get_nodes_block(phi);
213 phi_reg = get_reg(phi);
214 cls = arch_get_irn_reg_class(get_chordal_arch(chordal_env), phi, -1);
216 /* process all arguments of the phi */
217 for(i=0, max=get_irn_arity(phi); i<max; ++i) {
218 arg = get_irn_n(phi, i);
219 arg_block = get_Block_cfgpred_block(phi_block, i);
220 arg_reg = get_reg(arg);
221 assert(arg_reg && "Register must be set while placing perms");
223 DBG((dbg, LEVEL_1, " for %+F(%s) -- %+F(%s)\n", phi, phi_reg->name, arg, arg_reg->name));
225 if(nodes_interfere(chordal_env, phi, arg)) {
226 /* Insert a duplicate in arguments block,
227 * make it the new phi arg,
229 * insert it into schedule,
232 ir_node *dupl = new_Copy(chordal_env->main_env->node_factory, cls, chordal_env->irg, arg_block, arg);
233 assert(get_irn_mode(phi) == get_irn_mode(dupl));
234 set_irn_n(phi, i, dupl);
235 set_reg(dupl, phi_reg);
236 sched_add_after(sched_skip(sched_last(arg_block), 0, sched_skip_cf_predicator, chordal_env->main_env->arch_env), dupl);
237 pin_irn(dupl, phi_block);
238 DBG((dbg, LEVEL_1, " they do interfere: insert %+F(%s)\n", dupl, get_reg(dupl)->name));
241 * First check if there is a phi
242 * - in the same block
243 * - having arg at the current pos in its arg-list
244 * - having the same color as arg
246 * If found, then pin the arg
248 DBG((dbg, LEVEL_1, " they do not interfere\n"));
249 assert(is_Proj(arg));
250 if (!is_pinned(arg)) {
252 DBG((dbg, LEVEL_1, " searching for phi with same arg having args register\n"));
253 for(other_phi = get_irn_link(phi_block); other_phi; other_phi = get_irn_link(other_phi)) {
254 assert(is_Phi(other_phi) && get_nodes_block(phi) == get_nodes_block(other_phi) && "link fields are screwed up");
255 if (get_irn_n(other_phi, i) == arg && get_reg(other_phi) == arg_reg) {
256 DBG((dbg, LEVEL_1, " found %+F(%s)\n", other_phi, get_reg(other_phi)->name));
257 pin_irn(arg, phi_block);
262 if (is_pinned(arg)) {
263 /* Insert a duplicate of the original value in arguments block,
264 * make it the new phi arg,
266 * insert it into schedule,
269 ir_node *perm = get_Proj_pred(arg);
270 ir_node *orig_val = get_irn_n(perm, get_Proj_proj(arg));
271 ir_node *dupl = new_Copy(chordal_env->main_env->node_factory, cls, chordal_env->irg, arg_block, orig_val);
272 assert(get_irn_mode(phi) == get_irn_mode(dupl));
273 set_irn_n(phi, i, dupl);
274 set_reg(dupl, phi_reg);
275 sched_add_before(perm, dupl);
276 pin_irn(dupl, phi_block);
277 DBG((dbg, LEVEL_1, " arg is pinned: insert %+F(%s)\n", dupl, get_reg(dupl)->name));
279 /* No other phi has the same color (else arg would be pinned),
280 * so just set the register and pin
282 set_reg(arg, phi_reg);
283 pin_irn(arg, phi_block);
284 DBG((dbg, LEVEL_1, " arg is not pinned: so pin %+F(%s)\n", arg, get_reg(arg)->name));
290 static void set_regs_or_place_dupls_walker(ir_node *bl, void *data) {
291 be_chordal_env_t *chordal_env = data;
294 for(phi = get_irn_link(bl); phi; phi = get_irn_link(phi))
295 adjust_phi_arguments(chordal_env, phi);
298 static void set_regs_or_place_dupls(be_chordal_env_t *chordal_env)
300 DBG((dbg, LEVEL_1, "Setting regs and placing dupls...\n"));
301 irg_block_walk_graph(chordal_env->irg, set_regs_or_place_dupls_walker, NULL, chordal_env);
305 void be_ssa_destruction(be_chordal_env_t *chordal_env) {
306 pmap *perm_map = pmap_create();
307 ir_graph *irg = chordal_env->irg;
309 dbg = firm_dbg_register("ir.be.ssadestr");
311 /* create a map for fast lookup of perms: block --> perm */
312 chordal_env->data = perm_map;
314 build_phi_rings(chordal_env);
315 insert_all_perms(chordal_env);
317 dump_ir_block_graph_sched(irg, "-ssa_destr_perms_placed");
319 set_regs_or_place_dupls(chordal_env);
321 dump_ir_block_graph_sched(irg, "-ssa_destr_regs_set");
324 pmap_destroy(perm_map);
327 static void ssa_destruction_check_walker(ir_node *bl, void *data)
329 be_chordal_env_t *chordal_env = data;
333 for(phi = get_irn_link(bl); phi; phi = get_irn_link(phi)) {
334 const arch_register_t *phi_reg, *arg_reg;
336 phi_reg = get_reg(phi);
337 /* iterate over all args of phi */
338 for(i=0, max=get_irn_arity(phi); i<max; ++i) {
339 ir_node *arg = get_irn_n(phi, i);
340 arg_reg = get_reg(arg);
341 if(phi_reg != arg_reg) {
342 DBG((dbg, 0, "Error: Registers of %+F and %+F differ: %s %s\n", phi, arg, phi_reg->name, arg_reg->name));
345 if(!is_pinned(arg)) {
346 DBG((dbg, 0, "Warning: Phi argument %+F is not pinned.\n", arg));
353 void be_ssa_destruction_check(be_chordal_env_t *chordal_env) {
354 irg_block_walk_graph(chordal_env->irg, ssa_destruction_check_walker, NULL, chordal_env);