From 46fbaaf30aa63825bf9627cb13207308c3276d93 Mon Sep 17 00:00:00 2001
From: =?utf8?q?G=C3=B6tz=20Lindenmaier?= <goetz@ipd.info.uni-karlsruhe.de>
Date: Thu, 18 Jul 2002 08:29:47 +0000
Subject: [PATCH] implemented typecheck, called in inline_method.

[r445]
---
 ir/common/bool.h |   5 +
 ir/ir/irgopt.c   |   2 +
 ir/ir/irmode.c   |  11 ++
 ir/ir/irmode.h   |   5 +
 ir/tr/entity.c   |   4 +
 ir/tr/entity.h   |   5 +
 ir/tr/type.c     | 259 +++++++++++++++++++++++++++++++++++++++++++++++
 ir/tr/type.h     |  84 ++++++++++++++-
 8 files changed, 374 insertions(+), 1 deletion(-)

diff --git a/ir/common/bool.h b/ir/common/bool.h
index 6939b66b8..1476c2c4d 100644
--- a/ir/common/bool.h
+++ b/ir/common/bool.h
@@ -23,4 +23,9 @@ typedef unsigned char bool;
 #  define FALSE 0
 # endif /* ndef TRUE */
 
+# ifndef true
+#  define true  1
+#  define false 0
+# endif /* ndef TRUE */
+
 # endif /* _BOOL_H_ */
diff --git a/ir/ir/irgopt.c b/ir/ir/irgopt.c
index d76ad2646..287c4cc5b 100644
--- a/ir/ir/irgopt.c
+++ b/ir/ir/irgopt.c
@@ -432,6 +432,8 @@ void inline_method(ir_node *call, ir_graph *called_graph) {
   /** Check preconditions **/
   assert(get_irn_op(call) == op_Call);
   /* assert(get_Call_type(call) == get_entity_type(get_irg_ent(called_graph))); */
+  assert(smaller_type(get_entity_type(get_irg_ent(called_graph)),
+		      get_Call_type(call)));
   assert(get_type_tpop(get_Call_type(call)) == type_method);
   if (called_graph == current_ir_graph) return;
 
diff --git a/ir/ir/irmode.c b/ir/ir/irmode.c
index 2efc4220d..995f6eeb3 100644
--- a/ir/ir/irmode.c
+++ b/ir/ir/irmode.c
@@ -508,3 +508,14 @@ mode_is_dataM (ir_mode *mode)
   }
   return res;
 }
+
+/* Returns true if sm can be converted to lm without loss. */
+bool
+smaller_mode(ir_mode *sm, ir_mode *lm) {
+  if ((mode_is_int(sm) && mode_is_int(lm)) &&
+      get_mode_modecode(sm) <= get_mode_modecode(lm))
+    return true;
+  if ((mode_is_float(sm) && mode_is_float(lm)) &&
+      get_mode_modecode(sm) <= get_mode_modecode(lm))
+    return true;
+}
diff --git a/ir/ir/irmode.h b/ir/ir/irmode.h
index bca6b7461..76bf8fa75 100644
--- a/ir/ir/irmode.h
+++ b/ir/ir/irmode.h
@@ -20,6 +20,7 @@ reimplementation of the tarval module.
 # define _IRMODE_H_
 
 #include "ident.h"
+#include "bool.h"
 
 # define target_bits 8
 
@@ -128,4 +129,8 @@ int mode_is_data (ir_mode *mode);
 int mode_is_datab (ir_mode *mode);
 int mode_is_dataM (ir_mode *mode);
 
+/* Returns true if sm can be converted to lm without loss
+   according to firm definiton */
+bool smaller_mode(ir_mode *sm, ir_mode *lm);
+
 # endif /* _IRMODE_H_ */
diff --git a/ir/tr/entity.c b/ir/tr/entity.c
index 8b79c9f66..337db517c 100644
--- a/ir/tr/entity.c
+++ b/ir/tr/entity.c
@@ -506,3 +506,7 @@ int is_compound_entity(entity *ent) {
   return (is_class_type(t) || is_struct_type(t) ||
 	  is_array_type(t) || is_union_type(t));
 }
+
+bool equal_entity(entity *ent1, entity *ent2) {
+  return true;
+}
diff --git a/ir/tr/entity.h b/ir/tr/entity.h
index df943769f..5581b75f4 100644
--- a/ir/tr/entity.h
+++ b/ir/tr/entity.h
@@ -277,6 +277,11 @@ int is_atomic_entity(entity *ent);
    array or union type. */
 int is_compound_entity(entity *ent);
 
+/* Returns true if ent1 and ent2 have are equal except for their owner.
+   Two entities are equal if
+    - they have the same type (the same C-struct)
+*/
+bool equal_entity(entity *ent1, entity *ent2);
 
 /*****/
 
diff --git a/ir/tr/type.c b/ir/tr/type.c
index 8afb85926..47abbb269 100644
--- a/ir/tr/type.c
+++ b/ir/tr/type.c
@@ -255,6 +255,251 @@ int is_type            (void *thing) {
     return 0;
 }
 
+
+bool equal_type(type *typ1, type *typ2) {
+  entity **m;
+  type **t;
+  int i, j;
+
+  if (typ1 == typ2) return true;
+
+  if ((get_type_tpop_code(typ1) != get_type_tpop_code(typ2)) ||
+      (get_type_name(typ1) != get_type_name(typ2)) ||
+      (get_type_mode(typ1) != get_type_mode(typ2)) ||
+      (get_type_state(typ1) != get_type_state(typ2)))
+    return false;
+  if ((get_type_state(typ1) == layout_fixed) &&
+      (get_type_size(typ1) != get_type_size(typ2)))
+    return false;
+
+  switch(get_type_tpop_code(typ1)) {
+  case tpo_class:       {
+    if (get_class_n_members(typ1) != get_class_n_members(typ2)) return false;
+    if (get_class_n_subtypes(typ1) != get_class_n_subtypes(typ2)) return false;
+    if (get_class_n_supertypes(typ1) != get_class_n_supertypes(typ2)) return false;
+    if (get_class_peculiarity(typ1) != get_class_peculiarity(typ2)) return false;
+    /** Compare the members **/
+    m = alloca(sizeof(entity *) * get_class_n_members(typ1));
+    memset(m, 0, sizeof(entity *) * get_class_n_members(typ1));
+    /* First sort the members of typ2 */
+    for (i = 0; i < get_class_n_members(typ1); i++) {
+      entity *e1 = get_class_member(typ1, i);
+      for (j = 0; j < get_class_n_members(typ2); j++) {
+	entity *e2 = get_class_member(typ2, j);
+	if (get_entity_name(e1) == get_entity_name(e2))
+	  m[i] = e2;
+      }
+    }
+    for (i = 0; i < get_class_n_members(typ1); i++) {
+      if (!m[i]  ||  /* Found no counterpart */
+	  !equal_entity(get_class_member(typ1, i), m[i]))
+	return false;
+    }
+    /** Compare the supertypes **/
+    t = alloca(sizeof(entity *) * get_class_n_supertypes(typ1));
+    memset(t, 0, sizeof(entity *) * get_class_n_supertypes(typ1));
+    /* First sort the supertypes of typ2 */
+    for (i = 0; i < get_class_n_supertypes(typ1); i++) {
+      type *t1 = get_class_supertype(typ1, i);
+      for (j = 0; j < get_class_n_supertypes(typ2); j++) {
+	type *t2 = get_class_supertype(typ2, j);
+	if (get_type_name(t2) == get_type_name(t1))
+	  t[i] = t2;
+      }
+    }
+    for (i = 0; i < get_class_n_supertypes(typ1); i++) {
+      if (!t[i]  ||  /* Found no counterpart */
+	  get_class_supertype(typ1, i) != t[i])
+	return false;
+    }
+  } break;
+  case tpo_struct:      {
+    if (get_struct_n_members(typ1) != get_struct_n_members(typ2)) return false;
+    m = alloca(sizeof(entity *) * get_struct_n_members(typ1));
+    memset(m, 0, sizeof(entity *) * get_struct_n_members(typ1));
+    /* First sort the members of lt */
+    for (i = 0; i < get_struct_n_members(typ1); i++) {
+      entity *e1 = get_struct_member(typ1, i);
+      for (j = 0; j < get_struct_n_members(typ2); j++) {
+	entity *e2 = get_struct_member(typ2, j);
+	if (get_entity_name(e1) == get_entity_name(e2))
+	  m[i] = e2;
+      }
+    }
+    for (i = 0; i < get_struct_n_members(typ1); i++) {
+      if (!m[i]  ||  /* Found no counterpart */
+	  !equal_entity(get_struct_member(typ1, i), m[i]))
+	return false;
+    }
+  } break;
+  case tpo_method:      {
+    if (get_method_n_params(typ1) != get_method_n_params(typ2)) return false;
+    if (get_method_n_ress(typ1) != get_method_n_ress(typ2)) return false;
+    for (i = 0; i < get_method_n_params(typ1); i++) {
+      if (!equal_type(get_method_param_type(typ1, i), get_method_param_type(typ2, i)))
+	return false;
+    }
+    for (i = 0; i < get_method_n_ress(typ1); i++) {
+      if (!equal_type(get_method_res_type(typ1, i), get_method_res_type(typ2, i)))
+	return false;
+    }
+  } break;
+  case tpo_union:       {
+    if (get_union_n_members(typ1) != get_union_n_members(typ2)) return false;
+    m = alloca(sizeof(entity *) * get_union_n_members(typ1));
+    memset(m, 0, sizeof(entity *) * get_union_n_members(typ1));
+    /* First sort the members of lt */
+    for (i = 0; i < get_union_n_members(typ1); i++) {
+      entity *e1 = get_union_member(typ1, i);
+      for (j = 0; j < get_union_n_members(typ2); j++) {
+	entity *e2 = get_union_member(typ2, j);
+	if (get_entity_name(e1) == get_entity_name(e2))
+	  m[i] = e2;
+      }
+    }
+    for (i = 0; i < get_union_n_members(typ1); i++) {
+      if (!m[i]  ||  /* Found no counterpart */
+	  !equal_entity(get_union_member(typ1, i), m[i]))
+	return false;
+    }
+  } break;
+  case tpo_array:       {
+    type *set, *let;  /* small/large elt. type */
+    if (get_array_n_dimensions(typ1) != get_array_n_dimensions(typ2))
+      return false;
+    if (!equal_type(get_array_element_type(typ1), get_array_element_type(typ2)))
+      return false;
+    for(i = 0; i < get_array_n_dimensions(typ1); i++) {
+      if (get_array_lower_bound(typ1, i) != get_array_lower_bound(typ2, i) ||
+	  get_array_upper_bound(typ1, i) != get_array_upper_bound(typ2, i))
+	return false;
+      if (get_array_order(typ1, i) != get_array_order(typ2, i))
+	assert(0 && "type compare with different dimension orders not implemented");
+    }
+  } break;
+  case tpo_enumeration: {
+    assert(0 && "enumerations not implemented");
+  } break;
+  case tpo_pointer:     {
+    if (get_pointer_points_to_type(typ1) != get_pointer_points_to_type(typ2))
+      return false;
+  } break;
+  case tpo_primitive:   {
+  } break;
+  default: break;
+  }
+  return true;
+}
+
+bool smaller_type (type *st, type *lt) {
+  entity **m;
+  int i, j;
+
+  if (st == lt) return true;
+
+  if (get_type_tpop_code(st) != get_type_tpop_code(lt))
+    return false;
+
+  switch(get_type_tpop_code(st)) {
+  case tpo_class:       {
+    return is_subclass_of(st, lt);
+  } break;
+  case tpo_struct:      {
+    if (get_struct_n_members(st) != get_struct_n_members(lt)) return false;
+    m = alloca(sizeof(entity *) * get_struct_n_members(st));
+    memset(m, 0, sizeof(entity *) * get_struct_n_members(st));
+    /* First sort the members of lt */
+    for (i = 0; i < get_struct_n_members(st); i++) {
+      entity *se = get_struct_member(st, i);
+      for (j = 0; j < get_struct_n_members(lt); j++) {
+	entity *le = get_struct_member(lt, j);
+	if (get_entity_name(le) == get_entity_name(se))
+	  m[i] = le;
+      }
+    }
+    for (i = 0; i < get_struct_n_members(st); i++) {
+      if (!m[i]  ||  /* Found no counterpart */
+	  !smaller_type(get_entity_type(get_struct_member(st, i)),
+			get_entity_type(m[i])))
+	return false;
+    }
+  } break;
+  case tpo_method:      {
+    if (get_method_n_params(st) != get_method_n_params(lt)) return false;
+    if (get_method_n_ress(st) != get_method_n_ress(lt)) return false;
+    for (i = 0; i < get_method_n_params(st); i++) {
+      if (!smaller_type(get_method_param_type(st, i), get_method_param_type(lt, i)))
+	return false;
+    }
+    for (i = 0; i < get_method_n_ress(st); i++) {
+      if (!smaller_type(get_method_res_type(st, i), get_method_res_type(lt, i)))
+	return false;
+    }
+  } break;
+  case tpo_union:       {
+    if (get_union_n_members(st) != get_union_n_members(lt)) return false;
+    m = alloca(sizeof(entity *) * get_union_n_members(st));
+    memset(m, 0, sizeof(entity *) * get_union_n_members(st));
+    /* First sort the members of lt */
+    for (i = 0; i < get_union_n_members(st); i++) {
+      entity *se = get_union_member(st, i);
+      for (j = 0; j < get_union_n_members(lt); j++) {
+	entity *le = get_union_member(lt, j);
+	if (get_entity_name(le) == get_entity_name(se))
+	  m[i] = le;
+      }
+    }
+    for (i = 0; i < get_union_n_members(st); i++) {
+      if (!m[i]  ||  /* Found no counterpart */
+	  !smaller_type(get_entity_type(get_union_member(st, i)),
+			get_entity_type(m[i])))
+	return false;
+    }
+  } break;
+  case tpo_array:       {
+    type *set, *let;  /* small/large elt. type */
+    if (get_array_n_dimensions(st) != get_array_n_dimensions(lt))
+      return false;
+    set = get_array_element_type(st);
+    let = get_array_element_type(lt);
+    if (set != let) {
+      /* If the elt types are different, set must be convertible
+	 to let, and they must have the same size so that address
+	 computations work out.  To have a size the layout must
+	 be fixed. */
+      if ((get_type_state(set) != layout_fixed) ||
+	  (get_type_state(let) != layout_fixed))
+	return false;
+      if (!smaller_type(set, let) ||
+	  get_type_size(set) != get_type_size(let))
+	return false;
+    }
+    for(i = 0; i < get_array_n_dimensions(st); i++) {
+      if (get_array_lower_bound(lt, i))
+	if(get_array_lower_bound(st, i) != get_array_lower_bound(lt, i))
+	  return false;
+      if (get_array_upper_bound(lt, i))
+	if(get_array_upper_bound(st, i) != get_array_upper_bound(lt, i))
+	  return false;
+    }
+  } break;
+  case tpo_enumeration: {
+    assert(0 && "enumerations not implemented");
+  } break;
+  case tpo_pointer:     {
+    if (!smaller_type(get_pointer_points_to_type(st),
+		      get_pointer_points_to_type(lt)))
+      return false;
+  } break;
+  case tpo_primitive:   {
+    if (!smaller_mode(get_type_mode(st), get_type_mode(lt)))
+      return false;
+  } break;
+  default: break;
+  }
+  return true;
+}
+
 /*******************************************************************/
 /** TYPE_CLASS                                                    **/
 /*******************************************************************/
@@ -420,6 +665,20 @@ bool    is_class_type(type *clss) {
   if (clss->type_op == type_class) return 1; else return 0;
 }
 
+bool is_subclass_of(type *low, type *high) {
+  int i;
+  assert(is_class_type(low) && is_class_type(high));
+  if (low == high) return true;
+  /* depth first search from high downwards. */
+  for (i = 0; i < get_class_n_subtypes(high); i++) {
+    if (low == get_class_subtype(high, i))
+      return true;
+    if (is_subclass_of(low, get_class_subtype(high, i)))
+      return true;
+  }
+  return false;
+}
+
 /*******************************************************************/
 /** TYPE_STRUCT                                                   **/
 /*******************************************************************/
diff --git a/ir/tr/type.h b/ir/tr/type.h
index 7ff863a67..252bb806f 100644
--- a/ir/tr/type.h
+++ b/ir/tr/type.h
@@ -189,6 +189,86 @@ extern unsigned long type_visited;
  */
 int is_type            (void *thing);
 
+/****f* type/equal_types
+ *
+ * NAME
+ *   equal_type - Checks whether two types are structural equal.
+ * SYNOPSIS
+ *   bool equal_types   (type *typ1, type *typ2);
+ * INPUTS
+ *   two pointer types
+ * RESULT
+ *   true if the types are equal, else false.
+ *   Types are equal if
+ *    - they are the same type kind
+ *    - they have the same name
+ *    - they have the same mode (if applicable)
+ *    - they have the same type_state and, ev., the same size
+ *    - they are class types and have
+ *      - the same members (see same_entity in entity.h)
+ *      - the same supertypes -- the C-pointers are compared --> no recursive call.
+ *      - the same number of subtypes.  Subtypes are not compared,
+ *        as this could cause a cyclic test.
+ *      - the same peculiarity
+ *    - they are structure types and have the same members
+ *    - they are method types and have
+ *      - the same parameter types
+ *      - the same result types
+ *    - they are union types and have the same members
+ *    - they are array types and have
+ *      - the same number of dimensions
+ *      - the same dimension bounds
+ *      - the same dimension order
+ *      - the same element type
+ *    - they are enumeration types and have the same enumerator names
+ *    - they are pointer types and have the identical points_to type
+ *      (i.e., the same C-struct to represent the type, type_id is skipped.
+ *       This is to avoid endless recursions; with pointer types circlic
+ *       type graphs are possible.)
+ *
+ ***
+ */
+bool equal_type(type *tpy1, type *typ2);
+
+/****f* type/smaller_type
+ *
+ * NAME
+ *   smaller_type - Checks whether two types are structural comparable.
+ * SYNOPSIS
+ *   bool smaller_type   (type *st, type *lt);
+ * INPUTS
+ *   two pointer type
+ * RESULT
+ *   true if type st is smaller than type lt, i.e. whenever
+ *   lt is expected a st can be used.
+ *   This is true if
+ *    - they are the same type kind
+ *    - mode(st) < mode (lt)  (if applicable)
+ *    - they are class types and st is (transitive) subtype of lt,
+ *    - they are structure types and
+ *       - the members of st have exactly one counterpart in lt with the same name,
+ *       - the counterpart has a bigger type.
+ *    - they are method types and have
+ *      - the same number of parameter and result types,
+ *      - the parameter types of st are smaller than those of lt,
+ *      - the result types of st are smaller than those of lt
+ *    - they are union types and have the members of st have exactly one
+ *      counterpart in lt and the type is smaller
+ *    - they are array types and have
+ *      - the same number of dimensions
+ *      - all bounds of lt are bound of st
+ *      - the same dimension order
+ *      - the same element type
+ *      or
+ *      - the element type of st is smaller than that of lt
+ *      - the element types have the same size and fixed layout.
+ *    - they are enumeration types and have the same enumerator names
+ *    - they are pointer types and have the points_to type of st is
+ *      smaller than the points_to type of lt.
+ ***
+ */
+bool smaller_type (type *st, type *lt);
+
 /****** type/class
  * NAME
  *  Representation of a class type.
@@ -301,7 +381,9 @@ void set_class_dfn (type*, int);
 int  get_class_dfn (type*);
 
 /* typecheck */
-bool    is_class_type(type *clss);
+bool is_class_type(type *clss);
+/* Returns true if low is subclass of high. */
+bool is_subclass_of(type *low, type *high);
 /*****/
 
 /****** type/struct
-- 
2.20.1