4d5c336a910c0010e58a1abcf6875849e30119a0
[libfirm] / ir / lower / lower_hl.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   Lower some High-level constructs, moved from the firmlower.
23  * @author  Boris Boesler, Goetz Lindenmaier, Michael Beck
24  * @version $Id$
25  */
26 #ifdef HAVE_CONFIG_H
27 # include "config.h"
28 #endif
29
30 #include "lowering.h"
31 #include "irmode_t.h"
32 #include "irnode_t.h"
33 #include "entity_t.h"
34 #include "typerep.h"
35 #include "irprog_t.h"
36 #include "ircons.h"
37 #include "irhooks.h"
38 #include "irgmod.h"
39 #include "irgwalk.h"
40
41 /**
42  * Lower a Sel node. Do not touch Sels accessing entities on the frame type.
43  */
44 static void lower_sel(ir_node *sel) {
45         ir_graph *irg = current_ir_graph;
46         ir_entity   *ent;
47         ir_node  *newn, *cnst, *index, *ptr, *bl;
48         tarval   *tv;
49         ir_mode  *basemode, *mode, *mode_Int;
50         ir_type  *basetyp, *owner;
51         dbg_info *dbg;
52
53         assert(is_Sel(sel));
54
55         ent   = get_Sel_entity(sel);
56         owner = get_entity_owner(ent);
57
58         /* Do not lower frame type access: must be lowered by the backend. */
59         if (is_frame_type(owner))
60                 return;
61
62         /*
63          * Cannot handle value param entities here.
64          * Must be lowered by the backend.
65          */
66         if (is_value_param_type(owner))
67                 return;
68
69         ptr  = get_Sel_ptr(sel);
70         dbg  = get_irn_dbg_info(sel);
71         mode = get_irn_mode(sel);
72
73         mode_Int = get_reference_mode_signed_eq(mode);
74
75         /* TLS access, must be handled by the linker */
76         if (get_tls_type() == owner) {
77                 symconst_symbol sym;
78
79                 sym.entity_p = ent;
80                 bl = get_nodes_block(sel);
81
82                 cnst = new_rd_SymConst(dbg, irg, bl, mode, sym, symconst_addr_ent);
83                 newn = new_rd_Add(dbg, irg, bl, ptr, cnst, mode);
84         } else {
85                 /* not TLS */
86
87                 assert(get_type_state(get_entity_owner(ent)) == layout_fixed);
88                 assert(get_type_state(get_entity_type(ent)) == layout_fixed);
89
90                 bl = get_nodes_block(sel);
91                 if (0 < get_Sel_n_indexs(sel)) {
92                         /* an Array access */
93                         basetyp = get_entity_type(ent);
94                         if (is_Primitive_type(basetyp))
95                                 basemode = get_type_mode(basetyp);
96                         else
97                                 basemode = mode_P_data;
98
99                         assert(basemode && "no mode for lowering Sel");
100                         assert((get_mode_size_bits(basemode) % 8 == 0) && "can not deal with unorthodox modes");
101                         index = get_Sel_index(sel, 0);
102
103                         if (is_Array_type(owner)) {
104                                 ir_node *last_size;
105                                 ir_type *arr_ty = owner;
106                                 int dims = get_array_n_dimensions(arr_ty);
107                                 int *map = alloca(sizeof(int) * dims);
108                                 int i;
109
110                                 assert(dims == get_Sel_n_indexs(sel)
111                                         && "array dimension must match number of indices of Sel node");
112
113                                 for (i = 0; i < dims; i++) {
114                                         int order = get_array_order(arr_ty, i);
115
116                                         assert(order < dims &&
117                                                 "order of a dimension must be smaller than the arrays dim");
118                                         map[order] = i;
119                                 }
120                                 newn = get_Sel_ptr(sel);
121
122                                 /* Size of the array element */
123                                 tv = new_tarval_from_long(get_type_size_bytes(basetyp), mode_Int);
124                                 last_size = new_rd_Const(dbg, irg, get_irg_start_block(irg), mode_Int, tv);
125
126                                 /*
127                                  * We compute the offset part of dimension d_i recursively
128                                  * with the the offset part of dimension d_{i-1}
129                                  *
130                                  *     off_0 = sizeof(array_element_type);
131                                  *     off_i = (u_i - l_i) * off_{i-1}  ; i >= 1
132                                  *
133                                  * whereas u_i is the upper bound of the current dimension
134                                  * and l_i the lower bound of the current dimension.
135                                  */
136                                 for (i = dims - 1; i >= 0; i--) {
137                                         int dim = map[i];
138                                         ir_node *lb, *ub, *elms, *n, *ind;
139
140                                         elms = NULL;
141                                         lb = get_array_lower_bound(arr_ty, dim);
142                                         ub = get_array_upper_bound(arr_ty, dim);
143
144                                         assert(irg == current_ir_graph);
145                                         if (! is_Unknown(lb))
146                                                 lb = new_rd_Conv(dbg, irg, bl, copy_const_value(get_irn_dbg_info(sel), lb), mode_Int);
147                                         else
148                                                 lb = NULL;
149
150                                         if (! is_Unknown(ub))
151                                                 ub = new_rd_Conv(dbg, irg, bl, copy_const_value(get_irn_dbg_info(sel), ub), mode_Int);
152                                         else
153                                                 ub = NULL;
154
155                                         /*
156                                          * If the array has more than one dimension, lower and upper
157                                          * bounds have to be set in the non-last dimension.
158                                          */
159                                         if (i > 0) {
160                                                 assert(lb != NULL && "lower bound has to be set in multi-dim array");
161                                                 assert(ub != NULL && "upper bound has to be set in multi-dim array");
162
163                                                 /* Elements in one Dimension */
164                                                 elms = new_rd_Sub(dbg, irg, bl, ub, lb, mode_Int);
165                                         }
166
167                                         ind = new_rd_Conv(dbg, irg, bl, get_Sel_index(sel, dim), mode_Int);
168
169                                         /*
170                                          * Normalize index, id lower bound is set, also assume
171                                          * lower bound == 0
172                                          */
173                                         if (lb != NULL)
174                                                 ind = new_rd_Sub(dbg, irg, bl, ind, lb, mode_Int);
175
176                                         n = new_rd_Mul(dbg, irg, bl, ind, last_size, mode_Int);
177
178                                         /*
179                                          * see comment above.
180                                          */
181                                         if (i > 0)
182                                                 last_size = new_rd_Mul(dbg, irg, bl, last_size, elms, mode_Int);
183
184                                         newn = new_rd_Add(dbg, irg, bl, newn, n, mode);
185                                 }
186                         } else {
187                                 /* no array type */
188                                 ir_mode *idx_mode = get_irn_mode(index);
189                                 tarval *tv = new_tarval_from_long(get_mode_size_bytes(basemode), idx_mode);
190
191                                 newn = new_rd_Add(dbg, irg, bl, get_Sel_ptr(sel),
192                                         new_rd_Mul(dbg, irg, bl, index,
193                                         new_r_Const(irg, get_irg_start_block(irg), idx_mode, tv),
194                                         idx_mode),
195                                         mode);
196                         }
197                 } else if (is_Method_type(get_entity_type(ent)) &&
198                            is_Class_type(owner) &&
199                            (owner != get_glob_type()) &&
200                            (!is_frame_type(owner)))  {
201                         ir_node *add;
202                         ir_mode *ent_mode = get_type_mode(get_entity_type(ent));
203
204                         /* We need an additional load when accessing methods from a dispatch table. */
205                         tv   = new_tarval_from_long(get_entity_offset(ent), mode_Int);
206                         cnst = new_rd_Const(dbg, irg, get_irg_start_block(irg), mode_Int, tv);
207                         add  = new_rd_Add(dbg, irg, bl, get_Sel_ptr(sel), cnst, mode);
208 #ifdef DO_CACHEOPT  /* cacheopt version */
209                         newn = new_rd_Load(dbg, irg, bl, get_Sel_mem(sel), sel, ent_mode);
210                         cacheopt_map_addrs_register_node(newn);
211                         set_Load_ptr(newn, add);
212 #else /* normal code */
213                         newn = new_rd_Load(dbg, irg, bl, get_Sel_mem(sel), add, ent_mode);
214 #endif
215                         newn = new_r_Proj(irg, bl, newn, ent_mode, pn_Load_res);
216
217                 } else if (get_entity_owner(ent) != get_glob_type()) {
218                         int offset;
219
220                         /* replace Sel by add(obj, const(ent.offset)) */
221                         assert(!(get_entity_allocation(ent) == allocation_static &&
222                                 (get_entity_n_overwrites(ent) == 0 && get_entity_n_overwrittenby(ent) == 0)));
223                         newn   = get_Sel_ptr(sel);
224                         offset = get_entity_offset(ent);
225                         if (offset != 0) {
226                                 tv = new_tarval_from_long(offset, mode_Int);
227                                 cnst = new_r_Const(irg, get_irg_start_block(irg), mode_Int, tv);
228                                 newn = new_rd_Add(dbg, irg, bl, newn, cnst, mode);
229                         }
230                 } else {
231                         /* global_type */
232                         newn = new_rd_SymConst_addr_ent(NULL, current_ir_graph, mode, ent, firm_unknown_type);
233                 }
234         }
235         /* run the hooks */
236         hook_lower(sel);
237
238         exchange(sel, newn);
239 }  /* lower_sel */
240
241 /**
242  * Lower a all possible SymConst nodes.
243  */
244 static void lower_symconst(ir_node *symc) {
245         ir_node       *newn;
246         ir_type       *tp;
247         ir_entity     *ent;
248         tarval        *tv;
249         ir_enum_const *ec;
250         ir_mode       *mode;
251
252         switch (get_SymConst_kind(symc)) {
253         case symconst_type_tag:
254                 assert(!"SymConst kind symconst_type_tag not implemented");
255                 break;
256         case symconst_type_size:
257                 /* rewrite the SymConst node by a Const node */
258                 tp   = get_SymConst_type(symc);
259                 assert(get_type_state(tp) == layout_fixed);
260                 mode = get_irn_mode(symc);
261                 tv   = new_tarval_from_long(get_type_size_bytes(tp), mode);
262                 newn = new_r_Const(current_ir_graph,
263                                    get_irg_start_block(current_ir_graph),
264                                    get_irn_mode(symc), tv);
265                 assert(newn);
266                 /* run the hooks */
267                 hook_lower(symc);
268                 exchange(symc, newn);
269                 break;
270         case symconst_type_align:
271                 /* rewrite the SymConst node by a Const node */
272                 tp   = get_SymConst_type(symc);
273                 assert(get_type_state(tp) == layout_fixed);
274                 mode = get_irn_mode(symc);
275                 tv   = new_tarval_from_long(get_type_alignment_bytes(tp), mode);
276                 newn = new_r_Const(current_ir_graph,
277                                    get_irg_start_block(current_ir_graph),
278                                    mode, tv);
279                 assert(newn);
280                 /* run the hooks */
281                 hook_lower(symc);
282                 exchange(symc, newn);
283                 break;
284         case symconst_addr_name:
285                 /* do not rewrite - pass info to back end */
286                 break;
287         case symconst_addr_ent:
288                 /* leave */
289                 break;
290         case symconst_ofs_ent:
291                 /* rewrite the SymConst node by a Const node */
292                 ent  = get_SymConst_entity(symc);
293                 assert(get_type_state(get_entity_type(ent)) == layout_fixed);
294                 mode = get_irn_mode(symc);
295                 tv   = new_tarval_from_long(get_entity_offset(ent), mode);
296                 newn = new_r_Const(current_ir_graph,
297                                    get_irg_start_block(current_ir_graph),
298                                    mode, tv);
299                 assert(newn);
300                 /* run the hooks */
301                 hook_lower(symc);
302                 exchange(symc, newn);
303                 break;
304         case symconst_enum_const:
305                 /* rewrite the SymConst node by a Const node */
306                 ec   = get_SymConst_enum(symc);
307                 assert(get_type_state(get_enumeration_owner(ec)) == layout_fixed);
308                 tv   = get_enumeration_value(ec);
309                 newn = new_r_Const(current_ir_graph,
310                                   get_irg_start_block(current_ir_graph),
311                                   get_irn_mode(symc), tv);
312                 assert(newn);
313                 /* run the hooks */
314                 hook_lower(symc);
315                 exchange(symc, newn);
316                 break;
317         case symconst_label:
318                 /* leave */
319                 break;
320
321         default:
322                 assert(!"unknown SymConst kind");
323                 break;
324         }
325 }  /* lower_symconst */
326
327 /**
328  * Checks, whether a size is an integral size
329  *
330  * @param size  the size on bits
331  */
332 static int is_integral_size(int size) {
333         /* must be a 2^n */
334         if (size & (size-1))
335                 return 0;
336         /* must be at least byte size */
337         return size >= 8;
338 }  /* is_integral_size */
339
340 /**
341  * lower bitfield load access.
342  *
343  * @param proj  the Proj(result) node
344  * @param load  the Load node
345  */
346 static void lower_bitfields_loads(ir_node *proj, ir_node *load) {
347         ir_node *sel = get_Load_ptr(load);
348         ir_node *block, *n_proj, *res, *ptr;
349         ir_entity *ent;
350         ir_type *bf_type;
351         ir_mode *bf_mode, *mode;
352         int offset, bit_offset, bits, bf_bits, old_cse;
353         dbg_info *db;
354
355         if (get_irn_op(sel) != op_Sel)
356                 return;
357
358         ent     = get_Sel_entity(sel);
359         bf_type = get_entity_type(ent);
360
361         /* must be a bitfield type */
362         if (!is_Primitive_type(bf_type) || get_primitive_base_type(bf_type) == NULL)
363                 return;
364
365         /* We have a bitfield access, if either a bit offset is given, or
366            the size is not integral. */
367         bf_mode = get_type_mode(bf_type);
368         if (! bf_mode)
369                 return;
370
371         mode       = get_irn_mode(proj);
372         block      = get_nodes_block(proj);
373         bf_bits    = get_mode_size_bits(bf_mode);
374         bit_offset = get_entity_offset_bits_remainder(ent);
375
376         if (bit_offset == 0 && is_integral_size(bf_bits) && bf_mode == get_Load_mode(load))
377                 return;
378
379         bits   = get_mode_size_bits(mode);
380         offset = get_entity_offset(ent);
381
382         /*
383          * ok, here we are: now convert the Proj_mode_bf(Load) into And(Shr(Proj_mode(Load)) for unsigned
384          * and Shr(Shl(Proj_mode(load)) for signed
385          */
386
387         /* abandon bitfield sel */
388         ptr = get_Sel_ptr(sel);
389         db  = get_irn_dbg_info(sel);
390         ptr = new_rd_Add(db, current_ir_graph, block, ptr, new_Const_long(mode_Is, offset), get_irn_mode(ptr));
391
392         set_Load_ptr(load, ptr);
393         set_Load_mode(load, mode);
394
395
396         /* create new proj, switch off CSE or we may get the old one back */
397         old_cse = get_opt_cse();
398         set_opt_cse(0);
399         res = n_proj = new_r_Proj(current_ir_graph, block, load, mode, pn_Load_res);
400         set_opt_cse(old_cse);
401
402         if (mode_is_signed(mode)) { /* signed */
403                 int shift_count_up    = bits - (bf_bits + bit_offset);
404                 int shift_count_down  = bits - bf_bits;
405
406                 if (shift_count_up) {
407                         res = new_r_Shl(current_ir_graph, block, res,
408                                 new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(shift_count_up, mode_Iu)), mode);
409                 }
410                 if (shift_count_down) {
411                         res = new_r_Shrs(current_ir_graph, block, res,
412                                 new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(shift_count_down, mode_Iu)), mode);
413                 }
414         } else { /* unsigned */
415                 int shift_count_down  = bit_offset;
416                 unsigned mask = ((unsigned)-1) >> (bits - bf_bits);
417
418                 if (shift_count_down) {
419                         res = new_r_Shr(current_ir_graph, block, res,
420                                 new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(shift_count_down, mode_Iu)), mode);
421                 }
422                 if (bits != bf_bits) {
423                         res = new_r_And(current_ir_graph, block, res,
424                                 new_r_Const(current_ir_graph, block, mode, new_tarval_from_long(mask, mode)), mode);
425                 }
426         }
427
428         exchange(proj, res);
429 }  /* lower_bitfields_loads */
430
431 /**
432  * lower bitfield store access.
433  *
434  * @todo: It adds a load which may produce an exception!
435  */
436 static void lower_bitfields_stores(ir_node *store) {
437         ir_node   *sel = get_Store_ptr(store);
438         ir_node   *ptr, *value;
439         ir_entity *ent;
440         ir_type *bf_type;
441         ir_mode *bf_mode, *mode;
442         ir_node *mem, *irn, *block;
443         unsigned mask, neg_mask;
444         int bf_bits, bits_mask, offset, bit_offset;
445         dbg_info *db;
446
447         /* check bitfield access */
448         if (get_irn_op(sel) != op_Sel)
449                 return;
450
451         ent     = get_Sel_entity(sel);
452         bf_type = get_entity_type(ent);
453
454         /* must be a bitfield type */
455         if (!is_Primitive_type(bf_type) || get_primitive_base_type(bf_type) == NULL)
456                 return;
457
458         /* We have a bitfield access, if either a bit offset is given, or
459            the size is not integral. */
460         bf_mode = get_type_mode(bf_type);
461         if (! bf_mode)
462                 return;
463
464         value      = get_Store_value(store);
465         mode       = get_irn_mode(value);
466         block      = get_nodes_block(store);
467
468         bf_bits    = get_mode_size_bits(bf_mode);
469         bit_offset = get_entity_offset_bits_remainder(ent);
470
471         if (bit_offset == 0 && is_integral_size(bf_bits) && bf_mode == get_irn_mode(value))
472                 return;
473
474         /*
475          * ok, here we are: now convert the Store(Sel(), value) into Or(And(Load(Sel),c), And(Value,c))
476          */
477         mem        = get_Store_mem(store);
478         offset     = get_entity_offset(ent);
479
480         bits_mask = get_mode_size_bits(mode) - bf_bits;
481         mask = ((unsigned)-1) >> bits_mask;
482         mask <<= bit_offset;
483         neg_mask = ~mask;
484
485         /* abandon bitfield sel */
486         ptr = get_Sel_ptr(sel);
487         db  = get_irn_dbg_info(sel);
488         ptr = new_rd_Add(db, current_ir_graph, block, ptr, new_Const_long(mode_Is, offset), get_irn_mode(ptr));
489
490         if (neg_mask) {
491                 /* there are some bits, normal case */
492                 irn  = new_r_Load(current_ir_graph, block, mem, ptr, mode);
493                 mem  = new_r_Proj(current_ir_graph, block, irn, mode_M, pn_Load_M);
494                 irn  = new_r_Proj(current_ir_graph, block, irn, mode, pn_Load_res);
495
496                 irn = new_r_And(current_ir_graph, block, irn,
497                         new_r_Const(current_ir_graph, block, mode, new_tarval_from_long(neg_mask, mode)), mode);
498
499                 if (bit_offset > 0) {
500                         value = new_r_Shl(current_ir_graph, block, value,
501                                 new_r_Const(current_ir_graph, block, mode_Iu, new_tarval_from_long(bit_offset, mode_Iu)), mode);
502                 }
503
504                 value = new_r_And(current_ir_graph, block, value,
505                         new_r_Const(current_ir_graph, block, mode, new_tarval_from_long(mask, mode)), mode);
506
507                 value = new_r_Or(current_ir_graph, block, value, irn, mode);
508         }
509
510         set_Store_mem(store, mem);
511         set_Store_value(store, value);
512         set_Store_ptr(store, ptr);
513 }  /* lower_bitfields_stores */
514
515 /**
516  * Lowers unaligned Loads.
517  */
518 static void lower_unaligned_Load(ir_node *load) {
519   (void) load;
520         /* NYI */
521 }
522
523 /**
524  * Lowers unaligned Stores
525  */
526 static void lower_unaligned_Store(ir_node *store) {
527         (void) store;
528         /* NYI */
529 }
530
531 /**
532  * lowers IR-nodes, called from walker
533  */
534 static void lower_irnode(ir_node *irn, void *env) {
535         (void) env;
536         switch (get_irn_opcode(irn)) {
537         case iro_Sel:
538                 lower_sel(irn);
539                 break;
540         case iro_SymConst:
541                 lower_symconst(irn);
542                 break;
543         case iro_Load:
544                 if (env != NULL && get_Load_align(irn) == align_non_aligned)
545                         lower_unaligned_Load(irn);
546                 break;
547         case iro_Store:
548                 if (env != NULL && get_Store_align(irn) == align_non_aligned)
549                         lower_unaligned_Store(irn);
550                 break;
551         case iro_Cast:
552                 exchange(irn, get_Cast_op(irn));
553                 break;
554         default:
555                 break;
556         }
557 }  /* lower_irnode */
558
559 /**
560  * Walker: lowers IR-nodes for bitfield access
561  */
562 static void lower_bf_access(ir_node *irn, void *env) {
563         (void) env;
564         switch (get_irn_opcode(irn)) {
565         case iro_Proj:
566         {
567                 long proj     = get_Proj_proj(irn);
568                 ir_node *pred = get_Proj_pred(irn);
569                 ir_op *op     = get_irn_op(pred);
570
571                 if ((proj == pn_Load_res) && (op == op_Load))
572                         lower_bitfields_loads(irn, pred);
573                 break;
574         }
575         case iro_Store:
576                 lower_bitfields_stores(irn);
577                 break;
578
579         default:
580                 break;
581         }
582 }  /* lower_bf_access */
583
584 /*
585  * Replaces SymConsts by a real constant if possible.
586  * Replace Sel nodes by address computation.  Also resolves array access.
587  * Handle Bitfields by added And/Or calculations.
588  */
589 void lower_highlevel_graph(ir_graph *irg, int lower_bitfields) {
590
591         if(lower_bitfields) {
592                 /* First step: lower bitfield access: must be run as long as Sels still
593                  * exists. */
594                 irg_walk_graph(irg, NULL, lower_bf_access, NULL);
595         }
596
597         /* Finally: lower SymConst-Size and Sel nodes, Casts, unaligned Load/Stores. */
598         irg_walk_graph(irg, NULL, lower_irnode, NULL);
599         set_irg_phase_low(irg);
600 }  /* lower_highlevel */
601
602 void lower_const_code(void) {
603         walk_const_code(NULL, lower_irnode, NULL);
604 }
605
606 /*
607  * Replaces SymConsts by a real constant if possible.
608  * Replace Sel nodes by address computation.  Also resolves array access.
609  * Handle Bitfields by added And/Or calculations.
610  */
611 void lower_highlevel(int lower_bitfields) {
612         int i, n;
613
614         n = get_irp_n_irgs();
615         for (i = 0; i < n; ++i) {
616                 ir_graph *irg = get_irp_irg(i);
617                 lower_highlevel_graph(irg, lower_bitfields);
618         }
619         lower_const_code();
620 }  /* lower_highlevel */