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