nsz Git - libfirm/blob - testprograms/array-heap_example.c

   1  /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
   2 ** All rights reserved.
   3 **
   4 ** Authors: Goetz Lindenmaier
   5 **
   6 ** testprogram.
   7 */
   8
   9 # include "irdump.h"
  10 # include "firm.h"
  11
  12 /**  This example describes a possible representation of heap allocated
  13 ***  variables of imperative programs.
  14 ***  It constructs the IR for the following program:
  15 ***
  16 ***
  17 ***  main(): int
  18 ***    int *a[10];
  19 ***
  20 ***    a = malloc(sizeof(a[10]));
  21 ***    return (a[3]);
  22 ***  end;
  23 ***
  24 ***  The array is placed on the heap.  The pointer to the array that
  25 ***  is a local variable is represented as a dataflow edge.
  26 ***  There are two ways to model allocation to the heap in programs with
  27 ***  explicit memory allocation:
  28 ***  1. Model the calls to malloc and free as simple procedure (of compiler
  29 ***     known procedures returning a pointer.  This is the simpler way of
  30 ***     generating FIRM, but restricts the information that can be deduced
  31 ***     for the call.
  32 ***  2. Insert an Alloc node.  A later pass can lower this to the compiler
  33 ***     known function.  This makes the allocation explicit in FIRM, supporting
  34 ***     optimization.
  35 ***     A problem is modeling free.  There is no free node in FIRM.  Is this
  36 ***     a necessary extension?
  37 ***  This example shows the second alternative, where the size of the array
  38 ***  is explicitly computed.
  39 **/
  40
  41 #define OPTIMIZE_NODE 0
  42
  43 int
  44 main(void)
  45 {
  46   /* describes the method main */
  47   type_class     *owner;
  48   type_method    *proc_main;
  49   entity         *proc_main_e;
  50
  51   /* describes types defined by the language */
  52   type_primitive *prim_t_int;
  53
  54   /* describes the array and its fields. */
  55   type_array     *array_type;   /* the type information for the array */
  56   entity         *array_ent;    /* the entity representing a field of the array */
  57
  58   /* Needed while finding the element size.  */
  59   type_primitive *elt_type;
  60   ir_mode        *elt_type_mode;
  61   int            size;
  62   ir_node        *arr_size;
  63
  64   /* holds the graph and nodes. */
  65   ir_graph       *main_irg;
  66   ir_node        *array, *array_ptr, *c3, *elt, *val, *x;
  67
  68   init_firm ();
  69
  70   /* make basic type information for primitive type int.
  71      In Sather primitive types are represented by a class.
  72      This is the modeling appropriate for other languages.
  73      Mode_i says that all integers shall be implemented as a
  74      32 bit integer value.  */
  75   prim_t_int = new_type_primitive(id_from_str ("int", 3), mode_i);
  76
  77   printf("creating an IR graph: ARRAY-HEAP_EXAMPLE...\n");
  78
  79   /* first build procedure main */
  80   owner = get_glob_type();
  81   proc_main = new_type_method(id_from_str("main", 4), 0, 1);
  82   set_method_res_type(proc_main, 0, (type *)prim_t_int);
  83   proc_main_e = new_entity ((type*)owner, id_from_str ("main", 4), (type *)proc_main);
  84   main_irg = new_ir_graph (proc_main_e, 4);
  85
  86   /* make type information for the array and set the bounds */
  87 # define N_DIMS 1
  88 # define L_BOUND 0
  89 # define U_BOUND 9
  90   array_type = new_type_array(id_from_str("a", 1), N_DIMS);
  91   set_array_bounds(array_type, 1, L_BOUND, U_BOUND);
  92   set_array_element_type(array_type, (union type*)prim_t_int);
  93   /* As the array is accessed by Sel nodes, we need information about
  94      the entity the node selects.  Entities of an array are it's elements
  95      which are, in this case, integers. */
  96   array_ent = new_entity((type*)array_type, id_from_str("array_field", 11),
  97                          (type*)prim_t_int);
  98
  99   /* Allocate the array. All program known variables that
 100      are not modeled by dataflow edges need an explicit allocate node.
 101      If the variable shall be placed on the stack, set stack_alloc.  */
 102   /*   first compute size in bytes. */
 103   elt_type = (type_primitive *)get_array_element_type(array_type);
 104   if (! (elt_type->kind == k_type_primitive)) printf(" do something else\n");
 105   elt_type_mode = get_primitive_mode(elt_type);
 106   /*   better: read bounds out of array type information */
 107   size = (U_BOUND - L_BOUND + 1) * elt_type_mode->size;
 108   /*   make constant representing the size */
 109   arr_size  = new_Const(mode_I, tarval_from_long (mode_I, size));
 110   /*   allocate and generate the Proj nodes. */
 111   array     = new_Alloc(get_store(), arr_size, (type*)array_type, stack_alloc);
 112   set_store(new_Proj(array, mode_M, 0));   /* make the changed memory visible */
 113   array_ptr = new_Proj(array, mode_p, 1);  /* remember the pointer to the array */
 114
 115   /* Now the "real" program: */
 116   /* Load element 3 of the array. For this first generate the pointer to this
 117      array element by a select node.  (Alternative: increase array pointer
 118      by (three * elt_size), but this complicates some optimizations. The
 119      type information accessible via the entity allows to generate the
 120      pointer increment later. */
 121   c3 = new_Const (mode_I, tarval_from_long (mode_I, 3));
 122   {
 123      ir_node *in[1];
 124      in[0] = c3;
 125      elt = new_Sel(get_store(), array_ptr, 1, in, array_ent);
 126   }
 127   val = new_Load(get_store(), elt);
 128   set_store(new_Proj(val, mode_M, 0));
 129   val = new_Proj(val, mode_i, 1);
 130
 131   /* return the result of procedure main */
 132   {
 133      ir_node *in[1];
 134      in[0] = val;
 135
 136      x = new_Return (get_store (), 1, in);
 137   }
 138   mature_block (main_irg->current_block);
 139
 140   /* complete the end_block */
 141   add_in_edge (main_irg->end_block, x);
 142   mature_block (main_irg->end_block);
 143
 144   /* verify the graph */
 145   irg_vrfy(main_irg);
 146
 147   dead_node_elimination(main_irg);
 148
 149   printf("\nDone building the graph.\n");
 150   printf("Dumping the graph and a type graph.\n");
 151   dump_ir_block_graph (main_irg);
 152   dump_type_graph(main_irg);
 153
 154   printf("\nuse xvcg to view these graphs:\n");
 155   printf("/ben/goetz/bin/xvcg GRAPHNAME\n");
 156
 157   return (1);
 158 }