5 Added method to replace in array of a node in irnode.c/h
6 Added funcionality to irgmod:
7 * collect all Phi nodes as link-list in the Blocks link field
8 * collect all Proj nodes as link-list in node producing the tuple.
9 * Seperate a Block into two
10 Added inlining transformation in irgopt.h
11 Improved output of dump_ir_block_graph. Now also dumps nodes that
12 don't belong to a block.
13 Added flag opt_unreachable_code, opt_inline.
14 Changed irvrfy so that it accepts nodes with Bad predecessors.
17 renamed get_type_nameid to get_type_ident
20 Bugfix: dead node elimination did not replace the hash table
24 Added routine remove_irp_irg.
25 Changed comment to free_ir_graph.
28 Added routine to free irgraphs.
31 Improved add routines to sub, supertype in type.c
34 Added implementation of overwrites stuff.
37 Implemented stuff to change the type graph. See
38 typegmod.h and tpop.h for basic documentation of the change.
39 There now exists a type of kind type_id. If this appears
40 externally this is a bug.
43 Added some new access routines to types.
44 List of overwritten fields for entities.
45 Removed a bug in irnode.
48 Added a routine to set the mangled entity name.
49 Added two routines to copy entites.
52 Entities now have two more flags, for visibility and allocation mode.
53 Types that have a layout have a flag indicating whether the layout is
57 We distinguish three kinds of Cond nodes. These can be distinguished
58 by the mode of the selector operand and an internal flag of type cond_kind.
59 First we distinguish binary Conds and switch Conds.
60 A binary Cond has as selector a boolean value. Proj(0) projects the control
61 flow for case "False", Proj(1) the control flow for "True". A binary Cond
62 is recognized by the boolean selector.
63 The switch Cond has as selector an unsigned integer. It produces as result
64 an n+1 Tuple (cf0, ... , cfn) of control flows.
65 We differ two flavours of this Cond. The first, the dense Cond, passes
66 control along output i if the selector value is i, 0 <= i <= n. If the
67 selector value is >n it passes control along output n.
68 The second Cond flavor differes in the treatment of cases not specified in
69 the source program. It magically knows about the existence of Proj nodes.
70 It only passes control along output i, 0 <= i <= n, if a node Proj(Cond, i)
71 exists. Else it passes control along output n (even if this Proj does not
72 exist.) This Cond we call "fragmentary". There is a special constructor
73 new_defaultProj that automatically sets the flavor.
74 The two switch flavors are distinguished by a flag of type cond_kind.
75 Default flavor is "dense"
79 tv now implements Minus, Abs.
80 iropt now optimizes these and Div, Mod, Quot, DivMod.
81 Still missing: Shrs, Rot.
82 tarval_shr somtimes performs shrs, depending on the compiler/system!!
83 If the ArmRoq implementation is faulty there might appear errors.
86 Changed ircons: If undefined values are used the Phi construction
87 inserts a constant with value tarval_bad.
90 Changed array bounds in type.h to ir_node*. This allows to
91 construct array bounds that are complex constant expressions
92 simpler. Further dynamic array bounds can be displayed.
93 Comment in ircons.c extended: undefined values in start_block.
96 ifdef'ed all uses of gmp in tv.c away. Optimizations for
97 mode_Z no more supported, as well as constants of that mode.
100 Dokumentation in ir_dump
101 Habe Routinen fuer einzelne Knoten/Kanten aus header entfernt:
102 Benutzen globale Variable die nicht oeffentlich zugaenglich ist.
105 We need an entity for the array elements for the Sel nodes. This
106 entity should be stored in the array type. Changed constructor
107 parameters: include array element type. Entity for elements is built
112 Faulty use of va_arg, became visible with new, stricter gcc 2.96.
115 Added list of member entites to union. unioned_types and delimiters
116 are superfluous now -- removed.
117 Rationale: we want to express selection of a union member as a Sel
118 node. for this we need to have entities. The entities contain the
119 unioned type and have as name the delimiters...
122 Changed Makefile/MakeTargets to install headers and libraries
126 Changed Makefile and Configure scripts to produce a proper tar file
127 for distribution (libfirm-VERSION.tar)
128 Use 'make distrib' instead of 'make dist'
131 Changed implementation of tr module. With this I also changed the
132 interface!! Type casts are unnecessary now, but some access funcions
136 ======================================================================
137 ==================== New version: 0.3.0 ==============================
138 ======================================================================
144 added creation of a tar archive for distribution
145 replaced ir/.dummy.in by ir/Makefile.in
148 Changed equivalent_node() and copy_preds() so that the end block
149 is not optimized away if it has no real predecessors. This fixes
150 the problem with the while examples.
151 Added while_example in Makefile
154 Fooled around with if_while_example: Why does cse make it abort?
155 Cse removes path to End node, Bad remains as pred of Endblock.
156 The block walker can't deal with this.
157 Made new example with only loop: while_example.
160 added auto documentation in Makefiles, configure, etc
161 example in ir/ir/ircons.c - much must be added
162 creation of documentation by 'make autodoc' in architecture directory
165 added lots of #ifdef HAVE_CONFIG_G #include "config.h" #endif
166 replaced some C++ style comments (//) by standard C comments /**/
169 - configure (with some features, see --help for more)
170 - make [depend | tags | install]
171 - make [run] in testprograms
173 - compilation on SunOS
175 - automatic call of autoconf if required
178 More colours in vcg output.
179 Fixed bug: cse found that start block equals it's
180 first successor as both have the Start block as predecessor.
181 This only happens for local_optimize_graph() as during construction
182 the Start block is not entered in the value table.
183 Changed implementation: irgmod: local_optimize_graph() did not
184 empty the hash table with the irnodes for cse. This might cause that
185 cse turns up with a node that seems better but was removed from the
186 graph in an earlier optimization phase.
187 Removed old #if 1 from ircons.c
188 Commented in call of optimization for Block nodes in irgopt.c, copy_preds():
189 Optimizes blocks that had bad predecessors.
194 Moved struct from irprog.h to irprog_t.h, same for irmode.h.
195 Added a module deb_info in debug.h. Adapted makefile. Added example
197 Removed use of debug.h in ident.c. Now debug.c|h can be moved to
199 Removed inabled code for dead node elimination in irgopt.h.
200 Renamed some missnamed access routines (_of_). Macros with old names
201 are in old_fctnames.h.
202 Edited makefiles to remove #* and *.flc.
205 Some minor bugfixes...
208 After compacting of in arrays in dead_node_elimination
209 merge blocks and remove Phis with one pred.
212 Freeing of obstack in dead_node_elimination commented in.
213 Compacting in arrays of Block and Phi nodes in dead_node_
218 added set/get_SymConst_type_or_id in irnode.h
219 added field offset to entity in entity.h
220 added field size to type_class in type.h
221 include "gmp.h" in tv.h with "" instead <>
224 Some changes to make the lib better portable
227 Initialize max_node_nr in irprog.
230 Now outputs warning if faulty type in irdump, dump_type_info.
231 Explicit string termination in irdump, vcg_open.
234 Added external to declaration of irp.
235 Added typedef before pns and pnc_number.
236 irmode.c, init_mode(): We need to memset all new modes as
237 tarval_vrfy reads fields before they are initialized: It
238 compares to min/max when tarvals for min/max are allocated!
241 Changed parameter of Methods in type.h and type.c from
242 class to clss. Class is a C++ keyword.
245 Changed some testprograms to accomodate Uebprakt.
248 Finished implementation of dump_all_types.
249 Added new testprogram inheritance_example.
252 Added seven access routines in type.[hc]:
253 get_class_n_member, get_class_n_subtype, get_class_n_supertype,
254 get_strct_n_member, add_strct_member, get_strct_member and set_strct_member.
255 Fixed the type_walk_2 for those seven routines.
258 Added irdump routine dump_all_types.
259 Did changes to irprog, type, typewalk to achieve this.
260 typewalk needs to walk along members, sub and supertypes, this
261 is still missing! irdump then needs to output these edges.
263 ======================================================================
264 ==================== New version: 0.2.5 ==============================
265 ======================================================================
268 Made new Version: 0.2.5
270 15.8.2000 Goetz until 3.9.00
271 Separated irnode.h and many others into two files: one public
273 Added funcionality to extract headers for lib.
276 type_dump also dumps irg->ent
277 if_example: corrected nr of locals
280 irgopt: Correct copy of self pointer in start block.
281 irgopt: Correct treatment of loops: pre function in walker
282 breaks all possible loops in Phi and Block nodes.
283 irr_loop_example: wrong Return statement
284 Now I fixed all but one error: in memory_example.
285 This error showed a conceptual problem, so I wrote
286 a slightly different algorithm. This now runs for
288 dead_node_example: cse is buggy!! merges start and the
292 looking at bug in dead_node_elimination.
294 irnode: all get_..._arr functions changed
295 ircons: new_r_Block: set matured flag.
296 ircons: new_r_SymConst: needs mode_p for linkage_ptr_info.
297 adapted call_str_example to new concepts.
300 Implemented simpler Phi construction algorithm that constructs
301 correct code for three_cfpred_example in ircons. This algorithm
302 generates more Id nodes than the original algorithm and therefore
304 Also made some changes to optimizations of Not.
307 Fixed a bug, caused by the recursive use in type.h and entity.h.
308 Deleted the _TYPE_TYPEDEF_ and inserted the _ENTITY_TYPEDEF_ instead.
309 Fixed a problem in if_while testprogram, so it now works.
312 Fixed bug in optimize(). Returned Null instead n if
313 get_optimize() == false.
316 Added some access routines in type.[hc]. Solved a recursive definition
317 of type_class struct, entity struct and type union.
320 Separated entity header into pure functional header and header
324 ... a bunch small changes not documented
327 Changed output of oo_prog_example: now uses the internal list
328 of all irgs. Had to implement some of the access routines for
329 that. Also fixed a bug in irdump. Main routines did not use
330 current_ir_graph properly.
333 Implemented some missing parts in irgopt.
334 Added field irg to entity. Only valid if entity is a method.
335 Had to resove a cyclic de[endency between irgraph.h and entity.h
337 Added fields sub and super to type_class for inheritance.
338 Added field main_irg to irprog.
341 Fixed some bugs in irgopt.c
342 Added some missing 'get_new_node' methods, so the new obstack contains
346 Renamed ir_vrfy to irn_vrfy and vrfy_graphg to irg_vrfy.
347 Solved some copy'n'paste problems. Deleted most debug-code!
348 Added comments to several files.
351 Fixed bug in _r_ constructors for all four Div operations.
352 Fixed bug in turn_into_tuple: didn't remember the block.
353 Tested transform_node.
356 Fixed some testprograms to new semantics of firm.
357 Added testprogram global_var_example.
358 Fixed a bug in irop: Size of Sel node was (entity *) instead of
359 sel_attr. Therefor array_heap_example aborted.
360 Also found a missing break in typewalk, case iro_Alloc.
361 Added a construct that unifies all things constructed by the lib
362 and needed to represent a program: irprog.ch
363 This contains a list of all types as well as a list of all ir graphs.
364 I added calls to initialization and constructors so that this is constructed
365 automatically. I changed firm.c, type.c, irgraph.c and ev. more.
366 Removed strange block struct and constructor from ircons.c.
367 Moved routines for automatic Phi construction from irgmod to ircons.
368 Sorted functions in ircons to reflect the different interfaces.
369 Renamed dataseg to globals to be conformant with documentation.
370 Added conservation of current_ir_graph to irgopt.c.
371 Corrected bug in Makefiles: wrong path to directory ./inlude.
374 Commented a whole bunch of stuff, e.g. in ircons.h (Procedure to construct)
375 We should change the naming of the Block constructor.
376 Removed acces routines to attr. "closed" of Block.
377 Removed second implementation of new_ir_node from ircons and some comments
378 concerned with the now resolved cyclic dependency.
379 Fixed some bugs in irgopt so that the compilation goes through.
382 Changed the irnode attribut 'visit' into 'visited'.
383 Added some access functions, like get/set_irn_visit etc.
386 Renamed some access funtion in irgraph.*.
387 Deleted two global flags (ir_visited and block_visited) from irgraph.*.
388 Added two attributes to the irgraph struct. The visited flags belongs
389 to a ir graph, not to a whole program.
392 A new optimization has been finished. The dead-node-elimination copies
393 the existing ir graph from one opstack to another. While walking the
394 graph, only the reachable nodes will be copied, so the "dead-nodes"
395 (unreachable in the controlflow) are removed.
398 Solved some problems in the 'copy_node' function. The in array was not
399 as easy as it seamed.
402 Wrote a new 'post' funtion, for future use in 'dead-node-elimination'
403 optimization, which is needed in the paramter list of 'irg_walk'.
406 Moved 'optimze_in_place_wrapper' from iropt.* tothe new files irgopt.*.
407 New functions 'local_optimze_graph' and 'dead_node_elimination' are added,
411 Removed some files from the archive, after dependencies and usage are
413 - 'ir/common/strerror.c'
415 - 'ir/ident/xx_ident.h'
416 an empty file, only included by 'ident.c', but never used;
417 - 'ir/tv/label.c' and
419 contained a numeric counter;
420 The files were included in 'tv.h' and implemented in 'tarval.c'. The two
421 functions 'tarval_label' and 'tarval_forall_labeled' were also never used.
422 In the old fiasco compiler, the label thing is used in the backend.
423 Search for 'babil' to see the usage.
424 Also removed the two attributes 'lab' and 'used' in the tarval struct.
427 Moved the 'new_ir_node' constructor from ircons.* to irnode.* and fixed
428 afterwards some recursive includes, so libfirm works again.
431 Did a lot of changes, which I never commented until now (4.7.00).
433 * Added new result to Start node: Pointer to global data segment.
434 * Extended Semantics of SymConst node to represent information for the
436 * Added arithmeitc nodes (Shrs, Minus ...)
438 Rearranged the directory structure and adjusted the makefiles.
439 The directories contain:
440 ir: everything for the intermediate representation (better: src?)
441 /ir: the ir itself, and standard optimizations.
442 /tv: the target value module
443 /tr: the type and entity representation
444 /adt: abstract data types
445 /common: stuff needed by all other dirs
446 /debug: debugging Unterstuetzung
448 include: external files needen as includes
449 testprograms: examples to test the lib.
451 The makefiles generate files with extension .d that contain the dependencies
455 Added access routine to attribute link of irnode in irnode.ch.
456 Added get_negated_pnc to irnode.ch.
459 Added an iterator in iropt that calls the optimization for all nodes.
460 Copied optimize's code to optimize_in_place and removed deallocations.
461 Made set_irn_n in irnode.c public.
462 Added Bad as possible cfg predecessor in is_cfg_node in irnode. Bads
463 are allowded as cfgpredecessors to represent dead "incoming" control
465 Added call to optimize_in_place in mature_block. Is this useful?
468 Changed tests from comparing enums to comparing pointers. This is more
469 efficient (is it?) and reads better. e.g., instead get_irn_opcode == irm_And
470 now get_irn_op == op_And
473 Compared equivalent_value to the one in the original fiasco.
474 Added a test in case iro_And.
475 Changed implementation of iro_Div. Added routines turn_into_tuple
476 and set_irn_op() in irgmod/irnode.
477 Changed implementation of irn_Minus (although commented out).
478 Now all features are ported or documented for this function.
481 Compared computed_value to the one in the original fiasco.
482 Added one further optimization in case iro_Proj.
483 Now all features are ported for this function.
486 Updated comments in ircons.h.
489 Changed possible attribute of SymConst from type_class to type.
490 SymConst size could be the size of a union, array, ...
493 Implemented two dumpers that dump type information and a graph with
497 Implemented a walker that walks over the type informatin that can
498 be reached from an ir node.
499 Added routine get_kind(firm_thing) in common.h, Added file common.c.
500 Added files typewalk.ch and routines to irdump.
501 Added visited flags and initialization to entity and all types.
502 Implemented some of the missing access routines in type.c, entity.c
505 Implemented constructor for ShrA.
507 Added routine that iterates the graph and verifies all nodes.
508 Added Phi_in stack to irgraph. This allows to build several
509 graphs at once with respect to the Phi building algorithm.
512 Implemented dumper for control flow graphs. Changed irr_* and dead_*
513 examples to dump cfg.
516 Implemeted explicit stack for the Phi node generation. See ircons.c.
519 added include string.h in xoprintf.c to get rid of warning:
520 implicit declaration of function `bcopy'
524 Added more cases to equivalent_node.
525 Portet gigo, identify, identify_remember.
526 The set/pset library can not handle several hash tables. At least,
527 compiling several procedures causes a segmentation fault during access
528 to the tables (oo_program_example). Need to work on this.
529 transform_node still needs to be ported.
530 some cases in equivalent_node are still missing.
532 To get it running I had to remove the call to optimize in the
533 new_Block constructor. It can only be called when the Block is
537 Introduced a walker that walks only over blocks. The asserts
538 might be too strict for general graphs, but so far it works.
539 For the walker I introduced an additional flag in the attribute
540 of Blocks, an a global block_visited variable (in irgraph.h).
541 Furhter I modularized dump_ir_node, implemented dump_ir_graph
542 with the existing walker, and added new routines to output a
544 Changed the examples to call the new dump routine.
547 Added auxiliary routines to ir_node:
548 skip_Proj, skip_Nop, is_Bad ...
549 Changed access routines to use get_irn_n instead of explicit array
550 accesses. Changed get_irn_n to call skip_Id, so that the access routines
551 never will return Id nodes.
554 Repaired Phi computation, changed new_r_Phi_in. Added test program to
555 test irregular controlflow.
558 Updated optimizations computed_value and equivalent_node to new
559 Syntax of FIRM nodes and to use access routines.
560 Added routine skip_Proj in irnode.
562 2.2.2000 Boris Boesler
563 Added files irgwalk.c and irgwalk.h. They include a simple function to
564 traverse an ir graph and execute pre and post functions to current node.
567 Added arrays with parameters and result types to the type informtion
568 of a procedure. This is needed for the code generation. Also added
569 the corresponding access routines.
570 Adapted the testprograms.
573 Found a bug / complication: the call order
574 get_value (makes Phi0, put's it into graph_arr)
575 set_value (overwrites Phi0 in graph_arr)
576 mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
578 fails. Added test wether graph_arr is already set in phi_merge.
580 Added tons of comments to explain Phi generation -- the stack hack.
584 irdump now outputs the pnc_number for projs of Cmp nodes.
585 Added routine to access the pnc_string.
588 Added result "dataseg" to Start node, with all it's consequences.
589 We need this for the compiler lab to translate global variables.
590 Now they can be selected from the data segment, and the start
591 node supplies the pointer to this segment.
592 These changes are guarded by preprocessor variable UEBPRAKT in
594 Changed files: common.h, irgraph.ch, irnode.h
598 removed array_example, added array-heap_example and
599 array-stack_example and adapted makefile.
601 Entity now also allows type_method as owner. This is to model
602 the stack, Sel nodes that select a variable (array) from the
603 stack need an entity that describes what they select. This
604 entity gets the type of the enclosing procedure as owner.
607 Added future access routines in `irmode.[ch]' as comments,
608 that all attributes in the ir_mode struct can be user-defined.
609 Added access routines in `irgraph.[ch]', for all attributes.
612 Moved verify routines from `irgraph.[ch]' to own files `irvrfy.[ch]'.
613 Added `irvrfy.[ch]' to MAKEFILE
614 Added "inline" before access routines in `irnode.h', that no warnings
615 will appear furthermore.
616 Added three more access routines in `irmode.[ch]':
617 struct tarval *get_min_of_mode (ir_mode *mode);
618 struct tarval *get_max_of_mode (ir_mode *mode);
619 struct tarval *get_null_of_mode (ir_mode *mode);
622 Adaption of Alloc, Sel and Entity to new types:
623 Changed array_example to use type instead of type_class.
624 Changed entity to allow all types as owner instead of
625 only type_class. Added routine "assert_legal_owner_of_ent(type* type)".
626 Changed alloc to allow allocating variables of any type instead of
628 Adapted all testprograms to avoid warnings.
630 removed dtest ... from Makefile, replaced by test.
633 Added "run" to makefile, added array_example to makefile of testprograms.
634 Corrected testprogram array
635 Changed assert in irvrfy -- Conv.