Added a phase that normalizes the proj positions
[libfirm] / ir / ir / irgraph.c
1 /*
2  * Project:     libFIRM
3  * File name:   ir/ir/irgraph.c
4  * Purpose:     Entry point to the representation of procedure code.
5  * Author:      Martin Trapp, Christian Schaefer
6  * Modified by: Goetz Lindenmaier
7  * Created:
8  * CVS-ID:      $Id$
9  * Copyright:   (c) 1998-2003 Universität Karlsruhe
10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
11  */
12
13 #ifdef HAVE_CONFIG_H
14 # include <config.h>
15 #endif
16
17 # include <string.h>
18
19 # include "ircons.h"
20 # include "irgraph_t.h"
21 # include "irprog_t.h"
22 # include "irnode_t.h"
23 # include "iropt_t.h"
24 # include "irflag_t.h"
25 # include "array.h"
26 # include "irgmod.h"
27 # include "mangle.h"
28 # include "irouts.h"
29 # include "firmstat.h"
30
31 ir_graph *current_ir_graph;
32 INLINE ir_graph *get_current_ir_graph(void) {
33   return current_ir_graph;
34 }
35 INLINE void set_current_ir_graph(ir_graph *graph) {
36   current_ir_graph = graph;
37 }
38
39
40 int __interprocedural_view = false;
41
42 int (get_interprocedural_view)(void) {
43   return __get_interprocedural_view();
44 }
45
46 void (set_interprocedural_view)(int state) {
47   __interprocedural_view = state;
48
49   /* set function vectors for faster access */
50   if (state) {
51     __get_irn_arity = __get_irn_inter_arity;
52     __get_irn_n     = __get_irn_inter_n;
53   }
54   else {
55     __get_irn_arity = __get_irn_intra_arity;
56     __get_irn_n     = __get_irn_intra_n;
57   }
58 }
59
60 static ident* frame_type_suffix = NULL;
61 void init_irgraph(void) {
62   frame_type_suffix = new_id_from_chars(FRAME_TP_SUFFIX, strlen(FRAME_TP_SUFFIX));
63 }
64
65 #if USE_EXPLICIT_PHI_IN_STACK
66 /* really defined in ircons.c */
67 typedef struct Phi_in_stack Phi_in_stack;
68 Phi_in_stack *new_Phi_in_stack();
69 void free_Phi_in_stack(Phi_in_stack *s);
70 #endif
71
72 /* Allocates a list of nodes:
73     - The start block containing a start node and Proj nodes for it's four
74       results (X, M, P, Tuple).
75     - The end block containing an end node. This block is not matured after
76       new_ir_graph as predecessors need to be added to it.
77     - The current block, which is empty and also not matured.
78    Further it allocates several datastructures needed for graph construction
79    and optimization.
80 */
81 ir_graph *
82 new_r_ir_graph (entity *ent, int n_loc)
83 {
84   ir_graph *res;
85   ir_node *first_block;
86   ir_node *projX;
87
88   res = (ir_graph *) malloc (sizeof (ir_graph));
89   memset(res, 0, sizeof (ir_graph));
90   res->kind = k_ir_graph;
91
92   /* inform statistics here, as blocks will be already build on this graph */
93   stat_new_graph(res, ent);
94
95   current_ir_graph = res;
96
97   /*-- initialized for each graph. --*/
98   if (get_opt_precise_exc_context()) {
99     res->n_loc = n_loc + 1 + 1; /* number of local variables that are never
100                    dereferenced in this graph plus one for
101                    the store plus one for links to fragile
102                    operations.  n_loc is not the number of
103                    parameters to the procedure!  */
104   }
105   else {
106     res->n_loc = n_loc + 1;  /* number of local variables that are never
107                 dereferenced in this graph plus one for
108                 the store. This is not the number of parameters
109                 to the procedure!  */
110   }
111
112   res->visited = 0;     /* visited flag, for the ir walker */
113   res->block_visited = 0; /* visited flag, for the 'block'-walker */
114
115 #if USE_EXPLICIT_PHI_IN_STACK
116   res->Phi_in_stack = new_Phi_in_stack();  /* A stack needed for automatic Phi
117                                 generation */
118 #endif
119   res->kind = k_ir_graph;
120   res->obst      = (struct obstack *) xmalloc (sizeof (struct obstack));
121   obstack_init (res->obst);
122   res->value_table = new_identities (); /* value table for global value
123                        numbering for optimizing use in
124                        iropt.c */
125   res->outs = NULL;
126
127   res->phase_state    = phase_building;
128   res->op_pin_state_pinned = op_pin_state_pinned;
129   res->outs_state     = outs_none;
130   res->dom_state      = dom_none;
131   res->typeinfo_state = irg_typeinfo_none;
132   res->loopinfo_state = loopinfo_none;
133
134   /*-- Type information for the procedure of the graph --*/
135   res->ent = ent;
136   set_entity_irg(ent, res);
137
138   /*--  a class type so that it can contain "inner" methods as in Pascal. --*/
139   res->frame_type = new_type_class(mangle(get_entity_ident(ent), frame_type_suffix));
140
141   /* Remove type from type list.  Must be treated differently than other types. */
142   remove_irp_type_from_list(res->frame_type);
143
144   /*-- Nodes needed in every graph --*/
145   res->end_block  = new_immBlock();
146   res->end        = new_End();
147   res->end_reg    = res->end;
148   res->end_except = res->end;
149
150   res->start_block = new_immBlock();
151   res->start   = new_Start();
152   res->bad     = new_ir_node(NULL, res, res->start_block, op_Bad, mode_T, 0, NULL);
153   res->no_mem  = new_ir_node(NULL, res, res->start_block, op_NoMem, mode_M, 0, NULL);
154
155   /* Proj results of start node */
156   projX            = new_Proj (res->start, mode_X, pn_Start_X_initial_exec);
157   res->frame       = new_Proj (res->start, mode_P_mach, pn_Start_P_frame_base);
158   res->globals     = new_Proj (res->start, mode_P_mach, pn_Start_P_globals);
159   res->initial_mem = new_Proj (res->start, mode_M, pn_Start_M);
160   res->args        = new_Proj (res->start, mode_T, pn_Start_T_args);
161 #ifdef DEBUG_libfirm
162   res->graph_nr    = get_irp_new_node_nr();
163 #endif
164
165   set_store(res->initial_mem);
166
167   add_immBlock_pred(res->start_block, projX);
168   /*
169    * The code generation needs it. leave it in now.
170    * Use of this edge is matter of discussion, unresolved. Also possible:
171    * add_immBlock_pred(res->start_block, res->start_block), but invalid typed.
172    */
173   mature_immBlock (res->current_block);
174
175   /*-- Make a block to start with --*/
176   first_block = new_immBlock();
177   add_immBlock_pred (first_block, projX);
178
179   return res;
180 }
181
182
183 ir_graph *
184 new_ir_graph (entity *ent, int n_loc)
185 {
186   ir_graph *res = new_r_ir_graph (ent, n_loc);
187   add_irp_irg(res);          /* remember this graph global. */
188   return res;
189 }
190
191 /* Make a rudimentary ir graph for the constant code.
192    Must look like a correct irg, spare everything else. */
193 ir_graph *new_const_code_irg(void) {
194   ir_graph *res;
195   ir_node *projX;
196
197   res = (ir_graph *) malloc (sizeof(*res));
198   memset(res, 0, sizeof(*res));
199
200   /* inform statistics here, as blocks will be already build on this graph */
201   stat_new_graph(res, NULL);
202
203   current_ir_graph = res;
204   res->n_loc = 1;       /* Only the memory. */
205   res->visited = 0;     /* visited flag, for the ir walker */
206   res->block_visited=0; /* visited flag, for the 'block'-walker */
207 #if USE_EXPLICIT_PHI_IN_STACK
208   res->Phi_in_stack = NULL;
209 #endif
210   res->kind = k_ir_graph;
211   res->obst      = (struct obstack *) xmalloc (sizeof (struct obstack));
212   obstack_init (res->obst);
213   res->phase_state = phase_building;
214   res->op_pin_state_pinned = op_pin_state_pinned;
215   res->value_table = new_identities (); /* value table for global value
216                        numbering for optimizing use in
217                        iropt.c */
218   res->ent = NULL;
219   res->frame_type  = NULL;
220   res->start_block = new_immBlock ();
221   res->end_block  = new_immBlock ();
222   res->end        = new_End ();
223   res->end_reg    = res->end;
224   res->end_except = res->end;
225   mature_immBlock(get_cur_block());  /* mature the end block */
226   res->bad     = new_ir_node (NULL, res, res->start_block, op_Bad, mode_T, 0, NULL);
227   res->no_mem  = new_ir_node (NULL, res, res->start_block, op_NoMem, mode_M, 0, NULL);
228   res->start   = new_Start ();
229   res->initial_mem = new_Proj (res->start, mode_M, pn_Start_M);
230
231   /* Proj results of start node */
232   projX        = new_Proj (res->start, mode_X, pn_Start_X_initial_exec);
233   add_immBlock_pred (res->start_block, projX);
234   mature_immBlock   (res->start_block);  /* mature the start block */
235
236   add_immBlock_pred (new_immBlock (), projX);
237   mature_immBlock   (get_cur_block());   /* mature the 'body' block for expressions */
238   /* Set the visited flag high enough that the block will never be visited. */
239   set_irn_visited(get_cur_block(), -1);
240   set_Block_block_visited(get_cur_block(), -1);
241   set_Block_block_visited(res->start_block, -1);
242   set_irn_visited(res->start_block, -1);
243   set_irn_visited(res->bad, -1);
244   set_irn_visited(res->no_mem, -1);
245
246   res->phase_state = phase_high;
247   return res;
248 }
249
250 /* Defined in iropt.c */
251 void  del_identities (pset *value_table);
252
253 /* Frees the passed irgraph.
254    Deallocates all nodes in this graph and the ir_graph structure.
255    Sets the field irgraph in the corresponding entity to NULL.
256    Does not remove the irgraph from the list in irprog (requires
257    inefficient search, call remove_irp_irg by hand).
258    Does not free types, entities or modes that are used only by this
259    graph, nor the entity standing for this graph. */
260 void free_ir_graph (ir_graph *irg) {
261
262   stat_free_graph(irg);
263   if (irg->outs_state != outs_none) free_outs(irg);
264   if (irg->frame_type)  free_type(irg->frame_type);
265   if (irg->value_table) del_identities(irg->value_table);
266   if (irg->ent) {
267     peculiarity pec = get_entity_peculiarity (irg->ent);
268     set_entity_peculiarity (irg->ent, peculiarity_description);
269     set_entity_irg(irg->ent, NULL);  /* not set in const code irg */
270     set_entity_peculiarity (irg->ent, pec);
271   }
272
273   free_End(irg->end);
274   obstack_free(irg->obst,NULL);
275   free(irg->obst);
276 #if USE_EXPLICIT_PHI_IN_STACK
277   free_Phi_in_stack(irg->Phi_in_stack);
278 #endif
279   irg->kind = k_BAD;
280   free(irg);
281 }
282
283 /* access routines for all ir_graph attributes:
284    templates:
285    {attr type} get_irg_{attribute name} (ir_graph *irg);
286    void set_irg_{attr name} (ir_graph *irg, {attr type} {attr}); */
287
288 int
289 (is_ir_graph)(const void *thing) {
290   return __is_ir_graph(thing);
291 }
292
293 /* Outputs a unique number for this node */
294
295 INLINE long
296 get_irg_graph_nr(ir_graph *irg) {
297   assert(irg);
298 #ifdef DEBUG_libfirm
299   return irg->graph_nr;
300 #else
301   return (long)irg;
302 #endif
303 }
304
305 ir_node *
306 (get_irg_start_block)(const ir_graph *irg) {
307   return __get_irg_start_block(irg);
308 }
309
310 void
311 (set_irg_start_block)(ir_graph *irg, ir_node *node) {
312   __set_irg_start_block(irg, node);
313 }
314
315 ir_node *
316 (get_irg_start)(const ir_graph *irg) {
317   return __get_irg_start(irg);
318 }
319
320 void
321 (set_irg_start)(ir_graph *irg, ir_node *node) {
322   __set_irg_start(irg, node);
323 }
324
325 ir_node *
326 (get_irg_end_block)(const ir_graph *irg) {
327   return __get_irg_end_block(irg);
328 }
329
330 void
331 (set_irg_end_block)(ir_graph *irg, ir_node *node) {
332   __set_irg_end_block(irg, node);
333 }
334
335 ir_node *
336 (get_irg_end)(const ir_graph *irg) {
337   return __get_irg_end(irg);
338 }
339
340 void
341 (set_irg_end)(ir_graph *irg, ir_node *node) {
342   __set_irg_end(irg, node);
343 }
344
345 ir_node *
346 (get_irg_end_reg)(const ir_graph *irg) {
347   return __get_irg_end_reg(irg);
348 }
349
350 void     set_irg_end_reg (ir_graph *irg, ir_node *node) {
351   assert(get_irn_op(node) == op_EndReg || get_irn_op(node) == op_End);
352   irg->end_reg = node;
353 }
354
355 ir_node *
356 (get_irg_end_except)(const ir_graph *irg) {
357   return __get_irg_end_except(irg);
358 }
359
360 void     set_irg_end_except (ir_graph *irg, ir_node *node) {
361   assert(get_irn_op(node) == op_EndExcept || get_irn_op(node) == op_End);
362   irg->end_except = node;
363 }
364
365 ir_node *
366 (get_irg_cstore)(const ir_graph *irg) {
367   return __get_irg_cstore(irg);
368 }
369
370 void
371 (set_irg_cstore)(ir_graph *irg, ir_node *node) {
372   __set_irg_cstore(irg, node);
373 }
374
375 ir_node *
376 (get_irg_frame)(const ir_graph *irg) {
377   return __get_irg_frame(irg);
378 }
379
380 void
381 (set_irg_frame)(ir_graph *irg, ir_node *node) {
382   __set_irg_frame(irg, node);
383 }
384
385 ir_node *
386 (get_irg_globals)(const ir_graph *irg) {
387   return __get_irg_globals(irg);
388 }
389
390 void
391 (set_irg_globals)(ir_graph *irg, ir_node *node) {
392   __set_irg_globals(irg, node);
393 }
394
395 ir_node *
396 (get_irg_initial_mem)(const ir_graph *irg) {
397   return __get_irg_initial_mem(irg);
398 }
399
400 void
401 (set_irg_initial_mem)(ir_graph *irg, ir_node *node) {
402   __set_irg_initial_mem(irg, node);
403 }
404
405 ir_node *
406 (get_irg_args)(const ir_graph *irg) {
407   return __get_irg_args(irg);
408 }
409
410 void
411 (set_irg_args)(ir_graph *irg, ir_node *node) {
412   __set_irg_args(irg, node);
413 }
414
415 ir_node *
416 (get_irg_bad)(const ir_graph *irg) {
417   return __get_irg_bad(irg);
418 }
419
420 void
421 (set_irg_bad)(ir_graph *irg, ir_node *node) {
422   __set_irg_bad(irg, node);
423 }
424
425 ir_node *
426 (get_irg_no_mem)(const ir_graph *irg) {
427   return __get_irg_no_mem(irg);
428 }
429
430 void
431 (set_irg_no_mem)(ir_graph *irg, ir_node *node) {
432   __set_irg_no_mem(irg, node);
433 }
434
435 ir_node *
436 (get_irg_current_block)(const ir_graph *irg) {
437   return __get_irg_current_block(irg);
438 }
439
440 void
441 (set_irg_current_block)(ir_graph *irg, ir_node *node) {
442   __set_irg_current_block(irg, node);
443 }
444
445 entity *
446 (get_irg_entity)(const ir_graph *irg) {
447   return __get_irg_entity(irg);
448 }
449
450 void
451 (set_irg_entity)(ir_graph *irg, entity *ent) {
452   __set_irg_entity(irg, ent);
453 }
454
455 type *
456 (get_irg_frame_type)(const ir_graph *irg) {
457   return __get_irg_frame_type(irg);
458 }
459
460 void
461 (set_irg_frame_type)(ir_graph *irg, type *ftp) {
462   __set_irg_frame_type(irg, ftp);
463 }
464
465
466 /* To test for a frame type */
467 int
468 is_frame_type(const type *ftp) {
469   int i;
470   if (is_class_type(ftp)) {
471     for (i = 0; i < get_irp_n_irgs(); i++) {
472       const type *frame_tp = get_irg_frame_type(get_irp_irg(i));
473       if (ftp == frame_tp) return true;
474     }
475   }
476   return false;
477 }
478
479 int
480 get_irg_n_locs (ir_graph *irg)
481 {
482   if (get_opt_precise_exc_context())
483     return irg->n_loc - 1 - 1;
484   else
485     return irg->n_loc - 1;
486 }
487
488 void
489 set_irg_n_loc (ir_graph *irg, int n_loc)
490 {
491   if (get_opt_precise_exc_context())
492     irg->n_loc = n_loc + 1 + 1;
493   else
494     irg->n_loc = n_loc + 1;
495 }
496
497
498
499 /* Returns the obstack associated with the graph. */
500 struct obstack *
501 (get_irg_obstack)(const ir_graph *irg) {
502   return __get_irg_obstack(irg);
503 }
504
505 /*
506  * Returns true if the node n is allocated on the storage of graph irg.
507  *
508  * Implementation is GLIBC specific as is uses the internal _obstack_chunk implementation.
509  */
510 int node_is_in_irgs_storage(ir_graph *irg, ir_node *n)
511 {
512   struct _obstack_chunk *p;
513
514   /*
515    * checks wheater the ir_node pointer i on the obstack.
516    * A more sophisticated check would test the "whole" ir_node
517    */
518   for (p = irg->obst->chunk; p; p = p->prev) {
519     if (((char *)p->contents <= (char *)n) && ((char *)n < (char *)p->limit))
520       return 1;
521   }
522
523   return 0;
524 }
525
526 irg_phase_state
527 (get_irg_phase_state)(const ir_graph *irg) {
528   return __get_irg_phase_state(irg);
529 }
530
531 void
532 (set_irg_phase_low)(ir_graph *irg) {
533   __set_irg_phase_low(irg);
534 }
535
536 op_pin_state
537 (get_irg_pinned)(const ir_graph *irg) {
538   return __get_irg_pinned(irg);
539 }
540
541 irg_outs_state
542 (get_irg_outs_state)(const ir_graph *irg) {
543   return __get_irg_outs_state(irg);
544 }
545
546 void
547 (set_irg_outs_inconsistent)(ir_graph *irg) {
548   __set_irg_outs_inconsistent(irg);
549 }
550
551 irg_dom_state
552 (get_irg_dom_state)(const ir_graph *irg) {
553   return __get_irg_dom_state(irg);
554 }
555
556 void
557 (set_irg_dom_inconsistent)(ir_graph *irg) {
558   __set_irg_dom_inconsistent(irg);
559 }
560
561 irg_loopinfo_state
562 (get_irg_loopinfo_state)(const ir_graph *irg) {
563   return __get_irg_loopinfo_state(irg);
564 }
565
566 void
567 (set_irg_loopinfo_state)(ir_graph *irg, irg_loopinfo_state s) {
568   __set_irg_loopinfo_state(irg, s);
569 }
570
571 void
572 set_irg_loopinfo_inconsistent(ir_graph *irg) {
573   if (irg->loopinfo_state == loopinfo_ip_consistent)
574     irg->loopinfo_state = loopinfo_ip_inconsistent;
575
576   else if (irg->loopinfo_state == loopinfo_consistent)
577     irg->loopinfo_state = loopinfo_inconsistent;
578
579   else if (irg->loopinfo_state == loopinfo_cf_ip_consistent)
580     irg->loopinfo_state = loopinfo_cf_ip_inconsistent;
581
582   else if (irg->loopinfo_state == loopinfo_cf_consistent)
583     irg->loopinfo_state = loopinfo_cf_inconsistent;
584 }
585
586 void
587 (set_irg_pinned)(ir_graph *irg, op_pin_state p) {
588   __set_irg_pinned(irg, p);
589 }
590
591 irg_callee_info_state
592 (get_irg_callee_info_state)(const ir_graph *irg) {
593   return __get_irg_callee_info_state(irg);
594 }
595
596 void
597 (set_irg_callee_info_state)(ir_graph *irg, irg_callee_info_state s) {
598   __set_irg_callee_info_state(irg, s);
599 }
600
601 irg_inline_property
602 (get_irg_inline_property)(const ir_graph *irg) {
603   return __get_irg_inline_property(irg);
604 }
605
606 void
607 (set_irg_inline_property)(ir_graph *irg, irg_inline_property s) {
608   __set_irg_inline_property(irg, s);
609 }
610
611 void
612 (set_irg_link)(ir_graph *irg, void *thing) {
613   __set_irg_link(irg, thing);
614 }
615
616 void *
617 (get_irg_link)(const ir_graph *irg) {
618   return __get_irg_link(irg);
619 }
620
621 /* maximum visited flag content of all ir_graph visited fields. */
622 static int max_irg_visited = 0;
623
624 unsigned long
625 (get_irg_visited)(const ir_graph *irg) {
626   return __get_irg_visited(irg);
627 }
628
629 void
630 set_irg_visited (ir_graph *irg, unsigned long visited)
631 {
632   irg->visited = visited;
633   if (irg->visited > max_irg_visited) {
634     max_irg_visited = irg->visited;
635   }
636 }
637
638 void
639 inc_irg_visited (ir_graph *irg)
640 {
641   if (++irg->visited > max_irg_visited) {
642     max_irg_visited = irg->visited;
643   }
644 }
645
646 unsigned long
647 get_max_irg_visited(void)
648 {
649   /*
650   int i;
651   for(i = 0; i < get_irp_n_irgs(); i++)
652   assert(max_irg_visited >= get_irg_visited(get_irp_irg(i)));
653    */
654   return max_irg_visited;
655 }
656
657 void set_max_irg_visited(int val) {
658   max_irg_visited = val;
659 }
660
661 unsigned long
662 inc_max_irg_visited(void)
663 {
664   /*
665   int i;
666   for(i = 0; i < get_irp_n_irgs(); i++)
667   assert(max_irg_visited >= get_irg_visited(get_irp_irg(i)));
668   */
669   max_irg_visited++;
670   return max_irg_visited;
671 }
672
673 unsigned long
674 (get_irg_block_visited)(const ir_graph *irg) {
675   return __get_irg_block_visited(irg);
676 }
677
678 void
679 (set_irg_block_visited)(ir_graph *irg, unsigned long visited) {
680   __set_irg_block_visited(irg, visited);
681 }
682
683 void
684 (inc_irg_block_visited)(ir_graph *irg) {
685   __inc_irg_block_visited(irg);
686 }
687
688
689 /**
690  * walker Start->End: places Proj nodes into the same block
691  * as it's predecessors
692  *
693  * @param n    the node
694  * @param env  ignored
695  */
696 static void normalize_proj_walker(ir_node *n, void *env)
697 {
698   if (is_Proj(n)) {
699     ir_node *pred  = get_Proj_pred(n);
700     ir_node *block = get_nodes_block(pred);
701
702     set_nodes_block(n, block);
703   }
704 }
705
706 /* put the proj's into the same block as its predecessors */
707 void normalize_proj_nodes(ir_graph *irg)
708 {
709   irg_walk_graph(irg, NULL, normalize_proj_walker, NULL);
710 }