1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
2 ** All rights reserved.
4 ** Authors: Goetz Lindenmaier
12 /** This example describes a possible representation of heap allocated
13 *** variables of imperative programs.
14 *** It constructs the IR for the following program:
20 *** a = malloc(sizeof(a[10]));
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
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
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.
41 #define OPTIMIZE_NODE 0
46 /* describes the fake class "ARRAY-HEAP_EXAMPLE" with it's method main */
48 type_method *proc_main;
51 /* describes types defined by the language */
52 type_primitive *prim_t_int;
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 */
58 /* Needed while finding the element size. */
59 type_primitive *elt_type;
60 ir_mode *elt_type_mode;
64 /* holds the graph and nodes. */
66 ir_node *array, *array_ptr, *c3, *elt, *val, *x;
71 /* make basic type information for primitive type int.
72 In Sather primitive types are represented by a class.
73 This is the modeling appropriate for other languages.
74 Mode_i says that all integers shall be implemented as a
75 32 bit integer value. */
76 prim_t_int = new_type_primitive(id_from_str ("int", 3), mode_i);
78 printf("creating an IR graph: ARRAY-HEAP_EXAMPLE...\n");
80 /* first build procedure main */
81 owner = new_type_class (id_from_str ("ARRAY-HEAP_EXAMPLE", 13));
82 proc_main = new_type_method(id_from_str("main", 4), 0, 1);
83 set_method_res_type(proc_main, 0, (type *)prim_t_int);
84 proc_main_e = new_entity ((type*)owner, id_from_str ("main", 4), (type *)proc_main);
85 main_irg = new_ir_graph (proc_main_e, 4);
87 /* make type information for the array and set the bounds */
91 array_type = new_type_array(id_from_str("a", 1), N_DIMS);
92 set_array_bounds(array_type, 1, L_BOUND, U_BOUND);
93 set_array_element_type(array_type, (union type*)prim_t_int);
94 /* As the array is accessed by Sel nodes, we need information about
95 the entity the node select. Entities of an array are it's elements
96 which are, in this case, integers. */
97 array_ent = new_entity((type*)array_type, id_from_str("array_field", 11), (type*)prim_t_int);
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 */
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));
125 elt = new_Sel(get_store(), array_ptr, 1, in, array_ent);
127 val = new_Load(get_store(), elt);
128 set_store(new_Proj(val, mode_M, 0));
129 val = new_Proj(val, mode_i, 1);
131 /* return the result of procedure main */
136 x = new_Return (get_store (), 1, in);
138 mature_block (main_irg->current_block);
140 /* complete the end_block */
141 add_in_edge (main_irg->end_block, x);
142 mature_block (main_irg->end_block);
144 printf("\nDone building the graph.\n");
145 printf("Dumping the graph and a type graph.\n");
146 dump_ir_block_graph (main_irg);
147 dump_type_graph(main_irg);
149 printf("\nuse xvcg to view these graphs:\n");
150 printf("/ben/trapp/bin/i486/xvcg GRAPHNAME\n");