disabled show after showgraph, as it is (or was?) buggy
[libfirm] / ir / ana2 / pto_name.c
1 /* -*- c -*- */
2
3 /*
4   Project:     libFIRM
5   File name:   ir/ana/pto_name.c
6   Purpose:     Names for abstract objects
7   Author:      Florian
8   Modified by:
9   Created:     Sat Nov 13 19:35:27 CET 2004
10   CVS-ID:      $Id$
11   Copyright:   (c) 1999-2004 Universit�t Karlsruhe
12   Licence:     This file is protected by the GPL -  GNU GENERAL PUBLIC LICENSE.
13 */
14
15 # ifdef HAVE_CONFIG_H
16 #  include "config.h"
17 # endif
18
19 /*
20   pto_name: Names for abstract objects
21 */
22
23 # include "pto.h"
24 # include "pto_name.h"
25 # include "pto_util.h"
26
27 #include <assert.h>
28
29 #ifdef HAVE_STRING_H
30 # include <string.h>            /* for memcpy */
31 #endif
32 # include <obstack.h>
33 # include <errno.h>
34
35 # include "irnode.h"
36 # include "irprog.h"
37 # include "xmalloc.h"
38
39 # include "pto_debug.h"
40 # include "gnu_ext.h"
41
42 /* Local Defines: */
43 # define obstack_chunk_alloc xmalloc
44 # define obstack_chunk_free free
45
46 # define NALLOC(size)   obstack_alloc (name_obst, size)
47
48 /* Local Data Types: */
49
50 /* Local Variables: */
51 struct obstack *qset_obst = NULL;
52 struct obstack *name_obst = NULL;
53
54 static desc_t *all_descs = NULL;
55
56 static int name_id = 0;
57
58 # define PTO_COLOR
59
60 # ifdef PTO_COLOR
61 static int last_col_idx = 0;
62
63 /* Local Prototypes: */
64 static int pto_name_alloc_color (desc_t*);
65 static void pto_name_set_color (desc_t*, int);
66 # endif /* defined PTO_COLOR */
67
68 /* ===================================================
69    Local Implementation:
70    =================================================== */
71 # ifdef PTO_COLOR
72 /* set a nice color to an object descriptor */
73 static void pto_name_set_obj_color (obj_desc_t *obj_desc, int col_idx)
74 {
75   int i;
76
77   for (i = 0; i < obj_desc->n_fields; i ++) {
78     qset_t *ptos = obj_desc->values [i];
79
80     desc_t *tgt = (desc_t*) qset_start (ptos);
81
82     while (NULL != tgt) {
83       pto_name_set_color (tgt, col_idx);
84
85       tgt = (desc_t*) qset_next (ptos);
86     }
87   }
88 }
89
90 /* set a nice color to an array descriptor */
91 static void pto_name_set_arr_color (arr_desc_t *arr_desc, int col_idx)
92 {
93   qset_t *ptos = arr_desc->value;
94
95   desc_t *tgt = (desc_t*) qset_start (ptos);
96
97   while (NULL != tgt) {
98     pto_name_set_color (tgt, col_idx);
99
100     tgt = (desc_t*) qset_next (ptos);
101   }
102 }
103
104 /* set a nice color to a descriptor */
105 static void pto_name_set_color (desc_t *desc, int col_idx)
106 {
107   /* assert (0 == desc->col_idx); */
108
109   desc->col_idx = col_idx;
110
111   if (FALSE == desc->visit) {
112     desc->visit = TRUE;
113     if (object == desc->kind) {
114       pto_name_set_obj_color ((obj_desc_t*) desc, col_idx);
115     } else if (array == desc->kind) {
116       pto_name_set_arr_color ((arr_desc_t*) desc, col_idx);
117     }
118
119     desc->visit = FALSE;
120   }
121 }
122
123
124 /* allocate nice colors for an object descriptor */
125 static int pto_name_alloc_obj_color (obj_desc_t *obj_desc)
126 {
127   int i;
128   int col_idx = 0;
129
130   for (i = 0; (0 == col_idx) && (i < obj_desc->n_fields); i ++) {
131     qset_t *ptos = obj_desc->values [i];
132     desc_t *tgt = (desc_t*) qset_start (ptos);
133
134     while ((0 == col_idx) && (NULL != tgt)) {
135       col_idx = pto_name_alloc_color (tgt);
136
137       tgt = (desc_t*) qset_next (ptos);
138     }
139   }
140
141   return (col_idx);
142 }
143
144 /* allocate nice colors for an array descriptor */
145 static int pto_name_alloc_arr_color (arr_desc_t *arr_desc)
146 {
147   int col_idx = 0;
148
149   qset_t *ptos = arr_desc->value;
150
151   desc_t *tgt = (desc_t*) qset_start (ptos);
152
153   while ((NULL != tgt) && (0 == col_idx)) {
154     col_idx = pto_name_alloc_color (tgt);
155     tgt = (desc_t*) qset_next (ptos);
156   }
157
158   return (col_idx);
159 }
160
161 /* allocate nice colors for the given descriptor */
162 static int pto_name_alloc_color (desc_t *desc)
163 {
164   int col_idx = 0;
165
166   if (0 != desc->col_idx) {
167     return (desc->col_idx);
168   }
169
170   if (FALSE == desc->visit) {
171     desc->visit = TRUE;
172     if (object == desc->kind) {
173       col_idx = pto_name_alloc_obj_color ((obj_desc_t*) desc);
174     } else if (array == desc->kind) {
175       col_idx = pto_name_alloc_arr_color ((arr_desc_t*) desc);
176     }
177     desc->visit = FALSE;
178   }
179
180   if (0 == col_idx) {
181     col_idx = ++ last_col_idx;
182   }
183
184   pto_name_set_color (desc, col_idx);
185
186   return (col_idx);
187 }
188
189 /* allocate nice colors */
190 static void pto_name_alloc_colors (void)
191 {
192   desc_t *desc = all_descs;
193
194   while (NULL != desc) {
195     pto_name_alloc_color (desc);
196
197     desc = desc->prev;
198   }
199 }
200 # endif /* defined PTO_COLOR */
201
202 /* See whether the given entity is a field. */
203 static int is_field (ir_entity *ent)
204 {
205   ir_type *tp = get_entity_type (ent);
206
207   if (is_Primitive_type (tp) || is_Pointer_type (tp)) {
208     /* actually, we don't get by by restricting ourselves to pointer types */
209     return (TRUE);
210   } else {
211     return (FALSE);
212   }
213 }
214
215 /* Helper to collect_fields(ir_type*): collect all fields of the given
216   clazz and its super classes into the given obstack. */
217 static void _collect_fields (ir_type *clazz, struct obstack *obst)
218 {
219   int n_members = get_class_n_members (clazz);
220   int n_supers  = get_class_n_supertypes (clazz);
221   int i;
222
223   for (i = 0; i < n_members; i ++) {
224     ir_entity *ent = get_class_member (clazz, i);
225
226     if (is_field (ent)) {
227       if (allocation_static != get_entity_allocation (ent)) {
228         obstack_ptr_grow (obst, ent);
229       }
230     }
231   }
232
233   for (i = 0; i < n_supers; i ++) {
234     ir_type *s_clazz = get_class_supertype (clazz, i);
235
236     _collect_fields (s_clazz, obst);
237   }
238 }
239
240 /* Collect the fields of the given class and its super classes into an array.
241   The last entry of the array is written NULL. */
242 static ir_entity **collect_fields (ir_type *clazz)
243 {
244   struct obstack obst;
245   int n_fields;
246   ir_entity ** fields;
247   void *tmp;
248
249   if (NULL != get_type_link (clazz)) {
250     DBGPRINT (3, (stdout, "%s: reusing field list for \"%s\"\n",
251                   __FUNCTION__,
252                   get_type_name (clazz)));
253
254     return ((ir_entity **) get_type_link (clazz));
255   } else {
256     DBGPRINT (2, (stdout, "%s: new field list for \"%s\"\n",
257                   __FUNCTION__,
258                   get_type_name (clazz)));
259   }
260
261   obstack_init (&obst);
262
263   _collect_fields (clazz, &obst);
264
265   /* append terminating NULL */
266   obstack_ptr_grow (&obst, NULL);
267
268   n_fields = obstack_object_size (&obst) / sizeof (void*);
269
270   fields = NALLOC (n_fields * sizeof (ir_entity*));
271   tmp = obstack_finish(&obst);
272
273   memcpy (fields, tmp, n_fields * sizeof (ir_entity*));
274
275   obstack_free (&obst, NULL);
276
277   set_type_link (clazz, fields);
278
279   return (fields);
280 }
281
282 /* Write the intro text for a name dump into the given stream */
283 static void pto_name_dump_start (FILE *stream)
284 {
285 # ifdef PTO_COLOR
286   pto_name_alloc_colors ();
287 # endif /* defined PTO_COLOR */
288
289   fprintf (stream, "digraph \"Names\" {\n");
290   fprintf (stream, "\tgraph [rankdir=\"LR\", ordering=\"out\", size=\"11,7\", rotate=\"90\"];\n");
291   fprintf (stream, "\tnode [shape=\"record\", style=\"filled\"];\n");
292   fprintf (stream, "\tedge [color=\"black\"];\n");
293   fprintf (stream, "\n");
294 }
295
296 /* Write the extro text for a name dump into the given stream */
297 static void pto_name_dump_finish (FILE *stream)
298 {
299   fprintf (stream, "}\n");
300 }
301
302 /* Write a node for the given descriptor into the given stream */
303 static void pto_name_dump_desc (desc_t *desc, FILE *stream)
304 {
305   ir_type *tp = desc->tp;
306   const char *tp_name = get_type_name (tp);
307   ir_node *nd;
308
309   fprintf (stream, "\t/* %s \"%s\" */\n",
310            object == desc->kind ? "Object" : "Array",
311            tp_name);
312
313   fprintf (stream, "\tdesc_%i [label=\"<HEAD>type \\[%i\\]",
314            desc->id, desc->id);
315
316   if (-1 != desc->ctx) {
317     fprintf (stream, ", ctx = %i", desc->ctx);
318   } else {
319     fprintf (stream, " (global)");
320   }
321
322   fprintf (stream, "\\lname=\\\"%s\\\"",
323            tp_name);
324
325   nd = desc->node;
326
327   if (NULL != nd) {
328     ir_graph *graph = get_irn_irg (nd);
329     ir_entity *method = get_irg_entity (graph);
330     const char *ent_name = get_entity_name (method);
331     const char *own_name = get_type_name (get_entity_owner (method));
332
333     fprintf (stream, "\\lnode=%s\\[%li\\]",
334              get_op_name (get_irn_op (nd)),
335              get_irn_node_nr (nd));
336     fprintf (stream, "\\lgraph=\\\"%s.%s\\\"",
337              own_name,
338              ent_name);
339   }
340
341   if (desc->kind == object) {
342     obj_desc_t *obj_desc = (obj_desc_t*) desc;
343
344     int i;
345     for (i = 0; i < obj_desc->n_fields; i ++) {
346       ir_entity *field = obj_desc->fields [i];
347
348       if (is_Pointer_type (get_entity_type (field))) {
349         const char *ent_name = get_entity_name (field);
350
351         fprintf (stream, "|<%i>%s", i, ent_name);
352       }
353     }
354   } else if (array == desc->kind) {
355     fprintf (stream, "|<arr>[]");
356   } else {
357     assert (0 && "invalid descriptor");
358   }
359
360   /* end label string */
361   fprintf (stream, "\"");
362
363 # ifdef PTO_COLOR
364   {
365     const char *fontcolor;
366     int col_idx = desc->col_idx;
367     float hue = (float) col_idx / (float) last_col_idx;
368     float sat = 1.000f;            /* 0.300 .. 1.000 */
369     float val = 0.800f;            /* 0.300 .. 1.000 */
370
371   # define MAX_COLORS 12
372     if (last_col_idx > MAX_COLORS) {
373       /* too many colors ... vary value too */
374       float div = (float) MAX_COLORS / (float) last_col_idx;
375
376       sat = (div * ((col_idx / MAX_COLORS)));
377       val = (div * ((col_idx / MAX_COLORS)));
378
379       col_idx = col_idx % MAX_COLORS;
380       hue = (float) col_idx / (float) MAX_COLORS;
381
382       // re-adjust sat and val
383       {
384         const float sat_min = 0.200f; /* 0.200 .. 0.400 */
385         const float val_min = 0.300f; /* 0.300 .. 0.400 */
386
387         sat = sat_min + ((1.0f - sat_min) * sat);
388         val = val_min + ((1.0f - val_min) * val);
389       }
390     }
391   # undef MAX_COLORS
392
393     fprintf (stream, ", color=\"%01.3f, %01.3f, %01.3f\"", hue, sat, val);
394
395     if ((hue > 0.3) && (sat < 0.5)) {
396       fontcolor = "white";
397     } else if (sat < 0.4) {
398       fontcolor = "white";
399     } else {
400       fontcolor = "black";
401     }
402
403     fprintf (stream, ", fontcolor=\"%s\"", fontcolor);
404   }
405 # else /* if defined PTO_COLOR */
406   fprintf (stream, ", color=\"lightgrey\"");
407 # endif /* defined PTO_COLOR */
408
409   /* end attributes */
410   fprintf (stream, "];\n");
411   fprintf (stream, "\n");
412
413   /* now the edges */
414   if (desc->kind == object) {
415     obj_desc_t *obj_desc = (obj_desc_t*) desc;
416
417     int i;
418     for (i = 0; i < obj_desc->n_fields; i ++) {
419       desc_t *tgt = (desc_t*) qset_start (obj_desc->values [i]);
420
421       while (NULL != tgt) {
422         fprintf (stream, "\tdesc_%i:%i -> desc_%i:HEAD;\n",
423                  desc->id, i, tgt->id);
424
425         tgt = (desc_t*) qset_next (obj_desc->values [i]);
426       }
427     }
428   } else if (array == desc->kind) {
429     arr_desc_t *arr_desc = (arr_desc_t*) desc;
430
431     desc_t *tgt = (desc_t*) qset_start (arr_desc->value);
432
433     while (NULL != tgt) {
434       fprintf (stream, "\tdesc_%i:arr -> desc_%i:HEAD;\n",
435                desc->id, tgt->id);
436
437       tgt = (desc_t*) qset_next (arr_desc->value);
438     }
439   }
440
441   fprintf (stream, "\n");
442 }
443
444
445 /* ===================================================
446    Exported Implementation:
447    =================================================== */
448 /* Find the given descriptor's entry for the given entity */
449 qset_t *get_entry (desc_t *desc, ir_entity *ent)
450 {
451
452   if (desc->kind == object) {
453     obj_desc_t *obj_desc = (obj_desc_t*) desc;
454     int i;
455     const int n_fields = obj_desc->n_fields;
456
457     for (i = 0; i < n_fields; i ++) {
458       if (ent == obj_desc->fields [i]) {
459         return (obj_desc->values [i]);
460       }
461     }
462
463     assert (0 && "entry not found");
464   } else if (desc->kind == array) {
465     arr_desc_t *arr_desc = (arr_desc_t*) desc;
466
467     return (arr_desc->value);
468   } else {
469     assert (0 && "invalid descriptor");
470   }
471   return NULL;
472 }
473
474
475 /* get a new descriptor for the given type at the given node */
476 desc_t *new_name (ir_type *tp, ir_node *node, int ctx)
477 {
478   desc_t *desc = NULL;
479
480   assert ((is_Class_type (tp) || is_Array_type (tp)) && "unsuitable type");
481
482   DBGPRINT (2, (stdout, "%s: new name for type \"%s\"\n",
483                 __FUNCTION__,
484                 get_type_name (tp)));
485   fflush (stdout);
486
487   if (is_Class_type (tp)) {
488     obj_desc_t *obj_desc = NALLOC (sizeof (obj_desc_t));
489     int i;
490     int n_fields;
491
492     obj_desc->kind = object;
493     obj_desc->fields = collect_fields (tp);
494
495     for (n_fields = 0; (NULL != obj_desc->fields [n_fields]); n_fields ++) {
496       /* nothing, just count ... */
497     }
498
499     obj_desc->n_fields = n_fields;
500     obj_desc->values = (qset_t**) NALLOC (n_fields * sizeof (qset_t*));
501
502     for (i = 0; i < n_fields; i ++) {
503       obj_desc->values [i] = qset_new (N_INITIAL_OJBS, qset_obst);
504     }
505
506     desc = (desc_t*) obj_desc;
507   } else if (is_Array_type (tp)) {
508     arr_desc_t *arr_desc = (arr_desc_t*) NALLOC (sizeof (arr_desc_t));
509
510     arr_desc->kind = array;
511     arr_desc->value = qset_new (N_INITIAL_OJBS, qset_obst);
512
513     desc = (desc_t*) arr_desc;
514   }
515
516   desc->id    = name_id ++;
517   desc->col_idx = 0;
518   desc->tp    = tp;
519   desc->visit = FALSE;
520   desc->ctx   = ctx;
521   desc->node  = node;
522
523   desc->prev  = all_descs;
524   all_descs = desc;
525
526   return (desc);
527 }
528
529 # define N_GLOB_INITIAL_FIELDS  20
530 static obj_desc_t *obj_glob = NULL;
531 static int n_glob_fields = N_GLOB_INITIAL_FIELDS;
532
533 /* get a new descriptor for the given (presumably static) entity */
534 desc_t *new_ent_name (ir_entity *ent)
535 {
536   int i;
537   int missing = TRUE;
538   ir_type *tp = get_entity_type (ent);
539
540   assert (is_Pointer_type (tp));
541   tp = get_pointer_points_to_type (tp);
542   assert (is_Class_type (tp));
543
544   DBGPRINT (2, (stdout, "%s: new name for entity \"%s\"\n",
545                 __FUNCTION__,
546                 get_entity_name (ent)));
547   DBGEXE (2, (fflush (stdout)));
548
549   assert (((allocation_static == get_entity_allocation (ent)) ||
550            (allocation_automatic == get_entity_allocation (ent))) &&
551           "not a static/automatic field");
552
553   if (NULL == obj_glob) {
554     obj_glob = (obj_desc_t*) NALLOC (sizeof (obj_desc_t));
555
556     obj_glob->id   = name_id ++;
557     obj_glob->ctx  = -1;
558     obj_glob->col_idx = 0;
559     obj_glob->visit = FALSE;
560     obj_glob->kind = object;
561     obj_glob->tp   = get_glob_type ();
562     obj_glob->node = NULL;
563
564     obj_glob->n_fields = 0;
565     obj_glob->fields = (ir_entity**) NALLOC (N_GLOB_INITIAL_FIELDS * sizeof (ir_entity*));
566     obj_glob->values = (qset_t**) NALLOC (N_GLOB_INITIAL_FIELDS * sizeof (qset_t*));
567
568     obj_glob->prev = all_descs;
569     all_descs = (desc_t*) obj_glob;
570   }
571
572   for (i = 0; missing && (i < obj_glob->n_fields); i ++) {
573     if (ent == obj_glob->fields [i]) {
574       missing = FALSE;
575     }
576   }
577
578   if (missing) {
579     if (obj_glob->n_fields == n_glob_fields) {
580       ir_entity **fields = obj_glob->fields;
581       qset_t **values = obj_glob->values;
582
583       n_glob_fields *= 2;
584       obj_glob->fields = (ir_entity**) NALLOC (n_glob_fields * sizeof (ir_entity*));
585       obj_glob->values = (qset_t**) NALLOC (n_glob_fields * sizeof (qset_t*));
586
587       memcpy (obj_glob->fields, fields, obj_glob->n_fields * sizeof (ir_entity*));
588       memcpy (obj_glob->values, values, obj_glob->n_fields * sizeof (qset_t*));
589
590       /* free (fields); */
591       /* free (values); */
592     }
593
594     obj_glob->fields [obj_glob->n_fields   ] = ent;
595     obj_glob->values [obj_glob->n_fields ++] = qset_new (N_INITIAL_OJBS, qset_obst);
596   }
597
598   return ((desc_t*) obj_glob);
599 }
600 # undef N_GLOB_INITIAL_FIELDS
601
602 /* Dump all names to a file of the given name */
603 void pto_dump_names (const char *name)
604 {
605   desc_t *desc = all_descs;
606   FILE *stream = fopen (name, "w");
607
608   errno = 0;
609   if  (NULL == stream) {
610     fprintf (stderr, "%s: unable to open %s (%s)\n",
611              __FUNCTION__, name, strerror (errno));
612     return;
613   }
614
615   pto_name_dump_start (stream);
616
617   while (NULL != desc) {
618     pto_name_dump_desc (desc, stream);
619
620     desc = desc->prev;
621   }
622
623   pto_name_dump_finish (stream);
624   fclose (stream);
625 }
626
627 /* Initialise the name module */
628 void pto_name_init (void)
629 {
630   DBGPRINT (3, (stdout, "%s\n", __FUNCTION__));
631   assert (NULL == name_obst);
632   assert (NULL == qset_obst);
633
634   name_obst = xmalloc (sizeof (struct obstack));
635   qset_obst = xmalloc (sizeof (struct obstack));
636
637   obstack_init (name_obst);
638   obstack_init (qset_obst);
639 }
640
641 /* Cleanup the name module */
642 void pto_name_cleanup (void)
643 {
644   DBGPRINT (3, (stdout, "%s\n", __FUNCTION__));
645   obstack_free (name_obst, NULL);
646   obstack_free (qset_obst, NULL);
647
648   memset (name_obst, 0x00, sizeof (struct obstack));
649   memset (qset_obst, 0x00, sizeof (struct obstack));
650
651   free (name_obst);
652   free (qset_obst);
653
654   name_obst = NULL;
655   qset_obst = NULL;
656 }
657
658 \f
659 /*
660   $Log$
661   Revision 1.19  2006/12/13 19:46:47  beck
662   rename type entity into ir_entity
663
664   Revision 1.18  2006/01/13 22:56:21  beck
665   renamed all types 'type' to 'ir_type'
666
667   Revision 1.17  2005/12/16 16:59:54  grund
668   *** empty log message ***
669
670   Revision 1.16  2005/12/05 12:19:54  beck
671   added missing include <assert.h> (not anymore included in libFirm)
672
673   Revision 1.15  2005/03/02 10:14:38  beck
674   placed a return on all execution pathes
675
676   Revision 1.14  2005/02/17 08:45:38  liekweg
677   Don't return a value for an invalid descriptor
678
679   Revision 1.13  2005/02/11 10:21:28  beck
680   get_entry now always returns a value
681
682   Revision 1.12  2005/01/14 14:13:56  liekweg
683   fix gnu extension, fix fprintf's, fix allocs
684
685   Revision 1.11  2005/01/05 14:25:54  beck
686   renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG fronten
687
688   Revision 1.10  2004/12/22 14:43:14  beck
689   made allocations C-like
690
691   Revision 1.9  2004/12/21 15:34:09  beck
692   removed C99 constructs
693   make const float
694   add default return
695
696   Revision 1.8  2004/12/15 13:30:30  liekweg
697   use DBGEXE correctly; print yet nicer names
698
699   Revision 1.7  2004/12/15 09:18:18  liekweg
700   pto_name.c
701
702   Revision 1.6  2004/12/06 12:52:09  liekweg
703   colorize name dump
704
705   Revision 1.4  2004/11/30 15:49:27  liekweg
706   include 'dump'
707
708   Revision 1.3  2004/11/30 14:47:54  liekweg
709   fix initialisation; do correct iteration
710
711   Revision 1.2  2004/11/24 14:53:56  liekweg
712   Bugfixes
713
714   Revision 1.1  2004/11/18 16:37:34  liekweg
715   rewritten
716
717
718 */