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