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

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