nsz Git - libfirm/blob - ir/ana2/typalise.c

   1 /* -*- c -*- */
   2
   3 /*
   4  * Project:     libFIRM
   5  * File name:   ir/ana2/pto.c
   6  * Purpose:     Pto
   7  * Author:      Florian
   8  * Modified by:
   9  * Created:     Mon 18 Oct 2004
  10  * CVS-ID:      $Id$
  11  * Copyright:   (c) 1999-2004 Universität Karlsruhe
  12  * Licence:     This file is protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  13  */
  14
  15
  16 # ifdef HAVE_CONFIG_H
  17 #  include "config.h"
  18 # endif
  19
  20 # include "typalise.h"
  21
  22 # ifndef TRUE
  23 #  define TRUE 1
  24 #  define FALSE 0
  25 # endif /* not defined TRUE */
  26
  27 # include <assert.h>
  28
  29 #ifdef HAVE_STRING_H
  30 # include <string.h>
  31 #endif
  32
  33 # include "irnode_t.h"
  34 # include "irgwalk.h"
  35 # include "xmalloc.h"
  36 # include "gnu_ext.h"
  37
  38
  39 /*
  40   Local Globals
  41 */
  42
  43 static long ta_id = 0;
  44
  45 /*
  46   Local Protos
  47 */
  48 static typalise_t *typalise_proj (ir_node*);
  49
  50
  51 /*
  52   Ctors, Dtors for typalise_t-s
  53 */
  54 static typalise_t *ta_exact (type *tp)
  55 {
  56   typalise_t *ta = xmalloc (sizeof (typalise_t));
  57   ta->kind = type_exact;
  58   ta->res.type = tp;
  59   ta->id = ta_id ++;
  60
  61   assert (is_Class_type (tp));
  62
  63   return (ta);
  64 }
  65
  66 static typalise_t *ta_types (lset_t *set)
  67 {
  68   typalise_t *ta = xmalloc (sizeof (typalise_t));
  69   ta->kind = type_types;
  70   ta->res.types = set;
  71   ta->id = ta_id ++;
  72
  73   return (ta);
  74 }
  75
  76 static typalise_t *ta_type (type *tp)
  77 {
  78   typalise_t *ta = xmalloc (sizeof (typalise_t));
  79   ta->kind = type_type;
  80   ta->res.type = tp;
  81   ta->id = ta_id ++;
  82
  83   assert (is_Class_type (tp));
  84
  85   return (ta);
  86 }
  87
  88 static void ta_delete (typalise_t *ta)
  89 {
  90   if (type_types == ta->kind) {
  91     lset_destroy (ta->res.types);
  92     ta->res.types = NULL;
  93   } else {
  94     ta->res.type = NULL;
  95   }
  96
  97   ta->kind = type_invalid;
  98
  99   free (ta);
 100 }
 101
 102 /*
 103   Helpers for inheritance, overwriting and stuff
 104 */
 105 /**
 106    Find out whether otype is a subtype of stype.
 107    Return non-zero iff otype is a subtype of stype.
 108 */
 109 static int is_subtype (type *otype, type *stype)
 110 {
 111   int n_sub = get_class_n_subtypes (stype);
 112   int is_sub = FALSE;
 113   int i;
 114
 115   if (otype == stype) {
 116     return (TRUE);
 117   }
 118
 119   for (i = 0; (!is_sub) && (i < n_sub); i ++) {
 120     type *sub = get_class_subtype (stype, i);
 121
 122     is_sub |= is_subtype (otype, sub);
 123   }
 124
 125
 126   return (is_sub);
 127 }
 128
 129
 130 /**
 131     Compute the closure of all subtypes of otype (including otype
 132     itself)
 133 */
 134 static void _collect_subtypes (type *otype, lset_t *set)
 135 {
 136   int i, n_sub;
 137
 138   lset_insert (set, otype);
 139
 140   n_sub = get_class_n_subtypes (otype);
 141   for (i = 0; i < n_sub; i ++) {
 142     type *sub = get_class_subtype (otype, i);
 143
 144     _collect_subtypes (sub, set);
 145   }
 146 }
 147
 148 static lset_t *subtype_closure (type *otype)
 149 {
 150   lset_t *set = lset_create ();
 151
 152   _collect_subtypes (otype, set);
 153
 154   return (set);
 155 }
 156
 157 /**
 158    Helper method for get_owner_types
 159 */
 160 static void _collect_owner_types (entity *method, ir_graph *graph, lset_t *tps)
 161 {
 162   int i, n_over;
 163
 164   /* search DOWNwards in clazz hierarchy */
 165
 166   if ((peculiarity_description == get_entity_peculiarity (method)) ||
 167       (peculiarity_inherited   == get_entity_peculiarity (method))) {
 168     lset_insert (tps, get_entity_owner (method));
 169   } else if (peculiarity_existent == get_entity_peculiarity (method)) {
 170     ir_graph *ex_graph = get_entity_irg (method);
 171
 172     if ((NULL == ex_graph) || (ex_graph == graph)) {
 173       /* wtf? they define the same graph again? well, whatever: */
 174       lset_insert (tps, get_entity_owner (method));
 175     } else {
 176       /* aha: they define a new graph. can't have that, so bail out */
 177       return;
 178     }
 179   }
 180
 181   n_over = get_entity_n_overwrittenby (method);
 182   for (i = 0; i < n_over; i ++) {
 183     entity *ometh = get_entity_overwrittenby (method, i);
 184
 185     _collect_owner_types (ometh, graph, tps);
 186   }
 187 }
 188
 189
 190 /**
 191    Collect all classes that use the given implementation of a method.
 192 */
 193 static lset_t *get_owner_types (ir_graph *graph)
 194 {
 195   lset_t *tps = lset_create ();
 196   entity *meth = get_irg_entity (graph);
 197
 198   _collect_owner_types (meth, graph, tps);
 199
 200   return (tps);
 201 }
 202
 203 /**
 204    Return a list containing all types of 'set' which are a subtype of 'type'.
 205 */
 206 static lset_t *filter_for_type (lset_t *set, type *stype)
 207 {
 208   type *curs = (type*) lset_first (set);
 209   lset_t *lset = lset_create ();
 210
 211   while (NULL != curs) {
 212     if (is_subtype (curs, stype)) {
 213       lset_insert (lset, curs);
 214     }
 215
 216     curs = lset_next (set);
 217   }
 218
 219   return (lset);
 220 }
 221
 222 /*
 223  Handle typalise_t-s
 224 */
 225 /**
 226     Join 'one' and 'two'; both args are deallocated, result is freshly
 227     allocated.
 228 */
 229 static typalise_t *ta_join (typalise_t *one, typalise_t *two)
 230 {
 231   typalise_t *res = NULL;
 232
 233   switch (one->kind) {
 234   case (type_invalid): { /* shut up, gcc */ }
 235   case (type_exact): {
 236     switch (two->kind) {
 237     case (type_invalid): { /* shut up, gcc */ }
 238     case (type_exact): {
 239       if (one->res.type == two->res.type) {
 240         res = one;
 241       } else {
 242         lset_t *set = lset_create ();
 243         lset_insert (set, one->res.type);
 244         lset_insert (set, two->res.type);
 245         res = ta_types (set);
 246
 247         ta_delete (one);
 248       }
 249
 250       ta_delete (two);
 251     } break;
 252     case (type_types): {
 253       lset_insert (two->res.types, one->res.type);
 254       ta_delete (one);
 255
 256       res = two;
 257     } break;
 258     case (type_type): {
 259       if (is_subtype (one->res.type, two->res.type)) {
 260         ta_delete (one);
 261         res = two;
 262       } else {
 263         lset_t *closure = subtype_closure (two->res.type);
 264         lset_insert (closure, one->res.type);
 265
 266         ta_delete (two);
 267
 268         res = one;
 269       }
 270     } break;
 271     }
 272   } break;
 273   case (type_types): {
 274     switch (two->kind) {
 275     case (type_invalid): { /* shut up, gcc */ }
 276     case (type_exact): {
 277       res = ta_join (two, one);
 278     } break;
 279     case (type_types): {
 280       lset_insert_all (one->res.types, two->res.types);
 281       ta_delete (two);
 282
 283       res = one;
 284     } break;
 285     case (type_type): {
 286       lset_t *closure = subtype_closure (two->res.type);
 287       lset_append (one->res.types, closure);
 288
 289       ta_delete (two);
 290
 291       res = one;
 292     } break;
 293     }
 294   } break;
 295   case (type_type): {
 296     switch (two->kind) {
 297     case (type_invalid): { /* shut up, gcc */ }
 298     case (type_exact): {
 299       res = ta_join (two, one);
 300     } break;
 301     case (type_types): {
 302       res = ta_join (two, one);
 303     } break;
 304     case (type_type): {
 305       type *one_type = one->res.type;
 306       type *two_type = two->res.type;
 307
 308       if (is_subtype (one_type, two_type)) {
 309         ta_delete (one);
 310         res = two;
 311       } else if (is_subtype (two_type, one_type)) {
 312         ta_delete (two);
 313         res = one;
 314       } else {
 315         lset_t *one_closure = subtype_closure (one->res.type);
 316         lset_t *two_closure = subtype_closure (two->res.type);
 317
 318         lset_append (one_closure, two_closure);
 319
 320         ta_delete (two);
 321         ta_delete (one);
 322
 323         res = ta_types (one_closure);
 324       }
 325     } break;
 326     }
 327   } break;
 328   }
 329
 330   assert (res && "no result");
 331
 332   return (res);
 333 }
 334
 335
 336 # ifdef SHUT_UP_GCC
 337 static const char *ta_name (typalise_t *ta)
 338 {
 339 # define BUF_SIZE 1024
 340   static char buf [BUF_SIZE];
 341
 342   int len = sprintf (buf, "[%d] ", ta->id);
 343
 344   switch (ta->kind) {
 345   case (type_invalid): { /* shut up, gcc */ }
 346   case (type_exact): {
 347     len += sprintf (buf+len, "only ");
 348     strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
 349   } break;
 350   case (type_types): {
 351     len += sprintf (buf+len, "one_of ");
 352
 353     type *iter = lset_first (ta->res.types);
 354
 355     int size = BUF_SIZE - len - 1;
 356     while ((NULL != iter) && (0 < size)) {
 357       char *dest = strncat (buf, get_type_name (iter), size);
 358       size = (dest - buf);
 359
 360       iter = lset_next (ta->res.types);
 361     }
 362   } break;
 363   case (type_type): {
 364     len += sprintf (buf+len, "poly ");
 365     strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
 366   } break;
 367   }
 368
 369   return (buf);
 370   /* # undef BUF_SIZE */
 371 }
 372 # endif /* SHUT_UP_GCC */
 373
 374 /**
 375    Find out whether the given clazz uses the given implementation of a
 376    method.  Presumably, this is because clazz inherits the graph as
 377    the implementation for a method.
 378 */
 379 static int uses_graph (type *clazz, entity *meth, ir_graph *graph)
 380 {
 381   type *g_clazz = get_entity_owner (meth);
 382   int i, n_over, use = FALSE;
 383
 384   if (g_clazz == clazz) {
 385     return (TRUE);
 386   }
 387
 388   if (peculiarity_existent == get_entity_peculiarity (meth)) {
 389     ir_graph *g_graph = get_entity_irg (meth);
 390
 391     if (g_graph != graph) {
 392       return (FALSE);
 393     }
 394   }
 395
 396   /* else inherited or description */
 397   n_over = get_entity_n_overwrittenby (meth); /* DOWN-wards */
 398   for (i = 0; (i < n_over) && (!use); i ++) {
 399     entity *over = get_entity_overwrittenby (meth, i);
 400
 401     use |= uses_graph (clazz, over, graph);
 402   }
 403
 404   return (use);
 405 }
 406
 407 /**
 408    Check whether the given typalise_t includes the given type.
 409 */
 410 static int ta_supports (typalise_t *ta, ir_graph *graph)
 411 {
 412   switch (ta->kind) {
 413   case (type_invalid): { /* shut up, gcc */ }
 414   case (type_exact): {
 415     int res = FALSE;
 416     lset_t *tps = get_owner_types (graph);
 417
 418     if (lset_contains (tps, ta->res.type)) {
 419       res = TRUE;
 420     }
 421
 422     lset_destroy (tps);
 423
 424     return (res);
 425   }
 426   case (type_type): {
 427     entity *meth = get_irg_entity (graph);
 428     type *tp = get_entity_owner (meth);
 429     int res = is_subtype (tp, ta->res.type);
 430
 431     if (res) {
 432       return (TRUE);
 433     } else {
 434       res = uses_graph (ta->res.type, meth, graph);
 435     }
 436
 437     return (res);
 438   }
 439   case (type_types): {
 440     type *tp = get_entity_owner (get_irg_entity (graph));
 441
 442     return (lset_contains (ta->res.types, tp));
 443   }
 444   }
 445
 446   assert (0 && "invalid ta");
 447   return FALSE;
 448 }
 449
 450
 451 /* =========== WHAT ELSE ? =========== */
 452
 453 /*
 454   Helper to typalise (ir_node*)
 455 */
 456 /**
 457     Find an approximation to the given proj node's value's types
 458 */
 459 static typalise_t *typalise_proj (ir_node *proj)
 460 {
 461   typalise_t *res = NULL;
 462   ir_node *proj_in = get_Proj_pred (proj);
 463
 464   if (iro_Proj  == get_irn_opcode (proj_in)) {
 465     /* fprintf (stdout, "\tProj (Proj)\n"); */
 466
 467     proj_in = get_Proj_pred (proj_in);
 468     if (iro_Start == get_irn_opcode (proj_in)) {
 469       ir_graph *graph = get_irn_irg (proj);
 470       entity   *meth  = get_irg_entity (graph);
 471
 472       long n = get_Proj_proj (proj);
 473
 474       if (1 == n) {
 475         /* yay proj this */
 476         type     *tp    = get_entity_owner (meth);
 477
 478         /* res = ta_exact (tp); */
 479         res = ta_type (tp);     /* TODO */
 480       } else {
 481         /* ugh proj arg */
 482         type *tp = get_method_param_type (get_entity_type (meth), n);
 483         if (is_Pointer_type (tp)) {
 484           tp = get_pointer_points_to_type (tp);
 485         }
 486
 487         res = ta_type (tp);
 488       }
 489     } else if (iro_Call == get_irn_opcode (proj_in)) {
 490       /* call result ... 'whatever' */
 491       /* hey, this is redundant (or the check for iro_Call further down) */
 492       ir_node *call_ptr = get_Call_ptr (proj_in);
 493
 494       res = typalise (call_ptr);
 495     } else {
 496       fprintf (stdout, "\n Proj (Proj (%s)) not handled\n",
 497                get_op_name (get_irn_op (proj_in)));
 498       assert (0);
 499     }
 500   } else {
 501     opcode op = get_irn_opcode (proj_in);
 502     if ((iro_Load != op) && (iro_Alloc != op) && (iro_Call != op)) {
 503       fprintf (stdout, "\n Proj (%s) not handled\n",
 504                get_op_name (get_irn_op (proj_in)));
 505       assert (0);
 506     }
 507     res = typalise (proj_in);      /* everything else */
 508     /* Proj (Load), Proj (New), Proj (Call) */
 509   }
 510
 511   return (res);
 512 }
 513
 514
 515
 516 /*
 517   Public Interface
 518 */
 519 /**
 520    Given a set of graphs and a typalise_t,  return the method (s) in
 521    the set that are supported by the typalise_t.  Also, deallocates
 522    the given set.
 523 */
 524 lset_t *filter_for_ta (lset_t *set, typalise_t *ta)
 525 {
 526   lset_t *res = lset_create ();
 527   ir_graph *curs = (ir_graph*) lset_first (set);
 528
 529   while (NULL != curs) {
 530     if (ta_supports (ta, curs)) {
 531       lset_insert (res, curs);
 532     }
 533
 534     curs = lset_next (set);
 535   }
 536
 537   lset_destroy (set);
 538
 539   return (res);
 540 }
 541
 542 /**
 543    For the given ptr, do a quick check about what (class) types may be
 544    brought along on it.
 545 */
 546 typalise_t *typalise (ir_node *node)
 547 {
 548   opcode op = get_irn_opcode (node);
 549   typalise_t *res = NULL;
 550
 551   switch (op) {
 552   case (iro_Cast): {
 553     /* casts always succeed */
 554     typalise_t *ta = NULL;
 555     type *tp = get_Cast_type (node);
 556
 557     if (is_Pointer_type (tp)) {
 558       tp = get_pointer_points_to_type (tp);
 559     }
 560     assert (is_Class_type (tp));
 561
 562     ta = typalise (get_Cast_op (node));
 563
 564     if (NULL == ta) {           /* no type found */
 565       ta = ta_type (tp);
 566     } else if (type_exact == ta->kind) { /* one type found */
 567       /* nothing (maybe check cast? */
 568     } else if (type_type == ta->kind) { /* some types found */
 569       if (is_subtype (tp, ta->res.type)) {
 570         ta->res.type = tp;     /* assume cast is correct */
 571       } else {
 572         /* should assert (is_subtype (ta->res.type, tp)) */
 573       }
 574     } else if (type_types == ta->kind) {
 575       lset_t *ftp = filter_for_type (ta->res.types, tp);
 576       lset_destroy (ta->res.types);
 577       ta->res.types = ftp;
 578     }
 579
 580     res = ta;
 581   } break;
 582
 583   case (iro_Proj): {
 584     res = typalise_proj (node);
 585   } break;
 586
 587   case (iro_Load): {
 588     ir_node *load_ptr = get_Load_ptr (node);
 589
 590     res = typalise (load_ptr);
 591   } break;
 592
 593   case (iro_Sel): {
 594     /* FILTER */
 595     /* it's call (sel (ptr)) or load (sel (ptr)) */
 596     entity *ent = get_Sel_entity (node);
 597     type *tp = get_entity_type (ent);
 598
 599     if (is_Method_type (tp)) {
 600       tp = get_entity_type (ent);
 601       tp = get_method_res_type (tp, 0);
 602
 603       if (is_Pointer_type (tp)) {
 604         tp = get_pointer_points_to_type (tp);
 605       }
 606
 607       res = ta_type (tp);
 608     } else if (is_Class_type (tp)) {
 609       tp = get_entity_type (ent);
 610
 611       if (is_Pointer_type (tp)) {
 612         tp = get_pointer_points_to_type (tp);
 613       }
 614
 615       res = ta_type (tp);
 616     } else if (is_Pointer_type (tp)) {
 617       tp = get_pointer_points_to_type (tp);
 618       res = ta_type (tp);
 619     } else {
 620       assert (0 && "select not handled");
 621     }
 622   } break;
 623
 624   case (iro_Phi): {
 625     int n_ins = get_irn_arity (node);
 626     int i;
 627     ir_node *phi_in = NULL;
 628     typalise_t *ta = NULL;
 629     /* assert (0 && "Do we ever get here?"); */ /* apparently, we do. */
 630
 631     for (i = 0; i < n_ins; i ++) {
 632       phi_in = get_irn_n (node, i);
 633       ta = (NULL == ta) ? typalise (phi_in) : ta_join (ta, typalise (phi_in));
 634     }
 635
 636     res = ta;
 637   } break;
 638
 639   case (iro_Alloc): {
 640     type *type = get_Alloc_type (node);
 641     res = ta_exact (type);
 642   } break;
 643
 644   case (iro_Call): {
 645     /* presumably call (sel (proj (call))) */
 646     ir_node *ptr = get_Call_ptr (node);
 647     entity *meth = NULL;
 648     if (iro_Sel == get_irn_opcode (ptr)) {
 649       meth = get_Sel_entity (ptr);
 650     } else if (iro_SymConst == get_irn_opcode (ptr)) {
 651       if (get_SymConst_kind (ptr) == symconst_addr_ent) {
 652         meth = get_SymConst_entity (ptr);
 653       } else {
 654         meth = NULL;            /* WTF? */
 655       }
 656     }
 657
 658     if (NULL != meth) {
 659       type *tp = get_method_res_type ((type*) meth, 0);
 660       res = ta_type (tp);
 661     } else {
 662       /* could be anything */
 663       /* fprintf (stdout, "meth= (null)"); */
 664       res = NULL;
 665     }
 666
 667     fprintf (stdout, "]\n");
 668
 669   } break;
 670
 671   case (iro_SymConst): {
 672     if (get_SymConst_kind (node) == symconst_type_tag) {
 673       type *tp = get_SymConst_type (node);
 674
 675       res = ta_type (tp);
 676     } else if (get_SymConst_kind (node) == symconst_addr_ent) {
 677       entity *ent = get_SymConst_entity (node);
 678       type *tp = get_entity_type (ent);
 679       tp = get_pointer_points_to_type (tp);
 680       assert (is_Class_type (tp));
 681
 682       res = ta_type (tp);       /* can't use ta_exact */
 683     } else {
 684       fprintf (stdout, "%s (%s:%i): can't handle SymConst %s?\n",
 685                __FUNCTION__, __FILE__, __LINE__,
 686                get_op_name (get_irn_op (node)));
 687       res = NULL;
 688     }
 689   } break;
 690
 691   /* template:
 692      case (iro_Cast): {}
 693      break;
 694   */
 695
 696   default: {
 697     fprintf (stdout, "what's with %s?\n", get_op_name (get_irn_op (node)));
 698     assert (0);
 699   } break;
 700   }
 701
 702   return (res);
 703 }
 704
 705
 706
 707
 708 \f
 709 /*
 710   $Log$
 711   Revision 1.8  2005/01/14 14:13:24  liekweg
 712   fix gnu extension
 713
 714   Revision 1.7  2005/01/10 17:26:34  liekweg
 715   fixup printfs, don't put environments on the stack
 716
 717   Revision 1.6  2005/01/05 14:25:54  beck
 718   renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG fronten
 719
 720   Revision 1.5  2004/12/22 14:43:14  beck
 721   made allocations C-like
 722
 723   Revision 1.4  2004/12/21 15:50:18  beck
 724   removed C99 constructs
 725
 726   Revision 1.3  2004/12/02 16:17:51  beck
 727   fixed config.h include
 728
 729   Revision 1.2  2004/10/22 09:53:10  liekweg
 730   Correctly handle proj_args
 731
 732   Revision 1.1  2004/10/21 11:09:37  liekweg
 733   Moved memwalk stuf into irmemwalk
 734   Moved lset stuff into lset
 735   Moved typalise stuff into typalise
 736
 737
 738  */