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