- Rewrite internal backend logic for querying register constraints.
[libfirm] / ir / be / ia32 / ia32_common_transform.c
1 /*
2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
3  *
4  * This file is part of libFirm.
5  *
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.
10  *
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.
14  *
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
17  * PURPOSE.
18  */
19
20 /**
21  * @file
22  * @brief       This file implements the common parts of IR transformation from
23  *              firm into ia32-Firm.
24  * @author      Matthias Braun, Sebastian Buchwald
25  * @version     $Id: ia32_common_transform.c 21012 2008-08-06 13:35:17Z beck $
26  */
27 #include "config.h"
28
29 #include "error.h"
30 #include "ircons.h"
31 #include "irprintf.h"
32 #include "typerep.h"
33 #include "bitset.h"
34
35 #include "../betranshlp.h"
36 #include "../beirg.h"
37 #include "../beabi.h"
38
39 #include "ia32_architecture.h"
40 #include "ia32_common_transform.h"
41 #include "ia32_new_nodes.h"
42
43 #include "gen_ia32_new_nodes.h"
44 #include "gen_ia32_regalloc_if.h"
45
46 /** hold the current code generator during transformation */
47 ia32_code_gen_t *env_cg = NULL;
48
49 heights_t *heights = NULL;
50
51 static const arch_register_req_t no_register_req = {
52         arch_register_req_type_none,
53         NULL,                         /* regclass */
54         NULL,                         /* limit bitset */
55         0,                            /* same pos */
56         0                             /* different pos */
57 };
58
59 static int check_immediate_constraint(long val, char immediate_constraint_type)
60 {
61         switch (immediate_constraint_type) {
62                 case 0:
63                 case 'i': return 1;
64
65                 case 'I': return    0 <= val && val <=  31;
66                 case 'J': return    0 <= val && val <=  63;
67                 case 'K': return -128 <= val && val <= 127;
68                 case 'L': return val == 0xff || val == 0xffff;
69                 case 'M': return    0 <= val && val <=   3;
70                 case 'N': return    0 <= val && val <= 255;
71                 case 'O': return    0 <= val && val <= 127;
72
73                 default: panic("Invalid immediate constraint found");
74         }
75 }
76
77 /* creates a unique ident by adding a number to a tag */
78 ident *ia32_unique_id(const char *tag)
79 {
80         static unsigned id = 0;
81         char str[256];
82
83         snprintf(str, sizeof(str), tag, ++id);
84         return new_id_from_str(str);
85 }
86
87 /**
88  * Get a primitive type for a mode with alignment 16.
89  */
90 static ir_type *ia32_get_prim_type(pmap *types, ir_mode *mode)
91 {
92         pmap_entry *e = pmap_find(types, mode);
93         ir_type *res;
94
95         if (! e) {
96                 char buf[64];
97                 snprintf(buf, sizeof(buf), "prim_type_%s", get_mode_name(mode));
98                 res = new_type_primitive(new_id_from_str(buf), mode);
99                 if (get_mode_size_bits(mode) >= 80) {
100                         set_type_alignment_bytes(res, 16);
101                 }
102                 pmap_insert(types, mode, res);
103         }
104         else
105                 res = e->value;
106         return res;
107 }
108
109 ir_entity *create_float_const_entity(ir_node *cnst)
110 {
111         ia32_isa_t *isa = env_cg->isa;
112         tarval *key     = get_Const_tarval(cnst);
113         pmap_entry *e   = pmap_find(isa->tv_ent, key);
114         ir_entity *res;
115         ir_graph *rem;
116
117         if (e == NULL) {
118                 tarval  *tv   = key;
119                 ir_mode *mode = get_tarval_mode(tv);
120                 ir_type *tp;
121
122                 if (! ia32_cg_config.use_sse2) {
123                         /* try to reduce the mode to produce smaller sized entities */
124                         if (mode != mode_F) {
125                                 if (tarval_ieee754_can_conv_lossless(tv, mode_F)) {
126                                         mode = mode_F;
127                                         tv = tarval_convert_to(tv, mode);
128                                 } else if (mode != mode_D) {
129                                         if (tarval_ieee754_can_conv_lossless(tv, mode_D)) {
130                                                 mode = mode_D;
131                                                 tv = tarval_convert_to(tv, mode);
132                                         }
133                                 }
134                         }
135                 }
136
137                 if (mode == get_irn_mode(cnst)) {
138                         /* mode was not changed */
139                         tp = get_Const_type(cnst);
140                         if (tp == firm_unknown_type)
141                                 tp = ia32_get_prim_type(isa->types, mode);
142                 } else
143                         tp = ia32_get_prim_type(isa->types, mode);
144
145                 res = new_entity(get_glob_type(), ia32_unique_id(".LC%u"), tp);
146
147                 set_entity_ld_ident(res, get_entity_ident(res));
148                 set_entity_visibility(res, visibility_local);
149                 set_entity_variability(res, variability_constant);
150                 set_entity_allocation(res, allocation_static);
151
152                  /* we create a new entity here: It's initialization must resist on the
153                     const code irg */
154                 rem = current_ir_graph;
155                 current_ir_graph = get_const_code_irg();
156                 set_atomic_ent_value(res, new_Const_type(tv, tp));
157                 current_ir_graph = rem;
158
159                 pmap_insert(isa->tv_ent, key, res);
160         } else {
161                 res = e->value;
162         }
163
164         return res;
165 }
166
167 ir_node *ia32_create_Immediate(ir_entity *symconst, int symconst_sign, long val)
168 {
169         ir_graph *irg         = current_ir_graph;
170         ir_node  *start_block = get_irg_start_block(irg);
171         ir_node  *immediate   = new_bd_ia32_Immediate(NULL, start_block, symconst,
172                         symconst_sign, no_pic_adjust, val);
173         arch_set_irn_register(immediate, &ia32_gp_regs[REG_GP_NOREG]);
174
175         return immediate;
176 }
177
178 const arch_register_t *ia32_get_clobber_register(const char *clobber)
179 {
180         const arch_register_t       *reg = NULL;
181         int                          c;
182         size_t                       r;
183         const arch_register_class_t *cls;
184
185         /* TODO: construct a hashmap instead of doing linear search for clobber
186          * register */
187         for(c = 0; c < N_CLASSES; ++c) {
188                 cls = & ia32_reg_classes[c];
189                 for(r = 0; r < cls->n_regs; ++r) {
190                         const arch_register_t *temp_reg = arch_register_for_index(cls, r);
191                         if (strcmp(temp_reg->name, clobber) == 0
192                                         || (c == CLASS_ia32_gp && strcmp(temp_reg->name+1, clobber) == 0)) {
193                                 reg = temp_reg;
194                                 break;
195                         }
196                 }
197                 if (reg != NULL)
198                         break;
199         }
200
201         return reg;
202 }
203
204 int ia32_mode_needs_gp_reg(ir_mode *mode) {
205         if (mode == mode_fpcw)
206                 return 0;
207         if (get_mode_size_bits(mode) > 32)
208                 return 0;
209         return mode_is_int(mode) || mode_is_reference(mode) || mode == mode_b;
210 }
211
212 static void parse_asm_constraints(constraint_t *constraint, const char *c,
213                            int is_output)
214 {
215         char                         immediate_type     = '\0';
216         unsigned                     limited            = 0;
217         const arch_register_class_t *cls                = NULL;
218         int                          memory_possible       = 0;
219         int                          all_registers_allowed = 0;
220         int                          p;
221         int                          same_as = -1;
222
223         memset(constraint, 0, sizeof(constraint[0]));
224         constraint->same_as = -1;
225
226         if (*c == 0) {
227                 /* a memory constraint: no need to do anything in backend about it
228                  * (the dependencies are already respected by the memory edge of
229                  * the node) */
230                 return;
231         }
232
233         /* TODO: improve error messages with node and source info. (As users can
234          * easily hit these) */
235         while(*c != 0) {
236                 switch(*c) {
237                 case ' ':
238                 case '\t':
239                 case '\n':
240                         break;
241
242                 /* Skip out/in-out marker */
243                 case '=': break;
244                 case '+': break;
245
246                 case '&': break;
247
248                 case '*':
249                         ++c;
250                         break;
251                 case '#':
252                         while(*c != 0 && *c != ',')
253                                 ++c;
254                         break;
255
256                 case 'a':
257                         assert(cls == NULL || cls == &ia32_reg_classes[CLASS_ia32_gp]);
258                         cls      = &ia32_reg_classes[CLASS_ia32_gp];
259                         limited |= 1 << REG_EAX;
260                         break;
261                 case 'b':
262                         assert(cls == NULL || cls == &ia32_reg_classes[CLASS_ia32_gp]);
263                         cls      = &ia32_reg_classes[CLASS_ia32_gp];
264                         limited |= 1 << REG_EBX;
265                         break;
266                 case 'c':
267                         assert(cls == NULL || cls == &ia32_reg_classes[CLASS_ia32_gp]);
268                         cls      = &ia32_reg_classes[CLASS_ia32_gp];
269                         limited |= 1 << REG_ECX;
270                         break;
271                 case 'd':
272                         assert(cls == NULL || cls == &ia32_reg_classes[CLASS_ia32_gp]);
273                         cls      = &ia32_reg_classes[CLASS_ia32_gp];
274                         limited |= 1 << REG_EDX;
275                         break;
276                 case 'D':
277                         assert(cls == NULL || cls == &ia32_reg_classes[CLASS_ia32_gp]);
278                         cls      = &ia32_reg_classes[CLASS_ia32_gp];
279                         limited |= 1 << REG_EDI;
280                         break;
281                 case 'S':
282                         assert(cls == NULL || cls == &ia32_reg_classes[CLASS_ia32_gp]);
283                         cls      = &ia32_reg_classes[CLASS_ia32_gp];
284                         limited |= 1 << REG_ESI;
285                         break;
286                 case 'Q':
287                 case 'q':
288                         /* q means lower part of the regs only, this makes no
289                          * difference to Q for us (we only assign whole registers) */
290                         assert(cls == NULL || cls == &ia32_reg_classes[CLASS_ia32_gp]);
291                         cls      = &ia32_reg_classes[CLASS_ia32_gp];
292                         limited |= 1 << REG_EAX | 1 << REG_EBX | 1 << REG_ECX |
293                                    1 << REG_EDX;
294                         break;
295                 case 'A':
296                         assert(cls == NULL || cls == &ia32_reg_classes[CLASS_ia32_gp]);
297                         cls      = &ia32_reg_classes[CLASS_ia32_gp];
298                         limited |= 1 << REG_EAX | 1 << REG_EDX;
299                         break;
300                 case 'l':
301                         assert(cls == NULL || cls == &ia32_reg_classes[CLASS_ia32_gp]);
302                         cls      = &ia32_reg_classes[CLASS_ia32_gp];
303                         limited |= 1 << REG_EAX | 1 << REG_EBX | 1 << REG_ECX |
304                                    1 << REG_EDX | 1 << REG_ESI | 1 << REG_EDI |
305                                    1 << REG_EBP;
306                         break;
307
308                 case 'R':
309                 case 'r':
310                 case 'p':
311                         if (cls != NULL && cls != &ia32_reg_classes[CLASS_ia32_gp])
312                                 panic("multiple register classes not supported");
313                         cls                   = &ia32_reg_classes[CLASS_ia32_gp];
314                         all_registers_allowed = 1;
315                         break;
316
317                 case 'f':
318                 case 't':
319                 case 'u':
320                         /* TODO: mark values so the x87 simulator knows about t and u */
321                         if (cls != NULL && cls != &ia32_reg_classes[CLASS_ia32_vfp])
322                                 panic("multiple register classes not supported");
323                         cls                   = &ia32_reg_classes[CLASS_ia32_vfp];
324                         all_registers_allowed = 1;
325                         break;
326
327                 case 'Y':
328                 case 'x':
329                         if (cls != NULL && cls != &ia32_reg_classes[CLASS_ia32_xmm])
330                                 panic("multiple register classes not supproted");
331                         cls                   = &ia32_reg_classes[CLASS_ia32_xmm];
332                         all_registers_allowed = 1;
333                         break;
334
335                 case 'I':
336                 case 'J':
337                 case 'K':
338                 case 'L':
339                 case 'M':
340                 case 'N':
341                 case 'O':
342                         if (cls != NULL && cls != &ia32_reg_classes[CLASS_ia32_gp])
343                                 panic("multiple register classes not supported");
344                         if (immediate_type != '\0')
345                                 panic("multiple immediate types not supported");
346                         cls            = &ia32_reg_classes[CLASS_ia32_gp];
347                         immediate_type = *c;
348                         break;
349                 case 'n':
350                 case 'i':
351                         if (cls != NULL && cls != &ia32_reg_classes[CLASS_ia32_gp])
352                                 panic("multiple register classes not supported");
353                         if (immediate_type != '\0')
354                                 panic("multiple immediate types not supported");
355                         cls            = &ia32_reg_classes[CLASS_ia32_gp];
356                         immediate_type = 'i';
357                         break;
358
359                 case 'X':
360                 case 'g':
361                         if (cls != NULL && cls != &ia32_reg_classes[CLASS_ia32_gp])
362                                 panic("multiple register classes not supported");
363                         if (immediate_type != '\0')
364                                 panic("multiple immediate types not supported");
365                         immediate_type        = 'i';
366                         cls                   = &ia32_reg_classes[CLASS_ia32_gp];
367                         all_registers_allowed = 1;
368                         memory_possible       = 1;
369                         break;
370
371                 case '0':
372                 case '1':
373                 case '2':
374                 case '3':
375                 case '4':
376                 case '5':
377                 case '6':
378                 case '7':
379                 case '8':
380                 case '9':
381                         if (is_output)
382                                 panic("can only specify same constraint on input");
383
384                         sscanf(c, "%d%n", &same_as, &p);
385                         if (same_as >= 0) {
386                                 c += p;
387                                 continue;
388                         }
389                         break;
390
391                 case 'm':
392                 case 'o':
393                 case 'V':
394                         /* memory constraint no need to do anything in backend about it
395                          * (the dependencies are already respected by the memory edge of
396                          * the node) */
397                         memory_possible = 1;
398                         break;
399
400                 case 'E': /* no float consts yet */
401                 case 'F': /* no float consts yet */
402                 case 's': /* makes no sense on x86 */
403                 case '<': /* no autodecrement on x86 */
404                 case '>': /* no autoincrement on x86 */
405                 case 'C': /* sse constant not supported yet */
406                 case 'G': /* 80387 constant not supported yet */
407                 case 'y': /* we don't support mmx registers yet */
408                 case 'Z': /* not available in 32 bit mode */
409                 case 'e': /* not available in 32 bit mode */
410                         panic("unsupported asm constraint '%c' found in (%+F)",
411                               *c, current_ir_graph);
412                         break;
413                 default:
414                         panic("unknown asm constraint '%c' found in (%+F)", *c,
415                               current_ir_graph);
416                         break;
417                 }
418                 ++c;
419         }
420
421         if (same_as >= 0) {
422                 if (cls != NULL)
423                         panic("same as and register constraint not supported");
424                 if (immediate_type != '\0')
425                         panic("same as and immediate constraint not supported");
426         }
427
428         if (cls == NULL && same_as < 0) {
429                 if (!memory_possible)
430                         panic("no constraint specified for assembler input");
431         }
432
433         constraint->same_as               = same_as;
434         constraint->cls                   = cls;
435         constraint->allowed_registers     = limited;
436         constraint->all_registers_allowed = all_registers_allowed;
437         constraint->memory_possible       = memory_possible;
438         constraint->immediate_type        = immediate_type;
439 }
440
441 static bool can_match(const arch_register_req_t *in,
442                       const arch_register_req_t *out)
443 {
444         if (in->cls != out->cls)
445                 return false;
446         if ( (in->type & arch_register_req_type_limited) == 0
447                 || (out->type & arch_register_req_type_limited) == 0 )
448                 return true;
449
450         return (*in->limited & *out->limited) != 0;
451 }
452
453 ir_node *gen_ASM(ir_node *node)
454 {
455         ir_node                    *block = NULL;
456         ir_node                    *new_block = NULL;
457         dbg_info                   *dbgi      = get_irn_dbg_info(node);
458         int                         i, arity;
459         int                         out_idx;
460         ir_node                   **in;
461         ir_node                    *new_node;
462         int                         out_arity;
463         int                         n_out_constraints;
464         int                         n_clobbers;
465         const arch_register_req_t **out_reg_reqs;
466         const arch_register_req_t **in_reg_reqs;
467         ia32_asm_reg_t             *register_map;
468         unsigned                    reg_map_size = 0;
469         struct obstack             *obst;
470         const ir_asm_constraint    *in_constraints;
471         const ir_asm_constraint    *out_constraints;
472         ident                     **clobbers;
473         int                         clobbers_flags = 0;
474         unsigned                    clobber_bits[N_CLASSES];
475         int                         out_size;
476
477         memset(&clobber_bits, 0, sizeof(clobber_bits));
478
479         switch (be_transformer) {
480         case TRANSFORMER_DEFAULT:
481                 block     = get_nodes_block(node);
482                 new_block = be_transform_node(block);
483                 break;
484
485 #ifdef FIRM_GRGEN_BE
486         case TRANSFORMER_PBQP:
487         case TRANSFORMER_RAND:
488                 new_block = get_nodes_block(node);
489                 break;
490 #endif
491
492         default:
493                 panic("invalid transformer");
494         }
495
496         /* workaround for lots of buggy code out there as most people think volatile
497          * asm is enough for everything and forget the flags (linux kernel, etc.)
498          */
499         if (get_irn_pinned(node) == op_pin_state_pinned) {
500                 clobbers_flags = 1;
501         }
502
503         arity = get_irn_arity(node);
504         in    = ALLOCANZ(ir_node*, arity);
505
506         clobbers   = get_ASM_clobbers(node);
507         n_clobbers = 0;
508         for (i = 0; i < get_ASM_n_clobbers(node); ++i) {
509                 const arch_register_req_t *req;
510                 const char                *c = get_id_str(clobbers[i]);
511
512                 if (strcmp(c, "memory") == 0)
513                         continue;
514                 if (strcmp(c, "cc") == 0) {
515                         clobbers_flags = 1;
516                         continue;
517                 }
518
519                 req = parse_clobber(c);
520                 clobber_bits[req->cls->index] |= *req->limited;
521
522                 n_clobbers++;
523         }
524         n_out_constraints = get_ASM_n_output_constraints(node);
525         out_arity         = n_out_constraints + n_clobbers;
526
527         in_constraints  = get_ASM_input_constraints(node);
528         out_constraints = get_ASM_output_constraints(node);
529
530         /* determine size of register_map */
531         for (out_idx = 0; out_idx < n_out_constraints; ++out_idx) {
532                 const ir_asm_constraint *constraint = &out_constraints[out_idx];
533                 if (constraint->pos > reg_map_size)
534                         reg_map_size = constraint->pos;
535         }
536         for (i = 0; i < arity; ++i) {
537                 const ir_asm_constraint   *constraint = &in_constraints[i];
538                 if (constraint->pos > reg_map_size)
539                         reg_map_size = constraint->pos;
540         }
541         ++reg_map_size;
542
543         obst         = get_irg_obstack(current_ir_graph);
544         register_map = NEW_ARR_D(ia32_asm_reg_t, obst, reg_map_size);
545         memset(register_map, 0, reg_map_size * sizeof(register_map[0]));
546
547         /* construct output constraints */
548         out_size = out_arity + 1;
549         out_reg_reqs = obstack_alloc(obst, out_size * sizeof(out_reg_reqs[0]));
550
551         for (out_idx = 0; out_idx < n_out_constraints; ++out_idx) {
552                 const ir_asm_constraint   *constraint = &out_constraints[out_idx];
553                 const char                *c       = get_id_str(constraint->constraint);
554                 unsigned                   pos        = constraint->pos;
555                 constraint_t               parsed_constraint;
556                 const arch_register_req_t *req;
557
558                 parse_asm_constraints(&parsed_constraint, c, 1);
559                 req = make_register_req(&parsed_constraint, n_out_constraints,
560                                         out_reg_reqs, out_idx);
561                 out_reg_reqs[out_idx] = req;
562
563                 register_map[pos].use_input = 0;
564                 register_map[pos].valid     = 1;
565                 register_map[pos].memory    = 0;
566                 register_map[pos].inout_pos = out_idx;
567                 register_map[pos].mode      = constraint->mode;
568         }
569
570         /* inputs + input constraints */
571         in_reg_reqs = obstack_alloc(obst, arity * sizeof(in_reg_reqs[0]));
572         for (i = 0; i < arity; ++i) {
573                 ir_node                   *pred         = get_irn_n(node, i);
574                 const ir_asm_constraint   *constraint   = &in_constraints[i];
575                 ident                     *constr_id    = constraint->constraint;
576                 const char                *c            = get_id_str(constr_id);
577                 unsigned                   pos          = constraint->pos;
578                 int                        is_memory_op = 0;
579                 ir_node                   *input        = NULL;
580                 unsigned                   r_clobber_bits;
581                 constraint_t               parsed_constraint;
582                 const arch_register_req_t *req;
583
584                 parse_asm_constraints(&parsed_constraint, c, 0);
585                 if (parsed_constraint.cls != NULL) {
586                         r_clobber_bits = clobber_bits[parsed_constraint.cls->index];
587                         if (r_clobber_bits != 0) {
588                                 if (parsed_constraint.all_registers_allowed) {
589                                         parsed_constraint.all_registers_allowed = 0;
590                                         be_abi_set_non_ignore_regs(env_cg->birg->abi,
591                                                         parsed_constraint.cls,
592                                                         &parsed_constraint.allowed_registers);
593                                 }
594                                 parsed_constraint.allowed_registers &= ~r_clobber_bits;
595                         }
596                 }
597
598                 req = make_register_req(&parsed_constraint, n_out_constraints,
599                                         out_reg_reqs, i);
600                 in_reg_reqs[i] = req;
601
602                 if (parsed_constraint.immediate_type != '\0') {
603                         char imm_type = parsed_constraint.immediate_type;
604                         input = try_create_Immediate(pred, imm_type);
605                 }
606
607                 if (input == NULL) {
608                         ir_node *pred = NULL;
609                         switch (be_transformer) {
610                         case TRANSFORMER_DEFAULT:
611                                 pred  = get_irn_n(node, i);
612                                 input = be_transform_node(pred);
613                                 break;
614
615 #ifdef FIRM_GRGEN_BE
616                         case TRANSFORMER_PBQP:
617                         case TRANSFORMER_RAND:
618                                 input = get_irn_n(node, i);
619                                 break;
620 #endif
621
622                         default: panic("invalid transformer");
623                         }
624
625                         if (parsed_constraint.cls == NULL
626                                         && parsed_constraint.same_as < 0) {
627                                 is_memory_op = 1;
628                         } else if (parsed_constraint.memory_possible) {
629                                 /* TODO: match Load or Load/Store if memory possible is set */
630                         }
631                 }
632                 in[i] = input;
633
634                 register_map[pos].use_input = 1;
635                 register_map[pos].valid     = 1;
636                 register_map[pos].memory    = is_memory_op;
637                 register_map[pos].inout_pos = i;
638                 register_map[pos].mode      = constraint->mode;
639         }
640
641         /* parse clobbers */
642         for (i = 0; i < get_ASM_n_clobbers(node); ++i) {
643                 const char                *c = get_id_str(clobbers[i]);
644                 const arch_register_req_t *req;
645
646                 if (strcmp(c, "memory") == 0 || strcmp(c, "cc") == 0)
647                         continue;
648
649                 req = parse_clobber(c);
650                 out_reg_reqs[out_idx] = req;
651                 ++out_idx;
652         }
653
654         /* Attempt to make ASM node register pressure faithfull.
655          * (This does not work for complicated cases yet!)
656          *
657          * Algorithm: Check if there are fewer inputs or outputs (I will call this
658          * the smaller list). Then try to match each constraint of the smaller list
659          * to 1 of the other list. If we can't match it, then we have to add a dummy
660          * input/output to the other list
661          *
662          * FIXME: This is still broken in lots of cases. But at least better than
663          *        before...
664          * FIXME: need to do this per register class...
665          */
666         if (out_arity <= arity) {
667                 int       orig_arity = arity;
668                 int       in_size    = arity;
669                 int       o;
670                 bitset_t *used_ins = bitset_alloca(arity);
671                 for (o = 0; o < out_arity; ++o) {
672                         int   i;
673                         const arch_register_req_t *outreq = out_reg_reqs[o];
674
675                         if (outreq->cls == NULL) {
676                                 continue;
677                         }
678
679                         for (i = 0; i < orig_arity; ++i) {
680                                 const arch_register_req_t *inreq;
681                                 if (bitset_is_set(used_ins, i))
682                                         continue;
683                                 inreq = in_reg_reqs[i];
684                                 if (!can_match(outreq, inreq))
685                                         continue;
686                                 bitset_set(used_ins, i);
687                                 break;
688                         }
689                         /* did we find any match? */
690                         if (i < orig_arity)
691                                 continue;
692
693                         /* we might need more space in the input arrays */
694                         if (arity >= in_size) {
695                                 const arch_register_req_t **new_in_reg_reqs;
696                                 ir_node             **new_in;
697
698                                 in_size *= 2;
699                                 new_in_reg_reqs
700                                         = obstack_alloc(obst, in_size*sizeof(in_reg_reqs[0]));
701                                 memcpy(new_in_reg_reqs, in_reg_reqs, arity * sizeof(new_in_reg_reqs[0]));
702                                 new_in = ALLOCANZ(ir_node*, in_size);
703                                 memcpy(new_in, in, arity*sizeof(new_in[0]));
704
705                                 in_reg_reqs = new_in_reg_reqs;
706                                 in          = new_in;
707                         }
708
709                         /* add a new (dummy) input which occupies the register */
710                         assert(outreq->type & arch_register_req_type_limited);
711                         in_reg_reqs[arity] = outreq;
712                         in[arity]          = new_bd_ia32_ProduceVal(NULL, block);
713                         be_dep_on_frame(in[arity]);
714                         ++arity;
715                 }
716         } else {
717                 int       i;
718                 bitset_t *used_outs = bitset_alloca(out_arity);
719                 int       orig_out_arity = out_arity;
720                 for (i = 0; i < arity; ++i) {
721                         int   o;
722                         const arch_register_req_t *inreq = in_reg_reqs[i];
723
724                         if (inreq->cls == NULL) {
725                                 continue;
726                         }
727
728                         for (o = 0; o < orig_out_arity; ++o) {
729                                 const arch_register_req_t *outreq;
730                                 if (bitset_is_set(used_outs, o))
731                                         continue;
732                                 outreq = out_reg_reqs[o];
733                                 if (!can_match(outreq, inreq))
734                                         continue;
735                                 bitset_set(used_outs, i);
736                                 break;
737                         }
738                         /* did we find any match? */
739                         if (o < orig_out_arity)
740                                 continue;
741
742                         /* we might need more space in the output arrays */
743                         if (out_arity >= out_size) {
744                                 const arch_register_req_t **new_out_reg_reqs;
745
746                                 out_size *= 2;
747                                 new_out_reg_reqs
748                                         = obstack_alloc(obst, out_size*sizeof(out_reg_reqs[0]));
749                                 memcpy(new_out_reg_reqs, out_reg_reqs,
750                                        out_arity * sizeof(new_out_reg_reqs[0]));
751                                 out_reg_reqs = new_out_reg_reqs;
752                         }
753
754                         /* add a new (dummy) output which occupies the register */
755                         assert(inreq->type & arch_register_req_type_limited);
756                         out_reg_reqs[out_arity] = inreq;
757                         ++out_arity;
758                 }
759         }
760
761         /* append none register requirement for the memory output */
762         if (out_arity + 1 >= out_size) {
763                 const arch_register_req_t **new_out_reg_reqs;
764
765                 out_size = out_arity + 1;
766                 new_out_reg_reqs
767                         = obstack_alloc(obst, out_size*sizeof(out_reg_reqs[0]));
768                 memcpy(new_out_reg_reqs, out_reg_reqs,
769                            out_arity * sizeof(new_out_reg_reqs[0]));
770                 out_reg_reqs = new_out_reg_reqs;
771         }
772
773         /* add a new (dummy) output which occupies the register */
774         out_reg_reqs[out_arity] = arch_no_register_req;
775         ++out_arity;
776
777         new_node = new_bd_ia32_Asm(dbgi, new_block, arity, in, out_arity,
778                                    get_ASM_text(node), register_map);
779
780         if (arity == 0)
781                 be_dep_on_frame(new_node);
782
783         set_ia32_out_req_all(new_node, out_reg_reqs);
784         set_ia32_in_req_all(new_node, in_reg_reqs);
785
786         SET_IA32_ORIG_NODE(new_node, node);
787
788         return new_node;
789 }
790
791 ir_node *gen_CopyB(ir_node *node) {
792         ir_node  *block    = NULL;
793         ir_node  *src      = NULL;
794         ir_node  *new_src  = NULL;
795         ir_node  *dst      = NULL;
796         ir_node  *new_dst  = NULL;
797         ir_node  *mem      = NULL;
798         ir_node  *new_mem  = NULL;
799         ir_node  *res      = NULL;
800         dbg_info *dbgi     = get_irn_dbg_info(node);
801         int      size      = get_type_size_bytes(get_CopyB_type(node));
802         int      rem;
803
804         switch (be_transformer) {
805                 case TRANSFORMER_DEFAULT:
806                         block    = be_transform_node(get_nodes_block(node));
807                         src      = get_CopyB_src(node);
808                         new_src  = be_transform_node(src);
809                         dst      = get_CopyB_dst(node);
810                         new_dst  = be_transform_node(dst);
811                         mem      = get_CopyB_mem(node);
812                         new_mem  = be_transform_node(mem);
813                         break;
814
815 #ifdef FIRM_GRGEN_BE
816                 case TRANSFORMER_PBQP:
817                 case TRANSFORMER_RAND:
818                         block    = get_nodes_block(node);
819                         new_src  = get_CopyB_src(node);
820                         new_dst  = get_CopyB_dst(node);
821                         new_mem  = get_CopyB_mem(node);
822                         break;
823 #endif
824
825                 default: panic("invalid transformer");
826         }
827
828         /* If we have to copy more than 32 bytes, we use REP MOVSx and */
829         /* then we need the size explicitly in ECX.                    */
830         if (size >= 32 * 4) {
831                 rem = size & 0x3; /* size % 4 */
832                 size >>= 2;
833
834                 res = new_bd_ia32_Const(dbgi, block, NULL, 0, 0, size);
835                 be_dep_on_frame(res);
836
837                 res = new_bd_ia32_CopyB(dbgi, block, new_dst, new_src, res, new_mem, rem);
838         } else {
839                 if (size == 0) {
840                         ir_fprintf(stderr, "Optimization warning copyb %+F with size <4\n",
841                                    node);
842                 }
843                 res = new_bd_ia32_CopyB_i(dbgi, block, new_dst, new_src, new_mem, size);
844         }
845
846         SET_IA32_ORIG_NODE(res, node);
847
848         return res;
849 }
850
851 ir_node *gen_Proj_tls(ir_node *node) {
852         ir_node  *block = NULL;
853         dbg_info *dbgi  = NULL;
854         ir_node  *res   = NULL;
855
856         switch (be_transformer) {
857                 case TRANSFORMER_DEFAULT:
858                         block = be_transform_node(get_nodes_block(node));
859                         break;
860
861 #ifdef FIRM_GRGEN_BE
862                 case TRANSFORMER_PBQP:
863                 case TRANSFORMER_RAND:
864                         block = get_nodes_block(node);
865                         break;
866 #endif
867
868                 default: panic("invalid transformer");
869         }
870
871         res = new_bd_ia32_LdTls(dbgi, block, mode_Iu);
872
873         return res;
874 }
875
876 ir_node *gen_Unknown(ir_node *node)
877 {
878         ir_mode *mode = get_irn_mode(node);
879
880         if (mode_is_float(mode)) {
881                 if (ia32_cg_config.use_sse2) {
882                         return ia32_new_Unknown_xmm(env_cg);
883                 } else {
884                         /* Unknown nodes are buggy in x87 simulator, use zero for now... */
885                         ir_graph *irg   = current_ir_graph;
886                         dbg_info *dbgi  = get_irn_dbg_info(node);
887                         ir_node  *block = get_irg_start_block(irg);
888                         ir_node  *ret   = new_bd_ia32_vfldz(dbgi, block);
889
890                         be_dep_on_frame(ret);
891                         return ret;
892                 }
893         } else if (ia32_mode_needs_gp_reg(mode)) {
894                 return ia32_new_Unknown_gp(env_cg);
895         } else {
896                 panic("unsupported Unknown-Mode");
897         }
898         return NULL;
899 }
900
901 const arch_register_req_t *make_register_req(const constraint_t *constraint,
902                 int n_outs, const arch_register_req_t **out_reqs, int pos)
903 {
904         struct obstack      *obst    = get_irg_obstack(current_ir_graph);
905         int                  same_as = constraint->same_as;
906         arch_register_req_t *req;
907
908         if (same_as >= 0) {
909                 const arch_register_req_t *other_constr;
910
911                 if (same_as >= n_outs)
912                         panic("invalid output number in same_as constraint");
913
914                 other_constr     = out_reqs[same_as];
915
916                 req              = obstack_alloc(obst, sizeof(req[0]));
917                 *req             = *other_constr;
918                 req->type       |= arch_register_req_type_should_be_same;
919                 req->other_same  = 1U << pos;
920
921                 /* switch constraints. This is because in firm we have same_as
922                  * constraints on the output constraints while in the gcc asm syntax
923                  * they are specified on the input constraints */
924                 out_reqs[same_as] = req;
925                 return other_constr;
926         }
927
928         /* pure memory ops */
929         if (constraint->cls == NULL) {
930                 return &no_register_req;
931         }
932
933         if (constraint->allowed_registers != 0
934                         && !constraint->all_registers_allowed) {
935                 unsigned *limited_ptr;
936
937                 req         = obstack_alloc(obst, sizeof(req[0]) + sizeof(unsigned));
938                 memset(req, 0, sizeof(req[0]));
939                 limited_ptr = (unsigned*) (req+1);
940
941                 req->type    = arch_register_req_type_limited;
942                 *limited_ptr = constraint->allowed_registers;
943                 req->limited = limited_ptr;
944         } else {
945                 req       = obstack_alloc(obst, sizeof(req[0]));
946                 memset(req, 0, sizeof(req[0]));
947                 req->type = arch_register_req_type_normal;
948         }
949         req->cls = constraint->cls;
950
951         return req;
952 }
953
954 const arch_register_req_t *parse_clobber(const char *clobber)
955 {
956         struct obstack        *obst = get_irg_obstack(current_ir_graph);
957         const arch_register_t *reg  = ia32_get_clobber_register(clobber);
958         arch_register_req_t   *req;
959         unsigned              *limited;
960
961         if (reg == NULL) {
962                 panic("Register '%s' mentioned in asm clobber is unknown", clobber);
963         }
964
965         assert(reg->index < 32);
966
967         limited  = obstack_alloc(obst, sizeof(limited[0]));
968         *limited = 1 << reg->index;
969
970         req          = obstack_alloc(obst, sizeof(req[0]));
971         memset(req, 0, sizeof(req[0]));
972         req->type    = arch_register_req_type_limited;
973         req->cls     = arch_register_get_class(reg);
974         req->limited = limited;
975
976         return req;
977 }
978
979
980 int prevents_AM(ir_node *const block, ir_node *const am_candidate,
981                        ir_node *const other)
982 {
983         if (get_nodes_block(other) != block)
984                 return 0;
985
986         if (is_Sync(other)) {
987                 int i;
988
989                 for (i = get_Sync_n_preds(other) - 1; i >= 0; --i) {
990                         ir_node *const pred = get_Sync_pred(other, i);
991
992                         if (get_nodes_block(pred) != block)
993                                 continue;
994
995                         /* Do not block ourselves from getting eaten */
996                         if (is_Proj(pred) && get_Proj_pred(pred) == am_candidate)
997                                 continue;
998
999                         if (!heights_reachable_in_block(heights, pred, am_candidate))
1000                                 continue;
1001
1002                         return 1;
1003                 }
1004
1005                 return 0;
1006         } else {
1007                 /* Do not block ourselves from getting eaten */
1008                 if (is_Proj(other) && get_Proj_pred(other) == am_candidate)
1009                         return 0;
1010
1011                 if (!heights_reachable_in_block(heights, other, am_candidate))
1012                         return 0;
1013
1014                 return 1;
1015         }
1016 }
1017
1018 ir_node *try_create_Immediate(ir_node *node, char immediate_constraint_type)
1019 {
1020         int          minus         = 0;
1021         tarval      *offset        = NULL;
1022         int          offset_sign   = 0;
1023         long         val = 0;
1024         ir_entity   *symconst_ent  = NULL;
1025         int          symconst_sign = 0;
1026         ir_mode     *mode;
1027         ir_node     *cnst          = NULL;
1028         ir_node     *symconst      = NULL;
1029         ir_node     *new_node;
1030
1031         mode = get_irn_mode(node);
1032         if (!mode_is_int(mode) && !mode_is_reference(mode)) {
1033                 return NULL;
1034         }
1035
1036         if (is_Minus(node)) {
1037                 minus = 1;
1038                 node  = get_Minus_op(node);
1039         }
1040
1041         if (is_Const(node)) {
1042                 cnst        = node;
1043                 symconst    = NULL;
1044                 offset_sign = minus;
1045         } else if (is_SymConst(node)) {
1046                 cnst          = NULL;
1047                 symconst      = node;
1048                 symconst_sign = minus;
1049         } else if (is_Add(node)) {
1050                 ir_node *left  = get_Add_left(node);
1051                 ir_node *right = get_Add_right(node);
1052                 if (is_Const(left) && is_SymConst(right)) {
1053                         cnst          = left;
1054                         symconst      = right;
1055                         symconst_sign = minus;
1056                         offset_sign   = minus;
1057                 } else if (is_SymConst(left) && is_Const(right)) {
1058                         cnst          = right;
1059                         symconst      = left;
1060                         symconst_sign = minus;
1061                         offset_sign   = minus;
1062                 }
1063         } else if (is_Sub(node)) {
1064                 ir_node *left  = get_Sub_left(node);
1065                 ir_node *right = get_Sub_right(node);
1066                 if (is_Const(left) && is_SymConst(right)) {
1067                         cnst          = left;
1068                         symconst      = right;
1069                         symconst_sign = !minus;
1070                         offset_sign   = minus;
1071                 } else if (is_SymConst(left) && is_Const(right)) {
1072                         cnst          = right;
1073                         symconst      = left;
1074                         symconst_sign = minus;
1075                         offset_sign   = !minus;
1076                 }
1077         } else {
1078                 return NULL;
1079         }
1080
1081         if (cnst != NULL) {
1082                 offset = get_Const_tarval(cnst);
1083                 if (tarval_is_long(offset)) {
1084                         val = get_tarval_long(offset);
1085                 } else {
1086                         ir_fprintf(stderr, "Optimisation Warning: tarval from %+F is not a "
1087                                    "long?\n", cnst);
1088                         return NULL;
1089                 }
1090
1091                 if (!check_immediate_constraint(val, immediate_constraint_type))
1092                         return NULL;
1093         }
1094         if (symconst != NULL) {
1095                 if (immediate_constraint_type != 0) {
1096                         /* we need full 32bits for symconsts */
1097                         return NULL;
1098                 }
1099
1100                 /* unfortunately the assembler/linker doesn't support -symconst */
1101                 if (symconst_sign)
1102                         return NULL;
1103
1104                 if (get_SymConst_kind(symconst) != symconst_addr_ent)
1105                         return NULL;
1106                 symconst_ent = get_SymConst_entity(symconst);
1107         }
1108         if (cnst == NULL && symconst == NULL)
1109                 return NULL;
1110
1111         if (offset_sign && offset != NULL) {
1112                 offset = tarval_neg(offset);
1113         }
1114
1115         new_node = ia32_create_Immediate(symconst_ent, symconst_sign, val);
1116
1117         return new_node;
1118 }