| blob | 06772f3ab4699eaf32c1b4caa2a58d9458192c57 |
1 This is Info file suif1.info, produced by Makeinfo version 1.68 from
2 the input file suif1.texi.
4 This file documents the SUIF library.
6 Copyright (C) 1994 Stanford University. All rights reserved.
8 Permission is given to use, copy, and modify this documentation for
9 any non-commercial purpose as long as this copyright notice is not
10 removed. All other uses, including redistribution in whole or in part,
11 are forbidden without prior written permission.
13 \x1f
14 File: suif1.info, Node: Unregistered Annotes, Next: Predefined Annotes, Prev: Structured Annotes, Up: Annotations
16 Unregistered Annotations
17 ========================
19 If an annotation name is not registered with the manager, the format
20 of the annotation data is unknown. Such annotations cannot be written
21 to the SUIF output file, and when they are printed the data is just
22 shown as a hexadecimal value. If the data needs to be deallocated, you
23 must do so explicitly before the annotations are deleted. The library
24 cannot automatically update the data in unregistered annotations, and
25 the cloning functions do not copy them. The `immeds' method returns
26 `NULL' for unregistered annotations and `set_immeds' will not work at
27 all for them.
29 Due to these limitations, annotations should generally be registered
30 with the manager. There are, however, many situations where
31 unregistered annotations are useful. Because they are not written out,
32 the data in these annotations does not have to be converted to `immed'
33 lists. This means that they may contain totally arbitrary data
34 structures. The drawback is that it is entirely up to you to ensure
35 that the annotation data is maintained properly.
37 \x1f
38 File: suif1.info, Node: Predefined Annotes, Next: Annotation Manager, Prev: Unregistered Annotes, Up: Annotations
40 Predefined Annotations
41 ======================
43 The SUIF library automatically defines a number of annotations for
44 its own use. Most of these are only used internally to handle reading
45 and writing SUIF files. A few of them are visible to users. Unless
46 specified otherwise, they are all flat annotations.
48 * Menu:
50 * Initial Data Annotes:: Annotations for initializing variables.
51 * Call-By-Ref Annotes:: Handling call-by-reference parameters.
52 * Common Block Annotes:: Identifying Fortran `common' blocks.
53 * Miscellaneous Annotes:: Other predefined annotations.
55 \x1f
56 File: suif1.info, Node: Initial Data Annotes, Next: Call-By-Ref Annotes, Prev: Miscellaneous Annotes, Up: Predefined Annotes
58 Initial Data Annotations
59 ------------------------
61 Variables that are not in the automatic storage class can be
62 initialized by attaching annotations to their definitions (*note
63 Variable Definitions::.). These annotations are very low-level. Each
64 one specifies the initial value for a certain number of bits. Multiple
65 annotations may be used, in which case their order is significant.
67 `k_fill'
68 This annotation indicates that the variable should be initialized
69 with `N' bits filled with bit pattern `V', where `N' is the first
70 entry on the list and `V' is the second. The size must be a
71 multiple of the byte size and the bit pattern must be one byte
72 long. Currently, zero is the only bit pattern that is supported.
74 `k_repeat_init'
75 This is a generalized version of the `fill' annotation. The
76 variable is initialized to `R' copies of `N' bits holding the
77 value `V', where `R', `N', and `V' are the first, second, and
78 third entries on the `immed' list. The values that are currently
79 supported are integers, floating point values, and symbolic
80 addresses.
82 `k_multi_init'
83 This is another initial value annotation that is used to initialize
84 character strings. The first entry on the list is the size in
85 bits of each character. The rest of the entries on the `immed'
86 list are integers that specify the characters in the string.
88 Despite the low-level nature of the initial data annotations, SUIF
89 still requires that they correspond to the types of the variables. For
90 example, character strings should only be used to initialize character
91 arrays. Each value specified in one of these annotations must fit
92 exactly into the corresponding variable, field, or array element. The
93 only exception to this is that multiple fields or array elements may be
94 initialized to zero with a single `fill' annotation.
96 For example, this structure
98 struct {
99 int x[2];
100 float fp;
101 char string[7];
102 } sample;
104 might be initialized with the following annotations:
106 ["fill": 64 0]
107 ["repeat_init": 1 32 1.2000e+00]
108 ["multi_init": 8 102 97 116 112 105 103 0]
110 \x1f
111 File: suif1.info, Node: Call-By-Ref Annotes, Next: Common Block Annotes, Prev: Initial Data Annotes, Up: Predefined Annotes
113 Call-By-Reference Annotations
114 -----------------------------
116 Fortran and other languages pass procedure parameters by reference
117 but SUIF uses call-by-value. To implement call-by-reference parameters,
118 SUIF passes pointers to the actual parameters and then dereferences
119 those pointers when the formal parameters are used. While this is
120 perfectly adequate for many compiler passes, the pointer dereferences
121 are difficult to handle in some high-level Fortran passes. The SUIF
122 Fortran mode automatically converts the code to make it appear that the
123 parameters are passed by reference. The library uses two predefined
124 annotations to implement this.
126 `k_call_by_ref'
127 The Fortran front-end puts this annotation on pointer types that
128 are used to implement call-by-reference parameter passing. The
129 library uses this to detect parameters that should be modified
130 when converting to Fortran mode. This annotation has no data on
131 its `immed' list.
133 `k_orig_type'
134 While in Fortran mode, the types of the call-by-reference
135 parameters are temporarily replaced. The `orig_type' annotations
136 are attached to the parameter variables to record their original
137 types. The `immed' list contains a single entry, the original
138 pointer type of the parameter. These annotations are never
139 written to the output files.
141 \x1f
142 File: suif1.info, Node: Common Block Annotes, Prev: Call-By-Ref Annotes, Up: Predefined Annotes
144 Common Block Annotations
145 ------------------------
147 Fortran `common' blocks are represented in SUIF by global group
148 types. These can be accessed just like any other structures. In
149 addition, and the Fortran front-end will create sub-variables to
150 represent the fields in the `common' block, so most of the time only
151 the sub-variables themselves will be seen. If you want to know whether
152 a particular global group represents a `common' block, you can check
153 for the `k_common_block' annotation, which is put only on variables
154 representing `common' blocks (the blocks, not the fields).
156 \x1f
157 File: suif1.info, Node: Miscellaneous Annotes, Next: Initial Data Annotes, Up: Predefined Annotes
159 Miscellaneous Annotations
160 -------------------------
162 The SUIF library defines a few other annotations to record various
163 attributes of SUIF programs. These are straightforward except for the
164 `fields' annotation which is described here in more detail.
166 `k_line'
167 This annotation records line numbers from the source code to be
168 used when debugging the object code. It is usually attached to a
169 `mrk' instruction. The first list entry is the integer line
170 number and the second is the character string for the file name.
172 `k_history'
173 As each SUIF pass runs, the library automatically records the
174 command-line for the pass as an annotation on the file set entries.
175 These `history' annotations allow you to see how a particular SUIF
176 file was generated.
178 `k_enable_exceptions'
179 This annotation is attached to a `proc_symtab' to indicate which
180 run-time exceptions should be detected within that procedure. The
181 entries on the `immed' list are character strings. The system
182 currently recognizes `"int_divide-by-0"' and `"int_overflow"'.
183 IEEE floating point exceptions need to be added.
185 `k_reg_num'
186 This annotation is attached to variables that represent machine
187 registers to record the register numbers. It has one immediate
188 value which is the integer register number. The meaning of the
189 register numbers are machine-dependent.
191 `k_fields'
192 A field within a structure or union variable is specified in SUIF
193 by a constant offset and a base address. That is all that is
194 needed to generate code. However, if the offset is zero or if the
195 variable is a union, that information is not sufficient to
196 determine the field. The `fields' annotation may be used to
197 provide the field names that were used in the original source
198 code. The `immed' list for one of these annotations contains the
199 names of the fields being accessed. (There may be multiple field
200 names because of nested structures or unions.)
202 The `fields' annotation is somewhat more complicated than the
203 others. The difficulty is in defining where this annotation should be
204 used. Intuitively, the `fields' annotation should be placed on the
205 first instruction that produces a pointer to the field. There are
206 basically three different situations to consider.
208 In the simplest case, a field can be addressed directly with an
209 `ldc' instruction (*note Load Constant Instructions::.). Since that
210 produces a pointer to the field, a `fields' annotation may be placed on
211 the `ldc' instruction. Of course, the entries on the annotation must
212 be valid field names for the variable that is addressed.
214 To access a field of a structure or union variable that is
215 referenced by a pointer, the constant offset must be included with an
216 explicit `add' instruction. Since the result of the addition is a
217 pointer to the field, the `fields' annotation should be placed on the
218 `add' instruction. Note that if the field offset is zero, the `add'
219 instruction may be replaced by a `cvt' instruction. The same rule
220 applies: the `cvt' instruction gets the `fields' annotation because it
221 produces a pointer to the field.
223 For arrays of structures or unions, an `array' instruction (*note
224 Array Instructions::.) may include a constant offset for a field within
225 the array element being addressed, so this is another type of
226 instruction that may include a `fields' annotation. The entries on the
227 `fields' annotation must be valid fields within the array element type.
229 \x1f
230 File: suif1.info, Node: Annotation Manager, Next: SUIF Objects, Prev: Predefined Annotes, Up: Annotations
232 Annotation Manager
233 ==================
235 The annotation manager keeps track of the annotations that have been
236 registered. For each annotation name, it records whether the annotation
237 is flat or structured and whether it should be written to the output
238 file. Additional information is stored for structured annotations.
240 The annotation manager is implemented in the files `aman.h' and
241 `aman.cc'. The `annote_def' class is used to hold the annotation
242 information. Each `annote_def' object records the information for
243 annotations with a particular name (which can be accessed with the
244 `name' method). As with the annotations themselves, the name in the
245 `annote_def' is entered in the `lexicon' (*note Lexicon::.), except
246 that in this case the `annote_def' constructor automatically makes sure
247 that the name is in the `lexicon'.
249 The manager is implemented as a list of `annote_def' objects. This
250 list is initialized by the `init_aman' function, which is automatically
251 called when the library is initialized. The `register_annote' function
252 adds an `annote_def' to the list. An error occurs if the name in the
253 `annote_def' is already used in another registered `annote_def'.
254 Rather than calling the `register_annote' function directly, use the
255 `ANNOTE' and `STRUCT_ANNOTE' macros described below to enter new
256 annotations.
258 The information in the manager can be retrieved using the
259 `lookup_annote' function. Given an annotation name that is entered in
260 the `lexicon', `lookup_annote' searches the list of registered
261 annotations and returns the `annote_def' corresponding to that name.
262 If the name is not found, it returns `NULL'.
264 * Menu:
266 * Flat Annote Defs:: Definitions of flat annotations.
267 * Struct Annote Defs:: Definitions of structured annotations.
268 * Input Annotes:: Handling unknown annotations in the input.
270 \x1f
271 File: suif1.info, Node: Flat Annote Defs, Next: Struct Annote Defs, Up: Annotation Manager
273 Flat Annotation Definitions
274 ---------------------------
276 Flat annotation definitions (*note Flat Annotes::.) are represented
277 by base `annote_def' objects, for which the `is_structured' method
278 returns `FALSE'. Other than the annotation name, these entries contain
279 a flag that indicates whether the annotations should be written to the
280 SUIF output file. The `output' method is used to retrieve this flag
281 and the `set_output' method to change its value.
283 The `ANNOTE' macro provides a convenient way to register flat
284 annotations. This macro enters the annotation name in the `lexicon',
285 creates an `annote_def' object, and registers it with the manager. It
286 takes three arguments: the variable that will hold the pointer to the
287 annotation name in the `lexicon', the annotation name, and the value of
288 its `output' flag. For example:
290 char *k_my_annote;
291 ANNOTE(k_my_annote, "my_annote", TRUE);
293 This enters the name `"my_annote"' in the `lexicon' and sets
294 `k_my_annote' to point to that string. It also registers that name as
295 a flat annotation that will be written to the SUIF output file.
296 Typically, `k_my_annote' will be a global variable that is used
297 throughout the program to refer to annotations of this type.
299 \x1f
300 File: suif1.info, Node: Struct Annote Defs, Next: Input Annotes, Prev: Flat Annote Defs, Up: Annotation Manager
302 Structured Annotation Definitions
303 ---------------------------------
305 The `struct_annote_def' class, which is derived from the
306 `annote_def' class, is used to record the definitions of structured
307 annotations. Objects of this class behave just like base `annote_def'
308 objects, except the `is_structured' method returns `TRUE'. In
309 addition, these objects contain pointers to four functions:
311 `from'
312 The `from' function converts the annotation data from a list of
313 `immed' values to the user's data structure. This function is
314 required.
316 `to'
317 The `to' function converts the user's data structure to a list of
318 `immed' values. This function is required.
320 `free'
321 The `free' function is optional, but it should be provided if the
322 annotation data needs to be deallocated when the annotation is
323 deleted.
325 `print'
326 The `print' function is also optional, but without it the data in a
327 structured annotation is simply printed as a hexadecimal value.
328 This function allows you to print the annotations in more
329 meaningful formats. As much as possible, the annotations should
330 be printed in the same style as flat annotations.
332 Structured annotations must be registered with the manager before the
333 SUIF input file is read. Otherwise, the annotations will remain as
334 `immed' value lists, instead of being converted to the appropriate data
335 structures. The `STRUCT_ANNOTE' macro should be used to register
336 structured annotations. This is just like the `ANNOTE' macro except
337 that it takes four more arguments for the `struct_annote_def'
338 functions. For example:
340 char *k_struct_annote;
341 void *ann_from(char *name, immed_list *il, suif_object *obj);
342 immed_list *ann_to(char *name, void *data);
343 void ann_free(void *data);
345 STRUCT_ANNOTE(k_struct_annote, "struct_annote", TRUE,
346 ann_from, ann_to, ann_free, NULL);
348 This registers the annotation `"struct_annote"' as a structured
349 annotation. The `ann_from' function will be used to convert the
350 annotation data from a list of `immed' values; the `ann_to' function
351 will be used to convert the data back to an `immed_list'; and the
352 `ann_free' function will be used to deallocate the annotation data. No
353 function is provided to print the annotation data.
355 \x1f
356 File: suif1.info, Node: Input Annotes, Prev: Struct Annote Defs, Up: Annotation Manager
358 Unregistered Annotations in the Input File
359 ------------------------------------------
361 When an unregistered annotation is read from a SUIF input file, it is
362 automatically registered as a flat annotation. This is done so that the
363 manager knows to write the annotation back in the output.
365 Annotations are often added to a SUIF file in one pass to record some
366 sort of information, perhaps the results of a data flow analysis. Those
367 annotations may then used in later passes to guide various
368 transformations. Even if intervening passes do not recognize the
369 annotations, they will still be propagated to the output. (It is up to
370 the user, of course, to make sure that the intervening passes do not
371 invalidate the information in the annotations without updating them.)
373 \x1f
374 File: suif1.info, Node: SUIF Objects, Next: Annote Lists, Prev: Annotation Manager, Up: Annotations
376 SUIF Objects
377 ============
379 Most of the significant classes in the SUIF library are derived from
380 a common base class. This `suif_object' class includes a field with a
381 pointer to a list of annotations. Thus, annotations can be attached to
382 most objects in SUIF, and all of these objects share the same interface
383 for accessing the annotations. The files `suifobj.h' and `suifobj.cc'
384 contain the code for the `suif_object' class.
386 Besides the annotation list, each `suif_object' has a field to
387 identify the kind of the object. The `object_kind' method retrieves
388 the value from this field. The `object_kinds' enumerated type defines
389 the possible values:
391 `FILE_OBJ'
392 File set entry. *Note File Set Entries::.
394 `TREE_OBJ'
395 Abstract syntax tree node. *Note Tree Nodes::.
397 `INSTR_OBJ'
398 SUIF instruction. *Note Instructions::.
400 `SYMTAB_OBJ'
401 Symbol table. *Note Symbol Tables::.
403 `SYM_OBJ'
404 Symbol node. *Note Symbols::.
406 `DEF_OBJ'
407 Variable definition. *Note Variable Definitions::.
409 `TYPE_OBJ'
410 Type node. *Note Types::.
412 The rest of the methods in the `suif_object' class are related to
413 handling annotations. First of all, the `are_annotations' method
414 checks to see if an object has any annotations attached to it. If so,
415 the `annotes' method can be used to retrieve a pointer to the list of
416 annotations. Do not just grab the list of annotations and check to see
417 if it is empty, but use `are_annotations' instead. Since many objects
418 don't have any annotations, the library doesn't allocate annotation
419 lists unless they are needed. Calling `annotes' will create a new list
420 if one did not already exist, so to avoid creating a lot of empty lists
421 use `are_annotations' first.
423 The `prepend_annote' and `append_annote' methods are a convenient
424 way to add new annotations to an object. They simply create a new
425 annotation using the specified name and data and then add it to the
426 beginning or end, respectively, of the annotation list. If the object
427 is only supposed to have one annotation with a particular name, the
428 `set_annote' method works well for assigning new values for that
429 annotation. If the object already has an annotation with the specified
430 name, `set_annote' will replace the existing one (or the first one that
431 it finds); otherwise, it just adds the new annotation at the end of the
432 list.
434 There are two different methods to retrieve data from annotations
435 attached to an object. The first, `peek_annote', simply returns the
436 data field from the first annotation that it finds with the specified
437 name. If it doesn't find any annotations with that name, it returns a
438 `NULL' pointer. The `get_annote' method does the same thing except
439 that it is destructive. Besides returning the data from the
440 annotation, it also removes the annotation from the list and destroys
441 it. Note that with these methods it is impossible to distinguish the
442 case where an annotation exists but has a `NULL' data field from the
443 case where the annotation does not exist. If you want to retrieve the
444 actual annotation objects instead of just their data fields, the
445 annotation list (*note Annote Lists::.) provides `peek_annote' and
446 `get_annote' methods to do that.
448 When some kinds of SUIF objects (e.g. symbols and types) are copied,
449 the annotations are omitted. If you want to copy the annotations as
450 well as the base objects, the `copy_annotes' method must be called
451 separately. This method works for any two SUIF objects; they do not
452 have to be the same kind. If the target object already has some
453 annotations, the new ones are appended to the end of the list.
454 Unregistered annotations are not copied.
456 The `suif_object' class provides a `print_annotes' method for
457 printing the annotation list to a text file. This is used by the
458 `print' methods for the derived classes, but it could also be used
459 directly by users. The optional `depth' parameter specifies the
460 indentation level. Beware that a new-line character is printed
461 *before* each annotation and thus you probably want to print a new-line
462 after calling this method.
464 The `num_output_annotes' method checks to see if an object has any
465 annotations, and if so, it counts the ones that will be written to the
466 output file. This is primarily used by the SUIF library and most users
467 will not need it.
469 \x1f
470 File: suif1.info, Node: Annote Lists, Prev: SUIF Objects, Up: Annotations
472 Annotation Lists
473 ================
475 Annotations are stored on lists attached to SUIF objects. The
476 library defines an `annote_list' class for this purpose. Besides the
477 standard list functions (*note Generic Lists::.), the `annote_list'
478 class provides two additional methods. The `peek_annote' method
479 searches through the list for an annotation with the specified name. It
480 returns a pointer to the first such annotation or `NULL' if the search
481 was unsuccessful. The `get_annote' method does the same thing, but it
482 removes the annotation from the list.
484 \x1f
485 File: suif1.info, Node: Cloning, Next: Fortran, Prev: Annotations, Up: Top
487 Replicating Trees and Instructions
488 **********************************
490 Many SUIF programs need to duplicate parts of abstract syntax trees
491 or expression trees. For example, loop transformations such as
492 unrolling and peeling require copies of the loop bodies, and entire
493 procedures must be copied to implement procedure inlining. Because code
494 replication can be quite complicated in SUIF, it is handled in the
495 library by the "cloning" methods.
497 Several different kinds of SUIF objects can be cloned. The
498 `tree_node', `tree_node_list', `instruction', and `operand' classes
499 have `clone' methods. The various derived `tree_node' classes also
500 have wrapper methods to cast the result of the base class `clone'
501 method to the appropriate pointer types. When an object is cloned,
502 everything within it is recursively cloned. In addition to the child
503 nodes and instructions, this includes symbol tables and the types and
504 symbols within them. All of the known references to cloned objects
505 (including those in registered annotations) are updated.
507 The complexity of cloning is primarily due to SUIF's scope rules.
508 The code being copied may reference symbols and types that are not
509 visible in the scope where the copy will be used. Thus the cloning
510 process is divided into three steps:
512 1. The code to be copied is scanned for references to symbols and
513 types that are not visible in the specified destination scope.
514 These are referred to as "exposed references".
516 2. The exposed references are resolved in the symbol table for the
517 destination scope. New variables are created to replace the
518 exposed variables. Types are usually moved up in the symbol table
519 hierarchy so that they are visible in both the source and
520 destination scopes.
522 3. The code is actually copied. Symbol tables nested within the code
523 are copied and references to them and their contents are updated
524 to use the copies. Similarly, the exposed references are replaced
525 with references to any new symbols or types that were created in
526 the previous step.
528 Each of these steps is described in more detail below. The methods
529 that perform the individual steps are available to users who need more
530 control over the cloning process. For example, you may want to insert
531 code to initialize new variables that are created in the destination
532 scope due to exposed references. The cloning methods can also be used
533 to replace references to particular symbols or types without actually
534 copying anything.
536 The `replacements' structure is used throughout the cloning process
537 to keep track of exposed references and objects that have been replaced.
538 This structure includes lists of symbols, types, variable definitions,
539 symbol tables, and instructions. For each kind of object, there are two
540 lists. Except in intermediate steps, these lists should be the same
541 length. An entry on the first list refers to an object in the original
542 code and the corresponding entry on the second list is a new object that
543 has been created to replace the original.
545 * Menu:
547 * Finding Exposed References:: Finding things not visible at the destination.
548 * Resolving Exposed References:: Creating replacement objects.
549 * Copying the Objects:: Copying the code and updating references.
551 \x1f
552 File: suif1.info, Node: Finding Exposed References, Next: Resolving Exposed References, Prev: Cloning, Up: Cloning
554 Finding Exposed References
555 ==========================
557 The first step in the cloning process is to scan through the code
558 being copied to search for references to objects that are not visible
559 in the destination scope. The `tree_node_list', `tree_node',
560 `operand', `instruction', and `block_symtab' classes have
561 `find_exposed_refs' methods to perform this operation. The results are
562 returned in a `replacements' structure by putting the exposed
563 references in the lists of original objects. The lists of new objects
564 are left empty.
566 Besides checking for exposed references in the objects themselves,
567 the `find_exposed_refs' methods also check for references contained in
568 annotations attached to the objects. Both flat and structured
569 annotations are checked, but unregistered annotations are ignored since
570 they are not copied. The `find_annote_refs' method is used to check a
571 `suif_object' for exposed references.
573 Label symbols are a special case. Even if a label symbol is visible
574 in the destination scope, it must be replaced if the label instruction
575 is to be cloned. Otherwise, there would be two label instructions
576 sharing the same label symbol! Thus, the `find_exposed_refs' method
577 adds the symbol in a label instruction to the list of exposed
578 references. The exception to this is that label symbols that are
579 defined within cloned symbol tables will automatically be replaced and
580 are not included in the exposed references.
582 \x1f
583 File: suif1.info, Node: Resolving Exposed References, Next: Copying the Objects, Prev: Finding Exposed References, Up: Cloning
585 Resolving Exposed References
586 ============================
588 After the exposed references have been found, the destination scope
589 must be updated to include definitions for the objects in the exposed
590 references. The `base_symtab' class provides the
591 `resolve_exposed_refs' method to accomplish this. This method takes
592 the lists of original objects in the `replacements' structure produced
593 by the `find_exposed_refs' method (*note Finding Exposed References::.)
594 and adds corresponding entries to the lists of new objects. New
595 symbols are created and added to the symbol table to replace the
596 originals. Variable definitions are also created as needed.
598 Because some types use name equivalence, they cannot be copied
599 without creating different types. Thus, whenever possible, types are
600 moved up in the symbol table hierarchy so that they are visible in both
601 the source and destination scopes. If a type is successfully moved,
602 the old and new entries for the `replacements' lists are the same. Some
603 types contain references to variables (e.g. as array bounds), and if
604 those variables are not already visible in the destination scope, the
605 types cannot be moved. When that happens, `resolve_exposed_refs'
606 resorts to making a new type where the variable references are updated
607 to use the cloned variables.
609 \x1f
610 File: suif1.info, Node: Copying the Objects, Prev: Resolving Exposed References, Up: Cloning
612 Copying the Objects
613 ===================
615 Once the exposed references have been resolved, the code can be
616 copied. The `tree_node_list', `tree_node', `operand', `instruction',
617 `block_symtab', and `proc_symtab' classes have `clone_helper' methods
618 to perform the actual copying. These methods change references to
619 objects in the original objects lists of the `replacements' structure
620 to references to the newly created replacements.
622 Annotations on the objects are also cloned. The `clone_annotes'
623 method is used to copy the annotations from one `suif_object' to
624 another. Unregistered annotations cannot be copied because the
625 structure of their data fields is unknown. The `clone_helper' methods
626 call `clone_annotes' for each object that is cloned; you generally do
627 not need to call it directly.
629 The `clone_helper' and `clone_annotes' methods can also be used to
630 perform another related function. It is occasionally necessary to
631 replace references to one set of objects with references to another set
632 of objects. Since the cloning methods do that anyway, it is easy to
633 have them update the references without actually making copies. Setting
634 the `no_copy' parameter causes them to update the references as
635 specified in a `replacements' structure without copying the objects.
637 \x1f
638 File: suif1.info, Node: Fortran, Next: Generics, Prev: Cloning, Up: Top
640 Features for Compiling Fortran
641 ******************************
643 SUIF is roughly based on C semantics and does not directly support
644 some Fortran features. In particular, call-by-reference parameters
645 occur frequently in Fortran programs and must be implemented in terms of
646 other SUIF features. This introduces extra complexity that makes it
647 harder to analyze and optimize the procedures. Fortunately this
648 complexity can be hidden somewhat by converting the procedures to the
649 SUIF Fortran form. The SUIF library provides functions to translate a
650 procedure to this Fortran form after it is read from a file and to
651 translate it back to the original SUIF form before it is written out.
652 Common blocks and equivalences are generally handled using
653 sub-variables, so the library's Fortran form does not need to do
654 anything special to deal with them. Other more obscure Fortran
655 features are also not handled in the Fortran form because they are less
656 common and hard to deal with however they are represented.
658 * Menu:
660 * Call-By-Ref Parameters:: Passing parameters by reference.
662 \x1f
663 File: suif1.info, Node: Call-By-Ref Parameters, Up: Fortran
665 Call-By-Reference Parameters
666 ============================
668 Procedure parameters in Fortran are passed by reference. SUIF uses
669 call-by-value parameters and implements call-by-reference parameters by
670 passing pointers to the actual arguments. When the formal parameters
671 are used, the pointers must be dereferenced. However, one of the
672 primary advantages of compiling Fortran programs is that there are no
673 pointers in the source code. If not for the call-by-reference parameter
674 pointers, most compiler passes that only deal with Fortran can be
675 simplified by not having to deal with pointers. Thus the SUIF Fortran
676 form automatically converts the code to make it appear that the
677 parameters are passed by reference. The parameters are changed to
678 call-by-reference types instead of pointers and the pointer dereferences
679 are temporarily removed.
681 The `make_ref_params' function is used to convert call-by-reference
682 parameters in a procedure to the Fortran form. It must be called before
683 converting the procedure body to expression trees. This is done
684 automatically by the `read_proc' method for a `proc_sym' if the
685 `use_fortran_form' flag is set. Before writing a procedure to an
686 output file, the call-by-reference parameters must be converted back to
687 pointers using the `undo_ref_params' function. Since it is illegal to
688 write out a procedure in the Fortran form, the `write_proc' method for
689 the `proc_sym' always calls `undo_ref_params'; you do not need to call
690 it directly. Both `make_ref_params' and `undo_ref_params' are defined
691 in the file `callbyref.cc'.
693 The Fortran front-end must identify call-by-reference formal
694 parameters by putting `call_by_ref' annotations (*note Call-By-Ref
695 Annotes::.) on the pointer types used by those parameters. Before
696 actually changing the type of a call-by-reference parameter and
697 removing its dereferences, `make_ref_params' checks that the pointer
698 parameter is neither addressed nor assigned within the procedure. If
699 this check fails, the pointer is not a valid call-by-reference
700 parameter, so `make_ref_params' prints a warning message and does not
701 convert that parameter. Otherwise, it goes ahead and changes the type
702 of the parameter from a pointer to a call-by-reference type (*note
703 Modifier Types::.). Any dereferences of that pointer within the
704 procedure are removed, and other references to the pointer are changed
705 to `ldc' (load constant) instructions that take the address of the
706 parameter. The end result of all this is that it appears that the
707 parameters are passed by reference. Note that the call sites are not
708 changed; the actual arguments for call-by-reference parameters are
709 still passed as pointers.
711 The `undo_ref_params' function does as its name suggests and undoes
712 the transformations applied by `make_ref_params'. The only potential
713 complication is that while in the Fortran form the user may have used
714 the call-by-reference parameters in ways that cannot be expressed
715 outside of the Fortran form. Specifically, the call-by-reference
716 parameters cannot be used as index variables of `for' loops (*note For
717 Nodes::.), and they cannot be used as bounds in array types (*note
718 Array Types::.). Both of those uses require direct references to
719 variable symbols, and there is no place to insert the pointer
720 dereferences required outside of Fortran form.
722 \x1f
723 File: suif1.info, Node: Generics, Next: Other, Prev: Fortran, Up: Top
725 Generic Data Structures
726 ***********************
728 The SUIF library includes a number of generic data structure classes.
729 Some of these are used extensively by the library itself, while others
730 are only provided for your convenience. Since most of these data
731 structures are quite easy to understand, this section only gives a brief
732 description of each one and points out the unusual and potentially
733 confusing features.
735 * Menu:
737 * Generic Lists:: Generic lists (base list class).
738 * Move-to-front Lists:: Move-to-front lists.
739 * Association Lists:: Lists with search keys.
740 * Doubly-Linked Lists:: Doubly-linked lists.
741 * Bit Vectors:: Bit vectors.
742 * Hash Tables:: Hash tables.
743 * Extensible Arrays:: Variable-size arrays.
745 \x1f
746 File: suif1.info, Node: Generic Lists, Next: Move-to-front Lists, Up: Generics
748 Generic Lists
749 =============
751 While linked lists are not very efficient data structures, they are
752 flexible and work well for a research compiler like SUIF. Various kinds
753 of lists are used throughout the SUIF library and most SUIF programs.
754 Almost all of these lists are derived from the `glist' base class. The
755 files `glist.h' and `glist.cc' contain the declaration and
756 implementation of this class.
758 The individual elements of these lists are derived from the
759 `glist_e' class. The base class only contains a pointer to the next
760 element. To make a useful list, a derived class must add data fields
761 to the list elements. For doubly-linked lists, the list elements are
762 further extended to include backwards pointers (*note Doubly-Linked
763 Lists::.).
765 The `glist' class includes pointers to the head and tail elements.
766 This makes it possible to efficiently add elements at either end of the
767 list. A variety of methods are provided to insert and remove individual
768 elements, as well as to combine entire lists in different ways. All of
769 these operations are straightforward and are clearly documented in the
770 code.
772 The SUIF library also provides iterators for lists. This allows you
773 to write code at a higher level of abstraction. Instead of rewriting
774 the same code everywhere that your program traverses lists, you can
775 just use the built-in iterators. The base iterator class is
776 `glist_iter'. An iterator is initialized with a pointer to a
777 particular list. It then returns successive elements from the list
778 (via the `step' method) until the `is_empty' method returns `TRUE'.
779 Other methods are available to access the current and next list
780 elements without advancing the iterator.
782 To make a list with a particular type of elements, one must derive
783 new list classes that inherit from the base classes described above.
784 While this is not difficult, it is cumbersome and time consuming.
785 Instead of explicitly declaring these derived classes, the
786 `DECLARE_LIST_CLASS' macro may be used to declare them automatically.
787 This macro takes two arguments: the name of the new list class and the
788 type for the data in the list elements. It then creates classes
789 derived from `glist', `glist_e', and `glist_iter' that use the
790 specified type for the element data (1). For example,
791 `DECLARE_LIST_CLASS(string_list, char*)' generates classes named
792 `string_list', `string_list_e', and `string_list_iter'. The
793 `string_list_e' class includes a `contents' field with type `char*'.
794 The methods in all of these classes are changed to use the `char*' type
795 where appropriate and some new methods are added. (Once the element
796 data type is known, it is possible to provide methods, such as `copy',
797 that must access the data fields.)
799 The `DECLARE_LIST_CLASS' macro is implemented by other macros, one
800 for each kind of class. Using these other macros directly gives you
801 more control over the names of the new classes and allows you to add
802 more methods in the derived classes. There are several examples of this
803 in the library code. Another advanced feature of the
804 `DECLARE_LIST_CLASS' macro is the virtual `set_elem' method which is
805 included in the generated list class. This method is called for every
806 element that is added to a list. The base `set_elem' method does
807 nothing, but a derived class can change this method to automatically
808 update information in list elements when they are added to a list.
810 ---------- Footnotes ----------
812 (1) C++ templates would be a better solution, but at the time when
813 this was developed, we did not have a C++ compiler with a robust
814 implementation of templates.
816 \x1f
817 File: suif1.info, Node: Move-to-front Lists, Next: Association Lists, Prev: Generic Lists, Up: Generics
819 Move-to-front Lists
820 ===================
822 The move-to-front list class `mtflist' is just a minor variation of
823 the `glist' class. *Note Generic Lists::. The user must provide a
824 function that compares a list element with some other unspecified
825 object. The `mtflist' class then provides a `lookup' method that uses
826 the comparison function to search for a particular element. After
827 every successful lookup, the returned element is moved to the front of
828 the list. This works well for applications with good locality. The
829 `DECLARE_MTFLIST_CLASS' macro works just like the `DECLARE_LIST_CLASS'
830 macro, but it generates move-to-front list classes. The code for the
831 `mtflist' class is in the files `mtflist.h' and `mtflist.cc'.
833 \x1f
834 File: suif1.info, Node: Association Lists, Next: Doubly-Linked Lists, Prev: Move-to-front Lists, Up: Generics
836 Association Lists
837 =================
839 An association list element contains both a key and a data pointer.
840 The data associated with a particular key can be retrieved with a simple
841 lookup method. The key and data fields are both `void*' pointers.
842 Association lists are implemented by the `alist' and `alist_e' classes
843 in the files `alist.h' and `alist.cc'. These classes are derived from
844 the generic list classes (*note Generic Lists::.) and behave similarly.
846 The `amtflist' class has the same interface as the `alist' class and
847 provides the same functionality. The only difference is that it is
848 based on the move-to-front list class. *Note Move-to-front Lists::.
849 You may want to use this if you expect your application to access list
850 elements with a high degree of locality.
852 Like all of the other SUIF lists, the association lists have
853 iterators to make it easy for you to traverse them. The `alist_iter'
854 class uses the same interface as the generic list iterator and works
855 for both `alist' and `amtflist' objects.
857 \x1f
858 File: suif1.info, Node: Doubly-Linked Lists, Next: Bit Vectors, Prev: Association Lists, Up: Generics
860 Doubly-Linked Lists
861 ===================
863 For some applications, especially those where it is necessary to
864 traverse lists in both directions, doubly-linked lists work much better
865 than singly-linked lists. The `dlist' class provides doubly-linked
866 lists with the same interface as the generic lists. *Note Generic
867 Lists::. Thus you can interchange these data structures without having
868 to rewrite your code. The `dlist_e' elements are derived from the
869 generic list element class but they also include the backwards link
870 fields. The `dlist_iter' iterator works like the standard `glist_iter'
871 iterator, and the `DECLARE_DLIST_CLASS' macro is the same as the
872 `DECLARE_LIST_CLASS' macro except that it produces doubly-linked lists.
873 All of these things are implemented in the `dlist.h' and `dlist.cc'
874 files.
876 \x1f
877 File: suif1.info, Node: Bit Vectors, Next: Hash Tables, Prev: Doubly-Linked Lists, Up: Generics
879 Bit Vectors
880 ===========
882 Bit vectors are frequently used in compilers to represent sets of
883 integers, particularly for data flow analysis. The SUIF library
884 includes a `bit_set' class with an extensive collection of methods.
885 This class is implemented in the `bitset.h' and `bitset.cc' files.
886 When you create a new `bit_set', you must specify the range of integers
887 which it may contain.
889 The `bit_set_iter' class provides an easy and efficient way to
890 iterate through the entries in a `bit_set'. This iterator is slightly
891 different than the SUIF list iterators. You must call the `is_empty'
892 method once before each call to the `step' method. Other than that, it
893 is straightforward.
895 \x1f
896 File: suif1.info, Node: Hash Tables, Next: Extensible Arrays, Prev: Bit Vectors, Up: Generics
898 Hash Tables
899 ===========
901 SUIF hash tables are implemented by the `hash_table' class in the
902 files `hash.h' and `hash.cc'. Each hash table is a fixed-size array of
903 `hash_chain' buckets. A `hash_chain' is just a move-to-front list.
904 *Note Move-to-front Lists::. The entries in a hash table are derived
905 from the `hash_e' class, which contains a single unsigned value used as
906 the signature.
908 If you wish to store pointers in a hash table, you can use the
909 `hash_e' class directly (assuming that the pointers can fit into the
910 unsigned signature fields). Otherwise, you need to create a derived
911 `hash_e' class. The only other thing needed is a function to compare
912 two `hash_e' entries to determine if they are equal. You can then
913 create a new `hash_table' object. Even if you are using a derived
914 `hash_e' class, it may be easier to just type cast the pointers than to
915 derive a new `hash_table' class that includes the correct type casts.
917 The hash table `enter' method tries to add a new entry. If the
918 entry was already in the table it returns `TRUE' and does not enter a
919 duplicate; otherwise, it adds the new entry and returns `FALSE'. The
920 `lookup' method checks to see if a particular entry is in the table.
921 If so, it returns the pointer to the entry.
923 \x1f
924 File: suif1.info, Node: Extensible Arrays, Prev: Hash Tables, Up: Generics
926 Extensible Arrays
927 =================
929 Arrays are very efficient data structures but they can only be used
930 when their size is known in advance. For situations where the number of
931 elements is not even known at run-time, most programmers resort to using
932 linked lists. SUIF provides a compromise. Extensible arrays provide
933 almost the same efficiency as arrays without requiring a bound on the
934 number of elements. They are not as flexible as linked lists, however,
935 because it is still not possible to insert new elements in the middle of
936 an extensible array.
938 Extensible arrays are implemented by the `x_array' class in the
939 files `xarray.h' and `xarray.cc'. When an `x_array' is first created,
940 you must specify the number of elements to be allocated in the first
941 chunk of memory. If more elements are needed later, additional chunks
942 of the same size will be allocated automatically. The `ub' method
943 returns the number of elements that are currently in an `x_array'.
945 The elements of an `x_array' cannot be referenced until they are
946 added to the array. New elements can only be added at the end of an
947 array by using the `extend' method. In this way an `x_array' behaves
948 like a linked list. Elements must be appended (with `extend') to the
949 end of an array before they can be used.
951 The `x_array' class also provides an `operator[]' method so that
952 once an element has been entered in an `x_array' it can be referenced
953 using the standard array reference syntax. This works regardless of
954 which chunk of memory contains the element.
956 Each element of an `x_array' is a `void*' pointer. You can cast
957 these pointers to any other type that fits in the same amount of
958 storage. A better solution is to use the `DECLARE_X_ARRAY' macro to
959 derive a subclass of `x_array' with elements that are pointers to the
960 correct type. This macro takes three arguments: the name of the
961 derived class, the type to which the elements should point, and the
962 default chunk size. As with the macros for creating new list classes,
963 this is just a cheap substitute for templates.
965 \x1f
966 File: suif1.info, Node: Other, Next: Appendix, Prev: Generics, Up: Top
968 Other Features of the SUIF Library
969 **********************************
971 This chapter describes various features of the SUIF library that are
972 too small to warrant separate chapters. These include immediate values
973 and symbolic addresses, which are used in annotations and `ldc'
974 instructions, the `lexicon', in which almost all character strings are
975 entered, the `machine_params' structure, which records a variety of
976 parameters for the target architecture, and a variety of functions for
977 initializing the library, handling errors, and iterating through
978 procedures.
980 * Menu:
982 * Immeds:: Immediate values.
983 * Symbolic Addresses:: Symbolic addresses used in immediate values.
984 * Lexicon:: All character strings are stored in this table.
985 * Target Machine Parameters:: Various parameters for the target architecture.
986 * Initialization:: Initializing and finalizing SUIF libraries.
987 * Command-Line Parser:: Extracting options from the command-line.
988 * Error Handling:: Errors, warnings, and assertions.
989 * Procedure Iterators:: Code for visiting all procedures in a program.